Central-quotient eigengap conjecture for nilpotent Cayley graphs

A minimal counterexample to the central-quotient eigengap conjecture

Source. Rashid Barket, Enrico Grimaldi, Yacoub Hendi, Edward Hirst, Adam Onus, and Harmeet Singh, Learning the Graphical Nature of Symmetries, arXiv:2607.12026v1, Section 4.4, Conjecture 4.4. The conjecture concerns the normalized Laplacian of the underlying undirected Cayley graph and uses eigenvalues indexed starting at one.

We disprove the conjecture using the cyclic group of order five. Moreover, this is the smallest possible counterexample by group order, and it is the only counterexample among Cayley graphs that are simple cycles.

1. The precise conjecture

Let $G$ be a finite nilpotent group with upper central series

$$1=Z_0(G) \le Z_1(G) \le\cdots\le Z_c(G)=G.$$

Given a generating set $S$, let $\Gamma$ be the underlying undirected graph of $\operatorname{Cay}(G,S)$. Write $A$ and $D$ for its adjacency and degree matrices. The source defines the normalized Laplacian by

$$\mathcal L = I-D^{-1/2}AD^{-1/2}, \tag{1}$$

and orders its eigenvalues with multiplicity as

$$0=\lambda_1 \le\lambda_2 \le\cdots\le\lambda_{|G|} \le2.$$

Whenever a consecutive normalized eigengap exceeds one, define

$$k_{>1} = \min\left\{ i:\lambda_{i+1}-\lambda_i>1 \right\}. \tag{2}$$

Conjecture 4.4 asserts that either

$$k_{>1}=|G|-1, \tag{3}$$

or

$$k_{>1} = |G/Z_j(G)| \quad\text{for some }1\le j\le c. \tag{4}$$

2. A five-vertex cyclic Cayley graph

Take the finite cyclic group

$$G=\mathbb Z/5\mathbb Z$$

and its single-element generating set

$$S=\{1\}.$$

The directed Cayley graph has the arcs

$$x\longmapsto x+1\pmod 5.$$

Its underlying undirected Cayley graph is therefore the five-cycle

$$\Gamma=C_5. \tag{5}$$

Equivalently, one may start directly with the inverse-closed generating set $S=\{1,-1\}$ and obtain exactly the same undirected graph.

Every vertex of $C_5$ has degree two. Consequently, in the cyclic vertex order $0,1,2,3,4$, its normalized Laplacian is

$$\mathcal L(C_5) = \frac12 \begin{pmatrix} 2&-1&0&0&-1 \\ -1&2&-1&0&0 \\ 0&-1&2&-1&0 \\ 0&0&-1&2&-1 \\ -1&0&0&-1&2 \end{pmatrix}. \tag{6}$$

Its characteristic polynomial factors exactly as

$$\det\left(xI-\mathcal L(C_5)\right) = \frac{x}{16} \left(4x^2-10x+5\right)^2. \tag{7}$$

Thus the ordered normalized Laplacian eigenvalues, including multiplicity, are

$$\begin{aligned} \lambda_1&=0, \\ \lambda_2=\lambda_3 &=\frac{5-\sqrt5}{4}, \\ \lambda_4=\lambda_5 &=\frac{5+\sqrt5}{4}. \end{aligned} \tag{8}$$

The consecutive gaps are therefore

$$\begin{aligned} \lambda_2-\lambda_1 &=\frac{5-\sqrt5}{4}<1, \\ \lambda_3-\lambda_2 &=0, \\ \lambda_4-\lambda_3 &=\frac{\sqrt5}{2}>1, \\ \lambda_5-\lambda_4 &=0. \end{aligned} \tag{9}$$

The strict middle inequality follows from $5>4$. Hence the first gap greater than one occurs at the one-based index

$$\boxed{k_{>1}=3.} \tag{10}$$

Since $G$ is abelian, it is nilpotent of class one and

$$Z_1(G)=G.$$

Its only quotient permitted in (4) therefore has order

$$|G/Z_1(G)|=1,$$

whereas the exceptional index permitted in (3) is

$$|G|-1=4.$$

Consequently

$$\boxed{ k_{>1}=3 \notin \left\{ |G/Z_1(G)|,\ |G|-1 \right\} =\{1,4\}. } \tag{11}$$

This contradicts Conjecture 4.4 for a finite nilpotent group, a valid minimal generating set, and precisely the normalized undirected spectrum stipulated by the source.

3. Minimality and the complete cycle-family behavior

No smaller finite group supplies a counterexample. Every group of order at most four is abelian. A connected undirected Cayley graph of order two or three is respectively $K_2$ or $K_3$. A connected undirected Cayley graph of order four, being regular, is either $C_4$ or $K_4$.

For a complete graph, the normalized Laplacian spectrum is

$$\operatorname{spec}\left(\mathcal L(K_n)\right) = \left\{ 0, \left(\frac{n}{n-1}\right)^{(n-1)} \right\}.$$

The only gap greater than one is at index $1$, exactly the permitted central-quotient order. For $C_4$, the spectrum is

$$\operatorname{spec}\left(\mathcal L(C_4)\right) =\{0,1,1,2\},$$

so there is no gap strictly greater than one and the conjecture's conditional index is undefined. Therefore order five is the sharp minimum.

More generally, consider the standard cyclic Cayley graph

$$\operatorname{Cay} \left(\mathbb Z/n\mathbb Z,\{1,-1\}\right) =C_n, \qquad n\ge3.$$

Its normalized eigenvalues are

$$1-\cos\left(\frac{2\pi j}{n}\right), \qquad 0\le j<n. \tag{12}$$

After sorting and retaining multiplicities, every nonzero consecutive gap is of the form

$$\begin{aligned} \cos\left(\frac{2\pi j}{n}\right) -\cos\left(\frac{2\pi(j+1)}{n}\right) &= 2\sin\left(\frac{(2j+1)\pi}{n}\right) \sin\left(\frac{\pi}{n}\right) \\ &\le 2\sin\left(\frac{\pi}{n}\right). \end{aligned} \tag{13}$$

For every $n\ge6$,

$$2\sin\left(\frac{\pi}{n}\right) \le 2\sin\left(\frac{\pi}{6}\right) =1.$$

Thus $k_{>1}$ is undefined for every cycle $C_n$ with $n\ge6$. The triangle $C_3=K_3$ has $k_{>1}=1$, the square $C_4$ has no qualifying gap, and $C_5$ has the forbidden index $3$. Hence $C_5$ is the unique counterexample within the complete family of cyclic Cayley graphs generated by a single element.