4
$\begingroup$

I have the following problem. Let $p$ be some prime. What is the value of \begin{equation} \sum_{k=1}^{p-1} \left(\frac{k+1}{p}\right) \omega_p^{kl}, \end{equation} where $\left(\frac{k+1}{p}\right)$ is the Legendre symbol, and $\omega_p = e^{\frac{2\pi i}{p}}.$ [solved].

But what is the value of \begin{equation} \sum_{k=1}^{p-1} \left(\frac{k^2+k}{p}\right) \omega_p^{kl}? \end{equation}

I found the standard result for $\left(\frac{k}{p}\right)$, $\sqrt{p}$ or $i\sqrt{p},$ but I don't know the proof techniques and therefore don't know how to approach this one. Any ideas? I am not specialist in number theory, and I don't even know if it is easy or hard question :)

Any hints or links to references are welcomed.

What I actually need is the value (or a lower bound of the absolute value) of a Gauss sum with $\chi(k) = (\left(\frac{k}{p}\right)+1)(\left(\frac{k+1}{p}\right)+1).$

Improve this question
$\endgroup$
18
  • 5
    $\begingroup$ The missing term at $k = 0$ is $1$, so your sum is $\sum_{k \in \mathbf Z/(p)} (\frac{k+1}{p})\omega_p^{kl} - 1$. Now you're summing over an additive group, so replacing $k$ with $k-1$ makes it $\sum_{k \in \mathbf Z/(p)} (\frac{k}{p})\omega_p^{(k-1)l} - 1 = \omega_p^{-l}\sum_{k \in \mathbf Z/(p)} (\frac{k}{p})\omega_p^{kl} - 1$, and omitting the $k=0$ term (which is $0$) and then doing a multiplicative change of variable you get $\omega_p^{-l}(\frac{l}{p})\sum_{k \not\equiv 0 \bmod p} (\frac{k}{p})\omega_p^k - 1$. This last sum is a standard Gauss sum of the Legendre symbol. $\endgroup$
    – KConrad
    Commented May 16, 2015 at 20:27
  • 3
    $\begingroup$ @Liss, first of all you are right that $(\frac{l}{p})^{-1}$ comes out, but the character is quadratic so the exponent doesn't matter: $a^{-1} = a$ if $a = \pm 1$. Concerning a sum with $(\frac{k^2+k}{p}) = (\frac{k(k+1)}{p})$ in it, replacing $k$ with $-k$ makes that $(\frac{-1}{p})(\frac{k(1-k)}{p})$ and then you basically have a Jacobi sum, which you can look up elsewhere. This is not really a research-level question. I suggest if you have similar questions that you ask them on math.stackexchange. $\endgroup$
    – KConrad
    Commented May 16, 2015 at 21:09
  • 2
    $\begingroup$ Are you trying to count how often consecutive numbers $k$ and $k+1$ in $\mathbf Z/(p)$ are perfect squares? $\endgroup$
    – KConrad
    Commented May 16, 2015 at 22:30
  • 3
    $\begingroup$ Whoops, my previous comment on Jacobi sums was incorrect since the sum is not just $\sum_{k \in \mathbf Z/(p)} (\frac{k(k+1)}{p})$ but has the factor $\omega_p^{kl}$ in there too. Replacing $k$ with $k/l$ makes the sum $\sum_{k \in \mathbf Z/(p)} (\frac{k(k+l)}{p})\omega_p^k$. I agree with Will that it is hopeless to expect an exact formula for this but it gets a bound like $2\sqrt{p}$ from the Weil conjectures. $\endgroup$
    – KConrad
    Commented May 17, 2015 at 0:06
  • 2
    $\begingroup$ @Liss It's an upper bound on the absolute value. For a reference you can go back to Weil: "On Some Exponential Sums". Example 1 after equation (5) on the bottom of page 206 is the bound, where $\mathfrak d=\{0,-1\}$ so $R_{\mathfrak d}(t) = t(t+1)$, $\chi$ is the quadratic character, and $\psi(x) = \omega_p^{lx}$. $\endgroup$
    – Will Sawin
    Commented May 17, 2015 at 18:06

