How many non-equivalent sections of a regular 7-simplex?

Question

Suppose we have a regular 7-simplex in $\mathbb{R}^8$ defined by vertices <1,0,0,...,0>, <0,1,0,..,0>,...,<0,...,0,1>. A section is a 3-dimensional linear subspace of $\mathbb{R}^8$ that contains simplex centroid and three other points, each of which is a centroid of a non-empty set of simplex vertices. Two sections are equivalent if they are identical spaces under permutation of coordinates. In other words, when some permutation of coordinates is the bijection between two spaces. How many non-equivalent sections are there? Is there an efficient way to enumerate them?

Motivation: visualizing symmetric priors over distributions over 8 outcomes

Update 12/09 I tried an automatic search and got 49 sections, same as Peter Shor below. Here they are. Note that grouping is a bit different since I group sections with or without unexpected centroids together.

No empty vertices:

One empty vertex:

Two empty vertices:

Three empty vertices:

Four empty vertices:

old stuff Here's an illustration of solving this problem for 2-sections of a 3-simplex in 4 dimensions. There seems to be only 2 non-equivalent 2-sections (triangle and square). This solves the problem of visualizing entropy (contour lines) of distributions over 4 outcomes, and I'd like extend it to 8 outcomes.

^{Image sources: (1) (2) (3) (4) (5) (6)}

Answer 1

Here's the answer. The main claims (Claims 1-4) I am fairly sure I got right, but I could easily have missed a case (or counted an extra case) in the later enumeration. If anybody finds a mistake, please comment. Let me remark that I find Claims 1-4 much more interesting than the subsequent enumeration based on them.

The simplex centroid $e=(1,1,1,1,1,1,1,1)$ is included in all our hyperplanes, but I'm generally not counting it as a centroid in the discussion below (so centroid means centroid of a $k$-dimensional face, with $k < 7$).

We'll divide the question into cases.

The first case we deal with is when we don't have any unexpected centroids. We start with three centroids $a$, $b$, and $c$. These will automatically generate $\bar{a}$, $\bar{b}$, $\bar{c}$. We will call any centroid other than these six an unexpected centroid. We represent our centroids as subsets of {$1,2,\ldots,8$}. If we have the centroid {$1,2,3$}$=\langle 1,1,1,0,0,0,0,0\rangle $, then we automatically have the centroid {$4,5,6,7,8$}$=\langle 0,0,0,1,1,1,1,1\rangle$ corresponding to the complement of the set. So, to summarize, the first case consists of hyperplanes which pass through exactly six centroids: $a,b,c,\bar{a},\bar{b},\bar{c}$.

Now, let's represent this case by putting the numbers {$1,2,\ldots,8$} on the vertices of a cube. The cube will have three faces corresponding to $a,b,c$ and the three opposite faces will correspond to $\bar{a},\bar{b},\bar{c}$. For example, if the sets were $a=${$1,2,3$}, $b=${ $1,5,6$} and $c=${$2,5,6,7$}, then the vertex $\bar{a}bc$ would contain {$5,6$}, the vertex $\bar{a}\bar{b}\bar{c}$ would contain {$4,8$}, and the vertex $\bar{a}b\bar{c}$ would be empty. It's not too hard to see that whether there is an unexpected centroid only depends on the positions of the empty vertices. It's also clear that rotations and reflections of this cube give equivalent sections.

Claim 1: If two adjacent vertices are empty, there is an unexpected centroid.

Proof: The two adjacent vertices form an edge. We might as well rotate the cube so that the empty edge is the $ab$ edge. Then we have $a \cap b = \emptyset$. This means that $a \cup b$ is an unexpected centroid (here we have to use the fact $a \neq \bar{b}$). Example: if $a =${$1,2$}, $b = ${$3,4,5$}, then $a \cup b =${$1,2,3,4,5$} is in the linear span of $a$ and $b$.

Claim 2: If two opposite vertices of the cube are empty, then there is an unexpected centroid.

Proof: We can rotate the cube so the empty vertices correspond to $\bar{a}\bar{b}\bar{c}$ and $abc$. Then, for example, if $a=(1,1,1,0,0,0,0,0)$, $b=(0,0,1,1,1,1,0,0)$ and $c=(1,0,0,0,0,1,1,1)$, we can take $a+b+c-e$ where $e$ is the all-ones vector, and get $(1,0,1,0,0,1,0,0)$.

Claim 3: If the odd- or even-parity vertices of the cube are empty, then there is an unexpected centroid.

