Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The "largest square in a cube" problem, which asks for the largest square inside a cube, has a solution as can be seen on this page, which also says that the general problem in higher dimensions is unsolved.

          MathWorld image.

The problem is equivalent to the following optimization problem: find two orthogonal unit vectors in $\mathbb{R}^3$ such that the maximum of the absolute values of all their coordinates is minimized. For the "largest square in a cube" problem to have the answer it does, this minimum should be $2/3$, i.e., it occurs when the coordinates are $(2/3,2/3,1/3),(1/3,-2/3,2/3)$ (or some coordinate permutation-cum-axis reflection of those). How would we show that this is indeed where the optimum occurs? This seems like it should be some really simple algebra, but it is eluding me.

More abstractly, this is asking for a pair of orthogonal unit vectors such that the maximum of their $\ell^\infty$-norms is minimized. What happens if we are trying to minimize the larger of the $\ell^p$-norms, $p > 2$? Does the minimizing value tend to $2/3$ as $p \to \infty$?

share|improve this question

2 Answers 2

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.

The smallest case that seems to be unknown is $f(3,4)$: the largest three-dimensional cube inside a four-dimensional cube.

I used the methods described in http://arxiv.org/abs/1407.0683 to calculate the case $f(3,4)$. 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.

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*}a\quad&16x^4 + 8x^3 - 23x^2 + 14x - 2& 0.204901553506651293143\\ b\quad&16x^4 - 24x^3 + 25x^2 - 14x + 1& 0.082734498297453867827\\ c\quad&8x^4 - 32x^3 + 45x^2 - 30x + 1& 0.035139649420907685891\\ d\quad&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.

share|improve this answer

You can reduce things a bit as follows. Suppose your two vectors are (a,b,c) and (x,y,z). Without loss of generality all of a, b and c are non-negative. Let's suppose that a is bigger than both b and c. Pick a third vector (u,v,w) orthogonal to both (a,b,c) and (x,y,z). If u is non-zero, then we can add a tiny multiple of (u,v,w) to (a,b,c) in such a way that the $\ell_2$ norm increases by a quadratic amount but the $\ell_\infty$ norm decreases by a linear amount. So after rescaling we have got a better example.

I won't go through all possible cases here, but we now know that either u is zero or (WLOG) a=b. The same proof also tells us that the maximum absolute value of x, y and z is attained twice. Probably it's fairly easy to show, after a little bit of case analysis, that this maximum is attained once for a positive value and once for a negative value, and in places 2 and 3. If that works, then we've got to (a,a,b) and (x,-y,y), with a bigger than b and x bigger than y in absolute value. This starts to look like a much more manageable optimization problem.

I don't guarantee that all this works, but I think it has a good chance.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.