# On the density of eigenvalues on periodic graphs

Cosmas Kravaris

###### Abstract.

Using the Floquet-Bloch transform, we show that $\mathbb{Z}^{d}$-periodic
graphs have finitely many finite support eigenfunctions up to translations and
linear combinations and show that this can be used to calculate the density of
eigenvalues. We study the Kagome lattice to illustrate these techniques and
generalize the claims to amenable quasi-homogeneous graphs whose acting group
has Noetherian group algebra (this includes all virtually polycyclic groups).
Finally, we provide a formula for the von Neumann dimension of eigenvalues of
$\mathbb{Z}^{d}$-periodic graphs using syzygy modules.

##  1\. Introduction

On a a discrete graph $\Gamma=(V,E)$ with set of vertices $V$ and set of edges
$E$ which is locally finite (i.e. the degree of each vertex is finite) we may
consider the discrete Laplacian operator $\Delta$ which acts on the set of
complex valued functions $f$ on $V$ via the formula

$\Delta f(v):=\dfrac{1}{\sqrt{deg_{\Gamma}v}}\sum_{w\sim
v}\;(\dfrac{f(w)}{\sqrt{deg_{\Gamma}w}}-\dfrac{f(v)}{\sqrt{deg_{\Gamma}v}})$

where $w\sim v$ when they are connected by an edge and $deg_{\Gamma}w$ is the
degree of $w$. In the case where the graph is finite (so $|V|<\infty$)
$\Delta$ may be represented by an $|V|\times|V|$ matrix map whose domain is
the vectors of the form $(f(v))_{v\in V}$. The spectral theory of finite
graphs aims to study graph properties via the spectrum of this matrix, i.e.
the set of its eigenvalues. This theory has numerous applications in
theoretical computer science, network theory and spectral geometry. See [3]
for more details.

The story changes once we consider infinite locally finite graphs. Then the
operator $\Delta$ may be represented as an infinite matrix. In order to study
spectral properties, we need to restrict our attention to the Hilbert space
$l^{2}(V)$, making $\Delta$ a bounded self adjoint operator. Then we can apply
the classical theory of spectra of Hilbert space operators. Infinite locally
finite graphs and their spectral properties have connections to group theory,
the theory of random walks [23], visual processing (as was indicated by
A.Agrachev) and mathematical physics [2] [21].

It should be noted that there exist plenty of variations of this study. The
most obvious one is to consider the adjacency operator $A$, Markov operator
$M$ and Schrödinger operator $\Delta+q$ (where $q:V\rightarrow\mathbb{R}$ is
bounded) defined as

$Af(v):=\sum_{w\sim
v}f(w)\;\;\;\;\;\;\;\;Mf(v):=\dfrac{1}{deg_{\Gamma}v}\sum_{w\sim
v}f(w)\;\;\;\;\;\;\;\;(\Delta+q)f(v):=\Delta f(v)+q(v)$

Another variation is to account for multiple edges, or to use transition
probabilities. Furthermore, one may also consider quantum graphs [2] in which
edges are treated as unit intervals and analysis is performed on them.

The notion of the density of states originated in solid state physics [14]
where it is, roughly speaking, the number of states (eigenfunctions) per unit
volume whose energy (eigenvalue) lies in a given range. This notion is also of
interest in mathematics due to its relation to $l^{2}$-invariants in K-theory
and geometry and the von Neumann dimension [17] [7] as well as the study of
spectral measures of groups. The study of spectra, spectral measures and
density of states on infinite graphs is a large area of mathematics (see the
survey [18]).

Given an infinite finitely generated group $G$ with finite generated set $S$
one can construct the Cayley graph $\Gamma(G,S)$, which is an infinite regular
graph, and consider the Laplacian on it. Alternatively, one may also consider
the adjoint or the Markov operator or more generally a convolution operator on
$l^{2}(G)$ given by an element in the group algebra $\mathbb{C}G$. Information
about the group can be extracted from properties of these spectral measures;
for instance, Kesten’s Theorem asserts that $G$ is amenable if and only if the
spectral radius of the Markov operator is $1$. In [13], Kesten initiated the
study of random walks on groups and their spectral properties. He studied the
Markov operator on free groups and found their spectral measures, which are
all absolutely continuous.

The first example of a group with purely discrete spectrum was the lamplighter
group, $\mathbb{Z}_{2}\wr\mathbb{Z}$ [9]. It was studied by Grigorchuk and Zuk
in [9] by viewing $\mathbb{Z}_{2}\wr\mathbb{Z}$ as a group generated by a
2-state automaton. Later, Dicks and Schick [6] studied the spectra of
lamplighter groups using different methods and in a more general setting.
However, the spectral measure varies significantly on the generating set. In
[16], Grabowski and Virag found a generating set of the lamplighter group for
which its spectral measure is singular continuous (w.r.t. the Lebesgue
measure). In [7], Grigorchuk and Pittet showed that if a group $G$ is
indicable, that is, there is an epimorphism from $G$ to $\mathbb{Z}$ (this
applies to the lamplighter group), then there exists a generating set of $G$
such that the corresponding Cayley graph has no eigenvalues (and as a result
the spectral measure is continuous).

The study of spectral measures on groups is connected with various problems
from mathematical physics. In [21], Veselić studies spectral properties of
percolation Hamiltonians on amenable quasi-homogeneous graphs in connection
with the quantum percolation model. Finally, in [8], Grigorchuk and Simanek
find the spectral measures of a parameterized family of operators on the
lamplighter group (coming from the group algebra) and use that to study random
Schrödinger operators on the lamplighter group.

We begin with an introductory section on amenable quasi-homogeneous graphs.
Next, we focus on periodic graphs and review the Floquet-Bloch theory for
periodic graphs. We then provide an example, the Kagome lattice, to illustrate
the main ideas of the paper. We continue with a section on finite support
eigenfunctions and how to approximate (arbitrarily close) the density of
eigenvalues via the averaged density and Shubin’s formula. Next, we give a
short account of syzygy modules and free resolutions of polynomial ring
modules and use them to derive a formula for the density of an eigenvalue on a
periodic graph. Finally, we generalize the claims about finite support
eigenfunctions and Shubin’s formula to amenable quasi-homogeneous graphs whose
acting group has Noetherian group algebra and, in particular, to virtually
polycyclic groups.

## Acknowledgements

The author is grateful to Prof. Rostislav Grigorchuk for invaluable advice,
support and guidance and to Christophe Pittet for interest to this work and
valuable remarks.

##  2\. Amenable Quasi-Homogeneous Graphs

To begin with, suppose that $\Gamma=(V,E)$ is a discrete locally finite graph
with set of vertices $V$ and set of edges $E$. Consider the set of all complex
valued square summable functions on V

$l^{2}(V):=\\{f:V\rightarrow\mathbb{C}:\sum_{v\in V}|f(v)|^{2}<\infty\\}$

with the usual inner product $<f,g>:=\sum_{v\in V}f(v)\overline{g(v)}$.

On this graph, we define the discrete Laplacian $\Delta:l^{2}(V)\rightarrow
l^{2}(V)$ as

$\Delta f(v):=\dfrac{1}{\sqrt{d_{v}}}\sum_{w\sim
v}\;(\dfrac{f(w)}{\sqrt{d_{w}}}-\dfrac{f(v)}{\sqrt{d_{v}}})$

where $d_{v}:=deg_{\Gamma}v$. It is easy to see that $l^{2}(V)$ is a Hilbert
space and $\Delta$ defines a self adjoint operator on it. We may then talk
about the (continuous) spectrum of $\Delta$, $sp(\Delta)$, which is the set of
all $\lambda\in\mathbb{C}$ such that $(\Delta-\lambda I)$ does not have a
bounded inverse. Since $\Delta$ is self adjoint, $sp(\Delta)\subset$. We also
have the point spectrum, which is the set of all $\lambda\in\mathbb{C}$ for
which $(\Delta-\lambda I)$ is not injective. Since non-injective functions
cannot have an inverse function, the point spectrum lies inside the continuous
one. An element $\lambda$ of the point spectrum is called an eigenvalue. A
function $f\in l^{2}(V)$ such that $(\Delta-\lambda I)f=0$ is called an
eigenfunction of the eigenvalue $\lambda$ and the space of all such functions
is the eigenspace of $\lambda$.

Now suppose that $G$ is a finitely generated group with finite generating set
$S$. $G$ is amenable if and only if there exist a sequence $\\{F_{j}\\}_{j}$
of finite subsets of $G$ such that $|F_{j}\cdot S\setminus F_{j}|/|F_{j}|\to
0$ as $j\to\infty$. $\\{F_{j}\\}_{j}$ is called a Følner sequence for $(G,S)$.
Note that the amenability of G does not depend on the generating set $S$. A
quasi-homogeneous graph $G\curvearrowright\Gamma=(V,E)$ is a discrete locally
finite graph with a free action $G\curvearrowright V$ which preserves the
graph structure, so

$\forall g\in G,u,v\in V\;(u,v)\in E\implies(g\cdot u,g\cdot v)\in E$

and has finite orbit space i.e. $|V/G|<\infty$. Choosing a vertex from each
orbit of the group action, we obtain a fundamental domain $W\subset V$. When
the acting group $G$ is amenable, we call $\Gamma$ an amenable quasi-
homogeneous graph. When $G=\mathbb{Z}^{d}$ for some $d\in\mathbb{N}$, we call
$\Gamma$ a periodic graph.

The Koopman representation of a quasi-homogeneous graph
$\pi:G\rightarrow\mathcal{U}(l^{2}(V))$ is defined by

$\pi_{g}f(v):=f(g^{-1}\cdot v)\;\;\;v\in V,f\in l^{2}(V),g\in G$

It is a unitary representation of $G$ into the space of bounded unitary
operators on $l^{2}(V)$. Since $G\curvearrowright\Gamma$ preserves edges, it
follows that the discrete Laplacian and the Koopman representation commute:
$\pi_{g}\Delta f=\Delta\pi_{g}f,\;f\in l^{2}(V)$.

Next, we define some boundary operations on subsets of $V$. First, $\forall
v,w\in V$ denote by $d(v,w)$ the length of the shortest path in $\Gamma$ from
$v$ to $w$, taking value $\infty$ when no such path exists. The r-thick
boundary of a subset $F\subset G$ (where $r\in\mathbb{N}$) is defined to be:

$\partial_{r}F:=\\{v\in V\backslash F:\exists w\in F\;with\;d(v,w)\leq r\\}$

