9

This question is adapted from another question on the 2008 Putnam test which asks specifically for the case when $n = 4$ and $k = 2$. The answer is $\dfrac{1}{2}\sqrt{\dfrac{n}{k}}$ but I am looking for a proof or other justification.

In many of the attempts I have seen for similar problems, the hypercube is scaled by a factor of $2$ and centered at the origin.

Here are some posts regarding the Putnam and a discussion for the case when $k = 2$ for all values of $n$.

I would also be grateful for intuition regarding why the maximum radius increases and decreases with square roots when the dimension of the ball and cube are changed.

Brad
  • 5,156
  • 2
  • 19
  • 50
  • 1
    As for the latter paragraph, think geometrically about fixing $k=1$ (where the ball is just a line segment) inside cubes of dimension $n=1,2,3$; there's more room for the ball to be longer. Then think about fixing $n=3$ (a regular three-dimensional cube) and looking inside for balls of dimension $k=1,2,3$ (line segment, circle, sphere): each one requires more room. – Greg Martin May 13 '14 at 23:13
  • @GregMartin Is there any reason to explain why they both increase as square root of the dimension? I'd imagine one proof of the statement could involve a base case that can be solved easily and then showing that if the dimension increases by $1$ on either the ball or the cube the answer changes accordingly. – Brad May 13 '14 at 23:27
  • 1
    A 'dimensional induction' argument seems unlikely, since the delta between $\sqrt{n}$ and $\sqrt{n+1}$ is more complicated than either term by itself. The core reason behind the square root factor (certainly the $\sqrt{n}$ piece) almost certainly arises in the fact that $\sqrt{n}$ is the length of the 'long diagonal' of the cube; you can probably see the $\sqrt{k}$ factor in the same way, by 'inverting' the problem ("what's the smallest $n$-dimensional cube a unit-radius $k$-ball can fit into?"). – Steven Stadnicki May 13 '14 at 23:52

1 Answers1

4

Like you said, it's easiest to consider the cube $[-1,1]^n$. I'll try to generalize the argument made in the link you submitted. We can assume by symmetry that the center of the sphere is the origin. Consider a $k-1$ sphere in $k-1$ spherical coordinates $\theta_i$ for $i=1,k-1$ with the range of $\theta_{k-1}$ being $[0,2\pi)$ and each other having range $[0,\pi]$, and a radius of $r$. For any orthonormal set $\{x^i\}_{i=1}^k$ of vectors in $\Bbb{R}^n$ the sphere can be parametrized as

$$S(\theta_1,\ldots,\theta_{k-1}) = r(\cos(\theta_1)x^1 + \sin(\theta_1)\cos(\theta_2)x^2+\cdots+\sin(\theta_1)\sin(\theta_2)\cdots\cos(\theta_{k-1})x^{k-1}\\ +\sin(\theta_1)\cdots\sin(\theta_{k-1})x^{k})$$

Each component of this must lie in $[-1,1]$. Let $x^j_i = \langle e_i,x^j\rangle$ be the $i$th component of $x^j$. The $i$th component of $S$ is then $$S_i = r(\cos(\theta_1)x^1_i + \sin(\theta_1)\cos(\theta_2)x^2_i+\cdots+\sin(\theta_1)\sin(\theta_2)\cdots\cos(\theta_{k-1})x^{k-1}_i\\ +\sin(\theta_1)\cdots\sin(\theta_{k-1})x^{k}_i)$$

This can be written as $r\langle x_i^T, \Theta\rangle$ where $\Theta = (\cos\theta_1,\dots, \sin\theta_1\dots\sin\theta_{k-1})$. We have $||\Theta|| = 1$. Thus by the identity $\langle x,y\rangle = ||x|| ||y|| \cos(\theta) $ and the fact that $\Theta$ ranges over the entire sphere (hence $\theta$ can take the value $0$) we get $r||x|| \le 1 $ in order to fit inside the interval $[-1,1]$ and this gives $$\sum_{j=1}^k (x_i^j)^2 \le \frac{1}{r^2}.$$ Summing over $i$ gives $$\sum_{i=1}^n\sum_{j=1}^k (x_i^j)^2 \le \frac{n}{r^2}$$ and by changing the order or summation and using orthonormality we get $$k\le \frac n {r^2}$$ or, as desired $$r\le \sqrt\frac{n}{k}.$$

Scaling back down to a unit cube gives the bound that you proposed.

EDIT:

I was originally wrong about the way of attaining the bound. Googling the answer I found an article which proved a slightly general result: it's an interesting read.

guest196883
  • 6,049
  • I only have a few questions. I understand that $\theta$ can take the value of $0$ but why do we use it? Is it because we need the maximum value of $\cos(\theta)$ so that our sphere is contained in our interval? And when you change the order of the sum you are essentially just summing $x\cdot x$ for $k$ times, right? Thank you for the help. – Brad May 15 '14 at 00:11
  • We need $1\ge r<x,y> = r|x||y|cos(\theta)$ for all attainable theta. So if it fits with the maximum value of $\cos(\theta)$ then it will with any other $\theta$. – guest196883 May 15 '14 at 00:13
  • And yes, we're summing the length of a unit vector $k$ times after changing the order. – guest196883 May 15 '14 at 00:14
  • Can you explain the reasoning behind the last statement about the hyperplane? – Brad May 15 '14 at 00:19
  • @Brad,see the paper I linked to. If you have any more questions let me know. – guest196883 May 15 '14 at 01:43
  • @guest196883 Sorry the link is dead. Do you know how to rigorously show that the maximum is attained? – No One May 25 '22 at 20:48