Growth rate of an infinite sequence whose pairwise sums are all squarefree (Erdős #1103)
Statement
Let $A$ be an infinite sequence of positive integers such that every element of the sumset $A+A=\{a+b : a,b\in A\}$ is squarefree (an integer is squarefree if it is divisible by $p^2$ for no prime $p$). How fast must such a sequence grow? Writing $A=\{a_1<a_2<\cdots\}$, the question is how small $a_j$ can be as a function of $j$.
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable in Lean/Coq preferred, otherwise a full written proof) that pins down the true growth rate of the slowest such sequence — for instance matching upper and lower bounds on $\min a_j$, or a proof deciding whether an infinite $A$ with $A+A$ squarefree and $a_j = j^{O(1)}$ (polynomial growth) exists. ADVANCES: a proof strictly improving the best stated lower bound $a_j\gg j^{15/11-o(1)}$ (Konyagin) — state the current record in words and require a strictly larger exponent, with proof — or strictly improving the best stated upper construction $a_j<\exp(5j/\log j)$ (van Doorn–Tao); or an extension of the verified greedy squarefree-sumset sequence (OEIS A392164) to a new record length with the search program and a reproducible certificate of correctness. Deliver the proof, the improved-bound argument, or the search code plus attained data.
Background
Posed by Erdős [Er81h, p.180]. Erdős observed that a sequence with $A+A$ squarefree exists which grows exponentially, but doubted whether any such sequence of polynomial growth exists. His original framing asked for an infinite $A$ such that for every $a\in A$ and prime $p$, if $a\equiv t\pmod{p^2}$ then $1\leq t<p^2/2$ — a condition that forces $A+A$ to be squarefree — adding 'I am doubtful if such a sequence exists.' Frontier: van Doorn and Tao [vDTa25] proved the lower bound $a_j > 0.24\,j^{4/3}$ for all $j$, and constructed such a sequence (furthermore with squarefree terms) with $a_j < \exp(5j/\log j)$ for all large $j$; an even stronger lower bound $a_j \gg j^{15/11-o(1)}$ was found earlier by Konyagin [Ko04] while treating the finite analogue (Erdős #1109, erdosproblems.com/1109). They also handle the generalisation from squarefree to $k$-free integers and the variant replacing $A+A$ with $A\cup(A+A)\cup(A+A+A)$. The finite analogue Erdős #1109 is intimately linked: upper bounds on the largest squarefree-sumset subset of $\{1,\ldots,N\}$ directly imply lower bounds on the $a_j$ here. Related sequence OEIS A392164. Listed as open on erdosproblems.com/1103 (fetched 2026-07-21, status 'open'). Attacker's tool: computational search to extend the greedy squarefree-sumset sequence (OEIS A392164) and probe the true lower-bound exponent, together with analytic sieve methods to close the wide gap between the polynomial lower bound $j^{15/11-o(1)}$ and the near-exponential upper construction $\exp(5j/\log j)$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1103 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #1109 — finite analogue | website |
| REF-03 | OEIS A392164 | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.