LINEAR EQUATIONS OVER 𝔽_{p} AND MOMENTS OF EXPONENTIAL SUMS

VSEVOLOD F. LEV

Abstract. Two of our principal results (in a simplified form) are as follows. Theorem. For p prime, the number of solutions of the equation

c_{1}a_{1} + ⋯ + c_{k}a_{k} = λ; a_{j} ∈ A_{j}

where c_{j} ∈ 𝔽_{p}^{×} and λ ∈ 𝔽_{p} are fixed coefficients and the variables a_{j} range over sets A_{j} ⊆ 𝔽_{p}, does not exceed the number of solutions of the equation

a_{1} + ⋯ + a_{k} = 0; a_{j} ∈ Ā_{j}

where the variables a_{j} range over arithmetic progressions Ā_{j} ⊆ 𝔽_{p} of the cardinalities |Ā_{j}| = |A_{j}| and balanced around zero.

This readily implies an integer version, which strengthens a result of Gabriel, Hardy and Littlewood. Theorem. Let A be a set of n = |A| residues modulo a prime p. For z ∈ 𝔽_{p}, write

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

Then for ε > 0 we have

#\{z ∈ 𝔽_{p}^{×}: |S_{A}(z)| > (1 − ε)n\} ≤ \frac{2\sqrt{6}}{π} \frac{p}{n} ε^{1/2} (1 + o(1)),

provided n → ∞ and ε → 0. Equality is attained when A is an arithmetic progression modulo p.

This implies an integer version which is due to Yudin.

This paper consist of two parts, the latter of which depends on the results of the former.

The first part is aimed to establish 𝔽_{p}-analogs of a series of results due to Gabriel, Hardy and Littlewood, known as “rearrangement theorems”. It will be seen that the original integer versions follow easily from their counterparts in 𝔽_{p}, but not vice versa. The second part dials with the moments and distribution of the absolute values of exponential sums in the field 𝔽_{p}. Analogs modulo p of two Yudin’s results concerning exponential sums, associated with a finite set of integers, are established.

An extended discussion of the results obtained is presented in Sections 1 and 2; the proofs are given Sections 3–6.

1991 Mathematics Subject Classification. Primary: 11B75; Secondary: 11D04, 11L07, 11P99, 11B25, 11D72.

Partially supported by the Edmund Landau Center for Research in Mathematical Analysis and Related Areas, sponsored by the Minerva Foundation (Germany).

2 VSEVOLOD F. LEV

1. Historical background and summary of results. Inequalities, rearrangements and linear equations over finite sets

The classical rearrangement theorems are the subject of [HLP88, Chapter X]. We first quote and discuss the central results, changing somewhat the original notation in an attempt to simplify the presentation.

We say that a function f̄: ℤ → ℝ^{+} is balanced if it satisfies either

f̄(0) ≥ f̄(1) ≥ f̄(−1) ≥ f̄(2) ≥ f̄(−2) ≥ …,

or

f̄(0) ≥ f̄(−1) ≥ f̄(1) ≥ f̄(−2) ≥ f̄(2) ≥ ….

We write

δ(f̄) = \begin{cases}−1, & if f̄(i) < f̄(−i) for some i ∈ ℤ^{+}, \\ 1, & if f̄(i) > f̄(−i) for some i ∈ ℤ^{+}, \\ 0, & if f̄(i) = f̄(−i) for any i ∈ ℤ. \end{cases}

For each function f: ℤ → ℝ^{+} with a finite support there exists a balanced function f̄: ℤ → ℝ^{+} which is a rearrangement of f in the sense that f̄ = f ∘ σ (equivalently, f̄(i) = f(σ(i))) for some bijection σ: ℤ → ℤ. There are two ways to balance a given function f, unless it attains its maximal value an odd number of times and any other non-zero value an even number of times. In the latter case the corresponding balanced function f̄ is said to be symmetrically decreasing.

Theorem A ([G32, Theorem 3], see also [HLP88, Theorem 376]). Suppose that the functions f_{j}: ℤ → ℝ^{+} (j = 1, …, k) have finite support, and let f̄_{j} be balanced functions, corresponding to f_{j}. Then

∑_{\begin{matrix}i_{1},...,i′_{k}∈ℤ \\ i_{1}+···+i_{k}=i′_{1}+···+i′_{k} \end{matrix}} f_{1}(i_{1})f_{1}(i′_{1}) … f_{k}(i_{k})f_{k}(i′_{k})

≤ ∑_{\begin{matrix}i_{1},...,i′_{k}∈ℤ \\ i_{1}+···+i_{k}=i′_{1}+···+i′_{k} \end{matrix}} f̄_{1}(i_{1})f̄_{1}(i′_{1}) … f̄_{k}(i_{k})f̄_{k}(i′_{k}).

This theorem was applied by Gabriel, Hardy and Littlewood to a problem in Fourier analysis.

Corollary 1 ([G32, Theorem 4]). Given finite trigonometric series

F_{j}(x) = ∑ f_{j}(m)e^{2πimx}; j = 1, …, k,

let g_{j}(m) = |f_{j}(m)| and suppose that ḡ_{j} are balanced functions, corresponding to g_{j}. Define G_{j}(x) = ∑ ḡ_{j}(m)e^{2πimx} (so that G_{j} are obtained by replacing the Fourier coefficients of F_{j} with their absolute values and rearranging them). Then

∫_{0}^{1} |F_{1}(x)|^{2} … |F_{k}(x)|^{2} dx ≤ ∫_{0}^{1} |G_{1}(x)|^{2} … |G_{k}(x)|^{2} dx.

As a particular case, we have

∫_{0}^{1} |F (x)|^{2k} dx ≤ ∫_{0}^{1} |G(x)|^{2k} dx.

The proof of Theorem A is based on

Theorem B ([G32, Theorem 2], see also [HLP88, Theorem 374]). Suppose that the functions f_{j}: ℤ → ℝ^{+} (j = 1, …, k) have finite support, and let f̄_{j} be corresponding balanced functions. Assume that δ(f̄_{1}) ≥ 0, δ(f̄_{2}) ≤ 0, and δ(f̄_{j}) = 0 for j = 3, …, k. Then

∑_{\begin{matrix}i_{1},...,i_{k}∈ℤ \\ i_{1}+···+i_{k}=0 \end{matrix}} f_{1}(i_{1}) … f_{k}(i_{k}) ≤ ∑_{\begin{matrix}i_{1},...,i_{k}∈ℤ \\ i_{1}+···+i_{k}=0 \end{matrix}} f̄_{1}(i_{1}) … f̄_{k}(i_{k}).

This theorem is due to Gabriel [G32]; it generalizes an earlier result of Hardy and Littlewood [HL28] where all functions f̄_{j} (including those with j = 1 and j = 2) were required to be symmetrically decreasing.

For k = 2, Theorem B becomes a re-statement of the well-known fact that the “scalar product” of two non-negative real sequences is maximized when these sequences are similarly ordered. In general, Theorem B establishes an inequality between two convolutions:

f_{1} ∗ ⋯ ∗ f_{k} (0) ≤ f̄_{1} ∗ ⋯ ∗ f̄_{k} (0).

An important particular case, on which the proof of Theorem B in its full generality relies, is that of f_{j} being the indicator functions of finite sets of integers A_{j}:

f_{j}(i) = \begin{cases}1, & if i ∈ A_{j}, \\ 0, & if i ∉ A_{j}. \end{cases}

