2.1 Notation and basic facts

A useful reference for the circle method in function fields, of which the basics are sketched below, is [Reference Liu and Wooley14]. Let $\mathbb{F}_{q}(t)$ be the field of fractions of $\mathbb{F}_{q}[t]$ . On $\mathbb{F}_{q}(t)$ , we can define a norm by $|f/g|=q^{\deg f-\deg g}$ with the convention $\deg 0=-\infty .$ The completion of $\mathbb{F}_{q}(t)$ with respect to this norm is

$$\begin{eqnarray}\mathbb{F}_{q}\biggl(\biggl(\frac{1}{t}\biggr)\biggr)=\bigg\{\unicode[STIX]{x1D6FC}=\mathop{\sum }_{i=-\infty }^{n}a_{i}t^{i}:n\in \mathbb{Z},a_{i}\in \mathbb{F}_{q}\text{ for every }i\bigg\},\end{eqnarray}$$

the set of formal Laurent series in $1/t$ . It is easy to see that if $\unicode[STIX]{x1D6FC}$ is as above and $a_{n}\neq 0$ , then $|\unicode[STIX]{x1D6FC}|=q^{n}$ .

Then $\mathbb{F}_{q}[t]\subset \mathbb{F}_{q}(t)\subset \mathbb{F}_{q}((1/t))$ , and $\mathbb{F}_{q}[t],\mathbb{F}_{q}(t)$ and $\mathbb{F}_{q}((1/t))$ are the analogues of $\mathbb{Z},\mathbb{Q}$ and $\mathbb{R}$ , respectively.

Let us put $\mathbb{T}=\{\unicode[STIX]{x1D6FC}\in \mathbb{F}_{q}((1/t)):|\unicode[STIX]{x1D6FC}|<1\}$ . This is analogous to the usual torus $\mathbb{R}/\mathbb{Z}$ . Let $\text{Tr}:\mathbb{F}_{q}\rightarrow \mathbb{F}_{p}$ be the trace map. For $a\in \mathbb{F}_{q}$ , let us denote

$$\begin{eqnarray}e_{q}(a)=\exp \biggl(\frac{2\unicode[STIX]{x1D70B}i\,\text{Tr}(a)}{p}\biggr).\end{eqnarray}$$

This is an additive character on $\mathbb{F}_{q}$ . All additive characters on $\mathbb{F}_{q}$ are given by $a\mapsto e_{q}(ra)$ for some $r\in \mathbb{F}_{q}$ .

For $\unicode[STIX]{x1D6FC}\in \mathbb{F}_{q}((1/t))$ , we write $(\unicode[STIX]{x1D6FC})_{-1}$ to denote the coefficient of $t^{-1}$ in $\unicode[STIX]{x1D6FC}$ . We define $e(\unicode[STIX]{x1D6FC})=e_{q}((\unicode[STIX]{x1D6FC})_{-1})$ . This is an additive character on $\mathbb{F}_{q}((1/t))$ and allows us to do Fourier analysis on $\mathbb{F}_{q}[t]$ . It is analogous to the function $x\mapsto e^{2\unicode[STIX]{x1D70B}ix}$ with a few differences. For example, $e(\unicode[STIX]{x1D6FC})=1$ does not imply that $\unicode[STIX]{x1D6FC}\in \mathbb{F}_{q}[t]$ . All additive characters on $\mathbb{F}_{q}[t]$ are given by $f\mapsto e(f\unicode[STIX]{x1D6FC})$ for some $\unicode[STIX]{x1D6FC}\in \mathbb{T}$ .

We denote by $M$ the set of all monic polynomials in $\mathbb{F}_{q}[t]$ , $A_{n}$ the set of all polynomials of degree $n$ which are monic, $G_{n}$ the set of all polynomials (not necessarily monic) of degree less than $n$ and ${\mathcal{I}}$ the set of all monic, irreducible polynomials. We use the convention that $\sum _{\deg f=l}$ means $\sum _{f\in A_{l}}$ (that is, a sum over monic polynomials).

The von Mangoldt function on $\mathbb{F}_{q}[t]$ is defined by

