2.1 Density of states of operators on universal covers

Studying the density of states of periodic Jacobi matrices on universal covers is a hard problem, and only in specific cases can explicit results be obtained. Here, we provide a quick overview of what we consider the most relevant results in the context of this paper. We refer the reader to [Reference Anderson and ZeitouniABS20] for a broader and more detailed discussion.

The density of states of the adjacency matrix of the universal cover of d-regular graphs (i.e., the d-regular tree with constant edge weights $a\equiv 1$ and constant vertex potential $b\equiv 0$ ) was first computed by Kesten [Reference Keller, Lenz and WarzelKes59] in the context of Cayley graphs, then revisited by McKay [Reference Marcus, Spielman and SrivastavaMcK81] in the context of random graphs. Godsil derived a formula for the density of states of the adjacency matrix of the universal cover of bipartite biregular graphs [Reference Gouëzel and LalleyGM88]. In the case of d-regular graphs, but now allowing arbitrary edge weights (but still requiring $b\equiv 0$ ), Figà-Talamanca and Steger [Reference Friedman and KohlerFTS94] provided a complete description of the spectrum of the lift of Jacobi matrices to the infinite d-regular tree.

In the more general setting of arbitrary universal covers, Aomoto [Reference Accardi, Ghorbal and ObataA+88] (see Theorem 1.5) derived a system of coupled equations (with square roots) for the Cauchy transforms of the spectral measures of periodic Jacobi matrices. In a similar spirit, polynomial coupled equations for certain transforms were then obtained by Avni, Breuer, and Simon [Reference Anderson and ZeitouniABS20] in the context of periodic Jacobi matrices on trees, and by Keller, Lenz, and Warzel [Reference KestenKLW13] in the context of infinite trees of finite cone type (which are a family of infinite trees that contains universal covers [Reference Kollár, Fitzpatrick, Sarnak and HouckKLW15]).

In [Reference Arizmendi, Cébron, Speicher and YinAom91], Aomoto used the coupled equations for the Cauchy transforms that he obtained in [Reference Accardi, Ghorbal and ObataA+88] to show that periodic Jacobi matrices on d-regular trees have no point spectrum. A result in a similar direction was later obtained in [Reference KestenKLW13], where it was shown that under some conditions on the base graph (that allow nonconstant degree graphs), the density of states of the adjacency matrix of the universal cover is absolutely continuous. Certainly, this result does not apply to all universal covers, since the density of states may contain atoms (see Table 1). A general result was obtained in [Reference Anderson and ZeitouniABS20], where it was shown that periodic Jacobi matrices on trees have no singular continuous spectrum. Finally, we point out the work of Sunada [Reference SunadaSun92], which was discussed above (see Theorem 1.8).

Table 1:

Six graphs $\mathcal {G}_i$ alongside the respective approximation to $\mu _{\mathcal {T}_i}$ , the density of states of the adjacency operator $A_{\mathcal {T}_i}$ (that is, $a\equiv 1$ and $b\equiv 0$ ). The approximations presented are (scaled) histograms of the eigenvalues of a large random lift (taken as in Section 2.2) of the respective graph. See Table 2 for the spectral radii of the $\mathcal {T}_i$ .

The reasons for studying the spectrum of operators on universal covers have varied from author to author. Our main motivation is that, as shown in [Reference Belinschi and BercoviciBC19], the spectra of these infinite objects govern the behavior of large random lifts of finite graphs, and, on the other hand, random lifts have been instrumental for obtaining groundbreaking results on the existence of optimal (Ramanujan) expanders [Reference Hora and ObataHPS18, Reference MoharMSS13]. We refer the reader to Section 2.2 for a definition and discussion of random lifts.

That said, the complexity and variety of features that one can observe when looking at the spectrum of different universal covers is appealing in its own right, and it is the source of many interesting spectral problems. To exemplify this, below we include some simulations and observations.

2.2 Random lifts

A random d-lift of a graph is a random d-fold cover of the graph with a particular choice of randomness. Recently, random d-lifts have been studied in the context of expander graphs. For example, random 2-lifts were used by Marcus, Spielman, and Srivastava to show the existence of Ramanujan graphs of every degree [Reference MoharMSS13]; these techniques were later generalized by Hall, Puder, and Sawin [Reference Hora and ObataHPS18] to d-lifts for $d \ge 2$ .

Definition 2.1 (Random lift)

Let $\mathcal {G}$ be a finite graph with n vertices, and let $d \ge 1$ . Let $\mathcal {U}(d)$ be the unitary group of dimension d, and consider a random function $U: E(\mathcal {G}) \to \mathcal {U}(d)$ that satisfies for all f that:

1. (1) (Symmetry) $U_{\check {f}} = U_f^*$ .

2. (2) (Uniformly distributed) $U_f$ is a random matrix distributed uniformly in the space of $d\times d$ permutation matrices.

3. (3) (Independence) If $f_1\neq f_2 $ and $f_1\neq \check {f}_2$ , then the random matrices $U_{f_1}$ and $U_{f_2}$ are independent.

Then, a random d-lift of $\mathcal {G}$ is a random graph with $d n$ vertices, whose adjacency matrix is given by

$$\begin{align*}\sum_{f \in E(\mathcal{G})} \Delta_{\sigma(f) \tau(f)} \otimes U_{f}, \end{align*}$$

where $\Delta _{\sigma (f)\tau (f)}$ denotes the $n\times n$ matrix with a 1 in the $(\sigma (f), \tau (f))$ entry and 0 everywhere else. Moreover, if $\mathcal {G}$ has edge weights a and vertex potential b, then the Jacobi matrix $A_{\mathcal {G}}$ can be pulled back to the (random) Jacobi matrix $A_{d, \mathcal {G}}$ on the lift, given by

$$ \begin{align*} A_{d, \mathcal{G}} :=\sum_{u\in V(\mathcal{G})} b_u \Delta_{uu} \otimes I_d+ \sum_{f\in E(\mathcal{G})} a_f \Delta_{\sigma(f)\tau(f)} \otimes U_f. \end{align*} $$

It is well known (and easy to show) that as d goes to infinity, random d-lifts of a fixed graph $\mathcal {G}$ converge in the Benjamini–Schramm sense [Reference Bordenave and CollinsBS11] to the universal covering graph $\mathcal {T}$ of $\mathcal {G}$ .Footnote ⁶ In particular, this implies that the density of states of $A_{\mathcal {T}}$ is the weak limit of the mean eigenvalue distribution of the random d-lifts:

Lemma 2.2 (Limits of random lifts)

Using the above notation, for every fixed p, one has

$$ \begin{align*}\lim_{d\to \infty} \frac{1}{d |V(\mathcal{G})|} \mathbb{E}\big [\mathrm{Tr}\, A_{d, \mathcal{G}}^p\big] = \int_{\mathbb{R}} x^p d\mu_{A_{\mathcal{T}}}(x).\end{align*} $$

Recently, using tools from free probability, Bordenave and Collins viewed the limiting operator $A_{\mathcal {T}}$ as an element of a certain $C^*$ algebra and showed that the convergence above holds in a much stronger sense, implying convergence of the edges of the spectrum [Reference Belinschi and BercoviciBC19]. In Section 4.1, we revisit in detail this $C^*$ -algebra representation and use it to give a proof of Sunada’s theorem. The theorem of Bordenave and Collins also handles half-loops f, for which $U_f$ is defined to be a random matching (see [Reference Figà-Talamanca and StegerFK19] for a discussion of related models of random lifts), and we also revisit this idea in Section 4.2 and use it obtain an extension of Sunada’s theorem in the presence of half-loops.

2.3 Spectral radii of operators on universal covers

In this discussion, we fix a finite graph $\mathcal {G}$ and let $A_{\mathcal {G}}$ denote its adjacency matrix (that is, $a\equiv 1$ and $b\equiv 0$ ), and we denote the universal cover of $\mathcal {G}$ by $\mathcal {T}$ . We denote the spectral radius of $A_{\mathcal {G}}$ and $A_{\mathcal {T}}$ by $\mathrm {spr}(\mathcal {G})$ and $\mathrm {spr}(\mathcal {T})$ , respectively.

The quantity $\mathrm {spr}(\mathcal {T})$ is fundamental in the theory of Ramanujan graphs [Reference Lubotzky, Phillips and SarnakLPS88]. Indeed, in general, a graph $\mathcal {G}$ is said to be Ramanujan if $\mathrm {Spec}(\mathcal {G})$ is contained in $[-\mathrm {spr}(\mathcal {T}), \mathrm {spr}(\mathcal {T})]\cup \{-\mathrm {spr}(\mathcal {G}), \mathrm {spr}(\mathcal {G})\}$ [Reference GreenbergGre95]; and many of the results in the area are stated in terms of $\mathrm {spr}(\mathcal {T})$ . For example, the main result in [Reference MoharMSS13] states that any graph $\mathcal {G}$ has a 2-lift $\mathcal {G}'$ such that the new eigenvalues of $A_{\mathcal {G}'}$ are bounded above by $\mathrm {spr}(\mathcal {T})$ , whereas its generalization in [Reference Hora and ObataHPS18] shows that the same is true for n-lifts for every $n\geq 2$ . Similar techniques have been used in [Reference McLaughlinMO20] to obtain analogous results for quotients of a class of infinite graphs that goes beyond universal covers, where the results are also given in terms of the spectral radius of the given infinite graph. We refer the reader to [Reference Huang and RahmanHR19, Reference Speicher and WoroudiSS92] for discussions on the relation between $\mathrm {spr}(\mathcal {G})$ and $\mathrm {spr}(\mathcal {T})$ .

In most cases, $\mathrm {spr}(\mathcal {T})$ is mentioned only as an implicit quantity and no quantitative bounds on it are provided. When $\mathcal {G}$ is d-regular, by the work of Kesten [Reference Keller, Lenz and WarzelKes59], we know that $\mathrm {spr}(\mathcal {T}) = 2\sqrt {d-1}$ . If $\mathcal {G}$ is a $(c, d)$ -biregular bipartite graph, by Godsil [Reference Gouëzel and LalleyGM88] we know that $\mathrm {spr}(\mathcal {G}) =\sqrt {c-1}+\sqrt {d-1}$ . In the case of general graphs, Hoory [Reference HooryHoo05] proved that if $d_{\mathrm {avg}}(\mathcal {G})$ is the average degree of $\mathcal {G}$ , then

(2.1) $$ \begin{align} \mathrm{spr}(\mathcal{T}) \geq 2\sqrt{d_{\mathrm{avg}}(\mathcal{G})-1}. \end{align} $$

On the other hand, an upper bound can be obtained trivially by noting that if $d_{\max }(\mathcal {G})$ is the maximum degree of $\mathcal {G}$ , then $\mathcal {T}$ can be embedded in the infinite $d_{\max }(\mathcal {G})$ -regular tree and hence

(2.2) $$ \begin{align} 2\sqrt{d_{\max}(\mathcal{G})-1} \geq \mathrm{spr}(\mathcal{T}). \end{align} $$

Therefore, if $\mathcal {G}$ is a regular graph, we have $d_{\mathrm {avg}}(\mathcal {G}) = d_{\max }(\mathcal {G})$ , so by putting together (2.1) and (2.2), the formula of Kesten is recovered.

It is hard to find any explicit formula for $\mathrm {spr}(\mathcal {T})$ that only depends on the adjacencies in $\mathcal {G}$ and not, for example, on the paths in $\mathcal {G}$ or the powers of $A_{\mathcal {G}}$ . This is due in part to the fact that two similar base graphs may have universal covering trees with fairly different spectral radii. In Table 2, we used the system of equations in Corollary 6.6 to compute the spectral radii of the respective universal covering trees in Table 1.

Table 2:

Using Mathematica, the system of equations in Corollary 6.6 was solved for the graphs in Table 1. In some cases, explicit solutions in radicals were output. Previous results on the biregular bipartite case mentioned above imply the result for $\mathcal {G}_5$ .

2.4 Graph products and noncommutative probability

In recent years, different problems in spectral graph theory have been approached from the perspective of noncommutative probability theory; we refer the reader to the book of Hora and Obata [Reference Helton, Mai and SpeicherHO07] for a unified exposition. Of particular interest for the present work are a sequence of results [Reference Accardi, Lenczewski and SałapataABGO04, Reference AomotoALS07, Reference O’Donnell and XinyuOba04] which establish a correspondence between different combinatorial graph products and different notions of stochastic independence in noncommutative probability (see Example 2.3). We summarize this correspondence in the dictionary presented in Table 3. As mentioned before, part of the motivation of this project is to extend this dictionary to include the notion of freeness with amalgamation.Footnote ⁷

Table 3:

On the left, graph products are mentioned (see [Reference Accardi, Lenczewski and SałapataABGO04] for definitions). On the right, the corresponding notions of stochastic independence are given (see [Reference Sy and SunadaSW97, Reference MurakiMur01] for definitions of Boolean and Monotone independence, respectively).

Example 2.3 (Cartesian product)

Given two graphs $\mathcal {G}_1$ and $\mathcal {G}_2$ , one may form their Cartesian product $\mathcal {G}_1\, \Box \, \mathcal {G}_2$ , with vertex set and edge set as follows:

$$\begin{align*}V( \mathcal{G}_1 \, \Box \, \mathcal{G}_2) = V(\mathcal{G}_1) \times V(\mathcal{G}_2), \end{align*}$$

$$\begin{align*}E( \mathcal{G}_1 \, \Box \, \mathcal{G}_2) &= \{\{(v, w_1), (v, w_2)\} : \{w_1, w_2\} \in E(\mathcal{G}_2)\} \cup \{\{(v_1, w), (v_2, w)\} \\ &\quad : \{v_1, v_2\} \in E(\mathcal{G}_1)\}. \end{align*}$$

In other words, we have the relation of adjacency matrices $A_{\mathcal {G}_1 \, \Box \, \mathcal {G}_2} = A_{\mathcal {G}_1} \otimes I + I \otimes A_{\mathcal {G}_2}$ . Using this representation, one sees that the spectrum of $\mathcal {G}_1\, \Box \, \mathcal {G}_2$ is the Minkowski sum $\{\lambda _1 + \lambda _2 : \lambda _1 \in \mathrm {Spec}(\mathcal {G}_1), \lambda _2 \in \mathrm {Spec}(\mathcal {G}_2)\}$ . In the language of spectral measures, this says that the density of states $\mu $ of $A_{\mathcal {G}_1\,\Box \,\mathcal {G}_2}$ is the (classical) convolution of the density of states for the constituent graphs; that is, $\mu $ is the law of the sum of two independent random variables distributed according to the density of states of $A_{\mathcal {G}_1}$ and of $A_{\mathcal {G}_2}$ , respectively.

In this work, the free graph product is of particular interest. The connections of this product to free probability were developed by Accardi, Lenczewski, and Sałapata [Reference AomotoALS07]. The authors pointed out that Voiculescu’s notion of free independence introduced in [Reference VoiculescuVoi85] could be used when analyzing the spectrum of free products of graphs. As an example provided in their paper, one can recover the spectral measure of the d-regular infinite tree, as the free convolution of d signed Bernoulli distributions (also known as Rademacher distributions).

However, the roots of the theory of free graph products go back to Kesten [Reference Keller, Lenz and WarzelKes59], who studied the spectra of random walks on free groups. We survey this area in the next subsection.

Finally, we draw attention to the additive graph product recently defined by Mohanty and O’Donnell [Reference McLaughlinMO20], who showed that X-Ramanujan graphs (a generalized notion of Ramanujan graph) can always be obtained by taking certain quotients of any graph constructed via their product. In the aforementioned work, the features of the spectrum of the resulting infinite graphs are left as implicit quantities. Hence, a natural complementary line of research would then be that of understanding the spectrum of the infinite graphs arising from the additive graph product.

2.5 Random walks on groups and free probability

The ’80s and ’90s saw a flurry of activity on the spectra of random walks on Cayley graphs of free products of groups (see [Reference WoessWoe00] for a detailed exposition). The analytic formula relating the spectral measure of the product graph to the spectral measures of its factors (essentially, Voiculescu’s R-transform) was discovered independently by McLaughlin [Reference McKayMcL88], Soardi [Reference SoardiSoa86], and Woess [Reference WoessWoe86], but it was Voiculescu’s work [Reference VoiculescuVoi85] that put it into the more general context of noncommutative probability.

Interestingly, also in [Reference VoiculescuVoi85], Voiculescu laid out a more general theory of freeness with amalgamation, which extends the scalars $\mathbb {C}$ to an arbitrary unital algebra $\mathcal {B}$ . On the other hand, in a parallel way, some progress was also made by the graph theory community in the study of random walks on amalgams [Reference Pimsner and VoiculescuPW85]. In particular, Cartwright and Soardi [Reference Cartwright and SoardiCS86] developed the combinatorial tools to obtain the Green function of the Cayley graph of an amalgamated free product of finite groups, in the particular case in which the subgroup over which amalgamation is performed is a normal subgroup of the groups in the product. In Section 3.3, we explain why the tools of free probability allow one to approach this problem even if the normality assumption is dropped.

3.1 Free probability

Free probability was introduced by Voiculescu in his seminal papers [Reference VoiculescuVoi85, Reference VoiculescuVoi86]. We refer the reader to [Reference Mohanty and O’DonnellMS17, Reference NicaNS06, Reference VoiculescuVDN92] for a detailed introduction. This theory is developed in the context of noncommutative probability, in which random variables are viewed as elements of a noncommutative algebra and the notion of expectation from classical probability is substituted by a linear functional on the algebra.

In this work, the following examples of noncommutative probability spaces are of primary importance.

Example 3.2 Let G be a discrete group, and denote the reduced $C^*$ -algebra of G by $C_{\mathrm {red}}^*(G)$ .Footnote ⁸ Then, the $C^*$ -algebra $C_{\mathrm {red}}^*(G)$ has a canonical state given by

(3.1) $$ \begin{align} \varphi(x) := \langle \delta_e, x \delta_e \rangle, \quad \forall x \in C_{\mathrm{red}}^*(G), \end{align} $$

where $\delta _e \in \ell ^2(G)$ denotes the indicator of the identity element $e\in G$ .

As Voiculescu showed, in noncommutative probability, there is not a unique notion of stochastic independence.

In the proof of Theorem 1.8, we will use the following.

Note that in Proposition 3.3 the random variables $\lambda (g_i)$ are unitaries and satisfy that

(3.2) $$ \begin{align} \varphi(\lambda(g_i)^k) =0 \quad \forall k \in \mathbb{Z}\setminus \{0\}. \end{align} $$

In noncommutative probability, random variables satisfying (3.2) are called Haar unitaries.

3.2 Operator-valued probability spaces

We will require the following generalization of the notion of noncommutative probability space.

In the present, we are interested in the following situations.

Example 3.4 (Matrices with entries in the algebra)

Let $(\mathcal {A}, \varphi )$ be a noncommutative probability space. Then, the algebra $M_n(\mathbb {C})\otimes \mathcal {A}$ (i.e., $n\times n$ matrices with entries in $\mathcal {A}$ ) has a canonical copy of $M_n(\mathbb {C})$ as a subalgebra, namely $M_n(\mathbb {C})\otimes 1_{\mathcal {A}}$ . Hence, $M_n(\mathbb {C})\otimes \mathcal {A}$ can be viewed as an $M_n(\mathbb {C})$ -valued probability space with the conditional expectation $ \mathrm {Id}_{M_n(\mathbb {C})} \otimes \varphi $ . In other words, if $X \in M_n(\mathbb {C})\otimes \mathcal {A}$ is given by $X= (x_{ij})_{i, j=1}^n$ , then E defined by

(3.3) $$ \begin{align} E(X) := (\varphi(x_{ij}))_{i,j=1}^n \in M_n(\mathbb{C}), \end{align} $$

is an $M_n(\mathbb {C})$ -valued conditional expectation.

3.3 Freeness with amalgamation

One of the main technical ingredients of this paper is Voiculescu’s notion of freeness with amalgamation [Reference VoiculescuVoi85, Section 5]. See [Reference VoiculescuVDN92, Section 3.8] and [Reference Mohanty and O’DonnellMS17, Section 9] for an introduction to the subject, and [Reference JekelJek18] for a detailed development.

Observe that in the particular case of $\mathcal {B} = \mathbb {C} 1_{\mathcal {A}}$ , we recover the usual definition of free independence. In this work, we exploit the following relation between freeness and freeness with amalgamation.

The connection with the amalgamated free product of groups is the following.

We are now ready to explain in precise terms the way in which free probability appears in the study of the spectra of Cayley graphs. Consider a finitely generated group G, and let $S\subset G$ be a finite generating set. Denote by $\Gamma (G,S)$ the left Cayley graph of G with respect to S. When it is clear from the context, we will simply write $\Gamma $ . Let $\lambda $ be the left regular representation of G, and note that the operator

$$ \begin{align*} T_{\Gamma} := \sum_{s \in S} \lambda(s) \in C_{\mathrm{red}}^*(G) \end{align*} $$

is the adjacency operator of $\Gamma $ . Indeed, if G is identified with the vertices of $\Gamma $ , then for every $g\in G$ ,

$$ \begin{align*} T_{\Gamma}(\delta_g) = \sum_{ s \in S} \delta_{sg}. \end{align*} $$

Moreover, if S is symmetric, meaning $S = S^{-1}$ , then clearly $\Gamma $ is undirected and $T_{\Gamma }$ is self-adjoint.

Observation 3.8 Let $G_1, G_2$ be two finitely generated groups with a common subgroup H. Let $S_1 \subset G_1$ and $S_2 \subset G_2$ be respective finite generating sets. For $j=1, 2$ , let $\iota _j : G_j \to G_1 \ast _H G_2$ be the canonical inclusion, and let $S = \iota _1(S_1)\cup \iota _2(S_2)$ . Let $\lambda $ be the left regular representation of $G_1 \ast _H G_2$ on $\ell ^2(G_1\ast _H G_2)$ . Let $\Gamma := \Gamma (G_1\ast _H G_2, S ), \Gamma _1 := \Gamma (G_1, S_1)$ , and $\Gamma _2 := \Gamma (G_2, S_2)$ . Then, we have the following decomposition:

$$ \begin{align*} T_{\Gamma} = \sum_{s \in S} \lambda(s) = \sum_{s\in \iota_1(S_1)} \lambda(s) + \sum_{r \in \iota_2(S_2)} \lambda(r) = \widetilde{T_{\Gamma_1}}+ \widetilde{T_{\Gamma_2}}, \end{align*} $$

