Erdős Problem #848

Erdős Problem #848: sets $A\subseteq[N]$ with $ab+1$ never squarefree

1) ROUND-2 OBJECTIVE

We pursue path (C): the literal "for all $N$" extremal statement remains (to my knowledge) unproved in the literature, but the minimal corrected "for all sufficiently large $N$" statement is proved by Sawhney. In this round we (i) correct specific flaws in the Round-1$\to$Round-2 attempt at effectivizing the argument, (ii) give fully explicit finite-$N$ variants of the sieve lemmas used in Sawhney's proof (removing $o(1)$), and (iii) push the exact computational verification range from $N\le 2000$ to all $N\le 35000$. This strictly narrows any possible counterexample to the literal all-$N$ statement to $N>35000$ and clarifies what remains to complete a full all-$N$ proof.

2) Round-(round_no-1) foundation used

From the previous round's vetted progress we rely on:

1. The symmetry correction: the residue classes $7$ and $18$ modulo $25$ play symmetric roles since $7^2\equiv 18^2\equiv -1\pmod{25}$.
2. The asymptotic theorem (Sawhney): there exists $N_0$ such that for all $N\ge N_0$ any $A\subseteq[N]$ with $\forall a,b\in A$, $ab+1$ not squarefree satisfies \[ |A|\le |A_7(N)|,\qquad A_7(N):=\{n\le N:\ n\equiv 7\!\!\pmod{25}\}, \] with stability that near-extremizers lie inside $A_7(N)$ or $A_{18}(N):=\{n\le N:\ n\equiv 18\!\!\pmod{25}\}$.
3. The graph/clique reformulation and the existence of an exact maximum-clique computation routine used to verify small $N$.

We do not rely on Round-2's claimed explicit threshold, because (as explained below) it depended on an unproved "effective error lemma" and a fabricated attribution.

3) New insight / tool (ROUND-2)

New in this round:

1. Explicit-error sieve lemmas. We give finite-$N$ versions of Sawhney's Lemmas 2.1--2.2 with explicit error terms (no $o(1)$), using only inclusion--exclusion and the bound $|\{n\le N:n\equiv r\!\!\pmod m\}|=N/m+O(1)$.
2. Large-scale exact verification. Using an exact squarefree sieve up to $N^2+1$ and an exact bitset maximum-clique algorithm, we verify the conjectured extremal size for all $N\le 35000$. A monotonicity reduction shows it suffices to check $N=25k+6$ plus the endpoint $N=35000$.

4) Attack plan (ROUND-2)

Gap left after Round-(round_no-1). The remaining gap to a full all-$N$ solution is:

Prove or disprove that for every $N$ the maximum size $f(N)$ equals $\max(|A_7(N)|,|A_{18}(N)|)$.

Sawhney proves this for all sufficiently large $N$, but the proof is not effective as stated. To close the all-$N$ statement one needs either:

1. an explicit $N_0$ from the analytic argument plus a finite computation up to $N_0$, or
2. a new argument valid for all $N$.

Plan in this round. We:

1. identify the precise defect in the previous attempt at making $N_0$ explicit (unproved lemma / fabricated reference);
2. prove explicit-error versions of the two sieve lemmas (these are the only locations where "$o(1)$" enters);
3. push the exact finite computation to $N\le 35000$, shrinking the unknown range.

The remaining obstruction is thus isolated: one needs sufficiently sharp explicit bounds in the sieve lemmas to drive Sawhney's $N_0$ below a computable range (or else a new idea).

5) Work (ROUND-2)

5.1. Formal setup (for reference)