$$\begin{eqnarray}\unicode[STIX]{x1D6EC}(f)=\left\{\begin{array}{@{}ll@{}}\deg P & \text{if }f=P^{k}\text{ for some monic irreducible }P\text{ and }k\geqslant 1,\\ 0 & \text{otherwise.}\end{array}\right.\end{eqnarray}$$

Recall that the “prime number theorem” on $\mathbb{F}_{q}[t]$ reads

$$\begin{eqnarray}\mathop{\sum }_{\deg f=l}\unicode[STIX]{x1D6EC}(f)=q^{l}.\end{eqnarray}$$

2.2 $L$ -functions of arithmetically distributed relations

To prove Theorem 1, we first observe that any linear form on $G_{n}$ can be represented as a map $f\mapsto (\unicode[STIX]{x1D6FC}f)_{-1}$ for some $\unicode[STIX]{x1D6FC}\in \mathbb{T}$ . Thus, Theorem 1 can be rephrased as a bound for sums of the form

$$\begin{eqnarray}\mathop{\sum }_{f\in G_{n}}\unicode[STIX]{x1D707}(f)e(\unicode[STIX]{x1D6FC}f)\end{eqnarray}$$

or, equivalently and more conveniently, of the form

$$\begin{eqnarray}\mathop{\sum }_{f\in A_{n}}\unicode[STIX]{x1D707}(f)e(\unicode[STIX]{x1D6FC}f).\end{eqnarray}$$

Now, if $\unicode[STIX]{x1D6FC}$ is approximated by a fraction $a/Q$ of polynomials up to a remainder $\unicode[STIX]{x1D6FD}=\sum _{i=-\infty }^{-l}\unicode[STIX]{x1D6FD}_{i}t^{i}$ for some $l\geqslant 2$ , that is, $\unicode[STIX]{x1D6FC}=a/Q+\unicode[STIX]{x1D6FD}$ , then $e(\unicode[STIX]{x1D6FC}f)=e(af/Q)e(\unicode[STIX]{x1D6FD}f)$ depends only on the residue class of $f$ modulo $Q$ and the coefficients of the terms of degrees at least $l-1$ of $f=\sum _{i=1}^{n}a_{i}t^{n-i}+t^{n}$ . We refer to $a_{1},\ldots ,a_{l}$ as the first $l$ coefficients of $f$ (if $i>n$ , then we define $a_{i}=0$ ). We thus need to understand functions on $A_{n}$ that only depend on the congruence class modulo a fixed modulus $Q$ and the first $l$ coefficients. Hence, for $l\geqslant 0$ , $Q\in \mathbb{F}_{q}[t]$ , we define an equivalence relation $R_{l,Q}$ on $M$ as follows:

$$\begin{eqnarray}\displaystyle f\equiv g~(\text{mod }R_{l,Q})\text{ if }f & \equiv & \displaystyle g~(\text{mod }Q)\text{ and the first }l\text{ coefficients of }\nonumber\\ \displaystyle & & \displaystyle \quad f\text{ and }g\text{ are the same.}\nonumber\end{eqnarray}$$

It is an example of an arithmetically distributed relation, of which Hayes [Reference Hayes9, §8] developed the theory, which we briefly review. The relevant facts can also be found in [Reference Hsu12] or [Reference Car4].

It is easy to check that $M/R_{l,Q}$ is a semigroup with respect to multiplication on $\mathbb{F}_{q}[t]$ . The equivalence class of a polynomial $f\in \mathbb{F}_{q}[t]$ is invertible in $M/R_{l,Q}$ if and only if $(f,Q)=1$ .

Put $G_{l,Q}:=(M/R_{l,Q})^{\times }$ , the set of invertible elements. This is a group of cardinality $q^{l}\unicode[STIX]{x1D719}(Q)$ , where $\unicode[STIX]{x1D719}(Q)=\#(\mathbb{F}_{q}[t]/(Q))^{\times }$ . Note that $G_{0,Q}$ is simply $(\mathbb{F}_{q}[t]/(Q))^{\times }$ .

For a character $\unicode[STIX]{x1D706}$ on $G_{l,Q}$ , we extend it to all of $M$ by setting $\unicode[STIX]{x1D706}(f)=0$ if $(f,Q)\neq 1$ . We define the $L$ -function associated with $\unicode[STIX]{x1D706}$ as

$$\begin{eqnarray}L(s,\unicode[STIX]{x1D706})=\mathop{\sum }_{f\in M}\unicode[STIX]{x1D706}(f)\frac{1}{|f|^{s}},\end{eqnarray}$$

which converges absolutely for $\Re (s)>1$ . It is convenient to put

(8) $$\begin{eqnarray}{\mathcal{L}}(z,\unicode[STIX]{x1D706})=\mathop{\sum }_{f\in M}\unicode[STIX]{x1D706}(f)z^{\deg (f)}=\mathop{\sum }_{n=1}^{\infty }z^{n}\mathop{\sum }_{f\in A_{n}}\unicode[STIX]{x1D706}(f).\end{eqnarray}$$

Then $L(s,\unicode[STIX]{x1D706})={\mathcal{L}}(q^{-s},\unicode[STIX]{x1D706})$ . We have the Euler product formula

(9) $$\begin{eqnarray}{\mathcal{L}}(z,\unicode[STIX]{x1D706})=\mathop{\prod }_{P\in {\mathcal{I}}}(1-\unicode[STIX]{x1D706}(P)z^{\deg P})^{-1}\end{eqnarray}$$

for $|z|<1/q$ .

In the same range of $z$ , we also have

(10) $$\begin{eqnarray}\frac{1}{{\mathcal{L}}(z,\unicode[STIX]{x1D706})}=\mathop{\prod }_{P}(1-\unicode[STIX]{x1D706}(P)z^{\deg P})=\mathop{\sum }_{f\in M}\unicode[STIX]{x1D707}(f)\unicode[STIX]{x1D706}(f)z^{\deg f}=\mathop{\sum }_{n=1}^{\infty }z^{n}\mathop{\sum }_{f\in A_{n}}\unicode[STIX]{x1D707}(f)\unicode[STIX]{x1D706}(f).\end{eqnarray}$$

The character constantly equal to 1 on $G_{l,Q}$ is called the principal character. When $\unicode[STIX]{x1D706}$ is not the principal character, ${\mathcal{L}}(z,\unicode[STIX]{x1D706})$ is a polynomial of degree $d(\unicode[STIX]{x1D706})<l+\deg Q$  [Reference Hayes9, Lemma 8.2]. The generalized Riemann hypothesis states that all roots of ${\mathcal{L}}(z,\unicode[STIX]{x1D706})$ have modulus $q^{-1/2}$ or 1 for any character $\unicode[STIX]{x1D706}$ modulo an arithmetically distributed congruence relation such as $R_{l,Q}$ . Weil’s proof (for Dirichlet characters) was extended to these generalized characters by Rhin [Reference Rhin16] (see, in particular, Ch. 2, §§4–6). In other words, we can write

(11) $$\begin{eqnarray}{\mathcal{L}}(z,\unicode[STIX]{x1D706})=\mathop{\prod }_{i=1}^{d(\unicode[STIX]{x1D706})}(1-\unicode[STIX]{x1D6FC}_{i}z),\end{eqnarray}$$

where $|\unicode[STIX]{x1D6FC}_{i}|=q^{1/2}$ or 1 for $i=1,\ldots ,d(\unicode[STIX]{x1D706})$ . In particular, ${\mathcal{L}}(z,\unicode[STIX]{x1D706})$ can be extended to an entire function and (10) remains valid when $|z|<q^{-1/2}$ .

When $\unicode[STIX]{x1D706}$ is the principal character of $G_{l,Q}$ , we have

$$\begin{eqnarray}\displaystyle {\mathcal{L}}(z,\unicode[STIX]{x1D706}) & = & \displaystyle \mathop{\prod }_{\substack{ P\in {\mathcal{I}}, \\ (P,Q)=1}}(1-z^{\deg P})^{-1}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\prod }_{\substack{ P\in {\mathcal{I}}, \\ P|Q}}(1-z^{\deg P})\mathop{\prod }_{P\in {\mathcal{I}}}(1-z^{\deg P})^{-1}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\prod }_{\substack{ P\in {\mathcal{I}}, \\ P|Q}}(1-z^{\deg P})\frac{1}{1-qz}.\nonumber\end{eqnarray}$$

Consequently, ${\mathcal{L}}(z,\unicode[STIX]{x1D706})$ can be extended to a meromorphic function and

(12) $$\begin{eqnarray}\frac{1}{{\mathcal{L}}(z,\unicode[STIX]{x1D706})}=\mathop{\sum }_{n=1}^{\infty }z^{n}\mathop{\sum }_{f\in A_{n},(f,Q)=1}\unicode[STIX]{x1D707}(f)=(1-qz)\mathop{\prod }_{\substack{ P\in {\mathcal{I}}, \\ P|Q}}(1-z^{\deg P})^{-1}\end{eqnarray}$$

for all $|z|\neq 1$ .

2.3 The bilinear Bogolyubov theorem

When proving Theorem 2, we will suppose for a contradiction that

$$\begin{eqnarray}\mathop{\sum }_{f\in G_{n}}\unicode[STIX]{x1D707}(f+t^{n})\unicode[STIX]{x1D712}(Q(f))\geqslant \unicode[STIX]{x1D716}q^{n}.\end{eqnarray}$$

Let $M$ be the $n\times n$ symmetric matrix corresponding to $Q$ and $k$ an integer. For any $a\in G_{k+1}$ , consider the map $L_{a}:G_{n-k}\rightarrow G_{n}$ that maps $f$ to $af$ . We also write $L_{a}$ to denote its $n\times (n-k)$ coordinate matrix in the canonical basis (i.e., the basis of monomials). For any $(a,b)\in G_{k+1}^{2}$ , let $M_{a,b}=L_{a}^{T}ML_{b}+L_{b}^{T}ML_{a}$ ; it is a symmetric $(n-k)\times (n-k)$ matrix.

After exploiting Vaughan’s identity in Section 5.2, we will find that for some $n\ll k\leqslant n$ , $M$ has the property that the set of pairs

$$\begin{eqnarray}P_{h}:=\{(a,b)\in G_{k+1}\times G_{k+1}|\text{rk }M_{a,b}\leqslant h\}\end{eqnarray}$$

is large; that is, it contains at least $\unicode[STIX]{x1D6FF}q^{2k+2}$ pairs for some parameters $\unicode[STIX]{x1D6FF}$ and $h$ (depending on $\unicode[STIX]{x1D716}$ and $n$ ). We will want to convert this information about the ranks of many $M_{a,b}$ into one on the rank of $M$ itself. However, we need these pairs to have some special structure in order to extract some information; in particular, it would be extremely convenient if the set

(13) $$\begin{eqnarray}\{(t^{i},t^{j})\mid (i,j)\in \{0,\ldots ,k\}^{2}\}\end{eqnarray}$$

could be in $P_{h}$ , because $M_{t^{i},t^{j}}$ is then simply a submatrix of $M$ . Unfortunately, its large size alone does not force $P_{h}$ to contain such a nice structure, but, to boost our chances, we are ready to do some additive smoothing, that is, adjoining to our set $P$ elements such as $(a_{1}-a_{2},b)$ whenever $(a_{1},b)$ and $(a_{2},b)$ are in $P$ ; and the same on the second coordinate. The rank remains controlled under this operation, because $\text{rk }M_{a_{1}-a_{2},b}=\text{rk }(M_{a_{1},b}-M_{a_{2},b})\leqslant 2h$ . Now our companion paper [Reference Bienvenu and Lê3] shows that additive smoothing does indeed produce useful structures. Here is the result we get [Reference Bienvenu and Lê3, Corollary 4].

Proposition 4. For any $\unicode[STIX]{x1D6FF}$ , there exists a constant $c(\unicode[STIX]{x1D6FF})$ such that the following holds. If $|P_{h}|\geqslant \unicode[STIX]{x1D6FF}q^{2k+2}$ , then there exist $\mathbb{F}_{p}$ -subspaces $W_{1},W_{2}$ of the $\mathbb{F}_{p}$ -vector space $G_{k+1}$ of codimensions $r_{1},r_{2}$ and $\mathbb{F}_{p}$ -bilinear forms $Q_{1},\ldots ,Q_{r}$ on $W_{1}\times W_{2}$ such that $P_{64h}=\{(a,b)\in G_{k+1}^{2}|\text{rk }M_{a,b}\leqslant 64h\}$ contains the set

$$\begin{eqnarray}\{(x,y)\in W_{1}\times W_{2}\mid Q_{1}(x,y)=\cdots =Q_{r}(x,y)=0\}\end{eqnarray}$$

and $\max (r,r_{1},r_{2})\leqslant c(\unicode[STIX]{x1D6FF})$ .

