The density of numbers of the form $p + 2^k$

Question

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, 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-Schwarz 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.

Answer 1

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.

and

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

Answer 2

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.