Order 3 Spectra

Stream: Equational

[Ben Gunby-Mann]

I've been following this project on and off on the side, and though the following isn't relevant to the main thrust of the project, I thought I'd post it in case anyone else had thoughts.

Given that people have looked at both which equations have full spectra (which has been solved up to a fairly high order now as I recall?) and simple spectra (which is already difficult for order 2), I thought I'd take a look at the intermediately-difficult question of simply determining the spectrum of equations.

This question first becomes interesting at order 3 -- the only equation of order 2 that is not equivalent to equation 2 and doesn't have constant, left-, or right-absorptive magmas of every order is the Putnam law, which has full spectrum anyway using $x\cdot y=-x-y$. So every spectrum of order 2 is trivial or full.

I attached a short writeup, but the TL;DR is:

The potentially interesting (i.e. nontrivial and aren't satisfied by constant or absorptive) equations up to duality and (finite) equivalence are 63, 66, 73, 115, 167, and 168. We know 168 is the central groupoid law, whose spectrum is just the squares. Additionally, it's not difficult to show that 63 and 73 have the same spectra, as their magmas can be transformed into each other by replacing left-multiplication $L_x$ with its inverse $L_x^{-1}$.

So what's left at order 3 is 63, 66, 115, and 167. I was able to show that:

66 magmas exist if and only if there exists a Mendelsohn triple system of that size; that is, the spectrum of 66 is $\{n\in Z_{\geq 0}: n\equiv 0,1\pmod 3\}-\{6\}$. One direction is simple (idempotent 66 magmas are Mendelsohn triple systems) and for the other, one can show that $\{(x,y,z):x\neq y,\text{ } x\cdot y=Sz\}$ is an MTS for any 66 magma.

The spectrum of 167 is $\{n\in\mathbb{Z}_{\geq 0}: n\equiv 0,1\pmod 4\}$. One direction follows from the fact that $f: (x,y)\to (x\cdot y, y\cdot x)$ splits $\{(x,y): x\neq y\}$ into orbits of size 4, and thus $4|n^2-n$, and you can construct examples for all such $n$ by pairing up $\binom{[n]}{2}$ into pairs of pairs $(a,b)$ and $(c,d)$, and setting $a\cdot b=c$, $b\cdot a=d$, $c\cdot d=b$, and $d\cdot c=a$.

So the only remaining cases on order 3 are 63 (equivalently, 73) and 115. I don't know what to make of these, besides noting there are no modular obstructions to the spectrum of 115 (every arithmetic progression contains an element of its spectrum). (This follows from the fact that all MTS's give 115 magmas, and considering linear solutions.)

Order_3_spectra.pdf

[Bruno Le Floch]

That's great!

FYI The equivalence in Proposition 1 is stating that law 63 and 125 are parastrophically equivalent for quasigroups. If a magma has bijective left and right multiplications, one can define left and right divisions, and their duals, which gives six operations called parastrophes of each other. If a law for one operations is equivalent to a different law for its parastrophe, then the laws are called parastrophically equivalent.

Your observations relating law 66-magmas to Mendelsohn triples can be rephrased as follows: law 66 magmas (M,◇) are in one-to-one correspondence with idempotent semi-symmetric quasigroups (M,∘) (also called Mendelsohn quasigroup) characterized by law 4961, equipped with an involutive automorphism S: M→M. Here, x∘y = (x◇y)◇(x◇y) and S(x)=x◇x, and conversely, x◇y=S(x∘y).

I find the argument about law 167 very neat! In the construction of examples you wrote n≡1 instead of n≡0,1.

For law 115, I expect the spectrum to be [1,∞)∖{2,6}, checked with an ATP up to order 53. From Mendelsohn triples we have models of all sizes except 6 and 3k+2. The magmas I built using an ATP have the form {∞} ∪ ℤ/mℤ where m=3k+1, where ∞◇∞=∞ and i◇i = i+1 mod m for i∈ℤ/mℤ, and ∞◇i = i+C mod m and i◇∞ = i-C-1 mod m for some constant C, and with i◇j=i+f(j-i) except for one value of j-i for which i◇j=∞. The function f is all over the place. It might be better to see this by replacing ∞ by 0, and the squaring map i→i+1 by a multiplication map i→2i or so, but I don't understand why this would exist for all n=3k+1.

The Dupont law 63 seems much harder. For sizes 2,6,10 there are no magmas. For all sizes "0,1,3 mod 4 up to 100 except 29,41,47,71,87" there are linear models. Naive conjecture: the spectrum is {n≡0,1,3 mod 4}. Could there be some counting argument to rule out sizes 4k+2? How to build a nonlinear one to get size 29 and higher?

[Bruno Le Floch]

Linear models of law 63 come in two types, (a,b)=(-1,³√1) and (a,b)=(1-ψ,ψ) with ψ³-ψ+1=0. The first type is such that law 75 holds, x=y◇(y◇(y◇x)). Surprisingly, even a nonlinear model that I have of size 9 obeys this identity.

[Bruno Le Floch]

By Belousov, 1983, in a quasigroup satisfying law 63, defining the left division y:x as the unique solution of x=y◇(y:x) and x/y as the unique solution of x=(x/y)◇y, the maps φ:(x,y) ↦ (x◇y, y:x) and ψ:(z,w) ↦ (w/z, (w/z):z) are inverse bijections.

Ugly proof

First, ψ∘φ=id: the law 63 states y:x = x◇(x◇y) so x = (y:x) / (x◇y) = w / z, and then (w/z):z = x:(x◇y) = y. Second, φ∘ψ=id: one has x◇y = (w/z)*((w/z):z) = z by definition of :, and there remains to show ((w/z):z) : (w/z) = w, namely w/z = ((w/z):z) ◇ w. Denoting Y=(w/z):z and X=w/z we have X◇Y=z and X◇(X◇Y)=w and we want to prove X = (X:(X◇Y))◇(X◇(X◇Y)). This is simply law 63 for X,Y.

I have no idea if that bijection is useful. In linear models, it is (x,y) ↦ (ax+by, (x-ay)/b). Its powers are complicated. It might be possible to combine it with some left/right multiplications by a fixed element to get a nicer bijection whose fourth power is the identity, maybe eventually getting some mod 4 constraint on the magma size.

[Bruno Le Floch]

For what it's worth, here is my investigation of spectra for all 4694 laws: spectrum.pdf (EDIT: updated). Here is a summary of what we know about spectra and simple/subdirectly irreducible/directly irreducible spectra in json format: spectrum.json. There are around 30 (classes of) laws for which we don't know the spectrum, but probably some are still relatively easy. (EDIT: now 7 conjectures, 20 unknowns.)

[Bruno Le Floch]

One of the conjectures (because I know little about quadratic reciprocity) is that the spectrum of finite $\mathbb{Z}[i]$-modules consists of integers whose prime decomposition $n=2^{k_0}p_1^{k_1}\dots p_m^{k_m}$ is such that $p_i^{k_i}\equiv 1\mod 4$ (or equivalently that primes congruent to $3$ mod $4$ have even valuation).

[Ben Gunby-Mann]

Well, that certainly puts a damper on my attempt to prove that the 481 spectrum doesn't contain any multiples of 3!