Theorem B reduces then to

Theorem C. Suppose that A_{j} ⊆ ℤ (j = 1, …, k) are finite non-empty sets of integers of the cardinalities n_{j} = |A_{j}| such that n_{3}, …, n_{k} are odd. Define Ā_{j} to be arithmetic progressions of difference one, balanced around zero as follows:

Ā_{1} = [−(n_{1} − 1 − δ_{1})/2, (n_{1} − 1 + δ_{1})/2],
Ā_{2} = [−(n_{2} − 1 + δ_{2})/2, (n_{2} − 1 − δ_{2})/2],
Ā_{j} = [−(n_{j} − 1)/2, (n_{j} − 1)/2] (j = 3, …, k),

where for j = 1, 2 we put

δ_{j} = \begin{cases}0, & if n_{j} is odd, \\ 1, & if n_{j} is even. \end{cases}

Then the number of solutions of the equation

a_{1} + ⋯ + a_{k} = 0

in the variables a_{j} ∈ A_{j} does not exceed the number of solutions of this equation in the variables a_{j} ∈ Ā_{j}.

The major difficulty in converting Theorems A, B, and C into their 𝔽_{p}-counterparts lies in the proof of a modulo p version of the latter of the three theorems. Neither of the methods of [G32] or [HLP88] work in the new setting, and we had to employ a completely different argument. In fact, we prove a somewhat stronger result than just an analog of Theorem C, and we need an additional notation to formulate this result.

For p ≥ 3 prime, we write p′ = (p−1)/2. By a balanced set of residues modulo p we mean a non-empty block of consecutive residues of the form Ā = [−α, α + δ](mod p), where α ∈ [0, p′] and δ ∈ {0, ±1} are integers. (We exclude from consideration the degenerate cases α = 0, δ = −1 and α = p′, δ = 1.) Obviously, δ is uniquely defined by the set Ā and we write δ = δ(Ā). If the cardinality |Ā| is odd then necessarily δ(Ā) = 0; if |Ā| is even, there are two possibilities: either δ(Ā) = 1, or δ(Ā) = −1. If A is a non-empty set of residues modulo p, then Ā is used for a balanced set of the same cardinality as A.

For λ ∈ 𝔽_{p} we denote by N_{λ}(A_{1}, …, A_{k}) the number of representations λ = a_{1} + ⋯ + a_{k} with a_{j} ∈ A_{j}. Thus,

N_{λ}(A_{1}, …, A_{k}) = ∑_{\begin{matrix}i_{1},...,i_{k}∈𝔽_{p} \\ i_{1}+···+i_{k}=λ \end{matrix}} χ_{1}(i_{1}) … χ_{k}(i_{k}) = χ_{1} ∗ ⋯ ∗ χ_{k} (λ)

is the convolution of the characteristic functions χ_{j} of the sets A_{j}.

Given non-empty A_{1}, …, A_{k} ⊆ 𝔽_{p}, we write {ν_{i}(A_{1}, …, A_{k})}_{i=1}^{p} for the descending rearrangement of the sequence {N_{λ}(A_{1}, …, A_{k})}_{λ=−p′}^{p′}; thus,

ν_{1}(A_{1}, …, A_{k}) = max_{λ∈𝔽_{p}}N_{λ}(A_{1}, …, A_{k}),

∑_{i=1}^{p} ν_{i}(A_{1}, …, A_{k}) = ∑_{λ=−p′}^{p′} N_{λ}(A_{1}, …, A_{k}) = |A_{1}| ⋯ |A_{k}|,

and the number of indices i such that ν_{i}(A_{1}, …, A_{k}) > 0 is the cardinality of the sumset A_{1}+⋯+A_{k}. Furthermore, we write (A_{1}, …, A_{k}) ≺ (B_{1}, …, B_{k}) if A_{1}, …, A_{k} and B_{1}, …, B_{k} are two systems of sets such that

∑_{i=1}^{m} ν_{i}(A_{1}, …, A_{k}) ≤ ∑_{i=1}^{m} ν_{i}(B_{1}, …, B_{k})  (1)

for m = 1, …, p. In particular, when m = 1 this implies

max_{λ∈𝔽_{p}}N_{λ}(A_{1}, …, A_{k}) ≤ max_{λ∈𝔽_{p}}N_{λ}(B_{1}, …, B_{k}).

Example . For p = 7, consider A_{1} = {0, 2}, A_{2} = {1, 2, 6}, Ā_{1} = {0, 1}, and Ā_{2} = {−1, 0, 1}. Then

A_{1} + A_{2} = {1, 2, 3, 4, 6}, {ν_{i}(A_{1}, A_{2})}_{i=1}^{7} = (2, 1, 1, 1, 1, 0, 0),
Ā_{1} + Ā_{2} = {−1, 0, 1, 2}, {ν_{i}(Ā_{1}, Ā_{2})}_{i=1}^{7} = (2, 2, 1, 1, 0, 0, 0),

whence (A_{1}, A_{2}) ≺ (Ā_{1}, Ā_{2}).

We can now formulate our version of Theorem C.

Theorem 1. Suppose that A_{j} ⊆ 𝔽_{p} (j = 1, …, k) are non-empty sets of residues modulo a prime p ≥ 3, and let Ā_{j} be corresponding balanced sets. Then

(A_{1}, …, A_{k}) ≺ (Ā_{1}, …, Ā_{k}).

Moreover, assume that |δ(Ā_{1}) + ⋯ + δ(Ā_{k})| ≤ 1. Then, writing for brevity N_{λ} for N_{λ}(Ā_{1}, …, Ā_{k}), we have:

– if 0 ≤ δ(Ā_{1}) + ⋯ + δ(Ā_{k}) ≤ 1, then

N_{0} ≥ N_{1} ≥ N_{−1} ≥ N_{2} ≥ N_{−2} ≥ ⋯ ≥ N_{p′} ≥ N_{−p′};
– if −1 ≤ δ(Ā_{1}) + ⋯ + δ(Ā_{k}) ≤ 0, then
N_{0} ≥ N_{−1} ≥ N_{1} ≥ N_{−2} ≥ N_{2} ≥ ⋯ ≥ N_{−p′} ≥ N_{p′},

where p′ = (p − 1)/2.

That is, if λ̄_{1}, …, λ̄_{m} are the first m terms of either the sequence (0, 1, −1, 2, −2, …, p′, −p′) or the sequence (0, −1, 1, −2, 2, …, −p′, p′) (depending on the sign of the sum δ(Ā_{1}) + ⋯ + δ(Ā_{k})), and if λ_{1}, …, λ_{m} are any m pairwise distinct residues, then

N_{λ_{1}}(A_{1}, …, A_{k}) + ⋯ + N_{λ_{m}}(A_{1}, …, A_{k}) ≤ Nλ̄_{1}(Ā_{1}, …, Ā_{k}) + ⋯ + Nλ̄_{m}(Ā_{1}, …, Ā_{k}).

Remark. Clearly, the first assertion of Theorem 1 remains valid when Ā_{j} are arbitrary arithmetic progressions, sharing a common difference — not necessarily balanced around zero and of difference one.

