-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy path读书笔记.lean
1400 lines (1369 loc) · 120 KB
/
读书笔记.lean
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
正在阅读Adventures in group theory Rubiks cube,
Merlins machine, and other mathematical toys (Joyner, David) --ok
看完第5章,--doing 1.一组魔方操作,最多重复操作1260次就可以还原,不多吧,操作为m = RU2D−1BD−1 。柯西定理有此话题更多的讨论。 --ok
还是得从书的第一页开始,不懂的举例子|然后要将关键定理用我们自己的理解记下来,不然会忘|跳过非魔方的部分--ok
|定理不一定要详细证明,但是名词一定要彻底理解,这样证明就只是一种技巧 |写记录的时候先写个总概括--ok
实在不懂的找gpt举例子:
关键定理自我理解记录:
1.P (f ) :是一个矩阵,其中 f 是一个排列,举例;
写成f=(2,1,3), P(f)就是
[[0 1 0]
[1 0 0]
[0 0 1]], 也就是第1行第2列,第2行第1列,第3行第3列,根据f来的,都是1,其他为0
2.Sn : 有时代表任意排列组成的集合,元素数量当然就是n!个
3.与有关的魔方引理lemma 3.2.3:r^−1sr复合操作,能直接修改首位位置,修改效果是直接通过r映射。
举例:
i是uf位置,j是uf位置
有一个操作s效果是3循环:s:= uf → ul → ur → uf ,
另一个操作r := F^2
则:
r^−1sr的效果是r(i)位置 → r(j)位置
因为r(uf)= df,所以:
df → ul → ur → df
4.对于排列f,f的order定义:使得 f^N = 1 > 0 的最小整数 N 称为 f 的阶数order
5.对于排列f,f是even或odd的,意思是:swap(f ) 是even或odd,也就是f的逆序数之和
逆序数具体定义:
定义 3.1.1. 让 f : 跟n → 跟n 是一个排列组合,让
和f (i) = #{j > i | f (i) > f (j)}, 1 ≤ i ≤ n − 1.
swap(f ) = 和f (1) + . . . + 和f (n − 1)
6.算法:生成所有排列的方式竟然如此简单 3.4
7.超级翻转游戏:只翻转所有棱块,其他角块和中心块不影响
8.Sn :对于集合n,任意排列(一个排列可以用一个向量来表示)组成的集合,也可以记为“symmetric对称群”,
因为满足P87的四个属性:封闭+结合律+单位排列+逆排列。
symmetric:是群A的一个可选性质,群A需满足:封闭+结合律+单位排列+逆排列。
比如对于集合N={1,2,3},N中元素任意排列得到若干向量g1,g2,...gm ,有这些向量g1,g2,...gm组成的集合,满足群的定义,且满足四个属性,所以具备symmetric这个群的可选性质。
9.tips:从群的乘法表出发分析,可以很容易的定义和判别是否阿贝尔群,关于对角线对称。
10.对于集合S生成,置换群G,定义是:由某个有限的集合S,S集合里面元素是一个个排列,
这样来定义置换群G:G集合需要满足:里面元素是任意S里面的元素复合运算得到的结果(当然也是一个个排列)。
11.魔方群:是一个置换群G,也叫做由Sx中的元素“生成”的置换群。
X: 是魔方的 54 个面的集合,
Sx:是一个排列的集合,让 R、L、U、D、F、B ∈ Sx 表示魔方的基本动作, R、L、U、D、F、B都是一个个排列
置换群G = <R、L、U、D、F、B> ⊂ Sx 就称作魔方群(每一个状态,是由某一组操作来代表的)
12.对于群G,群G的order,符号|G|表示: 群元素的数量。 魔方群的|G| = 2^27*3^14*5^3*7^2*11
13.对于群的元素g,g的order,符号ord(g)表示:使得g^m=1 的最小的m(如果m存在的话).
魔方群中最大order为元素m = RU2D−1BD−1,其order为1260
14.柯西定理,用来判断元素g,g满足order是某个数,这样的g,是否存在。
因此可以判断魔方群中某个元素g,g符合order为某个值,能判断这样的g是否能存在。
15.对于群G,群G由一个元素A通过运算生成的,称为cyclic 循环的群。换句话说,G中元素都是这样的一般形式:A^k , k=1,2,3...
16.对于群G,和G的子群H,这样的数|G|/|H|, 称为index ,符号记为[G:H]。
17.对于群G,G的center,中心:center是一个G的子群,里面的元素z,对于任意的群G里面的元素g,z ∗ g = g ∗ z,换句话说可以左乘+右乘相等的
具体集合定义为Z(G) = {z ∈ G | z ∗ g = g ∗ z,对于所有 g ∈ G}。
trivial center:当子群Z(G)只有一个元素时,这个元素也就是最普通的单位元时,就称作平凡的。
借此机会,对于群G,可以定义commutative:群G,如果G = Z(G),即G等于G的这个子群,则G称作交换的。
18.对于魔方群G,G是S₄₈(一个由48元素的任意排列,这样的排列为元素组成的群)的一个子群。
19.对于魔方群G,G的center就是集合Z(G) = {1, superflip}
superflip已被人们所知道的一个是:
superflip = R · L · F · B · U · D · R · L · F · B · U · F 2 · M R ·
·F 2 · U −1 · MR 2
R · B2 · MR −1
R · B2 · U · MR 2
R · D
= R · L · F · B · U · D · R · L · F · B · U · F 2 · R−1 ·
·L · D2 · F −1 · R2 · L2 · D2 · R · L−1 ·
·F 2 · D · R2 · L2 · D (34 quarter turns)(它是34次转动的一组操作)
(这里MR 指的是右中间切片顺时针旋转 90 度(从右边的面来看))
而且已被证明,最小转动次数的superflip是一下这个:
R, R−1 , L, L−1 , U, U −1 , D, D−1 , B, B−1 , F, F −1
20.由魔方的两个2次操作组成的群H:H = 〈R^2, U^2〉,
这个群的所有12个元素是:
H = {1, R2 , R2 · U2 , R2 · U2 · R2 ,(R2 · U2 )^2 ,(R2 · U2 )^2 · R2 ,(R2 · U2 )^3 ,
(R2 · U2 )^3 · R2 ,(R2 · U2 )4 ,(R2 · U2 )^4 · R2 ,(R2 · U2 )^5 ,(R2 · U2 )^5 · R2 }
单位元满足:1 = (R2 · U2 )^6
21.对于群G,g、h是G中的元素,commutator of g,h:是一个G中的元素,记为[g,h],[g,h] = g ∗ h ∗ g−1 ∗ h−1
讲一个常识:先穿袜子再穿鞋,和,先穿鞋再穿袜子,不一样!!!
22.对于魔方群,Y commutator:[F, R−1 ] = F · R−1 · F−1 · R
Z commutator:[F, R] = F · R · F−1 · R−1
23.关于魔方群的只改变魔方本身有限块的位置的定理:如果 x、y 是魔方的基本移动,与共享边的面相关联,则
1.[x, y]^2 正好置换 3 个边块,不改变任何角块;
2.[x, y]^3 正好置换 2 个角块,不置换任何边块。
24.1. subgroup:子群
24.对于群G,commutator subgroup of G:是一个G的子群,里面的元素是所有的commutator [g,h],这样的commutator由G中的任意两个元素g,h生成。
具体定义是:{[g, h] | g, h belong to G}
有趣的事实:当commutator subgroup足够大时,基本上和魔方群是相差无几的。也就是说,任意魔方状态基本都通过一组commutator可以达到。
25.对于群G,derived series:是一个序列的子群:... ⊂ (G‘)‘ ⊂ G’ ⊂ G
以此前提,对于群G,可以定义solvable 可解群:derived series代表的序列中,有一个群是只有一个元素的,该元素是恒等变换。
26.对于群G,g、h是G中的元素,conjugate of g by h 共轭:是一个G中的元素,记为g^h, g^h = h−1 ∗ g ∗ h
27.对于群G,g1、g2是G中的元素, two elements g1,g2 are conjugate: 是一种关系,
需要满足:如果存在一个元素 h ∈ G,使得 g2= g1^h = h−1 ∗ g ∗ h
判断是否共轭也有一个柯西定理
28.2.对于集合S,R是S的一个关系, equivalence relation:满足自反性+对称性+传递性。
28.1.对于集合S,R是集合S的一个等价关系,s是集合S的任意一个元素,the equivalence class of s in S:是集合S的一个子集,
具体定义:[s] = {t ∈ S | s ∼ t} , 也就是记为[s]
28.对于群G,在等价关系“conjugation”下的 等价类的集合 G∗:是一个由等价类组成的集合,元素是一个个等价类???, 记为G∗。
以此前提,对于群G,可以定义一个多项式generating polynomial of the order function on G :
是一个多项式,变量是t,p G (t) = ∑c∈G∗ t^order(c)
29.对于群G,g是G中的一个元素,the conjugacy class of g in G :是一个集合,里面的元素由任意h通过conjugate运算得到,
因为conjugate这个关系是等价关系来的,等价关系可以理解成等价类,由于某种原因???可以把群G分成若干个类,所以每一个conjugate的计算结果可以代表一个等价类。
具体定义为:记为 Cl(g) 或 ClG (g),Cl(g) = ClG (g) = {h−1 ∗ g ∗ h | h ∈ G}
30.对于群G,X是一个群G的子集,G acts on X on the right:G和X的一个关系,需要满足:(这个定义的实际例子我觉得是G的元素分别作用在边块X1和角块X2上,所以要研究这样的作用在子集上的映射)
1.属于 G 的每个 g元素,对应产生一个函数φ:X → X
2.群 G 的恒等式 1 定义了 X → X 上的恒等式函数。
3. 如果 g、h 属于 G,则复合φgh:X → X满足:φgh(x) = φh(φg(x)) (φgh的意思是,gh在G中计算的结果,gh∈G,gh也对应一个映射的,这个映射记为φgh)
同样类似可以定义G acts on X on the left,唯一不同之处是第3点:
3.如果 g、h 属于 G,则复合φgh:X → X满足:φgh(x) = φg(φh(x))
以此为前提,可以定义某个action is transitive:action φ的一个可选性质。
需要满足:如果对于属于 X 的每对 x、y 都存在有一个 g ∈ G,该g对应的动作φ满足 y = φ(x),称该g对应的动作φ为transitive的。
31.对于群G,设满足G acts on X的关系, the orbit of x∈X under G
:是一个X的子集,其中元素这样生成的,对于某个特定的X中的元素x,
任意取一个G中的元素g,g对应的action φ作用在x上得到的所有结果,这个结果组成的集合就是orbit。
具体定义:G ∗ x = {φg(x) | g ∈ G} , 记为G ∗ x
对于魔方群G,X指的是魔方上的绝对位置,位置当作元素,这样的集合orbit其实可以分成两个集合V,E,两个块的绝对位置的集合
这两个集合V,E仍然分别满足定义G ∗ x = {φg(x) | g ∈ G},
也就是仍然满足V,E中的元素经过φg映射后,仍然分别在V,E集合里面。
32.对于群G,集合X,设满足G acts on X的关系,x是X中的一个元素,stablizer:是一个G中元素的集合G2,G2里面的任意元素g,
g需要满足条件是:φg作用在x后,结果仍然是x。
具体定义:stabG (x) = Gx = {g ∈ G | φg (x) = x} , 记为stabG (x) 或 Gx
33.对于群G,集合X这时取为G本身,即X=G,假设满足G acts on X的关系,G acts on X的关系中函数φ给出了固定的定义是 g ∗ x ∗ g−1
,centralizer of x in G:是一个G中元素的集合G2,首先我们知道stabG (x) = {g ∈ G | g ∗ x = x ∗ g},这个集合
stabG (x)就是我们的结果G2,记为CG(x),CG(x)=stabG (x)。
34.对于魔方群G,g是G的元素,H集合={1,D,D^2,D^3} left coset of H:是一个作用左乘结果的集合,g左乘H中全体元素的结果,
这些结果的集合就是left coset of H , 记为gH。
35.subset : 子集合
36.对于群G,H是G的子群,g是G的元素, left coset of H in G: 是一个G的子集, 形式是这样的g*H,或写成gH,换句话说,就是
选定g元素后,g左乘H中全体元素得到的结果,这些结果的集合就是 left coset of H in G。
全体的 left coset of H in G集合(每个不同之处在于g的选取),再拼成的一个大集合,记为G/H。
类似的,全体的 left coset of H in G集合(每个不同之处在于g的选取),再拼成的一个大集合,记为G\H。左右斜杠不同
37.对于群G,H是G的子群,拉格朗日定理:描述left coset of H in G集合的元素数量,直接可以用G的数量,H的数量计算出来。
38.对于群G,H是G的子群,C是一个G的子集a left coset of H in G, g是G中的元素
coset representative of C:是群G中的一个元素g,g满足:C= g * H。 其实就是left coset of H in G定义中选取的某个g元素。
全体 coset representatives,也可以称作全体coset representatives of G/H :是一个G的子集,
里面的元素比如有m个的话:x1,x2,...,xm , 这m个元素需要满足:
G/H = {x1*H,x2*H,...,xm*H} , 还需要满足:x1*H , x2*H ,..., xm*H 这m个G的子集是互不相交的。
39.定理5.11.2: 全体coset representatives of G/H 可以构造出完整的群G。G = U(s∈S) s*H , 即一个并集,“每一个集合”是
全体 coset representatives 某一项xk,xk右乘集合H得到的所有结果,这些所有结果的集合就是上面并集里的“每一个集合”。
40.对于群G1,群G2,映射f:G1→G2,*₁是群G1的运算,*₂是群G2的运算,f是 homomorphism 同态,俗称“保持运算”:映射f的一种可选性质,
描述是G1和G2之间的一种关系,
对于任意a,b∈ G1 , G1和G2需要满足:f(a *₁ b) = f(a) *₂ F(b) 。 注意:记号·和“并列写法”也可以代表* 。
41.对于群G1,群G2,映射f:G1→G2,f满足homomorphism, image of f:是群G2的一个子群 ,
具体定义:f (G1 ) = {g ∈ G2 | g = f (x), for some x ∈ G1 },换句话说,元素形式是g∈ G2,
需要满足:能找到至少一个x ∈ G1 ,x通过映射f映射后是g。
, 记为im(f) 。
42.对于群G1,群G2 , G1 embeds(or injects) into G2 单射:是G1和G2之间的一种关系,需要满足:能找到一个映射f:G1→ G2, 映射f是单射的。
也就是相同结果推相同原像。
43.对于群G1,群G2,映射f:G1→G2,f满足homomorphism, isomorphism 同构:f的一种可选性质,f需要满足:映射f是双射的。
以此为前提,isomorphic:G1和G2的一种关系,满足f是isomorphism的, 记为G1≃G2。
以此为前提,如果G1=G2,automorphism 自同构:f的一种可选性质,描述G1和G2的一种关系。
44.引理9.2.1:描述了G acts on X ↔ 存在同态的映射f, f满足:是一个这样类型的映射G→S×(这个集合指的是X中的元素的所有排列的集合,
每一个排列可以用一个向量来表示), 然后具体定义是将G中的任意元素g,映射到φg
(φg就是一个向量,一个排列,比如(1,2,3),作用在某个X上,比如2,就是将2变成了3,也是X中的元素)
(这个φg是一个X→X类型的映射,作用到X里元素结果封闭在X里)
45. 对于群G,集合X,设满足G acts on X×X − ∆的关系,(X×X − ∆)整体是一个集合, ∆具体定义是∆ = {(x, x) | x ∈ X} 即diagonal对角的二维的集合,
换句话说就是每一个分量都相同的二维的向量
,doubly transitive:
G和 (二维X集合 - 对角集合)之间的一种关系,而且附加了可选性质transitive。
46.对于群G,集合X,设满足G acts on X的关系 , k-tuply transitive:是关系action(关系action,
具体是指G和X需要满足的几个条件形成的一个总的命题)的一种可选性质。需要满足:
对于向量A(x1,x2,...,xk) 和 向量B(y1,y2,...,yk) , A和B中的每一个分量都来自集合X,
向量A都满足:A中每个分量都是互不相同的,换句话说就是xi≠xj
向量B同样:B中每个分量都是互不相同的,换句话说就是yi≠yj
A和B还有一点命题需要满足:对于每一个i,1<=i<=k,都存在一个群G中的元素g,由于满足假设“G acts on X”这个关系,每个g存在映射φg,
而这个φg需要满足:yi = φg(xi),换句话说就是,可以将A中的每个分量映射到B中的对应位置的分量,
比如A第1位x1映射到第一位y1,并且可以同时把x2映射到第一位y2,...,一直到 把xk映射到第一位yk。所以看起来条件非常苛刻。
47.1.对于集合Cn={0,1,...,n-1},整数n>1,集合Cn满足群的定义, cyclic group of order n 循环群:是一个群 ,
群的第一运算定义为“两元素相加,再模n的结果” 也记为Z/nZ。
47.4阶循环群,记为C4。对于魔方群G,R是魔方群G中的一个元素, 有一个引理: C4 ≃ H , 这里H是<R>,换句话说,H是由集合{R}生成的置换群
(也就是说集合{R}生成的每一个元素都是一个置换,比如对于魔方群就是一个54项的向量,54项向量→54项向量的一个映射)。
48.对于群G1,群G2,映射f:G1→G2,f满足homomorphism,而且f满足isomorphism,且G1=G2,f具备性质automorphism,f的automorphism性质是,
inner 内同构 : automorphism性质的进一步的一种可选性质,对于群G1,g是群G1的元素,h是G1中的已选定的元素,
automorphism需要满足:f映射满足:f是这种形式的:Ch(g) = h · g · h^−1 , g ∈ G.
以此为前提,Aut(G):是全体的automorphism,换句话说,是一个集合,集合里面元素是automorphism
(通常用对象f来代表这样的automorphism性质,因为首先要有映射,才有自同构的性质的)。
以此为前提,Inn(G):是全体的automorphism,这些automorphism需要满足:具备inner性质 。具体定义:Inn(G):={f ∈ Aut(G) | f = ch , some h ∈ G}
换句话说,就是首先是全体的automorphism, 后面的条件说的是,存在至少一个h,h是G中的元素,f需要满足:f等于Ch(换句话说,就是f能写成Ch的形式,也就是具备inner性质)。
以此为前提,可以定义outer:automorphism的一种可选性质 , 不是inner的automorphism,就称作automorphism具备性质outer。
49.引理9.3.2,an inner automorphism must ‘preserve the cycle structure’ 内自同构“保持循环结构” :对于内自同构的映射f,
引理描述了一组不相交的循环(比如(1,2,4,3)这样是一个循环,是一个映射)的乘积A,经过f映射后,得到的结果仍然是不相交的循环的乘积B。
50.对于群G1,群G2,映射f:G1→G2,f满足homomorphism ,e₂是G2的单位元, the kernal of f 核:是群G1的一个子集,
具体定义: kernal(f) = {g ∈ G1 | f(g) = e₂ } 换句话说,g需要满足:经过f映射后,结果是G2中的单位元。
51.对于群G1,群G2,映射f,f满足homomorphism,引理9.4.2:描述1.单射与kernal的互推关系,
2.对于G1中任意元素x,对于kernal(f)中的任意元素g, 则=> , (x^-1·g·x)也是kernal(f)中的元素
52.对于群G,H是群G的子群, normal 正态or正定:子群H的一个可选性质,需要满足:g是G中任意的元素, (g^-1)·H·g=H
(注意:这里 (g^-1)·H写法是left coset of H的意思,((g^-1)·H)·g同样类似的理解成right coset of ((g^-1)·H))
换句话说,就是对于任意g∈ G, 任意h∈ H , (g^-1)·H·g 集合 = H集合。
换句话说,往元素的角度来看,就是任意g∈ G, 任意h∈ H, (g^-1)·h·g ∈ H
,称作H is a normal subgroup of G, 记为H◃G
53.trivial group: 只包含单位元e的群,通常称作平凡群。
54.对于群G1,群G2,映射f,f满足homomorphism, 引理9.4.3:描述了kernal(f) is a normal subgroup of G1。
55.sgn:是一个Sn到正负1集合的映射,Sn → {+1,-1},具体定义: Sn中元素s排列是even时,结果为1;s排列是odd时,结果为-1
56.An:是一个Sn的子集,具体定义就是ker(sgn), An = ker(sgn) ⊂ Sn
57.9.4.2节内容与“不能用根式求解5次或更高次的多项式”有莫大关系,但是没有深入讲。
57.对于An,n满足n>=5,H是An的一个子群,满足H◃An, 引理9.4.1:H只能是这两个集合:H={1} or H=An。 换句话说,H不能是非平凡的。
58.对于排列群Sn,H是Sn的子群,H由某个集合I里面元素生成,集合I满足:I里面元素是的Sn中的全体的3循环的元素(换句话说,就是比如元素g^3=g,这样的全体g构成了I集合),
命题9.4.1: 如果前面这些假设成立,则=>,sgn是Sn→{+1,-1}的映射,H=An 换句话说,H=An=ker(sgn) ⊂ Sn ,H集合就是An。
(和“3循环”有莫大的联系,魔方群定义的重要关键定理。)
59.对于群G,群H,满足H◃G, quotient group of G by H: the coset space G/H with 二元运算定义为 aH·bH:=(ab)H,
(aH)^-1 = a^-1H。换句话说,是一个自定义的空间A(也是一个集合),A里面的元素是gH这样的集合,其中g是G的元素,对于任意两个A中的元素,
比如aH,bH, 是两个集合来的,他们之间定义第一个运算·为 aH·bH:=(ab)H。
可以证明这样的A集合,加上自定义的这个运算·,A是满足可选性质“A是一个群”的,此处没证明。
A群的单位元就是trivial coset H, 也就是e为G的单位元,eH这个元素(实际上是一个集合)。
A群记为 the quotient group of G by H 商群, 也可以记为"G mod H",也可以记为“factor group”
60.对于群G, abelianiation of G:是一个商群quotient group of G by G'商群, 记为Gab = G/G', 其中G' = [G,G]。
61.对于群G,proper subgroup:是一个G的子群A的一个可选性质,A需要满足:不是整个群,即不是G本身。
62.对于群G,a simple group:是群G的一个可选性质,群G需要满足:
{任意群G的子群H,H满足H◃G 且 H不等于G本身 ,则=>, H等于{1},{1}恰巧可以称为trivial subgroup }
63.对于群G1,群G2,映射f:G1→G2,f满足homomorphism,定理9.5.1 First isomorphism theory 第一同构定理 :
满足前面的假设条件的话,则=>,G1/ker(f) is isomorphic to(同构于) f(G1), 这里f(G1)指的是G1全体元素通过映射f后得到的结果元素的全体。
64.对于群G,群H,N都是群G的子群,N满足:N是normal正定的,定理9.5.2 Second isomorphism theory 第二同构定理 :
满足前面的假设条件的话,则=>,有两个结论:
1. (H ∩ N)这个交集A满足:A is normal in H
2. 存在一个isomorphism同构f,f满足:
H/(H∩N) ≃ NH/N
这里NH指的是一个集合B,B满足:B中的任意个元素,是这样生成的:由N中任意元素和H中任意元素通过G中的第一运算*,组合计算出来的。
NH举例:
假设我们有一个群 G,其中的元素由整数模 6 的剩余类表示。我们定义两个子群:
H = {0, 2, 4},包含模 6 余数为 0、2 和 4 的整数。
N = {0, 3},包含模 6 余数为 0 和 3 的整数。
现在我们来找到 H⋅K。
首先,我们按照群运算(加法)将 H 和 N 的元素进行组合:
H + N = {0 + 0, 0 + 3, 2 + 0, 2 + 3, 4 + 0, 4 + 3} = {0, 3, 2, 5, 4, 1}
所以知道HN = NH = {0, 3, 2, 5, 4, 1} = {0, 1, 2, 3, 4, 5}
65.对于群G,群N1,N2都是群G的子群,N1和N2满足:N1 ⊂ N2 ,且N1 is normal正定 ,且N2 is normal正定,定理9.5.3 Third isomorphism theory 第三同构定理 :
满足前面的假设条件的话,则=>,有两个结论:
1. N2/N1 is normal in G/N1 . (那前提条件肯定满足: N2/N1 是 G/N1 的子群,这个为什么呢?)
2.存在一个isomorphism同构f,f满足:
(G/N1) / (N2/N1) ≃ G/N2 (感觉像一个除法的类似的东西)
66.对于群H,H1和H2是群H的子群, the direct product of H1 with H2 直积,也称为笛卡尔积:是一个群G,群G的元素是一个个的二项向量,记为G= H1 × H2,
G需要满足:
1.G的元素是一个个这样的二项向量(x,y), 换句话说,x是H1的元素,y时H2的元素。
2.G的第一运算定义为:(x1,y1) · (x2,y2)= (x1·x2 , y1·y2) , 这里乘法符号“·”出现了3次,分别代表三个群的第一运算:G,H1,H2。
67.定理9.6.1 First Fundamental Theorem of Rubik’s Cube theory 魔方第一基本定理:魔方的一个状态是由以下性质来决定的:
1.边块的排列
2.角块的排列
3.中心块的排列
4.全体边块的翻转情况(相对于还原状态的时候)
4.全体角块的翻转情况(相对于还原状态的时候)
68.9.9.3节中,
H,the slice group :是一个群,由〈MR , MF , MU 〉也就是由魔方群中的3个元素(操作),这3个元素
是魔方中的3个中间层滑动 the middle slice move。
X :是一个魔方面的集合,X里面的元素是魔方中的48个面,不包含6个中心面,所以是54-6=48
G :魔方群(可推断出,为SX的一个子群?54反而是48的子群吗?)。
V :是一个魔方面的集合,V里面的元素是魔方中的角块的全体面。
E :是一个魔方面的集合,E里面的元素是魔方中的边块的全体面。
C :是一个魔方面的集合,C里面的元素是魔方中的中心块的全体面。
F :是一个群(可推断出,为SX的一个子群),由魔方群G中的某些元素gi生成,这些元素gi满足:不会重新排列角块和边块的位置,
但可能会改变角块或边块的角度。
SX : 是一个symmetric对称群,是X集合上的对称群。
SV : 是一个symmetric对称群(可推断出,为SX的一个子群),是V集合上的对称群。
SE : 是一个symmetric对称群(可推断出,为SX的一个子群),是E集合上的对称群。
GV = SV ∩ G
GE = SE ∩ G
FV = SV ∩ F
FE = SE ∩ F
69.C3 4(这里表示C4的4上面有个3):C4的3次笛卡尔积,也就是说一个3项的向量。
Cn d : the group of n-vectors with coefficients in Cd 。
70.对于群G,群H1,H2都是群G的任意的子群 semi-direct product of H1 by H2 半直积 第一种定义也称internal version 内部半直积:群G的一种可选性质,
记为G = H1 ⋊ H2
群G需要满足:存在G的任意2个子群H1,H2,需要满足3个命题:
1.G = H1 · H2 (也就是G中的任意元素g,g满足:存在H1中元素h1,存在H2中元素h2,g满足:g=h1·h2)
2.H1和H2共同的元素,只有单位元1(1∈G)
3.H1◃G (H1 is normal in G)
71.假设存在homomorphism 同态 φ: H2 → Aut(H1 ),对于群H1,群H2,当然可以笛卡尔积成H1×H2(元素为二项向量的集合),我们定义集合H1×H2的第一运算*1为:
(x1,y1 )· 注意:这个乘号"·"是集合H1×H2中的乘法运算*1,这里也写成"·" (x2,y2) = (x1 · 注意:这个乘号是集合H1中的乘法运算 φ(y1)(x2) , y1 · 注意:这个乘号是集合H2中的乘法运算 y2 )
去掉“注意”:
(x1,y1 ) · (x2,y2) = (x1·φ(y1)(x2) , y1·y2)
注意上一行的φ(y1)(x2),先看整体φ(y1),是将H2中元素,映射成一个“自同构的映射”(所以结果还是一个映射,类型是:H1→H1 ,还需要等待参数),等待的参数就是这个x2了。
,半直积 第二种定义 the (external) semi-direct product:是一个笛卡尔积H1×H2配合运算*1而得到的一个群(满足群需要证明)
,记为H1 ⋊ φH2 。
72.内外半直击是需要证明等价的,看书籍[R]7.22-7.23
73.the generalized symmetric group 广义对称群:?看P194
74.a monomial matrix 单项式矩阵:?看P194
75.对于群G1,群G2,X2是一个有限的集合,X2的元素个数为m,G2和X2满足关系:G2 acts on X2,
wreath product of G1,G2:是一个群,是群G1^(X2) 和 群G2的半直积(用半直积的第二种定义理解会容易一点)得到的那个群,
具体定义为:G1 wr G2 := G1^(X2) ⋊ G2 , 记为G1 wr G2。
这里G1^(X2)是一个记号:G1的对G1的直积m次的结果(是一个m项向量为元素的群)。
以此为前提,the base of wreath product: 是 G1^(X2) ⋊ G2的一个特定子群 G1^(X2) , 记为base of wreath product。
这里是要证明的,为什么G1^(X2)是 G1^(X2) ⋊ G2 的子群?目前先理解成,G1^(X2) 是 G1^(X2) ⋊ G2 (即G1^(X2) × G2,这里笛卡尔积的结果是一个向量,有两个分量),
G1^(X2)看成是G1^(X2) × G2中的第一个分量,第二个分量为0。
/----/
举例:以实数R,还有排列群Sn来举例:
(P195这里r是指acts on里面说的那个X→X的映射,r*?这里的"r*"写在左边的意思是:将该映射r作用到?元素上。)
先讲结论,R wr Sn 的结果是按照定义,是群R^(X2) 和 群Sn的半直积得到的那个群, 这里结论是R wr Sn = Rn × Sn
Rn: 是一个群,元素是一个个n项分量的向量。群Rn的第一运算是加法,加法具体定义:将向量的每个分量分别相加。
Sn acts on Rn , 其中Sn的某个元素s1,可以对应产生一个类型为Rn→ Rn的映射,
具体定义为:因为s1是一个排列,将排列s1作用在Rn中某个元素r1,作用效果是将Rn中的n个分量进行排列。
举例:n=3时,r1=(1,2,3),s1={1,3,2},s1的映射作用到r1的结果就是换了一下3个分量的位置,得到(3,1,2)
以此为前提,讨论这样的s1对应的这个映射s1_reflect,是满足加法的这个运算律的,思考一下问什么:
s1_reflct(x1+ 注意这里加法是R的加法 y1 , x2+y2 , .., xn+yn) = s1_reflct(x1,x2,...,xn) + 注意这里加法是Rn的第一运算加法 s1_reflct(y1,y2,...,yn)
s1_reflct(x1+y1 , x2+y2 , .., xn+yn) = s1_reflct(x1,x2,...,xn) + s1_reflct(y1,y2,...,yn)
X2:对应这里例子,就是{1,2,3,...,n}这个有限的集合。
Rn × Sn 记为 G:也是一个群(需要证明的),第一运算乘法·定义为:首先类型是G → G → G
具体定义为:(v1,p1)·(v2,p2) = (v1+p1* 注意:这里的*是p1在“Sn acts on Rn”定义的第一条件中对应的那个映射类型是Rn→Rn v2 , p1·p2) , 其中v1∈Rn , p1∈Sn
具体定义为:(v1,p1)·(v2,p2) = (v1+p1*v2 , p1·p2) , 其中v1,v2∈Rn , p1,p2∈Sn
这个群G,就记为当前例子中的R wr Sn , 其中Rn就记为base
76.illegal Rubik's Cube group: 合法操作(RLUDFB)+不合法的操作(拆开魔方重组,但是不包括撕掉贴纸!)
77.S(n,m) :是一个矩阵, n*n的矩阵,其中的每一项是群Cm中的元素。
78.f* : P194 的 (9.2)里面定义,这里没有记录详细定义.
79.棱块_位置的排序:UF,UR,UB,UL, LF,FR,RB,BL, DF,DR,DB,DL (这里每一项指的是块,不是面)
棱块的正方向是这12个,没有顺序,也就是选定这些面为正方向,注意这里字母顺序很重要,比如UF≠FU,两个面是不一样的,虽然在同一个棱块上 ,UF是在U面上的棱块的F面:
UF,UR, FD,FR, RB,RD, DL,DB, LF,LU, BL,BU
80.角块_位置的排序:FDR,DBR,FUR,RUB, FUL,LUB,LDB,FLD (这里每一项指的是块,不是面)
棱块的正方向是这8个,没有顺序,DFR指的是正方向在D面
DFR,DRB,DBL,DLF, UFR,URB,UBL,ULF
81.σ : 是一个同态映射,类型是:H→ SE , 换句话说,针对全体魔方块的变换,只取出了对棱块的变换影响,所以能从H中的某个元素,映射到,SE中的元素。
至于为什么满足同态?未证明
82.ρ : 是一个同态映射,类型是:H→ SV , 换句话说,针对全体魔方块的变换,只取出了对角块的变换影响,所以能从H中的某个元素,映射到,SV中的元素。
至于为什么满足同态?未证明
83.
进度:P220/329
下一个里程碑218开始研究可解的魔方状态,里面也有若干定理--no
224魔方第二基本定理已经可以开始做lean了
后面还有平方群的定理233-250 --no
跳过14章太难了 --no
290有我们想要证明的52步算法,多种魔方解法284-
188出现了质疑,跳过了。--no
200跳过了很多决策,字相关的内容。--no
α (Alpha), β (Beta), γ (Gamma), δ (Delta), ε (Epsilon), ζ (Zeta), η (Eta),
θ (Theta), ι (Iota), κ (Kappa), λ (Lambda), μ (Mu), ν (Nu), ξ (Xi), ο (Omicron),
π (Pi), ρ (Rho), σ (Sigma), τ (Tau), υ (Upsilon), φ (Phi), χ (Chi), ψ (Psi), ω (Omega)
/------------------/
视频:通过魔方上的群结构了解魔方的性质
1.魔方群共有8!*12!*2^12*3^8个元素 , 其中可还原的只有1/12 , 也就是8!*12!*2^10*3^7。
2.E:全体棱块
3.V:全体角块
4.对于某个棱块e,正方向:是人为一开始任选的面的那个坐标方向,换句话说,在还原状态中,e任选一个面,这个面的贴纸指向的方向,就是正方向。
通常正方向记为0,第二方向记为1
5.对于某个角块v,正方向:是人为一开始任选的面的那个坐标方向,换句话说,在还原状态中,v任选一个面,这个面的贴纸指向的方向,就是正方向。
通常正方向记为0,第二方向记为1(逆时针旋转120度),第二方向记为2(逆时针旋转120*2=240度)
6.魔方群G:是一个由变换生成的置换群,<R,L,F,B,U,D>,
比如,置换群中的元素C是由变换复合运算得到的元素,C可以看成变换,也可以看成一个状态。
对于元素x∈G,y∈G,xy:是魔方群G中元素的复合,(在魔方操作的角度看,xy初始定义为:先操作x,再操作y,所以操作xy复合为什么等于两次分步操作,其实是要证明的)
7. H:是全体魔方状态的集合,不同于魔方群G,群H包括不可还原和可还原的状态。(换句话说,可以拆开魔方,但是不能撕贴纸!)
8.SE :是一个群,里面的元素是12排列代表的向量,代表棱块的位置变换的全体, 由于E代表棱块一共12个,所以SE等价于S12。
9.SV :是一个群,里面的元素是8排列代表的向量,代表角块的位置变换的全体, 由于V代表棱块一共8个,所以SV等价于S8。
10.σ : 是一个同态映射,类型是:H→ SE , 换句话说,针对全体魔方块的变换,只取出了对棱块的变换影响,所以能从H中的某个元素,映射到,SE中的元素。
至于为什么满足同态?未证明
11.ρ : 是一个同态映射,类型是:H→ SV , 换句话说,针对全体魔方块的变换,只取出了对角块的变换影响,所以能从H中的某个元素,映射到,SV中的元素。
至于为什么满足同态?未证明
12.2.魔方在视频中的面的颜色:
上面:白U,下面:黄D
前面:蓝F, 后面:绿B
左面:红L,右面:橙R
12.1.棱块的排序:UF,UR,UB,UL, LF,FR,RB,BL, DF,DR,DB,DL
12. w : 是一个映射,(但是不满足同态性质),类型是:H→ C2^(12), w(g)第i个分量wi表示:
在第i位置的原坐标下,按逆时针计算的方向数为Fi,这个棱块x,经过某{F,B,L,R,U,D}某复合一个操作后,到达了第j位置
在新的第j位置的坐标下,按顺时针计算的方向数Fj,则这两个数之间的关系是:(Fi + wi) 再mod 3 , 就等于 Fj。也就是Fi+wi=Fj (mod 2环境下)
换句话说wi是一个过程量,原位置下计数为Fi,新位置下计数为(Fi+wi) (mod2)。
换句话说,我在未变换前的方向数知道了Fi,然后查表找到这个变换前位置的分量wi,就知道了变换后原方块在新位置的方向数是多少了。
13.1.角块的排序:FRD,RDB, UFR,URB, UFL,ULB, LBD,FLD
13. v : 是一个映射,(但是不满足同态性质),类型是:H→ C3^(8) , v(g)第i个分量vi表示:
在第i位置的原坐标下,按逆时针计算的方向数为Fi,这个棱块x,经过某{F,B,L,R,U,D}某复合一个操作后,到达了第j位置
在新的第j位置的坐标下,按顺时针计算的方向数Fj,则这两个数之间的关系是:(Fi + vi) 再mod 3 , 就等于 Fj。也就是Fi+vi=Fj (mod 3环境下)
换句话说vi是一个过程量,原位置下计数为Fi,新位置下计数为(Fi+vi) (mod3)。
换句话说,我在未变换前的方向数知道了Fi,然后查表找到这个变换前位置的分量vi,就知道了变换后原方块在新位置的方向数是多少了。
14. 17.55min的w和v表怎么看的??这个要看原书P.119
15.棱块_位置的排序:UF,UR,UB,UL, LF,FR,RB,BL, DF,DR,DB,DL (这里每一项指的是块,不是面)
棱块的正方向是这12个,没有顺序,也就是选定这些面为正方向,注意这里字母顺序很重要,比如UF≠FU,两个面是不一样的,虽然在同一个棱块上 ,UF是在U面上的棱块的F面:
UF,UR, FD,FR, RB,RD, DL,DB, LF,LU, BL,BU
16.角块_位置的排序:FDR,DBR,FUR,RUB, FUL,LUB,LDB,FLD (这里每一项指的是块,不是面)
棱块的正方向是这8个,没有顺序,DFR指的是正方向在D面
DFR,DRB,DBL,DLF, UFR,URB,UBL,ULF
17.w和v的具体作用表,会根据1.正方向的选定而不同,2.还有旋转顺时针还是逆时针。这两个要素而变化,所以只需要
合理就行,第i位意义就是:操作前,正号的位置是A,经过g映射(操作)后,第i位的正号得到位置是B,第i位的数字意思是,
A经过i次旋转后会得到B。就这么简单,瞄准的是第i位。
18.
目前在第一次粗略看的过程,能听懂一些
进度:25 min/45min
/------------------/
找出视频中定理出现的时间 和 书中定理的对应页数:
1. 18.21min 的命题1 ↔ P.223 Proposition 11.1.1
对于群H,g,h是H的元素,
v : 不是同态,代表方向 H→ C3^(8)
ρ : 是一个同态映射,代表位置 类型是:H→ SV
w : 不是同态,代表方向 H→ C2^(12)
σ : 是一个同态映射,代表位置 类型是:H→ SE
定义σ(g)(w) 和 ρ(g)(v) 这两个记号如下:
实际上都是接收一个H类型的参数g,然后得到一个12项的向量,这样的一个映射。
σ(g)(w): H→C2^12 := (w_σ(g)(1) , w_σ(g)(2) , ... , w_σ(g)(12) ) w的下标指的是w的第几个分量,比如σ(g)(1)这样计算出来的是一个整数来的
换句话说,就是σ(g)·w(x) , 还有一个x∈G参数没有传,σ(g)·作用在左边作用是重新排列w(x)的所有分量。
ρ(g)(v): H→C3^8 := (v_ρ(g)(1) , v_ρ(g)(2) , ... , v_ρ(g)(8) ) v的下标指的是w的第几个分量,比如ρ(g)(1)这样计算出来的是一个整数来的
换句话说,就是ρ(g)·v(x) , 还有一个x∈G参数没有传,ρ(g)·作用在左边作用是重新排列v(x)的所有分量。
(这里观察v_ρ(g)(1)就发现,其实v本身是没有确定的,需要再给个参数确定是哪个8项的向量,比如h=R,这样再传给
ρ(g)(v),写成ρ(g)(v)(h),就得到了这样的8项向量:(v(h)_ρ(g)(1) , v(h)_ρ(g)(2) , ... , v(h)_ρ(g)(8) ))
“类同态定理”:
则=> (→),
其实这里应该是一个定义,因为w(gh)实际定义就是作用g,再作用h后,得到的方向过程量。
w(gh) := w(g) + σ(g)^(-1)·w(h)
v(gh) := v(g) + ρ(g)^(-1)·v(h)
证明:(思路是一般化某个任意分量来做变化,是否成立。再推广到所有分量。)
已知g:{
方向过程量:w(g)= (p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12)
位置过程量:σ(g)
}
已知h:{
方向过程量:w(h)= (q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12)
位置过程量:σ(h)
}
1.先证明第一条公式:
对于某个状态Sta1:
方向绝对量:Sta1 = (j1,j2,j3,j4,j5,j6,j7,j8,j9,j10,j11,j12)
位置绝对量:(k1,k2,k3,k4,k5,k6,k7,k8,k9,k10,k11,k12)
1.经过g作用后:{
方向绝对量错误:(j1+p1,j2+p2,j3+p3,j4+p4,j5+p5,j6+p6,j7+p7,j8+p8,j9+p9,j10+p10,j11+p11,j12+p12)
方向过程量:Sta1 → (Sta1作用g以后) = w(g)
位置:σ(g)·(k1,k2,k3,k4,k5,k6,k7,k8,k9,k10,k11,k12)= ?
方向绝对量 : σ(g)·(j1+p1,j2+p2,j3+p3,j4+p4,j5+p5,j6+p6,j7+p7,j8+p8,j9+p9,j10+p10,j11+p11,j12+p12)
}
2.再经过h作用后:{
方向绝对量:σ(h)( σ(g)·(j1+p1,j2+p2,j3+p3,j4+p4,j5+p5,j6+p6,j7+p7,j8+p8,j9+p9,j10+p10,j11+p11,j12+p12) + (q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12) )
方向过程量:(Sta1作用g以后)→ (Sta1作用g以后,再作用h以后) = ?
位置:σ(h)·σ(g)·(k1,k2,k3,k4,k5,k6,k7,k8,k9,k10,k11,k12)= ?
}
小引理:绝对方向量A1 经过x→, 绝对方向量为A2, 和w(x)有什么关系,如何表达w(x):
σ(x)·(A1 + w(x)) = A2
所以,w(x) = (σ(x))^(-1)·A2 - A1
分析初始方向绝对量和最后2次作用后的方向绝对量,后者是按定义算出来的值。
(j1,j2,j3,j4,j5,j6,j7,j8,j9,j10,j11,j12) = "A1"
→
σ(h)( σ(g)·(j1+p1,j2+p2,j3+p3,j4+p4,j5+p5,j6+p6,j7+p7,j8+p8,j9+p9,j10+p10,j11+p11,j12+p12) + (q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12) )
= σ(h)·σ(g)·(j1+p1,j2+p2,j3+p3,j4+p4,j5+p5,j6+p6,j7+p7,j8+p8,j9+p9,j10+p10,j11+p11,j12+p12) + σ(h)·(q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12)
= "A2"
所以复合的方向过程量:
w(gh) := (σ(gh))^(-1)·A2 - A1 = (σ(g))^(-1)·σ(h)^(-1) · A2 - A1
= (j1+p1,j2+p2,j3+p3,j4+p4,j5+p5,j6+p6,j7+p7,j8+p8,j9+p9,j10+p10,j11+p11,j12+p12) +
(σ(g))^(-1)·(q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12) - (j1,j2,j3,j4,j5,j6,j7,j8,j9,j10,j11,j12)
= (p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12) + (σ(g))^(-1)·(q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12)
试着列举一下:
w(g) = (p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12)
σ(g)·w(h) = σ(g)·(q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12)
w(g) + σ(g)^(-1)·w(h) = (p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12) + (σ(g))^(-1)·(q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12)
举例说明:
g=F,h=R,
经过gh后,
已知:
因为g换位效果是:
{1,2,3,4,5,6,7,8}
{8,2,1,4,3,6,7,5}
因为h换位效果是:
{1,2,3,4,5,6,7,8}
{2,4,1,3,5,6,7,8}
gh复合换位:
{1,2,3,4,5,6,7,8}
{2,4,8,1,3,6,7,5}
v(g) = {2,0,1,0,2,0,0,1}
v(h) = {1,2,2,1,0,0,0,0}
-- 首先根据等式左边算一下,也就是根据定义算一下:
gh变换后绝对位置 =(0先经过g操作:加v(g),然后被ρ(g)作用) = {2,0,1,0,2,0,0,1} = {1,0,2,0,1,0,0,2}
=(经过h操作:加v(h),然后被ρ(h)作用) = {2,2,1,1,1,0,0,2} = {2,1,2,1,1,0,0,2}
v(gh) = (σ(gh))^(-1)·A2 - A1 = ?
这里A1 = 0, A2 = {2,1,2,1,1,0,0,2} ,
σ(gh) = {2,4,8,1,3,6,7,5} ,
σ(gh)^(-1) = {4,1,5,2,8,6,7,3}
v(gh) = {4,1,5,2,8,6,7,3} · {2,1,2,1,1,0,0,2} - 0
= {1,2,1,1,2,0,0,2}!!!对啦!!
-- 下面通过等式右边算一下:
σ(g)(v)(h)= σ(g)·v(h) = 就是按照g的换位来更改这些v(h)中的分量,
= {0,2,1,1,2,0,0,0}
v(g) + σ(g)(v)(h)= σ(g)·v(h) = {2,0,1,0,2,0,0,1} +
{0,2,1,1,2,0,0,0}
= {2,2,2,1,1,0,0,1}
(σ(g))^(-1)·v(h) = {2,2,0,1,0,0,0,1}
v(g) + (σ(g))^(-1)·v(h) = {2,0,1,0,2,0,0,1} +
{2,2,0,1,0,0,0,1}
= {1,2,1,1,2,0,0,2}!!!对啦!!
----------------------------
书中没看懂,看视频的吧,而且两者正方向定义不一样,理论形式也不一样,书里是逆排列,视频里是没有逆的排列。
2.21.57min关于命题1的延伸,P(r)这里没深究。应该不是我们必要懂的。
3. 23.15min 命题2
假设有映射l 类型是:H → (C2^12 ⋊ S12)×(C3^8 ⋊ S8) , 具体定义l(h):= (w(h),σ(h),v(h),ρ(h))
则=>:(这个太有用了吧,把广义魔方群同构都找到了)
l为群同构,也就是H ≃ (C2^12 ⋊ S12)×(C3^8 ⋊ S8)
4. 24.36min
重新定义下面这4个映射,原来是在H上定义,现在是在G上定义:
v : 不是同态 G→ C3^(8)
ρ : 是一个同态映射,类型是:G→ SV
w : 不是同态 G→ C2^(12)
σ : 是一个同态映射,类型是:G→ SE
则=>:
命题1在g,h∈G,的情况下,仍然成立,即:
w(gh) := w(g) + σ(g)^(-1)·w(h)
v(gh) := v(g) + ρ(g)^(-1)·v(h)
5. 24.40min ↔ 书中P.224-227
魔方第二基本定理:注意***,这里的正方向标记将使用TW算法的标记法。
对于∀g∈ H (也就是广义的魔方群,可以拆散魔方) ,g在这里代表任意的一个魔方状态
则=>:,以下两命题可以互推(↔)
{
g ∈ G (魔方群,可以通过6个基本操作生成的)
}
↔
{ 以下3个命题都成立
1.sgn(σ(g)) = sgn(ρ(g)) --(题外话:使用这个用来证明一个魔方不能单纯变化是:只交换一对角块位置,而棱块位置不变;
-- 也不能单纯变化是:只交换一对棱块位置,而角块位置不变)
2.∑(12在上 i=1) wi(g) = 0 (mod 2) -- 应用起来,可以解释魔方单纯这样变化是不可能的:只翻转一个棱块的方向;
3.∑(8在上 i=1) vi(g) = 0 (mod 3) -- 也不能单纯变化是:只翻转一个角块的方向,120 or 240都不行
}
证明:
已知集合{U,D,F,B,L,R},记为Actions={U,D,F,B,L,R}
左推右:比较简单,
{
1.符号相等:
1.任意g∈G,可以表示成g=X1X2...Xk, 这里X1到Xk都是集合{U,D,F,B,L,R}之一。
2.首先验证集合中单独6个元素满足sgn(σ(Xn)) = sgn(ρ(Xn)),这里略过(底层是因为因为4轮换?)。
3,sgn是同态映射,也就是具有“保持运算”的性质,所以任意复合的结果,sgn都不变。
4.sgn(σ(g)) = ∏(上k,下i=1)sgn(σ(Xi)) 由于g的定义,σ的同态性,sgn的同态性。
= ∏(上k,下i=1)sgn(ρ(Xi)) 由于集合中6个元素都满足sgn(σ(Xn)) = sgn(ρ(Xn))
= sgn(ρ(g)) 由于sgn的同态性,ρ的同态性,g的定义。
例如:
已知:sgn(σ(F)) = sgn(ρ(F)), sgn(σ(R)) = sgn(ρ(R))
则sgn(σ(R)σ(F)) = sgn(σ(R)) + sgn(σ(F)) 是由于sgn的同态性质
= sgn(ρ(R)) + sgn(ρ(F)) 由于已知等式
= sgn(ρ(R)ρ(F)) 是由于sgn的同态性质
2.棱块向量的各分量的和为0(模2):
做归纳法,对复合操作g所需的{U,D,F,B,L,R}中元素数量,记为l(g)作归纳:
1.l(g)=1 成立,因为根据查w表可知。
2.假设l(g)=k-1成立,也就是,假设g满足:可写成任意的n-1个复合,即:∀M_1∈Actions,∀M_2∈Actions,...,∀M_k-1∈Actions ,
即g=M_1M_2...M_k-1,则有:
∑(上12,下i=1)wi(M_1M_2...M_k-1) = 0(mod 2)
3.则l(g)=k,取g=X_1X_2...X_k,如何证明归纳成立?:
1.由假设,分别取M_1,M_2,...,M_k-1分别取为X_1,X_2,...,X_k-1,
可得到:∑(上12,下i=1)wi(X_1X_2...X_k-1) = 0(mod 2)
2.命题1已知: w(xy) := w(x) + σ(x)^(-1)·w(y) , 这里取x= X_1X_2...X_k-1 , y=Xk,
得到:w(xy) = w(g) = w(X_1X_2...X_k-1) + σ(X_1X_2...X_k-1)^(-1)·w(Xk)
3.将2中得到的等式左右取各分量的求和,仍然相等,
得到:∑(上12,下i=1)wi(xy) = w(g) = ∑(上12,下i=1)wi(X_1X_2...X_k-1) + ∑(上12,下i=1)(σ(X_1X_2...X_k-1)^(-1)·w(Xk))_i
4.小引理:因为X_1到X_k-1都满足σ(X_n)∈S12,σ是同态映射,即保持运算,因此σ(X_1)·σ(X_2)···σ(X_k-1) = σ(X_1X_2...X_k-1)
因为等式左边都是S12群中的元素,封闭性知等式左边∈ S12,则=>:, 等式右边σ(X_1X_2...X_k-1)∈ S12
5.观察3的等式右边加法的第二项: ∑(上12,下i=1)(σ(X_1X_2...X_k-1)^(-1)·w(Xk))_i ,
即:σ(X_1X_2...X_k-1)^(-1) 作用到 w(Xk) 以后 , 取所有分量求和。
因为 σ(X_1X_2...X_k-1)^(-1) 也是∈ S12, σ(X_1X_2...X_k-1)^(-1)作用到w(Xk)这个向量后,只是重新排列了各分量,求和是不变的,
因此得到:∑(上12,下i=1)(σ(X_1X_2...X_k-1)^(-1)·w(Xk))_i = ∑(上12,下i=1)(w(Xk))_i
以此为前提,因为Xk是Actions里面的单独一个元素,也就是归纳法l(g)=1的情况,因此∑(上12,下i=1)(w(Xk))_i = 0 (mod 2)
总结得到:∑(上12,下i=1)(σ(X_1X_2...X_k-1)^(-1)·w(Xk))_i = ∑(上12,下i=1)(w(Xk))_i = 0 (mod 2)
6.我们将3得到的等式:w(g) = ∑(上12,下i=1)wi(X_1X_2...X_k-1) + ∑(上12,下i=1)(σ(X_1X_2...X_k-1)^(-1)·w(Xk))_i
左右两边取模2,依然相等:
w(g) = ∑(上12,下i=1)wi(X_1X_2...X_k-1) + ∑(上12,下i=1)(σ(X_1X_2...X_k-1)^(-1)·w(Xk))_i (mod 2)
由1知道等式右边第1项:∑(上12,下i=1)wi(X_1X_2...X_k-1) = 0(mod 2)
由5知道等式右边第2项: ∑(上12,下i=1)(σ(X_1X_2...X_k-1)^(-1)·w(Xk))_i = 0 (mod 2)
因此w(g) = 0 (mod 2)
3.角块向量的各分量的和为0(模3)。基本和2类似的步骤,这里略过。
}
右推左:
(总体思路:)
{
魔方还原状态e ↔ g∈G,1.σ(g)=id,2.ρ(g)=id,3.w(g)={0,0,...,0},4.v(g)={0,0,...,0}
分情况讨论,这里分情况讨论并没有直接解决问题,而是分情况讨论的过程中会得到一些很有用的结论,
换句话说,每一个分类讨论其实就是一个lemma:(1.只满足条件1+2+3;2.只满足条件1+2+4;3.只满足条件3+4)
1.对于g∈H,对于棱块和角块位置不变,即σ(g)=id,ρ(g)=id,且w(g)={0,0,...,0}全零时的情况。
换句话说,也就是全体位置都不变,棱块方向都不变时,换句话说只有可能是部分角块方向变了
即已满足1,2,3,如果再给假设条件(3)的话,则=>: 满足g∈ G ,证明如下:
0.修改目标命题:
要证g∈ G,只需证新的目标命题:
“此时的状态,都能变换回还原状态”
给出变换的算法步骤,(或者弱一点,证明这样的变换存在即可)。
(题外话:TW算法的步骤是,先变十字,然后是的v(g)全零,然后调整角块的位置保证3个轨道,然后调整棱块的位置保证2个轨道)
1.小引理Lemma1:g1 = (R'D^2RB'U^2B)^2 ∈ G ,
即R' D D R B' U U B R' D D R B' U U B
g1的效果如下:
则=>: g1可以保持UFR和DBL以外的块的方向和位置,只改变UFR和DBL的方向,
分别是UFR的方向数+2,DBL的方向数+1。
2.以下会介绍一个完整的步骤,证明该状态g,可以通过Actions的复合得到(换句话说,就是能还原回初始魔方):
1.首先用小引理Lemma1中的g1还原F面的4个角块的方向数为0:
1.(涉及F,g1)向UFR位置移入其他F面的块,比如UFL:这一步通过F操作即可,同样类似1的操作n次g1后,方向数+2n后必然符合mod3 = 0 。完成F面1个方向数还原。然后执行F'。
2.(涉及F,g1)向UFR位置移入其他F面的块,比如DFL:这一步通过F^2操作即可,同样类似1的操作n次g1后,方向数+2n后必然符合mod3 = 0 。完成F面2个方向数还原。然后执行(F^2)⁻¹。
3.(涉及F,g1)向UFR位置移入其他F面的块,比如DFR:这一步通过F'操作即可,同样类似1的操作n次g1后,方向数+2n后必然符合mod3 = 0 。完成F面3个方向数还原。然后执行F。
(涉及F)注意,这里F面的第4个方向数,即UFR位置,还没处理,先留着。
3.然后上一步的还没处理第4个方向数X就起作用了,因为下面要处理的是B面的4个方向数,通过g1和B的复合操作可以将B面的一个个方向数还原为0,具体步骤:
1.(涉及B,g1)向DBL位置移入其他B面的块,比如UBL:这一步通过B操作即可,同样类似1的操作n次g1后,方向数+n后必然符合mod3 = 0 。因此B面第1个方向数还原。然后操作B'.
2.(涉及B,g1)向DBL位置移入其他B面的块,比如UBR:这一步通过B^2操作即可,同样类似1的操作n次g1后,方向数+n后必然符合mod3 = 0 。因此B面第2个方向数还原。然后操作(B^2)⁻¹.
3.(涉及B,g1)向DBL位置移入其他B面的块,比如DBR:这一步通过B'操作即可,同样类似1的操作n次g1后,方向数+n后必然符合mod3 = 0 。因此B面第3个方向数还原。然后操作B.
4.小引理:假设角块的方向数求和后,模3为0,假设8个角块的方向数中,有7个方向数被以上步骤还原为0以后,则=>,第8个角块的方向数也还原成0 ,为什么呢?:
由于前7个方向数还原操作后,7个方向数之和模3不会变,还是0,这是因为:
还原操作涉及到的只有{F,B和g1},由于这3者之一,任意取一个记为X,都满足∑(8 i=1)v(X)_i=0 (mod 3):
F和B通过查v表可知,
而g1则只需实际操作一次后,看到只修改了全体角块中2个角块的方向数,而且方向数一个+1,一个+2,所以也满足求和模3为0。
换句话说,初始状态经过上述{F,B和g1}任意操作后,增加v(X)的各个分量,因为上述已知求和都是mod 3为0,增加这些分量以后再求和也是mod 3为0。
5.观察现在还没还原的F面和B面中的角块的方向数,发现各剩下一个,分别在UFR和DBL位置,然后执行n次g1,则3号角块方向数+2n后必然符合mod3 = 0,详细步骤:
(涉及g1)执行g1以后,其中3号方向数还原为0了,再根据小引理4,得到第8个角块也会还原为0。
4.至此,已将8个角块的方向数全部还原为0,即v(g)={0,0,...,0}。而且w(g)还是全零。(是的,因为过程中操作g1,F,B不改变棱块的方向数。)
5.1. 这里整个分类讨论1其实可以记成一个小引理:假设有状态g∈H,假设σ(g)=id,ρ(g)=id,且∑(8在上 i=1) vi(g) = 0 (mod 3) , 则=>,
g能通过有限次作用G中的元素,得到新的性质:v(g)={0,0,...,0}。
5.1.2.lemma5: 其实引理可以再一般化一点:假设有状态g∈H,且∑(8在上 i=1) vi(g) = 0 (mod 3) , 则=>,
g能通过有限次作用G中的元素,得到新的性质:v(g)={0,0,...,0}。而且不改变棱块的方向数。
5.因此假设中情况:σ(g)=id,ρ(g)=id,且w(g)={0,0,...,0},
再加上上述步骤,记为C1,C1的操作结果:v(g)={0,0,...,0} , 就得到了魔方群中的一个元素状态e,
而上述步骤每个操作都是G中的元素,其复合C1也是元素,具有逆元C1^(-1)
也就是g是e可以通过作用Actions集合的复合C1^(-1)得到。
换句话说g可以表示成G中元素e·C1^(-1),根据封闭性,还是在群G中,
因此当前假设的情况g∈G成立。
2.对于棱块和角块位置不变,即σ(g)=id,ρ(g)=id,且v(g)={0,0,...,0}全零时的情况。且满足(1),(2),(3)的话,
换句话说,只有可能没有满足还原的条件是棱块的方向数w(g)。
则=>: 满足g∈ G,
证明如下:
1.可以用到这个小引理Lemma2:g2 = LFR'F'L'U^2RURU^−1R^2U^2R, 则=>:
g2可以保持其他块的方向和位置,只改变UF和UR的方向,分别是UF的方向+1,UR的方向的方向+1。
2.也可能用到这个小引理lemma3: g_3= U R L' F L L F R L B B L L U' B B R R F F D D L L U' D'
g_3可以保持其他块的方向和位置,只改变FU和FD的方向,分别是FU的方向+1,FD的方向的方向+1。
2.1. 小引理lemma4:假设棱块的方向数求和后,模2为0,假设12个棱块的方向数中,有11个方向数能被G中若干元素作用后还原为0,则=>,第12个棱块的方向数也还原成0。
为什么呢?:也是类似上面证明。
2.当前状况要变成还原状态,过程类似于情况1中的证明:这里简单描述步骤:
(题外话:TW算法中这一步简单很多。)
(涉及g1,R,虽然用到R,但是R是“类交换子”中的一部分,换句话说,R一共执行了4次,相当于没有对角块方向数和位置,发生影响)
先用g2和R逐个还原R面的4个方向数。至此已还原4个方向数。这一行前面的过程,R一共执行了3次。当然为了保证角块方向数不变,R面4个位置要弄回这一步开始时的顺序,再执行1次R即可。
(涉及g1_R,B,虽然用到B,但是B是“类交换子”中的一部分,换句话说,B一共执行了4次,相当于没有对角块方向数和位置发生影响)
还原B面的3个BU,BD,BL:然后g1的“R”变式,也就是用R面当成前面,直接操作g1,配合B,逐个还原B面的3个棱块。这一行前面的过程,B一共执行了3次。至此已还原7个方向数。当然B面4个位置要弄回这一步开始时的顺序,要执行1次B。
(涉及g1_B,L,虽然用到L,但是L是“类交换子”中的一部分,换句话说,L一共执行了4次,相当于没有对角块方向数和位置发生影响)
还原L面的1个LD:然后g1的“B”变式,也就是用B面当成前面,直接操作g1,配合L还原L面1个棱块。这一行前面的过程,L一共执行了2次。至此已还原8个方向数。当然B面4个位置要弄回这一步开始时的顺序,要执行2次L。(这一步故意留一个L面的LU没有还原方向数)
(涉及g1_L,F,虽然用到F,但是F是“类交换子”中的一部分,换句话说,F一共执行了4次,相当于没有对角块方向数和位置发生影响)
还原F面的3个FL,FD:然后g1的“L”变式,也就是用L面当成前面,直接操作g1,配合F逐个还原这2个棱块。这一行前面的过程,F一共执行了2次。至此已还原10个方向数。当然F面4个位置要弄回这一步开始时的顺序,要执行2次F。(这里故意留一个F面的FU没有还原方向数)。
现在的状态先分析一下,剩余的2个棱块UL,UF方向数只有下面的选择:分类讨论:
根据小引理lemma4即2.1. ,也就是以上设计的所有公式涉及的{g1,g1变式,以及Actions中的元素},都保持了一个性质:方向数求和模2为0。
因此当前情况下σ(g)=id,ρ(g)=id,且v(g)={0,0,...,0},也将得到性质w(g)={0,0,...,0}。v(g)还是全零。
{
1.0和1:由引理2.1的使用,这种情况不可能存在。因为mod 2 ≠ 0 。
2.0和0;不用操作,已还原方向数。
3.1和0;由引理2.1的使用,这种情况不可能存在。因为mod 2 ≠ 0。
4.1和1:执行一次g1的“L”变式,这样就还原了所有棱块方向数。
}
3.至此已还原了棱块的方向数。并且过程中不改变角块的方向数。加上原有假设全体位置不变(在过程中也不受影响),因此已达到魔方还原状态e。
3.0 这里其实可以记成一个小引理:假设有状态g∈H,假设σ(g)=id,ρ(g)=id,且∑(12在上 i=1) wi(g) = 0 (mod 2) , 则=>,
g能通过有限次作用G中的元素,得到新的性质:w(g)={0,0,...,0}。
3.0.1.lemma6: 这里可以一般化引理:假设有状态g∈H,且∑(12在上 i=1) wi(g) = 0 (mod 2) , 则=>,
g能通过有限次作用G中的元素,得到新的性质:w(g)={0,0,...,0}。并且不改变角块的方向数。
因此当前假设的情况g∈G成立。
(目前来看,思路是:为了达到还原成e的新目标,而分情况讨论,每次讨论都故意缺一个充要条件的其中一条,
其实是1/4的充要条件(σ(g)=id,ρ(g)=id,w(g)={0,0,...,0},v(g)={0,0,...,0})。
可以发现上面两种情况无意中独立出来2条引理,是下面的关键。)
3.现在考虑这种情况:σ(g)=id,ρ(g)=id,即棱块和角块位置不变,且满足(1),(2),(3)的话,也可以满足g∈ G。(换句话说,这里直接缺了e中的2条条件):
1.由上面5.1.引理知道,存在有限操作X1,g状态可以变成新的状态g_2,然后拥有性质v(g)={0,0,...,0}。
2.由上面3.0 引理知道,存在有限操作X1,g_2状态可以变成新的状态g_3,然后拥有性质w(g)={0,0,...,0}.
3.至此就集齐了e状态的4个充要条件。
4.也就是说,当前假设的情况g∈G成立。
4. 考虑棱块和角块方向不变时的情况g,即w(g)={0,0,...,0},v(g)={0,0,...,0},且满足(1),(2),(3)的话,即缺了e的前2个条件的情况。
看能不能再独立出一条充要的引理。
要证明状态g属于群G,当前证明目标变成新目标:
g可以通过若干Actions复合操作变成还原状态e接口。
也就是通过若干Actions复合后,能拥有性质σ(g)=id,ρ(g)=id。
这种情况的状态的全体记为
H':即w(g)={0,0,...,0},v(g)={0,0,...,0}的H中的状态。也就是棱块和角块方向数不变时的情况。只可能改变位置。
然后定义一个交集G',
G' := H' ∩ G , 换句话说,就是魔方群中方向数不变的元素集合
我们下面将给出3个这样的G'中的元素,他们当然满足:
1.不改变全体方向数,即w(g)={0,0,...,0},v(g)={0,0,...,0}
然后通过这3个操作的复合将任意一个G'中的方向分量全为0的状态A1,变换到原始状态e,也就是把位置也还原了,这就解决了我们的新目标。
4.1.g3 = RU'RURURU'R'U'R^2 (即R U' R U R U R U' R' U' R R): 是一个棱块位置3循环,也就是σ(g3) =(1,2,4)。方向数都是0。
4.2.第二个g4 = R' F' F' F' R' B B R' R' R' F' R' B B R' R',是一个角块位置3循环, ρ(g4) =(2,4,3)
4.2.错误的?第二个g4_2 = LF'LD^2L'FLD^2L^2 :是一个角块位置3循环, ρ(g4) =(4,5,6)
4.3.第三个g5 = RUR'F'RUR'U'R'FR^2U'R'U'(即R U R' F' R U R' U' R' F R R U' R' U')
:是2个2循环:2个棱块的2循环,2个角块的2循环σ(g5) =(1,2) ρ(g5) =(2,3)
下面将描述方向不变,只有位置变化时,如何变成e的具体步骤,也就是还原位置的具体步骤:
4.4 An :Sn置换群中,是偶的那些元素(即偶置换),这些组成的群。也称为“n元交错群”。
元素个数是Sn的一半,即1/2,记为|Sn/An|=2 ???
4.5 N:由G'中的全体元素,抽取2个位置变换拼成的的向量。向量里有两项内容(分别是12项向量,和8项向量),
从定义知: N={(σ(g) , ρ(g)) |g∈G' } < SE×SV。(备忘:N定义中的g∈G', g不会改变全体块的方向数)
4.6 小引理:假设n>=3,对于任意集合M,假设M包含Sn中全体3循环,则=>, M >= An
证明:因为P.180的9.4.1(用到P.56的引理3.4.1),即Sn中全体3循环元素生成的群,就是An。
因此M中只抽出Sn中的全体3循环,就能生成An了M集合肯定就>=An集合了。
以此为前提,我们可以把A8 = <S8中的所有3循环> , A12 = <S12中的所有3循环> ,
4.7 小引理:N >= AE×{(1)}。 因为N中元素是这样的形式(σ(g) , ρ(g)),所以可以把目标转化成新目标:
{N中符合ρ(g) = id的那些元素(这类元素是存在的,比如例子g3),将这些元素的集合,记为Y1,Y1={(σ(g),(1))|g满足:ρ(g) = id, g不改变全体块的方向数}
则=>: Y1中的全体元素都列举出第一个向量σ(g),组成一个集合Y2,Y2会满足: Y2 >= AE。
}
证明:
1. ((1,2,4),(1)) ∈ N ,换句话说,N中有这个向量((1,2,4),(1)),为什么呢?:
因为对应这个向量的g∈ G' , 是存在的,比如g3就是一个。
2.小引理:任意H'中的元素X1,假设X1存在满足这样的形式:((i,j,k),(1)),(这样的形式的确存在的,举例:g3,但是否能任意取i,j,k,还不确定),
换句话说,就是棱块位置是某个3轮换,角块位置不变,棱块和角块方向数为0。
则=>: X1状态能经过有限次G'中的操作,得到状态e ∈ G。
证明:
这里的证明其实就是给出这个有限次G'中的操作,记为G1
所以下面通常要涉及分类讨论(i,j,k)中3个分量的相对位置,具体步骤:
注意:这里用到的操作是g3,g4,g5,X1^(n)X2X1^(-n)(交换子中X1是{L2,R2,F,B,U,D}复合的)因为这样的集合保证了方向数不会改变,而且角块位置不变。
0.1. 交换子公式小引理:X1X2X1^(-1)这类的操作,假设X1取的是Actions的复合,X2取的是棱块3循环集合的元素,这里特指{g3},
记g3影响到的棱块位置为第i,j,k,这个3循环记为(i,j,k),则=>:
X1X2X1^(-1)的操作,不改变全体角块方向数和位置。
全体棱块方向数可能会变化的。
因为已知任意状态g,通过X1操作后,会有所影响的棱块位置集合,记为E1 = {l1,l2,l3,...},
X1操作效果是:{l1=>m1,l2=>m2,l3=>m3,...}
则=>:
{
1.如果E1中只存在一个初始位置为l1,通过X1操作后到达集合{i,j,k}中任意一个的,则=>:,
假设是{i,j,k}中的i
X1X2X1^(-1)的操作的结果会是一个不改变全体角块方向数和位置,这样的3棱块循环:
(i,j,k) → (l1,j,k) →(X2作用) → (k,l1,j), 也就是(k,l1,j)这样的新的3棱块循环,但全体棱块方向数可能改变。
{i,j,k}的其他情况类推可知:
假设是{i,j,k}中的j:(i,j,k) → (i,l1,k) →(X2作用) → (k,i,l1)这样的新的3棱块循环,但全体棱块方向数可能改变。
假设是{i,j,k}中的k:(i,j,k) → (i,j,l1) →(X2作用) → (l1,i,j)样的新的3棱块循环,但全体棱块方向数可能改变。
2.其他情况的定理目前先不探究:略。
}
证明:分类讨论:
{
1.对于全体角块:{
1.对于方向数:
先执行X1,这一步肯定有可能修改方向数的,设影响到方向数的4个位置是第{P1,P2,P3,P4,...,Pn},(先记这4个位置的执行这一行前的方向数分别是a1,a2,a3,a4,...an)
设改变的详细是{P1:a1→b1,P2:a2→b2,P3:a3→b3,P4:a4→b4,...Pn:an→bn},把这个过程记为函数f1,方向数分别变成了。
然后执行X2时已知不改变全体角块的方向数,这一步结束后,对于P1,P2,P3,P4,...,Pn来说,都没改变方向数,还是b1,b2,b3,b4,...,bn。
然后执行X1^(-1),对于P1,P2,P3,P4,...,Pn的方向数,相当于执行了一次f1^(-1),即f1的逆映射,
分别改变详细是:{P1:b1→a1,P2:b2→a2,P3:b3→ba,P4:b4→a4,...Pn:bn→an},因此又变回了a1,a2,a3,a4,...an方向数,因此不变。
2.对于位置:
先执行X1,这一步肯定改变位置的,设影响到的4个角块记为{V1,V2,...,Vn}。(执行这一行前这4个角块的位置分别记为第a1,第a2,...,第an)
设改变的详细是{V1:第a1→第b1,V2:第a2→第b2,...,Vn:第an→第bn},把这个过程记为函数f2,位置分别变成了第b1,第b2,...,第bn。
然后执行X2,已知不改变全体角块的位置,这一步结束后,对于V1,V2,...,Vn来说,都没改变位置,还是第a1,第a2,...,第an。
然后执行X1^(-n),对于V1,V2,...,Vn的位置,相当于执行了一次f2^(-1),即f2的逆映射,
分别改变详细是:{V1:第b1→第a1,V2:第b2→第a2,...,Vn:第bn→第an},因此又变回了第a1,第a2,...,第an的个位置,因此不变。
}
已知任意状态g,通过X1操作后,会有所“影响”(有动的都是)的棱块位置集合,记为E1 = {l1,l2,l3,...},X1操作效果是:{l1=>m1,l2=>m2,l3=>m3,...}
如果E1中只存在一个初始位置为l1,通过X1操作后到达集合{i,j,k}中的任意一个。
2.分类讨论:{
1.如果只有l1操作X1后到达了位置j:分类讨论棱块位置:--
{
注意这里全体棱块 = {i,j,k} + {E1 - j} + {E1 + i + k}外的全体棱块
换句话说= E1 + {i,k} + {E1 + i + k}外的全体棱块
1.对于{E1 + i + k}外的全体棱块:这个集合中任意一个元素,作分析:
由于X1操作改变了E1中的位置和方向,
但X2没有对E1中任何位置和方向发生变化,
所以X1^(-1)操作后E1中的位置和方向就还原了。
2.对于X1操作前的位置{i,k}的这两个棱块:
由于只有j被到达了,换句话说,{i,j,k}只有j收到了X1操作的影响,因此操作X1后{i,k}的方向和位置不变
操作X2后,位置变化:{第i→第j,第k→第i}
然后操作X1^(-1):
分类讨论:{
1.X1操作前的位置i:因为经过X2后移到了第j,会涉及方向和位置变化:
由于X1的位置操作变化有:{第l1→ 第j}
因此通过X1^(-1)操作后,当前分析的棱块位置会变到第l1。
2.X1操作前的位置k:因为经过X2后移到了第i,不受X1^(-1)的变化影响,方向数和位置不变。
}
总结就是:{第i→第l1,第k→第i}
3.对于X1操作前的位置E1这些棱块:分类讨论:
{
1.对于第l1位置的棱块:
X1操作改变了方向和位置,位置到了第j位置,
X2操作改变了方向和位置,位置到了第k位置,
X1^(-1)操作后,由于X1的作用范围集合E1,和X2的作用范围集合{i,j,k}只有交集第j位置,
而目前分析的棱块到了第k位置,不会收到X1的作用影响,保持第k位置。
总结这个棱块的变化:{第l1→第k}
2.对于第j位置的棱块:
X1操作改变了方向和位置,位置到了某个位置记为第j_2 ≠ 第j,方向数记为v_2,j_2在X1影响范围内,即j_2∈ E1
由于X1的作用范围集合E1,和X2的作用范围集合{i,j,k}只有交集第j位置,这个j_2 ∉ {i,j,k}
X2操作中,由于j_2 ∉ {i,j,k},当前棱块的方向和位置不变,位置还是第j_2,方向数还是v_2。
X1^(-1)操作中,方向数得到了还原,位置也因此得到还原。
总结变化:{第j→第j}
3.E1除了第l1位置,还有除了第j位置以外的棱块:
X1操作改变了方向和位置,
但X2不改变方向和位置,因为E1中只有l1到达了X2的作用区域中。
因此X1^(-1)操作后目前分析的这些“E1除了第l1位置,还有除了第j位置以外的棱块”就恢复了原来的方向和位置。
}
}
总结上面得到仅有的3个位置变换的:{第i→第l1,第k→第i},{第l1→第k},
合并起来就是{第i→第l1,第k→第i,第l1→第k} ,写成3循环就是(i,l1,k) = (k,i,l1),得证。
2.如果l1操作X1后到达了位置j:类似推理
3.如果l1操作X1后到达了位置k:类似推理
}
}
0.2. 推论:直接使用0.1引理,但是再加一个假设:全体棱块方向数不变化,即要求X1不改变方向数
(有一个方法很容易满足X1不改变方向数,只要组成它的元素都在这个集合中即可:{L2,R2,F,B,U,D},当然也有其他集合可以.)
则=>:
使用0.1引理得到的“3循环,但全体棱块方向数可能改变”,就可以变成单纯的3循环。换句话说,就是保证了全体棱块方向数不变。
1.首先把棱块还原成e:
g3:R U' R U R U R U' R' U' R R
σ(g3) =(1,2,4)
目标:任意棱块3循环(棱块方向数为0,角块位置为id),可以用g3和g3变式和交换子模式还原成e。
(硬要一个个列举的话,12个选3循环有220中不同的。)
证明:
1.对E1,E2,E3进行全体分类。
注意*:以下都是讨论单纯的3循环,方向数不变。
{
1.1个面包含了3个棱块,这样的面有1个的情况:
{
1.3个棱块都在某个面:
1.逆时针顺序是E1,E2,E3:使用若干次g3或g3变式,将E1先恢复,其他自动也会恢复。因此得到e。
2.逆时针顺序是E1,E3,E2:使用若干次g3或g3变式,将E1先恢复,其他自动也会恢复。因此得到e。
}
上述以外的情况里,也就是“1个面包含了3个棱块,这样的面有0个的情况”:
2.1个面包含了2个棱块,这样的面只有3个的情况:
{
E1,E2,E3只有这种相对位置:
1.E1,E2,E3的相对位置是类似{1,2,6}这样的,集合中取:交换子要用到中层变换。
}
3.1个面包含了2个棱块,这样的面只有2个的情况:
{ E1,E2,E3相对位置分类
1.类似{1,3,9}这样的:交换子
2.类似1,3,7:用到中层的交换子。
3.1,4,8:交换子。
4.1,4,12:交换子。
}
4.1个面包含了2个棱块,这样的面只有1个的情况:
{
1.1,3,10:交换子。
}
5.1个面包含了2个棱块,这样的面有0个的情况:
首先筛选剩下了这些可供E2,E3选择{BL,DL,BR,DR,BU,BD,DF} = {8,12,7,10,3,11,9}:
由于对称性,BL→BR,DL→DR,BU→DF,BD , 即{7,10,9,11}
E2从这4个归化的里面选:
{
1.1,7,12:2次交换子
2.1,10,8:2次交换子
3.1,9,7:2次交换子。
}
2.然后把角块还原成e:
g4: R' F' F' F' R' B B R' R' R' F' R' B B R' R'
ρ(g4) =(2,4,3)
目标:任意角块3循环(角块方向数为0,棱块位置为id),可以用g4和g4变式和交换子模式还原成e。
(硬要一个个列举的话,8个选3循环有56种不同的。)
证明:
直接对V1,V2,V3进行全体分类:
{
1.1个面包含了3个角块,这样的面有1个的情况:
{
1.3个角块在同一个面:
{
1.V1,V2,V3逆时针排列:执行若干次g4变式,将V1先恢复,则其他也跟着恢复。得到e。
2.V1,V2,V3顺时针排列:执行若干次g4变式,将V1先恢复,则其他也跟着恢复。得到e。
}
}
上述1除外的情况里,也就是“1个面包含了3个角块,这样的面有0个的情况”还有:
2.1个面包含了2个角块,这样的面有3个的情况:
{
1.2,1,7:交换子。
2.2,4,X:分类:
{
2,4,8: 3次交换子。
2,4,5: D' (2,4,8) D 即可。
2,4,7: D' (2,4,6) D 即可。
2,4,6: 3次交换子。
2,4,6举例:
先搞一个(2,3,6)交换子,记下来:D' L L g4 L L D
复原,使用(2,4,3)
然后使用(2,3,6) 2次?,把3还原,
最终得到(2,4,6): g4 (D' L L g4 L L D) (D' L L g4 L L D)
简化成了:R R D D L L D R R D' L L D R R D R R
}
{
2,3,5:交换子。
2,3,8:交换子。
}
4.2,7,X:
{
2,7,1:上面已存在。
2,7,4:上面已存在。
2,7,5:L L (2,4,7) L' L'即可。
2,7,8:L L (1,2,7) L' L'即可。
}
5.2,6,X:
{
2,6,4:上面已存在。
2,6,8:B B (2,6,7) B' B'即可。
}
6.2,5,X:
{
2,5,4:上面已存在。
2,5,3:上面已存在。
2,5,7:上面已存在。
2,5,8:B B (2,5,4) B' B'即可。
}
7.2,8,X:
{
2,8,1:上面已存在。
2,8,3:上面已存在。
2,8,4:上面已存在。
2,8,5:上面已存在。
2,8,6:上面已存在。
2,8,7:上面已存在。
}
}
3.1个面包含了2个角块,这样的面有2个的情况:
{
1.2,1,X: 不存在,所以不用讨论。
2.2,4,X: 不存在
3.2,3,X: 不存在
4.2,7,X: 不存在
5.2,6,X: 不存在
6.2,5,X: 不存在
7.2,8,X: 不存在
}
4.1个面包含了2个角块,这样的面有1个的情况:
{
不存在,所以不用讨论。
}
5.1个面包含了2个角块,这样的面有0个的情况:
{
不存在,所以不用讨论。
}
}
2.1 小引理推论***:如果从e出发,复合一些G中的交换子和g3变式和g4变式,则=>:
能经过有限次G'中的操作,得到((i,j,k),(1)),其中第一个分量(i,j,k)满足:1<=i<=j<=k<=12。
而且留意一下,全体棱块和角块的方向数不变,全体角块的位置也不变。
换句话说,对于任意1<=i<=j<=k<=12,得到的这个变量(i,j,k),也就是任意的S12中的任意3循环的状态,
都能从((1,2,4),(1))经过有限次G'中操作,得到第一个分量能变成这个任意的3循环。
5.总结:
目标问题:g∈ H , 则=>: g∈G 吗?
3个条件中第一个把H针对位置先分类,也就是针对(S8 X S12)分成了两个集合,分类讨论:
对于状态g∈H
1.有一个3.0小引理,由条件(2),即有求和棱块模2为0,因此g可以通过有限G中步骤,这里记为X1,得到新的性质:w(gX1) = {0,0,...,0}。
而且不改变角块的方向数,因此保持了条件(3)。
2.有一个5.1小引理,由条件(3),即求和角块模3为0,因此g·X1可以通过有限G中步骤,这里记为X2,得到新的性质:v(gX1X2) = {0,0,...,0}。
3.我们先介绍一些通用的已知知识:(S8 X S12)有一个“子群”,记为G1:(A X B),(A X B)= (A1 X B1)∪ (A2 X B2) ,换句话说就是(奇X奇)∪(偶X偶)这个并集。
其中A1是S8中全体奇的置换,A2是S8中全体偶的置换,
B1是S12中全体奇的置换,B2是S12中全体偶的置换。
很明显,这两个集合(A1 X B1),(A2 X B2) 是没有交集的。
可以证明这个子群是封闭的。因为(奇X奇)+(偶X偶) = (奇X奇)
3.1 同样用是否符合条件(1)来将H分成两个子集H1,H2的话。记符合条件(1)的为H1,不符合的为H2。其实这个H1就是G1, H1 = G1,因为H1和G1的定义是一样的。
H1经过P映射就是(A X B);
H2经过P映射就是 (S8 X S12) - (A X B);
4.由条件(1),g有性质:棱和角的位置排列的符号数相等,换句话说就是(奇X奇) or (偶X偶)。
所以:g属于3.1中的H1,g'是属于3中所说的(A X B)这个子群的。
即g∈H1,g'∈(A X B)
根据3的分析可知G1=H1是一个(S8 X S12)的子群,g∈H1,g经过X1,X2后变成了新状态gX1X2,这里记为g2。
因此可以把当前目标g∈G,转化成新的目标:g2∈ G。(因为X1,X2都是G中元素)
5. (S8 X S12)可以分成4个不相交子集的并集:奇X奇 ∪ 偶X偶 ∪ 奇X偶 ∪ 奇X偶。
这4个子集的元素个数都相等,因为An(偶置换)是Sn的指数为2的子群。Sn除了An的剩下的当然都是奇置换。
6.分析g2具有性质:w(g2) = {0,0,...,0},v(g2) = {0,0,...,0}。而且对g2经过P映射后的g'(仍然是g',因为g到g2只改变了方向数)。
7.右推左过程中,条件(1)让我们把g'的范围进一步缩小了,条件(1)换句话说,就是角块和棱块的排列的符号相等。
换句话说,角块的排列和棱块的排列,同为奇,或者同为偶。因此g'∈ 奇X奇 ∪ 偶X偶 。
8.我们这里把 (S8 X S12)分成两个子集,它们的元素个数相等。分别是
1.(奇X奇 ∪ 偶X偶),记为J1;
2.(奇X偶 ∪ 偶X奇),记为J2。
由3.1分析可知,H1经过P映射得到J1,H2经过P映射得到J2
9.G通过映射P得到集合G',由于我们已证明左推右,当然可以用。所以G中的元素都是满足条件(1)的性质:“角块的排列和棱块的排列,同为奇,或者同为偶”。
因此G'属于8中定义的J1。
10.由于2.1小引理推论,g_E124和g_E123可以生成所有的g_E???(方向数w,v都是全零,角块位置是id) 3循环,也就是(id)Xg_E???
类似的某个引理(这里没详细证明),g_V456可以生成所有的g_V???(方向数w,v都是全零,棱块位置是id) 3循环,也就是g_V???X(id)
11.小引理:无前提假设,则=>,g_E???和g_V???可以与G中元素复合生成({A8},{A12},id,id)这样的任意元素。
证明:由于({A8},{A12},id,id) = ({A8},(id),id,id) + ((id),{A12},id,id) , 这里的写法不太严谨,换句话说,({A8},{A12},id,id)这个集合里面任意的一个元素,
比如(a1,a2,id,id) = ((b1,b2,...,b8) ,(c1,c2,...,c12),id,id)
则由g_E???复合运算得到元素C1:((b1,b2,...,b8) ,(id),id,id)
g_V???复合运算得到元素D1:((id),(c1,c2,...,c12),id,id)
将D1作用到魔方状态C1上,就得到了:((b1,b2,...,b8) ,(c1,c2,...,c12),id,id),也就是({A8},{A12},id,id)中的任意一个元素。
12.小引理:g2是否一定能经过有限步G中操作,得到集合({A8},{A12},id,id)中的某一个元素
对g2的前两个排列的奇偶性进行分类讨论,条件(1)把g2的范围缩小成了(奇X奇) or (偶X偶):分类讨论:
{
1.g2的前两个排列的奇偶性是奇,奇:详细步骤:
先执行一次g5,g5保持了棱和角方向数不变,保持id,id。
然后将前两个排列的奇偶性都变换了,因此g2g5的前两个排列的奇偶性是偶,偶,因此转化成下面第2种情况。
2.g2的前两个排列的奇偶性是偶,偶:由小引理11,G中元素可以复合得到({A8},{A12},id,id),换句话说,由于g2∈ ({A8},{A12},id,id),所以g2同样可以被G中元素可以复合得到。
}
至此,新目标g2∈ G证明完毕。
}
----------------------------
书中同步看一下:
{
1. 由 9.4.1 (P.180), 我们知道AE是由一些棱块3循环生成的;
AV是由一些角块3循环生成的。
引理9.4.1: 对于Sn,Sn中所有的3循环的元素(也就是,比如s1,则s1^3 = s1, 即s1^2 = id)组成集合D,
H由D中的元素生成,H应该是一个置换群,是Sn的子群,则=>:
H = An , 换句话说,H就是Sn中的偶的置换。
?
引理3.4.1(P.56):任意非平凡的排列,都可以写成有限个2循环的乘积结果。
通过具体算法来说明:
用数学归纳法:
}
--/////////////////////---/
--/////////////////////---/
--/////////////////////---/
以下开始TW算法的内容,实际上只有七个公式:
6.降群法:逐步掉入更小的子群,掉入不同生成集生成的子群(换句话说,就是掉入一个新的状态集合,这个新的状态集合只需生成集中元素就能复合得到)。
7.1 G = <L,R,F,B,U,D>
7.G1 = <L^2,R^2,F,B,U,D> 具有性质:
1.不改变任何棱块的方向。
8.关于G1的命题1:∀g∈ G,
g∈G1
↔
wi(g)=0 , ∀i , 1<=i<=12
证明:
(换句话说:右推左其实也就是说,棱块方向都没变的状态,可以通过G1的生成集来生成。)
左推右:
{
对g的操作长度作归纳:
1.首先g的长度为1验证:只需要验证G1( <L^2,R^2,F,B,U,D>)中的6个生成元,都满足。
2.假设对于任意长度为k的时候成立,也就是:wi(X_1X_2...X_k) = 0 , ∀i , 1<=i<=12
3.验证长度为k+1的时候,也就是g=X_1X_2...X_kX_(k+1) , 需要验证:wi(X_1X_2...X_kX_(k+1)) = 0 , ∀i , 1<=i<=12
4.由于之前的类同态定理,我们已知w(X_1X_2...X_kX_(k+1)) = w(X_1X_2...X_k) + σ(X_1X_2...X_k)^(-1)·w(X_(k+1))
5.因此需要验证的目标,变成新的目标:wi(X_1X_2...X_k) + [σ(X_1X_2...X_k)^(-1)·w(X_(k+1))]_i , ∀i , 1<=i<=12
= [σ(X_1X_2...X_k)^(-1)·w(X_(k+1))]_i , ∀i , 1<=i<=12 因为假设,X_1X_2...X_kX_(k+1)的所有分量都是0,换句话说就是wi(X_1X_2...X_k) = 0
= 0 , ∀i , 1<=i<=12 因为w(X_(k+1))的每个分量都是0,不管怎么重新排列,还是全零。
}
右推左:
{
0.已知wi(g)=0 , ∀i , 1<=i<=12,换句话说,棱块的方向数全部为0。
0.1 g∈G,也就是g是可还原魔方群的一个元素。(换句话说,可以使用魔方第二基本定理)
1.由于目标是要推出g∈G1,换句话说,换成新的目标:就是g状态可以通过G1中的元素复合得到e。
2.给出不改变全体位置,且不改变全体棱块的方向数的前提,只单纯还原全体角块的方向数的操作步骤:
1.关键公式:h1 = (D' L L D B' R R B)^2 ,效果:4号方向数+1,6号方向数+2
(下面应该不止用到h1,还会用到一些包含h1的交换子公式)
2.(涉及U,h1)先依次还原这些角块的方向数为0:1号块,2号块,3号块。故意留一个4号块。