A congruence involving binomial coefficients

Question

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).

Answer 1

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.

Answer 2

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$.