# proving topological equivalence

How would I show that $$d_E = \sqrt{\sum_{i=1}^n(x_i-y_i)^2}$$ and $$d_\infty= \sum_{i=1}^n|x_i-y_i|$$ and $$\sup\{|x_1-y_1|,|x_2-y_2|,...,|x_n-y_n|\}$$ are topologically equivalent on $\mathbb{R}^n$? I can do it for $\mathbb{R}^2$, but I'm not sure how a generalization looks like.

-
What does topologically equivalent mean, again? That they induce the same topology? – Mike Miller Mar 31 '14 at 7:52
(BTW - I think it should say $(x_i-y_i)^2$ in $d_E$) – Mike Miller Mar 31 '14 at 7:53
yes.. The question would ultimately boil down to find an open ball that can "contain" the other metric. – Millardo Peacecraft Mar 31 '14 at 7:54
Thanks, I just edited the question. – Millardo Peacecraft Mar 31 '14 at 7:55
Your notation is a bit weird, $d_\infty$ is the $L^1$ distance. – Najib Idrissi Mar 31 '14 at 8:01

For your specific case, nik gives the simplest proof. This is in case you're interested in something more general.

I'm going to prove something stronger: all norms on $\Bbb R^n$ are equivalent. Pick a basis $\{e_1, \dots, e_n\}$ on $\Bbb R_n$, and write for convenience $a_1e_1 + \dots + a_ne_n = (a_1, \dots, a_n)$.

Let $||\cdot||_1$ be a given norm, and $||\cdot||_2$ be the norm given by $||v|| = d_E(v,0)$ in your notation. (This is the Euclidean metric.) Notice that topological equivalence between these two norms is the same as showing that there exist positive reals $a$ and $b$ with $$a||v||_2 \leq ||v||_1 \leq b||v||_2$$ (This equivalence follows from the fact that $\Bbb R^n$ is a vector space; I'll leave that bit to you.)

Now immediately $$||(a_1, \dots , a_n)||_1 \leq \sum_{i=1}^n |a_i| \cdot ||e_i||_1 \leq \left(\sum_{i=1}^n |a_i|\right) \max(||e_1||_1, \dots ||e_n||_1)$$ Let $M=\max(||e_1||_1, \dots ||e_n||_1)$. Then $||v||_1 \leq M\sqrt{n}||v||_2$ by the Cauchy-Schwarz inequality, as mentioned in nik's answer.

To prove the reverse direction, we can't make estimations like before; we have to invoke a teeny bit of topology.

What we just proved is, in addition, that the map $f:\Bbb R^n\rightarrow \Bbb R: v \mapsto ||v||_1$ is continuous (where I mean $\Bbb R^n$ with the topology given by $||\cdot||_2$). Now note that the unit sphere in $(\Bbb R^n, ||\cdot||_2)$ is the sphere, a compact topological space. Now, any continuous function from a compact space to the reals takes on a minimum value (see, for instance, here for a proof.) Let $m$ be the minimum value of the map $v \mapsto ||v||_1$ defined on the unit sphere. So (for $v$ in the unit sphere) $||v||_1 \geq m$, and so for any vector in $\Bbb R^n$, $||v||_1 \geq m||v||_2$. So $$m||v||_2 \leq ||v||_1 \leq M\sqrt{n} ||v||_2$$ So these two norms are equivalent. Since $||\cdot||_1$ was arbitrary, any two norms on $\Bbb R^n$ are equivalent.

-

Use CS inequality we have: $d_E \leq d_\infty \leq n^{0.5}\cdot d_E$. this shows the two metrics are topologically equivalent.

-

Let $D$ be another metric defined by $D(x,y) = \max_i |x_i - y_i|$. Then the following inequalities hold: \begin{align} d_E(x,y) & \leq \sqrt{\sum_{i = 1}^n D(x,y)^n} = \sqrt{n} D(x,y) \\ D(x,y) & \overset{(1)}{\leq} d_\infty(x,y) \\ d_\infty(x,y) & \overset{(2)}{\leq} \sqrt{n} d_E(x,y) \end{align}

(1) is because the specific $D(x,y) = |x_{i_0} - y_{i_0}|$ appears in the sum that defines $d_\infty$, and all the other terms are nonnegative. (2) is the Cauchy-Schwarz inequality.

From these you can conclude that $d_E \leq \sqrt{n} d_\infty \leq n d_E$. So when you have an open ball for $d_E$, it's included in the open ball of radius $r \sqrt{n}$ for $d_\infty$, and reciprocally.

Only one more inequality is necessary to prove that $D$ is equivalent to the other two: $$d_\infty(x,y) \leq \sum_{i=1}^n D(x,y) = n D(x,y)$$ Because then by inequality $(1)$ it's equivalent to $d_\infty$, which is equivalent to $d_E$.

-
I've edited the question. Mind if I pick your brain some more? – Millardo Peacecraft Mar 31 '14 at 8:43
@MillardoPeacecraft: I edited my answer. – Najib Idrissi Mar 31 '14 at 8:58