ON THE NUMBER OF SOLUTIONS OF A LINEAR EQUATION OVER FINITE SETS

VSEVOLOD F. LEV

Abstract. The largest possible number of representations of an integer in the k-fold sumset kA = A + ⋯ + A is maximal for A being an arithmetic progression.

More generally, consider the number of solutions of the linear equation

c_{1}a_{1} + ⋯ + c_{k}a_{k} = λ,

where c_{i} ≠ 0 and λ are fixed integer coefficients, and where the variables a_{i} range over finite sets of integers A_{1}, …, A_{k}. We prove that for fixed cardinalities n_{i} = |A_{i}|, this number of solutions is maximal when c_{1} = … = c_{k} = 1, λ = 0 and the A_{i} are arithmetic progressions balanced around 0 and with the same common difference.

For the corresponding residues problem, assuming c_{i}, λ ∈ 𝔽_{p} and A_{i} ⊆ 𝔽_{p} (where 𝔽_{p} is the set of residues modulo prime p), the number of solutions of the equation above does not exceed

\frac{1}{p} n_{1} … n_{k} + \sqrt{\frac{8}{π}} \frac{n_{1} … n_{k}}{\sqrt{n_{1}^{2} + ⋯ + n_{k}^{2}}} (1 + o(1))

as k → ∞ and under some mild restrictions on n_{i}. This is best possible save for the constant in the second term: we conjecture that in fact 8 can be replaced by 6.

1. Introduction

In [1], Erdős and Moser asked for the largest possible number of subsets of a given set of integers A sharing a common sum of elements. The problem appeared to be difficult and its solution took about 15 years — see [6, 7]. We consider a similar problem where subset sums are replaced by sumsets (meaning that repetitions of summands are allowed) and the number of summands is a fixed integer k. That is: what is the maximum possible number of solutions of the equation a_{1} + ⋯ + a_{k} = λ for all sets A of a preassigned cardinality |A| and all integers λ? More generally, one can consider the equation

(1)  c_{1}a_{1} + ⋯ + c_{k}a_{k} = λ

2 VSEVOLOD F. LEV

with fixed integer coefficients c_{i} ≠ 0 and λ, when a_{i} are chosen from k potentially distinct sets of integers A_{1}, …, A_{k}. (Here and in the sequel all sets denoted by A, B, C, with or without lower indices, are assumed to be non-empty and finite.) For the case when all the cardinalities |A_{i}| are odd, it follows from a result of Hardy and Littlewood (see [3]) that the number of solutions of (1) can only increase if we replace all c_{i} by 1, λ by 0, and A_{i} by blocks of consecutive integers centered around zero and of the same cardinalities as A_{i}. This was improved by Gabriel (see [2]) whose result implies the same conclusion when one or two of A_{i} may have an even cardinality. Hardy, Littlewood and Gabriel were motivated by possible applications in Fourier analysis. To avoid introducing extra notation, we do not state their results here. The interested reader may find them, as well as extended historical comments, in [4, Chapter X].

In Sections 2–3 below, we solve this extremal problem in the general case, showing that the conclusion above holds true for any cardinalities |A_{i}|. The argument is inspired by that of the classics. Though the original theorem of Gabriel can not be extended to sets of even cardinalities, we show that the corollary we are interested in, can be.

We now introduce some notation. By a balanced set we mean a block of consecutive integers of the form

Ā = {−α, −α + 1, −α + 2, …, α + δ − 1, α + δ}

where α ≥ 0 and δ ∈ {0, ±1}. Obviously, δ is uniquely defined by the set Ā and we write δ = δ(Ā). If |Ā| is odd then necessarily δ(Ā) = 0; if |Ā| is even, there are two possibilities: either δ(Ā) = 1, or δ(Ā) = −1. If A is a set of integers, then Ā will always stand for a balanced set of the same cardinality as A.

For λ ∈ ℤ we denote by N_{λ}(A_{1}, …, A_{k}) the number of solutions of (1) with c_{1} = … = c_{k} = 1, that is the number of representations of λ as a sum a_{1} + ⋯ + a_{k} with a_{i} ∈ A_{i}.

One of the central results of this paper (proved, as all other our results, in subsequent sections) is

Theorem 1. Let A_{1}, …, A_{k} be sets of integers, and assume that Ā_{1}, …, Ā_{k} are balanced and satisfy |δ(Ā_{1}) + ⋯ + δ(Ā_{k})| ≤ 1. Then for any integer λ

N_{λ}(A_{1}, …, A_{k}) ≤ N_{0}(Ā_{1}, …, Ā_{k}).

