# The branching number of intermediate growth trees

Gideon Amir  Gideon Amir Bar-Ilan University, 5290002, Ramat Gan, Israel.  :
<EMAIL_ADDRESS>and  Shangjie Yang  Shangjie Yang Bar-Ilan University,
5290002, Ramat Gan, Israel<EMAIL_ADDRESS>
###### Abstract.

We introduce an ”intermediate branching number”(IBN) which captures the
branching of intermediate growth trees, similar in spirit to the well-studied
branching number of exponential growth trees. We show that the IBN is the
critical parameter for recurrence vs. transience of random walk with suitably
chosen (random) conductances (analogous to the results of [LP16, Chapter 3],
[CHK18] for exponential and polynomial growth trees resp.). We analyze the IBN
on some examples of interest. Finally we show that on some permutation wreath
products of intermediate growth groups, the IBN coincides with the critical
value for the firefighter problem. This gives the first tight bounds for the
firefighter problem on intermediate growth groups.

###### Key words and phrases:

Branching number, random walk, random conductance, percolation, firefighter,
intermediate growth groups, permutation wreath product.
AMS subject classification: 60K35, 60K37, 20E08

##  1\. Introduction

Given an infinite rooted tree, there are several ways to measure the amount of
branching and structure of the tree. One obvious such measure is the volume
growth (of the balls around the root). However, the growth rate does not
capture many of the properties of the tree, especially with respect to the
behaviour of random walks on the tree. e.g. one can have an exponential growth
tree on which simple random walk is recurrent. This motivates finding other
measures. One such quantity, which proved to be very successful, is the
_branching number_ (See e.g [LP16, Chapter 3]). The branching number was
linked to the critical values of different processes on trees such as
transience/recurrence of biased random walk on trees, percolation thresholds,
and firefighting. One limitation of the branching number is that it is always
$1$ for subexponential growth trees, thus it does not convey any information
on them. A step in generalizing the branching number to smaller trees was done
in [CHK18, CHK19] where an analogous branching-ruin number on polynomial
growth trees was introduced and studied. While it managed to capture threshold
properties for several random processes on polynomial growth trees (e.g. the
one-reinforced random walk), the branching ruin number is infinite for
superpolynomial growth trees. Thus there is a gap left not covered by both
these branching numbers.

In this paper we introduce a new branching number, which we call the
_intermediate branching number_ (IBN), to capture the branching structure of
intermediate growth trees (or more precisely trees with stretched exponential
growth). Its exact definition is given in section 2.4. Part of the motivation
for studying intermediate growth trees comes from their connection to the
Cayley graphs of intermediate growth groups. Even though it has been about 40
years since the introduction of the first group of intermediate growth by
Grigorchuk [Gri83], the geometry of these groups and their Cayley graphs is
not well understood. Despite of lots of research and breakthroughs in the
area, many processes, which are well understood on exponential and on
polynomial growth groups, remain mostly mysterious on intermediate growth
groups. Thus we believe that any additional tools to study the Cayley graphs
of such groups are of interest.

We begin by giving some basic results and examples concerning intermediate
growth trees and their IBN, including the lexicographical minimal spanning
tree of Nathanson’s intermediate growth semigroup. The bulk of the paper
studies the connection between the IBN and some random processes on the trees,
such as random walks with random and random conductances, percolation and the
firefighter problem. A detailed description of the models and results is given
in the next section.

### Notations

${\mathbb{N}}_{0}\colonequals{\mathbb{Z}}\cap[0,\infty)$, and for $a,b>0$ let
$\llbracket a,b\rrbracket\colonequals[a,b]\cap{\mathbb{Z}}$. We use $|\cdot|$
to measure the distance to the root in a tree (or in a Cayley graph), and let
$\\#$ denote the cardinality of a set.

##  2\. Model and results

###  2.1. The setup

Let ${\mathcal{T}}=(V,E)$ be a locally finite, infinite tree with a rooted
vertex $\varrho$. For any vertex $x\in V$, let $|x|$ be the number of edges in
the self-avoiding path connecting $\varrho$ and $x$. For an edge $e\in E$, let
$e^{+}$ and $e^{-}$ be the two end points of $e$ with $|e^{+}|=|e^{-}|+1$.
That is to say, $e^{+}$ is a child of $e^{-}$. For $\mu,\nu\in V$, let
$[\mu,\nu]$ be the unique self-avoiding path connecting $\mu$ and $\nu$. If
$\mu$ is on the path $[\varrho,\nu]$, we say $\mu\leq\nu$, and $\mu<\nu$ if
$\mu\neq\nu$. Similarly, we define such a relation between two edges
$e_{1},e_{2}\in E$. In addition, let $e_{1}\wedge e_{2}$ be the common
ancestor of the deepest generation of $e_{1}$ and $e_{2}$, i.e.

$e_{1}\wedge e_{2}\colonequals\sup\left\\{e\in E:\ e\leq e_{1},e\leq
e_{2}\right\\}.$

Let $B(n)\colonequals\left\\{x\in V:\ |x|\leq n\right\\}$ be the set of those
vertices at distance at most $n$ (in the graph distance) to $\varrho$.
Moreover, set $E_{n}\colonequals\\{x\in V:\ |x|=n\\}$ to be the set of
vertices at distance exactly $n$ to the root $\rho$.

###  2.2. Intermediate growth trees

We say that a tree ${\mathcal{T}}$ is of intermediate (stretched exponential)
growth if

$0<\liminf_{n\to\infty}\log\log\\#B(n)/\log
n\leq\limsup_{n\to\infty}\log\log\\#B(n)/\log n<1.$ (2.1)

There exists examples of lexicographic minimal spanning trees of Cayley graphs
in [KP13, Theorem 2.3] such that the inequality in (2.1) can be strict. We say
the tree is of intermediate growth with parameter $\alpha\in(0,1)$ if

$\liminf_{n\to\infty}\log\log\\#B(n)/\log
n=\limsup_{n\to\infty}\log\log\\#B(n)/\log n=\alpha.$ (2.2)

Note that $\alpha$ only determines the first order of the growth rate. The
volume $\\#B(n)$ may be e.g. $\exp(cn^{\alpha})$, $\exp(cn^{\alpha}/\log n)$,
$\exp(cn^{\alpha}(\log n)^{2})$, etc.

We first give what is, perhaps, the simplest example of an intermediate growth
tree. Take a sequence of numbers $1,2,1,1,2,1,1,1,2,1,1,1,1,2,...$, denoted by
$(a_{n})_{n\in{\mathbb{N}}}$, where the amount of $1$s increases by one
between any two consecutive $2$s. In other words, the sequence
$(a_{n})_{n\in{\mathbb{N}}}$ is defined as follows: for $n\geq 1$

$a_{n}\colonequals\begin{cases}2&\text{ if }n=k+\frac{(1+k)k}{2}\text{ for
some }k\in{\mathbb{N}},\\\ 1&\text{ otherwise. }\end{cases}$ (2.3)

We construct a tree ${\mathcal{T}}$ such that the root $\varrho$ has only one
child and every vertex $x$ with $|x|=n\geq 1$ has $a_{n}$ children. We observe
$\\#E_{n}\leq\\#B(n)\leq n\\#E_{n}$,

$\\#E_{n}=2^{\sum_{k=1}^{n-1}(a_{k}-1)}$

and then obtain

$\lim_{n\to\infty}\log\log\\#B(n)/\log n=\frac{1}{2}.$ (2.4)

A tree is spherically symmetric if every vertex at distance $n$ to the root
has the same number of children (which can depend on $n$). The example above
is spherically symmetric.

An important source of interesting intermediate growth trees are the
lexicographical minimal spanning trees of intermediate growth groups. Such
trees where studied for exponential growth groups (See [LP16, Fur67]).

For a given tree ${\mathcal{T}}=(V,E)$ and $x\in V$, let ${\mathcal{T}}_{x}$
be the subtree consisting of $x$ and all descendants of $x$. We say that
${\mathcal{T}}$ is $M$-sub-periodic if for all $x\in V$ there exists an
injective map $f:{\mathcal{T}}_{x}\mapsto{\mathcal{T}}$ satisfying $|f(x)|\leq
M$ and keeping the adjacency of the vertices. If there exists one such
$M\in{\mathbb{N}}_{0}$, we say that ${\mathcal{T}}$ is sub-periodic.

One important structural properties of the lexicographical minimal spanning
tree is that it is _sub-periodic_. However intermediate growth trees cannot be
both sub-periodic and spherical symmetric as stated in the following theorem.

######  Theorem 2.1.

There is no spherically symmetric, sub-periodic and subexponential growth
tree, i.e.