Note that $\\{F_{j}\\}_{j}$ is a Følner sequence for $(G,S)$ when
$|\partial_{1}F_{j}|/|F_{j}|\to 0$ on the Cayley graph $\Gamma(G,S)$ Another
important point is that if $f\in l^{2}(V)$ is an eigenfunction and there
exists $F\subset G$ with $f\equiv 0$ on $\partial_{2}F$, then $I_{F}f$ is also
an eigenfunction, where $I_{F}$ is the projection operator onto functions
supported on $F$, i.e. $I_{F}f(v)=f(v)$ when $v\in F$ and is $0$ otherwise.
The proofs of the above claims are straightforward and left as an exercise to
the reader. However, we will prove the following lemma:

######  Lemma 2.1 (Thick Følner sequences).

If $G\curvearrowright\Gamma$ is a quasi-homogeneous graph, then $\forall r$
there exists a sequence of finite subsets of $V$, $\\{F_{j}\\}$ such that
$|\partial_{r}F_{j}|/|F_{j}|\to 0$ as $j\to\infty$. Moreover, we can choose
this sequence so that $F_{j}=\mathcal{F}_{j}\cdot W$ where
$\mathcal{F}_{j}\subset G$ and $W$ is a fundamental domain We shall call this
sequence a standard r-thick Følner sequence w.r.t a fixed fundamental domain
$W$ and generating set $S$ of $G$.

###### Proof.

The case when $r=1$ and $\Gamma=\Gamma(G,S)$ follows by the definition of
amenability. Next, lets look at the case where $r>1$ and $\Gamma=\Gamma(G,S)$
. Consider the generating set $S^{\prime}:=S\cup S^{2}\cup...S^{r}$ where
$S^{r}:=\\{s_{1}^{\epsilon_{1}}...s_{r}^{\epsilon_{r}}:s_{1},...s_{r}\in
S,\;\epsilon_{1},...\epsilon_{r}\in\\{+1,-1\\}\\}$. Since $G$ is amenable,
there exists a 1-thick Følner sequence $\\{F_{j}\\}$ By construction, the
$1$-thick boundary of $F_{j}$ with respect to $\Gamma(G,S^{r})$ is precisely
the $r$-thick boundary of $F_{j}$ with respect to $\Gamma(G,S)$ therefore
$\\{F_{j}\\}$ is our desired Følner sequence.

Next, we have the general case. Fix a fundamental domain $W$ and a generating
set $S$ of $G$ Each element $w\in W$ is connected to finitely many vertices
$v\in V=\sqcup_{g\in G}g\cdot W$. So for each such $v$, $\exists!g_{v}\in
G,w_{v}\in W$ such that $v=g_{v}\cdot w_{v}$. Consider $|g_{v}|$, which is the
distance of $g$ from $1$ in the Cayley graph $\Gamma(G,S)$. Out of all $v\sim
w$ and all $w\in W$ pick the largest value of $|g_{v}|$ and call it $t$.
Inductively, it follows that if $u\in g_{u}\cdot W,\;\;v\in g_{v}\cdot W$ and
$d(u,v)\leq r$ then $|g_{u}g^{-1}_{v}|\leq rt$. By the previous case, we may
choose an $rt$ thick Følner sequence of $\Gamma(G,S)$, $\\{\mathcal{F}_{j}\\}$
and define $F_{j}:=\mathcal{F}_{j}\cdot W$. We have:

$\dfrac{|\partial_{r}F_{j}|}{|F_{j}|}\leq\dfrac{|(\partial_{rt}\mathcal{F}_{j})\cdot
W|}{|\mathcal{F}_{j}\cdot
W|}=\dfrac{|\partial_{rt}\mathcal{F}_{j}||W|}{|\mathcal{F}_{j}||W|}=\dfrac{|\partial_{rt}\mathcal{F}_{j}|}{|\mathcal{F}_{j}|}\to
0$

∎

We next discuss the concept of density. According to the spectral theorem of
self adjoint operators (see [19]), from $\Delta$ we obtain a spectral measure
$E$ whose input are Borel sets and outputs are projections on $l^{2}(V)$. In
the case where $B=\\{\lambda\\}$ where $\lambda$ is an eigenvalue,
$E(\\{\lambda\\})$ is the orthonormal projection onto the eigenspace of
$\lambda$. We will denote this eigenspace by $E_{\lambda}$. Fixing a
fundamental domain $W$ of $\Gamma$, the density or von Neumann trace of Borel
subset $B\subset sp(\Delta)$ is

$dk(B):=\dfrac{1}{|W|}tr(E(B)I_{W})$

where $tr$ is the usual trace of a Hilbert space operator and $I_{W}$is the
standard projection $l^{2}(V)\twoheadrightarrow l^{2}(W)$. Moreover, we may
commute the operators inside the trace: $tr(E(B)I_{W})=tr(I_{W}E(B))$ (see
[19]). From the spectral theorem, it follows that $dk(\cdot)$ is a measure on
$sp(\Delta)$. It is well known (for instance see [7]) that this measure is
purely continuous except a set of point masses which occur precisely at the
eigenvalues of $\Delta$. When $\lambda$ is an eigenvalue, $dk(\\{\lambda\\})$
is called the von Neumann dimension of the eigenspace $E_{\lambda}$ (see [7]
for further context) and when $\Gamma=\Gamma(G,S)$ is a Cayley graph,
$dk(B)=<E(B)\delta_{1},\delta_{1}>$ and is often called the spectral measure
of $(G,S)$.

Closer to the original idea of density is the concept of averaged density.
Suppose that $\lambda$ is an eigenvalue of $\Delta$ and $\\{F_{j}\\}$ is an
$j_{0}$-thick Følner sequence of $\Gamma$ for some $j_{0}\in\mathbb{N}$. The
averaged density of $\\{\lambda\\}$ is the limit

$lim_{j\to\infty}\dfrac{dim_{\mathbb{C}}\\{f\in E_{\lambda}:sprt(f)\subset
F_{j}\\}}{|F_{j}|}$

It is not entirely clear why this limit should converge and whether it is
equal to the von Neumann trace of $\\{\lambda\\}$. We show in Theorem 5.2 that
this is the case for sufficiently large thickness $j_{0}$ and conditions on
the finitely support eigenfunctions (which hold for all virtually polycyclic
groups acting groups in view of Theorem 7.1).

A similar approach to averaged density is Shubin’s formula The idea originated
in Shubin’s study of the spectral theory and index of elliptic operators with
periodic coefficients [22] and has connections with K-theory and solid state
physics [1]. Suppose that $B\subset sp(\Delta)$ is a Borel subset and take an
$j_{0}$-thick Følner sequence of $\Gamma$, $\\{F_{j}\\}$. For each $j$,
consider the subgraph of $\Gamma$ that contains the vertices
$F_{j}\cup\partial_{j_{0}}F_{j}$ and all edges connecting them so

$\Gamma_{j}:=(F_{j}\cup\partial_{j_{0}}F_{j}\;,\;E\cap(F_{j}\cup\partial_{j_{0}}F_{j})\times(F_{j}\cup\partial_{j_{0}}F_{j}))$

i.e. the subgraph induced by $F_{j}\cup\partial_{j_{0}}F_{j}$. $\Gamma_{j}$
has $|F_{j}\cup\partial_{j_{0}}F_{j}|$ many eigenvalues accounting with
multiplicity. Denote by $mult(\Gamma_{j},B)$ the dimension of the space of all
eigenfunctions of $\Gamma_{j}$ whose corresponding eigenvalue lies in $B$.
Shubin’s formula is:

$dk(B)=lim_{j\to\infty}\dfrac{mult(\Gamma_{j},B)}{|F_{j}|}$

In [20], Schumacher and Schwarzenberger showed that Shubin’s formula holds for
all $B$ which do not contain any eigenvalues provided the acting group $G$ is
sofic (in particular this holds for amenable groups). In section 5, we will
see that under conditions on the finite support eigenfunctions, the
amenability of the acting group and for sufficiently thick Følner sequences,
Shubin’s formula holds at all the eigenvalues. Combining these results,
Shubin’s formula must then hold on the entire spectrum.

The key idea we will need to study the density of eigenvalues will be to use
finite support eigenfunctions and reduce the problem to an algebraic one. In
order to do this we need to know two things: that finite support
eigenfunctions exist and that they can be used to approximate any $l^{2}$
eigenfunction. These two questions were studied for periodic graphs by
Kuchment in [15]. Later in [11], Higuchi and Nomura answered the first
question for amenable quasi-homogeneous graphs. Their argument was first found
in the work of Delyon and Souillard [5]. We quickly outline the proof of
Higuchi and Nomura [11] and then employ Delyon’s and Souillard’s argument to
prove the second claim. In the case of random percolation Hamiltonians (which
contains the discrete case too), both of these claims were proven by Veselić
in [21] using different methods involving log-Hölder continuity.

######  Theorem 2.2 (Strong Localization Property).

.
Let $\Gamma$ be a quasi-homogeneous graph with amenable acting group $G$ and
let $\Delta$ be the Laplacian operator on it. If $\lambda$ is an eigenvalue of
$\Delta$, then there exists an eigenfunction of $\lambda$ which has finite
support.

###### Proof.

Since $\lambda$ is an eigenvalue, $\exists f\in l^{2}(V)\setminus\\{0\\}$ such
that $\Delta f=\lambda f$. WLOG (without loss of generality) $||f||=1$. Fix a
fundamental domain $W$. Since $f\neq 0$ and translations of eigenfunctions are
still eigenfunctions, WLOG $f(w)\neq 0$ for some $w\in W$. Picking an
orthonormal basis $\\{\phi_{i}\\}_{i}$of $l^{2}(V)$ such that $\phi_{1}=f$ we
have:

$dk(\\{\lambda\\})=\dfrac{1}{|W|}tr(E(\\{\lambda\\})I_{W})\geq\dfrac{<I_{W}E(\\{\lambda\\})f,f>}{|W|}=\dfrac{<I_{W}f,f>}{|W|}=\sum_{w\in
W}|f(w)|^{2}>0$

Next, since the action of $G$ commutes with $\Delta$, $\forall g\in G$

$|W|dk(\\{\lambda\\})=tr(E(\\{\lambda\\})I_{W})=tr(E(\\{\lambda\\})\pi_{g^{-1}}\pi_{g}I_{W})=tr(E(\\{\lambda\\})I_{g\cdot
W})$

