SETS OF INTEGERS WITH LARGE TRIGONOMETRIC SUMS

AMNON BESSER

Abstract. We investigate the problem of optimizing, for a fixed integer k and real u and on all sets K ⊂ ℤ of cardinality k, the measure of the set of α ∈ [0, 1] where the absolute value of the trigonometric sum S_{K}(α) = ∑_{j=1}^{k} e^{2πiαa_{j}} is greater than k − u. When u is sufficiently small with respect to k we are able to construct a set K_{ex} which is very close to optimal. This set is a union of a finite number of arithmetic progressions. We are able to show that any more optimal set, if one exists, has a similar structure to that of K_{ex}. We also get tight upper and lower bounds on the maximal measure.

1. Introduction

Let k be a positive integer and u < k a positive real. For a set

K = {a_{1} < a_{2} < … < a_{k}}, a_{j} ∈ ℤ, 1 ≤ j ≤ k,

let

S_{K}(α) = ∑_{j=1}^{k} e^{2πiαa_{j}}, s_{K}(α) = |S_{K}(α)|,

E_{K,u} = {α ∈ [0, 1) : s_{K}(α) ≥ k − u}

and

μ_{K}(u) = μ(E_{K,u}),

where μ is the Lebesgue measure on [0, 1] normalized so μ([0, 1]) = 1.

This work deals with the following problem, first raised at the talk of Freiman and Judin at the Number Theory Conference (Vladimir, 1968):

Problem 1. Find the set K which maximizes μ_{K}(u) and find the maximal value.

We denote by μ_{max}(k, u) the supremum of μ_{K}(u) on all sets K of size k.

The first results on this problem were obtained by Freiman and Judin:

Theorem 1 (Freiman, [2, page 144]). For u = 1, a_{1} = 0 and a_{k} < 0.05k^{3/2}, the maximal measure is

μ_{max}(k, u) = \frac{2\sqrt{6}}{π}k^{−3/2} + O(k^{−2})

and it is attained by K if and only if K is an arithmetic progression.

1991 Mathematics Subject Classification. Primary 11L03; Secondary 42A05.

Key words and phrases. Trigonometric sums.

Theorem 2 (Judin, [4]). For u = o(k)

μ_{max}(k, u) = \frac{2\sqrt{6}}{π} \frac{1}{k} (\frac{u}{k})^{1/2} (1 + o(1))

as k ⟶ ∞.

In [1] Freiman treated the problem assuming the ratio u/k is small enough. He sketched an approach for attacking the problem and conjectured it would prove that the best set is an arithmetic progression.

The purpose of this work is to carry out and extend Freiman’s approach (and also that of [4]). It will turn out that once u is sufficiently large it is no longer true that an arithmetic progression attains μ_{max}(k, u). We are unable to find a set which does. Nevertheless, we do describe to some extent the “structure” of the maximal set. To make precise what this means, we will introduce and use the following terminology

Definition 1.1. Let k and u be as above.

1. For any ψ ∈ [0, 1] we let 𝕂_{ψ} be the collection of all sets K ⊂ ℤ of size k that satisfy μ_{K}(u) ≥ ψ.

2. A collection 𝕂 of sets is said to be “good for ψ”, or to be a G_{ψ} collection, if it satisfies the following two properties:

(a) We have 𝕂 ⊂ 𝕂_{ψ},

(b) For any set K ⊂ ℤ of size k there exists a set K′ ∈ 𝕂 such that μ_{K}(u) ≤ μ_{K′}(u).

Our main results are of three types. We are able to describe the “structure” of sets in 𝕂_{ψ} for a ψ which is very close to maximal. In addition we construct a certain sub-collection of this which has property G_{ψ}. The subclass we describe is not a singleton but it does have a rather simple structure: it is essentially the union of arithmetic progressions, and we have a fairly accurate information about the location and length of all these sequences. Lastly, we get a good bound on μ_{max}(k, u).

The type of results we get is dictated by our method of proof, which could be describe as an iteration of four steps.

1. We first guess a set K expected to have a large μ_{K}(u). We will take ψ = μ_{K}(u).

2. We get information about sets K_{1} that have an even higher μ_{K_{1}}(u). Typically this information consists of knowledge that most elements are contained inside arithmetic progressions of relatively short length. This is what we mean by describing the “structure” of 𝕂_{ψ}.

3. Given a set K_{1} ∈ 𝕂_{ψ}, we give a procedure for obtaining out of K_{1} a set K_{2} such that μ_{K_{2}}(u) ≥ μ_{K_{1}}(u). The procedure usually involves compressing the elements contained in the short progressions described above to form short progressions, possibly with a single gap. Sets obtained in this way will form a subclass 𝕂 that has property G_{ψ} by construction.

4. We use the knowledge of 𝕂_{ψ} to get an improved bound on μ_{max}(k, u).

Our results apply under the assumptions k/30000 ≥ u > 1 and k ≥ Const, with Const an unspecified constant. We note that this second assumption is only forced on us because we are using lemma 5.2 which is ineffective. If an effective bound is supplied for that lemma, it will be very easy to deduce an effective lower bound on k as well.

We state a simplified version of the results here under the additional assumption u > k^{2/3}. With these assumptions, it follows (proposition 3.1) that for an arithmetic progression K of difference 1 and length k there exists some β_{k,u}(definition 3.2) such that

E_{K,u} = [−β_{k,u}, β_{k,u}] (mod 1).

We will see in proposition 3.4 that

β_{k,u} ≈ \frac{\sqrt{6}}{π} \frac{1}{k} (\frac{u}{k})^{1/2} .

We describe a certain basic set K_{ex} (a more precise description will be given in construction 6.1). Set m_{0} = k − 5u/12 and β = β_{m_{0},u}. To first order, β_{m_{0},u} ≈ β_{k,u}(1 + 5u/8k). The set K_{ex} is the union of an arithmetic progression of length m_{0}, symmetric around 0, and for any non zero integer n an arithmetic progression of length

\frac{1}{2}m_{n} = \frac{u}{(πn)^{2}} (1 − \frac{(−1)^{n}}{2} ) ,

centered around \frac{n}{β}. All the arithmetic progressions here have difference 1. The structure of K_{ex} and the particular values of the m_{n} are chosen in such a way that the contributions of the shorter progressions to S_{K_{ex}}(α) exactly compensates for the decline of the contribution of the large progression when |α| > β/2. We show in proposition 6.12 that μ_{K_{ex}}(u) ≈ 2β. The results are now as follows.

1.

μ_{max}(k, u) = 2β_{m_{0},u} (1 + O ((\frac{u}{k})^{2})) .

2. A set K ∈ 𝕂_{μ_{Kex} (u)} has the following structure (similar to that of K_{ex}). (a) All but

\frac{5}{12}u + O (\frac{u^{2}}{k} )

elements of K are contained in a short arithmetic progression of length 1/4β. To state the other results we will assume that this progression is symmetric around 0 and its difference is 1. The general case is essentially the same by translation and dilation which change nothing.

(b) Most other elements are contained in a union of short arithmetic progressions with centres near \frac{n}{β} and −\frac{n}{β} for n ∈ ℕ. each such short progression has length 2k at the most. The number of elements contained in progressions near ±\frac{n}{β} is

m_{n} + O (\frac{u^{2}}{k} ) .

(c) The number of elements not contained in any of the progressions above

is O ((u/k)^{1/2}u).

3. The following subclass of 𝕂_{μ_{Kex} (u)} is of type G_{μ_{Kex} (u)}. It consists of the sets where all the elements contained in the progression described in (a) above in fact form an arithmetic progression except that one gap may persist.

All O terms can and will be made explicit although no claim for best bounds is made.

Here is a brief summary of the contents of this paper. In section 3 we estimate μ(E_{K,u}) in the case where K is an arithmetic progression, and we prove the lower bound:

μ(E_{K,u}) ≤ \frac{2\sqrt{6}}{π} \frac{1}{k} (\frac{u}{k})^{1/2}

for such a progression. In section 4 we prove the upper bound

μ(E_{K,u}) ≤ \frac{d}{k} (\frac{u}{k})^{1/2}

holds for an explicitly given d ≈ 4 and all sets K under some mild restrictions on k and u. In section 5 we consider a set

K ∈ 𝕂_{ψ}, ψ = \frac{2\sqrt{6}}{π} \frac{1}{k} (\frac{u}{k})^{1/2}.

We show that this implies that E_{K,u} is contained in a union of small intervals and that K has most of its elements contained in an arithmetic progression of short length. We then perform the first of our “compression arguments” mentioned above and construct a G_{ψ} subclass consisting of the sets where these elements form an arithmetic progression with at most one gap. The construction of K_{ex} is described in section 6. In sections 7 to 9 we describe the structure of 𝕂_{μ_{Kex} (u)} and also describe a G_{μ_{Kex} (u)} subclass.

Some of the results of this paper appeared in [1]. We follow [1] very closely in sections 3 to 5. We note that the argument in [1, p. 368] may be completed to give the result that, the part of K not in an arithmetic progression is bounded in size by cu with c ⟶ 1/(2 − 4/π) as u/k ⟶ 0. This result is improved here to c ≈ 5/12.

It is a great pleasure to thank Prof. Freiman for the help and fruitful discussions during the preparation of this work. I would also like to thank the referee for making many valuable remarks.

2. Notation and terminology

An arithmetic progression {a, a + q, a + 2q, …, a + (n − 1)q} is said to have length n and difference q. We will often make the distinction between a set being contained in an arithmetic progression, which means it is a subset of the above, and set forming and arithmetic progression. We will also sometime talk about an interval of integers. This will mean a set of the form {x ∈ ℤ : s ≤ x ≤ t}. This interval has length t − s. Notice that a subset of {a, a + q, a + 2q, …, a + (n − 1)q} is contained in an arithmetic progression of length n but in an interval of length (n − 1)q.

In this paper, excluding the introduction, we will make a non-standard use of the notations O(1) and o(ϵ). The notation O(1) will mean having absolute value ≤ 1. In particular, we will write a = b + O(1)c to mean |a − b| ≤ c. We will use o(ϵ) to refer to a quantity which is very small and will be discarded in the computation by swallowing it in a larger quantity. A typical use of this will be for example 8(1 + o(ϵ)) ≤ 9. The reader will have to check for himself or herself that such an argument is justified, which should not be too hard. This notation is used because we have been asked to give explicit, while not best possible, upper bounds for everything.

3. The Case Of Arithmetic Progressions

As remarked in the introduction, we always assume that u > 1. In this section we want to determine s_{K}(α), E_{K,u} and μ_{K}(u) when K is an arithmetic progression. It will be occasionally convenient to write, when K is of length k and difference 1, s_{k}(α) for s_{K}(α), E_{k,u} for E_{K,u} and μ_{k}(u) for μ_{K}(u).

We first note that, for any set K and integers d and m,

s_{dK+m}(α) = s_{K}(dα). (1)

Therefore

E_{dK+m,u} = ⟨d⟩^{−1}(E_{K,u}). (2)

Here, the map ⟨d⟩ : [0, 1) → [0, 1) is defined by ⟨d⟩(α) = fractional part of dα. For F ⊂ [0, 1), ⟨d⟩^{−1}(F) denotes the inverse image of F under ⟨d⟩. It is easy to deduce from this that

μ_{dK+m}(u) = μ_{K}(u).

These observations allow us to reduce to the case of difference 1.

Proposition 3.1. Let K be an arithmetic progression of length k and difference 1. Assume k ≥ 2u.

1. We have

s_{K}(α) = |\frac{sin(παk)}{sin(πα)}| when α ≠ 0.

2. The set E_{k,u} is a single interval modulo 1, i.e.,

E_{K,u} = [−β, β] (mod 1),

For some β ∈ ℝ.

It will be worth while to give the number β appearing in the proposition a special notation.

Definition 3.2. Under the assumptions of proposition 3.1, define β_{k,u} > 0 by the equality

E_{K,u} = [−β_{k,u}, β_{k,u}] (mod 1),

for K an arithmetic progression of length k and difference 1. Note that

s_{K}(β_{k,u}) = k − u.

Corollary 3.3. If K is an arithmetic progression of length k and difference d, then

E_{K,u} = ⋃_{q=0}^{d−1} [\frac{q}{d} − \frac{β_{k,u}}{d} , \frac{q}{d} + \frac{β_{k,u}}{d} ] (mod 1).

Proof. From proposition 3.1 and (2) it follows that

E_{K,u} = ⟨d⟩^{−1}([−β_{k,u}, β_{k,u}]) = ⋃_{q=0}^{d−1} [\frac{q}{d} − \frac{β_{k,u}}{d} , \frac{q}{d} + \frac{β_{k,u}}{d} ] (mod 1).

Proof of proposition 3.1. By (1) it is enough to consider any arithmetic progression of difference 1. In particular, one can take

K = \{−\frac{k − 1}{2}, …, \frac{k − 1}{2}\}.

Note that this set might be composed of half integers but that makes no difference here. We get for α ≠ 0,

(3)  S_{K}(α) = ∑_{n=− \frac{k−1}{2}}^{\frac{k−1}{2}} e^{2πiαn} = e^{(1−k)πiα} ∑_{n=0}^{k−1} e^{2πiαn}

= e^{(1−k)πiα} \frac{e^{2πiαk} − 1}{e^{2πiα} − 1} = \frac{(e^{πiαk} − e^{−πiαk})/2i}{(e^{πiα} − e^{−πiα})/2i} = \frac{sin(παk)}{sin(πα)}.

Taking absolute values gives the first assertion. We now have

E_{K,u} = \{α ∈ (0, 1) : |\frac{sin(παk)}{sin(πα)}| ≥ k − u\} ∪ \{0\}.

This set is symmetric around 1/2. It is thus sufficient to consider its intersection with the interval (0, \frac{1}{2}). On this set S_{K} is in fact positive. Indeed, since by assumption 2u ≤ k, we find

\frac{1}{2}k ≤ k − u ≤ \frac{| sin(παk)|}{sin(πα)} ≤ \frac{1}{sin(πα)} ≤ \frac{π/2}{πα},

and therefore

παk ≤ π, (4)

which shows that sin(παk) ≥ 0. We can also write

S_{K}(α) = ∑_{n=− \frac{k−1}{2}}^{\frac{k−1}{2}} e^{2πiαn} = ∑_{n=− \frac{k−1}{2}}^{\frac{k−1}{2}} cos(2παn).

By (4), each term in this sum, and therefore S_{K}(α) = |S_{K}(α)|, is decreasing in α. Thus, E_{k,u} ∩ [0, \frac{1}{2}] is an interval.

Proposition 3.4. When k > 3u we have

β_{k,u} = \frac{\sqrt{6}}{π} \frac{1}{k} (\frac{u}{k})^{1/2} (1 + \frac{3u}{20k} + O(1)(\frac{u}{k})^{2}) .

Corollary 3.5. When k > 3u we have

μ_{max}(k, u) ≥ μ_{K}(u) ≥ \frac{2\sqrt{6}}{π} (\frac{u}{k})^{\frac{1}{2}} \frac{1}{k} .

Proof of proposition 3.4. Set β = πβ_{k,u}. Then

u = k − \frac{sin(kβ)}{sin(β)}.

We notice first that

0 ≤ \frac{sin(kβ)}{sin(β)} − \frac{sin(kβ)}{β} = \frac{sin(kβ)}{sin(β)} (\frac{β − sin(β)}{β})

≤ k (\frac{β^{3}/6}{β}) = \frac{k^{3}β^{2}}{6} \frac{1}{k^{2}} .

LARGE TRIGONOMETRIC SUMS 7

Now expand

\begin{aligned}k − \frac{sin(kβ)}{β} & = β^{−1}(kβ − sin(kβ)) \\ & = β^{−1} (\frac{(kβ)^{3}}{6} − \frac{(kβ)^{5}}{120} + \frac{(kβ)^{7}}{7!} − …) \\ & = \frac{k^{3}β^{2}}{6} (1 − \frac{6(kβ)^{2}}{120} + \frac{6(kβ)^{4}}{7!} − …) . \end{aligned} (5)

It follows that

\frac{k^{3}β^{2}}{6} (1 − \frac{(kβ)^{2}}{20} + \frac{(kβ)^{4}}{840} ) ≥ u ≥ \frac{k^{3}β^{2}}{6} (1 − \frac{(kβ)^{2}}{20} − \frac{1}{k^{2}} ) .

Thus,

\frac{6u}{k^{3}} (1 − \frac{(kβ)^{2}}{20} + \frac{(kβ)^{4}}{840} )^{−1} ≤ β^{2} ≤ \frac{6u}{k^{3}} (1 − \frac{(kβ)^{2}}{20} − \frac{1}{k^{2}} )^{−1} .

We now plug here our first estimate kβ ≤ π from (4) to iterate estimates on (kβ)^{2}. First, since we assume k > 3u > 3,

1 − \frac{(kβ)^{2}}{20} − \frac{1}{k^{2}} > \frac{1}{3},

so

(kβ)^{2} < 18\frac{u}{k}.

Applying this and using 1/k^{2} < u/(3k) we now get

6\frac{u}{k} ≤ (kβ)^{2} < 6\frac{u}{k} (1 + \frac{2u}{k}) .

Thus

\frac{6u}{k^{3}} (1 − \frac{6u}{20k} + \frac{6^{2}}{840} (\frac{u}{k})^{2})^{−1} ≤ β^{2}

and

\frac{6u}{k^{3}} (1 − \frac{6u}{20k} − \frac{12}{20} (\frac{u}{k})^{2} − (\frac{u}{k})^{2})^{−1} ≥ β^{2}.

The proposition follows easily from this.

4. An Upper Bound For μ_{max}(k, u)

We will prove the upper bound

μ_{max}(k, u) ≤ \frac{d}{k} (\frac{u}{k})^{\frac{1}{2}}

for a constant d ≈ 4.04 that will be defined later. Note that this is of the same type as the lower bound we got in corollary 3.5. We will need a few lemmas. Lemma 4.1. For any u and k we have

μ_{max}(k, u) ≤ \frac{k}{(k − u)^{2}} .

Proof. Since s_{K}(α) ≥ k − u on a set of measure μ_{K}(u), we have

(k − u)^{2}μ_{K}(u) ≤ ∫_{0}^{1} s_{K}(α)^{2}dα.

The right hand side can be explicitly computed.

∫_{0}^{1} s_{K}(α)^{2}dα = ∫_{0}^{1} S_{K}(α)\overline{S_{K}(α)}dα

= ∫_{0}^{1} (∑_{n=1}^{k} e^{2πiαa_{n}}) ( ∑_{m=1}^{k} e^{−2πiαa_{m}}) dα

= ∑_{n,m=1}^{k} ∫_{0}^{1} e^{2πiα(a_{n}−a_{m})}dα

= ∑_{n=m=1}^{k} ∫_{0}^{1} 1dα = k.

This immediately implies the result.

Lemma 4.2. Let p_{1}, p_{2}, …, p_{k} be real positive numbers such that ∑_{i=1}^{k} p_{i} = 1. Let a_{i}, i = 1, …, k, be integers. Set ϕ(α) = ∑_{i=1}^{k} p_{i}e^{2πiαa_{i}}. Then,

|ϕ(α_{1} + α_{2})| ≥ |ϕ(α_{1})||ϕ(α_{2})| − \sqrt{1 − |ϕ(α_{1})|^{2}}\sqrt{1 − |ϕ(α_{2})|^{2}}.

Proof. We reproduce the proof given in [5, Lemma 1]. Let

v_{0} = (\sqrt{p_{1}}, …, \sqrt{p_{k}}),
v_{1} = (\sqrt{p_{1}}e^{2πiα_{1}a_{1}}, …, \sqrt{p_{k}}e^{2πiα_{1}a_{k}}),
v_{2} = (\sqrt{p_{1}}e^{2πiα_{2}a_{1}}, …, \sqrt{p_{k}}e^{2πiα_{2}a_{k}}),

be three unit vectors in ℂ^{k}. Then |ϕ(α_{1} + α_{2})| = cos θ(v_{1}, v_{2}) and |ϕ(α_{i})| = cos θ(v_{i}, v_{0}) for i = 1, 2, where θ(v, w) is the angle between the vectors v and w. Since θ(v_{1}, v_{2}) ≤ θ(v_{1}, v_{0}) + θ(v_{2}, v_{0}) we have

|ϕ(α_{1} + α_{2})| ≥ cos θ(v_{1}, v_{0}) cos θ(v_{2}, v_{0}) − sin θ(v_{1}, v_{0}) sin θ(v_{2}, v_{0})
= cos θ(v_{1}, v_{0}) cos θ(v_{2}, v_{0})
− \sqrt{1 − cos^{2} θ(v_{1}, v_{0})}\sqrt{1 − cos^{2} θ(v_{2}, v_{0})}
= |ϕ(α_{1})||ϕ(α_{2})| − \sqrt{1 − |ϕ(α_{1})|^{2}}\sqrt{1 − |ϕ(α_{2})|^{2}}.

Corollary 4.3. For any set K and real numbers u_{1}, u_{2} we have E_{K,u_{1}} + E_{K,u_{2}} ⊆ E_{K,2(u_{1}+u_{2})}.

Proof. When u_{1} = u_{2} this was obtained in [5]. In the general case, putting in lemma 4.2 p_{i} = \frac{1}{k} and multiplying by k^{2} we get

ks_{K}(α_{1} + α_{2}) ≥ s_{K}(α_{1})s_{K}(α_{2}) − \sqrt{k^{2} − s_{K}(α_{1})^{2}}\sqrt{k^{2} − s_{K}(α_{2})^{2}}.

If we assume s_{K}(α_{i}) ≥ k − u_{i} for i = 1, 2, then we get

ks_{K}(α_{1} + α_{2}) ≥ (k − u_{1})(k − u_{2}) − \sqrt{k^{2} − (k − u_{1})^{2}}\sqrt{k^{2} − (k − u_{2})^{2}}
= k^{2} − k(u_{1} + u_{2}) + u_{1}u_{2} − \sqrt{u_{1}(2k − u_{1})}\sqrt{u_{2}(2k − u_{2})}.

By dropping the term u_{1}u_{2} and replacing 2k − u_{i} by k we see that

ks_{K}(α_{1} + α_{2}) ≥ k^{2} − k(u_{1} + u_{2}) − k(2\sqrt{u_{1}}\sqrt{u_{2}}).

Since 2\sqrt{u_{1}}\sqrt{u_{2}} ≤ u_{1} + u_{2} we get

ks_{K}(α_{1} + α_{2}) ≥ k^{2} − 2k(u_{1} + u_{2}),

which implies the result.

Lemma 4.4. If E ⊂ [0, 1) is closed and μ(E) ≤ \frac{1}{35}, then

μ(E + E (mod 1)) ≥ 2μ(E).

Proof. This is a result of Macbeath and Kneser (see [6] for reference). Also, this follows easily from the Theorem in [3, p. 46]. The referee informs me that this is also due to Raikov [7] with the relaxed condition μ(E) ≤ \frac{1}{2}.

Proposition 4.5. Put

c = \frac{\sqrt{2} − 1}{4\sqrt{2} − 1} ≈ 0.09 , d = \frac{1}{\sqrt{c}(1 − c)^{2}} ≈ 4.04 .

For k ≥ 50 and 15u < k we have

μ_{max}(k, u) ≤ \frac{d}{k} (\frac{u}{k})^{\frac{1}{2}} .

Proof. More precise restrictions on k and u are in fact k ≥ 35/(1 − c)^{2} and u < ck. From corollary 4.3 and lemma 4.4 it follows that

μ_{K}(4^{s}u) ≥ 2^{s}μ_{K}(u)

for every positive integer s for which μ_{K}(4^{s−1}u) ≤ \frac{1}{35}. On the other hand, by lemma 4.1 we have, for any s with 4^{s}u ≤ k,

μ_{K}(4^{s}u) ≤ \frac{k}{(k − 4^{s}u)^{2}} .

It follows that

μ_{max}(k, u) ≤ min (\frac{k}{2^{s}(k − 4^{s}u)^{2}} ) ,

where the minimum is taken over all the integers s such that

4^{s}u ≤ k and \frac{k}{(k − 4^{s−1}u)^{2}} ≤ \frac{1}{35}. (6)

To get a good upper bound we choose

s = [log_{4}(ck/u)] + 1,

where [ ] is the integral part and log_{4} is log in base 4. The conditions of the proposition guarantee that s is in the range (6). Also set t = log_{4}(ck/u) − (s − 1). Note that t ∈ [0, 1). We have

4^{s} = 4 · 4^{s−1} = 4^{1−t} (\frac{ck}{u} ) .

Therefore we obtain the bound

μ_{max}(k, u) ≤ \frac{1}{k} (\frac{u}{k})^{\frac{1}{2}} \frac{1}{\sqrt{4^{1−t}c} (1 − 4^{1−t}c)^{2}} .

Consider now \sqrt{4^{1−t}c} (1 − 4^{1−t}c)^{2} as a function of t. Its maximal value over [0, 1] is easily found. It is obtained at t = 1 and equals 1/d. This finishes the proof.

Remark 4.6. Here is the reasoning behind the choice of s. We are trying to minimize a function of the integer s. The replacement for a differential when computing a “critical value” in this situation is the difference of two successive values, but we may also consider the quotient of two such values, which is more natural here. Therefore, we look for an integer s for which the ratio of the expressions at s and s − 1 is closest to 1, i.e.,

2 (\frac{k − 4 (4^{s−1}u)}{k − (4^{s−1}u)})^{2} ≈ 1.

Solving this gives

4^{s−1} ≈ \frac{ck}{u} .

Remembering that s ∈ ℤ makes our choice clear. As mentioned above, we have arranged things so that this s will be in the range we are considering.

5. Structure Of K With Large E_{K,u}

In this section we will describe the structure of sets in the class 𝕂_{ψ}, where ψ is roughly the measure attained by an arithmetic progression. More precisely, set d_{1} = \frac{2\sqrt{6}}{π}. We let

ψ = \frac{d_{1}}{k} (\frac{u}{k})^{\frac{1}{2}}

and consider from now on a set K ∈ 𝕂_{ψ}. Towards the end of this section we will also describe a subclass satisfying property G_{ψ}.

Our initial restrictions on k and u in this section are that the restrictions of proposition 4.5 are satisfied for k and 4^{3}u. It is enough to require k ≥ 50 and 1000u < k. These assumptions will be strengthen later. Let d be defined as in proposition 4.5.

Lemma 5.1. For a constant c_{1} ≈ 0.75 there exists i ∈ {0, 1, 2} such that

μ(E_{K,4^{i}u} + E_{K,4^{i}u}) ≤ (2 + c_{1})μ(E_{K,4^{i}u}).

Proof. Assume by contradiction that for all 0 ≤ i ≤ 2 we have

μ(E_{K,4^{i}u} + E_{K,4^{i}u}) > (2 + c_{1})μ(E_{K,4^{i}u}).

Applying corollary 4.3 repeatedly we get

μ(E_{K,4^{3}u}) > (2 + c_{1})^{3}μ(E_{K,u}).

substituting the lower bound we imposed on μ(E_{K,u}) and the upper bound of proposition 4.5 on μ(E_{K,4^{3}u}) we get the inequality

2^{3}d > d_{1}(2 + c_{1})^{3}.

We fix c_{1} so that this last inequality fails, i.e., c_{1} = 2((d/d_{1})^{1/3} − 1). The approximation to c_{1} is recovered from the estimate d/d_{1} ≈ 2.59.

For a positive integer q we set

E_{q,δ} = ⋃_{r=0}^{q−1}[\frac{r}{q} − \frac{δ}{2}, \frac{r}{q} + \frac{δ}{2}] (mod 1).

The following lemma is proved in [5] on p.154-159.

Lemma 5.2. Let F ⊂ [0, 1) be a closed set such that μ(F) ≤ Const for some unspecified constant Const. Suppose that there exists 0 < c < 1 such that

μ(F + F) ≤ (2 + c)μ(F).

Then there exist β ∈ [0, 1) and a positive integer q such that

F ⊆ β + E_{q,δ},

where δ = \frac{(1+c)}{q}μ(F).

Lemma 5.3. Suppose F ⊆ β + E_{q,δ}, where δ = \frac{(1+c)}{q}μ(F), 0 < c < 1, Suppose in addition that μ(F) > 0, that 0 ∈ F and that −F = F (mod 1). Then F ⊆ E_{q,δ} and

E_{q,2δ} ⊆ F + F + F (mod 1).

Proof. To see that F ⊆ E_{q,δ} note first that E_{q,δ} is stable under translation by 1/q. Therefore, we may assume that |β| ≤ 1/2q. We know that 0 ∈ F ⊆ β + E_{q,δ}. This implies that |β| ≤ δ/2q. Finally, as F is stable under negation,

F ⊆ (β + E_{q,δ}) ∩ (−β + E_{q,δ}) = E_{q,δ−|β|} ⊆ E_{q,δ}.

When β = 0 the second part of the lemma is proved at the same place the previous lemma was.

From now, until the end of the paper, excluding section 6, we will be working under the following additional assumption

Assumption 5.4. Our u and k are such that

\frac{4.04}{k} (\frac{16u}{k})^{\frac{1}{2}} < Const,

where Const is the unknown constant of lemma 5.2.

Making this assumption allows one to use lemma 5.2 for our purposes. It is enough to require that k is big enough, of course. This assumption makes the results of this paper ineffective. It is our hope, however, that one can give an effective bound in lemma 5.2, and thereby for the entire paper.

Proposition 5.5. If K ∈ 𝕂_{ψ}, then there exist integers q and i ∈ {0, 1, 2} and a positive real number δ such that

1. We have the inclusions

E_{K,4^{i}u} ⊆ E_{q,δ} and E_{K,10·4^{i}u} ⊇ E_{q,2δ}.

2. We have the inequality

δ ≥ q^{−1}2^{i} \frac{d_{1}}{k} (\frac{u}{k})^{\frac{1}{2}} .

Proof. Let i ∈ {0, 1, 2} be the smallest integer for which the assertion of Lemma 5.1 holds. This lemma precisely says that Lemmas 5.2 and 5.3 can be applied in succession to F = E_{K,4^{i}u}. The implication is that there exist some positive integer q and some positive real number δ such that

E_{K,4^{i}u} ⊆ E_{q,δ} (7)

and

E_{q,2δ} ⊆ E_{K,4^{i}u} + E_{K,4^{i}u} + E_{K,4^{i}u}.

Corollary 4.3 implies that

E_{K,10·4^{i}u} ⊇ E_{K,4^{i}u} + E_{K,4^{i}u} + E_{K,4^{i}u}.

This gives the first assertion. The inclusion (7) implies

qδ = μ(E_{q,δ}) ≥ μ(E_{K,4^{i}u}) ≥ 2^{i}μ(E_{K,u}) ≥ 2^{i} \frac{d_{1}}{k} (\frac{u}{k})^{\frac{1}{2}} .

This gives the second assertion.

Proposition 5.6. Let q be a positive integer. If

E_{K,u} ⊃ \{0, q^{−1}, …, \frac{q − 1}{q}\},

then there exists an integer r such that the set

K_{r} = {a ∈ K : a ≡ r (mod q)}

satisfies

|K_{r}| ≥ k − 2u.

Proof. We have

q(k − u)^{2} ≤ ∑_{r=0}^{q−1} |S_{K}(r/q)|^{2} = ∑_{r=0}^{q−1} ∑_{m,n=1}^{k} e^{2πir(a_{n}−a_{m})/q}

= ∑_{m,n=1}^{k} ∑_{r=0}^{q−1} (e^{2πi(a_{n}−a_{m})/q})^{r} = ∑_{a_{m}≡a_{n} (q)} q

= q ∑_{r=0}^{q−1} |K_{r}|^{2} ≤ (q max |K_{r}|) ∑_{r=0}^{q−1} |K_{r}| = kq max |K_{r}|,

and therefore

max |K_{r}| ≥ k (1 − \frac{u}{k})^{2} ≥ k − 2u.

Let, for θ > 0,

b_{θ} = θ − ∫_{0}^{θ} | cos(πα)|dα.

Clearly, b_{θ} > 0. It is also easy to see that b_{θ} is increasing in θ because its derivative with respect to θ is 1 − | cos(πθ)| ≥ 0. Finally, one checks that 2b_{1/2} = b_{1}.

Proposition 5.7. Assume E_{K,u} ⊃ [0, δ] and set

ℓ_{i} = a_{k+1−i} − a_{i}, i = 1, …, k.

Then, for every 0 < θ < 1/2,

|\{i : |ℓ_{i}|δ ≥ θ\}| ≤ \frac{u}{b_{θ}} .

Proof. We have

δ(k − u) ≤ ∫_{0}^{δ} s_{K}(α)dα ≤ \frac{1}{2} ∑_{n=1}^{k} ∫_{0}^{δ} |e^{2πiαa_{k+1−n}} + e^{2πiαa_{n}} | dα

= \frac{1}{2} ∑_{n=1}^{k} ∫_{0}^{δ} |e^{2πiαℓ_{n}} + 1| dα = ∑_{n=1}^{k} ∫_{0}^{δ} | cos(παℓ_{n})|dα.

We bound each term from above. If |ℓ_{n}|δ ≤ θ, we use the trivial estimate

∫_{0}^{δ} | cos(παℓ_{n})|dα ≤ δ.

Otherwise, we make the change of variables

∫_{0}^{δ} | cos(παℓ_{n})|dα = \frac{1}{|ℓ_{n}|} ∫_{0}^{|ℓ_{n}|δ} | cos(πα)|dα.

When θ ≤ |ℓ_{n}|δ ≤ 1 we use the estimate

\frac{1}{|ℓ_{n}|} ∫_{0}^{|ℓ_{n}|δ} | cos(πα)|dα = \frac{1}{|ℓ_{n}|} (∫_{0}^{θ} | cos(πα)|dα + ∫_{θ}^{|ℓ_{n}|δ} | cos(πα)|dα)

≤ \frac{1}{|ℓ_{n}|} (θ − b_{θ} + |ℓ_{n}|δ − θ) = δ − b_{θ} \frac{1}{|ℓ_{n}|}

≤ δ(1 − b_{θ}).

When |ℓ_{n}|δ > 1 one finds similarly

\frac{1}{|ℓ_{n}|} ∫_{0}^{|ℓ_{n}|δ} | cos(πα)|dα ≤ δ − b_{1} \frac{[|ℓ_{n}|δ]}{|ℓ_{n}|}

≤ δ − \frac{1}{2}b_{1}δ = δ(1 − b_{\frac{1}{2}} ) ≤ δ(1 − b_{θ}).

Therefore,

δ(k − u) ≤ δ (k − b_{θ} · |{i : |ℓ_{i}|δ ≥ θ}|) ,

which proves what we wanted.

Lemma 5.8. Suppose k > 30000u and K ∈ 𝕂_{ψ}. Then there exists a unit vector v such that for any α ∈ E_{K,u} we have Angle(S_{K}(α), v) < π/2. In addition there is a subset K_{0} of K with at least k − 2000u elements such that the following is satisfied: For any a ∈ K_{0} and any α ∈ E_{K,u} one has Angle(v, e^{2πiαa}) < π/4.

Proof. By proposition 5.5 there exist i ∈ {0, 1, 2}, a positive integer q and a real number δ such that

E_{K,u} ⊆ E_{K,4^{i}u} ⊆ E_{q,δ}, E_{K,10·4^{i}u} ⊇ E_{q,2δ}.

Consider a parameter θ < 1/4 to be set later. According to proposition 5.7 all but 10 · 4^{i}u/b_{2θ} elements of K are in an interval of length ℓ such that ℓδ < 2θ, or equivalently 2πℓ(δ/2) < 2πθ. Further, all but 2 · 4^{i}u elements of these are in the same congruence class modulo q. We may translate K by an integer to make this interval symmetric around 0 and the residue class be that of 0. Now denote by K_{0} the intersection of K with the interval and the residue class of 0, and let K̄ = K − K_{0}. We will show the lemma with v = 1. One easily sees that the condition of the lemma is now equivalent to Re S_{K}(α)/|S_{K}(α)| > \sqrt{2}/2. We will in fact show this for all α in the bigger set E_{q,δ}. Consider such an α and a ∈ K_{0}. Suppose first that α is in the interval of E_{q,δ} around 0. Since |a| ≤ ℓ/2 we have

| arg(e^{2πiaα})| = |2πaα| ≤ 2π(ℓ/2)(δ/2) < πθ.

Therefore, Re e^{2πiaα} > cos(θπ). Now, since elements of K_{0} are divisible by q, it is easily seen that they behave the same on all intervals of E_{q,δ}. Thus, the same estimate is true for any α ∈ E_{q,δ}. Since K_{0} contains at least k − (10b_{2θ}^{−1} + 2)4^{i}u elements, this implies that for α ∈ E_{q,δ} we have

Re S_{K_{0}} > cos(θπ) (k − (10b_{2θ}^{−1} + 2)4^{i}u) .

Therefore

\frac{Re S_{K}(α)}{|S_{K}(α)|} ≥ \frac{Re S_{K_{0}}(α) − |SK̄(α)|}{k}

> \frac{cos(θπ)(k − (10b_{2θ}^{−1} + 2)4^{i}u) − (10b_{2θ}^{−1} + 2)4^{i}u}{k}.

Thus, the lemma will be true if we can find a θ < 1/4 for which the right hand side is larger than \sqrt{2}/2. Clearly the worst possible case is when i = 2, in which we need to solve

\frac{cos(θπ)(k − (160b_{2θ}^{−1} + 32)u) − (160b_{2θ}^{−1} + 32)u}{k} > \frac{\sqrt{2}}{2}.

This inequality is equivalent to

\frac{k}{u} > (160b_{2θ}^{−1} + 32)(1 + cos(πθ)) (cos(πθ) − \frac{\sqrt{2}}{2})^{−1} .

It remains to numerically find the minimum of the expression on the right over θ ∈ [0, 1/4]. This is found to be about 29439, located around θ = 0.19272. The result follows with the bound on the number of elements outside K_{0} being 160b_{2θ}^{−1} + 32 ≈ 1860 times u.

Proposition 5.9. Suppose k > 30000u. Then, the following subclass of 𝕂_{ψ} has property G_{ψ}. A set in the class can be written as a disjoint union

M = M_{0} ∪ K̄ with |K̄| < 2000u,

where M_{0} is an arithmetic progression with at most one gap.

Proof. Suppose K ∈ 𝕂_{ψ}. We will show how to find a set M in the subclass described above such that μ_{M}(u) ≥ μ_{K}(u). By the previous lemma we know that we have a decomposition K = K_{0} ∪ K̄ and that there is a unit vector v such that for all α ∈ E_{K,u} both the sum S_{K}(α) and any individual term e^{2πiαa}, with a ∈ K_{0}, form an angle of < π/4 with v. In the situation just described it is easily seen that by replacing a > b ∈ K_{0} by c = a − qt, d = b + qt, such that c > d and c, d ∉ K_{0}, we enlarge the value of S_{K}(α) for α ∈ E_{q,δ}. This is because the contribution of the pair (c,d) is larger than that of (a, b) and has the same direction which forms an acute angle with the rest of the sum. Therefore, such a change can only increase the value of μ_{K,u}. All that remain to do then is to show that by repeated application of this we transform K_{0} into a set M_{0} which is an arithmetic progression of difference q with possibly one gap. To see this we may again assume that elements of K_{0} are divisible by q. Suppose that e = max(K_{0}), f = min(K_{0}) and consider the set

K_{comp} = {x ∈ qℤ : f ≤ x ≤ e and x ∉ K_{0}}.

Let c = max(K_{comp}) and d = min(K_{comp}). Suppose that K_{comp} ≠ ϕ and that c ≠ d. Since a = c + q ∈ K_{0} and b = d − q ∈ K_{0}, we may perform a transformation as above. It is clear that each step decreases the sum of the absolute values of all the differences between the elements of K_{0}. Therefore the process has to stop. The computation above shows that it stops only when K_{comp} has at most one element. This means that the resulting set, has at most one gap.

6. A close to maximal set

In this section we describe a set K_{ex} which we suspect to be very close to maximal. Just how close will become evident later on. We will begin with parameters m_{0} and w and construct a set M(m_{0}, w). This will roughly be our set K_{ex} except that we can not guarantee in general that it will have exactly k elements. We will choose the parameters so that it has about k elements and then take out as many elements as we need to get it to be of the right size.

We assume we are given an odd positive integer m_{0} and a real number w which satisfy the assumption m_{0} > 30000w. Let M_{0} be the set {−(m_{0} − 1)/2, …, (m_{0} − 1)/2} of size m_{0}. Clearly |S_{M_{0}}| = S_{M_{0}}. We write β for β_{m_{0},w}. According to definition 3.2, β satisfies S_{M_{0}}(β) = m_{0} − w and furthermore E_{M_{0}}(w) = [−β, β].

Construction 6.1. Given m_{0} and w we construct the set M(m_{0}, w) as follows:

M = M(m_{0}, w) = M_{0} ∪ \overline{M} = ⋃_{n∈ℤ} M_{n}, (8)

where each M_{n} is an arithmetic progression of difference 1 centered (as best possible) around \frac{n}{β}. For n > 0, the length of the two progressions M_{±n} is the same and is denoted by \frac{m_{n}}{2} . To fully determine M(m_{0}, w) one only needs to give the number m_{n}. It will be defined to be the largest even integer smaller than a constant c_{n}, whose description is given in definition 6.3 below, and which has the approximation, given in proposition 6.8,

c_{n} ≈ \frac{2w}{(πn)^{2}} (1 − \frac{(−1)^{n}}{2} ) .

We note that c_{n} < 2 for n >> 0, hence m_{n} = 0 for all but finitely many values of n. Also m_{n} is always non-negative (see remark 6.9).

To define the constants c_{n} we need an auxiliary function f.

Definition 6.2. We define a function f = f_{m_{0},w} on [0, 1] as

f_{m_{0},w}(r) = \begin{cases}s_{m_{0}}(βr) − m_{0} + w & if r ∈ [\frac{1}{2}, 1] \\ f_{m_{0},w}(1 − r) & if r ∈ [0, \frac{1}{2}]. \end{cases}

Note that f(r) is a continuous function such that

f(0) = f(1) = s_{m_{0}}(β) − (m_{0} − w) = 0

by the definition of β = β_{m_{0},w}. Also, by construction, f is symmetric around 1/2, which implies that in its real Fourier expansion all the sin functions do not appear. Finally, for all r ∈ [0, 1], f(r) ≥ 0. It is enough to check this by symmetry for r ≥ 1/2, in which case βr ∈ E_{M_{0}}(w) hence s_{m_{0}}(βr) ≥ m_{0} − w.

Definition 6.3. Define real numbers c_{n} = c_{n}(m_{0}, w) for n ≥ 0 in such a way that the real Fourier expansion of f is

f(r) = c_{0} − ∑_{n=1}^{∞} c_{n} cos(2πnr). (9)

Define m_{n} as the largest even number smaller than c_{n}.

We have the usual integral expansions of c_{n},

(10)  c_{0} = ∫_{0}^{1} f(r) dr = 2 ∫ 1_{\frac{1}{2}} f(r) dr

and

(11)  c_{n} = −4 ∫ 1_{\frac{1}{2}} f(r) cos(2πnr) dr.

The Fourier expansion (9) clearly converges pointwise on [0, 1] because f is continuous and piecewise differentiable. Substituting r = 0 we have

c_{0} = ∑_{n=1}^{∞} c_{n}. (12)

Remark 6.4. The heuristic reasoning behind construction 6.1 is as follows: We are looking for a set M of the form (8). The number β is defined so that E_{M,w} ⊆ [−β, β] whatever \overline{M} is, so best we can hope for is near equality. We would also like to make m̄ = ∑_{n>0} m_{n} (and therefore m = |M|) as large as possible. Since S_{M_{0}} is real and large, it is easily seen that the best way to enlarge S_{M} is to contribute to its real part. Thus we assume from the start that \overline{M} is symmetric around 0. Then S_{M} is real valued. Therefore, the condition for α to be in E_{M,w} becomes S_{M}(α) ≥ k − w, which is equivalent to

m̄ − S\overline{M}(α) ≤ S_{M_{0}}(α) − m_{0} + w (13)

Suppose it was possible to have β ∈ E_{M,w}. Then we get m̄ − S\overline{M}(β) = 0 and thus e^{2πaβi} = 1 for a ∈ \overline{M}. This implies that each a ∈ \overline{M} is of the form a = \frac{n}{β} for some n ≠ 0. Set

e_{n} = |\{a = ±\frac{n}{β} ∈ \overline{M}\}|.

We can therefore write

f\overline{M}(r) := m̄ − S\overline{M}(βr) = m̄ − ∑_{n=1}^{∞} e_{n} cos(2πnr).

The function f\overline{M} satisfies f\overline{M} ≤ f since this is true on [1/2, 1] by (13) and since both sides are symmetric for replacing r by 1 − r. Conversely, for any symmetric f\overline{M} ≤ f we can, replacing f by f\overline{M} in definition 6.3 and what follows, find constants e_{n} and create an \overline{M} that will satisfy (13). But since we want the largest m̄ = e_{0} it is clear we should take f\overline{M} = f. Then we make the necessary adjustments to get from the c_{n} to a true candidate for \overline{M} by taking m_{n} to be the largest even number smaller than c_{n} and \overline{M} as a union of arithmetic progressions centered on ±n/β and of length m_{n}/2 each, which is just the construction 6.1.

We now derive estimates on the parameters of M and the size of E_{M,w}.

Lemma 6.5. Let n be an integer. Then,

sup_{\begin{matrix}z∈ℂ \\ |z|≤ \frac{1}{n} \end{matrix}} \frac{sin(nz)}{sin(z)} ≤ e^{\frac{1}{n}} · 1.2n.

Proof. We have

\frac{sin(nz)}{sin(z)} = \frac{e^{inz} − e^{−inz}}{e^{iz} − e^{−iz}} = e^{i(1−n)z} \frac{e^{2inz} − 1}{e^{2iz} − 1} = e^{i(1−n)z} ∑_{k=0}^{n−1} e^{2ikz}.

If z = x − iy, then, since |e^{iz}| = e^{y}, we get the upper bound

|\frac{sin(nz)}{sin(z)}| ≤ e^{−(n−1)y} ∑_{k=0}^{n−1} e^{2ky} = ∑_{\begin{matrix}1−n≤l≤n−1 \\ 2|n−1−l \end{matrix}} e^{ly}.

It is enough to find the maximal value of the last expression for −1/n ≤ y ≤ 1/n. It is clear that the expression is symmetric in y. The derivative is given by

∑_{\begin{matrix}1≤l≤n−1 \\ 2|n−1−l \end{matrix}} l(e^{ly} − e^{−ly}),

which is clearly positive for positive y. Therefore, the maximal value is obtained at y = 1/n and equals

e^{− \frac{n−1}{n}} ∑_{k=0}^{n−1} e^{\frac{2k}{n}} = e^{− \frac{n−1}{n}} \frac{e^{2} − 1}{e^{\frac{2}{n}} − 1}.

Using the inequality e^{x} − 1 ≥ x we obtain

|\frac{sin(nz)}{sin(z)}| ≤ e^{− \frac{n−1}{n}} (e^{2} − 1)\frac{n}{2} = e^{\frac{1}{n}} \frac{e^{2} − 1}{2e}n ≤ e^{\frac{1}{n}} · 1.2n.

Let

f(r) = w + ∑_{j=1}^{∞} a_{j}r^{2j}

be the expansion of f(r) on the interval [1/2, 1]. In other words, it is the Taylor expansion of s_{m_{0}}(βr) − m_{0} + w around 0. Note that the odd coefficients vanish because s_{m_{0}} is an even function, and that since its value at 0 is m_{0} the constant coefficient is indeed w. Let

R_{2}(r) := f(r) − w − a_{1}r^{2}

be the error term in the quadratic approximating of f(r).

Lemma 6.6. Let c = 6(w/m_{0})(1 + 2w/m_{0}) and define

h(r) := 2m_{0} \frac{(cr^{2})^{2}}{1 − cr^{2}} .

Then, for r ∈ [1/2, 1] and any n ≥ 1,

|\frac{d^{n}}{dr^{n}} R_{2}(r)| ≤ \frac{d^{n}}{dr^{n}} h(r).

Proof. We give an upper bound on the coefficients a_{j}. From the explicit description of s_{m_{0}} given in part 1 of proposition 3.1, we see the the complex function sin(m_{0}z)/ sin(z) extends the real function s_{m_{0}}(α/π). Consider the Taylor expansion

sin(m_{0}z)/ sin(z) = ∑_{j=0}^{∞} b_{j}z^{j}.

By lemma 6.5 we see that since m_{0} ≥ 3, s_{m_{0}}(z/π) = sin(m_{0}z)/ sin(z) is bounded by 2m_{0} when |z| ≤ 1/m_{0}. We use the Cauchy integral formula on a circle C_{m_{0}} of radius 1/m_{0} around 0 to obtain the estimate

|b_{j}| = |\frac{1}{2πi} ∮_{C_{m_{0}}} \frac{sin(m_{0}z)/ sin(z)}{z^{j+1}}dz| < 2m_{0}^{j+1}.

From the definition of f we see that for j > 0 we have a_{j} = b_{2j}(πβ)^{2j}. From the bound on β in proposition 3.4 we get for j > 0

|a_{j}| < 2m_{0}^{2j+1} ((\frac{6w(1 + 2u/m_{0})}{m_{0}})^{\frac{1}{2}} \frac{1}{m_{0}} )^{2j} = 2m_{0}c^{j}.

One easily checks that

h(r) = 2m_{0} ∑_{j=2}^{∞} c^{j}r^{2j}.

The bound is now clear.

Corollary 6.7. We have the following estimates for r ∈ [1/2, 1] and δ ∈ [0, 1/2].

(6.7.1)  R_{2}(r) ≤ 75\frac{w^{2}}{m_{0}} r^{4}.
(6.7.2)  R′_{2}(r) ≤ 300\frac{w^{2}}{m_{0}} r.
(6.7.3)  |w + a_{1}| ≤ 75\frac{w^{2}}{m_{0}} .
(6.7.4)  |f′(r) + 2wr| ≤ 450\frac{w^{2}}{m_{0}} r.
(6.7.5)  f(1 − δ) ≤ 2δw (1 + 225\frac{w}{m_{0}} ) .

Proof. To prove (6.7.1) we note that

R_{2}(r) ≤ h(r) ≤ 2m_{0} \frac{c^{2}}{1 − c}r^{4} = 2 · 6^{2} \frac{w^{2}}{m_{0}} r^{4}(1 + o(ϵ)) ≤ 75\frac{w^{2}}{m_{0}} r^{4}.

Similarly, we get (6.7.2) because

\begin{aligned}h′(r) & = 4m_{0}c^{2}r^{3} \frac{2 − r^{2}c}{(1 − cr^{2})^{2}} ≤ 8m_{0} \frac{c^{2}}{(1 − c)^{2}} r \\ & ≤ 8 · 36\frac{w^{2}}{m_{0}} r(1 + o(ϵ)) ≤ 300\frac{w^{2}}{m_{0}} r. \end{aligned} (14)

Since f(1) = 0 we find

|w + a_{1}| = |f(1) − w − a_{1}1^{2}| = |R_{2}(1)| ≤ h(1),

which is ≤ 75w^{2}/m_{0} by (6.7.1). This gives (6.7.3). We get (6.7.4) by

|f′(r) + 2wr| = |R′_{2}(r) + 2(w + a_{1})r| ≤ h′(r) + 2 · 75\frac{w^{2}}{m_{0}} r ≤ 450\frac{w^{2}}{m_{0}} r,

where the last two inequalities follow from (6.7.3) and (6.7.2) respectively. Finally, (6.7.5) is derived from (6.7.4) by the mean value theorem: Since f(1) = 0 we can find 1 − δ < ρ < 1 such that |f(1 − δ)| ≤ δ|f′(ρ)|. By (6.7.4) we find

|f′(ρ)| ≤ 2uρ + 450\frac{w^{2}}{m_{0}} ρ ≤ 2u + 450\frac{w^{2}}{m_{0}} = 2u (1 + 225\frac{w}{m_{0}} ) ,

which finishes the proof.

Proposition 6.8. We have the following estimates on the coefficients c_{n}.

(6.8.1)  c_{0} = \frac{5}{12}w + 75\frac{w^{2}}{m_{0}} O(1).
(6.8.2)  c_{n} = \frac{2w}{(πn)^{2}} (1 − \frac{(−1)^{n}}{2} ) + \frac{1500}{(πn)^{2}} \frac{w^{2}}{m_{0}} O(1).

Remark 6.9. In particular, c_{n} is positive for every n and hence we can indeed define m_{n} as we did in construction 6.1.

Lemma 6.10. For any C^{∞} real valued function g and any nonzero integer n we have

∫ 1_{\frac{1}{2}} cos(2πnr)g(r)dr

= \frac{1}{(2πn)^{2}} (g′(1) − (−1)^{n}g′ (\frac{1}{2}) − ∫ 1_{\frac{1}{2}} cos(2πnr)g′′(r)dr) .

Proof. We use integration by parts twice to get

Re ∫ 1_{\frac{1}{2}} e^{2πinr}g(r)dr

= Re (\frac{1}{2πni} (g(1) − (−1)^{n}g (\frac{1}{2}) − ∫ 1_{\frac{1}{2}} e^{2πinr}g′(r)dr))

= Re (\frac{−1}{(2πni)^{2}} (g′(1) − (−1)^{n}g′ (\frac{1}{2}) − ∫ 1_{\frac{1}{2}} e^{2πinr}g′′(r)dr)) .

Writing out the real part in terms of cos functions gives the result.

Proof of proposition 6.8. Taking g(r) = 1 and g(r) = r^{2} respectively in lemma 6.10 we get

(15)  ∫ 1_{\frac{1}{2}} cos(2πnr)dr = 0,

(16)  ∫ 1_{\frac{1}{2}} cos(2πnr)r^{2}dr = \frac{2}{(2πn)^{2}} (1 − \frac{(−1)^{n}}{2} ) ≤ \frac{3}{(2πn)^{2}} .

Now we use g(r) = R_{2}(r) as defined in lemma 6.6. In the inequality of lemma 6.10 we can replace R_{2} and its derivatives by the function h and its derivative, as follows from lemma 6.6. This gives

|∫ 1_{\frac{1}{2}} cos(2πnr)R_{2}(r)dr| ≤ \frac{1}{(2πn)^{2}} (h′(1) + h′(\frac{1}{2}) + ∫ 1_{\frac{1}{2}} h′′(r)dr) .

Evaluating the right hand side we find

|∫ 1_{\frac{1}{2}} cos(2πnr)R_{2}(r)dr| ≤ \frac{2h′(1)}{(2πn)^{2}} ≤ 150\frac{w^{2}}{m_{0}} \frac{1}{(πn)^{2}} , (17)

where the inequality follows from the estimate (14). By definition,

f(r) = R_{2}(r) + w + a_{1}r^{2} = R_{2}(r) + w(1 − r^{2}) + (w + a_{1})r^{2}.

Here, the main term is w(1 − r^{2}). Therefore, The main terms in the estimates on c_{n} and c_{0} are

c_{n} ≈−4w ∫ 1_{\frac{1}{2}}(1 − r^{2}) cos(2πnr) dr = \frac{2w}{(πn)^{2}} (1 − \frac{(−1)^{n}}{2} ) ,

c_{0} ≈ 2w ∫ 1_{\frac{1}{2}}(1 − r^{2})dr  = \frac{5}{12}w.

The error term for c_{n} is now obtained by integrating R_{2}(r)+(w+a_{1})r^{2} multiplied by cos(2πnr) and the appropriate constant, and the integral is estimated using (15),(16) and (17). For n > 0 we get

|c_{n} − \frac{2w}{(πn)^{2}} (1 − \frac{(−1)^{n}}{2} )| = 4 |∫ 1_{\frac{1}{2}} cos(2πnr) (R_{2}(r) + (w + a_{1})r^{2}) dr|

≤ 4 (150\frac{w^{2}}{m_{0}} \frac{1}{(πn)^{2}} + 75\frac{w^{2}}{m_{0}} \frac{3}{(πn)^{2}} )

= 1500\frac{w^{2}}{m_{0}} \frac{1}{(πn)^{2}} .

Similarly for c_{0} we find

|c_{0} − \frac{5}{12}w| = 2 |∫ 1_{\frac{1}{2}}(f(r) − w(1 − r^{2}))dr|

≤ 2 |∫ 1_{\frac{1}{2}} R_{2}(r)dr| + 2 |∫ 1_{\frac{1}{2}}(a_{1} + w)r^{2}dr|

≤ 2 |∫ 1_{\frac{1}{2}} 75\frac{w^{2}}{m_{0}} r^{4}dr| + 2 · \frac{1}{3} · \frac{7}{8}(a_{1} + w)

≤ \frac{2}{5} · 75\frac{w^{2}}{m_{0}} + \frac{2}{3} · \frac{7}{8} · 75\frac{w^{2}}{m_{0}} ≤ 75\frac{w^{2}}{m_{0}} .

We now wish to modify the set M to make it our candidate set K_{ex}. We need a few more computations.

Lemma 6.11. Let ω be a real constant. Then we have

∑_{n=1}^{∞} min (\frac{ω}{n^{2}} , 2) ≤ 4.2\sqrt{ω}.

Proof. Recall that ∑ 1/n^{2} = π^{2}/6. We begin by considering small values of ω. If ω ≤ 2, then the sum is clearly ωπ^{2}/6 ≤ \sqrt{ω}\sqrt{2}π^{2}/6. Similar computations show that when 2 < ω ≤ 4 we get a bound of \sqrt{ω}π^{2}/3 and when 4 < ω ≤ 9 we get a bound of

3 (\frac{π^{2}}{6} − \frac{1}{4}) \sqrt{ω} ≤ 4.2\sqrt{ω},

which is the largest so far. Now suppose that 9 ≤ ω. Let x = \sqrt{ω/2}. One checks that 2x^{2}/(x − 1) ≤ 3x + 2, It is easily seen that the largest n for which ω/n^{2} ≥ 2 is [x]. Thus we have

∑_{n=1}^{∞} min (\frac{ω}{n^{2}} , 2) ≤ 2[x] + ω ∑_{n=[x]+1}^{∞} \frac{1}{n^{2}} ≤ 2[x] + ω ∫_{[x]}^{∞} \frac{dt}{t^{2}} = 2[x] + \frac{ω}{[x]}

≤ 2(x − 1) + \frac{ω}{x − 1} = 2x + \frac{2x^{2}}{x − 1} − 2

≤ 5x = \frac{5}{\sqrt{2}}\sqrt{ω} ≤ 4.2\sqrt{ω}.

Proposition 6.12. Suppose k and u satisfy the condition 1 < u ≤ k/30000. Then there exist m_{0}, m̄ ∈ ℤ, w ∈ ℝ and a set K_{ex} = K_{ex}(k, u), such that the following are satisfied.

k = m_{0} + m̄. (6.12.1)

M_{0} ⊆ K_{ex} ⊆ M(m_{0}, w). (6.12.2)

E_{K_{ex},u} ⊇ [−β, β], with β = β_{m_{0},w}. (6.12.3)

c_{0}(m_{0}, w) ≥ m̄ ≥ c_{0}(m_{0}, w) − 5.2\sqrt{w}. (6.12.4)

u = w + (\frac{w}{k} )^{3} w + 2 (\frac{w}{k} )^{3/2} . (6.12.5)

Remark 6.13. Note that c_{0}(m_{0}, w) depends on w and m_{0} but to first order is just \frac{5}{12}w ≈ \frac{5}{12}u.

Proof of proposition 6.12. We start by choosing w such that (6.12.5) is satisfied. For a given m_{0} set m̃ = ∑_{n=1}^{∞} m_{n} and m = m_{0} + m̃ = |M(m_{0}, w)|. We take the smallest m_{0} for which m ≥ k. We now pull elements out of the sets M_{n} until we obtain our set K_{ex} (the choice of which elements to take is arbitrary, hence K_{ex} is not uniquely defined). By (12) and the construction of the m_{n} in 6.1 we find the left inequality in (6.12.4). To get the inequality on the right we need to compute the sum of the differences between c_{n} and m_{n} and count how many elements we take out of the M_{n} in the final step. Recall that m_{n} was taken to be the largest even integer smaller than c_{n}. Therefore,

c_{0} − m̃ = ∑_{n=1}^{∞} c_{n} − m_{n} ≤ ∑_{n=1}^{∞} min(c_{n}, 2).

Let ω = (3w/π^{2})(1 + o(ϵ)). It follows from (6.8.2) that

c_{0} − m̃ ≤ ∑_{n=1}^{∞} min (\frac{ω}{n^{2}} , 2) ,

which by lemma 6.11 is

≤ 4.2\sqrt{\frac{3}{π^{2}}} (1 + o(ϵ))\sqrt{u} ≤ 2.4\sqrt{u}.

The number of elements we may have to take out of M(m_{0}, w) to get K_{ex} is bounded from above by |M(m_{0}, w)|−|M(m_{0} −2, w)|. The difference in size between the two sets is caused by the fact that we have m_{n}(m_{0}, w) − m_{n}(m_{0} − 2, w) = 2 every time there is a multiple of 2 between c_{n}(m_{0}, w) and c_{n}(m_{0} − 2, w). With the constant ω as before, this does not occur once n > \sqrt{ω/2}. Thus,

m − k ≤ 2 + 2\sqrt{ω/2} ≤ 2 + 0.78\sqrt{u} ≤ 2.78\sqrt{u}.

This gives (6.12.4) as 2.4 + 2.78 ≤ 5.2. It remains to show (6.12.3). From the definition of f we see that for r ≥ 1/2,

S_{M_{0}}(βr) − m_{0} + w = f(r) = c_{0} − ∑_{n=1}^{∞} c_{n} cos(2πnr) = ∑_{n=1}^{∞} c_{n}(1 − cos(2πnr)),

where the last equality follows from (12). Since m_{n} ≤ c_{n} we find

S_{M_{0}}(βr) − m_{0} + w ≥ ∑_{n=1}^{∞} m_{n}(1 − cos(2πnr)) = m̃ − ∑_{n=1}^{∞} m_{n} cos(2πnr)

and, rearranging terms

S_{M_{0}}(βr) + ∑_{n=1}^{∞} m_{n} cos(2πnr) ≥ m_{0} + m̃ − w = m − w. (18)

Comparing the situation for r < \frac{1}{2}, we see that S_{M_{0}} is larger while the rest is symmetric around \frac{1}{2} and therefore the last inequality holds for r ∈ [0, 1]. Each term m_{n} cos(2πnr) is very close to S_{M_{n}}(rβ) + S_{M_{−n}}(rβ). We measure the difference in the following lemma.

Lemma 6.14. Let A = {s, s+1, …, t−1, t} be an arithmetic progression of length l = t − s + 1. Suppose α ∈ [0, 1/l] and suppose x ∈ ℝ satisfies |x − x′| ≤ 1/2, with x′ = (s + t)/2. Then,

| Re(le^{2πixα} − S_{A}(α))| ≤ πlα + \frac{π^{2}}{6} l^{3}α^{2}.

Proof. Suppose first that x = x′. Then,

| Re(le^{2πixα} − S_{A}(α))| = |l − e^{−2πixα}S_{A}(α)|.

It is easy to see that the expression inside the absolute value is real, positive and equal to

l − s_{l}(α) = l − \frac{sin(πlα)}{sin(πα)} ≤ \frac{sin(πlα)}{πα} ≤ \frac{π^{2}}{6} l^{3}α^{2},

where the last inequality follows from (5). To complete the proof all we have to do is to compute

| Re(le^{2πixα} − le^{2πix′α})| = |l(cos(2πxα) − cos(2πx′α))| ≤ l|2π(x − x′)α| ≤ πlα.

Applying the last lemma in our situation we see, using the fact that ∑ m_{n}^{3} ≤ m̃^{3}, that

∑_{n=1}^{∞} m_{n} cos(2πnr) − 2 Re S_{M_{n}}(βr) ≤ πm̃β + \frac{π^{2}}{6} m̃^{3}β^{2}

≤ (π \frac{w}{2} \frac{\sqrt{6}}{π} (\frac{w}{m_{0}} )^{\frac{1}{2}} \frac{1}{m_{0}} + \frac{π^{2}}{6} \frac{w^{3}}{8} \frac{6}{π^{2}} (\frac{w}{m_{0}} ) \frac{1}{m_{0}^{2}} ) (1 + o(ϵ))

by (6.8.1) and proposition 3.4

≤ (\frac{w}{k} )^{3} w + 2 (\frac{w}{k} )^{3/2} .

Thus, our choice of w in (6.12.5) guarantees by (18) that

S_{M}(βr) ≥ m − w − (\frac{w}{k} )^{3} w − 2 (\frac{w}{k} )^{3/2} = m − u

for all r ∈ [0, 1]. Therefore, E_{M,u} ⊇ [−β, β]. To finish we just need to note that taking elements out of M does not change the situation as is easily seen.

7. Structure of the maximal set

In the final three sections we try to determine the structure of a set K in the class 𝕂_{μ_{Kex} (u)}, i.e., a set which is “better” than the example we produced in the last section.

Our assumptions are as usual: 1 < u ≤ k/30000 and u and k satisfy assumption 5.4. Since μ_{K_{ex}}(u) is greater than the one for arithmetic progressions, we certainly know that our results from section 5 Apply here. Therefore, we can write K in the form K = K_{0} ∪ \overline{K}, where K_{0} is the set whose existence is guaranteed by lemma 5.8, |K_{0}| = k_{0}, |\overline{K}| = k̄, and k_{0} + k̄ = k. What we will try to do is determine the structure of \overline{K}. Since, as we saw in proposition 5.9, There is, for any set in 𝕂_{μ_{Kex} (u)}, a better one with the corresponding K_{0} forming an arithmetic progression with at most a single gap, it is no harm to assume that our sets are already of this type. We will assume in fact that K_{0} is an arithmetic progression (without a gap), that it has an odd number of elements and that its difference is 1. The modifications required to cover the general case will be explained in the end. Since by (2) we are always allowed to translate our set, we can assume

K_{0} = \{−\frac{k_{0} − 1}{2}, …, \frac{k_{0} − 1}{2}\} .

We also make the following shortcut:

k̄ < \frac{1}{2}u. (19)

The justification for this is as follows: we have already seen this estimate with \frac{1}{2} replaced by 2000 in proposition 5.9. Shortly (in (7.4.1)) we will see that k̄ is to first order \frac{5}{12}u, where the second order terms depend on the above mentioned constant. Iterating this we can assume in advance that the constant is say \frac{1}{2}.

Let β′ = β_{k_{0},u}. Set

K_{n} = K ∩ [(n − \frac{1}{8})/β′, (n + \frac{1}{8})/β′], k_{n} = |K_{n}| + |K_{−n}|. (20)

We also write g = f_{k_{0},u}. By definition 6.2,

k_{0} − u = S_{K_{0}}(β′r) − g(r). (21)

This function has a fourier expansion similar to (9) and the coefficients c_{n}(k_{0}, u) will be denoted d_{n}. Obviously

E_{K,u} ⊆ [−β′, β′]. (22)

Definition 7.1. A constant δ ≥ 0 (depending on K and u) is defined by the equation

μ_{K}(u) = 2(1 − δ)β′.

In this section, δ appears in the error terms for the estimates of the k_{n}. To get absolute bounds we will bound δ in section 9.

The basis for the estimates is a bound for Re S\overline{K}.

Proposition 7.2. If α = β′r ∈ E_{K,u}, then

k̄ − Re S\overline{K}(α) ≤ g(r) (1 + \frac{2k̄}{k} ) ≤ g(r) (1 + \frac{u}{k}) .

Corollary 7.3. For all r ∈ [0, 1],

(23)  k̄ − Re S\overline{K}(β′r) ≤ \begin{cases}g(r) + \frac{u^{2}}{k} & if β′r ∈ E_{K,u} \\ u & otherwise. \end{cases}

Proof. When β′r ∈ E_{K,u} this is clear from the proposition since g(r) ≤ u. Otherwise we just use the trivial upper bound 2k̄, which is < u by (19).

proof of proposition 7.2. Assume α ∈ E_{K,u} but drop α from the notation. Since S_{K_{0}} is real valued we find

(S_{K_{0}} + Re S\overline{K})^{2} + Im S2 ; \overline{K} = |S_{K}|^{2} ≥ (k − u)^{2} = (S_{K_{0}} + k̄ − g(r))^{2},

where the last equality follows from (21). Expanding this, cancelling Re S2 ; \overline{K} +Im S2 ; \overline{K} on the left with k̄^{2} on the right and cancelling out S_{K_{0}}^{2} one gets

2S_{K_{0}} Re S\overline{K} ≥ g(r)^{2} + 2S_{K_{0}} k̄ − 2k̄g(r) − 2S_{K_{0}}g(r).

Rearranging terms we find

2S_{K_{0}}(k̄ − Re S\overline{K}) ≤ g(r)(2k̄ + 2S_{k_{0}} − g(r))

and hence

k̄ − Re S\overline{K} ≤ g(r) (1 + \frac{k̄ − g(r)/2}{S_{K_{0}}}) ≤ g(r) (1 + \frac{k̄}{S_{K_{0}}} ) ,

because g ≥ 0. Now we use (19) to get

S_{K_{0}} ≥ k_{0} − u = k − k̄ − u ≥ k − \frac{3u}{2} ≥ \frac{1}{2}k.

Substituting this in the previous inequality we get

k̄ − Re S\overline{K} ≤ g(r) (1 + \frac{2k̄}{k} ) .

Using (19) again we get the second inequality.

Recall that the numbers d_{n} are the fourier coefficients of g and that their integral representations are given in (10) and (11), with f replaced by g.

Proposition 7.4. We have the following inequalities.

(7.4.1)  k̄ ≤ d_{0} + \frac{u^{2}}{k} + 6u\sqrt{δ}.
(7.4.2)  2k̄ ∓ k_{n} ≤ 2d_{0} ∓ d_{n} + 2\frac{u^{2}}{k} + 24u\sqrt{δ}.

Proof. We multiply (23) by the positive functions 1 ± cos(2πnr) and integrate from \frac{1}{2} to 1. By definition 7.1 the second case in (23) occurs on a set of measure at most δ of r’s. On this small set we bound 1 ± cos(2πnr) by 2. We easily obtain

(24)  ∫ 1_{\frac{1}{2}}(k̄ − Re S\overline{K}(β′r))(1 ± cos(2πnr))dr ≤ \frac{1}{2}d_{0} ∓ \frac{1}{4}d_{n} + \frac{u^{2}}{2k} + 2δu.

Similarly, multiplying by 1 and integrating, we get

∫ 1_{\frac{1}{2}}(k̄ − Re S\overline{K}(β′r))dr ≤ \frac{1}{2}d_{0} + \frac{u^{2}}{2k} + δu.

We will derive (7.4.1), the derivation of (7.4.2) being similar and simpler. We expand the left hand side of (24).

∫ 1_{\frac{1}{2}}(k̄ − Re S\overline{K}(β′r))(1 ± cos(2πnr))dr

= \frac{1}{2}k̄ − ∫ 1_{\frac{1}{2}} Re S\overline{K}(β′r)dr ∓ ∫ 1_{\frac{1}{2}} Re S\overline{K}(β′r) cos(2πnr)dr =

= \frac{1}{2}k̄ − ∑_{a∈\overline{K}} ∫ 1_{\frac{1}{2}} cos(2π|a|β′r)dr

∓ ∑_{a∈\overline{K}} ∫ 1_{\frac{1}{2}} cos(2π|a|β′r) cos(2πnr)dr.

(25)

We will split the summands in the last sum as

∫ 1_{\frac{1}{2}} cos(2π|a|β′r) cos(2πnr)dr

= \frac{1}{2} ∫ 1_{\frac{1}{2}} cos(2π(|a|β′ + n)r)dr + \frac{1}{2} ∫ 1_{\frac{1}{2}} cos(2π(|a|β′ − n)r)dr.

In case a ∈ K_{n} ∪ K_{−n} we will further split

\frac{1}{2} ∫ 1_{\frac{1}{2}} cos(2π(|a|β′ − n)r)dr = \frac{1}{4} + \frac{1}{2} (∫ 1_{\frac{1}{2}} cos(2π(|a|β′ − n)r)dr − \frac{1}{2}) .

We wish to obtain a lower bound for the left hand side of (24). We take all non-constant terms in the last 2 identities, replace them by the negatives of their absolute values and plug into (25). This gives

∫ 1_{\frac{1}{2}}(k̄ − Re S\overline{K}(β′r))(1 ± cos(2πnr))dr

≥ \frac{1}{2}k̄ ∓ \frac{1}{4}k_{n}

− \frac{1}{2} ∑_{a∈K_{n}∪K_{−n}} |∫ 1_{\frac{1}{2}} cos(2π(|a|β′ − n)r)dr − \frac{1}{2}|

− ∑_{a∈\overline{K}} |∫ 1_{\frac{1}{2}} cos(2π|a|β′r)dr|

− \frac{1}{2} ∑_{a∈\overline{K}−(K_{n}∪K_{−n})} |∫ 1_{\frac{1}{2}} cos(2π(|a|β′ + n)r)dr|

− \frac{1}{2} ∑_{a∈\overline{K}−(K_{n}∪K_{−n})} |∫ 1_{\frac{1}{2}} cos(2π(|a|β′ − n)r)dr| .

(26)

The last four terms are error terms. The last three have a common form, namely, they are sums of terms of the form ∫_{1/2}^{1} cos(2πbr) dr, with b sufficiently large. In fact, b will be |a|β′ or |a|β′ +n for a ∈ \overline{K} in the second and third terms respectively, or |a|β′ − n for a ∈ \overline{K} − K_{±n} in the fourth term. By (20) we have in all cases that |b| > \frac{1}{8}.

Lemma 7.5. Suppose |b| > \frac{1}{8} and that δ′ < 1. Then

|∫ 1_{\frac{1}{2}} cos(2πbr)dr| ≤ \frac{12}{π}| sin(πb(1 − δ′))| + \frac{3}{2}δ′.

Proof. By using the trivial bound | cos(x)| ≤ 1 on [1 − δ′, 1] ∪ \frac{1}{2}[1 − δ′, 1] we get

|∫ 1_{\frac{1}{2}} cos(2πbr)dr| ≤ |∫ 1−δ′_{\frac{1−δ′}{2}} cos(2πbr)dr| + \frac{3}{2}δ′.

Now set b′ = b(1 − δ′). Then

|∫ 1−δ′_{\frac{1−δ′}{2}} cos(2πbr)dr| = |\frac{1}{2πb}(sin(2πb′) − sin(πb′))| =

= |\frac{1}{2πb}(2 sin(πb′) cos(πb′) − sin(πb′))| ≤ \frac{2 + 1}{2π(1/8)}| sin(πb′)| = \frac{12}{π}| sin(πb′)|.

Applying the lemma just proved to the second error term we get

∑_{a∈\overline{K}} |∫ 1_{\frac{1}{2}} cos(2π|a|β′r) dr| ≤ \frac{12}{π} ∑_{a∈\overline{K}} | sin(πaβ′(1 − δ′))| + \frac{3}{2}k̄δ′. (27)

By the definition 7.1 of δ and by proposition 7.2 we know that there exists some δ′ < δ such that

k̄ − Re S\overline{K}(β′(1 − δ′)) ≤ g(1 − δ′) (1 + \frac{u}{k}) . (28)

The left hand side can be expanded as

∑_{a∈\overline{K}}(1 − cos(2πaβ′(1 − δ′))) = 2 ∑_{a∈\overline{K}} sin^{2}(πaβ′(1 − δ′)).

Using (6.7.5) to bound g(1 − δ) we get the estimate

∑_{a∈\overline{K}} sin^{2}(πaβ′(1 − δ′)) ≤ δ′u (1 + 225\frac{u}{k_{0}} ) (1 + \frac{u}{k}) ≤ δu (1 + 300\frac{u}{k}) .

Lemma 7.6. For any positive real numbers x_{1}, …, x_{r} we have

∑_{i=1}^{r} x_{i} ≤ \sqrt{r ∑_{i=1}^{r} x_{i}^{2}}.

Proof. This is just the Cauchy-Schwartz formula for the vectors (1, …, 1) and (x_{1}, x_{2}, …, x_{r}).

Applying this lemma in our situation to the numbers | sin(πaβ′(1 − δ′))| for a ∈ \overline{K} we find

∑_{a∈\overline{K}} | sin(πaβ′(1 − δ′))| ≤ \sqrt{k̄δu(1 + 300u/k)}.

By (27),

∑_{a∈\overline{K}} |∫ 1_{\frac{1}{2}} cos(2πaβ′r) dr| ≤ \frac{12}{π}\sqrt{k̄u (1 + 300u/k) δ} + \frac{3}{2}k̄δ.

Using (19) we see that the right hand side is smaller than

\frac{12}{π}\sqrt{\frac{1}{2}uδ(1 + o(ϵ))} + \frac{3}{4}uδ ≤ 2.9uδ^{\frac{1}{2}} + \frac{3}{4}uδ.

Clearly the same bound holds for the

∑ |∫ 1_{\frac{1}{2}} cos(2π(aβ′ ± n)r) dr|

and therefore the last three terms in (26) can be bounded by 5.8u\sqrt{δ} + (3/2)uδ. We now handle the first error term.

Lemma 7.7. If |b| < \frac{1}{8} and δ′ < 1/2, then

|∫ 1_{\frac{1}{2}} cos(2πbr) dr − \frac{1}{2}| ≤ \frac{1}{2}(1 − cos(2πb(1 − δ′))) + δ′.

Proof. We have

|∫ 1_{\frac{1}{2}} cos(2πbr) dr − \frac{1}{2}| = |∫ 1_{\frac{1}{2}}(1 − cos(2πbr)) dr| .

The estimate of the lemma is obtained by bounding the integrand by 1−cos(2πb(1− δ′)) on [\frac{1}{2}, 1 − δ′] and by 1 on [1 − δ′, 1].

Having the lemma, an argument similar to the one used to bound the last three error terms gives, using (28) and (6.7.5),

∑_{a∈K_{n}∪K_{−n}} |∫ 1_{\frac{1}{2}} cos(2π(|a|β′ − n)r) dr − \frac{1}{2}|

≤ \frac{1}{2}g(1 − δ)(1 + o(ϵ)) + k̄δ ≤ δ(u(1 + o(ϵ)) + k̄)

Altogether, the four error terms are bounded by 5.8u\sqrt{δ} + δ(u(2.5 + o(ϵ)) + k̄). Because δ << 1 this bound is ≤ 5.9u\sqrt{δ}. Now multiply (26) and (24) by 4 and compare them. One gets (7.4.2) up to noticing that we can neglect the δu term by increasing a bit the constant on the u\sqrt{δ} term.

Corollary 7.8. We have

|k_{n} − d_{n}| ≤ 2(d_{0} − k̄) + \frac{2u^{2}}{k} + 24u\sqrt{δ}.

Proof. This is because (7.4.2) implies immediately

∓k_{n} ± d_{n} ≤ 2(d_{0} − k̄) + \frac{2u^{2}}{k} + 24u\sqrt{δ}.

8. Small perturbations in k_{0} and u

In this section we prove bounds on β − β′ and c_{n} − d_{n}. Recall that

β = β(m_{0}, w), β′ = β(k_{0}, u), c_{n} = c_{n}(m_{0}, w), and d_{n} = c_{n}(k_{0}, u).

Therefore, the bounds will depend on m_{0}, k_{0}, w and u and all we need to do is to bound the perturbation of the functions β and c_{n} in terms of the parameters. Since we are assuming that K ∈ 𝕂_{μ_{Kex} (u)} and since E_{K,u} ⊆ [−β′, β′] by (22) where as E_{K_{ex},u} ⊇ [−β, β] by (6.12.3), we find β′ ≥ β. By the definition 7.1 of the parameter δ we have

δ ≤ \frac{β′ − β}{β′} (29)

Proposition 8.1. Suppose we are given m_{0}, k_{0}, w and u that satisfy

|k_{0} − m_{0}| ≤ u, (8.1.1)

w ≤ u ≤ w + (\frac{w}{k} )^{3} w + 2 (\frac{w}{k} )^{3/2} . (8.1.2)

Let β = β(m_{0}, w), β′ = β(k_{0}, u) and assume that β′ ≥ β. Then,

β′ − β ≤ [\frac{1}{2} (\frac{u − w}{w} ) + \frac{3(m_{0} − k_{0})}{2m_{0}} (1 ± \frac{2w}{m_{0}} )] (1 ± 250\frac{u}{k_{0}} ) β′

and

β′ − β ≥ [\frac{1}{2} (\frac{u − w}{w} ) + \frac{3(m_{0} − k_{0})}{2m_{0}} (1 ± \frac{2w}{m_{0}} )] (1 ± 250\frac{u}{m_{0}} ) β.

Here, the sign depends on the sings of m_{0} − k_{0}. The correct signs are those for which the bound is weakest possible.

Proof. We will assume that m_{0} > k_{0}, the other case being similar. By the mean value theorem there exists some β′′ ∈ [β, β′] such that

s′_{k_{0}}(β′′) = \frac{s_{k_{0}}(β) − s_{k_{0}}(β′)}{β − β′}.

Therefore,

β′ − β = \frac{s_{k_{0}}(β) − s_{k_{0}}(β′)}{−s′_{k_{0}}(β′′)}

= \frac{m_{0} − w − s_{m_{0}}(β) + s_{k_{0}}(β) − (k_{0} − u)}{−s′_{k_{0}}(β′′)}

= \frac{u − w + (m_{0} − s_{m_{0}}(β)) − (k_{0} − s_{k_{0}}(β))}{−s′_{k_{0}}(β′′)}.

By using the first expression for s_{k} in (3) we find

(m_{0} − s_{m_{0}}(β)) − (k_{0} − s_{k_{0}}(β)) = ( ∑_{n=(1−m_{0})/2}^{(m_{0}−1)/2} − ∑_{n=(1−k_{0})/2}^{(k_{0}−1)/2}) (1 − cos(2πnβ))

