Triangle inequality for Ruzsa distance

149 Views Asked by At

Suppose that $Z$ is an additive group, i.e. $Z$ is an abelian group under addition. Let $A$ be an additive set, i.e. $A$ is a non-empty finite subset of $Z$.

For any two additive sets $A$ and $B$ in $Z$ define the Ruzsa distance as follows: $d(A,B):=\log \dfrac{|A-B|}{\sqrt{|A||B|}}$, where $\log$ is a natural logarithm.

My goal is to show that Ruzsa distance obeys triangle inequality: for any additive sets $A,B,C$ in $Z$ we have $d(A,C)\leq d(A,B)+d(B,C).$ It is suffices to show that $|A-C||B|\leq |A-B||B-C|.$

Let's construct a function $f:(A-C)\times B\to (A-B)\times (B-C)$ defined by rule: $(a-c,b)\mapsto (a-b,b-c).$

I have some issues to show that this function is well-defined and injective.

Injectivity: Suppose that $f((a_1-c_1,b_1))=f((a_2-c_2,b_2)),$ then $(a_1-b_1,b_1-c_1)=(a_2-b_2,b_2-c_2),$ then it implies that $a_1-a_2=b_1-b_2=c_1-c_2.$ How to show that $(a_1-c_1,b_1)=(a_2-c_2,b_2)?$

Well-definedness: If $(a_1-c_1,b_1)=(a_2-c_2,b_2),$ then we need to show that $(a_1-b_1,b_1-c_1)=(a_2-b_2,b_2-c_2).$

Can anyone show it please?

1

There are 1 best solutions below

4
On

This function, as stated, isn't well-defined: if $A=B=C=\{0,1\}$, then you might define $f(0,0)$ by $$f(0-0,0)=(0-0,0-0)=(0,0)$$ while you could also select $$f(1-1,0)=(1-0,0-1)=(1,-1).$$ As for coming up with a function that does work, I'd recommend starting by, for each $x\in A-C$, selecting a fixed pair $(a_x,c_x)\in A\times C$ with $a_x-c_x=x$. Then, you won't run into the same issue as above (since you will no longer try to define $f$ using $0=0-0$ and $0=1-1$. Can you show that the function is then well-defined and injective?