Relationship of Duplicate Positions and Non-Trivial Identities

I have finally managed to understand several issues that have seemed to me like possible discrepancies between the numbers associated with my new formula for P[6] and the numbers in the analysis of the 1440 12q identities by mdlazreg.  I still arrive at the exact same final formula as before.  But I find that that better to understand some of the numbers I need to restate some of mdlazreg's results from a slightly different perspective.  To that end, I decided to prepare sort of a total redo of the whole development of the P[6] formula - hopefully stating things a little more clearly than the first time.

An enumeration of Cube space generally speaking must proceed recursively.  All the positions 1 move from Start are found, then all the positions 2 moves from Start, then all the positions 3 moves from Start, etc.  The most typical way to find all the positions that are n moves from Start is to form all the products of the form xq, where x is a position that is n-1 moves from Start and q is a quarter turn.  (For the face turn metric, the products would be of the form xf, where f is a face turn.)

There are two basic problems that must be solved when enumerating cube space in this manner.  One is that xq may be of length n-2 rather than of length n.  (In the face turn metric, xf may be of length n-2 or n-1 rather than of length n.)  So we would like to find some way to enumerate just the products that are of length n.  Secondly, there may be some position x₂ and some quarter turn q₂ with x ≠ x₂ and q ≠ q₂ such that xq=x₂q₂.  This is the so-called duplicate position problem.  The duplicate position problem should probably be called the multiple maneuver problem.  There is really only one position, but there are multiple maneuvers for that one position.

Many years ago, Dan Hoey developed a recursive formula for P[n], the number of positions that are n moves from Start.  Dan's formula partially solves both of the basic problems associated with enumerating Cube space at one fell swoop.  In the quarter turn metric, Dan's formula provides exact values for P[n] for 0≤n≤5, and provides and upper limit for P[n] for n≥6.  So we could say that Dan's formula completely solves both the problems associated with enumerating Cube space out to n=5, and it partially solves the problems thereafter.

Implicit in Dan's formula is a different way to enumerate Cube space.  Rather than using the xq method, he uses what I will call the ps method.  That is, the formula assumes that we form all products of the form ps, where p is a position and s is a syllable, where |p|+|s|=n, and where 0≤|p|≤n-1 and 1≤|s|≤n.  The formula has terms for |p|=n-1 and |s|=1; for |p|=n-2 and |s|=2; and so forth through |p|=0 and |s|=n.  Close to Start, all of Dan's products of the form ps have the characteristics that |ps|=|p|+|s| and that there is only one product per position.

Syllables in Dan's original formula are defined in terms of moves along parallel and orthogonal faces of the Cube.  Two moves are parallel if they are on the same or opposite faces.  Two moves that are not parallel are orthogonal.  A position is a syllable if an optimal sequence of moves for the position consists entirely of parallel moves.  This definition restricts syllables to a maximum length of 4q or 2f.

The original formula fails to be exact in the quarter turn metric for n≥6 because of duplicate positions that it does not take into account, and taking the additional duplicate positions into account for n≥6 has proven to be a very vexing problem for many years.  This message will outline how the formula can be extended to be exact for the n=6 case, and will suggest how the formula could be extended to be exact even further from Start.  Also, the new formula for P[6] may be extended as an inequality for n≥7.  Doing so provides a slightly tighter upper bound for n≥7 than the original formula.

The key element in extending the formula is to develop a definition for a syllable that is more general than the original definition.  The more general definition of a syllable will allow syllables to be of any length that a position can be, and will include the original syllables as a special case.  The intent of this definition is to declare positions that manifest themselves as duplicate positions to be syllables.  However, we wish to count as duplicate positions only those that are duplicate in some non-trivial way.  To that end, a canonical representation will be defined for optimal maneuvers for a position.  A syllable will then be defined as a position that has more than one optimal maneuver, even after the maneuvers have been reduced to a canonical form.

The following algorithm will serve to determine whether a position is a syllable or not, and thereby it will also serve to define whether a maneuver is expressed on canonical form or not.  The algorithm will be looking at position x of length n.  It assumes that all syllables of length 1..n-1 are already known, and it assumes that we have no a priori knowledge about whether x is a syllable or not.  Hence, the algorithm will rediscover Dan's original syllables even though we already know what they are.

