Skip to content

Erdős Problem #330

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: number theory, additive basis.

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

Erdős Problem #330 asks for an additive basis whose individual elements remain genuinely necessary in a quantitatively strong way. An additive basis is a set \(A\) of nonnegative integers for which every sufficiently large integer can be written as a sum of a fixed number \(h\) of elements of \(A\); repeated summands are allowed. It is minimal if removing any one element destroys that eventual coverage.

For \(a\in A\), call an integer private to \(a\) if it is representable using \(h\) elements of \(A\), but not using \(h\) elements after \(a\) is removed. The registered question asks whether one can choose \(A\) with positive upper density and with a positive upper density of private integers for every \(a\in A\). The live problem page says that the construction has order \(2\), so the relevant sums are \(x+y\).

There is an important source boundary. The 1980 Erdős survey is quoted by the live page as discussing a minimal basis of positive density, while the page's explanatory note says that the original source does not impose a density restriction on \(A\) and does impose a density condition on the integers needing a fixed element. Those formulations are close, but not identical. This article records the drift instead of silently choosing one version.

A small example

Take \(A=\{1,2,4\}\) and use exact two-term sums. Direct enumeration gives

\[ 2A=\{2,3,4,5,6,8\}. \]

After removing \(1\), the remaining sums are \(\{4,6,8\}\), so the finite private set for \(1\) is \(\{2,3,5\}\). Removing \(2\) leaves sums \(\{2,5,8\}\) and private set \(\{3,4,6\}\). Removing \(4\) leaves sums \(\{2,3,4\}\) and private set \(\{5,6,8\}\). These are exact-arithmetic calculations: each displayed sum is obtained from the six ordered pairs in \(A\times A\), with duplicates discarded.

This example illustrates the bookkeeping but proves nothing asymptotic. A finite private set has density zero, and this \(A\) is not an asymptotic basis. It also shows why “exactly two” matters: allowing one-term representations would add \(\{1,2,4\}\) to the representable set and change the private-set predicate.

What is known

The primary 1980 paper by Erdős and Nathanson defines asymptotic bases and minimality, and explicitly asks whether every element can have a positive upper-asymptotic-density set of integers that cannot be represented after that element is removed. It is a primary statement of the problem, not a proof of the present positive-density construction. The 1980 survey cited as [Er80, p.100] gives the historically relevant wording and is the source that must control any final normalization.

The maintained catalogue at commit 536408716724a2402bdfa7c1d764bf83d64a8c89 labels #330 “proved (Lean)” with last update 2026-05-11, and its entry blob is 4e60263a80af6207aca494d2e1388e44fa372889. The live page, also edited 11 May 2026, attributes an order-two construction to David Turturean's GPT-assisted proof process. The discussion contains a later formalization report and a reviewer comment saying it largely matches Turturean's proof; those are external reports, not independent mathematical certification.

A newer public Lean artifact is available at Jayyhk/erdos-lean@a5ffc87b3d684fc00ea906b9e746c283740da900, file problems/330/Erdos330.lean. The retrieved file has no sorry occurrences and states both an upper-density exact-two-sum theorem and a translation to the Formal Conjectures interface. Its own final axiom print lists only propext, Classical.choice, and Quot.sound. This is useful provenance and a reproducible source target, but it is not a GCL replay or certification.

GCL's current state

The frozen FormalConjectures source required by the issue is commit 85f863718beeec7b58a3a1926ee92e3472bc2020, file FormalConjectures/ErdosProblems/330.lean, blob fa2e1fc65d8ddc72e247df5a1d159f0127945808. That file is materially stale relative to the newer source: its Rep definition permits at most \(h\) summands, its density predicate is Set.HasPosDensity, which requires an actual limiting density, and its theorem is answer(sorry). The current main file instead uses exact sums, upper density, and a formal_proof using lean link. The difference is evidence of source drift, not evidence that the frozen theorem was proved.

Accordingly, GCL's state is an evidence ledger with a plausible external resolution and an unresolved source-normalization obligation. The V2 ledger, not this article or the catalogue label alone, decides accepted coverage. The original SOURCE RESULT/1 citation is authenticated original RESULT/1.

What remains

The next bounded work should lock the historical statement against the scan of [Er80, p.100] and the companion [ErGr80, p.50], then compare it line by line with the order-two upper-density theorem in the newer Lean artifact. The comparison must settle whether positive density is required for \(A\), whether “density” means upper density, and whether exact two-term sums are the intended convention.

After that semantic lock, a reviewer can inspect the Turturean writeup and the cited Lean commit as two separate evidence streams. The formal file can support a replay request, but its absence of sorry does not by itself establish that the code was built in the relevant environment or that the historical wording was translated without strengthening it. No finite calculation, catalogue status, or forum comment establishes the global theorem.

Sources and claim boundaries

The catalogue and external Lean artifact are reported as sources of evidence, not as GCL mathematical certification, publication authority, or a claim that the historical ambiguity has disappeared.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1600 — 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