4
$\begingroup$

Let $X=\{1,\cdots,2n\}$. Call a $2$-subset of $X$ a duad. Let $D$ be the collection of all $X$'s duads. Call a partition of $X$ into duads a syntheme. Call a partition of $D$ into (necessarily $2n-1$) synthemes a "synthematical total," or simply total for short.

So for example with $n=2$, $\{1,2\}$ would be a duad, $\{\{1,2\},\{3,4\}\}$ a syntheme and $$\{~\{\{1,2\},\{3,4\}\},~\{\{1,3\},\{2,4\}\},~\{\{1,4\},\{2,3\}\}~\}$$ is the only synthematic total for $n=2$, and includes all of the synthemes. Note the action of $S_4$ on this total gives us the exceptional homomorphism $S_4\to S_3$. In general, $S_{2n}$ acts transitively on the set of synthemes with point-stabilizer an internal wreath product $\mathbb{Z}_2\wr S_n$, which means the number of synthemes will be $(2n)!/(2^n n!)$.

Question I. What is the number $t(n)$ of synthematic totals as a function of $n$?

(The terms duad, syntheme and total come from Sylvester IIRC.)

We see $t(1)=1$ and $t(2)=1$ by inspection. One can derive $t(3)=6$ with some geometric reasoning; see John Baez's webpage write-up or Peter Cameron's blog post. The story behind $t(3)=6$ is that of the construction of the (unique) outer automorphism of $S_6$. (The action of $S_6$ induces an action on the set of $6$ totals, which as an automorphism $S_6\to S_6$ is outer.) So:

Question II: How does $S_{2n}$ act on the set of totals?

Recall every $G$-set is a disjoint union of orbits, and the isomorphism type (as a $G$-set) of an orbit is determined by the conjugacy class of its point-stabilizers, which allows us to completely (if abstractly) characterize a group action.

The $n=3$ case also gives rise to the so-called Tutte-Coxeter graph, so:

Bonus question I: Do higher values of $n$ yield additional exotic incidence structures?

And might as well stick this in:

Bonus question II: Does anything similarly interesting happen with $k$-subsets for $k>2$?


In the case of $n=4$, one of the orbits is in bijection with the set of distinct Fano planes.

Under the regular representation of $\mathbb{Z}_2^3$, each vector induces a translation map which, as a permutation of the underlying set is a product of four $2$-cycles or equivalently a syntheme. The set of vectors thus corresponds to a set of synthemes which happens to be a synthematic total.

The totals that can be achieved in this way correspond to the conjugacy class of this copy of $\mathbb{F}_2^3$ sitting inside $S_8$. In this orbit, the stabilizer will be the normalizer inside $S_8$, which will be the affine group $\mathrm{Aff}(3,2)=\mathbb{F}_2^3\rtimes\mathrm{GL}(2,3)$. If we pick an element of $\{1,\cdots,8\}$ to be the "origin," we have an isomorphism of $S_7$-sets

$$ S_8/\mathrm{Aff}(2,3)\cong S_7/\mathrm{GL}(2,3) $$

since $S_8$ is the knit product (aka Zappa–Szép product) of $S_7$ and the internal copy of $\mathbb{F}_2^3$.

pjs36 in the comments raises the question if $S_{2n}$ always acts transitively on the set of synthematic totals. Unfortunately, I can't think of a good reason for that to be the case.

$\endgroup$
  • 1
    $\begingroup$ I think this is a fun collection of things to think about. I briefly ran into sythemes (though I had no name for them) thinking about "orthogonal permutations," which resulted in this neat reference about division algebras. My route in was Hadamard matrices, first constructed by Sylvester. $\endgroup$ – pjs36 Jun 3 '17 at 14:04
  • 1
    $\begingroup$ I wanted the next term to check OEIS. So instead of thinking, I tried to get the software Sage to help me out. It appears $t(4) = 30$. For $n = 5$ there are a lot of computations to be made and it's really taking its time churning stuff out, but it seems weird so far. If correct, $t(5) \ge 7500$, which is an extraordinary jump from $t(4) = 30$: A measly $0.1\%$ of $S_8$ generated new totals, then up to more than $2\%$ of $S_{10}$. Sidenote, I'm hoping $t(4) = \#\ \text{distinct Fano planes}$ isn't a coincidence. Which reminds me, I wonder if the tag combinatorial-designs applies. $\endgroup$ – pjs36 Jun 4 '17 at 2:32
  • $\begingroup$ @pjs36 Aha, that Fano plane observation is very curious... Thanks for progress! $\endgroup$ – arctic tern Jun 4 '17 at 2:46
  • $\begingroup$ That's really nice! Your approach did give me an idea for computing $t(5)$, also: I had been letting $S_{2n}$ act on a "seed" total, and keeping a list of unique ones. It turns out, computers don't like running thousands of equality checks for millions of group elements (sorry computer!). So instead, I found the size of the stabilizer subgroup and things ran much more smoothly. But, the stabilizer subgroup came out to have size $4$, which seems impossibly small. This method does give the right $t$-values for $n = 3, 4$, so I don't know what to think... $\endgroup$ – pjs36 Jun 4 '17 at 20:16
  • $\begingroup$ Afterthought: is it possible that there's more than one $S_{2n}$-orbit of sythematical totals? I just realized my approaches assumes the action is transitive. $\endgroup$ – pjs36 Jun 4 '17 at 20:27
2
$\begingroup$

It turns out this problem is fairly well-studied, under a different guise: 1-factorizations of the complete graph with $2n$ nodes, and a few entries are given in OEIS A000438:

1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040

for $n = 1, 2, \ldots$. It seems to be a hard enough problem that no formula is known.

Isomorphism classes of these $1$-factorizations have also been enumerated for small values of $n$, but again no formula seems to be known. Here are the terms from OEIS A000474, for the same values of $n$:

1, 1, 1, 6, 396, 526915620, 1132835421602062347

I was not aware of this aspect of the problem. I only found it by generating all $6{,}240$ synthematic totals for $n = 4$, and searching OEIS!

One further note, which I'll introduce by copying from the Wikipedia page on graph factorization:

A perfect pair from a 1-factorization is a pair of 1-factors whose union induces a Hamiltonian cycle.

A perfect 1-factorization (P1F) of a graph is a 1-factorization having the property that every pair of 1-factors is a perfect pair. A perfect 1-factorization should not be confused with a perfect matching (also called a 1-factor).

That is (mixing notation), a perfect 1-factorization is one in which the union of any pair of synthemes forms a cycle. According to the page, it is currently only a conjecture that $K_{2n}$ has a perfect 1-factorization for all $n$.


Since I have them, I might as well list the isomorphism types, as well as their orbit sizes and stabilizer sizes, when $S_{8}$ acts on the underlying set $\{1,2, \ldots, 8\}$.

Here's a table on isomorphism classes, in ascending order of orbit size:

\begin{array}{c|c|c|c|c|c|c} \text{orbit size} & 30 & 420 & 630 & 960 & 1680 & 2520 \\ \hline \text{stabilizer size} & 1344 & 96 & 64 & 42 & 24 & 16 \end{array}

The stabilizers are, respectively:

And, everyone's favorite thing, pictures! Below are representatives from each orbit (in the same order as the table above), as well as a depiction of the total. I've tried to display as many symmetries of the total as possible, in each depiction -- I'm quite happy with several of them (notably the septagon, which immediately suggests a generalization for all values of $n$).

 Stabilizer size 1344:
 {{2, 5}, {4, 7}, {8, 3}, {1, 6}}
 {{3, 7}, {8, 4}, {1, 5}, {2, 6}}
 {{5, 6}, {8, 7}, {3, 4}, {1, 2}}
 {{8, 1}, {3, 6}, {4, 5}, {2, 7}}
 {{3, 5}, {8, 2}, {4, 6}, {1, 7}}
 {{2, 3}, {8, 5}, {6, 7}, {1, 4}}
 {{1, 3}, {2, 4}, {5, 7}, {8, 6}}