LINEAR EQUATIONS OVER FINITE SETS 3

The condition |δ(Ā_{1}) + ⋯ + δ(Ā_{k})| ≤ 1 is crucial: it is necessary to avoid “over-weighting” at one end if many of A_{i} have even cardinalities. For the general equation (1) with arbitrary coefficients c_{i}, the estimate follows immediately upon application of Theorem 1 to the sets c_{i}A_{i} = {c_{i}a_{i}: a_{i} ∈ A_{i}}.

Note, that Theorem 1 is trivial for k = 1, and it is almost obvious for k = 2, since in this case

N_{0}(Ā_{1}, Ā_{2}) = min{|Ā_{1}|, |Ā_{2}|} = min{|A_{1}|, |A_{2}|} ≥ N_{λ}(A_{1}, A_{2}).

For a non-negative function f: ℤ → ℝ^{+} with a finite support, let ν_{i}(f) denote the i-th value attained by f, counting downwards from the maximum value. In other words, the sequence ν_{1}(f), ν_{2}(f), ν_{3}(f), … is the rearrangement of the sequence of all the values of f in descending order, and the total number of non-zero elements of this sequence is the cardinality of the support of f. We will write f ≺ g if

ν_{1}(f) + ⋯ + ν_{m}(f) ≤ ν_{1}(g) + ⋯ + ν_{m}(g)

for all positive integers m. In particular, for m = 1 this implies max(f) ≤ max(g). Theorem 1 is superseded by

Theorem 2. Let A_{1}, …, A_{k} be sets of integers, and assume that Ā_{1}, …, Ā_{k} are balanced and satisfy |δ(Ā_{1}) + ⋯ + δ(Ā_{k})| ≤ 1. Then

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

For k = 1 this theorem becomes trivial.

The following (intuitively obvious) lemma will allow us to relate Theorems 1 and 2.

Lemma 1. Let Ā_{1}, …, Ā_{k} be any balanced sets, and write for brevity N_{λ} instead of N_{λ}(Ā_{1}, …, Ā_{k}). Then

i) If 0 ≤ δ(Ā_{1}) + ⋯ + δ(Ā_{k}) ≤ 1 then

N_{0} ≥ N_{1} ≥ N_{−1} ≥ N_{2} ≥ N_{−2} ≥ ⋯

ii) If −1 ≤ δ(Ā_{1}) + ⋯ + δ(Ā_{k}) ≤ 0 then

N_{0} ≥ N_{−1} ≥ N_{1} ≥ N_{−2} ≥ N_{2} ≥ ⋯

Again, for k = 1 the assertion is trivial.

Note, that using Lemma 1 we can easily deduce Theorem 1 from Theorem 2 as follows: by the lemma, max(N(Ā_{1}, …, Ā_{k})) = N_{0}(Ā_{1}, …, Ā_{k}) and therefore

4 VSEVOLOD F. LEV

by Theorem 2,

N_{λ}(A_{1}, …, A_{k}) ≤ max(N(A_{1}, …, A_{k})) ≤ max(N(Ā_{1}, …, Ā_{k}))
= N_{0}(Ā_{1}, …, Ā_{k}).

The problem, however, is that we need Theorem 1 to prove Theorem 2; for this reason we have to employ more sophisticated logic — see Section 2.

Unfortunately, the elementary method we use seems to be non-applicable for equations modulo a prime p. However, using trigonometric sums in the way which can be characterized as “inverse to that used in [8]”, we are able to prove the following result.

Theorem 3. Let p be an odd prime, and let c_{1}, …, c_{k} ∈ 𝔽_{p}^{×}, λ ∈ 𝔽_{p}, A_{1}, …, A_{k} ⊆ 𝔽_{p}. Define

κ = min_{1≤i≤k} \frac{n_{1}^{2} + ⋯ + n_{k}^{2}}{n_{i}^{2}} ,

where n_{i} = |A_{i}|, and suppose that n_{i} ≥ 2 (i = 1, …, k) and κ ≥ 2. Then the number of solutions of (1) satisfies

N_{λ}(A_{1}, …, A_{k}) ≤ \frac{1}{p} n_{1} … n_{k}

+ \sqrt{\frac{8}{π}} \frac{n_{1} … n_{k}}{\sqrt{n_{1}^{2} + ⋯ + n_{k}^{2}}} (1 + 2κ^{−1/2} + (3/4)^{κ/2−2}κ^{3/2}) .

The assumption κ ≥ 2 can be dropped if we sacrifice the accuracy of the main term.

Theorem 3′. Under the notation of Theorem 3 and assuming only n_{i} = |A_{i}| ≥ 2 (i = 1, …, k), we have

N_{λ}(A_{1}, …, A_{k}) ≤ \frac{1}{p} n_{1} … n_{k}

+ \sqrt{\frac{8}{πk}} (n_{1} … n_{k})^{1−1/k} (1 + 2k^{−1/2} + (3/4)^{k/2+3}k^{3/2}) .

In the important particular case when all n_{i} are equal, the main terms in Theorems 3 and 3′ coincide, and then the latter theorem is preferable as it gives a somewhat better remainder term.

The estimates of Theorems 3 and 3′ are nearly best possible. By the averaging argument, one always has max(N(A_{1}, …, A_{k})) ≥ \frac{1}{p} n_{1} … n_{k}, and if n_{1}, …, n_{k} ≫ p this shows that the first summand can not be dropped. On the other hand, if n = 2α + 1 and A_{i} = {−α, −α + 1, …, α} ( mod p) (i = 1, …, k), where kα < p, then the number of solutions of

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

in 𝔽_{p} is the same as in ℤ, and this number for fixed n and k → ∞ is known to be asymptotically

\sqrt{\frac{6}{πk}} n^{k−1}

(see, for instance, [5, Section 2.3, Example 1]). Therefore, the only improvement of the estimate of Theorems 3 and 3′ can be in the multiplicative constant of the second summand and the remainder term.

Theorems 3 and 3′ are proved in Section 4. Their proofs are based on the following lemma, which may be of independent interest.

Lemma 2. Let A be a set of n = |A| ≥ 2 residues modulo an odd prime p. For z ∈ 𝔽_{p}, write

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

Next, for φ ∈ [0, π/2] denote

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

Then

|E(φ)| < \frac{4}{π} \frac{p}{n} φ (1 + φ)

provided 0 < φ ≤ π/6.

For the supposedly extremal case A = {1, 2, …, n} ( mod p) and assuming n → ∞ and φ → 0, it is not difficult to see that

|E(φ)| = \frac{2\sqrt{3}}{π} \frac{p}{n} φ (1 + o(1)).

It is the discrepancy in the constant of Lemma 2 that causes the discrepancy in the constant of Theorems 3 and 3′. In fact, the problems of establishing sharp constants in Lemma 2 and these theorems are equivalent.

As to the constant π/6 and the factor 1+φ, they both are of technical nature and can be improved at the expense of each other.

6 VSEVOLOD F. LEV

2. Interconnections between Theorems 1 and 2 and Lemma 1

It will be convenient to consider Theorems 1, 2 and Lemma 1 as sequences of theorems and lemmas for all positive integers k and refer them as Theorem 1(k), Lemma 1(k − 1) etc.

We show in this section that

– Theorem 1(k) implies Lemma 1(k − 1) and Theorem 2(k − 1);

– Lemma 1(k − 1) along with Theorem 2(k − 1) imply Theorem 1(k + 1), provided we have already established Lemma 1(2) and Theorem 2(2).

This can be illustrated by the following diagram:

[figure: Theorem 1(k); Lemma 1(k − 1); Theorem 2(k − 1); Theorem 1(k + 1); Lemma 1(2), Theorem 2(2)]

Theorem 1(k) implies Lemma 1(k − 1). Let Ā_{1}, …, Ā_{k−1} be the sets of Lemma 1(k − 1), and assume for definiteness that 0 ≤ δ(Ā_{1}) + ⋯ + δ(Ā_{k−1}) ≤ 1. Let A be any set of integers, and let Ā be the corresponding balanced set such that

(2)  δ(Ā) ≤ 0.

Then

∑_{a∈A} N_{a}(Ā_{1}, …, Ā_{k−1}) = N_{0}(Ā_{1}, …, Ā_{k−1}, −A)

≤ N_{0}(Ā_{1}, …, Ā_{k−1}, Ā) (by Theorem 1(k))

= ∑_{a∈Ā} N_{−a}(Ā_{1}, …, Ā_{k−1}).

For |A| = m this shows (in view of (2)) that ν_{1}(N(Ā_{1}, …, Ā_{k−1})) + ⋯ + ν_{m}(N(Ā_{1}, …, Ā_{k−1})) is the sum of the first m terms of the sequence

N_{0}(Ā_{1}, …, Ā_{k−1}), N_{1}(Ā_{1}, …, Ā_{k−1}), N_{−1}(Ā_{1}, …, Ā_{k−1}), N_{2}(Ā_{1}, …, Ā_{k−1}), N_{−2}(Ā_{1}, …, Ā_{k−1}), …

and the lemma follows. □

Theorem 1(k) implies Theorem 2(k − 1). Let Ā_{1}, …, Ā_{k−1} be the sets of Theorem 2(k − 1), and assume for definiteness that 0 ≤ δ(Ā_{1}) + ⋯ + δ(Ā_{k−1}) ≤ 1. Let A be any set of integers, and let Ā be the corresponding balanced set such that δ(Ā) ≤ 0. Then

∑_{a∈A} N_{a}(A_{1}, …, A_{k−1}) = N_{0}(A_{1}, …, A_{k−1}, −A)

≤ N_{0}(Ā_{1}, …, Ā_{k−1}, Ā) (by Theorem 1(k))

= ∑_{a∈Ā} N_{−a}(Ā_{1}, …, Ā_{k−1})

≤ ∑_{i=1}^{|A|} ν_{i}(N(Ā_{1}, …, Ā_{k−1}))

and the theorem follows. □

To prove the remaining implication, we need one more lemma.

Lemma 3. Let f, g, F, G: ℤ → ℝ^{+} have finite support and satisfy f ≺ F, g ≺ G. Then for any λ ∈ ℤ,

∑_{u+v=λ} f(u)g(v) ≤ ∑_{i=1}^{∞} ν_{i}(f)ν_{i}(g) ≤ ∑_{i=1}^{∞} ν_{i}(F)ν_{i}(G).

Proof. The first inequality is a particular case of yet another and well-known inequality which, informally speaking, says that the scalar product of two sequences is maximized when they are same-ordered. For the second inequality, it suffices to prove that if h ≺ H and b_{1} ≥ b_{2} ≥ ⋯ ≥ 0, then

(3)  ∑_{i=1}^{∞} ν_{i}(h)b_{i} ≤ ∑_{i=1}^{∞} ν_{i}(H)b_{i}

as applying this twice we obtain

∑_{i=1}^{∞} ν_{i}(f)ν_{i}(g) ≤ ∑_{i=1}^{∞} ν_{i}(f)ν_{i}(G) ≤ ∑_{i=1}^{∞} ν_{i}(F)ν_{i}(G).

Therefore, it remains to prove (3). This can be done by partial summation: for any positive integer M,

∑_{i=1}^{M} ν_{i}(h)b_{i} = ∑_{i=1}^{M−1}(b_{i} − b_{i+1}) ∑_{j=1}^{i} ν_{j}(h) + b_{M} ∑_{j=1}^{M} ν_{j}(h)

≤ ∑_{i=1}^{M−1}(b_{i} − b_{i+1}) ∑_{j=1}^{i} ν_{j}(H) + b_{M} ∑_{j=1}^{M} ν_{j}(H)

= ∑_{i=1}^{M} ν_{i}(H)b_{i}

and the result follows by forcing M to approach infinity. □

Theorem 2(k − 1) and Lemma 1(k − 1) imply Theorem 1(k + 1) for k ≥ 3. Let A_{1}, …, A_{k+1} be the sets of Theorem 1(k + 1), and let Ā_{1}, …, Ā_{k+1} be the corresponding balanced sets. It is easily seen that we always can find two indices i, j such that δ(Ā_{i}) + δ(Ā_{j}) = 0; without loss of generality, we assume i = k, j = k + 1, and hence |δ(Ā_{1}) + ⋯ + δ(Ā_{k−1})| ≤ 1. We have then

N_{λ}(A_{1}, …, A_{k+1}) = ∑_{u+v=λ} N_{u}(A_{1}, …, A_{k−1})N_{v}(A_{k}, A_{k+1})

(by Lemma 3)

≤ ∑_{i=1}^{∞} ν_{i}(N(A_{1}, …, A_{k−1}))ν_{i}(N(A_{k}, A_{k+1}))

(by Theorem 2(k − 1), Theorem 2(2) and Lemma 3)

≤ ∑_{i=1}^{∞} ν_{i}(N(Ā_{1}, …, Ā_{k−1}))ν_{i}(N(Ā_{k}, Ā_{k+1}))

(by Lemma 1(k − 1) and Lemma 1(2))

= ∑_{u+v=0} N_{u}(Ā_{1}, …, Ā_{k−1})N_{v}(Ā_{k}, Ā_{k+1})

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

which was to be proved. □

To run now all the machinery above we have to prove Theorem 1(3). This is the subject of the next section.

