Last time I have mentioned the idea of the proof (of theorem 2). Now I continue and give a full detail here.
Lemma 7 The Bohr neighbourhood contains an arithmetic progression, named , of length at least .
Proof. By Lemma 6 (see last post), every element in is in the -linear span of a set of size at most . Hence we have (for, pick LHS, then for all , and so by triangle inequality, together with the fact that elements in can be written in the form , we have .) Note that by Lemma 5, LHS contains an AP of length at least . The result follows.
Lemma 8 For at least values of we have .
Proof. Suppose not. Then more than values of we have the reversed inequality. So
Now let . By Lemma 8, . Since the size of is large, it cannot have huge Fourier coefficient for .
(In fact, for , , where is the complement of and the first equality is because of the fact whenever .)
We now choose , using probabilistic method, with certain size so that the Fourier coefficient of is small.
Lemma 9 Let . Also assume . Then there exists with size such that .
Proof. Choose a set by letting each be in with probability , these choices being independent.
We first compute the expectations and variances of the Fourier coefficient of . Recall the notation .
Now consider the random variable . By above computations we have , . Also it is easy to see that . Therefore, we can apply Lemma 4 with these random variables .
Case 1: . Then
Case 2: . Then by Lemma 4.
Therefore, if , , and so there is a positive probability such that and happens. By adding or deleting suitable number of elements (which is at most ) from we will get (Since the number of changed elements is at most , and so ).
With the same proof we get the following lemma:
Lemma 10 Let . Also assume . Then there exists with size such that for .
Remark: The above two lemmas actually mean that for any set , there is always a subset such that 1. ; 2. has Fourier coefficients close to .
Lemma 11 Let . Assume . Then and for .
(Little remark: I avoid the notion “multiset” which is used in original paper. Although the concept of multiset is easy to understand but somehow there is ambiguity, and so I prefer saying that is disjoint union of two sets instead of saying is a multiset.)
Proof. Note that
The result follows.
Write . Let be any set obtained by replacing by , where . (Recall: is an AP in the Bohr neighbourhood of )
Lemma 12 Suppose that . Let . Assume the union is disjoint. Then .
Proof. If , as we changed the elements in , . Hence
If , recall , then
We are almost done (finally!). Recall is the set such that is minimal subject to the constraint . Therefore if , could not exist! In another words, no such choice of such that one could construct .
Lemma 13 There exists some such that is contained in , except for at most elements, which could lie in .
Proof. Suppose not. Then for all , more than elements in lie in . Choose such that . Choose such that . Continue this way, choose such that . This gives us a , contradiction.
Let be such that Lemma 13 holds. Recall that . Therefore . Therefore, contains at least and minus at most points.
If one choose , will contain a portion of . Suppose further that the parameters have also been chosen such that . Then contains more than of must contain an AP of length at least .
Remark: If we choose such that , then it is even impossible to define . But in this case will contain an AP of length at least .
And hence above leads to
Proposition 14 Suppose that , , and satisfies the condition in Lemma 9, 10. Then contains an AP of length at least .
By taking , , with some painful calculations we can get theorem 2. (Actually I didn’t check this, it may be wrong. But I think this part is less important compared to the whole argument.)