# Incomplete Kloosterman sum

I am interested in an upper bound on the following incomplete Kloosterman sum $$\sum_{\substack{x=1 \\ x+_{_{\bf Z}}x^{-1}>p}}^{p-1}e\left(\frac{x+x^{-1}}{p}\right).$$

Using the Weil's bound it is easy to show that the real part of the sum is bounded by $\sqrt p.$ It is because if $x+x^{-1}>p$ then $(p-x) + (p-x)^{-1}< p.$ Note that $x^{-1} \in \{1, \cdots , p-1\}$ and $xx^{-1} \equiv 1 \text{ mod } p$. And by $+_{_{\bf Z}}$ we mean that the sum in $\bf Z$ not in $\bf Z_p$.

-
The condition $x+x^{-1}>p$ looks rather artificial since it is natural to consider $x$ and $x^{-1}$ as elements of ${\mathbb F}_p$, and so $x+x^{-1}\in{\mathbb F}_p$, too. Could you explain the motivation behind your question? –  Seva Jul 11 '14 at 17:45
$x$ modulo $p$ is a number between $0$ and $p-1$, same for x^{-1}. Therefore sum(in \matcal(Z)) of these two numbers can be bigger or smaller than $p$. I need to restrict the sum to those $x$ modulo $p$ for which $x+x^{-1}>p$ and find an upper bound. –  Farzad Aryan Jul 11 '14 at 20:10
I understand, but this interpretation does not look very natural to me; and so, I would be interested to learn where this problem came from. –  Seva Jul 11 '14 at 20:15
I edited the question a bit, I hope it is more clear now. I am interested in the distribution of these residues $x$ (such that $x+_{_{\bf Z}}x^{-1}>p$). So this incomplete Kloosterman sum would help understanding the distribution. –  Farzad Aryan Jul 11 '14 at 20:40
Note that $x+x^{-1}=p$ occurs iff $p\equiv 1\pmod{4}$. –  GH from MO Jul 11 '14 at 20:51

We can estimate this using the Polya-Vinagradov method. We get a main term, which comes from the fact that two elements of $\mathbb F_p$ that sum to something greater than $p$ are more likely to sum to something a little bit greater than $p$ than a lot, and an error term. The formula is:

$$\frac{ i p}{2\pi} + O( \sqrt{p}\log{p} )$$

View the sum as a sum of the product of two characteristic functions and an exponential funcion:

$$\sum_{x,y\in \mathbb F_p}\mathbf 1_{\{xy=1\} } e(x+y) \mathbf 1_{\{x+y>p\}}$$

Let $f(a,b)$ be the Fourier transform of $\mathbf 1_{\{xy=1\} }$. Let $g(a,b)$ be the Fourier transform of $\mathbf 1_{\{x+y>p\}}$. Then by Plancherel's formula, this sum is:

$$\frac{\sum_{a,b\in \mathbb F_p} f(a+1,b+1) \overline{g} ( a,b)}{p^2}$$

This sum, it turns out, is easier to estimate. Our first function:

$$f(a,b) = \sum_{x \in \mathbb F_p} e(ax+ bx^{-1} ) = K(ab)$$

is a Kloosterman sum, unless $a=0$ or $b=0$, in which case it is $-1$, unless both $a$ and $b$ are $0$, in which case it is $p-1$. In particular, it is bounded by $2 \sqrt{p}$, unless $a=b=0$, in which case it is $p-1$.

Our second sum we may estimate by more elementary means:

$$g(a,b) = \sum_{0\leq x,y<p, x+y>p} e(ax + by) = \sum_{1\leq x <p} e(ax) \left( \sum_{p+1-x \leq y \leq p-1} e(by) \right) =\sum_{1\leq x <p} e(ax) \frac{ e(bp) - e(b (p+1-x))}{e(b)-1}= \frac{\sum_{1\leq x< p} e(ax+bp) }{e(b)-1} + \frac{\sum_{1\leq x< p} e((a-b) x+b) }{e(b)-1}$$

