From:

~~~ ~~~ Subject:

I have reluctantly concluded that encoding the nodes of a breadth first

search tree as resentative elements of M-conjugacy classes cannot be

combined with Shamir's method. The short version of the reason is that

Shamir works only for post-multiplying, and we must both pre-multiply and

post-multiply in order to calculate M-conjugates.

It is possible, I think, to use a number of what might be called "clever

hacks" involving M-conjugacy to reduce rather considerably the memory

requirements of a program implementing Shamir's method, but the basic

method cannot store just the representative elements. I will describe the

clever hacks if and when I get a working program. How "clever" the clever

hacks are may lie in the eye of the beholder. In all cases, they exchange

reduced storage requirements for increased running time. It is always a

question as to whether such trade-offs are advantageous or not.

The longer explanation follows. I will be starting with some real basics.

Almost any reasonable introductory or advanced math book will talk about

functions. There are two basic views of what a function is. In one view,

a function is a non-empty set X, a non-empty set Y, and some general rule

or correspondence such that for every x in X, there is exactly one y in Y.

In the other view, you start out with the set of all ordered pairs (x,y)

with x in X and y in Y. This set is usually called X x Y (X cross Y). A

function is then a non-empty subset of X x Y such that every x appears

exactly one time as the left hand element of the ordered pair, so that

again for every x in X there is exactly one y in Y.

The second definition is probably more accurate, but it loses (on purpose,

perhaps) the intuitive feel that there is some sort of "general" rule

relating X and Y. Indeed, for a finite X and Y, there may be no shorter

way to specify a particular function than simply to list the set of

ordered pairs of which it is comprised.

A function where X and Y are the same set is said to be a function "on X".

A function may be one-to-one or onto or both. There are many (equivalent)

definitions, but my favorites are that a function is onto if there is at

least one x for every y, and a function is one-to-one if there is at most

one x for every y. Hence, a function is both one-to-one and onto if there

is exactly one x for every y. This condition is necessary if we wish to

be able to run the function backwards, that is, if we wish to have an

inverse function. Finally, a function that is on a set and which is

one-to-one and onto is a permutation. We model the Rubik's cube as a set

of permutations.

Suppose F and G are functions. In algebra and calculus, we define the

composition of two functions something like the following: FoG(x)=F(G(x)).

Proper treatment of this definition would require some care in handling

the domain and range of the respective functions. But we will dispose of

this issue by simply stipulating that F and G are permutations on the same

set.

The algebra/calculus notation for function composition yields a

right-to-left evaluation of the functions. This is especially visible if

we compose more than two functions, e.g., FoGoH(x)=F(G(H(x))). In group

theory, function composition is more typically written left-to-right such

as HGF for the example at hand, with debates about where the argument

goes. I prefer in front -- (x)HGF. In Cube Theory, we almost *always*

write operators left-to-write, following group theory rather than

algebra/calculus.

This whole left-to-right vs. right-to-left issue is critical for for

proper implementation of Shamir. It is especially critical to get it

right because essentially all programming languages follow the

algebra/calculus model, whereas Cube Theory follows group theory. Hence,

everything is always backwards to some extent in a program.

I'm an *old* programmer, so my first higher level programming language

(after assembler) was FORTRAN. FORTRAN lets you have statements such as

Y=X(I) or Y=SQRT(X). FORTRAN has rather obtuse semantics and is hard to

compile. I can remember at the time I learned FORTRAN being puzzled by

how the compiler could figure out whether parentheses meant function

arguments or whether parentheses meant subscripts. More "modern"

languages (say, those less than 20 years old) tend to use square brackets

for subscripts, making the compiler's job a bit easier.

But the vagaries of FORTRAN serve us well at this point. Suppose we want

to define a permutation (which is after all, just a function) on 1..3. We

define F as what old FORTRAN programmers called an array with three

elements (more often called a vector these days). Then, we can assign

values to the array elements, such as F(1)=2, F(2)=3, and F(3)=1.

Finally, we can write statements such as Y=F(X), which look and act like

functions, although FORTRAN thinks of them as arrays. (Well, F, X, and Y

would have to be defined as INTEGERS, which is not very FORTRANish, but so

be it).

What about function composition, say G(F(X))? It works, but be careful

what you mean. A very short snippit of code might look something like the

following:

X=1 Y=F(X) Z=G(F(X)) PRINT Y, Z

Function composition works as advertized even though these things are

really arrays. But the composition is calculated only for one particular

value of X, namely X=1. If we want to calculate the full=blown

composition H=GoF (group theory, H=FG), the code snippit would be

