Home »

A Possible Approach to Generalize Dan Hoey's Syllables

Submitted by Jerry Bryan on Sat, 12/20/2008 - 11:39.

The thread on this forum entitled "Non Trivial Identities" has had the most responses of any thread to date (39 responses so far).  The thread contains a great deal of useful information, including a detailed analysis of non-trivial identities of length 12q.  The thread may be found at http://cubezzz.homelinux.org/drupal/?q=node/view/114 (you have to login to see all the responses).

I tend to view the problem of analyzing identities more in terms of duplicate positions than in terms of identities, but you can of course easily transition from one view of the problem to the other.  In any case, the problem of finding a formula for the number of moves at each distance from Start is closely tied to the problem of finding duplicate positions and/or non-trivial identities.

At this time I don't have a new formula to offer up concerning the number of moves at each distance from Start.  The best available formula remains Dan Hoey's original formula from 1981:
http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Dan_Hoey__The_Supergroup_--_Part_2__At_least_25_qtw,_and_why.html
But I did want to offer up some ideas about how such an improved formula might be developed. 

For an optimal sequence of moves, Dan defined a syllable as a sub-sequence of moves on parallel faces, F and B, R and L, or U and D.  Implicit in Dan's formula is that any syllable must be followed by a syllable from an orthogonal face.  For example, it is implicit that the syllable F cannot be followed by the syllable B because instead the sequence (FB) would be considered to be the syllable.  Dan's original posting concerned the quarter turn metric, but the concept of syllables applies equally well to the face turn metric.

Typical enumerations of Cube space are breadth first enumerations, going from distance n to distance n+1 in an iterative fashion.  Dan's formula works a little differently.  The formula begins conventionally.  If P[n] is the number of moves that are n moves from Start, then P[0] and P[1] are trivially calculated as P[0]=1 (the Start position itself) and P[1]=12*P[0]=12 (the 12 quarter turns).  But P[2] in Dan's formula is not calculated from P[1].  Rather, P[2] is calculated from both P[0] and P[1].  So for example, rather than going from the position I to the position R to the position RL in two steps, Dan's formula requires that you go from the position I to the position (RL) all in one step.

