Rational Catalan numbers for complex reflection groups
Take an irreducible spetsial complex reflection group, and assume the standard conjectures. The canonical symmetrizing trace of its Hecke algebra, evaluated at a power of a Coxeter element is related to the rational Catalan number5:
Cat(W, p) = ∏i p + (p mi mod h)di
Email me if you find any errors or want some specific function added.
The cycle lemma
Read a word of a north and b east steps off a necklace. Of its a+b rotations, exactly one stays above the diagonal1. That one is an (a, b)-Dyck path2. There are Cat(a,b) of them, and that number is also Cat(Sa, b). These are the objects the trace counts, in the case where the group is a symmetric group.
Necklace · rotation
·
Every Dyck path at these parameters
In the general language these are the objects attached to W = Sa at p = b. The twist that the other tabs apply to the exponents does nothing here. Multiplying 1, …, a−1 by a unit mod a only permutes them. That is why the classical formula has no twist in it.
The q-analogue
The same quotient, with every integer replaced by its q-analogue. Divisibility is not obvious. It fails as soon as gcd(a,b) > 1. This polynomial is Catb(Sa; q). The theorem tabs compute the same object from degrees and exponents. Here it is counted off lattice paths.
Catq()
Where the coefficients come from
Each path contributes one power of q3. The exponent is built from two counts. Area is the number of whole cells lying between the path and the diagonal. Dinv is explained below.
Catq(a, b) = ∑D q(a−1)(b−1)/2 + area(D) − dinv(D)
What dinv counts
Dinv counts cells in a partition built from the path. Take the cells lying north-west of the path. Reading their row lengths from the top down gives a partition, written λ(D).
Every cell of λ(D) has an arm and a leg. The arm is the number of cells to its right in the same row. The leg is the number of cells below it in the same column. Both are shown in the corners of each cell below, arm at the top right and leg at the bottom left.
A cell is counted when b/a lands in this half-open interval. Read the right-hand end as ∞ when the leg is 0.
armleg + 1 ≤ ba < arm + 1leg
Click a coefficient to see the paths behind it
The same number without the pictures
Degrees d1 ≤ … ≤ dr = h, exponents mi = di − 1, p coprime to h. The product again, with the exponents twisted by p first.
Cat(W, p) = ∏i p + (p mi mod h)di
Which p give an integer?
Degrees, codegrees and spetsial flags are read from the CHEVIE tables6. Well-generation is re-derived from di + d*r+1−i = h. The twisted product is the catalan function of tracesRegex.py with its normalising factor stripped.
The trace
The canonical symmetrizing trace splits over the irreducible characters.
τp(q) = ∑χ q−p(a+cχ)/h · Fegχ(ζhp)Sχ(q)
Why p stops below h
Write p = p0 + mh with 0 < p0 < h. The twist only ever sees the residue, because p mi ≡ p0mi (mod h). So the numerators are p + (p0mi mod h). One residue determines the whole family m = 0, 1, 2, … . Listing the residues coprime to h therefore loses nothing.
Where the classical numbers are. They sit at the residue p0 = 1. There mi mod h = mi, because mi = di − 1 lies between 1 and h − 1 for a well-generated group. So the twist does nothing, and the product collapses to ∏(mh + 1 + mi)/di. That is the Fuss–Catalan number of W. At m = 1 it is the W-Catalan number ∏(h + 1 + mi)/di. Everything else on this page happens at the other residues, where the twist really does move the exponents.
Where this formula comes from
For a split semisimple symmetric algebra, the canonical symmetrizing trace decomposes over the irreducible characters. There is one term for each, weighted by the inverse of its Schur element. This is Theorem 3.9 of the paper5:
τ = ∑χ 1Sχ χ
Evaluate it at Tc−p. Here c is a braid lift of a ζh-regular element with ch = π, the full twist. Two things come out of the character value. The central element acts by a scalar, which gives the power of q. What is left is the fake degree of χ at ζhp. That is the sum in the table above. Theorem 1.1 of the paper then reads
τq(Tc−p) = q−np(1−q)n Catp(W; q)
for W irreducible spetsial. That prefactor q−np(1−q)n is why the closed form on this page carries one too. It is also why the closed form vanishes at q = 1 while the Catalan number does not.
Why the powers of q are fractions. c is an h-th root of the full twist. Its eigenvalues are therefore h-th roots of the scalars by which π acts. The trace lives on q1/h, not on q. The exponents −p(a+cχ)/h are integers only when h divides a+cχ. The non-spetsial groups have the same problem one level down. Their Schur elements need a root of q as well.
From the paper's traces.gap in GAP3/CHEVIE6. Schur elements are printed as CHEVIE factors them. Φn is the n-th cyclotomic polynomial, and Φ′n, Φ″n are its factors over the field of definition. Fake degrees are in the paper's convention, Fegχ = FegGAPχ* (Remark 2.14). The generic degree is PW/Sχ, so dividing the trace by PW leaves 1/Sχ. That step uses the fact that the Poincaré polynomial is the Schur element of the trivial character, which was checked for every group here. For each spetsial group in the list, the sum was checked against the closed form in exact cyclotomic arithmetic at every p coprime to h. The well-generated groups that are not spetsial are listed too. Their Schur elements are not Laurent polynomials in q, so there is no table to lay out.
The other side of the trace
In this tab, we rewrite the trace sum with the generic degrees evaluated at the root of unity instead of the fake degrees. Almost everything vanishes, and the sum that survives is always the Catalan number. Identifying that sum with the trace is what Lusztig's Fourier transform does in the case that W is spetsial.
Catq(W, p) = 1PW(q) ∑k=0n (−1)k q−p(a+ck)/h · FegΛkVσp(q)
Only the exterior powers of the twist survive, so a sum over all of Irr(W) becomes n+1 terms with alternating signs.
Generic degrees at ζhp
The rational q-Catalan number
What is left of the sum
The Fourier transform lives on unipotent characters. Those exist only for spetsial W, which is CHEVIE's own test for the property. The sum above can be computed for every well-generated group, and it always returns the Catalan number. What fails outside the spetsial case is the step that identifies the sum with the trace. The trace is then a different number. Generic degrees at a root of unity are computed by dividing PW by Sχ as products of cyclotomic polynomials, so the values are exact and no limits are taken6.
How this was computed
Group data. Degrees, codegrees, character tables, Schur elements, fake degrees and unipotent characters come from CHEVIE in GAP36. The distribution is gap3-jm of 7 Jan 2024, with CHEVIE dated 19 Feb 2018. Everything is read from the tables rather than transcribed. Well-generation is re-derived from di + d*r+1−i = h. Spetsial is CHEVIE's own test, whether unipotent characters exist.
The trace. Produced by running the paper's traces.gap unmodified, except for the two lines naming the group and the output file. As a control, the run for G14 reproduces the output.txt shipped in the paper's code byte for byte. Fake degrees are permuted by χ ↦ χ* to match the paper's convention (Remark 2.14). That permutation reproduces the shipped fakeDegrees.txt exactly for all ten groups it covers.
What was checked, and how. Every generic degree Degχ(ζhp) shown here is exact, computed in characteristic zero. The Schur elements are taken in factored form, as a product of cyclotomic polynomials evaluated at monomials. A generic degree at a root of unity is then a limit of a ratio of products of linear atoms c xA − ζ. Both the order of vanishing and the leading coefficient of such a product can be read off atom by atom, so nothing is ever expanded. The two sum identities are tested as exact equalities at q = 2hm, a point where no atom can vanish. The one that divides by a Schur element is tested modulo a prime P ≡ 1 (mod hm), where a nonzero difference proves an inequality. Two independent primes agree in every case.
The result. Take any spetsial group in the list. The trace, the collapsed sum and the closed form agree at every p coprime to h. The generic degrees at ζhp are 0, except for (−1)k on the exterior powers of the twist. For all eight well-generated groups that are not spetsial, property 2 still holds and the collapsed sum still equals the closed form at every p. The trace equals it at none of them.
Type A. The lattice-path side is computed in the page itself, in exact integer arithmetic. The area/dinv identity was checked against the polynomial for all 101 coprime pairs with a+b ≤ 18, which is every pair the controls allow. That is 16,705 paths, and the two agree coefficient by coefficient on all of them.
The data. Everything the page draws is inline in its source as const LEDGER, minus the fields it rebuilds at load rather than ships. The q-exponents, the exterior-power index map, the numerators and the Catalan value are all arithmetic on what is already there, and the per-p rows that repeat are stored once. The full ledger is served as rational-catalan.json, and the GAP3 script that produced it as rational-catalan.gap.sh.
Sources
- The cycle lemma. A. Dvoretzky and Th. Motzkin, A problem of arrangements, Duke Math. J. 14 (1947), 305–313. The free rotation action and the one-Dyck-path-per-orbit count in the first tab.
- Rational Catalan combinatorics. D. Armstrong, B. Rhoades and N. Williams, Rational Catalan combinatorics: the associahedron, FPSAC 2013; arXiv:1305.7286. (a, b)-Dyck paths and the rational Catalan number Cat(a,b).
- The area/dinv statistic. The identity used in the third tab is the t = 1/q specialisation of the rational shuffle conjecture of F. Bergeron, A. Garsia, E. Leven and G. Xin, proved by A. Mellit, Toric braids and (m,n)-parking functions (arXiv:1604.07456). The form used here is a sum over (a,b)-Dyck paths of q(a−1)(b−1)/2 + area − dinv. It is stated that way, with dinv written via the sweep map, in D. Armstrong, Lattice points and rational q-Catalan numbers (arXiv:2403.06318, §5). The equality was checked against the polynomial for every coprime pair the controls allow, rather than assumed.
- Rational noncrossing objects. P. Galashin, T. Lam, M. Trinh and N. Williams, Rational noncrossing Coxeter–Catalan combinatorics, Proc. London Math. Soc. (2024); arXiv:2208.00121. The finite Coxeter case that the paper extends to spetsial complex reflection groups.
- The paper. W. Miller, Rational Catalan numbers for complex reflection groups, J. Algebra 435 (2025); doi:10.1016/j.jalgebra.2025.01.027, arXiv:2310.12354. The trace ledger and the twisted product come from here. The fake-degree convention is Remark 2.14.
- The computer algebra. J. Michel, The development version of the CHEVIE package of GAP3, J. Algebra 435 (2015), 308–336. Degrees, codegrees, Schur elements, fake degrees and character tables in the last two tabs are read from CHEVIE, via the paper's own traces.gap.
Companion to Rational Catalan numbers for complex reflection groups. Everything shown is computed in the page or read from the paper's own GAP3 output.