1. If |x|=0, declare x to be a non-syllable and stop.  If |x|=1, declare x to be a syllable that is written in canonical form and stop.
2. It is now the case that |x|≥2.  Make a list in quarter turns (or face turns in the face turn metric) of all optimal sequences for x.  Note that this may not be easy to do, but the finiteness of cube space assures that it is possible at least in principle.  At this point in the algorithm, "all sequences" means all sequences, even if some of the optimal sequences differ in what may seem like trivial ways.
3. Group the moves in each optimal sequence into segments of quarter turns in all possible ways, where the segments are of length n-1 or less.  A sequence of n moves can be grouped into segments in 2^n-1-1 possible ways.  For example, the sequence URF can be grouped as (UR)(F), (U)(RF), or as (U)(R)(F).
4. Eliminate any grouping that contains a segment that is not a syllable.  In the case of the sequence URF, the only surviving grouping would be (U)(R)(F) because neither (UR) nor (RF) is a syllable.  In the case of the sequence URL, the surviving groupings would be (U)(RL) and (U)(R)(L) because (UR) is not a syllable.
5. At this point in the algorithm, all surviving groupings consist of syllables rather than just consisting of segments.  Suppose a surviving grouping consists of k syllables.  Because the syllables are of length n-1 or less, it will be the case that k≥2.  If any j adjacent syllables anywhere in the grouping may be joined together to form a larger syllable where j is in 2..k-1, then eliminate the grouping.  Note that if k=2, then there is nothing to test and the grouping will not be eliminated.  In the case of the sequence URL, (U)(R)(L) would be eliminated because (R)(L) may be joined together to form a syllable, and the only surviving grouping would be (U)(RL).
6. At this point in the algorithm, all surviving groupings are optimal maneuvers that are said to consist of fully joined syllables of length n-1 or less.  An optimal maneuver that consists of fully joined syllables of length n-1 or less is said to be in canonical form.  If a position x has only one canonical maneuver, then x is not a syllable and the canonical maneuver can said to be a canonical form for the position x itself.  If a position x has more than one canonical maneuver, then x is a syllable and the canonical form for the position x is the syllable x itself not divided into any shorter syllables.  For example, the maneuvers for the position URL would have been written as both as URL and as ULR, and at this point in the algorithm we would have reduced the possible canonical maneuvers to (U)(RL) and (U)(LR).  But (RL) and (LR) are two different names for the same syllable.  Therefore, the position URL has the unique canonical maneuver (U)(RL) and URL is not a syllable.

With those definitions in mind, a general formula for the number of positions P[n] that are n moves from Start may be written as follows for n≥1.  The initial condition for the recursion is P[0]=1.

     P[n]=sum( a[n,i] * P[n-i] * S[n] ), i=1 to n, where the factors
                                                   are defined
                                                   as follows.

           a[n,i] If i=n, a[n,i]=1.
                  If i<n, a[n,i] is the proportion of the
                  products of the form ps with |p|=n-i and |s|=i such that
                     a. |ps|=n;
                     b. ps is not a syllable and the canonical maneuver
                        for ps ends with the syllable s.
           P[n-i] is the number of positions of length n-i
           S[n]   is the number of syllables of length n

The number of syllables of length n were given by Dan through n=4 as follows, and we can trivially extend his results through n=5.

      Syllables in the
        Quarter Turn
           Metric

         n      S[n]     examples

         0        0
         1       12  the quarter turns
         2       18  RL=LR, RL'=L'R, RR=R'R', etc.
         3       12  RLL=LRL=LLR=RL'L'=L'RL'=L'L'R, etc.
         4        3  RRLL=RLRL=R'R'L'L', etc.
         5        0

For i<n and n≤4, Dan gave a[n,i]=2/3 in all cases.  The reason is that given any quarter turn, 2/3 of the moves that can follow are orthogonal and 1/3 of the moves that can follow are parallel.  When there are parallel moves in succession, the last parallel move in the sequence either leads to a shorter position or leads to a syllable of length greater than the syllable that was already there.  The case of the shorter position must not be counted at all.  When parallel move in succession lead to a syllable of length greater than the syllable that was already there, we must count only canonical moves for the position, which means counting a sequence of parallel moves only once - as a single syllable.

Dan's formula produces the following results for 0≤n≤5.  If you think of the formula as a prediction, the prediction matches the actual values for 0≤n≤5.

                <-- a[n,i] * P[n-i] * S[i] ----->    S[n]        P[n]
                
                  i=4      i=3      i=2      i=1      i=0        

                |p|=4    |p|=3    |p|=2    |p|=1    |p|=0       
                |s|=n-4  |s|=n-3  |s|=n-2  |s|=n-1  |s|=n

 n                   

 0        1                                                        1 
 1                                                     12         12 
 2                                            96       18        114  
 3                                  912      144       12       1068
 4                        8544     1368       96        3      10011
 5               80088   12816      912       24        0      93840

