# Find the smallest triangulation of the n-dimensional

How to find the smallest triangulation of the n-dimensional cube into n- simplices?

It is known, for example, that the 4D cube (the hypercube) may be partitioned into 16 4-simplices, and this is minimal. But the minimum number is unknown except for the few small values of n that have yielded to exhaustive computer searches.

(These tags not available for me : hypercube , computer search)

• @AlexRavsky Thanks for editing tags.
– Zia
Aug 24 '13 at 16:38

This is a hard research question. As achille hui says, one of the best lower bounds for the number of n-simplices known is (roughly) $2^n n! /n^{n/2}$, obtained by Hadamard's inequality, which gives you an upper bound on the volume that a simplex contained in the cube can have. (achille seems to be forgetting a factor of $2^n$, which arises from the fact that Hadamard's inequality is about the $[-1,1]^n$ cube, rather than the $[0,1]$ cube).

This "Hadamard bound" was improved by Warren D. Smith by using Hiperbolic volume and very recently by Alexey Glazyrin. They change the $2^n$ factor to, respectively, $6^{n/2}$ and $e^n$ (http://www.sciencedirect.com/science/article/pii/S019566989990327X, http://arxiv.org/abs/0910.4200).

In terms of actual constructions of triangulations with "few" simplices, the smallest size of a triangulation is known only up to dimension 7. It was computed by Anderson and Hughes (http://www.sciencedirect.com/science/article/pii/0012365X95000758) and it has $1493$ simplices.

For high-dimensional cubes, there is a "simple but relatively efficient" trick by Haiman (http://link.springer.com/article/10.1007%2FBF02574690) that basically says: If you can triangulate an $n$-cube with $\alpha^n n!$ simplices for a certain dimension, then by taking Cartesian products you can triangulate every $N$-cube ($N$ is now consider very big) also with $\alpha^N N!$ simplices. The best value for $\alpha$ known so far is obtained for the minimum triangulation of the $7$-cube, $1493 = 0.840^7 7!$. That is, Haiman's trick gives you triangulations with $0.840^N N!$ simplices.

With a more elaborate argument I, with D. Orden, constructed triangulations of the $N$-cube with (asymptotically), $0.816^N N!$ simplices (http://link.springer.com/article/10.1007%2Fs00454-003-2845-5, http://arxiv.org/abs/math.CO/0204157).

For cubes of small dimension, apart of the Anderson-Hughes paper mentioned above I would cite this paper of Bliss and Su, dealing with lower bounds: http://link.springer.com/article/10.1007%2Fs00454-004-1128-0, http://arxiv.org/abs/math/0310142

Summing up, I would say that so far "sophisticated ideas" provide only slight improvements to "simple ideas" (by "simple" I mean Hadamard for lower bounds and Haiman for explicit constructions / upper bounds).

Let $S(n)$ be the minimal number of simplices in the triangulation of an $n$-dimensional cube. It seems the following.

Since an $n$-dimensional cube has $2^n$ vertices and an $n$-simplex has $n+1$ vertices, we see that $S(n)\ge 2^n/(n+1).$

A triangulation of an $n$-dimensional cube induces a triangulation of each of $(n-1)$-dimensional face of the $n$-cube. Since each such a face has at least $S(n-1)$ $(n-1)$-simplices, and each $n$-simplex has $n+1$ $(n-1)$-dimensional faces, we have that $S(n)\ge S(n-1)\cdot 2n/(n+1).$

Moreover, if we count (1-dimensional) edges instead of $(n-1)$-dimensional faces, we obtain the bound like $S(n)\ge (2n(n-1)S(n-1)-2^n)/(n+1)$ (each $k$-simplex has $k(k+1)/2$ edges, each $(n-1)$-dimensional face yields $S(n-1)$ edges and the edges of the $n$-cube are counted twice. This bound can be improved, because every edge of the triangulation of the $n$-cube which is not an edge of the $n$-cube, belongs to at least two simplices of the triangulation. Then we have a bound $S(n)\ge (4n(n-1)S(n-1)-3\cdot 2^n)/(n+1).$

Moreover, the bound $S(n)\ge S(n-1)\cdot 2n/(n+1)$ can be improved too, because an $n$-dimensional cube has $n$-pairs of parallel $(n-1)$-dimensional faces and each simplex of the triangulation cannot have parallel $(n-1)$-dimensional faces. So it has an $(n-1)$-dimensional face which not lies on an $(n-1)$-dimensional face of the cube. Therefore we have a bound $S(n)\ge 2S(n-1)$.

• An alternate lower bound for $S(n)$ can be obtained using Hadamard's upper bound for volume of $n$-simplex inside a unit cube $\frac{\sqrt{n}^n}{n!}$. This implies $S(n) \ge \frac{n!}{\sqrt{n}^n}$ which overtake the first estimate $\frac{2^n}{n+1}$ here at $n \ge 16$. Aug 24 '13 at 13:32