Problem 179

Let $1\leq k<\ell$ be integers and define $F_k(N,\ell)$ to be minimal such that every set $A\subset \mathbb{N}$ of size $N$ which contains at least $F_k(N,\ell)$ many $k$ -term arithmetic progressions must contain an $\ell$ -term arithmetic progression. Find good upper bounds for $F_k(N,\ell)$ . Is it true that

F_3(N,4)=o(N^2)?

Is it true that for every $\ell>3$

\lim_{N\to \infty}\frac{\log F_3(N,\ell)}{\log N}=2?

Source: erdosproblems.com/179

Additive combinatorics
Arithmetic progressions

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved: the site's label. Both displayed questions are answered yes by Fox and Pohoata (claim page (Fox and Pohoata, 2019)), whose bounds tie $F_k(N,\ell)$ to the largest $\ell$ -term-progression-free subset of $\{1,\ldots,N\}$ , so that the Szemerédi bounds of Leng, Sah and Sawhney [LSS24] sharpen the upper bound; the claim is accepted on the refereed publication in Random Structures and Algorithms (2021) and the site's adoption, and nothing rests on a review by this project.

Problem 179

Status

Proof claims

Discussion