Skip to content

Erdős Problem #245

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: 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

Let \(A\subseteq\mathbb N\) be infinite and have asymptotic density zero: \(A(N)=|A\cap[1,N]|=o(N)\). Let \(A+A\) be the set of distinct pairwise sums of two members, allowing an element to be added to itself. Erdős asked whether

\[ \limsup_{N\to\infty} \frac{|(A+A)\cap[1,N]|}{|A\cap[1,N]|}\ge3. \]

The numerator is the sumset truncated at \(N\), not the entire global sumset. The conclusion is a limsup, not a bound for every sufficiently large cutoff.

A small example

If \(A=\{1,2,3\}\), then \(A+A=\{2,3,4,5,6\}\). Its five distinct sums illustrate how addition expands a set. But \(A\) is finite, and so cannot be used as a witness for the infinite-set theorem.

An infinite example is the powers of two, whose density is zero. Its pairwise sums are largely distinct. That example illustrates a high sumset-to-set ratio but does not prove the minimum universal limsup factor.

What is known

PROVED. Freiman (1973) established the factor three for every infinite density-zero set. Erdős had earlier indicated that a factor two was easier, and that three should be best possible; Mann's 1960 result provides a route to the weaker bound.

The maintained Erdős #245 identifies Freiman as the source of the affirmative result. The density-zero condition and exact truncated-count denominator are indispensable to the cited formulation. It is not a theorem about the finite ratio \(|A+A|/|A|\) for one chosen small set.

GCL's current state

Pinned and maintained status: PROVED. Original authenticated issue #1514. An external formal statement is reported, but Freiman's proof and a GCL Lean kernel verification have not been independently replayed.

The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.

What remains

A bounded task enumerates sparse sets and counts their initial segments and their distinct pair sums not exceeding each cutoff. Acceptance: permit \(a+a\), never count sums greater than the cutoff, and verify the input set's density-zero requirement separately from the sumset calculation. Finite data are not a proof of the universal infinite limsup.

Sources and claim boundaries

No new additive-combinatorial theorem, independently verified Freiman proof or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1514 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: A provider statement was included in the pinned 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