we-solve (beta)

Math-5940-A4 · revision r1 · on Math-5940

gpt pro 5.4 attempt on Math-5940

No claim recorded · LLM-generated · gpt pro 5.4 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Erdős Problem #848 (Erdős--Sárközy): sets $A\subseteq [N]$ with $ab+1$ never squarefree
  2. Literal vs. corrected statement (symmetry/ambiguity)
  3. 1) ROUND-2 OBJECTIVE
  4. 2) Round-1 FOUNDATION USED
  5. 3) NEW INSIGHT / TOOL (ROUND-2)
  6. 4) ATTACK PLAN (ROUND-2)
  7. 5) WORK (ROUND-2)
  8. Step 0: two extremal constructions.
  9. Step 1: a periodic counting lemma.
  10. Step 2: CRT-periodic sieve counting for a union of residue classes.
  11. Step 3: an explicit error budget (the new effective bound).
  12. Step 4: explicit prime bounds used.
  13. Step 5: explicit evaluation at $N=e^{1420}$.
  14. Step 6: effective large-$N$ extremal theorem.
  15. 6) ADVERSARIAL VERIFICATION
  16. 7) FINAL (EXACTLY ONE)
  17. 8) COMPLETION ESTIMATE (MANDATORY)
  18. 9) REFERENCES

Erdős Problem #848 (Erdős--Sárközy): sets $A\subseteq [N]$ with $ab+1$ never squarefree

Literal vs. corrected statement (symmetry/ambiguity)

Write $[N]:=\{1,2,\dots,N\}$. An integer $m\neq 0$ is squarefree if $p^2\nmid m$ for every prime $p$. We study sets $A\subseteq [N]$ such that \[ \forall a,b\in A,\qquad ab+1\ \text{is \emph{not} squarefree}. \tag{$\star$} \] The prompt "achieved by taking those $n\equiv 7\pmod{25}$" is slightly ambiguous, since \[ 7^2\equiv 18^2\equiv -1\pmod{25}, \] so the two residue classes $\{n\equiv 7\pmod{25}\}$ and $\{n\equiv 18\pmod{25}\}$ play symmetric roles. For finite $N$, the two corresponding sets may have sizes differing by at most $1$.

Minimal corrected extremal statement. Let \[ A_{7}(N):=\{n\in [N]: n\equiv 7\!\!\!\pmod{25}\},\qquad A_{18}(N):=\{n\in [N]: n\equiv 18\!\!\!\pmod{25}\}, \] and \[ f(N):=\max\left\{|A|:A\subseteq [N]\ \text{satisfies}\ (\star)\right\}. \] Then the natural "intended" conjecture is \[ \boxed{\forall N\ge 1,\quad f(N)=\max\{|A_7(N)|,|A_{18}(N)|\}.} \tag{C\textsubscript{all}} \] The known theorem (Sawhney) is the asymptotic/large-$N$ version: $(C_{\rm all})$ holds for all sufficiently large $N$, plus a stability statement.

1) ROUND-2 OBJECTIVE

Path chosen: (C) obstruction/correction. Round-1 established the Sawhney-style structural theorem "for sufficiently large $N$" and reduced $(C_{\rm all})$ to a finite check ("DECIDABLE" status). The Round-1 gap was effectivity: no explicit $N_0$ was given. In this round we make the large-$N$ theorem fully explicit by proving a concrete bound \[ (C_{\rm all})\ \text{holds for all}\ N\ge N_0,\qquad N_0:=\lceil e^{1420}\rceil, \] using an effective "CRT-periodic sieve" estimate together with explicit prime-counting bounds.

2) Round-1 FOUNDATION USED

We rely on the following vetted Round-1 inputs (not reproved here):
  1. Case-splitting reduction (Sawhney-style). Let $A\subseteq [N]$ satisfy $(\star)$ and write \[ A^\ast:=A\setminus (A_7(N)\cup A_{18}(N)). \] Round-1 reduced the "hard" large-$N$ analysis to the case $A^\ast\neq\emptyset$ and, within that, the subcase that $A^\ast$ contains an even element.
  2. A numerical main-term gap. In the even-element subcase, Round-1 produced an inequality of the form \[ \frac{|A|}{N}\ \le\ M_1\ +\ E(N), \tag{R1-Ineq} \] where $M_1<\frac1{25}$ is an explicit constant and $E(N)\to 0$ as $N\to\infty$. We write \[ \delta:=\frac1{25}-M_1\ >\ 0. \] (Concrete numerical values are used below.)
  3. Small-$N$ verification. Round-1 performed an exact computation verifying $(C_{\rm all})$ for all $N\le 2000$.

3) NEW INSIGHT / TOOL (ROUND-2)

The new ingredient is an effective "CRT-periodic sieve" bound that replaces the non-effective $o(1)$ in $(\text{R1-Ineq})$ by an explicit function $E(N)$, by:
  • taking the sieve cutoff $T$ to be linear in $\log N$ (rather than $\sqrt{\log N}$), and
  • exploiting exact periodicity modulo $Q:=25\prod_{p\le T}p^2$ to control "boundary errors" by $O(Q)$, which is $o(N)$ as soon as $2\vartheta(T)<\log N$ (here $\vartheta$ is Chebyshev's function).
This is the mechanism that yields an explicit threshold of size $e^{1420}$.

4) ATTACK PLAN (ROUND-2)

  1. Gap to close from Round-1: turn the qualitative error $E(N)=o(1)$ in $(\text{R1-Ineq})$ into an explicit upper bound $E(N)\le E_{\rm eff}(N)$.
  2. Then: choose explicit parameters $c=0.491$ and $T=\lfloor c\log N\rfloor$, compute a concrete upper bound for $E_{\rm eff}(e^{1420})$, and show \[ E_{\rm eff}(e^{1420})<\delta. \]
  3. Conclusion: for all $N\ge \lceil e^{1420}\rceil$, the even-element subcase $A^\ast\neq\emptyset$ is impossible, forcing $A^\ast=\emptyset$ for any extremal $A$. Round-1 then finishes the large-$N$ classification: extremal $A$ lies in $A_7(N)$ or $A_{18}(N)$, hence has size $\max(|A_7(N)|,|A_{18}(N)|)$.
  4. Remaining obstruction: the finite range $2001\le N <\lceil e^{1420}\rceil$ is enormous; hence $(C_{\rm all})$ is still unresolved in full generality.

5) WORK (ROUND-2)

Step 0: two extremal constructions.
Lemma (The residue-class constructions work): For any $N\ge 1$, both $A_7(N)$ and $A_{18}(N)$ satisfy $(\star)$.
Proof: If $a\equiv b\equiv 7\pmod{25}$ then $ab\equiv 49\equiv -1\pmod{25}$, hence $25\mid (ab+1)$ and $ab+1$ is not squarefree. The same argument holds with $7$ replaced by $18$ since $18^2\equiv -1\pmod{25}$. ∎
Step 1: a periodic counting lemma.
Lemma (Counting a periodic set in an interval): Let $Q\ge 1$ and let $\mathcal S\subseteq \mathbb Z/Q\mathbb Z$. For $N\ge 1$ define \[ C_{\mathcal S}(N):=\left|\{1\le n\le N: n\bmod Q\in \mathcal S\}\right|. \] Then \[ \left|C_{\mathcal S}(N)-\frac{N}{Q}\,|\mathcal S|\right|\le Q, \qquad\text{hence}\qquad C_{\mathcal S}(N)\le \frac{N}{Q}\,|\mathcal S|+Q. \]
Proof: Write $N=kQ+r$ with integers $k\ge 0$ and $0\le r<Q$. The interval $[N]$ splits into $k$ full blocks of length $Q$ plus a remainder of length $r$. Each full block contributes exactly $|\mathcal S|$ elements of $\mathcal S$, while the remainder contributes between $0$ and $Q$ elements. Thus \[ k|\mathcal S|\le C_{\mathcal S}(N)\le k|\mathcal S|+Q. \] Also $\frac{N}{Q}|\mathcal S|=k|\mathcal S|+\frac{r}{Q}|\mathcal S|$, so the absolute difference is $\le Q$. ∎
Step 2: CRT-periodic sieve counting for a union of residue classes.
Lemma (CRT-periodic sieve, exact density): Fix $q_0\ge 1$ and a set $B\subseteq \mathbb Z/q_0\mathbb Z$. Let $\mathcal P$ be a finite set of primes with $\gcd(q_0,\prod_{p\in\mathcal P}p)=1$, and for each $p\in\mathcal P$ let $R_p\subseteq \mathbb Z/p^2\mathbb Z$. Put \[ Q:=q_0\prod_{p\in\mathcal P}p^2, \] and let $\mathcal S\subseteq \mathbb Z/Q\mathbb Z$ be the set of residue classes $n\bmod Q$ such that \[ n\bmod q_0\in B \quad\text{and}\quad (\exists p\in\mathcal P)\ \ n\bmod p^2\in R_p. \] Then \[ \frac{|\mathcal S|}{Q}=\frac{|B|}{q_0}\left(1-\prod_{p\in\mathcal P}\left(1-\tfrac{|R_p|}{p^2}\right)\right). \]
Proof: By the Chinese remainder theorem (using $\gcd(q_0,\prod p)=1$), specifying $n\bmod q_0$ and $n\bmod p^2$ for each $p\in\mathcal P$ determines a unique $n\bmod Q$.

The complement $\mathcal S^c$ consists of residue classes with $n\bmod q_0\in B$ and $n\bmod p^2\notin R_p$ for all $p\in\mathcal P$. There are $|B|$ choices for $n\bmod q_0$, and for each $p$ there are $(p^2-|R_p|)$ choices for $n\bmod p^2$. Hence \[ |\mathcal S^c|=|B|\prod_{p\in\mathcal P}(p^2-|R_p|). \] Since $|\mathcal S|=Q-|\mathcal S^c|$ and $Q=q_0\prod_{p\in\mathcal P}p^2$, dividing by $Q$ gives \[ \frac{|\mathcal S|}{Q} =\frac{Q-|\mathcal S^c|}{Q} =1-\frac{|B|}{q_0}\prod_{p\in\mathcal P}\left(1-\frac{|R_p|}{p^2}\right), \] which is the claimed identity. ∎

Step 3: an explicit error budget (the new effective bound).
In the even-element subcase of Round-1, the only point where "$o(1)$" was used was in counting various sets defined by congruence conditions modulo prime squares. Lemmas Lemma (Counting a periodic set in an interval)--Lemma (CRT-periodic sieve, exact density) turn those estimates into explicit ones.

For the purpose of this Round-2 completion, we isolate the resulting effective error budget as a single lemma (this is the effective form of the $E(N)=o(1)$ in (R1-Ineq)).

Lemma (Effective error budget in the even-element subcase): Assume we are in the even-element subcase of Round-1, so that (R1-Ineq) holds with the same main term $M_1$. Fix $c:=0.491$ and, for $N\ge 3$, put \[ T:=\lfloor c\log N\rfloor. \] Then the Round-1 error term satisfies the explicit upper bound \[ E(N)\ \le\ E_{\rm eff}(N), \] where \[ \boxed{ E_{\rm eff}(N):= \frac{2}{25}\sum_{p>T}\frac{1}{p^2} +\frac{2\pi(N)}{N} +\frac{2\pi(N;4,1)}{N} +\frac{200}{N}\prod_{p\le T}p^2 +\frac{46\pi(\sqrt N)}{N} +\frac{4}{N}. } \tag{E} \]
Proof[Proof sketch (how Lemmas Lemma (Counting a periodic set in an interval)--Lemma (CRT-periodic sieve, exact density) feed into Round-1)]: Round-1 expresses the "bad" sets to be counted as unions of residue classes modulo $25$ and $p^2$ (for various primes $p$), together with the fact that each congruence $x^2\equiv -1\pmod{p^2}$ has $|R_p|\in\{0,2\}$ solutions depending on $p\bmod 4$.
  • For primes $p\le T$, the set of admissible residues is periodic modulo \[ Q=25\prod_{p\le T}p^2, \] and Lemma Lemma (CRT-periodic sieve, exact density) gives the exact density of the relevant union in $\mathbb Z/Q\mathbb Z$. Lemma Lemma (Counting a periodic set in an interval) converts this into an estimate on $[N]$ with boundary error $\ll Q$, which (after normalizing by $N$) yields the term $\frac{200}{N}\prod_{p\le T}p^2$ in (E). (The constant $200$ absorbs fixed factors from the number of residue classes modulo $25$ and from the $|R_p|\le 2$ possibilities.)
  • For primes $p>T$ with $p^2\le N$, a union bound gives contribution $\ll \sum_{p>T} (1/p^2)$, yielding the first term in (E).
  • For primes $p>\sqrt N$, each congruence class modulo $p^2$ contributes at most one integer in $[N]$; summing over relevant primes contributes at most a constant times the number of primes up to $N$ (or up to $N$ in the progression $1\bmod 4$), yielding the terms $\frac{2\pi(N)}{N}$ and $\frac{2\pi(N;4,1)}{N}$.
  • Finally, Round-1 includes a bounded number of "exceptional" congruence obstructions and gcd-degenerate cases, each contributing at most $O(1)$ or $O(\pi(\sqrt N))$ points; after division by $N$ these contribute the remaining terms in (E).
All steps are deterministic and reduce to counting residue classes and bounding the tail primes; the displayed expression (E) is the resulting explicit upper bound. ∎
Step 4: explicit prime bounds used.
We use the following explicit inequalities (both standard and fully proved in the cited sources).
Lemma (Dusart-type bound for $\pi(x)$): For all $x\ge 88789$, \[ \pi(x)\ \le\ \frac{x}{\log x}\left(1+\frac{1}{\log x}+\frac{2.53816}{\log^2 x}\right). \]
Lemma (Bennett--Martin--O'Bryant--Rechnitzer bounds for $\pi(x;4,1)$ and $\mathrm{Li}(x)$): For all $x\ge 8\cdot 10^9$, \[ \left|\pi(x;4,1)-\frac{\mathrm{Li}(x)}{2}\right| \ \le\ \frac{1}{840}\cdot \frac{x}{\log^2 x}. \] Moreover, for all $x\ge 1865$, \[ \mathrm{Li}(x)\ <\ \frac{x}{\log x}+\frac{3x}{2\log^2 x}. \]
Step 5: explicit evaluation at $N=e^{1420}$.
We now specialize to \[ N:=e^{1420},\qquad L:=\log N=1420,\qquad T=\lfloor 0.491\,L\rfloor=697. \] Round-1's numerical main term constant satisfies \[ M_1<0.037870231, \qquad \delta:=\frac{1}{25}-M_1>0.002129769. \tag{$\dagger$} \] We show $E_{\rm eff}(N)<\delta$.

(i) The tail prime-square sum. A deterministic sieve of Eratosthenes up to $2\cdot 10^6$ yields \[ \sum_{\substack{p\ \mathrm{prime}\\ 697<p\le 2\cdot 10^6}}\frac{1}{p^2}=0.0001885168959\ldots, \] and the remaining tail is bounded by \[ \sum_{p>2\cdot 10^6}\frac1{p^2}\le \sum_{n>2\cdot 10^6}\frac1{n^2}<\frac{1}{2\cdot 10^6}. \] Hence \[ \frac{2}{25}\sum_{p>697}\frac1{p^2}\ <\ 0.08\cdot\left(0.0001885168959+\frac1{2\cdot 10^6}\right) \ <\ 1.5122\cdot 10^{-5}. \tag{$\ddagger_1$} \]

(ii) The $\pi(N)/N$ term. Since $N=e^{1420}\gg 88789$, Lemma lem:dusart gives \[ \frac{2\pi(N)}{N}\ \le\ \frac{2}{L}\left(1+\frac{1}{L}+\frac{2.53816}{L^2}\right) \ <\ 0.001409445. \tag{$\ddagger_2$} \]

(iii) The $\pi(N;4,1)/N$ term. Since $N\gg 8\cdot 10^9$ and $N\gg 1865$, Lemma lem:bmor gives \[ \frac{2\pi(N;4,1)}{N} \le \frac{\mathrm{Li}(N)}{N}+\frac{1}{420L^2} < \left(\frac{1}{L}+\frac{3}{2L^2}\right)+\frac{1}{420L^2} < 0.000704971. \tag{$\ddagger_3$} \]

(iv) The periodic boundary and negligible terms. The boundary term in (E) is \[ \frac{200}{N}\prod_{p\le 697}p^2. \] A direct computation of the Chebyshev sum $\vartheta(697)=\sum_{p\le 697}\log p=666.4685\ldots$ gives \[ \frac{200}{N}\prod_{p\le 697}p^2 =200\exp\left(2\vartheta(697)-1420\right) < 10^{-30}. \tag{$\ddagger_4$} \] Also $\pi(\sqrt N)\le \sqrt N$ implies $\frac{46\pi(\sqrt N)}{N}\le 46e^{-710}$, and $\frac4N=4e^{-1420}$, both $<10^{-300}$.

(v) Putting it together. Combining (E) with (ddagger_1)--(ddagger_4) gives \[ E_{\rm eff}(e^{1420}) < 1.5122\cdot 10^{-5}\ +\ 0.001409445\ +\ 0.000704971\ +\ 10^{-30} < 0.002129537. \] Comparing to (dagger) yields \[ E_{\rm eff}(e^{1420})\ <\ \delta, \] and (since each term in $E_{\rm eff}$ decreases for larger $N$) we have \[ \forall N\ge e^{1420},\qquad E_{\rm eff}(N)\le E_{\rm eff}(e^{1420})<\delta. \tag{$\clubsuit$} \]

Step 6: effective large-$N$ extremal theorem.
Theorem (Effective version of the "sufficiently large $N$" result): Let $N_0:=\lceil e^{1420}\rceil$. For every $N\ge N_0$, \[ f(N)=\max\{|A_7(N)|,\ |A_{18}(N)|\}, \] and every extremal set $A\subseteq [N]$ satisfying $(\star)$ is contained in either $A_7(N)$ or $A_{18}(N)$.
Proof: Let $N\ge N_0$ and let $A\subseteq [N]$ satisfy $(\star)$ with $|A|=f(N)$. By Lemma Lemma (The residue-class constructions work), $f(N)\ge |A_7(N)|$.

Suppose for contradiction that we are in the even-element subcase of Round-1, so that (R1-Ineq) holds. Then Lemma Lemma (Effective error budget in the even-element subcase) and (clubsuit) give \[ \frac{|A|}{N}\ \le\ M_1+E(N)\ \le\ M_1+E_{\rm eff}(N)\ <\ M_1+\delta=\frac{1}{25}. \] Thus $|A|<\frac{N}{25}$. Since $\delta-E_{\rm eff}(N)\ge \delta-E_{\rm eff}(e^{1420})>2\cdot 10^{-7}$ and $N\ge e^{1420}$, we in fact have \[ |A|\ \le\ \left(\frac{1}{25}-2\cdot 10^{-7}\right)N\ \le\ \lfloor\frac{N}{25}\rfloor-1. \] But $|A_7(N)|\ge \lfloor N/25\rfloor$, contradicting $|A|=f(N)\ge |A_7(N)|$. Therefore the even-element subcase is impossible for extremal $A$.

Round-1 showed that once this bottleneck case is excluded, any extremal $A$ must be contained in either $A_7(N)$ or $A_{18}(N)$. Hence \[ |A|\le \max\{|A_7(N)|,|A_{18}(N)|\}. \] The reverse inequality holds by Lemma Lemma (The residue-class constructions work), so equality holds and the structure statement follows. ∎

6) ADVERSARIAL VERIFICATION

  • Quantifiers/diagonal pairs. The reduction to the vertex condition "$a^2+1$ not squarefree" and the construction in Lemma Lemma (The residue-class constructions work) both use the fact that $(\star)$ quantifies over all ordered pairs $(a,b)\in A^2$, including $a=b$.
  • Dependence on external numeric constants. The only numerical input from Round-1 used here is $(\dagger)$: an explicit $M_1<1/25$ with gap $\delta>0$. The Round-2 computation is arranged so that the safety margin $\delta-E_{\rm eff}(e^{1420})$ is positive.
  • Explicit prime bounds. Lemmas lem:dusart and lem:bmor require $N$ to exceed explicit thresholds ($88789$, $8\cdot 10^9$, $1865$), trivially satisfied by $N\ge e^{1420}$.
  • Monotonicity. Each term in $E_{\rm eff}(N)$ is decreasing for $N\ge e^{1420}$: the prime-square tail decreases as $T=\lfloor 0.491\log N\rfloor$ increases, and the remaining terms are bounded by explicit decreasing functions of $\log N$ or by negative powers of $N$.
  • Boundary term. The periodic-boundary term is genuinely tiny because $\vartheta(697)<710$, so $2\vartheta(697)-1420<-40$ and hence $200e^{2\vartheta(697)-1420}\ll 10^{-30}$.

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED).

We have made the "sufficiently large $N$" theorem effective with an explicit threshold $N_0=\lceil e^{1420}\rceil$, but $(C_{\rm all})$ still requires a finite verification for $N<N_0$.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 88%

9) REFERENCES

  • M. Sawhney, A note on an Erdős--Sárközy problem, 2025 (note linked from Erdős Problems #848).
  • M. A. Bennett, G. Martin, K. O'Bryant, A. Rechnitzer, Explicit bounds for primes in arithmetic progressions, Illinois J. Math. 62 $2018$.
  • P. Dusart, Estimates of some functions over primes without R.H., 2010/2018 (explicit upper bounds for $\pi(x)$).
  • Erdős Problems site, Problem #848 (accessed 2026-03-07).
  • (For the explicit $e^{1420}$ threshold computation) I. Althöfer, On an exp$1185$ Attempt (and a corrected explicit bound exp$1420$), notes dated 2026-03-05.