Inmathematics,Light's associativity test is a procedure invented by F. W. Light for testing whether abinary operation defined in afinite set by aCayley multiplication table isassociative. The naive procedure for verification of the associativity of a binary operation specified by a Cayley table, which compares the two products that can be formed from each triple of elements, is cumbersome. Light's associativity test simplifies the task in some instances (although it does not improve the worst-case runtime of the naive algorithm, namely${\displaystyle \mathcal{O}\left(n^3\right)}$ for sets of size${\displaystyle n}$).

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

${\displaystyle x\star y=x\cdot (a\cdot y)}$

${\displaystyle x\circ y=(x\cdot a)\cdot y}$

The Cayley tables of these operations are constructed and compared. If the tables coincide then${\displaystyle x\cdot (a\cdot y)=(x\cdot a)\cdot y}$ for allx andy. This is repeated for every element of the setA.

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 }$ ' forall elements ofA. It is enough to compare Cayley tables of '${\displaystyle \star }$ ' and '${\displaystyle \circ }$ ' corresponding to the elements in a proper generating subset ofA.

When the operation ' · ' iscommutative, 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 anidentity 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 setA = {a,b,c,d,e } defined by the following Cayley table (Table 1):

The set {c,e } is a generating set for the setA 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 toc coincide and also that the binary operations '${\displaystyle \star }$ ' and '${\displaystyle \circ }$ ' corresponding toe coincide.

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

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

Under the headera copy the corresponding column in Table 1, under the headerb 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 elementc 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 thec column of Table 1:

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

Against the index entrya in Table 8 copy the corresponding row in Table 1, against the index entryb 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 elementc 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 thatx · (c ·y ) = (x ·c ) ·y for allx andy inA. If there were some discrepancy then it would not be true thatx · (c ·y ) = (x ·c ) ·y for allx andy inA.

Thatx · (e ·y ) = (x ·e ) ·y for allx andy inA 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

It is not necessary to construct the Cayley tables (Table 6 and table 11) of the binary operations '${\displaystyle \star }$ ' and '${\displaystyle \circ }$ '. It is enough to copy the column corresponding to the headerc in Table 1 to the index column in Table 5 and form the following table (Table 14) and verify that thea-row of Table 14 is identical with thea-row of Table 1, theb-row of Table 14 is identical with theb-row of Table 1, etc. This is to be repeatedmutatis mutandis for all the elements of the generating set ofA.

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

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

LetT = {t₁,t₂,${\displaystyle \dots }$,t_m } be amagma in which the operation is denoted byjuxtaposition. LetX = {x₁,x₂,${\displaystyle \dots }$,x_n } be a set. Let there be a mapping from theCartesian productT ×X toX denoted by (t,x) ↦tx and let it be required to test whether this map has the property

(st)x =s(tx) for alls,t inT and allx inX.

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 eacht inT, letL(t) be them ×n matrix of elements ofX whosei - th row is

( (t_it)x₁, (t_it)x₂,${\displaystyle \dots }$ , (t_it)x_n ) fori = 1,${\displaystyle \dots }$,m

and letR(t) be them ×n matrix of elements ofX, the elements of whosej - th column are

(t₁(tx_j),t₂(tx_j),${\displaystyle \dots }$ ,t_m(tx_j) ) forj = 1,${\displaystyle \dots }$,n.

According to the generalised test (due to Bednarek), that the property to be verified holds if and only ifL(t) =R(t) for allt inT. WhenX =T, Bednarek's test reduces to Light's test.

There is a randomized algorithm by Rajagopalan andSchulman 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 ⟨a,b,c⟩}$ for which${\displaystyle (ab)c\ne 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.{{cite book}}:ISBN / Date incompatibility (help) (pp. 7–9)

• Abstract algebra
• Semigroup theory
• Binary operations
• Elementary algebra

• Articles with short description
• Short description is different from Wikidata
• CS1 errors: ISBN date