445 views

Skip to first unread message

May 21, 1990, 3:28:15 PM5/21/90

to

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)

May 22, 1990, 12:55:45 AM5/22/90

to

There is a well-known paper applying computer enumeration and

automated reasoning to semigroups, although not their associativity

per se:

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu