 # sebastiano.tronto.net

Source files and build scripts for my personal website
git clone https://git.tronto.net/sebastiano.tronto.net

slice-theory.md (12137B)

```      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 
119 R2 U' R2 U D  R2 D' R2
120  = E
121  = 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  before the  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  F2 R2 F2  U2
141  =  = 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  F2 R2 U2 F2  R2 F2 U2
151  =  = M2
152 ```
153
154 or
155
156 ```
157 R2 F2  R2 U2 F2 R2  F2 U2
158  =  = 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'  B2 D' F2 U2 D'  B2 L2 B2  U' D
259  = E
260  = E2
261  = 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 I would like to add more examples here, but I have yet to use 3-slice
270 insertions in an actual FMC attempt.
271
272 ## General n-slice insertions
273
274 I have not been able to devise a general method for n-slice insertions,
275 but I have some ideas on how to work in this direction.  This section
276 contains only speculations, if you are only interested in learning
277 new techniques that you can apply to your solves you do not have
279
280 First of all, it could be worth considering only what we can call
281 *fundamental* slice sequences, i.e. those having no contiguous
282 sub-sequence that keeps centers solved. For example `E E E2` is
283 fundamental, but `E2 E' E E2` is not (the `E' E` subsequence keeps
284 centers solved) and neither is `E E' E E2 E` (both the `E E'` at the
285 beginning and the `E' E` starting on move 2, as well as the ending
286 `E E2 E`, are sub-sequences that do not affect centers).
287
288 The idea behind this is that we can perform a non-fundamental
289 slice insertion in two or more passes, by inserting the shorter
290 subsequences first. Unfortunately, this is not as simple: for example,
291 the non-fundamental sequence `E E' E E'` could be such that the first
292 `E E'` pair leaves a 3-cycle that is subsequently fixed by the other
293 `E E'` pair. Nevertheless, decomposing a sequence into fundamental
294 subsequences can have its use.
295
296 Classifying all fundamental sequences is actually very easy: up to
297 inverses and mirrors, this is the full list:
298
299 * `E E'`
300 * `E2 E2`
301 * `E E2 E`
302 * `E E E2`
303 * `E E E E`
304 * `E2 E E2 E'`
305
306 The fact that there are no fundamental sequences longer than 4 moves
307 is a consequence of the following theorem (warning: Math ahead,
309
310 **Theorem**. Let n and k be positive integers. If a sequence of k
311 elements of Z/nZ has sum 0 and it has no non-trivial (contiguous)
312 subsequence with sum 0, then k <= n.
313
314 *Clarification: non-trivial means that it contains at least one element
315 and it is not the whole sequence.*
316
317 **Proof** (thanks to Chiara for the nice proof). It is enough to
318 prove that any sequence of n+1 elements of Z/nZ has a subsequence whose
319 sum is 0. To prove this, let, for l=1 to n+1, s\_l = a\_1 + ... + a\_l.
320 If s\_i=0 for any i, we are done. Otherwise by the pigeonhole principle
321 there must be s\_i and s\_j with s\_i = s\_j and, say, i < j. But then
322 the subsequence a\_(i+1), ..., a\_j has sum s\_j - s\_i = 0. This proves
323 the claim.
324
325 More work needs to be done here.
```