This post is based mainly on the paper “Arithmetic progression in sumsets” by Ben Green, which talks about the length of arithmetic progressions of some special kind of subsets of , where is a sufficiently big odd prime. I will follow Green’s paper closely and will try to give a clearer proof of one of the main theorem in the paper, which I think the idea is quite interesting. Only very few knowledge about Discrete Fourier Transform is required.

Theorem 1Let , with cardinalities and respectively. Then the set contains an arithmetic progression of length at least .

(This result in fact has already been improved by Croot, Laba and Sisask last year.)

We first fix some notations. Let be a big odd prime and (no confusion will be caused since the is always fixed). The Fourier is defined by . If , we use to denote the characteristic function of .

* Definition* Let . Their convolution is defined by .

**Remark**: actually means the number of such that and , i.e. number of the solutions to the equation . It has the same support as of .

* Definition* Let and . We say that is a -hereditarily non-uniform (short notation: -HNU) if for any subset of , one has

.

One can consider such kind of set as some highly non-uniformly distributed in such that its subsets have large Fourier coefficient.

Theorem 1 will then follows from theorem 2 and proposition 3 below:

Theorem 2Suppose that , and that is a -HNU. Then , the complement of,contains an arithmetic progression of length at least .

Proposition 3Let such that and . Let . Then is -HNU.

*Proof of Proposition 3. *Let . Then (Recall has the support as of ). By Parseval’s Identity, we have . Then . Observe . Thus,

.

Rearranging we get , and hence is -HNU.

To prove theorem 2, we need three lemmas:

Lemma 4 (Large deviation inequality of Bernstein)Let be independent complex-valued random variables with and . Write and suppose that for all . Suppose that . Then .

* Defintion* Define by , where is the remainder of mod . Let and . Write , called the Bohr neighbourhood of with radius .

Lemma 5Suppose that . Then contains an AP of length at least .

Lemma 6 (Chang’s theorem)Let such that and . Then there is a set with such that , where is an absolute constant independent of etc. (A known and correct value for is ).

Proofs of above lemmas are omitted. Lemma 5 in fact is just a consequence of pigeonhole principle. Lemma 6 talks about the structure of the set with high Fourier coefficients (yet I could not quite figure out the meaning of -span of .)

The idea to prove theorem 2 is as follow: we first let such that is minimized among all subsets of with cardinality . Then make use of lemma 5 and lemma 6 to pick an AP, which we will call it later. Using this , we can define a set with large cardinality, and hence with small Fourier coefficients, and from which one can define a subset of with small cardinality and small Fourier coefficients (using lemma 4). Since has a small Fourier coefficients, if we remove elements from (with suitable choice), and put all the elements of into , the Fourier coefficients won’t change too much. If we further modify the elements in , we can then form a new set , with same cardinality as , yet has smaller Fourier coefficients than , which will contradict the minimality of . The problem comes from the modification of the elements in , and surprisingly this will lead to the conclusion that contains a long AP.

As it seems that this post is going to be too long, the technical details will be continued in the next part.