We call this statement a bilinear Bogolyubov theorem, by analogy with the original (linear) Bogolyubov theorem. We found that we can take $c(\unicode[STIX]{x1D6FF})$ to be $O(\exp (\exp (\exp (\log ^{O(1)}1/\unicode[STIX]{x1D6FF}))))$ , where the implied constants may depend on $q$ , but, unfortunately, because $\unicode[STIX]{x1D6FF}$ will be as small as, say, $n^{-5}$ , this bound for $c(\unicode[STIX]{x1D6FF})$ is too large. By analogy with Sanders’ bound for the linear Bogolyubov theorem [Reference Sanders18], it is reasonable to imagine [Reference Bienvenu and Lê3, Conjecture 3] that the linear and bilinear codimensions $r,r_{1},r_{2}$ could be taken as small as polylogarithmic in $\unicode[STIX]{x1D6FF}^{-1}$ . In [Reference Bienvenu and Lê3], we show that indeed we can take $r$ and one of $r_{1}$ and $r_{2}$ to be polylogarithmic in $\unicode[STIX]{x1D6FF}^{-1}$ . Recently, Hosseini and Lovett [Reference Hosseini and Lovett11, Theorem 1.3] lowered $c(\unicode[STIX]{x1D6FF})$ to $\log ^{O(1)}\unicode[STIX]{x1D6FF}^{-1}$ , at the cost of replacing 64 in Proposition 4 by a larger constant.

Theorem 5 (Polylogarithmic bilinear Bogolyubov).

For any $\unicode[STIX]{x1D6FF}$ , if $|P_{h}|\geqslant \unicode[STIX]{x1D6FF}q^{2k+2}$ , then there exist $\mathbb{F}_{p}$ -subspaces $W_{1},W_{2}$ of the $\mathbb{F}_{p}$ -vector space $G_{k+1}$ of codimensions $r_{1},r_{2}$ and $\mathbb{F}_{p}$ -bilinear forms $Q_{1},\ldots ,Q_{r}$ on $W_{1}\times W_{2}$ such that $P_{2^{9}h}=\{(a,b)\in G_{k+1}^{2}|\text{rk }M_{a,b}\leqslant 2^{9}h\}$ contains the set

(14) $$\begin{eqnarray}\{(x,y)\in W_{1}\times W_{2}\mid Q_{1}(x,y)=\cdots =Q_{r}(x,y)=0\}\end{eqnarray}$$

and $\max (r,r_{1},r_{2})\leqslant O(\log ^{80}\unicode[STIX]{x1D6FF}^{-1})$ .

Applied with $\unicode[STIX]{x1D6FF}=q^{-n^{c}}$ , this means that the codimensions should be $O(n^{O(c)})$ .

The reason why sets of the form (14) are so desirable for us is the following lemma.

Lemma 6. Let $W$ be an $\mathbb{F}_{p}$ -vector space of dimension $n$ and $Q_{1},\ldots ,Q_{r}$ be quadratic forms on $W$ . If $n\geqslant 2r(r+1)$ , then the set of isotropic vectors

(15) $$\begin{eqnarray}X=\{x\in W\mid Q_{1}(x)=\cdots =Q_{r}(x)=0\}\end{eqnarray}$$

contains at least $(1-p^{-1/2})p^{n-2r(r+1)}$ elements.

More compactly, we can write $|X|\gg p^{n-O(r^{2})}$ . We now prove Lemma 6. We introduce the averaging notation $\mathbb{E}_{x\in W}=(1/|W|)\sum _{x\in W}$ .

Proof. The density $|X|/|W|$ of isotropic vectors is given by

(16) $$\begin{eqnarray}\mathbb{E}_{x\in W}\mathbb{E}_{t_{1},\ldots ,t_{r}\in \mathbb{F}_{p}}\unicode[STIX]{x1D714}^{\mathop{\sum }_{i}t_{i}Q_{i}(x)}=\mathbb{E}_{t_{1},\ldots ,t_{r}}\mathbb{E}_{x\in W}\unicode[STIX]{x1D714}^{\mathop{\sum }_{i}t_{i}Q_{i}(x)},\end{eqnarray}$$

where $\unicode[STIX]{x1D714}=e^{2\unicode[STIX]{x1D70B}i/p}$ . Let $m\leqslant n$ be a parameter to be determined later (in terms of  $r$ ). Now, if a quadratic form $Q$ on $W\times W$ has rank at least $m$ , we can see that

$$\begin{eqnarray}|\mathbb{E}_{x\in W}\unicode[STIX]{x1D714}^{Q(x)}|\leqslant p^{-m/2}\end{eqnarray}$$

by squaring this expectation (see Lemma 13). Thus, if, for any nonzero $(t_{1},\ldots ,t_{r})$ , the rank of $\sum _{i}t_{i}Q_{i}$ is at least $m$ , we see from equation (16) that the density of isotropic vectors is at least $p^{-r}-p^{-m/2}$ . Otherwise, there exists a form $Q_{i}$ such that $Q_{i}=\sum _{j\neq i}t_{j}Q_{j}+R$ with $\text{rk }R<m$ ; without loss of generality, suppose that $i=r$ . Let $W^{\prime }$ be the kernel of $R$ , a subspace of codimension less than $m$ . Then the set

(17) $$\begin{eqnarray}X^{\prime }=\{x\in W^{\prime }|Q_{1}(x)=\cdots =Q_{r-1}(x)=0\}\end{eqnarray}$$

is a subset $X$ and we will now count isotropic vectors in $X^{\prime }$ . Thus, incurring a dimension loss of at most $m$ , we reduce the number of quadratic forms by 1. We iterate this process until we get a family of quadratic forms for which any nontrivial linear combination has rank at least $m$ (or an empty family). At that point, this is a family of at most $r$ forms on a space of dimension at least $n-rm$ . Thus, it must have at least

$$\begin{eqnarray}p^{n-r(m+1)}-p^{n-rm-m/2}\end{eqnarray}$$

