Light's associativity test

In mathematics, Light's associativity test is a procedure invented by F W Light for testing whether a binary operation defined in a finite set by a Cayley multiplication table is associative. Direct verification of the associativity of a binary operation specified by a Cayley table is cumbersome and tedious. Light's associativity test greatly simplifies the task.

Description of the procedure

Let a binary operation ' · ' be defined in a finite set A by a Cayley table. Choosing some element a in A, two new binary operations are defined in A as follows:

\star

y = x · ( a · y )

\circ

y = ( x · a ) · y

The Cayley tables of these operations are constructed and compared. If the tables coincide then x · ( a · y ) = ( x · a ) · y for all x and y. This is repeated for every element of the set A.

The example below illustrates a further simplification in the procedure for the construction and comparison of the Cayley tables of the operations ' $\star$ ' and ' $\circ$ '.

It is not even necessary to construct the Cayley tables of ' $\star$ ' and ' $\circ$ ' for all elements of A. It is enough to compare Cayley tables of ' $\star$ ' and ' $\circ$ ' corresponding to the elements in a proper generating subset of A.

Example

Consider the binary operation ' · ' in the set A = { a, b, c, d, e } defined by the following Cayley table (Table 1):

Table 1
·	a	b	c	d	e
a	a	a	a	d	d
b	a	b	c	d	d
c	a	c	b	d	d
d	d	d	d	a	a
e	d	e	e	a	a

The set { c, e } is a generating set for the set A under the binary operation defined by the above table, for, a = e · e, b = c · c, d = c · e. Thus it is enough to verify that the binary operations ' $\star$ ' and ' $\circ$ ' corresponding to c coincide and also that the binary operations ' $\star$ ' and ' $\circ$ ' corresponding to e coincide.

To verify that the binary operations ' $\star$ ' and ' $\circ$ ' corresponding to c coincide, choose the row in Table 1 corresponding to the element c :

Table 2
·	a	b	c	d	e
a	a	a	a	d	d
b	a	b	c	d	d
c	a	c	b	d	d
d	d	d	d	a	a
e	d	e	e	a	a

This row is copied as the header row of a new table (Table 3):

Table 3
	a	c	b	d	d

Under the header a copy the corresponding column in Table 1, under the header b copy the corresponding column in Table 1, etc., and construct Table 4.

Table 4
a	c	b	d	d
a	a	a	d	d
a	c	b	d	d
a	b	c	d	d
d	d	d	a	a
d	e	e	a	a

The column headers of Table 4 are now deleted to get Table 5:

Table 5

a	a	a	d	d
a	c	b	d	d
a	b	c	d	d
d	d	d	a	a
d	e	e	a	a

The Cayley table of the binary operation ' $\star$ ' corresponding to the element c is given by Table 6.

Table 6
$\star$ (c)	a	b	c	d	e
a	a	a	a	d	d
b	a	c	b	d	d
c	a	b	c	d	d
d	d	d	d	a	a
e	d	e	e	a	a

Next choose the c column of Table 1:

Table 7
·	a	b	c	d	e
a	a	a	a	d	d
b	a	b	c	d	d
c	a	c	b	d	d
d	d	d	d	a	a
e	d	e	e	a	a

Copy this column to the index column to get Table 8:

Table 8

a
c
b
d
e

Against the index entry a in Table 8 copy the corresponding row in Table 1, against the index entry b copy the corresponding row in Table 1, etc., and construct Table 9.

Table 9

a	a	a	a	d	d
c	a	c	b	d	d
b	a	b	c	d	d
d	d	d	d	a	a
e	d	e	e	a	a

The index entries in the first column of Table 9 are now deleted to get Table 10:

Table 10

a	a	a	d	d
a	c	b	d	d
a	b	c	d	d
d	d	d	a	a
d	e	e	a	a

The Cayley table of the binary operation ' $\circ$ ' corresponding to the element c is given by Table 11.

Table 11
$\circ$ (c)	a	b	c	d	e
a	a	a	a	d	d
b	a	c	b	d	d
c	a	b	c	d	d
d	d	d	d	a	a
e	d	e	e	a	a

One can verify that the entries in the various cells in Table 6 agrees with the entries in the corresponding cells of Table 11. This shows that x · ( c · y ) = ( x · c ) · y for all x and y in A. If there were some discrepancy then it would not be true that x · ( c · y ) = ( x · c ) · y for all x and y in A.

