Let $P$ be a proper progression of rank $d$ in an additive group $(Z,+)$, and let $A\subset P$ such that $|A| \leqslant ε|P|$ for some $0 <ε< 1.$ Show that $P\setminus A$ contains a proper progression $Q$ of rank $d$ with $|Q| \geqslant ε^{-1} C^{-d}$ for some absolute constant $C$.

This exercise from Tao-Vu's book (Additive Combinatorics) is solved as $\text{Q}2$ in this file, and the solution starts with the observation that the claim is trivial if $\varepsilon \geqslant 8^{-d}$. I am trying to understand this.

It seems they get $C = 4$ in the second part of the proof, and also assume this in the first part - but why? With $C = 4$, and $\varepsilon \geqslant 8^{-d}$ (i.e., $\varepsilon^{-1} \leqslant 8^{d}$), it is enough to find $Q$ with $|Q| \geqslant 8^d \cdot 4^{-d} = 2^d$, for then $|Q| \geqslant 8^d \cdot 4^{-d} \geqslant ε^{-1} C^{-d}$ with $C = 4$. If $P = a + [0,N]\cdot v$ for $a\in Z$, $N = (N_1,\ldots,N_d)$, and $v = (v_1,\ldots,v_d)$, then $$Q = \{a + n_1v_1 + \ldots + n_dv_d: 0\le n_j\le 1\},$$ is a generalized arithmetic progression with $|Q| = 2^d$. Is $Q\subset P\setminus A$? I am not sure, but perhaps using $|A| \leqslant \varepsilon |P|$, we can find some $k\in \Bbb N$ such that $$Q = \{a + n_1v_1 + \ldots + n_dv_d: k\le n_j\le k+1\} \subset P\setminus A\text{?}$$

Another possibly useful observation is that $|P\setminus A| \geqslant \frac{1-\varepsilon}{\varepsilon} |A|$.

Thanks for any help!


  1. Let $(Z,+)$ be an additive group. A progression of $P$ rank $d$ is $$P = \left\{a+\sum_{i=1}^d n_iv_i: 0\le n_i\le N_i\right\} = a + [0,N]\cdot v,$$ where $N = (N_1,\ldots,N_d) \in \Bbb Z^d_{\ge 1}$, $v = (v_1,\ldots,v_d) \in Z^d$, and $a\in Z$. $P$ is proper if all the terms in the progression are distinct.

1 Answer 1


When $\varepsilon \geq 8^{-d}$, take $C=8$. The content of the statement becomes that such a $Q$ can be found with $|Q|\geq 1$, which is certainly true (any set of size $1$ is a progression of rank $d$). When $\varepsilon < 8^{-d}$, the remainder of the solution shows that the result is true for $C=4$. This certainly implies that it is true for $C=8$. So, the result is true, regardless of $\varepsilon$, when one takes $C=8$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .