Character sums and arithmetic combinatorics

Abstract

In this survey we review some old and new results on character sums and their applications to various problems in analytic number theory, e.g., smallest quadratic nonresidues, Dirichlet L-function, Linnik’s problem. We also discuss open problems in this area. Some of the techniques involved belong to arithmetic combinatorics. One may hope for these methods to lead to further progress.

A function $\chi: \mathbb{Z}/q\mathbb{Z} \rightarrow \{ z \in \mathbb{C}: \vert z\vert = 1\} \cup \{ 0\}$ is a multiplicative character mod q if it satisfies the properties that χ(m n) = χ(m)χ(n), and χ(n) = 0 if $\gcd (n,q)\not =1.$ We are interested in bounding non-trivially the character sum of χ over an interval of length H ≤ q. More precisely, we want to study the following problem.

FormalPara Problem 1.

Assuming χ is non-principal and q ≫ 0, how small H = H(q) can be such that

$$\displaystyle{ \Big\vert \sum _{n=a+1}^{a+H}\chi (n)\Big\vert < H^{1-\epsilon }\;? }$$

(1)

In 1918, Polya and Vinogradov (Theorem 12.5 in [27]) had the estimate for $H \gg \sqrt{q}\log q$.

FormalPara Theorem 1 (Polya-Vinogradov).

Let χ be a non-principal Dirichlet character mod q. Then

$$\displaystyle{\Big\vert \sum _{m=a+1}^{a+H}\chi (m)\Big\vert < Cq^{\frac{1} {2} }(\log q).}$$

Forty four years later Burgess [5] improved Polya and Vinogradov’s result to $H > q^{\frac{1} {4} +\varepsilon }$, first for prime moduli, then for cube-free moduli.

FormalPara Theorem 2 (Burgess).

For $\varepsilon > 0$ there exists δ > 0 such that if $H > p^{\frac{1} {4} +\varepsilon },$ then

$$\displaystyle{\Big\vert \sum _{m=a+1}^{a+H}\chi (m)\Big\vert \ll p^{-\delta }H.}$$

Using sieving, there is the following

FormalPara Corollary 1.

The smallest quadratic nonresidue mod p is at most $p^{ \frac{1} {4\sqrt{e}}+\varepsilon }$.

At present time, Burgess’ estimate is still the best. Davenport and Lewis generalized it to higher dimensions by replacing the interval by a box $B \subset \mathbb{F}_{p^{n}}.$

Let {ω ₁, …, ω _n } be an arbitrary basis for $\mathbb{F}_{p^{n}}$ over $\mathbb{F}_{p}$. Then for any $x \in \mathbb{F}_{p^{n}}$, there is a unique representation of x in terms of the basis.

$$\displaystyle{x = x_{1}\omega _{1} + \cdots + x_{n}\omega _{n}}$$

A box $B \subset \mathbb{F}_{p^{n}}$ is a set such that for each j, the coefficients x _j form an interval.

$$\displaystyle\begin{array}{rcl} B& =& \Big\{\sum _{j=1}^{n}x_{ j}\omega _{j}: x_{j} \in [a_{j} + 1,a_{j} + H_{j}],\quad \forall i\Big\} \\ & =& \prod _{j=1}^{n}[a_{ j} + 1,a_{j} + H_{j}]. {}\end{array}$$

(2)

Davenport and Lewis had the following non-trivial estimate for character sums over boxes. (See [6, 28] for work on special boxes.)

FormalPara Theorem 3.

[12, Theorem 2] Let H _j = H for j = 1,…,n, with

$$\displaystyle{ H > p^{ \frac{n} {2(n+1)} +\delta }\text{ for some }\delta > 0 }$$

(3)

and let p > p(δ). Then, with B defined as above

$$\displaystyle{\big\vert \sum _{x\in B}\chi (x)\big\vert < (p^{-\delta _{1} }H)^{n},}$$

where δ ₁ = δ ₁ (δ) > 0.

For n = 1 (i.e., $\mathbb{F}_{q} = \mathbb{F}_{p}$) this is Burgess’ result. But as n increases, the exponent in (3) tends to $\frac{1} {2}$.

