21
$\begingroup$

Let $\Delta\subset\Bbb R^n$ be a simplex with $n+1$ vertices. Let $G\subset\mathrm{GL}(\Bbb R^n)$ be a finite group of linear symmetries of $\Delta$, i.e. linear transformations that fix the simplex set-wise. Set $m:=|G|$.

Question: Is there a simplicial subdivision $\Delta=\Delta_1\cup\cdots\cup\Delta_m$, so that $G$ acts regularly (that is, transitively and freely) on the set of simplices $\{\Delta_i:1\le i\le m\}$?

In other words, I want a decomposition of $\Delta$ into fundamental regions w.r.t. the group action, where each region is a simplex. By simplicial subdivision I mean a tiling of $\Delta$ with simplices, any two of which are either disjoint or intersect in a common face (though their intersection with the boundary of $\Delta$ might not be a face of $\Delta$).

Such subdivisions clearly exist when $n=1$, and the image below shows that they also exist for $n=2$. The groups are (from left to right)

$$G\cong\text{$\{$ $\Bbb Z_2$,$\;$ the cyclic group $\Bbb Z_3$,$\;$ the dihedral group $D_3$}\}.$$

(update: simplicial subdivisions also exist for $n=3$; see Note II below)

Instead of thinking of $G$ as a linear group, we can interpret it as a permutation group $G\subseteq\mathbf S_{n+1}$, a subgroup of the symmetric group $\mathbf S_{n+1}$, permuting the vertices $\{1,...,n+1\}$ of $\Delta$. The full symmetric group induces the barycentric subdivision (as seen in the right-most image). One can then ask whether it is always possible to combine some of the simplices in the barycentric subdivision to form a simplex that is a fundamental region for $G$.

I also wonder in how far such a subdivision (if it exists) is unique (update: they are not, see Note II below).


Note I

In the comments I describe how to construct a decomposition for any group of order 2.


Note II

I found simplicial fundamental domains for all subgroups of $\mathbf S_4$ (subgroups taken from here).

$$ \begin{array}{r|c|l} \text{group} & \text{size} & \text{fundamental simplex} \\ \hline \mathbf S_4 & 24 & \{1,2,3,4\},\{1,2,3\},\{1,2\},\{1\} \\ \hline \mathbf A_4 & 12 & \{1,2,3,4\},\{1,2,3\},\{1\},\{2\} \\ \hline \langle(1,2,3,4),(1,3)\rangle & 8 & \{1,2,3,4\},\{1,3\},\{1\},\{2\} \\[-0.4ex] & & \{1,2\},\{2,4\},\{1,3\},\{1\} \\ \hline \langle(1 2 3),(1 2)\rangle & 6 & \{1,2,3\},\{1,2\},\{1\},\{4\} \\ \hline \langle(1,2,3,4)\rangle & 4 & \color{blue}{\{1,2,3,4\},\{1\},\{2\},\{3\}} \\[-0.4ex] & & \color{orange}{\{1,3\},\{2,4\},\{1\},\{2\}} \\\hline \langle(1,2)(3,4),(1,3)(2,4)\rangle & 4 & \color{blue}{\{1,2,3,4\},\{1\},\{2\},\{3\}} \\ \hline \langle(1,3),(2,4)\rangle & 4 & \color{orange}{\{1,3\},\{2,4\},\{1\},\{2\}} \\ \hline \langle(1,2,3)\rangle & 3 & \{1,2,3\},\{2\},\{3\},\{4\} \\ \hline \langle(1,2)(3,4)\rangle & 2 & \color{red}{\{1,2\},\{2\},\{3\},\{4\}} \\ \hline \langle(1,2)\rangle & 2 & \color{red}{\{1,2\},\{2\},\{3\},\{4\}} \\ \hline \langle\varnothing\rangle & 1 & \{1\},\{2\},\{3\},\{4\} \end{array} $$

The groups are given as permutation groups on the vertex set $\{1,2,3,4\}$. Each fundamental simplex is given in terms of its vertices, where a subset $S\subseteq\{1,2,3,4\}$ denotes the vertex

$$\frac1{|S|}\sum_{i\in S} v_i.$$

Simplices highlighted in the same color indicate that different groups have the same fundamental simplex. I do not claim that the list of subdivisions is complete.

