text:
\section{Experiments}
\label{sec:expts}

We conduct experiments to demonstrate the dimension-independence of DP-GD with Gaussian noise. The setup mainly follows that from \citet[Figure 1(c)]{jain2014near}.
We use a normalized version of the Cod-RNA dataset~\citep{codrna}, and use logistic regression to solve for binary classification.
Following~\citet{jain2014near}, we append zero-valued features to the data samples, such that the accuracy of a non-private classifier does not change.
To solve the problem privately, we consider DP-SGD with mini-batch gradient and Gaussian noise.
For comparison, we consider DP-SGD with noise drawn from a Gamma distribution.
We fix $\epsilon \approx 5.0$ and $\delta=10^{-5}$.
Additional details on the setup can be found in Appendix~\ref{app:expts}.

In Figure~\ref{fig:expt}, we report the final test accuracy under different data dimensionality after tuning the learning rate.
It is clear that DP-SGD with Gaussian noise is dimension-independent, as is predicted by Theorem~\ref{thm:dimIndependence}.
On the other hand, the accuracy of DP-SGD with Gamma noise decreases as data dimensionality increases.

\begin{figure}[ht]
\centering
\includegraphics[width=0.39\textwidth]{fig/cod-rna.pdf}
\caption{Test accuracy vs. data dimensionality for DP-SGD with i) Gaussian noise, and ii) Gamma noise.

}
\label{fig:expt}
\end{figure}


TITLE: In Pollard p-1 how is the bound B chosen?
QUESTION [0 upvotes]: Does Pollard's p-1 method always produce an answer (given sufficient time and assuming input is composite)? If yes, what is the point of having the bound $B$, why not just keep increasing $a$? If no, how is $B$ reasonably guessed?
Is there a limit to how large $B$ should be? For example if the input is prime then checking up $B=\sqrt{\text{input}}$ would prove there's no factors, is that correct?

REPLY [2 votes]: The p-1-method works , if there is a prime factor $\ p\ $ of $\ N\ $ , such that $\ p-1\ $ splits into prime factors smaller than the chosen bound $\ B\ $. Whether a given bound $\ B\ $ will work, cannot be predicted.
Of course, increasing $\ B\ $ would eventually find a non-trivial factor, but at some point, this method would be not more efficient (perhaps even less efficient) then trial division.
If we are lucky, we can find large factors that could not be found with trial division in reasonable time.
The p-1-method rarely works , if there is no prime factor with , lets say , $\ 25\ $ digits or less. In this case, the better ECM (elliptic curve method) is usually used.


TITLE: Write it as an element of this ring?
QUESTION [2 upvotes]: Since the degree of the irreducible polynomial $x^3+2x+2$ over $\mathbb{Q}[x]$ is odd, it has a real solution , let $a$. I am asked to express $\displaystyle{\frac{1}{1-a}}$ as an element of $\mathbb{Q}[a]$.
I have done the following:
Since $a$ is a real solution of $x^3+2x+2$, we have that $a^3+2a+2=0$.
$\frac{1}{1-a}=y \Rightarrow a=\frac{y-1}{y}$
$$a^3+2a+2=0 \\ \Rightarrow \frac{(y-1)^3}{y^3}+2\frac{y-1}{y}+2=0 \\ \Rightarrow (y-1)^3+2(y-1)y^2+2y^3=0 \\ \Rightarrow 5y^3-5y^2+3y-1=0 \\ \Rightarrow 5\left ( \frac{a-1}{a} \right )^3-5\left ( \frac{a-1}{a} \right )^2+3\left ( \frac{a-1}{a} \right )-1=0 $$
That what I have found is not a polynomial of $a$, with coefficients at $\mathbb{Q}$, right??
Is there an other way to write $\displaystyle{\frac{1}{1-a}}$ as an element of $\mathbb{Q}[a]$ ??

REPLY [1 votes]: Without any trick: you know that $(1-a)^{-1}=\alpha+\beta a+\gamma a^2$ for some $\alpha,\beta,\gamma\in\mathbb{Q}$, that is
$$
(1-a)(\alpha+\beta a+\gamma a^2)=1
$$
This becomes
$$
\alpha+\beta a+\gamma a^2-\alpha a-\beta a^2-\gamma a^3=1
$$
Since $a^3=-2a-2$ this becomes
$$
(\alpha+2\gamma)+(\beta-\alpha+2\gamma)a+(\gamma-\beta)a^2=1
$$
or
\begin{cases}
\alpha+2\gamma=1\\
-\alpha+\beta+2\gamma=0\\
-\beta+\gamma=0
\end{cases}
This should be easy to solve.


TITLE: CM elliptic curves and isogeny
QUESTION [0 upvotes]: Q: Show that any two CM elliptic curves with the same endomorphism algebra (say $K$) are
isogenous.
I was thinking of the following:
Let $E_1\simeq \mathbb{C}/L_1$ and $E_2\simeq \mathbb{C}/L_2$, then since both elliptic curves have CM by $K$, we know $L_1\otimes \mathbb{Q} = L_2\otimes \mathbb{Q}=K$. WLOG we may assume $L_1\subseteq L_2$, then $L_1\cap L_2$ is also a lattice and has finite index in both $L_1$ and $L_2$ (this is where we probably use CM but I am unsure of the details, in fact is it even okay to assume the containment?). From here we conclude that there is an isogeny $\varphi: \mathbb{C}/L_1 \rightarrow \mathbb{C}/L_2$; indeed, since the map is surjective and kernel=$L_2/L_1$ is finite.
What happens for the case of non-CM elliptic curves?

REPLY [1 votes]: Non-CM elliptic curves over the complexes all have endomorphism ring $\Bbb Z$. Up to isomorphism, there are only countably many curves isogenous to
a given curve, but there are uncountably many curves (consider the $j$-invariants) so there are uncountably man isogeny classes of non-CM elliptic curves.


TITLE: Fourier transform of f on the unit sphere
QUESTION [1 upvotes]: My question is: do we have the right to compute the fourier transform of a function over the unit sphere? To be more precise, let $f\in L^1(\mathbb{R} ^n)$, $n\geq1$. Is the integral
$$\int_{S^{n-1}}f(t)e^{-i\langle \omega|t\rangle} d\sigma(t), $$
make any sense? With of course $S^{n-1}$ denotes the unit sphere and $d\sigma$ is the measure over the sphere.

REPLY [0 votes]: It does not make sense as is. An element of $L^1(\mathbb{R}^n)$ is not a function. It is an equivalence class of functions modulo equality away from (Lebesgue) measure zero sets. The sphere $S^{n-1}$ has measure zero, so it does not make sense to evaluate your $f$ on it. You need some regularity hypothesis on $f$, e.g., being continuous or being in a Sobolev space with a trace theorem to $S^{n-1}$.


TITLE: Equivalent ways of stating Cauchy criteria by using limits
QUESTION [0 upvotes]: Here Is this an equivalent way of stating Cauchy's convergence test for series? I learnt a way to state the Cauchy criterion for series by using the limit. Now, while studying function series and improper integrals I came across similar Cauchy criteria to test convergence and I would like to know how I can rephrase them in a similar way by using some limit.
For instance, we know that $\int_a^\infty f(x)dx$ converges if and only if $\forall \epsilon>0, \exists K_\epsilon\in \mathbb{R}$ such that $\displaystyle\left|\int_c^b f(x) dx\right|<\epsilon$ for all $b\ge c\ge K_\epsilon$. This can be rephrased as $\displaystyle\left|\int_c^{c+p} f(x) dx\right|<\epsilon$ for all $c\ge K_\epsilon$ and $p\in \mathbb{N}$, but I don't know what to do next to imply some limit(I am not even sure that this is possible).
However, in the case of function series it should be possible. I think that we can say that $\displaystyle\sum_{n=1}^\infty f_n(x)$ converges uniformly if and only if $\displaystyle \lim_{n\to \infty} \sup_{p\in \mathbb{N}}\left|\sum_{i=0}^p f_{n+i}(x)\right|=0$ for all $x$ in $f_n$'s domain. Am I right?

REPLY [1 votes]: $\int\limits_a^{\infty} f(x)dx$ converges if and only if $\lim_{x \to \infty} \sup_{b>a} |\int\limits_a^{b} f(x+y)dy|=0$. This is similar to the condition you wrote for  series and the proof of this follows from then fact that $\int\limits_a^{b} f(x+y)dy=\int\limits_{a+x}^{b+x} f(t)dt$.


text:
\chapter{The $\ell^2$ theory of \Lap and the transfer operator}
\label{sec:L2-theory-of-Lap-and-Trans}

\headerquote{One geometry cannot be more true than another; it can only be more convenient.}{---~H.~Poincare}

This chapter is devoted to the study of the graph Laplacian \Lap, and the transfer operator \Trans, when considered as acting on the space $\ell^2(\verts)$ of square-summable functions on the vertices. This is $\ell^2(\verts) = \ell^2(\verts,\gm)$ where \gm is the counting measure, and the operators \Lap and \Trans have a profoundly different spectral theory with respect to the $\ell^2$ inner product.

\section{$\ell^2(\verts)$}

In this section, we discuss results for \Lap and \Trans when considered as operators on
\linenopax
\begin{equation}\label{eqn:defn:l2}
  \ell^2(\unwtd) :=
  \{u:\verts \to \bC \suth {\textstyle\sum\nolimits_{x \in \verts}} |u(x)|^2 < \iy\},
\end{equation}
with the inner product
\linenopax
\begin{equation}\label{eqn:defn:l2-inner-prod}
  \la u, v\ra_\unwtd := \sum_{x \in \verts} u(x) v(x).
\end{equation}
  \glossary{name={$\la\cdot,\cdot\ra_\unwtd$},description={unweighted $\ell^2$ inner product},sort=l,format=textbf}
  \glossary{name={$\ell^2(\one)$ or $\ell^2(\verts,\one)$},description={unweighted $\ell^2$ space},sort=l,format=textbf}
The constant function \one appears in the notation to specify the weight involved in the inner product, in contrast to \cond. This is necessary because we will also be interested in \Lap and \Trans as operators on
\linenopax
\begin{equation}\label{eqn:defn:l2c}
  \ell^2(\cond) :=
  \{u:\verts \to \bC \suth {\textstyle\sum\nolimits_{x \in \verts}} \cond(x) |u(x)|^2 < \iy\},
\end{equation}
with the inner product
\linenopax
\begin{equation}\label{eqn:defn:l2c-inner-prod}
  \la u, v\ra_\cond := \sum_{x \in \verts} \cond(x) u(x) v(x).
\end{equation}
  \glossary{name={$\la\cdot,\cdot\ra_\cond$},description={\cond-weighted $\ell^2$ inner product},sort=<,format=textbf}
  \glossary{name={$\ell^2(\cond)$ or $\ell^2(\verts,\cond)$},description={\cond-weighted $\ell^2$ space},sort=<,format=textbf}

While the pointwise definition of \Lap and \Trans remains the same on $\ell^2(\unwtd)$ and  $\ell^2(\cond)$, they are different operators with different domains and different spectra! It is important to keep in mind that in general, none of \HE, $\ell^2(\unwtd)$ or $\ell^2(\cond)$ are contained in any of the others. However, we provide some conditions under which embeddings exist in \S\ref{sec:relating-HE-and-L2}.
We give only some selected results, as this subject is well-documented elsewhere in the literature.

In \S\ref{sec:weighted-spaces}, we consider a map $J:\ell^2(\cond) \to \HE$ is the quotient map induced by the equivalence relation discussed in Remark~\ref{rem:elements-of-HE-are-technically-equivalence-classes}. It turns out that $J$ is an embedding of $\ell^2(\cond)$ into \Fin, and that its range is dense in \Fin. We will also see that \Prob is self-adjoint on $\ell^2(\cond)$, even though it is not even Hermitian on $\ell^2(\unwtd)$ or \HE except when $\cond(x)$ is constant.

\section{The Laplacian on $\ell^2(\unwtd)$}
\label{sec:self-adjointness-of-the-Laplacian}

