|
The program below runs in seconds for order 5 and says there are 4,122
associative functions. Does it look correct?
-- edp
#define MAX_SIZE 100
static int f[MAX_SIZE][MAX_SIZE];
static int size;
unsigned int assign(int x, int y, int z);
main()
{
unsigned int i, num, max_size;
/* Read maximum size to work on from input.
*/
if (scanf("%d", &max_size) != 1)
exit(0);
if (max_size > MAX_SIZE)
exit(0);
/* Initialize all elements involving identity, so that ex = x = xe.
* (Other elements of the array should not be referred to until
* assigned.)
*/
for (i = 0; i < max_size; i++)
f[i][0] = f[0][i] = i;
/* For each size, call the assign routine to find the number of
* associative functions. Assign is initially called with
* assign(0, size-1, size-1); this redundantly assigns the
* product of identity and the last element to be the last element
* and then starts looping on the remaining unassigned entries in
* the function.
*/
for (size = 1; size <= max_size; size++)
printf("There are %u associative functions of order %d.\n",
assign(0, size-1, size-1), size);
}
/* This function takes as input:
*
* the function f as an array of integers with all elements preceding
* f[x][y] in row-order already assigned values and with all elements
* in the identity row and the identity column already assigned,
*
* a value z to assign to f[x][y], representing "z = xy", and
*
* the size of the set whose Cartesian product is the domain of the
* function (in the global variable called "size").
*
* It returns the number of associative functions that can be made by filling
* in the remaining unassigned positions in the function, given the already
* assigned positions.
*/
unsigned int assign(int x, int y, int z)
{
/* Declare some variables and set the counter to zero.
*/
int u, v, w, uv, vw, vl, wl;
unsigned int num = 0;
/* Assign the current position.
*/
f[x][y] = z;
/* Check to make sure the most recent assignment leaves the
* function still associative.
*
* This is done by checking triples (u, v, w) to ensure
* that (uv)w = u(vw). Every triple is checked except those
* involving an identity element or those involving an unassigned
* product (which can be uv, vw, (uv)w, or u(vw).
*
* It is permissible not to check unassigned products because
* when we have assigned the last element of the array, there will
* be no unassigned products and every triple (u, v, w) will be
* checked except those where u, v, or w is the identity element.
* Therefore, it is not necessary to verify that this routine
* excludes non-associative assignments until the final assignment is
* reached.
*
* However, it is necessary to verify that no associative functions
* are excluded from the search. This happens if the "return 0"
* statement is reached incorrectly. This verification is provided
* by the statements immediately preceding the return.
*
* Checking the identity elements is not necessary because
* associativity always holds when either u, v, or w is the identity:
*
* e(vw) = vw and (ev)w = vw,
* u(ew) = uw and (ue)w = uw,
* u(ve) = uv and (uv)e = uv.
*
* If it is found that associativity is violated given the current
* assignments, 0 is returned because there are no ways to fill in
* the remaining unassigned products so that the function is
* associative.
*
*/
/* First u is looped through various values. As explained above,
* it is not necessary to verify that these values are correct,
* except in the case when the last element is being assigned. When
* the last element is being assigned, x is the last row of the
* array, so u loops through all non-identity rows of the array.
*/
for (u = 1; u <= x; u++)
{
/* Then v is looped through various values. Again, it
* is not necessary to verify correctness except when
* x and y indicate the last element of the array. Since
* the following conditional statement assigns either y or
* x to vl and y and x are both the last index, v ranges
* from index 1 to the last index.
*/
vl = (u == x && x > y) ? y : x;
for (v = 1; v <= vl; v++)
{
uv = f[u][v];
/* The following statement exits the current loop
* when uv is in a row with no assignments. It is
* not necessary to verify this except in the case
* of x and y indicating the last element. When that
* is so, all entries in f have been assigned some value
* from 0 to the highest element. uv is entry f[u][v],
* so it has been assigned a value and that value is
* less than or equal to x. The loop is not exited.
*/
if (uv > x)
continue;
/* Again, we do not need to verify the w limit except
* to note that either x, y, or size-1 is assigned to
* wl. When x and y are the last index, all three
* of those values are size-1, so w ranges from 1 to
* the last index.
*/
wl = v == x ? y : size-1;
if (uv == x && wl > y)
wl = y;
for (w = 1; w <= wl; w++)
{
vw = f[v][w];
/* Here we need to verify the loop is not
* left if x and y are the last indexes. As
* before, vw is an assigned element of f, so
* it is less than or equal to y.
*/
if (u == x && vw > y)
continue;
/* Now we are about to see if associativity
* is violated and return 0 if it is. Since
* we did not prove above that uv, vw, (uv)w,
* and u(vw) were defined, we need to prove
* it here. This is done by directly checking
* each product's position in row-order with
* the current position. If we have made a
* mistake above, so that any of uv, vw,
* (uv)w, or u(vw) are not defined, the
* program will exit without printing a
* result.
*/
#define verify_defined(r0, c0, r1, c1) \
{ \
if ( (r0 > r1) || ((r0 == r1) && (c0 > c1)) ) \
exit(0); \
}
verify_defined( u, v, x, y);
verify_defined( v, w, x, y);
verify_defined(uv, w, x, y);
verify_defined( u, vw, x, y);
/* Finally, if all the products are defined,
* verify that associativity holds for this
* triple. If it is violated, return 0.
*/
if (f[u][vw] != f[uv][w])
return 0;
}
}
}
/*
* If associativity holds and all products are assigned, then 1
* is returned because there is 1 associative function using the
* current assignments.
*
* Otherwise, the next element in row-order is selected and each
* possible value in the function range is assigned to it, and
* the number of associative functions given each such assignment
* are counted (i.e., this routine is called recursively).
*
*/
if (y == size-1)
if (x == size-1)
return 1;
else
x++, y = 1;
else
y++;
for (z = 0; z < size; z++)
num += assign(x, y, z);
return num;
}
|
| 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)
|