Return to Answer

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

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

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 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 of each other 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 absolute norm is at least $1$, which also implies 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}.$$

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

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.

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 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 of each other 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 absolute norm is at least $1$, which also implies 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}.$$