Erdős Problem #201

Erdős Problem #201: progression-free subsets inside arbitrary $N$-sets (ROUND 2)

1) ROUND-2 OBJECTIVE

I again pursue path (C). This is Erdős Problem #201 [Bloom201]. Round 1 gave the classical comparison \[ G_k(N)\asymp_k R_k(N) \] up to unspecified constants, but it still relied on the external Komlós--Sulyok--Szemerédi theorem and did not isolate what structural feature of an arbitrary set $B$ makes it hard or easy to extract a large progression-free subset. In this round I replace that coarse comparison by a direct theorem depending on the number of progression-types already present in $B$, and then use it to rule out an entire class of candidate "worst-case" sets.

2) Round-1 FOUNDATION USED

From Round 1 I use only the notation \[ f_k(B):=\max\{|A|: A\subseteq B\text{ contains no nontrivial }k\text{-term AP}\} \] and \[ G_k(N):=\min_{|B|=N} f_k(B), \qquad R_k(N):=f_k(\{1,2,\dots,N\}). \] I also use the trivial inequality $G_k(N)\le R_k(N)$ already proved in Round 1, together with the fact that Komlós--Sulyok--Szemerédi give the complementary comparison $R_k(N)\ll_k G_k(N)$ and that Semchankau refines this on a dense subsequence [KSS75,Semchankau20].

3) NEW INSIGHT / TOOL (ROUND 2)

The new tool is O'Bryant's arbitrary-set version of the Behrend construction [OBryant10]. It gives lower bounds for $f_k(B)$ not merely in terms of $|B|$, but in terms of how many progression-types are present in $B$.

For $D=1$ (ordinary arithmetic progressions), the type of a nontrivial $k$-term progression is determined by its first two terms. So the relevant parameter is a concrete measure of how many $k$-term progression patterns $B$ actually supports.

This lets us bypass the KSS theorem entirely and prove a direct lower bound for $G_k(N)$.

4) ATTACK PLAN (ROUND 2)

The Round-1 obstacle was that constant-factor compression theorems do not get close to the ratio question $R_3(N)/G_3(N)\to 1$.

The new plan is different:

1. specialize O'Bryant's theorem to ordinary arithmetic progressions ($D=1$);
2. use the crude but universal bound that the number of $k$-term progression-types in an $N$-element set is at most $N^2$;
3. deduce a direct lower bound for $G_k(N)$ of Behrend type, with no appeal to KSS;
4. then sharpen it for sets with very few progression-types, thereby ruling out a large structured class of candidate hard examples.

This does not solve the ratio problem, but it produces a new structural obstruction not present in Round 1.

5) WORK (ROUND 2)

Fix $k\ge 3$. For a finite set $B\subset \mathbf Z$, let $\mathrm{Type}_k(B)$ denote the number of types of nontrivial $k$-term arithmetic progressions contained in $B$ in the sense of O'Bryant's theorem for $D=1$.

