Simple and (sub)directly irreducible spectrum

Stream: Equational

[Bruno Le Floch]

I've analyzed the finite simple and (sub)directly irreducible spectra of equations of order up to 2. For a law A, I denote by

• Sim the set of sizes of simple A-magmas (namely with no non-trivial quotient).
• Sub the set of sizes of subdirectly irreducible A-magmas (namely that do not inject into the product of their quotients).
• Dir the set of sizes of directly irreducible A-magmas.

The singleton is «too simple to be simple», so Sim ⊂ Sub ⊂ Dir ⊂ [2,∞). The set of all A-magma sizes is exactly the set of products of elements in Dir, so if Dir contains Primes={2,3,5,7,11,...} then the equation has full spectrum. Equation numbers in parentheses are either dual or equivalent to equations with lower numbers.

• Sim=Sub=Dir=[2,∞): equations 1, 3, 8, 9, 10, 11, 14, 16, (23, 25, 26, 28, 29, 31), 40, 43.
• Sim=Primes, Sub=Dir=[2,∞): equations 38, (39, 42, 45) describing sets equipped with some function.
• Sim={2}, Sub={2,3}, Dir=[2,∞): equations 13, (19, 24, 27) describing sets equipped with an involution.
• Sim=Sub={2}, Dir=Primes: equations 4, (5, 12, 34) describing sets, and 41, (44, 46) describing pointed sets.
• Sim=Sub=Dir=∅, All={1}: equation 2, (6,7,15,17,18,20,21,22,30,32,33,35,36,37).

(EDIT: 14 has been resolved and indeed it has full simple spectrum, as now indicated in the list above.)
I expect equations 14 (29) x=y*(x*y) to have Sim=Sub=Dir=[2,∞). The magmas are complicated to build so I only got the rather trivial observation that Primes ⊂ Sim using the linear magma x*y=-x-y. There seem to exist magmas with $0*0=0$ and $L_0=R_0^{-1}$ being cyclic permutations of the remaining elements. Such a magma is simple: it turns out that any equivalence relation on a 14-magma has all of its equivalence classes of the same size, so in particular a non-trivial relation will identify 0 to some other element, but then repeated applications of $L_0$ will identify 0 to all other elements in turn.

[Ben Gunby-Mann]

For the Putnam magmas you can get very slightly more than just primes using Steiner triple systems, which correspond to commutative idempotent Putnam magmas. Any quotient of a commutative idempotent magma must also be commutative and idempotent, so the only valid quotients of magmas corresponding to an STS also correspond to an STS.

If a quotient of an STS of size n is an STS of size k, all equivalence classes must be of size n/k. Furthermore, it follows from idempotence that these equivalence classes are closed under multiplication and thus form sub-STS's of size n/k. So for example you can get that $15\in Sim$, as every STS of size 15 is simple (the only nontrivial factorization, 3*5, contains elements not congruent to 1 or 3 modulo 6).

[Bruno Le Floch]

Besides primes, and non-factorizable elements of $(1+6\mathbb{N})\cup(3+6\mathbb{N})$, the spectrum of simple Putnam magmas (i.e. obeying equation 14) contains all sizes $n\equiv 2,5,11\mod 12$.

Consider an equivalence relation $\sim$ on a Putnam magma $M$. Since left multiplication and right multiplication by $x$ are inverses of each other, they are bijective (even in the infinite case), so they map equivalence classes to equivalence classes, and every equivalence class has the same cardinal. The quotient $M/{\sim}$ is a Putnam magma. If that magma has an idempotent element (or as a stronger condition if $M$ has an idempotent element) then that equivalence class is a Putnam submagma of $M$ so we have a «short exact sequence».

Here is a simple Putnam magma of size $n\equiv 2,5,11\mod 12$. We write $n=3k+2$ with $k\neq 2\mod 4$ and pick an idempotent quasigroup $(G,\circ)$ of size $k$ (which can be taken to be linear on $\mathbb{F}_{2^a}\times\mathbb{Z}/(2b+1)\mathbb{Z}$ where $k=2^a(2b+1)$). Then let $M=\{\pm\infty\}\cup G\times(\mathbb{Z}/3\mathbb{Z})$ and define

$$\begin{aligned} (\pm\infty)\diamond(\pm\infty) & = +\infty , \\ (\pm\infty)\diamond(\mp\infty) & = -\infty , \\ (\pm\infty)\diamond(x,i) & = (x,i\pm 1) , \\ (x,i)\diamond(x,i\pm 1) & = \pm\infty , \\ (x,i)\diamond(x,i) & = (x,i) , \\ (x,i)\diamond(y,i) & = (x\circ y,i+1) , \quad x\neq y , \\ (x,i)\diamond(z\circ x,i+1) & = (z,i) , \quad x\neq y , \\ (y\circ z,i)\diamond(y,i-1) & = (z,i-1) , \quad x\neq y . \end{aligned}$$

If I didn't mess up this defines a Putnam magma where only $-\infty$ is not idempotent. Since the number of idempotents in a direct product is the product of the numbers of idempotents in each factor, the magma cannot be a direct product.

Assume now that it has a non-trivial equivalence relation. Because of our general considerations, $-\infty\sim X$ for some $X\neq -\infty$. Squaring gives $+\infty = (-\infty)^2\equiv X^2=X\equiv -\infty$ so $+\infty\equiv-\infty$. Then we deduce $(x,i+1)\equiv(x,i-1)$ so $(x,i)\equiv(x,j)$ for all $i,j,x$. Thus, equivalence classes that do not contain $\pm\infty$ must be unions of sets $\{x\}\times(\mathbb{Z}/3\mathbb{Z})$, hence have cardinal a multiple of $3$. This does not divide the order of the Putnam magma. The only way out is that everything is in the same equivalence class. Every equivalence relation being trivial the magma is simple.

[Bruno Le Floch]

Hmm, a mace4 run shows that idempotent quasigroups of size 6 exist, which means my construction also gives a size-20 simple Putnam magma. More generally, if one can build an idempotent quasigroup of size $4m+2$ then the construction gives a simple Putnam magma of size $12m+8$.

[Bruno Le Floch]

The simple Putnam spectrum contains $4,25$ and more generally $p^2$ for any prime $p$ such that $Z^2-Z+1$ is irreducible mod $p$ (this includes $p=2,5,11$). The field $\mathbb{F}_{p^2}$ can be defined as $\mathbb{F}_p[Z]/(Z^2-Z+1)$, and this allows to define idempotent Putnam magmas $x\diamond y=Zx+(1-Z)y$, which we now show are simple. For any non-trivial equivalence relation, pick two (distinct) elements that are identified, $u\sim v$. Then $Zu=u\diamond 0\equiv v\diamond 0=Zv$. In addition, note that $((1-Z)y)\diamond(x\diamond 0) = x+y$, so if $x\equiv x'$ we have $x+y\equiv x'+y$ for any $y$, and in particular $x'-x\equiv 0$ and $k(x'-x)\equiv 0$ for any $k=0,1,2,\dots$. Together with the previous observation we learn that $(k+lZ)(v-u)\equiv 0$ for all $k,l=0,1,2,\dots$. Since $1,Z$ form a basis of $\mathbb{F}_{p^2}$ as a $\mathbb{F}_p$ vector space, the equivalence relation identifies everything to zero.

EDIT: Corrected the proof; this works on $\mathbb{F}_{p^2}$ but has no reason to work on $\mathbb{F}_{p^k}$ for $k>2$ so I removed that mention.

[Bruno Le Floch]

There exist simple Putnam magmas of all sizes greater than 1. (proof updated)
My ugly construction is based on disjoint unions of Putnam magmas and Kirkman triple systems, which exist for all sizes $6n+3$ by a 1971 paper of Ray-Chaudhuri and Wilson that I wasn't able to locate.

Let me call «snip» a simple non-idempotent Putnam magma, namely one with at least one non-idempotent element. The procedure below takes a snip of size $m$ and produces a snip of size $m+6n+3$ for any integer $n$ such that $6n+3>m$ (edited).

One can construct by hand snips of all prime sizes, as well as 6,8,9,10 (see below). Using only the snips of sizes 2,3,5,6,7,10 we complete most of the spectrum. Sorted by residue mod 6 of the resulting snips, this is as follows.

• From a snip of size 3 we get a snip of sizes $12+6\mathbb{N}$.
• From a snip of size 10 we get snips of sizes $25+6\mathbb{N}$.
• From a snip of size 5 we get snips of sizes $14+6\mathbb{N}$.
• From a snip of size 6 we get snips of sizes $15+6\mathbb{N}$.
• From a snip of size 7 we get snips of sizes $16+6\mathbb{N}$.
• From a snip of size 2 we get snips of sizes $5+6\mathbb{N}$.

This construction gives snips of all sizes greater than 1 except 4,8,9,13,19. The prime sizes 13,19 are known to have snips. For sizes 8,9 I got some explicit snips below. For size 4 there is no snip, but the linear construction above gives a simple Putnam magma (that happens to be unique and idempotent).

[Bruno Le Floch]

The basic snips from which all others are constructed are:

• the linear model $i\diamond j=1-i-j$ on $\mathbb{Z}/3\mathbb{Z}$;
• the linear model $i\diamond j=-i-j$ on $\mathbb{Z}/p\mathbb{Z}$ for prime $p\neq 3$ (it is simple because the size of equivalence classes has to divide the size of the magma);
• four explicit snips of sizes 6,8,9,10: they have $L_0(n-1)=1$ and $L_0(i)=i+1$ for $1\leq i\leq n-2$, thus are simple because if $0\sim x$ then $0=L_0(0)\sim L_0(x)$, and $L_0$ is a cyclic permutation so we end up with $0\sim\text{everything}$.

Explicit snips of sizes 6,8,9,10 with cyclic $L_0$

[[0,2,3,4,5,1],
 [5,1,0,2,3,4],
 [1,3,2,0,4,5],
 [2,4,1,5,0,3],
 [3,5,4,1,2,0],
 [4,0,5,3,1,2]]

[[0,2,3,4,5,6,7,1],
 [7,1,0,2,3,4,5,6],
 [1,3,2,0,6,5,4,7],
 [2,4,1,3,0,7,6,5],
 [3,5,6,1,7,0,2,4],
 [4,6,5,7,1,2,0,3],
 [5,7,4,6,2,1,3,0],
 [6,0,7,5,4,3,1,2]]

[[0,2,3,4,5,6,7,8,1],
 [8,1,0,2,3,4,5,7,6],
 [1,3,2,0,6,8,4,5,7],
 [2,4,1,3,0,7,8,6,5],
 [3,5,6,1,7,0,2,4,8],
 [4,6,7,8,1,5,0,3,2],
 [5,8,4,7,2,1,6,0,3],
 [6,7,8,5,4,2,3,1,0],
 [7,0,5,6,8,3,1,2,4]]

[[0,2,3,4,5,6,7,8,9,1],
 [9,1,0,2,3,4,5,6,7,8],
 [1,3,2,0,4,7,6,5,8,9],
 [2,4,1,3,0,8,9,7,5,6],
 [3,5,4,1,2,0,8,9,6,7],
 [4,6,7,8,1,9,0,2,3,5],
 [5,7,6,9,8,1,2,0,4,3],
 [6,8,5,7,9,2,1,3,0,4],
 [7,9,8,5,6,3,4,1,2,0],
 [8,0,9,6,7,5,3,4,1,2]]

[Bruno Le Floch]

The extension procedure.

Take a snip $(M,\circ)$ whose number of elements $m\geq 2$ is not a multiple of $3$. Take a Kirkman triple system on a set $S$ of cardinal $6n+3$. Then one can build a snip $M\sqcup S$ of size $6n+3+m$ as follows provided $m<6n+3$. The Kirkman triple system consists of triplets $(a_{ki},b_{ki},c_{ki})$ for $0\leq k\leq 3n$ and $0\leq i\leq 2n$, where $\{a_{ki},b_{ki},c_{ki}\mid 0\leq i\leq 2n\}=S$ for each $k$. For each $k$ define two permutations $\sigma_{2k}$ and $\sigma_{2k+1}=\sigma_{2k}^{-1}$ of the vertex set $S$ by

$$\sigma_{2k}(a_{ki}) = b_{ki} , \quad \sigma_{2k}(b_{ki}) = c_{ki} , \quad \sigma_{2k}(c_{ki}) = a_{ki} .$$

Each of these permutations consists of $2n+1$ three-cycles. Every pair $x\neq y\in S$ belongs to some triple hence there exists $z\in[0,6n+1]$ such that $y=\sigma_z(x)$. The third element of the triplet is then $\sigma_z^2(x)$. Then we consider an injection $\iota\colon M\to [0,6n+1]$, and we define the magma operation on $M\sqcup S$ by

$$x\diamond y = \begin{cases} x\circ y & \text{if } x,y\in M , \\ \sigma_{\iota(x)}(y) & \text{if } x\in M, y\in S , \\ \sigma_{\iota(y)}^{-1}(x) & \text{if } x\in S, y\in M , \\ \iota^{-1}(z) & \text{if } x\,y\in S \text{ and } y = \sigma_z(x) \text{ and } z\in\iota(M) , \\ \sigma_z^2(x) & \text{if } x\,y\in S \text{ and } y = \sigma_z(x) \text{ and } z\not\in\iota(M) , \\ x & \text{if } x=y\in S . \end{cases}$$

