Suppose $d$ is the Euclidean metric on $\mathbb{R}^n$, $d(x,y)=\sqrt{\sum_{i=1}^n(x_i-y_i)^2}$, and $\tau(x,y)=\sum_{i=1}^n|x_i-y_i|$ is the taxicab metric on $\mathbb{R}^n$.

When showing this two metrics are equivalent, it is not hard to bound $\tau$ by $$ \tau(x,y)\leq n d(x,y). $$

Is it possible to tighten the bound to $\tau(x,y)\leq\sqrt{n}d(x,y)$?


No, it's not possible: $\tau( (0.4,0.4), (0,0) ) = 0.8 > 0.46 > \sqrt{2} (0.4^2+0.4^2) = \sqrt{2}d( (0.4,0.4), (0,0) )$

edit: As I somehow missed to take the square root, this counterexample is wrong. See below for a correct answer that it is in fact possible to work with $\sqrt{n}$.

  • $\begingroup$ Thanks for counter-example. $\endgroup$ – Jong Gim May 24 '13 at 1:17

I think the counterexample forgot to take the square root of $d$. Instead, this follows from the Cauchy-Schwarz inequality.

If $x,y$ are in $\mathbb{R}^n$, $$ \tau(x,y)=\sum_{i=1}^n|x_i-y_i|=\left|\sum_{i=1}^n|x_i-y_i|\right|\leq\sqrt{\sum_{i=1}^n (x_i-y_i)^2}\sqrt{\sum_{i=1}^n 1^2}=\sqrt{n}d(x,y). $$

  • $\begingroup$ Oh, you are absolutly right... I somehow forgot to take the square root - weird... $\endgroup$ – user79202 May 24 '13 at 20:03
  • $\begingroup$ @user79202 Happens to all of us at some point! $\endgroup$ – Ben West May 24 '13 at 22:54

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.