Erdős Problem #347

Erdős problem #347

1) FORMAL RESTATEMENT. Construct increasing positive integers with consecutive ratio tending to $2$ whose finite subset sums have natural density $1$ after any finite deletion.

2) CONTEXT AND METHOD. The current statement is affirmative. The following reconstructs the block construction of Enrique Barschkis, based on Tao and van Doorn. It supplies the greedy and counting details, including passage from the block endpoints to every real cutoff. This is a known construction, with no novelty claim. The earlier local attempt's modular obstruction is only necessary: it does not imply impossibility.

3) CONSTRUCTION AND RATIOS. For $j\ge0$, put \[ k_j=4+\lceil\log_2\log_2(j+16)\rceil,\quad q_j=2^{k_j}-2, \quad M_0=10,\quad M_{j+1}=\lfloor(q_j+1/2)M_j\rfloor. \] Thus $q_j\ge62$, $q_j\asymp\log(j+16)$, $k_j\to\infty$, and \[ q_jM_j+1<M_{j+1}<(q_j+1)M_j, \qquad M_j\ge10\cdot62^j. \] Concatenate the blocks \[ M_j,2M_j,\ldots,2^{k_j-2}M_j, (2^{k_j-1}-1)M_j+1. \] Every block and every boundary is strictly increasing. Ratios inside a block equal $2$, except the last, which is $2-2^{2-k_j}+2^{2-k_j}/M_j$. The boundary ratio is \[ \frac{M_{j+1}}{(2^{k_j-1}-1)M_j+1} =2+O(2^{-k_j})+O(M_j^{-1}). \] Consequently all consecutive ratios tend to $2$.

4) GREEDY REPRESENTATION AND CORRECTION. Fix a tail of blocks $j\ge j_0$. Define \[ c_j=(2^{k_j-1}-1)M_j, \] \[ B_j=\{hM_j:0\le h\le2^{k_j-1}-1\} \cup\{hM_j+1:2^{k_j-1}\le h\le2^{k_j}-2\}. \] Every member of $B_j$ is a subset sum of its block. There are $q_j+1$ members, one of which is $c_j$. The extra subset sum $c_j+1$, excluded from $B_j$, is available by using the block's last term instead of all its preceding terms.

Consecutive entries of $B_j$ have gap at most $M_j+1$. Its largest entry is $q_jM_j+1<M_{j+1}$, and the remaining distance to $M_{j+1}$ is less than $M_j$. Hence, for every integer $0\le x\le M_{j+1}$, subtracting the largest $b\in B_j$ with $b\le x$ leaves an integer in $[0,M_j]$. Descending through the blocks gives, for every integer $0\le m\le M_{N+1}$, \[ m=\sum_{j=j_0}^{N}b_j+d,\qquad b_j\in B_j,\quad0\le d\le M_{j_0}. \] If at least $M_{j_0}$ of the digits equal $c_j$, switch exactly $d$ of them to $c_j+1$. All blocks use disjoint terms, so this is an exact subset-sum representation of $m$ using only the tail.

5) EXCEPTION COUNT AND NATURAL DENSITY. Write $H=M_{j_0}$ and $S_N=\sum_{j=j_0}^{N}q_j^{-1}$. The greedy map from $m$ to its digits and remainder is injective, since their sum recovers $m$. Therefore the number $E_N$ of missing integers in $[0,M_{N+1}]$ is at most \[ (H+1)\Big(\prod_{j=j_0}^{N}q_j\Big) \sum_{r=0}^{H-1}e_r(q_{j_0}^{-1},\ldots,q_N^{-1}) \le(H+1)\Big(\prod q_j\Big)\sum_{r=0}^{H-1}\frac{S_N^r}{r!}. \] The recurrence and convergence of $\sum M_j^{-1}$ give a constant $c>0$ with \[ M_{N+1}\ge cM_{j_0}\prod_{j=j_0}^{N}(q_j+1/2). \] Indeed the relative rounding losses are bounded by $1/((q_j+1/2)M_j)$, and the product of one minus these losses is positive. Since $\log(1+1/(2q_j))\ge1/(4q_j)$, \[ \frac{E_N}{M_{N+1}} \le C_H e^{-S_N/4}\sum_{r=0}^{H-1}\frac{S_N^r}{r!}. \] Now $S_N\gg N/\log(N+16)$ and $S_N=O(N)$, so the right side decays faster than every fixed negative power of $N$.

For an arbitrary large cutoff $X$, choose $N$ with $M_N\le X<M_{N+1}$. The number of missing integers up to $X$ is at most $E_N$, and \[ \frac{E_N}{X}\le\frac{M_{N+1}}{M_N}\frac{E_N}{M_{N+1}} \ll\log(N+16)\frac{E_N}{M_{N+1}}\longrightarrow0. \] Thus the tail's subset sums have natural density $1$. Every cofinite subsequence contains a whole block tail, proving the required assertion.

6) VERIFICATION AND FINAL. The integer remainder bound includes the unique gap of length $M_j+1$, and the final density argument controls cutoffs between the increasingly separated block endpoints. The argument is complete and elementary; it does not claim that every sufficiently large integer is represented. SOLVED. Completion is assessed for the precise density-one question.

Sources

COMPLETION ESTIMATE

Erdős problem #347

1) FORMAL RESTATEMENT. Let $A=\{a_1\le a_2\le\cdots\}$ be a nondecreasing sequence of positive integers. For any subsequence $A'$ (obtained by deleting terms), define \[ P(A'):=\left\{\sum_{n\in B} n:\ B\subseteq A'\ \text{finite}\right\}, \] the set of subset sums of distinct indices of $A'$. The (natural) density of a set $S\subseteq\mathbb{N}$ is \[ d(S)=\lim_{N\to\infty}\frac{|S\cap[1,N]|}{N} \] when it exists.

The question asks whether there exists a sequence $A$ such that

1. $\displaystyle \lim_{n\to\infty}\frac{a_{n+1}}{a_n}=2$, and
2. for every cofinite subsequence $A'$ (i.e. deleting finitely many terms), one has $d(P(A'))=1$.

2) QUICK LITERATURE/CONTEXT CHECK. No external results are assumed.

3) ATTACK PLAN.

• Prove necessary conditions for $d(P(A'))=1$ to hold for all cofinite subsequences (in particular, avoid modular obstructions in every tail).
• Do small computational experiments with natural "ratio $\to 2$" candidates to see how dense their subset sums are, and how sensitive density is to deleting one term.

4) WORK.

Lemma 347.1 (modular obstruction for density $1$ in all tails). Suppose there exists an integer $m\ge 2$ such that all but finitely many terms of $A$ are divisible by $m$. Then there exists a cofinite subsequence $A'$ with $d(P(A'))\le 1/m<1$. In particular, a necessary condition for the problem's requirement is:

For every $m\ge 2$, infinitely many terms of $A$ are not divisible by $m$.

Proof. Delete the finitely many terms not divisible by $m$ to obtain a cofinite subsequence $A'$ all of whose terms are multiples of $m$. Then every subset sum of $A'$ is a multiple of $m$, so $P(A')\subseteq m\mathbb{N}$. Therefore $|P(A')\cap[1,N]|\le \lfloor N/m\rfloor$ for all $N$, hence $d(P(A'))\le 1/m$. $\square$

Lemma 347.2 (a counting necessary condition at finite stage). Let $A_N:=\{a_1,\dots,a_N\}$ and let $S_N:=\sum_{i=1}^N a_i$. Then $P(A_N)\subseteq[0,S_N]$ and $|P(A_N)|\le 2^N$. Consequently, the density of $P(A_N)$ inside $[0,S_N]$ is at most \[ \frac{|P(A_N)|}{S_N+1}\le \frac{2^N}{S_N+1}. \] In particular, if for some cofinite tail one expects $d(P(A'))=1$, then for large $N$ in that tail one must have $S_N\lesssim 2^N$ at least along a subsequence.

Proof. Every subset sum of $A_N$ is between $0$ and $S_N$. There are $2^N$ choices of subsets of $\{1,\dots,N\}$, so $|P(A_N)|\le 2^N$. Dividing by $S_N+1$ gives the stated bound. $\square$

FAST REALITY CHECK (computational experiments with ratio $\to 2$ candidates). I tested the candidate sequence $a_n=2^n+1$ (which satisfies $a_{n+1}/a_n\to 2$). For $N=20$, the set of subset sums of the first $20$ terms has density about $0.458$ inside its natural range $[0,S_N]$. If one deletes a single term (e.g. the $10$th), the density drops to about $0.229$ at $N=20$. Thus this natural "$2^n$ with perturbation" candidate is far from satisfying $d(P(A'))=1$ robustly under deletions.

I also tested the mixed sequence $1,2,3,6,12,24,\dots$ (ratio tends to $2$ after the initial segment): its full subset sums fill every integer up to $S_N$ for finite $N$, but deleting $1$ already drops the finite-stage density to $2/3$, illustrating how sensitive density can be to removing a single small element.

5) VERIFICATION. Lemma 347.1 is a direct modular density bound. Lemma 347.2 is a direct counting argument. The computations are exact for the tested finite prefixes.

6) FINAL.

UNRESOLVED

(i) Strongest fully proved partial result obtained here. We proved necessary conditions for the requested robustness: in particular, every modulus $m\ge 2$ must divide only finitely many terms (Lemma 347.1), and finite-stage density forces $\sum_{i\le N}a_i$ not to be too large compared to $2^N$ (Lemma 347.2). Small experiments suggest natural $a_n\approx 2^n$ candidates do not have subset-sum density near $1$, and deletion of a single term can cut density substantially.

(ii) Exact first gap. We do not have either (a) an explicit construction of such a sequence $A$, or (b) a proof that no such sequence can exist. The first missing theoretical step is understanding how $a_{n+1}/a_n\to 2$ constrains the asymptotic coverage (density) of subset sums in every tail.

(iii) Top 3 next moves (concrete targets).

1. Attempt an impossibility proof by showing that for sequences with ratio $\to 2$, deleting one suitably chosen term forces a positive-density hole (e.g. via residue-class or carry constraints).
2. Attempt a constructive approach by building redundancy across scales (so that no single term is "essential"), while keeping consecutive ratios tending to $2$.
3. Strengthen Lemma 347.2 into an "if and only if" criterion relating tail completeness/density to inequalities of the form $a_{n+1}\le 1+\sum_{i\le n} a_i$ along the tail.

(iv) Minimal counterexample structure. If no such sequence exists, a minimal obstruction would likely arise from a cofinite subsequence $A'$ for which $P(A')$ omits an entire residue class modulo some $m$ (giving density $\le 1-1/m$), or from a persistent gap phenomenon where some interval lengths grow proportionally to $N$. Conversely, any successful construction must defeat all modular obstructions simultaneously (Lemma 347.1) and ensure that tail subset sums cover all but $o(N)$ integers up to $N$.