Motivated by the work of Burgess and Davenport-Lewis, we obtained the following estimates on incomplete character sums. Our result improves Theorem DL for n > 4 [7, 8] and is also uniform in n.

FormalPara Theorem 4.

Let χ be a non-trivial multiplicative character of $\mathbb{F}_{p^{n}}$ , and let $\varepsilon > 0$ be given. If

$$\displaystyle{B =\prod _{ j=1}^{n}[a_{ j} + 1,a_{j} + H_{j}]}$$

is a box satisfying

$$\displaystyle{\mathop{\Pi }\limits _{j=1}^{n}H_{ j} > p^{(\frac{2} {5} +\varepsilon )n},}$$

then for $p > p(\varepsilon )$

$$\displaystyle{\Big\vert \sum _{x\in B}\chi (x)\Big\vert \ll _{n}p^{-\frac{\varepsilon ^{2}} {4} }\vert B\vert,}$$

unless n is even and $\chi \vert _{F_{2}}$ is principal, where F ₂ is the subfield of size p ^n∕2 , in which case

$$\displaystyle{\Big\vert \sum _{x\in B}\chi (x)\Big\vert \leq \max _{\xi }\big\vert B \cap \xi F_{2}\big\vert + O_{n}(p^{-\frac{\varepsilon ^{2}} {4} }\vert B\vert ).}$$

The proof of Theorem 4 used ingredients and techniques from sum–product theory, specially multiplicative energy. Theorem 4 was improved by Konyagin [30] for regular boxes.

FormalPara Theorem 5.

[30] Let χ be a non-trivial multiplicative character of $\mathbb{F}_{p^{n}}$ , and let B be given as in  (2) with

$$\displaystyle{H_{j} = H > p^{\frac{1} {4} +\epsilon },\;\;\forall j.}$$

Then

$$\displaystyle{\Big\vert \sum _{x\in B}\chi (x)\Big\vert \ll _{n}p^{-\delta }\vert B\vert,}$$

where δ = δ(ε) > 0.

FormalPara Problem 2.

Obtain a non-trivial estimate on $\sum _{x\in B}\chi (x)$ , assuming $\vert B\vert > q^{1/4+\varepsilon }$ and B not ‘essentially’ contained in a multiplicative translate of a subfield.

As in [12] (see p. 131), Theorem 4 has the following application to the distribution of primitive roots of $\mathbb{F}_{p^{n}}$.

FormalPara Corollary 2.

Let $B \subset \mathbb{F}_{p^{n}}$ be as in Theorem  4 and satisfying $\max _{\xi }\big\vert B \cap \xi F_{2}\big\vert < p^{-\varepsilon }\vert B\vert$ if n even. The number of primitive roots of $\mathbb{F}_{p^{n}}$ belonging to B is

$$\displaystyle{\frac{\varphi (p^{n} - 1)} {p^{n} - 1} \vert B\vert (1 + o(p^{-\tau ^{{\prime}} })),}$$

where $\tau ^{{\prime}} =\tau ^{{\prime}}(\varepsilon ) > 0$ and assuming $n \ll \log \log p$.

The proof of Corollary 2 is by combining character sums estimate with the following.

