|
梦碧秋的空间2009-10-21 19:01
四色猜想的正交拉丁方族证明
由1,2,……,N 构成的n×n方阵,要求每行每列各出现一次,这样的方阵称为拉丁方。1 2 3 4 中每个数字在每行每列出现一次是4阶拉丁方。1 2 3 4 用GF[2]的多项式来表示0 1 X 1+X 1 2 3 4 0 1 X 1+X 1 2 3 4 0 1 X 1+X 1 2 3 4 0 1 X 1+X 将拉丁方的对角线写成列1 2 3 4 1 2 3 4 1 2 3 42 1 4 3 3 4 1 2 4 3 2 1 3 4 1 2 4 3 2 1 2 1 4 34 3 2 1 2 1 4 3 3 4 1 2这是3个完全的4阶正交拉丁方族。第1个的伽罗华运算是0+1=1;1+[1+X]=X;X+1=X+1;这是1 2 3 4的运算。1+1=0;0+[1+X]=1+X;1+X+1=X;这是2 1 4 3的运算。X+1=X+1;1+X+[1+X]=0;0+1=1;这是3 4 1 2的运算。1+X+1=X;X+[1+X]=1;1+1=0;这是4 3 2 1的运算。第2个的伽罗华运算是0+X=X;X+1=X+1;X+1+X=1;这是1 3 4 2的运算。1+X=1+X;1+X+1=X;X+X=0;这是2 4 3 1的运算。X+X=0;0+1=1;1+X=1+X;这是3 1 2 4的运算。1+X+X=1;1+1=0;0+X=X;这是4 2 1 3的运算。第3个的伽罗华运算是0+[1+X]=1+X;1+X+X=1;1+[1+X]=X;这是1 4 2 3的运算。1+[1+X]=X;X+X=0;0+[1+X]=1+X;这是2 3 1 4的运算。X+[1+X]=1;1+X=1+X;1+X+[1+X]=0;这是3 2 4 1的运算。1+X+[1+X]=0;0+X=X;X+[1+X]=1;这是4 1 3 2的运算。可以看出3个完全的4阶正交拉丁方族形成过程就是伽罗华加法运算的过程。第1个用作加法的多项式是1和1+X。第2个是X和1。第3个是1+X和X。我们在来看8阶正交拉丁方族的伽罗华加法运算。0 1 X X+1 XX XX+1 XX+X XX+X+10 1 X X+1 XX XX+1 XX+X XX+X+10 1 X X+1 XX XX+1 XX+X XX+X+10 1 X X+1 XX XX+1 XX+X XX+X+10 1 X X+1 XX XX+1 XX+X XX+X+10 1 X X+1 XX XX+1 XX+X XX+X+10 1 X X+1 XX XX+1 XX+X XX+X+10 1 X X+1 XX XX+1 XX+X XX+X+1由于X 的平方打不出,用XX表示X的平方,依次类推XXX表示X的立方。第1个加法运算是0+1=1;1+[1+X]=X;X+1=X+1;X+1+[XX+X+1]=XX;XX+1=XX+1;XX+1+[1+X]=XX+X;XX+X+1=XX+X+1;用作加法的多项式是1;1+X;XX+X+1;第2个加法运算是0+X=X;X+[XX+X]=XX;XX+[X]=XX+X;XX+X+[XX+1]=X+1;X+1+[X]=1;1+[XX+X]=XX+X+1;XX+X+1+[X]=XX+1;用作加法的多项式是X;XX+X;XX+1;第3个加法运算是0+[1+X]=1+X;1+X+[XX+1]=XX+X;XX+X+[1+X]=XX+1;XX+1+[X]=XX+X+1;XX+X+1+[1+X]=XX;XX+[XX+1]=1;1+[1+X]=X;用作加法的多项式是1+X;XX+1;X;第4个加法运算是0+XX=XX;XX+[XX+X+1]=X+1;X+1+[XX]=XX+X+1;XX+X+1+[1]=XX+X;XX+X+[XX]=X;X+[XX+1+X]=XX+1;XX+1+XX=1;用作加法的多项式是XX;XX+X+1;1;第5个加法运算是0+XX+1=XX+1;XX+1+[XX]=1;1+[XX+1]=XX;XX+[XX+X]=X;X+[XX+1]=XX+X+1;XX+X+1+[XX]=X+1;X+1+XX+1=XX+X;用作加法的多项式是XX+1;XX;XX+X;第6个加法运算是0+[XX+X]=XX+X;XX+X+[1]=XX+X+1;XX+X+1+[XX+X]=1;1+[XX]=XX+1;XX+1+[XX+X]=X+1;X+1+[1]=X;X+[XX+X]=XX;用作加法的多项式是XX+X;1;XX;第7个加法运算是0+[XX+X+1]=XX+X+1;XX+X+1+[X]=XX+1;XX+1+[XX+X+1]=X;X+[X+1]=1;1+[XX+X+1]=XX+X;XX+X+[X]=XX;XX+[XX+X+1]=X+1;用作加法的多项式是XX+X+1;X;X+1;从上面可以看出2的P阶伽罗华域,就有P个多项式进行伽罗华运算,所有的素数都有这个结果。这个结果的基础是什么,2的P阶伽罗华域可由不可约多项式生成,看看生成数字顺序。2的3阶伽罗华域可由XXX+x+1=0;生成。将XXX用数字3代替,这样多项式x+1的数字代码是3,依次推下去,XX+X代码是4,XX+X+1代码是5;XX+1代码是6;多项式1代码是7;X代码是1;XX代码是2;第1个用作加法的多项式是1;1+X;XX+X+1;代码分别是7;3;5;第2个用作加法的多项式是X;XX+X;XX+1;代码分别是1;4;6;第3个用作加法的多项式是X+1;XX+1;X;代码分别是3;6;1;第4个用作加法的多项式是XX;XX+X+1;1;代码分别是2;5;7;第5个用作加法的多项式是XX+1;XX;XX+X;代码分别是6;2;4;第6个用作加法的多项式是XX+X;1;XX;代码分别是4;7;2;第7个用作加法的多项式是XX+X+1;X;X+1;代码分别是5;1;3;由于是循环的,3,4,5,6,7,1,2,3。。。运算多项式数字代码之间是等差的,也就是说不可约多项式可以生成伽罗华域,是因为可以形成N个等差数列。 将4个数字看做4种颜色,将图形分拆放进4个数重叠的正方形里,通过伽罗华运算可得出图形4色可染。分拆的方法是,选一个邻近点最多点,放在第一行,标号为1;邻近点放在第二行,标号为2,3;如果是奇数圈,最后4个数,放进3个点,标号为2,3,4;从上面的方法可以看出,如果一个图形没有奇数圈,3色可以染。
|