Proof: Rotate the cube so that $\bar{a}\bar{b}\bar{c}$ is empty. Now, every coordinate is in exactly 1 or 3 of $a,b,c$. Thus, $\frac{1}{2}(a+b+c-e)$ is an unexpected centroid. Example $a=(1,1,1,0,0,0,1,1)$, $b=(0,0,0,1,1,0,1,1)$ and $c=(0,0,0,0,0,1,1,1)$, and $\frac{1}{2}(a+b+c-e) = (0,0,0,0,0,0,1,1)$

Claim 4: If none of the situations in Claims 1,2,3 hold, then there is no unexpected centroid.

Proof: We can rotate the cube so that the empty vertices are a subset of $\bar{a}bc$, $a\bar{b}c$ and $ab\bar{c}$. For there to be an unexpected centroid, you must be able to find $\alpha a + \beta b + \gamma c$ so that the coordinates of this vector take on two values. One of these coordinates is 0 (since $\bar{a}\bar{b}\bar{c}$ is not empty), meaning we can assume wlog that $\alpha, \beta, \gamma$ are either 1 or 0. But for $\alpha + \beta + \gamma$ to also be either 1 or 0, we need two of $\alpha, \beta, \gamma$ to be 0, which means that we don't get an unexpected centroid.

So now, we need to enumerate the number of ways of putting 8 elements onto the vertices of a unit cube so that at least one element is on each of the nonempty vertices. Since sections are equivalent under permutations of the coordinates, we should consider these to be 8 identical elements (so the only thing that matters is how many elements are on a vertex). There are four cases.

Case A: no empty vertices. There is just 1 way of doing this: putting one element on each vertex.

Case B: one empty vertex. There are 3 ways of doing this. Exactly one vertex will have two elements on it, and it can be either Hamming distance one, two, or three from the empty vertex.

Case C: two empty vertices. In this case, these two vertices must have Hamming distance 2. The two extra elements can either be on the same vertex (3 ways) or two different vertices (7 ways).

Case D: three empty vertices. In this case, any pair of these three vertices must have Hamming distance 2, so there's only one way of arranging them. The three extra elements can either be all on the same vertex (3 ways), divided two on one vertex and one on another (7 ways), or on three different vertices (4 ways).

This gives 28 essentially different sections with no unexpected centroids.

We now must count the cases with unexpected centroids corresponding to Claims 1-3. We'll deal with the situation in the Claims 1,2,3 separately.

Case of Claim 3 Let's start with the situation in Claim 3. First, we can assume that there are no empty vertices of the cube other than the two opposite ones (if this happens, we are in the Claim 1 situation, and we take care of it there).

We now can choose another centroid $d$ in the linear span of $a,b,c,e$ so that $a \cup b \cup c \cup d$ covers every coordinate exactly twice. By the criterion that there are six non-empty vertices, none of the six intersections $a \cap b$, $a \cap c$, etc. can be empty. We need to put the eight elements into these six intersections. This corresponds to putting 8 elements on the edges of a tetrahedron so that every edge corresponds to at least one element. There are 3 ways to do this (two extra on one edge, one extra on each of two opposite edges, and one extra on each of two adjacent edges). Claim 3 thus gives 3 more non-equivalent sections. Notice that if we had analysed Claim 3 by just looking at the symmetries of the cube (as we did for the cases without unexpected centroids), we would have obtained four non-equivalent sections.

Case of Claim 2 What I'd like to claim here is that this is really the situation in Claim 1 disguised. Maybe the best way to do this is by example. If we have $a=${$1,2,7,8$}, $b=${$3,4,7,8$}, $c=${$5,6,7,8$}, then the centroid {$7,8$} is in our hyperplane, and the hyperplane is thus generated by $a'=${$1,2$}, $b'=${$3,4$}, $c'=${$5,6$}, which is covered by Claim 1.

Case of Claim 1 Here, there are three possibilities. In the first one, there are four centroids $a$, $b$, $c$, $d$, with pairwise empty intersections so that $a \cup b \cup c \cup d =${$1,2,\ldots,8$}. The number of ways of doing this is the number of partitions of 8 into four non-empty parts, which is 5: {$(5,1,1,1), (4,2,1,1), (3,3,1,1),(3,2,2,1),(2,2,2,2)$}.

In the second possibility, we have three pairwise disjoint centroids $a$, $b$, $c$, with $a \cup b \cup c = e$, and also another centroid $d$ so that both $d\cap x$ and $\bar{d} \cap x$ are non-empty for $x=a,b,c$. The cardinalities of $a,b,c$ could be {$4,2,2$} or {$3,3,2$}. In either case, we get two non-equivalent sections, giving 4 total non-equivalent sections.

