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.
Omega-positive words are commutation-equivalent to sortable sorting words; sortable equals aligned; parabolic restriction
Statement
Let be a Coxeter system of finite type, a Coxeter element, and with reduced word and reflection sequence , , with positive roots (The inversion formula , the root-reflection dictionary and strong exchange (2)). Let and -alignment be as in The greedy scan computes the c-sorting word; commutation, conjugation and rank-two alignment and -sortability as in c-sortable elements, forced and unforced skips, skip roots, and the chamber cone.
(1) Characterization. The following are equivalent:
(i) for all , with strict inequality unless and commute;
(ii) is -sortable and can be converted into a -sorting word for by a sequence of transpositions of adjacent commuting letters.
(2) Sortable equals aligned. is -sortable if and only if is -aligned; and if is -sortable then is -aligned with respect to every generalized noncommutative rank-two parabolic subgroup of .
(3) Parabolic restriction. If is -sortable, and is the -prefix of (The weak parabolic projection, its adjoints, and the cover-join lemmas (1)), then is -sortable, where is the restriction of to . Conversely, if is -sortable then is -sortable as an element of . No Axiom of Choice is used.
Facts & Assumptions
Given: a finite-type Coxeter system , a Coxeter element with chosen reduced Coxeter word , the periodic word , the forms , , an element with reduced word , its reflection sequence and prefix roots , and an initial letter of when the statement mentions one.
Coxeter elements, the oriented Euler form, the skew form, and the periodic word (1),(2),(3): Coxeter words use each element of once; , for , for , for ; ; is the periodic word with dividers after each block of letters, with position sets, admissible sets, sorting word and block sequence.
The greedy scan computes the c-sorting word; commutation, conjugation and rank-two alignment (1): the greedy scan selects a position with letter exactly when , ends at remainder after selections, and yields the unique -sorting word of .
The greedy scan computes the c-sorting word; commutation, conjugation and rank-two alignment (2),(3): the block sequence is independent of the reduced Coxeter word chosen for ; for initial in , and ; for and the restriction, and on .
The greedy scan computes the c-sorting word; commutation, conjugation and rank-two alignment (4): a generalized rank-two parabolic with canonical generators ordered so that has reflections in angular order; if the endpoint value is the restriction of to the subsystem is zero, and if it is positive then for all ; and is -aligned with respect to it when either the restriction is zero and is empty or a singleton, or the endpoint value is positive and that intersection is empty, the singleton , or an initial segment .
A transported simple root lies in the positive span of the simple root and the inversion roots (1),(2): for with and a reduced expression , one has with , the coefficient of is , and .
Finite inversion sets are recognized by their rank-two initial or final segments (2): a sequence of distinct reflections is the reflection sequence of a reduced word if and only if for every generalized rank-two parabolic its subsequence is an initial or final subsequence of the angular reflection list, read inward from the chosen endpoint: or .
The weak parabolic projection, its adjoints, and the cover-join lemmas (1): for the -prefix of one has , and for if and only if .
The inversion formula , the root-reflection dictionary and strong exchange (1),(2): the root-reflection dictionary is a bijection with ; for a reduced expression , is the set of distinct prefix roots , so for every prefix reflection of a reduced word for .
The root-length criterion and faithfulness of the canonical reflection representation (1): for all , , and .
Root sign coherence and the action of simple reflections on positive roots (2),(3): with the cone of nonnegative simple coordinates and , permutes while .
The right and left weak orders, intervals, covers, and meets and joins of subsets (1),(2): with , and .
Weak order is a partial order with finite graded intervals; covers and the inversion-set criterion (2),(4),(5): covers have the form with ; ; and .
Support, intrinsic parabolic presentations, minimal coset representatives and length additivity, with the type-A identification (1),(2),(3): and ; is a Coxeter system with intrinsic length ; every has a unique factorization with and minimal in , characterized by for all , and .
Length parity, exchange, two-letter deletion, and faithfulness of the signed reflection action (1),(2): ; and if then left multiplication by deletes one letter from any reduced expression for .
c-sortable elements, forced and unforced skips, skip roots, and the chamber cone (1): is -sortable when the block sequence of its -sorting word is weakly decreasing.
Plane subsystems, their canonical generators, and the angular order of their roots (1),(2),(3),(4): for a generalized rank-two parabolic with root-spanned plane one has if and only if ; the positive system has exactly two extreme rays, on roots , every element of is a nonnegative combination of and , and with canonical generators and the reflections are the alternating list with and , the positive roots are in angular order, and reversing the extreme rays reverses the index order.
Disconnected diagrams, direct products, and comparison of invariant forms (4): if is finite then is positive definite.
Intersections of standard parabolics, the parabolic root subsystem, and global minimality of coset representatives (2): , , and a positive root belongs to exactly when its reflection belongs to . Every root has norm , and the action preserves (Descent of the reflection representation, unit root norms, and conjugation of reflections (2),(3)).
Proof
Equivalent forms of the left-descent conditions: for and , lengths are inversion-invariant, so [F14]; applying the root-length criterion [F9] to and translating with the descent/inversion criterion [F13] gives , and . Moreover if and only if [F14].
Restriction recursion: let be initial in and with . The letters are exactly the first letters of the successive -blocks, and deleting them from leaves the periodic word ; the remainder of the -scan is always in : it starts at , and if then for every selected , while : in the factorization of [F14] with one must have , since otherwise would give [F14], contradicting ; hence and is not a left descent. Therefore no -letter is ever selected [F2], and the scan of the remaining letters coincides position-by-position with the -scan of , with the same remainders; by the uniqueness in [F2] the two sorting words coincide and, since the non- letters of the -th -block are exactly the -th -block, for every . Consequently is -sortable if and only if it is -sortable, and the -sorting word for is a -sorting word for .
Descent recursion: let be initial in with and , and let . As letter sequences ; the first symbol is a left descent of , so it is selected by the greedy scan [F2], the remainder becomes , and the rest of the scan is exactly the -scan of . Hence the -sorting word of is followed by the -sorting word of , and the selection sets satisfy with the -selection set. Since every block of either periodic word contains each letter exactly once, a block sequence is weakly decreasing if and only if for every the selected occurrences of form an initial segment of the list of all its occurrences [F1]; the -occurrences of are the positions congruent to its index modulo , and the -occurrences correspond under the shift to the same set of positions with position excluded when and included otherwise. Therefore for the two per-letter conditions coincide term-by-term through the bijection , while for the position is the first -occurrence, so the condition on is equivalent to the condition on . Hence is -sortable if and only if is -sortable.
Negative case: let be initial in and let with , so [F14]. The -sorting word of is a reduced word for , so it contains [F12]; position of , whose letter is , is not selected because [F2]; the only positions carrying are , so the selected occurrence of lies in block . Hence but for some , so the block sequence is not weakly decreasing and is not -sortable [F16].
Initial-root inequality: let be initial in and let be a reflection with positive root , [F10]. With first in the word, , for and for [F1], so and ; hence , because is negative when and zero when [F1, F18]. Equality holds exactly when for every with , that is, when for , equivalently by [F19]; in particular equality forces and to commute, so whenever they do not.
Final-root inequality: let be final in . The same computation with last in the word gives for , for , and , so for every reflection with one has , with equality exactly when , equivalently by [F19], for ; in particular equality forces and to commute.
A commuting swap with zero skew value preserves condition (i). For adjacent commuting letters after a prefix , the two prefix roots are ; swapping the letters exchanges these roots and leaves every other prefix root unchanged. The only skew value whose sign reverses is the value between this pair. Thus if that value is zero, all inequalities and strictness conditions are preserved. Condition (ii) is invariant under every commuting swap by its definition. We use only zero-value swaps in the forward proof below, and justify separately the swaps needed in the reverse proof.
Induction claim and base cases: we prove the equivalences of clauses (1) and (2) by simultaneous induction on the pair (rank , length ): for every finite-type Coxeter system of rank , every Coxeter element and every element with reduced word of length , conditions (1)(i) and (1)(ii) are equivalent, and is -sortable if and only if it is -aligned. Every appeal to induction below is at a pair strictly smaller in the lexicographic order: the rank drops when the system is used, and the length drops when the element is used. The cases and are immediate: the empty sequence satisfies (i) vacuously and the empty conversion furnishes (ii) for ; the block sequence of is empty, hence weakly decreasing, so is -sortable [F16]; and is -aligned because is allowed in either case of the alignment condition of [F4].
Prefix construction for the non-descent alignment case. Suppose and , and set , . Minimality of implies that every left descent of is ; since , its reduced words begin with . Fix a reduced word for and continue it by such a reduced word for , so . Put for . Then . When is sortable we take its sorting word for the prefix.
Full recursion: for initial in and , is -sortable if and only if ( and is -sortable) or ( and is -sortable). Indeed, if is -sortable then either , and step 1.3 gives that is -sortable, or , and step 1.4 gives , so step 1.2 applies and is -sortable; conversely the two alternatives give -sortability by steps 1.2 and 1.3.
Step (i)(ii), case : let be initial in with . By step 1.1, , so all lie in and the restriction identity [F3] gives for all , so (i) holds for in the smaller-rank system . By induction on rank, is -sortable and converts into an -sorting word for by adjacent commuting transpositions inside . By step 1.2 that word is a -sorting word, so is -sortable and the conversion exhibits (ii).
Step (i)(ii), case : start with the given word satisfying (i), and let be its first occurrence of . If , the prefix avoids , and [F5] gives with . This expansion will supply a zero-value commuting swap moving the first earlier; finite iteration then puts first.
Aligned implies sortable in the descent case. Suppose is -aligned and . For a noncommutative rank-two parabolic not containing , conjugation by preserves positivity of all its roots, so it takes the extreme rays and angular list to those of the conjugate subsystem. The inversion recursion gives , and [F3] transfers the forms; alignment therefore transfers to the conjugate subsystem. In a rank-two parabolic containing , is an extreme ray: expressing it as a nonnegative combination of the two extreme positive roots forces one of those roots to be supported only on , by comparing the other simple coordinates, hence that root is by unit normalization [F19]. The restriction of omits , so rank-two recognition makes it an initial segment from the other endpoint (or empty). Since is final in , step 1.6 orders that other endpoint first with strictly positive skew value. Thus is -aligned in every subsystem. Length induction gives -sortability of , and step 1.3 gives -sortability of .
Clause (2), reverse direction, case : assume is -aligned with . We show first that . Suppose not and put , the -prefix of ; then is the length-additive factorization of [F14] with , and . For every noncommutative generalized rank-two parabolic contained in , the prefix inversion formula [F7] gives , and the forms agree by the restriction identity [F3]; hence is aligned with respect to . By the induction claim of step 1.8, applied inside the smaller-rank system , is -sortable, hence -sortable by step 1.2.
Claim: for every . We prove this by descending induction on . The base holds because is the reflection at position of the reduced word for , hence lies in [F8]. For the step fix , assume , and note that also [F8]. Put , and ; its generators are the reflections and , and for the root-spanned plane ; since is a prefix of the reduced word one has , and because otherwise and the simple length jump would make a reduced spelling of containing , contrary to support invariance [F14],[F15], contrary to ; so is the minimal representative of the left coset [F14], both and are positive. Every positive root of is a nonnegative combination of these two simple roots, so its image under is positive, and every negative subsystem root has negative image. Since by [F19], the positive roots of this plane are exactly . Their extreme rays are therefore and ; the extreme-ray characterization in [F17] proves that are the canonical generators, with no external theorem, and the reflection list is as in [F17]. If and commute, then , so by the induction hypothesis.
Clause (3), converse direction: let , the restriction of , and -sortable with -sorting word . Every letter of this word lies in ; the argument of step 1.2 with in place of shows that the -scan of never selects a letter outside (the remainder stays in by [F14], and for and the factorization with gives ), and the selected letters inside the successive -blocks are exactly those of the -sorting word, whose -th block coincides with the -th -block's -letters. Hence the -sorting word of is , for every , and is -sortable.
Under step 2.3, bilinearity gives . Each term is nonpositive by step 1.5 and (i); the left side is nonnegative by (i), so it is zero. Strictness in (i) forces to commute. Writing , these are and , so their commutation is equivalent to . This is exactly the zero-value swap required in step 2.3. Its finite iteration yields .
Step (ii)(i): let the given word be commutation-equivalent to a sorting word of sortable . If is absent, every word in the class lies in and the rank induction and restriction identity prove (i). Otherwise the sorting word begins with by step 2.1. In any commutation-equivalent word every letter preceding the first commutes with : a noncommuting letter cannot cross that occurrence under commuting swaps. Move this to the front. At each such swap the preceding prefix uses letters commuting with , hence fixes ; its adjacent other root is supported on those letters, and the formula in step 1.5 gives skew value zero with . Step 1.7 therefore preserves (i) in both directions for these swaps. Deleting the first from the commutation class gives a word commutation-equivalent to the -sorting word of (each original swap either survives deletion or exchanges that with a commuting letter and becomes an identity). The length induction proves (i) on this tail, and [F3] transports its roots to the tail roots of . Pairs involving the first root satisfy (i) by step 1.5. Reversing the zero-value swaps proves (i) for the original word.
Assume now that do not commute; then . Since is a reduced word for an element of , the positive-span expansion [F5] gives with . Then (the term of the expansion of [F5] drops because is alternating), where the first term is by step 1.5 and each other term is by the induction hypothesis for clause (1)(i) at the strictly shorter sortable element of step 2.5. If the sum were , then, because and is the reflection with normal [F8], the identity would hold (the normal component contributes to both values); since and are the canonical generators of [step 2.6], the endpoint value of on would vanish, so the restriction of to would be zero [F4], and the -alignment of with respect to would force to be empty or a singleton [F4]; but it contains the two distinct roots [F8] and (induction hypothesis). Therefore .
Step (i)(ii), conclusion in case : by step 3.1 the word is with a reduced word for [F15], and the conjugation identity [F3] transfers (i) to for the tail. By induction on length, is -sortable and converts into an -sorting word for by adjacent commuting transpositions. By step 1.3 the -sorting word of is , so is -sortable, and is the required conversion.
Alignment inference: retain the notation of step 3.3 with noncommuting, and let be the angular list of ordered so that [F4]; since , the restriction of to is nonzero and the endpoint value is positive [F4]. The relation and the alternating-list identities [F17] leave two possibilities: if and , then and [F4] gives , contradicting the strict negativity of step 3.3; hence , and . Since is -aligned with respect to , the set is empty, the singleton , or an initial segment [F4]; it contains [F8] and (induction hypothesis), so it is not empty, and the singleton case is excluded because for [F17]; therefore it is an initial segment containing , hence also , and . This closes the induction of step 2.6.
Clause (1) is proved by steps 1.8, 2.1-2.3, 3.1-3.2 and 4.1.
Clause (2), forward direction: let be -sortable with -sorting word and reflection sequence , prefix roots . By clause (1), applied to the sorting word in the direction (ii)(i), for , strictly unless commute. Let be a noncommutative generalized rank-two parabolic with angular reflection list , ; by the recognition lemma [F6] the subsequence of lying in is an initial or final subsequence of that list, so is an initial or final segment of [F8]. In the canonical order with [F4]: if the endpoint value is then any two-element segment contains two consecutive reflections with , contradicting the strictness of (i) since do not commute [F17], so the segment is empty or a singleton; if the endpoint value is positive then a final segment of size at least two presents the pair in that order in the reflection sequence, so strictness would force , while the orientation [F4] gives , a contradiction; hence the segment is empty, the singleton , or an initial segment. This is exactly -alignment with respect to [F4], and was arbitrary.
Consequence: by step 2.6 with , , so by [F13], contradicting . Hence a -aligned with lies in . It is then -aligned as an element of that parabolic: every noncommutative generalized rank-two parabolic of is one of , the inversion set satisfies , and the restriction identity [F3] preserves the alignment condition. By the induction claim of step 1.8 applied inside the smaller-rank system , is -sortable, and by step 1.2 it is -sortable. Together with steps 6.1 and 2.4 this proves both directions of clause (2).
Clause (3), forward direction. Let be -sortable and restrict its sorting reflection sequence to the reflections in . Apply [F6] inside the intrinsic Coxeter system of [F14]. Each root-spanned plane has intrinsic roots by [F19]; its angular list and canonical reflections are therefore the ambient ones, all contained in . The restricted sequence has exactly the original sequence's endpoint-inward subsequence in this plane, so satisfies [F6]. Hence it is the reflection sequence of an intrinsically reduced word for some , also reduced in by [F14]. Its positive prefix roots are by [F7],[F8],[F19], so [F13] gives . This restriction argument applies to every reduced-word reflection sequence, without a sortability assumption. For the present sortable , each ordered pair of restricted roots inherits the nonnegative omega value and strictness for noncommuting reflections from clause (1). Form restriction [F3] gives the same inequalities for ; clause (1) inside now gives -sortability of .
Conclusion: steps 1.1-1.4 supply the descent-condition translation, the two recursions and the negative case; steps 1.5-1.6 the two endpoint inequalities; step 1.7 the invariance under commuting transpositions; steps 1.8-1.9 set up the induction and the prefix construction; steps 2.1-2.3, 3.1-3.2 and 4.1 prove clause (1); steps 2.4-2.6, 3.3, 4.2, 6.1 and 7.1 prove clause (2); steps 2.7 and 7.2 prove clause (3). All inductions are on the well-founded lexicographic pair (rank, length), and every witness selected is a single existential instantiation from an explicitly given finite or fixed set (a reduced word of a fixed element, an initial or final letter, a canonical generator pair); no Axiom of Choice is used.
Depends on
- Coxeter elements, the oriented Euler form, the skew form, and the periodic word
- The greedy scan computes the c-sorting word; commutation, conjugation and rank-two alignment
- Finite inversion sets are recognized by their rank-two initial or final segments
- The weak parabolic projection, its adjoints, and the cover-join lemmas
- c-sortable elements, forced and unforced skips, skip roots, and the chamber cone
- The geometric inversion set $N(w)$ of an element of a Coxeter group
- The inversion formula $|N(w)|=\ell(w)$, the root-reflection dictionary and strong exchange
- The root-length criterion and faithfulness of the canonical reflection representation
- Root sign coherence and the action of simple reflections on positive roots
- Disconnected diagrams, direct products, and comparison of invariant forms
- 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
- A transported simple root lies in the positive span of the simple root and the inversion roots
- Plane subsystems, their canonical generators, and the angular order of their roots
- Support, intrinsic parabolic presentations, minimal coset representatives and length additivity, with the type-A identification
- Length parity, exchange, two-letter deletion, and faithfulness of the signed reflection action
- Intersections of standard parabolics, the parabolic root subsystem, and global minimality of coset representatives
- Descent of the reflection representation, unit root norms, and conjugation of reflections
Used by
- The recursive initial-letter sortable projection Definition
- Skip roots form a basis, negative skips are cover roots, and the cover decomposition of sortable elements Lemma
- The cone criterion, monotonicity of the projection, and the greatest sortable element below w Lemma
- The recursive projection is well defined, sortable-valued, below w, idempotent, descent-detecting and parabolic Lemma
- Sortable elements form a sublattice and the c-Cambrian quotient is its lattice-homomorphic image Theorem
- The upper endpoint of a c-Cambrian fiber, interval fibers and the explicit formula u_c(w) = pi_c⁻¹(ww0)w0 Theorem
Dependency tree · two levels
81 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
- N. Reading and D. E. Speyer, Sortable elements in infinite Coxeter groups, arXiv:0803.2722v3 (2010); Trans. Amer. Math. Soc. 363 (2011) 699-761 (standard reference, not scraped)
- N. Reading, Sortable elements and Cambrian lattices, arXiv:math/0512339v1 (2005); Algebra Universalis 56 (2007) 35-56 (standard reference, not scraped)
- A. Bjorner and F. Brenti, Combinatorics of Coxeter Groups, Graduate Texts in Mathematics 231, Springer 2005 (standard reference, not scraped)