# Evolution of a Computer Application - Groups16 -- 1990 version

Author(s):
John J. Wavrik

 The numbering of groups in this section is different from that in later sections and in the current Groups32 program. (Some of the groups in this section are isomorphic.)

Groups16 is an early version of the groups system.  The system originated with a posting to Usenet in 1989 by Kenneth Almquist. He had generated tables for groups of orders 1-16, apparently as an exercise in combinatorics programming. In his original posting some of the tables represented isomorphic groups.  Groups16 started in an effort to find out how much (or how little) one must know about groups to distinguish which tables were isomorphic.

The Almquist tables looked like this:

1 group of order 1:
___
A|A

1 group of order 2:
_____
A|A B
B|B A

1 group of order 3:
_______
A|A B C
B|B C A
C|C A B

2 groups of order 4:
_________        _________
A|A B C D        A|A B C D
B|B A D C        B|B C D A
C|C D A B        C|C D A B
D|D C B A        D|D A B C

1 group of order 5:
___________
A|A B C D E
B|B C D E A
C|C D E A B
D|D E A B C
E|E A B C D


An interesting thing happened: Some readers pointed out that Almquist had posted more groups of certain orders than the literature claimed.  He traced the problem to the fact that his algorithm had not detected that some of the original tables were isomorphic. A subsequent posting corrected the error.  However, this raised an interesting question: How much do you need to know about a group of order 1-16 to be able to easily detect isomorphism?  It is obvious that, even for groups of order 16, one does not try all possible bijective mappings to see if two groups are isomorphic.  Instead, one hopes to look at properties of the groups that must be preserved under isomorphism. The original steps in the system were to represent the data in a suitable way, and to implement words that computed various information about the groups.

### a. Data Representation

The original version was implemented on a computer that had only 64K of memory. The version of Forth used 16-bit integers and so could address only this much memory. The Forth system and DOS used 26K of memory -- and a nicer editor had been added to bring this to 44K.  This left just 20K for the group theory system and data.

Fortunately the Forth systems commonly available at that time provided a rather clever way to use the hard disk for virtual memory.  The disk was organized into 1024 byte blocks, and the system provided a word BLOCK with stack diagram ( n - addr ). Using 5 BLOCK, for example, the system would check if block 5 on the disk had already been loaded into memory. If not, it would be read from disk into a buffer. In either case, the base address of the buffer would be returned. With this scheme, one could create the illusion that a large amount of data was in memory.

For purposes of this article, I have moved the earlier code to a modern (32-bit) version of Forth on a computer that has 128 megabytes of memory.  I therefore put the tables into a section of the dictionary.  To make the earlier code run without rewriting, I redefined the word BLOCK to refer to parts of this section of memory.

The original tables were converted to an internal format by stripping everything except the interior squares of the tables. These were arranged sequentially by row:

   AABBAABCBCACABABCDBADCCDABDCBAABCDBCDACDABDABCABCDEBCDEACDEABDEA
BCEABCDABCDEFBCAEFDCABFDEDFEACBEDFBACFEDCBAABCDEFBCDEFACDEFABDEF
ABCEFABCDFABCDEABCDEFGBCDEFGACDEFGABDEFGABCEFGABCDFGABCDEGABCDEF
etc.


This amalgamation of the group tables was put in Blocks 1-10.  They were spaced so that tables did not straddle disk blocks. In order to locate a particular group, it is necessary to know the order of the group, the block in which the data are contained, and the number of bytes from the beginning of the block where the data are located.  With this information we can calculate the address in memory for a particular table.

Block 0 was used to store the triples Gnum, Gblk, Goffs for each group.

0  CONSTANT  IDXBLK   65  CONSTANT  ID
0  VALUE  GNUM   0  VALUE  GORD
0  VALUE  GBLK   0  VALUE  GOFFS


At this point I made an important decision. Most of my computations would be for a certain group, fixed for the moment.  Rather than write procedures to which I would have to pass the group number as a parameter, I designated the group of interest at the moment (given by number) as "the current group", and I wrote all procedures to refer to that current group.

My word to assign the current group is  >GROUP  -- it stores the group number as the value Gnum, as well as the triple mentioned above.  It is therefore not necessary to go back to block 0 each time we do a group computation, nor is it necessary to re-read the table from disk for each computation. Once the current group is specified, vital information about it is read into memory.

