Exercise 1.1.6 in Additive Combinatorics

Question

I'm having trouble understanding Exercise 1.1.6 in Additive Combinatorics by Tao and Vu.

1.1.6 Consider a set $A$ as above. Show that there exists a subset $\{v_1, \ldots, v_d\}$ of $Z$ with $d = O(\log \frac{|Z|}{|A|})$ such that

$|A + [0,1]^d \cdot (v_1, \ldots, v_d)| \geq |Z|/2$.

"As above" just means that $A \subseteq Z$, where $Z$ is a finite group. Here was my first attempt:

Let $A_1, \ldots, A_d$ be defined by the recurrence relation $A_{i+1} = A_i \cup (A_i + v_{i+1})$, with $A_0 = A$. Then, $A_d = A + [0,1]^d \cdot (v_1, \ldots, v_d)$. By Exercise 1.1.5, we have

$|A_{i+1}| = |A_i \cup (A_i + v_{i+1})| \geq |Z| \left[ 1 - \left( 1 - \dfrac{|A_i|}{|Z|} \right)^2 \right] = |A_i| \left( 2 - \dfrac{|A_i|}{|Z|} \right) \geq |A_i| \left( 2 - \dfrac{|A|}{|Z|} \right)$

Thus,

$|A_d| \geq |A| \left( 2 - \dfrac{|A|}{|Z|} \right)^d$

Since $\lim_{|Z| \to \infty} \log(2 - |A|/|Z|) = \log 2$, we can take

$d \geq \log \dfrac{|Z|}{|A|} \dfrac{1}{\log \left( 2 - \frac{|A|}{|Z|} \right)} - \dfrac{\log 2}{\log \left( 2 - \frac{|A|}{|Z|} \right)} = O \left( \log \dfrac{|Z|}{|A|} \right)$

However, applying this method to Exercise 1.1.7 gives a tighter bound than the question requests.

1.1.7 Consider a set $A$ as above. Show that there exists a subset $\{v_1, \ldots, v_d\}$ of $Z$ with $d := O(\log \frac{|Z|}{|A|} + \log \log(10 + |Z|))$ such that

$A + [0,1]^d \cdot (v_1, \ldots, v_d) = Z$.

Since $Z$ is finite, the removal of cardinality shouldn't matter, and, if the solution to Exercise 1.1.6 were valid, then we could simply take

$d \geq \log \dfrac{|Z|}{|A|} \dfrac{1}{\log \left( 2 - \frac{|A|}{|Z|} \right)} = O \left( \log \dfrac{|Z|}{|A|} \right)$

which doesn't have the $\log \log (10 + |Z|)$ term, suggesting I am in error.

Since this is self-study, I have no instructor to whom to turn.

• Am I understanding the big O notation correctly? (In particular that $A$ is fixed, that $n = |Z|$, and that $\log(2 - |A|/|Z|)$ is essentially a constant)
• Is my solution to 1.1.6 correct? If not, why does it fail?
• Whence comes the $\log \log (10 + |Z|)$ term?

And, more generally,

• Are there written solutions to the exercises for this textbook available?

Answer 1

I found the (silly) error:

$|A_i| \left( 2 - \dfrac{|A_i|}{|Z|} \right) \leq |A_i| \left( 2 - \dfrac{|A|}{|Z|} \right)$

Answer 2

The big $ O $ notation means "something whose norm or absolute value is bounded by a constant times whatever is inside the brackets". An important example is $ O (1) $ which means uniformly bounded (by an absolute constant such as 3 or 280).

Implicitly, in any case the constant should NEVER depend on what lies inside the brackets, otherwise anything would be a big $ O $ of anything. $ |Z| $ would be a $ O (1) $ since it is bounded by $ 1 $ times the "constant" $|Z|$...

So when you consider $\log(2 - |A|/|Z|)$ as a constant, that is wrong since it does depend on what lies inside your big $ O $, but you could argue that it lies between $0 $ and log $(2) $ no matter what. However, MOST IMPORTANTLY: the direction of your inequality is wrong. $ f (x) $ is $ O (x) $ means the absolute value of $f (x) $ is LESS than a constant times $ x $.

Another remark, when you have $|Z|$ tend to infinity in an expression involving $ A $, this doesn't really make sense if you don't control the behaviour of $A $ whose very definition depends on $Z$.