That x · ( e · y ) = ( x · e ) · y for all x and y in A can be verified in a similar way by constructing the following tables (Table 12 and Table 13):

Table 12
$\star$ (e)	a	b	c	d	e
a	d	d	d	a	a
b	d	d	d	a	a
c	d	d	d	a	a
d	a	a	a	d	d
e	a	a	a	d	d

Table 13
$\circ$ (e)	a	b	c	d	e
a	d	d	d	a	a
b	d	d	d	a	a
c	d	d	d	a	a
d	a	a	a	d	d
e	a	a	a	d	d

A further simplification

It is not necessary to construct the Cayley tables (Table 6 and table 11) of the binary operations ' $\star$ ' and ' $\circ$ '. It is enough to copy the column corresponding to the header c in Table 1 to the index column in Table 5 and form the following table (Table 14) and verify that the a -row of Table 14 is identical with the a -row of Table 1, the b -row of Table 14 is identical with the b -row of Table 1, etc. This is to be repeated mutatis mutandis for all the elements of the generating set of A.

Table 14
	a	c	b	d	d
a	a	a	a	d	d
c	a	c	b	d	d
b	a	b	c	d	d
d	d	d	d	a	a
e	d	e	e	a	a

Algorithm for Light's associativity test

Computer software can be written to carry out Light's associativity test. Kehayopulu and Argyris have developed such an algorithm for Mathematica.^[1]

Extension of Light's associativity test

Light's associativity test can be extended to test associativity in a more general context.^[2]^[3]

Let T = { t₁, t₂, $\ldots$ , t_m } be a magma in which the operation is denoted by juxtaposition. Let X = { x₁, x₂, $\ldots$ , x_n } be a set. Let there be a mapping from the Cartesian product T × X to X denoted by (t, x) ↦ tx and let it be required to test whether this map has the property

(st)x = s(tx) for all s, t in T and all x in X.

A generalization of Light's associativity test can be applied to verify whether the above property holds or not. In mathematical notations, the generalization runs as follows: For each t in T, let L(t) be the m × n matrix of elements of X whose i - th row is

( (t_it)x₁, (t_it)x₂,

\ldots

, (t_it)x_n ) for i = 1,

\ldots

, m

and let R(t) be the m × n matrix of elements of X, the elements of whose j - th column are

( t₁(tx_j), t₂(tx_j),

\ldots

, t_m(tx_j) ) for j = 1,

\ldots

, n.

According to the generalised test (due to Bednarek), that the property to be verified holds if and only if L(t) = R(t) for all t in T. When X = T, Bednarek's test reduces to Light's test.

More advanced algorithms

There is a randomized algorithm by Rajagopalan and Schulman to test associativity in time proportional to the input size. (The method also works for testing certain other identities.) Specifically, the runtime is $O(n^2 \log \frac1\delta)$ for an $n\times n$ table and error probability $\delta$ . The algorithm can be modified to produce a triple $\langle a,b,c\rangle$ for which $(ab)c\ne a(bc)$ , if there is one, in time $O(n^2 \log n \cdot\log \frac1\delta)$ .^[4]

References

↑ Kehayopulu, Niovi; Philip Argyris (1993). "An algorithm for Light's associativity test using Mathematica". J. Comput. Inform. 3 (1): 87–98. ISSN 1180-3886.
↑ Bednarek, A R (1968). "An extension of Light's associativity test". American Mathematical Monthly 75 (5): 531–532. doi:10.2307/2314731. JSTOR 2314731.
↑ Kalman, J A (1971). "Bednarek's extension of Light's associativity test". Semigroup Forum 3 (1): 275–276. doi:10.1007/BF02572966.
↑ "Verification of Identities". SIAM Journal on Computing 29: 1155–1163. doi:10.1137/S0097539797325387.

Clifford, Alfred Hoblitzelle; Preston, Gordon Bamford (1961). The algebraic theory of semigroups. Vol. I. Mathematical Surveys, No. 7. Providence, R.I.: American Mathematical Society. ISBN 978-0-8218-0272-4. MR 0132791. (pp. 7–9)

This article is issued from Wikipedia - version of the Sunday, December 20, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.