Tight Bounds for Arithmetic Progressions with Popular Common Differences in Dense Sets

A random subset with density alpha of an n-dimensional vector space over a finite field on p elements likely has about an alpha^3 fraction of the three-term arithmetic progressions with each nonzero common difference. Note that, for a subset of density alpha, the density of three-term arithmetic progressions can be much smaller than alpha^3. However, Green proved that for each epsilon>0 there is n_p(epsilon) such that if the dimension n of the vector space is at least n_p(epsilon), then there always exists a nonzero common difference d with three-term arithmetic progression density at least alpha^3-epsilon, what we expect from the random bound. The proof uses the arithmetic regularity lemma and gives a bound on n_p(epsilon) which is an exponential tower with height polynomial in 1/epsilon.

We provide a construction which shows that n_p(epsilon) is at least a tower with height logarithmic in 1/epsilon when epsilon is small, and prove a matching upper bound up to constant factor in the tower height. This gives the first natural application of a regularity lemma where the tower type bound is really necessary. Tight bounds are also obtained for other ranges of epsilon (in terms of the density alpha).

This is joint work with Jacob Fox and Yufei Zhao.