完美循环差集

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 的构造