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.
Two reduced expressions of one element whose subword descriptions agree
Example
In with one-line notation and the inversion number (Support, intrinsic parabolic presentations, minimal coset representatives and length additivity, with the type-A identification (4)), the element has the two reduced expressions both of length .
(i) The element satisfies , and the subword criterion certifies this in each expression, but at different positions: position of and position of (in the second word occurs only at position ). Thus the two descriptions of inside the two expressions of differ in position but must agree in value.
(ii) The subwords of either word realize the same set of elements, namely the interval The two expressions of therefore produce identical subword descriptions of the interval below ; if they could disagree, some element would be comparable with according to one reduced expression of and incomparable according to the other (The subword characterization of Bruhat order and its independence of the reduced expression (2)).
Facts & Assumptions
Given: with generators , the element with its two reduced expressions, the element , and the subword enumerations of the statement.
For type with , the assignment extends to an isomorphism and ; in particular a word in the is reduced if and only if its length equals the inversion number of its value. (Support, intrinsic parabolic presentations, minimal coset representatives and length additivity, with the type-A identification (4))
One-line notation lists the values of a permutation in order of the arguments, and the composition convention is ; hence right multiplication by swaps the entries in positions and of the one-line form. (The finite symmetric group , one-line notation, and cycle notation)
The inversion number of is . (Inversions, inversion number, the sign , and even and odd permutations)
Subword criterion: for a reduced expression and , one has if and only if there are with , and the indices may be chosen with . (The subword characterization of Bruhat order and its independence of the reduced expression (1))
Expression independence: for all the following are equivalent: (a) ; (b) every reduced expression of has a subword that is a reduced expression of ; (c) some reduced expression of has a subword that is a reduced expression of . (The subword characterization of Bruhat order and its independence of the reduced expression (2))
The interval of the statement is the Bruhat interval , and holds for every . (Finiteness of Bruhat intervals, the chain refinement property, and grading by length (1), The Bruhat graph by length-increasing reflection chains, the Bruhat order, inversion symmetry, and reflection parity (2))
Verification
For (i): , because the two words differ only in their last three letters, which are the two words and of the same element of the rank-two parabolic (the braid relation), and has inversion number by [F3], so both words have length and are reduced expressions of by [F1]; the product is computed by applying [F2] letter by letter. The element has one-line form and ; it occurs in at positions and and in at position only, so the subword criterion [F4] gives from either occurrence, at different positions in the two expressions of .
For (ii): fix either reduced expression of . Every subword value is the product of a subword of that reduced word, hence by the right-to-left direction of [F4], and by [F6], so the set of subword values of either expression is contained in the interval ; conversely, by [F5] every has a reduced subword expression inside every reduced expression of , hence is a value of a subword of either of the two words. Therefore the sets of subword values of the two expressions are both equal to , so they coincide. Enumerating the subwords of by multiplying out the indicated letters with [F2] gives exactly the displayed permutations , , , , , , , , , , , (the empty subword gives ), and enumerating the subwords of gives the same values; hence is exactly the displayed set.
Collecting: the two reduced expressions of describe the same interval below , both by the general equivalence of [F5] and by the explicit enumeration of step 1.2 of the subwords of each expression; the element is described at position in the first expression and position in the second, so the positions may differ while the value is the same, as (i) says. If the two descriptions could disagree, then some element would have a subword expression in one reduced expression of and none in the other, contradicting [F5]; all computations are finite and use no choice principle.
Depends on
- The subword characterization of Bruhat order and its independence of the reduced expression
- Finiteness of Bruhat intervals, the chain refinement property, and grading by length
- The Bruhat graph by length-increasing reflection chains, the Bruhat order, inversion symmetry, and reflection parity
- Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups
- Support, intrinsic parabolic presentations, minimal coset representatives and length additivity, with the type-A identification
- The finite symmetric group $S_n$, one-line notation, and cycle notation
- Inversions, inversion number, the sign $\operatorname{sgn}(\sigma)=(-1)^{\operatorname{inv}(\sigma)}$, and even and odd permutations
- Group and abelian group
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
43 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
- Anders Bjorner and Francesco Brenti, Combinatorics of Coxeter Groups (Graduate Texts in Mathematics 231, Springer 2005; author-hosted complete PDF) (standard reference, not scraped)
- Tom Denton, Lifting property and poset structure of finite Coxeter groups (UC Davis MAT 280 lecture notes, 26 January 2009) (standard reference, not scraped)