Pipeline-generated

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.

✓ 5 results · all verified · 4 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 1 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Weak Order, Inversions, and Lattice Operations

1 · Prerequisites

2 · Summary

Let $(W, S)$ be a Coxeter system of finite rank, with length function $ℓ$ . The right and left weak orders are the length-additive relations $u \leq_{R} v$ when $v = u x$ and $ℓ (v) = ℓ (u) + ℓ (x)$ , and $u \leq_{L} v$ when $v = x u$ with the same length equality. The descent sets $D_{L} (w)$ and $D_{R} (w)$ record the simple generators that lower length on the left and right.

The prefix and translation properties make these relations computable from reduced words. In right weak order, $u \leq_{R} v$ exactly when some reduced expression of $v$ begins with a reduced expression of $u$ . If $s$ is a left descent of both $u$ and $v$ , then $u \leq_{R} v$ exactly when $s u \leq_{R} s v$ ; comparable intervals translate to lower intervals by left multiplication.

Both weak orders are partial orders with minimum $1$ . A cover is exactly a multiplication by one simple generator that raises length by one; every comparison is a chain of covers, and each interval is finite and graded by length. The inversion sets characterize the orders: $u \leq_{R} v$ if and only if $N (u^{- 1}) \subseteq N (v^{- 1})$ , while $u \leq_{L} v$ if and only if $N (u) \subseteq N (v)$ . The corresponding simple-root tests identify left and right descents.

Every nonempty subset of either weak order has a meet. A nonempty subset has a join exactly when it is bounded above, and then its join is the meet of its upper bounds. The meet construction uses a finite descent in length, so no Axiom of Choice is needed. No general lattice property is asserted for infinite Coxeter groups.

When $W$ is finite, both weak orders are lattices with minimum $1$ and maximum $w_{0}$ . Their empty-set values are $⋀ \emptyset = w_{0}$ and $⋁ \emptyset = 1$ . More generally, for $J \subseteq S$ , the parabolic subgroup $W_{J}$ is finite exactly when $J$ has an upper bound, equivalently when its join exists; in that case $⋁ J = w_{0} (J)$ in both orders. For $J = \emptyset$ , this gives $w_{0} (J) = 1$ .

The root criterion also detects finiteness: if $w \in W_{J}$ and every $s \in J$ lowers $w$ on the left, then $W_{J}$ is finite and $w = w_{0} (J)$ . This argument applies without a definiteness assumption on the Coxeter form. The companion page gives the complete $A_{2}$ lattice table, the infinite-dihedral obstruction, and the counterexample to computing meets and joins by intersecting and uniting inversion sets.

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6.1-sol)audited 2026-10-08Open item page →

The right and left weak orders, intervals, covers, and meets and joins of subsets

Definition

Let $(S, m)$ be a finite Coxeter matrix, let $W$ be the presented group with length function $ℓ$ and reduced expressions (Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups), and for $w \in W$ let

$D_{L} (w) : = {s \in S : ℓ (s w) < ℓ (w)}, D_{R} (w) : = {s \in S : ℓ (w s) < ℓ (w)}$

be the left and right descent sets already fixed in Standard parabolic subgroups, descent-free one- and two-sided representatives, parabolic and reflection subgroups (2). Let $T$ , $Φ = Φ_{+} ⊔ Φ_{-}$ and the inversion sets $N (w) = {α \in Φ_{+} : ρ (w) α \in Φ_{-}}$ be the reflection set, the signed root system and the inversion sets of The canonical reflection homomorphism, roots, reflections, and the positive cone and The geometric inversion set $N (w)$ of an element of a Coxeter group.

(1) Right and left weak order. Define two relations on $W$ by

$u \leq_{R} v ⟺ v = u x for some x \in W with ℓ (v) = ℓ (u) + ℓ (x),$

$u \leq_{L} v ⟺ v = x u for some x \in W with ℓ (v) = ℓ (u) + ℓ (x) .$

These are the right weak order and the left weak order on $W$ . Inversion relates them definitionally: $u \leq_{R} v ⟺ u^{- 1} \leq_{L} v^{- 1}$ , because $v = u x$ with $ℓ (v) = ℓ (u) + ℓ (x)$ is equivalent to $v^{- 1} = x^{- 1} u^{- 1}$ with $ℓ (v^{- 1}) = ℓ (u^{- 1}) + ℓ (x^{- 1})$ , using $ℓ (y) = ℓ (y^{- 1})$ (Support, intrinsic parabolic presentations, minimal coset representatives and length additivity, with the type-A identification (3)). Write $u <_{R} v$ for $u \leq_{R} v$ with $u \neq v$ .

(2) Intervals, covers and bounded subsets. For $u, v \in W$ define $[u, v]_{R} : = {w \in W : u \leq_{R} w and w \leq_{R} v}$ and $[u, v]_{L} : = {w \in W : u \leq_{L} w and w \leq_{L} v}$ ; these are the right and left intervals. An element $v$ covers $u$ in $\leq_{R}$ , written $u ⋖_{R} v$ , when $u <_{R} v$ and there is no $w \in W$ with $u <_{R} w <_{R} v$ ; define $u ⋖_{L} v$ in the same way using $\leq_{L}$ . A subset $A \subseteq W$ is bounded above in $\leq_{R}$ if there exists $y \in W$ with $a \leq_{R} y$ for every $a \in A$ , and bounded below if there exists $y \in W$ with $y \leq_{R} a$ for every $a \in A$ . Define upper and lower bounds in $\leq_{L}$ by replacing $\leq_{R}$ with $\leq_{L}$ .

(3) Meets and joins of subsets. Let $A \subseteq W$ and $z \in W$ . The element $z$ is a right upper bound of $A$ if $a \leq_{R} z$ for every $a \in A$ ; it is a right join (least upper bound) if it is a right upper bound and $z \leq_{R} y$ for every right upper bound $y$ of $A$ . Dually, $z$ is a right lower bound if $z \leq_{R} a$ for every $a \in A$ , and a right meet (greatest lower bound) if it is a right lower bound and $u \leq_{R} z$ for every right lower bound $u$ of $A$ . Define left upper and lower bounds, meets, and joins by replacing $\leq_{R}$ with $\leq_{L}$ . Whenever the relevant meet or join is unique, write it as $⋀ A$ or $⋁ A$ in the order under discussion; for $A = {u, v}$ write $u \land v$ or $u \lor v$ . A meet or join, when it exists, is unique in either order: any two meets (respectively joins) bound one another, so antisymmetry gives equality. The partial-order property needed here is the recorded well-definedness justifier. This definition asserts no existence of meets or joins for any specified subset.

(4) Abstentions. This definition records $\leq_{R}, \leq_{L}$ and the interval and bound vocabulary; it asserts no further property. In particular, it does not assert that either relation is a partial order (Partial order and partially ordered set), that covers have the form $v = u s$ , that any meet or join exists, or that $w \mapsto N (w^{- 1})$ computes $\leq_{R}$ by inclusion of inversion sets. No Choice is used.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6.1-sol)audited 2026-10-08Open item page →

The length identity, the prefix property, left translation, and interval translation for weak order

Statement

Let $(S, m)$ be a finite Coxeter matrix, $W$ the presented group with length $ℓ$ , the descent sets $D_{L}, D_{R}$ and the weak orders $\leq_{R}, \leq_{L}$ as in The right and left weak orders, intervals, covers, and meets and joins of subsets. Then:

(1) Length identity. For all $u, v \in W$ ,

$u \leq_{R} v ⟺ ℓ (v) = ℓ (u) + ℓ (u^{- 1} v), u \leq_{L} v ⟺ ℓ (v) = ℓ (u) + ℓ (v u^{- 1}) .$

In particular $u \leq_{R} v$ implies $ℓ (u) \leq ℓ (v)$ , and likewise for $\leq_{L}$ .

(2) Prefix property. $u \leq_{R} v$ if and only if there exist reduced expressions $u = s_{1} \dots s_{k}$ and $v = s_{1} \dots s_{k} s_{1}^{'} \dots s_{q}^{'}$ with $k, q \geq 0$ ; equivalently, some reduced expression of $v$ has a reduced expression of $u$ as its initial segment. Symmetrically, $u \leq_{L} v$ if and only if there exist reduced expressions $u = t_{1} \dots t_{k}$ and $v = t_{1}^{'} \dots t_{q}^{'} t_{1} \dots t_{k}$ .

(3) Left translation. For all $u, v \in W$ and $s \in S$ with $s \in D_{L} (u) \cap D_{L} (v)$ ,

$u \leq_{R} v ⟺ s u \leq_{R} s v .$

