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

Erdős problem #1206 — wave w038

Date checked: 2026-07-29 UTC.

Claim labels used below:

(a) elementary-rigorous: a complete argument is given here, including finite exact certificates when applicable.
(b) rigorous-modulo-named-theorem: the claim is exactly attributed to a verified primary source.
(c) plausible/structural-unverified: a direction or diagnosis, not a theorem.
(d) computational-only: an exhaustive or experimental finite computation, never extrapolated.

0. Mandatory live-page check

I fetched the rendered live page through the Bright Data browser, then separately fetched its LaTeX-source view and public discussion thread. The relevant URLs were:

<https://www.erdosproblems.com/1206>
<https://www.erdosproblems.com/latex/1206>
<https://www.erdosproblems.com/forum/discuss/1206>

Verbatim current statement

Does $\{1,2^3,\ldots,N^3\}$ contain a Sidon set of size $\gg N$?
Is there an infinite set $A\subset \mathbb{N}$ of positive density such that $\{a^3 : a\in A\}$ is a Sidon set?

(d) The rendered page said OPEN, “0 claimed proofs,” “Currently working on this problem: None,” and “Interested in collaborating: None.” It listed two comments and said that the page was last edited on 8 April 2026. Thus none of the mandatory stop conditions applied.

Results and comments shown on the live page

(b) The main page attributes the following result to Gabdullin and Konyagin: for some absolute $c>0$,

\{n^3:N-cN^{1/2}\le n\le N\}

is Sidon. Their primary paper is M. R. Gabdullin and S. V. Konyagin, Trigonometric polynomials with frequencies in the set of cubes, Math. Notes 115 (2024), 336–340; the verified preprint is arXiv:2311.14937v2. Its abstract gives the explicit forward interval $\{n^3:N\le n\le N+(N/2)^{1/2}\}$.

(b) The page attributes to Garaev, Garayev, and Konyagin a Sidon interval of length $N^{4/7-o(1)}$ for infinitely many $N$, and an all-$N$ exponent $3/5$ for fourth powers. The verified primary source is M. Z. Garaev, F. M. Garayev, and S. V. Konyagin, On Sidon sets with squares, cubes and quartics in short intervals, arXiv:2602.08807v2, revised 6 May 2026. It states the cubic result as: for every $\varepsilon>0$, infinitely many $N$ admit the interval through $N+N^{4/7-\varepsilon}$.

(d) The page also points to problem #324 for fifth powers, defines Erdős's more general $g_k(A)$, asks whether

g_k(A)\ge g_k(\{1,\ldots,N\})\quad\text{when }|A|=N,

and points to #530 and #773. These are context, not assumptions in the computation below.

(b) The newer of the two comments points to Michael Tait's 2016 UCSD dissertation, Connections between graph theory, additive combinatorics, and finite incidence geometry. I checked the primary thesis PDF, not just the comment. Theorem 5.1.3 on thesis page 61 (PDF page 72) states that there is a Sidon set of cubes in $[n^3]$ of size $\gg n^{8/9}$. Thus the verified published-on-the-page lower bound relevant to the first question is at least

g_3(N)\gg N^{8/9}.

(a) The older comment's concrete cubic example is correct:

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

Direct enumeration gives $g_3(\{1,9,10,12\})=3$, whereas $\{1^3,2^3,3^3,4^3\}$ itself is Sidon, so $g_3(\{1,2,3,4\})=4$. The standalone checker independently checks both assertions. The comment's discussion of powers $k\ge5$ is explicitly conditional on the Lander–Parkin–Selfridge conjecture and is not used here.

1. Additional primary-source search

(b) Erdős's original source exists as P. Erdős, A survey of problems in combinatorial number theory, Ann. Discrete Math. 6 (1980), 89–115, DOI 10.1016/S0167-5060(08)70697-670697-6). A scan is hosted in the Erdős archive at <https://combinatorica.hu/~p_erdos/1980-03.pdf>. Page 109 is the source cited by the live tracker.

(b) Kiss and Sándor's Generalized Sidon sets of perfect powers, Ramanujan J. 59 (2022), 351–363, DOI 10.1007/s11139-022-00622-z, proves a dense-in-the-exponent sense result for weak $B_2[g]$ sets of perfect powers. In the cubic specialization, its Corollary 1 gives bounded distinct-term representation multiplicity and counting exponent $1/3-\varepsilon$ among cube values. It does not make the bound equal to one and does not give positive relative density among the cubes, so it does not answer #1206.

(b) A particularly current check is E. Croot, J. Mao, C. Pohoata, A. Sheffer, and C. H. Yip, A combinatorial large sieve for Sidon sets, distances, and norm forms, arXiv:2606.17487v2, revised 24 June 2026. Section 1.3 explicitly cites Erdős problem #1206 and distinguishes it from the paper's new result for $B_3[g]$ subsets of cubes. The paper proves no $B_2[1]$-in-cubes resolution.

(d) Targeted searches for “largest Sidon subset cubes,” “Sidon subset of cubes,” $N^{8/9}$, and “Erdős Problem #1206,” including July 2026 arXiv results, found the sources above but no claimed resolution, counterexample, or exact finite table for this particular sequence. A search miss is not a theorem; it is reported only to delimit this run's literature audit.

2. Exact reduction to a collision hypergraph

For this report define

g_3(N)=\max\bigl\{|I|:I\subseteq[N],\ \{i^3:i\in I\}\text{ is Sidon}\bigr\}.

The standard Sidon convention includes sums with a repeated summand.

For every integer $s$, let

\mathcal P_N(s)= \bigl\{\{a,b\}:1\le a\le b\le N,\ a^3+b^3=s\bigr\}.

Define a hypergraph $\mathcal H_N$ on vertex set $[N]$ by putting in an edge

P\cup Q

for every $s$ and every two distinct $P,Q\in\mathcal P_N(s)$.

(a) Exact reduction.

\boxed{g_3(N)=N-\tau(\mathcal H_N),}

where $\tau$ is the minimum transversal (hitting-set) number.

Indeed, $I\subseteq[N]$ fails the Sidon condition exactly when it contains both pairs $P$ and $Q$ from some repeated cube sum, which is exactly when it contains an edge of $\mathcal H_N$. Thus $I$ is independent in $\mathcal H_N$ if and only if its complement hits every edge. This formulation also handles a hypothetical collision between a diagonal pair $\{a,a\}$ and another pair; no assumption about edge uniformity is required.

3. A certificate proof that $g_3(131)=111$

The explicit construction

Let

D=\{1,2,4,6,18,24,33,36,42,48,50,51,58,60,63,72,76,80,90,92\}.

(a) The set

\{n^3:n\in[131]\setminus D\}

is a Sidon set of size $131-20=111$. The verifier checks this twice:

$D$ intersects every recomputed collision hyperedge;
independently, all $111\cdot112/2=6216$ unordered sums of two retained cubes are inserted into a fresh dictionary and found distinct.

Hence $g_3(131)\ge111$.

The exact upper certificate

(a) Enumeration at $N=131$ gives:

$131\cdot132/2=8646$ unordered root pairs;
8580 distinct cube-sum values;
66 values with two representations each;
66 collision hyperedges, all of size four in this finite range;
103 vertices occurring in at least one edge.

The lexicographically sorted edge list has SHA-256

f7dcf1d67204f7562b4515a4724080fa605703b433f68d60ff5d5742134ed61f

The checker contains 42 positive integer edge weights with common denominator $10^6$. It checks, using integer arithmetic only, that

\sum_{e\in E(\mathcal H_{131})}w_e =\frac{19285025}{10^6}=19.285025>19

and that every vertex $v$ has load

\sum_{e\ni v}w_e\le \frac{999000}{10^6}<1.

The complete 42-entry certificate is in DUAL_WEIGHTS in runs/erdos1206_wavew038_verify.py; every key is checked against the freshly recomputed collision edges.

For any transversal $T$,

\sum_e w_e \le \sum_{v\in T}\sum_{e\ni v}w_e \le |T|.

The first inequality holds because $T$ hits every edge. Therefore $|T|>19$, and integrality gives $|T|\ge20$. The displayed set $D$ is a transversal of size 20, so

\tau(\mathcal H_{131})=20 \quad\text{and consequently}\quad \boxed{g_3(131)=111}.

This upper bound is a finite rational certificate, not reliance on a solver's “optimal” status.

4. Exact table through $N=131$

(d) The following is the complete exact table in compressed form. On each inclusive interval, $g_3(N)=N-\tau$.

| $N$ interval | $\tau(\mathcal H_N)$ | Exact $g_3(N)$ | |---:|---:|---:| | 1–11 | 0 | $N$ | | 12–23 | 1 | $N-1$ | | 24–31 | 2 | $N-2$ | | 32–33 | 3 | $N-3$ | | 34–38 | 4 | $N-4$ | | 39–50 | 5 | $N-5$ | | 51–52 | 6 | $N-6$ | | 53–54 | 7 | $N-7$ | | 55–59 | 8 | $N-8$ | | 60–67 | 9 | $N-9$ | | 68 | 10 | 58 | | 69–79 | 11 | $N-11$ | | 80–81 | 12 | $N-12$ | | 82–83 | 13 | $N-13$ | | 84–95 | 14 | $N-14$ | | 96–98 | 15 | $N-15$ | | 99–101 | 16 | $N-16$ | | 102–107 | 17 | $N-17$ | | 108 | 18 | 90 | | 109–112 | 19 | $N-19$ | | 113–131 | 20 | $N-20$ |

Why the full table check is exact

(a) For each row $[L,R]$ with displayed value $\tau$, the standalone program does two things:

it exhaustively proves that $\mathcal H_L$ has no transversal of size

$\tau-1$;

it directly checks an explicit size-$\tau$ transversal of

$\mathcal H_R$, and separately checks its complementary cube set by all pair sums.

Since

\mathcal H_L\subseteq\mathcal H_N\subseteq\mathcal H_R \qquad(L\le N\le R),

these two endpoint checks prove the entire row.

The exhaustive lower-bound routine branches on all non-dominated vertices of an uncovered edge. Its only pruning rules are:

a greedily found collection of pairwise disjoint edges, each of which needs a

different transversal vertex;

vertex domination within the branch edge: if every currently uncovered edge

containing $v$ also contains $w$, any solution using $v$ can replace it by $w$;

memoization of identical uncovered-edge states.

These rules preserve exhaustiveness. Discovery used OR-Tools CP-SAT, but the reported verifier uses only the Python standard library and does not import or trust OR-Tools.

5. Reproduction

The standalone verifier is:

runs/erdos1206_wavew038_verify.py

Run from the repository root:

python runs/erdos1206_wavew038_verify.py

(d) On this VM it completed 54,893 recursive search states in about 23 seconds and ended with:

headline certificate: g3(131)=111; dual=19285025/1000000>19, max vertex load=999000/1000000
N=131 collision data: 8646 pairs, 8580 sums, 66 collision hyperedges, digest=f7dcf1d67204f7562b4515a4724080fa605703b433f68d60ff5d5742134ed61f
full table verified through N=131; search calls=54893
ALL CHECKS PASSED in 22.837 seconds

The source recomputes the cube sums from scratch; the only embedded data are the proposed endpoint transversals, the exact rational dual weights, and the expected digest/table, all of which are rejected if inconsistent with the recomputed arithmetic.

6. What remains and why standard machinery stalls

(b) Tait invokes Hooley's asymptotic count

R_\phi(N)=cN^{4/3}+o(N^{4/3}) \quad\text{for }\phi(x,y)=x^3+y^3

and obtains the $N^{8/9}$ Sidon subset in Theorem 5.1.3. At the level of the collision hypergraph, a naive random choice with root-selection probability $p$ retains about $pN$ vertices and about $p^4N^{4/3}$ collision edges. Balancing these terms gives $p\asymp N^{-1/9}$ and size $N^{8/9}$, exactly explaining the exponent.

(a) This count alone cannot make the elementary deletion argument linear: for fixed positive $p$, its collision term is of order $N^{4/3}$, larger than the $O(N)$ selected vertices. Any linear result must exploit much more than the total number of equal-sum quadruples—specifically, their arithmetic overlap or a construction that avoids them coherently.

(c) In the hypergraph formulation, the precise missing asymptotic lemma is a uniform constant $c>0$ such that

\alpha(\mathcal H_N)\ge cN \quad\text{equivalently}\quad \tau(\mathcal H_N)\le(1-c)N

for every sufficiently large $N$. A sufficient replacement would be an explicit positive-density rule for choosing indices, or a gluing lemma that combines the known Sidon short intervals while ruling out all cross-interval cube-sum collisions. None of the checked sources supplies such a lemma.

(a) The infinite question has an additional coherence issue. An infinite positive-natural-density $A$ with Sidon cubes immediately gives linear finite subsets $A\cap[N]$. Conversely, unrelated linear-size optimizers for every finite $N$ need not be nested and do not by themselves yield an infinite set of positive density; cube-sum collisions are not translation-invariant in the root variable. Thus even a positive answer to the finite formulation requires a genuine uniformity/compactness step before it answers the second formulation.

(d) Finite enumeration cannot close that gap. Pair generation is only $O(N^2)$, but exact transversal search is exponential in the collision structure; more importantly, any fixed cutoff proves no uniform positive density. The rational certificate and table above are therefore finite progress only, and no asymptotic or infinite conclusion is claimed.

PARTIAL: The problem remains open; a from-scratch exact certificate proves $g_3(131)=111$, and exhaustive independent verification gives the complete table $g_3(N)$ for every $1\le N\le131$.

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