Skip to content

Erdős Problem #349

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 question in plain language

Erdős Problem 349 asks for all positive real pairs \(t\) and \(\alpha\) for which the integer sequence

\[ s_n=\lfloor t\alpha^n\rfloor \]

is complete: every sufficiently large positive integer can be written as a sum of distinct terms of the sequence. “Distinct” means that each index is used at most once and only finitely many indices are selected. The phrase “sufficiently large” permits finitely many exceptions; it does not mean that every positive integer must occur.

The quantifiers matter. This is one question about every \(t>0\) and \(\alpha>0\), not just about the square \(0<t<1\), \(1<\alpha<2\). The maintained Erdős Problems entry records the full question, tags it as number theory and complete sequences, and currently displays an open status. The original GCL assignment is issue #1619.

There is also an indexing convention to preserve. Graham’s paper writes the sequence from \(n=1\), while the pinned formal file uses Set.range (fun n : ℕ => ⌊t * α ^ n⌋), which includes the \(n=0\) term. A finite initial term may be harmless in particular arguments, but equivalence is not assumed here without a proof.

A small example

Take \(t=1\) and \(\alpha=3/2\), and calculate with exact integer division rather than decimal approximations. For \(n=1\) through \(8\),

\[ \left(\left\lfloor\frac{3^n}{2^n}\right\rfloor\right)_{n=1}^8=(1,2,3,5,7,11,17,25). \]

The exact sum of these eight terms is \(71\). A direct subset-sum enumeration gives no missing integer in \(0,1,\ldots,71\). The same result follows from the elementary greedy lemma: if a finite increasing list begins with \(1\) and each next term is at most one plus the sum of all previous terms, its distinct subset sums cover the entire interval from \(0\) to the total sum. Here the successive checks are

\[ 2\le2,\quad 3\le4,\quad 5\le7,\quad 7\le12,\quad 11\le19,\quad 17\le30,\quad 25\le47. \]

This is a reproducible finite calculation: the eight floors are the exact quotients \(3^n\) divided by \(2^n\), the displayed inequalities hold in integer arithmetic, and the resulting covered interval is exactly \([0,71]\). It does not establish completeness of the infinite sequence. Later terms might create gaps, and a finite prefix can never prove a statement about all sufficiently large integers.

What is known

The primary paper read for this audit is R. L. Graham, “On a conjecture of Erdős in additive number theory,” Acta Arithmetica 10 (1964), 63–70, DOI 10.4064/aa-10-1-63-70. The journal record is here, and the scanned paper is here. Its introduction on p. 63 defines “complete” and the stronger “entirely complete,” meaning that every positive integer is representable.

Graham’s Theorem 2 on p. 65 proves that \(0<t<1\) and \(1<\alpha\le5^{1/3}\) imply entire completeness. Theorem 3 on the same page proves, for \(0<t<1\) and \(1<\alpha<2\), that completeness is equivalent to entire completeness. Theorem 4 on p. 67 reduces the remaining cases to three local patterns, and Theorems 5–6 on pp. 68–69 give an explicit union of the corresponding regions where the sequence is not complete. Graham therefore settles the unit-square subproblem described in his paper, with the complete region having area approximately \(0.85\); this is not a solution of the full \((0,\infty)^2\) question.

The maintained page cites P. Erdős and R. Graham, Old and new problems and results in combinatorial number theory (1980), p. 57, as the original catalogue source, and Graham’s 1964 paper as the primary result behind the remarks. The page says that Graham found arbitrarily many disjoint completeness intervals in the unit-square regime and repeats the conjectural-looking range \(1<\alpha<(1+\sqrt5)/2\). Those are source-backed historical statements, not a claim that the complete region is the whole square.

GCL's current state

The protected catalogue snapshot is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, entry blob 4e60263a80af6207aca494d2e1388e44fa372889. It records informal status open, formal status unformalized, and statement metadata formalized: yes, all dated 2025-08-31. The protected Programme registry class is PROTECTED_READY_BACKLOG; the batch readback records no existing result for this assignment.

The pinned provider source is google-deepmind/formal-conjectures commit 85f863718beeec7b58a3a1926ee92e3472bc2020, file blob 2a95c8a806c3e63979cba72fe0e7afcd0f7288f9, FormalConjectures/ErdosProblems/349.lean. It defines IsGoodPair using additive completeness of the range, states the global answer with answer(sorry), and contains several partial theorems whose bodies are also by sorry. The file is a formal statement interface, not a proof. Its annotations pointing to later external formal work are unverified reports here and do not change the protected catalogue status.

What remains

The most useful bounded successor is a source-to-formal normalization audit of Graham’s unit-square result. Its input should be the exact p. 63–69 paper, the pinned Lean file, and the live statement. Its target should be a short ledger matching the original \(n=1\) sequence to the formal \(n=0\) range, defining exactly what IsAddComplete means, and listing the hypotheses and conclusion of Graham’s Theorem 6 without broadening its unit-square scope.

Acceptance should require: every quantifier and interval is copied or justified; the extra \(n=0\) term is either formally removed by a proved invariance lemma or retained as an explicit discrepancy; the finite example above reproduces; and each external theorem is labelled as published proof, provider statement, or unverified report. Falsification is any missing hypothesis, a counterexample to the claimed index normalization, or a formal conclusion stronger than Graham’s theorem. Stop after one such discrepancy is recorded, or after the ledger and a bounded source comparison are complete. No exhaustive Lean build is needed for this source audit.

Sources and claim boundaries

Graham’s published results are external mathematical evidence, not GCL certification. The live page’s open label is current-status evidence, while the pinned catalogue is the protected status snapshot. The finite arithmetic check is only finite evidence. The Lean declarations are source interfaces with sorry, and no Lean replay, acceptance, publication, priority claim, or mathematical certification is supplied by this article.

Catalogue and evidence provenance

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

Back to catalogue · Compendium introduction