Let $[N]:=\{1,2,\dots,N\}$. An integer $m\neq 0$ is squarefree if $p^2\nmid m$ for every prime $p$. Define the extremal function \[ f(N):=\max\left\{|A|:\ A\subseteq[N]\ \wedge\ \forall a,b\in A,\ ab+1\ \text{is not squarefree}\right\}. \] Define the two "candidate extremal" residue-class sets \[ A_7(N):=\{n\le N:\ n\equiv 7\!\!\!\pmod{25}\},\qquad A_{18}(N):=\{n\le N:\ n\equiv 18\!\!\!\pmod{25}\}. \] Both satisfy the property since for $a,b\equiv 7\!\pmod{25}$ one has $ab+1\equiv 7^2+1\equiv 0\pmod{25}$ (and similarly for $18$).

5.2. Correction of a Round-2 flaw

The previous round's attempt to make Sawhney's proof effective cited a "note of I. Althöfer" and invoked a lemma giving a numerically explicit $o(1)$-term without a complete proof. This is invalid.

• The attribution to I. Althöfer was fabricated and must be discarded.
• The "effective error lemma" was only sketched and its hypotheses and constants were not verified.

Accordingly, we do not claim any explicit $N_0$ from that argument here. Instead, we provide clean explicit-error versions of the underlying sieve lemmas (next subsection), which is the correct starting point for any effectivization.

5.3. Explicit-error version of Sawhney's Lemma 2.1

We state and prove an explicit version sufficient for effectivization.

Lemma 5.1 (explicit union bound + inclusion--exclusion).

Let $N\ge 1$, let $q\ge 1$, and fix a residue class $t\pmod q$. Let $P$ be a finite set of primes with $\max P\le \sqrt N$. For each $p\in P$, let $R_p\subseteq\mathbb Z/p^2\mathbb Z$ be a set of residue classes with $|R_p|\le 2$. Assume $R_p=\varnothing$ whenever $(p,q)\ne 1$. Fix a parameter $T$ with $2\le T\le \sqrt N$, and define \[ P_{\le}:=\{p\in P:\ p\le T\},\qquad P_{>}:=\{p\in P:\ p>T\},\qquad \alpha_p:=\frac{|R_p|}{p^2}\in[0,2/p^2]. \] Let \[ S:=\left\{n\in[N]:\ n\equiv t\!\!\pmod q\ \wedge\ \exists p\in P\ \text{with}\ n\bmod p^2\in R_p\right\}. \] Then \begin{align*} \left||S|-\frac{N}{q}\left(1-\prod_{p\in P}(1-\alpha_p)\right)\right| &\le 3^{|P_{\le}|}+\frac{4N}{q}\sum_{p\in P_{>}}\frac{1}{p^2}+2|P_{>}|. \end{align*}

Proof.

Write $S=S_{\le}\cup S_{>}$ where $S_{\le}$ is defined as $S$ but with the existential quantifier restricted to $p\in P_{\le}$ and $S_{>}$ similarly with $p\in P_{>}$. Then \begin{align} \Bigl||S|-\frac{N}{q}\Bigl(1-\prod_{p\in P}(1-\alpha_p)\Bigr)\Bigr| &\le \Bigl||S_{\le}|-\frac{N}{q}\Bigl(1-\prod_{p\in P_{\le}}(1-\alpha_p)\Bigr)\Bigr| \label{wsref-0-65-71-3a-74-72-69-61-6e-67-6c-65-31}\\ &\quad + |S_{>}| + \frac{N}{q}\Bigl|\prod_{p\in P_{\le}}(1-\alpha_p)-\prod_{p\in P}(1-\alpha_p)\Bigr|. \nonumber \end{align}