Theorem 5.1 (O'Bryant, specialized to $D=1$). Fix an integer $n\ge 2$ with \[ k>2^{n-1}. \] Let $\Psi(N)\ge 2$ be any function. Then every finite set $B\subset \mathbf Z$ of size $N$ satisfying \[ \mathrm{Type}_k(B)\le N\Psi(N) \] contains a $k$-AP-free subset of size at least \[ f_k(B)\gg_{k,n,\Psi} N\, (\log \Psi(N))^{1/(2n)} \exp\! \left(-C_{k,n}(\log \Psi(N))^{1/n}\right) \] for some constant $C_{k,n}>0$ depending only on $k$ and $n$.

Justification. This is exactly O'Bryant's Theorem 1 for $D=1$ [OBryant10], rewritten with natural logarithms and with all harmless base-change constants absorbed into $C_{k,n}$ and the Vinogradov symbol.

Lemma 5.2. For every $N$-element set $B$, \[ \mathrm{Type}_k(B)\le N^2. \]

Proof. A nontrivial $k$-term arithmetic progression is determined by its first two terms. There are at most $N^2$ ordered choices for those two terms from $B$, so there are at most $N^2$ progression-types. $\square$

Corollary 5.3 (direct arbitrary-set lower bound). Let \[ n_k:=\lceil \log_2 k\rceil. \] Then, for every $N\ge 2$, \[ G_k(N)\gg_k N\, (\log N)^{1/(2n_k)} \exp\!\left(-C_k(\log N)^{1/n_k}\right) \] for some constant $C_k>0$.

Proof. By definition of $n_k$, we have $k>2^{n_k-1}$, so Theorem 5.1 applies with $n=n_k$. By Lemma 5.2 every $N$-element set $B$ satisfies \[ \mathrm{Type}_k(B)\le N^2=N\cdot N, \] so we may take $\Psi(N)=N$. Hence every such $B$ contains a $k$-AP-free subset of size at least \[ \gg_k N\, (\log N)^{1/(2n_k)} \exp\!\left(-C_k(\log N)^{1/n_k}\right). \] Minimizing over all $B$ of size $N$ gives the claimed bound for $G_k(N)$. $\square$

Special case $k=3$. Here $n_k=2$, so Corollary 5.3 becomes \[ G_3(N)\gg N\, (\log N)^{1/4}\exp\!\left(-C\sqrt{\log N}\right). \] This is a direct arbitrary-set Behrend-type lower bound, proved without using Komlós--Sulyok--Szemerédi.

Corollary 5.4 (ruling out low-type-complexity families). Fix $A>0$. Suppose $\mathcal B$ is a family of finite sets such that every $B\in \mathcal B$ of size $N$ satisfies \[ \mathrm{Type}_k(B)\le N(\log N)^A. \] Then every such $B$ of sufficiently large size $N$ contains a $k$-AP-free subset of size at least \[ f_k(B)\gg_{k,A} N\, (\log\log N)^{1/(2n_k)} \exp\!\left(-C_{k,A}(\log\log N)^{1/n_k}\right). \] In particular, for $k=3$ one gets \[ f_3(B)\gg_A N\, (\log\log N)^{1/4} \exp\!\left(-C_A\sqrt{\log\log N}\right). \]

Proof. Apply Theorem 5.1 with $n=n_k$ and $\Psi(N)=(\log N)^A$. The conclusion follows immediately. $\square$

Interpretation. Corollary 5.4 rules out an entire class of candidate hard examples: sets whose $k$-term progression-type count is only polylogarithmic per element automatically contain progression-free subsets far denser than the general Behrend scale. So any family that is genuinely difficult for Problem #201 must have substantially richer progression-type structure than that.

6) ADVERSARIAL VERIFICATION

Again I try to break the new work.

• Does O'Bryant's theorem really apply to ordinary arithmetic progressions? Yes. It is stated for $k$-term $D$-progressions, and ordinary arithmetic progressions are exactly the case $D=1$.
• Is $n_k=\lceil \log_2 k\rceil$ admissible? Yes, because then $2^{n_k-1}<k$.
• Could the type count exceed $N^2$? No. Once the first two terms are fixed, the common difference is fixed, hence the whole progression is fixed.
• Did I accidentally claim a pointwise theorem with a constant depending on the individual set $B$? No. Corollary 5.3 is a uniform class statement with $\Psi(N)=N$, and Corollary 5.4 is a uniform class statement with $\Psi(N)=(\log N)^A$.
• Is the improvement genuinely beyond Round 1? Yes. Round 1 used the external KSS comparison $R_k\ll_k G_k$; Round 2 derives a direct lower bound for $G_k$ from an arbitrary-set theorem and, more importantly, isolates a concrete structural obstruction via progression-type complexity.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 establishes a new direct theorem for Problem #201:

Every $N$-element set of integers contains a $k$-AP-free subset of size at least \[ \gg_k N\, (\log N)^{1/(2n_k)}\exp\!\left(-C_k(\log N)^{1/n_k}\right), \qquad n_k=\lceil \log_2 k\rceil, \] without using the Komlós--Sulyok--Szemerédi comparison theorem.

In addition, any family whose $k$-AP-type count is only $N(\log N)^A$ is ruled out as a genuinely hard family: such sets automatically contain much denser progression-free subsets than the generic Behrend scale.

The sharp ratio question \[ \frac{R_3(N)}{G_3(N)}\to 1 \] remains open, but the obstruction has been sharpened: any counterexample strategy must come from sets with very rich arithmetic-progression-type structure.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 62%

References

References

