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 1 Let , 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 2 Suppose that , and that is a -HNU. Then , the complement of , contains an arithmetic progression of length at least .
Proposition 3 Let 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 5 Suppose 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.