On Certain Sums with Quadratic Expressions Involving the Legendre Symbol

Ram Krishna Pandey Department of Mathematics

Indian Institute of Technology Roorkee

Roorkee 247667 Haridwar India

       ramkpfma@iitr.ac.in

Anshumaan Parashar

Department of Mechanical and Industrial Engineering

Indian Institute of Technology Roorkee

Roorkee 247667 Haridwar India

   apairs.anshumaan@gmail.com

Abstract

In this paper, we find some identities for sums with quadratic and higher-order expressions involving the Legendre symbol. Some of these identities generalize identities recently obtained by Karaivanov and Vassilev.

1 Introduction

Let a be an integer and p be an odd prime. The well-known Legendre symbol, denoted by (\frac{a}{p}), is defined by

(\frac{a}{p}) := \begin{cases}0, & if p | a; \\ 1, & if a is a quadratic residue modulo p; \\ −1, & if a is a quadratic nonresidue modulo p. \end{cases}

Introduced by Legendre [10], the Legendre symbol is a convenient formalism for discussing quadratic residues. Using the Legendre symbol, we can easily state the classical “quadratic reciprocity law”, which was first formulated by Euler and Legendre. Besides this formulation, Legendre also partially proved the law.

The first complete proof of the law was given by Gauss [3]. Gauss was extremely proud of his proof, and he called it the Theorema Aureum (the golden theorem). In his whole lifetime, Gauss provided a total of eight proofs, out of which only six are published. There are over a hundred proofs of the law now in existence.

An efficient algorithm to compute the Legendre symbol has been discussed by Bach and Shallit [2, Thm. 5.9.3, p. 113]. There are several generalizations of the Legendre symbol now in the literature. The Jacobi symbol is one of them. Almost all the generalizations of the quadratic reciprocity law may be found in the textbook by Lemmermeyer [11].

Since the Legendre symbol is a multiplicative character on ℤ/pℤ, this symbol is extensively used in counting the number of solutions of an equation with coefficients in a finite field by introducing the notion of Jacobi sums, as can be seen, for example, in the textbook by Ireland and Rosen [6] .

In this paper, we consider certain sums involving Legendre symbol with linear, quadratic, and higher-order expressions. Sums involving linear expressions in the Legendre symbol can be easily evaluated, and may be found in textbooks such as [5, 6], mostly as an exercise. The sum involving a quadratic expression was evaluated by Hua [5, Thm. 8.2, p. 174] in a particular case. We evaluate two sums in Section 2.

Finding estimates of sums involving the Legendre symbol has been a main topic of research in the twentieth century. Some of the work on estimates of sums may be found in the work of several authors [4, 7, 9, 12, 13, 14, 15]. In a recent work, Wright [15, Thm. 9.1, p. 213, Thm. 9.2, p. 214] estimated both the complete Weil sum and incomplete Weil sum.

Evaluating the sums of higher-order expressions involving the Legendre symbol is quite challenging. We find certain sums of higher-order expressions in Section 3. To the best of our knowledge, these sums are new and have not appeared before. Some of our identities generalize the identities recently obtained by Karaivanov and Vassilev [8]. The identities obtained by Karaivanov and Vassilev [8] are basically the main motivation of the paper. Sums considered in Theorem 4 and Theorem 9 are also motivated by an exercise [6, Exercise 28, p. 107].

The definitions and properties are used in this paper related to the Legendre symbol may be found in any introductory number theory textbook.

2 Preliminary results

Theorem 1. Let a, b, and c be integers, and let p be an odd prime. Then

∑_{ℓ=0}^{p−1} (\frac{aℓ^{2} + bℓ + c}{p}) = \begin{cases}−(\frac{a}{p}), & if p ∤ (b^{2} − 4ac); \\ (\frac{a}{p})(p − 1), & if p | (b^{2} − 4ac). \end{cases}

Proof. Let S be the required sum to be calculated. Let p | a. Then

S = ∑_{ℓ=0}^{p−1} (\frac{bℓ + c}{p}) .

Clearly, the numbers bℓ + c, where ℓ varies from 0 to p − 1, form a complete residue system modulo p, if b ≢ 0 (mod p). Hence, S = 0 = −(\frac{a}{p}). Next let p ∤ a. Then

S = (\frac{a}{p}) (\frac{4}{p}) ∑_{ℓ=0}^{p−1} (\frac{4a^{2}ℓ^{2} + 4abℓ + 4ac}{p}) = (\frac{a}{p}) ∑_{ℓ=0}^{p−1} (\frac{(2aℓ + b)^{2} + (4ac − b^{2})}{p}) .

