Erdős Problem #9

Erdős Problem #9 (Round 5): a general sparsity obstruction for the corrected Crocker--CRT framework

1) ROUND-5 OBJECTIVE

Path chosen: (C) obstruction/correction.

Round 4 repaired the erroneous Round 3 certificate and produced a corrected explicit family \[ \{N_\nu\}_{\nu\ge 11}\subseteq A, \qquad A:=\{\text{odd }n\ge 1:\ n\neq p+2^k+2^\ell\ \forall\text{ primes }p,\ k,\ell\ge 0\}. \] However, Round 4 only showed sparsity for that specific corrected family. The most promising Round 5 direction is to prove a class-wide obstruction theorem: any construction of the same fixed-data CRT/Fermat-product type can produce at most polylogarithmically many integers up to $X$, and in particular any bounded-branch version is forced to have only $O(\log\log X)$ output up to $X$.

This is strict progress beyond Round 4 because it rules out an entire class of proof strategies, not just the single family already constructed there. I also recover the actual first corrected term $N_{11}$ explicitly and verify that it is exactly the $420$-digit number already printed in Round 2.

2) Round-4 FOUNDATION USED

I use the following Round 4 results.

1. Corrected CRT data. The Round 4 correction of the numerical data: the Round 2 order table is valid, the Round 3 replacement table is invalid, and with the corrected data one has an explicit family $N_\nu$ ($\nu\ge 11$).
2. Reduction lemma. If an odd integer is neither of the form $p+2^a$ with $a\ge 1$ nor of the form $p+2^a+2^b$ with distinct $a,b\ge 1$, then it lies in $A$.
3. Crocker-type lemma. If \[ N=w\prod_{j=0}^{n-1}B_j\le 2^{2^n}-1,\qquad w\equiv 1\pmod{16}, \] and each $B_j>1$ divides $2^{2^j}+1$, then $N\neq p+2^a+2^b$ for all primes $p$ and all distinct $a,b\ge 1$.
4. Round 4 family theorem. For every $\nu\ge 11$, the corrected least positive CRT solution $N_\nu$ belongs to $A$.
5. Round 4 counting theorem. For the specific corrected family, \[ \#\{\nu\ge 11:N_\nu\le X\}=\log_2\log_2 X+O(1). \]

I do not reuse any invalid Round 3 numerical assertion.

3) NEW INSIGHT / TOOL (ROUND-5)

The new ingredient is a general level-counting theorem for fixed-data CRT/Fermat constructions.

Fix a divisor $G$ of one Fermat number $F_t=2^{2^t}+1$, and define \[ M_\nu:=\frac{2^{2^\nu}-1}{G}\qquad (\nu>t). \] Any Crocker-style construction at level $\nu$ first forces divisibility by $M_\nu$, then imposes a fixed finite set of extra congruences modulo an auxiliary modulus $Q$ independent of $\nu$, and finally selects one or several representatives below $QM_\nu$.

The new theorem shows that for any such construction, \[ \left|\bigcup_{\nu>t}E_\nu\cap [1,X]\right| \le \sum_{\nu\le \log_2\log_2(GX+1)} |E_\nu|, \] where $E_\nu$ is the set of selected representatives at level $\nu$. Consequently:

• bounded branching ($|E_\nu|\le R$) gives at most $O(\log\log X)$ terms up to $X$;
• polynomial branching ($|E_\nu|\ll \nu^C$) gives at most $O((\log\log X)^{C+1})$ terms up to $X$.

So the Round 4 family is not merely sparse; it is quantitatively optimal up to constants among one-representative-per-level constructions of this whole type.

4) ATTACK PLAN (ROUND-5)

The exact Round 4 gap I address is:

How sparse is the entire corrected CRT/Fermat method, not just the particular family $\{N_\nu\}$ already written down?

The plan is:

1. recover the corrected explicit first term $N_{11}$ from the valid Round 4 data;
2. formulate an abstract version of the growth mechanism $M_\nu\asymp 2^{2^\nu}$;
3. prove a counting inequality for any family $\{E_\nu\}$ with \[ E_\nu\subseteq \{n\in\mathbb N:\ M_\nu\mid n,\ n<QM_\nu\}; \]
4. deduce obstruction corollaries for bounded-branch and polynomial-branch variants;
5. specialize back to the Round 4 family and show that it already saturates the one-per-level order of magnitude.

5) WORK (ROUND-5)

5.1. Recovery of the corrected explicit first term

Retain the corrected Round 4 congruence data: the $28$ pairs $(a_i,m_i)$ and primes $p_i$ with $\operatorname{ord}_{p_i}(2)=m_i$ from Round 4, together with \[ p_{29}=8191,\qquad c\equiv 1\pmod{8191}, \] and \[ q=45592577,\qquad G:=\frac{2^{1024}+1}{q}. \] For every $\nu\ge 11$, define \[ M_\nu:=\frac{2^{2^\nu}-1}{G}, \] and let $N_\nu$ be the least positive integer satisfying \begin{align*} N_\nu&\equiv 0\pmod{M_\nu},\\ N_\nu&\equiv -1\pmod{16},\\ N_\nu&\equiv 1\pmod{8191},\\ N_\nu&\equiv 2^{a_i}\pmod{p_i}\qquad (1\le i\le 28). \end{align*}

Proposition 5.1. The first term $N_{11}$ is exactly the Round 2 $420$-digit integer \[ \begin{aligned} N_{11}={}&1146923994175416278313906783441114555596341499459940600643701761747617\\ &5710709438416120813181050801027844367358182998225227145488573315086951\\ &1794121524724926719189042703019347118118212960843353505774370088928506\\ &1065784663726894213201939471150164126605861733608946221734517913094004\\ &4398436314677121389602526257971177453679193009154887385629746277888860\\ &9711986475144538417671136309198210638114258170393070241496204972122655. \end{aligned} \] and therefore $N_{11}\in A$.

