Large gaps between Romanov numbers

Natural numbers representable as the sum of a prime and a power of two with a natural exponent are called Romanov numbers. The study of such numbers was initiated by L. Euler, C. Goldbach [3] and A. de Polignac [1, Th´eor`eme 2, IV]. In his 1934 work [10], N. Romanov proved
that the set of Romanov numbers has positive lower density, i.e., for some constant 𝛼 > 0 every interval [1, 𝑥] for 𝑥 ≥ 4 contains at least 𝛼𝑥 numbers representable as 𝑝 + 2𝑛. This result also generalizes to the case of powers of an arbitrary natural number 𝑎: 𝑝 + 𝑎𝑛, with a constant
depending on 𝑎. The main method of proof consists in combining the Cauchy–Bunyakovsky–Schwarz inequality with sieve methods. Romanov’s theorem admits many generalizations: for instance, G. Rieger [8] proved its analogue for number fields, I. Shparlinski and A. Weingartner [11] established the same result for polynomials over finite fields, and A. Radomskii [7] obtained a series of results on the number of representations of natural numbers as 𝑎 + 𝑏, where 𝑎 is an element of a sifted set (e.g., a prime or a sum of two squares of integers) and 𝑏 is taken from a more intricately structured set. In particular, the cited work contains results on sums 𝑝 + #𝐸(Fℓ), where 𝑝 and ℓ are primes, and #𝐸(Fℓ) is the number of points of a fixed elliptic curve 𝐸 over the field Fℓ.
Concerning odd numbers that are not Romanov numbers, P. Erd˝os [2] established in 1950 that the upper density of Romanov numbers does not exceed 1/2− 1/(2^(241)·3·5·7·13·17·241). The proof uses
covering systems of congruences to construct an explicit arithmetic progression with difference 2^241 ·3·5·7·13·17·241 that contains no Romanov numbers. In the same work, he formulated the conjecture on the unboundedness of the smallest modulus in a covering system, which received a negative answer only 63 years later in [5]. Erd˝os’s estimate was later lowered to 0.490491 by L. Habsieger and X.-F. Roblot [4].
The present work is also devoted to results about the complement of the set of Romanov numbers. Namely, lower bounds are proved for the length of the largest subinterval of [1,𝑋] containing no Romanov numbers. Theorem 2 provides a general method for obtaining such
lower bounds, depending on an arbitrary set 𝒫 consisting of prime numbers. The main result — Theorem 1 — is proved in two different ways: an elementary unconditional approach uses primitive prime divisors of the numbers 2𝑚−1, while the second approach relies on the Extended Riemann Hypothesis for the zeta functions of a certain family of number fields. The estimates obtained by these two approaches coincide.

1. de Polignac, A. 1849, “Recherches nouvelles sur les nombres premiers”, Comptes Rendus, vol. 29, pp. 397–401.

2. Erd˝os, P. 1950, “On integers of the form 2𝑘+𝑝 and some related problems”, Summa Brasiliensis Mathematicae, vol. 2, pp. 113–125.

3. Euler, L. 2016, “Letter to Christian Goldbach. 16.12.1752”, in Lemmermeyer, F. & Mattm¨uller, M. (eds.), Correspondence of Leonhard Euler with Christian Goldbach, Bernoulli-Euler-Gesellschaft, Basel, Opera Omnia IVA 4 (online edition).

4. Habsieger, L. & Roblot, X.-F. 2006, “On integers of the form 𝑝 + 2𝑘”, Acta Arithmetica, vol. 1, pp. 45–50.

5. Hough, B. 2015, “Solution of the minimum modulus problem for covering systems”, Annals of Mathematics, vol. 181, no. 1, pp. 361–382.

6. Lagarias, J.C. & Odlyzko, A.M. 1977, “Effective versions of the Chebotarev theorem”, Algebraic Number Fields, pp. 409–464.

7. Radomskii, A. 2025, “Variants of Romanoff’s theorem”, arXiv, arXiv:2504.09954.

8. Rieger, G.J. 1961, “Verallgemeinerung zweier S¨atze von Romanov aus der additiven Zahlentheorie”, Mathematische Annalen, vol. 144, pp. 49–55.

9. Roitman, M. 1997, “On Zsigmondy primes”, Proceedings of the American Mathematical Society, vol. 125, no. 7, pp. 1913–1919.

10. Romanoff, N.P. 1934, “ ¨Uber einige S¨atze der additiven Zahlentheorie”, Mathematische Annalen, vol. 109, no. 1, pp. 668–678.

11. Shparlinski, I.E. & Weingartner, A. 2017, “An explicit polynomial analogue of Romanoff’s theorem”, Finite Fields and Their Applications, vol. 44, pp. 22–33.

12. Tˆoyama, H. 1955, “A note on the different of the composed field”, K¯odai Mathematical Seminar Reports, vol. 7, pp. 43–44.