Alexandersson's Fuss–Catalan conjecture

What Lean checks

Lean proves the literal Fuss–Dyck enumeration and closed formula, real-rootedness, the exact simple-negative-root count, and scalar reduction to the ordinary case. It proves that any ordinary-case relation between root multisets transfers; the cited ordinary-case interlacing theorems themselves are not re-proved. Strict standalone compilation, all-owned axiom audit and isolated stock-kernel replay passed; the combined repository gate is pending.

Proved as a short deduction from classical results. The exact refinement comes from classical Kreweras/cycle-lemma enumeration, and its real-rooted binomial polynomial is already known from Bóna et al. and Wang–Zhang. The contribution recorded here is the positive scalar reduction for every Fuss parameter. The proof has been independently reviewed. Priority is qualified as described in NOVELTY.md; no claim of a new root-preserving method is made.

The theorem

For integers m,n≥1m,n\geq1, let 𝒟n(m)\mathcal D_n^{(m)} be the north-east lattice paths from (0,0)(0,0) to (mn,n)(mn,n) staying weakly above y=x/my=x/m. For 1≤k≤n1\leq k\leq n, define

Wn,k(m)(t)=∑π∈𝒟n(m)#NE(π)=kt#NNE(π).W_{n,k}^{(m)}(t) =\sum_{\substack{\pi\in\mathcal D_n^{(m)}\\ \#NE(\pi)=k}} t^{\#NNE(\pi)}.

Occurrences are contiguous factors in the step word. The conjecture attributed to P. Alexandersson (2023) is that every Wn,k(m)W_{n,k}^{(m)} is real-rooted.

For n>kn>k we prove the exact formula

Wn,k(m)(t)=1mn+1(mn+1k)∑i=1min(k,n−k)(ki)(n−k−1i−1)ti.W_{n,k}^{(m)}(t) =\frac1{mn+1}\binom{mn+1}{k} \sum_{i=1}^{\min(k,n-k)} \binom ki\binom{n-k-1}{i-1}t^i. \tag{1}

For n=kn=k,

Wn,n(m)(t)=1mn+1(mn+1n).W_{n,n}^{(m)}(t)=\frac1{mn+1}\binom{mn+1}{n}. \tag{2}

Consequently, the nonconstant polynomials have a simple zero at zero and exactly min(k−1,n−k−1)\min(k-1,n-k-1) simple negative zeros. In particular, the conjecture holds for every parameter choice.

The empty-path case, if included, is W0,0(m)=1W_{0,0}^{(m)}=1. Values with kk outside 1,…,n1,\ldots,n are zero enumerators and need no nonzero-polynomial convention in the stated theorem.

1. Counting north runs by cyclic rotation

Put L=mn+1L=mn+1. Append one east step to an mm-Dyck path. Split the resulting word into its LL blocks

Na1ENa2E⋯NaLE,aj≥0,∑j=1Laj=n.N^{a_1}E\,N^{a_2}E\,\cdots\,N^{a_L}E, \qquad a_j\geq0,\qquad \sum_{j=1}^L a_j=n.

