CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs (Brief version)

• URL: http://arxiv.org/abs/2509.19162v1
• Date: Tue, 23 Sep 2025 15:40:36 GMT
• Title: CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs (Brief version)
• Abstract summary: We announce the first public release of CayleyPy, an open source Python library for computations with Cayley and Schreier graphs.<n>Compared with systems such as GAP and Sage, CayleyPy handles much larger graphs and performs several orders of magnitude faster.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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. Moreover. 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.

Related papers

• AutoGraphForge: Towards Automated Graph Theory Discovery [0.0]
  AutoGraphForge is an automated graph-theoretic conjecturing-refuting-formalizing-trivial system.<n>A novelty filter decides via a linear program whether a candidate is already implied by known results.<n>Run for several rounds on an HPC cluster, the loop yields $6,522$ conjectures that survived the refutation dataset.
  arXiv  Detail & Related papers  (2026-09-03T07:35:29Z)
• CayleyR: Solving the TopSpin puzzle via cycle intersection [0.0]
  We present cayleyR, an R package for solving permutation puzzles by detecting cycle intersections in Cayley graphs.<n>We describe the mathematical framework, the algorithm, and its implementation, which combines a C++ hash-indexed state store with optional Vulkan GPU acceleration.
  arXiv  Detail & Related papers  (2026-07-14T19:28:41Z)
• CayleyPy-4: AI-Holography. Towards analogs of holographic string dualities for AI tasks [0.0]
  This is the fourth paper in the CayleyPy project, which applies AI methods to the exploration of large graphs.<n>We suggest the existence of a new discrete version of holographic string dualities for this setup.
  arXiv  Detail & Related papers  (2026-03-23T16:54:44Z)
• The Geometry of LLM Quantization: GPTQ as Babai's Nearest Plane Algorithm [52.89358421626026]
  GPTQ emerged as one of the standard methods for one-shot post-training quantization at LLM scale.<n>We show that GPTQ is mathematically identical to Babai's nearest plane algorithm for the classical closest vector problem.
  arXiv  Detail & Related papers  (2025-07-24T16:22:18Z)
• Diffusion Models for Cayley Graphs [0.0]
  We show how to formulate problems in the framework of diffusion models.<n>We propose a reversed score'' ansatz which substantially improves over previous comparable algorithms.
  arXiv  Detail & Related papers  (2025-03-07T16:33:16Z)
• CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs [0.0]
  This paper is the second in a series of studies on developing efficient artificial intelligence-based approaches to pathfinding on large graphs.<n>We present a novel combination of a reinforcement learning approach with a more direct diffusion distance approach from the first paper.<n>We provide strong support for the OEIS-A186783 conjecture that the diameter is equal to n(n-1)/2 by machine learning and mathematical methods.
  arXiv  Detail & Related papers  (2025-02-25T21:53:41Z)
• Imaginary Hamiltonian variational ansatz for combinatorial optimization problems [3.14105061893604]
  We introduce a tree arrangement of the parametrized quantum gates, enabling the exact solution of arbitrary tree graphs using the one-round $i$HVA.<n>Our ansatz solves MaxCut exactly for graphs with up to 24 nodes and $D leq 5$, whereas only approximate solutions can be derived by the classical near-optimal Goemans-Williamson algorithm.
  arXiv  Detail & Related papers  (2024-08-17T03:34:17Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  Sponge hashing is a widely used class of cryptographic hash algorithms.<n>Intrepid permutations have so far remained a fundamental open problem.<n>We show that finding zero-pairs in a random $2n$-bit permutation requires at least $Omega (2n/2)$ many queries.
  arXiv  Detail & Related papers  (2024-03-07T18:46:58Z)
• Large-Plaintext Functional Bootstrapping in FHE with Small Bootstrapping Keys [1.6319731389952283]
  Functional bootstrapping is a core technique in Fully Homomorphic Encryption (FHE) In this paper, we propose to encode the look-up table of any function in a vector, whose coefficients can hold more data. The new algorithm has the prominent benefit of small key size and small key-switching key size, which leads to factor improvement in key size and constant factor improvement in run-time cost.
  arXiv  Detail & Related papers  (2023-10-19T03:30:36Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  We find a generalization-time algorithm that finds the RUM that best approximates the given distribution on average. Our theoretical result can also be made practical: we obtain a that is effective and scales to real-world datasets.
  arXiv  Detail & Related papers  (2023-05-22T17:43:34Z)
• The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model [0.0]
  The Quantum Approximate Optimization Algorithm (QAOA) finds approximate solutions to optimization problems. We give an iterative formula to evaluate performance for any $D$ at any depth $p$. We make an optimistic conjecture that the QAOA, as $p$ goes to infinity, will achieve the Parisi value.
  arXiv  Detail & Related papers  (2021-10-27T06:35:59Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  This work considers a large family of bandit problems where the unknown underlying reward function is non-concave. Our algorithms are based on a unified zeroth-order optimization paradigm that applies in great generality. We show that the standard optimistic algorithms are sub-optimal by dimension factors.
  arXiv  Detail & Related papers  (2021-07-09T16:04:24Z)
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams [69.4411417775822]
  Adversarial examples are a widely studied phenomenon in machine learning models. We propose an algorithm for evaluating the adversarial robustness of $k$-nearest neighbor classification.
  arXiv  Detail & Related papers  (2020-11-19T08:49:10Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  We show that families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
  arXiv  Detail & Related papers  (2020-04-25T05:45:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.