完美循环差集

hujunhua

完美循环差集 本文中的小写字母皆表整数。 一、 问题描述 这是一个从几何图形——正多边形中抽出的组合数论问题。我们从两个较小的例子说起。 先交代一下完全n点形的概念：由平面上n点及其两两连线——称为边构成的图形。 例1（正7边形）正完全7点形的21条边（图1只画出了其中正7边形的边）有3种不同的长度，其子图△124刚好包含3种长度的边。 例2（正13边形）图2，正完全13点形含有6种长度的边，其子图完全4点形0146的6条边刚好不同长度各占一条。并且另有一种不全等的完全4点形0139也具有这种性质。 推广到一般情况，当m= n(n-1)+1时, 正完全m点形`G_m`含有C(n,2)种长度的边，要求在`G_m`中寻找一个完全n点形子图，恰好含有不同长度的边各一条。 这的确是一个美妙的“巧合”，值得一番探究。 考虑正m边形的外接圆，设圆周长为m. 由于等弧对等弦，改用弧长代替弦长，问题转述为：取正m边形的n个顶点，将以其中任意两点为端点的弧长，包括劣弧和优弧归入集C，能否恰好使C={1, 2, 3, …, m-1}。弧ab之长可简单地表为顶点的标号之差a-b(mod m)或者b-a(mod m)。模余函数Mod(x, m)默认取最小正余数，a-b(mod m)或者b-a(mod m)自动地一为劣弧，一为优弧。可见问题实际上属于组合数论，用数论的语言来说，就是要求在m的完全剩余系`Z_m`中取一个n元子集A，使得A中任意两个不同的数之差互不同余，恰好生成{1,2,3,...,m-1}。 这样的 n 元子集称为完美循环差集（感谢shshsh_0510指出正确的名称，感谢Wiley提供链接） 例1中，对于`Z_7`取A={1, 2, 4}，可以验证 1=2-1 2=4-2 3=4-1 4=-3=1-4 5=-2=2-4 6=-1=1-2 例2中，对于`Z_{13}`取A={0, 1, 4, 6}, 可以验证（由例1可知仅需考察绝对值较小的一半） 1=1-0 2=6-4 3=4-1 4=4-0 5=6-1 6=6-0 或取A={0, 1, 3, 9}, 可以验证: 1=1-0 2=3-1 3=3-0 -4=9-0 -5=9-1 6=9-3 二、基本性质 对于特定的n和m，设全部解集为`S_m=\{A_i\}=\{A_1, A_2, …，A_l\}`, 以下两条性质是显然的： 性质1（旋转变换）：A是一解，则A + r(表示所有顶点坐标同时加r）亦是一解。 性质2（伸缩变换）：A是一解，则 kA 亦是一解。这里(k,m)=1. 所以对例1中的标号7可以取为0，A={1, 2, 4}可以变得像例2那样从0开始，即{0, 1, 3}。一般而言，任意解A={a1, a2, … , an}总可以变换成{b1=0, b2=1, b3,…, bn}，故以下进行计算搜索时预设如此。 定义1（同形解）若两个解A和B存在变换关系B=A+r, A和B即为同形解，记为A≌B. 易证: 性质3 任意解都不是旋转自对称的。即不可能成立A=A+r, r≠0. 因此，从任一解出发，都可以变换生成 m 个同形解（包括自身），它们组成一个同形类。 定义2（仿射解）若两个解A，B存在变换关系B=kA+r, A与B即为仿射相关，互称仿射解。 同样，从任一解出发，可以变换生成`S_m`的一个仿射类。 k=-1时的仿射变换称为反射，A与B互称反射解。 定义3（不动点）若kA=A, A即称为解空间`S_m`在伸缩变换k下的不动点。k 称为Zm的特征值。 比如在例1中，有2{1,2,4}={1,2,4},在例2中，有3{0,1,3,9}={0,1,3,9}. 引理1 k 为`Z_m`的特征值，A是相应的不动点，那么仿射类（A）中的任意解`A_i` 在缩放倍数为k的仿射变换作用下都是自相关的，即总有`kA_i=A_i+r_i`. 三、计算更多的例子 在进行计算搜索时，对于每个仿射类只需要搜到一个代表就行了，但是我没有找到搜索时避免一般仿射重复的算法。但对于同形类和反射解，容易避免搜索重复，只需要预设为 `A=\{a_1=0, a_2=1, a_3,\cdots, a_n\}`，(`2≤a_3-1≤m-a_n` 排除反射解） 例3 n=5, m=21, 计算结果为A={0, 1, 4, 14,16}. 特征值k=4, A及其缩放都是S21的不动点。 例4 n=6, m=31, 计算结果为5个同形类, 特征值k=5 A1= {0, 1, 3, 10, 14, 26} A2= {0, 1, 3, 8, 12, 18} A3= {0, 1, 4, 6, 13, 21} A4= {0, 1, 4, 10, 12, 17} A5= {0, 1, 8, 11, 13, 17} 例5 n=7, m=43, 计算结果无解。 例6 n=8, m=57, 计算结果为6个同形类，特征值k=7 A1= {0, 1, 3, 13, 32, 36, 43, 52} A2= {0, 1, 4, 12, 14, 30, 37, 52} A3= {0, 1, 4, 9, 20, 22, 34, 51} A4= {0, 1, 5, 7, 17, 35, 38, 49}（不动点） A5= {0, 1, 5, 27, 34, 37, 43, 45} A6= {0, 1, 7, 19, 23, 44, 47, 49}（不动点） 例7 n=9, m=73, 计算结果得到4个不同形状的解,特征值k=2 A1= {0, 1, 3, 7, 15, 31, 36, 54, 63}, 易观察到A1+1为不动点。 A2= {0, 1, 5, 12, 18, 21, 49, 51, 59} A3= {0, 1, 12, 20, 26, 30, 33, 35, 57} A4= {0, 1, 7, 11, 35, 48, 51, 53, 65} 例8 n=10, m=91, 计算结果无解。 四、特征值和不动点分析 1、m=7和73时，都有特征值k=2, 相应的不动点分别为 m=7时，为{1，2，4} m=73时为{1，2，4，8，16，32，37，55，64}，(注意37≡256，55≡128)。 在这两例中，不动点内为一整个循环节，特征值2对m的指数刚好等于n，为循环节之长. 2、m=13, 特征值k=3, 不动点{0，1，3，9}分为2个轨道{0}和{1，3，9}。 3、m=21=3×7, 特征值k=4, 不动点{0, 1, 4, 14, 16}分为3个轨道{0}，{14}和{1, 4, 16}。 4、m=31, 因5A1=A1+5，得特征值k=5，易得A=A1-9为不动点. A=A1-9={1, 5, 17, 22, 23, 25}={1, 17}×{1, 5, 25}（即分为2个轨道）。 5、m=57=3×19, 特征值k=7, 不动点A4= {0, 1, 5, 7, 17, 35, 38, 49}={0}U{38}U({1, 5}×{1, 7, 49})（即分为2个轨道）. 五、问题和下一步研究方向 1、现在的例子都只有一个仿射类，是否对所有有解的情况，都只有一个仿射类？ 2、什么样的n和m有解？给出无解的n和m序列，提交到那个数列网站。 3、同形类和仿射类的类数公式总结 4、避免仿射重复的搜索算法。在目前的例子中, n-1都是特征值（易证 n-1 对m的指数都是3)。如果这是一般成立的，应可以找到更好的算法。 结后语： n=10,m=91时无解的结论99%是正确的，因为我的电脑计算了16个小时都没打印出一个解来，我相信无解中断计算了。

shshsh_0510

4、n=10,m=91时无解的结论99%是正确的，因为我的电脑计算了16个小时都没打印出一个解来，我相信无解中断计算了。

99%是错误的，才16小时 最小循环差集

wiley

Perfect Difference Set 记得mathe已经回答过这个问题: 一个充分条件是n-1是素数的幂, 然后用Sidon Set来构造. n=10, m=91 {0,1,6,10,23,26,34,41,53,55}

hujunhua

原来叫着“完美循环差集”，谢谢shshsh_0510和wiley. 这下子找到了不少资料。

hujunhua

根据3#给出的这个解{0,1,6,10,23,26,34,41,53,55}，计算了一下其它同形类，发现特征值k=3，不动点 `A=\{0,1,3,9,27,49,56,61,77,81\}=\{0\}\cup49\cdot\{1, 3, 9\}\cup\{1, 3, 3^2, 3^3, 3^4, 3^5\}`(3个轨道).

hujunhua

本因坊算帐

m边形中有完全n点形，那么把这个n边形沿圆周旋转一个单位，可以证明，和原n边形没有公共的边或者对角线，有且仅有一个公共顶点 依次旋转1，2，…… m-1个单位，加上原来的，共得到m个n边形，它们的边和对角线恰好构成了m边形的边和对角线的一个覆盖 换句话说，本贴的题目蕴含了用 完全kn 覆盖 km 的构造