I've been itching to post this table of permutations for the 2x2x2 Rubik's "toy'. This P-space is known to be complete (it has a small algebraic height), however no table is known to have been composed for the 3x3x3 or higher-N puzzles. This is indirectly related to the notion of an intersection "identity"; I consider this table to show the "carry/lookahead" function in the QTM and FTM metrics. F "borrows" from Q, and Q "carries" F (across to the right-handed total). Note also that the number of intersections per carry/borrow, increases as n+1, up to n = 4 in the FTM. Code: FTM 0 1 2 3 4 5 6 7 8 9 10 11 Total QTM 0 1 1 1 6 6 2 3 24 27 3 24 96 120 4 6 144 384 534 5 72 768 1,416 2,256 6 9 564 3,608 4,788 8,969 7 126 3,600 15,072 14,260 33,058 8 5 1,248 18,996 57,120 36,780 114,149 9 120 9,480 85,548 195,400 69,960 360,508 10 1,728 55,548 341,604 487,724 43,984 930,588 11 72 14,016 238,920 841,500 256,248 96 1,350,852 12 1,032 56,440 455,588 268,532 944 782,536 13 12 928 32,968 54,876 1,496 90,280 14 8 160 108 276 Total 1 9 54 321 1,847 9,992 50,136 227,536 870,072 1,887,748 623,800 2,644 3,674,160 That is, the table says something about the symmetry.
Well, the array isn't sparse, it's compact. (duh!) Is there a straightforward formula that gives the width or depth of a particular intersection, for a row or column respectively, that only selects nonzero values? Can it be written in terms of m,n the row,column metrics? How to account for the apparent nonlinearities (for instance the column depth is 5 in three places and the row width is 5 in five places) in what must be a multilinear set of relations? Ed: apologies for vague terminology like "number of intersections", which should be "number of groups intersecting the QTM, for n" as the def. for depth in the graph G, or matrix M or array A, ...whatever.
There is a solution to the problem of building a table for the 3x3x3 which is 6th order in polynomial time. http://www.math.toronto.edu/~drorbn/Talks/Mathcamp-0907/NCGE.pdf It uses a table of permutations as generators, so the inductive step is that a permutation table exists for the 2x2x2. So that Gaussian elimination and noncommutative relations in G will reveal the widths and depths. The rule is that the quarter turn metric is "squared" by a full turn. So the intersection at (1,1) = 6 means there are 6xQ and 6xF isometries. You can't make a single quarter turn into a squared full turn so they must be separate automorphisms. When m = 2 there are 3 isometries for a single f (at n = 1). Which values of n and m have intersections that include identical states, since both metrics map the entire distance |G| or have the same outer extreme?