mg.metric geometry - Problem equivalent to "largest square in a cube"

When studying this problem in the general case, i.e. $m$-dimensional cube inside $n$-dimensional cube for $m<n$, it might make sense to look at small examples to gain some intuition. From the small examples (largest square in (hyper)cubes) one could get the impression that the coordinates of the optimal solution are always rationals and hence the optimal edge length are always square root of rationals. In this post I argue that this is not the case in general.

Here is how your formulation as an optimization problem generalizes: Let $S$ be a set of half of the $2^m$ vertices of the m-cube of diagonal lenght 2 centered at the origin such that $S cup {-s : sin S}$ is the entire set of vertices. Now find $2^{m-1}$ unit-vectors in $mathbb{R}^n$ such that each pair of them has the same vector product as a corresponding pair in $S$, and such that the absolute value of their coordinates in minimized.

For example for m=3 one can take as $S$ every other vertex of the cube, such that they form a regular tetrahedron (see picture by Kepler), and then for each pair there vector product would have to be $-frac{1}{3}$

One potential problem with this formulation as optimization problem in practice is that the number of variables is $n2^{m-1}$ and there are $frac{2^{m-1}(2^{m-1}+1)}{2}$ quadratic equations.

Together with this optimization formulation and methods described in http://arxiv.org/abs/1407.0683 I calculate some cases $f(m,n)$ for small $m$ and $n$. There is some numerical optimization involved, so it is not a formal proof that the following result is optimal, but I obtain exact symbolic values for the coordinates and it is certainly a lower bound.

On mathworld the cases $f(1,n)$ and $f(2,n)$ are explained, so the smallest cases that seem to be unknown are $f(3,n)$. The cases $f(3,4)$ and $f(3,5)$ are also mentioned in Sloane's oeis: A243309, A243313 .

---

The 8 vertices of a largest 3-cube inside $[0,1]^4$ have the following coordinates:

$$(1, 0, 1-a, b),(1, 0, b, 1-a), (0,c,1-d, 0), (0,c, 0, 1-d),(1, 1-c, 1,d), (1, 1-c,d, 1), (0,1, 1-b, a),(0, 1, a,1-b)$$

where $a,b,c,d$ are algebraic numbers of degree $4$, with the these minimal polynomials and decimal approximations:

$$begin{align*}aquad&16x^4 + 8x^3 - 23x^2 + 14x - 2& 0.204901553506651293143\ bquad&16x^4 - 24x^3 + 25x^2 - 14x + 1& 0.082734498297453867827\ cquad&8x^4 - 32x^3 + 45x^2 - 30x + 1& 0.035139649420907685891\ dquad&4x^4 - 4x^3 - x^2 + 4x - 1& 0.287636051804105160970 end{align*}$$

This gives a edge length s, which hast the following minimal polynomial:

$$4x^8 - 28x^6 - 7x^4 + 16x^2 + 16$$

and $1.007434756884279376098253595231$ as decimal approximation.

---

The 8 vertices of a largest 3-cube inside $[0,1]^5$ have the following coordinates:

$$(1, e, 0, e, 0), (1, e, 0, 1, 1-e), (0, 0, e, 0, e), (0, 0, e, 1-e, 1), (1, 1, 1-e, e, 0), (1, 1, 1-e, 1, 1-e), (0, 1-e, 1, 0, e), (0, 1-e, 1, 1-e, 1)$$

where $e=sqrt{frac{3}{2}}-1approx 0.224744871391589049098$

This gives as edge length $sqrt{11-8sqrt{frac{3}{2}}}approx 1.09637631717731280407593110$.

---

The 8 vertices of a largest 3-cube inside $[0,1]^6$ all lie on the vertices of (a diagonal section of) the 6-cube:

$$(0, 1, 1, 0, 1, 0), (0, 0, 0, 1, 1, 1), (1, 0, 1, 0, 0, 1), (1, 1, 0, 1, 0, 0), (1, 0, 0, 1, 0, 1), (1, 1, 1, 0, 0, 0), (0, 1, 0, 1, 1, 0), (0, 0, 1, 0, 1, 1)$$

and this gives an edge length of $sqrt{2}approx 1.414213562373095048$.

• Next co.combinatorics - Random Alternating Permutations
• Previous at.algebraic topology - De Rham cohomology and antiderivatives