ON THE DISTRIBUTION OF EXPONENTIAL SUMS

Sergei V. Konyagin

Department of Mechanics and Mathematics, Moscow State University, Moscow 119899, Russia

                              kon@nw.math.msu.su

Vsevolod F. Lev^{1}

Institute of Mathematics, Hebrew University, Jerusalem 91904, Israel

                             seva@math.huji.ac.il

Received: 9/3/99, Accepted: 10/12/99, Published: 5/19/00

Abstract

We discuss three problems of the following kind: given a set A ⊆ 𝔽_{p} of n := |A| residues modulo a prime p, how are the absolute values |S_{A}(z)| of the corresponding exponential sums

S_{A}(z) := ∑_{a∈A} e^{2πi \frac{az}{p}}; z ∈ 𝔽_{p}

distributed in the interval [0, n]?

1. Introduction

One of the most popular tools in number theory, exponential sums, are usually studied from the following point of view only: given a particular set A of n = |A| residues, integers, or real numbers, show that the absolute values of the exponential sums corresponding to this set are small. In this note we adopt a more general standpoint, trying to understand the distribution of the absolute values of the exponential sums in the interval [0, n]. Moreover, we are interested not in the sets A of some special arithmetic structure, but rather in the common properties of the exponential sums, independent of the structure of A. This is primarily a survey note: we review several known results and pose some new problems.

We stick with the case of residues modulo a prime p. For a set A ⊆ 𝔽_{p} of n = |A| residues we write

S_{A}(z) := ∑_{a∈A} e^{2πi \frac{az}{p}}; z ∈ 𝔽_{p}.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 0 (2000), #A01 2

(More generally, one can consider character sums in any locally compact Abelian group. Local compactness implies the existence of Haar measure on the group of characters, and we can ask “how many” characters with a given property are there.) To avoid trivialities, we often assume tacitly that 2 ≤ n ≤ p − 1.

1Supported in part by the Edmund Landau Center for Research in Mathematical Analysis and Related Areas, sponsored by the Minerva Foundation (Germany)

The basic observation is that 0 < |S_{A}(z)| ≤ n and moreover, |S_{A}(z)| = n if and only if z = 0. (The reason why S_{A}(z) is not 0 is that it can be considered as a polynomial of a pth root of unity, and this polynomial is not divisible by the minimal polynomial x^{p−1} +⋯+x+1.) Furthermore, Parseval’s identity gives

∑_{z∈𝔽_{p}} |S_{A}(z)|^{2} = np.  (1)

Below we address the following three questions.

1) As we have noticed, |S_{A}(z)| are distinct from 0, but how close to 0 can they be?

2) How many of the p sums |S_{A}(z)| can be close to 0?

3) How many of the p sums |S_{A}(z)| can be close to n?

(The answer to the missed question “How large |S_{A}(z)| can be?” is immediate: it can be equal to n, if z = 0, and plainly the next largest value is | sin(πn/p)/ sin(π/p)|, attained when A is an arithmetic progression (mod p).)

We discuss these three questions in Sections 2 – 4, respectively.

2. How Small Can Exponential Sums Be?

The first question of this sort was probably first raised in 1975 by Gerry Myerson (see [M86]), who introduced the function f(n, N), the least absolute value of a sum of n Nth roots of unity. Myerson allowed the roots of unity to be equal and proved several estimates for the case of N even. In this note we confine ourselves to N prime and require the roots to be pairwise distinct.

Theorem 1 Suppose that A ⊆ 𝔽_{p} is a set of n = |A| ∈ [3, p − 1] residues (mod p), and let z ∈ 𝔽_{p}^{×}. Then

|S_{A}(z)| > n^{− \frac{p−3}{4}} .

Proof. For any fixed z_{0} ∈ 𝔽_{p}^{×}, the sum S_{A}(z_{0}) is an algebraic integer of the norm ∏_{z∈𝔽_{p}^{×}} S_{A}(z). This product is, therefore, at least 1 in absolute value, whence by the arithmetic-geometric means inequality and (1) we have

1 ≤ ∏_{z∈𝔽_{p}^{×}} |S(z)|^{2} = |S_{A}(z_{0})|^{4} _{∏_{z∈𝔽_{p}^{×}} ; z≠±z_{0}}|S(z)|^{2}

≤ |S_{A}(z_{0})|^{4} (\frac{1}{p − 3}_{∑_{z∈𝔽_{p}^{×}} ; z≠±z_{0}}|S(z)|^{2})^{p−3}

< |S_{A}(z_{0})|^{4} (\frac{n(p − n)}{p − 3})^{p−3}

≤ n^{p−3} |S_{A}(z_{0})|^{4}.

□

On the other hand, we were able to prove the following.

Theorem 2 For any n = 2^{k} < p/20 (where k is a positive integer) there exists A ⊆ 𝔽_{p} of the cardinality n such that

|S_{A}(1)| < n^{− \frac{ln p}{2 ln 2}} .

Proof. Let p′ = (p − 1)/2 and define A to be the set of all the subset sums of

{p′ + 1, p′ + 2, p′ + 4, …, p′ + 2^{k−1}} ⊆ 𝔽_{p}.

We first show that all these subset sums are distinct, and therefore |A| = 2^{k}.

We assume that

∑_{i∈I}(p′ + 2^{i}) ≡ ∑_{j∈J}(p′ + 2^{j}) (mod p)  (2)

for two subsets I, J ⊆ {0, …, k − 1} and we prove that I = J. Define ξ := ∑_{i∈I} 2^{i} and η := ∑_{j∈J} 2^{j}. Then

0 ≤ ξ, η, |I|, |J| ≤ 2^{k} − 1 < p/20

and (2) implies

\begin{aligned}2ξ − |I| & ≡ 2η − |J| (mod p), \\ 2ξ − |I| & = 2η − |J|. \end{aligned}

Next, it is easily seen that

\begin{aligned}|I| & = ξ − ⌊\frac{ξ}{2}⌋ − ⌊\frac{ξ}{4}⌋ − …, \\ |J| & = η − ⌊\frac{η}{2}⌋ − ⌊\frac{η}{4}⌋ − …, \end{aligned}

whence

ξ + ⌊\frac{ξ}{2}⌋ + ⌊\frac{ξ}{4}⌋ + ⋯ = η + ⌊\frac{η}{2}⌋ + ⌊\frac{η}{4}⌋ + ….

As x + ⌊x/2⌋ + ⌊x/4⌋ + … is a strictly increasing function of x, we obtain ξ = η and therefore I = J.

It follows that

S_{A}(1) = ∏_{j=0}^{k−1} (1 + e^{2πi \frac{p′+2^{j}}{p}} ) ,

and the absolute value of this product is easy to estimate:

|S_{A}(1)| = 2^{k} ∏_{j=0}^{k−1} | cos π \frac{p − 1 + 2^{j+1}}{2p} |

= 2^{k} ∏_{j=1}^{k} | sin \frac{π}{2p} (2^{j} − 1) |

< (\frac{π}{p} )^{k} 2^{\frac{k(k+1)}{2}}

= n^{−^{\frac{ln(p/π\sqrt{2})}{ln 2}} + \frac{ln n}{2 ln 2}}

< n^{− \frac{ln p}{2 ln 2}} .

□

It is clear from the proof that ln p/(2 ln 2) in the exponent can be replaced with (1 − ε) ln p/ ln 2 for any positive ε. However, the gap between the estimates of Theorems 1 and 2 makes refinements of this sort senseless.

3. How Many Small Sums Are There?

Suppose that Z ⊆ 𝔽_{p} is a set of residues such that |S_{A}(z)| is “small” for all z ∈ Z. Then the sum ∑_{z∈Z} |S_{A}(z)|^{2} is small also. We normalize this sum letting

G(Z) := \frac{1}{|Z|} ∑_{z∈Z} |S_{A}(z)|^{2}.

A way to express the fact that not too many of the exponential sums are small is to bound G(Z) from below for |Z| large enough. As G(𝔽_{p}) = n by (1), one could expect that G(Z) ≫ n^{c} with a positive constant c and assuming that |Z| is large. This, however, is not the case. In fact, it is easy to show (see Theorem 5 below) that for any ε ∈ (0, 1), any positive integer n, and sufficiently large p, there exist A and Z with |A| = n and |Z| ≥ (1 − ε)p such that G(Z) ≤ 1/ε. Moreover, there is no δ > 0 such that G(Z) ≥ δ holds for all A, Z ⊆ 𝔽_{p} with |Z| ≥ p/2 (see Theorem 6). It is reasonable to expect that G(Z) ≫ n^{−δ} for any δ > 0 and |Z| > δp; however, the estimate we were able to prove is considerably weaker.

Theorem 3 Let Z ⊆ 𝔽_{p}, and suppose that |Z| ≥ (1 − ε)p, where ε ∈ (0, 1). Then

G(Z) > \frac{1}{e} n^{− \frac{ε}{1−ε}} .

Proof. Using the inequality between arithmetic and geometric means, we get

(G(Z))^{|Z|} ≥ ∏_{z∈Z} |S_{A}(z)|^{2} = ∏_{z∈𝔽_{p}} |S_{A}(z)|^{2} ∏_{z∉Z} |S_{A}(z)|^{−2}.

The first product in the right-hand side is |S_{A}(0)|^{2} = n^{2} times the norm of a non-zero algebraic integer, whence

(G(Z))^{|Z|} > ∏_{z∉Z} |S_{A}(z)|^{−2}

and therefore using the arithmetic-geometric means inequality once again and taking into account (1) we obtain

(G(Z))^{−|Z|} < (\frac{1}{p − |Z|} ∑_{z∉Z} |S_{A}(z)|^{2})^{p−|Z|} < (\frac{np}{p − |Z|})^{p−|Z|} ,

G(Z) > (\frac{np}{p − |Z|})^{− \frac{p−|Z|}{|Z|}} .  (3)

Write α = (p − |Z|)/|Z|. Then

(\frac{p}{p − |Z|})^{− \frac{p−|Z|}{|Z|}} = (1 + \frac{1}{α})^{−α} > e^{−1},

and the result follows from (3) since

\frac{p − |Z|}{|Z|} ≤ \frac{ε}{1 − ε}.

□

A continuous analog of the quantity G(Z) was considered by Pichorides, who proved the following.

Theorem 4 ([P80, Lemma 1]) Let S(z) = 1 + ∑_{j=1}^{k} a_{j}e^{2πijz}, where a_{j} are real coefficients. For a set Z ⊆ [0, 1) of measure μ(Z) > 0 define

G_{1}(Z) := \frac{1}{μ(Z)} ∫_{Z} |S(z)| dz.

Suppose that μ(Z) < 1 and let Z̄ be the complement of Z in [0, 1). Then

(G_{1}(Z))^{μ(Z)} (G_{1}(Z̄))^{μ(Z̄)} ≥ 1.

We now show that G(Z) can be rather small even for |Z| large.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 0 (2000), #A01 6

Theorem 5 For any ε ∈ (0, 1), any positive integer n, and p sufficiently large, there exist A, Z ⊆ 𝔽_{p} such that |A| = n, |Z| ≥ (1 − ε)p, and G(Z) ≤ 1/ε. Proof. Consider the trigonometric polynomial

P (x) = ∑_{j=0}^{n−1} e^{2πijx}.

For 0 < x < 1/2 we have

|P (x)| = |\frac{e^{2πinx} − 1}{e^{2πix} − 1}| = \frac{| sin(πnx)|}{sin(πx)} ≤ \frac{1}{sin(πx)} < \frac{1}{2x},

whence

∫_{ε/2}^{1/2} |P (x)|^{2}dx < ∫_{ε/2}^{1/2} \frac{dx}{4x^{2}} = \frac{1}{2ε} − \frac{1}{2}.  (4)

Denote

E = [ε/2, 1 − ε/2]

and

E_{δ} = [ε/2 − δ, 1 − ε/2 + δ]

for δ > 0. By (4),

∫_{E} |P (x)|^{2}dx = 2 ∫_{ε/2}^{1/2} |P (x)|^{2}dx < \frac{1}{ε} − 1,

and therefore for sufficiently small δ > 0 we have

∫_{E_{δ}} |P (x)|^{2}dx < \frac{1}{ε} − 1.  (5)

Let A = {0, …, n − 1}. For any p put Z = {z : z/p ∈ E_{δ}}, so that

|Z| ≥ (1 − ε)p  (6)

for p large enough. Also,

lim_{p→∞} ∑_{z∈Z} |S_{A}(z)|^{2}/p = ∫_{E_{δ}} |P (x)|^{2}dx,

and it follows from (5) that for sufficiently large p

∑_{z∈Z} |S_{A}(z)|^{2} < p (\frac{1}{ε} − 1) .  (7)

Inequalities (6) and (7) readily imply the required estimate G(Z) ≤ 1/ε. □ The following theorem is the main result of [K97].

Theorem 6 (cf. [K97]) For any δ > 0 there exist a prime number p and sets A, Z ⊆ 𝔽_{p} such that |Z| > p/2 and G(Z) < δ.

Sketch of proof. The main part of the proof is a construction of a trigonometric polynomial P (x) = ∑_{a∈A} e^{2πiax} (where A is a finite set of integers) and a set E ∈ [0, 1] such that E is the union of finitely many segments,

μ(E) > 1/2,  (8)

and

∫_{E} |P (x)|^{2}dx < δ/2.  (9)

Once P and E are constructed, it is easy to complete the proof using the same kind of argument as in Theorem 5.

We can assume that δ < 1. Let η_{0}, η_{1}, … be independent random variables, distributed uniformly in [0, 1]. We define ξ_{j} = 2 cos(πη_{j}) and ψ_{j} = ln |ξ_{j}|, and we observe that ψ_{j} are independent and satisfy

Eψ_{j} = 0, E|ψ_{j}|^{3} < ∞.

It follows from the Berry-Essen theorem (see [B76, Theorem 12.4]) that there exists a constant C > 0 such that for any positive integer m

Pr (∑_{j=0}^{m−1} ψ_{j} ≤ C) > 1/2  (10)

and moreover,

Pr (− ln(4/δ) ≤ ∑_{j=0}^{m−1} ψ_{j} ≤ C) < δ/(4e^{2C})  (11)

for m sufficiently large.

We denote by (Ω, ν) the probability space and by F ⊂ Ω the event ∑_{j=0}^{m−1} ψ_{j} ≤ C. By (10),

ν(F) > 1/2  (12)

and from (11) (see [K97] for details)

∫_{F} exp (∑_{j=0}^{m−1} ψ_{j}) dν < δ/2,

or equivalently

∫_{F} ∏_{j=0}^{m−1} |ξ_{j}|dν < δ/2.  (13)

Using weak convergence of the distribution function of the random vectors (2 cos(2πx), 2 cos(2πlx), …, 2 cos(2πl^{m−1}x)) to the distribution function of (ξ_{0}, ξ_{1}, …, ξ_{m−1}) as l → ∞ (cf. [K97])), we get weak convergence of the distribution function of ∏_{j=0}^{m−1} 2 cos(2πl^{j}x) to the distribution function of ∏_{j=0}^{m−1} ξ_{j} as l → ∞. Therefore, for the 2^{m}-term trigonometric polynomial

P (x) = ∏_{j=0}^{m−1} (1 + e^{2πil^{j}x})

and for the set

E = {x ∈ [0, 1] : |P (x)| ≤ e^{C}},

using the identity

|P (x)| = ∏_{j=0}^{m−1} |2 cos(πl^{j}x)|

one can deduce from (12) and (13) the required inequalities (8) and (9), provided that l is large enough. □

Analysis of the proof shows that if n is a power of 2, then one can have G(Z) ≪ (ln n)^{−1/2} with |Z| > p/2 and G(Z) ≪ exp(−c(α)(ln n)^{1/2}) with |Z| ≥ αp, 0 < α < 1/2. Also, for arbitrary n ≥ 2 we can give examples with the same estimates for G(Z) under weaker restrictions for |Z|: G(Z) ≪ (ln n)^{−1/2} with |Z| > p/4 and G(Z) ≪ exp(−c(α)(ln n)^{1/2}) with |Z| ≥ αp, 0 < α < 1/4.

4. Large Exponential Sums

For exponential sums corresponding to a set A of integers, a rather precise estimate for the number of “large” sums was obtained by Yudin in [Y73]. Yudin proved that

mes \{z ∈ [0, 1): |S_{A}(z)| > (1 − ε)n\} ≤ \frac{2\sqrt{6}}{π} \frac{1}{n} ε^{1/2}(1 + o(1)),  (14)

where

S_{A}(z) = ∑_{a∈A} e^{2πiaz}; z ∈ ℝ

and assuming that n → ∞ and ε = o(1). Equality is attained when A is an arithmetic progression. In [B99], Besser replaced the assumption ε = o(1) by ε < c with an absolute constant c > 0; this required numerous fresh ideas and the final result differs considerably from (14).

Yudin’s argument was based on a “rearrangement theorem” due to Hardy and Littlewood. In [L00, Theorem 1], the second of the present authors was able to obtain residue analogs of the results of Hardy and Littlewood, which allowed him to extend Yudin’s theorem onto the residues case.

We now return back to our original notation, assuming A ⊆ 𝔽_{p} and z ∈ 𝔽_{p}. It turns out that a convenient way to measure the number of large exponential sums is provided by the function

T_{A}(φ) := {z ∈ 𝔽_{p}^{×}: |S_{A}(z)| > n cos φ}; 0 ≤ φ ≤ π/2.

Evidently, T_{A}(φ) is piecewise constant, monotonically increasing, and satisfies T_{A}(0) = 0 and T_{A}(π/2) = p − 1. A non-trivial property of T_{A}(φ) which explains why it arises naturally in this context is its sup-additivity, expressed in the following lemma.

Lemma 1 ([L00, Lemma 1]) Suppose that φ_{1}, φ_{2} ≥ 0 and φ_{1} + φ_{2} ≤ π/2. Then

T_{A}(φ_{1} + φ_{2}) ≥ min{T_{A}(φ_{1}) + T_{A}(φ_{2}), p − 1}.

(A parallel lemma for sets of integers is implicit in [Y73].)

Assume for a moment that the assertion of the lemma can be strengthened to

T_{A}(φ_{1} + φ_{2}) ≥ T_{A}(φ_{1}) + T_{A}(φ_{2}).  (15)

By induction, it follows then that T_{A}(jφ_{0}) ≥ jT_{A}(φ_{0}) provided jφ_{0} ≤ π/2. Choosing j = ⌊φ/φ_{0}⌋ and taking into account that T_{A}(φ) ≥ T_{A}(jφ_{0}) as T_{A} is increasing, we obtain

Corollary 1 ([L00, Lemma 2]) Suppose that 0 < φ, φ_{0} ≤ π/2. Then

T_{A}(φ) ≥ ⌊\frac{φ}{φ_{0}} ⌋ T_{A}(φ_{0}).

Though it can be shown that (15) does not hold in general, Corollary 1 is true and is established in [L00]. In conjunction with a rearrangement theorem for residues, it was used to prove the following analog of (14).

Theorem 7 ([L00, Theorem 5]) For any set A ⊆ 𝔽_{p} of n = |A| ≥ 4 residues modulo a prime p and any φ ∈ [0, π/6] we have

T_{A}(φ) ≤ \frac{2\sqrt{3}}{π} \frac{p}{n} φ (1 + n^{−2})(1 + 2φ^{2/3}).