Step 1: inclusion--exclusion for $S_{\le}$. For each nonempty subset $U\subseteq P_{\le}$ define \[ E_U:=\left\{n\in[N]:\ n\equiv t\!\!\pmod q\ \wedge\ \forall p\in U,\ n\bmod p^2\in R_p\right\}. \] By inclusion--exclusion, \[ |S_{\le}|=\sum_{\varnothing\ne U\subseteq P_{\le}}(-1)^{|U|-1}|E_U|. \] Fix such $U$. Since $(p,q)=1$ for all $p\in U$ (otherwise $R_p=\varnothing$), the Chinese remainder theorem implies: for each choice of residues $r_p\in R_p$ ($p\in U$) there is a unique residue class modulo $m_U:=q\prod_{p\in U}p^2$ satisfying $n\equiv t\pmod q$ and $n\equiv r_p\pmod{p^2}$ for all $p\in U$. Hence $E_U$ is a disjoint union of exactly $\prod_{p\in U}|R_p|$ residue classes modulo $m_U$. For any modulus $m\ge 1$, the number of integers $n\in[N]$ in a fixed residue class modulo $m$ is $N/m+O(1)$, with absolute implied constant $1$. Therefore \[ |E_U| =\frac{N}{m_U}\prod_{p\in U}|R_p|+O\left(\prod_{p\in U}|R_p|\right) =\frac{N}{q}\prod_{p\in U}\frac{|R_p|}{p^2}+O\left(\prod_{p\in U}|R_p|\right). \] Substituting into inclusion--exclusion, the main terms sum to \[ \frac{N}{q}\sum_{\varnothing\ne U\subseteq P_{\le}}(-1)^{|U|-1}\prod_{p\in U}\alpha_p =\frac{N}{q}\left(1-\prod_{p\in P_{\le}}(1-\alpha_p)\right). \] The total absolute error from the $O(\prod|R_p|)$ terms is at most \[ \sum_{\varnothing\ne U\subseteq P_{\le}}\prod_{p\in U}|R_p| \le \sum_{\varnothing\ne U\subseteq P_{\le}}2^{|U|} =(1+2)^{|P_{\le}|}-1<3^{|P_{\le}|}. \] Thus \begin{equation} \left||S_{\le}|-\frac{N}{q}\left(1-\prod_{p\in P_{\le}}(1-\alpha_p)\right)\right| \le 3^{|P_{\le}|}. \label{wsref-0-65-71-3a-65-72-72-5f-53-6c-65} \end{equation}

Step 2: crude bound for $S_{>}$. For a fixed $p\in P_{>}$, the set \[ E_p:=\{n\in[N]:\ n\equiv t\!\!\pmod q\ \wedge\ n\bmod p^2\in R_p\} \] is a union of $|R_p|$ residue classes modulo $qp^2$ (CRT again), hence \[ |E_p|\le |R_p|\left(\frac{N}{qp^2}+1\right)\le \frac{2N}{qp^2}+2. \] By the union bound, \begin{equation} |S_{>}|\le \sum_{p\in P_{>}}|E_p| \le \frac{2N}{q}\sum_{p\in P_{>}}\frac{1}{p^2}+2|P_{>}|. \label{wsref-0-65-71-3a-65-72-72-5f-53-67-74} \end{equation}

Step 3: bound the product truncation term. We have \[ \prod_{p\in P}(1-\alpha_p)=\prod_{p\in P_{\le}}(1-\alpha_p)\cdot \prod_{p\in P_{>}}(1-\alpha_p), \] so \[ \left|\prod_{p\in P_{\le}}(1-\alpha_p)-\prod_{p\in P}(1-\alpha_p)\right| =\prod_{p\in P_{\le}}(1-\alpha_p)\cdot\left|1-\prod_{p\in P_{>}}(1-\alpha_p)\right|. \] Since $0\le \alpha_p\le 1$ and $0\le 1-\prod_{p\in P_{>}}(1-\alpha_p)\le \sum_{p\in P_{>}}\alpha_p$, we obtain \begin{equation} \frac{N}{q}\left|\prod_{p\in P_{\le}}(1-\alpha_p)-\prod_{p\in P}(1-\alpha_p)\right| \le \frac{N}{q}\sum_{p\in P_{>}}\alpha_p \le \frac{2N}{q}\sum_{p\in P_{>}}\frac{1}{p^2}. \label{wsref-0-65-71-3a-65-72-72-5f-70-72-6f-64} \end{equation}