Similar, Dan's formula requires you to go from the position I to the position F to the position FR in two steps because FR is not a syllable. Indeed, F can be followed by any of the 8 orthogonal moves: (F)(R), (F)(R'), (F)(L), (F)(L'), (F)(U), (F)(U'), (F)(D), and (F)(D'), and these 8 moves are accounted for in Dan's formula.  But the formula does not allow F to be followed by B to yield (F)(B).  Rather, the formula allows I (the Start position) to be followed by the syllable FB to yield (FB), going from a distance of 0 from Start to a distance of 2 from Start all in one go.  Which is to say, it is legal under Dan's formula to have two successive parallel moves, but it is not legal under Dan's formula to have two successive parallel syllables.  So we go from a distance of 1 to a distance of 2 in some cases, and from a distance of 0 to a distance of 2 in other cases.  Further from Start, quarter turn syllables may consist of 1, 2, 3, or 4 quarter turns.  Similarly, face turn syllables may consist of 1 or 2 face turns.  So the calculation of P[5] in the quarter turn metric involves going directly from a distance of 1 to a distance of 5 in some cases, going directly from a distance of 2 to a distance of 5 in some cases, going directly from a distance of 3 to a distance of 5 in some cases, and going from a distance of 4 to a distance of 5 in all the other cases.

Dan's formula is making note of the fact that successive moves on parallel faces commute.  For example, the syllable (FB) and the syllable (BF) are the same syllable.  The formula is also making note of trivial identities.  For example, FFFF=I, so that FF=(FF)'=(F'F'), and therefore (FF) and (F'F') are the same syllable.

My idea is that rather than thinking about syllables in terms of moves that commute or in terms of identities, we think about syllables in terms of duplicate positions - that is, in terms of different optimal sequences that yield the same position.  For example, we make note of the fact that FB=BF and that FF=F'F' without regard to why.  And we discover these duplicate positions via search rather than by any sort of analysis.  The approach I'm suggesting is much less elegant than Dan's, but it might offer the possibility of improving the formula to yield tighter bounds further from Start.

In thinking about syllables in terms of duplicate positions, we maintain Dan's notion of writing optimal sequences in terms of syllables rather than in terms of moves.  And we also maintain Dan's notion of combining together adjacent syllables when combining the syllables will yield a longer syllable.  A decomposition of an optimal sequence into syllables will be said to consist of fully joined syllables when all the adjacent syllables that can be joined together have been joined together.  The "joining" process itself may not be unique.  But a sequence of joined syllables is not fully joined if any additional joining may be accomplished.

The tricky part of using duplicate positions to define syllables is the following.  One the one hand, URL and ULR are duplicate positions, but we don't want to treat URL=ULR as a syllable.  On the other hand. RRL and RLR are duplicate positions, and we do want to treat RRL=RLR as a syllable.  So we need a syllable definition that somehow or other is able to make a distinction between the URL=ULR case and the RRL=RLR case.

The main idea is the following: The Start position is not a syllable.  A position that has exactly one decomposition into shorter fully joined syllables is not a syllable.  All other positions are syllables.

This approach still does not give us a better formula (at least not yet!).  But it does provide a syllable definition that depends totally on duplicate positions, rather than on moves of parallel faces.  It provides a syllable definition that matches Dan's definition for distances from Start of 1q through 5q.  And for 6q from Start, it provides a syllable that matches the analysis of 12q identities in the "Non Trivial Identities" thread (the 6q syllables are the halfway positions of the 12q identities).

My proposed definition of a syllable is recursive.  Let's see how it works for a few distances close to Start.

  • n=0.  The Start position is not a syllable.
  • n=1.  The quarter turns have no decompositions into shorter fully joined syllables, so they are syllables.
  • n=2.  (These examples exhaust all the ways in which optimal sequences of length 2q may be formed.)
    • Sequences of the form RL and RL' have two decompositions into shorter fully joined syllables (e.g., RL=(R)(L)=(L)(R) and RL'=(R)(L')=(L')(R) ), so they are syllables.
    • Sequences of the form RR have two decompositions into shorter fully joined syllables (e.g., RR=(R)(R)=(R')(R') ), so they are syllables.
    • Sequences of the form RU and RU' have one decomposition into shorter fully joined syllables (e.g., RU=(R)(U) and RU'=(R)(U') ), so they are not syllables.
  • n=3.  (These examples do not exhaust all the ways in which optimal sequences of length 3q may be formed, but they are illustrative nonetheless.)
    • Sequences of the form FRU have one decomposition into shorter fully joined syllables (e.g., FRU=(F)(R)(U) ), so they are not syllables.
    • Sequences of the form FRL=FLR have one decomposition into shorter fully joined syllables (e.g., FRL=FLR=(F)(RL) ), so they are not syllables.
    • Sequences of the form RRL=RLR=LRR=R'R'L=R'LR'=LR'R' have numerous decompositions into shorter fully joined syllables (e.g., (R)(RL), (RR)(L), (RL)(R), etc. ), so they are syllables.  It might appear "obvious" that sequences such as (R)(RL) can and should be combined together to form the longer syllable (RRL) without first checking to see if (RRL) can be decomposed into shorter fully joined syllables.  That is, RRL clearly complies with the Hoey definition of a syllable.  But remember that the more general definition of syllable is recursive, and that in the case of syllables of length 3q we are defining them in terms of syllables of length 1q and 2q.  So we can't declare (RRL) to be a syllable until we have found at least two different ways to decompose it into fully joined syllables each of which is less than 3q in length.

Finally, let's look at syllables of length 6q just a little bit.  In the "Non Trivial Identities" thread, Herbert Kociemba posted 32 non-trivial identities of length 12q that are unique up to symmetry.  The first one is
 
U U R U R' F' U U L' U' L F (12q*)
 
We may write this as xy'=UURUR'F'UUL'U'LF where x=UURUR'F' and y'=UUL'U'LF, so that y=F'L'ULU'U'.  Because xy'=I, we have x=y which manifests as duplicate positions when enumerating cube space.  Written as fully joined syllables, we have x=(UU)(R)(U)(R')(F') and y=(F')(L')(U)(L)(UU).  Hence, x=y has more than one decomposition into shorter fully joined syllables, and therefore x=y is a syllable of length 6q.  We note in passing that StartsWith(x)={U,U',F'} and EndsWith(x)={U,U',F'}.

I haven't verified all 32 of Herbert's non-trivial identities of length 12q, but I'm sure that for each one of them the halfway position corresponds to a syllable.  Indeed, I would argue that if one of them didn't correspond to a syllable, then the 12q identity wasn't really non-trivial and could be trivially changed to a shorter identity.

For example, suppose instead of 12q identities we were enumerating 6q identities, and we claimed that URLR'L'U' were a non-trivial identity.  The obvious counter-argument is that all the moves in the subsequence RLR'L' commute and can therefore be rewritten as the trivial identity RLL'R'.  The syllable counter-argument as applied to the 6q identity would suggest writing the identity as (U)(RL)(R'L')(U') and would note that the syllables (RL) and (R'L') are inverses.  The syllable counter-argument as applied to duplicate positions would suggest rewriting the identity as xy' with x=(U)(RL) and y=(U)(LR) and would note that (RL) and (LR) are the same syllable so that x=y only has one decomposition into shorter fully joined syllables.

