# Exercise $3.2.6$ in Tao-Vu's Book - why is it trivial for $\epsilon \geqslant 8^{-d}$?

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!

Notation:

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.

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$$.