From cube-lovers-errors@oolong.camellia.org Mon Jun 30 15:09:03 1997 Return-Path: cube-lovers-errors@oolong.camellia.org Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id PAA18257; Mon, 30 Jun 1997 15:09:02 -0400 Precedence: bulk Errors-To: cube-lovers-errors@oolong.camellia.org Date: Mon, 30 Jun 1997 14:08:40 -0400 (Eastern Daylight Time) From: Jerry Bryan Subject: Inverses of Local Maxima To: cube-lovers@ai.mit.edu Reply-to: Jerry Bryan Message-id: MIME-version: 1.0 Content-type: TEXT/PLAIN; charset=US-ASCII X-X-Sender: jbryan@PSTCC6.pstcc.cc.tn.us One of the oldest unsolved problems on Cube-Lovers (aside from God's Algorithm itself) has to do with inverses of local maxima. It seems obvious that the inverse of a local maximum also ought to be a local maximum. But is it necessarily so? In Symmetry and Local Maxima, Jim Saxe and Dan Hoey suggest that it may not be. Their example is UFF, which can end with F or F' because we can write it as UF'F'. But the inverse is F'F'U', which can only end with U' Hence, there are very simple positions where the number of q-turns with which the position can end is different than the number of q-turns with with the inverse of the position can end. If the same thing should happen with a local maximum, then the inverse would not be a local maximum. On the other hand, for all known local maxima in G, the inverse is also a local maximum. What are we to think? I have some small progress. I can report that for the corners-only group, there are local maxima for which the inverse is not a local maximum. The results were obtained with my new Shamir program. For each position x, we define E(x) to be the set of all quarter-turns with which a minimal process for the position can end. As an example, if x=UFF, then E(x)={F,F'}. E(x) is a subset of Q, the set of twelve quarter-turns, or equivalently it is an element of P(Q), the power set of Q. As such, it is conveniently represented in my program as a bit-string of twelve bits. In this notation, we would say that a position x is a local maximum if E(x)=Q or if |E(x)|=12. We also define S(x) to be the set of all quarter-turns with which a minimal process for a position can start. In this notation, for x=UFF we would say that |S(x)|=1 and |E(x)|=2. So the general question for local maxima becomes the following: if |E(x)|=12, does it necessarily follow that |S(x)|=12? My program calculates S(x) and E(x) as follows. Any breadth-first search may be characterized as calculating products of the form z=xy for suitable choices of x and y. Most typically, x comes from Q[n], the set of all quarter-turns of length n, and y comes from Q[1], the set of all quarter-turns of length 1. But in my more general Shamir program, x comes from Q[m] and y comes from Q[n] to form products of length m+m. In any case, S(z) is the union of S(x) over all x which can be a part of a product which produces z, and E(z) is the union of E(y) over all y which can be a part of a product which produce z. For each q in Q, we initialize with S(q)=E(q)={q} and go from there. Here is a portion of a printout from my program. |x| |E(x)| |S(x)| M-Conjugacy Positions Classes 0 0 0 1 1 1 1 1 1 12 2 1 1 2 96 2 2 2 3 18 3 1 1 12 576 3 1 2 3 96 3 2 1 3 96 3 2 2 4 96 3 3 3 2 60 As you can see, the effect pointed out by Saxe and Hoey first shows up three moves from Start, where there are six positions unique up to M-conjugacy where |S(x)| is not equal to |E(x)|. (Actually, three of the six positions are just the inverses of the other three.) The first local maxima are six moves from Start in the corners-only group. |x| |E(x)| |S(x)| M-Conjugacy Positions Classes 6 12 12 8 114 As you can see, there are 114 local maxima of which 8 are unique up to M-conjugacy. However, for all 8 of them, the inverse is also a local maximum so we discover nothing new. The new discovery occurs 7 moves from Start. |x| |E(x)| |S(x)| M-Conjugacy Positions Classes 7 12 8 4 120 7 12 10 3 144 7 12 12 14 336 As you can see, there are 21 local maximu unique up to M-conjugacy. For 14 of them, the inverse is also a local maximum. But for the other 7, the inverse is not a local maximum. In 4 cases, we have |S(x)|=8, and in 3 cases we have |S(x)|=10. Here follow summaries for local maximum up to a distance of 11 moves from Start. |x| |E(x)| |S(x)| M-Conjugacy Positions Classes 8 12 6 14 576 8 12 8 12 576 8 12 10 86 4128 8 12 11 13 624 8 12 12 272 12012 9 12 4 26 1152 9 12 6 31 1344 9 12 8 24 1152 9 12 10 14 576 9 12 12 131 5976 10 12 2 14 576 10 12 4 88 4032 10 12 6 218 10368 10 12 8 144 6336 10 12 10 168 8064 10 12 12 140 5664 11 12 4 384 18432 11 12 6 2687 128688 11 12 8 5550 264192 11 12 10 5014 240576 11 12 12 3617 166224 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us Pellissippi State (423) 539-7198 10915 Hardin Valley Road (423) 694-6435 (fax) P.O. Box 22990 Knoxville, TN 37933-0990