Here's a question for Herbert.  When you were calculating your 32 non-trivial identities of length 12q unique up to symmetry, what was your criterion for verifying that all of them were non-trivial (i.e., that they couldn't be shortened)?

» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

Some Syllable Theorems

Submitted by Jerry Bryan on Fri, 12/26/2008 - 16:01.

By my new definition of a syllable, a syllable in the quarter turn metric is either a quarter turn itself or else is a position that has more than one decomposition into shorter fully joined syllables.

Proposition.  Let M be the group of 48 symmetries of the cube.  The M-conjugate of a syllable is a syllable.

Proof.  I think this one is obvious.

Proposition.  The inverse of a syllable is a syllable.

Proof.  I think this one is almost as obvious as the previous one.  I will simply make note of the fact that if an optimal sequence for position x is written as shorter fully joined syllables, then an optimal sequence for x' may be written by reversing the order of the syllables and taking the inverse of each syllable.

Proposition.  Let x be any syllable with |x| ≥ 2q, and let the following be any two distinct decompositions of x into shorter fully joined syllables: s=s1s2...sm and t=t1t2...tn, where the si and the tj are fully joined syllables that are each shorter than |x|.  Then, sm ≠ tn.  More informally, two distinct decompositions of a syllable into shorter fully joined syllables must end with different shorter syllables.   This is the principle result in this note.

Proof.  Suppose the syllables sm and tn are equal.  Then, the positions s1,s2...sm-1 and t1,t2...tn-1 are equal.  That means that the position s1,s2...sm-1 = t1,t2...tn-1 is a syllable, call it v.  We may therefore decompose the position s=t into shorter fully joined syllables as s=vsm and t=vsm so that s and t are not distinct decompositions.  Therefore, sm ≠ tn.

Corollary.  Let x be any syllable with |x| ≥ 2q.  Then |EndsWith(x)| ≥ 2q and |StartsWith(x)| ≥ 2q.

Proof.  Suppose |EndsWith(x)| = 1q, and in particular that EndsWith(x) = {q}.  Because x is a syllable with |x| ≥ 2q, there must be at least two distinct decompositions of x into shorter fully joined syllables, say s=s1s2...sm and t=t1t2...tn.  Because sm ≠ tn, either sm or tn must be a syllable other than (q).  So suppose sm is a syllable other than (q).  Because EndsWith(x) = {q}, it must be the case that EndsWith(sm)={q}.  Because sm is a syllable other than q itself and because EndsWith(sm)={q}, it must be the case that |sm| ≥ 2q.  Applying the same argument to sm that we just applied to x then yields an infinite regress.  Therefore, the assumption that |EndsWith(x)| = 1q is false, and |EndsWith(x)| ≥ 2q.  That |StartsWith(x)| ≥ 2q then follows immediately from the fact that the inverse of a syllable is a syllable.