isotropic vectors. Taking $m=2r+1$ , we obtain the result.◻

We will use this lemma in §6 to obtain sets of the form (13) inside $P_{2^{9}h}$ .

2.4 Divisor bounds

We list some facts regarding the divisor function in $\mathbb{F}_{q}[t]$ which we will need in the sequel. Let $\unicode[STIX]{x1D70F}(f)$ denote the number of monic divisors of $f\in \mathbb{F}_{q}[t]$ . We first have the following result.

Lemma 7 [Reference Lê13, Lemma 8].

If $\deg f=n>1$ , then

$$\begin{eqnarray}\unicode[STIX]{x1D70F}(f)\leqslant \exp \biggl(O_{q}\biggl(\frac{n}{\log n}\biggr)\biggr).\end{eqnarray}$$

Consequently, the number of monic irreducible factors of $f$ is $O_{q}(n/\text{log}\,n)$ .

The next result is a bound for the second moment of $\unicode[STIX]{x1D70F}$ .

Lemma 8. We have

$$\begin{eqnarray}\mathbb{E}_{\deg d=n}\unicode[STIX]{x1D70F}(d)^{2}\leqslant 4n^{3}.\end{eqnarray}$$

Proof. We observe that for any irreducible $P$ and any integer $k$ , we have $\unicode[STIX]{x1D70F}(P^{k})^{2}=(k+1)^{2}$ .

Thus, the Dirichlet series $D=\sum _{n=0}^{+\infty }\sum _{f\in A_{n}}(\unicode[STIX]{x1D70F}(f)^{2}/|f|^{s})$ of the function $\unicode[STIX]{x1D70F}^{2}$ can be written as an Euler product as

(18) $$\begin{eqnarray}D=\mathop{\prod }_{P}\mathop{\sum }_{k=0}^{+\infty }(k+1)^{2}|P|^{-ks}.\end{eqnarray}$$

Next we note the following relations between formal power series:

$$\begin{eqnarray}\displaystyle \mathop{\sum }_{k=0}^{+\infty }(k+1)^{2}x^{k} & = & \displaystyle \mathop{\sum }_{k=0}^{+\infty }(k+2)(k+1)x^{k}-\mathop{\sum }_{k=0}^{+\infty }(k+1)x^{k}\nonumber\\ \displaystyle & = & \displaystyle 2(1-x)^{-3}-(1-x)^{-2}=\frac{1+x}{(1-x)^{3}},\nonumber\end{eqnarray}$$

so finally

(19) $$\begin{eqnarray}\mathop{\sum }_{k=0}^{+\infty }(k+1)^{2}x^{k}=\frac{1-x^{2}}{(1-x)^{4}}.\end{eqnarray}$$

Combining equations (18) and (19) yields

$$\begin{eqnarray}D=\mathop{\prod }_{P}\frac{1-|P|^{-2s}}{(1-|P|^{-s})^{4}}.\end{eqnarray}$$

We can then express this Euler product in terms of the zeta function of $\mathbb{F}_{q}[t]$ . Letting $u=q^{-s}$ , we obtain

$$\begin{eqnarray}D=\unicode[STIX]{x1D701}(s)^{4}/\unicode[STIX]{x1D701}(2s)=(1-q^{1-2s})(1-q^{1-s})^{-4}=(1-qu^{2})(1-qu)^{-4}.\end{eqnarray}$$

This is a power series $S(u)$ in $u$ and $S(u)=\sum _{n}a_{n}u^{n}=\sum _{n}(S^{(n)}(0)/n!)u^{n}$ , where $a_{n}=\sum _{\deg d=n}\unicode[STIX]{x1D70F}(d)^{2}$ . Now, for $n\geqslant 3$ , deriving $n$ times using Leibniz’ formula, we find that

$$\begin{eqnarray}\displaystyle S^{(n)}(u) & = & \displaystyle (1-qu^{2})q^{n}(4\times \cdots \times (n+3))(1-qu)^{-4-n}\nonumber\\ \displaystyle & & \displaystyle -\,2qunq^{n-1}(4\times \cdots \times (n+2))(1-qu)^{-3-n}\nonumber\\ \displaystyle & & \displaystyle -\,2q\binom{n}{2}q^{n-2}(4\times \cdots \times (n+1))(1-qu)^{-2-n}.\nonumber\end{eqnarray}$$

Evaluating in $u=0$ gives

$$\begin{eqnarray}\frac{S^{(n)}(0)}{q^{n}n!}=(n+3)(n+2)(n+1)/6-q^{-1}n(n+1)^{2}/6\leqslant 4n^{3},\end{eqnarray}$$

where the left-hand side is exactly $\mathbb{E}_{\deg d=n}\unicode[STIX]{x1D70F}(d)^{2}$ .◻

5.1 Quadratic phases

We call a quadratic form on $\mathbb{F}_{q}^{n}$ a homogenous polynomial of degree 2, that is, a map of the form $F(x)=x^{T}Mx$ , where $M$ is a symmetric matrix. The corresponding (symmetric) bilinear form is the map

$$\begin{eqnarray}B(x,y)=x^{T}My.\end{eqnarray}$$

The rank of $F$ is the rank of the matrix $M$ . It equals the codimension of the space $K$ of vectors $x$ such that the linear form $B_{x}$ defined by $B_{x}(y)=B(x,y)$ satisfies $B_{x}=0$ . A quadratic polynomial is a polynomial of degree 2, that is, a quadratic form plus a linear form. A quadratic phase is a map of the form $\unicode[STIX]{x1D6F7}(x)=\unicode[STIX]{x1D712}(P(x))$ for a quadratic polynomial $P$ and an additive character $\unicode[STIX]{x1D712}$ . Its rank is the rank of the corresponding quadratic form. Thanks to the following standard lemma, quadratic phases can be classified, depending on their rank, into major arcs and minor arcs, by analogy with the circle method.

