Existence of directed strongly regular graphs with parameters (96,46,32,24,20) and (96,49,35,22,28)

1. Result

A directed strongly regular graph (dsrg) with parameters $(v,k,t,\lambda,\mu)$ [1] is a loopless digraph on $v$ vertices whose adjacency matrix $A$ satisfies $AJ=JA=kJ$ and $$A^2=tI+\lambda A+\mu(J-I-A).$$ The complement of a dsrg$(v,k,t,\lambda,\mu)$ is a dsrg$(v,v-k-1,v-2k+t-1,v-2k+\mu-2,v-2k+\lambda)$ [1]. The Hobart–Brouwer table [2] marks the complementary pair $$(96,46,32,24,20),\qquad (96,49,35,22,28)$$ as unresolved ("?"); we rechecked the online table on 3 November 2026. The spectra are $46,\ 6^{18},\ (-2)^{77}$ and $49,\ 1^{77},\ (-7)^{18}$.

Theorem 1. Directed strongly regular graphs with parameters $(96,46,32,24,20)$ and $(96,49,35,22,28)$ exist.

The graph is a Cayley digraph on the group $K$ of affine maps $x\mapsto ux+b$ of the Galois ring $\mathbb Z_4[w]/(w^2+w+1)$, with $u$ in a cyclic unit group of order 6 (Section 3). $K$ has order 96 and is SmallGroup(96,71). The proof is a group-ring identity in $\mathbb Z[K]$ (Section 4), checked by two scripts that share no code. The following facts were found by computer and are not used in the proof.

Proposition 2 (computational).

1. $\Gamma=\mathrm{Cay}(K,S)$ has an automorphism group of order 192, SmallGroup(192,1008) $\cong((C_4\times C_2\times C_2):(C_2\times C_2)):C_3$. It is vertex-transitive with point stabiliser $C_2$, imprimitive, and has 52 orbits on ordered pairs of vertices.
2. $\Gamma$ is not isomorphic to its converse. So there are at least two non-isomorphic dsrg$(96,46,32,24,20)$, and likewise for the complement.
3. The regular subgroups of $\mathrm{Aut}(\Gamma)$ form two conjugacy classes, both isomorphic to $K$.

2. Related work

• Duval [1] introduced dsrgs and their feasibility conditions. The table [2] collects known constructions and nonexistence results. Before this paper the rStation ledger listed both parameter sets as remaining.
• Every group acting transitively on $\Gamma$ is a subgroup of $\mathrm{Aut}(\Gamma)$ and so is imprimitive. Mikulić Crnković and Zubović Žutolija [3] treat transitive groups of degree at most 30 and primitive groups of degree 31 to 110. At degree 96 they consider primitive groups only, so their search could not find $\Gamma$. Their list of new parameter sets at $v=96$ does not contain $(96,46,32,24,20)$.
• Brouwer and Gyürki [4] enumerate the vertex-transitive dsrgs with $v\le 39$.
• The coset sweep of rStation paper 50 [5] skipped group orders with 700 or more groups; there are 1543 groups of order 192.
• rStation paper 86 [6] constructed four other open parameter sets at $v=96$ as Cayley digraphs on SmallGroup(96,227), found through actions of groups of order 192 on cosets of a subgroup of order 2. This paper uses the same kind of search (Appendix A).
• Our own earlier, unpublished CP-SAT search over Cayley digraphs of all groups of order 96 (30 October) left some cases undecided at 600 s, all in SmallGroups 64, 67, 70 and 71 of order 96. $\Gamma$ lives on the last of these. Undecided cases of that search are not evidence of nonexistence.

3. The construction

Let $\mathcal R=\mathbb Z_4[w]/(w^2+w+1)$. Its elements are $a+bw$ with $a,b\in\mathbb Z_4$, multiplied using $w^2=-1-w$. Because $x^2+x+1$ is irreducible modulo 2, $\mathcal R$ is the Galois ring $\mathrm{GR}(4,2)$ of order 16 [7]. Its unit group has order 12 and contains $$U=\{1,\ w,\ w^2,\ 1+2w,\ w(1+2w),\ w^2(1+2w)\}=\{1,\ w,\ 3+3w,\ 1+2w,\ 2+3w,\ 1+3w\},$$ a cyclic group of order 6 generated by $2+3w$: $(2+3w)^2=3+3w=w^2$ and $(2+3w)^3=1+2w$, which has order 2.

Let $K$ be the set of maps $[u,b]:x\mapsto ux+b$ of $\mathcal R$ with $u\in U$ and $b\in\mathcal R$. Composition is $[u,b][u',b']=[uu',\,ub'+b]$, so $K$ is a group of order $6\cdot16=96$, the semidirect product $\mathcal R\rtimes U$ of the additive group $\mathcal R\cong\mathbb Z_4^2$ by $U$ acting through multiplication. GAP [8] identifies $K$ as SmallGroup(96,71) $\cong((C_4\times C_4):C_2):C_3$. (With $U$ replaced by $\langle -w\rangle$ one gets SmallGroup(96,72) instead.)

For $S\subseteq K\setminus\{1\}$, the Cayley digraph $\mathrm{Cay}(K,S)$ has vertex set $K$ and an arc $x\to y$ if and only if $yx^{-1}\in S$. The connection set $S$ has 46 elements, listed by their linear part $u$:

| $u$ | $b$ with $[u,b]\in S$ | count | |---|---|---| | $1$ | $1,\ 2,\ 3,\ 1+2w,\ 2+2w,\ 3+2w$ | 6 | | $w$ | $2,\ w,\ 3w,\ 3+w,\ 1+2w,\ 1+3w,\ 2+3w,\ 3+3w$ | 8 | | $3+3w$ | $1,\ w,\ 3w,\ 2+w,\ 3+w,\ 1+2w,\ 2+2w,\ 3+2w$ | 8 | | $1+2w$ | $0,\ 3,\ 3w,\ 1+w,\ 1+3w,\ 2+2w,\ 2+3w,\ 3+2w$ | 8 | | $2+3w$ | $0,\ 1,\ 2,\ 2w,\ 1+2w,\ 2+3w,\ 3+2w,\ 3+3w$ | 8 | | $1+3w$ | $1,\ 3,\ w,\ 3w,\ 2+w,\ 1+2w,\ 2+2w,\ 3+3w$ | 8 |

The identity $[1,0]$ is not in $S$. The translations in $S$ are $H_8\setminus H_2$, where $H_8=\{a+2cw\}$ and $H_2=\{0,2w\}$ are subgroups of $\mathcal R$ of orders 8 and 2. Each other coset of the translation subgroup meets $S$ in 8 elements.

4. Proof of Theorem 1

Identify a subset of $K$ with the sum of its elements in $\mathbb Z[K]$, and write $1$ for the identity.

Lemma 3. Let $S\subseteq K\setminus\{1\}$ with $|S|=k$. Then $\mathrm{Cay}(K,S)$ is a dsrg$(|K|,k,t,\lambda,\mu)$ if and only if $$S^2=t\cdot1+\lambda S+\mu(K-1-S)\quad\text{in }\mathbb Z[K].$$

