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. 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
l{O}\left(n3\right)
n
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
x
\circ
The example below illustrates a further simplification in the procedure for the construction and comparison of the Cayley tables of the operations '
\star
\circ
It is not even necessary to construct the Cayley tables of '
\star
\circ
\star
\circ
When the operation ' . ' is commutative, then x
\star
\circ
\star
\circ
\star
\circ
\star
\circ
When there is an identity element e, it does not need to be included in the Cayley tables because x
\star
\circ
Consider the binary operation ' · ' in the set A = defined by the following Cayley table (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 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
\circ
\star
\circ
To verify that the binary operations '
\star
\circ
· | 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):
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.
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:
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
\star | 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:
· | 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:
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.
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:
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
\circ | 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):
\star | 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 |
\circ | 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 '
\star
\circ
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 |
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 = be a magma in which the operation is denoted by juxtaposition. Let X = 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
\ldots
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
\ldots
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
O(n2log
1\delta) | |
n x n
\delta
\langlea,b,c\rangle
(ab)c\nea(bc)
O(n2logn ⋅ log
1\delta) | |