# Is Weil's bound for Kloosterman sums ever attained?

Weil's bound for Kloosterman sums states that for $(a,b)\not=(0,0)$, $$|K(a,b;q)|:=\left|\sum_{x\in\mathbb{F}_q^*}\chi(ax+bx^{-1})\right|\leq 2\sqrt{q},$$ where $\chi$ is a non-trivial additive character on $\mathbb{F}_q$ (the field with $q$ elements).

My question is, is it known to be false that $\sqrt{q}$ can be replaced by $\sqrt{q-1}$?

Here's what is known (to me):

• Weil's bound follows from the fact that $K(a,b;q)=\alpha+\beta$ where $\alpha\beta =q$ and $|\alpha|=|\beta|=\sqrt q$.
• Thus there is a unique angle $\theta(a,b;q)$ in $[0,\pi]$ such that $$\frac{K(a,b;q)}{2\sqrt q}=\cos\theta(a,b;q)$$
• My question then asks, is there $a,b,q$ such that $$|\cos\theta(a,b;q)|>\sqrt{1-\frac 1q}?\qquad (*)$$
• "Vertical" equidistribution of Kloosterman angles implies that as $q\to\infty$ $$\frac 1{q-1}\sum_{\lambda\in F_q^*}f(\theta(1,\lambda;q))\to\frac 2\pi\int_0^\pi f(\theta)\sin^2\theta\,d\theta$$
• Thus for any fixed $\delta>0$, as $q\to\infty$ the proportion of angles $\theta(a,b;q)\in [0,\delta]$ approaches $\frac 1\pi (\delta-\frac 12\sin(2\delta))\approx \frac{2\delta^3}{3\pi}$.
• $(*)$ is roughly equivalent to $|\theta(a,b;q)|<q^{-1/2}$, so by equidistribution the expected number of such angles is $\approx 2(q-1)\frac{2}{3\pi} q^{-3/2}\approx \frac{4}{3\pi} q^{-1/2}$, which is (much) less than 1.

So one might ask how good is the concentration around the expected number of angles? And how good is this approximation of the expectation to begin with?

Probably the most reasonable approach is to just search by computer. For $q=p$ prime and $p\leq 61$ there are no counterexamples, but this isn't very convincing.

-
I note that if you consider Kloosterman sums over $\Bbb Z/q\Bbb Z$ rather than $\Bbb F_q$, then the bound $2\sqrt{q-1}$ is in fact invalid. Consider the result of Salie (last bullet point in en.wikipedia.org/wiki/… ) with say $a=b=(q-1)/2$. – Greg Martin May 16 '14 at 1:53
From Katz's theorem on equidistribution and some Fourier analysis I think one can show that for every prime large $p$ there exists a Kloosterman sum with $|K(1,a;p)| \ge 2\sqrt{p} - C p^{\frac 14}$ for some constant $C$. This is weaker than what you want of course, but at least gives some quantitative result near the Weil bound. If something like this of interest to you, I can sketch the argument sometime (or somebody else here can). Interestingly for say Fourier coefficients of a modular form I don't see how one can get nearly so close to the Deligne bounds. – Lucia May 16 '14 at 2:56
Are you sure about the factor $\frac1{12\pi}$ in the formula $(q-1)\,/\,(12\pi q^{-3/2})$? For large $q$ I get about $\frac{4}{3\pi} q^{-3/2}$ for the fraction of the unit disc $x^2+y^2 \leq 1$ in which $|x| > (1-\frac1q)^{-1/2}$. – Noam D. Elkies May 16 '14 at 5:31
It seems to me that your final bullet point in fact predicts an infinitude of q's for which the conjecture fails, since $\sum_q \frac{4}{3\pi} q^{-1/2}$ diverges. – Terry Tao May 16 '14 at 15:51
If you consider Kloosterman sums twisted by a nontrivial multiplicative character then equality can be achieved. See my comment to Noam's answer. – KConrad May 16 '14 at 22:45

Going a bit beyond $61$, I find that the first counterexample to $|K(a,b;q)| < 2 \sqrt{q-1}$ with prime $q$ has $(q,ab) = (139,38)$, when $K(a,b;q) = -23.51308393\ldots = -2 \sqrt{138.216\ldots}\,$, and there are no further prime counterexamples up to $10^3$.

[added later] Extending the search overnight reached a bit beyond $10^4$ and found five more cases, at $q=1747$, $3121$, $3593$, $3853$, and $10973$. The smallest $\delta$ for $|K(a,b;q)| = 2\sqrt{q-\delta}$ is about $0.2892$ for $(q, ab) = (1747, 461)$. The other $\delta$'s are about $0.653$, $0.830$, $0.833$, and $0.2999$, the last for $(q,ab) = (10973, 8093)$.

The gp code I ran is about an order of magnitude faster than yesterday's, mostly thanks to storing a table of cosines instead of computing each $\chi(ax+bx^{-1})$ as it arises. But it still takes about $q^2$ time per $q$, and thus about $x^3$ to try all $q \leq x$. There's a factor of about $q$ (and thus of about $x$) to be saved by setting up the computation as a fast Fourier transform over either ${\bf F}_q$ or ${\bf F}_q^*$, but I'll leave that to somebody else to implement (or has it been done already?).

-

