Erdős Problem #345

Erdős Problem #345: completeness thresholds of powers

1. Statement and scope

For $A_k=\{j^k:j\ge1\}$ let $P(A_k)$ consist of finite sums of distinct members, including the empty sum, and use the inclusive convention \[ T_k=\min\{m\ge1:[m,\infty)\cap\mathbb Z\subseteq P(A_k)\}. \] The question is whether $T_k>T_{k+1}$ for infinitely many $k$. This attempt proves exact small thresholds by finite certificates with an infinite continuation argument, and an explicit obstruction when $k$ is a power of two. The comparison for infinitely many $k$ remains unresolved.

2. An interval certificate that really proves completeness

Suppose the subset sums of $1^k,\ldots,m^k$ contain the integer interval $[L,U]$, of cardinality $W=U-L+1$, where \[ m\ge2k,\qquad W\ge(m+1)^k. \] Adding the unused term $j^k$, initially $j=m+1$, supplies both the old interval and its translate by $j^k$. They overlap or are adjacent when $W\ge j^k$, yielding $[L,U+j^k]$ and new width $W+j^k\ge2j^k$. For $j\ge2k$, \[ (j+1)^k/j^k=(1+1/j)^k\le e^{1/2}<2. \] Thus the width condition propagates indefinitely. The right endpoints tend to infinity, so every integer at least $L$ is representable. Merely testing a large finite range would not supply this conclusion.

Here are two exact certificates: \[ \begin{array}{c|r|r|r|r|r} k&m&\sum_{j\le m}j^k&L&U&W\\ \hline 2&12&650&129&521&393\\ 3&24&90000&12759&77241&64483 \end{array} \] They can be checked without any heuristic search: start with $R_0=\{0\}$ and repeat \[ R_j=R_{j-1}\cup\{x+j^k:x\in R_{j-1}\}\quad(1\le j\le m). \] Exact integer bitset evaluation gives $[L,U]\subseteq R_m$ and $L-1\notin R_m$ in both rows. Equivalently, start with the integer $b=1$ and replace $b$ by the bitwise union of $b$ and $b$ shifted left by $j^k$; bit $s$ then records membership of $s$. This specifies the entire finite certificate algorithm. Independent set enumeration gives the same outputs. Since $13^2>128$ and $25^3>12758$, later terms cannot repair the two missing integers. The interval lemma therefore proves \[ \boxed{T_2=129,\qquad T_3=12759.} \] The commonly quoted values $128$ and $12758$ are the largest missing integers, so differ by one from the inclusive threshold defined above. This convention issue does not change comparisons between exponents.

3. A large modular obstruction for powers of two

Let $k=2^t$ with $t\ge2$, and put $q=2^{t+2}=4k$. Every odd integer $a$ satisfies $a^k\equiv1\pmod q$. Indeed, odd squares are $1$ modulo $8$, and squaring a number congruent to $1$ modulo $2^u$ raises this divisibility to $2^{u+1}$. Every even $a$ satisfies $a^k\equiv0\pmod q$, since $k\ge t+2$.

Set \[ S=\sum_{j=1}^{q-1}(2j-1)^k,\qquad N=S-q. \] Then $N\equiv q-1\pmod q$. Any representation of $N$ by distinct $k$th powers must use a number of odd bases congruent to $q-1$ modulo $q$, hence at least $q-1$ odd bases. Their least possible total is precisely $S$, exceeding $N$. Consequently \[ N\notin P(A_k),\qquad T_{2^t}\ge\sum_{j=1}^{2^{t+2}-1}(2j-1)^{2^t}-2^{t+2}+1. \] This proves the obstruction directly; it is not a probabilistic expectation about residues.

4. Assessment and provenance

The modular bound explains why powers of two are plausible exponents at which the threshold is unusually large. It gives no sufficiently small upper bound for $T_{2^t+1}$, which is the missing comparison. Neither infinitely many descents nor eventual monotonicity is proved. The estimate below measures partial proof coverage, not a probability that an answer is correct.

The statement and the suggested power-of-two obstruction are from Erdős--Graham, as recorded at https://www.erdosproblems.com/345 (checked 2026-09-25). The earlier GPT Pro 5.2 attempt noticed the threshold convention; the explicit interval certificates and continuation argument here verify the correction. No novelty or formal Lean verification is claimed.

COMPLETION ESTIMATE

COMPLETION: 45%

Erdős problem #345

1) FORMAL RESTATEMENT. For $A\subseteq\mathbb{N}$ define \[ P(A):=\left\{\sum_{n\in B} n:\ B\subseteq A\ \text{finite}\right\} \] (the set of all finite sums of distinct elements of $A$). A sequence $A$ is complete if every sufficiently large integer belongs to $P(A)$. Define the threshold of completeness \[ T(A):=\min\{m\in\mathbb{N}:\ \forall n\ge m,\ n\in P(A)\}. \] (As written, this definition is inclusive: it requires $m\in P(A)$.)

