# Algebra behind equidistant subdivision of unit simplices

Let $k\in\mathbb Z_+$ and define the $k$-dimensional unit simplex: \begin{align*} \bigtriangleup_k\equiv\left\{(\lambda_1,\ldots\lambda_{k+1})\in\mathbb R^{k+1}\,\Bigg|\,\lambda_1,\ldots,\lambda_{k+1}\geq0\text{ and }\sum_{i=1}^{k+1}\lambda_i=1\right\}. \end{align*} My goal is to describe a rigorous algebraic construction of the equidistant subdivision of this simplex into smaller simplices that meet each other only at vertices, edges, or (hyper)faces.

Formally, let $\ell\in\mathbb N$. (Note: As @LordSharktheUnknown and @EthanBolker have pointed out in their comments, the construction under investigation may fail to work as desired if $\ell$ is too small as compared to $k$. I do not mind imposing additional assumptions on $\ell$, for example, that $\ell$ be “sufficiently” large and/or a multiple of $k+1$. All I care about is that I need the construction to work for infinitely many values of $\ell$ for each fixed $k$.) Consider $$\bigtriangleup_{k,\ell}\equiv\left\{\left(\frac{w_1}{\ell},\ldots,\frac{w_{k+1}}{\ell}\right)\,\Bigg|\,w_1,\ldots,w_{k+1}\in\mathbb Z_+\text{ and }\sum_{i=1}^{k+1}w_i=\ell\right\},$$ those points in $\bigtriangleup_k$ that are gained by dividing each edge of the original simplex into $\ell$ equal segments and then “cutting” $\bigtriangleup_k$ by parallel hyperplanes accordingly. The intuitive idea is pretty simple and is depicted in the following figure for $k=2$ and $\ell=3$.

Define $\mathscr A$ to be the set consisting of collections of the $k+1$ vertices of each of these smaller polyhedra in the equidistant subdivision. That is, $(\boldsymbol{\lambda}^{(1)},\ldots,\boldsymbol\lambda^{(k+1)})$ is in $\mathscr A$ if

• $\boldsymbol\lambda^{(j)}\in\bigtriangleup_{k,\ell}$ for every $j\in\{1,\ldots,k+1\}$;
• the vectors $\boldsymbol\lambda^{(1)},\ldots,\boldsymbol\lambda^{(k+1)}$ are affinely independent—that is, $\alpha_1,\ldots,\alpha_{k+1}\in\mathbb R$, $\sum_{j=1}^{k+1}\alpha_j\boldsymbol\lambda^{(j)}=\mathbf{0}$ and $\sum_{j=1}^{k+1}\alpha_j=0$ together imply $\alpha_1=\cdots=\alpha_{k+1}=0$; and
• $\boldsymbol\lambda^{(1)},\ldots,\boldsymbol\lambda^{(k+1)}$ are “adjacent” in the sense that $$\lambda_i^{(\alpha)}-\lambda_i^{(\beta)}\in\left\{-\frac{1}{\ell},0,\frac{1}{\ell}\right\}$$ for every $i,\alpha,\beta\in\{1,\ldots,k+1\}$.

For each $(\boldsymbol\lambda^{(1)},\ldots,\boldsymbol\lambda^{(k+1)})\in\mathscr A$, let $S_{(\boldsymbol\lambda^{(1)},\ldots,\boldsymbol\lambda^{(k+1)})}$ denote the convex hull of $\{\boldsymbol\lambda^{(1)},\ldots,\boldsymbol\lambda^{(k+1)}\}$.

My goal is to provide an elementary (!) proof showing that the collection $$\mathscr S\equiv\{S_{(\boldsymbol\lambda^{(1)},\ldots,\boldsymbol\lambda^{(k+1)})}\,|\,(\boldsymbol\lambda^{(1)},\ldots,\boldsymbol\lambda^{(k+1)})\in\mathscr A\}$$ constitutes a simplicial subdivision of $\bigtriangleup_k$, that is:

• $\bigtriangleup_k=\bigcup_{S\in\mathscr S}S$; and
• if $S,S'\in\mathscr S$, then $S\cap S'$ is either empty or a common face of both $S$ and $S'$.

While this seems intuitively obvious (see the figure), I have trouble:

$\phantom{\text{i}}$(i) finding the adjacent grid points in whose convex hull a given $\boldsymbol\lambda\in\bigtriangleup_k$ lies; and

(ii) showing that if $(\boldsymbol\lambda^{(1)},\ldots,\boldsymbol\lambda^{(k+1)}),(\boldsymbol\mu^{(1)},\ldots,\boldsymbol\mu^{(k+1)})\in\mathscr A$, then $$\operatorname{hull}\left(\{\boldsymbol\lambda^{(1)},\ldots,\boldsymbol\lambda^{(k+1)}\}\right)\cap\operatorname{hull}\left(\{\boldsymbol\mu^{(1)},\ldots,\boldsymbol\mu^{(k+1)}\}\right)=\operatorname{hull}\left(\{\boldsymbol\lambda^{(1)},\ldots,\boldsymbol\lambda^{(k+1)}\}\cap\{\boldsymbol\mu^{(1)},\ldots,\boldsymbol\mu^{(k+1)}\}\right).$$

Any suggestion on what proof strategy could make the perhaps “obvious” yet tedious algebra work efficiently would be appreciated.

• In three dimensions, I'm not sure all the cells you get are simplices. – Lord Shark the Unknown Sep 15 '18 at 18:36
• As @LordSharktheUnknown notes. Slicing a tetrahedron with four planes parallel to the faces and bisecting the altitudes leaves an octahedron in the middle. – Ethan Bolker Sep 15 '18 at 18:39
• @EthanBolker I see. However, doesn’t requiring that every collection in $\mathscr A$ be affinely independent ultimately generate simplices along the grid points? – triple_sec Sep 15 '18 at 18:47
• @EthanBolker OK, what if $\ell$ is also assumed to be a multiple of $k+1$? In that case, it seems to me that it can be arranged that the barycenter of the original simplex $\bigtriangleup_k$ be a member of some collection in $\mathscr A$, right? I will make this extra assumption more explicit in the hope it helps. – triple_sec Sep 15 '18 at 18:56
• Did you draw the picture (in principle) for cutting the tetrahedron with four slices parallel to each face (or three - not sure how you are counting)? If that works then you're probably OK, but I suspect it won't. I've no time to try it now. – Ethan Bolker Sep 16 '18 at 0:05

The desired goal is not possible, regardless of any tweaks you make to it, if indeed it follows from your conditions that this would provide a decomposition of the regular simplex into smaller regular simplices. Intuitively this follows immediately from the fact that vertices, which would follow from a "corrected" version of the adjacency condition (as it stands you have lots of simplices intersecting each other "badly", e.g. for $$k=4$$ and $$\ell=5$$ notice that conv(2111,1200,1020,1002) is probably not one of the simplices you wanted...).
A fact which may help if you try to pin down an exact reference for yourself: breaking a polytope $$X$$ into smaller copies of $$X$$, each of the same size, is only possible if $$X$$ [and its isometric images] can fill space. The latter is already a rare property for regular polytopes to possess, and there are four-dimensional regular polytopes which do fill space but still cannot be broken down into smaller copies.