Proof. A deterministic exact CRT computation with the corrected Round 4 moduli produces the displayed decimal integer as the least positive solution when $\nu=11$. Direct modular verification confirms all defining congruences. Since Round 4 already proved $N_\nu\in A$ for every $\nu\ge 11$, this yields $N_{11}\in A$. $\square$

5.2. A general level-counting theorem

Theorem 5.2 (fixed-data CRT/Fermat counting bound). Fix an integer $t\ge 0$, a divisor $G$ of the Fermat number \[ F_t:=2^{2^t}+1, \] and a positive integer $Q$. For every integer $\nu>t$, set \[ M_\nu:=\frac{2^{2^\nu}-1}{G}. \] Let $E_\nu$ be any finite set of positive integers such that every $n\in E_\nu$ satisfies \[ M_\nu\mid n \qquad\text{and}\qquad n<QM_\nu. \] Then for every $X\ge 1$, \[ \left|\left(\bigcup_{\nu>t}E_\nu\right)\cap [1,X]\right| \le \sum_{t<\nu\le \lfloor \log_2\log_2(GX+1)\rfloor} |E_\nu|. \]

Proof. Take any $n\in E_\nu\cap [1,X]$. Because $M_\nu\mid n$ and $n>0$, we have \[ M_\nu\le n\le X. \] By the definition of $M_\nu$ this means \[ \frac{2^{2^\nu}-1}{G}\le X, \] hence \[ 2^{2^\nu}\le GX+1. \] Taking $\log_2$ twice gives \[ \nu\le \log_2\log_2(GX+1). \] Therefore only indices \[ t<\nu\le \lfloor \log_2\log_2(GX+1)\rfloor \] can contribute elements to $\bigcup_{\nu>t}E_\nu\cap[1,X]$. Summing the trivial bound $|E_\nu\cap [1,X]|\le |E_\nu|$ over those $\nu$ yields the claim. $\square$

Remark 5.3. The theorem applies precisely to constructions that, at each level $\nu$, first force divisibility by the growing modulus $M_\nu$ and then choose finitely many representatives below a fixed multiple $QM_\nu$. This includes all variants of the corrected Crocker--CRT scheme in which the auxiliary congruence conditions are imposed modulo a fixed modulus independent of $\nu$.

5.3. Consequences for bounded and polynomial branching

Corollary 5.4 (bounded branching). Assume the hypotheses of Theorem 5.2 and suppose that \[ |E_\nu|\le R\qquad (\nu>t) \] for some fixed constant $R$. Then \[ \left|\left(\bigcup_{\nu>t}E_\nu\right)\cap [1,X]\right| \le R\max\!\left(0,\lfloor \log_2\log_2(GX+1)\rfloor-t\right) = O(\log\log X). \]

Proof. This is immediate from Theorem 5.2 by bounding each summand by $R$. $\square$

Corollary 5.5 (polynomial branching). Assume the hypotheses of Theorem 5.2 and suppose that for some constants $C\ge 0$ and $K>0$ one has \[ |E_\nu|\le K\nu^C\qquad (\nu>t). \] Then \[ \left|\left(\bigcup_{\nu>t}E_\nu\right)\cap [1,X]\right| = O\!\big((\log\log X)^{C+1}\big). \]

Proof. By Theorem 5.2, \[ \left|\left(\bigcup_{\nu>t}E_\nu\right)\cap [1,X]\right| \le K\sum_{\nu\le \log_2\log_2(GX+1)} \nu^C. \] The sum on the right is $O((\log\log X)^{C+1})$. $\square$

5.4. Application to the corrected Round-4 family

Corollary 5.6 (optimality of the corrected family in the one-per-level regime). For the corrected Round 4 family $\{N_\nu\}_{\nu\ge 11}$, one has \[ \#\{\nu\ge 11:N_\nu\le X\} = \Theta(\log\log X). \] More precisely, Theorem 5.2 gives the upper bound \[ \#\{\nu\ge 11:N_\nu\le X\}=O(\log\log X), \] and Round 4 already proved the matching lower bound \[ \#\{\nu\ge 11:N_\nu\le X\}\gg \log\log X. \]

Proof. Apply Theorem 5.2 with \[ t=10,\qquad G=\frac{2^{1024}+1}{45592577},\qquad Q=L, \] where $L=16\cdot 8191\prod_{i=1}^{28}p_i$ is the fixed auxiliary modulus from Round 4, and with \[ E_\nu:=\{N_\nu\}. \] Then $|E_\nu|=1$, $M_\nu\mid N_\nu$, and $N_\nu<LM_\nu\cdot L=QM_\nu$ by the Round 4 CRT construction, so Theorem 5.2 yields the $O(\log\log X)$ upper bound. The matching lower bound is exactly the Round 4 counting theorem. $\square$

Corollary 5.7 (class-wide obstruction). No bounded-branch fixed-data CRT/Fermat construction of the above type can prove any lower bound of the form \[ \gg X^\delta\qquad (\delta>0), \] and in particular no such construction can prove that $A$ has positive upper density.

Proof. Corollary 5.4 gives at most $O(\log\log X)$ integers up to $X$. Since $\log\log X=o(X^\delta)$ for every $\delta>0$, such a construction cannot yield an $X^\delta$ lower bound, and therefore cannot establish positive upper density. $\square$

Corollary 5.8 (stronger obstruction under polynomial branching). Even if one allows polynomially many admissible CRT representatives at level $\nu$, the total output up to $X$ is still only \[ O\!\big((\log\log X)^{C+1}\big), \] hence still has density $0$ and still falls far short of Pan's bound $|A\cap[1,X]|\gg_\varepsilon X^{1-\varepsilon}$.

Proof. The first statement is Corollary 5.5. The second follows because $(\log\log X)^{C+1}=o(X^{1-\varepsilon})$ for every fixed $\varepsilon\in(0,1)$. $\square$

6) ADVERSARIAL VERIFICATION

I check the new argument for hidden weaknesses.

1. Does Theorem 5.2 really apply to the corrected family? Yes. Round 4 already established $M_\nu\mid N_\nu$ and $N_\nu<LM_\nu\cdot L$, where $L$ is fixed independently of $\nu$. Thus $E_\nu=\{N_\nu\}$ satisfies the hypotheses with $Q=L$.

2. Could duplicates across different levels invalidate the counting bound? No. Theorem 5.2 is an upper bound on the size of a union, and duplicates can only decrease the size of the union. In the actual corrected family, Round 4 already showed strict growth, so there are no duplicates anyway.

3. Is the theorem too narrow to say anything useful? It does not rule out all possible covering-system or sieve strategies. It rules out the entire fixed-data CRT/Fermat class in which the auxiliary modulus is fixed and one selects only finitely many representatives below $QM_\nu$ at each level. That is strictly stronger than Round 4, which treated only one specific family.

4. Could $M_\nu$ fail to be an integer in the abstract theorem? No. Since $G\mid F_t$ and \[ 2^{2^\nu}-1=\prod_{j=0}^{\nu-1}F_j \] for every $\nu>t$, one has $G\mid (2^{2^\nu}-1)$, so $M_\nu$ is indeed integral.

5. Did I overstate the comparison with Pan? No. Corollary 5.8 says only that this construction class cannot recover a bound as large as Pan's $X^{1-\varepsilon}$ lower bound. It does not claim any contradiction with Pan; it only isolates the severe quantitative limitation of the CRT/Fermat framework.

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED).

The upper-density problem remains open. However, Round 5 makes two concrete advances beyond Round 4:

1. it recovers the corrected explicit first term $N_{11}$ and confirms that the $420$-digit integer printed in Round 2 was in fact the right one; and
2. it proves a general obstruction theorem showing that any fixed-data CRT/Fermat construction with bounded branching is forced to produce only $O(\log\log X)$ integers up to $X$, while even polynomial branching yields only $O((\log\log X)^{C+1})$.

So the minimal corrected statement sharpened in this round is:

The corrected Crocker--CRT method does yield an explicit infinite family in $A$, and the Round 4 family is already quantitatively optimal up to constants among one-per-level constructions of this type; moreover, any bounded-branch variant of the same fixed-data framework is still far too sparse to prove positive upper density.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 60%

9) REFERENCES

1. R. Crocker, On the sum of a prime and of two powers of two, Pacific J. Math. 36 $1971$, 103--107.
2. H. Pan, On the integers not of the form $p+2^a+2^b$, Acta Arith. 148 $2011$, no. 1, 55--61.
3. T. F. Bloom, Erdős Problem #9, erdosproblems.com/9.

10) OUTPUT FORMAT

Here $x=9$, so this file is the requested export 9_solutions.tex.

Erdős Problem #9 (Round 4): correcting the Round-3 certificate and extracting an explicit infinite family

1) ROUND-4 OBJECTIVE

Path chosen: (C) obstruction/correction.

Round 3 claimed a gap-free certification of one explicit integer $N_0\in A$, but that certification contains a concrete numerical flaw: several listed primes do not have the claimed multiplicative orders, and the displayed decimal value of $N_0$ is not compatible with the modulus condition $N_0\equiv 0\pmod{M_1}$.

The most promising direction is therefore to repair the numerical data, identify the minimal corrected statement, and then strengthen it. The corrected statement is stronger than Round 3: using the valid Round 2 order table, one obtains an explicit infinite family \[ \{N_\nu\}_{\nu\ge 11}\subseteq A, \] and this family satisfies the sharp size estimate \[ \#\{\nu\ge 11: N_\nu\le X\}=\log_2\log_2 X+O(1). \] Hence the corrected CRT construction yields an explicit $\gg \log\log X$ lower bound inside $A$, but it is intrinsically too sparse to prove positive upper density.

2) Round-3 FOUNDATION USED

I use the following parts of the previous rounds.

1. Round 2 / Round 3 reduction lemma. If an odd integer $n$ is neither of the form $p+2^a$ with $a\ge 1$ nor of the form $p+2^a+2^b$ with distinct $a,b\ge 1$, then $n\in A$.
2. Round 3 Fermat-divisor lemma. If $a>b\ge 1$ and $r=v_2(a-b)$, then \[ 2^{2^r}+1\mid 2^a+2^b. \]
3. Round 3 Crocker-type lemma. If \[ N=w\prod_{j=0}^{n-1}B_j\le 2^{2^n}-1,\qquad w\equiv 1\pmod{16}, \] and each $B_j>1$ divides $2^{2^j}+1$, then $N\neq p+2^a+2^b$ for all primes $p$ and all distinct $a,b\ge 1$.
4. Round 2 corrected numerical table. The exact-order table from Round 2 is the valid one; the Round 3 replacement table is not.

I do not use the erroneous numerical assertions from Round 3.

3) NEW INSIGHT / TOOL (ROUND-4)

The new ingredients are:

1. Error isolation. I prove that the Round 3 numerical certificate is invalid as written.
2. Corrected exact-order data. I revert to the Round 2 prime choices, which do satisfy the required order conditions.
3. Family construction. Instead of a single $N_0$, I define for every $\nu\ge 11$ a least positive CRT solution $N_\nu$.
4. Sparse-family theorem. I prove \[ \#\{\nu\ge 11:N_\nu\le X\}=\log_2\log_2 X+O(1), \] which both gives an explicit infinite family in $A$ and rigorously shows that this fixed CRT method cannot by itself establish $\overline d(A)>0$.

4) ATTACK PLAN (ROUND-4)

The exact gaps left after Round 3 are now:

1. The Round 3 order table must be checked entry-by-entry.
2. The Round 3 displayed decimal $N_0$ must be checked against the defining congruences.
3. After repairing the data, the construction should be upgraded from a single exceptional integer to a uniform family.
4. Finally, one should quantify how many integers this repaired construction actually produces up to $X$.

The plan is:

1. Prove that the Round 3 numerical table is wrong.
2. Replace it by the valid Round 2 table.
3. For each $\nu\ge 11$, define $M_\nu=(2^{2^\nu}-1)/G$ with fixed $G=(2^{1024}+1)/45592577$, and define $N_\nu$ by the same corrected congruence conditions.
4. Prove $N_\nu\in A$ for every $\nu\ge 11$.
5. Prove the counting law $\#\{\nu\ge 11:N_\nu\le X\}=\log_2\log_2 X+O(1)$.

5) WORK (ROUND-4)

5.1. The Round-3 numerical certificate is incorrect

Let $M_1=(2^{2048}-1)/G$ with $G=(2^{1024}+1)/45592577$ as in Round 3.

Proposition 5.1. The numerical table displayed in Round 3 is incorrect, and the displayed Round 3 decimal value of $N_0$ is not the CRT integer defined there.

Proof. A deterministic exact computation gives the following counterchecks:

• $48691=23\cdot 29\cdot 73$, so it is not prime; in particular it cannot serve as a prime with $\operatorname{ord}_{48691}(2)=45$.
• $\operatorname{ord}_{811}(2)=270\neq 48$.
• $\operatorname{ord}_{87211}(2)=54\neq 72$.
• $\operatorname{ord}_{233}(2)=29\neq 72$.
• $\operatorname{ord}_{5419}(2)=42\neq 90$.
• $\operatorname{ord}_{2521}(2)=1260\neq 120$.
• $\operatorname{ord}_{1153}(2)=288\neq 144$.
• $\operatorname{ord}_{6700417}(2)=64\neq 144$.
• $\operatorname{ord}_{1303}(2)=651\neq 180$.
• $\operatorname{ord}_{118831}(2)=11883\neq 180$.
• $\operatorname{ord}_{19231}(2)=9615\neq 360$.

Thus at least $11$ of the $28$ claimed order constraints fail.

Moreover, the decimal integer printed in Round 3 has only $202$ decimal digits, while $M_1$ has $316$ decimal digits. Hence that printed integer is strictly between $0$ and $M_1$ and therefore cannot satisfy \[ N_0\equiv 0\pmod{M_1}. \] So the Round 3 numerical certificate must be discarded. $\square$

5.2. Corrected exact-order data

We retain the same overlapping congruence system $(a_i,m_i)$ as in Rounds 2--3: \[ \begin{aligned} &(0,3),(0,5),(1,9),(1,10),(8,12),(8,15),(4,18),(7,20),(5,24),(29,30),\\ &(2,36),(14,36),(17,40),(34,45),(43,45),(13,48),(37,48),(16,60),(19,60),\\ &(26,72),(62,72),(52,90),(37,120),(49,144),(121,144),(103,180),(106,180),(229,360). \end{aligned} \] Its least common multiple is $720$, and every positive integer exponent lies in at least one of these residue classes modulo its corresponding modulus.

The corrected prime choices are exactly the Round 2 ones: \[ \begin{array}{rcl@{\qquad}rcl} (0,3)&\mapsto&7,&(34,45)&\mapsto&631,\\ (0,5)&\mapsto&31,&(43,45)&\mapsto&23311,\\ (1,9)&\mapsto&73,&(13,48)&\mapsto&97,\\ (1,10)&\mapsto&11,&(37,48)&\mapsto&673,\\ (8,12)&\mapsto&13,&(16,60)&\mapsto&61,\\ (8,15)&\mapsto&151,&(19,60)&\mapsto&1321,\\ (4,18)&\mapsto&19,&(26,72)&\mapsto&433,\\ (7,20)&\mapsto&41,&(62,72)&\mapsto&38737,\\ (5,24)&\mapsto&241,&(52,90)&\mapsto&18837001,\\ (29,30)&\mapsto&331,&(37,120)&\mapsto&4562284561,\\ (2,36)&\mapsto&37,&(49,144)&\mapsto&577,\\ (14,36)&\mapsto&109,&(121,144)&\mapsto&487824887233,\\ (17,40)&\mapsto&61681,&(103,180)&\mapsto&181,\\ &&&(106,180)&\mapsto&54001,\\ &&&(229,360)&\mapsto&168692292721. \end{array} \] Let these primes be denoted $p_1,\dots,p_{28}$ in the displayed order. Also let \[ p_{29}=8191=2^{13}-1,\qquad q=45592577,\qquad G=\frac{2^{1024}+1}{q}. \] We fix \[ c\equiv 1\pmod{8191}. \]

Finite certificate used below. A deterministic computation verifies:

1. each listed $p_i$ is prime and $\operatorname{ord}_{p_i}(2)=m_i$;
2. every residue class modulo $720$ is covered by at least one $(a_i,m_i)$;
3. $1\not\equiv p_i+2^e\pmod{8191}$ for all $1\le i\le 28$ and $0\le e\le 12$;
4. with \[ L:=16\cdot 8191\cdot\prod_{i=1}^{28}p_i, \] one has \[ L<G. \]

5.3. The corrected family $N_\nu$

For every integer $\nu\ge 11$, define \[ M_\nu:=\frac{2^{2^\nu}-1}{G}. \] This is an integer because $G\mid (2^{1024}+1)=F_{10}$ and \[ 2^{2^\nu}-1=\prod_{j=0}^{\nu-1}F_j\qquad (\nu\ge 11). \] Equivalently, \[ M_\nu=q\prod_{\substack{0\le j\le \nu-1\\ j\neq 10}}F_j. \]

Now define $N_\nu$ to be the least positive integer satisfying the simultaneous congruences \begin{align} N_\nu&\equiv 0\pmod{M_\nu},\label{wsref-0-65-71-3a-6e-75-2d-4d}\\ N_\nu&\equiv -1\pmod{16},\label{wsref-0-65-71-3a-6e-75-2d-31-36}\\ N_\nu&\equiv 1\pmod{8191},\label{wsref-0-65-71-3a-6e-75-2d-38-31-39-31}\\ N_\nu&\equiv 2^{a_i}\pmod{p_i}\qquad (1\le i\le 28).\label{wsref-0-65-71-3a-6e-75-2d-70-69} \end{align}

Lemma 5.2. For every $\nu\ge 11$, the congruence system (eq:nu-M)--(eq:nu-pi) has a unique solution modulo $LM_\nu$, and the least positive solution satisfies \[ M_\nu\le N_\nu<LM_\nu. \] In particular, \[ N_\nu<2^{2^\nu}-1. \]

Proof. We first show $\gcd(L,M_\nu)=1$.

The factors $16$ and $8191$ are coprime to $M_\nu$: clearly $M_\nu$ is odd, and if $8191\mid M_\nu$, then $8191\mid (2^{2^\nu}-1)$, which would force $\operatorname{ord}_{8191}(2)\mid 2^\nu$, i.e. $13\mid 2^\nu$, impossible.

Next fix one of the primes $p_i$. If $p_i\mid M_\nu$, then again $p_i\mid (2^{2^\nu}-1)$, so $\operatorname{ord}_{p_i}(2)\mid 2^\nu$. But $\operatorname{ord}_{p_i}(2)=m_i$, and every $m_i$ in the list has an odd factor greater than $1$. Therefore $m_i\nmid 2^\nu$, contradiction. Hence $\gcd(p_i,M_\nu)=1$ for all $i$.

So all moduli in (eq:nu-M)--(eq:nu-pi) are pairwise coprime, and the Chinese remainder theorem gives a unique residue class modulo $LM_\nu$.

The least positive solution is divisible by $M_\nu$, so $N_\nu\ge M_\nu$. Since it is the least positive element of its CRT class, we also have $N_\nu<LM_\nu\cdot L$. Because $L<G$ by the finite certificate, \[ N_\nu<LM_\nu L < M_\nu G = 2^{2^\nu}-1. \] This proves the claim. $\square$

5.4. Excluding representations $p+2^d$

Lemma 5.3. For every $\nu\ge 11$, there are no prime $p$ and integer $d\ge 1$ such that \[ N_\nu=p+2^d. \]

Proof. Fix $\nu\ge 11$ and $d\ge 1$. Because the residue system $(a_i,m_i)$ is overlapping, there exists an index $i$ such that \[ d\equiv a_i\pmod{m_i}. \] Since $\operatorname{ord}_{p_i}(2)=m_i$, this implies \[ 2^d\equiv 2^{a_i}\pmod{p_i}. \] Together with (eq:nu-pi), we obtain \[ N_\nu-2^d\equiv 0\pmod{p_i}. \] So if $N_\nu-2^d$ were prime, then necessarily \[ N_\nu-2^d=p_i. \] Reducing modulo $8191$ and using (eq:nu-8191), we would get \[ 1\equiv p_i+2^d\pmod{8191}. \] Since $\operatorname{ord}_{8191}(2)=13$, the residue $2^d\pmod{8191}$ depends only on $d\bmod 13$, so \[ 1\equiv p_i+2^e\pmod{8191} \] for some $0\le e\le 12$, contradicting the finite certificate from § 5.2. Thus $N_\nu-2^d$ is never prime. $\square$

5.5. Excluding representations $p+2^a+2^b$ with $a\neq b$

Lemma 5.4. For every $\nu\ge 11$, there do not exist a prime $p$ and distinct integers $a,b\ge 1$ such that \[ N_\nu=p+2^a+2^b. \]

Proof. By (eq:nu-M), the quotient \[ w_\nu:=\frac{N_\nu}{M_\nu} \] is an integer. Now \[ M_\nu=q\prod_{\substack{0\le j\le \nu-1\\ j\neq 10}}F_j. \] Since $q\equiv 1\pmod{16}$, $F_0=3$, $F_1=5$, and $F_j\equiv 1\pmod{16}$ for all $j\ge 2$, we have \[ M_\nu\equiv 3\cdot 5\equiv -1\pmod{16}. \] Together with (eq:nu-16), this gives \[ w_\nu\equiv 1\pmod{16}. \]

Write \[ B_j= \begin{cases} F_j,&0\le j\le \nu-1,\ j\neq 10,\\ q,&j=10. \end{cases} \] Then each $B_j>1$ divides $F_j=2^{2^j}+1$, and \[ N_\nu=w_\nu\prod_{j=0}^{\nu-1}B_j. \] By Lemma 5.2 we have $N_\nu<2^{2^\nu}-1$. Therefore all hypotheses of the Round 3 Crocker-type lemma are satisfied (with $n=\nu$), and it follows that \[ N_\nu\neq p+2^a+2^b \] for all primes $p$ and all distinct $a,b\ge 1$. $\square$

5.6. The corrected explicit infinite family in $A$

Theorem 5.5. For every integer $\nu\ge 11$, one has \[ N_\nu\in A. \] Hence $A$ contains an explicit infinite family.

Proof. By Lemma 5.3, $N_\nu$ is not of the form $p+2^d$ with $d\ge 1$. Therefore it is not of the diagonal form $p+2^a+2^a$, since $2^a+2^a=2^{a+1}$.

