# A divisibility of q-binomial coefficients combinatorially

Let a and b be coprime positive integers. Then the number a+b divides the binomial coefficient $${a+b \choose a}$$. I know how to prove this combinatorially - for example after choosing an ordered set of a+b elements, there is a free action of a cyclic group of order a+b on the set of a-element subsets (and you can even choose a distinguished representative of each orbit if you so wish).

Passing to q-binomial coefficients, the quantum number $$[a+b]_q$$ divides the q-binomial coefficient $$\begin{bmatrix}{a+b}\\ {a}\end{bmatrix}_q$$.

My question today is whether this divisibility fact has a combinatorial proof or interpretation.

I remark that one can also ask whether or not $$\frac{1}{[a+b]_q}\begin{bmatrix}{a+b}\\ {a}\end{bmatrix}_q\in \mathbb{N}[q],$$ which would likely follow from any such combinatorial argument. When a+b=p is prime, I know this is the case by constructing algebraically a free $$\mathbb{F}_p[d]/(d^p)$$-module structure on the cohomology of the Grassmannian. I haven't done enough numerical experiments for non-prime values of a+b to be confident that this polynomial has non-negartive coefficients in general.

• When $a,b$ are not necessarily coprime, I would look at $\frac{1}{[(a+b)/\gcd(a,b)]_q}\begin{bmatrix}{a+b}\\ {a}\end{bmatrix}_q$. The usual proofs of ($q$-)integrality work for this more general form. – Ofir Gorodetsky Oct 23 '18 at 11:46
• Related – Peter Taylor Oct 23 '18 at 14:47

Assume $$q$$ is a prime power. Then there is a straightforward combinatorial interpretation.

Consider the group action of $$\mathbb F_{q^{a+b}}^\times / \mathbb F_{q^\times}$$ on the space of $$a$$-dimensional subspaces of $$\mathbb F_{q^{a+b}}$$, viewed as an $$a+b$$-dimensional vector space over $$\mathbb F_q$$. We have $$| \mathbb F_{q^{a+b}}^\times / \mathbb F_{q^\times}| = \frac{ q^{ a+b}-1}{q-1} = [a+b]_q$$ and the cardinality of the space of $$a$$-dimensional subspaces of $$\mathbb F_{q^{a+b}}$$ is $${a+b \choose a}_q$$. To show the divisibility, it suffices to show that this action is free. If any element of $$\mathbb F_{q^{a+b}}$$ fixes a subspace, by linearity the field it generates fixes that subspace, so the dimension of the subspace is divisible by the degree of the field it generates, which divides $$a+b$$.

This shows the ratio is a rational function in q which takes integer values on prime powers, which I believe some number theory shows is a polynomial in q that takes integer values on prime powers, which unfortunately is not an integral polynomial in q.

• Very cool, Will. Is there an extension of this idea that proves other q-congurences, such as q-Lucas or q-Chu-Vandermonde? – Ofir Gorodetsky Oct 23 '18 at 13:09
• @OfirGorodetsky It's not so hard to get $q$-Lucas from the action of $\mathbb F_{q^d}^\times$ on $\mathbb F_{q}^{n_1} \times \mathbb F_{q}^{n_0}$ by multiplication on the first factor. For any non-fixed point, the stabilizer is a proper subfield, hence the orbit has size $\frac{q^d-1}{q^{e}-1}$ which is a multiple of $\phi_d(q)$. Fixed points are counted by ${n_1 \choose k_1}_{q^d} {n_0 \choose k_0}_q$ and the first term is congruent mod $q^{d}-1$ to ${n_1 \choose k_1}$. – Will Sawin Oct 23 '18 at 23:43

A proof of nonnegativity appears in https://arxiv.org/pdf/0912.1578.pdf. The number $$\frac{1}{a+b}{a+b\choose a}$$ is called a rational Catalan number by Drew Armstrong. See for instance http://www.math.miami.edu/~armstrong/Talks/RCC_AIM.pdf. The $$q$$-analogue appears on page 200. I don't know whether a combinatorial interpretation of the coefficients is known.

This divisibility can be deduced from a $$q$$-analogue of Lucas's Theorem, which enjoys a group-action proof, see Theorem 2.2 and its proof in this elegant paper paper of Sagan.

The $$q$$-Lucas Theorem states that $$\begin{bmatrix}{n}\\ {k}\end{bmatrix}_q \equiv \binom{n_1}{k_2}\begin{bmatrix}{n_0}\\ {k_0}\end{bmatrix}_q \bmod \phi_d(q),$$ where: $$n=n_1d +n_0$$, $$k=k_1 d + k_0$$, $$0 \le k_0, n_0 < d$$, and $$\phi_d$$ is the $$d$$-th cyclotomic polynomial. Applying the theorem with $$n=a+b$$, $$k=a$$ and $$d$$ an arbitrary divisor of $$n$$ greater than $$1$$, the coprimality condition ensures that $$k_0 \neq 0$$ while $$n_0=0$$, so that we obtain $$\begin{bmatrix}{a+b} \\ {a} \end{bmatrix}_q \equiv 0 \bmod \phi_d(q)$$ for all $$d \mid a+b$$ ($$d >1$$). Since $$\{ \phi_q(d) \}_{d \mid a+b,\, d>1}$$ are distinct, monic polynomials whose product is $$[a+b]_q$$, it follows that $$\begin{bmatrix}{a+b} \\ {a} \end{bmatrix}_q \equiv 0 \bmod [a+b]_q.$$

The only non-combinatorial ingredient is the fact that we deal with each $$d$$ separately. It is interesting to see if there is a way around it, by modifying Sagan's proof. Sagan's proof uses the representation $$\begin{bmatrix}{n} \\ {k} \end{bmatrix}_q = \sum_{w \in W_{n,k}} q^{\text{inv}(w)},$$ where $$W_{n,k}$$ is the set of binary strings of length $$n$$ and $$k$$ zeros, and $$\text{inv}$$ counts inversions.

• Careful with the "distinct, monic polynomials": You're also using their coprimality over $\mathbb{Q}$, and then you're using Gauss's lemma to conclude that the final congruence holds over $\mathbb{Z}$ and not just over $\mathbb{Q}$. – darij grinberg Oct 23 '18 at 18:12

Supposing $$\gcd(a,b)=1$$ throughout this answer. Haiman was able to prove that $$\frac{1}{[a+b]_q}\begin{bmatrix}{a+b}\\ {a}\end{bmatrix}_q\in \mathbb{N}[q]$$ by interpreting it as the Hilbert series of some quotient of a polynomial ring. See propositions 2.5.(2-4) in his paper "Conjectures On The Quotient Ring By Diagonal Invariants".

Regarding combinatorial proofs: It is known in rational Catalan land that the quantity $$\frac{1}{a+b}\binom{a+b}{a}$$ counts

• paths from $$(0,0)$$ to $$(a,b)$$ with steps $$(1,0),(0,1)$$ that don't go below the $$y=bx/a$$ line
• simultaneous $$a,b$$ core partitions
and there are explicit statistics on both of these sets which conjecturally give $$\frac{1}{[a+b]_q}\begin{bmatrix}{a+b}\\ {a}\end{bmatrix}_q$$ (see conjectures 2 and 3 in this paper) but to my knowledge they are still open.