Erdős Problem #1096

Erdős Problem 1096: gaps between sums of powers

1. Statement and explicit external inputs

For $q>1$, let \[ X(q)=\left\{\sum_{i\ge0}\epsilon_iq^i:\epsilon_i\in\{0,1\},\ \epsilon_i=0\text{ eventually}\right\} =\{0=x_1<x_2<\cdots\}. \] Does $x_{j+1}-x_j\to0$ for every $q$ in some fixed interval $(1,1+\epsilon)$? Yes. We prove this for $1<q<\sqrt{q_0}$, where $q_0\approx1.324717957$ is the real root of $q_0^3=q_0+1$. This is a sufficient interval, not a claimed optimal threshold. We explicitly use three established inputs. First, $q_0$ is the smallest Pisot number, where a Pisot number is a real algebraic integer greater than one whose other conjugates have modulus less than one. Second, Feng's Theorem 1.2 states that the signed spectrum \[ Y(Q)=\left\{\sum_i e_iQ^i:e_i\in\{-1,0,1\},\ e_i=0\text{ eventually}\right\} \] is dense in $\mathbb R$ whenever $1<Q<2$ is not Pisot. Third, the small-gap block lemma, stated as Lemma 2.2 by Akiyama--Komornik, says that if the successive gaps in $X(Q)$ have lower limit zero, then for every $0<\delta<\Delta$ some consecutive finite block has every gap less than $\delta$ and total span greater than $\Delta$. The density theorem and this block lemma are external inputs; a small gap alone must not be substituted for the entire block conclusion. Sources: De-Jun Feng, On the topology of polynomials with bounded integer coefficients, J. Eur. Math. Soc. 18 $2016$, https://doi.org/10.4171/JEMS/587; Akiyama--Komornik, Discrete spectra and Pisot numbers, https://arxiv.org/abs/1103.4508, Lemmas 2.2--2.5 and the discussion of the smallest Pisot number. The following gives the remaining gap-transfer argument explicitly.

2. Local finiteness and a uniform elementary gap bound

Below a fixed height $T$, a nonzero digit at position $i$ forces $q^i\le T$, so there are only finitely many possible digit strings. Thus $X(q)$ is locally finite, unbounded, and has the indicated increasing enumeration. For $1<q\le2$, every successive gap is at most one. To prove this, let $S_N$ use positions $0,\ldots,N$, with largest element $M_N=(q^{N+1}-1)/(q-1)$. Starting from $S_0=\{0,1\}$, use \[ S_{N+1}=S_N\cup(q^{N+1}+S_N). \] Both translated pieces have internal gaps at most one by induction. If their enclosing intervals overlap, their union also has gaps at most one; otherwise the only extra gap is \[ q^{N+1}-M_N=\frac{q^{N+1}(q-2)+1}{q-1}\le1. \] Every pair of consecutive elements of $X(q)$ appears in a sufficiently large $S_N$, proving the assertion.

3. Small even-position gaps imply small gaps everywhere

Suppose $1<q<\sqrt2$ and $q^2$ is not Pisot, and put $Q=q^2$. Since $Y(Q)=X(Q)-X(Q)$ is dense, there are arbitrarily close distinct points of $X(Q)$. Its local finiteness ensures that such pairs cannot all stay in a bounded interval; consequently its consecutive gaps have lower limit zero. Write $X(Q)=\{u_0<u_1<\cdots\}$ and $v_j=qu_j$. The preceding uniform bound gives $v_{j+1}-v_j\le q$, and $v_j\to\infty$. Also \[ X(Q)+qX(Q)\subseteq X(q), \] because the first summand uses even digit positions and the second odd positions, without any overlap. Fix $0<\delta<q$. By the block lemma, choose $u_n,\ldots,u_N$ with all intervening gaps less than $\delta$ and $u_N-u_n>q$. For any real $a\ge u_n$, choose $j$ such that \[ u_n+v_j\le a<u_n+v_{j+1}. \] Then $u_n\le a-v_j<u_n+q<u_N$. Within the chosen block, the first point strictly exceeding $a-v_j$ differs from it by less than $\delta$, including when $a-v_j$ itself is a block point. Thus $(a,a+\delta)$ contains an element of $X(Q)+qX(Q)$, and hence of $X(q)$. This holds for every $a\ge u_n$, so all sufficiently late gaps of $X(q)$ are less than $\delta$. Letting $\delta\downarrow0$ proves convergence to zero. Finally, if $1<q<\sqrt{q_0}$, then $1<q^2<q_0<2$, so $q^2$ cannot be Pisot. The preceding argument applies uniformly to every $q$ in that interval. Therefore $\epsilon=\sqrt{q_0}-1>0$ answers the stated existence question.

4. Why Pisot numbers obstruct the conclusion

For completeness, the obstruction has a short independent proof. Suppose $q$ is Pisot with other conjugates $q_2,\ldots,q_d$. A nonzero difference of elements of $X(q)$ is $P(q)$ for an integer polynomial with coefficients in $\{-1,0,1\}$. Its algebraic norm is a nonzero integer, and \[ |P(q_j)|\le\frac1{1-|q_j|}\quad(j\ge2). \] Hence \[ |P(q)|\ge\prod_{j=2}^d(1-|q_j|)>0. \] All distinct points are uniformly separated, so their successive gaps cannot tend to zero. This does not identify the exact non-Pisot threshold for the stronger gap-limit property.

5. Assessment

The requested affirmative answer is derived with an explicit positive interval. Local finiteness, the unit gap bound, the full even/odd-position transfer and the Pisot obstruction are proved here. The smallest-Pisot theorem, Feng's signed-spectrum density theorem and the stated small-gap block lemma remain explicit external dependencies; no independent proof of those inputs or local Lean verification is claimed. Source statement: https://www.erdosproblems.com/1096.

Completion rate estimate: 100%.

FORMAL RESTATEMENT

Fix a real number $q>1$. Define the set \[ X(q):=\Big\{\sum_{i\in S} q^i\ :\ S\subseteq \{0,1,2,\dots\}\text{ finite}\Big\}\subset\mathbb{R}_{\ge 0}. \] Let $\{x_k\}_{k\ge 1}$ be the strictly increasing sequence of distinct elements of $X(q)$, so $x_1=0<x_2<\cdots$.

Question. Is it true that there exists $\epsilon>0$ such that for every $q$ with $1<q<1+\epsilon$ we have \[ x_{k+1}-x_k\to 0\quad\text{as }k\to\infty? \]

QUICK LITERATURE/CONTEXT CHECK

The problem text mentions a conjectured threshold near $q_0\approx 1.3247$ (real root of $x^3=x+1$) and states (i) a result that Pisot--Vijayaraghavan numbers cannot have the gap-$\to0$ property, and (ii) a uniform bound $x_{k+1}-x_k\le 1$ for all $k$ when $1<q\le 2$. Per the integrity rule for this task, I do not assert any additional literature beyond what is written in the problem file.

ATTACK PLAN

• Prove from first principles the uniform gap bound $x_{k+1}-x_k\le 1$ for $1<q\le 2$ (a strong partial result).
• Use the recursive structure $X_{m+1}=X_m\cup(X_m+q^m)$ to understand how gaps behave as $m$ grows.
• Compute large initial segments numerically for $q$ close to $1$ to see whether typical gaps appear to shrink.

WORK

Lemma 1096.1 (finite-stage decomposition). For $m\ge 0$, define the finite subset \[ X_m(q):=\Big\{\sum_{i=0}^{m-1} \varepsilon_i q^i\ :\ \varepsilon_i\in\{0,1\}\Big\}. \] Then \[ X_{m+1}(q)=X_m(q)\ \cup\ \left(X_m(q)+q^m\right), \] and the maximum element of $X_m(q)$ is \[ \max X_m(q)=\sum_{i=0}^{m-1} q^i=\frac{q^m-1}{q-1}. \]

