Romanov's theorem

Romanov initially stated that he had proven the statements "In jedem Intervall (0, x) liegen mehr als ax Zahlen, welche als Summe von einer Primzahl und einer k-ten Potenz einer ganzen Zahl darstellbar sind, wo a eine gewisse positive, nur von k abhängige Konstante bedeutet" and "In jedem Intervall (0, x) liegen mehr als bx Zahlen, weiche als Summe von einer Primzahl und einer Potenz von a darstellbar sind. Hier ist a eine gegebene ganze Zahl und b eine positive Konstante, welche nur von a abhängt".[1] These statements translate to "In every interval ${\displaystyle (0,x)}$ there are more than ${\displaystyle \alpha x}$ numbers which can be represented as the sum of a prime number and a k-th power of an integer, where ${\displaystyle \alpha }$ is a certain positive constant that is only dependent on k" and "In every interval ${\displaystyle (0,x)}$ there are more than ${\displaystyle \beta x}$ numbers which can be represented as the sum of a prime number and a power of a. Here a is a given integer and ${\displaystyle \beta }$ is a positive constant that only depends on a" respectively. The second statement is generally accepted as the Romanov's theorem, for example in Nathanson's book.[2]

Precisely, let ${\displaystyle d(x)={\frac {\left\vert \{n\leq x:n=p+2^{k},p\ {\textrm {prime,}}\ k\in \mathbb {N} \}\right\vert }{x}}}$ and let ${\displaystyle {\underline {d}}=\liminf _{x\to \infty }d(x)}$, ${\displaystyle {\overline {d}}=\limsup _{x\to \infty }d(x)}$. Then Romanov's theorem asserts that ${\displaystyle {\underline {d}}>0}$.[3]

Alphonse de Polignac wrote in 1849 that every odd number larger than 3 can be written as the sum of an odd prime and a power of 2. (He soon noticed a counterexample, namely 959.)[4] This corresponds to the case of ${\displaystyle a=2}$ in the original statement. The counterexample of 959 was, in fact, also mentioned in Euler's letter to Christian Goldbach,[5] but they were working in the opposite direction, trying to find odd numbers that cannot be expressed in the form.

In 1934, Romanov proved the theorem. The positive constant ${\displaystyle \beta }$ mentioned in the case ${\displaystyle a=2}$ was later known as Romanov's constant.[6] Various estimates on the constant, as well as ${\displaystyle {\overline {d}}}$, has been made. The history of such refinements are listed below.[3] In particular, since ${\displaystyle {\overline {d}}}$ is shown to be less than 0.5 this implies that the odd numbers that cannot be expressed this way has positive lower asymptotic density.

Refinements of ${\displaystyle {\overline {d}}}$ and ${\displaystyle {\underline {d}}}$

Year	Lower bound on ${\displaystyle {\underline {d}}}$	Upper bound on ${\displaystyle {\overline {d}}}$	Prover	Notes
1950		${\displaystyle 0.5-5.06\times 10^{-80}}$[lower-alpha 1]	Paul Erdős	;[7] First proof of infinitely many odd numbers that are not of the form ${\displaystyle 2^{k}+p}$ through an explicit arithmetic progression
2004	0.0868		Chen, Xun	[8]
2006	0.0933	0.49094093[lower-alpha 2]	Habsieger, Roblot	;[9] Considers only odd numbers; not exact, see note
2006	0.093626		Pintz	;[6] originally proved 0.9367, but an error was found and fixing it would yield 0.093626
2010	0.0936275		Habsieger, Sivak-Fischler	[10]
2018	0.107648		Elsholtz, Schlage-Puchta

Analogous results of Romanov's theorem has been proven in number fields by Riegel in 1961.[11] In 2015, the theorem was also proven for polynomials in finite fields.[12] Also in 2015, an arithmetic progression of Gaussian integers that are not expressible as the sum of a Gaussian prime and a power of 1+i is given.[13]