where $\widetilde {T_{\Gamma _j}}$ denotes the natural inclusion of $T_{\Gamma _j}\in C_{\mathrm {red}}^*(G_j)$ into $C_{\mathrm {red}}^*(\ell ^2(G_1\ast _H G_2))$ . From Proposition 3.7, we know that $\widetilde {T_{\Gamma _1}}$ and $\widetilde {T_{\Gamma _2}}$ are free with amalgamation over $C_{red}^*(H)$ with respect to the conditional expectation $E: C_{\mathrm {red}}^*(G_1\ast _H G_2) \to C_{\mathrm {red}}^*(H)$ defined as in Example 3.5.

3.4 The amalgamated free product of Hilbert $\mathcal {B}$ -modules

In this section, we will assume that $\mathcal {B}$ is a unital $C^*$ -algebra and we will focus on $\mathcal {B}$ -valued probability spaces given by operators on Hilbert modules. The theory of Hilbert modules is delicate, and we refer the reader to [Reference JekelJek18] for a comprehensive treatment. Below, we content ourselves with providing a quick summary of the objects considered here, referring the reader to specific places in [Reference JekelJek18] for details.

A right Hilbert $\mathcal {B}$ -module, say $\mathcal {H}$ , is a right $\mathcal {B}$ -module with a $\mathcal {B}$ -valued inner product

$$ \begin{align*} \langle\cdot , \cdot \rangle: \mathcal{H} \times \mathcal{H} \to \mathcal{B}, \end{align*} $$

for which $\mathcal {H}$ is complete with respect to a norm determined by $\langle \cdot , \cdot \rangle $ in a suitable way (see [Reference JekelJek18, Section 1.2] for definitions and basic properties of these objects). Then, a linear map $T : \mathcal {H} \to \mathcal {H}$ (when viewing $\mathcal {H}$ as a vector space) is said to be right- $\mathcal {B}$ -linear if $T(\eta b)=T(\eta )b$ for all $b\in \mathcal {B}$ and $\eta \in \mathcal {H}$ . The $\mathcal {B}$ -valued inner product on $\mathcal {H}$ allows one to define the adjoint for right- $\mathcal {B}$ -linear operators (which may not always exist), and the norm induced by the inner product leads to a natural definition of bounded right- $\mathcal {B}$ -linear operators (see Section 1.2 and Definitions 1.2.8 and 1.2.9 of [Reference JekelJek18]).

In what follows, for $\mathcal {H}$ a right Hilbert $\mathcal {B}$ -module, we will denote the $\ast $ -algebra of bounded, adjointable (i.e., operators for which the adjoint exists), right $\mathcal {B}$ -linear operators on $\mathcal {H}$ by $\widetilde {B}(\mathcal {H})$ . Then, a Hilbert $\mathcal {B}$ -bimodule $\mathcal {H}$ is defined as a right Hilbert $\mathcal {B}$ -module together with a $\ast $ -homomorphism $\pi : \mathcal {B} \to \widetilde {B}(\mathcal {H})$ . Intuitively, $\pi $ provides a left action of $\mathcal {B}$ on $\mathcal {H}$ (complementing the existing right action provided by the right $\mathcal {B}$ -module structure), so for $b\in \mathcal {B}$ and $\eta \in \mathcal {H}$ , we will use $b \eta $ as a shorthand notation for $\pi (b) \eta $ .

In Section 5, we will work with the following type of operator-valued probability space, introduced by Voiculescu in [Reference VoiculescuVoi85, Section 5.1].

Example 3.9 ( $\mathcal {B}$ -valued conditional expectation on $\widetilde {B}(\mathcal {H})$ )

Assume that $\mathcal {B}$ is a unital $C^*$ -algebra and that $\mathcal {H}$ is a Hilbert $\mathcal {B}$ -bimodule. Furthermore, assume that $\xi \in \mathcal {H}$ is a unit central vector, that is, $\langle \xi , \xi \rangle _{\mathcal {H}} = 1_{\mathcal {B}}$ and $b\xi = \xi b$ for all $b\in \mathcal {B}$ , and consider the decomposition $\mathcal {H} = \xi \mathcal {B} \oplus \overset {\circ }{\mathcal {H}}$ , where $\overset {\circ }{\mathcal {H}}$ denotes the orthogonal complement of $\xi \mathcal {B}$ with respect to the $\mathcal {B}$ -valued inner product of $\mathcal {H}$ (this is well defined by Lemma 4.3.2 in [Reference JekelJek18]). It is easy to see that because $\xi $ is a unit central vector, $\pi : \mathcal {B} \to \widetilde {B}(\mathcal {H})$ induces a $\mathcal {B}$ -bimodule isomorphism between $\mathcal {B}$ and $\xi \mathcal {B}$ , and hence $\mathcal {B}$ can be viewed as a subalgebra of $\widetilde {B}(\mathcal {H})$ (see Lemma 4.3.2 in [Reference JekelJek18]); moreover, the map $E: \widetilde {B}(\mathcal {H}) \to \mathcal {B}$ given by

$$ \begin{align*} E[X] := \langle \xi, X \xi \rangle, \quad \forall X \in \widetilde{B}(\mathcal{H}), \end{align*} $$

is a $\mathcal {B}$ -valued conditional expectation (see Lemma 1.5.4 in [Reference JekelJek18]) and hence $\big (\widetilde {B}(\mathcal {H}), E, \mathcal {B}\big )$ is an operator-valued probability space.

Now, consider a family of Hilbert $\mathcal {B}$ -bimodules $\{\mathcal {H}_i\}_{i\in I}$ , and for every $i\in I$ , suppose that $\xi _i \in \mathcal {H}_i$ is a unit central vector. Then, as in Example 3.9, consider the decomposition $\mathcal {H}_i = \xi _i \mathcal {B} \oplus \overset {\circ }{\mathcal {H}_i}$ and define the $\mathcal {B}$ -valued conditional expectation $E_i(X) := \langle \xi _i, X\xi _i \rangle _{\mathcal {H}_i}$ , so that we can view each $\widetilde {B}(\mathcal {H}_i)$ as a $\mathcal {B}$ -valued probability space. We will now explain how to construct a bigger $\mathcal {B}$ -valued probability space inside which we can find copies of each of the $\widetilde {B}(\mathcal {H}_i)$ that are free with amalgamation over $\mathcal {B}$ . We refer the reader to [Reference VoiculescuVoi85, Section 5] for the original source and [Reference JekelJek18, Section 4] for an extended exposition.

Define the amalgamated free product over $\mathcal {B}$ of the $\mathcal {H}_i$ as

$$ \begin{align*} (\mathcal{H}, \xi) :=\underset{ i \in I}{\ast_{\mathcal{B}}} (\mathcal{H}_i, \xi_i) := \xi\mathcal{B} \oplus \bigoplus_{i_1\neq i_2 \neq \cdots \neq i_n} \overset{\circ}{\mathcal{H}_{i_1}} \otimes_{\mathcal{B}} \cdots \otimes_{\mathcal{B}} \overset{\circ}{\mathcal{H}_{i_n}}. \end{align*} $$

Next, for every $i \in I$ , we consider the subspace of $\mathcal {H}$

$$ \begin{align*} \mathcal{H}(i) := \xi \mathcal{B} \oplus \bigoplus_{i \neq i_1, i_1\neq i_2 \neq \cdots \neq i_n} \overset{\circ}{\mathcal{H}_{i_1}} \otimes_{\mathcal{B}} \cdots \otimes_{\mathcal{B}} \overset{\circ}{\mathcal{H}_{i_n}}, \end{align*} $$

and define the identifications $V_i: \mathcal {H}_i\otimes _{\mathcal {B}} \mathcal {H}(i) \to \mathcal {H} $ by sending $\xi _i \otimes \xi $ to $\xi $ , and in the obvious way identifying $\overset {\circ }{\mathcal {H}_i} \otimes \xi $ with $\overset {\circ }{\mathcal {H}_i}$ , each $\xi _i \otimes (\overset {\circ }{\mathcal {H}_{i_1}}\otimes _{\mathcal {B}} \cdots \otimes _{\mathcal {B}} \overset {\circ }{\mathcal {H}_{i_n}})$ with $\overset {\circ }{\mathcal {H}_{i_1}}\otimes _{\mathcal {B}} \cdots \otimes _{\mathcal {B}} \overset {\circ }{\mathcal {H}_{i_n}}$ and each $\overset {\circ }{\mathcal {H}_i} \otimes _{\mathcal {B}} (\overset {\circ }{\mathcal {H}_{i_1}}\otimes _{\mathcal {B}} \cdots \otimes _{\mathcal {B}} \overset {\circ }{\mathcal {H}_{i_n}})$ with $\overset {\circ }{\mathcal {H}_i} \otimes _{\mathcal {B}} \overset {\circ }{\mathcal {H}_{i_1}}\otimes _{\mathcal {B}} \cdots \otimes _{\mathcal {B}} \overset {\circ }{\mathcal {H}_{i_n}}$ . Then, for every $i \in I$ , define the left actions of the elements in $\widetilde {B}(\mathcal {H}_i)$ on $\mathcal {H}$ by the inclusion $\lambda _i : \widetilde {B}(\mathcal {H}_i) \to \widetilde {B}(\mathcal {H})$ given by

$$ \begin{align*} \lambda_i(X) := V_i (X \otimes \mathrm{Id}_{\mathcal{H}(i)})V_i^{-1}. \end{align*} $$

Finally, note that also $\xi \in \mathcal {H}$ defines a $\mathcal {B}$ -valued conditional expectation on $\widetilde {B}(\mathcal {H})$ given by

$$ \begin{align*} E(X) :=\langle \xi , X \xi \rangle. \end{align*} $$

3.5 The operator-valued R-transform

In what follows, we consider an operator-valued space $(\mathcal {A}, E, \mathcal {B})$ with $\mathcal {A}$ and $\mathcal {B}$ being unital $C^*$ -algebras. Moreover, we assume that E is positive, meaning that $E[XX^*]\geq 0$ for all $X\in \mathcal {A}$ .

In the scalar case, namely when $\mathcal {B} \cong \mathbb {C}$ , Voiculescu’s R-transform is used to compute the distribution of sums of free random variables. See [Reference VoiculescuVDN92, Section 3] for an introductory reference. The same machinery extends without many modifications to the operator-valued context. A good introductory reference for this subject is [Reference Mohanty and O’DonnellMS17, Section 9].

The first step toward defining the operator-valued R-transform is to define the operator-valued version of the Cauchy transform, which essentially is the conditional expectation applied to the resolvent.

Definition 3.5 (Operator-valued Cauchy transform)

Let $\mathbb {H}^+ := \{ b\in \mathcal {B} : \mathrm {Im}(b)> \varepsilon 1_{\mathcal {A}}, \text { for some } \varepsilon > 0 \}$ and $\mathbb {H}^- := -\mathbb {H}^+$ , where $\mathrm {Im}(b) := \frac {b-b^*}{2i}$ . Then, for any self-adjoint $X\in \mathcal {A}$ , the operator-valued Cauchy transform of X is the function $G_X: \mathbb {H}^+ \to \mathbb {H}^-$ given by

(3.4) $$ \begin{align} G_X(b) := E[(b1_{\mathcal{A}}-X)^{-1}]. \end{align} $$

Observation 3.11 We can recover the scalar Cauchy transform from the operator-valued Cauchy transform. More specifically, consider a noncommutative probability space $(\mathcal {A}, \varphi )$ and a unital subalgebra $\mathcal {B}\subset \mathcal {A}$ together with a conditional expectation $E: \mathcal {A} \to \mathcal {B}$ . Furthermore, assume that $\varphi $ and E are compatible in the sense that $\varphi (X) = \varphi (E(X))$ for every $X\in \mathcal {A}$ .