2 Answers 2

Reset to default
6
$\begingroup$

We may assume that $l\not\equiv 0\pmod p$ because otherwise the given sum is simple. The answer is a Kloosterman sum.

Let $$\delta_q(x)=\begin{cases} 1,& \text{if } x\equiv 0\pmod{q};\\ 0,& \text{if } x\not\equiv 0\pmod{q}.\\ \end{cases}$$ Then \begin{gather*} S(l)=\sum\limits_{k=1}^{p}\left(\dfrac{k(k+1)}{p}\right)e\left(\dfrac{kl}{p}\right)=\\= \sum\limits_{k=1}^{p}\left(\sum\limits_{y=1}^{p}\delta_p(k(k+1)-y^2)-1\right)e\left(\dfrac{kl}{p}\right)=\\= \sum\limits_{k,y=1}^{p}\delta_p(k(k+1)-y^2)e\left(\dfrac{kl}{p}\right)=[k=x+y]=\\= \sum\limits_{x,y=1}^{p}\delta_p(x^2+2xy+x+y)e\left(\dfrac{(x+y)l}{p}\right). \end{gather*} For each non-zero summand $y=\dfrac{x^2+x}{2x+1}$. Hence \begin{gather*} S(l)= \sum\limits_{\substack{1\leq x\leq p\\x\neq (p-1)/2}}e\left(\dfrac{l}{p}\cdot\left(\dfrac{x^2+x}{2x+1}+x\right)\right)=[t=2x+1]=\\= \sum\limits_{t=1}^{p-1}e\left(\dfrac{l}{p}\cdot\left(\dfrac{3t}{4}-\dfrac{1}{4t}-\dfrac{1}{2}\right)\right), \end{gather*} where the expression $\dfrac{3t}{4}-\dfrac{1}{4t}-\dfrac{1}{2}$ is understood modulo $p$.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thank you for a different insight! I didn't follow all the details, but in any case, this calculations gives us only a reformulation of the problem, and not a solution that I can use for my research.. - Do you have an idea, if such sums can be bounded from below by something away from 0? $\endgroup$
    – Liss
    Commented May 18, 2015 at 12:51
  • 1
    $\begingroup$ I think it is impossible. For $p$ an odd prime, there are no known simple formula for $K(a, b; p)$, and the Sato–Tate conjecture suggests that none exist, see arxiv.org/abs/1111.5455v2 . $\endgroup$
    – Alexey Ustinov
    Commented May 18, 2015 at 13:08
  • $\begingroup$ @Liss What kind of lower bound do you need? (For all $p$, or for infinitely many $p$?) $\endgroup$
    – Alexey Ustinov
    Commented May 19, 2015 at 5:58
  • $\begingroup$ It would be nice to have any bound I can get, only that it doesn't go to zero as $p$ goes to infinity. The main point is to show that it is "safe" to divide by this value in a algorithm for signal processing which I have.. That's why an answer like $4p^{(2-p)/2}$ will not solve my problem. I can test numerically how those sums behave for small $p$, and they vary, but they are larger than at least $0.02$ or so.. $\endgroup$
    – Liss
    Commented May 19, 2015 at 20:44
  • $\begingroup$ @Liss, if all you test is a finite set of primes $p$, especially what you call "small" $p$, then of course you'll find a positive lower bound on them. But is there any reason to expect over all $p$ that the sums don't include values that get arbitrarily small? When you're dealing with a family of exponential sums (in your case, varying over all primes), even if individually they are never $0$ it doesn't mean particular values couldn't get arbitrarily close to $0$. $\endgroup$
    – KConrad
    Commented May 19, 2015 at 21:25
3
$\begingroup$

