MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Banach-Mazur distance between $\ell^p$-norms

Let $E^n$ be the real or complex space of dimension $n$. If $N$ and $M$ are two norms over $E^n$, and if $A$ is an endomorphism, then $$\|A\|^M_N:=\sup_{x\ne0}\frac{M(Ax)}{N(x)}$$ is an operator norm of $A$.

The Banach-Mazur distance between $N$ and $M$ is $$d(N,M):=\log\inf_{A\in Aut(E)}\|A\|^M_N\|A^{-1}\|^N_M.$$ It is actually a semi-distance, with $d(N,M)=0$ iff one passes from $N$ to $M$ by a change of coordinates. Thus $d$ is a distance on some quotient space, in which there is only one Euclidian norm, for instance.

Let us define the usual $\ell^p$-norm by $$\|x\|_p:=\left(\sum_j|x_j|^p\right)^{1/p}.$$ The $L^\infty$-norm is as usual. It has been known for a long time that if $1\le p,q\le2$, or if $2\le p,q\le\infty$, then $$d(\ell^p,\ell^q)=\left|\frac{1}{p}-\frac{1}{q}\right|\log n.$$ What is known if $1\le p\le2\le q\le+\infty$ ?

-

I've just looked in the "Handbook of the Geometry of Banach Spaces", Chapter 1, Section 8, which gives that $$d(\ell^p,\ell^q) = \log\max(n^{|1/p-1/2|}, n^{|1/q-1/2|})$$ up to a constant (which seems hard to find!) The argument is not entirely elementary, using cotype estimates. I'd also look in Tomczak-Jaegermann's book "Banach-Mazur distances and finite-dimensional operator ideals" but I don't have that on my shelf right now.

-
This does not seem correct, because the distance is zero when $p=q$, whereas your formula gives $|1/p-1/2|\log n$ instead. – Denis Serre Sep 16 2010 at 10:49
@Denis: Matt gave the formula for $p \le 2 \le q$ because that is what you asked for. BTW, it is conventional to define the B-M distance without the log, making the distance submultiplicative instead of subadditive, so the the B-M distance is the isomorphism constant between the two spaces. – Bill Johnson Sep 16 2010 at 11:31
@Bill : you are right. @Matt : the Handbook only gives the inequality $\le$, and says that it is acccurate up to an absolute constant. The equality cannot be always valid, because in dimension $2$ one has $d(\ell^1,\ell^\infty)=0$ (whereas this is positive in dimension $\ge3$). – Denis Serre Sep 16 2010 at 12:16
Is this a correct reading of the above: to compare $l^p$ with $l^q$, if $p$ and $q$ are on the same side of $2$, then the map $A = I$ is optimal. If they are on opposite sides of $2$, then it's hard to find a recipe for an optimal linear map, but it's only boundedly suboptimal to compare them to the $l^2$ norm. It shouldn't be hard to find optimal comparisons numerically in low dimensions. It would be interesting to see the optimal $A$ for some of these starting with dimension 3, e.g., what linear map best fits an octahedron inside the cube? Are pictures available somewhere? – Bill Thurston Sep 16 2010 at 13:31
@Denis: With complex scalars, $d(\ell_1^2,\ell_\infty^2)>0$. @Bill Thurston: For the upper bound, consider the case $n=2^k$ and the mapping from $\ell_p^n$ to $L_q^n$, $p\le 2 \le q$, that takes the unit vector basis to the Walsh basis. (Here $L_q^n$ is $L_q(\mu)$ with $\mu$ the uniform probability on $\{1,...,n\}$). – Bill Johnson Sep 17 2010 at 2:31
show 4 more comments
The text passage is a discussion about the Banach-Mazur distance between norms in finite-dimensional spaces, specifically focusing on the $\ell^p$-norms. It includes a mathematical question about the Banach-Mazur distance for certain values of $p$ and $q$ and provides some partial answers and references to further reading.
single_question_with_answer
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Banach-Mazur distance between $\ell^p$-norms

