Is Weil's bound for Kloosterman sums ever attained?

Question

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.

Answer 1

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?).

Answer 2

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$.

Answer 3

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$

Answer 4

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.)

Answer 5

Not an answer, but:

A closely related question is considered by Bombieri and Katz here:

Bombieri, Enrico(1-IASP-SM); Katz, Nicholas M.(1-PRIN) A note on lower bounds for Frobenius traces. Enseign. Math. (2) 56 (2010), no. 3-4, 203–227. 11G20 (11J87 14G15)

Their result is not quite strong enough to answer the OP's question, but the paper is certainly enlightening.