This is a supplement to Noam Elkies' answer. I claim that the Weil bound is never attained for $q=p$ prime. Assume that the bound is attained, then $K(a,b,p)=\pm 2\sqrt{p}$, so $\sqrt{p}$ lies in the cyclotomic field $\mathbb{Q}(\zeta_p)$. Then $\mathbb{Q}(\sqrt{p})$ is a subfield of $\mathbb{Q}(\zeta_p)$, so $2$ is unramified in $\mathbb{Q}(\sqrt{p})$, so $p\equiv 1\pmod{4}$. Then, using Gauss sums and the notation $e_p(t):=e^{2\pi it/p}$, we can write the equation $K(a,b,p)=\pm 2\sqrt{p}$ as $$\sum_{x=1}^{p-1}e_p(ax+b\overline{x}) = \pm 2\sum_{t=1}^{p-1}\left(\frac{t}{p}\right)e_p(t).$$ For a given $t$, the number of solutions of $ax+b\overline{x}=t$ equals $1+\left(\frac{t^2-4ab}{p}\right)$, hence we have $$\sum_{t=0}^{p-1}\left(\frac{t^2-4ab}{p}\right)e_p(t) = \pm 2\sum_{t=1}^{p-1}\left(\frac{t}{p}\right)e_p(t).$$ Eliminating the term $t=0$ from the left hand side, $$\sum_{t=1}^{p-1}\left(\left(\frac{t^2-4ab}{p}\right)-\left(\frac{-4ab}{p}\right)\right)e_p(t) = \pm 2\sum_{t=1}^{p-1}\left(\frac{t}{p}\right)e_p(t).$$ The complex numbers $e_p(t)$ occurring on both sides are linearly independent over $\mathbb{Q}$, hence we conclude, with a constant sign $\pm$, $$\left(\frac{t^2-4ab}{p}\right)-\left(\frac{-4ab}{p}\right)=\pm 2\left(\frac{t}{p}\right),\qquad 1\leq t\leq p-1.$$ This is a contradiction, because the right hand side changes by $4$ at several values of $t$, while the left hand side always changes by at most $2$.

-

Here's a simple proof that $|K(a,b;q)|$ can never exactly equal $2\sqrt q$ for any prime power $q=p^f$ and any $a,b \in {\bf F}_q^*$.

Recall that $K := K(a,b;q) \in {\bf R}$, because in the defining sum $\sum_{x \in {\bf F}_q^*} \chi(ax+bx^{-1})$ the contributions of $x$ and $-x$ to the imaginary part of $K$ are equal and opposite. Therefore if $|K| = 2 \sqrt q$ then $K = \pm 2 \sqrt q$. In particular $K$ would be contained in the prime ideal $\pi = (1-\zeta_p)$ above $p$ in the cyclotomic field ${\bf Q}(\zeta_p)$. [In fact this would have to be true even if we did not know that $K$ is real, because $(p) = \pi^{p-1}$.]

But $K$ is a sum of $q-1$ roots of unity of order $p$, each congruent to $1 \bmod \pi$. Hence $K \equiv q-1 \equiv -1 \bmod \pi$. Therefore $K \notin \pi$. $\ \diamondsuit$

-
Two nice proofs by @GHfromMO and Noam Elkies. How about this third one liner inspired by both your proofs? (I stick to $q$ prime.) Here goes: The $p$-th power of the quadratic Gauss sum is $0\pmod p$, while the $p$-th power of the Kloosterman sum is $-1 \pmod p$; therefore the Kloosterman sum is not an algebraic integer multiple of the Gauss sum. – Lucia May 16 '14 at 18:52
Noam's proof is the same one I gave in the paper "On Weil's proof of the bound for Kloosterman sums", J. Number Theory 97 (2002), 439--446. See the line after the proof of Theorem 3. If we twist the Kloosterman sum with a nontrivial multiplicative character then its absolute value is still bounded above by $2\sqrt{q}$, but now equality can be achieved. For example, set $q = 81$, $a = -1$, and $b = 1$, and twist the sum by a character on ${\mathbf F}_q^\times$ of order 4. The sum is $18 = 2\sqrt{q}$. I learned this example from Timothy Choi. See p. 445 of the paper for another example. – KConrad May 16 '14 at 22:34
Very nice, including the comments by Lucia and KConrad! – GH from MO May 18 '14 at 20:15

This is an interesting paper but in a different direction. As far as I can see, they fix $a$, and vary $q$ over powers of a prime. More relevant to the original question is Katz's work on the equidistribution of angles of Kloosterman sums, which can be made into a quantitative bound, as pointed out in my comment above. – Lucia May 16 '14 at 20:52
Part of the question asked about how good the concentration of Kloosterman angles is around the expected measure. It turns out that the discrepancy in the problem of vertical distribution" of Kloosterman angles was worked out by Niederreiter: The distribution of values of Kloosterman sums in Arch. der Math. (1991) pages 270--277. The proof is based on Erdos-Turan type Fourier analysis together with Katz's theorem on equidistribution (essentially what I had in mind in my comment to the question above, but of course carried out 25 years back!). From Niederreiter's bound on the discrepancy one immediately gets that there are Kloosterman sums $K(1,a;p)$ for each large prime $p$ which are larger than $2\sqrt{p} - C p^{\frac 13}$ for some constant $C$. One can improve this a little bit and replace $Cp^{\frac 13}$ by $Cp^{\frac 14}$ by working through the argument more carefully in this special situation. (The vanishing of the measure at $0$ makes the general discrepancy bound a little weaker in this situation.)