God's Second Number?

[cuBerBruce]

do you know any positions that are both 20f* and 26q*?

That's an easy question. There is essentially only one known 26q* position (actually 3 symmetrically equivalent positions) and that position is indeed a 20f* position. I don't believe there is a manuever for it, however, that is both 26q* and 20f*.

Reid's site lists:

U2 D2 L F2 U' D R2 B U' D' R L F2 R U D' R' L U F' B' (26q*, 21f)
F U2 R L D F2 U R2 D F2 D F' B' U2 L F2 R2 B2 U' D (20f*, 28q)

A 26q*/26f maneuver (for whatever that's worth) is: U F U F U' R D' F L D' F B' D' F D' L U F' U' F D' F U' F' R' D'

Thanks for the list, I always thought only "id", Superflip and both Supertwists were invariant. Cool!
Edit: huh? I thought x invariant meant x * y * x' = y here. Seems to be something different.

An element of the cube group (g) is invariant under a cube symmetry (m) if:

m' g m = g

Note that the cube symmetry group has 48 elements: 24 whole cube rotations (including the identity) and 24 refelections.

So, for example, we let g = U R F' B U' D' F U' D F L F' L' U R D F U R L and let m = x y; then

m' g m = y' x' U R F' B U' D' F U' D F L F' L' U R D F U R L x y

results in the same position as just applying:
U R F' B U' D' F U' D F L F' L' U R D F U R L = g

Hence, U R F' B U' D' F U' D F L F' L' U R D F U R L is invariant under the cube symmetry x y.

 

[rokicki]

I don't believe there is a manuever for it, however, that is both 26q* and 20f*.

This is fascinating! I tried to come up with a quick counterexample, generating a few hundred 20f* solutions
and a few hundred 26q* solutions, and could not come up with a solution that is both 20f* and 26q*.

I can't think of a reasonable explanation for this, and I know this position has just an incredible number of both
20f* and 26q* solutions.

So, can anyone either prove there is no such solution, or find a counterexample?

Is there a concise explanation for this?

 

[cuBerBruce]

This is fascinating! I tried to come up with a quick counterexample, generating a few hundred 20f* solutions
and a few hundred 26q* solutions, and could not come up with a solution that is both 20f* and 26q*.

I can't think of a reasonable explanation for this, and I know this position has just an incredible number of both
20f* and 26q* solutions.

So, can anyone either prove there is no such solution, or find a counterexample?

Is there a concise explanation for this?

I stated my belief that there are no 20f*/26q* maneuvers based on:

1) Reid's page did not list a maneuver that was both 26q* and 20f* and I believe he would have if he had found one.
2) About 2 years ago, I believe I identified all symmetrically distinct canonical 26q* maneuvers for the known 26q* position. I counted 16738 such maneuvers. I checked these for how long they are in FTM, and found all of them to be at least 21 moves.

I've now generated the distribution of these maneuvers in terms of FTM length. That distribution is:

FTM length   count
    20           0
    21         380
    22         770
    23        1894
    24        3540
    25        5514
    26        4640

Possibly I could have missed some maneuvers in my original search. You're welcome to try to find an error in my data.

 

[rokicki]

Wow. I decided to check it the other way around, finding all 20f*'s
and seeing where they showed up in the QTM metric.

Here are the results.

Every single 20f* solution to superflip-fourspot has exactly eight
double twists (and is therefore 28q).

There are something like 1600 of them. Every single one has
exactly eight half-twists. None with six, none with ten, none with
twelve.

There's got to be a logical explanation for this.

 

[Stefan]

As I don't think I've seen a proof for the existence of God's Second Number, I'll try one (and an upper bound):

You can replace every F turn (other turns similarly) in a solution with
F U D R2 L2 U' D' B' U D R2 L2 U' D' F (15 moves)
or
F U2 R2 D2 L' B' L2 B L B R D2 R U2 L2 F (16 moves)
and this doesn't introduce cancellations. So if you have an optimal solution of length m and replace a move like this m times with 15 moves and 20-m times with 16 moves, you have a solution with m+14m+15(20-m)=300 moves and thus all states are solvable in exactly 300 moves. And since there is a natural number with this property, there also is a smallest one, which is God's Second Number.