The first term depends on whether $a=0$, equaling $\frac{(p-1) e(bp)}{e(b)-1}$ if $a=0$ and $\frac{- e(bp)}{e(b)-1}$ otherwise. The second term depends on whether $a=b$, equaling $\frac{(p-1) e(bp)}{e(b)-1}$ if $a=b$ and $\frac{- e(bp)}{e(b)-1}$ otherwise. The whole equation is wrong if $b=0$, but we can use symmetry to handle that, unless $a=0$ and $b=0$, in which case the sum is obviously $(p-1)(p-2)/2$.

Altogether, the $L_1$-norm of $g$ is $O(p^2 \log p)$. Since each term of $f$ but one is bounded by $2\sqrt{p}$, this gives a contribution of at most $\sqrt{p} \log{p}$. This is the error term.

The leading term comes from $f(0,0)$, which is $p-1$, summing against $\overline{g}(-1,-1)$, which is $- p e(1) / (e(1)-1)=\frac{i p^2}{2 \pi} + O(p)$. This gives a contribution of $ip/2\pi+O(1)$

-
You forget about $e(a)-1$ in denominator. The error term is $O(\sqrt p\log^2p)$. –  Alexey Ustinov Jul 12 '14 at 5:15
I don't think so - my second set of sums is over all $x$ from $1$ to $p$. I'm not using the geometric progression formula. –  Will Sawin Jul 12 '14 at 5:19
Sorry, this full sum saves a $\log$ indeed. I was accustomed to think about arbitrary lines. –  Alexey Ustinov Jul 12 '14 at 5:31
In your third display, $f(a-1,b-1)$ should be $f(a+1,b+1)$. This is because the Fourier transform of $\mathbf 1_{\{xy=1\}}e(x+y)$ equals $f(a+1,b+1)$. –  GH from MO Jul 12 '14 at 7:16
@GHfromMO It is now! –  Will Sawin Jul 13 '14 at 14:04

The key fact here is that the integer pairs $(x,y) \in (0,p)^2$ such that $xy \equiv 1 \bmod p$ are asymptotically equidistributed as $p \rightarrow \infty$. This is a consequence of Weil's 1948 bound $\left|\sum_x e((ax+bx^{-1})/p)\right| \leq 2 \sqrt p$ (any bound $O(p^\theta)$ with $\theta < 1$ would suffice).

It follows that Farzad Aryan's sum is $Cp + o(p)$, where $C$ is the integral of $\exp(2\pi i (x+y))$ over the triangle $\{ (x,y) \in (0,1)^2 \mid x+y > 1 \}$. That integral is elementary, and is not zero; it turns out that $C = i/2\pi$. A more precise estimate using Weil's bound is $$\sum_{x=1}^{p-1} e\Bigl(\frac{x+x^{-1}}{p}\Bigr) = \frac{i}{2\pi} p + O(p^{\frac12 + \epsilon}),$$ and if I did this right then the $p^\epsilon$ factor can be replaced by $\log^2 p$.

(I see that while I was writing this up Will Sawin posted much the same answer, claiming that moreover even $\log^2 p$ has one log factor more than necessary.)

[added later] My online notes on analytic number theory include a short chapter "An application of Kloosterman sums" one of whose exercises outlines an elementary proof that each Kloosterman sums is $O(p^{3/4})$; this is weaker than the Weyl bound, but still sufficient to prove the asymptotic equidistribution of $\{ (x,y) \in (0,p)^2 \mid xy \equiv c \bmod p \}$ for any $c \in ({\bf Z} / p{\bf Z})^*$. See Exercise 5 on page 3 (and also Lemma 1 on page 1 for an estimate that implies the equidistribution result).

-
Noam adn Will, Thank you very much for the Answer. –  Farzad Aryan Jul 13 '14 at 1:28