How fast can we numerically calculate Kloosterman sums?

Define the usual Kloosterman sum by $$S(m,n;c) = \sum_{\substack{x \pmod{c} \\ (x,c) = 1}} e\Big(\frac{mx + n\overline{x}}{c}\Big),$$ where $x \overline{x} \equiv 1 \pmod{c}$, and $e(x) = e^{2 \pi i x}$. I'm interested in knowing if there is a faster way to calculate values of this rather than just adding up the $\varphi(c) \leq c$ values of the sum. By calculate here, I just mean to find a good numerical approximation; the definition already gives an exact expression for it as an element of $\mathbb{Z}[e^{2\pi i/c}]$ which probably can't be improved by much in general. I'm interested in $m$ and $n$ fixed, and how fast it can be computed in terms of $c$. The case $c=$prime is probably the most interesting. I'd also be interested to know if people have considered the speed of evaluation of the full list of values of $S(m,n;c)$ for $c \leq C$.

For the case of a Gauss sum to modulus $q$, I have heard that it is "well-known" how to calculate it in around $\sqrt{q}$ steps as follows. The main point is to use the fact that the completed Dirichlet $L$-function has the approximate functional equation (See Theorem 5.3 of Iwaniec and Kowalski's book) $$L(1/2, \chi) = \sum_{n} \frac{\chi(n)}{\sqrt{n}} V(\frac{n}{X \sqrt{q}}) + \epsilon(\chi) \sum_{n} \frac{\overline{\chi}(n)}{\sqrt{n}} V(nX/\sqrt{q}).$$ Here $V$ is a special function that in practice can be calculated (e.g. in Mike Rubinstein's Lcalc package), $\epsilon(\chi) = i^{-a} \tau(\chi) q^{-1/2}$ where $a$ is $0$ or $1$ if $\chi$ is even or odd, $\tau(\chi)$ is the Gauss sum, and $X> 0$ is a parameter to choose. Write this in the form $L(1/2, \chi) = A(X) + \epsilon(\chi)B(X)$. Taking say $X=1$ and another value of $X$ close to $1$ will give different values for $A(X)$ and $B(X)$, and so one can solve for $\epsilon(\chi)$. The function $V(x)$ has rapid decay for $x \gg 1$, so it takes around $\sqrt{q}$ terms in the sum to evaluate $A(X)$ and $B(X)$, far fewer than the full $q$ terms needed to evaluate the Gauss sum by definition.

• Is there a reciprocity theorem for Kloosterman sums (as there is for Dedekind sums)? – Gerry Myerson Sep 13 '13 at 0:24
• No, there aren't any formulas that relate $S(m,n;p)$ to another Kloosterman sum of smaller modulus. – Matt Young Sep 13 '13 at 1:37
• In the case of Dedekind sums, a fast way to compute $\sum_k e^{ \pi i \left[ s(c,\, k) \;-\; \frac{1}{k} 2 nc \right] }$ using the prime factorization of $c$ is given in Whiteman, "A sum connected with the series for the partition function", Pacific J. Math., vol 6, no 1 (1956), 159-176. – Fredrik Johansson Sep 15 '13 at 10:17

This is not quite an answer to your interesting question, but rather a couple of related comments. First your nice "well known" observation on the Gauss sum can perhaps be expressed more simply by noting that if $\chi(-1)=1$ then Poisson summation gives $$\tau(\overline{\chi}) \sum_{-\infty}^{\infty} \chi(n) e^{-\pi n^2/q} = \sqrt{q} \sum_{-\infty}^{\infty} \overline{\chi}(n) e^{-\pi n^2/q},$$ so that about $\sqrt{q}$ terms are needed to approximate $\tau(\chi)$. A similar argument of course holds if $\chi(-1)=-1$, and in any case this is closely related to what you wrote.