For the third possibility, we have three pairwise disjoint centroids $a$, $b$, $c$, with $a \cup b \cup c = e$, and we have two more pairwise disjoint centroids $f$ and $g$ so that $f \cup g = a \cup b$. In this case, the cardinality of $c$ can range from 1 to 4. I'll just list representative vectors for these possibilities. The coordinates considered are those not in $c$.

$c=4$

$(1,1,0,0),(0,1,1,0),(0,0,1,1),(1,0,0,1)$

$c=3$

$(1,1,1,0,0),(0,0,1,1,0),(0,0,0,1,1),(1,1,0,0,1)$

$c=2$

$(1,1,1,0,0,0),(0,0,1,1,1,0),(0,0,0,1,1,1),(1,1,0,0,0,1)$

$(1,1,1,1,0,0),(0,0,1,1,1,0),(0,0,0,0,1,1),(1,1,0,0,0,1)$

$(1,1,1,1,0,0),(0,1,1,1,1,0),(0,0,0,0,1,1),(1,0,0,0,0,1)$

$c=1$

$(1,1,1,1,1,0,0),(0,1,1,1,1,1,0),(0,0,0,0,0,1,1),(1,0,0,0,0,0,1)$

$(1,1,1,1,1,0,0),(0,0,1,1,1,1,0),(0,0,0,0,0,1,1),(1,1,0,0,0,0,1)$

$(1,1,1,1,0,0,0),(0,0,1,1,1,1,0),(0,0,0,0,1,1,1),(1,1,0,0,0,0,1)$

$(1,1,1,1,0,0,0),(0,1,1,1,1,0,0),(0,0,0,0,1,1,1),(1,0,0,0,0,1,1)$

This gives 9 more non-equivalent sections, making 49 altogether.

Answer 2

Preliminary thoughts:

There are 8 vertices of a 7 dimensional simplex, 28 edges, and $\binom{8}{k+1}$ k-faces. Each $k$-face is a $k$-simplex and they all have distinct centroids. There are thus $\sum_{k=0}^6\binom{8}{k+1}=2^8-2=254$ different centroids that we might choose from (you have excluded the centroid of the entire 7-simplex by asking for "other" points). 3d sections are defined by making 3 (for non-degenerate sections, different) choices, so there will be $\binom{254}{3}$. Many are still degenerate, and many are equivalent.

Let the rank of a centroid be the dimensionality of the face that it arises from, and I'll write k-centroid for a centroid with rank k.

