A Quantitative Bound For Szemerédi’s Theorem for a Complexity One Polynomial Progression over ℤ/Nℤ

A quantitative bound For Szemerédi’s theorem for a complexity one polynomial progression over $\mathbb Z/N\mathbb Z$, Discrete Analysis 2024:3, 33 pp.

One of the central results of additive combinatorics, Szemerédi’s theorem, asserts that for every $\delta>0$ and every positive integer $k$ there exists a positive integer $n$ such that every subset of $\{1,2,\dots,n\}$ of size at least $\delta n$ contains an arithmetic progression of length $k$. A remarkable “polynomial extension” of Szemerédi’s result, due to Bergelson and Leibman, asserts that for every $\delta>0$ and every $k$-tuple of polynomials $P_1,\dots,P_k$ that have integer coefficients and vanish at zero, there exists a positive integer $n$ such that every subset of $\{1,2,\dots,n\}$ has a subset of the form $\{a+P_1(d),\dots,a+P_k(d)\}$ with $d\ne 0$. Setting $P_i(d)=id$ (or $(i-1)d$ if you prefer) yields Szemerédi’s theorem, and setting $P_1(d)=0$ and $P_2(d)=d^r$ for some positive integer $r$ yields a well-known theorem of Furstenberg and Sárközy, but the Bergelson-Leibman theorem vastly generalizes both these results, and allows one to find configurations such as $\{a,a+d,a+2d,a+d^3\}$ in any dense subset of $\{1,2,\dots,n\}$ as long as $n$ is sufficiently large.

The proof of Bergelson and Leibman used ergodic theory and therefore gave no bounds at all (though in principle it would, with sufficient effort, be possible to extract an explicit but very weak bound). There has therefore been considerable interest in finding reasonable quantitative bounds, where typically “reasonable” means that $n$ is bounded above by an iterated exponential function of $1/\delta$, where the number of iterations depends only on the polynomials $P_1,\dots,P_k$.

The first bound of this type for Szemerédi’s theorem was obtained by Gowers, who showed that one could take $n$ to be doubly exponential in a power of $1/\delta$ (where that power was itself doubly exponential in $k$). A recent result of the author, proved with Ashwin Sah and Mehtaab Sawhney, has improved this bound to one that is doubly exponential in a power of $\log(1/\delta)$.

For the configuration $\{a,a+d^2\}$ the best known bound, after a sequence of previous bounds that began with the proof of Sárközy, is $\exp\exp(O(\log(1/\delta)/\log\log(1/\delta)))$. This was shown by Thomas Bloom and James Maynard. It is a major open problem whether a bound of $(1/\delta)^C$ is possible.

For more general polynomial configurations, much of our knowledge is contained in results of Sarah Peluse and Sean Prendiville. For example, they have proved that for the configuration $\{a,a+d,a+d^2\}$ one can take $n$ to be exponential in a power of $1/\delta$, and more generally, Peluse has obtained a doubly exponential bound in a power of $1/\delta$ for any instance of the Bergelson-Leibman theorem where the polynomials have distinct degrees.

Central to these arguments was a technique of Peluse known as a degree-lowering argument. The rough idea is to establish first that the count of polynomial configurations associated with a function $f$ can be controlled by its $U^s$ norm $\|f\|_{U^s}$ for some $s$ that depends just on the polynomials, and then to use a detailed understanding of what happens on shorter progressions to deduce control by the $U^{s-1}$ norm. Iterating this, one arrives at control by the $U^2$ norm or even the $U^1$ norm, which allows one to use Fourier analysis in a straightforward way.

The assumption that the polynomials have different degree is crucial to getting the above strategy to work. In this paper, the author considers some cases where the polynomials do not have that property. The main result of the paper is that if one takes the configuration $\{a,a+P(d),a+Q(d),a+P(d)+Q(d)\}$ for two linearly independent polynomials $P$ and $Q$ that vanish at zero, then one can obtain a bound for $n$ that is an iterated exponential in $1/\delta$, where the number of iterations depends on $P$ and $Q$.

As commented above, Peluse’s degree-lowering strategy does not work in this case. However, the author adapts the strategy to a higher-order version, replacing Peluse’s appeals to Fourier analysis by appeals to a result of Green and Tao known as the inverse theorem for the $U^3$ norm.

The proofs are technically demanding, but they break new ground and are likely to lead to further progress in the general project of understanding the quantitative aspects of the Bergelson-Leibman theorem.