---
abstract: 'We show that sets of integers lacking the configuration $x$, $x+y$, $x+y^2$ have at most polylogarithmic density.'
address:
- |
    Mathematical Institute\
    University of Oxford\
    UK
- |
    Department of Mathematics and Statistics\
    Lancaster University\
    UK
author:
- Sarah Peluse
- Sean Prendiville
bibliography:
- '/Users/sean/Dropbox/SeanBib.bib'
title: A polylogarithmic bound in the nonlinear Roth theorem
---

Introduction
============

Statement of results
--------------------

In [@PelusePrendivilleQuantitative] the authors obtained, for the first time, an effective bound for subsets of ${\left\{1, \dots, N\right\}}$ lacking the nonlinear Roth configuration $x$, $x+y$, $x+y^2$. There it was established that such sets have cardinality at most $O(N/(\log\log N)^c)$, where $c> 0$ is an absolute constant. The key breakthrough of [@PelusePrendivilleQuantitative] was a “local $U^1$-control” result, from which a bound for sets lacking the nonlinear Roth configuration follows via standard methods. Here, we combine this local $U^1$-control result with a more sophisticated argument to remove a logarithm from the bound of [@PelusePrendivilleQuantitative].

\[main\] There exists an absolute constant $c > 0$ such that the following holds. Suppose that $A \subset {\left\{1,\dots, N\right\}}$ lacks configurations of the form $$\label{main config}
x,\ x+y, \ x+y^2 \qquad (y \neq 0).$$ Then$$|A| = O\left( N/(\log N)^{c}\right).$$

A careful analysis shows that the exponent $c = 2^{-150}$ is permissible, where 150 represents the combined number of times we utilise the Cauchy–Schwarz inequality in [@PelusePrendivilleQuantitative] and this paper

We also show, in a quantitatively effective manner, that the major arc Fourier coefficients of a set determine how many nonlinear Roth configurations the set contains.

\[global control\] Let $\delta > 0$ and $f, g, h : {\mathbb{Z}}\to {\mathbb{C}}$ be 1-bounded functions with support in ${\left\{1, \dots, N\right\}}$. Suppose that $${\left| \sum_{x\in{\mathbb{Z}}}\sum_{ y\in {\mathbb{N}}} f(x) g(x+y)h(x+y^2) \right|}{\geqslant}\delta N^{3/2}.$$ Then either $N \ll \delta^{-O(1)}$, or there is a frequency $\alpha \in {\mathbb{R}}$ and a positive integer $q \ll \delta^{-O(1)}$ such that[^1] ${\left\| q\alpha\right\|} \ll \delta^{-O(1)}/N$ and $${\left| \sum_{x\in {\mathbb{Z}}} h(x)e(\alpha x) \right|} \gg \delta^{O(1)} N.$$

In the nomenclature of [@TaoObstructions], the major arc linear phases are the only obstructions to uniformity for the nonlinear Roth configuration.

The major arc Fourier coefficients of a subset of $\{1,\dots,N\}$ essentially measure its distribution in arithmetic progressions of common difference $\ll 1$ and length $\gg N$. To illustrate this, the following definition is useful.

\[local function def\] We call a function $\phi : {\mathbb{Z}}\to {\mathbb{C}}$ a *local function of resolution $M$ and modulus $q$* if there exists a partition of ${\mathbb{Z}}$ into intervals of length $M$ such that $\phi$ is constant on the intersection of every such interval with every congruence class mod $q$.

\[global control cor\] Let $\delta > 0$ and $f, g, h : {\mathbb{Z}}\to {\mathbb{C}}$ be 1-bounded functions with support in ${\left\{1, \dots, N\right\}}$. Suppose that $${\left| \sum_{x\in{\mathbb{Z}}}\sum_{ y\in {\mathbb{N}}} f(x) g(x+y)h(x+y^2) \right|}{\geqslant}\delta N^{3/2}.$$ Then either $N \ll \delta^{-O(1)}$, or there is a 1-bounded local function $\phi $ of resolution $\gg \delta^{O(1)} N$ and modulus $q \ll \delta^{-O(1)}$ such that $${\left| \sum_{x\in {\mathbb{Z}}} h(x)\phi(x) \right|} \gg \delta^{O(1)} N.$$

One cannot hope to prove that the functions $f$ and $g$ above also correlate globally with local functions, as the following example illustrates. For any positive integers $x_1, x_2 {\leqslant}N^{1/2}$, set $$f{\left( x_1 + (x_2-1){\left\lfloor N^{1/2} \right\rfloor} \right)} = \begin{cases} 
        1 & \text{ if } x_2 \equiv 0 \pmod 4,\\
        0 & \text{ if } x_2 \equiv 1 \pmod 4,\\ 
        -1 & \text{ if } x_2 \equiv 2 \pmod 4,\\
        0 & \text{ if } x_2 \equiv 3 \pmod 4; \end{cases}$$ and set $f(x) = 0$ everywhere else. Taking $g := f$ and $h:=1_{\{1,\dots, N\}}$, one can check that either $N \ll 1$ or $$\sum_{x\in {\mathbb{Z}}}\sum_{y\in {\mathbb{N}}} f(x)g(x+y) h(x+y^2) \gg N^{3/2}.$$ However, for any arithmetic progression $P\subset\{1, \dots, N\}$, we have $${\left| \sum_{x \in P} f(x)\right|} \ll N^{1/2}.$$ Hence, for any local function $\phi$ of resolution ${\geqslant}\delta N$ and modulus ${\leqslant}\delta^{-1}$, the triangle inequality gives the discorrelation $${\left| \sum_{x \in {\mathbb{Z}}} f(x) \phi(x)\right|} \ll \delta^{-2} N^{1/2}.$$

This example is a local obstruction coming from the real numbers: the nature of our counting operator means that we cannot disentangle possible correlations between the $f$ and $g$ functions on subintervals of length $N^{1/2}$. We can, however, show that these are the only other possible obstructions to uniformity.

\[local control\] Let $\delta > 0$ and $f_1, f_2, f_3 : {\mathbb{Z}}\to {\mathbb{C}}$ be 1-bounded functions with support in ${\left\{1, \dots, N\right\}}$. Suppose that $${\left| \sum_{x\in{\mathbb{Z}}}\sum_{ y\in {\mathbb{N}}} f_1(x) f_2(x+y)f_3(x+y^2) \right|}{\geqslant}\delta N^{3/2}.$$ Then either $N \ll \delta^{-O(1)}$, or for each $i=1,2,3$ there is a 1-bounded local function $\phi_i$ of resolution $\gg \delta^{O(1)} N^{1/2}$ and modulus $q_i \ll \delta^{-O(1)}$ such that $${\left| \sum_{x\in {\mathbb{Z}}} f_i(x)\phi_i(x) \right|} \gg \delta^{O(1)} N.$$