By Lemma 5.4, $N_\nu$ is also not of the form $p+2^a+2^b$ with distinct $a,b\ge 1$.

Applying the Round 2 / Round 3 reduction lemma, we conclude $N_\nu\in A$. $\square$

Corollary 5.6. The family $\{N_\nu\}_{\nu\ge 11}$ is infinite and consists of distinct elements of $A$.

Proof. By Lemma 5.2, $N_\nu\ge M_\nu$ for each $\nu$, and $M_\nu$ is strictly increasing in $\nu$. Hence the $N_\nu$ are distinct. $\square$

5.7. Quantitative size of the corrected family

Theorem 5.7. Define \[ \mathcal{N}(X):=\#\{\nu\ge 11: N_\nu\le X\}. \] Then \[ \mathcal{N}(X)=\log_2\log_2 X+O(1)\qquad (X\to\infty). \] More explicitly, for all sufficiently large $X$, \[ \left\lfloor \log_2\log_2\!\left(\frac{G}{L}X+1\right)\right\rfloor-10 \le \mathcal{N}(X) \le \left\lfloor \log_2\log_2(GX+1)\right\rfloor-10. \]

Proof. From Lemma 5.2 we have \[ M_\nu\le N_\nu<LM_\nu=\frac{L}{G}\left(2^{2^\nu}-1\right). \]

For the upper bound, if $N_\nu\le X$, then $M_\nu\le X$, so \[ \frac{2^{2^\nu}-1}{G}\le X, \] hence \[ 2^{2^\nu}\le GX+1. \] Therefore \[ \nu\le \log_2\log_2(GX+1), \] which gives the displayed upper bound.

For the lower bound, if \[ \frac{L}{G}\left(2^{2^\nu}-1\right)\le X, \] then $N_\nu<X$ by Lemma 5.2. This is implied by \[ 2^{2^\nu}\le \frac{G}{L}X+1. \] So every integer $\nu\ge 11$ satisfying \[ \nu\le \log_2\log_2\!\left(\frac{G}{L}X+1\right) \] contributes one element $N_\nu\le X$, giving the displayed lower bound.

The two bounds differ by at most an additive constant, since $G/L$ and $G$ are fixed positive constants. Hence \[ \mathcal{N}(X)=\log_2\log_2 X+O(1). \] $\square$

Corollary 5.8 (explicit lower bound inside $A$). For all sufficiently large $X$, \[ |A\cap[1,X]|\ge \mathcal{N}(X)\gg \log\log X. \]

Proof. This is immediate from Theorem 5.5 and Theorem 5.7. $\square$

Corollary 5.9 (construction-level obstruction). The corrected fixed-data CRT construction from Rounds 2--4 cannot by itself prove \[ \overline d(A)>0. \] Indeed, the family it produces has counting function only $\log_2\log_2 X+O(1)$, and therefore has density $0$.

Proof. This is immediate from Theorem 5.7. $\square$

6) ADVERSARIAL VERIFICATION

I now try to break the new argument.

1. Did the correction really fix the Round 3 flaw? Yes. Proposition 5.1 explicitly shows that the Round 3 numerical table is invalid. The new family uses the valid Round 2 table instead.
2. Could some $p_i$ divide $M_\nu$ for large $\nu$? No. If $p_i\mid M_\nu$, then $\operatorname{ord}_{p_i}(2)\mid 2^\nu$. But each $\operatorname{ord}_{p_i}(2)=m_i$ has an odd factor greater than $1$, impossible.
3. Could the congruence argument for $p+2^d$ fail when $d$ is huge? No. The overlap property is periodic modulo $720$, and the reduction modulo $8191$ is periodic modulo $13$; both are uniform in $d$.
4. Could the family collapse to finitely many repeated numbers? No. Lemma 5.2 gives $N_\nu\ge M_\nu$, and $M_\nu$ strictly increases with $\nu$.
5. Is Corollary 5.9 overstated? The corollary rules out only the fixed corrected CRT family constructed here. It does not rule out all conceivable covering-system or sieve arguments for positive density.
6. Did we re-use a broken Round 3 step? Only the abstract Round 3 lemmas were re-used. The concrete Round 3 number-theoretic data were discarded and replaced.

No further gap remains in the corrected family construction.

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED).

The upper-density problem remains unresolved here, but Round 4 makes genuine progress in two ways:

1. it identifies and repairs a concrete mathematical error in Round 3; and
2. it upgrades the corrected construction to an explicit infinite family $\{N_\nu\}_{\nu\ge 11}\subseteq A$ with \[ \#\{\nu\ge 11:N_\nu\le X\}=\log_2\log_2 X+O(1). \]

So the minimal corrected statement extracted from the Round 2 / Round 3 CRT method is:

There is an explicit infinite family in $A$, generated by a fixed corrected CRT recipe, but this family is necessarily sparse (size $\asymp \log\log X$ up to $X$), so this route cannot by itself prove positive upper density.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 50%

9) REFERENCES

1. R. Crocker, On the sum of a prime and of two powers of two, Pacific J. Math. 36 $1971$, 103--107.
2. H. Pan, On the integers not of the form $p+2^a+2^b$, Acta Arith. 148 $2011$, no. 1, 55--61.
3. T. F. Bloom, Erdős Problem #9, erdosproblems.com/9.

10) OUTPUT FORMAT

This file is the requested export for problem number $x=9$, namely 9_solutions.tex.

ROUND-2 OBJECTIVE

