# Shortest path connecting two opposite points on a cube

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$?

• why close?! is it obvious? – Fedor Petrov Mar 16 '17 at 16:02
• In my opinion, this is a research level question. If you think this is off-topic, do you think the same about the following: "Does every central section of the unit cube have area at least 1?" – Ivan Izmestiev Mar 16 '17 at 16:14
• I do not understand the level, but want to know the answer. If @Mikhail Katz has it, I would like to read. – Arseniy Akopyan Mar 16 '17 at 16:18
• The OP is certainly a research mathematician (and a good one), so I trust his judgement completely. – Igor Rivin Mar 16 '17 at 16:52
• The internal proof works also for a generalization of Arseniy's statement onto d-dimensional skeletons of n-cube (it's combinatorially just a bit more interesting). I wonder if the external Anton's proof can be generalized onto skeletons. – Włodzimierz Holsztyński Mar 19 '17 at 9:29

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.

• "Note also that if one maps a unit cube centered at the origin by the exponential map it will cover the spherical cube" — Sorry, I do not understand the description of the map. – Arseniy Akopyan Mar 16 '17 at 17:50
• What does the "sphere with equator 4" mean? – Carl Schildkraut Mar 16 '17 at 21:52
• This is a bit hard to follow. Do I understand correctly that "sphere with equator $4$" means "$(d-1)$-dimensional sphere with equator of length $4$", that the "spherical cubes" are $(d-1)$-dimensional ones, corresponding to the facets of the cube in the original problem; and that a "short" map means one which never increases lengths? – Gro-Tsen Mar 16 '17 at 22:22
• @მამუკაჯიბლაძე "Short" means $1$-Lipschitz (see other comments). The $2$ comes from the fact that for equator length $4$, the inverse exponential map (=azimuthal equidistant projection) of a spherical cube covering $1/(2d)$ of the $(d-1)$-sphere maps inside the Euclidean $(d-1)$-dimensional unit cube. (And because both have an inscribed sphere of radius $1/2$, this is optimal.) "Symmetric" means the maps for the faces can be glued together. I agree that, as written, the answer leaves a lot to be filled in, but it is impressive. – Gro-Tsen Mar 17 '17 at 10:59
• Maybe one way to explain this answer is to start by a simpler lower bound, $\pi/2$, which can be obtained by simply projecting centrally (=gnomonically) the unit cube to the (inscribed) sphere of radius $1/2$: this map is $1$-Lipschitz so we get a lower bound of $\pi/2$ on the cube from the sphere. The surprising fact that Anton shows is that by essentially patching together $2d$ azimuthal equidistant projections, one for each side of the cube, we can get a bound of $2$. – Gro-Tsen Mar 17 '17 at 11:03

[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.)

• You say "clearly it is at most 2", which is surely false if $d \ge 3$. – TonyK Mar 17 '17 at 15:42
• I meant the smallest possible distance between two antipodal points. Fixed. – Gro-Tsen Mar 17 '17 at 18:05
• The mathematics was clear (of the question and of Anton's answer--I believe). It was hard only (so-to-speak) linguistically. The English was fine but the style was, well, next to impossible :-), – Włodzimierz Holsztyński Mar 17 '17 at 19:53

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.

• Yes, I think it is correct. – Arseniy Akopyan Mar 17 '17 at 10:47
• How does velocity enter the picture, and why does the argument only work for $n\ge4$? – მამუკა ჯიბლაძე Mar 17 '17 at 10:52
• @მამუკა ჯიბლაძე: if $n < 4$ then $2\sqrt n/2 < 2$. – TonyK Mar 17 '17 at 15:39

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).

• What does the triangle notation mean? – Todd Trimble Mar 19 '17 at 0:59
• "Triangle" notation stands for the "diagonal product" (the triangle or $\Delta$ reminds one of letter D for Diagonal). Richard Engelking used this notation in his classical textbook on general topology. It is used in the theory of categories in the context of the product of morphisms and objects: $\ f:X\rightarrow \prod_t Y_t = \triangle_t\, f_t\$ for the respective (coordinate) morphisms $\ f_t:X\rightarrow Y_t$. – Włodzimierz Holsztyński Mar 19 '17 at 1:12
• Thanks. I've never seen that notation used in the theory of categories, although the concept is of course quite familiar; I call it "tupling": mathoverflow.net/a/220213 – Todd Trimble Mar 19 '17 at 1:37
• What is the difference with Ivan's proof? – Arseniy Akopyan Mar 19 '17 at 8:13
• You are right. Ivan (and me after) did not noted that we always live in dimension one less. Thank you, I've got two beautifull solutions of the problem. – Arseniy Akopyan Mar 19 '17 at 9:00

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.

• Your model does not represent all geodesics. Consider the hexagonal path on the unit cube $\mathbb R^3$. – Arseniy Akopyan Mar 17 '17 at 9:50
• Acknowledged. There are also other unfoldings to consider. – მამუკა ჯიბლაძე Mar 17 '17 at 9:54

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.

• Looks like Anton is quicker than I today. Gerhard "Maybe It's In The Coffee" Paseman, 2017.03.16. – Gerhard Paseman Mar 16 '17 at 18:00

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.

• The question is about general antipodal points, not necessarily corners. – მამუკა ჯიბლაძე Mar 18 '17 at 5:30
• Good point - I've added a note. – user7868 Mar 18 '17 at 13:53