Erdős problem 354 — an exact irrational pair and a certified 16-cell table

Date: 2026-07-28 (UTC)

Outcome

The general problem is not solved here. The verified progress is:

1. [a] A finite interval-propagation lemma reduces completeness of a

comparable pair of floor-doubling sequences to one exact finite subset-sum interval.

1. [d] For

\[ \boxed{\alpha=10\sqrt2,\qquad\beta=10\sqrt3} \] the greatest nonrepresentable positive integer is exactly \[ \boxed{558}. \] In particular every integer \(n\ge559\) has the required representation. The ratio \(\alpha/\beta=\sqrt{2/3}\) is irrational [a]; both parameters are themselves irrational and exceed \(14\). Thus neither the page's dyadic/nondyadic theorem nor its \(\alpha<2<\beta<3\) region applies.

1. [d] More strongly, exact greatest exceptions are determined uniformly

on the rectangle \[ \frac{904}{64}\le\alpha<\frac{908}{64},\qquad \frac{1108}{64}\le\beta<\frac{1112}{64}. \] Splitting it into the 16 cells indexed by \(K=\lfloor64\alpha\rfloor\in\{904,905,906,907\}\) and \(L=\lfloor64\beta\rfloor\in\{1108,1109,1110,1111\}\), the exact table is \[ \begin{array}{c|rrrr} &L=1108&1109&1110&1111\\ \hline K=904&558&558&784&784\\ K=905&558&558&1322&784\\ K=906&569&569&870&870\\ K=907&569&569&870&870 \end{array} \] for every real pair in the corresponding half-open cell, whether its ratio is rational or irrational.

1. [a] After power-of-two alignment, the unresolved uniform step for this

route is isolated precisely: prove that every comparable irrational-ratio pair has a finite prefix whose subset sums contain an interval satisfying the two inequalities in the propagation lemma below.

No result is claimed here for the separate \(\gamma\in(1,2)\) question; the all-future induction below uses the exact binary recurrence at \(\gamma=2\).

Claim labels used throughout:

• [a] elementary-rigorous;
• [b] rigorous modulo the named published theorem;
• [c] plausible/structural-unverified, including literature-search

conclusions;

• [d] computational-only, exact for the stated finite computation and

coupled here to an elementary all-future certificate.

Step 0: mandatory live-page audit

I first fetched the live page and its discussion thread through the Bright Data anti-bot browser. No mathematical work was begun before this check.

Live page: Erdős problem 354, accessed 2026-07-28.

• Status: OPEN.
• Last edited: 1 December 2025.
• Comments: 10.
• Claimed proofs: 0.
• “Currently working on this problem”: None.
• “Interested in collaborating”: Woett, jbbaehr22.
• Likes: Woett, jbbaehr22, kasko37.
• “This problem looks difficult”: None.
• “This problem looks tractable”: None.
• “The results on this problem could be formalisable”: None.
• “I am working on formalising the results”: None.
• “Formalised statement?”: Yes.

Thus neither mandatory stop condition fired: the page has no claimed proof, solved/falsified status, or current worker. The two “interested” users are reported because the task requested all such markers, but the page does not list either as currently working.

Verbatim live statement

The following is copied verbatim from the live page's LaTeX-source view:

Let $\alpha,\beta\in \mathbb{R}_{>0}$ such that $\alpha/\beta$ is irrational. Is the multiset\[\{ \lfloor \alpha\rfloor,\lfloor 2\alpha\rfloor,\lfloor 4\alpha\rfloor,\ldots\}\cup \{ \lfloor \beta\rfloor,\lfloor 2\beta\rfloor,\lfloor 4\beta\rfloor,\ldots\}\]complete? That is, can all sufficiently large natural numbers $n$ be written as\[n=\sum_{s\in S}\lfloor 2^s\alpha\rfloor+\sum_{t\in T}\lfloor 2^t\beta\rfloor\]for some finite $S,T\subset \mathbb{N}$?

