Erdoes #829 - working report - Erdős Problem a Day

Erdős problem #829 — wave w017

Date: 2026-07-28 UTC

Claim labels

[a] elementary-rigorous: proved here from elementary algebra and

arithmetic.

[b] rigorous-modulo-named-theorem: the deduction is rigorous modulo the

theorem named at the point of use.

[c] plausible/structural-unverified: a search conclusion, heuristic, or

proposed target, not asserted as a theorem.

[d] computational-only/source-verified: either an exact finite

computation or a direct observation from a fetched source.

0. Mandatory live-page check

[d: live-page observation] I fetched <https://www.erdosproblems.com/829>, its LaTeX view, its dynamic bibliography, and its discussion thread through the Bright Data cloud browser on 2026-07-28. The page rendered as OPEN.

The current statement, copied verbatim from the page's LaTeX view, is:

Let $A\subset\mathbb{N}$ be the set of cubes. Is it true that\[1_A\ast 1_A(n) \ll (\log n)^{O(1)}?\]

The known-results text in that view is:

Mordell proved that\[\limsup_{n\to \infty} 1_A\ast 1_A(n)=\infty\]and Mahler \cite{Ma35b} proved\[1_A\ast 1_A(n) \gg (\log n)^{1/4}\]for infinitely many $n$. Stewart \cite{St08} improved this to\[1_A\ast 1_A(n) \gg (\log n)^{11/13}.\]

The displayed references are:

[Ma35b] Kurt Mahler, On the Lattice Points on Curves of Genus 1,

Proc. London Math. Soc. (2) 39 (1935), 431–466.

[St08] Cameron L. Stewart, Cubic Thue equations with many solutions,

Int. Math. Res. Not. IMRN (2008), Art. ID rnn040, 11 pages.

Opening the dynamic [Er83] entry gave Paul Erdős and Underwood Dudley, Some remarks and problems in number theory related to the work of Euler, Math. Mag. 56 (1983), 292–298, MR 720650.

[d: complete status/activity audit]

| live-page field | value | |---|---:| | status | OPEN | | page last edited | 14 October 2025 | | comments | 1 | | claimed proofs | 0 | | interested in collaborating | None | | currently working on this problem | None | | formalised statement? | Yes |

The one comment, by msellke at 20:02 on 13 October 2025, says:

The lower bound was improved to $(\log n)^{11/13}$ by Stewart ("Cubic Thue Equations with Many Solutions"; IMRN 2008), relying on an elliptic curve construction of Elkies and Rogers ("Elliptic Curves $x^3+y^3=k$ of High Rank"; International Algorithmic Number Theory Symposium 2004).
(The reference was located by GPT-5.)
(The site has been updated to address this comment.)

The page labels comments as unverified user content. There is no proof claim, current worker, or interested-collaborator marker, so the mandatory stop rule did not apply.

1. Conventions

For $n\ge1$, define

\begin{aligned} r_+(n)&=\#\{(x,y)\in\mathbb Z_{>0}^2:x^3+y^3=n\},\\ \rho_+(n)&=\#\{(x,y)\in\mathbb Z_{>0}^2:x\le y,\ x^3+y^3=n\}. \end{aligned}

Thus $r_+$ is ordered and $\rho_+$ is unordered.

[a] If the page's $\mathbb N$ includes zero, then its convolution is

R(n):=(1_A*1_A)(n) =r_+(n)+2\,\mathbf 1_{\{n\text{ is a positive cube}\}}. \tag{1}

If $\mathbb N=\{1,2,\ldots\}$, then $R=r_+$. Consequently the convention changes the function by at most two and has no effect on the asymptotic question. All structural bounds below include the possible extra two.

2. Primary-source and literature audit

[d] The original paper exists at

Erdős's archive and at DOI 10.1080/0025570X.1983.11977060. Page 296 defines the number of solutions to $n=x^3+y^3$, records the Mordell and Mahler lower results, says that no nontrivial upper bound was then known, and proposes a power of $\log n$.

[d] Mahler's 1935 paper exists at

DOI 10.1112/plms/s2-39.1.431; a scan is available from the Kurt Mahler archive. Its Theorem 6 is specifically about representations as sums of two positive cubes. The live page is used as ground truth for the displayed $1/4$ exponent.