Lemma 13 (Gauss sums).

Let $\unicode[STIX]{x1D6F7}(x)=\unicode[STIX]{x1D712}(P(x))$ be a quadratic phase of rank at least $r$ . Then

$$\begin{eqnarray}|\mathbb{E}_{x\in \mathbb{F}_{q}^{n}}\unicode[STIX]{x1D6F7}(x)|\leqslant q^{-r/2}.\end{eqnarray}$$

Thus, quadratic phases of low rank correspond to major arcs, while the ones of high rank correspond to minor arcs.

Proof. We use the standard technique called Weyl differencing, consisting of squaring the expectation to duplicate the variable. We have

$$\begin{eqnarray}\displaystyle |\mathbb{E}_{x\in \mathbb{F}_{q}^{n}}\unicode[STIX]{x1D6F7}(x)|^{2} & = & \displaystyle \mathbb{E}_{x,h}\unicode[STIX]{x1D6F7}(x+h)\overline{\unicode[STIX]{x1D6F7}(x)}\nonumber\\ \displaystyle & = & \displaystyle \mathbb{E}_{x,h}\unicode[STIX]{x1D712}(P(x+h)-P(x))\nonumber\\ \displaystyle & = & \displaystyle \mathbb{E}_{h}\unicode[STIX]{x1D712}(P(h))\mathbb{E}_{x}\unicode[STIX]{x1D712}(2B_{h}(x)),\nonumber\end{eqnarray}$$

where all variables range over $\mathbb{F}_{q}^{n}$ . Now, if $h\notin K$ , the form $2B_{h}$ is a nonzero linear form (remember that the characteristic $p$ is not 2), whence $\mathbb{E}_{x\in \mathbb{F}_{q}^{n}}\unicode[STIX]{x1D712}(2B_{h}(x))=\mathbb{E}_{x\in \mathbb{F}_{q}}\unicode[STIX]{x1D712}(x)=0$ . This implies that

$$\begin{eqnarray}|\mathbb{E}_{x\in \mathbb{F}_{q}^{n}}\unicode[STIX]{x1D6F7}(x)|^{2}\leqslant \mathbb{E}_{h\in \mathbb{F}_{q}^{n}}1_{h\in K}=q^{-r}\end{eqnarray}$$

and the claim follows. ◻

We now start the proof of Theorem 2. Let $P$ be a quadratic polynomial on $\mathbb{F}_{q}^{n}$ and $\unicode[STIX]{x1D6F7}=\unicode[STIX]{x1D712}\circ P$ be a quadratic phase. We want to bound the sum

$$\begin{eqnarray}\mathop{\sum }_{f\in G_{n}}\unicode[STIX]{x1D707}(f+t^{n})\unicode[STIX]{x1D6F7}(f)=\mathop{\sum }_{f\in A_{n}}\unicode[STIX]{x1D707}(f)\unicode[STIX]{x1D6F7}(f),\end{eqnarray}$$

where, by abuse of notation, if $f\in A_{n}$ , we write $\unicode[STIX]{x1D6F7}(f)$ for $\unicode[STIX]{x1D6F7}(f-t^{n})$ . The general strategy is the following. We first observe that when $\unicode[STIX]{x1D6F7}$ is a quadratic phase of rank at most $cn$ with $c<1/4$ , then Corollary 12 concludes: indeed, a quadratic form of rank $r$ depends on $r$ linear forms only, so a quadratic polynomial of rank $r$ depends on $r+1$ linear forms at most. So, we will show that in order for $\unicode[STIX]{x1D707}$ to correlate with a quadratic phase $\unicode[STIX]{x1D6F7}$ , the corresponding quadratic form needs to be of small rank (major arcs). This would imply that $\unicode[STIX]{x1D707}$ cannot correlate with a quadratic phase at all.

5.2 Exploitation of Vaughan’s identity

We will show the following result.

Before proving this proposition, we underline that for any $d\in G_{k+1}$ , we see the map $w\mapsto dw$ as a linear map from $G_{n-k}$ to $G_{n}$ , which allows one to see $w\mapsto P(dw)$ as a quadratic polynomial.

We now start proving the proposition. The first tool we need is Vaughan’s identity, which reads

$$\begin{eqnarray}\unicode[STIX]{x1D707}(f)=-\mathop{\sum }_{\substack{ ab\mid f \\ \deg a\leqslant u,\deg b\leqslant v}}\unicode[STIX]{x1D707}(a)\unicode[STIX]{x1D707}(b)+\mathop{\sum }_{\substack{ ab\mid f \\ \deg a>u,\deg b>v}}\unicode[STIX]{x1D707}(a)\unicode[STIX]{x1D707}(b),\end{eqnarray}$$

where the sum is over monic polynomials $a$ and $b$ , and $u=v=n/18$ (though in general they can be chosen arbitrarily). We shall adopt the notational convention that $N=q^{n},U=q^{u}$ and so on. Moreover, for $f\in \mathbb{F}_{q}[t]$ , recall the notation $|f|=q^{\deg f}$ . Vaughan’s identity implies that

(42) $$\begin{eqnarray}\mathop{\sum }_{f\in A_{n}}\unicode[STIX]{x1D707}(f)\unicode[STIX]{x1D6F7}(f)=-T_{1}+T_{2},\end{eqnarray}$$

where

(43) $$\begin{eqnarray}T_{1}=\mathop{\sum }_{|d|\leqslant UV}a_{d}\mathop{\sum }_{w\in A_{n-\deg d}}\unicode[STIX]{x1D6F7}(dw)\end{eqnarray}$$

and

