How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
The fourteen elements below (1 2 3 4), the noncrossing partitions of a square, and their Kreweras complements
Example
Work in the type- Coxeter system realized as , with , , , and (The finite symmetric group , one-line notation, and cycle notation, is a group under composition, and it is non-abelian whenever has at least three distinct elements, The symmetric group has the Coxeter presentation, Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups, Coxeter elements, the noncrossing interval [1,c], and the Kreweras map w ↦ w⁻¹c (1)). The following finite computations use right-to-left composition.
(1) The interval. With , counting fixed points (The Kreweras complement of [1,c], and the type-A model by noncrossing set partitions (2), Every permutation of a finite set is a product of pairwise disjoint cycles, uniquely up to reordering and cyclic rotation, Support, fixed points, disjoint cycles, cycle length, disjoint-cycle decompositions, and cycle type), the interval has exactly these fourteen elements: the identity; the six transpositions ; the double transpositions and ; the 3-cycles ; and (Coxeter elements, the noncrossing interval [1,c], and the Kreweras map w ↦ w⁻¹c (2), The Kreweras complement of [1,c], and the type-A model by noncrossing set partitions (3)).
(2) The crossing obstruction and the partition model. Of the fifteen partitions of , exactly is crossing in the cyclic order ; its permutation is the unique double transposition absent from (1). The cycle-support partition of every element in (1) is noncrossing and its cycles are cyclically increasing. Conversely, the fourteen noncrossing partitions each give exactly one element of (1), by the type-A criterion and partition isomorphism (The Kreweras complement of [1,c], and the type-A model by noncrossing set partitions (3)–(4)).
(3) Kreweras complements. The map is an order-reversing bijection and (The Kreweras complement of [1,c], and the type-A model by noncrossing set partitions (1)). Its values on (1) are For every in (1), the support partition of has blocks. On support partitions, rotates labels by .
Facts & Assumptions
Given: The Coxeter presentation of , right-to-left permutation composition, the reflection-length formula and the type-A criterion/isomorphism of The Kreweras complement of [1,c], and the type-A model by noncrossing set partitions.
The adjacent transpositions are the simple reflections of type and their product in the stated order is (The symmetric group has the Coxeter presentation, Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups).
The disjoint cycles determine the orbits, including fixed points as singleton blocks; cycle notation composes with the rightmost factor first (Every permutation of a finite set is a product of pairwise disjoint cycles, uniquely up to reordering and cyclic rotation, Support, fixed points, disjoint cycles, cycle length, disjoint-cycle decompositions, and cycle type, The finite symmetric group , one-line notation, and cycle notation).
For type A, ; interval membership is equivalent to having a noncrossing support partition and cyclically increasing cycles; the support map identifies the interval with noncrossing set partitions (The Kreweras complement of [1,c], and the type-A model by noncrossing set partitions (2)–(4)).
On the general finite-type interval, is an order-reversing bijection, , and (The Kreweras complement of [1,c], and the type-A model by noncrossing set partitions (1)).
Verification
Given: The data above.
(The fourteen interval elements.) By [F3], and exactly when its cycles are cyclically increasing and its support partition is noncrossing. Length gives only . Length gives all six transpositions; each has one pair block and two singleton blocks, so is noncrossing, and its 2-cycle is cyclically increasing. Length means two cycles, hence either a 3-cycle and a fixed point or two transpositions. For each of the four 3-element supports, exactly one orientation is cyclically increasing, giving ; each support partition is noncrossing. Of the three double transpositions, and have noncrossing pair blocks, while has crossing pair blocks. Length means a single 4-cycle; only is cyclically increasing in the stated order. These cases exhaust the possible cycle counts and give precisely the list in (1).
(Direct complement products.) For an involution , . Applying on the right first gives , , , , , and . The same multiplication gives and . For the 3-cycles, multiplying their inverses by gives , , , and ; also and . This is the full list in Statement (3).
(The fifteen partitions.) By block sizes, the set partitions of four labels consist of one partition with one block, six with three blocks, seven with two blocks, and one with four blocks, for a total of fifteen. A partition with one or four blocks is noncrossing. The six three-block partitions have one pair and two singletons, so are noncrossing. Among the seven two-block partitions, the four triple-plus-singleton partitions are noncrossing; the three pairings are , , and , of which only the last has alternating endpoints. This proves the unique crossing claim. The first-step list has fourteen elements, all with noncrossing cyclically increasing cycles; [F3] says each noncrossing partition has a unique such interval permutation. Thus the supports in (1) give exactly the fourteen noncrossing partitions.
(Order, square, and block counts.) [F4] gives that is an order-reversing bijection of the interval, , and . Conjugating a cycle by relabels each entry by , so the support partition rotates as stated. Since and by [F3], the length complement gives .
Depends on
- Coxeter elements, the noncrossing interval [1,c], and the Kreweras map w ↦ w⁻¹c
- The Kreweras complement of [1,c], and the type-A model by noncrossing set partitions
- Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups
- The finite symmetric group $S_n$, one-line notation, and cycle notation
- $\operatorname{Sym}(X)$ is a group under composition, and it is non-abelian whenever $X$ has at least three distinct elements
- The symmetric group has the Coxeter presentation
- Every permutation of a finite set is a product of pairwise disjoint cycles, uniquely up to reordering and cyclic rotation
- Support, fixed points, disjoint cycles, cycle length, disjoint-cycle decompositions, and cycle type
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
45 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.