$\lim_{n\to\infty}\frac{\log\\#E_{n}}{n}=0,$ (2.5)

and satisfying $\lim_{n\to\infty}\\#E_{n}=\infty.$

We obtain the following corollary.

######  Corollary 2.2.

The lexicographic minimal spanning tree of any finitely generated, infinite
and subexponential growth group with $\lim_{n\to\infty}\\#E_{n}=\infty$ is not
spherically symmetric. In particular, this holds for finitely generated
Abelian groups with superlinear growth, Grigorchuk groups.

###  2.3. Nathanson’s example

Since the Cayley graphs of intermediate growth groups are extremely
complicated, we look for interesting intermeidate growth trees also in
semigroups. The lexicographic minimal spanning tree of any semigroup is also
$0$-subperiodic.

Nathanson in [Nat99] provided an interesting example of a semigroup of
intermediate growth: a semigroup of $2\times 2$ matrices generated by the set
$A=\\{a,b\\}$ w.r.t. multiplication where

$a\colonequals\begin{pmatrix}1&1\\\ 0&1\end{pmatrix}\quad\text{ and }\quad
b\colonequals\begin{pmatrix}1&0\\\ 1&0\end{pmatrix}.$ (2.6)

The volume growth is given in the following theorem.

######  Theorem A (Theorem 1 in [Nat99]).

Let $S$ be the semigroup generated by $\\{a,b\\}$ defined in (2.6). Then there
exists a constant $c>0$ such that for all $n$ sufficiently large,

$2^{c\sqrt{n}/\log n}\leq\\#B(n)\leq 2n^{2\sqrt{n}+2}.$ (2.7)

We define a lexicographical order on $S$ by setting $b<a$, to obtain its
lexicographic minimal spanning tree as in Figure 1. We refer to Section 4 for
more details about the construction of this tree and the calculation of its
intermediate branching number.

$\mathrm{Id}$123456789101234567123451234567891012345678(L)(M)(R)Id$1$$2$$i$$1$$2$$p-1$$1$$2$$p^{\prime}-1$Id12$p-1$12$p^{\prime}-1$12
Figure 1.  A graphical explanation: a black edge represents $a$ while a red
edge represents $b$ with a blue dot standing for a vertex. (L): the general
picture of the lexicographic minimal spanning tree (note that not all the
branches are shown.), and the green dashed lines depicts where the flows
splits; (M): A generic branch of those vertices of the form
$a^{i}ba^{p-1}ba^{p^{\prime}-1}b\cdots$ with $p\leq p^{\prime}$ being primes;
(R): A generic branch of those vertices of the form
$ba^{p-1}ba^{p^{\prime}-1}b\cdots$ with $p\leq p^{\prime}$ being primes.

###  2.4. The intermediate branching number.

Now we turn to characterize the structure and complexity of intermediate
growth trees. We define the growth of intermediate trees as

${\mathrm{I_{gr}}}({\mathcal{T}})\colonequals\sup\left\\{\lambda>0:\
\liminf_{n\to\infty}\sum_{e\in
E_{n}}\exp\left(-n^{\lambda}\right)>0\right\\}.$ (2.8)

Since ${\mathrm{I_{gr}}}({\mathcal{T}})$ only captures the volume growth of a
tree, to characterize its structure we mimic [LP16, Eq. (3.4)] to define the
intermediate branching number. We say that $\pi\subset E$ is a cutset if any
infinite self-avoiding path connecting $\varrho$ to infinity has one unique
edge in $\pi$, and define the intermediate branching number as

${\mathrm{IBN}}({\mathcal{T}})\colonequals\sup\left\\{\lambda>0:\
\inf_{\pi\in\Pi}\sum_{e\in\pi}\exp\left(-|e|^{\lambda}\right)>0\right\\}$
(2.9)

where $\Pi$ is the set of all cutsets. Since
$(E_{n})_{n\in{\mathbb{N}}}\subset\Pi$, we have

${\mathrm{IBN}}({\mathcal{T}})\leq{\mathrm{I_{gr}}}({\mathcal{T}}).$ (2.10)

We recall that given the conductances $(c_{e})_{e\in E}\geq 0$,
$\theta:E\mapsto{\mathbb{R}}_{+}$ is an admissible flow if for all $e\in E$,
$0\leq\theta(e)\leq c_{e}$ and

$\theta(e)=\sum_{\widetilde{e}:\
\widetilde{e}^{+}=e^{-}}\theta(\widetilde{e}).$

Furthermore, we define
$\mathrm{Strength}(\theta)\colonequals\sum_{e:e^{-}=\varrho}\theta(e)$.

For a spherically symmetric tree ${\mathcal{T}}$, we have

${\mathrm{IBN}}({\mathcal{T}})={\mathrm{I_{gr}}}({\mathcal{T}})$ (2.11)

where we use the max-flow min-cut theorem [LP16, Theorem 3.1] and the flow
splits equally among the children.

Without spherical symmetry (2.11) may fail. To construct a tree
${\mathcal{T}}$ satisfying
${\mathrm{IBN}}({\mathcal{T}})<{\mathrm{I_{gr}}}({\mathcal{T}})$, we take the
$3-1$ tree [LP16, Example 1.2] and replace each edge at distance $n$ by a path
of length $n$ to obtain a tree satisfying
${\mathrm{I_{gr}}}({\mathcal{T}})=1/2$ and ${\mathrm{IBN}}({\mathcal{T}})=0$.

For exponential growth groups, a theorem of Furstenberg ([Fur67],[LP16,
Theorem 3.8]) shows that the branching number is equal to the growth rate.
This is deduced from sub-periodicity of the lexicographical minimal spanning
tree. However, we do not know if equality between the growth and IBN holds for
intermediate growth trees.

Open question: For sub-periodic and intermediate growth trees: is it true that

${\mathrm{I_{gr}}}({\mathcal{T}})={\mathrm{IBN}}({\mathcal{T}})?$ (2.12)

For the lexicographic minimal spanning tree ${\mathcal{T}}$ of the semigroup
in Theorem A, we calculate
${\mathrm{I_{gr}}}({\mathcal{T}})={\mathrm{IBN}}({\mathcal{T}})=1/2$ in
Section 4.

###  2.5. The recurrence/transience phase transition of random walks

In this subsection, we are concerned with the recurrence/transience phase
transition of the random walk on an intermediate growth tree
${\mathcal{T}}=(V,E)$ with conductances given as $c(e)=\exp(-|e|^{\lambda})$
for all $e\in E$. Similar results linking the branching number of exponential
growth trees and the phase transition of biased random walks (taking
$C(e)=\lambda^{-|e|}$) can be found in [Lyo90], [LP16, Theorem 3.5].

We define a random walk $\textbf{X}=(X_{n})_{n\geq 0}$ with $X_{0}=\varrho$
and for $n\geq 1$

${\mathbb{P}}\left[X_{n}=\nu\ |\
X_{n-1}=\mu\right]\colonequals\frac{C([\mu,\nu])\mathbf{1}_{\\{\mu\sim\nu\\}}}{\sum_{\nu^{\prime}:\nu^{\prime}\sim\mu}C([\mu,\nu^{\prime}])}$
(2.13)

where we allow $\mu<\nu^{\prime}$ or $\mu>\nu^{\prime}$. In other words, when
$X_{n-1}=\mu$, $X_{n}$ picks a neighbor among all the neighbors of $\mu$ with
probability proportional to the conductance. We link the phase transition of
the random walk with the intermediate branching number in the following
theorem.

######  Theorem 2.3.

Let $\textbf{X}=(X_{n})_{n\geq 0}$ be the random walk defined above. If
$\lambda>{\mathrm{IBN}}({\mathcal{T}})$, X is recurrent. If
$\lambda\in(0,{\mathrm{IBN}}({\mathcal{T}}))$, X is transient.

The proof for Theorem 2.3 is presented in Section 5.

###  2.6. The intermediate branching number and percolation

Given an intermediate growth tree, we consider the following percolation. We
first fix $\lambda\in(0,1)$. Each edge is open independently, and for $e\in
E$,

${\mathbb{P}}\left[e\text{ is
open}\right]=\exp\left(-|e|^{-1+\lambda}\right).$ (2.14)

We define the critical parameter about percolation as

$\Theta({\mathcal{T}})\colonequals\sup\left\\{\lambda\geq 0:\
{\mathbb{P}}\left[\varrho\leftrightarrow\infty\right]>0\right\\}.$ (2.15)

######  Theorem 2.4.

In the setting of (2.14) and (2.15), we have

$\Theta({\mathcal{T}})={\mathrm{IBN}}({\mathcal{T}}).$ (2.16)

An analogous result linking the branching number and the percolation threshold
in exponential growth trees can be found in [Lyo90], [LP16, Theorem 5.15].

###  2.7. Random walks with random conductance

In [CHK19] the authors study a random walk in heavy-tailed random conductances
on polynomial-growth trees. They prove a phase transition between recurrence
and transience depending on the tail of the law of the conductances, and show
that the branching-ruin number is the critical threshold for this transition.
Our aim in this section is to show a similar result for intermediate growth
trees and show that critical threshold for recurrence vs transience is the
intermediate branching number. We start by describing the random conductance
model.

Let $(C_{e})_{e\in E}$ be a sequence of i.i.d. random variables with common
law ${\mathbb{P}}$ supported on $(0,\infty)$. We assume there exists
$\lambda\in(0,1)$ such that for all $t\geq 1$

${\mathbb{P}}\left[C_{1}<\exp\left(-t^{\lambda}\right)\right]=L(t)\cdot
t^{\lambda-1}$ (2.17)

where $L:[1,\infty)\mapsto{\mathbb{R}}_{+}$ is a slowly varying function,
i.e. for all $a>0$

$\lim_{t\to\infty}\frac{L(at)}{L(t)}=1.$

In other words, the random conductance $C_{e}$ has a heavy tail at $0$. Given
a realization of $(C_{e})_{e\in E}$, we define the random walk
$\textbf{X}=(X_{n})_{n\geq 0}$ with conductance $(C_{e})_{e\in E}$ exactly the
same as (2.13). From now on, we abbreviate $\textbf{X}=(X_{n})_{n\geq 0}$, the
random walk on random conductance, as RWRC.

######  Theorem 2.5.

If $\lambda>\alpha={\mathrm{IBN}}({\mathcal{T}})$, then RWRC is recurrent
almost surely. If $\lambda<\alpha={\mathrm{IBN}}({\mathcal{T}})$, then RWRC is
transient a.s.

###  2.8. Firefighting problem

Let ${\mathcal{G}}=(V,E)$ be a locally finite, connected, infinity graph, with
$E$ denoting its edges and $V$ denoting its vertices. Given $g=(g_{n})_{n}$ a
sequence of nonnegative integers, we play a firefighting game on
${\mathcal{G}}$ as follows: ($W_{0}\colonequals\emptyset$)

  * 1.

the initial fire is set on a finite subset $Z_{0}\subset V$;

  * 2.

for $n\geq 1$, at round $n\in{\mathbb{N}}$, we can pick a subset $S_{n}\subset
V\setminus(Z_{n-1}\cup W_{n-1})$ with $\\#S_{n}\leq g_{n}$ to protect all the
vertices in $S_{n}$. Once a vertex is protected (or on fire), it keeps the
state forever.

  * 3.

for $n\geq 1$, set

$\begin{gathered}W_{n}=W_{n-1}\cup S_{n}=\cup_{i=1}^{n}S_{n},\\\
Z_{n}=Z_{n-1}\cup\left\\{v\in V\setminus W_{n}:\ \exists u\in Z_{n-1},u\sim
v\right\\}.\end{gathered}$ (2.18)

That is to say, $W_{n}$ are the protected vertices up to round $n$, and in
every round the fire spreads to its nearest neighbors except those protected
vertices.

Given $Z_{0}$, let $\Upsilon:{\mathbb{N}}\mapsto V$ be the map defined by
$\Upsilon(n)=S_{n}$ described above, and we say that $\Upsilon$ is legal.
Furthermore, if the fire stops growing after finitely many step, i.e.
$\\#\cup_{n=0}^{\infty}Z_{n}<\infty$, we say that $\Upsilon$ is containable
for $Z_{0}$ or the fire $Z_{0}$ is containable w.r.t. $\Upsilon$. Otherwise,
we say that the fire percolates. Furthermore, the graph ${\mathcal{G}}$ is
said to be $g$-containable if for any finite subset $Z_{0}$ there is a
corresponding containable map $\Upsilon$ satisfying $\\#\Upsilon(n)\leq g(n)$
for all $n\in{\mathbb{N}}$. Understanding the relation between ${\mathcal{G}}$
and its containment functions is considered an asymptotic version of the
firefighting game introduced by Hartnell in [Har95].

A graph ${\mathcal{G}}$ satisfies intermediate containment of rate
$\gamma\in(0,1)$ if there is some $C>0$ and $g=(g_{n})_{n\in{\mathbb{N}}}$
with $g_{n}\leq C\exp(n^{\gamma})$ for all $n\in{\mathbb{N}}$ such that
${\mathcal{G}}$ is $g$-containable. Due to the monotonicity (c.f. Lemma 8.1),
there is a critical parameter $\lambda_{c}$ such that if $\gamma>\lambda_{c}$
then ${\mathcal{G}}$ satisfies intermediate containment of rate $\gamma$ and
if $\gamma<\lambda_{c}$ then ${\mathcal{G}}$ does not satisfy intermediate
containment of rate $\gamma$. For $\lambda_{c}=0$ or $\lambda_{c}\geq 1$, the
graph ${\mathcal{G}}$ is not of intermediate containment type in our
definition. Our first theorem on firefighting says that for intermediate
growth trees, the intermediate branching number is the critical parameter for
containment. This can be seen as an analogous result to Lehner’s theorem for
exponential growth trees [Leh19, Theorem 3.1].

######  Theorem 2.6.

Let ${\mathcal{T}}$ be a locally finite, infinite tree satisfying
${\mathrm{IBN}}({\mathcal{T}})=\alpha\in(0,1)$, and then we have
${\mathrm{IBN}}({\mathcal{T}})=\lambda_{c}({\mathcal{T}})$.

###  2.9. Firefighting problem on some permutation wreath groups

The firefighter problem is of particular interest in the case of Cayley
graphs, where one can hope to find connections between the geometry of the
group ${\mathcal{G}}$ and the containment threshold. Precise asymptotic bounds
are known for exponential growth groups ([Leh19]) and for polynomial growth
groups ([ABK20]), but no such tight bounds were known for any intermediate
growth groups. Our main aim in this section is to find such bounds for a
family of intermediate growth groups. The groups we will use are permutation
wreath products. More precisely our bounds will be tight for a certain family
of permutation wreath products over Grigorchuk’s group, studied by Bartholdi
and Erschler [BE12]. We start by recalling some definitions and basic facts
regarding permutation wreath products.

Let $G$ be a group acting on a set $X$ from the right, and let $A$ be another
group. Borrowing terminology from ”lamplighter groups”, We will call $G$ the
”base” group, and refer to $A$ as the ”lamp” group. The permutation wreath
product $W=A\wr_{X}G$ is the semidirect product of $\sum_{X}A$ with $G$ where
$\sum_{X}A$ consists of those functions $f:X\mapsto A$ with
$\mathrm{supp}(f)\colonequals\\{x\in X:\ f(x)\neq 1_{A}\\}$ being finite. A
generic element of $W$ is written as $fg$ with $f\in\sum_{X}A$ and $g\in G$.
Moreover, for $f_{1},f_{2}\in\sum_{X}A$ and $g_{1},g_{2}\in G$, the product
between $f_{1}g_{1}$ and $f_{2}g_{2}$ is defined as

$(f_{1}g_{1})\cdot(f_{2}g_{2})\colonequals(g_{2}^{-1}\cdot
f_{1})f_{2}g_{1}g_{2}$

where $(g^{-1}\cdot f)(x)\colonequals f(xg^{-1})$ for all $x\in X$. We
distinguish a vertex $x_{0}\in X$ and identify $a\in A$ with
$f_{a}\in\sum_{X}A$ where

$f_{a}(x)\colonequals\begin{cases}a,&\text{ if }x=x_{0},\\\ 1_{A},&\text{ if
}x\neq x_{0}.\end{cases}$ (2.19)

Let $S_{A}$ and $S_{G}$ be the generating sets of $A$ and $G$ respectively. We
will define a generating set for $W$ by taking all products of the form
$(a_{i}g_{i})_{n\in{\mathbb{N}}}$ with $g_{i}\in S_{G},a_{i}=1_{A}$ or
$g_{i}=1_{G},a_{i}\in S_{A}$. Let $u=a_{1}g_{1}a_{2}g_{2}\cdots
a_{\ell}g_{\ell}\equalscolon f_{u}g_{u}$ and
$v=ua_{\ell+1}g_{\ell+1}\equalscolon f_{v}g_{v}$, and then we say

  * (1)

if $g_{\ell+1}\in S_{G}$ and $a_{\ell+1}=1_{A}$, there is an edge of ”$G$”
type from $u$ to $v$ and $g_{v}=g_{u}g_{\ell+1},f_{v}=g_{\ell+1}^{-1}\cdot
f_{u}$;

  * (2)

if $g_{\ell+1}=1_{G}$ and $a_{\ell+1}\in S_{A}$, there is an edge of ”$A$”
type from $u$ to $v$ and $g_{u}=g_{v},f_{v}=f_{u}$ except at $x_{0}$ where
$f_{v}(x_{0})=f_{u}(x_{0})a_{\ell+1}$.

With this rule, the Cayley graph $(W,S_{A}\cup S_{G})$ is determined. Indeed
for $u=a_{1}g_{1}a_{2}g_{2}\cdots a_{\ell}g_{\ell}=f_{u}g_{u}$ , we know that
$g_{u}=g_{1}\cdots g_{\ell}$ and $f_{u}=((g_{1}\cdots g_{\ell})^{-1}\cdot
f_{a_{1}})((g_{2}\cdots g_{\ell})^{-1}\cdot
f_{a_{2}})\cdots(g_{\ell}^{-1}\cdot f_{a_{\ell}})$. Then we have
$\mathrm{supp}(f_{v})\subset\\{x_{0}g_{\ell},x_{0}g_{\ell-1}g_{\ell},\cdots,x_{0}g_{1}g_{2}\cdots
g_{\ell}\\}$. For $w=g_{1}g_{2}\cdots g_{\ell}$, we define its inverted orbit
as

${\mathcal{O}}(w)\colonequals\\{x_{0}g_{\ell},x_{0}g_{\ell-1}g_{\ell},\cdots,x_{0}g_{1}g_{2}\cdots
g_{\ell}\\}.$

Our strategy for finding the critical threshold for the firefighter problem
relies on finding a good (spherical symmetric) tree inside the Cayley graph,
and then using Theorem 2.6 to get a lower bound that will match the upper
bound coming from the growth rate of the group. Our first Theorem says that if
the inverted orbit growth is at least $n^{\alpha}$ then there is a tree in the
Cayley graph with ${\mathrm{IBN}}\geq\alpha$.

######  Theorem 2.7.

Assume $\\#S_{A}\geq 2$ and that there exists $C_{2}>0$ such that for all
$n\in{\mathbb{N}}$ there is a word $w_{n}$ of length $n$ satisfying

$\\#{\mathcal{O}}(w_{n})\geq C_{2}n^{\alpha}.$ (2.20)

Then there is a spherical symmetric tree ${\mathcal{T}}$ in the Cayley Graph
$(W,S_{A}\cup S_{G})$ satisfying

${\mathrm{IBN}}({\mathcal{T}})\geq\alpha.$

Combining the above Theorem with 2.6 and the upper bound for the growth of the
group we get:

######  Corollary 2.8.

Under the assumptions of Theorem 2.7, if in addition the volume of the ball of
radius $n$ in the Cayley graph $(W,S_{A}\cup S_{B})$ satisfies

$\liminf_{n\to\infty}\frac{\log\log\\#B(n)}{\log n}\leq\alpha.$ (2.21)

Then the critical parameter $\lambda_{c}$ for the firefighter problem on $W$
satisfies

$\lambda_{c}((W,S_{A}\cup S_{G}))=\alpha.$ (2.22)

Finally, in section 9.1 we apply the above corollary, together with results of
[BE12], to conclude the critical threshold for the firefighter problem on the
permutation wreath product over Grigorchuk’s group.

##  3\. Proof of Theorem 2.1

###### Proof.

Suppose there exits such a tree, and it is $M$-subperiodic. Let
$(a_{n})_{n\in{\mathbb{N}}_{0}}$ denote a sequence of positive integers such
that a vertex at generation $n$ has $a_{n}$ children. By $M$-sub-periodicity,
for all $j>M$, there exists $i=i(j)\leq M$ such that

$\forall n\in{\mathbb{N}}_{0},\quad a_{j+n}\leq a_{i+n}.$ (3.1)

In particular,

$\sup_{n\in{\mathbb{N}}_{0}}a_{n}=\max_{0\leq n\leq M}a_{n}\colonequals U\geq
2.$

Therefore,

$2^{\sum_{n=0}^{n-1}\mathbf{1}_{\\{a_{n}\geq 2\\}}}\leq\\#E_{n}\leq
U^{\sum_{n=0}^{n-1}\mathbf{1}_{\\{a_{n}\geq 2\\}}}.$

Therefore it is enough to analyze a simpler sub-periodic spherical symmetric
tree ${\mathcal{T}}^{\prime}$ associated with the sequence
$(b_{n})_{n\in{\mathbb{N}}_{0}}$ where

$\forall n\in{\mathbb{N}}_{0},\quad b_{n}\colonequals
2\mathbf{1}_{\\{a_{n}\geq 2\\}}+\mathbf{1}_{\\{a_{n}=1\\}}$

is $M$-subperiodic and
$\lim_{n\to\infty}E_{n}({\mathcal{T}}^{\prime})=\infty$. From now on, for
simplicity, we assume $a_{n}\in\\{1,2\\}$ for all $n\in{\mathbb{N}}_{0}$, and
let $c_{n}=a_{n}-1$.

For $\varepsilon>0$ sufficiently small, by (2.5), there exists
$N\in{\mathbb{N}}$ sufficiently large such that

$\sum_{k=0}^{N-1}c_{k}\leq\varepsilon N.$

Taking $\ell=M+1\geq 1$, we cut the interval $\llbracket 0,\ell\lfloor
N/\ell\rfloor-1\rrbracket$ into intervals of size $\ell$, and count the number
of those intervals without $c_{n}$ taking value $1$, i.e.

$\\#{\mathcal{A}}\colonequals\\#\left\\{j\in\llbracket 0,\ell\lfloor
N/\ell\rfloor-1\rrbracket:\ \forall n\in\llbracket
j\ell,(j+1)\ell-1\rrbracket,c_{n}=0\right\\}\geq\left\lfloor\frac{N}{\ell}\right\rfloor-\varepsilon
N\geq\frac{N}{2\ell}.$ (3.2)

Setting $\kappa\colonequals\min\\{j:\ j\in{\mathcal{A}}\\}$, we claim

$\left\\{n\in\llbracket\kappa\ell,\ell\lfloor N/\ell\rfloor-1\rrbracket:\
c_{n}=1\right\\}=\emptyset.$ (3.3)

Otherwise, let $n_{0}=\min\left\\{n\in\llbracket\kappa\ell,\ell\lfloor
N/\ell\rfloor-1\rrbracket:\ c_{n}=1\right\\}$, and note that
$n_{0}\geq(\kappa+1)\ell$ by the definition of $\kappa$.

x$n_{0}$$0$$N$ Figure 2.  A graphical explanation with $\ell=\kappa=4$: black
dots are the positions where $c_{n}=1$, the other positions (including blue
dots) are where $c_{n}=0$. Blue intervals are those in ${\mathcal{A}}$. By
subperiodicity, we can move the black dot at $n_{0}$ to the left at least $1$
and at most $\ell$, and thus it should be blue.

Taking $j=M+1$ and applying the analogous relation (3.1) for
$(c_{n})_{n\in{\mathbb{N}}_{0}}$, we obtain

$c_{n_{0}}\leq c_{n_{0}-(j-i)}=0$ (3.4)

where $i=i(M+1)$ is a number depending on $M+1$ as claimed before (3.1), and
the equality is a consequence of $0<j-i\leq M+1$,
$c\restriction_{\llbracket\kappa\ell,n_{0}-1\rrbracket}=0$ and

$\kappa\ell\leq(\kappa+1)\ell-(M+1)\leq n_{0}-(j-i)\leq n_{0}-1.$

This is a contradiction to the assumption $c_{n_{0}}=1$. Therefore, we prove
(3.3).

By induction and (3.4), we obtain $c_{n}=0$ for all $n\geq\kappa\ell.$ This
contradicts the assumption $\lim_{n\to\infty}\\#E_{n}=\infty$. Therefore, we
conclude the proof. ∎

##  4\. Nathanson’s example

######  Lemma 4.1.

Recalling $E_{n}=\\{v\in V:\ |v|=n\\}$, we have

$\lim_{n\to\infty}\frac{\log\log\\#E_{n}}{\log n}=\frac{1}{2}.$ (4.1)

###### Proof.

By Theorem A, we have

$\limsup_{n\to\infty}\frac{\log\log\\#E_{n}}{\log
n}\leq\limsup_{n\to\infty}\frac{\log\log\\#B(n)}{\log n}=\frac{1}{2}.$ (4.2)

Concerning the lower bound on
$\liminf_{n\to\infty}\frac{\log\log\\#E_{n}}{\log n}$, it is a consequence of
the proof in [Nat99, Theorem 1]. For the sake of completeness, we include a
proof here. As observed in [Nat99, Theorem 1], $b^{2}=b$ and

$ba^{k}b=\begin{pmatrix}k+1&0\\\ k+1&0\end{pmatrix},$ (4.3)

and then for any positive integers $k_{1},\cdots,k_{r}$,

$ba^{k_{1}}ba^{k_{2}}b\cdots
ba^{k_{r}}b=\left(\prod_{i=1}^{r}(k_{i}+1)\right)b.$ (4.4)

Taking $p_{1},p_{2},\cdots,p_{r}$ to be distinct prime numbers smaller than or
equals to $\sqrt{n}$, we have

$ba^{p_{1}-1}ba^{p_{2}-1}b\cdots
ba^{p_{r}-1}b=\left(\prod_{i=1}^{r}p_{i}\right)b.$ (4.5)

Moreover, by Chebyshev’s theorem [Nat96, Theorem 6.3], there exist two
universal constants $c,c^{\prime}>0$ such that

$\frac{c^{\prime}\sqrt{n}}{\log n}\leq\\#\\{p\leq\sqrt{n}:\ p\text{ is a prime
number }\\}\leq\frac{c\sqrt{n}}{\log n}.$ (4.6)

By (4.6), the length of such word in (4.5) is bounded above by

$1+\sum_{i=1}^{r}p_{i}\leq 1+r\sqrt{n}\leq 1+\frac{cn}{\log n}\leq n$

for all $n$ sufficiently large. Then each of such elements belongs to $B(n)$.
Moreover, any two such elements are distinct since each positive integer is a
unique product of primes. Whence, every subset of primes up to $\sqrt{N}$
corresponds to an element of the semigroup $S$. Write

$S_{m}\colonequals\left\\{ba^{p_{1}-1}ba^{p_{2}-1}b\cdots ba^{p_{r}-1}b:\
p_{1}<p_{2}<\cdots<p_{r}\text{ are primes},\forall i\leq r,\
p_{i}\leq\sqrt{n};\sum_{i=1}^{r}p_{i}=m\right\\},$

and we have

$\sum_{m=0}^{n-1}\\#S_{m}\geq 2^{c^{\prime}\sqrt{n}/\log n}$ (4.7)

where we have used (4.6). Therefore, there exists at least one $m_{0}\leq n-1$
such that

$\\#S_{m_{0}}\geq 2^{c^{\prime}\sqrt{n}/\log n}/n.$

Observe that for any two distinct positive integers $k,\ell\geq 2$,
$ba^{k-1}ba^{\ell-1}b=ba^{k\ell-1}b$ and

$k+\ell+1=|ba^{k-1}ba^{\ell-1}b|\leq|ba^{k\ell-1}b|=k\ell+1.$

Therefore, every element in $S_{m}$ is written in the shortest expression. By
$a^{n-m_{0}-1}S_{m_{0}}\subset E_{n}$, we conclude the proof.

∎

We consider the associated lexicographic minimal spanning tree ${\mathcal{T}}$
of the semigroup $S$ by taking the lexicographic order $b<a$. There are three
types of words in $E_{n}$: (1) $a^{n}$; (2) $a^{i}ba^{j}$ with
$i,j\in{\mathbb{N}}_{0}\text{ and }i+j=n-1$; and (3)

$a^{i}\underbrace{ba^{p_{1}-1}\cdots ba^{p_{1}-1}}_{r_{1}\text{ copies
}}\cdots\underbrace{ba^{p_{k}-1}\cdots ba^{p_{k}-1}}_{r_{k}\text{ copies
}}ba^{j}$ (4.8)

where $i+j+1+\sum_{\ell=1}^{k}r_{\ell}p_{\ell}=n$ and
$p_{1}<p_{2}<\cdots<p_{k}\text{ are primes}$. All these three types of words
are written in the lexicographic minimal sense. For two words $g\in E_{n}$,
$h\in E_{n+1}$ written in the forms stated above, there is an edge linking $g$
with $h$ if $h=ga$ or $h=gb$. We refer to Figure 1 for visualization of the
minimal spanning tree. The figures (M) and (R) in Figure 1 explain the rule in
(4.8).

As we know the structure of the lexicographic minimal spanning tree
${\mathcal{T}}$, we can calculate its ${\mathrm{IBN}}$ in the following
proposition.

######  Proposition 4.2.

For the lexicographic minimal spanning tree ${\mathcal{T}}$ of the semigroup
$S$ generated by $\\{a,b\\}$ defined in (2.6) and setting $b<a$ for the
lexicographic order, we have

${\mathrm{IBN}}({\mathcal{T}})=\frac{1}{2}.$ (4.9)

###### Proof.

By (2.10), we have

${\mathrm{IBN}}({\mathcal{T}})\leq\liminf_{n\to\infty}\frac{\log\log\\#E_{n}}{\log
n}=\frac{1}{2}.$ (4.10)

Now we show ${\mathrm{IBN}}({\mathcal{T}})\geq 1/2$. For any
$\lambda<\frac{1}{2}$, we designate a flow from $\mathrm{Id}$ to infinity as
follows: $\theta(\\{\mathrm{Id},a\\})=0,\theta(\\{\mathrm{Id},b\\})=c>0$, and
the flow along any self-avoiding path from $\mathrm{Id}$ to infinity splits
equally when it visits ${p-1}$ the first time with $p$ being prime. We refer
to Figure 1 for a graphic explanation. Now we verify that this flow is
admissible, i.e. $\theta(e)\leq\exp({-|e|^{\lambda}})$. For any vertex at
distance $\ell=j+\sum_{i=1}^{k}p_{i}$ where $p_{1}<p_{2}<\cdots<p_{k}$ are
primes and $0\leq j<\kappa(p_{k})$ with

$\kappa(p_{k})\colonequals\inf\\{p>p_{k}:p\text{ is prime }\\}.$

The flow in the edge $e$ between this vertex and its parent is

$c\cdot 2^{-\\#\\{p\leq p_{k}:\ p\text{ is prime}\\}}.$ (4.11)

By Cheyshev’s Theorem [Nat96, Theorem 6.3], for all $p_{k}$ sufficiently
large, we have $q(p_{k})\leq 2p_{k}$ and then

$\ell\leq\kappa(p_{k})+\sum_{i=1}^{p_{k}}i\leq 2p_{k}+\sum_{i=1}^{p_{k}}i\leq
p_{k}^{2}.$

Therefore, by Cheyshev’s Theorem, for all $p_{k}$ sufficiently large, the
r.h.s. in (4.11) is bounded above by

$c\cdot 2^{-\frac{p_{k}}{2\log p_{k}}}\leq
c2^{-\frac{\sqrt{\ell}}{2\log\sqrt{\ell}}}\leq e^{-\ell^{\lambda}}.$ (4.12)

Moreover, we can choose $c>0$ sufficiently small such that the inequalities
above hold for all $p_{k}$. Therefore, the designated flow is admissible, and
by [LP16, Theorem 3.1] we have $\lambda_{c}\geq\frac{1}{2}$. We conclude the
proof.

∎

##  5\. proof of Theorem 2.3

We first deal with the statement about recurrence. Since
$\lambda>{\mathrm{IBN}}({\mathcal{T}})$, then

$\inf_{\pi\in\Pi}\sum_{e\in\pi}\exp\left(-|e|^{\lambda}\right)=0.$ (5.1)

Therefore, there exists a sequence of pairwise disjoint cutsets
$(\pi_{n})_{n\geq 1}\subset\Pi$ with $\pi_{n}\cap\pi_{m}=\emptyset$ for $n\neq
m$, satisfying

$\forall\
n\in{\mathbb{N}},\quad\sum_{e\in\pi_{n}}\exp\left(-|e|^{\lambda}\right)\leq\frac{1}{n}.$

We apply the Nash-Williams Criterion [LP16, Page 37] to give a lower bound on
the effective resistance, defined in [LP16, Eq. (2.4)], between $\varrho$ and
infinity:

${\mathcal{R}}(\varrho\leftrightarrow\infty)\geq\sum_{n=1}^{\infty}\left(\sum_{e\in\pi_{n}}\exp\left(-|e|\right)^{\lambda}\right)^{-1}=\infty.$
(5.2)

Thus, X is recurrent.

Now we move to treat the statement about transience by applying [LP16,
Proposition 3.4]. We take
$\lambda^{\prime}\in(\lambda,{\mathrm{IBN}}({\mathcal{T}}))$ and define
$w_{n}\colonequals\exp\left(-n^{\lambda^{\prime}}+n^{\lambda}\right)$ for
$n\in{\mathbb{N}}$. We have

$\sum_{n=1}^{\infty}w_{n}<\infty,$

and $w_{|e|}c(e)=\exp(-|e|^{\lambda^{\prime}})$. By [LP16, Theorem 3.1], we
have

$\displaystyle\max\left\\{\mathrm{Strength}(\theta):\ \theta\text{ flows from
$\varrho$ to $\infty$ satisfying }\forall e\in E,\ 0\leq\theta(e)\leq
c(e)w_{|e|}\right\\}$ (5.3) $\displaystyle=$
$\displaystyle\inf_{\pi\in\Pi}\sum_{e\in\pi}c(e)w_{|e|}>0$

where the last inequality uses
$\lambda^{\prime}<{\mathrm{IBN}}({\mathcal{T}})$. By [LP16, Proposition 3.4],
there exists a flow $\theta$ satisfying $0\leq\theta(e)\leq w_{|e|}c(e)$ for
all $e\in E$ whose energy is finite. Therefore, by [LP16, Theorem 2.11], X is
transient. ∎

##  6\. Proof of Theorem 2.4

We first show that $\Theta({\mathcal{T}})\leq{\mathrm{IBN}}({\mathcal{T}})$ by
the first moment method as in [LP16, Proposition 5.8]. For $x\in V$, let
$e(x)$ denote the edge connecting $x$ with its parent
$\accentset{\leftharpoonup}{x}$. For any cutset $\pi$ separating $\varrho$
from $\infty$, we have

$\\{\varrho\leftrightarrow\infty\\}\subset\bigcup_{x:\
e(x)\in\pi}\\{\varrho\leftrightarrow x\\},$

and then

${\mathbb{P}}\left[\varrho\leftrightarrow\infty\right]\leq\inf_{\pi\in\Pi}\sum_{x:\
e(x)\in\pi}{\mathbb{P}}\left[\varrho\leftrightarrow x\right]$ (6.1)

where $\Pi$ is the set of cutsets. Moreover,
${\mathbb{P}}\left[\varrho\leftrightarrow x\right]=\prod_{y\leq
x}\exp(-|y|^{-1+\lambda})$, and there exist two constant
$c(\lambda),C(\lambda)>0$ such that for all $n\in{\mathbb{N}}$

$c(\lambda)\leq\frac{1}{n^{\lambda}}\sum_{i=1}^{n}i^{-1+\lambda}\leq
C(\lambda).$

Then for $\lambda>{\mathrm{IBN}}({\mathcal{T}})$, we have

${\mathbb{P}}\left[\varrho\leftrightarrow\infty\right]\leq\inf_{\pi\in\Pi}\sum_{x:\
e(x)\in\pi}\exp\left(-c|x|^{\lambda}\right)=0.$ (6.2)

Therefore, $\Theta({\mathcal{T}})\leq{\mathrm{IBN}}({\mathcal{T}})$.

Now we turn to show $\theta({\mathcal{T}})\geq{\mathrm{IBN}}({\mathcal{T}})$
by applying [LP16, Theorem 5.14], i.e.

${\mathbb{P}}\left[\varrho\leftrightarrow\infty\right]\geq\frac{{\mathcal{C}}(\varrho\leftrightarrow\infty)}{1+{\mathcal{C}}(\varrho\leftrightarrow\infty)}$
(6.3)

where, as in [LP16, Equation (5.13)], the conductance $c(e(x))$ of the edge
$e(x)$ is defined by

$c(e(x))\colonequals\frac{{\mathbb{P}}\left[\varrho\leftrightarrow
x\right]}{1-{\mathbb{P}}\left[e(x)\text{ is
open}\right]}=\frac{1}{1-\exp\left(-|x|^{-1+\lambda}\right)}\prod_{\varrho<y\leq
x}{\mathbb{P}}\left[e(y)\text{ is open }\right]$ (6.4)

Whence, it suffices to show that for
$\lambda\in(0,{\mathrm{IBN}}({\mathcal{T}}))$, we have
${\mathcal{C}}(\varrho\leftrightarrow\infty)>0.$ By (6.4), for
$\lambda^{\prime}\in(\lambda,{\mathrm{IBN}}({\mathcal{T}}))$, there exists a
constant $c>0$ such that for all $x\neq\varrho$

$c(e(x))\geq\exp\left(-C(\lambda)|x|^{\lambda}\right)\geq
c\exp(-|x|^{\lambda^{\prime}}).$

By Theorem 2.3 and Rayleigh’s Monotonicity Principle, we obtain
${\mathcal{C}}(\varrho\leftrightarrow\infty)>0$ to conclude the proof.

∎

##  7\. Random walks with random conductance

In this section, we follow the blueprint in [CHK19] to prove Theorem 2.5. We
define $\psi_{RC}:E\mapsto[0,1]$ by $\psi_{RC}(e)=1$ for $|e|=1$, and for
$|e|>1$

$\psi_{RC}(e)\colonequals\frac{\sum_{g<e}C_{g}^{-1}}{\sum_{g\leq
e}C_{g}^{-1}}.$ (7.1)

which is the probability that the RWRC, restricted to $[\varrho,e^{+}]$ and
starting from $e^{-}$, hits $e^{+}$ before hitting $\varrho$. Let

$\Psi_{RC}(e)\colonequals\prod_{g\leq e}\psi_{RC}(e)=\frac{1}{\sum_{g\leq
e}C_{g}^{-1}}$ (7.2)

which is the probability of RWRC, restricted to $[\varrho,e^{+}]$ and starting
at $\varrho$, hits $e^{+}$ before returning to $\varrho$. For any function
$\psi:E\mapsto[0,1]$, setting $\Psi(e)\colonequals\prod_{g\leq e}\psi(g)$ and

$RT({\mathcal{T}},\psi)\colonequals\sup\left\\{\gamma>0:\inf_{\pi\in\Pi}\sum_{e\in\pi}\Psi(e)^{\gamma}>0\right\\},$
(7.3)

we state [CKS20, Theorem 2.5] in our setting.

######  Proposition 7.1 (Theorem 2.5 in [CKS20]).

For any locally finite, infinite tree ${\mathcal{T}}$, we have

  * •

if $RT({\mathcal{T}},\psi_{RC})<1$ ${\mathbb{P}}$-a.s., then RWRC associated
with $\psi_{RC}$ is recurrent;

  * •

if $RT({\mathcal{T}},\psi_{RC})>1$ with positive ${\mathbb{P}}$-probability,
then RWRC associated with $\psi_{RC}$ is transient.

###  7.1. Recurrence

######  Proposition 7.2.

If $\lambda>\alpha={\mathrm{IBN}}({\mathcal{T}})$, then RWRC associated with
$\psi_{RC}$ is recurrent almost surely.

###### Proof.

For fixed $\varepsilon>0$ sufficiently small, we want to apply Proposition 7.1
for which we need to show

$\inf_{\pi\in\Pi}\sum_{e\in\pi}\Psi_{RC}(e)^{1-\varepsilon}=0.$ (7.4)

We first show that typically $\Psi_{RC}(e)$ is small:

${\mathbb{P}}\left[\sum_{g\leq
e}C_{g}^{-1}\leq\exp\left(|e|^{\lambda}\right)\right]\leq{\mathbb{P}}\left[\bigcap_{g\leq
e}\left\\{C_{g}^{-1}\leq\exp\left(|e|^{\lambda}\right)\right\\}\right]\\\
=\prod_{g\leq
e}{\mathbb{P}}\left[\left\\{C_{g}^{-1}\leq\exp\left(|e|^{\lambda}\right)\right\\}\right]=\left(1-{\mathbb{P}}\left[C_{e}<\exp\left(-|e|^{\lambda}\right)\right]\right)^{|e|}\\\
\leq\exp\left(-L(|e|)|e|^{\lambda}\right)$ (7.5)

where we have used (2.17) and the inequality $1-x\leq\exp(-x)$ for all
$x\in[0,1]$ in the last inequality.

Taking $\varepsilon>0$ such that $\alpha+2\varepsilon<\lambda$, by definition
of ${\mathrm{IBN}}$ in (2.9) there exists a sequence of cutsets
$(\pi_{n})_{n}\subset\Pi$ satisfying

$\forall
n\in{\mathbb{N}},\quad\quad\sum_{e\in\pi_{n}}\exp\left(-|e|^{\alpha+\varepsilon}\right)\leq\exp(-n).$
(7.6)

Concerning $(\pi_{n})_{n}\subset\Pi$, we have

${\mathbb{P}}\left[\bigcup_{e\in\pi_{n}}\left\\{\sum_{g\leq
e}C_{g}^{-1}\leq\exp\left(|e|^{\lambda}\right)\right\\}\right]\leq\sum_{e\in\pi_{n}}{\mathbb{P}}\left[\left\\{\sum_{g\leq
e}C_{g}^{-1}\leq\exp\left(|e|^{\lambda}\right)\right\\}\right]\\\
\leq\sum_{e\in\pi_{n}}\exp\left(-L(|e|)|e|^{\lambda}\right),$ (7.7)

and then

$\sum_{n=1}^{\infty}{\mathbb{P}}\left[\bigcup_{e\in\pi_{n}}\left\\{\sum_{g\leq
e}C_{g}^{-1}\leq\exp\left(|e|^{\lambda}\right)\right\\}\right]\leq\sum_{n=1}^{\infty}\sum_{e\in\pi_{n}}\exp\left(-L(|e|)|e|^{\lambda}\right)<\infty\\\
\leq\sum_{n=1}^{\infty}\sum_{e\in\pi_{n}}C\exp\left(-|e|^{\alpha+\varepsilon}\right)<\infty,$
(7.8)

where we have used (7.6) and $\alpha+\varepsilon<\lambda$. By Borel-Cantelli
Lemma, for almost surely all fixed realization $(C_{e})_{e\in E}$, and all
$n\geq N((C_{e})_{e\in E})$, we have

$\forall e\in\pi_{n},\quad\quad\sum_{g\leq
e}C_{g}^{-1}\geq\exp\left(|e|^{\lambda}\right)$

and thus

$\liminf_{n\to\infty}\sum_{e\in\pi_{n}}\Psi_{RC}(e)^{1-\varepsilon}=\liminf_{n\to\infty}\sum_{e\in\pi_{n}}\left(\sum_{g\leq
e}C_{g}^{-1}\right)^{-(1-\varepsilon)}\leq\liminf_{n\to\infty}\sum_{e\in\pi_{n}}\exp\left(-(1-\varepsilon)|e|^{\lambda}\right)=0$
(7.9)

where the last equality is by $\lambda>\alpha$. Therefore, we have
$RT({\mathcal{T}},\psi_{RC})\leq 1-\varepsilon$ and conclude the proof by
Proposition 7.1.

∎

###  7.2. Transience

The goal of this subsection is the following proposition.

######  Proposition 7.3.

If $\lambda<\alpha={\mathrm{IBN}}({\mathcal{T}})$, then the RWRC associated
with $\psi_{RC}$ is transient.

We adopt the definition of quasi-independence in [CHK19, Definition 4.1].

######  Definition 7.4.

An edge percolation is quasi-independent if there exists a constant
$C_{Q}\in(0,\infty)$ such that for any two edges $e_{1},e_{2}\in E$ with their
common ancestor $e_{1}\wedge e_{2}$ satisfy

$\displaystyle{\mathbf{P}}\left(e_{1},e_{2}\in C(\varrho)\ |\ e_{1}\wedge
e_{2}\in C(\varrho)\right)\leq C_{Q}\cdot$
$\displaystyle{\mathbf{P}}\left(e_{1}\in C(\varrho)\ |\ e_{1}\wedge e_{2}\in
C(\varrho)\right)$ (7.10) $\displaystyle\cdot$
$\displaystyle{\mathbf{P}}\left(e_{2}\in C(\varrho)\ |\ e_{1}\wedge e_{2}\in
C(\varrho)\right),$

where $C(\rho)$ is the connected component of the root $\rho$.

######  Proposition 7.5 (Proposition 4.2 in [CHK19]).

Consider an edge-percolation (not necessarily independent), such that edges at
generation $1$ are open almost surely, and for $e_{1}\in E$ with $|e_{1}|>1$

${\mathbf{P}}\left(e_{1}\in C(\varrho)\ |\ e_{0}\in
C(\varrho)\right)=\psi(e_{1})>0$ (7.11)

where $e_{0}\sim e_{1}$ and $e_{0}<e_{1}$. If $RT({\mathcal{T}},\psi)<1$, then
$C(\varrho)$ is finite almost surely. If the percolation is quasi-independent
and $RT({\mathcal{T}},\psi)>1$, then $C(\varrho)$ is infinite with positive
${\mathbf{P}}-$probability.

######  Corollary 7.6.

Let ${\mathcal{T}}$ be a locally finite, infinite tree with
$\alpha:={\mathrm{IBN}}({\mathcal{T}})\in(0,1)$. Fix a parameter
$z\in(0,\infty)$ and perform a percolation on the edges (not necessarily
independent) satisfying (7.11). Assume there exists $n_{0}\in{\mathbb{N}}$ and
$c>0$ such that any $e\in E$ with $|e|>n_{0}$ satisfies

$\psi(e)\leq 1-c|e|^{-z}.$ (7.12)

If $z\in(0,1-\alpha)$, then the percolation is subcritical.

###### Proof.

For a cutset $\pi$, define $|\pi|\colonequals\inf\\{|e|:\ e\in\pi\\}.$ For
$\gamma>0$, we have

$\inf_{\pi\in\Pi:\ |\pi|\leq
n_{0}}\sum_{e\in\pi}\exp\left(-|e|^{\gamma}\right)\geq\exp\left(-n_{0}^{\gamma}\right)>0.$

Thus, for all $\gamma>\alpha$,

$\inf_{\pi\in\Pi:\
|\pi|>n_{0}}\sum_{e\in\pi}\exp\left(-|e|^{\gamma}\right)=\inf_{\pi\in\Pi}\sum_{e\in\pi}\exp\left(-|e|^{\gamma}\right)=0.$

Moreover, for any $\beta>0$ and $z\in(0,1-\alpha)$, there exists a constant
$C>0$ such that for all $e\in E$ with $|e|=n_{0}$

$\prod_{g\leq e}\psi(g)\leq C\prod_{g\leq e}\left(1-c|g|^{-z}\right).$

We have

$\inf_{\pi\in\Pi:\ |\pi|>n_{0}}\sum_{e\in\pi}\prod_{g\leq
e}\psi(e)^{\beta}\leq C^{\beta}\inf_{\pi\in\Pi:\
|\pi|>n_{0}}\sum_{e\in\pi}\prod_{g\leq e}\left(1-c|g|^{-z}\right)^{\beta}\\\
\leq\inf_{\pi\in\Pi:\
|\pi|>n_{0}}C^{\beta}\sum_{e\in\pi}\exp\left(-c\beta\sum_{g\leq
e}|g|^{-z}\right)\leq\inf_{\pi\in\Pi:\
|\pi|>n_{0}}C^{\prime}\sum_{e\in\pi}\exp\left(-\frac{c\beta}{1-z}|e|^{1-z}\right)=0$
(7.13)

where the first inequality uses (7.12), the second inequality uses $1-x\leq
e^{-x}$ for all $x\geq 0$, and the last inequality is by integral
approximation and $1-z>\alpha$. Therefore, $RT({\mathcal{T}},\psi)<1$, and
then we conclude the proof by Proposition 7.5.

∎

######  Proposition 7.7.

Let ${\mathcal{T}}$ be a locally finite, infinite tree with
${\mathrm{IBN}}({\mathcal{T}})=\alpha\in(0,1)$, and perform a quasi-
independent percolation on the edges of ${\mathcal{T}}$ such that (7.11)
holds. Fix $z>1-\alpha$, and assume there exists $c>0$ and
$n_{0}\in{\mathbb{N}}$ such that for all $e$ with $|e|>n_{0}$,

$\psi(e)\geq 1-c|e|^{-z}.$

Then we have:

  * (1)

$RT({\mathcal{T}},\psi)>1$ and ${\mathcal{C}}(\varrho)$ is infinite with
positive ${\mathbb{P}}-$probability.

  * (2)

${\mathrm{IBN}}({\mathcal{C}}(\varrho))\geq 1-z$ With positive
${\mathbb{P}}-$probability.

###### Proof.

We first deal with $(1)$. For $\pi\in\Pi$, let $|\pi|\colonequals\inf\\{|e|:\
e\in\pi\\}$. For any $\beta>1$, since $\psi(e)>0$ for all $e\in E$, we have

$\inf_{\pi\in\Pi:\ |\pi|\leq n_{0}}\sum_{e\in\pi}\prod_{g\leq
e}\psi(g)^{\beta}>0,$ (7.14)

and

$\inf_{\pi\in\Pi:\ |\pi|>n_{0}}\sum_{e\in\pi}\prod_{g\leq
e}\psi(g)^{\beta}\geq c^{\prime}\inf_{\pi\in\Pi:\
|\pi|>n_{0}}\sum_{e\in\pi}\prod_{g\leq e}\left(1-c|g|^{-z}\right)^{\beta}\\\
\geq c^{\prime}\inf_{\pi\in\Pi:\
|\pi|>n_{0}}\sum_{e\in\pi}\exp\left(-2c\beta\sum_{g\leq e}|g|^{-z}\right)\geq
c^{\prime\prime}\inf_{\pi\in\Pi:\
|\pi|>n_{0}}\sum_{e\in\pi}\exp\left(-\frac{2c\beta}{1-z}|e|^{1-z}\right)>0$
(7.15)

where the second inequality is by $1-x\geq e^{-2x}$ for all $x\in[0,1/2]$, and
the last inequality is by $1-z<\alpha$. Therefore, $RT({\mathcal{T}},\psi)>1$.
As the percolation is quasi-independent, we conclude the proof for (1) by
Proposition 7.5.

Now we move to (2). On the event $\\{{\mathcal{C}}(\varrho)\text{ is
infinite}\\}$ which has positive ${\mathbb{P}}-$probability, we perform an
independent percolation on the edges of ${\mathcal{C}}(\varrho)$ on which an
edge $e$ is open with probability $1-p|e|^{-z}$ independently. Let
${\mathcal{C}}^{\prime}(\varrho)$ denote the resulting cluster containing
$\varrho$. Thus, it is a quasi-independent percolation on ${\mathcal{T}}$ and

${\mathbf{P}}\left(e_{1}\in{\mathcal{C}}^{\prime}(\varrho)\ |\
{\mathcal{C}}^{\prime}(\varrho)\right)=\psi(e)(1-p|e|^{-z})\geq
1-(c+p)|e|^{-z}.$ (7.16)

We apply (1) to obtain that ${\mathcal{C}}^{\prime}(\varrho)$ is infinite with
positive probability. By Corollary 7.6, we have
${\mathrm{IBN}}({\mathcal{C}}(\varrho))\geq 1-z$. Therefore, we conclude the
proof.

∎

###  7.3. Percolation linked to transience

Given a realization of $(C_{e})_{e\in E}$, we define a percolation on the
edges of ${\mathcal{T}}$ as following: $\\{e\text{ is open }\\}$ holds almost
surely for $|e|=1$, and for $|e|>1$

$\left\\{e\text{ is open }\right\\}\colonequals\bigcap_{g\leq
e}\left\\{C_{g}^{-1}\leq\exp\left(|g|^{\lambda}\right)\right\\}.$ (7.17)

Moreover, we define

$\psi_{C}(e)\colonequals\begin{cases}1&\text{ if }|e|=1,\\\
{\mathbb{P}}\left(e\in{\mathcal{C}}(\varrho)\ |\
e_{0}\in{\mathcal{C}}(\varrho)\right)&\text{ if }|e|>1,\end{cases}$ (7.18)

where $e_{0}\sim e$ and $e_{0}<e$.

######  Proposition 7.8.

The percolation defined in (7.18) is quasi-independent. Moreover, for all
$\varepsilon\in(0,\alpha/2)$ and $\lambda=\alpha-2\varepsilon$, we have
$RT({\mathcal{T}},\psi_{C})>1$ and with positive ${\mathbb{P}}-$probability
${\mathrm{IBN}}({\mathcal{C}}(\varrho))\geq\alpha-\varepsilon.$

###### Proof of Proposition 7.3 from Proposition 7.8.

Let ${\mathcal{C}}(\varrho)\colonequals(V_{C},E_{C})$ denote the graph of the
cluster containing $\varrho$. For any cutset $\pi\subset E$, $\pi\cap E_{C}$
is a cutset of ${\mathcal{C}}(\varrho)$, and let $\Pi_{C}$ denote the set of
cutsets of ${\mathcal{C}}(\varrho)$. Thus for $\delta>0$, we have

$\inf_{\pi\in\Pi}\sum_{e\in\pi}\left(\sum_{g\leq
e}C_{g}^{-1}\right)^{-(1+\delta)}\geq\inf_{\pi\in\Pi_{C}}\sum_{e\in\pi}\left(\sum_{g\leq
e}C_{g}^{-1}\right)^{-(1+\delta)}\geq
c\inf_{\pi\in\Pi_{C}}\sum_{e\in\pi}\exp\left(-(1+\delta)|e|^{\alpha-\frac{3\varepsilon}{2}}\right)>0$
(7.19)

where the second inequality is by (7.17) so that

$\sum_{g\leq e}C_{g}^{-1}\leq|e|\exp\left(|e|^{\lambda}\right)\leq
C_{1}\exp\left(2|e|^{\lambda}\right)\leq
C\exp\left(|e|^{\alpha-\frac{3\varepsilon}{2}}\right)$

and the last inequality is by Proposition 7.8. Therefore
$RT({\mathcal{T}},\psi_{RC})\geq 1+\delta$, and then we conclude the proof by
Proposition 7.1 and Kolmogorov’s $0-1$ law.

∎

###### Proof of Proposition 7.8.

We first show that the percolation is quasi-independent. Let $e_{1},e_{2}\in
E$ with $e=e_{1}\wedge e_{2}$, and we have

${\mathbb{P}}\left(e_{1},e_{2}\in{\mathcal{C}}(\varrho)\ |\
e\in{\mathcal{C}}(\varrho)\right)={\mathbb{P}}\left(\bigcap_{i=1}^{2}\bigcap_{e<g\leq
e_{i}}\left\\{C_{g}^{-1}\leq\exp\left(|g|^{\lambda}\right)\right\\}\right)\\\
={\mathbb{P}}\left(\bigcap_{e<g\leq
e_{1}}\left\\{C_{g}^{-1}\leq\exp\left(|g|^{\lambda}\right)\right\\}\right){\mathbb{P}}\left(\bigcap_{e<g\leq
e_{2}}\left\\{C_{g}^{-1}\leq\exp\left(|g|^{\lambda}\right)\right\\}\right)\\\
={\mathbb{P}}\left(e_{1}\in{\mathcal{C}}(\varrho)\ |\
e\in{\mathcal{C}}(\varrho)\right){\mathbb{P}}\left(e_{1}\in{\mathcal{C}}(\varrho)\
|\ e\in{\mathcal{C}}(\varrho)\right).$ (7.20)

Therefore, the percolation is quasi-independent.
Moreover, for $e\sim e_{0}$ and $e_{0}<e$, we have

$1-\psi_{C}(e)={\mathbb{P}}\left(e\not\in{\mathcal{C}}(\varrho)\ |\
e_{0}\in{\mathcal{C}}(\varrho)\right)={\mathbb{P}}\left(C_{e}^{-1}>\exp\left(|e|^{\lambda}\right)\right)\\\
=L(|e|)\cdot|e|^{-(1-\lambda)}\leq
C|e|^{-(1-\lambda)+\varepsilon}=C|e|^{-(1-\alpha+\varepsilon)}$ (7.21)

where the second last inequality holds for all $|e|>n_{0}$ with some
$n_{0}\in{\mathbb{N}}$ as $L(n)=o(n^{\varepsilon})$. Then we conclude the
proof by Proposition 7.7. ∎

Combining Proposition 7.2 with Proposition 7.3, we conclude the proof of
Theorem 2.5.

##  8\. Firefighting and the intermediate branching number

In this section we prove Theorem 2.6 that the Intermediate Branching Number is
the critical threshold for the firefighter problem on trees. Our strategy
follows the strategy in [Leh19] for the (standard) branching number on
exponential growth trees. We first state two Lemmas proved by Lehner. We
include their (short) proofs in our notation for sake of completeness.

Let $\varrho\in V$ be rooted, and $|v|$ is the graph distance between
$\varrho$ and $v$. The following lemma says that it is sufficient to consider
the following initial fire set

$B(k)\colonequals\left\\{v\in V:\ |v|\leq k\right\\},\quad k\in{\mathbb{N}}.$
(8.1)

######  Lemma 8.1 (Lemma 2.1 [Leh19]).

The graph ${\mathcal{G}}$ satisfies $g$-containment if and only if for all
$k\in{\mathbb{N}}$, there is a containable map $\Upsilon_{k}$ for $B(k)$.

###### Proof.

Observe that if $Z_{0}^{\prime}\subset Z_{0}$ and $\Upsilon$ is containable
for $Z_{0}$, then $\Upsilon$ is also containable for $Z_{0}^{\prime}$ since
$Z_{n}^{\prime}\subset Z_{n}$. Due to this monotonicity, we conclude the
proof. ∎

When ${\mathcal{G}}$ is a tree, we can go one step further due to the
structure of trees. Given $V_{0}\subset V$, let ${\mathcal{G}}-V_{0}$ be the
(connected/disconnected) graph obtained by deleting all the edges whose
further endpoints are in $V_{0}$. For a subset $U\subset V$, we say that $U$
is a surrounding set for $Z_{0}$ if $U\cap Z_{0}=\emptyset$, $U$ is a cutset
and $Z_{0}$ is a subset of the finite component of ${\mathcal{G}}-U$. Observe
that a containable map $\Upsilon$ for $Z_{0}$ provides a surrounding set $U$
which is the set of those vertices with one neighbor in
$Z_{\infty}=\cup_{n=0}^{\infty}Z_{n}$ and $U\cap Z_{\infty}=\emptyset$.
Conversely, if there is a legal map $\Upsilon$ protect a sounding set $U$,
then $\Upsilon$ is containable for $Z_{0}$. The following lemma gives a
criterion to tell whether ${\mathcal{G}}$ is $g$-containable.

######  Lemma 8.2 (Lemma 2.2 [Leh19]).

A locally finite, infinite tree ${\mathcal{T}}$ is $g$-containable if and only
if for each $B(k)$ with $k\in{\mathbb{N}}$ there exists a surrounding set $U$
for $B(k)$ and all $n\in{\mathbb{N}}$ such that

$\\#U_{k+n}\colonequals\\#\left\\{v\in U:\ |v|\leq
k+n\right\\}\leq\sum_{i=1}^{n}g_{i}.$ (8.2)

###### Proof.

If ${\mathcal{T}}$ is $g$-containable, we take $Z_{0}=B(k)$ and the
corresponding containable map $\Upsilon_{k}$ provides a sounding set $U$ for
$B(k)$ by taking the protected vertices
$U\colonequals\cup_{j=1}^{\infty}W_{j}$. From the definition of containable
maps, we see that $U$ satisfies (8.2) for all $n\in{\mathbb{N}}$.

For each given $Z_{0}=B(k)$, now we assume that (8.2) is satisfied for all
$n\in{\mathbb{N}}$. We first order all the vertices in $U$ according to their
distance to $\varrho$ such that vertices with smaller distance to $\varrho$
have higher priority (arbitrary order among vertices with the same distance to
$\varrho$). The map $\Upsilon$ is defined as follows: $\Upsilon_{k}(1)$ is the
set of the first $g_{1}$ highest priority vertices in $U$, and
$\Upsilon_{k}(n)$ is the set of the highest $g_{n}$ priority vertices of
$U\setminus\cup_{j=1}^{n-1}\Upsilon_{k}(j)$ for $n>1$. We can see that by
(8.2) the map $\Upsilon_{k}$ is legal. Moreover, since $U$ is a surrounding
set and protected by $\Upsilon$, then $\Upsilon$ is a containable map. ∎

###### Proof of Theorem 2.6 .

We first show that $\lambda_{c}\leq\alpha$. For any fixed
$\lambda\in(\alpha,1)$, we define
$g_{n}\colonequals\lfloor\exp\left(n^{\lambda}\right)\rfloor$. For each fixed
$B(k)$, we define

$\varepsilon=\exp\left(-k^{\lambda}\right)-\exp\left(-(k+1)^{\lambda}\right)>0.$

Since $\lambda>\alpha$, by the definition of ${\mathrm{IBN}}$, there exists a
cutset $\pi\subset E$ such that

$\sum_{e\in\pi}\exp\left(-|e|^{\lambda}\right)<\varepsilon.$

Therefore, $\pi$ does not contain any edge in $B(k)$, i.e.
$\inf_{e\in\pi}|e|>k$. We define

$U\colonequals\left\\{v\in V:\ \exists e\in\pi,e^{+}=v\right\\}$ (8.3)

which is a surrounding set for $B(k)$. Recalling $U_{n}^{\prime}=\\{v\in U:\
|v|=n\\}$, we have

$\varepsilon>\sum_{e\in\pi}\exp\left(-|e|^{\lambda}\right)=\sum_{v\in
U}\exp\left(-|v|^{\lambda}\right)\geq\sum_{v\in
U_{n}^{\prime}}\exp\left(-|v|^{\lambda}\right)=|U_{n}^{\prime}|\exp\left(-n^{\lambda}\right).$
(8.4)

Recalling $U_{n}=\\{v\in U:\ |v|\leq n\\}$, since $U_{n}=\emptyset$ for $n\leq
k$, by (8.4), for $n\geq k+1$ we have

$|U_{n}|=\sum_{j=k+1}^{n}|U_{j}^{\prime}|\leq\sum_{j=k+1}^{n}\left\lfloor\varepsilon\exp\left(j^{\lambda}\right)\right\rfloor\leq\sum_{j=k+1}^{n}\left\lfloor\exp\left((j-k)^{\lambda}\right)\right\rfloor=\sum_{j=1}^{n-k}g_{j}$

where we have used $x^{\lambda}+(1-x)^{\lambda}\geq 1$ for all $x\in[0,1]$ in
the last inequality. Since $k$ is arbitrary, we conclude the proof by Lemma
8.2 and Lemma 8.1.

Now we move to prove $\lambda_{c}\geq\alpha$. For any fixed
$\lambda\in(0,\alpha)$, and any fixed $K>0$, we show that ${\mathcal{T}}$ is
not $g$-containable with $g_{n}\colonequals K\exp(n^{\lambda})$. Taking
$\gamma\in(\lambda,\alpha)$, by the definition of ${\mathrm{IBN}}$ in (2.9),
we have

$\varepsilon\colonequals\inf_{\pi\in\Pi}\sum_{e\in\pi}\exp\left(-|e|^{\gamma}\right)>0.$
(8.5)

Moreover, we choose $k\in{\mathbb{N}}$ such that

$\sum_{n=k+1}^{\infty}nK\exp\left(-n^{\gamma}+n^{\lambda}\right)<\varepsilon,$
(8.6)

which is possible as $\lambda<\gamma$. For the chosen $k$ above, we claim that
there is no surrounding set $U$ for $B(k)$ satisfying (8.2). We argue by
contradiction. Suppose there is one such $U$, and let
$\pi_{U}\colonequals\\{e\in E:\ e^{+}\in U\\}$. By (8.2) and
$U_{n}^{\prime}=\\{v\in U:\ |v|=n\\}$, we have

$\\#U_{n}^{\prime}\leq\\#U_{n}\leq\sum_{j=1}^{n-k}g_{j}\leq
nK\exp\left(n^{\lambda}\right).$ (8.7)

As $\pi_{U}$ is a cutset, combining (8.5) and (8.7), we have

$\varepsilon\leq\sum_{e\in\pi_{U}}\exp\left(-|e|^{\gamma}\right)=\sum_{v\in
U}\exp\left(-|v|^{\gamma}\right)=\sum_{n=k+1}^{\infty}|U_{n}^{\prime}|\exp\left(-n^{\gamma}\right)\\\
\leq\sum_{n=k+1}^{\infty}nK\exp\left(n^{\lambda}\right)\exp\left(-n^{\gamma}\right)<\varepsilon$
(8.8)

which is a contradiction. By Lemma 8.2, we conclude the proof.

∎

##  9\.  Firefighting problem on some permutation wreath groups

We now turn to the study of the firefighting problem on intermediate growth
groups. As was done for exponential growth groups, our strategy will be based
on finding a nice tree inside the group, whose ${\mathrm{IBN}}$ is equal to
the growth rate of the group. However, finding such trees is harder than that
in the exponential growth case. In [Leh19], the lexicographical minimal
spanning tree was used. The lexicographical spanning tree is sub-periodic, and
by a theorem of Furstenberg (See e.g. [Fur67]) sub-periodic trees have a
branching number equal to their growth rate. However, for the IBN, we do not
know such a theorem (See (2.12)). Therefore we must look for other
intermediate growth trees inside the groups. We manage to do this in the case
of certain permutation wreath products. We give a general construction of a
tree inside permutation wreath products whose IBN is bounded below by the
growth exponent of the inverted orbit of an (infinite) given word in the base
group. We then use properties of the inverted orbit in Grigrochuk’s group to
show that for permutation wreath products over Grigorchuk’s group, the IBN of
this tree is equal to the growth rate of the permutation wreath product.

### Proof of Theorem 2.7

We divide the proof into several steps.
Step 1: We first find an infinite word $w=g_{1}g_{2}\cdots$ satisfying

$\text{for all }n\in{\mathbb{N}},\quad\\#{\mathcal{O}}(g_{1}\cdots g_{n})\geq
Cn^{\alpha}.$ (9.1)

By (2.20), for all $n\in{\mathbb{N}}$ there exists a word
$\xi_{n}=g_{1}^{(n)}g_{2}^{(n)}\cdots g_{2^{n}}^{(n)}\in G$ with
$g_{i}^{(n)}\in S_{G}$ such that $\\#{\mathcal{O}}(\xi_{n})\geq C_{2}2^{\alpha
n}.$ We construct an infinite word
$w=\xi_{1}\xi_{2}\xi_{3}\cdots\xi_{n}\cdots$ by concatenating
$(\xi_{n})_{n\in{\mathbb{N}}}$. For $0\leq i<2^{n+1}$, observe

$\begin{gathered}{\mathcal{O}}(\xi_{1}\xi_{2}\cdots\xi_{n}g^{(n+1)}_{1}\cdots
g^{(n+1)}_{i})\supset{\mathcal{O}}(\xi_{n})g^{(n+1)}_{1}\cdots
g^{(n+1)}_{i},\\\ |\xi_{1}\xi_{2}\cdots\xi_{n}g^{(n+1)}_{1}\cdots
g^{(n+1)}_{i}|\leq 4|\xi_{n}|,\end{gathered}$ (9.2)

where $|\xi|$ denotes the number of generators in the word $\xi$. Therefore
$w=\xi_{1}\xi_{2}\cdots$ is a desired word.

Step 2: We now want to use the infinite word $w$ and the wreath structure of
the permutation wreath product to construct our tree. The basic idea is to use
the lamps to branch the path. We want to split in a manner whenever we
encounter a ”new” branching position that is when the inverted orbit increases
by $1$. However, if the orbit of a segment inside the infinite word is a loop
in the base group, then this may cause a loop in our constructed graph, so
that it may not be a tree. An important observation is that the problematic
loops are only those in which the size of the inverted orbit does not increase
(otherwise, the branching breaks the loop in $W$.) We therefore describe a way
to ”delete” those loops where the inverted orbit does not increase. We make
this more precise below.

We start with the following observation

${\mathcal{O}}(g_{1}\cdots
g_{n}g_{n+1})=\left\\{x_{0}g_{n+1}\right\\}\cup{\mathcal{O}}(g_{1}\cdots
g_{n})g_{n+1},$ (9.3)

and in particular $\\#{\mathcal{O}}(g_{1}\cdots
g_{n}g_{n+1})\geq\\#{\mathcal{O}}(g_{1}\cdots g_{n})$. Moreover, for a loop
$g_{i+1}g_{i+2}\cdots g_{i+j}=1_{G}$, we say that this loop does not
contribute to the inverted orbit if

