\documentclass[finalversion]{FPSAC2025}
\articlenumber{63}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

% --------------------------------------------
% Front Matter
\title{Differential transcendence and walks on self-similar graphs}

\address{Department of Mathematics, Simon Fraser University}
%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author
\author[Y. Kahane and M. Mishna]{\texorpdfstring{Yakob Kahane\addressmark{1} \and Marni Mishna\addressmark{2}\thanks{\href{mailto:mmishna@sfu.ca}{mmishna@sfu.ca}. This work is supported by NSERC Discovery Grant ``Transcendence and Combinatorics.''}}{Yakob Kahane and Marni Mishna}}
%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}\'Ecole Polytechnique \addressmark{2}Simon Fraser University}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{Symmetrically self-similar graphs are an important type of fractal graph. Their Green functions satisfy order one iterative functional equations.  We show when the branching number of a generating cell is two, either the graph is a star consisting of finitely many one-sided lines meeting at an origin vertex,  in which case the Green function is algebraic, or the Green function is differentially transcendental over $\mathbb{C}(z)$.  The proof strategy relies on a recent work of Di Vizio, Fernandes and Mishna. The result adds evidence to a conjecture of Kr\"on and Teufl about the spectrum of this family of graphs. A long version of this abstract with complete proofs is available~\cite{kahane_differential_2024}.}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Green functions, fractals, random walks, differential transcendence}

\usepackage[backend=bibtex, giveninits]{biblatex}
\addbibresource{ref.bib}

%-------------------------------------------------
% Packages 
\usepackage{amsxtra, mathtools}%, 

\usepackage{float}

\usepackage{tikz}
\usetikzlibrary{decorations.pathreplacing,decorations.markings}
\usetikzlibrary{lindenmayersystems}
\usepackage{booktabs}
\usepackage{enumitem}
\usepackage{nicefrac}
\usepackage{bbm}
\usepackage{xspace}
\usepackage{url}\urlstyle{rm}
\usepackage{graphics,color, soul}
\usepackage{graphicx}
\graphicspath{ {./images/} }
\usepackage{wrapfig}
%\usepackage{lmodern}
\usepackage{subfigure}


% -----------------------------------------------
% Theorem definitions
\newtheorem{theorem}{Theorem}[section]
\newtheorem{nontheorem}[theorem]{Theorem} 
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}
\newtheorem{question}[theorem]{Question}
% ---------------------------------------------
% Math Notation
\setcounter{MaxMatrixCols}{20}%
\newcommand{\dd}{\emph{d}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\origin}{\mathbf{o}}
\newcommand{\cell}{\ensuremath{C}}
\newcommand{\hcell}{\ensuremath{\hat\cell}}

\def\trianglewidth{8cm}%
\pgfdeclarelindenmayersystem{Sierpinski triangle}{
    \symbol{X}{\pgflsystemdrawforward}
    \symbol{Y}{\pgflsystemdrawforward}
    \rule{X -> X-Y+X+Y-X}
    \rule{Y -> YY}
}%
%\tikzset{
%    l-system={step=\trianglewidth/(2^3), order=3, angle=-120}
%}%

    \tikzset{d/.style={minimum width=1pt,inner sep=1pt,circle,fill=black}}
    \tikzset{f/.style={minimum width=1.2pt,inner sep=1pt,circle,fill=red}}
    \tikzset{g/.style={circle,fill=white}}

\usepackage{xcolor}


\tikzset{
  % style to apply some styles to each segment of a path
  on each segment/.style={
    decorate,
    decoration={
      show path construction,
      moveto code={},
      lineto code={
        \path [#1]
        (\tikzinputsegmentfirst) -- (\tikzinputsegmentlast);
      },
      curveto code={
        \path [#1] (\tikzinputsegmentfirst)
        .. controls
        (\tikzinputsegmentsupporta) and (\tikzinputsegmentsupportb)
        ..
        (\tikzinputsegmentlast);
      },
      closepath code={
        \path [#1]
        (\tikzinputsegmentfirst) -- (\tikzinputsegmentlast);
      },
    },
  },
  % style to add an arrow in the middle of a path
  mid arrow/.style={postaction={decorate,decoration={
        markings,
        mark=at position .5 with {\arrow[#1]{stealth}}
      }}},
}

% ------------------------------------------------------
% Editing support
\usepackage{comment}
%\usepackage[textwidth=3cm,textsize=tiny]{todonotes}
%\newcounter{todocounter}
%\newcommand{\mjm}[1] 
%{\stepcounter{todocounter}\todo[,color=yellow!25]%{\sf\thetodocounter:  #1}}
%\newcommand{\yk}[1]% use this function to make comments
%{\stepcounter{todocounter}\todo[color=blue!20]{\tiny \sf\thetodocounter:  #1}}

%\def\postit#1{\bigskip\todo[color=yellow,inline]{\small #1}}
%\def\change#1{\textcolor{red}{\bfseries #1}\todo[color=yellow]{\Huge\ding{45}}}
%\def\tobechanged#1{\textcolor{grey}{#1}}
%\usepackage[notcite,notref,color]{showkeys} % shows labels in the margin. Comment in the final version
% -------------------------------------------------------
% Document start
\begin{document}

\maketitle

%{\small \tableofcontents }

% --------------------------------------------------------------------------
\section{Introduction}
\label{sec:intro}
The discretization of fractals as graphs produces a rich object of
study. Fractal graphs possess a regularity which facilitates
combinatorial and graph theoretic analysis. A uniform random walk on a
graph $X=(V, E)$ starts at some vertex, and proceeds along the edges
of the graph. We assume the degree of every vertex is bounded and that
every edge incident to a given vertex is equally likely to be
chosen. A random walk is a Markov chain $(v_i)_{i=0}^n$ encoded by a
pair $(X,P)$, governed by the probability transition matrix $P$. The $[x,y]$ entry of~$P$ is the transition function $p(x,y):=\delta_{\{x,y\}\in E} \frac{1}{\deg(x)}$. The probability of a path $x_0, x_1, \dots, x_n$, given that we start from $x_0$, is
\[
\mathbb{P}_{x_0}[v_0=x_0, v_1=x_1, \dots, v_n=x_n]=p(x_0, x_1) p(x_1, x_2)\cdots p(x_{n-1}, x_n). 
\]
The probability of a walk starting at $x$ ending at $y$ after $n$ steps is denoted~$p^{(n)}(x,y)$ and is equal to~$\mathbb{P}_x[v_n=y]$. A \emph{Green function} of $(X, P)$, denoted $G(x,y|z)$, is a generating function of probabilities: 
\[
G(x, y| z) := \sum_{n\geq 0} p^{(n)}(x,y) z^n.
\]
Here we focus on walks that start and end at some specified origin vertex labeled $\origin$, and hence refer to the Green function for a graph, and use the shorthand $G(z)$. Precisely,
\[G(z):= G(\origin,\origin|z)=\sum_{n\geq 0} p^{(n)}(\origin,\origin) z^n.\] 

This Green function, and the functional equations it satisfies, can tell you a surprising amount about $X$, and possibly even objects the graph encodes (like groups in the case of a Cayley graph).  We focus here on different notions of transcendency. Recall, a series in the ring of formal power series $\C[[z]]$ is said to be \emph{algebraic} if it satisfies a non-trivial polynomial equation, and is \emph{D-finite} over $\C(z)$ if its derivatives span a finite dimensional vector space over~$\C(z)$. A function is \emph{differentiably algebraic} if it satisfies a non-trivial polynomial differential equation, and is \emph{differentially transcendental} if is not differentiably algebraic.  These categories are useful in the case of Cayley graphs: algebraicity and D-finiteness of a Green function are each correlated with structural properties of the group~\cite{bell_complexity_2020}.

%
\begin{figure}
\centering
\noindent\begin{tikzpicture} \node[inner sep=0pt]  at (0,0) {\includegraphics[width=.7\textwidth]{G_4.png}}; \node[circle, draw, fill=blue!50, inner sep=1.5pt, label=above:{$\origin$}] at (-.35\textwidth,0){};  
\end{tikzpicture}
\caption{Close up on a symmetrically self-similar graph with branching number 2 near its origin $\origin$. The generating cell is pictured in \Cref{fig:cell}(a).}
\label{fig:diamond}
\end{figure}

\subsection{Symmetrically self-similar graphs}
Here, we consider only symmetrically self-similar graphs with bounded geometry. They are discretizations of fractals and appear in a variety of different domains such as quantum information protocol design, the study of Brownian motion on fractals, and group theory ~\cite{lindstrom_brownian_1990,malozemov_integrated_1993}. They are generated in a blow up construction from a finite cell graph. We recall a precise definition in a moment, but the Sierpi\'nski graph is a classic example.  The Green functions of these graphs are well studied~\cite{grabner_functional_1997, kron_asymptotics_2004}, including, the asymptotic behaviour of the excursion probabilities. Kr\"on and Teufl~\cite{kron_asymptotics_2004} show that asymptotically, as $n$ tends towards infinity,  $p^{(n)}(\origin,\origin)$ tends to~$n^\beta w(n)$ where $\beta$ is  related to the geometry of the graph, and~$w(n)$ is some oscillating function.  

In the case of the Sierpi\'nski graph, $\beta=\log{5}/\log{3}$. Because $\beta$ is irrational, we can deduce by the classic Structure Theorem for singularities of solutions to differential equations~\cite[Theorem 19.1 p. 111]{wasow_asymptotic_1987} that the Green function is not D-finite. Indeed, in almost all examples that have been studied, non-D-finiteness (and hence transcendence) of the Green function can be deduced immediately from the singular expansion. The graphs with a line as the cell graph (See \Cref{ex:line} below for details) are the only known examples with algebraic Green functions. 

Recently, Di Vizio \emph{et al.}~\cite{di_vizio_inhomogeneous_2023} showed that the Green function of the Sierpi\'nski graph is not just transcendental, but actually differentially transcendental\footnote{Also called hypertranscendental in some literature}.
There are no similarly applicable structure theorems for  differentially algebraic functions. Instead, the proof of differential transcendence uses the key result of  Grabner and Woess~\cite{grabner_functional_1997} that the Green function of the Sierpi\'nski graph satisfies an iterative equation of the form 
%-----------------------------------------------------
\begin{equation}
\label{eq:central}
G(z)= f(z)G(d(z)),
\end{equation}
%-----------------------------------------------------
where~$f$ and~$d$ are explicit rational functions and are themselves Green functions of a finite graph related to the generating cell. By Di Vizio \emph{et al}., series solutions to such equations are either algebraic, or are differentially transcendental. In the present work we generalize this approach to the full class of the symmetrically self-similar graphs. 


%
\subsection{Transcendence of the Green functions}
We are more generally motivated to understand connections between
combinatorial structure, and generating function behaviour. We
conjecture the following, which gives strong insight into
transcendence from a combinatorial perspective. 
%-----------------------------------------------------

\begin{conjecture}
\label{conj:main}
The Green function of a symmetrically self-similar graph with bounded geometry is algebraic if, and only if, the graph is a star consisting of finitely many one-sided lines with exactly one origin vertex in common. Otherwise, it is differentially transcendental.
\end{conjecture}
%-----------------------------------------------------
\begin{comment}
We prove this conjecture for one family in the main theorem of this paper. The hypotheses depend on the the initial cell, $\hcell$, the branching number $\theta$, and the transition function on $\cell$, $d(z)$, all of which are defined below. In every case we have tested for $\theta>2$, the second condition holds, a verification that can be computed in time polynominal in the size of the cell graph. Here we state our Main Theorem which appears in \Cref{sec:main_theorem} as \Cref{thm:MAIN}.
\end{comment}

We prove this conjecture for a sub-case in the main theorem of this paper, of which \Cref{fig:diamond} is an example. The hypotheses depend on the branching number $\theta$ of $X$, which is defined below. Here we state our Main Theorem which appears in \Cref{sec:main_theorem} as \Cref{thm:MAIN}.

\begin{nontheorem}[Main result] 
Let~$X$ be a symmetrically self-similar graph with finite geometry, origin~$o$, and branching number~$\theta=2$. Either the graph is a star consisting of finitely many one-sided lines coinciding at $o$
or the Green function $G(\origin, \origin|z)$ of~$X$, is differentially transcendental over~$\mathbb{C}(z)$. 
\end{nontheorem}
%\begin{nontheorem}[Main result] 
%Let~$X$ be a symmetrically self-similar graph with respect to~$\hcell$, with %origin~$o$, and branching number~$\theta$. Suppose that $\hcell$ is not a line. 
%If $\theta=2$, or if~$d(1-\theta)\neq\infty$ then $G(z) = G(o, o|z)$, the Green %function of~$X$, is differentially transcendental over~$\mathbb{C}(z)$. 
%\end{nontheorem}

Malozemov and Teplyaev~\cite{malozemov_self-similarity_2003} showed that the spectrum of self-similar graphs consists of the Julia set of a rational function and a (possibly empty) set of isolated eigenvalues that accumulate to the Julia set.  Kr\"on and Teufl conjectured this Julia set is an interval if, and only if, the graph is a star consisting of finitely many one-sided lines with exactly one origin vertex in common, otherwise it is a Cantor set. Our main result resolves the conjecture of Kr\"on and Teufl in a narrow case.  Furthermore, our result demonstrates an important connection between the spectrum of infinite self-similar graphs, and the transcendent nature of Green functions. 

There are still some open questions: 
\begin{enumerate}
    \item The proof of the main theorem applies whenever we can prove $G$ has no singularity less than ${-}1$. A better understanding of the spectrum could facilitate a combinatorial characterization of this case. 
    \item Some infinite Cayley graphs are also fractal, and their Green functions satisfy functional equations of the type in Equation~\eqref{eq:central}.     However, they are easily proved to be algebraic~\cite{bell_cogrowth_2023}. Can we characterize a wider class of fractal graphs with algebraic Green functions?
   % \item Can the theorem of Di Vizio \emph{et al.} be extended to a multivariate context to handle diffusion on simply and doubly symmetric fractal graphs. 
    %G. Schweitzer. PhD thesis, Graz University of Technology, 2006.
\end{enumerate}

% -----------------------------------------------
\begin{figure}
\centering 
\subfigure[$\theta=2$, $\mu=6$]%
{ 
% wolfhead:  \includegraphics[width=0.3\textwidth]{theta_2.png}
\begin{tikzpicture}[scale=.75]\foreach \i/\x/\y in {
   1/0/0, 2/1/0, 3/2/0, 4/3/0, 
    5/1.5/.5, 6/1.5/-.5} 
{
    \node[circle, draw, inner sep=1.5pt] (\i) at (\x,\y) {};
}
% extremal vertices
    \node[circle, draw, fill=blue!50, inner sep=1.5pt, label=left:{$v_1$}] (1) at (0,0) {};
    \node[circle, draw, fill=blue!50, inner sep=1.5pt, label=right:{$v_2$}] (4) at (3,0) {};

\foreach \i/\j in {
1/2, 3/4, 
2/5, 5/3,  
2/6, 6/3}
{\draw[-] (\i) -- (\j);}

\end{tikzpicture}
}\quad
\subfigure[$\theta=3$, $\mu=3$]%
{
\begin{tikzpicture}[scale=.75]
    % Define the vertices
    \node[circle, draw, fill=blue!50, inner sep=1.5pt, label=left:{$v_1$}] (v1) at (0,0) {};
    \node[circle, draw, fill=blue!50, inner sep=1.5pt, label=right:{$v_2$}] (v2) at (3,0) {};
    \node[circle, draw, fill=blue!50, inner sep=1.5pt, label=above:{$v_3$}] (v3) at (1.5,2.6) {};
    
    % Define the internal vertices
    \node[circle, draw, inner sep=1.5pt] (v4) at (1.5, 0) {};
    \node[circle, draw, inner sep=1.5pt] (v5) at (0.75, 1.3) {};
    \node[circle, draw, inner sep=1.5pt] (v6) at (2.25, 1.3) {};
    
    % Draw the triangles
    \draw (v1) -- (v5) -- (v4) -- (v1);
    \draw (v3) -- (v5) -- (v6) -- (v3);
    \draw (v2) -- (v4) -- (v6) -- (v2);
\end{tikzpicture}
}\quad
\subfigure[$\theta=4$, $\mu=5$]%
{
\begin{tikzpicture}[scale=.75]
\foreach \i/\x/\y in {
%    1/0/3, 2/0/0, 3/3/0, 4/3/3, 
    5/0/2, 6/1/3, 7/1/0, 8/0/1, 
    9/3/1, 10/2/0, 11/2/3, 12/3/2,
    13/1/2, 14/1/1, 15/2/1, 16/2/2} 
{
    \node[circle, draw, inner sep=1.5pt] (\i) at (\x,\y) {};
}
% extremal vertices
\foreach \i/\x/\y in {
    1/0/3, 2/0/0
   } 
{
    \node[circle, draw, fill=blue!50, inner sep=1.5pt, label=left:{$v_\i$}] (\i) at (\x,\y) {};
}
\foreach \i/\x/\y in {
   3/3/0, 4/3/3
   } 
{
    \node[circle, draw, fill=blue!50, inner sep=1.5pt, label=right:{$v_\i$}] (\i) at (\x,\y) {};
}
\foreach \i/\j in {
1/5, 1/6, 1/13, 
2/7, 2/8, 2/14, 
3/9, 3/10, 3/15, 
4/11, 4/12, 4/16, 
5/6, 5/13, 
6/13, 
7/8, 7/14, 
8/14, 
9/10, 9/15, 
10/15, 
11/12, 11/16, 
12/16, 
13/14, 13/15, 13/16, 
14/15, 14/16, 
15/16}
{\draw[-] (\i) -- (\j);}
\end{tikzpicture}
}

\caption{Three cell graphs, with their extremal vertices in blue.}
\label{fig:cell}
\end{figure}

\section{Symmetrically self-similar graphs}
\label{sec:self-sim-graphs}
The class of symmetrically self-similar graphs can be defined in two
different ways: either as a
fixed point to a particular type of graph morphism or as the limit of
a blow up process. Different authors have conisdered it, including
Malozemov and Teplyaev~\cite{malozemov_pure_1995},
Kr\"on~\cite{kron_green_2002}, and Kr\"on and
Teufl~\cite{kron_asymptotics_2004}. In this abstract we can, at best,  sketch out one
description, but finer details of the construction are well defined in
these references.  

We consider graphs  $X = (V, E)$ with vertex set $V$ and edge set $E$. Here we restrict our attention to undirected, simple graphs with no loops nor multiple edges. Given a set of vertices $\cell\subset V$, we define the boundary, denoted $\theta\cell$, to be the set of all vertices in $X\setminus \cell$ which are adjacent to some vertex in $\cell$. We write $\hcell$ for the subgraph of $X$ spanned by $\cell$ and its boundary. 

\begin{comment}
Let $B$ be a sub-graph of a simple graph~$X$.  We define the set $\operatorname{Con}_X(B)$ to be the set of connected components in $X \setminus B$. We define the graph $X_B$ on vertex set $V(B)$ and edge set $\{\{x,y\}\mid \exists \text{ component } \cell\in \operatorname{Con}_X(B), x, y\in\theta \cell\}$.

A connected infinite graph $X$ is said to be \emph{self-similar} with respect to sub-graph $B$ and the map $\psi: V(X) \to V(X_B)$ if the following hold:
\begin{enumerate}
	\item no two vertices in $B$ are adjacent in $X$;
	\item the intersection of the boundaries of two different components in $\operatorname{Con}_X(B)$ contains at most one vertex; and
	\item $\psi(X_B)$ is isomorphic to $X$.
\end{enumerate}
We call the components of $\operatorname{Con}_X(B)$ \emph{cells}. Roughly,~$\psi$ replaces a cell $\cell$ in $X$ with a complete graph on the vertices of~$\theta C$. If an infinite graph is self-similar, this defines an isomorphism. 


\end{comment}

A symmetrically self-similar graph $X$ is generated from a finite cell
graph $\cell$ that it ultimately contains. There are restrictions on its boundary $\theta
\cell$. The closure of the cell, $\hcell$,  satisfies a symmetry condition. The automorphism group $\operatorname{Aut}(\hat \cell)$ of $\hat \cell$
acts doubly transitively on $\theta \cell$, which means that it acts
transitively on the set of ordered pairs		 $\left\{
  (x,y) \mid x,y \in \theta \cell, \; x \neq y \right\},$
where $g((x,y))$ is defined as $(g(x),g(y))$ for any $g\in
\operatorname{Aut}(\hcell)$.  There are some restrictions which
roughly translate into $\hcell$ being built from $\mu$ cliques of the
same order, $\theta$. These are two essential parameters for a graph. 

%The graph $X$ is \emph{symmetric} if it is locally finite\footnote{all vertices have finite degree}, and it satisfies the following axioms:
%\begin{enumerate}
%	\item All cells are finite,  and for any pair of cells $C$ and $D$ in $C_X(F)$		there exists a isomorphism on vertices from		of $\hat C$ to $\hat D$ such that the image of $\theta C$ is $\theta D$;
%	\item The automorphism group $\operatorname{Aut}(\hat C)$ of $\hat C$
%		acts doubly transitively on $\theta C$,
%		which means that it acts transitively on the set of ordered pairs
%		 $\left\{ (x,y) \mid x,y \in \theta C, \; x \neq y \right\},$ 
%		where $g((x,y))$ is defined as $(g(x),g(y))$ for any $g\in \%operatorname{Aut}(\hcell)$.
%\end{enumerate}


Krön and Teufl~\cite[Theorem 1]{kron_asymptotics_2004} describe an
iterative process to construct a self-similar graph starting from
$\hcell$. Roughly, the $\mu$ copies of $K_\theta$ in $\hcell$ are
``blown up'', and are replaced by a copy of the~$\hcell$, as pictured
in \Cref{fig:Serp}. The sequence of substitutions converges to a
unique limit graph $C_\infty$.

Kr\"on showed~\cite[Theorem~1]{kron_green_2002} that in this process,
there is either a unique fixed origin
cell, or a unique origin vertex, that is fixed in this blow up
process. In \Cref{fig:Serp} it is $v_1$, and in the limit we denote
it here~$\origin$. In
this work, we consider graphs with a unique origin vertex.

The graph $C_\infty$ is a symmetrically self-similar graphs, but so
are finitely many copies of $C_\infty$ coinciding at the origin
vertex. Remark, the Green function for either will be the same. 

%An \emph{origin cell} is a cell $\cell$ such that $\psi(\theta C) \subset \cell$. A vertex fixed point of $\psi$ is called an \emph{origin vertex}.  If $X$ is self-similar with respect to $B$ and $\psi$ then by Kr\"on, (\cite[Theorem~1]{kron_green_2002}) %\cite{kron_growth_02}? 
%$X$ has precisely one origin cell and no origin vertex or exactly one% origin vertex, which we shall denote~$o$ when it is the case. 

%If a self-similar graph $X$ satisfies these properties, the cells are
%finite and isomorphic. Denote this cell by $\cell$ and its boundary in
%$X$ by $\theta\cell$.

The boundary vertices $\theta\cell$ are called the \emph{extremal
  vertices}. There must be $\theta$ of them to do the substitution so this is the \emph{branching number} of $X$. The closure cell $\hcell$ is \emph{the} cell associated to the graph.  The edges of $\hcell$ can be partitioned into~$\mu$ complete graphs on $\theta$ vertices. Thus, $\mu = \frac{2|E|}{\theta(\theta-1)}$ and it corresponds 
to the usual mass scaling factor of self-similar sets. 
%On the other hand, the number $\tau=d'(1)$ corresponds to the time scaling factor.   

\Cref{fig:cell} has three examples of cell graphs, their extremal
vertices, and the values of $\theta$ and $\mu$.  Remark, if a self-similar graph is bipartite, its cell graph is bipartite.
 
 %Krön and Teufl~\cite[Theorem 1]{kron_asymptotics_2004} describe an iterative process to construct a self-similar graph starting from $\hcell$ using an inverse action to $\psi$. Very roughly,  the $\mu$ copies of $K_\theta$ in $\hcell$ are ``blown up'', and are replaced by a copy of the~$\hcell$, as pictured in \Cref{fig:Serp}.  The sequence of substitutions converges to a unique graph $X$ fixed under $\psi$. 
%A suitable cell graph $\hcell$ can be blown up to an infinite self-similar graph. Remark that the graph with a fixed number of copies of this graph centered at $o$ is also a fixed point of $\psi$. Given~$\hcell$, we can generate a countable family of self-similar graphs.  In this article we consider walks on symmetrically self-similar graphs starting and ending from an origin vertex. 
%
\begin{figure}
    \centering
    \includegraphics[width=.5\textwidth]{Sierpinski.png}\
    \caption{$C_0=K_3$, $C_1=\hcell$ and $C_2$. From $C_i$ to $C_{i+1}
    $ the shaded area are replaced by a copy $\hcell$. The limit graph in this case is the Sierpi\'nski graph.}
    \label{fig:Serp}
\end{figure}
%

\begin{example}[A simple star graph]
\label{ex:line}
Let $\hcell$ be a path on three vertices. There are two extremal
vertices, so $\theta=2$. The blow up process roughly divides each edge
in two at every step, and so $C_\infty$ a one-sided infinite line with
origin at $v_1$.  We could join
two lines at the origin to make the symmetrically self-similar graph that is a bi-finite line:
\begin{center}
\begin{tikzpicture}[scale=1]\foreach \i/\x/\y in {
   1/0/0, 2/1/0, 3/2/0} 
{
    \node[circle, draw, inner sep=1.5pt] (\i) at (\x,\y) {};
}
% extremal vertices
    \node[circle, draw, fill=blue!50, inner sep=1.5pt, label=left:{$\hcell=\quad v_1$}] (1) at (0,0) {};
    \node[circle, draw, fill=blue!50, inner sep=1.5pt, label=right:{$v_2$}] (3) at (2,0) {};

\foreach \i/\j in {
1/2, 2/3}
{\draw[-] (\i) -- (\j);}
\end{tikzpicture}
\quad 
\begin{tikzpicture}[scale=1]\foreach \i/\x/\y in {
 2/1/0, 3/2/0, 4/3/0, 5/4/0, 6/5/0} 
{
    \node[circle, draw, inner sep=1.5pt] (\i) at (\x,\y) {};
}
\node (1) at (.5,0) {};
\node (7) at (5.5, 0) {};
\foreach \i/\j in {
 1/2, 2/3, 3/4, 4/5, 5/6, 6/7}
{\draw[-] (\i) -- (\j);}
% extremal vertices
    \node[circle, draw, fill=blue!50, inner sep=1.5pt, label=above:{\hphantom{$\origin$}},label=below:{$\origin$}] (1) at (3,0) {};
    \node[label=left:{$X=\quad\cdots$}] (1) at (.5,0) {};
    \node[label=right:{$\cdots$}] (1) at (5.5,0) {};
\end{tikzpicture}
\end{center}
%
%Here $B$ is every second vertex, and $\psi$ on $X$ contracts every second vertex, and we can remark that the infinite line is fixed under this action. 
The Green function here is a standard combinatorial problem:
$p^{(2n)}(\origin,\origin) =\binom{2n}{n}2^{-2n}$, from which we deduce
$G(z)= \frac{1}{\sqrt{1-z^2}}$.  This is an example of a star graph,
and we see immediately that the generating function is algebraic. The
central claim of this work is that a path is the only cell that leads
to an algebraic Green function. 
\end{example}
%
%--------------------------------------------------------------------

\subsection{Green functions}
\label{sec:green_functions}
One of the main results of Kr\"on and Teufl in~\cite{kron_asymptotics_2004} is a functional equation satisfied by $G(z)$ that exploits the iterative nature of the blow up construction.  Define~$d$ to be the \emph{transition function}: the generating function of the probabilities that the simple random walk on $\hcell$ starting at $o$ in $\theta\cell$ hits a vertex in $\theta\cell\setminus \{\origin\}$ for the first time after exactly $n$ steps. Furthermore $f$ is the \emph{return function}: the generating function of $f_n$, the probability that the random walk on $\hcell$ starting at $\origin$ returns to $\origin$ after $n$ stages without hitting a vertex in $\theta\cell\setminus \{\origin\}$. Since the start is considered the first visit, $f_0=1$, and thus $f(0)=1$. We also use $r(z)$, the probability function of first return which satisfies $f(z)=\frac{1}{1-r(z)}$. The series $d(z)$ is the generating function of $d_n$, the probability of walks on $\hcell$ that start at $v_1$ and end the first $v_i$ ($i\neq 1$) they visit. Because $\hcell$ is finite, $f$ and $d$ are expressed in terms of Green functions of a finite graph. They are well understood: they are rational functions that can be computed as the determinant of a specific matrix. We first give the functional equation, and then consider singular expansions of $G$, $d$ and $f$.

\begin{lemma}[{Kr\"on and Teufl \cite[Lemma 3]{kron_asymptotics_2004}}]
\label{lem:GSS}
Let $G(z)$ be the Green function for a symmetrically self-similar graph with origin $\origin$. Then, the following equation holds for all $z$ in the open unit disc:
\begin{equation}
    G(z) = f(z)G(d(z)).
\end{equation}
\end{lemma}
It was first proved for the Sierpi\'nski graph by Grabner and Woess \cite{grabner_functional_1997} before being generalized for all self-similar graphs by Krön \cite{kron_green_2002}. We inspect the components of this equation more closely.
The Green function $G(u,v|z)$ of a finite graph with transition probability matrix $P$ is the $[u,v]$ entry of $(I-zP)^{-1}$. Analytically, we know a fair amount about $G$ in this case.  The structure of the Green function and its expansion near its dominant singularity is captured in the comprehensive Theorem V.7 and Lemma V.1 in ~\cite{flajolet_analytic_2009}. We do not copy them here, but they are very important to our analysis.   Remark the result does not apply to bipartite graphs, as $P$ fails the condition of aperiodicity, but there are workarounds. The singular expansion of $f$ (and $d$) is of the form $\kappa(1-z/\rho)^{-1} + O(1)$,  as $z\rightarrow \rho$ for a real, positive $\kappa$. Furthermore, as $\hcell$ is finite, $d$ and $f$ are rational. 

In the case of symmetrically self-similar graphs with bounded geometries Kr\"on and Teufl exploit their functional equation to determine the singular expansion of~$G(z)$ near~$z=1$. Here $\tau=d'(1)$ and $\alpha=f(1)$.

\begin{theorem}[{Kr\"on and Teufl \cite[Theorem 5]{kron_asymptotics_2004}}]
\label{thm:KT}
Let~$X$ be a symmetrically self-similar graph with bounded geometry and origin vertex~$o$.  Then there exists a 1-periodic, holomorphic function $\omega$ on some horizontal  strip around the real axis such that the Green
function $G$ has the local singular expansion
    \[\forall |z|<1, \quad G(z) = (z-1)^{\eta} \left( \omega \left( \frac{1-z}{\tau} \right) + o(z-1) \right), \quad \eta = \frac{\log \mu}{\log \tau}-1\]
\end{theorem}
Recall that~$\mu$ is the number of cliques that form~$\hcell$. Moreover, even though it is not directly stated, it follows from a quick analysis of the asymptotics of $G$ at $1$  that $\eta = \frac{\log \alpha}{\log \tau}$. 
In the case of the line graph, as $G(z)= \frac{1}{\sqrt{1-z^2}}$, we see that $\omega$ is constant and $\eta=-1/2$.
Kr\"on and Teufl conjecture that the converse is also true: if $\omega$ is constant, then $\hcell$ is a line. 

The domain of analyticity of $G$ is governed by the dynamic behaviour of $f$ and $d$, and is well studied by Kr\"on~\cite{kron_green_2002} and Kr\"on and Teufl~\cite{kron_asymptotics_2004}. The asymptotic behaviour of the coefficients of an algebraic series is well understood, and explains why if~$\omega$ is not constant, then $G$ is not algebraic. More is true, thanks to a recent result of Di Vizio \emph{et al}. 

\begin{theorem}[{Di Vizio, Fernandes, Mishna~\cite[{Special case of Theorem C}]{di_vizio_inhomogeneous_2023}}] \label{thm:DFM}
Suppose $y(z)\in\mathbb{C}[[z]]$ is a series that satisfies the following iterative equation, with $a(z), b(z)\in \C(z)$:
\[y(z)=a(z)y(b(z)).\]
    If additionally $b(z)$ satisfies the following conditions : 
$b(0) = 0$;  $b'(0) \in \{ 0, \emph{roots of unity}\}$; and
 no iteration of $b(z)$ (i.e $b \circ b \circ \dots \circ b(z)$)is equal to the identity, then either there is some $ N \in \mathbb{N}^*$, such that $y(z)^N$ is rational,  or $y$ is differentially transcendental over $\mathbb{C}(z)$. 
\end{theorem}
Putting these results together we have our workhorse result. 

\begin{corollary}
\label{cor:DFM}
Let $G(z)$ be the Green function of a symmetrically self-similar graph with origin~$\origin$. Then, $G(z)$ is either algebraic or differentially transcendental over $\mathbb{C}(z)$.  If $G$ is algebraic, then there exists a minimal $N$ such that $G^N=P/Q$ with~$P, Q\in\mathbb{C}[z]$, $P$ and $Q$ co-prime and $Q$ monic.
\end{corollary}
\begin{proof}
We verify that the hypotheses of \Cref{thm:DFM} hold. We set $b$ to $d$, $f$ to $a$ and $y$ to $G$. By definition, two vertices on the boundary of the cell have distance at least two away, so $0=d_0=d(0)$ and $0=d_1=d'(0)$. No iteration of $d(z)$ is the identity, since each iteration increases the number of initial terms equal to 0. The rest follows from \Cref{thm:DFM}. 
\end{proof}

We note additionally that there is a unique analytic continuation of any Green function $G(u,v,|z)$ to some domain beyond the radius of convergence.  If $G$ is algebraic, using the polynomial equation it satisfies we can verify that Equation~\eqref{eq:central} holds in that domain. Under these results, we know that $G^N$ is rational, and it will be convenient to work with this function. 

\subsection{Further analysis on \texorpdfstring{$f(z)$, $d(z)$ and $r(z)$}{f(x), d(z) and r(z)}}
Recall that $d_n, f_n$ and $r_n$ are the coefficients of respective
series $d, f$ and $r$ expanded at $0$. Since they come from walks on
finite graphs, we can write $d$ and $f$ explicitly as quotients of determinants, and
deduce that the radius of convergence $\rho_d$ (respectively $ \rho_f$
and $\rho_r$) of $d$, ($f$ and $r$), given by the dominant
singularity is bounded above by~$1$ in each case. As these are Green functions, we can deduce key facts about these elements that we use in subsequent proofs. The proofs are a mix of basic facts on Green functions, and series analysis. The proofs are in the full version of this abstract.
%

\begin{lemma} 
\label{lem:technical}
For $\rho_d, \rho_f$ and $\rho_r$ as defined above the following are true: 
\begin{itemize}
    \item $\rho_d$ and $\rho_f$ are each poles of order 1; 
    \item $\rho_d=\rho_f < \rho_r$;
    \item  $\forall z\in (1, \rho_d), \, d'(z) > 1$ and therefore $d(z)>z$;
        for $z \in [0, \rho_r]$ if $f(z) = \infty$, then $z=\rho_f^{-1}$.
\end{itemize}
         
            
    \end{lemma}
%

\begin{example}
We can continue the example of the line to help visualize these results. 
$G(z)^2=\frac{1}{1-z^2}$ is a rational function. We can similarly directly compute the transition and return probabilities by direct argument: $d=\frac{2}{2-z^2}$, $f(z)=d(z)+1$, $r(z)= z^2/2$ hence $\rho_d=\rho_f=\sqrt{2}$. Using this we can verify that $G$ satisfies Equation~\eqref{eq:central}.  
Remark, $G(z)^2$ has simple poles at 1 and -1.
\end{example}

\begin{comment}
\begin{proof}[Proof of \Cref{lem:technical}]\mbox{}
\begin{enumerate}
\item This is an application of~\cite{flajolet_analytic_2009}, Theorem V.7.\emph{iii} and V.7.\emph{i}.
\item  This is a consequence of $f(z)=\frac{1}{1-r(z)}$: $f(z)$ is singular where $r(z)=1$.
\item  Consequence of the symmetric self-similarity. All of the Green functions of a given graph have the same dominant singularity.  Now, $d$ is a finite sum of Green functions of a graph and $f$ is a Green function of the same graph, specifically a graph isomorphic to $\cell$ minus all but one extremal vertex. Thus, $d$ and $f$ have the same dominant singularity. 
\item  This is a direct computation on derivatives. 
\item  Since $f(z)$ is singular where $r(z)=1$, and $r$ is increasing until its radius of convergence. 
\end{enumerate}
\end{proof}
\end{comment}



%----------------------------------------------
\section{Proof the Main Theorem}
\label{sec:main_theorem}
%----------------------------------------------
Recall the statement of the Main Theorem:

\begin{theorem}
\label{thm:MAIN}
Let $X$ be a symmetrically self-similar graph with bounded geometry, origin $\origin$ and branching number $\theta=2$. Either the graph is a star consisting of finitely many one-sided lines coinciding at $\origin$ or the Green function $G(\origin, \origin|z)$ is differentially transcendental over $\mathbb{C}(z)$. 
\end{theorem}
The proof is split into two key lemmata that we prove in \Cref{sec:bipartite} and \Cref{sec:nonbipartite} respectively.
\begin{proof}[Sketch of proof of \Cref{thm:MAIN}]
First by~\cite[Lemma 2]{kron_green_2002} a star centered at an origin vertex if, and only  $\hcell$ is a line. 
By \Cref{cor:DFM}, $G$ is either differentially transcendental or algebraic. If $G$ is algebraic and $X$ is bipartite, then by \Cref{lem:bipartite}, $\hcell$ is a line graph. Otherwise, if $X$ is not bipartite, by \Cref{lem:non-bipartite}, $G$ is differentially transcendental. 
\end{proof}
%
Throughout this section, we assume $X$ is  a symmetrically
self-similar graph with bounded geometry, and origin $\origin$. When
we assume that $G$ is algebraic, we write $G^N=P/Q$, as in \Cref{cor:DFM}.
%
%----------------------------------------------

\subsection{The structure of an algebraic \texorpdfstring{$G(z)$}{G(z)}}
\label{sec:algebraic}
%----------------------------------------------
In this section, assume that $G$ is algebraic. 
\begin{lemma}
\label{lem:no_positive_poles}
    The only possible real pole of $G^N$  greater than 0 is 1 
\end{lemma}

\begin{proof}
If~$G$ is algebraic, then $\omega$ in \Cref{thm:KT} is constant and by Kr\"on~\cite[Theorem 7]{kron_green_2002} the singularities of $G(z)$ are real, and contained in the set $(-\infty, -1]\cup[1, \infty)$. Furthermore, they are poles of $G^N$. Towards a contradiction, assume there is some real $z_0$, with $z_0>1$ that is either a pole or a zero. Since $G^N$ has only a finite number of zeroes and poles, we can assume that $z_0$ is the smallest one strictly greater than $1$. Since $\rho_d$ is the first pole of $d(z)$ and $d$ has non-negative coefficient,  $d((1,\rho_d)) = (1,\infty)$ and $d$ is increasing on $(1,\rho_d)$, and so there exists a $z' \in (1,\min(z_0,\rho_d))$ such that $d(z') = z_0$.  Similarly, $f$ analytic and defined on the interval $[1, \rho_d)$. Recall $f_0=1$ and $f$ is increasing on this interval so $z'$ is neither a zero nor a pole of $f$. 
Next consider Equation~\eqref{eq:central} and take $N$th powers: $\frac{G(z)^N}{f(z)^N} = G(d(z))^N$.
Since $z_0$ is a pole of $G^N$, 
\[\lim_{z\rightarrow z'} G(d(z))^N=\lim_{z\rightarrow z_0} G(z_0)^N=\infty,\] but $\lim_{z\rightarrow z'} \frac{G(z)^N}{f(z)^N}=(G(z')/f(z'))^N$, which is finite since $z'$ is not a pole of $G$ and $z'$ is not a zero of $f$.  This contradiction establishes the result.   
\end{proof}

\begin{lemma}
\label{lem:deg}
Under the hypotheses above, $\deg Q\geq N$. 
\end{lemma}
%
\begin{proof}
We apply the central functional equation to $G^N=P/Q$ and consider expansions of $G$, $f$, and $d$ around $\rho_f=\rho_d$. Now, $G(z)$ is not singular at $\rho_f$, since $\rho_f>1$, nor is $G$ zero at $\rho_f$, by \Cref{lem:no_positive_poles}.
Here $\kappa_f$ and $\kappa_d$ are positive real constants which correspond to $f$ and $d$ given by~\cite[Theorem 7.]{flajolet_analytic_2009}. We compute the following limits in~$\mathbb{R}$:
\begin{eqnarray*}
G(\rho_f)^N &=&\lim_{z \rightarrow \rho_f} G(z)^N \\
&=&\lim_{z \rightarrow \rho_f} f(z)^N P(d(z))/Q(d(z)).\\
&=&\lim_{z \rightarrow \rho_f}\left(\frac{\kappa_f^N}{(1-z/\rho_f)^{N}} + O(z-\rho_f)^{-N+1}\right) \frac{P(\kappa_d(1-z/\rho_f)^{-1} + O(1))}{Q(\kappa_d(1-z/\rho_f)^{-1} + O(1))}\\
&=&\lim_{u\rightarrow \infty} (\kappa_f^N u^{N} + O(u)^{N-1}) P(\kappa_d u + O(1))/Q(\kappa_d u + O(1))\\
&=&\lim_{u\rightarrow \infty} \kappa_f^N u^{N}  P(\kappa_d u)/Q(\kappa_d u).
\end{eqnarray*}
We have applied the variable change $u=(1-z/\rho_f)^{-1}$, and as $z$ approaches $\rho_f$, $u$~is arbitrarily large. The degree of $Q$ as a polynomial in $z$ must be larger than $N$ since the value of the last limit is non-zero.
\end{proof}
Analyzing the last limit, we see that $\lim_{u\rightarrow \infty} P(\kappa_d u)/Q(\kappa_d u)=0$ hence \begin{equation}0=\lim_{u\rightarrow \infty} G(u)^N=\lim_{u\rightarrow \infty} G(u).
\end{equation}
We prove the main result in two stages depending on whether or not $X$ is bipartite. 
%-----------------------------------------

\subsection{Case 1: \texorpdfstring{$X$}{X} is bipartite}
\label{sec:bipartite}
%-----------------------------------------
First we consider the case of bipartite graphs. In this case it must be that~$\theta=2$, since any complete graph on three or more vertices is not bipartite.  
% The $\theta=2$ case was particularly 
%\mjm{Mention that this case was also studied separately by the Russian authors} 
The main result of this subsection is the following: 

\begin{lemma}
\label{lem:bipartite}
   Let $X$ be a symmetrically self-similar graph with bounded
   geometry, origin $\origin$. If $X$ is bipartite, and $G$ is algebraic, then $\hcell$ is a path.  
\end{lemma} 
We proceed by examining the form of $Q$.
%-----------------------------------------

\begin{lemma}\label{lem:form_of_Q}
 Let $X$ be a symmetrically self-similar graph with bounded
   geometry, origin $\origin$. If $X$ is bipartite, and $G$ is
   algebraic, then  $Q(z) = a_Q(1-z)^{-\eta N}(1+z)^{-\eta N}$.
\end{lemma}
With $a_Q$ a constant such that $Q(z)$ is a monic polynomial. 
Recall that $\eta = \frac{\log \mu}{\log \tau}-1$.
%-----------------------------------------
\begin{proof}
By \Cref{lem:no_positive_poles} the only positive singularity of $G$ is at 1, and by \Cref{thm:KT}, the exponent of the singular expansion is $\nu$. As $G$ is an even function with real singularities, the only other singularity is ${-}1$. As taking positive integer powers does not introduce singularities, the singularities of $G$ are all roots of $Q$. From the singular expansion of $G$ near~1, we can deduce the order of the root $1$ in $Q$, and since the function is even, it is the same as the order of the root ${-}1$, and the result follows.
\end{proof}
%-----------------------------------------

\begin{lemma}
\label{thm:alpha_mu}
If $X$ is bipartite, then  $\alpha \leq \mu$ with equality if and only if $\hcell$ is a line graph. 
\end{lemma}
Recall that $\alpha=f(1)$. 
\begin{proof}[Proof intuition]
%The proof is quite long and technical and can be found in annex. 
That there is equality in the case of a line graph follows from \cite[Example 1]{kron_asymptotics_2004}. As $\theta=2$, $\mu$ is the number of edges in $\cell$ and $\alpha=f(1)$, and $\alpha$ is the average number of returns for walks enumerated by the return function. 

The proof is technical, but relies on a straightforward intuition that among all finite cell graphs $\hcell$ where $v_1$ and $v_2$ are a fixed distance apart, the average number of times a random walk starting at $v_1$ hits $v_1$ before $v_2$ (i.e. $f(1)$) is minimized when the graph is a line. 
\qedhere
%It is sufficient to show that $\alpha\leq d(v_1, v_2)$ where $d$ is the shortest distance in the cell $\hcell$ between $v_1$ and $v_2$, with $v_1, v_2\in\theta\cell$. Recall that $\alpha=f(1)$ is the average number of times a random walks on $\hcell$ starts at $v_1$ before reaching $v_2$. Since $\theta=2$, $v_1$ has only one neighbour, let us call it $w$. For each vertex $v\in\cell$ let $P(v)$ be the probability that a uniform random walk on $\hcell$ starting with $v$ will reach $v_2$ before $v_1$. 

%After each time a random walk reaches v1 the next vertex of the random walk is $w$. Thus we have a try until fail process with the fail corresponding to reaching $v_2$ and a success is reaching $v_1$. This process follows a geometric law of parameter~$P(w)$. Thus, $\alpha=1+\frac{1}{P(w)}$. Starting with a line from $v_1$ to $v_2$, we can see the impact on $P$ of adding edges within $\cell$. 
%Intuitively, each added edge can only increase the quantity $P(w)$ since it will create more pathways from $w$ to $v_2$. Therefore, for a given cell, the parameter $\alpha$ is bounded above by the corresponding $P$ with the minimal number of edges, that is, the line graph $L_n$, with $n=d(v1,v2)$. We have the following inequalities which hold in each case $\hcell$ is not $L_n$:
%Thus, \[\alpha_{\hcell}<\alpha_{L_n}=\mu_{L_n}<|E(\hcell)|=\mu_{\hcell}.\]

%The rigorous proof of this intuition is technical, and reserved for the full paper corresponding to this abstract.



%As in the proof of Corollary 4 of~\cite{kron_asymptotics_2004}, the coefficient of the return function of $\hcell$ is strictly less than the corresponding coefficient for the return function for the line graph on the same number of edges.  Suppose the distance between the vertices in the boundary  is $n$. the probability of returning to $o$ in exactly $2m$ steps is strictly smaller than the corresponding probability for the line $L_n$. From this we can deduce that \[\alpha_{\hcell}<\alpha_{L_n}=\mu_{L_n}<|E(\hcell)|=\mu_{\hcell}.\]
\end{proof}

%-----------------------------------------

\begin{corollary}\label{lem:eta}
    Under the hypotheses of  \Cref{thm:alpha_mu}, $\eta \geq -\dfrac{1}{2}$ with equality if, and only if, $\hcell$ is a line graph. 
\end{corollary}
%-----------------------------------------
\begin{proof}
    Putting together the above equalities, we have the following: \[\eta = -\frac{\log \alpha}{\log \tau} = \frac{\log \mu}{\log \tau}-1 \geq \frac{\log \alpha}{\log \tau} - 1 = -\eta -1.\]
Solving for $\eta$ gives $\eta \geq -\frac{1}{2}.$
\end{proof}
\begin{proof}[Proof of \Cref{lem:bipartite}]
Recall $G^N=P/Q$ with $\deg Q \geq N$ from \Cref{lem:deg} and $\deg Q= -2\eta N$ by \Cref{lem:form_of_Q}. Thus, $-2\eta N\geq N$, hence $\eta \leq -1/2.$  This, coupled with \Cref{lem:eta} suggests that $\eta=-1/2$ precisely.  By \Cref{lem:eta}~this equality holds only if $\hcell$ is a line graph. 
\end{proof}

%-----------------------------------------
\subsection{Case 2: \texorpdfstring{$X$}{X} is non-bipartite}
\label{sec:nonbipartite}
%-----------------------------------------
In this section we assume additionally that $X$ is not bipartite and that $\theta=2$.  We will show that if $G$ is algebraic, and if $G^N$ only has a pole at $z=1$, then we can deduce a contradiction. 

\begin{lemma}\label{lem:non-bipartite}
Let $X$ be a non-bipartite symmetrically self-similar graph with origin $\origin$, bounded geometry and branching number $\theta=2$. Then the Green function $G(z)$ is differentially transcendental over $\mathbb{C}(z)$. 
\end{lemma}

Recall that if $G$ is algebraic, then $\omega$ in \Cref{thm:KT} is constant, and thus the singularities of $G$ are contained in the set $(-\infty, -1]\cup[1, \infty)$. We also know that 1 is the only singularity on the unit disc~\cite[p. 13]{kron_asymptotics_2004}, and that there are no singularities in $(1, \infty)$ by \Cref{lem:no_positive_poles}. 
We next show that there are also no singularities in $(-\infty, -1)$. 
%\begin{lemma}
%\label{lem:21}
%The following statement is true for all real $z_0>1$: $\lim_{z \rightarrow %z_0} d(z) = \infty \Longrightarrow \lim_{z \rightarrow z_0} f(z) = \infty.$ 
%\end{lemma}
%\begin{proof}
 %   Let $z_0 > 1$ such that $\lim_{z\rightarrow z_0} d(z) = \infty$.     \[\lim_{z  \rightarrow z_0} f(z)^N=\lim_{z  \rightarrow z_0} G(z)^N/G(d(z))^N  \]
  %  Now, $G(z_0)\neq 0$, and $\lim_{z\rightarrow \infty} G(z)=0$, therefore $\lim_{z \rightarrow z_0}f(z)=\infty$.
%\end{proof}

\begin{lemma}
 \label{lem:ppt_pole_neg}
If $X$ is not bipartite, $\theta=2$, and $G$ is algebraic, then $G$ has no singularity or zero of smaller than ${-}1$.
\end{lemma}
\begin{proof} 
 Since $\rho_d$ is a pole of order $1$ of $d$, we can deduce that $\lim_{z \rightarrow \rho_d^+} d(z) = -\infty$. We can show $f$ has neither zero nor pole in the interval~$(\rho_f, \rho_r)$, and that $d$ also has no pole in the interval $(\rho_f, \rho_r)$.  Therefore, by intermediate value theorem, given $z_0 \in (-\infty, -1)$, there is some pre-image $z' \in (\rho_f, \rho_r)$ such that $d(z') = z_0$. Since $z' >\rho_f$, $z'$ is a positive real number greater than 1,  therefore, $z'$ is neither a pole nor a zero of $G$.
    We substitute this into the main functional equation to determine that $G(z_0)$ is finite and nonzero. 
    %:
    %%\[ G(z') = f(z')G(d(z')) =  f(z')G(z_0) \implies G(z_0) = \frac{G(z')}%{f(z')} \notin \{0, \infty\}.\]
\end{proof}

\begin{corollary}
Under these conditions, the only zero of $Q$ is at $1$. It is a zero of order $-N\eta$.
\end{corollary} 
\begin{proof}[Proof of \Cref{lem:non-bipartite}]
 By \Cref{lem:form_of_Q},  $\deg Q = -N \eta$. However, by \Cref{lem:deg}, $\deg Q \geq N$. This is a contradiction, as $-\eta<1$. Thus, there are no non-bipartite symmetrically self-similar graphs with both $\theta=2$ and $G$ algebraic.
\end{proof}

Anytime that we can establish that $G$ is algebraic, and that $Q$ only has a zero at $1$, this argument will apply. 

\printbibliography

\end{document}


