Erdős Problem #323

Erdős Problem 323: a checked attempt

GPT_6_Astra_Ultra

25 September 2026

Statement and scope

The general questions are unresolved here. We prove the one-summand case, a recursive separated-sums lower bound for every $m$, and a precise sufficient second-moment condition for the diagonal question. This replaces the earlier GPT-5.2 bound whose written constant calculation lost a factor of two and which did not use the number of available summands.

Elementary upper bound and the exact first case

A recursive construction of disjoint blocks

These intervals are pairwise disjoint. Indeed, for successive eligible $a$, \[ (a+1)^k-a^k\ge k a^{k-1}\ge k(N/2)^{k-1}>y. \] There are at least $N/2$ eligible integers. As $N\asymp_k x^{1/k}$ and $y\asymp_k x^{(k-1)/k}$, induction gives \[ f_{k,m}(x)\ge\frac N2 f_{k,m-1}(y) \gg_{k,m}x^{1/k+(k-1)\beta_{m-1}/k}=x^{\beta_m}. \] This proves $2$, with rounding absorbed only into fixed positive constants after the explicit disjointness inequalities. For example, the three-cube case gives exponent $19/27$, and each additional summand improves the bound. These are elementary estimates, weaker than known results in several cases, not claims of new records.

The collision estimate that would bridge the gap

Remaining gap

Completion rate estimate: 25%.

1) FORMAL RESTATEMENT

Fix integers $k\ge 2$ and $1\le m\le k$. Define \[ f_{k,m}(x):=\left|\{n\in\mathbb Z_{\ge 0}: n\le x\text{ and }n=a_1^k+\cdots+a_m^k\text{ for some }a_i\in\mathbb Z_{\ge 0}\}\right|. \] So $f_{k,m}(x)$ counts distinct integers $\le x$ representable as a sum of $m$ nonnegative $k$th powers.

Questions (as written):

$Q1$ Is it true that for every $\epsilon>0$, \[ f_{k,k}(x)\gg_\epsilon x^{1-\epsilon}?\]

$Q2$ Is it true that if $m<k$, then \[ f_{k,m}(x)\gg x^{m/k}\quad\text{for all sufficiently large }x?\]

Edge cases. $f_{k,m}(x)$ is nondecreasing in $x$, and $f_{k,m}(x)\ge 1$ for all $x\ge 0$ since $0=0^k+\cdots+0^k$.

2) QUICK LITERATURE/CONTEXT CHECK

I do not use any results not stated in the problem text. The statement notes:

* For $k=2$, Landau proved $f_{2,2}(x)\sim c x/\sqrt{\log x}$. * For $k>2$, it is not known whether $f_{k,k}(x)=o(x)$.

3) ATTACK PLAN

Provide elementary (weak) bounds and a clean construction giving a power-law lower bound.

$1$ Trivial bound: all $k$th powers $\le x$ are representable (using one nonzero term and the rest $0$).

$2$ For $m\ge 2$ and $k\ge 3$, construct many distinct sums $a^k+b^k\le x$ using a large-$a$/small-$b$ separation argument. This gives a provable lower bound $f_{k,m}(x)\ge c x^{3/(2k)}$ for large $x$.

Also: compute small values for sanity.

4) WORK

PHASE 1: FAST REALITY CHECK (brute force for small parameters)

Exact computed values (distinct representable integers) include:

For $k=3$: \[ \begin{array}{c|ccc} & x=100 & x=500 & x=1000\\\hline f_{3,2}(x) & 14 & 34 & 51\\ f_{3,3}(x) & 29 & 98 & 173 \end{array} \]

For $k=4$: \[ \begin{array}{c|ccc} & x=100 & x=500 & x=1000\\\hline f_{4,2}(x) & 9 & 14 & 20\\ f_{4,3}(x) & 15 & 30 & 49\\ f_{4,4}(x) & 22 & 54 & 97 \end{array} \]

Lemma 323.1 (trivial lower bound from single $k$th powers).

For any $k\ge 2$, any $m\ge 1$, and any $x\ge 0$, \[ f_{k,m}(x)\ge \lfloor x^{1/k}\rfloor+1. \]

Proof. For each integer $0\le t\le \lfloor x^{1/k}\rfloor$, the number $t^k\le x$ is representable as \[ t^k = t^k + 0^k+\cdots+0^k\quad\text{(with $m-1$ zeros)}. \] These $\lfloor x^{1/k}\rfloor+1$ values are distinct, so $f_{k,m}(x)$ is at least this large. $\square$

Lemma 323.2 (a provable power-law lower bound for $m\ge 2$, $k\ge 3$).

Fix $k\ge 3$. There exists $x_0=x_0(k)$ such that for all $x\ge x_0$ and all $m\ge 2$, \[ f_{k,m}(x)\ge \frac{1}{8}\,x^{3/(2k)}. \]

Proof. It suffices to prove the bound for $m=2$, since any sum of two $k$th powers is also a sum of $m$ $k$th powers by adding $(m-2)$ zeros. So fix $m=2$.

