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.

  • 1
    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 at 11:46
  • Related – Peter Taylor Oct 23 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 at 13:09
  • 1
    @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 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.

  • 1
    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 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.

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.