A four-regular bipartite Cayley graph with point spectrum $\mathbb C\setminus\{0\}$ on $\mathbb C^G$

Problem

For every infinite connected vertex-transitive graph of finite valency, is every complex number an adjacency eigenvalue on the space of all complex-valued functions?

$$\forall\lambda\in\mathbb C,\quad \exists f\in\mathbb C^{V(\Gamma)}\setminus\{0\}:\quad \sum_{u\sim v}f(u)=\lambda f(v)\quad(v\in V(\Gamma))\;?$$

There is no finite-support, boundedness, or summability condition on $f$.

The graph and its point spectrum

For a locally finite simple graph $\Gamma$, its adjacency operator on the space of all complex-valued functions is

$$A_\Gamma:\mathbb C^{V(\Gamma)}\longrightarrow\mathbb C^{V(\Gamma)},\qquad (A_\Gamma f)(v)=\sum_{u\sim v}f(u).$$

Each sum is finite. We write

$$\operatorname{Eig}(A_\Gamma)= \{\lambda\in\mathbb C:\exists f\in\mathbb C^{V(\Gamma)}\setminus\{0\},\ A_\Gamma f=\lambda f\}.$$

There is no support, boundedness or summability condition on $f$. Problem 15.89 of the Kourovka Notebook, proposed by V. I. Trofimov, asks whether $\operatorname{Eig}(A_\Gamma)=\mathbb C$ for every infinite connected vertex-transitive graph of finite valency (1).

Theorem 1. Put

$$G=C_3*C_2=\langle a,t\mid a^3=t^2=1\rangle, \qquad S=\{ata,ata^2,a^2ta,a^2ta^2\}.$$

The graph $\Gamma=\operatorname{Cay}(G,S)$ is infinite, connected, simple, undirected, four-regular, bipartite and vertex-transitive. On $\mathbb C^G$ its adjacency operator $A$ is bijective and

$$\tag{4} \operatorname{Eig}(A)=\mathbb C\setminus\{0\}.$$

More precisely, for $(R_gf)(x)=f(xg)$,

$$\tag{5} A^{-1}=\tfrac14(R_a+R_{a^2}-\mathrm{Id})R_t(R_a+R_{a^2}-\mathrm{Id}).$$

Trofimov gives a finite-support criterion for a missing eigenvalue (2, Theorem 5.3). His complex examples in §§8.2–8.4 have several vertex orbits; the vertex-transitive examples in §8.1 use positive characteristic. The graph in (3) has unbounded degrees. Theorem 1 gives a four-regular vertex-transitive complex example with explicit point spectrum.

The graph also has a description by the three-arc construction (4). Put $H=\langle a\rangle$. The graph with vertices $gH$ and edges $\{gH,gtH\}$ is the cubic tree: reduced normal forms in $C_3*C_2$ give connectedness and exclude non-backtracking closed paths. The map $g\mapsto(gH,gtH)$ is a bijection onto its oriented edges. For an oriented edge $(u,v)$, three-arc adjacency joins it to $(x,y)$ when $(v,u,x,y)$ is a non-backtracking path of length three. Taking $(u,v)=(gH,gtH)$ gives exactly $x=ga^itH$ and $y=ga^ita^jtH$, where $i,j\in\{1,2\}$. Thus $\Gamma$ is the three-arc graph of the cubic tree; the spectral assertion concerns this established construction.

Verification of the graph properties

We use composition as multiplication of affine maps. Fix a primitive cube root of unity $\omega\in\mathbb C$, so that

$$\tag{6} \omega^3=1,\qquad \omega\ne1,\qquad 1+\omega+\omega^2=0.$$

The maps

$$\alpha(z)=\omega z,\qquad \tau(z)=1-z$$

satisfy $\alpha^3=\tau^2=\mathrm{Id}$. They therefore determine a homomorphism from $G$ to the affine group of $\mathbb C$, taking $a$ to $\alpha$ and $t$ to $\tau$. On the invariant lattice $\mathbb Z+\mathbb Z\omega$, their coordinate maps are $\alpha(u,v)=(-v,u-v)$ and $\tau(u,v)=(1-u,-v)$.

Lemma 2. The four elements of $S$ are distinct, nonidentity, inverse-closed and generate $G$. The group $G$ is infinite.

Define adjacency by $g\sim h$ if $h=gs$ for some $s\in S$. Lemma 2 gives symmetry and absence of loops. Cancellation in $G$ identifies the neighbors of $g$ with the four elements of $S$. Generation by $S$ gives connectedness. For every $b\in G$, left multiplication $g\mapsto bg$ preserves adjacency, and these automorphisms act transitively on vertices.

Finally, the homomorphism

$$\varepsilon:G\longrightarrow\mathbb Z/2\mathbb Z,\qquad \varepsilon(a)=0,\quad\varepsilon(t)=1$$

is well-defined by the presentation. Every $s\in S$ has $\varepsilon(s)=1$. Hence every edge joins the two fibers of $\varepsilon$, proving bipartiteness.

The finite-range inverse

Translations on $\mathbb C^G$ satisfy $R_gR_h=R_{gh}$. Put

