Arithmetic progression in some subsets of $\mathbb{Z}_N$ (Part 1)

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 $\mathbb{Z}_N$, where $N$ 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 $C, D \subset \mathbb{Z}_N$, with cardinalities $\gamma N$ and $\delta N$ respectively. Then the set $C+D:=\{ x\in\mathbb{Z}_N: x=c+d \text{ for some } c\in C, d\in D\}$ contains an arithmetic progression of length at least $e^{\frac{\sqrt{\gamma\delta\log{N}}}{32}}$.

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

We first fix some notations. Let $N$ be a big odd prime and $\omega = e^{\frac{2\pi i}{N}}$ (no confusion will be caused since the $N$ is always fixed). The Fourier $\hat{f}(r)$ is defined by $\displaystyle\Sigma_{x\in\mathbb{Z}_N} f(x)\omega^{rx}$. If $A\subset\mathbb{Z}_N$, we use $A(x)$ to denote the characteristic function of $A$.

Definition Let $A,B\subset\mathbb{Z}_N$. Their convolution $A*B$ is defined by $(A*B)(x) = \Sigma_y A(y)B(x-y)$.

Remark: $(A*B)(x)$ actually means the number of $y$ such that $y\in A$ and $x-y \in B$, i.e. number of the solutions to the equation $a+b=x$. It has the same support as of $(A+B)(x)$.

Definition Let $A\subset \mathbb{Z}_N$ and $\alpha \in (0,1)$. We say that $A$ is a $\alpha$-hereditarily non-uniform (short notation: $\alpha$-HNU) if for any subset $S$ of $A$, one has

$\displaystyle \sup_{r\neq 0}|\hat{S}(r)|\geq\alpha|S|$.

One can consider such kind of set as some highly non-uniformly distributed in $\mathbb{Z}_N$ such that its subsets have large Fourier coefficient.

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

Theorem 2 Suppose that $1>\alpha\geq\frac{4000\log{\log{N}}}{\sqrt{\log{N}}}$, and that $A$ is a $\alpha$-HNU. Then $A^c$, the complement of $A$, contains an arithmetic progression of length at least $e^{\frac{\alpha \sqrt{\log{N}}}{32}}$.

Proposition 3 Let $C, D\subset \mathbb{Z}_N$ such that $|C|=\gamma N$ and $|D|=\delta N$. Let $A=(C+D)^c$. Then $A$ is $\sqrt{\gamma\delta}$-HNU.

Proof of Proposition 3. Let $S\subset A$. Then $\Sigma_x S(x)(C*D)(x) = 0$ (Recall $(C*D)(x)$ has the support as of $(C+D)(x)$). By Parseval’s Identity, we have $\Sigma_r \hat{S}(r)\overline{\hat{C}(r)\hat{D}(r)} = 0$. Then $-\hat{S}(0)\overline{\hat{C}(0)\hat{D}(0)}=\Sigma_{r\neq0} \hat{S}(r)\overline{\hat{C}(r)\hat{D}(r)}$. Observe $\hat{S}(0)\overline{\hat{C}(0)\hat{D}(0)}=|S||C||D|$. Thus,

$\displaystyle \begin{array}{rcl} |S||C||D|&\leq& \Sigma_{r\neq0} |\hat{S}(r)||\hat{C}(r)||\hat{D}(r)| \text{\qquad (Triangle inequality)}\\ &\leq& \sup_{r\neq0}|\hat{S}(r)| \Sigma_{r}|\hat{C}(r)||\hat{D}(r)| \\ &\leq& \sup_{r\neq0}|\hat{S}(r)| (\Sigma_{r}|\hat{C}(r)|^2)^\frac{1}{2}(\Sigma_{r}|\hat{D}(r)|^2)^\frac{1}{2} \text{\qquad (Cauchy Schwarz inequality)}\\ &=& \sup_{r\neq0}|\hat{S}(r)| (N|C|)^\frac{1}{2}(N|D|)^\frac{1}{2} \text{\qquad (Parseval's Identity)} \\ &=& \sup_{r\neq0}|\hat{S}(r)| (\gamma\delta)^\frac{1}{2}N^2 \end{array}$.

Rearranging we get $\sup_{r\neq 0}|\hat{S}(r)|\geq(\gamma\delta)^\frac{1}{2}|S|$, and hence $A$ is $\sqrt{\gamma\delta}$-HNU. $\Box$

To prove theorem 2, we need three lemmas:

Lemma 4 (Large deviation inequality of Bernstein) Let $X_1,\cdots,X_n$ be independent complex-valued random variables with $\mathbb{E}X_j = 0$ and $\mathbb{E}|X_j| = {\sigma_j}^2$. Write $\sigma^2 = \sum^n_{i=1} {\sigma_j}^2$ and suppose that $|X_j|\leq 1$ for all $j$. Suppose that $\sigma^2 \geq 6nt$. Then $\mathbb{P}(|X_1+\cdots+X_n|\geq nt) \leq 4e^{-\frac{n^2t^2}{8\sigma^2}}$.

Defintion Define $\|\cdot\|:\mathbb{Z}_N \rightarrow \mathbb{R}$ by $\|x\| = |x'/N|$, where $x'\in\{-\frac{N-1}{2},\cdots,\frac{N-1}{2}\}$ is the remainder of $x$ mod $N$. Let $\Gamma \subset \mathbb{Z}_N$ and $\varepsilon > 0$. Write $\mathcal{B}(\Gamma,\varepsilon) = \{x\in\mathbb{Z}_N: \|\gamma x\|\leq \varepsilon \text{ for all } \gamma\in\Gamma\}$, called the Bohr neighbourhood of $\Gamma$ with radius $\varepsilon$.

Lemma 5 Suppose that $|\Gamma| = d$. Then $\mathcal{B}(\Gamma,\varepsilon)$ contains an AP of length at least $\varepsilon N^\frac{1}{d}$.

Lemma 6 (Chang’s theorem) Let $B\subset \mathbb{Z}_N$ such that $|B| = \beta N, \rho \in (0,1)$ and $\mathcal{R} = \{r\in\mathbb{Z}_N: |\hat{B}(r)|\geq \rho |B|\}$. Then there is a set $\Lambda\subset\mathbb{Z}_N$ with $|\Lambda|\leq C\rho^{-2}\log{(\frac{1}{\beta})}$ such that $\mathcal{R} \subset \{\sum_j \varepsilon_j\lambda_j: \varepsilon_j\in\{-1,0,1\}, \lambda_j\in\Lambda \text{ for all }j\}$, where $C$ is an absolute constant independent of $\Lambda, B, \beta, N, \rho$ etc. (A known and correct value for $C$ is $144e^2$).

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 $\{-1,0,1\}$-span of $\Lambda$.)

The idea to prove theorem 2 is as follow: we first let $B\subset A$ such that $\sup_{r\neq 0} |\hat{B}(r)|$ is minimized among all subsets of $A$ with cardinality $\beta N$. Then make use of lemma 5 and lemma 6 to pick an AP, which we will call it $P$ later. Using this $P$, we can define a set $C$ with large cardinality, and hence with small Fourier coefficients, and from which one can define a subset $D$ of $C$ with small cardinality $t$ and small Fourier coefficients (using lemma 4). Since $D$ has a small Fourier coefficients, if we remove $t$ elements from $B$ (with suitable choice), and put all the elements of $D$ into $B$, the Fourier coefficients won’t change too much. If we further modify the elements in $D$, we can then form a new set $S'$, with same cardinality as $B$, yet has smaller Fourier coefficients than $B$, which will contradict the minimality of $B$. The problem comes from the modification of the elements in $D$, and surprisingly this will lead to the conclusion that $A$ 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.