1344 symmetries

 Stabilizer size 96
 {{1, 7}, {4, 6}, {2, 5}, {8, 3}}
 {{2, 3}, {8, 5}, {1, 6}, {4, 7}}
 {{2, 4}, {8, 7}, {1, 5}, {3, 6}}
 {{1, 3}, {5, 6}, {8, 4}, {2, 7}}
 {{5, 7}, {3, 4}, {2, 6}, {8, 1}}
 {{8, 6}, {1, 2}, {3, 7}, {4, 5}}
 {{8, 2}, {6, 7}, {3, 5}, {1, 4}}

96 automorphisms

 Stabilizer size 64:
 {{2, 4}, {8, 6}, {1, 5}, {3, 7}}
 {{2, 5}, {4, 7}, {8, 3}, {1, 6}}
 {{5, 6}, {8, 7}, {3, 4}, {1, 2}}
 {{8, 1}, {3, 6}, {4, 5}, {2, 7}}
 {{3, 5}, {8, 2}, {4, 6}, {1, 7}}
 {{2, 3}, {8, 5}, {6, 7}, {1, 4}}
 {{1, 3}, {5, 7}, {2, 6}, {8, 4}}

64 automorphisms

 Stabilizer size 42:
 {{1, 7}, {2, 6}, {3, 5}, {8, 4}}
 {{8, 1}, {3, 6}, {4, 5}, {2, 7}}
 {{3, 4}, {1, 6}, {2, 5}, {8, 7}}
 {{2, 4}, {1, 5}, {6, 7}, {8, 3}}
 {{5, 7}, {8, 6}, {2, 3}, {1, 4}}
 {{1, 2}, {3, 7}, {8, 5}, {4, 6}}
 {{1, 3}, {5, 6}, {8, 2}, {4, 7}}

42 automorphisms

 Stabilizer size 24:
 {{1, 7}, {2, 6}, {3, 5}, {8, 4}}
 {{5, 7}, {8, 6}, {2, 3}, {1, 4}}
 {{3, 4}, {1, 6}, {2, 5}, {8, 7}}
 {{8, 2}, {1, 5}, {4, 6}, {3, 7}}
 {{1, 3}, {2, 4}, {8, 5}, {6, 7}}
 {{8, 1}, {3, 6}, {4, 5}, {2, 7}}
 {{4, 7}, {5, 6}, {8, 3}, {1, 2}}

24 automorphisms

 Stabilizer size 16:
 (cube)                               (octagon)
 {{5, 6}, {8, 2}, {3, 4}, {1, 7}}     {{2, 3}, {8, 1}, {6, 7}, {4, 5}}
 {{1, 3}, {2, 4}, {5, 7}, {8, 6}}     {{1, 5}, {2, 7}, {8, 4}, {3, 6}}
 {{6, 7}, {2, 5}, {8, 3}, {1, 4}}     {{1, 3}, {5, 7}, {8, 2}, {4, 6}}
 {{3, 7}, {8, 4}, {1, 5}, {2, 6}}     {{2, 6}, {1, 4}, {8, 5}, {3, 7}}
 {{1, 2}, {3, 5}, {4, 6}, {8, 7}}     {{5, 6}, {8, 7}, {3, 4}, {1, 2}}
 {{8, 1}, {3, 6}, {4, 5}, {2, 7}}     {{2, 4}, {1, 7}, {3, 5}, {8, 6}}
 {{2, 3}, {8, 5}, {1, 6}, {4, 7}}     {{2, 5}, {4, 7}, {8, 3}, {1, 6}}

16 automorphisms

$\endgroup$
  • $\begingroup$ Shown algebraically in the question, the orbit of the first kind of total (with stabilizer size 1344) is in bijection with distinct Fano planes. Here is a combinatorial bijection: The points are the $7$ synthemes, the lines are the sets of $3$ synthemes whose union is disconnected. For example, the red, green, and grey totals contain all edges & diagonals of the left & right faces of the cube, so $\{\text{red, green, grey}\}$ would be one line this Fano plane. If you prefer numerical labels, label each syntheme by the vertex connected to 8 (so the blue syntheme is 1, orange 2, etc). $\endgroup$ – pjs36 Jun 28 '17 at 13:57

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.