用AI发现群论中赛利格图的新猜想，速度超传统工具百倍。
CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs (Brief version)
- 开发开源库CayleyPy，高效计算赛利格图与增长函数。
- 提出对称群直径的拟多项式公式，证实15以内最大直径生成元。
- 适合群论、算法优化和大模型验证的研究者参考。
本是CayleyPy项目第三篇论文，将人工智能应用于群论问题。首次公开发布CayleyPy，一个用于赛利格图与施莱尔图计算的开源Python库。相比GAP和Sage，CayleyPy能处理更大图且速度快数个数量级。利用该工具，我们获得约200个新猜想，聚焦于图的直径与增长。对对称群Sn的许多赛利格图，观察到直径呈拟多项式形式：一组由n mod s索引的二次或线性多项式。我们推测这是普遍现象，可实现尽管问题是NP难的高效直径计算。提出对巴拜型猜想的改进：在无向情形下，直径上界为n²/2 + 4n，优于此前O(n²)结果。还提供一组显式生成元，与“带胡须的正方形”对合相关，猜想其使直径最大化；搜索确认在n≤15时成立。进一步回答了1968年格鲁什科夫提出的关于循环移位与换位生成的有向赛利格图问题。对幂零群，猜想对椭圆矩阵群上界的改进，显示直径与素数p呈线性依赖。部分猜想适合大语言模型验证，自然表述为可算法检验的排序问题。为路径查找基准，创建超10个Kaggle数据集。CayleyPy支持任意置换群或矩阵群，含超过100个预定义生成元。其增长计算代码比GAP和Sage快达1000倍，且处理规模更大。
原文摘要 · Abstract (English)
This is the third paper of the CayleyPy project applying artificial intelligence to problems in group theory. We announce the first public release of CayleyPy, an open source Python library for computations with Cayley and Schreier graphs. Compared with systems such as GAP and Sage, CayleyPy handles much larger graphs and performs several orders of magnitude faster. Using CayleyPy we obtained about 200 new conjectures on Cayley and Schreier graphs, focused on diameters and growth. For many Cayley graphs of symmetric groups Sn we observe quasi polynomial diameter formulas: a small set of quadratic or linear polynomials indexed by n mod s. We conjecture that this is a general phenomenon, giving efficient diameter computation despite the problem being NP hard. We propose a refinement of the Babai type conjecture on diameters of Sn: n^2/2 + 4n upper bounds in the undirected case, compared to previous O(n^2) bounds. We also provide explicit generator families, related to involutions in a square with whiskers pattern, conjectured to maximize the diameter; search confirms this for all n up to 15. We further conjecture an answer to a question posed by V M Glushkov in 1968 on directed Cayley graphs generated by a cyclic shift and a transposition. For nilpotent groups we conjecture an improvement of J S Ellenberg's results on upper unitriangular matrices over Z/pZ, showing linear dependence of diameter on p. Some conjectures are LLM friendly, naturally stated as sorting problems verifiable by algorithms or Python code. To benchmark path finding we created more than 10 Kaggle datasets. CayleyPy works with arbitrary permutation or matrix groups and includes over 100 predefined generators. Our growth computation code outperforms GAP and Sage up to 1000 times in speed and size.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。