The Number of Subsets of Integers with No k -Term Arithmetic Progression

Addressing a question of Cameron and Erdos, we show that, for infinitely many values of n, the number of subsets of {1, 2, . . . ,n} that do not contain a k-term arithmetic progression is at most 2O(rk(n)), where rk(n) is the maximum cardinality of a subset of {1, 2, . . . ,n} without a k-term arithmetic progression. This bound is optimal up to a constant factor in the exponent. For all values of n, we prove a weaker bound, which is nevertheless sufficient to transfer the current best upper bound on rk(n) to the sparse random setting. To achieve these bounds, we establish a new supersaturation result, which roughly states that sets of size (rk(n)) contain superlinearly many k-term arithmetic progressions. For integers r and k, Erdos asked whether there is a set of integers S with no (k + 1)-term arithmetic progression, but such that any r-coloring of S yields a monochromatic k-term arithmetic progression. Nešetřil and Rodl, and independently Spencer, answered this question affirmatively. We show the following density version: for every k ≥ 3 and δ > 0, there exists a reasonably dense subset of primes S with no (k + 1)-term arithmetic progression, yet every U ⊆ S of size |U| ≥ δ|S| contains a k-term arithmetic progression. Our proof uses the hypergraph container method, which has proven to be a very powerful tool in extremal combinatorics.