Associativity Problem
Eric Postpischil (Always mount a scratch monkey.)
Recap
Richard Henderson asked for information on the number of closed associative
functions on a set of five elements, given that a particular element was
the identity element.
I responded with an answer of 4,122, and added that there were 208,672
associative functions on a set of six elements with a particular one of them
being the identity element.
Basil Gordon at UCLA said that John Selfridge's 1958 Ph.D. thesis at UCLA
covered this, indicating 4,105 for the original question, as well as some other
results. Gordon also reported that 228 of these are non-isomorphic, 156 if
anti-isomorphisms are excluded. I agree with the latter two figures, but I
believe 4,105 is incorrect.
The Adventure Continues
The local Digital library borrowed Selfridge's thesis for me (UCLA sent the
original!). It is "On Finite Semigroups" by John L. Selfridge, June, 1958, LD
791.9 M2S465. I have checked the theorems in it and the numbers. The theorems
look good, although there are a few points I still wish to check. (E.g.,
there's a spot where Selfridge assigns values to/transposes elements in an
array and expects the result to still be "normal" [first of its isomorphism
class when sorted by row-major order], and I need to convince myself that is
true.)
However, Selfridge presents a table enumerating the arrays in various
categories, and I think there are a few errors in it. The bulk of the thesis
is 145 pages listing 1,915 closed, associative, non-isomorphic arrays
which are binary operations on { 0, 1, 2, 3, 4 }. Selfridge describes the
algorithm used to find these arrays, and I also find 1,915 of these arrays, so
we agree on that. However, it is not apparent to me how some of the other
numbers in the table were derived. I have reproduced the enumerations with my
own programs, and I find a few discrepancies.
I'll duplicate Selfridge's table here. Since the theorems seem sound and I
do not know what method Selfridge used to produce the numbers I disagree with,
I do not see a good way to settle the matter except to check my own results.
I welcome any suggestions for further investigation. Also, if anybody knows
of other work in this area or related information, please let me know. I may
check the index to citations to see if Selfridge's thesis has been used
elsewhere; is it worth doing?
Before presenting the table, I need to define some terminology, some standard
and some that Selfridge uses. I'll start with the basics because it leads into
Selfridge's terminology and also for the benefit of any interested parties
reading this who are new to it. Feel free to send mail or post a message if
you would like more information.
A binary operation on a set S is any function from the Cartesian product SxS to
a set V. A binary operation on S is closed if V is contained in S. The sets
S and V and the operation * form a system, and the order of the system is the
cardinality of S. If the operation is closed, the system may be denoted with
just (S,*). Products of the operation may be written a*b or ab. The operation
is said to be associative if (ab)c = a(bc) for all a, b, and c in S. It is
commutative if ab = ba for all a and b in S. An element e of a system is
called an identity (or unit) if ae = ea = a for all a in S. (A basic theorem
states that there is at most one identity element in a system.)
Two systems consisting of S, U, and * and T, V, and *' are isomorphic if there
is a one-to-one function f from S union U to T union V such that for all a and
b in S, f(a*b) = f(a)*'f(b). The two systems are anti-isomorphic if there is a
function f such that f(a*b) = f(b)*'f(a) for all a and b in S.
Note that a binary operation can be represented by an n by n array filled in
with values from V. A table of order n is a system with S = { 0, 1, . . . n-1
} and the set V = { 0, 1, . . . n^2+n-1 }. Since V extends from 0 to n^2+n-1,
each element in the array can be identical to one of the elements of S or can
be different from each element of S and all other elements of the array. Thus,
every system of order n is isomorphic to a table of order n. (An arbitrary
system might have something other than numbers as the elements of its sets,
but whatever they are, they can be mapped isomorphically to the numbers from
0 to n^2+n-1.) As Selfridge says, "Hence for all questions of description and
classification of systems, we may restrict our attention to tables.".
A set of tables isomorphic to each other form a class. A type is either a pair
of classes which have tables anti-isomorphic to each other or a single class
whose elements are anti-isomorphic to themselves.
For closed systems, Selfridge lists categories with and without each possible
combination of restrictions to associativity, commutativity, and possession of
identity. Within each of those categories, Selfridge enumerated tables,
classes, and types. (In the categories possessing commutativity, the numbers
of tables and classes are identical, so separate entries for classes are
omitted.)
For systems not restricted to being closed (but not required not to be),
Selfridge enumerated the commutative and identity-possessing tables. I will
not reproduce those here; they are derived from formulae:
total tables of order n: (n^2+n)^n^2
(fill in n^2 spaces with any of n^2+n values),
unit-possessing tables: n(n^2+n)^(n-1)^2,
(select a unit, fill in remaining (n-1)^2 spaces),
commutative tables: (n^2+n)^C(n+1,2),
(fill in diagonal and one side of it), and
commutative and with unit: n(n^2+n)^C(n,2)
(select unit, fill in diagonal and one side).
C(a,b) denotes the number of ways to choose b objects from a set of a objects;
C(n,2) = n(n-1)/2.
Selfridge's results for closed systems follow. Letters in parentheses refer
to my annotations below. I have checked all the entries in this table, by
either machine enumeration or the indicated formulae.
A C
S O
S M W
O M I
C U T
C I T H
L A A
O T T U
S I I N
E V V I order
D E E T 1 2 3 4 5 n
------- ------- - -- ------ --------- ----------------- ---------------
X X X X types 1 2 5 19 78
tables 1 4 27 376 7,345(c)
X X X types 1 3 12 58 325
tables 1 6 63 1,140 30,730
X X X types 1 2 6 27 156
classes 1 2 7 35 228
tables 1 4 33 624 20,525(d) (f)
X X types 1 4 18 126 1,160
classes 1 5 24 188 1,915
tables 1 8 113 3,492 183,732
X X X types 1 2 15 720
tables 1 4 81 16,384 48,828,125 n^[C(n,2)+1]
X X types 1 4 129 (b)
tables 1 8 729 1,048,576 30,517,578,125 n^C(n+1,2)
X X types 1 2 30
classes 1 2 45
tables 1 4 243 1,048,576 3,814,697,265,625(e) n^[(n-1)^2+1]
X types 1 7 1,596(a)
classes 1 10 3,330
tables 1 16 19,683 4^16 5^25 n^n^2
(4^16 = 4,294,967,296. 5^25 = 298,023,223,876,953,125.)
a: 1,596 is clearly incorrect because the number of types must be at
least half the number of classes, since at most two classes form a
type, and 3,330 is the number of closed classes of order 3. My
enumeration is 1,734. Since 1,734 + 1,596 = 3,330, this appears to
be a simple procedural error of writing the number of classes
eliminated by anti-isomorphism instead of the number left after
elimination.
b: I have a new result for this space: 43,968.
c: My result differs from Selfridge's; I get 7,430; I found 85 more
tables than Selfridge.
d: This is the original discrepancy that prompted this check; Selfridge
found 20,525 closed, associative, unit-possessing tables. If the
unit element is restricted to a particular element, that reduces to
4,105. I found 4,122. My result without the element restriction is
20,610, again 85 more than Selfridge.
e: This appears to be an arithmetic error; 5^[4^2+1] = 5^17 =
762,939,453,125. Selfridge's number is 5^18.
f: I have a new result for order 6: 6*208,672 = 1,252,032.
Selfridge does not indicate how the 20,525 figure was arrived at. Section 7 of
the thesis discusses machine enumeration of semigroups (closed associative
systems). It appears that normal semigroups were enumerated. (Selfridge
defines an ordering for tables, and a table is normal if it is the earliest
member of its isomorphism class in the ordering.) Most of Selfridge's thesis
deals with characteristics of normal tables, but this discrepancy is in the
count of total tables.
The number of normal semigroups is the number of isomorphism classes. Given
that number, one might compute the total number of semigroups if one knew how
many semigroups there were in each isomorphism class. This varies from class
to class. I'll describe an approach below.
Given a semigroup, one could examine each of the n! permutations of it. (This
requires permuting the rows and columns and the elements themselves. E.g.,
suppose (1 2 3)(4 5) is being applied and the element in row 2, column 3 is a
4. It moves to row 3, column 1 and becomes a 5.) One or more of those
permutations will yield the same semigroup. (Obviously the identity
permutation will; the other permutations may or may not.) Suppose k of the n!
permutations yield the original semigroup. Then there are n!/k semigroups in
this isomorphism class, because each of those other semigroups also yields
itself under k of the n! permutations.
Another method would be to enumerate the order 5 semigroups without regard to
normality. I cannot tell which method Selfridge used, if either were used. If
you have any ideas, please mail or post them.
When Richard Henderson posed the original question, I wrote a program which
started with row 0 and column 0 filled in with 0 1 2 3 4, to make 0 the
identity. Then the program attempted to fill in each of the remaining
positions, checking that associativity was maintained at each step. This
program yielded a count of 4,122 arrays. (All of my programs are available
upon request.)
When Basil Gordon posted the information about the contrary result, I had my
program write each of the arrays to a file. Each array was written on a single
line, with all 25 digits printed in row-major order. A new program was written
to read each line, test that it contained 25 digits each from 0 to 4, test
that the lines were in strictly increasing order, test that the 0 element was
the identity, and test that associativity was maintained. The program
correctly identified errors in a few sample cases; it passed the entire 4,122
lines without finding an error.
The lines were checked independently by Dan E'Eramo here at Digital. If
anybody else is interested, I will mail the file to them.
Since receiving Selfridge's thesis, I rewrote my program not to assume that
0 was the identity element -- it just searched for all closed associative
operations of order 5. Upon finding each one, it classified it according to
whether or not it was commutative, unit-possessing, and normal. The program
also checked whether the array followed transpositions of any of its
permutations when sorted by row-major order; any array which did not follow
such transpositions is the earliest representative of a type. After completing
the search, the program printed counts in each of the categories Selfridge
used; they matched except as noted above.
-- edp (Eric Postpischil)
Lewis Stiller
automated reasoning to semigroups, although not their associativity
per se:
@article{winkerwoslusk1981,
author = "S. Winker and L. Wos and E. Lusk",
title = "Semigroups, antiautomorphisms, and involutions:
a computer solution to an open problem, I",
journal="Mathematics of Computation",
volume=37,
number=156,
pages="533-545",
month="October",
year=1981}
Thanks for your posting, and keep us apprised: the question is interesting.
lewis