MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In 1934, Romanoff proved that the following set has positive lower density:

$$\displaystyle \mathcal{R}(x)= \{n \in \mathbb{N} : n \leq x, n = p + 2^k \}$$

where $p$ is a prime and $k \geq 0$ is a non-negative integer. In 2010 Lee proved the analogous result when powers of 2 are replaced by terms in the Fibonacci sequence. Very recently, Ballot and Luca generalized the above to arbitrary non-degenerate linear recurrences (Ballot, Christian, Luca, Florian, $\textit{On the sumset of the primes and a linear recurrence}$, Acta Arithmetica 161.1 (2013)).

The basic idea behind the proof is to define $r(n)$ to be the number of ways to write $n$ as the sum of a prime and a term in the linear recurrence considered, and simultaneously obtain a lower bound for $\displaystyle \sum_{n \leq x} r(n) \gg x$ and and upper bound for $\displaystyle \sum_{n \leq x} r(n)^2 \ll x$, and then apply the Cauchy-Schwartz inequality to obtain the desired result.

Thus, the nature of the proof does not yield an explicit constant. So there are two questions that remain unanswered:

1) Can one obtain an asymptotic for $\#\mathcal{R}(x)$? Is the natural density expected to exist at all?

2) Can one obtain an explicit constant for the lower bound $\#\mathcal{R}(x) \gg x$?

Thanks for any insights. It would already be insightful to obtain an answer to the above two inquiries for the case of Romanoff's theorem.

share|cite|improve this question
See also – Charles Jul 22 '15 at 13:56
up vote 7 down vote accepted

The density is expected to exist, but this seems difficult.

As for question 2, the first explicit lower bound for $\liminf \frac{1}{x}\#\mathcal{R}(x)$ was established by Chen and Sun. I think the most up to date results are due (independently) to Pintz and to Habsieger and Roblot. The relevant references are

Pintz, J. A note on Romanov's constant. Acta Math. Hungar. 112 (2006), no. 1-2, 1–14.


Habsieger, Laurent; Roblot, Xavier-François. On integers of the form $p+2^k$. Acta Arith. 122 (2006), no. 1, 45–50.

share|cite|improve this answer

Romani (Calcolo 20 (1983), 319 - 336) gave a heuristic argument leading to the conjecture that the asymptotic density should exist and should be about 0.434... . The basic idea of the heuristics is that the probability for the event $n=p+2^a$ there are some obvious congruence conditions, but that apart from these conditions these events behave like independent random variables. In this way one can not only obtain a guess for the density, but also a conjectural distribution for the number of integers for which the equation $n=p+2^a$ has exactly $k$ solutions.

share|cite|improve this answer

Your Answer


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.