The following is the result when Dan's formula is extended to n=6.

                                 n=6

           <-------- a[n,i] * P[n-i] * S[i] -------->    S[n]        P[n]

             i=5       i=4      i=3      i=2      i=1      i=0

           |p|=5     |p|=4    |p|=3    |p|=2    |p|=1    |p|=0
           |s|=n-5   |s|=n-4  |s|=n-3  |s|=n-2  |s|=n-1  |s|=n


Prediction  750720    120132    8544     228        0       0      879624
Actual      749376    120036    8544     228        0     696      878880

The formula may therefore be adjusted by changing two of the coefficients and by noting that S[6]=696 rather than S[6]=0.  The two coefficients must be adjusted as follows.

      a[6,1] = 2/3    becomes    a[6,1] = (2/3) * (749376/750720)
      a[6,2] = 2/3    becomes    a[6,2] = (2/3) * (120036/120132)

We next need to explain where the numbers 749376, 120036, and 696 come from.  In the case of 749376, the original prediction of 750720 is based on the assumption that 2/3 of the products of the form ps with |p|=5 and |s|=1 result in positions of length 6 that have a unique canonical maneuver.  In the case of 120036, the original prediction of 120132 is based on the assumption that 2/3 of the products of the form ps with |p|=4 and |s|=2 result in positions of length 6 that have a unique canonical maneuver.  Therefore, some of the products in question have multiple canonical maneuvers, and there are precisely 696 positions that have such multiple canonical maneuvers.  These 696 syllables result in the number of products with |p|=5 and |s|=1 with unique canonical forms being reduced by 1344, from 750720 to 749376.  Similarly, these 696 syllables result in the number of products with |p|=4 and |s|=2 with unique canonical forms being reduced by 96, from 120132 to 120036.

