On an infinite sequence of strongly regular digraphs with parameters $(9(2n+3), 3(2n+3), 2n+4, 2n+1, 2n+4)$

This paper constructs and proves the existence of an infinite sequence of strongly regular digraphs with parameters $(9(2n+3), 3(2n+3), 2n+4, 2n+1, 2n+4)$ by utilizing block circulant matrices, polynomial arithmetic, and computational tools to derive explicit adjacency formulas and propose a conjecture regarding their automorphism groups.

The Gist

Imagine you are an architect trying to build a city where every street follows a very strict, magical set of rules. This is essentially what mathematicians Viktor A. Byzov and Igor A. Pushkarev did in this paper, but instead of buildings, they built directed graphs (which we can think of as cities with one-way streets).

Here is the story of their discovery, broken down into simple concepts.

1. The Goal: The "Perfect" City

The authors wanted to create an infinite family of these cities. No matter how big you want the city to be (as long as it follows a specific size formula), they wanted a blueprint that guarantees the city works perfectly.

The rules for these cities are called Strongly Regular Digraphs. Think of them as cities with three golden rules:

1. Balance: Every intersection (vertex) has exactly the same number of roads leaving it and entering it.
2. The Loop: If you start at any intersection and take two steps, there is a specific, fixed number of ways you can end up back where you started.
3. The Connection: If you take two steps to get from Intersection A to Intersection B:
   • If there is a direct road from A to B, there are exactly $\lambda$ two-step paths.
   • If there is no direct road, there are exactly $\mu$ two-step paths.

The authors found a way to build these cities for sizes like 45, 63, 81, 99, and so on, forever.

2. The Problem: Too Many Possibilities

Building a city with 45 intersections is hard. Building one with 117 intersections is nearly impossible if you try to draw every single road by hand. The number of possible road layouts is so huge it's like trying to find a specific grain of sand on all the beaches on Earth.

To solve this, the authors used a Lego Strategy.
Instead of building the whole city from scratch, they decided to build it using 9 giant blocks, where each block is a smaller, repeating pattern (a "circulant matrix").

• Imagine a stamp. If you stamp a pattern over and over, you get a repeating design.
• They treated the whole city as a 9x9 grid of these stamps.

3. The Secret Weapon: "Compactification"

