ERDŐS/DAILY ▸

← back to the ledger

ERDőS #340 · PARTIAL

Erdős problem 340 — wave 5v

Accessed 2026-07-26 UTC. Claim labels used below:

0. Mandatory live-page gate

I fetched the live page through the configured Bright Data Chromium path, not with datacenter curl. The browser rendered the following current statement on erdosproblems.com/340. This is a verbatim transcription of the statement, with only the displayed mathematics rendered as LaTeX:

Let \(A=\{1,2,4,8,13,21,31,45,66,81,97,\ldots\}\) be the greedy Sidon sequence: we begin with \(1\) and iteratively include the next smallest integer that preserves the Sidon property (i.e. there are no non-trivial solutions to \(a+b=c+d\)). What is the order of growth of \(A\)? Is it true that \[ > \lvert A\cap \{1,\ldots,N\}\rvert \gg N^{1/2-\epsilon} > \] for all \(\epsilon>0\) and large \(N\)?

The live page's listed remarks are:

This sequence is sometimes called the Mian-Chowla sequence. It is trivial that this sequence grows at least like \(\gg N^{1/3}\).

Erdős and Graham [ErGr80] also asked about the difference set \(A-A\), whether this has positive density, and whether this contains \(22\). It does contain \(22\), since \(a_{15}-a_{14}=204-182=22\). The smallest integer which is unknown to be in \(A-A\) is \(33\) (see A080200). It may be true that all or almost all integers are in \(A-A\).

This sequence is at OEIS A005282.

See also [156].

(d: live-page observation) The gate was clear:

Thus there was no page-listed claimed proof or current worker, so I proceeded.

1. Normalisation and equivalence to the term-growth question

Write

\[ 1=a_1<a_2<a_3<\cdots \]

for the greedy sequence and \(A(x)=|A\cap[1,x]|\).

(a) A strictly increasing integer set is Sidon if and only if all of its positive differences \(a_j-a_i\), \(i<j\), are distinct. Indeed, equality of two nonidentical positive differences rearranges to a nontrivial equality of two pair sums, and conversely a nontrivial pair-sum equality can be rearranged after cancelling any common term.

Consequently the \(\binom n2\) positive differences of \(\{a_1,\ldots,a_n\}\) all lie in \([1,a_n-1]\). Hence

\[ a_n\geq \binom n2+1. \tag{1} \]

This is an elementary lower bound for every Sidon sequence, not a property specific to greediness.

(a) The question on the live page is equivalent to

\[ a_n=O_\delta(n^{2+\delta})\quad \text{for every }\delta>0, \tag{2} \]

and, in view of (1), equivalently \(a_n=n^{2+o(1)}\).

For completeness, if the page's lower bound holds, put \(N=a_n\) and solve \(n\gg a_n^{1/2-\epsilon}\) for \(a_n\); choosing \(\epsilon\) in terms of \(\delta\) gives (2). Conversely, if (2) holds and \(m=A(N)\), then

\[ N<a_{m+1}\ll_\delta(m+1)^{2+\delta}. \]

Thus \(A(N)\gg_\delta N^{1/(2+\delta)}\), and \(\delta\) can be chosen so that \(1/(2+\delta)>1/2-\epsilon\).

2. Exact forward-obstruction characterisation

For a prefix \(A_m=\{a_1,\ldots,a_m\}\), define

\[ {\cal T}_m=\{(i,j,k):1\leq i<j\leq k\leq m\} \]

and the set of distinct forward-obstruction values

\[ F_m=\{a_j+a_k-a_i:(i,j,k)\in{\cal T}_m\}. \tag{3} \]

There are

\[ |{\cal T}_m|=\binom{m+1}{3} \tag{4} \]

triple slots, though different slots can have the same value.

Forward-obstruction lemma

(a) The following statements hold exactly:

  1. \(\mathbb N\setminus A=\bigcup_{m\geq1}F_m\).
  2. If \(m=A(X)\), then

