\documentclass[11pt]{article} \usepackage[margin=2.6cm]{geometry} \usepackage{amsmath,amssymb,amsthm} \usepackage[hidelinks]{hyperref} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{corollary}{Corollary} \theoremstyle{remark} \newtheorem{remark}{Remark} \newcommand{\ord}{\operatorname{ord}} \title{An upper bound $0.4893562$ for the upper density of the integers $p+2^k$} \author{David Niedbala Giraudin} \date{17 November 2026} \begin{document} \maketitle \begin{abstract} Let $A$ be the set of odd integers of the form $p+2^k$ with $p$ prime and $k\ge 0$. We prove $\overline{d}(A)<0.489356157186869$, improving the bound $0.489440909905826$ announced by Patankar in November 2026. The proof uses the finite obstruction inequality of Erd\H{o}s, as in the work of Habsieger--Roblot, Chen--Dai--Li, Griego, Yoo, Salavatov and Patankar, together with a simple averaging lemma: any prime may be added to the obstruction set, whatever the multiplicative order of $2$ modulo it, at the cost of averaging over its residue classes. Adding all odd primes below $200\,000$ to Patankar's $59$-prime certificate gives the bound. Starting instead from Salavatov's $51$-prime certificate, whose base histogram we rebuilt, gives $\overline{d}(A)<0.489419333025262$, which also improves the previous record. The certificates are exact rational computations and are provided with the verification programs. \end{abstract} \section{Statement} Let $A=\{n\text{ odd}:\ n=p+2^k \text{ for some prime } p \text{ and some } k\ge 0\}$ and let $\overline{d}(A)$ be its upper asymptotic density. Erd\H{o}s~\cite{E} proved $\overline{d}(A)<1/2$; the explicit bound was lowered to $0.4909$ by Habsieger and Roblot~\cite{HR}, to $0.490341088858244$ by Chen, Dai and Li~\cite{CDL}, to $0.490249407811155$ by Griego~\cite{G}, to $0.490180063290061$ by Yoo~\cite{Y}, to $0.489481743486002$ by Salavatov~\cite{S} and to $0.489440909905826$ by Patankar~\cite{P}. This is the upper bound for the constant $C_{45}$ of Tao's list of optimization constants~\cite{T}. \begin{theorem}\label{thm:main} $\overline{d}(A) < 0.489356157186869$. \end{theorem} \begin{theorem}\label{thm:second} $\overline{d}(A) < 0.489419333025262$, with a certificate whose base histogram we rebuilt from the residue conditions with Salavatov's generator. \end{theorem} \section{The obstruction inequality} For a finite set $P$ of odd primes put $M=\prod_{q\in P}q$, $T=\operatorname{lcm}_{q\in P}\ord_q(2)$ and, for $a\bmod M$, \[ \nu(a)=\#\{r\bmod T:\ \gcd(a-2^r,M)=1\}. \] \begin{lemma}[Erd\H{o}s; see \cite{HR,CDL,G}]\label{lem:E} For every $\lambda\in(0,\log 2]$, \[ \overline{d}(A)\ \le\ \sum_{a\bmod M}\min\Bigl(\frac{1}{2M},\ \frac{\nu(a)}{T\,\varphi(M)\,\lambda}\Bigr). \] \end{lemma} \begin{proof}[Sketch] The odd integers $n\equiv a\pmod M$ have density $1/(2M)$. If $n=p+2^k$ with $n\equiv a$ and $p\nmid M$, then $k\bmod T$ lies in the set counted by $\nu(a)$, and by the prime number theorem in arithmetic progressions the number of such $n\le x$ is at most $(1+o(1))\,\nu(a)\,x/(T\varphi(M)\log 2)$. The finitely many $p\mid M$ contribute density $0$. Replacing $\log 2$ by a smaller $\lambda$ only increases the bound. \end{proof} We take $\lambda=2\sum_{j<60}\frac{1}{(2j+1)3^{2j+1}}<\log 2$. \section{An averaging lemma} Write $P=B\sqcup Q$, where $B$ is a \emph{base} for which the histogram of $\nu_0(a_0)=\#\{r\bmod T_0:\gcd(a_0-2^r,M_0)=1\}$ over $a_0\bmod M_0$ is known exactly ($M_0=\prod_B q$, $T_0=\operatorname{lcm}_B\ord_q(2)$). Split $Q$ into groups $Q_d=\{q\in Q:\ord_q(2)=d\}$. For $q\in Q_d$ the class $a\bmod q$ either lies outside the subgroup $\langle 2\rangle$ of $(\mathbb Z/q)^\times$ or is $0$ (this happens for $q-d$ classes), and then it excludes no exponent; or $a\equiv 2^{c}\pmod q$ for a unique $c\bmod d$, and then it excludes exactly the exponents $r\equiv c\pmod d$. For a group $Q_d$ let $j\in\{0,\dots,d\}$ be the number of distinct excluded classes modulo $d$; its law over the $\prod_{Q_d}q$ choices is the occupancy law $\pi_d(j)$, computed by the recursion of Griego~\cite{G}. \begin{lemma}\label{lem:avg} Let $\kappa=M/(T_0\,\varphi(M)\,\lambda)$, and let $H=\prod_d (d-j_d)/d$ with independent $j_d\sim\pi_d$. Then the right-hand side of Lemma~\ref{lem:E} is at most \[ \frac{1}{M_0}\sum_{a_0\bmod M_0}\ \mathbb E\Bigl[\min\Bigl(\frac12,\ \kappa\,\nu_0(a_0)\,H\Bigr)\Bigr]. \] If every $d$ is prime to $T_0$ and to the other group orders, this is an equality. \end{lemma} \begin{proof} Multiply the summand of Lemma~\ref{lem:E} by $M$; it becomes $\min(\frac12,\nu(a)M/(T\varphi(M)\lambda))$ and each class has weight $1/M$. Fix one group $Q_d$ and all the other coordinates of $a$ (its class modulo $M/\prod_{Q_d}q$). Let $T'=\operatorname{lcm}(T_{\mathrm{rest}},d)$ and let $R$ be the set of $r\bmod T'$ that survive all other primes, so that $|R|=(T'/T_{\mathrm{rest}})\,\nu_{\mathrm{rest}}$. The classes of the block differ only by the tuple $(c_q)_{q\in Q_d}$ (with ``no exclusion'' as a possible value), and $\nu=\#\{r\in R:\ r\not\equiv c_q \ (\bmod d)\ \forall q\}$. Group the classes of the block by the set $J\subset\mathbb Z/d$ of excluded classes. The law of the tuple is invariant under permutations of $\mathbb Z/d$, so, given $|J|=j$, the set $J$ is uniform among the $j$-subsets of $\mathbb Z/d$, and \[ \mathbb E\bigl[\nu \bigm| |J|=j\bigr]=|R|-\sum_{r\in R}\Pr\bigl(r\bmod d\in J\bigm| |J|=j\bigr)=|R|\Bigl(1-\frac jd\Bigr). \] Since $x\mapsto \min(\frac12,x)$ is concave, replacing $\nu$ by this conditional mean in each sub-block does not decrease the sum (Jensen). Doing this group after group (each step uses only that the classes of the current group are permuted by $\mathbb Z/d$, never independence from the base) and collecting the factors $M/(T\varphi(M))$ gives the statement. When $d$ is prime to everything else, $r\bmod d$ is an independent CRT coordinate, $\nu=\nu_{\mathrm{rest}}\cdot(d-j)$ exactly, and there is no loss. \end{proof} \begin{remark} The previous certificates added outside the base only primes whose order is prime to $T_0$ and to the other cluster orders (``clusters''); for them Lemma~\ref{lem:avg} is the exact cluster formula of Griego. Lemma~\ref{lem:avg} allows every prime. The gain from a prime $q$ of order $d$ is small when $d$ is large or $d/q$ is small; the largest single gains come from $71$ ($d=35$), $79$ ($d=39$), $337$ ($d=21$) and $103$ ($d=51$). \end{remark} \begin{lemma}\label{lem:round} The bound of Lemma~\ref{lem:avg} does not decrease if (i) two atoms $(h_1,w_1),(h_2,w_2)$ of the law of $H$ are replaced by one atom $\bigl((w_1h_1+w_2h_2)/(w_1+w_2),\,w_1+w_2\bigr)$; (ii) an atom $h$ is replaced by some $h'\ge h$; (iii) a weight is lowered and the missing mass is counted with the value $\frac12$; (iv) several values $\nu_0$ are replaced by their weighted mean; (v) classes of the base are counted $\frac12$. \end{lemma} \begin{proof} (i) and (iv) are Jensen's inequality for the concave function $x\mapsto\min(\frac12,x)$; (ii) holds since the function is nondecreasing; (iii) and (v) since it is at most $\frac12$. Each property is preserved when the law is multiplied by an independent factor, because $h\mapsto\min(\frac12,\kappa\nu h f)$ is again concave and nondecreasing. \end{proof} \section{The computation} \paragraph{Base.} For Theorem~\ref{thm:main} we use the $34$-prime base and the $25$ cluster primes of Patankar's certificate~\cite{P}, with his published histogram of $\nu_0$ (classes with $\nu_0\le 1\,528\,627$, $1\,495\,742$ lines, SHA-256 \texttt{612e6348\ldots 4b8d}); the classes above the cut are counted $\frac12$. We did not regenerate this histogram: its generation needs about $170$\,GB of memory. For Theorem~\ref{thm:second} we use the $24$-prime base and the $27$ cluster primes of Salavatov's $51$-prime certificate~\cite{S}; we rebuilt its histogram with his generator (about $97$ minutes on one core) and obtained the published SHA-256 \texttt{67943dd5\ldots 6b6f} ($56\,798$ lines); its total and its first two moments agree with the values computed from the residue conditions. In both cases the histogram is merged into $5000$ blocks of consecutive values (Lemma~\ref{lem:round}(iv)); the block files are among the ancillary files. \paragraph{Added primes.} All odd primes below $200\,000$ that are not already used, grouped by order together with the cluster primes; this gives $16\,769$ groups and $17\,983$ primes in all for Theorem~\ref{thm:main}. \paragraph{Arithmetic.} The law of $H$ is kept in fixed point with $2^{128}$ as unit: multipliers are rounded up, weights rounded down, the lost mass is counted $\frac12$, and after each group the atoms are merged on a logarithmic grid of $20\,000$ cells (Lemma~\ref{lem:round}). The final sum is computed with exact rationals. The resulting exact values are \begin{align*} S_1&=0.489356157186868706448607751256875\ldots,\\ S_2&=0.489419333025261548400130260082272\ldots, \end{align*} which gives Theorems~\ref{thm:main} and~\ref{thm:second}. \begin{remark} Starting from Salavatov's $54$-prime certificate, whose published histogram we did not rebuild (SHA-256 \texttt{e011429b\ldots f91c}), the same procedure gives $S=0.4893892273408777\ldots$, hence $\overline{d}(A)<0.489389227340878$. \end{remark} \paragraph{Checks.} (a) Without added primes, with Patankar's full histogram and without merging, the program reproduces his sum $0.48944090990582567951\ldots$ to $33$ digits, from above; with the block file instead of the full histogram it gives $0.4894409099312\ldots$, that is $2.5\cdot10^{-11}$ above. (b) On $80$ small configurations, including orders that share factors with $T_0$ and a range of values of $\lambda$, the exact sum of Lemma~\ref{lem:E}, computed by enumerating all classes, is at most the bound of Lemma~\ref{lem:avg}, which is at most the bound without the added primes. (c) A separate floating-point evaluation, with $80\,000$ atoms, gives $0.4893561484\ldots$ for Theorem~\ref{thm:main}, just below the certified value, as it should. (d) Without merging, the program and a separate program written with rational arithmetic give the same value to $33$ digits when the single prime $71$ is added to Patankar's certificate. \section*{Ancillary files} \texttt{cert.py} computes a bound from a configuration file and checks it against the announced value; run without arguments it treats \texttt{cfg\_theorem1.json} and \texttt{cfg\_theorem2.json} (about $12$ minutes each). \texttt{cfg\_remark\_f54.json} gives Remark~2 and \texttt{cfg\_check\_patankar.json} check (a). \texttt{selftest.py} is check (b). \texttt{make\_groups.py} rebuilds the block files \texttt{hist\_*\_groups.csv} from the published histograms. The files \texttt{*.S.json} give the exact sums, the \texttt{*.log} files the outputs of the runs, including the rebuild of Salavatov's $51$-prime histogram. \section*{Acknowledgements} The mathematics, the computations and the writing were produced with Claude (Anthropic) under the author's direction. The base histograms are those of Patankar and Salavatov, whose certificates build on those of Griego and Yoo. \begin{thebibliography}{9} \bibitem{CDL} Y.~Chen, X.~Dai, H.~Li, \emph{Some computational results on a conjecture of de Polignac about numbers of the form $p+2^k$}, J. Number Theory (2025), doi:10.1016/j.jnt.2024.07.004; arXiv:2402.06644. \bibitem{E} P.~Erd\H{o}s, \emph{On integers of the form $2^k+p$ and some related problems}, Summa Brasil. Math. \textbf{2} (1950), 113--123. \bibitem{G} S.~Griego, \emph{C45 Romanoff upper-density certificate}, GitHub (2026), \url{https://github.com/sebastian-griego/c45-romanoff-certificate}. \bibitem{HR} L.~Habsieger, X.-F.~Roblot, \emph{On integers of the form $p+2^k$}, Acta Arith. \textbf{122} (2006), 45--50. \bibitem{P} V.~Patankar, \emph{A 34-prime-base obstruction certificate for Romanoff's constant: $C_{45}<0.489440909905826$}, GitHub (2026), \url{https://github.com/vidigoat/optimization-records}, directory \texttt{tao/certificates/c45/v3}. \bibitem{S} R.~Salavatov, \emph{Romanoff's constant: $C_{45}<0.489481743486002$}, GitHub (2026), \url{https://github.com/fortunto2/romanoff-c45}. \bibitem{T} T.~Tao et al., \emph{Optimization constants in mathematics}, constant 45a, \url{https://teorth.github.io/optimizationproblems/constants/45a.html}. \bibitem{Y} A.~Yoo, \emph{An improved upper bound on Romanoff's constant}, GitHub (2026), \url{https://github.com/andrew-yoo/romanoff}, tag v3. \end{thebibliography} \end{document}