Equational classes generated by 3-element magmas

Stream: Equational

[Stanley Burris]

A computer study of key properties of equational classes generated by 3-element magmas, properties studied by universal algebraists, appeared in a 1996 paper by Joel Berman and Stanley Burris in
A computer study of 3-element groupoids.
In Logic and Algebra, (The Proceedings of the Magari Conference),
edited by A. Ursini and P. Agliano (1996), 379 - 430, Marcel Dekker, Inc.

A PDF preprint can be found as item 58 on https://math.uwaterloo.ca/~snburris/htdocs/MYWORKS/publ.html

[Terence Tao]

Thanks for the reference! In our project, I guess computational power had advanced sufficiently since 1996 that we were able to brute force the consequences of 3-element and even 4-element magmas without needing to first classify them up to equivalence first, but if compute was more of a bottleneck then this work would certainly have been very helpful. In any event, I will add a reference to this work to our draft paper.

[Bruno Le Floch]

For the study of which equations have full spectrum, the 2-element magmas were very useful as many of them were such that their direct powers had submagmas of all sizes. The 3-element magmas were also quite useful, but a bit too diverse to make such sweeping statements. I'll see what I can learn from that reference, at least in terms of relevant terminology. For instance it might be possible to say that "any equation that is obeyed by this 3-element magma has full spectrum".

[Stanley Burris]

In our paper of 1996 we did not look at the spectrum of the equational class V(A) generated by a 3-element magma A, nor do I know any great results to apply here. After playing around with this a little I am now wondering : does V(A) has full spectrum imply that some 2-element B in V(A) is such that V(B) has full spectrum. If so then your work on 2-element magmas would cover the cases of equations with full spectra obtained from examining 3-element magmas.

[Bruno Le Floch]

If I understood correctly and did not mess up my calculations, [[0, 0, 1], [0, 2, 1], [1, 1, 1]] satisfies your requirements. It has a 2-element submagma {1,2} isomorphic to NAND that does not give full spectrum, but in the k-th power of the 3-element magma one finds a 2k+1 element submagma (then a direct product with some copies of NAND gives any number of elements). The submagma consists of elements of the form (0,\dots,0,x,\dots,x) with any number of zeros to begin with and otherwise all entries equal. For instance for k=3 it is {(0,0,0),(0,0,1),(0,0,2),(0,1,1),(0,2,2),(1,1,1),(2,2,2)}.

I was somewhat lucky: programmatically I was only able to reduce from 3330 three-element magmas to 397 candidates, and thankfully the first one was ok. The next two in my list, [[0, 0, 1], [0, 2, 1], [1, 1, 2]] and [[0, 0, 1], [0, 2, 1], [2, 1, 1]], do not seem to have full spectrum, but I don't know how to prove it. Maybe if we figure this out I can filter the list further.

[Stanley Burris]

Indeed you have found an excellent example. which I will call A, to refute my query. In B&B (my magma catalog with Berman) your example is 562, one of the representatives of the clone equivalence classes. Since it generates a congruence distributive variety V(A), all subdirectly irreducibles in the variety must be quotients of subalgebras of A. Thus the only 2-element algebra in V(A) is the 2-element subalgebra of A. and as you observe, it does not generate a variety with full spectrum. The natural question now is whether or not there is a magma equation that holds in A but not in any 2-element magma with full spectrum.

The next two magmas in your list have B&B catalog numbers 563 and 571. Since 571 is quasi-primal then all finite models of the variety it generates are products of it and its two-element subalgebra, so the spectrum of V(571) is the set of numbers of the form 2^m x 3^n. Definitely not full. 563 looks like a challenge to analyze. It is distinguished in the B&B catalog by having an enormously long Mal'cev term. I have long been inactive in universal algebra, but my guess is that analyzing the spectra of varieties generated by 3-element magmas, even determining which are full, could be a very challenging project.

[Stanley Burris]

(deleted)

[Stanley Burris]

I didn't see any mention of the famous results of V.L. Murskii --- my apologies if I am repeating items that have already been covered.

