pith. sign in

arxiv: 2606.12129 · v1 · pith:AQ3HFALAnew · submitted 2026-06-10 · 🧮 math.CO

Middle orders: all distributive lattices between weak and Bruhat

Ludovic Schwob This is my paper

Pith reviewed 2026-06-27 09:15 UTC · model grok-4.3

classification 🧮 math.CO
keywords middle ordersweak orderBruhat orderdistributive latticesbinary treesroot posetCoxeter groupsparabolic quotients
0
0 comments X

The pith

In type A, binary trees index all distributive lattices between the weak and Bruhat orders.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines middle orders as distributive lattices that refine the weak order on a Coxeter group while being refined by the Bruhat order. In type A it gives an explicit construction indexed by binary trees: each tree determines a partition of the root poset into rectangles, and permutations correspond to lower sets of that partition. The author proves these lattices are the only distributive ones sitting between weak and Bruhat in type A. For general types the construction yields minuscule middle orders on parabolic quotients, which turn out to be a subset of Armstrong's sorting orders, with conjectures for the remaining cases.

Core claim

Middle orders on the symmetric group are in bijection with binary trees; each tree gives a partition of the root poset into rectangles such that the lower sets of the partition are in bijection with permutations, and the inclusion order on these lower sets is a distributive lattice refining the weak order and refined by the Bruhat order. These are the only such lattices in type A.

What carries the argument

The rectangle partition of the root poset determined by a binary tree, which induces a bijection from permutations to lower sets and thereby equips them with a distributive lattice structure between the weak and Bruhat orders.

If this is right

  • The left-comb binary tree recovers the middle order previously defined by Bouvel, Ferrari, and Tenner.
  • All minuscule middle orders are sorting orders in the sense of Armstrong.
  • The construction extends from type A to other Weyl groups using parabolic quotients.
  • Conjectural descriptions are proposed for non-minuscule middle orders.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The rectangle-partition technique might apply to other poset families on permutations beyond Coxeter groups.
  • One could check whether the number of linear extensions of these lattices admits a closed formula in terms of the binary tree.
  • The uniqueness result in type A suggests that similar classification problems could be posed for other pairs of orders on the same ground set.

Load-bearing premise

The map sending each permutation to the lower set corresponding to its rectangle partition must define a distributive lattice order that sits between the weak and Bruhat orders.

What would settle it

A counterexample would be a distributive lattice on the set of permutations that properly refines the weak order, is properly refined by the Bruhat order, yet is not isomorphic to any of the lattices constructed from binary trees.

Figures

Figures reproduced from arXiv: 2606.12129 by Ludovic Schwob.

