Erdős Problem #11

Problem #11 -- Round 5: many integers have no squarefree shift by a small power of $2$

1) ROUND-5 OBJECTIVE

Path pursued: (C) obstruction / correction of proof strategy.

Round 4 showed that there are infinitely many odd integers $n$ for which every exponent \[ 0\le e\le c\,\frac{\log n}{\log\log n} \] is bad (that is, $n-2^e$ is not squarefree), but only in a one-point existence form. The most promising next step is to strengthen that obstruction from existence to abundance. The goal of this round is therefore to prove that for every fixed $c<\tfrac12$, there are many odd integers $n\le X$ whose first possible good exponent exceeds \[ c\,\frac{\log X}{\log\log X}. \] This rules out an entire class of proof strategies: any argument that only inspects exponents up to $(\tfrac12-\varepsilon)\log n/\log\log n$ cannot possibly settle the problem.

2) Round-4 FOUNDATION USED

I use the following Round 4 results without reproving them:

1. Definition of $e_{\min}(n)$: \[ e_{\min}(n):=\min\{e\ge 0: n-2^e\ge 1\text{ and }n-2^e\text{ is squarefree}\}, \] with $e_{\min}(n)=+\infty$ if no such exponent exists.
2. Lemma 11.8 (corrected finite-range CRT killing): for every finite exponent set $E\subset\mathbb Z_{\ge 0}$ there are infinitely many odd integers $n>2^{\max E}$ such that $n-2^e$ is not squarefree for every $e\in E$.
3. Theorem 11.10 (primorial-scale finite-range killing): using the first $K+1$ odd primes gives an odd integer $n$ with $2^K<n<4((K+2)!)^4$ and $n-2^e$ non-squarefree for all $0\le e\le K$.

3) NEW INSIGHT / TOOL (ROUND-5)

The new ingredient is that the Round 4 CRT construction does not merely produce one integer for each $K$; it produces a full arithmetic progression of such integers. Estimating the modulus of that progression sharply enough shows:

• for every fixed $0<c<\tfrac12$, the set of odd integers $n\le X$ with \[ e_{\min}(n)>c\,\frac{\log X}{\log\log X} \] has size at least $X^{1-2c-o(1)}$;
• equivalently, \[ \max_{\substack{n\le X\\ n\text{ odd}}} e_{\min}(n)\ge \left(\frac12-o(1)\right)\frac{\log X}{\log\log X}. \]

Thus Round 5 upgrades the Round 4 infinite-sequence obstruction to a quantitative counting theorem.

4) ATTACK PLAN (ROUND-5)

The exact gap left after Round 4 is that the obstruction was only existential: it showed that some odd integers force large good exponents, but it did not measure how often this happens.

The plan is:

1. strengthen the Round 4 CRT argument into a progression lemma: for each $K$, one residue class modulo a modulus $M_K$ forces every shift $n-2^e$ with $0\le e\le K$ to be non-squarefree;
2. bound $M_K$ from above by \[ \log M_K\le 2K\log K+O(K\log\log K); \]
3. count how many terms of that residue class lie below $X$ when \[ K=\left\lfloor c\frac{\log X}{\log\log X}\right\rfloor, \qquad 0<c<\frac12. \] This produces a lower bound of order $X^{1-2c-o(1)}$.

5) WORK (ROUND-5)

Throughout this round, all unadorned logarithms are natural logarithms.

5.1. A progression version of the finite-range CRT obstruction

Let $p_m$ denote the $m$-th prime, so $p_1=2$, $p_2=3$, $p_3=5$, and so on. For $K\ge 0$, define \[ M_K:=2\prod_{m=2}^{K+2} p_m^2. \]

Lemma 11.12 (CRT progression certificate). For every integer $K\ge 0$, there exists a residue class $a_K\pmod{M_K}$ such that for every integer $n\equiv a_K\pmod{M_K}$ one has \[ p_{e+2}^2\mid (n-2^e)\qquad (0\le e\le K). \] Consequently, every such $n$ with $n>2^K$ satisfies \[ e_{\min}(n)\ge K+1. \]

