Patterns without a popular difference

Patterns without a popular difference, Discrete Analysis 2021:8, 30 pp.

Szemerédi’s theorem states that for every \(\delta>0\) and every positive integer \(k\) there exists \(N\) such that every subset \(A\subset[N]\) of size at least \(\delta N\) contains an arithmetic progression of length \(k\). From this theorem one can deduce by an averaging argument (first observed by Varnavides) that there exists a constant \(c=c(\delta,k)>0\) such that for every \(N\) the number of arithmetic progressions in a subset of \(N\) of size at least \(\delta N\) must be at least \(cN^2\). (For convenience, so that the result is true for all \(N\) rather than just for all sufficiently large \(N\), we include degenerate arithmetic progressions, that is, progressions for which the common difference is zero.)

A simple observation that is very useful for guiding intuition is that if \(A\) is a set of size \(\delta N\) chosen randomly, then the number of arithmetic progressions of length \(k\) is with high probability approximately equal to \(\delta^k\) times the total number of progressions of length \(k\) in \([N]\), and indeed that for each \(d>0\) (provided it is not too close to \(N/(k-1)\)) the same is true of the number of progressions of common difference \(d\).

If \(d\) is such that the number of progressions in \(A\) of length \(k\) and common difference \(d\) is at least \((\delta^k-o(1))|A|\), then we can call it a popular common difference. With the help of the arithmetic regularity lemma that he had developed, Ben Green proved that when \(k=3\), popular common differences always exist. (As an aside, we note that this led to tower-type bounds, which turned out, very interestingly, to be necessary. See this editorial introduction for more discussion.) With Terence Tao, he later proved the same for \(k=4\), but surprisingly the result is false for \(k\geq 5\), a counterexample having been discovered by Imre Ruzsa.

This paper considers, and completely answers, the following natural generalization of the question above. For which finite subsets \(P\) of \(\mathbb Z^r\) is it the case that for every \(\delta>0\) and every \(A\subset[N]^r\) there exists some \(d\ne 0\) such that the number of translates of \(d\cdot P\) that lie inside \(A\) is at least \((\delta^{|P|}-o(1))N^r\)? (Here \(d\cdot P\) denotes the dilate of \(P\) by a factor \(d\).) The answer turns out to be that the only examples are subsets of \(\mathbb Z\) of size 3 and subsets of \(\mathbb Z\) of size 4 such that the sum of two elements is equal to the sum of the other two. That these are examples follows from the proofs of Green, and Green and Tao, so the short answer is that there are no further examples. Thanks to previous work, it was already known that any example would have to have size 4 and be a subset of \(\mathbb Z\) or \(\mathbb Z^2\).

There is, however, a further distinction that can be drawn. For some configurations \(P\) one can at least prove that there is a constant \(C\) such that there is a difference \(d\) such that the number of translates of \(d\cdot P\) is at least \(\delta^CN^r\), and for others it can be proved that there is no such constant. Amongst other results, the authors show that there are configurations of size 4 in \(\mathbb Z^2\) for which there is no power-type lower bound, and that for every \(C\) there is a subset \(P\) of \(\mathbb Z\) of size 4 and a set \(A\subset[N]\) such that the number of translates of \(d\cdot P\) inside \(A\) is at most \(\delta^CN\) for every \(d>0\).

The work of this paper also has a bearing on another problem that has been open for some time. Let \(A\) be a subset of \(\mathbb Z/N\mathbb Z\) that is uniform, in the sense that all its non-trivial Fourier coefficients are small. Timothy Gowers gave examples of such sets \(A\) of size \(\delta N\) such that \(A^4\) contains at most \(\alpha N^2\) quadruples of the form \((x,x+y,x+2y,x+3y)\), with \(\alpha\) strictly less than \(\delta^4\). However, it is unknown whether \(\alpha\) can be taken to be \(\delta^C\) for an arbitrarily large \(C\). The example just mentioned shows that for every \(C\) there is a configuration \(P\) of size 4 and a Fourier-uniform set that gives rise to an upper bound of \(\delta^C\).