Let \[ M:=\left\lfloor x^{1/k}\right\rfloor,\qquad B:=\left\lfloor x^{1/(2k)}\right\rfloor. \] Consider integers $a$ in the range \[ \left\lceil \frac{M}{2}\right\rceil\le a\le M. \] For each such $a$ and each integer $b$ with $0\le b\le B$, the sum $a^k+b^k$ satisfies \[ a^k+b^k\le M^k+B^k\le x + x^{1/2}. \] To ensure $a^k+b^k\le x$ we restrict slightly: replace $M$ by \[ M':=\left\lfloor (x-B^k)^{1/k}\right\rfloor. \] For $x\ge 1$, $M'\ge M-1$, and for $x$ large we still have $M'\ge M/2$. So we take \[ \left\lceil \frac{M}{2}\right\rceil\le a\le M'. \] Then $a^k\le x-B^k$ and hence $a^k+b^k\le x$ for all $0\le b\le B$.

For a fixed $a$, the values $a^k+b^k$ are strictly increasing in $b$ (since $b\mapsto b^k$ is strictly increasing on $\mathbb Z_{\ge 0}$), so for each $a$ we obtain at least $B+1$ distinct representable integers.

We now show that for $x$ large, the intervals \[ I_a:=[a^k,\ a^k+B^k] \] for consecutive values of $a$ in the chosen range are disjoint. It is enough to show \[ (a+1)^k > a^k + B^k. \] By the binomial theorem, \[ (a+1)^k = a^k + k a^{k-1} + \binom{k}{2}a^{k-2}+\cdots+1 \ge a^k + k a^{k-1}. \] So it suffices to have $k a^{k-1} > B^k$. For $a\ge M/2$, \[ ka^{k-1} \ge k\left(\frac{M}{2}\right)^{k-1}. \] Since $M\ge x^{1/k}-1$, there exists $x_0(k)$ such that for all $x\ge x_0(k)$, \[ k\left(\frac{M}{2}\right)^{k-1} > x^{1/2} \ge B^k. \] (The exponent comparison is $(k-1)/k>1/2$ for $k\ge 3$.) Thus for $x\ge x_0(k)$, the intervals $I_a$ are pairwise disjoint over $a\in[\lceil M/2\rceil, M']\cap\mathbb Z$.

Therefore, for $x\ge x_0(k)$, all the values $a^k+b^k$ with $\lceil M/2\rceil\le a\le M'$ and $0\le b\le B$ are distinct. Hence \[ f_{k,2}(x)\ge (\#\{a\})\cdot (B+1). \] For $x$ large, $M'\ge M/2$ and $\#\{a\}\ge M/4$, while $B+1\ge B\ge \tfrac12 x^{1/(2k)}$. Also $M\ge \tfrac12 x^{1/k}$ for $x$ large. Combining these crude inequalities yields \[ f_{k,2}(x)\ge \frac{M}{4}\cdot \frac12 x^{1/(2k)}\ge \frac{1}{8}\,x^{1/k}\,x^{1/(2k)}=\frac{1}{8}\,x^{3/(2k)}. \] Finally $f_{k,m}(x)\ge f_{k,2}(x)$ for all $m\ge 2$, proving the lemma. $\square$

5) VERIFICATION

-- Lemma 323.1: uses only the representation $t^k=t^k+0+\cdots+0$.

-- Lemma 323.2: key disjointness condition is $(a+1)^k-a^k\ge k a^{k-1}$ (binomial theorem), and $k a^{k-1}>B^k$ holds for all large $x$ because $a\asymp x^{1/k}$ while $B^k\asymp x^{1/2}$.

-- Computations: performed by brute force over all tuples $(a_1,\dots,a_m)$ with $a_i^k\le x$.

6) FINAL

UNRESOLVED

(i) Strongest fully proved partial result obtained here.

* Trivial lower bound: $f_{k,m}(x)\ge \lfloor x^{1/k}\rfloor+1$ for all $k\ge 2$, $m\ge 1$ (Lemma 323.1). * For $k\ge 3$ and $m\ge 2$, a rigorous power-law lower bound $f_{k,m}(x)\ge \tfrac18 x^{3/(2k)}$ for all sufficiently large $x$ (Lemma 323.2).

(ii) Exact first gap.

Prove the conjectured exponent $m/k$ (or $1-\epsilon$ when $m=k$): my construction only yields exponent $3/(2k)$ (independent of $m$ once $m\ge 2$), far weaker than $m/k$ when $m$ is close to $k$.

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

1. Replace the "$b$-varies" argument in Lemma 323.2 by a method producing $\gg B^{m}$ distinct sums of $m$ $k$th powers (not just $\gg B$), ideally by controlling collisions among $b_1^k+\cdots+b_m^k$. 2. Develop an upper bound on collision multiplicity for $b_1^k+\cdots+b_m^k$ in a box, which would convert tuple-counting into distinct-sum counting. 3. Compute $f_{k,m}(x)$ for larger $x$ for small $(k,m)$ (e.g. $(3,3)$, $(4,4)$) to see whether the conjectured exponents fit data.

(iv) What a minimal counterexample would likely look like.

If $f_{k,m}(x)\not\gg x^{m/k}$ for some $m<k$, then there would be massive collisions among sums of $m$ $k$th powers, forcing the set \[\{a_1^k+\cdots+a_m^k: 0\le a_i\le x^{1/k}\}\] to have size $o(x^{m/k})$. Any structural explanation would need a mechanism producing many distinct $m$-tuples with the same sum (beyond the obvious permutation symmetries), at a scale polynomial in $x$.