Erdős problem 1097 — live-page audit, reduction, and exact small cases

Accessed 2026-07-27 UTC. This report uses:

• (a) elementary-rigorous;
• (b) rigorous modulo a named theorem;
• (c) plausible/structural-unverified;
• (d) computational-only.

0. Mandatory live-page check

I fetched both the problem page and its discussion thread through the Bright

Data browser, rather than through datacenter curl:

• <https://www.erdosproblems.com/1097>
• <https://www.erdosproblems.com/forum/discuss/1097> (redirected to

/forum/thread/1097)

The live page displayed OPEN, was last edited 01 April 2026, and

displayed:

• 17 comments;
• 0 claimed proofs;
• Interested in collaborating: None;
• Currently working on this problem: None;
• all other interest/difficulty/formalisation-work markers: None;
• “Formalised statement? Yes.”

Thus none of the mandatory stop conditions applied.

Verbatim current statement

> Let \(A\) be a set of \(n\) integers. How many distinct \(d\) can occur as the common difference of a three-term arithmetic progression in \(A\)?

>

> In particular, are there always \(O(n^{3/2})\) many such \(d\)?

Known results stated on the live page

The page says:

1. Erdős posed this at the 1989 Great Western Number Theory problem session.

Erdős and Ruzsa had an explicit construction with \(n^{1+c}\) differences

for some \(c>0\), while Erdős and Spencer probabilistically attained

\(n^{3/2}\).

2. Koishi Chan observed that the optimal exponent is exactly the

sums-differences exponent from Bourgain's Kakeya work.

3. The current bounds are

\[ 1.77898\ldots\ \leq \gamma\leq \frac{11}{6}=1.8333\ldots. \]

The upper bound is attributed to Katz--Tao; the lower bound to Lemm, with

a tiny (eighth-decimal) AlphaEvolve improvement.

4. Consequently the \(O(n^{3/2})\) question is false, but the first,

open-ended question asking for the correct order remains open.

This is why the page is OPEN even though the displayed \(3/2\) suggestion has

been falsified.

What all 17 comments contain

The forum warns that comments are not verified. I read all 17. In condensed

form, without treating any of them as a theorem:

• Koishi Chan gave the initial constructions connecting progression

differences with sum/difference sets, including

\[ A=(U+Y)\cup(-U-Y)\cup\tfrac12(U+U), \]

and explained the resulting score

\(|U+U||U-U|/|U|\). Chan also reported an unsuccessful search over subsets

of \(\{1,\ldots,17\}\) for one earlier construction.

• Thomas Bloom observed a \(5/3\) ceiling for that particular construction,

pointed to the Hennecart--Robert--Yudin high-dimensional construction

(score about \(1.5828\)), and later asked for the missing direction in the

claimed full equivalence.

• Chan used Gerbicz's arXiv:2505.16105 data to get an intermediate \(1.528\)

construction for this problem.

• Terence Tao reported \(U=\{0,3,7,15,16,21\}\), with

\((|U|,|U+U|,|U-U|)=(6,21,31)\) and score about \(1.5394\), followed after

ten hours by a 14-element example with \((14,105,183)\) and score about

\(1.5523\).

• Chan identified Bourgain's partial sums-differences question and the

Katz--Tao \(11/6\) upper bound. In response to Bloom's question, Chan gave

the reverse construction

\(X=A\cup B\cup \tfrac12(A+_G B)\), which turns every edge of \(G\) into a

3-AP. Bloom accepted the equivalence and noted the \(1.77898\) record in

the AlphaEvolve paper.

• Six comments by Adenwalla, Moritz Firsching, Woett, Nat Sothanaphan, and

Bloom discussed wording and whether the page should be called solved. The

resolution was that it is a two-part question: the \(3/2\) part is settled

negatively, while the optimal exponent is not known. The site says it was

updated in response.

• One John N. Dvorak comment was appreciative but contained no mathematical

claim.

There was no proof claim and no current-worker marker hidden in the discussion

thread.

1. Primary-source audit

The following sources were opened and their relevant statements checked.

1. Original source. The linked 1989 scan

<https://westcoastnumbertheory.org/wp-content/uploads/2018/02/wcnt-problems-1989.pdf>

is image-only. Local OCR locates problem 89:27 on scan page 14 and

matches the live-page attribution and the \(n^{3/2}\) speculation.

2. Bourgain. J. Bourgain, *On the dimension of Kakeya sets and related

maximal inequalities*, GAFA 9 (1999), 256--282,

<https://doi.org/10.1007/s000390050087>. This is the cited source of the

partial sums-differences route.

3. Katz--Tao. N. H. Katz and T. Tao, *A new bound on partial sum-sets and

difference-sets, and applications to the Kakeya conjecture*,

<https://arxiv.org/abs/math/9906097>. Its abstract and displayed proof

give

\[ |A-_G B|\leq N^{\,2-1/6}=N^{11/6} \]

when \(|A|,|B|,|A+_G B|\leq N\). (b)

4. Lemm. M. Lemm, New Counterexamples for Sums-Differences,

<https://arxiv.org/abs/1404.3745>, Theorem 2.1: there is

\(\alpha>1.77898\) for which the corresponding

\(\mathrm{SD}(0,1,\infty;\alpha)\) statement fails. (b)

5. AlphaEvolve paper. B. Georgiev, J. Gómez-Serrano, T. Tao, A. Wagner,

Mathematical exploration and discovery at scale,

<https://arxiv.org/abs/2511.02864>, p. 41: it records

\(1.77898\leq C(\{0,1,\infty\};-1)\leq11/6\) and says AlphaEvolve improved

the first lower bound only in the eighth decimal. (b)

6. Independent current confirmation. T. Tao, *Sum-difference exponents

for boundedly many slopes, and rational complexity*,

<https://arxiv.org/abs/2511.15135>, equation in §1.1, again states

\[ 1.77898\leq\mathrm{SD}(\{0,1,\infty\};-1)\leq11/6. \]

Its new theorems concern rational complexity/bounded slope families and

do not improve this three-slope interval. (b)

7. The thread's auxiliary references also exist and say what the comments

claim: Gerbicz's Sums and differences of sets is

<https://arxiv.org/abs/2505.16105>, and Hennecart--Robert--Yudin's paper is

<https://www.numdam.org/item/AST_1999__258__173_0/>.

Two 2026 search hits do not settle or improve the unrestricted problem:

Carnovale--Senger, <https://arxiv.org/abs/2602.03029>, imposes density/Fourier

conditions, while Conlon--Fox--Pham, <https://arxiv.org/abs/2605.13628>,

studies restricted differences over finite vector spaces. I found no primary

source claiming a post-page improvement to the unrestricted three-slope

exponent. This is a search report, not proof that no such source exists.

2. Exact equivalence, with constants and the integer scaling exposed

Define the signed nonzero progression-difference set

This agrees with the linked formalisation. Put

For finite \(A,B\subset\mathbb Z\) and \(G\subseteq A\times B\), write

Partial sums-differences upper bound implies the AP upper bound

Given \(X\), let \(A=B=X\) and

Then \(|A|=|B|=|X|\), \(|A+_G B|\leq|X|\), and

as sets up to the harmless sign convention; in particular their cardinalities

are equal. Therefore any uniform partial sums-differences exponent is a

uniform AP-difference exponent. (a)

AP upper bound implies the partial sums-differences upper bound

Given \(A,B,G\), use the integer set

For every \((a,b)\in G\),

is a 3-AP with difference \(b-a\). Hence

The \(+1\) only accounts for the possible zero difference. Thus the two

optimal exponents are exactly equal, including the required uniformity in

the input sets. (a)

Combining this reduction with Katz--Tao and Lemm/AlphaEvolve yields the

live-page interval for \(\gamma\). (b)

3. New exact small-case computation

For clarity, define only positive differences

Reversing a progression pairs \(d\) with \(-d\), so

The exhaustive result is:

| \(n\) | exact \(M_n\) | exact signed maximum | attaining \(A\) | \(P(A)\) |

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

| 1 | 0 | 0 | \(\{0\}\) | \(\varnothing\) |

| 2 | 0 | 0 | \(\{0,1\}\) | \(\varnothing\) |

| 3 | 1 | 2 | \(\{0,1,2\}\) | \(\{1\}\) |

| 4 | 2 | 4 | \(\{0,1,2,4\}\) | \(\{1,2\}\) |

| 5 | 3 | 6 | \(\{0,1,2,4,7\}\) | \(\{1,2,3\}\) |

| 6 | 4 | 8 | \(\{0,1,2,4,5,8\}\) | \(\{1,2,3,4\}\) |

| 7 | 6 | 12 | \(\{0,1,2,4,7,8,14\}\) | \(\{1,2,3,4,6,7\}\) |