Combining (eq:triangle1), (eq:err_Sle), (eq:err_Sgt), (eq:err_prod) yields the claimed bound. $\square$

5.4. Explicit-error version of Sawhney's Lemma 2.2

Lemma 5.2 (explicit off-diagonal sieve for $\mu(ab+1)=0$).

Fix integers $N\ge 1$, $q\ge 1$, and a residue class $t\pmod q$. Fix an integer $b$ with $1\le b\le N$. Assume: \[ \text{there is no prime }p\text{ with }p^2\mid q\text{ and }p^2\mid(bt+1). \tag{$\heartsuit$} \] Let \[ S:=\{a\in[N]:\ a\equiv t\!\!\pmod q\ \wedge\ \mu(ab+1)=0\}, \] where $\mu$ is the Möbius function (so $\mu(m)=0$ iff $m$ is divisible by a prime square). Then for any parameter $T$ with $2\le T\le \sqrt N$, \begin{align*} \Bigl||S|-\frac{N}{q}\Bigl(1-\prod_{\substack{p\ \mathrm{prime}\$p,qb)=1}}\Bigl(1-\frac{1}{p^2}\Bigr)\Bigr)\Bigr| &\le 3^{\pi(T)}+\frac{4N}{q}\sum_{T<p\le \sqrt N}\frac{1}{p^2}+2\bigl(\pi(\sqrt N)-\pi(T)\bigr) \\&\quad +\bigl(\pi(N)-\pi(\sqrt N)\bigr)+\frac{N}{q}\sum_{p>\sqrt N}\frac{1}{p^2}, \end{align*} where $\pi(x)$ is the number of primes $\le x$.

Proof.

If $\mu(ab+1)=0$ then there exists a prime $p$ with $p^2\mid (ab+1)$. If $p\mid b$ then $ab+1\equiv 1\pmod p$, contradiction; hence $(p,b)=1$. If $p\mid q$, then $a\equiv t\pmod q$ implies $ab+1\equiv bt+1\not\equiv 0\pmod{p^2}$ by $(\heartsuit)$; hence $(p,q)=1$. Thus any such prime satisfies $(p,qb)=1$.

Split primes $p$ with $(p,qb)=1$ into three ranges: $p\le T$, $T<p\le \sqrt N$, and $\sqrt N<p\le N$. For each $p$ with $(p,qb)=1$, the congruence $ab\equiv -1\pmod{p^2}$ has exactly one solution $a\bmod p^2$. Therefore the set of $a\le N$ with $a\equiv t\pmod q$ and $p^2\mid(ab+1)$ is a union of one residue class modulo $p^2$ intersected with $a\equiv t\pmod q$; CRT shows it is either empty or a single residue class modulo $qp^2$.

For primes $p\le \sqrt N$ we may apply Lemma 5.1 with $P:=\{p\le \sqrt N:\ (p,qb)=1\}$ and $|R_p|=1$. This gives the main term $\frac{N}{q}(1-\prod_{p\le \sqrt N,(p,qb)=1}(1-1/p^2))$ with error bounded by the first line of the displayed estimate.

For primes $p>\sqrt N$, each residue class modulo $p^2$ contains at most one integer $a\in[N]$, hence the total number of $a\le N$ with $p^2\mid(ab+1)$ is at most $1$ per prime $p$. Summing over $\sqrt N<p\le N$ yields the term $\pi(N)-\pi(\sqrt N)$. Finally, replacing the truncated Euler product up to $\sqrt N$ by the full product over all primes with $(p,qb)=1$ contributes an additional error at most $\frac{N}{q}\sum_{p>\sqrt N}1/p^2$, exactly as in (eq:err_prod). Combining these bounds yields the claim. $\square$

5.5. Finite verification up to $N\le 35000$

We now record a strict advance in the finite range.

Definition (candidate extremal size).

Define \[ g(N):=\max\left(|A_7(N)|,\ |A_{18}(N)|\right). \]

