# A congruence involving binomial coefficients

The following open problem was shown to me by Maxim Kontsevich. I state it in a different but equivalent form. Let $a(n)$ be the sequence at http://oeis.org/A131868, that is, $$a(n) =\frac{1}{2n^2}\sum_{d|n}(-1)^{n+d}\mu(n/d){2d\choose d}.$$ Is it true that $6a(n)/n$ is always an integer? The sequence begins (starting at $n=1$) $(1,1,1,2,5,13,35,100,300,925,2915,9386,\dots)$.

If $n$ is prime then the result is true. It is equivalent to the well-known fact that ${2p\choose p}\equiv 2\,(\mathrm{mod}\,p^3)$ for a prime $p>3$. See for instance Enumerative Combinatorics, vol. 1, second ed., Exercise 1.14(d).

• Let $g(n) = 3(-1)^{n}\binom{2n}{n} = 3\binom{-n-1}{n}$. If I'm not mistaken, the conjecture will be implied by: $p^{3k} \mid g(dp^{k})-g(dp^{k-1})$ for any prime $p$. – Ofir Gorodetsky Jan 31 '15 at 17:23
• For $p \ge 5$, this is equation (39) here: arxiv.org/pdf/1111.3057.pdf . – Ofir Gorodetsky Jan 31 '15 at 17:43
• @Vesselin The conjecture states that $(g * \mu)(n)$ is always divisible by $n^3$. We can couple summands, i.e. - take the divisors $\{ d | n \mid \mu(n/d) \neq 0\}$, and couple them as follows: $d_1,d_2$ are coupled iff $d_1 = pd_2$. The sum $g * \mu$ is a sum of the form $\sum_{(d_1,d_2)} \mu(n/d_1) (g(d_1) - g(d_2))$. For this to be divisible by $p^{3k}$ where $p^k || n$, it is enough to require $p^{3k} \mid g(d_1)-g(d_2)$. As $p^k || d_1$ necessarily, the reduction follows (the other direction is not necessarily true). Hope I didn't make a stupid mistake. – Ofir Gorodetsky Jan 31 '15 at 18:13
• @VesselinDimitrov I did have a mistake in the first line, but I edited it in time. It is correct now. – Ofir Gorodetsky Jan 31 '15 at 18:22
• I took a liberty to add this sequence as oeis.org/A254593 – Max Alekseyev Feb 2 '15 at 1:06

Let $g(n) = 3(-1)^n\binom{2n}{n}$. The conjecture states $(g * \mu)(n)$ is divisible by $n^3$. We'll show the divisibility prime-power-wise.

Consider any $p|n$. We can couple summands in $g * \mu$ as follows: divisors $d_1,d_2$ of $n$ are coupled iff $d_1=pd_2$ and $\mu(n/d_1), \mu(n/d_2)\neq 0$. We can now rewrite $(g * \mu)(n)$ as a sum over couples: $\sum_{(d_1,d_2)} \mu(n/d_1) (g(d_1) - g(d_2))$. This way we see it is enough to show that $p^{3k} \mid g(dp^k)-g(dp^{k-1})$ for any prime $p$ and $(d,p)=1$.

For $p \ge 5$, this follows directly from the case $\epsilon=0$ of Lemma A in Gessel's Paper:

Let $p$ be a prime. Let $\epsilon=1$ if $p$ is 2 or 3, and $\epsilon=0$ if $p$ is greater than $3$. Then $\binom{p^ka}{p^k b} \equiv \binom{p^{k-1}a}{p^{k-1}b} \pmod {p^{3k-\epsilon}}$

This means that the conjecture is true for any $n$ not divisible by $2,3$.

For $p=3$, this also follows from the lemma from the $\epsilon=1$ case, thanks to the fact that the multiplicative term 3 appears in $g$.

So it remains to work out $p=2$. From the same lemma, we find that for $p=2$, $p^{3k-1} \mid g(dp^k)-g(dp^{k-1})$, so $a(n)$ is at worst an half-integer.

The proof of the lemma relied on theorem 2.2. Specializing the theorem to the case $p=2, a=2^{k+1}t,b=2^k t$ we find (using the fact that $v_{2}(\binom{2n}{n}) \ge 1$):

If $t$ is odd and $k\ge 2$, $\binom{2^{k+1}t}{2^{k}t} \equiv \binom{2^k t}{2^{k-1}t} \pmod {2^{3k}}$. If $t$ is odd and $k=1$, $\binom{2^{k+1}t}{2^{k}t} \equiv -\binom{2^k t}{2^{k-1}t} \pmod {2^{3k}}$

So $g(2^k t) \equiv g(2^{k-1}t) \pmod {2^{3k}}$ (only in the case $k=1$ we used the $(-1)^n$ term in $g(n)$). Hence the conjecture is proved.

• @RichardStanley - Care to share Maxim's (and yours) motivation behind the problem? Is there a new interpretation to $a(n)$? – Ofir Gorodetsky Feb 1 '15 at 18:41
• Maxim did not explain to me his motivation, but it was in the context of certain series being algebraic. In particular, $\prod_{n\geq 1}(1-x^n)^{(-1)^{n-1}na(n)}=C(-x)$, where $C(x) = \frac{1-\sqrt{1-4x}}{2x} = 1+x+ 2x^2+5x^3+\cdots$, the generating function for Catalan numbers. – Richard Stanley Feb 2 '15 at 4:02

I'd like to draw your attention to a recent paper On p-adic approximation of sums of binomial coefficients where we briefly discuss (in Section 4) the divisibility of this kind. Namely, we claim that for any integers $a\geq b>0$ and $m>0$, $$m^3\mid M(a,b)\cdot\sum_{d\mid m}\mu\left(\frac md\right)\binom{ad}{bd}$$ and $$m^3\mid M'(a,b)\cdot\sum_{d\mid m}(-1)^{m+d}\mu\left(\frac md\right)\binom{ad}{bd},$$ where $M(a,b) = \frac{12}{\gcd(12,ab(a-b))}$ and $M'(a,b) = \frac{3}{\gcd(3,ab(a-b))}\cdot 2^\delta$, where $$\delta = \begin{cases} \min\{1,\nu_2(b)\}, & \text{if}\ \nu_2(a-b)=\nu_2(b),\\ 2, & \text{otherwise}. \end{cases}$$ In particular, for the case $(a,b)=(2,1)$ (questioned here), we have $M(2,1)=6$ and $M'(2,1)=3$.

We don't give a proof in the paper (as this is only loosely related to the main subject), but we can share it if anyone is interested. In fact, the paper is mainly devoted to generalization of the congruence ${2p\choose p}\equiv 2\pmod{p^3}$ ($p>3$) to higher powers of $p$.