And hence for all finite subsets $\mathcal{F}$ of $G$,
$dk(\\{\lambda\\})=\dfrac{1}{|\mathcal{F}\cdot W|}tr(E(B)I_{\mathcal{F}\cdot
W})$.

Now, pick a standard 2-thick Følner sequence $\\{F_{j}\\}_{j}$. where
$F_{j}=\mathcal{F}_{j}\cdot W$ $\forall j$, pick an orthonormal basis
$\\{\phi_{1},...\phi_{m_{j}}\\}$ of
$I_{F_{j}\cup\partial_{2}F_{j}}E(\\{\lambda\\})l^{2}(V)$ and extend it to an
orthonormal basis $\\{\phi_{j}\\}_{j=1}^{\infty}$ of $l^{2}(V)$. We have:

$tr(I_{F_{j}\cup\partial_{2}F_{j}}E(\\{\lambda\\})=\sum_{i=1}^{m_{j}}<I_{F_{j}\cup\partial_{2}F_{j}}E(\\{\lambda\\})\phi_{i},\phi_{i}>+\sum_{i=m_{j}+1}^{\infty}<I_{F_{j}\cup\partial_{2}F_{j}}E(\\{\lambda\\})\phi_{i},\phi_{i}>$
$=\sum_{i=1}^{m_{j}}<I_{F_{j}\cup\partial_{2}F_{j}}\phi_{i},\phi_{i}>\;\leq
m_{j}$

Using the above estimate, we claim that $\exists j$ such that
$|\partial_{2}F_{j}|<m_{j}$. If not, that $|\partial_{2}F_{j}|\geq m_{j}$ for
all $j$ and hence

$0<dk(\\{\lambda\\})=\dfrac{1}{|F_{j}\cup\partial_{2}F_{j}|}tr(I_{F_{j}\cup\partial_{2}F_{j}}E(\\{\lambda\\})\leq\dfrac{m_{j}}{|F_{j}\cup\partial_{2}F_{j}|}\leq\dfrac{|\partial_{2}F_{j}|}{|F_{j}|}\to
0$

a contradiction. Picking $j$ such that $|\partial_{2}F_{j}|<m_{j}$, it follows
that
$\\{I_{\partial_{2}F_{j}}\phi_{1},...I_{\partial_{2}F_{j}}\phi_{m_{j}}\\}$ is
a linearly dependent set so we can find $a_{1},...a_{m_{j}}$ not all zero such
that

$h:=\sum_{i=1}^{m_{j}}a_{j}\phi_{i}\equiv 0\;\;on\;\partial_{2}F_{j}$

It then follows that $I_{F_{j}}h$ is an eigenfunction with finite support
inside $F_{j}$ which is nonzero due to the independence of the $\phi_{i}$ on
$F_{j}$. ∎

Denote by $D(\Gamma)$ all functions on the vertices $V$ of $\Gamma$ with
finite support and by $D_{\lambda}(\Gamma)$ all $\lambda$-eigenfunctions in
$D(\Gamma)$.

######  Theorem 2.3 (Finite Support Approximation of Eigenfunctions).

.
Let $G\curvearrowright\Gamma$ be an amenable quasi-homogeneous graph and let
$\Delta$ be the Laplacian operator on it with eigenvalue $\lambda$. If $f\in
l^{2}(V)$ is a $\lambda$-eigenfunction then for all $\epsilon>0$ arbitrarily
small, there exists $g\in D_{\lambda}(\Gamma)$ such that $||f-g||<\epsilon$,
i.e. the finite support eigenfunctions of $\lambda$ are $l^{2}$-dense in the
$l^{2}$-eigenspace of $\lambda$.

###### Proof.

Let $\mathcal{M}$ be the closure of $D(\Gamma)$ in $l^{2}(V)$ and
$E_{\lambda}$ be the $\lambda$-eigenspace. Suppose the contrary, i.e.
$\mathcal{M}\neq E_{\lambda}$. Then the orthogonal complement of $\mathcal{M}$
(w.r.t. the subspace $E_{\lambda}$) is not empty,
$\mathcal{N}:=\mathcal{M}^{\perp}\neq\emptyset$ Note that since $\forall g\in
G\;\;\pi_{g}D(\Gamma)=D(\Gamma)$,

$f\in\mathcal{N}\iff\forall h\in D(\Gamma)<f,h>=0\iff\forall h\in
D(\Gamma)<\pi_{g}f,\pi_{g}h>=0\iff<\pi_{g}f,h>=0$

Hence $\mathcal{N}$ is also invariant under translations.

Next, consider the orthogonal projection onto $\mathcal{N}$, $P_{\mathcal{N}}$
and fix a fundamental domain W. Define the ”density” of $\mathcal{N}$ as

$d:=\dfrac{1}{|W|}tr(I_{W}P_{\mathcal{N}})$

where the trace is take w.r.t. $l^{2}(V)$ Pick some $f\in\mathcal{N}$ with
$||f||=1$ and translated so that $f(w)\neq 0$ for some $w\in W$. Then by
extending $\\{f\\}$ to an orthonormal basis, we conclude that $d>0$. Since
$\mathcal{N}$ is invariant under translations, it also follows that
$d=\dfrac{1}{|\mathcal{F}\cdot W|}tr(I_{\mathcal{F}\cdot W}P_{\mathcal{N}})$
for every finite subset $F$ of $G$.

Choose a standard 2-thick Følner sequence $\\{F_{j}\\}_{j}$. where
$F_{j}=\mathcal{F}_{j}\cdot W$ $\forall j$, pick an orthonormal basis
$\\{\psi_{1},...\psi_{n_{j}}\\}$ of
$I_{F_{j}\cup\partial_{2}F_{j}}P_{\mathcal{N}}l^{2}(V)$ and extend it to an
orthonormal basis $\\{\psi_{j}\\}_{j=1}^{\infty}$ of $l^{2}(V)$. We conclude
that $tr(I_{F_{j}\cup\partial_{2}F_{j}}P_{\mathcal{N}})\leq n_{j}$. Similar to
before, if $\forall j$, $|\partial_{2}F_{j}|\geq n_{j}$, then
$0<d<\dfrac{|\partial_{2}F_{j}|}{|F_{j}|}\to 0$ This cannot happen, so there
is some $j$ such that $|\partial_{2}F_{j}|\leq n_{j}$. We can then find
$b_{1},....b_{j}$ not all zero such that

$g:=\sum_{i=1}^{n_{j}}b_{j}\psi_{i}\equiv 0\;\;on\;\partial_{2}F_{j}$

Then $I_{F_{j}}g\in D(\Gamma)$. Here comes the contradiction. Since $\forall
i=1...n_{j}$, $\psi_{i}\in
I_{F_{j}}P_{\mathcal{N}}l^{2}(V)=I_{F_{j}}\mathcal{N}$, there exists
$\bar{\psi_{i}}\in\mathcal{N}$ such that $I_{F_{j}}\bar{\psi_{i}}=\psi_{i}$ so
$\sum_{i=1}^{n_{j}}b_{j}\bar{\psi_{i}}\in\mathcal{N}$. On the other hand, the
$\psi_{i}$ are linearly independent over $F_{j}$, $g\neq 0$. We have:

$0=\;<g,\sum_{i=1}^{n_{j}}b_{j}\bar{\psi_{i}}>\;=\sum_{v\in
F_{j}}|g(v)|^{2}\neq 0$

This is a contradiction, therefore
$\mathcal{N}=\emptyset\implies\mathcal{M}=E_{\lambda}$ and the claim follows.
∎

##  3\. The Floquet-Bloch Transform

For this section, let $\mathbb{Z}^{d}\curvearrowright\Gamma=(V,E)$ be a
periodic graph. The Floquet-Bloch transform of $f\in l^{2}(V)$ is a complex
valued function with domain $V\times\mathbb{T}^{d}$ (where $\mathbb{T}^{d}$ is
the d dimensional torus)

$\hat{f}(v,e^{ik}):=\sum_{g\in\mathbb{Z}^{d}}f(g\cdot v)e^{-ik\cdot g}$

where $v\in V$, $k\in\mathbb{Z}^{d}$,
$e^{ik}=(e^{ik_{j}})_{j=1}^{d}\in\mathbb{T}^{d}$ and $k\cdot g$ is the
standard dot product.

One can verify that $\forall g\in\mathbb{Z}^{d},\hat{f}(g\cdot
v,e^{ik})=e^{ig}\hat{f}(v,e^{ik})$. This means that the entire function
$\hat{f}$ may be recovered from its restriction to $W\times\mathbb{T}^{d}$,
hence from now on we will view $\hat{f}$ as a function on this restricted
domain. The following key theorem is a consequence of standard techniques from
Fourier analysis. For a more detailed exposition see [2].

######  Theorem 3.1.

a) Inversion Formula: $\forall v\in W,g\in\mathbb{Z}^{d}$, $f(g\cdot
v)=\int_{[-\pi,\pi]^{d}}\hat{f}(v,e^{ik})e^{ik\cdot g}dk$
b) The map $f(u)\mapsto(2\pi)^{-n/2}\hat{f}(v,e^{ik})$ is a unitary map from
$l^{2}(V)$ to $L^{2}(\mathbb{T}^{d},\mathbb{C}^{|W|})$, the space of all
square summable functions from $\mathbb{T}^{d}$ to $\mathbb{C}^{|W|}$.

As a result of the above theorem, by composing $\Delta$ with the Floquet-Bloch
transform and its inverse, we may transform the discrete Laplacian
$\Delta:l^{2}(\Gamma)\rightarrow l^{2}(\Gamma)$ to a corresponding self
adjoint map $\hat{\Delta}:L^{2}(\mathbb{T}^{d},\mathbb{C}^{|W|})\rightarrow
L^{2}(\mathbb{T}^{d},\mathbb{C}^{|W|})$.

Let $v_{1}:=(\delta_{1,i})_{i=1}^{d},...v_{d}:=(\delta_{d,i})_{i=1}^{d}$ be
the standard basis of $\mathbb{Z}^{d}$ and write $z_{j}:=e^{iv_{j}}$. By
definition, the image of $f\in D(\Gamma)$ under the Floquet-Bloch transform is
a vector of size $n=|W|$ whose entries are Laurent polynomials in
$(z_{j})_{j}$ (that is, polynomials in $(z_{j})_{j}\cup(z_{j}^{-1})_{j}$). We
denote this ring of Laurant polynomials by $\mathbb{C}[z_{1}^{\pm
1},z_{2}^{\pm 1},...,z_{d}^{\pm 1}]$. The next two propositions allow us to
pass questions about finite support eigenfunctions to questions in commutative
algebra.

