Riddell's $G_k(N)$: the largest $k$-AP-free subset forced in any $N$ integers, versus $R_k(N)$ (Erdős #201)
Statement
Let $G_k(N)$ be the largest integer such that every set of $N$ integers contains a subset of size at least $G_k(N)$ with no $k$-term arithmetic progression. Determine the size of $G_k(N)$. How does it relate to $R_k(N)$, the size of the largest subset of $\{1,\ldots,N\}$ without a $k$-term arithmetic progression? Is it true that $$\lim_{N\to\infty}\frac{R_3(N)}{G_3(N)}=1?$$
Acceptance. FULLY RESOLVES: a proof — machine-checkable (Lean/Coq) preferred, else a complete written proof — determining $G_k(N)$ up to $(1+o(1))$ relative to $R_k(N)$ for some $k\geq 3$; in particular a proof or disproof of $\lim_{N\to\infty}R_3(N)/G_3(N)=1$. ADVANCES: a proof making the Komlós–Sulyok–Szemerédi comparison $R_k(N)\ll_k G_k(N)$ explicit or improving it toward ratio $1+o(1)$, strictly better than what is stated in the background; new exact values or improved bounds for $G_3(N)$ for specific $N$ beyond the values stated in the background — each upper bound certified by an explicit witness set of $N$ integers together with reproducible exhaustive-search code confirming its largest 3-AP-free subset size, and each exact value additionally certified by an argument or enumeration covering all realizable $N$-point AP-structures; or a proof that $\limsup_{N\to\infty}R_3(N)/G_3(N)>1$ via an explicit family of witness sets. Deliver the proof file, or the witness sets + search code + exhaustiveness certificates for the computational route.
Background
First asked and investigated by Riddell [Ri69], then pursued by Erdős across [Er73], [Er75b], [ErGr79], [Er80, p.109], [ErGr80]; listed as open on erdosproblems.com/201 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics | arithmetic progressions'). Taking the $N$ integers to be $\{1,\ldots,N\}$ shows trivially that $G_k(N)\leq R_k(N)$, and the inequality can be strict: $G_3(5)=3$ while $R_3(5)=4$, and $G_3(14)\leq 7$ while $R_3(14)=8$. In the other direction Komlós, Sulyok, and Szemerédi [KSS75] proved $R_k(N)\ll_k G_k(N)$, so the two quantities agree up to a constant factor; the open question is whether the ratio tends to $1$ for $k=3$. Exact values of $R_3$ are OEIS A003002 (with A003003–A003005 for $k=4,5,6$); no sequence of exact $G_3$ values exists. Note that for fixed $N$ only finitely many 'AP-structures' (the hypergraph of 3-term-AP triples, constrained by realizability over the integers) can occur on an $N$-point set, so each exact value $G_3(N)$ is in principle a finite computation, though the site classifies the full problem as not resolvable by finite computation. The attacker's tool: small-$N$ exact computation — upper bounds on $G_3(N)$ are finite machine-checkable certificates (an explicit witness set of $N$ integers plus an exhaustive check that its largest 3-AP-free subset is small, via ILP/SAT), and lower bounds come from enumerating realizable AP-structures — building the first table of $G_3(N)$ values and testing $R_3(N)/G_3(N)\to 1$ empirically.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #201 (T. F. Bloom) | website |
| REF-02 | OEIS A003002 — r3(n): size of the largest subset of [1..n] with no 3-term arithmetic progression | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.