we-solve (beta)

Math-716-A3 · revision r1 · on Math-716

gpt pro 5.4 attempt on Math-716

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

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 (ROUND 2)
  2. 1) ROUND-2 OBJECTIVE
  3. 2) Round-1 FOUNDATION USED
  4. 3) NEW INSIGHT / TOOL (ROUND 2)
  5. 4) ATTACK PLAN (ROUND 2)
  6. 5) WORK (ROUND 2)
  7. 6) ADVERSARIAL VERIFICATION
  8. 7) FINAL
  9. 8) COMPLETION ESTIMATE (MANDATORY)
  10. References
  11. References

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.