¿Cuál es la suma de los coeficientes binomiales ${n\choose p}$ sobre números primos?

Question

Qué se sabe sobre el orden asintótico y/o el límite inferior y superior de la suma de los coeficientes binomiales

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

donde la suma corre sobre todos los primos $\le n$ ?

Actualización 12-Ago-2019 : Sungjin Kim ha demostrado que casi para todos los $n$ ,

$$ S_n \sim \frac{2^n}{\log(n/2)} $$ En la versión anterior teníamos $\log n$ en el denominador que no se ha corregido.

Valores reales: Mi cálculo dio el siguiente orden asintótico de $n$ y la relación $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)

Answer 1

Siguiendo el enfoque de Qiaochu Yuan, las desigualdades $$ \frac{2^n}{\log n} \ll S_n \ll \frac{2^n }{\log n} $$ parece plausible. El límite inferior es una conjetura, pero es posible demostrar el límite superior.

Anotaciones en esta respuesta

$T_n \sim \mathrm{B}(n,\frac12)$ es la distribución binomial.

$S_n=\sum_{p\leq n} \binom np$ sumado sobre $p$ de primera.

$\pi(y)=\sum_{p\leq y}1$ es la función de recuento de primos.

$A(n)\ll B(n)$ significa $|A(n)|\leq CB(n)$ para alguna constante absoluta $C>0$ .

Límite inferior (conjetura)

Fijar $x>0$ . Tenemos $$ 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}. $$ Dado que los coeficientes binomiales $\binom nk$ pico en $k=n/2$ y se reducen cuando $k$ está más lejos de $n/2$ , tomamos lo siguiente como límite inferior de la probabilidad.

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

Por la fórmula de Stirling, y $\log (1+t)=t-\frac{t^2}2+O(\frac1{t^3})$ para $|t|\leq 1/2$ tenemos $$ P\left(T_n=\lfloor \frac n2+x\sqrt n\rfloor\right)\sim \frac{2}{\sqrt{2\pi n}} e^{-2x^2}. $$

Si tenemos la siguiente conjetura (ver esta encuesta de Yildrim para más información), $$ \pi(\frac n2+x\sqrt n)-\pi(\frac n2-x\sqrt n)\sim \frac{2x\sqrt n}{\log n}, $$ entonces tenemos el límite inferior conjetural $$ \frac{4x\cdot 2^n}{e^{2x^2}\sqrt{2\pi}\log n} \lesssim S_n. $$

Límite superior (versión fácil)

Por La desigualdad de Hoeffding damos un límite de suma sobre los primos más alejados de $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}. $$ Para los primos cercanos a $n/2$ aplicamos la desigualdad de Brun-Titchmarsh, $$ 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}. $$ Por lo tanto, tenemos el límite superior $$ S_n\ll \frac{2^n\sqrt{\log\log n}}{\log n}. $$

Límite superior (añadido el 28 de septiembre)

Con más cuidado, podemos eliminar $\sqrt{\log\log n}$ del límite superior.

De nuevo, por la desigualdad de Hoeffding, $$ P\left(p \mathrm {\ is \ prime}, \ T_n=p, \ |T_n-\frac n2|>\sqrt{n \log\log n} \right) \ll \frac1{(\log n)^2}. $$

Para los primos en $|T_n-\frac n2|\leq\sqrt{n \log\log n} $ , considere los subintervalos $$ \frac n2 + x\sqrt n \leq p < \frac n2 + (x+1)\sqrt n $$ para enteros no negativos $x\leq \sqrt{\log\log n}$ primero.

Entonces los enteros negativos $-\sqrt{\log\log n}\leq x$ se tratan de forma similar.

El número de primos en este intervalo es por la desigualdad de Brun-Titchmarsh, $\ll \frac{\sqrt n}{\log n}$ , mientras que $$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}.$$

Obsérvese que la última asíntota sigue siendo válida si $|x|\leq \sqrt{\log\log n}$ . Entonces tenemos

$$ 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}. $$ Así, sumando sobre $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}. $$ Por lo tanto, obtenemos $$ S_n\ll \frac{2^n}{\log n}. $$

Actualización en 2019/3/4

Nilotpal Kanti Sinha y yo empezamos a trabajar en la redacción de un artículo sobre este tema. Aquí está el progreso actual. Las pruebas son demasiado largas para contenerlas aquí, pero la idea principal de dividir la suma en intervalos cortos está presente en esta respuesta. Para demostrar 1, necesitamos la estimación de la densidad cero de Huxley y su consecuencia sobre los primos en los intervalos cortos. (Capítulo 5 de esta nota de Angel Kumchev: https://tigerweb.towson.edu/akumchev/a5.pdf ).

1. Tenemos para casi todo $n$ , $$ S_n= \frac{2^n}{\log n}+O\left(\frac{2^n}{(\log n)^2}\right) \ \textrm{as }n\rightarrow \infty. $$

Aquí, casi todo significa que el número de $n\in [1,N]\cap \mathbb{Z}$ para el que falla la fórmula asintótica es $o(N)$ .

2. Tenemos $$ \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. $$

3. La declaración $\alpha>0$ implica que, hay $b>0$ y $N_0(b)>0$ tal que, $$ \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). $$