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