Corollary.  Let x be any position with |x| ≥ 2q and either |EndsWith(x)| = 1q or |StartsWith(x)| = 1q.  Then x is not a syllable.

Corollary.  Let x be any position with |x| ≥ 2q.  Consider the set of all decompositions of x into shorter fully joined syllables.  If each such decomposition Starts with the same shorter syllable or each such decomposition Ends with the same shorter syllable, then x is not a syllable.

Corollary.  Let x be any syllable with |x| ≥ 2q.  and consider the set of all decompositions of x into shorter fully joined syllables.  Then there are at least two shorter syllables with which x can Start and at least two shorter syllables with which x can End.

(NB: In the "Non Trivial Identities" thread, Herbert Kociemba listed 32 non-trivial identities of length 12q and mdlazreg listed 1440 non-trivial identities of length 12q.  The two lists are essentially identical except that Herbert's list was reduced by symmetry and anti-symmetry and mdlazreg's list was not.  mdlazreg gave an excellent analysis of the 1440 identities, and he spoke of StartsWith and EndsWith values for the halfway positions associated with the 1440 identities.  For example, he gave StartsWith=2 and EndsWith=1 for UURUR'F'.  But UURUR'F' is a syllable, so his results seem so be a counter-example to my results above.  But he also gave StartsWith=1 and EndsWith=2 for F'L'ULUU.  Also, he noted that UURUR'F'=F'L'ULUU and therefore he noted that when the two sequences are combined the results are StartsWith=3 and EndsWith=3.  My usage of StartsWith and EndsWith corresponds to the StartsWith=3 and EndsWith=3 case, which is to say I apply the functions to a position rather than to optimal processes that produce the position.  So there is no real contradiction.  It remains the case that if x is a position of length 2q or greater and if |StartsWith(x)| = 1q or |EndsWith(x)|=1q, then x is not a syllable.)

» login or register to post comments

A New Formula

Submitted by Jerry Bryan on Sun, 01/04/2009 - 20:09.

The following table gives the number of syllables of length n quarter turns for n from 0 through 6.  For n=1..4, the numbers are straight from Dan Hoey's syllable analysis.  For n=5, the fact that the number of syllables is 0 may be inferred by the fact that Dan's formula for the number of positions is correct using only syllables of length 1..4.  For n=6, the number of syllables is based on the analysis of non-trivial identities by Herbert Kociemba and mdlazreg. 

   n      Number of      Number of            Total
quarter    Syllables     Non-syllables      Positions
 turns

   0           0                1                 1
   1          12                0                12
   2          18               96               114
   3          12             1056              1068
   4           3            10008             10011
   5           0            93840             93840
   6         696           878184            878880
 

The number 696 probably requires a bit of justification as follows because it does not appear explicitly in mdlazreg's analysis.  

       Length      |EndsWith(x)|  Syllables   Duplicate      Non-Trivial
         of                                   Positions       Identities
       Syllable                                  per
                                              Syllable

          6q              4           24          4              96
          6q              3           96          2             192
          6q              2          576          2            1152
                                     ---                       ----
        Total                        696                       1440
 

And of course, 1440-696=744, so the 696 syllables yield a reduction of 744 in the number of positions at 6q from Start.  744 is the number that appears in mdlazreg's analysis.  For a new formula, I need the number of syllables rather than the amount of reduction.

Let's now look at Dan Hoey's original formula in some detail. 

   P[0]   = 1
   P[1]  <= 4*3*P[0]
   P[2]  <= 4*2*P[1]   + 6*3*P[0]
   P[3]  <= 4*2*P[2]   + 6*2*P[1]   + 4*3*P[0]
   P[4]  <= 4*2*P[3]   + 6*2*P[2]   + 4*2*P[1]   + 1*3*P[0]
   P[n]  <= 4*2*P[n-1] + 6*2*P[n-2] + 4*2*P[n-3] + 1*2*P[n-4]
						for n > 4.
 