≤ (m_{0} − k_{0})(1 − cos(πm_{0}β)) ≤ \frac{1}{2}(m_{0} − k_{0})(πm_{0}β)^{2}.

By proposition 3.4 we find

(πm_{0}β)^{2} = 6 (\frac{w}{m_{0}} ) (1 + \frac{3w}{20m_{0}} + O(1)(\frac{w}{m_{0}} )^{2})^{2} ≤ 6 (\frac{w}{m_{0}} ) (1 + \frac{2w}{m_{0}} ) ,

which implies

(m_{0} − s_{m_{0}}(β)) − (k_{0} − s_{k_{0}}(β)) ≤ (m_{0} − k_{0})\frac{3w}{m_{0}} (1 + \frac{2w}{m_{0}} ) .

Using (6.7.4) one gets

−s′_{k_{0}}(β′′) = −\frac{f′_{k_{0},u} (\frac{β′′}{β′} )}{β′} ≥ \frac{2u}{β′} (1 − 225\frac{u}{k_{0}} ) \frac{β′′}{β′} ≥ \frac{2w}{β′} (1 − 225\frac{u}{k_{0}} ) \frac{β}{β′}

and therefore

\frac{β′ − β}{β′} ≤ [\frac{1}{2} (\frac{u − w}{w} ) + \frac{3(m_{0} − k_{0})}{2m_{0}} (1 + \frac{2w}{m_{0}} )]

× [(1 − 225\frac{w}{k_{0}} ) (1 − \frac{β′ − β}{β′} )]^{−1} .

To get the first inequality we iterate some trivial estimate on β − β′. Start with β − β′ ≤ β′/2. Then we can derive an inequality of the form \frac{β′−β}{β} ≤ \frac{4u}{m_{0}} (see the derivation of (8.2.2) below). This in turn implies

[(1 − 225\frac{w}{k_{0}} ) (1 − \frac{β′ − β}{β′} )]^{−1} ≤ (1 − 225\frac{w}{k_{0}} − \frac{4u}{m_{0}} )^{−1} ≤ 1 + 250\frac{u}{k_{0}} .

This gives the first inequality. The second is similar.

Corollary 8.2. We have the following inequalities.

k̄ ≥ m̄ − \frac{w^{3}}{k^{2}} − (\frac{w}{k} )^{1/2} . (8.2.1)

\frac{β′ − β}{β} ≤ \frac{2u}{m_{0}} . (8.2.2)

δ ≤ (\frac{w}{k} )^{3} + \frac{2}{k} (\frac{w}{k} )^{1/2} + \frac{3|k̄ − m̄|}{2k} (1 + 300\frac{u}{k}) . (8.2.3)

Proof. For the first inequality we only need to check the case k̄ < m̄. In this case m_{0} < k_{0}. From proposition 8.1 and the assumption β′ ≥ β we find

0 ≤ \frac{1}{2} (\frac{u − w}{w} ) + \frac{3(k̄ − m̄)}{2m_{0}} (1 − \frac{2w}{m_{0}} ) .

Therefore,

m̄ − k̄ ≤ \frac{1}{2} (\frac{w − u}{w}) (\frac{3}{2m_{0}} (1 − o(ϵ)))^{−1}

= \frac{1}{3}m_{0} (\frac{w − u}{w}) (1 + o(ϵ))

≤ \frac{1}{3}m_{0} (\frac{w}{k} )^{3} (1 + o(ϵ)) + \frac{2}{3} \frac{m_{0}}{w} (\frac{w}{k} )^{3/2} (1 + o(ϵ)) by (8.1.2)

≤ \frac{w^{3}}{k^{2}} + (\frac{w}{k} )^{1/2} .

LARGE TRIGONOMETRIC SUMS 31

Next, by proposition 8.1 and by (8.1.2) and (8.1.1) we get

\frac{β′ − β}{β} ≤ [\frac{1}{2} (\frac{w}{k} )^{3} + 2w^{−1} (\frac{w}{k} )^{3/2} + \frac{3u}{2m_{0}} (1 + o(ϵ))] (1 + o(ϵ)) ≤ \frac{2u}{m_{0}} ,

proving (8.2.2). The third inequality follows easily from the proposition and (29).

Lemma 8.3. We have the following inequalities.

(8.3.1)  |d_{n} − c_{n}| ≤ \frac{u^{2}}{m_{0}(πn)^{2}} .
(8.3.2)  |d_{0} − c_{0}| ≤ \frac{u^{2}}{3m_{0}} .

Proof. We follow the proofs of lemma 6.6 and proposition 6.8. Let

sin(k_{0}z)/ sin(z) = ∑_{j=0}^{∞} b′_{j}z^{j}

be a Taylor expansion around 0, and let

g(r) = u + ∑_{j=1}^{∞} a′_{j}r^{2j}

be the expansion for g converging on [1/2, 1]. We have a′_{j} = b′_{2j}(πβ′)^{2j}. The identity

\frac{sin(m_{0}z)}{sin(z)} − \frac{sin(k_{0}z)}{sin(z)} = 2 sin (\frac{m_{0} − k_{0}}{2} z) cos (\frac{m_{0} + k_{0}}{2} z) / sin(z)

easily implies, together with lemma 6.5, that on a circle C_{m_{0}} of radius 1/m_{0} we have

|\frac{sin(m_{0}z)}{sin(z)} − \frac{sin(k_{0}z)}{sin(z)}| ≤ 2|m_{0} − k_{0}|.

Therefore, using the Cauchy integral formula, we have

|b_{j} − b′_{j}| ≤ 2m_{0}^{j}|m_{0} − k_{0}|.

Recall how the constant c was defined in lemma 6.6 and used in its proof. We find

|a_{j} − a′_{j}| = |b_{2j}(πβ)^{2j} − b′_{2j}(πβ′)^{2j}|

≤ |b_{2j} − b′_{2j}|(πβ)^{2j} + |b′_{2j}|π^{2j}|β′^{2j} − β^{2j}|

≤ 2c^{j}|m_{0} − k_{0}| + 2m_{0}c^{j} (\frac{β′^{2j} − β^{2j}}{β^{2j}} )

= 2c^{j}|m_{0} − k_{0}| + 2m_{0}c^{j} ((1 + \frac{β′ − β}{β} )^{2j} − 1) .

By (8.1.1) and (8.2.2) we get

|a_{j} − a′_{j}| ≤ 2c^{j}u + 2m_{0}c^{j} (u + m_{0}((1 + 2u/m_{0})^{2j} − 1))
≤ 2c^{j} (u + m_{0}((1 + 2u/m_{0})^{2j} − 1)) .

32 AMNON BESSER

When j = 2 we use the bound

(1 + 2\frac{u}{m_{0}} )^{4} − 1 ≤ 9\frac{u}{m_{0}}

to get

|a_{2} − a′_{2}| ≤ 20c^{2}u ≤ 20 · 6^{2}(1 + o(ϵ)) (\frac{u}{m_{0}} )^{2} u ≤ 800 (\frac{u}{m_{0}} )^{2} u.

When j > 2 we use the bound

(1 + 2\frac{u}{m_{0}} )^{2j} − 1 < (1 + 2\frac{u}{m_{0}} )^{2j} = (1 + o(ϵ))^{2j}.

This gives

|a_{j} − a′_{j}| ≤ 2 (c(1 + o(ϵ))^{2})^{j} (u + m_{0}) ≤ 2 · 7^{j} (\frac{u}{m_{0}} )^{j−1} u.

Since f(1) = g(1) = 0 we see that

|a_{1} − a′_{1}| ≤ |w − u| + ∑_{j=2}^{∞} |a_{j} − a′_{j}|

≤ (\frac{w}{k} )^{3} w + 800 (\frac{u}{m_{0}} )^{2} u + 2 · 7^{3} (\frac{u}{m_{0}} )^{2} u

+ lower order terms ≤ 1500 (\frac{u}{m_{0}} )^{2} u.

Then, imitating the proof of proposition 6.8, we find

|c_{n} − d_{n}| ≤ \frac{8}{(2πn)^{2}} \frac{d}{dr} (∑_{j=0}^{∞} |a_{j} − a′_{j}|r^{2j}) |_{r=1}

≤ \frac{2}{(πn)^{2}} (2 · |a_{1} − a′_{1}| + 4 · |a_{2} − a′_{2}| + 6 · |a_{3} − a′_{3}| + l.o.t.)

≤ \frac{2}{(πn)^{2}} (\frac{u}{m_{0}} )^{2} u (2 · 1500 + 4 · 800 + 6 · 2 · 7^{3} + l.o.t.)

≤ 21000\frac{1}{(πn)^{2}} (\frac{u}{m_{0}} )^{2} u ≤ \frac{1}{(πn)^{2}} (\frac{u}{m_{0}} ) u.

The second estimate is similar.

9. The main theorems

In the last two sections we gathered many conditional estimates. It is now easy to make these absolute. Lemma 9.1. We have

|k̄ − m̄| ≤ 2\frac{u^{2}}{k} + 6u\sqrt{δ} + 5.2\sqrt{u}.

Proof. If k̄ < m̄, then (8.2.1) implies that |k̄ − m̄| ≤ w^{3}/k^{2} + (w/k)^{1/2}, which is certainly within the bound. Otherwise we have

|k̄ − m̄| = k̄ − m̄ = (k̄ − d_{0}) + (d_{0} − c_{0}) + (c_{0} − m̄),

which, by (6.12.4),(7.4.1) and (8.3.2), is

≤ (\frac{u^{2}}{k} + 6u\sqrt{δ}) + (\frac{u^{2}}{3m_{0}} ) + (5.2\sqrt{u})

≤ 2\frac{u^{2}}{k} + 6u\sqrt{δ} + 5.2\sqrt{u}.

Proposition 9.2. We have the inequality

\sqrt{δ} ≤ 10 (\frac{u}{k}) + \sqrt{8} (\frac{u}{k})^{1/4} k^{−1/4}.

Proof. The last lemma, together with (8.2.3), gives the inequality

δ ≤ (\frac{w}{k} )^{3} + \frac{2}{k} (\frac{w}{k} )^{1/2} + \frac{3}{2k} (2\frac{u^{2}}{k} + 6u\sqrt{δ} + 5.2\sqrt{u}) (1 + o(ϵ))

≤ 4 (\frac{u}{k})^{2} + 9 (\frac{u}{k}) (1 + o(ϵ))\sqrt{δ} + \frac{8\sqrt{u}}{k}.

Here, notice that we were able to swallow the first two terms on the first line, the (w/k)^{3} term in the (u/k)^{2} term and the (2/k)(w/k)^{1/2} term by the \sqrt{u}/k term. We treat the last inequality as a quadratic inequality in x = \sqrt{δ}, which reads

x^{2} ≤ 4 (\frac{u}{k})^{2} + 9 (\frac{u}{k}) (1 + o(ϵ))x + \frac{8\sqrt{u}}{k}.

The variable x should lie between the roots of the corresponding equation,

x^{2} − 9 (\frac{u}{k}) (1 + o(ϵ))x − (4 (\frac{u}{k})^{2} + \frac{8\sqrt{u}}{k}) = 0.

In particular, it is smaller than the bigger root. This gives

\sqrt{δ} ≤ \frac{1}{2} (\frac{9u}{k}(1 + o(ϵ)) + \sqrt{(81 + 12) (\frac{u}{k})^{2} (1 + o(ϵ)) + \frac{32\sqrt{u}}{k}}) .

Using the fact that for any two positive reals a and b we have \sqrt{a + b} ≤ \sqrt{a} + \sqrt{b}, we easily get the required bound.

Corollary 9.3. We have δ < 200 (\frac{u}{k})^{2} + \frac{16\sqrt{u}}{k}.

Proof. This just uses the inequality (a + b)^{2} ≤ 2(a^{2} + b^{2}).

We now begin to state the main theorems. Recall our assumptions from the beginning of section 7: We have u > 1, k > 30000u and k and u satisfy assumption 5.4. We have a set K ∈ 𝕂_{μ_{Kex} (u)}, written as K = K_{0} ∪ \overline{K}. Recall also that K_{0} is contained inside an arithmetic progression. Let q be the difference of this sequence. By translation we can normalise things so that elements of K_{0} are divisible by q. Recall that we have a compression procedure for K_{0} to an arithmetic progression with at most one gap. Assume also that this progression is symmetric around 0 (as best possible). This fixes K up to shift. With these assumption we associated certain parameters k_{n} to K, counting roughly the number of elements near ±n/β(k_{0}, u). When q ≠ 1 we count only those elements which are divisible by q. We have analogous parameters m_{n} for our “test set” K_{ex}. The theorem will show that these parameters are pretty close to each other.

Theorem 9.4. We have the following inequalities.

m_{0} + \frac{u^{3}}{k^{2}} + \frac{1}{k} (\frac{u}{k})^{1/2} ≥ k_{0} ≥ m_{0} − 62\frac{u^{2}}{k} − 6\sqrt{u} − 20 (\frac{u}{k})^{1/4} k^{−1/4}u. (9.4.1)

|k_{n} − m_{n}| ≤ 250\frac{u^{2}}{k} + 11\sqrt{u} + 70 (\frac{u}{k})^{1/4} k^{−1/4}u + 4. (9.4.2)

|\{a ∈ K : |a|β ≥ t or q ∤ a\}| ≤ \frac{4u}{t} + tu (400 (\frac{u}{k})^{2} + \frac{32\sqrt{u}}{k}) , (9.4.3)

for t > 0.

Proof. As discussed at the beginning of section 7, we may assume that K_{0} is an arithmetic progression with at most one gap. Continue first to assume that it is a progression, has difference 1 and is symmetric around 0. We now write out the results we have so far.

The left inequality in (9.4.1) is just (8.2.1). The right inequality follows since

|k̄ − m̄| ≤ 2\frac{u^{2}}{k} + 6u\sqrt{δ} + 5.2\sqrt{u} by lemma 9.1

