# How to show that $\mathbb R^n$ with the $1$-norm is not isometric to $\mathbb R^n$ with the infinity norm for $n>2$?

Could you please give me a hint to prove that $\mathbb{R}^n$ with the 1-norm $\lvert x\rvert_1=\lvert x_1\rvert+\cdots+\lvert x_n\rvert$ is not isometric to $\mathbb{R}^n$ with the infinity-norm $\lvert x\rvert_\infty = \max_{i=1,\ldots,n}(\lvert x_i\rvert)$ for $n\gt2$.

I do not see how the critical case $n=2$ enters the picture.

Thank you!

-
Count the number of extreme points for the unit ball. – GEdgar Aug 7 '12 at 11:56
@GEdgar: the way I understand it, the question is about purely metric structure, so you can't really define extreme points. – tomasz Aug 7 '12 at 12:11
The unit ball for the 1-norm is a cross-polytope with $2*n$ extreme points (in these two cases they are just the vertices) and the unit ball for the infinity norm is just an n-cube with $2^n$ vertices. So for $n=2$ there are in both cases $4$ vertices, but for $n>2$ the infinity unit ball has more. – zerhan Aug 7 '12 at 12:25
I guess for knowing that an isometry carries extreme points to extreme points you need to know that surjective isometries between normed spaces are affine (hence linear if they preserve the origin). This isn't trivial: it's the Mazur-Ulam theorem. – t.b. Aug 7 '12 at 12:30
@tomasz: you're very welcome, I like it too :) see this thread for further remarks and pointers. – t.b. Aug 7 '12 at 13:41

To wrap the comments up (assuming $n \geq 2$ since the cases $n=0,1$ are uninteresting):

From the Mazur–Ulam theorem we know that a surjective distance-preserving map between normed spaces is necessarily affine. After composing with a translation we may assume that our isometry preserves $0$, so we may assume that the isometry is linear right from the start.

A surjective linear isometry must map the extreme points of the unit ball of the domain onto the extreme points of the unit ball of the range. A moment's thought shows that the unit ball in the $\ell^1$-norm has $2n$ extreme points, namely the $n$ coordinate vectors and their $n$ negatives; and that the unit ball in the $\ell^\infty$-norm has $2^n$ extreme points: the vectors all of whose entries are $\pm 1$. Therefore isometry is only possible if $n =2$, where there is an isometry, given by $e_1 \mapsto e_1+e_2$ and $e_2 \mapsto -e_1 + e_2$.

-

But one can do without the Mazur-Ulam theorem just as easily. I find it convenient to put the exponent $p$ in subscript, freeing the superscript for dimension: $\ell_\infty^n$ and $\ell_1^n$

Suppose $F:\ell_\infty^n\to \ell_1^n$ is an isometry (which I do not assume to be surjective or linear). By translation we can achieve $F(0)=0$. Let $V\subset \ell_\infty^n$ be the set of vertices of the unit cube, i.e., the set of all vectors with entries $\pm1$. This set has three interesting properties:

1. all points are at distance $1$ from the origin
2. all points are at distance $2$ from one another
3. the cardinality of the set is $2^n$.

Let $W=F(V)$. The set $W\subset \ell_1^n$ also has the properties 1,2,3 listed above. For each vector $v\in W$ consider its positive and negative supports $\mathrm{supp}^+v=\{1\le j\le n : v_j> 0\}$ and $\mathrm{supp}^-v=\{1\le j\le n : v_j< 0\}$. If $n>2$, then $2^n>2n$. Therefore, we can assume that at least $n+1$ vectors in $W$ have nonempty positive supports. But then at least two of them, say $v'$ and $v''$, have overlapping positive supports. This creates cancellation when we compute distance between them: $\|v'-v''\|_1<\|v'\|_1+\|v''\|_1=2$ , a contradiction. QED

The proof actually shows that $\ell_{\infty}^n$ does not admit an isometric embedding (linear or not) into $\ell_1^N$ for $N<2^{n-1}$.

-
That's very nice! – t.b. Aug 7 '12 at 17:26
Thank you! It is nice to see also a proof without the Mazur-Ulam theorem! – zerhan Aug 8 '12 at 8:48
I just saw your blog entry on this answer. Very beautiful. Thanks a lot for that! – t.b. Aug 19 '12 at 20:21