# Joining the $2^k$ points of $\{0,1\}^k$ with the shortest tree

Let $$k$$ be a given positive integer, and then consider the unit hypercube $$\{0, 1\}^k \subset \mathbb{R}^k$$ (i.e., a $$k$$-dimensional "cube" in the well-known Euclidean space).
We need to join all the $$2^k$$ vertices of the stated hypercube by using a Euclidean Steiner tree, which is a spanning tree of the original vertices plus zero or more new vertices (Steiner points) such that we minimise the total Euclidean length of the edges in the tree. Denote the total length of these optimal trees as $$l_{min}(k)$$, for any integer $$k$$ (e.g., $$l_{min}(1) = 1$$, $$l_{min}(2) = 1 + \sqrt{3}$$, $$l_{min}(3) \approx 6.196$$, and so forth).

I wonder if solving the problem for every $$k$$ would be doable. I can only point out that an upper bound is trivially given by $$2^k-1$$ and that the trick to join $$2^{k-1}$$ pairs of opposite vertices does not improve the mentioned trivial solution as $$k$$ goes above $$3$$.

The figure below constructively shows that $$l_{min}(3) \leq 4 \cdot \sqrt{2} + 1$$.

P.S. For any $$k + 1$$ we can also recycle our best tree, double it and then spend a unit segment to join the two subtrees, so $$l_{min}(k+1) \le 1 + 2 l_{min}(k)$$.

P.P.S. The user Noam D. Elkies suggested in a comment of the present thread that $$l_{min}(k) < l_{upper}(k)$$ holds for every $$k>2$$ (since my value of $$l_{upper}(2)$$ is certainly bigger than the optimal solution of the square Steiner tree problem and thus $$l_{min}(3) < 4 \cdot \sqrt{2} + 1$$ follows). Noam was definitely right since in this paper the solution $$l_{upper}(2) = 1 + \sqrt{3}$$ is given (see Figure 2 from the Reference above).

• For starters you can improve on that tree by replacing each X by a Steiner tree for the four vertices of a square. Commented Jun 11 at 4:30
• @HenrikRüping, what little I can read of the paper I linked above (the first page) seems to suggest that this is incorrect in 3D (and presumably higher dimensions). Commented Jun 11 at 11:52
• An optimum Steiner tree always has all internal vertices $3$-valent and all angles equal to $120^{\circ}$ (even in higher dimensions). Commented Jun 11 at 13:15
• My guess is that the optimum is given by the tree with $2^k+2^{k-1} + \cdots + 2 = 2^{k+1}-2$ vertices, labeled by strings of the form $x_1 x_2 \cdots x_j$ with $x_i \in \{ \pm 1 \}$ and $1 \leq j \leq k$. Here $(x_1, \ldots, x_k)$ is the corresponding vertex of the cube, there are edges from $(x_1, \ldots, x_j)$ to $(x_1, \ldots, x_j, 1)$ and $(x_1, \ldots, x_j, -1)$, as well as a central edge from $(1)$ to $(-1)$, and all the angles are $120^{\circ}$. I don't know how to efficiently compute the coordinates of these vertices. Commented Jun 11 at 13:16
• Using the recursive construction of my previous comment it appears that $l_{min}(k) \le 1 + (2^{k-1}-1)\sqrt 3$. Commented Jun 11 at 14:40

I suspect that the optimum, for a cube of side length $$2$$, is $$2^k \sqrt{3} - 2 \sqrt{3}+2$$. Note that the optimum if we use edges of the cube is $$2 (2^k-1)$$, so this is better by a factor of roughly $$\sqrt{3}/2$$. (Side comment: For trees in the plane, there is a famous conjecture of Gilbert and Pollack (1968) that adding extra vertices can never decrease the length by a factor better than $$\sqrt{3}/2\approx 0.866$$. However, in $$k$$-dimensional space, better improvements are possible; Gilbert and Chung (1976) give examples with ratio approaching $$\tfrac{\sqrt{3}}{4-\sqrt{2}} \approx 0.669$$. It is peculiar that this particular $$k$$-dimensional problem seems to have the same ratio as the conjectured worst case of the $$2$$-dimensional problem.)

The form of the solution: I'll write $$\vec{e}_1$$,..., $$\vec{e}_k$$ for the standard basis of $$\mathbb{R}^k$$. The vertices of my cube are at $$x_1 \vec{e}_1 + \cdots + x_k \vec{e}_k$$ for $$x_1$$, ..., $$x_k \in \{ \pm 1 \}$$.

I will add an extra $$2$$-valent vertex denoted $$v( )$$ at the center $$(0,0,\ldots, 0)$$ of the cube. It will be at the midpoint of an edge, so we can erase it at the end, but it makes the notation more symmetric.

Combinatorially, my tree is the perfect binary rooted tree with $$1+2+\cdots + 2^{k-1}+2^k$$ vertices. A general vertex will be denoted $$v(x_1, x_2, \ldots, x_j)$$ where $$0 \leq j \leq k$$ and each $$x_i$$ is $$\pm 1$$. The root is $$v()$$ at position $$(0,0,\ldots,0)$$; the $$2^k$$ leaves are the vertices of the cube, with $$v(x_1, x_2, \ldots, x_k)$$ at $$(x_1, x_2, \ldots, x_k) = x_1 \vec{e}_1 + \cdots + x_k \vec{e}_k$$. In general, the children of $$v(x_1, x_2, \cdots, x_j)$$ are $$v(x_1, x_2, \cdots, x_j, 1)$$ and $$v(x_1, x_2, \cdots, x_j, (-1))$$.