######  Proposition 3.2.

The map $\hat{\Delta}:L^{2}(\mathbb{T}^{d},\mathbb{C}^{|W|})\rightarrow
L^{2}(\mathbb{T}^{d},\mathbb{C}^{|W|})$ restricted to
$\bigoplus_{k=1}^{n}\mathbb{C}[z_{1}^{\pm 1},...,z_{d}^{\pm 1}]$ is an
$\mathbb{C}[z_{1}^{\pm 1},...,z_{d}^{\pm 1}]$-linear homomorphism from the
$\mathbb{C}[z_{1}^{\pm 1},...,z_{d}^{\pm 1}]$-module
$\bigoplus_{k=1}^{n}\mathbb{C}[z_{1}^{\pm 1},...,z_{d}^{\pm 1}]$ to itself.

###### Proof.

We first need some more notation. Write $W=\\{w_{1}...w_{n}\\}$ and let
$h_{i,j}^{1}...h_{i,j}^{m_{i,j}}\in\mathbb{Z}^{d}$ be such that

$\\{v\in V|v\sim w_{i}\\}=\\{h_{i,j}^{m}\cdot w_{j}|1\leq j\leq n,\;\;\;1\leq
m\leq m_{i,j}\\}$

Fixing $w_{i}\in W,k\in\mathbb{Z}^{d}$ we compute:

$\hat{\Delta}\hat{f}(w_{i},e^{ik})=(\Delta
f)\hat{~{}}(w_{i},e^{ik})=\sum_{h\in\mathbb{Z}^{d}}\Delta f(h\cdot
w_{i})e^{-ik\cdot h}$
$=\sum_{h\in\mathbb{Z}^{d}}\dfrac{1}{\sqrt{d_{w_{i}}}}\sum_{v\sim h\cdot
w_{i}}\;(\dfrac{f(v)}{\sqrt{d_{v}}}-\dfrac{f(h\cdot w_{i})}{\sqrt{d_{h\cdot
w_{i}}}})e^{-ik\cdot h}$
$=\sum_{h\in\mathbb{Z}^{d}}\dfrac{1}{\sqrt{d(w_{i})}}\sum_{j=1}^{n}\sum_{m=1}^{m_{i,j}}\;(\dfrac{f(h\cdot
h_{i,j}^{m}\cdot w_{j})}{\sqrt{d(h\cdot h_{i,j}^{m}\cdot
w_{j})}}-\dfrac{f(h\cdot w_{i})}{\sqrt{d(h\cdot w_{i})}})e^{-ik\cdot h}$
$=\dfrac{1}{\sqrt{d(w_{i})}}\sum_{j=1}^{n}\sum_{m=1}^{m_{i,j}}\;\left(\dfrac{1}{\sqrt{d(w_{j})}}\sum_{h\in\mathbb{Z}^{d}}f(h\cdot
h_{i,j}^{m}\cdot w_{j})e^{-ik\cdot
h}\;-\dfrac{1}{\sqrt{d(w_{i})}}\sum_{h\in\mathbb{Z}^{d}}f(h\cdot
w_{i})e^{-ik\cdot h}\;e^{-ik\cdot h}\right)$
$=\dfrac{1}{\sqrt{d_{w_{i}}}}\sum_{j=1}^{n}\sum_{m=1}^{m_{i,j}}\;(e^{ik\cdot
h_{i,j}^{m}}\dfrac{\hat{f}(w_{j},e^{ik})}{\sqrt{d_{w_{j}}}}-\dfrac{\hat{f}(w_{i},e^{ik})}{\sqrt{d_{w_{i}}}})$
$=\dfrac{1}{\sqrt{d_{w_{i}}}}\sum_{j=1}^{n}\left(\dfrac{1}{\sqrt{d_{w_{j}}}}\sum_{m=1}^{m_{i,j}}e^{ik\cdot
h_{i,j}^{m}}\right)\hat{f}(w_{j},e^{ik})\;\;-\;\dfrac{\hat{f}(w_{i},e^{ik})}{d_{w_{i}}}$
$=\dfrac{1}{\sqrt{d_{w_{i}}}}\sum_{j=1}^{n}\left(\dfrac{1}{\sqrt{d_{w_{j}}}}\sum_{m=1}^{m_{i,j}}z^{h_{i,j}^{m}}\right)\hat{f}(w_{j},e^{ik})\;\;-\;\dfrac{\hat{f}(w_{i},e^{ik})}{d_{w_{i}}}$

where $d()$ is the degree function and $z^{h_{i,j}^{m}}$ is just the multi
index notion for the monomial where $z_{k}$ is raised to the power of the
$k^{th}$ coordinate of $h_{i,j}^{m}$. The claim follows immediately from the
last expression. ∎

By the above proporition we may express $\hat{\Delta}$ as a $|W|\times|W|$
matrix whose entries are rational functions on
$\mathbb{T}^{d}\subset\mathbb{C}^{d}$ expressed via Laurant polynomials.
Classical perturbation analysis shows that $\lambda$ is an eigenvalue iff
$det(\hat{\Delta}-\lambda I)$ is the zero function on $\mathbb{T}^{d}$.
Moreover, $\lambda$ lies in the spectrum $sp(\Delta)$ iff
$det(\hat{\Delta}-\lambda I)$ has a zero. For more details see [2]. Moreover,
we have:

######  Proposition 3.3.

A periodic graph $\Gamma$ with Laplacian $\Delta$ has an eigenvalue $\lambda$
if and only if the map

$(\hat{\Delta}-\lambda I_{n}):\bigoplus_{k=1}^{n}\mathbb{C}[z_{1}^{\pm
1},...,z_{d}^{\pm 1}]\rightarrow\bigoplus_{k=1}^{n}\mathbb{C}[z_{1}^{\pm
1},...,z_{d}^{\pm 1}]$

is not injective and its kernel of this map corresponds to the finite support
eigenfunctions of $\lambda$.

###### Proof.

By the Strong Localization Property, every eigenvalue of $\Delta$ has a finite
support eigenfunction, therefore $\lambda$ is an eigenvalue of $\Delta$ $\iff$
$(\hat{\Delta}-\lambda I_{n}):\bigoplus_{k=1}^{n}\mathbb{C}[z_{1}^{\pm
1},...,z_{d}^{\pm 1}]\rightarrow\bigoplus_{k=1}^{n}\mathbb{C}[z_{1}^{\pm
1},...,z_{d}^{\pm 1}]$ is not injective. Any element in the kernel corresponds
(via the Floquet Bloch transform) to a function $f$ such that $(\Delta-\lambda
I)f=0$, i.e. an eigenfunction. It is clear that this eigenfunction must have
finite support and that the opposite direction also holds. ∎

In view of the formula $\hat{f}(g\cdot
v,e^{ik})=e^{ig}\hat{f}(v,e^{ik})=z_{1}^{g_{1}}...z_{d}^{g_{d}}\hat{f}(v,e^{ik})=z^{g}\hat{f}(v,e^{ik})$,
we see that when we multiply each component of $\hat{f}$ by the same monomial
$z^{g}\in\mathbb{C}[z_{1}^{\pm 1},...,z_{d}^{\pm 1}]$ we are essentially
translating $f$ by $g\in\mathbb{Z}^{d}$. It follows that when we multiply each
component of $\hat{f}$ by an arbitrary element of $\mathbb{C}[z_{1}^{\pm
1},...,z_{d}^{\pm 1}]$, then we are taking linear combinations of translations
of $\hat{f}$. Notice that $(\hat{\Delta}-\lambda
I_{n})\hat{f}=0\iff(\hat{\Delta}-\lambda I_{n})z^{g}\hat{f}=0$ hence
translations of eigenfunctions are still eigenfunctions w.r.t. the same
eigenvalue (alternatively one can just use the fact that
$\mathbb{Z}^{d}\curvearrowright\Gamma$ preserves edges). Therefore, if we wish
to describe all finite support eigenfunctions of $\lambda$, it suffices to
find them up to translations by $\mathbb{Z}^{d}$.

##  4\. An Example: The Kagome Lattice

In order to illustrate the main ideas of the paper, we study an important
example. We will find the eigenvalue (there is only one) of the Laplacian on
the Kagome lattice, then classify all its finite support eigenfunctions up to
translations and linear combinations and finally find the density of this
eigenvalue.

Consider the periodic graph shown below in Figure 1. It is called the Kagome
lattice or trihexagonal graph. It is a 4-regular periodic graph, has a group
action by $\mathbb{Z}^{2}$ which becomes multiplication by $z_{1}$ and $z_{2}$
under the Floquet-Bloch transform, and a fundamental domain
$W=\\{w_{1},w_{2},w_{3}\\}$ shown below. We summarize our result for this
example in following proposition:

Figure 1. The Kagome graph

######  Proposition 4.1.

The dicrete Laplacian on the trihexagonal graph or Kagome lattice has exactly
one eigenvalue $\lambda=-2/3$ with density $dk(\\{-2/3\\})=1/3$. Moreover,
every finite support eigenfunction is linear combination of translations of
the eigenfunction with Floquet Bloch transform

$(\;z_{1}-z_{2},\;1-z_{1},\;z_{2}-1\;)$

First, using the description of $\hat{\Delta}$ in the last section, we obtain:

$\hat{\Delta}=\dfrac{1}{4}\;\begin{pmatrix}-4&1+z_{2}&1+z_{1}\\\
1+z_{2}^{-1}&-4&1+z_{1}z_{2}^{-1}\\\
1+z_{1}^{-1}&1+z_{1}^{-1}z_{2}&-4\end{pmatrix}$

where the matrix is ordered based on the ordering $\\{w_{1},w_{2},w_{3}\\}$ of
the fundamental domain.

We next find the eigenvalues of $\Delta$. We have:

$det(\hat{\Delta}-\lambda
I_{3})=\dfrac{1}{4^{3}}((6+2\lambda)(z_{1}+z_{1}^{-1}+z_{2}+z_{2}^{-1}+z_{1}z_{2}^{-1}+z_{2}z_{1}^{-1})-36-168\lambda-192\lambda^{2}-64\lambda^{3})$

hence $det(\hat{\Delta}-\lambda I_{3})\equiv 0$ iff $\lambda=-2/3$.

Moving on, we find all finite support eigenfunctions of $\lambda$. Suppose
that $f^{\prime}=(f^{\prime}_{1},f^{\prime}_{2},f^{\prime}_{3})$ is the
Floquet Bloch transform of an eigenfunction with finite support, so
$f^{\prime}_{1},f^{\prime}_{2},f^{\prime}_{3}\in\mathbb{C}[z_{1}^{\pm
1},z_{2}^{\pm 1}]$. By multiplying $f^{\prime}$ by $(z_{1}z_{2})^{m}$ for
sufficiently large $m\in\mathbb{N}$ we may assume that
$(z_{1}z_{2})^{m}h\in\bigoplus_{k=1}^{3}\mathbb{C}[z_{1},z_{2}]$. As discussed
in the last section, $f=(f_{1},f_{2},f_{3}):=(z_{1},z_{2})^{m}f^{\prime}$
corresponds to the eigenfunction $f^{\prime}$ translated by $m$ units in the
vertical directions and $m$ units in the horizontal direction and is still an
eigenfunction. By Proposition 3.3, $f_{1},f_{2},f_{3}$ solve the following
system of equations:

$\dfrac{1}{4}\;\begin{pmatrix}2&1+z_{2}&1+z_{1}\\\
1+z_{2}^{-1}&2&1+z_{1}z_{2}^{-1}\\\
1+z_{1}^{-1}&1+z_{1}^{-1}z_{2}&2\end{pmatrix}\cdot\begin{pmatrix}f_{1}\\\
f_{2}\\\ f_{3}\end{pmatrix}=\begin{pmatrix}0\\\ 0\\\ 0\end{pmatrix}$
$\iff\begin{pmatrix}2z_{1}z_{2}&z_{1}z_{2}+z_{1}z_{2}^{2}&z_{1}z_{2}+z_{1}^{2}z_{2}\\\
z_{1}z_{2}+z_{1}&2z_{1}z_{2}&z_{1}z_{2}+z_{1}^{2}\\\
z_{1}z_{2}+z_{2}&z_{1}z_{2}+z_{2}^{2}&2z_{1}z_{2}\end{pmatrix}\cdot\begin{pmatrix}f_{1}\\\
f_{2}\\\ f_{3}\end{pmatrix}=\begin{pmatrix}0\\\ 0\\\ 0\end{pmatrix}$
$\iff\begin{pmatrix}z_{2}-1&0&-z_{1}+z_{2}\\\ 0&z_{2}-1&z_{1}-1\\\
0&0&0\end{pmatrix}\cdot\begin{pmatrix}f_{1}\\\ f_{2}\\\
f_{3}\end{pmatrix}=\begin{pmatrix}0\\\ 0\\\ 0\end{pmatrix}$
$\iff(z_{2}-1)f_{1}=(z_{1}-z_{2})f_{3}\;\;\;and\;\;\;(z_{2}-1)f_{2}=(1-z_{1})f_{3}$

It is well known that $\mathbb{C}[z_{1},z_{2}]$ is a Unique Factorization
Domain , hence its irreducible and prime elements coincide (see [12]). Since
$(z_{2}-1)$, $(z_{1}-z_{2})$ and$(z_{2}-1)$ are irreducible elements

$(z_{1}-z_{2})|(z_{2}-1)f_{1}\implies(z_{1}-z_{2})|f_{1}$

hence there is some $h\in\mathbb{C}[z_{1},z_{2}]$ such that
$f_{1}=(z_{1}-z_{2})h$. Plugging in this equation to our system we get

$(z_{2}-1)h=f_{3}\;\;\;and\;\;\;(z_{2}-1)f_{2}=(1-z_{1})f_{3}$ $\implies
f_{3}=(z_{2}-1)h\;\;\;and\;\;\;f_{2}=(1-z_{1})h$

Check that $(f_{1},f_{2},f_{3})$ is an eigenfunction $\forall
h\in\mathbb{C}[z_{1},z_{2}]$ (i.e. it solves the equation from Proposition
3.3.), so it follows that any finite support eigenfunction of $\Delta$ on the
Kagome lattice has Floquet-Bloch transform of the form

$(\;(z_{1}z_{2})^{-m}(z_{1}-z_{2})h,\;(z_{1}z_{2})^{-m}(1-z_{1})h,\;(z_{1}z_{2})^{-m}(z_{2}-1)h\;)\;\;\;\;h\in\mathbb{C}[z_{1},z_{2}],\;m\in\mathbb{N}$

Therefore all finite support eigenfunctions of $\lambda=-2/3$ are translations
and linear combinations of the single eigenfunction:

$(\;z_{1}-z_{2},\;1-z_{1},\;z_{2}-1\;)$

With the use of the inversion formula of the Floquet-Bloch transform (Theorem
3.1), Figure 2 displays this eigenfunction, placing numbers next to the
vertices in the support of this eigenfunction.

Figure 2. The unique eigenfunction up to translations and linear combinations

We conclude this section by finding the density of $\\{-2/3\\}$. For each
$g=(g_{1},g_{2})\in\mathbb{Z}^{2}$ let $|g|=max(|g_{1}|,|g_{2}|)$. Then the
sequence $F_{j}:=\cup_{|g|\leq j}g\cdot W$ is a Følner sequence of the graph
$\Gamma$. This sequence is $j_{0}$-thick for all $j_{0}\in\mathbb{N}$. An
enumerative argument shows that $|F_{j}|=3(2j+1)^{2}$. On the other hand, the
number of translated copies of our eigenfunction
$(\;z_{1}-z_{2},\;1-z_{1},\;1-z_{2}\;)$ which lie inside $F_{j}$ is
$(2j)^{2}$.

Figure 3. Finding the density of $\\{-2/3\\}$

All these eigenfunctions are linearly independent. For if there where any
$\mathbb{C}$-linear relation between these eigenfunctions, looking at the copy
with nonzero coefficient which is translated to the furthest domain $g$
(w.r.t. the length $|g|$) we must conclude that this coefficient is zero, a
contradiction. Therefore all these $(2j)^{2}$ eigenfunctions are linearly
independent. We conclude that the average dimension of the $\lambda=-2/3$
eigenspace is:

$lim_{j\to\infty}\;\;\dfrac{dim_{\mathbb{C}}\\{f\in
D_{\lambda}(\Gamma):sprt(f)\subset
F_{j}\\}}{|F_{j}|}=lim_{j\to\infty}\dfrac{(2j)^{2}}{3(2j+1)^{2}}=\dfrac{1}{3}$

By Theorem 5.2 (see below), $dk(\\{-2/3\\})=1/3$.

##  5\. The Finite Support Eigenfunctions and Averaged Density

Inspired by the above example, we have the following characterization of
finite support eigenfunctions on a periodic graph.

######  Theorem 5.1.

Let $\Gamma$ be a periodic graph with discrete Laplacian $\Delta$ on it and
let $\lambda$ be an eigenvalue of $\Delta$. Then $\lambda$ has finitely many
finite support eigenfunctions up to translation and linear combinations. That
is, there are $\lambda$-eigenfunctions $f^{(1)},...f^{(r)}$ such that every
$\lambda$-eigenfunction $f$ of finite support is the finite linear combination
of translations of $f^{(1)},...f^{(r)}$.

###### Proof.

Suppose that we had, a priori, a finite support eigenfunction $f\in
D_{\lambda}(\Gamma)$. Then we may translate it such that, WLOG, $f$ has
support in $\cup_{g\in\mathbb{N}^{d}}\;\text{-}g\cdot W$. This means that
$\hat{f}\in\mathbb{C}[z_{1},...,z_{d}]$. Next consider the entries of
$(\hat{\Delta}-\lambda I_{n})$ (which are elements of the ring
$\mathbb{C}[z_{1}^{\pm 1},...,z_{d}^{\pm 1}]$), look at all the integer powers
of $z_{1},...z_{d}$ in the terms of the entries and pick the smallest negative
power $-P$ (set $P=0$ if all the powers are non-negative). That way, the
entries of $(z_{1},...z_{d})^{P}(\hat{\Delta}-\lambda I_{n})$ all lie in
$\mathbb{C}[z_{1},...,z_{d}]$. We conclude that the set of all eigenfunctions
of $\lambda$ whose support is finite and lies in
$\cup_{g\in\mathbb{N}^{d}}\;\text{-}g\cdot W$ is the kernel of the
$\mathbb{C}[z_{1},...,z_{d}]$-linear map:

$(z_{1},...z_{d})^{P}(\hat{\Delta}-\lambda
I_{n}):\bigoplus_{k=1}^{n}\mathbb{C}[z_{1},...,z_{d}]\rightarrow\bigoplus_{k=1}^{n}\mathbb{C}[z_{1},...,z_{d}]$

By the classical Hilbert Basis Theorem, every ideal of
$\mathbb{C}[z_{1},...,z_{d}]$ is finitely generated, i.e.
$\mathbb{C}[z_{1},...,z_{d}]$ is Noetherian. Every finitely generated module
over a Noetherian ring is a Noetherian module ([12]). The kernel of
$(z_{1},...z_{d})^{P}(\hat{\Delta}-\lambda I_{n})$ is certainly a submodule of
the finitely generated $\mathbb{C}[z_{1},...,z_{d}]$-module
$\bigoplus_{k=1}^{n}\mathbb{C}[z_{1},...,z_{d}]$, so it is finitely generated,
say by generators $f^{(1)},...f^{(r)}$. But what does this mean? For every
eigenfunction with Floquet-Bloch transform $f$ there are
$g_{1},g_{2},...g_{r}\in\mathbb{C}[z_{1},...,z_{d}]$ such that
$f=g_{1}f^{(1)}+g_{2}f^{(2)}+...+g_{r}f^{(r)}$. Breaking down
$g_{1},g_{2},...g_{r}$ into linear combinations of monomials, and noting that
multiplication by $z^{g}$ corresponds to translation in $\Gamma$ by $g$, we
see that $f$ is the linear combination of translations of
$f^{(1)},...f^{(r)}$, and the claim follows. ∎

Next, we show that under a special condition, the averaged density of an
eigenvalue $\\{\lambda\\}$ is the same as the density of $\\{\lambda\\}$
defined via the von Neumann trace. From this equality, Shubin’s formula for
$\\{\lambda\\}$ will follow. This special condition is exactly the conclusion
of Theorem 5.1 and so it will hold for periodic graphs. In section 7 we will
see that this condition will also hold when the acting group is amenable with
Noetherian group algebra.

######  Theorem 5.2 (Averaged Density Formula).

Let $\Gamma$ be an amenable quasi-homogeneous graph with acting group $G$,
discrete Laplacian $\Delta$ and let $\lambda$ be an eigenvalue of $\Delta$. If
every element in $D_{\lambda}(\Gamma)$ is the linear combination of
translations (via the group action) of finitely many eigenfunctions
$f^{(1)},...f^{(r)}$ (in particular, if $\Gamma$ is periodic), then for any
fundamental domain $W$ and any generating set $S$ of $G$ there exists
$j_{0}\in\mathbb{N}$ such that a standard $j_{0}$ thick Følner sequence
$\\{F_{j}\\}$ of $\Gamma$ satisfies the following formula:

$dk(\\{\lambda\\})=lim_{j\to\infty}\dfrac{dim_{\mathbb{C}}\\{f\in
D_{\lambda}(\Gamma):sprt(f)\subset F_{j}\\}}{|F_{j}|}$

###### Proof.

Consider the supports of $f^{(1)},...f^{(r)}$ which are all finite, hence we
can find a finite $K\subset G$ such that
$\cup_{i=1}^{r}sprt(f^{(i)})\subset\cup_{g\in K}g\cdot W$ and let
$j_{0}:=max_{g\in K}|g|$. Take a standard $j_{0}$ thick Følner sequence
$\\{F_{j}\\}_{j}$. As we saw in section 2,
$dk(\\{\lambda\\})=\dfrac{1}{|F_{j}|}tr(E(\\{\lambda\\})I_{F_{j}})$ Define the
$\mathbb{C}$ vector spaces

$U_{j}:=Span\\{\pi_{g}f^{i}:g\in G,\;i=1...r\;sprt(\pi_{g}f^{i})\subset
F_{j}\\}$ $W_{j}:=Span\\{\pi_{g}f^{i}:g\in
G,\;i=1...r\;sprt(\pi_{g}f^{i})\subset F_{j}\cup\partial_{j_{0}}F_{j}\\}$

By Theorem 2.3, the (closed) subspace of $l^{2}(V)$ generated by
$\\{\pi_{g}f^{i}:g\in G,\;i=1...r\\}$ is precisely $E_{\lambda}$. Since
$\forall\pi_{g}f^{(i)}\in\\{\pi_{g}f^{(i)}:sprt(\pi_{g}f^{i})\not\subset
F_{j}\cup\partial_{j_{0}}F_{j},1\leq i\leq r\\}$ we get
$sprt(\pi_{g}f^{(i)})\cap F_{j}=\emptyset$ (by the very definition of
$j_{0}$), $<I_{F_{j}}\pi_{g}f^{(i)},\pi_{g}f^{(i)}>=0$ and we conclude that
$tr(E(\\{\lambda\\})I_{F_{j}})\leq dim_{\mathbb{C}}W_{j}$. On the other hand,
each element $\phi$ of an orthonormal basis for $U_{j}$ satisfies
$<I_{F_{j}}\phi,\phi>=||\phi||^{2}=1$. We end up with the estimate:

$dim_{\mathbb{C}}U_{j}\leq tr(E(\\{\lambda\\})I_{F_{j}})\leq
dim_{\mathbb{C}}W_{j}$

Next, we work on estimating $dim_{\mathbb{C}}\\{f\in
E_{\lambda}:sprt(f)\subset F_{j}\\}$. Obviously $U_{j}\subset\\{f\in
E_{\lambda}:sprt(f)\subset F_{j}\\}$. On the other hand, if $f\in E_{\lambda}$
with $sprt(f)\subset F_{j}\cup\partial_{j_{0}}F_{j}$, $f$ is the linear
combination of translations of $f^{(1)},...f^{(r)}$. The values of $f$ on
$F_{j}\cup\partial_{j_{0}}F_{j}$ depend only through the terms $\pi_{g}f^{i}$
whose support is not disjoint from $F_{j}\cup\partial_{j_{0}}F_{j}$. Each such
term should have support inside $F_{j}\cup\partial_{2j_{0}}F_{j}$, by the
construction of $j_{0}$. Hence there is a function $f^{\prime}\in W_{j}$ which
is equal to $f$ on $F_{j}\cup\partial_{j_{0}}F_{j}$. We get a map from
$\\{f\in E_{\lambda}:sprt(f)\subset F_{j}\\}$ to $W_{j}$ which is obviously
injective. We conclude that: $\forall j$

$dim_{\mathbb{C}}U_{j}\leq dim_{\mathbb{C}}\\{f\in E_{\lambda}:sprt(f)\subset
F_{j}\\}\leq dim_{\mathbb{C}}W_{j}$

Finally we ask: what is $q_{j}:=|\\{\pi_{g}f^{i}:g\in
G,\;i=1...r\;sprt(\pi_{g}f^{i})\not\subset
F_{j}\;but\;sprt(\pi_{g}f^{i})\subset F_{j}\cup\partial_{j_{0}}F_{j}\\}|$? We
get the obvious bound $q_{j}\leq|\partial_{j_{0}}\mathcal{F}_{j}|r$. Dividing
by $|F_{j}|$, we take the limit as $j\to\infty$:

$0\leq
lim_{j\to\infty}\dfrac{dim_{\mathbb{C}}U_{j}-dim_{\mathbb{C}}W_{j}}{|F_{j}|}\leq
lim_{j\to\infty}\dfrac{q_{j}}{|F_{j}|}\leq
lim_{j\to\infty}\dfrac{|\partial_{j_{0}}\mathcal{F_{j}}|r}{|F_{j}|}=0$

Therefore,
$dk(\\{\lambda\\})=lim_{j\to\infty}\dfrac{1}{|F_{j}|}tr(E(\\{\lambda\\})I_{F_{j}})=lim_{j\to\infty}\dfrac{dim_{\mathbb{C}}\\{f\in
D_{\lambda}(\Gamma):sprt(f)\subset F_{j}\\}}{|F_{j}|}$. ∎

######  Corollary 5.2.1 (Shubin’s Formula at Discontinuities).

Under the above assumptions let
$\Gamma_{j}:=(F_{j}\cup\partial_{j_{0}}F_{j},E\cap(F_{j}\cup\partial_{j_{0}}F_{j})\times(F_{j}\cup\partial_{j_{0}}F_{j}))$,
i.e. the subgraph induced by $F_{j}\cup\partial_{j_{0}}F_{j}$. Denote by
$mult(\Gamma_{j},\\{\lambda\\})$ the multiplicity of the eigenvalue $\lambda$
in $\Gamma_{j}$ Then

$dk(\\{\lambda\\})=lim_{j\to\infty}\dfrac{mult(\Gamma_{j},\\{\lambda\\})}{|F_{j}|}$

###### Proof.

WLOG take $j_{0}\geq 2$ We just have to compare
$mult(\Gamma_{j},\\{\lambda\\})$ with $dim_{\mathbb{C}}\\{f\in
D_{\lambda}(\Gamma):sprt(f)\subset F_{j}\\}$. If $h_{1},h_{2}$ are
$\lambda$-eigenfunctions of $\Gamma_{j}$ such that $h_{1}=h_{2}$ on
$\partial_{2}F_{j}$ then $h_{1}-h_{2}\in\\{f\in
D_{\lambda}(\Gamma):sprt(f)\subset F_{j}\\}$ by extending the function to be
zero outside $F_{j}$. This means that the $\lambda$\- eigenspace of
$\Gamma_{j}$ quotient the vector space $\\{f\in
D_{\lambda}(\Gamma),sprt(f)\subset F_{j}\\}$ has dimension at most
$|\partial_{2}F_{j}|$ therefore:

$lim_{j\to\infty}\dfrac{mult(\Gamma_{j},\\{\lambda\\})-dim_{\mathbb{C}}\\{f\in
D_{\lambda}(\Gamma):sprt(f)\subset F_{j}\\}}{|F_{j}|}\leq
lim_{j\to\infty}\dfrac{|\partial_{2}F_{j}|}{|F_{j}|}=0$

∎

######  Corollary 5.2.2 (Error of averaged density and Shubin’s formula).

Under the above assumptions and notation, we get the bounds $\forall j\geq
j_{0}$:

$|dk(\\{\lambda\\})-\dfrac{dim_{\mathbb{C}}\\{f\in
D_{\lambda}(\Gamma):sprt(f)\subset
F_{j}\\}}{|F_{j}|}|\leq\dfrac{|\partial_{j_{0}}F_{j}|}{|F_{j}|}$
$|dk(\\{\lambda\\})-\dfrac{mult(\Gamma_{j},\\{\lambda\\})}{|F_{j}|}|\leq\dfrac{2|\partial_{j_{0}}F_{j}|}{|F_{j}|}$

In view of the above Corollary, we can numerically approximate
$dk(\\{\lambda\\})$, and the rate of convergence is as fast as that of our
Følner sequence. Moreover, the constant $j_{0}$ may be computed so long as we
can find some eigenfunctions $f^{(1)},...f^{(r)}$ that generate all finite
support eigenfunctions. Still, in the case of periodic graphs we can do even
better; we can get an exact formula for $dk(\\{\lambda\\})$ using some basic
commutative algebra. This is done in the next section.

##  6\. Formula for the Density of Eigenvalues on Periodic Graphs

Throughout this section, $\Gamma$ is a periodic graph with Laplacian $\Delta$
having an eigenvalue $\lambda$. For brevity, we write
$K:=kernel((z_{1},...z_{d})^{P}(\hat{\Delta}-\lambda I_{n}))$ and
$R:=\mathbb{C}[z_{1},....z_{d}]$. Our goal is to find von Neumann dimension of
$E_{\lambda}$ (i.e. the density of $\lambda$) using the $R$-module $K$. In
this general case, there is a small difference with the Kagome lattice; we may
not have only one eigenfunction up to translations and linear combinations. As
a result when we translate our eigenfunctions so that they lie inside some
large Følner set (to compute the averaged density), we are not certain that
these translations will be linearly independent over $\mathbb{C}$ as
functions. That is, we may have eigenfunctions $f^{(1)},f^{(2)},...f^{(r)}\in
K$ which are not translated versions of each other but nonetheless there exist
$g_{1},g_{2},...g_{r}\in R$ s.t.
$g_{1}f^{(1)}+g_{2}f^{(2)}+...+g_{r}f^{(r)}=0$ that is, an R-linear relation
in K.

If $\\{f^{(1)},f^{(2)},...f^{(r)}\\}$ is a finite generating set of a finitely
generated $R$-module $M$, the (first) syzygy module of of $M$ w.r.t. the
generators $\\{f^{(1)},f^{(2)},f^{(r)}\\}$ is the set of all
$g=(g_{1},...g_{r})\in R^{r}$ such that

$g_{1}f^{(1)}+g_{2}f^{(2)}+...+g_{r}f^{(r)}=0$

and is denoted by $Syz(M)$. Via pointwise multiplication $Syz(M)$ is an
$R$-module as well. By the Hilbert Basis Theorem, $Syz(M)\subset R^{r}$ is
finitely generated. Picking generators for $Syz(M)$, we can consider its own
syzygy module, $Syz(Syz(M))$, abbreviated by $Syz^{2}(M)$. By iteration we can
define the (higher) syzygy module $Syz^{k}(M)$ (which is finitely generated)
for any positive power $k$ along with the conventions $Syz^{1}(M)=Syz(M)$ and
$Syz^{0}(M)=M$.

A alternative way to describe syzygies is through free resolutions. Picking a
finite generating set $\\{f^{(1)},f^{(2)},...f^{(r_{0})}\\}$ for $M$ is
equivalent to finding a surjection $R^{r_{0}}\rightarrow M\rightarrow 0$. The
kernel of this map is precisely the first syzygy module, so we get the SES
$0\rightarrow Syz(M)\rightarrow R^{r_{0}}\rightarrow M\rightarrow 0$.
Iterating this proccess we get another SES $0\rightarrow Syz^{2}(M)\rightarrow
R^{r_{1}}\rightarrow Syz(M)\rightarrow 0$ where we choose a generating set of
$Syz(M)$ of length $r_{1}$. We end up with the following sequence of maps:

$...\;\twoheadrightarrow Syz^{r}(M)\hookrightarrow R^{r_{3}}\twoheadrightarrow
Syz^{3}(M)\hookrightarrow R^{r_{2}}\twoheadrightarrow
Syz^{2}(M)\hookrightarrow R^{r_{1}}\twoheadrightarrow Syz(M)\hookrightarrow
R^{r_{0}}\twoheadrightarrow M\rightarrow 0$

Via composition we get a free resolution of M, that is, a LES beginning with
$\rightarrow R^{r_{0}}\rightarrow M\rightarrow 0$ and consequently consisting
of free R-modules:

$...\;\rightarrow R^{r_{3}}\rightarrow R^{r_{2}}\rightarrow
R^{r_{1}}\rightarrow R^{r_{0}}\rightarrow M\rightarrow 0$

Observe that $Syz^{k}(M)$ can be recovered as the kernels (or equivalently
images) of each map. Hence there is a one-one correspondence between free
resolutions and sequences of higher syzygy modules.

Hilbert’s Syzygy Theorem (see [4]) asserts that the $d^{th}$ syzygy module
$Syz^{d}(M)$ of a finitely generated $\mathbb{C}[z_{1},....z_{d}]$ module $M$
will always be free. This means that if we choose a free generating set for
$Syz^{d}(M)$, then $Syz^{d+1}(M)=0$. As a result the correspoding free
resolution will terminate at the $(d+1)^{th}$ step. We wish to study
$K:=kernel((z_{1},...z_{d})^{P}(\hat{\Delta}-\lambda I_{n}))$. If $L$ is the
image of $(z_{1},...z_{d})^{P}(\hat{\Delta}-\lambda I_{n})$, then the rows of
this matrix generate $L$ and $K$ is the corresponding generating set. By the
Hilbert Syzygy Theorem applied to $L$, this means that $Syz^{d-1}(K)$ is
always free and hence choosing a free generating set of $Syz^{d-1}(K)$,
$Syz^{d}(K)=0$. With all this in mind, we have a formula for the density
$dk(\\{\lambda\\})$ using syzygy modules.

######  Theorem 6.1.

Suppose that $\mathbb{Z}^{d}\curvearrowright\Gamma$ is a periodic graph with
fundamental domain $|W|$ and $\lambda$ is an eigenvalue of the Laplacian
$\Delta$ on $\Gamma$. Let $K$ be the kernel of the map
$(z_{1}...z_{d})^{P}(\hat{\Delta}-\lambda I_{n})$ (for sufficiently large
$P\in\mathbb{N}$) viewed as a map from the
$R=\mathbb{C}[z_{1},....z_{d}]$-module
$\bigoplus_{k=1}^{|W|}\mathbb{C}[z_{1},...z_{d}]$ to itself. Then the
following formula about the density of $\\{\lambda\\}$ holds:

$dk(\\{\lambda\\})=\dfrac{1}{|W|}\sum_{k=0}^{d}(-1)^{k}r_{k}$

where $r_{0},...r_{d}$ are the ranks of the free modules in a free resolution
of M

$0\rightarrow R^{r_{d}}\rightarrow R^{r_{d-1}}\;...\;\rightarrow
R^{r_{1}}\rightarrow R^{r_{0}}\rightarrow M\rightarrow 0$

We will use the following notation for an R-submodule $M$ of a free R-module
$R^{n}$ ($n\in\mathbb{N}$). For each monomial
$z^{l}=z_{1}^{l_{1}}...z_{d}^{l_{d}}$ let $|z^{l}|:=|l|=max_{1\leq i\leq
d}|l_{i}|$. Next, $\forall f_{1}\in R$, let $|f|$ be the maximum length of the
monomials it is comprised of and $\forall f=(f_{1},...f_{n})\in R^{n}$ let
$|f|:=max_{1\leq k\leq n}|f_{k}|$. Define

$B(M,j):=\\{f\in M:\;|f|\leq
j\\}\;\;\;\;\;\;|B(M,j)|:=dim_{\mathbb{C}}(\\{f\in M:\;|f|\leq j\\})$

which are interpreted as balls. Note that the norm $|f|$ of $f\in M$ is taken
with respect to the free R-module $R^{n}$. The proof of this Theorem will rely
on the following lemma:

######  Lemma 6.2.

Let $M$ be a submodule of the free $R$-module $R^{n}$
($R=\mathbb{C}[z_{1},...z_{d}],n\in\mathbb{N}$) with syzygy module

$0\rightarrow Syz(M)\rightarrow R^{r}\rightarrow M\rightarrow 0$

Then $\exists j_{0}$ such that $\forall j>j_{0}$ we have the estimate

$(j-j_{0})^{d}r-|B(Syz(M),j-j_{0})|\;\;\leq\;\;|B(M,j)|\;\;\leq\;\;j^{d}r-|B(Syz(M),j)|$

###### Proof of Lemma.

Fix a generating set $\\{f^{(1)},...,f^{(r)}\\}$ of $M$. Let
$j_{0}:=max_{1\leq i\leq r}|f^{(i)}|$. For all $j>j_{0}$, there are exactly
$(j-j_{0})^{d}$ monomials $z^{k}$ such that $|k|\leq j-j_{0}$. For each such
$k$, $z^{k}f^{(i)}\in B(M,j),\;\forall i$. If
$U_{j}:=Span_{\mathbb{C}}\\{z^{k}f^{(i)}|1\leq i\leq r,|k|\leq j-j_{0}\\}$ is
linearly independent over $\mathbb{C}$, then certainly $r(j-j_{0})^{d}\leq
dim_{\mathbb{C}}U_{j}\leq|B(M,j)|$. However, this is not the case in general.
Instead, the relations $\sum_{\alpha}z^{k_{\alpha}}f^{(i_{\alpha})}=0$ with
$|k_{\alpha}|\leq j-j_{0}$ are in 1-1 correspondence with the syzygies
$(h_{1},...h_{r})\in Syz(M)$ (w.r.t. $\\{f^{(1)},...,f^{(r)}\\}$) such that
$|h_{i}|\leq j-j_{0}\;\forall i$, that is, in 1-1 correspondence with
$B(Syz(M),j-j_{0})$. This correspondence is easily seen to be a linear map and
hence we get a SES:

$0\rightarrow B(Syz(M),j-j_{0})\rightarrow B(R^{r},j-j_{0})\rightarrow
U_{j}\rightarrow 0\;\;\;\implies$
$(j-j_{0})^{d}r-|B(Syz(M),j-j_{0})|\;=\;dim_{\mathbb{C}}B(R^{r},j-j_{0})-dim_{\mathbb{C}}B(Syz(M),j-j_{0})\;=\;dim_{\mathbb{C}}U_{j}\;\leq\;|B(M,j)|$

For the second inequality, suppose that $f\in B(M,j)$. Since
$M=<f^{(1)},...,f^{(r)}>$, $\exists h_{1},...h_{r}$ s.t.
$f=h_{1}f^{(1)}+...+h_{r}f^{(r)}$. But $f$ consists of entries with monomials
$z^{k}$ s.t. $|k|\leq j$ hence we may remove any monomials $z^{k}$ from
$h_{1},...h_{r}$ with $|k|>j$ and we still get
$f=h_{1}f^{(1)}+...+h_{r}f^{(r)}$. This shows that $B(M,j)\subset
W_{j}:=Span_{\mathbb{C}}\\{z^{k}f^{(i)}|1\leq i\leq r,|k|\leq j\\}$. In the
exact same manner as with the first inequality, we get a SES

$0\rightarrow B(Syz(M),j)\rightarrow B(R^{r},j)\rightarrow W_{j}\rightarrow 0$

therefore taking dimensions, the second inequality follows:

$|B(M,j)|\;\leq\;dim_{\mathbb{C}}U_{j}\;=\;dim_{\mathbb{C}}B(R^{r},j)-dim_{\mathbb{C}}B(Syz(M),j)\;=\;j^{d}r-|B(Syz(M),j)|$

∎

###### Proof of Theorem.

Taking the following $\partial_{j_{0}}$ Følner sequence:

$F_{j}=\mathcal{F}_{j}\cdot W=\\{k\in\mathbb{Z}^{d}:|k|\leq j\\}\cdot W$

Then $\forall j$ we have:

$|F_{j}|=|W|(2j_{0}-1)^{d}\;,\;\;\;\;\;\;\mathcal{FB}((j,...j)\cdot
F_{j})=B(R^{|W|},2j)$

where $\mathcal{FB}$ is the Floquet Bloch transform,
$(j,...j)\in\mathbb{Z}^{d}$ is the translation by $j$ units in each direction
and $R=\mathbb{C}[z_{1},..z_{d}]$. We can hence transform the problem from
eigenfunctions to polynomial rings:

