0

I was reading the proof of the Proposition 2.18 from Tao-Vu book but one moment is really confusing.

Question 1: I did not understand how the authors obtained ineqality which I highlighted by green color. But this is my guess: consider a function $f:M\to N$, where $$M=\{(x,x',c,c',a_1,a'_1)\in X\times X\times (A+B)\times (A+B)\times A\times A: z=c-a_1-x, \ z'=c'-a'_1-x'\}$$ and $$N=\{(x,x',c,c',a_1-a'_1)\in X\times X\times (A+B)\times (A+B)\times (A-A): z-z'=c-c'-(a_1-a'_1)-x+x'\}$$ defined by $(x,x',c,c',a_1,a'_1)\mapsto (x,x',c,c',a_1-a'_1)$.

It is obvious that $f$ is well-defined and injective. We already know that $|M|\geq \frac{|A|^2}{4}$. Since $f$ is injective, then $|N|\geq |M|$ and hence $|N|\geq \frac{|A|^2}{4}$. Is my reasoning correct?

If yes, then why they write the lines which I hightlighted by red color? what they want to say?

Question 2: Also I am slightly confused by the last paragraph of the proof. I understood that for any element of $2B-2B$ we can find $\geq \frac{|A|^2}{4}$ representations of the form $c-c'-d-x+x'$, where $(x,x',c,c',d)\in X\times X\times (A+B)\times (A+B)\times (A-A)$. How to obtain the desired inequality? Do I need to consider some function (injective or surjective?) $\phi: 2B-2B\to X\times X\times (A+B)\times (A+B)\times (A-A)$? Can anyone provide more details please?

enter image description here

RFZ
  • 16,814
  • 2
    Yes, you are right. The line you've highlighted in red is the authors verifying that your injection is indeed an injection (which requires that $a_1$ and $a_1'$ are recoverable from $z,z',c,c',x,x',a_1-a_1'$). – Thomas Bloom Feb 16 '22 at 09:22
  • 2
    For Question 2, consider for each $w\in 2B-2B$ the set of $(x,x',c,c',d)\in X^2\times (A+B)^2\times (A-A)$ such that $w=c-c'-d-x+x'$. These are disjoint for different $w\in 2B-2B$, and each has size at least $\lvert A\rvert^2/4$. Therefore their union, which must have size at most $\lvert X\rvert^2\lvert A+B\rvert^2\lvert A-A\rvert$, has size at least $\lvert 2B-2B\rvert\lvert A\rvert^2/4$. – Thomas Bloom Feb 16 '22 at 09:26
  • @ThomasBloom, Dear Prof. Bloom! I am slightly confused because I don't think what I've highlighted in red is the justification of injectivity of $f$. You see in my post that I defined the function $f:M\to N$ such that $f((x,x',c,c',a_1,a'_1))=(x,x',c,c',a_1-a'_1)$. Let's prove that $f$ is injective. Suppose that $f((x,x',c,c',a_1,a'_1))=f((x_0,x'_0,c_0,c'_0,\alpha_1,\alpha'_1))$, then $(x,x',c,c',a_1-a'_1)=(x_0,x'_0,c_0,c'_0,\alpha_1-\alpha'_1)$. Also $z=c-a_1-x=c_0-\alpha_1-x_0 \ ()$ and $z'=c'-a'_1-x'=c'_0-\alpha'_1-x'_0 \ (*)$. – RFZ Feb 16 '22 at 21:14
  • @ThomasBloom, Since $x=x_0, c=c_0$ then $(*)$ gives us that $a_1=\alpha_1$ and in the same way $a'_1=\alpha'_1$. We are done. – RFZ Feb 16 '22 at 21:14
  • @ThomasBloom, or probably I am misunderstanding what authors wrote there. – RFZ Feb 16 '22 at 21:15
  • 2
    Yes, your argument is an alternative arrangement of the proof of injectivity. That is what the sentence is red is also doing, albeit perhaps expressed slightly informally. The idea is the same: that the input can be uniquely recovered from the output, which is injectivity. – Thomas Bloom Feb 16 '22 at 22:24
  • @ThomasBloom, Dear Prof. Bloom! Thanks a lot for your constant! I really apprecciate it! – RFZ Feb 16 '22 at 23:54
  • @ThomasBloom, Dear Prof. Bloom! I was wondering do you time to take a look at this link please? https://math.stackexchange.com/questions/4387086/exercise-2-4-2-from-tao-vu-book – RFZ Feb 20 '22 at 21:01

0 Answers0