Let $X\in \mathcal {A}$ be self-adjoint, and let $\mu $ be the probability measure on $\mathbb {R}$ given by the distribution of X with respect to $\varphi $ , i.e., $\mu $ is the unique probability measure whose kth moment equals $\varphi (X^k)$ . Then, for $z\in \mathbb {C}$ with $\mathrm {Im}(z)> 0$ , we have that

$$ \begin{align*} \varphi(G_X(z1_{\mathcal{B}})) = \int_{\mathbb{R}} \frac{1}{z-t} d \mu(t), \end{align*} $$

where $G_X$ is as in (3.4).

Without going into much detail, we recall that the operator-valued Cauchy transform has a left inverse when restricted to a proper neighborhood of infinity, so the following definition makes sense.

Definition 3.6 (Operator-valued R-transform)

Let $X \in \mathcal {A}$ be self-adjoint. In a suitable neighborhood of $0_{\mathcal {B}} \in \mathcal {B}$ , the operator-valued R-transform of X, denoted by $R_X$ , is well defined by the following equation:

(3.5) $$ \begin{align} bG_X(b) = 1+R_X(G_X(b)) G_X(b), \end{align} $$

where $G_X(b)$ is as in (3.4).

Many things are known about the R-transform (both the scalar- and operator-valued). Here, we will only need the following fact.

Theorem 3.12 (Voiculescu)

Let $X, Y \in \mathcal {A}$ be self-adjoint random variables that are free with amalgamation over $\mathcal {B}$ , then

$$ \begin{align*} R_{X+Y} = R_X+R_Y, \end{align*} $$

where $R_X$ and $R_Y$ are as in Definition 3.6.

4.1 Sunada’s theorem via aymptotic freeness

Here, we give an alternate route to a theorem of Sunada [Reference Anderson and ZeitouniABS20, Reference SunadaSun92] (i.e. Theorem 1.8) upper-bounding the number of connected components of the spectrum of the universal cover, and below we point out a slight generalization to the case where the base graph is allowed to contain half-loops. However, for now, let us assume that every loop in $\mathcal {G}$ is a whole-loop.

For every d, let

$$ \begin{align*} A_{d, \mathcal{G}} =\sum_{u\in V(\mathcal{G})} b_u \Delta_{uu} \otimes I_d+ \sum_{f\in E(\mathcal{G})} a_f \Delta_{\sigma(f)\tau(f)} \otimes U_f^{(d)} \end{align*} $$

be the Jacobi matrix of a random d-lift, as specified in Definition 2.1. Now, if $\mathcal {G}$ has m undirected edges, say $\{f_1, \check {f}_1\}, \dots , \{f_m, \check {f}_m\}$ , for every $i\in [m]$ , we can use $U_i^{(d)}$ as a shorthand notation of $U_{f_i}^{(d)}$ . Then, by construction, $U_1, \dots , U_m$ are independent random uniform permutation matrices and $\{U_f^{(d)}\}_{f\in E(\mathcal {G})}= \{U_i^{(d)}\}_{i\in [m]} \cup \{(U_i^{(d)})^*\}_{i\in [m]}$ . It easy to see that each $U_i$ converges in distribution to a Haar unitary random variable (see (3.2) for a definition). Moreover, the asymptotic joint distribution is given by the following classical result of Nica.

On the other hand, recall that the result in Proposition 3.3 gives a construction for a family of free Haar unitaries in $C_{\mathrm {red}}^*(\mathbb {F}_m)$ , whereas Lemma 2.2 says that random lifts converge in distribution to $A_{\mathcal {T}}$ . These arguments put together yield the following lemma, which appeared implicitly in [Reference Belinschi and BercoviciBC19].

Lemma 4.2 Let $\{f_1, \check {f}_1\}, \dots , \{f_m, \check {f}_m\}$ be a numbering of the undirected edges of $\mathcal {G}$ , and let $g_1, \dots , g_m$ be the canonical free generators of $\mathbb {F}_m$ , $\varphi $ the canonical trace of $C_{\mathrm {red}}^*(\mathbb {F}_m)$ , and $\lambda $ the left regular representation of $\mathbb {F}_m$ on $\ell ^2(\mathbb {F}_m)$ . Then, the density of states of $A_{\mathcal {T}}$ is the same as the spectral measure of

(4.1) $$ \begin{align} \sum_{u\in V(\mathcal{G})} b_u\Delta_{uu} \otimes 1+ \sum_{i=1}^m a_{f_i}\big( \Delta_{\sigma(f_i)\tau(f_i)}\otimes \lambda(g_{i}) + \Delta_{\tau(f_i)\sigma(f_i)} \otimes \lambda(g_i^{-1}) \big) \end{align} $$

in the noncommutative probability space $(M_n(\mathbb {C})\otimes C_{\mathrm {red}}^*(\mathbb {F}_m), \frac {1}{n}\mathrm {Tr}\otimes \varphi )$ .

Now, the problem has been reduced to studying the spectral measure of a particular operator that lives in a well-studied $C^*$ -algebra.Footnote ¹¹ In order to study the band structure of the spectrum of this random variable, a standard trick in operator K-theory will be used. In the context of graph theory, this technique was first used by Aomoto [Reference Accardi, Ghorbal and ObataA+88] and has been used in the study of different infinite graphs by different authors (e.g., [Reference Keller, Lenz and WarzelKFSH19, Reference SunadaSun92]).

The main technical result that one needs from the theory of $C^*$ -algebras is the following.

Using a standard K-theory argument, it can be seen that the above proposition follows from a deep and technical result of Pimsner and Voiculescu [Reference Picardello and WoessPV82]. A self-contained proof appears in [Reference Anderson and ZeitouniABS20]. We can now show Sunada’s theorem.

Proof Use $T_{\mathcal {G}}$ to denote the operator in (4.1), and let I be a connected component of $\mathrm {Spec}(A_{\mathcal {T}}) = \mathrm {Spec}(T_{\mathcal {G}})$ . Now, let $ \chi _I(x)$ be the indicator function of the set I, and note that since I is a connected component of the spectrum, $\chi _I$ is a continuous function on $\mathrm {Spec}(T_{\mathcal {G}})$ and hence $\chi _I(T_{\mathcal {G}})\in M_n(\mathbb {C}) \otimes C_{\mathrm {red}}^*(\mathbb {F}_m)$ . Moreover, since the range of $\chi _I$ is contained in $\mathbb {R}$ and $\chi _I^2 = \chi _I$ , by the continuous functional calculus, we have that $\chi _I(T_{\mathcal {G}})$ is a projection.

On the other hand, if $\mu _{A_{\mathcal {T}}}$ is the density of states of $A_{\mathcal {T}}$ , and $\mu _{T_{\mathcal {G}}}$ is the spectral measure of $T_{\mathcal {G}}$ with respect to the function $\frac {1}{n}\mathrm {Tr}\otimes \varphi $ , we have that

$$ \begin{align*} \mu_{A_{\mathcal{T}}}(I) = \mu_{T_{\mathcal{G}}}(I) = \int_{\mathrm{Spec}(T_{\mathcal{G}})} \chi_I(x) d \mu_{T_{\mathcal{G}}}(x) = \left( \frac{1}{n} \mathrm{Tr} \otimes \varphi \right) (\chi_I(T_{\mathcal{G}})). \end{align*} $$

So, by Proposition 4.3, the quantity above is $k/n$ for some integer $k \ge 1$ , as desired.

4.2 Allowing half-loops

When the base graph $\mathcal {G}$ has half-loops, a modification of Sunada’s result still holds. In this case, the random permutations in the lift associated with half-loops should be taken to be random matchings. To be precise, if $L(\mathcal {G})$ denotes the set of half-loops of $\mathcal {G}$ , the Jacobi matrix on a random $2d$ -lift is given by

$$ \begin{align*} A_{d, \mathcal{G}} = \!\sum_{u\in V(\mathcal{G})} b_u \Delta_{uu} \otimes I_d+ \!\sum_{f\in L(\mathcal{G})} \Delta_{\sigma(f)\tau(f)}\otimes P_f^{(d)}+ \sum_{f\in E(\mathcal{G})\setminus L(\mathcal{G})} a_f \Delta_{\sigma(f)\tau(f)} \otimes U_f^{(d)}, \end{align*} $$

where the $P_f^{(2d)}$ are independent random permutations distributed uniformly in the space of random matchings of $[2d]$ (i.e., matrices whose corresponding permutation $\alpha $ has no fixed points and satisfies $\alpha ^2 = \mathrm {Id}$ ). It is not hard to see that by the way we defined the universal cover a graph with half-loops (see Section 1.7), we again have Benjamini–Schramm convergence to $\mathcal {T}$ when defining random lifts in this way, and hence Lemma 2.2 still holds.

Now, note that each $P_f^{(2d)}$ is self-adjoint and distributes as a Rademacher random variable with respect to the state $\frac {1}{2d}\mathrm {Tr}(\cdot )$ . On the other hand, by the work of Nica [Reference Nagnibeda and WoessNic93], we know that asymptotic freeness also holds for independent random matchings and independent random uniform permutations. That is, Theorem 4.1 admits the following extension.

On the other hand, a copy in distribution of the free family $\{p_1, \dots , p_{m_1}, u_1, \dots , u_{m_2}\}$ mentioned above is given by the variables

$$ \begin{align*} \{\lambda(h_1), \ldots, \lambda(h_{m_1}), \lambda(g_1), \dots, \lambda(g_{m_2})\}\subset C_{\mathrm{red}}^*(\Gamma_{m_1}\ast \mathbb{F}_{m_2}), \end{align*} $$

where $h_1, \dots , h_{m_1}, \dots , g_1, \dots , g_{m_2}$ are the canonical generators of the group $\Gamma _{m_1}\ast \mathbb {F}_{m_2}$ (recall that $\Gamma _{m_1}$ denotes the free product of $m_1$ copies of $\mathbb {Z}_2$ ), and $\lambda $ denotes the left regular representation. The K-theory of this $C^*$ -algebra is also well understood (see, for example, [Reference SunadaSun92]), and hence one can get the corresponding analog of Proposition 4.3. In this case, one obtains the following result.

The bound of $2n$ is again tight since $\mathcal {G}$ can be a finite tree with a half-loop added to some vertex, in which case $\mathcal {T}$ will be a finite tree with $2n$ vertices, and it is then easy to construct examples where the (in this case finite) Jacobi matrix $A_{\mathcal {T}}$ has $2n$ distinct eigenvalues. Moreover, if one allows the coefficients $b_v$ to be nonzero, then one can obtain many more examples with $2n$ bands. In particular, we have the following example, which was pointed out to us by Barry Simon. Roughly speaking, one may take n disjoint copies $\mathcal {G}_1, \dots , \mathcal {G}_n$ of a fixed finite graph $\mathcal {G}$ (and its graph Jacobi matrix), add different large multiples of the identity to the Jacobi matrix on each $\mathcal {G}_i$ , and then connect the $\mathcal {G}_i$ by some edges with very small weights $a_f$ . This produces a connected graph $\mathcal {G}'$ whose universal cover has n times as many spectral bands as $A_{\mathcal {G}}$ . If $\mathcal {G}$ is a single vertex with a whole-loop and a half-loop with coefficients chosen so that the spectrum of $A_{\mathcal {T}(\mathcal {G})}$ has two bands by Theorem A.1, then $A_{\mathcal {T}(\mathcal {G}')}$ has $2n$ bands in its spectrum.

