Noncrossing Partition Lattices and Kreweras Complements

Let $(W,S)$ be a Coxeter system with $S$ finite, Coxeter diagram $\mathrm{\Gamma }$, word length $\mathrm{\ell }$, and presented group $W$ (Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups, Coxeter diagrams: edges, labels, components and finite type). Let $V={\mathbb{R}}^S$ have its Coxeter form $B$ and canonical reflection homomorphism $\rho :W\to \mathrm{G}\mathrm{L}(V)$; its reflection set is $T=\{ws{w}^{-1}:w\in W,s\in S\}$ (The real Coxeter form, its radical, reflections, and form-preserving maps, The canonical reflection homomorphism, roots, reflections, and the positive cone). Extend the finite-type formulas of Reflection length, the absolute order on a finite Coxeter group, and the moved and fixed spaces of an orthogonal operator (1),(2) to this possibly infinite group by defining ${\mathrm{\ell }}_T(w):=\min \{k\in \mathbb{N}:w=t_1\cdots t_k,t_i\in T\},u{\le }_{T}v⟺{\mathrm{\ell }}_T(v)={\mathrm{\ell }}_T(u)+{\mathrm{\ell }}_T(u^{-1}v)\mathrm{.}$ The minimum exists because $S\subseteq T$ generates $W$; the empty product is $1$.

(1) Coxeter elements. Put $n=\mathrm{\mid }S\mathrm{\mid }$ and choose a bijection $\sigma :\{1,\dots ,n\}\to S$. The product $c_{\sigma }=\sigma (1)\cdots \sigma (n)$ is the Coxeter element for that ordering; a Coxeter element of $(W,S)$ is any such product, with each simple reflection used exactly once. For $n=0$ the unique empty ordering has empty product $1$; for $n=1$ the product is the sole simple reflection. If $\mathrm{\Gamma }$ is connected and $W$ is of finite type, the bipartite construction of The bipartite Coxeter element, its ordered prefix roots, and the conditional vector map mu(a) = -2(c-1)^{-1}a (1) gives one particular Coxeter element. This definition makes no claim that distinct orderings give conjugate elements.

(2) The noncrossing interval. For an irreducible system and a Coxeter element $c$, define $\mathrm{NC}(W,c):=[1,c{]}_{{\le }_T}=\{w\in W:1{\le }_{T}w{\le }_{T}c\},$ with the order induced by ${\le }_T$. Since $T$ generates $W$, ${\mathrm{\ell }}_T$ is a word length: it is subadditive, vanishes only at $1$, and ${\mathrm{\ell }}_T(1)=0$. Thus $u{\le }_{T}u$; if $u{\le }_{T}v$ and $v{\le }_{T}u$, adding the two defining equalities gives ${\mathrm{\ell }}_T(u^{-1}v)={\mathrm{\ell }}_T(v^{-1}u)=0$, so $u=v$. If $u{\le }_{T}v{\le }_{T}w$, subadditivity gives ${\mathrm{\ell }}_T(w)\le {\mathrm{\ell }}_T(u)+{\mathrm{\ell }}_T(u^{-1}w)\le {\mathrm{\ell }}_T(u)+{\mathrm{\ell }}_T(u^{-1}v)+{\mathrm{\ell }}_T(v^{-1}w)={\mathrm{\ell }}_T(w),$ so equality holds throughout and $u{\le }_{T}w$. Hence ${\le }_T$ is a partial order, and $1$ is the least element of the interval. The chosen $c$ is part of the definition; independence up to isomorphism for finite type is proved in Finite noncrossing intervals are lattices, independently of the Coxeter element ↗ (4), not assumed here.