In this section, we investigate certain properties of the Laplacian on $\ell^2(\unwtd)$, including self-adjointness and boundedness. Dealing with unbounded operators always requires a bit of care; the reader is invited to consult Appendix~\ref{sec:self-adjointness-for-unbounded-operators} to refresh on some principles of self-adjointness of unbounded operators.  Recall that for $S$ to be \emph{self-adjoint}, it must be Hermitian \emph{and} satisfy $\dom S = \dom S^\ad$, where
\linenopax
\begin{align*}
  \dom S^\ad := \{v \in \sH \suth |\la v, Su\ra| \leq K_v \|u\|, \forall u \in \dom S\}.
\end{align*}
In the unbounded case, it is not unusual for $\dom S \subsetneq \dom S^\ad$. Some good references for this section are \cite{Jor78,vN32a,Nel69, ReedSimonII,Rud91,DuSc88}.

Due to Corollary~\ref{thm:nontrivial-harmonic-fn-is-not-in-L2}, we can ignore the possibility of nontrivial harmonic functions while working in this context. Combining Theorem~\ref{thm:E(u,v)=<u,Lapv>+sum(normals)} with Theorem~\ref{thm:TFAE:Fin,Harm,Bdy}, one can relate the inner products of \HE and $\ell^2(\unwtd)$ by
\begin{equation}\label{eqn:rem:energy-as-l2-inner-prod-with-Lap}
  \la u, \Lap v\ra_\unwtd = \la u, v\ra_{\energy},
\end{equation}
for all $u,v \in \spn\{\gd_x\}$. Observe that $\spn\{\gd_x\}$ is dense in $\ell^2(\unwtd)$ with respect to \eqref{eqn:defn:l2-inner-prod}, and dense in \HE in the \energy norm when $\Harm=0$. Then \eqref{eqn:rem:energy-as-l2-inner-prod-with-Lap} immediately implies that the Laplacian is Hermitian on $\ell^2(\unwtd)$ because, again for all $u,v \in \spn\{\gd_x\}$,
\linenopax
\begin{align}\label{eqn:l2-Hermitian}
  \la u, \Lap v\ra_\unwtd = \la u,v \ra_{\energy} = \cj{\la v, u\ra}_{\energy} = \cj{\la v, \Lap u\ra}_\unwtd = \la \Lap u, v \ra_\unwtd,
\end{align}
This may seem trivial, but it turns out that \Lap is not Hermitian on $\ell^2(\cond)$; cf. Lemma~\ref{thm:Lap-not-Hermitian-on-l2(c)}.

Theorem~\ref{thm:Lap-is-bounded-selfadjoint-on-L2c} shows that if \cond is uniformly bounded \eqref{eqn:def:power-bound}, then \Lap is a bounded operator and hence self-adjoint. However, in Theorem~\ref{thm:Laplacian-is-essentially-self-adjoint} we are able to obtain a much stronger result, without assuming any bounds: the Laplacian on any \ERN is \emph{essentially self-adjoint} on $\ell^2(\unwtd)$. (Recall that \Lap is essentially self-adjoint iff it has a unique self-adjoint extension; cf.~Definition~\ref{def:essentially-self-adjoint}.) This is a sharp contrast to the case for \HE, as seen from Theorem~\ref{thm:LapV-not-ess-selfadjoint-iff-Harm=0}. In the latter parts of this section, we also derive several applications of Theorem~\ref{thm:Laplacian-is-essentially-self-adjoint}.

\subsection{The Laplacian as an unbounded operator}

We begin with the operator \Lap defined on $\spn\{\gd_x\}$, the dense domain consisting of functions with finite support. Then let \Lapu denote the closure of \Lap with respect to \eqref{eqn:defn:l2-inner-prod}, that is, its minimal self-adjoint extension to $\ell^2(\unwtd)$. Some good references for this section are \cite{vN32a,Rud91,DuSc88}.

\begin{lemma}\label{thm:Lap-is-semibounded-on-l2}
  The Laplacian \Lapu is semibounded on $\dom \Lapu$. \emph{A fortiori}, for any $u,v \in \ell^2(\unwtd)$,
    \linenopax
    \begin{align}\label{eqn:semibounded-innerprod-l2-identity}
      \la u, \Lapu v \ra_{\unwtd}

      = \sum_{x \in \verts} \cond(x) \cj{u(x)} v(x)
      - \sum_{x,y \in \verts} \cond_{xy} \cj{u(x)} v(y)
    \end{align}
  \begin{proof}
    For any $u, v \in \Fin$, a straightforward computation shows
    \linenopax
    \begin{align}\label{eqn:semibounded-l2-identity}
      \la u, \Lapu u \ra_{\unwtd}
      = \sum_{x \in \verts} \cond(x) |u(x)|^2
      - \sum_{x,y \in \verts} \cond_{xy} \cj{u(x)} u(y),
    \end{align}
    whence the equality in \eqref{eqn:semibounded-innerprod-l2-identity} follows by taking limits and polarizing. To see that \Lapu is semibounded, apply the Schwarz inequality first with respect to $y$, then with respect to $x$, to compute
    \linenopax
    \begin{align*}
      \left|\sum_{x \in \verts} \sum_{y \nbr x} \cond_{xy} \cj{u(x)} u(y)\right|

      &\leq \sum_{x \in \verts} \sqrt{\cond(x)} |u(x)| \left[\sum_{y \nbr x} \cond_{xy} |u(y)|^2 \right]^{1/2} \\
      &\leq \left[\sum_{x \in \verts} \cond(x) |u(x)|^2\right]^{1/2} \left[ \sum_{x,y \in \verts} \cond_{xy} |u(y)|^2 \right]^{1/2} \\
      &= \sum_{x \in \verts} \cond(x) |u(x)|^2,
    \end{align*}
    so that the difference on the right-hand side of \eqref{eqn:semibounded-l2-identity} is nonnegative.
      \end{proof}
\end{lemma}

\begin{theorem}\label{thm:Laplacian-is-essentially-self-adjoint}
  If $\deg(x) < \iy$ for every $x \in \verts$, \Lapu is essentially self-adjoint on $\ell^2(\unwtd)$.
  \begin{proof}
    Lemma~\ref{thm:Lap-is-semibounded-on-l2} shows \Lapu is semibounded on $\ell^2(\unwtd)$, so by Theorem~\ref{thm:essentially-self-adjointness-criterion}, it suffices to show the implication
    \linenopax
    \begin{equation}\label{eqn:thm:essentially-self-adjointness-criterion}
      \Lapu^\ad v = -v \q\implies\q v=0, \qq v \in \dom \Lapu ^\ad.
    \end{equation}
    Suppose that $v \in \ell^2$ is a solution to $\Lapu^\ad v = -v$. Then clearly $\Lapu^\ad v \in \ell^2$, and then by Lemma~\ref{thm:bandedness-sublemma},
    \linenopax
    \begin{align*}
      0 \leq
       \la v, M_{\Lapu} v\ra_\unwtd
      &= \la v, \Lapu^\ad v\ra_\unwtd
      = -\la v, v\ra_\unwtd
      = -\|v\|_\unwtd^2
      \leq 0
      \q\implies\q
      v=0,
    \end{align*}
    where $M_{\Lapu}$ is the matrix of \Lapu in the ONB $\{\gd_x\}_{x \in \verts}$. To justify the first inequality, consider that we may find a sequence $\{v_n\} \ci \Fin$ with $\|v-v_n\|_\unwtd \to 0$. Because the matrix $M_{\Lapu}$ is banded, this is sufficient to ensure that $M_{\Lapu} v_n \to M_{\Lapu} v$ and hence $(v_n,M_{\Lapu} v_n)$ converges to $(v,M_{\Lapu} v)$ in the graph norm, and so $\la v_n, M_{\Lapu} v_n\ra_\unwtd$ converges to $\la v, M_{\Lapu} v\ra_\unwtd$. Then $\la v_n, M_{\Lapu} v_n\ra_\unwtd = \energy(v_n) \geq 0$ for each $n$, and positivity is maintained in the limit (even though $\lim \energy(v_n)$ may not be finite).
  \end{proof}
\end{theorem}

See \cite{Web08} for a similar result.
It follows from Theorem~\ref{thm:Laplacian-is-essentially-self-adjoint} that the closure of the operator \Lapu is self-adjoint on $\ell^2(\unwtd)$, and hence has a unique spectral resolution, determined by a projection valued measure on the Borel subsets of the infinite half-line $\bR_+$. This is in sharp contrast with the continuous case; in Example~\ref{exm:eigenvectors-at-infinity} we illustrate this by indicating how $\Lapu = - \frac{d^2}{dx^2}$ fails to be an essentially self-adjoint operator on the Hilbert space $L^2(\bR_+)$.

\begin{remark}\label{rem:Lap-is-banded}
  The matrix for the operator \Lapu on $\ell^2(\unwtd)$ is \emph{banded} (cf.~\S\ref{sec:banded-matrices}):
  \linenopax
  \begin{align}\label{eqn:L2-Laplacian-is-banded}
    M_{\Lapu}(x,y) = \la \gd_x,\Lapu \gd_y\ra_\unwtd
    =
    \begin{cases}
      \cond(x), &y=x,\\
      - \cond_{xy}, &y \nbr x, \\
      0, &\text{else}.
    \end{cases}
  \end{align}

  The bandedness of $M_{\Lapu}$ is a crucial element of the above proof; Example~\ref{exm:eigenvectors-at-infinity} shows how this proof technique can fail without bandedness. See also Remark~\ref{rem:Lap-is-banded} and  Example~\ref{exm:banded-nonselfadjoint-matrix} for what can go awry without bandedness.

  However, bandedness is not sufficient to guarantee essential self-adjointness. In fact, see Example~\ref{exm:banded-nonselfadjoint-matrix} for a Hermitian operator on $\ell^2$ which is not self-adjoint, despite having a \emph{uniformly banded} matrix, that is, there is some $n \in \bN$ such that each row and column has no more than $n$ nonzero entries.
  The essential self-adjointness of \Lapu in this context is likely a manifestation of the fact that the banding is geometrically/topologically local; the nonzero entries correspond to the vertex neighbourhood of a point in \verts.
\end{remark}

\subsection{The spectral representation of \Lap}
It is clear from Lemma~\ref{thm:converse-to-E(u,v)=<u,Lapv>} that $v \in \dom \energy$ whenever $v, \Lapu v \in \ell^2(\unwtd)$. However, this condition is not necessary, and the precise characterization of $\dom\energy$ is more subtle.

\begin{theorem}\label{thm:HE=Lap1/2}
  For all $u \in \ell^2(\unwtd) \cap \dom\energy$, $\|u\|_\energy = \|\hat\Lap^{1/2} \hat u\|_2$. Therefore, \HE can be characterized in terms of the spectral resolution of \Lap as
  \linenopax
  \begin{equation}\label{eqn:thm:H_energy=dom(sqrt(Lap))}
    \ell^2(\unwtd) \cap \dom\energy
    = \{v: \verts \to \bC \suth \|\widehat{\Lap}_\unwtd^{1/2} \hat v\|_2 < \iy\},
  \end{equation}
  where $\hat v$ is the image of $v$ in the spectral representation of \Lapu.
  \begin{proof}
    Theorem~\ref{thm:Laplacian-is-essentially-self-adjoint} also gives a spectral resolution
    \linenopax
    \begin{align}
      \Lap = \int \gl E(d\gl), \q E:\sB(\bR_+) \to Proj(\ell^2).
    \end{align}
    Applying the functional calculus to the Borel function $r(x) = \sqrt x$, we have
    \linenopax
    \begin{align}\label{eqn:dom-Lap1/2}
      {\Lap}^{1/2} = \int \gl^{1/2} E(d\gl),
      \qq \dom {\Lap}^{1/2} = \{v \in \ell^2 \suth \int |\gl| \cdot \|E(d\gl)v\|^2 < \iy\}.
    \end{align}
    This gives $v \in \ell^2(\unwtd) \cap \dom\energy$ if and only if $v+k \in \dom {\Lap}^{1/2}$ for some $k \in \bC$. However, $\Lap(v+k) = \Lap v$, so the same is true for
    ${\Lap}^{1/2}$ by the functional calculus.
  \end{proof}
\end{theorem}

\begin{remark}\label{rem:domeE-not-domLap12}
  It is important to observe that $\dom\energy$ is not simply the spectral transform of $\dom \hat\Lap^{1/2} = \{\hat v \suth \hat v \in L^2$ and $\|\hat \Lap^{1/2} \hat v\|<\iy\}.$ The restriction $\hat v \in L^2$ must be removed because there are many functions of finite energy which do not correspond to $L^2$ functions. For an elementary yet important example, see Figure~\ref{fig:vx-in-Z1} of Example~\ref{exm:Z-not-bounded}.

  Indeed, recall from Corollary~\ref{thm:nontrivial-harmonic-fn-is-not-in-L2} that no nontrivial harmonic function can be in $\ell^2$; see Example~\ref{exm:binary-tree:nontrivial-harmonic}. In this, example $v$ is equal to the constant value $1$ on one infinite subset of the graph, and equal to the constant value $0$ on another.
\end{remark}

\begin{remark}\label{rem:LapTilde-doesn't-see-constants}
  For the example of the integer lattice \bZd, Remark~\ref{rem:HE(Zd)-lies-in-L2(Zd)} shows quite explicitly why the addition of a constant to $v \in \HE$ has no effect on the spectral (Fourier) transform. In this example, one can see directly that addition of a constant $k$ before taking the transform corresponds to the addition of a Dirac mass after taking the transform. As the Dirac mass is supported where the transform of the function vanishes, it has no effect.
\end{remark}

We can also give a reproducing kernel for \Lap on $\ell^2(\unwtd)$. Recall from \eqref{eqn:def:graph-neighbours} that the \emph{vertex neighbourhood} of $x \in \verts$ is $\vnbd(x) := \{y \in \verts \suth y \nbr x\} \ci \verts$. Also recall from Definition~\ref{def:ERN} that $x \notin \vnbd(x)$ and from Definition~\ref{def:conductance-measure} that the conductance function is $\cond(x) := \sum_{y \nbr x} \cond_{xy}$.

\begin{lemma}\label{thm:Lap-has-reproducing-kernel-on-L2}
  The functions $\{\Lap \gd_x\}_{x \in \verts} = \{\cond(x) \gd_x - \cond_{(x\cdot)} \charfn{\vnbd(x)}\}_{x \in \verts}$ give a reproducing kernel for \Lap on $\ell^2(\unwtd)$.
  \begin{proof}
    Since $\la \gd_x, u \ra_\unwtd = u(x)$, the result follows by
    \linenopax
    \begin{align*}
      \Lap v(x)
      = \cond(x) v(x) - \sum_{y \nbr x} \cond_{xy} v(y)
      = \la \cond(x) \gd_x, v\ra_\unwtd - \la \cond_{(x \cdot)}\charfn{G(x)},v\ra_\unwtd
      = \la \Lap \gd_x, v \ra_\unwtd.
    \end{align*}
    This is a recapitulation of \eqref{eqn:L2-Laplacian-is-banded}. Since $\cond(x) < \iy$, it is clear that $\Lap \gd_x \in \ell^2(\unwtd)$.
  \end{proof}
\end{lemma}

\section{The transfer operator}
\label{sec:the-transfer-operator}
\label{sec:The-transfer-operator-on-L2c}

\begin{defn}\label{def:power-bound}
  We say the graph $(\Graph, \cond)$ \sats the \emph{Powers bound} iff
  \linenopax
  \begin{equation}\label{eqn:def:power-bound}
    \|\cond\|_\iy := \sup_{x \in \verts} \cond(x)

       < \iy.
  \end{equation}

\end{defn}
  \glossary{name={$\|\cond\|$},description={operator norm of \cond, also $\sup \cond(x)$},sort=M,format=textbf}
The terminology ``Powers bound'' stems from \cite{Pow76b}, wherein the author uses this bound to study the emergence of long-range order in statistical models from quantum mechanics. Our motivation is somewhat different, and most of our results do not require such a uniform bound. However, when satisfied, it implies the boundedness of the graph Laplacian (and hence its self-adjointness) and the compactness of the associated transfer operator; see \S\ref{sec:the-transfer-operator}.

The fact that the Powers bound entails the inclusion $\ell^2(\unwtd) \ci \HE$ (see Theorem~\ref{thm:energy-bounded-by-L2}) illustrates how strong this assumption really is.

While the Laplacian may be unbounded for infinite networks in general, Theorem~\ref{thm:Lap-is-bounded-selfadjoint-on-L2c} gives one situation in which \Lap is always bounded. To see sharpness, note that this bound is obtained in the integer lattices of Example~\ref{exm:infinite-lattices}. In particular, for $d=1$, we have $\|\Lap\| = \sup |4(\sin^2\frac t2)| = 4 = 2 \|\cond\|$.

\begin{theorem}\label{thm:Lap-is-bounded-selfadjoint-on-L2c}
  As an operator on $\ell^2(\unwtd)$, the Laplacian satisfies $\|\Lap\|_\unwtd \leq 2\uBd$, and hence is a bounded self-adjoint operator whenever the Powers bound holds. Moreover, this bound is sharp.
  \begin{proof}
    Since $\Lap = \cond - \Trans$, this is clear by the following lemma.
  \end{proof}
\end{theorem}

Recall from Definition~\ref{def:graph-transfer-operator} that the \emph{transfer operator} \Trans acts on an element of $\dom \Lap$ by
\begin{equation}\label{eqn:def:transfer-operator-on-HE}
  (\Trans v)(x) := \sum_{y \nbr x} \cond_{xy} v(y).
\end{equation}
One should not confuse \Trans with the (bounded) probabilistic transition operator $\Prob = \cond^{-1}\Trans$; recall that the Laplacian may be expressed as $\Lap = \cond - \Trans$, where \cond denotes the associated multiplication operator. Note that $\Trans = \cond - \Lap$ is Hermitian on $\ell^2(\one)$ by \eqref{eqn:l2-Hermitian}. This is a bit of a surprise, since transfer operators are not generally Hermitian. Unfortunately, $\Trans_\unwtd$ may not be self-adjoint. In fact, the transfer operator of Example~\ref{exm:banded-nonselfadjoint-matrix} is not even essentially self-adjoint; see also \cite{vN32a,Rud91,DuSc88}.

\begin{lemma}\label{thm:Transc-bounded-when-cond-is}
  $\|\Trans_\unwtd\| \leq \|\cond\|$.
  \begin{proof}

    Recall that $\Trans_\unwtd = \Trans$ pointwise. The triangle inequality and Schwarz inequality give
    \linenopax
    \begin{align*}
      |\la f, \Trans f\ra_\unwtd|

      &\leq \sum_{x \in \verts} |f(x)| \sum_{y \nbr x} \left| \sqrt{\cond_{xy}} \sqrt{\cond_{xy}} f(y) \right| \\

      &\leq \sum_{x \in \verts} |f(x)| \cond(x)^{1/2} \left(\sum_{y \nbr x} \cond_{xy}|f(y)|^2 \right)^{1/2} \\
      &\leq \left(\sum_{x \in \verts} \cond(x) |f(x)|^2 \right)^{1/2}
        \left(\sum_{x,y \in \verts} \cond_{xy}|f(y)|^2 \right)^{1/2}.
    \end{align*}
    Since the both factors above may be bounded above by $\left(\uBd \cdot \|f\|_\unwtd^2\right)^{1/2}$ (using another application of Schwarz for the one on the right), we have $|\la f, \Trans f\ra_\cond| \leq \uBd \cdot \|f\|^2_\unwtd$.
  \end{proof}
\end{lemma}

\begin{remark}\label{rem:Transc-bounded-by-cond}
  When $d=1$, Example~\ref{exm:infinite-lattices} (the simple integer lattice) shows that the bound of Corollary~\ref{thm:Transc-bounded-when-cond-is} is sharp. From the proof of Lemma~\ref{thm:Fourier-transform-of-Lap-on-Zd}, one finds that
  \linenopax
  \begin{align*}
    \|\Trans\| = \sup|2\cos t| = 2 = 1+1 = \cond(n), \; \forall n \in \bZ.
  \end{align*}
\end{remark}

\begin{defn}\label{def:cond_x2}
  Let $\cond_x$ be defined by $\cond_x(y) = \cond_{xy}$, so
  \begin{equation}\label{eqn:cond_x^2-notation}
    \cond_x \cdot \cond_x := \sum_{y \nbr x} \cond_{xy}^2
  \end{equation}
  We denote this with the shorthand $\cond_x^2 = \cond_x \cdot \cond_x$.
\end{defn}

\begin{theorem}\label{thm:transfer-operator-is-bounded-on-L2c}
  If \cond is bounded, then $\Trans_\unwtd:\ell^2(\unwtd) \to \ell^2(\unwtd)$ is bounded and self-adjoint. If $\Trans_\unwtd$ is bounded, then $\cond_x^2$ is a bounded function of $x$.
  \begin{proof}
    \fwd The boundedness of \Trans is Lemma~\ref{thm:Transc-bounded-when-cond-is}.
    Any bounded Hermitian operator is immediately self-adjoint; see Definition~\ref{def:self-adjoint}.

    \bwd For the converse, suppose that $\cond_x^2$ is unbounded. It follows that there is a sequence $\{x_n\}_{n=1}^\iy \ci \verts$ with $\cond_{x_n}^2 \to \iy$, and a path \cpath passing through each $x_n$ exactly once.  Consider the orthonormal sequence $\left\{\gd_{x_n}\right\}$:
    \linenopax
    \begin{align*}
      \Trans_\unwtd \gd_z(x)
      &= \sum_{y \nbr x} \cond_{xy} \gd_z(y)
      = \sum_{y \nbr z} \cond_{zy} \gd_z(y), \text{ and }
      \|\Trans_\unwtd \gd_z\|_\unwtd^2 = \sum_{y \nbr z} \cond_{yz}^2.
    \end{align*}
    Then letting $z$ run through the vertices of \cpath, it is clear that  $\|\Trans_\unwtd \gd_z\|_\unwtd^2 \to \iy$.
  \end{proof}
\end{theorem}

Recall from Definition~\ref{def:limit-at-infty} that $u(x)$ \emph{vanishes at \iy} iff for any exhaustion $\{\Graph_k\}$, one can always find $k$ such that $\|u(x)\|_\iy < \ge$ for all $x \notin \Graph_k$.

Using a nested sequence as describe in Definition~\ref{def:limit-at-infty}, it is not difficult to prove that $\Trans_\unwtd$ is always the weak limit of the finite-rank operators $\Trans_n$ defined by $\Trans_n := P_n \Trans_\unwtd P_n$, where $P_n$ is projection to $\Graph_n = \spn\{\gd_x \suth x \in G_n\}$, so that
\begin{equation}\label{eqn:Trans-is-limit-of-Transn}
  \Trans_n v(x) = \charfn{G_n(x)} (\Trans_\unwtd v)(x) = \sum_{\substack{y \nbr x \\ y \in G_n}} \cond_{xy} v(y).
\end{equation}
Norm convergence does not hold without further hypotheses (see Example~\ref{exm:nonuniformly-converging-transfer-operator}) but we do have Theorem~\ref{thm:transfer-operator-is-compact-on-L2c}, which requires a lemma.

\begin{theorem}\label{thm:transfer-operator-is-compact-on-L2c}
  If $\cond \in \ell^2$ and $\deg(x)$ is bounded on \Graph, then the transfer operator $\Trans_\unwtd:\ell^2(\unwtd) \to \ell^2(\unwtd)$ is compact. If $\Trans_\unwtd$ is compact, then $\cond_x^2$ vanishes at \iy.
  \begin{proof}
    \bwd Consider any nested sequence $\{\Graph_k\}$ of finite connected subsets of \Graph, with $\Graph = \bigcup \Graph_k$, and the restriction of the transfer operator to these subgraphs, given by $\Trans_N := P_N \Trans_\unwtd P_N$, where $P_N$ is projection to $\Graph_N$. Then for $D_N := \Trans_\unwtd - \Trans_N$, consider the operator norm
    \linenopax
    \begin{align}\label{eqn:norm-estimate-on-trans-approximation}
      \|D_N\|
      = \left\|\begin{array}{cc}
          0 & P_N \Trans_\unwtd P_N^\perp \\
          P_N^\perp \Trans_\unwtd P_N & P_N^\perp \Trans_\unwtd P_N^\perp \\
        \end{array}\right\|,
    \end{align}
    where the ONB for the matrix coordinates is given by $\{\gd_{x_k}\}_{k=1}^\iy$ for some enumeration of the vertices.

    Since $\deg(x)$ is bounded, the matrices for $\Lap_\unwtd$ and hence also $\Trans_\unwtd$ are uniformly banded; whence $D_N$ is uniformly bounded with band size $b_N$ and Lemma~\ref{thm:bandedness-gives-norm-bound} applies.
         \begin{comment}
             it follows that $D_N$ is, too.
             For a banded matrix $A$,
             \linenopax
             \begin{align*}
               \|v\|=1
               \q\implies\q |v_m| \leq 1, \forall m
               \q\implies\q [Av]_m \leq \sum_{k=1}^{b_m} |a_{m,n_k}|
             \end{align*}
             where $[Av]_m$ denotes the \nth[m] entry of the vector $Av$ and $b_m$ is the size of the \nth[m] band. Then
             \linenopax
             \begin{align*}
               \|Av\|^2 = \sum_{m=1}^\iy \left(\sum_{k=1}^{b_m} |a_{m,n_k}|\right)^2.
             \end{align*}
         \end{comment}
    Since the first $N$ entries of $D_{N+b_N}v$ are 0, we have
    \linenopax
    \begin{align*}
      \|D_{N+b_N}v\|^2
      = \sum_{m=N+1}^\iy \left(\sum_{k=1}^{b_m} \cond_{mn_k} \right)^2
      = \sum_{m=N+1}^\iy \cond(x_m)^2,
    \end{align*}
    which tends to 0 for $\cond \in \ell^2(\unwtd)$.

        \begin{comment}
            Fix $\ge > 0$. From the hypothesis, we can choose $n$ large enough that
            \linenopax
            \begin{align*}
              x>n \implies \cond_{x,y} < \ge,
              \q\text{and}\q
              y>n \implies \cond_{x,y} < \ge.
            \end{align*}

            Then all entries of the \nth row of $D_n$ are less than \ge and hence $\|D_n\| \leq \ge$.

            Denote the width of the band of the row of $D_n$ corresponding to $x_k$ by $B_{x_k}$.

            Observe that any entry $\cond_{xy}$ appearing in submatrix of \eqref{eqn:norm-estimate-on-trans-approximation} corresponding to $P_n \Trans_\unwtd P_n^\perp$ (i.e., upper right) must satisfy the restrictions
            \linenopax
            \begin{align*}
              \cond_{xy} \in [P_n \Trans_\unwtd P_n^\perp]
              \q\implies\q y > n \text{ and } n \geq x > n-B_x,
            \end{align*}
            where $B_x$ is the bandwidth mentioned just above. These restrictions ensure that $\|\cond(x)\|_\unwtd = \sum_y \cond_{xy}^2$ is well-defined. Since $\|\cond(x)\|_\unwtd \to 0$ as $y \to \iy$, one also has $\max_y \cond_{xy} \to 0$ as $y \to \iy$. This means that taking $n$ sufficiently large ensures all entries in $[P_n \Trans_\unwtd P_n^\perp]$ are less than a specified $\ge>0$.

            The other two submatrices have the restrictions
            \linenopax
            \begin{align*}
              \cond_{xy} \in [P_n^\perp \Trans_\unwtd P_n] &\q\implies\q y \leq n \text{ and } n < x \leq n+B_x, \text { and} \\
              \cond_{xy} \in [P_n^\perp \Trans_\unwtd P_n^\perp] &\q\implies\q n < y \leq n + B_x \text{ and } n < x \leq n+B_x,
            \end{align*}
            but the rest of the argument is the same.
        \end{comment}

    \fwd For the converse, suppose that $\cond_x^2$ does not vanish at \iy. It follows that there is a sequence $\{x_n\}_{n=1}^\iy \ci \verts$ with $\|\cond_{x_n}^2\|_\unwtd \geq \ge > 0$, and a path \cpath passing through each of them exactly once. By passing to a subsequence if necessary, is also possible to request that the sequence satisfies
    \linenopax
    \begin{align*}
      \vnbd(x_n) \cap \vnbd(x_{n+1}) = \es, \q\forall n,
    \end{align*}
    since the sequence need not contain every point of \cpath.
    Consider the orthonormal sequence $\left\{\gd_{x_n}\right\}$. We will show that $\left\{\Trans_\unwtd \gd_{x_n}\right\}$ contains no convergence subsequence:
    \linenopax
    \begin{align*}
      \Trans_\unwtd \gd_{x_n} - \Trans_\unwtd \gd_{x_m}
      &= \sum_{y \nbr x_n} \cond_{x_n y} \gd_{x_n} - \sum_{z \nbr x_m} \cond_{x_m z} \gd_{x_m} \\
      \|\Trans_\unwtd \gd_{x_n} - \Trans_\unwtd \gd_{x_m}\|^2
      &= \|\Trans_\unwtd \gd_{x_n}\|^2 + \|\Trans_\unwtd \gd_{x_m}\|^2
       = \sum_{y \nbr x_n} \cond_{x_n y}^2 + \sum_{z \nbr x_m} \cond_{x_m z}^2 \geq 2\ge.
    \end{align*}
    There are no cross terms in the final equality by orthogonality; $x_{n+1}$ was chosen to be far enough past $x_n$ that they have no neighbours in common.
  \end{proof}
\end{theorem}

\begin{cor}\label{thm:Transc-compact-when-cond-vanishes}
  If \cond vanishes at \iy and $\deg(x)$ is bounded, then $\Trans_\unwtd$ is compact.
  \begin{proof}
    The proof of the forward direction of Theorem~\ref{thm:transfer-operator-is-compact-on-L2c} just uses the hypotheses to show that $\sup_{x,y} \cond_{xy}$ can be made arbitrarily small by restricting $x,y$ to lie outside of a sufficiently large set.
  \end{proof}
\end{cor}

\subsection{Fredholm property of the transfer operator}
A stronger form of the Theorem~\ref{thm:Pot-nonempty-by-Fredholm} was already obtained in Corollary~\ref{thm:Pot-nonempty-via-Riesz}, but we include this brief proof for its radically contrasting flavour.

\begin{defn}\label{def:Fredholm-operator}
  A \emph{Fredholm operator} $L$ is one for which the kernel and cokernel are finite dimensional. In this case, the Fredholm index is $\dim \ker L - \dim \ker L^\ad$. Alternatively, $L$ is a Fredholm operator if and only if $\hat L$ is self-adjoint in the Calkin Algebra, i.e., $L = S + K$, where $S = S^\ad$ and $K$ is compact.
\end{defn}

\begin{theorem}\label{thm:Pot-nonempty-by-Fredholm}
  If \cond vanishes at infinity, then $\Pot(\ga,\gw)$ is nonempty.
  \begin{proof}
    When the Powers bound is satisfied, the previous results show \Lap is a bounded self-adjoint operator, and \Trans is compact. Consequently, \Lap is a Fredholm operator. By the Fredholm Alternative, $\ker \Lap = 0$ if and only if $\ran \Lap = \ell^2(\unwtd)$. Modulo the harmonic functions, $\ker \Lap = 0$, so $\gd_\ga - \gd_\gw$ has a preimage in $\ell^2(\unwtd)$.
  \end{proof}
\end{theorem}

\begin{comment}
  The spaces $\ell^2(\unwtd)$ and $\ell^2(\unwtd)$ are unitarily equivalent. Moreover, this equivalence is implemented by the operator
  \begin{equation}\label{eqn:unitary-equivalence-of-L2c,L2}
    U:\ell^2(\unwtd) \to \ell^2(\unwtd)
    \q\text{via}\q
    (Uv)(x) = \sqrt{\gm(x)}v(x),
  \end{equation}
  so that the matrix entries for the transfer operators are related by
  \begin{equation}\label{eqn:matrix-entries-for-transfer-operators-related}
    [\Trans_\cond]_{x,y} = \frac1{\sqrt{\cond(x)}} [\Trans_\unwtd]_{x,y} \sqrt{\cond(y)},
  \end{equation}
  where the ONB for $[\Trans_\unwtd]$ is $\{\gd_x\}_{x \in \verts}$ and the ONB for $[\Trans_\cond]$ is $\{\cond(x)^{-1/2}\gd_x\}_{x \in \verts}$.
  \begin{proof}
    From the respective inner products, one observes directly that $U$ is unitary:
    \linenopax
    \begin{align*}
      \|v\|_\cond^2
      = \sum_{x \in \verts} \cond(x) |v(x)|^2
      = \sum_{x \in \verts} \left|\sqrt{\cond(x)} v(x)\right|^2
      =\|\sqrt{\cond} v\|_\unwtd^2
      =\|Uv\|_\unwtd^2.
    \end{align*}
    Then from the following commutative diagram,
    \linenopax
    \begin{equation}\label{xy:transfer-operator-unitary-equiv}
      \xymatrix{
        \ell^2(\unwtd) \ar[r]^U \ar[d]_{\Trans_\cond} &\ell^2(\unwtd) \ar[d]_{\Trans_\unwtd} \\
        \ell^2(\unwtd) \ar@/^/[r]^U &\ell^2(\unwtd) \ar@/^/[l]^{U^\ad}
      }
    \end{equation}
    one immediately has $\Trans_\cond = U^\ad \Trans_\unwtd U$ and $\Trans_\unwtd = U \Trans_\cond U^\ad$. It is immediate that $U^\ad = U^{-1} = \frac1{\sqrt{\cond}}$, and so $U$ transforms the respective ONBs
    \linenopax
    \begin{align*}
      U^\ad:\ell^2(\unwtd) \to \ell^2(\unwtd)
      \q\text{via}\q
      U^\ad:\{\gd_x\}_{x \in \verts} \mapsto \left\{\tfrac{\gd_x} {\sqrt{\cond(x)}} \right\}_{x \in \verts}.
    \end{align*}
    For $v \in \ell^2(\unwtd)$, one easily obtains \eqref{eqn:matrix-entries-for-transfer-operators-related} from
    \linenopax
    \begin{align*}
      \Trans_\cond v(x)
      &= (U^\ad \Trans_\unwtd U v)(x)
       = \frac1{\sqrt{\cond(x)}} \sum_{y \in \verts} [\Trans_\unwtd]_{x,y} \sqrt{\cond(y)} v(y).
      \qedhere
    \end{align*}
  \end{proof}
\end{comment}

\subsection{Some estimates relating \HE and $\ell^2(\unwtd)$}
\label{sec:relating-HE-and-L2}

In this section, we make the standing assumption that the functions under consideration lie in $\HE \cap \ell^2(\unwtd)$. Strictly speaking, elements of \HE are equivalence classes, but each has a unique representative in $\ell^2$ and it is understood that we always choose this one. Our primary tool will be the identity $\energy(u,v) = \la u, \Lap v \ra_\unwtd$ from \eqref{eqn:rem:energy-as-l2-inner-prod-with-Lap}, which is valid on the intersection $\HE \cap \ell^2(\unwtd)$. For example, note that this immediately gives
\begin{equation}\label{eqn:norm(lapl)-related-to-energy}
  \la v, \Lap v \ra_\energy = \|\Lap v\|_\unwtd^2,
  \qq\text{and}\qq
  \energy(v) = \|\Lap^{1/2} v\|_\unwtd^2,
\end{equation}
where the latter follows by the spectral theorem.
Theorem~\ref{thm:Pot-is-nonempty-by-current-flows} showed that $\Pot(\ga,\gw) \neq \es$, for any choice of $\ga \neq \gw$. It is natural to ask other questions in the same vein.
\begin{enumerate}[(i)]
  \item Is $\ell^2(\unwtd) \ci \HE$? No: consider the 1-\dimnl integer lattice described in Example~\ref{exm:1-dimnl-integer-lattice}.
  \item Is $\HE \ci \ell^2(\unwtd)$? No: consider the function $f$ defined on the binary tree in Example~\ref{exm:binary-tree:nonapproximable} which takes the value $1$ on half the tree and $-1$ on the other half (and is 0 at $o$). This function has energy $\energy(f)=2$, but it is easily seen that there is no $k$ for which $f+k \in \ell^2(\unwtd)$.
  \item Does $\Lap v \in \ell^2$ imply $v \in \HE$ or $v \in \ell^2(\unwtd)$? Neither of these are true, by the example in the previous item.
  \item Is $\Pot(\ga,\gw) \ci \ell^2$? No: consider again the 1-\dimnl integer lattice, with $\ga < \gw$. Then if $v \in \Pot(\ga,\gw)$, it will be constant (and equal to $v(\ga)$) for $x_n$ to the left of \ga, and it will be constant (and equal to $v(\gw)$) for $x_n$ right of \gw.
\end{enumerate}

\version{}{
However, we have some results in these directions under further restrictions:
\begin{enumerate}[(i)]
  \item When the Powers bound \eqref{eqn:def:power-bound} is satisfied, then $\ell^2(\unwtd) \ci \HE$. See Theorem~\ref{thm:energy-bounded-by-L2}.
  \item When the Powers bound \eqref{eqn:def:power-bound} is satisfied, then $v \in \HE \iff \Lap v \in \HE$. See Theorem~\ref{thm:hypoellipticity-in-HE}.
  \item If $\Lap v \in \ell^2(\unwtd)$, then $v \in \HE$. Moreover, if \Lap has a spectral gap, then the converse holds. See Theorem~\ref{thm:hypoellipticity-in-L2}.
\end{enumerate}
}

\begin{lemma}\label{thm:energy-bounded-by-L2}
  $\|v\|_\energy \leq \|\Lap^{1/2}\| \cdot \|v\|_\unwtd$ for every $v \in \HE$. If the Powers bound \eqref{eqn:def:power-bound} is satisfied, then  $\ell^2(\unwtd) \ci \HE$.
  \begin{proof}
    Since $\|v\|_\energy^2 = \la v, \Lap v\ra_\unwtd$, this is immediate from Lemma~\ref{thm:Lap-is-bounded-selfadjoint-on-L2c}.
  \end{proof}
\end{lemma}

\begin{lemma}\label{thm:Lap-bdd-onHE-by-L2}
  If \Lap is bounded on $\ell^2(\unwtd)$, then it is bounded with respect to \energy.
  \begin{proof}
    The hypothesis implies \Lap is self-adjoint on $\ell^2$, so that one can take the spectral representation $\hat \Lap$ on $L^2(X,d\gn)$ and perform the following computation:
    \linenopax
    \begin{align*}
      \|\Lap v\|_\energy
      &= \|\Lap \Lap^{1/2} v\|_\unwtd
      \leq \|\hat \Lap\|_\iy \cdot \|\Lap^{1/2} v\|_\unwtd
      = \|\hat \Lap\|_\iy \cdot \|v\|_\energy.
      &&\qedhere
    \end{align*}
  \end{proof}
\end{lemma}

\begin{lemma}\label{thm:energy-bounded-by-positivity}
  Let $v \in \ell^2(\unwtd)$. If $v \geq 0$ (or $v \leq 0$), then $\|v\|_\energy \leq \|v\|_\unwtd$. If $v$ is bipartite and alternating, then $\|v\|_\energy \geq \|v\|_\unwtd$.
  \begin{proof}
    Both statements follow immediately from the equality
    \linenopax
    \begin{align*}
      \energy(v)
      &= \la v, \Lap v\ra_\unwtd
      = \la v, v\ra_\unwtd - \la v, \Trans v\ra_\unwtd
      = \|v\|_\unwtd - \sum_{y \nbr x} \cond_{x,y} v(x) v(y).
      \qedhere
    \end{align*}
  \end{proof}
\end{lemma}

\section{The Laplacian and transfer operator on $\ell^2(\cond)$}
\label{sec:weighted-spaces}

In \S\ref{sec:self-adjointness-of-the-Laplacian}--\ref{sec:the-transfer-operator}, we studied \Lap and \Trans as operators on the unweighted space $\ell^2(\unwtd)$. In this section, we consider the renormalized versions of these operators and attempt to carry over as many results as possible to the context of $\ell^2(\cond)$.
\linenopax
\begin{equation}\label{eqn:defn:l2c-recall}
  \ell^2(\cond) :=
  \{u:\verts \to \bC \suth {\textstyle\sum\nolimits_{x \in \verts}} \cond(x) |u(x)|^2 < \iy\},
\end{equation}
with the inner product
\linenopax
\begin{equation}\label{eqn:defn:l2c-inner-prod-recall}
  \la u, \Lap v\ra_\cond := \sum_{x \in \verts} \cond(x) u(x) \Lap v(x).
\end{equation}

Take the operator \Lap defined on $\spn\{\gd_x\}$, the dense domain consisting of functions with finite support. Then let \Lapc denote the closure of \Lap with respect to \eqref{eqn:defn:l2c-inner-prod-recall}, that is, its minimal self-adjoint extension to $\ell^2(\cond)$.

\begin{lemma}\label{thm:sum(uLapv)<=|u|.|v|}
  For $u \in \ell^2(\cond)$ and $v \in \HE$,
  \linenopax
  \begin{align}\label{eqn:sum(uLapv)<=|u|.|v|}
    \sum_{x \in \verts} |u(x) \Lap v(x)| \leq \sqrt2 \; \|u\|_\cond \cdot \|v\|_\energy.
  \end{align}
  \begin{proof}
    Apply the Schwarz inequality twice, first with respect to the $x$ summation, then with respect to $y$:
    \linenopax
    \begin{align*}
      \sum_{x \in \verts} |u(x) \Lap v(x)|
      &= \sum_{x,y \in \verts} \left|\sqrt{c_{xy}} u(x)\sqrt{c_{xy}} (v(x)-v(y))\right| \\
      &\leq \sum_{y \in \verts} \left(\sum_{x \nbr y} c_{xy} |u(x)|^2\right)^{1/2}
        \left(\sum_{x \nbr y} c_{xy}|v(x)-v(y)|^2\right)^{1/2} \\
      &\leq \left(\sum_{x,y \in \verts} c_{xy} |u(x)|^2\right)^{1/2}
        \left(\frac22\sum_{x,y \in \verts} c_{xy}|v(x)-v(y)|^2\right)^{1/2},
    \end{align*}
    and the resulting inequality retroactively justifies the implicit initial Fubination.
  \end{proof}
\end{lemma}

\begin{defn}\label{def:J-quotient-inclusion-map}
  For $u \in \spn\{\gd_x\} \ci \ell^2(\cond)$, define a linear functional $\gx_u$ on $\HE$ by
  \linenopax
  \begin{align}\label{eqn:def:gx_u}
    \gx_u(v) := \sum_{x \in \verts} u(x) \Lap v(x)
  \end{align}
  Then $\gx_u$ is continuous because $|\gx_u(v)| \leq \|u\|_\cond \cdot \|v\|_\energy$ by Lemma~\ref{thm:sum(uLapv)<=|u|.|v|}, whence Riesz's lemma gives a $w \in \Fin$ for which $\gx_u(v) = \la w, v\ra_\energy$ holds for every $v \in \Fin$.
  Let $J:\ell^2(\cond) \to \HE$ denote the map which sends $u \mapsto w$, i.e., the map defined by
  \linenopax
  \begin{align}\label{eqn:def:J}
    \la Ju, v \ra_\energy = \gx_u(v).
  \end{align}
\end{defn}

Definition~\ref{def:J-quotient-inclusion-map} allows one to see directly that $J\gd_x = [\gd_x]$:
\linenopax
\begin{align*}
  \la J\gd_x, v\ra_\energy
  &= \sum_{y \in \verts} \gd_x(y) \Lap v(y)
   = \Lap v(x)
   = \la \gd_x, v\ra_\energy,
   \q\text{for all } v \in \HE.
\end{align*}
This idea is the reason for Definition~\ref{def:J-quotient-inclusion-map} and also Theorem~\ref{thm:l2c-in-HE}. It is also easy to see that $\|\gd_x\|_\cond^2 = \cond(x) = \|\gd_x\|_\energy^2$, although the two norms $\|\cdot\|_\cond$ and $\|\cdot\|_\energy$ are clearly different in general. In fact, if $\gf = \sum_{x \in F} \gx_x \gd_x \in \spn\{\gd_x\}$ (so $F$ is finite), then one may easily compute
\begin{align*}
  \|\gf\|_\cond^2 = \sum_{x \in F} \cond(x) |\gx|^2,
  \q\text{whereas}\q
  \|\gf\|_\energy^2 = \|\gf\|_\cond^2 - \sum_{x \in F} \sum_{y \nbr x} \cond_{xy} \gx_x \gx_y.
\end{align*}

\begin{theorem}\label{thm:l2c-in-HE}
  The map $J$ is the quotient map induced by the equivalence relation $u\simeq v$ iff $u-v=const$, and gives a continuous embedding of $\ell^2(\cond)$ into \Fin with
  \linenopax
  \begin{align}\label{eqn:l2c-in-HE}
    \|Ju\|_\energy \leq  \sqrt2 \, \|u\|_\cond,
    \qq \forall u \in \ell^2(\cond).
  \end{align}
  Furthermore, the closure of $\ran J$ with respect to \energy is \Fin.
  \begin{proof}
    The formulation of $J$ in \eqref{eqn:def:J} gives
    \linenopax
    \begin{align*}
      \la Ju, v_x \ra_\energy
       = \gx_u(v_x)
       = \sum_{x \in \verts} u(y) \Lap v_x(y)
       = \sum_{x \in \verts} u(y) (\gd_x - \gd_o)(y)
       = u(x) - u(o).
    \end{align*}
    This shows that $J$ is the quotient map as claimed.
    The bound \eqref{eqn:l2c-in-HE} follows immediately upon combining \eqref{eqn:sum(uLapv)<=|u|.|v|} with \eqref{eqn:def:gx_u}.
    Now let $w = Ju$ for any $u \in \ell^2(\cond)$ and apply $\gx_u$ to $v = f_x = \Pfin v_x \in \Fin$ to get
    \linenopax
    \begin{align*}
      w(x) - w(o)
      &= \la f_x, w\ra_\energy
      = \gx_u(f_x)
      = \sum_{y \in \verts} u(y) (\gd_x-\gd_o)(y)
      = u(x) - u(o).
    \end{align*}
    Since $\{f_x\}$ is thus a reproducing kernel for any element of $\ran J$, this shows that $\ran J \ci \Fin$, and hence
    \linenopax
    \begin{align*}
      \left| \la Ju, v\ra_\energy\right| = |\gx_u(v)| \leq \sqrt2 \, \|u\|_\cond \cdot \|v\|_\energy
      \q\implies\q
      \|Ju\|_\energy \leq \sqrt2 \, \|u\|_\cond.
    \end{align*}
    The \energy-closure of $\ran J$ is equal to \Fin because $\ran J$ contains $\spn\{\gd_x\}$.
  \end{proof}
\end{theorem}

\begin{comment}\label{thm:sum(uLapv)-conv-absolutely}
  For $u \in \ell^2(\cond)$ and $v \in \HE$, $\sum_{x \in \verts} u(x) \Lap v(x)$ is absolutely convergent with
  \linenopax
  \begin{align}\label{eqn:gx_u-is-abs-conv}
    \sum_{x \in \verts} |u(x) \Lap v(x)|

    \leq \sqrt2 \; \|u\|_\cond \cdot \|v\|_\energy.
  \end{align}
  \begin{proof}
    Two applications of the Schwarz inequality yield
    \linenopax
    \begin{align*}

      \sum_{y \in \verts} \sum_{x \in \verts} |u(x) \cond_{xy} (v(x)-v(y))|
      &\leq \sum_{y \in \verts} \left(\sum_{x \in \verts} \cond_{xy} |u(x)|^2 \sum_{x \in \verts} \cond_{xy} |v(x)-v(y)|^2\right)^{1/2} \\
      &\leq \left(\sum_{x \in \verts} \sum_{y \in \verts} \cond_{xy} |u(x)|^2 \right)^{1/2} \left(\frac22\sum_{x \in \verts} \sum_{y \in \verts} \cond_{xy} |v(x)-v(y)|^2\right)^{1/2} \\
      &\leq \sqrt2 \; \|u\|_\cond \cdot \|v\|_\energy,
    \end{align*}
    so that \eqref{eqn:gx_u-is-abs-conv} follows by Fubini's theorem.

  \end{proof}
\end{comment}

\begin{lemma}\label{thm:adjJ-and-Prob}
  The adjoint map $J^\ad:\HE \to \ell^2(\cond)$ is given by
  \begin{align}\label{eqn:adjJ-and-Prob}
    J^\ad u = u - \Prob u,
  \end{align}
  where \Prob is the probabilistic transition operator defined in \eqref{eqn:def:p(x,y)}.
  \begin{proof}
    First let $u \in \spn\{\gd_x\}$ and $v \in \HE$ and note that $\la Ju, v\ra_\energy = \la u, \Lap v\ra_\unwtd$ by \eqref{eqn:rem:energy-as-l2-inner-prod-with-Lap}. Then

    \linenopax
    \begin{align*}
     \la u, \Lap v\ra_\unwtd
      &= \sum_{x \in \verts} u(x) \Lap v(x)
      = \sum_{x \in \verts} u(x) \cond(x) \left(v(x) - \frac1{\cond(x)} \sum_{y \nbr x} \cond_{xy} v(y)\right),
    \end{align*}
    whence $\la Ju, v\ra_\energy = \la u, (\one-\Prob)v\ra_\cond$ on the subspace $\spn\{\gd_x\}$, which is dense in \Fin in the norm $\|\cdot\|_\energy$ and dense in $\ell^2(\cond)$ in the norm $\|\cdot\|_\cond$.
  \end{proof}
\end{lemma}

\begin{remark}\label{rem:proof-of-{thm:l2c-in-HE}-via-Harm}
  Lemma~\ref{thm:adjJ-and-Prob} provides another proof of Theorem~\ref{thm:l2c-in-HE}:
  \begin{proof}[Alternative proof of Theorem~\ref{thm:l2c-in-HE}]
    Suppose that $v \in \ran(J)^\perp \ci \HE$ so that $\la Ju, v\ra_\energy = 0$ for all $u \in \ell^2(\cond)$. Then
    \linenopax
    \begin{align*}
     \la Ju, v\ra_\energy
      &= \la u, J^\ad v\ra_\cond
       = \la u, v-\Prob v\ra_\cond,
       \q \forall u \in \ell^2(\cond)
    \end{align*}
    by \eqref{eqn:adjJ-and-Prob}, so that $v-\Prob v = 0$ in $\ell^2(\cond)$. Then recall that $v \in \Harm$ iff $\Lap v = 0$ iff $\Prob v = v$. This shows that $\ran(J)^\perp = \Harm$, and hence $\opclosure{\ran(J)}= \ran(J)^{\perp\perp} = \Harm^\perp = \Fin$.
  \end{proof}
\end{remark}

\begin{remark}\label{rem:defs-of-Lap}
  Many authors use $J^\ad J = \one-\Prob$ as the definition of the Laplace operator on $\ell^2(\cond)$. It is intriguing to note that for $v \in \HE$, one has $v-\Prob v \in \ell^2(\cond)$, even though it is quite possible that neither $v$ nor $\Prob v$ lies in $\ell^2(\cond)$ (for an extreme example, consider $v \in \Harm$).
  Furthermore, note that for every $v \in \HE$, one has
  \linenopax
  \begin{align}\label{eqn:v-tends-to-harmonicity-at-iy}
    \sum_{x \in \verts} \cond(x) |v(x) - \Prob v(x)|^2
    = \|J^\ad v\|_\cond^2
    \leq \sqrt2 \, \|v\|_\energy^2
    < \iy.
  \end{align}
  This obviously implies a bound $\cond(x) |v(x) - \Prob v(x)|^2 \leq B^2$, whence
  \linenopax
  \begin{align*}
    |v(x) - \Prob v(x)| \leq B \cond(x)^{-1/2}.
  \end{align*}
  Consequently, if $\{G_k\}$ is any exhaustion of \Graph, then $v \approx \Prob v$ on $G_k^\complm$ for large $k$ (in the sense of $\ell^2(\cond)$). Roughly, one can say that  any $v \in \HE$ tends to being a harmonic function at \iy, and the faster \cond grows, the better the approximation.
\end{remark}

\begin{cor}\label{thm:defective-corollary}
  If $\Lap u = -u$, then $\sum \frac1{\cond(x)} |u(x)|^2 < \iy$ and $u(x) = O(\negsp[5]\sqrt{\cond(x)})$, as $x \to \iy$.
  \begin{proof}
    Recall that a defect vector $u$ satisfies $\Lap u = -u \in \HE$ and hence $u-\Prob u = -\frac{1}{\cond} u$. The result follows by substituting the latter into \eqref{eqn:v-tends-to-harmonicity-at-iy}. This immediately implies a bound $\frac1{\cond(x)} |u(x)|^2 \leq B$, which gives the final claim.
  \end{proof}
\end{cor}

Recall
that \LapV denotes the closure of the Laplacian when taken to have the dense domain $V := \spn\{v_x\}_{x \in \verts \less\{o\}}$ of \emph{finite} linear combinations of dipoles.

\begin{cor}\label{thm:c-bdd-implies-Lap-selfadjoint-on-HE}
  If $\cond(x)$ is bounded on \verts and $\deg(x) < \iy$, then \LapV is essentially self-adjoint on \HE.
  \begin{proof}
    Suppose $w \in \dom \LapV^\ad$ satisfying $\Lap^\ad w = -w$. This means there is a $K$ (possibly depending on $w$) such that $|\la w, \Lap v\ra_\energy| \leq K \|v\|_\energy$ for all $v \in V$.

    Then for $u \in \ell^2(\cond)$ and $v \in \spn\{v_x\}$, set $\gx_u(v) = \sum_{x \in \verts} u(x) \Lap v(x)$. As in the proof of Theorem~\ref{thm:l2c-in-HE}, $\gx_u$ extends to a continuous linear functional on \HE, so applying it to $w$ gives
    \linenopax
    \begin{align*}
      \left|\sum_{x \in \verts} u(x) w(x)\right|
      = \left|\sum_{x \in \verts} u(x) (-w(x))\right|
      = \left|\sum_{x \in \verts} u(x) \Lap w(x)\right|
      = |\gx_u(w)|
      \leq \sqrt2 \, \|u\|_\cond \cdot \|w\|_\energy.
    \end{align*}
    However, if $\cond(x)$ is bounded by \uBd, then
    \linenopax
    \begin{align*}
      \|u\|_\cond
      = \left(\sum_{x \in \verts} \cond(x) |u(x)|^2 \right)^{1/2}
      \leq \uBd^{1/2} \|u\|_\unwtd.
    \end{align*}
    Combining the two displayed equations above yields the inequality
    \linenopax
    \begin{align*}
      \left|\sum u(x) w(x)\right|
      \leq \sqrt2 \, \uBd^{1/2} \|u\|_\unwtd \cdot \|w\|_\energy.
    \end{align*}
    This shows $u \mapsto \sum_{x \in \verts} u(x) w(x)$ is a continuous linear functional on $\ell^2(\cond)$, so that Riesz's lemma puts $w \in \ell^2(\unwtd)$. However, now that $w$ is a defect vector in $\ell^2(\unwtd)$, Theorem~\ref{thm:Laplacian-is-essentially-self-adjoint} applies, and hence $w=0$.
  \end{proof}
\end{cor}

\begin{defn}
 Let $\Lapc := \cond^{-1} \Lap = \one-\Prob = JJ^\ad$ denote the probabilistic Laplace operator on \HE, as in \eqref{eqn:probablistically-reweighted-laplacian}. Note that we abuse notation here in the suppression of the quotient map, so that $\one-\Prob$ denotes an operator on \HE and a mapping $\HE \to \ell^2(\cond)$.
\end{defn}

\begin{cor}
  For any $v \in \HE$, \Lapc is contractive on \HE and $(\one-\Prob)v \in \ell^2(\cond)$ with
  \linenopax
  \begin{align*}
   \|(\one-\Prob)v\|_\energy \leq \|v\|_\energy.
  \end{align*}
  \begin{proof}
    Since $J$ is contractive, it follows that $J^\ad$ is contractive by basic operator theory; this is a consequence of the polar decomposition applied to $J$.

    Then $\Lapc = JJ^\ad$ is certainly continuous with $\|(\one-\Prob)v\|_\energy = \|JJ^\ad v\|_\energy \leq \sqrt2 \, \|J^\ad v\|_\cond \leq 2 \|v\|_\energy$.
  \end{proof}
\end{cor}

\begin{lemma}\label{thm:Lap-not-Hermitian-on-l2(c)}
  \Lapc is Hermitian if and only if $\cond(x)$ is a constant function on the vertices.
  \begin{proof}
   This can be seen by computing the matrix representation of \Lapc with respect to the ONB $\{\frac{\gd_x}{\sqrt{\cond(x)}}\}$, in which case the \nth[(x,y)] entry is
    \linenopax
    \begin{align*}
      [M_{\Lapc}]_{x,y}
      = \left\la \frac{\gd_x}{\sqrt{\cond(x)}}, \Lap \frac{\gd_y}{\sqrt{\cond(y)}} \right\ra_\cond
      &= \sum_{z \in \verts} \cond(z)\frac{\gd_x(z)}{\sqrt{\cond(x)}} \left(\frac{\cond(y)\gd_y(z)}{\sqrt{\cond(y)}} - \sum_{t \nbr y} \cond_{ty} \frac{\gd_t(z)}{\sqrt{\cond(y)}} \right) \\
      &= \sum_{z \in \verts} \left(\frac{\cond(z)\gd_x(z)}{\sqrt{\cond(x)}} \frac{\cond(y)\gd_y(z)}{\sqrt{\cond(y)}} - \frac{\cond(z)\gd_x(z)}{\sqrt{\cond(x)}}\sum_{t \nbr y} \cond_{ty} \frac{\gd_t(z)}{\sqrt{\cond(y)}} \right) \\
      &= \cond(x)\gd_{xy} - \sqrt{\cond(x)} \sum_{t \nbr y} \cond_{ty} \frac{\gd_t(x)}{\sqrt{\cond(y)}} \\
      &= \cond(x)\gd_{xy} - \sqrt{\cond(x)} \sum_{y \nbr x} \cond_{xy} \frac{\gd_y}{\sqrt{\cond(y)}},
    \end{align*}
    which is not symmetric in $x$ and $y$. We used $\Lap \gd_y = \cond(y)\gd_y - \sum_{t \nbr y} \cond_{ty} \gd_t$, which follows easily from Lemma~\ref{thm:dx-as-vx}.
  \end{proof}
\end{lemma}

\version{}{
\begin{lemma}
\marginpar{Removed until we can fix the proof}
  Let $u \in \HE$. Then $u \in \dom \LapV^\ad$ if and only if $\Lap u \in \ell^2(\cond)$.
  \begin{proof}
    By definition, $u \in \dom \LapV^\ad$ iff there is a $K$ (possibly depending on $u$) such that
    \linenopax
    \begin{align*}
      |\la u, \Lap v\ra_\energy|
      \leq K \|v\|_\energy, \qq \forall v \in \spn\{v_x\}.
    \end{align*}
    However,
    \linenopax
    \begin{align*}
      |\la u, \Lap v\ra_\energy|
      =
    \end{align*}
  \end{proof}
\end{lemma}
}

\begin{theorem}\label{thm:Prob-self-adjoint-in-[-1,1]}
  (i) As an operator on $\ell^2(\cond)$, $\Prob = \id - J^\ad J$ is self-adjoint with $-\id \leq \Prob \leq \id$.

  (ii) As an operator on $\HE$, $\Prob = \id -J J^\ad$ is self-adjoint with $-\id \leq \Prob \leq \id$.
  \begin{proof}
    (i) Since $J$ is bounded and hence closed, a theorem of von Neumann implies $J^\ad J$ is self-adjoint. Then
    \linenopax
    \begin{align*}
      \la u, \Prob u \ra_\cond
      &= \la u, (\id - J^\ad J)u \ra_\cond
       = \la u, u \ra_\cond - \la Ju, Ju \ra_\energy
       = \|u\|_\cond^2 - \|Ju\|_\energy^2.
    \end{align*}
    Since $\|Ju\|_\energy^2 \leq 2 \|u\|_\cond^2$ by \eqref{eqn:l2c-in-HE}, this establishes $-\|u\|_\cond^2 \leq \la u, \Prob u\ra_\cond \leq \|u\|_\cond^2$.

    (ii) By the same argument as in part (i), $JJ^\ad$ is self-adjoint. Then $\|JJ^\ad\| = \|J^\ad J\|$ gives the same bound for \Prob on \HE.
  \end{proof}
\end{theorem}

\begin{remark}\label{rem:Prob-self-adjoint-by-comp}
  One can also see that \Prob is self-adjoint by independent arguments. For $\ell^2(\cond)$, we have $\la u, \Prob v\ra_\cond = \sum_{x,y} u(x) \cond_{xy} v(y) = \la \Prob u, v\ra_\cond$, and for \HE, we have
  \linenopax
  \begin{align}\label{eqn:Prob-computation-1}
    \la \Prob v_x,v_y\ra_\energy
    &= \la v_x - \cond^{-1}(\gd_x-\gd_o),v_y\ra_\energy \notag \\%- \la v_x, v_y - \cond^{-1}(\gd_y-\gd_o)\ra_\energy \\
    &= \la v_x,v_y\ra_\energy-\cond^{-1}(\gd_x-\gd_o)(y) + \cond^{-1}(\gd_x-\gd_o)(o) \notag \\%- \cond^{-1}(\gd_y-\gd_o(x) +\cond^{-1}(\gd_y-\gd_o(o)\\
    &= \la v_x,v_y\ra_\energy - \tfrac1{\cond(o)} - \tfrac{\gd_{xy}}{\cond(x)},
  \end{align}
  where $\gd_{xy}$ is the Kronecker delta.
\end{remark}

\begin{remark}\label{rem:von-Neumann's-ergodic-theorem}
  von Neumann's ergodic theorem implies that
  \linenopax
  \begin{align*}
    \lim_{N \to \iy} \frac1N \sum_{n=1}^N \Prob^n u = \Phar u.
  \end{align*}
  In general, it is difficult to know when one has the stronger result that $\Prob^n u \to \Phar u$. A Perron-Frobenius-Ruelle theorem would require an invariant measure with certain properties not satisfied in the present context. Nonetheless, one can see that $\lim_{n \to \iy} \Prob^n u$ lies in \Harm; this is shown in Theorem~\ref{thm:Prob-is-strictly-contractive-on-Fin}.
\end{remark}

\begin{lemma}\label{thm:Prob-removes-Lap(cinv)}
  For all $\gf \in \spn\{v_x\}$, one has
  \linenopax
  \begin{align}\label{eqn:Prob-removes-Lap(cinv)}
    \la \Prob \gf, \gf \ra_\energy
    = \|\gf\|_\energy^2 - \sum_{x \in \verts} \frac{|\Lap \gf(x)|^2}{\cond(x)}.
  \end{align}
  \begin{proof}
    For some finite set $F \ci \verts$ and $\gf = \sum_{x \in F} a_x v_x$,
    \linenopax
    \begin{align*}
      \la \Prob \gf, \gf \ra_\energy
      &= \sum_{x,y \in F} a_x a_y \la v_x, v_y\ra_\energy
        - \frac1{\cond(o)} \left|\sum_{x \in \verts} a_x \right|^2
        -\sum_{x \in \verts} \frac{\left| a_x \right|^2}{\cond(x)} \\
      &= \|\gf\|_\energy^2
        - \frac1{\cond(o)} \left|\sum_{x \in \verts} \Lap \gf(x) \right|^2
        - \sum_{x \in \verts} \frac{|\Lap \gf(x)|^2}{\cond(x)},
    \end{align*}
    where we have used \eqref{eqn:Lapu(y)-is-the-yth-coord} and \eqref{eqn:Prob-computation-1} for the last step. Then Theorem~\ref{thm:sum(Lap v)=0} shows that the middle sum vanishes, and we have \eqref{eqn:Prob-removes-Lap(cinv)}.
  \end{proof}
\end{lemma}

\begin{cor}\label{thm:Lapsumming-is-contractive-on-V}
  For $\gf \in \spn\{v_x\}$, $\sum_{x \in \verts} \frac{|\Lap \gf(x)|^2}{\cond(x)}
    \leq 2 \|\gf\|_\energy^2$.
  \begin{proof}
    Apply \eqref{eqn:Prob-removes-Lap(cinv)} to the bound $-\id \leq \Prob \leq \id$ from Theorem~\ref{thm:Prob-self-adjoint-in-[-1,1]}.
  \end{proof}
\end{cor}

\begin{theorem}\label{thm:Prob-is-strictly-contractive-on-Fin}
  \Prob is strictly contractive on \Fin.
  \begin{proof}
    Note that no harmonic functions lie in $\spn\{v_x\}$ (by Lemma~\ref{thm:E(u,v)=<u,Lapv>-on-spn{vx}}, for example), so $\sum_{x \in \verts} \frac{|\Lap \gf(x)|^2}{\cond(x)} > 0$.

  \end{proof}
\end{theorem}

For Theorem~\ref{thm:prob-bounded-on-ell2}, we will need to consider iterates $\Prob^n$ of the probabilistic transition operator, the induced conductances $\cond_{xy}^{(n)}$, and the corresponding energy spaces $\HE(\cond^{(n)})$. From
\linenopax
\begin{align*}
  (\Prob^2 u)(x)
  = \Prob \left(\sum_{y \nbr x} p(x,y) u(y)\right)
  = \sum_{y \nbr x} p(x,y) \sum_{z \nbr y} p(y,z) u(z)
  = \sum_{y \nbr x} \sum_{z \nbr y} \frac{\cond_{xy}}{\cond(x)} \frac{\cond_{yz}}{\cond(y)}  u(z),
\end{align*}
we take $p^2(x,y) = \sum_{z \nbr x,y} p(x,z) p(z,y)$ and define $\cond^{(2)}_{xy} := \cond(x) p^2(x,y)$. Iterating, we obtain $\cond^{(n)}$ and the spaces $ \HE^{(n)} :=\{u:\verts \to \bC \suth \energy^{(n)}(u) < \iy\}$ where
\linenopax
\begin{align*}
  \energy^{(n)}(u) := \frac12 \sum_{x,y \in \verts} \cond^{(n)}_{xy} |u(x)-u(y)|^2.
\end{align*}

\begin{lemma}\label{thm:sums-invariant-under-iteration-of-P}
  For each $n=1,2,\dots$, one has $\cond(x) = \sum_{y \in \verts} \cond^{(n)}_{xy}$.
  \begin{proof}
    From above, $\sum_{y \in \verts} \cond^{(2)}_{xy} = \cond(x) \sum_{y \in \verts} p^{(2)}(x,y) = \cond(x)$ shows that the sum at $x$ does not change. The case for general $n$ follows by iterating.
  \end{proof}
\end{lemma}

In the proof of the following theorem, we write $\Lap_n := \cond(\id - \Prob^n)$, which is \emph{not} the same as $\Lap^n$. Also, we abuse notation and write $\ell^2(\cond)$ for $J(\ell^2(\cond))$, in accordance with Theorem~\ref{thm:l2c-in-HE}.

\begin{theorem}\label{thm:prob-bounded-on-ell2}
  \Prob is densely defined on \HE with
  \linenopax
  \begin{align}\label{eqn:prob-bounded-on-ell2}
    \|\Prob u\|_\cond \leq \|u\|_\cond + \|u\|_\energy,
    \qq \forall u \in J(\ell^2(\cond)).
  \end{align}
  In fact, $\|\Prob^{(n)} u\|_\cond \leq \|u\|_\cond + \|u\|_{\energy^{(n)}}$, for every $n \geq 1$.
  \begin{proof}
    Note that it immediately follows from Lemma~\ref{thm:sums-invariant-under-iteration-of-P} that $\ell^2(\cond) \ci \bigcap_n \HE^{(n)}$, and hence that there is a $J_n:\ell^2(\cond) \to \HE^{(n)}$ for which
    \linenopax
    \begin{align*}
      \la J_n u, v\ra_{\energy^{(n)}}
      &= \sum_{x \in \verts} u(x) \Lap_n v(x)
       = \sum_{x \in \verts} u(x) \cond(x)\left(v(x) - \Prob^n v(x)\right)
       = \la u, v \ra_\cond - \la u, \Prob^n v \ra_\cond.
    \end{align*}
    Observe that the rearrangement in the last step is justified by the convergence of $\la J_n u, v\ra_{\energy^{(n)}}$ and $\la u, v \ra_\cond$. The Schwarz inequality gives $\Prob^n v \in \ell^2(\cond)$, and
    \linenopax
    \begin{align*}
      \left|\la u, \Prob^n v \ra_\cond\right|
      \leq \left|\la u, v \ra_\cond\right| + \left|\la J_n u, v\ra_{\energy^{(n)}}\right|
      \leq \|u\|_\cond \|v\|_\cond + \|u\|_\cond \|v\|_{\energy^{(n)}}.
    \end{align*}
    This shows that $\Prob^nv$ is in the dual of $\ell^2(\cond)$ and hence in $\ell^2(\cond)$. By Riesz's theorem, $\|\Prob u\|_\cond$ is the best constant possible in the above inequality, and so \eqref{eqn:prob-bounded-on-ell2} follows.
  \end{proof}
\end{theorem}

\section{Remarks and references}
\label{sec:Remarks-and-References-ell2-of-Lap-and-Trans}

The material above is an assortment of results on spectral theory for the operators from Chapter~\ref{sec:Lap-on-HE}.

Of the results in the literature of relevance to the present chapter, the references \cite{Dod06, DuRo08, Sto08, DMS07, BaBa05, Chu07, ChRi06, BiLeSt07} are especially relevant. The reader may also wish to consult \cite{Nel73a}, \cite{vN32a}, and good background references include \cite{DuSc88, ReedSimonII, Arveson:spectral-theory, Chu01, Lax-Phillips}.

\version{}{
\section{The spectral Laplacian and transfer operator}
\label{sec:spectral-spaces}

One disadvantage of \Lapc is that it is not self-adjoint. In this section, we consider a renormalized version of \Lap which is defined to as to remain self-adjoint.

\subsection{The spectral transfer operator on $\ell^2(\cond)$}
\label{sec:The-spectral-transfer-operator-on-L2}
In this section, we consider the \emph{spectral Laplacian} $\Lapsp = \cond^{-1/2} \Lap \cond^{-1/2}$, given pointwise by
\linenopax
\begin{align}
  (\Lapsp v)(x)
  := \frac1{\sqrt{\cond(x)}} \sum_{y \nbr x}
  \cond_{xy} \left(\frac{v(x)}{\sqrt{\cond(x)}} - \frac{v(y)}{\sqrt{\cond(y)}}\right) ,
    \label{eqn:spectral-laplace-operator}
\end{align}
and the associated spectral transfer operator $\Transp = \id - \Lapsp = \cond^{-1/2} \Trans \cond^{-1/2}$. Recall that with respect to the ONB $\left\{\frac{\gd_x}{\sqrt{\cond(x)}}\right\}$, the operator \cond is the diagonal matrix with entries $\cond(x)$.

It is not usually true that transfer operators are self-adjoint, so the following result is a bit of a surprise.

\begin{theorem}\label{thm:spectral-transfer-operator-is-Hermitian-on-L2}
  The transfer operator is Hermitian, as an operator on on $\ell^2(\cond)$.
  \begin{proof}
    Using Theorem~\ref{thm:transfer-operator-is-Hermitian-on-L2c} for the third equality,
    \linenopax
    \begin{align*}
      \la u, \Transp v\ra_\cond
      = \la u, \cond^{-1/2} \Trans \cond^{-1/2} v \ra_\cond
      &= \la \cond^{-1/2} u, \Trans \cond^{-1/2} v \ra_\unwtd \\
      &= \la \Trans \cond^{-1/2} u, \cond^{-1/2} v \ra_\unwtd \\
      &= \la \Transp u, v \ra_\spectral.
      \qedhere
    \end{align*}
  \end{proof}
\end{theorem}

Unfortunately, $\Trans_\spectral$ may not be essentially self-adjoint, as shown by Example~\ref{exm:banded-nonselfadjoint-matrix}; see also \cite{vN32a,Rud91,DuSc88}. In view of the fact that
\linenopax
\begin{align*}
  \energy(u) = \la u, u\ra_{\energy} = \la u, \Lap u\ra_\spectral \geq 0,
\end{align*}
self-adjointness follows automatically.

\begin{theorem}\label{thm:transfer-operator-is-bounded-on-L2}
  The transfer operator $\Trans_\spectral:\ell^2(\spectral) \to \ell^2(\spectral)$ is bounded if and only if $\cond(x)$ is bounded, i.e., iff the Powers bound \eqref{eqn:def:power-bound} is satisfied.
  \begin{proof}
    Apply conjugation.
  \end{proof}
\end{theorem}

\begin{theorem}\label{thm:transfer-operator-is-compact-on-L2}
  The transfer operator $\Trans_\spectral:\ell^2(\spectral) \to \ell^2(\spectral)$ is compact if and only if $\cond(x) \limas{x} 0$ in $\ell^2$, i.e., iff $\|\cond(x)\|_2$ vanishes at \iy.
  \begin{proof}
    \bwd Consider any nested sequence $\{\Graph_k\}$ of finite connected subsets of \Graph, with $\Graph = \bigcup \Graph_k$, and the restriction of the transfer operator to these subgraphs, given by
    \linenopax
    \begin{align*}
      \Trans_n := P_n \Trans P_n,
    \end{align*}
    where $P_n$ is projection to $\Graph_n$. Then for $D_n := \Trans - \Trans_n$, consider
    \linenopax
    \begin{align}\label{eqn:norm-estimate-on-trans-approximation-L2}
      \|D_n\|
      = \left\|\begin{array}{cc}
          0 & P_n \Trans P_n^\perp \\
          P_n^\perp \Trans P_n & P_n^\perp \Trans P_n^\perp \\
        \end{array}\right\|,
    \end{align}
    where the basis for the matrix coordinates is given by $\{\gd_{x_k} \cond(x_k)^{-1/2}\}_{k=1}^\iy$ for some enumeration of the vertices.
    We consider the estimate $\|D_n\| \leq \max \cond_{xy}$, ranging over the matrix entries of the three submatrices indicated in \eqref{eqn:norm-estimate-on-trans-approximation}. Since \Lap and hence \Trans is a banded matrix, it follows that $D_n$ is, too. Denote the width of the band of the row of $D_n$ corresponding to $x_k$ by $B_{x_k}$.

    Observe that any entry $\cond_{xy}$ appearing in submatrix of \eqref{eqn:norm-estimate-on-trans-approximation} corresponding to $P_n \Trans P_n^\perp$ (i.e., upper right) must satisfy the restrictions
    \linenopax
    \begin{align*}
      \cond_{xy} \in [P_n \Trans P_n^\perp]
      \q\implies\q y > n \text{ and } n \geq x > n-B_x,
    \end{align*}
    where $B_x$ is the bandwidth mentioned just above. Since $\|\cond(x)\|_2 = \sum_y \cond_{x,y}^2 \to 0$ as $y \to \iy$, one also has $\max_y \cond_{xy} \to 0$ as $y \to \iy$. This means that taking $n$ sufficiently large ensures all entries in $[P_n \Trans P_n^\perp]$ are less than a specified $\ge>0$.

    The other two submatrices have the restrictions
    \linenopax
    \begin{align*}
      \cond_{xy} \in [P_n^\perp \Trans P_n] &\q\implies\q y \leq n \text{ and } n < x \leq n+B_x, \text { and} \\
      \cond_{xy} \in [P_n^\perp \Trans P_n^\perp] &\q\implies\q y > n \text{ and } x > n,
    \end{align*}
    but the rest of the argument is the same.

    \fwd For the converse, suppose that \cond does not vanish at \iy. It follows that there is a sequence $\{x_n\}_{n=1}^\iy \ci \verts$ with $\cond(x_n) \geq \ge > 0$, and a path \cpath passing through each of them exactly once. By passing to a subsequence if necessary, is also possible to request that the sequence satisfies
    \linenopax
    \begin{align*}
      \vnbd(x_n) \cap \vnbd(x_{n+1}) = \es, \q\forall n,
    \end{align*}
    since the sequence need not contain every point of \cpath.
    Consider the orthonormal sequence $\left\{\gd_{x_n}\right\}$. We will show that $\left\{\Trans\gd_{x_n}\right\}$ contains no convergence subsequence:
    \linenopax
    \begin{align*}
      \Trans \gd_{x_n} - \Trans \gd_{x_m} &= \sum_{k \nbr n} \gx_{nk} \gd_{x_n} - \sum_{l \nbr m} \gx_{lm} \gd_{x_m} \\
      \|\Trans \gd_{x_n} - \Trans \gd_{x_m}\|^2 &= \sum_{k \nbr n} |\gx_{nk}|^2 + \sum_{l \nbr m} |\gx_{lm}|^2 \geq 2\ge^2.
    \end{align*}
    There are no cross terms in the final equality by orthogonality; $x_{n+1}$ was chosen to be far enough past $x_n$ that they have no neighbours in common.
  \end{proof}
\end{theorem}
}

config: arxiv


TITLE: Determinant's role on matrix-vector multiplication
QUESTION [1 upvotes]: I am trying to understand the role of determinant on matrix-vector multiplication. I am reading Math Insight in order to get some intuition regarding the determinant's role.
Let's take $2\times2$ matrix $A$ (as in the blog)
$$A = \begin{bmatrix} -2 & 0 \\ 0 & -2 \end{bmatrix}$$
According to the blog, the determinant's role can be seen by multiplying TWO vectors (that span a basis) by the matrix. And in this case the determinant shows how the square of the parallelogram formed by the original vectors and by the transformed vectors changes.
$$x=\begin{bmatrix} 1 \\ 0 \end{bmatrix}$$
$$y=\begin{bmatrix}
0 \\
1
\end{bmatrix}$$
The parallelogram formed by x and y has a square of 1. And the parallelogram formed by $Ax$ and $Ay$ has a square of $\det(A) = 4$.
But what the role of determinant when you have just one vector $x$? How the determinant influences the result of $Ax$?

REPLY [1 votes]: Quite honestly, I think the direct relation between determinant and matrix-vector multiplication that you are looking for does not exist. There will certainly be ways to relate the one to the other, and if anyone then it will be the smart people of this site who will go out of their way to find them, but I fear that most of these possibly indirect relations might not be satisfying for you.

As pointed out in the comments and the website you refer to, the determinant of a matrix affects volume. However for a single vector, this could mean all kinds of things. Take for example
$$
A = \begin{pmatrix} 9 & 0 \\ 0 & \tfrac19 \end{pmatrix}
$$
which has determinant $1$ as can be seen by how it maps the unit cube to the $9$ by $\frac19$ rectangle, which has area $1$ - but its effect on the two vectors
\begin{align*}
x_1&=\begin{pmatrix} 1\\0 \end{pmatrix} & x_2&=\begin{pmatrix} 0\\1\end{pmatrix}
\end{align*}
is quite different: One is stretched ninefold, the other is compressed ninefold.

The one thing you can say is that $\det(A)=0$ is equivalent to the existence of a vector $v$ with $Av=0$, and also equivalent to the fact that there is some vector $w$ such that $\forall v: Av \ne w$. This is because $\det(A)\ne0$ is equivalent to $A$ representing an invertible linear transformation.

To be more precise in my response, let me give you the following
Proposition. Let $\Bbbk$ be a field. For every nonzero $a\in\Bbbk$, every $n\in\Bbb N$, $n\ge 2$ and any two nonzero vectors $v,w\in\Bbbk^n$, there is a matrix $A\in\Bbbk^{n\times n}$ with $\det(A)=a$ and $Av=w$.
If you are interested, I can write a proof for this, but it might also be a good exercise. The prosaic phrasing of this proposition says that regardless of the determinant (excluding zero) you can have at least one vector that is mapped any way you like (except for sending it to zero).


TITLE: Why does the volumetric flow rate increase downstream for a jet?
QUESTION [0 upvotes]: I did a laboratory and the volumetric flow rate increased downstream and I don't understand why? Are there any sources that say why this is? I tried searching and I don't understand
The apparatus was the following https://i.imgur.com/a0SOoCP.png
It was measured with a pitot static tube connected to a manometer and velocity was found.

REPLY [2 votes]: This is due to a property called entrainment, in which the central high speed jet shares its kinetic energy with parcels of fluid at the margins of the jet, setting them in motion, which then share with other parcels farther off-axis to set them in motion, and so on. Downstream from the origin of the jet you then observe that it has spread itself out and now consists of a larger volume of air which is traveling slightly slower.


text:
\section{Bounded Orbits and Schmidt Games}
\label{section: schmidt games}

	We describe a version of Schmidt's games played on intervals of the real line.
	These games were introduced in~\cite{KleinbockWeiss-SchmidtExpanding,KleinbockWeiss-SchmidtSLn+m} in the general setting of connected Lie groups building on earlier ideas of Schmidt~\cite{Schmidt-Games}.

    Fix a compact interval $I_0 \subset \R$ and a positive constant $\s>0$.
    For each $t>0$, consider the following contraction of $\R$.
    \[ \Phi_t (x) = e^{-\s t} x \]
    Denote by $\mf{F} = \set{\Phi_t: t>0}$ this one-parameter semigroup of contractions.

    Now pick two real numbers $a,b >0$ and, following~\cite{KleinbockWeiss-SchmidtSLn+m,KleinbockWeiss-SchmidtExpanding}, we define a game,
played by two players Alice and Bob.
	First, Bob picks $t_0 >0$ and $x_1 \in \R$ so that the set $B_1 = \Phi_{t_0}(I_0) + x_1$ is contained in $I_0$.
	Then, Alice picks a translate $A_1$ of $\Phi_a(B_1)$ which
is contained in $B_1$, Bob picks a translate $B_2$ of $\Phi_b(A_1)$ which is contained in $A_1$, after that Alice picks a translate $A_2$ of $\Phi_a(B_2)$ which is contained in $B_2$, and so on.
	In other words, for $k \in \N$, we set
    \begin{equation} \label{eqn: t_k and s_k}
    	t_k = t_0 + (k-1)(a+b), \quad \text{and} \quad
        s_k = t_k + a.
    \end{equation}
    Thus, at the $k^{th}$ step of the game, Alice picks a translate $A_k$ of $\Phi_{s_k}(I_0)$ which is contained inside $B_k$. Then, Bob picks a translate $B_{k+1}$ of $\Phi_{t_{k+1}}(I_0)$ which is contained inside $A_k$.
    From compactness of $I_0$ and the definition of the sets $A_k$ and $B_k$, we see that the following intersections
    \begin{equation} \label{eqn: intersection}
    \bigcap_{k\geqslant 1} A_k = \bigcap_{k\geqslant 1} B_k
    \end{equation}
    are non-empty and consist of a single point. Note also that
    \begin{equation} \label{eqn: diameter of A_k and B_k}
    	\mathrm{diam}(A_k) = e^{-\s s_k} \mathrm{diam}(I_0), \quad
        \mathrm{diam}(B_k) = e^{-\s t_k} \mathrm{diam}(I_0).
    \end{equation}
    where the diameter of sets is with respect to the standard metric on $\R$.
    This game is referred to as the $\mathbf{(a,b)-}$\textbf{modified Schmidt game} on $I_0$.

    A subset $S \subseteq \R$ is said to be $\mathbf{(a,b)-}$\textbf{winning} if Alice can always pick her translates $A_k$ so that the point in the intersection~\eqref{eqn: intersection} always belongs to $S$, no matter how Bob picks his translates $B_k$.
    We say $S$ is $a$-winning if it is $(a,b)$-winning for all $b>0$ and winning if it is $a$-winning for some $a$.

    \input{BoundedTrajectories/CurveGames}