5.1 Combinatorial description

First, following the presentation in [Reference AomotoALS07], we recall Quenell’s free product of rooted graphs. Let $\mathcal {G}_1=(\mathcal {V}_1, \mathcal {E}_1, e_1),\, \dots ,\, \mathcal {G}_n=(\mathcal {V}_n, \mathcal {E}_n, e_n)$ be rooted graphs, and for every $i\in [n]$ , denote $\overset {\circ }{\mathcal {V}_i} := \mathcal {V}_i \setminus \{e_i\}$ . The free product of rooted graphs will be denoted by $\ast \{\mathcal {G}_i\}_{i=1}^n$ .

The vertex set of $\ast \{\mathcal {G}_i\}_{i=1}^n$ will be the following set of words:

(5.1) $$ \begin{align} \ast \{\mathcal{V}_i\}_{i=1}^n := \{e \} \cup \{v_m\cdots v_1 : v_k \in \overset{\circ}{\mathcal{V}_{i_k}} \text{and } i_k \neq i_{k+1} \text{ for } 1 \le k \le m-1, m\geq 1 \}. \end{align} $$

As in [Reference AomotoALS07], we think of e as the empty word and we allow the roots $e_i$ to appear in words also playing the role of an empty word, that is, if $w \in \ast \{\mathcal {V}_i\}_{i=1}^n$ , then we have the convention $we_i = e_i w = w$ . The set of edges in the free product is defined as follows:

(5.2) $$ \begin{align} \ast \{ \mathcal{E}_i\}_{i=1}^n = \left\{(vw, v'w) : (v, v') \in \cup_{i\in [n]} \mathcal{E}_i \text{ and } w, vw, v'w \in \ast \{ \mathcal{V}_i\}_{i=1}^n \right\}. \end{align} $$

In summary, $\ast \{\mathcal {G}_{i}\}_{i=1}^n = (\ast \{\mathcal {V}_i\}_{i=1}^n, \ast \{\mathcal {E}_i\}_{i=1}^n , e)$ . See Figure 1 for an example.

Figure 1:

The free product of two graphs $\mathcal {G}_1$ and $\mathcal {G}_2$ .

We now expand the notion of free product of graphs by introducing the concept of relator graph.

Our amalgamated free product of rooted graphs $\mathcal {G}_1=(\mathcal {V}_1, \mathcal {E}_1, e_1), \dots , \mathcal {G}_n=(\mathcal {V}_n, \mathcal {E}_n, e_n)$ will be defined relative to a relator graph $(\mathcal {G}, c)$ and a coloring of the $\mathcal {G}_i$ compatible with the coloring of the relator graph. The colorings together with the graph structure of the relator graph indicate how the $\mathcal {G}_i$ will be combined to form an infinite (possibly disconnected) multirooted graph. Thus, one may obtain different results even when the $\mathcal {G}_i$ are fixed, if the relator $(\mathcal {G}, c)$ is modified.

To lighten notation, sometimes we will use $\ast _{(\mathcal {G}, c)}\{\mathcal {G}_i\}_{i=1}^n$ and $\ast _{(\mathcal {G}, c)}\{\mathcal {E}_i\}_{i=1}^n$ , as shorthand notations for $*_{(\mathcal {G}, c)} \left \{(\mathcal {G}_i, c_i)\right \}_{i=1}^n$ and $*_{(\mathcal {G}, c)} \left \{(\mathcal {E}_i, c_i)\right \}_{i=1}^n$ , respectively.

We first observe that this product generalizes different relevant constructions.

Example 5.1 (Universal cover of a graph)

Let $\mathcal {G}=(\mathcal {V}, \mathcal {E})$ be a finite graph with k vertices.

First, we consider the case where $\mathcal {G}$ has no loops. Let m be the number of undirected edges in $\mathcal {G}$ , and let $c: \mathcal {E} \to [m]$ be a coloring satisfying $c(f)=c(\check {f})$ and $c(f_1)\neq c(f_2)$ whenever $f_1 \neq f_2$ and $\check {f}_1\neq f_2$ . Then, choose $(\mathcal {G}, c)$ as the relator graph, and for every $i\in [m]$ , let $\mathcal {G}_i$ be a rooted graph consisting of two vertices (one of them being the root $e_i$ ) connected by a single undirected edge with color i.

Now, if $\mathcal {G}$ has loops, one should replace every whole-loop for two half-loops. Then, m is defined as the number of undirected nonloop edges in $\mathcal {G}$ plus the number of half-loops. Once again, one considers a coloring $c: \mathcal {E} \to [m]$ with $c(f_1)=c(f_2)$ if and only if $f_1=f_2$ or $\check {f}_1=f_2$ . The rest is done as in the no-loop case.

In any case, with this construction, note that $\mathcal {T}_{\mathrm {full}}:= \ast _{(\mathcal {G}, c)} \{\mathcal {G}_i\}_{i=1}^m$ has k roots $(1, e), \dots , (k, e)$ and that the connected component of $\mathcal {T}_{\mathrm {full}}$ containing $(i, e)$ , say $\mathcal {T}_i$ , is isomorphic to $\mathcal {T}(\mathcal {G})$ . Moreover, $\mathcal {T}_i$ and $\mathcal {T}_j$ are disjoint whenever $i\neq j$ and the unique root $(i, e)$ in $\mathcal {T}_i$ is in the fiber of $i\in V(\mathcal {G})$ . See Figure 2 for an example.

Figure 2:

Here, we illustrate the construction in Example 5.1 in the particular case of a graph $\mathcal {G}$ with three vertices and three edges. On the top left, we have the graph $\mathcal {G}$ and the graphs $\mathcal {G}_1, \mathcal {G}_2, \mathcal {G}_3$ defined in the construction. On the top right, a part of the vertex set $\ast _{(\mathcal {G}, c)}\{\mathcal {V}_i\}_{i=1}^n$ is shown, which in general is the union of the vertex sets of k disjoint m-regular trees, where m is the number of undirected edges in $\mathcal {G}$ . The vertices of these m-regular trees correspond to sequences of edges in $\mathcal {G}$ containing all nonbacktracking walks, and the connected components of the amalgamated graph product $\ast _{(\mathcal {G}, c)}\{\mathcal {G}_i\}_{i=1}^n$ (which are copies of $\mathcal {T}$ ) move across the different k levels in the vertex set, as it can be seen in the lower part of the image, which is part of the connected component containing the root $(1, e)$ .

Example 5.2 (Free products of graphs)

Given n finite rooted graphs $\mathcal {G}_1 = (\mathcal {V}_1, \mathcal {E}_1, e_1), \dots , \mathcal {G}_n = (\mathcal {V}_n, \mathcal {E}_n, e_n)$ , one can construct its free product by taking $\mathcal {G}=(\mathcal {V}, \mathcal {E})$ to be the graph that has only one vertex and n half-loops around it. Then, for any $i\in [n]$ , let $\mathcal {C}_i$ be the singleton $\{i\}$ , that is, $c_i$ will color all edges in $\mathcal {G}_i$ with color i. And, $c: \mathcal {C} \to [n]$ will color each half-loop in $\mathcal {G}$ with a different color.

With this setup, it is easy to see that

$$\begin{align*}\ast_{(\mathcal{G}, c)} \{(\mathcal{G}_i, c_i)\}_{i=1}^n = \ast \{\mathcal{G}_i\}_{i=1}^n. \end{align*}$$

In this case, because the relator graph has only one vertex, the amalgamated product has only one root. Hence, this construction generalizes Quenell’s free product of graphs.

So far, all the discussion in this section has been at the level of combinatorics; however, our main result here is about Jacobi operators. It is then necessary to clarify how edge weights and vertex potentials can be incorporated in our framework.

Definition 5.3 (Lifting coefficients)

If the relator graph, $\mathcal {G}=(\mathcal {V}, c)$ has edge weights a and vertex potential b, then the graph $\ast _{(\mathcal {G}, c)} \{\mathcal {G}_i\}_{i=1}^n$ can be endowed with “periodic” edge weights $\tilde {a}$ and vertex potential $\tilde {b}$ in a natural way as follows:

$$ \begin{align*} \tilde{a}_{\big( (l, vw), (l', v'w)\big)} := a_{(l, l')} \quad \text{and} \quad \tilde{b}_{(l, w)}:= b_l, \end{align*} $$

for all $\big ( (l, vw), (l', v'w)\big )\in \ast _{(\mathcal {G}, c)} \{\mathcal {E}_i\}_{i=1}^n$ and $(l, w)\in \ast _{(\mathcal {G}, c)} \{\mathcal {V}_i\}_{i=1}^n$ .

When working with Jacobi operators on amalgamated free products of graphs, it will be convenient to have the following notation.

We are now ready to state the main theorem.

To see Theorem 5.4 in action, we refer the reader to Section 5.4, where we combine Example 5.1 and Theorem 5.4 to obtain a $C^*$ -representation of periodic Jacobi operators on universal covers.

5.2 Proof of Theorem 5.4

Since we care about the explicit action of the operators in question, we think of the $X_{\alpha }$ as elements in $B(\ell ^2(\mathcal {V}))$ and of the $A_{\alpha }$ as elements of $B(\ell ^2(\mathcal {V}_i))$ if $\alpha \in \mathcal {C}_i$ . To lighten notation, let

$$ \begin{align*} \mathcal{B} := B(\ell^2(\mathcal{V})) \cong M_k(\mathbb{C}), \end{align*} $$

and because of the last equivalence, let $I_k$ denote the unit of $\mathcal {B}$ . In what follows, the notion of tensor will be used in different ways, and we will use $\otimes _{\mathcal {B}}, \otimes _{\mathbb {C}}$ , and $\otimes $ to denote the tensor of $\mathcal {B}$ -modules, $\mathbb {C}$ -algebras, and $\mathbb {C}$ -vector spaces, respectively. However, to avoid overloading, the subscript in $\otimes _{\mathcal {B}}$ will be dropped when using it to denote pure tensor elements in a $\mathcal {B}$ -module tensor product.

For clarity of exposition, we divide the proof in several steps. The first one consists in defining the building blocks $\mathcal {H}_i$ to which we apply the construction of the amalgamated free product for Hilbert modules described in Section 3.4.

Step 1: Construction of the operator-valued probability spaces. For every $i\in [n]$ , let

$$ \begin{align*} \mathcal{H}_i := \mathcal{B} \otimes \ell^2(\mathcal{V}_i), \end{align*} $$

and note that this is a $\mathcal {B}$ -bimodule with the right and left actions of $\mathcal {B}$ on pure tensors given by

(5.3) $$ \begin{align} (X\otimes \eta) Y & := XY \otimes \eta \quad \text{and} \quad Y(X\otimes \eta) \nonumber \\ & = YX \otimes \eta \quad \forall X, Y \in \mathcal{B}, \, \forall \eta \in \ell^2(\mathcal{V}_i), \end{align} $$

and then extended by linearity. Moreover, we can turn each $\mathcal {H}_i$ into a right Hilbert $\mathcal {B}$ -module by using the $\mathcal {B}$ -valued inner product determined by

(5.4) $$ \begin{align} \langle X\otimes \eta, Y\otimes \zeta \rangle_{\mathcal{H}_i} := \langle \eta, \zeta \rangle_{\ell^2(\mathcal{V}_i)} X^* Y, \quad \forall X, Y \in \mathcal{B}, \, \forall \eta, \zeta \in \ell^2(\mathcal{V}_i). \end{align} $$

In fact, because we are working with finite-dimensional spaces, operators are automatically bounded, so this turns $\mathcal {H}_i$ into a Hilbert $\mathcal {B}$ -bimodule where, as expected, the representation $\pi _i : \mathcal {B} \to \widetilde {B}(\mathcal {H}_i)$ is given by the left action of $\mathcal {B}$ on $\mathcal {H}_i$ .

Now, recall that, for every $i\in [n]$ , $e_i \in \mathcal {V}_i$ denotes the root of $\mathcal {G}_i$ , so $\delta _{e_i} $ is the distinguished vector in the Hilbert space $\ell ^2(\mathcal {V}_i)$ . Following the construction outlined in Section 3.4, we set $\xi _i := I_k \otimes \delta _{e_i}$ to be the distinguished vector of $\mathcal {H}_i$ . It is easy to see that $\xi _i$ is a unit central vector, and moreover, by (5.3), $\xi _i \mathcal {B} = \mathcal {B}\otimes \delta _{e_i}$ . Hence, the decomposition $\mathcal {H}_i= \xi _i \mathcal {B} \oplus \overset {\circ }{\mathcal {H}_i}$ satisfies

$$ \begin{align*} \overset{\circ}{\mathcal{H}_i} = \mathcal{B} \otimes \ell^2(\overset{\circ}{\mathcal{V}_i} ), \end{align*} $$

where as before $\overset {\circ }{\mathcal {V}_i} := \mathcal {V}_i\setminus \{e_i\}$ .

As mentioned in Example 3.9, the $\ast $ -algebra of bounded, adjointable, right $\mathcal {B}$ -linear operators $\widetilde {B}(\mathcal {H}_i)$ is a $\mathcal {B}$ -valued probability space with the conditional expectation defined by $E_i(S) := \langle \xi _i, S\xi _i\rangle _{\mathcal {H}_i}$ for every $S\in \widetilde {B}(\mathcal {H}_i)$ . However, since $\mathcal {B}$ and $B(\ell ^2(\mathcal {V}_i))$ are finite-dimensional, we can use the identification

$$ \begin{align*} \widetilde{B}(\mathcal{H}_i) \cong \mathcal{B} \otimes_{\mathbb{C}} B(\ell^2(\mathcal{V}_i)), \end{align*} $$

by letting each $X \otimes A \in \mathcal {B}\otimes _{\mathbb {C}} B(\ell ^2(\mathcal {V}_i))$ act on $\mathcal {H}_i$ by

(5.5) $$ \begin{align} X\otimes A (X' \otimes \eta) = XX' \otimes A \eta, \quad \forall X' \in \mathcal{B}, \forall \eta \in \ell^2(\mathcal{V}_i), \end{align} $$

and extending this definition by linearity to all elements in $\mathcal {B}\otimes _{\mathbb {C}} B(\ell ^2(\mathcal {V}_i))$ . Now, note that under this identification, the $E_i$ we just defined also coincide with the construction given in Example 3.4, since for a pure tensor $X \otimes A \in \mathcal {B} \otimes _{\mathbb {C}} B(\ell ^2(\mathcal {V}_i)) $ we have, by (5.4) and (5.5), that

$$ \begin{align*} E_i( X \otimes A) &= \langle \xi_i , X \otimes A (\xi_i) \rangle_{\mathcal{H}_i} = \langle I_k \otimes \delta_{e_i}, X \otimes A (I_k\otimes \delta_{e_i}) \rangle_{\mathcal{H}_i} \nonumber \\ &= \langle I_k\otimes \delta_{e_i} , X \otimes A \delta_{e_i} \rangle_{\mathcal{H}_i} = \langle \delta_{e_i}, A \delta_{e_i} \rangle_{\ell^2(\mathcal{V}_i)} X. \end{align*} $$

Step 2: Defining $\mathcal {A}$ , $\varphi $ , and the $T_i$ . Note that $\mathcal {B}$ and the Hilbert $\mathcal {B}$ -bimodules $\mathcal {H}_i$ satisfy all the conditions required in Section 3.4, so we can go ahead with the construction of the amalgamated free product. Define

$$ \begin{align*} \mathcal{H} &:= \xi\mathcal{B} \oplus \bigoplus_{i_1\neq i_2 \neq \cdots \neq i_m} \overset{\circ}{\mathcal{H}_{i_1}} \otimes_{\mathcal{B}} \cdots \otimes_{\mathcal{B}} \overset{\circ}{\mathcal{H}_{i_m}}, \end{align*} $$

where $\xi = I_k \otimes \delta _e$ and $\delta _e$ is the vector resulting from identifying the $\delta _{e_i}$ , and let $\mathcal {A} := \widetilde {B}(\mathcal {H})$ . Then, for every $i \in [n]$ , set $\lambda _i : \widetilde {B}(\mathcal {H}_i) \to \mathcal {A}$ to be the inclusions described in Section 3.4 and define

$$ \begin{align*} T_i := \sum_{\alpha \in \mathcal{C}_i} \lambda_i(X_{\alpha} \otimes A_{\alpha}). \end{align*} $$

With these definitions, from Theorem 3.10, it is clear that the $T_i$ are free with amalgamation over $\mathcal {B}$ with respect to the conditional expectation E, and that each $T_i$ has the same distribution as

$$ \begin{align*} \sum_{\alpha\in \mathcal{C}_i} X_{\alpha} \otimes A_{\alpha}. \end{align*} $$

This proves the claims about the $T_i$ made in items (2) and (3) in Theorem 5.4. Before completing the proof of the theorem, we will understand better the structure of $\mathcal {H}$ .

Step 3: Rewriting $\mathcal {H}$ and defining D. First, recall that

$$ \begin{align*} \mathcal{H} &= \xi\mathcal{B} \oplus \bigoplus_{i_1\neq i_2 \neq \cdots \neq i_m} \overset{\circ}{\mathcal{H}_{i_1}} \otimes_{\mathcal{B}} \cdots \otimes_{\mathcal{B}} \overset{\circ}{\mathcal{H}_{i_m}} \\ &= \mathcal{B}\otimes \delta_{e} \oplus \bigoplus_{i_1\neq i_2 \neq \cdots \neq i_m} (\mathcal{B}\otimes \ell^2(\overset{\circ}{\mathcal{V}}_{i_1})) \otimes_{\mathcal{B}} \cdots \otimes_{\mathcal{B}} (\mathcal{B}\otimes \ell^2(\overset{\circ}{\mathcal{V}}_{i_m})) \nonumber \end{align*} $$

and note that as $\mathcal {B}$ -bimodules we have the identification

$$ \begin{align*} (\mathcal{B}\otimes \ell^2(\overset{\circ}{\mathcal{V}}_{i_1})) \otimes_{\mathcal{B}} \cdots \otimes_{\mathcal{B}} (\mathcal{B}\otimes \ell^2(\overset{\circ}{\mathcal{V}}_{i_m})) \cong \mathcal{B} \otimes \ell^2(\overset{\circ}{\mathcal{V}}_{i_1})\otimes \cdots \otimes \ell^2(\overset{\circ}{\mathcal{V}}_{i_m}), \end{align*} $$

for every $i_1\neq i_2 \neq \cdots \neq i_m$ . So we can view $\mathcal {H}$ as follows:

$$ \begin{align*} \mathcal{H} & \cong \mathcal{B} \otimes \delta_e \oplus \bigoplus_{i_1\neq i_2 \neq \cdots \neq i_m} \mathcal{B} \otimes \ell^2(\overset{\circ}{\mathcal{V}}_{i_1})\otimes \cdots \otimes \ell^2(\overset{\circ}{\mathcal{V}}_{i_m})\\ & \cong \mathcal{B} \otimes \mathcal{K}, \end{align*} $$

where $\mathcal {K} := \ast _{\mathbb {C}} \{\ell ^2(\mathcal {V}_i)\}_{i=1}^n$ , and the last equivalence (which is clearly true at the level of $\mathcal {B}$ -bimodules for the algebraic direct sum) holds at the level of Hilbert $\mathcal {B}$ -bimodules because $\mathcal {B}$ is finite-dimensional. We can then use this identification to define

$$ \begin{align*} D:= \text{diag}(b_1, \dots, b_k)\otimes \text{Id}_{\mathcal{K}}. \end{align*} $$

It is clear that $D\in \mathcal {A}$ and that it is free with amalgamation over $\mathcal {B}$ from any other element in $\mathcal {A}$ , as stated in (2).

Step 4: Interpreting T as the Jacobi operator. Define $T:=D+T_1+\cdots +T_n$ , and for every $i, j\in [k]$ , let $\Delta _{ij}$ denote the operator in $\mathcal {B}$ corresponding to the matrix in $M_k(\mathbb {C})$ with a 1 in the entry $(i, j)$ and 0 everywhere else. Observe that

(5.6) $$ \begin{align} \Delta_{ij} \Delta_{lm} = \begin{cases} \Delta_{im}, & \text{if }j =l, \\ 0, & \text{otherwise}, \end{cases} \end{align} $$

and hence the lth column space $C_l := \mathrm {Span} \{\Delta _{i l} : i\in [k]\} $ is a left ideal of $\mathcal {B}$ for every $l \in [k]$ (where the span is taken at the level of $\mathbb {C}$ -vector spaces).

The main idea in this step is to find a $\mathbb {C}$ -vector subspace W of $\mathcal {H}$ that is T-invariant and such that a $\mathbb {C}$ -basis of W can be bijected with $\ast _{(\mathcal {G}, c)} \{\mathcal {V}_i\}_{i=1}^n$ so that it is clear that T acts on W in the same way that the Jacobi operator acts on $\ell ^2(\ast _{(\mathcal {G}, c)} \{\mathcal {V}_i\}_{i=1}^n)$ . With this end, recall that $\mathcal {K} := \ast _{\mathbb {C}} \{\ell ^2(\mathcal {V}_i)\}_{i=1}^n$ and for every $l\in [k]$ define

$$ \begin{align*} W_l:= C_l \otimes \mathcal{K}, \end{align*} $$

and consider the $\mathbb {C}$ -basis for $W_l$ given by

$$ \begin{align*} \Theta_l := \{ \Delta_{il} \otimes \delta_e & : i \in [k]\} \cup \{ \Delta_{il} \otimes \delta_{v_m}\otimes \cdots \otimes \delta_{v_1} \\ & : i \in [k], v_1\in \overset{\circ}{\mathcal{V}}_{i_1}, \dots, v_m\in \overset{\circ}{\mathcal{V}}_{i_m}, i_1 \neq i_{2} \neq \cdots \neq i_m\}. \end{align*} $$

Now, because $C_l$ is a left ideal of $\mathcal {B}$ , it is clear that $W_l$ is left-invariant under the action of each $T_j$ and D, and hence it is invariant under the action of T. Then, we can decompose

$$ \begin{align*} I_k \otimes \delta_e = \sum_{i=1}^k \Delta_{ii} \otimes \delta_e, \end{align*} $$

and it will follow that $ T^p(\Delta _{ll}\otimes \delta _e)\in W_l$ for every l and every p. On the other hand,

$$ \begin{align*} E[T^p] = \langle I_k\otimes \delta_e , T^p (I_k\otimes \delta_e) \rangle_{\mathcal{H}} = \sum_{l=1}^k \sum_{i=1}^k \langle \Delta_{ii}\otimes \delta_e, T^p(\Delta_{ll}\otimes \delta_e) \rangle_{\mathcal{H}}, \end{align*} $$

and because of the construction of $\langle \cdot , \cdot \rangle $ , and since $C_l$ is a left ideal, it is easy to see that

$$ \begin{align*} \sum_{i=1}^k \langle \Delta_{ii}\otimes \delta_e, T^p(\Delta_{ll}\otimes \delta_e) \rangle_{\mathcal{H}}\in C_l, \quad \forall l\in [k]. \end{align*} $$

Similarly, we can define the row space $R_i= \mathrm {Span}\{\Delta _{ij} : j\in [k]\}$ , which is a right ideal, and use the same reasoning to conclude that $\langle \Delta _{ii}\otimes \delta _e, T^p(\Delta _{ll}\otimes \delta _e) \rangle _{\mathcal {H}} \in R_i$ for every i. Hence, if we view $E[T^p]$ as a $k\times k$ matrix, we get that

(5.7) $$ \begin{align} E[T^p](i, l) = \langle \Delta_{ii} \otimes \delta_e, T^p(\Delta_{ll}\otimes \delta_e) \rangle_{\mathcal{H}}. \end{align} $$

To analyze the above expression, for any word $w=v_m \cdots v_1\in \ast \{\mathcal {V}_i\}$ , denote $\delta _w := \delta _{v_m} \otimes \cdots \otimes \delta _{v_1}$ and note that

$$ \begin{align*} \Delta_{sl} \otimes \delta_w \mapsto (s, w) \end{align*} $$

is a bijection between $\Theta _l$ and the vertex set $\ast _{(\mathcal {G}, c)} \{\mathcal {V}_i\}$ . Moreover, for every $j\in [n]$ , any $w\in \ast \{\mathcal {V}_i\}$ , and any $v\in \mathcal {V}_j$ , it is clear that

$$ \begin{align*} & T_j(\Delta_{sl}\otimes \delta_{vw}) \\ &\quad = \sum_{\alpha\in \mathcal{C}_j}\, \sum_{f_1\in \sigma_{\mathcal{E}}(s),\, f_2\in \sigma_{\mathcal{E}_j}(v)} X_{\alpha}\big(\sigma(f_1), \tau(f_1)\big) A_{\alpha} \big( \sigma(f_2), \tau(f_2) \big)\cdot \Delta_{\tau(f_1)l}\otimes \delta_{\tau(f_2)w} \\ &\quad = \sum_{\substack{s'\in \mathcal{V}, \, v'\in \mathcal{V}_j \\ (s, s')\in \mathcal{E},\, (v, v')\in \mathcal{E}_j,\, c(s, s')=c_j(v, v')}} a_{(s, s')} \cdot \Delta_{s'l}\otimes \delta_{v'w}, \end{align*} $$

where in the first line we have used the notation $\sigma _{\mathcal {E}}$ and $\sigma _{\mathcal {E}_j}$ , to emphasize that $\sigma _{\mathcal {E}}(s):=\sigma (s)\subset \mathcal {E}$ and $\sigma _{\mathcal {E}_j}(v):=\sigma (v)\subset \mathcal {E}_j$ . It is also clear that

$$ \begin{align*} D (\Delta_{sl}\otimes \delta_w) = b_s \Delta_{sl}\otimes \delta_w. \end{align*} $$

From the above, it follows that T acts on $\Theta _l$ in the same way in which J acts on $\ast _{(\mathcal {G}, c)} \{\mathcal {V}_i\}_{i=1}^n$ as we wanted to show.

Therefore,

$$ \begin{align*} T^p(\Delta_{ll}\otimes \delta_e) = \sum c_{i, v_1, \dots, v_m} \Delta_{i, l} \otimes \delta_{v_m}\otimes \cdots \delta_{v_1}, \end{align*} $$

where the sum ranges over all tuples $(i, v_m, \dots , v_1)$ for which there is a (possibly lazy) walk of length p in $\ast _{(\mathcal {G}, c)}\{\mathcal {G}_i\}_{i=1}^n$ between the vertices $(l, e)$ and $(i, v_m \cdots v_1)$ , where the coefficients $c_{i, v_1, \dots , v_m}$ are determined by the edge weights and vertex potential. So, recalling (5.7) and the definition of the inner product $\langle \cdot , \cdot \rangle _{\mathcal {H}}$ , we can conclude that $E[T^p](i, l)$ is the sum of weighted walks of length p between $(l, e)$ and $(i, e)$ , as we wanted to show.

5.3 Amalgamated free product of groups as amalgamated free product of graphs

Here, we show that Cayley graphs of amalgamated free products of finite groups can be realized as an amalgamated free product of finite graphs. Note that this is not an obvious fact and requires a proof. In the setup of Observation 3.8, freeness with amalgamation appears because we are working in a group $C^*$ -algebra of an amalgamated free group product. In contrast, in the case of the amalgamated free graph product, the freeness with amalgamation comes from the fact that we are working in a tensor algebra.

In this section, we will consider finite groups $G_1, \dots , G_n$ with a common subgroup H. And we will work with the right cosets of H in each of this groups. For every i, we will fix $R_i$ with $e_{G_i}\in R_i$ to be a set of representatives of the right cosets of H in $G_i$ , and heavily exploit the following structural theorem for amalgamated graph products (see [Reference SerreSer80, Section 1.2, Theorem 1]).

Theorem 5.6 (Structure of amalgamated free products of groups)

Let $H, G_i$ , and $R_i$ be as above. Then, every element g of the amalgamated free product $G:= \ast _H \{G_i\}_{i=1}^n$ has a unique representation of the form

$$ \begin{align*} g=hr_m \cdots r_1, \end{align*} $$

where $h\in H$ , $r_j\in R_{i_j}\setminus \{e_{G_{i_j}}\}$ , and $i_{j+1}\neq i_{j}$ . This representation is called the normal form of g.

Although we have chosen to consider right cosets, we will be interested in constructing left Cayley graphs (the reason for this discrepancy will become apparent below). As in Section 3.3, given a group G and a generating set S, we denote the left Cayley graph of G with respect to S by $\Gamma (G, S)$ . Now, for every i, fix $S_i$ a symmetric generating set of $G_i$ , that is, assume that for every $s\in S_i$ one also has $s^{-1}\in S_i$ . The symmetry of the symmetric sets will ensure that the constructed graphs are undirected.

Below, we will show how to construct the Cayley graph $\Gamma (\ast _H \{G_i\}_{i=1}^n, S)$ for $S=\bigcup _{i=1}^n S_i$ as an amalgamated free product of graphs $\{\mathcal {G}_i\}_{i=1}^n$ over some relator graph $(\mathcal {G}, c)$ . However, before describing the construction in detail, we provide some intuition on why such construction should exist. First, note that, for every i, we can view $G_i$ as the amalgamated free product of the singleton $\{G_i\}$ over H, and apply Theorem 5.6 with $n=1$ to obtain that every $g\in G_i$ can be uniquely represented as $g=hr$ with $h\in H$ and $r\in R_i$ . This induces a bijection between $G_i$ and $H\times R_i$ , which in turn induces an isomorphism between the vector spaces $\ell ^2(G)$ and $\ell ^2(H)\otimes \ell ^2(R_i)$ . On the other hand, the Jacobi operator on $\Gamma (G, S)$ is constructed via the operators $\lambda _s : \ell ^2(G_i)\to \ell ^2(G_i)$ given by the left regular representation of $G_i$ . The idea is that, because $\ell ^2(G_i)\cong \ell ^2(H)\otimes \ell ^2(R_i)$ , we can view $\lambda _s$ as an operator over the latter, and decompose it as a sum of pure tensors in $B(\ell ^2(H))\otimes B(\ell ^2(R_i))$ . Once this is done, one is precisely in the setup of the amalgamated graph product. Below, we exemplify this procedure in the case of two small abelian groups, and we later present the general construction.

Example 5.7 Here, we provide an explicit construction for the Jacobi operator on the Cayley graph of $SL(2, \mathbb {Z})$ with respect to some canonical generators. It is well known that this group can be viewed as the free product of $\mathbb {Z}_4$ and $\mathbb {Z}_6$ with amalgamation over $\mathbb {Z}_2$ , and has the finite presentation

$$\begin{align*}SL(2, \mathbb{Z}) \cong \langle x, y \mid x^4 = y^6 = 1, x^2 = y^3\rangle. \end{align*}$$

Let $\lambda _{\mathbb {Z}_4}, \lambda _{\mathbb {Z}_6}$ denote the left regular representations of $\mathbb {Z}_4$ and $\mathbb {Z}_6$ , respectively, and note that the cosets of (the inclusion of) $\mathbb {Z}_2$ in $\mathbb {Z}_4$ and $\mathbb {Z}_6$ are $\{\{0, 2\}, \{1, 3\}\}$ and $\{\{0, 3\}, \{1, 4\}, \{2, 5\}\}$ , respectively. Then, fix the generating sets $S_1=\{1, -1\}\subset \mathbb {Z}_4$ and $S_2=\{-1, 1\}\subset \mathbb {Z}_6$ .

Now, consider the algebra inclusions (constructed as above)

$$ \begin{align*} \chi_1: \mathbb{C}[\mathbb{Z}_4]\to B(\ell^2(\mathbb{Z}_2))\otimes B(\ell^2(\{0, 2\}, \{1, 3\})) \end{align*} $$

and

$$ \begin{align*} \chi_2: \mathbb{C}[\mathbb{Z}_6] \to B(\ell^2(\mathbb{Z}_2)) \otimes B(\ell^2(\{0, 3\}, \{1, 4\}, \{2, 5\})). \end{align*} $$

We start by evaluating $\chi _1 $ at the element $\lambda _{\mathbb {Z}_4}(1)+ \lambda _{\mathbb {Z}_4}(-1)$ (which is the Jacobi operator of $\Gamma (\mathbb {Z}_4, S_1)$ ) where we use the coset representatives $R = \{0, 1\}$ . It is easily seen that

$$ \begin{align*} \chi_1(\lambda_{\mathbb{Z}_4}(1)+ \lambda_{\mathbb{Z}_4}(-1)) = \left(\begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array}\right) \otimes \left(\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}\right) + \left(\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}\right) \otimes \left(\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}\right). \end{align*} $$

Similarly, we evaluate $\chi _2$ on $\lambda _{\mathbb {Z}_6}(1)+ \lambda _{\mathbb {Z}_6}(-1)$ where the set of coset representatives $R = \{0, 1, 2\}$ is used to obtain

$$ \begin{align*} \chi_2(\lambda_{\mathbb{Z}_6}(1)+ \lambda_{\mathbb{Z}_6}(-1)) = \left(\begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array}\right) \otimes \left(\begin{array}{ccc} 0 & 1 & 0\\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{array}\right) + \left(\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}\right) \otimes \left(\begin{array}{ccc} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \end{array}\right). \end{align*} $$

