Skip to content

Erdős Problem #354

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

Take two positive real numbers \(\alpha\) and \(\beta\) whose ratio is irrational. From each one, form the rapidly growing integer sequence

\[ \lfloor \alpha\rfloor,\lfloor 2\alpha\rfloor,\lfloor 4\alpha\rfloor,\ldots \]

and the analogous sequence for \(\beta\). “Complete” means that every sufficiently large natural number can be made by adding distinct available terms. The two sequences are treated as a multiset: a value appearing once in each sequence gives two usable occurrences. Equivalently, one asks whether there is an \(N\) such that every \(n\geq N\) has the form

\[ n=\sum_{s\in S}\lfloor 2^s\alpha\rfloor+\sum_{t\in T}\lfloor 2^t\beta\rfloor \]

for finite sets \(S,T\subseteq\mathbb N\).

The main question is whether this always happens under the irrational-ratio hypothesis. A second question replaces the base \(2\) by one fixed real \(\gamma\) with \(1<\gamma<2\), and asks whether some such \(\gamma\) works for every admissible pair \(\alpha,\beta\). The original issue-bound statement and source packet are MATH-PROGRAMME issue #1624.

A small example

Let \(\alpha=1\) and \(\beta=\sqrt 2\). Their ratio is irrational, so this is an instance of the first question. The first five terms from the \(\alpha\) sequence are \(1,2,4,8,16\). For the \(\beta\) sequence, exact integer arithmetic gives \(1,2,5,11,22\).

There is no floating-point approximation hidden here. For \(k_n=\lfloor 2^n\sqrt2\rfloor\), it is enough to check

\[ k_n^2\leq 2\cdot 4^n<(k_n+1)^2. \]

For \(n=0,1,2,3,4\), the verified values are \(k_n=1,2,5,11,22\). Sorting the ten available occurrences gives \(1,1,2,2,4,5,8,11,16,22\). Each term is at most one plus the sum of its predecessors, so the usual interval argument shows that their subset sums contain every integer from \(0\) through \(72\), their total sum. An exact integer check records \(73\) reachable sums and no gaps.

This is a useful sanity check for the definitions and for the multiset convention. It is not evidence of eventual completeness: a finite initial segment cannot control the infinitely many later terms, and one pair \((1,\sqrt2)\) cannot settle a universal assertion.

What is known

The primary source read for this audit is N. Hegyvári, “On complete sequences,” Annales Universitatis Scientiarum Budapestinensis, 34 (1991), 7–10, available in the journal’s 1991 volume PDF. On page 7, Hegyvári defines completeness through finite sums of distinct sequence terms and proves that, for each fixed \(\alpha>0\), the set of \(\beta\) for which the paired sequence is incomplete is measurable and has either measure zero or infinite measure. His Lemma 1 on pages 8–9 gives a concrete sufficient condition: an already represented interval can be extended when the two next sequence terms leave gaps smaller than the interval’s starting threshold. The proof also uses the scaling implication that incompleteness for \((\alpha,2\beta)\) implies incompleteness for \((\alpha,\beta)\).

The live problem page attributes additional results to Hegyvári’s 1989 paper: completeness when exactly one parameter is dyadic, and non-completeness for special power-of-two-related pairs. The 1991 paper’s introduction independently records the dyadic case and a stronger conjectural direction, but the 1989 article itself was not read in this timebox. The maintained page also reports that Jiang and Ma, International Journal of Number Theory 20 (2024), 915–933, and Fang and He, Acta Mathematica Hungarica 175 (2025), 532–542, extend non-completeness results for power-of-two-related parameters with \(1<\alpha<2\). Those are primary bibliographic records, but their full texts were not used here to certify a theorem beyond the stated report.

Thus the irrational-ratio universal assertion remains a live question in the audited sources. Results for dyadic or power-of-two-related parameters do not decide it, because those pairs are generally outside the irrational-ratio hypothesis.

GCL's current state

The frozen catalogue source is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, with the data/problems.yaml Git blob 4e60263a80af6207aca494d2e1388e44fa372889. Its entry for 354 says open, last updated 2025-08-31, with statement-formalized metadata yes and formal-solution status unformalized. The live page was edited 2025-12-01 and contains the same two questions plus later forum reports; those reports are not themselves acceptance or certification records.

The pinned Formal Conjectures source is commit 85f863718beeec7b58a3a1926ee92e3472bc2020, file FormalConjectures/ErdosProblems/354.lean, blob 5807194064f39ca4c79e5bb773961e7f4c613d17. It defines the interleaved sequence with indices \(n/2\) and leaves both theorem bodies by sorry. A material source discrepancy is present: the pinned part (ii) hard-codes base \(2\) in the conclusion instead of using the quantified \(\gamma\). The maintained live file uses \(\gamma\), but its theorem is also still by sorry. The formal file is therefore a statement interface, not a proof.

What remains

A bounded successor should first reconcile the pinned and live formal statements, then read one primary paper in full and extract a theorem-level interface for a selected parameter family. A suitable target is Hegyvári’s interval-extension mechanism: for explicit \(\alpha,\beta\), compute the first indices where the hypotheses of Lemma 1 hold, prove the required floor inequalities exactly, and produce a finite interval of represented integers. Acceptance would require a checked chain of integer inequalities and a precise statement of which later terms are controlled. Falsification would be either a failed inequality, a missing distinct-term condition, or a counterexample to the claimed interval. Stop after one family and one complete interval certificate; do not extrapolate it to all irrational ratios or to the \(\gamma\) variant.

The larger gap is conceptual: no audited source here supplies a theorem settling the universal irrational-ratio case. Any future claim that it does must identify the exact theorem, hypotheses, page, and parameter translation. A Lean compilation or a proof by sorry would not fill that gap.

Sources and claim boundaries

The principal statement source is Erdős Problem 354, maintained by the Erdős Problems project. The frozen catalogue evidence is the commit and blob named above. The primary theorem source is Hegyvári 1991, especially pages 7–9 of the linked PDF. The maintained page’s references include Graham, Hegyvári 1989 and 1994, Jiang–Ma 2024 (DOI 10.1142/S1793042124500477), and Fang–He 2025 (DOI 10.1007/s10474-025-01515-5); only the 1991 paper was directly read as a primary full-text source here.

The original issue is #1624. Original SOURCE RESULT/1 citation: authenticated original RESULT/1. This article reports source evidence and a bounded research interface only. It does not provide GCL mathematical certification, change the catalogue status, or decide accepted coverage; the V2 ledger alone governs that coverage decision.

Catalogue and evidence provenance

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