New lower bounds for Romanoff's constant

A mix of human-written and AI-generated textHuman understanding: all partsmath.NT — Number Theorymath.OC — Optimization and Control

Contributed by Tejasvi Singh Tomar ↗

Version 1 / Nov 15, 2026 / CC BY 4.0

Abstract

Romanoff proved in 1934 that the integers of the form p+2ap+2^a, with pp prime and a≥1a\ge1, have positive lower density dd. We prove that d≥0.110825d\ge0.110825 and, conditionally on an upper bound for prime pairs that Johnston and Trudgian derive from Lichtman's work on primes in arithmetic progressions, that d≥0.119178d\ge0.119178; the best lower bound so far was 0.107880.10788. The proof refines the method of Elsholtz and Schlage-Puchta, which bounds the second moment of the number of representations in each residue class modulo a fixed integer. Both bounds are certified by computer and also proved in the Lean proof assistant, with the analytic inputs as hypotheses.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23715954

References

  1. E. Bombieri and H. Davenport, Small differences between prime numbers , Proc. Roy. Soc. Ser. A 293 (1966), 1--18.
  2. Y. Chen, X. Dai and H. Li, Some results on a conjecture of de Polignac about numbers of the form p+2kp+2^k , arXiv:2402.06644 (2024).arXiv
  3. Y.-G. Chen and X.-G. Sun, On Romanoff's constant , J. Number Theory 106 (2004), 275--284.
  4. G. M. Del Corso, I. Del Corso, R. Dvornicich and F. Romani, On computing the density of integers of the form 2n+p2^n+p , Math. Comp. 89 (2020), 2365--2386.
  5. C. Elsholtz and J.-C. Schlage-Puchta, On Romanov's constant , Math. Z. 288 (2018), 713--724.
  6. P. Erdős, On integers of the form 2k+p2^k+p and some related problems , Summa Brasil. Math. 2 (1950), 113--123.
  7. The FLINT team, FLINT: Fast Library for Number Theory , https://flintlib.org.link
  8. L. Habsieger and X.-F. Roblot, On integers of the form p+2kp+2^k , Acta Arith. 122 (2006), 45--50.
  9. H. Halberstam and H.-E. Richert, Sieve Methods , Academic Press, London, 1974.
  10. L. Habsieger and J. Sivak-Fischler, An effective version of the Bombieri--Vinogradov theorem, and applications to Chen's theorem and to sums of primes and powers of two , Arch. Math. (Basel) 95 (2010), 557--566.
Show all 22 referencesShow fewer references
  1. D. R. Johnston and T. Trudgian, An update on the Linnik--Goldbach problem , arXiv:2605.17825v2 (2026).arXiv
  2. L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language , in: Automated Deduction -- CADE 28, Lecture Notes in Comput. Sci. 12699 , Springer, 2021, 625--635.
  3. J. D. Lichtman, Primes in arithmetic progressions to large moduli, and Goldbach beyond the square-root barrier , arXiv:2309.08522 (2023).arXiv
  4. The mathlib Community, The Lean mathematical library , in: Proc. 9th ACM SIGPLAN Int. Conf. Certified Programs and Proofs (CPP 2020), 2020, 367--381.
  5. J. Pintz, A note on Romanov's constant , Acta Math. Hungar. 112 (2006), 1--14.
  6. V. R. Pratt, Every prime has a succinct certificate , SIAM J. Comput. 4 (1975), 214--220.
  7. D. J. Platt and T. S. Trudgian, Linnik's approximation to Goldbach's conjecture, and other problems , J. Number Theory 153 (2015), 54--62.
  8. F. Romani, Computations concerning primes and powers of two , Calcolo 20 (1983), 319--336.
  9. N. P. Romanoff, Über einige Sätze der additiven Zahlentheorie , Math. Ann. 109 (1934), 668--678.
  10. J. G. van der Corput, On de Polignac's conjecture , Simon Stevin 27 (1950), 99--105.
  11. J. Wu, Chen's double sieve, Goldbach's conjecture and the twin prime problem , Acta Arith. 114 (2004), 215--273.
  12. A. Yoo, An improved upper bound on Romanoff's constant , 2026, https://github.com/andrew-yoo/romanoff.link

Version history

  1. v1 · 13 pagesSubmitted by Tejasvi Singh TomarPublished on Zenodo: https://doi.org/10.5281/zenodo.23715954CurrentNov 15, 2026