With the above, one can decompose the Jacobi operator on the Cayley graph of $SL(2, \mathbb {Z})$ as a sum of two random variables that are free with amalgamation over $B(\ell ^2(\mathbb {Z}_2))$ by applying the construction in Section 3.4 to the operators obtained above. Equivalently, this gives a way to construct the Cayley graph of $SL(2, \mathbb {Z})$ as an amalgamated free product of finite graphs.

Note that the above decompositions into pure tensors are very simple, and hence a construction of the Cayley graph via our graph product can be obtained using few colors. This simplicity is due to the abelian nature of the groups considered here. In general, the situation is more complicated, and as we will see below, more colors are needed.

5.3.1 General construction

We produce a family of colored graphs $\{(\mathcal {G}_i, c_i)\}_{i=1}^n$ and a relator graph $(\mathcal {G}, c)$ as follows:

1. (1) Vertices: Set $V(\mathcal {G})=H$ , and for every i, put $V(\mathcal {G}_i)=R_i$ .

2. (2) Roots: For every i, root $\mathcal {G}_i$ at $e_{G_i}$ .

3. (3) Color sets: For every i, we will choose

   $$ \begin{align*} \mathcal{C}_i =S_i\times H \times R_i/\sim, \end{align*} $$
   where $(s, h, r)\sim (s', h', r')$ if $(s, h, r) =(s', h', r')$ or if $s'=s^{-1}$ and $shr= h'r'$ .

