On sums of a prime and a central binomial coefficient

Question

Let $\mathbb Z^+$ be the set of positive integers. In 1934, Romanoff proved that $$\liminf_{x\to+\infty}\frac{|\{n\le x:\ 2n+1=p+2^k\ \text{for some prime}\ p\ \text{and}\ k\in\mathbb Z^+\}|}x>0.$$ On the other hand, in 1950 van der Corput showed that $$\liminf_{x\to+\infty}\frac{|\{n\le x:\ 2n+1\not=p+2^k\ \text{for any prime}\ p\ \text{and}\ k\in\mathbb Z^+\}|}x>0.$$ These two results are well-known, and they have stimulated some further work.

For $n\in\mathbb Z^+$, the central binomial coefficient $\binom{2n}n=2\binom{2n-1}{n-1}$ is even. By Stirling's formula $n!\sim\sqrt{2\pi n}(n/e)^n$, we have $$\binom{2n}n=\frac{(2n)!}{(n!)^2}\sim \frac{4^n}{\sqrt{n\pi}}.$$

Motivated by the results of Romanoff and van der Corput, here I ask the following question.

QUESTION. Let $$S=\left\{p+\binom{2k}k:\ p\ \text{is an odd prime and}\ k\in\mathbb Z^+\right\},$$ and define $$s_1=\liminf_{x\to+\infty}\frac{|\{n\le x:\ 2n+1\in S\}|}x \ \ \text{and}\ \ s_2=\liminf_{x\to+\infty}\frac{|\{n\le x:\ 2n+1\not\in S\}|}x.$$ Is it true that both $s_1$ and $s_2$ are positive? Can one modify Romanoff's method or van der Corput's method to prove $s_1>0$ or $s_2>0$.

By the Prime Number Theorem, $\pi(x)\sim x/(\log x)$. Note also that $1/\log4>1/2$. Based on this and my computation, I conjecture that the two constants $s_1$ and $s_2$ are indeed positive.

Any comments are welcome!

Fedor Petrov · Accepted Answer · 2025-11-30 16:39:17Z

The limit (not only liminf) $s_1$ equals 0, i. e., $|S\cap [1,x]|=o(x)$.

The reason is that the central binomials are almost always divisible by 3, 5 etc (and by every specific prime). To be more precise, we have

Observation. for every fixed $p$ we have $\bigl|n\leqslant x: p\nmid{2n\choose n}\bigr|=o(x)$.

Proof. Recall that by Kummer's theorem $p$ does not divide ${n+k\choose k}$ if and only if the base $p$ expansions $n=\sum c_i p^i$ and $k=\sum b_i p^i$, $0\leqslant b_i,c_i\leqslant p-1$, satisfy $b_i+c_i\leqslant p-1$ for all $i$ (i.e., there are no carries if we sum up $n$ and $k$ in base $p$). For ${2n\choose n}$ this means that all base $p$ digits of $n$ must be less than $p/2$, there are at most $\lceil p/2\rceil^{1+\log_p x}=o(x)$ such numbers not exceeding $x$.

Thus, for every fixed $M$ the number of $n\leqslant x$ for which there exists prime $p<M$ not dividing ${2n\choose n}$ is $o(x)$. Fix $M$ and call such $n$ $M$-strange.

Counting numbers of the form $p+{2n\choose n}$ not exceeding $x$, we note that there exist $O(x/\log x)$ choices of $p$ and $o(\log x)$ choices of $M$-strange $n$. Totally this gives $o(x)$ numbers of the form $p+{2n\choose n}$ with $M$-strange $n$. For not $M$-strange $n$, the number $y=p+{2n\choose n}\leqslant x$ either satisfies $p\leqslant M$ (there are $O(\log x)$ such numbers), or $y$ does not have a prime divisor $q<M$, since $q$ divides ${2n\choose n}$ and does not divide $p$ (there are at most $x\cdot \prod_{p<M}(1-1/p)+o(x)$ such numbers $y$). Since the product $\prod_p (1-1/p)$ equals 0, we get that there are only $o(x)$ numbers less than $x$ of the form $p+{2n\choose n}$.

Stack Exchange Network

On sums of a prime and a central binomial coefficient

1 Answer 1

You must log in to answer this question.

On sums of a prime and a central binomial coefficient

1 Answer 1

You must log in to answer this question.

Related