In the ring $\mathbb{Z}[\omega_p]$, the OP's second sum $\sum_{k=1}^{p-1} \left(\frac{k^2+k}{p}\right) \omega_p^{kl}$ raised to the $p$-th power is congruent to $\sum_{k=1}^{p-2} \left(\frac{k^2+k}{p}\right)$ modulo $p$. This new sum consists of $p-2$ terms, each equal to $\pm 1$, hence it is invertible modulo $p$ in $\mathbb{Z}$ (hence also in $\mathbb{Z}[\omega_p]$) when $p>2$. We conclude that the OP's second sum is a nonzero element of $\mathbb{Z}[\omega_p]$, which can be turned into an exponential lower bound, and perhaps even a better one (see here for a related discussion).

P.S. This argument was inspired by Alexey Ustinov's response to the OP's question and Noam Elkies's response here, more precisely by Lucia's comment to Noam Elkies's response.

Added 1. As Alexey Ustinov remarked below, $\sum_{k=1}^{p-2} \left(\frac{k^2+k}{p}\right)=-1$. In fact this follows from his response to the OP's question by setting $l=0$ there and making the obvious modifications.

Added 2. Here is a slight variation of the above argument. The sums $\sum_{k=1}^{p-1} \left(\frac{k^2+k}{p}\right) \omega_p^{kl}$ for $1\leq l\leq p-1$ are Galois conjugates in the cyclotomic field $\mathbb{Q}(\omega_p)$, while their sum equals $$ \sum_{l=1}^{p-1}\sum_{k=1}^{p-1} \left(\frac{k^2+k}{p}\right) \omega_p^{kl}=-\sum_{k=1}^{p-2} \left(\frac{k^2+k}{p}\right)=1.$$ Hence all the sums $\sum_{k=1}^{p-1} \left(\frac{k^2+k}{p}\right) \omega_p^{kl}$ for $1\leq l\leq p-1$ are nonzero. Moreover, their product is a nonzero rational integer, which also implies (by bounding the relevant Kloosterman sums from above) that each of them has length $$ \left| \sum_{k=1}^{p-1} \left(\frac{k^2+k}{p}\right) \omega_p^{kl}\right|>(4p)^{(2-p)/2}.$$

Improve this answer
$\endgroup$
7
  • $\begingroup$ Isn't Elkies's answer about ruling out the maximal size $2\sqrt{p}$ for Kloosterman sums, rather than zero? $\endgroup$
    – Lucia
    Commented May 19, 2015 at 3:07
  • 1
    $\begingroup$ Yes indeed! I forgot about my comment! $\endgroup$
    – Lucia
    Commented May 19, 2015 at 3:41
  • 1
    $\begingroup$ $$\sum_{x=1}^p \biggl(\frac{(x-a)(x-b)}{p}\biggr)=p\delta_p(a-b)-1.$$ $\endgroup$
    – Alexey Ustinov
    Commented May 19, 2015 at 3:46
  • 1
    $\begingroup$ thank you, @GHfromMO, this is also interesting approach to know. I already have found similar bound in the work of Konyagin, S.V. and Lev, V.F. (2000) "On the distribution of exponential sums". Theorem 1 there says that a sum of roots of unity taken over a set of $n$ elements is bounded in absolute value from below by $n^{-(p-3)/4}.$ I can use this result to show that the full sum from the beginning of the question (with the prescribed $\chi(k)$) is bounded by $(\frac{p-3}{4})^{-(p-3)/4}.$ Still, as I wrote in some other comment, I was curious to know if a bound away from zero can be obtained. $\endgroup$
    – Liss
    Commented May 19, 2015 at 21:18
  • 1
    $\begingroup$ @Liss: I am pretty sure your sums are not bounded away from zero, i.e. they can be arbitrary small for large $p$. (I don't have a proof though.) $\endgroup$
    – GH from MO
    Commented May 19, 2015 at 21:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .