18
$\begingroup$

This is a question I have since longer time, but I have absolutely no idea how to proceed on it.

Let $p>3$ be a prime. Prove that $\displaystyle\sum\limits_{k=1}^{p-1}\frac{1}{k}\binom{2k}{k}\equiv 0\mod p^2$. Here, we work in $\mathbb{Z}_{\mathbb{Z}\setminus p\mathbb{Z}}$ (that is, $\mathbb{Z}$ localized at all numbers not divisible by $p$).

I know that it is $0\mod p$ (though I can't find the reference at the moment; it was some hard olympiad problem on MathLinks). The $0\mod p^2$ assertion is backed up by computation for all $p<100$. I am sorry if this is trivial or known. I would be delighted to see a combinatorial proof (= finding a binomial identity which reduces to the above when computed $\mod p^2$). Some number-theoretical arguments would be nice, too. However, I fear that if you use analytic number theory, I will not understand a single word.

EDIT: Epic fail at question title fixed.

Improve this question
$\endgroup$
8
  • $\begingroup$ This might help: mathworld.wolfram.com/WolstenholmesTheorem.html $\endgroup$
    – Steve Huntsman
    Commented Jan 10, 2010 at 16:10
  • $\begingroup$ I know of Wolstenholme's theorem - but it seems to weak to be of use here. $\endgroup$
    – darij grinberg
    Commented Jan 10, 2010 at 16:25
  • 1
    $\begingroup$ "Almost" is good. $\endgroup$
    – darij grinberg
    Commented Jan 10, 2010 at 17:19
  • 2
    $\begingroup$ For p<2001, v_p(sum) \geq 2 if and only if p is a prime greater than 3, in which case v_p(sum) = 2. $\endgroup$
    – Kevin O'Bryant
    Commented Jan 10, 2010 at 18:40
  • 2
    $\begingroup$ The world of supercongruences is really nice and unpredictable. Some of them are easy and some are too hard. The really beautiful congruence is the one for $$ \sum_{k=1}^{(p-1)/2}\frac{(-1)^k}{k^2}\binom{2k}{k}; $$ the binomial sum is very similar to yours. Check with math/0906.5150 (the end of the preprint) on how it is related to Apery's formula for $\zeta(3)$ (more precisely to its generalization). $\endgroup$
    – Wadim Zudilin
    Commented Jun 8, 2010 at 13:19

3 Answers 3

Reset to default
18
$\begingroup$

Your binomial sum is divisible by $p^2$ as is shown in a recent paper of Sun and Tauraso: https://arxiv.org/abs/0805.0563

Even more remarkably, they compute that it's equivalent to $\frac{8}{9}p^2B_{p-3} \bmod p^3$, as well as various other congruences for the corresponding alternating sum.

Improve this answer
$\endgroup$
0
4
$\begingroup$

For the asymptotics: begin with the well-known generating function

$$ \sum_{k \ge 0} {2k \choose k} z^k = (1-4z)^{-1/2}. $$

We can remove the first term to get

$$ \sum_{k \ge 1} {2k \choose k} z^k = (1-4z)^{-1/2} - 1. $$

Dividing by $z$, and then integrating with respect to $z$, turns $z^k$ into $z^k/k$.

$$ \sum_{k \ge 1} {2k \choose k} {1 \over k} z^k = -2 \log (1 + \sqrt{1-4z}) + 2 \log 2. $$

(The $2 \log 2$ is a constant of integration.)

Finally, let $f(n) = \sum_{k=1}^n {1 \over k} {2k \choose k}$. These are the partial sums of the previous sequence, so we have

$$ F(z) = \sum_{n \ge 1} f(n) z^n = {-2 \over 1-z} \log( 1 + \sqrt{1-4z} ) $$

We can find the asymptotics of the coefficients of this generating function by singularity analysis. The singularity closest to the origin is at $z = 1/4$. Near $z = 1/4$,

$$ F(z) \sim {-8 \over 3} \sqrt{1-4z} $$

and by a transfer theorem (probably originally due to Flajolet and Odlyzko and in the Flajolet-Sedgewick book Analytic Combinatorics, although it's too late to look up the details right now) we get

$$ f(n) = [z^n] F(z) \sim {-8 \over 3} [z^n] \sqrt{1-4z} $$

Finally, $[z^n] \sqrt{1-4z} = -{2 \over n} {2n-2 \choose n-1}$, and so by Stirling's formula, as $n \to \infty$

$$ f(n) \sim {-8 \over 3} {-2 \over n} {4^{n-1} \over \sqrt{\pi n}} = {4 \over 3} {4^n \over \sqrt{\pi n^3}}. $$

Finally, because I was somewhat awkward in my indexing, we have to take $p = n-1$, and so

$$ f(p) \sim {1 \over 3} {4^p \over \sqrt{\pi p^3}} $$.

As has been observed by John Mangual and Mariano Suárez-Alvarez, this is about one-third of the $p$th Catalan number. Examining the singularity near $z = 1/4$ more closely would lead to higher-order terms.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Very nice observation, though completely orthogonal to my question, as long as it's not $p$-adic asymptotics. But my question is answered anyway. $\endgroup$
    – darij grinberg
    Commented Jan 11, 2010 at 13:47
  • $\begingroup$ That's true, it's orthogonal to your question. There seemed to be some interest in the real (as opposed to $p$-adic) asymptotics, though. As far as I know methods like the ones I used here are useless for number-theoretic work (but I'd love to be proven wrong!) $\endgroup$
    – Michael Lugo
    Commented Jan 11, 2010 at 16:24
1
$\begingroup$

This is too big to go into a comment...

A little bit of experimental observations:

The factorizations of these numbers are quite impressive. The primes which appear with a positive exponent appear with exponent $1$, except for two expections at most: $p$ and, in some cases, another prime, while typically there is only one. Moreover, these factors are, as far as I can caculate in small time, all small except for one huge factor. For example, factoring the sum for $p=163$ gives the following:

{{2,-6},{3,-4},{5,-3},{7,-1},{11,-2},{13,1},{19,-1},{23,-1},{29,-1},{37,-1},{41,-1},{43,-1},{47,-1},{53,-1},{59,-1},{61,-1},{67,-1},{71,-1},{73,-1},{79,-1},{83,-1},{89,-1},{97,-1},{101,-1},{103,-1},{107,-1},{109,-1},{113,-1},{127,-1},{131,-1},{137,-1},{139,-1},{149,-1},{151,-1},{157,-1},{163,2},{167,1},{173,1},{179,1},{181,1},{191,1},{193,1},{197,1},{199,1},{211,1},{223,1},{227,1},{229,1},{233,1},{239,1},{241,1},{251,1},{257,1},{263,1},{269,1},{271,1},{277,1},{281,1},{283,1},{293,1},{307,1},{311,1},{313,1},{317,1},{13220623261776675290879751941470274402307094729054895565509915203488199874013343384493,1}}

Here we see that $163$ is the only prime which appears more than one time, and all primes are $O(163)$ except the last one, which is pretty huge. (At that size, one really has to trust Wolfram!) This is typical (as far as I can compute in a small time, which is up to $163$ :) )

Moreover, as John Mangual observes in a comment above, this sums appear to be quite close to one third of the $p$th Catalan number. Mathematica quite immediately tells me that the sum is equal to $$\frac{\left(\begin{array}{c} 2 p \\\\ p\end{array}\right) {}\_3F_2\left(1,p,p+\frac{1}{2};p+1,p+1;4\right)}{p}-\frac{2 i \pi }{3},$$ so if some asymtoptic information about ${}\_3F_2$ might actually prove this.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Also the denominator tends to consist of primes less than p, and the numerator of primes between p and 2p, plus a few larger ones. There isn't necessarily one large factor; for example for p = 31 the numerator has prime factors 31^2*37^2*41*43*47*53^2*59*61*73*1801*6143. $\endgroup$
    – Michael Lugo
    Commented Jan 11, 2010 at 3:05
  • $\begingroup$ Here is my attempt at explaining the many small primes: At first, it is clear that the denominator of $\displaystyle\sum\limits_{k=1}^{p-1}\frac{1}{k}\binom{2k}{k}$ has only primes <p in its factorization (actually, it divides (p-1)!). As for the numerator, we notice that if we denote $\displaystyle\sum\limits_{k=1}^{n-1}\frac{1}{k}\binom{2k}{k}$ by F(n), then F(p) is not only divisible by p, but also by all primes between p and 2p-1 (because F(p) is congruent to F(u) mod u for every prime u between p and 2p-1, since the sums F(p) and F(u) differ from each other only by some terms which ... $\endgroup$
    – darij grinberg
    Commented Jan 11, 2010 at 13:56
  • $\begingroup$ ... are easily seen to be divisible by u, since $\binom{2k}{k}$ is divisible by u for every k between p and 2p-2). So the numerator must be divisible by all primes u between p and 2p-1, including p twice (according to the original question). With so many little prime factors, there is not much place for big prime factors - but this is just a heuristic argument, and I wouldn't be surprised if for really large p, the big factors would "win" (i. e., their distribution will be not much different from any other "typical" number sequence of similar asymptotics). $\endgroup$
    – darij grinberg
    Commented Jan 11, 2010 at 14:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .