4

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

Liss
  • 145
  • 5
    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. – KConrad May 16 '15 at 20:27
  • @KConrad: I suggest you give your comment as a response below, and then this question can be closed. – GH from MO May 16 '15 at 20:47
  • Great, thanks a lot! this was super-easy :) also, instead of $(\frac{l}{p})$ I believe what comes out is $(\frac{l^{-1}}{p})$ – Liss May 16 '15 at 20:50
  • Could we keep the question open for the case $(\frac{k^2+k}{p})$? I could edit the question.. Similar trick I think can not be done in that case.. – Liss May 16 '15 at 20:52
  • 3
    @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. – KConrad May 16 '15 at 21:09
  • Ok, thank you! I understand. I it true I didn't estimate the hardness of the question correctly, I will start with math.stackexchange next time. Thanks a lot for your help and explanations! – Liss May 16 '15 at 21:21
  • 2
    Are you trying to count how often consecutive numbers $k$ and $k+1$ in $\mathbf Z/(p)$ are perfect squares? – KConrad May 16 '15 at 22:30
  • 1
    This is a finite field hypergeometric sum. There is no simple formula, but it's bounded by $2\sqrt{p}$. – Will Sawin May 16 '15 at 23:50
  • 3
    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. – KConrad May 17 '15 at 00:06
  • @WillSawin, thank you. Is that an upper or lower bound? Could you give me some reference?

    KConrad, what I try to do is to find a lower bound for a sum of roots of unity taken over a set $k \in K, k-q \in K,$ for fixed $q,$ where $K$ is a quadratic difference set, i.e. elements of the form $t^2, t \in Z_p^*.$ I need it for an estimate of the coherence of a Gabor system generated by difference sets...

     – Liss May 17 '15 at 17:11
  • 2
    @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}$. – Will Sawin May 17 '15 at 18:06
  • thank you a lot, @KConrad and Will Sawin. It looked like these bounds can be sufficient for what I need, but when all expression taken together (with $\chi(X)$ as in the question posed), I get only $\geq -2\sqrt{p}-2$ which is useless, because I need to show that their absolute values are away from zero. – Liss May 18 '15 at 12:58
  • 1
    Some Kloosterman sums involving a quadratic character are zero. I'm not saying yours might be zero, but if you are looking for some off-the-shelf result that will prove character sums $S$ in some family do not equal $0$ then you will be disappointed. The standard task for exponential sums is to get sharp upper bounds, not lower bounds away from $0$. Saying there is a lower bound that is a negative number is not really the point of these bounds which is to say $|S|$ is less than or equal to some sharp value. – KConrad May 18 '15 at 18:41
  • 1
    Your sum in absolute value is at least $(4p)^{(2-p)/2}$. See my response below. – GH from MO May 19 '15 at 04:02
  • thank you, @KConrad, my interest is coming from signal processing (discrete time-frequency analysis), and it is just very beautiful "coincidence" that I am dealing with quadratic characters and uncommon questions for those sums.. I can prove that this particular type of sums is non-zero, but it would have been nice to show that it is away from zero in absolute value.. – Liss May 19 '15 at 20:59
  • thank you, @GHfromMO, too :) I will comment also below on your response – Liss May 19 '15 at 21:01
  • @WillSawin, maybe this is a trivial question, but the same bound $2\sqrt{p}$ also holds if it was $R(t)=t(t+\ell),$ too? I made a mistake in my question, so I need to have $k(k+l)$, or and $k(k+1)$ is just the case of $l=1,$ in which in the exponent there should be also no $l...$ But I guess the bounds , both lower and upper do not change from this fact? – Liss May 28 '15 at 14:49
  • 1
    @Liss Yes, the same bound from the same proof in both cases. In fact it's the same sum- to see this, multiply the variable by $l$, and you get an $l^2$ in the exponent. – Will Sawin May 28 '15 at 16:45

2 Answers2

6

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

GH from MO
  • 98,751
Alexey Ustinov
  • 11,875
  • 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? – Liss May 18 '15 at 12:51
  • 1
    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 http://arxiv.org/abs/1111.5455v2 . – Alexey Ustinov May 18 '15 at 13:08
  • @Liss What kind of lower bound do you need? (For all $p$, or for infinitely many $p$?) – Alexey Ustinov May 19 '15 at 05:58
  • 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.. – Liss May 19 '15 at 20:44
  • @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$. – KConrad May 19 '15 at 21:25
  • @KConrad, it is true, there is no reason to believe that over all $p$ the sums will bounded away from zero.. I was basically trying my luck :). But actually, after I found the bound $n^{-(p-3)/4}$ which is true for any subset of dimension $n,$ I thought that maybe the fact that I have a structured set (coming from quadratic difference sets) could give me a better estimate, so I posed this question.. But apparently this structure is also already investigated via the Kloosterman sums, and there is not much hope for better bound. – Liss May 19 '15 at 21:54
  • @Liss Will it be enogth if almost all sums (in terms of $l$) will be bounded from below? – Alexey Ustinov May 20 '15 at 02:26
  • @AlexeyUstinov, yes, if I have result that for almost all $l$ the sums are bounded, it would be also nice :) – Liss May 20 '15 at 10:15
3

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

Community
  • 1
GH from MO
  • 98,751
  • Isn't Elkies's answer about ruling out the maximal size $2\sqrt{p}$ for Kloosterman sums, rather than zero? – Lucia May 19 '15 at 03:07
  • @Lucia: I think Elkies proves that the Kloosterman sum is not in the prime ideal $(1-\omega_p)$, which rules out zero. Anyways, I gave a direct argument based on your version of Elkies's proof, please check! (I am too sleepy now.) – GH from MO May 19 '15 at 03:33
  • 1
    Yes indeed! I forgot about my comment! – Lucia May 19 '15 at 03:41
  • 1
    $$\sum_{x=1}^p \biggl(\frac{(x-a)(x-b)}{p}\biggr)=p\delta_p(a-b)-1.$$ – Alexey Ustinov May 19 '15 at 03:46
  • 1
    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. – Liss May 19 '15 at 21:18
  • 1
    @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.) – GH from MO May 19 '15 at 21:24
  • Ok, thank you! I really appreciate your intuition and all the hints. This is not my field, so I was not sure if this was a feasible question. It was worth trying though :), and learning a small bit of the beautiful mathematics behind those questions.. – Liss May 19 '15 at 21:47