MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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.

Secondly, one can consider a different related problem: namely rapid algorithms for counting points on curves over finite fields. For elliptic curves there is a rapid algorithm of Schoof which allows this in polynomial time, but for general curves I don't think an algorithm faster than the naive one is known. One survey is Elkies but this is now twenty years old so perhaps much more is known. Schoof's algorithm is useful in computing Kloosterman sums over large finite fields of characteristic two or three: see work of Lisonek and others on this topic

The above is somewhat orthogonal to the problem you have in mind. My only other thought was to try to use divisor function in arithmetic progressions to compute Kloosterman sums, but I did not obtain anything nontrivial.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.