$dim_{\mathbb{C}}\\{f\in D_{\lambda}(\Gamma):sprt(f)\subset
F_{j}\\}=dim_{\mathbb{C}}\\{f\in
D_{\lambda}(\Gamma):sprt(f)\subset(j,...j)\cdot F_{j}\\}$
$=dim_{\mathbb{C}}(K\cap\mathcal{FB}((j,...j)\cdot
F_{j}))=dim_{\mathbb{C}}(K\cap B(R^{|W|},2j))=|B(K,2j)|$

By Theorem 5.2,

$dk(\\{\lambda\\})=lim_{j\to\infty}\dfrac{dim_{\mathbb{C}}\\{f\in
D_{\lambda}(\Gamma):sprt(f)\subset
F_{j}\\}}{|F_{j}|}=lim_{j\to\infty}\dfrac{|B(K,2j)|}{|W|(2j-1)^{d}}$

By the previous Lemma:

$(j-j_{0})^{d}r_{0}-|B(Syz(K),j-j_{0})|\;\;\leq\;\;|B(K,j)|\;\;\leq\;\;j^{d}r_{0}-|B(Syz(K),j)|$

Dividing by $j^{d}$ and letting $j\to\infty$ we get

$lim_{j\to\infty}\dfrac{|B(K,j)|}{j^{d}}=r_{0}-lim_{j\to\infty}\dfrac{|B(Syz(K),j)|}{j^{d}}$

By induction and since $Syz^{d+1}(K)=0$,

$lim_{j\to\infty}\dfrac{|B(K,j)|}{j^{d}}=r_{0}-r_{1}+r_{2}-...+(-1)^{d}r_{d}$

And the theorem follows. ∎

Finally, we remark that there exist plenty of algorithms for the computation
of $K$ and its higher syzygy modules, as well as software for these algorithms
(see [4]).

##  7\. Amenable Quasi-homogeneous Graphs with Noetherian Groups Algebra

In this section we generalize Theorem 5.1. Recall that the Hilbert basis
theorem (polynomial rings are Noetherian) was the key ingredient in proving
Theorem 5.1.

######  Theorem 7.1.

Let $G\curvearrowright\Gamma$ be an amenable quasi-homogeneous graph, $\Delta$
be the discrete Laplacian on $\Gamma$ and $\lambda$ an eigenvalue of $\Delta$.
If the group algebra $\mathbb{C}[G]$ is Noetherian (in particular if G is
virtually polycyclic), then there are finitely many finite support
eigenfunctions $f^{(1)},...f^{(r)}\in D_{\lambda}(\Gamma)$ such that every
$\lambda$-eigenfunction of finite support on $\Gamma$ is the linear
combination of translations of $f^{(1)},...f^{(r)}$

###### Proof.

Associate to each $f\in D(\Gamma)$ a function $\hat{f}:V\to\mathbb{C}[G]$
sending $v\in V$ to $\sum_{g\in G}f(g^{-1}\cdot v)g\in\mathbb{C}[G]$. Since
$f$ has finite support, the sum is finite and the map well defined. Notice
that

$\forall h\in G\;\;\hat{(\pi_{h}f)}(v)=\hat{f}(h^{-1}\cdot
v)=h^{-1}\hat{f}(v)$

Fix a fundamental domain $W$. In view of the above identity, we can recover
$\hat{f}:V\to\mathbb{C}[G]$ from the vector $(\hat{f}(w))_{w\in W}=(\sum_{g\in
G}f(g\cdot w)g)_{w\in W}\in\mathbb{C}[G]^{|W|}$. It is easy to see that
$\hat{\cdot}:D(\Gamma)\to\mathbb{C}[G]^{|W|}$ is a bijective
$\mathbb{C}$-linear map. To the operator $\Delta:D(\Gamma)\to D(\Gamma)$
corresponds some other operator
$\hat{\Delta}:\mathbb{C}[G]^{|W|}\to\mathbb{C}[G]^{|W|}$.

In a manner similar to Proposition 3.2, the reader may check that
$\hat{\Delta}$ is a $\mathbb{C}[G]$-module homomorphism from the free
$\mathbb{C}[G]$-module $\mathbb{C}[G]^{|W|}$ to itself. Also note that $f\in
D_{\lambda}(\Gamma)$ iff $(\Delta-\lambda I)f=0$ iff $(\hat{\Delta}-\lambda
I)\hat{f}=0$ iff $f\in kernel(\hat{\Delta}-\lambda I)$. This kernel is a
submodule of $\mathbb{C}[G]^{|W|}$. Since $\mathbb{C}G$ is Noetherian,
$kernel(\hat{\Delta}-\lambda I)$ is finitely generated. Say
$kernel(\hat{\Delta}-\lambda I)=<\hat{f}^{(1)},...,\hat{f}^{(r)}>$. Then
$\forall f\in D_{\lambda}(\Gamma)$, $\exists h_{1},...h_{r}\in\mathbb{C}[G]$
such that $\hat{f}=h_{1}\hat{f}^{(1)}+...+h_{r}\hat{f}^{(r)}$. Write
$h_{1}=\sum_{g\in G}a_{g}g$ so that:

$h_{1}\hat{f}^{(1)}=(\sum_{g\in G}a_{g}g)\hat{f}^{(1)}=\sum_{g\in
G}a_{g}(g\hat{f}^{(1)})=\sum_{g\in G}a_{g}(\hat{\pi_{g}^{-1}f^{(1)}})$

Hence to $h_{1}\hat{f}^{(1)}$ corresponds a function which is the finite
linear combination of translations of $f^{(1)}$, and the theorem follows. ∎

######  Corollary 7.1.1.

Under the above assumptions, Shubin’s formula holds for the discontinuity
points of the spectrum of $\Delta$.

###### Proof.

Combine Theorem 7.1 and Theorem 5.2. ∎

The theorem of Paul Hall [10] states that the group algebra of a virtually
polycyclic group is Noetherian. Recall that a finitely generated group G is
polycyclic if it admits a subnormal series whose factors are all cyclic
groups. Note that nilpotent groups are polycyclic, polycyclic groups are
solvable and solvable groups are amenable. The lamplighter group is an example
of a solvable group which is not polycyclic. Since finite extensions of
amenable groups are amenable, it follows that virtually polycyclic groups are
amenable. Thanks to P. Hall’s theorem, we get a large family of groups to
which the above results apply.

## References

  * [1] Jean Bellissard.  $K$-theory of $C^{\ast}$-algebras in solid state physics.  In Statistical mechanics and field theory: mathematical aspects (Groningen, 1985), volume 257 of Lecture Notes in Phys., pages 99–156. Springer, Berlin, 1986.
  * [2] Gregory Berkolaiko and Peter Kuchment.  Introduction to quantum graphs, volume 186 of Mathematical Surveys and Monographs.  American Mathematical Society, Providence, RI, 2013.
  * [3] Fan R. K. Chung.  Spectral graph theory, volume 92 of CBMS Regional Conference Series in Mathematics.  Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1997.
  * [4] David A. Cox, John Little, and Donal O’Shea.  Using algebraic geometry, volume 185 of Graduate Texts in Mathematics.  Springer, New York, second edition, 2005.
  * [5] François Delyon and Bernard Souillard.  Remark on the continuity of the density of states of ergodic finite difference operators.  Comm. Math. Phys., 94(2):289–291, 1984.
  * [6] Warren Dicks and Thomas Schick.  The spectral measure of certain elements of the complex group ring of a wreath product.  Geom. Dedicata, 93:121–137, 2002.
  * [7] Rostislav Grigorchuk and Christophe Pittet.  Laplace and schrödinger operators without eigenvalues on homogeneous amenable graphs.  2021\.  preprint.
  * [8] Rostislav Grigorchuk and Brian Simanek.  Spectra of Cayley graphs of the lamplighter group and random Schrödinger operators.  Trans. Amer. Math. Soc., 374(4):2421–2445, 2021.
  * [9] Rostislav I. Grigorchuk and Andrzej Żuk.  The lamplighter group as a group generated by a 2-state automaton, and its spectrum.  Geom. Dedicata, 87(1-3):209–244, 2001.
  * [10] P. Hall.  Finiteness conditions for soluble groups.  Proc. London Math. Soc. (3), 4:419–436, 1954.
  * [11] Yusuke Higuchi and Yuji Nomura.  Spectral structure of the Laplacian on a covering graph.  European J. Combin., 30(2):570–585, 2009.
  * [12] Thomas W. Hungerford.  Algebra, volume 73 of Graduate Texts in Mathematics.  Springer-Verlag, New York-Berlin, 1980.  Reprint of the 1974 original.
  * [13] Harry Kesten.  Symmetric random walks on groups.  Trans. Amer. Math. Soc., 92:336–354, 1959.
  * [14] Charles Kittel.  Introduction to Solid State Physics.  Wiley, 6th edition.
  * [15] P. A. Kuchment.  On the Floquet theory of periodic difference equations.  In Geometrical and algebraical aspects in several complex variables (Cetraro, 1989), volume 8 of Sem. Conf., pages 201–209. EditEl, Rende, 1991.
  * [16] Grabowski L. and Virag.  Random walks on lamplighters via random schrödinger operators.  2015\.  unpublished.
  * [17] Wolfgang Lück.  $L^{2}$-invariants: theory and applications to geometry and $K$-theory, volume 44 of Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics].  Springer-Verlag, Berlin, 2002.
  * [18] Bojan Mohar and Wolfgang Woess.  A survey on spectra of infinite graphs.  Bull. London Math. Soc., 21(3):209–234, 1989.
  * [19] Michael Reed and Barry Simon.  Methods of modern mathematical physics. I.  Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York, second edition, 1980.  Functional analysis.
  * [20] Christoph Schumacher and Fabian Schwarzenberger.  Approximation of the integrated density of states on sofic groups.  Ann. Henri Poincaré, 16(4):1067–1101, 2015.
  * [21] Ivan Veselić.  Spectral analysis of percolation Hamiltonians.  Math. Ann., 331(4):841–865, 2005.
  * [22] M. A. Šubin.  Spectral theory and the index of elliptic operators with almost-periodic coefficients.  Uspekhi Mat. Nauk, 34(2(206)):95–135, 1979.
  * [23] Wolfgang Woess.  Random walks on infinite graphs and groups, volume 138 of Cambridge Tracts in Mathematics.  Cambridge University Press, Cambridge, 2000.