Erdős Problem #254

Erdős Problem #254

1) ROUND-2 OBJECTIVE

Path (C): isolate a single sharp obstruction whose resolution would settle the problem.

Round-1 extracted only very basic consequences from the hypotheses. The best Round-2 move is to prove a dyadic bootstrap theorem showing that, once one finite initial segment of $A$ creates a long enough interval of subset sums, the hypothesis \[ |A\cap[1,2x]|-|A\cap[1,x]|\to\infty \] by itself propagates that interval forever. This would identify the exact missing bridge from the hypotheses to completeness.

2) Round-1 FOUNDATION USED

I use only the following Round-1 facts.

• Writing \[ B_j:=A\cap(2^j,2^{j+1}], \qquad m_j:=|B_j|, \] Round-1 showed that $m_j\to\infty$.
• Round-1 also showed that the second hypothesis implies $\gcd(A)=1$, but the new theorem below does not actually need that fact.

3) NEW INSIGHT / TOOL (ROUND-2)

The new tool is an interval absorption lemma for subset sums.

It shows that the only thing still missing is a "starter interval" of subset sums inside one sufficiently large dyadic initial segment.

More precisely, I prove:

If for some large $J$ the finite set $A\cap[1,2^J]$ already has a subset-sum interval of length at least $2^{J+1}$, then the dyadic growth condition $m_j\to\infty$ forces $A$ to be complete.

So the second hypothesis involving \[ \sum_{n\in A}\{\theta n\}=\infty \] must, in any successful proof, be used only to manufacture such a starter interval.

4) ATTACK PLAN (ROUND-2)

The exact Round-1 gap was the absence of any mechanism turning the two qualitative hypotheses into actual intervals inside the subset-sum set \[ \Sigma(A):=\left\{\sum_{a\in F}a:\ F\subseteq A\text{ finite}\right\}. \]

The new plan is:

• prove a general interval-absorption lemma for subset sums;
• apply it block-by-block to the dyadic decomposition $A=\bigsqcup_j B_j$;
• conclude that once one interval has length at least the next dyadic scale, all later dyadic blocks can be absorbed greedily.

This produces a single sharply formulated obstruction to completeness.

5) WORK (ROUND-2)

For a finite set $F\subseteq \mathbf{N}$, write \[ \Sigma(F):=\left\{\sum_{a\in E} a:\ E\subseteq F\right\}. \]

Lemma 1 (interval absorption by one new element).

Let $F\subseteq \mathbf{N}$ be finite, and suppose there is an interval \[ [L,U]\subseteq \Sigma(F). \] Let $c\in \mathbf{N}$ with \[ c\le U-L+1. \] Then \[ [L,U+c]\subseteq \Sigma(F\cup\{c\}). \]

Proof.

The sums not using $c$ give the interval $[L,U]$, and the sums using $c$ give the translated interval \[ [L+c,U+c]. \] The assumption $c\le U-L+1$ is equivalent to \[ L+c\le U+1, \] so these two intervals overlap or are adjacent. Hence their union is the full interval \[ [L,U+c]. \] Every sum in this union uses distinct elements because $c$ is a new element not in $F$. $\square$

Theorem 2 (dyadic bootstrap from one starter interval).

Assume $m_j\to\infty$. Suppose there exists an integer $J$ such that:

• $m_j\ge 2$ for every $j\ge J+1$;
• the finite set $A\cap[1,2^J]$ has a subset-sum interval \[ [L_J,U_J]\subseteq \Sigma\left(A\cap[1,2^J]\right) \] of length \[ W_J:=U_J-L_J+1\ge 2^{J+1}. \]

Then every sufficiently large integer belongs to $\Sigma(A)$.

Proof.

We induct on $j\ge J$.

Induction hypothesis: there exists an interval \[ [L_J,U_j]\subseteq \Sigma\left(A\cap[1,2^j]\right) \] of length \[ W_j:=U_j-L_J+1\ge 2^{j+1}. \] This is true for $j=J$ by assumption.

