Reference needed for Lucas' Theorem for multinomial coefficients modulo a prime

Question

I am looking for a reference for a proof of the following:

Let $n$ and $a,b, \ldots ,z$ be non-negative integers with $a + b + \ldots + z = n$, and let $p$ be a prime. Write $n = n_0 + n_1 p + \ldots + n_m p^m$ in $p$-ary notation, similarly for $a, b, \ldots , z$. Then, modulo $p$, the multinomial coefficient ${n \choose a,b, \ldots, z}$ is zero if there is some "carrying" in computing the sum $a + b + \ldots + z$ (i.e., $a_i + b_i + \ldots + z_i \geq p$ for some $i$). Otherwise, it is the product of the multinomial coefficients of the individual $p$-digits, that is,

${ n \choose a, b, \ldots, z} = {n_0 \choose a_0, b_0, \ldots, z_0}{n_1 \choose a_1, b_1, \ldots, z_1} \ldots {n_m \choose a_m, b_m, \ldots , z_m}$

I've found plenty of references for this theorem restricted to binomial coefficients, otherwise known as Lucas' theorem, but can't seem to find one for arbitrary multinomials.

Thanks in advance for the help.

Answer 1

You can prove this by induction on the maximum number of base $p$ digits, and to make the argument simpler it's better to formulate a mildly stronger theorem where the leading base $p$ "digit" is allowed to be nonnegative rather than be constrained between 0 and $p-1$: for $d \geq 0$, $t \geq 1$ and nonnegative integers $m_0,m_1,\dots,m_t$, write the $m_i$'s as $$ m_0 = c_0 + c_1p + \cdots + c_dp^d \text{ and } m_j = c_{0j} + c_{1j}p + \cdots + c_{dj}p^d $$ where $0 \leq c_i, c_{ij} \leq p-1$ for $i < d$ and $c_d \geq 0$, $c_{dj} \geq 0$. Then you want to show $$ \binom{m_0}{m_1,\dots m_t} \equiv \binom{c_0}{c_{01},\dots,c_{0t}}\cdots \binom{c_d}{c_{d1},\dots,c_{dt}} \bmod p. $$ Your description of this result treats separately the case when one of the multinomial coefficients on the right doesn't have a combinatorial meaning (because the numbers in the bottom have a sum exceeding the top), but the congruence is true even in that case if you define a multinomial coefficient as a polynomial in the upper parameter, in the same way you can define $\binom{a}{n}$ as $a(a-1)\cdots(a-n+1)/n!$ in order to give a meaning to $\binom{a}{n}$ even if $a$ is not a positive integer greater than or equal to $n$.

By allowing $c_d,c_{d1},\dots,c_{dt}$ to be just nonnegative, a proof by induction on $d$ immediately reduces to the case $d = 1$. Now use the multinomial theorem in ${\mathbf F}_p[X_1,\dots,X_t]$: in the mod $p$ equation $$ (1 + X_1 + \cdots + X_t)^{c_0+c_1p} = (1 + X_1 + \cdots + X_t)^{c_0}(1 + X_1^p + \cdots + X_t^p)^{c_1} $$ comparing the coefficient of $X_1^{m_1}\cdots X_t^{m_t}$ on both sides implies $$ \binom{m_0}{m_1,\dots m_t} \equiv \binom{c_0}{c_{01},\dots,c_{0t}}\binom{c_1}{c_{11},\dots,c_{1t}} \bmod p $$ and we're done.

I gave this argument when I needed the result in www.math.uconn.edu/~kconrad/articles/jacobistick.pdf. See congruence C2 at the bottom of the third page. (Appeared in Enseign. Math. 41 (1995), 141−153.)

Answer 2

Instead of giving a reference, I suggest either proving it the same way as Lucas' theorem, or noting that it's a quick corollary of Lucas' theorem, or both. It's a corollary because you can express a multinomial coefficient as a product of binomial coefficients in the standard way. Or to prove it the same way, you can divide a set $S$ of $n$ elements into rings of size $p^k$ for $k \le m$, and then look at the action of a product of cyclic groups $\mathbb{Z}/p^k$ on colored partitions of $S$ of type $a,b,\ldots,z$. Lucas' theorem counts the orbits of size 1, noting that the size of any larger orbit is divisible by $p$.

A lot of people feel obliged to either give a reference or a detailed proof for everything in a paper. I personally don't mind an abbreviated argument for this type of fact, together with a disclaimer that it isn't claimed to be a new result. Sometimes I even prefer that.

Answer 3

I've heard the theorem identified as Kummer's theorem. Here's the reference (without umlauts and accents):

E. E. Kummer, Uber die Erganzungssatze zu den allgemeinen Reciprocitatsgesetzen, J. Reine Angew. Math. 44 (1852), 93–146