12
$\begingroup$

In a unit square the biggest circle is of diameter 1.

In a unit cube I have reasoned that the biggest circle is $\sqrt{\frac{6}{5}}$

(EDIT:(Full solution: $r = \sqrt{\frac{n}{8}}$) This reasoning is wrong; there are larger circles, only read this section if you enjoy seeing me work out the radius of a specific non-maximal class of circles in hypercubes. See below for my working after seeing people's answers.)

In higher dimensions, I only speculate that the biggest circle has diameter $\sqrt{\frac{2n}{n+2}}$

My reasoning is as follows:

enter image description here

To find the plane on which the biggest circle would lie, it seems reasonable to pick the farthest two corners $(0,0,0), (1,1,1)$, and then pick the midpoint of the vertical edges $(1, 0, \frac{1}{2}), (0, 1, \frac{1}{2})$. This gives a rhombus with diagonals $\sqrt{3}$ and $\sqrt{2}$ (the diagonals of the cube and the square at height $\frac{1}{2}$, respectively), and side lengths all $\sqrt{1^2 + \frac{1}{2}^2} = \frac{\sqrt{5}}{2}$

Now, $(1, 0, \frac{1}{2}).(0, 1, \frac{1}{2}) = \frac{1}{4}$ so the cosine of the acute angle of the rhombus is $\frac{1}{4}/(\frac{\sqrt{5}}{2})^2 = \frac{1}{5}$, so the acute angle is $\cos^{-1}\left(\frac{1}{5}\right)$. The smallest distance between opposite sides (the height) of this rhombus is:

$$\begin{aligned} \frac{\sqrt{5}}{2}\cos\left(\frac{\pi}{2} - \cos^{-1}\left(\frac{1}{5}\right)\right) &= \frac{\sqrt{5}}{2}\left[\sin\left(\cos^{-1}(\frac{1}{5})\right)\right]\\ &=\frac{\sqrt{5}}{2}\sqrt{1 -\frac{1}{5^2}} \\ &=\sqrt{\frac{6}{5}}\end{aligned} $$

The circle centred at the centre of the rhombus has at most this diameter, since it will then meet the rhombus tangentially.

My reasoning is not rigorous, but here's how it extends to higher dimensions:

I presume the plane the circle lies on would include (wlog.) the diagonal of length $2$, $(0,0,0,0),(1,1,1,1)$

I also guess that the vectors $(1,0,\frac{1}{2},\frac{1}{2}),(0,1,\frac{1}{2},\frac{1}{2})$ define the plane. These have length $\frac{\sqrt{6}}{2}$, dot product $\frac{2}{4}$ and hence angle $\cos^{-1}(\frac{2}{6})$. The height would then be:

$$\begin{aligned} \frac{\sqrt{6}}{2}\left[\sin\left(\cos^{-1}\left(\frac{2}{6}\right)\right)\right] &=\frac{\sqrt{6}}{2}\sqrt{1 - (\frac{2}{6})^2}\\ &=\sqrt{\frac{8}{6}}\end{aligned}$$

And if this guess of a plane holds in dimension n: $$\begin{aligned} \left(1,0,\frac{1}{2},\frac{1}{2},\frac{1}{2},...\right)\cdot\left(0,1,\frac{1}{2},\frac{1}{2},\frac{1}{2},...\right) &= \frac{n-2}{4}\\ &= \left|\left(1,0,\frac{1}{2},\frac{1}{2},\frac{1}{2},...\right)\right|\\ &= \sqrt{\frac{n+2}{4}}\end{aligned}$$

gives angle $\cos^{-1}(\frac{n-2}{n+2})$

and height $\sqrt{\frac{n+2}{4}} \sqrt{1 - \frac{(n-2)^2}{(n+2)^2}}$

$= \sqrt{\frac{2n}{n+2}}$

So, on the assumption that this is a plane holding a circle of maximal diameter, the diameter would be $= \sqrt{\frac{2n}{n+2}}$, radius $= \sqrt{\frac{n}{4n+4}}$ so I could never fit a circle radius $\frac{1}{\sqrt{2}}$ in any hyper-cube.

I'm asking for either justification or correction of this method. Is it right to assume that the plane cuts out a rhombus in higher dimensions?

End of original question

As was pointed out by Mark Bennet, a maximal circle in a cube $[-1,1]^3$ lies in the plane through the origin normal to $(1,1,1)$ and has radius $\frac{\sqrt{6}}{2}$

enter image description here

Here, I try to generalise Mark Bennet's example: (Please read with a critical eye)

This plane intersects the cube at the six points whose coordinates have one $1$, one $-1$ and one $0$. These are the furthest points the plane reaches in the cube. The shortest lines between these points lie on the surface of the cube and can be expressed, symmetrically in the 3 coordinates, as $\pm(-1,t,1-t)$ with $ t \in [0,1]$ these lines make a hexagon with minimal distance $\sqrt{1+\frac{1}{2}^2 +\frac{1}{2}^2} = \frac{\sqrt{6}}{2}$ I've done this methodically so that I can generalise to higher dimensions.

In higher dimension n there are two cases:

n even:

In this case, the hyperplane through the origin normal to $(1,1,..)$ reaches all corners of the hypercube that have $\frac{n}{2} 1$'s and $\frac{n}{2} -1$'s. Now we must pick a basis for the plane in this hyperplane that contains the largest circle.

We can recover the circles given by @celtschk by using the basis vectors: $$\underbrace{(1,-1,1,-1\ldots,1,-1)}_{n}$$, and $$ \underbrace{(1,-1,1,-1\ldots}_{\frac{n}{2}} \underbrace{\ldots,-1,1,-1,1)}_{\frac{n}{2}}$$

That is, switching sign half way through so that they add to cancel the second half and subtract to cancel the first. Then the circle is given by:

$$\{(\underbrace{\cos\phi,-\cos\phi,\ldots}_{\frac{n}{2}}, \underbrace{\sin\phi,-\sin\phi,,\ldots}_{\frac{n}{2}})|0\le\phi\le 2\pi\}$$

(since $(\underbrace{1,-1,\ldots}_{\frac{n}{2}}0,0,\ldots)$ and $(0,0,\ldots\underbrace{-1,1,\ldots}_{\frac{n}{2}})$ are orthogonal, and $\phi = 0$ gives us their scaling.(largest scaling that fits in the cube))

which has radius $\sqrt{\frac{n}{2}}$

But can we pick a basis that gives a bigger circle?

n odd:

$\endgroup$
  • $\begingroup$ When n=3 : did you check that your rhombus gives a better surface for a circle, than the equilateral triangle that lies between A=(1, 1, -1), B=(-1,-1,-1) and C=(-1,1,1)? Each AB BC CA is on a face of the square, which makes it easy to compute the radius of the circle within this equilateral triangle. $\endgroup$ – Taamer Dec 17 '17 at 12:31
  • $\begingroup$ @Taamer That is equivalent to taking a regular hexagon with side $\sqrt 2/3$ for a unit cube. $\endgroup$ – Mark Bennet Dec 17 '17 at 12:35
  • $\begingroup$ @MarkBennet Actually, the circle within your hexagon seems bigger than the circle within my triangle. Nice pick! $\endgroup$ – Taamer Dec 17 '17 at 12:38
  • 1
    $\begingroup$ +1, because the question (what is the largest circle that will fit in an n-dimensional hypercube?) is really nice and I'd like to see a full answer. But I suggest you edit out your mistaken analysis to focus on the question itself. (We can always find it in the edit history if we need it.) $\endgroup$ – Nathaniel Dec 17 '17 at 14:17
  • 1
    $\begingroup$ From @MichaelBehrend's comment on my (non-)answer: See home.lu.lv/~sd20008/papers/essays/Hypercube%20[paper].pdf . $\endgroup$ – John Hughes Dec 17 '17 at 18:09
6
$\begingroup$

To make calculations easier, let's take a hypercube of side length $2$ centered at the origin; as is easily verified, the maximal radius of a circle in that cube equals the maximal diameter of a circle in an unit cube.

For even dimension, there's an easy to find circle with radius $\sqrt{n/2}$: $$\{(\underbrace{\cos\phi,\ldots,\cos\phi}_{\frac{n}{2}}, \underbrace{\sin\phi,\ldots,\sin\phi}_{\frac{n}{2}})|0\le\phi\le 2\pi\}$$

This already exceeds your conjecture, as for $n>2$ we have: $$\sqrt{\frac{n}{2}}=\sqrt{\frac{2n}{4}} > \sqrt{\frac{2n}{n+2}}\quad .$$

Interestingly, the "hexagon circle" described by Mark Bennet for the cube ($n=3$) also fits that formula, as then $$\sqrt{\frac{3}{2}} = \sqrt{\frac{6}{4}} = \frac{\sqrt{6}}{2}\quad.$$

However I suspect that for $n>3$ this is not the biggest circle you can find.

Here's another thought: The longest diameter in an $k$-dimensional hypercube is the diagonal of length $\sqrt{k}$ Now a hypercube with dimension $n=mk$ can be produced as Cartesian product of $m$ hypercubes of dimension $k$. The diagonals then give an inscribed hypercube of dimension $m$ and side length $\sqrt{k}$. Obviously any circle that can be fit in that inscribed hypercube can also be fit into the original hypercube. Therefore if we denote with $d(n)$ the maximal diameter of a circle that can be inscribed in an $n$-dimensional unit hypercube, then we have the relation $$d(mk) \ge\max\{d(m)\,\sqrt{k},\sqrt{m}\,d(k)\}$$

In particular, if $d(k)\ge \sqrt{k/2}$ then $d(mk)\ge \sqrt{mk/2}$.

Edit: In a comment to another answer, Michael Behrend linked to a paper that proves (under the reasonable assumption that the center of the maximal circle must be the center of the cube) that indeed the maximal radius of a circle inscribed in a unit hypercube is $\sqrt{n/8}$, which means the corresponding diameter is $\sqrt{n/2}$, in agreement with the lower bound implied by this answer for any dimension that is a multiple of $2$ or $3$.

$\endgroup$
  • $\begingroup$ This is the same circle I thought of when I saw the question. $\endgroup$ – John Dvorak Dec 17 '17 at 13:47
6
$\begingroup$

Note that if you take the cross section of a unit cube by a plane perpendicular to the diagonal joining opposite corners you get a regular hexagon of side $\frac {\sqrt 2} 2$. The inscribed circle has diameter $\frac {\sqrt 6}2$.

I would suggest this as a starting point for constructions in higher dimensions.

$\endgroup$
  • $\begingroup$ Thanks - it is remarkable how easy it was to miss this. $\endgroup$ – Christian Fieldhouse Dec 17 '17 at 12:46
  • $\begingroup$ @celtschk You are right and I've changed it. $\endgroup$ – Mark Bennet Dec 17 '17 at 13:16
  • $\begingroup$ As I just realized, the plane with the hexagon is not orthogonal to (1, 1, 1). We should fix this. $\endgroup$ – Taamer Dec 17 '17 at 14:57
  • $\begingroup$ @Taamer The hexagon shown in the current diagram in the question isn't, but I am explicitly constructing an orthogonal plane first. The vertices of the hexagon, which is regular, join the midpoints of adjacent sides. $\endgroup$ – Mark Bennet Dec 17 '17 at 14:59
  • $\begingroup$ @Taamer: You can easily see that there's a hexagon in that plane as follows: (1) There are 3 corners of the cube adjacent to the one at $(1,1,1)$; those define a plane. And so do the 3 corners of the cube adjacent to $(0,0,0)$. (2) The two planes I just described both are orthogonal to the vector $(1,1,1)$ for symmetry reasons. (3) Since they are parallel, there's another parallel plane right in between those two; it intersects each of the six edges connecting the six corners defining the two planes. The six intersection points form a hexagon. (4) For symmetry reasons, that hexagon is regular. $\endgroup$ – celtschk Dec 17 '17 at 15:06
3
$\begingroup$

This was essentially the Putnam 2008 B3 problem. Here's a link to the solutions for that test: link. It is proven there that for the more general problem of trying put a $k$ dimension ball inside an $n$ dimensional unit cube, the maximum radius of the ball is $\frac{1}{2}\sqrt{\frac{n}{k}}$.

$\endgroup$
0
$\begingroup$

Not an answer, but some idle musings:

"Is it right to assume...": no. It's not a bad idea to guess that this might be true, but only an actual proof will establish it.

If I were going to set about establishing it via calculus, I guess I'd use the cube $-1 \le x, y, z \le 1$, because then you merely have to optimize over the set of 2-planes passing through the origin, rather than the point $(0.5, 0.5, 0.5)$ (or the analogous thing in higher dimensions). Of course, the result you get needs to be scaled down by a factor of $2$.

The "obvious" way to parameterize the set of 2-planes is as $S^2 \times S^2$, taking the pair of unit vectors as a basis for the plane. This has two problems: one is that the pair $(v, v)$ doesn't actually determine a plane; the other is that if $(v, w)$ determines a plane $P$, then $(v, w')$ also determines $P$, where $w'$ is any other unit vector in $P$ (except $v$) determines the same plane. That means that $Area(v, w)$ won't have a strict minimum when $(v, w)$ is a basis for the ideal plane $P$, and that makes things messy.

The next most obvious way is to pick a unit vector $v$ and an orthogonal unit vector $w$, i.e., a point in the tangent plane to $S^{n-1} \subset \Bbb R^n$. Now optimizing the area function gets...well... messy.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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