Quasigroup

In mathematics, especially in abstract algebra, a quasigroup is an algebraic structure resembling a group in the sense that "division" is always possible. Quasigroups differ from groups mainly in that they need not be associative.

A quasigroup with an identity element is called a loop.

Definitions

There are at least two equivalent formal definitions of quasigroup. One defines a quasigroup as a set with one binary operation, and the other, from universal algebra, defines a quasigroup as having three primitive operations. We begin with the first definition.

A quasigroup (Q, ∗) is a set, Q, with a binary operation, ∗, (that is, a magma), obeying the Latin square property. This states that, for each a and b in Q, there exist unique elements x and y in Q such that both

  1. ax = b
  2. ya = b

hold. (In other words: Each element of the set occurs exactly once in each row and exactly once in each column of the quasigroup's multiplication table, or Cayley table. This property ensures that the Cayley table of a finite quasigroup is a Latin square.)

The unique solutions to these equations are written x = a \ b and y = b / a. The operations '\' and '/' are called, respectively, left and right division.

The empty set equipped with the empty binary operation satisfies this definition of a quasigroup. Some authors accept the empty quasigroup but others explicitly exclude it.[1][2]

Universal algebra

Given some algebraic structure, an identity is an equation in which all variables are tacitly universally quantified, and in which all operations are among the primitive operations proper to the structure. Algebraic structures axiomatized solely by identities are called varieties. Many standard results in universal algebra hold only for varieties. Quasigroups are varieties if left and right division are taken as primitive.

A quasigroup (Q, ∗, \, /) is a type (2,2,2) algebra (i.e., equipped with three binary operations) satisfying the identities:

y = x ∗ (x \ y) ;

y = x \ (xy) ;

y = (y / x) ∗ x ;

y = (yx) / x .

In other words: Multiplication and division in either order, one after the other, on the same side by the same element, have no net effect.

Hence if (Q, ∗) is a quasigroup according to the first definition, then (Q, ∗, \, /) is the same quasigroup in the sense of universal algebra.

Loop

Algebraic structures between magmas and groups.

A loop is a quasigroup with an identity element; that is, an element, e, such that:

xe = x and ex = x for all x in Q.

It follows that the identity element, e, is unique, and that every element of Q has a unique left and right inverse. Since the presence of an identity element is essential, a loop cannot be empty.

A quasigroup with an idempotent element is called a pique ("pointed idempotent quasigroup"); this is a weaker notion than loop but common nonetheless because given an abelian group, (A, +), its subtraction operation (as quasigroup multiplication) yields a pique (A, -) with the abelian group's zero/identity turned into a "pointed idempotent"; i.e., there's a principal isotopy (x, y, z) \mapsto (x, -y, z).

A loop which is associative is a group. A group can have a non-associative pique isotope, but it cannot have a nonassociative loop isotope. There are also some weaker associativity-like properties which have been given special names.

A Bol loop is a loop that satisfies either:

x ∗ (y ∗ (xz)) = (x ∗ (yx)) ∗ z    

for each x, y and z in Q (a left Bol loop),

or else

((zx) ∗ y) ∗ x = z ∗ ((xy) ∗ x)    

for each x, y and z in Q (a right Bol loop).

A loop that is both a left and right Bol loop is a Moufang loop. This is equivalent to any one of the following single Moufang identities holding for all x, y, z:

x ∗ (y ∗ (xz)) = ((xy) ∗ x) ∗ z,

z ∗ (x ∗ (yx)) = ((zx) ∗ y) ∗ x,

(xy) ∗ (zx) = x ∗ ((yz) ∗ x), or

(xy) ∗ (zx) = (x ∗ (yz)) ∗ x.

Symmetries

Smith (2007) names the following important subclasses:

Semisymmetry

A quasigroup is semisymmetric if all of the following equivalent identities hold:

xy = y / x

yx = x \ y

x = (yx)y

x = y(xy)

Although this class may seem special, every quasigroup Q induces a semisymmetric quasigroup QΔ on the direct product cube Q3 via following operation:

(x_1, x_2, x_3) \cdot (y_1, y_2, y_3) = (y_3/x_2, y_1 \backslash x_3 , x_1y_2) = (x_2//y_3, x_3 \backslash \backslash y_1, x_1y_2)

where "//" and "\\" are the conjugate division operations; the latter formula more explicitly shows that the construction is exploiting an orbit of S3.

Total symmetry

A narrower class that is a total symmetric quasigroup (sometimes abbreviated TS-quasigroup) in which all conjugates coincide as one operation: xy = x/y = x\y. Another way to define (the same notion of) totally symmetric quasigroup is as a semisymmetric quasigroup which additionally is commutative, i.e. xy=yx.

Idempotent total symmetric quasigroups are precisely (i.e. in a bijection with) Steiner triples, so such a quasigroup is also called a Steiner quasigroup, and sometimes the latter is even abbreviated as squag; the term sloop is defined similarly for a Steiner quasigroup that is also a loop. Without idempotency, total symmetric quasigroups correspond to the geometric notion of extended Steiner triple, also called Generalized Elliptic Cubic Curve (GECC).

Total antisymmetry

A quasigroup (Q, ∗) is called totally anti-symmetric if for all c, x, yQ, both of the following implications hold:[3]

  1. (cx) ∗ y = (cy) ∗ x implies that x = y
  2. xy = yx implies that x = y.

It is called weakly totally anti-symmetric if only the first implication holds.[3]

This property is required, for example, in the Damm algorithm.

Examples

(x1, x2, x3, x4) ∗ (y1, y2, y3, y4) = (x1, x2, x3, x4) + (y1, y2, y3, y4) + (0, 0, 0, (x3y3)(x1y2x2y1)).
Then, (F4, ∗) is a commutative Moufang loop that is not a group.[5]

Properties

In the remainder of the article we shall denote quasigroup multiplication simply by juxtaposition.

Quasigroups have the cancellation property: if ab = ac, then b = c. This follows from the uniqueness of left division of ab or ac by a. Similarly, if ba = ca, then b = c.

Multiplication operators

The definition of a quasigroup can be treated as conditions on the left and right multiplication operators L(x), R(y): QQ, defined by

\begin{align}
  L(x)y &= xy \\
  R(x)y &= yx \\
\end{align}

The definition says that both mappings are bijections from Q to itself. A magma Q is a quasigroup precisely when all these operators, for every x in Q, are bijective. The inverse mappings are left and right division, that is,

\begin{align}
  L(x)^{-1}y &= x\backslash y \\
  R(x)^{-1}y &= y/x
\end{align}

In this notation the identities among the quasigroup's multiplication and division operations (stated in the section on universal algebra) are

\begin{align}
  L(x)L(x)^{-1} &= 1\qquad&\text{corresponding to}\qquad x(x\backslash y) &= y \\
  L(x)^{-1}L(x) &= 1\qquad&\text{corresponding to}\qquad x\backslash(xy) &= y \\
  R(x)R(x)^{-1} &= 1\qquad&\text{corresponding to}\qquad (y/x)x &= y \\
  R(x)^{-1}R(x) &= 1\qquad&\text{corresponding to}\qquad (yx)/x &= y
\end{align}

where 1 denotes the identity mapping on Q.

Latin squares

The multiplication table of a finite quasigroup is a Latin square: an n × n table filled with n different symbols in such a way that each symbol occurs exactly once in each row and exactly once in each column.

Conversely, every Latin square can be taken as the multiplication table of a quasigroup in many ways: the border row (containing the column headers) and the border column (containing the row headers) can each be any permutation of the elements. See small Latin squares and quasigroups.

Inverse properties

Every loop element has a unique left and right inverse given by

x^{\lambda} = e/x \qquad x^{\lambda}x = e
x^{\rho} = x\backslash e \qquad xx^{\rho} = e

A loop is said to have (two-sided) inverses if x^{\lambda} = x^{\rho} for all x. In this case the inverse element is usually denoted by x^{-1}.

There are some stronger notions of inverses in loops which are often useful:

A loop has the inverse property if it has both the left and right inverse properties. Inverse property loops also have the antiautomorphic and weak inverse properties. In fact, any loop which satisfies any two of the above four identities has the inverse property and therefore satisfies all four.

Any loop which satisfies the left, right, or antiautomorphic inverse properties automatically has two-sided inverses.

Morphisms

A quasigroup or loop homomorphism is a map f : QP between two quasigroups such that f(xy) = f(x)f(y). Quasigroup homomorphisms necessarily preserve left and right division, as well as identity elements (if they exist).

Homotopy and isotopy

Main article: Isotopy of loops

Let Q and P be quasigroups. A quasigroup homotopy from Q to P is a triple (α, β, γ) of maps from Q to P such that

\alpha(x)\beta(y) = \gamma(xy)\,

for all x, y in Q. A quasigroup homomorphism is just a homotopy for which the three maps are equal.

An isotopy is a homotopy for which each of the three maps (α, β, γ) is a bijection. Two quasigroups are isotopic if there is an isotopy between them. In terms of Latin squares, an isotopy (α, β, γ) is given by a permutation of rows α, a permutation of columns β, and a permutation on the underlying element set γ.

An autotopy is an isotopy from a quasigroup to itself. The set of all autotopies of a quasigroup form a group with the automorphism group as a subgroup.

Every quasigroup is isotopic to a loop. If a loop is isotopic to a group, then it is isomorphic to that group and thus is itself a group. However, a quasigroup which is isotopic to a group need not be a group. For example, the quasigroup on R with multiplication given by (x + y)/2 is isotopic to the additive group (R, +), but is not itself a group. Every medial quasigroup is isotopic to an abelian group by the Bruck–Toyoda theorem.

Conjugation (parastrophe)

Left and right division are examples of forming a quasigroup by permuting the variables in the defining equation. From the original operation ∗ (i.e., xy = z) we can form five new operations: x o y := yx (the opposite operation), / and \, and their opposites. That makes a total of six quasigroup operations, which are called the conjugates or parastrophes of ∗. Any two of these operations are said to be "conjugate" or "parastrophic" to each other (and to themselves).

Paratopy

If the set Q has two quasigroup operations, ∗ and ·, and one of them is isotopic to a conjugate of the other, the operations are said to be paratopic to each other. There are also many other names for this relation of "paratopy", e.g., isostrophe.

Generalizations

Polyadic or multiary quasigroups

An n-ary quasigroup is a set with an n-ary operation, (Q, f) with f: QnQ, such that the equation f(x1,...,xn) = y has a unique solution for any one variable if all the other n variables are specified arbitrarily. Polyadic or multiary means n-ary for some nonnegative integer n.

A 0-ary, or nullary, quasigroup is just a constant element of Q. A 1-ary, or unary, quasigroup is a bijection of Q to itself. A binary, or 2-ary, quasigroup is an ordinary quasigroup.

An example of a multiary quasigroup is an iterated group operation, y = x1 · x2 · ··· · xn; it is not necessary to use parentheses to specify the order of operations because the group is associative. One can also form a multiary quasigroup by carrying out any sequence of the same or different group or quasigroup operations, if the order of operations is specified.

There exist multiary quasigroups that cannot be represented in any of these ways. An n-ary quasigroup is irreducible if its operation cannot be factored into the composition of two operations in the following way:

 f(x_1,\dots,x_n) = g(x_1,\dots,x_{i-1},\,h(x_i,\dots,x_j),\,x_{j+1},\dots,x_n),

where 1 ≤ i < jn and (i, j) ≠ (1, n). Finite irreducible n-ary quasigroups exist for all n > 2; see Akivis and Goldberg (2001) for details.

An n-ary quasigroup with an n-ary version of associativity is called an n-ary group.

Right- and left-quasigroups

A right-quasigroup (Q, ∗, /) is a type (2,2) algebra satisfying both identities:

y = (y / x) ∗ x;

y = (yx) / x.

Similarly, a left-quasigroup (Q, ∗, \) is a type (2,2) algebra satisfying both identities:

y = x ∗ (x \ y);

y = x \ (xy).

Number of small quasigroups and loops

The number of isomorphism classes of small quasigroups (sequence A057991 in OEIS) and loops (sequence A057771 in OEIS) is given here:[6]

Order Number of quasigroups Number of loops
0 1 0
1 1 1
2 1 1
3 5 1
4 35 2
5 1,411 6
6 1,130,531 109
7 12,198,455,835 23,746
8 2,697,818,331,680,661 106,228,849
9 15,224,734,061,438,247,321,497 9,365,022,303,540
10 2,750,892,211,809,150,446,995,735,533,513 20,890,436,195,945,769,617
11 19,464,657,391,668,924,966,791,023,043,937,578,299,025 1,478,157,455,158,044,452,849,321,016

See also

Notes

  1. Hala O. Pflugfelder (1990). Quasigroups and loops: introduction. Heldermann Verlag. p. 2.
  2. Bruck, Richard Hubert (1971), A survey of binary systems, Springer, p. 1, ISBN 0-387-03497-8
  3. 1 2 Damm, H. Michael (2007). "Totally anti-symmetric quasigroups for all orders n2,6". Discrete Mathematics 307 (6): 715–729. doi:10.1016/j.disc.2006.05.033. ISSN 0012-365X.
  4. Colbourn & Dinitz 2007, pg. 497, definition 28.12
  5. Smith, Jonathan D. H.; Romanowska, Anna B. (1999), "Example 4.1.3 (Zassenhaus's Commutative Moufang Loop)", Post-modern algebra, Pure and Applied Mathematics (New York), John Wiley & Sons, Inc., New York, p. 93, doi:10.1002/9781118032589, ISBN 0-471-12738-8, MR 1673047.
  6. McKay, Brendan D.; Meynert, Alison; Myrvold, Wendy (2007). "Small Latin squares, quasigroups, and loops" (PDF). J. Comb. Des. 15 (2): 98–119. doi:10.1002/jcd.20105. Zbl 1112.05018.

References

External links

This article is issued from Wikipedia - version of the Tuesday, March 29, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.