4. (4) Edges: For every i and every $(h, h')\in H^2$ and $(r, r')\in R_i^2$ , put a directed edge in $\mathcal {G}$ from h to $h'$ , and in $\mathcal {G}_i$ from r and $r'$ , both of color $[(s, h, r)]$ , if $shr = h'r'$ .

Proposition 5.8 The graphs $\mathcal {G}$ and $\mathcal {G}_1, \dots , \mathcal {G}_n$ are undirected, the colorings of the edges are well defined, and the graphs $\Gamma (\ast _{H} \{G_i\}_{i=1}^n, S)$ and $\ast _{(\mathcal {G}, c)} \{\mathcal {G}_i\}_{i=1}^n$ are isomorphic.

Proof We begin by arguing that the color sets are well defined, and that all of the edges defined are in fact undirected (i.e., for any directed edge that appears in the construction, its reverse edge was also added and both have the same color). To do this, first we point out that the relation defined in (3) induces a pairing of the elements of $S_i\times H \times R_i$ . Indeed, by Theorem 5.6, for any $(s, h, r)$ , there are unique $h'\in H$ and $r'\in R_i$ such that $shr =h'r'$ , and hence each triple is related to exactly one other triple. Moreover, if $(s, h, r)\sim (s', h', r')$ for $(s', h', r')\neq (s, h, r)$ , then by definition we have that $shr =h'r'$ and $s'=s^{-1}$ , so we also have $hr = s'h'r'$ and hence $(s', h', r')\sim (s, h, r)$ , that is, $\sim $ is a symmetric relation. Because $\sim $ is symmetric and each triple is only related to one triple (other than itself), we can conclude that $\sim $ is an equivalence relation, and hence $\mathcal {C}_i$ is well defined. Moreover, because $\sim $ induces a pairing in $S_i\times H\times R_i$ , we are also guaranteed that for any directed edge of the form $(h, h')\in H^2$ (in $\mathcal {G}$ ) or of the form $(r, r')\in R_i^2$ (in $\mathcal {G}_i$ ), its inverse was also added, and both received the same color, so we can think of both of them as an undirected edge.

Now, we prove the isomorphism claim. First, note that, by the definition of $\ast _{(\mathcal {G}, c)} V(\mathcal {G}_i)$ and Theorem 5.6, there is a natural bijection $\phi : \ast _{(\mathcal {G}, c)} V(\mathcal {G}_i) \to \ast _{H} \{G_i\}_{i=1}^n$ given by

$$ \begin{align*} \phi(h, r_m \cdots r_1) = h r_m \cdots r_1. \end{align*} $$

It then just remains to show that $\phi $ preserves edge incidences. For this, suppose that $(h, r r_m \cdots r_1)$ and $(h', r'r_m \cdots r_1)$ are incident in the free amalgamated product of graphs (where r and $r'$ are allowed to be the empty word and m is allowed to be 0). Then, by definition, there is some i such that $ r, r' \in V(\mathcal {G}_i)=R_i$ , and there is an edge between r and $r'$ in $\mathcal {G}_i$ and between h and $h'$ in $\mathcal {G}$ . Moreover, the aforementioned edges have the same color, which in this case means that there exists some $s\in S_i$ such that $shr = h'r'$ , and therefore

$$ \begin{align*} s\cdot \phi(h, rr_m \cdots r_1) =shrr_m\cdots r_1=h'r'r_m \cdots r_1= \phi(h', r' r_m \cdots r_1). \end{align*} $$

That is, any pair of adjacent vertices in $\ast _{(\mathcal {G}, c)} \{\mathcal {G}_i\}_{i=1}^n$ gets sent to a pair of adjacent vertices in $\Gamma (\ast _H\{G_i\}_{i=1}^n, S)$ . The same argument can then be used to show that any pair of adjacent vertices in $\Gamma (\ast _H\{G_i\}_{i=1}^n, S)$ comes from a pair of adjacent vertices in $\ast _{(\mathcal {G}, c)} \{\mathcal {G}_i\}_{i=1}^n$ , so the proof is concluded.

5.4 Implications for $A_{\mathcal {T}(\mathcal {G})}$

Here, we revisit Example 5.1 in the context of Theorem 5.4. As in Example 5.1, we assume without loss of generality that every loop in $\mathcal {G}$ is a half-loop and furthermore that $V(\mathcal {G})= [n]$ . Let a and b be the edge weights and vertex potential of $\mathcal {G}$ , and let $\mathcal {T}$ be its universal cover.

Label the half-loops of $\mathcal {G}$ by $f_1, \dots , f_l$ and its nonloop undirected edges by $\{f_{l+1}, \check {f}_{l+1}\}, \dots , \{f_m, \check {f}_m\}$ . Then, define the discrete group $\Gamma _m := \mathbb {Z}_2 \ast \cdots \ast \mathbb {Z}_2$ and denote its canonical generators by $g_1, \dots , g_m$ . As usual, $\lambda $ will denote the left regular representation of $\Gamma _m$ on $\ell ^2(\Gamma _m)$ . We will now see that the following result follows easily from Theorem 5.4.

Proposition 5.9 Define $X_{\mathcal {G}}\in M_n(\mathbb {C})\otimes C_{\mathrm {red}}^*(\Gamma _m)$ by

$$ \begin{align*} X_{\mathcal{G}} & := \sum_{i=1}^n b_i \Delta_{ii} \otimes 1_{C_{\mathrm{red}}^*(\Gamma_m)}+ \sum_{i=1}^l a_{f_i} \Delta_{\sigma(f_i)\tau(f_i)}\otimes \lambda(g_i) \\ &\quad + \sum_{i=l+1}^m (a_{f_i} \Delta_{\sigma(f_i)\tau(f_i)}+ a_{\check{f}_i}\Delta_{\sigma(\check{f}_i)\tau(\check{f}_i)})\otimes \lambda(g_i) , \end{align*} $$

and let $E: M_n(\mathbb {C})\otimes C_{\mathrm {red}}^*(\Gamma _m) \to M_n(\mathbb {C})$ be the canonical conditional expectation (see (3.3)). Then:

1. (1) $E[X_{\mathcal {G}}^p]$ is a diagonal matrix for all $p\in \mathbb {Z}_{\geq 0}$ .

2. (2) For any $r\in [n]$ , let $\varphi _r: M_n(\mathbb {C})\to \mathbb {C}$ be defined by $\varphi _r(B):=B_{rr}$ for all $B\in M_n(\mathbb {C})$ . Then, the spectral distribution of $X_{\mathcal {G}}$ with respect to $\varphi _r\circ E$ is equal to $\mu _r$ , the spectral measure of $A_{\mathcal {T}}$ associated with r.

3. (3) The spectral distribution of $X_{\mathcal {G}}$ with respect to $\frac {1}{n} \mathrm {Tr} \circ E$ is equal to the density of states of $A_{\mathcal {T}}$ .

Proof Consider the construction in Example 5.1 and recall that for such a construction $\mathcal {T}_{\text {full}}= \ast _{(\mathcal {G}, c)} \{\mathcal {G}_i\}_{i=1}^m$ has n roots $(1, e), \dots , (n, e)$ and that the connected components $\mathcal {T}_1, \dots , \mathcal {T}_n$ of each are disjoint copies of $\mathcal {T}$ . Lift the edge weights and vertex potential of $\mathcal {G}$ to $\mathcal {T}_{\mathrm {full}}$ as in Definition 5.3. Then, apply Theorem 5.4 to obtain operators $D, T_1, \dots , T_m$ in an operator-valued probability space $(\mathcal {A}, E, M_n(\mathbb {C}))$ , so that $T_i$ distributes with respect to E as

$$ \begin{align*} a_{f_i}\Delta_{\sigma(f_i)\sigma(f_i)} \otimes \left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right)\in (M_n(\mathbb{C})\otimes M_2(\mathbb{C}), E_i, M_n(\mathbb{C})), \end{align*} $$

for $i=1, \dots , l$ (i.e., when $f_i$ is a half-loop), and it distributes as

$$ \begin{align*} a_{f_i} (\Delta_{\sigma(f_i)\tau(f_i)}+\Delta_{\tau(f_i)\sigma(f_i)} ) \otimes \left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right)\in (M_n(\mathbb{C})\otimes M_2(\mathbb{C}), E_i, M_n(\mathbb{C})), \end{align*} $$

for $i=l+1, \dots , m$ (i.e., when $\{f_i, \check {f}_i\}$ is an undirected nonloop edge), and D distributes with respect to E as $\text {diag}(b_1, \dots , b_n)\in (M_n(\mathbb {C}), \mathrm {Id}, M_n(\mathbb {C}))$ . Moreover, we know that $D, T_1, \dots , T_m$ are free with amalgamation with respect to E.

Now, decompose $X_{\mathcal {G}}$ by defining $X_{\mathcal {G}}^D := \sum _{i=1}^n b_i\Delta _{ii}\otimes 1_{C_{\mathrm {red}}^*(\Gamma _m)}$ and $X_{\mathcal {G}}^{(i)} := a_{f_i} \Delta _{\sigma (f_i)\sigma (f_i)}\otimes \lambda (g_i)$ , for $i=1, \dots , l$ , and $X_{\mathcal {G}}^{(i)} := a_{f_i}(\Delta _{\sigma (f_i)\tau (f_i)}+ \Delta _{\tau (f_i)\sigma (f_i)} ) \otimes \lambda (g_i)$ when $i=l+1, \dots , m$ . Now, from Observation 3.6, we know that the family $\{X_{\mathcal {G}}^D, X_{\mathcal {G}}^{(1)}, \dots , X_{\mathcal {G}}^{(m)} \}$ is free with amalgamation over $M_n(\mathbb {C})$ . Moreover, it is clear that D is equal in distribution (over $M_n(\mathbb {C})$ ) to $X_{\mathcal {G}}^D$ , and similarly each $T_i$ is equal in distribution to $X_{\mathcal {G}}^{(i)}$ .

Hence, $X_{\mathcal {G}}$ is equal in distribution over $M_n(\mathbb {C})$ to $T=D+T_1+\cdots +T_m$ . Then, (2) follows directly from Theorem 5.4(1). On the other hand, because $\frac {1}{n}\mathrm {Tr} = \frac {1}{n} \sum _{r\in [n]} \varphi _r$ , we get (3) from (2). Finally, to show (1), take $i\neq j$ and use that $E[T^p](i, j) = E[X_{\mathcal {G}}^p](i, j)$ combined with Theorem 5.4(1), to conclude that $E[X_{\mathcal {G}}^p](i, j)$ is equal to the sum of the weighted paths of length p in $\mathcal {T}_{\mathrm {full}}$ from $(i, e)$ to $(j, e)$ , but since these vertices are in distinct connected components, we can conclude that $E[X_{\mathcal {G}}^p](i, j)=0$ as we wanted to show.