（基础数学专业论文）群论在魔方中的应用.pdf

群论在魔方中的应用摘要 摘要 本文从群论的角度讨论了魔方( r u b i k sc u b e ) 的数学性质首先，本文 以魔方作为工具，展示了群论中的各种概念及其相关性质的实际应用，如置 换，作用，轨道，传递性，本原性，共轭，换位子，同态；其次，介绍了魔 方群的结构；最后，作为本文的核心，将魔方群对应的c a y l e y 图直径下界由 2 0 提升到2 1 关键词：魔方，置换群，直径，下界 作者：朱磊 导师：施武杰 a p p l i c a t i o n so fg r o u pt h o e r yi nr u b i k sc u b e a b s t r a c t a p p l i c a t i o n so fg r o u pt h o e r yi nr u b i k sc u b e ab s t r a c t t h i sp a p e rd i s c u s s e dt h em a t h e m a t i c a lp r o p e r t i e so ft h er u b i k sc u b ef r o mt h ev i e w - p o i n to fg r o u pt h e o r y f i r s to fa l l ，t a k i n gt h er u b i k sc u b e a sa t o o l ，t h i sp a p e rd e m o n - s t r a f e dt h ep r a c t i c a la p p l i c a t i o n so fa l lk i n d so fc o n c e p t sm a dt h e i rr e l e v a n tp r o p e r t i e s i ng r o u pt h e o r y , s u c ha sp e r m u t a t i o n ，a c t i o n ，o r b i t ，t r a n s i t i v i t y , p r i m i t i v i t y , c o n j u g a - t i o n ，c o m m u t a t o ra n dh o m o m o r p h i s m ；s e c o n d l y , t h i sp a p e ri n t r o d u c e dt h es t r u c t u r e o ft h er u b i k sc u b eg r o u p ；a tl a s t ，a st h ec o r eo ft h i sp a p e r ，i tp r o m o t e dt h el o w e r b o u n do ft h ed i a m e t e ro ft h ec a y l e yg r a p hw i t hr e s p e c tt ot h er u b i k sc u b eg r o u p ， f r o m2 0t o2 1 k e y w o r d s ：r u b i k sc u b e ，p e r m u t a t i o ng r o u p s ，d i a m e t e r ，l o w e rb o u n d i i w r i t t e nb yl z h u s u p e r v i s e db yp r o f w j s h i 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：塑 日期：磁剑19 f 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：塞丝日期：乙巫! 里! 墨竺 i 导师签名：玉迭生日期：竺壁b 垒亟1 9 日 l 1 群论在魔方中的应用一群论概念在魔方中的应用 第一章群论概念在魔方中的应用 1 1 前言 魔方最初是在1 9 7 4 年由一位匈牙利的建筑学教授r u b i k 所发明，其最 初的目的不过是为了使学生对立体事物增加一些实感令r u b i k 始料未及的 是，魔方一经问世后竟然风靡全球，成了2 0 世纪8 0 年代初期最受欢迎的玩 具 魔方不仅是一个令千万人着迷的有趣玩具，同时也是一个能够展示许 多群论概念及其相关i 生质的有力工具如置换，作用，轨道，传递性，本原 性，同态等诸多概念在魔方中的体现，如共轭和换位子在复原魔方的过程中 起到的化繁为简的作用 人们在玩魔方的时候，很自然地会提出如下问题：魔方不同色彩组合的 种数是多少? 这个问题已经得到解决，大致思路是建立所有魔方色彩组合 到魔方群的双射，计算出该群的阶，从而确定魔方不同色彩组合的种数更 进一步地，利用群论作为工具，还可以分析出魔方的结构，这点将在后文中 详细介绍 除了上述问题，人们在玩魔方的时候，最核心的问题是：如何将一个处于 混乱状态的魔方复原? 这个问题已经得到解决，而且解法远远不止一种，这 都归功于众多魔方爱好者本文不对如何复原魔方进行探讨，如果有兴趣， 可以参考 1 1 上述问题是比较特殊的一种形式，与之对应的是由此衍生的问题：魔方 群c a y l e y 图的直径是多少? 这个问题目前没有得到解决有人把该直径称为 上帝之数( g o d sn u m b e r ) 相应地，还原魔方的步骤被称为上帝的算法( g o d s a l g o r i t h m ) 1 9 8 2 年，s i n g m a s t e r 和p r e y 在【2 】2 中猜想上帝之数是2 0 出头的一个数 群论在魔方中的应用一群论概念在魔方中的应用 字直接求解上帝之数恐非易事，否则它也不会背上上帝之数这个称号屹立 2 6 年不倒了一种比较可行的办法是分别从上界和下界逼近，如果最后能 够达到上下界相等，那么该相等的值也即是上帝之数 k u n k l e 和c o o p e r m a a 在【3 】中给出了目前关于上界的最好结果：2 6 ( 该值 是在包含半周旋转的情况下所得，如果只考虑四分之一周旋转，该值应该更 大) 【4 1 给出了目前关于下界的结果：2 0 本文的主要成果是将下界从2 0 提升到2 1 ，基本思路是把魔方群的元素 按照长度进行分类，并且尽可能地排除每个分类中重复的元素，最后将这些 分类的元素个数相加，与魔方群的阶比较大小，最终确定下界 1 2 基本介绍 从外观看，魔方是由3x3x3 1 = 2 6 个块( 不包含最里面的块) 组成的 立方体它有6 个面，每个面有3 3 = 9 个小面，共6x9 = 5 4 个小面2 6 个块中，有3 个小面是角块，有2 个小面是边块，只有1 个小面是中心块 显然，魔方共有8 个角块，1 2 个边块和6 个中心块 定义1 1 转动是指将魔方的某个面上的所有块顺时针何对该面j 旋转丌2 类似地，逆转动是逆时针旋转丌2 转动和逆转动统称为转动 这里定义的转动都是四分之一周旋转，不包括半周旋转为了简明，若 非特别提及，本文不使用魔方中间层面的转动，因为其可以被相邻两侧的面 转动所替代 作为惯例，本文使用s i n g m a s t e r 记号表示6 个面的转动及各小面和块的 方位用大写的u ( 上) ，d ( 下) ，f ( 前) ，b ( 后) ，l ( 左) ，r ( 右) 表示各面相应的转 动，用小写的u ，d ，b ，f ，r 表示备面及相应的中心块对于角块上的小面，用 x y z 表示其方位，含义是：z 面y z 方位的小面如u f l 表示u ( 上) 面，z ( 前 左) 方位的小面这种方法也可以用来表示相应的角块类似地，对于边块 2 群论在魔方中的应用 一群论概念在魔方中的应用 上的小面，用x y 表示z 面y 方位的小面如d 6 表示d ( 下) 面6 ( 后) 面方位的 小面同样：这种方法也可以用来表示相应的边块这种既表示小面又表示 块的方法不会造成混淆，可以通过上下文理解其含义 一个简单的事实是：在不对魔方中间层面进行转动的情况下，无论怎样 转动魔方，各个面的中心块总是固定的据此，在涉及魔方各面的时候，总 是指其中心块所代表的那个面，这样为讨论问题提供了一个固定的参考系 1 3 魔方群 规定魔方的转动合成运算是从左向右的，即vm ，m 2 仉d ，只b ，l ，舛， m 表示先转动尬，再转动尬如r u 表示先转动r ( 右) 面，再转动u ( 上) 面用c 表示魔方状态，即各块和小面的方位，用m ( c ) 表示魔方在状态 c 下经m 转动后所生成的新状态考虑到转动合成运算是从左到右的，有 ( 尬) ( c ) = m 2 c m l ( c ) ) 定理1 2 由魔方所有转动生成的集合，以合成作为运算，构成一个群，称为 魔方群 证明：设g = 是魔方所有转动生成的集合 g 中任意元素都可以表示成一系列转动的合成，则g 中任意两个元素的合 成同样是一系列转动的合成故g 是封闭的 用c 表示任意魔方状态，则v 舰，m 2 ，m 3 g ，有： ( ( m m 2 ) ) ( c ) = 地( ( 尬尬) ( c ) ) = ( ( 尬( c ) ) ) ( 尬( 尬) ) ( c ) = ( 慨) ( 蛆( c ) ) = 慨( ( m ( c ) ) ) 根据c 的任意性，可得( 尬) m 3 = m ( 地) 故结合律成立 若魔方状态c 在转动m 的作用下不发生改变，则m 是单位转动故单位元 存在 若m = 尬坛是生成元素的乘积，旭 阢d ，只b ，l ，r ) ，i 1 ，2 ，n ) ， 3 群论在魔方中的应用一群论概念在魔方中的应用 则m _ 1 = m z l 岈1 m 1 1 故逆元存在 综上四点，g = 构成一个群，称为魔方群 n 1 4 置换 魔方群g 的生成元可以用一系列小面的置换来表示： u = ( u l bu b ru r ，t l 川( t 6u rt ：，t 2 ) ( 地zr u bl u r2 t l ，) ( 轧r t ，u 轧) ( 6 r uf l u l ul b u ) d = ( d b ld l f 形rd r 功( d 6d l 珂d r ) ( b z dz l di r dr 6 d ) ( 6 dl df d7 d ) ( 6 打l d bf d lr d ! ) f = ( f l u ，u rf r df d l ) ( f uf rf df o ( u i z7 ，u 够rl f d ) ( u fr ，珂l f ) ( u r fr d ld 1 轧，) b = ( b u lb l dm r 打u ) ( 乩b lb d6 r ) ( t 2 6l d bd r br u b ) ( u bl bd br 6 ) ( u 6 rl b ud b lr b d ) l = ( 2 t | ，z ，dl d bl b u ) ( i t ll ，l dl b ) ( t i l ll d ld b lb u o ( u l ，ld lb o ( u l bi l ud qb i d ) r = p ，u r u br b dr d ，) ( 7 ur br d7 ，) ( u ，b r ud r bi r d ) ( u 7 b rd r 打) ( 缸6 rb d rd l rl u r ) 如1 2 节介绍的那样，这里各个循环中的x y z 和x y 表示相应的小面类似 地，可以用块置换表示生成元，不过块置换没有小面置换全面，因为小面的 方向这个信息被遗漏了后文将会建立这两者之间的同态。 引理1 3f 5 】( p 3 7 ) 晶中的不相交循环是可交换的 引理1 - 4 【5 】( p 3 8 ) 晶中的所有置换都是一系列不相交循环的乘积 定理1 5 & 中的不相交置换是可交换的 证明：设厂，g 是& 中的不相交置换由引理1 4 ，= ，2 厶，g = g i 9 2 和乃是不相交循环，i 1 ，2 ，几) ，歹 1 ，2 ，m ) 由引理1 3 ，这些循 环是交换的，l g = j f 2 厶夕1 9 2 蜘= g l 仂夕m 如厶= 9 ， 口 推论1 6 魔方群的对面转动是可交换的 证明：在魔方群g = 中，对面转动是不相交的根据定理 1 5 ，对面转动是可交换的，即u d = d u , f b = b e , l r = r l 口 4 群论在魔方中的应用一群论概念在魔方中的应用 1 5 作用，传递性，轨道和本原性 用r 表示魔方的小面集合，鼠表示魔方的块集合，耶表示魔方边块上 的小面集合，嵋表示魔方角块上的小面集合，玩表示魔方的边块集合， 表示魔方的角块集合显然，有： f o = e pu 许，e rnv r = 仍 b 。= e bu ，e bnv b = 口 定理1 7 魔方群g 分别作用在f ，及上 证明：只需将1 3 节中的魔方状态c 换成这里的只，鼠就可以了 推论1 8 魔方群g 分别作用在e f ，v f ，e b ，v s 上 定理1 9 魔方群g 在历，v f ，e 8 ，v b 上的作用是传递的 证明：以d z 角块为例，考虑如下转动：m = f f f d b b b d 一，则d l z 角块沿 着上述路径遍历所有角块，最终回到起点于是中任意两个元素都可以 在g 的作用下传递，从而g 在上的作用是传递的类似地，可以证明g 在e f ，v f ，e b 上的作用也是传递的实际上，只需找到一条遍历所有元素的 路径，就证明了传递性口 魔方群g 在只，b 。上却不是传递的因为角块不能传递到边块，角块上 的小面也不能传递到边块上的小面，反之亦然 推论1 1 0 魔方群g 在r 上有两个轨道：e f 和j 在b 。上有两个轨道： 玩和 定义1 1 l 群g 在集合q 上是传递的，称q 的子集是非本原块，如果 v g g ，n g ( a ) = 或d 如果非本原块只是单点集和q ，则称g 是本原 的，否则称为非本原的 5 群论在魔方中的应用 一 群论概念在魔方中的应用 定理1 1 2 魔方群g 在e f ，v f 上的作用是非本原的 证明：设同一边块上两个小面组成的子集是，在g g 的作用下，若该边 块的位置发生变化，则n g ( h ) = 口，否则a n g ( h ) = ，从而是非本原 块另外1 生成的置换群， g 关于x 的c a y l e y 图是图( ve ) ，其中y 是g 中的元素，边由以下条件决 定：如果z ，y v = g ，则z 和y 有边相连当且仅当y = g i x 或者z = 职弘i 1 ，2 ，扎) 定理3 7 【5 】( p 1 1 7 ) r g = ( ve ) 表示关于置换群g = 的c a y l e y 图则v 钉kd e g ( v ) = i g l ，g i - 1 ，9 2 ，万1 ，g , ，簖1 根据定理3 7 ，魔方群g = 的c a y l e y 图中任意顶点的 度数是1 2 1 3 群论在魔方中的应用 三 魔方拜c a y l e y 图直径的下界 定义3 8 群g = 中的任意元素可以表示成生成元及其逆的 乘积：g = g i l g i 2 g i 七如果g 不能写成比k 个元素更少的乘积形式，称g 是 不可缩减的，这时称七为该元素g 的长度特别规定单位元的长度为0 3 2 基本性质 定理3 9 设r g = ( ve ) 是魔方群g 关于 阢d ，只b ，厶r ) 的c a y l e y 图，则 v 钐，叫kj 让k 使得d ( v ，伽) = d ( 1 ，t ) 证明：不妨设d ( 御，伽) = n ，则v g l 9 2 g n = t i ，g l 沪1 ，d 士1 ，f 士1 ，b “，l 士1 ，r 圭1 ， i 1 ，2 ，竹) 取 i l = 口一1 t l j 即可 口 推论3 1 0d i a m ( f a ) = m a x d ( 1 ，t ，) ，臼y ) 由推论3 1 0 ，魔方群c a y l e y 图的直径等于离单位元最远的点到单位元的 距离用g ( 神表示魔方群g 中长度为竹的元素集合 定理3 1 1a ( i ) n g 0 ) = d ，i j i 定理3 1 2g = u 刍g ( 嘞 推论3 1 3l g i = 函i g ( , 0 1 确定魔方群c a y l e y 图的直径实际上等同于找到使得i g ( 礼) l 0 且 i g ( n + 1 ) i = 0 但是直接计算 g ( n ) l 十分困难，尤其是当扎十分大的时候考 虑一个相对容易确定的集合近似估计l g ( n ) i 定义如下集合： x ( 礼) = g i 9 2 9 h lg i 【厂士1 ，d 士1 ，f 士1 ，b 士1 ，l 士1 ，j 净1 ) ，i 1 ，2 ，礼) ) ， 特别地，令x ( o ) = 1 ) 定理3 1 4i g ( 礼) i i x ( 他) i 推论3 1 5 若函j x ( i ) l i g l 铷n + ll x ( i ) l ，则魔方群c a y l e y 图的直径至少 是n + 1 1 4 群论在魔方中的应用 三 魔方群c a y l e y 图直径的下界 3 3 魔方群c a y l e y 图直径的下界 【4 1 中给出了一种确定下界的方法：剔除x ( n ) 中可缩减的元素，然后对 x ( n ) 的元素个数求和，再与l g i 比较大小，从而确定下界本文在此基础上 做了改进，得到下界是2 l 的结果 定义3 1 6 在x ( n ) 中，设m m ，m 2 u 士1 ，d 士1 ，f 士1 ，b 士1 ，l 士1 ，r 士1 满足条 件m m 一1 = 1 的叫做单位重复；满足条件m 2 = m 一2 的叫做对合重复；满足 条件 华1 研1 = 埘1 砰1 ，其中尬和是对面转动的叫做交换重复；满足 条件m 3 = m 一1 的叫做逆元重复 定理3 1 7 魔方群c a y l e y 图直径的下界是2 l ， 证明：当n = 0 时，显然i x ( o ) l = 1 当n = 1 时，由定理3 。7 ，从单位元出发，有1 2 个点与单位元相连接，从 而j x ( 1 ) i = 1 2 当，, - , - - - 2 时，剔除单位重复，由x ( 1 ) 向外扩散的新元素是1 1xi x ( 1 ) 1 个 对合重复共有6 个；交换重复共3 对，每对有2 2 = 4 个重复，共3 4 = 1 2 个重复这样，i x ( 2 ) i = 1 1 i x ( 1 ) i - 6 1 2 = 1 1 4 当n = 3 时，剔除单位重复，由x ( 2 ) 向外扩散的新元素是1 1xi x ( 2 ) 1 个对 合重复只有5 种情况，设x 0 ) 中某元素的末转动是m ，则m m - 1 m _ 1 = m m m 这种情况不可能出现，因为其包含在了单位重复中，于是对合重复的总个数 是5 x i x 0 ) 1 另外，交换重复有1 0 种情况，设x ( 1 ) 中某元素的末转动是m ， 对面转动是，则m 1 m 1 - 1 研1 = m 砑1 圻1 这种情况不可能出现，因为其 同样包含在了单位重复中，于是交换重复的总个数是1 0xi x ( 1 ) 1 最后，逆元 重复有1 2 个这样，i x ( 3 ) i = 1 1xi x ( 2 ) i _ 5 i x ( 1 ) i 一1 0xi x 0 ) i 一1 2 = 1 0 6 2 。 当n = 4 时，单位重复，对合重复，交换重复与n = 3 时类似逆元重复有l o 种情况，设x ( 1 ) 中某元素的末转动是m ，则m m 3 = m m 一1 和m m 一3 = m m 1 5 群论在魔方中的应用 三 魔方群c a y l e y 图直径的下界 这两种情况不可能出现，因为其包含在单位重复中，于是逆元重复的总个数 是1 0xi x ( 1 ) 1 i x ( 4 ) i = 1 1 l x ( 3 ) i 一5xi x ( 2 ) i 一1 0xi x ( 2 ) i 一1 0xl x ( 1 ) l = 9 8 5 2 当n 4 时，一般的递推公式是： i x ( n ) i = 1 1 i x ( n 一1 ) i 一5xi x ( n 一2 ) i 一1 0 i x ( n 一2 ) l 一1 0xi x ( n 一3 ) 1 其中，等式右边的第一项表示在剔除单位重复的情况下扩散的新元素 个数，第二项表示剔除对合重复，第三项表示剔除交换重复，第四项表示剔 除逆元重复经过计算，有： 銎oi x ( n ) i 3 3x1 0 1 9 l g l 4 3x1 0 t m 脚2 1i x ( n ) l 2 4 1 0 2 0 ， 根据推论3 1 5 ，魔方群c a y l e y 图的直径至少是2 1 口 评注：上述方法只是把最简单的重复情况考虑了，实际上还有很多比较 复杂的重复情况存在设m ，是对面转动，聊聊= m s 这种重复情 况就没有出现在上述考虑中另外聊= 舰m = m s 聊也是上述方 法没有考虑到的重复情况理论上说，如果把所有的重复情况都剔除了，则 g ( 佗) = x ( n ) 如果尽可能地剔除重复的元素，估计下界还有进一步上升的空 间，只是要考虑的情况非常复杂，需要细致全面的分析 1 6 群论在魔方中的应用四未解决的问题 四未解决的问题 j o y n e r 在其著作【5 】的末章列举了一些关于魔方的未解决的问题，现转 述于此： 问题4 1 ( 上帝的算法，s i n g m a s t e r ) 确定魔方群c a y l e y 图的直径 这是关于魔方的最著名问题，自s i n g m a s t e r 在1 9 8 2 年提出后2 6 年来没 有得到解决由于近10 年科技的迅猛发展，一些人开始用高速计算机求解 该问题，获得了不错的结果 定义4 2r 是个图，r 上的h a m i l t o n 巡回是指恰好经过每个点一次的路 径如果h a m i l t o n 巡回存在，则称r 是h a m i l t o n 图 问题4 3 ( s c h w e n k ) 魔方群c a y l e y 图是否为h a m i l t o n 图? 问题4 4 ( s i n g m a s t e r ) 确定魔方群每个阶的元素个数 问题4 3 实际上即是确定魔方群的阶方程所谓阶方程就是把群的元素 按照阶进行分类的表达式 定义4 5g 是置换群，元素g g 的长度记作z ( 夕) ，定义g 的p o i n c a r d 多项 式为：忍( z ) = g e e t 。( 鲋 问题4 6 计算魔方群的p o i n c a x d 多项式 定义4 7g 的共轭类集合记作g 。，g g 的阶记作d ( 9 ) ，定义g 上的生成多项 式为：r 。( t ) = 9 以t o ( 引 问题4 8 计算魔方群的生成多项式 1 7