Compared to Theorem C, we were able to replace the asymmetrical requirement on δ(Ā_{j}) (and thus on the parity of |A_{j}|) by the weaker and more aesthetic assumption |δ(Ā_{1}) + ⋯ + δ(Ā_{k})| ≤ 1. At the same time, the conclusion of Theorem 1 is considerably stronger than just N_{0}(A_{1}, …, A_{k}) ≤ N_{0}(Ā_{1}, …, Ā_{k}), claimed by Theorem C.

Theorem 1 is an 𝔽_{p}-analog of [L98, Theorem 2 and Lemma 1].

We show in Section 3 that the first assertion of Theorem 1 is essentially equivalent to a well-known result of Pollard [P74], and we obtain the second assertion as a consequence of the first one.

Following the argument of Hardy and Littlewood (or that of Gabriel), from Theorem 1 one can easily derive the following analog of Theorem B.

6 VSEVOLOD F. LEV

Theorem 2. Suppose that f_{j}: 𝔽_{p} → ℝ^{+} (j = 1, …, k) is any system of functions, and let f̄_{j} be corresponding balanced functions. Assume that δ(f̄_{1}) ≥ 0, δ(f̄_{2}) ≤ 0, and δ(f̄_{j}) = 0 for j = 3, …, k. Then

∑_{\begin{matrix}i_{1},...,i_{k}∈𝔽_{p} \\ i_{1}+···+i_{k}=0 \end{matrix}} f_{1}(i_{1}) … f_{k}(i_{k}) ≤ ∑_{\begin{matrix}i_{1},...,i_{k}∈𝔽_{p} \\ i_{1}+···+i_{k}=0 \end{matrix}} f̄_{1}(i_{1}) … f̄_{k}(i_{k}).

(Though we have never given a formal definition of a balanced function with 𝔽_{p} as a domain, the reader won’t have a problem extrapolating the definition for functions defined on ℤ.)

From Theorem 2 we deduce an 𝔽_{p}-version of Theorem A; this is somewhat tricky, though requires no principally new ideas compared to [HLP88] and [G32].

Theorem 3. Suppose that f_{j}: 𝔽_{p} → ℝ^{+} (j = 1, …, k) is any system of functions, and let f̄_{j} be corresponding balanced functions. Then

∑_{\begin{matrix}i_{1},...,i′_{k}∈𝔽_{p} \\ i_{1}+···+i_{k}=i′_{1}+···+i′_{k} \end{matrix}} f_{1}(i_{1})f_{1}(i′_{1}) … f_{k}(i_{k})f_{k}(i′_{k})

≤ ∑_{\begin{matrix}i_{1},...,i′_{k}∈𝔽_{p} \\ i_{1}+···+i_{k}=i′_{1}+···+i′_{k} \end{matrix}} f̄_{1}(i_{1})f̄_{1}(i′_{1}) … f̄_{k}(i_{k})f̄_{k}(i′_{k}).

We prove Theorems 2 and 3 in Section 4.

Remark . Theorem 1 implies Theorem C; to see this, given integer sets A_{1}, …, A_{k} choose p large enough and consider the canonical images of A_{j} in 𝔽_{p}. Similarly, Theorem 2 implies Theorem B, and Theorem 3 implies Theorem A. However, no sufficiently general and powerful method is known to derive modulo p results from their integer counterparts.

Immediate from Theorem 3 is

Corollary 2. Given trigonometric series

F_{j}(x) = ∑_{m=−p′}^{p′} f_{j}(m)e^{2πi \frac{mx}{p}}; j = 1, …, k,

let g_{j}(m) = |f_{j}(m)| and suppose that ḡ_{j} are balanced functions, corresponding to g_{j}. Define

G_{j}(x) = ∑_{m=−p′}^{p′} ḡ_{j}(m)e^{2πi \frac{mx}{p}}

(so that G_{j} are obtained by replacing the Fourier coefficients of F_{j} with their absolute values and rearranging them). Then

∑_{x=−p′}^{p′} |F_{1}(x)|^{2} … |F_{k}(x)|^{2} ≤ ∑_{x=−p′}^{p′} |G_{1}(x)|^{2} … |G_{k}(x)|^{2}.

As a particular case, we have

∑_{x=−p′}^{p′} |F (x)|^{2k} ≤ ∑_{x=−p′}^{p′} |G(x)|^{2k}.

2. Historical background and summary of results. Moments and large values of exponential sums

For a set A ⊆ 𝔽_{p} of n = |A| residues modulo a prime p, let

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

denote the exponential sums of A. The number of solutions of the linear equation

a_{1} + ⋯ + a_{k} = λ; a_{j} ∈ A  (2)

is

\frac{1}{p} ∑_{z=0}^{p−1} S^{k}(z)e^{−2πi \frac{λz}{p}} ,

and for k large the terms that determine the behavior of this sum are those with |S(z)| large. In [L98], we gave an estimate for the number of such z, which allowed us to estimate the number of solutions of (2). Now, equipped with Theorem 1 that establishes a precise bound for the number of solutions of equations of the type (2), we can reverse the procedure and obtain a sharp estimate for the number of z such that |S(z)| is large. In doing so, we follow in general the approach of Yudin [Y73], who solved the parallel problem for integer sets; the technical details are quite different, however.

It is convenient to measure the number of large exponential sums by the function T (φ), defined by

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

Thus, T (φ) is a non-decreasing, piecewise constant function such that T (0) = 0 and T (π/2) = p − 1. The reason for introducing T (φ) is that it has a nice additivity property, established in following lemma.

Lemma 1. Suppose that φ_{1}, φ_{2} ≥ 0 and φ_{1} + φ_{2} ≤ π/2. Then

T (φ_{1} + φ_{2}) ≥ min{T (φ_{1}) + T (φ_{2}), p − 1}  (3)

for any non-empty A ⊆ 𝔽_{p}.

8 VSEVOLOD F. LEV

This lemma follows easily from an observation of Yudin and was first used in [L98]. For the benefit of the reader we will reproduce its proof (which is just a few lines long) in Section 6.

From Lemma 1 we will derive the following property of the function T (φ).

Lemma 2. Suppose that n = |A| ≥ 4. Then for any 0 < φ, φ_{0} ≤ π/2 we have

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

We note that the integer part brackets cannot be dropped; indeed, the function T (φ)/φ is not monotonic.

Remark. The proof of Lemma 2 would be immediate if we could omit the p − 1 term in (3) and rewrite it as

T (φ_{1} + φ_{2}) ≥ T (φ_{1}) + T (φ_{2}) :

by induction, we have then T (jφ_{0}) ≥ jT (φ_{0}) provided jφ_{0} ≤ π/2, and we choose j = ⌊φ/φ_{0}⌋. It can be shown, however, that this “strong” form of (3) is incorrect.

Lemma 2 is implicit in [L98]; here we give an explicit formulation and an independent explicit proof.

We prove two estimates for the number of large sums S(z). The first is indirect but may turn more useful in certain applications.

Theorem 4. For any set A ⊆ 𝔽_{p} of n = |A| ≥ 3 residues modulo a prime p and any even integer k ≥ 2 we have

∑_{z=1}^{p−1} |S(z)|^{k} ≤ \sqrt{\frac{6}{πk}} n^{k−1} p (1 + n^{−2})(1 + 4k^{−1}).

(In fact, we give a somewhat better reminder term, provided k ≥ 16 — see the proof in Section 6.) It is interesting to compare the estimate of Theorem 4 with the trivial estimate ∑ |S(z)|^{k} ≤ n^{k−1}p.

The second is a direct estimate.

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

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

In Section 5 we consider the case of an arithmetic progression A = {0, …, n − 1} and show that Theorems 4 and 5 are best possible save for the reminder terms.

LINEAR EQUATIONS & EXPONENTIAL SUMS 9

3. Pollard’s theorem and the proof of Theorem 1

Theorem D (Pollard, [P74, Theorem 1]). Suppose that A_{j} ⊆ 𝔽_{p} (j = 1, …, k) are non-empty sets of residues modulo a prime p ≥ 3, and let Ā_{j} be arithmetic progressions modulo p sharing a common difference and such that |A_{j}| = |Ā_{j}|. Write ν_{i} = ν_{i}(A_{1}, …, A_{k}), ν̄_{i} = ν_{i}(Ā_{1}, …, Ā_{k}), and define

h(t) := ∑_{i=1}^{∞} min{ν_{i}, t}, h̄(t) := ∑_{i=1}^{∞} min{ν̄_{i}, t}; t ≥ 0.

Then

h(t) ≥ h̄(t)

for any non-negative real t.

Remark . For k = 2, this theorem is better known in an apparently different, but equivalent form: writing K_{i} for the number of elements c ∈ A_{1} +A_{2} that have at least i representations as c = a_{1} + a_{2} (a_{j} ∈ A_{j}), for any integer 1 ≤ t ≤ min{|A_{1}|, |A_{2}|} we have

K_{1} + ⋯ + K_{t} ≥ t min{|A_{1}| + |A_{2}| − t, p}.

The first assertion of Theorem 1 follows immediately from Pollard’s theorem and our next lemma^{1}.

Lemma 3. Let ν_{1} ≥ ν_{2} ≥ ⋯ and ν̄_{1} ≥ ν̄_{2} ≥ ⋯ be two sequences of non-negative real numbers, such that ν_{1} + ν_{2} + ⋯ = ν̄_{1} + ν̄_{2} + ⋯, and only a finite number of elements of each sequence is distinct from zero. For non-negative real t define h(t) and h̄(t) as in Theorem D. Then the two following assertions are equivalent:

(a) ν_{1} + ⋯ + ν_{m} ≤ ν̄_{1} + ⋯ + ν̄_{m} for any m = 1, 2, …;

(b) h(t) ≥ h̄(t) for any t ≥ 0.

Proof. Put σ = ν_{1} +ν_{2} +⋯ = ν̄_{1} +ν̄_{2} +⋯, so that both h(t) and h̄(t) are continuous, non-decreasing functions, satisfying h(0) = h̄(0) = 0, h(ν_{1}) = h̄(ν̄_{1}) = σ, and σ = max h = max h̄.

i) We first show that (a) implies (b). We assume that t ≤ ν_{1}, as otherwise h(t) = σ ≥ h̄(t). Thus, t ≤ ν̄_{1} also, and there exist indices i, j ≥ 1 such that

ν_{i+1} ≤ t ≤ ν_{i}, ν̄_{j+1} ≤ t ≤ ν̄_{j},

1When our paper was completed, we discovered that this lemma is known in the theory of majorization, cf. [MO79, Proposition 4.B.4]). It originates from the works of Hardy, Littlewood, and Polya, who also gave several other characterizations of sequences satisfying the conditions of the lemma: for instance, ψ(ν_{1}) + ⋯ + ψ(ν_{m}) ≤ ψ(ν̄_{1}) + ⋯ + ψ(ν̄_{m}) for all m ≥ 1 and all continuous increasing convex functions ψ (cf. [MO79, Proposition 4.B.2]). For the sake of completeness, we retain our proof of the lemma.

10 VSEVOLOD F. LEV

whence

h(t) = σ − ν_{1} − ⋯ − ν_{i} + it, h̄(t) = σ − ν̄_{1} − ⋯ − ν̄_{j} + jt.

What we want to prove is, therefore,

ν_{1} + ⋯ + ν_{i} − it ≤ ν̄_{1} + ⋯ + ν̄_{j} − jt,

and we show that, moreover,

ν̄_{1} + ⋯ + ν̄_{i} − it ≤ ν̄_{1} + ⋯ + ν̄_{j} − jt.  (4)

Indeed, if i ≤ j then (4) is equivalent to

(j − i)t ≤ ν̄_{i+1} + ⋯ + ν̄_{j},

which is evident in view of t ≤ ν̄_{j} ≤ ⋯ ≤ ν̄_{i+1}; otherwise, i ≥ j and (4) is equivalent to

(i − j)t ≥ ν̄_{j+1} + ⋯ + ν̄_{i},

which follows from t ≥ ν̄_{j+1} ≥ ⋯ ≥ ν̄_{i}.

ii) We now use induction by m to show that (b) implies (a). First, we have σ = h̄(ν̄_{1}) ≤ h(ν̄_{1}) ≤ σ, whence h(ν̄_{1}) = σ and therefore ν_{1} ≤ ν̄_{1}. Next, assuming ν_{1} + ⋯ + ν_{m} ≤ ν̄_{1} + ⋯ + ν̄_{m} for some m ≥ 1, we show that

ν_{1} + ⋯ + ν_{m+1} ≤ ν̄_{1} + ⋯ + ν̄_{m+1}.  (5)

Indeed, this is obvious if ν_{m+1} ≤ ν̄_{m+1}, while otherwise ν_{m+1} ≥ ν̄_{m+1} and then

σ − ν̄_{1} − ⋯ − ν̄_{m} + mν̄_{m+1} = h̄(ν̄_{m+1}) ≤ h(ν̄_{m+1})

= (m + 1)ν̄_{m+1} + ∑_{j=m+2}^{∞} min{ν_{j}, ν̄_{m+1}} ≤ (m + 1)ν̄_{m+1} + ∑_{j=m+2}^{∞} ν_{j}

= (m + 1)ν̄_{m+1} + σ − ν_{1} − ⋯ − ν_{m+1},

from which (5) follows. □

To complete the proof of Theorem 1, it remains to show how its first assertion implies the second one. We use induction by k. The case k = 2 is easy, and we consider k ≥ 3. For definiteness, we suppose that 0 ≤ δ(Ā_{1}) + ⋯ + δ(Ā_{k}) ≤ 1. Moreover, permuting the indices, if necessary, we can assume that δ(Ā_{k}) ≥ 0, and then

|δ(Ā_{1}) + ⋯ + δ(Ā_{k−1})| ≤ 1.  (6)

For m ∈ [1, p], let λ_{1}, …, λ_{m} ∈ 𝔽_{p} be any pairwise distinct residues modulo p. We put Λ = {−λ_{1}, …, −λ_{m}}, and we define λ̄_{1}, …, λ̄_{m} to be the first m elements of the sequence (0, 1, −1, 2, −2, …, p′, −p′), so that Λ̄ := {−λ̄_{1}, …, −λ̄_{m}} is balanced and

δ(Λ̄) ≤ 0, |δ(Ā_{k}) + δ(Λ̄)| ≤ 1.  (7)

LINEAR EQUATIONS & EXPONENTIAL SUMS 11

Moreover, if δ(Ā_{k}) = 0, then

δ(Ā_{1}) + ⋯ + δ(Ā_{k−1}) ≥ 0, and δ(Ā_{k}) + δ(Λ̄) ≤ 0,

and if δ(Ā_{k}) = 1, then

δ(Ā_{1}) + ⋯ + δ(Ā_{k−1}) ≤ 0, and δ(Ā_{k}) + δ(Λ̄) ≥ 0.

By (6), (7), the latter observation, the first assertion of Theorem 1, and the induction hypothesis, we have

∑_{i=1}^{m} N_{λ_{i}}(Ā_{1}, …, Ā_{k}) = N_{0}(Ā_{1}, …, Ā_{k}, Λ)

= ∑_{\begin{matrix}u,v∈𝔽_{p} \\ u+v=0 \end{matrix}} N_{u}(Ā_{1}, …, Ā_{k−1})N_{v}(Ā_{k}, Λ)

≤ ∑_{i=1}^{p} ν_{i}(Ā_{1}, …, Ā_{k−1})ν_{i}(Ā_{k}, Λ)

= ∑_{m=1}^{p−1} (ν_{m}(Ā_{1}, …, Ā_{k−1}) − ν_{m+1}(Ā_{1}, …, Ā_{k−1})) ∑_{i=1}^{m} ν_{i}(Ā_{k}, Λ)

+ ν_{p}(Ā_{1}, …, Ā_{k−1}) ∑_{i=1}^{p} ν_{i}(Ā_{k}, Λ)

≤ ∑_{m=1}^{p−1} (ν_{m}(Ā_{1}, …, Ā_{k−1}) − ν_{m+1}(Ā_{1}, …, Ā_{k−1})) ∑_{i=1}^{m} ν_{i}(Ā_{k}, Λ̄)

+ ν_{p}(Ā_{1}, …, Ā_{k−1}) ∑_{i=1}^{p} ν_{i}(Ā_{k}, Λ̄)

= ∑_{i=1}^{p} ν_{i}(Ā_{1}, …, Ā_{k−1})ν_{i}(Ā_{k}, Λ̄)

= ∑_{\begin{matrix}u,v∈𝔽_{p} \\ u+v=0 \end{matrix}} N_{u}(Ā_{1}, …, Ā_{k−1})N_{v}(Ā_{k}, Λ̄)

= N_{0}(Ā_{1}, …, Ā_{k}, Λ̄)

= ∑_{i=1}^{m} Nλ̄_{i}(Ā_{1}, …, Ā_{k}),

which is to be proved.

4. Proofs of Theorems 2 and 3

Proof of Theorem 2. We follow the method of Hardy and Littlewood [HL28]; Gabriel [G32] gives an alternative approach. The idea is to represent f̄_{j} as linear combinations of indicator functions of balanced subsets of 𝔽_{p}, yielding corresponding representations of f_{j}. Indeed, we can write

f̄_{j}(i) = ∑_{m=1}^{p} c_{jm}χ̄_{jm}(i); j = 1, …, k,

where c_{jm} are non-negative coefficients and χ̄_{jm} are the indicator functions of some balanced Ā_{jm} ⊆ 𝔽_{p}. Moreover, the conditions imposed on f̄_{j} imply that Ā_{jm} can be chosen to satisfy

δ(Ā_{1m}) ≥ 0, δ(Ā_{2m}) ≤ 0, δ(Ā_{jm}) = 0 for 3 ≤ j ≤ k.

Accordingly, we have

f_{j}(i) = ∑_{m=1}^{p} c_{jm}χ_{jm}(i); j = 1, …, k,

where χ_{mj} are the indicator functions of some A_{jm} such that |A_{jm}| = |Ā_{jm}|. Now

∑_{i_{1}+···+i_{k}=0} f_{1}(i_{1}) ⋯ f_{k}(i_{k}) = ∑_{m_{1},...,m_{k}=1}^{p} c_{1m_{1}} … c_{km_{k}} ∑_{i_{1}+···+i_{k}=0} χ_{1m_{1}}(i_{1}) … χ_{km_{k}}(i_{k}),

and the inner sum at the right is simply the number of solutions of the equation i_{1} + ⋯ + i_{k} = 0 in the variables i_{j} ∈ A_{jm_{j}}. By Theorem 1, this number of solutions can only increase if all A_{jm_{j}} are replaced by Ā_{jm_{j}}, that is the inner sum can only increase if all χ_{im_{j}} are replaced by χ̄_{jm_{j}}. The result follows. □

To prove Theorem 3 we rewrite its assertion as

∑_{m_{1}+···+m_{k}=0} F_{1}(m_{1}) … F_{k}(m_{k}) ≤ ∑_{m_{1}+···+m_{k}=0} F̄_{1}(m_{1}) … F̄_{k}(m_{k}),

where we put

F_{j}(m) = ∑_{i−i′=m} f_{j}(i)f_{j}(i′) and F̄_{j}(m) = ∑_{i−i′=m} f̄_{j}(i)f̄_{j}(i′).  (8)

Notice that, for j = 1, …, k,

F_{j}(0) = max F_{j}(m), F_{j}(m) = F_{j}(−m) (m ∈ 𝔽_{p})  (9)

and similarly,

F̄_{j}(0) = max F̄_{j}(m), F̄_{j}(m) = F̄_{j}(−m) (m ∈ 𝔽_{p}).  (10)

for any j = 1, …, k.

We need several lemmas.

Lemma 4. For j = 1, …, k, the functions F̄_{j} defined by (8) are symmetrically decreasing:

F̄_{j}(0) ≥ F̄_{j}(1) = F̄_{j}(−1) ≥ ⋯ ≥ F̄_{j}(p′) = F̄_{j}(−p′).

LINEAR EQUATIONS & EXPONENTIAL SUMS 13

Proof. For a non-empty set A ⊆ 𝔽_{p} of odd cardinality, let Ā be the corresponding balanced set, and let χ = χ_{A} and χ̄ = χĀ be the indicator functions of A and Ā, respectively. Then χ̄ is the balanced rearrangement of χ and we have

∑_{m} F̄_{j}(m)χ(m) = ∑_{i′−i+m=0} f̄_{j}(i)f̄_{j}(i′)χ(m) = ∑_{i′+i+m=0} f̄_{j}(−i)f̄_{j}(i′)χ(m)

(by Theorem 2)

≤ ∑_{i′+i+m=0} f̄_{j}(−i)f̄_{j}(i′)χ̄(m) = ∑_{m} F̄_{j}(m)χ̄(m).

From this and (10) the assertion follows. □

For two functions g, h: 𝔽_{p} → ℝ^{+} we write f ≺ g if for any system of m ≥ 1 pairwise distinct residues λ_{1}, …, λ_{m} ∈ 𝔽_{p} there exists another system of pairwise distinct residues μ_{1}, …, μ_{m} ∈ 𝔽_{p} such that

f(λ_{1}) + ⋯ + f(λ_{m}) ≤ g(μ_{1}) + ⋯ + g(μ_{m}).

(This agrees with the notation (A_{1}, …, A_{k}) ≺ (B_{1}, …, B_{k}) if we consider the latter as an abbreviation for N(A_{1}, …, A_{k}) ≺ N(B_{1}, …, B_{k}).)

Lemma 5. For j = 1, …, k we have F_{j} ≺ F̄_{j}, where the functions F_{j} and F̄_{j} are defined by (8).

Proof. For A, Ā, χ and χ̄ as in the proof of Lemma 4, we have

∑_{m} F_{j}(m)χ(m) = ∑_{i′−i+m=0} f_{j}(i)f_{j}(i′)χ(m) = ∑_{i′+i+m=0} f_{j}(−i)f_{j}(i′)χ(m)

(by Theorem 2)

