Erdős Problem #10

Round 4 (Erdős Problem #10): explicit multiplicity in Crocker's construction

1) ROUND-4 OBJECTIVE

Path (C): obstruction / correction. After Round 3, the main infinite-family obstruction for $k=3$ was rigorous but still only qualitative up to an unspecified implicit constant. The most promising strict advance is therefore to extract explicit quantitative strength from Crocker's construction.

The goal of this round is to prove a theorem strictly stronger than the Round 3 bound $E_3(X)\gg \log\log X$: namely, to show that for each stage of Crocker's construction there are at least \[ C_0:=7827\cdot 2^{554} \] distinct even integers, all divisible by $16$, that are not representable as \[ \text{prime}+\text{at most }3\text{ powers of }2, \] and consequently \[ E_3(X)\ge C_0\left(\lfloor \log_2\log_2 X\rfloor-10\right) \qquad (X\ge 2^{2^{11}}). \]

2) Round-3 FOUNDATION USED

We use the following previously established facts.

• Round 1, Lemma 10.1. An integer $N$ is $k$-representable if and only if there exists $m\ge 0$ with $\mathrm{wt}_2(m)\le k$ such that $N-m$ is prime.
• Round 1, Lemma 10.2. If $N$ is even and $N=p+S$ with $p$ an odd prime and $\mathrm{wt}_2(S)\le k$, then $S=1+m$ with $m$ even and $\mathrm{wt}_2(m)\le k-1$, hence $N-1=p+m$.
• Round 2, Lemma 5.1. If $t\equiv -1\pmod{2^r}$ and $t>2^r-1$, then $\mathrm{wt}_2(t-1)\ge r$; in particular, $t\equiv -1\pmod{16}$ and $t>15$ imply $\mathrm{wt}_2(t-1)\ge 4$.
• Round 3 repaired shift theorem. If $t$ is one of Crocker's odd integers with
  1. $t\equiv -1\pmod{16}$,
  2. $t$ composite,
  3. $t\neq p+2^a$ for all primes $p$ and all $a\ge 1$,
  4. $t\neq p+2^a+2^b$ for all primes $p$ and all $a,b\ge 1$,
  then $N:=t+1$ is even and not $3$-representable.

We will not re-prove these facts; the new work in this round is entirely quantitative.

3) NEW INSIGHT / TOOL (ROUND-4)

The new ingredient is that Round 3 did not use two explicit numerical outputs of Crocker's proof:

1. he proves that the parameter $v$ in his counting argument satisfies \[ (16\prod_{i=1}^{h+1}p_i)\,v<G_k<(v+1)(16\prod_{i=1}^{h+1}p_i), \] and then explicitly estimates \[ 16\prod_{i=1}^{h+1}p_i<2^{434}<2^{988}<G_k; \] hence \[ v\ge 2^{554}; \]
2. for the same construction he proves that there are at least \[ 2^{13}-1-13\cdot 28=7827 \] admissible choices of the residue class $c$.

The key new observation is that different admissible choices of $c$ produce disjoint congruence classes modulo the full CRT modulus, so these $7827$ choices multiply the stage-by-stage count.

A second useful observation is that the stage-$s$ odd integers are all divisible by \[ \frac{2^{2^s}-1}{G_{10}}, \] hence in particular by the factor $2^{2^{s-1}}+1$ for every $s\ge 11$. This places the resulting even counterexamples inside explicit disjoint tower intervals.

4) ATTACK PLAN (ROUND-4)

Round 3 left two quantitative gaps.

• First, the constant hidden in $E_3(X)\gg \log\log X$ was not made explicit.
• Second, the proof counted only one congruence class per stage, whereas Crocker's construction actually allows many admissible choices of $c$.

So the plan is:

1. fix a stage $s\ge 11$ and an admissible choice of $c$;
2. use Crocker's inequalities to show that this single choice contributes at least $v\ge 2^{554}$ odd integers $t$;
3. prove that different admissible $c$ give disjoint sets of $t$, so stage $s$ contributes at least $7827\cdot 2^{554}$ odd integers;
4. invoke the Round 3 shift theorem to convert these into even non-$3$-representable integers;
5. locate them inside the interval \[ [2^{2^{s-1}}+2,\;2^{2^s}], \] and then sum over stages.

This overcomes the previous obstacle because it uses all of the multiplicity already present in Crocker's CRT construction, rather than only one residue class per stage.

5) WORK (ROUND-4)

5.1 Crocker's stage data

Fix Crocker's explicit choice $k=10$ and his overlapping congruence system $1$. For each stage $s>10$, each admissible residue class $c$ modulo \[ p_{h+1}=2^{13}-1 \] produces an enlarged simultaneous congruence system $S_s(c)$. Let \[ M_s:=16\cdot \frac{2^{2^s}-1}{G_{10}}\cdot \prod_{i=1}^{h+1}p_i. \] By the Chinese Remainder Theorem, the solutions of $S_s(c)$ are exactly the integers \[ t\equiv q_s(c)\pmod{M_s} \] for a uniquely determined nonzero residue class $q_s(c)\pmod{M_s}$, with $1\le q_s(c)<M_s$.

Crocker proves that for each such $c$ there are exactly $v$ or $v+1$ positive integers $t\le 2^{2^s}-1$ satisfying $S_s(c)$, where $v$ is independent of $s$ and $c$ and is defined by \[ (16\prod_{i=1}^{h+1}p_i)\,v<G_{10}<(v+1)(16\prod_{i=1}^{h+1}p_i). \] He also proves the explicit estimates \[ 16\prod_{i=1}^{h+1}p_i<2^{434}<2^{988}<G_{10}. \] Therefore \[ \frac{G_{10}}{16\prod_{i=1}^{h+1}p_i}>2^{554}. \] Since $v=\left\lfloor \dfrac{G_{10}}{16\prod_{i=1}^{h+1}p_i}\right\rfloor$, it follows that \[ v\ge 2^{554}. \] Hence:

Lemma 5.1. For every stage $s\ge 11$ and every admissible choice of $c$, the system $S_s(c)$ has at least $2^{554}$ positive solutions $t\le 2^{2^s}-1$.

Proof. As just noted, each $S_s(c)$ has either $v$ or $v+1$ positive solutions $\le 2^{2^s}-1$, and $v\ge 2^{554}$. $\square$

5.2 Distinct admissible choices of $c$ give disjoint sets

Crocker next proves that the number of admissible residue classes $c$ modulo $p_{h+1}=2^{13}-1$ is at least \[ 2^{13}-1-13\cdot 28=7827. \] Let $\mathcal C$ be any set of $7827$ such admissible choices.

Lemma 5.2. Fix $s\ge 11$. If $c_1,c_2\in \mathcal C$ are distinct, then \[ q_s(c_1)\not\equiv q_s(c_2)\pmod{M_s}. \] Consequently, the corresponding solution sets \[ T_s(c):=\{t\le 2^{2^s}-1:\ t\equiv q_s(c)\pmod{M_s}\} \] are pairwise disjoint.

Proof. In the CRT system $S_s(c)$, the residue class modulo $p_{h+1}$ is exactly $t\equiv c\pmod{p_{h+1}}$. If $c_1\neq c_2$, then any solution of $S_s(c_1)$ is incongruent modulo $p_{h+1}$ to any solution of $S_s(c_2)$. Since $p_{h+1}$ divides $M_s$, equality \[ q_s(c_1)\equiv q_s(c_2)\pmod{M_s} \] would force \[ q_s(c_1)\equiv q_s(c_2)\pmod{p_{h+1}}, \] hence $c_1\equiv c_2\pmod{p_{h+1}}$, contradiction. Thus the residue classes modulo $M_s$ are distinct, and therefore the sets $T_s(c)$ are pairwise disjoint. $\square$

5.3 Explicit stage multiplicity

Let \[ T_s:=\bigcup_{c\in\mathcal C} T_s(c). \]

Proposition 5.3. For every stage $s\ge 11$, \[ |T_s|\ge 7827\cdot 2^{554}. \]

Proof. By Lemma 5.1, each $T_s(c)$ has cardinality at least $2^{554}$. By Lemma 5.2, the sets $T_s(c)$ are pairwise disjoint as $c$ ranges over $\mathcal C$. Hence \[ |T_s|=\sum_{c\in\mathcal C}|T_s(c)|\ge |\mathcal C|\cdot 2^{554}\ge 7827\cdot 2^{554}. \] $\square$

5.4 Conversion to even counterexamples for $k=3$

Theorem 5.4 (uniform stage theorem). For every integer $s\ge 11$, the interval \[ I_s:=[\,2^{2^{s-1}}+2,\;2^{2^s}\,] \] contains at least \[ C_0:=7827\cdot 2^{554} \] distinct even integers $N$, all divisible by $16$, that are not representable as a prime plus at most $3$ powers of $2$.

Proof. Fix $s\ge 11$ and $t\in T_s$.

Because $t$ satisfies $S_s(c)$ for some admissible $c$, the Round 3 repaired shift theorem applies: $t$ is odd, composite, congruent to $-1\pmod{16}$, and is neither of the form $p+2^a$ nor of the form $p+2^a+2^b$ with $a,b\ge 1$. Therefore \[ N:=t+1 \] is even and not $3$-representable.

Also $t\equiv -1\pmod{16}$, so $16\mid N$.

It remains to locate $N$ inside $I_s$. From the defining condition in $S_s(c)$ we have \[ t\equiv 0\pmod{\frac{2^{2^s}-1}{G_{10}}}. \] Now \[ 2^{2^s}-1=\prod_{j=0}^{s-1}(2^{2^j}+1), \] and $G_{10}$ is a divisor of the single factor $2^{2^{10}}+1$. Since $s\ge 11$, the quotient $\dfrac{2^{2^s}-1}{G_{10}}$ still contains the factor $2^{2^{s-1}}+1$. Hence \[ t\ge 2^{2^{s-1}}+1. \] On the other hand, by construction, \[ t\le 2^{2^s}-1. \] Therefore \[ 2^{2^{s-1}}+2\le N=t+1\le 2^{2^s}, \] so $N\in I_s$.

Finally, Proposition 5.3 provides at least $C_0$ distinct choices of $t$, hence at least $C_0$ distinct values of $N=t+1$. $\square$

5.5 Global counting consequence

Let \[ E_3(X):=\#\{N\le X:\ N\text{ even and not }3\text{-representable}\}. \]

Corollary 5.5. For every $X\ge 2^{2^{11}}$, \[ E_3(X)\ge C_0\left(\lfloor \log_2\log_2 X\rfloor-10\right), \qquad C_0=7827\cdot 2^{554}. \] In particular, \[ E_3(X)\gg \log\log X \] with an explicit constant, and indeed the integers counted on the left may all be chosen divisible by $16$.

Proof. Let \[ m:=\lfloor \log_2\log_2 X\rfloor. \] Then $m\ge 11$ and $2^{2^s}\le X$ for every $11\le s\le m$. By Theorem 5.4, each interval \[ I_s=[2^{2^{s-1}}+2,\;2^{2^s}] \] contains at least $C_0$ even non-$3$-representable integers. These intervals are pairwise disjoint. Hence \[ E_3(X)\ge \sum_{s=11}^{m} C_0 = C_0(m-10) = C_0\left(\lfloor \log_2\log_2 X\rfloor-10\right). \] $\square$

6) ADVERSARIAL VERIFICATION

• Did we really get a new theorem, rather than a repackaging of Round 3? Yes. Round 3 only proved $E_3(X)\gg \log\log X$ with an unspecified constant and no local interval statement. Theorem 5.4 gives an explicit stagewise count $C_0=7827\cdot 2^{554}$ in each tower interval, and Corollary 5.5 gives an explicit global lower bound.

• Is the use of $7827$ legitimate? Yes. Crocker explicitly proves that there are at least $7827$ admissible choices for $c$. The only additional point needed here is disjointness of the resulting congruence classes modulo $M_s$, which is established in Lemma 5.2 by reducing modulo $p_{h+1}$.

• Could two different $c$ choices yield the same actual integer $t$ below $2^{2^s}-1$? No. Any such $t$ would satisfy both $t\equiv c_1\pmod{p_{h+1}}$ and $t\equiv c_2\pmod{p_{h+1}}$, forcing $c_1=c_2$.

• Is the lower bound $v\ge 2^{554}$ correct? Yes. Crocker proves \[ (16\prod p_i)\,v<G_{10}<(v+1)(16\prod p_i) \] and \[ 16\prod p_i<2^{434}<2^{988}<G_{10}. \] Therefore \[ \frac{G_{10}}{16\prod p_i}>2^{554}, \] so its floor is at least $2^{554}$.

• Why does every stage-$s$ integer lie above $2^{2^{s-1}}+1$? Because each stage-$s$ integer is divisible by $\dfrac{2^{2^s}-1}{G_{10}}$, and for $s\ge 11$ this quotient still contains the full factor $2^{2^{s-1}}+1$.

• Have we used any unproved new representation argument? No. The passage from odd $t$ to even $N=t+1$ is exactly the repaired Round 3 argument, which itself rests on Round 1 Lemmas 10.1--10.2 and Round 2 Lemma 5.1.

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED). This round does not settle Erdős Problem #10 in full. It does, however, strengthen the current obstruction substantially beyond Round 3: for every $s\ge 11$, the interval \[ [2^{2^{s-1}}+2,\;2^{2^s}] \] contains at least \[ 7827\cdot 2^{554} \] even integers, all divisible by $16$, that are not representable as a prime plus at most $3$ powers of $2$. Consequently, \[ E_3(X)\ge 7827\cdot 2^{554}\left(\lfloor \log_2\log_2 X\rfloor-10\right) \qquad (X\ge 2^{2^{11}}). \] So we now have an explicit, quantitative, infinitely repeated obstruction at $k=3$.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 64%

9) REFERENCES

1. T. F. Bloom, Erdős Problem #10, https://www.erdosproblems.com/10.
2. R. Crocker, On the sum of a prime and of two powers of two, Pacific J. Math. 36 $1971$, 103--107.

Erdős Problem #10: independent continuation

1) OBJECTIVE AND SOURCE AUDIT

2) REPAIR OF THE FIRST STAGE

3) THE SHIFT, INCLUDING THE PRIME TWO

4) LIMITATION OF THE QUANTITATIVE CLAIM

7) FINAL

8) COMPLETION ESTIMATE

Round 2 $v2$: Infinite family of even integers not $3$-representable

1) ROUND-2 OBJECTIVE

Path (C): obstruction / correction. We prove a structural obstruction strictly beyond Round 1: there are infinitely many even integers that are not $3$-representable. Consequently, any universal constant $k$ (if it exists) must satisfy $k\ge 4$.

2) ROUND-1 FOUNDATION USED

We use the following Round 1 results (without re-proving them):

• Lemma 10.1 (binary-weight reformulation). An integer $n$ is $k$-representable iff there exists $m\ge 0$ with $\mathrm{wt}_2(m)\le k$ such that $n-m$ is prime.
• Lemma 10.2 (parity reduction for even targets). If $n$ is even and $n=p+S$ with $p$ an odd prime and $\mathrm{wt}_2(S)\le k$, then $S=1+m$ with $m$ even and $\mathrm{wt}_2(m)\le k-1$, so $n-1=p+m$.

3) NEW INSIGHT / TOOL (ROUND-2)

New external input: Crocker $1971$. Crocker constructs infinitely many odd integers $t$ with

1. $t\equiv -1 \pmod{16}$,
2. $t$ is not representable as $p+2^a$ with $p$ prime and $a\ge 1$,
3. $t$ is not representable as $p+2^a+2^b$ with $p$ prime and $a,b\ge 1$.

New local lemma (proved here). From the congruence $t\equiv -1\pmod{16}$ we deduce a Hamming-weight lower bound $\mathrm{wt}_2(t-1)\ge 4$ for all $t>15$, which blocks any $k=3$ representation using the even prime $2$.

4) ATTACK PLAN (ROUND-2)

Round 1 gap. Round 1 verified one explicit even $k=3$ counterexample, but had no infinite mechanism.

Plan. Take $t$ from Crocker's infinite family and set $n=t+1$ (even). If $n$ had a $3$-representation $n=p+m$ with $\mathrm{wt}_2(m)\le 3$, then:

• if $p$ is odd, Lemma 10.2 forces $t=n-1$ to be representable as $p+m'$ with $m'$ even and $\mathrm{wt}_2(m')\le 2$, i.e. $m'\in\{0,2^a,2^a+2^b\}$ with $a,b\ge 1$; Crocker forbids this;
• if $p=2$, then $m=n-2=t-1$ and we would need $\mathrm{wt}_2(t-1)\le 3$, contradicted by the new Hamming-weight lemma coming from $t\equiv -1\pmod{16}$.

5) WORK (ROUND-2)

5.1 Congruence-to-weight lemma

Lemma 5.1. Let $r\ge 1$. If $t\equiv -1\pmod{2^r}$ and $t>2^r-1$, then \[ \mathrm{wt}_2(t-1)\ \ge\ r. \] In particular, if $t\equiv -1\pmod{16}$ and $t>15$, then $\mathrm{wt}_2(t-1)\ge 4$.

Proof. Write $t=2^r q+(2^r-1)$ with an integer $q\ge 1$. Then \[ t-1=2^r q+(2^r-2). \] The number $2^r-2$ has binary form $(111\cdots 110)_2$ (with exactly $r-1$ ones), and $2^r q$ has its lowest $r$ bits equal to $0$, so there is no carry interaction when adding these two summands. Therefore \[ \mathrm{wt}_2(t-1)=\mathrm{wt}_2(2^r q)+\mathrm{wt}_2(2^r-2)=\mathrm{wt}_2(q)+(r-1)\ge 1+(r-1)=r. \] $\square$

5.2 Infinite family of even integers not $3$-representable

Theorem 5.2 (Crocker, 1971; extracted form). There exist infinitely many odd integers $t>15$ such that:

1. $t\equiv -1\pmod{16}$;
2. $t\neq p+2^a$ for any prime $p$ and any integer $a\ge 1$;
3. $t\neq p+2^a+2^b$ for any prime $p$ and integers $a,b\ge 1$.

Theorem 5.3 (Round 2 main theorem). There exist infinitely many even integers $n$ that are not $3$-representable.

Proof. Let $t$ be an odd integer satisfying Theorem 5.2, and set $n:=t+1$ (even). Assume for contradiction that $n$ is $3$-representable. By Lemma 10.1 there exists $m\ge 0$ with $\mathrm{wt}_2(m)\le 3$ such that $p:=n-m$ is prime, i.e. \[ n=p+m,\qquad \mathrm{wt}_2(m)\le 3. \] We split into cases.

Case 1: $p$ is an odd prime. Then $m=n-p$ is odd. Apply Lemma 10.2 with $k=3$ to write $m=1+m'$ where $m'$ is even and $\mathrm{wt}_2(m')\le 2$. Hence \[ t=n-1=(p+m)-1=p+m'. \] Because $m'$ is even and $\mathrm{wt}_2(m')\le 2$, we have $m'\in\{0,2^a,2^a+2^b\}$ with $a,b\ge 1$ (distinct in the last option). This contradicts Theorem 5.2.

Case 2: $p=2$. Then $m=n-2=t-1$, so $\mathrm{wt}_2(t-1)\le 3$. But $t\equiv -1\pmod{16}$ and $t>15$, so Lemma 5.1 (with $r=4$) gives $\mathrm{wt}_2(t-1)\ge 4$, contradiction.

Both cases contradict, hence $n$ is not $3$-representable. Since Theorem 5.2 provides infinitely many such $t$, we obtain infinitely many even counterexamples $n=t+1$. $\square$

5.3 Consequence for the original question

Corollary 5.4. If there exists an absolute $k$ such that every integer $n\ge 2$ is $k$-representable, then necessarily $k\ge 4$.

Proof. Theorem 5.3 gives infinitely many integers that are not $3$-representable, so no universal $k\le 3$ can work. $\square$

6) ADVERSARIAL VERIFICATION

• Repetitions of powers of $2$. Eliminated by Lemma 10.1: allowing repetition is equivalent to a Hamming-weight bound.
• The $p=2$ edge case. Handled separately via Lemma 5.1. Note that the exceptional small value $t=15$ would fail Lemma 5.1, but Crocker's family contains infinitely many $t>15$.
• $m=0$ possibility. For $n=t+1>16$ even, $m=0$ would force $p=n$ an even prime, impossible (only $2$ is even prime).
• Use of Crocker. We only use the three listed properties (including the imposed congruence $t\equiv -1\!\!\pmod{16}$) and the fact that infinitely many such $t$ exist.

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED). We proved (using Round 1 Lemmas 10.1--10.2 and Crocker $1971$) that there are infinitely many even integers not $3$-representable. Hence any universal $k$ must satisfy $k\ge 4$. The existence of a universal $k$ remains open.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 45%

9) REFERENCES

1. R. Crocker, On the sum of a prime and of two powers of two, Pacific J. Math. 36 $1971$, 103--107.