Light's associativity test

From Wikipedia, the free encyclopedia
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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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]

See also[edit]

References[edit]

  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