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 right weak order interval below a fully commutative element is the lattice of order ideals of its heap
Statement
Let , , be as in Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups, let be the right weak order with intervals and covers (The right and left weak orders, intervals, covers, and meets and joins of subsets, Weak order is a partial order with finite graded intervals; covers and the inversion-set criterion), and let fully commutative elements, reduced words and heaps be as in Words, heaps, linear extensions, commutation classes, and fully commutative elements and Labeled linear extensions of a heap are exactly the words in its commutativity class, and heaps classify commutativity classes. Let be fully commutative, let , and let be the heap of , with lattice of order ideals (Lattices, distributive lattices, and order ideals, The order ideals of a finite poset form a distributive lattice under union and intersection).
(1) The ideal of an element of the interval. For write , a chain in , with elements , and for a word let be the number of occurrences of in . If and , then for all , and is an order ideal of ; it does not depend on the choice of . Writing for this common ideal, one has , and .
(2) Order isomorphism. The map is an order isomorphism from onto ordered by inclusion.
(3) Lattice structure. Consequently , as a subposet of , is a finite distributive lattice: for all the meet and the join exist in and satisfy the least element is and the greatest element is .
(4) Caveats. This identifies the right weak order interval with , for a fully commutative ; no identification of the Bruhat order interval below with is made, and no claim is made about the intervals of elements that are not fully commutative.
Facts & Assumptions
Given: A finite Coxeter matrix , the presented group with length , a fully commutative element , a reduced word with heap , and the right weak order .
The group is presented with relators and ; is the set of reduced words of , of common length , and concatenation of words represents the product of the represented elements (Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups).
The right weak order is defined by if and only if with ; intervals are , and means that with no element strictly between (The right and left weak orders, intervals, covers, and meets and joins of subsets, clauses (1)-(2)).
For all one has (length identity), and if and only if some reduced expression of has a reduced expression of as its initial segment (prefix property) (The length identity, the prefix property, left translation, and interval translation for weak order, clauses (1)-(2)).
Covers in are exactly the pairs with and , and every is joined by a chain of covers (Weak order is a partial order with finite graded intervals; covers and the inversion-set criterion, clause (2)).
In the heap , any two positions with equal or noncommuting labels are comparable by the defining relation, so each same-label set is a chain; an element is fully commutative when for one (equivalently every) (Words, heaps, linear extensions, commutation classes, and fully commutative elements, clauses (2), (6)).
For every word one has , the set of labeled words of linear extensions of (Labeled linear extensions of a heap are exactly the words in its commutativity class, and heaps classify commutativity classes, clause (1)).
Every finite poset has a linear extension; for every order ideal of and every linear extension of the induced poset on , there is a linear extension of whose first entries are exactly the elements of . A linear extension is as in Linear extensions of a finite poset (Linear extensions of a finite poset: existence, prescribed initial ideals, and adjacent-swap connectivity, clause (2)).
An order ideal of a poset is a subset closed downward under , and denotes the set of order ideals ordered by inclusion (Lattices, distributive lattices, and order ideals). Here an order isomorphism means an order-preserving bijection whose inverse is order-preserving.
For a finite poset , is a finite distributive lattice under inclusion, with meet intersection, join union, least element and greatest element (The order ideals of a finite poset form a distributive lattice under union and intersection).
Proof
Given: A fully commutative element , a reduced word and its heap .
Proof technique: direct.
Clause (1), construction of the ideal. Let , in the right weak order of [F2], and let . By the length identity F3, ; fix a reduced word of . Then represents and has length , so . Since is fully commutative, by [F5] and [F6], so is the labeled word of a linear extension of . In any linear extension the elements of the chain occur in increasing order , so the first letters of , namely the letters of , are exactly for each . Hence , and is the set of the first entries of , an initial segment of a linear extension; a prefix of a linear extension is downward closed, so is an order ideal of .
Clause (2), the heap of an ideal. Let . By [F7], choose a linear extension of whose initial block lists exactly , where . Let be the word of labels on this block, let be its product in , and define by . This bijection preserves labels. For any strict relation with , choose a chain of maximal length between and (such a chain exists because is finite). Every lies in , since and . Each consecutive pair is a cover in ; it must be a generating pair of the heap, because a generating path with an intermediate element would contradict the cover property. Since is a linear extension, each such pair occurs in the same order in , and its labels are equal or noncommuting. Thus the corresponding positions are related in , and transitivity shows that in implies .
Clause (1), well-definedness and basic properties. If is a second reduced word, then with the same suffix the word also has length and represents , so ; a word in is the labeled word of a linear extension of , hence contains each exactly times, and this holds for as well. Subtracting the common multiplicity of the suffix gives for every , so is well defined. Moreover because the sets are disjoint; because the empty word has ; and because for one has .
Conversely, each generating relation of joins positions with equal or noncommuting labels. Their corresponding elements of are comparable in by [F5], and the order is the one in , so every generating relation of respects the induced order on . Together with 1.2, this proves that is a labeled poset isomorphism. If a different linear extension of is used, transport its listing through to a linear extension of ; the labels are unchanged, so its labeled word lies in and [F6] makes it commutation-equivalent to , and [F1] says these interchanges preserve the product. Therefore depends only on , and is well defined.
Clause (2), is order-preserving. Let be order ideals of . Apply [F7] twice: extend a linear extension of (with first entries ) to a linear extension of the induced poset on , which therefore has first entries and first entries , and extend that in turn to a linear extension of ; then the first entries of are and its first entries are . The full labeled word of lies in by [F5] and [F6]. The word constructed in 1.2 is a prefix of the word , and both are reduced: replacing either prefix by a shorter word for its product would shorten the full reduced word of ; by the prefix property F3 applied to and we get .
Clause (2), monotonicity of . If , then by [F4] with and ; for the word represents and has length , hence lies in , and for all . By the well-definedness 2.1 the ideals may be computed from these words, so . For arbitrary , [F4] joins to by a chain of covers and inclusion is transitive along that chain; hence implies .
The full labeled word of belongs to by definition. By [F6] and full commutativity [F5], , so represents and is reduced of length . Its prefix is also reduced, since a shorter expression for that prefix would shorten as an expression of . The prefix property F3 gives . Conversely, for any , step 1.1 gives a reduced word of as the initial segment of a linear extension of with initial ideal ; using that extension in the definition of gives . Finally, because is an order ideal and each is a chain, is an initial segment of with exactly elements; hence . Thus is a two-sided inverse of .
Clauses (3) and (4). By steps 3.1 and 3.2, is an order-preserving bijection with inverse , and by step 2.3 the inverse is order-preserving; hence this is an order isomorphism . For , put and . Since preserves order and is inverse to , and . If satisfies , then monotonicity of gives , so ; therefore . Dually, if is a common upper bound, then , so and . Applying gives the displayed intersection and union formulas. By [F9], is a finite distributive lattice with least element and greatest element , so the order isomorphism transports this structure to , whose least and greatest elements are and . Clause (4) holds because the argument uses only the right weak order and its prefix property, and it assumes that is fully commutative; no Bruhat-interval or non-fully-commutative claim is made.
Depends on
- Words, heaps, linear extensions, commutation classes, and fully commutative elements
- Linear extensions of a finite poset: existence, prescribed initial ideals, and adjacent-swap connectivity
- Labeled linear extensions of a heap are exactly the words in its commutativity class, and heaps classify commutativity classes
- The right and left weak orders, intervals, covers, and meets and joins of subsets
- The length identity, the prefix property, left translation, and interval translation for weak order
- Weak order is a partial order with finite graded intervals; covers and the inversion-set criterion
- The order ideals of a finite poset form a distributive lattice under union and intersection
- Lattices, distributive lattices, and order ideals
- Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups
- Linear extensions of a finite poset
Used by
Dependency tree · two levels
41 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)
- C. Krattenthaler, The theory of heaps and the Cartier-Foata monoid, appendix to the electronic reedition of P. Cartier and D. Foata, Problemes combinatoires de commutation et rearrangements (2006) (standard reference, not scraped)