7
$\begingroup$

Let $C_n\subset\mathbb{R}^n$ be the $n$-dimensional cube with side $1$, and let $P_k$ be any $k$-dimensional plane, $k\leq n$. What is the maximal $k$-volume $V_{n,k}$ of the projection of $C_n$ on $P_k$?

Quite obviously, the minimal area should be $1$, obtained by taking $C_n = [0,1]^n$ and projecting it on $\{\mathbf{x}\in\mathbb{R}^n|x_{k+1}=\ldots=x_n=0\}$. I think the maximum should be obtained by projecting onto something orthogonal to one of the maximal diagonals of the cube, but I haven't found any proof of this, nor a formula for the volume so obtained.

I am particularly interested in the case $k = n-1$.


I got an upper bound for $V_{n,k}$.

We can inscribe $C_n$ in the $n$-ball of radius $\sqrt{n}$. The projection of such a sphere on a $k$-plane is a $k$-ball of radius $\sqrt{n}$ containing the projection of $C_n$. Its volume is $$V(n,k) = \frac{(n\pi)^\frac{k}{2}}{\Gamma\left(1+\frac{k}{2}\right)}\geq V_{n,k}$$ where $\Gamma$ is the Gamma function.

Conjecture: As $n,k$ become big we have the asymptotical behavior $V(n,k)\sim V_{n,k}$.

Would anyone care to try to prove this, if not to solve the initial problem?

Assuming the conjecture to be true, we have the asymptotical behavior for $V(n,k)$ given by the estimate of the volume of the $k$-ball for $k\gg 1$: $$V_{n,k}\sim V(n,k)\sim\frac{1}{\sqrt{\pi}}\left(\frac{2\pi e}{k}\right)^\frac{k} {2}n^\frac{k}{2}$$ as $n,k\rightarrow\infty$.

$\endgroup$
  • $\begingroup$ I wonder whether the determinant could help you here. $\endgroup$ – Bitwise Jul 29 '13 at 0:03
  • $\begingroup$ @Bitwise Well, it would be possible to calculate the volume of the projection of an $(n-1)$-dimensional face by projecting its edges and taking the determinant, but what about the intersections of the projections of the faces? I will maybe try to use your idea for some particular cases, though. $\endgroup$ – Daniel Robert-Nicoud Jul 29 '13 at 9:06
  • 1
    $\begingroup$ The "volume" of the intersection of the hypercube $[0,1]^n$ and the hyperplane $x_1 + \ldots + x_n = \lambda$ has a simple formula: $$\frac{\sqrt{n}}{(n-1)!} \sum_{k=0}^{\lfloor\lambda\rfloor} (-1)^k \binom{n}{k} (\lambda-k)^{n-1}$$ The $\lambda=\frac{n}{2}$ case should give you an lower bound of $V_{n,n-1}$. $\endgroup$ – achille hui Jul 29 '13 at 15:18
  • $\begingroup$ @achillehui Thank you. Could you write down a derivation of the formula, or refer to some paper/website where it's worked out? $\endgroup$ – Daniel Robert-Nicoud Jul 29 '13 at 15:25
  • $\begingroup$ Bitwise's trivial comment actually works for calculating the projection of the cube onto the complement of $(1,\dots,1)$. You can just take the faces and project them, and take into account that each point will be covered exactly twice. The calculation of the area gives something like $\sqrt n$. $\endgroup$ – Alexander Shamov Jan 14 '14 at 20:06
3
$\begingroup$

It happens that the area of the orthogonal projection of a unit $n$-dimensional cube onto a $k$ dimensional space is equal to the area of the projection of the cube on the $(n-k)$-dimensional orthogonal plane.

Hence for $k=n-1$ the answer is very simple: the maximal area of the projection is equal to the diagonal of the cube: $\sqrt{n}$.

Reference: https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/blms/16.3.278

$\endgroup$
  • $\begingroup$ That is nice! I suspected that relation to hold, but didn't know how to prove it. Thanks a lot for the reference! $\endgroup$ – Daniel Robert-Nicoud Apr 20 '18 at 16:13
1
$\begingroup$

