Conference Graph Existence

Existence of Conference Graphs

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

A strongly regular graph with parameters $(v,k,\lambda,\mu)$ is a simple $k$-regular graph on $v$ vertices in which adjacent pairs have $\lambda$ common neighbours and nonadjacent pairs have $\mu$. A conference graph has parameters $(v,(v-1)/2,(v-5)/4,(v-1)/4)$. The proposed existence is for every $v>1$ satisfying $v\equiv1\pmod4$ and $v=a^2+b^2$ with integers $a,b$. [S1] [S2]

Statement recorded in the supplied source.

Does there exist a conference graph for every number of vertices $v > 1$ where $v \equiv 1 \pmod{4}$ and v is an odd sum of two squares? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Either construct conference graphs at all arithmetically admissible orders or identify an admissible order for which they cannot exist. [S1]

Short English statement

Do conference graphs exist for every order meeting the stated congruence and sum-of-two-squares conditions?

Research attempt

Scope and construction strategy.

The target is existence at every admissible order, not merely at prime powers. The route below proves the finite-field family and rewrites the general case as an exact matrix problem. Gritsenko's primary abstract [E1] reports a construction at order $65$, so a failure of the finite-field construction at that order is not a nonexistence result. Neither that published construction nor the general matrix problem is claimed to be resolved afresh here.

A complete construction at prime-power orders.

Let $q\equiv1\pmod4$ be an odd prime power, and let $F$ be the field with $q$ elements. Write $\chi$ for its quadratic character, with $\chi(0)=0$. Join distinct $x,y\in F$ when $\chi(x-y)=1$. Since $-1$ is a square in $F$, adjacency is symmetric. Multiplication by a nonzero element is a bijection, and exactly half the nonzero elements are squares, so the degree is $(q-1)/2$.

We derive the common-neighbour counts rather than infer them from the degree. Translate the pair to $0,a$ with $a\ne0$. The identity \[ \sum_{x\in F}\chi(x(x-a))=-1 \] follows by counting solutions of $y^2=x(x-a)$. For each $x$ there are $1+\chi(x(x-a))$ choices of $y$. On the other hand, \[ (2x-a-2y)(2x-a+2y)=a^2. \] Each choice of a nonzero first factor determines the second and then determines $x,y$, since two and four are invertible. There are $q-1$ solutions in total, proving the identity.

The number of common neighbours is therefore \begin{align*} \frac14\sum_{x\ne0,a}(1+\chi(x))(1+\chi(x-a)) &=\frac14\left(q-2-\chi(a)-\chi(-a)-1\right)\\ &=\frac{q-3-2\chi(a)}4. \end{align*} For adjacent vertices this is $(q-5)/4$, and for nonadjacent vertices it is $(q-1)/4$. Thus the construction has all the required parameters. The argument covers finite fields of nonprime order as well as prime fields; the finite computations below use only prime fields.

An exact matrix reformulation at arbitrary order.

For any putative graph let $A$ be its adjacency matrix, $I$ the identity, and $J$ the all-ones matrix of order $v$. Counting walks of length two gives \[ A^2=\frac{v-1}{4}I-A+\frac{v-1}{4}J, \qquad A\mathbf1=\frac{v-1}{2}\mathbf1. \] Set $S=J-I-2A$. It is symmetric, has zero diagonal and off-diagonal entries in $\{-1,1\}$, and satisfies \[ S\mathbf1=0,\qquad S^2=vI-J. \] Consequently the bordered matrix \[ C=\begin{pmatrix}0&\mathbf1^T\\\mathbf1&S\end{pmatrix} \quad\hbox{satisfies}\quad C^2=vI_{v+1}. \] This gives a symmetric conference matrix in normalized form. Conversely a symmetric matrix of this displayed form, with zero diagonal, signs off the diagonal, and $C^2=vI$, forces $S\mathbf1=0$ and $S^2=vI-J$. Then $A=(J-I-S)/2$ is a simple graph adjacency matrix with exactly the desired degree and common-neighbour counts. The equivalence does not require a transitive automorphism group.

On the subspace perpendicular to $\mathbf1$, the eigenvalues of $A$ must be $(-1+\sqrt v)/2$ and $(-1-\sqrt v)/2$. Each has multiplicity $(v-1)/2$, as follows from the zero trace and the principal eigenvalue $(v-1)/2$. These spectral data are consistent at the admissible orders; they do not supply a sign matrix. In particular an orthogonal real matrix with the right eigenvalues need not have entries $0,1$ after the inverse transformation.

Where a product construction would need more information.

The hypothesis that $v$ is a sum of two squares is arithmetic. The matrix requirement is simultaneous orthogonality of $v+1$ rows with prescribed signs and zeros. Neither multiplying two admissible orders nor writing $v=a^2+b^2$ specifies those rows. A plain tensor product of conference matrices has zeros wherever either factor has a diagonal zero, so it does not have the required single zero in each row. This pinpoints why an uncorrected multiplicative construction fails. Extra block designs or replacement rules would be necessary.

The field proof also cannot simply be performed modulo an arbitrary composite $v$. Nonzero residue classes need not be invertible, the quadratic character need not have the two-level correlations used above, and the factor-pair count for $a^2$ changes when $a$ is a zero divisor. The exact identity, rather than only the congruence $v\equiv1\pmod4$, is the operative ingredient of that proof.

Executed checks and limitations.

The script constructs the four prime-field graphs at $q=5,13,17,29$ and checks every vertex degree and every pairwise common-neighbour count. The resulting $(k,\lambda,\mu)$ are respectively $(2,0,1),(6,2,3),(8,3,4),(14,6,7)$; all four have diameter two. These checks are in checks_graphs.py and results_graphs.json in _Local/Erdos_problems/UnsolvedMath/attempt_audit_2026_10_01/number_theory/. No search at all admissible composite orders was executed.

Remaining gap and outcome.

The prime-power family is proved, and the general existence assertion is reduced to a normalized symmetric sign-matrix construction. The argument does not cover every admissible order or exclude a single admissible order. A construction for all such orders, or a rigorous obstruction beyond the supplied arithmetic tests, remains missing. Outcome: UNRESOLVED. The Paley construction and matrix reformulation are standard deductions, not claimed as new discoveries.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1410 (GRAPH-023), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 R. Mathon, Symmetric Conference Matrices of Order pq^2+1, Canadian Journal of Mathematics 30 $1978$, 321–331. https://doi.org/10.4153/CJM-1978-029-1. Bibliographic information from the supplied record.

• S3 O. Gritsenko, On strongly regular graph with parameters $65; 32; 15; 16$, arXiv:2102.05432 $2021$. https://arxiv.org/abs/2102.05432. Bibliographic information from the supplied record.

• E1 Oleg Gritsenko, On strongly regular graph with parameters $65; 32; 15; 16$, arXiv:2102.05432v1 $2021$. https://arxiv.org/abs/2102.05432. Primary abstract inspected 1 October 2026; its order-65 construction is background, not reproduced by the prime-field checks in this attempt.