13 Equation 677
In this chapter we study finite magmas that obey equation 677,
for all \(x,y\), and whether this implies equation 255,
Using the usual notation \(L_y x = y \diamond x\), \(R_y x = x \diamond y\), \(Sx = x \diamond x\), we can rewrite equation 677 as
and 255 as
Let \(M\) be a finite magma obeying 1.
(i) The left multiplication operators \(L_y: M \to M\) are all invertible.
(ii) If \(x,y \in M\) and \(y \diamond x = x\), then \(x = Sx \diamond x\). In particular, 255 holds if and only if the equation \(y \diamond x = x\) is solvable for every \(x\).
From 3 we see that \(L_y\) is surjective, hence invertible on finite magmas, giving (i). For (ii), we apply 1 to conclude that
and hence by left invertibility
On the other hand, from 1 with \(y\) replaced by \(x\) we have
and the claim then follows by left invertibility.
This for instance gives the implication for linear magmas:
Suppose we have a finite magma \(M\) obeying 677 which is linear in the sense that \(M\) is an abelian group and \(x \diamond y = \alpha x + \beta y + c\) for some endomorhpisms \(\alpha ,\beta : M \to M\) and constant \(c\). Then \(M\) obeys 255.
By the previous lemma, it suffices to show that right multiplication \(R_x\) is surjective, or equivalently injective by finiteness. If this is not the case, then we can find distinct \(y,y'\) such that \(R_x y = R_x y'\), hence \(L_y x = L_{y'} x\). But in this linear model, \(L_y\) and \(L_{y'}\) differ by a constant, hence we have \(L_y = L_{y'}\). Applying 3 we have
and hence by left-invertiblity \(y=y'\), a contradiction.
In fact the argument gives a stronger obstruction to refuting 255:
Suppose that we have a magma with carrier \(G \times M\) obeying 677, where \(G\) already is a magma obeying 677 and 255, \(M\) is an abelian group, and the multiplication operation on \(G \times M\) is of the form
for some endomorphisms \(\alpha _{x,y},\beta _{x,y}: M \to M\) and constants \(c_{x,y}\). Then \(G \times M\) obeys 255.
By Lemma 13.1, it suffices to show that for any \((y,t)\), the equation \((x,s) \diamond (y,t) = (y,t)\) is solvable. Since \(G\) already obeys 255, we know that we can find \(x\) such that \(x \diamond y = y\), so it suffices to show that the operation \(s \mapsto \alpha _{x,y} s + \beta _{x,y} t + c_{x,y}\) is surjective, or equivalently injective. If this were not the case, then we could find \(s,s'\) such that \(\alpha _{x,y} s = \alpha _{x,y} s'\), and hence \(L_{(x,s)} (y,t') = L_{(x,s')} (y,t')\) for all \(t' \in M\). Since
from 1, we have \(y = y \diamond ((x \diamond y) \diamond x)\), and hence \(L_{(y,t)} L_{L_{(x,s)} (y,t)} (x,s)\) is of the form \((y,t')\) for some \(t'\), and similarly with \((x,s)\) replaced by \((x,s')\). We conclude that
and hence by left invertibliity \(s=s'\), a contradiction.
Linear models \(x \diamond y = \alpha x + \beta y + c\) on the finite field \(F_p\) turn out to be classified into two types:
(Type 1) \(\alpha =1-\beta \), \(\beta \) is a primitive tenth root of unity, and \(c=0\). (These models are also translation-invariant.)
(Type 2) \(\alpha \) is a primitive third root of unity, \(c\) is arbitrary, and \(\beta \) solves \(\beta ^3+\beta +1=-\alpha \) and \(\beta ^4+\beta ^3+2\beta ^2+2\beta +1=0\).
An example of a Type I model is \(x \diamond y = 2x-y\) on \(F_5\). Examples of Type II models include \(x \diamond y = 4x+3y\) and \(x \diamond y = 4x+y\) on \(F_7\). An exceptional class of Type II models are \(x \diamond y = 5x-4y+c\) on \(F_{31}\), these are the only Type II models that are translation-invariant and do not have idempotents (if \(c \neq 0\)).
13.1 The free 677 magma
In this section we construct the free 677 magma \(M_{X,677}\) generated by some set of generators \(X\). First let \(M_X\) be the free magma generated \(X\) with operation given by pairing \(x,y \mapsto (x,y)\); one can think of elements of \(M_X\) as finite trees with leaves in \(X\). If \(w = (x,y)\) we write \(x = w_L\) and \(y = w_R\) for the left and right components of \(w\); we also define \(w_{LL}\), \(w_{LR}\), etc. iteratively if they are defined, for instance if \(w = ((x,y),z)\) then \(w_{LR} = y\). We define a partial order \({\lt}\) on \(M_X\) by declaring \(w {\lt} w'\) if \(w\) is a subtree of \(w'\), thus \(w {\lt} w'\) if one of \(w \leq w'_L\), \(w \leq w'_R\) holds.
We define an operation \(\diamond \) recursively on \(M_X\) by the following rule:
If \(x,y \in M_X\) is such that \(x {\lt} y = (y_L, (x \diamond y_L) \diamond x)\), then \(x \diamond y := y_L\). Otherwise, \(x \diamond y = (x,y)\).
Note that to define \(x \diamond y\), one only needs to be able to compute \(x' \diamond y'\) for \(y' {\lt} y\). Since there are no infinite descending chains in the partial order \({\lt}\), we see that \(\diamond \) is well-defined. By construction, we observe the following properties:
Let \(x,y \in M_X\) be such that \(x \diamond y = z\). Then either
or
In particular, \(x\) is strictly upper bounded by one of \(y,z\).
Next, we observe
If \(x,y \in M_X\), then
Write \(z := y \diamond x\), \(u = z \diamond y\), \(v = x \diamond u\). Our task is to show that \(v = (x,u)\).
From Lemma 13.4 we know that \(y\) is upper bounded by one of \(z,x\), \(z\) is upper bounded by one of \(u,y\), and \(x\) is upper bounded by one of \(u,v\). So out of \(x,y,z,u,v\), the only elements that can be maximal in this set are \(u\) and \(v\). If \(v\) is maximal, then by Lemma 13.4 we have \(v = (x,u)\) as required, hence we may assume for contradiction that \(u\) is maximal. From Lemma 13.4, this implies that \(u = (z,y)\) and \(u = (u_L, (x \diamond u_L) \diamond x)\), hence \(u_L = z\) and \(y = (x \diamond z) \diamond x\).
From Lemma 13.4, \(x\) is upper bounded by one of \(x \diamond z\) and \(z\), and \(x \diamond z\) is upper bounded by one of \(y\) and \(x\). We also recall that \(y\) was upper bounded by one of \(z,x\). We conclude that out of \(x,y,z,x \diamond z\), the only one that can be maximal is \(z\). In particular \(z\) is not bounded by \(x\), hence by Lemma 13.4 \(z = (y,x)\). \(z\) is also not bounded by \(w\), hence by Lemma 13.4 \(x \diamond z = z_L = y\), hence \(y = y \diamond x = z\), contradicting the fact that \(y\) was not maximal. This gives the required contradiction.
By the previous lemma and definition of \(\diamond \), it suffices to show that \(y {\lt} (x, (y \diamond x) \diamond y)\). Defining \(z,y,v\) as before, this amounts to showing that \(y {\lt} v\). We already have \(v = (x,u)\), hence by Lemma 13.4 \(x {\lt} u\). Also recall that \(y\) is bounded by one of \(x,z\), and \(z\) is bounded by one of \(y,u\). Since \(u\) is also bounded by \(v\), we obtain the claim.
Let \(M_{X,677}\) be the magma generated by \(X\) with operation \(\diamond \). Then \(M_{X,677}\) is the free magma for 1 generated by \(X\).
By the previous corollary, it suffices to show that every function \(f: X \to M\) into a 677 magma \(M\) can be extended to a unique homomorphism \(\varphi _f: M_{X,677} \to X\). Uniqueness is clear since \(M_{X,677}\) is generated by \(X\). For existence, we define \(\varphi _f\) by first extending \(f\) to the unique homomorphism from \(M_X\) to \(X\) (using the pairing map) and then restricting to \(M_{X,677}\). To verify the homomorphism property \(\varphi _f(x \diamond y) = \varphi _f(x) \diamond \varphi _f(y)\), we are already done when \(x \diamond y = (x,y)\). The only remaining case is when \(x \diamond y = y_L\) and \(x {\lt} y = (y_L, (x \diamond y_L) \diamond x)\). If we assume inductively that the homomorphism property \(\varphi _f(x' \diamond y') = \varphi _f(x') \diamond \varphi _f(y')\) has already been verified for \(y' {\lt} y\), then we have
and the claim now follows since \(M\) obeys 677.
By construction, we have \(x \diamond y {\gt} y\) or \(x \diamond y {\lt} y\) for any \(x,y\). In particular, \(M_{X,677}\) does not obey 2.