# Corner permutations generated by E perms



## xyzzy (Apr 8, 2020)

(Partly inspired by the Y Perm Challenge thread, although I'd already worked this out last year and never bothered posting it here.)

*tl;dr* this post is not for you if you don't have the attention span to read through it (but basically you get only 1344 of the possible corner permutations)

It is known that you can solve a cube using only J perms, and indeed only one of the two J perms is needed. The same can be said of R perms and (I think) G perms as well. T perms and F perms (with the blocks aligned) won't work, since they divide the edges into three orbits of four pieces. What about the diag PLLs?

What corner permutations can you get by doing only E perms, starting from a solved cube? For the sake of not making this "trivial", we choose to use the standard E perm [R U' R', D] [R U R', D] that swaps two pairs of corners, while leaving the edges intact, and we forbid any AUFing. There are two possible E perms for each face, so there are twelve E perms in total that we are free to use. Since we're ignoring edges, we could just as well use the even-parity N perms, V perm, or Y perm, but those all have odd-parity standard algs, which would be confusing.

Label the eight corners with the three-bit binary strings \( \{0,1\}^3 \) thus: place the DBL corner at the origin and, for each corner, read off the x, y, z coordinates in that order to get its label. (Assume the cube is of unit width blah blah, this is not the important or interesting part.) Now, we can treat the coordinates as living in the vector space \( \mathbb F_2^3 \), which is a vector space over the finite field \( \mathbb F_2=\{0,1\} \). Let \( G\le\operatorname{Sym}(\{0,1\}^3) \) be the group of corner permutations generated by E perms
\( \begin{aligned}G:=\langle&\overbrace{(000,001)(010,011),~(000,010)(001,011)}^{\text{L-face E perms}},~\overbrace{(100,101)(110,011),~(100,110)(101,111)}^{\text{R-face E perms}},\\
&\overbrace{(000,001)(100,101),~(000,100)(001,101)}^{\text{D-face E perms}},~\overbrace{(010,011)(110,111),~(010,110)(011,111)}^{\text{U-face E perms}},\\
&\overbrace{(000,010)(100,110),~(000,100)(010,110)}^{\text{B-face E perms}},~\overbrace{(100,001)(110,111),~(100,110)(101,111)}^{\text{F-face E perms}}\rangle\end{aligned} \)

The first easy result: \( G \) is _transitive_, which is to say, given any corner piece in any corner location, you can always find some sequence of E perms that'll solve that one corner. How do you do this? You can always use an E perm to bring a corner piece to any adjacent location, so just keep doing this until you get the corner piece to where you want it to be. More than that, \( G \) is in fact _triply_ transitive: given any three corner pieces in any three corner locations, you can always find some sequence of E perms that'll solve those three corner pieces. This can be done in essentially the same manner: assuming that the three locations are all on the same face, you can solve one corner first, then use E perms on the remaining three faces to solve the second corner, then E perms on the remaining two faces to solve the third corner.

If you try to extend this to the fourth corner, you run into some trouble: no matter which three corners you solve first, you'll have either no free face (in which case you're stuck), or you have one free face and one extra free location, and you cannot get any corner piece that's on the free face into the extra free location via E perms on just that free face. _A priori_, we can't yet conclude whether _G_ is 4-transitive; maybe the basic method described for 3-transitivity won't work, but there's a more sophisticated method that does? (Think of this as being analogous to how, after solving the first layer with the LBL method, you can't do much without temporarily breaking it up.) It turns out that \( G \) is in fact _not_ 4-transitive. I'll first demonstrate the first proof I found (which is somewhat brute-forcey), then show a clean and slightly more sophisticated proof later on.

Lemma: \( G \) is a proper subgroup of the alternating group \( \operatorname{Alt}(\{0,1\}^3) \) (the collection of even permutations).

Proof: The generating elements given in the definition are all even permutations, so \( G\le\operatorname{Alt}(\{0,1\}^3) \). Consider the possible ways of partitioning the eight corners into two disjoint subsets of four corners each; there are \( \binom84/2=35 \) ways of doing this. Let \( S:=\{\{A,B\}:A\sqcup B=\{0,1\}^3\text{ and }|A|=|B|=4\} \) be the set of such partitions. We have the induced action of \( \operatorname{Alt}(\{0,1\}^3) \) on \( S \) given by \( \pi\cdot\{\{a,b,c,d\},\{e,f,g,h\}\}:=\{\{\pi(a),\pi(b),\pi(c),\pi(d)\},\{\pi(e),\pi(f),\pi(g),\pi(h)\}\} \).

The orbit of \( \{\{000,001,010,011\},\{100,101,110,111\}\} \) (the partition into corners on the left side and corners on the right side) under \( G \) can be verified (with some effort; exercise for the reader) to consist exactly of the following seven partitions:
\( \{\{000,001,010,011\},\{100,101,110,111\}\}\\
\{\{000,001,100,101\},\{010,011,110,111\}\}\\
\{\{000,010,100,110\},\{001,011,101,111\}\}\\
\{\{000,001,110,111\},\{010,011,100,101\}\}\\
\{\{000,011,100,111\},\{001,010,101,110\}\}\\
\{\{000,010,101,111\},\{001,011,100,110\}\}\\
\{\{000,011,101,110\},\{001,010,100,111\}\}
\)
(This can be written more succinctly as \( \{\{u\in\mathbb F_2^3:u\cdot v=0\},\{u\in\mathbb F_2^3:u\cdot v=1\}\} \) where \( v\in\mathbb F_2^3\backslash\{000\} \) and \( u\cdot v:=u_xv_x+u_yv_y+u_zv_z \) is the dot product.) However, the orbit under \( \operatorname{Alt}(\{0,1\}^3) \) is exactly \( S \) itself, so \( G \) and \( \operatorname{Alt}(\{0,1\}^3) \) must be different groups. □

Theorem: \( G \) is not 4-transitive.

Proof: Suppose for contradiction that \( G \) is 4-transitive. Then \( G \) contains every permutation that decomposes into two disjoint transpositions. However, this generates all of \( \operatorname{Alt}(\{0,1\}^3) \), contradicting the above lemma. □

(Note that for any \( n\ge5 \), the collection of 2+2-cycles generates \( A_n \). (Proof omitted.) We used the case \( n=8 \) above. This is incidentally false for \( n=4 \): the 2+2-cycles in a set of four elements do not generate every even permutation, but just the Klein four-group \( V\cong(\mathbb Z/2)^2 \).)

So what's the short proof? First observe that we can write the generating elements of \( G \) given above (the twelve E perms) as invertible affine functions on the vector space \( \mathbb F_2^3 \). For example, the first four (E perms on the left and right faces) are, in the same order as given above:
\( (x,y,z)\mapsto(x,y,x+z+1)\\
(x,y,z)\mapsto(x,x+y+1,z)\\
(x,y,z)\mapsto(x,y,x+z)\\
(x,y,z)\mapsto(x,x+y,z) \)
Clearly, \( G \) must be a subgroup of the group of invertible affine functions, \( AGL(3,2) \). We can compute the order of \( AGL(n,F) \) to be \( |F|^n\prod_{j=0}^{n-1}(|F|^n-|F|^j) \) if \( F \) is a finite field; substituting \( n=3 \) and \( F=\mathbb F_2 \), we get \( |AGL(3,2)|=2^3(2^3-1)(2^3-2)(2^3-4)=1344 \). Whatever \( G \) is, it can't be larger than \( AGL(3,2) \), which is already a proper subgroup of \( \operatorname{Alt}(\{0,1\}^3) \). This gives an alternative proof of the lemma above.

(In general, we _almost_ have something like multiple transitivity for \( AGL(n,F) \)—if we have \( n \) points not lying in an \( (n-2) \)-dimensional hyperplane, then we can send those \( n \) points to any other \( n \) points not lying in an \( (n-2) \)-dimensional hyperplane. This "linear independence" condition cannot be dropped; we cannot say that \( AGL(n,F) \) is \( n \)-transitive even though "most" sets of \( n \) points can be sent to "most" sets of \( n \) destination locations. However, it does turn out that \( AGL(n,2) \) is 3-transitive for \( n\ge2 \). Also, in general, it may or may not be true that \( AGL(n,F) \) has only even permutations; it happens to be true for \( AGL(3,2) \), though.)

(Another side note: multiple transitivity is a very strange thing in the study of permutation groups. While transitive groups show up all over the place, 2-transitive groups are rarer, 3-transitive groups have very special properties, and with only finitely many exceptions, 4-transitive groups are all alternating groups or symmetric groups. This seemingly innocuous statement about 4-transitive groups requires the notorious mega-theorem of the classification of finite simple groups to prove. In the context of twisty puzzles, think of this as something like: if the puzzle has a lot of pieces and you can always bring any 4 pieces to any 4 locations, then you can get _every_ even permutation. Note that this doesn't tell you how to accomplish this! It doesn't tell you how to construct commutators that affect only a small number of pieces with "short" move sequences. It doesn't even guarantee that such short commutators will exist.)

Theorem: \( G=AGL(3,2) \) and \( |G|=1344 \).

Proof: We have already established "\( \le \)". For the other direction, note that the affine group is generated by the nondegenerate elementary row operations and the translations, so we check that those are in \( G \). Since both \( G \) and \( AGL(3,2) \) are closed under conjugation by the symmetries of a cube, we will only look at one symmetry representative for each case.

Translation: \( ((x,y,z)\mapsto(x,y,z+1))=\overbrace{(000,001)(010,011)}^{\in G}\overbrace{(100,101)(110,111)}^{\in G} \)
Swapping rows: \( ((x,y,z)\mapsto(x,z,y))=(001,010)(101,110)=(000,001)(000,010)(000,001)(100,101)(100,110)(100,101)=\overbrace{(000,001)(100,101)}^{\in G}\overbrace{(000,010)(100,110)}^{\in G}\overbrace{(000,001)(100,101)}^{\in G} \)
Adding one row to another: \( ((x,y,z)\mapsto(x,y,x+z))\in G \) (this is already an E perm; see above)
Multiplying a row by a nonzero amount: the only nonzero scalar is 1, so there's nothing to check here.

Therefore \( AGL(3,2)\le G \), and hence \( G=AGL(3,2) \). As a consequence, \( |G|=|AGL(3,2)|=1344 \). □

To conclude, exactly 1344 out of all 8! = 40320 corner permutations are reachable using only E perms.

Your homework, if you've somehow read through all of this: Show that \( G \) is a maximal subgroup of \( \operatorname{Alt}(\{0,1\}^3) \), i.e. for any \( \pi\in\operatorname{Alt}(\{0,1\}^3)\backslash G \), it holds that \( \langle G,\pi\rangle=\operatorname{Alt}(\{0,1\}^3) \). (What this means: while we don't get every even permutation of the corners with only E perms, we fail to do so by the "smallest" possible amount.)


----------



## kubesolver (Apr 8, 2020)

> The same can be said of R perms and (I think) *G perms* as well



Nope. G-perm is 3c3e and no matter how many times you do this you can never get the 2c2e "parity". Good question for a kompetition though


----------



## xyzzy (Apr 8, 2020)

kubesolver said:


> Nope. G-perm is 3c3e and no matter how many times you do this you can never get the 2c2e "parity". Good question for a kompetition though


You can AUF it to 2c4e or 4c2e. (For that matter, most of the common J perm and R perm algs are 3c3e too!)


----------



## kubesolver (Apr 8, 2020)

xyzzy said:


> You can AUF it to 2c4e or 4c2e. (For that matter, most of the common J perm and R perm algs are 3c3e too!)


Right! Forgot that different aufs are still the same perm

i commented on the only part i could understand. I tried but i couldn't follow the whole proof. 
Few days ago i was sure that i have a proof of this that doesn't require a degree in group theory to understand but i didn't see all the details in my head. 
.......
I just spent 20 minutes writing down my idea semi formally to just prove it wrong.


----------



## xyzzy (Apr 9, 2020)

kubesolver said:


> i commented on the only part i could understand. I tried but i couldn't follow the whole proof.


I'm here to explain anything that needs further elaboration! (I typed out the post at like 2 am so I glossed over loads of tiny details.)

---

Also, I write these walls of text to _educate_, not merely to show off. Although that latter thing is something I somehow need to do every so often because if I don't, some randos forget who I am and think _I_ need to be schooled on babby-tier mathematics. (Yes, I'm calling the skewb NAR holder a rando, _fight me_.)


----------



## Bruce MacKenzie (Apr 9, 2020)

xyzzy said:


> (Partly inspired by the Y Perm Challenge thread, although I'd already worked this out last year and never bothered posting it here.)
> 
> *tl;dr* this post is not for you if you don't have the attention span to read through it (but basically you get only 1344 of the possible corner permutations)
> 
> ...




I entered the 12 E-Perms into GAP, closed the group and it shows the group size as 2,939,328. Why is this? Does your analysis ignore orientation?


The 12 "E Perms"

U D R D' L D R' U' D' R U L' U' R'
U D F U' B U F' U' D' F D B' D' F'
F B R F' L F R' F' B' R B L' B' R'
U L D L' U' R L U R' D' R U' R' L'
U D F D' B D F' U' D' F U B' U' F'
F B R B' L B R' F' B' R F L' F' R'
F B U F' D F U' F' B' U B D' B' U'
R L U L' D L U' R' L' U R D' R' U'
R L F L' B L F' R' L' F R B' R' F'
U D R U' L U R' U' D' R D L' D' R'
F L B L' F' R L F R' B' R F' R' L'
F B U B' D B U' F' B' U F D' F' U'

GAP Canonical Cycle Notation as permutations of the facelets:

 •• •• •• •• •1 •• •• •• •• •2 •• •• ••• ••3 ••• ••• ••• 4•• ••• •••
Index 12 34 56 78 90 12 34 56 78 90 12 34 567 890 123 456 789 012 345 678
Slot UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR

FOO := Group(
(25,35)(26,36)(27,34)(37,42)(38,40)(39,41),
(25,30)(26,28)(27,29)(37,47)(38,48)(39,46),
(25,34)(26,35)(27,36)(28,31)(29,32)(30,33),
(25,38)(26,39)(27,37)(34,42)(35,40)(36,41),
(31,36)(32,34)(33,35)(40,45)(41,43)(42,44),
(37,40)(38,41)(39,42)(43,46)(44,47)(45,48),
(31,45)(32,43)(33,44)(34,41)(35,42)(36,40),
(28,48)(29,46)(30,47)(31,44)(32,45)(33,43),
(25,28)(26,29)(27,30)(31,34)(32,35)(33,36),
(28,33)(29,31)(30,32)(43,48)(44,46)(45,47),
(37,46)(38,47)(39,48)(40,43)(41,44)(42,45),
(25,39)(26,37)(27,38)(28,47)(29,48)(30,46)
);
<permutation group with 12 generators>
Size (FOO);
2939328


----------



## xyzzy (Apr 9, 2020)

Bruce MacKenzie said:


> I entered the 12 E-Perms into GAP, closed the group and it shows the group size as 2,939,328. Why is this? Does your analysis ignore orientation?


Yes, I'm completely ignoring orientation.

Your GAP calculation does verify that all 3^7 = 2187 orientations for each of the 1344 permutations are reachable, which I was only semi-sure of because I hadn't bothered to rigorously prove that.


----------



## Bruce MacKenzie (Apr 9, 2020)

xyzzy said:


> Yes, I'm completely ignoring orientation.
> 
> Your GAP calculation does verify that all 3^7 = 2187 orientations for each of the 1344 permutations are reachable, which I was only semi-sure of because I hadn't bothered to rigorously prove that.



Ok. I did the GAP calculation using only position permutation and can confirm your result:


FOO := Group(
(13,16)(17,18),
(14,20)(15,19),
(13,16)(14,15),
(13,17)(16,18),
(13,14)(17,20),
(17,18)(19,20),
(14,15)(19,20),
(15,16)(18,19),
(13,14)(15,16),
(15,19)(16,18),
(17,20)(18,19),
(13,17)(14,20)
);

<permutation group with 12 generators>
Size (FOO);
1344

Interesting. If you add a three cycle to the generators you get all 8! / 2 even parity permutations. So, you can generate these tandem two cycle perms using three cycle perms but not the other way around.


----------



## pjk (Apr 10, 2020)

Just a heads up, I removed many posts that simply comment saying "yeah, I understand" or "this is over my head". They aren't constructive to the conversation at all and are not useful to have here. In order to keep discussion useful and interesting, please avoid commenting on threads like this unless you have something legitimate to say to the conversation or something useful, or have a good question for the thread creator.


----------

