CayleyPy: Scalable Computation and Conjecture Discovery for Cayley and Schreier Graphs

We present the first public release of CayleyPy, an open-source Python library for large-scale computation with Cayley and Schreier graphs. Unlike general-purpose computer algebra systems such as GAP and Sage, CayleyPy is optimized for massive graph exploration and enables computations on instances far beyond the practical range of existing tools, with orders-of-magnitude speedups in our experiments. The library forms the computational backbone of an AI-assisted conjecture-discovery pipeline that combines fast graph algorithms with reinforcement-learning-guided search over generating sets. Using CayleyPy, we obtain approximately 200 new conjectures on diameters and growth functions of Cayley and Schreier graphs. Our main empirical discovery is a quasi-polynomiality phenomenon for Cayley graphs of symmetric groups: for many natural families of generators, the diameter appears to be governed by a small collection of linear or quadratic polynomials indexed by congruence classes of n mod s. We formulate this as a general quasi-polynomiality hypothesis, suggesting that structured diameter problems may admit efficient closed-form solutions despite the general computational hardness of diameter computation. We further propose a sharpened Babai-type conjecture for undirected Cayley graphs of symmetric groups, predicting that every undirected Cayley graph of permutation group has diameter at most n^2/2 + 4n. This improves the expected constant in known (O(n^2))-type bounds. Our reinforcement-learning-guided searches identify explicit candidate extremal generator families, related to involutions arranged in a “square with whiskers” pattern, and exhaustive search verifies their optimality among tested instances for all (n \leq 15). We also 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. Finally, for nilpotent groups, we formulate conjectural improvements to results of J.S.Ellenberg on upper unitriangular groups, predicting linear dependence of the diameter on p. Together, these results demonstrate how scalable symbolic-combinatorial software and reinforcement learning can support systematic conjecture discovery in group theory.