• [Bloom152] T. F. Bloom, Erdős Problem #152, https://www.erdosproblems.com/152, accessed 2026-03-07.
• [Bloom200] T. F. Bloom, Erdős Problem #200, https://www.erdosproblems.com/200, accessed 2026-03-07.
• [Bloom201] T. F. Bloom, Erdős Problem #201, https://www.erdosproblems.com/201, accessed 2026-03-07.
• [ESS94] P. Erdős, A. Sárközy, and T. Sós, On sum sets of Sidon sets. I, Journal of Number Theory 47 $1994$, 329--347.
• [GT08] B. Green and T. Tao, The primes contain arbitrarily long arithmetic progressions, Annals of Mathematics 167 $2008$, 481--547.
• [KSS75] J. Komlós, M. Sulyok, and E. Szemerédi, Linear problems in combinatorial number theory, Acta Mathematica Academiae Scientiarum Hungaricae 26 $1975$, 113--121.
• [MV07] H. Montgomery and R. Vaughan, Multiplicative Number Theory I. Classical Theory, Cambridge Studies in Advanced Mathematics 97, Cambridge University Press, 2007.
• [OBryant04] K. O'Bryant, A complete annotated bibliography of work related to Sidon sequences, Electronic Journal of Combinatorics 11 $2004$, Dynamic Survey 11.
• [OBryant10] K. O'Bryant, Thick subsets that do not contain arithmetic progressions, arXiv:0912.1494.
• [Semchankau20] A. Semchankau, Maximal subsets free of arithmetic progressions in arbitrary sets, arXiv:2010.04490.

OBJECTIVE AND SOURCE REVIEW

Erdős #201; independent attempt, 2026-09-23. For $|B|=N$, let $f_3(B)$ be its maximum three-term-progression-free subset size; set $G_3(N)=\min f_3(B)$ and $R_3(N)=f_3([N])$. The target is the sharp comparison $R_3(N)/G_3(N)\to1$. I read all of 201.tex. It invokes O'Bryant's progression-type theorem. Here I obtain a self-contained necessary condition on any putative extremal set, without importing that theorem.

WORK: COUNTING THE REQUIRED OBSTRUCTIONS

Let $T$ count nontrivial three-term progressions of $B$ as unordered triples, and write $r=f_3(B)$. Independently retain each element with probability $p$. Deleting at most one point from each surviving progression leaves a progression-free set, so \[ r\ge pN-p^3T\qquad(0\le p\le1). \] If $T<N/3$, taking $p=1$ gives $r>N(2/3)$. Therefore whenever $r\le2N/3$ we have $T\ge N/3$ and may put $p=\sqrt{N/(3T)}\le1$. This yields \[ r\ge\frac{2}{3\sqrt3}\frac{N^{3/2}}{\sqrt T}, \qquad T\ge\frac{4N^3}{27r^2}. \] More generally, for $k$-term progressions, optimizing $pN-p^kT_k$ gives \[ f_k(B)\ge\frac{k-1}{k}N\left(\frac{N}{kT_k}\right)^{1/(k-1)} \quad\text{when }T_k\ge N/k. \] Thus a proposed family with unusually small progression-free subsets must support quantitatively many actual progressions. This is the usual alteration argument, not a novel extremal theorem.

ADVERSARIAL VERIFICATION AND REMAINING GAP

A progression is counted once, by its increasing ordering; arbitrary ordered endpoint counts would change constants. Deleting a vertex cannot create new progressions, so overlapping obstructions cause no problem. The cutoff $T\ge N/3$ is essential to keep $p\le1$. A large $T$ is only necessary: it gives no matching upper bound on $f_3(B)$ and no characterization of sets minimizing it. The supplied claim that low-type families cannot be extremal requires comparison to an appropriate upper bound for $R_3$, not merely to another lower bound. No ratio-one conclusion follows from either displayed alteration inequality.

SOURCES CHECKED

Complete local source: gpt_pro_5.4/201.tex. The source's stated ratio problem is used as the target. An external indexed-statement search was attempted on 2026-09-23; no additional external theorem is relied upon in this self-contained calculation.

FINAL

UNRESOLVED. A necessary quantitative progression-count condition is verified, but the sharp comparison remains open in this attempt.

COMPLETION ESTIMATE

Subjective progress toward the ratio-one target. COMPLETION: 8%

Erdős Problem #201: Progression-free subsets inside arbitrary $N$-sets

1) Formal restatement (quantifiers, definitions, edge cases)

Fix an integer $k\ge 3$.

Definition ($k$-term arithmetic progression).

