Browse Prior Art Database

On the n1092n Isomorphism Technique

IP.com Disclosure Number: IPCOM000128608D
Original Publication Date: 1978-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 6 page(s) / 20K

Publishing Venue

Software Patent Institute

Related People

Gary L. Miller: AUTHOR [+3]

Abstract

Tarjan has given an algorithm for deciding isomorphism of two groups of order n (given as multiplication tables) which runs in 0(n (log2n + 0(1)) steps where n is the order of the groups. Tarian uses the fact that a group of n is generated by log n elements. In this paper, we show that Tarjan technique generalizes to isomorphism of quasigroups, latin squares, and some graphs generated from latin squares.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 33% of the total text.

Page 1 of 6

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

On the n1092n Isomorphism Technique*

Gary L. Miller Departments of Computer Science and Mathematics The University of Rochester

TR17

Tarjan has given an algorithm for deciding isomorphism of two groups of order n (given as multiplication tables) which runs in 0(n (log2n + 0(1)) steps where n is the order of the groups. Tarian uses the fact that a group of n is generated by log n elements. In this paper, we show that Tarjan technique generalizes to isomorphism of quasigroups, latin squares, and some graphs generated from latin squares.

*This research was in part supported by the National Research Council, Grant #NRC-A5549; in part by the Alfred P. Sloan Foundation under Grant #74-12-5; and in part by the Advanced Research Projects Agency of the Dept. of Defense, monitored by ONR under Contract #NO0014-75-C-1091. A group throughout this paper is a Caley table. If G is a group of order n and we pick some linear ordering of G we can then view G as a binary function on {1,...,nl and the Caley table as a n xn matrix consisting of integers between 1 and n. If fact this table is a latin square (every number between I and n appears exactly once in every row and in every column). On the other hand, latin squares can be viewed as binary functions; whereas functions whose multiplication tables are latin squares are called quasigroups.

Giving the definition once more we have: A group is a binary operation satisfying 1) and 2).

(Equation Omitted)

2)

(Equation Omitted)

A quasigroup is a binary operation satisfying 1), and a quasigroup viewed as a table or a trinary relation is a latin square.

For groups or functions it is clear what we mean by isomorphism, namely, G is isomorphic to G' if there exists a 1-1 onto function g from G to G' such that g(x*y) = g(x)*'g(y). If we view G and G' as trinary relations < 9 > and < >~ respectively, then we get E: G implies ' E: G. Thus, viewing latin squares as quasigroups we say L and L' are isomorphic if there exists a permutation a such that if we simultaneously interchange rows, columns, and values in L we get L'. But this definition is quite restrictive. We know that independently permuting rows, columns, and values preserves the latin square properties. Thus, we say two latin squares are isotopic if we can get from one to the other by independently permuting rows, columns, and values; see

Definition: Two latin squares L and L' are said to be isotopic if there exists permutations (a, a Y) such that

(Equation Omitted)

implies

University of Rochester Page 1 Dec 31, 1978

Page 2 of 6

On the n1092n Isomorphism Technique

(Equation Omitted)

(Equation Omitted)

.

We say that two latin squares L and L' are conjugate if there exists a permutation a E: S3 such that

(Equation Omitted)

implies

(Equation Omitted)

. Finally, L and L' are main class isotopic, denoted by

(Equation Omitted)

,-if we can get from L to L' by a conjugation and an isotopic map.

Tar...