Note that for P[1], P[2], P[3], and P[4], the inequality can be written as a strict equality, if we so choose.  Or, we can rewrite the inequalities as follows. 

   P[n]   = 4*3*P[n-1], n = 1
   P[n]  <= 4*3*P[n-1], n > 1

   P[n]   = 4*2*P[n-1] + 6*3*P[n-2], n = 2
   P[n]  <= 4*2*P[n-1] + 6*3*P[n-2], n > 2

   P[n]   = 4*2*P[n-1] + 6*2*P[n-2] + 4*3*P[n-3], n = 3
   P[n]  <= 4*2*P[n-1] + 6*2*P[n-2] + 4*3*P[n-3], n > 3

   P[n]   = 4*2*P[n-1] + 6*2*P[n-2] + 4*2*P[n-3] + 1*3*P[n-4], n = 4
   P[n]  <= 4*2*P[n-1] + 6*2*P[n-2] + 4*2*P[n-3] + 1*2*P[n-4], n > 4
 

A way to think about this result is that Dan's formula is actually a series of formulas, each one providing slightly tighter bounds on P[n] for successively larger values of n.  For example, P[n] <= 4*3*P[n-1], n>1 is not a very tight bound.  It's just saying that the number of positions at a distance of n cannot be more than 12 times more than the number of positions at distance n-1 in the quarter turn metric.  We can do much better than that, but the formula is indeed a "correct" bound even if it's not very useful.

Next, we observe that the coefficient of the P[0] term in each formula is simply the number of syllables of length n.  If we write the number of syllables of length n as sn, we get the following. 

   P[n]   = s1*P[0],   n = 1
   P[n]  <= s1*P[n-1], n > 1

   P[n]   = 4*2*P[1]   + s2*P[0],   n = 2
   P[n]  <= 4*2*P[n-1] + s2*P[n-2], n > 2

   P[n]   = 4*2*P[2]   + 6*2*P[1]   + s3*P[0], n = 3
   P[n]  <= 4*2*P[n-1] + 6*2*P[n-2] + s3*P[n-3], n > 3

   P[n]   = 4*2*P[3]   + 6*2*P[2]   + 4*2*P[1]   + s4*P[0],         n = 4
   P[n]  <= 4*2*P[n-1] + 6*2*P[n-2] + 4*2*P[n-3] + s4*(2/3)*P[n-4], n > 4
 

Now let's look at one piece of Dan's formula in even greater detail. 

   P[1]  <= 4*3*P[0]
   P[2]  <= 4*2*P[1] + 6*3*P[0]
 

For the P[1] formula, the 4 means that there are 4 quarter turns parallel to any particular axis, and the 3 means that there are 3 axes.  My version of the formula rewrites this as 12*P[0], or s1*P[0] if you prefer.  For the P[1] term of the P[2] formula, the 4 means that there are 4 quarter turns parallel to any particular axis, and the 2 means that there are only 2 axes that can now be used.  That's because the formula (for example) doesn't allow the syllable (R) to be followed by the syllable (L).  Rather, the maneuver RL must be accomplished all at one go as the syllable (RL).  So I would render the P[2] formula as 

    P[2]  <= 12*( (2/3)*P[1] ) + 18*P[0]

                 or

    P[2]  <= s1*( (2/3)*P[1] ) + s2*P[0]
 

We may think of 2/3 as a fudge factor to account for the fact that each of the 12 syllables of length 1q may follow only 2/3 of the positions of length 1q.  Dan came up with the 2/3 based on the 3 axes of the cube and based on parallel and orthogonal moves.  More generally, we might say that we may not write two syllables consecutively if the two syllables can be joined together into a longer syllable.  This more general rule about consecutive syllables is in accord with my more general definition of a syllable.

