6
$\begingroup$

I am new to the notion of distance between two symmetric convex bodies, and I am looking for some help in understanding the same. This is also meant to be an informative post for those who are not already familiar with the idea and want to scratch their brains a little on New Year's Eve. I hope you enjoy it!
To begin with, I quote the definition with a supplementary figure below:

The distance $d(K, L)$ between symmetric convex bodies $K$ and $L$ is the least positive $d$ for which there is a linear image $\tilde L$ of $L$ such that $\tilde L ⊂ K ⊂ d\tilde L$. Note that this distance is multiplicative, not additive: in order to get a metric (on the set of linear equivalence classes of symmetric convex bodies), we would need to take $\log d$ instead of $d$. In particular, if $K$ and $L$ are identical then $d(K, L) = 1$. enter image description here

  1. From the image it seems that the distance between $K$ and $L$, is not dependent on the size of $L$. I mean, we are looking at a linear image $\tilde L$ of $L$, so looks like all information about the initial size of $L$ is already lost. Is it safe to conclude that $d(K,L)$ does not depend on the size of $L$, and only on its shape? Does it depend on the size of $K$, or that is immaterial too?

  2. The author remarks that if $K$ and $L$ are identical, then $d(K,L) = 1$. What does identical mean? Only the shape, or also the size? $d(K,L) = 1$ just means $\tilde L ⊂ K ⊂ \tilde L$ so that $K = \tilde L$. Again, this says nothing about the size of $L$ originally.
    To add to this, does the converse hold, i.e. if $d(K,L) = 1$ then are $K$ and $L$ identical? I think so.

  3. It is worth noting that $\tilde L$ is defined as the linear image of $L$, i.e. $$\tilde L = \alpha L = \{\alpha z : z\in L\}$$ where $\alpha \in\mathbb{R}^{+}$ right? This means $\tilde L ⊂ K ⊂ \tilde L$ can be written equivalently as $\alpha L ⊂ K ⊂ d\alpha L$ which gives $$\frac{K}{d\alpha} ⊂ L ⊂ \frac{K}{\alpha} \implies \tilde K \subset L\subset d\tilde K$$ where $\tilde K = \frac{K}{d\alpha}$. So can we conclude that $d(K,L)$ is symmetric, i.e. $d(K,L) = d(L,K)$ for all $K,L$? This is indeed a desirable property, I would not want the distance between two symmetric convex bodies to depend on the order in which they are chosen as arguments to $d(\cdot, \cdot)$.

  4. If $d(K,L) = \beta$, and $d(L,M) = \gamma$, what can we say about $d(K,M)$? Here are my thoughts, please let me know if this makes sense:
    From the definition, we know that there exist linear images $\tilde L, \tilde M$ of $L,M$ respectively such that $$\tilde L\subset K\subset \beta\tilde L \text{ and }\tilde M \subset L\subset \gamma\tilde M$$ hold. Since $\tilde M$ is some linear image of $M$, we might as well write $\tilde M \subset L\subset \gamma\tilde M$ as $\tilde M \subset \tilde L\subset \gamma\tilde M$ by scaling $\tilde M$ by an appropriate factor (the one with which you would relate $L$ and $\tilde L$). This brings us to: $$\tilde M \subset \tilde L \subset K \subset \beta \tilde L \subset \beta\gamma\tilde M \implies \tilde M \subset K\subset \beta\gamma\tilde M\implies d(K,M) = \beta\gamma$$ So $d(\cdot,\cdot)$ is multiplicative. Not to mention, this is a little weird and contrary to the notion of distance (between two points) that we are familiar with in $\mathbb{R}^n$.

  5. On Pg.9 of the attached reference (below), it is written that the distance between the cube $K = [-1,1]^n$ and the Euclidean ball $B = B^n_2$ in $\mathbb{R}^n$ is at most $\sqrt{n}$. $d(K,B) \le\sqrt{n}$ makes sense because the largest ball inside the cube has radius $1$, while the ball that circumscribes the cube has radius $\sqrt{n}$. Why does the author say "at most" in place of "exactly"? Is it possible that $d(K,B) < n$? I think $d(K,B) = n$.

  6. Are there any other interesting properties of $d(\cdot,\cdot)$ that you can think of? These are all the ones that came to my mind.

  7. A lot of times it's easier to understand new concepts with examples. It'd be extremely helpful if someone could provide some examples (in the usual $\mathbb{R}^2$,$\mathbb{R}^3$ as well as in $\mathbb{R}^n$ for $n\ge 4$) of bodies $K$ and $L$, along with $d(K,L)$ and the thought that went into computing the same.

