1. Introduction
1·1. Set-up and motivation
Let p be a prime. Given a subset ${\mathcal X}$ of a finite field ${\mathbb F}_p$ of p elements and a polynomial $f \in {\mathbb F}_p[X]$ , we define the Weil sum over ${\mathcal X}$ as
where
and we always assume that the elements of ${\mathbb F}_p$ are represented by the set $ \{0, \ldots, p-1\}$ .
The celebrated result of Weil [ Reference Weil28 ] asserts that for any nontrivial polynomial $f \in {\mathbb F}_p[X]$ , when ${\mathcal X} = {\mathbb F}_p$ , we have
where $n = \deg f$ , see also, for example, [ Reference Iwaniec and Kowalski8 , chapter 11] and [ Reference Li14 , chapter 6].
The sums $S({\mathbb F}_p;\;\; f)$ are usually called complete sums. The problem usually becomes harder for smaller sets ${\mathcal X}$ , that is, for sums called incomplete sums.
Most of the attention the incomplete sums received is in the case of the sets ${\mathcal I}_N = \{0, \ldots, N-1\}$ of $N \le p$ consecutive integers. In fact, using the classical Weil bound and the completing technique (see [ Reference Iwaniec and Kowalski8 , section 12·2]), it is easy to show that in this case
for any nonlinear polynomial $f \in {\mathbb F}_p[X]$ , where the implied constant depends only on the degree n. Clearly the bound (1·2) is nontrivial only for $N \ge p^{1/2+\varepsilon}$ for some fixed $\varepsilon>0$ . For smaller values of N one can also use general bounds on the Weyl sums, see, for example, [ Reference Bourgain3 , theorem 5], which remain nontrivial as long as $N \ge p^{1/n+\varepsilon}$ , which is an optimal range. In the special case of monomials $f(X) = X^n$ , that is, for Gauss sums, Kerr [ Reference Kerr9 ] has obtained a better bound in the middle range of N. Kerr and Macourt [ Reference Kerr and Macourt10 , theorem 1·4] have also considered exponential sums over generalised arithmetic progressions rather than over intervals.
The multiplicative analogues of this problem, when, instead of interval, the sum is over a multiplicative subgroup ${\mathcal G}\subseteq {\mathbb F}_p^*$ has also been studied, however significantly less general results are known. Again, the Weil bound (1·1), using that
instantly gives a nontrivial result for subgroups of order $\tau=\#{\mathcal G} \ge p^{1/2+\varepsilon}$ .
In the case of linear polynomials, the bound of [ Reference Shparlinski23 , theorem 2] has started a series of further improvements which goes beyond this limitation on $\#{\mathcal G}$ , see [ Reference Bourgain2 , Reference Bourgain, Glibichuk and Konyagin4 , Reference Di Benedetto, Garaev, Garcia, Gonzalez–Sanchez, Shparlinski and Trujillo5 , Reference Heath–Brown and Konyagin7 , Reference Konyagin11 , Reference Shkredov21 ] and references therein.
Significantly less is known in the case of non-linear polynomials $f \in {\mathbb F}_p[X]$ . Until very recently, the only known approach to such bounds was that of Bourgain [ Reference Bourgain1 ], which actually works in a much more general scenario of exponential sums with linear combinations of several exponential functions. This result of Bourgain [ Reference Bourgain1 ] gives a bound saving some power $p^\eta$ compared to the trivial bound, however the exponent $\eta$ is not explicit and an attempt to make it explicit in [ Reference Popova20 , theorems 4 and 5] has some problems. Indeed, it seems that the argument in [ Reference Popova20 ] quotes incorrectly the result of [ Reference Shkredov22 , corollary 16], which, after correcting, leads to exponentially smaller saving.
More recently, the authors [ Reference Ostafe, Shparlinski and Voloch19 ] have used a different approach to a similar problem, based on a bound for the number of rational points on curves over finite fields from [ Reference Voloch27 ], which in some cases is stronger than the use of the classical Weil bound [ Reference Lorenzini15 , equation (5·7)], and estimate Kloosterman sums
over a subgroup ${\mathcal G}$ of order $\tau$ with $a,b\in {\mathbb F}_p^*$ . More precisely, the Weil bound, in the form given for example, in [ Reference Moreno and Moreno17 , theorem 2], instantly gives
for $a,b\in {\mathbb F}_p^*$ , which becomes trivial for $\tau < p^{1/2}$ .
On the other hand, by [ Reference Ostafe, Shparlinski and Voloch19 , corollary 2·9] we have
where, as usual, the notations $U = O(V)$ , $U \ll V$ and $ V\gg U$ are equivalent to $|U|\leqslant c V$ for some positive constant c, which throughout this work may depend only on n (and thus is absolute in (1·4)). Clearly, the bound (1·4) is nontrivial for $\tau\ge p^{3/7 + \varepsilon}$ for some fixed $\varepsilon>0$ .
We also note that several other bounds of exponential sums which rely on the result of [ Reference Voloch27 ] and go beyond the Weil bound (1·1) have been given in [ Reference Shparlinski and Voloch24 ], see also [ Reference Shparlinski and Wang25 ].
1·2. Approach
It is important to recall that it has been shown in [ Reference Shparlinski23 ], and used again in [ Reference Heath–Brown and Konyagin7 ], that in the case of linear polynomials, good bounds on the 4th moment of the corresponding sums already allow us to improve the Weil bound (1·3).
However, for higher degree polynomials this is not sufficient and one needs strong bounds on at least the 6th moment. Hence, to obtain nontrivial bounds for $S({\mathcal G};\;\; f)$ for a given non-constant polynomial $f\in{\mathbb F}_p[X]$ and a small multiplicative subgroup ${\mathcal G}$ of ${\mathbb F}_p^*$ , we modify the ideas of our previous work [ Reference Ostafe, Shparlinski and Voloch19 ] to investigate some high degree systems of polynomial equations. The main difficulty here is to study the generic absolute irreducibility of a certain family of curves and to be able to apply the result of [ Reference Voloch27 , theorem (i)]. We then combine this with the inductive approach of Bourgain [ Reference Bourgain1 ].
More precisely, the method of Bourgain [ Reference Bourgain1 ] (see also the exposition in [ Reference Garaev6 , section 4·4]) is inductive on the number of non-constant terms r of the polynomial, and it requires the case $r=1$ and $r=2$ as the basis of induction. For $r=1$ we can use the bound of Shkredov [ Reference Shkredov21 ], or even one of the earlier bounds from [ Reference Heath–Brown and Konyagin7 , Reference Shparlinski23 ]. So we start with obtaining a bound for binomial sums over a subgroup, see Lemma 3·7, which is similar to (1·4). The proof of Lemma 3·7 resembles that of our previous work [ Reference Ostafe, Shparlinski and Voloch19 , theorem 2·7] but requires to investigate the absolute irreducibility of some special polynomials. Then we use this bound to initiate the induction and derive our main result.
1·3. Main result
For a real $\varepsilon>0$ we set
and define the sequence $\eta_n(\varepsilon)$ , $n =3,4, \ldots$ , recursively as follows
where
Theorem 1·1. Let $f(X) \in {\mathbb F}_p[X]$ be a polynomial of degree $n\ge 1$ , and let ${\mathcal G}\subseteq {\mathbb F}_p^*$ be a subgroup of order $\tau \ge p^{3/7 + \varepsilon}$ for some fixed $\varepsilon>0$ . Then
Remark 1·2. We have included the case of linear polynomials in Theorem 1·1, but as we have mentioned in this case stronger results are available, see, for example, [ Reference Shkredov21 ].
Remark 1·3. It is obvious from our argument that if some information about the sparsity of the polynomial f in Theorem 1·1 is known, then this can be accommodated in a stronger bound with $\eta_r(\varepsilon)$ instead of $\eta_n(\varepsilon)$ where $r\le n$ is the number of monomials in f.
Since it may not be easy to understand the behaviour of the sequence $\eta_n(\varepsilon)$ from (1·6) and (1·7), here we give some clarifying examples.
First we compute explicitly,
We also notice that a simple inductive argument shows that for, say, $\varepsilon < 1/2$ , for some absolute constant $c > 0$ we have
(certainly for $\varepsilon > 1/2$ the Weil bound (1·3) is much stronger).
2. Algebraic geometry background
2·1. Rational points on absolutely irreducible curves
Let q be a prime power. It is well known that by the Weil bound we have
for any absolutely irreducible polynomial $F(X,Y) \in {\mathbb F}_q[X,Y]$ of degree d (see, for example, [ Reference Lorenzini15 , section X·5, equation (5·2)]). One can see that (2·1) is a genuine asymptotic formula only for $d = O(q^{1/4})$ and is in fact weaker than the trivial bound
for $d \ge q^{1/2}$ , which is exactly the range of our interest. To obtain nontrivial bounds for such large values of d we recall the following result, which is a combination of [ Reference Voloch27 , theorem (i)] with the Weil bound (2·1) (and the trivial inequality $p + 2d^2p^{1/2} \le 3p$ for $d \le p^{1/4}$ ).
Lemma 2·1. Let p be prime and let $F(X,Y) \in {\mathbb F}_p[X,Y]$ be an absolutely irreducible polynomial of degree $d<p$ . Then
2·2. Absolute irreducibility of some polynomials
To apply the bound of Lemma 2·1 we need to establish absolute irreducibility of polynomials relevant to our applications. We present it in a general form for arbitrary finite fields, as it may be useful for other applications. Below we use a natural mapping of integers into elements of a finite field ${\mathbb F}_q$ of q elements of characteristic p via the reduction modulo p.
Lemma 2·2. Given integers $n>m \ge 1$ with $\gcd(m,n)=1$ , there exists a non-zero polynomial $\Delta(U,V)\in {\mathbb Z}[U,V]$ , such that for every prime power q and positive integer s with $\gcd(s,q)=1$ and $A,B \in {\mathbb F}_q$ with $\Delta(A,B) \ne 0$ , the polynomial
is absolutely irreducible.
Proof. Let us begin by considering the case $s=1$ .
We introduce a new variable Z and note that for $s=1$ the curve $F=0$ is isomorphic to
The isomorphism is the projection to the X, Y-plane, with inverse given by
with some fixed integers u and v satisfying
The two equations in (2·2) have gradients
respectively. For the curve defined by the system (2·2) to be singular at a point (x, y, z) the corresponding gradients have to be linearly dependent. This condition, when fed back into (2·2) gives a relation between A, B.
More explicitly we proceed as follows.
First, we seek the polynomial $\Delta$ in the form
with some $\Delta_0(U,V)\in {\mathbb Z}[U,V]$ , thus $\Delta(A,B) \ne 0$ , guarantees that $mn \ne 0$ in ${\mathbb F}_q$ .
If (x, y, z) is a solution to (2·2) with $x=y=0$ , then $z^m = -A$ , $z^n = -B$ , and so $(\!-\!A)^n = (\!-\!B)^m$ . Thus we also request
The possibilities $x=z=0$ and $y=z=0$ can be similarly treated and lead to the requirement
If $x=0$ and $yz \ne 0$ , then the gradient condition gives $y = \zeta z$ with some $\zeta^{n-m}=1$ and (2·2) gives
Therefore, $\left(\zeta^n-1\right)^m A^n = \left(\zeta^m-1\right)^n B^m$ , and we also request
where the product is taken over all roots of unity $\zeta$ with $\zeta^{n-m}=1$ .
If $xyz \ne 0$ , then we see from (2·7) that there has to be a constant $\lambda$ with
so we can write $y = \zeta_1 x,$ and $z = \zeta_2 x$ with $\zeta_1^{n-m}= \zeta_2^{n-m}=1$ , leading to
where the product is taken over all pairs of roots of unity $(\zeta_1, \zeta_2)$ with $\zeta_1^{n-m}= \zeta_2^{n-m}=1$ .
A similar argument works at infinity and shows that, for generic A and B, the curve is smooth.
Given X, Y, there is a unique choice of Z satisfying (2·2), so the projection to the X, Y does not acquire singularities from distinct points in three-space. The only singularities are cusps coming from a vertical tangent line which are unibranched (since the curve in three-space is smooth). However, a reducible plane curve has singular points with more than one branch wherever two components meet. Hence (2·2) is an irreducible curve. (See [ Reference Kunz12 , chapter 16] for a detailed exposition of branches of curve singularities.)
We have shown that, for $s=1$ , the polynomial F is absolutely irreducible. We consider the algebraic curve ${\mathcal C}$ which is a non-singular projective model of $F=0$ (still with $s=1$ ).
Suppose $n>m>1$ . We now use an argument similar to [ Reference Ostafe, Shparlinski and Voloch19 , lemma 4·3].
For a point $P=(0,y_0)$ on the curve $F=0$ we have
Next we show that the point $P=(0,y_0)$ is a simple point on the curve $F=0$ with
(for generic A and B). It now suffices to show that the discriminant D(A, B) of $F(0,Y) \in {\mathbb F}_q[Y]$ (as a polynomial in A, B) is not identically zero, and can be chosen with integer coefficients which depend only on m and n.
Taking $A=1$ and $B = 0$ , the polynomial F specialises to
which has a non-zero discriminant as each factor $(Y^m(1-\xi) -1)$ is square-free and these factors are relatively prime. Thus we impose the condition
It remains to choose $ \Delta(A,B) \in {\mathbb Z}[A,B]$ as an arbitrary fixed polynomial which depends only on m and n and satisfies the divibility conditions (2·3), (2·4), (2·5), (2·6), (2·8) and (2·10).
We now consider the case of arbitrary $s\ge 1$ (and $n>m>1$ ).
So P corresponds to a place of ${\mathcal C}$ . We consider the functions x, y on ${\mathcal C}$ that satisfy the equation $F(x,y)=0$ . The function x has a simple zero at P, hence is not a power of another function on ${\mathcal C}$ . It follows from [ Reference Stichtenoth26 , proposition 3·7·3], that the equation $U^s = x$ is irreducible over the function field of ${\mathcal C}$ and defines a cover ${\mathcal D}$ of ${\mathcal C}$ . Now, consider any point Q on ${\mathcal D}$ above a point $(x_0,0)$ on ${\mathcal C}$ . Since x is not zero at $(x_0,0)$ (for generic A, B), the curve ${\mathcal D}$ is locally isomorphic to ${\mathcal C}$ near Q and we conclude, as above, that the function y on ${\mathcal D}$ has a simple zero at Q and, in particular, is not a power of another function on ${\mathcal D}$ . Again, we conclude that the equation $W^s = y$ is irreducible over the function field of ${\mathcal D}$ and defines a cover ${\mathcal E}$ of ${\mathcal D}$ . In other words, $F(U^s,W^s)=0$ is an absolutely irreducible equation defining the curve ${\mathcal E}$ , which concludes the case $n>m>1$ .
We are now left with $n>m=1$ . It is still true that a point $P=(0,y_0)$ is a simple point on the curve $F=0$ with (2·9) (for generic A, B). Indeed, if
then combining this with
we derive
Hence
Considering the resultant of $B(Y-B)^{n-1} -A$ and $BY^{n-1} - A$ (which clear does not vanish for $A=1$ and $B=0$ and thus is a nontrivial polynomial) gives a contradiction for generic A, B. The proof then continues as before in the case $n>m>1$ .
3. Exponential sums and systems of diagonal equations
3·1. Exponential sums and the number of solutions to some systems of equations
Here we collect some previous results on exponential sums and also about links between these bounds and the number of solutions to some congruences.
Given an integer vector $\mathbf{n} = \left(n_1, \ldots, n_r\right)\in {\mathbb Z}^r$ with $n_r> \cdots > n_1 \ge 1$ , and a subgroup ${\mathcal G} \subseteq {\mathbb F}_p^*$ , we denote by $Q_{k}(\mathbf{n};\;{\mathcal G})$ the number of solutions to the following system of r equations
The following link between $S({\mathcal G};\;\; f)$ and $Q_{k}(\mathbf{n};\; G)$ is a slight variation of several previous results of a similar spirit.
Lemma 3·1. Let
with nonzero coefficients $a_1, \ldots, a_r \in {\mathbb F}_p^*$ and integer exponents $n_r> \cdots > n_1 \ge 1$ . Then, for a subgroup ${\mathcal G} \subseteq {\mathbb F}_p^*$ and for any positive integers k and $\ell$ , we have
Proof. We start by noticing that, for any $h \in {\mathcal G}$ , we have
Hence, for any integer $k \ge 1$ we have
where $J_k(\lambda_1, \ldots, \lambda_r)$ is the number of solutions to the following system of equations:
Hence, changing the order of summations, we obtain
Observe that since $a_1, \ldots, a_r \ne 0$ , we have
where $\mathbf{n} = \left(n_1, \ldots, n_r\right)$ .
Writing
and applying the Hölder inequality, we derive
which concludes the proof.
We now establish a link in the opposite direction, that is, from bounds on exponential sums to bounds on $ Q_{k}(\mathbf{n};\; {\mathcal G})$ .
Lemma 3·2. Let $r \ge 2$ and let $\varepsilon\ge 0$ be fixed. Assume that there is some fixed $\eta> 0$ (depending only on r and $\varepsilon$ ) such that for all nonzero vectors $\left(a_1, \ldots, a_r\right)\in {\mathbb F}_p^r$ and for a vector $\mathbf{n} = \left(n_1, \ldots, n_r\right)\in {\mathbb Z}^r$ with $n_r> \ldots > n_1 \ge 1$ , for a subgroup ${\mathcal G} \subseteq {\mathbb F}_p^*$ of order $\tau$ with
we have
Then for any integer $k\ge 3$ we have
where $\xi = \min\{r, \eta(2k-6) +1 +7\varepsilon/3\}$ .
Proof. Using the orthogonality of characters, we write
Now, using our assumption (3·3) we obtain
Dropping the restriction $\left(a_1, \ldots, a_r\right)\ \ne \mathbf{0}$ from the summation, we now obtain
Since $r \ge 2$ , we obviously have
Thus applying Corollary 3·4 in Section 3·2 below and using that under our assumption (3·2) we have $\tau^{11/3} \ge \tau^5/p$ , we obtain
Recalling (3·2) again we see that
which together with (3·4) concludes the proof.
3·2. Bounds on the number of solutions to some systems of equations in six variables
We start with an observation that the results of this section are independent of those in Section 3·1 and hence there is no logical problem in our use of them in the proof of Lemma 3·2.
For $r=2$ and $\mathbf{n} = (m,n)$ we write $Q_{k}(m,n;\; {\mathcal G})$ for $Q_{k}(\mathbf{n};\; {\mathcal G})$ .
Here we obtain some bounds on $Q_{3}(m,n;\;{\mathcal G})$ . In fact, it is easier to work with the following system of equations:
instead of the system of the type (3·1) with group elements.
Denoting by $T_{3}(m,n;\;s)$ the number of solutions to (3·5) we see that
where
and, as before, $\tau = \# {\mathcal G}$ .
Lemma 3·3. For integers $n > m >0$ , we have
Proof. First we note that if $\gcd(m,n)= d$ then
where $e = \gcd(d,p-1)$ .
Hence we can assume that
which enables us to apply Lemma 2·2.
We now fix $x_4$ , $x_5$ and $x_6$ and thus we obtain $(p-1)^3$ systems of equations of the form
where
from which we derive
Under the assumption (3·7), let the polynomials $\Delta(U,V)\in {\mathbb Z}[U,V]$ be as in Lemma 2·2.
Since $\Delta$ depends only on m and n, we see that if p is large enough, $\Delta$ is a non-zero polynomial modulo p.
We assume first that $\Delta(A,B) = 0$ for a pair $(A,B)\in {\mathbb F}_p^2$ as above. Thus
If $\Delta\left(X^{sm}+x_5^{sm}+ x_6^{sm},X^{sn}+ x_5^{sn}+ x_6^{sn}\right)$ , as a polynomial in X, is not identically zero for some $(x_5,x_6)\in{\mathbb F}_p^2$ , then obviously it has O(s) zeros. Thus, in this case, the equation (3·9) has $O(sp^2)$ solutions $(x_4,x_5,x_6)\in{\mathbb F}_p^3$ .
On the other hand, if $\Delta\left(X^{sm}+x_5^{sm}+ x_6^{sm},X^{sn}+ x_5^{sn}+ x_6^{sn}\right)$ , as a polynomial in X, is identically zero, then it also holds for $X=0$ , thus
Now, a similar argument shows that (3·10) holds for O(sp) pairs $(x_5,x_6)$ for which there are at most p values of $x_4$ .
Therefore, the equation (3·9) has $O(sp^2)$ solutions $(x_4,x_5,x_6)\in{\mathbb F}_p^3$ in total.
For each of such $O\left(sp^2\right)$ values of $(x_4,x_5,x_6)$ the corresponding equation (3·8) is nontrivial since it contains a unique term $nx_1^{sm(n-1)} x_2^{sm}$ and hence has O(sp) solutions $(x_1,x_2)$ after which there are O(s) possible values for $x_3$ (we recall that the implied constants may depend on n). Hence, the total contribution from the case $\Delta(A,B) = 0$ is $O\left(s^3 p^3\right)$ .
If $\Delta(A,B) \ne 0$ , then for the corresponding $O(p^3)$ possibilities for $(x_4, x_5, x_6) \in {\mathbb F}_p^3$ , by Lemma 2·2, we can apply Lemma 2·1 to bound the number of solutions to (3·8) (after which we have O(s) possibilities for $x_3$ ). Hence, the total contribution from the case $\Delta(A,B) \ne 0$ is $O\left(s \left(s^{4/3} p^{2/3} + p\right)p^3\right)$ .
Therefore $T_{3}(m,n;\;s) \le s^3 p^3 + s^{7/3} p^{11/3} + sp^4$ . Since $s^3 p^3 \le s^{7/3} p^{11/3}$ for $s \le p$ , the result follows.
Recalling (3·6), we see that Lemma 3·3 implies the following.
Corollary 3·4. For integers $n > m >0$ , we have
Remark 3·5. We recall that the method of Kurlberg and Rudnick [ Reference Kurlberg and Rudnick13 , lemma 5], immediately implies that $Q_{2}(m,n;\; {\mathcal G}) \ll \tau^{2}$ . However this bound is not sufficient for our purpose.
3·3. Bounds on monomial and binomial sums
First we recall the following result of Shkredov [ Reference Shkredov21 , theorem 1] (with a slight generalisation and also combined with a direct implication of (1·1)).
Lemma 3·6. Let $f(X) = aX^n \in {\mathbb F}_p[X]$ of degree $n\ge 1$ and with $a \ne 0$ , and let ${\mathcal G}\subseteq {\mathbb F}_p^*$ be a subgroup ${\mathcal G}$ of order $\tau$ . Then
Proof. We remark that the result of Shkredov [ Reference Shkredov21 , theorem 1] corresponds to $n=1$ . Otherwise we note that
where $d = \gcd(\tau, n)$ and ${\mathcal G}^d= \{g^d \;:\; g \in {\mathcal G}\}$ .
We now derive the following estimate, which improves (1·3) for $\tau \le p^{21/40}$ , remains nontrivial for $\tau \ge p^{3/7+\varepsilon}$ for any fixed $\varepsilon>0$ and which we believe is of independent interest. For this, we apply Lemma 3·1 with $k=\ell=3$ and we use Corollary 3·4.
Lemma 3·7. Let $f(X) = aX^m + bX^n \in {\mathbb F}_p[X]$ with integers $n > m \ge 1$ and $(a,b) \ne (0,0)$ , and let ${\mathcal G}\subseteq {\mathbb F}_p^*$ be a subgroup of order $\tau$ . Then
Proof. If $ab= 0$ then the result is instant from Lemma 3·6.
Hence we now assume $a,b \in {\mathbb F}_p^*$ . We apply Lemma 3·1 with
and the bound of Corollary 3·4. We also note that for $\tau >p^{21/40}$ we have
Hence we only need to apply Corollary 3·4 for $\tau \le p^{21/40}$ in which case $ \tau^{11/3} \ge \tau^5/p$ , and thus in this case we simply have $Q_{3}(m,n;\; {\mathcal G}) \ll \tau^{11/3}$ and the result follows.
4. Proof of Theorem 1·1
4·1. Preliminaries and the basis of induction
We prove the result by induction on the number of terms r in the polynomial
with nonzero coefficients $a_1, \ldots, a_r \in {\mathbb F}_p^*$ and integer exponents $n =n_r> \cdots > n_1 \ge 1$ .
We see from Lemma 3·7 that for $r=1,2$ the condition (3·3) of Lemma 3·2 is satisfied with
respectively, where $\eta_{1}(\varepsilon)$ and $\eta_{2}(\varepsilon)$ are given by (1·5), which form the basis of induction.
4·2. Inductive step
Assume that the result holds for all nontrivial polynomials of degree at most n with at most $r-1$ monomials and we prove it for polynomials with $r \ge 3$ monomials. First we note that we can assume that $\tau \le p^{3/4}$ since otherwise the bound (1·3) is stronger than that of Theorem 1·1.
In particular, the condition (3·2) of Lemma 3·2 is satisfied. We fix some arbitrary positive integers k, $\ell$ , u and v with $u, v \le r$ . Let
We now use the trivial bounds
In fact, we choose $u = r-1$ and $v = 2$ . Furthermore, we recall the definition (1·7) and set
in which case, using the induction assumption, by Lemma 3·2, used with $u = r-1$ instead of r, we have
while by Corollary 3·4, using that $\tau\le p^{3/4}$ , we obtain
Indeed, (4·3) follows from the definition of $\kappa_r(\varepsilon)$ in (1·7), which ensures that $\xi =r-1$ in Lemma 3·2.
Next, substituting the bounds (4·1), (4·3) and (4·4) in the estimate of Lemma 3·1, we obtain
Hence
Recalling the definition (1·6) and the choice of k in (4·2), we conclude the proof.
5. Comments
If $\vartheta$ is a generator of ${\mathcal G}$ then the sum $S({\mathcal G};\;\; f)$ can be written as
This reformulation also allows us to generalise these sums to twisted sums,
to which all our results apply without any changes (with just minor typographic adjustments). In turn, together with the well-known completing technique (see, for example, [ Reference Iwaniec and Kowalski8 , section 12·2]) bounds on the sums $S_b({\mathcal G};\;\; f) $ lead to bounds on incomplete sums
We note that in [ Reference Niederreiter and Winterhoff18 ] sequences of the form $\left(f\left(\vartheta^{x}\right)\right)$ have been studied as sources of pseudorandom numbers, but with nontrivial results only in the case of periods $\tau > p^{1/2+\varepsilon}$ , while our results allows us to extend this range to $\tau > p^{3/7+\varepsilon}$ .
We also note that in [ Reference Meidl and Winterhof16, Reference Winterhof29 ] the sequence
has been suggested as a source of pseudorandom numbers. Unfortunately neither the method of Bourgain [ Reference Bourgain1 ] nor of this work applies to the corresponding exponential sums
(with a natural convention that the values with $a\vartheta^{x}=-b$ are excluded), which are necessary for investigating this sequence. So we leave a question of obtaining such nontrivial bounds for $\tau < p^{1/2}$ as an open problem. Even the case of complete sums
is of interest.
Acknowledgements
During the preparation of this work, the first two authors (A.O. and I.E.S.) were partially supported by the Australian Research Council Grant DP200100355. The third author (J.F.V.) was partially supported by a grant from the Ministry of Business, Innovation and Employment of New Zealand.