(4) Interval translation. If $u \leq_{R} v$ , then $x \mapsto u x$ is a bijection $[1, u^{- 1} v]_{R} \to [u, v]_{R}$ satisfying $ℓ (u x) = ℓ (u) + ℓ (x)$ for every $x \in [1, u^{- 1} v]_{R}$ and preserving and reflecting the relation: for all $x, x^{'}$ in the source interval, $x \leq_{R} x^{'} ⟺ u x \leq_{R} u x^{'}$ . If $u \leq_{L} v$ , then $x \mapsto x u$ is a bijection $[1, v u^{- 1}]_{L} \to [u, v]_{L}$ with the analogous length and relation properties. No Choice is used.

Facts & Assumptions

Given: A finite Coxeter matrix $(S, m)$ with presented group $W$ , length function $ℓ$ , descent sets $D_{L}, D_{R}$ and weak orders $\leq_{R}, \leq_{L}$ as in The right and left weak orders, intervals, covers, and meets and joins of subsets, and elements $u, v, x \in W$ and $s \in S$ as specified in each clause.

[F1]

The right and left weak orders, intervals, covers, and meets and joins of subsets: $u \leq_{R} v$ means that $v = u x$ for some $x \in W$ with $ℓ (v) = ℓ (u) + ℓ (x)$ ; $u \leq_{L} v$ means that $v = x u$ for some $x \in W$ with $ℓ (v) = ℓ (u) + ℓ (x)$ ; and $u \leq_{R} v ⟺ u^{- 1} \leq_{L} v^{- 1}$ . Intervals, covers and bounded subsets are defined there.

[F2]

Support, intrinsic parabolic presentations, minimal coset representatives and length additivity, with the type-A identification (3): by inversion, $w \mapsto w^{- 1}$ preserves lengths, that is $ℓ (y) = ℓ (y^{- 1})$ for every $y \in W$ .

[F3]

Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups: for $w \in W$ , $ℓ (w) = \min {k \in N : there exist s_{1}, \dots, s_{k} \in S with w = s_{1} \dots s_{k}}$ ; a reduced expression of $w$ is a word $(s_{1}, \dots, s_{k})$ in $S$ with $w = s_{1} \dots s_{k}$ and $k = ℓ (w)$ .

[F4]

Standard parabolic subgroups, descent-free one- and two-sided representatives, parabolic and reflection subgroups (2): $D_{L} (w) = {s \in S : ℓ (s w) < ℓ (w)}$ , $D_{R} (w) = {s \in S : ℓ (w s) < ℓ (w)}$ , and for every $s \in S, w \in W$ , $ℓ (s w) - ℓ (w)$ and $ℓ (w s) - ℓ (w)$ lie in ${- 1, + 1}$ . Thus $s \in D_{L} (w)$ implies $ℓ (s w) = ℓ (w) - 1$ ; also $ℓ (s) = 1$ by taking $w = 1$ and using $ℓ (1) = 0$ from [A1].

[F5]

Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups: every simple generator $s \in S$ satisfies $s^{2} = 1$ in $W$ .

[A1]

For the word length of [F3]: $ℓ (1) = 0$ , since $1$ is the value of the empty word and no shorter length is possible; $ℓ (a) = 0$ forces $a = 1$ ; and $ℓ (a b) \leq ℓ (a) + ℓ (b)$ for all $a, b \in W$ , because concatenating a reduced expression of $a$ with one of $b$ gives a word of length $ℓ (a) + ℓ (b)$ representing $a b$ .

Proof

1.1F1F3A1givenalgebra

For all $u, v \in W$ , $u \leq_{R} v$ if and only if $ℓ (v) = ℓ (u) + ℓ (u^{- 1} v)$ , and then $ℓ (u) \leq ℓ (v)$ . Indeed, if $u \leq_{R} v$ then $v = u x$ with $ℓ (v) = ℓ (u) + ℓ (x)$ for some $x$ , and multiplying $v = u x$ on the left by $u^{- 1}$ gives $x = u^{- 1} v$ , hence $ℓ (v) = ℓ (u) + ℓ (u^{- 1} v)$ ; conversely, if $ℓ (v) = ℓ (u) + ℓ (u^{- 1} v)$ , then $x : = u^{- 1} v$ satisfies $v = u x$ with $ℓ (v) = ℓ (u) + ℓ (x)$ , so $u \leq_{R} v$ . The final inequality follows from $ℓ (u^{- 1} v) \geq 0$ .

1.2F1F3A1givenalgebra

For all $u, v \in W$ , $u \leq_{L} v$ if and only if $ℓ (v) = ℓ (u) + ℓ (v u^{- 1})$ , and then $ℓ (u) \leq ℓ (v)$ . The argument is symmetric: if $u \leq_{L} v$ then $v = x u$ with $ℓ (v) = ℓ (u) + ℓ (x)$ , and multiplying on the right by $u^{- 1}$ gives $x = v u^{- 1}$ ; conversely $x : = v u^{- 1}$ realizes the defining factorization whenever the displayed length identity holds.

2.1F1F3A1step 1.1givenalgebra

If $u \leq_{R} v$ , then $v$ has a reduced expression $s_{1} \dots s_{k} s_{1}^{'} \dots s_{q}^{'}$ whose initial segment $s_{1} \dots s_{k}$ is a reduced expression of $u$ . By step 1.1, $ℓ (v) = ℓ (u) + ℓ (u^{- 1} v)$ ; choose reduced expressions $u = s_{1} \dots s_{k}$ and $u^{- 1} v = s_{1}^{'} \dots s_{q}^{'}$ , so $k = ℓ (u)$ and $q = ℓ (u^{- 1} v)$ . The concatenated word $s_{1} \dots s_{k} s_{1}^{'} \dots s_{q}^{'}$ represents the element $u \cdot u^{- 1} v = v$ and has length $k + q = ℓ (v)$ ; hence it is a reduced expression of $v$ whose initial segment $s_{1} \dots s_{k}$ is the chosen reduced expression of $u$ .

2.2F1A1step 1.1givenalgebra

Conversely, if $v$ has a reduced expression $s_{1} \dots s_{m}$ and $k \leq m$ is such that the initial segment $s_{1} \dots s_{k}$ is a reduced expression of $u$ , then $u \leq_{R} v$ . Indeed the suffix $x : = s_{k + 1} \dots s_{m}$ satisfies $v = u x$ and $ℓ (x) \leq m - k$ , so $ℓ (u) + ℓ (x) \leq k + (m - k) = m = ℓ (v)$ , while subadditivity gives the reverse inequality $ℓ (v) \leq ℓ (u) + ℓ (x)$ ; hence $ℓ (v) = ℓ (u) + ℓ (x)$ , which is the defining condition for $u \leq_{R} v$ by step 1.1.

2.3F1F4F5A1step 1.1givenalgebra

Let $s \in D_{L} (u) \cap D_{L} (v)$ . Then $u \leq_{R} v$ if and only if $s u \leq_{R} s v$ . By [F4], each of $ℓ (s u) - ℓ (u)$ and $ℓ (s v) - ℓ (v)$ lies in ${- 1, + 1}$ ; the strict descent inequalities therefore give $ℓ (s u) = ℓ (u) - 1$ and $ℓ (s v) = ℓ (v) - 1$ . Also $ℓ (s) = 1$ by [F4] and [A1]. For the forward direction assume $u \leq_{R} v$ ; by step 1.1, $v = u x$ with $ℓ (v) = ℓ (u) + ℓ (x)$ . Subadditivity gives $ℓ (s v) = ℓ (s u x) \leq ℓ (s u) + ℓ (x) = ℓ (v) - 1$ , while $v = s (s v)$ by [F5], so $ℓ (v) \leq ℓ (s) + ℓ (s v) = 1 + ℓ (s v)$ and $ℓ (s v) \geq ℓ (v) - 1$ . Therefore $ℓ (s v) = ℓ (s u) + ℓ (x)$ and $s v = s u \cdot x$ , which is $s u \leq_{R} s v$ . For the converse assume $s u \leq_{R} s v$ ; then $s v = s u \cdot x$ with $ℓ (s v) = ℓ (s u) + ℓ (x)$ . Multiplying on the left by $s$ and using [F5] gives $v = u x$ , and the descent identities give $ℓ (v) = ℓ (s v) + 1 = ℓ (s u) + ℓ (x) + 1 = ℓ (u) + ℓ (x)$ , so $u \leq_{R} v$ .

2.4F1A1step 1.1givenalgebra

Assume $u \leq_{R} v$ . Then for every $x \in W$ one has $x \in [1, u^{- 1} v]_{R}$ if and only if $u x \in [u, v]_{R}$ , and in that case $ℓ (u x) = ℓ (u) + ℓ (x)$ . For the forward direction suppose $x \leq_{R} u^{- 1} v$ ; by step 1.1, $ℓ (u^{- 1} v) = ℓ (x) + ℓ (x^{- 1} u^{- 1} v)$ , so $ℓ (v) = ℓ (u) + ℓ (u^{- 1} v) = ℓ (u) + ℓ (x) + ℓ (x^{- 1} u^{- 1} v)$ . Since $ℓ (u x) \leq ℓ (u) + ℓ (x)$ and $ℓ (v) \leq ℓ (u x) + ℓ (x^{- 1} u^{- 1} v)$ both hold by subadditivity, these are equalities, giving $ℓ (u x) = ℓ (u) + ℓ (x)$ and $ℓ (v) = ℓ (u x) + ℓ ((u x)^{- 1} v)$ , that is $u \leq_{R} u x \leq_{R} v$ . For the converse suppose $u \leq_{R} u x \leq_{R} v$ ; then $ℓ (u x) = ℓ (u) + ℓ (x)$ and $ℓ (v) = ℓ (u x) + ℓ (x^{- 1} u^{- 1} v) = ℓ (u) + ℓ (x) + ℓ (x^{- 1} u^{- 1} v)$ , while the hypothesis $u \leq_{R} v$ and step 1.1 give $ℓ (v) = ℓ (u) + ℓ (u^{- 1} v)$ ; cancelling $ℓ (u)$ yields $ℓ (u^{- 1} v) = ℓ (x) + ℓ (x^{- 1} u^{- 1} v)$ , that is $x \leq_{R} u^{- 1} v$ .

3.1F1F2A1step 2.1step 2.2givenalgebra

$u \leq_{L} v$ if and only if there are reduced expressions $u = t_{1} \dots t_{k}$ and $v = t_{1}^{'} \dots t_{q}^{'} t_{1} \dots t_{k}$ . By [F1], $u \leq_{L} v ⟺ u^{- 1} \leq_{R} v^{- 1}$ , and by [F2] inversion preserves lengths; moreover, if $s_{1} \dots s_{m}$ is a reduced expression, then $(s_{1} \dots s_{m})^{- 1} = s_{m} \dots s_{1}$ has length $m = ℓ (s_{1} \dots s_{m}) = ℓ ((s_{1} \dots s_{m})^{- 1})$ , so reversing a reduced expression gives a reduced expression of the inverse. Applying steps 2.1 and 2.2 to the pair $u^{- 1} \leq_{R} v^{- 1}$ and then inverting the two reduced expressions produces exactly the two directions of the claim.

4.1F1F2step 2.4givenalgebra∎

Assume $u \leq_{R} v$ . The map $y \mapsto u y$ on $W$ is a bijection with inverse $y \mapsto u^{- 1} y$ ; by step 2.4 it restricts to a bijection $[1, u^{- 1} v]_{R} \to [u, v]_{R}$ satisfying $ℓ (u x) = ℓ (u) + ℓ (x)$ throughout. For $x, x^{'} \in [1, u^{- 1} v]_{R}$ , if $x \leq_{R} x^{'}$ , then $x^{'} = x y$ with $ℓ (x^{'}) = ℓ (x) + ℓ (y)$ , so $u x^{'} = u x y$ and $ℓ (u x^{'}) = ℓ (u) + ℓ (x^{'}) = ℓ (u) + ℓ (x) + ℓ (y) = ℓ (u x) + ℓ (y)$ , giving $u x \leq_{R} u x^{'}$ ; conversely, if $u x \leq_{R} u x^{'}$ , then $u x^{'} = u x y$ with $ℓ (u x^{'}) = ℓ (u x) + ℓ (y)$ , so cancelling $u$ gives $x^{'} = x y$ , and step 2.4 gives $ℓ (u) + ℓ (x^{'}) = ℓ (u x^{'}) = ℓ (u x) + ℓ (y) = ℓ (u) + ℓ (x) + ℓ (y)$ , hence $ℓ (x^{'}) = ℓ (x) + ℓ (y)$ and $x \leq_{R} x^{'}$ . Thus the bijection preserves and reflects $\leq_{R}$ . If instead $u \leq_{L} v$ , then $u^{- 1} \leq_{R} v^{- 1}$ by [F1]; applying the right-handed result to $u^{- 1} \leq_{R} v^{- 1}$ and inverting gives a bijection $x \mapsto x u$ from $[1, v u^{- 1}]_{L}$ to $[u, v]_{L}$ that preserves and reflects $\leq_{L}$ . Its length identity is $ℓ (x u) = ℓ ((x u)^{- 1}) = ℓ (u^{- 1} x^{- 1}) = ℓ (u^{- 1}) + ℓ (x^{- 1}) = ℓ (u) + ℓ (x)$ by [F2]. No Choice was used anywhere in this proof.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-10-08Open item page →

Weak order is a partial order with finite graded intervals; covers and the inversion-set criterion

Statement

Let $(S, m)$ be a finite Coxeter matrix, $W$ the presented group with length $ℓ$ , descent sets $D_{L}, D_{R}$ , weak orders $\leq_{R}, \leq_{L}$ and intervals $[u, v]_{R}, [u, v]_{L}$ as in The right and left weak orders, intervals, covers, and meets and joins of subsets, with inversion sets $N (w) = {α \in Φ_{+} : ρ (w) α \in Φ_{-}}$ and the recursion of The geometric inversion set $N (w)$ of an element of a Coxeter group (2). Then:

(1) Partial orders. $\leq_{R}$ and $\leq_{L}$ are partial orders on $W$ , both with minimum $1$ ; $u \leq_{R} v$ and $ℓ (u) = ℓ (v)$ imply $u = v$ ; and inversion $w \mapsto w^{- 1}$ is an order isomorphism $(W, \leq_{R}) \to (W, \leq_{L})$ , i.e. $u \leq_{R} v ⟺ u^{- 1} \leq_{L} v^{- 1}$ .

(2) Covers. For all $u, v \in W$ ,

$u ⋖_{R} v ⟺ v = u s for some s \in S with ℓ (v) = ℓ (u) + 1, u ⋖_{L} v ⟺ v = s u for some s \in S with ℓ (v) = ℓ (u) + 1.$

Moreover $u \leq_{R} v$ if and only if there is a chain $u = u_{0} ⋖_{R} u_{1} ⋖_{R} \dots ⋖_{R} u_{m} = v$ , and then necessarily $m = ℓ (v) - ℓ (u)$ ; the same holds in $\leq_{L}$ .

(3) Intervals are finite and graded. For every $k \geq 0$ the ball ${w \in W : ℓ (w) \leq k}$ is finite, with at most $1 + ∣ S ∣ + \dots + ∣ S ∣^{k}$ elements. Consequently, whenever $u \leq_{R} v$ , the interval $[u, v]_{R}$ is finite and $x \mapsto ℓ (x) - ℓ (u)$ is a rank function on it in the sense of Graded poset, rank function, and rank levels; in particular every maximal chain in $[u, v]_{R}$ has exactly $ℓ (v) - ℓ (u) + 1$ elements, and if $u^{- 1} v = s_{1}^{'} \dots s_{m}^{'}$ is a reduced expression then $u ⋖_{R} u s_{1}^{'} ⋖_{R} \dots ⋖_{R} u s_{1}^{'} \dots s_{m}^{'} = v$ is such a maximal chain. The same statements hold for $\leq_{L}$ .

(4) Inversion-set criterion. For all $u, v \in W$ ,

$u \leq_{R} v ⟺ N (u^{- 1}) \subseteq N (v^{- 1}), u \leq_{L} v ⟺ N (u) \subseteq N (v);$

moreover $∣ N (w^{- 1}) ∣ = ∣ N (w) ∣ = ℓ (w)$ for every $w$ . Equivalently, $w \mapsto N (w^{- 1})$ embeds $(W, \leq_{R})$ into the lattice of subsets of $Φ_{+}$ as an order-preserving and length-preserving map. The criterion is not the definition of $\leq_{R}$ ; it is derived from The right and left weak orders, intervals, covers, and meets and joins of subsets.

(5) Descents and roots. For all $w \in W$ and $s \in S$ ,

$s \in D_{L} (w) ⟺ e_{s} \in N (w^{- 1}) ⟺ ρ (w^{- 1}) e_{s} \in Φ_{-}, s \in D_{R} (w) ⟺ e_{s} \in N (w) ⟺ ρ (w) e_{s} \in Φ_{-} .$

No Choice is used.

Facts & Assumptions

Given: A finite Coxeter matrix $(S, m)$ with presented group $W$ , length function $ℓ$ , descent sets $D_{L}, D_{R}$ , weak orders $\leq_{R}, \leq_{L}$ , reflection homomorphism $ρ$ , roots $Φ_{\pm}$ and inversion sets $N (w)$ as in The right and left weak orders, intervals, covers, and meets and joins of subsets and The geometric inversion set $N (w)$ of an element of a Coxeter group; $u, v, x, y, w \in W$ , $s \in S$ , $k \geq 0$ and $m \geq 0$ are arbitrary unless a clause specifies otherwise.

[F1]

The right and left weak orders, intervals, covers, and meets and joins of subsets: $u \leq_{R} v$ means that $v = u x$ for some $x \in W$ with $ℓ (v) = ℓ (u) + ℓ (x)$ , and $u \leq_{L} v$ means that $v = x u$ with the same length condition; $u \leq_{R} v ⟺ u^{- 1} \leq_{L} v^{- 1}$ ; covers, intervals and bounded subsets are defined there.

[F2]

The length identity, the prefix property, left translation, and interval translation for weak order (1): the length identities for $\leq_{R}$ and $\leq_{L}$ , and the resulting monotonicity of length along either relation.

[F3]

Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups: for $w \in W$ , $ℓ (w) = \min {k \in N : there exist s_{1}, \dots, s_{k} \in S with w = s_{1} \dots s_{k}}$ , and a reduced expression is a word realizing this minimum.

[F4]

Length parity, exchange, two-letter deletion, and faithfulness of the signed reflection action (1): for all $w$ and $s$ , $ℓ (s w) = ℓ (w) \pm 1$ and $ℓ (w s) = ℓ (w) \pm 1$ , with $ℓ (s w) \equiv ℓ (w) + 1$ modulo $2$ and likewise on the right.

[F5]

The geometric inversion set $N (w)$ of an element of a Coxeter group (2): for $u \in W$ , $s \in S$ the recursions $N (u s) = {e_{s}} ⊔ s N (u)$ when $ℓ (u s) > ℓ (u)$ and $N (u s) = s (N (u) ∖ {e_{s}})$ when $ℓ (u s) < ℓ (u)$ .

[F6]

The inversion formula $∣ N (w) ∣ = ℓ (w)$ , the root-reflection dictionary and strong exchange (2): for every $w$ , $∣ N (w) ∣ = ℓ (w)$ , and for a reduced expression $w = s_{1} \dots s_{n}$ , $N (w)$ and $N (w^{- 1})$ are the sets of suffix roots $ρ (s_{i + 1} \dots s_{n})^{- 1} e_{s_{i}}$ and prefix roots $ρ (s_{1} \dots s_{i - 1}) e_{s_{i}}$ respectively, pairwise distinct. In particular, the prefix-root list has $ℓ (w)$ distinct elements, so $∣ N (w^{- 1}) ∣ = ℓ (w)$ ; applying the cardinality formula to $w^{- 1}$ gives $ℓ (w^{- 1}) = ∣ N (w^{- 1}) ∣ = ℓ (w)$ .

[F7]

The root-length criterion and faithfulness of the canonical reflection representation (1): for all $w$ and $s$ , $ℓ (w s) > ℓ (w) ⟺ ρ (w) e_{s} \in Φ_{+}$ and $ℓ (w s) < ℓ (w) ⟺ ρ (w) e_{s} \in Φ_{-}$ .

[F8]

[F9]

Graded poset, rank function, and rank levels: a rank function on a finite poset $P$ is a map $ρ : P \to N$ with every minimal element of rank $0$ and $ρ (y) = ρ (x) + 1$ whenever $y$ covers $x$ ; a poset admitting one is graded.

[F10]

Intervals in a poset; locally finite, lower-finite and upper-finite posets: $[x, y] = {z : x \leq z \leq y}$ for comparable elements, and a poset is locally finite when all its intervals are finite.

[F11]

Partial order and partially ordered set: a partial order is reflexive, antisymmetric and transitive.

[F12]

Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups: each defining generator satisfies $s^{2} = 1$ in $W$ .

[F13]

The geometric inversion set $N (w)$ of an element of a Coxeter group (1): $N (w) = {α \in Φ_{+} : ρ (w) α \in Φ_{-}}$ .

[F14]

The length identity, the prefix property, left translation, and interval translation for weak order (2): the reduced-word prefix property: $u \leq_{R} v$ exactly when some reduced expression of $v$ has a reduced expression of $u$ as its initial segment.

[F15]

The length identity, the prefix property, left translation, and interval translation for weak order (3): if $s \in D_{L} (u) \cap D_{L} (v)$ , then $u \leq_{R} v ⟺ s u \leq_{R} s v$ .

[A1]

Consequences of [F3] used throughout: $ℓ (1) = 0$ ; $ℓ (a) = 0$ implies $a = 1$ ; and $ℓ (a b) \leq ℓ (a) + ℓ (b)$ . Also $ℓ (s) = 1$ for every $s \in S$ : applying [F4] (1) at $w = 1$ gives $ℓ (s) = ℓ (1) \pm 1$ , and nonnegativity of length forces $ℓ (s) = 1$ .

Proof

1.1F1F3A1givenalgebra

Reflexivity and minimum: for every $v \in W$ one has $v = v \cdot 1$ with $ℓ (v) = ℓ (v) + ℓ (1) = ℓ (v) + 0$ , so $v \leq_{R} v$ , and $1 \cdot v = v$ with $ℓ (v) = ℓ (1) + ℓ (v)$ , so $1 \leq_{R} v$ ; reading the same products in the other order gives $v \leq_{L} v$ and $1 \leq_{L} v$ . Hence both relations are reflexive and $1$ is below every element in both orders.

1.2F1A1givenalgebra

Transitivity: if $u \leq_{R} y$ and $y \leq_{R} v$ , write $y = u x$ and $v = y x^{'}$ with $ℓ (y) = ℓ (u) + ℓ (x)$ and $ℓ (v) = ℓ (y) + ℓ (x^{'})$ . Then $v = u (x x^{'})$ , and $ℓ (v) = ℓ (u) + ℓ (x) + ℓ (x^{'}) \geq ℓ (u) + ℓ (x x^{'}) \geq ℓ (v)$ by subadditivity together with the word bound $v = u (x x^{'})$ ; hence $ℓ (v) = ℓ (u) + ℓ (x x^{'})$ and $u \leq_{R} v$ . The same computation with the products in the other order shows that $\leq_{L}$ is transitive.

1.3F1givenalgebra

Inversion: the map $w \mapsto w^{- 1}$ is a bijection of $W$ with inverse itself, and $u \leq_{R} v ⟺ u^{- 1} \leq_{L} v^{- 1}$ for all $u, v$ ; hence it is an order isomorphism $(W, \leq_{R}) \to (W, \leq_{L})$ . This completes clause (1).

1.4F3A1givenalgebra

Ball finiteness: every $w$ with $ℓ (w) \leq k$ has a reduced expression of length $ℓ (w) \leq k$ , so the ball ${w : ℓ (w) \leq k}$ is the set of values of the finitely many words in $S$ of lengths $0, 1, \dots, k$ ; those words number $1 + ∣ S ∣ + \dots + ∣ S ∣^{k}$ , and listing their values exhibits the ball as the image of a finite list, hence finite with at most that many elements.

1.5F6F14givenalgebra

The criterion, forward direction, and cardinalities: if $u \leq_{R} v$ , then $N (u^{- 1}) \subseteq N (v^{- 1})$ . By the prefix property there are reduced expressions $u = s_{1} \dots s_{k}$ and $v = s_{1} \dots s_{k} s_{1}^{'} \dots s_{q}^{'}$ . By the prefix-root formula, $N (u^{- 1}) = {ρ (s_{1} \dots s_{i - 1}) e_{s_{i}} : 1 \leq i \leq k}$ and $N (v^{- 1}) = {ρ (s_{1} \dots s_{j - 1}) e_{s_{j}} : 1 \leq j \leq k + q}$ , so the first is contained in the second. The same formula gives $∣ N (w) ∣ = ℓ (w)$ and $∣ N (w^{- 1}) ∣ = ℓ (w)$ for every $w$ .

2.1F1F2A1F11step 1.1step 1.2givenalgebra

Antisymmetry and equal-length uniqueness: if $u \leq_{R} v$ and $v \leq_{R} u$ then $ℓ (u) \leq ℓ (v) \leq ℓ (u)$ , so $ℓ (u) = ℓ (v)$ ; then $ℓ (u^{- 1} v) = ℓ (v) - ℓ (u) = 0$ by the length identity, so $u^{- 1} v = 1$ and $v = u$ . In particular $u \leq_{R} v$ together with $ℓ (u) = ℓ (v)$ forces $u = v$ ; the same argument in $\leq_{L}$ gives antisymmetry there. Together with steps 1.1 and 1.2 this shows that $\leq_{R}$ and $\leq_{L}$ are partial orders with minimum $1$ .

2.2F3F4F5F6F7F8F12F13F15A1step 1.1step 1.5givenalgebra

The criterion, converse direction, by induction on $ℓ (u)$ : assume $N (u^{- 1}) \subseteq N (v^{- 1})$ ; then $u \leq_{R} v$ . If $ℓ (u) = 0$ then $u = 1$ and $1 \leq_{R} v$ by step 1.1. Otherwise choose a reduced expression $u = s t_{2} \dots t_{k}$ with $k = ℓ (u) \geq 1$ . By [F12], $s u = t_{2} \dots t_{k}$ , so $ℓ (s u) \leq k - 1 = ℓ (u) - 1$ ; by the length-change property [F4] this forces $ℓ (s u) = ℓ (u) - 1$ , hence $s \in D_{L} (u)$ by [F8]. The root-length criterion applied to $u^{- 1}$ and the definition of $N$ give $e_{s} \in N (u^{- 1}) \subseteq N (v^{- 1})$ , and the same criterion for $v^{- 1}$ gives $s \in D_{L} (v)$ . By the left-translation property [F15] it suffices to prove $s u \leq_{R} s v$ ; the induction hypothesis applies to the shorter element $s u$ once $N ((s u)^{- 1}) \subseteq N ((s v)^{- 1})$ is shown. Now $(s u)^{- 1} = u^{- 1} s$ and $(s v)^{- 1} = v^{- 1} s$ . By [F6], $ℓ ((s u)^{- 1}) = ℓ (s u) = ℓ (u) - 1 < ℓ (u^{- 1})$ ; likewise $ℓ ((s v)^{- 1}) < ℓ (v^{- 1})$ , so the descent case of the recursion [F5] gives $N (u^{- 1} s) = s (N (u^{- 1}) ∖ {e_{s}})$ and $N (v^{- 1} s) = s (N (v^{- 1}) ∖ {e_{s}})$ . Since $e_{s}$ lies in both $N (u^{- 1})$ and $N (v^{- 1})$ , the inclusion remains true after removing $e_{s}$ , and applying the map $ρ (s)$ to both sets preserves inclusion; hence $N ((s u)^{- 1}) \subseteq N ((s v)^{- 1})$ . Thus $s u \leq_{R} s v$ by induction and $u \leq_{R} v$ by left translation.

3.1F1F2F3F6A1step 2.1givenalgebra

Cover characterization: $u ⋖_{R} v$ if and only if $v = u s$ for some $s \in S$ with $ℓ (v) = ℓ (u) + 1$ . For the forward direction assume $u ⋖_{R} v$ ; then $u \leq_{R} v$ with $u \neq v$ , so $v = u x$ with $ℓ (v) = ℓ (u) + ℓ (x)$ and $x \neq 1$ . Write a reduced expression $x = s_{1} \dots s_{k}$ , $k = ℓ (x) \geq 1$ , and put $u_{i} : = u s_{1} \dots s_{i}$ for $0 \leq i \leq k$ . For each $i$ , subadditivity gives $ℓ (u_{i}) \leq ℓ (u) + i$ . Put $y_{i} : = s_{i + 1} \dots s_{k}$ (the empty word when $i = k$ ); its displayed word gives $ℓ (y_{i}) \leq k - i$ , and $v = u_{i} y_{i}$ . Hence $ℓ (v) \leq ℓ (u_{i}) + ℓ (y_{i}) \leq ℓ (u_{i}) + k - i$ , so $ℓ (u_{i}) \geq ℓ (u) + i$ and therefore $ℓ (u_{i}) = ℓ (u) + i$ . Since $ℓ (v) = ℓ (u) + k$ and $ℓ (u_{i}) = ℓ (u) + i$ , subadditivity in $v = u_{i} y_{i}$ also gives $ℓ (y_{i}) \geq k - i$ ; together with the displayed-word bound this yields $ℓ (y_{i}) = k - i$ for every $i$ . If $k \geq 2$ , then $u_{1} = u s_{1}$ and $ℓ (s_{1}) = 1$ by [A1], so $u <_{R} u_{1}$ . Since $v = u_{1} y_{1}$ and $ℓ (y_{1}) = k - 1$ , one has $u_{1} \leq_{R} v$ ; also $ℓ (u_{1}) < ℓ (v)$ , giving $u <_{R} u_{1} <_{R} v$ , contrary to the cover. Thus $k = 1$ , $v = u s_{1}$ and $ℓ (v) = ℓ (u) + 1$ . For the converse assume $v = u s$ and $ℓ (v) = ℓ (u) + 1$ ; by [A1], $ℓ (s) = 1$ , so $u \leq_{R} v$ . If $u \leq_{R} w \leq_{R} v$ , the length identity [F2] gives $ℓ (u) \leq ℓ (w) \leq ℓ (u) + 1$ . If $ℓ (w) = ℓ (u)$ then $w = u$ by step 2.1; if $ℓ (w) = ℓ (v)$ then $w = v$ by step 2.1. Hence no element lies strictly between $u$ and $v$ , and $u \neq v$ , so $u ⋖_{R} v$ . For the left-handed version, $u ⋖_{L} v$ is equivalent under the inversion isomorphism [F1] to $u^{- 1} ⋖_{R} v^{- 1}$ ; the right-handed result and length invariance [F6] give $v^{- 1} = u^{- 1} s$ with a one-length rise, hence $v = s u$ with $ℓ (v) = ℓ (u) + 1$ , and conversely.

3.2F1step 2.1step 1.5step 2.2givenalgebra

The left criterion and the embedding: by [F1], $u \leq_{L} v ⟺ u^{- 1} \leq_{R} v^{- 1}$ , and applying steps 1.5 and 2.2 to the pair $(u^{- 1}, v^{- 1})$ gives $u \leq_{L} v ⟺ N (u) \subseteq N (v)$ . Hence $w \mapsto N (w^{- 1})$ preserves and reflects $\leq_{R}$ and is injective, since $N (u^{- 1}) = N (v^{- 1})$ yields $u \leq_{R} v$ and $v \leq_{R} u$ , hence $u = v$ by antisymmetry; it is length-preserving by $∣ N (w^{- 1}) ∣ = ℓ (w)$ . This completes clause (4).

4.1F1F2F6step 1.2step 3.1givenalgebra

Chains of covers: $u \leq_{R} v$ if and only if there is a chain $u = u_{0} ⋖_{R} u_{1} ⋖_{R} \dots ⋖_{R} u_{m} = v$ , and then $m = ℓ (v) - ℓ (u)$ . If $u \leq_{R} v$ , put $x : = u^{- 1} v$ , so $ℓ (x) = ℓ (v) - ℓ (u)$ ; choose a reduced expression $x = s_{1} \dots s_{m}$ and set $u_{i} : = u s_{1} \dots s_{i}$ . The estimates in step 3.1 give $ℓ (u_{i}) = ℓ (u) + i$ and $ℓ (s_{i + 1} \dots s_{m}) = m - i$ , so $u \leq_{R} u_{i} \leq_{R} v$ for every $i$ . Since $u_{i + 1} = u_{i} s_{i + 1}$ and $ℓ (u_{i + 1}) = ℓ (u_{i}) + 1$ , each consecutive pair is a cover by step 3.1's converse, giving a chain of $m = ℓ (v) - ℓ (u)$ covers. Conversely, if $u = u_{0} ⋖_{R} \dots ⋖_{R} u_{m} = v$ , then repeated transitivity from step 1.2 gives $u \leq_{R} v$ , and each cover adds exactly one to the length by step 3.1's forward direction, so $ℓ (v) = ℓ (u) + m$ and $m = ℓ (v) - ℓ (u)$ . For left order, apply the right-hand result to $u^{- 1} \leq_{R} v^{- 1}$ and invert each element of the chain; inversion preserves covers by [F1] and lengths by [F6].

5.1F1F2F3F6F9F10A1step 3.1step 4.1step 1.4givenalgebra

Graded intervals: if $u \leq_{R} v$ , then $[u, v]_{R} \subseteq {w : ℓ (w) \leq ℓ (v)}$ by the length identity, so $[u, v]_{R}$ is finite by step 1.4 and is a finite poset with least element $u$ ; its unique minimal element is $u$ , because every $x \in [u, v]_{R}$ satisfies $u \leq_{R} x$ . The map $x \mapsto ℓ (x) - ℓ (u)$ takes values in $N$ on $[u, v]_{R}$ and has value $0$ at $u$ . If $x ⋖ y$ in the interval poset, then $x <_{R} y$ and no $z$ with $x <_{R} z <_{R} y$ lies in $[u, v]_{R}$ ; an intermediate $z$ in $W$ would satisfy $u \leq_{R} x <_{R} z <_{R} y \leq_{R} v$ , hence lie in $[u, v]_{R}$ , so $x ⋖_{R} y$ in $W$ as well, and step 3.1's forward direction gives $ℓ (y) = ℓ (x) + 1$ . Thus $x \mapsto ℓ (x) - ℓ (u)$ is a rank function, so $[u, v]_{R}$ is graded. A maximal chain $u = x_{0} < \dots < x_{t} = v$ in it consists of covers, so its ranks increase by one at each step from $0$ to $ℓ (v) - ℓ (u)$ : it has exactly $ℓ (v) - ℓ (u) + 1$ elements. Finally, for a reduced expression $u^{- 1} v = s_{1}^{'} \dots s_{m}^{'}$ , the chain of step 4.1, $u ⋖_{R} u s_{1}^{'} ⋖_{R} \dots ⋖_{R} u s_{1}^{'} \dots s_{m}^{'} = v$ , is a chain of covers in $W$ between elements of $[u, v]_{R}$ , hence a maximal chain in $[u, v]_{R}$ . For left order, inversion identifies $[u, v]_{L}$ with $[u^{- 1}, v^{- 1}]_{R}$ and [F6] shows that the length shift is preserved; the same rank and maximal-chain conclusions follow.

6.1F6F7F8F13givenalgebra∎

The descent-root dictionary: for $w \in W$ and $s \in S$ , $s \in D_{L} (w)$ means $ℓ (s w) < ℓ (w)$ ; since $ℓ (s w) = ℓ ((s w)^{- 1}) = ℓ (w^{- 1} s)$ and [F6] gives $ℓ (w^{- 1}) = ℓ (w)$ , the root-length criterion applied to $w^{- 1}$ gives $s \in D_{L} (w) ⟺ ρ (w^{- 1}) e_{s} \in Φ_{-}$ , which by [F13] is equivalent to $e_{s} \in N (w^{- 1})$ . Similarly, $s \in D_{R} (w)$ means $ℓ (w s) < ℓ (w)$ , which by the root-length criterion applied to $w$ is equivalent to $ρ (w) e_{s} \in Φ_{-}$ , that is to $e_{s} \in N (w)$ . No Choice was used anywhere in this proof.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6.1-sol)audited 2026-10-08Open item page →

Binary meets, meets of arbitrary nonempty subsets, and joins of bounded subsets in weak order

Statement

Let $(S, m)$ be a finite Coxeter matrix, $W$ the presented group with length $ℓ$ , descent sets $D_{L}, D_{R}$ , weak orders $\leq_{R}, \leq_{L}$ and intervals as in The right and left weak orders, intervals, covers, and meets and joins of subsets, so that $\leq_{R}$ is a graded partial order by Weak order is a partial order with finite graded intervals; covers and the inversion-set criterion. Then:

(1) Binary meets. For all $x, y \in W$ the set $E (x, y) : = [1, x]_{R} \cap [1, y]_{R}$ of common lower bounds is finite, and each element of $E (x, y)$ of maximal length is the meet $x \land y$ ; in particular $x \land y$ exists, and $x \land y = 1$ if and only if $E (x, y) = {1}$ .

(2) Meets of nonempty subsets. Every nonempty subset $A \subseteq W$ has a meet $⋀ A$ . Explicitly, if $x_{0} \in A$ and one repeatedly replaces a current candidate $x_{i}$ by $x_{i + 1} : = x_{i} \land y_{i}$ for some $y_{i} \in A$ with $x_{i} ̸ \leq_{R} y_{i}$ , then the lengths $ℓ (x_{i})$ strictly decrease, so the procedure stops after at most $ℓ (x_{0})$ replacements at a candidate $x_{i} \leq_{R} y$ for all $y \in A$ , and this candidate is $⋀ A$ ; only finitely many choices are made.

(3) Joins of bounded subsets. If a nonempty subset $A \subseteq W$ is bounded above in $\leq_{R}$ , then its set $U (A)$ of upper bounds is nonempty and

$⋁ A = ⋀ U (A),$

the least upper bound of $A$ . The analogous statements hold in $\leq_{L}$ , and inversion exchanges the two. No Choice is used.

Facts & Assumptions

Given: A finite Coxeter matrix $(S, m)$ with presented group $W$ , length function $ℓ$ , descent sets $D_{L}, D_{R}$ , weak orders $\leq_{R}, \leq_{L}$ and intervals as in The right and left weak orders, intervals, covers, and meets and joins of subsets; subsets $A \subseteq W$ and elements $u, w, x, y, z, x_{0}, \dots \in W$ and $s \in S$ as specified in each clause.

[F1]

The right and left weak orders, intervals, covers, and meets and joins of subsets (1): $u \leq_{R} v$ iff $v = u x$ with $ℓ (v) = ℓ (u) + ℓ (x)$ , and $u \leq_{L} v$ iff $v = x u$ with the same length-additive condition; inversion exchanges the two relations.

[F2]

The length identity, the prefix property, left translation, and interval translation for weak order (1): the length identity $u \leq_{R} v ⟺ ℓ (v) = ℓ (u) + ℓ (u^{- 1} v)$ and the resulting monotonicity of length along either weak order.

[F3]

Weak order is a partial order with finite graded intervals; covers and the inversion-set criterion (1): both weak orders are partial orders with minimum $1$ ; comparable elements of equal length coincide; and inversion is an order isomorphism between the two weak orders.

[F4]

[F5]

Length parity, exchange, two-letter deletion, and faithfulness of the signed reflection action (2), Tits exchange: if $w = s_{1} \dots s_{k}$ is reduced and $ℓ (s w) = k - 1$ , then $s w = s_{1} \dots \hat{s_{i}} \dots s_{k}$ for some $i$ .

[F6]

The geometric inversion set $N (w)$ of an element of a Coxeter group (1),(2): $N (w) = {α \in Φ_{+} : ρ (w) α \in Φ_{-}}$ , and for $u \in W$ , $s \in S$ , $ℓ (u s) > ℓ (u)$ implies $N (u s) = {e_{s}} ⊔ s N (u)$ while $ℓ (u s) < ℓ (u)$ implies $N (u s) = s (N (u) ∖ {e_{s}})$ .

[F7]

Standard parabolic subgroups, descent-free one- and two-sided representatives, parabolic and reflection subgroups (2): $D_{L} (w) = {s \in S : ℓ (s w) < ℓ (w)}$ and $D_{R} (w) = {s \in S : ℓ (w s) < ℓ (w)}$ ; both left and right multiplication by a simple generator change length by exactly $1$ or $- 1$ .

[F8]

Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups: each simple generator $s \in S$ satisfies $s^{2} = 1$ in $W$ .

[F9]

The length identity, the prefix property, left translation, and interval translation for weak order (2): the reduced-word prefix property: if $u \leq_{R} v$ , some reduced expression of $v$ has a reduced expression of $u$ as its initial segment.

[F10]

The length identity, the prefix property, left translation, and interval translation for weak order (3): for $s \in D_{L} (u) \cap D_{L} (v)$ , $u \leq_{R} v ⟺ s u \leq_{R} s v$ .

[F11]

The canonical reflection homomorphism, roots, reflections, and the positive cone (1): $ρ : W \to G L (V)$ is a group homomorphism, so $ρ (s)^{2} = I_{V}$ follows from $s^{2} = 1$ .

[F12]

The right and left weak orders, intervals, covers, and meets and joins of subsets (2): the intervals $[u, v]_{R} = {w : u \leq_{R} w and w \leq_{R} v}$ and their left analogues are defined for the two binary relations.

[F13]

The right and left weak orders, intervals, covers, and meets and joins of subsets (3): a meet is a greatest lower bound and a join is a least upper bound, with the analogous definitions for subsets; such a bound is unique when it exists.

[F14]

Weak order is a partial order with finite graded intervals; covers and the inversion-set criterion (3): every interval in right weak order is finite.

[F15]

Weak order is a partial order with finite graded intervals; covers and the inversion-set criterion (4): $u \leq_{R} v ⟺ N (u^{- 1}) \subseteq N (v^{- 1})$ and $∣ N (w^{- 1}) ∣ = ∣ N (w) ∣ = ℓ (w)$ ; applying this cardinality formula to $w^{- 1}$ gives $ℓ (w^{- 1}) = ℓ (w)$ .

[F16]

Weak order is a partial order with finite graded intervals; covers and the inversion-set criterion (5): $s \in D_{L} (w) ⟺ e_{s} \in N (w^{- 1})$ .

[A1]

Consequences of [F4] used throughout: $ℓ (1) = 0$ and $ℓ (a b) \leq ℓ (a) + ℓ (b)$ . Also $ℓ (s) = 1$ for each $s \in S$ : [F7] at $w = 1$ gives $ℓ (s) = ℓ (1) \pm 1$ , and nonnegative length forces the value $1$ .

Proof

1.1F12F14givenalgebra

For all $x, y \in W$ the set $E (x, y) = [1, x]_{R} \cap [1, y]_{R}$ is finite: by [F14] the interval $[1, x]_{R} = {w : w \leq_{R} x}$ is finite, and $E (x, y) \subseteq [1, x]_{R}$ is a subset of a finite set, hence finite; in particular $E (x, y)$ has an element of maximal length.

1.2F1F5F7F8F9A1givenalgebra

Common atoms: let $z \in E (x, y)$ have maximal length and let $s \in S$ lie in $E (x, y)$ ; then $s \leq_{R} z$ . By [F9], $z \leq_{R} x$ and $z \leq_{R} y$ give reduced expressions $x = z x^{'}$ and $y = z y^{'}$ with $ℓ (x) = ℓ (z) + ℓ (x^{'})$ and $ℓ (y) = ℓ (z) + ℓ (y^{'})$ . Suppose, for contradiction, that $ℓ (s z) = ℓ (z) + 1$ ; by [F7] the only other possibility is $ℓ (s z) = ℓ (z) - 1$ , so this is the case to exclude. Since $s \leq_{R} x$ , the defining length-additive factorization gives $x = s a$ and $ℓ (x) = ℓ (s) + ℓ (a)$ for some $a$ ; as $s^{2} = 1$ , $a = s x$ , and [A1] gives $ℓ (x) = 1 + ℓ (s x)$ . Thus Tits exchange [F5] applies to the reduced expression $z_{r e d} x_{r e d}^{'}$ of $x$ and the letter $s$ : the element $s x$ is that word with exactly one letter deleted. If the deleted letter lies in $z_{r e d}$ , then $s x = \tilde{z} x^{'}$ for the word $\tilde{z}$ obtained from $z_{r e d}$ by deleting one letter, so $ℓ (\tilde{z}) \leq ℓ (z) - 1$ ; cancelling $x^{'}$ on the right in $x = z x^{'} = s \tilde{z} x^{'}$ gives $z = s \tilde{z}$ , and $s^{2} = 1$ gives $s z = \tilde{z}$ , whence $ℓ (s z) = ℓ (\tilde{z}) \leq ℓ (z) - 1$ , contradicting $ℓ (s z) = ℓ (z) + 1$ . If instead the deleted letter lies in $x_{r e d}^{'}$ , then $s x = z x^{''}$ for the word $x^{''}$ obtained from $x_{r e d}^{'}$ by deleting one letter, so $ℓ (x^{''}) \leq ℓ (x^{'}) - 1$ . Since $z = s (s z)$ , $s^{2} = 1$ gives $x = (s z) x^{''}$ ; therefore $ℓ (x) = ℓ (z) + ℓ (x^{'}) \leq ℓ (s z) + ℓ (x^{''})$ forces $ℓ (x^{''}) = ℓ (x^{'}) - 1$ . Hence $x = (s z) x^{''}$ is length-additive and $s z \leq_{R} x$ with $ℓ (s z) = ℓ (z) + 1$ ; the same argument using $y = z y^{'}$ gives $s z \leq_{R} y$ . Then $s z \in E (x, y)$ has length larger than the maximal length $ℓ (z)$ , a contradiction. Hence $ℓ (s z) = ℓ (z) - 1$ , that is $s \leq_{R} z$ .

1.3F3F12F13givenalgebra

The remaining assertions of clause (1): if $E (x, y) = {1}$ then $1$ is the only common lower bound, hence the greatest one, so $x \land y = 1$ ; conversely if $x \land y = 1$ then every $w \in E (x, y)$ satisfies $w \leq_{R} x \land y = 1$ with $1 \leq_{R} w$ , so $w = 1$ by antisymmetry, and $E (x, y) = {1}$ . This completes clause (1).

2.1F1F2F3F6F7F8F10F11F13F15F16A1step 1.2givenalgebra

Every $w \in E (x, y)$ satisfies $w \leq_{R} z$ for every $z \in E (x, y)$ of maximal length; hence such a $z$ is the meet $x \land y$ . We prove the first claim by induction on $ℓ (x) + ℓ (y)$ ; the case $w = 1$ is the minimum property of $1$ , so assume $w \neq 1$ . Choose a reduced expression $w = s v$ with first letter $s$ . Its suffix $v$ must be reduced, since otherwise replacing it by a shorter expression would shorten $w$ ; hence $ℓ (v) = ℓ (w) - 1$ ; since $s^{2} = 1$ , $s w = v$ , and therefore $s \in D_{L} (w)$ by [F7]. Since $w \leq_{R} x$ , the length identity gives $ℓ (x) = ℓ (w) + ℓ (w^{- 1} x)$ , so $ℓ (s x) \leq ℓ (s w) + ℓ (w^{- 1} x) = ℓ (x) - 1$ by subadditivity. The $\pm 1$ length change in [F7] forces $ℓ (s x) = ℓ (x) - 1$ , hence $s \in D_{L} (x)$ ; symmetrically $s \in D_{L} (y)$ . By step 1.2, $s \leq_{R} z$ . The length-additive factorization of $z$ by $s$ and $s^{2} = 1$ give $z = s (s z)$ and $ℓ (s z) = ℓ (z) - 1$ , so $s \in D_{L} (z)$ by [F7]. Since $x = z \cdot (z^{- 1} x)$ and $z = s (s z)$ are length-additive, $s x = (s z) (z^{- 1} x)$ and $ℓ (s x) = ℓ (x) - 1 = ℓ (s z) + ℓ (z^{- 1} x)$ ; hence $s z \leq_{R} s x$ and, symmetrically, $s z \leq_{R} s y$ . The induction hypothesis applied to $(s x, s y)$ , whose length sum is $ℓ (x) + ℓ (y) - 2$ , provides the meet $z^{'} : = s x \land s y$ , and $s z \leq_{R} z^{'}$ by its universal property. Because $s \in D_{L} (w) \cap D_{L} (x)$ and $w \leq_{R} x$ , [F10] gives $s w \leq_{R} s x$ ; similarly $s w \leq_{R} s y$ , so the meet property gives $s w \leq_{R} z^{'}$ . Next, $s z^{'} \leq_{R} x$ and $s z^{'} \leq_{R} y$ : from $z^{'} \leq_{R} s x$ the inversion criterion gives $N (z^{' - 1}) \subseteq N ((s x)^{- 1}) = N (x^{- 1} s)$ . Since $s \in D_{L} (x)$ , the descent dictionary gives $e_{s} \in N (x^{- 1})$ , and [F15] gives $ℓ (x^{- 1} s) = ℓ ((s x)^{- 1}) = ℓ (s x) = ℓ (x) - 1 < ℓ (x^{- 1})$ ; thus the descent recursion gives $N (x^{- 1} s) = s (N (x^{- 1}) ∖ {e_{s}})$ . By [F7] and [F3], $ℓ (z^{' - 1} s)$ differs from $ℓ (z^{' - 1})$ by $1$ , so one of the two recursions in [F6] gives $N (z^{' - 1} s) \subseteq {e_{s}} \cup s N (z^{' - 1})$ . Applying $ρ (s)$ to $N (z^{' - 1}) \subseteq s (N (x^{- 1}) ∖ {e_{s}})$ and using [F11] gives $s N (z^{' - 1}) \subseteq N (x^{- 1}) ∖ {e_{s}}$ , so $N ((s z^{'})^{- 1}) = N (z^{' - 1} s) \subseteq {e_{s}} \cup (N (x^{- 1}) ∖ {e_{s}}) = N (x^{- 1})$ because $e_{s} \in N (x^{- 1})$ . The inversion criterion gives $s z^{'} \leq_{R} x$ , and the same argument gives $s z^{'} \leq_{R} y$ . Hence $s z^{'} \in E (x, y)$ and $ℓ (s z^{'}) \leq ℓ (z)$ by maximality. If $ℓ (s z^{'}) = ℓ (z^{'}) - 1$ , then $z^{'} = s (s z^{'})$ with additive length, so $s \leq_{R} z^{'}$ ; transitivity with $z^{'} \leq_{R} s x$ would give $s \leq_{R} s x$ . By $s^{2} = 1$ and $ℓ (s) = 1$ , this means $ℓ (s x) = ℓ (s) + ℓ (x) = 1 + ℓ (x)$ , contradicting $ℓ (s x) = ℓ (x) - 1$ . Thus $ℓ (s z^{'}) = ℓ (z^{'}) + 1$ and $ℓ (z^{'}) = ℓ (s z^{'}) - 1 \leq ℓ (z) - 1 = ℓ (s z) \leq ℓ (z^{'})$ , the last inequality from $s z \leq_{R} z^{'}$ . Hence $ℓ (s z) = ℓ (z^{'})$ and the equal-length property in [F3] yields $s z = z^{'}$ . We now have $s w \leq_{R} z^{'} = s z$ , and $s \in D_{L} (w) \cap D_{L} (z)$ ; [F10] in its reverse direction gives $w \leq_{R} z$ , completing the induction. Therefore every element of $E (x, y)$ lies below $z$ , while $z \in E (x, y)$ ; so $z$ is the greatest lower bound $x \land y$ , and in particular the meet exists and is an element of $E (x, y)$ of maximal length.

3.1F1F3F4F13A1step 2.1step 1.3givenalgebra

Meets of nonempty subsets: let $A \neq \emptyset$ and $x_{0} \in A$ . We run the procedure of the statement and verify its invariants. If $u$ is a lower bound of $A$ and $u \leq_{R} x_{i}$ , and $x_{i + 1} = x_{i} \land y_{i}$ with $y_{i} \in A$ , then $u \leq_{R} x_{i}$ and $u \leq_{R} y_{i}$ (the latter because $u$ is a lower bound of $A$ ), so $u \leq_{R} x_{i + 1}$ by the universal property of the meet; the invariant "every lower bound of $A$ is below the current candidate" therefore persists from $x_{0}$ , which satisfies it because $x_{0} \in A$ . Each replacement gives $x_{i + 1} = x_{i} \land y_{i} \leq_{R} x_{i}$ and $x_{i + 1} \neq x_{i}$ (else $x_{i} \leq_{R} y_{i}$ , contrary to the choice of $y_{i}$ ), so $ℓ (x_{i + 1}) < ℓ (x_{i})$ by the equal-length property of [F3]; as $ℓ$ takes values in $N$ by [F4], the procedure stops after at most $ℓ (x_{0})$ replacements. At a stopping stage $x_{i} \leq_{R} y$ for all $y \in A$ , so $x_{i}$ is a lower bound of $A$ ; and every lower bound $u$ of $A$ satisfies $u \leq_{R} x_{i}$ by the invariant, so $x_{i}$ is the greatest lower bound $⋀ A$ . At each nonstopping stage, failure of $x_{i} \leq_{R} y$ for all $y \in A$ supplies a witness $y_{i} \in A$ . The strictly decreasing natural lengths bound the recursion by $ℓ (x_{0})$ updates, so it selects at most $ℓ (x_{0}) + 1$ elements including $x_{0}$ ; this finite recursion uses no Axiom of Choice, and each meet $x_{i} \land y_{i}$ is uniquely determined.

4.1F1F13step 3.1givenalgebra

Joins of bounded subsets: let $A \neq \emptyset$ be bounded above in $\leq_{R}$ , so that its set of upper bounds $U (A)$ is nonempty. By step 3.1 the meet $z : = ⋀ U (A)$ exists. For every $a \in A$ and every $u \in U (A)$ one has $a \leq_{R} u$ , so each $a \in A$ is a lower bound of $U (A)$ and therefore $a \leq_{R} z$ ; hence $z$ is an upper bound of $A$ . If $u$ is any upper bound of $A$ , then $u \in U (A)$ and $z \leq_{R} u$ because $z$ is the greatest lower bound of $U (A)$ . Therefore $z$ is the least upper bound $⋁ A$ .

5.1F1F3F13step 2.1step 3.1step 4.1givenalgebra∎

The left-order statements follow by inversion: the map $w \mapsto w^{- 1}$ is an order isomorphism $(W, \leq_{R}) \to (W, \leq_{L})$ , so it carries $E (x, y)$ , $U (A)$ and every universal bound property for $\leq_{R}$ into the corresponding objects for $\leq_{L}$ ; explicitly, meets in $\leq_{L}$ are the inverses of meets in $\leq_{R}$ of the inverted sets. No Choice was used anywhere in this proof.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6.1-sol)audited 2026-10-08Open item page →

An element with full left descent makes the Coxeter group finite and is the longest element

Statement

Let $(S, m)$ be a finite Coxeter matrix, $W$ the presented group with length $ℓ$ , $V = R^{S}$ with Coxeter form $B$ , the canonical reflection homomorphism $ρ$ , the signed root system $Φ = Φ_{+} ⊔ Φ_{-}$ , the positive cone $V_{+} = {\sum_{s} λ_{s} e_{s} : λ_{s} \geq 0}$ and the reflection set $T$ (The real Coxeter form, its radical, reflections, and form-preserving maps, The canonical reflection homomorphism, roots, reflections, and the positive cone, Root sign coherence and the action of simple reflections on positive roots), with inversion sets $N (w)$ (The geometric inversion set $N (w)$ of an element of a Coxeter group) and descent sets $D_{L}, D_{R}$ (Standard parabolic subgroups, descent-free one- and two-sided representatives, parabolic and reflection subgroups (2)).

(1) Full left descent forces finiteness. Suppose $x \in W$ satisfies $D_{L} (x) = S$ , i.e. $ℓ (s x) < ℓ (x)$ for every $s \in S$ . Then:

(i) $ρ (x^{- 1}) Φ_{+} = Φ_{-}$ and $N (x^{- 1}) = Φ_{+}$ ;

(ii) $Φ$ is finite, $∣ Φ_{+} ∣ = ℓ (x) = ∣ T ∣$ , and $W$ is finite;

(iii) $x$ is the longest element $w_{0}$ of $W$ ; equivalently $x$ is the unique element of $W$ with $N (x^{- 1}) = Φ_{+}$ ; and $x^{- 1} = x$ as well as $ℓ (w_{0} w) = ℓ (w_{0}) - ℓ (w)$ for all $w \in W$ .

(2) Parabolic form. Let $J \subseteq S$ , let $W_{J} = ⟨ s : s \in J ⟩$ be the standard parabolic subgroup, $V_{J} = s p a n {e_{s} : s \in J}$ , $Φ_{J} = Φ \cap V_{J} = Φ_{J}^{+} ⊔ Φ_{J}^{-}$ the parabolic root subsystem of Intersections of standard parabolics, the parabolic root subsystem, and global minimality of coset representatives (2), and put $N_{J} (y) : = {α \in Φ_{J}^{+} : ρ (y) α \in Φ_{J}^{-}}$ for $y \in W_{J}$ . If $w \in W_{J}$ satisfies $ℓ (s w) < ℓ (w)$ for every $s \in J$ , then $W_{J}$ is finite, $N_{J} (w^{- 1}) = Φ_{J}^{+}$ , and $w = w_{0} (J)$ is the longest element of the Coxeter system $(W_{J}, J)$ . No Choice is used.

Facts & Assumptions

Given: A finite Coxeter matrix $(S, m)$ with presented group $W$ , length $ℓ$ , canonical reflection homomorphism $ρ : W \to G L (V)$ on $V = R^{S}$ with basis $(e_{s})_{s \in S}$ , signed root system $Φ = Φ_{+} ⊔ Φ_{-}$ , positive cone $V_{+}$ , reflection set $T$ , inversion sets $N (w)$ and descent sets $D_{L}, D_{R}$ as in the cited items; $w, x \in W$ , $J \subseteq S$ and $s \in S$ as specified in each clause.

[F1]

The real Coxeter form, its radical, reflections, and form-preserving maps: $V = R^{S}$ has the basis $(e_{s})_{s \in S}$ , and each $u \in V$ is the finite sum $u = \sum_{s} u (s) e_{s}$ .

[F2]

The canonical reflection homomorphism, roots, reflections, and the positive cone: $ρ$ is a homomorphism with $ρ (s) = r_{e_{s}}$ ; $Φ = {ρ (u) e_{s} : u \in W, s \in S}$ is the root system, so $ρ (v) Φ = Φ$ for every $v \in W$ ; $T = {u s u^{- 1} : u \in W, s \in S}$ ; and $V_{+} = {\sum_{s} λ_{s} e_{s} : λ_{s} \geq 0}$ .

[F3]

Root sign coherence and the action of simple reflections on positive roots (2): $Φ = Φ_{+} ⊔ Φ_{-}$ with $Φ_{+} = Φ \cap V_{+}$ , $Φ_{-} = Φ \cap (- V_{+})$ and $Φ_{-} = - Φ_{+}$ ; every positive root is a nonnegative combination of the $e_{s}$ , and $e_{s} \in Φ_{+}$ for every $s$ .

[F4]

Weak order is a partial order with finite graded intervals; covers and the inversion-set criterion (5): for all $y$ and $s$ , $s \in D_{L} (y) ⟺ e_{s} \in N (y^{- 1}) ⟺ ρ (y^{- 1}) e_{s} \in Φ_{-}$ .

[F5]

The geometric inversion set $N (w)$ of an element of a Coxeter group (1): $N (y) = {α \in Φ_{+} : ρ (y) α \in Φ_{-}}$ .

[F6]

The inversion formula $∣ N (w) ∣ = ℓ (w)$ , the root-reflection dictionary and strong exchange (1)(iv): the map $Φ_{+} \to T$ , $α \mapsto t_{α}$ , is a bijection; (2): $∣ N (y) ∣ = ℓ (y)$ for every $y$ .

[F7]

The root-length criterion and faithfulness of the canonical reflection representation (3): $ρ$ is injective, so $W$ embeds in $S y m (Φ)$ , and for every $y \neq 1$ there is $s$ with $ρ (y) e_{s} \in Φ_{-}$ .

[F8]

Standard parabolic subgroups, descent-free one- and two-sided representatives, parabolic and reflection subgroups: $W_{J} = ⟨ s : s \in J ⟩$ is the standard parabolic subgroup of type $J$ .

[F9]

Intersections of standard parabolics, the parabolic root subsystem, and global minimality of coset representatives (2): $ρ (u) V_{J} = V_{J}$ for $u \in W_{J}$ , $Φ_{J} = Φ \cap V_{J}$ , and $Φ_{J} = Φ_{J}^{+} ⊔ Φ_{J}^{-}$ with $Φ_{J}^{\pm} = Φ_{J} \cap Φ^{\pm}$ .

[F10]

Support, intrinsic parabolic presentations, minimal coset representatives and length additivity, with the type-A identification (2): $(W_{J}, J)$ is a Coxeter system whose intrinsic length function agrees with $ℓ$ on $W_{J}$ .

[F11]

The longest element as the opposition of the chamber, and longest elements of finite parabolics (1)(i)-(iv): if $W$ is finite, there is a unique $w_{0} \in W$ with $N (w_{0}^{- 1}) = Φ_{+}$ ; $ℓ (w_{0}) = ∣ N (w_{0}) ∣ = ∣ Φ_{+} ∣ = ∣ T ∣$ , $ρ (w_{0}) Φ_{+} = Φ_{-}$ , $ℓ (w_{0} w) = ℓ (w_{0}) - ℓ (w)$ for every $w$ , and $w_{0}^{2} = 1$ .

[F12]

The real Coxeter form, its radical, reflections, and form-preserving maps (2): $B (e_{s}, e_{s}) = 1$ for all $s \in S$ .

[F13]

The real Coxeter form, its radical, reflections, and form-preserving maps (3): for $B (a, a) \neq 0$ , $r_{a} (v) = v - \frac{2 B (v, a)}{B (a, a)} a$ .

[F14]

Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups (Universal property): any assignment of the generators of a Coxeter presentation to elements of a group satisfying the Coxeter relators extends uniquely to a group homomorphism.

[F15]

Support, intrinsic parabolic presentations, minimal coset representatives and length additivity, with the type-A identification (3): $ℓ (y) = ℓ (y^{- 1})$ for every $y \in W$ .

[A1]

Consequences of [F1] and [F2] used throughout: $ρ (v)$ is a linear bijection with $ρ (v)^{- 1} = ρ (v^{- 1})$ , and $V_{+}$ is a cone, so a nonnegative combination of elements of $- V_{+}$ lies in $- V_{+}$ , because every coordinate of such a combination is nonpositive; a nonzero element of $Φ_{+}$ stays nonzero under the linear bijection $ρ (v)$ .

Proof

1.1F1F2F3F4A1givenalgebra

Assume $D_{L} (x) = S$ . Then $ρ (x^{- 1}) Φ_{+} = Φ_{-}$ : for every $s \in S$ the hypothesis and [F4] give $ρ (x^{- 1}) e_{s} \in Φ_{-}$ . Every $α \in Φ_{+}$ has the form $α = \sum_{s} λ_{s} e_{s}$ with all $λ_{s} \geq 0$ by [F3], so by linearity of $ρ (x^{- 1})$ the image $ρ (x^{- 1}) α = \sum_{s} λ_{s} ρ (x^{- 1}) e_{s}$ is a nonnegative combination of elements of $Φ_{-} \subseteq - V_{+}$ , hence lies in $- V_{+}$ , and it is nonzero because $ρ (x^{- 1})$ is injective and $α \neq 0$ ; thus $ρ (x^{- 1}) α \in Φ \cap (- V_{+} ∖ {0}) = Φ_{-}$ , giving $ρ (x^{- 1}) Φ_{+} \subseteq Φ_{-}$ . Replacing $α$ by $- α$ shows $ρ (x^{- 1}) Φ_{-} \subseteq Φ_{+}$ , using $Φ_{-} = - Φ_{+}$ and linearity; since $ρ (x^{- 1})$ permutes $Φ$ by [F2], these two inclusions force $ρ (x^{- 1}) Φ_{+} = Φ_{-}$ .

2.1F5step 1.1givenalgebra

Under the hypothesis of step 1.1, $N (x^{- 1}) = Φ_{+}$ : by definition $N (x^{- 1}) = {α \in Φ_{+} : ρ (x^{- 1}) α \in Φ_{-}}$ , and step 1.1 maps all of $Φ_{+}$ into $Φ_{-}$ .

3.1F2F3F6F7F15step 1.1step 2.1givenalgebra

Under the hypothesis of step 1.1, $Φ$ is finite and $∣ Φ_{+} ∣ = ℓ (x) = ∣ T ∣$ , and $W$ is finite. By [F15], $ℓ (x^{- 1}) = ℓ (x)$ , and [F6] gives $∣ N (x^{- 1}) ∣ = ℓ (x^{- 1})$ , so step 2.1 gives $∣ Φ_{+} ∣ = ℓ (x)$ ; as $Φ = Φ_{+} ⊔ Φ_{-}$ with $Φ_{-} = - Φ_{+}$ , the root system $Φ$ is finite, the map $Φ_{+} \to T$ is a bijection, and $ρ$ embeds $W$ into the finite symmetric group $S y m (Φ)$ , so $W$ is finite.

4.1F11step 2.1step 3.1givenalgebra

Under the hypothesis of step 1.1, $x$ is the longest element $w_{0}$ of $W$ , and $x^{- 1} = x$ and $ℓ (w_{0} w) = ℓ (w_{0}) - ℓ (w)$ for all $w$ . Since $W$ is finite by step 3.1, [F11] gives a unique $w_{0}$ with $N (w_{0}^{- 1}) = Φ_{+}$ ; step 2.1 says $N (x^{- 1}) = Φ_{+}$ , so $x = w_{0}$ ; the remaining properties are the listed clauses of [F11] (1).

5.1F1F2F3F4F6F7F8F9F10F12F13F14F15step 1.1step 3.1step 4.1givenalgebra∎

Now let $J \subseteq S$ and let $w \in W_{J}$ satisfy $ℓ (s w) < ℓ (w)$ for every $s \in J$ ; then $W_{J}$ is finite, $N_{J} (w^{- 1}) = Φ_{J}^{+}$ and $w = w_{0} (J)$ . For each $s \in J$ , [F4] turns the hypothesis into $ρ (w^{- 1}) e_{s} \in Φ_{-}$ ; since $ρ (w^{- 1})$ preserves $V_{J}$ by [F9] and $e_{s} \in V_{J}$ , this image lies in $Φ \cap V_{J} \cap Φ_{-} = Φ_{J}^{-}$ , so $ρ (w^{- 1}) e_{s} \in Φ_{J}^{-}$ for every $s \in J$ . Every $α \in Φ_{J}^{+}$ is a nonnegative combination of the $e_{s}$ by [F3]; because $α \in V_{J}$ and the $e_{s}$ form a basis by [F1], its coordinates outside $J$ are zero, so it is a nonnegative combination $\sum_{s \in J} λ_{s} e_{s}$ . Thus the computation of step 1.1, carried out inside the invariant subspace $V_{J}$ and using that $ρ (w^{- 1})$ permutes $Φ_{J}$ (it sends $ρ (u) e_{s}$ to $ρ (w^{- 1} u) e_{s}$ with $w^{- 1} u \in W_{J}$ ), yields $ρ (w^{- 1}) Φ_{J}^{+} = Φ_{J}^{-}$ , that is $N_{J} (w^{- 1}) = Φ_{J}^{+}$ . The pair $(W_{J}, J)$ is a Coxeter system whose intrinsic length is the restriction of $ℓ$ by [F10]. For $s \in J$ and $v \in V_{J}$ , [F2], [F12] and [F13] give $ρ (s) v = r_{e_{s}} (v) = v - 2 B (v, e_{s}) e_{s}$ ; this lies in $V_{J}$ and is the simple reflection for the restricted Coxeter form. Since [F9] makes $V_{J}$ invariant under every $ρ (u)$ with $u \in W_{J}$ , the restriction $ρ ∣_{W_{J}}$ is a homomorphism to $G L (V_{J})$ . It agrees on generators with the canonical reflection representation of $(W_{J}, J)$ ; uniqueness from the presented-group universal property [F14] makes the two representations equal, and their root system is exactly $Φ_{J}$ by the definition in the statement. Applying [F6] inside this subsystem gives $∣ Φ_{J}^{+} ∣ = ∣ N_{J} (w^{- 1}) ∣ = ℓ_{J} (w^{- 1}) = ℓ (w^{- 1}) = ℓ (w)$ , using [F10] for intrinsic length and [F15] for inversion invariance. Since $Φ_{J} = Φ_{J}^{+} ⊔ (- Φ_{J}^{+})$ , the subsystem root set is finite. Its canonical representation is faithful by [F7] applied to the restricted matrix, so $W_{J}$ embeds in $S y m (Φ_{J})$ and is finite. Since $W_{J}$ is finite, clause (1) of this lemma, whose proof consists of steps 1.1, 2.1, 3.1 and 4.1 and applies to any finite Coxeter system, gives on the subsystem a unique element $w_{0} (J)$ with $N_{J} (w_{0} (J)^{- 1}) = Φ_{J}^{+}$ ; since $w$ has this property, $w = w_{0} (J)$ , the longest element of $(W_{J}, J)$ . No Choice was used anywhere in this proof.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (gpt-6.1-sol)audited 2026-10-08Open item page →

Weak order is a meet-semilattice, finite Coxeter groups are lattices, and joins of simple reflections exist exactly for finite parabolics

Statement

Let $(S, m)$ be a finite Coxeter matrix and $W$ the presented group with length $ℓ$ , descent sets $D_{L}, D_{R}$ and weak orders $\leq_{R}, \leq_{L}$ as in The right and left weak orders, intervals, covers, and meets and joins of subsets. Then:

(1) Complete meet-semilattice and bounded joins. In $(W, \leq_{R})$ every nonempty subset has a meet; a nonempty subset has a join if and only if it is bounded above, in which case its join is the meet of its nonempty set of upper bounds. The same statements hold in $(W, \leq_{L})$ .

(2) Finite Coxeter groups are lattices. If $W$ is finite, then $(W, \leq_{R})$ and $(W, \leq_{L})$ are lattices with minimum $1$ and maximum $w_{0}$ ; that is, every subset of $W$ has a meet and a join, and for the empty subset

$⋀ \emptyset = w_{0}, ⋁ \emptyset = 1.$

Moreover $w \leq_{R} w_{0}$ for every $w \in W$ .

(3) Joins of sets of simple reflections. Let $J \subseteq S$ and let $W_{J} = ⟨ s : s \in J ⟩$ be the standard parabolic subgroup. The following are equivalent:

(a) $W_{J}$ is finite;

(b) $J$ has an upper bound in $\leq_{R}$ (equivalently, in $\leq_{L}$ );

If these hold, then $⋁ J = w_{0} (J)$ , the longest element of the finite parabolic $W_{J}$ , in both orders; and every upper bound $w$ of $J$ satisfies $w_{0} (J) \leq_{R} w$ . In particular, if $W_{J}$ is infinite then the set $J$ has no upper bound in either order. For $J = \emptyset$ , these conditions hold and $w_{0} (\emptyset) = 1$ .

(4) The infinite dihedral obstruction. Let $S = {s, t}$ with $s \neq t$ and $m (s, t) = \infty$ , so that $W$ is the infinite dihedral group. Then $s t$ has infinite order and the powers $(s t)^{k}$ ( $k \in Z$ ) are pairwise distinct, so $W_{{s, t}} = W$ is infinite; consequently the set ${s, t}$ has no upper bound in $\leq_{R}$ or $\leq_{L}$ , and its join does not exist in either order. The elements $s$ and $t$ are incomparable in both orders. No completeness or lattice property beyond (1) is claimed for infinite $W$ .

Facts & Assumptions

Given: A finite Coxeter matrix $(S, m)$ with presented group $W$ , length function $ℓ$ , descent sets $D_{L}, D_{R}$ and weak orders $\leq_{R}, \leq_{L}$ as in The right and left weak orders, intervals, covers, and meets and joins of subsets; subsets $A \subseteq W$ , $J \subseteq S$ , and elements $u, w \in W$ and $s, t \in S$ as specified in each clause.

[F1]

The right and left weak orders, intervals, covers, and meets and joins of subsets (1): $u \leq_{R} v$ iff $v = u x$ with $ℓ (v) = ℓ (u) + ℓ (x)$ .

[F2]

Weak order is a partial order with finite graded intervals; covers and the inversion-set criterion (1): both weak orders are partial orders with minimum $1$ , and inversion is an order isomorphism $(W, \leq_{R}) \to (W, \leq_{L})$ .

[F3]

Binary meets, meets of arbitrary nonempty subsets, and joins of bounded subsets in weak order (2): every nonempty subset $A \subseteq W$ has a meet.

[F4]

Binary meets, meets of arbitrary nonempty subsets, and joins of bounded subsets in weak order (3): if a nonempty subset $A \subseteq W$ is bounded above, then $⋁ A = ⋀ U (A)$ ; the analogous statements hold in $\leq_{L}$ by inversion.

[F5]

An element with full left descent makes the Coxeter group finite and is the longest element (2): if $w \in W_{J}$ satisfies $ℓ (s w) < ℓ (w)$ for every $s \in J$ , then $W_{J}$ is finite and $w = w_{0} (J)$ is its longest element.

[F6]

Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups: $ℓ (w)$ is the minimum length of a word in $S$ representing $w$ , so $ℓ (1) = 0$ and $ℓ (x) = 0$ implies $x = 1$ .

[F7]

Support, intrinsic parabolic presentations, minimal coset representatives and length additivity, with the type-A identification (3): every $w \in W$ has a unique factorization $w = u d$ with $u \in W_{J}$ , $d \in^{J} W$ , and $ℓ (v d) = ℓ (v) + ℓ (d)$ for every $v \in W_{J}$ .

[F8]

Support, intrinsic parabolic presentations, minimal coset representatives and length additivity, with the type-A identification (3): $ℓ (y) = ℓ (y^{- 1})$ for every $y \in W$ .

[F9]

Standard parabolic subgroups, descent-free one- and two-sided representatives, parabolic and reflection subgroups (1): $W_{J} = ⟨ s : s \in J ⟩$ is the standard parabolic subgroup.

[F10]

Standard parabolic subgroups, descent-free one- and two-sided representatives, parabolic and reflection subgroups (2): $D_{L} (w) = {s \in S : ℓ (s w) < ℓ (w)}$ .

[F11]

The longest element as the opposition of the chamber, and longest elements of finite parabolics (1)(iii): for finite $W$ , $ℓ (w w_{0}) = ℓ (w_{0}) - ℓ (w)$ for every $w \in W$ .

[F12]

The longest element as the opposition of the chamber, and longest elements of finite parabolics (1)(iv): for finite $W$ , $w_{0}^{2} = 1$ .

[F13]

The longest element as the opposition of the chamber, and longest elements of finite parabolics (2): if $W_{J}$ is finite, then $w_{0} (J)^{2} = 1$ and $ℓ (u w_{0} (J)) = ℓ (w_{0} (J)) - ℓ (u)$ for every $u \in W_{J}$ .

[F14]

The rank-two block computation, exact dihedral orders, the signed reflection action, and ambient reducedness (1): $ℓ (s) = 1$ for every $s \in S$ .

[F15]

The rank-two block computation, exact dihedral orders, the signed reflection action, and ambient reducedness (4): for distinct $s, t \in S$ , one has $s \neq t$ in $W$ and $s t$ has order exactly $m (s, t)$ in $W$ , infinite when $m (s, t) = \infty$ .

[F16]

Lattices, distributive lattices, and order ideals: a lattice is a poset in which every pair has a greatest lower bound and a least upper bound.

[F17]

Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups: the presented group has relator set $R = {s^{2} : s \in S} \cup {(s t)^{m (s, t)} : s, t \in S, m (s, t) < \infty}$ ; when $S = {s, t}$ and $m (s, t) = \infty$ , its presentation is $⟨ s, t ∣ s^{2} = t^{2} = 1 ⟩$ .

[F18]

The right and left weak orders, intervals, covers, and meets and joins of subsets (3): a right join of $A$ is an upper bound of $A$ that lies below every right upper bound of $A$ .

[F19]

Binary meets, meets of arbitrary nonempty subsets, and joins of bounded subsets in weak order (3): no Axiom of Choice is used; its proof makes only finitely many choices in the finite recursion of (2).

[F20]

The right and left weak orders, intervals, covers, and meets and joins of subsets (3): left joins are defined by replacing $\leq_{R}$ with $\leq_{L}$ in the upper-bound and join definitions.

[F21]

The right and left weak orders, intervals, covers, and meets and joins of subsets (1): $u \leq_{L} v$ iff $v = x u$ with $ℓ (v) = ℓ (u) + ℓ (x)$ .

[F22]

The longest element as the opposition of the chamber, and longest elements of finite parabolics (1)(iii): when $W$ is finite, it has a longest element $w_{0}$ , unique among elements of maximum length.

[F23]

The longest element as the opposition of the chamber, and longest elements of finite parabolics (2): when $W_{J}$ is finite, it has a unique longest element $w_{0} (J)$ .

Proof

1.1F2F3F4givenalgebra

Clause (1): the complete meet-semilattice and bounded-join assertions in $\leq_{R}$ are exactly [F3] and [F4]. Inversion is an order isomorphism by [F2], so for every nonempty $A \subseteq W$ it transports meets of $A^{- 1} : = {a^{- 1} : a \in A}$ to meets of $A$ in $\leq_{L}$ , and transports existence and values of joins in the same way. Thus clause (1) holds in both orders.

1.2F1F2F3F4F8F11F12F16F18F20F22givenalgebra

Clause (2): assume $W$ is finite, with longest element $w_{0}$ from [F22]. For every $w \in W$ , applying [F11] to $w^{- 1}$ and using [F8] gives $ℓ (w^{- 1} w_{0}) = ℓ (w_{0}) - ℓ (w^{- 1}) = ℓ (w_{0}) - ℓ (w)$ ; hence $w_{0} = w (w^{- 1} w_{0})$ is length-additive, so $w \leq_{R} w_{0}$ by [F1]. Applying this to $w^{- 1}$ and then using inversion and $w_{0}^{- 1} = w_{0}$ from [F12] shows $w \leq_{L} w_{0}$ as well. Thus $w_{0}$ is a maximum in both orders, and [F2] gives their minimum $1$ . Every nonempty $A \subseteq W$ is bounded above by $w_{0}$ , so [F3] and [F4] give its join and meet in each order. For $A = \emptyset$ , every element is both an upper and a lower bound, so the maximum and minimum give $⋀ \emptyset = w_{0}$ and $⋁ \emptyset = 1$ in both orders by [F18] and [F20]. The two orders are lattices by [F16].

1.3F1F5F7F8F9F10F13F14F17F23givenalgebra

Clause (3), $(a) \Rightarrow (b)$ , and minimality of $w_{0} (J)$ : if $J = \emptyset$ , then $W_{J} = {1}$ and $w_{0} (J) = 1$ , which is an upper bound of $J$ and lies below every $w \in W$ . Now assume $J \neq \emptyset$ and $W_{J}$ is finite, with longest element $w_{0} (J)$ from [F23]. For each $s \in J$ , [F13] and [F14] give $ℓ (s w_{0} (J)) = ℓ ((s w_{0} (J))^{- 1}) = ℓ (w_{0} (J) s) = ℓ (w_{0} (J)) - ℓ (s) = ℓ (w_{0} (J)) - 1$ , using $w_{0} (J)^{2} = 1$ from [F13], $s^{2} = 1$ from [F17], and length invariance under inversion from [F8]. Thus $w_{0} (J) = s (s w_{0} (J))$ is length-additive, so $s \leq_{R} w_{0} (J)$ by [F1] and $w_{0} (J)$ is an upper bound of $J$ . To prove that boundedness forces finiteness and minimality, let $w$ be any upper bound of $J$ , with no finiteness assumption on $W_{J}$ . For each $s \in J$ , [F1] gives $w = s x$ with $ℓ (w) = ℓ (s) + ℓ (x)$ ; [F17] gives $x = s w$ , so [F14] implies $ℓ (s w) = ℓ (w) - 1$ and [F10] gives $s \in D_{L} (w)$ . Factor $w = w_{J} d$ uniquely as in [F7], with $w_{J} \in W_{J}$ , $d \in^{J} W$ , and $ℓ (v d) = ℓ (v) + ℓ (d)$ for every $v \in W_{J}$ . Then $s w_{J} \in W_{J}$ and $ℓ (s w_{J}) + ℓ (d) = ℓ (s w_{J} d) = ℓ (s w) < ℓ (w) = ℓ (w_{J}) + ℓ (d)$ , so $ℓ (s w_{J}) < ℓ (w_{J})$ for every $s \in J$ . By [F5], $W_{J}$ is finite and $w_{J} = w_{0} (J)$ . Hence $w = w_{0} (J) d$ is length-additive, so $w_{0} (J) \leq_{R} w$ by [F1]: it lies below every upper bound of $J$ , and boundedness of $J$ forces $W_{J}$ finite.

2.1F4F18step 1.3givenalgebra

Clause (3) and the join value: if $J = \emptyset$ , then $⋁ J = 1 = w_{0} (J)$ because $1$ is the minimum in both orders, and conditions (a)–(c) all hold. Suppose $J \neq \emptyset$ . If $J$ has an upper bound, step 1.3 gives that $W_{J}$ is finite and that $w_{0} (J)$ is an upper bound below every upper bound. By [F4], the join exists and is the meet of the nonempty set $U (J)$ of upper bounds; therefore $⋁ J = w_{0} (J)$ . Conversely, if $W_{J}$ is finite then step 1.3 supplies an upper bound, and if the join exists then it is itself an upper bound by [F18]. This proves the equivalence and join value in $\leq_{R}$ ; if $W_{J}$ is infinite, the equivalence shows that $J$ has no upper bound and no join.

3.1F2F13F17step 1.1step 2.1givenalgebra

The left-order half of clauses (1) and (3): inversion is an order isomorphism by [F2]. By [F17], each $s \in S$ is an involution, so inversion fixes $J$ pointwise and transports its upper bounds, joins and boundedness in one order to those in the other. By [F13], $w_{0} (J)^{- 1} = w_{0} (J)$ , so the join value in the left order is also $w_{0} (J)$ .

4.1F1F3F6F14F15F17F18F19F20F21step 2.1givenalgebra∎

Clause (4): let $S = {s, t}$ with $s \neq t$ and $m (s, t) = \infty$ . By [F17], the Coxeter presentation here is $⟨ s, t ∣ s^{2} = t^{2} = 1 ⟩$ , the standard infinite dihedral presentation. By [F15], $s t$ has infinite order; if $(s t)^{i} = (s t)^{j}$ for integers $i \neq j$ , then $(s t)^{i - j} = 1$ , a contradiction, so these powers are pairwise distinct and $W$ is infinite. Since $W_{{s, t}} = W$ , clause (3) shows ${s, t}$ has no upper bound in either weak order; consequently it has no join in either order by [F18] and [F20]. To prove incomparability, if $s \leq_{R} t$ then [F1] gives $t = s x$ and $ℓ (t) = ℓ (s) + ℓ (x)$ . Since $ℓ (s) = ℓ (t) = 1$ by [F14], [F6] yields $x = 1$ , contradicting $s \neq t$ ; the same argument with $s, t$ exchanged excludes $t \leq_{R} s$ . For $\leq_{L}$ , [F21] gives the factorizations $t = x s$ or $s = x t$ , and the same length calculation excludes both comparisons. No Axiom of Choice is used: the arbitrary-subset meet assertion is supplied by [F3], and [F19] records that its construction makes only finitely many choices. No completeness or lattice property beyond (1) is claimed for infinite $W$ .

5 · Examples, counterexamples and false statements

None yet.

Weak Order, Inversions, and Lattice Operations

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

The right and left weak orders, intervals, covers, and meets and joins of subsets

Definition

The length identity, the prefix property, left translation, and interval translation for weak order

Statement

Facts & Assumptions

Proof

Weak order is a partial order with finite graded intervals; covers and the inversion-set criterion

Statement

Facts & Assumptions

Proof

Binary meets, meets of arbitrary nonempty subsets, and joins of bounded subsets in weak order

Statement

Facts & Assumptions

Proof

An element with full left descent makes the Coxeter group finite and is the longest element

Statement

Facts & Assumptions

Proof

Weak order is a meet-semilattice, finite Coxeter groups are lattices, and joins of simple reflections exist exactly for finite parabolics

Statement

Facts & Assumptions

Proof

5 · Examples, counterexamples and false statements

Sources