As in all previous posts in this series, we adopt the following asymptotic notation: ${x}$ is a parameter going off to infinity, and all quantities may depend on ${x}$ unless explicitly declared to be “fixed”. The asymptotic notation ${O(), o(), \ll}$ is then defined relative to this parameter. A quantity ${q}$ is said to be of polynomial size if one has ${q = O(x^{O(1)})}$, and bounded if ${q=O(1)}$. We also write ${X \lessapprox Y}$ for ${X \ll x^{o(1)} Y}$, and ${X \sim Y}$ for ${X \ll Y \ll X}$.

The purpose of this (rather technical) post is both to roll over the polymath8 research thread from this previous post, and also to record the details of the latest improvement to the Type I estimates (based on exploiting additional averaging and using Deligne’s proof of the Weil conjectures) which lead to a slight improvement in the numerology.

In order to obtain this new Type I estimate, we need to strengthen the previously used properties of “dense divisibility” or “double dense divisibility” as follows.

Definition 1 (Multiple dense divisibility) Let ${y \geq 1}$. For each natural number ${k \geq 0}$, we define a notion of ${k}$-tuply ${y}$-dense divisibility recursively as follows:

• Every natural number ${n}$ is ${0}$-tuply ${y}$-densely divisible.
• If ${k \geq 1}$ and ${n}$ is a natural number, we say that ${n}$ is ${k}$-tuply ${y}$-densely divisible if, whenever ${i,j \geq 0}$ are natural numbers with ${i+j=k-1}$, and ${1 \leq R \leq n}$, one can find a factorisation ${n = qr}$ with ${y^{-1} R \leq r \leq R}$ such that ${q}$ is ${i}$-tuply ${y}$-densely divisible and ${r}$ is ${j}$-tuply ${y}$-densely divisible.

We let ${{\mathcal D}^{(k)}_y}$ denote the set of ${k}$-tuply ${y}$-densely divisible numbers. We abbreviate “${1}$-tuply densely divisible” as “densely divisible”, “${2}$-tuply densely divisible” as “doubly densely divisible”, and so forth; we also abbreviate ${{\mathcal D}^{(1)}_y}$ as ${{\mathcal D}_y}$.

Given any finitely supported sequence ${\alpha: {\bf N} \rightarrow {\bf C}}$ and any primitive residue class ${a\ (q)}$, we define the discrepancy

$\displaystyle \Delta(\alpha; a \ (q)) := \sum_{n: n = a\ (q)} \alpha(n) - \frac{1}{\phi(q)} \sum_{n: (n,q)=1} \alpha(n).$

We now recall the key concept of a coefficient sequence, with some slight tweaks in the definitions that are technically convenient for this post.

Definition 2 A coefficient sequence is a finitely supported sequence ${\alpha: {\bf N} \rightarrow {\bf R}}$ that obeys the bounds

$\displaystyle |\alpha(n)| \ll \tau^{O(1)}(n) \log^{O(1)}(x) \ \ \ \ \ (1)$

for all ${n}$, where ${\tau}$ is the divisor function.

• (i) A coefficient sequence ${\alpha}$ is said to be located at scale ${N}$ for some ${N \geq 1}$ if it is supported on an interval of the form ${[cN, CN]}$ for some ${1 \ll c < C \ll 1}$.
• (ii) A coefficient sequence ${\alpha}$ located at scale ${N}$ for some ${N \geq 1}$ is said to obey the Siegel-Walfisz theorem if one has

$\displaystyle | \Delta(\alpha 1_{(\cdot,q)=1}; a\ (r)) | \ll \tau(qr)^{O(1)} N \log^{-A} x \ \ \ \ \ (2)$

for any ${q,r \geq 1}$, any fixed ${A}$, and any primitive residue class ${a\ (r)}$.

• (iii) A coefficient sequence ${\alpha}$ is said to be smooth at scale ${N}$ for some ${N > 0}$ is said to be smooth if it takes the form ${\alpha(n) = \psi(n/N)}$ for some smooth function ${\psi: {\bf R} \rightarrow {\bf C}}$ supported on an interval of size ${O(1)}$ and obeying the derivative bounds

$\displaystyle |\psi^{(j)}(t)| \lesssim \log^{O(1)} x \ \ \ \ \ (3)$

for all fixed ${j \geq 0}$ (note that the implied constant in the ${O()}$ notation may depend on ${j}$).

Note that we allow sequences to be smooth at scale ${N}$ without being located at scale ${N}$; for instance if one arbitrarily translates of a sequence that is both smooth and located at scale ${N}$, it will remain smooth at this scale but may not necessarily be located at this scale any more. Note also that we allow the smoothness scale ${N}$ of a coefficient sequence to be less than one. This is to allow for the following convenient rescaling property: if ${n \mapsto \psi(n)}$ is smooth at scale ${N}$, ${q \geq 1}$, and ${a}$ is an integer, then ${n \mapsto \psi(qn+a)}$ is smooth at scale ${N/q}$, even if ${N/q}$ is less than one.

Now we adapt the Type I estimate to the ${k}$-tuply densely divisible setting.

Definition 3 (Type I estimates) Let ${0 < \varpi < 1/4}$, ${0 < \delta < 1/4+\varpi}$, and ${0 < \sigma < 1/2}$ be fixed quantities, and let ${k \geq 1}$ be a fixed natural number. We let ${I}$ be an arbitrary bounded subset of ${{\bf R}}$, let ${P_I := \prod_{p \in I} p}$, and let ${a\ (P_I)}$ a primitive congruence class. We say that ${Type^{(k)}_I[\varpi,\delta,\sigma]}$ holds if, whenever ${M, N \gg 1}$ are quantities with

$\displaystyle M N \sim x \ \ \ \ \ (4)$

and

$\displaystyle x^{1/2-\sigma} \lessapprox N \lessapprox x^{1/2-2\varpi-c} \ \ \ \ \ (5)$

for some fixed ${c>0}$, and ${\alpha,\beta}$ are coefficient sequences located at scales ${M,N}$ respectively, with ${\beta}$ obeying a Siegel-Walfisz theorem, we have

$\displaystyle \sum_{q \in {\mathcal S}_I \cap {\mathcal D}_{x^\delta}^{(k)}: q \leq x^{1/2+2\varpi}} |\Delta(\alpha * \beta; a\ (q))| \ll x \log^{-A} x \ \ \ \ \ (6)$

for any fixed ${A>0}$. Here, as in previous posts, ${{\mathcal S}_I}$ denotes the square-free natural numbers whose prime factors lie in ${I}$.

The main theorem of this post is then

Theorem 4 (Improved Type I estimate) We have ${Type^{(4)}_I[\varpi,\delta,\sigma]}$ whenever

$\displaystyle \frac{160}{3} \varpi + 16 \delta + \frac{34}{9} \sigma < 1$

and

$\displaystyle 64\varpi + 18\delta + 2\sigma < 1.$

In practice, the first condition here is dominant. Except for weakening double dense divisibility to quadruple dense divisibility, this improves upon the previous Type I estimate that established ${Type^{(2)}_I[\varpi,\delta,\sigma]}$ under the stricter hypothesis

$\displaystyle 56 \varpi + 16 \delta + 4 \sigma < 1.$

As in previous posts, Type I estimates (when combined with existing Type II and Type III estimates) lead to distribution results of Motohashi-Pintz-Zhang type. For any fixed ${\varpi, \delta > 0}$ and ${k \geq 1}$, we let ${MPZ^{(k)}[\varpi,\delta]}$ denote the assertion that

$\displaystyle \sum_{q \in {\mathcal S}_I \cap {\mathcal D}_{x^\delta}^{(k)}: q \leq x^{1/2+2\varpi}} |\Delta(\Lambda 1_{[x,2x]}; a\ (q))| \ll x \log^{-A} x \ \ \ \ \ (7)$

for any fixed ${A > 0}$, any bounded ${I}$, and any primitive ${a\ (P_I)}$, where ${\Lambda}$ is the von Mangoldt function.

Corollary 5 We have ${MPZ^{(4)}[\varpi,\delta]}$ whenever

$\displaystyle \frac{600}{7} \varpi + \frac{180}{7} \delta < 1 \ \ \ \ \ (8)$

Proof: Setting ${\sigma}$ sufficiently close to ${1/10}$, we see from the above theorem that ${Type^{(4)}_{II}[\varpi,\delta]}$ holds whenever

$\displaystyle \frac{600}{7} \varpi + \frac{180}{7} \delta < 1$

and

$\displaystyle 80 \varpi + \frac{45}{2} \delta < 1.$

The second condition is implied by the first and can be deleted.

From this previous post we know that ${Type^{(4)}_{II}[\varpi,\delta]}$ (which we define analogously to ${Type'_{II}[\varpi,\delta], Type''_{II}[\varpi,\delta]}$ from previous sections) holds whenever

$\displaystyle 68 \varpi + 14 \delta < 1$

while ${Type^{(4)}_{III}[\varpi,\delta,\sigma]}$ holds with ${\sigma}$ sufficiently close to ${1/10}$ whenever

$\displaystyle 70 \varpi + 5 \delta < 1.$

Again, these conditions are implied by (8). The claim then follows from the Heath-Brown identity and dyadic decomposition as in this previous post. $\Box$

As before, we let ${DHL[k_0,2]}$ denote the claim that given any admissible ${k_0}$-tuple ${{\mathcal H}}$, there are infinitely many translates of ${{\mathcal H}}$ that contain at least two primes.

Corollary 6 We have ${DHL[k_0,2]}$ with ${k_0 = 632}$.

This follows from the Pintz sieve, as discussed below the fold. Combining this with the best known prime tuples, we obtain that there are infinitely many prime gaps of size at most ${4,680}$, improving slightly over the previous record of ${5,414}$.

— 1. Multiple dense divisibility —

We record some useful properties of dense divisibility.

Lemma 7 (Properties of dense divisibility) Let ${k \geq 0}$ and ${y \geq 1}$.

• (i) If ${n}$ is ${k}$-tuply ${y}$-densely divisible, and ${m}$ is a factor of ${n}$, then ${m}$ is ${k}$-tuply ${y (n/m)}$-densely divisible. Similarly, if ${l}$ is a multiple of ${n}$, then ${l}$ is ${y (l/n)}$-densely divisible.
• (ii) If ${m,n}$ are ${y}$-densely divisible, then ${[m,n]}$ is also ${y}$-densely divisible.
• (iii) Any ${y}$-smooth number is ${k}$-tuply ${y}$-densely divisible.
• (iv) If ${n}$ is ${y'}$-smooth and square-free for some ${y' \geq y}$, and ${\prod_{p|n: p \leq y} p \geq (y')^k/y}$, then ${n}$ is ${k}$-tuply ${y}$-densely divisible.

Proof: (i) is easily established by induction on ${k}$, the idea being to start with a good factorisation of ${n}$ and perturb it into a factorisation of ${m}$ or ${l}$ by dividing or multiplying by a small number. To prove (ii), we may assume without loss of generality that ${m \leq n}$, so that ${n \geq [m,n]^{1/2}}$. If we set ${a := \frac{[m,n]}{n}}$, then the factors of ${n}$, as well as the factors of ${n}$ multiplied by ${a}$, are both factors of ${[m,n]}$. From this we can deduce the ${y}$-dense divisibility of ${[m,n]}$ from the ${y}$-dense divisibility of ${n}$.

The claim (iii) is easily established by induction on ${k}$ and a greedy algorithm, so we turn to (iv). The claim is trivial for ${k=0}$. Next, we consider the ${k=1}$ case. Our task is to show that for any ${1 \leq R \leq n}$, one can find a factorisation ${n=qr}$ with ${y^{-1} R \leq r \leq R}$. If ${\prod_{p|n: p>y} p \leq R}$, we can achieve this factorisation by initialising ${r}$ to equal ${\prod_{p|n: p>y} p}$ and then greedily multiplying the remaining factors of ${n}$ until one exceeds ${y^{-1} R}$, so we may assume instead that ${\prod_{p|n: p>y} p > R}$. Then by the greedy algorithm we can find a factor ${r'}$ of ${\prod_{p|n: p>y} p}$ with ${(y')^{-1} R \leq r' \leq R}$; if we then greedily multiply ${r'}$ by factors ${p|n}$ with ${p we obtain the claim.

Finally we consider the ${k>1}$ case. We assume inductively that the claim has already been proven for smaller values of ${k}$. Let ${i,j \geq 0}$ be such that ${i+j=k-1}$. By hypothesis, the ${y}$-smooth quantity ${n' := \prod_{p|n: p \geq y} p}$ is at least ${(y')^i (y')^j (y'/y)}$. By the greedy algorithm, we may thus factor ${n' = n_1 n_2 n_3}$ where

$\displaystyle (y')^i y^{-1} \leq n_1 \leq (y')^i$

and

$\displaystyle (y')^j y^{-1} \leq n_2 \leq (y')^j$

and thus

$\displaystyle n_3 \geq y'/y.$

Now we divide into several cases. Suppose first that ${n_1 \leq R \leq n/n_2}$. Then ${1 \leq \frac{R}{n_1} \leq \frac{n}{n_1 n_2}}$, so by the ${k=1}$ case, we may find a factorisation ${\frac{n}{n_1 n_2} = q' r'}$ with ${y^{-1} \frac{R}{n_1} \leq r' \leq \frac{R}{n_1}}$. Setting ${r := n_1 r'}$ and ${q := n_2 q'}$, the claim then follows from the induction hypothesis.

Now suppose that ${R < n_1}$. By the greedy algorithm, we may then find a factor ${r}$ of the ${y}$-smooth quantity ${n_1}$ with ${y^{-1} R \leq r \leq R}$; setting ${q := n/r}$, we see that ${q}$ is a multiple of ${n_2}$ and hence ${\prod_{p|q: p \leq y} p \geq (y')^j y^{-1}}$. The claim now follows from the induction hypothesis and (iii).

Finally, suppose that ${R > n/n_2}$. By the greedy algorithm, we may then find a factor ${q}$ of the ${y}$-smooth quantity ${n_2}$ with ${n/R \leq q \leq yn/R}$; setting ${r := n/q}$, we see that ${r}$ is a multiple of ${n_1}$ and hence ${\prod_{p|r: p \leq y} p \geq (y')^i y^{-1}}$. The claim now follows from the induction hypothesis and (iii). $\Box$

Now we record the criterion for using ${MPZ^{(k)}}$ to deduce ${DHL[k_0,2]}$.

Proposition 8 (Criterion for DHL) Let ${\varpi, \delta}$ be such that ${MPZ^{(k)}[\varpi,\delta]}$ holds. Suppose that one can find a natural number ${k_0 > 2}$ and real numbers ${\delta \leq \delta' \leq 1/4+\varpi}$ and ${A > 0}$ such that

$\displaystyle (1+4\varpi) (1-2\kappa_1 - 2\kappa_2 - 2\kappa_3) > \frac{j^{2}_{k_0-2}}{k_0(k_0-1)}$

where

$\displaystyle \kappa_1 := \int_{\theta}^1 (1-t)^{(k_0-1)/2} \frac{dt}{t}$

$\displaystyle \kappa_2 := (k_0-1) \int_{\theta}^1 (1-t)^{k_0-1} \frac{dt}{t}$

$\displaystyle \kappa_3 := \tilde \theta \frac{J_{k_0-2}(\sqrt{\tilde \theta} j_{k_0-2})^2 - J_{k_0-3}(\sqrt{\tilde \theta} j_{k_0-2}) J_{k_0-1}(\sqrt{\tilde \theta} j_{k_0-2})}{ J_{k_0-3}(j_{k_0-2})^2 }$

$\displaystyle \times \exp( A + (k_0-1) \int_{\tilde \delta}^\theta e^{-(A+2\alpha)t} \frac{dt}{t} )$

$\displaystyle \alpha := \frac{j_{k_0-2}^2}{4(k_0-1)}$

$\displaystyle \theta := \frac{\delta'}{1/4 + \varpi}$

$\displaystyle \tilde \theta := \frac{k\delta' - \delta/2 + \varpi}{1/4 + \varpi}$

$\displaystyle \tilde \delta := \frac{\delta}{1/4 + \varpi}.$

Then ${DHL[k_0,2]}$ holds.

Proof: We use the Pintz sieve from this post, repeating the proof of Theorem 5 from that post (and using the explicit formulae for ${G_{k_0-1}(0,0)}$ and ${G_{k_0-1,\tilde \theta}(0,0)}$ from this comment thread). The main difference is that the exponent ${(\delta'-\delta)/2 + \varpi + \epsilon/2}$ in equation (10) of that post needs to be replaced with ${(k\delta'-\delta)/2 + \varpi + \epsilon/2}$ (and similarly for the displays up to (11)), and ${{\mathcal D}_{x^\delta}}$ needs to be replaced with ${{\mathcal D}_{x^\delta}^{(k)}}$. $\Box$

Applying this proposition with ${k_0 := 632}$, ${\delta = 1/11500}$, ${\delta' := 1/128}$, ${600 \varpi/7 + 180 \delta / 7}$ sufficiently close to ${1}$, and ${A := 200}$ we obtain ${DHL[632,2]}$ as claimed.

— 2. van der Corput estimates —

In this section we generalise the van der Corput estimates from Section 1 of this previous post to wider classes of “structured functions” than rational phases. We will adopt an axiomatic approach, laying out the precise axioms that we need a given class of structured functions to obey:

Definition 9 (Structured functions) Let ${I}$ be a bounded subset of ${{\bf R}}$. A class of structured functions is a family ${{\mathcal C} = ({\mathcal C}_{p,C})_{p,C}}$ of collections ${{\mathcal C}_{p,C}}$ of functions ${K:U \rightarrow {\bf C}}$ defined on subsets ${U}$ of ${{\bf Z}/p{\bf Z}}$ for each prime ${p \in I}$ and every ${C \geq 1}$; an element of ${{\mathcal C}_{p,C}}$ is then said to be a structured function of complexity at most ${C}$ and modulus ${p}$. Furthermore we place an equivalence relation ${\equiv}$ on each class ${{\mathcal C}_{p,C}}$ with ${p}$ sufficiently large depending on ${C}$. This class and this equivalence relation is assumed to obey the following axioms:

• (i) (Monotonicity) One has ${{\mathcal C}_{p,C} \subset {\mathcal C}_{p,C'}}$ whenever ${C' \geq C}$. Furthermore, if ${p}$ is sufficiently large depending on ${C,C'}$, the equivalence relations on ${{\mathcal C}_{p,C}}$ and ${{\mathcal C}_{p,C'}}$ agree on their common domain of definition.
• (ii) (Near-total definition) If ${K \in {\mathcal C}_{p,C}}$, then the domain ${U}$ of ${K}$ consists of ${{\bf Z}/p{\bf Z}}$ with at most ${O_C(1)}$ points removed.
• (iii) (Pointwise bound) If ${K \in {\mathcal C}_{p,C}}$, then ${K(x) = O_C(1)}$ for all ${x}$ in the domain ${U}$ of ${K}$.
• (iv) (Conjugacy) If ${K \in {\mathcal C}_{p,C}}$, then ${\overline{K} \in {\mathcal C}_{p,C'}}$ for some ${C' = O_C(1)}$.
• (v) (Multiplication) If ${K,K' \in {\mathcal C}_{p,C}}$, then the pointwise product ${KK'}$ (on the common domain of definition) can be expressed as the sum of ${k=O_C(1)}$ functions ${K_1,\ldots,K_k}$ (which we will call the components of ${KK'}$) in ${{\mathcal C}_{p,C'}}$ for some ${C' = O_C(1)}$.
• (vi) (Translation invariance) If ${K \in {\mathcal C}_{p,C}}$, and ${h \in {\bf Z}/p{\bf Z}}$, then the function ${x \mapsto K(x+h)}$ (defined on the translation ${U-h}$ of the domain of definition of ${K}$) lies in ${{\mathcal C}_{p,C'}}$ for some ${C' = O_C(1)}$.
• (vii) (Dilation invariance) If ${K \in {\mathcal C}_{p,C}}$, and ${a \in ({\bf Z}/p{\bf Z})^\times}$, then the function ${x \mapsto K(ax)}$ (defined on the dilation ${a^{-1} U}$ of the domain of definition of ${f}$) lies in ${{\mathcal C}_{p,C'}}$ for some ${C' = O_C(1)}$.
• (viii) (Polynomial phases) If ${P: {\bf Z}/p{\bf Z} \rightarrow {\bf Z}/p{\bf Z}}$ is a polynomial of degree at most ${d}$, then the function ${x \mapsto e_p(P(x))}$ lies in ${{\mathcal C}_{p,C}}$ for some ${C = O_d(1)}$. More generally, if ${K \in {\mathcal C}_{p,C}}$, then the product ${x \mapsto e_p(P(x)) K(x)}$ lies in ${{\mathcal C}_{p,C'}}$ for some ${C' = O_{C,d}(1)}$. Furthermore, if ${p}$ is sufficiently large depending on ${d,C}$, this operation respects the equivalence relation ${\equiv}$: ${K \equiv K'}$ if and only if ${e_p(P) K \equiv e_p(P) K'}$. Finally, if ${K \equiv e_p(P)}$ and ${K}$ is not identically zero, then ${c_{K,e_p(P)} \neq 0}$.
• (ix) (Almost orthogonality) If ${K,K' \in {\mathcal C}_{p,C}}$ have domains of definition ${U, U'}$ respectively, one has ${\sum_{x \in U \cap U'} K(x) \overline{K'(x)} = c_{K,K'} p + O_C(p^{1/2})}$ for an algebraic integer ${c_{K,K'}}$, with the error term ${O_C(p^{1/2})}$ being Galois-absolute in the sense that all Galois conjugates of the error term are also ${O_C(p^{1/2})}$. Furthermore, if ${p}$ is sufficiently large depending on ${C}$, then ${c_{K,K'}}$ vanishes whenever ${K \not \equiv K'}$.
• (x) (Integration) Suppose that ${K \in {\mathcal C}_{p,C}}$ is such that ${K(\cdot+h) \overline{K}}$ contains a component equivalent to ${1}$ for some ${h \in ({\bf Z}/p{\bf Z})^\times}$. Suppose also that ${p}$ is sufficiently large depending on ${C}$. Then there exists ${a \in {\bf Z}/p{\bf Z}}$ such that ${K \equiv e_p(a \cdot)}$.

Example 1 (Polynomial phases) Let ${I}$ be a bounded subset of ${{\bf R}}$. If, for every prime ${p \in I}$ and ${C \geq 1}$, we define ${{\mathcal C}_{p,C}}$ to be the set of all functions of the form ${x \mapsto e_p(f(x))}$, where ${f}$ are polynomials of degree at most ${C}$ with integer coefficients, defined on all of ${{\bf Z}/p{\bf Z}}$, then this is a class of structured functions (note that the almost orthogonality axiom requires the Weil conjectures for curves). Two polyomial phases ${e_p(f(x)), e_p(g(x))}$ will be declared equivalent if ${f,g}$ differ only in the constant term. Note from the Chinese remainder theorem that the function ${x \mapsto e_q( f(x) )}$ is then also a structured function of complexity at most ${C}$ and modulus ${q}$.

Example 2 (Polynomial phases twisted by characters) Let ${I}$ be a bounded subset of ${{\bf R}}$. If, for every prime ${p \in I}$ and ${C \geq 1}$, we define ${{\mathcal C}_{p,C}}$ to be the set of all functions of the form ${x \mapsto e(\theta) e_p(f(x)) \prod_{i=1}^k \chi_i( g_i(x) )}$, where ${e(\theta)}$ is a phase, ${g_i,f}$ are polynomials of degree at most ${C}$ with integer coefficients, ${0 \leq k \leq C}$, and the ${\chi_i}$ are Dirichlet characters of order ${p}$, with the non-standard convention that ${\chi_i}$ is undefined (instead of vanishing) at zero. Then this is a class of structured functions (again, the almost orthogonality axiom requires the Weil conjectures for curves). We declare two structured functions to be equivalent if they agree up to a constant phase on their common domain of definition. Note from the Chinese remainder theorem that the function ${x \mapsto e_q( f(x) ) \prod_{i=1}^k \chi_i(g_i(x))}$ is then also a structured function of complexity at most ${C}$ if the ${\chi_i}$ are Dirichlet characters of period ${q}$ (and conductor dividing ${q}$), again with the convention that ${\chi(x)}$ is undefined (instead of vanishing) when ${(x,q) \neq 1}$.

Example 3 (Rational phases) Let ${I}$ be a bounded subset of ${{\bf R}}$. If, for every prime ${p \in I}$ and ${C \geq 1}$, we define ${{\mathcal C}_{p,C}}$ to be the set of all functions of the form ${x \mapsto e_p(\frac{f(x)}{g(x)})}$, where ${f,g}$ are polynomials of degree at most ${C}$ with integer coefficients and with ${g}$ monic, with the function only defined when ${g(x) \neq 0}$, then this is a class of structured functions (again, the almost orthogonality axiom requires the Weil conjectures for curves). We declare two structured functions to be equivalent if they agree up to a constant phase on their common domain of definition. Note from the Chinese remainder theorem that the function ${x \mapsto e_q( \frac{f(x)}{g(x)})}$ is then also a structured function of complexity at most ${C}$ and modulus ${q}$.

Example 4 (Trace weights) Let ${I}$ be a bounded subset of ${{\bf R}}$. We fix a prime ${\ell}$ not in ${I}$, and we fix an embedding ${\iota: {\bf Q}_\ell \rightarrow {\bf C}}$ of the ${\ell}$-adics into ${{\bf C}}$. If, for every prime ${p \in I}$ and ${C \geq 1}$, we define ${{\mathcal C}_{p,C}}$ to be the set of all functions ${K = K_{\mathcal F}: U \rightarrow {\bf C}}$ of the form

$\displaystyle K(x) := \iota( \hbox{tr}( \hbox{Frob}_x | {\mathcal F}_x ) )$

where ${U}$ is ${{\Bbb F}_p = {\bf Z}/p{\bf Z}}$ with at most ${C}$ points removed, and ${{\mathcal F}}$ is a lisse ${\ell}$-adic sheaf on ${U}$ that is pure of weight ${0}$ and geometrically isotypic with conductor at most ${C}$ (see this previous post for definitions of these terms), then this is a class of structured functions. We declare two trace weights ${K, K'}$ to be equivalent if one has ${K = K_{\mathcal F}}$ and ${K' = K_{{\mathcal F}'}}$ for some geometrically isotypic sheaves ${{\mathcal F}, {\mathcal F}'}$ whose geometrically irreducible components are isomorphic. The almost orthogonality now is deeper, being a consequence of Deligne’s second proof of the Weil conjectures, and also using a form of Schur’s lemma for sheaves; see Section 5 of this paper of Fouvry, Kowalski, and Michel. The integration axiom follows from Lemma 5.3 of the same paper. This class of structured functions includes the previous three classes, but also includes Kloosterman-type objects such as ${x \mapsto \frac{1}{\sqrt{p}} \sum_{y \in {\Bbb F}_p^\times} e_p( \frac{1}{y} + xy)}$ (and many other exponential sums) besides. (Indeed, it basically closed under the operations of Fourier transforms, convolution, and pullback, as long as certain degenerate cases are avoided.)

We now turn to the problem of obtaining non-trivial bounds for the expression

$\displaystyle \sum_n \psi_N(n) K_q(n)$

where ${q \in {\mathcal S}_I}$, ${K_q}$ is a structured function of bounded complexity and modulus ${q}$, and ${\psi_N}$ is a smooth function at scale ${N}$. The trivial bound here is

$\displaystyle \sum_n \psi_N(n) K_q(n)| \lessapprox N,$

since one has ${|K_q(n)| \lessapprox 1}$ from the divisor bound. In some cases we cannot hope to improve upon this bound; for instance, if ${K_q}$ is a constant phase ${e(\theta)}$ then there is clearly no improvement available. Similarly, if ${K_q}$ is the linear phase ${K_q(n) = e_q(n) e(\theta)}$, then there is no improvement in the regime ${N \ll q}$; if ${K_q}$ is the quadratic phase ${K_q(n) = e_q(n^2) e(\theta)}$ then there is no improvement in the regime ${N \ll q^{1/2}}$; if ${K_q}$ is the cubic phase ${K_q(n) = e_q(n^3) e(\theta)}$ then there is no improvement in the regime ${N \ll q^{1/3}}$; and so forth. On the other hand, we will be able to establish a van der Corput estimate which roughly speaking asserts that as long as these polynomial obstructions are avoided, and ${q}$ is smooth, one gets a non-trivial gain.

We first need a lemma:

Lemma 10 (Fundamental theorem of calculus) Let ${{\mathcal C}}$ be a class of structured functions. Let ${C, d \geq 0}$, let ${p \in I}$, and let ${K}$ be a structured function of complexity at most ${C}$ with modulus ${p}$. Assume that ${p}$ is sufficiently large depending on ${C,d}$. Let ${h \in ({\bf Z}/p{\bf Z})^\times}$, and suppose that there is a polynomial ${P: {\bf Z}/p{\bf Z} \rightarrow {\bf Z}/p{\bf Z}}$ of degree at most ${d}$ such that ${K(\cdot+h) \overline{K} \equiv e_p(P)}$ for all ${n \in {\bf Z}/p{\bf Z}}$ for which this identity is well-defined. Then there exists a polynomial ${Q: {\bf Z}/p{\bf Z} \rightarrow {\bf Z}/p{\bf Z}}$ of degree at most ${d+1}$ such that ${K \equiv e_p(Q)}$ for all ${n \in {\bf Z}/p{\bf Z}}$ for which this identity is well-defined.

Proof: By dilating by ${h}$ and using the dilation invariance of structured functions, we may assume without loss of generality that ${h=1}$. We can write ${P}$ in terms of the binomial functions ${n \mapsto \binom{n}{i}}$ for ${i=0,\ldots,d}$ (which are well-defined if ${p > d}$) as

$\displaystyle P(n) = \sum_{i=0}^d c_i \binom{n}{i}$

for some coefficients ${c_0,\ldots,c_d\in {\bf Z}/p{\bf Z}}$. If we then define

$\displaystyle Q_0(n) := \sum_{i=0}^d c_i \binom{n}{i+1}$

then ${Q_0}$ is a polynomial of degree at most ${d+1}$ (if ${p>d+1}$) and ${Q_0(n+1)-Q_0(n)=P(n)}$ by Pascal’s identity. So if we multiply ${K}$ by ${e_p(-Q_0)}$ (using the polynomial phase invariance of structured functions) we may assume without loss of generality that ${P=0}$, thus ${K(\cdot+1) \overline{K} \equiv 1}$. But then the claim follows from the integration axiom. $\Box$

Now we can state the van der Corput estimate.

Proposition 11 (van der Corput) Let ${{\mathcal C}}$ be a class of structured functions. Let ${q \in {\mathcal S}_I}$ be of polynomial size, and let ${K_q = \prod_{p|q} K_p}$ be a structured function of modulus ${q}$ and complexity at most ${O(1)}$. Let ${l \geq 1}$ be fixed, and let ${{\mathcal P}}$ denote the set of sufficiently large primes ${p}$ dividing ${q}$ with the property that there exists a polynomial ${P_p: {\bf Z}/p{\bf Z} \rightarrow {\bf Z}/p{\bf Z}}$ of degree at most ${l}$ such that ${c_{K_p,e_p(P_p)} \neq 0}$, and let ${q_0 := \prod_{p|{\mathcal P}} p}$. Then for any ${N > 0}$ of polynomial size, any factorisation ${q = q_1 \ldots q_l}$, and any coefficient sequence function ${\psi_N(n)}$ which is smooth at scale ${N}$, one has

$\displaystyle |\sum_n \psi_N(n) K_q(n)| \lessapprox q_0 (1 + \sum_{i=1}^{l-1} (N')^{1-1/2^i} (q'_i)^{1/2^i}$

$\displaystyle + (N')^{1-1/2^{l-1}} (q'_l)^{1/2^l})+ N (q')^{-1/2}$

where ${q' := q / q_0}$, ${N' := N/q_0}$, and ${q'_i := (q_i,q')}$, where the sum is implicitly assumed to range over those ${n}$ for which ${K_q(n)}$ is defined.

The ${q_0}$ parameter is technical, as is the ${1}$ term; heuristically one should view this estimate as asserting that

$\displaystyle |\sum_n \psi_N(n) K_q(n)| \lessapprox \sum_{i=1}^{l-1} N^{1-1/2^i} q_i^{1/2^i} + N^{1-1/2^{l-1}} q_l^{1/2^l}$

under reasonable non-degeneracy conditions. Assuming sufficient dense divisibility and in the regime ${N \geq q^{1/(l+1)}}$, the optimal value of the right-hand side is ${\epsilon N}$, where ${\epsilon := (q/N^{l+1})^{1/(2^{l+1}-2)}}$, which is attained when ${q_i := N \epsilon^{2^i}}$ for ${i=1,\ldots,l-1}$ and ${q_{l} := q_{l-1}^2}$.

Proof: We induct on ${l}$, assuming that the claim has already been proven for all smaller values of ${l}$.

We may factor ${K_q = K_{q_0} K_{q'}}$ where ${K_{q_0} := \prod_{p|q_0} K_p}$ and ${K_{q'} := \prod_{p|q'} K_p}$. Then we may write

$\displaystyle \sum_n \psi_N(n) K_q(n) = \sum_{a=0}^{q_0-1} K_{q_0}(a) \sum_n \psi_N( q_0 n + a ) K_{q'}(q_0n+a).$

Observe that any given ${a}$, ${K_{q_0}(a)}$ has magnitude ${|K_{q_0}(a)| \lessapprox 1}$ (from the divisor bound), the function ${n \mapsto \psi_N(q_0n+a)}$ is of the form ${\tilde \psi( \frac{n}{N'} )}$ for some ${\tilde \psi}$ supported on an interval of length ${\lessapprox 1}$ and obeying the bounds ${|\nabla^j \tilde \psi(x)| \lessapprox 1}$, and the function ${n \mapsto K_{q'}(q_0 n+a)}$ is a structured function of modulus ${q'}$ and complexity at most ${O(1)}$ (here we use the dilation and translation invariance properties of structured functions). From this we see that to prove the proposition for a given value of ${l}$, it suffices to do so under the assumption ${q_0=1}$, in which case the objective is to prove that

$\displaystyle |\sum_n \psi_N(n) K_q(n)| \lessapprox 1 + \sum_{i=1}^{l-1} N^{1-1/2^i} q_i^{1/2^i} + N^{1-1/2^{l-1}} q_l^{1/2^l}$

$\displaystyle + N q^{-1/2} 1_{N \geq A q}.$

The claim is trivial (from the divisor bound) with ${N \leq 1}$, so we may assume ${N \geq 1}$, in which case we will show that

$\displaystyle |\sum_n \psi_N(n) K_q(n)| \lessapprox \sum_{i=1}^{l-1} N^{1-1/2^i} q_i^{1/2^i} + N^{1-1/2^{l-1}} q_l^{1/2^l}$

$\displaystyle + N q^{-1/2} 1_{N \geq A q}.$

By applying a similar reduction to before we may also assume that all prime factors of ${q}$ are larger than some large fixed constant ${C}$, which we will assume to be sufficiently large for the arguments below to work.

We begin with the base case ${l=1}$. In this case it will suffice to establish the bound

$\displaystyle |\sum_n \psi_N(n) K_q(n)| \lessapprox q^{1/2} + N q^{-1/2}.$

By completion of sums, it will suffice to show that

$\displaystyle \sum_{n \in {\bf Z}/q{\bf Z}} e_q( hn) K_q(n)| \lessapprox q^{1/2}$

for all ${h \in {\bf Z}/q{\bf Z}}$. By the Chinese remainder theorem and the divisor bound, it will suffice to show that

$\displaystyle \sum_{n \in {\bf Z}/p{\bf Z}} e_p( hn) K_p(n)| \ll p^{1/2}$

for all ${p|q}$ and all ${h \in {\bf Z}/q{\bf Z}}$. However, by the hypothesis ${q_0=1}$, ${e_p(h \cdot) K_p \not \equiv 1}$, and the claim now follows from the almost orthogonality properties of structured functions.

Now suppose that ${l > 1}$, and the claim has already been proven for smaller values of ${l}$. If ${N \geq q}$ then the claim follows from the ${l=1}$ bound, so we may assume that ${N < q}$, in which case we will establish

$\displaystyle |\sum_n \psi_N(n) K_q(n)| \lessapprox \sum_{i=1}^{l-1} N^{1-1/2^i} q_i^{1/2^i} + N^{1-1/2^{l-1}} q_l^{1/2^l}.$

If we have ${N \geq q_l}$, then

$\displaystyle N^{1-1/2^{l-1}} q_{l-1}^{1/2^{l-1}} + N^{1-1/2^{l-1}} q_l^{1/2^l} \geq N^{1-1/2^{l-2}} (q_{l-1} q_l)^{1/2^{l-1}}$

and the claim then follows by the induction hypothesis (concatenating ${q_l}$ and ${q_{l-1}}$). Similarly, if ${N \leq q_1}$, then ${N^{1/2} q_1^{1/2} \geq N}$, and the claim follows from the triangle inequality. Thus we may assume that

$\displaystyle q_1 < N < q_l.$

Let ${M := \lfloor N/q_1\rfloor}$. We can rewrite ${\sum_n \psi_N(n) K_q(n)}$ as

$\displaystyle \frac{1}{M} \sum_n \sum_{m=1}^M \psi_N(n+kq_1) K_q(n+mq_1).$

We factor

$\displaystyle K_q(n+mq_1) = K_{q_1}(n) K_{q_2 \ldots q_l}(n+mq_1)$

and by the divisor bound ${|K_{q_1}(n)| \lessapprox 1}$, and so by the triangle inequality and the Cauchy-Schwarz inequality

$\displaystyle |\sum_n \psi_N(n) K_q(n)| \lessapprox \frac{1}{M} \sum_n |\sum_{m=1}^M \psi_N(n+mq_1) K_{q_2 \ldots q_l}( n+mq_1 )|$

$\displaystyle \lessapprox \frac{N^{1/2}}{M} (\sum_n |\sum_{m=1}^M \psi_N(n+mq_1) K_{q_2 \ldots q_l}( n+mq_1 )|^2)^{1/2}$

since the summand is only non-zero when ${n}$ is supported on an interval of length ${\lessapprox N}$. This last expression may be rearranged as

$\displaystyle \frac{N^{1/2}}{M} |\sum_{1 \leq m,m' \leq M} \sum_n \psi_N(n+mq_1) \overline{\psi_N(n+m'q_1)}$

$\displaystyle K_{q_2 \ldots q_l}( n+mq_1 ) \overline{K_{q_2 \ldots q_l}}(n+m'q_1)|^{1/2}.$

The diagonal contribution ${m=m'}$ can be estimated (using the pointwise bounds ${|K_{q_2\ldots q_l}| \lessapprox 1}$) by ${\lessapprox \frac{N^{1/2}}{M} ( M N )^{1/2} \lessapprox N^{1/2} q_1^{1/2}}$, which is acceptable, so it suffices to show that

$\displaystyle |\sum_{1 \leq m,m' \leq M: m \neq m'} \sum_n \psi_N(n+mq_1) \overline{\psi_N(n+m'q_1)} \ \ \ \ \ (9)$

$\displaystyle K_{q_2 \ldots q_l}( n+mq_1 )\overline{K_{q_2 \ldots q_l}}(n+m'q_1) |$

$\displaystyle \lessapprox M^2 ( \sum_{i=2}^{l-1} N^{1-1/2^{i-1}} q_i^{1/2^{i-1}} + N^{1-1/2^{l-2}} q_l^{1/2^{l-1}} ).$

We observe that ${n \mapsto K_{q_2 \ldots q_l}( n+mq_1 )\overline{K_{q_2 \ldots q_l}}(n+m'q_1)}$ is the sum of ${\lessapprox 1}$ structured functions of modulus ${q_2 \ldots q_l}$ and complexity ${O(1)}$, each of which the product of one of the components of ${K_p( n+mq_1) \overline{K_p}(n+m'q_1)}$ of modulus ${p}$ and complexity ${O(1)}$ for all ${p|q_2 \ldots q_l}$. We can of course delete any components that vanish identically. Suppose that for one of these primes ${p}$, one of the components of the function ${K_p( n+mq_1) \overline{K_p}(n+m'q_1)}$ is equivalent to ${e_p( P(n) )}$ for some polynomial ${P}$ of degree at most ${l-1}$. Then by Lemma 10, if ${p}$ is sufficiently large (larger than a fixed constant), either ${p|m'-m}$, or else ${K_p(n)}$ is equivalent ${e_p(Q)}$ for some polynomial ${Q}$ of degree at most ${l}$, but by the hypothesis ${q_0=1}$ the latter case cannot occur since ${K_p}$ is non-vanishing and ${c_{K_p,e_p(Q)} = 0}$. Thus if we set ${\tilde q_0}$ to be the product of all the primes ${p}$ with this property, we see that ${\tilde q_0 \ll (m'-m,q_2 \ldots q_l)}$.

Applying the induction hypothesis, we may thus bound

$\displaystyle |\sum_n \psi_N(n+mq_1) \overline{\psi_N(n+m'q_1)} K_{q_2 \ldots q_l}( n+ mq_1) \overline{K_{q_2 \ldots q_l}}( n+ m'q_1)$

by

$\displaystyle \lessapprox (q_2 \ldots q_l, m-m') [ \sum_{i=2}^{l-1} N^{1-1/2^{i-1}} q_i^{1/2^{i-1}} + N^{1-1/2^{l-2}} q_l^{1/2^{l-1}} ]$

$\displaystyle + N (q_2 \ldots q_l)^{-1/2} (q_2 \ldots q_l, m-m')^{1/2}.$

The contribution of the first two terms to (9) is acceptable thanks to Lemma 5 of this previous post, so the only contribution remaining to control is

$\displaystyle \sum_{1 \leq m,m' \leq M: m \neq m'} N (q_2 \ldots q_l)^{-1/2} (q_2 \ldots q_l, m-m')^{1/2}.$

We may bound

$\displaystyle N (q_2 \ldots q_l)^{-1/2} (q_2 \ldots q_l, m-m')^{1/2} \ll N^{1/2} + N^{3/2} (q_2 \ldots q_l)^{-1} (q_2 \ldots q_l, m-m').$

The first term is dominated by the ${N^{1/2} q_1^{1/2}}$ term appearing as the ${i=1}$ summand in (9), while the contribution of the second term may be bounded using another application of Lemma 5 of this previous post and the bound ${N < q_l}$ by

$\displaystyle \lessapprox K^2 N^{1-1/2^{l-2}} q_l^{1/2^{l-1}}$

which is acceptable. $\Box$

Remark 1 The above arguments relied on a ${q}$-version of the van der Corput ${A}$-process, and in the case of Dirichlet characters is essentially due to Graham and Ringrose (see also Heath-Brown). If we work with a class of structured functions that is closed under Fourier transforms (such as the trace weights), then the ${q}$-version of the van der Corput ${B}$-process also becomes available (in principle, at least), thus potentially giving a slightly larger range of “exponent pairs”; however this looks complicated to implement (the role of polynomial phases now needs to be replaced by a more complicated class that involves things like the Fourier transforms of polynomial phases, as well as their “antiderivatives”) and will likely only produce rather small improvements in the final numerology.

We isolate a special case of the above result:

Corollary 12 Let the notation and assumptions be as in Proposition 11 with ${l=2}$, ${N \geq 1}$, and ${q}$ ${y}$-densely divisible. Then for any ${N > 0}$, one has the bounds

$\displaystyle |\sum_n \psi_N(n) K_q(n)| \lessapprox q_0 + q_0^{1/2} q^{1/2} + N q_0^{1/2} q^{-1/2}$

and

$\displaystyle |\sum_n \psi_N(n) K_q(n)| \lessapprox q_0 + q_0^{1/2} N^{1/2} q^{1/6} y^{1/6} + N q_0^{1/2} q^{-1/2}.$

The dependence on ${q_0}$ in the first bound can be improved, but we will not need this improvement here.

Proof: From the ${l=1}$ case of the above proposition we have

$\displaystyle |\sum_n \psi_N(n) K_q(n)| \lessapprox q_0 (1 + (q/q_0)^{1/2}) + N (q/q_0)^{-1/2}$

giving the first claim of the proposition.

Similarly, from the ${l=2}$ case of the above proposition we have

$\displaystyle |\sum_n \psi_N(n) K_q(n)| \lessapprox q_0 (1 + (N')^{1/2} (q_1)^{1/2} + (N')^{1/2} (q_2)^{1/4} )$

$\displaystyle + N q_0^{1/2} q^{-1/2}$

for any factorisation ${q=q_1q_2}$ of ${q}$. As ${q}$ is ${y}$-densely divisible, we may select ${q_1}$ so that

$\displaystyle y^{-2/3} q^{1/3} \leq q_1 \leq y^{1/3} q^{1/3}$

so that

$\displaystyle y^{-1/3} q^{2/3} \leq q_2 \leq y^{2/3} q^{2/3}$

and the second claim follows. $\Box$

— 3. A two-dimensional exponential sum —

We now apply the above theory to obtain a new bound on a certain two-dimensional exponential sum that will show up in the Type I estimate.

Proposition 13 Let ${u}$ be a ${y}$-densely divisible squarefree integer of polynomial size for some ${y \geq 1}$, let ${D, N > 0}$ be of polynomial size, and let ${c,l,v,a,b \in {\bf Z}/u{\bf Z}}$. Let ${\psi_D, \psi_N}$ be smooth sequences at scale ${D, N}$ respectively. Then

$\displaystyle |\sum_d \sum_n \psi_D(d) \psi_N(n) e_u( \frac{cl}{(n+vd+a)(n+vd+ld+b)} )|$

$\displaystyle \lessapprox (cl,u) (u^{1/2} + \frac{N}{u^{1/2}}) ( 1 + D^{1/2} u^{1/6} y^{1/6} + \frac{D}{u^{1/2}}).$

Here the summations are implicitly restricted to those ${d,n}$ for which the denominator in the phase is non-zero. We also have the bound

$\displaystyle |\sum_d \sum_n \psi_D(d) \psi_N(n) e_u( \frac{cl}{(n+vd+a)(n+vd+ld+b)} )|$

$\displaystyle \lessapprox (cl,u) ( u^{1/2} + \frac{N}{u^{1/2}}) ( u^{1/2} + \frac{D}{u^{1/2}}).$

The main term here is ${(cl,u) u^{1/2} \times (D^{1/2} u^{2/3} y^{1/6})}$, which in certain regimes improves upon the bound of ${((cl,u)^{-1/2} u^{1/2}) \times D}$ that one obtains by completing the sums in the ${n}$ variable but not exploiting any additional cancellation in the ${d}$ variable.

Proof: We first claim that it suffices to verify the proposition when ${(cl,u)=1}$. Indeed, if we set

$\displaystyle u' := u / (cl,u)$

$\displaystyle y' := y (cl,u)$

$\displaystyle c' := c/(cl,u) = \frac{c/(c,u)}{(cl,u)/(c,u)}$

(where one computes the reciprocal of ${(cl,u)/(c,u)}$ inside ${{\bf Z}/(u/(cl,u)){\bf Z}}$), we see that ${u'}$ is ${y'}$-densely divisible (thanks to Lemma 7), squarefree, and polynomial size, that ${(c'l,u')=1}$, and that

$\displaystyle \sum_d \sum_n \psi_D(d) \psi_N(n) e_u( \frac{cl}{(n+vd+a)(n+vd+ld+b)} )$

$\displaystyle = \sum_d \sum_n \psi_D(d) \psi_N(n) e_{u'}( \frac{c'l}{(n+vd+a)(n+vd+ld+b)} )$

$\displaystyle \prod_{p|(cl,u)} 1_{p \not | (n+vd+a)(n+vd+ld+b)}.$

By the inclusion-exclusion formula and divisor bound, it thus suffices to show that for all ${f | (cl,u)}$, one has

$\displaystyle |\sum_d \sum_n \psi_D(d) \psi_N(n) e_{u'}( \frac{c'l}{(n+vd+a)(n+vd+ld+b)} )$

$\displaystyle 1_{f|(n+vd+a)(n+vd+ld+b)}| \lessapprox X$

where ${X}$ is either of the two right-hand sides in the proposition, i.e. either

$\displaystyle X = (cl,u) (u^{1/2} + \frac{N}{u^{1/2}})$

or

$\displaystyle X = (cl,u) ( u^{1/2} + \frac{N}{u^{1/2}}) ( u^{1/2} + \frac{D}{u^{1/2}}).$

By the divisor bound, we see that there are ${\lessapprox f}$ pairs ${(n_0,d_0) \in ({\bf Z}/f{\bf Z})^2}$ such that ${(n_0+vd_0+a)(n_0+vd_0+ld_0+b) = 0\ (f)}$. Thus it will suffice to show that

$\displaystyle |\sum_{d=d_0\ (f)} \sum_{n=n_0\ (f)} \psi_D(d) \psi_N(n) e_{u'}( \frac{c'l}{(n+vd+a)(n+vd+ld+b)} )| \lessapprox X/f.$

Making the change of variables ${d = fd' +d_0}$, ${n = fn'+n_0}$ and using the ${(cl,u)=1}$ case of the proposition, we can bound the left-hand side by

$\displaystyle ((u')^{1/2} + \frac{N/f}{(u')^{1/2}}) ( 1 + (D/f)^{1/2} (u')^{1/6} (y')^{1/6} + \frac{D/f}{(u')^{1/2}})$

and

$\displaystyle ((u')^{1/2} + \frac{N/f}{(u')^{1/2}}) ( (u')^{1/2} + \frac{D/f}{(u')^{1/2}})$

and one verifies that these two quantities bound the two possible values of ${X/f}$ respectively.

Henceforth ${(cl,u)=1}$. Note that the above reduction also allows us to assume that ${u}$ has no prime factors less than a sufficiently large fixed constant ${C}$ to be chosen later. Our task is now to show that

$\displaystyle |\sum_d \sum_n \psi_D(d) \psi_N(n) e_u( \frac{cl}{(n+vd+a)(n+vd+ld+b)} )|$

$\displaystyle \lessapprox (\frac{N}{u}+1) (u^{1/2} + D^{1/2} u^{2/3} y^{1/6} + D)$

and

$\displaystyle |\sum_d \sum_n \psi_D(d) \psi_N(n) e_u( \frac{cl}{(n+vd+a)(n+vd+ld+b)} )|$

$\displaystyle \lessapprox (\frac{N}{u}+1) (u + D).$

From completion of sums we have

$\displaystyle |\sum_d \sum_n \psi_D(d) \psi_N(n) e_u( \frac{cl}{(n+vd+a)(n+vd+ld+b)} )|$

$\displaystyle \lessapprox (\frac{N}{u}+1) \sup_{m \in{\bf Z}/u{\bf Z}} |\sum_d \sum_{n \in {\bf Z}/u{\bf Z}} \psi_D(d)$

$\displaystyle e_u( \frac{cl}{(n+vd+a)(n+vd+ld+b)} + mn)|$

so it will suffice to show that

$\displaystyle |\sum_d \sum_{n \in {\bf Z}/u{\bf Z}} \psi_D(d) e_u( \frac{cl}{(n+vd+a)(n+vd+ld+b)} + mn)|$

$\displaystyle \lessapprox u^{1/2} + D^{1/2} u^{2/3} y^{1/6} + D$

and

$\displaystyle |\sum_d \sum_{n \in {\bf Z}/u{\bf Z}} \psi_D(d) e_u( \frac{cl}{(n+vd+a)(n+vd+ld+b)} + mn)|$

$\displaystyle \lessapprox u + D$

for any given ${m \in {\bf Z}/u{\bf Z}}$. We rewrite this as

$\displaystyle |\sum_d \psi_D(d) K_u(d)| \lessapprox \min( 1 + D^{1/2} u^{1/6} y^{1/6}, u^{1/2}) + D u^{-1/2} \ \ \ \ \ (10)$

where

$\displaystyle K_u(d) := \frac{1}{\sqrt{u}} \sum_{n \in {\bf Z}/u{\bf Z}} e_u( \frac{cl}{(n+vd+a)(n+vd+ld+b)} + mn).$

By the Chinese remainder theorem, this function factors as ${K_u(d) = \prod_{p|u} K_p(d)}$, where

$\displaystyle K_p(d) := \frac{1}{\sqrt{p}} \sum_{n \in {\bf Z}/p{\bf Z}} e_p( \frac{1}{u_p} ( \frac{cl}{(n+vd+a)(n+vd+ld+b)} + mn ) )$

and ${u_p := u/p}$. Note that for any prime ${p}$ dividing ${u}$ (and thus larger than ${C}$), the rational function ${n \mapsto \frac{1}{u_p} ( \frac{cl}{n(n+ld+b-a)} + mn )}$ is not divisible by ${p}$. From the Weil conjectures for curves this implies that ${K_p(d) = O(1)}$. In fact, from Deligne’s theorem (and in particular the fact that cohomology groups of sheaves are again sheaves), we have the stronger assertion that ${K_p}$ is a sum of boundedly many trace weights at modulus ${p}$ with complexity ${O(1)}$ in the sense of Example 4. (In the Grothendieck-Lefschetz trace formula, only the first cohomology ${H^1_c}$ is non-trivial; the second cohomology ${H^2_c}$ disappears because the rational function is not divisible by ${p}$, and the zeroth cohomology ${H^0_c}$ disappears because the underlying curve is affine, although in any event the contribution of the zeroth cohomology could be absorbed into the ${Du^{-1/2}}$ term in (10).) By the divisor bound, this implies that ${K_u}$ is the sum of ${\lessapprox 1}$ trace weights at modulus ${u}$ with complexity ${O(1)}$. We can of course delete any components that vanish identically.

We claim that for any ${p}$ dividing ${u}$ (and hence larger than ${C}$), none of the components of ${K_p(d)}$ are equivalent to a quadratic phase ${e_p( ed^2+fd )}$. Assuming this claim for the moment, the required bound (10) then follows from Corollary 12. It thus suffices to verify the claim. If the claim failed, then we would have

$\displaystyle \sum_{d \in {\bf Z}/p{\bf Z}} K_p(d) e_p( - ed^2 - fd ) = \alpha p + O(\sqrt{p}) \ \ \ \ \ (11)$

for some algebraic integer ${\alpha}$, which is non-zero since ${K_p(d)}$ is equivalent to ${e_p(ed^2+f d)}$ and is non-zero. Since all non-zero algebraic integers have at least one Galois conjugate of modulus at least ${1}$, it will suffice (for ${p}$ large enough) to establish that all Galois conjugates of the left-hand side of (27) are ${O(\sqrt{p})}$. In other words, it suffices to establish the bound

$\displaystyle |\sum_{d,n \in {\bf Z}/p{\bf Z}} e_p( g ( \frac{1}{u_p} ( \frac{cl}{(n+vd+a)(n+vd+ld+b)} + mn ) - ed^2 - fd ) )|$

$\displaystyle \ll p$

for all ${g \in ({\bf Z}/p{\bf Z})^\times}$. Setting ${x := n+vd+a}$ and ${y := ld+b}$ and concatenating parameters, it suffices to show that

$\displaystyle |\sum_{x,y \in {\bf Z}/p{\bf Z}} e_p( \frac{c}{x (x+y)} - ax - by - dy^2 )| \ll p$

whenever ${c \in ({\bf Z}/p{\bf Z})^\times}$ and ${a,b,d \in {\bf Z}/p{\bf Z}}$.

We now use a result of Hooley, which asserts that for any rational function ${f(x,y)}$ of two variables and bounded degree, one has

$\displaystyle |\sum_{x,y \in {\bf Z}/p{\bf Z}} e_p( f(x,y) )| \ll p$

provided that

$\displaystyle \{ (x,y): f(x,y)-T = 0\}$

is a geometrically generically irreducible curve (i.e. irreducible over an algebraic closure ${k := \overline{{\Bbb F}_p(T)}}$ of ${k_0 := {\Bbb F}_p(T)}$) and also that

$\displaystyle \{ (x,y): f(x,y)-t = 0 \}$

is a (possibly reducible or empty) curve for any ${t \in \overline{F}_p}$. We apply this result to the rational function

$\displaystyle f(x,y) := \frac{c}{x (x+y)} - ax - by - dy^2.$

For any ${t}$, it is clear that ${f(x,y)-t}$ is not identically zero, so the second condition of Hooley is satisfied. It remains to verify the first. (Thanks to Brian Conrad for fixing some errors in the argument that follows.) Suppose that the claim failed, thus ${f(x,y)-T}$ is reducible for generic ${T}$, or equivalently that the polynomial

$\displaystyle P(x,y) := c - (ax + by + dy^2 - T) (x(x+y))$

is reducible in ${k[x,y]}$. Being linear in ${T}$, this polynomial ${P}$ is clearly irreducible in ${{\Bbb F}_p[x,y,T] = {\Bbb F}_p[T][x,y]}$; since ${P}$ does not lie in ${{\Bbb F}_p[T]}$, it remains irreducible in the larger ring ${k_0[x,y]}$ by Gauss’s lemma.

We now perform a technical reduction to deal with the problem that the field ${k_0}$ is not perfect. Since ${P}$ involves the nonzero term ${Txy}$ as its only ${xy}$-term, over ${k}$ it cannot be a constant multiple of a ${p}$-power. Hence, if it is irreducible over the separable closure ${k_{0,s}}$ of ${k_0}$ then it remains irreducible over the perfect closure ${k}$ of ${k_{0,s}}$, so it suffices to check irreducibility over the separable closure.

Assuming ${P}$ is reducible over the separable closure, then up to constant multipliers (i.e. multiples in ${k_{0,s}}$) its irreducible factors in ${k_{0,s}[x,y]}$ must be Galois conjugate to each other with respect to ${{\rm{Gal}}(k_{0,s}/k_0)}$. Thus, none of these factors can lie in ${k_{0,s}[x]}$ or ${k_{0,s}[y]}$, as otherwise all the factors would and hence so would their product ${P}$ (a contradiction since ${c \ne 0}$). Thus, the irreducible factorization over ${k_{0,s}[x,y]}$ remains an irreducible factorization in ${k_{0,s}(x)[y]}$ and over ${k_{0,s}(y)[x]}$. Since ${P}$ has nonzero constant term and degree at most ${3}$ in either ${x}$ or ${y}$, this implies that the irreducible factors of ${P}$ in ${k[x,y]}$ are linear in both ${x}$ and ${y}$, thus

$\displaystyle P(x,y) = \prod_{i=1}^3 (\alpha_i x + \beta_i y + \gamma_i)$

for some ${\alpha_i, \beta_i \in k}$ and ${\gamma_i \in k^{\times}}$. But ${P(0,y)}$ is visibly constant, so all ${\beta_i}$ vanish and hence ${P \in k[x]}$, an absurdity. $\Box$

— 4. Type I estimate —

We begin the proof of Theorem 4, closely following the arguments from Section 5 of this previous post or Section 2 of this previous post. One difference however will be that we will not discard the ${r}$ averaging as we will need it near the end of the argument. Let ${I, a, N, M, \alpha}$ be as in the theorem. We can restrict ${q}$ to the range

$\displaystyle q \gtrapprox x^{1/2}$

for some sufficiently slowly decaying ${o(1)}$, since otherwise we may use the Bombieri-Vinogradov theorem (Theorem 4 from this previous post). Thus, by dyadic decomposition, we need to show that

$\displaystyle \sum_{d \in {\mathcal S}_I \cap {\mathcal D}_{x^\delta}^4: D \leq d < 2D} |\Delta(\alpha \ast \beta; a\ (d))| \ll NM \log^{-A} x. \ \ \ \ \ (12)$

for any fixed ${A}$ and for any ${D}$ in the range

$\displaystyle x^{1/2} \lessapprox D \lessapprox x^{1/2+2\varpi}.$

Let

$\displaystyle \epsilon > 0 \ \ \ \ \ (13)$

be a sufficiently small fixed exponent.

By Lemma 11 of this previous post, we know that for all ${d}$ in ${[D,2D]}$ outside of a small number of exceptions, we have

$\displaystyle \prod_{p|d: p \leq D_0} p \lessapprox 1 \ \ \ \ \ (14)$

where

$\displaystyle D_0 := \exp(\log^{1/3} x). \ \ \ \ \ (15)$

Specifically, the number of exceptions in the interval ${[D,2D]}$ is ${O(D \log^{-A} x)}$ for any fixed ${A>0}$. The contribution of the exceptional ${d}$ can be shown to be acceptable by Cauchy-Schwarz and trivial estimates (see Section 5 of this previous post), so we restrict attention to those ${d}$ for which (14) holds. In particular, as ${d}$ is restricted to be quadruply ${x^\delta}$-densely divisible, we may factor

$\displaystyle d=qr$

with ${q,r}$ coprime and square-free, with ${q \in {\mathcal S}_{I'}}$ ${x^{\delta+o(1)}}$-densely divisible with ${I' := [D_0,\infty) \cap I}$, ${r \in {\mathcal S}_I}$ doubly ${x^{\delta+o(1)}}$-densely divisible,and

$\displaystyle x^{-\epsilon-\delta} N \lessapprox r \lessapprox x^{-\epsilon} N$

and

$\displaystyle x^{1/2} \lessapprox qr \lessapprox x^{1/2+2\varpi}.$

Here we use the easily verified fact that ${N \gtrapprox x^\epsilon}$, and we have also used Lemma 7 to ensure that dense divisibility is essentially preserved when transferring a factor of ${x^{o(1)}}$ from ${r}$ (namely, the portion of ${r}$ coming from primes up to ${D_0}$) to ${q}$.

By dyadic decomposition, it thus suffices to show that

$\displaystyle \sum_{q \in {\mathcal S}_{I'} \cap {\mathcal D}_{x^\delta+o(1)}: q \sim Q} \sum_{r \in {\mathcal S}_I \cap {\mathcal D}_{x^\delta+o(1)}^{(2)}: r \sim R} |\Delta(\alpha \ast \beta; a\ (qr))| \ll NM \log^{-A} x.$

for any fixed ${A>0}$, where ${Q, R \geq 1}$ obey the size conditions

$\displaystyle x^{-\epsilon-\delta} N \lessapprox R \lessapprox x^{-\epsilon} N \ \ \ \ \ (16)$

and

$\displaystyle x^{1/2} \lessapprox QR \lessapprox x^{1/2 + 2\varpi}. \ \ \ \ \ (17)$

Fix ${Q,R}$. We abbreviate ${\sum_{q \in {\mathcal S}_{I'} \cap {\mathcal D}_{x^\delta+o(1)}: q \sim Q}}$ and ${\sum_{r \in {\mathcal S}_I \cap {\mathcal D}_{x^{\delta+o(1)}}^2: r \sim R}}$ by ${\sum_q}$ and ${\sum_r}$ respectively, thus our task is to show that

$\displaystyle \sum_q \sum_{r: (q,r)=1} |\Delta(\alpha \ast \beta; a\ (qr))| \ll NM \log^{-A} x.$

We now split the discrepancy

$\displaystyle \Delta(\alpha \ast \beta; a\ (qr)) = \sum_{n = a\ (qr)} \alpha \ast \beta(n) - \frac{1}{\phi(qr)} \sum_{n: (n,qr)=1} \alpha \ast \beta(n)$

as the sum of the subdiscrepancies

$\displaystyle \sum_{n: n = a\ (qr)} \alpha \ast \beta(n) - \frac{1}{\phi(q)} \sum_{n: (n,q)=1; n = a\ (r)} \alpha \ast \beta(n)$

and

$\displaystyle \frac{1}{\phi(q)} \sum_{n: (n,q)=1; n = a\ (r)} \alpha \ast \beta(n) - \frac{1}{\phi(qr)} \sum_{n: (n,qr)=1} \alpha \ast \beta(n).$

In Section 5 of this previous post, it was established (using the Bombieri-Vinogradov theorem) that

$\displaystyle \sum_{q} \sum_{r; (q,r)=1} |\frac{1}{\phi(q)} \sum_{n: (n,q)=1; n = a\ (r)} \alpha \ast \beta(n) - \frac{1}{\phi(qr)} \sum_{n: (n,qr)=1} \alpha \ast \beta(n)|$

$\displaystyle NM \log^{-A} x$

so it suffices to show that

$\displaystyle \sum_{q} \sum_{r; (q,r)=1} |\sum_{n: n = a\ (qr)} \alpha \ast \beta(n) - \frac{1}{\phi(q)} \sum_{n: (n,q)=1; n = a\ (r)} \alpha \ast \beta(n)| \ \ \ \ \ (18)$

$\displaystyle \ll NM \log^{-A} x.$

It will suffice to prove the slightly stronger statement

$\displaystyle \sum_r \sum_{q: (q,r)=1} |\sum_{n: n = a\ (r); n= b\ (q)} \alpha \ast \beta(n) - \sum_{n: (n,q)=1; n = a\ (r); n = b'\ (q)} \alpha \ast \beta(n)| \ \ \ \ \ (19)$

$\displaystyle \ll NM \log^{-A} x$

for all ${a,b,b'}$ coprime to ${P_I}$, since if one then specialises to the case when ${b=a}$ and averages over all primitive ${b'\ (P_I)}$ we obtain (18) from the triangle inequality.

We use the dispersion method. We write the left-hand side of (19) as

$\displaystyle \sum_r \sum_{q: (q,r)=1} c_{q,r} (\sum_{n: n = a\ (r); n= b\ (q)} \alpha \ast \beta(n) - \sum_{n: n = a\ (r); n = b'\ (q)} \alpha \ast \beta(n))$

for some bounded sequence ${c_{q,r}}$. This expression may be rearranged as

$\displaystyle \sum_r \sum_m \alpha(m) (\sum_{q,n: mn = a\ (r); (q,r)=1} c_{q,r} \beta(n) (1_{mn = b\ (q)} - 1_{mn = b'\ (q)})),$

so from the Cauchy-Schwarz inequality and crude estimates it suffices to show that

$\displaystyle \sum_r \sum_{m} \psi_M(m) |\sum_{q,n: mn = a\ (r); (q,r)=1} c_{q,r} \beta(n) (1_{mn = b\ (q)} - 1_{mn = b'\ (q)})|^2 \ \ \ \ \ (20)$

$\displaystyle \ll N^2 M R^{-1} \log^{-A} x$

for any fixed ${A>0}$, where ${\psi_M}$ is a smooth coefficient sequence at scale ${M}$. Expanding out the square, it suffices to show that

$\displaystyle \sum_r \sum_{m} \psi_M(m) \sum_{q_1,q_2,n_1,n_2: mn_1=mn_2 = a\ (r); (q_1q_2,r)=1} \ \ \ \ \ (21)$

$\displaystyle c_{q_1,r} \overline{c_{q_2,r}} \beta(n_1) \overline{\beta(n_2)} 1_{mn_1 = b\ (q_1)} 1_{mn_2 = b'\ (q_2)}$

$\displaystyle = X + O( N^2 M R^{-1} \log^{-A} x )$

where ${q_1,q_2}$ is subject to the same constraints as ${q}$ (thus ${q_i \in {\mathcal S}_{I'} \cap {\mathcal D}_{x^\delta}}$ and ${q_i \sim Q}$ for ${i=1,2}$), and ${X}$ is some quantity that is independent of ${b,b'}$.

Observe that ${n_1}$ must be coprime to ${q_1r}$ and ${n_2}$ coprime to ${q_2r}$, with ${n_1 = n_2\ (r)}$, to have a non-zero contribution to (21). We then rearrange the left-hand side as

$\displaystyle \sum_r \sum_{q_1,q_2: (q_1q_2,r)=1} \sum_{m} \psi_M(m) \sum_{n_1,n_2: n_1=n_2\ (r); (n_1,q_1r)=(n_2,q_2)=1}$

$\displaystyle c_{q_1,r} \overline{c_{q_2,r}} \overline{\beta(n_1)} \overline{\beta(n_2)} 1_{m = a/n_1\ (r); m = b/n_1\ (q_1); m = b'/n_2 (q_2)};$

note that these inverses in the various rings ${{\bf Z}/r{\bf Z}}$, ${{\bf Z}/q_1{\bf Z}}$, ${{\bf Z}/q_2{\bf Z}}$ are well-defined thanks to the coprimality hypotheses.

We may write ${n_2 = n_1+kr}$ for some ${k = O(N/R)}$. By the triangle inequality, and relabeling ${n_1}$ as ${n}$, it thus suffices to show that

$\displaystyle \sum_r \sum_{k = O(N/R)} \sum_{q_1,q_2: (q_1q_2,r)=1} |\sum_{n; (n,q_1r)=(n+kr,q_2)=1} \ \ \ \ \ (22)$

$\displaystyle c_{q_1} \overline{c_{q_2}} \beta(n) \overline{\beta(n+kr)} \sum_{m} \psi_M(m) 1_{m = a/n\ (r); m = b/n\ (q_1); m = b'/(n+kr) (q_2)}|$

$\displaystyle = X + O( N^2 M R^{-1} \log^{-A} x )$

for some ${X}$ independent of ${b}$, ${b'}$.

At this stage in previous posts we isolated the coprime case ${(q_1,q_2)=1}$ as the dominant case, using a controlled multiplicity hypothesis to deal with the non-coprime case. Here, we will carry the non-coprime case with us for a little longer so as not to rely on a controlled multiplicity hypothesis; this introduces some additional factors of ${q_0 := (q_1,q_2)}$ into the analysis but they should be ignored on a first reading.

Applying completion of sums (Section 2 from this previous post), we can express the left-hand side of (22) as a main term

$\displaystyle \sum_r \sum_{k = O(N/R)} \sum_{q_1,q_2: (q_1q_2,r)=1} |\sum_{n; (n,q_1r)=(n+kr,q_2)=1} \ \ \ \ \ (23)$

$\displaystyle c_{q_1,} \overline{c_{q_2,r}} \beta(n) \overline{\beta(n+kr)} (\sum_{m} \psi_M(m)) \frac{1}{r[q_1,q_2]} 1_{b/n = b'/(n+kr)\ ((q_1,q_2))}$

plus an error term

$\displaystyle O( \frac{1}{H} \sum_r \sum_{k=O(N/R)} \sum_{1 \leq h \leq H} \sum_{q_1,q_2} |\sum_{n} \beta(n) \beta(n+kr) \Phi_{k,r}(h,q_1,q_2; n)| ) \ \ \ \ \ (24)$

$\displaystyle + O( x^{-A} ),$

where

$\displaystyle H := x^\epsilon Q^2 R/M \ \ \ \ \ (25)$

and ${\Phi_{k,r}}$ is the phase

$\displaystyle \Phi_{k,r}(h,q_1,q_2;n) := 1_{(n,r)=(n,q_1)=(n+kr,q_2)=1} 1_{q_1,q_2 \in {\mathcal S}_I \cap {\mathcal D}_{x^{\delta+o(1)}}; (q_1q_2,r)=1} \ \ \ \ \ (26)$

$\displaystyle 1_{b/n=b'/(n+kr)\ ((q_1,q_2))}$

$\displaystyle e_r( \frac{ah}{nq_1 q'_2} ) e_{q_1}( \frac{bh}{n r q'_2} ) e_{q'_2}( \frac{b' h}{(n+kr) r q_1} ),$

where ${q'_2 := q_2/(q_1,q_2)}$.

Let us first deal with the main term (23). The contribution of the coprime case ${(q_1,q_2)=1}$ does not depend on ${b,b'}$ and can thus be absorbed into the ${X}$ term. Now we consider the contribution of the non-coprime case when ${q_0 = (q_1,q_2) > 1}$. We may estimate the contribution of this case by

$\displaystyle O( \sum_r \sum_{k = O(N/R)} \sum_{q_0 \in {\mathcal S}_{I'}: 1 < q_0 \ll Q, (q_0,r)=1} \sum_{q'_1,q'_2 \sim Q/q_0} |\sum_{n: b/n = b'/(n+kr)\ (q_0)}$

$\displaystyle |\beta(n)| |\beta(n+kr)| M \frac{1}{rq_0 q'_1 q'_2} ).$

We may estimate ${|\beta(n)| |\beta(n+kr)|}$ by ${|\beta(n)|^2 + |\beta(n+kr)|^2}$. We just estimate the contribution of ${|\beta(n)|^2}$, as the other case is treated similarly (after shifting ${n}$ by ${kr}$). We rearrange this contribution as

$\displaystyle O( \sum_r \sum_{q_0 \in {\mathcal S}_{I'}: 1 < q_0 \ll Q, (q_0,r)=1} \sum_{q'_1,q'_2 \sim Q/q_0} |\sum_{n}$

$\displaystyle |\beta(n)|^2 M \frac{1}{Rq_0 q'_1 q'_2} \sum_{k = O(N/R)} 1_{b/n = b'/(n+kr)\ (q_0)} ).$

The ${k}$ summation is ${O( 1 + \frac{N}{Rq_0} )}$. Evaluating the ${n, r, q'_1,q'_2}$ summations, we obtain a bound of

$\displaystyle O( MN \log^{O(1)} x \sum_{q_0 \in {\mathcal S}_{I'}: 1 < q_0 \ll Q} \frac{1}{q_0} ( 1 + \frac{N}{Rq_0} ) ).$

Since ${q_0 > 1}$ and ${q_0 \in {\mathcal S}_{I'}}$, we have ${q_0 \geq D_0}$, and so we may evaluate the ${q_0}$ summation as

$\displaystyle O( MN \log^{O(1)} x (1 + \frac{N}{RD_0} ) ).$

By (16) and (15), this is ${O( N^2 M R^{-1} \log^{-A} x )}$ as required.

It remains to control (24). We may assume that ${H \geq 1}$, as the claim is trivial otherwise. It will suffice to obtain the bound

$\displaystyle \frac{1}{H} \sum_r \sum_{k=O(N/R)} \sum_{1 \leq h \leq H} \sum_{q_1,q_2 \sim Q} |\sum_{n} \beta(n) \overline{\beta(n+kr)} \Phi_{k,r}(h,q_1,q_2; n)|$

$\displaystyle \lessapprox x^{-\epsilon} N^2 M R^{-1}.$

Using (25), it will suffice to show that

$\displaystyle \sum_r \sum_{1 \leq h \leq H} \sum_{q_1,q_2 \sim Q} |\sum_{n} \beta(n) \overline{\beta(n+kr)} \Phi_{k,r}(h,q_1,q_2; n)|$

$\displaystyle \lessapprox Q^2 N R$

for each ${k = O(N/R)}$.

We now work with a single ${k}$. To proceed further, we write ${q_0 := (q_1,q_2)}$ and ${q_1 = q_0 q'_1}$, ${q_2 = q_0 q'_2}$; it then suffices to show that

$\displaystyle \sum_r \sum_{1 \leq h \leq H} \sum_{q'_1,q'_2 \sim Q/q_0: (q'_1,q'_2) = 1} \ \ \ \ \ (27)$

$\displaystyle |\sum_{n} \beta(n) \overline{\beta(n+kr)} \Phi_{k,r}(h,q_0 q'_1,q_0 q'_2; n)|$

$\displaystyle \lessapprox Q^2 N R / q_0$

for each ${q_0 \geq 1}$.

Henceforth we work with a single choice of ${q_0}$. We pause to verify the relationship

$\displaystyle H \lessapprox Q.$

From (25) and (17), this follows from the assertion that

$\displaystyle x^{1/2+2\varpi+\epsilon} \lessapprox M,$

but this follows from (4), (5) if ${\epsilon}$ is sufficiently small depending on ${c}$.

As ${q_1}$ is ${x^{\delta+o(1)}}$-densely divisible, we may now factor ${q_1 = s_1 t_1}$ where

$\displaystyle x^{-\delta} Q/H \lessapprox s_1 \lessapprox Q/H$

and thus

$\displaystyle H \lessapprox t_1 \lessapprox x^\delta H.$

Factoring out ${q_0}$, we may then write ${q'_1 = s'_1 t'_1}$ where

$\displaystyle q_0^{-1} x^{-\delta} Q/H \lessapprox s'_1 \lessapprox Q/H$

and

$\displaystyle q_0^{-1} H \lessapprox t'_1 \lessapprox x^\delta H.$

By dyadic decomposition, it thus suffices to show that

$\displaystyle \sum_r \sum_{1 \leq h \leq H} \sum_{s'_1 \sim S; t'_1 \sim T; q'_2 \sim Q/q_0: (s'_1 t'_1,q'_2) = 1}$

$\displaystyle |\sum_{n} \beta(n) \overline{\beta(n+kr)} \Phi_{k,r}(h,q_0 s'_1 t'_1,q_0 q'_2; n)|$

$\displaystyle \lessapprox Q^2 N R / q_0$

whenever ${S,T}$ are such that

$\displaystyle q_0^{-1} x^{-\delta} Q/H \lessapprox S \lessapprox Q/H$

and

$\displaystyle q_0^{-1} H \lessapprox T \lessapprox x^\delta H.$

and

$\displaystyle ST \sim Q/q_0.$

We rearrange this estimate as

$\displaystyle |\sum_r \sum_{n; s'_1 \sim S; q'_2 \sim Q/q_0} \beta(n) \overline{\beta(n+kr)} \sum_{1 \leq h \leq H; t'_1 \sim T}$

$\displaystyle c_{h,s'_1,t'_1,q'_2} \Phi_{k,r}(h,q_0 s'_1 t'_1,q_0 q'_2; n)|$

$\displaystyle \lessapprox QRSTN$

for some bounded sequence ${c_{h,s_1,t_1,q_2}}$ which is only non-zero when

$\displaystyle (s'_1 t'_1,q'_2) = (q_0,s'_1t'_1) = (q_0,q'_2) = 1.$

By Cauchy-Schwarz and crude estimates, it then suffices to show that

$\displaystyle \sum_r \sum_{n; s'_1 \sim S; q'_2 \sim Q/q_0} \psi_N(n) |\sum_{1 \leq h \leq H; t'_1 \sim T} c_{h,s'_1,t'_1,q'_2} \Phi_{k,r}(h,q_0 s'_1 t'_1,q_0 q_2; n)|^2$

$\displaystyle \lessapprox QRST^2 N q_0$

where ${\psi_N}$ is a coefficient sequence at scale ${N}$. The left-hand side may be bounded by

$\displaystyle \sum_{1 \leq h,\tilde h \leq H; t'_1,\tilde t'_1 \sim T; s'_1 \sim S; q'_2 \sim Q/q_0; (s'_1t'_1\tilde t'_1,q_0q'_2)=1} \ \ \ \ \ (28)$

$\displaystyle |\sum_r \sum_n \psi_N(n) \Phi_{k,r}(h, q_0 s'_1 t'_1,q_0 q'_2; n) \overline{ \Phi_{k,r}(\tilde h,q_0 s'_1 \tilde t'_1,q_0 q'_2; n) } |.$

The contribution of the diagonal case ${h \tilde t'_1 = \tilde h t'_1}$ is ${\lessapprox RHTSQ N/q_0}$ by the divisor bound, which is acceptable since ${q_0 T \gtrapprox H}$. Thus it suffices to control the off-diagonal case ${h\tilde t'_1 \neq \tilde ht'_1}$.

Note that ${t'_1, \tilde t'_1}$ need to lie in ${{\mathcal S}_I}$ for the summand to be non-vanishing. We use the following elementary lemma:

Lemma 14 We have

$\displaystyle \sum_{1 \leq h,\tilde h \leq H; t'_1,\tilde t'_1 \sim T; t'_1,\tilde t'_1 \in {\mathcal S}_I; s'_1 \sim S; q'_2 \sim Q/q_0: (s'_1t'_1\tilde t'_1,q_0q'_2)=1; h\tilde t'_1 \neq \tilde h t'_1}$

$\displaystyle (h\tilde t'_1-\tilde h t'_1, q_0 s'_1 [t'_1, \tilde t'_1] q'_2) \lessapprox H^2 S T^2 Q / q_0.$

Proof: Setting ${w := q_0 s'_1 q'_2}$, it suffices to show that

$\displaystyle \sum_{1 \leq h,\tilde h \leq H; t'_1,\tilde t'_1 \sim T: (t'_1\tilde t'_1,w)=1; h\tilde t'_1 \neq \tilde h t'_1} (h\tilde t'_1-\tilde h t'_1, [t'_1, \tilde t'_1] w) \lessapprox H^2 T^2$

for each fixed ${s'_1, q'_2}$. Since

$\displaystyle (h\tilde t'_1-\tilde h t'_1, [t'_1, \tilde t'_1] w) \leq \sum_{d|w} \sum_{e: (d,e)=1} de 1_{de| h\tilde t'_1-\tilde h t'_1} 1_{e|[t'_1,\tilde t'_1]}$

it suffices to show that

$\displaystyle \sum_{1 \leq h,\tilde h \leq H; t'_1,\tilde t'_1 \sim T: (t'_1\tilde t'_1,w)=1; h\tilde t'_1 \neq \tilde h t'_1} 1_{de| h\tilde t'_1-\tilde h t'_1} 1_{e|[t'_1,\tilde t'_1]} \lessapprox \frac{H^2 T^2}{de^2}$

for all coprime ${d,e}$ of polynomial size.

If ${e}$ divides both ${h\tilde t'_1-\tilde h t'_1}$ and ${[t'_1,\tilde t'_1]}$, then for each ${p}$ dividing ${e}$, ${p}$ must divide one of ${(h, t'_1)}$, ${(\tilde h, \tilde t'_1)}$, or ${(t'_1, \tilde t'_1)}$. Thus we can factor ${e = e_1 e_2 e_3}$ and ${h = e_1 h'}$, ${\tilde h = e_2 \tilde h'}$, ${t'_1 = e_1 e_3 t''_1}$, ${\tilde t'_1 = e_2 e_3 \tilde t''_1}$, which implies that ${d | h' \tilde t''_1 -\tilde h' t''_1}$. For fixed ${e}$, we see from the divisor bound that there are ${\lessapprox 1}$ choices for ${e_1,e_2,e_3}$. Fixing ${e_1,e_2,e_3}$, we see that ${h' \tilde t''_1, \tilde h' t''_1}$ have magnitude ${O(HT/e)}$, so there are ${O( (HT/e)^2 / d )}$ possible pairs of ${h' \tilde t''_1, \tilde h' t''_1}$ whose difference is non-zero and divisible by ${d}$. The claim then follows from the divisor bound. $\Box$

From this lemma, we see that for each fixed choice of ${h,\tilde h, t'_1, \tilde t'_1, s'_1, q'_2}$ in the above sum, it suffices to show that

$\displaystyle |\sum_r \sum_n \psi_N(n) \Phi_{k,r}(h, q_0 s'_1 t'_1,q_0 q'_2; n) \overline{ \Phi_{k,r}(\tilde h,q_0 s'_1 \tilde t'_1,q_0 q'_2; n) } |$

$\displaystyle \lessapprox H^{-2} q_0^2 RN (h\tilde t'_1-\tilde h t'_1, q_0 s'_1 [t'_1, \tilde t'_1] q'_2)$

Thus far the arguments have been essentially identical to that in the previous post, except that we have retained the ${r}$ averaging (and crucially, this averaging is inside the absolute values rather than outside). We now exploit the doubly dense divisibility of ${r}$ to factor ${r=dr'}$ where

$\displaystyle \max(1,x^{-\delta-\epsilon} H^{-4} N) \lessapprox d \lessapprox x^{-\epsilon} H^{-4} N$

and ${r'}$ is ${x^{\delta+o(1)}}$-densely divisible; this is admissible as long as

$\displaystyle 1 \lessapprox x^{-\epsilon} H^{-4} N \lessapprox R, \ \ \ \ \ (29)$

which are conditions which we will verify later. By dyadic decomposition, and the triangle inequality in ${r'}$, it thus suffices to show that

$\displaystyle |\sum_d \psi_D(d) \sum_n \psi_N(n) \Phi_{k,dr'}(h, q_0 s'_1 t'_1,q_0 q'_2; n) \overline{ \Phi_{k,dr'}(\tilde h,q_0 s'_1 \tilde t'_1,q_0 q'_2; n) } |$

$\displaystyle \lessapprox H^{-2} q_0^2 DN (h\tilde t'_1 - \tilde h t'_1,u)$

for all

$\displaystyle \max(1,x^{-\delta-\epsilon} H^{-4} N) \lessapprox D \lessapprox x^{-\epsilon} H^{-4} N \ \ \ \ \ (30)$

and all ${x^{\delta+o(1)}}$-densely divisible ${r' \sim R/D}$, where ${\psi_D}$ is a smooth non-negative coefficient sequence at scale ${D}$, where

$\displaystyle u:= r'q_0 s'_1 [t'_1, \tilde t'_1] q'_2. \ \ \ \ \ (31)$

Note that if the ${\Phi}$ factors are to be non-vanishing, ${q_0 s'_1 t'_1}$, ${q_0, s'_1 \tilde t'_1}$ are to be ${x^{\delta+o(1)}}$-densely divisible, and so ${u}$ is ${x^{\delta+o(1)}}$-densely divisible as well thanks to Lemma 7.

We write the above estimate as

$\displaystyle |\sum_d \psi_D(d) \sum_n \psi_N(n) \Psi(d,n)| \lessapprox H^{-2} q_0^2 DN (h\tilde t'_1 - \tilde h t'_1,u)$

where

$\displaystyle \Psi(d,n) :=\Phi_{k,dr'}(h, q_0 s'_1 t'_1,q_0 q'_2; n) \overline{ \Phi_{k,dr'}(\tilde h,q_0 s'_1 \tilde t'_1,q_0 q'_2; n) }.$

We now perform Weyl differencing. Set ${L := \lfloor x^{-\epsilon} N/D \rfloor}$, then ${L \geq 1}$ and we can rewrite

$\displaystyle \sum_d \psi_D(d) \sum_n \psi_N(n) \Psi(d,n) = \frac{1}{L} \sum_{d \sim D} \sum_n \sum_{l=1}^L \psi_N(n+dl) \Psi(d,n+dl)$

and so it suffices to show that

$\displaystyle |\sum_d \psi_D(d) \sum_n \sum_{l=1}^L \psi_N(n+dl) \Psi(d,n+dl)| \lessapprox H^{-2} q_0^2 DNL (h\tilde t'_1 - \tilde h t'_1,u).$

By Cauchy-Schwarz, it suffices to show that

$\displaystyle \sum_d \psi_D(d) \sum_n |\sum_{l=1}^L \psi_N(n+dl) \Psi(d,n+dl)|^2$

$\displaystyle \lessapprox H^{-4} q_0^4 DNL^2 (h\tilde t'_1 - \tilde h t'_1,u)^2.$

We restrict ${n}$ and ${d}$ to individual residue classes ${n=n_0\ (q_0)}$ and ${d = d_0\ (q_0)}$; it then suffices to show that

$\displaystyle \sum_{d=d_0\ (q_0)} \psi_D(d) \sum_{n=n_0\ (q_0)} |\sum_{l=1}^L \psi_N(n+dl) \Psi(d,n+dl)|^2$

$\displaystyle \lessapprox H^{-4} q_0^2 DNL^2 (h\tilde t'_1 - \tilde h t'_1,u)^2.$

From (26) we see that the quantity ${\Psi(d,n)}$ vanishes unless

$\displaystyle d r' q_0 s'_1 [t'_1,\tilde t'_1] q'_2$

is square-free, and in that case it takes the form

$\displaystyle \Psi(d,n) = \alpha_{n_0,d_0} e_d(\frac{c_0}{n}) e_{r's'_1[t'_1,\tilde t'_1]}(\frac{c_1}{dn} ) e_{q'_2}( \frac{c_2}{d(n+kdr')} )$

when restricted to ${n=n_0\ (q_0)}$, ${d = d_0\ (q_0)}$, where ${c_0,c_1,c_2}$ are quantities that may depend on ${q_0,r',s_1,t_1,\tilde t_1,q'_2}$ but are independent of ${n,d}$ with

$\displaystyle (c_1,r's'_1[t'_1,\tilde t'_1]) = (h\tilde t'_1 - \tilde h t'_1,r's'_1[t'_1,\tilde t'_1])$

and

$\displaystyle (c_2,q'_2) = (h\tilde t'_1 - \tilde h t'_1,q'_2).$

adopting the convention that ${e_q(\frac{a}{b})}$ vanishes when ${(b,q) \neq 1}$, and ${\alpha_{n_0,d_0}}$ is a bounded quantity depending on ${n_0,d_0,q_0,r',s_1,t_1,\tilde t_1,q'_2}$ but otherwise independent of ${n,d}$. If we let ${v \in {\bf Z}/u{\bf Z}}$ be such that ${v = 0\ (r's'_1[t'_1,\tilde t'_1])}$ and ${v = kr'\ (q'_2)}$, and let ${c_3:= c_1 q'_2 + c_2 r's'_1[t'_1,\tilde t'_1]}$, we can simplify the above as

$\displaystyle \Psi(d,n) = \alpha_{n_0,d_0} e_d(\frac{c_0}{n}) e_u(\frac{c_3}{d(n+vd)} )$

and note that

$\displaystyle (c_3,u) = (h\tilde t'_1 - \tilde ht'_1,u).$

We thus have

$\displaystyle |\sum_{l=1}^L \psi_N(n+dl) \Psi(d,n+dl)| \ll |\sum_{l=1}^L e_u(\frac{c_3}{d(n+vd)} )$

and therefore

$\displaystyle |\sum_{l=1}^L \psi_N(n+dl) \Psi(d,n+dl)|^2$

$\displaystyle \ll \sum_{1 \leq l,l' \leq L} \psi_N(n+dl) \psi_N(n+dl') e_u(\frac{c_3 l}{(n+vd+ld)(n+vd+l'd)} ).$

It thus suffices to show that

$\displaystyle |\sum_{d=d_0\ (q_0)} \psi_D(d) \sum_{n=n_0\ (q_0)} \sum_{1 \leq l,l' \leq L} \psi_N(n+dl) \psi_N(n+dl')$

$\displaystyle e_u(\frac{c_3 l}{(n+vd+ld)(n+vd+l'd)} )|$

$\displaystyle \lessapprox H^{-4} q_0^2 DNL^2 (h\tilde t'_1 - \tilde h t'_1,u)^2.$

Shifting ${n}$ by ${dl}$, then relabeling ${l'-l}$ as ${l}$, it suffices to show that

$\displaystyle \sum_{|l| \leq L} |\sum_{d=d_0\ (q_0)} \psi_D(d) \sum_{n=n_0\ (q_0)} \psi_N(n) \psi_N(n+dl) \ \ \ \ \ (32)$

$\displaystyle e_u(\frac{c_3 l}{(n+vd+ld)(n+vd+l'd)} ) |$

$\displaystyle \lessapprox H^{-4} q_0^2 DNL (h\tilde t'_1 - \tilde h t'_1,u)^2.$

The contribution of the diagonal case ${l=0}$ is ${O( D N )}$, which is acceptable thanks to (29) (which implies ${L \gtrapprox H^4}$; we have a factor of ${q_0^4}$ to spare which we will simply discard). It thus suffices to control the off-diagonal case ${l \neq 0}$. It then suffices to show that

$\displaystyle |\sum_{d=d_0\ (q_0)} \psi_D(d) \sum_{n=n_0\ (q_0)} \psi_N(n) \psi_N(n+dl)$

$\displaystyle e_u(\frac{c_3 l}{(n+vd+ld)(n+vd+l'd)} )|$

$\displaystyle \lessapprox H^{-4} q_0^2 DN (h\tilde t'_1 - \tilde h t'_1,u) (l,u)$

for each non-zero ${l}$.

Performing a Taylor expansion, we can write

$\displaystyle \psi_N(n+dl) = \sum_{j=0}^J (\frac{d}{D})^j \psi_{N,j}(n) + O( x^{-\epsilon J} )$

for any fixed ${J}$, where

$\displaystyle \psi_{N,j}(n) = \frac{1}{j!} (\frac{Dl}{N})^j \psi^{(j)}(\frac{n}{N}).$

Absorbing the ${(\frac{d}{D})^j}$ factor into ${\psi_D}$, and taking ${J}$ large enough, it suffices to show that

$\displaystyle |\sum_{d=d_0\ (q_0)} \tilde \psi_D(d) \sum_{n=n_0\ (q_0)} \tilde \psi_N(n) e_u(\frac{c_3 l}{(n+vd+ld)(n+vd+l'd)} )|$

$\displaystyle \lessapprox H^{-4} q_0^2 DN (h\tilde t'_1 - \tilde h t'_1,u) (l,u)$

for coefficient sequences ${\tilde \psi_D, \tilde \psi_N}$ which are smooth at scales ${D,N}$ respectively. But by applying Proposition 13, and making the substitutions ${d = q_0 d' + d_0}$, ${n = q_0 n' + n_0}$, we may bound the left-hand side by

$\displaystyle (c_3l,u) (u^{1/2} + \frac{N/q_0}{u^{1/2}}) ( 1 + (D/q_0)^{1/2} u^{1/6} x^{\delta/6} + \frac{D/q_0}{u^{1/2}})$

and

$\displaystyle (c_3l,u) (u^{1/2} + \frac{N/q_0}{u^{1/2}}) (u^{1/2} + \frac{D/q_0}{u^{1/2}}).$

Using the former bound when ${N/q_0 \leq u^{1/2}}$ and the latter bound when ${N/q_0 > u^{1/2}}$, we obtain the upper bound of

$\displaystyle (c_3l,u) [ u^{1/2} ( 1 + (D/q_0)^{1/2} u^{1/6} x^{\delta/6} + \frac{D/q_0}{u^{1/2}}) + \frac{N/q_0}{u^{1/2}} (u^{1/2} + \frac{D/q_0}{u^{1/2}})].$

Since

$\displaystyle (c_3l,u) \leq (c_3,u)(l,u) = (h\tilde t'_1 - \tilde h t'_1,u) (l,u)$

and ${q_0 \geq 1}$, it suffices to show that

$\displaystyle u^{1/2} ( 1 + D^{1/2} u^{1/6} x^{\delta/6} + \frac{D}{u^{1/2}}) + \frac{N}{u^{1/2}} (u^{1/2} + \frac{D}{u^{1/2}}) \lessapprox H^{-4} DN q_0^2.$

Since ${D,u \geq 1}$, we can replace ${1 + D^{1/2} u^{1/6} x^{\delta/6} }$ by ${D^{1/2} u^{1/6} x^{\delta/6}}$. The above bounds then simplify to

$\displaystyle D^{1/2} u^{2/3} x^{\delta/6} + D + N + DN u^{-1} \lessapprox H^{-4} D N q_0^2. \ \ \ \ \ (33)$

From (29) we already have ${D \lessapprox H^{-4} DN}$. Also, from (31) we have

$\displaystyle u \lessapprox \frac{R}{D} q_0 S T^2 (Q/q_0)$

$\displaystyle \lessapprox R D^{-1} Q^2 T$

$\displaystyle \lessapprox x^\delta R D^{-1} Q^2 H.$

and conversely

$\displaystyle u \gtrapprox \frac{R}{D} q_0 S T (Q/q_0)$

$\displaystyle \gtrapprox R D^{-1} Q^2 / q_0.$

Inserting these bounds and discarding the remaining powers of ${q_0}$, we reduce to

$\displaystyle D^{1/2} (x^\delta R D^{-1} Q^2 H)^{2/3} x^{\delta/6} \lessapprox H^{-4} DN$

and

$\displaystyle N \lessapprox H^{-4} DN$

and

$\displaystyle DN (R D^{-1} Q^2)^{-1} \lessapprox H^{-4} DN.$

We rearrange these as

$\displaystyle x^{5\delta/6} R^{2/3} Q^{4/3} H^{14/3} \lessapprox N D^{7/6}$

$\displaystyle H^4 \lessapprox D$

$\displaystyle H^4 D \lessapprox R Q^2.$

Applying the bounds on ${D}$ from (30), these reduce to

$\displaystyle x^{2\delta} x^{7\epsilon/6} R^{2/3} Q^{4/3} H^{28/3} \lessapprox N^{13/6}$

$\displaystyle x^{\delta+\epsilon} H^8 \lessapprox N \ \ \ \ \ (34)$

$\displaystyle x^{-\epsilon} N \lessapprox RQ^2.$

The third bound follows since ${N \lessapprox x^{1/2} \lessapprox QR}$, and so may be dropped. We also recall the two bounds assumed from (29):

$\displaystyle x^\epsilon H^4 \lessapprox N \ \ \ \ \ (35)$

$\displaystyle N \lessapprox x^\epsilon H^4 R.$

The bound (35) is implied by (34) and may thus be dropped. We have

$\displaystyle H = x^\epsilon Q^2 R/M \sim x^{-1+\epsilon} Q^2 R N,$

so the remaining three bounds may be rewritten as

$\displaystyle x^{2\delta} x^{21\epsilon/2} R^{10} Q^{20} N^{43/6} \lessapprox x^{28/3}$

$\displaystyle x^{\delta+9\epsilon} Q^{16} R^8 N^7 \lesssim x^8$

$\displaystyle x^4 \lessapprox x^{5\epsilon} Q^8 R^5 N^3.$

Since ${x^{1/2} \lessapprox QR \lessapprox x^{1/2+2\varpi}}$, these three bounds reduce to

$\displaystyle x^{2/3 + 40\varpi + 2\delta + 21\epsilon/2} N^{43/6} \lessapprox R^{10}$

$\displaystyle x^{32\varpi+\delta+9\epsilon} N^7 \lesssim R^8$

$\displaystyle R^3 \lessapprox x^{5\epsilon} N^3.$

From (16) we have ${x^{-\delta-\epsilon} N \lessapprox R \lessapprox x^{-\epsilon} N}$, so the third bound is automatic, and the other two bounds become

$\displaystyle x^{2/3 + 40\varpi + 12\delta + 41\epsilon/2} \lessapprox N^{17/6}$

$\displaystyle x^{32\varpi+9\delta+17\epsilon} \lessapprox N.$

Since ${N \gtrapprox 1/2-\sigma}$, these two bounds become

$\displaystyle \frac{2}{3} + 40\varpi + 12\delta < \frac{17}{6} (\frac{1}{2}-\sigma )$

$\displaystyle 32 \varpi + 9\delta < \frac{1}{2} - \sigma$

which we rearrange as

$\displaystyle \frac{160}{3} \varpi + 16 \delta + \frac{34}{9} \sigma < 1$

$\displaystyle 64\varpi + 18\delta + 2\sigma < 1$

and the claim follows.