$\text{for all }\,k\in\llbracket 1,j\rrbracket,\quad
x_{0}g_{i+k}\in{\mathcal{O}}(g_{1}\cdots g_{i})g_{i+1}\cdots g_{i+k}.$ (9.4)

In this case, we have

${\mathcal{O}}(g_{1}\cdots g_{i}g_{i+1}\cdots
g_{i+j}g_{i+j+1})={\mathcal{O}}(g_{1}\cdots g_{i}g_{i+j+1}).$ (9.5)

This implies that the erasure of such a loop does not affect the inverted
orbit of any prefix containing this loop, and therefore we can delete it from
the word $w$ without affecting the inverted orbit growth. Notice on the other
hand, that if a loop does not satisfy (9.4), we will not delete it, as
deleting such a loop will decrease the inverted orbit. Such loops however will
not cause a problem as they add at least one new point in the inverted orbit
which we use to branch and thus break the loop in the permutation wreath
product.

Step 3: We next give an algorithm for erasing only those loops in $w$
satisfying (9.4). We use the convention $\inf\emptyset=\infty.$

######  Lemma 9.1.

There exists an infinite word $q=q_{1}q_{2}\cdots$ satisfying: for all
$n\in{\mathbb{N}}$

$\\#{\mathcal{O}}(q_{1}\cdots q_{n})\geq
C_{2}\left(\frac{n}{4}\right)^{\alpha},$ (9.6)