Some oberservations:

  • There are groups (e.g. $\langle(1,2,3,4)\rangle$) that have two geometrically different subdivisions! So subdivisions are not always unique.
  • A single subdivision can work for multiple groups (see the highlighted colors).
  • The second fundamental simplex listed for the 8-element group is not a union of simplices from the barycentric subdivision! So there can exist other subdivision. But this subdivision still uses the same vertex coordinates as the barycentric subdivision.
  • Curious observation (partially explained by David in the comments): the size of each group equals the product of the cardinalities of the sets listed in the right column. The reason seems to be that these cardinalities determine the volume of the fundamental simplex, which must be $|G|^{-1}\cdot\mathrm{vol}(\Delta)$.
$\endgroup$
14
  • 1
    $\begingroup$ @Jemery This would be my attempt: if $G=\{\mathrm{id},g\}$ then choose a vertex $v_1\in\mathrm{vert}(\Delta)$ with $v_2:=gv_1\not= v_1$. Let $x$ be the mid-point of the edge between $v_1$ and $v_2$. Then we can choose $\Delta_i$ to have vertices $\mathrm{vert}(\Delta)-\{v_1,v_2\}\cup\{v_i,x\}$. $\endgroup$
    – M. Winter
    Jun 21 at 8:57
  • 1
    $\begingroup$ @JeremyRickard at least for a double transposition in dimension 3, it works easily. $\endgroup$
    – YCor
    Jun 21 at 10:02
  • 1
    $\begingroup$ @Henrik As I tried to explain in my comment, the simplex $\{\{0,1\},\{1\},\{2\},\{3\}\}$ should work. You don't need to have $\{2,3\}$. The only thing that is forbidden is that only one of $2$ and $3$ is in the fundamental region. $\endgroup$
    – M. Winter
    Jun 21 at 12:28
  • 3
    $\begingroup$ @Henrik I also expect (and hope) that something like this will turn out true. But I worry that it is more subtle. For example, both groups $\langle(1,2),(3,4)\rangle$ and $\langle (1,2)(3,4)\rangle$ act identically on their orbits, but the groups have different orders and therefore require different subdivisions. $\endgroup$
    – M. Winter
    Jun 21 at 18:35
  • 1
    $\begingroup$ I can get part way to explaining the observation about the products of the sizes of the sets. A set $S$ corresponds to the point $\tfrac{1}{|S|} \sum_{i \in S} e_i$ in the simplex. So, to compute the volume of the simplex corresponding to $S_1$, $S_2$,..., $S_n$, one computes the determinant of these vectors, and gets $\left( \prod \tfrac{1}{|S_i|} \right) \det M$ where $M_{ij}$ is $1$ if $j \in S_i$ and $0$ if $j \not \in S_i$. In every example so far, we have $\det(M) = 1$, so we just get $\prod \tfrac{1}{|S_i|}$. $\endgroup$ Jun 22 at 19:11

1 Answer 1

20
$\begingroup$

The answer is yes!

Notation: Let $e_1$, $e_2$, ..., $e_n$ be the vertices of the simplex. Let $[n] = \{ 1,2,3, \ldots, n \}$. For $S$ a nonempty subset of $[n]$, let $p(S) = \tfrac{1}{|S|} \sum_{i \in S} e_i$.

Let $G$ be a subgroup of $S_n$. Let $G_k$ be the subgroup of $G$ stabilizing (pointwise) each of $1$, $2$, ..., $k$. Let $A_k$ be the orbit of $k$ under the action of $G_{k-1}$. Our fundamental domain will be the convex hull of $p(A_1)$, $p(A_2)$, ..., $p(A_n)$.

Example Take the third group in the OP's table, the dihedral group of order $8$. Then $A_1 = \{ 1,2,3,4 \}$, $A_2 = \{ 2, 4 \}$, $A_3 = \{ 3 \}$, $A_4 = \{ 4 \}$ which, up to relabeling of coordinates, is the OP's first solution for this case.

Define a relation $\preceq$ on $[n]$ by $i \preceq j$ if $j \in A_i$. In other words, $i \preceq j$ if there is $g \in G$ with $g(1)=1$, $g(2)=2$, ..., $g(i-1)=i-1$ and $g(i) = j$.

Lemma $\preceq$ is a partial order.

Proof It is clear that $i \in A_i$. If $j \in A_i$ then $i \leq j$, so it is clear that $\preceq$ is antisymmetric. It remains to check transitivity.

Suppose that $j \in A_i$ and $k \in A_j$. Note that $i \leq j$. The condition $k \in A_j$ means that $k \in G_{j-1} \cdot j \subseteq G_{i-1} \cdot j$. But the condition that $j \in A_i$ means that $G_{i-1} \cdot j = G_{i-1} \cdot i$. So we conclude that $k \in G_{i-1} \cdot i = A_i$, as desired. $\square$