In the current version of Groups32, all the tables are stored in memory and the word >GROUP is replaced by an appropriate version.  The virtual memory scheme is not used, and it is not essential for the reader to understand how it is used.  It is, however, interesting that

1. there was such a mechanism for dealing with the limited memory of early computers and
2. code written to use this scheme can be updated fairly easily.

: >GROUP ( n -- ) \ set GORD GBLK and GOFFS
DUP TO GNUM
6 * IDXBLK BLOCK + DUP @ TO GORD
2+ DUP @ TO GBLK
2+ @ TO GOFFS ;


[To run this on a 32-bit system using the original data file, the @ needs to be replaced by W@, which fetches a 16-bit value.]

We now have the group data stored, together with information needed to locate the start of a particular table.  Next we want to implement multiplication - which means to locate an element in a particular row and column of the table. If we number the rows and columns from 0 to Gord-1, the entry in the i-th row and j-th column will be located  i*Gord + j bytes from the start of the table.

Remember that we are storing group elements as letters A, B, C, …  that a computer is representing by ASCII codes  65, 66, 67, … . If we want to multiply B and C in the current group, we must first subtract 65 (the ASCII code for "A") to get the row and column, and then compute the location of the product in the table.

: 'ELE ( ele1 ele2 – addr )     \ compute address of product
ID - SWAP ID - GORD * +   \ offset from base address
GBLK BLOCK GOFFS +        \ address of start of table
+ ;                       \ address of element


Now we can define a word to print the table of a group. We first define a word that takes two elements and returns their product:

: G*  ( ele1 ele2 - ele1*ele2 )
'ELE C@  ;


Notice we have named this word G* suggesting it computes the product of two elements in a group.

: .ELE  ( ele -- )
\ print element with a trailing space.
EMIT SPACE ;


The following word produces the limits for loops over all elements in the current group.

: GLIMITS ( -- u l )
\ loop limits to run through group
GORD  ID +  ID  ;

: TABLE   ( N -- )   >GROUP  CR
2 SPACES GLIMITS
DO  ." __"  LOOP CR
GLIMTS DO   I .ELE  ." |"
GLIMITS DO  J I G* .ELE LOOP CR
LOOP CR ;

You can't usually tell much about a group by looking at its table. I have found that the ability to generate tables in various formats is a useful way to transport information to other computer programs.

### b. Input and Output

At this point we have a way of representing and storing the main pieces of data for the program -- the group tables. We can "install" a group as the current group. We have defined the main "group theory" word, G*, which determines multiplication in the current group. We have the output word TABLE to display the table of a given group. In some sense, the word >GROUP is an input word: It allows us to specify the number of the group currently of interest.

The next step is to develop words that compute group information by chasing around the table.  We need a way to input an element of the current group. We cannot, at this moment, type "B C G*"  to get the product of B and C in the current group.  We could, however, type  66 67 G*. WHY? First note that G* takes two parameters that are expected to be ASCII codes of upper case letters within the range of the current group.  The parameters for G* must be on the stack in advance.  If we type B C G*, the system will start reading from the left and will try to find B and C as words in the dictionary. If it cannot find them, it will try to interpret them as numbers in the current base (10).  So 66 67 G* will work -- and the letters won’t.

Here is what happens on the current Forth system (Win32Forth) running the original code:

8 >group  ok
B C G*
Error: C is undefined


In this case, B is actually a word in the dictionary (having something to do with the editor) -- but its action is not to put 66 in the stack!  On the other hand, C is neither a word in the dictionary nor a recognized number. (Note 4)

Keep in mind that G* is expecting ASCII codes for group letters. An input format that requires the user to remember and put in these codes is not friendly. There are several ways to handle the input of group letters.

Input of Elements - method 1 (using a handler)

Forth is perfectly happy to work with strings that are not names for words in the dictionary (and not numbers):  We just precede them by a "handler," a word that reads a string from the following input and does something specific with it.

The Forth word ASCII (which is replaced by CHAR in the current Forth Standard) takes a following string and returns the ASCII code of its first character.  In the following example we use the word . (dot) to print the number on top of the stack (and remove it).

