# Light's associativity test

Jump to: navigation, search

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:

x $\star$ y = x · ( a · y )
x $\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 = { t1, t2, $\ldots$, tm } be a magma in which the operation is denoted by juxtaposition. Let X = { x1, x2, $\ldots$, xn } 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

( (tit)x1, (tit)x2, $\ldots$ , (tit)xn ) 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

( t1(txj), t2(txj), $\ldots$ , tm(txj) ) 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

1. ^ Kehayopulu, Niovi; Philip Argyris (1993). "An algorithm for Light's associativity test using Mathematica". J. Comput. Inform. 3 (1): 87–98. ISSN 1180-3886.
2. ^ Bednarek, A R (1968). "An extension of Light's associativity test". American Mathematical Monthly 75 (5): 531–532. doi:10.2307/2314731. JSTOR 2314731.
3. ^ Kalman, J A (1971). "Bednarek's extension of Light's associativity test". Semigroup Forum 3 (1): 275–276. doi:10.1007/BF02572966.
4. ^ Rajagopalan and Schulman, FOCS 1996, SICOMP 2000 http://dx.doi.org/10.1137/S0097539797325387