Erdős Problem #773
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, sidon sets, squares.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
How many perfect squares can we select from the first \(N\) squares while ensuring that every sum of two selected squares uniquely identifies the pair? Such a collection is a Sidon set. Erdős Problem #773 asks whether we can select almost \(N\) squares on the scale of powers: at least \(N^{1-o(1)}\) for large \(N\). This is weaker than selecting a positive fraction of the squares, but much stronger than the presently established lower exponent \(2/3\).
The question remains OPEN as of this source audit. A strong June 2026 upper bound improves what we know about how large such a set can be, but it does not settle the existence question.
A small example
The first four squares form the set \(S_4=\{1,4,9,16\}\). The ten unordered pair sums when repetitions are allowed are
All ten are different. Therefore the full set of four squares is Sidon. The order of a pair does not matter: \(1+9\) and \(9+1\) are the same representation, not two violations.
This property need not persist as more squares are included. At \(N=7\) we find
The unordered pairs \(\{1,49\}\) and \(\{25,25\}\) are distinct, so the entire set \(S_7\) is not Sidon under the usual diagonal-inclusive definition. This finite collision does not estimate the asymptotic maximum: a large Sidon subset might still exist after deleting some squares.
What is known
Write \(S_N=\{1^2,\ldots,N^2\}\), and let \(F(N)\) denote the maximum size of a Sidon subset of \(S_N\). The problem asks whether
The notation means that the exponent of the largest achievable set tends to one. In particular, a construction of only \(N^{2/3}\) elements would not answer the conjecture.
Alon and Erdős discussed the question in An Application of Graph Theory to Additive Number Theory, European Journal of Combinatorics 6 (1985), pp. 201–203. On p. 203 they give, for each fixed positive \(\varepsilon\), a probabilistic construction with at least \(c(\varepsilon)N^{2/3-\varepsilon}\) elements, and ask whether the exponent can approach one. The maintained catalogue attributes a subsequent \(\Omega(N^{2/3})\) lower bound to Lefmann and Thiele (1995); the latter's original proof still requires a separate source check in this tranche.
An elementary route to an upper bound counts the available sums of two squares. A Sidon subset of size \(m\) determines \(m(m+1)/2\) distinct sums, all at most \(2N^2\). The classical Landau–Ramanujan estimate bounds the number of integers up to \(2N^2\) representable as sums of two squares by \(O(N^2/\sqrt{\log N})\). Hence
This is an upper bound, not a construction.
A stronger modern result was proved in the five-author June 2026 preprint by Croot, Mao, Pohoata, Sheffer and Yip, A combinatorial large sieve for Sidon sets, distances, and norm forms, arXiv:2606.17487v2, Corollary 1.2:
The authors' Theorem 1.1 and Corollary 1.2 appear on pp. 2–3. Their method exploits the fact that the squares use only \((p+1)/2\) residue classes modulo each odd prime \(p\), then combines local modular restrictions with the scarcity of repeated differences in a Sidon set. The paper itself describes this as the first super-polylogarithmic saving for #773. Its contribution is a much stronger upper bound.
Even this upper bound is still of the form \(N^{1-o(1)}\). It therefore neither confirms nor rules out a construction of size \(N^{1-o(1)}\). A bound \(F(N)\leq N^{1-\delta}\) for some fixed \(\delta>0\) would have a different logical consequence, but no such bound is claimed here.
GCL's current state
The original authenticated RESULT/1 source return records BOUNDED_TASK_DESIGNED and retains the original mathematical qualifications. This is an editorially reviewed explanatory article in the EC-BULK-005-R9 protected batch, effective only when that exact-hash transaction merges. The corresponding maintained Erdős statement and its bibliography were inspected. This editorial decision does not certify any full original theorem proof, independent external formalization, or Lean kernel check.
Preserved source-review qualifications: open n1 o1 not resolved by superpolylog upper; 2026 five author corollary v2 distinct from earlier preprint. See the immutable 128-case critical review record for the complete source-return caveats.
What remains
Inspect the original Lefmann–Thiele 1995 theorem to verify the \(N^{2/3}\) lower construction and whether diagonal equal-summand cases are included. Reconcile the distinct-summand convention in the 1985 article with the 2026 paper's diagonal-inclusive Sidon definition. Independently check finite Sidon examples for \(N\leq12\) and preserve the theorem numbering, versions, and ambient parameter conventions in the claim ledger.
A successful resolution of the main open question needs either a construction with exponent tending to one or an upper bound with a fixed power saving below one. Improvements that merely change logarithmic factors, even dramatically, do not settle it.
Sources and claim boundaries
- Erdős Problem #773, maintained OPEN as of the 24 April 2026 indexed revision. The original protected 2025 registry packet is pinned in source issue #2044.
- N. Alon and P. Erdős, An Application of Graph Theory to Additive Number Theory, European Journal of Combinatorics 6 (1985), 201–203, DOI, especially p. 203.
- E. Croot, J. Mao, C. Pohoata, A. Sheffer and C. H. Yip, A combinatorial large sieve for Sidon sets, distances, and norm forms, version 2, 24 June 2026, Theorem 1.1 and Corollary 1.2, pp. 2–3. Full author-uploaded text also appears here.
- Original GCL source-audit return. Outstanding original-source check: Lefmann–Thiele 1995 lower bound. Editorial state: EDITORIALLY_REVIEWED. Protected merge, browser verification, mathematical certification: NONE.
Editorial source decision: R9 critical review, REVIEWED as a source-grounded explanation only. All open mathematical questions, primary-proof fidelity obligations, and external formalization caveats remain separate.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2044 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: FORMAL_SOURCE_REFRESH_REQUIRED.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.