Thanks a lot!


References:

  1. Lecture 2 (Pg. 8-9) of these notes.
$\endgroup$
3
  • 1
    $\begingroup$ Nice post. Happy new year $43\cdot 47$. $\endgroup$
    – mathproof
    Dec 31 '20 at 5:17
  • 1
    $\begingroup$ I just want to say I had so much fun answering your question, I mentioned it in a recent meta post of mine as a question that opens doors to new parts of mathematics. Just want to say there's a nice link between inequalities between distances for $l_p$ balls , and Sobolev-type inequalities for PDE. It goes via the Brunn-Minkowski inequality and the Prekopa-Leindler inequality, and it was fascinating to get this connection from your otherwise unrelated topic. $\endgroup$ Jan 4 at 6:37
  • $\begingroup$ That's really cool! Thanks :) @TeresaLisbon $\endgroup$ Jan 4 at 6:39
5
+100
$\begingroup$

Two convex bodies $A,B \subset \mathbb R^n$ are called affinely invariant if there exists a matrix $M$ of square dimension $n$ and a vector $v \in \mathbb R^n$ such that $A = MB + v$. That is, $A$ is $B$ scaled by $M$, and then shifted by $v$. Since both $A$ and $B$ have non-empty interior(that's what a convex body is) then $M$ will be invertible, so this is a symmetric relation.

For example , any two parallelograms are affinely invariant, by scaling the sides appropriately , rotating if required then shifting.

$B$ is called a linear image of $A$, if there exists a matrix $M$ such that $MB = A$. Again, we are dealing with convex bodies so $M$ will be invertible.

Note that the only differences is that if $A$ is a linear image of $B$ then both will be "centered" around the same point.

An alternate definition for the distance $D$ may be provided as follows : given two symmetric convex bodies $K$ and $L$, shift them both so that their centers are at the origin. Then : $$ d(K,L) = \inf_{T \textrm{ linear transformation}} \inf \left\{a \cdot b : \frac 1a K \subset TL \subset bK\right\} $$

Try to prove the equivalence. If you cannot prove it, then just assume it for the following discussion.


This definition is inspired from the Banach-Mazur distance between two normed spaces. Essentially, you want the best linear transformation which kind of brings two normed spaces as close as possible. The best you can do is if they were isometrically isomorphic i.e. a linear transformation took one set to the other while preserving distances. But this doesn't always happen, so the best way to do it then specifies a distance, on the spaces of $n$-dimensional normed linear spaces up to isometric isomorphism, which is basically what identical means in the context above.


(i)

Since scaling is an affine transformation, the distance does not depend upon either the size of $L$ or $K$. It only depends on their respective shapes. For example, when we talk about the distance between a square and a cirle, we are only thinking about the shapes and not about the sizes. Can you prove that a square and a circle are not identical?


(ii)

Now, identical in the text refers to identical up to affine invariance.

So, $A$ and $B$ being identical implies $d(A,B) = 1$. This is obvious, since $B \subset B \subset B$ where $d =1$ and $B$ is a linear image of $A$.

Conversely, if the distance between two convex bodies is $1$, then one is a linear image of the other and they are identical.


(iii)

Indeed, the distance is symmetric, for the reason you mention. You can try to prove it from the definition in my answer.


(iv)

The distance is not multiplicative, it is sub-multiplicative. The problem is basically with the last implication : sure $\tilde{M} \subset K \subset \beta \gamma\tilde{M}$, but this does not imply that $\beta \gamma$ is the smallest number with this property, so $d(K,M) \boxed{\leq} \beta \gamma$, and it very well could be smaller. Just like how it is with numbers (equality in the triangle inequality implies something about the numbers), equality of the kind $d(K,M) = d(K,L)d(L,M)$ should imply something about $K,L,M$, but I am not sure what this relation is.


(v)

The author's exact paragraph is this :

Our observations of the last lecture show that the distance between the cube and the Euclidean ball in $\mathbb R^n$ is at most $\sqrt n$. It is intuitively clear that it really is $\sqrt n$, i.e., that we cannot find a linear image of the ball that sandwiches the cube any better than the obvious one. A formal proof will be immediate after the next lecture.

The thing is, just like you have done in part $4$, finding a covering of one body by another scaled, doesn't automatically make that covering the best one!

To justify the author, why is the distance atmost $\sqrt n$? To see this, it is enough to show that the unit square $\{x : |x_i| \leq 1 \ \ \forall i\}$ contains the unit sphere centered at zero $\{x : \|x\| \leq 1\}$ , and is contained the unit sphere scaled by $\sqrt n$.

Both of these are easy exercises.

But this is just one covering. What if there's a better covering, which gives a better value for $d$? This is intuitively obvious when we think about it, but the proof involves the notion of a maximal ellipsoid contained in a convex body. In fact , it is true that the distance is $\sqrt n$ : this comes from comparing the maximal ellipsoids for the square and the sphere.

But again, why ellipsoids? The answer is simple : an ellipsoid is basically a linear image of the unit sphere. Any linear transformation is characterized by what it does with the unit ball i.e. which ellipsoid it produces. So looking at a convex figure, and the linear transformation associated to distances, is like thinking about each convex figure as an $n$-dimensional normed space in its own right, and the respective "unit balls" which are then ellipsoids. The best fit ellipsoid is then the best "unit-ball" approximation of a convex figure, so studying a convex body kind of comes down to studying this maximal ellipsoid.


(vi)

There are a few desirable things : taking the logarithm of $d$ provides a (usual) metric among isomorphism classes of normed linear spaces in $\mathbb R^n$. It is nice to know that this metric space is compact, so basically given an $\epsilon>0$ , you can find a finite set of spaces so that every space is at most $\epsilon$ far away from that. This is like saying that this finite set "approximates all possible shapes" very well.

You can also prove that any convex body is at most $n$ away from the unit square, in this distance. Thus, by sub-multiplicativity, any two convex bodies are at most $n^2$ apart in this metric. Try this exercise for yourself.

John's theorem is that any convex body is in fact at most $\sqrt n$ away from the unit sphere. This is more difficult than the exercise above.

Gluskin's theorem states that there is a universal constant $C>0$ such that for each $n$, one can find two convex bodies that are at least $c \sqrt n$ apart. This took some effort as well.

Apart from that, I can't really say anything about $d$ being very special. In the same lecture notes, you will find however, that if as a polytope gets closer to a ball in distance, its number of faces increases exponentially fast. Basically, approximating a ball by a polytope in this distance, you'd require exponentially many faces in the required distance.

Finally, imagine that some property was "continuous" with respect to $d$ : that is, if a space has this property and another space is very close to it, then that space also has the property. This is nice, right?

Turns out one such property is called $B_n$-convexity. I don't want to go into the definition, but a space is $B_n$-convex, if there is an $\epsilon>0$ such that given any $n$ elements of unit norm in the space, you can add/subtract them from one another , using each one exactly once, so that you can travel at least $\epsilon n$ distance away from the unit sphere.

One can show that the Euclidean ball has this property . The unit square does not : if I take the usual basis coordinate vectors, and add/subtract them in any order, I will always land up on a corner of the square, never outside it.

Now, it turns out that $B_n$ convexity is nice. More precisely, for any $B_n$-convex body $X$ you can find a $\lambda_n(X) > 1$ such that any space that has distance less than $\lambda(X)$ from $X$ , is also $B_n$ convex.


(vii)

It is difficult to work with two convex bodies in general, because it is difficult to justify equality, but one can find coverings that at least provide upper bounds.

For example, think about the $p$ and $q$ balls, i.e. $\sum |x_i|^p \leq 1$ and $\sum |x_i|^q \leq 1$ for $1 \leq p,q \leq 2$. Can you use the Holder inequality to find a bound on the distance between these balls?

Apart from this, there's not really much that can be done : even simple upper and lower bounds are difficult, forget about actual values.

One can do asymptotic analysis : for large $n$, what is the maximal distance of a convex body from another fixed one? For the unit square, polynomial upper and lower bounds are available.

Both are difficult to show in general. Techniques include randomizing(!) the selection of convex bodies, which is what leads to Glushkin's proof. Then, there's a "dual"-realization of every convex body, which kind of "flips" problems around : if you can't deal with the body at hand, dualize.

Then there's a result of Szarek-Talagrand, which is basically a nice approximation-type result for the minimal ellipsoid, along with the Sauer-Shelah lemma, which kind of provides lower and upper bounds of intersections of a set family with another fixed set. These results are all beyond my technical ability , though, and I assume that for your further reading of the document, this is all you will need to know about $d$ : neither is it explicitly calculated for a pair in the document (other than between square and ball) nor is it much expounded on.


EDIT : Suppose that $d(K,L) = \alpha$. Then there is a linear image of $L$, call it $ML$ for a matrix $M$ (which is invertible as I mentioned earlier) such that $ML \subset K \subset \alpha ML$.

Then, consider the linear image of $K$ given by $M^{-1}K$. Note that we can apply $M^{-1}$ to all sides of the containment (this is because if $f$ is any function and $S \subset T$ then $f(S) \subset f(T)$ can be easily proven) to get $L \subset M^{-1}K \subset \alpha L$ (the $M^{-1}$ commutes with $\alpha$).

Note that $L \subset M^{-1}K$ and $M^{-1}K \subset \alpha L$, which upon scaling by $\frac 1 \alpha$ (this is also a function, so the same logic applies) gives $\frac{1}{\alpha} M^{-1}K \subset L$. Therefore, we have : $$ \frac{1}{\alpha} M^{-1}K \subset L \subset \alpha \left(\frac 1 \alpha M^{-1}K\right) $$

Now, the linear image $\hat{K} = \frac 1{\alpha}(M^{-1}K)$ satisfies $\hat{K} \subset L \subset \alpha \hat{K}$. Thus, we get $d(L,K) \leq \alpha$ (CAREFUL : This does not imply equality because we don't know if there's a number that is smaller than $\alpha$ that does this).

But then, we've proved that $d(K,L) \geq d(L,K)$. Just switching the roles of $K$ and $L$ (literally switching every $K$ with $L$ and $L$ with $K$ in the argument above) gives us $d(L,K) \geq d(K,L)$ and therefore combining the two, $d(K,L ) =d(L,K)$ is clear.

$\endgroup$
9
  • 1
    $\begingroup$ In the definition of affine-invariance, how did you show that $M$ is invertible? I wasn't able to follow the argument. I feel it has something to do with the fact that $\det$ is related to the volume. $\endgroup$ Jan 4 at 12:31
  • 1
    $\begingroup$ @strawberry-sunshine Yes. If $M$ is not invertible, then it is not of full rank, so $MB$ will be contained in a subspace of dimension less than $n$, but then any such subspace has zero volume, which $A$ does not. So $A$ cannot be contained in that subspace, so $MB \neq A$. Thus, $MB=A$ implies $M$ is invertible. $\endgroup$ Jan 4 at 12:33
  • 1
    $\begingroup$ To talk about the multiplicative nature, instead of $d(K,M) = d(K,L)d(L,M)$ can we say that $$d(K,M) \leq d(K,L)d(L,M)$$ Also, I'm not sure how you define sub-multiplicative. $\endgroup$ Jan 4 at 13:55
  • 1
    $\begingroup$ @strawberry-sunshine That's exactly what sub-multiplicative means : $d(K,M) \leq d(K,L)d(L,M)$ for all convex symmetric bodies $K,L,M$. Your proof is correct. $\endgroup$ Jan 4 at 14:48
  • 1
    $\begingroup$ Sorry to bring this up so late, but I think my proof of $d(K,L) = d(L,K)$ uses a very special linear transformation. Perhaps you could help me complete that proof? $\endgroup$ Jan 15 at 15: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.