Quantitative bounds in the polynomial Szemerédi theorem: the homogeneous case

Quantitative bounds in the polynomial Szemerédi theorem: the homogeneous case, Discrete Analysis 2017:5, 34 pp.

Szemerédi’s theorem, proved in 1975, asserts that for every positive integer \(k\) and every \(\delta>0\) there exists \(n\) such that every subset \(A\) of \(\{1,2,\dots,n\}\) of cardinality at least \(\delta n\) contains an arithmetic progression of length \(k\). This apparently simple statement turns out to be surprisingly hard to prove, though it now has many different proofs and has become a hugely influential result in additive and extremal combinatorics.

In 1996, Bergelson and Leibman proved a far-reaching extension of Szemerédi’s theorem, which states the following. Let \(P_1,\dots,P_k\) be polynomials that take integer values at the integers and have no constant terms. Then for every \(\delta>0\) there exists \(n\) (which depends on \(\delta\) and the polynomials \(P_1,\dots,P_k\)) such that for every subset \(A\) of \(\{1,\dots,n\}\) of cardinality at least \(\delta n\) there exist positive integers \(a,d\) such that \(a+P_1(d),\dots,a+P_k(d)\) all belong to \(A\). This is a huge common generalization of Szemerédi’s theorem, which is the case \(P_i(d)=(i-1)d\), and a theorem of Furstenberg and Sárközy, which is the case \(P_1(d)=0\) and \(P_2(d)=d^2\), so it tells us that a dense subset of \(\{1,2,\dots,n\}\) must contain two elements that differ by a perfect square.

Szemerédi’s proof of Szemerédi’s theorem was an intricate combinatorial argument that led to a very weak bound – indeed, so weak that it has not been explicitly calculated. So although it is in principle quantitative, in effect it is a qualitative statement. In 1977 Furstenberg gave a new proof using ergodic theory, which led to many extensions of the theorem, including that of Bergelson and Leibman, but these methods were ineffective by their very nature, so did not provide bounds. (Tao later found a quantitative version of Furstenberg’s proof that did give bounds, though once again they were very weak.) The first reasonable bound was due to Gowers, who gave a bound for \(n\) with a doubly exponential dependence on a power of \(1/\delta\), the power depending on \(k\) in such a way that the dependence on \(k\) for fixed \(\delta\) is quintuply exponential.

For a long time, the only cases of the Bergelson-Leibman theorem for which reasonable bounds were known were those where the configurations being sought were of the form \(\{a,a+P(d)\}\). In 2002, Green obtained quantitative bounds for the related problem where the forbidden configurations are those of the form \(\{a,a+d_1^2+d_2^2,a+2(d_1^2+d_2^2)\}\), and there matters stood for some time. In 2013, Tao wrote an interesting blog post in which he described an approach that he had discovered with Green and Ziegler a few years earlier for proving the Furstenberg-Sárközy theorem without using Fourier analysis but still obtaining quantitative bounds.

This paper obtains quantitative bounds in the homogeneous case of the problem: that is, the case where the polynomials \(P_1,\dots,P_k\) are homogeneous of the same degree, which includes many of the most interesting examples. The approach is along broadly similar lines to the approach of Green, Tao and Ziegler, but the argument is much more complicated: it involves delving into the details of Gowers’s proof of Szemerédi’s theorem and using “local \(U_k\) norms” that were introduced by Tao and Ziegler in order to prove a polynomial generalization of the Green-Tao theorem. The simplest previously unknown case is that of arithmetic progressions of length 3 and square common difference – that is, the case where we are looking for configurations of the form \((a,a+d^2,a+2d^2)\). Here the result of the paper gives a bound of the form \(n=\exp\exp(\delta^{-C})\). In fact, the same sort of bound holds in general, but the dependence of \(C\) on the polynomials is not given explicitly, though the methods of the paper could probably be used to give an explicit dependence for anybody sufficiently patient to keep track of all the constants in the argument.