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

This paper introduces CayleyPy, a high-performance open-source Python library that significantly outperforms existing systems in computing Cayley and Schreier graph growth, enabling the discovery of approximately 200 new conjectures on diameters and growth patterns across various group structures.

The Gist

Imagine you are trying to solve a giant, complex puzzle. Maybe it's a Rubik's Cube, a sliding tile game, or even rearranging a deck of cards. In mathematics, these puzzles are often represented as Cayley Graphs.

Think of a Cayley Graph as a massive, multi-dimensional maze.

• The Rooms: Every possible arrangement of your puzzle (every way the cards can be shuffled) is a room.
• The Doors: The moves you are allowed to make (like "swap card 1 and 2" or "rotate the top layer") are the doors connecting the rooms.
• The Goal: You want to get from a messy starting room to a perfectly sorted "home" room using the fewest possible doors.

The Diameter of this maze is the length of the longest possible path you might have to take to get from the messiest room to the cleanest one. It's the "worst-case scenario" for how hard the puzzle is.

The Problem: The Maze is Too Big

For simple puzzles, we can map the whole maze. But for complex ones (like shuffling a deck of 52 cards), the number of rooms is so huge (a "googol" or more) that even the world's most powerful supercomputers get stuck. Traditional math software (like GAP or Sage) is like a very smart, but slow, librarian who tries to check every single book one by one. It takes them days or years to solve problems that a modern AI could solve in seconds.

The Solution: CayleyPy (The AI Explorer)

The authors of this paper built a new tool called CayleyPy. Think of it as a team of super-fast, AI-powered explorers equipped with high-tech flashlights and drones.

• Speed: Instead of walking through the maze, they can "teleport" and scan millions of rooms at once using Graphics Processing Units (GPUs)—the same chips that make video games look realistic.
• Efficiency: They are up to 1,000 times faster than the old tools. They can explore mazes that were previously impossible to map.

What Did They Discover?

By using this new tool, the team didn't just solve a few puzzles; they looked at nearly 50 different types of mazes and found 200 new mathematical guesses (conjectures). Here are the most exciting ones, explained simply:

1. The "Quasi-Polynomial" Pattern (The Magic Formula)

Mathematicians have always struggled to predict the diameter of these mazes because it's usually a nightmare to calculate.

• The Discovery: The team found that for many types of puzzles, the answer isn't random chaos. Instead, it follows a simple, repeating pattern based on the size of the puzzle.
• The Analogy: Imagine that for a 10-piece puzzle, the answer is $X$. For an 11-piece puzzle, it's $Y$. You might expect the numbers to jump around wildly. But the team found that the answers follow a smooth curve (like a parabola) that just shifts slightly depending on whether the number of pieces is even or odd.
• Why it matters: This means we can now predict how hard a puzzle will be for a huge number of pieces just by looking at a few small examples, without having to solve the whole thing.

2. The "Square with Whiskers" (The Perfect Puzzle Design)

The team asked: "What is the absolute hardest puzzle we can build?"

• The Discovery: They found that the hardest mazes are created by specific types of moves that look like a square with two little branches sticking out (like a whisker).
• The Analogy: If you are designing a maze to be as confusing as possible, don't just make random doors. Arrange your doors in this specific "square with whiskers" shape. It turns out this shape creates the longest possible paths. They tested this up to size 15 and it held true every time.

3. Solving a 50-Year-Old Mystery (Glushkov's Problem)

In 1968, a famous Soviet scientist named V.M. Glushkov asked a specific question: "If you have a specific set of moves (shifting everything left and swapping the first two), how many moves does it take to sort the worst-case scenario?"

• The Discovery: The team used their AI to calculate this for many sizes and found a perfect formula. They essentially solved a problem that had been open for over 50 years.
• The Result: They provided a precise formula that tells you exactly how hard this specific puzzle is, depending on its size.

4. The "Bell Curve" of Chaos

When you shuffle a deck of cards, most arrangements are "medium" difficulty. Some are very easy, and a few are very hard.

• The Discovery: For certain types of puzzles, the distribution of difficulty looks like a Bell Curve (the classic hill shape in statistics). This means most puzzles are average, and extreme difficulties are rare. This helps mathematicians understand the "shape" of randomness in these groups.

Why Should You Care?

This isn't just about math puzzles. The techniques used here are the same ones used in:

• Robotics: Planning the most efficient path for a robot arm to move without crashing.
• Genetics: Understanding how DNA rearranges itself over millions of years (evolution).
• Artificial Intelligence: Testing if AI can "think" like a mathematician. The authors even created a "Kaggle Challenge" (a public competition) where they ask AI models to try and solve these puzzles. So far, the AI models are struggling, showing that there is still a lot of human-like intuition needed to solve these problems.

Summary

The CayleyPy project is like giving mathematicians a pair of X-ray glasses. They can now see through the fog of massive, complex puzzles, find hidden patterns, and make accurate predictions about how hard they are. They turned a problem that used to take supercomputers years to solve into something that takes seconds, opening the door to solving hundreds of new mathematical mysteries.

Technical Summary

1. Problem Statement

The paper addresses fundamental open problems in group theory and graph theory concerning Cayley graphs of finite groups (specifically symmetric groups $S_n$, alternating groups $A_n$, and matrix groups). Key challenges include:

• Diameter Computation: Determining the diameter (the maximum shortest path between any two nodes) of Cayley graphs is generally NP-hard and often P-space complete.
• Growth Analysis: Understanding the statistical properties of the "growth" of a graph (the number of elements at distance $k$ from the identity), including its distribution, mean, mode, and variance.
• Scalability: Existing computer algebra systems (CAS) like GAP and SageMath struggle with large groups (e.g., $S_{12}$ and above) due to memory and time constraints, limiting the ability to test conjectures on large $n$.
• Open Conjectures: Many specific conjectures regarding diameters (e.g., Babai's conjecture, Glushkov's 1968 problem) remain unresolved due to a lack of computational data for large $n$.

2. Methodology

The authors introduce CayleyPy, an open-source, AI-based Python library designed to overcome the limitations of traditional CAS.

• High-Performance Computing:

  • GPU Acceleration: The library leverages GPUs for parallel processing, utilizing efficient Breadth-First Search (BFS) algorithms.
  • Bitmask Optimization: A specific "bfs-bitmask" algorithm uses 3-bit encoding per state, drastically reducing memory usage (allowing computation on $S_{13}$ with only 3–8 GB RAM).
  • Performance: CayleyPy is reported to be 10 to 1000 times faster than GAP/Sage for growth computations, enabling the analysis of groups up to $S_{15}$ and beyond.

• The "AI Pipeline":

  • The workflow follows a cycle: Computational Experiments $\rightarrow$ Pattern Observation $\rightarrow$ Conjecture Formulation $\rightarrow$ Iterative Verification.
  • While the current release focuses on direct growth computation, it includes preliminary deep learning components (beam search, diffusion models) for path-finding (decomposing group elements into generators).

• Benchmarking:

  • The authors created over 10 Kaggle challenges to benchmark path-finding algorithms on various Cayley graphs, framing the mathematical problems as sorting tasks.
  • They also propose using these problems to test Large Language Models (LLMs) on their ability to invent new sorting algorithms for non-standard generators.

3. Key Contributions

A. The CayleyPy Library

• First public release of an open-source library capable of handling "googol-sized" graphs.
• Supports arbitrary permutation and matrix groups, with built-in collections of over 100 generator sets (including puzzle groups like Rubik's Cube and biological models).
• Provides tools for visualizing graphs, computing spectra, and simulating random walks.

B. The "Quasi-Polynomiality" Conjecture

• Conjecture: The diameter of Cayley graphs for $S_n$ (and $A_n$) generated by algorithmically defined sets is a quasi-polynomial in $n$ (i.e., a set of polynomials indexed by $n \pmod s$).
• Significance: If true, this implies that despite the NP-hard nature of the general problem, diameters for specific structured families can be computed efficiently by fitting data from small $n$ to a polynomial form.

C. Refinement of Babai's Conjecture

• The authors propose a refined upper bound for the diameter of standard undirected Cayley graphs of $S_n$:
  $$\text{diam}(S_n) \leq \frac{n^2}{2} + 4n$$
• This improves upon the previous general $O(n^2)$ conjecture by specifying the leading coefficient ($1/2$) and the linear term.
• They identify specific generator families (related to involutions) that maximize the diameter, following a visual pattern they call "square with whiskers."

D. Solution to Glushkov's Problem (1968)

• They provide a conjectural closed-form solution for the diameter of the directed Cayley graph generated by the left cyclic shift ($L$) and the transposition of the first two elements ($X$):
  • For odd $n$: $\frac{3n^2 - 8n + 9}{4}$
  • For even $n$: $\frac{3n^2 - 8n + 12}{4}$
• This resolves a decades-old open problem in Soviet cybernetics.

E. Nilpotent Groups and Growth Distributions

• Unitriangular Groups: They conjecture a linear dependence of the diameter on the modulus $p$ for unitriangular groups over $\mathbb{Z}/p\mathbb{Z}$, improving on Ellenberg's results.
• Central Limit Phenomenon: They conjecture that the growth distribution for nilpotent groups follows a Gaussian (Normal) distribution, similar to Diaconis' results for $S_n$ with Coxeter generators.

4. Key Results and Data

• Extensive Conjectures: The paper presents ~200 new mathematical conjectures derived from computations on nearly 50 different Cayley/Schreier graphs up to $n=15$ (and $n=42$ for cosets).
• Maximal Diameters:
  • Found maximal diameters for $S_n$ ($n \leq 15$) using generators that follow the "square with whiskers" pattern (involutions).
  • For $n=15$, the maximal diameter found is 148, which aligns closely with their refined bound of 150.
• Biological Applications:
  • Analyzed "Reversals" and "Transposons" (genome rearrangement models).
  • Discovered that on binary cosets (Schreier graphs), the growth of reversals and transposons coincides and follows explicit combinatorial formulas involving binomial coefficients.
• LLM Performance: Current LLMs fail to generate correct sorting algorithms for non-standard generators, highlighting a gap in AI's ability to solve novel research problems in this domain.

5. Significance

• Computational Breakthrough: CayleyPy demonstrates that GPU-accelerated, specialized algorithms can outperform general-purpose CAS by orders of magnitude, opening the door to exploring mathematical structures previously considered intractable.
• New Mathematical Insights: The paper shifts the paradigm from purely theoretical proofs to data-driven discovery in group theory, using massive computational experiments to formulate precise conjectures that can guide future theoretical proofs.
• Interdisciplinary Impact: The work bridges group theory, computer science (path-finding, AI), and biology (genome rearrangement), providing a unified framework for analyzing complex state-transition systems.
• Open Science: By releasing the library, datasets, and Kaggle challenges, the authors democratize access to high-level group theory research, inviting the broader AI and mathematical communities to contribute to solving these open problems.

In summary, this paper presents a powerful new tool (CayleyPy) and a wealth of new data that challenges and refines long-standing conjectures in group theory, suggesting that the diameters of many Cayley graphs follow elegant, computable quasi-polynomial laws.