0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ @CalvinLin, for well-definedness: if $(a_1-c_1,b_1)=(a_2-c_2,b_2)$, then $b_1=b_2$. How it follows that $a_1=a_2$ and $c_1=c_2$? I do not see that. $\endgroup$
    – ZFR
    Nov 12, 2021 at 19:03
  • $\begingroup$ @CalvinLin, for infectivity I do not think that you are right because this map is actually injective! $\endgroup$
    – ZFR
    Nov 12, 2021 at 19:04

1 Answer 1

1
$\begingroup$

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?

$\endgroup$
4
  • $\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$
    – ZFR
    Nov 12, 2021 at 19:45
  • $\begingroup$ It seems to me that our functions are identical. $\endgroup$
    – ZFR
    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$
    – ZFR
    Nov 12, 2021 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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