\[ [1,X]\setminus A=F_m\cap[1,X], \qquad X-m=|F_m\cap[1,X]|. \tag{5} \]

  1. The greedy recurrence can be written

\[ a_{m+1}=\min\{x>a_m:x\notin F_m\}. \tag{6} \]

Proof. If \(i<j\leq k\), then

\[ v=a_j+a_k-a_i>a_k \quad\text{and}\quad v+a_i=a_j+a_k. \]

When the greedy process reaches \(v\), all three witness terms have already been accepted, so \(v\) is rejected. Thus every value in every \(F_m\) is outside \(A\).

Conversely, suppose an integer \(v\) is rejected. The terms accepted when \(v\) is tested are all smaller than \(v\), and they already form a Sidon set. Therefore a new collision must have the form

\[ v+a_i=a_j+a_k, \]

with \(a_i,a_j,a_k<v\). A collision involving \(2v\) is impossible because every old pair sum is less than \(2v\), and two sums both containing \(v\) cannot collide unless they are the same pair. Order the old summands so that \(j\leq k\). Since \(v>a_k\), the displayed equation forces \(a_i<a_j\), so \(i<j\leq k\) and \(v\in F_m\) for a sufficiently long prefix. If \(v\leq X\), all witness terms also lie in \(A\cap[1,X]\), which proves (5). Formula (6) is the same argument applied just above \(a_m\). ∎

This characterisation is more informative than the unrestricted expression \(A+A-A\): the ordering \(i<j\leq k\) records exactly which triples can reject a future integer.

3. A from-scratch recovery of the best cited cubic scale

Take \(X=a_n-1\) in (5), so \(m=n-1\). There are \(n-1\) accepted and \(a_n-n\) rejected integers below \(a_n\). Equations (4) and (5) give

\[ \begin{aligned} a_n-n &=|F_{n-1}\cap[1,a_n-1]|\\ &\leq |{\cal T}_{n-1}|=\binom n3. \end{aligned} \]

Therefore

\[ \boxed{\displaystyle a_n\leq \binom n3+n =\frac{n^3-3n^2+8n}{6}.} \tag{7} \]

(a) Formula (7) is uniform and its proof is self-contained. It implies the page's \(A(N)\gg N^{1/3}\), now with the \(1/6\) leading constant in the inverse term bound.

(b: Jia attribution; see the source limitation below) Modern literature attributes \(a_n\leq n^3/6+O(n^2)\) to Xing De Jia (1988). Thus (7) recovers the cited leading term independently; I do not claim that the \(1/6\) scale is new.

4. Exact isolation of what remains

Define

\[ \begin{aligned} T_m&=\binom{m+1}{3},\\ D_m&=|F_m|,\\ C_m&=T_m-D_m &&\text{(triple slots lost to repeated values)},\\ P_m&=|F_m\cap[1,a_{m+1}-1]| =a_{m+1}-1-m &&\text{(distinct obstructions before the first gap)},\\ R_m&=D_m-P_m &&\text{(distinct obstructions at or beyond that gap)}. \end{aligned} \]

The forward-obstruction lemma gives the exact partition

\[ T_m=C_m+R_m+P_m. \tag{8} \]

(a) Problem 340 is equivalent to

\[ P_m=O_\eta(m^{2+\eta}) \quad\text{for every }\eta>0, \tag{9} \]

or, using (8),

\[ C_m+R_m\geq \binom{m+1}{3}-O_\eta(m^{2+\eta}) \quad\text{for every }\eta>0. \tag{10} \]

The lower bound (1) ensures that replacing \(a_{m+1}\) by \(P_m\) does not lose the quadratic scale.

Equation (10) is a precise collision-or-overshoot formulation of the missing lemma: asymptotically almost every one of the \(\sim m^3/6\) forward triple slots must either collide with another slot or produce a value beyond the first uncovered integer.