First there is his result from 1965 that the equational theory of the 3-element magma whose table is [ [0 0 0], [0 0 1], [0 2 2] ] does not have a finite basis (is not finitely axiomatizable).( All 2-element magmas have equational theories that are finitely based.)

Second, and more dramatic, is his result from 1975 that says almost all finite algebras are quasi-primal. I have not studied this result but my understanding is that it applies to magmas. Quasi-primal algebras are probably the most successful generalization of the 2-element Boolean algebra. If A is quasi-primal then it is hereditarily simple (all subalgebras are simple), its equational theory is finitely based, and the finite members of the variety V(A) that it generates are precisely the finite products of subalgebras of A, consequently its spectrum is far from being full. The infinite members of V(A) also have a powerful structure theorem, namely they are "Boolean products" of the simples.

For details on the universal algebra involved, but not Murskii's results, see the online 2012 free PDF copy of "A Course in Universal Algebra", originally published in 1981 by Springer Verlag. The 2012 version has several corrections to the original text, but does not make an attempt to bring the reader up to date. It does give the biblio info on the two papers of Murskii mentioned here.

[Terence Tao]

Thanks! I'll incorporate these references into the draft paper soon. EDIT: equational#1159

[Stanley Burris]

My colleague Joel Berman just informed me that the result is stronger than I stated above, namely almost all finite magma are idemprimal, so in addition to being quasi-primal they have no non-trivial proper submagmas and have only the trivial automorphism. For such a magma A the only finite members of V(A) are powers of A.

For references Joel said Cliff Bergman’s 2012 book Universal Algebra contains a very detailed proof of The probability that a random finite binar is idemprimal is 1. And another place where Murskii’s "almost all finite algebras”  results are proved in detail is in Volume III of Algebras, Lattices Varieties by Freese, McKenzie, McNulty and Taylor. Section 9.7 of that book it titled “Properties of ‘Almost all Finite Algebras’ ”.

A quick search on idemprimal led me to a 2020 Master's Thesis online by Florian Aichinger titled Probability in Universal Algebra that covers the topic following Bergman's book, proving the result for idemprimal groupoids.

[Кирилл Фролов]

There is a typo in commit https://github.com/teorth/equational_theories/commit/133c881ef09685cdeff94ca97a9ca3ec1dbe72bf
It duplicates line It was also shown in \cite{murskii-2} that ``almost all'' magmas $M$ (in a certain precise sense) are

[Terence Tao]

Thanks, I fixed it now.

[Shreyas Srinivas]

(deleted)

[Bjørn Kjos-Hanssen]

Speaking of subdirectly irreducible things, I proved that there exists a subdirectly irreducible, non-simple lattice here. The proof is 836 lines, any suggestions for shortening it? :upside_down:

[Bruno Le Floch]

The only relevant file to look at is the Lean file https://github.com/bjoernkjoshanssen/wollic25/blob/main/Wollic25/Basic.lean , is that correct?

[Bjørn Kjos-Hanssen]

Correct!

[Alex Meiburg]

This is a very short proof, if a very slow one to run.

[Alex Meiburg]

I think that some optimizations could maybe make it more reasonable though. As written, it is unreasonably slow.

[Bruno Le Floch]