What if $2$ is replaced by some $\gamma\in(1,2)$?

I use the displayed multiset, beginning with exponent \(0\), and preserve multiset semantics: numerically equal terms at different indices, or in the two different sequences, may each be used once.

Results and comments actually present on the live page

The page records the following mathematical results:

• Hegyvári [He89]: completeness when one parameter is dyadic rational and

the other is not.

• Hegyvári [He91]: for fixed \(\alpha>0\), the set of successful \(\beta\)

has measure \(0\) or infinite measure.

• Hegyvári [He94]: continuum many pairs whose subset-sum set contains no

infinite arithmetic progression.

• Hegyvári [He89]: noncompleteness for

\(\alpha\ge2,\ \beta=2^k\alpha\).

• Jiang--Ma [JiMa24] and Fang--He [FaHe25]: noncompleteness when

\(1<\alpha<2,\ \beta=2^k\alpha\), for sufficiently large \(k\).

• Hegyvári's stronger conjectural boundary: it should suffice that at least

one parameter is not dyadic and their ratio is not a power of two.

• The page attributes to van Doorn's comments completeness in the floor case

\(\alpha<2<\beta<3\), and completeness of the ceiling analogue when at least one parameter is nondyadic.

I read all 10 comments, not just the page summary. The mathematical comments add these details:

• van Doorn gives an elementary floor proof for

\(\min(\alpha,\beta)<2\) and \(\max(\alpha,\beta)<3\), and a proof of the dyadic/nondyadic case later identified with Hegyvári's 1989 result;

• van Doorn gives the ceiling-sequence argument using Graham's

\(\Sigma\)-sequence/precomplete criterion;

• van Doorn surveys the 1989, 1991, 1994, 2024, and 2025 papers;
• Tao reports that Jiang--Ma and Fang--He concern the power-of-two-ratio

obstruction and do not claim a result when the ratio is not a power of two;

• three December comments discuss an Aristotle counterexample to a

misformalised Lean statement, not a counterexample or proof for the informal problem.

The remaining comments are short replies about the value of documenting misformalisations and literature-search experiences. The forum warns that comments are unverified. None is labelled a claimed proof of the actual problem, and the current-worker field remains “None”.

Primary-source literature check

The following sources were opened and checked rather than inferred from titles or secondary summaries.

1. Erdős--Graham,

Old and New Problems and Results in Combinatorial Number Theory, p. 58, is the original source cited by the page. [b]

1. Hegyvári,

“On sumset of certain sets”, Publ. Math. Debrecen 45 (1994), 115–122, DOI 10.5486/PMD.1994.1404. Its introduction explicitly restates the problem and the 1989/1991 results. Its Theorem 1 gives continuum many non-subcomplete power-of-two-ratio pairs. It also proves the exact one-sequence binary recurrence \[ \lfloor2^{n+1}x\rfloor =2\lfloor2^nx\rfloor+\varepsilon_{n+1}(x) \] and analyzes the resulting gaps. [b]

1. Jiang--Ma,

“A conjecture of Hegyvári”, Int. J. Number Theory 20 (2024), 915–933. The DOI and publisher preview exist and state that the paper gives a partial result on Hegyvári's conjecture. [b]

1. Fang--He,

“On a problem of Erdős and Graham”, Acta Math. Hungar. 175 (2025), 532–542, DOI 10.1007/s10474-025-01515-5. The primary abstract says \(\beta=2^\ell\alpha\) and determines an infinite family of exceptions in that setting; it does not claim the irrational-ratio case. [b]

1. A relevant source not listed on the live page is Hegyvári,

“On arithmetic sums of Cantor-type sequences of integers”, Discrete Applied Mathematics 345 (2024), 1–3; the corresponding arXiv:2307.07237 exists. Theorem 2.4 proves, for \(1<x<2\), that two copies of the same single-sequence subset-sum set satisfy \[ FS(A_x)+FS(A_x)=\mathbb N. \] This is the rational-ratio \(1\) situation and does not resolve a mixed irrational-ratio pair. [b]

I could verify the bibliographic existence and later primary-source cross-references for He89 and He91, but did not obtain their full texts. Accordingly I do not attribute to them anything beyond what the live page, the 1994 paper, and the 2025 paper explicitly state.

I also searched exact title, exact formula, “Hegyvári conjecture”, author, DOI, and 2025–2026 combinations. I found no later primary source claiming a solution for a ratio that is not a power of two. This is a documented search miss, not a completeness claim about the literature. [c]

Elementary finite-to-infinite reduction

For \(x>0\), put

For a finite indexed multiset \(C\), write \(P(C)\) for its 0/1 subset sums.

Interval extension fact [a]

If \(P(C)\) contains \([L,L+W]\) and a new indexed term \(c\) satisfies

then \(P(C\cup\{c\})\) contains

The inequality says exactly that the two integer intervals overlap or are adjacent.

Paired-tail propagation lemma [a]

Let \(1<x<y<2x\), set \(a_n=a_n(x)\) and \(b_n=a_n(y)\), and suppose a finite prefix through index \(N-1\) has a subset-sum interval \([L,L+W]\). If

then every integer at least \(L\) is a subset sum of the full paired sequence.

Proof

The floor recurrence gives, for digits \(e_n,f_n\in\{0,1\}\),

Also \(a_n\le b_n\). Since \(y<2x\),

where \(a_n\ge1\).

Condition (1) and the interval extension fact add \(a_N\) and then \(b_N\). Suppose inductively that the pair \(a_n,b_n\) has just been added. The current interval width includes at least \(a_n+b_n\), so

and \(a_{n+1}\) can be added. After that addition, (2)–(3) give

so \(b_{n+1}\) can be added as well. Induction adds every tail term and the right endpoint tends to infinity. \(\square\)

This lemma uses no published theorem.

The explicit irrational pair

Take

Their ratio is \(\sqrt{2/3}\). A reduced positive rational has a rational square root only when its numerator and denominator are both squares; \(2\) and \(3\) are not. Hence the ratio is irrational. [a]

Exact integer-square-root arithmetic gives the first seven terms from each sequence, interleaved:

14, 17, 28, 34, 56, 69, 113, 138,
226, 277, 452, 554, 905, 1108

The standalone checker performs three independent finite calculations on these 14 indexed terms:

1. the integer-bitset recurrence bits |= bits << weight;
2. explicit repeated set translation;
3. literal enumeration of all \(2^{14}=16384\) masks.

All three obtain the same subset-sum set and verify

This finite assertion is [d].

Here \(W=3432-559=2873\), while the next two terms are

Thus

The paired-tail lemma proves that every integer at least \(559\) is representable. All unused terms are at least \(1810>558\), while (4) says the finite prefix does not represent \(558\). Therefore 558 is the exact greatest exception. The conclusion is a computer-assisted exact theorem, classified [d] because of the finite exhaustive step.

Two small witnesses independently reconstructed by the checker are

The verifier also constructs and checks a distinct-index representation of \(10^6\), exercising the all-future backtracking algorithm.

Uniform rectangle and exact table

For

the checker handles all 16 pairs

Each coarse cell is partitioned into \(4\times4\) cells of side \(1/256\), for 256 fine cells overall. If

then every value \(\lfloor2^n\alpha\rfloor\), \(0\le n\le8\), is fixed exactly by integer endpoint arithmetic; the same holds for \(\beta\). Thus every fine cell has a fixed 18-term indexed prefix.

For every one of the 256 cells the verifier:

1. recomputes all prefix subset sums by both a bitset DP and an explicit-set

DP;

1. compares the answers at every integer from \(0\) through the prefix sum;
2. scans all maximal solid intervals;
3. checks (1) against the worst possible next terms

\[ a_9\in\{2k,2k+1\},\qquad b_9\in\{2\ell,2\ell+1\}; \]

