# Binomial Coefficients involving Prime Powers Minus 1

I would like to show the following is true; Let $p\in\mathbb{P}, \alpha,n\in\mathbb{N}$. Then

$$p^\alpha\mid\sum_{k=1}^{n-1}\binom{(p^\alpha-1)n}{(p^\alpha -1)k}.$$

I've never worked with prime powers inside binomial coefficients. I was hoping to see if there are any theorems, papers, or other research materials that deal with these types of objects. The reason for the belief is due to a Mathematica calculation that I ran that suggests this holds so long as the binomial coefficient involves multiples of $m=p^\alpha-1$. Here is the calculation. The green rows represent the values of $m$ from 2 to 30 that support the divisibility claim. These numbers in order are

$$2,3,4,6,7,8,10,12,15,16,18,22,24,26,28,30$$

and these numbers, when entered into OEIS.org return that these numbers are prime powers minus one. (i ran the calculation again from $m=31..50$ to ensure this was the correct sequence, as for $m=1$ to $30$ yield a similar sequence...but i verified that $44$ is not a value of $m$ that produces divisibility). I know that this does not constitute a proof, and in NT, 40 is so small a number to test. But I reran the calculation for $n$ up to $100$ and $m$ up to $100$ and it still seems to hold. If this is true, it must be due to the nature of $p^{\alpha}-1$ as apposed to $p^{\alpha}\cdot k-1$, where $k$ is some other integer.

I know that $p^\alpha-1=(p-1)(p^{\alpha-1}+p^{\alpha-2}+...+p+1)$ but I can't see how this helps. Are there properties of cyclotomic polynomials that help?

EDIT: This question is directly related. Thank you.

• For $m<p$, the term-wise divisibility follows from Kummer's theorem. Numerically, term-wise divisibility fails sometimes for $m\geq p$ (specifically, this appears to happen when $p|m$). – Julian Rosen Aug 20 '18 at 16:48
• Thanks! I found an example where termwise divisibility fails but the conjecture still holds. However, not for $p|n$, but for $p|n-1$. Could that be the case you meant? The example I found is for $m=15=2^4-1$ and $n=17$. While $2^4\mid\sum_{k=1}^{16}\binom{255}{15k}$, it turns out that $2^4$ never divides $\binom{255}{15k}$, as these binomial coefficients are all odd. – Steve Kass Aug 20 '18 at 17:46
• @SteveKass Oh yes, I meant $p|n-1$ – Julian Rosen Aug 20 '18 at 18:00
• @SteveKass On Mathematica ver 10.1.3.0 you will get a wrong answer for $p=17,\alpha =6, n=9$. It should return $0$ for each term, which is easy to show with Kummer's Theorem, but Mathematica returns $8$. If you find any counterexamples be sure to check them thoroughly. I would recommend implementing Generalized Lucas Theorem for testing larger ranges. Mathematica computes the actual binomial terms which makes it too slow for large parameters. – Yong Hao Ng Aug 22 '18 at 12:29
• So what has been proven, what disproven and what conjectured? The comment thread is confusing to outsiders. – darij grinberg Aug 25 '18 at 19:12

## 1 Answer