Proof. Consider the congruence system \[ n\equiv 1\pmod 2, \qquad n\equiv 2^e\pmod{p_{e+2}^2} \qquad (0\le e\le K). \] The moduli $2,p_2^2,p_3^2,\dots,p_{K+2}^2$ are pairwise coprime, so by the Chinese remainder theorem there is a unique residue class $a_K\pmod{M_K}$ satisfying all congruences.

If $n\equiv a_K\pmod{M_K}$, then in particular $n\equiv 2^e\pmod{p_{e+2}^2}$ for each $0\le e\le K$, hence \[ p_{e+2}^2\mid (n-2^e) \qquad (0\le e\le K). \] Therefore each $n-2^e$ is not squarefree. If moreover $n>2^K$, then $n-2^e\ge 1$ for every $0\le e\le K$, so all exponents $e\le K$ are genuinely inadmissible as witnesses, and hence $e_{\min}(n)\ge K+1$. $\square$

5.2. Size of the progression modulus

Lemma 11.13 (upper bound for $M_K$). As $K\to\infty$, \[ \log M_K\le 2K\log K+O(K\log\log K). \] Also, \[ M_K>2^K \] for every $K\ge 0$.

Proof. The lower bound is immediate: \[ M_K=2\prod_{m=2}^{K+2}p_m^2\ge 2\cdot 3^{2(K+1)}>2^K. \]

For the upper bound, use the explicit Rosser--Schoenfeld estimate (already used in Round 4): for all sufficiently large $m$, \[ p_m<m(\log m+\log\log m). \] Hence for all sufficiently large $m$, \[ p_m\le 3m\log m, \] so \[ \log p_m\le \log m+\log\log m+O(1). \] Therefore \[ \log M_K =\log 2+2\sum_{m=2}^{K+2}\log p_m \le C+2\sum_{m=2}^{K+2}\log m+2\sum_{m=2}^{K+2}\log\log m, \] for some absolute constant $C$.

Now \[ \sum_{m=2}^{K+2}\log m=\log((K+2)!)=K\log K+O(K) \] by Stirling's formula, while trivially \[ \sum_{m=2}^{K+2}\log\log m\le (K+1)\log\log(K+2)=O(K\log\log K). \] Combining these estimates gives \[ \log M_K\le 2K\log K+O(K\log\log K), \] as claimed. $\square$

5.3. A counting theorem for large least good exponent

For $0<c<\tfrac12$ and $X\ge 3$, define \[ \mathcal B_c(X):=\left\{n\le X:\ n\text{ odd and }e_{\min}(n)>c\frac{\log X}{\log\log X}\right\}. \]

Theorem 11.14 (many odd integers have no good small exponent). Fix $0<c<\tfrac12$. Then \[ |\mathcal B_c(X)|\ge X^{1-2c-o(1)} \qquad (X\to\infty). \] Equivalently: for every fixed $0<c<\tfrac12$, there are at least $X^{1-2c-o(1)}$ odd integers $n\le X$ such that every exponent \[ 0\le e\le c\frac{\log X}{\log\log X} \] is bad.

Proof. Fix $0<c<\tfrac12$ and let \[ K:=\left\lfloor c\frac{\log X}{\log\log X}\right\rfloor. \] Apply Lemma 11.12 to this $K$, obtaining a residue class $a_K\pmod{M_K}$ with the property that every $n\equiv a_K\pmod{M_K}$ satisfies \[ p_{e+2}^2\mid (n-2^e) \qquad (0\le e\le K). \] Let $b_K$ be the smallest positive integer congruent to $a_K\pmod{M_K}$ and exceeding $2^K$. Because $0<a_K<M_K$ and $M_K>2^K$ by Lemma 11.13, we have \[ b_K<2M_K. \] Then every integer of the form \[ n=b_K+tM_K\qquad (t\ge 0) \] is odd, satisfies $n>2^K$, and obeys $e_{\min}(n)\ge K+1$ by Lemma 11.12. Hence all such $n\le X$ belong to $\mathcal B_c(X)$.

The number of such integers is at least \[ \left\lfloor\frac{X-b_K}{M_K}\right\rfloor+1\ge \frac{X}{M_K}-2. \] So it remains to bound $M_K$.

By Lemma 11.13, \[ \log M_K\le 2K\log K+O(K\log\log K). \] Since \[ K=c\frac{\log X}{\log\log X}+O(1), \] we have \[ K\log K=c\log X+O\!\left(\frac{\log X\,\log\log\log X}{\log\log X}\right), \] and similarly $K\log\log K=o(\log X)$. Therefore \[ \log M_K\le (2c+o(1))\log X, \] that is, \[ M_K\le X^{2c+o(1)}. \] Substituting into the counting bound yields \[ |\mathcal B_c(X)|\ge X^{1-2c-o(1)}, \] which proves the theorem. $\square$

5.4. Consequences

Corollary 11.14.1 (maximal order lower bound). As $X\to\infty$, \[ \max_{\substack{n\le X\\ n\text{ odd}}} e_{\min}(n) \ge \left(\frac12-o(1)\right)\frac{\log X}{\log\log X}. \]

Proof. Let $\varepsilon>0$ be fixed. Apply Theorem 11.14 with $c=\tfrac12-\varepsilon$. Then for all sufficiently large $X$, \[ |\mathcal B_{1/2-\varepsilon}(X)|\ge X^{2\varepsilon-o(1)}>0, \] so there exists an odd integer $n\le X$ with \[ e_{\min}(n)>\left(\frac12-\varepsilon\right)\frac{\log X}{\log\log X}. \] Taking the maximum over odd $n\le X$ gives \[ \max_{\substack{n\le X\\ n\text{ odd}}} e_{\min}(n) \ge \left(\frac12-\varepsilon\right)\frac{\log X}{\log\log X} \] for all sufficiently large $X$. Since $\varepsilon>0$ is arbitrary, the stated $(\tfrac12-o(1))$ lower bound follows. $\square$

Corollary 11.14.2 (proof strategies ruled out). Fix any $\varepsilon>0$. No proof strategy that, for each odd $n$, only inspects exponents \[ e\le \left(\frac12-\varepsilon\right)\frac{\log n}{\log\log n} \] can prove the Erdős conjecture.

Proof. By Corollary 11.14.1, for arbitrarily large $X$ there is an odd $n\le X$ with \[ e_{\min}(n)\ge \left(\frac12-\frac\varepsilon2\right)\frac{\log X}{\log\log X}. \] Since the function $t\mapsto \log t/\log\log t$ is increasing for all sufficiently large $t$, we have \[ \frac{\log n}{\log\log n}\le \frac{\log X}{\log\log X}, \] so, for large $X$, \[ e_{\min}(n)>\left(\frac12-\varepsilon\right)\frac{\log n}{\log\log n}. \] Thus every exponent in that range is bad for this $n$, and any method confined to inspecting only those exponents must fail on infinitely many inputs. $\square$

6) ADVERSARIAL VERIFICATION

Use of Round 4. The new progression lemma is a genuine strengthening of the Round 4 CRT obstruction: Round 4 produced one integer for each $K$, whereas Lemma 11.12 identifies an entire arithmetic progression of such integers.

Admissibility of exponents. The original problem only cares about exponents $e$ with $n-2^e\ge 1$. This is why the proof explicitly introduces $b_K>2^K$. Without that step, the CRT congruences alone would not guarantee relevance to the representation problem.

Counting bound. The estimate \[ \left\lfloor\frac{X-b_K}{M_K}\right\rfloor+1\ge \frac{X}{M_K}-2 \] is valid because $b_K<2M_K$. This is exactly where the bound $M_K>2^K$ is used.

Asymptotic regime. The theorem requires $c<\tfrac12$. This is not an artefact of a sloppy estimate; it comes from the exponent $2c$ in the bound $M_K\le X^{2c+o(1)}$. The present one-prime-per-exponent CRT method does not by itself cross the natural barrier $c=\tfrac12$.

Monotonicity in Corollary 11.14.2. The function $t\mapsto \log t/\log\log t$ is increasing for all sufficiently large $t$, so replacing $X$ by a smaller $n\le X$ is legitimate there.

No conflict with Round 2's Wieferich obstruction. The present construction still uses one distinct prime square per exponent. Therefore it does not contradict, bypass, or weaken Round 2's structural results about reusing a non-Wieferich prime across multiple exponents. Rather, it isolates what can already be forced without any reuse at all.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 5 strictly strengthens Round 4 in a mathematically substantive way:

1. it upgrades the finite-range CRT obstruction from an existence theorem to an arithmetic-progression theorem (Lemma 11.12);
2. it proves a quantitative counting statement: for every fixed $0<c<\tfrac12$, \[ \#\left\{n\le X:\ n\text{ odd and }e_{\min}(n)>c\frac{\log X}{\log\log X}\right\}\ge X^{1-2c-o(1)}; \]
3. it yields the sharp obstruction, within this proof paradigm, that \[ \max_{n\le X\atop n\text{ odd}} e_{\min}(n) \ge \left(\frac12-o(1)\right)\frac{\log X}{\log\log X}. \]

Thus any eventual proof of Problem #11 must cope not merely with isolated integers, but with many integers whose first good exponent is forced above $(\tfrac12-o(1))\log n/\log\log n$.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 78%

9) REFERENCES

• J. B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 $1962$, 64--94. Used for the explicit upper bound $p_m<m(\log m+\log\log m)$.
• Stirling's formula for $\log((K+2)!)=K\log K+O(K)$.

Problem 11: reusing two square divisors

1) OBJECTIVE AND SOURCE REVIEW

Attempt dated 2026-09-23. The target is the representation of every sufficiently large odd integer as a positive squarefree integer plus a power of two. I read the complete supplied gpt_pro_5.4/11.tex. Its Chinese remainder construction excludes small exponents using a different prime for each exponent; that is an obstruction to a restricted search, not a counterexample to the representation conjecture. Here two primes are reused periodically. No claim of literature novelty is made.

2) WORK

Write $e_{\min}(n)=\min\{e\ge0:n-2^e\ge1\text{ is squarefree}\}$, with value $+\infty$ if the set is empty. For each integer $K$, let \[ R_K=\{0\le e\le K:6\nmid e,\ 20\nmid e\},\qquad r=|R_K|. \] In every block of 60 exponents, 10 are divisible by 6, 3 by 20, and 1 by both. Thus $r=4K/5+O(1)$. List $R_K$ as $e_1,\ldots,e_r$ and let $q_1,\ldots,q_r$ be the first $r$ primes exceeding 5. Impose \[ n\equiv1\pmod2,\quad n\equiv1\pmod9,\quad n\equiv1\pmod{25},\quad n\equiv2^{e_j}\pmod{q_j^2}\quad(1\le j\le r). \] The Chinese remainder theorem gives one class modulo $M_K=450\prod_{j\le r}q_j^2$. Since $2^6\equiv1\pmod9$ and $2^{20}\equiv1\pmod{25}$, all exponents $0\le e\le K$ are killed by a specified prime square. Every member of the class exceeding $2^K$ therefore has $e_{\min}(n)>K$.

Using the standard prime bound $q_j=O(j\log(j+2))$ gives \[ \log M_K\le2r\log r+O(r\log\log(r+2)) =\frac85K\log K+O(K\log\log(K+2)). \] For $K=\lfloor c\log X/\log\log X\rfloor$, $0<c<5/8$, the number of admissible progression members in $(2^K,X]$ is at least \[ \frac{X-2^K}{M_K}-1 \ge X^{1-8c/5-o(1)}. \] Here $2^K=X^{o(1)}$ and $M_K\le X^{8c/5+o(1)}$. Consequently at least this many odd $n\le X$ satisfy $e_{\min}(n)>c\log X/\log\log X$. This improves the supplied method's constant $1/2$ to $5/8$ by a concrete modification of its congruences.

3) ADVERSARIAL VERIFICATION

The condition $n>2^K$ is essential: divisibility of a nonpositive difference is not a failed positive representation. The congruences use distinct prime moduli, so sharing the same residue 1 modulo 9 and 25 causes no compatibility problem. Inclusion--exclusion counts multiples of 60 once. The assertion for the maximum of $e_{\min}$ alone would be vacuous if small exceptional integers already have value $+\infty$; the growing counting statement above avoids relying on that issue.

4) FINAL

UNRESOLVED. This forces a longer initial interval of bad exponents, but leaves roughly $\log_2 n$ admissible exponents in the original problem. It proves neither an eventual squarefree representation nor failure of every admissible exponent for any sufficiently large $n$.

5) SOURCES CHECKED

The supplied file was read in full. Rosser--Schoenfeld, Approximate formulas for some functions of prime numbers $1962$, publisher record https://doi.org/10.1215/ijm/1255631807, checked 2026-09-23; the prime-growth estimate is the only external input. The official problem-page request returned HTTP 403; no claim of a new live status check is made.

6) COMPLETION ESTIMATE

Subjective progress toward the original question, not a probability of correctness. COMPLETION: 15%

Round 3: finite-range CRT obstructions and a lower bound on the least "good" exponent

1) ROUND-3 OBJECTIVE

Path pursued: (C) obstruction / correction of proof-strategy.

Round 2 reduced any genuine counterexample to a covering problem on the exponent interval $E_L=\{0,1,\dots,L\}$ by residue classes modulo orders $\operatorname{ord}_{p^2}(2)$ (Corollary 11.3.1), and isolated a Wieferich-type obstruction to reusing non-Wieferich primes (Corollary 11.4.2). However, the global quantifier gap \[ \forall\ \text{odd }n\ge 3\ \exists e\ge 0:\ n-2^e\ \text{squarefree} \] remains open.

In this round I prove a sharp obstruction to several natural proof strategies: for any fixed finite set of exponents $E$, one can force all shifts $n-2^e$ ($e\in E$) to be divisible by prime squares via CRT. In particular, no approach that searches only a bounded set of exponents (independent of $n$) can ever prove the conjecture.

Moreover, using a mild prime-existence input (Bertrand's postulate), I quantify this obstruction and show that along an explicit infinite sequence of $n$, the least exponent $e$ for which $n-2^e$ could possibly be squarefree must satisfy \[ e \ \gtrsim\ \sqrt{\log_2 n}. \] This is strictly stronger than any result in Rounds 1--2, and it rules out an entire class of "small-$e$" strategies.

2) Round-2 FOUNDATION USED

I use the following Round 2 results as black boxes:

1. Lemma 11.3: For fixed odd prime $p$, the set $\mathcal E_p(n)=\{e\ge 0: p^2\mid(n-2^e)\}$ is either empty or a single residue class modulo $\operatorname{ord}_{p^2}(2)$.
2. Corollary 11.3.1: A counterexample $n$ forces a covering of $E_L$ by such residue classes.
3. Lemma 11.5: Any counterexample can be reduced modulo the product of its certifying prime squares.

(While the new constructions below do not logically require Lemma 11.3, they are best interpreted as producing explicit exponent-coverings of the type isolated in Corollary 11.3.1.)

3) NEW INSIGHT / TOOL (ROUND-3)

New content introduced here:

• Theorem 11.6 (finite-range CRT killing): for any finite set of exponents $E$, there are infinitely many odd $n$ for which every $n-2^e$ ($e\in E$) is divisible by an odd prime square.
• Theorem 11.7 (quantitative obstruction): choosing $E=\{0,1,\dots,K\}$ and selecting primes using Bertrand's postulate yields an explicit upper bound on the constructed $n$ in terms of $K$, implying the lower bound $e_{\min}(n)\gtrsim\sqrt{\log n}$ along an infinite sequence.

4) ATTACK PLAN (ROUND-3)