This is a Putnam magma. If $y\in M$ then $L_y\circ R_y=\mathrm{id}$ on $M$ by the first line and on $S$ by the next two lines. If $y\in S$ then $L_y\circ R_y=\mathrm{id}$ on $M$ by the second and fourth lines, and on $x\in S$ as follows. Write $x=\sigma_z^{-1}(y)$. If $z\in\iota(M)$ then $y\diamond(x\diamond y)=y\diamond\iota^{-1}(z)=\sigma_z^{-1}(y)=x$, while if $z\not\in\iota(M)$ then $y\diamond(x\diamond y)=y\diamond\sigma_z(y)=\sigma_z^2(y)=x$. It clearly is not idempotent since $M$ is a submagma.

Simplicity for $\{0,1\}\subset\iota(M)$.

Assume now $m\neq 0\mod 3$. Choose an injection such that $\{0,1\}\subset\iota(M)$. Now take a non-trivial equivalence relation $\sim$ on $M\sqcup S$. Pick a non-idempotent element $x\in M$. Being non-trivial, its equivalence class either contains some other element of $M$ or it contains some $y\in S$ (which is automatically idempotent) then $x\sim y=y^2\sim x^2$ which is another element of $M$ anyways. By simplicity of $M$ the equivalence class must thus identify all elements of $M$ together.

Next, consider $y\in S$. Using that $0,1\in\iota(M)$ we get

$$y = 0\diamond \sigma_0^{-1}(y) \sim 1\diamond \sigma_0^{-1}(y) = \sigma_1(\sigma_0^{-1}(y)) = \sigma_0(y)$$

which implies that the equivalence relation identifies orbits of $\sigma_0$. Next, for any $z\in\iota(M)$,

$$y \sim \sigma_0(y) = \iota^{-1}(0)\diamond y \sim \iota^{-1}(z)\diamond y = \sigma_z(y) .$$

Thus (again for any $z\in\iota(M)$),

$$y\sim y^2 = y\diamond\sigma_z(y) = \iota^{-1}(z) \in M ,$$

so we found that any element $y\in S$ is equivalent to any element in $M$, namely the equivalence class is all of $M\sqcup S$. The magma is thus simple, hence a snip.

[Bruno Le Floch]

(deleted)

[Bruno Le Floch]

Conclusion: equation 14 has full simple spectrum. (I've edited the above proof correspondingly.)
We now know the simple spectrum of all equations of order at most 2.
I certainly won't attempt the next order, given that this order was already quite hard and it is not central to the project as a whole.

[Terence Tao]

Perhaps worth writing up as a blueprint chapter? If you are willing, I can set up a formal task for this.

[Bruno Le Floch]

Yes please, especially given that for many of the equations I only stated the simple spectrum here without any proof, but I have some relevant notes for all of them.

It would make sense as well to have a blueprint chapter on the full spectrum problem (maybe it already exists?). The techniques used are completely different.

[Terence Tao]

equational#1052

[Alex Meiburg]

I'm a little late to this discussion - but there are two nonequivalent standard ways to view an STS as a structure with a commutative Putnam law, called "squags" and "sloops". (Words derived from "Steiner quasigroup" and "Steiner loop".)

Squags are what have been talked about here, where you have an element in your magma for each point in the STS, and if (x,y,z) is a triple then x*y=z; the case of x*x is filled in by making the law idempotent, so x*x=x.

Sloops offer an alternative completion. After setting x*y=z for all triples (x,y,z), you say that you have an identity element e, so e*x=x=x*e. By the Putnam law, we also have x*x=e, so the identity is the universal square.

These two completions satisfy equation 3 in our project (x*x=x) or equation 40 (x*x=y*y), respectively. And so squags ("idempotent commutative Putnam law magmas") and sloops ("commutative Putnam law magmas with identity") are both in a fairly natural 1-to-1 correspondence with Steiner triple systems. But, they different in cardinality by 1, due to the additional identity element. These both fall under TS-quasigroups.

What's funny is that these two distinct equational theories then give rise to two different category structures for Steiner triple systems, when viewed as an equational theory. Squags have the notion of "direct product" you would usually expect, that take STS's of cardinality m and n and give you a new STS of size m*n. Sloops give a different product, that take STS's of cardinality m and n and give you one of size m*n+m+n. They also have different unit elements under this product: for squags, it's the (trivial) one-element Steiner triple system, but for sloops it's the (even more trivial) zero-element Steiner triple system.

[Bruno Le Floch]

Thanks, that's really helpful!! I had realized that from an idempotent Putnam magma (not necessarily commutative) one could build a Putnam magma with one extra identity element by setting all squares equal, but had completely forgotten about it. This has a good chance of simplifying the proof of complete simple spectrum, I'll think about it when writing the blueprint chapter some time this week.