Now fix $j\ge J$ and write the next dyadic block as \[ B_{j+1}=\{b_1<b_2<\cdots<b_t\}, \qquad t=m_{j+1}. \] Every element of $B_{j+1}$ satisfies \[ 2^j < b_i \le 2^{j+1} \le W_j. \] Therefore Lemma 1 applies to $b_1$, giving an interval of length $W_j+b_1$. Since $b_2\le 2^{j+1}\le W_j < W_j+b_1$, Lemma 1 applies again to $b_2$. Continuing in this way, we can absorb the entire block $B_{j+1}$ one element at a time, obtaining an interval \[ [L_J,U_{j+1}]\subseteq \Sigma\left(A\cap[1,2^{j+1}]\right) \] of length \[ W_{j+1}=W_j+\sum_{i=1}^{t} b_i. \] Because $t\ge 2$ and each $b_i>2^j$, \[ \sum_{i=1}^{t} b_i > 2\cdot 2^j = 2^{j+1}. \] Hence \[ W_{j+1}>W_j+2^{j+1}\ge 2^{j+1}+2^{j+1}=2^{j+2}. \] So the induction closes.

Thus for every $j\ge J$, the finite set $A\cap[1,2^j]$ has an interval of subset sums with the same left endpoint $L_J$ and with length at least $2^{j+1}$. As $j\to\infty$, these lengths tend to infinity, so \[ [L_J,\infty)\subseteq \Sigma(A). \] Therefore every sufficiently large integer is a sum of distinct elements of $A$. $\square$

Corollary 3 (sharp obstruction to a counterexample).

Assume the hypotheses of Problem #254 and suppose $A$ is not complete. Then for every sufficiently large $J$ the finite subset-sum set \[ \Sigma\left(A\cap[1,2^J]\right) \] contains no interval of length $2^{J+1}$.

Proof.

Round-1 gives $m_j\to\infty$, so there exists $J_0$ such that $m_j\ge 2$ for all $j\ge J_0$. If for some $J\ge J_0$ the set $\Sigma(A\cap[1,2^J])$ contained an interval of length $2^{J+1}$, then Theorem 2 would imply that $A$ is complete, contradiction. $\square$

Interpretation.

The unresolved part of Problem #254 is now concentrated in one sharply formulated finite statement:

Produce, from the two original hypotheses, one initial dyadic scale $2^J$ for which the finite set $A\cap[1,2^J]$ already has a subset-sum interval of length at least $2^{J+1}$.

Once such a scale exists, the dyadic growth hypothesis alone finishes the proof.

6) ADVERSARIAL VERIFICATION

• The absorption lemma depends on interval length, not on the right endpoint alone. This was checked carefully: the overlap condition is exactly $c\le U-L+1$.
• Distinctness of summands is preserved, because each absorbed element is added only once and is not already present in the finite set used at that step.
• The theorem needs $m_j\ge 2$ eventually, not merely $m_j\ge 1$. This is why the hypothesis $m_j\to\infty$ is used at precisely that point.
• The second hypothesis involving $\sum_{n\in A}\{\theta n\}$ plays no role in the bootstrap theorem itself; this is intentional, and it cleanly isolates where any future proof must use that hypothesis.

So the new theorem is internally consistent and pinpoints a single missing bridge rather than leaving the obstruction diffuse.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The strict Round-2 advance is a dyadic bootstrap theorem:

If one can obtain just one subset-sum interval of length at least the next dyadic scale inside some finite initial segment $A\cap[1,2^J]$, then the dyadic growth condition propagates this interval forever and forces completeness.

Equivalently, any genuine counterexample would have to avoid such starter intervals at every sufficiently large dyadic scale. That is a much sharper obstruction than in Round-1.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 35%

9) REFERENCES

Only references actually used or checked.

