DISTRIBUTION OF POINTS ON ARCS

VSEVOLOD F. LEV

Abstract. Let z_{1}, …, z_{N} be complex numbers situated on the unit circle |z| = 1, and write S := z_{1} + ⋯ + z_{N}. Generalizing a well-known lemma by Freiman, we prove the following.

(i) Suppose that any open arc of length φ ∈ (0, π] of the unit circle contains at most n of the numbers z_{1}, …, z_{N}. Then

|S| ≤ 2n − N + 2(N − n) cos(φ/2).

(ii) Suppose that any open arc of length π of the unit circle contains at most n of the numbers z_{1}, …, z_{N} and suppose, in addition, that for any 1 ≤ i < j ≤ N the length of the (shortest) arc between z_{i} and z_{j} is at least δ > 0. Then

|S| ≤ \frac{sin (n − N/2)δ}{sin δ/2}

provided that nδ ≤ π.

These estimates are sharp.

1. Introduction

Write 𝕌 := {z ∈ ℂ: |z| = 1}, the unit circle on the complex plane. In 1962 Freiman established a lemma showing that if z_{1}, …, z_{N} ∈ 𝕌 are “uniformly distributed on arcs of length π”, then the sum z_{1} + ⋯ + z_{N} is small in absolute value.

Lemma 1 ([F62, Lemma 1]). Let N and n be positive integers. Suppose that the complex numbers z_{1}, …, z_{N} ∈ 𝕌 have the property that any open arc of 𝕌 of length π contains at most n of them. Then

|z_{1} + ⋯ + z_{N}| ≤ 2n − N.

Observe, that the assumption “any open arc of 𝕌 of length π contains at most n of the numbers z_{1}, …, z_{N}” implies readily that N ≤ 2n.

Lemma 1 is best possible in the following sense: for any integers 1 ≤ n ≤ N ≤ 2n there exist z_{1}, …, z_{N} ∈ 𝕌 with the property in question and such that |z_{1}+⋯+z_{N}| = 2n − N. Say, one can take 2n − N of the numbers z_{j} equal one, N − n equal i, and N − n equal −i.

In practice, one often needs an analog of Lemma 1 with the arcs of length π replaced by arcs of other prescribed lengths; see for instance [GR, S03]. Though some estimates

2 VSEVOLOD F. LEV

of this sort are easy to obtain, to our knowledge no precise result in this direction has ever been established. We fill this gap proving (in Section 2)

Theorem 1. Let N and n be positive integers and let φ ∈ (0, π]. Suppose that the complex numbers z_{1}, …, z_{N} ∈ 𝕌 have the property that any open arc of 𝕌 of length φ contains at most n of them. Then

|z_{1} + ⋯ + z_{N}| ≤ 2n − N + 2(N − n) cos(φ/2).

Theorem 1 is sharp, at least in the range N/2 ≤ n ≤ N: the bound is attained, for instance, if 2n − N of the numbers z_{j} equal one, N − n equal exp(iφ/2), and N − n equal exp(−iφ/2).

In a typical application of Lemma 1, one has a set A of residues modulo an integer m > 1 and uses combinatorial properties of A to conclude that its indicator function possesses a “large” Fourier coefficient; that is, the exponential sum ∑_{a∈A} exp(2πisa/m) is large in absolute value for some integer s. Using Lemma 1 one then recovers initial structure information about the set A showing that its distribution in residue classes modulo m exhibits a bias. Thus, Lemma 1 is applied with z_{j} = exp(2πia_{j}/m) where m is a positive integer and a_{j} are integers, pairwise incongruent modulo m. In this situation z_{j} are bounded away from each other and one can expect that now the estimate of Lemma 1 is no longer best possible. Indeed, in Section 2 we prove

Theorem 2. Let N and n be positive integers and let δ ∈ (0, π) satisfy nδ ≤ π. Suppose that the complex numbers z_{1}, …, z_{N} ∈ 𝕌 have the following two properties:

(i) any open arc of 𝕌 of length π contains at most n of them; (ii) any open arc of 𝕌 of length δ contains at most one of them.

Then

|z_{1} + ⋯ + z_{N}| ≤ \frac{sin (n − N/2)δ}{sin δ/2} .

This refinement of Lemma 1 is crucial in [L].

The restriction nδ ≤ π is easy to drop: if it fails then (i) follows from (ii) and can be omitted; in this case the maximum possible value of |z_{1} + ⋯ + z_{N}| is sin(Nδ/2)/ sin(δ/2), attained, say, for z_{j} = exp(ijδ) (j = 1, …, N). This situation is not of much interest and for this reason excluded from the statement of the theorem.

Theorem 2 is sharp. To see this notice that its assumptions imply N ≤ 2n and consider the union of three geometric progressions contained in 𝕌 of ratio exp(iδ), one of which is centered around one and has 2n − N terms, and two other are centered around i and −i and have N − n terms each.

DISTRIBUTION OF POINTS ON ARCS 3

2. Proofs

Proof of Theorem 1. Throughout the proof we assume that φ ∈ (0, π] and n ≥ 1 are fixed, while N can vary. We say that a finite sequence of elements of 𝕌 is admissible if any open arc of length φ of 𝕌 contains at most n terms of the sequence. We call an admissible sequence good if

|S| ≤ 2n − N + 2(N − n) cos(φ/2),

where N is the number of terms of the sequence and S is their sum; otherwise the sequence is bad. With a slight language abuse, we say that the complex number z is an element of the sequence Z if (at least) one of the terms of Z equals z.

Suppose that bad sequences do exist, and let N be the minimum possible number of terms of a bad sequence. Furthermore, let Z be an N-term bad sequence with the largest possible absolute value of the sum of its terms. (Such an extremal sequence exists by the standard compactness argument: just notice that the set of all N-term sequences over 𝕌 is a compact topological space in which admissible sequences form a closed subset and the sum-of-the-terms function is continuous. Notice that this argument goes through due to the fact that we consider open arcs.) Denote the sum of the terms of Z by S. Multiplying all terms of Z by exp(iθ) with a suitably chosen θ, we can assume without loss of generality that S is a positive real number.

Consider an element z of Z with −π < arg z < 0 and for real ε > 0 denote by Z_{ε} the sequence, obtained from Z by replacing z with z exp(iε); that is, by rotating z along the unit circle by the angle ε. It is not difficult to see that if ε is small enough, then (i) the sum of the terms of Z_{ε} is greater in absolute value than S, and (ii) if z exp(iφ) is not an element of Z, then Z_{ε} is admissible. From the extremal property of Z we derive that in fact z exp(iφ) is an element of Z. Similarly, if z is an element of Z with 0 < arg z ≤ π then also z exp(−iφ) is an element of Z.

Define now φ_{0} ∈ (0, φ] by cos^{2}(φ_{0}/2) = cos(φ/2); we claim then that all elements of Z fall into the arc | arg z| < φ_{0}. For a contradiction, assume that z is an element of Z outside this arc, and let Z′ be obtained from Z by removing this offending element. The number of terms of Z′ is N′ = N − 1, and their sum S′ satisfies

|S′|^{2} = (S − ℜz)^{2} + (ℑz)^{2} = S^{2} − 2S ℜz + 1 ≥ S^{2} − 2S cos φ_{0} + 1 = S^{2} − 4S cos(φ/2) + 2S + 1 ≥ (S + 1 − 2 cos(φ/2))^{2}.

Since Z is bad we conclude that

|S′| ≥ S + 1 − 2 cos(φ/2) > 2n − N′ + 2(N′ − n) cos(φ/2).

4 VSEVOLOD F. LEV

This shows that Z′ is bad, too, contradicting minimality of N.

Next, we show that indeed all elements of Z fall into the arc | arg z| ≤ φ/2. Suppose this is wrong; say, there exist elements z of Z with −φ_{0} < arg z < −φ/2. Fix one with this property for which arg z is minimal. We know that z exp(iφ) is an element of Z. On the other hand, z exp(2iφ) is not an element of Z unless φ = π (in which case z exp(2iφ) = z) in view of

φ_{0} ≤ −φ_{0} + 2φ < arg z + 2φ ≤ arg z + 2π

and by minimality of arg z. It follows that for sufficiently small ε > 0 the sequence, obtained from Z by replacing z with z exp(iε) and z exp(iφ) with z exp(i(φ + ε)), is admissible. Moreover, in view of arg z < −φ/2 the sum of the terms of this new sequence exceeds S in absolute value, contradicting the choice of Z.

We have shown that for any element z ≠ 1 of Z, (i) either z exp(iφ) or z exp(−iφ) is an element of Z, and (ii) | arg z| ≤ φ/2. Evidently, this implies that all terms of Z with negative argument equal exp(−iφ/2), and all terms of Z with positive argument equal exp(iφ/2). Let k denote the number of terms of each sort, so that the remaining N − 2k terms equal one. Since Z is admissible, we have k + (N − 2k) ≤ n and then

S = (N − 2k) + 2k cos(φ/2) ≤ N − 2(N − n) + 2(N − n) cos(φ/2) = 2n − N + 2(N − n) cos(φ/2),

contradicting the assumption that Z is bad. □

Proof of Theorem 2. We use induction on N. For N = 1 the assertion is almost immediate and for N = 2 easy to verify, and we assume that N ≥ 3. Suppose that sequences (z_{1}, …, z_{N}) of elements of 𝕌, satisfying assumptions (i) and (ii) of the theorem but violating its conclusion, do exist, and find one with |z_{1} + ⋯ + z_{N}| as large as possible. (The existence of such a sequence follows by the compactness argument.) Denote this extremal sequence by Z. Without loss of generality, we can assume that the sum S of its terms is a positive real number.

Let z be an element of Z. If arg z < 0 then replacing z with z exp(iε), where ε > 0 is sufficiently small, we obtain a new sequence the sum of the terms of which is larger in absolute value than S. This shows that either z exp(iδ) or −z is an element of Z. A similar conclusion holds if arg z > 0, though this time z exp(−iδ) (rather than z exp(iδ)) is to be an element of Z.

We claim that in fact there is no z ∈ 𝕌 such that Z contains both z and −z. For otherwise removing these two elements from Z we obtain a sequence Z′ of N′ = N −2 terms such that (i) any open arc of 𝕌 of length π contains at most n′ := n − 1 terms of Z′, (ii) any open arc of 𝕌 of length δ contains at most one term of Z′, and (iii) the sum of all terms of Z′ is S. By the induction hypothesis we have then

S ≤ \frac{sin (n′ − N′/2)δ}{sin δ/2} = \frac{sin (n − N/2)δ}{sin δ/2} ,

contradicting the choice of Z.

We have shown that along with every its element z ≠ 1, the sequence Z contains either the element z exp(iδ) (if arg z < 0) or the element z exp(−iδ) (if arg z > 0). From this and the assumption that any open arc of length δ contains at most one term of Z, one derives easily that Z is a geometric progression with ratio exp(iδ). Any n + 1 consecutive terms of this progression would lie on an arc of length nδ, hence either the progression has n terms at most, or nδ = π. In the former case we have N ≤ n whence

S = |∑_{j=0}^{N−1} exp(ijδ)| = \frac{| sin Nδ/2|}{sin δ/2} ≤ \frac{sin (n − N/2)δ}{sin δ/2}

(in view of Nδ/2 ≤ (n − N/2)δ ≤ π − Nδ/2), and in the latter case

S = \frac{| sin Nδ/2|}{sin δ/2} = \frac{sin (n − N/2)δ}{sin δ/2} .

In any case we have obtained a contradiction. □

3. Concluding remarks

Specifying Theorems 1 and 2 to the situation described in Section 1 and putting them “the other way round” one deduces the following two corollaries.

Corollary 1. Let A be a set of N residues modulo an integer m > 1. Write S := ∑_{a∈A} exp(2πia/m). Then for any integer k ≥ 2 there exist integers u and v satisfying u ≤ v < u + m/k such that the image of the interval [u, v] under the canonical homomorphism ℤ → ℤ/mℤ contains at least

\frac{|S| + (1 − 2 cos(π/k)) N}{2(1 − cos(π/k))}

elements of A.

Proof. Consider the system of complex numbers {exp(2πia/m)}_{a∈A} and apply Theorem 1 to this system with φ = 2π/k. □

6 VSEVOLOD F. LEV

Corollary 2. Let A be a set of N residues modulo an integer m > 1. Write S := ∑_{a∈A} exp(2πia/m). Then there exists an integer u such that the image of the interval [u, u + m/2) under the canonical homomorphism ℤ → ℤ/mℤ contains at least

\frac{N}{2} + \frac{m}{2π} arcsin (|S| sin \frac{π}{m})

elements of A.

Proof. Consider the system of complex numbers {exp(2πia/m)}_{a∈A}. Chose δ = 2π/m and let n be the maximum number of elements of A in the canonical image of an interval of the form [u, u + m/2). If n < m/2 then nδ < π and the assertion follows by Theorem 2. Otherwise N ≥ n ≥ m/2 and since |S| ≤ (sin πN/m)/(sin π/m) (the simple verification is left to the reader) we get

\frac{N}{2} + \frac{m}{2π} arcsin (|S| sin \frac{π}{m}) ≤ \frac{N}{2} + \frac{m}{2π} arcsin ( sin π \frac{N}{m})

= \frac{N}{2} + \frac{m}{2π} \frac{π(m − N)}{m} = \frac{m}{2} ≤ n.

□

It seems natural to combine Theorems 1 and 2 and determine the maximum possible value of |z_{1} + ⋯ + z_{N}| given that z_{1}, …, z_{N} ∈ 𝕌 have the properties that (i) any open arc of 𝕌 of length φ contains at most n of the z_{j}, and (ii) any open arc of 𝕌 of length δ contains at most one of the z_{j}. We do not consider a generalization of this sort since we have no applications in mind for it.

In conclusion, we notice that from Theorem 1 it is not difficult to deduce the following more general result.

Theorem 1′. Let λ ≤ 1/2 and ν be positive real numbers and let μ be a probabilistic measure on the torus group ℝ/ℤ. Suppose that μ(I) ≤ ν for any open interval I ⊆ ℝ/ℤ of length |I| = λ. Then

| ∫_{ℝ/ℤ} exp(it) dμ| ≤ 2ν − 1 + 2(1 − ν) cos(πλ).

References

[F62] G.A. Freiman, Inverse problems of additive number theory, VII. On addition of finite sets, IV, Izv. Vyss. Ucebn. Zaved. Matematika 6 (31) (1962), 131–144.

[GR] B. Green and I.Z. Ruzsa, Sets with small sumset and rectification, manuscript in preparation.

[L] V.F. Lev, Large sum-free sets in ℤ/pℤ, manuscript in preparation.

[S03] T. Schoen, Multiple set addition in ℤ_{p}, Integers 3 (2003), A13, 11 pp. (electronic).