Listing all interesting sections of a tetrahedron

Question

Answer update, 12/22: Using Peter Shor's observation that there's a homomorphism between distinct sections and permutations of objects on the cube, list all such permutations by representing a group of cube symmetries as a subgroup of SymmetricGroup[8] and using GroupElements/Permute, find centroid assignments using Mathematica's SAT solver, select point sets with distinct singular values, few more details and complete code given here

Question

An interesting 2D section is a plane that goes through the center of a regular 3D simplex and 2 other points each of which is a centroid of some non-empty subset of vertices. It is defined by two subsets of vertices. For instance {{1},{1,2}} gives a plane defined by 3 points -- center of the tetrahedron, first vertex, and average of first and second vertices.

An interesting set of sections is a set in which no two sections define the same plane under vertex relabeling. For instance, set {{{1},{2}},{{3},{4}}} is not interesting. Is there an efficient approach to finding an interesting set of interesting sections? I need something that could generalize to an analogous problem for 3D sections of 7D simplex, and finish overnight.

My attempted approach is below. One problem is that if you ignore geometry, some equivalent sections are going to be retained, so I get 10 sections instead of 3. A bigger problem is that I used brute-force and it definitely doesn't scale and (needs 10^17 comparisons for 7D simplex)

_{(source: yaroslavvb.com)}

Here's the Mathematica code to generate picture above.

entropy[vec_] := Total[Table[p Log[p], {p, vec}]];
hadamard = KroneckerProduct @@ Table[{{1, 1}, {1, -1}}, {2}];
(* rows of hadamard matrix give simplex vertex coordinates *)

vertices = hadamard;
invHad = Inverse[hadamard];
m = {m1, m2, m3, m4};
vs = Range[4];

