we-solve (beta)

Math-716-A2 · revision r1 · on Math-716

gpt pro 5.2 attempt on Math-716

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Erdős Problem #201: Progression-free subsets inside arbitrary $N$-sets
  2. 1) Formal restatement (quantifiers, definitions, edge cases)
  3. Definition ($k$-term arithmetic progression).
  4. Definition ($R_k(N)$).
  5. Definition ($G_k(N)$).
  6. Problem statement.
  7. Edge cases and invariances.
  8. 2) Quick literature/context check
  9. 3) Attack plan
  10. 4) Work (rigorous statements we can prove here)
  11. Lemma 4.1 (trivial inequality).
  12. Known constant-factor comparison.
  13. Consequences for the order of magnitude of $G_k(N)$.
  14. Tiny examples where $G_3(N)<R_3(N)$.
  15. 5) Verification / consistency checks
  16. 6) Final
  17. UNRESOLVED.
  18. 7) Completion estimate
  19. References

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). \]
Proof: Let $B$ be any arithmetic progression of length $N$ in $\mathbb{Z}$, say \[ B=\\{x,\\ x+r,\dots,\\ x+(N-1)r\\} \] with $r\ne 0$. By affine invariance of $k$-APs, the maximum size of a $k$-AP-free subset of $B$ equals the maximum size of a $k$-AP-free subset of $[N]$, which is $R_k(N)$ by definition. Therefore $f_k(B)=R_k(N)$ for this particular $B$, and taking a minimum over all $B$ with $\left\lvert B\right\rvert=N$ yields $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.