18
$\begingroup$

The Banach-Mazur distance $d(X, Y)$ between two normed spaces $X, Y$ of the same dimension is defined as $d(X, Y) = \log\inf \|T\| \cdot \|T^{-1}\|$, where the $T:X \to Y$ is a linear and invertible operator. The estimates between classical $\ell_p^n$ spaces are known and in particular we have that $d\left(\ell_1^n, \ell_{\infty}^n\right) \sim \sqrt{n}$ asymptotically. Using Walsh matrices it can be shown that for $n=2^k$ this distance is actually not greater than $\sqrt{n}$.

In the two dimensional case we clearly have $d(\ell_1^2, \ell_{\infty}^2)=1$. I wonder if anybody has managed to provide some more specific results in the three dimensional case. It is equivalent to finding two positively homothetic parallelotopes with one contained in and the second containing the regular octahedron with the homothety ratio as minimal as possible. It seems like pretty basic question in three dimensional discrete geometry, but still I could not find any information and the problem might be highly non-trivial. The only information I found was in the paper of Stromquist ("The maximum distance between two dimensional Banach spaces") where he wrote that this distance is not known. But it was 35 years ago, so I guess that there could be some new results in this direction. If not, maybe at least one could make some good conjecture on what this distance should be like?

$\endgroup$
2
  • $\begingroup$ If I understand well, you are especially interested in some situations where $Y$ is the dual of $X$. $\endgroup$ Apr 28, 2016 at 15:39
  • $\begingroup$ Well, that could be the next step to study it more generally. Actually there are some deep results of maximal possible distance between the space and its dual in the asymptotic settings. However, for the three dimensional case I think that very little is known. There are even some polytopes affinely equivalent to its dual, so that the distance is one. But as far as I know there is no characterization of such situation. $\endgroup$
    – tkobos
    Apr 28, 2016 at 15:45

1 Answer 1

15
$\begingroup$

This can be done as a nonlinear optimization problem: $T$ is a $3 \times 3$ matrix, and if $e_i$ and $v_j$ are the vertices of the unit balls in $\|\cdot\|_1$ and $\|\cdot\|_\infty$ norms respectively, you want to minimize $s$ subject to constraints $\|T e_i\|_\infty \le 1$, $\|T^{-1} v_j\|_1 \le s$ (or equivalently, $\|\text{Adj}(T) v_j\|_1 \le s |\det(T)|$, with $\det(T) \ne 0$).
Maple's Global Optimization Toolbox returns (almost immediately) an approximate solution, which is (up to roundoff error)

$$ T = \pmatrix{1/3 & 1 & 1\cr -1 & 1 & -1/3\cr 1 & 1/3 & -1\cr},\ s = \dfrac{9}{5}$$

It is easy to check that this does satisfy the constraints. Thus it appears that the answer is $9/5$. It should be possible to prove optimality rigorously, if somewhat tediously, using the Karush-Kuhn-Tucker conditions.

EDIT: I also tried the $4$-dimensional case. The solution Maple obtained was

$$ T = \pmatrix{0 & 1 & -1 & 1\cr -1 & 0 & 1 & 1\cr 1 & -1 & 0 & 1\cr -1 & -1 & -1 & 0\cr}, \ s = 2 $$

$\endgroup$
3
  • 1
    $\begingroup$ For what it's worth, this Mathematica code gist.github.com/anonymous/8f2bbb5ddb9a463a592ae6e6bfe363d6 returns the same values of s (though my T is the inverse of yours, confusingly). When I try using your conventions for T, Mathematica returns s=2.15 for n=4, and it's not clear to me why numerical error is so much larger in that case. I couldn't get a numerically reliable answer for n=5, there the best I've found is s=2.32871 with a floating point matrix with some entries suspiciously close to +-1 but the other entries messy. $\endgroup$
    – j.c.
    Apr 28, 2016 at 19:15
  • $\begingroup$ $n=5$ also seems difficult for the Global Optimization Toolbox. $\endgroup$ Apr 28, 2016 at 23:44
  • $\begingroup$ That is a very good insight! And that would be actually a really nice answer. As I said, for $n=2^k$ it can be proved that the distance is at most $\sqrt{n}$ using Walsh matrices (although I don't recall the details at this moment). Maybe it is actually $\sqrt{n}$? For $n=4$ it seems so. I will wait for a few days before accepting this as an answer, as someone could possibly find a specific reference or post the proof. $\endgroup$
    – tkobos
    Apr 29, 2016 at 10:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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