• T. F. Bloom, Erdős Problem #254, https://www.erdosproblems.com/254, accessed 2026-03-07.
• J. W. S. Cassels, On the representation of integers as the sums of distinct summands taken from a fixed set, Acta Sci. Math. (Szeged) 21 $1960$, 111--124.

Problem 254: correcting the interval bootstrap and isolating its input

1) OBJECTIVE AND SOURCE REVIEW

Attempt dated 2026-09-23. I read the complete 254.tex. Its target is completeness of distinct-element subset sums under growing dyadic block counts and the problem's fractional-part divergence assumption. The supplied attempt obtains a conditional interval bootstrap but does not produce its starting interval. I audit that bootstrap and make its exact sufficient input explicit.

2) WORK

Let $F$ be finite, with $[L,U]\cap\mathbb Z\subseteq\Sigma(F)$, and put $W=U-L+1$. List the unused elements increasingly as $b_1,b_2,\ldots$. If \[ b_i\le W+\sum_{h<i}b_h\qquad(i\ge1), \] then induction gives \[ \left[L,U+\sum_{h\le i}b_h\right]\cap\mathbb Z \subseteq\Sigma(F\cup\{b_1,\ldots,b_i\}). \] Indeed, adjoining $b_i$ adds a translate of the preceding interval, and the displayed inequality says the two integer intervals overlap or are adjacent. This proves completeness if the $b_i$ are infinite. For this particular union-of-translates construction the first failed inequality leaves an actual gap between the intervals arising from subsets of the preceding elements and those using $b_i$; additional subset sums of $F$ outside $[L,U]$ may still fill it, so failure is not a converse for completeness.

Here is a corrected dyadic corollary. If $F=A\cap[1,2^J]$ contains an interval of subset sums of length at least $2^{J+1}$, and \[ |A\cap(2^j,2^{j+1}]|\ge2\qquad\text{for every }j\ge J, \] then $A$ is complete. At the beginning of block $j$, maintain width at least $2^{j+1}$. Every member of that block is at most that width, so it can be absorbed. Two members increase the width by more than $2^{j+1}$, giving the invariant for block $j+1$.

The supplied statement began its count hypothesis at $j\ge J+1$, but its induction tried to absorb the block $(2^J,2^{J+1}]$. That block has no guaranteed two elements under the stated hypothesis. Starting the count hypothesis at $J$ repairs the proof; equivalently, supply the wider starter needed to jump directly to the next controlled block.

3) ADVERSARIAL VERIFICATION

Growing dyadic counts and $\gcd(A)=1$ alone cannot produce the missing starter. For $A=3\mathbb N\cup\{1\}$, both hold, but every subset sum is $0$ or $1$ modulo $3$. At $\theta=1/3$, the fractional-part sum is only $1/3$, so this example does not satisfy the additional divergence assumption. It illustrates precisely why that assumption still needs to enter the proof.

4) FINAL

UNRESOLVED. The propagation step is rigorous after an indexing correction. Deriving a sufficiently long interval from the original hypotheses remains entirely necessary; no implication from the fractional-part condition to that interval has been established here.

5) SOURCES CHECKED

The complete supplied 254.tex, read 2026-09-23. The interval proof and modular obstruction above are self-contained. An attempted official-page retrieval was unavailable, so no additional external formulation is asserted.

6) COMPLETION ESTIMATE

Subjective progress toward proving completeness under all original hypotheses. COMPLETION: 10%

Erdős Problem #254

1) FORMAL RESTATEMENT

Let $A\subseteq \mathbb{N}$. Write $A(x):=\left|A\cap[1,x]\right|$ for $x\ge 1$ (with $[1,x]$ understood as $\{n\in\mathbb{N}:1\le n\le x\}$). Assume: \begin{align} A(2x)-A(x) &\xrightarrow[x\to\infty]{} \infty,\label{wsref-0-65-71-3a-64-79-61-64-69-63-5f-67-72-6f-77-74-68}\\ \sum_{n\in A} \{\theta n\} &= \infty\quad\text{for every }\theta\in(0,1),\label{wsref-0-65-71-3a-74-68-65-74-61-5f-64-69-76} \end{align} where $\{y\}$ denotes the distance from $y$ to the nearest integer (so $\{y\}\in[0,1/2]$).

Conclusion to prove: There exists $N_0$ such that every integer $N\ge N_0$ can be expressed as a sum of distinct elements of $A$.

2) QUICK LITERATURE/CONTEXT CHECK

Cassels proved the conclusion under stronger hypotheses: instead of (eq:dyadic_growth) he assumed \[ \frac{A(2x)-A(x)}{\log\log x}\to\infty, \] and instead of (eq:theta_div) he assumed $\sum_{n\in A} \{\theta n\}^2=\infty$ for every $\theta\in(0,1)$ [Ca60]. The version stated above is listed as open in [ErdosProblems254].

3) ATTACK PLAN

Track A (prove): Attempt to extract from $A$ a "complete" increasing subsequence $(a_j)$ satisfying a coin-representation criterion such as $a_{j+1}\le 1+\sum_{i\le j}a_i$ after some point, or prove directly that the subset-sum set \[ \Sigma(A):=\Big\{\sum_{a\in F} a\;:\;F\subseteq A\text{ finite}\Big\} \] contains all integers beyond some threshold. A Fourier-analytic approach is natural: if the exponential sums $\sum_{n\in A} e(\theta n)$ are small in aggregate, subset sums should spread.

Track B (disprove): Try to build $A$ satisfying (eq:dyadic_growth)--(eq:theta_div) but for which $\Sigma(A)$ misses infinitely many integers (e.g. misses an arithmetic progression). Condition (eq:theta_div) blocks simple congruence obstructions (like $A\subseteq q\mathbb{N}$), so any counterexample would need a subtler obstruction.

4) WORK

4.1 Immediate consequences of the hypotheses

Infinitude and dyadic thickness.

Condition (eq:dyadic_growth) implies that for every $M$ there exists $x_M$ such that for all $x\ge x_M$ the interval $(x,2x]$ contains at least $M$ elements of $A$. In particular $A$ is infinite.

No fixed modulus obstruction; in particular $\gcd(A)=1$.

Fix an integer $q\ge2$ and take $\theta=1/q$. For $n\in\mathbb{N}$, the quantity $\{n/q\}$ equals $0$ exactly when $q\mid n$, and otherwise $\{n/q\}\ge 1/q$. If $A$ contained only finitely many integers not divisible by $q$, then $\sum_{n\in A}\{n/q\}$ would be finite, contradicting (eq:theta_div). Therefore, for every $q\ge2$, the set $A$ contains infinitely many integers not divisible by $q$. In particular, $\gcd(A)=1$.

4.2 Relation to Cassels' theorem

Cassels' result [Ca60] proves the desired completeness conclusion under two strengthened assumptions:

1. Dyadic growth strengthened from $A(2x)-A(x)\to\infty$ to $(A(2x)-A(x))/\log\log x\to\infty$.
2. Divergence strengthened from $\sum \{\theta n\}=\infty$ to $\sum \{\theta n\}^2=\infty$ for all $\theta\in(0,1)$.

The implication "$\sum \{\theta n\}=\infty\Rightarrow\sum \{\theta n\}^2=\infty$" is false in general (bounded terms can have divergent sum but convergent sum of squares), so Cassels' hypotheses do not follow formally from (eq:dyadic_growth)--(eq:theta_div).

4.3 Where a naive attempt stalls

A standard sufficient condition for a sequence $1\le a_1<a_2<\cdots$ to be complete (every sufficiently large integer is a sum of distinct terms) is the "greedy" inequality \[ a_{j+1} \le 1+\sum_{i\le j} a_i\qquad\text{for all large }j, \] which ensures that consecutive representable intervals expand without gaps. Condition (eq:dyadic_growth) guarantees many elements of $A$ in each dyadic interval, but does not obviously give control on the relative sizes needed to force such a greedy inequality for some subsequence.