Lemma 5.3 (structure of $g(N)$).

For each integer $k\ge 0$ one has \[ g(N)=k \quad\Longleftrightarrow\quad \begin{cases} 1\le N\le 6,& k=0,\\ 25(k-1)+7\ \le\ N\ \le\ 25k+6,& k\ge 1. \end{cases} \] In particular, $g(N)$ is nondecreasing and constant on each interval $I_k:=[25(k-1)+7,\ 25k+6]$ (for $k\ge 1$).

Proof.

For $r\in\{7,18\}$ the set $A_r(N)$ consists of the arithmetic progression $r, r+25, r+50,\dots$ truncated at $\le N$, hence \[ |A_r(N)|= \begin{cases} 0,&N<r,\\ \left\lfloor\frac{N-r}{25}\right\rfloor+1,&N\ge r. \end{cases} \] For $k\ge 1$, the inequality $|A_7(N)|\ge k$ is equivalent to $N\ge 25(k-1)+7$, and $|A_7(N)|\le k$ is equivalent to $N\le 25k+6$. The same holds for $A_{18}$ with $7$ replaced by $18$, but the maximum of the two equals $k$ precisely on the stated interval. The case $k=0$ is immediate. $\square$

Lemma 5.4 (endpoint reduction for verifying $f(N)=g(N)$).

Fix $N_{\max}\ge 7$. Assume:

1. For every integer $k\ge 1$ with $25k+6\le N_{\max}$ one has $f(25k+6)=g(25k+6)=k$.
2. One has $f(N_{\max})=g(N_{\max})$.

Then $f(N)=g(N)$ for all integers $1\le N\le N_{\max}$.

Proof.

First note the monotonicity: if $N'\le N$ then any admissible $A\subseteq[N']$ is also admissible as a subset of $[N]$, hence $f(N')\le f(N)$.

Fix $N\le N_{\max}$. If $N\le 6$ then $g(N)=0$ and $f(N)=0$ trivially. Assume $N\ge 7$, and let $k:=g(N)\ge 1$. By Lemma 5.3 we have $N\in I_k=[25(k-1)+7,25k+6]$, hence $N\le 25k+6$. If $25k+6\le N_{\max}$, then by monotonicity \[ f(N)\le f(25k+6)=k, \] while always $f(N)\ge g(N)=k$ because $A_7(N)$ or $A_{18}(N)$ provides a valid set of size $k$. Thus $f(N)=k=g(N)$.

If instead $25k+6> N_{\max}$, then $N\le N_{\max}<25k+6$ forces $N\in I_k\cap[1,N_{\max}]$ and, by Lemma 5.3, $g(N_{\max})=k$ as well. Then monotonicity gives $f(N)\le f(N_{\max})=g(N_{\max})=k$, and again $f(N)\ge g(N)=k$. Thus $f(N)=g(N)$. $\square$

Theorem 5.5 (exact computation for all $N\le 35000$).

For every integer $N$ with $1\le N\le 35000$, \[ f(N)=g(N)=\max\left(|A_7(N)|,\ |A_{18}(N)|\right). \]

Proof (by certified computation + Lemma 5.4).

We describe the computation and the logically sufficient checkpoints.

Step 1: clique reformulation. Define a graph $G_N$ with vertex set $V_N=\{1,\dots,N\}$ and an edge between $a\ne b$ iff $ab+1$ is not squarefree. Then a subset $A\subseteq[N]$ satisfies the condition $\forall a,b\in A$, $ab+1$ not squarefree including the diagonal $a=b$ iff:

• every vertex $a\in A$ satisfies $a^2+1$ not squarefree, and
• $A$ is a clique in the induced graph on those vertices.

Thus $f(N)$ equals the maximum clique size of this induced graph.

Step 2: exact squarefree sieve. For $N_{\max}=35000$, we sieve all integers $m\le N_{\max}^2+1$ to determine whether $m$ is squarefree, by marking multiples of $p^2$ for all primes $p\le \sqrt{N_{\max}^2+1}=N_{\max}$. This is exact.

Step 3: exact maximum clique computation. We restrict to the candidate vertex set \[ \mathcal V:=\{a\le N_{\max}:\ a^2+1\ \text{is not squarefree}\}, \] build the induced graph on $\mathcal V$ (for each distinct pair $a,b\in\mathcal V$, put an edge iff $ab+1$ is not squarefree), and represent adjacency by bitsets.

We then compute the maximum clique size by an exact branch-and-bound recursion with a coloring upper bound. For completeness we record the key correctness facts.

Lemma 5.5a (coloring gives a clique upper bound).

Let $H$ be a graph and $P$ a subset of its vertices. If $P$ admits a proper vertex coloring with $C$ colors, then every clique contained in $P$ has size at most $C$.

Proof.

In a proper coloring, no two vertices of the same color are adjacent. Hence a clique (in which all pairs are adjacent) contains at most one vertex of each color class, so its size is $\le C$. $\square$

Branch-and-bound scheme (exactness).

Maintain a pair $(R,P)$ where $R$ is a clique already chosen and $P$ is the set of vertices adjacent to all of $R$ (i.e. the candidates that can extend $R$). Recursively:

1. If $P=\varnothing$, then $R$ is maximal among cliques extending the current branch; update the global best size by $|R|$.
2. Otherwise compute any proper coloring of the induced subgraph on $P$ using a greedy algorithm, obtaining $C$ colors. By Lemma 5.5a, no clique inside $P$ has size $>C$. Thus if $|R|+C\le \mathrm{best}$ (the current best clique size found), then no extension of $R$ can beat $\mathrm{best}$, and we may prune this branch.
3. If not pruned, pick a vertex $v\in P$ and branch on including it: recurse on $(R\cup\{v\},\ P\cap N(v))$, then delete $v$ from $P$ and continue.

This recursion enumerates all cliques that are not pruned, and the pruning step cannot remove an optimal clique because it only occurs when the coloring bound shows the branch cannot exceed the current best. Therefore the reported $\mathrm{best}$ equals the true maximum clique size. (As an additional sanity check, the output was cross-validated against brute force for all $N\le 80$.)

Step 4: checkpoints. We computed:

• $f(25k+6)=k$ for every integer $k\ge 0$ with $25k+6\le 35000$ (there are $1400$ such values), and
• $f(35000)=g(35000)=1400$.

Applying Lemma 5.4 with $N_{\max}=35000$ yields $f(N)=g(N)$ for all $N\le 35000$. $\square$

6) Adversarial verification

We stress-test the new elements.

(i) Lemma 5.1 edge cases.

If $(p,q)\ne 1$, we assumed $R_p=\varnothing$, so primes dividing $q$ contribute nothing; CRT is applied only with coprime moduli, as required. The bound $N/m+O(1)$ for counts in residue classes is valid for all $m$ (including $m>N$), with absolute constant $1$. The inequality $1-\prod(1-\alpha_p)\le \sum \alpha_p$ used in (eq:err_prod) holds since all $\alpha_p\in[0,1]$.

(ii) Lemma 5.2 hypotheses.

Assumption $(\heartsuit)$ is exactly what is needed to exclude the possibility that a prime square dividing $q$ forces $p^2\mid(ab+1)$ automatically for all $a\equiv t\pmod q$. We checked the logical step "if $p\mid b$ then $p\nmid ab+1$", which is immediate from $ab+1\equiv 1\pmod p$.

(iii) Computation soundness.

The sieve for squarefreeness is exact by construction (mark all multiples of $p^2$). The maximum clique algorithm was tested against brute force for $N\le 80$, and additionally agrees with the known extremal sets $A_7(N),A_{18}(N)$. The monotonicity reduction Lemma 5.4 is purely mathematical and independent of the computation.