≤ 2\frac{u^{2}}{k} + 5.2\sqrt{u} + 6u (10 (\frac{u}{k}) + \sqrt{8} (\frac{u}{k})^{1/4} k^{−1/4}) by proposition 9.2

≤ 62\frac{u^{2}}{k} + 6\sqrt{u} + 20 (\frac{u}{k})^{1/4} k^{−1/4}u.

We next establish

d_{0} − k̄ ≤ 5.5\sqrt{u} + \frac{u^{2}}{2k} . (30)

Indeed

k̄ ≥ m̄ − \frac{u^{3}}{k^{2}} − (\frac{u}{k})^{1/2} ≥ c_{0} − 5.2\sqrt{u} − \frac{u^{3}}{k^{2}} − (\frac{u}{k})^{1/2}

≥ d_{0} − \frac{u^{2}}{3m_{0}} − 5.2\sqrt{u} − \frac{u^{3}}{k^{2}} − (\frac{u}{k})^{1/2} ≥ d_{0} − \frac{u^{2}}{2k} − 5.5\sqrt{u}

by (6.12.4), (8.2.1) and (8.3.2). Here again, like in the proof of proposition 9.2, we are able to swallow the terms (u/k)^{1/2} and u^{3}/k^{2}. It now follows that

|k_{n} − d_{n}| ≤ 2(d_{0} − k̄) + \frac{2u^{2}}{k} + 24u\sqrt{δ} by corollary 7.8

≤ 11\sqrt{u} + \frac{u^{2}}{k} + \frac{2u^{2}}{k} + 24u\sqrt{δ} by (30)

≤ 11\sqrt{u} + \frac{3u^{2}}{k} + 24u (10 (\frac{u}{k}) + \sqrt{8} (\frac{u}{k})^{1/4} k^{−1/4}) by proposition 9.2

≤ 243\frac{u^{2}}{k} + 11\sqrt{u} + 70 (\frac{u}{k})^{1/4} k^{−1/4}u.

From (8.3.2) we get

|d_{n} − c_{n}| ≤ \frac{u^{2}}{m_{0}π^{2}} ≤ \frac{u^{2}}{9k} .

By the definition of the m_{n} in (6.1) (taking into account the possible modifications at the proof of (6.12)), we see that |c_{n} − m_{n}| ≤ 4. This gives (9.4.2).

To get (9.4.3) we integrate the inequality of proposition 7.2 on the interval [1 − \frac{1}{t}, 1]. Recalling that there is a subset of size δ on which the inequality fails to hold, and on which bound k̄ − Re S\overline{K} trivially by 2k̄ ≤ u, we get

∫_{1− \frac{1}{t}}^{1} (k̄ − Re S\overline{K}(βr)) ≤ ∫_{1− \frac{1}{t}}^{1} g(r) (1 + \frac{u}{k}) dr + uδ. (31)

The left hand side is

∫_{1− \frac{1}{t}}^{1} (k̄ − Re S\overline{K}(βr)) dr = ∑_{a∈\overline{K}} ∫_{1− \frac{1}{t}}^{1} (1 − cos(2πaβr)) dr.

One finds that if b ≥ t, then

∫_{1− \frac{1}{t}}^{1} (1 − cos(2πbr)) dr = \frac{1}{t} − \frac{1}{2πb} (sin (2πb (1 − \frac{1}{t})) − sin(2πb))

≥ \frac{1}{t} − \frac{2}{2πb} ≥ \frac{1}{2t}.

It follows that the left hand side of (31) is greater than

\frac{1}{2t}|\{a ∈ K : |a|β ≥ t\}|.

Using (6.7.5) the right hand side of (31) is smaller than

(1 + 225\frac{u}{k_{0}} ) u ∫0^{\frac{1}{t}} 2r dr + uδ ≤ \frac{2u}{t^{2}} + uδ.

Therefore,

\frac{1}{2t}|\{a ∈ K : |a|β ≥ t\}| ≤ \frac{2u}{t^{2}} + \frac{1}{2}uδ.

Thus,

|\{a ∈ K : |a|β ≥ t\}| ≤ \frac{4u}{t} + 2uδ,

which gives the result after substituting the estimate for δ given in corollary 9.3.

To see that the everything continues to hold for the case q > 1, we consider the structure of the proof and see what modifications one must make. Most of the time we have been integrating certain identities on certain intervals. Whenever there is an integral on some interval I involved for the case q = 1, take the corresponding integral on the set ⟨q⟩^{−1}(I) and make the obvious adaptations. It is easy to see that all terms in the integration which involve elements that are not congruent to 0 mod q vanish. There was one place, in deriving (28), where we used the value of the sum at a certain point. But there note that elements congruent to 0 mod q behave the same on all intervals and the claim made there about the existence of δ′ is certainly true for at least one interval. With these remarks the proof goes through unchanged.

Now comes a second “compression argument”. It is based on the following lemma.

Lemma 9.5. Let x_{1}, x_{2}, y_{1}, y_{2} and z be vectors in an Euclidean space with scalar product “·” and norm | |, such that |x_{1}| = |x_{2}| = |y_{1}| = |y_{2}| = 1. Let x = x_{1} + x_{2}, y = y_{1} + y_{2}. Put x_{1} · x_{2} = cos θ_{1}, y_{1} · y_{2} = cos θ_{2}, x · z = (cos θ)|z|. If

cos θ_{1} − cos θ_{2} > 4(1 − cos θ),

then

|x + z| > |y + z|.

Proof.

x · x − y · y = 2 + 2x_{1} · x_{2} − 2 − 2y_{1} · y_{2} = 2(cos θ_{1} − cos θ_{2}) > 8(1 − cos θ).

Since |x| + |y| < 4,

|x| − |y| > 2(1 − cos θ) ≥ (1 − cos θ)|x|,

and therefore |x| cos θ > |y|. Thus

|z + x|^{2} − |z + y|^{2} ≥ |x|^{2} − |y|^{2} + 2|z|(|x| cos θ − |y|) > 0.

Corollary 9.6. Suppose K is as before, with K_{0} and arithmetic progression symmetric around 0. Suppose a, b ∈ K, q|a and q|b, and a and b satisfy the inequalities

β^{−1} − 2k ≥ |a − b|/q ≥ 2k.

Then, if K′ is the set obtained from K by replacing a and b with two elements c and d on the sides of K_{0}, i.e., c ≈ k_{0}/2 and d = −c, we get μ_{K′}(u) ≥ μ_{K}(u).

Proof. Assume again that q = 1 for simplicity. Observe first that if α = β_{k_{0},u}r, with r < \frac{1}{\sqrt{6}}, then

|S_{K_{0}}(α)| − k̄ ≈ k_{0} − ur^{2} − k̄ ≈ k − \frac{5}{6}u − ur^{2} > k − \frac{5}{6}u − u\frac{1}{\sqrt{6}}^{2} = k − u,

because k̄ ≈ \frac{5}{12}u. This implies that such an α belongs to both E_{K,u} and E_{K′,u}.

Now assume α > \frac{1}{10}β_{k_{0},u}. Set x_{1} = e^{2πicα}, x_{2} = e^{2πidα}, y_{1} = e^{2πiaα}, y_{2} = e^{2πibα} and z = S_{K}(α) − (y_{1} + y_{2}), so that z + y, z + x are the values of S_{K}(α) and S_{K′}(α) respectively. In our case the conditions of the lemma hold. To see this, notice that we have

4πkα ≤ 2π(a − b)α ≤ 2π(a − b)β ≤ 2π − 4πkβ ≤ 2π − 4πkα.

It follows that cos(θ_{2}) = cos(2π(a − b)α) ≤ cos(4πkα). Therefore,

cos θ_{1} − cos θ_{2} ≥ cos(θ_{1}) − cos(4πkα) ≈ cos(2πkα) − cos(4πkα)

≈ (4παk)^{2} − (2παk)^{2} = 3(2παk)^{2} ≥ 3 (2π \frac{1}{10}β_{k_{0},u}k)^{2} ≥ \frac{u}{2k} .

On the other hand, since x is on the real line, θ is almost the angle between S_{K} and the real line so

| sin θ| = |\frac{Im S_{K}}{Re S_{K}} | < \frac{\frac{1}{2}u}{k − \frac{3}{2}u} < \frac{u}{k}

and therefore 1 − cos θ ≤ sin^{2} θ ≤ (u/k)^{2}. Since the lemma applies we see that α ∈ E_{K,u} implies α ∈ E_{K′,u}, hence the result.

The following two theorems are immediate consequences.

Theorem 9.7. Suppose K ∈ 𝕂_{μ_{Kex} (u)}. Then around each of ±n/β, n ≠ 0, there exists an interval of length 2kq such that the total number of elements of ∪_{n=1}^{∞}(K_{n} ∪ K_{−n}) not in any of the intervals is ≤ 63\frac{u^{2}}{k} + 7\sqrt{u} + 20 (\frac{u}{k})^{1/4} k^{−1/4}u.

Proof. Indeed, corollary 9.6 implies that any two elements in any K_{n} that are of distance ≥ 2kq apart can be “pushed” into K_{0}, increasing μ_{K}(u) and in particular keeping the set in 𝕂_{μ_{Kex} (u)}. But by (9.4.1) the number of elements one can move

into K_{0} keeping K in 𝕂_{μ_{Kex} (u)} is ≤ 63\frac{u^{2}}{k} + 7\sqrt{u} + 20 (\frac{u}{k})^{1/4} k^{−1/4}u (again we have swallowed some terms).

Theorem 9.8. The following is a G_{μ_{Kex} (u)} sub-collection of 𝕂_{μ_{Kex} (u)}. It consists of all sets in which K_{0} is an arithmetic progression with at most one gap, and where each of the sets K_{n}, for n ≠ 0, is contained in an interval of length 2kq.

Proof. Immediate from corollary 9.6.

We end with an improved bound on μ_{max}.

Theorem 9.9. We have the following inequalities

μ_{max}(k, u) ≥ \frac{2\sqrt{6}}{π} \frac{1}{k} (\frac{u}{k})^{1/2} (1 + (\frac{3}{20} + \frac{5}{8}) \frac{u}{k} − 300 (\frac{u}{k})^{2} − \frac{8\sqrt{u}}{k})
μ_{max}(k, u) ≤ \frac{2\sqrt{6}}{π} \frac{1}{k} (\frac{u}{k})^{1/2} (1 + (\frac{3}{20} + \frac{5}{8}) \frac{u}{k} + 400 (\frac{u}{k})^{2} + 30 (\frac{u}{k})^{5/4} k^{−1/4}) .

Proof. We clearly have 2β_{m_{0},w} ≤ μ_{max}(k, u) ≤ 2β_{k_{0},u}, so the theorem is about estimating the terms on both sides. We show the second inequality only. By (22) and proposition 8.1,

μ_{max}(k, u) ≤ 2β_{k_{0},u} ≤ 2β_{k,u} [1 + \frac{3(k − k_{0})}{2k} (1 + \frac{2u}{k}) (1 + 250\frac{u}{k_{0}} )] .

By proposition 3.4,

β_{k,u} ≤ \frac{\sqrt{6}}{π} \frac{1}{k} (\frac{u}{k})^{1/2} (1 + \frac{3u}{20k} + (\frac{u}{k})^{2}) .

By (7.4.1),

k − k_{0} = k̄ ≤ d_{0} + \frac{u^{2}}{k} + 6u\sqrt{δ}.

It follows from (6.8.1) that

d_{0} ≤ \frac{5}{12}u + 75\frac{u^{2}}{k_{0}} ≤ \frac{5}{12}u + 79\frac{u^{2}}{k} .

Hence, using proposition 9.2 we find

k − k_{0} ≤ \frac{5}{12}u + 80\frac{u^{2}}{k} + 6u (10 (\frac{u}{k}) + \sqrt{8} (\frac{u}{k})^{1/4} k^{−1/4})

≤ \frac{5}{12}u + 140\frac{u^{2}}{k} + 17u (\frac{u}{k})^{1/4} k^{−1/4}.

It follows that

(1 + \frac{3u}{20k} + (\frac{u}{k})^{2}) [1 + \frac{3}{2k} (k − k_{0}) (1 + \frac{2u}{k}) (1 + 250\frac{u}{k_{0}} )]

≤ 1 + (\frac{3}{20} + \frac{5}{8}) \frac{u}{k} + 400 (\frac{u}{k})^{2} + 30 (\frac{u}{k})^{5/4} k^{−1/4}.

The upper bound is now clear.

References

[1] Freiman, G.A., On the measure of large trigonometric sums, In Sixth international conference on collective phenomena: Reports from the Moscow Refusnik seminar. Annals of the New York academy of sciences. New York, New York, 1985.

[2] Freiman, G.A.; Judin, A.A., The general principles of additive number theory, in [6], pp. 135-147.

[3] Freiman, G.A., Foundations of a structural theory of set addition. In Translation of Mathematical Monographs, vol. 37, American Mathematical Society, Providence, R.I., 1973.

[4] Judin, A.A., The measure of the large values of the modulus of a trigonometric sum, in [6], pp. 163-171.

[5] Moskvin, D.A.; Freiman, G.A. and Judin, A.A., Inverse problems of additive number theory and local limit theorems for lattice random variables, in [6], pp. 163-171.

[6] Freiman, G.A. edt., Number-theoretic studies in the Markov spectrum and in the structural theory of set addition (Russian), Kalinin Gos. University., Moscow, 1973, 191 pp.

[7] Raikov, D., On the addition of point-sets in the sense of Schnirelmann, Rec. Math. [Mat. Sbornik] N.S. 5(47), 1939, pp. 425–440.

Department of Mathematical Sciences, University of Durham, Science Laboratories, South Road, Durham DH1 3LE, England

   E-mail address: Amnon.Besser@durham.ac.uk
   URL: http://fourier.dur.ac.uk:8000/~dma1ab