A Constructive Lower Bound on Szemerédi's Theorem

Abstract

Let $r_k(n)$ denote the maximum cardinality of a set $A\subset \{1,2,\dots ,n\}$ such that $A$ does not contain a $k$-term arithmetic progression. In this paper, we give a method of constructing such a set and prove the lower bound $n^{1-\frac{c_k}{k\ln k}}<r_k(n)$ where $k$ is prime, and $c_k\to 1$ as $k\to \infty$. This bound is the best known for an increasingly large interval of $n$ as we choose larger and larger $k$. We also demonstrate that one can prove or disprove a conjecture of Erdős on arithmetic progressions in large sets once tight enough bounds on $r_k(n)$ are obtained.

13 pages