Figure 1
Figure 1. Figure 1: On the left: Coxeter diagrams of finite Coxeter groups. On the right: Dynkin diagrams of Weyl groups, with highlighted nodes corresponding to minuscule roots. The inversion set of w ∈ W is N(w) := Φ+ ∩ w(Φ−). N(w) characterizes w and |N(w)| = ℓ(w). Inversion sets are the subsets A ⊂ Φ + that are both closed and coclosed, where A is closed if for all α, β ∈ A, α + β ∈ Φ + implies α + β ∈ A, and A is coclose… view at source ↗
Figure 2
Figure 2. Figure 2: The poset R312546 with its corresponding binary search tree. We will now show that for all T ∈ Tn−1, we have a bijection between Sn and lower sets of RT . Definition 3.3. Let T ∈ Tn−1. For all 1 ≤ k ≤ n−1, let (iT,k, jT,k) := max RT,k. For all w ∈ Sn, let w L,k and w R,k be the subwords of w consisting respectively of values between iT,k and k, and between k + 1 and jT,k. We define IT (w) as the subset of … view at source ↗
Figure 3
Figure 3. Figure 3: From left to right and from top to bottom: the inversion set of the permutation w = 3714625, its right-packing, its left-packing and the lower set IT (w). Theorem 3.6. Let T ∈ Tn−1. IT is a bijection between Sn and lower sets of RT . We define a partial order ≤T on Sn where v ≤T w if and only if IT (v) ⊂ IT (w). Then (Sn, ≤T ) is a distributive lattice. Proof. IT (w) is a lower set of RT , consisting of lo… view at source ↗
Figure 4
Figure 4. Figure 4: The lower set IT (w) with w = 3714625 decomposed into lower sets of RT1 (in red), RT2 (in blue), and RT,k (in green). These encode respectively w L,k = 312, w R,k = 7465, and the shuffle of the two subpermutations. IT (w) differ by one element in RTL (resp. RTR ), then v L,k ⋖ w L,k in (Sk, ≤T1 ) (resp. v R,k ⋖ w R,k in (Sn−k, ≤T2 )). By induction on the size of RT , we obtain the result. □ From the descri… view at source ↗
Figure 5
Figure 5. Figure 5: Equivalence classes of strict Bruhat edges in S4. Proof. The permutation w1 i j k w2 is covered by w1 j i k w2 and w1 i k j w2, which have exactly two common upper covers w1 j k i w2 and w1 k i j w2 in the Bruhat order. Hence, we have either w1 (j i k) w2 ∈ E or w1 (i k j) w2 ∈ E by Proposition 4.1. This relation translates on equivalence classes of edges by Proposition 4.5. □ We now study the implication … view at source ↗
Figure 6
Figure 6. Figure 6: Implications between equivalence classes of strict Bruhat edges in S5, with the left and right edges highlighted. We now show that a middle order is characterized by its left edges, or equivalently by its right edges. Proposition 4.8. Let E be the set of edges of a middle order. For all 1 < i ≤ a < b ≤ j < n, we have h (a, i, j+1, b) ⊂ E i ∧ h (a, i−1, j, b) ⊂ E i =⇒ h (a, i, j, b) ⊂ E i . Proof. Let w2 co… view at source ↗
Figure 7
Figure 7. Figure 7: The poset of equivalence classes of left edges in S5 ordered by implica￾tions and the poset of irreducible elements of GT4. Proposition 4.11. A set of left edges of Sn satisfying equivalence relations ( cf. Proposition 4.5) and implication relations ( cf. Proposition 4.7) satisfies the equation of Proposition 4.9 h (i, 1, k−1, j) ⊂ E i ∧ h (j, 1, ℓ−1, k) ̸⊂ E i ⇐⇒ h (i, 1, ℓ−1, j) ⊂ E i ∧ h (i, 1, ℓ−1, k) … view at source ↗
Figure 8
Figure 8. Figure 8: The lattice GTn−1 with n = 4 with its elements satisfying Equation (4.11) being highlighted, and the corresponding binary trees. Theorem 4.13. Every distributive lattice between the weak and Bruhat orders on Sn is equal to (Sn, ≤T ) for some T ∈ Tn. Proof. Throughout this section, we have described properties that sets of edges must satisfy in order to form a middle order (cf. Propositions 4.5, 4.6, 4.7, 4… view at source ↗
Figure 9
Figure 9. Figure 9: Isomorphic posets corresponding to non-isomorphic binary trees. The subtrees sizes of a binary tree T are the multiset containing the number of internal nodes of each subtree of T, or equivalently m + n − 1 for each rectangular poset of dimensions m × n in RT . If RT1 and RT2 are isomorphic, then the binary trees T1 and T2 have the same subtree sizes. The converse is not true (see [PITH_FULL_IMAGE:figures… view at source ↗
Figure 10
Figure 10. Figure 10: Non-isomorphic posets with their subtree sizes both equal to (10, 5, 4, 3, 2, 2, 1, 1, 1, 1). These observations give us lower and upper bounds for the number of middle orders up to isomorphism [18, A247139], as it is smaller than the number of binary trees up to isomorphism [18, A001190], and larger than the number of binary trees up to their subtrees sizes [18, A382440]. Similarly we can consider binary… view at source ↗
Figure 11
Figure 11. Figure 11: On the left: the weak and Bruhat orders on S4, with a parabolic subgroup WJ and its quotient JW given by J = {(12),(23)}. On the right: A middle order on S4, obtained as the product of middle orders on JW and WJ . Let us focus on the case of the symmetric group. Elements of WJ \Sn can be seen as multiper￾mutations with αk occurrences of k for 1 ≤ k ≤ n − |J|, where α is an integer composition of n such th… view at source ↗
Figure 12
Figure 12. Figure 12: On the right: a middle order on S122 induced by a binary tree U with set of labels {1, 3}. On the left: the posets P122 and RU,5. This construction yields all middle orders on Sα, because if it was not the case, we could construct middle orders on Sn different from those we already know (we will see in Section 7 that all middle orders on Sn are obtained as a product of middle orders on a parabolic subgrou… view at source ↗
Figure 13
Figure 13. Figure 13: The Coxeter diagram of E6, and a partition of its root poset into minuscule posets induced by the permutation s6, s2, s4, s1, s3, s5 We define Rsi1 ,...,sir recursively as the disjoint union of Rsi2 ,...,sir and the minuscule poset Psi1 , with R∅ = ∅. Since a minuscule middle order is the product of distributive lattices whose posets of irreducibles are minuscule posets, we have an isomorphism (W, ≤si1 ,.… view at source ↗
Figure 14
Figure 14. Figure 14: Posets of irreducibles of the 8 middle orders on the Coxeter group B3. The first 4 are isomorphic to minuscule middle orders on Weyl groups B3 or C3 1 , and the last 2 are non-minuscule sorting orders (cf. Section 8) [PITH_FULL_IMAGE:figures/full_fig_p018_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: The sequence of packings corresponding to 132312 (a reduced word for the longest element of WJ ), going from w = 12314324 to Jw = 4324, with W = C4 and J = {s1, s2, s3}. Nonnesting partitions associated to a Weyl group W with root poset Φ+ are defined as the antichains of Φ+, or equivalently as its lower sets. Nonnesting partitions are counted by a gener￾alization of Catalan numbers [1, Section 2.7]: Cat(… view at source ↗
Figure 16
Figure 16. Figure 16: The Coxeter diagram of E6, and a partition of its root poset into minuscule posets R induced by the permutation s6, s2, s4, s1, s3, s5, with the corresponding minuscule heaps. An example of a sorting word giving a sorting order isomorphic to Low(R) is 5|3|13|435143|2435143245|6543214354625431. It is straightforward to show that the definition of the Jω-sorting order does not depend on the choice of ω, tha… view at source ↗
Figure 17
Figure 17. Figure 17: Irreducible posets of middle orders on F4 [PITH_FULL_IMAGE:figures/full_fig_p027_17.png] view at source ↗
Figure 18
Figure 18. Figure 18: Irreducible posets of middle orders on H3 [PITH_FULL_IMAGE:figures/full_fig_p027_18.png] view at source ↗
read the original abstract

For a given Coxeter group, we study distributive lattices called middle orders refining the weak order and refined by the Bruhat order. In type $A$, we construct such lattices indexed by binary trees using a direct bijection between permutations and lower sets of a certain partition of the root poset into rectangles. When the binary tree is a left-comb tree, we recover the middle order defined by Bouvel, Ferrari, and Tenner (2025). We study combinatorial properties of these lattices, and show they are the only distributive lattices between the weak and Bruhat orders in type $A$. For general Coxeter groups, we study middle orders on parabolic quotients and use these to generalize our construction in type $A$ to other Weyl groups, obtaining so-called ``minuscule middle orders''. We show that they are a subset of sorting orders defined by Armstrong (2009), and we give conjectural descriptions of all middle orders that are not minuscule.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper defines middle orders as distributive lattices on Coxeter groups that refine the weak order and are refined by the Bruhat order. In type A, it constructs such lattices indexed by binary trees via an explicit bijection mapping permutations in S_n to lower sets of a partition of the root poset into rectangles (one rectangle per tree). It proves these lattices are distributive and satisfy the sandwich property, recovers the Bouvel-Ferrari-Tenner construction for left-comb trees, establishes that these are all distributive lattices between weak and Bruhat in type A, and studies their combinatorial properties. For general Coxeter groups, it defines minuscule middle orders on parabolic quotients, generalizes the construction to other Weyl groups, proves containment in Armstrong's sorting orders, and offers conjectural descriptions of non-minuscule cases.

Significance. If the constructions and uniqueness hold, the work supplies a complete classification of distributive lattices between weak and Bruhat orders in type A, with an explicit link to binary trees and root-poset geometry. The generalization to minuscule middle orders and their inclusion among sorting orders provides a concrete framework for other types. Explicit bijections, direct combinatorial arguments, and recovery of prior work are notable strengths; the results are parameter-free and rest on standard root-poset structure.

minor comments (3)
  1. [§3] §3 (type A construction): the bijection between permutations and lower sets of the rectangle partition should include a small explicit example (e.g., n=3 or n=4) to illustrate how the induced order refines weak order and is refined by Bruhat order.
  2. [§4] The uniqueness statement in type A would be strengthened by a brief remark confirming that distinct binary trees produce non-isomorphic lattices (or noting when they coincide).
  3. A figure showing the rectangle partition for a non-left-comb binary tree would improve readability of the generalization to minuscule middle orders.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript, recognition of its contributions, and recommendation for minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation chain consists of explicit combinatorial constructions: a direct bijection from permutations to lower sets of a rectangle-partitioned root poset (indexed by binary trees), verification that the induced order refines weak and is refined by Bruhat, and a classification proof that every distributive lattice with the sandwich property arises this way. These steps rest on standard definitions of weak order, Bruhat order, root posets, and Armstrong's sorting orders (external 2009 reference). The minuscule-middle-order generalization is likewise an explicit containment argument. No equations or claims reduce by construction to fitted parameters, self-definitions, or load-bearing self-citations; the manuscript supplies the required direct arguments without circular reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard poset axioms (distributivity, refinement of orders) and the existence of the described bijection and partition, which are domain assumptions in Coxeter combinatorics; no free parameters or invented entities are apparent from the abstract.

axioms (2)
  • domain assumption Weak order and Bruhat order are partial orders on Coxeter groups with the stated refinement relation.
    Invoked in the definition of middle orders as lattices between them.
  • standard math A poset is a distributive lattice when meet and join distribute over each other.
    Core property required for the constructed objects to qualify as middle orders.

pith-pipeline@v0.9.1-grok · 5684 in / 1394 out tokens · 25471 ms · 2026-06-27T09:15:16.080726+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 2 canonical work pages

  1. [1]

    Generalized noncrossing partitions and combinatorics of coxeter groups.Mem

    Drew Armstrong. Generalized noncrossing partitions and combinatorics of coxeter groups.Mem. Amer. Math. Soc., 202(949), 2009

    2009

  2. [2]

    The sorting order on a Coxeter group.Journal of Combinatorial Theory, Series A, 116(8):1285–1305, 2009

    Drew Armstrong. The sorting order on a Coxeter group.Journal of Combinatorial Theory, Series A, 116(8):1285–1305, 2009

    2009

  3. [3]

    On the Glucose SAT solver.International Journal on Artificial Intelli- gence Tools, 27(01):1840001, February 2018

    Gilles Audemard and Laurent Simon. On the Glucose SAT solver.International Journal on Artificial Intelli- gence Tools, 27(01):1840001, February 2018

    2018

  4. [4]

    Coxeter-biCatalan combinatorics.Journal of Algebraic Combinatorics, 47(2):241–300, August 2017

    Emily Barnard and Nathan Reading. Coxeter-biCatalan combinatorics.Journal of Algebraic Combinatorics, 47(2):241–300, August 2017

    2017

  5. [5]

    Rings of sets.Duke Mathematical Journal, 3(3), 1937

    Garrett Birkhoff. Rings of sets.Duke Mathematical Journal, 3(3), 1937

    1937

  6. [6]

    Lattice Theory

    Garrett Birkhoff. Lattice Theory. revised edition.Amer. Math. Soc. Colloq. Publ., 25(2), 1948

    1948

  7. [7]

    Affine permutations of typeA.The Electronic Journal of Combinatorics, 3(2), September 1995

    Anders Bj¨ orner and Francesco Brenti. Affine permutations of typeA.The Electronic Journal of Combinatorics, 3(2), September 1995

    1995

  8. [8]

    Graduate Texts in Mathematics

    Anders Bj¨ orner and Francesco Brenti.Combinatorics of Coxeter Groups. Graduate Texts in Mathematics. Springer, April 2005

    2005

  9. [9]

    Mathilde Bouvel, Luca Ferrari, and Bridget E. Tenner. Between weak and Bruhat: The middle order on permutations.Graphs Comb., 41(2), April 2025

    2025

  10. [10]

    Lattices of pretorsion classes

    Federico Campanini, Francesca Fedele, and Emine Yıldırım. Lattices of pretorsion classes. Preprint, arXiv:2511.19223, 2025

    work page arXiv 2025

  11. [11]

    Mixed dimer models for Euler and Catalan numbers

    Andrew Claussen and Nicholas Ovenhouse. Mixed dimer models for Euler and Catalan numbers. Preprint, arXiv:2503.11936, 2025

    work page arXiv 2025

  12. [12]

    The shape of a typical boxed plane partition

    Henry Cohn, Michael Larsen, and James Propp. The shape of a typical boxed plane partition. 2002

    2002

  13. [13]

    Sur la topologie de certains espaces homog` enes.The Annals of Mathematics, 35(2):396, April 1934

    Charles Ehresmann. Sur la topologie de certains espaces homog` enes.The Annals of Mathematics, 35(2):396, April 1934

    1934

  14. [14]

    Springer Basel, 2011

    George Gr¨ atzer.Lattice Theory: Foundation. Springer Basel, 2011

    2011

  15. [15]

    Novelli, and Jean-Yves Thibon

    Florent Hivert, Jean-Christophe. Novelli, and Jean-Yves Thibon. The algebra of binary search trees.Theoretical Computer Science, 339(1):129–165, 2005. Combinatorics on Words

    2005

  16. [16]

    Treillis et bases des groupes de Coxeter.Electron

    Alain Lascoux and Marcel-Paul Sch¨ utzenberger. Treillis et bases des groupes de Coxeter.Electron. J. Combin., 3(2):Research paper 27, approx. 35, 1996

    1996

  17. [17]

    Macdonald.Symmetric Functions and Hall Polynomials

    Ian G. Macdonald.Symmetric Functions and Hall Polynomials. Oxford University Press, 1979

    1979

  18. [18]

    The On-Line Encyclopedia of Integer Sequences

    OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences. Published electronically athttp: //oeis.org

  19. [19]

    Permutrees.Electronic Notes in Discrete Mathematics, 61:987–993, 2017

    Vincent Pilaud and Viviane Pons. Permutrees.Electronic Notes in Discrete Mathematics, 61:987–993, 2017. The European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB’17)

    2017

  20. [20]

    Quotientopes.Bulletin of the London Mathematical Society, 51(3):406– 420, 2019

    Vincent Pilaud and Francisco Santos. Quotientopes.Bulletin of the London Mathematical Society, 51(3):406– 420, 2019

    2019

  21. [21]

    Robert A. Proctor. Bruhat lattices, plane partition generating functions, and minuscule representations.Eu- ropean Journal of Combinatorics, 5(4):331–350, 1984

    1984

  22. [22]

    Lattice structure for orientations of graphs.The Electronic Journal of Combinatorics, 32(4):P4.26, Nov

    James Propp. Lattice structure for orientations of graphs.The Electronic Journal of Combinatorics, 32(4):P4.26, Nov. 2025

    2025

  23. [23]

    Lattice congruences, fans and Hopf algebras.Journal of Combinatorial Theory, Series A, 110(2):237–273, 2005

    Nathan Reading. Lattice congruences, fans and Hopf algebras.Journal of Combinatorial Theory, Series A, 110(2):237–273, 2005

    2005

  24. [24]

    Cambrian lattices.Advances in Mathematics, 205(2):313–353, 2006

    Nathan Reading. Cambrian lattices.Advances in Mathematics, 205(2):313–353, 2006

    2006

  25. [25]

    Rush and XiaoLin Shi

    David B. Rush and XiaoLin Shi. On orbits of order ideals of minuscule posets.Journal of Algebraic Combina- torics, 37(3):545–569, June 2012

    2012

  26. [26]

    Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics, 2024.https://wiki.sagemath.org/combinat

    The Sage-Combinat community. Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics, 2024.https://wiki.sagemath.org/combinat

    2024

  27. [27]

    Stembridge

    John R. Stembridge. On minuscule representations, plane partitions and involutions in complex Lie groups. Duke Mathematical Journal, 73(2):469 – 490, 1994

    1994

  28. [28]

    Stembridge

    John R. Stembridge. On the fully commutative elements of Coxeter groups.Journal of Algebraic Combinatorics, 5(4):353–385, October 1996

    1996

  29. [29]

    Sagemath, the Sage Mathematics Software System (Version 10.2), 2023

    The Sage Developers. Sagemath, the Sage Mathematics Software System (Version 10.2), 2023. https://www.sagemath.org

    2023

  30. [30]

    "" p = permutation of length n−1 w = permutation of length n Compute the ideal of R T corresponding to w, where T is the binary search tree of p

    Sergei V. Tsaranov. Representation and classification of Coxeter monoids.European Journal of Combinatorics, 11(2):189–204, 1990. MIDDLE ORDERS: ALL DISTRIBUTIVE LATTICES BETWEEN WEAK AND BRUHAT 25 AppendixA. The first function creates clauses in conjunctive normal form (CNF) whose variables are strict Bruhat edges that a set of edges must satisfy in order...

    1990