The examples and displayed difference sets are direct exact checks (a).

The assertion that they are globally maximal is an exhaustive exact-rational

computation (d), with the completeness reduction below (a).

For comparison, the elementary center-counting bound is

Indeed, reflection about the \(j\)-th ordered element injects the possible

left endpoints into the right endpoints. The exhaustive result sharpens

this bound from \(9\) to \(6\) when \(n=7\). (a)

4. Why the enumeration is global (no coordinate cutoff)

Write \(A=\{a_0<\cdots \[ g_i=a_{i+1}-a_i>0\quad(0\leq iFor every \(i

linear form

vanishes. There are only \(\binom n3\) such hyperplanes.

The verifier enumerates every row space generated by a subset of these

forms, stores it in canonical reduced row-echelon form over Fraction, and

keeps it precisely when its kernel meets the positive orthant. Completeness

is elementary: take the AP equations true for any proposed \(A\), choose a

spanning sequence, and add them in that order. Every prefix is retained

because the same positive gap vector lies in its kernel. (a)

The positivity test is also exact. From a rational nullspace basis

\(v_1,\ldots,v_q\), write \(g=\sum y_s v_s\). By homogeneity, \(g_i>0\) for

all \(i\) is equivalent to the feasibility of \(g_i\geq1\) for all \(i\).

The verifier decides these rational inequalities by an in-source

Fourier--Motzkin eliminator. It calls no floating-point LP, SAT solver, or

external algebra package. (a)

On a row space \(R\), every AP equation in \(R\) holds. Its positive

difference is the linear form

Two such differences are forced equal exactly when

\(Q_{ij}-Q_{i'j'}\in R\). The program counts the residue classes modulo

\(R\). For an actual gap vector, any additional accidental equality can

only merge classes, so this count is an upper bound. The explicit examples

meet the computed upper bounds. (a)+(d)

The numbers of positive-orthant flats exhausted were:

| \(n\) | feasible flats | ranks of those flats |

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

| 3 | 2 | \(1,1\) |

| 4 | 8 | \(1,4,3\) |

| 5 | 54 | \(1,10,27,16\) |

| 6 | 581 | \(1,20,126,286,148\) |

| 7 | 9,257 | \(1,35,420,2184,4463,2154\) |

Here each rank list starts at rank zero.

5. Reproduction

The standalone verifier is

runs/erdos1097_wave6u_verify.py. Run:

python runs/erdos1097_wave6u_verify.py

It independently computes each example's differences in two ways (by

ordered pairs and by unordered triples), asserts the displayed sets, then

rebuilds the complete flat enumeration. A reference run on this VM used

about 46 seconds and ended with:

n  max positive d  max signed nonzero d  positive D  example
1               0                     0  ()  (0,)
2               0                     0  ()  (0, 1)
3               1                     2  (1,)  (0, 1, 2)
4               2                     4  (1, 2)  (0, 1, 2, 4)
5               3                     6  (1, 2, 3)  (0, 1, 2, 4, 7)
6               4                     8  (1, 2, 3, 4)  (0, 1, 2, 4, 5, 8)
7               6                    12  (1, 2, 3, 4, 6, 7)  (0, 1, 2, 4, 7, 8, 14)
ALL CHECKS PASSED

6. What remains

The asymptotic problem is untouched by a finite \(n\leq7\) table. Under the

exact equivalence above, an improved uniform upper bound requires the missing

lemma

for some fixed \(\varepsilon>0\); existing Katz--Tao machinery supplies

\(\varepsilon=0\), not a saving. Closing the problem requires either such a

uniform inequality, a construction/entropy distribution raising the

\(1.77898\ldots\) lower exponent, or a meeting argument.

The exact-flat method itself scales rapidly: its feasible-flat count grew

\(581\to9257\) from \(n=6\) to \(7\), while runtime grew from about one second

to about 45 seconds. A naive \(n=8\) extension is plausibly tens of minutes

to several hours (roughly \(0.5\)--\(3\) core-hours, extrapolated rather than

measured), so it was deliberately not run under the stated CPU budget. (c)

PARTIAL: Exact exhaustive rational enumeration proves the signed maxima \(0,0,2,4,6,8,12\) for \(1\leq n\leq7\), with a standalone checker; the asymptotic exponent remains in the verified interval \(1.77898\ldots\leq\gamma\leq11/6\).