Each non-degenerate section is the intersection of the 7-simplex with a 3-plane through the unique 7-centroid (I'll call that point "the origin"). Let's see if we can count distinct 3-planes first.

We'd like to choose 3 centroids which are all "linearly independent" over the origin. Let's order the choices so that the rank is nondecreasing.

First note the following duality - the centroid of a $k$-face and the centroid of the "opposing" $(6-k)$-face lie on the same line through the origin. The vertices of the k-face and the (6-k)-face form a partition of the vertices of the 7-simplex. Therefore, we can restrict the first choice to choosing centroids with rank between 0 and 3 inclusive, and let's just choose a subset of 1/2 of the 3-centroids which don't lie opposite each other, so there are 8+28+56+35=127 choices at first. (It was helpful to me here to draw the 3-d case, I'm sorry that I haven't included images). (When we start considering choices up to equivalence rather than up to defining the same planes, we probably can just reduce to 4 choices here, one for each different rank...?)

For the second centroid, there are 126 remaining centroids from the set above, however some of the choices lead to equivalent 2-planes. The principle here should be similar. We've already ruled out points which lie opposite each other from the origin, now we need to rule out points which lie opposite each other from the line defined by the 1st centroid and the origin.

The first centroid $q$ defines a m-simplex $T$ if it is rank m and also defines a (6-m)-simplex $S$ which comes from the vertices not in $T$. For a k-centroid $p$ which is a centroid of a subsimplex of $T$ (or $S$), the (m-1-k)-centroid opposite $p$ in $T$ (or (6-m-1-k)-centroid opposite $p$ in $S$, as the case may be) defines the same 2-plane with the origin and $q$. We'd just like to count one of these.

I'm less clear on what happens with the centroids arising from simplices with vertices both in $T$ and $S$, so perhaps I'll take a break for now.

---

Addendum 1:

I realized that what I'm describing above is really part of a vector matroid. Let the set $E$ be the set of 255 centroids of nonempty subsimplices of the 7-simplex, now treated as vectors in a vector space (they are vectors from the 7-centroid at the origin to their positions on the faces of the 7-simplex). There is a matroid $M$ represented by $E$ - the closure $\langle A\rangle$ on a subset $A$ of $E$ is defined by adjoining to $A$ the other centroids in $E$ which are in the linear span of $A$. [Hopefully I have my terminology correct, I am just learning about matroids. Further, I hope that introducing the matroid language clarifies, rather than confuses. Please comment with any suggestions.]

The problem of counting the 3-planes above can be reformulated as finding the rank 3 flats of $M$. The problem of finding 3-sections up to equivalence is then finding the orbit sets of these flats under the obvious action of the group of permutations of 8 letters $S_8$.

Let me work out the case of 1- and 2-sections in a 3d simplex. Let the vectors to each of the vertices of the 3 simplex be $e_1,e_2,e_3,e_4$ and note that $e_1+e_2+e_3+e_4=0$.

The elements of the set $E$ of centroids are in one to one correspondence with nonemepty subsets of the set {1,2,3,4}. For instance {1,2} corresponds to $\frac{e_1+e_2}{2}$, the centroid of the 1-face whose vertices are $e_1$ and $e_2$. I find this combinatorial notation a little easier to work with than keeping track of the detailed geometry.

As I sketched out in my "preliminary thoughts", there is a duality between the centroid of a k-face and the centroid of the (2-k)-faces opposite them. What I meant by this is just that this pair of centroids lie on a line, i.e. are linearly dependent. This fact follows from the single relation $e_1+e_2+e_3+e_4=0$ above. In the subset notation, this corresponds to a duality between a subset and its complement in {1,2,3,4}, e.g. {1} and {2,3,4}. In matroid language, this just means that the closure $\langle\{1\}\rangle$ must contain {2,3,4} as well.

From this, it follows that the set of 1-sections (rank 1 flats of $M$) is in bijection with the partitions of {1,2,3,4} into 2 strict subsets. (We must also include {1,2,3,4} in every flat, since it represents the zero vector).

It's easy to see that there are 4+3=7 of these:
{{1},{2,3,4},{1,2,3,4}}, {{2},{1,3,4},{1,2,3,4}}, {{3},{1,2,4},{1,2,3,4}}, and {{4},{1,2,3},{1,2,3,4}}
{{1,3},{2,4},{1,2,3,4}}, {{1,2},{3,4},{1,2,3,4}}, and {{1,4},{2,3},{1,2,3,4}}

These 7 break into two orbits (of size 4 and 3) under the action of $S_4$, so there are only two inequivalent 1-sections. These are the center and lower left picture in Yaroslav's images.

The set of (non-degenerate) 2-sections (rank 2 flats of $M$) is more intricate, but not hard to enumerate "by hand" by considering closures of subsets of the power set of {1,2,3,4}.

Rather than write out in more detail the closure operation, let me give an example of finding the closure of a subset. Suppose we'd like to find the closure of {{1},{1,2}}, which is certainly a rank 2 subset of $M$. We must adjoin {2} because the complement of {1} in {1,2} is {2} (this corresponds to the fact that $e_2$ is in the linear span of $\{e_1,(e_1+e_2)/2\}$). Similarly, we adjoin {3,4} and {1,3,4} and {2,3,4} as they are the complements of {1,2}, {2}, and {1}, respectively in {1,2,3,4}. I hope that you can see that this arises from the relation $e_1+e_2+e_3+e_4=0$. Finally, we adjoin {1,2,3,4}, which represents the 0 vector; though again, this is just a notational artifact.

Eventually, we get:
{{1},{2},{1,2},{3,4},{1,3,4},{2,3,4},{1,2,3,4}} and 5 other permutations (see any of the triangles in Yaroslav's pictures)
{{1,2},{2,3},{3,4},{1,4},{1,2,3,4}} and 2 other permutations (the square in Yaroslav's pictures)

Unfortunately, my combinatorics is not good enough to extrapolate up to the 7-simplex. But perhaps someone else can see the pattern?

Computation?

Alternatively, you might try inputting this matroid into Macek or Oid and doing the computation in those systems? It also looks like SAGE has some matroid functionality as well see this link -- though for this problem, the computation needed is linear algebra, and ought to be doable in Mathematica as well.

However, I can't at the moment extract from my response an algorithm much better than brute force; particularly, I don't know a good way to count orbit sets of the linear spans under $S_8$... Any ideas?