Lemma Let $(x_1, x_2, \ldots, x_n)$ be a point of in the simplex. Then $(x_1, x_2, \ldots, x_n)$ is in the convex hull of $p(A_1)$, $p(A_2)$, ..., $p(A_n)$ if and only if we have $x_i \leq x_j$ whenever $i \preceq j$.

Proof It is cleaner to work with $(x_1, x_2, \ldots, x_n) \in \mathbb{R}_{\geq 0}^n$ and show that $(x_1, x_2, \ldots, x_n)$ is a nonnegative linear combination of $p(A_1)$, $p(A_2)$, ..., $p(A_n)$ if and only if $x_i \leq x_j$ whenever $i \preceq j$.

Suppose first that $(x_1, x_2, \ldots, x_n)$ is a nonnegative linear combination of $p(A_1)$, $p(A_2)$, ..., $p(A_n)$, and let us deduce that $x_i \leq x_j$ whenever $i \preceq j$. It is enough to show that, if $i \preceq j$, then $p(A_k)_i \leq p(A_k)_j$ for all $k$. If $k \leq i$, then $p(A_k)_i = p(A_k)_j$. If $k > i$ then $p(A_k)_i=0$ and $p(A_k)_j \geq 0$.

Now, suppose that $x_i \leq x_j$ whenever $i \preceq j$. In particular, $x_1 = \min_{i \in A_1} x_i = \min_{i \in G \cdot 1} x_i$. So we can write $(x_1, \ldots, x_n) = x_1 |A_1| p(A_1) + (0, y_2, \ldots, y_n)$ for some $(0, y_2, \ldots, y_n) \in \mathbb{R}_{\geq 0}^n$, and we also have $y_i \leq y_j$ whenever $i \prec j$. We then induct, considering the group $G_1$ and the vector $(y_2, y_3, \ldots, y_n)$. $\square$

Theorem The convex hull of $p(A_1)$, $p(A_2)$, ..., $p(A_n)$ is a fundamental domain for $G$.

Proof Take a generic $(x_1, \ldots, x_n)$ in the simplex. We will show that there is a unique $g \in G$ such that $(gx)_i \leq (gx)_j$ if and only if $i \preceq j$. First of all, we must have $(gx)_1 = \min_{i \in G \cdot 1} (gx)_i$. So we must use $G$ to take the minimal element of $\min_{i \in G \cdot 1} x_i$ and move it to position $1$. We can do this, and once we do this we may only further apply elements of $G_1$. We then must similarly have $(gx)_2 = \min_{i \in G_1 \cdot 2} (gx)_i$; again, we can apply an element of $G_1$ to do this and then we are only permitted to apply elements of $G_2$. Continuing in this way, there is a unique element of $g$ which makes it so that $(gx)_i = \min_{j \in G_{i-1} \cdot i } (gx)_j$ for each $i$. $\square$

This concludes the proof that we have the fundamental domain as desired. We close by noting that, by the orbit-stabilizer theorem, we have $|A_k| = |G_{k-1}|/|G_k|$ so $\prod_{k=1}^n |A_k| = \prod_{k=1}^n |G_{k-1}|/|G_k| = |G_0|/|G_n| = |G|/1 = |G|$, proving the curious observation in the question.

$\endgroup$
3
  • $\begingroup$ That is an amazing answer, thank you! Can you say a word or two about how you came up with this? Was it by looking hard at the examples in my post or are there some more underlying insights? $\endgroup$
    – M. Winter
    Jun 23 at 9:44
  • 2
    $\begingroup$ Beyond your examples, I also did the $10$ and $20$ element subgroups of $S_5$, the $21$ element subgroup of $S_7$ and worked out the general case of $C_p \ltimes C_q$ before I got it. I focused on groups that had few prime factors, since then the condition $\prod |A_j| = |G|$ was very restrictive, especially when combined with the condition that the determinant was nonzero. $\endgroup$ Jun 23 at 12:55
  • 2
    $\begingroup$ For example, for the $10$ element subgroup of $S_5$, the only way to factor $10$ as a product of $5$ numbers each $\leq 5$ is $5 \times 2 \times 1 \times 1 \times 1$, and then only way to make the determinant nonzero is to use sets of the form $abcde$, $ab$, $a$, $c$, $d$. I noted that this worked if $e \equiv (a+b)/2 \bmod 5$, and not otherwise. I probably should have gotten it then, but it really clicked when I did the $21$ element subgroup of $S_7$. The sets had to be of the form $abcdefg$, $abc$, $a$, $b$, $d$, $e$, $f$, and it only worked when $abc$ was an orbit for $\text{Stab}(g)$. $\endgroup$ Jun 23 at 12:59

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.