and if $q_{i+1}\cdots q_{i+j}=1_{G}$ is a loop, it does not satisfies (9.4).
That is to say, any loop in $q$ increase the size of the inverted orbit at
least by one.

###### Proof.

We take the word $w=g_{1}g_{2}\cdots g_{n}\cdots$ stated in Step 1 and delete
all those loops satisfying (9.4) in order of appearance, to obtain the word
$q$. We locate these kind of loops by specifying the starting and ending
indices. The starting and ending points of the first loop are

$\begin{gathered}L_{1}\colonequals\inf\\{n\geq 1:\exists
k\in{\mathbb{N}},g_{n}g_{n+1}\cdots g_{n+k}=1_{G}\text{ and
}\\#{\mathcal{O}}(g_{1}\cdots g_{n+k})=\\#{\mathcal{O}}(g_{1}\cdots
g_{n-1})\\},\\\ U_{1}\colonequals\sup\\{\ell>L_{1}:g_{L_{1}}g_{L_{1}+1}\cdots
g_{\ell}=1_{G}\text{ and }\\#{\mathcal{O}}(g_{1}\cdots
g_{\ell})=\\#{\mathcal{O}}(g_{1}\cdots g_{L_{1}-1})\\},\end{gathered}$

where ${\mathcal{O}}(g_{1}\cdots g_{n-1})\colonequals\\{x_{0}\\}$ for $n=1$.
If $L_{1}=\infty$, there is no loop satisfying (9.4) and then we do not need
to erase any loop in $w$. If $L_{1}<\infty$, by (9.5) and (9.1) we have
$U_{1}<\infty.$ Supposing $(L_{i},U_{i})_{1\leq i<m}$ is defined with
$U_{m-1}<\infty$, we define

