Which polytopes are $01$-polytopes?

Question

Are there some basic criteria by which to check whether a polytope $P\subset\Bbb R^n$ is a $01$-polytope, that is, can be rotated and scaled to have vertices in $\{0,1\}^n$, maybe even by using higher-dimensional space? I am especially interested in necessary conditions.

In particuar, which of the regular or uniform polytopes is a $01$-polytopes? Here are some examples for which I know that they are:

• simplices (and also hyper-simplices) .
• $n$-cubes (and also demi-cubes).
• $n$-crosspolytopes.
• cartesian products of $01$-polytopes (e.g. certain prisms, duo-prisms, ...).

I know that polytopes with a 5-fold rotational symmetry are not $01$-polytopes, e.g. the regular dodecahedron or 600-cell, since they do not have an embedding with purely rational vertex-coordinates. I also read that the cuboctahedron is not a $01$-polytope, but I have no argument for that. What about the 24-cell?

Answer 1

When the 24-cell would be a 01-polytope, then its equatorial section, the cuboctahedron, would be too. And, iterating that argument, when the cuboctahedron would be a 01-polytope, then its equatorial section, the regular hexagon, would be too. Sure, the hexagon well can be inscribed into a cube by means of a single cut, but then it would intersect it mid-edge wise. Thus it isn't a 01-polytope. And therefore those other 2 neither.

--- rk

Answer 2

One necessary condition is that the set of distances between vertices (in particular, edge lengths) must scale to a subset of $$ \{ 1, \sqrt{2}, \ldots \} $$ since those are the distances between vertices of the unit cube.

Answer 3

I found two further criteria that helped me to eliminate a lot of candidates from my list of symmetric polytopes.

• Assuming a sufficiently symmetric polytope $P$ with barycenter in the origin, we can ask for the cosines $\cos\sphericalangle(v,w)$ of the angles between vectors $v$ and $w$ that belong to vertices of $P$ (in a sense, these are just the distances from Ethan's answer, but normalized in a sense). I also was able to derive a formula that gives these cosines in a $01$-polytopes in $\{0,1\}^n$, in which any two vertices have exactly $k$ one-entries. It is $$\frac{n i-k^2}{n k-k^2},$$ where $i$ is the number of ones the two vectors have in common. So if you let $i$ run in $\{0,...,\max(2k-n,0)\}$ you can find all the cosines such a configuration allows. E.g., the list for the cuboctahedron and 24-cell coincide and are $\{-1,-1/2,0,1/2,1\}$. This list occures first time for $n=8,k=4$. Still, as Dr. Klitzing explained, they are no $01$-polytopes.

• If we look at $01$-polytopes $P$ in which all edges have the same length (e.g. uniform polytopes), then I was able to prove, that if you have to vertices $v$ and $w$ of $P$, their graph theoretical distance in the edge graph determines their Euclidean distance in the polytope and vice versa. This then gives an alternative proof that cuboctahedron and 24-cell are not $01$-polytopes: both have two distinct pairs of vertices at graph theoretical distance two, some belongs to the cosine $0$, and some to the cosine $-1/2$.