As suggested by @AlexanderShamov, there is the following formula for $k=n-1$: let $u$ be a unit normal vector to the hyperplane, then the area of the projection is given by the formula: $$\sum_{i=1}^n|\left<u,e_i\right>|=\sum_{i=1}^n|u_i|=\|u\|_1$$ where $e_i$ denotes the $i$th basis vector (this is an adaptation of the more general formula (1.2) found in the paper Projection Bodies, by J. Bourgain and J. Lindenstrauss to our simple case). We want to find the extrema for this formula for $u\in S^n$. We'll use Lagrange multipliers: $$L(u,\lambda)=\|u\|_1-\lambda(\|u\|_2^2-1)$$ $$\frac{\partial}{\partial u_i}L(u,\lambda)=\operatorname{sgn}(u_i)-2\lambda u_i$$ where we assumed $u_i\neq0$. Thus $\lambda = \frac{1}{2|u_i|}$ must be true for all $i$, and by $\|u\|_2^2=1$ we get that $|u_i|=\frac{1}{\sqrt{n}}$. Thus the maximal value of the area of such a projection is: $$V_{n,n-1}=\frac{n}{\sqrt{n}}=\sqrt{n}$$ The problem for $k\neq n-1$ remains open.

$\endgroup$
1
$\begingroup$

For $k \ll n$ it looks like a reasonable idea to split the coordinates into $k$ blocks of length roughly equal $n/k$ and project onto the $k$-space generated by $e_{in/k}+e_{in/k+1}+\dots+e_{in/k+(n/k-1)},i=1,\dots,k$. This projection will be isometric to the cube $[0,\sqrt{n/k}]^k$ (since the whole thing decomposes into the direct sum of $k$ instances of taking the longest diagonal), so $V_{n,k} \ge (n/k)^{k/2}$. Obviously, for larger $k$ - namely, at scale $k \sim \lambda n$, $\lambda$ fixed - we need to allow non-equal lengths of blocks - with this modification this idea gives an exponential lower bound there.

A similarly straightforward upper bound is given by considering the diameter, which is $\sqrt n$, and using an isodiametric inequality. The gap between the two bounds grows exponentially in $k$, which doesn't look like a big deal up to scale $k \sim \lambda n$, at which point it confirms exponential growth of $V_{n,k}$, but leaves the precise exponent unknown.

However, at $k$ really close to $n$ something funny happens. The upper bound becomes hopelessly inefficient. In the regime $k = (1 - \frac{1}{r})n$, $r$ constant or large, I would split the coordinates into $n/r$ blocks of length $r$, take inside each $r$-dimensional subspace the largest $(r-1)$-dimensional projection, which has volume $\sqrt{r}$, and take the direct sum of $(n/r)$ of these, which gives $V_{n,k} \ge r^{n/2r}$. This glues well with the $k = \lambda n$ regime, and provides the correct value for $k = n-\mathrm{const}$. I don't have a nontrivial upper bound here.

Edit: Actually, by expressing the cube as an orthogonal sum of two cubes, and taking the corresponding projections onto direct sums, we get the following inequality:

$V_{n_1+n_2,k_1+k_2} \ge V_{n_1,k_1} V_{n_2,k_2}$

All of the lower bounds in my answer follow from this inequality, together with the known values $V_{n,1} = V_{n,n-1} = \sqrt n$.

$\endgroup$
  • $\begingroup$ I'm having some difficulty understanding what you mean when you speak of "splitting coordinates" and "writing the cube as the direct sum of two cubes". Could you elaborate, please? $\endgroup$ – Daniel Robert-Nicoud Jan 15 '14 at 13:41
  • $\begingroup$ Well, if we have a cube $[0,1]^{n_1+n_2} \subset \mathbb{R}^{n_1+n_2} \simeq \mathbb{R}^{n_1} \oplus \mathbb{R}^{n_2}$, and let's say we have two subspaces $V_i \subset \mathbb{R}^{n_i}, i=1,2$, $\dim V_i = k_i$. Then $\mathrm{pr}_{V_1 \oplus V_2} [0,1]^{n_1+n_2} \simeq \mathrm{pr}_{V_1} [0,1]^{n_1} \times \mathrm{pr}_{V_2} [0,1]^{n_2}$, i.e. the projection looks like a product of two projections of lower-dimensional cubes. Therefore, $V_{n_1+n_2,k_1+k_2} \ge V_{n_1,k_1} V_{n_2,k_2}$. $\endgroup$ – Alexander Shamov Jan 16 '14 at 14:41
  • $\begingroup$ ... So the first part of the answer is an application of this idea to products of one-dimensional projections, i.e. longest diagonals, and the second part is about using products of projections of dimension $k_i=n_i-1$. $\endgroup$ – Alexander Shamov Jan 16 '14 at 14:42
  • $\begingroup$ Ah, I see. Nice! +1 $\endgroup$ – Daniel Robert-Nicoud Jan 16 '14 at 17:28

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.