LINEAR EQUATIONS OVER FINITE SETS 9

3. Proof of Theorem 1(3)

To simplify the notation, we denote the three sets involved A, B, C (instead of A_{1}, A_{2}, A_{3}), so that the corresponding balanced sets are denoted by Ā, B̄, C̄. Recall, that by the assumptions of the theorem,

(4)  |δ(Ā) + δ(B̄) + δ(C̄)| ≤ 1,

and we have to prove that N_{λ}(A, B, C) ≤ N_{0}(Ā, B̄, C̄). We use induction on the sum of the cardinalities |A| + |B| + |C|.

First, if |A| + |B| + |C| ≤ 5, then min{|A|, |B|, |C|} = 1. Suppose, for instance, |C| = 1. Then δ(C̄) = 0, hence |δ(Ā) + δ(B̄)| ≤ 1 and it follows that

N_{0}(Ā, B̄, C̄) = N_{0}(Ā, B̄) = min{|A|, |B|} ≥ N_{λ}(A, B, C).

Now we assume |A|, |B|, |C| ≥ 2. As (4) shows, of the three numbers δ(Ā), δ(B̄), δ(C̄) at least one is non-positive, and at least one is non-negative; without loss of generality, we can assume

(5)  δ(Ā) ≤ 0,  δ(B̄) ≥ 0.

We define −α, −β, −γ to be the minimum elements of Ā, B̄, C̄, respectively, so that

Ā = {−α, −α + 1, …, α + δ(Ā)},
B̄ = {−β, −β + 1, …, β + δ(B̄)},
C̄ = {−γ, −γ + 1, …, γ + δ(C̄)},

and consider separately two cases. I. Suppose first that

γ ≥ α + β + max{−δ(C̄), δ(Ā) + δ(B̄)}.

Then it is easily seen that to each pair a ∈ Ā, b ∈ B̄ there corresponds c ∈ C̄ such that a + b + c = 0, and therefore

N_{0}(Ā, B̄, C̄) = |Ā||B̄| = |A||B| ≥ N_{λ}(A, B, C)

for any λ ∈ ℤ. II. It remains to consider the case

γ ≤ α + β + max{−δ(C̄), δ(Ā) + δ(B̄)} − 1.

Since

max{−δ(C̄), δ(Ā) + δ(B̄)} − min{−δ(C̄), δ(Ā) + δ(B̄)} = |δ(Ā) + δ(B̄) + δ(C̄)| ≤ 1,

in this second case we clearly have

(6)  γ ≤ α + β + min{−δ(C̄), δ(Ā) + δ(B̄)}.

Let a_{0} = min(A) be the minimal element of A, and denote

A′ = A \ {a_{0}}, Ā′ = Ā \ {−α}.

Similarly, let b_{0} = max(B), and denote

B′ = B \ {b_{0}}, B̄′ = B̄ \ {β + δ(B̄)}

(note the difference in the definitions of Ā′ and B̄′). The sets Ā′ and B̄′ are balanced by (5), and

δ(Ā′) + δ(B̄′) + δ(C̄) = (δ(Ā) + 1) + (δ(B̄) − 1) + δ(C̄) = δ(Ā) + δ(B̄) + δ(C̄),

hence by the induction hypothesis

(7)  N_{λ}(A′, B′, C) ≤ N_{0}(Ā′, B̄′, C̄)

for any integer λ. On the other hand, we show below that

N_{λ}(A, B, C) ≤ N_{λ}(A′, B′, C) + |C|, (8) N_{0}(Ā, B̄, C̄) ≥ N_{0}(Ā′, B̄′, C̄) + |C̄|; (9)

clearly, (7),(8) and (9) will suffice to complete the induction step, as |C| = |C̄|.

The crucial inequality is (8), and it follows from the observation that for every fixed c ∈ C, there exists at most one representation of λ of the form a + b + c with either a = a_{0}, or b = b_{0}: indeed, if

λ = a_{0} + b + c = a + b_{0} + c,

then a − a_{0} = b − b_{0}; but this is possible only if a = a_{0} and b = b_{0} (as a − a_{0} ≥ 0, b − b_{0} ≤ 0), so the representations λ = a_{0} + b + c and λ = a + b_{0} + c actually coincide. This proves (8).

As to (9), we notice that, by (6)

