Light's associativity test

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 ${\displaystyle \star }$ y = x · ( a · y )

x ${\displaystyle \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 ' ${\displaystyle \star }$ ' and ' ${\displaystyle \circ }$ '.

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

When the operation ' . ' is commutative, then x ${\displaystyle \star }$ y = y ${\displaystyle \circ }$ x. As a result, only part of each Cayley table must be computed, because x ${\displaystyle \star }$ x = x ${\displaystyle \circ }$ x always holds, and x ${\displaystyle \star }$ y = x ${\displaystyle \circ }$ y implies y ${\displaystyle \star }$ x = y ${\displaystyle \circ }$ x.

When there is an identity element e, it does not need to be included in the Cayley tables because x ${\displaystyle \star }$ y = x ${\displaystyle \circ }$ y always holds if at least one of x and y are equal to e.

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

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 ' ${\displaystyle \star }$ ' and ' ${\displaystyle \circ }$ ' corresponding to c coincide and also that the binary operations ' ${\displaystyle \star }$ ' and ' ${\displaystyle \circ }$ ' corresponding to e coincide.

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

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

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.

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

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

Table 6

${\displaystyle \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:

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

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.

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

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

Table 11

${\displaystyle \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

${\displaystyle \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

${\displaystyle \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

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

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

Let T = { t₁, t₂, ${\displaystyle \ldots }$, t_m } be a magma in which the operation is denoted by juxtaposition. Let X = { x₁, x₂, ${\displaystyle \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₂, ${\displaystyle \ldots }$ , (t_it)x_n ) for i = 1, ${\displaystyle \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), ${\displaystyle \ldots }$ , t_m(tx_j) ) for j = 1, ${\displaystyle \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.

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 ${\displaystyle O(n^{2}\log {\frac {1}{\delta }})}$ for an ${\displaystyle n\times n}$ table and error probability ${\displaystyle \delta }$. The algorithm can be modified to produce a triple ${\displaystyle \langle a,b,c\rangle }$ for which ${\displaystyle (ab)c\neq a(bc)}$, if there is one, in time ${\displaystyle O(n^{2}\log n\cdot \log {\frac {1}{\delta }})}$.[4]

• 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)