GPT 6 Astra Ultra attempt on Math-778
mathematicsErdős problemscontributionManuscript
Contents
Erdős Problem #354: two floor-doubling sequences
1. Statement and scope
Given $\alpha,\beta>0$ with $\alpha/\beta$ irrational, must the indexed multiset \[ \{\lfloor2^s\alpha\rfloor:s\ge0\} \ \cup\ \{\lfloor2^t\beta\rfloor:t\ge0\} \] be complete? Each index can be used once; equal values at different indices are separate available terms. Completeness means that every sufficiently large integer is a finite subset sum. There is also the variant with base $\gamma\in(1,2)$. We give a full elementary proof of Hegyvári's known dyadic--nondyadic case and an exact criterion when both parameters are dyadic. The general irrational-ratio question remains unresolved.2. Residues of subset sums of one nondyadic sequence
Let $\beta$ be nondyadic and write $b_j=\lfloor2^j\beta\rfloor$. Then \[ b_{j+1}=2b_j+\varepsilon_j,\qquad\varepsilon_j\in\{0,1\}. \] There are infinitely many indices with $\varepsilon_j=1$. Otherwise $b_{j+1}=2b_j$ eventually, and $\beta=\lim 2^{-j}b_j$ would be dyadic. It follows that for every modulus $m\ge1$ and every $J$, \[ \gcd(m,b_J,b_{J+1},\ldots)=1. \tag{1} \] Indeed, any common divisor of the displayed numbers divides every tail increment $\varepsilon_j$, including an increment equal to $1$.Let $R_N\subseteq\mathbb Z/m\mathbb Z$ be the residues of subset sums of $b_J,\ldots,b_N$, including $0$. These finite sets increase with $N$, so eventually stabilize to a nonempty set $R$. At every subsequent index $j$, adjoining $b_j$ gives $R\cup(R+b_j)=R$, hence $R+b_j=R$ by equality of finite cardinalities. Therefore $R$ is invariant under the subgroup generated by all tail $b_j$. By $1$ this is the entire cyclic group, so $R=\mathbb Z/m\mathbb Z$. Every residue is thus achieved by a subset sum from a finite prefix of any tail. No assumption that single terms hit every residue is needed.
3. Complete reconstruction of the dyadic--nondyadic case
Write $\alpha=m/2^s$ with $m\ge1$ an integer and $s\ge0$. The $\alpha$-sequence contains the tail $m,2m,4m,\ldots$, whose subset sums are exactly $m\mathbb Z_{\ge0}$. By the preceding lemma choose, for each residue $r$ modulo $m$, a finite $\beta$-subset sum $B_r\equiv r\pmod m$. Set $C=\max_r B_r$. For every $N\ge C$, choose $r\equiv N\pmod m$ and write \[ N=B_r+m q,\qquad q\ge0. \] The second summand is a binary subset sum of the $\alpha$-tail. The two index families are disjoint, so no term is reused. This proves completeness whenever one parameter is dyadic and the other is not, including the corresponding irrational-ratio cases.4. An exact finite criterion when both parameters are dyadic
Suppose $\alpha=a/2^s$ and $\beta=b/2^t$ with positive integers $a,b$. Let $H$ be the finite multiset of the terms before the respective tails $a,2a,\ldots$ and $b,2b,\ldots$, and put $g=\gcd(a,b)$. Then \[ P(\alpha,\beta)=P(H)+a\mathbb Z_{\ge0}+b\mathbb Z_{\ge0}. \tag{2} \] The numerical semigroup on the right contains every sufficiently large multiple of $g$: dividing by $g$, write $A=a/g,B=b/g$; for each residue modulo $A$ choose $0\le v<A$ with $Bv$ in that residue. Every sufficiently large integer in the residue is $Bv+Au$ with $u\ge0$. Consequently $2$ is complete if and only if the subset sums of $H$ hit every residue modulo $g$. Necessity follows because the two tails contribute only multiples of $g$; sufficiency follows by choosing a fixed head sum in each residue and then using the tails. The criterion is independent of the chosen dyadic representations, because $2$ always gives exactly the same subset-sum set.5. Assessment and provenance
Both arguments use an exact tail supplying all sufficiently large multiples of a fixed modulus. For two general nondyadic parameters, the residue lemma remains valid, but it does not supply such a tail. Surjectivity modulo every modulus is not itself completeness. The general irrational-ratio case and the general $\gamma\in(1,2)$ variant remain unresolved in this attempt.The statement and attribution of the special case to Hegyvári [He89] are at https://www.erdosproblems.com/354, checked 2026-09-25. The earlier GPT Pro 5.2 special-case argument was checked and reconstructed; in particular one must not infer $\gcd(R)=1$ merely from $\gcd(m,R)=1$. The finite-group argument above avoids that incorrect inference. All inputs to the proof are elementary and proved here. No novelty or formal verification is claimed.