Source-linked AI summary
A symmetric conference matrix of order 86
Harshit Verma
TL;DR
Order 86 was the smallest order for which existence of a symmetric conference matrix remained open. The paper constructs and verifies such a matrix, yielding exactly ten isomorphism classes among its 86 descendants.
Problem
Order 86 was the smallest open case, with strongly regular graph parameters (85, 42, 20, 21) marked unknown in Brouwer’s table.
Source: §1 · p. 1Method
The authors construct an order-86 matrix with an 84×84 core arranged as a 12×12 array of 7×7 circulants, and verify its square is 85I.
Source: §2 · pp. 2–3Results
Exactly ten isomorphism classes arise among the 86 descendants, and each is a strongly regular graph with parameters (85, 42, 20, 21).
Source: §3 · p. 3Takeaways & Limitations
The construction also yields a regular two-graph on 86 points and a Taylor graph on 172 vertices.
Source: §4 · p. 4
Abstract
from arXiv · showhide
We construct a symmetric conference matrix of order $86$, the smallest order for which existence was open. Equivalently, there exist a conference graph with parameters $(85,42,20,21)$, a regular two-graph on $86$ points, and a real equiangular tight frame of $86$ vectors in $\mathbb{R}^{43}$. The matrix is a $12\times12$ array of $7\times7$ circulants with two border rows, and it admits a group of automorphisms of order $21$. Its $86$ descendants give exactly ten nonisomorphic strongly regular graphs.
1 Introduction
The paper resolves the previously open order-86 case by constructing a symmetric conference matrix. It also establishes the corresponding strongly regular graph parameters.
1 Introduction
- Order 86 was the smallest case still open, and Brouwer’s table marked the parameters (85, 42, 20, 21) unknown.Source: §1 · p. 1
- A symmetric conference matrix of order 86 exists, and consequently a strongly regular graph exists with parameters (85, 42, 20, 21).Source: §1 · p. 1
- The matrix was found by computer search, but the proofs rely on finite computations in the explicit matrix rather than on the search.The stated checks use exact integer arithmetic.Source: §1 · p. 1
2 The matrix
The construction specifies an 86×86 matrix using a circulant block and border entries, then verifies that its square is 85I. The verification reduces the matrix claim to finite identities.
2 The matrix
- The core entries use signs s_ij(b−a) indexed modulo 7, with their values encoded by bits of the specified integers M_ij.The diagonal entry s_ii(0) is set to zero.Source: §2 · p. 2
- The matrix has two border coordinates and an 84×84 core B arranged as a 12×12 array of 7×7 circulants.Source: §2 · pp. 1–2
- Coefficient comparison reduces the required conditions to finitely many integer identities, which a direct computation verifies.Source: §2 · p. 2
- Representing the cyclic shift by Z converts the polynomial blocks into matrices, so the lemma yields block identities used to establish C^2 = 85I.Source: §2 · pp. 2–3
- C^2 = 85I, verifying that the constructed matrix is a symmetric conference matrix of order 86.The graph consequence follows from Proposition 3.1.Source: §2 · p. 3
3 Descendants and automorphisms
The matrix’s descendants are strongly regular graphs with parameters (85, 42, 20, 21), and the automorphism group organizes them into exactly ten nonisomorphic classes. The group has order 21, and its orbits on the 86 points correspond to those classes.
Descendants and automorphisms
- Every descendant Γr is strongly regular with parameters (85, 42, 20, 21).Adjacent vertices have 20 common neighbors and nonadjacent vertices have 21.Source: §3 · p. 3
- The automorphisms g and h generate a group G ≅ C7 ⋊ C3 of order 21, with ten orbits on the 86 points.The orbits are the two border points, six individual 7-point blocks, and two sets of three 7-point blocks.Source: §3 · p. 3
- Descendants rooted in the same G-orbit are isomorphic, and distinct four-clique counts distinguish representatives from the ten orbits.Table 1 reports four-clique counts for one root in each orbit.Source: §3 · p. 3, Table 1 · p. 4
- The 86 descendants fall into exactly ten isomorphism classes, yielding at least ten pairwise nonisomorphic strongly regular graphs with parameters (85, 42, 20, 21).Each class corresponds to one orbit of the order-21 group.Source: §3 · p. 3
- The full automorphism group of the two-graph is G, and each descendant’s automorphism group is the stabilizer of its root in G.The proof identifies Aut Ω with Aut Γ∞ using the unique descendant whose four-clique count is 25900.Source: §3 · p. 3
4 Equivalent forms
The matrix also yields a regular two-graph on 86 points and an equiangular tight frame whose lines form an optimal packing in R^43. Its points define an antipodal distance-regular graph, and a tensor construction gives further conference-matrix orders.
4 Equivalent forms
- Each pair of points lies in exactly 42 triples of the regular two-graph on 86 points [2, §8.10].The pairwise product sum is zero, yielding the stated triple count.Source: §4 · p. 4
- The 86 unit vectors form an equiangular tight frame whose 86 lines optimally pack R^43, meeting the Welch bound.The passage notes that this case was listed as open in [10, Table 1], with [3] also cited.Source: §4 · p. 4
- The two-graph defines an antipodal distance-regular Taylor graph on 172 vertices with intersection array {85, 42, 1; 1, 42, 85}.The construction takes two copies (x, ±1) of each point and joins them according to Cxy.Source: §4 · p. 4
- From a symmetric matrix S of order q with the stated row-sum and square conditions, a tensor construction yields a conference matrix of order q^2 + 1 [2, Proposition 8.2.2].Starting from q = 85, the passage gives a family of further orders.Source: §4 · p. 4