# The duad-syntheme-total construction for higher values of $n$

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.

• 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. – pjs36 Jun 3 '17 at 14:04
• 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. – pjs36 Jun 4 '17 at 2:32
• @pjs36 Aha, that Fano plane observation is very curious... Thanks for progress! – arctic tern Jun 4 '17 at 2:46
• 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... – pjs36 Jun 4 '17 at 20:16
• 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. – pjs36 Jun 4 '17 at 20:27

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:

• $\mathrm{Aff}(3, 2)$ (as in the original post),

• $D_8 \times C_2$ ($D_8$ being the dihedral group of order $8$).

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}}


 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}}


 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}}


 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}}


 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}}


 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}}


• 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). – pjs36 Jun 28 '17 at 13:57