(* take a set of vertex averages, generate all combinations arising \
from labeling of vertices *)
vertexPermutations[set_] := (
   newSets = set /. Thread[vs -> #] & /@ Permutations[vs];
   Map[Sort, newSets, {2}]
   );
(* anchors used to define a section plane *)

sectionAnchors = Subsets[{1, 2, 3, 4}, {1, 3}];
(* all sets of anchor combinations with centroid anchor always \
included *)
anchorSets = Subsets[sectionAnchors, {2}];
anchorSets = Prepend[#, {1, 2, 3, 4}] & /@ anchorSets;
anchorSets = Map[Sort, anchorSets, {2}];
setEquivalent[set1_, set2_] := MemberQ[vertexPermutations[set1], set2];
equivalenceMatrix = 
  Table[Boole[setEquivalent[set1, set2]], {set1, anchorSets}, {set2, 
    anchorSets}];
Needs["GraphUtilities`"];
(* Representatives of "vertex-relabeling" equivalence classes of \
ancher sets *)
reps = First /@ StrongComponents[equivalenceMatrix];

average[verts_] := Total[vertices[[#]] & /@ verts]/Length[verts];
makeSection2D[vars_, {p0_, p1_, p2_}] := Module[{},
   v1 = p1 - p0 // Normalize;
   v2 = p2 - p0;
   v2 = v2 - (v1.v2) v1 // Normalize;
   Thread[vars -> (p0 + v1 x + v2 y)]
   ];

plotSection2D[f_, pointset_] := (
   simplex = 
    Graphics3D[{Yellow, Opacity[.2], 
      GraphicsComplex[Transpose@Rest@hadamard, 
       Polygon[Subsets[{1, 2, 3, 4}, {3}]]]}];
   anchors = average /@ pointset;
   section = makeSection2D[m, anchors];
   rf = Function @@ ({{x, y, z, u, v}, 
       And @@ Thread[invHad.{1, x, y, z} > 0]});
   mf = Function @@ {{p1, p2, p3, x, y}, f[invHad.m /. section]};
   sectionPlot = 
    ParametricPlot3D @@ {Rest[m] /. section, {x, -3, 3}, {y, -3, 3}, 
      RegionFunction -> rf, MeshFunctions -> {mf}};
   anchorPlot = Graphics3D[Sphere[Rest[#], .05] & /@ anchors];
   Show[simplex, sectionPlot, anchorPlot]
   );
plots = Table[
   plotSection2D[entropy, anchorSets[[rep]]], {rep, reps}];
GraphicsGrid[Partition[plots, 3]]

Answer 1

The correct programming solution is, in outline:

• Observe that centers come in projective pairs -- so identify and only retain the half of the centers that are in one or the other hemispherical covers of the set of centers. Pairs are set complements of each other. An example rule: all subsets containing vertex 1, and of those on the "equator", those containing vertex 2, and on that set's "equator", those containing vertex 3, and so on recursively keeping the boundary half adjacent to the smallest indexed vertex.
• Observe that for every subsimplex, either the subsimplex is adjacent to vertex 1 or it is of distance 1 away from simplex. (Cause: each new vertex in the tetrahedron is attached to every previous vertex of the tetrahedron -- consequently every subsimplex is either incident on vertex 1 or vertex 1 is connected to every vertex in the simplex.) Consequently there are only two populations of each kind of subsimplex (with respect to a specified vertex). (We can replace this observation with the decision to only keep the smaller member of each projective pair, but then the rule for labeling vertices is more complicated.)

• Tetrahedra are completely symmetric under permutation of vertex labels. Consequently, any "interesting section" is equivalent to another section containing only the leading segment of vertices -- i.e. can be identified among the vertices Range[1,n] for some n.

• Collecting the above, we find that there is a surjection from interesting section to a set of graphs. For each graph we must enumerate consistent vertex memberships (described later). Except for one vertex, the vertices of the graph come in pairs

  • The pair contains all centers of a given cardinality (all subsimplices of a given dimension).
  • One member of the pair contains centers incident on vertex 1.
  • The other member of the pair contains centers not incident on vertex 1.
  • The special vertex is either the center containing all vertices or its projective pair (the "empty center").
  • If a graph contains any member of a pair it must (at least) contain the member containing centers incident on 1 (or the vertices can be relabeled to make this so).
• The edges of the graph are weighted. The weight is the number of vertices shared by the two centers. There are restrictions on the weight based on the cardinality of the centers at each end and based on whether the two vertices are both first members, both second members, or are one of each. ("One of each" can't share vertex 1, for instance.)
• A graph is a complete subgraph on the set of vertices, containing the special vertex. For instance for the tetrahedron, a graph is a K_{3} on the set of vertices identified above, with one vertex the special one and with edge weights.
• A section is a graph with a consistent application of labels to the centers at the end of each edge (i.e. consistently labeled to respect the number of shared vertices indicated by the edge's weight and that each subset in one set of graph vertices contains vertex 1). A given graph can therefore represent multiple sections (via different labelings). (That there aren't as many options as it sounds as if there are will make sense in a second.)
• A section is not interesting if the matrix made from the coordinates of its centers has zero determinant.

In the case of three dimensions, with four vertices, we get the following sets (we use the short projective pair because there's enough visibility in this example to not necessitate the simpler vertex labeling rejection rule):
0: projective pair of {1,2,3,4}
1: {1}
1': {2},{3},{4}
2: {1,2},{1,3},{1,4}
2': projective pairs to 2 (so omitted)
3: projective pairs to 1' (so omitted)
3': projective pairs to 1 (so omitted)

Label constraints:
{0->x,x}
{0->x',x}
{1->1,1} -- disallowed: centers are not included twice
{1->1',0}
{1->2,1}
{2->2,1}
No other weights are possible with these graph vertices.

A graph is a K_{3} incident on 0, the following graphs survive the graph selection rules:
A: {0->1,1},{0->1',1},{1->1',0}
B: {0->2,2},{0->2,2},{2->2,1}

A has only one labeling: {1},{2},{} and is your triangular interesting set. This labeling does not have zero determinant.
B has only one labeling: {1,2},{1,3},{} and is your square interesting set. This labeling does not have zero determinant.

Converting to code is left as an exercise to the reader (because I have to leave for work).