H(1)=G(F(1)) H(2)=G(F(2)) H(3)=G(F(3))

As you can see, this programming way of implementing a permutation as an

array is really the second way in which math books define a function,

namely as a set of ordered pairs. For example, the function F from above

is simply F={ (1,2), (2,3), 3,1) }. But the X values were never stored

explicitly. Rather, they were the array indices. We would say that the F

array stores the Y values as a vector. In this case, we would say that

F=[2,3,1].

Notice that it is somewhat arbitrary whether X is represented by the

indices and Y is represented by the vector, or vice versa. The way I have

shown it seems more natural, but the vice versa is certainly tenable.

Notice also that if we think of the vice versa where X is represented by

the vector and Y is represented by the indices, then we have the inverse

function F'. Hence, the same vector can represent both F and F'.

As a practical matter, I really prefer to have indices represent X and to

store the inverse as a separate vector. Let me switch to a more modern

look and feel, using square brackets. The code to calculate an inverse

would then look something like.

F_inverse[F[1]] := 1; F_inverse[F[2]] := 2; F_inverse{F[3]] := 3;

You would really do this with a loop, so it would be something like

For i := 1 to 3 F_inverse[F[i]] := i;

If you translate this loop back into group theory, it more or less states

the identity FF'=I (the looping just makes sure that we touch all our X

values -- the index i is our X value, and the order of F and F' is

backwards between our program and group theory).

The key component of Shamir's method involves multiplying a permutation t

by each permutation s in a set S, where the set S is in lexicographic

order. I want to show what happens with both pre-multiplying and

post-multiplying. In order to deal with representative elements of

M-conjugacy classes, we need both to pre-multiply by m' and to

post-multiply by m, so the issue of pre-multiplying vs. post-multiplying

is critical. I will use permutations on 1..4 in vector notation for my

examples.

t S tS[3,1,4,2] [1,2,3,4] = [3,1,4,2] [3,1,4,2] [1,2,4,3] = [4,1,3,2] [3,1,4,2] [1,3,4,2] = [4,1,2,3] [3,1,4,2] [2,1,3,4] = [3,2,4,1] [3,1,4,2] [3,1,2,4] = [2,3,4,1] [3,1,4,2] [4,3 2,1] = [2,4,1,3]S t St[1,2,3,4] [3,1,4,2] = [3,1,4,2] [1,2,4,3] [3,1,4,2] = [3,1,2,4] [1,3,4,2] [3,1,4,2] = [3,4,2,1] [2,1,3,4] [3,1,4,2] = [1,3,4,2] [3,1,2,4] [3,1,4,2] = [4,3,1,2] [4,3,2,1] [3,1,4,2] = [2,4,1,3]

Let's take the case of St first. This is classic Shamir. S is in

lexicographic order. Going from S to St, every 1 has been replaced by a

3, every 2 has been replaced by a 1, every 3 has been replaced by a 4, and

every 4 has been replaced by a 2.

We can get St into lexicographic order by sorting S in the order 2 first,

4 second, 1 third, and 3 fourth. The vector [2,4,1,3] which controls this

alternative sorting order is simply t'. Hence, we don't really have to

sort St if S is made into a tree. Rather, we traverse the S tree using t'

as a template to define an alternative order of traversal, and St

automagically pops out in lexicographic order.

(By the way, there is a minor error in one of my previous posts. Allen

Bawden used right-to-left notation in his original Shamir article. I

copied what he wrote thinking he was using left-to-right notation. To

properly "copy" what he wrote and also put it in left-to-write notation, I

needed to reverse everything, but I failed to do so. Hopefully,

everything will be consistent and correct in this article.)

The tS case is much trickier. Think of S as a matrix. To get to tS, what

you do is permute the columns. With the particular t we are using, column

3 becomes column 1, column 1 becomes column 2, column 4 becomes column 3,

and column 2 becomes column 4.

I really can't think of any Shamir-like tree traversal that would put tS

into lexicographic order. To see the nature of the problem very clearly,

look at the original S and think of sorting the rows using column 3 as the

major sort. We can't really move the rows around of course, because we

only have one S and we have to sort it differently for each t. Just look

down column 3 and think about sorting without actually moving anything.

Remember that in case of ties, you would then have to look at column 1,

then column 4, etc. It's a mess, and I don't think you can do it without

adding a data structure much larger than what we already have. And the

original point of combining Shamir with M-conjugacy was to save memory.

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us Pellissippi State (423) 539-7127 10915 Hardin Valley Road (423) 694-6435 (fax) P.O. Box 22990 Knoxville, TN 37933-0990