This question is from Tao and Vu's book, Exercise 1.1.7., which is part of the chapter "The probabilistic method".
The problem is:
Problem. Consider a nonempty subset $A$ of finite abelian group $(Z,+)$. Show that there exists a subset $\{v_1,v_2, ..., v_d\}$ of $Z$ with $d=O(\log\frac{|Z|}{|A|}+\log\log(10+|Z|))$ such that \begin{equation} A+\{0,1\}^d \cdot (v_1,v_2, ..., v_d)=\{a+\sum u_i v_i | a\in A, u_i=0 \ \text{or} \ 1 \}=Z. \end{equation}
I tried to solve this problem, but I am having a hard time to improve this. I'd like to introduce my attempt:
I used the following lemma.
Lemma. Let $A,B$ be nonempty subsets of $Z$, then there exists an $x\in Z$ such that \begin{equation} 1-\frac{|A\cup(B+x)|}{|Z|}\leq \left( 1-\frac{|A|}{|Z|}\right)\left( 1-\frac{|B|}{|Z|}\right). \end{equation}
Proof: Let us choose $x$ uniformly random from $Z$ and $(B+x)=B'$. Then $E(|A\cup B'|)=E(|A|+|B'|-|A\cap B'|)$ $=E(|A|)+E(|B'|)-E(|A\cap B'|)$, and $E(|A\cap B'|)=\sum_{x\in Z} P(x\in A\cap B')=\sum_{x\in Z} P(x\in A)P(x\in B')$ $=\displaystyle\sum_{x\in Z}\frac{|A||B'|}{|Z|^2}=|A||B'|/|Z|$. Since $|B'|=|B|$, we deduce $E\left(1-\displaystyle\frac{|A\cup(B')|}{|Z|}\right)= \left( 1-\displaystyle\frac{|A|}{|Z|}\right)\left( 1-\displaystyle\frac{|B|}{|Z|}\right)$.
Now let $A_i=A_{i-1}\cup (A_{i-1}+v_i)$. Then clearly $A_0=A$ and $A_d=A+\{0,1\}^d \cdot (v_1,v_2, ..., v_d)$. By lemma, we can choose $v_i$ such that $$1-|A_i|/|Z|\leq (1-|A_{i-1}|/|Z|)^2,$$ or $$|A_i|\geq |A_{i-1}|(2-|A_{i-1}|/|Z|).$$ Using this inequality inductively, we get $|A_d|\geq \prod_{1\leq i\leq d}(2-|A_{i-1}|/|{Z}|)|A_0|$. Now, since we can choose $v_i$ such that $|A_i|\gneq|A_{i-1}|$ (if |A_i|=|A_{i-1}|, adding $v_i$ is actually meaningless.), so at least $$|A_d|\geq \prod_{1\leq i \leq d}\left(1+i/|Z|\right) |A_0|.$$ Taking logarithm at both side, we get $\log|A_d|\geq\sum_{1\leq i\leq d}\log(1+i/|Z|)+\log|A|$. We have to choose $d$ satisfying $|A_d|\geq|Z|$ so that $A_d=Z$, so let's find such $d$ with $\sum_{1\leq i\leq d}\log(1+i/|Z|)+\log|A|\geq \log |Z|$. I want to estimate 'well' $$\sum_{1\leq i\leq d}\log(1+i/|Z|)\sim\int_1^d \log(1+\frac{x}{|Z|})dx\sim (|Z|+d)\log(1+\frac{d}{|Z|})-d$$ so that we can find inequality of $d$.
I am having trouble to make this inequality into usable form.
Also, I worry the assumption of at least part that bounds $|A_d|\geq \prod_{1\leq i \leq d}\left(1+i/|Z|\right) |A_0|$ is overkilling.
Another question, I am undergraduate student and not mathematically mature yet. However, I am very fascinated to analytic number theory and additive combinatorics. I am also interested in ergodic number theory, or ergodic Ramsey theory. However, in my university, classes about these subjects merely opens, so I have to self-study these subjects. Are there any recommendations about studying materials, or curriculums, or anything else?
Any helps will be thankful!
You have the right construction, just need to arrange the derivation of the final bound a little differently.
Let $\alpha=\lvert A\rvert/\lvert Z\rvert$ and, in general, $\alpha_i=\lvert A_i\rvert/\lvert Z\rvert$. By the construction you outline, with $A_0=A$ and $A_i = A + \{0,1\}^i\cdot (v_1,\ldots,v_i)$ for some suitable choice of $v_i$ we can iteratively ensure that
$$ 1- \alpha_{i+1}\leq (1-\alpha_i)^2.$$
While $\alpha_i\leq 1/2$ this implies that $\alpha_{i+1}\geq \frac{3}{2}\alpha_i$, and so in general $\alpha_d \geq (3/2)^d\alpha$. In particular, there is $d=O(\log(1/\alpha))$ such that $\alpha_d\geq 1/2$.
We now continue the same procedure, but now notice that $(1-\alpha_d)\leq 1/2$, and so in general this iteration will give $$ 1-\alpha_{d+k} \leq 2^{-2^k}.$$
In particular after $k=O(\log\log \lvert Z\rvert)$ steps we have $1-\alpha_{d+k}< 1/\lvert Z\rvert$, and so $\lvert A_{d+k}\rvert > \lvert Z\rvert-1$, and hence $A_{d+k}=Z$ as required.