Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
This might help: mathworld.wolfram.com/WolstenholmesTheorem.html –  Steve Huntsman Jan 10 '10 at 16:10
    
I know of Wolstenholme's theorem - but it seems to weak to be of use here. –  darij grinberg Jan 10 '10 at 16:25
1  
"Almost" is good. –  darij grinberg Jan 10 '10 at 17:19
2  
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. –  Kevin O'Bryant Jan 10 '10 at 18:40
2  
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). –  Wadim Zudilin Jun 8 '10 at 13:19
show 4 more comments

3 Answers

up vote 18 down vote accepted

Your binomial sum is divisible by $p^2$ as is shown in a recent paper of Sun and Tauraso: http://front.math.ucdavis.edu/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.

share|improve this answer
    
Thank you very much! –  darij grinberg Jan 11 '10 at 13:48
add comment

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.

share|improve this answer
    
Very nice observation, though completely orthogonal to my question, as long as it's not $p$-adic asymptotics. But my question is answered anyway. –  darij grinberg Jan 11 '10 at 13:47
    
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!) –  Michael Lugo Jan 11 '10 at 16:24
add comment

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.

share|improve this answer
    
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. –  Michael Lugo Jan 11 '10 at 3:05
    
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 ... –  darij grinberg Jan 11 '10 at 13:56
    
... 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). –  darij grinberg Jan 11 '10 at 14:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.