The claim is true. Summary: we show by induction it is enough to prove the congruence for $A_m$ for $m = 1,\ldots, k$ where $N+1 = p^k$, and then we prove that by showing (in this particular case) that the binomial coefficients are all divisible by $p^k$ (which doesn't hold in general).

Let $$A_m = \sum_{j=0}^{m} \binom{Nm}{Nj}.$$ The claim to be proven is $A_m \equiv 2 \mod N+1$ if $N + 1 = p^k$ is a prime power.

Note that

$$(1 + x)^{Nm} = \sum_{j=0}^{Nm} \binom{Nm}{j} x^j,$$

if one lets $\zeta$ denote a primitive $N$th root of unity, then

$$\sum_{i=0}^{N-1} (1 + \zeta^i)^{Nm} = \sum_{j=0}^{Nm} \binom{Nm}{j} \sum_{i=0}^{N-1} \zeta^{ji}$$ $$= \sum_{j=0}^{Nm} \binom{Nm}{j} \begin{cases} N, & j \equiv 0 \mod N \\ 0, & j \not\equiv 0 \mod N. \end{cases}$$ $$= N \sum_{j=0}^{m} \binom{Nm}{Nj}.$$ So if, for $m \ge 1$, $$B_m = \sum_{i=0}^{N-1} (1 + \zeta^i)^{Nm} = \sum_{\zeta^i \ne -1} (1 + \zeta^i)^{Nm},$$ then the congruence $A_m \equiv 2 \mod (N+1)$ is equivalent to the congruence $B_m \equiv - 2 \mod (N+1)$.

The roots of unity are all distinct modulo $p$, so there is a unique $\zeta^i \equiv -1 \mod p$. If $p$ is odd, then $N$ is even, and it is $\zeta^{i} = -1$, and $(1 + \zeta^i) = 0$. If $p = 2$, then $N$ is odd, and it is $\zeta^i = 1$ and $(1 + \zeta^i) = 2$. In the latter case, for $m \ge 1$, the term $(1 + \zeta^i)^N$ is equal to $2^N$ which is certainly trivial modulo $2^k = N+1$ because $2^N \ge N+1 = 2^k$. Hence we have

$$B_m = \sum_{\zeta^i \ne -1} (1 + \zeta^i)^{Nm} \equiv \sum_{\zeta^i \not\equiv -1} (1 + \zeta^i)^{Nm} \mod p^k.$$

The polynomial $X^N - 1$ is separable over $\mathbf{F}_p$. Moreover, its roots over this field are precisely the units of $\mathbf{F}_q$, since the units in that field are cyclic of order $q - 1 = N$. Hence the extension cut out by the roots of unity $\zeta^i$ over $\mathbf{Q}_p$ is just the fraction field of the Witt vectors $W(\mathbf{F}_q)$. All of this is just to say (if you don't know algebraic number theory) that it makes sense to talk of congruences for these algebraic integers modulo powers of $p$, and that we also have (assuming $\zeta^i \not\equiv -1 \mod p$): $$(1 + \zeta^i)^N \equiv 1 \mod p$$ Hence it also follows that $$((1 + \zeta^i)^{N} - 1)^k \equiv 0 \mod p^k$$ But then, for any non-negative integer $r$, we have: $$\sum_{\zeta^i \not\equiv -1} ((1 + \zeta^i)^{N} - 1)^k (1 + \zeta^i)^{Nr} \equiv 0 \mod p^k,$$ or, expanding out: $$\sum_{r=0}^{k} B_{n+ r} (-1)^r \binom{k}{r} \equiv 0 \mod p^k,$$ and thus we obtain the $k$-term recurrence $$B_{n+k} (-1)^{k-1} = \sum_{r=0}^{k-1} B_{n+r} (-1)^r \binom{k}{r} \mod p^k$$ Suppose that $B_m \equiv -2 \mod p^k$ for $m = 1, \ldots, k$. Then, by induction, we get $B_m \equiv -2 \mod p^k$ for all $m$, simply by applying the recurrence above and using the identity $$\sum (-1)^r \binom{k}{r} = 0.$$ So we just need to prove the first few values of $A_m \equiv 2 \mod p^k$. But now we can look at the actual binomial coefficients themselves.

Suppose that $N+1 = p^k$. We claim that, in the range $a+b \le k$ and $a,b > 0$, we have $$\binom{N(a+b)}{Nb} \equiv 0 \mod p^k.$$ Once we know this, it follows that $A_m \equiv 2 \mod p^k$ for $m \le k$ and we are done by induction.

In fact, since trivially $k \le p^k$, we are done by the following stronger claim.

Claim Suppose that $a + b \le p^k$ and $N + 1 = p^k$. Then the $p$-adic valuation of $$\binom{N(a+b)}{Nb}$$ for $a,b \ge 1$ is exactly $k$.

Proof

The $p$-adic valuation of the binomial coefficient is precisely the number of times one has to carry the one when adding $Na$ and $Nb$. For a number $0 \le m-1 < p^k$ (which includes $a-1$, $b-1$, and $c = a+b-1$, we may write $$m - 1 = (m_{k-1}, m_{k-2}, \ldots, m_0)$$ in base $p$, and we may also write $$p^k - m = (p^k - 1) - (m - 1) = (m'_{k-1}, m'_{k-2}, \ldots, m'_0).$$ Since $$m-1 + (p^k - m) = p^k - 1,$$ we have, for all $i = 0,1,\ldots,k-1$, that $$m_i + m'_i = p - 1.$$ We now find that $aN$, $bN$, and $cN$ have $p$-adic expansions as follows $$aN = (a_{k-1}, a_{k-2}, \ldots, a_0,a'_{k-1}, \ldots, a'_0),$$ $$bN = (b_{k-1}, b_{k-2}, \ldots, b_0,b'_{k-1}, \ldots, b'_0),$$ $$cN = (c_{k-1}, c_{k-2}, \ldots, c_0,c'_{k-1}, \ldots, c'_0),$$ As noted before, we have $$a_i + a'_i = p-1, \ b_i + b'_i = p-1, c_i + c'_i = p -1.$$ Hence $$(a_i + b_i) + (a'_i + b'_i) = (c_i + c'_i) + p - 1,$$ or $$(a_i + b_i - c_i) + (a'_i + b'_i - c'_i) = p - 1.$$

Now

$$a_i + b_i = c_i + \begin{cases} p & \text{carry required} \\ 0 & \text{no carry required}\end{cases} \ + \begin{cases} -1 & \text{carry required in i-1 slot} \\ 0 & \text{no carry required in i-1 slot} \end{cases}$$ and the same with $a'_i$, $b'_i$, and $c'_i$.

There is a unique way of writing $p-1$ as a sum of exactly two terms in the set $\{p,0,-1,0\}$. It follows that in the pair of slots $(i,i+k)$, either exactly one of the pairs coming from the $m_i$-coefficient and the $m'_i$ coefficient requires "carrying the one," (It also follows that exactly one of the pairs $m_{i-1}$ and $m'_{i-1}$ (which might be $m'_k$ if $i = 0$) also requires carrying the one, although this is the same statement for $i-1$ instead of $i$. This is why the sum is $p-1$ and not $p$.)

But since exactly one of the pair coming from the $m_i$-coefficient and the $m'_i$ coefficient requires "carrying the one," exactly half the terms have this property, and we are done.

Additional: A weaker version of the induction argument is as follows. By the analog of Fermat's Little Theorem and Euler's Theorem in $W(\mathbf{F}_q)$ ($q = p^k$), one has the identity $$\gamma^{N p^{k-1}} = \gamma^{(q-1)p^{k-1}} \equiv 1 \mod p^k$$ for any $\gamma \in W(\mathbf{F}_q)^{\times}$, that is, any $\gamma \not\equiv 0 \mod p$. It follows that

\begin{aligned} B_{m + p^{k-1}} = & \ \sum_{\zeta^i \not\equiv - 1} (1 + \zeta^i)^{mN + N p^{k-1}}\\ \equiv & \ \sum_{\zeta^i \not\equiv - 1} (1 + \zeta^i)^{mN} \mod p^k\\ = & \ B_m \mod p^k, \end{aligned} and so by induction it suffices to show that $B_m \equiv -2 \mod p^k$ for $m = 1, \ldots, p^{k-1}$ rather than $m = 1, \ldots, k$. Since the second step actually proves the congruence $B_m \equiv -2 \mod p^k$ for $m = 1, \ldots, p^k$, this also suffices, and one might find this version of the inductive step slightly easier.

• @Lalaloopsy of course it is original. When I'm bored, I look at math.stackexchange, and I was at the airport, so definitely bored. – Margerie Mumblecrust Aug 28 '18 at 17:32
• @MargerieMumblecrust: In my personal view, the population of readers that understand an argument using Witt vectors and unramified extensions is much smaller than that of readers that understand an argument using basic finite field theory (such as mine). And I don't think what I'm doing is dubious -- you are saying that it proves a bit more than what is necessary; but that doesn't doom it to being false. There is nothing wrong with your answer! – darij grinberg Aug 28 '18 at 19:51
• @darijgrinberg The sum is better written as a sum over $\zeta^i \not\equiv -1 \mod p$. Then, in the $p = 2$ case, one has to additionally note that the extra term $2^N$ can be ignored. I've edited accordingly. – Margerie Mumblecrust Aug 28 '18 at 20:31
• @darijgrinberg ps you are doing a good job simulating a persnickety referee, that combined with the very clunky LaTeX compiling which makes making minor edits and checking for typos close to impossible is having a triggering effect. I came here to relax! – Margerie Mumblecrust Aug 28 '18 at 20:44
• Very nice piece of math, enjoy the bounty! Though I must say you lost me on the fraction fields of Witt vectors, but I guess that is a good thing (new stuff to learn). – Sil Aug 29 '18 at 6:48