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 Answer 1


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?

  • $\begingroup$ First of all thank you for your reply! I appreciate that! I'll try to show that this function is well-defined and injective. But let me ask you one question: yeah I see that the "function" which I "defined" is not well-defined. But I cannot feel the difference between my "function" and the way you defined? Can you explain it please? $\endgroup$
    – RFZ
    Nov 12, 2021 at 19:45
  • $\begingroup$ It seems to me that our functions are identical. $\endgroup$
    – RFZ
    Nov 12, 2021 at 20:02
  • $\begingroup$ @ZFR Yours isn't a function, since it isn't well-defined. What I'm essentially doing is picking a way modify your function so that it is well-defined. $\endgroup$ Nov 12, 2021 at 20:18
  • $\begingroup$ I checked and I see that your function is indeed injective and well-defined but I guess you did not get my question. What is the main difference between my "function" and your construction? $\endgroup$
    – RFZ
    Nov 12, 2021 at 22:00

You must log in to answer this question.

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