[d] I downloaded and read Stewart's primary paper from the

author's Waterloo page; the publisher record is DOI 10.1093/imrn/rnn040. Stewart proves exponent $1/2$ for a general nonsingular integral binary cubic form. For $x^3+y^3$, he explicitly says that Silverman's rank-3 construction gives $3/5$, Stewart's earlier rank-6 twist gives $3/4$, and the rank-11 twist of Elkies–Rogers gives $11/13$.

[d] The cited Elkies–Rogers paper exists as

arXiv:math/0403116. It constructs curves $x^3+y^3=k$ of ranks $8,9,10,11$, and supplies the rank-11 value used by Stewart.

[d] A relevant item not mentioned on the live page is Saunak

Bhattacharjee, An effective estimate for the sum of two cubes problem, arXiv:2403.17955v3 (2024). It makes the $11/13$ construction explicit, claiming \[ N_f(m)>4.2\cdot10^{-6}(\log|m|)^{11/13} \] for infinitely many $m$, where that paper defines $N_f(m)$ using all $(x,y)\in\mathbb Z^2$. This is the same exponent, not an improvement. Its signed-integer convention is broader than the positive-cube convolution, so the explicit constant should not be transferred to the live statement without an additional sign argument.

[d] James Maynard's 2026 survey

Sums of three positive cubes invokes the qualitative fact that the number of representations of one integer as two cubes is $n^{o(1)}$. Section 3 below gives an independent elementary proof of that qualitative upper bound.

[c: search miss, not a nonexistence theorem] Exact-title, exact-

statement, DOI, forward-citation, arXiv, and cubic-twist searches found no primary source proving or disproving the requested polylogarithmic upper bound, and no post-Stewart improvement to the $11/13$ exponent. A missed paper remains possible.

3. Exact divisor–discriminant reduction

Lemma 1 [a]. For a positive divisor $s\mid n$, put

\Delta_n(s)=\frac{4n/s-s^2}{3}. \tag{2}

There is a positive unordered representation

n=x^3+y^3,\qquad 1\le x\le y,

with $x+y=s$ if and only if $\Delta_n(s)=t^2$ for an integer $0\le t<s$. In that event it is unique and

(x,y)=\left(\frac{s-t}{2},\frac{s+t}{2}\right). \tag{3}

Proof [a]. If $s=x+y$, then

n=(x+y)(x^2-xy+y^2) =s\left(\frac{s^2+3(y-x)^2}{4}\right),

which gives (2) with $t=y-x$. Conversely, (2) implies $t^2\equiv s^2\pmod4$, so (3) is integral; $t<s$ makes both entries positive, and substitution recovers $n$. The displayed formula makes uniqueness for fixed $s$ immediate. ∎

Corollary 1 [a] (short divisor interval).

\rho_+(n)= \#\left\{s\mid n: n^{1/3}<s\le(4n)^{1/3},\ \Delta_n(s)\text{ is a square}\right\}. \tag{4}

Proof [a]. Writing $q=x^2-xy+y^2=s^2-3xy$, positivity and $xy\le s^2/4$ give

\frac{s^2}{4}\le q<s^2.

Since $n=sq$, this is equivalent to the interval in (4); Lemma 1 supplies the exact square test. ∎

Corollary 2 [a].

\rho_+(n)\le\tau(n),\qquad R(n)\le2\tau(n)+2. \tag{5}

[b: modulo Wigert's maximal-order theorem] Therefore

R(n)\le \exp\!\left((\log2+o(1))\frac{\log n}{\log\log n}\right). \tag{6}

This is $n^{o(1)}$, but it is much larger than every fixed power of $\log n$. Formula (4), rather than the raw divisor bound, exhibits the unexploited condition: the discriminant must be a square in a very short multiplicative divisor interval.

4. An Eisenstein-integer reduction

This section removes all primes $p\equiv2\pmod3$ from the genuine source of large multiplicity and proves the desired bound whenever the number of primes $p\equiv1\pmod3$ dividing $n$ is bounded.

Take one positive representation and write

g=(x,y),\qquad x=ga,\quad y=gb,\quad (a,b)=1,

and

s=a+b,\qquad q=a^2-ab+b^2. \tag{7}

Then

n=g^3sq. \tag{8}

Lemma 2 [a] (primitive prime support).

$\gcd(s,q)\in\{1,3\}$.
No prime $p\equiv2\pmod3$ divides $q$.
If $3\mid q$, then $v_3(q)=1$.

Proof [a].

Since $q=s^2-3ab$, a common divisor of $s,q$ divides $3ab$. But $(s,a)=(s,b)=1$, proving the first assertion.

If $p\equiv2\pmod3$ divided $q$, neither $a$ nor $b$ could vanish modulo $p$. The ratio $z=a/b$ would satisfy

z^2-z+1=0,\qquad z^3=-1,\qquad z\ne-1.

For odd $p$, this gives an element of order $6$ in $\mathbb F_p^\times$, forcing $p\equiv1\pmod3$; $p=2$ is checked directly. This proves the second assertion.

Finally, $3\mid q$ implies $3\mid s$. Write $a=-b+3k$. Then

\[ q=3(b^2-3bk+3k^2), \]

and the parenthesis is nonzero modulo $3$, proving $v_3(q)=1$. ∎

Let $e_p=v_p(n)$, and for every prime $p\equiv1\pmod3$ define

E_p(n)=\{0\}\cup \{r:1\le r\le e_p,\ r\equiv e_p\pmod3\}. \tag{9}

Let

\mathcal Q(n)= \left\{ 3^\epsilon\prod_{\substack{p\mid n\\p\equiv1\ (3)}}p^{r_p}: 0\le\epsilon\le\min(1,v_3(n)),\ r_p\in E_p(n) \right\}. \tag{10}

Theorem 1 [a] (exact finite reduction). If

\mathcal P(q)= \{(a,b)\in\mathbb Z_{>0}^2:(a,b)=1,\ a^2-ab+b^2=q\},

then

r_+(n)= \sum_{q\in\mathcal Q(n)} \#\left\{(a,b)\in\mathcal P(q): \frac{n}{(a+b)q}\text{ is a positive integer cube}\right\}. \tag{11}

Proof [a]. A representation gives (7)–(8). Lemma 2 restricts the prime support of $q$. If a split prime $p$ occurs in $q$ to exponent $r>0$, then $p\nmid s$, so

\[ e_p=3v_p(g)+r, \]

which is exactly (9). Thus it contributes one term on the right of (11). Conversely, a term counted on the right has $n/((a+b)q)=g^3$ and yields the ordered representation $(x,y)=(ga,gb)$. For fixed $n,a,b$, the positive $g$ is unique, so there is no overcount. ∎

For $e\ge1$, put

S(e)=1+\!\!\sum_{\substack{1\le r\le e\\r\equiv e\ (3)}}(r+1). \tag{12}

Theorem 2 [b: modulo unique factorisation and rational-prime splitting in $\mathbb Z[\omega]$].

r_+(n)\le 6(1+\mathbf1_{3\mid n}) \prod_{\substack{p^{e_p}\parallel n\\p\equiv1\ (3)}}S(e_p) \le 12\prod_{\substack{p^{e_p}\parallel n\\p\equiv1\ (3)}}S(e_p). \tag{13}

Proof [b]. In the norm-Euclidean ring $\mathbb Z[\omega]$, where $\omega^2+\omega+1=0$,

N(a+b\omega)=a^2-ab+b^2.

For

q=3^\epsilon\prod p^{r_p}

of the form (10), unique factorisation gives exactly

6\prod_p(r_p+1) \tag{14}

integer pairs $(a,b)\in\mathbb Z^2$ of norm $q$: there are six units, and for each split $p=\pi\bar\pi$, the exponent $r_p$ can be divided between $\pi$ and $\bar\pi$ in $r_p+1$ ways. The ramified prime $3$ adds no such factor. This overcounts the positive coprime pairs in (11). Summing (14) over (9) independently prime by prime gives (13). ∎

Corollary 3 [b] (the conjecture for bounded split-prime support). Let

K=\#\{p:p\mid n,\ p\equiv1\pmod3\},\qquad L=\lfloor\log_2n\rfloor.

Then

R(n)\le 2+12\left(\frac{(L+1)(L+2)}2\right)^K. \tag{15}

In particular, for every fixed $K$,

R(n)\ll_K(\log n)^{2K} \tag{16}

uniformly over integers with at most $K$ distinct prime divisors $p\equiv1\pmod3$.

Proof [b]. Directly from (12),

S(e)\le1+\sum_{r=1}^e(r+1)=\frac{(e+1)(e+2)}2.

Every $e_p\le L$; now apply (1) and (13). ∎

A complete sharp classification when $K=0$

Theorem 3 [a]. Suppose $n\ge1$ has no prime divisor congruent to $1\pmod3$. Its positive representations are exactly:

$n=2g^3$: the single ordered representation $(g,g)$;
$n=9g^3$: the two ordered representations $(g,2g)$ and $(2g,g)$;
otherwise: none.

Consequently, under the convention $0\in\mathbb N$,

R(n)= \begin{cases} 2,&n\text{ is a cube},\\ 2,&n=9g^3\text{ for some }g\ge1,\\ 1,&n=2g^3\text{ for some }g\ge1,\\ 0,&\text{otherwise}. \end{cases} \tag{17}

The displayed cases are mutually exclusive.

Proof [a]. Lemma 2 forces the primitive norm $q$ in (7) to be either $1$ or $3$. Since

\[ q=(a-b)^2+ab, \]

positive coprime solutions to $q=1$ consist only of $(a,b)=(1,1)$; positive solutions to $q=3$ are only $(1,2),(2,1)$. Equation (8) gives the two asserted families. Conversely, the displayed pairs verify both families directly. Prime valuations modulo $3$ show that the two families and the cubes cannot overlap. Adding the two zero-coordinate representations of a positive cube gives (17). ∎

5. Exact computation through $10^{12}$

[d: computation definition] The computation below concerns positive unordered pairs $1\le x\le y$ and writes

H_j(B)=\#\{n\le B:\rho_+(n)=j\}.

The last column is the maximum of the live convolution $R(n)$, including zero cubes if that is the convention.

[d: exact table]

| $B$ | pairs $x\le y$ | positive represented $n$ | $H_1(B)$ | $H_2(B)$ | $H_3(B)$ | $\max_{n\le B}R(n)$ | |---:|---:|---:|---:|---:|---:|---:| | $10$ | 2 | 2 | 2 | 0 | 0 | 2 | | $10^2$ | 9 | 9 | 9 | 0 | 0 | 2 | | $10^3$ | 41 | 41 | 41 | 0 | 0 | 2 | | $10^4$ | 204 | 202 | 200 | 2 | 0 | 4 | | $10^5$ | 948 | 938 | 928 | 10 | 0 | 4 | | $10^6$ | 4,397 | 4,354 | 4,311 | 43 | 0 | 4 | | $10^7$ | 20,480 | 20,330 | 20,180 | 150 | 0 | 4 | | $10^8$ | 95,111 | 94,625 | 94,140 | 484 | 1 | 6 | | $10^9$ | 441,521 | 439,959 | 438,405 | 1,546 | 8 | 6 | | $10^{10}$ | 2,049,798 | 2,045,048 | 2,040,324 | 4,698 | 26 | 6 | | $10^{11}$ | 9,514,790 | 9,500,746 | 9,486,780 | 13,888 | 78 | 6 | | $10^{12}$ | 44,164,746 | 44,124,084 | 44,083,658 | 40,190 | 236 | 6 |

Thus:

[d] No $n\le10^{12}$ has four positive unordered representations.
[d] The first $n$ with two is

\[ 1729=1^3+12^3=9^3+10^3. \]

[d] The first $n$ with three is

\[ 87539319 =167^3+436^3 =228^3+423^3 =255^3+414^3. \]

[d] No positive represented value through $10^{12}$ is itself a

cube; hence including zero does not enlarge the tabulated maximum.

Completeness of the computation

[a] For a cutoff $B$, every unordered positive pair occurs in exactly one monotone row

(x,x),(x,x+1),\ldots, \left(x,\left\lfloor(B-x^3)^{1/3}\right\rfloor\right), \quad 1\le x\le\lfloor(B/2)^{1/3}\rfloor. \tag{18}

A heap containing the next item of every row is therefore a complete sorted merge of all pairs, with no omission or duplication. Grouping equal adjacent sums gives every $\rho_+(n)$ exactly. It uses $O(B^{1/3})$ memory rather than storing $O(B^{2/3})$ sums.

[d] The final dependency-free Python verifier performed this merge through $10^{12}$ in 94.0 seconds and about 23 MB on this VM. It hashes every collision together with all of its representing pairs; the SHA-256 is

da42e736fa20a48a3e081642b42bef1a00baea176230290092fddbb9026a62d5

[d: independent implementation] The auxiliary C++ checker uses a different algorithm: it materialises all 44,164,746 sums as 64-bit integers, sorts them, and counts runs. It independently returned

pairs=44164746
represented=44124084
histogram 1:44083658 2:40190 3:236
first 1:2 2:1729 3:87539319

in 4.16 seconds with 348,520 KB peak RSS.

6. Verification and reproducibility

The standalone verifier is runs/erdos829_wavew017_reverify.py; it uses only the Python standard library. It independently:

checks integer cube roots and the divisor–discriminant bijection for every

$n\le20{,}000$;

brute-forces the Eisenstein norm representation formula for every

$q\le500$;

verifies the primitive prime restrictions, candidate exponents, explicit

upper bound, and the complete $K=0$ classification on the finite audit range;

compares the heap merge with a separate dictionary enumeration through

$10^7$;

rechecks the displayed 1729 and 87539319 certificates from scratch;
reruns the full $10^{12}$ merge and refuses to pass unless every frozen

table entry and the collision hash agree.

Reproduction command:

python3 runs/erdos829_wavew017_reverify.py

The independent high-memory checker is runs/erdos829_wavew017_crosscheck.cpp:

g++ -O3 -std=c++17 -Wall -Wextra -Wpedantic \
  runs/erdos829_wavew017_crosscheck.cpp -o /tmp/erdos829_crosscheck
/tmp/erdos829_crosscheck 1000000000000

7. What remains and the precise wall

[a] Theorems 1–3 isolate the difficult inputs exactly. Primes $p\equiv2\pmod3$ and arbitrarily large powers of such primes do not cause the obstruction: for bounded

K=\omega_{\{1\bmod3\}}(n)

the desired conclusion already follows from (15).

[a] The elementary candidate bound does become too large when $K$ grows. For squarefree $n$ supported on $K$ primes $p\equiv1\pmod3$, (12) has $S(1)=3$, so (13) gives $O(3^K)$. For a product of the first $K$ such primes, $K$ is of order $\log n/\log\log n$; this upper bound is super-polylogarithmic. Unique factorisation enumerates candidates but does not show that many candidates pass the final perfect-cube compatibility test in (11).

[c: exact missing lemma] Either of the following uniform statements would finish the problem:

\#\left\{s\mid n: n^{1/3}<s\le(4n)^{1/3},\ \frac{4n/s-s^2}{3}\text{ is a square}\right\} \ll(\log n)^C \tag{19}

for one absolute $C$, or equivalently a polylogarithmic bound on the number of triples in (11) that survive

\frac{n}{(a+b)(a^2-ab+b^2)}=\text{a perfect cube}. \tag{20}

The exact missing ingredient is thus a uniform square-discriminant / cube-compatibility sparsity lemma over divisors with unbounded split-prime support. The checked Thue and elliptic-curve lower-bound machinery supplies many examples; it does not supply this uniform upper-bound sieve.

[d: computation boundary] The finite scan cannot establish (19). At the observed $B^{2/3}$ scaling, taking the dependency-free heap scan to $10^{15}$ would process about $4.4$ billion pairs and cost roughly 2.6 single-core hours at the measured rate. A flat 64-bit sort would require about 35 GB merely for the sum array. I did not run either computation, and no finite cutoff would supply the missing uniformity step.

PARTIAL: Proved an exact divisor and Eisenstein-norm reduction, proved the conjectured polylog bound uniformly when the number of prime divisors p=1 (mod 3) is bounded (with a complete sharp classification when there are none), and independently certified that every n<=10^12 has at most three positive unordered two-cube representations; the unbounded split-prime compatibility lemma remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger