INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 4 (2004), #A20

SUMS OF THE FORM 1/x_{1}^{k} + ⋯ + 1/x_{n}^{k} MODULO A PRIME

Ernie Croot ^{1}

Department of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332

                         ecroot@math.gatech.edu

Received: 5/24/04, Revised: 10/11/04, Accepted: 10/21/04, Published: 11/1/04

Abstract

Using a sum-product result due to Bourgain, Katz, and Tao, we show that for every 0 < ϵ ≤ 1, and every integer k ≥ 1, there exists an integer N = N(ϵ, k), such that for every prime p and every residue class a (mod p), there exist positive integers x_{1}, ..., x_{N} ≤ p^{ϵ} satisfying

a ≡ \frac{1}{x_{1}^{k}} + ⋯ + \frac{1}{x_{N}^{k}} (mod p).

I. Introduction

In the monograph [2], among the many questions asked by Erdős and Graham was the following: Is it true that for every 0 < ϵ ≤ 1 there exists a number N such that for every prime number p, every residue class a (mod p) can be expressed as a ≡ 1/x_{1}+⋯+1/x_{N} (mod p), where x_{1}, ..., x_{k} are positive integers ≤ p^{ϵ}? This question was answered in the affirmative by Shparlinski [6] using a result due to Karatsuba [5] (actually, a simplified version of Karatsuba’s result, due to Friedlander and Iwaniec [3]).

A natural question that one can ask, and which Shparlinski recently posed to me, was whether this result can be extended to reciprocal powers. Unfortunately, in this case, the methods of Karatsuba do not give a bound on N (at least not using an obvious modification of his argument). Fortunately, there is a powerful result due to Bourgain, Katz, and Tao [1] which can be used to bound certain exponential sums, and which can be used to solve our problem:

Theorem 1 (Bourgain, Katz, Tao) Let A be a subset of a finite field ℤ/pℤ. If p^{δ} < |A| < p^{1−δ} for some δ > 0, then |A + A| + |A · A| ≥ c|A|^{1+θ}, where θ = θ(δ) > 0 and c = c(δ) > 0.

1Partially supported by an NSF grant.

Using this result, we prove the following theorem, which is just a restatement of the problem posed by Shparlinski:

Theorem 2 For every 0 < ϵ ≤ 1, and every integer k ≥ 1, there exists an integer N = N(ϵ, k) such that for every prime p ≥ 2, and every integer 0 ≤ a ≤ p − 1, there exist integers x_{1}, ..., x_{N} such that 1 ≤ x_{i} ≤ p^{ϵ}, and

a ≡ \frac{1}{x_{1}^{k}} + ⋯ + \frac{1}{x_{N}^{k}} (mod p).

Comments. A more general theorem can perhaps be proved here, as was suggested to me by Shparlinski in an email. Basically, suppose S = S(p) ⊆ {1, ..., p − 1} is an infinite sequence of sets, indexed by primes p satisfying the following two conditions

1. The sets S(p) are multiplicative in the sense that 1 ∈ S, and if s, t ∈ S satisfy st ≤ p − 1, then st ∈ S; and,

2. There exists an absolute constant 0 < θ ≤ 1 so that for every 0 < ϵ ≤ 1, and p sufficiently large, the set S(p) contains at least p^{ϵθ} elements ≤ p^{ϵ}.

Then, there exists an integer J = J(ϵ) ≥ 1 such that for every sufficiently large prime p, and for every residue class r (mod p), there exist integers x_{1}, ..., x_{J} ∈ S(p), all of size at most p^{ϵ}, such that

r ≡ \frac{1}{x_{1}} + ⋯ + \frac{1}{x_{J}} (mod p),

An example of a set S = S(p) satisfying the properties above, is the set of positive integers ≤ p − 1 having no prime divisors greater than log^{2} p. It is well known that the number of elements in this multiplicative set up to p^{ϵ} is at least p^{ϵ/2+o(1)} (see, for example, [4])

II. Proof of Theorem 2

First, we note that it suffices to prove the result only for sufficiently large primes p, as we may enlarge N = N(ϵ, k) as needed so that the theorem holds for all prime p < p_{0}, for some p_{0}. We also may assume 0 < ϵ < ϵ_{0}(k), for any function ϵ_{0}(k) that we might happen to need, since if the conclusion of the theorem holds for these smaller values of ϵ, then it holds for any larger value of ϵ. In fact, we will use ϵ_{0}(k) = 1/5k in the proof of our theorem.

Let 0 < β < 1/5k be some parameter, to be chosen later, and let u be the largest integer less than β^{−1}/(2k), and consider the set

S = \{\frac{1}{p_{1}^{k}} + ⋯ + \frac{1}{p_{u}^{k}} (mod p) : 2 ≤ p_{1} < ⋯ < p_{u} ≤ p^{β}, p_{i} prime\} ,

which will be non-empty for p sufficiently large. We claim that

|S| > \frac{p^{1/(2k)−β}}{u! log^{u} p}  (1)

for p sufficiently large, which would follow from the prime number theorem if we had that all the sums in S were distinct modulo p. To see that they are, suppose that we had

\frac{1}{p_{1}^{k}} + ⋯ + \frac{1}{p_{u}^{k}} ≡ \frac{1}{q_{1}^{k}} + ⋯ + \frac{1}{q_{u}^{k}} (mod p),

where the left and right side of the congruence are elements of S, where the p_{1}, ..., p_{k} and q_{1}, ..., q_{k} are increasing sequences. Multiplying through by (p_{1} ⋯ p_{u}q_{1} ⋯ q_{u})^{k} on both sides and moving terms to one side of the congruence, we get that

∑_{j=1}^{u} ((q_{1} ⋯ q_{u})^{k} ∏_{{i=1 \atop i≠j}}^{u} p_{i}^{k} − (p_{1} ⋯ p_{u})^{k} ∏_{{i=1 \atop i≠j}}^{u} q_{i}^{k}) ≡ 0 (mod p).  (2)

Since all the terms in the sum are smaller than p^{(2u−1)kβ} < p/u (for p sufficiently large), we deduce that if (2) holds, then

∑_{j=1}^{u} ((q_{1} ⋯ q_{u})^{k} ∏_{{i=1 \atop i≠j}}^{u} p_{i}^{k} − (p_{1} ⋯ p_{u})^{k} ∏_{{i=1 \atop i≠j}}^{u} q_{i}^{k}) = 0;

and so,

\frac{1}{p_{1}^{k}} + ⋯ + \frac{1}{p_{u}^{k}} = \frac{1}{q_{1}^{k}} + ⋯ + \frac{1}{q_{u}^{k}} .

It is obvious then that the p_{i} = q_{i}, and (1) now follows.

Let S_{0} = S, and consider the sequence of subsets of ℤ/pℤ, which we denote by S_{1}, S_{2}, ..., where