1. verifies that the integer immediately before the selected interval is

missing and smaller than every unused term;

1. applies the elementary propagation lemma.

The prefix sums range from 16062 to 16114. In total the two independent DPs are compared at 4,118,784 integer positions. The qualifying interval widths range from 13,438 to 14,966. Collapsing the 16 fine results inside each coarse cell gives the constant exact table:

For example, \(10\sqrt2\in I_{905}\) and \(10\sqrt3\in J_{1108}\), agreeing with the first entry of its row.

The distribution among the 256 fine cells is

greatest exception 558:   64 cells
greatest exception 569:   64 cells
greatest exception 784:   48 cells
greatest exception 870:   64 cells
greatest exception 1322:  16 cells

The finite table and scans are [d]; their promotion from a finite prefix to an exact all-future threshold uses the proved lemma [a].

Reproduction

Standalone verifier: erdos354_wave8v_reverify.py.

Run:

python3 runs/erdos354_wave8v_reverify.py

On this VM it finishes in about 1.8 seconds and prints PASS, table (5), the two short witnesses, and a representation of \(10^6\). It uses only the Python standard library and no floating-point arithmetic, stored table, or external solver.

The deterministic digest of all 256 recomputed fine-cell certificate records is

7179a03a48dafbce8cf777604ca88f5d34796308f21b4a388dcac5a0d4a1ced0

The verifier source SHA-256 is

8b6d604a67854bf73fdd07ac5832d79d770bf27c123e148253e3319b9dae0e24

It was also rerun under PYTHONHASHSEED=0,1,12345; all three complete outputs had the same SHA-256 c2d80112f86bebd15cf37c67ad225efc83419ddde9d20e71705bb5e2599d565f.

Core finite recurrence:

bits = 1
for weight in weights:
    bits |= bits << weight

The independent implementation literally starts from {0} and, for each indexed term, unions the set with its translate. For the short irrational pair a third routine loops over all masks and sums their selected indexed weights.

Exact remaining lemma for this route

Power-of-two alignment loses only finitely many terms. Given any irrational-ratio \((\alpha,\beta)\), swap the parameters if necessary and first choose \(r\ge0\) such that

Then choose a common \(q\ge0\) large enough that \(x=2^qx_0>1\), and put \(y=2^qy_0\). The sequences for \(x\) and \(y\) are tails of the original two sequences, and \(x/y\) remains irrational. Thus the following statement would settle the original \(\gamma=2\) question via the paired-tail lemma:

Missing finite-interval lemma. For every \(1<x<y<2x\) with \(x/y\) irrational, there exist \(N,L,W\) such that the subset sums of \[ > \{a_0(x),b_0(y),\ldots,a_{N-1}(x),b_{N-1}(y)\} > \] contain \([L,L+W]\), with \[ > a_N(x)\le W+1,\qquad b_N(y)\le W+a_N(x)+1. > \]

The reduction to this lemma is [a]. The assertion of the missing lemma itself is not proved here; it is the precise wall for this method.

The obstruction is uniformity, not checking a fixed pair. Ratios arbitrarily close to a power of two can share arbitrarily long aligned binary behavior with the known noncomplete power-of-two-ratio examples. A fixed-depth computation cannot distinguish all such pairs.

For scale: within the rectangle above, refining depth \(8\) to depth \(d\) without pruning multiplies the number of two-dimensional cells by \(4^{d-8}\) and the subset-sum span by roughly \(2^{d-8}\), for a naive time factor about \(8^{d-8}\). Depth 20 would therefore be about \(8^{12}\approx6.9\times10^{10}\) times this run—roughly \(4\times10^3\) single-core years at the observed rate—and still would not prove the uniform irrational statement. This cost estimate is structural [c] and is why no such computation was attempted.

PARTIAL: exact computer-assisted thresholds are proved for a 16-cell rectangle, including greatest exception 558 for the irrational pair (10√2,10√3), and the remaining uniform finite-interval lemma is isolated.