Shortest path connecting two opposite points on a cube

Question

Is it true, that a path connecting two opposite points (i.e. such that the segment joining them passes through the centre of mass of the cube) on the surface of the $d$-dimensional unit cube (with $d>1$) is not shorter than $2$?

Answer 1

Consider the sphere with equator 4. Divide it into spherical cubes, the central projections from an inscribed cube.

Note that the exponential map from tangent plane to the sphere is short. Note also that if one maps a unit cube centered at the origin by the exponential map it will cover the spherical cube. It is easy to modify the map to get a short symmetric map from the unit cube to each spherical cube.

Joining all these maps, we get a short map fro the surface of the cube to our sphere, where the statement is evident.

Answer 2

[This is an attempt to explain the details in Anton Petrunin's answer to this question, since the comments suggest that a number of people have found it hard to understand as it was written.]

Let $C$ be the surface of the unit cube in $\mathbb{R}^d$ (for $d\geq 2$); when considered as a metric space, it is endowed with the distance-on-the-surface: so the goal is to show that the smallest possible distance between two antipodal points is $2$ (clearly it is at most $2$). Let $S$ be the ($(d-1)$-dimensional) sphere of radius $2/\pi$, also endowed with the intrinsic distance: certainly the distance between two antipodal points is $2$. So we are done if we can find a $1$-Lipschitz (="short", =which doesn't increase distances) map $h\colon C\to S$ mapping antipodal points to antipodal points. Note that this map does not have to be injective.

Let $Q_i$, for $1\leq i\leq 2d$ be the facets of $C$: each can be considered as a $(d-1)$-dimensional Euclidean unit cube with its usual distance; let $o_i$ be the center of $Q_i$. Let $K_i$ be the image of $Q_i$ by the central (=gnomonic) projection map $g\colon C\to S$ (i.e., if we imagine both $C$ and $S$ as centered at the origin of $\mathbb{R}^d$, then $g$ takes an element of $C \subseteq \mathbb{R}^d$ to the unique point of $S$ having that direction; note that $g$ is not the sought-after map $h$). So $K_i$ is a "spherical cube"; let $o'_i = g(o_i)$ be its center (the $o'_i$ are the $2d$ vertices of a regular cross-polytope on $S$, and the $K_i$ are the Voronoi cells of the $o'_i$, if we want).

We will define $h\colon Q\to K$ merely on one of the $Q_i$ (henceafter simply written "$Q$", and "$K$" is the corresponding $K_i$), commuting with all the symmetries of $(Q,K)$, so that we can use the same map on each $Q_i$ to get the sought-after $h\colon C\to S$.

Let $e\colon T_{o'} S\to S$ be the exponential map centered at the center $o'$ of $K$ (which can also be called the azimuthal equidistant projection): it takes a tangent vector to $S$ at $o'$ to the point of $S$ which is "in that direction, at that distance" (the direction and distance being given by the tangent vector). The map $e$ is $1$-Lipschitz (a fact which, for the sphere, is completely elementary, as the distance between two points can be expressed in polar coordinates around $o'$). Identify $T_{o'} S$ with the Euclidean space in which $Q$ lives, so that the origin is $o$ (center of $Q$): so now we have a map $e\colon Q\to S$ (taking $o$ to $o'$, and clearly commuting with all symmetries).

Note that this $e$ (restricted to $Q$) is a homeomorphism taking $Q$ to a set $e(Q)$ containing $K$: in other words, the distance in a given direction from $o$ to the boundary point of $Q$ in that direction is always at least the distance from $o'$ to the boundary point of $K$ in the same direction. (This is again an elementary fact that can be checked by comparing explicit formulæ for the gnomonic projection and the azimuthal equidistant projection; it is here that the choice of $2/\pi$ for the radius of $S$ is crucial.) So we can restrict $e$ to the inverse image $P := e^{-1}(K) \subseteq Q$ of $K$ (the azimuthal equidistant projection of a spherical cube: it looks like a kind of "puffy cube", tangent to $Q$ in the centers of its facets). Note that $P$ is convex. (I don't have an argument here, but it's surely not too difficult.)

What follows is an illustration of $P$ for $d=2$ (the boundary of $P$ is in red, the boundary of $Q$ is, of course, the black square):

This map still needs to be modified a little: let $h\colon Q\to K$ be obtained by composing the nearest point projection $Q\to P$ (which makes sense since $P$ is convex compact) with the exponential map $P\to K$ (restricted to $P$, as explained above, where it is a homeomorphism). So $h$ is $1$-Lipschitz (and not injective on all of $Q$, although it is a homeomorphism on $P$). Also, $h$ commutes with all the symmetries of $(Q,K)$ because the construction is completely symmetric. In particular, the various copies of $h\colon Q_i\to K_i$ match at the boundaries, so we get a map $h\colon C\to S$ as announced.

(Alternatively, instead of using the nearest point projection $Q\to P$, I think we can "truncate" the azimuthal projection: given a point in $x$ in $Q$, map it to the point in $P$ or $K$ which is in the same direction and at the same distance except if the distance exceeds the distance to the boundary, in which case map it to the boundary point in that direction. This avoids the argument that $P$ is convex but then makes it less clear that the map is $1$-Lipschitz.)

Answer 3

Take a path that joins the antipodes and concatenate it with its symmetric image. Get a centrally symmetric closed path on the boundary of the cube. If this path avoids one of the facets of the cube (and hence the antipodal facet as well), then we can project it to the boundary of the cube one dimension less and get a centrally symmetric path of at most the same length. If the path goes through all the faces, then its length is at least $2\sqrt{n}$ (apply the quadratic-arithmetic mean inequality to the components of the velocity vector). So, if $n \ge 4$, a path is either long or can be projected.

One has to deal with the $n=3$ case by hand, for example by using the development of the cube.

Answer 4

The impressive and beautiful @AntonPetrunin solution is external. Let me present an internal argument. The goal is to prove that the Euclidean length $\ |p|\ $ of any (rectifiable) path $\ p:[-\frac 12;\frac 12]\rightarrow F^{d-1}\ $ is at least $\ 2,\ $ where $\ p(-\frac 12) = -p(\frac 12),\ $ and $\ F^{d-1}\ $ is the boundary of $\ [-\frac 12;\frac 12]^{\,d},\ $ for every integer $\ d\ge2.$ (My solution will provide a little more).

Let $\ p\ :=\ \triangle_{k=1}^d\, p_k, $ where $\ p_1\ \ldots\ p_d\ $ are the coordinate functions. Define the set of the essential coordinates:

$$ D\ :=\ \{\, k : |\max p_k| = 1\, \} $$

and let $\ \delta:=|D|\ $ be the essential dimension; we see that $\ \delta\ge 2.\ $ Finally, define the essential projection

$$ q\ :=\ \triangle_{k\in D}\, p_k $$

The range of the essential path $\ q\ $ is contained in $\ F^{\delta-1},\ $ where $\ F^{\delta-1}\ $ is defined as the boundary of cube $\ [-\frac 12;\frac 12]^D.$ Of course $\ q(-\frac 12) = -q(\frac 12). $ Since $$ |p|\ge |q| $$

it is enough to prove that $\ |q|\ge 2$. Observe that $\forall_{k\in D}\, var(p_k)\ge 1 $ hence

$$ \sum_{k\in D}\, var(p_k)\ \ge D $$

Let us also consider the $\ell^1$-norm in Euclidean spaces, namely $\ ||x|| = \sum |x_k|.\ $ Let $\ ||q||\ $ be the $\ell^1$-length of $\ q.\ $ We see that

$$ ||q||\ =\ \sum_{k\in D}\, var(p_k)\ \ge D $$

Let's apply the comparison between the two norms in any $n$-dimensional euclidean space: $\ |x|\ge \frac{||x||}{\sqrt{n}}\ $ for arbitrary $\ n=1\ 2\ \ldots\ $. It follows that

$$\forall_{k\in D}\,\forall_{x\ y\in F^{\delta-1}: p_k(x)=p_k(y)}\quad |x-y|\ \ge \frac{||x-y||}{\sqrt{\delta-1}} $$

and $\ |q|\ \ge\ \frac{||q||}{\sqrt{\delta-1}} $ hence $\ |p|\ge|q| \ge \frac D{\sqrt{\delta-1}}.\ $ Thus,

THEOREM   $\ \forall_{d\ge 2}\ |p|\ \ge\ \frac D{\sqrt{\delta-1}} $

 

COROLLARY   $\ \forall_{d\ge 2}\ |p|\ \ge\ 2 $

REMARK   When considering above implication Thm => Cor, only $\ D=3\ $ makes you stop for a moment (unless you are a relative of John von Neumann).

Answer 5

This answer realizes the idea from the answer by Gerhard "Mentally Less Energetic" Paseman.

NB: as pointed out by the OP in the comment below, this answer is incomplete. I will think about adding other possible unfoldings into consideration.

The unfolding of the surface of the $n$-cube into the ($n-1$)-space is the union of $2n$ ($n-1$)-cubes (facets of the $n$-cube); they may be arranged in this fashion: one central ($n-1$)-cube, with vertices $(\pm\frac12,\pm\frac12,...,\pm\frac12)$, its shifts by $1$ and by $-1$ along each of the coordinate axes, and one more shift by $2$ in one of these directions.

Two general opposite points on the surface can be now represented as a point $(x_1,x_2,...,x_{n-1})$ inside the central cube (i. e. with $-\frac12\le x_i\le\frac12$, $i=1,...,n-1$) and the reflection of $(-x_1,...,-x_{n-1})$ in the hyperplane passing through $(1,0,...,0)$ perpendicularly to the first axis, i. e. the point $(2+x_1,-x_2,...,-x_{n-1})$ inside the cube shifted by $2$ in the positive direction along the first axis.

The distance thus is $\sqrt{\left(x_1-(2+x_1)\right)^2+\left(x_2-(-x_2)\right)^2+...+\left(x_{n-1}-(-x_{n-1})\right)^2}$ $=2\sqrt{1+x_2^2+...+x_{n-1}^2}$. Choosing different axes for shifts gives the numbers $2\sqrt{1+x_1^2+...+x_{i-1}^2+x_{i+1}^2+...+x_{n-1}^2}$, and shortest possible distance is the smallest among these numbers.

So evidently $2$ is the absolute minimum, attainable on arbitrary shifts of the center of a facet in a direction parallel to one of the edges of that facet (and nowhere else): the minimizing path follows that direction all the way.

Answer 6

While we wait for an official solution, here is a suggestion with which to play.

A version of this problem is the fly and the honey problem. The room in which antipodal points are taken (one fly, one honey) is a rectangular prism; unfolding the prism and using Pythagoras, one finds (since the antipodes are near edges) a path shorter than half the perimeter of the rectangle between the two points. This is because we can find a room with height h, length l, and distance d from the floor so that (l+2d)^2 + (2h)^2 is less than (l+h)^2. Of course, one only needs one unfolding to check.

For d (the dimension now) equal to 3, one considers two antipodal spots with z coordinates 0 and 1. One unfolds the cube onto the z-x plane and notes a z value of (-b) and (1+b) out of the possibilities for carrying the points to this plane by unfolding. One then has to observe (this is the hard part) that the point images have difference at least 2 in their x coordinate when this happens. For the other possible unfolding and positions one has to compute that the sums of the squares of the coordinate differences Is larger than 4. I leave this part to you.

For higher dimensions, it should be possible to show that any path projects down by one dimension to a not longer path in a similar example. Again I leave the implementation to the mentally energetic.

There is literature on similar problems for convex poly to pew, certainly in three dimensions and possibly higher. If a search term other than "antipodal metric" or "fly and honey" occur to me, I will add them in a comment later.

Gerhard "Problem Cornered But Not Captured" Paseman, 2017.03.16.

Answer 7

EDIT: As has been pointed out in the comments, this isn't an answer to the original question. It only works in a single specific case.

The distance from one corner to the opposite corner of a $d$-dimensional cube is always longer than the distance from one corner to the opposite corner of a $d-1$-dimensional cube. Suppose you have a piecewise-linear path from opposite corners of a $d$-diensional cube, i.e. from $(0, 0, ..., 0)$ to $(1, 1, ..., 1)$. Suppose your path is piecewise linear, suppose it consists of the straight-line path between some sequence of points $(0,0,...,0),(x_{1,1}, x_{1,2},...x_{1,d}), (x_{2,1}, x_{2,2},...x_{2,d}),$ $...,(x_{n,1},x_{n,2},...,x_{n,d}), (1,1,...1)$ for some $n$. Now consider the straight-line path between the alternative sequence of points $(0,0,...,0),(x_{1,1}, x_{1,2},...x_{1,d-1},0),$ $(x_{2,1}, x_{2,2},...x_{2,d-1},0),...,$ $(x_{n,1},x_{n,2},...,x_{n,d-1},0),$ $(1,1,...,1,0)$. This alternative path is obviously shorter. Thus, it is a shorter path between opposite sides of a $d-1$-dimensional cube.