Erdős Problem #345
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, complete sequences.
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 documentary status of this article is controlled by the protected V2 ledger. It explains the source record and verified interfaces; it is not mathematical certification.
The question in plain language
For a set \(A\) of positive integers, form every finite sum in which each member of \(A\) is used at most once:
The set is called complete when every sufficiently large natural number belongs to \(P(A)\). Its threshold \(T(A)\) is the least point from which this happens. Problem 345 applies this to powers with exponent \(k\), \(A_k=\{1^k,2^k,3^k,\ldots\}\). It asks whether infinitely many positive exponents \(k\) satisfy
In ordinary language: does increasing the exponent sometimes make the last unavoidable gap in the distinct-power subset sums move downward, and does that happen infinitely often? The powers are positive, and the subset sum is finite and distinct. The source uses \(n^k\) as a description of the sequence, so it is important not to read \(n\) as one fixed base. The formal version restricts \(k\) to \(k>0\); this avoids the zeroth-power set, which is just \(\{1\}\) and is not complete.
A small example
The first-power set contains every positive integer, so the empty sum gives \(0\) and every \(m>0\) is already a singleton sum. Under the nonnegative convention, \(T(A_1)=0\).
Here is an exact finite check at the next exponent. The only squares that can occur in a sum at most \(129\) are \(1^2,\ldots,11^2\). The following dynamic program uses integers only and updates subset sums once for each square:
values = [n*n for n in range(1, 12)]
reachable = {0}
for value in values:
reachable |= {s + value for s in tuple(reachable)}
print(128 in reachable)
print(129 in reachable)
print(4 + 9 + 16 + 36 + 64)
The verified output is:
False
True
129
Thus \(128\) has no representation by distinct positive squares, while
Because no square larger than \(11^2\) can enter a sum for \(128\), the negative check is exhaustive for that particular integer. It does not show that every integer at least \(129\) is representable, so it is not by itself a proof that \(T(A_2)=128\), still less evidence for infinitely many exponent descents.
What is known
The original source is Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), p. 55, cited by the maintained problem page as [ErGr80]. It records the question and the known values
The sequence of positive powers with exponent \(k\) is complete for every positive \(k\). A relevant primary source is Doyon Kim, “On the Largest Integer that is not a Sum of Distinct Positive powers with exponent \(n\),” Journal of Integer Sequences 20 (2017), Article 17.7.5, arXiv:1610.02439, especially its introduction and Theorem 1. Kim states the earlier completeness theorem and proves an explicit upper bound for the threshold as a function of \(n\). His introduction also reports the exact threshold values through \(n=6\), including \(T(A_6)=11146309947\). These results guarantee that the thresholds used in Problem 345 exist and give upper bounds, but they do not compare \(T(A_k)\) and \(T(A_{k+1})\) infinitely often.
The live page also notes the suggestion that powers of two may be promising exponents because of their restricted residues modulo a related power of two. That is a heuristic direction recorded by the source, not a theorem establishing the requested inequality.
GCL's current state
The original issue is MATH-PROGRAMME issue #1615, assignment ERDOS-CATALOGUE-0345-S01. Its frozen catalogue packet pins teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml, Git blob 4e60263a80af6207aca494d2e1388e44fa372889. At that revision, entry 345 says informal status open, last updated 2025-08-31; formal status is unformalized, statement-formalized metadata is no, and the topics are number theory and complete sequences.
The live page was edited on 28 December 2025 and now displays “Formalised statement? Yes.” That is source drift, not a contradiction about the mathematics: it reflects a later formal-conjectures file that was absent from the frozen packet. The live page still presents the problem and its historical remarks; the V2 ledger, not a page label alone, decides accepted coverage.
The current Formal Conjectures file is pinned here by commit 7278d69dad79f4ca5e54c9f389e2e8985466b025, with blob 62ea292369528f9d5d134a2c8c2bbf7829dcc1aa: FormalConjectures/ErdosProblems/345.lean. It defines positive kth powers and encodes the descent question using least-threshold witnesses. The open theorem and the completeness theorem both end in by sorry. The file proves a separate first-power threshold lemma, but no GCL mathematical certification follows from that file.
What remains
The smallest useful successor is a source-faithful threshold comparison for a bounded set of exponents. Its input should be a positive bound \(K\) and exact subset-sum data for \(A_k\) and \(A_{k+1}\) through a declared integer cutoff. Its target should be either an exact pair of threshold certificates for one chosen \(k\), or a rigorously stated obstruction showing that the cutoff cannot certify a threshold because an untested larger generator may matter.
The method can use dynamic programming over the finitely many powers not exceeding the cutoff. Acceptance requires exact integer arithmetic, a reconstruction of every claimed representation, and an explicit missing-sum certificate for every claimed lower bound. Falsification is immediate if a reported missing value is represented, a representation reuses a power, or the proposed threshold is tested below the cutoff without controlling larger powers. Stop after the fixed exponent and cutoff range, at the first semantic mismatch, or when the source assumptions needed for an unbounded theorem become unavoidable. This would generate bounded evidence only; it would not promote the catalogue status or prove the infinite assertion.
Sources and claim boundaries
The primary historical citation is ErGr80, p. 55; the original SOURCE RESULT/1 citation is authenticated original RESULT/1. The maintained statement and date metadata are on Erdős Problem 345. The exact frozen catalogue source is the pinned problems.yaml, and the formal interface is the pinned Lean file. Kim’s primary paper is available as arXiv:1610.02439 and in the cited journal record.
The external proof status is limited to the results actually stated in those sources: completeness of positive powers and explicit threshold information or bounds. The infinite descent assertion remains the source problem. The finite square calculation is independently reproduced exact arithmetic, not a global theorem. The Lean declarations are formal statements with sorry, not replayed proofs. GCL has supplied no mathematical certification, publication authority, or claim that the live formalization settles Problem 345.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1615 — 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.