For posterity (in case this helps in the construction direction and it's not already known), the main thing I noted about 481 is that if $f(x)=x\diamond e$, then for any $x,y,z$ with $x\diamond z=y$, we can construct a chain $\ldots,f^{-1}(x),f^{-1}(y),f^{-1}(z),x,y,z,f(x),f(y),f(z),f^2(x),f^2(y),f^2(z),\ldots$ (which due to finiteness must be periodic) such that for any three consecutive $a,b,c$ in the sequence, $a\diamond c=b$.

Since every pair of elements occurs two apart in exactly one such chain ($(x,y)$ appears in the chain $x,x\diamond y, y, \ldots$), and ignoring chains of the form $x,e,x,f(x),e,f(x),\ldots$, these chains partition $\{(x,y): x,y\neq e, x\neq y\}$, which has cardinality $(n-1)(n-2)$. I was hoping to show that chains of size not divisible by 3 don't work but I guess that hope was misplaced; maybe it does restrict the solution space somewhat for multiples of three, however. (Since if we get a cycle length not divisible by three we automatically get relations like $f^{k}(x)=y$, etc. among the generating elements.)

[Ben Gunby-Mann]

Another fairly simple but perhaps notable overall point (again, this might have already been discussed and I missed it) is that if a law allows for any nontrivial idempotent magmas (say of size k), then you can get an infinite subset of its spectrum by using that magma as a basis for an S(2,k,n) design for various n--first stipulate idempotence, and then define the remaining products by covering the edges with copies of k-cliques which correspond to the base magma. (Similarly to how the idempotent solution to 14 of size 3 allows us to turn Steiner systems into magmas.) In particular, we get infinite arithmetic progressions contained within the spectra.

For example, this works for any law of the form $x=f(x,y)$, which should always have a nontrivial idempotent translation-invariant magma over some $\mathbb{Z}/p\mathbb{Z}$ just by taking $x\diamond y=cx+(1-c)y$, whereupon $f(x,y)=(1-q(c))x+q(c)y$ for some polynomial $q$ and taking $p$ for which $q$ has a root.

[Kevin Buzzard]

Bruno Le Floch said:

One of the conjectures (because I know little about quadratic reciprocity) is that the spectrum of finite $\mathbb{Z}[i]$-modules consists of integers whose prime decomposition $n=2^{k_0}p_1^{k_1}\dots p_m^{k_m}$ is such that $p_i^{k_i}\equiv 1\mod 4$ (or equivalently that primes congruent to $3$ mod $4$ have even valuation).

I don't understand what you're saying here. Are you saying "conjecture: a finite abelian group of size $n$ with an action of $\Z[i]$ exists iff $n=\prod_i p_i^{e_i}$ where (only finitely many of the $e_i$ are positive and) $e_i$ is even whenever $p_i$ is 3 mod 4?" This is indeed true.

[Bruno Le Floch]

Ah, thanks Kevin. Here is a proof by a cardinality argument: first note that each prime factor is independent, then for $\bigoplus_k(\mathbb{Z}/p^{a_k}\mathbb{Z})$ note that $i^2=-1$ has a unique fixed point $0$ (except for $p=2$) so orbits of the action of $i$ other than $\{0\}$ have four elements. So $p^{\sum_k a_k}\equiv 1\mod 4$.

[Kevin Buzzard]

and for 2 you just say "Z/2Z with i acting trivially works, now just take products of this"

[Bruno Le Floch]

@Ben Gunby-Mann Your observations about 481 may be a useful rewriting of that law. It also applies to law 115 and law 667 and law 883 for the most part.

Regarding design theory, do you know for which n an S(2,k,n) design exists?

[Kevin Buzzard]

Bruno Le Floch said:

Ah, thanks Kevin. Here is a proof by a cardinality argument: first note that each prime factor is independent, then for $\bigoplus_k(\mathbb{Z}/p^{a_k}\mathbb{Z})$ note that $i^2=-1$ has a unique fixed point $0$ (except for $p=2$) so orbits of the action of $i$ other than $\{0\}$ have four elements. So $p^{\sum_k a_k}\equiv 1\mod 4$.

Oh actually you also need to go the other way, so you need to say "if p=3 mod 4 then there's a group of size p^2 with an action of $\Z[i]$" and the answer is $\Z[i]/p\Z[i]$, but you also need to say "if p=1 mod 4 then there's a group of size p with an action of $\Z[i]$" and this boils down to proving that $-1$ is a square mod $p$, which as you say is often bundled in with quadratic reciprocity as a "supplement" (a quick proof is "use ((p-1)/2)! and Wilson's theorem")

[Kevin Buzzard]

In fact ((p-1)/2)! is a "canonical" square root of -1 mod p when p=1 mod 4 (and a "canonical" square root of +1 mod p when p=3 mod 4)

[Ben Gunby-Mann]

@Bruno Le Floch it’s known to exist for all sufficiently large n as long as $k-1|n-1$ and $\binom{k}{2}|\binom{n}{2}$ (both of which are necessary). Maybe for r=2 designs like we have, more is known about small values of n, but I’m not sure. (Edited initial mistake)

[Bruno Le Floch]

Just to be sure, for law 14 this would only give large enough n=1,3 mod 6, whereas we know (via linear models) existence for all n? I think the technique is still useful for Dupont-related laws.

[Ben Gunby-Mann]

Yes, that's right. This technique is inherently limited (for one thing, it can only pick up on idempotent magmas).

A refinement (that I'm not sure exactly how to formalize, and can still only pick up on idempotent magmas) is that if you can construct a "partial" idempotent magma that satisfies the law for all pairs corresponding to, you can also tile the multiplication table with these. For example, the partial magma
[[0, 2, _], [_, 1, 0], [1, _, 2] satisfies Law 14 for all pairs $(x,y)$ for which the multiplication is defined, which is why we can tile with directed cycles (Mendelsohn triple systems) instead.

I tried doing something like this with the idempotent 63-magma of order 5 to see if I could get a partial magma that still worked, but I think you just end up having to fill out the entire multiplication table.

[Bruno Le Floch]

Actually your construction only works for certain if the equation has two variables: say you have a subexpression (x◇y)◇z, then x◇y is in the k-clique containing x-y, but then z can be taken outside that clique.

[Ben Gunby-Mann]

Argh, that's a good point that I'd missed. (I think in practice a lot of the 3-variable equations don't have nontrivial idempotent models, so this wasn't that useful anyway for them.)

[Bruno Le Floch]

@Kevin Buzzard When writing this up I realized there is a simpler construction: since the spectrum we found is the same as the set $\{a^2+b^2\mid a,b\in\mathbb{Z}\}$, we can just use $\mathbb{Z}[i]/(a+ib)\mathbb{Z}[i]$.

[Kevin Buzzard]

Sure but the proof that this set is the set of sums of two squares is made from the same ideas as the proof above. The proof above is self-contained.

[Bruno Le Floch]

I decided to combine into one set of notes, spectrum.pdf (for a blueprint chapter) earlier and current discussions on:

• which laws have full spectrum,
• what the spectrum is otherwise,
• the (sub)directly irreducible and simple spectrum,
• asymptotic number of magmas as the size goes to infinity.

[Bruno Le Floch]

I'll focus on writing more on the full spectrum problem, so if anyone wants to attack the following questions there will be no overlap with my effort:

• Build magmas obeying law 115 x=y◇((x◇x)◇y) of sizes 2 mod 3, see p.7.
• Use the graph theory description I found for magmas obeying law 1489 x = (y◇x) ◇ (y◇(x◇y)) to construct them of all large sizes, see p.11.
• Saturate the bound on the number of semi-symmetric quasigroups (law 14 x=y◇(x◇y)), see p.16.

[Bruno Le Floch]

Ben Gunby-Mann said:

Bruno Le Floch it’s known to exist for all sufficiently large n as long as $k-1|n-1$ and $\binom{k}{2}|\binom{n}{2}$ (both of which are necessary). Maybe for r=2 designs like we have, more is known about small values of n, but I’m not sure.

Actually, your idea of using designs can be generalized by using several block sizes. Let me be concrete: the two-variable Dupont law 63 has idempotent models of sizes 5,7,8,11 (and more). If we find a partition of the complete graph with n vertices into cliques of any of these sizes (not necessarily all the same) then we can define the magma operation on each clique using the known idempotent models. This avoids the congruence requirements on n.

I find it very difficult to find concrete examples of such mixed-block designs. The only examples I found are irrelevant for law 63: on the 10-element set [0,9], using cliques of sizes 3, 4: [[0,1,2,3],[0,4,5,6],[0,7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[1,6,8],[2,4,9],[2,6,7],[3,5,7],[3,4,8]], and on the 11-element set [0,10] using cliques of sizes 3,5: [[0,1,2,3,4],[0,5,6],[0,7,8],[0,9,10],[1,5,7],[1,6,9],[1,8,10],[2,5,8],[2,6,10],[2,7,9],[3,5,9],[3,6,8],[3,7,10],[4,5,10],[4,6,7],[4,8,9]].

[Ben Gunby-Mann]

Ah, that’s a really good point. I think this is fairly powerful, and in fact can probably show that the spectrum of 63 contains all sufficiently large integers by tiling with cliques of sizes 8 and 11. I can try to sketch this out when I get home later but essentially we need G that is decomposable into 11-cliques but has complement decomposable into 8-cliques. We can then try to fix a degree sequence that satisfies the resulting divisibility conditions, and prove that a random graph has this degree sequence with higher probability than it not being quasirandom, so there exists a graph with this degree sequence which is quasirandom. Then we can apply Thm 1.4 from https://arxiv.org/abs/1401.3665 to show both decompositions are possible.

(There probably is a much simpler argument here, but I’m not familiar enough with the literature here to know.)

EDIT: Yep the above is massive overkill, I think the paper “An existence theory for pairwise balanced designs, III” proves exactly what’s needed in Thm 1.

[Bruno Le Floch]

Thanks! I had come across that paper of Peter Keevash but not decoded it. It seems the tools there can also be used to count designs, so it looks like we can determine the asymptotics of the number of law 63 magmas. In fact, we may be able to say much more generally that any two-variable law with idempotent models has asymptotically full spectrum and growth rate $e^{Cn^2\log n}$ for some constant $C$ (e.g., $C=1/3$ for law 14, $C=1/2$ for 167 etc).

[Ben Gunby-Mann]

Well, 167 does not have asymptotically full spectrum, so it’s not true for all 2-variable equations with idempotent models. I’d definitely believe it works for a wide class, though.

[Bruno Le Floch]

Good point, sorry. That's because the basic idempotent models for 167 have $n(n-1)\equiv 0\mod 4$ so that modularity constraint remains in the construction. By the way, why did you plan to use 8-cliques and 11-cliques, instead of 5 and 7? EDIT: Ah, sorry we have two modularity constraints: given idempotent models of sizes $k,l,\dots$, we can only hope to build models of size $n$ provided $n-1$ is a sum of $k-1,l-1,\dots$ and $n(n-1)$ is a sum of $k(k-1),l(l-1),\dots$, so if we only want to use two of the sizes 5,7,8,11 we need to use 8,11.

[Bruno Le Floch]

I just saw your edit above about Wilson's paper. So the Dupont law 63 has asymptotically full spectrum. But to get the asymptotic count of magmas, we probably need Keevash's paper. Do you have an expectation for the resulting asymptotics? It seems that to maximize it we should use all clique sizes, and especially the smallest one 5?

[Ben Gunby-Mann]

I wrote up more formally the discussion about getting magmas from clique decompositions, and applied it to the remaining 2-variable laws.

The remaining 2-variable laws are 63, 115, 467, 501, 667, 670, 677, 704, 873, 883, 907, 1076, 1083, 1110, 1279, 1286, 1313, 1489, 1516, and 1719.

Using the clique decomposition technique, we can show that 63, 467, 667, 670, 704, 883, 1076, 1110, 1279, 1313, 1489, and 1516 have asymptotically full spectrum (idempotent spectrum, even, as those are the only magmas that this technique produces).

Out of the remaining 8 laws, 115, 501, 873, 1083, and 1719 do not have asymptotically full idempotent spectrum; in fact, their idempotent spectrum contains no $n\equiv 2\pmod 3$ due to being "downstream" from Law 14, so we will have to look outside idempotent magmas for these.

The remaining three two-variable laws, 677 (of course), 907, and 1286, have modular barriers to idempotent linear models, but it's not clear that those barriers exist for nonlinear models, so they may still have asymptotically full idempotent spectrum, though it cannot be proven with this technique.

Two-variable Clique Decompositions.pdf

[Bruno Le Floch]

Here are the updated notes spectrum.pdf. The main progress since last time is writing up the full spectrum problem (section 1) and counting magmas for many more laws (section 4), probably no changes relevant to the current discussion.

(EDIT: rewrote this paragraph which had mistakes.) For law 115. Finite models of 115 are quasigroups in which squaring is an automorphism, so idempotents form a sub-quasigroup, which easily implies (Drury W. Wall, Pacific J. Math. 7 (4), 1711-1714, (1957)) that there are at most $n/2$ idempotents. To get models with n≡2 mod 3 we need many non-idempotents. In addition, the cycle lengths of squaring are at least 4.

EDIT 2: An interesting consequence is that law-115 magmas that are not idempotent are much more constrained since fixing one entry in the table fixes many others instead of just three others like in semi-symmetric quasigroups. This means that the limit $\log N_{115}(n) / (n^2 \log n)$ as $n\to+\infty$ is $1/3$ for $n\equiv 0,1\bmod 3$ but much lower for $n\equiv 2\bmod 3$. I'm not sure yet how to determine it. EDIT 3: Upper bound $\log N_{115}(n)<(7/48+o(1)) n^2\log n$ achieved if we can have $\sim n/2$ idempotents and others in 4-cycles of squaring, and then choose cycles of 12 entries generically enough.