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

  • 3
    $\begingroup$ 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? $\endgroup$ – Seva Jul 11 '14 at 17:45
  • $\begingroup$ $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. $\endgroup$ – Farzad Aryan Jul 11 '14 at 20:10
  • $\begingroup$ 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. $\endgroup$ – Seva Jul 11 '14 at 20:15
  • $\begingroup$ 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. $\endgroup$ – Farzad Aryan Jul 11 '14 at 20:40
  • $\begingroup$ Note that $x+x^{-1}=p$ occurs iff $p\equiv 1\pmod{4}$. $\endgroup$ – 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)$

| cite | improve this answer | |
  • $\begingroup$ You forget about $e(a)-1$ in denominator. The error term is $O(\sqrt p\log^2p)$. $\endgroup$ – Alexey Ustinov Jul 12 '14 at 5:15
  • $\begingroup$ 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. $\endgroup$ – Will Sawin Jul 12 '14 at 5:19
  • $\begingroup$ Sorry, this full sum saves a $\log$ indeed. I was accustomed to think about arbitrary lines. $\endgroup$ – Alexey Ustinov Jul 12 '14 at 5:31
  • $\begingroup$ 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)$. $\endgroup$ – GH from MO Jul 12 '14 at 7:16
  • 1
    $\begingroup$ @GHfromMO It is now! $\endgroup$ – 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).

| cite | improve this answer | |
  • $\begingroup$ Noam adn Will, Thank you very much for the Answer. $\endgroup$ – Farzad Aryan Jul 13 '14 at 1:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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