# Message #1846

From: David Vanderschel <DvdS@Austin.RR.com>

Subject: Re: [MC4D] State graph of MC2D

Date: Thu, 04 Aug 2011 17:02:28 -0500

Melinda wrote:

> You looked at my diagram and thought that what I was

> attempting had something to do with cycles and conjugates

> but was just doing it wrong.

Melinda, you are making assumptions about what I was

thinking that are not only false, but are contrary to what I

actually wrote. I hope that, after reading this, you will

apologize for the above inappropriate accusation. I hope

you will read this post carefully, because it appears that

you have failed to do so with my previous posts.

One of the first things I wrote was:

```
As I (fail to) recall, Melinda never made it very clear<br>
about what were her criteria for the particular<br>
partitioning of the 24 permutations she chose for her<br>
"states". I never understood what technical meaning she<br>
was ascribing to "complete" or why she used the definite<br>
article on "the complete graph". There are many ways to<br>
partition the 24 elements of S4. Nan's graphs certainly<br>
would seem to me to be closer to what I would call<br>
"complete" in this context.
```

As you can see, I made it clear that I was trying to

understand how you arrived at your particular partitioning.

I raised the issue of conjugacy classes because I understand

them and they seemed close to your partition. I never said

that what you were doing was "wrong" - just that I did not

understand it. And I wanted to understand it. I finally

did after Andrew Gould’s post.

I was not ignoring the value of your graph either. In that

first post, I had mentioned:

```
Melinda's graph accurately depicts the fact that you<br>
cannot get from any member of either of the last two<br>
states to one of the first 3 with one twist. Similarly<br>
for 0 -> 2. But I cannot turn this observation into a<br>
clue for the partitioning.
```

So I was acknowledging the fact that your graph puts limits

on the minimum number of twists required to solve. I did

understand that, and I would not discount its interest as an

academic issue. And note, in the above, that I was still

harping on the fact that I did not understand the rule for

your partition.

More recently I wrote:

```
What I am trying to get hold of is the relation which<br>
determines the partitioning. I suggested, "...
If it is not clear what I am concerned with, check out<br>
http://en.wikipedia.org/wiki/Partition_of_a_set#Partitions_and_equivalence_relations<br>
or http://preview.tinyurl.com/3u6tzeh<br>
Partitions of a set and equivalence relations on the set<br>
are equivalent concepts. I see the partitioning. I am<br>
trying to figure out a nice way to state the<br>
corresponding equivalence relation. I am also biased to<br>
try to find such a description in terms of the<br>
permutations themselves and not in terms of manipulating<br>
an abstract physical model in 2-space or 3-space. (As<br>
we have already experienced, the latter type of<br>
description is difficult to make precise in a<br>
mathematical sense.)
```

I was concerned that maybe you were still confused about

what I was actually concerned with, so I went into even more

detail. Alas, that apparently still did not help. It

should be very clear that, at no point, did I ever claim

that what you had done was "wrong".

> Different problems indeed. I don’t know the precise

> mathematical language to express my diagram in your terms

> but it looks like you and Nan are doing a good job of

> that.

Actually, no. It was Andrew Gould who straightened this

out, providing a way to specify the equivalence relation

that gives rise to your partition. It is mathematically

sound and elegantly simple. And, as it turns out,

conjugating is the way it’s done. It’s just that you cannot

conjugate with _any_ permutation of S4 - only those that

arise from symmetries. Thus the fact that I started talking

about conjugation early on was not irrelevant, as you seem

to imply. Nan had left me confused by omitting the

possibility of conjugating with a reflection.

Now there certainly is a sense in which I have expressed a

negative attitude about the graph. Indeed, my very first

comment in this thread was:

```
I think maybe a little too much is being made of this<br>
state graph business for the 2D puzzle.
```

There were a couple things I had in mind when I made that

remark:

```
One was that Nan's elaboration of it was not<br>
accomplishing anything that you had not already<br>
accomplished. His treatment struck me as being more an<br>
exploration of S4 than as offering insight into the<br>
puzzle. That is why I went on to make the point that S4<br>
is a rather well understood subject.
The other thing I had in mind is that your graph is not<br>
an effective aid for solving the puzzle. I acknowledge<br>
that it has relevance in an academic sense; but, from<br>
the practical point of view, it is most definitely not<br>
practical. I will stand by that. The puzzle is so very<br>
easy to solve directly, that one can solve it in far<br>
less time than it takes to figure out which node of the<br>
graph a given permutation corresponds to, let alone<br>
figuring out which permutation in the next node on the<br>
solution path is one you can reach from your current<br>
state.
```

For the purpose of actually solving the puzzle, I offered:

```
Whenever any cubie is diagonally displaced, then, to get<br>
a shortest solution, you must immediately do a twist<br>
that moves at least one such diagonally displaced cubie.<br>
For such a diagonally displaced cubie, there are two<br>
slices you can twist. If twisting one of them will<br>
place the other cubie in it, twist that slice. If<br>
twisting one of them will displace the other cubie from<br>
its home position and twisting the other slice won't do<br>
that, twist the other. When no cubie is diagonally<br>
displaced, the solution is obvious.
```

Not only is that much easier to grok than your graph, a few

more lines of reasoning will prove that it always leads to a

solution in 4 or fewer twists. (In constructing that

argument, I see that I failed to mention one (fairly

obvious) rule: If there is a slice in which both cubies are

diagonally displaced, twist that one. That rule comes

before the other which-slice-to-twist rules.) Actually, I

was somewhat embarrassed to be belaboring what seems rather

obvious to me. (My friends and I mastered tic-tac-toe when

we were in the first grade, and that problem strikes me as

being more difficult than solving MC2D.)

But, again, my criticism was not that anything was "wrong".

I was just criticizing the graph’s value from a practical

point of view when it comes to actually working the puzzle.

Now there is one rather odd thing you stated in your last

post that is indeed profoundly wrong:

```
"With my diagram it is trivial to see that God's number<br>
must be 3 ..."
```

What I see is that it takes 4 twists to get from node 2 to

node 0.

One thing that is frustrating me about this diversion is

that I thought I had made a real contribution with the Cycle

Length Signature approach to a succinct but useful way to

classify the permutation state for any sort of cubie in any

generalization these puzzles. That approach is closely

related, as the CLS characterizes the conjugacy class of an

arrangement. The difference is that these conjugates are

not limited to conjugation by a symmetry. As it turns out,

that makes it much easier to identify the CLS class of an

arrangement; and it leads to a state graph with far fewer

nodes, which could be viewed as an advantage. Furthermore,

the insights from the CLS do have real practical

significance which can be readily applied when solving. I

thought folks would be excited about this.

Regards,

David V.