$$U=R_a+R_{a^2},\qquad T=R_t.$$

On each left coset of $\langle a\rangle$, $U$ is the matrix $J-I$ with $J$ the $3\times3$ all-ones matrix, as in the local decomposition of the non-backtracking operator (5). The adjacency sum factors as

$$\tag{14} A=UTU.$$

The defining group relations give

$$\begin{align*} U^2&=R_{a^2}+2R_{a^3}+R_{a^4}=U+2\mathrm{Id}, \tag{15}\\ T^2&=\mathrm{Id}.\nonumber \end{align*}$$

Consequently the operator $V=(U-\mathrm{Id})/2$ satisfies

$$UV=VU=\mathrm{Id}.$$

Using (14),

$$(VTV)A=VT(VU)TU=VU=\mathrm{Id}, \qquad A(VTV)=UT(UV)TV=UV=\mathrm{Id}.$$

This proves (5). Expanding it yields

$$\begin{align*} 4A^{-1}={}&R_{ata}+R_{ata^2}+R_{a^2ta}+R_{a^2ta^2} \tag{18}\\ &-R_{at}-R_{a^2t}-R_{ta}-R_{ta^2}+R_t.\nonumber \end{align*}$$

These finite operator identities imply

$$Af=0\quad\Longrightarrow\quad f=A^{-1}Af=0,$$

so $0\notin\operatorname{Eig}(A)$.

Eigenfunctions for every nonzero complex number

For $s\in\mathbb C$, consider the matrices

$$D=\begin{pmatrix}1&0\\0&\omega\end{pmatrix},\qquad B_s=\begin{pmatrix}s&1\\1-s^2&-s\end{pmatrix}.$$

They satisfy

$$D^3=I,\qquad B_s^2=I.$$

The presentation of $G$ therefore defines a representation

$$\rho_s:G\longrightarrow\operatorname{GL}_2(\mathbb C), \qquad \rho_s(a)=D,\quad \rho_s(t)=B_s.$$

By (6), $D+D^2=\operatorname{diag}(2,-1)$. Thus

$$\tag{23} \sum_{u\in S}\rho_s(u) =(D+D^2)B_s(D+D^2) =M_s:=\begin{pmatrix}4s&-2\\-2(1-s^2)&-s\end{pmatrix}.$$

Its characteristic polynomial is

$$\tag{24} \det(\lambda I-M_s)=\lambda^2-3s\lambda-4.$$

Fix $\lambda\ne0$ and set

$$\tag{25} s_\lambda=\frac{\lambda^2-4}{3\lambda},\qquad v_\lambda=\begin{pmatrix}2\\4s_\lambda-\lambda\end{pmatrix}.$$

Then

$$M_{s_\lambda}v_\lambda=\lambda v_\lambda.$$

Indeed, the first coordinate is $8s_\lambda-2(4s_\lambda-\lambda) =2\lambda$; the second is $-4+s_\lambda\lambda$, equal to $\lambda(4s_\lambda-\lambda)$ by $\lambda^2-3s_\lambda\lambda-4=0$.

Define the matrix coefficient

$$\tag{27} f_\lambda(g)=(1\ \ 0)\rho_{s_\lambda}(g)v_\lambda \qquad(g\in G).$$

It is nonzero since $f_\lambda(1)=2$. Equations (23)–(27) give, for every $g\in G$,

$$\begin{align*} (Af_\lambda)(g) &=\sum_{u\in S}(1\ \ 0)\rho_{s_\lambda}(gu)v_\lambda\\ &=(1\ \ 0)\rho_{s_\lambda}(g) \left(\sum_{u\in S}\rho_{s_\lambda}(u)\right)v_\lambda\\ &=(1\ \ 0)\rho_{s_\lambda}(g)M_{s_\lambda}v_\lambda =\lambda f_\lambda(g). \end{align*}$$

Thus every $\lambda\ne0$ belongs to $\operatorname{Eig}(A)$. Together with (5), this proves Theorem 1.

References

Preprint · Lean (GitHub)

1. E. I. Khukhro and V. D. Mazurov (eds.), The Kourovka Notebook: Unsolved Problems in Group Theory, 21st ed., version of 1 September 2026. arXiv:1401.0300v46.

2. V. I. Trofimov, On adjacency operators of locally finite graphs, Izv. Math. 88 (2024), no. 3, 542–589. MathNet: im9408. Author version arXiv:2208.01926v3.

3. V. I. Trofimov, Infinite locally finite connected graphs with countable complements in $\mathbb C$ of the sets of eigenvalues, Proc. Steklov Inst. Math. 329 (2025), suppl. 1, S250–S256. doi:10.1134/S0081543825600942.

4. G. Xu and S. Zhou, Three-arc graphs: characterization and domination, Discrete Applied Mathematics 193 (2015), 200–207. doi:10.1016/j.dam.2015.04.019.

5. O. Angel, J. Friedman and S. Hoory, The non-backtracking spectrum of the universal cover of a graph, Trans. Amer. Math. Soc. 367 (2015), no. 6, 4287–4318. Author version arXiv:0712.0192.