Problems Involving Arithmetic Progressions - Largest Progression-free Subsets

Largest Progression-free Subsets

Find the cardinality (denoted by A_k(m)) of the largest subset of {1, 2, ..., m} which contains no progression of k distinct terms. The elements of the forbidden progressions are not required to be consecutive.

For example, A₄(10) = 8, because {1, 2, 3, 5, 6, 8, 9, 10} has no arithmetic progressions of length 4, while all 9-element subsets of {1, 2, ..., 10} have one. Paul Erdős set a $1000 prize for a question related to this number, collected by Endre Szemerédi for what has become known as Szemerédi's theorem.