# What is the sum of the binomial coefficients ${n\choose p}$ over prime numbers?

What is known about the asymptotic order and/or lower and upper bound of the sum of the binomial coefficients

$$S_n = {n\choose 2} + {n\choose 3} + {n\choose 5} + \cdots + {n\choose p}$$

where the sum runs over all primes $$\le n$$?

Update 12-Aug-2019: Sungjin Kim has shown that almost for all $$n$$,

$$S_n \sim \frac{2^n}{\log(n/2)}$$ In the previous version we had $$\log n$$ in the denominator which has not been corrected.

Actual values: My calculation gave the following asymptotic order of $$n$$ and the ratio $$r_n = s_n/(2^n/\log n)$$.

(100000, 1.13766407097665)
(110000, 1.00289966767667)
(120000, 0.97497422941139)
(130000, 1.07297773163979)
(140000, 1.09130325488627)
(150000, 1.03493135205282)
(160000, 1.09228831426585)
(170000, 1.02437859352022)
(180000, 1.18789309596329)
(190000, 1.11814470079054)
(200000, 1.00572021128112)
(210000, 1.03114155491856)
(220000, 0.95835641265769)
(230000, 1.03176200981585)
(240000, 1.10141025102049)
(250000, 1.04435554152951)
(260000, 1.02244981941248)
(270000, 1.03103959797895)
(280000, 1.05303304022584)
(290000, 1.00915670279005)
(300000, 1.08798558856723)
(310000, 1.05106334090960)
(320000, 1.07582903038813)
(330000, 0.920056638088384)
(340000, 1.13576974339066)
(350000, 0.923576122540866)
(360000, 1.15321376273496)
(370000, 1.08344303929811)
(380000, 1.02063510069254)
(390000, 1.08363394859595)
(400000, 1.05463839543006)
(410000, 1.04986600633135)

• Here it is in oeis: oeis.org/A121497 – jwc845 Sep 25 '18 at 19:07
• The asymptotics should be dominated by the distribution of primes near $\frac{n}{2}$. By the PNT we expect such primes to locally have a density of about $\frac{1}{\log \frac{n}{2}}$. So a rough guess for the asymptotics is $O \left( \frac{1}{\log n} {n \choose n/2} \right)$, which works out to something like $O \left( \frac{2^n}{\sqrt{n} \log n} \right)$. This shouldn't be hard to get experimental data on. – Qiaochu Yuan Sep 25 '18 at 20:42
• @QiaochuYuan According to your guess, $O(\frac{2^n}{\log n})$ is plausible since you began with the density. – Sungjin Kim Sep 26 '18 at 4:51
• I think we may be able to prove something like $\frac {2^n}{\log n} \ll S_n \ll \frac{2^n \log\log n}{\log n}$. – Sungjin Kim Sep 26 '18 at 4:53
• Experimentally $O(2^n/(\log n))$ looks more likely than the form with the square root. – Michael Lugo Sep 26 '18 at 15:46

Following Qiaochu Yuan's approach, the inequalities $$\frac{2^n}{\log n} \ll S_n \ll \frac{2^n }{\log n}$$ seems plausible. The lower bound is a conjecture, but it is possible to prove the upper bound.

$$T_n \sim \mathrm{B}(n,\frac12)$$ is the binomial distribution.

$$S_n=\sum_{p\leq n} \binom np$$ summed over $$p$$ prime.

$$\pi(y)=\sum_{p\leq y}1$$ is the prime counting function.

$$A(n)\ll B(n)$$ means $$|A(n)|\leq CB(n)$$ for some absolute constant $$C>0$$.

Lower Bound (Conjecture)

Fix $$x>0$$. We have $$P\left(p \mathrm {\ is \ prime}, \ T_n=p, \ \frac n2 -x\sqrt n\leq T_n \leq \frac n2 + x\sqrt n\right) \leq \frac {S_n}{2^n}.$$ Since binomial coefficients $$\binom nk$$ peak at $$k=n/2$$ and become smaller when $$k$$ is further away from $$n/2$$, we take the following as a lower bound of the probability.

$$\left(\pi(\frac n2+x\sqrt n)-\pi(\frac n2-x\sqrt n)\right)P\left(T_n=\lfloor \frac n2+x\sqrt n\rfloor\right).$$

By Stirling's formula, and $$\log (1+t)=t-\frac{t^2}2+O(\frac1{t^3})$$ for $$|t|\leq 1/2$$, we have $$P\left(T_n=\lfloor \frac n2+x\sqrt n\rfloor\right)\sim \frac{2}{\sqrt{2\pi n}} e^{-2x^2}.$$

If we have the following conjecture (see this survey by Yildrim for more information), $$\pi(\frac n2+x\sqrt n)-\pi(\frac n2-x\sqrt n)\sim \frac{2x\sqrt n}{\log n},$$ then we have the conjectural lower bound $$\frac{4x\cdot 2^n}{e^{2x^2}\sqrt{2\pi}\log n} \lesssim S_n.$$

Upper Bound (Easy Version)

By Hoeffding's inequality, we give a bound of sum over primes further away from $$n/2$$. $$P\left(p \mathrm {\ is \ prime}, \ T_n=p, \ |T_n-\frac n2|>\sqrt{n \log\log n} \right)$$ $$\leq P\left( |T_n-\frac n2|\geq \sqrt{n \log\log n}\right)\leq 2e^{-2\log\log n}\ll \frac{1}{(\log n)^2}.$$ For the primes close to $$n/2$$, we apply Brun-Titchmarsh inequality, $$P\left(p \mathrm {\ is \ prime}, \ T_n=p, \ |T_n-\frac n2|\leq \sqrt {n \log\log n }\right)$$ $$\leq \left(\pi(\frac n2 + \sqrt {n \log\log n})-\pi(\frac n2-\sqrt {n \log\log n})\right)P\left(T_n=\lfloor \frac n2\rfloor\right)$$ $$\ll \frac{\sqrt{n\log\log n}}{\log n} \cdot \frac{1}{\sqrt n} = \frac{\sqrt{\log\log n}}{\log n}.$$ Therefore, we have the upper bound $$S_n\ll \frac{2^n\sqrt{\log\log n}}{\log n}.$$

With more care, we can remove $$\sqrt{\log\log n}$$ from the upper bound.

Again, by Hoeffding's inequality, $$P\left(p \mathrm {\ is \ prime}, \ T_n=p, \ |T_n-\frac n2|>\sqrt{n \log\log n} \right) \ll \frac1{(\log n)^2}.$$

For the primes in $$|T_n-\frac n2|\leq\sqrt{n \log\log n}$$, consider the subintervals $$\frac n2 + x\sqrt n \leq p < \frac n2 + (x+1)\sqrt n$$ for nonnegative integers $$x\leq \sqrt{\log\log n}$$ first.

Then the negative integers $$-\sqrt{\log\log n}\leq x$$ are treated similarly.

The number of primes in this interval is by Brun-Titchmarsh inequality, $$\ll \frac{\sqrt n}{\log n}$$, while $$P(T_n=p)\leq P\left(T_n=\lfloor \frac n2 + x\sqrt n\rfloor\right)\sim \frac{2}{\sqrt{2\pi n}} e^{-2x^2}.$$

Note that the last asymptotic still holds if $$|x|\leq \sqrt{\log\log n}$$. Then we have

$$P\left(p \mathrm {\ is \ prime}, \ T_n=p, \ \frac n2 + x\sqrt n \leq p < \frac n2 + (x+1)\sqrt n\right)$$ $$\ll \frac{\sqrt n}{\log n} \cdot \frac{e^{-2x^2}}{\sqrt n}.$$ Thus by summing over $$x$$, $$P\left(p \mathrm {\ is \ prime}, \ T_n=p, \ |T_n-\frac n2|\leq \sqrt {n \log\log n }\right)$$ $$\ll \sum_{x=0}^{\infty}\frac{e^{-2x^2}}{\log n}\ll \frac 1{\log n}.$$ Therefore, we obtain $$S_n\ll \frac{2^n}{\log n}.$$

Update on 2019/3/4

Nilotpal Kanti Sinha and I started working on writing a paper on this subject. Here is current progress. The proofs are too long to be contained here, but the main idea of splitting up the sum into short intervals is present in this answer. To prove 1, we need Huxley's zero density estimate and its consequence on the primes in the short intervals. (Chapter 5 of this note by Angel Kumchev: https://tigerweb.towson.edu/akumchev/a5.pdf).

1. We have for almost all $$n$$, $$S_n= \frac{2^n}{\log n}+O\left(\frac{2^n}{(\log n)^2}\right) \ \textrm{as }n\rightarrow \infty.$$

Here, almost all means that the number of $$n\in [1,N]\cap \mathbb{Z}$$ for which the asymptotic formula fails is $$o(N)$$.

1. We have $$\alpha:=\liminf_{n\rightarrow\infty}\frac{S_n\log n}{2^n}\leq 1\leq \limsup_{n\rightarrow\infty} \frac{S_n \log n}{2^n} \leq 4.$$

2. The statement $$\alpha>0$$ implies that, there is $$b>0$$ and $$N_0(b)>0$$ such that, $$\pi\left(\frac n2 +\sqrt {n\log\log n}\right)-\pi\left( \frac n2-\sqrt {n\log\log n}\right)\geq \frac{b\sqrt n}{\log n} \ \textrm{for all }n\geq N_0(b).$$

• This looks very impressive and non-trivial. Let me take some time to go through it in details. By the way, whats with the number 707107? – NiloS Sep 26 '18 at 15:26
• This is very interesting problem. The number is by the way, came from $1/\sqrt 2$. – Sungjin Kim Sep 26 '18 at 15:28
• I just came up with a little stronger upper bound. I will edit. – Sungjin Kim Sep 26 '18 at 15:39
• I wonder under what assumptions if any can the square root term in the upper bound be replaced by $1+\epsilon$ – NiloS Sep 26 '18 at 15:50
• I put the meaning of $\ll$ on top. This notation is Vinogradov's notation. $\ll$ means the same of the big-Oh. – Sungjin Kim Sep 28 '18 at 20:35