A nontrivial $k$-term arithmetic progression (AP) in $\mathbb{Z}$ is a sequence \[ x,\\ x+r,\\ x+2r,\dots,\\ x+(k-1)r \] with $r\ne 0$.

Definition ($R_k(N)$).

Let $R_k(N)$ be the maximum size of a subset $A\subseteq\\{1,2,\dots,N\\}$ containing no nontrivial $k$-term AP.

Definition ($G_k(N)$).

For a finite set $B\subset\mathbb{Z}$, let $f_k(B)$ be the maximum size of a subset of $B$ containing no nontrivial $k$-term AP. Define \[ G_k(N):=\min_{B\subset\mathbb{Z}\\,:\\ \left\lvert B\right\rvert=N} f_k(B). \] Thus $G_k(N)$ is the guaranteed size of a largest $k$-AP-free subset inside an arbitrary $N$-element set of integers.

Problem statement.

Determine the size/order of growth of $G_k(N)$, and in particular decide whether \[ \lim_{N\to\infty}\frac{R_3(N)}{G_3(N)}=1. \]

Edge cases and invariances.

Affine maps $x\mapsto ux+v$ with $u\ne 0$ preserve $k$-APs, hence preserve the quantity $f_k(B)$ up to relabeling.

2) Quick literature/context check

• Riddell introduced and studied $G_k$-type quantities [Riddell69].
• Trivially $G_k(N)\le R_k(N)$: take $B$ to be an $N$-term arithmetic progression, an affine copy of $[N]$.
• A key theorem of Komlós--Sulyok--Szemerédi states that for fixed $k$, \[ R_k(N)\ll_k G_k(N), \] so $G_k(N)$ and $R_k(N)$ are comparable up to a constant factor depending only on $k$ [KSS75].
• More recently, Semchankau [Semchankau20] re-derives (and for $k>3$ improves along a dense subsequence) such constant-factor comparisons using "compression" (Freiman-homomorphism) ideas; for example for $k=3$ it records the explicit constant $(2^{-15}+o(1))$ from [KSS75], and for $k>3$ shows $(1/4+o(1))$ along a dense subsequence of $N$.

3) Attack plan

1. Establish the trivial inequality $G_k(N)\le R_k(N)$ rigorously.
2. Record the best known (asymptotic) bounds for $R_k(N)$ (Behrend lower bound, Gowers-type upper bounds), and transfer them to $G_k(N)$ using the constant-factor theorem $R_k(N)\ll_k G_k(N)$.
3. Discuss why the sharper asymptotic $R_3(N)/G_3(N)\to 1$ is substantially stronger than constant-factor comparability and seems open.
4. Give tiny-$N$ examples witnessing $G_3(N)<R_3(N)$ (as in the problem statement).

4) Work (rigorous statements we can prove here)

Lemma 4.1 (trivial inequality).

For every $k\ge 3$ and $N\ge 1$, \[ G_k(N)\le R_k(N). \]

Known constant-factor comparison.

Komlós--Sulyok--Szemerédi proved that for each fixed $k$ there exists a constant $C_k$ such that \[ R_k(N)\le C_k\\,G_k(N)\qquad\text{for all }N, \] equivalently $G_k(N)\ge c_k R_k(N)$ with $c_k=1/C_k>0$ [KSS75]. We do not reproduce their full proof here; we instead treat it as an external theorem.

Consequences for the order of magnitude of $G_k(N)$.

Combining Lemma 4.1 and the KSS theorem gives \[ c_k\\,R_k(N)\\ \le\\ G_k(N)\\ \le\\ R_k(N). \] Therefore, up to multiplicative constants depending only on $k$, determining $G_k(N)$ is equivalent to determining $R_k(N)$.

In particular, any known upper/lower bounds on $R_k(N)$ transfer to $G_k(N)$:

• (Lower bounds.) Behrend-type constructions give, for fixed $k$, \[ R_k(N)\ge N\exp\big(-C_k\sqrt{\log N}\big) \] for some constant $C_k>0$ [Beh46,Semchankau20]. Hence the same form holds for $G_k(N)$ (possibly with a different constant in the exponent due to the factor $c_k$).
• (Upper bounds.) Quantitative Szemerédi/Gowers bounds imply $R_k(N)=o(N)$ and give explicit upper bounds such as \[ R_k(N)\le \frac{N}{(\log\log N)^{s_k}} \] for some $s_k>0$ (for fixed $k$) [Gow01,Semchankau20]. Thus $G_k(N)=o(N)$ as well with comparable explicit bounds.

