18
$\begingroup$

Let $C_d$ be a unit edge-length cube in $d$ dimensions. I would like to orient it ("tilt" it) so that the vertical (last) coordinates of its $2^d$ vertices are maximally separated, in the sense that the minimum vertical distance between any two vertices is maximized over all orientations.

For $C_2$ (in standard orientation, edges parallel to Cartesian axes), tilting $\arctan \frac{1}{2} \approx 26.6^\circ$ separates the vertices by $\delta=1/\sqrt{5} \approx 0.447$:


         


For $C_3$ (in standard orientation), I believe that rotating the vector $(0,0,1)$ to lie on the vector $(\frac{1}{4},\frac{1}{2},1)$ results in a vertex separation of $\delta=1/\sqrt{21} \approx 0.218$:


         
My question is:

Q. What is the generalization to $C_d$ for $d>3$? What is the largest vertex separation $\delta$ achievable? Can one always achieve a uniform vertex separation (the same $\delta$ between each vertically adjacent pair), as in $C_2$ and $C_3$?

$\endgroup$
6
$\begingroup$

Robert Israel's answer is best possible.

As pointed out there, the problem is equivalent to finding a vector in $\mathbb{R}^d$ with minimal separation $1$ among sums of subsets of entries, and with the least possible length ($\ell_2$ norm). The vector Robert constructed, after rescaling to make the separation $1$, is $v_d=[2^0,2^1,\dots,2^{d-1}]$. Clearly this has the smallest possible $\ell_1$ norm.

It turns out that it also has the smallest possible $\ell_2$ norm, but for $d>3$ not the smallest $\ell_\infty$ norm.

Proof. It is a straightforward consequence of these 2 facts:

  1. Lemma. The following equality holds in $\mathbb{Z}[x_1,\dots x_d]$:

$$\sum_{S,T\subseteq I_d}(x_S-x_T)^2=C_d \sum_{i=1}^d x_i^2$$

where $I_d=\{1,2,\dots d\}$, $\displaystyle x_S=\sum_{i\in S} x_i$ and the positive integer $C_d$ depends only on $d$.

  1. if $x=v_d$ then $\{x_S\}=\{0,1,2,\dots 2^d-1\}$ clearly has the tightest possible packing of values (among vectors with separation $1$, and uniquely up to permutations) and therefore must minimize the left hand side in the lemma.

Proof of Lemma. There are 16 equally frequent cases for the occurrence of $x_ix_j$ in $(x_S-x_T)^2$:

$$\begin{array}{@{}l|l|l|c|c@{}} \mbox{case} & \in S & \in T & x_S-x_T & x_ix_j \text{ coef in }\\ & & & & (x_S-x_T)^2\\ \hline \mbox{1} & \_ & \_ & \cdots & 0 \\ \mbox{2} & i & \_ & x_i\cdots & 0 \\ \mbox{3} & j & \_ & x_j\cdots & 0 \\ \mbox{4} & i,j & \_ & x_i+x_j\cdots & 2 \\ \mbox{5} & \_ & i & -x_i\cdots & 0 \\ \mbox{6} & i & i & \cdots & 0 \\ \mbox{7} & j & i & x_j-x_i\cdots & -2 \\ \mbox{8} & i,j & i & x_j\cdots & 0 \\ \mbox{9} & \_ & j & -x_j\cdots & 0 \\ \mbox{10} & i & j & x_i-x_j\cdots & -2 \\ \mbox{11} & j & j & \cdots & 0 \\ \mbox{12} & i,j & j & x_i\cdots & 0 \\ \mbox{13} & \_ & i,j & -x_i-x_j\cdots & 2 \\ \mbox{14} & i & i,j & -x_j\cdots & 0 \\ \mbox{15} & j & i,j & -x_i\cdots & 0 \\ \mbox{16} & i,j & i,j & \cdots & 0 \end{array}$$

the total coefficient of $x_ix_j$ over all the cases is 0. Therefore $\sum_{S,T\subseteq I_d}(x_S-x_T)^2$ only contains square terms and by symmetry must then be a multiple of $\sum_{i=1}^d x_i^2 \quad\blacksquare$