This theorem is sharp in the sense that equality is attained asymptotically (for n → ∞ and φ → 0) if A is an arithmetic progression modulo p.

We conclude by outlining the proof of Theorem 7.

Sketch of proof. For brevity we drop below the subscript A in S_{A}(z) and T_{A}(φ), and we define

A_{0} := {0, …, n − 1}, S_{0}(z) := S_{A_{0}}(z), T_{0}(z) := T_{A_{0}}(z).

For k ≥ 1 consider the moments

\frac{1}{p} ∑_{z∈𝔽_{p}} |S(z)|^{2k} and \frac{1}{p} ∑_{z∈𝔽_{p}} |S_{0}(z)|^{2k}.

The former is the number of solutions of the equation a_{1} + ⋯ + a_{k} = a′_{1} + ⋯ + a′_{k} in the variables a_{i}, a′_{i} ∈ A, the latter is the number of solutions of the same equation in the variables a_{i}, a′_{i} ∈ A_{0}. By [L00, Theorem 1], the number of solution is maximized when the variables range over an arithmetic progression; thus,

∑_{z∈𝔽_{p}} |S(z)|^{2k} ≤ ∑_{z∈𝔽_{p}} |S_{0}(z)|^{2k},

and partial integration allows one to rewrite it as

∫_{0}^{π/2} T (φ) cos^{2k−1} φ sin φ dφ ≤ ∫_{0}^{π/2} T_{0}(φ) cos^{2k−1} φ sin φ dφ.

Furthermore, T_{0}(φ) can be estimated explicitly and it can be shown that the integral at the right does not exceed

\sqrt{\frac{6}{π}} \frac{p}{n} (2k)^{−3/2}(1 + o(1))

(as n, k → ∞). As to the integral at the left, we use Corollary 1 to estimate it from below by

T (φ_{0}) ∫_{0}^{π/2} ⌊\frac{φ}{φ_{0}} ⌋ cos^{2k−1} φ sin φ dφ ≥ \frac{T (φ_{0})}{φ_{0}} \sqrt{\frac{π}{2}} (2k)^{−3/2}(1 + o(1))

for any fixed φ_{0}. Therefore,

\frac{T (φ_{0})}{φ_{0}} \sqrt{\frac{π}{2}} (2k)^{−3/2} ≤ \sqrt{\frac{6}{π}} \frac{p}{n} (2k)^{−3/2}(1 + o(1))

and the result follows. □

Acknowledgment

The work on this paper was initiated in July 1999 when the authors attended the “Paul Erdős and his mathematics” conference in Budapest and its satellite workshop on combinatorial number theory. Our visit was partially supported by the Erdős center. It is our pleasure to thank the Erdős center for its hospitality and the excellent working environment.

References

[B76]R. N. Bhattacharya, R. Rao, Normal approximation and asymptotic expansions, John Wiley & Sons, New York, 1976.

[B99] A. Besser, Sets of integers with large trigonometric sums, Astérisque 258 (1999), 35–76.

[K97] S. V. Konyagin, On a question of Pichorides, C. R. Acad. Sci. Paris Ser. I Math. 324 (1997), 385–388.

[L98] V.F. Lev, On the number of solutions of a linear equation over finite sets, J. Comb. Theory, Ser. A 83 (1998), 251–267.

[L00] V.F. Lev, Linear equations over 𝔽_{p} and moments of exponential sums, Duke Math. Journal, to appear.

[M86] G. Myerson, How small can a sum of roots of unity be? American Math. Monthly 93 (1986) , 457–459.

[P80] S.K. Pichorides, On the L^{1}-norm of exponential sums, Annales de l’Inst. Fouier 30 (2) (1980), 79–89.

[Y73] A.A. Yudin, On the measure of large values of a trigonometric sum, in: Number Theory (under the edition of G.A. Freiman, A.M. Rubinov, E.V. Novosyolov), Kalinin State Univer., Moscow (1973), 163–174.