$\begin{gathered}L_{m}\colonequals\inf\\{n>U_{m-1}:\exists
k\in{\mathbb{N}},g_{n}g_{n+1}\cdots g_{n+k}=1_{G}\text{ and
}\\#{\mathcal{O}}(g_{1}\cdots g_{n+k})=\\#{\mathcal{O}}(g_{1}\cdots
g_{n-1})\\},\\\ U_{m}\colonequals\sup\\{\ell>L_{m}:g_{L_{m}}g_{L_{m}+1}\cdots
g_{\ell}=1_{G}\text{ and }\\#{\mathcal{O}}(g_{1}\cdots
g_{\ell})=\\#{\mathcal{O}}(g_{1}\cdots g_{L_{m}-1})\\}.\end{gathered}$

If $L_{m}=\infty$, then $(L_{i},U_{i})_{1\leq i<m}$ is the final sequence.
Else if $L_{m}<\infty$, then $U_{m}<\infty$ by (9.5) and (9.1). We can iterate
this algorithm until some $L_{i}=\infty$ or we obtain an infinite sequence
$(L_{i},U_{i})_{i\in{\mathbb{N}}}$ with $\lim_{i\to\infty}L_{i}=\infty.$ This
algorithm is well-defined: for any prefix $g_{1}g_{2}\cdots g_{n}$, by (9.1)
we delete at most $n-Cn^{\alpha}$ letter since we only erase those loops
satisfying (9.4). Therefore, for all $n$ sufficiently large, and for a prefix
$g_{1}\cdots g_{n}$ of $w$, to decide which letters in $g_{1}\cdots g_{n}$
will be deleted, we just need to run the algorithm with the prefix
$g_{1}\cdots g_{n}g_{n+1}\cdots g_{2n}$. After the loop erasure procedure in
$q$, we obtain an infinite word $q$ without loops satisfying (9.4):