Use height m(#N)−(#E)m\,(\#N)-(\#E). The block increments are

bj=maj−1≥−1,∑j=1Lbj=−1.b_j=ma_j-1\geq-1,\qquad \sum_{j=1}^L b_j=-1.

A block sequence is called good if its proper prefix sums are nonnegative. The appended path gives a good sequence. Conversely, the last increment of any good sequence must equal −1-1: its final sum is −1-1, its penultimate sum is nonnegative, and every increment is at least −1-1. Thus its last block has aL=0a_L=0, and the penultimate sum is zero. Deleting that final east step gives an mm-Dyck path. Within a block the north steps only increase height, so checking block endpoints suffices.

For completeness, the required cycle lemma is elementary in this setting. For any integer sequence b1,…,bLb_1,\ldots,b_L with total −1-1, set s0=0s_0=0 and sj=b1+⋯+bjs_j=b_1+\cdots+b_j. Among s0,…,sL−1s_0,\ldots,s_{L-1}, let sqs_q be the first occurrence of the minimum. The rotation beginning with bq+1b_{q+1} has nonnegative proper prefix sums. Prefixes before wrapping are nonnegative by minimality. After wrapping, a proper prefix has value −1−sq+sr-1-s_q+s_r with r<qr<q, which is nonnegative since sr>sqs_r>s_q and the sums are integers. If q>0q>0, the prefix reaching the original final index has value −1−sq≥0-1-s_q\geq0 because then sq≤−1s_q\leq-1.

Conversely, a good rotation beginning after index qq forces sr≥sqs_r\geq s_q for q<r<Lq<r<L, and sr>sqs_r>s_q for r<qr<q. Therefore qq is exactly that first minimum. There is one good rotation.

No orbit here can have fewer than LL distinct rotations. A period of length d<Ld<L would express the total sum as (L/d)(L/d) times an integer, contradicting total sum −1-1. Hence a rotation-invariant collection of these sequences has exactly one good sequence per LL elements.

Every positive aja_j is one maximal north run, hence contributes one NENE factor. Every aj≥2a_j\geq2 contributes exactly one NNENNE factor. Fix kk positive slots and ii slots of size at least two. For n>kn>k:

  1. choose the positive slots in (Lk)\binom Lk ways;
  2. choose which ii receive excess above one in (ki)\binom ki ways;
  3. distribute total excess n−kn-k positively among those ii slots in (n−k−1i−1)\binom{n-k-1}{i-1} ways.

This set is rotation invariant. Dividing by LL proves (1). If n=kn=k, every positive slot equals one; there are (Ln)\binom Ln tuples and no NNENNE factors. Division by LL proves (2).

2. The real-zero argument

For n>kn>k, write a=k−1a=k-1, b=n−k−1b=n-k-1, d=min(a,b)d=\min(a,b) and e=max(a,b)e=\max(a,b). Both d,ed,e are nonnegative integers. The polynomial in the sum in (1) equals

ktHd,e(t),Hd,e(t)=∑j=0d(dj)(ej)j+1tj.k t H_{d,e}(t),\qquad H_{d,e}(t)=\sum_{j=0}^{d} \frac{\binom dj\binom ej}{j+1}t^j. \tag{3}

If d=0d=0, this is ktkt and the claim is immediate. Suppose d≥1d\geq1. Define

R(y)=yd+1(1−y)e.R(y)=y^{d+1}(1-y)^e.

Repeated Rolle's theorem shows that R(d)(y)R^{(d)}(y) has precisely dd simple zeros in (0,1)(0,1), a zero of multiplicity one at zero, and a zero of multiplicity e−de-d at one. Here is the degree count that rules out missing or repeated interior zeros. After rr derivatives, 0≤r≤d0\leq r\leq d, the endpoint multiplicities are d+1−rd+1-r and e−re-r. Inductively, Rolle supplies rr distinct interior zeros, one in each gap created by the preceding derivative's interior zeros and the endpoints. These zeros and endpoint multiplicities total d+e+1−rd+e+1-r, the full degree. Thus there are no others, and the interior zeros are simple.

Leibniz's rule gives the polynomial identity

Q(y):=R(d)(y)(d+1)!y(1−y)e−d=∑j=0d(dj)(ej)j+1(−y)j(1−y)d−j=(1−y)dHd,e(yy−1).\begin{aligned} Q(y) &:=\frac{R^{(d)}(y)} {(d+1)!\,y(1-y)^{e-d}}\\ &=\sum_{j=0}^d \frac{\binom dj\binom ej}{j+1} (-y)^j(1-y)^{d-j}\\ &=(1-y)^d H_{d,e}\!\left(\frac{y}{y-1}\right). \end{aligned} \tag{4}

The quotient in the first line is a polynomial because of the endpoint multiplicities. It has exactly dd simple zeros in (0,1)(0,1). The map y↦y/(y−1)y\mapsto y/(y-1) is a bijection from (0,1)(0,1) onto (−∞,0)(-\infty,0). Equation (4), together with degHd,e=d\deg H_{d,e}=d, therefore proves that every zero of Hd,eH_{d,e} is simple and negative. Its constant term is one, so multiplying by tt adds a distinct simple zero at zero. The prefactor in (1) is positive. This proves the theorem.

3. Relation to the ordinary-Dyck results

Equation (1), including the constant boundary (2), gives the stronger scalar identity

Wn,k(m)(t)=(n+1)(mn+1k)(mn+1)(n+1k)Wn,k(1)(t).W_{n,k}^{(m)}(t) =\frac{(n+1)\binom{mn+1}{k}} {(mn+1)\binom{n+1}{k}}\, W_{n,k}^{(1)}(t). \tag{5}

Thus, for fixed n,kn,k, the zeros do not depend on mm at all. The real-rootedness theorem for m=1m=1 already appears in Bóna et al.; the consecutive and rowwise interlacing statements for that case are proved by Wang–Zhang. Formula (5) transfers those root statements whenever the same indices are used.

The proof above includes the elementary Rolle argument only to make the real-zero conclusion independently checkable. Its binomial polynomial is a classical Jacobi form, and its ordinary-Dyck instance is already known. The only target-specific step needed for the named Fuss conjecture is the uniform enumeration leading to (5). Classical refined Fuss–Narayana enumeration may already imply that step; the novelty audit must distinguish an unrecorded deduction from an explicit prior resolution.

Sources and scope

No numerical root check is used in the proof. The literal path enumerator, formula, root simplicity and conditional transfer of ordinary-case root relations are Lean-verified; see the Lean status.