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)
  • 1
    $\begingroup$ Here it is in oeis: oeis.org/A121497 $\endgroup$
    – jwc845
    Commented Sep 25, 2018 at 19:07
  • 7
    $\begingroup$ 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. $\endgroup$ Commented Sep 25, 2018 at 20:42
  • 1
    $\begingroup$ @QiaochuYuan According to your guess, $O(\frac{2^n}{\log n})$ is plausible since you began with the density. $\endgroup$ Commented Sep 26, 2018 at 4:51
  • 1
    $\begingroup$ 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}$. $\endgroup$ Commented Sep 26, 2018 at 4:53
  • 1
    $\begingroup$ Experimentally $O(2^n/(\log n))$ looks more likely than the form with the square root. $\endgroup$ Commented Sep 26, 2018 at 15:46

1 Answer 1


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.

Notations in this answer

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

Upper Bound (Added on 9/28)

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

  • 1
    $\begingroup$ 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? $\endgroup$ Commented Sep 26, 2018 at 15:26
  • 1
    $\begingroup$ This is very interesting problem. The number is by the way, came from $1/\sqrt 2$. $\endgroup$ Commented Sep 26, 2018 at 15:28
  • 1
    $\begingroup$ I just came up with a little stronger upper bound. I will edit. $\endgroup$ Commented Sep 26, 2018 at 15:39
  • $\begingroup$ I wonder under what assumptions if any can the square root term in the upper bound be replaced by $1+\epsilon$ $\endgroup$ Commented Sep 26, 2018 at 15:50
  • 3
    $\begingroup$ I put the meaning of $\ll$ on top. This notation is Vinogradov's notation. $\ll$ means the same of the big-Oh. $\endgroup$ Commented Sep 28, 2018 at 20:35

You must log in to answer this question.

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