Tiny examples where $G_3(N)<R_3(N)$.

As recorded in [Semchankau20] (and in the problem statement), \[ R_3(5)=4\quad\text{(e.g. }\\{1,2,4,5\\}\text{)},\qquad G_3(5)=3\quad\text{(witness set }\\{1,2,3,4,7\\}\text{)}. \] So the interval $[5]$ is not the worst case even for very small $N$.

5) Verification / consistency checks

• Lemma 4.1 uses only affine invariance, which is immediate from the definition of AP.
• The squeeze $c_k R_k(N)\le G_k(N)\le R_k(N)$ is logically correct given the KSS theorem.
• The transferred bounds are only "up to constants" and do not claim sharp exponents.

6) Final

UNRESOLVED.

1. Strongest proved partial result included here. The trivial inequality $G_k(N)\le R_k(N)$ is proved (Lemma 4.1). With the external theorem of Komlós--Sulyok--Szemerédi [KSS75] that $R_k(N)\ll_k G_k(N)$, one obtains \[ c_k R_k(N)\le G_k(N)\le R_k(N), \] so $G_k(N)$ has the same order of magnitude as $R_k(N)$ up to constants depending only on $k$.
2. First precise obstacle. The question $R_3(N)/G_3(N)\to 1$ asks for asymptotic equality, not just a constant-factor comparison. Known methods (compressions/Freiman-homomorphisms) lose a fixed positive proportion of the set size, and do not currently control this loss down to $o(1)$.
3. Most plausible next lemma. A plausible intermediate goal is to prove that for every $\varepsilon>0$ and all large $N$, \[ G_3(N)\ge (1-\varepsilon)R_3(N), \] perhaps by showing that every $N$-element set contains a large subset that is Freiman-isomorphic to a reasonably long interval (or to a dense subset of an interval) with only $o(N)$ losses. Any "near-lossless" compression theorem of this type would directly address the ratio limit.

7) Completion estimate

\[ \textbf{Completion: }45\%. \] (We can pin down $G_k$ up to constant factors via known theorems, but the sharper ratio question remains open.)

References

• [Beh46] F. A. Behrend, On sets of integers which contain no three terms in arithmetic progression, Proc. Nat. Acad. Sci. U.S.A. 32 $1946$, 331--332.
• [BloSi20] T. F. Bloom and O. Sisask, Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions, arXiv:2007.03528 $2020$.
• [ESS94] P. Erdős, A. S
  'ark
  özy, and T. S
  'os, On sum sets of Sidon sets. I, J. Number Theory 47 $1994$, 329--347.
• [ESS95] P. Erdős, A. S
  'ark
  özy, and V. T. S
  'os, On sum sets of Sidon sets. II, Israel J. Math. 90 $1995$, 221--233.
• [Gow01] W. T. Gowers, A new proof of Szemer
  'edi's theorem, Geom. Funct. Anal. 11 $2001$, no. 3, 465--588.
• [GreenTao08] B. Green and T. Tao, The primes contain arbitrarily long arithmetic progressions, Ann. of Math. 167 $2008$, no. 2, 481--547.
• [KSS75] J. Koml
  'os, M. Sulyok, and E. Szemer
  'edi, Linear problems in combinatorial number theory, Acta Math. Acad. Sci. Hungar. 26 $1975$, 113--121.
• [OBryant04] K. O'Bryant, A complete annotated bibliography of work related to Sidon sequences, Electron. J. Combin. 11 $2004$, #DS11. (Also available as arXiv:math/0407117.)
• [PrimePagesAP] C. Caldwell and others, Primes in arithmetic progression, The Prime Pages (accessed 2026-01-17). https://t5k.org/top20/page.php?page=aplist.html
• [Riddell69] J. Riddell, Sets of integers containing no $n$ terms in arithmetic progression, Nieuw Archief voor Wiskunde $3$ 17 $1969$, 204--209.
• [Semchankau20] S. Semchankau, Maximal subsets free of arithmetic progressions in arbitrary sets, arXiv:2010.04490 $2020$.
• [TV06] T. Tao and V. Vu, Additive Combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge Univ. Press, 2006.