1 Introduction
In the present work, by a graph, we mean a locally finite undirected graph allowing loops and multi-edges, unless otherwise specified. Given a graph $\mathcal {G}$ , we denote its vertex set by $V(\mathcal {G})$ and its edge set by $E(\mathcal {G})$ . Although we will only be considering undirected graphs, it will be convenient to view $E(\mathcal {G})$ as a set of directed edges, where each $f \in E(\mathcal {G})$ will have a source $\sigma (f)\in V(\mathcal {G})$ and a target $\tau (f)\in V(\mathcal {G})$ , and $E(\mathcal {G})$ will be equipped with the involution $\,\check {} : E(\mathcal {G})\to E(\mathcal {G})$ which to each edge f assigns its reversed edge $\check {f}$ . Given any vertex $u\in V(\mathcal {G})$ , it will prove useful to define the sets
Oftentimes, we will be working with graphs $\mathcal {G}$ that are endowed with edge weights and a vertex potential. Formally, the edge weights will be given by a function $a:E(\mathcal {G}) \to \mathbb {R}$ Footnote 1 that is symmetric in the sense that $a_f=a_{\check {f}}$ for all $f\in E(\mathcal {G})$ , and the vertex potential will be given by a function $b: V(\mathcal {G})\to \mathbb {R}$ .
The adjacency matrix, the graph Laplacian matrix, and transition matrices for symmetric random walks all fall under the umbrella of so-called Jacobi matrices on graphs [Reference Anderson and ZeitouniABS20]. These are bounded Hermitian operators associated with weighted graphs with vertex potential. More specifically, if $\mathcal {G}$ is a graph with edge weights a and vertex potential b, then the Jacobi matrix on $\mathcal {G}$ is the bounded operator $A_{\mathcal {G}}$ acting on $\mathcal {H}:= \ell ^2(V(\mathcal {G}))$ by
When working with Jacobi matrices on graphs (which will be the main focus of this paper), it is convenient to consider the spectral measures associated with the vertices of the graph. To be precise, given a vertex $u \in V(\mathcal {G})$ , one can define the state $\varphi _u: B(\mathcal {H}) \to \mathbb {C}$ as
where $\delta _u \in \ell ^2(V(\mathcal {G}))$ denotes the indicator function of the singleton $\{u\}$ . Then, since $A_{\mathcal {G}}$ is self-adjoint, its spectrum $\mathrm {Spec}(A_{\mathcal {G}})$ is contained in $\mathbb {R}$ , and by the functional calculus $\varphi _u$ induces a probability measure $\mu _{A_{\mathcal {G}}, u}$ supported on $\mathrm {Spec}(A_{\mathcal {G}})$ with the property that
for all $k \in \mathbb {Z}_{\geq 0}$ . Throughout this work, we refer to $\mu _{A_{\mathcal {G}}, u}$ as the spectral measure of $A_{\mathcal {G}}$ with respect to the root $u \in V(\mathcal {G})$ . In terms of functional analysis, $\mu _{A_{\mathcal {G}}, u}$ is the composition of the usual projection-valued spectral measure of $A_{\mathcal {G}}$ with $\varphi _u$ .
The spectra and spectral measures of operators on infinite graphs have been extensively studied in the last several decades in different contexts. However, despite significant progress in the area, current mathematical tools are still unable to answer simple fundamental questions.
Since our goal is to provide a new perspective on problems of current interest, the content of this paper is a combination of new results, new proofs of existing results, and new tools for the analysis of infinite graphs, all through the lens of free probability.
Our discussion includes the following families of graphs.
Cayley graphs
Let G be a finitely generated group, and let $S\subset G$ be a finite symmetric generating set; i.e., we assume that if $s \in S$ , then $s^{-1}\in S$ . We denote by $\Gamma = \Gamma (G, S)$ the left Cayley graph of G with respect to S. Note that since S is symmetric, $\Gamma $ is undirected, and by definition of $\Gamma $ , any symmetric weighting $a: S \to \mathbb {R}$ (i.e., $a(s)=a(s^{-1})$ ) induces a symmetric weighting on the edges of $\Gamma $ in the obvious way. Typically, in this context, vertex potentials are not considered; that is, one takes the constant function $b\equiv 0$ . The canonical measure associated with $A_{\Gamma }$ is the spectral measure of $\Gamma $ with respect to the identity $e\in G$ . Both $\mathrm {Spec}(A_{\Gamma })$ and $\mu _{\Gamma , e}$ have been studied thoroughly in the context of random walks on groups [Reference Cartwright and SoardiCS86, Reference Keller, Lenz and WarzelKes59, Reference McKayMcL88, Reference WoessWoe86, Reference WoessWoe87]. However, several basic spectral questions about some natural Cayley graphs remain open [Reference Keller, Lenz and WarzelKFSH19].
The amalgamated free product of groups inspired the notions of free independence and freeness with amalgamation [Reference VoiculescuVoi85], and since Voiculescu’s seminal work it became apparent that tools from free probability can provide important insights into the spectral theory of certain Cayley graphs. In this work, we focus on a new connection, namely the role of freeness with amalgamation in the study of universal covering graphs, which are not always Cayley graphs.
Universal covering graphs
Let $\mathcal {G}$ be a connected graph with n vertices. One can form its universal covering graph Footnote 2 (also called universal covering tree or universal cover), denoted here by $\mathcal {T}(\mathcal {G})$ , or simply by $\mathcal {T}$ when $\mathcal {G}$ is clear from the context. Recall that $\mathcal {T}$ is an infinite tree if $\mathcal {G}$ has at least one cycle or loop and is $\mathcal {G}$ itself when $\mathcal {G}$ is a tree. In this context, we will often refer to $\mathcal {G}$ as the base graph.
The universal covering graph comes with a covering map $\Xi : \mathcal {T}\to \mathcal {G}$ . So, when $\mathcal {G}$ is equipped with edge weights a and vertex potential b, one can use $\Xi $ in the obvious way to lift a and b to functions on $E(\mathcal {T})$ and $V(\mathcal {T})$ , respectively, and with this equip $\mathcal {T}$ with (periodic) edge weights and vertex potential. The corresponding Jacobi matrix $A_{\mathcal {T}}$ can then be viewed as a pullback of $A_{\mathcal {G}}$ , and it is referred to as a periodic Jacobi matrix with period n [Reference Anderson and ZeitouniABS20] or a pulled-back local operator [Reference Angel, Friedman and HooryAFH15].
It is standard to associate with $A_{\mathcal {T}}$ a set of spectral measures as follows. For any $u \in V(\mathcal {G})$ , we fix any representative $\tilde {u}\in V(\mathcal {T})$ in the fiber $\Xi ^{-1}(u)$ and consider the spectral measure $\mu _u:= \mu _{A_{\mathcal {T}}, \tilde {u}}$ . We can then associated the following canonical measure with $A_{\mathcal {T}}$ :
which is referred to as the density of states of $A_{\mathcal {T}}$ in accordance with the physics and spectral theory literature.
It is a well-known fact that $\mathcal {T}$ is the limit, in the Benjamini–Schramm sense, of random lifts of $\mathcal {G}$ (see Section 2.2). Hence, $A_{\mathcal {T}}$ can be regarded as a limit of random matrices. A bit of thought from the free probability perspective shows that in fact $A_{\mathcal {T}}$ can be viewed as an operator-valued matrix with free entries (see Section 4). This is the starting point of the present work.
Previous results give an explicit description of $\mathrm {Spec}(A_{\mathcal {T}})$ and $\mu _{A_{\mathcal {T}}}$ when $\mathcal {G}$ has a particular structure [Reference Friedman and KohlerFTS94, Reference Gouëzel and LalleyGM88, Reference Keller, Lenz and WarzelKes59, Reference Marcus, Spielman and SrivastavaMcK81]. Others have made some progress in the case when $\mathcal {G}$ is an arbitrary graph [Reference Accardi, Ghorbal and ObataA+88, Reference Anderson and ZeitouniABS20, Reference Arizmendi, Cébron, Speicher and YinAom91, Reference Speicher and WoroudiSS92, Reference SunadaSun92]. However, as we discuss in the last section, many fundamental questions remain open (also see [Reference Anderson and ZeitouniABS20]).
Amalgamated free product for graphs
As mentioned above, since generic universal covering graphs are not Cayley graphs, the emergence of freeness with amalgamation in this context might seem somewhat fortuitous. Here, we clarify this connection by introducing a graph product that corresponds to the notion of freeness with amalgamation.
Here is some context. Inspired by the combinatorial description of Cayley graphs of free products of groups, Quenell [Reference QuenellQue94] introduced the free product of graphs. Only later it was understood by Accardi, Lenczewski, and Sałapata [Reference AomotoALS07] that this graph product is equivalent to Voiculescu’s free product of Hilbert spaces [Reference VoiculescuVDN92] and that free probability can be used to compute the spectra of graphs arising from Quenell’s graph product. We refer the reader to Section 2.4 for a detailed and more precise discussion.
In the spirit of [Reference AomotoALS07, Reference QuenellQue94], in this paper, we define a combinatorial graph product and show that the machinery of freeness with amalgamation can be used to compute the spectra of graphs arising from this product. In particular, universal covering trees and Cayley graphs of amalgamated products of groups can be constructed using our product.
Bibliographic Note
After posting the first version of this article to the arXiv, we became aware of the work of Avni, Breuer, and Simon [Reference Anderson and ZeitouniABS20] posted 6 weeks prior. Upon reading their work, we have revised our article in a few ways. First, in place of our previous notion of “adjacency operators on weighted graphs,” we have adopted their terminology of Jacobi matrices on graphs, both to provide consistency in the literature and because it provides a useful distinction between diagonal elements $b_v$ and loops (which behave differently upon taking covers). Second, our theorem on the number of bands in the spectrum was demonstrated in [Reference Anderson and ZeitouniABS20] to be implicit in the work of Sunada [Reference SunadaSun92], which we had not realized. Both our independent proof and the proof given in [Reference Anderson and ZeitouniABS20] argue that the Jacobi operator of a universal cover can be viewed as a specific element of a matrix $C^*$ -algebra, and then use a standard K-theory argument which relies on a theorem of Pimsner and Voiculescu. However, these two proofs differ in the way in which the connection with the $C^*$ -algebra is made. The proof we present here uses random lifts and the fact that independent random permutation matrices are asymptotically free (an idea that has previously been exploited in [Reference Belinschi and BercoviciBC19] for different purposes), whereas the proof in [Reference Anderson and ZeitouniABS20] deals directly with the Jacobi operator on a concrete Hilbert space. Given the relevance of this result, we have decided to keep our alternative argument in this work, but we no longer state the result as ours. Finally, as we are able to answer some questions left open in [Reference Anderson and ZeitouniABS20], we include these answers in Appendix A of this revision.
To the best of our knowledge, other than what is mentioned in the above paragraph, there is no further overlap between our work and [Reference Anderson and ZeitouniABS20].
1.2 Results
1.2.1 Universal covers
In this section, we will consider a finite graph $\mathcal {G}$ with n vertices, universal cover $\mathcal {T}$ , and covering map $\Xi : \mathcal {T}\to \mathcal {G}$ . The base graph $\mathcal {G}$ will be equipped with edge weights a and vertex potential b, and $\mathcal {T}$ will be equipped with the induced periodic edge weights and vertex potential.
Roughly speaking, the proofs of the results in this section use free probability in two different ways.
-
(1) Free probability techniques are used to argue that periodic Jacobi matrices on $\mathcal {T}$ can be represented as $n\times n$ matrices with entries in a certain $C^*$ -algebra. For different applications, it is convenient to use different $C^*$ -algebras.
-
(2) Once a given periodic Jacobi matrix $A_{\mathcal {T}}$ is viewed as an element of a matrix $C^*$ -algebra, we argue that such an element can be decomposed as a sum of simpler operators that are free with amalgamation over the algebra $M_n(\mathbb {C})$ (see Section 3 for precise definitions). This decomposition allows the use of tools from free probability to understand the spectrum of $A_{\mathcal {T}}$ .
Regarding step (1), it is worth noting that once one has represented the Jacobi operator as an specific element of a matrix $C^*$ -algebra, one might be able to find elementary proofs that show that such a representation is correct. However, one should appreciate that it is not clear a priori that this connection with $C^*$ -algebras exists, and neither is it easy to “guess” what the correct representation of the Jacobi operator on a given $C^*$ -algebra is. It is for this reason that we decided to include the free probability arguments for step (1), since we believe that they provide a conceptual way to arrive at the $C^*$ -algebra representations.
Spectral radius
Let m be the number of undirected edges in $\mathcal {G}$ , and let $\Gamma _m$ be the discrete group obtained by taking the free product of m copies of $\mathbb {Z}_2$ . Using our combinatorial graph product, which is discussed in Section 1.5.2, we show that periodic Jacobi operators on $\mathcal {T}$ can be represented as elements in $M_n(\mathbb {C})\otimes C_{\mathrm {red}}^*(\Gamma _m)$ (see Section 3 for definitions). We then use a theorem of Lehner [Reference LehnerLeh99] to prove the following min-max formula for the spectral radius (actually, both spectral edges) of $A_{\mathcal {T}}$ .
Theorem 1.1 (Formula for the spectral radius)
Let $\mathcal {G}$ be a graph with vertex set $[n]$ , edge weights a, and vertex potential b. Let $\mathcal {T}$ be its universal cover with the induced periodic edge weights and vertex potential. If $\rho _r(A_{\mathcal {T}})$ denotes the right edge (i.e., maximum element) of $\mathrm {Spec}(A_{\mathcal {T}})$ , then
where $\deg (i)$ is the degree of the vertex i in $\mathcal {G}$ . Moreover, the infimum can be restricted to those n-tuples $(y_1, \dots , y_n)$ for which the n expressions inside the $\max $ symbol are equal to each other.
Remark 1.2 (Left edge and spectral radius)
Using the fact that $-A_{\mathcal {T}}$ is also a periodic Jacobi matrix on $\mathcal {T}$ , one may obtain a similar expression for the left edge $\rho _l$ of $\mathrm {Spec}(A_{\mathcal {T}})$ . Furthermore, to compute the spectral radius $\mathrm {spr}(A_{\mathcal {T}})$ , use the trivial observation $\mathrm {spr}(A_{\mathcal {T}}) = \max \{\rho _r, - \rho _l\}$ .
Remark 1.3 (The symmetric case)
In the case where $b_v = 0$ for all $v \in V(\mathcal {G})$ , the spectrum of $A_{\mathcal {T}}$ is symmetric about zero, because $\mathcal {T}$ is a bipartite graph. So, in this case, the spectral radius equals $\rho _r=\rho _l$ .
Aomoto’s equations
For $u \in V(\mathcal {G})$ , recall that $\mu _u$ denotes the spectral measure of $A_{\mathcal {T}}$ associated with a vertex in $\Xi ^{-1}[u]$ . We may then form the Cauchy transform of this measure:
The Cauchy transform is also known as the Stieltjes transform, and is closely related to the Green function or resolvent $(z - A_{\mathcal {T}})^{-1}$ , as well as to the walk generating function $Q_{u}(z) = \frac {1}{z} w_{u}(1/z)$ , which counts weighted closed walks on $\mathcal {T}$ based at a fixed $\tilde {u} \in \Xi $ . It is a standard fact in analysis that the spectral measure $\mu _{u}$ can be fully recovered from $w_u(z)$ via the Stieltjes inversion formula.
Using the operator-valued version of Voiculescu’s R-transform, we recover Aomoto’s system of equations for the $w_u(z)$ presented in Theorem 1.5.
Theorem 1.5 (Aomoto [Reference Accardi, Ghorbal and ObataA+88])
Using the above notation, the following system of equations holds:
for all $z \in \mathbb {C}$ in a neighborhood of infinity and for all real z outside the convex hull of the spectrum $\mathrm {Spec}(A_{\mathcal {T}})$ .Footnote 3
Remark 1.6 Since in Theorem 1.5 we are restricting z to be in a neighborhood of infinity and Cauchy transforms vanish at infinity, the expressions inside the radicals of (1.5) are always on the right side of the complex plane, and hence the square roots are globally defined. Moreover, by analyzing the behavior of the $w_u(z)$ at infinity, one sees that one should take the principal branch for each square root for the system of equations to hold.
The above system of equations was first discovered by Aomoto [Reference Accardi, Ghorbal and ObataA+88] using techniques from the literature of random walks on groups. See [Reference KestenKLW13, Sections 5 and 6], [Reference Kollár, Fitzpatrick, Sarnak and HouckKLW15, Section 4], and [Reference Anderson and ZeitouniABS20, Section 6] for a survey of similar results related to algebraicity of Cauchy transforms. In particular, see [Reference Anderson and ZeitouniABS20, Section 6] for a discussion of the role of algebraicity in showing that $A_{\mathcal {T}}$ has no singular continuous spectrum.
In [Reference Arizmendi, Cébron, Speicher and YinAom91], Aomoto used (1.5) to obtain necessary conditions on $\mathcal {G}$ for the existence of point spectrum in $\mathrm {Spec}(A_{\mathcal {T}})$ . Here, in Appendix B, we take a brief detour to show that (1.5) can be used to establish a connection between the behavior of the density of states at the right edge of $\mathrm {Spec}(A_{\mathcal {T}})$ and the growth rate of $\mathcal {T}$ . We prove the following.
Theorem 1.7 (Vanishing density at the right edge)
Use the above notation, and assume that $a_f>0$ for all $f \in E(\mathcal {G})$ . Let $\mu _{A_{\mathcal {T}}}$ be the density of states of $A_{\mathcal {T}}$ , and let $\rho _r$ be the right edge of $\mathrm {Spec}(A_{\mathcal {T}})$ . If $\mathcal {G}$ has at least two cycles, then $\mu _{A_{\mathcal {T}}}$ is absolutely continuous with respect to the Lebesgue measure in a neighborhood of $\rho _r$ and its density $s(x)$ satisfies $\lim _{x\to \rho _r} s(x) =0$ .Footnote 4
The behavior of $s(x)$ at the edge is tied to the type of singularity of the Cauchy transforms $w_u(z)$ at $z=\rho _r$ . On the other hand, the latter have been extensively studied for many classes of infinite graphs (e.g., [Reference Godsil and MoharGL13, Reference LalleyLal01, Reference Nica and SpeicherNW02, Reference WoessWoe00]), as an intermediate step to understand the asymptotic behavior of transition probabilities and escape rates of random walks. In particular, Theorem 1.7 can be deduced from the results in [Reference Nica and SpeicherNW02, Section 2], where the $w_u(z)$ are related to an auxiliary family of transforms, and sophisticated methods (that seek to prove stronger results) from the theory of random walks on infinite graphs are used. The argument in [Reference Nica and SpeicherNW02, Section 2] analyzes, as z varies, the evolution of the Perron eigenvalue of the nonbacktracking matrix of $\mathcal {G}$ Footnote 5 with entries weighted as a function of the auxiliary transforms. In contrast, our proof of Theorem 1.7 is short and self-contained, and uncovers a nice relation between Aomoto’s equations and the Perron eigenvalue of $A_{\mathcal {G}}$ .
Sunada’s theorem on the band structure
Let m be the number of undirected edges of $\mathcal {G}$ , and let $\mathbb {F}_m$ denote the free group on m generators. In [Reference Belinschi and BercoviciBC19], large random lifts of graphs were studied in the context of free probability. In Section 4, we recall from [Reference Belinschi and BercoviciBC19] how random lifts can be used to obtain a representation of $A_{\mathcal {T}}$ as elements in $M_n(\mathbb {C})\otimes C_{\mathrm {red}}^*(\mathbb {F}_m)$ . This representation can be combined with a theorem of Pimsner and Voiculescu [Reference Picardello and WoessPV82] to conclude the following result.
Theorem 1.8 (Sunada)
Using the notation above, the density of states of $A_{\mathcal {T}}$ assigns a positive integer multiple of $1/n$ to any connected component of the spectrum of $A_{\mathcal {T}}$ . Consequently, the spectrum of $A_{\mathcal {T}}$ contains at most n connected components.
Remark 1.9 (Tightness of the bound)
As mentioned above, if $\mathcal {G}$ is a tree, then $\mathcal {G} \cong \mathcal {T}$ , and hence if $\mathcal {G}$ has distinct eigenvalues (e.g., $\mathcal {G}$ is a path and $A_{\mathcal {G}}$ is its adjacency matrix), Sunada’s bound on the number of components is tight. A more interesting example of tightness is any finite graph with $\mathcal {G}$ with distinct $b_v$ and $\sum _{f \in E(\mathcal {G})} a_f < \min _{u \ne v} |b_u - b_v|$ (see [Reference Anderson and ZeitouniABS20, Section 10.2]).
Once the $C^*$ -algebra representation is obtained, the trick needed to reduce the proof of the above theorem to the theorem in [Reference Picardello and WoessPV82] is standard in K-theory and in the context of graph theory it was first used by Aomoto and Kato in [Reference AomotoAK88]. The upper bound on the number of bands of the spectrum of $A_{\mathcal {T}}$ is implicit in the work of Sunada [Reference SunadaSun92]. It was then highlighted and proved explicitly in [Reference Anderson and ZeitouniABS20]. This technique was also used in [Reference Keller, Lenz and WarzelKFSH19] to establish an upper bound on the number of bands for certain infinite lattices.
In relation to questions regarding the number of bands in the spectrum of $A_{\mathcal {T}}$ , in Appendix A, we discuss the phenomenon of spectral splitting and provide answers to several questions in [Reference Anderson and ZeitouniABS20] regarding possible extensions of theorems of Borg and Borg–Hochstadt.
1.2.2 Amalgamated graph products
Inspired by a series of results of different authors [Reference Accardi, Lenczewski and SałapataABGO04, Reference AomotoALS07, Reference O’Donnell and XinyuOba04] in which it is shown that each notion of noncommutative stochastic independence corresponds to a combinatorial graph product, we investigate the possibility of associating a graph product with the notion of freeness with amalgamation [Reference VoiculescuVDN92, Section 3.8]. Recall that freeness with amalgamation is not an independence in the sense of Muraki or Speicher [Reference MurakiMur02, Reference SpeicherSpe97], but it shares many desired properties with the five independences.
With this purpose in mind, we consider the following setting. Let $\mathcal {G}_1, \dots , \mathcal {G}_n$ be finite rooted graphs, and let $\mathcal {C}_1, \dots , \mathcal {C}_n$ be disjoint sets of colors. Assume that each $\mathcal {G}_i$ is equipped with an edge coloring $c_i: E(\mathcal {G}_i) \to \mathcal {C}_i$ . Let $\mathcal {C} = \bigcup _{i=1}^n \mathcal {C}_i$ , and let $\mathcal {G}$ be a finite graph with an edge coloring $c: E(\mathcal {G})\to \mathcal {C}$ .
In this work, we define a graph called the free product of $\mathcal {G}_1, \dots , \mathcal {G}_n$ with amalgamation over $\mathcal {G}$ . This product can be viewed as a procedure to construct an infinite graph by iteratively copying the local structure of the $\mathcal {G}_i$ and where the way in which these neighborhoods are combined is dictated by the structure of the graph $\mathcal {G}$ and by how the colorings $c_i$ relate to c.
Now, if $\mathcal {G}$ is a weighted graph with vertex potential, then these can be lifted in a natural (periodic) way to the graph $\mathcal {K}$ constructed through this procedure. The upshot here is that the Jacobi operator $A_{\mathcal {K}}$ can be written as an amalgamated free convolution of much simpler noncommutative random variables. Hence, in this situation, much of the machinery developed around freeness with amalgamation (e.g., [Reference Belinschi, Bercovici and LiuBBL19, Reference LehnerLeh99, Reference SpeicherSpe98, Reference Voiculescu, Dykema and NicaVoi95]) can be used to understand the spectral measures of $A_{\mathcal {K}}$ . It turns out that the amalgamated free product of graphs is general enough to be able to construct both:
-
(1) any Cayley graph of an amalgamated free product of groups, and
-
(2) any universal cover of a graph.
1.3 Structure of the paper
In Section 2, we discuss related work and motivate the study of the spectral properties of $A_{\mathcal {T}}$ . The latter has already been done impeccably by Avni, Breuer, and Simon in [Reference Anderson and ZeitouniABS20]. So, to minimize redundancy, we very briefly survey some of the important results mentioned in [Reference Anderson and ZeitouniABS20], and limit our detailed discussion to topics that were not touched upon in [Reference Anderson and ZeitouniABS20]: the relevance of $\mathrm {Spec}( A_{\mathcal {T}})$ in the theory of relative expanders, with a particular emphasis on the right and left edges of $\mathrm {Spec}( A_{\mathcal {T}})$ and the role of random lifts in this context. We also discuss the connections between noncommutative probability and spectral graph theory and spectral results about Cayley graphs in the context of free probability.
Section 3 contains all the machinery from the theory of free probability that will be needed in the present work, as it is our hope that this paper be of interest to multiple audiences. For example, the reader who is well-acquainted with free probability may skip Section 3, but might find Section 2 informative, whereas a reader coming from a background of spectral graph theory may want to skip Sections 2.1–2.3, review parts of Section 3, and proceed to the sections on the spectra of universal covers (Sections 4 and 6). The subsequent sections draw from different parts of Section 3 and are developed in a more or less parallel fashion. For this reason, the reader may jump straight to any of the sections that are of their interest and go back as needed.
In Section 4, we prove Theorem 1.8 using asymptotic freeness of random permutation matrices and an argument from operator K-theory. The knowledge from free probability required for this section is contained in Section 3.1.
In Section 5, we develop the theory behind our graph product, which we call the amalgamated free graph product. This discussion is based on the construction of Hilbert bimodules given in Section 3.4, and a good understanding of the content of Sections 3.1–3.3 is recommended.
In Section 6, we adopt an algebraic approach to the description of the spectral measure of $A_{\mathcal {T}}$ . The analysis of this section is based on interpreting $A_{\mathcal {T}}$ as an operator-valued matrix with free entries. This interpretation coincides with the framework used by Lehner in [Reference LehnerLeh99], and his results are used in the proofs of Theorems 1.1 and 1.5.
In Section 7, future directions are discussed.
1.3.1 Note for the free probability expert
Our contribution to the theory of free probability is the definition of the amalgamated free product of graphs presented in Section 5. The generality of this graph product has the potential to allow a free probability approach in contexts that go beyond what is discussed here.
In some sense, our construction provides a combinatorial interpretation of Voiculescu’s amalgamated free product for Hilbert bimodules when the underlying algebra is $M_n(\mathbb {C})$ . Moreover, our discussion from Section 5.3 has the nontrivial implication that for groups $G_1, G_2$ with a common finite subgroup H, operators in $C_{\text {red}}^*(G_1\ast _H G_2)$ that are free with amalgamation over $C_{\text {red}}^*(H)$ have explicit copies in distribution in an algebra of the form $M_n(\mathbb {C})\otimes B(\mathcal {H})$ where n is the order of H. This could facilitate numerical computations of amalgamated free convolutions.
Sections 4 and 6 on the other hand contain applications of well-understood tools in free probability. Their value resides in providing a new perspective to the independently interesting problem of understanding the spectral properties of $A_{\mathcal {T}}$ .
1.4 Definitions and conventions
Let us be precise about our notion of universal cover for graphs, which is not identical to the standard topological notion of universal covering space. For this, let $\mathcal {G}$ be a finite connected graph.
When it comes to loops in $\mathcal {G}$ (i.e., edges f for which $\sigma (f)=\tau (f)$ ), it will be useful to follow Friedman’s distinction between whole-loops and half-loops [Reference FriedmanFri93]. A whole-loop is a pair of distinct directed edges $f_1, f_2$ with $\check {f}_1 = f_2$ and $\sigma (f_1)=\tau (f_1)=\sigma (f_2)=\tau (f_2)$ , whereas a half-loop is composed of a single directed edge f satisfying $\check {f} =f$ and $\sigma (f)=\tau (f)$ . Whole-loop corresponds to the standard notion of loop used in graph theory. We will occasionally allow half-loops, for example, in the definition of universal cover below, but unless explicitly stated otherwise, in this work, graphs will not be permitted to have half-loops, and “loops” will refer exclusively to whole-loops.
A nonbacktracking walk in $\mathcal {G}$ is a sequence $f_1, \dots , f_m$ of edges in $E(\mathcal {G})$ such that $\tau (f_i)=\sigma (f_{i+1})$ and such that $f_{i+1}\neq \check {f}_i$ when $f_i$ is not a loop (i.e., $\sigma (f_i)\neq \tau (f_i)$ ), and $f_i\neq f_{i+1}$ when $f_i$ is a whole- or half-loop.
Definition 1.1 (Universal cover of a graph)
Let $\mathcal {G}$ be a finite undirected graph, possibly with half-loops, and fix a root $v_0 \in V(\mathcal {G})$ . The universal cover of $\mathcal {G}$ is the tree $\mathcal {T}(\mathcal {G})$ constructed as follows:
-
(1) We place one vertex in $\mathcal {T}(\mathcal {G})$ for every nonbacktracking walk in $\mathcal {G}$ starting at $v_0$ (this includes the empty walk).
-
(2) We connect two vertices in $\mathcal {T}(\mathcal {G})$ by an edge if the walk corresponding to one of them can be obtained by appending an edge to the walk corresponding to the other.
Example 1.10 (Bouquets)
Let $d \ge 0$ . The universal cover of a single vertex with d half-loops is the d-regular tree, which is a single vertex for $d=0$ , a single edge for $d = 1$ , and infinite otherwise. On the other hand, the universal cover of a single vertex with d whole-loops is the $2d$ -regular tree.
One may also define the notion of covering map for graphs (see, e.g., [Reference Figà-Talamanca and StegerFK19]), and one has that any connected cover of $\mathcal {G}$ is covered by $\mathcal {T}(\mathcal {G})$ .
2 Motivation and related work
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).
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.
Observation 2.1 For simplicity, let us consider only the adjacency operator (so $b_v = 0$ and $a_e = 1$ for all vertices v and edges e.) Table 1 shows that even if the base graphs are similar in some sense, the spectra of their universal cover may be quite different. In particular, we make the following remarks:
-
(1) (Topological equivalence) $\mathcal {G}_1$ and $\mathcal {G}_2$ are homeomorphic and, in particular, they have the same fundamental group. Yet, the spectra of the universal covers differ.
-
(2) (Eigenvalues of base graph) The graphs $\mathcal {G}_3$ and $\mathcal {G}_4$ are cospectral (i.e., their nonweighted adjacency matrices have the same multiset of eigenvalues); however, the spectra of their universal covers possess very different features.
-
(3) (Perturbations) $\mathcal {G}_3$ is obtained by adding a leaf to $\mathcal {G}_2$ . In this case, a gap in the spectrum around zero is created. From experiments, it seems adding leaves or edges can often cause major changes in the spectrum.
-
(4) (Degrees) Graphs $\mathcal {G}_5$ and $\mathcal {G}_6$ have the same degree sequence.
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) (Symmetry) $U_{\check {f}} = U_f^*$ .
-
(2) (Uniformly distributed) $U_f$ is a random matrix distributed uniformly in the space of $d\times d$ permutation matrices.
-
(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
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
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 6 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
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
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
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.
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 7
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:
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 Preliminaries on free probability
In this section, we describe the tools from the theory of free probability that will be used throughout this preprint. A basic background on $C^*$ -algebras is recommended, but not necessary for all of the following discussion. We refer the reader to [Reference DavidsonDav96] for an introduction to $C^*$ -algebras.
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.
Definition 3.1 (Noncommutative probability space)
A noncommutative probability space is a pair $(\mathcal {A}, \varphi )$ where $\mathcal {A}$ is a unital $\mathbb {C}$ -algebra and $\varphi : \mathcal {A} \to \mathbb {C}$ is a unital linear map.
In this work, the following examples of noncommutative probability spaces are of primary importance.
Example 3.1 The pair $\big (M_n(\mathbb {C}), \frac {1}{n} \mathrm {Tr}(\cdot ) \big )$ is a noncommutative probability space.
Example 3.2 Let G be a discrete group, and denote the reduced $C^*$ -algebra of G by $C_{\mathrm {red}}^*(G)$ .Footnote 8 Then, the $C^*$ -algebra $C_{\mathrm {red}}^*(G)$ has a canonical state given by
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.
Definition 3.2 (Free independence)
Let $(\mathcal {A},\varphi )$ be a noncommutative probability space, and let $\{\mathcal {A}_i\}_{i\in I}$ be a family of unital subalgebras of $\mathcal {A}$ . We say that the algebras $\mathcal {A}_i$ are freely independent (or just free) if $\varphi (a_1 \cdots a_m) =0$ whenever $a_i \in \mathcal {A}_{j_i}$ , $j_1\neq j_2\neq \cdots \neq j_m$ ,Footnote 9 and $\varphi (a_i)=0$ . Sets of random variables are said to be freely independent if the algebras they generate are free.
In the proof of Theorem 1.8, we will use the following.
Proposition 3.3 (Voiculescu)
Let $g_1, \dots , g_m $ be the m canonical generators of $\mathbb {F}_m$ ,Footnote 10 and let $\lambda $ be the left regular representation of $\mathbb {F}_m$ on $\ell ^2(\mathbb {F}_m)$ . Then, the random variables $\lambda (g_1), \dots , \lambda (g_m)$ are free in the noncommutative probability space $(C_{\mathrm {red}}^*(\mathbb {F}_m), \varphi )$ , where $\varphi $ is as in (3.1).
Note that in Proposition 3.3 the random variables $\lambda (g_i)$ are unitaries and satisfy that
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.
Definition 3.3 (Operator-valued probability space)
A triple $(\mathcal {A}, E, \mathcal {B})$ is called an operator-valued probability space if $\mathcal {A}$ is a unital algebra, $\mathcal {B} \subset \mathcal {A}$ is a subalgebra of $\mathcal {A}$ with $1_{\mathcal {A}}\in \mathcal {B}$ , and $E: \mathcal {A} \to \mathcal {B}$ is a conditional expectation, i.e., E is a linear map satisfying:
-
(1) $E \restriction _{\mathcal {B}} = \mathrm {Id}_{\mathcal {B}}$ , where $E \restriction _{\mathcal {B}}$ denotes the restriction of E to the subdomain $\mathcal {B} \subset \mathcal {A}$ .
-
(2) $E[b_1a b_2] = b_1 E[a] b_2$ for every $a \in \mathcal {A}$ and $b_1, b_2 \in \mathcal {B}$ .
Often, to emphasize the role of $\mathcal {B}$ , we will say that $(\mathcal {A}, E, \mathcal {B})$ is a $\mathcal {B}$ -valued 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
is an $M_n(\mathbb {C})$ -valued conditional expectation.
Example 3.5 (Group $C^*$ -algebras)
Let H be a subgroup of G, and denote by $\mathcal {B}$ the canonical copy of $C_{\mathrm {red}}^*(H)$ inside $C_{\mathrm {red}}^*(G)$ . Then, we can view $C_{\mathrm {red}}^*(G)$ as a $\mathcal {B}$ -valued probability space, by considering the canonical conditional expectation $E: C_{\mathrm {red}}^*(G) \to \mathcal {B}$ , namely the projection of $C_{\mathrm {red}}^*(G)$ onto $\mathcal {B}$ that is orthogonal with respect to the Gelfand-Naumark-Segal (GNS) inner product induced by the canonical tracial state on $C^*_{\mathrm {red}}(G)$ .
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.
Definition 3.4 (Freeness with amalgamation)
Consider an operator-valued probability space $(\mathcal {A}, E, \mathcal {B})$ . Let $\{\mathcal {A}_i\}_{i\in I}$ be a family of subalgebras of $\mathcal {A}$ such that $\mathcal {B}\subset \mathcal {A}_i$ for every $i\in I$ . We say that the algebras $\mathcal {A}_i$ are free with amalgamation over $\mathcal {B}$ if $E(a_1 \cdots a_m) =0$ whenever $a_i \in \mathcal {A}_{j_i}$ , $j_1\neq j_2\neq \cdots \neq j_m$ , and $E(a_i)=0$ .
Random variables in $\mathcal {A}$ are said to be free with amalgamation over $\mathcal {B}$ if the subalgebras generated by them are so.
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.
Observation 3.6 Let $(\mathcal {A}, \varphi )$ be a noncommutative probability space, and let $\mathcal {A}_1, \mathcal {A}_2 \subset \mathcal {A}$ be freely independent subalgebras. Let $X, Y \in M_n(\mathbb {C})\otimes \mathcal {A}$ with $X=(x_{ij})_{i,j=1}^n$ and $Y=(y_{ij})_{i,j=1}^n$ . If $x_{ij}\in \mathcal {A}_1$ and $y_{ij}\in \mathcal {A}_2$ for every $i, j=1, \dots , n$ , then X and Y are free with amalgamation over $M_n(\mathbb {C})$ with respect to the conditional expectation defined in (3.3).
The connection with the amalgamated free product of groups is the following.
Proposition 3.7 (Voiculescu)
Let $G_1, G_2$ be discrete groups with a common subgroup H. Let G be the group free product with amalgamation of $G_1, G_2$ over H, i.e., $ G := G_1 \ast _H G_2$ . Consider the inclusions $\rho _0 : C_{\mathrm {red}}^*(H) \to C_{\mathrm {red}}^*(G)$ and $\rho _i : C_{\mathrm {red}}^*(G_i)\to C_{\mathrm {red}}^*(G)$ for $i=1, 2$ . Now, as in Example 3.5, put $\mathcal {B} := \rho _0( C_{\mathrm {red}}^*(H))$ and view $C_{red}^*(G)$ as a $\mathcal {B}$ -valued probability space. Then, $\rho _1( C_{\mathrm {red}}^*(G_1))$ and $\rho _2( C_{\mathrm {red}}^*(G_2))$ are free with amalgamation over $\mathcal {B}$ .
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
is the adjacency operator of $\Gamma $ . Indeed, if G is identified with the vertices of $\Gamma $ , then for every $g\in G$ ,
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:
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
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
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
Next, for every $i \in I$ , we consider the subspace of $\mathcal {H}$
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
Finally, note that also $\xi \in \mathcal {H}$ defines a $\mathcal {B}$ -valued conditional expectation on $\widetilde {B}(\mathcal {H})$ given by
Theorem 3.10 (Voiculescu)
The above construction satisfies the following:
-
(1) For every $i \in I$ , $\lambda _i : \widetilde {B}(\mathcal {H}_i) \to \widetilde {B}(\mathcal {H})$ is an injective $\ast $ -algebra homomorphism.
-
(2) For every $i \in I$ and every $X \in \widetilde {B}(\mathcal {H}_i)$ it holds that $E(\lambda _i(X))=E_i(X)$ .
-
(3) The family of subalgebras $\left \{\lambda _i\big (\widetilde {B}(\mathcal {H}_i)\big )\right \}_{i\in I}$ of $\widetilde {B}(\mathcal {H})$ are free with amalgamation over $\mathcal {B}$ with respect to E.
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
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
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:
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
where $R_X$ and $R_Y$ are as in Definition 3.6.
4 Band structure of universal covers
In this section, $\mathcal {G}$ will be a graph with n vertices, edge weights a, and vertex potential b. Moreover, as above, $\mathcal {T}$ will denote its universal cover (with the inherited periodic weights and potential) and $A_{\mathcal {T}}$ will be the corresponding periodic Jacobi matrix on $\mathcal {T}$ .
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
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.
Theorem 4.1 (Nica [Reference Nagnibeda and WoessNic93])
Let $\{U_1^{(d)}, \dots , U_m^{(d)}\}$ be a family of independent random uniform $d\times d$ permutation matrices. Then, with respect to the state $\frac {1}{d} \mathbb {E} \circ \mathrm {Tr}(\cdot )$ , as d goes to infinity, the family $\{U_1^{(d)}, \dots , U_m^{(d)}\}$ converges in distribution to a family $\{u_1, \dots , u_m\}$ of free Haar unitaries.
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
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 11 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.
Proposition 4.3 Let m and n be positive integers, and let $\varphi $ be the canonical trace in $C_{\mathrm {red}}^*(\mathbb {F}_m)$ . Then, if $P \in M_n (\mathbb {C})\otimes C_{\mathrm {red}}^*(\mathbb {F}_m)$ is a projection, $(\mathrm {Tr}\otimes \varphi )(P)$ is a nonnegative integer.
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
So, by Proposition 4.3, the quantity above is $k/n$ for some integer $k \ge 1$ , as desired.
Remark 4.4 (Spectral splitting)
The $C^*$ -algebra representation of $A_{\mathcal {T}}$ given in (4.1) can also be used to answer other questions about the number of bands in $\mathrm {Spec}(A_{\mathcal {T}})$ . We refer the reader to Appendix A for a discussion of some problems about the number of bands in $\mathrm {Spec}(A_{\mathcal {T}})$ that were left open in [Reference Anderson and ZeitouniABS20].
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
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.
Theorem 4.5 (Nica [Reference Nagnibeda and WoessNic93])
Let $\{P_1^{(2d)}, \dots , P_{m_1}^{(2d)}, U_1^{(2d)}, \dots , U_{m_2}^{(2d)}\}$ be a family of independent random $d\times d$ permutation matrices, with the $P_i^{(2d)}$ distribute as uniform matchings and the $U_i^{(2d)}$ as uniform permutation matrices. Then, as d goes to infinity, this family converges in distribution (with respect to the state $\frac {1}{2d}\mathrm {Tr}(\cdot )$ ) to the free family $\{p_1, \dots , p_{m_1}, u_1, \dots , u_{m_2}\}$ , where the $p_i$ are Rademacher random variables and the $u_i$ are Haar unitaries.
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
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.
Proposition 4.6 (Analog of Sunada’s theorem)
If $\mathcal {G}$ contains half-loops, then the density of states of $A_{\mathcal {T}}$ assigns a positive integer multiple of $1/2n$ to any connected component of $\mathrm {Spec}(A_{\mathcal {T}})$ . Hence, $\mathrm {Spec}(A_{\mathcal {T}})$ has at most $2n$ components.
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.
Remark 4.7 (Avoiding asymptotic freeness)
Alternatively, using the amalgamated free product of graphs, in Section 5.4, we will show that $A_{\mathcal {T}}$ can be represented as an element in $M_n(\mathbb {C})\otimes C_{\mathrm {red}}^*(\Gamma _m)$ , from where Proposition 4.6 can be easily deduced from K-theory results as explained above.
5 The amalgamated free product for graphs
In Section 5.1, we give a combinatorial description of our graph product and show that it extends both the free product of graphs given in [Reference QuenellQue94] and the notion of universal cover of a graph. At the end of Section 5.1, we state Theorem 5.4, the main result of this section, which explains the connection with freeness with amalgamation and the use of having such a product.
In Section 5.2, we delve into the technicalities of the product, showing the connection between the combinatorial description given in Section 5.1 and the construction of the amalgamated free product of Hilbert modules described in Section 3.4.
To lighten notation, in the remaining of this section, for a graph $\mathcal {G}$ , we will write $\mathcal {G} = (\mathcal {V}, \mathcal {E}, e)$ to denote that $\mathcal {V}(\mathcal {G})=\mathcal {V}$ , $E(\mathcal {G})=\mathcal {E}$ , and e is the root of $\mathcal {G}$ .
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:
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:
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.
We now expand the notion of free product of graphs by introducing the concept of relator graph.
Definition 5.1 (Relator graph)
Let $\mathcal {C}$ be a finite set. A relator graph with colors in $\mathcal {C}$ is a finite graph $\mathcal {G}= (\mathcal {V}, \mathcal {E})$ together with an edge coloring $c: \mathcal {E} \to \mathcal {C}$ .
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.
Definition 5.2 (Amalgamated free product for graphs)
First, we describe the input data for the product:
-
• (Colored 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 finite rooted graphs. Assume that each $\mathcal {G}_i$ comes equipped with an edge coloring $c_i : \mathcal {E}_i\to \mathcal {C}_i$ such that $\mathcal {C}_i \cap \mathcal {C}_j = \emptyset $ for every $i\neq j$ .
-
• (Relator graph) Let $\mathcal {C} := \bigcup _{i=1}^n \mathcal {C}_i$ , and let $(\mathcal {G}, c)$ be a relator graph with colors in $\mathcal {C}$ and k vertices. Denote $\mathcal {G} = (\mathcal {V}, \mathcal {E})$ and without loss of generality set $\mathcal {V} = [k]$ .
Then, the free product of the $(\mathcal {G}_i, c_i)$ with amalgamation over $(\mathcal {G}, c)$ , which we denote by $*_{(\mathcal {G}, c)} \left \{(\mathcal {G}_i, c_i)\right \}_{i=1}^n$ , is the k-rooted graph defined as follows:
-
• (Vertex set) For the vertex set, we take k copies of the free product of the $\mathcal {V}_i$ , that is,
$$ \begin{align*} \ast_{(\mathcal{G}, c)} \{\mathcal{V}_i\}_{i=1}^n := [k] \times \ast \{\mathcal{V}_i\}_{i=1}^n. \end{align*} $$ -
• (Edge set) The colorings $c_i$ and c are used to know which edges should be added:
$$ \begin{align*} \ast_{(\mathcal{G}, c)} \{(\mathcal{E}_i, c_i)\}_{i=1}^n & := \left\{ \big( (l, vw), (l', v'w)\big) : (v, v')\in \mathcal{E}_j \text{ for some } \right.\\ & \left.\quad j \in [n], (l, l') \in \mathcal{E} \text{ and } c(l, l') = c_j(v, v') \right\}, \end{align*} $$where of course we are assuming that $w, vw, v'w\in \ast \{\mathcal {V}_i\}_{i=1}^n$ . -
• (Roots) The root set of $\mathcal {G}$ is $\{(l, e)\}_{l=1}^k$ .
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.
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
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.
Example 5.3 (Cayley graphs of amalgamated free products of groups)
In Section 5.3, we will show that if $G_1, \dots , G_n$ are finite groups with symmetric generating sets $S_1, \dots , S_n$ and a common subgroup H, then the left Cayley graph $\Gamma (\ast _H \{G_i\}_{i=1}^n, S)$ (where $S=\bigcup _{i=1}^nS_i$ ) can be constructed explicitly as an amalgamated free product of graphs. In our construction, H is taken to be the vertex set of the relator graph, and for every $i\in [n]$ , a set of representatives for the right cosets of H in $G_i$ is taken as the vertex set of the graph $\mathcal {G}_i$ . Then, the edges in $\mathcal {G}$ and $\mathcal {G}_i$ , and the colorings c and $c_i$ , encode the way in which the generators interact with the elements in H and the cosets of H in $G_i$ .
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:
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.
Definition 5.4 (Notation)
Fix $\mathcal {G}= (\mathcal {V}, \mathcal {E})$ a graph and $c: \mathcal {E} \to \mathcal {C}$ a coloring of the edges. For each $\alpha \in \mathcal {C}$ , we denote by $\mathcal {G}[\alpha ]$ the graph with the same vertex set as $\mathcal {G}$ , but that only includes those edges of color $\alpha $ , i.e., $\mathcal {G} = (\mathcal {V}, c^{-1}(\alpha ))$ . If $\mathcal {G}$ has edge weights and vertex potential, then $\mathcal {G}[\alpha ]$ inherits these in the obvious way.
We are now ready to state the main theorem.
Theorem 5.4 Use the notation in Definitions 5.2 and 5.4, and assume that the relator graph $\mathcal {G}$ is equipped with edge weights a and vertex potential b. Let J denote the Jacobi operator on $\ast _{(\mathcal {G}, c)} \{(\mathcal {G}_i, c_i)\}_{i=1}^n$ where the edge weights and vertex potential are defined as in Definition 5.3.
For every $i\in [n]$ and every $\alpha \in \mathcal {C}_i$ , let $X_{\alpha }$ and $A_{\alpha }$ be the weighted adjacency matrix of $\mathcal {G}[\alpha ]$ and the unweighted adjacency matrix of $\mathcal {G}_i[\alpha ]$ , respectively.Footnote 12 Then, there exists an operator-valued probability space $(\mathcal {A}, E, M_k(\mathbb {C}))$ , and random variables $D, T_1, \dots , T_n \in \mathcal {A}$ with the following properties:
-
(1) (Path counting) If $T:=D+T_1+\cdots +T_n$ , then for every natural number p and $i, j \in [k]$ , we have that
$$ \begin{align*} E[T^p](i, j) = J^p\big((e, i), (e, j)\big). \end{align*} $$ -
(2) (Freeness with amalgamation) The $T_i$ are free with amalgamation over $M_k(\mathbb {C})$ with respect to E. Moreover, D is free with amalgamation over $M_k(\mathbb {C})$ from any other element in $\mathcal {A}$ .
-
(3) (Equal in distribution) Fix $i \in [n]$ , let $m_i := |\mathcal {V}_i| $ , and note that $X_{\alpha } \otimes A_{\alpha } \in M_k(\mathbb {C})\otimes M_{m_i}(\mathbb {C})$ for every $\alpha \in \mathcal {C}_i$ . Then, if we view $ M_{m_i}(\mathbb {C})$ as a noncommutative probability space with the functional induced by the root of $\mathcal {G}_i$ , and from there construct the $M_k(\mathbb {C})$ -valued probability space $(M_k(\mathbb {C})\otimes M_{m_i}(\mathbb {C}), E_i, M_k(\mathbb {C}) )$ as in Example 3.4, we have that
$$ \begin{align*} \sum_{\alpha\in \mathcal{C}_i} X_{\alpha} \otimes A_{\alpha} \end{align*} $$distributes with respect to $E_i$ as $T_i$ with respect to E. Moreover, D distributes with respect to E as the matrix $\mathrm {diag}(b_1, \dots , b_k)$ distributes in the space $(M_k(\mathbb {C}), \mathrm {Id}, M_k(\mathbb {C}))$ .
Remark 5.5 (Scalar-valued distributions)
Note that item (1) in the above theorem tells us that the $k\times k$ matrices obtained as the operator-valued moments of T encode all of the information provided by walks between any two roots of the amalgamated free graph product. Hence, for every $i\in [k]$ , if one composes the conditional expectation E with the functional $\varphi _i: M_k(\mathbb {C})\to \mathbb {C}$ given by $\varphi _i(X) :=X(i, i)$ , then one can understand the spectral measure of the Jacobi matrix J on $\ast _{(\mathcal {G}, c)}\{(\mathcal {G}_i, c_i)\}$ associated with the root $(e, i)$ .
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
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
and note that this is a $\mathcal {B}$ -bimodule with the right and left actions of $\mathcal {B}$ on pure tensors given by
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
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
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
by letting each $X \otimes A \in \mathcal {B}\otimes _{\mathbb {C}} B(\ell ^2(\mathcal {V}_i))$ act on $\mathcal {H}_i$ by
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
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
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
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
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
and note that as $\mathcal {B}$ -bimodules we have the identification
for every $i_1\neq i_2 \neq \cdots \neq i_m$ . So we can view $\mathcal {H}$ as follows:
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
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
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
and consider the $\mathbb {C}$ -basis for $W_l$ given by
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
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,
and because of the construction of $\langle \cdot , \cdot \rangle $ , and since $C_l$ is a left ideal, it is easy to see that
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
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
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
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
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,
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
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
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)
and
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
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
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) Vertices: Set $V(\mathcal {G})=H$ , and for every i, put $V(\mathcal {G}_i)=R_i$ .
-
(2) Roots: For every i, root $\mathcal {G}_i$ at $e_{G_i}$ .
-
(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) 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
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
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
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) $E[X_{\mathcal {G}}^p]$ is a diagonal matrix for all $p\in \mathbb {Z}_{\geq 0}$ .
-
(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) 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
for $i=1, \dots , l$ (i.e., when $f_i$ is a half-loop), and it distributes as
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.
Remark 5.10 (Distinct $C^*$ -algebra representations)
Note that we have so far presented two essentially different methods to view $A_{\mathcal {G}}$ as an element of a $C^*$ -algebra. First, in Section 4, we used asymptotic freeness of random matrices to argue that $A_{\mathcal {T}}$ could be viewed as an element in $M_n(\mathbb {C})\otimes C_{\mathrm {red}}^*(\mathbb {F}_m)$ . Here, we have used the machinery from amalgamated graph products to show that $A_{\mathcal {T}}$ can be viewed as an element in $M_n(\mathbb {C})\otimes C_{\mathrm {red}}^*(\Gamma _m)$ . Although each representation and each proof are insightful in their own way, note that having access to distinct $C^*$ -algebras is also relevant in applications. The representation in $M_n(\mathbb {C})\otimes C_{\mathrm {red}}^*(\mathbb {F}_m)$ was exploited in Section 4.1 to prove Sunada’s theorem, where the K-theory of $C_{\mathrm {red}}^*(\mathbb {F}_m)$ (which is different from that of $C_{\mathrm {red}}^*(\Gamma _m)$ ) played a crucial role. On the other hand, in Section 6, we will use the representation in $M_n(\mathbb {C})\otimes C_{\mathrm {red}}^*(\Gamma _m)$ , which will allow us to apply verbatim some results of Lehner [Reference LehnerLeh99] about the norm and Cauchy transform of elements in this $C^*$ -algebra.
6 Universal covers: algebraic description of the spectrum
In this section, we give two applications of Proposition 5.9, where it was shown that $A_{\mathcal {T}}$ can be represented as an element in $M_n(\mathbb {C})\otimes C_{\mathrm {red}}^*(\Gamma _m)$ . An important ingredient for our proofs will be the work of Lehner [Reference LehnerLeh99], which has formulas for the operator-valued R-transform and norm of certain elements in $M_n(\mathbb {C})\otimes C_{\mathrm {red}}^*(\Gamma _m)$ . In what follows, we maintain the same setup and notation defined at the beginning of Section 5.4.
6.1 Aomoto’s equations via the R-transform
Here, we will recover Aomoto’s system of equations (i.e., Theorem 1.5) using free probability. We begin by noting that if we apply [Reference LehnerLeh99, Proposition 3.1], and specialize from positive definite matrices to diagonal positive definite matrices, we get the following result.
Proposition 6.1 (Lehner)
Let $W\in M_n(\mathbb {C})$ be a diagonal matrix with positive entries, and let $w_i := W_{ii}$ . Then, the $M_n(\mathbb {C})$ -valued R-transform of $X_{\mathcal {G}}$ at W, i.e., $R_{X_{\mathcal {G}}}(W)$ , is also diagonal, and the diagonal entries are given by
In order to use the above proposition, we will need the following observation, which is a corollary of Proposition 5.9.
Observation 6.2 Let $G_{X_{\mathcal {G}}}$ denote the $M_n(\mathbb {C})$ -valued Cauchy transform of $X_{\mathcal {G}}$ . Then, for $z \in \mathbb {C}$ in a neighborhood of infinity, $G_{X_{\mathcal {G}}}(zI_n)$ is diagonal.
Proof We will use the following power series expansion (in a neighborhood of infinity) for the Cauchy transform:
For $B= zI_n$ , the terms in the right-hand side of the above equation will be of the form $z^{-(p+1)} E\big [X_{\mathcal {G}}^p\big ]$ . Proposition 5.9(1) then implies that each term of the series expansion of $G_{X_{\mathcal {G}}}$ is a diagonal matrix, so the claim follows.
We can now show Theorem 1.5.
Proof As in the statement, for every $i\in [n]$ , let $w_i(z)$ be the Cauchy transform of $\mu _i$ , the spectral measure of $A_{\mathcal {T}}$ corresponding to i. Let $W(z) := G_{X_{\mathcal {G}}}(zI_n)$ , and note that, from Observation 6.2, we know that $W(z)$ is diagonal. Moreover, from Observation 3.11, we have that
Moreover, because they are Cauchy transforms, for any i, we have that $w_i(z)> 0$ for all sufficiently large real z. Using the definition of the R-transform in (3.5), we obtain
for all $1 \le i \le n$ . After substituting in the expression for $R_{X_{\mathcal {G}}}$ from Proposition 6.1 and simplifying, we get that the system of equations in the theorem statement holds for sufficiently large positive real z. Since $w_u(z)$ is holomorphic and $w_u(z) \to 0$ as $|z| \to \infty $ , both sides of the equations are holomorphic in a neighborhood of infinity, so by analytic continuation the system of equations holds in a neighborhood of infinity. Since $w_i(z) w_j(z)> 0$ for all $i,j$ when z is real and outside the convex hull of the spectrum $\mathrm {Spec}(A_{\mathcal {T}})$ , the system of equations holds for these z as well, as the singularity of the square root is always avoided.
Remark 6.3 (Half-loops are allowed)
Although (for exposition purposes) we stated Theorem 1.5 for graphs without half-loops, note that the above proof does allow half-loops, and the statement is left unchanged.
Remark 6.4 (Understanding the density of states)
In [Reference Arizmendi, Cébron, Speicher and YinAom91], Aomoto used this system of equations to prove results about the point spectrum of $A_{\mathcal {T}}$ (equivalently the atoms in the density of states). In Appendix B, we show that this system of equations can also be used to understand the behavior of the density of states at the edge of $\mathrm {Spec}(A_{\mathcal {T}})$ . Specifically, we prove Theorem 1.7 stated in the introduction.
6.2 Formula for the spectral radius
Let $\mathrm {spr}(A_{\mathcal {T}})$ denote the spectral radius of $A_{\mathcal {T}}$ , and let $\rho _r$ denote the right edge of $\mathrm {Spec}(A_{\mathcal {T}})$ . This subsection will be devoted to proving Theorem 1.1. We will build on [Reference LehnerLeh99, Theorem 1.1], and, as above, we will use $g_1, \dots , g_m$ to denote the canonical generators in $\Gamma _m$ .
Theorem 6.5 (Lehner)
Assume that $m \geq 2$ , and let $A_0, \dots , A_m$ be $n\times n$ Hermitian matrices, with $A_0$ positive semidefinite. Then,
where the infimum is taken over all positive definite invertible $n\times n$ matrices Z. Moreover, the infimum can be restricted to those Z for which the expression inside the norm sign equals a positive scalar multiple of the identity matrix $I_n$ .
We are now ready to prove Theorem 1.1. In short, the proof uses Aomoto’s equations (Theorem 1.5) to reduce the expression (6.1).
Proof For $i = 1, \dots , n$ , define $g_i(y_1, \dots , y_n)$ to be the expression inside the $\max $ symbol in the theorem statement, and let $w_i(z)$ denote the Cauchy transform of $\mu _i$ (the spectral measure of $A_{\mathcal {T}}$ associated with i). Fix $t> \rho _r(A_{\mathcal {T}})$ , and observe that $\infty>w_i(t)> 0$ , for every $i\in [n]$ . On the other hand, from Theorem 1.5, we have $t= g_i(w_1(t), \dots , w_n(t))$ for every i. Together, this implies that
Since the above inequality holds for any $t> \rho _r(A_{\mathcal {T}})$ , it holds for $t = \rho _r(A_{\mathcal {T}})$ . It remains to show the opposite inequality.
From Proposition 5.9, we have that $\mathrm {spr}(A_{\mathcal {T}}) = ||X_{\mathcal {G}}||$ . We would like to apply Theorem 6.5 on $X_{\mathcal {G}}$ , but the theorem requires $A_0$ to be positive semidefinite. To remedy this, take $\lambda \ge 0$ large enough so that $\lambda + b_i \ge 0$ for all i; we may now apply Theorem 6.5 on $X_{\mathcal {G}}+\lambda $ to obtain
where $D = \operatorname {diag}(b_1, \dots , b_n)$ , $A_i= \Delta _{\sigma (f_i)\sigma (f_i)}$ for $i=1, \dots , l$ , and $A_i = \Delta _{\sigma (f_i)\tau (f_i)}+ \Delta _{\tau (f_i)\sigma (f_i)} $ for $i=l+1, \dots , m$ . We will now see that in this case the infimum is achieved by diagonal matrices. Let $y_1, \dots , y_n>0$ and take $Y := \mathrm {diag}(1/2y_1, \dots , 1/2y_n)$ . Simple computations yield that upon setting $Z = Y$ in (6.2), the quantity inside the norm on the right-hand side becomes
Since $\lambda + g_i(y_1, \dots , y_n)\geq 0$ for all i, we have
Since $\rho _r(A_{\mathcal {T}}) + \lambda = \rho _r(A_{\mathcal {T}} + \lambda ) \le \mathrm {spr}(A_{\mathcal {T}} + \lambda )$ , we have
as desired.
Applying Lagrange multipliers to the optimization problem (1.3), using the constraint that all n expressions inside the $\max $ symbol are equal, we have the following corollary.
Corollary 6.6 With the above setup and notation, $t=\rho _r$ is the only real number such that, under the constraint $y_1, \dots , y_n>0$ , the following system of $2n+1$ equations in the variables $t, y_1, \dots , y_n, \lambda _1, \dots , \lambda _n \in \mathbb {R}$ has a solution:
where half-loops count once toward the count in $\mathrm {deg}(i)$ .
7 Future research
Since the first version of the present paper has been made public, some of the questions discussed in this section have been answered. Below, we discuss relevant recent work and highlight the questions that we still believe to be open and interesting.
7.1 Amalgamated free product for graphs
In the first version of this paper, we pointed out similarities and differences between our graph product and the additive graph product introduced by Mohanty and O’Donnell in [Reference McLaughlinMO20], and asked for a complete characterization of the graphs that could be constructed using each of these products. This has been answered in [Reference ObataOW20] by O’Donnell and Wu, where a new graph product was introduced (with the purpose of exploiting results in [Reference Belinschi and BercoviciBC19] to generate relative expanders), and was shown to generalize the amalgamated free product of graphs and the additive product. Moreover, the authors gave a full characterization of the graphs that could be obtained using their product.
On a different direction, we would like to recall questions about algebraicity and absence of singular continuous spectrum for general classes of graphs (such as the ones that can be obtained using the amalgamated graph product). For certain operators on different classes of infinite graphs, the respective Green functions (or other related functions) have been shown to be algebraic [Reference Anderson and ZeitouniABS20, Reference LalleyLal01, Reference KestenKLW13, Reference Nica and SpeicherNW02, Reference WoessWoe87]. On the other hand, algebraicity is relevant in the context of spectral theory since it provides means to show that the operators in question have no singular continuous spectrum [Reference Anderson and ZeitouniABS20] or in some cases that the spectrum is purely absolutely continuous [Reference KestenKLW13]. We believe that Jacobi operators on any graph defined via our product also have no singular continuous spectrum, and it is possible that the work of Anderson [Reference Aomoto and KatoAnd14] might lead to showing algebraicity of their Green functions. Proving this would provide a generalization of Theorem 6.7 in [Reference Anderson and ZeitouniABS20] and other results in the literature of spectral analysis of Cayley graphs. We state this as a conjecture.
Conjecture 7.1 (Algebraicity and absence of singular continuous spectrum)
The Cauchy transforms of the spectral measures of any Jacobi operator on a graph constructed via the amalgamated free product of graphs are algebraic, and the Jacobi operator has no singular continuous spectrum.
The above could also be relevant in relation to numerical computations. In particular, we point out that an operator-valued analog of [Reference Rao and EdelmanRE08] can lead to accurate numerical method for computing the spectral measures of any graph obtained via the amalgamated free product of graphs.
7.2 Universal covering graphs
In [Reference Anderson and ZeitouniABS20] and in previous versions of this paper, some questions about the point spectrum of $A_{\mathcal {T}}$ were asked. These questions were answered in [Reference Belinschi, Mai and SpeicherBGVM20], where a full characterization of the point spectrum of $A_{\mathcal {T}}$ was provided by analyzing the combinatorial structure of its eigenvectors. Later in [Reference AndersonACSY21], using free probability tools, a general theory about atoms of spectral measures of polynomials in noncommutative random variables was developed, and some of the results in [Reference Belinschi, Mai and SpeicherBGVM20] can be obtained directly from this general theory.
On a different direction, we bring to the attention of the reader that many of the questions about m-functions of $A_{\mathcal {T}}$ raised in [Reference Anderson and ZeitouniABS20] remain open (in particular, see [Reference Anderson and ZeitouniABS20, Section 10.1]). On the other hand, in the same way in which we deduced Aomoto’s systems of equations using the R-transform, we believe that results about the m-functions of $A_{\mathcal {T}}$ can be obtained via the theory of subordination in free probability [Reference Banks, Garza-Vargas and MukherjeeBB07, Reference Benjamini and SchrammBia98, Reference BianeBMS17, Reference VoiculescuVoi93]. Moreover, the subordination approach would yield numerical methods for computing the density of states of $A_{\mathcal {T}}$ via fixed point equations (see [Reference BianeBMS17, Reference Hall, Puder and SawinHMS18]).
Finally, we highlight that, despite recent activity in the area, simple questions about the number of bands in the spectrum of $A_{\mathcal {T}}$ seem to be out of reach of current tools. For example, we believe that the following toy problems are quite challenging.
Problem 7.2 Find a characterization of the base graphs $\mathcal {G}$ and coefficients $a_f, b_v$ for which $A_{\mathcal {T}}$ has connected spectrum.
Problem 7.3 Find an infinite sequence of Jacobi matrices $A_{\mathcal {G}_n}$ on graphs $\mathcal {G}_n$ (without half-loops) with $|V(\mathcal {G}_n)| \to \infty $ as $n \to \infty $ , and with $b_v^{(n)} = 0$ for every $v \in V(\mathcal {G}_n)$ , such that for every n, $\mathcal {G}_n$ has at least two cycles and the spectrum of $A_{\mathcal {T}(\mathcal {G}_n)}$ has $|V(\mathcal {G}_n)|$ bands.Footnote 13
A Spectral splitting
Theorem 1.8 provides an upper bound to the number of bands in the spectrum of the universal cover, and we have provided examples of when this bound is tight above. A natural further question is to determine what properties of a graph result in one band, two bands, and so on, as the number of bands has some relevance in physics (see [Reference Anderson and ZeitouniABS20]). In this section, we discuss some interesting examples yielding various numbers of bands.
One way to vary the number of bands in the spectrum of the universal cover is to fix the base graph $\mathcal {G}$ and vary the edge weights $a_f$ . For the specific case of regular trees, Figá-Talamanca and Steger [Reference Friedman and KohlerFTS94] gave an explicit description of this phenomenon. Here, to make it compatible with our context, the theorem below paraphrases Lemma 1.4 in Chapter 2 of [Reference Friedman and KohlerFTS94].
Theorem A.1 (Figá-Talamanca and Steger)
Let $\mathcal {G}$ be the graph with two vertices $u, v$ and d parallel edges $f_1, \dots , f_d$ connecting them. Assume that $a_{f_1} \geq \cdots \geq a_{f_d}> 0$ and $b_u=b_v =0$ . Then, zero is in the spectrum of $A_{\mathcal {T}(\mathcal {G})}$ if and only if
Let $\mathcal {G}$ be as in the above theorem. Note that, from Theorem 1.8, it follows that the spectrum of $A_{\mathcal {T}(\mathcal {G})}$ has at most two bands. Combining this with the fact that the spectrum is symmetric about zero (as $\mathcal {T}$ is bipartite), we have the following.
Observation A.2 Using the notation of Theorem A.1, $A_{\mathcal {T}(\mathcal {G})}$ has a connected spectrum if and only if inequality (A.1) is satisfied. Moreover, this remains true if we add a constant to $b_u$ and $b_v$ .
We pause to mention some examples. If $d=2k+1$ and the $a_{f_i}$ are chosen to be distinct and in such a way that (A.1) holds, we get a $(2k+1)$ -regular tree with nonconstant coefficients and connected spectrum. On the other hand, if $d =2k$ and the $a_{f_i}$ are chosen with the same characteristics as above, we get that $A_{\mathcal {T}(\mathcal {G})}$ has connected spectrum.Footnote 14
More can be said about the graph $\mathcal {G}$ from Theorem A.1.
Proposition A.3 Using the notation of Theorem A.1, if $b_u$ and $b_v$ are instead taken to be arbitrary distinct reals, then the spectrum of $A_{\mathcal {T}}$ has two bands.
Proof Applying Lemma 4.2, in particular, we obtain that the spectrum of $A_{\mathcal {T}}$ is the spectrum of an operator-valued matrix of the form
Since $b_1 \ne b_2$ by assumption, let us subtract a suitable multiple of the identity to obtain
for some real t; this merely translates the spectrum. Note that the spectrum of X is symmetric about zero, as $U X U^{-1} = -X$ for the unitary $U = \begin {pmatrix} 0 & -1 \\ 1 & 0 \end {pmatrix}$ .Footnote 15 Since $X^2 = \begin {pmatrix} y & 0 \\ 0 & y^* \end {pmatrix}$ , where $y = xx^* + t^2$ is invertible, 0 is not in the spectrum of X. Thus, the spectrum has a gap, as desired.
Now, we show that nonconstant-degree universal covers with similar characteristics can be constructed. To this end, we will now use $\mathcal {G}$ to denote the graph consisting of two vertices $u, v$ , with a loop $f_1$ on u and two parallel edges $f_2, f_3$ connecting u and v. Put $b_u=b_v =0$ and assume that $a_{f_i}>0$ .
As in the example of regular trees, since $\mathcal {G}$ has two vertices, we also have that the spectrum of $A_{\mathcal {T}(\mathcal {G})}$ is connected if and only if it contains zero. By Lemma 4.2, determining the invertibility of $A_{\mathcal {T}}$ is equivalent to deciding if the following operator-valued matrix is invertible:
where $g_1, g_2$ , and $g_3$ are the canonical generators of $\mathbb {F}_3$ .
We separate our analysis into two cases. First assume that $a_{f_2}\neq a_{f_3}$ . We can further assume without loss of generality that $a_{f_2}> a_{f_3}$ . Note that
From $a_{f_2}> a_{f_3}$ , we have $\|\frac {a_{f_3}}{a_{f_2}} \lambda (g_2^{-1} g_1)\| < 1$ , which implies that $1+ \frac {a_{f_3}}{a_{f_2}} \lambda (g_2^{-1} g_1)$ is invertible, and in view of (A.2), this implies that $a_{f_2}\lambda (g_2)+ a_{f_3}\lambda (g_3)$ is also invertible. Set $x := (a_{f_2}\lambda (g_2)+a_{f_3}\lambda (g_{3}))^{-1}$ and
It is easy to see that $X Y = I_2 \otimes 1$ and hence that zero is not in the spectrum of $A_{\mathcal {T}}$ when $a_{f_2}\neq a_{f_3}$ .
Now, assume that $a_{f_2}=a_{f_3}$ . In this case, one can show that $A_{\mathcal {T}}$ is not invertible. Indeed, let $x_n$ be the vector whose entries alternate between $1$ and $-1$ along n consecutive degree-two vertices on the y-axis of $\mathcal {T}$ as depicted in Figure 3. Then, $\Vert x_n \Vert = \sqrt {n}$ , whereas $\Vert A_{\mathcal {T}} x_n \Vert = \sqrt {2}$ , so $\{x_n\}$ is a sequence of approximate eigenvectors for zero. Alternatively, one can show that X is not invertible by noting that $X(1, 2)$ is a scalar multiple of $\lambda (g_2)+\lambda (g_3)$ , which is not invertible since its spectrum is $\{z \in \mathbb {C}: |z|\leq \sqrt {2}\}$ (see Example 5.5 in [Reference Haagerup and LarsenHL00]). This means that both $X(1, 2)$ and $X(2, 1)$ are not invertible, and hence X is not invertible.
This discussion can be summarized as follows.
Example A.4 Let $\mathcal {G}$ be the graph consisting of two vertices $u, v$ , with a loop $f_1$ on u and two parallel edges $f_2, f_3$ connecting u and v. Put $b_u=b_v =0$ and assume that $a_{f_i}>0$ for $i=1, 2, 3$ . Then, if $a_{f_1} = a_{f_2}$ , the spectrum of $A_{\mathcal {T}}$ is connected; otherwise, it has two bands.
This example disproves Conjecture 9.5 in [Reference Anderson and ZeitouniABS20], since it provides a graph $\mathcal {G}$ of nonconstant degree and specific coefficients for which $A_{\mathcal {T}}$ has a connected spectrum.
Finally, in [Reference Anderson and ZeitouniABS20], an interesting conjecture was made regarding the possibility of generalizing the Borg–Hochstadt theorem. Roughly speaking, in the language of our work, it was conjectured that for an arbitrary universal cover $\mathcal {T}$ , if the cumulative distribution function of the density of states of $A_{\mathcal {T}}$ is of the form $j/p$ inside every gap, then there exists a quotient of $\mathcal {T}$ , say $\mathcal {G}$ , such that $|V(\mathcal {G})|$ is a divisor of p.Footnote 16 In some sense, Example A.4 is already a counterexample of this conjecture, since in this case when $a_{f_1}=a_{f_2}$ there is only one band in the spectrum, while the smallest quotient of the universal cover has two vertices. However, it is still of interest to find an example with an interior spectral gap where the extension of the Borg–Hochstadt theorem does not hold. We do this below.Footnote 17
Let $m\geq 4$ , and let $g_1, \dots , g_m$ be the canonical generators of $\mathbb {F}_m$ . Take $x \in C_{\mathrm {red}}^*(\mathbb {F}_m)$ self-adjoint. If x is invertible, then
Now, consider a graph $\mathcal {G}$ with three vertices $u, v, w$ and edges $f_1, f_2$ connecting u with v, and v with w, respectively. Assume that $b_u=b_v=b_w=0$ . If we add whole-loops on the vertex u, then by Lemma 4.2 $A_{\mathcal {T}}$ will have the form of the first matrix in the left side of (A.3). Moreover, x will correspond to the loops on u and it can be made invertible by putting at least two loops on u and varying their Jacobi coefficients as shown in Example A.4. So, for the cases where x is invertible, zero will not be in the spectrum of $A_{\mathcal {T}}$ , but by Theorem 1.8 and since the density of states is symmetric about zero, this means that $A_{\mathcal {T}}$ has exactly two bands, each with mass $1/2$ . This provides an example of a universal cover whose smallest quotient has three vertices, and where the mass of the bands has the form $j/2$ .
B Behavior of the density of states at the right edge of the spectrum
Here, we use the same notation and setup as the one described at the beginning of Section 5.4.
Using Aomoto’s systems of equations for the Cauchy transforms, we may prove the following condition on when the spectral radii of a graph and its universal cover match.
Proposition B.1 Let $\mu $ and $\rho _r$ denote the density of states of $A_{\mathcal {T}}$ and maximum element of the spectrum of $A_{\mathcal {T}}$ , respectively. Then, the (possibly infinite) limit $\lim _{\epsilon \to 0^+} \frac {\mu ((\rho _r - \epsilon , \rho _r])}{\epsilon }$ exists. Moreover, if
then the maximum eigenvalue of $A_{\mathcal {G}}$ is equal to $\rho _r$ .
Proof Let $w(z)$ denote the Cauchy transform. We begin by noting that $w(z)$ is algebraic, since it is the average of the $w_u(z)$ (defined as in (1.4)), which were shown to be algebraic in [Reference Anderson and ZeitouniABS20]. On the other hand, this implies (by [Reference Avni, Breuer and SimonAZ08, Theorem 2.9]) that for some $\delta>0$ the measure $\mu $ is absolutely continuous with respect to the Lebesgue measure on $(\rho _r-\delta , \rho _r)$ and its density $s(x)$ is of beta type (i.e., there is a version of its Radon–Nikodym derivative, say $s(x)$ , which is continuous and has a power-like behavior at $\rho _r$ ).
There are now two cases. If $\mu $ has an atom at $\rho _r$ , then $\lim _{\epsilon \to 0^+} \frac {\mu ((\rho _r - \epsilon , \rho _r])}{\epsilon }=+\infty $ (showing that the limit exists), and it is easy to see that $\lim _{t\to \rho _r^+} w(t) = \infty $ . On the other hand, if $\mu $ has no atom at $\rho _r$ , the existence of the limit follows from the density of $\mu $ being continuous on $(\rho _r-\epsilon , \rho _r)$ , and moreover if in this case (B.1) holds, we have that there is some $C>0$ such that $s(x)>C$ for all x close enough to (the left of) $\rho _r$ . Hence, for any $\epsilon> 0$ ,
So taking $\epsilon \to 0^+$ , we get that even when there is no atom at $\rho _r$ , (B.1) implies that
Now, note that for any u, $w_u(t)$ is analytic, positive, and strictly decreasing for $t> \rho _r$ , so $\lim _{t \to \rho _r^+} w_u(t)$ exists and lies in $(0, \infty ]$ . Thus, for all $u, v \in V(\mathcal {G})$ , we have that $\lim _{t \to \rho _r^+} w_v(t) / w_u(t)$ exists and lies in $[0, \infty ]$ . In fact, we claim $\lim _{t \to \rho _r^+} w_v(t) / w_u(t) < \infty $ when u is a neighbor of v. If not, then setting $z = t$ in Theorem 1.5 and rearranging, we would have
and the right-hand side would diverge as $t \to \rho _r^+$ , whereas the left-hand side would converge, a contradiction.
Taking the reciprocal and switching the roles of u and v, we in fact obtain
whenever u and v are neighbors. By the connectedness of $\mathcal {G}$ , (B.4) actually holds for arbitrary vertices $u ,v$ . Together with (B.2), this implies $\lim _{t \to \rho _r^+} w_u(t) = \infty $ for all $u\in V(\mathcal {G})$ .
By (B.4), there exist positive real numbers $\{\widetilde {w}_u\}_{u\in V(\mathcal {G})}$ with the property
Taking the limit as $t \to \rho _r^+$ of (B.3), we get
Recalling the definition (1.1) of $A_{\mathcal {G}}$ , the above equation explicitly shows that $\rho _r$ is an eigenvalue of $A_{\mathcal {G}}$ with an eigenvector with positive entries $\left (\sqrt {\widetilde {w}_f}\right )_{f \in E(\mathcal {G})}$ . Now, take $\lambda> 0$ large enough so that $\lambda + b_u> 0$ for all $u \in V(\mathcal {G})$ . Then, the entries of $A_{\mathcal {G}} + \lambda $ are nonnegative, the eigenvector for $\rho _r + \lambda $ has positive entries, and $A_{\mathcal {G}}$ is irreducible (since as a directed graph $\mathcal {G}$ is strongly connected), so by the Perron–Frobenius theorem $\rho _r + \lambda $ is in fact the maximum eigenvalue of $A_{\mathcal {G}} + \lambda $ . Thus, $\rho _r$ is the maximum eigenvalue of $A_{\mathcal {G}}$ , as desired.
The following theorem of Sy and Sunada will be useful. We rephrase it in the language of Jacobi matrices on graphs. Their original formulation is in terms of what they call a discrete Schrodinger operator, but every graph Jacobi matrix with positive edge weights $a_f$ can be represented in their framework.
Theorem B.2 [Reference Speicher and WoroudiSS92]
Let $\mathcal {G}_1$ be a finite connected graph with no loops or multi-edges, and let $A_{\mathcal {G}_1}$ be a Jacobi matrix on $\mathcal {G}_1$ with $a_e> 0$ for all $e \in E(\mathcal {G}_1)$ . Let $\mathcal {G}_2$ be a graph covering $\mathcal {G}_1$ , and let $A_{\mathcal {G}_2}$ be the lift of $A_{\mathcal {G}_1}$ . Then, $\rho _r(A_{\mathcal {G}_1}) \ge \rho _r(A_{\mathcal {G}_2})$ with equality if and only if the deck transformation group of the covering is amenable, where $\rho _r(\cdot )$ denotes the right edge of the spectrum.
We may now prove our main result on the edge of the spectrum:
Restatement of Theorem 1.7 Let $A_{\mathcal {G}}$ be a Jacobi matrix on a finite graph $\mathcal {G}$ with at least two cycles, and let $A_{\mathcal {T}}$ be its pullback to the universal cover $\mathcal {T}(\mathcal {G}).$ Furthermore, assume that $a_f>0$ for all $f \in E(\mathcal {G})$ . Let $\mu $ and $\rho _r$ be the density of states and the maximum element of the spectrum of $A_{\mathcal {T}}$ , respectively. Then, $\mu _{A_{\mathcal {T}}}$ is absolutely continuous with respect to the Lebesgue measure in a neighborhood of $\rho _r$ and its density $s(x)$ satisfies $\lim _{x\to \rho _r} s(x) =0$ .
Proof Since $\mathcal {G}$ has at least two cycles, the deck transformation group of the universal cover contains the free group on two generators as a subgroup, and is therefore nonamenable. If $\mathcal {G}$ has no loops and no multi-edges, Theorem B.2 then implies that the maximum eigenvalue of $A_{\mathcal {G}}$ is strictly greater than $\rho _r$ . Thus, applying the contrapositive of Proposition B.1, we have
In particular, $\mu $ has no atoms in $(\rho _r - \epsilon , \rho _r]$ for $\epsilon $ sufficiently small. Furthermore, $\mu $ has no singular continuous part [Reference Anderson and ZeitouniABS20] due to algebraicity of the Cauchy transforms. Thus, the conclusion follows.
If, on the other hand, $\mathcal {G}$ has loops or multi-edges, we use the following work-around. One may first take a finite cover $\mathcal {G}'$ of $\mathcal {G}$ that does not contain loops or multi-edges. (If j is the maximum number of loops at any vertex and k is the maximum number of edges in any multi-edge, a cover with $\max \{2j+1, k\}$ sheets suffices.) Since $\mathcal {T}(\mathcal {G}) = \mathcal {T}(\mathcal {G}')$ , the only thing left to check is that $\rho _r(A_{\mathcal {G}}) \ge \rho _r(A_{\mathcal {G}'})$ , where $\rho _r(\cdot )$ denotes the maximum eigenvalue. This holds because the top eigenvector v of $A_{\mathcal {G}'}$ can be projected down to an eigenvector $v'$ of $A_{\mathcal {G}}$ for the same eigenvalue by summing the entries of v in each fiber. Note that $v'$ is nonzero because v has positive entries, by Perron–Frobenius applied to $A_{\mathcal {G}} + \lambda $ for $\lambda> 0$ sufficiently large (as the $b_u$ may be negative). Thus, $\rho _r(A_{\mathcal {G}}) \ge \rho _r(A_{\mathcal {G}'})$ , as desired.
Acknowledgment
We thank Nikhil Srivastava and Dan-Virgil Voiculescu for many helpful discussions and suggestions of research directions. We also thank Peter Sarnak for a very helpful and encouraging conversation we had at the Simons Institute. We also thank Barry Simon for his helpful feedback on a previous version of this paper, for pointing out key references and for helpful discussions. We are also grateful to Nalini Anantharaman, Octavio Arizmendi, Benson Au, Hari Bercovici, Shai Evra, and Sidhanth Mohanty for helpful discussions.