(3) Reducible systems. If the connected components of $\mathrm{\Gamma }$ have vertex sets $S_1,\dots ,S_k$, then $W\cong W_{S_1}\times \cdots \times W_{S_k}$ by Disconnected diagrams, direct products, and comparison of invariant forms (1), where $W_{S_i}=⟨S_i⟩$ (The subgroup $⟨S⟩$ generated by a subset, the cyclic subgroup $⟨g⟩$, and cyclic groups). A Coxeter element $c$ has coordinates $c_i$, each a Coxeter element for $(W_{S_i},S_i)$. Define $\mathrm{NC}(W,c):={\prod }_{i=1}^k\mathrm{NC}(W_{S_i},c_i)$ with componentwise order; for $k=0$ this is the one-element empty product. This agrees with the ambient interval $[1,c{]}_{{\le }_T}$: conjugates of a simple generator stay in its component, so $T$ is the disjoint union of the component reflection sets $T_i$ in their respective factors. Any reflection factorization of $(w_i)$ projects to one in each factor, giving ${\mathrm{\ell }}_T((w_i))\ge {\sum }_i{\mathrm{\ell }}_{T_i}(w_i)$; concatenating shortest factorizations in the factors gives the reverse inequality. Hence reflection length is the sum of the component lengths, and the absolute-order relation is componentwise. For $k=0$, $W=\{1\}$ and both the interval and product are singletons.

(4) The Kreweras map. Define $K:\mathrm{NC}(W,c)\to W,K(w):=w^{-1}c\mathrm{.}$ This is well-defined as a map to $W$ by the group operations. It is not defined here as a map into $\mathrm{NC}(W,c)$, and no bijectivity or order-reversal is asserted; those properties are proved in The Kreweras complement of [1,c], and the type-A model by noncrossing set partitions ↗ (1).

(5) Abstentions. This definition asserts no finiteness, lattice property, conjugacy of Coxeter elements, independence from $c$, or Kreweras-complement property beyond the definitions above. In the reducible case the product definition in (3) is justified locally as the ambient absolute interval; the lattice theorem remains a separate finite-type result. No form of the Axiom of Choice is used.

• The set of Coxeter elements need not be a union of $W$-conjugacy classes. Take the presentation with generators $s_1,s_2,s_3$ and only the relations $s_i^2=1$ (the free product $C_2\ast C_2\ast C_2$). On the set $X$ of words with no equal adjacent letters, let $s_i$ delete the first letter when it is $s_i$, and otherwise prepend $s_i$. Each operation is an involution in the permutation group $\mathrm{Sym}(X)$ (The symmetric group $\mathrm{Sym}(X)$: the bijections of a set $X$ under composition, $\mathrm{Sym}(X)$ is a group under composition, and it is non-abelian whenever $X$ has at least three distinct elements), so the presentation's universal property gives a homomorphism to that group. A word with no equal adjacent letters sends the empty word to its own letter string, whereas a product of $k$ generators sends it to a string of length at most $k$. Therefore $s_2{s}_1{s}_2{s}_3{s}_2$ has word length five. It equals $s_2(s_1{s}_2{s}_3)s_2$, but cannot be a once-each product of three generators.

Let $(V,⟨\cdot ,\cdot ⟩)$ be a finite-dimensional real inner-product space, let $k\ge 0$, and let ${\sigma }_1,\dots ,{\sigma }_k\in V$ be linearly independent unit vectors (Real and complex inner-product spaces and their induced length, Linear independence: a finite list $v:n\to V$ is independent when ${\sum }_{i<n}{\lambda }_i{v}_i=0_V$ forces every ${\lambda }_i=0_F$, and a subset $S\subseteq V$ is independent when every injective finite list into $S$ is independent, For a subspace $W$ of a finite-dimensional inner product space, $V=W\oplus W^{\perp }$). For a unit vector $v$ define the orthogonal reflection $R(v)x:=x-2⟨x,v⟩v\mathrm{.}$ For a linear map $A:V\to V$ write $M(A):=\mathrm{im}(A-{\mathrm{i}\mathrm{d}}_V)$ (Linear map between vector spaces over the same field, Kernel and image of a linear map). Then:

(1) The moved space. $M(R({\sigma }_k)R({\sigma }_{k-1})\cdots R({\sigma }_1))=\mathrm{span}({\sigma }_1,\dots ,{\sigma }_k),$ and its dimension is $k$. When $k=0$, the product is the identity, the span of the empty set is $\{0\}$, and the moved space is $\{0\}$.