Let $E^n$ be the real or complex space of dimension $n$. If $N$ and $M$ are two norms over $E^n$, and if $A$ is an endomorphism, then $$\|A\|^M_N:=\sup_{x\ne0}\frac{M(Ax)}{N(x)}$$ is an operator norm of $A$.

The Banach-Mazur distance between $N$ and $M$ is $$d(N,M):=\log\inf_{A\in Aut(E)}\|A\|^M_N\|A^{-1}\|^N_M.$$ It is actually a semi-distance, with $d(N,M)=0$ iff one passes from $N$ to $M$ by a change of coordinates. Thus $d$ is a distance on some quotient space, in which there is only one Euclidian norm, for instance.

Let us define the usual $\ell^p$-norm by $$\|x\|_p:=\left(\sum_j|x_j|^p\right)^{1/p}.$$ The $L^\infty$-norm is as usual. It has been known for a long time that if $1\le p,q\le2$, or if $2\le p,q\le\infty$, then $$d(\ell^p,\ell^q)=\left|\frac{1}{p}-\frac{1}{q}\right|\log n.$$ What is known if $1\le p\le2\le q\le+\infty$ ?

-

I've just looked in the "Handbook of the Geometry of Banach Spaces", Chapter 1, Section 8, which gives that $$d(\ell^p,\ell^q) = \log\max(n^{|1/p-1/2|}, n^{|1/q-1/2|})$$ up to a constant (which seems hard to find!) The argument is not entirely elementary, using cotype estimates. I'd also look in Tomczak-Jaegermann's book "Banach-Mazur distances and finite-dimensional operator ideals" but I don't have that on my shelf right now.

-
This does not seem correct, because the distance is zero when $p=q$, whereas your formula gives $|1/p-1/2|\log n$ instead. – Denis Serre Sep 16 2010 at 10:49
@Denis: Matt gave the formula for $p \le 2 \le q$ because that is what you asked for. BTW, it is conventional to define the B-M distance without the log, making the distance submultiplicative instead of subadditive, so the the B-M distance is the isomorphism constant between the two spaces. – Bill Johnson Sep 16 2010 at 11:31
@Bill : you are right. @Matt : the Handbook only gives the inequality $\le$, and says that it is acccurate up to an absolute constant. The equality cannot be always valid, because in dimension $2$ one has $d(\ell^1,\ell^\infty)=0$ (whereas this is positive in dimension $\ge3$). – Denis Serre Sep 16 2010 at 12:16
Is this a correct reading of the above: to compare $l^p$ with $l^q$, if $p$ and $q$ are on the same side of $2$, then the map $A = I$ is optimal. If they are on opposite sides of $2$, then it's hard to find a recipe for an optimal linear map, but it's only boundedly suboptimal to compare them to the $l^2$ norm. It shouldn't be hard to find optimal comparisons numerically in low dimensions. It would be interesting to see the optimal $A$ for some of these starting with dimension 3, e.g., what linear map best fits an octahedron inside the cube? Are pictures available somewhere? – Bill Thurston Sep 16 2010 at 13:31
@Denis: With complex scalars, $d(\ell_1^2,\ell_\infty^2)>0$. @Bill Thurston: For the upper bound, consider the case $n=2^k$ and the mapping from $\ell_p^n$ to $L_q^n$, $p\le 2 \le q$, that takes the unit vector basis to the Walsh basis. (Here $L_q^n$ is $L_q(\mu)$ with $\mu$ the uniform probability on $\{1,...,n\}$). – Bill Johnson Sep 17 2010 at 2:31
show 4 more comments
user
The text passage is a discussion about the Banach-Mazur distance between norms in finite-dimensional spaces, specifically focusing on the $\ell^p$-norms. It includes a mathematical question about the Banach-Mazur distance for certain values of $p$ and $q$ and provides some partial answers and references to further reading.

TYPE: SINGLE_QUESTION_WITH_ANSWER