Return to Question

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}(k) = 1 + \sqrt{3}$ is given (see Figure 2 from the Reference above).

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

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}(k) = 1 + \sqrt{3}$ is given (see Figure 2 from the Reference above).

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}(k) = 1 + \sqrt{3}$ is given (see Figure 2 from the Reference above).

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 tree, which is just a set of line segments connected to each other so that none of them is isolated from the rest of this rigid structure.
Now, our goal is to find the minimum total (Euclidean) length, $l_{min}(k)$ of these optimal trees, for any integer $k$ (e.g., $l_{min}(1) = 1$, $l_{min}(2) \leq 2 \cdot \sqrt{2}$, $l_{min}(3) \leq 4 \cdot \sqrt{2} + 1$, 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 (e.g., from $l_{upper}(3) = 4 \cdot \sqrt{2} + 1$ we would get the upper bound $l_{upper}(4) = 2 \cdot(4 \cdot \sqrt{2} + 1)+1$ and so on).

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}(k) = 1 + \sqrt{3}$ is given (see Figure 2 from the Reference above).

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}(k) = 1 + \sqrt{3}$ is given (see Figure 2 from the Reference above).