Sliding over the Polya-Vinogradov gap

In my series of papers with É. Fouvry and Ph. Michel, we seem to alternate between longer papers and shorter ones. The last one, which we just put up on arXiv, is in some sense the shortest one: even if it goes up to 19 pages in length, the basic idea can be explained extremely quickly, and much of the paper is taken with variations on its basic theme and illustrations.

The context is the all-important problem of estimating short exponential sums, in the specific case of sums over intervals in a cyclic group $A=\mathbf{Z}/m\mathbf{Z}$ , where (for the sake of this post) we define an interval $I$ in $A$ to be the injective image of a set of successive integers under reduction modulo $m$ . An interval is “short” if its length is significantly smaller than $m$ , in the sense that $|I|=m^{\theta}$ for some real parameter with $0\leq \theta<1$ . We are then looking for non-trivial estimates for
$\sum_{x\in I}\varphi(x)$
where $\varphi\,:\, A\rightarrow \mathbf{C}$
is some complex-valued function, which is supposed to oscillate in such a way that we expect that
$\sum_{x\in I}\varphi(x)=o(|I|\|\varphi\|_{\infty}).$

There is a fundamental technique to attack this problem, which is of constant use in analytic number theory, and which is known as the completion method. Abstractly, one can see it as a case of the Plancherel formula in (discrete) Fourier analysis, namely, one writes
$\sum_{x\in I}\varphi(x)=\sum_{t\in A}\hat{\varphi}(t)\hat{I}(t),$
where
$\hat{\varphi}(t)=\frac{1}{\sqrt{m}}\sum_{x\in A}\varphi(x)e\Bigl(\frac{tx}{m}\Bigr),$
and $\hat{I}$ is the same transform applied to the characteristic function of the interval $I$ . One then deduces the bound
$\sum_{x\in I}\varphi(x)\ll \|\hat{\varphi}\|_{\infty}\sqrt{m}(\log m),$
where the implied constant is absolute, simply by estimating the $L^1$ -norm of $\hat{I}$ — in our normalization, this is $\ll \sqrt{m}(\log m)$ .

In many cases, the Fourier transform of $\varphi$ can be estimated quite well, and in particular, in the context of finite fields $A=\mathbf{F}_p$ , if $\varphi$ is a trace function which is not proportional to an additive character $e(x/p)$ , Deligne’s Riemann Hypothesis gives
$\|\hat{\varphi}\|_{\infty}\ll 1,$
where the implied constant depends only on the conductor of (the sheaf underlying) $\varphi$ .

The resulting estimate
$\sum_{x\in I}\varphi(x)\ll \sqrt{m}(\log m)$
is known as the general Polya-Vinogradov bound (although the name is sometimes restricted to the case where $\varphi=\chi$ is a Dirichlet character modulo $m$ .)

This is quite an efficient result: it gives non-trivial estimates for all intervals $I$ such that $p/(\log p)=o(|I|)$ (or even $|I|=c\sqrt{p}(\log p)$ , for a suitable $c>0$ , if one only desires some cancellation by a multiplicative constant, and not that the sum be of smaller order of magnitude.) With this generality, it is also almost best possible: if we take $\varphi(x)=e(x^2/p)$ , then the sum over $1\leq x\leq \sqrt{p}$ has essentially no cancellation (the phase does not have enough time to turn around sufficiently.)

It seems natural, then, to ask: is the Polya-Vinogradov range (where $I$ is a bit larger than $\sqrt{p}(\log p)$ ) best possible? Does the gap between $\sqrt{p}$ and $\sqrt{p}(\log p)$ really represent a different behavior for such generalized exponential sums?

Our paper answers this question quite satisfactorily: there is, in fact, no gap, in the sense that for trace functions (not proportional to an additive character), one can get cancellation in sums over intervals of length $\sqrt{p}\beta(p)$ for any function $\beta(p)$ tending to infinity with $p$ (assuming we do tend to infinity while keeping the conductor bounded.)

As a direct corollary, we get for instance the equidistribution in $[0,1]$ (with respect to Lebesgue measure) of fractional parts $\{\frac{f(n)}{p}\}$ for $1\leq n\leq \sqrt{p}\beta(p)$ , for any fixed polynomial $f\in \mathbf{Z}[X]$ of degree $\geq 2$ , and the equidistribution with respect to the Sato-Tate measure of the angles of Kloosterman sums $\theta_p(x)$ such that
$\frac{1}{\sqrt{p}}\sum_{y\in\mathbf{F}_p^{\times}}e\Bigl(\frac{xy+y^{-1}}{p}\Bigr)=2\cos\theta_p(x),$
again for $1\leq x\leq \sqrt{p}\beta(p)$ , whenever $\beta(p)\rightarrow +\infty$ . (This last result had been proved in the Polya-Vinogradov regime by Philippe a while ago, and in the full range $1\leq x\leq p-1$ , it is a celebrated result of Katz.)