$$\displaystyle{\begin{array}{ll} &\frac{\phi (p^{n}-1)} {p^{n}-1} \bigg\{1 +\sum \limits _{{ d\vert p^{n}-1 \atop d>1} }\ \frac{\mu (d)} {\phi (d)}\sum _{\text{ord}(\chi )=d}\chi (x)\bigg\} = \left \{\begin{array}{@{}l@{\quad }l@{}} 1\text{ if x is primitive,}\quad \\ 0\ \text{ otherwise.} \quad \end{array} \right. \end{array}}$$

We also generalize Burgess’s inequality in a slightly different direction.

FormalPara Theorem 6.

Let $\mathcal{P}$ be a proper d-dimensional generalized arithmetic progression in $\mathbb{F}_{p}$ with

$$\displaystyle{\vert \mathcal{P}\vert > p^{\frac{2} {5} +\varepsilon },\text{ some }\varepsilon > 0}$$

If χ is a non-principal multiplicative character of $\mathbb{F}_{p}$ , we have

$$\displaystyle{\Big\vert \sum _{x\in \mathcal{P}}\chi (x)\Big\vert < p^{-\tau }\vert \mathcal{P}\vert,}$$

where $\tau =\tau (\varepsilon,d) > 0$ and assuming $p > p(\varepsilon,d)$.

FormalPara Remark 6.1.

The exponent $\frac{2} {5} < \frac{1} {2}$ does not depend on d.

FormalPara Remark 6.2.

Similar results hold for $\mathbb{F}_{p^{n}}$ with worse exponent.

Using Freiman’s theorem, sum–product, and character sums, we obtained the following.

FormalPara Corollary 3.

Given C > 0 and $\varepsilon > 0$ , there is a constant $\kappa =\kappa (C,\varepsilon )$ and a positive integer $k < k(C,\varepsilon )$ such that if $A \subset \mathbb{F}_{p}$ satisfies

• (i) $\vert A\vert > p^{2/5+\varepsilon }$

• (ii) |A + A| < C|A|.

Then we have

$$\displaystyle{\vert A^{k}\vert >\kappa p,}$$

where A ^k = A⋯A is the k-fold product set of A.

There is also the study of multi-linear character sums.

Let (L _j )_{1 ≤ j ≤ n} be n independent linear forms in n variables over $\mathbb{F}_{p}$, and let χ be a non-principal multiplicative character mod p. Denote a box by $B =\prod _{ i=1}^{n}[a_{i},\;a_{i} + H].$ We are interested in the following non-trivial estimates

$$\displaystyle{ \bigg\vert \sum _{\begin{array}{c}x\in B\end{array}}\chi \Big(\prod _{j=1}^{n}L_{ j}(x)\Big)\bigg\vert < p^{-\delta }H^{n}. }$$

(4)

FormalPara Theorem 7 (Burgess).

Assume

$$\displaystyle{ H > p^{\frac{1} {2} - \frac{1} {2(n+1)} +\varepsilon }. }$$

(5)

Then  (4) holds.

For n = 1, condition (5) is the well-known Burgess assumption $H > p^{\frac{1} {4} +\varepsilon }$ for character sum bound. For n = 2, it is $H > p^{\frac{1} {3} +\varepsilon }$. We generalized the Burgess assumption to any dimension. (See [4].)

FormalPara Theorem 8 (Bourgain-Chang).

Assume

$$\displaystyle{H > p^{\frac{1} {4} +\varepsilon },\;\text{ for any }n.}$$

Then  (4) holds.

The theorem above has application to character sums of polynomials.

FormalPara Theorem 9.

Let f(x ₁ ,…,x _d ) be a homogeneous polynomial of degree d and split over $\overline{\mathbb{F}}_{p}$ , and let $B =\prod _{ i=1}^{d}[a_{i},a_{i} + H] \subset \mathbb{F}_{p}^{d}$ be a box of length H with

$$\displaystyle{H = p^{\frac{1} {4} +\varepsilon }.}$$

Then

$$\displaystyle{\Big\vert \sum _{x\in B}\chi (f(x))\Big\vert < p^{-\delta }H^{d}.}$$

This improves Gillett’s condition $H > p^{ \frac{d} {2(d+1)} +\varepsilon }.$

Coming back to Problem 1, for special moduli, the condition on H in Burgess’ theorem can be improved. One can proved (1) for much smaller intervals. There are two classical results, based on quite different arguments by Graham–Ringrose ([27], Corollary 12.15) and Iwaniec ([27], Theorem 12.16).

First, for the modulus q, we set up the following notations for the largest prime divisor $\mathcal{P}$ of q, and the core k of q.

$$\displaystyle{\mathcal{P} =\max _{p\vert q}p\quad \text{ and }\quad k =\prod _{p\vert q}p.}$$

FormalPara Theorem 10.

[18] Let χ be a primitive character of modulus q ≥ 3 with q square free. Then, for

$$\displaystyle{N = \vert I\vert \geq q^{ \frac{4} {\sqrt{\log \log q}} } + \mathcal{P}^{9}}$$

we have

$$\displaystyle{\Big\vert \sum _{n\in I}\chi (n)\Big\vert \ll Ne^{-\sqrt{\log q}}.}$$

The purpose of the work of Graham and Ringrose is to study the following least quadratic nonresidue problem.

FormalPara Problem 3.

Let p be a prime, and let n(p) be the least quadratic nonresidue mod p. Find a lower bound on n(p).

Independent of Burgess’ result $n(p) \leq p^{\; \frac{1} {4\sqrt{e}}+\varepsilon }$, Friedlander [14] and Salié [35] showed that $n(p) = \Omega (\log p)$, i.e., there are infinitely many p such that $n(p) > c\log p$ for some absolute constant c. By assuming the Generalized Riemann Hypothesis, in 1971 Montgomery [33] proved that $n(p) = \Omega (\log p\;\log \log p).$ Using Theorem 10, Graham and Ringrose showed that $n(p) = \Omega (\log p\;\log \log \log p)$ unconditionally.

In 1974, Iwaniec [26] proved the following theorem by generalizing Postnikov’s theorem [34].

FormalPara Theorem 11.

[34] Let χ be a primitive character of modulus q, $2 \nmid q$ . Then, for

$$\displaystyle{ k^{100} < N < N^{{\prime}}\leq 2N }$$

(6)

we have

$$\displaystyle{\Big\vert \sum _{N<n\leq N^{{\prime}}}\chi (n)\Big\vert \leq C^{s(\log s)^{2} }N^{1- \frac{c} {s^{2}\log s} },}$$

where $s = \frac{\log q} {\log N}.$

Theorem 11 is good for q powerful. A related problem is about the digital aspects of the primes. Let x < N = 2ⁿ. Write

$$\displaystyle{x = x_{0} + 2x_{1} + 2^{2}x_{ 2} + \cdots + 2^{n-1}x_{ n-1}\;\;\text{ with }\;\;x_{0},x_{1},\cdots \,,x_{n-1} \in \{ 0,1\}.}$$

For $A \subset \{ 1,\cdots \,,n\}$, given {α _j  ∈ { 0, 1}} _j ∈ A , one expects

$$\displaystyle{\left \vert \{p = x < N: x_{j} =\alpha _{j},\;\forall j \in A\}\right \vert \sim \frac{N} {\log N}\;2^{{-\vert A\vert } }.}$$

FormalPara Problem 4.

How large can A be?

For related work, see Sierpinski [39], Harman–Katai [22], Bourgain [3].

Theorem 10 is for q with small prime factors (smooth moduli), for which one assumes

$$\displaystyle{ \log N \gg \log \mathcal{P} + \frac{\log q} {\sqrt{\log \log q}}. }$$

(7)

On the other hand, Theorem 11 is for q with small core. Condition (6) implies that

$$\displaystyle{ \log N \gg \log k. }$$

(8)

If fix k, to get non-trivial result, in Theorem 11, one needs to assume

$$\displaystyle{ \log N \gg \log k + (\log q)^{\frac{3} {4} +\epsilon }. }$$

(9)

Both are special cases of the following theorem in [11].

Denote

$$\displaystyle{K = \frac{\log q} {\log k}.}$$

FormalPara Theorem 12.

Assume N satisfies

$$\displaystyle{q > N > \mathcal{P}^{10^{3} }}$$

and

$$\displaystyle{ \log N > (\log q)^{ \frac{9} {10} }\; +\; 10^{3}\;\frac{\log 2K} {\log \log q} \;\log k\;. }$$

(10)

Let χ be a primitive multiplicative character modulo q and I an interval of size N. Then

$$\displaystyle{ \Big\vert \sum _{x\in I}\chi (x)\Big\vert \ll Ne^{-(\log N)^{3/5} }. }$$

(11)

FormalPara Remark 12.1.

In the same spirit as assumptions (7) and (9), assumption (10) can be replaced by the stronger and friendlier assumption.

$$\displaystyle{ \log N \gg \log \mathcal{P}\; +\; \frac{\log q} {\log \log q}. }$$

(12)

(The second term of condition (12) is clearly bigger than either term of (10).)

FormalPara Remark 12.2.

This result is completely general and gives bounds for very short character sums as soon as $\log \mathcal{P}$ is small compared with $\log q$.

FormalPara Remark 12.3.

To compare Theorem 12 with Theorem 10, we note also that condition (12) gives a better result than (7). Moreover, condition (7) is restricted to square free q. As for comparing Theorem 12 with Theorem 11, we let k be square free and q = k ^m, where m is large but not too large. More precisely, we assume $\log m = o(\log \log k)$. Theorem 11 certainly requires that $\log N > C\log k$ while condition (10) in Theorem 12 becomes $\log N > (m\log k)^{ \frac{9} {10} } + C\frac{\log m} {\log \log q}\;\log k$, which is clearly better.

FormalPara Remark 12.4.

We did not try to optimize the power of $\log q$ in the first term in (10) nor the saving in (11).

The following is a mixed character sum version of Theorem 12 (see also [10]).

FormalPara Theorem 13.

[15] Under the assumptions of Theorem  12,

$$\displaystyle{\Big\vert \sum _{x\in I}\chi (x)e^{if(x)}\Big\vert < Ne^{-\sqrt{\log N}}}$$

assuming $f(x) \in \mathbb{R}[x]$ of degree at most $(\log N)^{c}$ for some c > 0.

FormalPara Corollary 4.

Let T > 0. Assume N satisfies

$$\displaystyle{q > N > \mathcal{P}^{10^{3} }}$$

and q satisfies

$$\displaystyle{\log N > (\log qT)^{ \frac{9} {10} } + 10^{3}\;\frac{\log 2K} {\log \log q} \;\log k.}$$

Then for χ primitive, we have

$$\displaystyle{\Big\vert \sum _{n\in I}\chi (n)n^{it}\Big\vert < Ne^{-\sqrt{\log N}}\quad \text{for}\;\;\vert t\vert < T.}$$

Following the classical arguments going back to Hadamand, de-la-Vallee-Poissin, and Landau, the above estimates lead to zero-free regions for the corresponding Dirichlet L-functions. Denote

$$\displaystyle{L(s,\chi ) =\sum _{n}\chi (n)n^{-s},\;\;\;\;s =\rho +it.}$$

Iwaniec [26] obtained the following results.

FormalPara Theorem 14.

[26] Assume |L(s,χ)| < M for ρ > 1 −η, |t| < T ² . Then L(s,χ) has no zeros in the region $\rho > 1 - \frac{\eta } {400\log M},\;\vert t\vert < T$ , except for possible Siegel zeros.

FormalPara Corollary 5.

[26] Assume Y and γ > 0 satisfy

$$\displaystyle{\big\vert \sum _{n\sim N}\chi (n)n^{it}\big\vert < N^{1-\gamma }\;\;\;\text{ for }N > Y,\vert t\vert < T.}$$

Then

$$\displaystyle{\rho > 1 - \frac{c} {\log Y + \frac{1} {\gamma } \;\log \frac{1} {\gamma } + \frac{1} {\gamma } \;\log \log \frac{qT} {Y } }\;.}$$

From Corollary 4 and Corollary 5, one derives bounds on the Dirichlet L-function L(s, χ) and zero-free regions the usual way. For a detailed argument, see, for instance, Lemmas 8–11 in [26]. This leads to the following theorem.

FormalPara Theorem 15.

Let χ be a primitive multiplicative character with modulus q. For T > 0, let

$$\displaystyle{\theta = c\min \Big( \frac{1} {\log \mathcal{P}}, \frac{\log \log k} {(\log k)\log 2K}, \frac{1} {(\log qT)^{9/10}}\Big).}$$

Then the Dirichlet L-function $L(s,\chi ) =\sum _{n}\chi (n)n^{-s},s =\rho +it$ has no zeros in the region $\rho > 1-\theta,\;\vert t\vert < T$ , except for possible Siegel zeros.

It follows in particular that $\theta \log qT \rightarrow \infty$ if $\frac{\log \mathcal{P}} {\log q} \rightarrow 0$.

In certain range of k, this improves Iwaniec’s bound (See [27], Theorem 8.29.)

$$\displaystyle{\theta =\min \bigg\{ c\; \frac{1} {(\log T)^{\frac{2} {3} }(\log \log T)^{\frac{1} {3} }} \;, \frac{1} {\log k}\bigg\}.}$$

A well-known application of zero-free region is to primes in arithmetic progressions. In 1944, Linnik proved the following theorem about the least prime in an arithmetic progression.

FormalPara Theorem 16.

[31, 32] There exists c such that if (a,q) = 1, then there is a prime p < q ^c such that p ≡ a mod  q.

For explicit value of c in Theorem 16, Xylouris [40] has the best estimate c = 5. 2 by using Heath-Brown [23, 24] (who obtained c = 5. 5) proposed improvements.

Theorem 15 gives a lower c for q smooth.

FormalPara Theorem 17.

In Theorem  16 , one may take $c = \frac{12} {5} +\epsilon$ , assuming $\log \mathcal{P} < \frac{\log q} {\log \log q}.$

Estimates on short character sums are also related to Polya–Vinogradov’s theorem. Based on the work of Granville and Soundararajan [19] (which characterizes when character sums are large), Goldmakher [17] used Theorem 10 to improve Polya–Vinogradov’s bound on $\sum _{n<x}\chi (n)$ and obtained the following.

FormalPara Theorem 18.

[18] Let χ mod  q be a primitive character. Then

$$\displaystyle{\Big\vert \sum _{n<x}\chi (n)\Big\vert \ll \sqrt{q}\;\log q\;\sqrt{\log ^{3 } q}\;\Big( \frac{1} {\log ^{2}q} + \frac{\log \mathcal{P}} {\log q} \Big)^{\frac{1} {4} }.}$$

When q is square free, then

$$\displaystyle{\Big\vert \sum \chi (n)\Big\vert \ll \sqrt{q}\;\; \frac{\log q} {\;\;(\log \log q)^{\frac{1} {4} }}.}$$

Instead of Theorem 10, we use Theorem 17 (and Granville–Soundararajan) and obtain the following.

FormalPara Corollary 6.

Let χ mod  q be a primitive character, and let

$$\displaystyle{M = (\log q)^{ \frac{9} {10} } + (\log 2K)\frac{\log k} {\log \log k} +\log \mathcal{P}.}$$

Then

$$\displaystyle{\Big\vert \sum _{n<x}\chi (n)\Big\vert \ll \sqrt{q}\;\;\sqrt{\log q}\;\;\sqrt{M}\;\;\sqrt{\log \log \log q}.}$$

When q is square free,

$$\displaystyle{\Big\vert \sum _{n<x}\chi (n)\Big\vert \ll \sqrt{q}\;\; \frac{\log q} {\;\;(\log \log q)^{\frac{1} {2} }}.}$$

Let $f(x_{1},\ldots,x_{n}) \in \mathbb{F}_{q}[x_{1},\ldots,x_{n}]$, q = p ^ℓ be a polynomial of degree d. We are interested in bounding the exponential sum

$$\displaystyle{ S =\sum _{x_{1},\ldots,x_{n}}e_{p}\Big(\mathrm{Tr}\big(f(x_{1},\ldots,x_{n})\big)\Big) }$$

(13)

as well as a certain incomplete sums where the variables are restricted to a ‘box’ $B \subset \mathbb{F}_{q}^{n}$. More specifically, we consider various instances of this question where Deligne type estimates are not applicable, either because f is too singular or the box B is too small. In their work on Gowers’ norms, Green and Tao [20] obtain non-trivial bounds in the situation where $\mathbb{F}_{q} = \mathbb{F}_{p}$ and d are fixed and n is large, assuming that the value of f is not determined by a few polynomials of lower degree.

FormalPara Problem 5.

Obtain quantitative version of the Green–Tao result.

For Problem 5, see the recent result by Forni and Flaminio [13].

Estimates of this type are also particularly relevant to circuit complexity [21].

Using methods from geometry of numbers, W. Schmidt [36] obtained bounds on incomplete sums (13) over boxes, but without exploring the effect of large n or ℓ.

FormalPara Problem 6.

Investigate the bounds obtained in [36] when n or ℓ is large.

It is possible that techniques from arithmetic combinatorics may be relevant.

For n = 1, estimates of this type are obtained in [2].

There are some other problems related to Problem 1.

FormalPara Problem 7.

Let V be a vector subspace of $\mathbb{F}_{p^{n}}$ over $\mathbb{F}_{p}$ , not essentially contained in a multiplicative translate of a subfield. Under what assumptions on $\dim _{\mathbb{F}_{p}}V$ can one obtain non-trivial bounds on $\sum _{x\in V }\chi (x)$ ?

The arithmetic combinatorics approach permits to go below the n∕2 barrier of classical methods. We are particularly interested in the situation where p is fixed and n is large. Assuming $\xi \in \mathbb{F}_{p^{n}}$ a generator, one may specify further $V =\langle \xi ^{j}: j \in S\rangle$ with $S \subset \{ 0,1,\ldots,n - 1\}$. In the special case S = { 0, 1, …, m}, V. Shoup [38] used the Hasse–Weil method to get results for $m = O(\log n)$.

In the paper [8], we also succeeded in improving Karacuba’s result on character sums of the type

$$\displaystyle{ \sum _{x\in I}\;\Big\vert \sum _{y\in A}\chi (x + y)\Big\vert, }$$

(14)

where χ is a multiplicative character$\pmod p$, I an interval and $A \subset \mathbb{F}_{p}$ arbitrary. This result was important to the recent work [16] on the distribution of quadratic and higher order residues$\pmod p$. See also [25].

Further improvement on Karacuba’s result was obtained by X. Shao [37].

FormalPara Theorem 19.

[39] Let $q \in \mathbb{Z}_{+}$ be cube-free and χ mod q be non-principal. If $A \subset [1,q]$ is a union of disjoint intervals I ₁ ,…,I _s with $\vert A\vert > q^{1/4+\varepsilon }s^{1/2}$ and $\vert I_{j}\vert > q^{\varepsilon },(1 \leq j \leq s)$ for any $\varepsilon > 0$ , then $\sum _{n\in A}\chi (n)$ has a non-trivial bound.

One could expect that for ‘most p’ better results are obtainable. However, the following problem seems still open.

FormalPara Problem 8.

Show that for most p, the largest gap between quadratic residues is o(p ^1∕4 ).

The following interesting character sum questions were highlighted in Karacuba’s survey [29].

FormalPara Problem 9.

Obtain a non-trivial bound on general sums

$$\displaystyle{\sum _{x\in A,\;y\in B}\chi (x + y),}$$

when $\vert A\vert \sim \sqrt{p} \sim \vert B\vert$.

It is well-known that this question is related to the Paley graph conjecture and also relevant to the theory of ‘extractor’ in computer science [1].

FormalPara Problem 10.

Prove that for p large and $a\not =0\pmod p$

$$\displaystyle{\sum _{1\leq x<H}\Big(\frac{x + a} {p} \Big)\Lambda (x) = o(H),}$$

when $H \sim \sqrt{p}$.

Results of this type were obtained by Vinogadov, for large values of H.

FormalPara Problem 11.

Prove that for large p

$$\displaystyle{\min \left \{1 \leq x \leq p:\Big (\frac{a + x^{2}} {p} \Big) = -1\right \} = o(\sqrt{p})}$$

uniformly in 1 ≤ a ≤ p.

In [9], the bound $p^{ \frac{1} {2\sqrt{e}}+\varepsilon }$ was obtained, but for a ≠ 0 given.