Regarding the fact that $v_d$ above is not minimal $\ell_\infty$-wise, counterexamples are provided via the Atkinson-Negro-Santoro sequence:

$d=4: [3,5,6,7]$

$d=5: [6,9,11,12,13]$

$d=6: [11,17,20,22,23,24]$

etc.

$\endgroup$
1
  • $\begingroup$ I should mention that the Atkinson-Negro-Santoro derived sequences mentioned above are by no means the best in the $\ell_\infty$ metric. For example $[39,59,70,77,78,79,81,84]$ is a better one for $d=8$. $\endgroup$ Feb 14 at 13:28
17
$\begingroup$

Given a unit vector $u \in \mathbb R^d$, the "heights" of vertices of the $n$-cube where $u$ is regarded as the vertical direction are the sums of subsets of the entries of $u$. Thus the minimum separation is the minimum difference between the sums of two distinct subsets of these entries. If you take $$u = [1,2,\ldots,2^{d-1}]/\sqrt{1^2 + 2^2 + \ldots (2^{d-1})^2} = \sqrt{\dfrac{3}{4^d-1}}[1,2,\ldots,2^{d-1}]$$ you get uniform separation of $\sqrt{3/(4^d-1)}$.

$\endgroup$
4
  • $\begingroup$ Beautiful! $\mbox{}$ $\endgroup$ Jan 5 '15 at 2:01
  • 7
    $\begingroup$ Is it clear that uniform separation gives the optimal separation? (if you change the vector $u$, you might in principle destroy the uniformity, but obtain separation over a (reasonably substantially) larger range: if $u=[1,1,1,\ldots,1]$ then the image of the diagonal is of length $\sqrt d$, whereas here it is $O(1)$). This gives an upper bound for the minimal separation of $\sqrt d/2^d$, whereas here you have a lower bound of approximately $\sqrt 3/2^d$. $\endgroup$ Jan 5 '15 at 5:02
  • 1
    $\begingroup$ @AnthonyQuas: Good point! I can verify that for $d=2,3$, the max separation is achieved with uniform separation. $\endgroup$ Jan 5 '15 at 11:30
  • $\begingroup$ (Initially I accepted this lucid answer, but as Anthony points out, it doesn't necessarily solve the original question [not that Robert ever claimed it did].) $\endgroup$ Jan 6 '15 at 12:37
4
$\begingroup$

Just a small additional observation: It is possible to have nonuniform separations that are locally optimal but not globally. By local I mean that small perturbations of the $u$ vector do not improve the minimum separation.

Here are some examples in $d=3$ and $d=4$. The leftmost solutions are Robert's uniform separation solutions. In the others, the vertical order of the corners is different. (Corners are here numbered as bit strings, so in $d=4$ the four neighbors of origin are 1,2,4,8. In Robert's solution the vertical order is then same as numerical order. Edges from origin to its neighbors shown in red.) Locally optimal solutions in d=3 Locally optimal solutions in d=4

This means that one cannot characterize the optimal solution by local conditions on derivatives; the problem seems to have a "combinatorial" nature. If one first fixes the vertical order of all $2^d$ corners, then maximizing the separation can be formulated as a quadratic optimization problem. The remaining question is then, what is the best vertical order. But naively trying all possilities (e.g. all permutations of $2^d$ corners) will run into trouble with $d>4$, even if one applies some obvious symmetry reductions (without loss of generality, assume that corner 0 is lowest, and that its $d$ neighbors are in increasing numerical order).

With $d=4$, with some symmetry reductions, one needs to try only 252 different vertical orders (I can provide more details if needed), and the corresponding QP programs find three essentially different solutions (that are optimal for that particular vertical order). These three solutions are shown above, and the best is Robert's solution, so with $d=4$ we know it is the best possible.

(Additional note 27.9.2021: The number of possible vertical orders is even smaller. In fact it is A009997, and for $d=4$ there are just $14$ possible vertical orders of the corners.)

Perhaps there is an obvious geometric reason why the optimal separation has to be uniform?

$\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.