We now rewrite all of Dan's formulas in terms of syllables and fudge factors, and extend the table to P[5].  Remember that s5=0 so that the s5 term is being included only for completeness and consistency, and no fudge factor is required for s5. 

   P[n]   = s1*P[0],   n = 1
   P[n]  <= s1*P[n-1], n > 1

   P[n]   = s1*(2/3)*P[1]   + s2*P[0],   n = 2
   P[n]  <= s1*(2/3)*P[n-1] + s2*P[n-2], n > 2

   P[n]   = s1*(2/3)*P[2]   + s2*(2/3)*P[1]   + s3*P[0],   n = 3
   P[n]  <= s1*(2/3)*P[n-1] + s2*(2/3)*P[n-2] + s3*P[n-3], n > 3

   P[n]   = s1*(2/3)*P[3]   + s2*(2/3)*P[2]   + s3*(2/3)*P[1]   + s4*P[0],   n = 4
   P[n]  <= s1*(2/3)*P[n-1] + s2*(2/3)*P[n-2] + s3*(2/3)*P[n-3] + s4*P[n-4], n > 4

   P[n]   = s1*(2/3)*P[4]   + s2*(2/3)*P[3]   + s3*(2/3)*P[2]   + s4*(2/3)*P[1]   + s5*P[0],   n = 5
   P[n]  <= s1*(2/3)*P[n-1] + s2*(2/3)*P[n-2] + s3*(2/3)*P[n-3] + s4*(2/3)*P[n-4] + s5*P[n-5], n > 5
 

The above table suggests the following formula for n >= 6, remembering that s6 is 696. 

   P[n]   = s1*(2/3)*P[5]   + s2*(2/3)*P[4]   + s3*(2/3)*P[3]   + s4*(2/3)*P[2]   + s5*P[1]   + s6*P[0],   n = 6
   P[n]  <= s1*(2/3)*P[n-1] + s2*(2/3)*P[n-2] + s3*(2/3)*P[n-3] + s4*(2/3)*P[n-4] + s5*P[n-5] + s6*P[n-6], n > 6
 

But for the n=6 case, this formula is not correct at all.  It's even worse than Dan's formula.  And for the n>6 case, the formula is "correct", but it's a looser bound than Dan's formula.  Because we have found new syllables, the fudge factors are no longer correct.  What we need are new fudge factors to take into account the fact that some of our syllables of lengths 1..4 may be combined together to form syllables of length 6, and we shouldn't count such combinations more than once.  So the final and hopefully correct formula is as follows. 

   P[n]   = s1*(2/3)*(749376/750720)*P[5]   + s2*(2/3)*(120036/120132)*P[4]   + s3*(2/3)*P[3]   + s4*(2/3)*P[2]   + s5*P[1]   + s6*P[0],   n = 6
   P[n]  <= s1*(2/3)*(749376/750720)*P[n-1] + s2*(2/3)*(120036/120132)*P[n-2] + s3*(2/3)*P[n-3] + s4*(2/3)*P[n-4] + s5*P[n-5] + s6*P[n-6], n > 6
 

Those strange looking fudge factors actually come directly out of mdlazreg's analysis.  Notice that 750720-749376 is 1344 and that 120132-120036 is 96.  One of mdlazreg's formulas was 1440=1248+96+96 which we may write as 1440=1344+96.  I think the best way to see what's going on might be the following table.  Here, "predicted" means "predicted from Dan's original formula". Note that rather than saying that we get a decrease of 744 between predicated and actual, I think it makes a little more sense to say that there is a decrease of 1440 and an increase of 696, for a net decrease of 744.  The table makes this point very clear. 


                                       Positions 6q from Start

|EndsWith(x)|     Predicted         Actual     Difference    Predicted   Actual     Actual
                Non-syllables  Non-syllables    for        Syllables   Syllables    Totals
                                             Non-Syllables

      4              228            228            0            0           24          252
      3             8544           8544            0            0           96         8640
      2           120132         120036           96            0          576       120612
      1           750720         749376         1344            0            0       749376
                  ------         ------         ----          ---          ---       ------
   Total          879624         878184         1440            0          696       878880
 

