Skip to content

Erdős Problem #333

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (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

Let \(A\) be a set of nonnegative integers that becomes rarer and rarer: its natural density is zero. We ask whether there must always be a set \(B\) whose pairwise sums cover \(A\), while \(B\) is exceptionally sparse. Writing

\[ B(N)=\lvert B\cap\{0,1,\ldots,N\}\rvert, \]

the proposed sparsity is \(B(N)=o(\sqrt N)\). In words, after dividing by \(\sqrt N\), the ratio should tend to zero. The maintained problem page writes the counting interval as \(\{1,\ldots,N\}\); the 1977 source and the formal statement use the nonnegative-integer convention. This endpoint choice changes at most one counted element and does not change a little \(o\) assertion, but it should be stated.

The sumset \(B+B\) consists of all \(b+b'\) with \(b,b'\in B\). Problem 333 asks whether every density-zero \(A\) can be covered by such sums from a basis \(B\) that is much thinner than the square-root scale. The answer reported by the source record is no: there is a density-zero set that forces every covering set \(B\) to have square-root-sized initial segments infinitely often.

A small example

The finite version makes the issue concrete. Take \(A=\{1,3,5,7\}\). An exhaustive exact check of all subsets \(B\subseteq\{0,1,\ldots,7\}\) of size at most three finds that none has \(A\subseteq B+B\). The four-element set

\[ B=\{0,1,2,5\} \]

does work: its pairwise sums include \(1=0+1\), \(3=1+2\), \(5=0+5\), and \(7=2+5\). Thus this finite example has minimum basis size four. The enumeration is finite and exact: any summand of a number at most seven is itself at most seven, so no larger element of a nonnegative \(B\) can help.

This calculation illustrates, but does not prove, the Erdős question. A finite set can have a minimum basis, whereas the problem asks for one infinite \(A\), density zero, for which every possible \(B\) fails the asymptotic condition. The obstruction must therefore be repeated at unbounded scales, not merely observed once.

What is known

The primary source is P. Erdős and D. J. Newman, “Bases for Sets of Integers,” Journal of Number Theory 9 (1977), 420–425, received 13 October 1976. They define a basis for a finite set \(A\) as a set \(B\) with every \(a\in A\) expressible as \(b+b'\), and write \(m_A\) for the minimum size of such a basis. Their Theorem 2 states that most sets of type \((n,N)\)—having \(n\) elements and largest element \(N\)—satisfy

\[ m_A>\min\left(\frac{n}{\log N},\frac{\sqrt N}{2}\right). \]

This is a finite, probabilistic counting theorem. It does not, on the printed page, state the infinite density-zero problem verbatim. The maintained Erdős Problems entry explains that Theorem 2 already supplies a negative answer by choosing increasingly large hard finite sets and gluing them into one sparse sequence. That block-gluing inference is mathematically plausible and is also sketched in the site's discussion, but this audit does not present it as a new proof or as a checked GCL theorem.

The same paper studies squares and proves that they behave differently: it gives nontrivial finite upper and lower bounds for bases of the first \(n\) squares. That positive special case must not be confused with the general density-zero question. Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), is the source associated with the problem's later formulation.

GCL's current state

The original source-audit issue is #1603, assignment ERDOS-CATALOGUE-0333-S01; at investigation time it was available and had zero comments, so no prior RESULT/1 existed to reuse or duplicate. Its pinned catalogue source is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml, entry 333, Git blob 4e60263a80af6207aca494d2e1388e44fa372889. That snapshot records informal status disproved, status disproved (Lean), and last update 2025-12-25.

The maintained Problem 333 page was last edited 27 December 2025. It states the question, cites Erdős–Newman, and says that Theorem 2 implies a negative answer. It also exposes a current FormalConjectures link. The exact pinned upstream file read for this audit is FormalConjectures/ErdosProblems/333.lean at commit 0cfdea64bb89881ce06f41c303e2009ec6c66ea5, SHA-256 e9179bfd9a4584a28ce8619fb047d16c4fa0a85069f6630d72fc10baa27b67ad. Its theorem has the normalized quantifiers and is classified “research solved,” but its proof is literally by sorry; the linked external Lean proof is a report, not a GCL replay. The issue packet separately says that no statement file is present in GCL's admitted FC-GDM-85F86371 provider snapshot.

What remains

The remaining bounded mathematical task is to check the bridge from Theorem 2 to one infinite density-zero counterexample. It must specify the finite sets, their locations, their sizes, and the growth of successive scales. It must then prove both properties: the union has density zero, and any \(B\) covering the union has \(B(N)\geq c\sqrt N\) along an unbounded sequence of \(N\). The nonnegative convention also needs an explicit observation that a representation of \(a\leq N\) only uses summands at most \(N\).

A formalization would additionally need to choose the exact density predicate, the interval endpoint convention, and the meaning of answer(False). A theorem source containing sorry records a formal interface, not a completed proof. No GCL mathematical certification, Lean build, or claim of independent resolution is supplied here.

Sources and claim boundaries

The primary paper is Erdős–Newman (1977), direct PDF, SHA-256 678a832f03fdfe705b3c726fb986ffae218365a27955b3e1540d2e56e98c603a. The original issue and its packet are MATH-PROGRAMME #1603. The maintained source is erdosproblems.com/333; its bibliography identifies Erdős and Newman and Erdős–Graham. The pinned catalogue commit and blob, and the pinned FormalConjectures commit and file hash, are given above so that source drift is visible.

The published finite theorem is established external literature. The infinite block-gluing implication is reported by the maintained entry and forum discussion, but remains an unverified external report for this audit. The four-element example is an exact finite computation and establishes only its stated finite minimum. The Lean theorem source is present at the pinned upstream commit but contains sorry; it is not a replay and not GCL certification. V2 ledger state alone decides accepted compendium coverage. Original SOURCE RESULT/1 citation: authenticated original RESULT/1.

Catalogue and evidence provenance

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