0
$\begingroup$

I am reading Tao-Vu book on Additive combinatorics and came across the following lemma. I know that it is better to ask this question on MathStack but I asked few questions before and no one answered yet and so I've decided to ask it here.

I understood most of the proof but I am slightly confused with the last part and how they obtained an upper bound in $(2.13)$? Can anyone explain it in a more detailed way please?

Thanks a lot!

enter image description here

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

For each element of $x\in A+B+nS$ we construct at least $(\frac{|A||B|}{2|A+B|})^n$ distinct sequences $(t_0,\ldots,t_n)\in (A+B)^{n+1}$ such that $x=t_0+\ldots+t_n$ (the sentence after "observe that..." verifies that they are distinct). Since such sequences for different $x$'s are obviously distinct (they have not equal sums), all sequences are distinct, so the total number of sequences is at most $$|A+B|^{n+1}\geqslant |A+B+nS|\cdot \left(\frac{|A||B|}{2|A+B|}\right)^n$$ that is (2.13).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Dear Fedor! I think that I got your point. But let me ask you a minor a question: I edited my question yesterday when I added an edit but later I deleted but you can see it anyway. So my point was basically to construct some function from $A+B+nS$ to $(n+1)(A+B)$ with desired properties (please see my edit). But in your answer do you construct implicitly some function from $A+B+nS$ to $(A+B)^{n+1}$? I guess no. You claim is that from any element of $A+B+nS$ you can construct $\geq \alpha^n$ elements from $(A+B)^{n+1}$. $\endgroup$
    – RFZ
    Nov 16, 2021 at 23:36
  • 1
    $\begingroup$ We construct a function from $A+B+nS$ to subsets of $(A+B)^{n+1}$ such that each subset has size at least $\alpha^n$ and these subsets are disjoint. $\endgroup$
    – Fedor Petrov
    Nov 17, 2021 at 4:58
  • $\begingroup$ Great! Thank you so much, Fedor! +1 $\endgroup$
    – RFZ
    Nov 18, 2021 at 0:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.