S_{i+1} = \{ \begin{matrix}S_{i} + S_{i}, & if |S_{i} + S_{i}| > |S_{i}S_{i}|; and \\ S_{i}S_{i}, & if |S_{i} + S_{i}| ≤ |S_{i}S_{i}|. \end{matrix}

We continue constructing this sequence until we reach the set S_{n} satisfying

|S_{n}| > p^{2/3}.  (3)

Using Theorem 1 we can produce a non-trivial upper bound on the size of n for β < 1/5k: Let δ = 1/4k, and let c = c(δ), θ = θ(δ) be as in Theorem 1. Then, for p sufficiently large, we will have

p^{δ} < |S_{0}| = |S| < p^{1−δ},

and the same inequality will hold for S_{1}, S_{2}, ..., S_{n−1}. Now, applying Theorem 1, we deduce that

|S_{i+1}| > c|S_{i}|^{1+θ};

and so,

|S_{1}| > c|S_{0}|^{1+θ}, and for j = 2, ..., n, |S_{j}| > c^{1+(1+θ)^{j−1}}|S_{0}|^{(1+θ)^{j}}.

From this inequality and (3) , we deduce that

(\frac{1}{2k} − β) (1 + θ)^{n} + o(1) > \frac{2}{3},

where the o(1) tends to 0 as p tends to infinity; and so, since β < 1/5k, our sequence S_{0}, S_{1}, ..., S_{n} finishes with

n < \frac{log(3k)}{log(1 + θ)} + 1

for p sufficiently large.

Now, every element of S_{0} is a sum of at most u terms; each element of S_{1} is a sum of at most u^{2} terms; and, by an induction argument, each element of S_{n} is a sum of at most u^{2^{n}} terms. Also, each element of S_{n} is a sum of terms of the form 1/q_{1}^{k} ⋯ q_{2^{n}}^{k}, where q_{1} ⋯ q_{2^{n}} ≤ p^{2^{n}β}.

Now, let β = ϵ/2^{n+1}. If ϵ < 1/5k, then this value of β < 1/5k (recall we said that ϵ is allowed to be bounded from above by a function of k). Let h

h = u^{2^{⌈^{\frac{log(3k)}{log(1+θ)}}⌉}},

and define

T = \{\frac{1}{q_{1}^{k}} + ⋯ + \frac{1}{q_{h}^{k}} (mod p) : 2 ≤ q_{1}, ..., q_{h} ≤ p^{ϵ/2}\}

Here, q_{1}, ..., q_{h} are not restricted to being prime numbers. Since |T | ≥ |S_{n}|, we have that |T | > p^{2/3} for p sufficiently large.

Now we use the following simple lemma, which has appeared in many works before, and uses a standard bilinear exponential sums technique:

Lemma 1 Suppose that T ⊆ ℤ/pℤ satisfies |T | > p^{1/2+β}. Then, every residue class modulo p contains an integer of the form x_{1} + ⋯ + x_{J}, where the x_{1}, ..., x_{J} are all of the form t_{1}t_{2}, where t_{1}, t_{2} ∈ T, and where J = ⌊2(1 + 2β)/β⌋ + 1.

Proof of the Lemma. First, we consider the exponential sums

h(a) = ∑_{t∈T} e (\frac{at}{p}) ,

and

f(a) = ∑_{t_{1},t_{2}∈T} e (\frac{at_{1}t_{2}}{p} ) .

We have from Parseval’s identity and the Cauchy-Schwarz inequality that for a ≢ 0 (mod p),

|f(a)| ≤ ∑_{t_{1}∈T} |∑_{t_{2}∈T} e (\frac{at_{1}t_{2}}{p} )|

≤ (∑_{t_{1}∈T} 1)^{1/2} (∑_{t_{2}∈T} |h(at_{2})|^{2})^{1/2}
= p^{1/2}|T | ≤ |f(0)|^{(1+β)/(1+2β)}.

Now, if we let J be the least integer greater than

2 (1 − \frac{1 + β}{1 + 2β} )^{−1} = \frac{2(1 + 2β)}{β},

then we have that for a ≢ 0 (mod p),

|f(a)|^{J} < |f(0)|^{J(1+β)/(1+2β)} < |f(0)|^{J}|f(0)|^{−Jβ/(1+2β)}
≤ |f(0)|^{J−2} ≤ \frac{|f(0)|^{J}}{p} .

Thus, given an integer r, the number

#(x_{1}, ..., x_{J} : x_{i} = t_{1}t_{2}; t_{1}, t_{2} ∈ T; and x_{1} + ⋯ + x_{J} ≡ r (mod p))

= \frac{1}{p} ∑_{a=0}^{p−1} f(a)^{J}e(−ar/p) ≥ \frac{f(0)}{p} − \frac{1}{p} ∑_{1≤a≤p−1} |f(a)|^{J}

≥ \frac{f(0)}{p} − \frac{(p − 1)f(0)}{p^{2}} > 0.

This proves the lemma. □

From this lemma, we deduce that for every residue class r modulo p, there exist integers t_{1}, ..., t_{16}, such that

r ≡ t_{1}t_{2} + t_{3}t_{4} + ⋯ + t_{15}t_{16} (mod p),

where t_{1}, ..., t_{16} ∈ T. This sum can be expressed as a sum of at most 16h^{2} terms of the form 1/(qq′)^{k}, where q, q′ < p^{ϵ/2}. This then proves the theorem, since h depends only on k and ϵ.

Acknowledgements

I would like to thank Igor Shparlinski for the interesting problem, which is the one solved by Theorem 2.

References

[1] J. Bourgain, N. Katz, and T. Tao, A Sum-Product Estimate in Finite Fields, and Applications, Preprint on the Arxives.

[2] P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, Univ. Genève, Geneva, 1980.

[3] J. Friedlander and H. Iwaniec, Analytic Number Theory (Kyoto, 1996), Cambridge University Press, Cambridge, 1997.

[4] A. Granville, Smooth Numbers: Computational Number Theory and Beyond, MSRI Workshop Notes.

[5] A. A. Karatsuba, Fractional Parts of Functions of a Special Form, Izv. Ross. Akad. Nauk Ser. Mat. 59 (1995), 61-80.

[6] I. Shparlinski, On a Question of Erdős and Graham, Arch. Math. (Basel) 78 (2002), 445-448.