Counting Integers Representable as Sums of k-th Powers Modulo n

Fabián Arias Departamento de Matemáticas Universidad del Atlántico Barranquilla, 081007 Colombia

                 farias374@hotmail.com

Jerson Borja and Samuel Anaya Departamento de Matemáticas y Estadística Universidad de Córdoba Montería, 230002 Colombia

         jersonborjas@correo.unicordoba.edu.co
         samuelanayai@correo.unicordoba.edu.co

Abstract

Given a polynomial f(x_{1}, x_{2}, …, x_{t}) in t variables with integer coefficients and a positive integer n, we define α(n) as the number of integers 0 ≤ a < n such that the congruence f(x_{1}, x_{2}, …, x_{t}) ≡ a (mod n) is solvable.

We improve some known results for computing α(p^{n}), where p is prime and n ≥ 1, for polynomials of the form c_{1}x_{1}^{k} +c_{2}x_{2}^{k} +⋯+c_{t}x_{t}^{k}. We apply these results to calculate α(p^{n}) for polynomials of the form x^{k} ± y^{k} and to study the modular Waring problem.

1 Introduction

Additive number theory focuses on estimating the size of sumsets or characterizing the elements that can be expressed as sums of elements from a given set. One of the earliest problems in this context concerns the characterization of integers that can be expressed as sums of squares. Fermat’s theorem states that an odd prime number p can be written as a sum of two squares if and only if p is of the form 4k +1. Euler characterized the integers that can be represented as a sum of two squares. The Gauss-Legendre theorem gives a criterion for an integer n to be represented as a sum of three squares. Finally, Lagrange’s theorem asserts that every nonnegative integer can be expressed as the sum of four squares. These results completely solve the problem of representing integers as sums of squares.

A natural question that arises when we consider a polynomial f(x_{1}, …, x_{t}) with integer coefficients is to characterize the integers that can be expressed in the form f(k_{1}, …, k_{t}), where k_{1}, …, k_{t} are integers. We know the answer to this question for certain polynomials, such as x^{2} + y^{2}, x^{2} + y^{2} + z^{2}, and x^{2} + y^{2} + z^{2} + w^{2}.

Another well known problem in additive number theory is the Waring problem. It states that for every positive integer k, there exists a positive integer t such that every nonnegative integer can be written as a sum of t k-th powers. The Waring-Hilbert theorem establishes the existence of t for every k. The minimum value of such t is denoted by g(k). For instance, g(2) = 4, g(3) = 9, g(4) = 15.

It is interesting to consider modular versions of the above problems. Specifically, let f(x_{1}, …, x_{t}) be a polynomial with integer coefficients, n ∈ ℤ^{+}, and let A_{n} be the set of all elements a ∈ {0, 1, …, n − 1} such that the congruence f(x_{1}, x_{2}, …, x_{t}) ≡ a (mod n) has a solution. Let α(n) denote the size of A_{n}. In these terms, we consider the following questions:

1. Determine α(n) in terms of n.

2. Characterize all n such that α(n) = n.

Harrington, Jones, and Lamarche [5] characterized the integers in ℤ_{n} that can be expressed as a sum of two nonzero squares in ℤ_{n}, and they also determined the integers n such that α(n) = n, for the function α associated with x^{2} + y^{2}. Broughan [4] provided explicit calculations of α(n) for the polynomial x^{3}+y^{3}. Arias, Borja, and Rubio [3] found explicit formulas for α(n) in terms of the prime decomposition of n for the polynomials x^{2} + y^{2}, x^{2} − y^{2}, and x^{2} + y^{2} + z^{2}.

In this work, we study the aforementioned problems for polynomials of the form c_{1}x_{1}^{k} + ⋯+c_{t}x_{t}^{k}. We focus our attention on polynomials of the form x^{k} +y^{k} and x^{k} −y^{k}. In Section 2, we give slightly improvements of some results by Arias et al. [3] about polynomials of the form c_{1}x_{1}^{k} + ⋯ + c_{t}x_{t}^{k}. One of these results is Proposition 4, which provides a method to compute α(p^{n}) for such polynomials. Then we apply these results to the computation of α(p^{n}) for polynomials of the form x^{k} + y^{k} and x^{k} − y^{k}.

Finally, we consider the modular version of the Waring problem. It consists in determining the minimum positive integer γ(k, n) such that every element in ℤ_{n} can be expressed as a sum of γ(k, n) k-th powers in ℤ_{n}. Small [8] showed a method to solve the modular Waring problem. Waring problem for diagonal forms has been treated recently, for instance by Alnaser and Cochrane [2]. We apply our techniques to compute α(p^{n}) for polynomials of the form x_{1}^{k} + x_{2}^{k} + ⋯ + x_{t}^{k}, for t ≤ γ(k, n), and to determine the value max_{n} γ(k, n) for small values of k.

2 General results

We will follow the notation of [3]. For a prime p and n ≥ 1 we define sets

A_{p^{n}} = {a ∈ {0, 1, …, p^{n} − 1} : f(x_{1}, …, x_{t}) ≡ a (mod p^{n}) is solvable},

and

A_{p^{n}}(p^{n−1}) = {a + jp^{n−1} : a ∈ A_{p^{n−1}}, 0 ≤ j < p}.

The inclusion A_{p^{n}} ⊆ A_{p^{n}}(p^{n−1}) holds and we set N_{p^{n}} = A_{p^{n}}(p^{n−1}) \ A_{p^{n}}.

We say that a nonnegative integer e is an exponent of p in f(x_{1}, …, x_{t}), if whenever p^{e} divides an integer of the form f(m_{1}, …, m_{t}), then the quotient f(m_{1}, …, m_{t})/p^{e} is also of the form f(q_{1}, …, q_{t}), for some integers q_{1}, …, q_{t}.

Now we show some results related to the function α associated with a polynomial of the form f(x_{1}, x_{2}, …, x_{t}) = c_{1}x_{1}^{k} + c_{2}x_{2}^{k} + ⋯ + c_{t}x_{t}^{k}, where c_{1}, …, c_{t} are integers and k ≥ 1.

Proposition 1. Let p be a prime number that does not divide c_{1}, c_{2}, …, c_{t}, and let s be the highest nonnegative integer such that p^{s} divides k. Let a ∈ A_{p^{n}} and suppose that the congruence