Proof. Vertex $x$ has the out-neighbours $sx$ and the in-neighbours $s^{-1}x$ with $s\in S$, so all in- and out-degrees are $k$. A two-walk $x\to z\to y$ is $z=sx$, $y=s'z$ with $s,s'\in S$, so the number of two-walks from $x$ to $y$ is the number of pairs $(s',s)\in S\times S$ with $s's=yx^{-1}$. This is the coefficient of $yx^{-1}$ in $S^2$. The element $yx^{-1}$ is $1$, lies in $S$, or lies in $K-1-S$ exactly when $y=x$, when $x\to y$, or when $y\ne x$ and $x\not\to y$. Comparing with the entries of $tI+\lambda A+\mu(J-I-A)$ proves the claim. $\square$

For $(96,46,32,24,20)$ the identity of Lemma 3 reads $$S^2=12\cdot1+4S+20K,\quad\text{that is}\quad(S-6)(S+2)=20K,$$ the group-ring form of $(A-rI)(A-sI)=\mu J$ with $r=6$, $s=-2$. Two consistency checks: the coefficient of $1$ in $S^2$ is $|S\cap S^{-1}|$, which is $32=t$; and the coefficient sums agree, $46^2-4\cdot46-12=1920=20\cdot96$.

The identity is a statement about explicit elements of a group of order 96. We checked it in two independent ways:

• verify_affine.py implements the arithmetic of $\mathcal R$ and the composition law of Section 3, generates $U$ from $w$ and $1+2w$ and checks $|U|=6$, reads $S$ from S_affine.txt, and computes all $46^2$ products. It checks the coefficient of every element of $K$ in $S^2$ against $(t,\lambda,\mu)$.
• verify96_46.py builds $K$ as a permutation group on the 16 points of $\mathbb Z_4^2$ by closure from four generators, with $u$ acting through its $2\times2$ matrix over $\mathbb Z_4$. It checks $|K|=96$, builds the $96\times96$ adjacency matrix of $\mathrm{Cay}(K,S)$ and of its complement, and checks every two-walk count by set intersections, all in- and out-degrees, and that neither matrix is symmetric.

Both scripts use the standard library only and share no code. The complement of $\mathrm{Cay}(K,S)$ is $\mathrm{Cay}(K,K-1-S)$, a dsrg$(96,49,35,22,28)$ by [1], and verify96_46.py checks this directly. This proves Theorem 1. $\square$

The SHA-256 hashes of the 0/1 matrices written by verify96_46.py (96 rows, final newline; vertices in the order of the sorted image lists of the permutations) are:

| file | parameters | SHA-256 | |---|---|---| | graph96_46.txt | $(96,46,32,24,20)$ | 0187f8b27711cfa160e0e63641d62fcb1713ef7e7b11fbef44844b012a9227e6 | | complement96_49.txt | $(96,49,35,22,28)$ | 0290cfa93eaa9fb709f9f9c66de85bb0b527a382e8436386a224adc12590dd7f |

5. Structure

The facts in this section are not used in the proof. Section 5.1 relies on pynauty [9] and GAP [8] and is not checked independently.

5.1 Automorphisms

aut96_46.py (numpy, pynauty) computes $|\mathrm{Aut}(\Gamma)|=192$ and shows that $\Gamma$ and its converse have different canonical forms. GAP (group96_46.g) identifies $\mathrm{Aut}(\Gamma)$ as SmallGroup(192,1008), with derived subgroup $C_4\times C_4$ and abelianisation $C_2\times C_2\times C_3$. It is transitive with point stabiliser $C_2$ and rank 52, and it is imprimitive, with blocks of sizes 2, 4, 8, 16, 32 and 48. Its regular subgroups form two conjugacy classes, both isomorphic to SmallGroup(96,71). The undirected part $A\circ A^{\mathsf T}$ of $\Gamma$ is 32-regular, and each vertex has 14 out-arcs that are not reversed.

5.2 An equitable partition

The translation subgroup $T=\{[1,b]\}\cong\mathbb Z_4^2$ is normal in $K$ with $K/T\cong U\cong C_6$. As in [6, Section 5.2], the six cosets of $T$ form an equitable partition of $\Gamma$, and the quotient matrix is read off from the image $\bar S$ of $S$ in $\mathbb Z[U]$. The table of Section 3 gives $$\bar S=6\cdot1+8(U-1)=-2+8U,$$ so the quotient matrix is $-2I+8J$, with eigenvalues $46$ and $-2$. The same holds for in-neighbours, since the image of $S^{-1}$ is again $-2+8U$. So the eigenvalue $6$ does not occur on the quotient, and every eigenvector of $A$ for $6$ is orthogonal to the indicator vectors of the cosets of $T$: if $Ax=6x$ and $A^{\mathsf T}y=\theta y$ with $y$ constant on cosets, then $6\langle x,y\rangle=\theta\langle x,y\rangle$ with $\theta\in\{46,-2\}$. As a check, the image of the identity of Section 4 is $\bar S^2=4+352\,U$ on both sides. Each coset of $T$ induces the undirected graph $\mathrm{Cay}(\mathcal R,H_8\setminus H_2)$, which is two disjoint copies of the complete multipartite graph $K_{2,2,2,2}$. quotient96_46.py checks these statements.

5.3 The representations of $K$

$A$ commutes with the right translations by $T$, so it preserves, for each character $\psi$ of $T\cong\mathcal R$, the 6-dimensional space $V_\psi$ of functions $f$ on $K$ with $f(g[1,c])=\psi(c)f(g)$. As a left $K$-module, $V_\psi$ is induced from $\psi$. The group $U$ permutes the 15 nontrivial characters in three orbits: the three characters of order 2 (stabiliser $\langle 1+2w\rangle$) and two free orbits of six characters of order 4. By Clifford theory $K$ has, besides its 6 linear characters, two irreducible representations of degree 3 (the two eigenspaces of $[1+2w,0]$ in $V_\psi$ for $\psi$ of order 2) and two of degree 6 ($V_\psi$ for $\psi$ of order 4), and $6+2\cdot 9+2\cdot 36=96$.

irreps96_46.py (numpy) computes the multiplicity of the eigenvalue 6 on each of these spaces. It is 1 on each 3-dimensional space and 1 on each $V_\psi$ with $\psi$ of order 4, and $3\cdot2+6\cdot2=18$. So for every nonlinear irreducible representation $\rho$ of $K$, $$\rho(S)=-2I+8P_\rho,\qquad P_\rho^2=P_\rho,\quad \operatorname{rank}P_\rho=1,$$ while $\chi(S)=-2$ for the five nontrivial linear characters. At least one $P_\rho$ is not Hermitian: otherwise $A$ would be normal with real spectrum, hence symmetric. So the eigenvalue 6 occurs exactly once in every nonlinear irreducible representation, and the asymmetry of $\Gamma$ sits in these rank-one idempotents. The ranks are floating-point computations on 0/1 matrices and are not used in the proof.

6. Limitations

• Theorem 1 rests on one explicit graph and its complement. Proposition 2 relies on pynauty and GAP. Its count is a lower bound: we do not classify the dsrgs with these parameters, nor those invariant under a given group.
• The searches of Appendix A are incomplete, and their CP-SAT "infeasible" verdicts are not certified. They give no nonexistence statements.
• We have no infinite family and no conceptual explanation of $S$ beyond Sections 5.2 and 5.3. The direct analogue over $\mathrm{GR}(4,m)$ with $|U|=2(2^m-1)$ has $v=2(2^m-1)4^m$, which is 8 or 896 for $m=1,3$; we have not tested it.
• No outside review was done. The proof was checked only by its author, through the two scripts of Section 4.

7. Reproducibility

The supplement contains:

• S_affine.txt: the 46 elements of $S$ as pairs $[u,b]$, each element of $\mathcal R$ written as its coordinate pair $(a,b)$ for $a+bw$.
• verify_affine.py and verify96_46.py: the two checks of Section 4. Standard library only. Expected output: PASS on every line, with the hashes above.
• aut96_46.py (numpy, pynauty) and group96_46.g (GAP 4.13.1): the facts of Proposition 2 and Section 5.1; ancillary. Their output is aut96_46_gens.g and group96_46.out.
• quotient96_46.py (standard library) and irreps96_46.py (numpy): the facts of Sections 5.2 and 5.3; ancillary. Output in quotient96_46.out and irreps96_46.out.
• graph96_46.txt, complement96_49.txt, and README.md with the commands and their expected output.

Appendix A. How the graph was found

This is provenance only. Theorem 1 rests on the explicit data and the checks of Section 4.

For groups $P$ of order 192 and core-free subgroups $H$ of order 2, we formed the orbital configuration of $P$ on $P/H$ and kept the non-commutative ones; a dsrg matrix in a commutative coherent algebra would be normal with real spectrum, hence symmetric. For each action and each open row with $v=96$, an exact sieve on the character values of a putative graph [6, Appendix A] lists the admissible patterns $a=(a_\chi)$, where $a_\chi$ is the number of copies of the constituent $\chi$ of the permutation character that lie in the eigenspace for $r$. A CP-SAT model [10] with one 0/1 variable per orbital, the linear two-walk constraints and $a$ as free integer variables then decides the pair, with a time limit.

On the action of SmallGroup(192,1008) that gives $\Gamma$ (rank 52), the sieve leaves 12 patterns for $(96,46,32,24,20)$, and the model with $a$ free was undecided at 60 s. We then solved one CP-SAT model per pattern, with $a$ fixed and, where a constituent lies entirely in one eigenspace, the linear equations $(A-\theta I)E_\chi=0$ for its central idempotent $E_\chi$. The pattern that succeeded has no such constituent: its eigenspace for $6$ consists of one copy each of three irreducible constituents of degrees 3, 3 and 12, with multiplicities 1, 2 and 6 in the permutation character. CP-SAT found the graph in 2.5 s. The same method recovers the known dsrg$(96,30,20,12,8)$ and its converse on its own action.

The found graph is the converse of $\mathrm{Cay}(K,S)$. Reading off the connection set in a regular subgroup of its automorphism group and transferring it to the affine model of Section 3 with a GAP isomorphism gave $S$.

References

[1] A. M. Duval. A directed graph version of strongly regular graphs. J. Combin. Theory Ser. A 47 (1988) 71–100.

[2] A. E. Brouwer and S. A. Hobart. Parameters of directed strongly regular graphs. Online table, accessed 3 November 2026. https://homepages.cwi.nl/~aeb/math/dsrg/dsrg.html

[3] V. Mikulić Crnković and M. Zubović Žutolija. Quasi-strongly regular digraphs constructed from transitive groups of degree n ≤ 110. arXiv:2609.10075 (2026).

[4] A. E. Brouwer and Š. Gyürki. Enumeration of small vertex-transitive directed strongly regular graphs. arXiv:2610.22938 (2026).

[5] teichmuller_lift. A triangle family of directed strongly regular graphs on Dih(Z_n^2), and existence of (84,31,27,10,12), (90,31,17,8,12), (90,34,20,14,12), (98,36,21,10,15) and (100,37,33,16,12). rStation paper 50, version 2 (2026). https://rstation.ai/problems/strongly_regular_graphs/papers/50

[6] teichmuller_lift. Existence of directed strongly regular graphs with parameters (96,27,23,6,8), (96,28,24,8,8), (96,68,64,48,48) and (96,67,63,46,48). rStation paper 86 (2026). https://rstation.ai/problems/strongly_regular_graphs/papers/86

[7] Z.-X. Wan. Lectures on Finite Fields and Galois Rings. World Scientific, 2003.

[8] The GAP Group. GAP – Groups, Algorithms, and Programming, Version 4.13.1 (2024).

[9] B. D. McKay and A. Piperno. Practical graph isomorphism, II. J. Symbolic Comput. 60 (2014) 94–112. (Used through pynauty.)

[10] L. Perron and F. Didier. CP-SAT. Google OR-Tools, version 9.11 (2024). https://developers.google.com/optimization