I'll abbreviate $$v(\overbrace{1,1,\ldots,1}^j)$$ to $$v(1^j)$$. If I figure out the coordiantes of the $$v(1^j)$$, then the other vertices at level $$j$$ are obtained by switching the sign of the coordinates in all possible ways. Let $$\vec{u}_j$$ be the unit vector in direction $$v(1^j) - v(1^{j-1})$$ and let $$r_j$$ be the length of the edge $$(v(1^{j-1}), v(1^j))$$. So $$v(1^j)$$ is in position $$r_1 \vec{u}_1 + \cdots + r_j \vec{u}_j$$. The rest of this post is computing the values of the $$\vec{u}_j$$ and $$r_j$$.

Computing the $$\vec{u}_j$$ Look at the vertex $$v(1^j)$$ for $$1 \leq j \leq k$$. Its neighbors are $$v(1^{j-1})$$, $$v(1^{j+1})$$ and $$v(1^j (-1))$$. These four vertices lie in an affine two-plane $$P$$. By symmetry, the vertices $$v(1^{j-1})$$ and $$v(1^j)$$ are on $$\vec{e}_{j+1}^{\perp}$$ and $$v(1^{j+1})$$ and $$v(1^j(-1))$$ are reflections of each other over $$e_{j+1}^{\perp}$$. Thus, $$(\vec{u}_j, \vec{e}_{j+1})$$ is an orthonormal basis for $$P$$. We want $$\vec{u}_{j+1}$$ and $$-\vec{u}_j$$ to make a $$120^{\circ}$$ angle, so we should have $$\vec{u}_{j+1} = (\cos 60^{\circ}) \vec{u}_j + (\sin 60^{\circ}) \vec{e}_{j+1} = \frac{1}{2} \vec{u}_j +\frac{\sqrt{3}}{2} \vec{e}_{j+1} \tag{1}$$ Using $$(1)$$ recursively with the base case $$\vec{u}_1 = \vec{e}_1$$, we get $$\vec{u}_j = \frac{1}{2^{j-1}} \vec{e}_1 + \frac{\sqrt{3}}{2^{j-1}} \vec{e}_2 + \cdots + \frac{\sqrt{3}}{4} \vec{e}_{j-1} + \frac{\sqrt{3}}{2} \vec{e}_j. \tag{2}$$

Computing the $$r_j$$: We want to have $$r_1 \vec{u}_1 + \cdots + r_k \vec{u}_k = (1,1,\ldots,1) \tag{3}.$$ Extracting the $$j$$-th component of $$(3)$$, and using $$(2)$$, we get $$\begin{array}{rcll} r_1+\frac{1}{2} r_2 + \cdots + \frac{1}{2^{k-1}} r_k &=& 1 & \\ \frac{\sqrt{3}}{2} r_j + \frac{\sqrt{3}}{4} r_{j+1} + \cdots + \frac{\sqrt{3}}{2^{k-j+1}} r_k &=& 1 & \text{for}\ j \geq 2 \\ \end{array} \tag{4}$$ Solving $$(4)$$ recursively (starting at $$r_k$$ and working back to $$r_1$$), I get $$r_j = \begin{cases} 1-1/\sqrt{3} & j=1 \\ 1/\sqrt{3} & 2 \leq j \leq k-1 \\ 2/\sqrt{3} & j=k. \end{cases} \tag{5}.$$

The total length of the tree is \begin{align} 2 r_1 + 4 r_2 + \cdots + 2^k r_k &= 2(1-1/\sqrt{3}) + (4+8+\cdots+2^{k-1})/\sqrt{3} + 2^k \cdot 2/\sqrt{3} \\ &= 2^k \sqrt{3} - 2 \sqrt{3}+2. \end{align}

In case this formula is useful to anyone, for $$1 \leq j \leq k-1$$, we have $$v(1^j) = {\Big(}1-\frac{1}{2^{j-1} \sqrt{3}},\ 1-\frac{1}{2^{j-1}}, 1-\frac{1}{2^{j-2}},\ \ldots,\ 1-\frac{1}{4},\ 1-\frac{1}{2},\ 0,0,\ldots,0 {\Big)}.$$

As mentioned above, an optimal Steiner tree always has all interior vertices trivalent and all angles equal to $$120^{\circ}$$. See, for example, the first paragraph of Section 6.1 in

Hwang, Frank K.; Richards, Dana S.; Winter, Pawel, The Steiner tree problem, Annals of Discrete Mathematics. 53. Amsterdam: North-Holland. xi, 339 p. (1992). ZBL0774.05001.

So the remaining problem is to guess which trivalent tree with $$2^k$$ labeled leaves to use. This one seems like the best choice, but I have no idea how to prove that it can't be improved on.

• There are obviously equivalent trees by permuting the basis, but in higher dimensions it's also possible to rotate subtrees, so a proof of optimality has to take that into account. My intuition is that it would begin by considering how the vertices can be paired up and which plane the edges of a given pair must lie in. Commented Jun 11 at 18:10
• A tight upper bound and a very useful constraint (+1). On the other hand, I agree with Peter's point of view about the fact that we cannot easily disregard the chance that a multidimensional optimization would work as $k$ grows. I remember when I found the solution to a similar problem (the generalization of the well-known Nine dots problem in higher dimensions that considers trails instead of trees) and that time the clue was to swirl over and over in all the dimensions available. I'll wait a few days before voting for the best answer to let everybody take his time to work on this problem. Commented Jun 11 at 23:22