Does the lattice really need to be built in terms of lcm and gcd? It seems like specifying the entries of meet and join essentially one by one should require less heavy machinery. Probably working with some custom type (syntax given by ChatGPT, sorry I didn't check right now).

inductive MyElements
| elt0
| elt1
| elt2
| elt3
| elt4

[Bjørn Kjos-Hanssen]

Hi @Alex Meiburg, nice! --- I guess you turned it into a computation whereas mine is halfway between computational and conceptual. @Bruno Le Floch yes maybe that'd be easier, I'm really not sure

[Bjørn Kjos-Hanssen]

Re. @Alex Meiburg's code, I recall native_decide not being sufficient if you want to say that the theorem is "proved"... but maybe decide works too.

[Alex Meiburg]

decide works too, but is even more unbearably slow :')

[Stanley Burris]

Let A be a finite magma such that V(A) is not CP (congruence permutable), i.e. does not have a Mal'cev term p(x,y,z).

Let Spec V(A) be the set of sizes of members of V(A).

From Corollary 13.7 page 189 of B&S we see that V(A) has infinitely many finite directly indecomposable members since it is not CP.

I think one can lightly rework the proof to obtain a stronger result, namely to show that the set of primes which have the property of dividing some number in Spec V(A) is infinite. Is there an example of a 3-element magma A with V(A) not CP and Spec V(A) not having a full spectrum, i.e., not {1,2,3,...}?

[Stanley Burris]

Here is a comment about an example examined by @Bruno Le Floch back on Feb 14 in the search for 3-element magmas which generate an equational class with full spectrum, likely a very difficult project. The example was
[[0, 0, 1], [0, 2, 1], [1, 1, 2]],
and he said that it does

not seem to have full spectrum, but I don't know how to prove it.

I spent a fair amount of time thinking about this magma, which I will call A, with little to show for it. But before I forget, let me record what I know here.

Thoughts on the spectrum of V(A).

From the B&B catalog this magma is simple and has a Malcev term (so the equational class is congruence permutable). Let B be the 2-element submagma on {1,2}. By Corollary 10.2, page 170 in B&S, all subalgebras of a finite power of A are isomorphic to some direct product A^j x B^k. In particular the free magma F(n) in the variety V(A) freely generated by n elements is a submagma of some finite power of A, and thus of the form A^j x B^k. From the B&B catalog
|F(1)| = 2 and |F(2)| = 324.
This means that up to isomorphism
F(1) is B and F(2) is A^4 x B^2.

If there are sizes of finite magma in the variety V(A) other than 2^a3^b then to find them we likely need to look at quotients of submagmas of powers of A, using the full strength of the theorem V(A) = HSP(A). The first number not of this form is 5, so can we find a magma M in V(A) of size 5?

One way to see if such a M exists is to compute F(m) starting with m = 1 and then to examine the congruences on F(m) to see if any yields a 5 element quotient. If there is no 5 element quotient for m \le 5 then 5 is not in the spectrum. But this algorithm looks like it would require enormous computational resources, more than I have.

[Stanley Burris]

This continues my observations on the 3-element magma A given by
[[0, 0, 1], [0, 2, 1], [1, 1, 2]],
and its 2-element submagma B given by
[[2, 1], [1, 2]].

Previously it was noted that all magma in SP(A) are of the form
A^j x B^k since V(A) is congruence permutable and A is hereditarily simple (i.e., both A and B are simple). If these are the only finite magmas in V(A) then 5 is not in the spectrum of V(A), and I wanted to determine, but did not succeed, if the latter is the case.

Free magma in V(A)

For any finite A and positive integer n there is a brute force algorithm to determine if n is in the spectrum of V(A), namely generate the finite free magma F(m) on m free generators in V(A), starting with m = 1, and see if there is a congruence on F(m) that gives a quotient with n elements. As long as no such congruence is found then generate F(m) for the next m, up to m = n. If some F(m) has a quotient of size n then n is in the spectrum of V(A). If no F(m) has an n-element quotient for m \le n then n is not in the spectrum of V(A).

A standard method for generating F(n) in V(A).
Choose J large enough so that one has in A^J elements f_1 ,..., f_n such that the collection of tuples <f_1(j), ..., f_n(j)>, j \in J, gives every possible n-tuple of elements from A. Then the submagma of A^J generated by f_1 ,..., f_n is isomorphic to F(n).

Thus F(n) is, up to isomorphism, a submagma of A ^{ |A|^n}, and its cardinality |F(n)| is bounded by |A|^{ |A|^n}.

If A is primal, for example,
[[1, 0, 0], [0, 2, 0], [0,0,0]],
then the size of F(n) is actually this upper bound which grows doubly exponentially with n.
Another primal example is the 2-element Boolean algebra.

Returning to the original A above found by @Bruno Le Floch , my weakly supported guess is that
F(n) is A^p(n) x B^n
where p(n) = 3^n - 2^n - 1.
This would give
|F(1)| = 2
|F(2)| = 324
|F(3)| = 3,099,363,912.
The first two sizes agree with the B&B catalog, but |F(3)| was not calculated there. It makes the brute force approach to determining if 5 is in the spectrum of V(A) look unlikely to be within current computational capabilities. A clever insight is needed!

[Bruno Le Floch]

5 is not in the spectrum. Indeed, A obeys laws 43, 244743, 295304, 618376 (and many more of orders ≤6), namely x◇y=y◇x, x = S(x)◇(x◇S(x◇y)), x=(y◇S(x))◇(x◇(y◇S(x))), x◇y=x◇(y◇S(x◇y)) where S:x↦x◇x is the squaring map. By a mace4 run there is no magma of size 5 satisfying these laws. To find that, I looped through all equations of order ≤6 (order 4 is not enough), testing if B obeys them, then if A obeys them (it's faster to test for B first). Then called the ATP with the resulting huge list of 113841 equations. Then reduced the list by hand to four equations.

[Stanley Burris]

@Bruno Le Floch I am impressed, and will sleep better knowing that my question has been resolved! One could design a project to do for small magmas what one has done for small magma equations, namely to determine the graph of A_1 --> A_2, defined to mean A_2 is in V(A_1). But I suspect that even for magmas of size at most 3 this could be a brutal undertaking.

[Stanley Burris]

The possible spectra of a variety generated by a 3-element magma continues to fascinate me. I now suspect the magma $\mathbf{A}$ with table
[[0, 0, 1], [0, 2, 1], [1, 1, 2]]
generates a variety where the only finite models are products of $\mathbf{A}$ and its 2-element submagma $\mathbf{B}$, so the spectrum would be the collection of numbers $2^m3^n$. I will say more on this at a later time.

An interesting, possibly not so well known method of constructing subdirect powers of a non-simple finite algebra $\mathbf{A}$ is based on generalizing the fact that a congruence $\theta$ of $\mathbf{A}$ is the carrier of a subalgebra of $\mathbf{A}^2$. For $J$ a finite set (or use $n$ along with $n = \{0,\ldots,n-1\}$), define $B$ to be the set $\{f \in A^J : f(i) \theta f(j) \textrm{ for all } i,j \in J\}$. Then $B$ is the carrier of a subalgebra $\mathbf{B}$ of $\mathbf{A}^J$, and the size of $\mathbf{B}$ is
$c_1^n + \cdots + c_k^n$
where $c_i$ is the size of the coset $C_i$ of $\theta$, the cosets being $C_1,\ldots, C_k$ and $n$ is the cardinality of $J$.

Now let's apply this to the 3-element magma $\mathcal M$ with table
[[0, 1, 2], [1, 0, 1], [2, 1, 0]]
With a 2-element subalgebra clearly every $2^i3^j$ is in the spectrum of $V(\mathcal{M})$.
Since there is a congruence $\theta$ with the two cosets $\{1\}$ and $\{0,2\}$,
the congruence construction just described says that $2^i + 1$ is also in the spectrum. Thus we have at least the 5 Fermat primes in the spectrum. Also, by a theorem of Polya, the set of primes $p$ such that $p$ divides some $2^i + 1$ is infinite, so the spectrum is not finitely generated as a monoid. This analysis of the spectrum applies to every non-simple 3-element magma.

The obvious question: "Can one clearly describe the spectrum, its generators; is the spectrum full?" A wildly optimistic conjecture is that the only possible spectra for varieties generated by a 3-element magma are one of:
1) $\{3^n : n \ge 0\}$
2) $\{2^m3^n : m,n \ge 0$
3) the spectrum is full, i.e., is the set of positive integers.

This would augment the fact that for a variety generated by a 2-element magma the spectrum is either $\{2^n : n \ge 0\}$ or it is full.