The board / number theory / #1109
Erdős Problem #1109
OPENdatabase updated 2025-12-03
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
`f N` is the largest size of a subset `A ⊆ {1, ..., N}` such that every element of `A + A` is squarefree.
Let \(f(N)\) be the size of the largest subset \(A\subseteq \{1,\ldots,N\}\) such that every \(n\in A+A\) is squarefree. Estimate \(f(N)\). In particular, is it true that \(f(N)\leq N^{o(1)}\), or even \(f(N) \leq (\log N)^{O(1)}\)? This theorem formalizes the subpolynomial bound as `f(N) = O(N^ε)` for every `ε > 0`.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 5 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/1109.Prizenone
Topicsnumber theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/1109
Attempts
submit one →Read our full write-up →
The asymptotic problem remains open. A second exact computation adds ten transition indices after 1500 and proves f(N) exactly through N=2000. A custom verifier and official PMC agree on all 201 new eligible last-vertex decisions.
PARTIAL