Erdős Problem #772
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: number theory, sidon sets, additive combinatorics.
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 large a Sidon subset can one guarantee inside a finite set whose pair sums do not repeat too often? A Sidon set has essentially unique pair sums. This question measures how much uniqueness survives when the original set allows a bounded number of repetitions.
Editorial status: REVIEWED EXPLANATORY ARTICLE; SOURCE-SEMANTICS CAVEAT RETAINED. The maintained catalogue labels the growth question PROVED. The 1985 primary paper proves a positive \(n^{2/3}\) scale guarantee under its own definition, but a quoted universal upper bound does not transfer literally to the catalogue's ordered convolution definition.
A small example
Take \(A=\{1,2,4,8\}\). Its sums of two distinct elements are \(3,5,9,6,10,12\), each occurring for exactly one unordered pair. Its double-element sums are \(2,4,8,16\); none is equal to one of those six distinct-element sums, nor to another double-element sum. Consequently \(A\) is Sidon even when repeated elements are permitted in the definition.
If \(r_A(s)\) counts ordered pairs \((a,b)\in A^2\) with \(a+b=s\), then \(r_A(s)\leq2\) for every \(s\). The two orders of a distinct pair count separately. This elementary observation already exposes the main normalization issue: any \(n\) element set with \(r_A(s)\leq2\) for all \(s\) must itself be Sidon. Indeed, two distinct unordered pairs of distinct elements giving the same sum would produce at least four ordered representations. A collision \(2a=b+c\) with \(b\neq c\) would produce at least three ordered representations. Both are impossible. Powers of two give an example for every \(n\).
Thus for the literal ordered-convolution definition in the maintained catalogue,
for every positive integer \(n\), rather than a quantity bounded above by a fixed multiple of \(n^{2/3}\).
What is known
The maintained Erdős problem #772 defines \(H_k(n)\) as the largest cardinality guaranteed for a Sidon subset of every \(n\) element \(A\subset\mathbb N\) with
and asks whether \(H_k(n)/n^{1/2}\to\infty\), or even whether some fixed positive power improvement over \(n^{1/2}\) holds.
In their 1985 article An Application of Graph Theory to Additive Number Theory, Noga Alon and Paul Erdős define a \(B_2^{(k)}\) set differently: every integer has at most \(k\) representations as a sum of two distinct elements. Such representations are counted once per unordered pair. Their Theorem 1 (p. 201) partitions any \(n\) element \(B_2^{(k)}\) sequence into at most \(C(k)n^{1/3}\) \(B_2\) subsequences. Its lower consequence, displayed as (4), is a \(B_2\) subsequence of size at least \(c(k)n^{2/3}\). The authors also cite a separate \(B_2^{(2)}\) construction giving an \(O(n^{2/3})\) obstruction in that model. Neither statement licenses an \(O(n^{2/3})\) upper bound uniformly over the catalogue's \(k=1,2,\ldots\).
The primary proof (p. 202) constructs a four-uniform hypergraph: vertices are the elements of \(A\); an edge is a set of four distinct indices supporting a collision of two pair sums. There are at most \(O_k(n^2)\) such edges. Retain each vertex independently with probability \(p=c(k)n^{-1/3}\). The expected retained size is \(c(k)n^{2/3}\), whereas the expected count of surviving collision edges is \(O_k(c(k)^4n^{2/3})\). With a sufficiently small positive \(c(k)\), deleting one vertex from each offending edge leaves at least \(c'(k)n^{2/3}\) elements without such collisions.
For the stronger diagonal-inclusive Sidon convention, a collision \(2a=b+c\) involving three distinct elements must also be removed. Under ordered convolution bounded by \(k\), there are at most \(O(kn)\) such triples. At the same sampling probability they contribute expected \(O_k(np^3)=O_k(1)\) obstructions, which do not change the \(n^{2/3}\) order. The primary article does not explicitly formulate this diagonal-inclusive extension, so it should be recorded as a separate elementary deduction rather than misquoted as its theorem.
GCL's current state
The authenticated issue-bound source audit independently inspected the original 1985 article on pp. 201–202, compared it with the pinned and maintained catalogue formulation, and recorded STATUS_CONFLICT. The literal statement about a two-sided \(n^{2/3}\) law for all \(k\geq1\) is incompatible with the exact \(k=2\) example above.
The positive growth question is not thereby refuted. The lower guarantee \(\Omega_k(n^{2/3})\) is consistent with the original paper and with a direct sampling argument for the ordered model. No novel theorem certification or independent Lean replay is claimed. This source-critical manuscript has been editorially admitted as a reviewed explanation in protected batch EC-BULK-005-R3. The underlying theorem and historical source semantics are not independently GCL-certified.
What remains
Resolve the statement conventions at the historical sources [Er80e] and [Er84d], including whether diagonal pair sums are permitted, whether representations are ordered, the admissible ranges of \(k\), and which extremal upper bounds really transfer between models. In particular, \(k=1\) gives no admissible set of size \(n\geq2\) under ordinary ordered convolution, so a universal quantifier must not quietly turn vacuity into an asymptotic assertion. Examine the \(B_2^{(2)}\) construction independently before assigning an upper bound in the convolution model.
For a reproducible finite regression, verify all ordered sums of \(\{1,2,4,8\}\), and separately verify the pair-sum collision argument for an arbitrary set with convolution maximum at most two. Conduct substantive mathematical/editorial review of the ordered versus unordered definition before separate V2 admission. Protected publication and the live browser MathJax check are already complete.
Sources and claim boundaries
- Erdős problem #772, maintained statement and status; catalogue LaTeX with original bibliography. Pinned catalogue source: teorth/erdosproblems commit
536408716724a2402bdfa7c1d764bf83d64a8c89,data/problems.yaml. - N. Alon and P. Erdős, An Application of Graph Theory to Additive Number Theory, European Journal of Combinatorics 6 (1985), 201–203, DOI 10.1016/S0195-6698(85)80027-5. Definition and Theorem 1: p. 201; hypergraph/sampling proof: p. 202.
- Original GCL source-audit return. Open boundary: historical Er80e/Er84d statements and matching of upper-bound quantifiers.
- Editorial state: REVIEWED EXPLANATORY ARTICLE (EC-BULK-005-R3); Mathematical certification: NONE; Protected source merge: COMPLETE; Public rendered-readback: VERIFIED; V2 admission: MERGED in PR #2650.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2043 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- 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.