$q=g_{1}g_{2}\cdots g_{L_{1}-1}g_{U_{1}+1}g_{U_{1}+2}\cdots
g_{L_{2}-1}g_{U_{2}+1}g_{U_{2}+1}\cdots
g_{L_{i}-1}g_{U_{i}+1}g_{U_{i}+2}\cdots g_{L_{i+1}-1}\cdots.$

In words, we delete the loops $(g_{L_{i}}g_{L_{i}+1}\cdots
g_{U_{i}})_{i\in{\mathbb{N}}}$ in $q$ to obtain $q.$ We relabel the indices to
write $q=q_{1}q_{2}\cdots q_{n}\cdots$. The lower bound in (9.6) follows from
(9.1) and the fact that the algorithm does not delete any invert orbit point
in any prefix of $q$. ∎

Step 4: With $q$ at hand, we are ready to construct a tree ${\mathcal{T}}$ in
the Cayley graph $(W,S_{A}\cup S_{B})$ by picking up the vertices for
${\mathcal{T}}$, and two vertices are linked by an edge of type ”$A$” or ”$G$”
according to the rule stated below (2.19).

We fix two generators $a_{1},a_{2}\in S_{A}$ and let $*$ represent a generic
element in $\\{a_{1},a_{2}\\}$. The algorithm for picking the vertices for
${\mathcal{T}}$ is as follows: as we walk along the word $q$ (in the Cayley
$(G,S_{G})$), we place $*$ if and only if the size of the inverted orbit
increases by one. The root of the tree is $1_{W}$, and $a_{1},a_{2}\in
V({\mathcal{T}})$. We mark those positions where the size of the inverted
orbit increases by one when we go along the word $q$ as follows:
$M_{1}\colonequals 1$ and for all $n\geq 2$,

$M_{n}\colonequals\inf\left\\{\ell:\\#{\mathcal{O}}(q_{1}\cdots q_{\ell})\geq
n\right\\}.$ (9.7)

For any $n$, we define

$\zeta(n)\colonequals\sup\left\\{\ell:M_{\ell}\leq n\right\\},$ (9.8)

and then a generic vertex in $V({\mathcal{T}})$ is of the form:

$*q_{1}q_{2}\cdots q_{M_{2}-1}*q_{M_{2}}\cdots
q_{M_{3}-1}*q_{M_{3}}q_{M_{3}+1}\cdots q_{M_{4}-1}*q_{M_{4}}\cdots
q_{M_{\zeta(n)}-1}*q_{M_{\zeta(n)}}q_{M_{\zeta(n)}+1}\cdots q_{n}.$

In other words, for any prefix of $q$, we add a generic generator
$*\in\\{a_{1},a_{2}\\}$ exactly in front of those $q_{i}$s where the size of
the inverted orbit increases by one. Note that after adding $*$ before
$(q_{M_{i}})_{i\in{\mathbb{N}}}$ in the loops of $q$ (in the Cayley graph
$(G,S_{G})$), there is no loop in ${\mathcal{T}}$ any more.

Now we can calculate ${\mathrm{IBN}}({\mathcal{T}})$. Since by construction
${\mathcal{T}}$ is a spherically symmetric tree, we have
${\mathrm{IBN}}({\mathcal{T}})={\mathrm{I_{gr}}}({\mathcal{T}})$. To calculate
${\mathrm{I_{gr}}}({\mathcal{T}})$, we estimate $\\#E_{N}$ where
$E_{n}=\\{x\in V({\mathcal{T}}):\ |x|=n\\}$ with the graph distance $|\cdot|$
in ${\mathcal{T}}$. At distance $n$ in ${\mathcal{T}}$, we count the number of
splitting

$\Lambda(n)\colonequals\sup\left\\{\ell:|{\mathcal{O}}(q_{1}\cdots
q_{\ell})|+\ell\leq n\right\\}$ (9.9)

Since $|{\mathcal{O}}(q_{1}\cdots q_{\ell})|\leq\ell$, we have
$\Lambda(n)\geq(n-2)/2$. As $\\#E_{n}=2^{|{\mathcal{O}}(q_{1}\cdots
q_{\Lambda(n)})|}$, by (9.6) we have

$\liminf_{n\to\infty}\frac{\log\log\\#E_{n}}{\log n}\geq\alpha.$ (9.10)

∎

###### Proof of Corollary 2.8.

Now we turn to deal with (2.22). By Theorem 2.6, the tree ${\mathcal{T}}$ does
not satisfy intermediate containment of rate $\gamma<\alpha$. Furthermore, by
monotonicity, at any time instant $n$ the fire on ${\mathcal{T}}$ is a subset
of the fire on $(W,S_{A}\cup S_{G})$, and then $(W,S_{A}\cup S_{G})$ does not
satisfy intermediate containment of rate $\gamma<\alpha$. Therefore, we have

$\lambda_{c}(W,S_{A}\cup S_{G})\geq\alpha.$ (9.11)

To deal with $\lambda_{c}\leq\alpha$, observe that any initial finite fire
contained in some ball $B(n_{0})$, the total fire at time $n$ is contained in
$B(n_{0}+n)$ for all $n\in{\mathbb{N}}$. Moreover, for fixed $\gamma>\alpha$,
let $(g(n))_{n\in{\mathbb{N}}}$ be the containment satisfying

$\liminf_{n\to\infty}\frac{\log\log g(n)}{\log n}=\gamma.$

Then for $\varepsilon\in(0,(\gamma-\alpha)/2)$, there exits $n_{1}$
sufficiently large such that

$g(n_{1})\geq e^{n_{1}^{\gamma-\varepsilon}}\geq
e^{(n_{1}+n_{0})^{\alpha+\varepsilon}}\geq\\#B(n_{1}+n_{0})$ (9.12)

At time instant $n_{1}$, all the vertices in $E_{n_{1}+n_{0}}$ are not on fire
yet and we can protect them by $E_{n_{0}+n_{1}}\subset B(n_{0}+n_{1})$ and
(9.12). Therefore, the fire is eventually finite, and then we have
$\lambda_{c}\leq\alpha.$ We conclude the proof. ∎

###  9.1. A tree in the wreath permutation group based on the first Grigorchuk
group.

The first Grigorchuk group $G_{012}$ is a subgroup of the automorphism group
of the binary tree. It is generated by $\\{a,b,c,d\\}$ which are defined by
the wreath recursion as follows: let $\varepsilon$ be the transposition of
$(0,1)$, and the wreath recursion $\psi$ is defined as

$\psi:a\mapsto\varepsilon\mathopen{\hbox{\set@color${\langle}$}\kern-1.94444pt\leavevmode\hbox{\set@color${\langle}$}}1,1\mathclose{\hbox{\set@color${\rangle}$}\kern-1.94444pt\leavevmode\hbox{\set@color${\rangle}$}},\quad
b\mapsto\mathopen{\hbox{\set@color${\langle}$}\kern-1.94444pt\leavevmode\hbox{\set@color${\langle}$}}a,c\mathclose{\hbox{\set@color${\rangle}$}\kern-1.94444pt\leavevmode\hbox{\set@color${\rangle}$}},\quad
c\mapsto\mathopen{\hbox{\set@color${\langle}$}\kern-1.94444pt\leavevmode\hbox{\set@color${\langle}$}}a,d\mathclose{\hbox{\set@color${\rangle}$}\kern-1.94444pt\leavevmode\hbox{\set@color${\rangle}$}},\quad
d\mapsto\mathopen{\hbox{\set@color${\langle}$}\kern-1.94444pt\leavevmode\hbox{\set@color${\langle}$}}1,b\mathclose{\hbox{\set<EMAIL_ADDRESS>(9.13)

The generators $\\{a,b,c,d\\}$ satisfy

$a^{2}=b^{2}=c^{2}=d^{2}=1,\quad bc=cb=d,\quad bd=db=c,\quad cd=dc=b.$ (9.14)

We refer to [GP08] and [Man12, Chapter 10] for introductions to the first
Grigorchuk group. Bartholdi and Erschler prove the following theorem
concerning the inverted orbit for $G_{012}$ acting on the rightmost branch of
the binary tree, i.e. $x_{0}=1^{\infty}$ where the binary tree is labeled by
$\\{0,1\\}^{\infty}$ with two vertices linked by en edge if one is obtained by
appending a ”$0$” or ”$1$” to the other.

######  Theorem 9.2 (Propositions 4.4 and 4.7, Lemma 5.1 in [BE12]).

Let $\eta$ be the real root of the polynomial $X^{3}+X^{2}+X-2$ and set
$\alpha=\log 2/\log(2/\eta)\approx 0.7674$. Taking $G=G_{012}$, $A$ some
finite group, $W=A\wr_{X}G_{012}$ and $x_{0}=1^{\infty}$, then the assumptions
in (2.21) and (2.20) are satisfied.

Combining Theorems 9.2, 2.6 and Corollary 2.8 we obtain:

######  Corollary 9.3.

The critical threshold for firefighter problem on $W$ is $\alpha$.

By Theorem 2.7, for the firefight problem on the wreath product group $W$ with
assumptions stated in Theorem 9.2 and (2.21), we have $\lambda_{c}(W)=\alpha$.

### Acknowledgment

The authors thank Mikhail Belolipetsky, Russell Lyons and Olivier Thom for
helpful discussions. The authors are supported by the Israel science
foundation grant #957/20. This work has been perform partially when S.Y. was a
postdoc fellow in UFBA and a visiting researcher in IMPA.

## References

  * [ABK20] Gideon Amir, Rangel Baldasso, and Gady Kozma.  The firefighter problem on polynomial and intermediate growth groups.  Discrete Math., 343(11):112077, 4, 2020.
  * [BE12] Laurent Bartholdi and Anna Erschler.  Growth of permutational extensions.  Invent. Math., 189(2):431–455, 2012.
  * [CHK18] Andrea Collevecchio, Mark Holmes, and Daniel Kious.  On the speed of once-reinforced biased random walk on trees.  Electron. J. Probab., 23:Paper No. 86, 32, 2018.
  * [CHK19] Andrea Collevecchio, Cong Bang Huynh, and Daniel Kious.  The branching-ruin number as critical parameter of random processes on trees.  Electron. J. Probab., 24:Paper No. 121, 29, 2019.
  * [CKS20] Andrea Collevecchio, Daniel Kious, and Vladas Sidoravicius.  The branching-ruin number and the critical parameter of once-reinforced random walk on trees.  Comm. Pure Appl. Math., 73(1):210–236, 2020.
  * [Fur67] Harry Furstenberg.  Disjointness in ergodic theory, minimal sets, and a problem in Diophantine approximation.  Math. Systems Theory, 1:1–49, 1967.
  * [GP08] Rostislav Grigorchuk and Igor Pak.  Groups of intermediate growth: an introduction.  Enseign. Math. (2), 54(3-4):251–272, 2008.
  * [Gri83] R. I. Grigorchuk.  On the Milnor problem of group growth.  Dokl. Akad. Nauk SSSR, 271(1):30–33, 1983.
  * [Har95] Bert Hartnell.  Firefighter! an application of domination.  In the 24th Manitoba Conference on Combinatorial Mathematics and Computing, University of Minitoba, Winnipeg, Cadada, 1995, 1995.
  * [KP13] Martin Kassabov and Igor Pak.  Groups of oscillating intermediate growth.  Ann. of Math. (2), 177(3):1113–1145, 2013.
  * [Leh19] Florian Lehner.  Firefighting on trees and Cayley graphs.  Australas. J. Combin., 75:66–72, 2019.
  * [LP16] Russell Lyons and Yuval Peres.  Probability on trees and networks, volume 42 of Cambridge Series in Statistical and Probabilistic Mathematics.  Cambridge University Press, New York, 2016.
  * [Lyo90] Russell Lyons.  Random walks and percolation on trees.  Ann. Probab., 18(3):931–958, 1990.
  * [Man12] Avinoam Mann.  How groups grow, volume 395 of London Mathematical Society Lecture Note Series.  Cambridge University Press, Cambridge, 2012.
  * [Nat96] Melvyn B. Nathanson.  Additive number theory, volume 164 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 1996.  The classical bases.
  * [Nat99] Melvyn B. Nathanson.  Number theory and semigroups of intermediate growth.  Amer. Math. Monthly, 106(7):666–669, 1999.


[datatype=bibtex] [fieldset=issn, null] [datatype=bibtex] [fieldset=urldate,
null] [datatype=bibtex] [fieldset=pagetotal, null]

# Proof that the Kalman gain minimizes the generalized variance

Eviatar Bach111Email<EMAIL_ADDRESS>
###### Abstract

The optimal gain matrix of the Kalman filter is often derived by minimizing
the trace of the posterior covariance matrix. Here, I show that the Kalman
gain also minimizes the determinant of the covariance matrix, a quantity known
as the generalized variance. When the error distributions are Gaussian, the
differential entropy is also minimized.

For the classic Kalman filter, the Kalman gain is

$\mathbf{K}=\mathbf{P}^{\text{f}}\mathbf{H}^{\top}(\mathbf{H}\mathbf{P}^{\text{f}}\mathbf{H}^{\top}+\mathbf{R})^{-1},$
(1)

where $\mathbf{P}^{\text{f}}$ is the background error covariance matrix (also
called the prior error covariance matrix), $\mathbf{R}$ is the observation
error covariance matrix, and $\mathbf{H}$ is the linearized observation
operator [1].

Eq. (1) can be shown to minimize $\operatorname{tr}(\mathbf{P}^{\text{a}})$,
where $\mathbf{P}^{\text{a}}$ is the analysis error covariance matrix (also
called the posterior error covariance matrix). In fact, Eq. (1) is often
derived by minimizing $\operatorname{tr}(\mathbf{P}^{\text{a}})$ [7, 12, 8,
1]. $\mathbf{P}^{\text{a}}$ is the updated error covariance after observations
are assimilated, and can be expressed as

$\mathbf{P}^{\text{a}}=\mathbf{(I-KH)}\mathbf{P}^{\text{f}}\mathbf{(I-KH)^{\top}+KRK^{\top}}.$
(2)

Note that this formula for the updated covariance matrix applies to any gain
$\mathbf{K}$, not necessarily optimal [1]. It is sometimes known as the Joseph
form of the covariance update equation [12]. Here I use the notation common in
the atmospheric sciences [6]; in other fields, there are a variety of
notations, but $\mathbf{P}^{\text{f}}$ is sometimes written as
$\mathbf{P}_{k|k-1}$ and $\mathbf{P}^{\text{a}}$ as $\mathbf{P}_{k|k}$.

The trace of a covariance matrix is sometimes known as the total variance.
However, this measure of the dispersion of the probability distribution does
not take into account the cross-covariances between variables. Another scalar
measure of dispersion is the generalized variance, introduced by Samuel S.
Wilks, which is defined as the determinant of the covariance matrix. The
generalized variance has been used in a wide variety of fields as a measure of
multidimensional scatter [9, 4, 2].

Since the determinant of a positive definite matrix is lesser or equal to the
product of its diagonal elements (this follows from Hadamard’s inequality
[5]), nonzero off-diagonal elements decrease the generalized variance. This
captures the intuition that an error distribution with correlated errors is
“less dispersed” than the same distribution with uncorrelated errors, a
property that the total variance does not possess. For a multivariate
Gaussian, contours of the probability density function are ellipsoids of
constant Mahalanobis distance from the mean. The volume of these ellipsoids is
proportional to the square root of the generalized variance. Increasing
correlations between the variables makes the ellipsoid more elongated, and
decreases the volume [13]. The trace and determinant of
$\mathbf{P}^{\text{a}}$ were compared as measures of Kalman filter performance
in [14].

One might ask, then, what Kalman gain is obtained by minimizing the
generalized variance of the analysis (posterior) distribution. Here, I prove
that the Kalman gain in Eq. (1) in fact also minimizes the generalized
variance.

######  Theorem 1.

The Kalman gain in Eq. (1) minimizes the generalized variance.

###### Proof.

We wish to find the optimal gain $\mathbf{K^{*}}$ by minimizing the
generalized variance of the analysis distribution, defined as the determinant
of the analysis covariance matrix:

$\displaystyle\mathbf{K^{*}}$
$\displaystyle={\arg\min}_{\mathbf{K}}\det(\mathbf{P}^{\text{a}})$ (3)
$\displaystyle={\arg\min}_{\mathbf{K}}\log(\det(\mathbf{P}^{\text{a}})),$ (4)

where the second line follows from the fact that $\mathbf{P}^{\text{a}}$ is
positive definite and from the monotonicity of log.

Using an identity of matrix calculus [11],

$\text{d}\log(\det(\mathbf{P}^{\text{a}}))=\operatorname{tr}((\mathbf{P}^{\text{a}})^{-1}\text{d}\mathbf{P}^{\text{a}}).$
(5)

Then $\text{d}\mathbf{P}^{\text{a}}$ can be expanded:

$\displaystyle\text{d}\mathbf{P}^{\text{a}}=$
$\displaystyle-\mathbf{P}^{\text{f}}\mathbf{H}^{\top}\text{d}\mathbf{K}^{\top}-(\text{d}\mathbf{K})\mathbf{H}\mathbf{P}^{\text{f}}+(\text{d}\mathbf{K})\mathbf{H}\mathbf{P}^{\text{f}}\mathbf{H^{\top}K^{\top}}+\mathbf{KH}\mathbf{P}^{\text{f}}\mathbf{H}^{\top}\text{d}\mathbf{K}^{\top}$
(6)
$\displaystyle\qquad+(\text{d}\mathbf{K})\mathbf{RK^{\top}}+\mathbf{KR}\;\text{d}\mathbf{K}^{\top}.$

Substituting Eq. (6) into Eq. (5) and simplifying using properties of the
trace (distributive,
$\operatorname{tr}(\mathbf{A}^{\top})=\operatorname{tr}(\mathbf{A})$, and
invariant under cyclic permutation when sizes are commensurate) as well as
symmetry of the covariance matrices, we obtain

$\text{d}\log(\det(\mathbf{P}^{\text{a}}))=\operatorname{tr}\left((2\mathbf{KH\mathbf{P}^{\text{f}}H^{\top}}+2\mathbf{KR}-2\mathbf{\mathbf{P}^{\text{f}}H^{\top}})^{\top}(\mathbf{P^{\text{a}}})^{-1}\text{d}\mathbf{K}\right)$
(7)

This is equivalent to

$\frac{\text{d}}{\text{d}\mathbf{K}}\log(\det(\mathbf{P}^{\text{a}}))=(\mathbf{P}^{\text{a}})^{-1}(2\mathbf{KH\mathbf{P}^{\text{f}}H^{\top}}+2\mathbf{KR}-2\mathbf{\mathbf{P}^{\text{f}}H^{\top}}).$
(8)

This result can also be verified with http://www.matrixcalculus.org/ [10].

Setting Eq. (8) to $\mathbf{0}$ in order to optimize, and since
$(\mathbf{P}^{\text{a}})^{-1}\neq\mathbf{0}$,

$\mathbf{K^{*}H\mathbf{P}^{\text{f}}H^{\top}+K^{*}R-\mathbf{P}^{\text{f}}H^{\top}=0}.$
(9)

Solving for $\mathbf{K^{*}}$, we recover Eq. (1). ∎

######  Corollary 1.

Under the assumption of Gaussian error distributions, Eq. (1) also minimizes
the differential entropy of the analysis distribution.

###### Proof.

For a multivariate Gaussian with covariance matrix $\boldsymbol{\Sigma}$ and
dimension $N$, the differential entropy is [3]

$\frac{N}{2}\log(2\pi e)+\frac{1}{2}\log(\det(\boldsymbol{\Sigma})).$ (10)

The first term is a constant and can thus be neglected in the minimization.

If the background and observation error distributions are Gaussian, the
analysis error distribution will also be Gaussian. Thus, under the Gaussian
assumption, minimizing the generalized variance is equivalent to minimizing
the differential entropy. ∎

Furthermore, for Gaussian error distributions the related quantities of Rényi
entropy and the entropy power are also minimized [2].

## References

  * [1] Mark Asch, Marc Bocquet and Maëlle Nodet  “Data Assimilation: Methods, Algorithms, and Applications”, Fundamentals of Algorithms  Society for Industrial and Applied Mathematics, 2016  DOI: 10.1137/1.9781611974546
  * [2] Badong Chen, Jianji Wang, Haiquan Zhao and Jose C. Principe  “Insights into Entropy as a Measure of Multivariate Variability”  In _Entropy_ 18.5 Multidisciplinary Digital Publishing Institute, 2016, pp. 196  DOI: 10.3390/e18050196
  * [3] Thomas M. Cover and Joy A. Thomas  “Elements of Information Theory”  Hoboken, N.J: Wiley-Interscience, 2006
  * [4] Ashis Sen Gupta  “Generalized Variance”  In _Encyclopedia of Statistical Sciences_ John Wiley & Sons, Inc., 2006  DOI: 10.1002/0471667196.ess6053.pub2
  * [5] Roger A. Horn and Charles R. Johnson  “Matrix Analysis”  Cambridge: Cambridge University Press, 2013  DOI: 10.1017/9781139020411
  * [6] Kayo Ide, Philippe Courtier, Michael Ghil and Andrew C. Lorenc  “Unified Notation for Data Assimilation: Operational, Sequential and Variational”  In _Journal of the Meteorological Society of Japan. Ser. II_ 75, 1997, pp. 181–189  DOI: 10.2151/jmsj1965.75.1B˙181
  * [7] Andrew H. Jazwinski  “Stochastic Processes and Filtering Theory”  New York: Academic Press, Inc., 1970
  * [8] Eugenia Kalnay  “Atmospheric Modeling, Data Assimilation and Predictability”  New York: Cambridge University Press, 2002
  * [9] S. Kocherlakota and K. Kocherlakota  “Generalized Variance”  In _Encyclopedia of Statistical Sciences_ 3 John Wiley & Sons, Inc., 1983  DOI: 10.1002/0471667196.ess0869
  * [10] Sören Laue, Matthias Mitterreiter and Joachim Giesen  “MatrixCalculus.org – Computing Derivatives of Matrix and Tensor Expressions”  In _Machine Learning and Knowledge Discovery in Databases_ , Lecture Notes in Computer Science  Cham: Springer International Publishing, 2020, pp. 769–772  DOI: 10.1007/978-3-030-46133-1˙48
  * [11] Kaare Brandt Petersen and Michael Syskind Pedersen  “The Matrix Cookbook”  Technical University of Denmark, 2012  URL: http://www2.imm.dtu.dk/pubdb/pubs/3274-full.html
  * [12] Ricardo Todling  “Estimation Theory and Foundations of Atmospheric Data Assimilation”, Office Note Series on Global Modeling and Data Assimilation 1999-01, 1999  URL: https://gmao.gsfc.nasa.gov/pubs/DAO_on/docs/20060010368.pdf
  * [13] Daniel S. Wilks  “Statistical Methods in the Atmospheric Sciences”  Elsevier, 2019  DOI: 10.1016/C2017-0-03921-6
  * [14] C. Yang, L. Kaplan and E. Blasch  “Performance Measures of Covariance and Information Matrices in Resource Management for Target State Estimation”  In _IEEE Transactions on Aerospace and Electronic Systems_ 48.3, 2012, pp. 2594–2613  DOI: 10.1109/TAES.2012.6237611