≤ ∑_{i′+i+m=0} f̄_{j}(−i)f̄_{j}(i′)χ̄(m) = ∑_{m} F̄_{j}(m)χ̄(m).

The assertion follows in view of (9) and (10). □

Lemma 6. If g_{1}, …, g_{k}: 𝔽_{p} → ℝ^{+} are symmetrically decreasing, then the convolution G = g_{1} ∗ ⋯ ∗ g_{k} is symmetrically decreasing also.

Proof. Let A, Ā, χ, and χ̄ be as in the proofs of Lemmas 4 and 5, except that we don’t require the cardinality of A to be odd and accordingly, there can be a freedom of choice of Ā. We have

∑_{m} G(m)χ(m) = ∑_{i_{1}+···+i_{k}+m=0} g_{1}(i_{1}) … g_{k}(i_{k})χ(−m)

(by Theorem 2)

≤ ∑_{i_{1}+···+i_{k}+m=0} g_{1}(i_{1}) … g_{k}(i_{k})χ̄(−m) = ∑_{m} G(m)χ̄(m).

14 VSEVOLOD F. LEV

It follows that G is symmetrically decreasing. □

Lemma 7. Let g, g_{1}, g_{2} : 𝔽_{p} → ℝ^{+} be symmetrically decreasing functions, and suppose that g_{1} ≺ g_{2}. Then

∑_{m∈𝔽_{p}} g(m)g_{1}(m) ≤ ∑_{m∈𝔽_{p}} g(m)g_{2}(m).

Proof. We have

∑_{m=−p′}^{p′} g(m)g_{1}(m) = ∑_{m=0}^{p′−1}(g(m) − g(m + 1)) ∑_{i=−m}^{m} g_{1}(i) + g(p′) ∑_{i=−p′}^{p′} g_{1}(i)

≤ ∑_{m=0}^{p′−1}(g(m) − g(m + 1)) ∑_{i=−m}^{m} g_{2}(i) + g(p′) ∑_{i=−p′}^{p′} g_{2}(i)

= ∑_{m=−p′}^{p′} g(m)g_{2}(m).

□

Now we can prove Theorem 3.

Proof of Theorem 3. Let σ_{j}: ℤ → ℤ (j = 1, …, k) be bijections of ℤ such that F_{j} ∘σ_{j} are balanced and thus symmetrically decreasing in view of (9). By Theorem 2, we have

∑_{m_{1}+···+m_{k}=0} F_{1}(m_{1}) … F_{k}(m_{k}) ≤ ∑_{m_{1}+···+m_{k}=0} F_{1}(σ_{1}(m_{1})) … F_{k}(σ_{k}(m_{k}))

= ∑_{m_{1}} F_{1}(σ_{1}(m_{1})) ∑_{m_{2}+···+m_{k}=−m_{1}} F_{2}(σ_{2}(m_{2})) … F_{k}(σ_{k}(m_{k})),

and we notice that both F_{1} ∘σ_{1} and the inner sum, considered as a function of m_{1}, are symmetrically decreasing (the latter by Lemma 6). Next, F_{1} ∘ σ_{1} ≺ F̄_{1} by Lemma 5, and therefore by Lemmas 4 and 7 the right-hand side does not exceed

∑_{m_{1}} F̄_{1}(m_{1}) ∑_{m_{2}+···+m_{k}=−m_{1}} F_{2}(σ_{2}(m_{2})) … F_{k}(σ_{k}(m_{k}))

= ∑_{m_{2}} F_{2}(σ_{2}(m_{2})) ∑_{m_{1}+m_{3}+···+m_{k}=−m_{2}} F̄_{1}(m_{1})F_{3}(σ_{3}(m_{3})) … F_{k}(σ_{k}(m_{k})).

In a similar vein, replacing F_{2}(σ_{2}(m_{2})) by F̄_{2}(m_{j}) we can only increase this latter expression, and continuing in this way we see that

∑_{m_{1}+···+m_{k}=0} F_{1}(m_{1}) … F_{k}(m_{k})

≤ ∑_{m_{1}+···+m_{k}=0} F_{1}(σ_{1}(m_{1})) … F_{k}(σ_{k}(m_{k})) ≤ ∑_{m_{1}+···+m_{k}=0} F̄_{1}(m_{1}) … F̄_{k}(m_{k})

which is to be proved. □

5. Large exponential sums: the case of an arithmetic progression

Let A_{0} = {0, …, n − 1}(mod p), so that the corresponding sums S_{0}(z) satisfy

|S_{0}(z)| = \frac{| sin π \frac{nz}{p}|}{sin π \frac{z}{p}}  (z = 1, …, p − 1).  (11)

We write

G(x) = \frac{sin x}{x} (0 < x ≤ π)

and we define G(0) = 1 by continuity; thus, the inverse function G^{−1}(x) is a continuous, monotonically decreasing function of [0, 1], satisfying G^{−1}(0) = π, G^{−1}(1) = 0.

Lemma 8. For κ ∈ (0.5, 1) and n ≥ 2 the equation

\frac{| sin(nx)|}{sin x} = κn  (12)

has exactly one solution x = x(n, κ) on the interval (0, π/2), and this solution satisfies

x = \frac{1}{n} G^{−1}(κ) (1 + \frac{θ}{n^{2}} ) ,

where θ = θ(n, κ) ∈ (0, 1).

Proof. As the function f(x) = sin(nx)/ sin x decreases on (0, π/n) and f(0+) = n > nκ > 0 = f(π/n), equation (12) has precisely one solution on (0, π/n). Moreover, if x ∈ (π/n, π/2), then

|f(x)| ≤ (\frac{2}{π} x)^{−1} ≤ \frac{n}{2} < κn,

which shows that (π/n, π/2) contains no solutions. We now estimate the solution x = x(n, κ) ∈ (0, π/n).

Since (12) implies G(nx) = κG(x) < κ, we have nx > G^{−1}(κ), whence x > n^{−1}G^{−1}(κ). To obtain the upper bound, we first note that

G(nx) = κG(x) > κ (1 − \frac{x^{2}}{6} ) .  (13)

Next, we let μ = n/(n^{2} + 1), and we show that

G(nx) ≤ (1 − \frac{x^{2}}{6} ) G((n − μ)x).  (14)

Notice, that (14) along with (13) yield

G((n − μ)x) > κ,
(n − μ)x < G^{−1}(κ),
x < \frac{1}{n − μ} G^{−1}(κ) = \frac{1}{n} (1 + \frac{1}{n^{2}} ) G^{−1}(κ),

16 VSEVOLOD F. LEV

and it remains to prove (14). To this end we rewrite it as

G((n − μ)x) − G(nx) ≥ \frac{x^{2}}{6} G((n − μ)x),  (15)

and we observe that

G((n − μ)x) − G(nx) ≥ μx (−G′((n − μ)x)).

Letting ξ = (n − μ)x and using the inequality

sin ξ ≥ ξ cos ξ + \frac{1}{3} ξ^{2} sin ξ

(valid for any ξ ∈ [0, π/2]), we get

G((n − μ)x) − G(nx) ≥ μx \frac{sin ξ − ξ cos ξ}{ξ^{2}}

≥ \frac{1}{3} μx sin ξ

= \frac{x^{2}}{6} 2μ(n − μ) G(ξ)

≥ \frac{x^{2}}{6} G(ξ),

which proves (15). □ Corollary 3. For 0 < φ < π/3, the number of z ∈ 𝔽_{p}^{×} such that |S_{0}(z)| > n cos φ is

T_{0}(φ) = 2⌈Z⌉ − 2,

where

Z = \frac{1}{π} \frac{p}{n} G^{−1}(cos φ) (1 + \frac{θ}{n^{2}} ); θ ∈ (0, 1).

We next estimate the function G^{−1}(x). Lemma 9.

\sqrt{6(1 − x)} ≤ G^{−1}(x) ≤ \sqrt{6(1 − x)} (1 + \frac{1}{4}(1 − x)) ,

provided 7/15 ≤ x ≤ 1. (In fact, the lower bound holds true for all x ∈ [0, 1].) Proof. i) Given x ∈ [0, 1], we define z = \sqrt{6(1 − x)}. Then

G(z) ≥ 1 − \frac{z^{2}}{6} = x,
G^{−1}(x) ≥ z = \sqrt{6(1 − x)}.

ii) To prove the upper bound, we use the inequality

G(z) ≤ 1 − \frac{z^{2}}{6} + \frac{z^{4}}{120}  (z ≥ 0).  (16)

LINEAR EQUATIONS & EXPONENTIAL SUMS 17

Given x ∈ [7/15, 1], we define z ∈ [0, 2] by

x = 1 − \frac{z^{2}}{6} + \frac{z^{4}}{120},  (17)

and we get then

6(1 − x) = z^{2} (1 − \frac{z^{2}}{20}) ≥ \frac{4}{5}z^{2},

whence

\frac{z^{2}}{20} ≤ \frac{3}{8}(1 − x).

The latter inequality and (17) give

6(1 − x) = z^{2} (1 − \frac{z^{2}}{20}) ≥ z^{2} (1 − \frac{3}{8} (1 − x)) ≥ \frac{z^{2}}{1 + \frac{1}{2} (1 − x)},

z^{2} ≤ 6(1 − x) (1 + \frac{1}{2} (1 − x)) .  (18)

Now by (16), (17) and (18),

G^{−1}(x) ≤ z ≤ \sqrt{6(1 − x)}\sqrt{1 + \frac{1}{2} (1 − x)} ≤ \sqrt{6(1 − x)} (1 + \frac{1}{4} (1 − x)) .

□

6. Large exponential sums: Proofs of Theorems 4 and 5 We first prove several auxiliary lemmas.

Proof of Lemma 1. The observation of Yudin, mentioned in Section 2, is that

|S(z_{1} + z_{2})| > n cos(φ_{1} + φ_{2}),  (19)

provided

|S(z_{1})| > n cos φ_{1}, |S(z_{2})| > n cos φ_{2}, and 0 ≤ φ_{1}, φ_{2}, φ_{1} + φ_{2} ≤ π/2. (20)

(See [Y73, Lemma 1].) Consider the subsets of 𝔽_{p}

E(φ) := {z ∈ 𝔽_{p}: |S(z)| > n cos φ},

so that T (φ) = |E(φ)| − 1. What (19) and (20) mean is

E(φ_{1}) + E(φ_{2}) ⊆ E(φ_{1} + φ_{2}),

provided 0 ≤ φ_{1}, φ_{2}, φ_{1} + φ_{2} ≤ π/2. By Cauchy-Davenport theorem we have then

|E(φ_{1} + φ_{2})| ≥ min{|E(φ_{1})| + |E(φ_{2})| − 1, p},

and the result follows. □

Proof of Lemma 2. We assume 0 < φ_{0} < φ ≤ π/2, as otherwise the assertion is trivial. Let j = ⌊φ/φ_{0}⌋; then 0 < jφ_{0} ≤ φ ≤ π/2 and by Lemma 1,

T (φ) ≥ T (jφ_{0}) ≥ min{jT (φ_{0}), p − 1}.

Thus, the desired estimate follows unless

⌊\frac{φ}{φ_{0}} ⌋ T (φ_{0}) ≥ p,  (21)

and we suppose (21) to hold for the rest of the proof. We define

l := ⌊\frac{p − 1}{T (φ_{0})}⌋ ≥ 1,

so that

lT (φ_{0}) ≤ p − 1  (22)

whence, by (21),

l ≤ ⌊\frac{φ}{φ_{0}} ⌋ − 1,  (23)

and therefore,

lφ_{0} < φ ≤ π/2.  (24)

Now by Lemma 1, (22), and (24), T (iφ_{0}) ≥ iT (φ_{0}) for i = 1, …, l, and it follows that there exist l pairwise disjoint residue sets E_{1}, …, E_{l} ⊆ 𝔽_{p}^{×} such that |E_{1}| = … = |E_{l}| = T (φ_{0}) and |S(z)| > n cos(iφ_{0}) for z ∈ E_{i}. We conclude that

n(p − n) = ∑_{z=1}^{p−1} |S(z)|^{2}
≥ n^{2}(cos^{2} φ_{0} + ⋯ + cos^{2}(lφ_{0}))T (φ_{0})
= n^{2} (\frac{1}{2} l + \frac{1}{4} \frac{sin(2l + 1) φ_{0} − sin φ_{0}}{sin φ_{0}} ) T (φ_{0}).  (25)

Also, by (23),

(2l + 1)φ_{0} ≤ 2φ − φ_{0} ≤ π − φ_{0},

whence

sin(2l + 1) φ_{0} ≥ sin φ_{0}.  (26)

LINEAR EQUATIONS & EXPONENTIAL SUMS 19

From (25) and (26),

p − n ≥ \frac{1}{2} nlT (φ_{0}),  (27)

\frac{p − n}{T (φ_{0})} ≥ \frac{n}{2} l ≥ 2l ≥ 2 ⌊\frac{p − n}{T (φ_{0})}⌋ ,

⌊\frac{p − n}{T (φ_{0})}⌋ ≤ \{\frac{p − n}{T (φ_{0})}\} ,

T (φ_{0}) > p − n.

The latter inequality, however, contradicts (27). □

In the course of the proof of Theorems 4 and 5 we need estimates of the Euler beta function

B(u, v) = ∫_{0}^{1} t^{u−1}(1 − t)^{v−1} dt.

Lemma 10. For k > 0,

B(k, 3/2) < \frac{\sqrt{π}}{2} k^{−3/2},
B(k, 5/2) < \frac{3\sqrt{π}}{4} k^{−5/2}.

Proof.

B(k, 3/2) = ∫_{0}^{1} t^{1/2} \frac{−1}{k} ((1 − t)^{k})′ dt

= \frac{1}{2k} ∫_{0}^{1} t^{−1/2}(1 − t)^{k} dt < \frac{1}{2k} ∫_{0}^{1} t^{−1/2}e^{−kt} dt = \frac{1}{2} k^{−3/2} ∫_{0}^{k} τ^{−1/2}e^{−τ} dτ

< \frac{1}{2} k^{−3/2}Γ(1/2) = \frac{\sqrt{π}}{2} k^{−3/2}.

Similarly,

B(k, 5/2) = ∫_{0}^{1} t^{3/2} \frac{−1}{k} ((1 − t)^{k})′ dt

= \frac{3}{2k} ∫_{0}^{1} t^{1/2}(1 − t)^{k} dt < \frac{3}{2k} ∫_{0}^{1} t^{1/2}e^{−kt} dt = \frac{3}{2} k^{−5/2} ∫_{0}^{k} τ^{1/2}e^{−τ} dτ

< \frac{3}{2} k^{−5/2}Γ(3/2) = \frac{3\sqrt{π}}{4} k^{−5/2}.

□

We prove Theorems 4 and 5 together.

Proof of Theorems 4 and 5. Using partial summation, we write

∑_{z=1}^{p−1} |S(z)|^{k} = kn^{k} ∫_{0}^{π/2} T (φ) cos^{k−1} φ sin φ dφ,

∑_{z=1}^{p−1} |S_{0}(z)|^{k} = kn^{k} ∫_{0}^{π/2} T_{0}(φ) cos^{k−1} φ sin φ dφ,  (28)

and we denote the integrals in the right-hand sides by I and I_{0}, respectively. Since |S(0)| = |S_{0}(0)|, by Corollary 2 we have

I ≤ I_{0}  (29)

for k even. We first estimate I_{0}.

By Corollary 3 and Lemmas 9 and 10,

I_{0} ≤ \frac{2}{π} \frac{p}{n} (1 + \frac{1}{n^{2}} ) ∫_{0}^{π/3} G^{−1}(cos φ) cos^{k−1} φ sin φ dφ
+ cos^{k−2}(π/3) ∫_{π/3}^{π/2} T_{0}(φ) cos φ sin φ dφ

≤ \frac{2}{π} \frac{p}{n} (1 + \frac{1}{n^{2}} ) ∫_{1/2}^{1} t^{k−1}G^{−1}(t) dt + 2^{2−k} ∫_{0}^{π/2} T_{0}(φ) cos φ sin φ dφ

≤ \frac{2\sqrt{6}}{π} \frac{p}{n} (1 + \frac{1}{n^{2}} ) (∫_{1/2}^{1} t^{k−1}(1 − t)^{1/2} dt + \frac{1}{4} ∫_{1/2}^{1} t^{k−1}(1 − t)^{3/2} dt)

+ 2^{2−k} \frac{n(p − n)}{2n^{2}}

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

Using elementary calculus, one can easily derive the two following estimates:

I_{0} ≤ \sqrt{\frac{6}{π}} \frac{p}{n} k^{−3/2} (1 + \frac{1}{n^{2}} ) (1 + \frac{4}{k}); k ≥ 2,

and

I_{0} ≤ \sqrt{\frac{6}{π}} \frac{p}{n} k^{−3/2} (1 + \frac{1}{n^{2}} ) (1 + \frac{2}{5k} ); k ≥ 16.  (30)

The first estimate, in view of (28), proves Theorem 4, and we proceed with the proof of Theorem 5. Fix φ_{0} ∈ (0, π/6]. Our plan is to apply Lemma 2 to show that large value of T (φ_{0}) results in a large value of I, while I cannot be “too large” by (29) and (30). Indeed, for k ≥ 16 even, by Lemma 2 and using Stirling formula we have

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

≥ \frac{T (φ_{0})}{φ_{0}} ∫_{0}^{π/2} \frac{−1}{k} φ (cos^{k} φ)′ dφ − T (φ_{0}) ∫_{0}^{π/2} \frac{−1}{k} (cos^{k} φ)′ dφ

= \frac{1}{k} \frac{T (φ_{0})}{φ_{0}} ∫_{0}^{π/2} cos^{k} φ dφ − \frac{1}{k} T (φ_{0})

= \frac{1}{k} \frac{T (φ_{0})}{φ_{0}} 2^{−k}\binom{k}{k/2} \frac{π}{2} − \frac{1}{k} T (φ_{0})

≥ \sqrt{\frac{π}{2}} k^{−3/2} \frac{T (φ_{0})}{φ_{0}} e^{−1/3k} − \frac{1}{k} T (φ_{0})

= \sqrt{\frac{π}{2}} k^{−3/2} \frac{T (φ_{0})}{φ_{0}} (1 − \sqrt{\frac{2}{π}} e^{1/3k}φ_{0}\sqrt{k}) e^{−1/3k}

> \sqrt{\frac{π}{2}} k^{−3/2} \frac{T (φ_{0})}{φ_{0}} (1 − \frac{5}{6} φ_{0}\sqrt{k}) e^{−1/3k}.

Along with (29) and (30), this yields

\sqrt{\frac{π}{2}} k^{−3/2} \frac{T (φ_{0})}{φ_{0}} (1 − \frac{5}{6} φ_{0}\sqrt{k}) e^{−1/3k} < \sqrt{\frac{6}{π}} \frac{p}{n} k^{−3/2} (1 + \frac{1}{n^{2}} ) (1 + \frac{2}{5k} ) .

Using the inequality

(1 + \frac{2}{5k} ) e^{1/3k} < 1 + \frac{3}{4k} (k ≥ 16)

and replacing for brevity φ_{0} by φ, we get

T (φ) < \frac{2\sqrt{3}}{π} \frac{p}{n} φ (1 + \frac{1}{n^{2}} ) \frac{1 + \frac{3}{4k}}{1 − \frac{5}{6} φ\sqrt{k}} .  (31)

We now recall the estimate of [L98, Lemma 2]:

T (φ) < \frac{4}{π} \frac{p}{n} φ(1 + φ); 0 < φ ≤ π/6.

This supersedes Theorem 5 for φ ≥ 0.03, and therefore we assume φ < 0.03.

To optimize by k in (31) we choose k = 2⌈0.75φ^{−2/3}⌉; this leads to k ≥ 16 by the above assumption that φ < 0.03. We have

\frac{1 + \frac{3}{4k}}{1 − \frac{5}{6} φ\sqrt{k}} = 1 + \frac{\frac{3}{4k} + \frac{5}{6} φ\sqrt{k}}{1 − \frac{5}{6} φ\sqrt{k}} ,  (32)

and

\frac{3}{4k} + \frac{5}{6} φ\sqrt{k} ≤ \frac{1}{2} φ^{2/3} + \frac{5}{6} φ\sqrt{2 + \frac{3}{2} φ^{−2/3}}

= φ^{2/3} (\frac{1}{2} + \frac{5}{6} \sqrt{\frac{3}{2} + 2φ^{2/3}} )

≤ \frac{8}{5} φ^{2/3},

1 − \frac{5}{6} φ\sqrt{k} > 1 − \frac{5}{6} φ\sqrt{2 + \frac{3}{2} φ^{−2/3}}

= 1 − \frac{5}{6} φ^{2/3}\sqrt{\frac{3}{2} + 2φ^{2/3}}

> \frac{8}{9}.

The result now follows from (31) and (32). □

References

[G32] R.M. Gabriel, The rearrangement of positive Fourier coefficients, Proc. London Math. Soc. (Second Series) 33 (1932), 32–51.

[HL28] G.H. Hardy and J.E. Littlewood, Notes on the theory of series (VIII): an inequality, J. London Math. Soc. 3 (1928), 105–110.

[HLP88] G.H. Hardy, J.E. Littlewood and G. Polya, Inequalities, 2d ed., Camb. Univer. Press, 1988.

[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.

[MO79] A.W. Marshall and I. Olkin, Inequalities: theory of majorization and its applications, Academic Press, 1979.

[P74] J.M. Pollard, Addition properties of residue classes, J. London Math. Soc. 2 (11) (1975), 147–152. 460–462.

[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.

Institute of Mathematics, Hebrew University, Jerusalem 91904, Israel.

E-mail address: seva@math.huji.ac.il