Largest subset of $\{1,\ldots,N\}$ whose pairwise sums are all squarefree (Erdős #1109)
Statement
Let $f(N)$ be the size of the largest subset $A\subseteq\{1,\ldots,N\}$ such that every element of the sumset $A+A=\{a+b : a,b\in A\}$ is squarefree (divisible by $p^2$ for no prime $p$). Estimate $f(N)$. In particular, is it true that $f(N)\leq N^{o(1)}$, or even that $f(N)\leq(\log N)^{O(1)}$?
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable in Lean preferred, otherwise a full written proof) determining the order of $f(N)$ — in particular settling whether $f(N)\leq N^{o(1)}$, or whether $f(N)\leq(\log N)^{O(1)}$ — with matching bounds. ADVANCES: a proof strictly improving either best stated bound of Konyagin — the lower bound $\log\log N\,(\log N)^2\ll f(N)$ or the upper bound $f(N)\ll N^{11/15+o(1)}$ — state the current record in words and require a strict improvement, with proof; or exact computed values of $f(N)$ extending OEIS A392164/A392165 over a new verified range, with the search program and a certificate that each reported set is optimal. Deliver the proof or the improved bound / computed values with code.
Background
First studied by Erdős and Sárközy [ErSa87], who proved $\log N\ll f(N)\ll N^{3/4}\log N$ and guessed the lower bound is nearer the truth. Sárközy [Sa92c] extended the study to the case $A+B$ and to $k$-th-power-free sumsets. Gyarmati [Gy01] gave an alternative proof of $f(N)\gg\log N$ and new bounds for $A+B$. Konyagin [Ko04] improved both sides to $\log\log N\,(\log N)^2\ll f(N)\ll N^{11/15+o(1)}$. This is the finite analogue of the infinite squarefree-sumset problem (Erdős #1103, erdosproblems.com/1103): upper bounds for $f(N)$ directly imply lower bounds for the growth of the sequences considered there. Related sequences OEIS A392164 and A392165. Listed as open on erdosproblems.com/1109 (fetched 2026-07-21, status 'open'). Attacker's tool: exact computation of $f(N)$ for small $N$ — a maximum independent-set / clique computation on the graph joining pairs $\{a,b\}$ whose sum $a+b$ (and each double $2a$) is non-squarefree — to extend OEIS A392164/A392165 and sharpen intuition, together with sieve and analytic methods to close the enormous gap between the poly-logarithmic lower bound and the $N^{11/15}$ upper bound.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1109 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #1103 — infinite analogue | website |
| REF-03 | OEIS A392164 | website |
| REF-04 | OEIS A392165 | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.