As I mentioned, the basic method is very easy, and we call it the “sliding sum method”. It is reminiscent of the van der Corput inequality, and we wouldn’t be surprised to learn that it had already been established by other people. (The applicability to trace functions, on the other hand, requires some rather deep results, as I will discuss below.)

I will give the simplest variant. Consider an interval $I$ in $A=\mathbf{Z}/m\mathbf{Z}$ . We assume that $|I|=\sqrt{m}\beta$ with $\beta=\beta(I)\geq 1$ (so we are certainly above the square-root length). We then compare upper and lower bounds for the average
$\Sigma=\sum_{a\in A}{\Bigl|\sum_{x\in I}{\varphi(x+a)}\Bigr|^2}.$

For the upper-bound, we expand the square and exchange the order of summation, obtaining
$\Sigma=\sum_{x,y\in I}C(\varphi;x-y)$
where
$C(\varphi,t)=\sum_{a\in A}\varphi(a)\overline{\varphi(a+t)}$
is an additive correlation sum of $\varphi$ (it is a special case of those correlation sums we have considered extensively in our first works.)

We assume that $\varphi$ has the property that, if $t$ is not in a set containing at most $c$ values, we have
$|C(\varphi,t)|\leq c \sqrt{m}$
(i.e., the correlation exhibits uniform square-root cancellation, except for a few exceptional cases, among which of course we expect to have $t=0$ ). Then, using the trivial bound
$|C(\varphi,t)|\leq \|\varphi\|_{\infty}^2m$
for the exceptional values of $t=x-y$ , we get
$\Sigma\ll m|I|+m^{1/2}|I|^2\ll m^{1/2}|I|^{1/2},$
where the implied constant depends on the parameter $c$ that we just introduced, and on the $L^{\infty}$ -norm of $\varphi$ (and we use the fact that $|I|\geq \sqrt{m}$ .)

As for the lower bound, we just use the fact that if we shift $I$ by a small amount, the sum over $a+I$ does not change too much (because the interval and its shift overlap significantly; intuitively, we slide the sum over a certain range, hence our name for the method):
$\Bigl|\sum_{x\in I}\varphi(x)-\sum_{x\in I}\varphi(x+a)\Bigr|\leq 2|a|\|\varphi\|_{\infty}.$

This means that if we consider the sums shifted by $a$ of size up to (roughly) the sum
$S=\sum_{x\in I}\varphi(x)$
itself, these will have a contribution to $\Sigma$ of size roughly $\gg |S|^3.$ So by comparing the upper and lower bounds (using positivity), we get
$|S|^3\ll m^{1/2}|I|^2,$
or, in terms of the parameter $\beta\geq 1$ , we get
$S\ll |I|^{2/3}m^{1/6}=|I|\beta^{-1/3}$
(where the implied constant depends on $c$ and on $\|\varphi\|_{\infty}$ ).

Hence, provided we work with functions with bounded $L^{\infty}$ -norm and with uniformly small correlations in the sense we described, then we can get cancellation as long as $\beta(I)\rightarrow +\infty$ , but arbitrarily slowly.

This is elementary, but now the really significant part is that if $\varphi$ is a trace function modulo $m=p$ , and if it is associated to an irreducible sheaf, and is not proportional to an additive character, then it does have the desired properties, the parameter $c$ being bounded in terms of the conductor $c(\varphi)$ of $\varphi$ (which also satisfies $\|\varphi\|_{\infty}\leq c(\varphi)$ , so that it serves as a universal complexity parameter, as it did in our previous works.)

We do not need to fight very hard to prove this in our new paper, but this is because we can quote and use various lemmas from the previous ones, and — as usual — rely on Deligne’s fundamental version of the Riemann Hypothesis over finite fields; the result itself is undoubtedly quite deep when applied to trace functions which are not of rank $1$ .

As a last remark: the method is robust, and we adapt it for instance to sums over proper generalized arithmetic progressions, which are natural generalizations of intervals. Here we get bounds of quality depending also on the dimension of the progression (the saving $\beta^{-1/3}$ is replaced by $\beta^{-1/(k+2)}$ for a $k$ -dimensional progression), but the result is appealing even for large $k$ because the Polya-Vinogradov gap is
$\sqrt{m}\leq |B|\leq \sqrt{m}(\log m)^k$
for a $k$ -dimensional progression $B\subset \mathbf{Z}/m\mathbf{Z}$ , hence its size also increases with $k$ (this follows from a recent result of X. Shao bounding the $L^1$ -norm of the Fourier transform of the characteristic function of $B$ .)

One thought on “Sliding over the Polya-Vinogradov gap”

math stat says:

24.08.2014 at 16:38

1. Are there any Polya-Vinogradov type and Paley type results for character sum over arbitrary subset A of Fp?

For example, a Plaley type result such as

Sum_{a in A} X(a) > (#A)^{1/2}

for infinitely many primes p?

2. For random subset R of Fp?

Thank you.

Comments are closed.

Sliding over the Polya-Vinogradov gap

Published by

Kowalski

One thought on “Sliding over the Polya-Vinogradov gap”