Similarly, the divergence condition (eq:theta_div) suggests $A$ is not concentrated near multiples of $1/\theta$ for any fixed $\theta$, but converting this into uniform smallness of Fourier coefficients for $A$ (which would help show subset sums fill intervals) requires quantitative estimates, whereas (eq:theta_div) is qualitative.

5) VERIFICATION (adversarial check)

• The deduction that $A$ has infinitely many elements not divisible by each $q\ge2$ is rigorous and uses only $\theta=1/q$.
• The claim that Cassels' hypotheses are stronger and not implied by (eq:dyadic_growth)--(eq:theta_div) is justified by the general fact that divergence of $\sum x_n$ for bounded $x_n\ge0$ does not force divergence of $\sum x_n^2$.
• No step here assumes equidistribution or any deep estimate; the point is precisely that such quantitative input is missing.

6) FINAL

UNRESOLVED.

1. (i) Most advanced partial result proved here. From the stated hypotheses one can deduce $\gcd(A)=1$ and that $A$ meets every dyadic interval $(x,2x]$ in arbitrarily large finite sets.
2. (ii) Strongest obstruction / missing lemma. What is missing is a mechanism that converts the qualitative divergence condition (eq:theta_div) into a quantitative additive-structure conclusion about the subset-sum set $\Sigma(A)$ (for example, a bound forcing long intervals inside $\Sigma(A)$). Cassels' theorem achieves this using stronger growth and a square-divergence condition.
3. (iii) Next concrete steps. One concrete direction is to attempt a "quantitative upgrade" of (eq:theta_div) to a lower bound on the average of $\{\theta n\}$ over $A\cap[1,x]$ for many $x$ (uniform in $\theta$), then feed that into Fourier analysis of subset sums. Another is to attempt to extract a complete subsequence from $A$ using the dyadic thickness to enforce a greedy-type inequality.
4. (iv) Counterexample search description. A potential counterexample would be a set $A$ built in blocks so that $A(2x)-A(x)\to\infty$ and for each fixed $\theta$ the terms $\{\theta n\}$ do not decay too fast along $A$, yet the subset sums avoid infinitely many integers. Any construction must avoid congruence obstructions (ruled out by (eq:theta_div) at rational $\theta$), so the obstruction would likely be more subtle (e.g. structured gaps in the subset-sum semigroup).

7) COMPLETION ESTIMATE

$\mathbf{90\%}$ confidence that the deductions recorded here are correct; $\mathbf{0\%}$ confidence of a full resolution (the stated form is open).

---

References

• [ErdosProblems254] T. F. Bloom, Erdős Problem #254, https://www.erdosproblems.com/254 (accessed 2026-01-17).
• [Ca60] J. W. S. Cassels, On the representation of integers as the sums of distinct summands taken from a fixed set, Acta Sci. Math. (Szeged) $1960$, 111--124.
• [Er52] P. Erdős, Problem 4493, Amer. Math. Monthly $1952$, 557--558.
• [Er58b] P. Erdős, Sur certaines séries à valeur irrationnelle, Enseign. Math. $2$ $1958$, 93--100.
• [Er88c] P. Erdős, On the irrationality of certain series: problems and results, in New advances in transcendence theory (Durham, 1986), $1988$, 102--109.
• [FLC07] J. B. Friedlander, F. Luca, and M. Stoiciu, On the irrationality of a divisor function series, Integers $2007$.
• [Pr22] K. Pratt, The irrationality of a divisor function series of Erdős and Kac, arXiv:2209.11124 $2022$.
• [ScPu06] J. C. Schlage-Puchta, The irrationality of a number theoretical series, Ramanujan J. $2006$, 455--460.