(a) Merely using the Sidon property proves that positive differences are unique, but it gives no upper bound of order \(m^{2+o(1)}\) for the truncated set in (9). A global estimate \(D_m=O_\eta(m^{2+\eta})\) would suffice, but it is stronger than necessary because the \(R_m\) tail also helps.

(c) A viable future attack would therefore need a genuinely greedy-specific theorem forcing either many equalities

\[ a_j+a_k-a_i=a_{j'}+a_{k'}-a_{i'} \]

across different forward triples, or forcing most distinct values above \(a_{m+1}\). I found no standard Sidon-set theorem that supplies either conclusion uniformly.

5. Exact finite computation

The complete standalone verifier is erdos340_wave5v_reverify.py. It reads no term table and uses only exact integer operations (NumPy int64 is ample in the verified range).

Run:

/home/exedev/.venv/bin/python runs/erdos340_wave5v_reverify.py

It performs four separate checks:

  1. It generates 3,000 terms with a window sieve. If

\(\Delta_m=\{a_j-a_i:i<j\}\), a candidate \(x>a_m\) is rejected exactly when \(x=a+d\) for some \(a\in A_m,d\in\Delta_m\).

  1. It independently applies the pair-sum definition candidate by candidate

through \(a_{500}=2{,}085{,}045\). Every one of the 2,084,545 rejected candidates is checked against an explicit ordered witness \(i<j\leq k\), and the two generators agree term-for-term.

  1. It rebuilds and sorts all 4,498,500 positive differences of the 3,000-term

prefix and checks that none repeat.

  1. At six prefix sizes it enumerates every slot in (3), sorts the values,

counts collisions and tail values, and asserts (5). A separate pure Python set enumeration reproduced all six rows.

All statements in the preceding numbered list are (d).

Recomputed terms

(d) Selected exact terms are:

\(n\)\(a_n\)\(a_n-a_{n-1}\)\(\log a_n/\log n\) (descriptive only)
1081151.908485019
20475742.057365025
504,851722.169450470
10027,2199642.217436083
200172,9221,9382.276306810
300514,6443,3862.305703406
5002,085,0453,8272.341306284
1,00014,018,95115,0742.382238506
1,50043,205,71246,1042.404068568
2,00096,592,68012,6822.418925071
2,500181,112,496297,2862.430280816
3,000303,314,91338,1362.439343682

The SHA-256 digest of all 3,000 lines in the exact format index:term\n is

427ce916b5df205e3b78a533010fa0453b4c4d1bc103fb815e9743cea755da24

(d) After generation, I compared this digest with the first 3,000 rows of the independent OEIS table; it agrees. OEIS already provides tables far beyond this range, so this is a reproducible audit, not a record computation.

An exact finite exponent bracket

(d) Direct big-integer comparison proves for this finite range that

\[ a_n^{25}\leq n^{61} \qquad (2\leq n\leq3000), \tag{11} \]

i.e. \(a_n\leq n^{61/25}=n^{2.44}\). The nearby inequality

\[ a_n^{16}\leq n^{39} \]

first fails at

\[ n=2853,\qquad a_{2853}=264{,}446{,}854. \]

This brackets the best exponent of this particular no-constant form between \(39/16=2.4375\) and \(61/25=2.44\) on the tested prefix. It says nothing uniformly as \(n\to\infty\).

Collision/tail census

(d) The exact obstruction split in (8) is:

\(m\)\(a_{m+1}\)\(T_m\)\(D_m\)\(C_m\) collisions\(R_m\) tail\(P_m\) prefix\(P_m/T_m\)
10971651224336860.521212121
259162,6001,2931,3074038900.342307692
505,12320,8257,80213,0232,7305,0720.243553421
10028,566166,65045,253121,39716,78828,4650.170807081
200174,1711,333,300285,7051,047,595111,735173,9700.130480762
300524,3074,499,950850,3913,649,559326,385524,0060.116447072

The decreasing last column is finite evidence for the mechanism demanded by (10), but (c) it is not evidence of a proved rate and must not be extrapolated into an asymptotic conclusion.

Resource use

(d) On this VM (Python 3.12.3, NumPy 2.4.6), the full default verification took 62.18 seconds and 117,072 KiB peak RSS. The window sieve itself took 56.16 seconds.

6. Literature audit

  1. Original source. I inspected the scan of Erdős and Graham,

Old and New Problems and Results in Combinatorial Number Theory (1980), page 53 in the UCSD scan. It asks “What is the order of growth of \(a_n\)? In particular is \(a_n=O(n^{2+\epsilon})\)?” and records the then-known \(O(n^3)\) bound. (d: direct source observation)

  1. Jia (1988). The bibliographic item exists as X. D. Jia,

“On the distribution of a \(B_2\)-sequence,” Qufu Shifan Daxue Xuebao Ziran Kexue Ban 14 (1988), 12–18, MR 89j:11023. I did not locate an inspectable copy of the original six-page article. I therefore do not pretend to have checked its proof directly. (d: bibliographic audit)

  1. Modern primary research source. Yin Choi Cheng,

“Greedy Sidon sets for linear forms”, Journal of Number Theory 266 (2025), 225–248, calls the classical growth problem “enigmatic” and attributes \(a_n\leq n^3/6+O(n^2)\) to Jia. The same statement and full reference are visible in Cheng's institutional 2023 dissertation. (b: rigorous attribution through Cheng, not direct inspection of Jia)

  1. Survey cross-check. Kevin O'Bryant's

annotated Sidon bibliography verifies the Jia bibliographic entry and records Stöhr's earlier \(a_n<(n-1)^3+1\) bound, while describing the greedy growth as not well understood. (b: source-based historical claim)

  1. Recent open-problem cross-check. Boris Alexeev and Dustin Mixon's

2025 paper Forbidden Sidon subsets of perfect difference sets restates this growth question as an open problem; it does not claim a solution. (d: direct source observation)

  1. Computation already in the public record. The current

OEIS A005282 entry links exact tables through 100,000 terms. It also contains a user-contributed conjecture \(a_n\sim n^3/\log^2n\). That conjecture is (c) and is not treated here as a theorem or as evidence that Problem 340 is false.

The primary-source/title/DOI searches found no claimed proof of \(a_n=n^{2+o(1)}\) or its negation. (d: search result, not a theorem) This is consistent with, but logically weaker than, the authoritative live page's OPEN status.

7. Why this stops short of the conjecture

The reduction (8)–(10) is exact, but it exposes the obstacle rather than removing it. The ordinary Sidon condition controls equal two-term differences. The needed estimate controls either collisions between three-term forward obstructions or their location relative to a greedily-defined first gap. Neither feature follows from the usual distinct difference count. (a)

Finite computation cannot provide the uniformity in (9). For scale, at \(m=100{,}000\),

\[ \binom{100001}{3}=166{,}666{,}666{,}650{,}000. \]

Materialising one 64-bit value per forward triple would require about 1.33 PB before sorting or deduplication. At an optimistic 10–50 million triple evaluations per second per native-code core, enumeration alone would cost roughly 4,630–926 core-hours; sorting/deduplication and memory traffic would be substantially worse. The term sieve also needs \(\binom{100000}{2}\) 64-bit differences, about 37.25 GiB, with the present implementation. (c: engineering estimate) I did not run such a job.

The concrete missing result is therefore (10), or any stronger lemma that implies it uniformly. Without that uniform collision-or-overshoot estimate, the exact identities and finite tables cannot close Problem 340.

PARTIAL: Proved the exact forward-obstruction characterisation and \(a_n\leq\binom n3+n\), independently recomputed 3,000 terms and the collision/tail split, but the required uniform \(m^{2+o(1)}\) bound remains the unproved collision-or-overshoot inequality (10).

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