This is the paper's coolest trick.
Usually, a matrix (a grid of numbers) is huge. But because their blocks are repeating patterns, they realized they could shrink the whole thing down into a polynomial (a math equation with $x$'s).

• The Analogy: Imagine you have a long song that repeats a melody. Instead of writing out the whole sheet music for 1,000 notes, you just write the melody and say "Repeat this 1,000 times."
• In the paper: They turned the massive grid of roads into a small algebraic equation. They did all their heavy math on this tiny equation (using a computer) instead of the giant grid. This made the search for the right pattern much faster.

4. The Computer Hunt

The authors wrote a computer program (using a tool called pychoco) to act as a "digital detective."

1. They told the computer: "Find a pattern that fits these rules."
2. They gave the computer some hints (constraints) to narrow the search, like "The first block must look like this."
3. The computer tested thousands of possibilities for small city sizes ($n=1$ to $5$).
4. The Breakthrough: The computer found solutions! It didn't just find one; it found a pattern. The solutions looked so similar that the authors realized, "Wait a minute, there's a formula here!"

5. The Grand Discovery: The Infinite Formula

Once the computer found the first few examples, the authors stopped guessing and started proving. They wrote down a master formula (Theorem 7) that generates the blueprint for any size city in this family.

They proved mathematically that if you use this formula:

• The city will always have the right number of roads.
• The "two-step" rules will always work perfectly.
• It works for $n=1$, $n=100$, or $n=1,000,000$.

6. The Mystery of the "City Guards" (Automorphism Groups)

Every city has symmetry. If you rotate the city or flip it, does it look the same? The "Automorphism Group" is the mathematical name for all the ways you can shuffle the city around without breaking the rules.

The authors used another computer tool (GAP) to count these symmetries. They noticed a pattern in the symmetry groups of their small cities and made a Conjecture (a smart guess):

• They believe the symmetry group for any city in this family follows a specific, beautiful structure involving powers of 2 and a cycle of numbers.
• They haven't proven this part yet, but the pattern is so strong they are 99% sure it's true.

Summary

In short, these mathematicians:

1. Wanted to build perfect, rule-abiding road networks.
2. Used a "shrink-wrap" math trick to turn giant problems into small equations.
3. Let a computer find the first few examples.
4. Spotted the pattern in the computer's results.
5. Wrote a universal formula that builds these networks forever.

It's a beautiful example of how computers can help us find patterns, and human mathematicians can then step in to explain why those patterns work, turning a list of numbers into a timeless theory.

Technical Summary

Here is a detailed technical summary of the paper "On an infinite sequence of strongly regular digraphs with parameters $(9(2n + 3), 3(2n + 3), 2n + 4, 2n + 1, 2n + 4)$" by Viktor A. Byzov and Igor A. Pushkarev.

1. Problem Statement

The paper addresses the construction of an infinite family of Directed Strongly Regular Graphs (DSRGs). A DSRG with parameters $(v, k, t, \lambda, \mu)$ is a directed graph with $v$ vertices where:

• Every vertex has out-degree and in-degree equal to $k$.
• There are exactly $t$ paths of length 2 from a vertex to itself ($x \to z \to x$).
• If there is an arc $x \to y$, there are exactly $\lambda$ paths of length 2 from $x$ to $y$.
• If there is no arc $x \to y$, there are exactly $\mu$ paths of length 2 from $x$ to $y$.

The authors specifically target an infinite sequence of DSRGs with the parameter set:
$$(v, k, t, \lambda, \mu) = (9(2n + 3), \ 3(2n + 3), \ 2n + 4, \ 2n + 1, \ 2n + 4)$$
for integers $n \ge 1$. While previous work had found specific instances (e.g., for $n=1$), the challenge was to derive a general, explicit formula for the adjacency matrices of this infinite family.

2. Methodology

The authors employed a hybrid approach combining computer-assisted search and algebraic construction.

A. Structural Representation

The adjacency matrix $A_n$ of the target digraph is represented as a **$9 \times 9$block matrix**, where each block is a **circulant matrix** of order$m = 2n + 3$.

• Compactification: The authors utilize the isomorphism between the ring of circulant matrices and the quotient ring of polynomials $\mathbb{Z}[x] / (x^m - 1)$. This allows the $9 \times 9$block matrix to be "compactified" into a$9 \times 9$matrix of polynomials, denoted$A_n(x)$.
• Algebraic Conditions: The DSRG conditions translate into polynomial congruences modulo $x^{2n+3} - 1$:
  1. $A_n(x)^2 + 3A_n(x) \equiv (2n+4)J_9 Q(x)$
  2. $A_n(x)J_9 Q(x) \equiv J_9 A_n(x) Q(x) \equiv 3(2n+3)J_9 Q(x)$
     (Where $J_9$ is the all-ones matrix and $Q(x) = \sum_{i=0}^{2n+2} x^i$).

B. Computer Search (Constraint Programming)

To find the specific structure of $A_n(x)$, the authors used the pychoco constraint programming library to search for solutions for small values of $n$ ($n=1$ to $5$).

• Search Space Reduction: To make the search feasible, they imposed structural constraints based on observed patterns and a "potential candidate" matrix $C_n$ (derived from evaluating the polynomial matrix at $x=1$).
• Constraints Applied:
  • $A_n(1) = C_n$ (matching a specific integer matrix sequence).
  • Specific entries were fixed to simple polynomials (e.g., $1+x+\dots+x^n$).
  • Cyclic shift relationships were enforced between rows and columns (e.g., Row $i$ is $x$ times Row $i-1$).
• Verification: The resulting digraphs were analyzed using GAP (Groups, Algorithms, Programming) to compute their automorphism groups.

C. Algebraic Proof

Based on the patterns observed in the computer-generated solutions, the authors formulated an explicit formula for $A_n(x)$ involving specific polynomials $P(x), Q(x), R(x), S(x)$. They then provided a rigorous mathematical proof (Theorem 7) demonstrating that this formula satisfies the defining DSRG equations for all $n \ge 2$.

3. Key Contributions

1. Explicit Construction: The paper provides a closed-form formula for the adjacency matrix of an infinite sequence of DSRGs with parameters $(9(2n+3), 3(2n+3), 2n+4, 2n+1, 2n+4)$. This resolves the existence question for this infinite family.
2. Matrix Structure: The construction reveals that the adjacency matrix consists of 81 circulant submatrices, organized with a high degree of symmetry (block-circulant structure).
3. New Existence Results: The computational search confirmed the existence of DSRGs with parameters $(63, 21, 8, 5, 8)$ and $(81, 27, 10, 7, 10)$, which were previously unrecorded in standard tables (as of the paper's writing).
4. Automorphism Group Analysis:
   • The authors computed the automorphism groups for the constructed graphs.
   • They formulated Conjecture 8, proposing that the automorphism group for the general sequence is isomorphic to:
     $$C_2 \times (C_{2n+2}^2 \rtimes C_{2n+3})$$
     where $C_k$ denotes a cyclic group of order $k$, and $\rtimes$ denotes the semidirect product.

4. Results

• Verification: The explicit formula was proven to satisfy the DSRG conditions $A^2 = tI + \lambda A + \mu(J - I - A)$ and the degree constraints.
• Computational Data:
  • For $n=1$ (45 vertices), 1 non-isomorphic graph was found.
  • For $n=2$ (63 vertices), 4 non-isomorphic graphs were found.
  • For $n=3, 4, 5$, the search yielded 2 non-isomorphic graphs for each case.
• Search Efficiency: The use of constraint programming reduced the search time significantly, allowing the discovery of solutions for $n=5$ (117 vertices) in roughly 25 hours on a standard desktop processor.

5. Significance

• Expansion of DSRG Theory: Directed strongly regular graphs are significantly rarer and harder to construct than their undirected counterparts. This paper adds a substantial new infinite family to the known literature, expanding the catalog of known combinatorial designs.
• Methodological Innovation: The paper demonstrates the power of combining computer search (to guess structural patterns) with algebraic compactification (to prove infinite existence). This "guess-and-prove" methodology is a robust template for solving similar problems in algebraic graph theory.
• New Parameters: The construction provides the first known examples for specific parameter sets (e.g., $v=63$ and $v=81$), filling gaps in the classification of DSRGs.
• Group Theory Insights: The conjectured structure of the automorphism groups offers new insights into the symmetry properties of these complex directed graphs, suggesting a deep connection between the graph parameters and specific group extensions.

In summary, Byzov and Pushkarev successfully bridged the gap between computational discovery and theoretical proof to establish a new, infinite class of strongly regular digraphs, providing explicit formulas and deep structural insights into their symmetry.