(2) Reflection length. For a finite-type Coxeter system, specialize the inner-product space of (1) to $V={\mathbb{R}}^S$ with Coxeter form $B$ (The real Coxeter form, its radical, reflections, and form-preserving maps); this is positive definite by Finiteness criterion: W is finite exactly when the Coxeter form is positive definite. Let $\rho$ be the canonical reflection homomorphism and $T$ the reflection set (The canonical reflection homomorphism, roots, reflections, and the positive cone, Reflection length, the absolute order on a finite Coxeter group, and the moved and fixed spaces of an orthogonal operator). If ${\sigma }_1,\dots ,{\sigma }_k$ are roots, choose any $r_i\in T$ with $\rho (r_i)=R({\sigma }_i)$; such reflections exist by Descent of the reflection representation, unit root norms, and conjugation of reflections (3),(4). Then ${\mathrm{\ell }}_T(r_k{r}_{k-1}\cdots r_1)=\dim M(R({\sigma }_k)\cdots R({\sigma }_1))=k\mathrm{.}$ The product order is the reverse of the root list, as in The Brady-Watt ordered root complex X(c), its subcomplexes X(sigma) and X(sigma,rho), and their positive-cone realizations (1),(2): the reflection with normal ${\sigma }_1$ acts first on vectors when applying the product.

(3) Limits. Clause (1) needs only linear independence and unit norms; the normals need not lie in a common open half-space and no Coxeter complex is needed. Clause (2) uses finite type so that the Coxeter form is a positive definite inner product. No crystallographic assumption or Choice is used.

Let $(W,S)$ be an irreducible finite-type Coxeter system, and let $c$ be the bipartite Coxeter element with positive-root order, ordered root complex $X(c)$, cones $c[F]$, $c[Y]$, and realizations $\mathrm{\mid }Y\mathrm{\mid }=c[Y]\cap S^{n-1}\subset V={\mathbb{R}}^S$ of The Brady-Watt ordered root complex X(c), its subcomplexes X(sigma) and X(sigma,rho), and their positive-cone realizations (1)–(3), The Coxeter plane, ordered-root enumeration, and invertibility of rho(c) - id (3), and Real and complex inner-product spaces and their induced length. The vertices of every face are linearly independent unit positive roots, all in a common open half-space (The factorization criterion, linear independence of the faces, and the geometric simplicial structure of X(sigma) (2)); all spans are taken in $V$ (Linear subspace of a vector space). Set $c[\mathrm{\varnothing }]=\{0\}$, and let $Y,Z$ be subcomplexes of $X(c)$ (An abstract simplicial complex, The geometric realization of an abstract simplicial complex). Then:

(1) Realization of an intersection. If $Y\cap Z$ is the subcomplex consisting of simplices common to both, then $c[Y\cap Z]=c[Y]\cap c[Z],\mathrm{\mid }Y\cap Z\mathrm{\mid }=\mathrm{\mid }Y\mathrm{\mid }\cap \mathrm{\mid }Z\mathrm{\mid }\mathrm{.}$ If $Y$ and $Z$ have no common vertex, this reads $c[Y]\cap c[Z]=\{0\}$ and $\mathrm{\mid }Y\cap Z\mathrm{\mid }=\mathrm{\varnothing }$.

(2) Purity under convexity. Suppose $Y\cap Z$ has at least one vertex. Put $C=c[Y]\cap c[Z]$ and $K=\mathrm{\mid }Y\mathrm{\mid }\cap \mathrm{\mid }Z\mathrm{\mid }$. If $C$ is convex, then every maximal simplex $F$ of $Y\cap Z$ satisfies $\mathrm{span}(F)=\mathrm{span}(C)\mathrm{.}$ Under the common-open-half-space condition above, convexity of $C$ is equivalent to geodesic convexity of $K$: for any two points of $K$, the shorter great-circle arc between them lies in $K$. Consequently all maximal simplices have dimension $\dim \mathrm{span}(C)-1$, so $Y\cap Z$ is pure (all maximal simplices have the same dimension).

(3) Small cases. If $Y\cap Z$ consists of one vertex $v$, its unique maximal simplex is $\{v\}$ and its span is $\mathrm{span}(C)=\mathrm{span}(v)$. If $Y\cap Z$ has no vertex, then $c[Y\cap Z]=\{0\}$, $\mathrm{\mid }Y\cap Z\mathrm{\mid }=\mathrm{\varnothing }$, and (2) is vacuous.

(4) Limits. The result does not identify $\mathrm{span}(c[Y]\cap c[Z])$ with $\mathrm{span}(c[Y])\cap \mathrm{span}(c[Z])$. In particular, it does not determine $M(\alpha )\cap M(\beta )$ for $Y=X(\alpha )$ and $Z=X(\beta )$. No Choice is used.

Let $(W,S)$ be a Coxeter system with $S$ finite, $\mathrm{\mid }S\mathrm{\mid }=n$, Coxeter diagram $\mathrm{\Gamma }$, and Coxeter elements $c,c^{\mathrm{\prime }}$ defined as once-each products (Coxeter diagrams: edges, labels, components and finite type, Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups, Coxeter elements, the noncrossing interval [1,c], and the Kreweras map w ↦ w⁻¹c (1)). Suppose $W$ is of finite type. Then every connected component of $\mathrm{\Gamma }$ is a tree: finiteness of $W$ makes the Coxeter form $B$ positive definite, and its restriction to each component is positive definite (Finiteness criterion: W is finite exactly when the Coxeter form is positive definite (1)); the positive-definite diagram exclusions show each component has no cycle (Exclusions for positive definite diagrams: trees, valency, labels, chains and arms (2)); hence each nonempty connected component is a tree (Trees, forests, leaves and isolated vertices).

(1) Orientation moves on a tree. Let $T$ be a finite tree. A source in an orientation is a vertex whose incident arrows all point away from it; a sink is one whose incident arrows all point towards it. Firing a source or sink reverses all its incident arrows. Every orientation of $T$ is acyclic, and any two orientations are connected by a finite sequence of firings.

(2) Orderings and orientations. An ordering of $S$ orients each edge $\{s,t\}$ of $\mathrm{\Gamma }$ from its earlier vertex to its later vertex. This orientation is acyclic, and every acyclic orientation is obtained from some ordering. Its product is independent of the chosen ordering that realizes the orientation, so an acyclic orientation determines a Coxeter element. If a source or sink $s$ is fired, the new Coxeter element is $scs=sc{s}^{-1}$.

(3) Conjugacy. If every connected component of $\mathrm{\Gamma }$ is a tree, then any two Coxeter elements are conjugate by a product of simple reflections. In particular this holds in finite type, since then every connected component is a tree. If $S=\mathrm{\varnothing }$, then $W=\{1\}$ and the unique Coxeter element is conjugate to itself.

(4) Limits. Finite type is sufficient, not necessary, for the conjugacy assertion: its proof only needs each component to be a tree. No conjugacy claim is made for diagrams with cycles. No finite classification or geometric realization is used, and no Choice is needed.

Let $(W,S)$ be a Coxeter system of finite type with $S$ finite, reflection set $T$, reflection length ${\mathrm{\ell }}_T$, absolute order ${\le }_T$, and noncrossing interval $\mathrm{NC}(W,c)=[1,c{]}_{{\le }_T}$ (The real Coxeter form, its radical, reflections, and form-preserving maps, The canonical reflection homomorphism, roots, reflections, and the positive cone, Reflection length, the absolute order on a finite Coxeter group, and the moved and fixed spaces of an orthogonal operator, Carter's reflection-length formula, the absolute order on a finite Coxeter group, and moved-space rigidity under a common upper bound, Coxeter elements, the noncrossing interval [1,c], and the Kreweras map w ↦ w⁻¹c (2)). For a connected system, denote by $\gamma$ the designated bipartite Coxeter element and use its ordered root complex $X(\gamma )$, subcomplexes $X(\sigma )$, and root sets $P_{\sigma }=\{\alpha \in {\mathrm{\Phi }}_{+}:t_{\alpha }{\le }_T\sigma \}$ (The Brady-Watt ordered root complex X(c), its subcomplexes X(sigma) and X(sigma,rho), and their positive-cone realizations, The mu-dot-root identities, the cone separation, and the canonical simple systems of the subintervals [1, sigma] (4), The bipartite Coxeter element, its ordered prefix roots, and the conditional vector map mu(a) = -2(c-1)^{-1}a (1)). Then:

(1) Binary meets in the bipartite interval. For all $a,b\in [1,\gamma ]$, their common lower bounds have a greatest element $a\wedge b$. If $a=1$, $b=1$, or $P_a\cap P_b=\mathrm{\varnothing }$, then $a\wedge b=1$. In the last case, $X(a)\cap X(b)$ has no vertices (though it contains the empty face), and its realization is empty. This case occurs in rank two: for the Coxeter system $m(s,t)=3$, take $\gamma =st$, $a=s$, $b=t$; then $a,b{\le }_T\gamma$ and their distinct singleton root sets are disjoint.

Otherwise choose a maximal simplex $F=\{v_1<\cdots <v_r\}$ of $X(a)\cap X(b)$ and put $\sigma :=R(v_r)R(v_{r-1})\cdots R(v_1)\mathrm{.}$ Then $\sigma {\le }_T\gamma$, $M(\sigma )=\mathrm{span}(F)=\mathrm{span}(\mathrm{\mid }X(a)\mathrm{\mid }\cap \mathrm{\mid }X(b)\mathrm{\mid })$, and $\sigma =a\wedge b$. In every case, $M(a\wedge b)=\mathrm{span}(\mathrm{\mid }X(a)\mathrm{\mid }\cap \mathrm{\mid }X(b)\mathrm{\mid }),P_{a\wedge b}=P_a\cap P_b,$ where $\mathrm{span}(\mathrm{\varnothing })=\{0\}$.

(2) Joins and the lattice property. The common upper bounds of any $a,b\in [1,\gamma ]$ form a nonempty finite set and have a least element $a\vee b$. Thus $[1,\gamma ]$ is a finite lattice with least element $1$ and greatest element $\gamma$ (Lattices, distributive lattices, and order ideals). The meet of any nonempty finite subset is obtained by iterating the binary meet of (1).

(3) Reducible systems. If the connected components of $\mathrm{\Gamma }$ have vertex sets $S_1,\dots ,S_k$, write $W=W_{S_1}\times \cdots \times W_{S_k}$ and $c=(c_1,\dots ,c_k)$ under the component decomposition (Coxeter diagrams: edges, labels, components and finite type, Disconnected diagrams, direct products, and comparison of invariant forms, Coxeter elements, the noncrossing interval [1,c], and the Kreweras map w ↦ w⁻¹c (3)); each $c_i$ is a Coxeter element of $W_{S_i}$. Let $T_i$ be the reflection set of $(W_{S_i},S_i)$. Then $[1,c{]}_{{\le }_T}={\prod }_{i=1}^k[1,c_i{]}_{{\le }_{T_i}}={\prod }_{i=1}^k\mathrm{NC}(W_{S_i},c_i)$ as posets, where $T_i$ is the reflection set of $(W_{S_i},S_i)$ and each factor uses its own absolute order. The empty product when $S=\mathrm{\varnothing }$ is a singleton. Consequently every finite-type noncrossing interval is a finite lattice.

(4) Independence of the Coxeter element. Any two Coxeter elements $c,c^{\mathrm{\prime }}$ of a finite-type $W$ are conjugate: choose $w\in W$ with $c^{\mathrm{\prime }}=wc{w}^{-1}$ (Coxeter elements of tree type are conjugate by source and sink firings (3)). Then ${\mathrm{Ad}}_w:[1,c{]}_{{\le }_T}⟶[1,c^{\mathrm{\prime }}{]}_{{\le }_T},x⟼wx{w}^{-1},$ is a lattice isomorphism. It preserves reflection length and satisfies $M(wx{w}^{-1})=\rho (w)M(x)$; hence the isomorphism type of $\mathrm{NC}(W,c)$ is independent of $c$.

(5) Limits. No assertion is made about whether the whole absolute order $\mathrm{Abs}(W)$ is a lattice, about intervals $[1,w]$ when $w$ is not a Coxeter element, or about non-finite types. No finite classification, crystallographic hypothesis, or Axiom of Choice is used; the finite noncrystallographic types are included.