slice-theory.md (12772B)
1 # Optimizing solutions: n-slice insertions 2 3 ## tl;dr 4 5 You can insert 3 slices in one of the following ways: 6 7 * `E (I) E (I or D) E2` 8 * `E (I) E2 (I) E` 9 * `E (D) E2 (D) E` 10 11 Where `(I)` denotes a "neutral" sequence like `R2 R2` or `R2 F2 L2` 12 and `(D)` denotes a "diagonal swap" sequence like `R2 F2 R2`. The list 13 above is complete up to inverses and mirrors. 14 15 ## Setting 16 17 The problem is this: say you have a DR finish on U/D that contains some 18 "sliceable" sequences, such as `U D'`, `U2 D`, `U D` or similar. To be 19 more precise, a sliceable sequence is a sequence of moves that would 20 cancel out on a 2x3x3 cube. 21 22 *(I will not address the problem of having a DR finish minus slice 23 and inserting E-moves to solve the slice, because it can be reduced 24 to the "solved slice" case by solving the slice sub-optimally with 25 any insertion.)* 26 27 Sliceable sequences can often be simplified also in a 3x3x3 cube. One 28 way to do this is to insert E-layer moves at different points of the 29 solution in such a way that the effect on the E-layer cancels out. It 30 has been known since the early days of DR (2019) how to insert two moves 31 that cancel out (`E` and `E'`, or `E2` and `E2`) without affecting the 32 E-layer edges even without looking at a cube. *(I believe the first person 33 to come up with a way to do this was Wen, but correct me if I am wrong.)* 34 35 I will call insertions of multiple E-layer moves n-slice insertions. 36 I will start this post with some necessary preliminaries, and then I'll 37 recall how to find 2-slice insertions without looking at the cube. Then 38 I will move explain how to do 3-slice insertions in a similar way, and I 39 will prove that there is no other way to do 3-slice insertions. Finally, 40 I'll leave here some considerations I have made for more complex cases, 41 hoping that this will help us develop a general theory to perform any 42 kind of n-slice insertion quickly and without looking at a cube. 43 44 ## Preliminaries: floppy and "minidisc" sequences 45 46 To insert slices, we have to understand how sequences of DR moves affect 47 the edges of the E-layer. For this purpose, we can ignore any `U*` or 48 `D*` move, hence we have to study move sequences in the floppy cube 49 subgroup <R2, L2, F2, B2>. 50 51 There are two kinds of sequences that are particularly important: those 52 that, up to `y` rotations, do not affect the E-layer (we'll call these 53 sequences *I-sequences*, where I stands for "Identity") and those that, 54 up to `y` rotations, perform a single diagonal swaps (*D-sequences*). 55 56 Some examples of I-sequences: 57 58 * `R2 F2 F2 R2` (all moves "cancel out") 59 * `R2 F2 L2` (equivalent to y', E-edges stay in the same relative position) 60 * `R2 F2 R2 L2 B2 L2` (two D-sequences in a row always give an I-sequence) 61 62 Some examples of D-sequences: 63 64 * `F2 B2` 65 * `R2 F2 R2` 66 67 Considering only the effect of a floppy sequence on the E-layer 68 edges up to y rotations, there are only 6 possible types of sequences. 69 They are equivalent to the possible permutations of a 2x2x1 cube 70 (or "minidisc" cube, name that I have just made up) that keep one 71 corner (say BL) fixed: 72 73 * `(no moves)` I-sequences 74 * `R2` 75 * `R2 F2` 76 * `R2 F2 R2` D-sequences 77 * `F2 R2` 78 * `F2` 79 80 This fact will come into play later on. 81 82 ## 2-slice insertions 83 84 As I said at the beginning, it has been known for a while how to 85 do 2-slice insertions (`E E'` or `E2 E2`) without affecting the E-layer 86 edges. The trick is the following: 87 88 * For `E E'` insertions, insert either `E` or `E'` wherever you want 89 (usually in a "sliceable" place, i.e. right before/after a `U* D*` 90 pair of moves) and insert the other slice (either `E'` or `E`) in a 91 spot such that the moves between the two insertions form an I-sequence. 92 * For `E2 E2` insertions, insert the first `E2` wherever you want, and 93 the second `E2` in a spot such that the moves between the two 94 insertions form either an I-sequence or a D-sequence. 95 96 There is no other way of inserting two slices so that they cancel out. 97 98 ### Examples 99 100 For our first example, say you have a DR finish like this: 101 102 ``` 103 Setup: R2 D R2 D' U' R2 U R2 U' B2 L2 104 105 Solution: 106 L2 B2 U //Blocks + OBL 107 R2 U' R2 U D R2 D' R2 //J+J perm 108 ``` 109 110 Ideally, you would like to "slice away" the `U D` in the second step. 111 You can insert there either an `E` or an `E'`, in either case one you save 112 one move. Where can you insert the second slice move? We can see that the 113 three moves before `U D` are an I-sequence, and placing an `E'` before 114 them would cancel out the `U` ending the first step. Here only an `E'` 115 can be inserted, so we'll have to use `E` in the other spot. So we have: 116 117 ``` 118 L2 B2 U [2] 119 R2 U' R2 U D [1] R2 D' R2 120 [1] = E 121 [2] = E' 122 ``` 123 124 Giving a final solution: `L2 B2 D B2 U' B2 U2 R2 D' R2`. 125 One move saved! 126 127 *(I like to number my insertions in the order I found them, hence the 128 [2] before the [1] in this case.)* 129 130 For our second example, take the double edge swap `(UF DF) (UL DR)`: 131 132 ``` 133 R2 F2 R2 U2 F2 R2 F2 U2 134 ``` 135 136 You can turn the two `U2` moves into `Uw2` and you get an equivalent alg. 137 This is equivalent to the following two-slice insertion: 138 139 ``` 140 R2 F2 R2 U2 [1] F2 R2 F2 [2] U2 141 [1] = [2] = E2 142 ``` 143 144 Notice that the two slices are separated by a D-sequence. 145 146 Less intuitively, you can also change some of the other moves to 147 their wide counterpart: 148 149 ``` 150 R2 [1] F2 R2 U2 F2 [2] R2 F2 U2 151 [1] = [2] = M2 152 ``` 153 154 or 155 156 ``` 157 R2 F2 [1] R2 U2 F2 R2 [2] F2 U2 158 [1] = [2] = S2 159 ``` 160 161 This trick is useful for maximizing cancellations with edge insertions, 162 without memorizing many variations of the same alg. 163 164 ## Bonus: 2 slices to solve a 4x case 165 166 This bit is out of scope for this page, but it is still interesting 167 to note. If, instead of shortening a "solved slice", you are trying to 168 solve a 4x case (that is, edges are solved but the 4 E-layer centers are 169 swapped), you can still use 2-slice insertions fairly easily. In fact, 170 inserting `E E` or `E' E'` so that they are separated by a D-sequence is 171 going solves this case. Keep in mind that this will *not* work if the two 172 `E` moves in the same direction are separated by an I-sequence! 173 174 ## 3-slice insertions 175 176 Up to inverses and mirrors, there are only two possible types of 3-slice 177 insertions: `E E E2` and `E E2 E`. Both consist of two `E` moves (or two 178 `E'` moves) and one `E2` move. 179 180 To understand how to find spots to insert them, we are going to think 181 about them as if we are inserting two `E` moves in the same direction, 182 and then fixing the slice by inserting an `E2`. This works for both 183 types of 3-slice insertions. 184 185 The first question we want to ask is then: where can we insert two 186 `E` moves so that the result can be fixed by a single `E2` insertion? 187 An `E2` insertion necessarily performs a double swap of edges, so our 188 two `E` insertion must leave such a case. (We are ignoring centers, 189 because we already now they will be solved at the end of our process if 190 we insert two `E` moves in the same direction and one `E2` move.) 191 192 The answer is: the moves between the two `E` moves must form an 193 I-sequence. Indeed, since an I-sequence does not affect the relative 194 position of E-layer edges, two `E` moves separated by an I-sequence 195 have the same effect as an `E2` move, that is a double edge swap (up to 196 `y` rotations). 197 198 This already tells us something useful: in those cases where we 199 would like to insert two slices `E E'`, but we find an admissible 200 spot for the second slice that would cancel more if we inserted the 201 inverse move, we can the inverse move and hope to find a suitable 202 spot to "correct" the insertions with an `E2`. We'll see in a minute 203 where we can insert the `E2`, now let's prove that this is the only 204 way to perform 3-slice insertions. 205 206 We can check that this is the only admissible way to insert the two 207 `E` moves by going through all other "minidisc sequences" listed in 208 the previous section, and checking that E (minidisc sequence) `E` 209 does not yield, up to a `y` rotation, a double edge swap. 210 211 Up to a `y` rotation: 212 213 * `E R2 E` is a single edge swap (`y2 F2` solves the slice) 214 * `E R2 F2 E` is a 3-cycle (`y2 [E, F2]` solves the slice) 215 * `E R2 F2 R2 E` is a single edge swap (`y2 [R2: B2]` solves the slice) 216 * `E F2 R2 E` is a 3-cycle (`y2 [E', L2]` solves the slice) 217 * `E F2 E` is a single edge swap (`y2 L2` solves the slice) 218 219 So, where can we insert the final `E2`? This is easy: the moves between 220 the `E2` and any of the two `E` moves must be either an I-sequence 221 or a D-sequence. This can be proved with the same reasoning we used a 222 few paragraphs above when we said that two `E` moves separated by an 223 I-sequence have the same effect as an `E2`, combined with the knowledge 224 on 2-slice insertions of type `E2 E2`. 225 226 This gives us 4 possible "patterns" for 3-slice insertions, up to 227 inverses and mirrors: 228 229 * `E (I) E (I) E2` 230 * `E (I) E (D) E2` 231 * `E (I) E2 (I) E` 232 * `E (D) E2 (D) E` 233 234 Where (I) and (D) denote I- and D-sequences, respectively. 235 236 ### Examples 237 238 Let's take this example: 239 240 ``` 241 Setup: L2 F2 L2 D' L2 D R2 D B2 U' 242 Solution: 243 U B2 U' B2 D' F2 U //HTR 244 U D' B2 L2 B2 U' D // Finish, one move cancel 245 ``` 246 247 *(The second step could be replace by `U' D F2 R2 F2 U D'` for one less 248 move, and then you could use a 2-slice insertion, but please let me use 249 this artificial example for now.)* 250 251 The DR finish is then: `U B2 U' B2 D' F2 U2 D' B2 L2 B2 U' D` 252 253 We would like to slice away the `U2 D'` and the `U' D` at the end, but 254 they are separated by a D-sequence, and an `E2 E2` insertion would not 255 work here. But fear not, for we can use 3-slice insertions: 256 257 ``` 258 U B2 U' [3] B2 D' F2 U2 D' [2] B2 L2 B2 [1] U' D 259 [1] = E 260 [2] = E2 261 [3] = E 262 ``` 263 264 In this case rather than inserting the two `E` moves first and then adjust 265 with an `E2` it makes more sense to insert and `E` and an `E2` and then fix 266 with another `E`, for maximum cancellation. This is reflected in the order 267 I wrote the insertions. 268 269 Here is an example of 3-slice insertion in a real (at-home) solve of mine: 270 271 ``` 272 Scramble: R' U' F D2 F' D2 F2 R2 F U2 F2 D2 F2 R2 L U2 B2 U' L R' F2 D' B U2 R' U' F 273 Solution: F' L' R D' B U L' F2 L' R2 D' L2 D2 B2 D2 R' D2 B2 R2 B2 L F2 R (23) 274 275 F' L' R D' B //EO (5/5) 276 U L' F2 L' R2 D' //DR (6/11) 277 (R' F2 R' *) R2 U2 F2 U2 L' //HTR (8/19) 278 B2 U2 R2 U2 //Slice (4/23) 279 ``` 280 281 The slice is not solve here, so the first thing I do is solving it 282 (very inefficiently). 283 284 ``` 285 * = R' D2 L R' B2 L' //Placeholder solve slice (6-2/27) 286 ``` 287 288 Then I rewrite DR part and work on insertions: 289 290 ``` 291 R2 [1] U2 F2 U2 L' [2] B2 U2 R2 U2 L B2 R L' [3] D2 F2 R 292 [1] = M2 (0) 293 [2] = [3] = M' (-4) 294 ``` 295 296 In this case, each pair of insertions is separated by an I-sequence. 297 298 ## General n-slice insertions 299 300 I have not been able to devise a general method for n-slice insertions, 301 but I have some ideas on how to work in this direction. This section 302 contains only speculations, if you are only interested in learning 303 new techniques that you can apply to your solves you do not have 304 to read it. 305 306 First of all, it could be worth considering only what we can call 307 *fundamental* slice sequences, i.e. those having no contiguous 308 sub-sequence that keeps centers solved. For example `E E E2` is 309 fundamental, but `E2 E' E E2` is not (the `E' E` subsequence keeps 310 centers solved) and neither is `E E' E E2 E` (both the `E E'` at the 311 beginning and the `E' E` starting on move 2, as well as the ending 312 `E E2 E`, are sub-sequences that do not affect centers). 313 314 The idea behind this is that we can perform a non-fundamental 315 slice insertion in two or more passes, by inserting the shorter 316 subsequences first. Unfortunately, this is not as simple: for example, 317 the non-fundamental sequence `E E' E E'` could be such that the first 318 `E E'` pair leaves a 3-cycle that is subsequently fixed by the other 319 `E E'` pair. Nevertheless, decomposing a sequence into fundamental 320 subsequences can have its use. 321 322 Classifying all fundamental sequences is actually very easy: up to 323 inverses and mirrors, this is the full list: 324 325 * `E E'` 326 * `E2 E2` 327 * `E E2 E` 328 * `E E E2` 329 * `E E E E` 330 * `E2 E E2 E'` 331 332 The fact that there are no fundamental sequences longer than 4 moves 333 is a consequence of the following theorem (warning: Math ahead, 334 caution advised): 335 336 **Theorem**. Let n and k be positive integers. If a sequence of k 337 elements of Z/nZ has sum 0 and it has no non-trivial (contiguous) 338 subsequence with sum 0, then k <= n. 339 340 *Clarification: non-trivial means that it contains at least one element 341 and it is not the whole sequence.* 342 343 **Proof** (thanks to Chiara for the nice proof). It is enough to 344 prove that any sequence of n+1 elements of Z/nZ has a subsequence whose 345 sum is 0. To prove this, let, for l=1 to n+1, s\_l = a\_1 + ... + a\_l. 346 If s\_i=0 for any i, we are done. Otherwise by the pigeonhole principle 347 there must be s\_i and s\_j with s\_i = s\_j and, say, i < j. But then 348 the subsequence a\_(i+1), ..., a\_j has sum s\_j - s\_i = 0. This proves 349 the claim. 350 351 More work needs to be done here.