(−α + B̄) ∪ (Ā + (β + δ(B̄))

= {−α − β, …, −α + β + δ(B̄), …, (α + δ(Ā)) + (β + δ(B̄))}

⊇ {−γ − δ(C̄), …, γ} = −C̄.

LINEAR EQUATIONS OVER FINITE SETS 11

Therefore, for each c ∈ C̄ there exists a representation of 0 either of the form 0 = −α + b + c (with some b ∈ B̄), or of the form 0 = a + (β + δ(B̄)) + c (with some a ∈ Ā), and (9) is proved.

4. Proof of Theorems 3 and 3′

We first show how to deduce Theorems 3′ and 3 (in the indicated order) assuming Lemma 2 and then prove that lemma.

For j = 1, …, k, denote

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

and let a_{j} vary over all the elements of A_{j}. Then using the standard trigonometric sums technique and applying the inequality of Hölder we obtain

N_{λ}(A_{1}, …, A_{k}) = \frac{1}{p} ∑_{a_{1},...,a_{k}} ∑_{z=0}^{p−1} e^{2πi \frac{c_{1}a_{1}+···+c_{k}a_{k}−λ}{p} z}

= \frac{1}{p} n_{1} … n_{k} + \frac{1}{p} ∑_{z=1}^{p−1} S_{1}(c_{1}z) … S_{k}(c_{k}z) e^{−2πi \frac{λz}{p}}

≤ \frac{1}{p} n_{1} … n_{k} + \frac{1}{p} ∏_{j=1}^{k} (∑_{z=1}^{p−1} |S_{j}(z)|^{k})^{1/k} . (10)

Let A be one of the sets A_{j}, denote n = |A| and let S(z) be the corresponding trigonometric sum. Using partial summation we write

∑_{z=1}^{p−1} |S(z)|^{k} = ∫_{0}^{∞} K(t) dt,

where

K(t) = #{z ∈ 𝔽_{p}^{×}: |S(z)|^{k} > t}.

Evidently, K(t) = 0 if t ≥ n^{k}. This allows us to change to another variable of integration φ, defined by t = (n cos φ)^{k} and varying in the range [0, π/2]. We have then

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

T (φ) being defined by

T (φ) = #{z ∈ 𝔽_{p}^{×}: |S(z)| > n cos φ}.

12 VSEVOLOD F. LEV

We notice now that the set in the right-hand side is precisely the set E(φ) of Lemma 2, therefore T (φ) satisfy the estimate of this lemma and we proceed as follows. By (11) and Lemma 2,

(12)  ∑_{z=1}^{p−1} |S(z)|^{k} ≤ I_{0} + I_{1} + I_{2},

where

I_{0} = \frac{4}{π} kn^{k−1}p ∫_{0}^{π/6} φ cos^{k−1} φ sin φ dφ,
I_{1} = \frac{4}{π} kn^{k−1}p ∫_{0}^{π/6} φ^{2} cos^{k−1} φ sin φ dφ,
I_{2} = kn^{k} ∫_{π/6}^{π/2} cos^{k−1} φ sin φ T (φ) dφ.

The first two integrals can be estimated using the elementary inequality cos φ ≤ e^{−φ^{2}/2} (0 ≤ φ ≤ π/2):

I_{0} ≤ \frac{4}{π} n^{k−1}p ∫_{0}^{π/2} φ(− cos^{k} φ)′ dφ

= \frac{4}{π} n^{k−1}p ∫_{0}^{π/2} cos^{k} φ dφ

≤ \frac{4}{π} n^{k−1}p ∫_{0}^{∞} e^{−kφ^{2}/2} dφ

= \frac{4}{π\sqrt{k}} n^{k−1}p ∫_{0}^{∞} e^{−t^{2}/2} dt

= \sqrt{\frac{8}{πk}} n^{k−1}p, (13)

LINEAR EQUATIONS OVER FINITE SETS 13

I_{1} ≤ \frac{4}{π} n^{k−1}p ∫_{0}^{π/2} φ^{2}(− cos^{k} φ)′ dφ

= \frac{8}{π} n^{k−1}p ∫_{0}^{π/2} φ cos^{k} φ dφ

≤ \frac{8}{π} n^{k−1}p ∫_{0}^{∞} φe^{−kφ^{2}/2} dφ

= \frac{8}{π} n^{k−1}p ∫_{0}^{∞} e^{−kt} dt

= \frac{8}{πk} n^{k−1}p

< \sqrt{\frac{8}{πk}} \frac{2}{\sqrt{k}} n^{k−1}p. (14)

The remaining integral I_{2} can be estimated using (11) with k = 2 “in the opposite direction”:

I_{2} ≤ kn^{k} cos^{k−2}(π/6) ∫_{0}^{π/2} cos φ sin φ T (φ) dφ

= kn^{k}(3/4)^{(k−2)/2} \frac{1}{2n^{2}} ∑_{z=1}^{p−1} |S(z)|^{2}

= \frac{1}{2}(3/4)^{k/2−1}kn^{k−1}(p − n)

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

From (12)–(15) we get

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

and the assertion of Theorem 3′ follows from (10).

To prove Theorem 3, we define

κ_{j} = \frac{n_{1}^{2} + ⋯ + n_{k}^{2}}{n_{j}^{2}} (j = 1, …, k)

so that

∑_{j=1}^{k} \frac{1}{κ_{j}} = 1, κ = min_{1≤j≤k} κ_{j},

and in (10) use the weighted Hölder’s inequality to obtain

(16)  N_{λ}(A_{1}, …, A_{k}) ≤ \frac{1}{p} n_{1} … n_{k} + \frac{1}{p} ∏_{j=1}^{k} (∑_{z=1}^{p−1} |S_{j}(z)|^{κ_{j}})^{1/κ_{j}} .

The internal sums can be estimated precisely in the same way as in the proof of Theorem 3′:

∑_{z=1}^{p−1} |S_{j}(z)|^{κ_{j}} ≤ \sqrt{\frac{8}{πκ_{j}}} n_{j}^{κ_{j}−1}p (1 + 2κ_{j}^{−1/2} + (3/4)^{κ_{j}/2+3}κ_{j}^{3/2}).

(To estimate the integral I_{2} we need the condition κ_{j} ≥ 2 which follows from κ ≥ 2.) Thus, the second summand in (16) can be estimated by

\sqrt{\frac{8}{π}} n_{1} … n_{k} ∏_{j=1}^{k}(κ_{j}^{1/2}n_{j})^{−1/κ_{j}} ∏_{j=1}^{k} (1 + 2κ_{j}^{−1/2} + (3/4)^{κ_{j}/2+3}κ_{j}^{3/2})^{1/κ_{j}}

≤ \sqrt{\frac{8}{π}} \frac{n_{1} … n_{k}}{\sqrt{n_{1}^{2} + ⋯ + n_{k}^{2}}} max_{1≤j≤k} (1 + 2κ_{j}^{−1/2} + (3/4)^{κ_{j}/2+3}κ_{j}^{3/2})

≤ \sqrt{\frac{8}{π}} \frac{n_{1} … n_{k}}{\sqrt{n_{1}^{2} + ⋯ + n_{k}^{2}}} (1 + 2κ^{−1/2} + max_{1≤j≤k}(3/4)^{κ_{j}/2+3}κ_{j}^{3/2}) .

To complete the proof of Theorem 3 it remains to explain the inequality

(17)  max_{1≤j≤k}(3/4)^{κ_{j}/2+3}κ_{j}^{3/2} ≤ (3/4)^{κ/2−2}κ^{3/2}.

To this end, we consider

f(x) = (3/4)^{x/2+3}x^{3/2}.

This function increases on the interval [2, x_{0}] and decreases on [x_{0}, ∞), where x_{0} = 3/ log(4/3) ≈ 10.4. Therefore, if κ ≥ x_{0} then for all j

f(κ_{j}) ≤ f(κ) < (3/4)^{κ/2−2}κ^{3/2},

and otherwise 2 ≤ κ ≤ x_{0} so that

f(κ_{j}) ≤ f(x_{0}) ≤ \frac{f(x_{0})}{f(2)} f(κ) < 3.6f(κ)
< (3/4)^{−5}f(κ) = (3/4)^{κ/2−2}κ^{3/2}.

We now turn to the proof of Lemma 2. For n = 2 we have |S(z)| = 2| cos π(a_{2} − a_{1})z/p|, and the assertion can be easily verified.

LINEAR EQUATIONS OVER FINITE SETS 15

Suppose n ≥ 3. We use the following observation ([8, Lemma 1]): if |S(z_{1})| ≥ n cos φ_{1} and |S(z_{2})| ≥ n cos φ_{2}, where 0 ≤ φ_{1}, φ_{2}, φ_{1} + φ_{2} ≤ π/2, then

|S(z_{1} + z_{2})| ≥ n cos(φ_{1} + φ_{2}).

Defining E_{0}(φ) = E(φ) ∪ {0}, one can rewrite this as

E_{0}(φ_{1}) + E_{0}(φ_{2}) ⊆ E_{0}(φ_{1} + φ_{2}),

and then by the theorem of Cauchy-Davenport

|E_{0}(φ_{1} + φ_{2})| ≥ min{|E_{0}(φ_{1})| + |E_{0}(φ_{2})| − 1, p}.

Since |E_{0}(φ)| = T (φ) + 1, this means

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

Iterating, we obtain

(18)  T (jφ) ≥ min{jT (φ), p − 1}

for any positive integer j, provided jφ ≤ π/2.

Assume that l is a positive integer satisfying

(19)  l T (φ) ≤ p − 1,  lφ ≤ \frac{π}{2} .

Then applying (18) subsequently with j = 1, …, l and recalling the definition of T (φ) we see that there exist l pairwise non-intersecting sets of residues E_{1}, …, E_{l} such that |E_{j}| = T (φ) and E_{j} ⊆ E(jφ) (for all j = 1, …, l). It follows that

n(p − n) = ∑_{z=1}^{p−1} |S(z)|^{2} ≥ n^{2}(cos^{2} φ + ⋯ + cos^{2} lφ)T (φ)

(20) = n^{2} (\frac{1}{2}l + \frac{1}{4} \frac{sin(2l + 1)φ − sin φ}{sin φ}) T (φ)

(we omit the routine evaluation of cosines squares sum). Moreover, this shows that

(21)  \frac{p − n}{T (φ)} ≥ n cos^{2} φ > 2.

We proceed by cases. I. First, suppose that

(22)  ⌊\frac{π}{2φ}⌋ T (φ) ≥ p.

16 VSEVOLOD F. LEV

We show that this case is actually impossible. Indeed, defining then

l = ⌊\frac{p − 1}{T (φ)}⌋

we see that lT (φ) ≤ p − 1, hence by (22)

l ≤ ⌊\frac{π}{2φ}⌋ − 1,

(l + 1)φ ≤ \frac{π}{2} . (23)

Therefore (19) is satisfied and so (20) holds. Next, by (4)

(2l + 1)φ ≤ π − φ,

hence

sin(2l + 1)φ ≥ sin φ

and it follows from (20) that

n(p − n) ≥ \frac{1}{2} T (φ)n^{2}l,

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

which produces a contradiction in view of (21) and n ≥ 3. II. We see, therefore, that

⌊\frac{π}{2φ}⌋ T (φ) ≤ p − 1,

and we define then

l = ⌊\frac{π}{2φ}⌋ .

Condition (19) is clearly satisfied, so (20) holds and we notice that

sin(2l + 1)φ = sin (π + (1 − 2 \{\frac{π}{2φ}\}) φ) = sin (2 \{\frac{π}{2φ}\} − 1) φ.

Thus, (20) implies

np > \frac{1}{4} T (φ)n^{2} (\frac{π}{φ} − 2 + g(φ)) ,

where

g(φ) = \frac{sin (2 \{\frac{π}{2φ}\} − 1) φ}{sin φ} − (2 \{\frac{π}{2φ}\} − 1) .

The function g(φ) can be investigated using elementary calculus, and it is not difficult to see that if φ ≤ π/6, then g(φ) > −0.02. It follows that

4\frac{p}{n} > T (φ) (\frac{π}{φ} − 2.02) ,

T (φ) < \frac{4}{π} \frac{p}{n} φ (1 − \frac{2.02}{π} φ)^{−1} < \frac{4}{π} \frac{p}{n} φ (1 + φ)

as

(1 − \frac{2.02}{π} φ)^{−1} = 1 + \frac{1}{\frac{π}{2.02} − φ} φ ≤ 1 + \frac{1}{\frac{π}{2.02} − \frac{π}{6}} φ < 1 + φ.

This proves the lemma.

5. Acknowledgment

I am indebted to the anonymous referee whose suggestion to use the weighted version of Hölder’s inequality allowed me to upgrade Theorem 3′ to Theorem 3.

References

[1] P. Erdős, Extremal problems in number theory, Amer. Math. Soc. Proc. Symp. Pure Math. 8(1965), 181–189.

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

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

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

[5] A.G. Postnikov, Introduction to Analytic Number Theory, Nauka, Moscow 1971.

[6] R. Proctor, Solution of two difficult combinatorial problems with linear algebra, Amer. Math. Monthly 89(1982), no. 10, 721–734.

[7] R. Stanley, Weyl groups, the hard Lefschetz theorem, and the Sperner property, SIAM J. Algebraic Discrete Methods 1(1980), 168–184.

[8] 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 (pp. 163–174).

Department of Mathematics, The University of Georgia, Athens, GA 30602, USA

  E-mail address: seva@@math.uga.edu