Erdős Problem #323
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, powers.
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
For integers \(k\) and \(m\), let \(f_{k,m}(x)\) count the integers not exceeding \(x\) that can be written as a sum of \(m\) nonnegative powers of degree \(k\). The main question asks whether, for every \(k\geq 1\) and every \(\epsilon>0\), the case of \(k\) summands satisfies
In words, does allowing exactly \(k\) powers of degree \(k\) produce almost as many represented integers as the interval up to \(x\), apart from an arbitrarily small power loss? The companion question asks whether, whenever \(1\leq m<k\), one has
for all sufficiently large \(x\). Here the implied constants may depend on the fixed parameters, and the functions count distinct represented integers, not representations with multiplicity. Zero is allowed as a summand, so the natural-number convention includes zero among the represented values.
The original Erdős Problem 323 issue asks for source locking and a bounded research design. It does not authorize a claim that either open estimate has been proved.
A small example
Take \(k=m=3\) and \(x=100\). The available cubes are \(0,1,8,27,64\). Exact enumeration of all triples, retaining sums at most \(100\), gives
Thus \(f_{3,3}(100)=29\). This is reproducible with integer arithmetic:
from itertools import product
p = [a**3 for a in range(5)]
direct = sorted({sum(t) for t in product(p, repeat=3) if sum(t) <= 100})
pairs = {a + b for a in p for b in p if a + b <= 100}
recombined = sorted({s + c for s in pairs for c in p if s + c <= 100})
assert direct == recombined
assert len(direct) == 29
print(direct)
The second construction independently forms pair sums before adjoining the third cube, so the assertions check both the count and the set identity. This finite calculation illustrates collisions between representations and the meaning of “distinct integers.” It proves no asymptotic lower bound: one value of \(x\) cannot establish behavior as \(x\) tends to infinity, and the case \(k=3\) does not settle any other exponent or number of summands.
What is known
The primary source is P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, Monographies de l’Enseignement Mathématique 28 (1980), section 5, printed p. 45. The scan states the definition of \(f_{k,l}(x)\), gives the two lower-bound questions, says the first inequality appears unattackable by the methods then available, and records Landau’s result
for some \(c>0\). This is an external historical statement in the source, not a new proof supplied here. The maintained Erdős Problems entry repeats that \(k=2\) result and says that for \(k>2\) it is not known whether \(f_{k,k}(x)=o(x)\). Its visible discussion includes recent numerical reports for \(k=m=3\); those posts explicitly provide numerical evidence rather than a proof and are not used as theorem evidence.
The pinned catalogue record at teorth/erdosproblems commit 5364087 identifies number theory and powers, no prize, informal status open with last update 2025-08-31, formal status unformalized, and statement-formalized metadata yes (last update 2026-03-15). The live main entry observed during this audit has the same Problem 323 fields; its current file blob is 97ae243a7fc056bb9c6413ce665b575eadd27ff3, so no status drift was found in this entry.
GCL's current state
The pinned FormalConjectures file, blob ddf5609b91bef24a3b2598b0a4af7a16bbf7e342, defines \(f\) over natural numbers and contains four theorem interfaces. The first two encode the open lower-bound questions, the third encodes the \(k=2\) asymptotic, and the fourth encodes the open \(k>2\) question about little-oh density. Every theorem body is by sorry; this is a formal statement/interface, not a checked proof. The formal definition counts natural numbers \(n\leq x\) with a vector of exactly \(m\) natural summands, which matches the nonnegative-summand reading, but exact equivalence to every convention in the historical prose still deserves semantic review.
The catalogue and formal metadata are evidence about records and interfaces. They do not certify mathematics. V2 ledger disposition alone decides accepted coverage. This article therefore preserves the open status and does not promote numerical discussion, a solved category tag for the Landau variant, or the existence of Lean syntax into a proof claim.
What remains
The smallest useful successor is a fixed-parameter source-and-lemma audit for \((k,m)=(3,3)\), followed by a narrowly stated finite certificate. Its input should be the primary definition, the exact formal definition, and an independently reproduced table of \(f_{3,3}(10^r)\) over a declared finite range. Its target should be either a proved elementary bound valid on that range, or a rigorously verified obstruction to a proposed stronger finite claim. Acceptance should require exact integer code, a second implementation or independently checkable certificate, and explicit agreement on whether zero is counted. Falsification is any mismatching value, omitted summand, or claimed asymptotic inference from finite data. Stop when the declared range and cross-check are complete; do not infer positive density or solve the open problem.
Sources and claim boundaries
The source chain is: the original issue; the frozen catalogue commit and blob 4e60263a80af6207aca494d2e1388e44fa372889; the frozen formal commit and blob ddf5609b91bef24a3b2598b0a4af7a16bbf7e342; the primary 1980 scan, whose downloaded SHA-256 was 0cbf0c32f0ab1e1c71db5121a88bac905bf976c4a6ab6bb6d7d9cf9ddd184ed3; and the maintained problem page. The original SOURCE RESULT/1 citation is authenticated original RESULT/1. No paper unavailable during this audit was substituted, no Lean replay was attempted, and no mathematical certification or publication decision is supplied here.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1593 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- 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.