Proof. A subset $S\subseteq\{0,1,\dots,m\}$ either does not contain $m$ or does contain $m$. If it does not contain $m$, its sum lies in $X_m(q)$. If it does contain $m$, then writing $S=S'\cup\{m\}$ with $S'\subseteq\{0,\dots,m-1\}$, we have \[ \sum_{i\in S}q^i=q^m+\sum_{i\in S'}q^i\in X_m(q)+q^m. \] This proves the union decomposition.

For the maximum, since all terms $q^i$ are positive, the maximum is attained by taking all $\varepsilon_i=1$, giving the geometric sum $\sum_{i=0}^{m-1}q^i=(q^m-1)/(q-1)$. $\square$

Lemma 1096.2 (uniform gap bound for $1<q\le 2$). Assume $1<q\le 2$. For every $m\ge 1$, if we list the distinct elements of $X_m(q)$ in increasing order, the gap between any two consecutive elements is at most $1$. Consequently, for the full ordered sequence $0=x_1<x_2<\cdots$ of $X(q)$, we have \[ x_{k+1}-x_k\le 1\quad\text{for all }k\ge 1. \]

Proof. We prove by induction on $m$ that the maximum gap between consecutive elements in the sorted list of $X_m(q)$ is at most $1$.

Base case $m=1$. We have $X_1(q)=\{0,1\}$, so the only gap is $1$.

Induction step. Assume the claim for $X_m(q)$, and consider $X_{m+1}(q)$. By Lemma 1096.1, \[ X_{m+1}(q)=A\cup (A+q^m),\quad\text{where }A:=X_m(q). \] Sort $A$ increasingly as $a_1<\cdots<a_r$ (distinct values). Then $A+q^m$ sorts as $(a_1+q^m)<\cdots<(a_r+q^m)$.

Gaps within the $A$ block are at most $1$ by the induction hypothesis. The same holds within the shifted block $A+q^m$ (since shifting does not change gaps).

It remains to control the gap between the top of $A$ and the bottom of $A+q^m$. The smallest element of $A+q^m$ is $q^m$ (shift of $0\in A$), and the largest element of $A$ is $\max A=(q^m-1)/(q-1)$ by Lemma 1096.1. Therefore the separation between the two blocks is \[ \Delta_m:=q^m-\frac{q^m-1}{q-1}. \] If $\Delta_m\le 0$, then the two blocks overlap as intervals, so there is no gap created between them. If $\Delta_m>0$, then the union creates a gap of size exactly $\Delta_m$ between the last element of $A$ and the first element of $A+q^m$.

We now show $\Delta_m\le 1$ for all $m$ whenever $1<q\le 2$. Compute \[ \Delta_m-1 =\left(q^m-\frac{q^m-1}{q-1}\right)-1 =\frac{(q-1)q^m-(q^m-1)-(q-1)}{q-1} =\frac{(q-2)(q^m-1)}{q-1}. \] Since $1<q\le 2$, we have $q-2\le 0$, and also $q^m-1\ge 0$ and $q-1>0$. Hence $(q-2)(q^m-1)/(q-1)\le 0$, so $\Delta_m-1\le 0$, i.e. $\Delta_m\le 1$.

Therefore every possible new "inter-block" gap is $\le 1$, and the within-block gaps are $\le 1$ by induction. This completes the induction for all $m$.

Finally, to pass from $X_m(q)$ to $X(q)$: given any bound $B>0$, if $q^m>B$ then every element of $X(q)$ that is $\le B$ uses only exponents $<m$ (since any term $q^i$ with $i\ge m$ is already $>B$). Thus the initial segment of the increasing sequence $(x_k)$ up to $B$ coincides with the sorted list of $X_m(q)$ up to $B$, and the gap bound $\le 1$ carries over to all $k$. $\square$

FAST REALITY CHECK (numerics for $q$ near $1$).

Because $X(q)$ is infinite, I approximated initial segments by taking $X_m(q)$ for moderate $m$, sorting, and examining the first $K$ consecutive gaps. For $q=11/10$ and $m=18$, I also computed all $2^{18}=262144$ sums exactly as rationals (scaled integers), obtaining an exact minimum gap.

Exact rational check: for $q=11/10$ and $m=18$, among all distinct elements of $X_{18}(q)$, \[ \min\{y'-y:\ y<y',\ y,y'\in X_{18}(11/10)\}=1.8372458061\times 10^{-7}. \]

Floating-point exploratory check (first $K$ gaps within $X_m$):

• For $q=1.1$ with $m=18$, among the first $K=50{,}000$ sorted values from $X_{18}(q)$ (after removing the trivial initial gap $1$), the smallest observed gap was $\approx 4.28\times 10^{-7}$ and the largest observed gap was $0.1$.
• For $q=1.001$ with $m=20$, among the first $K=50{,}000$ sorted values from $X_{20}(q)$ (after removing the trivial initial gap $1$), the smallest observed gap was $\approx 1.20\times 10^{-13}$.

These computations provide evidence that very small gaps occur already at modest scales when $q$ is close to $1$, but they do not by themselves prove $x_{k+1}-x_k\to 0$.

VERIFICATION

• Lemma 1096.1 is purely combinatorial: every subset either contains $m$ or not.
• Lemma 1096.2 checks the only possible new gap created when passing from $X_m$ to $X_{m+1}$, and bounds it by an explicit algebraic calculation. The sign case $\Delta_m\le 0$ was handled separately.
• The "finite-stage implies initial-segment" argument at the end of Lemma 1096.2 is checked: if $x\le B$ and $q^m>B$, then no term $q^i$ with $i\ge m$ can appear in a representation of $x$.
• The exact rational computation for $q=11/10$ avoids floating-point artifacts.

UNRESOLVED

(i) Strongest proved partial result here. For every $q$ with $1<q\le 2$, we proved $x_{k+1}-x_k\le 1$ for all $k$ (Lemma 1096.2). We also established the recursive decomposition $X_{m+1}=X_m\cup(X_m+q^m)$ (Lemma 1096.1).

(ii) First gap (crisp). Prove (or disprove) that there exists $\epsilon>0$ such that for every $q\in(1,1+\epsilon)$ and every $\delta>0$ there exists $K$ with \[ x_{k+1}-x_k<\delta\quad\text{for all }k\ge K. \]

(iii) Top 3 next moves.

1. Quantify how much overlap occurs between $X_m$ and $X_m+q^m$ for $q$ close to $1$ and large $m$, and convert overlap into explicit small gaps between consecutive sorted sums.
2. Replace floating computations by exact arithmetic for carefully chosen rational $q$ and larger $m$ to search for persistent large gaps (or to measure how the maximum gap in the tail behaves).
3. Try to relate the gap-$\to0$ property to the existence of many near-collisions of the form $\sum \varepsilon_i q^i\approx \sum \varepsilon'_i q^i$ (small values of polynomials with coefficients in $\{-1,0,1\}$ evaluated at $q$).

(iv) Minimal counterexample structure. A counterexample for small $\epsilon$ would consist of some $q\in(1,1+\epsilon)$ and a $\delta>0$ such that infinitely many consecutive gaps satisfy $x_{k+1}-x_k\ge \delta$. This would mean infinitely many real intervals of length $\delta$ contain no elements of $X(q)$, forcing strong "no-approximation" constraints on differences of two subset sums $\sum \varepsilon_i q^i-\sum \varepsilon'_i q^i$.