\documentclass[12pt]{amsart}
%\usepackage{mathrsfs}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{epstopdf}
\usepackage{amsmath,amscd}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{url,verbatim}

\RequirePackage[colorlinks,citecolor=blue,urlcolor=blue]{hyperref}
%\usepackage[notcite,notref]{showkeys}
\usepackage{breakurl}
\theoremstyle{plain}
%\textwidth=430pt
%\textheight=660pt
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1 `/`basename #1 .tif`.png}
%\setlength{\parindent}{1.5em}

\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{example}[theorem]{Example}
\newtheorem{assumption}[theorem]{Assumption}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{question}[theorem]{Question}

\newcommand{\grg}[1]{{\textcolor{blue}
{[GRG: #1\marginpar{\textcolor{red}{\bf $\bigstar$}}]}}}
\newcommand{\grgr}[1]{{\textcolor{red}
{[GRG: #1\marginpar{\textcolor{red}{\bf $\bigstar$}}]}}}
\newcommand{\zl}[1]{{\textcolor{blue}
{[ZL: #1\marginpar{\textcolor{red}{\bf $\bigstar$}}]}}}


\newcommand\es{\varnothing}
\newcommand\wt{\widetilde}
\newcommand\ol{\overline}
\newcommand\Aut{\mathrm{Aut}}
\newcommand \sA{\mathcal{A}}
\newcommand\sB{{\mathcal B}}
\newcommand\sQ{{\mathcal Q}}
\newcommand\sH{{\mathcal H}}
\newcommand\EE{{\mathbb E}}
\newcommand\sE{{\mathcal E}}
\newcommand\RR{{\mathbb R}}
\newcommand\ZZ{{\mathbb Z}}
\newcommand\NN{{\mathbb N}}
\newcommand\QQ{{\mathbb Q}}
\newcommand\PP{{\mathbb P}}


\renewcommand\a{\alpha}
\newcommand\om{\omega}
\newcommand\g{\gamma}
\newcommand\be{\beta}
\newcommand\si{\sigma}
\newcommand\eps{\epsilon}
\newcommand\De{\Delta}
\newcommand\qq{\qquad}
\newcommand\q{\quad}
\newcommand\resp{respectively}
\newcommand\spz{\mathrm{span}}
\newcommand\rank{\mathrm{rank}}
\newcommand\oo{\infty}
\newcommand\sG{{\mathcal G}}
\newcommand\sD{{\mathcal D}}
\newcommand\sC{{\mathcal C}}
\newcommand\sT{{\mathcal T}}
\newcommand\sN{{\mathcal N}}
\newcommand\sS{{\mathcal S}}
\newcommand\sM{{\mathcal M}}
\newcommand\Ga{\Gamma}
\newcommand\La{\Lambda}
\newcommand\Si{\Sigma}
\newcommand\de{\delta}
\newcommand\la{\lambda}
\newcommand\bid{{\bf I}}
\newcommand\id{{\bf 1}} 
\newcommand\osi{\widehat\si}
\newcommand\oSi{\widehat\Si}
\newcommand\lra{\leftrightarrow}
\newcommand\dih{\mathrm{Dih}}
\newcommand\bzero{{\bf 0}}
\newcommand\bigmid{\,\big|\,}
\newcommand\pc{p_{\text{\rm c}}}
\newcommand\gir{{\text{\rm gir}}}

\renewcommand\ell{l}
\newcommand\SL{\text{\rm SL}}
\newcommand\Tc{T_{\text{\rm c}}}
\newcommand\zc{z_{\text{\rm c}}}
\newcommand\vecol[1]{\ol{\vec #1}}
\newcommand\hcf{\text{\rm hcf}}
\newcommand\vG{\vec G}
\newcommand\olV{\ol V}
\newcommand\olE{\ol E}
\newcommand\olG{\ol G}
\newcommand\vE{\vec E}
\newcommand\pd{\partial}
\newcommand\vpi{\vec \pi}
\newcommand\vmu{\vec\mu}
\newcommand\sAz{\sH}
\newcommand\veol[1]{\vec l_{#1}}
\newcommand\lro[1]{#1^\pm}
\newcommand\ro[1]{#1^\pm}
\newcommand\sm{\,\triangle\,}
\newcommand\ghf{graph height function}
\newcommand\sghf{strong \ghf}
\newcommand\GHF{group height function}
\newcommand\Stab{\mathrm{Stab}}
\newcommand\hdi{$\sH$-difference-invariant}
\newcommand\sap{point of increase}
\newcommand\saps{points of increase}
\newcommand\zcp{cycle property}
\renewcommand\o{{\mathrm o}}
\newcommand\normal{\trianglelefteq}
\newcommand\normalgr{\trianglerighteq}
\newcommand\vvG{\olra G}
\newcommand\olra{\overleftrightarrow}
\newcommand\vvE{\olra E}
\newcommand\EG{\mathrm{EG}}
\newcommand\EGF{\mathrm{EFG}}  %%{\EG^{\mathrm{F}}}
\newcommand\BS{\mathrm{BS}}
\newcommand\dist{\mathrm{dist}}
\newcommand\Od{\mathrm{ord}}
\newcommand\saw{self-avoiding walk}
\newcommand\pde{\partial_{\text{\rm e}}}


\newcommand\sO{{\mathcal O}}

\newcounter{mycount}
\newenvironment{romlist}{\begin{list}{\rm(\roman{mycount})}%
   {\usecounter{mycount}\labelwidth=1cm\itemsep 0pt}}{\end{list}}
\newenvironment{numlist}{\begin{list}{\arabic{mycount}.}%
   {\usecounter{mycount}\labelwidth=1cm\itemsep 0pt}}{\end{list}}
\newenvironment{letlist}{\begin{list}{\rm(\alph{mycount})}%
   {\usecounter{mycount}\labelwidth=1cm\itemsep 0pt}}{\end{list}}
\newenvironment{Alist}{\begin{list}{\MakeUppercase{\alph{mycount}}.}%
   {\usecounter{mycount}\labelwidth=1cm\itemsep 0pt}}{\end{list}}
\newenvironment{problist}{\begin{list}{{\alph{mycount}}}%
   {\usecounter{mycount}\leftmargin=0pt\itemindent=1cm\labelwidth=1cm\itemsep 0pt}}{\end{list}}
   
\numberwithin{equation}{section}
\numberwithin{theorem}{section}
\numberwithin{figure}{section}

\title{Height functions for amenable groups}
\author{Geoffrey R.\ Grimmett}
\address{Statistical Laboratory, Centre for
Mathematical Sciences, Cambridge University, Wilberforce Road,
Cambridge CB3 0WB, UK} 
\email{g.r.grimmett@statslab.cam.ac.uk, }
\urladdr{\url{http://www.statslab.cam.ac.uk/~grg/}}

\author{Zhongyang Li}
\address{Department of Mathematics,
University of Connecticut,
Storrs, Connecticut 06269-3009, USA}
\email{zhongyang.li@uconn.edu}
\urladdr{\url{http://www.math.uconn.edu/~zhongyang/}}
\begin{document}
\begin{abstract}
The connective constant $\mu(G)$ of an infinite transitive graph $G$
is the exponential growth rate of the number of self-avoiding walks 
from a given origin.  Various properties of connective constants depend on
the existence of so-called \lq\ghf s\rq, namely: (i) whether 
$\mu(G)$ is a local function on certain graphs derived from $G$, 
(ii) the equality of $\mu(G)$
and the asymptotic growth rate of bridges,
and (iii) whether there exists a terminating algorithm for approximating $\mu(G)$ to a given degree of accuracy.

Graph height functions are explored here on Cayley graphs of
infinite, finitely presented groups $\Ga$, in which context they are related 
to integer-valued surjective homomorphisms on the finite-index subgroups of $\Ga$.
We prove that the Cayley graphs of infinite, finitely generated, elementary amenable
groups support \ghf s, which are in addition harmonic.
In contrast, we show that the Cayley graph of the first Grichorchuk group,
which is amenable but not elementary amenable, does not have a \ghf.

Examples are given of non-amenable groups without \ghf s,
of which one is the Higman group. 

This work extends the set of groups for which \ghf s are known to exist, and 
resolves in the negative an open question concerning the existence of height functions on 
general transitive graphs.
\end{abstract}

\date{12 October 2015} %%\today}

\keywords{Self-avoiding walk, connective constant, 
Cayley graph,  amenable group, elementary amenable group, Grigorchuk group,
Higman group, Baumslag--Solitar group, graph height function, group height function, harmonic function}
\subjclass[2010]{20F65, 05C30, 60K35, 82B20}
\maketitle

\begin{comment}
\section{Direct Product}
\begin{theorem} Let $G=(\g,S)$ be a Cayley graph with underlying group $\g$ and generator set $S$ satisfying $S=S^{-1}$, $|S|<\infty$. Assume $\g=\g_1\times \g_2$, i.e., $\g$ is the direct product of two subgroups $\g_1$ and $\g_2$. Assume $\g_1$ is a virtually solvable group with a finite-index normal subgroup $\sH$, which is solvable. Then $G$ admits a graph height function.

\end{theorem}

\begin{proof}Since $\g=(\g_1,\g_2)$, for each $s\in S$, $s=(s_1,s_2)$ with $s_1\in \g_1$, and $s_2\in \g_2$. Let 
\begin{eqnarray*}
S_1=\{s_1: \mathrm{there\ exists}\ s\in S,\ \mathrm{s.t.}\ s=(s_1,s_2)\}.
\end{eqnarray*}
Then $s_1$ is a generator set of $\g_1$, and we can construct a (connected) Cayley graph $G_1=(\g_1,S_1)$. Then $G_1$ admits a $\sH$-difference-invariant graph height function. We define $h:\g\to \ZZ$ as follows. For each $\g\in\g$, satisfying $\g=(\g_1,\g_2)$ with $\g_1\in\g_1$, and $\g_2\in\g_2$, let $h(\g)=h_1(\g_1)$. Note that $\sH\times \g_2$ is a finite index normal subgroup of $\g_1\times \g_2$, then $\sH\times \g_2$-difference-invariant, and $h_1$ is $\sH$-difference-invariant. It is straightforward to check that $h$ is a graph height function on $G$.
\end{proof}

We have the following general theorem
\begin{theorem}Let $G_1=(V_1,E_1)$, $G_2=(V_2,E_2)$ be two infinite, connected, vertex-transitive, locally finite graphs. Let $G=(V,E)$ be the direct product of $G_1$ and $G_2$; i.e. $V=(V_1,V_2)$, and $(v_1,v_2)$ is connected to $(v_1',v_2')$ by an edge in $E$ if and only if one of the following conditions holds
\begin{enumerate}
\item $v_1=v_1'$, and $v_2$ and $v_2'$ are connected by an edge in $E_2$.
\item $v_2=v_2'$, and $v_1$ and $v_1'$ are connected by an edge in $E_1$.
\end{enumerate}
If $G_1$ admits graph height function, then $G$ admits a graph height function.
\end{theorem}
\end{comment}

\section{Introduction}\label{sec:intro}

A \emph{\saw} on a graph $G=(V,E)$ is a path that visits no vertex more than once.
The study of the number $\si_n$ of \saw s of length $n$ from a given initial vertex was initiated
by Flory, \cite{f}, in his work on polymerization, and this topic has acquired an iconic status
in the mathematics and physics associated with lattice-graphs. Hammersley and
Morton, \cite{hm}, proved in 1954 that, if $G$ is vertex-transitive, there exists a constant $\mu=\mu(G)$,
called the \emph{connective constant} of $G$, 
such that $\si_n=\mu^{n(1+\o(1))}$ as $n \to\oo$.
This result is important not only for its intrinsic value, but also because its proof 
contained the introduction of
subadditivity to the theory of interacting systems. Subsequent work has concentrated on
understanding polynomial corrections in the above asymptotic for $\si_n$
(see, for example, \cite{bdgs,ms}), and on finding exact values and inequalities for connective constants
(for example, \cite{ds,GrLrev}).

There are several natural questions about connective constants whose answers depend on 
whether or not the underlying graph admits a so-called \ghf.
The first of these is whether $\mu(G)$ is a continuous
function of the graph $G$ (see \cite{Ben13,GL-loc}). This so-called \emph{locality} question
has received serious attention also in the context of percolation and other disordered systems
(see \cite{bnp,mt,psn}),
and has been studied in recent work of the current authors on general transitive
graphs, \cite{GL-loc},  and also on Cayley graphs of finitely generated groups, \cite{GL-Cayley}.
Secondly, when $G$ has a \ghf, one may define 
\emph{bridge} \saw s on $G$, and show that their numbers grow asymptotically
in the same manner as $\si_n$ (see \cite{GL-loc}). 
The third such question is whether there exists a terminating
algorithm to approximate $\mu(G)$ within any given (non-zero) margin of accuracy
(see \cite{GL-loc, GrL3}).

Roughly speaking, a \ghf\ on $G=(V,E)$ is a non-constant 
function $h:V\to\ZZ$ whose increments are invariant
under the action of a finite-index subgroup of automorphisms (a formal definition may be found  
at Definition \ref{def:height}).  It is, therefore, useful to know which transitive graphs support \ghf s. 

A method for constructing \ghf s on a certain class of
transitive graphs is described in \cite{GL-loc},
and the question is posed there of deciding whether all transitive graphs support \ghf s.
A rich source of interesting examples of transitive graphs is provided by Cayley graphs of finitely
generated groups, as studied in \cite{GL-Cayley}. It is proved there that the Cayley graphs
of finitely generated, virtually solvable groups support \ghf s, which are in addition harmonic.
The question is posed of determining whether or not the Cayley graph of the Grigorchuk group
possesses a  \ghf.

The current work has two principal results, one positive and the other negative.
Firstly, it is proved that every Cayley graph of an infinite, finitely generated, 
elementary amenable group supports a \ghf. This extends \cite[Thm 5.1]{GL-Cayley}
beyond the class of virtually solvable groups. Secondly, it is proved that
the Cayley graph of the Grigorchuk group does not support a \ghf. This answers 
in the negative the above question of \cite{GL-loc} (see also \cite[Sect.\ 5]{GL-Cayley}).
Since the Grigorchuk group is amenable (but not elementary amenable), 
possession of a  \ghf\ is not a characteristic of amenable groups.
This is in contrast with work of Lee and Peres, \cite{LeeP}, who have studied the existence of
non-constant, Hilbert space valued, equivariant harmonic
maps on amenable graphs.

An ancillary result is the non-existence of a \ghf\ for the Cayley graph
of two non-amenable groups, namely the Higman group, \cite{Hg}, together with a variant 
with similar properties.  

This paper is organized as follows.
Relevant notation for groups and graphs is summarized
in Section \ref{sec:Cay}, and three different
types of height functions are explained in Section \ref{sec:ht}.
 The class $\EG$ of elementary amenable groups
is introduced in Section \ref{sec:eag}. The existence of \ghf s on infinite, finitely generated
members of $\EG$ is stated in Theorem \ref{eag}. The Grigorchuk group is defined
in Section \ref{sec:grig} and the non-existence of \ghf s thereon is given in Theorem \ref{grig}.
Similarly, the Higman group, together with another `Higman-type' group,
is presented and discussed in Section \ref{sec:hig}. 
Theorem \ref{eag} is proved in Section \ref{sec:proof1}, and Theorems \ref{eag}, \ref{grig},
\ref{thm:hg1}, and \ref{thm:hg2} in Sections \ref{sec:noht}--\ref{sec:pfhig}.

\section{Groups and graphs}\label{sec:Cay}

The graphs $G=(V,E)$ in this paper are \emph{simple}, 
in that they have neither loops nor multiple edges. 
The \emph{degree} $\deg(v)$ of vertex $v\in V$ is the number of edges incident to $v$.
We write $u \sim v$ for neighbours $u$ and $v$,  
$\pd v$ for the neighbour set of $v$, and $\pde v$ for set of edges incident to $v$.
The graph is \emph{locally finite} if $|\pd v|<\oo$ for $v \in V$.  
An edge from $u$ to $v$ is denoted $\langle u,v\rangle$
when undirected, and $[u,v\rangle$ when directed from $u$ to $v$.

The automorphism group of  $G$ is
denoted $\Aut(G)$. The subgroup $\Ga\le\Aut(G)$ is said to act \emph{transitively} on $G$
if, for $u,v\in V$, there exists
$\a\in\Aut(G)$ with $\a(u)=v$. It acts \emph{quasi-transitively} if there exists a finite
subset $W \subseteq V$ such that, for $v\in V$, there exists $\a\in\Ga$ and $w\in W$
such that $\a(v)=w$.
The graph $G$ is said to be \emph{(vertex-)transitive} if $\Aut(G)$ acts transitively
on $V$.

Let $\Ga$ be a group with
generator set $S$ satisfying $|S|<\oo$ 
and $\id\notin S$, where
$\id=\id_\Ga$ is the identity element.  We shall assume that $S^{-1}=S$,
while noting that this  was not assumed in \cite{GL-Cayley}.
We write $\Ga =\langle S \mid R\rangle$ with $R$ a set of relators
(or relations, when convenient).
Such a group is called \emph{finitely generated}, and is called \emph{finitely presented}
if, in addition,  $|R|<\oo$.

The \emph{Cayley graph} of the presentation 
$\Ga=\langle S \mid R\rangle$ is the simple graph $G=G(\Ga,S)$
with vertex-set $\Ga$, and an (undirected) edge $\langle \g_1,\g_2\rangle$ if and only
if $\g_2=\g_1s$ for some $s\in S$. Thus, our Cayley graphs are simple graphs.
See \cite{bab95,LyP} for accounts of Cayley graphs, and \cite{dlH} of geometric group theory.

\section{Height functions}\label{sec:ht}

We review the definitions of the two types of height functions, and introduce a third type.

Let $\sG$ be the set of all infinite, connected, transitive, locally finite, simple graphs,
and let $G=(V,E)\in\sG$. 
Let $\sH \le\Aut(G)$.
A function $F:V \to \RR$ is said to be \emph{\hdi} if 
\begin{equation}\label{eq:hdi2}
F(v)-F(w)=F(\g v)-F(\g w), \qq v,w\in V,\ \g\in \sH.
\end{equation}

\begin{definition}[\cite{GL-loc}] \label{def:height}

A \emph{graph height function} on $G$ is a pair $(h,\sH)$, where 
$\sH\le \Aut(G)$ acts quasi-transitively on $G$ and  $h:V \to \ZZ$, such that:
\begin{letlist}
\item $h(\id)=0$,
\item $h$ is \hdi,
\item for  $v\in V$,
there exist $u,w \in \pd v$ such that
$h(u) < h(v) < h(w)$.
\end{letlist}
\end{definition}

\begin{remark}\label{rem:Poin}
By Poincar\'e's Theorem for subgroups (see \cite[p.\ 48, Exercise 20]{Her}), it is immaterial
whether or not we require $\sH$ to be a \emph{normal} subgroup of $\Aut(G)$
in Definition \ref{def:height}.
\end{remark}

We turn to Cayley graphs of finitely generated groups.
Let $\Ga$ be a finitely generated group with presentation $\langle S\mid R\rangle$.
As in Section \ref{sec:Cay}, we assume $S^{-1}=S$ and $\id \notin S$.

\begin{definition}\label{def:GHF}
A \emph{\GHF}\ on $\Ga$ (or on a Cayley graph of $\Ga$) is a function $h:\Ga\to\ZZ$ such that:
\begin{letlist}
\item $h(\id)=0$, and $h$ is not identically zero,
\item if $\g=s_1s_2\cdots s_m$ with $s_i \in S$, then $h(\g)=\sum_{i=1}^m h(s_i)$,
\item the values $(h(s): s\in S)$ are such that, if $s_1s_2\cdots s_n=\id$
is a representation of the identity with $s_i\in S$, then $\sum_{i=1}^n h(s_i)=0$.  
\end{letlist}
\end{definition}

A necessary and sufficient condition for the existence of a \GHF\ is given in \cite[Thm 4.1]{GL-Cayley}.
In the language of group theory, this condition amounts to requiring that the first Betti number is 
strictly positive.
It was pointed out in \cite[Remark 4.2]{GL-Cayley} that
(when the non-zero $h(s)$, $s\in S$, are coprime) a \GHF\ is simply a surjective homomorphism
from  $\Ga$ to $\ZZ$.

We introduce a third type of height function, which may be 
viewed as an intermediary between a  \ghf\ and \GHF.

\begin{definition}\label{def:sghf}
For a Cayley graph $G$ of
a finitely generated group $\Ga$, we say that the pair $(h,\sH)$ is
a \emph{\sghf} of the pair $(\Ga,G)$ if
\begin{romlist}
\item $\sH\normal \Ga$ acts on $\Ga$ by left multiplication, and $[\Ga:\sH]<\oo$,
\item $(h,\sH)$ is a \ghf.
\end{romlist}
\end{definition}

It is evident that a \GHF\ $h$ (of $\Ga$)  is a \sghf\ of the form $(h,\Ga)$, and a \sghf\ is a \ghf.
The assumption in (i) above of the normality of $\sH$ is benign, as in Remark \ref{rem:Poin}.  

We recall the definition  of a harmonic function. A function $h:V \to\RR$ is called \emph{harmonic}
on the graph $G=(V,E)$ if
$$
h(v) = \frac1{\deg(v)}\sum_{u \sim v} h(u), \qq v \in V.
$$
It is an exercise to show that any \GHF\ is harmonic.

\section{Elementary amenable groups}\label{sec:eag}

The class $\EG$ of elementary amenable groups was introduced by Day in 1957, \cite{Day57}, as the 
smallest class of groups that contains the set $\EG_0$ of all finite and abelian groups, 
and is closed under the operations 
of taking subgroups, and of forming quotients, extensions, and directed unions.
Day noted that every group in $\EG$ is amenable (see also von Neumann \cite{vN}). 
An important example of an amenable but not elementary amenable group was described by 
Grigorchuk in 1984, \cite{Grig84}. 
Grigorchuk's group is important in the study of height functions, and
we return to this in Section \ref{sec:grig}.

Let $\EGF$ be the set of
infinite, finitely generated members of $\EG$. 

\begin{theorem}\label{eag}
Let $\Ga\in\EGF$. Any locally finite Cayley graph $G$ of $\Ga$ admits a harmonic, strong \ghf.
\end{theorem}

We prove a slightly stronger version of this at Theorem \ref{st} in Section \ref{sec:proof1},
using transfinite induction.

The class $\EGF$ includes all virtually solvable groups, and thus Theorem \ref{eag}
extends \cite[Thm 5.1]{GL-Cayley}.
Since any finitely generated group with polynomial growth is virtually nilpotent, \cite{MG81},
and hence lies in $\EGF$, its locally finite Cayley graphs admit harmonic \ghf s.


\section{The first Grigorchuk group}\label{sec:grig}

The (first) Grigorchuk group is an infinite, finitely generated, amenable group that is not elementary amenable.
We show in Theorem \ref{grig} that there exists a 
locally finite Cayley graph of the Grigorchuk group with \emph{no} \ghf.
This answers in the negative Question 3.3 of \cite{GL-loc} (see also \cite[Sect.\ 3]{GL-Cayley}).
 
Here is the definition of the group in question (see \cite{Grig80,Grig84,RG05}).
Let $T$ be the rooted binary tree with root vertex $\es$. 
The vertex-set of $T$ can be identified with the set of finite strings $u$ having entries $0$, $1$, 
where the empty string corresponds to the root $\es$.
Let $T_u$ be the subtree of all vertices with root labelled $u$. 

Let $\Aut(T)$ be the automorphism group of $T$, and
let $a\in\Aut(T)$ be the automorphism
that, for each string $u$, interchanges the two vertices $0u$ and $1u$. 

Any $\g\in\Aut(G)$ may be applied
in a natural way to either subtree $T_i$, $i=0,1$. 
Given two elements 
$\g_0,\g_1\in\Aut(T)$, we define $\g=(\g_0,\g_1)$ to be the automorphism
on $T$ obtained by applying $\g_0$ to $T_0$ and $\g_1$ to $T_1$.
Define automorphisms $b$, $c$, $d$ of $T$ recursively as follows:
\begin{equation}\label{eq:grigrels}
b=(a,c),\quad c=(a,d),\quad d=(e,b),
\end{equation}
where $e$ is the identity automorphism. 
The Grigorchuk group is defined as the subgroup of  $\Aut(T)$ generated by the 
set $\{a,b,c\}$.

\begin{theorem}\label{grig}
The Cayley graph $G=(V,E)$ of the Grigorchuk group with generator set $\{a,b,c\}$ satisfies:
\begin{letlist}
\item $G$  admits no \ghf,
\item for $\sH\leq\Aut(G)$ with finite index, 
any \hdi\  function on $V$ is constant on each orbit of $\sH$.
\end{letlist}
\end{theorem}

The proof of Theorem \ref{grig} is given in Section \ref{sec:pfgrig}.
In the preceding Section \ref{sec:noht}, two approaches are developed for
showing the absence of a \ghf\ within particular classes of Cayley graph. 

Since the Grigorchuk group is amenable,  Theorems \ref{eag} and \ref{grig} yield that:
within the class of infinite, finitely generated groups, every elementary amenable group has a \ghf, but there
exists an amenable group without a \ghf.  The Grigorchuk group is finitely \emph{generated} but not finitely 
\emph{presented}, \cite[Thm 6.2]{Grig84}.
Two Cayley graphs of finitely presented, \emph{non-amenable} groups 
are considered in Section \ref{sec:hig},  one of which is shown to possess no \ghf.

We ask if there exists an infinite, finitely \emph{presented}, amenable group 
with a Cayley graph having no \ghf.
A natural candidate might be the group $\Ga=\langle S\mid R\rangle$ of \cite[Thm 1]{Grig98},
with
\begin{gather*}
S=\{a,c,d,t\},\\
R=\bigl\{a^2=c^2=d^2=(ad)^4=(adacac)^4=\id,
t^{-1}at=aca, t^{-1}ct=dc, t^{-1}dt=c\bigr\}.
\end{gather*}
This finitely presented, amenable HNN-extension of the Grigorchuk group 
is not elementary amenable.
However, since it contains  the free group generated by the stable letter $t$, it possesses a
\GHF. More precisely, the function
$$
h(\id)=0,\q h(t)=1,\q h(t^{-1})=-1,\q \q h(s)=0 \text{ for } s\in S,\ s\ne t^{\pm 1}
$$
defines  a \GHF.

\section{The Higman group}\label{sec:hig}

The \emph{Higman group}  $\Ga$  of \cite{Hg} is the infinite, finitely presented 
group with presentation $\Ga=\langle S \mid R\rangle$ where
\begin{equation}\label{eq:higpres}
\begin{aligned}
S&=\{ a,b,c,d,a^{-1},b^{-1},c^{-1},d^{-1}\},\\ 
R&= \{a^{-1}ba=b^{2},b^{-1}cb=c^{2},c^{-1}dc=d^{2}, d^{-1}ad= a^{2}\}.
\end{aligned}
\end{equation}
This group is interesting since it has no proper normal subgroup with finite index, and the
quotient of $\Ga$ by its maximal proper normal 
subgroup is an infinite, finitely generated, simple group. 
By \cite[Thm 4.1(b)]{GL-Cayley}, $\Ga$ has no \GHF.

\begin{theorem}\label{thm:hg1}
The Cayley graph $G=(V,E)$ of the Higman group $\Ga=\langle S\mid R\rangle$ has no \ghf.
\end{theorem}

A further group of Higman type is given as follows. 
Let $S$ be as above, and let $\Ga'=\langle S\mid R' \rangle$ be the finitely presented group with
\begin{equation*}
R'=\{a^{-1}ba=b^{2},b^{-2}cb^2=c^{2},c^{-3}dc^3=d^{2}, d^{-4}ad^4= a^{2}\}.
\end{equation*}
Note that $\Ga'$ is infinite and non-amenable, since the subgroup generated by 
the set $\{a,c,a^{-1},c^{-1}\}$  is a free group (as in the corresponding
step for the Higman group at \cite[pp.\ 62--63]{Hg}).

\begin{theorem}\label{thm:hg2}
The Cayley graph $G=(V,E)$ of the above group $\Ga'=\langle S\mid R'\rangle$ has no \ghf.
\end{theorem}

The proofs of the above theorems are given in Sections \ref{sec:pfhg} and \ref{sec:pfhig}, \resp.

\section{Proof of Theorem \ref{eag}}\label{sec:proof1}

We shall prove the following stronger form of Theorem \ref{eag}. 

\begin{theorem}\label{st}
Let $\Ga\in\EGF$. 
There exists a normal subgroup $\sH\normal\Ga$
with $1<[\Ga:\sH]<\oo$ such that any locally finite Cayley graph $G$ of 
$\Ga$ possesses a harmonic, \sghf\ of the form $(h,\sH)$.
\end{theorem}
 
Whereas every member of $\EGF$ has a proper, normal subgroup
with finite index, it is proved in \cite{JM} that there exist amenable \emph{simple}
groups.

We review next the structure of $\EG$. Let $\EG_0$ be the class of all groups
that are either finite or abelian (or both), and let $\sO$ be the set of all ordinals. 
Let $\alpha\in\sO$, $\a\ne 0$, and assume we have defined $\EG_{\beta}$ for each $\be\in\sO$,
$\beta<\alpha$. Each $\a\in\sO$ is either a limit ordinal or a successor ordinal.
If $\alpha$ is a limit ordinal, we set 
\begin{equation}\label{eq:limitord}
\EG_{\alpha}=\bigcup_{\be<\a} \EG_{\beta}.
\end{equation}
If $\alpha$ is a successor ordinal, let $\EG_{\alpha}$ be the class of groups 
which can be obtained from members of $\EG_{\alpha-1}$ by no more
than  one operation of extension or directed union.

\begin{theorem}[\cite{CH80}]\label{lem:cc}
We have that $\EG=\bigcup_{\a\in\sO} \EG_{\alpha}$.
\end{theorem}

\begin{proof}[Proof of Theorem \ref{st}]

Let $\EGF_\a=\EGF \cap \EG_\a$.  
For $\a\in\sO$, let H$_\a$ be the following statement:
\begin{itemize}
\item [$\text{H}_\a$\ :] for $\be\in\sO$, $\beta\le\alpha$, and $\Ga\in \EGF_{\beta}$, there exists
$\sH\normal\Ga$ such that every locally finite Cayley graph of $\Ga$ admits
a harmonic, \sghf\ of the form $(h,\sH)$.
\end{itemize}

Now, $\EGF_0$ is the set of infinite, finitely generated, abelian groups. 
By \cite[Prop.\ 4.3, Thm 5.2(b)]{GL-Cayley}, any locally finite Cayley graph of $\Ga$ has a 
\GHF, and hence a harmonic, \sghf\ of the form $(h,\Ga)$. Therefore, H$_0$ holds, and we turn to the 
induction step.

Let $\a\in\sO$, $\a\ne 0$, and assume H$_\be$ holds for all $\be< \a$. 
Let $\Ga\in \EGF_{\alpha}$ with $\a$ the smallest such ordinal.
There are two cases to consider, depending on whether or not $\a$ is a limit ordinal.
\emph{If $\alpha$ is a limit ordinal}, by \eqref{eq:limitord},
there exists $\be\in\sO$, $\be < \a$, such that $\Ga\in\EGF_\be$. 
The claim now follows by H$_\be$. 

\emph{We assume for the remainder of this proof that $\a$ is a successor ordinal.}
By Theorem \ref{lem:cc}, the group $\Ga\in\EGF_\a$ is obtained from groups in $\EGF_{\alpha-1}$ by 
exactly one operation of either extension or directed union. 
That is, there are two sub-cases to consider.
\begin{letlist}
\item There exist $\sN',\sQ'\in \EGF_{\alpha-1}$ such that $\sN'$ is isomorphic to a 
normal subgroup $\sN$ of $\Ga$, and $\sQ'\simeq \sQ:=\Ga/\sN$.
\item There exist a directed set $\La$ and a family $(S_{\lambda}:\lambda\in \Lambda)$ 
satisfying 
\begin{romlist}
\item $S_\la\in\EGF_{\a-1}$, 
\item $S_{\lambda_1}\subseteq S_{\lambda_2}$ whenever $\la_1\le\la_2$, 
\item $\Ga=\bigcup_{\lambda\in \Lambda}S_{\lambda}$.
\end{romlist}
\end{letlist}

\medskip
\noindent
{\bf Assume (a) holds.}
Since $\Ga$ is finitely generated, so is $\sQ$. 

\medskip\noindent
\emph{Suppose $\sQ$ is infinite.}
We shall use the fact that $\sQ\in \EGF_{\alpha-1}$. Let $S$ be a finite set of generators of $\Ga$
with $S=S^{-1}$ and $\id\notin S$,
and let $G=G(\Ga,S)$ be the corresponding  Cayley graph of $\Ga$. 
A locally finite Cayley graph $G_{\sQ}$ of $\sQ$ may be constructed as follows. 
Let
\begin{equation*}
\ol{S}=\{\ol{s}=s\sN:  s\in S\},
\end{equation*}
be the (finite) generator set of $\sQ$ derived from $S$.
The vertex-set of $G_{\sQ}=G_\sQ(Q,\ol S)$ is the set of cosets $\{\ol v:= v\sN: v \in \Ga\}$,
and two such vertices $\ol{v}$, $\ol{w}$ are connected by an edge of $G_{\sQ}$ if and only if there exist  
$v\in\ol{v}$, $w\in\ol{w}$ such that $v$ and $w$ are connected by an edge in $G$. 

By H$_{\a-1}$, there exists $\ol\sH\normal\sQ$, not depending
on the choice of $S$, such that $G_\sQ$
admits a harmonic, \sghf\ $(h_\sQ,\ol\sH)$.
Let $h:\Ga\to\ZZ$ and $\sH\subseteq\Ga$ be given by
\begin{equation}\label{eq:4}
 h(v)=h_{\sQ}(\ol{v}),\qq
\sH=\bigcup_{\g\sN\in\ol\sH} \g\sN.
\end{equation}
The following lemma completes the proof of this case.

\begin{lemma}\label{lem:2}
We have that:
\begin{romlist}
\item $\sH\normal\Ga$, and $\sH$ acts quasi-transitively on $G$ by left-multiplication,
\item the pair $(h,\sH)$ is a harmonic, \sghf\ of $G$.
\end{romlist}
\end{lemma}

\begin{proof}
(i) Since $\ol\sH\normal\sQ$, we have that $(a\sN)\ol\sH(a\sN)^{-1}=\ol\sH$ for $a\in \Ga$,
whence 
\begin{equation}\label{eq:3}
(a\g a^{-1})\sN \in \ol\sH\q \text{whenever}\q a,\g\in\Ga,\ \g\sN\in\ol\sH.
\end{equation}
It is elementary that, for $a\in \Ga$ and $\g_1\sN,\g_2\sN\in\ol\sH$,
\begin{equation}\label{eq:5}
(a\g_1 a^{-1})\sN = (a\g_2a^{-1})\sN \q \text{if and only if}\q \g_1\sN=\g_2\sN. 
\end{equation}

Since $\ol\sH$ is a group, so is $\sH$. For $a\in \Ga$, by \eqref{eq:4}--\eqref{eq:5},
\begin{align*}
a\sH a^{-1}&=\bigcup_{\g \sN \in \ol\sH} a(\g\sN)a^{-1}
=\bigcup_{\g\sN\in\ol\sH} (a\g a^{-1})\sN\\
&=\bigcup_{\g\sN\in\ol\sH} \g \sN = \sH.
\end{align*}
Therefore, $\sH\normal \Ga$. We prove next that $[\Ga:\sH]<\oo$.

Since $(h_\sQ,\ol\sH)$ is a \ghf, we have that $[\sQ:\ol\sH]<\oo$.
Let $\ol{W}_1, \ol{W}_2,\dots,\ol{W}_k$ be the cosets of $\ol{\sH}$ in $\sQ$,
and let 
\begin{equation*}
W_i=\bigcup_{\g\sN \in \ol W_i} \g\sN.
\end{equation*}
We show next that each $W_i$ is contained in an orbit of $\sH$ acting
on $\Ga$.  (Actually the $W_i$ \emph{are} the orbits.) It follows that $\sH$ acts
quasi-transitively on $G$.

Without loss of generality, let $u,v \in W_1$. We shall show that there exists
$\nu\in\sH$ such that $v=\nu u$.
Suppose $u \in a\sN$, $v \in b\sN$ where $a\sN, b\sN  \in \ol W_1$. 
There exists $\g\sN\in\ol\sH$ such that $\g\sN a\sN=b \sN$, which is to
say that  $a\sN b^{-1}\in\ol\sH$.

There exist $n_i$ such that $u=an_1$, $v=b n_2$. Then, $u=(an_1n_2^{-1}b^{-1})v$,
and $\nu:=a(n_1n_2^{-1})b^{-1}\in \sH$ by \eqref{eq:4}.

(ii) It is trivial that $h(\id)=h_{\sQ}(\ol\id)=0$.
For $\g\in \sH$ and $u,v\in \Ga$, we have
\begin{alignat*}{2}
h(\g u)-h(\g v)&=h_{\sQ}(\ol{\g}\ol{u})-h_{\sQ}(\ol{\g}\ol{v})\\
&=h_\sQ(\ol\g\, \ol u)-h_\sQ(\ol\g\, \ol v)\q&&\text{since $\sN$ is normal}\\
&=h_{\sQ}(\ol{u})-h_{\sQ}(\ol{v}) &&\text{since $h_\sQ$ is $\ol \sH$-difference invariant, 
$\ol\g\in\ol\sH$}\\
&=h(u)-h(v).
\end{alignat*}
Therefore, $h$ is \hdi.

For $v\in \Ga$, there exist $\ol{s}_1, \ol{s}_2\in \ol S$ such that
\begin{equation*}
h_{\sQ}(\ol{v}\,\ol{s}_1)<h_{\sQ}(\ol{v})<h_{\sQ}(\ol{v}\,\ol{s}_2),
\end{equation*}
whence, since $\sN$ is a normal subgroup of $\Ga$,
\begin{equation*}
h(vs_1)<h(v)<h(vs_2).
\end{equation*}
In conclusion, $(h,\sH)$ is a \sghf\ of $G$.

We show finally that $h$ is harmonic on the Cayley graph $G=(V,E)$.  The edges
incident to the vertex labelled $\g \in \Ga$ have the form $\langle \g, \g s\rangle$ for $s \in S$. 
Since $h_\sQ$ is harmonic on the quotient graph,
it suffices to show that the cardinality $N_s:=|\pd\g \cap (\g\sN s)|$ does not 
depend on the choice of $s\in 
S \setminus \sN$. For $s\in S\setminus \sN$ and  $n \in \sN$, $\g \sim \g ns$ if and only if
$ns\in S$, which is to say that $n \in s^{-1}S$, whence $N_s=|S|$.
\end{proof}

\medskip
\noindent
\emph{Suppose $\sQ$ is finite.}
Since $\sN\simeq\sN'\in\EGF_{\a-1}$, we have that $\sN\in \EGF_{\alpha-1}$ and $1<[\Ga:\sN]<\oo$. 
By H$_{\a-1}$, there exists $\sH'\normal\sN$ with $[\sN:\sH']<\oo$ such that any
locally finite Cayley graph $G_{\sN}$ of $\sN$
admits a \sghf\ of the form $(h_{\sN},\sH')$. 

Since $|\Ga/\sH'|=|\Ga/\sN|\cdot|\sN/\sH'|<\oo$, there exists (by Poincar\'e's Theorem for
subgroups) a subgroup $\sH\le \sH'$ that is normal in $\Ga$ with finite index, that is,
$\sH\normal \Ga$ and $1<[\Ga:\sH]<\oo$. Choose a locally finite Cayley graph $G_\sN$ of
$\sN$, and find a \sghf\ of the form $(h_\sN,\sH')$. Let $F:\sH\to\ZZ$ be the restriction
of $h_\sN$ to $\sH$. 

\begin{lemma}\label{lem:GHF}
The function $F$ is a \GHF\ on the group $\sH$.
\end{lemma}

\begin{proof}
As noted in \cite[Remark 4.2]{GL-Cayley}, a \GHF\ is 
a homomorphism from $\sH$ to $\ZZ$ that is not identically zero. For $\g_1,\g_2\in\sH$,
\begin{align*}
F(\g_1\g_2)-F(\g_1) &= h_\sN(\g_1\g_2)-h_\sN(\g_1)\\
&=h_\sN(\g_2)-h_\sN(\id)=F(\g_2),
\end{align*}
since $\g_1\in\sH'$ and $h_\sN$ is $\sH'$-difference invariant.
Therefore, $F$ is a homomorphism.  

It suffices now to show that $F\not\equiv 0$ on $\sH$.
Assume the converse, that $F \equiv 0$ on $\sH$.
For $\g\in\Ga$, there exists $a_\g\in \sN$ such that $\g\in a_\g \sH$,
so that $\g=a_\g\nu$ for $\nu\in\sH$. Since $h_\sN$ is
$\sH$-difference-invariant,
\begin{equation}\label{eq:6}
h_\sN(\g) = h_\sN(a_\g) + F(\nu) = h_\sN(a_\g).
\end{equation}
Now $|\sN/\sH|<\oo$, so we may restrict consideration to only finitely many $a_\g$.
Therefore, $h_\sN(\g)$ is bounded, which is impossible since $h_\sN$ is
a \ghf. We deduce that $F\not\equiv 0$ on $\sH$.
\end{proof}

Let $G=G(\Ga,S)$ be a locally finite Cayley graph of $\Ga$.
The triple $(\Ga,\sH,F)$ satisfies the conditions
of \cite[Thm 3.5]{GL-Cayley} with $\sH$ acting by left multiplication, and it follows that $G$ possesses
a harmonic \ghf\ of the form $(h,\sH)$.
 
\medskip\noindent
{\bf Assume (b) holds.}
Let $\Ga$ be finitely generated with finite generator set $S=\{s_1,s_2,\dots,s_k\}$. 
Since $\Ga=\bigcup_{\la\in \La}S_{\lambda}$, there exists $\la_i\in \La$ such that $s_i\in S_{\la_i}$. Let $L=\max\{\lambda_1,\la_2,\dots,\lambda_k\}$, so that $S_{L}=\Ga$. 
Then $\Ga\in \EGF_{\alpha-1}$, which contradicts the
minimality of $\a$.  
\end{proof}

\section{Criteria for the absence of height functions}\label{sec:noht}

This section contains some observations relevant to proofs of the non-existence
of \ghf s.

Let $\Ga=\langle S \mid R\rangle$ where $|S|<\oo$, and
let $G=(V,E)$ be the corresponding Cayley graph. Let
$\Pi$ be the set of permutations of $S$ that preserve $\Ga$
up to isomorphism, and write $e \in \Pi$ for the identity. 
Thus, $\pi\in\Pi$ acts on $\Ga$ by: for $w=s_1s_2\cdots s_m$
with $s_i\in S$, we have $\pi(w)=\pi(s_1)\pi(s_2)\cdots \pi(s_m)$.
It follows that  $\Pi\subseteq \Aut(G)$.
For $\g=g_1g_2\cdots g_n\in\Ga$ with $g_i \in S$, and $\pi\in\Pi$, 
we define $\g\pi\in\Aut(G)$ by $\g\pi(w)=g_1g_2\cdots g_n \pi(w)$,
$w\in V$. Write $\Ga\Pi\subseteq \Aut(G)$ for the subgroup containing all such $\g\pi$,
and note that $\g e$ operates on $G$ in the manner of
$\g$ with left-multiplication.

The \emph{stabilizer} $\Stab_v$ of  $v\in V$
is the set of automorphisms of $G$ that preserve $v$, that is,
$$
\Stab_v = \{\eta\in\Aut(G): \eta(v)=v\}.
$$

\begin{proposition}\label{thm:stab}
Suppose $\Stab_\id=\Pi$. 
\begin{letlist}
\item $\Aut(G) = \Ga\Pi$.
\item If $\sM \normal \Aut(G)$ has finite index,  the subgroup
 $\sN = \sM\cap \Ga$ satisfies $\sN \normal \Ga$ and $[\Ga:\sN]<\oo$.
\item If $G$ has a \ghf, then it has a \sghf.
\end{letlist}
\end{proposition}

\begin{proof}
Assume $\Stab_\id=\Pi$. 

(a)
Let $\eta\in\Aut(G)$, and write $\g=\eta(\id)$. Then $\g^{-1}\eta\in\Stab_\id$,
which is to say that $\g^{-1}\eta=\pi\in\Pi$, and thus
$\eta=\g\pi \in \Ga\Pi$ so that $\Aut(G)=\Ga\Pi$. Note for future use that
$$
[\Aut(G):\Ga] = |\Pi| < \oo.
$$

(b) 
Let $\sM\normal \Aut(G)$ be a finite-index normal subgroup,
and let $\sN=\{\g e: \g e \in \sM\}$. Viewed as automorphisms,
we have that $\g e= \g$, and hence $\sN \le \Ga \le \Aut(G)$.
For $\a\in\Ga$, $\nu\in \sN$, we have that $(\a^{-1}\nu\a) e =\a^{-1}(\nu e)\a \in \sM$, 
since $\sM \normal \Aut(G)$. Therefore, $\sN \normal \Ga$.

Since $\Ga,\sM\le \Aut(G)$ and $\sN =\Ga \cap \sM$, we have that
$$
[\Aut(G):\sN] \le [\Aut(G):\Ga]\cdot[\Aut(G): \sM]<\oo,
$$
which implies $[\Ga:\sN]<\oo$, as required.

(c) Let $(h,\sH)$ be a \ghf\ of $G$. Since $\sH$ is a finite-index normal subgroup of $\Aut(G)$,
by part (b), there exists $\sN \le \sH$ that is a finite-index normal subgroup of $\Ga$.
Since $\sN \le \sH$, $h$ acts on $\Ga$ and is $\sN$-difference invariant,
whence $(h,\sN)$ is a \sghf. 
\end{proof}

\begin{corollary}\label{cor}
Let $\Ga=\langle S\mid R\rangle$ have Cayley graph $G$ satisfying $\Stab_\id = \Pi$.
\begin{letlist}
\item  If $\Ga$ has no proper, normal subgroup with finite index, any \ghf\ of
$G$ is also a \GHF\ of $\Ga$.

\item  If every element in $\Ga$ has finite order, then $G$ has no \ghf.
\end{letlist}
\end{corollary}

\begin{proof}
(a) Let $(h,\sM)$ be a \ghf\ of $G$.
If $\Ga$ satisfies the given condition then, by Proposition \ref{thm:stab}(b), $\sM \supseteq \Ga$.
Therefore, $(h,\Ga)$ is a \ghf\ and hence a \GHF.

(b) If $G$ has a \ghf, by Proposition \ref{thm:stab}(c), $G$ has a \sghf\ $(h,\sN)$.
Assume every element of $\Ga$ has finite order.
For $\g\in \sN$ with $\g^n=\id$,
we have that $h(\g^n)=nh(\g)=0$, whence $h \equiv 0$ on $\sN$.

We now use the argument around \eqref{eq:6}. For $\g\in\Ga$, find $\a_\g$ such that $\g\in\a_\g\sN$.
Since $h$ is $\sN$-difference-invariant, there exists $\nu\in \sN$ such that
\begin{equation}\label{eq:6.2}
h(\g) =h(\a_\g) + h(\nu)=h(\a_\g).
\end{equation}
Now $[\Ga:\sN]<\oo$, so we may consider only finitely many choices for $\a_\g$. Therefore,
$h$ is bounded on $\Ga$, in contradiction of the assumption that it is a \ghf.
\end{proof}



\section{Proof of Theorem \ref{grig}} \label{sec:pfgrig}

The main step is to show that 
\begin{equation}\label{eq:triv}
\Stab_\id=\{e\},
\end{equation}
where $e$ is
the identity of $\Aut(G)$. Once this is shown, the result follows from
Corollary \ref{cor}(b) and the fact that every element of the Grigorchuk
group has finite order, \cite{dlH}.  
It therefore suffices to show \eqref{eq:triv}, and
to this end we study the structure of the Cayley graph $G=(V,E)$.

It was shown in \cite{L85} (see also \cite[eqn (4.7)]{RG05}) that $\Ga = \langle S \mid R\rangle$
where $S=\{a,b,c,d\}$, $R$ is the following  set of relations
\begin{align}\label{eq:relations}
\id&=a^2=b^2=c^2=d^2=bcd\\
&=\si^k((ad)^4)=\si^k((adacac)^4),
\qq k = 0,1,2,\dots,
\nonumber
\end{align}
and $\si$ is the substitution
$$
\si: \begin{cases} a \mapsto aca,\\
b \mapsto d,\\
c \mapsto b,\\
d \mapsto c.
\end{cases}
$$
It follows that the following, written in terms of the reduced generator set
$\{a, b, c\}$ after elimination of $d$, are valid relations:
\begin{equation}\label{eq:relations2}
\id = a^2=b^2=c^2=(bc)^2=(abc)^4=(ac)^8=(abcacac)^4=(acab)^8=(ab)^{16},
\end{equation}
(see also \cite[Sect.\ 1]{RG05}).
Note the asymmetry between $b$ and $c$ in that $ab$ (\resp, $ac$) has order $16$ (\resp, $8$).

Let
\begin{equation*}
V_n=\{v\in\Ga: \dist(v,\id)=n\},
\end{equation*}
where $\dist$ denotes graph-distance on $G$.
Since $G$ is locally finite, $|V_n|<\infty$. 
For $\eta\in \Stab_\id$, $\eta$ restricted to $V_n$ 
is a permutation of $V_n$. As illustrated in Figure \ref{fig:G},
$$
V_0=\{\id\},\qq V_1=\{a,b,c\},\qq V_2=\{ab,ac,ba,bc=cb, ca\}.
$$

\begin{figure}[htbp]
\centerline{\includegraphics*[width=0.35\hsize]{G}}
   \caption{The subgraph of $G$ on $V_0\cup V_1\cup V_2$.}
   \label{fig:G}
\end{figure}

Let $\eta\in\Stab_\id$, so that $\eta(a)\in V_1$. Since the shortest cycles using the edges 
$\langle\id,b\rangle$ and $\langle\id,c\rangle$ have length $4$, and using $\langle\id,a\rangle$
greater than $4$ (see Figure \ref{fig:G}), we have that
$\eta(a)=a$.
By a similar argument,  we obtain that, for $n \ge 1$,
\begin{equation}\label{eq:a}
\eta(va)=\eta(v)a, \qq v \in V_n,\ va\in V_{n+1},
\end{equation}
which we express by saying that $\eta$ maps $a$-type edges to $a$-type edges.

We show next that
\begin{equation}\label{eq:b}
\eta(vc)=\eta(v)c, \qq v \in V,\ \eta\in\Stab_\id,
\end{equation}
which is to say that $\eta$ maps $c$-type edges to 
$c$-type edges. By \eqref{eq:a}--\eqref{eq:b}, $\eta\in \Stab_\id$ maps
$b$-type edges to $b$-type edges also, whence $\eta=e$ as required. It remains to
prove \eqref{eq:b}.

Assume, in contradiction of \eqref{eq:b}, 
that there exists $v\in V$, $\eta\in \Stab_\id$ such that $\eta(vc)=\eta(v)b$. 
Since $ac$ has order $8$, we have that $(ca)^8=\id$.
Let $C$ be the directed cycle corresponding to the word $v (ca)^8$; thus, $C$ includes the edge 
$[ v,vc \rangle$. Then $\eta(C)$ is a cycle of length 
$16$ including the edge $[ \eta(v),\eta(v)b\rangle$. 
Since $C$ contains exactly $8$ $a$-type edges at alternating positions, by \eqref{eq:a},
so does $\eta(C)$.
Therefore, $\eta(C)$ has the form $\eta(v)ba\prod_{i=2}^{8}(x_i a)$, where $x_i\in\{b,c\}$ 
for $i=2,3,\dots,8$. In particular,
\begin{equation}\label{eq:ax}
ba\prod_{i=2}^{8}(x_ia)=\id, \qq x_i\in\{b,c\},\  i=2,3,\dots,8.
\end{equation}

The  word problem of the Grigorchuk group is solvable (see \cite{Grig84}
and \cite[Sect.\ 4]{RG05}),
in that there exists an algorithm to determine whether or not $w=\id$ for any 
given word $w\in \{a,b,c\}^*$. 
By applying this algorithm (see below), we deduce that \eqref{eq:ax}
has no solution. Equation \eqref{eq:b} follows, and the proof
is complete.

Finally, here is a short amplification of the analysis of \eqref{eq:ax}.
The word in \eqref{eq:ax} has the form  $b(ay_1a)z_1(ay_2a)z_2(ay_3a)z_3(ay_4a)$, where
$y_i,z_j \in\{b,c\}$. By \eqref{eq:grigrels}, the effect of such a word on the right sub-tree $T_1$
is $\g_1:=ca(c/d)a(c/d)a(c/d)a$, where each term of the form $(y/z)$ is to be interpreted as 
\lq either $y$ or $z$'.
The effect of $\g_1$ on the left sub-tree $T_{10}$ of $T_1$ is $\g_{10}:=
a(d/b)(a/e)(d/b)$. If there is an odd number of appearances
of $a$ in $\g_{10}$, then $\g_{10}$ is not the identity, and thus we may assume  $\g_{10}:= a(d/b)a(d/b)$.
It is immediate that none of the four possibilities is the identity, and the claim follows.

\section{Proof of Theorem \ref{thm:hg1}}\label{sec:pfhg}

We shall prove three statements:
\begin{romlist}
\item $\Ga$ has no \GHF,
\item $\Pi$ is
the cyclic group generated by the permutation $(abcd)$, with the convention that $\eta(x^{-1})
= \eta(x)^{-1}$, for $\eta\in\Pi$, $x\in\{a,b,c,d\}$,
\item $\Stab_\id=\Pi$.
\end{romlist}
It is proved in \cite{Hg} that the Higman group has
no proper, finite-index, normal subgroup, and
the result follows from the above statements by Corollary \ref{cor}(a).

(i)
The absence of a \GHF\ is immediate by \cite[Example 6.3]{GL-Cayley}.

(ii)
Evidently, $\Pi$ contains the given cyclic group, and we turn to the converse.
Since elements of $\Pi$ preserve $\Ga$ up to isomorphism,
\begin{equation}\label{eq:345}
\eta(x^{-1})=\eta(x)^{-1}, \qq x \in S.
\end{equation}
We next rule out the possibility that $\eta(x)=y^{-1}$ for some $x,y\in\{a,b,c,d\}$.
Suppose, for illustration, that $\eta(a)=b^{-1}$. By \eqref{eq:345}, the relation $a^{-1}ba=b^2$
becomes $b\be b^{-1}=\be^2$ where $\be=\eta(b)$. The Higman group has no such relation
with $\be \in S$. In summary,
\begin{equation}\label{eq:346}
\eta(x)\in\{a,b,c,d\},\q \eta(x^{-1})=\eta(x)^{-1}, \qq x \in \{a,b,c,d\}.
\end{equation}

The shortest cycles containing the edge $\langle \id,a\rangle$, 
modulo rotation and reversal, arise
from the relations
$ab^2 a^{-1}b^{-1}=\id$  and $ada^{-2}d^{-1}=\id$
(see Figure \ref{fig:BS-sheet}).
The first uses $a^{\pm1}$ twice and $b^{\pm1}$ thrice, and the second uses
$a^{\pm1}$ thrice and $d^{\pm1}$ twice. Let $\eta\in\Pi$, and suppose for illustration that 
$\eta(a)=b$ (the same argument is valid for any $\eta(x)$, 
$x\in\{a,b,c,d\}$). 
By considering the cycles starting $\langle\id,b\rangle$, 
$\langle\id,c\rangle$, $\langle\id, d\rangle$, and using \eqref{eq:346}, we deduce that
$$
\eta(b)=c, \q \eta(c)=d, \q \eta(d)=a,
$$
and the claim is proved.

\begin{figure}[htbp]
\centerline{\includegraphics*[width=0.6\hsize]{BS2}}
   \caption{Part of the Cayley graph 
   of the Baumslag--Solitar group $\BS(x,y)$.}
   \label{fig:BS-Cayley}
\end{figure}

(iii)
We begin with some observations concerning the Baumslag--Solitar ($\BS$) group $\BS(x,y)$
with presentation $\langle x,y,x^{-1}, y^{-1} \mid x^{-1}yx=y^2\rangle$,
of which the Cayley graph is sketched in Figure \ref{fig:BS-Cayley}.
Edges of the form $\langle\g,\g x^{\pm 1}\rangle$ have \emph{type} $x$,
and of the form $\langle\g,\g y^{\pm 1}\rangle$  \emph{type} $y$. By inspection, 
the shortest cycles have length $5$ (see Figure \ref{fig:BS-sheet}), 
and, for $\g\in\BS(x,y)$,
\begin{align}\label{eq:22}
&\text{for $p,q=\pm 1$, the edges $\langle\g,\g x^p\rangle$ and $\langle\g,\g y^q\rangle$ 
lie in a common $5$-cycle,}\\
&\text{the third edge of any directed $5$-cycle beginning $[ \g, \g x\rangle$ has type $y$,}\label{eq:22.5}\\
&\text{the third edge of any directed $5$-cycle beginning $[ \g,\g x^{-1}\rangle$ has type $x$,}\label{eq:22.6}\\
&\text{every $5$-cycle contains two consecutive edges of type $y$, and not of type $x$,}\label{eq:22.7}\\
&\text{a type $x$ (\resp, type $y$) edge lies in $2$ (\resp, $3$) 5-cycles.}
\label{eq:23}\end{align}

\begin{figure}[htbp]
\centerline{\includegraphics*[width=0.44\hsize]{BS-fol}}
   \caption{Part of one `sheet' of the Cayley graph of $\BS(x,y)$.}
   \label{fig:BS-sheet}
\end{figure}

Returning to the Higman group, for convenience, we relabel the vector
$(a,b,c,d)$ as $(s_0,s_1,s_2,s_3)$,
with addition and subtraction of indices modulo $4$.
Let $G$ be the Cayley graph of the Higman group $\Ga=\langle S\mid R\rangle$, rooted at $\id$. An edge
of $G$ is said to be of \emph{type} $s_i$ if it has the
form $\langle \g,\g s_i^{\pm 1}\rangle$ with $\g\in\Ga$. We explain next how
to obtain  information about the types of the edges of $G$, by examination of $G$ only, 
and without further information about the vertex-labellings as elements of $\Ga$.

We consider first the set $\pde \id$ of edges of $G$ incident to $\id$.
Let $e_1=\langle \id,v\rangle $, $t\in\{0,1,2,3\}$, and $p\in\{-1,1\}$. 
Assume that 
\begin{equation}\label{eq:ass1}
v=s_t^ p,
\end{equation}
so that, in particular, $e_1$ has type $s_t$.
By \eqref{eq:22}, for $j=\pm 1$, $e_1$ lies in a $5$-cycle of
$\BS(s_{t-1},s_t)$ (\resp, $\BS(s_t,s_{t+1})$) containing $\langle\id, s_{t-1}^j\rangle$
(\resp, $\langle\id, s_{t+1}^j\rangle$).
On the other hand, by consideration of the relator set $R$, 
$e_1$ lies in no $5$-cycle including an edge of type $s_{t+2}$.
Therefore, the edges  of the form $\langle \id , s_{t+2}^{\pm 1}\rangle$
may be identified by examination of $G$, 
and we denote these as $g_1$, $g_2$. 
There is exactly one further edge of $\pde\id$ that lies in no $5$-cycle containing
either $g_1$ or $g_2$, and we denote this edge as $e_2$.
In summary, 
$$
\{e_1,e_2\}=\bigl\{\langle \id,s_t^{-1}\rangle,\langle \id,s_t\rangle\bigr\},\qq
\{g_1,g_2\} =\bigl\{\langle \id,s_{t+2}^{-1}\rangle, \langle \id,s_{t+2}\rangle\bigr\}.
$$ 

Having identified the edges of $\pde\id$ with types $s_t$ and $s_{t+2}$,
we move to the other endpoint $v=s_t^p$ of $e_1$, and apply the same argument.
Let $e_1$, $e_1'$ be the two type-$s_t$ edges incident to $v$.

We turn next to the remaining four edges of $\pde\id$. Let $k$ be such an edge, and
consider the property: \emph{$k$ lies in a $5$-cycle of $G$ containing both $e_1$
and $e_1'$}.
By \eqref{eq:22.7} and examination of
the Cayley graphs of the four groups $\BS(s_i,s_{i+1})$, $0\le i < 4$,
we see that $k$ has this property if it has type $t-1$, and not if it has type  $t+1$.
Thus we may identify the types of the four remaining edges of $\pde\id$, which
we write as 
$$
\{f_1,f_2\}=\bigl\{\langle \id,s_{t+1}^{-1}\rangle,\langle \id,s_{t+1}\rangle\bigr\},\qq
\{h_1,h_2\} =\bigl\{\langle \id,s_{t+3}^{-1}\rangle, \langle \id,s_{t+3}\rangle\bigr\}.
$$

Having determined the types of edges in $\pde\id$ 
(relative to the type $t$ of the initial edge $e_1$),
we move to an endpoint of  such an edge other than $\id$, and apply the same argument.  By 
iteration, we deduce the types of all edges of $G$. Let $T(k)$ denote the type of
edge $k$. It follows from the above that 
\begin{equation}\label{eq:rot}
\text{$T(k)-T(e_1)$ is independent of $t=T(e_1)$},
\end{equation}
with arithmetic on indices, modulo $4$.

We explain next how to identify the value of $p=p(v)$ in \eqref{eq:ass1} from the
graphical structure of $G$.
Let $S_i$ be the subgraph of $G$
containing all edges with type either $s_i$ or $s_{i+1}$, so that 
each component of $S_i$ is isomorphic to the Cayley
graph of $\BS(s_i,s_{i+1})$.  By \eqref{eq:22.5}--\eqref{eq:22.6},
every directed $5$-cycle of $\BS(s_t,s_{t+1})$  starting with the edge 
$[\id, s_t\rangle$  has third edge with type $s_{t+1}$, 
whereas every directed $5$-cycle starting with  
$[\id, s_t^{-1}\rangle$  has third edge with type $s_t$.
We examine $S_t$ to determine which of these two cases holds,
and the outcome determines the value of $p=p(v)$.

The above argument is applied to each directed edge $[\g,\g s_i^{\pm 1}\rangle$
of $G$, and the power of $s_i$ is thus determined from the graphical structure of $G$.

Let $\eta\in\Stab_\id$. By \eqref{eq:rot}, the effect of $\eta$ is to
change the edge-types by 
$$
T(k) \mapsto T(k) + T(\eta(e_1))-t.
$$ 
Now, $\eta(v)$ is adjacent to $\id$ and, by the above, once $\eta(v)$ is known,
the action of $\eta$ on the rest of $G$ is determined.  Since $\eta\in\Aut(G)$,
$\eta(v)$ may be any neighbour $w$ of $\id$ with the property that $p(w)=p(v)$.
There are exactly four such neighbours (including $v$)
and we deduce from \eqref{eq:rot} that $\eta$ lies in the cyclic group
generated by the permutation $(s_0s_1s_2s_3)$.


\section{Proof of Theorem \ref{thm:hg2}}\label{sec:pfhig}

We shall prove three statements:
\begin{romlist}
\item $\Ga$ has no \GHF,
\item $\Stab_\id=\Pi$ where $\Pi=\{e\}$,
\item $\Ga$ has no proper normal subgroup with finite index.
\end{romlist}
The result follows from these statements by Corollary \ref{cor}(a), and we turn to their proofs.
 
 
(i)
The absence of a \GHF\ is immediate by \cite[Thm 4.1(b)]{GL-Cayley}.

(ii)
Let $\eta\in\Stab_\id$ and $\g \in \Ga$. We consider the action of $\eta$ on directed edges of $G$.
By inspection of the set $R'$ of relations, an edge of the type $\langle \g, \g x\rangle$
lies in shortest cycles of length
\begin{equation*}
\begin{cases} 5,\ 8 &\text{if } x=a^{\pm 1},\\
5,\ 7 &\text{if } x=b^{\pm 1},\\
7,\ 8 &\text{if } x=c^{\pm 1},\\
9,\ 11 &\text{if } x=d^{\pm 1}.
\end{cases}
\end{equation*}
Since the four combinations are distinct, it must be that
\begin{equation}\label{eq:230}
\eta([\g,\g x\rangle) = [\g',\g'x^{\pm 1}\rangle, \qq \g\in\Ga, \ x\in S,
\end{equation}
where $\g'=\eta(\g)$.
We  show next that
\begin{equation}\label{eq:213}
\eta([\g,\g x\rangle) \ne [\g',\g' x^{-1}\rangle, \qq \g\in\Ga,\ x\in S,
\end{equation} 
which combines with \eqref{eq:230} to imply $\eta=e$ as required.

It suffices to consider the case $x=a$ in \eqref{eq:213},
since a similar proof holds in the other cases.
Suppose $\eta([\g,\g a\rangle)=[\g',\g' a^{-1}\rangle$, and consider the 
cycle corresponding to $\g ab^{-2}a^{-1}b^{-1}$, that is $(\g,\g a,\g a b^{-1},\g ab^{-2}, \g ab^{-2}a^{-1},
\g ab^{-2}a^{-1}b^{-1}=\g)$. 
By \eqref{eq:230}, this is mapped under $\eta$ to the cycle 
corresponding to  $\g' a^{-1}b^{\pm 2}a^{\pm 1}b^{\pm 1}$.
By examining the relation set $R'$, the only cycles beginning $\g' a^{-1}b^{\pm 1}$ with length 
not exceeding $5$ are $\g'a^{-1}bab^{-2}$ and $\g'a^{-1}b^{-1}ab^2$, in contradiction
of the above (since the third step of these two cycles is $a$ rather than the required $b^{\pm 1}$).

(iii)
Suppose $\sN$ is a proper normal subgroup of $\Ga$ with finite index. 
The quotient group $\Ga/\sN$ is non-trivial and finite  with generators $\ol s=s\sN$,
$s\in S$, satisfying
\begin{equation}\label{eq:ord3}
\begin{alignedat}{3}
\ol{a}^{-1}\ol{b}\ol{a}&=\ol{b}^2,&\qq
\ol{b}^{-2}\ol{c}\ol{b}^2&&=\ol{c}^2,\\
\ol{c}^{-3}\ol{d}\ol{c}^3&=\ol{d}^2,&\qq
\ol{d}^{-4}\ol{a}\ol{d}^4&&=\ol{a}^{2}.
\end{alignedat}
\end{equation}
Since $\Ga/\sN$ is finite, each $\ol s$ has finite order, denoted $\Od(\ol{s})$.
It follows from \eqref{eq:ord3} that 
\begin{equation}\label{eq:ord4}
\Od(\ol s)>1, \qq s=a,b,c,d.
\end{equation}
To see this, suppose for illustration that $\Od(\ol c)=1$, so that $\ol c=\ol\id$. 
By the third equation of \eqref{eq:ord3},
$\Od(\ol d)=1$, so that $\ol d=\ol\id$, and similarly for $\ol a$ and $\ol b$, implying
that $\Ga/\sN$ is trivial, a contradiction.

By induction, for $n \ge 1$,
\begin{alignat*}{3}
\ol{a}^{-n}\ol{b}\ol{a}^n&=\ol{b}^{2^n},&\qq
\ol{b}^{-2n}\ol{c}\ol{b}^{2n}&&=\ol{c}^{2^n},\\
\ol{c}^{-3n}\ol{d}\ol{c}^{3n}&=\ol{d}^{2^n},&\qq
\ol{d}^{-4n}\ol{a}\ol{d}^{4n}&&=\ol{a}^{2^n},
\end{alignat*}
whence, by setting $n=\Od(\ol a)$, etc,
\begin{equation}\label{eq:ord2}
\begin{alignedat}{2}
\Od(\ol{b})&\bigmid (2^{\Od(\ol{a})}-1),\qq\Od(\ol{c})&&\bigmid (2^{\Od(\ol{b})}-1),\\
\qq\Od(\ol{d})&\bigmid (2^{\Od(\ol{c})}-1),\qq\Od(\ol{a})&&\bigmid (2^{\Od(\ol{d})}-1),
\end{alignedat}
\end{equation}
where $u \mid v$ means that $v$ is a multiple of $u$.
We shall deduce a contradiction from \eqref{eq:ord4} and \eqref{eq:ord2}.
This is done as in \cite{Hg}, of which we reproduce the proof for completeness.

Let $p$ be the least prime factor of the four integers $\Od(\ol s)$, $s\in\{a,b,c,d\}$. By \eqref{eq:ord4},
$p>1$. Suppose that $p \mid \Od(\ol a)$ (with a similar argument
if $p\mid \Od(\ol s)$ for some other parameter $s$).
Then $p \mid 2^{\Od(\ol d)}-1$ by \eqref{eq:ord2}, and in particular $p$ is odd and 
therefore coprime with $2$.
Let $r$ be the multiplicative order of $2$ mod $p$, that is,
the least positive integer $r$ such that $p \mid 2^r-1$.
In particular, $r > 1$, so that $r$ has a prime factor $q$.
By Fermat's little theorem, $r \mid p-1$ so that $q<p$.
Furthermore, $r \mid \Od(\ol d)$ so that $q \mid \Od(\ol d)$, in contradiction of the
minimality of $p$.
We deduce that $\Ga$ has no proper, normal subgroup with finite index.


\section*{Acknowledgements} 
GRG was supported in part
by the Engineering and Physical Sciences Research Council under grant EP/103372X/1. 
ZL acknowledges support from the Simons Foundation under  grant $\#$351813.

\bibliography{dpr4}
\bibliographystyle{amsplain}




\end{document}