The total net reduction in products that have unique canonical maneuvers is 1440.  It might seem that the net increase in syllables ought to be half of 1440, or 720.  However, some of the 696 syllables have two canonical maneuvers and some of the 696 syllables have four canonical maneuvers.  The following analysis of the products with more than one canonical maneuver follows roughly the analysis by mdlazreg (see http://cubezzz.homelinux.org/drupal/?q=node/view/114).

There are 1440 non-trivial identities of length 6q.  The 1440 figure is based on the non-trivial identities not being reduced by symmetry, but the non-trivial identities are all reduced into a canonical form.  The half way position of the identities may be taken to be a duplicate position.  To that end, we write an identity as xy' with x=y and y'x also being an identity, where x and y are canonical maneuvers for the duplicate position.  Therefore, each duplicate position corresponds to two identities and vice versa.

However, there are cases where there are four canonical maneuvers for the same position.  In such a case, we have distinct canonical maneuvers w, x, y, and z such that w=x=y=z.  In such a case, there should be twelve different identities for the duplicate position and vice versa.  But as we shall see, there are only ten identities associated with a 6q duplicate position that has four distinct canonical maneuvers.  The apparent discrepancy is related to the fact that the identities are reduced to a canonical form.  And for the same reason, there are some 6q duplicate positions with two canonical maneuvers that do not correspond to any canonical 12q identity.  Our analysis must take these complications into account.

The following table will help to guide our analysis.

      Class            Canonical     Canonical     Duplicate
        of             Identities    Maneuvers     Positions
      Maneuver                                     or Syllables

        D                 864          864            432
        Z                 144          288            144
       B/C                192          192             96
        E                 240           96             24

      Total              1440         1440            696

I believe it's a bit of an accident that the number of canonical identities equals the number of canonical maneuvers for 12q identities and 6q maneuvers.  As will be described below, there can be canonical maneuvers that do not appear as a part of a canonical identity, and the same canonical maneuver can appear multiple times as a part of a canonical identity.  I cannot think of any reason in general why these two effects should always cancel each other out exactly.

A class B maneuver is of the form ps with |p|=4 and |s|=2 and a class C maneuver is of the form ps with |p|=5 and |s|=1 such that every class B maneuver x has a companion class C maneuver y where x=y, and xy' and y'x are non-trivial identities of length 12q.  A class B maneuver may be exemplified by U R U' B' R R and the companion class C maneuver by R R B' D' R D.  These identities have the effect of reducing the a[6,1] coefficient by 96 for the class C maneuvers, of reducing the a[6,2] coefficient by 96 for the class B maneuvers and of increasing the number of 6q syllables by 96.

We really should speak of class E maneuvers as being either of class E1 or class E2.  A class E maneuver is of the form ps with |p|=5 and |s|=1.  A class E maneuver may be exemplified by w = U' R U R' F' U, x = U F' L' U L U', y = F R' F' R U F', and z = F' U L F' L' F, with w=x=y=z.  Let's say that those four maneuvers are of type E1.  These four maneuvers correspond to twelve identities.  We need to make special note of wx', xw', yz', and zy'.  For example, consider wx'=U' R U R' F' U U L' U' L F U'.  We make think of wx' as being written in canonical form with a middle syllable of (UU), vis. U' R U R' F' (UU) L' U' L F U'.  The middle syllable may also be written as (U'U') which yields the non-canonical form for wx' of U' R U R' F' U' U' L' U' L F U', which in turn leads to a class E2 maneuver w₂=U' R U R' F' U'.  w₂ is a part of a group of four E2 maneuvers w₂=x₂=y₂=z₂.  This group of four E2 maneuvers also corresponds to 12 identities, but only 8 of the 12 identities are canonical.  Each group of four E1 maneuvers may be paired in this manner with one group of four E2 maneuvers, with the paired E1/E2 groups of eight maneuvers corresponding to 20=12+8 identities.  This is because a group of four E1 maneuvers and the group of E2 maneuvers with which it is paired with yield some of the same identities, with the E1 version of the duplicate identities in canonical form and the E2 version in non-canonical form.  Working the problem in the other direction, the 240=20*12 group E identities correspond to 96=8*12 group E maneuvers and 24 group E syllables.  The class E identities have the effect of reducing the a[6,1] coefficient by 96, and of increasing the number of 6q syllables by 24.

A class Z maneuver is of the form ps with |p|=5 and |s|=1.  A class Z maneuver may be exemplified by x = U R U R' F' U and y = U' F' L' U' L' U', with xy' = U R U R' F' U U L' U' L F U .  The class Z identities are like the class E identities in that there is a middle syllable that can be written, for example, as (UU) or as (U'U').  Only one of the two ways appears in the list of canonical identities, but the non-canonical form of the identity yields a different duplicate position.  There are 144 class Z identities in canonical form  Because there are another 144 class identities that are not in canonical form and not in the list of 1440 canonical identities, there are 288 class Z identities in all that yield 288 canonical maneuvers and 144 syllables.  The class Z identities have the effect of reducing the a[6,1] coefficient by 288, and of increasing the number of 6q syllables by 144.

A class D maneuver is of the form ps with |p|=5 and |s|=1.  A class D maneuver may be exemplified by x = U R U U B L and y = R B U U L U, with xy' = U R U U B L U' L' U U B' R'.  The class D identities do not have any funny business about a middle syllable, so their analysis is straightforward.  There are 864 class D identities of length 12q corresponding to 864 canonical class D maneuvers of length 6q corresponding to 432 class D syllables of length 6q.  The class D identities have the effect of reducing the a[6,1] coefficient by 864, and of increasing the number of 6q syllables by 432.

The following summarizes these adjustments in tabular form.

                                 n=6

           <-------- a[n,i] * P[n-i] * S[i] -------->    S[n]        P[n]

             i=5       i=4      i=3      i=2      i=1      i=0

           |p|=5     |p|=4    |p|=3    |p|=2    |p|=1    |p|=0
           |s|=n-5   |s|=n-4  |s|=n-3  |s|=n-2  |s|=n-1  |s|=n

Prediction  750720    120132    8544     228        0       0      879624

B/C            -96       -96                              +96         -96
E              -96                                        +24         -72
D             -864                                       +432        -432
Z             -288                                       +144        -144
Total Adjust -1344       -96                             +696        -744

Actual      749376    120036    8544     228        0     696      878880

Dan's original formula worked both as an equation and as an inequality, depending on the exact context in which it was applied.  In particular, the formula provides exact values for P[n] through n=5, and provides an upper bound for P[n] for n≥6.  The upper bound is extremely tight until n is fairly far from Start.  I want to finish by revisiting why the formula works both as an equation and as an inequality, and then by explaining why the newer version of the formula has the same characteristics.

The "formula" is really a series of formulas.  The P[0] formula stands alone.  Subsequently, there is a P[n] formula that is exact for n=1 and that is an upper bound for n≥2; there is a P[n] formula that is exact for n=2 and that is an upper bound for n≥3; etc.  Let's consider the P[n] formula for n=3 and n=4.

   P[n] = (2/3)*P[3-1]*S[1] + (2/3)*P[3-2]*S[2] +     1*P[3-3]*S[3], n=3
   P[n] ≤ (2/3)*P[n-1]*S[1] + (2/3)*P[n-2]*S[2] +     1*P[n-3]*S[3], n≥4

The equation form of the formula has the following characteristics for the rightmost term.  The coefficient is always 1 and the P[n-i] factor is always P[0], which is also equal to 1.  So the right most term can be reduced simply to S[n], which is the number of syllables of length n.  For the inequality form of the formula, the rightmost term cannot be simplified.  But if we add another term by increasing n, then any coefficient that is not the rightmost coefficient must be changed from 1 to (2/3).

To illustrate what happens, let's take the inequality form of the formula for n≥4 and apply it to the case of n=5.  Let's also take the equality form for the formula for n=5, and compare the two results.  The two results will be compared numerically rather than as formulas.

       Total    |p|=4    |p|=3    |p|=2    |p|=1    |p|=0
                |s|=1    |s|=2    |s|=3    |s|=4    |s|=5

P[5] ≤ 94272    80088    12816     1368        -        -
P[5] = 93840    80088    12816      912       24        0

In effect, we have created the situation that would happen if we applied the formula without knowing how many syllables there were of length 4.  There would be 1368 products of the form ps with |s|=3.  But many of these products shouldn't be counted because they are duplicate positions.  And they are duplicate positions because a product with |s|=3 should have been counted only as a product with |s|=4, if only we had known how many syllables of length 4 there were.  But since we do actually know how many syllables of length 4 there are, we can make the appropriate adjustments.  A way to think of it is that the |s|=3 term needs to be adjusted down, and the |s|=4 and |s|=5 terms need to be adjusted up.  (In this case, the adjustment for the |s|=5 is zero because there are no syllables of length 5.)  Because the downward adjustment is always more than 1 for each duplicate position and the upward adjustment is always exactly 1 for each duplicate position, the net adjustment must always be down.  Therefore, the inequality form of the formula is indeed an upper limit.  This is true both with Dan's original version of the formula and for my new version of the formula for P[6].  For completeness, we write the final forms of the P[6] formula as follows.

P[6] = (2/3)*(749376/750720)*P[5]*12 + (2/3)*(120036/120132)*P[4]*18 + (2/3)*P[3]*12 +
       (2/3)*P[2]*3  + (2/3)*P[1]*0 + 696

P[n] ≤ a[n,1]*P[n-1]*S[1] + a[n,2]*P[n-2]*S[2] + a[n,3]*P[n-3]*S[3] +
       a[n,4]*P[n-4]*S[4] + a[n,5]*P[n-5]*S[5] + a[n,6]*P[n-6]*S[6], n≥7

       S[1]=12, S[2]=18, S[3]=12, S[4]=3, S[5]=0, S[6]=696

       a[n,1]=(2/3)*(749376/750720), a[n,2]=(2/3)*(120036/120132),
       a[n,3]=(2/3), a[n,4]=(2/3), a[n,5]=(2/3), a[n,6]=1

Here's another odd thing. I took Herbert Kociemba's list of 32 12q identities that were reduced by symmetry and antisymmetry, and loaded the halfway point of each of them into Cube Explorer.  I also took mdlazreg's list of 1440 12q identities that were not reduced by symmetry and antisymmetry and loaded the halfway point of each of them into Cube Explorer.  In both cases, I used the Cube Explorer option Skip Isomorphics when Loading from File.

Because I was reducing the lists by symmetry, I expected to get the same result in Cube Explorer whether I was loading the 32 positions or the 1440 positions.  But I didn't.  The 32 positions became reduced to 14 positions.  The 1440 positions became reduced to 15 positions.  The extra or 15th position is U' R' U' R B U, and it's kind of interesting.  It's the only position in the group that fixes one of the cube's faces, so it's visually striking.

I've been trying to figure out why there is a difference, and I'm not sure why.  Aside from the possibility of an error, it would have to be something like the following.  Herbert's list of 32 identities is reduced by symmetry and antisymmetry.  He couldn't really be reducing the identity position by symmetry and antisymmetry because to do so he would just get the identity position back again.  Rather, he would have to be reducing the processes themselves.  Then when I was loading the halfway positions into Cube Explorer and reduced them by symmetry, I was reducing the positions by symmetry.  Reducing halfway positions by symmetry and reducing the processes for the identities by symmetry and antisymmetry is not exactly the same thing - close, but not exactly the same.  And by the way, I also tried reducing by both symmetry and antisymmetry when I loaded the halfway positions into Cube Explore.  Doing it that way, the list of 1440 positions was reduced to 14, and the list of 32 positions was reduced to 13.