\chapter{Infinite trees}
\label{sec:tree-networks}

\headerquote{A great discovery solves a great problem but there is a grain of discovery in the solution of any problem. Your problem may be modest; but if it challenges your curiosity and brings into play your inventive faculties, and if you solve it by your own means, you may experience the tension and enjoy the triumph of discovery.}{---~G.~P\'{o}lya}


\begin{figure}
  \centering
  \scalebox{1.0}{\includegraphics{homogeneous-vs-symbolic.pdf}}
  \caption{\captionsize The homogeneous tree of degree 3 (left) and the binary tree from symbolic dynamics (right). The root of the tree is labeled $x_o$. If the grey branch is pruned from the homogeneous tree, the two become isomorphic.}
  \label{fig:homogeneous-vs-symbolic}
\end{figure}

The $n$-ary trees play an important role in symbolic dynamics, and they support a rich family of nontrivial harmonic functions of finite energy. These graphs are essentially homogeneous trees; the only difference is that the homogeneous tree has one more branch at the root, as can be seen from Figure~\ref{fig:homogeneous-vs-symbolic}. We use the latter examples as they are simpler yet still sufficient for our purposes, and because of our related interest in symbolic dynamics. However, almost all remarks extend to the homogeneous trees without effort; these examples are well-studied because of their close relationship with group theory (especially free groups). 
\version{}{\marginpar{Must include the case for varying \cond!}} Also, they provide an excellent testbed for studying the effects of varying \cond, and for illustrating several of our theorems.

A network whose underlying graph is a homogeneous tree always allows for the construction of a nontrivial harmonic function. In particular, \Fin is not dense in \HE by Lemma~\ref{thm:TFAE:Fin,Harm,Bdy} that these are equivalent.

\begin{remark}\label{rem:convention-negative-tree-branch}
  If the origin were removed from the binary tree, we adopt the convention that vertices in one component are ``positive'' and indices in the other are ``negative''. If the vertices are indexed with binary numbers (using the empty string $\es$ to denote the origin $o=x_\es$), then indices beginning with $1$ are positive and indices beginning with $0$ are negative.
\end{remark}

\begin{figure}
  \centering
  \scalebox{1.0}{\includegraphics{tree-repkernels.pdf}}
  \caption{\captionsize The reproducing kernel on the tree with $\cond = \one$. For a vertex $x$ which is adjacent to the origin $o$, this figure illustrates the elements $v_x$, $f_x = \Pfin v_x$, and $h_x = \Phar v_x$; see Example~\ref{exm:binary-tree:reproducing-kernel}. }
  \label{fig:tree-repkernels}
\end{figure}

\begin{figure}
  \centering
  \scalebox{1.0}{\includegraphics{tree-repkernel-approximants.pdf}}
  \caption{\captionsize Approximants to the reproducing kernel on the tree with $\cond = \one$; see Example~\ref{exm:binary-tree:reproducing-kernel}.}
  \label{fig:tree-repkernel-approximants}
\end{figure}

\begin{exm}[The reproducing kernel on the tree]
  \label{exm:binary-tree:nontrivial-harmonic}
  \label{exm:binary-tree:reproducing-kernel}
  Let $(\sT,\one)$ be the binary tree network in Figure~\ref{fig:homogeneous-vs-symbolic} with constant conductances. Figure~\ref{fig:tree-repkernels} depicts the embedded image of a vertex $v_x$, as well as its decomposition in terms of \Fin and \Harm. We have chosen $x$ to be adjacent to the origin $o$; the binary label of this vertex would be $x_1$.

  In Figure~\ref{fig:tree-repkernels}, numbers indicate the value of the function at that vertex; artistic liberties have been taken. If vertices $s$ and $t$ are the same distance from $o$, then $|f_x(s)|=|f_x(t)|$ and similarly for $h_x$. Note that $h_x$ provides an example of a nonconstant harmonic function in \HE. Another key point is that $h_x \notin \ell^2$, see Corollary~\ref{thm:nontrivial-harmonic-fn-is-not-in-L2}. It is easy to see that $\lim_{z \to \pm\iy} h_x(z) = \frac12 \pm \frac12$, whence $h_x$ is bounded. 
  
  For $f_x = \Pfin v_x$ of Figure~\ref{fig:tree-repkernels}, the illustration of $f_x^{(k)}$ in Figure~\ref{fig:tree-repkernel-approximants} is the projection of $v_x$ (or $f_x$) to $\spn\{\gd_x \suth x \in G_k\}$, where $G_k$ consists of all vertices within $k$ steps of $o$. The lines at the right side of each figure just indicate that the function is constant on the remainder of the graph (at value 0 or 1); in particular, note that $f_x^{(k)}(y) = 0$ for every vertex $y$ which is at least $k+1$ steps from the origin. Also, observe that 
  \[\Lap f_x^{(k)} = \gd_x - \gd_y + \sum_{s \in \bd G_{k+1}^+} \frac{\gd_s}{2^{k+2}-2} - \sum_{t \in \bd G_{k+1}^-} \frac{\gd_t}{2^{k+2}-2},\]
  where $\bd G_{k+1}^+$ is the subset of $\bd G_{k+1}$ that lies on the positive branch, etc. It is interesting to note that if one were to identify all the vertices of $\bd G_{k+1} = \bd G_{k+1}^+ \cup \bd G_{k+1}^+$, then $f_x^{(k)}$ would become harmonic at this new vertex. Observe also that $h_x^{(k)} = v_x - f_x^{(k)}$ is its orthogonal complement and is harmonic everywhere except on $\bd G_{k+1}$.
\end{exm}


\begin{exm}[A function of finite energy which is not approximable by \Fin]
  \label{exm:binary-tree:nonapproximable}  
  We continue to refer to in Figure~\ref{fig:tree-repkernel-approximants}. Since $f_x^{(k)} \in \Fin$ and it is easy to see that $\|f_x-f_x^{(k)}\|_\energy \to 0$ and that $\Lap f_x = \gd_x - \gd_y$, this approximation verifies that $f_x = \Pfin v_x$. It also shows that $\min_{f \in \Fin} \|v_x - f\|_\energy = \frac14$.
\end{exm}


\begin{exm}[A monopole which is not a ``dipole at infinity'']
  \label{exm:monopole-on-binary-tree}
  Let $(\sT,\one)$ be the binary tree network in Figure~\ref{fig:homogeneous-vs-symbolic} with constant conductances.  Let $|x|$ be the number of edges in the path connecting $x$ to $o$. Define a function
  \linenopax
  \begin{equation}\label{eqn:monopole-on-binary-tree}
    w_o(x) = 1-\frac1{2^{|x|}},
  \end{equation}
  so that essentially $w_o = 2|h_x-\frac12|$ for $h_x$ of Example~\ref{exm:binary-tree:reproducing-kernel}. It is easy to check that $\Lap w_o = -\gd_o$ so that $w_o$ is a monopole at the root $o$. To see that $w_o \in \HE$,
  \begin{align*}
    \energy(w_o)
    &= 2 \sum_{n=0}^\iy 2^n \left(\left(1-\frac1{2^{n}}\right) - \left(1-\frac1{2^{n+1}}\right)\right)^2 \\
    &= 2 \sum_{n=0}^\iy 2^n \left(\frac1{2^{n+1}}\right)^2 \\
    &= \frac12 \sum_{n=0}^\iy \frac1{2^n} \\
    &= 1.
  \end{align*}

  However, $w_o$ is not a ``dipole at infinity'' in the sense that there is no sequence $\{x_n\}$ of distinct and successively adjacent vertices for which $\{v_{x_n}\}$ converges to $w_o$ (this is in contrast to the integer lattices \bZd, $d \geq 3$). Observe that $R^F(x,y)$ coincides with shortest-path distance on this network (as it does on any tree). If $\{x_n\}$ is a sequence tending to \iy (i.e., for any $N$, there is an $n$ such that $x_n$ is more than $n$ steps from $o$ for all $n \geq N$), then $\energy(v_{x_n}) = R^F(x_n,o) = n$, so that $w_o$ is not a limit of a sequence of dipoles. 
  
  Of course, since $\{v_x\}$ is dense in \HE, $w_o$ is the limit of \emph{linear combinations} of dipoles. In fact, let $\bd G_k = \{x \in \sT \suth R(x,o) = k\}$ as before. Then
  \linenopax
  \begin{align*}
    w_o(x) = \lim_{k \to \iy} \sum_{z \in \bd G_k} \frac{v_z}{2^k}.
  \end{align*}
\end{exm}

\begin{exm}[A function with nonvanishing boundary sum]
  \label{exm:nonvanishing normal derivatives}
  In Theorem~\ref{thm:E(u,v)=<u,Lapv>+sum(normals)}, we showed
  \linenopax
  \[\la u, v \ra_\energy = \lim_{k \to \iy} \sum_{x \in \inn \Graph_k} u(x) \Lap v(x)
      + \lim_{k \to \iy} \sum_{x \in \bd \Graph_k} u(x) \dn v(x).\]
  Let $w_o(x) = 1-\frac1{2^{|x|}}$ be the monopole from Example~\ref{exm:monopole-on-binary-tree}. With $G_k := \{x \suth |x| \leq k\}$, we have 
  \begin{align*}
    \dn{w_o}(x) = \left(1-\frac1{2^{k}}\right) - \left(1-\frac1{2^{k-1}}\right) = \frac1{2^{k}},
    \q \text{ for } x \in \bd G_k = \{x \suth |x| = k\}.
  \end{align*}
  Since $\Lap w = -\gd_o$, we have $\sum_{\Graph_k} w_o(x) \Lap w_o(x) = -w(o)$, for each $k$, and the energy of $w_o$ is
  \begin{align*}
    \energy(w_o) 
     = \la w_o, w_o\ra_\energy
    &= -\left(1-\frac1{2^{0}}\right)
      + \lim_{k \to \iy} \sum_{x \in \bd \Graph_k} \left(1-\frac1{2^{k}}\right)\frac1{2^{k}} = 1.
    
    
  \end{align*}
  
  For $h_x$, the harmonic function with $\energy(h_x)=\frac14$ in Example~\ref{exm:binary-tree:nontrivial-harmonic}, this becomes
  \linenopax
  \[\energy(h_x,h_x) = 
    \lim_{k \to \iy} \sum_{x \in \bd \Graph_k} h_x(x) \dn{h_x}(x)
    =\frac14.\]
  In fact, one can obtain this by computing the boundary term directly: each of the $2^{k-1}$ vertices in $\bd \Graph_k^+$ is connected by a single edge to $G_k$, and similarly for the $2^{k-1}$ vertices in $\bd \Graph_k^-$, so
  \linenopax
  \begin{align*}
    \sum_{y \in \bd \Graph_k} h_x(y) \dn{h_x}(y)
    &= 2^{k-1} \frac{2^{k+1}-1}{2^{k+1}} \cdot \frac{1}{2^{k+1}}
     + 2^{k-1} \frac{1}{2^{k+1}} \cdot \frac{-1}{2^{k+1}}
    = \frac14 \left(1-\frac1{2^k}\right).
  \end{align*}
\end{exm}


\begin{exm}[The tree supports many nontrivial harmonic functions]
  \label{exm:a-forest-of-binary-trees}
  We can use $h_x$ of Example~\ref{exm:binary-tree:nontrivial-harmonic} to describe an infinite forest of mutually orthogonal harmonic functions on the binary tree. Let $z \in \Graph$ be represented by a finite binary sequence, as discussed in Remark~\ref{rem:convention-negative-tree-branch}. Define a morphism (cf.~Definition~\ref{def:ERN-morphism}) $\gf_z:\Graph \to \Graph$ by prepending, i.e., $\gf_z(x) = zx$. This has the effect of ``rigidly'' translating the the tree so that the image lies on the subtree with root $z$. Then $h_z := h_x \comp \gf_z$ is harmonic and is supported only on the subtree with root $z$. The supports of $h_{z_1}$ and $h_{z_2}$ intersect if and only if $\Im(\gf_{z_i}) \ci \Im(\gf_{z_j})$. For concreteness, suppose it is $\Im(\gf_{z_1}) \ci \Im(\gf_{z_2})$. If they are equal, it is because $z_1=z_2$ and we don't care. Otherwise, compute the dissipation of the induced currents
  \linenopax
  \begin{align*}
    \la \drp h_{z_1}, \drp h_{z_2} \ra_\diss
    = \tfrac12 \negsp \sum_{(x,y) \in \gf_{z_1}(\edges)} \negsp
      \ohm(x,y) \drp h_{z_1}(x,y), \drp h_{z_2}(x,y).
  \end{align*}
  Note that $\drp h_{z_2}(x,y)$ always has the same sign on the subtree with root $z_1 \neq o$, but $\drp h_{z_1}(x,y)$ appears in the dissipation sum positively signed with the same multiplicity as it appears negatively signed. Consequently, all terms cancel and $0 = \la \drp h_{z_1}, \drp h_{z_2} \ra_\diss = \la h_{z_1}, h_{z_2} \ra_\energy$ shows $h_{z_1} \perp h_{z_2}$.
\end{exm}


\begin{exm}[Haar wavelets and cocycles]
  \label{exm:Haar-wavelets-and-cocycles}
  \version{}{\marginpar{Add cocycles}}
  Example~\ref{exm:a-forest-of-binary-trees} can be heuristically described in terms of Haar wavelets. Consider the boundary of the tree as a copy of the unit interval with $h_x$ as the basic Haar mother wavelet; via the ``shadow'' cast by $\lim_{n \to \pm \iy} h_x(x_n) = \pm 1$. Then $h_z$ is a Haar wavelet localized to the subinterval of the support of its shadow, etc. Of course, this heuristic is a bit misleading, since the boundary is actually isomorphic to $\{0,1\}^\bN$ with its natural cylinder-set topology.
\end{exm}


\begin{exm}[Why the harmonic functions may not be in the domain of \Lap]
  \label{exm:Harm-notin-domLap}
  We have not been able to construct an example in which we can prove that \Harm is not contained in $\dom \Lap$, but we do have the following suggestive example, motivated by Lemma~\ref{thm:powers-bd-implies-Fin1=0}.
  As before, let $V := \spn\{v_x\}_{x \in \verts}$ and let $\Lap = \LapV$ denote the closure of the Laplacian when taken to have the dense domain $V$. 
  Let $h \in \Harm$. If $h$ were an element of $\dom \LapV$, then by \eqref{eqn:def:domain-of-clo(S)}, we would have a sequence 
  \linenopax
  \begin{align}\label{eqn:def:domain-of-clo(S)}
    \dom \opclosure S := \{u \suth \lim_{n \to \iy}\|u-u_n\|_\sH = \lim_{n \to \iy}\|v-Su_n\|_\sH = 0\}
  \end{align}
  Again, think of the vertices of the tree as begin labelled by a word on $\{0,1\}$, that is, a finite binary string. If $x=\word$, then $|\word|$ is the length of the word and corresponds to the number of edges between $x$ and $o$ (i.e., shortest path distance to the root). Using $\word_1$ to denote the first coordinate of \word, define the function
  \linenopax
  \begin{align}\label{eqn:harmonic-approximants-on-tree}
    h_n := \frac1{2^n} \sum_{|\word|=n} \left(\sum_{\word_1=1} v_\word - \sum_{\word_1=0} v_\word\right).
  \end{align}
  Since $h_n$ is a (finite) sum of all the dipoles at distance $n$ from $o$, with half weighted by $2^{-n}$ and the other half weighted by $-2^{-n}$, it is clear that $h_n \in \spn\{v_x\}$. One can check that for $G_n = \{\word \suth |\word| \leq n\}$,
  \linenopax
  \begin{align*}
    h(\word) = 
    \begin{cases}
      h(\word), &|\word| \leq n, \\
      \pm 2^{-n}, &\text{else},
    \end{cases}
  \end{align*}
  whence it is immediate that $\lim_{n \to \iy} \|h_n - h\|_\energy =0$.
  One can also check that
  \linenopax
  \begin{align*}
    \Lap h_n = \frac1{2^n} \sum_{|\word|=n} \left(\sum_{\word_1=1} \gd_\word - \sum_{\word_1=0} \gd_\word \right)
  \end{align*}
  since the positive and negative weights of $\gd_0$ cancel out. If $\word \neq \word'$ but $|\word|=|\word'|$, then they cannot be neighbours, and hence $\gd_{\word}$ and $\gd_{\word'}$ are orthogonal with respect to \energy. It is then easy to compute 
  \linenopax
  \begin{align*}
    \lim_{n \to \iy} \| \Lap h_n - \Lap h\|_\energy^2
    = \lim_{n \to \iy} \| \Lap h_n\|_\energy^2
    = \lim_{n \to \iy} \frac1{2^n} \sum_{|\word|=n} \| \gd_{\word}\|_\energy^2
    = \lim_{n \to \iy} \frac1{2^n} \cdot 2^n \cdot 3
    = 3 \neq 0.
  \end{align*}
\end{exm}

\begin{exm}\label{exm:monopole-in-range-of-1+Lap}
  On the binary tree with $\cond = \one$, the monopole $w(x) = 2^{-|x|}$ can be written as $v+\Lap v$ for $v \in \dom\LapV$:
  \linenopax
  \begin{align*}
    v(x) := 2^{-|x|} - \sqrt2 \left(1 + \tfrac1{\sqrt2}\right)^{n+1}.
  \end{align*}
  We leave it to the reader to check that this $v$ satisfies the above equation and also
  \linenopax
  \begin{align*}
    \energy(v) = \tfrac{2(46\sqrt2 - 65)}{(2-\sqrt2)^2 (\sqrt2-1)}, \;
    \energy(\Lap v) = \tfrac{4(99-70\sqrt2)}{(2-\sqrt2)^4 (\sqrt2 - 1)}, 
    \; \text{and} \;
    \sum_{\verts} v \Lap v = \tfrac27 (-23 + 17 \sqrt2). 
  \end{align*}
  
\end{exm}

\begin{exm}[An unbounded harmonic function of finite energy]
  \label{exm:unbounded-harmonic}
  Figure~\ref{fig:unbounded-harmonic} is a sketch of an unbounded harmonic function of finite energy on the binary tree with $\cond = \one$. To construct it, pick one ray from $o$ to \iy, and let
  \linenopax
  \begin{align*}
    h(x) = \sum_{k=1}^{|x|} \frac1k
  \end{align*}
  for $x$ along this ray. Then if $x$ is in the ray and $y \nbr x$, fix $h(y)$ so that $h$ is harmonic at $x$ (i.e., $h(y) = h(x)+\frac1{|x|(|x|+1)}$), and define $h$ along the rest of this branch by 
  \linenopax
  \begin{align*}
    h(z) = \frac{h(y)-h(x)}{2^{|y-z|}}.
  \end{align*}
  If $w$ denotes the monopole at $o$ defined by $w(x) = 2^{-|x|}$ as discussed in Example~\ref{exm:monopole-in-range-of-1+Lap} and previously, then we are essentially attaching a scaled copy of $w$ to each neighbour of the chosen ray. See Figure~\ref{fig:unbounded-harmonic}.
  
  It is clear that $h(x) \to \iy$ logarithmically along the chosen ray; the energy coming from $h(x)$ on this ray is
  \linenopax
  \begin{align*}
    \energy(h)|_{\text{ray}} = \sum_{n=1}^\iy \left(\frac1n\right)^2 = \frac{\gp^2}6.
  \end{align*}
  The energy from each branch incident upon the ray is
  \linenopax
  \begin{align*}
    \energy(h)|_{\text{branch}(n)} 
    = \left(\frac1{n(n+1)}\right)^2 + \frac1{n(n+1)}\energy(w)
    =\frac1{n^2(n+1)^2} + \frac1{n(n+1)}.
  \end{align*}
  Summing up, $\energy(h) = \energy(h)|_{\text{ray}} + \sum_{n=0}^\iy \energy(h)|_{\text{branch}(n)} = \frac{\gp^2}2 - 2$. We leave it to the reader to check that $h$ is harmonic.
\end{exm}

\begin{figure}
  \centering
  \scalebox{1.0}{\includegraphics{unbounded-harmonic.pdf}}
  \caption{\captionsize An unbounded harmonic function of finite energy. See Example~\ref{exm:unbounded-harmonic}.}
  \label{fig:unbounded-harmonic}
\end{figure}


\begin{exm}\label{exm:Lapu-not-summable}
  On the binary tree with $\cond = \one$, the function $u_\gx(x) = \gx^{-|x|}$ has energy
  \linenopax
  \begin{align*}
    \energy(u_\gx) = 2\frac{(1-\gx)^2}{1-2\gx^2} < \iy, 
    \q\text{for } \gx \in [0,\tfrac1{\sqrt2}).
  \end{align*}
  Moreover, the Discrete Gauss-Green formula applies to this example with
  \linenopax
  \begin{align*}
    \sum_{\verts} u_\gx \Lap u_\gx
    = (1-\gx)\left(2 + (2\gx-1)\tfrac{2\gx}{1-2\gx^2}\right), 
    \q\text{for } \gx \in [0,\tfrac1{\sqrt2}).
  \end{align*}
  However, for $\gx \in [0,\tfrac12)$, one also has $\sum_{\verts} \Lap u_\gx = (1-\gx) \left(2 + (2\gx-1)\tfrac{1}{1-2\gx} \right)$. Thus, for $\frac12 < \gx < \frac1{\sqrt2}$, one has $\sum \Lap u_\gx = \iy$, even though $\energy(u_\gx) < \iy$ and $\sum u_\gx \Lap u_\gx < \iy$.
\end{exm}


\begin{comment}
  Continuing to follow the convention of Remark~\ref{rem:convention-negative-tree-branch}, consider the function $f \in \HE$ defined by $f(x_n) = \operatorname{sgn}(n) = n/|n|$:
  \linenopax
  \begin{equation}\label{eqn:xy:nonapproximable-fn}
    \xymatrix{
    \dots -1 & -1 \ar@{-}[dl] \ar@{-}[l] & -1 \ar@{-}[dl] \ar@{-}[l] & 0 \ar@{-}[r] \ar@{-}[l] & 1 \ar@{-}[r] \ar@{-}[dr] & 1 \ar@{-}[r] \ar@{-}[dr] & 1 \dots\\
    \dots -1 & -1 & &&& 1 \dots & 1 \dots
    }
  \end{equation}
  We attempt to approximate this function by functions $f_n$ supported in $\Graph_n$, the subgraph of \Graph consisting of all vertices within $n$ edges from 0 (equivalently, all vertices with addresses/subscripts of length $n$ or smaller). To simplify the calculation, apply symmetry to see $f_n(0)=0$ for all $n$. Thus we can work only on positive vertices, and apply symmetry again to see that for $k>0$, $f_n$ must take the same value at every vertex with addresses of length $k$. (This can be made rigourous by an averaging argument; if $f_n$ weren't symmetric, one could average it with its ``reflection'' to obtain a better minimizer.) Replacing multiplicity with resistance, this reduces \eqref{eqn:xy:nonapproximable-fn} to
  \linenopax
  \begin{equation}\label{eqn:xy:nonapproximable-fn:as-line}
    \xymatrix{
    \dots & -1 \ar@{-}_4[l] & -1 \ar@{-}_2[l] & 0 \ar@{-}^1[r] \ar@{-}_1[l] & 1 \ar@{-}^2[r] & 1 \ar@{-}^4[r] & 1 \ar@{-}^8[r] &  \dots
    }
  \end{equation}
  Let $f_n$ be the best approximation, and define $g_n := f-f_n$. Then $\energy(g_n)$ minimizes $\sum_{k=1}^n 2^k(g_n(x_k)-g_n(x_{k-1}))^2$. Note that $g_n(x_k)\equiv1$ for $k>n$, so there is no contribution to the energy from this part of the graph. One can show that
  \linenopax
  \begin{align*}
    g_n(x_k) &= \frac2{2^{n+2}} \sum\nolimits_{j=0}^k 2^{k-j}
    \q\text{and}\q \energy(g_n) = \frac{2^n}{2^{n+1}-1}.
  \end{align*}
  Thus, $\|f-f_n\|>\frac12$ and $f$ cannot be approximated by functions of finite support.
\end{comment}


\section{Remarks and references}
\label{sec:Remarks-and-References-tree-examples}

The infinite trees offer an especially attractive source of examples, and there are theories devoted to them; see \cite{Car72, Car73a, Car73b}. Here we merely scratch the surface. Excellent books and introductions are \cite{Lyons:ProbOnTrees, Peres99, LevPerWil08}.
The reader may also find the sources \cite{Dha98, DfdeG04, DLP09, HLL08, NaPe08a, NaPe08b} to be helpful, and the preprint \cite{Kig09b} deals specifically with trees in our context, and in relation to self-similar fractals.
{"config": "arxiv", "file": "0806.3881/tree-examples.tex"}