CHARACTER SUMS IN COMPLEX HALF-PLANES

SERGEI V. KONYAGIN AND VSEVOLOD F. LEV

Abstract. Let A be a finite subset of an abelian group G and let P be a closed half-plane of the complex plane, containing zero. We show that (unless A possesses a special, explicitly indicated structure) there exists a non-trivial Fourier coefficient of the indicator function of A which belongs to P. In other words, there exists a non-trivial character χ ∈ Ĝ such that ∑_{a∈A} χ(a) ∈ P.

1. Introduction: the main result

Let G be an abelian group and let Ĝ denote the dual group. For a finite subset A ⊆ G and a character χ ∈ Ĝ we write

S_{A}(χ) := ∑_{a∈A} χ(a);

that is, S_{A}(χ) are Fourier coefficients of the indicator function of A.

Fix A and let χ run over all characters of G. How are the numbers S_{A}(χ) distributed on the complex plane? What can be said about A if S_{A}(χ) exhibit an “irregular” behavior? For instance, when are all S_{A}(χ) situated in the same half-plane? The following theorem is our main result.

Theorem 1. Let P be a closed complex half-plane with zero on its boundary, and let A be a finite subset of an abelian group G. Then either there exists a non-trivial character χ ∈ Ĝ such that S_{A}(χ) ∈ P, or at least one of the following holds:

i) A = {0, g}, where g ∈ G is a non-zero element of odd order; ii) G is finite and A = G \ {0, g}, where g ∈ G is a non-zero element of odd

order; iii) A ∩ (−A) = {0}, and A ∪ (−A) is a finite subgroup of G; iv) G is finite, A∪(−A) = G\{0}, and A∩(−A) is the complement of a subgroup

of G.

For cyclic groups of prime order and torsion-free abelian groups we were able to drop the assumption that P is closed. This yields additional exceptional cases; however,

1991 Mathematics Subject Classification. Primary 11L03; Secondary 11L40.

2 SERGEI V. KONYAGIN AND VSEVOLOD F. LEV

specific features of the groups allow us to put conditions i)–iv) of Theorem 1 in a more explicit form.

Theorem 2. Let P be an open complex half-plane with zero on its boundary and such that P ∩ ℝ ≠ ∅. Suppose that G is a cyclic group of odd prime order, and let A be a non-empty proper subset of G. Then either there exists a non-trivial character χ ∈ Ĝ such that S_{A}(χ) ∈ P, or at least one of the following holds:

i) 0 ∈ A and |A| ≤ 2; ii) 0 ∉ A and |A| ≥ |G| − 2; iii) A ∩ (−A) = {0}, and A ∪ (−A) = G; iv) A ∪ (−A) = G \ {0}, and A ∩ (−A) = ∅.

Theorem 3. Let P be an open complex half-plane with zero on its boundary and such that P ∩ ℝ ≠ ∅. Suppose that G is a torsion-free abelian group, and let A be a finite non-empty subset of G. Then either there exists a non-trivial character χ ∈ Ĝ such that S_{A}(χ) ∈ P, or 0 ∈ A and |A| ≤ 2.

Remark 1. Conditions given in Theorems 1–3 are easily seen to be not only necessary, but also sufficient for a half-plane P to exist so that S_{A}(χ) ∉ P for any non-trivial character χ ∈ Ĝ. For instance, if A satisfies either of the conditions i) and iii) of Theorem 1 and if P = {z ∈ ℂ: ℜ(z) ≤ 0} (the left closed half-plane), then S_{A}(χ) ∉ P for any χ ∈ Ĝ. Indeed, this is obvious for condition i). As to condition iii), suppose that L is a finite subgroup of G and that A ⊆ L satisfies A ∩ (−A) = {0} and A ∪ (−A) = L. Then

2ℜ(S_{A}(χ)) = S_{A}(χ) + S_{−A}(χ) = 1 + S_{L}(χ) ≥ 1,

whence S_{A}(χ) ∉ P. Similarly, it is not difficult to verify that if A satisfies either of the conditions ii) and iv) of Theorem 1 and if P = {z ∈ ℂ: ℜ(z) ≥ 0} (the right closed half-plane), then S_{A}(χ) ∉ P for any non-trivial character χ ∈ Ĝ. We notice also that the sets {0} and G \ {0} satisfy conditions iii) and iv) of Theorem 1.

Remark 2. The assumption P ∩ ℝ = ∅ of Theorems 2 and 3 excludes the situation when P is either the upper or the lower complex half-plane, and A = −A, implying that S_{A}(χ) is real for any χ ∈ Ĝ. In fact, it is easy to see that the condition A = −A is necessary and sufficient for all character sums S_{A}(χ) (χ ∈ Ĝ) to be real.

We derive Theorems 1–3 from a particular case of the first of the three theorems — the case that refers to the left closed half-plane and finite abelian groups. We state it as a separate proposition.

CHARACTER SUMS IN COMPLEX HALF-PLANES 3

Proposition 1. Let A be a subset of a finite abelian group G. Then we have ℜ(S_{A}(χ)) > 0 for all χ ∈ Ĝ if and only if one of the following holds:

i) A = {0, g}, where g ∈ G \ {0} is of odd order; ii) A ∩ (−A) = {0}, and A ∪ (−A) is a subgroup of G.

We prove Proposition 1 in Section 3 (this presents the major difficulty), and then derive Theorems 1–3 in Section 4. The proofs are mostly of combinatorial nature. Two auxiliary geometry of numbers results that we will need are established in the Appendix.

Before we turn to the proofs, we discuss some consequences of Theorems 1–3.

2. Applications

For certain groups G the property in question has a transparent “geometric” interpretation. Say, if A is a subset of the elementary 2-group ℤ_{2}^{r} (where r is a positive integer), then letting H = ker χ we get S_{A}(χ) = |A∩H|−|A\H| = 2(|A∩H|−|A|/2). As χ runs over all non-trivial characters of ℤ_{2}^{r}, the kernel ker χ runs over all index two subgroups of ℤ_{2}^{r}. Thus, |A ∩ H| > |A|/2 for any index two subgroup H if and only if there is no character χ such that S_{A}(χ) belongs to the left closed half-plane, and |A ∩ H| < |A|/2 for any index two subgroup if and only if there is no non-trivial character χ such that S_{A}(χ) belongs to the right closed half-plane. Applying Theorem 1 we obtain the following corollary.

Corollary 1. Let r ≥ 1 be an integer, and let A ⊆ ℤ_{2}^{r}.

i) If A ≠ {0} then there exists an index two subgroup H ≤ ℤ_{2}^{r} such that |A∩H| ≤ |A|/2;

ii) if A ≠ ℤ_{2}^{r} \ {0} then there exists an index two subgroup H ≤ ℤ_{2}^{r} such that |A ∩ H| ≥ |A|/2.

(In fact, it can be shown that there exists an index two subgroup H ≤ ℤ_{2}^{r} such that |A∩H| < |A|/2, unless A is a subgroup itself, and there exists an index two subgroup H ≤ ℤ_{2}^{r} such that |A ∩ H| > |A|/2, unless A is the complement of a subgroup.)

Consider now the elementary 3-group ℤ_{3}^{r}. We have ℜ(S_{A}(χ)) = |A∩H|−|A\H|/2 = \frac{3}{2}(|A ∩ H| − |A|/3), where H = ker χ. As χ runs over all non-trivial characters of ℤ_{3}^{r}, the kernel ker χ runs over all index three subgroups of ℤ_{3}^{r}. Applying Theorem 1 we get

Corollary 2. Let r ≥ 1 be an integer, and let A ⊆ ℤ_{3}^{r}.

4 SERGEI V. KONYAGIN AND VSEVOLOD F. LEV

i) If |A ∩ H| > |A|/3 for all index three subgroups H ≤ ℤ_{3}^{r}, then there exists a subgroup L ≤ ℤ_{3}^{r} such that A ∩ (−A) = {0} and A ∪ (−A) = L;

ii) if |A ∩ H| < |A|/3 for all index three subgroups H ≤ ℤ_{3}^{r}, then there exists a subgroup L ≤ ℤ_{3}^{r} such that A ∪ (−A) = ℤ_{3}^{r} \ {0} and A ∩ (−A) = ℤ_{3}^{r} \ L.

Characters of the additive group of integers are of the form χ: a ↦ e^{2πiaz}, where z ∈ [0, 1). Consequently, applied to this group and the left open half-plane, Theorem 3 yields

Corollary 3. Let T (z) = cos(2πa_{1}z) + ⋯ + cos(2πa_{n}z), where n ≥ 2 and a_{1}, …, a_{n} are pairwise distinct integers. Then min_{z∈[0,1)} T (z) < 0, unless n = 2 and a_{1}a_{2} = 0.

It should be pointed out that Corollaries 1–3 can be established directly, without appealing to Theorems 1 and 3. Howeer, application of these theorems to other groups (like finite cyclic groups) leads to results which we cannot prove in another way.

The problem of estimating the minimum value of the polynomial T (z) of Corollary 3 in terms of n is well-known and is far from being solved; see [BK96]. If a_{1}, …, a_{n} are positive, the best known result for large n is

min_{z∈[0,1]} T (z) ≤ −e^{(ln n)^{δ}}

(where δ is an absolute positive constant), obtained by Bourgain [B86]. For arbitrary integers a_{1}, …, a_{n} it is known that

min_{z∈[0,1]} T (z) ≤ −δ ln n,

see [K81, MPS81a, MPS81b]. To our knowledge, for abelian groups other than the additive group of integers this problem has never been considered.

Several problems on distribution of character sums for cyclic groups of prime order were studied in [KL].

3. Proof of Proposition 1

Throughout this section we assume that G is a finite non-trivial abelian group. (Notice, that Proposition 1 is immediate for the trivial group G = {0}.) By A we denote a non-empty subset of G. We say that A is positive if ℜ(S_{A}(χ)) > 0 for any χ ∈ Ĝ. We want to establish the structure of positive subsets A ⊆ G.

Lemma 1. If A ⊆ G is positive, then 0 ∈ A.

Proof. If χ_{0} denotes the principal character of G, then

|A| = S_{A}(χ_{0}) ≤ ∑_{χ} ℜ(S_{A}(χ)) = ℜ (∑_{a} ∑_{χ} χ(a)) = \begin{cases}0 & if 0 ∉ A, \\ |G| & if 0 ∈ A. \end{cases}

□

Notice that the above computation gives

min_{χ} ℜ(S_{A}(χ)) ≤ (|G| − |A|)/(|G| − 1) ≤ 1,

while our goal is to prove that

min_{χ} ℜ(S_{A}(χ)) ≤ 0

(unless A possesses some special structure).

Observing that for any element g ∈ G of either infinite or even order there exists a character χ ∈ Ĝ such that χ(g) = −1, we obtain

Corollary 4. Suppose that A ⊆ G is positive.

i) If |A| = 1, then A = {0}; ii) if |A| = 2, then A = {0, g}, where g ∈ G \ {0} is of odd order.

We say that A ⊆ G is antisymmetric if A ∩ (−A) ⊆ {0}. If A is antisymmetric and A ∪ (−A) is a finite subgroup of G then we say that A is maximal antisymmetric.

Proposition 1 essentially states that any positive set A of cardinality |A| > 2 is maximal antisymmetric. Though maximality is subtle, the fact that positive sets are antisymmetric is easy to establish.

In the proof of the following lemma and henceforth, we denote by δ_{A} the indicator function of A.

Lemma 2. If A ⊆ G is positive, then it is antisymmetric.

Proof. Fix b ∈ G \ {0}. We have

0 < \frac{1}{|G|} ∑_{χ} ℜ(S_{A}(χ)) |1 − χ(b)|^{2}

= \frac{1}{|G|} ℜ( ∑_{χ} S_{A}(χ) (2 − χ(b) − χ(−b)))

= 2 − δ_{A}(b) − δ_{A}(−b),

hence either b ∉ A, or b ∉ −A. □

Corollary 5. If A ⊆ G is positive, then A ∩ (−A) = {0}. In particular, A does not contain elements of order two.

Lemma 3. Suppose that B ⊆ G is symmetric, contains zero (that is, 0 ∈ B = −B) and satisfies kS_{B}(χ) + 1 ≥ 0 for some fixed integer k ≥ 2 and all characters χ ∈ Ĝ. Then B is a subgroup of G.

Proof. We assume that k = 2, which yields the weakest restriction on B. If |B| = 2 then B = {0, b} where b is of order two and the assertion is trivial. If |B| = 3 then B = {0, −b, b} where b is of order m ≥ 3. Indeed, the case

m = 3 is trivial, while otherwise there exists an mth root of unity, say ζ, such that ℜ(ζ) ≤ cos 4π/5 < −3/4. Accordingly, there exists a character χ ∈ Ĝ such that χ(b) = ζ and then 2S_{B}(χ) + 1 = 4ℜ(ζ) + 3 < 0, a contradiction.

Suppose now that |B| ≥ 4. Let b, c ∈ B, b ≠ ±c. Then

0 ≤ \frac{1}{|G|} ∑_{χ}(2S_{B}(χ) + 1) |1 − χ(b)|^{2}|1 − χ(c)|^{2}  (∗)

= \frac{1}{|G|} ∑_{χ}(2S_{B}(χ) + 1) (2 − χ(b) − χ(−b))(2 − χ(c) − χ(−c))

= 12 − 8δ_{B}(b) − 8δ_{B}(c) + 4δ_{B}(b + c) + 4δ_{B}(b − c)

= 4δ_{B}(b + c) + 4δ_{B}(b − c) − 4.

This shows that b ± c ∈ B, unless each summand in (∗) equals zero. But in this latter case we would have

0 = \frac{1}{|G|} ∑_{χ}(2S_{B}(χ) + 1) (1 − χ(b))(1 − χ(c))

= \frac{1}{|G|} ∑_{χ}(2S_{B}(χ) + 1) (1 − χ(b) − χ(c) + χ(b + c))

= 3 − 2δ_{B}(b) − 2δ_{B}(c) + 2δ_{B}(b + c)

= 2δ_{B}(b + c) − 1

which is impossible.

We see that b + c ∈ B for any b, c ∈ B, provided that c ≠ b. To conclude the proof it suffices to show that 2b ∈ B for any b ∈ B. For this, fix arbitrarily c ∈ B \ {0, ±b}; such c exists as |B| ≥ 4. By the above, b − c, b + c ∈ B. If 2c ≠ 0 then b + c ≠ b − c whence 2b = (b + c) + (b − c) ∈ B. Now suppose that 2c = 0. Since b + c ∈ B and

CHARACTER SUMS IN COMPLEX HALF-PLANES 7

thus also 2b + c = (b + c) + b ∈ B, we have 2b = (2b + c) + c ∈ B unless 2b + c = c. But in this case 2b = 0 ∈ B. □

We now introduce some more notation. Given a set A ⊆ G, we put S^{∗} := A∪(−A) and denote by S^{∗}(χ) the Fourier coefficients, and by δ^{∗} the indicator function of A^{∗}; this allows us to avoid bulky expressions like S_{A^{∗}} and δ_{A^{∗}}. Clearly, if A is antisymmetric and contains zero then |A^{∗}| = 2|A| − 1 and moreover, 2ℜ(S_{A}(χ)) = S_{A}(χ) + S_{−A}(χ) = S^{∗}(χ) + 1. It follows that if A ∩ (−A) = {0}, then for A to be positive it is necessary and sufficient that S^{∗}(χ) + 1 > 0 for any χ ∈ Ĝ.

Lemma 4. Suppose that A ⊆ G is positive. Then for any b, c ∈ A^{∗} at least one of the two elements b + c and b − c belongs to A^{∗}.

Proof. We can assume that b, c, b ± c ≠ 0. Then

∑_{χ}(1 − χ(b))(1 − χ(c)) = |G| > 0,

hence there is a character χ such that both χ(b) and χ(c) are distinct from one. Thus

0 < \frac{1}{|G|} ∑_{χ}(S^{∗}(χ) + 1) |1 − χ(b)|^{2}|1 − χ(c)|^{2}

= \frac{1}{|G|} ∑_{χ}(S^{∗}(χ) + 1) (2 − χ(b) − χ(−b))(2 − χ(c) − χ(−c))

= 8 − 4δ^{∗}(b) − 4δ^{∗}(c) + 2δ^{∗}(b + c) + 2δ^{∗}(b − c)

= 2δ^{∗}(b + c) + 2δ^{∗}(b − c)

implying the result. □

Lemma 5. Suppose that A ⊆ G is positive, and let b − c, b, b + c ∈ A^{∗}. Then c ∈ A^{∗}.

Proof. We can assume that b, c, b ± c ≠ 0. Then, as in the proof of the previous lemma,

0 < \frac{1}{|G|} ∑_{χ}(S^{∗}(χ) + 1) |1 − χ(b)|^{2}|1 + χ(c)|^{2}

= \frac{1}{|G|} ∑_{χ}(S^{∗}(χ) + 1) (2 − χ(b) − χ(−b))(2 + χ(c) + χ(−c))

= 8 − 4δ^{∗}(b) + 4δ^{∗}(c) − 2δ^{∗}(b + c) − 2δ^{∗}(b − c)

= 4δ^{∗}(c)

and the result follows. □

Lemma 6. Suppose that A ⊆ G is positive. If there exists a non-zero element h ∈ G such that A^{∗} + h = A^{∗} (that is, if A^{∗} is periodic), then A is maximal antisymmetric.

Proof. Let H be the set of all h ∈ G satisfying A^{∗} + h = A^{∗}. Clearly, H is a nonzero subgroup of G, and we denote by A^{∗}/H the image of A^{∗} under the canonical homomorphism G → G/H. If χ̃ is a character of G/H and χ is the induced character of G, then

|H| S_{A^{∗}/H}(χ̃) + 1 = S^{∗}(χ) + 1 > 0.

Plainly, 0 ∈ A^{∗}/H and A^{∗}/H is symmetric. By Lemma 3, the set A^{∗}/H is a subgroup of G/H. Since A^{∗} is a union of H-cosets, it is a subgroup of G, as wanted. □

Lemma 7. Suppose that A ⊆ G is positive. If A^{∗} contains a non-zero subgroup H ⊆ G, then A is maximal antisymmetric.

Proof. We fix arbitrarily b ∈ A^{∗} and h ∈ H \ {0} and show that b + h ∈ A^{∗}; the result will follows then from Lemma 6. Assume the opposite: b + h ∉ A^{∗}. Denote by T the set of all those non-negative integers t satisfying b − th ∈ A^{∗}. Clearly, 0 ∈ T. Furthermore, if t ∈ T then applying Lemma 4 to b − th, (t + 1)h ∈ A^{∗} we conclude that 2t + 1 ∈ T. Moreover, if t − 1, t + 1 ∈ T then applying Lemma 5 to b − (t − 1)h, h, −b + (t + 1)h ∈ A^{∗} we obtain t ∈ T. This shows that in fact T contains all non-negative integers: for if t ≥ 1 is the smallest integer which does not belong to T, then t is even and t − 1, t + 1 ∈ T, which is impossible. It remains to observe that h is of finite order, so that there exists t such that b − ht = b + h. □

Lemma 8. Suppose that A ⊆ G is positive. If there exists a ∈ A^{∗} \ {0} such that 2a ∈ A^{∗}, then A^{∗} is maximal antisymmetric.

Proof. By Lemma 7, it suffices to show that A^{∗} contains the cyclic subgroup generated by a. Assuming that this is false, let k ≥ 3 denote the smallest positive integer such that ka ∉ A^{∗}.

Suppose first that k ≥ 4. Applying Lemma 5 with b = a, c = ka we see that (k + 1)a ∉ A^{∗}. Applying Lemma 5 with b = (k − j)a, c = ka for j ∈ {1, 2, 3} we see that (2k − j)a ∉ A^{∗}. Applying Lemma 5 with b = (k − 1)a, c = (2k − 2)a we see that (3k − 3)a ∉ A^{∗}. Since

∑_{χ}(1 − χ((k − 2)a))(1 − χ((k − 1)a))(1 + χ(ka)) = |G| > 0,

it follows that

0 < \frac{1}{|G|} ∑_{χ}(S^{∗}(χ) + 1) |1 − χ((k − 2)a)|^{2}|1 − χ((k − 1)a)|^{2}|1 + χ(ka)|^{2}

= \frac{1}{|G|} ∑_{χ}(S^{∗}(χ) + 1) (2 − χ((k − 2)a) − χ(−(k − 2)a))

· (2 − χ((k − 1)a) − χ(−(k − 1)a))(2 + χ(ka) + χ(−ka))

= 16 − 4δ^{∗}(2a) + 2δ^{∗}((k − 3)a) − 8δ^{∗}((k − 2)a) − 6δ^{∗}((k − 1)a)

+ 8δ^{∗}(ka) + 2δ^{∗}((k + 1)a) + 4δ^{∗}((2k − 3)a)
− 4δ^{∗}((2k − 2)a) − 4δ^{∗}((2k − 1)a) + 2δ^{∗}((3k − 3)a)

= 16 − 4 + 2 − 8 − 6,

a contradiction.

Now suppose that k = 3. Let l be the smallest positive integer such that l ≥ 4 and la ∈ A^{∗}. Applying Lemma 5 with b = a, c = 3a we see that 4a ∉ A^{∗}. Applying Lemma 5 with b = 2a, c = 3a we see that 5a ∉ A^{∗}. Applying Lemma 5 with b = 2a, c = 4a we see that 6a ∉ A^{∗}. Therefore, l ≥ 7. Applying Lemma 4 with b = la, c = a we see that (l + 1)a ∈ A^{∗}. Applying Lemma 4 with b = la, c = 2a we see that (l + 2)a ∈ A^{∗}. Applying Lemma 4 with b = (l + 1)a, c = 2a we see that (l + 3)a ∈ A^{∗}. In view of −3a ∉ A^{∗} (recall that k = 3) this implies that the order of a is either l + 2, or at least l + 7. This gives

∑_{χ}(1 − χ(a))(1 − χ(2a))(1 − χ(la)) ≥ |G| > 0

and it follows that

0 < \frac{1}{|G|} ∑_{χ}(S^{∗}(χ) + 1) |1 − χ(a)|^{2}|1 − χ(2a)|^{2}|1 − χ(la)|^{2}

= \frac{1}{|G|} ∑_{χ}(S^{∗}(χ) + 1) (2 − χ(a) − χ(−a))

· (2 − χ(2a) − χ(−2a))(2 − χ(la) − χ(−la))

= 16 − 4δ^{∗}(a) − 8δ^{∗}(2a) + 4δ^{∗}(3a) − 2δ^{∗}((l − 3)a) + 4δ^{∗}((l − 2)a) + 2δ^{∗}((l − 1)a)

− 8δ^{∗}(la) + 2δ^{∗}((l + 1)a) + 4δ^{∗}((l + 2)a) − 2δ^{∗}((l + 3)a)

= 16 − 4 − 8 − 8 + 2 + 4 − 2,

a contradiction. □

Corollary 6. Any positive set A ⊆ G of cardinality |A| = 3 is maximal antisymmetric.

Proof. Let A = {0, b, c}. By Lemma 2 we have b + c ≠ 0, thus by Lemma 4 at least one of

b + c = −b, b + c = −c, b − c = −b, or b − c = c

holds. In any case we have either 2b = ±c ∈ A^{∗}, or 2c = ±b ∈ A^{∗}, hence A is maximal antisymmetric by Lemma 8. □

We are now in a position to sharpen Lemmas 4 and 5 considerably.

Lemma 9. Suppose that A ⊆ G is positive. Then either A is maximal antisymmetric, or for any b, c ∈ A^{∗} \ {0} exactly one of the two elements b + c and b − c belongs to A^{∗}.

Proof. Assume that both b + c and b − c belong to A^{∗}. Then by Lemma 4 either 2b = (b + c) + (b − c) ∈ A^{∗}, or 2c = (b + c) − (b − c) ∈ A^{∗}. However, if A is not maximal antisymmetric then any of the two conclusions contradict Lemma 8. □

Lemma 10. Suppose that A ⊆ G is positive and let b − c, b, b + c ∈ A^{∗}. Then either A is maximal antisymmetric, or b = 0, or c = 0. That is, either A is maximal antisymmetric, or A^{∗} contains no three-term arithmetic progressions, except those centered at zero.

Proof. By Lemma 5 we have c ∈ A^{∗}, and by Lemma 9 from b + c, b − c ∈ A^{∗} it follows that either A is maximal antisymmetric, or b = 0, or c = 0. □

Lemma 11. Any positive set A ⊆ G of cardinality |A| ≥ 5 is maximal antisymmetric.

Proof. Suppose that A is not maximal antisymmetric. Fix arbitrarily a ∈ A^{∗} \ {0} and b ∈ A^{∗} \ {0, ±a} and observe that by Lemma 9, either b + a ∈ A^{∗}, or b − a ∈ A^{∗}. Replacing b by −b, if necessary, we can assume that b + a ∈ A^{∗}. Notice that b + a ∉ {0, ±a, ±b}: for if b + a = −a then 2a = −b ∈ A^{∗} and if b + a = −b then 2b = −a ∈ A^{∗}, contradicting Lemma 8. Since |A| ≥ 5, there exists an element c ∈ A^{∗} \ {0, ±a, ±b, ±(b + a)}. Similarly to the above, we can assume that c + a ∈ A^{∗} and verify that c+a ∉ {0, ±a, ±b, ±(b+a), ±c}. (Say, if c+a = b then c, c+a, c+2a = b + a ∈ A^{∗}, contradicting Lemma 10; if c + a = −b then c = −(b + a), contradicting the choice of c; if c+a = −(b+a), then c, c+a, c+2a = −b ∈ A^{∗}, again, contradicting Lemma 10.) Thus, {0, ±a, ±b, ±(b + a), ±c, ±(c + a)} ⊆ A^{∗}.

CHARACTER SUMS IN COMPLEX HALF-PLANES 11

We claim that a + b + c ∈ A^{∗}. Indeed, otherwise we would have (a + c) + b ∉ A^{∗}, hence a + c − b ∈ A^{∗} by Lemma 9, and similarly a + b − c ∈ A^{∗}. However, a + c − b, a, and a + b − c are in a progression, which contradicts Lemma 10.

The only property of c we used in the above argument is that {±c, ±(c + a)} ⊆ A^{∗} \ {0, ±a, ±b, ±(b + a)}. Since c′ := −c − a also has this property, we conclude that b − c = a + b + c′ ∈ A^{∗} and therefore b + c ∉ A^{∗} by Lemma 9.

As b−c = (b+a)−(c+a) ∈ A^{∗}, by Lemma 9 we have 2a+b+c = (b+a)+(c+a) ∉ A^{∗}. We have obtained that a + b + c ∈ A^{∗}, whereas (a + b + c) + a = 2a + b + c ∉ A^{∗}

and (a + b + c) − a = b + c ∉ A^{∗}; this, however, is impossible by Lemma 9. □

The assertion of Proposition 1 follows at once from Corollaries 4 and 6, Lemma 11, and our next lemma.

Lemma 12. Any positive set A ⊆ G of cardinality |A| = 4 is maximal antisymmetric.

Proof. The proof is based on two more claims.

Claim 1. Let d ≥ 2 be an integer. Suppose that m, n ∈ ℤ satisfy

m, n, m + n ≢ 0 (mod d) and gcd(m, n, d) = 1.

Then there exists an integer z such that

cos π \frac{mz}{d} cos π \frac{nz}{d} cos π \frac{(m + n)z}{d} ≤ 0,

except if d = 7 and 0, ±m, ±n, ±(m + n) represent all residue classes modulo d.

Claim 2. Let d_{0}, d ≥ 2 be integers such that d_{0} | d. Suppose that m_{0}, n_{0}, m, n ∈ ℤ satisfy

gcd(m, n, d) = gcd(m_{0}n − mn_{0}, d_{0}) = 1.

Then there exist integers z_{0} and z such that

cos π(\frac{m_{0}z_{0}}{d_{0}} + \frac{mz}{d} ) cos π(\frac{n_{0}z_{0}}{d_{0}} + \frac{nz}{d} ) cos π(\frac{(m_{0} + n_{0})z_{0}}{d_{0}} + \frac{(m + n)z}{d} ) ≤ 0.

Remark 3. Though this is not obvious, the two claims are actually geometry of numbers statements. For instance, the former of them asserts that the cyclic twodimensional lattice (m, n)ℤ + dℤ^{2} has a point in the “butterfly area” formed by the two triangles x, y ≤ d/2, x + y ≥ d/2 and x, y ≥ d/2, x + y ≤ (3/2)d. This is the idea underpinning the proof of Claim 1.

12 SERGEI V. KONYAGIN AND VSEVOLOD F. LEV

Postponing the proofs of Claims 1 and 2 until the Appendix, we return to the proof of Lemma 12. Assume that A ⊆ G is a positive set of cardinality |A| = 4 which is not maximal antisymmetric. Fix a ∈ A^{∗} \{0} and b ∈ A^{∗} \{0, ±a}. By Lemma 9 we have either b + a ∈ A^{∗} or b − a ∈ A^{∗}. Replacing b by −b, if necessary, we can assume that b + a ∈ A^{∗}, whence A^{∗} = {0, ±a, ±b, ±(b + a)}. (Observe, that b + a ∉ {0, ±a, ±b} by Lemma 8.) Denote by G_{0} the subgroup of G, generated by a and b. Clearly, A remains positive when considered as a subset of G_{0}.

Suppose first that G_{0} is cyclic. Denote by g its generator and let d = |G_{0}| be the order of g. Choose m, n ∈ ℤ such that a = mg, b = ng. Since a, b, a + b ≠ 0 we have m, n, m + n ≢ 0(mod d). Furthermore, if α and β are integers such that g = αa + βb, then g = (mα + nβ)g whence mα + nβ ≡ 1(mod d) and consequently, gcd(m, n, d) = 1. This shows that the assumptions of Claim 1 are satisfied.

Given an integer z, consider the character χ ∈ Ĝ_{0} that maps g into e^{2πiz/d}. We have

S^{∗}(χ) + 1 = 2 + 2 cos 2π \frac{mz}{d} + 2 cos 2π \frac{nz}{d} + 2 cos 2π \frac{(m + n)z}{d}

= 4 cos π \frac{(m − n)z}{d} cos π \frac{(m + n)z}{d} + 4 cos^{2} π \frac{(m + n)z}{d}

= 8 cos π \frac{mz}{d} cos π \frac{nz}{d} cos π \frac{(m + n)z}{d} ,

and by Claim 1 either there exists χ ∈ Ĝ_{0} such that S^{∗}(χ) + 1 ≤ 0, or we have d = 7 and {0, ±m, ±n, ±(m + n)}(mod d) = ℤ_{d}. However, the former is impossible in view of the assumption that A is positive, and the latter is impossible for otherwise we would have A^{∗} = {0, ±a, ±b, ±(b + a)} = G_{0}, contradicting the assumption that A is not maximal antisymmetric.

Now suppose that G_{0} is not cyclic, and therefore of rank two. (Recall that G_{0} is generated by two elements, a and b.) Fix g_{0}, g ∈ G_{0} such that G = ⟨g_{0}⟩ ⊕ ⟨g⟩ and that the orders d_{0} and d of g_{0} and g satisfy d_{0} | d; here ⟨g_{0}⟩ and ⟨g⟩ denote the cyclic subgroups, generated by g_{0} and g, respectively. Choose m_{0}, n_{0}, m, n ∈ ℤ satisfying

a = m_{0}g_{0} + mg, b = n_{0}g_{0} + ng.

If α_{0}, β_{0}, α, and β are integers such that

g_{0} = α_{0}a + β_{0}b, g = αa + βb,

CHARACTER SUMS IN COMPLEX HALF-PLANES 13

then

g_{0} = (α_{0}m_{0} + β_{0}n_{0})g_{0} + (α_{0}m + β_{0}n)g,  (∗)
g = (αm_{0} + βn_{0})g_{0} + (αm + βn)g  (∗∗)

implying αm + βn ≡ 1(mod d) and consequently, gcd(m, n, d) = 1. We observe also that (∗) and (∗∗) can be interpreted as

(\begin{matrix}g_{0} \\ g \end{matrix}) = (\begin{matrix}α_{0} & β_{0} \\ α & β \end{matrix}) (\begin{matrix}m_{0} & m \\ n_{0} & n \end{matrix}) (\begin{matrix}g_{0} \\ g \end{matrix})

whence

(\begin{matrix}α_{0} & β_{0} \\ α & β \end{matrix}) (\begin{matrix}m_{0} & m \\ n_{0} & n \end{matrix}) ≡ (\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}) (mod d_{0})

and therefore

|\begin{matrix}α_{0} & β_{0} \\ α & β \end{matrix}| |\begin{matrix}m_{0} & m \\ n_{0} & n \end{matrix}| ≡ 1 (mod d_{0}),

gcd(m_{0}n − mn_{0}, d_{0}) = 1.

Thus the assumptions of Claim 2 are satisfied.

Given integers z_{0} and z, consider the character χ ∈ Ĝ_{0} defined by χ(g_{0}) = e^{2πiz_{0}/d_{0}} and χ(g) = e^{2πiz/d}. We have

S^{∗}(χ) + 1 = 2 + 2 cos 2π(\frac{m_{0}z_{0}}{d_{0}} + \frac{mz}{d} ) + 2 cos 2π(\frac{n_{0}z_{0}}{d_{0}} + \frac{nz}{d} )

+ 2 cos 2π(\frac{(m_{0} + n_{0})z_{0}}{d_{0}} + \frac{(m + n)z}{d} )

= 8 cos π(\frac{m_{0}z_{0}}{d_{0}} + \frac{mz}{d} ) cos π(\frac{n_{0}z_{0}}{d_{0}} + \frac{nz}{d} )

cos π(\frac{(m_{0} + n_{0})z_{0}}{d_{0}} + \frac{(m + n)z}{d} ),

which, according to Claim 2, contradicts the fact that A is positive. □

4. Proof of Theorems 1–3

In this section we derive Theorems 1–3 from Proposition 1.

A special role in our argument is played by the half-planes

P^{−} := {z ∈ ℂ: ℜ(z) < 0}, P^{+} := {z ∈ ℂ: ℜ(z) > 0}

and their closures

P_{0}^{−} := {z ∈ ℂ: ℜ(z) ≤ 0}, P_{0}^{+}:= {z ∈ ℂ: ℜ(z) ≥ 0}.

14 SERGEI V. KONYAGIN AND VSEVOLOD F. LEV

Indeed, it suffices to prove Theorem 1 only for the half-planes P_{0}^{+} and P_{0}^{−}, and Theorems 2 and 3 only for the half-planes P^{+} and P^{−}. For let P be an arbitrary closed half-plane with zero on its boundary, and let A be a finite subset of an abelian group G. Consider the “conjugate” half-plane \overline{P} := \{z ∈ ℂ: z̄ ∈ P \}. If S_{A}(χ) ∉ P for any non-trivial character χ, then considering conjugate characters we conclude that also S_{A}(χ) ∉ \overline{P} for any non-trivial character χ. Therefore S_{A}(χ) ∉ (P ∪ \overline{P}). However, the union P ∪ \overline{P} contains one of the half-planes P_{0}^{+} and P_{0}^{−}. The situation when P is open and G is torsion-free or cyclic of prime order is considered similarly.

Theorem 1 is a consequence of the two lemmas that follow. The former of them is identical to Proposition 1, except that the group G is not assumed to be finite.

Lemma 13. Let A be a finite subset of an abelian group G. Then we have ℜ(S_{A}(χ)) > 0 for any χ ∈ Ĝ if and only if one of the following holds:

i) A = {0, g}, where g ∈ G \ {0} is of odd order;
ii) A ∩ (−A) = {0}, and A ∪ (−A) is a subgroup of G.

Proof. Suppose that ℜ(S_{A}(χ)) > 0 for any χ ∈ Ĝ. Since every character of a subgroup can be extended to a character of the whole group, A is a positive subset of ⟨A⟩, the subgroup that it generates. We can write ⟨A⟩ = G_{0} ⊕ G_{1}, where G_{0} is finite and G_{1} is freely generated. Let k ≥ 0 be the rank, and {g_{1}, …, g_{k}} a free system of generators of G_{1}. Fix an integer N and a prime number p > N^{k} and consider the homomorphism φ: ⟨A⟩ → G_{0} ⊕ ℤ_{p} defined by

(g_{0}, m_{1}g_{1} + ⋯ + m_{k}g_{k}) ⟼^{φ} (g_{0}, m_{1} + Nm_{2} + ⋯ + N^{k−1}m_{k} (mod p))

(for any g_{0} ∈ G_{0} and m_{1}, …, m_{k} ∈ ℤ). Provided that N is large enough, the restriction of φ onto A is one-to-one and moreover, if a ∉ G_{0} then also φ(a) ∉ G_{0} for any a ∈ A. Letting Ã = φ(A), for any character χ of the group G_{0} ⊕ ℤ_{p} we have S_{A}(χ ∘ φ) = SÃ(χ). Thus Ã is a positive subset of the finite group G_{0} ⊕ ℤ_{p}. By Proposition 1, either |Ã| ≤ 2 holds, or Ã ∪ (−Ã) is a subgroup of G_{0} ⊕ ℤ_{p}. In the former case we have |A| = |Ã| ≤ 2 and the result follows easily. In the latter case, observing that any subgroup of G_{0} ⊕ ℤ_{p} is actually a subgroup of G_{0}, or otherwise has cardinality at least p, we conclude that Ã ⊆ G_{0}, and consequently A ⊆ G_{0}. This, again, reduces the situation to the finite case. □

Next, we consider “negative” sets.

CHARACTER SUMS IN COMPLEX HALF-PLANES 15

Lemma 14. Let A be a finite subset of an abelian group G. Then ℜ(S_{A}(χ)) < 0 for any non-trivial character χ ∈ Ĝ if and only if G is finite and moreover, one of the following holds:

i) A = G \ {0, g}, where g ∈ G \ {0} is of odd order; ii) A ∪ (−A) = G \ {0}, and A ∩ (−A) is the complement of a subgroup of G.

Proof. Suppose that ℜ(S_{A}(χ)) < 0 for any non-trivial character χ ∈ Ĝ. Denote by ⟨A⟩ the subgroup of G, generated by A. If ⟨A⟩ ≠ G, we choose arbitrarily a non-trivial character χ̃ of the factor group G/⟨A⟩ and lift it to a non-trivial character χ ∈ Ĝ. As χ contains A in its kernel, we have S_{A}(χ) = |A| > 0, contradicting the assumption. This shows that ⟨A⟩ = G and in particular, G is finitely generated. To simplify the notation we assume that G = G_{0} ⊕ ℤ^{k} where G_{0} is finite and k ≥ 0. If k ≥ 1, we fix a real number α > 0 and consider the character χ ∈ Ĝ defined by

χ: (g_{0}, m_{1}, …, m_{k}) ↦ e^{2πim_{1}α} (g_{0} ∈ G_{0}, m_{1}, …, m_{k} ∈ ℤ).

If α is small enough then evidently ℜ(χ(a)) > 0 for any a ∈ A, whence ℜ(S_{A}(χ)) > 0, again, contradicting the assumptions. Thus k = 0 and G is finite. Since S_{G\A}(χ) = −S_{A}(χ) for any non-trivial character χ, the complement G \ A is a positive subset of G, and it remains to apply Proposition 1. □

Theorem 1 is an immediate corollary of Lemmas 13 and 14 and the observation at the beginning of this section. Theorem 2 follows from this observation, Theorem 1, and our next lemma.

Lemma 15. Let G be a cyclic group of odd prime order, and let A be a non-empty proper subset of G. Then ℜ(S_{A}(χ)) ≠ 0 for any character χ ∈ Ĝ.

Proof. Let p = |G| be the order of G. Identifying the elements of G with residue classes modulo p, we can write any non-trivial character of G in the form

χ: z ↦ ζ^{z} (z ∈ G),

where ζ = ζ(χ) a primitive root of unity of degree p. Consequently,

2ℜ(S_{A}(χ)) = ∑_{a∈A} ζ^{a} + ∑_{a∈A} ζ^{p−a}.

If ℜ(S_{A}(χ)) = 0 then ∑_{a∈A} t^{a} + ∑_{a∈A} t^{p−a} is a multiple of P_{ζ}(t) = t^{p−1} + ⋯ + t + 1, the minimal polynomial of ζ over the field of rational numbers. (Here we identify A with the set of its integer representatives in [0, p − 1].) It is immediately seen, however, that this cannot be the case. □

Finally, we turn to torsion-free abelian groups. Theorem 3 follows from the observation at the beginning of this section and Lemmas 16 and 17 below.

Lemma 16. Let A be a finite non-empty subset of a torsion-free abelian group G. Then ℜ(S_{A}(χ)) ≥ 0 for any χ ∈ Ĝ if and only if 0 ∈ A and |A| ≤ 2.

Proof. We can assume that G = ℤ^{k}. Fix an integer N and a prime number p > N^{k}, and define a homomorphism φ: G → ℤ_{p} by

(m_{1}, …, m_{k}) ⟼^{φ} m_{1} + Nm_{2} + ⋯ + N^{k−1}m_{k} (mod p)

(for any m_{1}, …, m_{k} ∈ ℤ). We assume that N is so large that the restriction of φ on A is one-to-one and moreover, no non-zero element of A maps to zero. Write Ã := φ(A) ⊆ ℤ_{p}. Since for any character χ̃ ∈ ℤ̂_{p} we have SÃ(χ̃) = S_{A}(χ̃ ∘ φ), if ℜ(S_{A}(χ)) ≥ 0 for any χ ∈ Ĝ then also ℜ(SÃ(χ̃)) ≥ 0 for any χ̃ ∈ ℤ̂_{p}. By Lemma 15, the set Ã is strictly positive and by Proposition 1 we have either Ã = {0}, or Ã = {0, g̃} for some g̃ ∈ ℤ_{p}. Accordingly, either A = {0}, or A = {0, g} for some g ∈ G \ {0}. □

Lemma 17. For any finite non-empty subset A of a torsion-free abelian group G there exists a non-trivial character χ ∈ Ĝ such that ℜ(S_{A}(χ)) > 0.

Proof. As in the proof o Lemma 16, we assume that G = ℤ^{k}. For α > 0 consider the character χ ∈ Ĝ defined by

χ: (m_{1}, …, m_{k}) ↦ e^{2πiαm_{1}} (m_{1}, …, m_{k} ∈ ℤ).

We can choose α so small that ℜ(χ(a)) > 0 for any a ∈ A, and then ℜ(S_{A}(χ)) > 0. □

Appendix. Proof of Claims 1 and 2

Proof of Claim 1. If d is even the assertion follows by taking z = d/2 and observing that at least one of m and n is odd. Below we assume that d is odd.

Denote the product under consideration by P_{m,n}(z). Since

P_{m,n}(z) = P_{n,m}(z) = P_{−m,−n}(z) = P_{m+n,−m}(z),

we can assume that

gcd(m, d) ≤ min{gcd(n, d), gcd(m + n, d)}.

We let δ := gcd(m, d) and observe that if δ > 1, then the inequality above is strict in view of gcd(m, n, d) = 1.

CHARACTER SUMS IN COMPLEX HALF-PLANES 17

Notice that P_{m,n}(z) actually depends only on the residue classes of m, n, and z modulo d. Hence, if u is an integer such that mu ≡ δ (mod d), then P_{m,n}(zu) = P_{mu,nu}(z) = P_{δ,nu}(z). It is not difficult to see that u can be chosen to be co-prime with d, and this shows that m = δ can be assumed without loss of generality.

Next, we can assume that 1 ≤ n ≤ d − 1. In fact we have then δ ≤ n ≤ d − δ, for otherwise

gcd(n, d) = gcd(d − n, d) ≤ min{n, d − n} < δ.

Since P_{δ,n}(z) = P_{δ+n,−δ}(z) = P_{δ,d−δ−n}(z), we can actually assume that

δ ≤ n ≤ \frac{d − δ}{2} .

Moreover, if n = δ then δ = 1 and it is easy to verify that min_{z} P_{1,1}(z) ≤ 0. Similarly, if n = (d−δ)/2 then δ | (n, d) whence δ = 1, and min_{z} P_{1,(d−1)/2}(z) ≤ P_{1,(d−1)/2}(1) ≤ 0 in view of

P_{1,(d−1)/2}(1) = cos \frac{π}{d} cos π \frac{(d − 1)/2}{d} cos π \frac{(d + 1)/2}{d}

= − cos \frac{π}{d} cos^{2} π \frac{(d − 1)/2}{d}.

With the above said in mind, for the rest of the proof we assume that

δ + 1 ≤ n ≤ \frac{d − δ}{2} − 1

and we notice that this implies δ ≤ d/5.

If n is odd we set z := (d − 1)/2 and observe that i) δz = \frac{δ−1}{2} d + \frac{d−δ}{2}, whence sign cos π \frac{δz}{d} = (−1)^{\frac{δ−1}{2}} ; ii) nz = \frac{n−1}{2} d + \frac{d−n}{2}, whence sign cos π \frac{nz}{d} = (−1)^{\frac{n−1}{2}} ; iii) (δ + n)z = \frac{δ+n}{2} d − \frac{δ+n}{2} > \frac{δ+n}{2} d − \frac{d}{2}, whence sign cos π \frac{(δ+n)z}{d} = (−1)^{\frac{δ+n}{2}} .

It follows that

signP_{δ,n}(z) = (−1)^{\frac{δ−1}{2} + \frac{n−1}{2} + \frac{δ+n}{2}} = −1.

If n is even we fix positive integers k and t such that (2k + 1)δ = n + 1 + 2nt (this is possible as gcd(2δ, 2n) = 2 divides n + 1 − δ) and set

z := ⌈\frac{2k + 1}{2n} d⌉ .

We have then i) δz > \frac{(2k+1)δ}{2n} d = td + \frac{d}{2} + \frac{d}{2n} > (t + 1)d − \frac{d}{2},

δz < td + \frac{d}{2} + \frac{d}{2n} + δ ≤ td + \frac{d}{2} + \frac{d}{4} + \frac{d}{5} < (t + 1)d,

whence sign cos π \frac{δz}{d} = (−1)^{t+1}; ii) nz > (k + 1)d − \frac{d}{2} and nz < (k + 1)d − \frac{d}{2} + n < (k + 1)d, whence sign cos π \frac{nz}{d} =

(−1)^{k+1}; iii) (δ + n)z = δz + nz > ((t + 1)d − \frac{d}{2}) + ((k + 1)d − \frac{d}{2}) = (k + t + 1)d.

To complete the proof it suffices to show that

(δ + n)z < (k + t + 3/2)d,  (∗)

as then we obtain sign cos π \frac{(δ+n)z}{d} = (−1)^{k+t+1} and

signP_{δ,n}(z) = (−1)^{(t+1)+(k+1)+(k+t+1)} = −1.

We multiply (∗) by 2n (for technical reasons) and then consider the difference between its left-hand and right-hand sides. Denoting this difference by Δ, we get

Δ := 2n(δ + n)z − 2n(k + t + 3/2)d
≤ (δ + n) ((2k + 1)d + 2n − gcd(n, d)) − (2k + 2t + 3)nd
≤ (δ + n)(2k + 1)d + (δ + n)(2n − δ) − (2k + 1)nd − 2(t + 1)nd
= (2k + 1)δd − 2(t + 1)nd + (2n^{2} + nδ − δ^{2})
= (1 − n)d + (2n^{2} + nδ − δ^{2})
≤ (1 − n)(2n + δ + 2) + (2n^{2} + nδ − δ^{2})
= −δ^{2} + δ + 2.

Thus, if δ > 1 then Δ ≤ 0, proving (∗). (Observe, that Δ ≠ 0 as the left-hand side of (∗) is an integer, while the right-hand side is not.) Moreover, if δ = 1 and n ≤ (d−δ)/2−2, then d ≥ 2n+δ +4 and the latter computation can be strengthened to give

Δ ≤ (1 − n)(2n + δ + 4) + (2n^{2} + nδ − δ^{2})
= −δ^{2} + δ + 4 − 2n
= −2n + 4
≤ 0.

We can assume, therefore, that δ = 1 (which yields 2k = n+2nt) and n = (d−δ)/2− 1 = (d − 3)/2.

CHARACTER SUMS IN COMPLEX HALF-PLANES 19

If (2k + 1)d ≢ 1(mod 2n), then z ≤ ((2k + 1)d + 2n − 2)/2n and we have

Δ ≤ (1 + n) ((2k + 1)d + 2n − 2) − (2k + 2t + 3)nd

= −3(n − 1) (verification left to the reader) < 0.

Finally, suppose that δ = 1, n = (d − 3)/2, and (2k + 1)d ≡ 1(mod 2n). Then

1 ≡ (2k + 1)d ≡ (n + 1) · 3 ≡ n + 3 (mod 2n),

hence 2n | n + 2 implying n = 2 and d = 7. This is the exceptional case. □

Proof of Claim 2. If d is even then the result follows easily as in the proof of Claim 1. Suppose that d is odd and consequently, d_{0} > 2.

If d = 7 then d_{0} = 7, and the assumptions imply that there exist integers z_{0} and z such that

m_{0}z_{0} + mz ≡ n_{0}z_{0} + nz ≡ 2 (mod 7).

Plainly, with this choice of z_{0} and z the product we are interested in is negative.

Suppose now that d is odd and d ≠ 7. If m, n, m + n ≢ 0(mod d), then we can disregard z_{0} (taking it to be zero) and the result follows from Claim 1. Otherwise, we can assume that m + n ≡ 0(mod d): for if, say, m ≡ 0(mod d), then one verifies readily that

m′_{0} := m_{0} + n_{0}, n′_{0} := −n_{0}, m′ := m + n, n′ := −n

satisfy the assumptions, and m′ + n′ ≡ 0(mod d). Next, since our product remains unchanged when n increases by a multiple of d, we can assume that n = −m. Similarly, the product is invariant under changes of n_{0} by multiples of d_{0}, and therefore we can assume that m_{0} and n_{0} are of the same parity.

In view of gcd(m, d) = gcd(m, −m, d) = gcd(m, n, d) = 1, for any integer z_{0} we can find z so that

mz ≡ \frac{n_{0} − m_{0}}{2} \frac{d}{d_{0}} z_{0} (mod d).

With this choice of z (and under the assumption that n = −m) we have

\frac{m_{0}z_{0}}{d_{0}} + \frac{mz}{d} = \frac{((m_{0} + n_{0})/2) z_{0}}{d_{0}} + u and \frac{n_{0}z_{0}}{d_{0}} + \frac{nz}{d} = \frac{((m_{0} + n_{0})/2) z_{0}}{d_{0}} − u

for some u ∈ ℤ. Thus our product equals

cos^{2} π \frac{((m_{0} + n_{0})/2) z_{0}}{d_{0}} cos π \frac{(m_{0} + n_{0})z_{0}}{d_{0}}

and since m_{0} + n_{0} ≢ 0(mod d_{0}) (along with m + n = 0 this would contradict the assumptions of the claim), there exists z_{0} ∈ ℤ which makes this last expression negative. □

Acknowledgment

Much of this paper was completed when the authors attended the “Research in Pairs” program of the Oberwolfach Mathematics Institute. We are greatly indebted to its administration and stuff for their hospitality.

References

[B86] J. Bourgain, Sur le minimum d’une somme de cosinus, [On the minimum of a sum of cosines], Acta Arithmetica 45 (4) (1986), 381–389.

[BK96] A.S. Belov and S.V. Konyagin, On the conjecture of Littlewood and minima of even trigonometric polynomials, Harmonic analysis from the Pichorides viewpoint (Anogia, 1995), 1–11, Publ. Math. Orsay, 96-01, Univ. Paris XI, Orsay, 1996.

[K81] S.V. Konyagin, On the Littlewood problem, Izv. Akad. Nauk SSSR Ser. Mat. 45 (2) (1981), 243–265. (English translation: Mathematics of the USSR - Izvestiya 45 (2) (1982), 205–225.)

[KL] S.V. Konyagin and V. Lev, On the distribution of exponential sums, Integers 0 (2000), #A1 (electronic).

[MPS81a] O.C. McGehee, L. Pigno, and B. Smith, Hardy’s inequality and the Littlewood conjecture, Bull. Amer. Math. Soc. (N.S.) 5 (1) (1981), 71–72.

[MPS81b] O.C. McGehee, L. Pigno, and B. Smith, Hardy’s inequality and the L^{1} norm of exponential sums, Annals of Mathematics (2) 113 (3) (1981), 613–618.

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

  E-mail address: konyagin@ok.ru

Department of Mathematics, Haifa University at Oranim, Tivon 36006, Israel

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