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 heap of in type : a V-shaped heap with exactly two linear extensions
Example
Let with and , the Coxeter matrix of type (Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups), let be the presented group and let . Then:
(1) The heap of the word has elements with , and no relation between and ; its covering pairs are and , with labels and .
(2) satisfies both conditions of Fully commutative elements: the braid-factor criterion and the forbidden-chain heap criterion (2): its chains have at most two elements, so it has no convex alternating chain of length , and its covering pairs have distinct labels. Hence the word is reduced, is fully commutative and is the heap of ; in particular .
(3) The linear extensions of are exactly and , and the corresponding labeled linear extensions are the words and . By Labeled linear extensions of a heap are exactly the words in its commutativity class, and heaps classify commutativity classes (1) these are exactly the members of the commutativity class : the two reduced words of differ by the commute .
(4) The order ideals of are , , , and ; they form a five-element distributive lattice under inclusion.
Facts & Assumptions
Given: The Coxeter matrix of type on , the presented group , and the word with heap and product .
The heap of a word is the labeled poset whose relations are generated by for with or ; labeled linear extensions are read from linear extensions; is the commutativity class of ; and is fully commutative when (Words, heaps, linear extensions, commutation classes, and fully commutative elements, clauses (2), (4), (5), (6)).
For the Coxeter matrix, is the order of in ; in particular means that and commute in (Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups).
For a word with heap and product , conditions (a) and (b) of Fully commutative elements: the braid-factor criterion and the forbidden-chain heap criterion (2) together are equivalent to: is reduced and is fully commutative; when they hold, is the heap of (Fully commutative elements: the braid-factor criterion and the forbidden-chain heap criterion, clause (2)).
For every word one has (Labeled linear extensions of a heap are exactly the words in its commutativity class, and heaps classify commutativity classes, clause (1)).
An element covers when and no satisfies (Graded poset, rank function, and rank levels).
For a finite poset , the order ideals form a finite distributive lattice under inclusion, with meet intersection and join union (The order ideals of a finite poset form a distributive lattice under union and intersection).
Verification
Given: The type Coxeter matrix and the word with product .
Proof technique: direct.
The heap relations are computed pair by pair from [F1]: positions carry the distinct commuting letters with , so there is no relation between them; position is above position because and ; and position is above position because and . These are therefore all generating relations, and the transitive closure adds nothing, so is the three-element poset with exactly and . By [F5] its covering pairs are and : the only elements are , and no satisfies or , since and are incomparable. The covering labels are and .
The order ideals are the subsets that contain and whenever they contain , that is, : downward closure of a subset of the three-element poset is a condition only on the predecessors of . These five sets are exactly , and by [F6] they form a finite distributive lattice under inclusion, with meet intersection and join union.
The criterion of [F3] applies: every chain of has at most two elements, since the only relations are and , so there is no convex chain of any length , and in particular none of length ; hence condition (a) of Fully commutative elements: the braid-factor criterion and the forbidden-chain heap criterion (2) holds. The covering pairs and have labels and , and are pairwise distinct, so condition (b) holds. By [F3] the word is reduced, is fully commutative and ; since a reduced word of has length , this gives .
A listing of is a linear extension of exactly when is last, because both relations point to and are incomparable; the two linear extensions are therefore and , with labeled words and . By [F4], , and by 2.1 the word is reduced with fully commutative, so ; hence the reduced words of are exactly these two words, which differ by interchanging the adjacent commuting letters .
Depends on
- Words, heaps, linear extensions, commutation classes, and fully commutative elements
- Labeled linear extensions of a heap are exactly the words in its commutativity class, and heaps classify commutativity classes
- Fully commutative elements: the braid-factor criterion and the forbidden-chain heap criterion
- Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups
- Graded poset, rank function, and rank levels
- The order ideals of a finite poset form a distributive lattice under union and intersection
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
32 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.
Sources
- J. R. Stembridge, On the Fully Commutative Elements of Coxeter Groups, author manuscript (March 1995, minor revisions September 1995); published in J. Algebraic Combin. 5 (1996), 353-385 (standard reference, not scraped)
- P. Nadeau, On the length of fully commutative elements, arXiv:1511.08788 (standard reference, not scraped)