\documentclass[11pt]{amsart} \usepackage[margin=1.1in]{geometry} \usepackage{amsmath,amssymb,amsthm} \usepackage{booktabs} \usepackage[hidelinks]{hyperref} \newtheorem{theorem}{Theorem} \newtheorem{proposition}{Proposition} \theoremstyle{remark} \newtheorem{remark}{Remark} \newcommand{\ord}{\operatorname{ord}} \begin{document} \title{A lower bound $0.11096505$ for Romanoff's constant} \author{David Niedbala Giraudin} \address{Independent researcher, Meaux, France} \urladdr{\href{https://orcid.org/0009-0009-1526-1178}{https://orcid.org/0009-0009-1526-1178}} \date{15 November 2026} \subjclass[2020]{11P32, 11N36, 11Y16} \keywords{Romanoff's theorem, primes and powers of two, Selberg sieve, computer-assisted proof} \begin{abstract} Let $d$ be the lower density of the integers of the form $p+2^a$ with $p$ prime and $a\ge 1$. We prove $d\ge 0.11096505$, unconditionally. The previous best unconditional bound is $d\ge 0.110825$, due to Tomar. The proof is Tomar's method, with the same analytic inputs, applied to a different modulus of the same period $27720$; the bound is certified in exact rational arithmetic by Tomar's checking program, with changes that only make the computation faster and that we verify against the original program. \end{abstract} \maketitle \section{Result} For a positive integer $n$ let $r(n)$ be the number of pairs $(p,a)$ with $p$ prime, $a\ge1$ and $n=p+2^a$, and \[ d=\liminf_{N\to\infty}\frac1N\,\#\{n\le N:\ r(n)>0\}. \] Romanoff proved $d>0$ \cite{Rom34}. Explicit lower bounds are $0.0868$ (Chen and Sun \cite{CS04}), $0.0936275$ (Habsieger and Sivak-Fischler \cite{HSF10}), $0.107648$ (Elsholtz and Schlage-Puchta \cite{ESP18}, recomputed as $0.10788$ by Johnston and Trudgian \cite{JT26}) and $0.110825$ (Tomar \cite{Tom26}). In Tao's list of optimization constants \cite{Tao} this is the lower bound for $C_{45}$. \begin{theorem}\label{thm:main} We have $d\ge 0.11096505$. \end{theorem} The theorem is unconditional: it uses exactly the analytic inputs of Theorem~1.1 of \cite{Tom26}, namely the per-class sieve bound with the constant $8$ quoted by Johnston and Trudgian from \cite[(28)]{ESP18}, the prime number theorem in arithmetic progressions to a fixed modulus, Pintz's bound for the series $R_0$ \cite{Pin06}, and Pintz's inequality for nonnegative integers. It does not use the conditional input of Theorem~1.2 of \cite{Tom26}. \section{The method} We recall the method of \cite{Tom26}, which refines \cite{ESP18}; we refer to \cite{Tom26} for the proofs. Let $l$ be an odd squarefree integer and $P$ the order of $2$ modulo $l$. For a residue class $k\bmod l$ let $U_k=\{r\in\mathbb Z/P\mathbb Z:(k-2^r,l)=1\}$ and $s_k=|U_k|$. In each class the first moment of $r(n)$ is given by the prime number theorem in progressions, and the second moment is bounded by the per-class sieve bound, applied to the pairs $p_1+2^{a_1}=p_2+2^{a_2}$ grouped by $(a_1\bmod P,a_2\bmod P)$, together with upper bounds $B_g$ ($g\mid P$) for the singular series. The part of the singular series that is not computed is bounded only through its total mass $\vartheta$, and the worst distribution of this mass over the divisors of $P$ is taken. With Pintz's inequality in each class this gives (\cite[Proposition~4.2]{Tom26}) \[ d\ \ge\ \min_\beta\ \frac{\nu}{l}\sum_{k:\,s_k>0}\biggl(\frac{2s_k}{j_k+1}-\frac{8\kappa}{j_k(j_k+1)}\Bigl(\sum_{g\mid P}B_gS_{k,g}+\sum_{g\mid P}g\,\beta_g\,S_{k,g}\Bigr)\biggr), \] where $S_{k,g}=\sum_{a\bmod g}|U_k\cap(a+g\mathbb Z)|^2$, $\kappa$ and $\nu$ are explicit constants depending on $l$, the $j_k\ge1$ are arbitrary integers, and $\beta$ runs through the vertices of the simplex $\{\beta_g\ge0,\ \sum_g\beta_g\le\vartheta\}$. The bound depends on the modulus $l$. Tomar uses \[ l_3=3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\cdot29\cdot31\cdot37\cdot41\cdot43\cdot73\cdot241, \] with period $P=27720$, and obtains $0.110825$. We use \[ l_E=3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\cdot29\cdot31\cdot37\cdot41\cdot43\cdot73\cdot89\cdot127, \] that is, $l_3$ without $241$ and with $89$ and $127$, for which $\ord_{89}(2)=11$ and $\ord_{127}(2)=7$. The period is again $P=27720$. \section{The computation} The computation uses the structure of \cite[Appendix~A]{Tom26} and the certificate format \texttt{r45a-u3f} of its checking program. The base primes are $3,5,7,11,13,17,31$ (period $120$; their nonempty patterns fall into $822$ rotation orbits). The core primes are $41,19,73,37$ (period $360$). The remaining primes are treated as independent components: $43,29,127$ for the factor $7$ of the period (orders $14,28,7$) and $23,89$ for the factor $11$ (orders $11,11$). The program checks that the orders of $2$ modulo these primes come from proven complete factorizations, that this decomposition is valid, that the multiplicities of the combined patterns ($380$ of them) add up to the product of the independent primes, and that the total weight equals $l_E$. The singular series is bounded as in \cite[Section~5]{Tom26}, from the complete factorizations of $\Phi_t(2)$ for $t\le300$ and the known factorizations for $301\le t\le1200$. The program gives $T(0)\le1.179578218$ and a tail mass $\vartheta\le1.9583\cdot10^{-4}$. The Pintz indices $j_k$ range over $1,\dots,43$. The value at the vertex $\beta=0$ is $0.1110554\ldots$; the minimum over the $97$ vertices is at $\beta=\vartheta e_{27720}$, and the program checks in exact rational arithmetic that it is at least $0.11096505$. This proves Theorem~\ref{thm:main}. \subsection*{Changes to the checking program} Tomar's program \cite{Tom26} would need about $9.6$ hours on two cores for this certificate. We changed three things, all inside the \texttt{u3f} part of the program, and an ancillary file lists them exactly. \begin{enumerate} \item In each base orbit, identical rows of the core enumeration (the same mask on $\mathbb Z/360\mathbb Z$) are merged and their weights added. Every quantity computed from a row depends on the row only through its mask and is linear in its weight, so the sums do not change; the program checks that the total weight is unchanged. \item The weighted sums over the rows are computed in $64$-bit integers, with an asserted bound against overflow, instead of in floating point; the original bound that makes the computed $S_{k,g}$ exact is kept. \item The base orbits can be processed in slices, with the exact partial sums written to a file after each orbit, and the slices are recombined exactly; the recombination repeats all the checks of the original program and checks that the slices cover every orbit exactly once. \end{enumerate} With these changes the computation took about three hours on two cores. \subsection*{Checks} \begin{itemize} \item On Tomar's test certificate \texttt{test\_cert\_t1\_u3f}, the changed program gives $0.107200250$, the value of Tomar's log, both in one run and in two slices recombined. \item Tomar's original program, changed only so that it processes a slice of orbits and writes its exact sums, and the changed program were run on the certificate of this note for the slices of orbits $0$--$1$ (the most expensive), $410$--$413$ and $815$--$821$ (the least expensive). The exact sums agree in all $2717$, $1747$ and $292$ integers respectively. \item The original program accepts the certificate of this note: all its checks up to the evaluation of the orbits pass. \end{itemize} The original program has not been run end to end on this certificate, and the computation has not been formalized in Lean (Tomar's bound $0.110825$ is also proved in Lean \cite{Tom26}). \section{Ancillary files} The directory \texttt{anc/} contains the following files. \begin{itemize} \item The certificate \texttt{cert\_E\_27720.json}. \item The changed program \texttt{check\_r45u3f\_patched.py} and the list of its changes. \item The exact partial sums \texttt{partial\_sums\_0\_822.json}, and the logs of the run and of the recombination. \item Tomar's factorization data \texttt{fac300\_41e4cdd6.json} and \texttt{fac1200\_fdb\_af082adc.json}. \item For the comparison with the original program: \texttt{chk\_orig\_tranche.py}, its list of changes, the slice sums and \texttt{cmp.py}. \item The Apache License 2.0, under which Tomar's program is distributed. \end{itemize} To reproduce, with Python~3, \texttt{python-flint} and \texttt{numpy}: \begin{verbatim} TRANCHE=0:822 SORTIE=s.json python3 -I check_r45u3f_patched.py \ fac300_41e4cdd6.json cert_E_27720.json 3000000 \ fac1200_fdb_af082adc.json 1200 --workers 2 RECOMBINE=s.json python3 -I check_r45u3f_patched.py \ fac300_41e4cdd6.json cert_E_27720.json 3000000 \ fac1200_fdb_af082adc.json 1200 --claim 0.11096505 \end{verbatim} \section*{Acknowledgements and use of AI} The method and the checking program are those of T.~S.~Tomar \cite{Tom26}, building on Elsholtz and Schlage-Puchta \cite{ESP18}, Johnston and Trudgian \cite{JT26} and Pintz \cite{Pin06}. The mathematics, the computations and the writing were produced with Claude (Anthropic) under the author's direction. The result has not yet been examined by a professional mathematician. \begin{thebibliography}{99} \bibitem{CS04} Y.-G. Chen and X.-G. Sun, \emph{On Romanoff's constant}, J. Number Theory \textbf{106} (2004), 275--284. \bibitem{ESP18} C. Elsholtz and J.-C. Schlage-Puchta, \emph{On Romanov's constant}, Math. Z. \textbf{288} (2018), 713--724. \bibitem{HSF10} L. Habsieger and J. Sivak-Fischler, \emph{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) \textbf{95} (2010), 557--566. \bibitem{JT26} D. R. Johnston and T. Trudgian, \emph{An update on the Linnik--Goldbach problem}, arXiv:2605.17825v2 (2026). \bibitem{Pin06} J. Pintz, \emph{A note on Romanov's constant}, Acta Math. Hungar. \textbf{112} (2006), 1--14. \bibitem{Rom34} N. P. Romanoff, \emph{\"Uber einige S\"atze der additiven Zahlentheorie}, Math. Ann. \textbf{109} (1934), 668--678. \bibitem{Tao} T. Tao et al., \emph{Optimization constants in mathematics}, constant $C_{45}$, \url{https://teorth.github.io/optimizationproblems/constants/45a.html}. \bibitem{Tom26} T. S. Tomar, \emph{New lower bounds for Romanoff's constant}, version 11 (2026), doi:10.5281/zenodo.23715955; programs at \url{https://github.com/tejasvi/romanoff-constant}, tag v11. \end{thebibliography} \end{document}