Skip to content

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,

\[ H_2(n)=n \]

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

\[ \|1_A*1_A\|_\infty\leq k, \]

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

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.

Back to catalogue · Compendium introduction