13 Equation 677

In this chapter we study finite magmas that obey equation 677,

x = y ⋄ (x ⋄ ((y ⋄ x) ⋄ y))

for all $x, y$ , and whether this implies equation 255,

x = ((x ⋄ x) ⋄ x) ⋄ x .

Using the usual notation $L_{y} x = y ⋄ x$ , $R_{y} x = x ⋄ y$ , $S x = x ⋄ x$ , we can rewrite equation 677 as

x = L_{y} L_{x} L_{L_{y} x} y = L_{y} (x ⋄ R_{y} L_{y} x)

and 255 as

x = (S x ⋄ x) ⋄ x .

Lemma 13.1 Basic properties of 677 magma

Let $M$ be a finite magma obeying 1.

(i) The left multiplication operators $L_{y} : M \to M$ are all invertible, with $L_{y}^{- 1} x = x ⋄ R_{y} L_{y} x$ .
(ii) If $x, y \in M$ and $y ⋄ x = x$ , then $y = S x ⋄ x$ . In particular, 255 holds if and only if the equation $y ⋄ x = x$ is solvable for every $x$ .
(iii) For all $x, y \in M$ , we have $x = L_{y} x ⋄ R_{y} L_{y}^{2} x$ .

Proof ▶

From 3 we see that $L_{y}$ is surjective, hence invertible on finite magmas, giving (i) (the formula for $L_{y}^{- 1} x$ being immediate from 3).

For (ii), using the fact that $L_{y} x = x$ , (i) becomes $x = x ⋄ R_{y} x = L_{x} L_{x} y$ , then, using the invertibility of $L_{x}$ given by (i) we have

y = L_{x}^{- 1} L_{x}^{- 1} x \overset{(i)}{=} L_{x}^{- 1} (x ⋄ R_{x} L_{x} x) = L_{x}^{- 1} (L_{x} R_{x} L_{x} x) = R_{x} L_{x} x = S x ⋄ x .

For (iii), we apply (i) with $x$ replaced by $L_{y} x$ .

We have the following equivalent characterizations of 255:

Lemma 13.2

Let $M$ be a finite magma obeying 1, and let $x \in M$ . Then the following are equivalent:

(i) 255 holds for $x$ , that is to say $R_{x} (S x ⋄ x) = x$ .
(ii) The equation $R_{x} y = x$ has the unique solution $y = S x ⋄ x$ .
(iii) The equation $R_{x} y = x$ has a solution.
(iv) The equation $R_{x} L_{x} z = x$ has a solution.
(v) The equation $L_{x} R_{x} z = z$ has a solution.
(vi) The equation $R_{x} L_{x} y = y$ has a solution.
(vii) The equation $L_{x} S y = y$ has a solution.

Proof ▶

Clearly (ii) implies (i), which implies (iii). If (iii) holds, we apply 3 to conclude that

y ⋄ x = x = y ⋄ (x ⋄ (x ⋄ y))

and hence by left invertibility

x = x ⋄ (x ⋄ y) .

On the other hand, from 1 with $y$ replaced by $x$ we have

x = x ⋄ (x ⋄ (S x ⋄ x))

and hence by left invertibility $y = S x ⋄ x$ , giving (ii).

From left cancellativity we see that (v) and (vi) are equivalent, as are (iii) and (iv).

If (vii) holds, then $L_{x} L_{y} y = y$ , but from 3 we have $y = L_{x} L_{y} R_{x} L_{x} y$ , so (vi) follows from left-cancellativity; the converse implication follows by reversing the steps. If (v) holds, then we have $L_{x} L_{z} x = z$ , but from 3 one has $z = L_{x} L_{z} R_{x} L_{x} z$ , giving the (iv) by left-cancellativity; the converse implication follows by reversing the steps.

This for instance gives the implication for linear magmas:

Lemma 13.3 No linear counterexamples

Suppose we have a finite magma $M$ obeying 677 which is linear in the sense that $M$ is an abelian group and $x ⋄ y = α x + β y + c$ for some endomorphisms $α, β : M \to M$ and constant $c$ . Then $M$ obeys 255.

Proof ▶

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

L_{y} L_{x} L_{L_{y} x} y = x = L_{y} L_{x} L_{L_{y} x} y^{'}

and hence by left-invertibility $y = y^{'}$ , a contradiction.

In fact the argument gives a stronger obstruction to refuting 255:

Lemma 13.4 No counterexamples via linear extension

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

(x, s) ⋄ (y, t) = (x ⋄ y, α_{x, y} s + β_{x, y} t + c_{x, y})

for some endomorphisms $α_{x, y}, β_{x, y} : M \to M$ and constants $c_{x, y}$ . Then $G \times M$ obeys 255.

Proof ▶

By Lemma 13.1, it suffices to show that for any $(y, t)$ , the equation $(x, s) ⋄ (y, t) = (y, t)$ is solvable. Since $G$ already obeys 255, we know that we can find $x$ such that $x ⋄ y = y$ , so it suffices to show that the operation $s \mapsto α_{x, y} s + β_{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 $α_{x, y} s = α_{x, y} s^{'}$ , and hence $L_{(x, s)} (y, t^{'}) = L_{(x, s^{'})} (y, t^{'})$ for all $t^{'} \in M$ . Since

x ⋄ y = y = x ⋄ (y ⋄ ((x ⋄ y) ⋄ x))

from 1, we have $y = y ⋄ ((x ⋄ y) ⋄ 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

L_{(x, s)} L_{(y, t)} L_{L_{(x, s)} (y, t)} (x, s) = (y, t) = L_{(x, s)} L_{(y, t)} L_{L_{(x, s)} (y, t)} (x, s^{'})

and hence by left invertibility $s = s^{'}$ , a contradiction.

Linear models $x ⋄ y = α x + β y + c$ on the finite field $F_{p}$ turn out to be classified into two types:

(Type 1) $α = 1 - β$ , $β$ is a primitive tenth root of unity, and $c = 0$ . (These models are also translation-invariant.)
(Type 2) $α$ is a primitive third root of unity, $c$ is arbitrary, and $β$ solves $β^{3} + β + 1 = - α$ and $β^{4} + β^{3} + 2 β^{2} + 2 β + 1 = 0$ .

An example of a Type I model is $x ⋄ y = 2 x - y$ on $F_{5}$ . Examples of Type II models include $x ⋄ y = 4 x + 3 y$ and $x ⋄ y = 4 x + y$ on $F_{7}$ . An exceptional class of Type II models are $x ⋄ y = 5 x - 4 y + 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 A finite non-right-cancellative example

Suppose $G$ is already a 677 magma, and to each pair $x, y \in G$ we assign a binary operation $⋄_{x, y} : M \times M \to M$ such that one has the functional equation

s = t ⋄_{y, L_{y}^{- 1} x} (s ⋄_{x, (y ⋄ x) ⋄ y} ((t ⋄_{y, x} s) ⋄_{y ⋄ x, y} t))

for all $x, y \in G$ , then the operation

(x, s) ⋄ (y, t) := (x ⋄ y, s ⋄_{x, y} t)

is easily seen to be a 677 magma. It is right-injective if $G$ and all of the $⋄_{y, x}$ are right-injective.

Suppose $M$ is a field that admits a primitive cube root of unity $ω$ as well as a primitive fifth root of unity $ζ$ (for instance, $M$ could be a field of order $16$ ). Then the three operations

s ⋄^{0} t := s - ζ (t - s)

s ⋄^{+} t := t

s ⋄^{-} t := s - ω (t - s)

can easily be seen to obey the identities

s = t ⋄^{0} (s ⋄^{0} ((t ⋄^{0} s) ⋄^{0} t))

s = t ⋄^{+} (s ⋄^{+} ((t ⋄^{-} s) ⋄^{-} t))

s = t ⋄^{-} (s ⋄^{-} ((t ⋄^{+} s) ⋄^{+} t))

for all $t, s$ .

Now suppose that $G$ is also a field with a primitive fifth root of unity $β$ (so that $β = β^{4}$ is a quadratic residue), but $- 1$ and $β + 1$ are non-zero quadratic non-residues (for instance, $G$ could be the field of order $31$ , with $β = 2$ ). If we define $x ⋄ y = x - β (y - x)$ , and then define $⋄_{x, y}$ to be $⋄^{0}$ when $y = x$ , $⋄^{+}$ when $y - x$ is a non-zero quadratic residue, and $⋄^{-}$ when $y - x$ is a non-zero quadratic non-residue, one can then check that 4 holds. Since $⋄^{0}$ is not right-cancellative, this gives a finite 677 magma that is not right-cancellative.

13.2 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_{L L}$ , $w_{L R}$ , etc. iteratively if they are defined, for instance if $w = ((x, y), z)$ then $w_{L R} = y$ . We define a partial order $<$ on $M_{X}$ by declaring $w < w^{'}$ if $w$ is a subtree of $w^{'}$ , thus $w < w^{'}$ if one of $w \leq w_{L}^{'}$ , $w \leq w_{R}^{'}$ holds.

We define an operation $⋄$ recursively on $M_{X}$ by the following rule:

If $x, y \in M_{X}$ is such that $x < y = (y_{L}, (x ⋄ y_{L}) ⋄ x)$ , then $x ⋄ y := y_{L}$ . Otherwise, $x ⋄ y = (x, y)$ .

Note that to define $x ⋄ y$ , one only needs to be able to compute $x^{'} ⋄ y^{'}$ for $y^{'} < y$ . Since there are no infinite descending chains in the partial order $<$ , we see that $⋄$ is well-defined. By construction, we observe the following properties:

Lemma 13.5 Properties of operation

Let $x, y \in M_{X}$ be such that $x ⋄ y = z$ . Then either

x, y < z = (x, y)

x, z < y = (z, (x ⋄ z) ⋄ x) .

In particular, $x$ is strictly upper bounded by one of $y, z$ .

Next, we observe

Lemma 13.6 Additional property

If $x, y \in M_{X}$ , then

x ⋄ ((y ⋄ x) ⋄ y) = (x, (y ⋄ x) ⋄ y) .

Proof ▶

Write $z := y ⋄ x$ , $u = z ⋄ y$ , $v = x ⋄ u$ . Our task is to show that $v = (x, u)$ .

From Lemma 13.5 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.5 we have $v = (x, u)$ as required, hence we may assume for contradiction that $u$ is maximal. From Lemma 13.5, this implies that $u = (z, y)$ and $u = (u_{L}, (x ⋄ u_{L}) ⋄ x)$ , hence $u_{L} = z$ and $y = (x ⋄ z) ⋄ x$ .

From Lemma 13.5, $x$ is upper bounded by one of $x ⋄ z$ and $z$ , and $x ⋄ 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 ⋄ z$ , the only one that can be maximal is $z$ . In particular $z$ is not bounded by $x$ , hence by Lemma 13.5 $z = (y, x)$ . $z$ is also not bounded by $x ⋄ z$ , hence by Lemma 13.5 $x ⋄ z = z_{L} = y$ , hence $y = y ⋄ x = z$ , contradicting the fact that $y$ was not maximal. This gives the required contradiction.

Corollary 13.7

The operation $⋄$ obeys 1.

Proof ▶

By the previous lemma and definition of $⋄$ , it suffices to show that $y < (x, (y ⋄ x) ⋄ y)$ . Defining $z, u, v$ as before, this amounts to showing that $y < v$ . We already have $v = (x, u)$ , hence by Lemma 13.5 $x < v$ . 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.

Corollary 13.8

Let $M_{X, 677}$ be the magma generated by $X$ with operation $⋄$ . Then $M_{X, 677}$ is the free magma for 1 generated by $X$ .

Proof ▶

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 $φ_{f} : M_{X, 677} \to X$ . Uniqueness is clear since $M_{X, 677}$ is generated by $X$ . For existence, we define $φ_{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 $φ_{f} (x ⋄ y) = φ_{f} (x) ⋄ φ_{f} (y)$ , we are already done when $x ⋄ y = (x, y)$ . The only remaining case is when $x ⋄ y = y_{L}$ and $x < y = (y_{L}, (x ⋄ y_{L}) ⋄ x)$ . If we assume inductively that the homomorphism property $φ_{f} (x^{'} ⋄ y^{'}) = φ_{f} (x^{'}) ⋄ φ_{f} (y^{'})$ has already been verified for $y^{'} < y$ , then we have

φ_{f} (y) = φ_{f} (y_{L}) ⋄ φ_{f} (y_{R}) = φ_{f} (y_{L}) ⋄ (φ_{f} (x ⋄ y_{L}) ⋄ φ_{f} (x)) = φ_{f} (y_{L}) ⋄ ((φ_{f} (x) ⋄ φ_{f} (y_{L})) ⋄ φ_{f} (x))

and the claim now follows since $M$ obeys 677. □

By construction, we have $x ⋄ y > y$ or $x ⋄ y < y$ for any $x, y$ . In particular, $M_{X, 677}$ does not obey 2.