Gap remaining after Round 2. We still lack a method to guarantee, for each odd $n$, some exponent $e\le \lfloor\log_2(n-1)\rfloor$ such that $n-2^e$ is squarefree.

Round 3 goal. Instead of attempting to close the universal quantifier directly, we:

1. prove that CRT can force arbitrarily long finite blocks of exponents to be "bad" (all shifts divisible by squares),
2. thereby rule out strategies that only test finitely many exponents independent of $n$,
3. quantify the size of such CRT constructions to obtain a lower bound on how large the smallest "good" exponent must sometimes be.

This overcomes a key ambiguity from Round 2: the exponent-covering condition is  easy  to satisfy on a fixed finite set of exponents, so any genuine resolution must exploit the self-referential dependence $L\approx\log_2 n$.

5) WORK (ROUND-3)

5.1. A CRT construction killing any prescribed finite set of exponents

5.2. Quantifying the obstruction: a lower bound on the least possible good exponent

To turn Theorem Theorem (Finite-range CRT killing) into a statement relating $K$ and the size of the constructed $n$, we need a mild way to choose the primes $p_e$ with explicit size control.

6) ADVERSARIAL VERIFICATION

CRT coprimality. In (eq:CRTsystem), the moduli are $2$ and $p_e^2$ for distinct odd primes $p_e$, hence pairwise coprime. CRT applies without further hypotheses.

Parity. Because the nontrivial moduli are odd, the congruences $n\equiv 2^e\pmod{p_e^2}$ do not determine parity. Adding $n\equiv 1\pmod 2$ forces $n$ odd and remains compatible.

Squarefree definition. If an odd prime square $p_e^2$ divides $n-2^e$, then $n-2^e$ is not squarefree by definition. No other hidden assumption is used.

Edge cases ($K=0,1$). For $K=0$, one can take $p_0=3$ and obtain solutions $n\equiv 1\pmod{18}$, so $n-1$ is divisible by $9$ (hence not squarefree); this matches the theorem. For $K=1$, choosing $p_0=3,p_1=5$ yields an explicit CRT system with solutions, forcing both $n-1$ and $n-2$ to be divisible by odd prime squares.

Use of Bertrand. Lemma Lemma (Bertrand's postulate (external input)) is the only external input. The disjoint-interval choice ensures distinct primes and yields the claimed size bound. If Bertrand were replaced by a weaker prime-existence bound, the qualitative Theorem Theorem (Finite-range CRT killing) would remain valid (it needs only infinitely many distinct odd primes), but the quantitative inequality in Theorem Theorem (Quantitative finite-range killing) would weaken.

Interaction with Round 2 Wieferich obstruction. The present constructions do not reuse primes across multiple exponents, so Corollary 11.4.2 is not invoked. This is consistent: Theorem Theorem (Finite-range CRT killing) deliberately chooses the least efficient covering (one prime per exponent). Any attempt to make a true counterexample must cover $E_L$ with far fewer primes, hence must reuse primes, where the Wieferich obstruction becomes relevant.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

We still do not have a proof (or disproof) of the global statement for all odd $n\ge 3$. However, Round 3 proves two new theorems that substantially sharpen the obstruction landscape:

• For any fixed finite exponent set $E$, CRT produces infinitely many odd $n$ for which all $n-2^e$ ($e\in E$) are divisible by odd prime squares (Theorem Theorem (Finite-range CRT killing)). Hence any proof strategy confined to finitely many exponents cannot succeed.
• Quantitatively, there exist infinitely many odd $n$ for which every $e\le \sqrt{\log_2 n}-2$ is "bad" (Theorem Theorem (Quantitative finite-range killing)). Thus the least possible exponent witnessing the conjectured representation must sometimes be at least on the order of $\sqrt{\log n}$.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 62%

9) REFERENCES

• Bertrand's postulate (Chebyshev): for every $m>1$ there is a prime $p$ with $m<p<2m$. (Used only for Lemma Lemma (Bertrand's postulate (external input)) and Theorem Theorem (Quantitative finite-range killing).)