ASCII A . 65
ASCII B . 66
ASCII b . 98
ASCII C . 67
66 EMIT B
98 EMIT b


So, for example, we could say   ASCII B  ASCII C  G*  to multiply elements B and C.

In the 1990 version, I introduced a new handler, GETE:

: GETE BL WORD 1+ C@ ;


The Forth word WORD does not take parameters from the stack -- it reads the input stream. WORD, preceded by a delimiter, takes the next string from the input stream up to the delimiter and returns the address as a counted string.

So GETE gets the next word (up to blank) and returns its first character.  It is used just like ASCII but has a name that suggests that we are getting a group element.

Input of Elements - method 2 (making group elements dictionary words)

If we wish to use the simple syntax  B C G*  we could just make A, B, C, etc., words in the dictionary whose action is to put their ASCII codes on the stack.  The easiest way to do this is to make them constants:

65 CONSTANT A      66 CONSTANT B
67 CONSTANT C      68 CONSTANT D
69 CONSTANT E      70 CONSTANT F
71 CONSTANT G      72 CONSTANT H   etc.


There is a major disadvantage to this: The words I and J are the names used in Forth for loop indices. If they are redefined, they cannot be used with their original meanings. Any particular Forth implementation may already have some useful meaning attached to other letters. (Note 5)

A better approach is to use slightly different names, /A, /B, etc., for the group elements:

 65 CONSTANT /A      66 CONSTANT /B
67 CONSTANT /C      68 CONSTANT /D
69 CONSTANT /E      70 CONSTANT /F
71 CONSTANT /G      72 CONSTANT /H   etc.


This allows the syntax  /B /C G* when typing from the keyboard.

### c. Some First Procedures

: EORDER  ( ele -- ord )   ID  GLIMITS
DO  OVER G*  DUP ID =
IF 2DROP I ID - 1+ LEAVE THEN
LOOP ;


This computes the order of an element by taking powers until the identity is found.

 Output using EORDER for group 8 Table of group 8 for reference Definition of EORDER Comments for definition  /A EORDER . 1 /B EORDER . 6 /C EORDER . 3 /D EORDER . 2 /F EORDER . 6   8 table ____________ A |A B C D E F B |B C D E F A C |C D E F A B D |D E F A B C E |E F A B C D F |F A B C D E  : EORDER ID GLIMITS DO ( x x^n ) OVER G* DUP ID = IF 2DROP I ID - 1+ LEAVE THEN LOOP ;  loop over ASCII codes <- loop invariant ( x x^n x ) ( x x^[n+1] ) If pwr is ident compute order
: POWERS  GETE  ID  GLIMITS
DO  DUP .ELE  OVER G*  DUP ID =
IF 2DROP LEAVE THEN  LOOP ;


This computes and prints the powers of an element in the given group.  Note that the group letter comes after the POWERS command:

POWERS A A
POWERS B A B C D E F
POWERS C A C E
POWERS D A D
POWERS E A E C
POWERS F A F E D C B


There are two groups of order 4 (numbers 4 and 5 in our list of groups). They are not isomorphic -- which can be immediately seen by computing the orders of their elements.

 4 >GROUP /A EORDER . 1 /B EORDER . 2 /C EORDER . 2 /D EORDER . 2  5 >GROUP /A EORDER . 1 /B EORDER . 4 /C EORDER . 2 /D EORDER . 4 

At this point I intended the program just to find a quick way to determine whether two groups of order 1-16 are isomorphic. An obvious step toward solving the isomorphism problem is to recognize that certain properties of a group (such as the order of the group and the order of its elements) must be preserved. It seemed useful, therefore, to write a command to loop through all elements in a group and print their orders.

Here is a very simplified version of ORDERS.  In the next section we will develop fancier versions:

:  ORDERS ( grp# -- )   >GROUP
GLIMITS DO I EORDER . LOOP ;

4 ORDERS 1 2 2 2
5 ORDERS 1 4 2 4



### d. The Evolution of ORDERS

In this section I discuss several attempts to improve the functionality of ORDERS. The process illustrated here, where several versions of a word are produced, each improving upon the previous in some respect, is common. We always have the older version available for comparison – the system is never "broken" at any point. We try to write so that individual words can be improved without affecting other parts of the system.

The ORDERS command provides important information, but group letters may be rearranged in an isomorphism, so the orders of elements may be in a different order for two isomorphic tables. It may not be easy to see at a glance if two groups have the same number of elements of each order. It would also be much easier to compare two groups if the outputs were in a matching form. One approach would be to sort the list of orders of elements. A simpler approach, since we just want the number of elements of each order, is to define a new version of ORDERS that does book-keeping. We need an array to save the number of times each order occurs. Here we look at a way to build special types of array structures by allocating memory and producing words to access it.

I wrote the original version of Groups16 using F83, a 16-bit version of Forth (integers occupied 16 bits or 2 bytes) so a sequence of integers in memory had addresses 2 units apart. To allocate a block of memory for storage of up to 20 integers I used

CREATE OCNT 40 ALLOT

Invoking the word OCNT puts the base address of this block of storage on the stack. We now need to locate the address of the kth integer in this block:

: 'OCNT  ( k – addr )  2* OCNT +  ;


We need to be able to increment the number at this location:

: +OCNT  ( k --  )   'OCNT  1 SWAP +!  ;


And we need to be able to initialize the array (setting all integers to zero):

: OCLEAR  OCNT 40 ERASE ;


This code contains assumptions about the size of an integer and is one of the few places where modification of the code was needed when I transported it to Win32Forth for this article. Win32Forth is a 32-bit version, and addresses for consecutive integers are 4 bytes apart.  The "bittedness" assumptions in the earlier code are in the use of 40 ALLOT to make space for 20 integers and in the use of 2* in the calculation of the address for a particular table entry.

What is bad about this is that one cannot update the code automatically. (Sometimes 2* is used for multiplication by 2 -- it cannot be just changed to multiplication by 4 everywhere.)

Here is a way to make the code "implementation independent":  Rather than introduce "magic numbers" in the code, we introduce a word or words to contain the implementation-specific information used for allocation and address calculations.  The word CELL is used to refer to the size of an integer or stack element. For F83 it has the value 2, and for Win32Forth it has the value 4.  The word CELLS multiplies a number on the stack by CELL. (Note 6) With this understanding, the following definitions would work on either version of Forth:

CREATE OCNT 20 CELLS ALLOT
: 'OCNT  ( k – addr )  CELLS OCNT +  ;
: +OCNT  ( k --  )   'OCNT  1 SWAP +!  ;
: OCLEAR  OCNT 20 CELLS ERASE ;


The use of CELLS rather than 2* (which does the same in F83) has the advantage of alerting the reader to the fact that memory allocation is the issue here, rather than arithmetic.  It can be useful to have different names for the same action to clarify the purpose for which the action is being taken.

We now define an improved version of ORDERS:

:  ORDERS ( grp# -- )  >GROUP
OCLEAR
GLIMITS DO I EORDER +OCNT LOOP

GNUM 3 .R  GORD 3 .R 2 SPACES
20 1 DO
GORD I MOD 0=
IF I 'OCNT @ . THEN
LOOP ;


There are two sections of this code, one to count the orders and the second to print the results. Notice that we print the number of elements of order k only when k is a divisor of the order of the group.

8 orders   8  6  1 1 2 2
21 orders  21 12  1 3 8 0 0 0


A slight further refinement of the output section makes it possible to produce a comma- and quote-delimited file for use in a spreadsheet.  For future reference, here are words that print a comma or quotation marks, respectively:

: COMMA   ASCII , EMIT ;
: QUOTES  ASCII " EMIT ;


These can be used to produce "comma-delimited" output that is accepted by most spreadsheet programs. The spreadsheet file looks like this:

 gnum gord # elements of each order 1 1 "  1" 2 2 "  1  1" 3 3 "  1  2" 4 4 "  1  3  0" 5 4 "  1  1  2" 6 5 "  1  4" 7 6 "  1  3  2  0" 8 6 "  1  1  2  2" 9 7 "  1  6" 10 8 "  1  7  0  0" 11 8 "  1  3  4  0" 12 8 "  1  5  2  0" 13 8 "  1  1  6  0" 14 8 "  1  1  2  4"

The ability to export these results to a spreadsheet program (where they can be sorted and examined) proved to be a major step in identifying which of the original set of groups might be isomorphic. The number of elements of each order is preserved under isomorphism -- groups that differ in this invariant are certainly not isomorphic. We ask whether the following theorem is true:

Theorem?  Two groups of order n are isomorphic if and only if they have the same number of elements of each order.

I think most of us would regard such a theorem as unlikely. (If it were true, it would have been proved by Lagrange or Cauchy, and we would find it in textbooks.) If it is false, what is the first counter-example?

Notice that the chart above shows that up to order 8, groups are distinguished by the numbers of elements of various orders. The theorem is also true if we require the groups to be abelian. (Two abelian groups are isomorphic if and only if they have the same number of elements of each order.) For what N is the theorem true for n < N?

My last step in modifying ORDERS was to produce output in a more pleasant format.

 4 orders Group number 4 of Order 4 1 elements of order 1: A 3 elements of order 2: B C D 0 elements of order 4:  5 orders Group number 5 of Order 4 1 elements of order 1: A 1 elements of order 2: C 2 elements of order 4: B D 

Producing this output requires saving not only the count but also the order of each element. The original code, as mentioned, had built-in assumptions that integers were 16-bit. We show both the original and modified version of the code for this final version of ORDERS.

 Original version for F83 - 24Mar90jjw Revised for Win32Forth CREATE OTABLE 40 ALLOT CREATE OCNT 40 ALLOT  : 'ORD ( ele -- addr ) ID - 2* OTABLE + ; : 'OCNT ( i -- addr ) 2* OCNT + ; : +OCNT ( ord -- ) 'OCNT 1 SWAP +! ; : ORD! ( ord ele -- ) 'ORD ! ; : OCLEAR OTABLE 40 ERASE OCNT 40 ERASE ;  CREATE OTABLE 20 CELLS ALLOT CREATE OCNT 20 CELLS ALLOT  : 'ORD ( ele -- addr ) ID - CELLS OTABLE + ; : 'OCNT ( i -- addr ) CELLS OCNT + ; : +OCNT ( ord -- ) 'OCNT 1 SWAP +! ; : ORD! ( ord ele -- ) 'ORD ! ; : OCLEAR OTABLE 20 CELLS ERASE OCNT 20 CELLS ERASE ; 

Using these auxiliary words, the new definition of ORDERS is

: ORDERS  ( grp# --  )  CR >GROUP
." Group number " GNUM .
." of Order " GORD .  CR  OCLEAR
GLIMITS  DO
I EORDER DUP +OCNT I ORD!  LOOP
GORD 1+ 1 DO  GORD I MOD 0=
IF 3 SPACES I 'OCNT @ 2 .R
."  elements of order "

I 2 .R ." :   "
GLIMITS DO I 'ORD @ J =
IF  I .ELE THEN
LOOP  CR
THEN  LOOP ;

This code is hard to read. Too many different functions are combined in one word. It takes a sharp eye to discern that part of this code is devoted to computing orders and part to printing results.  Code that is designed to produce aligned output is mixed with code to perform computations. Code that is essentially routine "boilerplate" conceals the main ideas.  By the time of Groups32, I paid some attention to writing style, as I will discuss shortly.

Here is the current version of ORDERS:
: Orders  ( grp# --  )   CR >Group
." Group number " Gnum .
." of Order "     Gord .  CR
Calc-Orders  Prt-Orders  ;


### e. Finding Isomorphisms

All of the groups in Almquist's list have different distributions for the orders of elements until we get to his groups of order 12. Here we find, for the first time, two groups in his list that have the same number of elements of each order.

 Gnum  Gord  #elements of each order  25  12  " 1 1 2 2 2 4"  24  12  " 1 1 2 6 2 0"  22  12  " 1 3 2 0 6 0"  20  12  " 1 3 8 0 0 0"  21  12  " 1 3 8 0 0 0" 

Groups #20 and #21 are, therefore, the first groups in the original set that could be isomorphic. To show that they are isomorphic, we need to display an isomorphism between them. A first attempt at displaying an isomorphism is to create a mechanism for showing what happens to a table under a mapping of elements.  We imagine a mapping X that sends the letters A, B, C, … to the same letters in a permuted order.

CREATE 'XG  20 ALLOT   \ This will contain the images of A,B,C,…

: XG   ( ele - xele )  \  given ele this displays the image xele
ID - 'XG + C@ ;

: XG'  ( xele - ele )     \  this finds the inverse image of a letter
GLIMITS DO I XG OVER =
IF DROP I LEAVE THEN LOOP ;

: XG*  ( x1 x2 - x3 )  \ Multiply in image group
XG' SWAP XG' SWAP G* XG  ;

: >XG   ( follow by string in letters )
\  this allows input of the mapping
BL WORD COUNT 'XG SWAP CMOVE ;

: RTABLE  ( n -- )  \  This prints the table of the image group
>GROUP   CR
2 SPACES  GLIMITS DO  ." __"  LOOP  CR
GLIMITS DO   I .ELE ." |"
GLIMITS DO  J I XG* .ELE LOOP CR
LOOP CR ;

 >XG ACBD  This applies map A to A, B to C, C to B, D to D 5 TABLE ________ A |A B C D B |B C D A C |C D A B D |D A B C  Original table for group 5  _A_C_B_D A|A C B D C|C B D A B|B D A C D|D A C B  Intermediate table obtained by interchanging B and C wherever they occur. 5 RTABLE ________ A |A B C D B |B A D C C |C D B A D |D C A B  Final table obtained by rearranging rows and columns

We have applied the isomorphism X and obtained the resulting table.  Can we apply an isomorphism like this to Group #20 and transform its table to that of Group #21?

There are 12! = 479,001,600 candidates for X. However, if X is an isomorphism from group 20 to group 21, it must send A to A, it must send an element of order k to an element of order k, and it must send a product in the first group to the product of the images in the second group. (In fact, the map is determined by what it does to the generators -- but we do not yet have tools to determine the generators.)

 20 orders Group number 20 of Order 12 1 elements of order 1: A 3 elements of order 2: D I K 8 elements of order 3: B C E F G H J L 0 elements of order 4: 0 elements of order 6: 0 elements of order 12:  21 orders Group number 21 of Order 12 1 elements of order 1: A 3 elements of order 2: E I K 8 elements of order 3: B C D F G H J L 0 elements of order 4: 0 elements of order 6: 0 elements of order 12: 

 20 table ________________________ A |A B C D E F G H I J K L B |B C A E F D H I G K L J C |C A B F D E I G H L J K D |D G J A L H B F K C I E E |E H K B J I C D L A G F F |F I L C K G A E J B H D G |G J D L H A F K B I E C H |H K E J I B D L C G F A I |I L F K G C E J A H D B J |J D G H A L K B F E C I K |K E H I B J L C D F A G L |L F I G C K J A E D B H  21 table ________________________ A |A B C D E F G H I J K L B |B C A E F D H I G K L J C |C A B F D E I G H L J K D |D I L G C K A F J B H E E |E G J H A L B D K C I F F |F H K I B J C E L A G D G |G J E A L H D K B I F C H |H K F B J I E L C G D A I |I L D C K G F J A H E B J |J E G L H A K B D F C I K |K F H J I B L C E D A G L |L D I K G C J A F E B H 

If we map B to B, then we must map C to C, since C is B*B in both groups.  D must get mapped to an element of order 2.  Let’s try D to E. B*D is F in Group 20, B*E is F in group 21 so we should map F to F.  Continue working in this fashion.

   >XG ABCEFDGHIJKL
20 RTABLE
A |A B C D E F G H I J K L
B |B C A E F D H I G K L J
C |C A B F D E I G H L J K
D |D I L G C K A F J B H E
E |E G J H A L B D K C I F
F |F H K I B J C E L A G D
G |G J E A L H D K B I F C
H |H K F B J I E L C G D A
I |I L D C K G F J A H E B
J |J E G L H A K B D F C I
K |K F H J I B L C E D A G
L |L D I K G C J A F E B H


This can be seen to be the same as the table for group 21.  We have, therefore, shown that groups 20 and 21 are isomorphic by displaying an isomorphism between them.

 The ISOMORPHISM command in Groups32 developed from this idea.  It is much more sophisticated:  It allows the user to experiment with images of elements (undoing trials if they do not seem to work), automatically computes and fills in all consequences of a partial mapping, checks for inconsistencies, etc.

John J. Wavrik, "Evolution of a Computer Application - Groups16 -- 1990 version," Convergence (December 2004)

## JOMA

Journal of Online Mathematics and its Applications