(44) $$\begin{eqnarray}T_{2}=\mathop{\sum }_{V\leqslant |d|\leqslant N/U}b_{d}\mathop{\sum }_{w\in A_{n-\deg d}}\unicode[STIX]{x1D707}(w)\unicode[STIX]{x1D6F7}(dw)\end{eqnarray}$$

are called type I and type II sums, respectively. The sums over $d$ are over monic polynomials. The coefficients $a_{d}$ are unimportant and all we need to know is that $\max (|a_{d}|,|b_{d}|)\leqslant \unicode[STIX]{x1D70F}(d)$ . In the type I sum, we have made the change of variables $d=ab,w=f/d$ , while in the other one we wrote $w=fb,d=f/w$ . The splitting into two sums yields the following dichotomy, which we will use to prove Proposition 14.

Proposition 15. Make the same hypothesis as in Proposition 14. Then either there exists $k\leqslant n/9$ so that

(45) $$\begin{eqnarray}\mathbb{E}_{d\in A_{k}}|\mathbb{E}_{w\in A_{n-k}}\unicode[STIX]{x1D6F7}(dw)|^{2}\geqslant \unicode[STIX]{x1D6FF}^{2}/(16n^{5})\end{eqnarray}$$

or there is a $k\in [n/18,17n/18]$ such that

(46) $$\begin{eqnarray}\mathbb{E}_{w,w^{\prime }\in A_{n-k}}\mathbb{E}_{d,d^{\prime }\in A_{k}}\unicode[STIX]{x1D6F7}(dw)\overline{\unicode[STIX]{x1D6F7}(dw^{\prime })\unicode[STIX]{x1D6F7}(d^{\prime }w)}\unicode[STIX]{x1D6F7}(d^{\prime }w^{\prime })\geqslant \unicode[STIX]{x1D6FF}^{4}/(256n^{10}).\end{eqnarray}$$

Proof. If $|\!\sum _{f\in A_{n}}\unicode[STIX]{x1D707}(f)\unicode[STIX]{x1D6F7}(f)|\geqslant \unicode[STIX]{x1D6FF}N$ , the decomposition (42) implies that either $|T_{1}|\geqslant \unicode[STIX]{x1D6FF}N/2$ or $|T_{2}|\geqslant \unicode[STIX]{x1D6FF}N/2$ . Suppose first that $|T_{1}|\geqslant \unicode[STIX]{x1D6FF}N/2$ . On the other hand, using the triangle inequality and equation (43), we bound $T_{1}$ by

$$\begin{eqnarray}\displaystyle |T_{1}| & {\leqslant} & \displaystyle \mathop{\sum }_{k\leqslant u+v}\mathop{\sum }_{d\in A_{k}}\unicode[STIX]{x1D70F}(d)\frac{N}{|d|}|\mathbb{E}_{w\in A_{n-k}}\unicode[STIX]{x1D6F7}(dw)|\nonumber\\ \displaystyle & {\leqslant} & \displaystyle n\max _{k\leqslant u+v}\frac{N}{K}\mathop{\sum }_{d\in A_{k}}\unicode[STIX]{x1D70F}(d)|\mathbb{E}_{w\in A_{n-k}}\unicode[STIX]{x1D6F7}(dw)|.\nonumber\end{eqnarray}$$

Fix a $k\leqslant u+v=n/9$ that realizes the maximum in the line above. The Cauchy–Schwarz inequality then yields

$$\begin{eqnarray}|T_{1}|^{2}/N^{2}\leqslant n^{2}\,(\mathbb{E}_{d\in A_{k}}\,\unicode[STIX]{x1D70F}^{2}(d))(\mathbb{E}_{d\in A_{k}}|\mathbb{E}_{w\in A_{n-k}}\unicode[STIX]{x1D6F7}(dw)|^{2}).\end{eqnarray}$$

Now Lemma 8 ensures that

$$\begin{eqnarray}\mathbb{E}_{d\in A_{k}}\,\unicode[STIX]{x1D70F}^{2}(d)\leqslant 4k^{3}\leqslant 4n^{3},\end{eqnarray}$$

so we can affirm that

$$\begin{eqnarray}\unicode[STIX]{x1D6FF}^{2}N^{2}/4\leqslant |T_{1}|^{2}\leqslant 4n^{5}N^{2}\mathbb{E}_{d\in A_{k}}|\mathbb{E}_{w\in A_{n-k}}\unicode[STIX]{x1D6F7}(dw)|^{2}.\end{eqnarray}$$

This means that

$$\begin{eqnarray}\mathbb{E}_{d\in A_{k}}|\mathbb{E}_{w\in A_{n-k}}\unicode[STIX]{x1D6F7}(dw)|^{2}\geqslant \unicode[STIX]{x1D6FF}^{2}/(16n^{5}),\end{eqnarray}$$

which proves equation (45).

Let us now suppose that $|T_{2}|\geqslant \unicode[STIX]{x1D6FF}N/2$ . Using the triangle inequality and equation (44), we have

$$\begin{eqnarray}\displaystyle |T_{2}| & {\leqslant} & \displaystyle \mathop{\sum }_{V\leqslant |d|\leqslant N/U}\unicode[STIX]{x1D70F}(d)\biggl|\mathop{\sum }_{w\in A_{n-k}}\unicode[STIX]{x1D707}(w)\unicode[STIX]{x1D6F7}(dw)\biggr|\nonumber\\ \displaystyle & {\leqslant} & \displaystyle nN\max _{v\leqslant k\leqslant n-u}\mathbb{E}_{d\in A_{k}}\unicode[STIX]{x1D70F}(d)|\mathbb{E}_{w\in A_{n-k}}\,\unicode[STIX]{x1D707}(w)\unicode[STIX]{x1D6F7}(dw)|.\nonumber\end{eqnarray}$$

We again fix a $k$ (this time $k\in [n/18,17n/18]$ ) that realizes the maximum and apply the Cauchy–Schwarz inequality together with Lemma 8, obtaining

$$\begin{eqnarray}|T_{2}|^{2}/N^{2}\leqslant 4n^{5}\,\mathbb{E}_{d\in A_{k}}\mathbb{E}_{w,w^{\prime }\in A_{n-k}}\unicode[STIX]{x1D707}(w)\unicode[STIX]{x1D707}(w^{\prime })\unicode[STIX]{x1D6F7}(dw)\overline{\unicode[STIX]{x1D6F7}(dw^{\prime })}.\end{eqnarray}$$

This implies that

$$\begin{eqnarray}\mathbb{E}_{w,w^{\prime }\in A_{n-k}}\,\unicode[STIX]{x1D707}(w)\unicode[STIX]{x1D707}(w^{\prime })\mathbb{E}_{d\in A_{k}}\unicode[STIX]{x1D6F7}(dw)\overline{\unicode[STIX]{x1D6F7}(dw^{\prime })}\geqslant \unicode[STIX]{x1D6FF}^{2}/(16n^{5})\end{eqnarray}$$

and again we apply Cauchy–Schwarz to eliminate $\unicode[STIX]{x1D707}$ , which yields

$$\begin{eqnarray}\mathbb{E}_{w,w^{\prime }\in A_{n-k}}\mathbb{E}_{d,d^{\prime }\in A_{k}}\unicode[STIX]{x1D6F7}(dw)\overline{\unicode[STIX]{x1D6F7}(dw^{\prime })\unicode[STIX]{x1D6F7}(d^{\prime }w)}\unicode[STIX]{x1D6F7}(d^{\prime }w^{\prime })\geqslant \unicode[STIX]{x1D6FF}^{4}/(256n^{10}).\end{eqnarray}$$

This is the content of clause (46), so the proof of Proposition 15 is complete. ◻

We now derive Proposition 14 using Proposition 15. Suppose first that equation (45) holds, so there is $k\leqslant n/9$ such that

(47) $$\begin{eqnarray}\mathbb{E}_{d\in A_{k}}|\mathbb{E}_{w\in A_{n-k}}\unicode[STIX]{x1D6F7}(dw)|^{2}\geqslant \unicode[STIX]{x1D6FF}^{\prime },\end{eqnarray}$$

where $\unicode[STIX]{x1D6FF}^{\prime }=\unicode[STIX]{x1D6FF}^{2}/(16n^{5})$ . Equation (47) implies that there exists $d\in A_{k}$ such that

$$\begin{eqnarray}|\mathbb{E}_{w\in A_{n-k}}\unicode[STIX]{x1D6F7}(dw)|^{2}\geqslant \unicode[STIX]{x1D6FF}^{\prime }.\end{eqnarray}$$

Fix such a $d\in A_{k}$ . Lemma 13 then implies that the quadratic polynomial $w\mapsto P(dw)$ has rank at most $\log _{q}({\unicode[STIX]{x1D6FF}^{\prime }}^{-1})=O(\log (n/\unicode[STIX]{x1D6FF}))$ . This corresponds exactly to the first statement of Proposition 14.

Suppose instead that equation (46) holds. Then we have $k\in [n/18,17n/18]$ such that

$$\begin{eqnarray}\mathbb{E}_{w,w^{\prime }\in A_{n-k}}\mathbb{E}_{d,d^{\prime }\in A_{k}}\unicode[STIX]{x1D6F7}(dw)\overline{\unicode[STIX]{x1D6F7}(dw^{\prime })\unicode[STIX]{x1D6F7}(d^{\prime }w)}\unicode[STIX]{x1D6F7}(d^{\prime }w^{\prime })\geqslant \unicode[STIX]{x1D6FF}^{\prime },\end{eqnarray}$$

where $\unicode[STIX]{x1D6FF}^{\prime }=\unicode[STIX]{x1D6FF}^{4}/(256n^{10})$ . The triangle inequality ensures that

$$\begin{eqnarray}\mathbb{E}_{d,d^{\prime }\in A_{k}}|\mathbb{E}_{w\in A_{n-k}}\unicode[STIX]{x1D712}(P(dw)-P(d^{\prime }w))|\geqslant \unicode[STIX]{x1D6FF}^{\prime }.\end{eqnarray}$$

In particular, for a proportion of at least $\unicode[STIX]{x1D6FF}^{\prime }/2$ pairs of monic polynomials $d,d^{\prime }$ of degree $k$ , we have

$$\begin{eqnarray}\displaystyle & & \displaystyle |\mathbb{E}_{w\in G_{n-k}}\unicode[STIX]{x1D712}(P(d(w+t^{n-k}))-P(d^{\prime }(w+t^{n-k})))|\nonumber\\ \displaystyle & & \displaystyle \qquad =|\mathbb{E}_{w\in A_{n-k}}\unicode[STIX]{x1D712}(P(dw)-P(d^{\prime }w))|\geqslant \unicode[STIX]{x1D6FF}^{\prime }/2.\nonumber\end{eqnarray}$$

Observe that for $w\in G_{n-k}$ , the rank of $w\mapsto P(d(w+t^{n-k}))-P(d^{\prime }(w+t^{n-k}))$ is the same as that of $w\mapsto P(dw)-P(d^{\prime }w)$ . Lemma 13 implies that the rank of $w\mapsto P(dw)-P(d^{\prime }w)$ is at most $-2\log _{q}(\unicode[STIX]{x1D6FF}^{\prime }/2)=O(\log (n/\unicode[STIX]{x1D6FF}))$ . This is precisely the second part of Proposition 14. So, in every case, Proposition 14 holds.