(The zero-moves solution of the solved state doesn't have moves to replace, but there are identity algs with 10 moves you can start with.)

Because of the symmetry of [the superflip] position, any move you make makes the position closer to solved.

I don't think the symmetry alone rules out that a quarter turn would get you closer to solved but a half turn wouldn't (or vice versa).

If [from superflip] you do any two moves on opposite sides, [...] no 20 move solution is possible.

I must misunderstand, as for example
(U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2) (F2 B)
obviously has a 20 move solution. Please clarify.

 

[Lucas Garron]

You can replace every F turn (other turns similarly) in a solution with

1. Very nice argument!
2. I think you also need to handle half-turns. I don't think your replacements allow us to expand R2 U2 into 300.

Perhaps use there?

F R U R' F' U2 L' U' L F U2 F (12h)
F R2 F2 R2 F2 R2 F2 R2 F2 R2 F2 R2 F' (13h)

EDIT: Never mind, we could simply replace the last F in each of your algs with F2.

 

[Stefan]

Ah yeah, I don't know why I packed Do-F-without-turning-F algs between the F turns, I should have just packed identity algs between them. Here are shorter ones:

F2 U2 R2 L2 U2 D2 R2 L2 D2 F' (replaces F, adds 9 moves)
F2 U R2 L2 U2 D2 R2 L2 U D2 F' (replaces F, adds 10 moves)

If your optimal solution has fewer than 13 moves, first append 8-move-identities so you have a solution with m=13..20 moves. Then do m-13 replacements adding 9 moves and 20-m replacements adding 10 moves and you have m+9(m-13)+10(20-m)=83 moves.

Then again, 83 of course isn't really better than 300.

 

[Stefan]

Um, we can also reduce the variation instantly by adding more moves:

F2 U2 R2 L2 U2 D2 R2 L2 D2 F' (replaces F, adds 9 moves)
F2 U R2 L2 U2 D2 R2 L2 U D2 F' (replaces F, adds 10 moves)
F2 R U2 R2 L2 U2 D2 R2 L2 D2 R' F' (replaces F, adds 11 moves)
F2 R U R2 L2 U2 D2 R2 L2 U D2 R' F' (replaces F, adds 12 moves)
F2 U R U2 R2 L2 U2 D2 R2 L2 D2 R' U' F' (replaces F, adds 13 moves)
F2 U R U R2 L2 U2 D2 R2 L2 U D2 R' U' F' (replaces F, adds 14 moves)
F2 R U R U2 R2 L2 U2 D2 R2 L2 D2 R' U' R' F' (replaces F, adds 15 moves)

So get to m=13..20 moves and then add an 8-moves-identity (if m=20) or replace some move so that you have 28 moves. Thus GSN is at most 28.

 

[EMI]

An element of the cube group (g) is invariant under a cube symmetry (m) if:

m' g m = g

Note that the cube symmetry group has 48 elements: 24 whole cube rotations (including the identity) and 24 refelections.

So, for example, we let g = U R F' B U' D' F U' D F L F' L' U R D F U R L and let m = x y; then

m' g m = y' x' U R F' B U' D' F U' D F L F' L' U R D F U R L x y

results in the same position as just applying:
U R F' B U' D' F U' D F L F' L' U R D F U R L = g

Hence, U R F' B U' D' F U' D F L F' L' U R D F U R L is invariant under the cube symmetry x y.

Ok thanks, I thought it was about turns.

 

[Stefan]

Actually, since it's that easy to build identities for any number of moves from 8 and starting with any side, just take an optimal alg and append an appropriate identity to get to 28 moves. (And now it's so obvious that I'm sure someone must have said this before somewhere.)

 

[cuBerBruce]

I don't think the symmetry alone rules out that a quarter turn would get you closer to solved but a half turn wouldn't (or vice versa).

Correct. For example, Pons Asinorum is also completely symmetrical but doing U from Pons Asinorum doesn't get you closer to solved in FTM. The statement would be correct for QTM. For FTM, it can be claimed that you at least can not get farther from solved with one turn (of course, this is for the stated symmetry condition).

Given that superflip is also in its own conjugacy class, any cyclic shift of a superflip maneuver is also a a superflip maneuver. Since a known optimal superflip maneuver contains both quarter turns and half turns, we can use this (along with the symmetry) to infer that any half turn or quarter turn from superflip gets us closer to solved.

I note that the Wiki page for superflip is making essentially the same false claim:

Also, because the superflip is completely symmetrical but not solved, any move will bring it to a position that is easier to solve.

 

[elrog]

I must misunderstand, as for example
(U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2) (F2 B)
obviously has a 20 move solution. Please clarify.

I was wrong in saying that no 20 move solution is possible. What I should have said is that if there is a 20 move solution it will be unrelated to the 20 move solution you started with. My thinking was that if you find a 20 move strong state that is isolated enough, you could do this and not run in to other 20 move solutions.

Nice job on establishing an upper bound.

Wow. I decided to check it the other way around, finding all 20f*'s
and seeing where they showed up in the QTM metric.

Here are the results.

Every single 20f* solution to superflip-fourspot has exactly eight
double twists (and is therefore 28q).

There are something like 1600 of them. Every single one has
exactly eight half-twists. None with six, none with ten, none with
twelve.

There's got to be a logical explanation for this.

May I ask how you found every 20 move sequence and checked the similarities in all of them? I assume you know something of computer programming. It seems as if everyone is accomplishing things that I can't imagine trying to find usually through being skilled in programming.

Edit:
Going by Stefen's logic, I have come up with the following move sequence: B2 D2 U2 B2 F2 D2 U2. You can add F2 to the beginning and any F move you want to the end to replace an F move.

This would by a 9 move (so you add 8 moves) sequence with an F at the beginning and end, so that lowers the upper bound to 27.

 

[qqwref]

I have come up with the following move sequence: B2 D2 U2 B2 F2 D2 U2. You can add F2 to the beginning and any F move you want to the end to replace an F move.

I note that your sequence has a B2 right after the first F2. I was going to post saying that that could create cancellations (e.g. B2 F => B2 F2 B2 D2 ...) but I realized you could just put the B2 after the F move instead of before it. So we're still adding the right number of moves.

If we want to improve the bound to 27, though. 20-move sequences still need to have 7 moves added.
- If the 20f* sequence ends with F without a B move before it, replace it with F' B2 U2 D2 F2 B2 U2 D2.
- If the 20f* sequence ends with F2 without a B move before it, replace it with B U2 D2 F2 B2 U2 D2 B.
- If the 20f* sequence ends with B F, replace it with F' B U2 D2 F2 B2 U2 D2 B2. For B F', just treat it like F2 + B F.
- If the 20f* sequence ends with B F2, replace it with F R2 L2 F2 B2 R2 L2 F' B'.
- If the 20f* sequence ends with R B2 F2, replace it with R' U D' F2 L2 R2 F2 D U' R2.
- If the 20f* sequence ends with R2 B2 F2, replace it with R' B R' U' B2 L' B' L U F2.
(This should cover everything, up to symmetry and mirroring.)

 

[rokicki]

May I ask how you found every 20 move sequence and checked the similarities in all of them? I assume you know something of computer programming. It seems as if everyone is accomplishing things that I can't imagine trying to find usually through being skilled in programming.

I ran my optimal solver on the position and it found all the distance-20 solutions.

Initially I did something faster; I found all neighbors, eliminated symmetry-equivalent
positions reducing the count from 18 to 4, and then found all distance-19 solutions for
these positions. But later I just ran the optimal solver on the position directly and
asked it to find all solutions.

 

[elrog]

Do you have a fast optimal solver? I would love to get a faster one but I was lucky my parents let me get the regular cube explorer.

@ qqwref - Stefen found a position that adds nine moves and said that makes the upper bound 28. So adding 7 moves makes the upper bound 27. By my logic, I came to the same conclusion.

Here's my thinking: For there to be a second god's number, there has to be a 19 move strong or lower position that cannot be solved in 20 moves exactly. If you can add 8 or more moves to any position and keep the same position, you can turn a position that proves there is a second god's number into a 27 move strong position or lower if it is less than 19 moves strong.

I am in the middle of lowering the upper bound down to 25.

 

[qqwref]

@ qqwref - Stefen found a position that adds nine moves and said that makes the upper bound 28. So adding 7 moves makes the upper bound 27. By my logic, I came to the same conclusion.

That's not quite valid, though. Stefan said: "So get to m=13..20 moves and then add an 8-moves-identity (if m=20) or replace some move so that you have 28 moves". But there is no 7-move identity to add, and your sequence adds 8 moves. So you missed the case of taking a 20-move algorithm and getting a 27-move algorithm. As for the paragraph you typed after the above quote, no idea what you're saying

 

[elrog]

That's not quite valid, though. Stefan said: "So get to m=13..20 moves and then add an 8-moves-identity (if m=20) or replace some move so that you have 28 moves". But there is no 7-move identity to add, and your sequence adds 8 moves. So you missed the case of taking a 20-move algorithm and getting a 27-move algorithm. As for the paragraph you typed after the above quote, no idea what you're saying

I will try to explain myself better then. Lets pretend we find a position that is 19 moves strong and cannot be solved in 20 moves exactly. If we rotate the algorithm so that it ends it with an F move, we can replace the F at the end with a sequence that adds 8 moves. This would give us a 27 move sequence that solves the same cube state.

So for such a position to exist, there has to be a 27 move sequence for it making 27 the upper bound.

Stefen showed that we can add any number of moves above 8 in place of an F at the end. This would make the upper bound of 27 hold true for states that are 18 moves strong and cannot be solved in exactly 20 moves.

 

[qqwref]

It sounds like you're just saying that if we have an 18- or 19-move sequence we can make it 27 moves. That's pretty clear. The thing I think you're glossing over is how to turn a 20-move sequence into a 27-move sequence. Remember, to have an upper bound, we need to be able to write all sequences as that number of moves, even 20f* ones.

 

[rokicki]

Do you have a fast optimal solver?

Yes; I believe I have the world's fastest
optimal solver.

 

[Renslay]

Yes; I believe I have the world's fastest
optimal solver.

Is it public?

I just run the HugeOptimalSolver of CubeExplorer 5.00s on three random cubes. All three of them were 18f*, and the runtimes were 0:50, 1:30 and 2:56. The superflip took 3:40 (it reached depth 18 much faster, I think because of the high level of symmetry.)