There are

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} \]

3. The greedy recurrence can be written

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

Proof. If \(i \[ 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

with \(a_i,a_j,a_k

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

\(i

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

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

Therefore

(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

The forward-obstruction lemma gives the exact partition

(a) Problem 340 is equivalent to

or, using (8),

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

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:ia_m\) is rejected exactly

when \(x=a+d\) for some \(a\in A_m,d\in\Delta_m\).

2. 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

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

prefix and checks that none repeat.

4. 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) |

|---:|---:|---:|---:|

| 10 | 81 | 15 | 1.908485019 |

| 20 | 475 | 74 | 2.057365025 |

| 50 | 4,851 | 72 | 2.169450470 |

| 100 | 27,219 | 964 | 2.217436083 |

| 200 | 172,922 | 1,938 | 2.276306810 |

| 300 | 514,644 | 3,386 | 2.305703406 |

| 500 | 2,085,045 | 3,827 | 2.341306284 |

| 1,000 | 14,018,951 | 15,074 | 2.382238506 |

| 1,500 | 43,205,712 | 46,104 | 2.404068568 |

| 2,000 | 96,592,680 | 12,682 | 2.418925071 |

| 2,500 | 181,112,496 | 297,286 | 2.430280816 |

| 3,000 | 303,314,913 | 38,136 | 2.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

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

first fails at

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\) |

|---:|---:|---:|---:|---:|---:|---:|---:|

| 10 | 97 | 165 | 122 | 43 | 36 | 86 | 0.521212121 |

| 25 | 916 | 2,600 | 1,293 | 1,307 | 403 | 890 | 0.342307692 |

| 50 | 5,123 | 20,825 | 7,802 | 13,023 | 2,730 | 5,072 | 0.243553421 |

| 100 | 28,566 | 166,650 | 45,253 | 121,397 | 16,788 | 28,465 | 0.170807081 |

| 200 | 174,171 | 1,333,300 | 285,705 | 1,047,595 | 111,735 | 173,970 | 0.130480762 |

| 300 | 524,307 | 4,499,950 | 850,391 | 3,649,559 | 326,385 | 524,006 | 0.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)

2. 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)

3. 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)

4. 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)

5. 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)

6. 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\),

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).