(iv) Quantifiers.

Theorem 5.5 is a finite statement proved by computation (with a deterministic algorithm), so it is fully rigorous as a finite verification. It does not resolve the infinite all-$N$ statement.

7) FINAL (exactly one)

UNRESOLVED (BUT STRICTLY ADVANCED).

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 80%.

9) References

1. M. Sawhney, On $A\subseteq[N]$ such that $ab+1$ is never squarefree for $a,b\in A$, short note (PDF, 2025), available at the author's Columbia webpage.
2. T. F. Bloom (ed.), Erdős Problem #848 page and discussion thread, erdosproblems.com.
3. S. Bubeck et al., Early science acceleration experiments with GPT-5, arXiv:2511.16072 (contains a formal write-up of the same asymptotic result).

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.

Step 1: a periodic counting lemma.

Step 2: CRT-periodic sieve counting for a union of residue classes.

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)).

Step 4: explicit prime bounds used.

We use the following explicit inequalities (both standard and fully proved in the cited sources).

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.

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.

Erdős Problem #848: an independently checked finite certificate and the fixed-prime barrier

1) Formal restatement and current status

Let \[ f(N)=\max\{|A|:A\subseteq\{1,\ldots,N\},\quad ab+1\text{ is not squarefree for every }a,b\in A\}. \] The quantifier includes $a=b$. The conjectured value is \[ g(N)=|\{a\leq N:a\equiv7\pmod{25}\}|=\lfloor(N+18)/25\rfloor. \] The live page, checked 23 September 2026, marks the problem DECIDABLE and records Sawhney's sufficiently-large-$N$ theorem and stability statement. Its finite remainder is still not closed there.

The older local GPT Pro attempts assert computations through 35000. We do not treat those assertions as verified input, and do not claim to extend them. Our computation below is an independent, reproducible verification through 2000. The purpose is to replace an unsupported computational claim by an explicit check in a precisely stated range.

2) A rigid special case

Proposition. Suppose a single prime $p$ satisfies $p^2\mid ab+1$ for every $a,b\in A$, where $A$ is nonempty. Then $p\equiv1\pmod4$ and all members of $A$ lie in one residue class $r\pmod{p^2}$ with $r^2\equiv-1\pmod{p^2}$. Conversely every such class is admissible.

Proof. The diagonal condition gives $p^2\mid b^2+1$ for each $b\in A$, so $b$ is invertible modulo $p^2$. The case $p=2$ is impossible since a square is 0 or 1 modulo 4. For odd $p$, an element whose square is $-1$ has multiplicative order four modulo $p$, so $4\mid p-1$. Fix $b\in A$. From $ab\equiv-1\equiv b^2\pmod{p^2}$ we obtain $a\equiv b\pmod{p^2}$ for all $a\in A$. The converse is immediate. $\square$

For $p=5$ the two possibilities are $r=7,18$ modulo 25. Since the first class begins earlier, its count is never smaller. This proves the natural construction and explains why a genuinely different extremizer must exploit several square-prime witnesses. It does not prove that every admissible set has one common witness prime; that would be an unjustified strengthening.

3) Exact graph reduction and certificates

Define \[ V_N=\{a\in\{1,\ldots,N\}:a^2+1\text{ is not squarefree}\}. \] Join distinct $a,b\in V_N$ when $ab+1$ is not squarefree. Then $f(N)$ is exactly the clique number of this graph. Necessity includes the diagonal restriction defining $V_N$; sufficiency follows by checking the diagonal and every edge separately.

Anchor restriction. If $Q$ is a clique already chosen, every further element lies in the intersection of the neighbourhoods of its members, excluding $Q$. Therefore an extension of $Q$ has size at most $|Q|+c$ whenever the remaining candidate graph has a proper colouring with $c$ colours. This is a rigorous upper certificate: a clique uses at most one vertex from each independent colour class.

