Skip to content

Erdős Problem #336

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (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 #336 studies how far two notions of “additive basis” can separate. An infinite set \(A\) of nonnegative integers is a basis of order \(r\) if every sufficiently large integer is a sum of at most \(r\) members of \(A\), with repetition allowed, and \(r\) is the least such number. Its exact order is the least \(k\) for which every sufficiently large integer is a sum of exactly \(k\) members of \(A\). The distinction matters because adding a fixed number of summands is not automatically possible when the set has no suitable residue structure.

Let \(h(r)\) be the largest finite exact order attained by a basis of order \(r\). The problem asks for the value of

\[ \lim_{r\to\infty}\frac{h(r)}{r^2}. \]

The word “sufficiently” is an eventual quantifier: finitely many small exceptions do not matter. The original Erdős–Graham paper writes the corresponding extremal function as \(g(r)\) and works with nonnegative integers; the maintained page phrases the set as \(A\subseteq\mathbb N\). That ambient-set convention should be retained explicitly in any future formal statement, rather than silently treating the two wordings as identical.

A small example

The maintained entry gives the lacunary set

\[ A=\bigcup_{j\geq 0}(2^{2j},2^{2j+1}], \]

as an example whose ordinary order is \(2\) while its exact order is \(3\). This is an infinite asymptotic claim, not something a finite prefix can prove. Nevertheless, its first two nonempty blocks already make the mechanism visible. Taking \(A_0=\{2,5,6,7,8\}\), exact enumeration gives every integer from \(10\) through \(16\) as a sum of two members and also as a sum of three members:

\[ \begin{aligned} 10&=5+5=2+2+6, & 11&=5+6=2+2+7,\\ 12&=5+7=2+2+8, & 13&=5+8=2+5+6,\\ 14&=6+8=2+5+7, & 15&=7+8=2+5+8,\\ 16&=8+8=5+5+6. \end{aligned} \]

The same finite set has sorted consecutive gaps \(1,2,1\), whose gcd is \(1\). This is a reproducible exact-arithmetic sanity check of the local pattern and of the gap calculation. It does not establish that all sufficiently large integers have either representation, nor does it determine \(h(2)\) or the limiting constant. The asymptotic construction and its proof require the infinite set and the source theorem.

What is known

The primary source is P. Erdős and R. L. Graham, “On bases with an exact order,” Acta Arithmetica 37 (1980), 201–207. Its Theorem 1, on p. 202, proves that a basis \(A=\{a_1<a_2<\cdots\}\) has an exact order if and only if

\[ \gcd\{a_{i+1}-a_i:i\geq 1\}=1. \]

The hypothesis is about all consecutive gaps of the infinite sorted set, not merely a finite sample. Their Theorem 2, on pp. 203–206, bounds the extremal function at quadratic scale, with asymptotic constants \(1/4\) and \(5/4\). In the concluding remarks on p. 206 they ask whether the limit exists and, if it does, what its value is. Thus this primary paper is evidence for the definition, the exact-order criterion, and the original bounds; it is not a solution of the limit problem.

The maintained Erdős Problems #336 entry, last edited there on 28 October 2025, reports later bounds \(1/3\leq\lim h(r)/r^2\leq 1/2\), attributing the lower bound to Georges Grekos and the upper bound to John C. M. Nash, and reports \(h(2)=4\), \(h(3)=7\), and \(10\leq h(4)\leq 11\). Those are useful literature pointers. In this bounded audit I directly read Erdős–Graham, but did not independently inspect the Grekos, Nash, or Plagne proofs; those page-level attributions remain reported external evidence here, not a new verification.

GCL's current state

The original MATH-PROGRAMME issue #1606 is the source-audit docket for this article. At readback it was available, had the required direct-editorial/source labels, and had no comments, so no existing RESULT/1 was duplicated. The protected catalogue registry maps problem 336 to issue 1606, records catalogue status open, classifies it as STATEMENT_CAPTURE_REQUIRED, and records no protected Formal Conjectures statement.

The frozen catalogue evidence is teorth/erdosproblems at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, entry number: "336", Git blob 4e60263a80af6207aca494d2e1388e44fa372889. It records open, unformalized, and formalized: no, with the last update dated 2025-08-31. The pinned formal provider commit 85f863718beeec7b58a3a1926ee92e3472bc2020 has no FormalConjectures/ErdosProblems/336.lean at that revision; the current provider lookup also returned no such file. There is therefore no Lean theorem source, even a sorry-bearing one, to compare for semantic drift.

What remains

The smallest useful successor is a source-and-interface task: freeze the exact natural-number convention, define ordinary and exact order with explicit eventual quantifiers and repetition, and reconcile the notation \(h(r)\) with Erdős–Graham’s \(g(r)\). Then obtain and inspect the cited Grekos, Nash, and Plagne primary documents, recording theorem or page locations for each later bound. A bounded computational companion can enumerate finite prefixes of candidate bases, verify gap gcds, and test representation intervals, but must label every result finite and non-asymptotic.

The central mathematical remainder is still the limit question: either prove existence and identify the constant, or produce a rigorously sourced obstruction to the asserted limit. Neither the finite example, the catalogue label, the live page, nor a future formal statement would by itself supply that proof.

Sources and claim boundaries

The frozen catalogue commit and blob above are identity evidence, not mathematical authority. The primary PDF used here is the Erdős–Graham article (archive copy; SHA-256 f44cf64462480beee3239be050306d6f2bc0597c179cc1821b70ab3cddfd0f6), with bibliographic confirmation at EuDML. The maintained page lists Plagne 2004 and the Grekos and Nash references, but this article does not promote their reported bounds beyond that evidence boundary.

The GCL source-audit return is authenticated original RESULT/1. V2 ledger state, not this manuscript, decides accepted coverage. This article supplies documentary exposition and a bounded research interface only: it is not a Lean replay, a mathematical certificate, an independence claim, or a publication decision.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1606 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_REQUIRED.
  • 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