Since p ∤ 2a, the set of integers 2aℓ + b, where ℓ varies from 0 to p − 1, forms a complete set of residues modulo p. Thus

S = (\frac{a}{p}) ∑_{ℓ=0}^{p−1} (\frac{ℓ^{2} + (4ac − b^{2})}{p}) .

Now let p | (4ac − b^{2}). Then

S = (\frac{a}{p}) ∑_{ℓ=0}^{p−1} (\frac{ℓ^{2} + (4ac − b^{2})}{p}) = (\frac{a}{p}) ∑_{ℓ=0}^{p−1} (\frac{ℓ^{2}}{p} ) = (\frac{a}{p}) (0 + ∑_{ℓ=1}^{p−1} 1) = (\frac{a}{p}) (p − 1).

It remains to consider the case p ∤ (4ac − b^{2}). Taking the summation modulo p and putting k = (4ac − b^{2}), we get

S ≡ (\frac{a}{p}) ∑_{ℓ=0}^{p−1} (\frac{ℓ^{2} + k}{p} ) ≡ (\frac{a}{p}) ∑_{ℓ=0}^{p−1}(ℓ^{2} + k)^{\frac{p−1}{2}} ≡ (\frac{a}{p}) ∑_{ℓ=1}^{p}(ℓ^{2} + k)^{\frac{p−1}{2}} (mod p).

Putting x = \frac{p−1}{2} and using the binomial theorem, we can write

S ≡ (\frac{a}{p}) ∑_{ℓ=1}^{p} ∑_{r=0}^{x} \binom{x}{r}k^{x−r}ℓ^{2r} (mod p).

Rearranging the sum, we get

S ≡ (\frac{a}{p}) ∑_{r=0}^{x} (\binom{x}{r}k^{x−r} ∑_{ℓ=1}^{p} ℓ^{2r}) (mod p).

To calculate the sum ∑_{ℓ=1}^{p} ℓ^{2r} modulo p, we use the following sum, which is a simple exercise in [1, Exercise 7, Chapter 10],

∑_{ℓ=1}^{p} ℓ^{n} ≡ \{ \begin{matrix}−1, & if (p − 1) | n; \\ 0, & if (p − 1) ∤ n, \end{matrix}

where n ≥ 1.

Since 2r ≤ p − 1, ∑_{ℓ=1}^{p} ℓ^{2r} = −1, only if 2r = p − 1, i.e., r = \frac{p−1}{2} and 0 otherwise. Therefore, in our main summation, all terms are zero except for r = x. Thus,

S ≡ − (\frac{a}{p}) (mod p).

Now, since each term in the summation S, is either −1 or 0 or 1, the value of S lies between −p and p. If (\frac{a}{p}) = −1, then S is either 1 or −p + 1. We have

S = (\frac{a}{p}) ∑_{ℓ=0}^{p−1} (\frac{ℓ^{2} + k}{p} ) .

Since ℓ^{2} ≡ (−ℓ)^{2} ≡ (p − ℓ)^{2} (mod p),

S = (\frac{a}{p}) ((\frac{k}{p}) + 2 ∑_{ℓ=1}^{\frac{p−1}{2}} (\frac{ℓ^{2} + k}{p} )) .

The above identity proves that if p ∤ k, then S is odd. But −p + 1 is even. Therefore, S ≠ −p + 1, consequently, S = 1. A similar argument would show that S = −1, when (\frac{a}{p}) = 1. Hence, in both the cases

S = − (\frac{a}{p}) .

This completes the proof of the theorem.

We obtain Lemma 1 of Karaivanov and Vassilev [8] and a theorem of Hua [5, Thm. 8.2, p. 174] as special cases of the above theorem as follows:

Corollary 2. For integers b and c with p ∤ b,

∑_{ℓ=0}^{p−1} (\frac{bℓ + c}{p}) = 0.

Proof. Setting a ≡ 0 (mod p) in Theorem 1, we get the result. Corollary 3. Let p > 2 and b^{2} − 4c ≢ 0 (mod p). Then

∑_{ℓ=1}^{p} (\frac{ℓ^{2} + bℓ + c}{p}) = −1.

Proof. Setting a = 1 in Theorem 1, we get the corollary.

3 Main results

Theorem 4. Let p be an odd prime and c be an integer. Then

∑_{ℓ=0}^{p−1} (\frac{ℓ^{n} + c}{p}) ≡ \begin{cases}− ∑_{k=1}^{⌊ \frac{gcd(p−1,n)}{2} ⌋} \binom{\frac{p−1}{2}}{k \frac{p−1}{gcd(p−1,n)}}c^{( \frac{p−1}{2} −k \frac{p−1}{gcd(p−1,n)} )}, & if p ∤ c; \\ −1, & if p | c and n ≡ 0 (mod 2); \\ 0, & if p | c and n ≡ 1 (mod 2). \end{cases}

Proof. Let S be the required sum to be calculated. Then

S ≡ ∑_{ℓ=0}^{p−1}(ℓ^{n} + c)^{\frac{p−1}{2}} (mod p).

If p | c, then

S = ∑_{ℓ=0}^{p−1} (\frac{ℓ^{n}}{p} ) mod p.

Hence,

S = \begin{cases}∑_{ℓ=0}^{p−1}(\frac{ℓ^{2}}{p}) = p − 1, & if n ≡ 0 (mod 2); \\ ∑_{ℓ=0}^{p−1}(\frac{ℓ}{p}) = 0, & if n ≡ 1 (mod 2). \end{cases}

Now let p ∤ c. Then taking the summation limits from ℓ = 1 to ℓ = p and using the binomial theorem, we can write

S ≡ ∑_{ℓ=1}^{p} ∑_{r=0}^{\frac{p−1}{2}} \binom{\frac{p−1}{2}}{r}c^{( \frac{p−1}{2} −r)}ℓ^{nr} (mod p).

Rearranging the sum, we get

S ≡ ∑_{r=0}^{\frac{p−1}{2}} (\binom{\frac{p−1}{2}}{r}c^{( \frac{p−1}{2} −r)} ∑_{ℓ=1}^{p} ℓ^{nr}) (mod p).

The value of the sum ∑_{ℓ=1}^{p} ℓ^{nr} modulo p is −1 if (p − 1) | nr and 0 otherwise, for r ≥ 1. For r = 0, the value modulo p is clearly 0. Thus

S ≡ − ∑_{r≥1, (p−1)|nr}^{r≤ \frac{p−1}{2}} \binom{\frac{p−1}{2}}{r}c^{( \frac{p−1}{2} −r)} (mod p).

If (p − 1) | nr, then \frac{p−1}{gcd(p−1,n)} | r. Therefore, the possible values of r are k \frac{p−1}{gcd(p−1,n)}, where k

is an integer satisfying 1 ≤ k ≤ ⌊\frac{gcd(p−1,n)}{2}⌋. So, we have

S ≡ − ∑_{k=1}^{⌊ \frac{gcd(p−1,n)}{2} ⌋} \binom{\frac{p−1}{2}}{k \frac{p−1}{gcd(p−1,n)}}c^{(\frac{p−1}{2} −k \frac{p−1}{gcd(p−1,n)})} (mod p).

This completes the proof.

Theorem 5. Let ξ(a, b, c) = ∑_{ℓ=0}^{p−1}(\frac{aℓ^{2}+bℓ+c}{p})ℓ. Then

2a (\frac{a}{p}) ξ(a, b, c) ≡ b (mod p).

Proof. Clearly,

2a (\frac{a}{p}) ξ(a, b, c) = ∑_{ℓ=0}^{p−1} (\frac{(2aℓ + b)^{2} + (4ac − b^{2})}{p}) 2aℓ

= ∑_{ℓ=0}^{p−1} (\frac{(2aℓ + b)^{2} + (4ac − b^{2})}{p}) (2aℓ + b) − b ∑_{ℓ=0}^{p−1} (\frac{(2aℓ + b)^{2} + (4ac − b^{2})}{p}) .

Since the set of integers 2aℓ + b forms a complete set of residues,

2a (\frac{a}{p}) ξ(a, b, c) ≡ ∑_{ℓ=0}^{p−1} (\frac{ℓ^{2} + (4ac − b^{2})}{p}) ℓ − b ∑_{ℓ=0}^{p−1} (\frac{l^{2} + (4ac − b^{2})}{p}) (mod p).

By Theorem 1,

∑_{ℓ=0}^{p−1} (\frac{ℓ^{2} + (4ac − b^{2})}{p}) ≡ −1 (mod p).

This gives

2a (\frac{a}{p}) ξ(a, b, c) ≡ ∑_{ℓ=0}^{p−1} (\frac{ℓ^{2} + (4ac − b^{2})}{p}) ℓ + b ≡ ξ(1, 0, 4ac − b^{2}) + b (mod p). (1)

Note that

ξ(1, 0, 4ac − b^{2}) = ∑_{ℓ=0}^{p−1} \frac{ℓ^{2} + (4ac − b^{2})}{p}ℓ ≡ ∑_{ℓ=1}^{p}(ℓ^{2} + (4ac − b^{2}))^{\frac{p−1}{2}} ℓ (mod p).

Hence, using the binomial theorem, we get

ξ(1, 0, 4ac − b^{2}) ≡ ∑_{ℓ=1}^{p} ∑_{r=0}^{\frac{p−1}{2}} \binom{\frac{p−1}{2}}{r}(4ac − b^{2})^{( \frac{p−1}{2} −r)}ℓ^{2r+1} (mod p).

Thus, rearranging the terms, we get

ξ(1, 0, 4ac − b^{2}) ≡ ∑_{r=0}^{\frac{p−1}{2}} (\binom{\frac{p−1}{2}}{r}(4ac − b^{2})^{( \frac{p−1}{2} −r)} ∑_{ℓ=1}^{p} ℓ^{2r+1}) (mod p).

The sum ∑_{ℓ=1}^{p} ℓ^{2r+1}, is equal to −1 modulo p if (p − 1) | (2r + 1) and 0 otherwise. But p − 1 is even and 2r + 1 is odd. Therefore, (p − 1) ∤ (2r + 1) and the sum ∑_{ℓ=1}^{p} ℓ^{2r+1}, is equal to 0 modulo p for all values of r. Therefore,

ξ(1, 0, 4ac − b^{2}) ≡ 0 (mod p).

Using this in (1), we get

2a (\frac{a}{p}) ξ(a, b, c) ≡ b (mod p).

Corollary 6. We have ξ(ka, kb, kc) = (\frac{k}{p})ξ(a, b, c) for all integers k.

Proof. Follows directly from the above theorem.

Remark 7. As a consequence of the above theorem, we get that ξ(a, b, c) is the unique solution of the congruence 2a(\frac{a}{p})x ≡ b (mod p).

Theorem 8. Let

S(a, b, c) = ∑_{ℓ=0}^{p−1} (\frac{aℓ^{2} + bℓ + c}{p})

and m be a positive integer. Then

ξ(a, b + 2ma, m^{2}a + mb + c) = ξ(a, b, c) + p ∑_{r=0}^{m−1} (\frac{r^{2}a + rb + c}{p}) − mS(a, b, c).

Proof. The proof is by induction on m. We have

ξ(a, b + 2a, a + b + c) = ∑_{ℓ=0}^{p−1} (\frac{aℓ^{2} + (b + 2a)ℓ + (a + b + c)}{p}) ℓ

= ∑_{ℓ=0}^{p−1} (\frac{a(ℓ + 1)^{2} + b(ℓ + 1) + c}{p}) (ℓ + 1) − S(a, b, c)

= ∑_{ℓ=1}^{p} (\frac{aℓ^{2} + bℓ + c}{p}) ℓ − S(a, b, c)

= ∑_{ℓ=0}^{p−1} (\frac{aℓ^{2} + bℓ + c}{p}) ℓ + p (\frac{c}{p}) − S(a, b, c)

= ξ(a, b, c) + p (\frac{c}{p}) − S(a, b, c).

So the basis step, m = 1, is satisfied. Now let the identity hold for m − 1; we prove it for m. Let B = b + 2(m − 1)a and C = (m − 1)^{2}a + (m − 1)b + c. Then

ξ(a, b + 2ma, m^{2}a + mb + c) = ξ(a, B + 2a, a + B + C) = ξ(a, B, C) + p (\frac{C}{p} ) − S(a, B, C).

Using the induction hypothesis on ξ(a, B, C), we can write

ξ(a, b + 2ma, m^{2}a + mb + c) = ξ(a, b, c) + p ∑_{r=0}^{m−2} (\frac{r^{2}a + rb + c}{p}) − (m − 1)S(a, b, c)

+ p (\frac{(m − 1)^{2}a + (m − 1)b + c}{p}) − S(a, B, C).

We have 4aC − B^{2} = 4ac − b^{2}. Hence, by Theorem 1, S(a, b, c) = S(a, B, C). This implies that

ξ(a, b + 2ma, m^{2}a + mb + c) = ξ(a, b, c) + p ∑_{r=0}^{m−1} (\frac{r^{2}a + rb + c}{p}) − mS(a, b, c).

This completes the proof of the theorem.

Theorem 9. Let p be an odd prime and c, n ≥ 1, and k ≥ 1 be integers. Then, modulo p, we have

∑_{ℓ=0}^{p−1} (\frac{ℓ^{n} + c}{p}) ℓ^{k} ≡ \{ \begin{matrix}− ∑_{{0≤r≤(p−1)/2 \atop (p−1)|(nr+k)}} \binom{\frac{p−1}{2}}{r}c^{( \frac{p−1}{2} −r)}, & if p ∤ c; \\ −1, & if p | c and (p − 1) | (n(\frac{p−1}{2}) + k); \\ 0, & if p | c and (p − 1) ∤ (n(\frac{p−1}{2}) + k). \end{matrix}

Proof. Let η denote the required sum to be calculated. If p | c, then the sum reduces to

η ≡ ∑_{ℓ=0}^{p−1} ℓ^{n( \frac{p−1}{2} )+k} (mod p).

This is equal to 0 if (p − 1) ∤ (n(\frac{p−1}{2}) + k), and −1 otherwise. Next let p ∤ c. Proceeding in the same way as in the proof of Theorem 4, we obtain

η ≡ ∑_{r=0}^{\frac{p−1}{2}} \binom{\frac{p−1}{2}}{r}c^{( \frac{p−1}{2} −r)} ∑_{ℓ=1}^{p} ℓ^{nr+k} (mod p).

The sum ∑_{ℓ=1}^{p} ℓ^{nr+k} modulo p is equal to 0 when (p − 1) ∤ (nr + k), and −1 otherwise. Thus

η ≡ − ∑_{{0≤r≤(p−1)/2 \atop (p−1)|(nr+k)}} \binom{\frac{p−1}{2}}{r}c^{( \frac{p−1}{2} −r)} (mod p).

Corollary 10. If n is even and k is odd, then

η ≡ 0 (mod p).

Proof. Since the given conditions imply that nr + k is odd, there does not exist r such that (p − 1) | (nr + k). Therefore, by Theorem 9, we have η ≡ 0 (mod p).

As another corollary, we obtain [8, Claim 1] in a special case, when a = 1.

Corollary 11. For odd primes p, the quantity S_{p}(1, b) is divisible by p.

Proof. The proof follows from the above theorem by taking n = 1 = k and c = b.

4 Acknowledgments

We thank the anonymous referee for his remarks on the results.

References

[1] T. M. Apostol, Introduction to Analytic Number Theory, Springer, 1989.

[2] E. Bach and J. Shallit, Algorithmic Number Theory, Volume I: Efficient Algorithms, Cambridge, 1996.

[3] C. F. Gauss, Disquisitiones Arithmeticae, Leipzig, 1801.

[4] E. A. Grechnikov, An estimate for the sum of Legendre symbols, Math. Notes 88 (2010), 819–826.

[5] L. K. Hua, Introduction to Number Theory, Springer-Verlag, 1982.

[6] K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer-Verlag, 1990.

[7] A. A. Karacuba, Sums of Legendre symbols of polynomials of second degree over prime numbers, Izv. Math. 12 (1978), 299–308.

[8] B. Karaivanov and T. S. Vassilev, On certain sums involving the Legendre symbol, Integers 16 (2016), A14.

[9] P. M. Korobov, An estimate of the sum of the Legendre symbols, Dokl. Akad. Nauk SSSR 196 (1971), 764–767.

[10] A. M. Legendre, Essai sur la Théorie des Nombres, Dupart, Paris, 1798.

[11] F. Lemmermeyer, Reciprocity Laws: from Euler to Eisenstein, Springer, 2000.

[12] D. A. Mit’kin, Sharpening an estimate for the sum of the Legendre symbols of polynomials of odd degree, Chebyshevskiĭ Sb. 6 (2005), 123–126.

[13] A. Weil, Number Theory: An Approach Through History, Birkhäuser Boston, 2001.

[14] A. Weil, Sur les Courbes Algébriques et les Variétés qui s’en Déduisent, Hermann, 1948.

[15] S. Wright, Quadratic Residues and Non-Residues: Selected Topics, Springer-Verlag, 2016.

2010 Mathematics Subject Classification: Primary 11A07; Secondary 11A15. Keywords: quadratic residue, quadratic nonresidue, Legendre symbol.

Received November 28 2017; revised versions received January 9 2018; April 8 2018. Published in Journal of Integer Sequences, May 9 2018.

Return to Journal of Integer Sequences home page.