I pursue path (A) in the following limited but rigorous sense: rather than restarting from scratch or speculating about the full conjecture, I prove new density theorems that were not obtained in Round 1 and that bear directly on the target set \[ A=\{n\in\mathbb N: n\text{ odd and } n\neq p+2^k+2^\ell\text{ for all primes }p\text{ and }k,\ell\ge 0\}. \] The most promising direction after Round 1 is to force positive density on the representable side, because Round 1 had no density theorem there at all. This leads to a nontrivial quantitative upper bound for $\overline d(A)$ and sharpens the remaining gap.

ROUND-1 FOUNDATION USED

I use the following Round-1 items without reproving them.

1. Round-1 Lemma 1 (parity classification). For odd targets $n$, every representation $n=p+2^k+2^\ell$ is either:
   1. $p=2$ and exactly one of $k,\ell$ is $0$; or
   2. $p$ is odd and $2^k+2^\ell$ is even.
2. Round-1 computation. The exact finite check \[ A\cap[1,20{,}000{,}000]=\{1,3\} \] was established already.
3. Round-1 gap statement. The unresolved issue is whether $\overline d(A)>0$.

NEW INSIGHT / TOOL (ROUND-2)

There are three genuinely new ingredients in this round.

1. A direct modern density theorem of Chen--Xu for sets of the form \[ p+2^{k_1}r_1+\cdots+2^{k_t}r_t, \] which applies to our problem when $t=2$ and $r_1=r_2=1$.

2. An explicit quantitative route through the classical Romanoff-type set $\{p+2^k\}$: combining the best current lower bound for its density with a fixed shift by $2$ gives an explicit positive-density subset of our representable odd integers.

3. A much larger exact computation: I extend the deterministic verification from $2\cdot 10^7$ to $5\cdot 10^8$ and still find only the trivial odd exceptions $1,3$.

ATTACK PLAN (ROUND-2)

After Round 1, the exact missing pieces were:

1. no nontrivial density theorem for the representable odd set;
2. no quantitative upper bound on $\overline d(A)$ beyond the trivial bound $\overline d(A)\le 1/2$;
3. only a modest finite computation.

I will prove the following claims.

1. The representable odd set has positive lower density.
2. Quantitatively, \[ \overline d(A)\le 0.392352. \]
3. Computer-assisted but exact verification gives \[ A\cap[1,5\cdot 10^8]=\{1,3\}. \]

This overcomes the main Round-1 obstacle about overlap of many shifted prime sets by locking onto one structured positive-density subfamily, namely $p+2^k+2$ with $k\ge 1$.

WORK (ROUND-2)

Let \[ R:=\{n\in\mathbb N: n\text{ is odd and }n=p+2^k+2^\ell\text{ for some prime }p\text{ and }k,\ell\ge 0\}. \] Then $A=(2\mathbb N+1)\setminus R$. For $x\ge 1$, write \[ A(x):=|A\cap[1,x]|,\qquad R(x):=|R\cap[1,x]|. \]

5.1. Positive lower density of the representable odd set

External theorem used. Let $r_1,\dots,r_t\in\mathbb N$, and let $S(r_1,\dots,r_t)$ be the set of positive odd integers of the form \[ p+2^{k_1}r_1+\cdots+2^{k_t}r_t, \] where $p$ is prime and $k_1,\dots,k_t$ are positive integers. Chen and Xu prove that if \[ \frac1{r_1}+\cdots+\frac1{r_t}>1, \] then $S(r_1,\dots,r_t)$ has positive lower asymptotic density.

Claim 5.1. The set $R$ has positive lower asymptotic density. In particular, there exists $\delta>0$ such that \[ \underline d(R)\ge \delta, \qquad\text{and hence}\qquad \overline d(A)\le \frac12-\delta<\frac12. \]

Proof. Apply the Chen--Xu theorem with $t=2$ and $r_1=r_2=1$. Since \[ \frac1{r_1}+\frac1{r_2}=1+1=2>1, \] it follows that the set \[ S(1,1)=\{p+2^a+2^b: p\text{ prime},\ a,b\ge 1\}\cap(2\mathbb N+1) \] has positive lower density.

Now $S(1,1)\subseteq R$, because our original set $R$ allows all $k,\ell\ge 0$, hence in particular $a,b\ge 1$. Therefore \[ \underline d(R)\ge \underline d(S(1,1))>0. \]

Finally, for every $x$, \[ A(x)=\Big\lfloor\frac{x+1}{2}\Big\rfloor-R(x), \] since $A$ and $R$ partition the odd integers. Taking limsup on the left and using \[ \lim_{x\to\infty}\frac1x\Big\lfloor\frac{x+1}{2}\Big\rfloor=\frac12 \] gives \[ \overline d(A)\le \frac12-\underline d(R)<\frac12. \] This proves the claim. $\square$

5.2. An explicit quantitative upper bound for $\overline d(A)$

External theorem used. Let \[ B:=\{n\in\mathbb N: n=p+2^k\text{ for some prime }p\text{ and }k\ge 0\}. \] Elsholtz and Schlage-Puchta proved the explicit lower-density bound \[ \underline d(B)\ge 0.107648. \]

Claim 5.2. We have \[ \underline d(R)\ge 0.107648 \qquad\text{and hence}\qquad \overline d(A)\le 0.392352. \]

Proof. Define the odd-only Romanoff set \[ B^{\ast}:=\{n\in\mathbb N: n=q+2^k\text{ for some odd prime }q\text{ and }k\ge 1\}. \] Then \[ B\setminus B^{\ast}\subseteq \{q+1:q\text{ odd prime}\}\cup\{2+2^k:k\ge 0\}. \] Hence, for $x\ge 2$, \[ |(B\setminus B^{\ast})\cap[1,x]| \le \pi(x-1)+1+\lfloor\log_2 x\rfloor = o(x). \] Therefore removing $B\setminus B^{\ast}$ does not change lower density, so \[ \underline d(B^{\ast})=\underline d(B)\ge 0.107648. \]

Now let \[ C:=\{m+2:m\in B^{\ast}\}. \] A fixed shift changes counting functions by at most $O(1)$, hence preserves lower density: \[ \underline d(C)=\underline d(B^{\ast})\ge 0.107648. \] If $m\in B^{\ast}$, then $m=q+2^k$ with $q$ an odd prime and $k\ge 1$, so \[ m+2=q+2^k+2^1. \] Thus $m+2\in R$, and therefore $C\subseteq R$. It follows that \[ \underline d(R)\ge \underline d(C)\ge 0.107648. \] Using again \[ A(x)=\Big\lfloor\frac{x+1}{2}\Big\rfloor-R(x), \] we obtain \[ \overline d(A)\le \frac12-0.107648=0.392352. \] This proves the claim. $\square$

5.3. The remaining quantitative gap after combining Pan with Claim 5.2

External theorem used. Pan proved that for every $\varepsilon>0$, \[ A(x)\gg_{\varepsilon} x^{1-\varepsilon}. \]

Corollary 5.3. For every $\varepsilon>0$, \[ x^{1-\varepsilon}\ll_{\varepsilon} A(x)\le (0.392352+o(1))x. \]

Proof. The lower bound is Pan's theorem. The upper bound is Claim 5.2. $\square$

This is the sharp residual obstruction after Round 2: the exceptional set is now known to be much larger than any fixed power $x^{1-\varepsilon}$, but still far from being known to occupy a positive proportion of the integers on infinitely many scales.

5.4. Exact finite computation up to $5\cdot 10^8$

Claim 5.4 (computer-assisted, exact). We have \[ A\cap[1,5\cdot 10^8]=\{1,3\}. \]

Proof. This uses Round-1 Lemma 1 exactly as stated. By that lemma, an odd representable integer $n\le X$ falls into one of two disjoint types:

1. $n=3+2^m$ with $m\ge 1$ (the case $p=2$ and exactly one zero exponent);
2. $n=q+s$, where $q$ is an odd prime and $s=2^k+2^\ell$ is even.

For $X=5\cdot 10^8$, there are exactly $406$ distinct even offsets $s\le X$ of the form $2^k+2^\ell$. I performed the following deterministic computation.

1. Sieve all odd primes $q\le X$.
2. For each of the $406$ even offsets $s$, mark every odd integer of the form $q+s\le X$.
3. Separately mark every special value $3+2^m\le X$.

After all admissible representations are marked, the only unmarked odd integers are $1$ and $3$. I also cross-checked the bitset method against a naive exhaustive search for $X\le 10^4$, and the outputs agree exactly. Hence the computation is exact. $\square$

ADVERSARIAL VERIFICATION

I now try to break the new work.

1. Positive versus nonnegative exponents in Chen--Xu. Their theorem uses $k_i\ge 1$, whereas our original problem allows $k,\ell\ge 0$. This is not a flaw: the Chen--Xu set $S(1,1)$ is a subset of $R$, so positive lower density for $S(1,1)$ implies positive lower density for $R$.

2. Does the explicit bound really come from a subset of $R$? Yes. Every element of $B^{\ast}$ has the form $q+2^k$ with $q$ odd prime and $k\ge 1$, so adding $2$ gives $q+2^k+2^1$, which is an allowed representation in the original problem.

3. Did removing $B\setminus B^{\ast}$ accidentally discard positive density? No. The discarded set is contained in $\{q+1\}$ and $\{2+2^k\}$, whose counting function is $o(x)$. Therefore lower density is unchanged.

4. Is the passage from $A(x)=\lfloor(x+1)/2\rfloor-R(x)$ to $\overline d(A)\le 1/2-\underline d(R)$ legitimate? Yes. It is a direct limsup/liminf application to an exact identity holding for every $x$.

5. Could the finite computation have missed an admissible representation? Not if Round-1 Lemma 1 is correct. The odd-prime branch was covered by all even offsets $2^k+2^\ell$, and the special $p=2$ branch was covered separately by the exact list $3+2^m$.

6. Does any of this settle $\overline d(A)>0$? No. All new results are compatible with both possibilities \[ \overline d(A)=0 \qquad\text{and}\qquad 0<\overline d(A)\le 0.392352. \] So the original problem remains open after this round.

FINAL

UNRESOLVED (BUT STRICTLY ADVANCED)

The strict advances beyond Round 1 are:

1. I proved, using Chen--Xu, that the set of representable odd integers \[ R=\{p+2^k+2^\ell\}\cap(2\mathbb N+1) \] has positive lower density.

2. I proved the explicit quantitative bound \[ \overline d(A)\le 0.392352. \] Thus the problem is no longer squeezed only between $0$ and the trivial ceiling $1/2$; it is squeezed between $0$ and $0.392352$.

3. I extended the exact finite verification from $2\cdot 10^7$ to $5\cdot 10^8$ and still found \[ A\cap[1,5\cdot 10^8]=\{1,3\}. \]

The remaining obstruction is now sharply formulated: one must upgrade Pan's lower bound \[ A(x)\gg_{\varepsilon} x^{1-\varepsilon} \] to a genuinely linear lower bound along infinitely many scales, or else prove that such an upgrade is impossible.

COMPLETION ESTIMATE

COMPLETION: 65%

REFERENCES

References

• [CX24] Y.-G. Chen and J.-Z. Xu, On integers of the form $p+2^{k_1}r_1+\cdots+2^{k_t}r_t$, Journal of Number Theory 258 $2024$, 66--93.
• [ESP18] C. Elsholtz and J.-C. Schlage-Puchta, On Romanov's constant, Mathematische Zeitschrift 288 $2018$, 713--724.
• [Pan11] H. Pan, On the integers not of the form $p+2^a+2^b$, Acta Arithmetica 148 $2011$, 55--61.