For $k\ge 1$ let $A_k:=\{n^k: n\in\mathbb{N}\}$. The problem asks whether there are infinitely many $k$ with \[ T(A_k) > T(A_{k+1}). \] The statement lists claimed values for $T(A_k)$ for $k=1,2,3,4,5$.

2) QUICK LITERATURE/CONTEXT CHECK. We do not assume the listed numerical values are correct beyond what we can verify directly by computation for small $k$.

3) ATTACK PLAN.

• Check the definition of $T(A)$ against the quoted values for $k=2,3$ via exact subset-sum computation.
• Record any definitional ambiguity (inclusive vs exclusive threshold).
• Provide explicit nonrepresentability certificates for the boundary values.

4) WORK.

Proposition 345.1 (squares: $128\notin P(A_2)$, but $129\in P(A_2)$). Let $A_2=\{1^2,2^2,3^2,\dots\}$. Then $128\notin P(A_2)$, but \[ 129 = 8^2+6^2+4^2+3^2+2^2\in P(A_2). \]

Proof. To test membership of $128$ in $P(A_2)$, it suffices to consider the finite set of squares $\le 128$: \[ \{1,4,9,16,25,36,49,64,81,100,121\}. \] There are only $2^{11}=2048$ subsets, so membership is a finite check. A subset-sum dynamic program over these squares (equivalently, exhaustive search) finds that no subset sums to $128$. Therefore $128\notin P(A_2)$.

For $129$, the displayed representation uses distinct squares, so $129\in P(A_2)$. $\square$

Proposition 345.2 (cubes: $12758\notin P(A_3)$, but $12759\in P(A_3)$). Let $A_3=\{1^3,2^3,3^3,\dots\}$. Then $12758\notin P(A_3)$, while \[ 12759 = 17^3+13^3+12^3+11^3+10^3+9^3+8^3+6^3+5^3+2^3\in P(A_3). \]

Proof. All cubes $\le 12758$ are $1^3,2^3,\dots,23^3$ (since $23^3=12167$ and $24^3=13824>12758$), so there are $23$ candidate summands. Membership in $P(A_3)$ for a fixed target is again a finite subset-sum problem. A subset-sum dynamic program confirms that no subset of $\{1^3,2^3,\dots,23^3\}$ sums to $12758$, hence $12758\notin P(A_3)$.

For $12759$, the displayed representation uses distinct cubes and sums exactly to $12759$, so $12759\in P(A_3)$. $\square$

FAST REALITY CHECK (inclusive vs exclusive threshold). By exhaustive subset-sum computation:

• For squares, every integer $n\ge 129$ is representable as a sum of distinct squares for all $n\le 500$, and $128$ is the largest nonrepresentable $\le 500$.
• For cubes, $12758$ is nonrepresentable, $12759$ is representable, and for all $n$ with $12759\le n\le 20000$ the computation found $n\in P(A_3)$.

Thus, under the inclusive definition of $T(A)$ (requiring $m\in P(A)$), the thresholds suggested by these checks are \[ T(A_2)\ge 129,\qquad T(A_3)\ge 12759. \] If instead one defined $T'(A)=\min\{m: \forall n>m,\ n\in P(A)\}$ (strictly greater), then the largest missing values $128$ and $12758$ would match $T'(A_2)=128$ and $T'(A_3)=12758$. The problem statement uses the inclusive form $n\ge m$.

5) VERIFICATION. Propositions 345.1--345.2 are fully certified by finite computation on the relevant finite sets of squares/cubes, together with explicit representations for the successor integers.

6) FINAL.

UNRESOLVED

(i) Strongest fully proved partial result obtained here. We provided explicit counterexamples to the boundary values under the inclusive definition of $T(A)$: $128\notin P(A_2)$ and $12758\notin P(A_3)$, while $129\in P(A_2)$ and $12759\in P(A_3)$ (Propositions 345.1--345.2). We also identified a likely inclusive/exclusive threshold ambiguity.

(ii) Exact first gap. We did not prove completeness of $A_k=\{n^k\}$ for general $k$, nor did we establish or refute the existence of infinitely many $k$ with $T(A_k)>T(A_{k+1})$. The first gap is obtaining any general mechanism to compare $T(A_k)$ and $T(A_{k+1})$.

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

1. Clarify (and fix) the intended convention for $T(A)$ (inclusive vs exclusive), then verify the quoted $T(A_k)$ values for $k=4,5$ with independent computation/certificates.
2. Prove a general sufficient condition for completeness for power sequences (e.g. using additive-combinatorial covering arguments) and extract an explicit upper bound on $T(A_k)$.
3. Develop lower-bound constructions: produce explicit integers not representable as sums of distinct $k$th powers, to force $T(A_k)$ large and allow comparison with $T(A_{k+1})$.

(iv) Minimal counterexample structure. A counterexample to "infinitely many $k$ with $T(A_k)>T(A_{k+1})$" would require that from some point on, the thresholds are nonincreasing: $T(A_k)\le T(A_{k+1})$ for all large $k$. This would suggest a monotonicity phenomenon in representability by distinct powers that is not explained by current small-$k$ data.