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
    Commented 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
    Commented Nov 17, 2021 at 4:58
  • $\begingroup$ Great! Thank you so much, Fedor! +1 $\endgroup$
    – RFZ
    Commented Nov 18, 2021 at 0:10

You must log in to answer this question.

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