c_{1}x_{1}^{k} + c_{2}x_{2}^{k} + ⋯ + c_{t}x_{t}^{k} ≡ a (mod p^{n})

has a solution, where at least one of the x_{i}’s is not divisible by p. If at least one of the following conditions holds:

1. p is odd and n ≥ s + 1, or

2. p = 2 and n ≥ min(s + 2, 2s + 1),

then a + jp^{n} ∈ A_{p^{n+1}}, for all 0 ≤ j < p. Moreover, for all 0 ≤ j < p, the congruence

c_{1}x_{1}^{k} + c_{2}x_{2}^{k} + ⋯ + c_{t}x_{t}^{k} ≡ a + jp^{n} (mod p^{n+1})

has a solution, where at least one of the x_{i}’s is not divisible by p.

Proof. The proof of this proposition, in the case s ≥ 1, is similar to that of [1, Lemma 1]. In the case s = 0, the result follows from [3, Lemma 2.6].

Remark 2. Assume n_{0} ≥ s + 1, if p is an odd prime, or n_{0} ≥ min(s + 2, 2s + 1), if p = 2. If a ∈ A_{p^{n_{0}}}, then there are integers m_{1}, …, m_{t} such that c_{1}m_{1}^{k} + ⋯ + c_{t}m_{t}^{k} ≡ a (mod p^{n_{0}}). If p ∤ a, then at least one of the m_{i}’s is not divisible by p. Thus, from Proposition 1 we conclude that a + jp^{n_{0}} ∈ A_{p^{n_{0}+1}} for all 0 ≤ j < p. Hence, the only elements that might not belong to A_{p^{n_{0}+1}} are those of the form a + jp^{n_{0}}, where p | a and 0 ≤ j < p. Therefore, under the assumption that the congruence

c_{1}x_{1}^{k} + c_{2}x_{2}^{k} + ⋯ + c_{t}x_{t}^{k} ≡ a (mod p^{n_{0}})

has a solution, where some x_{i} is not divisible by p, for every a ∈ A_{p^{n_{0}}} such that p | a, then we get A_{p^{n_{0}+1}} = {a + jp^{n_{0}} : a ∈ A_{p^{n_{0}}}, 0 ≤ j < p}. So α(p^{n_{0}+1}) = pα(p^{n_{0}}), and an induction argument shows that α(p^{n}) = p^{n−n_{0}}α(p^{n_{0}}), for all n ≥ n_{0}. We can now formulate the following result.

Proposition 3. Let p be a prime number that does not divide c_{1}, c_{2}, …, c_{t}, let s be the highest nonnegative integer such that p^{s} divides k, and n_{0} be a positive integer. Assume that n_{0} ≥ s + 1, if p is an odd prime, or n_{0} ≥ min(s + 2, 2s + 1), if p = 2. Suppose that for every a ∈ A_{p^{n_{0}}} such that p | a, the congruence

c_{1}x_{1}^{k} + c_{2}x_{2}^{k} + ⋯ + c_{t}x_{t}^{k} ≡ a (mod p^{n_{0}})

has a solution, where some x_{i} is not divisible by p. Then α(p^{n}) = p^{n−n_{0}}α(p^{n_{0}}) for all n ≥ n_{0}.

Proposition 4. Let p be a prime number that does not divide c_{1}, c_{2}, …, c_{t}, and let s be the highest nonnegative integer such that p^{s} divides k. If p is odd, assume that the congruence

c_{1}x_{1}^{k} + c_{2}x_{2}^{k} + ⋯ + c_{t}x_{t}^{k} ≡ 0 (mod p^{s+1})

has a solution, where some x_{i} is not divisible by p. Then α(p^{n}) = p^{n−s−1}α(p^{s+1}) for all n ≥ s + 1. If p = 2 and k ≠ 2, define β = min(s + 2, 2s + 1) and assume that the congruence

c_{1}x_{1}^{k} + c_{2}x_{2}^{k} + ⋯ + c_{t}x_{t}^{k} ≡ 0 (mod 2^{β})

has a solution, where some x_{i} is not divisible by 2. Then α(2^{n}) = 2^{n−β}α(2^{β}) for all n ≥ β.

Proof. Assume p is an odd prime number. Write k = p^{s}k_{0}, where p ∤ k_{0} and s ≥ 0. Given a ∈ A_{p^{s+1}}, let us consider the congruence

c_{1}x_{1}^{k} + c_{2}x_{2}^{k} + ⋯ + c_{t}x_{t}^{k} ≡ 0 (mod p^{s+1}).  (1)

By hypothesis, if a = 0, then (1) has a solution where, some x_{i} is not divisible by p. The same conclusion is true, if p ∤ a.

Now assume p | a and a ≠ 0. Since a ∈ A_{p^{s+1}}, there are integers m_{1}, …, m_{t}, w such that c_{1}m_{1}^{k} + c_{2}m_{2}^{k} + ⋯ + c_{t}m_{t}^{k} = a + wp^{s+1}. We want to prove that some m_{i} is not divisible by p. On the contrary, if all m_{i}’s are divisible by p, then there exist integers n_{1}, n_{2}, …, n_{t} such that m_{i} = pn_{i}, for all i ∈ {1, …, t}. Therefore, p^{k}(c_{1}n_{1}^{k} + c_{2}n_{2}^{k} + ⋯ + c_{t}n_{t}^{k}) = a + wp^{s+1}, which shows that p^{s+1} divides a, since k ≥ s + 1. It follows that a = 0, which is a contradiction.

We have proved that for every a ∈ A_{p^{s+1}}, the congruence (1) has a solution, where at least one x_{i} is not divisible by p. By Proposition 3, we have α(p^{n}) = p^{n−s−1}α(p^{s+1}), for all n ≥ s + 1.

The proof for the case p = 2 is similar.

Corollary 5. Let p be a prime number that does not divide k, c_{1}, c_{2}, …, c_{t}. If the congruence

c_{1}x_{1}^{k} + c_{2}x_{2}^{k} + ⋯ + c_{t}x_{t}^{k} ≡ 0 (mod p)

has a nontrivial solution, then α(p^{n}) = p^{n−1}α(p), for all n ≥ 1.

The hypothesis of Corollary 5 holds when c_{1} + c_{2} + ⋯ + c_{t} is divisible by p. Clearly, this occurs for a difference of k-th powers x^{k} − y^{k}.

Recall that N_{p^{n}} is the set of all elements of the form a + jp^{n−1}, a ∈ {0, 1, …, p^{n−1} − 1}, 0 ≤ j < p such that the congruence c_{1}x_{1}^{k} + c_{2}x_{2}^{k} + ⋯ + c_{t}x_{t}^{k} ≡ a (mod p^{n−1}) is solvable, but the congruence c_{1}x_{1}^{k} + c_{2}x_{2}^{k} + ⋯ + c_{t}x_{t}^{k} ≡ a + jp^{n−1} (mod p^{n}) is not solvable.

Proposition 6. Let p be a prime number that does not divide c_{1}, c_{2}, …, c_{t}, and s be the highest nonnegative integer such that p^{s} divides k. Then

N_{p^{r}} ⊆ {jp^{r−1} : 0 < j < p},

for s + 2 ≤ r ≤ k, and

N_{p^{k+1}} ⊆ {jp^{k} : j ∉ A_{p}, 0 < j < p}.

Moreover, if some exponent of p in c_{1}x_{1}^{k} + c_{2}x_{2}^{k} + ⋯ + c_{t}x_{t}^{k} divides k, then

N_{p^{k+1}} = {jp^{k} : j ∉ A_{p}, 0 < j < p}.

Proof. Assume s + 2 ≤ r ≤ k + 1. Let us show that a + jp^{r−1} ∈ A_{p^{r}}, for all a ∈ A_{p^{r−1}} with a ≠ 0 and 0 ≤ j < p. Indeed, if a ∈ A_{p^{r−1}} and a ≠ 0, then there exist integers m_{1}, …, m_{t} such that

c_{1}m_{1}^{k} + c_{2}m_{2}^{k} + ⋯ + c_{t}m_{t}^{k} ≡ a (mod p^{r−1}).

If p divides all the m_{i}’s, then p^{r−1} divides a because s + 1 ≤ r − 1 ≤ k. Since 0 ≤ a < p^{r−1}, it follows that a = 0, which is a contradiction. So, at least one m_{i} is not divisible by p. By Proposition 1, we have a + jp^{r−1} ∈ A_{p^{r}}, for all 0 ≤ j < p. Therefore, every element in N_{p^{r}} has the form jp^{r−1}, where 0 ≤ j < p. Since 0 ∉ N_{p^{r}}, we have N_{p^{r}} ⊆ {jp^{r−1} : 0 < j < p}.

Now, if r = k + 1 and j ∈ A_{p}, where 0 < j < p, then there are integers m_{1}, …, m_{t} such that

c_{1}m_{1}^{k} + c_{2}m_{2}^{k} + ⋯ + c_{t}m_{t}^{k} ≡ j (mod p),

from which

c_{1}(pm_{1})^{k} + c_{2}(pm_{2})^{k} + ⋯ + c_{t}(pm_{t})^{k} ≡ jp^{k} (mod p^{k+1}).

This implies that jp^{k} ∈ A_{p^{k+1}}. Consequently, N_{p^{k+1}} ⊆ {jp^{k} : j ∉ A_{p}, 0 < j < p}.

Finally, we assume that some exponent of p in c_{1}x_{1}^{k} + c_{2}x_{2}^{k} + ⋯ + c_{t}x_{t}^{k} divides k. If jp^{k} ∈ A_{p^{k}}, then c_{1}m_{1}^{k} +c_{2}m_{2}^{k} +⋯+c_{t}m_{t}^{k} ≡ jp^{k} (mod p^{k+1}) for some integers m_{1}, m_{2}, …, m_{t}. Since (c_{1}m_{1}^{k} + c_{2}m_{2}^{k} + ⋯ + c_{t}m_{t}^{k})/p^{k} = c_{1}q_{1}^{k} + c_{2}q_{2}^{k} + ⋯ + c_{t}q_{t}^{k} for some integers q_{1}, q_{2}, …, q_{t}, we obtain the congruence c_{1}q_{1}^{k} + c_{2}q_{2}^{k} + ⋯ + c_{t}q_{t}^{k} ≡ j (mod p), which shows that j ∈ A_{p}. Thus, N_{p^{k+1}} = {jp^{k} : j ∉ A_{p}, 0 < j < p}.

The following two results can be found in [3].

Proposition 7. Let p be a prime and k ≥ 1. Suppose that some exponent e of p in the polynomial c_{1}x_{1}^{k} + ⋯ + c_{t}x_{t}^{k} divides k. Then

α(p^{n}) = pα(p^{n−1}) − |N_{p^{r}}|,

for all n > 1 such that n ≡ r (mod k).

Proposition 8. Let p be a prime and k be a positive integer. Suppose that some exponent e of p in the polynomial c_{1}x_{1}^{k} + ⋯ + c_{t}x_{t}^{k} divides k, and p does not divide c_{1}, …, c_{t}. Let n be a positive integer. Then

(i) If n ≡ 1 (mod k), then

α(p^{n}) = p^{n−1}α(p) − \frac{p^{n−1} − 1}{p^{k} − 1} ∑_{j=2}^{k+1} |N_{p^{j}}|p^{k−j+1};

(ii) If n ≡ r (mod k), where 2 ≤ r ≤ k, then

α(p^{n}) = p^{n−1}α(p) − \frac{p^{n−1} − p^{r−1}}{p^{k} − 1} ∑_{j=2}^{k+1} |N_{p^{j}}|p^{k−j+1} − ∑_{j=2}^{r} |N_{p^{j}}|p^{r−j}.

3 Some results from additive number theory

The following results from additive number theory can be consulted in [7].

Theorem 9 (Cauchy-Davenport). Let p be a prime number, and let A and B be nonempty subsets of ℤ/pℤ. Then

|A + B| ≥ min(p, |A| + |B| − 1).

By an induction argument, we see that if B_{1}, B_{2}, …, B_{h} are nonempty subsets of ℤ/pℤ, then

|B_{1} + B_{2} + ⋯ + B_{h}| ≥ min (p, ∑_{i=1}^{h} |B_{i}| − h + 1) .

The following theorem gives us conditions to get equality in the Cauchy-Davenport theorem.

Theorem 10 (Vosper). Let p be a prime number, and let A and B be nonempty subsets of the group G = ℤ/pℤ such that A + B ≠ G. Then

|A + B| = |A| + |B| − 1

if and only if at least one of the following three conditions holds:

(i) min(|A|, |B|) = 1,

(ii) |A + B| = p − 1 and B = \overline{c − A} (the complement of c − A), where \{c\} = G \ (A + B),

(iii) A and B are arithmetic progressions with the same common difference.

Proposition 11. Let p > 3 be a prime number, and let p ≡ 1 (mod k), where 1 < k < (p − 1)/2. If B_{k} = {x^{k} : x ∈ ℤ/pℤ}, then B_{k} is not an arithmetic progression in ℤ/pℤ.

Following the terminology of Nathanson [7, Section 2.6], the polynomial f(x_{1}, …, x_{t}) = c_{1}x_{1}^{k} + ⋯ + c_{t}x_{t}^{k} with coefficients in the finite field ℤ/pℤ is called a diagonal form of degree k. The range of f is the set

R(f) = {f(x_{1}, …, x_{t}) : x_{1}, …, x_{t} ∈ ℤ/pℤ} .

Note that |R(f)| = α(p), where α is the function associated with c_{1}x_{1}^{k} + ⋯ + c_{t}x_{t}^{k}.

Theorem 12. Let p > 3 be a prime number, and let k be a positive integer such that

1 < gcd(p − 1, k) < \frac{p − 1}{2}.

Let c_{1}, c_{2}, …, c_{t} be nonzero elements of the field ℤ/pℤ, and let f(x_{1}, …, x_{t}) = c_{1}x_{1}^{k}+⋯+c_{t}x_{t}^{k}. Then

|R(f)| ≥ min (p, \frac{(2t − 1)(p − 1)}{gcd(p − 1, k)} + 1) .

The following theorem is an application of the above results.

Theorem 13. Let p be a prime number and c_{1}, …, c_{t} be integers numbers not divisible by p. Assume that 1 < gcd(k, p − 1) < (p − 1)/2 and t > (k + 2)/2. Then the congruence

c_{1}x_{1}^{k} + ⋯ + c_{t}x_{t}^{k} ≡ 0 (mod p)

has a nontrivial solution.

Proof. Let A = {c_{1}x_{1}^{k} + ⋯ + c_{t}x_{t}^{k} (mod p) : x_{1}, …, x_{t} ∈ ℤ, p ∤ x_{1}} and d = gcd(p − 1, k). It is easy to check that

A = {c_{1}x_{1}^{d} + ⋯ + c_{t}x_{t}^{d} (mod p) : x_{1}, …, x_{t} ∈ ℤ, p ∤ x_{1}}.

We want to show that 0 ∈ A. Assume that 0 ∉ A. Let B = {c_{1}x_{1}^{d} (mod p) : x_{1} ∈ ℤ, p ∤ x_{1}} and C = {c_{2}x_{2}^{d} + ⋯ + c_{t}x_{t}^{d} (mod p) : x_{2}, …, x_{t} ∈ ℤ}. Thus, A = B + C. It is clear that

|B| = (p − 1)/d and it follows from Theorem 12 that |C| ≥ min(p, \frac{(2t−3)(p−1)}{d} + 1). Now,

from the Cauchy-Davenport theorem, we obtain

|A| = |B + C| ≥ min(p, |B| + |C| − 1) = min (p, \frac{(2t − 2)(p − 1)}{d}) .

Note that |A| < p. If we assume that |A| = \frac{(2t−2)(p−1)}{d}, then by Vosper’s theorem we have three cases:

1. |B| = 1 or |C| = 1. This is impossible because (p − 1)/d > 1.

2. |B + C| = p − 1. This implies that p − 1 = (2t − 2)(p − 1)/d, so t = (d + 2)/2. Now, since d ≤ k, we obtain that t ≤ (k + 2)/2, which contradicts the hypothesis.

3. B and C are arithmetic progressions with the same common difference. This is impossible by Proposition 11.

We conclude that

|A| > \frac{(2t − 2)(p − 1)}{d}.

Now the set A is a disjoint union of sets of the form {cx^{d} (mod p) : x ∈ ℤ, p ∤ x}, where p ∤ c, see [7, Lemma 2.9]. Therefore, we have |A| ≡ 0 (mod (p − 1)/d). If follows that

|A| ≥ \frac{(2t − 2)(p − 1)}{d} + \frac{p − 1}{d} = \frac{(2t − 1)(p − 1)}{d}.

Since |A| < p, we have \frac{(2t−1)(p−1)}{d} < p. Hence, t ≤ (k+1)/2, which contradicts the hypothesis. This finishes the proof.

4 Polynomials of the form x^{k} + y^{k}

In this section, α is the function associated with a polynomial of the form x^{k} + y^{k}. We want to determine explicit formulas for α(p^{n}), where p is prime and n ≥ 1. Since the cases k = 2 and k = 3 were solved by Arias et al. [3], and Broughan [4], respectively, we will focus on k ≥ 4.

4.1 General results on the computation of α(p^{n})

We start with p = 2. The following proposition will help us to find α(2^{n}), when k is even.

Proposition 14. Let k be an even positive integer. Then k is an exponent of the prime number p = 2 in the polynomial x^{k} + y^{k}.

Proof. Assume 2^{k} divides an integer of the form x^{k} + y^{k}. Clearly, x and y have the same parity. If x and y are even, then x = 2x_{0} and y = 2y_{0}, for some integers x_{0} and y_{0}. So, we have x^{k} + y^{k} = 2^{k}(x_{0}^{k} + y_{0}^{k}), which implies that (x^{k} + y^{k})/2^{k} = x_{0}^{k} + y_{0}^{k}. Now, if x and y are odd, then x = 2x_{0} + 1 and y = 2y_{0} + 1, for some integers x_{0} and y_{0}. Using the binomial theorem, we find that x^{k} = 4x_{1} + 1 and y^{k} = 4y_{1} + 1, for some positive integers x_{1} and y_{1}. Therefore, x^{k} + y^{k} = 4(x_{1} + y_{1}) + 2, which is not divisible by 2^{k}. We conclude that k is an exponent of the prime 2 in the polynomial x^{k} + y^{k}.

Now we consider the case where the prime p is odd. It is easy to check the following result.

Lemma 15. Let p be an odd prime number and d be a positive divisor of p − 1. Then p ≡ 1 (mod 2d) or p ≡ d + 1 (mod 2d).

Proposition 16. Let p be an odd prime, d = gcd(p − 1, k), and assume that p ≡ d + 1 (mod 2d). Then k is an exponent of p in the polynomial x^{k} + y^{k}.

Proof. Suppose that p^{k} divides a^{k} + b^{k}, where a and b are integer. For the proof, it is sufficient to show that p divides a and b. Assume that p does not divide a. Then there exists an integer c such that ca ≡ 1 (mod p). Since a^{k} + b^{k} ≡ 0 (mod p), it follows that

1 + (cb)^{k} ≡ (ca)^{k} + (cb)^{k} ≡ c^{k}(a^{k} + b^{k}) ≡ 0 (mod p).

Therefore, the congruence z^{k} ≡ −1 (mod p) has a solution, which implies (−1)^{\frac{p−1}{d}} ≡ 1 (mod p), so \frac{p−1}{d} is even. This contradicts the hypothesis that \frac{p−1}{d} is odd. Thus, we conclude that p divides a. Similarly, p divides b.

We conclude that (a^{k} + b^{k})/p^{k} = (a/p)^{k} + (b/p)^{k} is a sum of two k-th powers. This ends the proof.

Proposition 17. Suppose p is an odd prime, p^{s} is the highest power of p that divides k, and let d = gcd(p − 1, k). If p ≡ d + 1 (mod 2d), then N_{p^{r}} = {jp^{r−1} : 0 < j < p}, for s + 2 ≤ r ≤ k and N_{p^{k+1}} = {jp^{k} : 0 < j < p, j ∉ A_{p}}.

Proof. By Proposition 6, it only remains to prove that {jp^{r−1} : 0 < j < p} ⊆ N_{p^{r}} for s + 2 ≤ r ≤ k. Let us suppose that there exists 0 < j_{0} < p such that j_{0}p^{r−1} ∉ N_{p^{r}}, that is, there are integers x, y such that, x^{k} +y^{k} ≡ j_{0}p^{r−1} (mod p^{r}). Since r −1 ≥ 1, we have p divides x^{k} +y^{k}, so p divides both x and y. Thus, from the congruence x^{k} +y^{k} ≡ j_{0}p^{r−1} (mod p^{r}) and the fact that r ≤ k, it follows that p^{r} divides j_{0}p^{r−1}, so p divides j_{0}, which is a contradiction.

In the following theorem, we find recursive formulas for computing α(p^{n}).

Theorem 18. Let p be an odd prime, d = gcd(p − 1, k), and s be the highest nonnegative integer such that p^{s} divides k.

1. If k is even, s = 0 and p ≡ 1 (mod 2d), then α(p^{n}) = p^{n−1}α(p), for all n ≥ 1.

2. If k is even and p ≡ d + 1 (mod 2d), then α(p^{n}) = pα(p^{n−1}) + α(p) − p, for all n ≡ 1 (mod k).

3. If k is even and p ≡ d+1 (mod 2d), then α(p^{n}) = pα(p^{n−1})−p+1, for all n ≡ r (mod k), where s + 2 ≤ r ≤ k.

4. If k is odd and s = 0, then α(p^{n}) = p^{n−1}α(p), for all n ≥ s + 1.

Proof. We first assume that k is even, s = 0 and p ≡ 1 (mod 2d). Then \frac{p−1}{d} is even, so (−1)^{\frac{p−1}{d}} ≡ 1 (mod p). It follows that the congruence x^{k} ≡ −1 (mod p) is solvable, which implies that x^{k} + y^{k} ≡ 0 (mod p) has a nontrivial solution. Therefore, from Corollary 5, it follows that α(p^{n}) = p^{n−1}α(p), for all n ≥ 1.

Statements 2 and 3 follow from Propositions 7 and 17.

Finally, we prove statement 4. If k is odd, then d = gcd(p−1, k) is odd, so p ≡ 1 (mod 2d). The rest of the proof is the same as the proof of statement 1.

Corollary 19. Let p be an odd prime that does not divide k, where k is even, and let d = gcd(p − 1, k). If n ≡ r (mod k), where 1 ≤ r ≤ k, then

α(p^{n}) = \begin{cases}(α(p) − 1)\frac{p^{n+k−1} − p^{r−1}}{p^{k} − 1} + 1, & if p ≡ d + 1 (mod 2d); \\ p^{n−1}α(p), & if p ≡ 1 (mod 2d). \end{cases}

4.2 Calculation of α(p)

We have already formulas that express α(p^{n}) in terms of α(p), for an odd prime p. To compute α(p), we will use the following result of Joly [6].

Proposition 20. Let K be a finite field with q elements, d_{i} be positive integers and b, a_{i} ∈ K, for i = 1, 2, …, t. If N(b, t) is the number of solutions of the diagonal equation given by a_{1}x_{1}^{d_{1}} + a_{2}x_{2}^{d_{2}} + ⋯ + a_{t}x_{t}^{d_{t}} = b in K^{t}, then

|N(b, t) − q^{t−1}| ≤ Aq^{\frac{t−1}{2}} ,

where A = (δ_{1} − 1) ⋯ (δ_{t} − 1), and δ_{i} = gcd(q − 1, d_{i}), for i = 1, 2, …, t.

A direct application of Proposition 20 is the following.

Corollary 21. Let p be a prime, b, c_{i} ∈ ℤ/pℤ for i = 1, 2, …, t, and k be a positive integer. If N(b, t) is the number of solutions in (ℤ/pℤ)^{t} of the diagonal equation c_{1}x_{1}^{k}+c_{2}x_{2}^{k}+⋯+c_{t}x_{t}^{k} = b, then

|N(b, t) − p^{t−1}| ≤ (k − 1)^{t}p^{\frac{t−1}{2}} .

Moreover, if p > (k − 1)^{\frac{2t}{t−1}} , then α(p) = p.

Proof. The first part is a direct consequence of Proposition 20. For the second part, if K = ℤ/pℤ, d_{i} = k, for i = 1, 2, …, t and δ_{i} = gcd(k, p − 1), then δ_{i} ≤ k and N(b, t) − p^{t−1} ≥ −(k − 1)^{t}p^{\frac{t−1}{2}} , which implies that N(b, t) ≥ p^{t−1} − (k − 1)^{t}p^{\frac{t−1}{2}} . The hypothesis that p > (k − 1)^{\frac{2t}{t−1}} yields N(b, t) > 0. Hence, for p > (k − 1)^{\frac{2t}{t−1}} , the diagonal equation c_{1}x_{1}^{k} + c_{2}x_{2}^{k} + ⋯ + c_{t}x_{t}^{k} = b has a solution, for all b ∈ ℤ/pℤ. It follows that α(p) = p.

As an example, for polynomials of the form c_{1}x^{k} + c_{2}y^{k}, we obtain α(p) = p, for every prime p > (k − 1)^{4}.

5 The polynomial x^{k} − y^{k} with k even

Throughout this section, let p be a prime and s be the highest nonnegative integer such that p^{s} divides k, where k is even. For the polynomial x^{k} − y^{k}, we can apply Proposition 4 (take x = y = 1), to obtain the following formula:

α(p^{n}) = \begin{cases}2^{n−s−2}α(2^{s+2}), & if p = 2 and n ≥ s + 2; \\ p^{n−s−1}α(p^{s+1}), & if p is odd and n ≥ s + 1. \end{cases}  (2)

We show the explicit calculation of α(2^{n}), for all n. Let α_{0} be the function associated with the polynomial x^{2^{s}} − y^{2^{s}}.

Lemma 22. For 1 ≤ n ≤ s + 2, the congruence x^{2^{s}} − y^{2^{s}} ≡ a (mod 2^{n}) has a solution if and only if a = 0, 1, 2^{n} − 1. Then α_{0}(2^{n}) = 3 for 2 ≤ n ≤ s + 2.

Proof. Let 2 ≤ n ≤ s + 2. If a ∈ {0, 1, 2, …, 2^{n} − 1}, then the congruence x^{2^{s}} ≡ a (mod 2^{n}) is solvable only for a = 0 and a = 1. Thus, the congruence x^{2^{s}} − y^{2^{s}} ≡ a (mod 2^{n}) has solution only for a = 0, 1, −1. Since −1 ≡ 2^{n} − 1 (mod 2^{n}), we obtain the desired result.

Theorem 23. Let α be the function associated with the polynomial x^{k} − y^{k}. If k = 2^{s}m, where s ≥ 1 and m is odd, then

α(2^{n}) = \begin{cases}2, & if n = 1; \\ 3, & if 1 < n ≤ s + 2; \\ 3 · 2^{n−s−2}, & if n > s + 2. \end{cases}

Proof. If the congruence x^{2^{s}m}−y^{2^{s}m} ≡ a (mod 2^{n}) is solvable, then the congruence x^{2^{s}}−y^{2^{s}} ≡ a (mod 2^{n}) is also solvable. Thus, α(2^{n}) ≤ α_{0}(2^{n}), for 2 ≤ n ≤ s + 2. Since 0, 1, 2^{n} − 1 ∈ A_{2^{n}} (for the polynomial x^{k} − y^{k}), we obtain α(2^{n}) = 3 for 2 ≤ n ≤ s + 2. For n > s + 2, it follows from (2) that α(2^{n}) = 2^{n−s−2}α(2^{s+2}) = 3 · 2^{n−s−2}.

6 Applications to particular polynomials

In this section, we will apply our results to find explicit formulas for α(p^{n}), where α is the function associated with the following polynomials: x^{4} + y^{4}, x^{4} − y^{4}, x^{5} + y^{5} and x^{6} + y^{6}.

Theorem 24. Let α be the function associated with the polynomial x^{4} + y^{4}. Then

α(p^{n}) = \begin{cases}\frac{4}{15}(2^{n−1} − 2^{r−1}) + 3, & if p = 2, n ≡ r (mod 4), where r = 2, 3, 4; \\ \frac{4}{15}(2^{n−1} − 1) + 2, & if p = 2 and n ≡ 1 (mod 4); \\ p^{n}, & if p ≡ 1 (mod 8), p ≠ 17, n ≥ 1; \\ 13 · 17^{n−1}, & if p = 17, n ≥ 1; \\ (p − 1)\frac{p^{n+3} − p^{r−1}}{p^{4} − 1} + 1, & if p ≢ 1 (mod 8), p ≠ 5, 13, 29, n ≡ r (mod 4), where 1 ≤ r ≤ 4; \\ \frac{1}{312}(5^{n+3} − 5^{r−1}) + 1, & if p = 5, n ≡ r (mod 4), where 1 ≤ r ≤ 4; \\ \frac{1}{3173}(13^{n+3} − 13^{r−1}) + 1, & if p = 13, n ≡ r (mod 4), where 1 ≤ r ≤ 4; \\ \frac{1}{33680}(29^{n+3} − 29^{r−1}) + 1, & if p = 29, n ≡ r (mod 4), where 1 ≤ r ≤ 4. \end{cases}

Proof. For p = 2, direct calculations show that |N_{2^{2}}| = 1, |N_{2^{3}}| = |N_{2^{4}}| = 3, and |N_{2^{5}}| = 0. Then from Proposition 8, we obtain the given formulas for α(2^{n}).

Now, from Corollary 21, it follows that α(p) = p, for all p > 81. For primes p < 81, we have α(5) = 3, α(13) = 10, α(17) = 13, α(29) = 22, and α(p) = p, for 31 ≤ p < 81.

Odd primes divide into 4 types depending on their residue upon division by 8. Observe that only those primes of the form 8m + 1 satisfy p ≡ 1 (mod 2d), where d = gcd(p − 1, 4). The rest of the proof follows from Theorem 18 and Corollary 19.

Theorem 25. If α is the function associated with the polynomial x^{5} + y^{5}, p is prime and n ≥ 1, then

α(p^{n}) = \begin{cases}5, & if p = 5 and n = 1; \\ 13 · 5^{n−2}, & if p = 5 and n ≥ 2; \\ 5 · 11^{n−1}, & if p = 11; \\ 19 · 31^{n−1}, & if p = 31; \\ 33 · 41^{n−1}, & if p = 41; \\ 49 · 61^{n−1}, & if p = 61; \\ p^{n}, & if p ≠ 5, 11, 31, 41, 61. \end{cases}

Proof. It follows, from Corollary 21 and direct computations, that α(p) = p for all p ≠ 11, 31, 41, 61, and α(11) = 5, α(31) = 19, α(41) = 33, α(61) = 49. Now we apply part 4 of Theorem 18 to obtain α(p^{n}) = p^{n−1}α(p), for all odd primes p ≠ 5, and n ≥ 1. This gives us the desired formulas for α(p^{n}), for all primes p ≠ 2, 5.

On the other hand, it is clear that the congruence x^{5} + y^{5} ≡ 0 (mod 5^{2}) has a nontrivial solution. From Proposition 4, it follows that α(5^{n}) = 5^{n−2}α(5^{2}), for all n ≥ 2. An easy computation shows that α(5) = 5 and α(5^{2}) = 13.

Finally, we apply Proposition 4 to obtain α(2^{n}) = 2^{n−1}α(2) = 2^{n}.

The following proposition shows us formulas for α(2^{n}) and α(3^{n}), where α is the function associated with x^{6} + y^{6}. These formulas are obtained by using the fact that 6 is an exponent of p = 2 and p = 3 in x^{6} + y^{6} by Propositions 14 and 16. Then we finish the proof by applying Proposition 8.

Proposition 26. Let α be the function associated with the polynomial x^{6}+y^{6}. Then α(2^{n}) = \frac{1}{63}(16 · 2^{n} + β_{i}) and α(3^{n}) = \frac{1}{364}(81 · 3^{n} + γ_{i}), where n ≡ i (mod 6), i = 0, 1, 2, 3, 4, 5, and the values β_{i} and γ_{i} are shown in Table 1.

\begin{matrix}i & β_{i} & γ_{i} \\ 0 & 47 & 283 \\ 1 & 94 & 849 \\ 2 & 125 & 363 \\ 3 & 61 & 361 \\ 4 & 59 & 355 \\ 5 & 55 & 337 \end{matrix}

Table 1: The values β_{i} and γ_{i}.

Before computing α(p^{n}) for primes p > 3 and n ≥ 1, we compute α(p). By Corollary 21 and direct computations, we obtain the following result.

Proposition 27. Let α be the function associated with the polynomial x^{6}+y^{6}. Then α(p) = p for all primes p, where p ∉ {7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 109, 139, 223}.

For p ∈ {7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 109, 139, 223}, Table 2 shows the values α(p).

\begin{matrix}p & 7 & 13 & 19 & 31 & 37 & 43 & 61 & 67 & 73 & 79 & 109 & 139 & 223 \\ α(p) & 3 & 5 & 10 & 16 & 19 & 29 & 51 & 56 & 61 & 66 & 91 & 116 & 186 \end{matrix}

Table 2: The values α(p).

The following proposition shows us a formula for computing α(p^{n}) in terms of α(p), where p > 3 is prime. This result is a direct application of Corollary 19.

Proposition 28. Let p > 3 be a prime, and α be the function associated with the polynomial x^{6} + y^{6}. If n ≡ r (mod 6), where 1 ≤ r ≤ 6, then

α(p^{n}) = \begin{cases}(α(p) − 1)\frac{p^{n+5} − p^{r−1}}{p^{6} − 1} + 1, & if p ≡ 3 (mod 4); \\ p^{n−1}α(p), & if p ≡ 1 (mod 4). \end{cases}

The following result shows a formula for α(p^{n}), where α is the function associated with x^{4} −y^{4}. To obtain this formula, we apply Equation (2), Corollary 21, Theorem 23, and direct computations.

Theorem 29. Let α be the function associated with the polynomial x^{4} − y^{4}. If p is a prime and n ≥ 1, then

α(p^{n}) = \begin{cases}2, & if p = 2, n = 1; \\ 3, & if p = 2, n = 2, 3; \\ 3 · 2^{n−4}, & if p = 2, n ≥ 4; \\ 3 · 5^{n−1}, & if p = 5; \\ 13 · 17^{n−1}, & if p = 17; \\ p^{n}, & if p is odd, p ≠ 5, 17. \end{cases}

7 Application to the modular Waring problem

Let α_{k,t} be the function associated with the polynomial x_{1}^{k} + ⋯ + x_{t}^{k}. Given n ∈ ℤ^{+}, we define γ(k, n) to be the least positive integer t such that α_{k,t}(n) = n, and γ(k) to be the least positive integer t such that α_{k,t}(n) = n, for all n ∈ ℤ^{+}. For every k, the integer γ(k) exists by the Hilbert-Waring theorem. We clearly have

γ(k) = max_{n∈ℤ^{+}} γ(k, n).

Moreover, since α_{k,t} is multiplicative,

γ(k) = max_{p,n} γ(k, p^{n}),

where p runs over all primes and n ≥ 1. The computation of γ(k, n) is called the modular Waring problem.

We are interested in comparing γ(k) and g(k), where g(k) is the least positive integer t such that every positive integer can be expressed as a sum of at most t k-th powers (see sequence \underline{A002804} in the On-Line Encylopedia of Integer Sequences).

The following three results, concerning the functions α_{2,j}, for j ∈ {1, 2, 3}, can be inferred from [3]:

i) α_{2,1}(n) = n if and only if n = 1 or n = 2,

ii) α_{2,2}(n) = n if and only if 4 ∤ n and n is not divisible by the square of any prime p ≡ 3 (mod 4),

iii) α_{2,3}(n) = n if and only if 8 does not divide n.

Lagrange four-square theorem implies that α_{2,4}(n) = n, for all n. Hence,

γ(2, n) = \begin{cases}1, & if n = 1, 2; \\ 2, & if n ≠ 1, 2; 4 ∤ n and p^{2} ∤ n for all primes p ≡ 3 (mod 4); \\ 3, & if 4 | n and 8 ∤ n; \\ 4, & if 8 | n. \end{cases}

It follows that γ(2) = 4.

Now let us consider the modular Waring problem for cubic powers. Let α_{3,t} be the function associated with x_{1}^{3} + ⋯ + x_{t}^{3}. Broughan [4] proved that

α_{3,2}(n) = \begin{cases}n, & if 7 ∤ n and 9 ∤ n; \\ \frac{5}{7}n, & if 7 | n and 9 ∤ n; \\ \frac{5}{9}n, & if 7 ∤ n and 9 | n; \\ \frac{25}{63}n, & if 7 | n and 9 | n. \end{cases}

Proposition 30. Let p be a prime and n be a positive integer. Then

α_{3,3}(p^{n}) = \begin{cases}3, & if p = 3 and n = 1; \\ 7 · 3^{n−2}, & if p = 3 and n ≥ 2; \\ p^{n}, & if p ≠ 3. \end{cases}

Proof. The triple (1, −1, 0) is a nontrivial solution of the congruence x^{3}+y^{3}+z^{3} ≡ 0 (mod p). It follows, from Corollary 5, that if p ≠ 3, then α_{3,3}(p^{n}) = p^{n−1}α_{3,3}(p), for all n. Note that gcd(3, p − 1) = 1 or 3. If gcd(3, p − 1) = 1, then there are p − 1 cubic residues modulo p, so α_{3,3}(p) = p. On the other hand, if gcd(3, p − 1) = 3 and p ≥ 11, then, from Theorem 12 we have

α_{3,3}(p) ≥ min (p, \frac{(2 · 3 − 1)(p − 1)}{3}) = p.

Therefore, α_{3,3}(p) = p. We conclude that α_{3,3}(p^{n}) = p^{n}, for all p ≠ 3, 7, n ≥ 1. When p = 7, we see that α_{3,3}(7) = 7, so α_{3,3}(7^{n}) = 7^{n}, for all n ≥ 1.

Finally, from Proposition 4, it follows that

α_{3,3}(3^{n}) = 3^{n−2}α(3^{2}),

for all n ≥ 3, and it is easily seen that α_{3,3}(3) = 3 and α_{3,3}(9) = 7. This finishes the proof.

The formula in the above proposition can be simplified as follows:

α_{3,3}(n) = \begin{cases}n, & if 9 ∤ n ; \\ \frac{7}{9}n, & if 9 | n. \end{cases}

It is not difficult to see that α_{3,4}(n) = n, for all n ∈ ℤ^{+}, which implies that γ(3) = 4.

Proposition 31. Let t be a positive integer, 1 ≤ t ≤ 15. If 16 divides an integer of the form x_{1}^{4} + x_{2}^{4} + ⋯ + x_{t}^{4}, then x_{i} is even for all i. Consequently, 4 is an exponent of p = 2 in the polynomial x_{1}^{4} + x_{2}^{4} + ⋯ + x_{t}^{4}.

Proof. We proceed by induction on t. The result is clear for t = 1. Let us assume that if 16 divides a sum of the form x_{1}^{4} + x_{2}^{4} + ⋯ + x_{t}^{4}, where 1 ≤ t < 15, then all x_{i}’s are even.

Suppose that 16 divides a sum of the form x_{1}^{4} + x_{2}^{4} + ⋯ + x_{t+1}^{4}. If all the x_{i}’s are odd, then x_{i}^{4} ≡ 1 (mod 16) for all i, so 16 divides t + 1, which is absurd. Thus, we can assume that x_{t+1} is even. It follows that 16 divides x_{1}^{4} + x_{2}^{4} + ⋯ + x_{t}^{4}, and the induction hypothesis implies that all the x_{i}’s are even.

With our techniques and the use of a computer program, it is not difficult to deduce the following result.

Proposition 32. Let t be an integer, 3 ≤ t ≤ 15, and α_{4,t} be the function associated with the polynomial x_{1}^{4} + x_{2}^{4} + ⋯ + x_{t}^{4}. Then

α_{4,t}(2^{n}) = \begin{cases}\frac{1}{15}(t · 2^{n} − 2t + 30), & if n ≡ 1 (mod 4) and 3 ≤ t ≤ 15; \\ \frac{1}{15}(t · 2^{n} − 4t + 60), & if n ≡ 2 (mod 4) and 3 ≤ t ≤ 15; \\ \frac{1}{15}(t · 2^{n} + 7t + 15), & if n ≡ 3 (mod 4) and 3 ≤ t ≤ 7; \\ \frac{1}{15}(t · 2^{n} − 8t + 120), & if n ≡ 3 (mod 4) and 8 ≤ t ≤ 15; \\ \frac{1}{15}(t · 2^{n} − t + 15), & if n ≡ 4 (mod 4) and 3 ≤ t ≤ 15. \end{cases}

Furthermore, if p is an odd prime and t ≥ 5, then α_{4,t}(p^{n}) = p^{n}, for all n ≥ 5.

In particular, when t = 15 in Proposition 32, we obtain α_{4,t}(2^{n}) = 2^{n}, for all n ≥ 1. Thus, we see that γ(4) = 15.

With the use of a computer program, we can compute γ(k) for small values of k. In Table 3, we compare γ(k) and g(k), for 2 ≤ k ≤ 9.

\begin{matrix}k & g(k) & γ(k) \\ 2 & 4 & 4 \\ 3 & 9 & 4 \\ 4 & 19 & 15 \\ 5 & 37 & 5 \\ 6 & 73 & 9 \\ 7 & 143 & 5 \\ 8 & 279 & 32 \\ 9 & 548 & 13 \end{matrix}

Table 3: Comparison of g(k) and γ(k), 2 ≤ k ≤ 9.

8 Acknowledgments

The authors thank the referee and editor for all the suggestions that helped to improve this paper.

References

[1] A. Alnaser and T. Cochrane, Waring’s number mod m, J. Number Theory 128 (2008), 2582–2590.

[2] A. Alnaser, T. Cochrane, M. Ostergaard, and C. Spencer, Waring numbers for diagonal congruences, Rocky Mountain J. Math. 50 (2020), 825–838.

[3] F. Arias, J. Borja, and L. Rubio, Counting integers representable as images of polynomials modulo n, J. Integer Sequences 22 (2019), Article 19.6.7.

[4] K. Broughan, Characterizing the sum of two cubes, J. Integer Sequences 6 (2003), Article 03.4.6.

[5] J. Harrington, L. Jones, and A. Lamarche, Representing integers as the sum of two squares in the ring ℤ_{n}, J. Integer Sequences 17 (2014), Article 14.7.4.

[6] J. Joly, Equations et variétés algébriques sur un corps fini, Enseign. Math. 19 (1973), 1–117.

[7] M. B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets, Springer, 1996.

[8] C. Small, Waring’s problem mod n, Amer. Math. Monthly 84 (1977), 12–25.

2020 Mathematics Subject Classifications: Primary 11A07; Secondary 11B13, 11B83, 11P05. Keywords: polynomial congruence, modular Waring problem, additive number theory.

(Concerned with sequence \underline{A002804})

Received April 19 2023; revised versions received April 24 2023; May 16 2023; August 24 2023. Published in Journal of Integer Sequences, August 28 2023.

Return to Journal of Integer Sequences home page.