Longer polynomial progressions {#longer intro}
------------------------------

In analogy with the first author’s generalisation [@PeluseBounds] of [@PelusePrendivilleQuantitative], it is natural to ask whether the methods of this paper yield polylogarithmic bounds for sets of integers lacking longer progressions $$\label{longer}
x,\ x+ P_1(y), \ \dots, \ x + P_m(y),$$ where the $P_i \in {\mathbb{Z}}[y]$ have zero constant term and $\deg P_1 < \dots < \deg P_m$.

As was mentioned above, the key input to this paper is the local $U^1$-control result [@PelusePrendivilleQuantitative Theorem 7.1]. Replacing this with [@PeluseBounds Theorem 3.3], our argument generalises in a straightforward manner to yield polylogarithmic bounds for subsets of $\{1,\dots,N\}$ lacking when $m = 2$, that is, for all three-term polynomial progressions with distinct degrees and zero constant term.

Obtaining polylogarithmic bounds for longer polynomial progressions requires an additional idea. We sketch a strategy in §\[longer section\], which relies on obtaining an appropriate generalisation of [@PeluseBounds Theorem 3.3], a generalisation that would require re-running the majority of the arguments therein.

Acknowledgements {#acknowledgements .unnumbered}
----------------

S. Peluse is supported by the NSF Mathematical Sciences Postdoctoral Research Fellowship Program under Grant No. DMS-1903038

An outline of our argument {#sec3}
--------------------------

Effective Szemerédi-type theorems are commonly proved via a density increment strategy, the prototypical example being the proof of Roth’s theorem [@RothCertainI] on three-term arithmetic progressions. This strategy begins with a set $A \subset \{1, \dots, N\}$ of density $\delta := |A|/N$ that lacks the configuration in question. It then proceeds to show that there is a substructure $S \subset \{1, \dots, N\}$ on which $A$ has increased density $\delta + \Omega_\delta(1)$. One then hopes to iterate the argument with $A \cap S$ in place of $A$ and $S$ in place of $\{1, \dots, N\}$.

One avenue to obtaining polylogarithmic bounds in a Szemerédi-type theorem is to obtain a constant proportion density increment $\delta + \Omega(\delta)$ on a substructure $S$ of polynomial size $|S| \approx N^{\Omega(1)}$. This was accomplished for three-term arithmetic progressions by Heath–Brown [@HeathBrownInteger] and Szemerédi [@SzemerediInteger] (in fact, they were able to handle a smaller lower bound on $|S|$).

An alternative strategy for obtaining polylogarithmic bounds is to obtain the weaker polynomial increment $\delta + \Omega(\delta^{O(1)})$, yet on a *dense* or *global* substructure $S$, that is, a substructure of size $|S| {\geqslant}\exp(-O(\delta^{-O(1)})) N$. This was accomplished by Sárközy [@SarkozyDifferenceI] for the configuration $x, x+y^2$ and for three-term arithmetic progressions by Bourgain [@BourgainTriples].

Both of these strategies are achievable for the nonlinear Roth configuration. The global structure strategy is perhaps the most natural, and may be accomplished by utilising a generalisation of Theorem \[global control\]. In this note we do not pursue this, and instead give details for a constant-proportion density increment, as our argument is somewhat cleaner in this form.

More specifically, we show that if $A \subset {\left\{1,\dots, N\right\}}$ has density $\delta$ and lacks nontrivial configurations of the form $x, x+y, x+y^2$, then there exists an arithmetic progression $P$ of length $|P| \gg \delta^{O(1)} N^{1/2}$ and common difference $q \ll \delta^{-O(1)}$ such that we have the density increment $$\label{constant proportion}
\frac{|A\cap P|}{|P|} {\geqslant}(1+\Omega(1)) \frac{|A|}{N}.$$ As outlined in [@PelusePrendivilleQuantitative], the ‘almost bounded’ size of $q$ allows us to iterate this procedure. (In [@PelusePrendivilleQuantitative], we obtain the weaker density increment $(1+\Omega(\delta^{O(1)}))|A|/N$, which leads to the extra logarithm appearing in the bound there.)

We obtain the constant-proportion increment by combining the local $U^1$-control result of [@PelusePrendivilleQuantitative] with a strategy of Heath–Brown [@HeathBrownInteger] and Szemerédi [@SzemerediInteger], which has a very robust formulation due to Green and Tao [@GreenTaoNewII]. To accomplish this, we first give a structural characterisation of sets lacking the nonlinear Roth configuration (Theorem \[local control\]). These sets resemble the level sets of the product of a function that is constant on intervals of length $N^{1/2}$ and a function that is constant on congruence classes modulo a bounded $q$.

Having obtained such a structural characterisation, an energy increment procedure closely following [@GreenTaoNewII] allows us to approximate an arbitrary set of integers by these level sets, up to an error that does not contribute substantially to the count of nonlinear Roth configurations. A combinatorial argument then allows us to deduce that our set must have a substantial density increment on one of these level sets, of the form $\delta + \Omega(\delta)$. As a result, our density increment procedure requires only $\log(\delta^{-1})+O(1)$ iterations, compared with the $O(\delta^{-O(1)})$ required in [@PelusePrendivilleQuantitative], and this yields the polylogarithmic improvement over our previous density increment iteration.

The remainder of this paper is organized as follows. We derive Theorem \[main\] in §\[increment sec\] via a density increment iteration. Our deduction uses a density increment lemma that is established in §§\[inverse theorem section\]–\[increment proof sec\]. We prove Theorem \[global control\] and Corollary \[global control cor\] in §\[global sec\]. Theorem \[local control\] will follow from combining Lemma \[partial inverse theorem\] with Corollary \[global control cor\].

Notation
--------

### Standard conventions

We use ${\mathbb{N}}$ to denote the positive integers. For a real number $X {\geqslant}1$, write $[X] = \{ 1,2, \ldots, {\left\lfloor X \right\rfloor}\}$. A complex-valued function is said to be *1-bounded* if the modulus of the function does not exceed 1.

We use counting measure on ${\mathbb{Z}}$, so that for $f,g :{\mathbb{Z}}\to {\mathbb{C}}$, we have $${\left\| f\right\|}_{\ell^p} := {\biggl( \sum_x |f(x)|^p \biggr)}^{{\frac{1}{p}}}, \ {\left\langlef,g\right\rangle} := \sum_x f(x)\overline{g(x)},\ \text{and}\ (f*g)(x) = \sum_y f(y)g(x-y).$$ Any sum of the form $\sum_x$ is to be interpreted as a sum over ${\mathbb{Z}}$. The *support* of $f$ is the set ${\mathrm{supp}}(f) := {\left\{x \in {\mathbb{Z}}: f(x) \neq 0\right\}}$. We write ${\left\| f\right\|}_\infty$ for $\sup_{x \in {\mathbb{Z}}} |f(x)|$.

We use Haar probability measure on ${\mathbb{T}}:= {\mathbb{R}}/{\mathbb{Z}}$, so that for measurable $F : {\mathbb{T}}\to {\mathbb{C}}$, we have $${\left\| F\right\|}_{L^p} := {\biggl( \int_{\mathbb{T}}|F(\alpha)|^pd\alpha \biggr)}^{{\frac{1}{p}}} = {\biggl( \int_0^1 |F(\alpha)|^pd\alpha \biggr)}^{{\frac{1}{p}}}.$$ We write ${\left\| \alpha\right\|}_{\mathbb{T}}$ for the distance from $\alpha \in {\mathbb{R}}$ to the nearest integer $
\min_{n \in {\mathbb{Z}}} |\alpha - n|.
$ This remains well-defined on ${\mathbb{T}}$.

We define the Fourier transform of $f : {\mathbb{Z}}\to {\mathbb{C}}$ by $$\label{Fourier transform}
\hat{f}(\alpha) := \sum_x f(x) e(\alpha x) \qquad (\alpha \in {\mathbb{T}}),$$ when this makes sense. Here $e(\alpha)$ stands for $e^{2\pi i \alpha}$.

For a finite set $S$ and function $f:S\to{\mathbb{C}}$, denote the average of $f$ over $S$ by $${\mathbb{E}}_{s\in S}f(s):=\frac{1}{|S|}\sum_{s\in S}f(s).$$

If $\|\cdot\|$ is a seminorm on an inner product space, recall that its dual seminorm $\|\cdot\|^*$ is defined by $$\label{dual norm}
\|f\|^{*}:=\sup_{\|g\|{\leqslant}1}|\langle f,g\rangle|.$$ Hence, $$\label{dual ineq}
{\left| {\left\langlef,g\right\rangle}\right|} {\leqslant}{\left\| f\right\|}^* {\left\| g\right\|}.$$

For a complex-valued function $f$ and positive-valued function $g$, write $f \ll g$ or $f = O(g)$ if there exists a constant $C$ such that $|f(x)| \le C g(x)$ for all $x$. We write $f = \Omega(g)$ if $f \gg g$.

### Local conventions

Up to normalisation, all of the above are well-used in the literature. Next, we list notation specific to our paper. We have tried to minimise this in order to aid the casual reader.

The quantity $(N/q)^{1/2}$ appears repeatedly, where $N$ and $q$ are integers fixed throughout the majority of our paper. We therefore adopt the convention that $$\label{M def}
M:= {\left\lfloor \sqrt{N/q} \right\rfloor}.$$ Assuming this, define the *counting operator* on the functions $f_i : {\mathbb{Z}}\to {\mathbb{C}}$ by $$\label{counting op}
\Lambda_{q, N}(f_0, f_1, f_2) := {\mathbb{E}}_{x \in [N]} {\mathbb{E}}_{y \in [M]} f_0(x)f_1(x+y) f_2(x+qy^2).$$ When the $f_0=f_1=f_2=f$, we simply write $\Lambda_{q, N}(f)$ for $\Lambda_{q,N}(f_0,f_1,f_2)$.

For a real parameter $H {\geqslant}1$, we use $\mu_H : {\mathbb{Z}}\to [0,1]$ to represent the following normalised Fejér kernel $$\label{fejer}
\mu_H(h) := {\frac{1}{{\left\lfloor H \right\rfloor}}} {\left( 1 - \frac{|h|}{{\left\lfloor H \right\rfloor}} \right)}_+ = \frac{(1_{[H]} * 1_{-[H]} )(h)}{{\left\lfloor H \right\rfloor}^2}.$$ This is a probability measure on ${\mathbb{Z}}$ with support in the interval $(-H, H)$.

Iterating the density increment {#increment sec}
===============================

In this section we prove Theorem \[main\] using the following lemma, which we will devote §§\[inverse theorem section\]–\[increment proof sec\] to proving.

\[increment lemma\] Let $q {\leqslant}N$ be positive integers and $\delta > 0$. Suppose that $A \subset [N]$ satisfies $|A| {\geqslant}\delta N$ and lacks the configuration $$\label{q config}
x,\ x+y, \ x+qy^2 \qquad (y \neq 0).$$ Then either $N \ll (q/\delta)^{O(1)}$ or there exists $q' {\leqslant}\exp{\left( O{\left( \delta^{-O(1)} \right)} \right)}$ and $N' {\geqslant}q^{-O(1)}\exp{\left( -O{\left( \delta^{-O(1)} \right)} \right)}N^{1/2} $ such that $$\label{increment}
 |A \cap (a + qq'\cdot[N'])| {\geqslant}(1+\Omega(1))\delta N'.$$

This is the same as the proof of [@PelusePrendivilleQuantitative Theorem 1.1], but using the improved density increment lemma above in place of the density increment lemma of [@PelusePrendivilleQuantitative]. Note first that if $A$ lacks the configuration , then the set $$\{x :a+qq'x\in A\},$$ lacks configurations of the form $$x,\ x+y,\ x+q^2q'y^2 \qquad (y \neq 0).$$

Let $A \subset [N]$ have size $\delta N$, and suppose that it has no non-linear Roth configurations . Setting $A_0 := A$, $N_0 := N$ and $q_0 = 1$, let us suppose we have a sequence of tuples $(A_i, N_i, q_i)$ for $i = 0, 1, \dots, n$ that each satisfy the following:

(i) $A_i$ lacks configurations of the form $$x,\ x+y,\ x+q_0^{2^i} q_1^{2^{i-1}}\dotsm q_{i-1}^2 q_i y^2 \qquad (y \neq 0).$$

(ii) \[qi upper bound\] $q_i {\leqslant}\exp{\left( O{\left( \delta^{-O(1)} \right)} \right)}$;

(iii) $A_i \subset [N_i]$ and for $i {\geqslant}1$ we have $$\frac{|A_i|}{N_i} {\geqslant}(1+c)\frac{|A_{i-1}|}{N_{i-1}},$$ where $c = \Omega(1)$ is a positive absolute constant;

(iv) \[length lower bound\] for $i {\geqslant}1$ we have the lower bound $$N_i {\geqslant}\frac{N_{i-1}^{1/2}}{{\left( q_0^{2^{i-1}}\dotsm q_{i-1}\exp{\left( \delta^{-O(1)} \right)} \right)}^{O(1)}}.$$

By Lemma \[increment lemma\], either $$\label{termination condition}
N_n \ll {\left( q_0^{2^n}q_1^{2^{n-1}}\dotsm q_{n-1}^2 q_n/\delta \right)}^{O(1)},$$ or we may obtain $(A_{n+1}, N_{n+1}, q_{n+1})$ satisfying conditions (i)–(iv). If holds, then our iterative process terminates at stage $n$.

If the number of iterations $n$ is at least $c^{-1}$, then the density of $A_n$ on $[N_n]$ is at least $2\delta$. After an additional ${\tfrac{1}{2}}c^{-1}$ iterations, the density is at least $4\delta$. Hence if the number of iterations is at least $${\left\lceil c^{-1} \right\rceil} + {\left\lceil {\tfrac{1}{2}}c^{-1} \right\rceil} + {\left\lceil {\tfrac{1}{4}}c^{-1} \right\rceil}+ \dots + {\left\lceil {\tfrac{1}{2^{m-1}}}c^{-1} \right\rceil},$$ then the density is at least $2^m\delta$. The density therefore exceeds one if the number of iterations exceeds $2c^{-1} + \log_2(\delta^{-1})$. Since this cannot happen, it follows that there exists $n {\leqslant}\log_2(\delta^{-1})+O(1)$ such that the procedure terminates at stage $n$.

At the point of termination, the smallness assumption must hold, so that $$\label{N_i upper bound}
N_n {\leqslant}\exp{\left( O{\Bigl( \delta^{-O(1)} \Bigr)} \right)}.$$ On the other hand, iteratively applying the lower bound , we have $$\label{N_i lower bound}
\begin{split}
N_n  & {\geqslant}\frac{N_{n-1}^{1/2}}{{\left( q_0^{2^{n-1}}\dotsm q_{n-1}\exp{\left( \delta^{-O(1)} \right)} \right)}^{O(1)}}\\
&  {\geqslant}N^{1/2^n}{\left[ q_0^{2^{n-1}}\dotsm q_{n-1}\exp{\left( \delta^{-O(1)} \right)} \right]}^{-O(1 + {\frac{1}{2}} + {\frac{1}{4}} + \dots + 2^{1-n}) } \\
& \gg \exp{\left( -O{\left( \delta^{-O(1)} \right)} \right)} N^{\Omega(\delta)},
\end{split}$$ where we use the upper bound on the $q_i$’s, together with $n {\leqslant}\log_2(1/\delta)+O(1)$. Taking a logarithm and comparing upper and lower bounds for $N_n$ gives $
\log N \ll \delta^{-O(1)},
$ which yields the bound claimed in Theorem \[main\].

The cut norm inverse theorem {#inverse theorem section}
============================

The first step of the proof of Lemma \[increment lemma\] is to use the main technical result of [@PelusePrendivilleQuantitative] to prove an inverse theorem for the cut norm associated to $\Lambda_{q,N}$, which we now define.

For positive integers $q {\leqslant}N$, we define the *cut norm* of $f : {\mathbb{Z}}\to {\mathbb{C}}$ by $$\label{q norm eq}
{\left\| f\right\|}_{q, N} := \sup\{|\Lambda_{q, N}(f, g_1,g_2)|,\ |\Lambda_{q, N}(g_1, f,g_2)|,\ |\Lambda_{q, N}(g_1,g_2, f)|\},$$ where the supremum is taken over all 1-bounded functions $g_i : [N] \to {\mathbb{C}}$. We note that, in spite of our nomenclature, this is not a norm, but a seminorm. One could remedy this by summing over $y {\geqslant}0$ in the counting operator

Initially, the cut norm is too restrictive for us, so we begin by working with the weaker quantity $$\label{flat q norm eq}
{\left\| f\right\|}^\flat_{q,N} := \sup\{|\Lambda_{q, N}(f, g_1,g_2)|, |\Lambda_{q, N}(g_1, f,g_2)| :  |g_i| {\leqslant}1 \text{ and } {\mathrm{supp}}(g_i) \subset [N] \},$$ which we refer to as the *partial cut norm*.

The following lemma is simply a rephrasing of [@PelusePrendivilleQuantitative Theorem 7.1], which is the technical heart of that paper. See Definition \[local function def\] for the meaning of ‘local function’.

\[partial inverse theorem\] Let $q {\leqslant}N$ be positive integers, $\delta>0$, and $f:{\mathbb{Z}}\to{\mathbb{C}}$ be a $1$-bounded function with support in $[N]$. Suppose that $${\left\| f\right\|}^\flat_{q,N}{\geqslant}\delta .$$ Then either $N \ll (q/\delta)^{O(1)}$ or there exists a 1-bounded local function $\phi$ of resolution $\gg (\delta/q)^{O(1)}N^{1/2}$, modulus $qq'$ for some $q'\ll  \delta^{-O(1)}$, and such that $$\sum_{x\in[N]} f(x)\phi(x) \gg \delta^{O(1)} N.$$

By compactness, there exist 1-bounded functions $g_1, g_2 : [N] \to {\mathbb{C}}$ such that either $
|\Lambda_{q, N}(f, g_1, g_2)| {\geqslant}\delta
$ or $
|\Lambda_{q, N}(g_1,f, g_2)| {\geqslant}\delta.
$ In the latter case, we may apply [@PelusePrendivilleQuantitative Theorem 7.1] to deduce that there exist positive integers $q'\ll\delta^{-O(1)}$ and $N' \gg (\delta/q)^{O(1)}N^{1/2}$ such that $$\sum_{x}{\left| \sum_{y\in[N']}f(x+qq'y)\right|}\gg \delta^{O(1)}NN'.$$ In the former case, the reader may check that the argument of [@PelusePrendivilleQuantitative Theorem 7.1] delivers the same conclusion[^2].

To ease notation, write $Q := qq'$. Partitioning the integers into arithmetic progressions of length $N'$ and common difference $Q$ gives $$\begin{gathered}
\delta^{O(1)} NN'  \ll \sum_{z \in [N']}\sum_{u\in [Q]} \sum_{x\in{\mathbb{Z}}} {\left| \sum_{y \in [N']} f( Qz +QN'x +u + Qy)\right|}\\  {\leqslant}N'\max_z\sum_{u\in [Q]} \sum_{x\in {\mathbb{Z}}} {\left| \sum_{y \in [N']} f(Qz + QN'x +u  +Qy)\right|}.\end{gathered}$$ Defining $ \psi_z(u,x)$ to be the conjugate phase of the inner sum, we deduce the existence of $z$ for which $$\begin{aligned}
\delta^{O(1)} N  \ll \sum_{u \in [Q]}\sum_x\sum_{y \in [N']}f(Qz + QN'x +u  +Qy)\psi_z(u,x).\end{aligned}$$ The result follows on noting that every integer has a unique representation of the form $QN'x +u  +Qy$ with $u \in [Q]$, $x \in {\mathbb{Z}}$ and $y \in [N']$. Hence the map $$Qz + QN'x +u  +Qy \mapsto \psi_z(u,x)$$ is a local function of resolution $QN'$ and modulus $Q$.

Now we can prove an inverse theorem for the cut norm itself.

\[inverse theorem\] Let $q {\leqslant}N$ be positive integers, $\delta>0$, and $f:{\mathbb{Z}}\to{\mathbb{C}}$ be a $1$-bounded function with support in $[N]$. Suppose that $${\left\| f\right\|}_{q,N}{\geqslant}\delta .$$ Then either $N \ll (q/\delta)^{O(1)}$ or there exist 1-bounded local functions $\phi_1$ and $\phi_2$, of resolution $\gg (\delta/q)^{O(1)}N^{1/2}$ and moduli $qq_1$ and $qq_2$, respectively, for some $q_1,q_2\ll  \delta^{-O(1)}$ such that $$\label{cut norm density increment}
{\left| \sum_{x\in[N]} f(x)\phi_1(x)\phi_2(x)\right|} \gg \delta^{O(1)} N.$$

A key tool in proving Lemma \[inverse theorem\] is the following decomposition result, which relies on the finite-dimensional Hahn–Banach theorem.

\[HB decomp\] Let $\|\cdot\|$ be a seminorm on the space of complex-valued functions with support in $[N]$. For any such function $f$ and ${\varepsilon}> 0$, there exists a decomposition $f=f_{str}+f_{unf}$ such that $${\left\| f_{str}\right\|}^* {\leqslant}{\varepsilon}^{-1}{\left\| f\right\|}_{2} \quad \text{and} \quad {\left\| f_{unf}\right\|}{\leqslant}{\varepsilon}{\left\| f\right\|}_{2}.$$

This can be found in the discussion following [@GowersDecompositions Proposition 3.6]. Although the statement therein is for norms, and not seminorms, one can check that the (simple) argument remains valid in this greater generality[^3].

Using the dual norm decomposition afforded by Lemma \[HB decomp\], we can gain control of every function in the counting operator.

By the definition of the cut norm and Lemma \[partial inverse theorem\], we may assume that there are 1-bounded functions $g, h : [N] \to {\mathbb{C}}$ such that $$|\Lambda_{q, N}(g, h, f)|  {\geqslant}\delta .$$ Applying Lemma \[HB decomp\] to $g$ with ${\left\| \cdot\right\|} := {\left\| \cdot\right\|}_{q, N}^\flat$ and ${\varepsilon}:= {\tfrac{1}{2}}\delta N^{-1/2}$, we deduce that $$|\Lambda_{q, N}(g_{str}, h,f)|    {\geqslant}\delta  -  |\Lambda_{q, N}(g_{unf}, h,f)|
 {\geqslant}\delta -  {\left\| g_{unf}\right\|}_{q, N}^\flat {\geqslant}\tfrac{\delta}{2} .$$

Recalling that $M := \lfloor\sqrt{N/q}\rfloor$, define the dual function $$F(x) : = {\mathbb{E}}_{y \in [M]} h(x+y) f(x+qy^2).$$ The dual inequality then gives $$\tfrac\delta2  {\leqslant}|\Lambda_{q, N}(g_{str}, h,f)| = N^{-1}|{\left\langleg_{str}, F\right\rangle}| {\leqslant}2 \delta^{-1} {\left\| F\right\|}_{q, N}^\flat.$$ Hence, by the partial cut norm inverse theorem (Lemma \[partial inverse theorem\]), there exists a 1-bounded local function $\phi_1$ of resolution $\gg (\delta/q)^{O(1)}N^{1/2}$ and modulus $qq_1$ for some $q_1\ll  \delta^{-O(1)}$ such that $${\left| \sum_{x\in[N]} F(x)\phi_1(x)\right|} \gg \delta^{O(1)} N.$$ Thus $$|\Lambda_{q, N}(\phi_1, h, f)|  \gg \delta^{O(1)} .$$

We now re-run our argument, this time applying Lemma \[HB decomp\] to $h$ and deducing the existence of a 1-bounded local function $\phi_2$ of resolution $\gg (\delta/q)^{O(1)}N^{1/2}$ and modulus $qq_2$ for some $q_2\ll  \delta^{-O(1)}$ such that $$|\Lambda_{q, N}(\phi_1, \phi_2, f)|  \gg \delta^{O(1)} .$$ Expanding the counting operator and taking a maximum over $y\in [M]$ gives $$\begin{aligned}
\delta^{O(1)} NM & \ll {\left| \sum_{y \in [M]}\sum_x f(x)\phi_1(x-qy^2) \phi_2(x-qy^2 + y)\right|}\\
&  {\leqslant}M {\left| \sum_x f(x)\tilde{\phi}_1(x) \tilde{\phi}_2(x)\right|},\end{aligned}$$ where both $\tilde{\phi}_i$ are 1-bounded local functions of resolution $\gg (\delta/q)^{O(1)}N^{1/2}$ and moduli $qq_i$ for some $q_i\ll \delta^{-O(1)}$.

A weak regularity lemma
=======================

Much of the material is this section is standard, and closely follows the expositions in Green [@GreenMontreal] and Green–Tao [@GreenTaoNewII]. To simplify the exposition of later arguments, while the factors in [@GreenMontreal] and [@GreenTaoNewII] are $\sigma$-algebras, our factors will be the set of atoms of certain $\sigma$-algebras (which can obviously be recovered by taking the $\sigma$-algebra generated by the set of atoms).

We define a *factor* $\mathcal{B}$ of $[N]$ to be a partition of $[N]$, so that $[N] = \sqcup_{B \in \mathcal{B}} B$. We say that a factor $\mathcal{B}'$ *refines* $\mathcal{B}$ if every element of $\mathcal{B}$ is a union of elements of $\mathcal{B}'$. The *join* $\mathcal{B}_1\vee\dots\vee\mathcal{B}_d$ of factors $\mathcal{B}_1, \dots, \mathcal{B}_d$ is the factor formed by taking the $d$-fold intersections of the elements of $\mathcal{B}_1$, …, $\mathcal{B}_d$, that is, $$\mathcal{B}_1\vee\dots\vee\mathcal{B}_d:=\{B_1\cap\dots\cap B_d:B_i\in\mathcal{B}_i\text{ for }i=1,\dots,d\}.$$

Given a factor $\mathcal{B}$, we say that a function $f : [N] \to {\mathbb{C}}$ is *$\mathcal{B}$-measurable* if it is constant on the elements of $\mathcal{B}$.

Define the *projection* of any function $f : [N] \to {\mathbb{C}}$ onto $\mathcal{B}$ by $$\label{conditional expectation}
\Pi_{\mathcal{B}} f(x) = \frac{\sum_{B \in \mathcal{B}} 1_B(x) \sum_{y \in B} f(y)}{\sum_{B \in \mathcal{B}} 1_B(x) \sum_{y \in B} 1_{[N]}(y)}.$$ Notice that $\Pi_{\mathcal{B}} f$ is $\mathcal{B}$-measurable, and is just the conditional expectation of $f$ with respect to the $\sigma$-algebra generated by the elements of $\mathcal{B}$.

We record some well-known properties of the projection operator $\Pi_{\mathcal{B}}$ (that is, properties of conditional expectation) in the next lemma.

\[properties\] [ ]{}

1.  \[projection part\] The operator $\Pi_{\mathcal{B}}$ linearly projects onto the space of $\mathcal{B}$-measurable functions.

2.  \[adjoint part\] $\Pi_{\mathcal{B}}$ is self-adjoint with respect to the inner product $${\left\langlef, g\right\rangle} := \sum_x f(x) \overline{g(x)} \qquad (f, g : [N] \to {\mathbb{C}}),$$ so that ${\left\langlef, \Pi_{\mathcal{B}}g\right\rangle} = {\left\langle\Pi_{\mathcal{B}} f, g\right\rangle}$.

3.  If $\mathcal{B}'$ is a refinement of $\mathcal{B}$ then $$\Pi_{\mathcal{B}'}\Pi_{\mathcal{B}}f  = \Pi_{\mathcal{B}}f. $$

4.  \[orthog part\] If $\mathcal{B}'$ refines $\mathcal{B}$ then $\Pi_{\mathcal{B}}f $ is orthogonal to $\Pi_{\mathcal{B}'}f  - \Pi_{\mathcal{B}}f $.

Inspecting the formula reveals that $\Pi_{\mathcal{B}}$ is linear, that $\Pi_{\mathcal{B}}f$ is constant on elements of $\mathcal{B}$, and that if $f$ itself is constant on elements of $\mathcal{B}$, then $\Pi_{\mathcal{B}}f = f$. This establishes .

Interchanging the order of summation gives $$\begin{split}
{\left\langlef, \Pi_{\mathcal{B}}g\right\rangle} = \sum_{B \in \mathcal{B}} |B|^{-1} \sum_{x,y \in B} f(x)\overline{g(y)} = {\left\langle\Pi_{\mathcal{B}}f, g \right\rangle}.
\end{split}$$ This proves that $\Pi_\mathcal{B}$ is self-adjoint.

The first refinement property follows from the fact that $\Pi_{\mathcal{B}} f$ is $\mathcal{B}'$-measurable.

We utilise self-adjointness of $\Pi_{\mathcal{B}}$ and the first refinement property to conclude that $$\begin{split}
{\left\langle\Pi_{\mathcal{B}} f  , \Pi_{\mathcal{B}} f- \Pi_{\mathcal{B}'} f\right\rangle}& = {\left\langle\Pi_{\mathcal{B}} f  , \Pi_{\mathcal{B}} f-  f\right\rangle} = {\left\langlef  , \Pi_{\mathcal{B}} f-  \Pi_{\mathcal{B}} f\right\rangle} = 0.
\end{split}$$

Now we describe the particular type of factors that will be relevant to us.

\[local factor def\] A *simple real factor* of resolution $M$ is a factor of $[N]$ obtained by partitioning ${\mathbb{R}}$ into intervals all of length $M$.

A *simple congruence factor* of modulus $q$ is the factor of $[N]$ obtained by partitioning into congruence classes mod $q$.

We say that $\mathcal{B}$ is a *simple local factor* of resolution $M$ and modulus $q$ if it is the join of a simple real factor of resolution $M$ and a simple congruence factor of modulus $q$. Notice that $\mathcal{B}$ is a simple local factor if and only if it consists of the level sets of a local function (Definition \[local function def\]) of resolution $M$ and modulus $q$.

A *local factor* of dimension $d$, resolution $M$ and modulus $q$ is the join of $d$ simple local factors $\mathcal{B}_i$, each of resolution $M_i$ and modulus $q_i$, where $M_i {\geqslant}M$ and $q = {\mathrm{lcm}}[q_1, \dots, q_d]$.

Local factors of large resolution and small modulus and dimension necessarily contain few sets. This fact will be useful later in the proof of Lemma \[increment lemma\].

\[atom bound\] If $\mathcal{B}$ is a local factor of dimension $d$, resolution $M$, and modulus $q$, then $$|\mathcal{B}| {\leqslant}qd{\left( \frac{N}{M} + 2 \right)}.$$

By the definition of a local factor, it suffices to bound the size of the join of $d$ simple real factors, and then bound the size of the join of $d$ simple congruence factors. The product of these two numbers gives us our final bound.

Joining $d$ congruence simple factors with moduli $q_1, \dots, q_d$ results in another congruence simple factor of modulus $q= {\mathrm{lcm}}[q_1, \dots, q_d]$. The number of parts in such a partition is $q$.

The join of $d$ simple real factors partitions $[N]$ into intervals. The upper endpoint of each of these intervals is either equal to $N$ or is equal to an endpoint of an interval in one of the original simple real factors. For a simple real factor of resolution $M$, at most $1+N/M$ upper endpoints lie in $[1, N)$. Hence the number of intervals in the join of $d$ simple real factors of resolutions $M_1$, …, $M_d$ is at most $2d + N(M_1^{-1} + \dots + M_d^{-1})$.

We now prove a weak regularity lemma for the cut norm via an energy increment argument.

\[weak regularity\] Let $q {\leqslant}N$ be positive integers and $\delta >0$. Either $N \ll (q/\delta)^{O(1)}$, or for any function $f : [N] \to [0, 1]$ there exists a local factor $\mathcal{B}$ of dimension $d \ll \delta^{-O(1)}$, resolution $\gg (\delta/q)^{O(1)}N^{1/2}$, and modulus $qq'$ for some $q'{\leqslant}O{\left( 1/ \delta \right)}^{O(d)}$ such that $$\label{proj error}
{\left\| f - \Pi_\mathcal{B} f\right\|}_{q, N} {\leqslant}\delta$$

We run an energy increment argument, initialising at stage $0$ with the trivial factor $\mathcal{B}_0 := {\left\{[N]\right\}}$. Suppose that at stage $d$ of this iteration we have a local factor $\mathcal{B}$ of resolution $ \gg (\delta/q)^{O(1)}N^{1/2}$, dimension at most $2d$, and modulus $qq'$ for some $q'{\leqslant}O(1/  \delta)^{O(d)}$. In addition, suppose that we have the energy lower bound $$\label{energy bound}
{\left\| \Pi_{\mathcal{B}} f\right\|}_{\ell^2}^2 \gg d\delta^{O(1)} N.$$

With these assumptions in place, we query if the following holds $$\label{query}
{\left\| f - \Pi_{\mathcal{B}}f\right\|}_{q, N} {\leqslant}\delta .$$ If so, then the process terminates. If not, we show how our iteration may proceed to stage $d+1$.

Applying the cut norm inverse theorem (Lemma \[inverse theorem\]), we conclude that there exist 1-bounded local functions $\phi_i$ of resolution $ \gg (\delta/q)^{O(1)}N^{1/2}$ and modulus $qq_i$ for some $q_i{\leqslant}\delta^{-O(1)}$ such that $${\left| {\left\langlef - \Pi_{\mathcal{B}}f, \phi_1\phi_2\right\rangle}\right|} = {\left| \sum_{x \in [N]} (f - \Pi_{\mathcal{B}}f)(x) \phi_1(x)\phi_2(x)\right|} \gg \delta^{O(1)} N.$$

Let $\mathcal{B}' $ denote the join of $\mathcal{B}$ and the simple local factors generated by $\phi_1$ and $\phi_2$, so that $\mathcal{B}'$ is a local factor of dimension at most $2(d+1)$, resolution $ \gg (\delta/q)^{O(1)}N^{1/2}$ and modulus $qq''$ for some $q'' {\leqslant}q'q_1q_2{\leqslant}O(1/\delta)^{O(d+1)}$. Since $\phi_1\phi_2$ is $\mathcal{B}'$-measurable, we can use the properties listed in Lemma \[properties\] together with the Cauchy–Schwarz inequality to deduce that $$\begin{split}
{\left| {\left\langlef- \Pi_{\mathcal{B}}f ,\phi_1\phi_2\right\rangle}\right|} & ={\left| {\left\langlef- \Pi_{\mathcal{B}}f ,\Pi_{\mathcal{B}'}(\phi_1\phi_2)\right\rangle}\right|} = {\left| {\left\langle\Pi_{\mathcal{B}'} f - \Pi_{\mathcal{B}} f , \phi_1\phi_2\right\rangle}\right|}\\
& {\leqslant}N^{1/2}  {\left\| \Pi_{\mathcal{B}'} f - \Pi_{\mathcal{B}}f \right\|}_{\ell^2}.
\end{split}$$ It follows that $${\left\| \Pi_{\mathcal{B}'} f - \Pi_{\mathcal{B}}f\right\|}_{\ell^2} \gg\delta^{O(1)} N^{1/2}.$$

Lemma \[properties\] tells us that $\Pi_{\mathcal{B}} f$ is orthogonal to $\Pi_{\mathcal{B}'}f -  \Pi_{\mathcal{B}} f$, hence by Pythagoras’s theorem $${\left\| \Pi_{\mathcal{B}'} f\right\|}_{\ell^2}^2 = {\left\| \Pi_{\mathcal{B}}f \right\|}_{\ell^2}^2+ {\left\| \Pi_{\mathcal{B}'} f- \Pi_{\mathcal{B}}f \right\|}_{\ell^2}^2.$$ The energy bound follows for $\mathcal{B}'$, allowing us to proceed to the next stage of our iteration.

Since the function $f$ is $1$-bounded, the projection $\Pi_\mathcal{B}f$ is also 1-bounded, hence the energy is always bounded above by $N$. It follows that this energy increment must terminate at stage $d$ for some $d \ll \delta^{-O(1)}$, yielding the lemma.

The density increment lemma {#increment proof sec}
===========================

In this section we prove Lemma \[increment lemma\], modelling our argument on that given by Green and Tao [@GreenTaoNewII Corollary 5.8]. We first record, for the sake of convenience, the following immediate consequence of the triangle inequality.

\[L1 control\] Suppose that $N {\geqslant}q$. Then for any $f_0, f_1, f_2 : [N]\to {\mathbb{C}}$ we have $$|\Lambda_{q, N}(f_0, f_1, f_2)| {\leqslant}N^{-1}{\left\| f_i\right\|}_{\ell^1} \prod_{j \neq i} {\left\| f_j\right\|}_\infty .$$

We prove the result for $i = 1$, the other cases being similar. A reparametrisation gives $$\begin{aligned}
{\left| \Lambda_{q, N}(f_0, f_1, f_2)\right|} &= {\left|  {\mathbb{E}}_{x\in[N]} f_1(x) {\mathbb{E}}_{y \in [M]} f_0(x-y)f_2(x+qy^2 - y)\right|}\\
 & {\leqslant}{\mathbb{E}}_{x\in[N]} |f_1(x)| {\mathbb{E}}_{y \in [M]} |f_0(x-y)||f_2(x+qy^2 - y)|.\end{aligned}$$

We are now in a position to prove Lemma \[increment lemma\], and thereby complete our proof of Theorem \[main\].

Let $A$ satisfy the assumptions of Lemma \[increment lemma\]. Increasing $\delta$ only strengthens our conclusion, so we may assume that $|A| = \delta N$. Since $\Lambda_{q, N}(1_A) = 0$, we have that $
{\left| \Lambda_{q, N}(1_A)  -\Lambda_{q, N}(\delta1_{[N]})\right|} =  \delta^3 \Lambda_{q, N}(1_{[N]}) \gg \delta^3
$.

Applying the weak regularity lemma (Lemma \[weak regularity\]), there exists a local factor $\mathcal{B}$ of dimension $d \ll \delta^{-O(1)}$, resolution $\gg (\delta/q)^{O(1)}N^{1/2}$, and modulus $qq'$ for some $q' {\leqslant}O(1/ \delta)^{O(d)}$ such that $${\left\| 1_A - \Pi_\mathcal{B} 1_A\right\|}_{q, N} {\leqslant}\tfrac{1}{6} \delta^3 \Lambda_{q, N}({1_{[N]}}).$$ Setting $f := \Pi_\mathcal{B} 1_A$, a telescoping identity thus yields $${\left| \Lambda_{q, N}(f)  -\Lambda_{q, N}(\delta1_{[N]})\right|} {\geqslant}{\tfrac{1}{2}}  \delta^3 \Lambda_{q, N}({1_{[N]}}) \gg \delta^3.$$

Define the $\mathcal{B}$-measurable set $$S:= {\left\{x \in [N] : f(x) {\geqslant}(1+c)\delta\right\}},$$ where $c>0$ is a sufficiently small absolute constant that will be chosen to make the following argument valid. By Lemma \[L1 control\] and a telescoping identity, we have ${\left| \Lambda_{q, N}(f)  -\Lambda_{q, N}(f1_{S^c})\right|} {\leqslant}3|S|/N$, so that $$\tfrac{|S|}{N} + {\left| \Lambda_{q, N}(f1_{S^c})  -\Lambda_{q, N}(\delta1_{[N]})\right|} \gg  \delta^3 .$$ Yet another telescoping identity, in conjunction with Lemma \[L1 control\], gives $$\begin{aligned}
{\left| \Lambda_{q, N}(f1_{S^c})  -\Lambda_{q, N}(\delta 1_{[N]})\right|} & \ll \tfrac{\delta^2 }{N}
{\left\| f1_{S^c}- \delta1_{[N]}\right\|}_{\ell^1} {\leqslant}\tfrac{\delta^2 }{N} {\left\| f - \delta1_{[N]}\right\|}_{\ell^1} + \tfrac{|S|}{N},\end{aligned}$$ so that $$|S| + \delta^2 {\left\| f - \delta1_{[N]}\right\|}_{\ell^1}  \gg \delta^3 N.$$

Since $f - \delta1_{[N]}$ has mean zero, its $\ell^1$-norm is equal to twice the $\ell^1$-norm of its positive part. The function ${\left( f - \delta1_{[N]} \right)}_+$ can only exceed $c \delta$ on $S$, so taking $c$ small enough gives $
|S| \gg \delta^3N
$. Letting $B$ denote the largest element of $\mathcal{B}$ for which $B \subset S$, the bound in Lemma \[atom bound\] yields $$|B| \gg q^{-O(1)}\delta^{O(d)} 2^{-O(d)} N^{1/2}.$$ By construction (see Definition \[local factor def\]), the set $B$ is an arithmetic progression of common difference $qq'$ with $q' {\leqslant}O(1/\delta)^{O(d)}$. Moreover, the density of $A$ on $B$ is equal to the value of $f(x)$ for any $x \in  B$, and this is at least $(1+c)\delta$ by the definition of $S$.

Global control by major arc Fourier coefficients {#global sec}
================================================

The purpose of this section is to prove Theorem \[global control\] and Corollary \[global control cor\]. We begin with an alternative version of Lemma \[partial inverse theorem\], replacing the rigid local function found therein with something more continuous. In the following, we say that $\phi : {\mathbb{Z}}\to {\mathbb{C}}$ is *$C$-Lipschitz along $q \cdot {\mathbb{Z}}$* if for any $x, y \in {\mathbb{Z}}$ we have $$|\phi(x+qy) - \phi(x)| {\leqslant}C |y|.$$ Recalling our definition for the Fejér kernel , we observe that a function of the form $$\label{h def}
x \mapsto \sum_h \mu_H(h) f(x+qh)$$ is Lipschitz along $q \cdot {\mathbb{Z}}$.

\[h lipschitz\] Let $q, H$ be positive integers and $f : {\mathbb{Z}}\to {\mathbb{C}}$ be 1-bounded. If $\phi$ is defined as in , then $\phi$ is $O(H^{-1})$-Lipschitz along $q \cdot {\mathbb{Z}}$, in that for any $x, y\in {\mathbb{Z}}$ we have $\phi(x+qy) = \phi(x) + O(|y|/H)$.

Recalling , the triangle inequality for $|\cdot|$ and $\max\{\cdot, 0\}$ show that $|\mu_H(h+y) - \mu_H(h)| {\leqslant}|y|/{\left\lfloor H \right\rfloor}^2$ for all $h, y \in {\mathbb{Z}}$. Hence a change of variables gives $$|\phi(x+qy) - \phi(x)|  {\leqslant}\sum_h |\mu_H(h-y) - \mu_H(h)| \ll \frac{|y|}{H^2}\sum_{h \in (-H, H)\cup(y-H, y+H) } 1.$$

Now we prove another partial cut norm inverse theorem, this time getting correlation with functions that are Lipschitz along progressions with small common difference.

\[partial inverse theorem II\] Let $N$ be a positive integer, $ \delta>0$, and $f, g, h:{\mathbb{Z}}\to{\mathbb{C}}$ be $1$-bounded functions with support in $[N]$. Suppose that $${\left| {\mathbb{E}}_{x \in [N]} {\mathbb{E}}_{y \in [N^{1/2}]} f(x) g(x+y) h(x+y^2)\right|}{\geqslant}\delta .$$ Then either $N \ll \delta^{-O(1)}$, or there exists $q \ll \delta^{-O(1)}$ and a 1-bounded function $\phi$ that is $O(\delta^{-O(1)} N^{-1/2})$-Lipschitz along $q \cdot {\mathbb{Z}}$ such that $$\sum_{x\in[N]} g(x)\phi(x) \gg \delta^{O(1)} N.$$

Applying [@PelusePrendivilleQuantitative Theorem 7.1], we obtain positive integers $q\ll\delta^{-O(1)}$ and $N^{1/2} {\geqslant}M \gg \delta^{O(1)}N^{1/2}$ such that $$\sum_{x}{\left| \sum_{y\in[M]}g(x+qy)\right|}\gg \delta^{O(1)}NM.$$ By the Cauchy–Schwarz inequality and a change of variables, we have $$\sum_{x}g(x)\sum_{y_1, y_2\in[M]}\overline{g(x+q(y_1 - y_2))}\gg \delta^{O(1)}NM^2.$$ Setting $$\phi(x) := {\mathbb{E}}_{y_1, y_2\in[M]}\overline{g(x+q(y_1 - y_2))},$$ Lemma \[h lipschitz\] shows this function has the required properties.

Before proving Theorem \[global control\], we record two standard facts.

\[rog lem\] There are at most $O(N^4)$ solutions $x \in [N]^6$ to the equation $$x_1^2+x_2^2+x_3^2 = x_4^2 +x_5^2 + x_6^2.$$

There are a number of ways to prove this. Perhaps the most robust is via the circle method, see [@DavenportAnalytic].

\[weyl-ineq\] Let $P \subset {\mathbb{Z}}$ be an arithmetic progression with common difference $q$ and let $0< \delta {\leqslant}1$. Suppose that $${\left| \sum_{x \in P} e(\alpha x^2) \right|} {\geqslant}\delta |P|.$$ Then either $|P| \ll \delta^{-O(1)}$ or there exists a positive integer $q' \ll \delta^{-O(1)}$ such that $$\|q'q^2\alpha\| \ll \delta^{-O(1)}|P|^{-2}.$$

Let $P = x_0 + q\cdot [N]$, so that our exponential sum becomes $$\sum_{x \in P} e(\alpha x^2) = \sum_{y \in [N]} e(\alpha q^2 y^2 + 2\alpha q x_0 y + \alpha x_0^2).$$ Applying [@GreenTaoQuadratic Lemma A.11], either $N \ll \delta^{-O(1)}$ or the conclusion of our lemma follows.

Write $\Lambda_N$ for the counting operator $\Lambda_{1, N}$ (that is, the average with $q=1$). Let $f, g, h : [N] \to {\mathbb{C}}$ be 1-bounded functions satisfying $$|\Lambda_{N}(f, g, h) |  {\geqslant}\delta .$$ Define the seminorm $${\left\| g\right\|} := \sup{\left\{|\Lambda_N(g_1, g, g_2)|: |g_i| {\leqslant}1 \text{ and } {\mathrm{supp}}(g_i) \subset [N]\right\}}.$$ Applying Lemma \[HB decomp\] to $g$ with ${\varepsilon}:= {\tfrac{1}{2}}\delta N^{-1/2}$, we follow the argument in the proof of Lemma \[inverse theorem\] to deduce that $$|\Lambda_{N}(f,g_{str},h)|    {\geqslant}\delta  -  |\Lambda_{N}(f, g_{unf},h)|
 {\geqslant}\delta -  {\left\| g_{unf}\right\|} {\geqslant}\tfrac{\delta}{2} .$$

Define the dual function $$F(x) : = {\mathbb{E}}_{y \in [N^{1/2}]} f(x) h(x+y^2).$$ The dual inequality then gives $$\tfrac\delta2  {\leqslant}|\Lambda_{N}(f, g_{str},h)| = N^{-1}|{\left\langleg_{str}, F\right\rangle}| {\leqslant}2 \delta^{-1} {\left\| F\right\|}.$$ Hence, by Lemma \[partial inverse theorem II\], there exists $q \ll \delta^{-O(1)}$ and a 1-bounded function $\phi$ that is $O(\delta^{-O(1)} N^{-1/2})$-Lipschitz along $q \cdot {\mathbb{Z}}$ and satisfies $$\sum_{x\in[N]} F(x)\phi(x) \gg \delta^{O(1)} N.$$ Expanding the definition of the dual function, we have $$\sum_{x\in [N]}\sum_{y \in [N^{1/2}]}f(x)\phi(x+y) h(x+y^2) \gg \delta^{O(1)}N^{3/2}.$$

Let us partition ${\mathbb{Z}}$ into arithmetic progressions $P$ each of common difference $q$ and length $M$, where $M$ will be chosen shortly. For each such arithmetic progression $P$, fix an element $y_P \in P$. Using the Lipschitz property of $\phi$, for any $x \in {\mathbb{Z}}$ and $y \in P$ we have $$|\phi(x+y_P) - \phi(x+y)| \ll \delta^{-O(1)}M N^{-1/2}.$$ Hence, $${\left| \sum_P\sum_{x\in [N]}\sum_{y \in P\cap [N^{1/2}]}f(x)[\phi(x+y) - \phi(x + y_P) ]h(x+y^2)\right|} \ll \delta^{-O(1)}MN.$$ We can therefore take $M$ sufficiently small to satisfy both $M \gg \delta^{O(1)} N^{1/2}$ and $${\left| \sum_P\sum_x\sum_{y \in P\cap [N^{1/2}]}f(x) \phi(x + y_P) h(x+y^2)\right|} \gg \delta^{O(1)}N^{3/2}.$$

Set $f_P(x) := f(x) \phi(x+y_P)$. The number of progressions $P$ that intersect $[N^{1/2}]$ is at most $O(N^{1/2}M^{-1} + q) = O(\delta^{-O(1)})$. Therefore, the pigeon-hole principle gives a progression $P$ for which $$\label{shorter sarko}
{\left| \sum_x\sum_{y \in P\cap[N^{1/2}]} f_P(x) h(x+y^2)\right|} \gg \delta^{O(1)}N^{3/2}.$$ In particular, $|P \cap [N^{1/2}]| \gg \delta^{O(1)} N^{1/2}$.

Writing $S_{P}(\alpha)$ for $\sum_{y \in P\cap [N^{1/2}]} e{\left( \alpha y^2 \right)}$, the orthogonality relations allow us to reformulate as $$\begin{aligned}
 {\left| \int_{\mathbb{T}}\hat{f}_P(\alpha) \hat{h}(-\alpha) S_{P}(\alpha) d \alpha\right|} \gg \delta^{O(1)}N^{3/2}.\end{aligned}$$ Let $\eta > 0$ be a parameter to be determined shortly, and define the major arcs $$\mathfrak{M} := {\left\{\alpha \in {\mathbb{T}}: |S_{P}(\alpha)| {\geqslant}\eta N^{1/2}\right\}}.$$ Parseval’s identity then gives $${\left| \int_{{\mathbb{T}}\setminus\mathfrak{M}} \hat{f}_P(\alpha) \hat{h}(-\alpha) S_{P}(\alpha) d \alpha\right|} {\leqslant}\eta N^{1/2} {\big\| \hat{f}_P \big\|}_2{\big\| \hat{h} \big\|}_2 {\leqslant}\eta N^{3/2}.$$ Hence we may take $\eta \gg \delta^{O(1)}$ and ensure that $$\begin{aligned}
 {\left| \int_{\mathfrak{M}} \hat{f}_P(\alpha) \hat{h}(-\alpha) S_{P}(\alpha)d \alpha\right|} \gg \delta^{O(1)}N^{3/2}.\end{aligned}$$

By Lemma \[rog lem\] and orthogonality, we have ${\left\| S_{P}\right\|}_6 \ll  N^{1/3}$. Thus, by Hölder’s inequality, we get that $${\left| \int_{\mathfrak{M}} \hat{f}_P(\alpha) \hat{h}(-\alpha) S_{P}(\alpha)d \alpha\right|} {\leqslant}{\big\| \hat{f}_P \big\|}_2 {\big\| \hat{h} \big\|}_2^{2/3} {\big\| S_P \big\|}_6 \sup_{\alpha \in \mathfrak{M}}  {\bigl| \hat{h}(-\alpha) \bigr|}^{1/3}.$$ We therefore deduce that there exists $\alpha \in \mathfrak{M}$ such that $${\bigl| \hat{h}(-\alpha) \bigr|} \gg \delta^{O(1)} N.$$

Finally, an application of Weyl’s inequality (Lemma \[weyl-ineq\]) shows that if $-\alpha \in \mathfrak{M}$ then $\alpha$ has the required Diophantine approximation property.

Let $\alpha\in{\mathbb{R}}$ be the frequency and $q$ the positive integer provided by Theorem \[global control\]. For any integer $a$ and positive integer $M$, if $x, y \in a + q\cdot[M]$, then $${\left| e(\alpha x) - e(\alpha y)\right|} {\leqslant}2\pi{\left\| \alpha(x-y)\right\|} \ll \delta^{-O(1)} M N^{-1}.$$ Partitioning ${\mathbb{Z}}$ into arithmetic progressions of common difference $q$ and length $M$ then gives $$\delta^{O(1)} N \ll \sum_P{\Bigl| \sum_{x \in P} f(x) \Bigr|} +   \delta^{-O(1)} M .$$ We thus take $M \gg \delta^{O(1)} N$ sufficiently small to ensure that $$\delta^{O(1)} N \ll \sum_P{\Bigl| \sum_{x \in P} f(x) \Bigr|}.$$ Write $\theta_P$ for the conjugate phase of the inner sum. Then the map $x \mapsto \sum_P\theta_P1_P(x)$ is a local function of resolution $\gg \delta^{O(1)}N$ and modulus $\ll \delta^{-O(1)}$, yielding the corollary.

Longer progressions {#longer section}
===================

As mentioned in §\[longer intro\], the main obstacle to generalising our polylogarithmic bound to longer configurations such as is in obtaining an appropriate generalisation of Lemma \[inverse theorem\]; in particular, showing that if the relevant counting operator is large, then *all* functions must correlate with a product of a bounded number of local functions.

Let us demonstrate where the argument breaks down for $m > 2$. Given polynomials as in and 1-bounded functions $f_0, f_1, \dots, f_m : [N] \to {\mathbb{C}}$, define the counting operator $$\begin{gathered}
\Lambda_{P_1, \dots, P_m}^N(f_0, f_1, \dots, f_m) := \\{\mathbb{E}}_{x \in [N]} {\mathbb{E}}_{y \in [N^{1/\deg P_m}]}f_0(x)f_1(x+P_1(y))\dotsm f_m(x+P_m(y)) .\end{gathered}$$ Using the main technical result of [@PeluseBounds], [@PeluseBounds Theorem 3.3], one can show that if $${\left| \Lambda_{P_1, \dots, P_m}^N(f_0, f_1, \dots , f_m)\right|} {\geqslant}\delta ,$$ then both $f_0$ and $f_1$ correlate with local functions $\phi_0$ and $\phi_1$. Using the Hahn–Banach decomposition (Lemma \[HB decomp\]), as in our proof of Theorem \[global control\] and Lemma \[inverse theorem\], one may conclude that $${\left| \Lambda_{P_1, \dots, P_m}^N(\phi_0, \phi_1, f_2, \dots , f_m)\right|} \gg \delta^{O(1)},$$ If $m = 2$, one can then pigeon-hole in the smaller $y$ variable appearing in the counting operator (as we do in the proof of Lemma \[inverse theorem\]) to conclude that $f_2$ correlates with a product of two local functions. It is this simple pigeon-holing argument that fails when $m > 2$.

An alternative strategy for longer progressions
-----------------------------------------------

A more productive strategy is to follow our proof of Theorem \[global control\] instead of Theorem \[main\]. In proving Theorem \[global control\] we replace the counting operator $\Lambda_{y, y^2}^N(f_0, f_1, f_2)$ with $\Lambda_{y, y^2}^N(f_0, \phi, f_2)$, where $\phi$ is a local function that is constant on progressions of length $\approx N^{1/2}$ with common difference of size $\approx O(1)$. Provided that we pass to appropriate subprogressions in all of the variables appearing in our counting operator, we can exploit the properties of this local function and ‘remove’ it from our count. In effect (after passing to subprogressions of bounded common difference), we replace the count $\Lambda_{y, y^2}^N(f_0, f_1, f_2)$ with one of the form $\Lambda_{Q}^{N'}(f_0, f_2)$, where $Q$ is a quadratic polynomial and $N'$ is slightly smaller than $N$.

Generalising this approach, one can use [@PeluseBounds Theorem 3.3] to replace the counting operator $\Lambda_{P_1, \dots, P_m}^N(f_0, f_1, \dots , f_m)$ with $\Lambda_{P_1, \dots, P_m}^N(f_0, \phi, f_2, \dots , f_m)$, where $\phi$ is a local function. Provided that this local function has resolution $\gg N^{\deg P_1 / \deg P_m}$ and common difference $q \ll 1$, we have $$\phi(x+P_1(y)) \approx \phi(x)$$ for any $x\in {\mathbb{Z}}$ and any $y$ constrained to a subprogression of common difference $q$ and length $\approx N^{\deg P_1 / \deg P_m}$. Passing to subprogressions in $x$ and $y$, one should then be able to replace the operator $$\Lambda_{P_1, \dots, P_m}^N(f_0, \phi, f_2, \dots , f_m)$$ by one of the form $$\Lambda_{Q_2, \dots, Q_m}^{N'}(f_0, f_2, \dots , f_m).$$ Applying induction on $m$ may then allow one to show that every function in the original counting operator correlates with a local function.

The main impediment to carrying out this strategy is that the polynomials $Q_2$, …, $Q_m$, which arise on passing to a subprogression, may not satisfy the hypotheses required to reapply [@PeluseBounds Theorem 3.3]. It is likely that the polynomials are sufficiently well-behaved for the arguments of [@PeluseBounds] to remain valid, but we leave this verification to the energetic reader.

[^1]: Here ${\left\| \cdot\right\|}$ denotes the distance to the nearest integer, and $e(\alpha) := e^{2\pi i\alpha}$. For our conventions regarding asymptotic notation see §\[notation\].

[^2]: For details see the second author’s exposition [@PrendivilleInverse].

[^3]: On occasion the relevant results in [@GowersDecompositions] appear to assume that unit balls are *bounded* (if we take the definition of *convex body* to be a compact convex set with non-empty interior), which may not be true for the unit ball of a seminorm. However, the boundedness assumption is not necessary in the pertinent proofs. Moreover, one could quotient by the norm zero set to obtain a genuine norm.