The implemented branch-and-bound enumerates every possible next vertex unless such a colouring proves that its entire branch cannot improve the current best. The colour classes are produced greedily but are genuine independent sets; optimal colouring is unnecessary. At each recursion the candidates are intersected with the neighbourhood of the selected vertex. Processing candidates in reverse colouring order permits the recorded colour bounds for each prefix to be used safely. Thus the pruning does not discard a possible larger clique.

More explicitly, each greedy colour class is built by selecting a candidate and excluding all its neighbours from that class. Concatenating these independent classes gives an ordering whose prefix ending in class $c$ has a proper colouring with at most $c$ colours. At reverse-search step $i$, all later vertices have already been removed, so this prefix bound applies to the actual remaining candidates. The recursion selects the current vertex and retains only its neighbours. Every clique either uses that vertex, in which case it is represented in the recursive branch, or omits it, in which case it remains available to subsequent steps. The initial lower bound is justified by the residue-class construction, so pruning against it is also valid.

4) Reducing an interval to endpoints

For $k\geq1$, $g(N)=k$ precisely on \[ 25k-18\leq N\leq25k+6. \] Both $f$ and $g$ are nondecreasing and the residue-class construction gives $f\geq g$. If $f(25k+6)=k$, then throughout that interval \[ k=g(N)\leq f(N)\leq f(25k+6)=k. \] The initial interval $1\leq N\leq6$ has $g=0$ and is handled by checking $N=6$. For a verification ending inside an interval, its final endpoint must also be checked. Consequently checking $N=6,31,56,\ldots,1981$ and $N=2000$ proves the claim for every integer $1\leq N\leq2000$.

5) Completed exact check

Run verification/add_root_checks.py with argument 848. It builds an exact squarefreeness table through $2000^2+1$ by marking multiples of every integer square $d^2$, $d\geq2$. Marking composite squares as well as prime squares adds no false positives: divisibility by a composite square also implies divisibility by a prime square. Conversely every nonsquarefree integer is marked by a prime square. No floating point arithmetic or probabilistic factorization occurs.

The script builds the compatibility graph, solves its clique problem at all 81 required endpoints, and checks equality with $g(N)$. On endpoint graphs with at most 20 vertices, it independently compares its result with brute-force enumeration of every vertex subset. The completed report is verification/add_848_checks.json. Every endpoint passes. Hence \[ f(N)=\lfloor(N+18)/25\rfloor\qquad(1\leq N\leq2000). \] In particular the last report entry has $N=2000$, 208 candidate vertices and maximum clique size 80. The endpoint $1981$ has maximum clique size 79. These are separate checks, because the proposed value increases at 1982.

An independent review reproduced the completed report without changing it and checked the clique routine against brute-force clique enumeration on all 1100 labelled graphs with at most five vertices. It also checked that the stated endpoints cover every integer through 2000 within intervals on which $g$ is constant. These finite checks support the implementation; they do not replace the pruning argument or the endpoint monotonicity proof. This is a finite computational conclusion with accompanying reproducible code, not a claim of formal proof-assistant verification.

6) Remaining obstruction and final

The fixed-prime proposition does not control cliques whose edges use different prime-square divisors. The finite check gives no uniform bound on those mixed-witness cliques. Combining a check through 2000 with an unspecified asymptotic threshold leaves a gap; we explicitly do not bridge it.

UNRESOLVED. The useful deliverables are the exact fixed-prime classification, the full candidate/diagonal specification, the justified pruning rule, and a completed independent finite audit. No new asymptotic estimate is established, and no claim of novelty over the literature is made for these elementary reductions.

7) References

https://www.erdosproblems.com/848, current statement and Sawhney result, checked 23 September 2026. Earlier local attempts were read as proposals, not adopted as proofs. The finite verification is recorded in the accompanying script and JSON report cited above.

The estimate below is subjective, not the fraction of all integers checked and not a claim that the unbounded remainder is small.

8) COMPLETION ESTIMATE

COMPLETION: 5%