I would probably prefer going back more to Dan's original formulation and write my new formula as follows, noting that strict equality holds only for n=6.  This is the principle result of this note.  We can note that the ratio 749376/750720 can be reduced to 3903/3910, or about 99.8%.  Similarly, 120036/120132 can be reduced to 10003/10011, or about 99.9%.  But to reduce the ratios in this manner obscures the derivation of the numbers. 

   P[n]  <= s1*(2/3)*(749376/750720)*P[n-1] + s2*(2/3)*(120036/120132)*P[n-2] + s3*(2/3)*P[n-3] + s4*(2/3)*P[n-4] + s5*P[n-5] + s6*P[n-6], n >= 6
 

It's straightforward to verify that the formula produces the correct result for n=6.  It's a little more interesting to apply it to n=7 to see what happens.  We get the following results. 

                    P[7] results

     Dan Hoey's formula           8239344
     New formula                  8225857
     Actual                       8221632
 

It is gratifying that the new formula is slightly tighter than the old one.  That fact that the new formula doesn't match the actual simply means that there are syllables of length 7q that need to be found and incorporated into the formula (or equivalently that there are non-trivial identities of length 14q that need to be found and incorporated into the formula).

» login or register to post comments

Improving the new formula

Submitted by mdlazreg on Mon, 08/24/2009 - 06:49.
I think you can improve on your formula by noticing that the last term in your formula: 
s6*P[n-6]
is true only for n=6. For n>6 it MUST be lower. The reason is that at n=6 you can count all your 696 positions, but at n>6 you cannot for the same reasons why you can count at n=4 all your 3 positions XXYY [4 syllables] but at n>4 you can count only 2 of them, this can be seen in Dan's formulas where the coefficient of the last term in each formula decreases in the next formula: 
   P[0]   = 1
   P[1]  <= 4*3*P[0]
   P[2]  <= 4*2*P[1]   + 6*3*P[0]
   P[3]  <= 4*2*P[2]   + 6*2*P[1]   + 4*3*P[0]
   P[4]  <= 4*2*P[3]   + 6*2*P[2]   + 4*2*P[1]   + 1*3*P[0]
   P[n]  <= 4*2*P[n-1] + 6*2*P[n-2] + 4*2*P[n-3] + 1*2*P[n-4]
In any case, to verify your formula we will need to generate all 14q* identities and see how do they account for the 4225 missing positions : 
 
8225857 - 8221632 = 4225
Do you have the list of 14q* identities regardless of symmetries?
» login or register to post comments

A Clarification on Fully Joining Syllables

Submitted by Jerry Bryan on Fri, 12/26/2008 - 11:04.

Consider the optimal sequence FFBB.  It may be decomposed into syllables as (F)(F)(B)(B), but (F)(F)(B)(B) is not fully joined.  We may join (F)(F) into (FF) to yield (FF)(B)(B).  Then we may join (FF)(B) into (FFB) to yield (FFB)(B).  Etc.  This example might give the false impression that full joining must be accomplished by repetitively joining two adjacent syllables until no additional adjacent syllables may be joined.

But repetitively joining two adjacent syllables is not a requirement for full joining.  For example, consider once again UURUR'F' which may be decomposed into fully joined shorter syllables as (UU)(R)(U)(R')(F'), and no further joining is possible in terms of shorter syllables.  That is, (UU) may not be joined with (R), (R) may not be joined with (U), etc.  But after UURUR'F' has been determined to a syllable because it is equal to F'L'ULU'U', we may join it together all in one go as (UURUR'F').  For example, consider the optimal sequence RUURUR'F'.  We may write it in terms of fully joined syllables as (R)(UURUR'F').  Indeed, (R)(UU)(R)(U)(R')(F') would not be considered to be a fully joined decomposition of RUURUR'F', even though no two adjacent syllables of (R)(UU)(R)(U)(R')(F') may be joined.

» login or register to post comments