# Power Law Decay at Criticality for the q-State Antiferromagnetic Potts Model
on Regular Trees

Chenlin Gu, Wei Wu, Kuan Yang  Mathematics Department, NYU Shanghai & NYU-ECNU
Institute of Mathematical Sciences, China  Mathematics Department, NYU
Shanghai & NYU-ECNU Institute of Mathematical Sciences, China  John Hopcroft
Center for Computer Science, Shanghai Jiao Tong University, China

###### Abstract.

We present a proof of the power law decay of magnetic moment for the $q$-state
antiferromagnetic Potts model on the regular tree at critical temperature, and
also justify that the exact exponent is $\frac{1}{2}$. Our proof relies on the
assumption of the uniqueness at critical temperature, which has been
established for $q=3,4$, and for $q\geqslant 5$ with large degree. An
iterative contraction inequality is developed for independent interests.

MSC 2010: 05C99, 60K35, 82B20.

Keywords: antiferromagnetic Potts model, Gibbs measure, infinite regular tree,
critical exponent.

##  1\. Introduction

We study the Gibbs measure of the antiferromagnetic (AF for short) Potts
models on regular trees. Let $\mathbb{T}^{d}_{n}$ be the $d$-ary tree, which
is a rooted tree of height $n$ and every vertex except leaves has $d$
children. Here the height means the graph distance from the root to leaves. We
then use $\partial\mathbb{T}^{d}_{n}$ for the set of leaves and
$\operatorname{int}(\mathbb{T}^{d}_{n}):=\mathbb{T}^{d}_{n}\setminus\partial\mathbb{T}^{d}_{n}$
its interior. Let $q\operatorname{int}\mathbb{N}^{+}$ be the number of state
for the spin in our model and let $[q]=\\{1,2,3,\cdots,q\\}$ be all possible
states. We define $\sigma\in[q]^{\mathbb{T}^{d}_{n}}$ the spin on $d$-ary
tree, and associate it with a Hamiltonian $H^{\xi}_{\mathbb{T}^{d}_{n}}$

(1.1) $\displaystyle
H^{\xi}_{\mathbb{T}^{d}_{n}}(\sigma)=-\sum_{u,v\in\mathbb{T}^{d}_{n},u\sim
v}\mathbf{1}_{\left\\{\sigma_{u}=\sigma_{v}\right\\}},$

where $\xi:\partial\mathbb{T}^{d}_{n}\to[q]$ is the boundary condition for
$\sigma$ i.e. $\sigma_{|\partial\mathbb{T}^{d}_{n}}=\xi$. We define the Gibbs
measure as

(1.2)
$\displaystyle\mu^{\xi}_{\mathbb{T}^{d}_{n},\beta,q}[\sigma]=\frac{1}{Z^{\xi}_{\mathbb{T}^{d}_{n},\beta,q}}\exp\left(-\beta
H^{\xi}_{\mathbb{T}^{d}_{n}}(\sigma)\right),$

where the partition function is defined as

(1.3) $\displaystyle
Z^{\xi}_{\mathbb{T}^{d}_{n},\beta,q}=\sum_{\sigma\in[q]^{\mathbb{T}^{d}_{n}},\sigma_{|\partial\mathbb{T}^{d}_{n}}=\xi}\exp\left(-\beta
H^{\xi}_{\mathbb{T}^{d}_{n}}(\sigma)\right).$

When $\beta>0$, it is the ferromagnetic Potts model where the adjacent spins
tend to be equal, and when $\beta<0$, it is the antiferromagnetic Potts model
(adjacent spins tend to be different) and it is the object we would like to
study.

It is clear, that the probability of each spin configuration in the AF Potts
model only depends on the number of monochromatic edges, i.e., edges that
connecting two identical spins. Thus by setting

(1.4) $\displaystyle p:=e^{\beta}\in(0,1),\qquad
W^{\xi}_{n,p,q}(\sigma):=p^{\\#\\{\\{u,v\\}:u,v\in\mathbb{T}^{d}_{n},\,u\sim
v,\,\sigma_{u}=\sigma_{v}\\}}=\exp\left(-\beta
H^{\xi}_{\mathbb{T}^{d}_{n}}(\sigma)\right),$

and using $\mu^{\xi}_{n,p,q}$ short for
$\mu^{\xi}_{\mathbb{T}^{d}_{n},\beta,q}$, $Z^{\xi}_{n,p,q}$ short for
$Z^{\xi}_{\mathbb{T}^{d}_{n},\beta,q}$, we obtain that

$\displaystyle Z^{\xi}_{n,p,q}$
$\displaystyle=\sum_{\sigma\in[q]^{\mathbb{T}^{d}_{n}},\sigma_{|\partial\mathbb{T}^{d}_{n}}=\xi}W^{\xi}_{n,p,q}(\sigma),$
$\displaystyle\mu^{\xi}_{n,p,q}[\sigma]$
$\displaystyle=W^{\xi}_{n,p,q}(\sigma)/Z^{\xi}_{n,p,q}.$

We use $*$ to indicate the root and use the dictionary notation
$\\{1,2,3,\cdots,d\\}^{\mathbb{N}^{+}}$ for other vertices on the tree. One of
the most well-studied problem in statistical physics is the so-called
uniqueness and non-uniqueness phase transition of the Gibbs measure on
(infinite) graphs. Roughly, the system has a unique Gibbs state if the spin at
each vertex is “not too sensitive” to the value of the spins at long distances
[5]. In the case of regular trees, it is shown by [3] that the uniqueness of
Gibbs state is equivalent to the maximal discrepancy of the probability
distribution at the root tends to zero, namely,

(1.5)
$\displaystyle\limsup_{n\to\infty}\max_{\xi:\partial\mathbb{T}^{d}_{n}\to[q]}\mu^{\xi}_{n,p,q}[\sigma_{*}=1]=\frac{1}{q}.$

Dobrushin [5] formulated an explicit condition that guarantees the uniqueness
of Gibbs states, which implies the AF $q$-state Potts model satisfies the
uniqueness condition whenever either $\beta\leqslant\frac{C_{q}}{\Delta}$, or
$q>2\Delta$, where $\Delta$ is the maximal degree of the graph (see also
[18]). These conditions are far from sharp, and one expects that for the AF
$q$-state Potts model on a regular lattice ${\mathbb{Z}^{d}}$, there is a
critical temperature $\beta_{c}(d)$, such that the model has a unique Gibbs
state for all $\beta<\beta_{c}$, and exhibit multiple Gibbs states for
$\beta>\beta_{c}$. Very few is known for the AF $q$-state Potts model on
${\mathbb{Z}^{d}}$: there is some improvement for the Dobrushin uniqueness
condition on $\mathbb{Z}^{2}$ (see, e.g., [10] for AF Potts model and [1] for
ferromagnetic Potts model); proof of the existence of the multiple Gibbs
states in very high dimension and very low temperature [14, 7, 15]; and proof
of the uniqueness of Gibbs state for $3$-coloring on $\mathbb{Z}^{2}$ [17]
(based on the result of the height function representation in [6]). Otherwise,
the conjecture remains largely open on ${\mathbb{Z}^{d}}$.

In this paper, we focus on the AF Potts model on regular trees and study its
critical exponent. We assume the following hypothesis of the uniqueness of
Gibbs states on trees throughout the paper. Notice that for our main result,
Theorem 1.2, we assume the following hypothesis with the critical value
$p=1-\frac{q}{d+1}$.

######  Hypothesis 1.1.

Let $q,d\in\mathbb{N}^{+}$ and $q\geqslant 2$. Also let
$p\in[1-\frac{q}{d+1},1)\cap(0,1)$. Assume that the $q$-state AF Potts model
on $d$-ary tree with parameter $p$, defined via the measure (1.4), has a
unique Gibbs state in the sense of (1.5).

This uniqueness/non-uniqueness assumption is confirmed in several cases. In
particular, the uniqueness/non-uniqueness threshold for proper $q$-colorings
(i.e., the $\beta=-\infty$ case in (1.3)) was proved by Jonasson [13],
building upon the work of Brightwell and Winkler [3]. Jonasson showed that the
model on the $d$-ary tree exhibits uniqueness if $q>d+1$. When $q\leqslant
d+1$, non-uniqueness follows from the existence of so-called “frozen”
colorings and semitranslation-invariant Gibbs measures [3]. For the general AF
Potts model, it has been known since the 80s that non-uniqueness holds when
$p<p_{c}$, see [16]. For fixed small values of $q$, it is proved that
uniqueness holds on the $d$-ary tree when $p\geqslant p_{c}$ and $p>0$ (see
[9] for the $q=3$, $d\geqslant 2$ case and the $q=d=4$ case, and see [4] for
the $q=4$, $d\geqslant 4$ case). A recent work [2] also claims the uniqueness
for $q\geqslant 5$, $p\geqslant p_{c}(q,d)$ with very large $d$.

Our main results is based on Hypothesis 1.1. Like many statistical physics
model, at the critical temperature, the AF Potts model on the $d$-ary tree
also illustrates a power law decay, and the critical exponent is universal for
the color number $q$ and the degree $d$.

######  Theorem 1.2 (Power law decay).

Under Hypothesis 1.1 and for the critical case $p_{c}=1-\frac{q}{d+1}>0$, the
convergence of marginal probability follows the power law that

(1.6)
$\displaystyle\lim_{n\to\infty}\frac{1}{n}\left(\max_{\xi:\partial\mathbb{T}^{d}_{n}\to[q]}\left|\mu^{\xi}_{n,p_{c},q}[\sigma_{*}=1]-\frac{1}{q}\right|\right)^{-2}=\frac{d^{2}-1}{6d^{2}}\left(\frac{q^{2}}{q-1}\right)^{2}.$

A direct corollary of the main theorem is a upper and a lower bound for the
convergence rate at critical temperature: there exist $0<c(d,q)<C(d,q)<\infty$
such that for $p_{c}=1-\frac{q}{d+1}>0$

(1.7)
$\displaystyle\frac{c}{\sqrt{n}}\leqslant\max_{\xi}\left|\mu^{\xi}_{n,p_{c},q}[\sigma_{*}=1]-\frac{1}{q}\right|\leqslant\frac{C}{\sqrt{n}}.$

######  Remark 1.3.

As mentioned above, Hypothesis 1.1 is justified for certain values of $(q,d)$.
Therefore we obtained (1.6) and (1.7) for the case

  * •

$q=3,4$, for all $d\geqslant q$, and $p_{c}=1-\frac{q}{d+1}$;

  * •

for any $q\geqslant 5$, $d\geqslant d_{0}(q)$ sufficiently large, and
$p_{c}=1-\frac{q}{d+1}$.

We also remark that the critical exponent is only valid for $d\geqslant 2$,
because for $d=1$ it is either $q=1$ a trivial case or $q=2$ for two-coloring
problem with long range order.

######  Remark 1.4.

Using a similar, and somewhat simpler argument, under Hypothesis 1.1, we also
obtain the exact exponential decay rate for the two point function in the sub-
critical phase, namely

(1.8)
$\displaystyle\lim_{n\to\infty}\frac{1}{n}\log\left(\max_{\xi:\partial\mathbb{T}^{d}_{n}\to[q]}\left|\mu^{\xi}_{n,p,q}[\sigma_{*}=1]-\frac{1}{q}\right|\right)=\log\left(\frac{d(1-p)}{p+q-1}\right).$

Again this is verified for $q=3,4$, for all $d\geqslant q$, and $p>p_{c}$; and
for any $q\geqslant 5$, $d\geqslant d_{0}(q)$ sufficiently large, and
$p>p_{c}$.

We now describe the strategy to prove our main result. Let $\sigma^{u}$ be the
subset of spins on the tree rooted by $u\in\\{1,2,\cdots,d\\}$ and $\xi^{u}$
the boundary condition on this subtree. Then one can obtain a recurrence
equation

(1.9)
$\displaystyle\mu^{\xi}_{n,p,q}[\sigma_{*}=1]=\frac{\prod_{u=1}^{d}\left((p-1)\mu^{\xi^{u}}_{n-1,p,q}[\sigma_{u}=1]+1\right)}{\sum_{i=1}^{q}\prod_{u=1}^{d}\left((p-1)\mu^{\xi^{u}}_{n-1,p,q}[\sigma_{u}=i]+1\right)}.$

A useful technique is to consider the ratio in order to simplify the
expression

(1.10)
$\begin{split}r_{n}(\xi)&:=\frac{\mu^{\xi}_{n,p,q}[\sigma_{*}=2]}{\mu^{\xi}_{n,p,q}[\sigma_{*}=1]}=\prod_{u=1}^{d}\left(\frac{(p-1)\mu^{\xi^{u}}_{n-1,p,q}[\sigma_{u}=2]+1}{(p-1)\mu^{\xi^{u}}_{n-1,p,q}[\sigma_{u}=1]+1}\right),\\\
r^{*}_{n}&:=\max_{\xi}r_{n}(\xi),\end{split}$

and then prove the maximal ratio $r^{*}_{n}$ converges to $1$ at a power law
rate.

Notice that the ratio $r_{n}(\xi)$ depends on the boundary condition, which
changes with respect to $n$ in (1.9). Only for the boundary condition that is
a pure state of one color, the expression can be closed as an iteration. We
call this situation _pure boundary condition_ and we use $\mu^{i}_{n,p,q}$ for
the Gibbs measure with pure boundary condition $\xi\equiv i\in[q]$.
Afterwards, We define a quantity

(1.11) $\displaystyle
r_{n}:=\frac{\mu^{2}_{n,p,q}[\sigma_{*}=2]}{\mu^{2}_{n,p,q}[\sigma_{*}=1]},$

and the sequence $(r_{n})_{n\in\mathbb{N}}$ satisfies an iteration

(1.12) $\displaystyle r_{n+1}=f(r_{n}),\qquad
f(x)=\left(\frac{px+(q-1)}{p+(q-2)+x}\right)^{d}.$

The iteration function $f$ here plays an important role in the analysis of
convergence. By an heuristic asymptotic analysis, we have

(1.13) $\displaystyle
f(x)-1=\left(1+\frac{(1-p)(1-x)}{p+(q-2)+x}\right)^{d}-1\simeq\frac{d(1-p)(1-x)}{p+(q-2)+x}.$

This implies that $x=1$ is a fixed point, and the uniqueness regime
corresponds to the contraction rate less than $1$ near the fixed point that

(1.14) $\displaystyle\frac{d(1-p)}{p+q-1}\leqslant 1\Longleftrightarrow
p\geqslant 1-\frac{q}{d+1}.$

By analysis of the two-step iteration function $(f\circ f)$, we obtain
$r_{2n}\simeq 1+\frac{C}{\sqrt{2n}}$. The critical exponent $\frac{1}{2}$ and
the constant $\frac{d^{2}-1}{6d^{2}}$ in (1.6) are closely related to the
analytical expansion of $(f\circ f)$ near $1$.

The above reasoning gives the critical exponent for the pure boundary
conditions. A natural question to ask, is whether the pure boundary condition
dominates other boundary conditions. This is unfortunately false. For the
ferromagnetic Ising model, it is known that the magnetization is an increasing
function of the boundary condition, thanks to the GKS inequality [11]. For the
ferromagnetic Potts model, the GKS inequality no longer applies, yet a weaker
form of the positive association can be derived via the random cluster
representation with the FKG inequality [12]. Such classical representation and
FKG inequality are in general false for the AF Potts model. Some correlation
inequalities, such as the first Griffith’s inequality, were proved for the AF
Potts model on bipartite graphs [8], based on the Swendsen-Wang-Kotecky
algorithm, but they are not sufficient to deduce the boundary domination.

To explain better the non-existence of boundary condition domination, we give
the following example in Figure 1. It is an AF Potts model with $q=3$ and
$d=3$, then for any $p\in(0,1)$ it is always in the subcritical regime. For
every fixed boundary condition, there are $3^{3}=27$ configurations. The
boundary condition for the example on the left-hand side is the one of pure
boundary condition, but we see that this configuration with $\sigma_{*}=3$
also has no monochromatic edges, which implies that
$\mu^{1}_{2,p,q}[\sigma_{*}=3]=\mu^{1}_{2,p,q}[\sigma_{*}=2]\geqslant\frac{1}{27}$
and $\mu^{1}_{2,p,q}[\sigma_{*}=1]\leqslant\frac{25}{27}$. On the other hand,
the configuration on the right-hand side is the one with so called frozen
boundary $\xi^{\prime}$. If $p=0$, then it is the configuration which charges
all the weight because the other configurations have at least one
monochromatic edge. When $p>0$, we have
$\mu^{\xi^{\prime}}_{2,p,q}[\sigma_{*}=1]\geqslant\frac{1}{1+26p}$, so for $p$
very close to $0$, this probability is larger than
$\mu^{1}_{2,p,q}[\sigma_{*}=1]$. This example can be generalized to any $n$
which justifies that the pure boundary is not the maximiser for the marginal
probability at the root.

Figure 1. The example on the left-hand side is the one with the pure boundary
condition, while the one on the right-hand side is with the frozen boundary.

Despite the lack of boundary condition domination, it is also not clear which
boundary condition realizes $r^{*}_{n}$. Thus, the analysis of
$(r_{n})_{n\in\mathbb{N}}$ above only gives a lower bound of the discrepancy
probability. However, we will prove that

(1.15) $\displaystyle\text{ for all }r^{*}_{n}=1+o(1),\qquad\text{we have
}r^{*}_{n+2}\leqslant(f\circ f)(r^{*}_{n}).$

In another word, when $r^{*}_{n}$ is very close to $1$, its upper bound is
also dominated by the two-step iteration function $(f\circ f)$. Therefore, the
upper bound and lower bound follow the same dynamic iteration near the fixed
point, which implies Theorem 1.2.

Let us add more comments on (1.15) and the iteration. The upper bound
iteration (1.15) here is obtained quite qualitatively, i.e. we do not go
further to give all possible values of $r_{n}^{*}$ such that
$r^{*}_{n+2}\leqslant(f\circ f)(r^{*}_{n})$ holds. That is why we need to
assume Hypothesis 1.1, which guarantees $r_{n}^{*}=1+o(1)$ for large $n$. On
the other hand, we obtained precise contraction rate of the two-step iteration
$(f\circ f)$ and its generalization. Therefore, if we could enlarge the regime
such that (1.15) holds, and show that $r_{n}^{*}$ enters this regime for large
$n$, it will give a unconditional proof for Theorem 1.2.

The rest of the paper is organized as following. In Section 2, we prove the
lower bound of $(r^{*}_{n})_{n\in\mathbb{N}}$ by studying the pure boundary
iterations. In Section 3, we formulate the general two-step iterations, and
justify the asymptotic upper bound (1.15), when $r_{n}^{*}$ lies in a small
neighborhood of $1$. In Section 4, we give a proof of the contraction rate of
the $(f\circ f)$ type maps, thus concluding Theorem 1.2, and is of independent
interest.

### Notations

Throughout the paper, we will use the notation of Dirac function
$\delta_{i}(j)=\delta_{i,j}=\mathbf{1}_{\left\\{i=j\right\\}}$. We also recall
that we use the dictionary notation $\\{1,2,3,\cdots,d\\}^{\mathbb{N}^{+}}$
for the vetrices of the tree, and $|u|$ for the word length. Then for
$u\in\\{1,2,3,\cdots,d\\}^{\mathbb{N}^{+}}$ with $|u|=k$, we use $\xi^{u}$ to
represent the boundary condition of the subtree rooted at $u$, and
$\mu^{\xi^{u}}_{n-k,p,q},W^{\xi^{u}}_{n-k,p,q}$ respectively for its
probability space and the weight function.

##  2\. Lower bound by pure boundary condition

In this section, we prove the lower bound in Theorem 1.2. Our method is to
establish the one-step iteration, which has a closed expression for the pure
boundary condition case, i.e. $r_{n+1}=f(r_{n})$ in Lemma 2.2. Therefore, we
will focus on the iteration function $f$ defined in (1.12).

###  2.1. One-step iteration

In this part, we establish the recurrence called _one-step iteration_.

######  Lemma 2.1.

For any $p\in(0,1)$, integers $d,n\geqslant 1,q\geqslant 2$, we have the
following recurrence for the ratio function

(2.1)
$\displaystyle\frac{\mu^{\xi}_{n,p,q}[\sigma_{*}=2]}{\mu^{\xi}_{n,p,q}[\sigma_{*}=1]}=\prod_{u=1}^{d}\left(\frac{(p-1)\mu^{\xi^{u}}_{n-1,p,q}[\sigma_{u}=2]+1}{(p-1)\mu^{\xi^{u}}_{n-1,p,q}[\sigma_{u}=1]+1}\right).$

Similar recursions are also used in [9, 4], and the proof are almost the same.
However, for completeness we present the proof as follows.

###### Proof.

Using the weight function defined in (1.4)

$\displaystyle
W^{\xi}_{n,p,q}(\sigma_{*}=1)=\prod_{u=1}^{d}\left(W^{\xi^{u}}_{n-1,p,q}(\sigma^{u})p^{\delta_{1}(\sigma_{u})}\right),$

which implies

(2.2)
$\displaystyle\mu^{\xi}_{n,p,q}[\sigma_{*}=1]=\frac{\sum_{\sigma^{1},\cdots,\sigma^{d}}\prod_{u=1}^{d}\left(W^{\xi^{u}}_{n-1,p,q}(\sigma^{u})p^{\delta_{1}(\sigma_{u})}\right)}{\sum_{j=1}^{q}\sum_{\sigma^{1},\cdots,\sigma^{d}}\prod_{u=1}^{d}\left(W^{\xi^{u}}_{n-1,p,q}(\sigma^{u})p^{\delta_{j}(\sigma_{u})}\right)}.$

Then we notice that conditioned on the state of $\sigma_{*}$, the spins on
different subtrees are independent, so we have

(2.3)
$\displaystyle\mu^{\xi}_{n,p,q}[\sigma_{*}=1]=\frac{\prod_{u=1}^{d}\left(\sum_{\sigma^{u}}W^{\xi^{u}}_{n-1,p,q}(\sigma^{u})p^{\delta_{1}(\sigma_{u})}\right)}{\sum_{j=1}^{q}\prod_{u=1}^{d}\left(\sum_{\sigma^{u}}W^{\xi^{u}}_{n-1,p,q}(\sigma^{u})p^{\delta_{j}(\sigma_{u})}\right)}.$

After a normalization by $Z^{\xi^{u}}_{n-1,\beta,q}$, this equation becomes

$\displaystyle\mu^{\xi}_{n,p,q}[\sigma_{*}=1]=\frac{\prod_{u=1}^{d}\left(\sum_{j_{u}\in[q]}\mu^{\xi^{u}}_{n-1,p,q}[\sigma_{u}=j_{u}]p^{\delta_{1}(j_{u})}\right)}{\sum_{i=1}^{q}\prod_{u=1}^{d}\left(\sum_{j_{u}\in[q]}\mu^{\xi^{u}}_{n-1,p,q}[\sigma_{u}=j_{u}]p^{\delta_{i}(j_{u})}\right)},$

and this can be further simplified by

$\displaystyle\sum_{j_{u}\in[q]}\mu^{\xi^{u}}_{n-1,p,q}[\sigma_{u}=j_{u}]p^{\delta_{i}(j_{u})}$
$\displaystyle=p\mu^{\xi^{u}}_{n-1,p,q}[\sigma_{u}=i]+\sum_{j_{u}\in[q]\setminus\\{i\\}}\mu^{\xi^{u}}_{n-1,p,q}[\sigma_{u}=j_{u}]$
$\displaystyle=(p-1)\mu^{\xi^{u}}_{n-1,p,q}[\sigma_{u}=i]+1.$

Therefore, we have

$\displaystyle\mu^{\xi}_{n,p,q}[\sigma_{*}=1]=\frac{\prod_{u=1}^{d}\left((p-1)\mu^{\xi^{u}}_{n-1,p,q}[\sigma_{u}=1]+1\right)}{\sum_{i=1}^{q}\prod_{u=1}^{d}\left((p-1)\mu^{\xi^{u}}_{n-1,p,q}[\sigma_{u}=i]+1\right)}.$

This gives us the desired result. ∎

Generally speaking, the one-step iteration is not a closed formula for
$r_{n}(\xi)$, because as we move to different subtrees, the boundary
conditions $\xi^{u}$ are different from $\xi$. A very special case is the pure
boundary situation, in which we obtain a closed formula.

######  Lemma 2.2.

For any $p\in(0,1)$, integers $d\geqslant 1,q\geqslant 2$ and the pure
boundary condition $\xi\equiv 2$, the ratio function
${r_{n}=\frac{\mu^{2}_{n,p,q}[\sigma_{*}=2]}{\mu^{2}_{n,p,q}[\sigma_{*}=1]}}$
satisfies the iteration $r_{n+1}=f(r_{n})$ with $f$ defined in (1.12).

###### Proof.

When the boundary condition is pure $\xi\equiv 2$, the probability
$\mu^{2}_{n,p,q}[\sigma_{*}=i]$ only takes two values, and we can calculate
that

(2.4)
$\displaystyle\mu^{2}_{n,p,q}[\sigma_{*}=2]=\frac{r_{n}}{r_{n}+q-1},\qquad\mu^{2}_{n,p,q}[\sigma_{*}=1]=\frac{1}{r_{n}+q-1}.$

We put them back to (2.1) and obtain the iteration function $f$. ∎

###  2.2. Convergence rate for the pure boundary condition

The main result in this part is the following convergence rate in the special
case of pure boundary condition.

######  Proposition 2.3.

For the critical case $p_{c}=1-\frac{q}{d+1}>0$, the convergence rate for the
pure boundary condition is that

(2.5)
$\displaystyle\lim_{n\to\infty}\frac{1}{n}\left(\left|\mu^{1}_{n,p_{c},q}[\sigma_{*}=1]-\frac{1}{q}\right|\right)^{-2}=\frac{d^{2}-1}{6d^{2}}\left(\frac{q^{2}}{q-1}\right)^{2}.$

We remark that for the pure boundary condition, the convergence of the ratio
$\lim_{n\to\infty}r_{n}=1$ follows directly from explicit computations in
Proposition 4.1 and Corollary 4.5. Therefore the proposition above does not
require assuming Hypothesis 1.1.

The following elementary properties about $f$ are useful.

######  Lemma 2.4 (Elementary properties of $f$).

For $p\in[1-\frac{q}{d+1},1)\cap(0,1)$, the following properties hold for $f$
defined in (1.12).

  1. (1)

Range: $f(x)\geqslant 1$ for all $x\in[0,1]$; $f(x)\in(0,1]$ for all
$x\geqslant 1$.

  2. (2)

Fixed point: $f(x)=x$ admits a unique solution on $\mathbb{R}^{+}$ that $x=1$.

  3. (3)

Monotonicity: $f$ is decreasing.

  4. (4)

Contraction on one side: for every $x\geqslant 1$, $1-f(x)\leqslant x-1$.

###### Proof.

Property (1) can be deduced directly from the expression of $f$ and the fixed
point is a corollary. To study the monotonicity of $f$, we look at its
derivative

(2.6) $\displaystyle
f^{\prime}(x)=\left(\frac{px+(q-1)}{p+(q-2)+x}\right)^{d-1}\frac{d(p-1)(p+q-1)}{(p+(q-2)+x)^{2}}\leqslant
0,$

because we have $p<1$. For the contraction on one side, it suffices to study
${F(x)=f(x)+x-2}$ and we know that $F(1)=0$. Thus we look at its derivative.
It is clear that

(2.7) $\displaystyle\forall x\geqslant 1,\qquad
F^{\prime}(x)=f^{\prime}(x)+1\geqslant 0,$

which can be deduced directly from (2.6). ∎

A direct corollary from Lemma 2.4 is that $r_{2k}\geqslant 1$ while
$r_{2k+1}\leqslant 1$ for all $k\in\mathbb{N}$, so the ratio converges to the
fixed point from two sides. This suggests us to use the two-step iteration
$(f\circ f)$ to study the convergence rate for even terms and odd terms
separately.

###### Proof of Proposition 2.3.

Throughout the proof we admit $\lim_{n\to\infty}r_{n}=1$, which will be proved
in Corollary 4.5. We divide the proof into three steps.

_Step 1: identification of the critical exponent._ We explain at first the
intuition to find the critical exponent. Suppose that $r_{2k}\simeq
1+(Ck)^{-\frac{1}{\alpha}}$, then we should have

$\displaystyle(r_{2k}-1)^{-\alpha}\simeq Ck,$

which implies

$\displaystyle(r_{2k+2}-1)^{-\alpha}-(r_{2k}-1)^{-\alpha}\simeq C.$

Thus, the problem can be reduced to find an exponent $\alpha>0$ and a non-
trivial constant $C>0$ in order to see the power law behavior

(2.8) $\displaystyle\lim_{x\searrow 1}((f\circ
f)(x)-1)^{-\alpha}-(x-1)^{-\alpha}=C.$

Since $f$ is analytic, we do the Taylor expansion for $(f\circ f)$ around $1$
that

(2.9) $\displaystyle(f\circ
f)(x)-1=\sum_{m=1}^{\infty}\frac{c_{m}}{m!}(x-1)^{m},\qquad
c_{m}=\frac{{\mathrm{d}}^{m}}{{\mathrm{d}}x^{m}}_{|_{x=1}}(f\circ f)(x).$

At the critical phase, one can calculate several terms using (2.6) and the
chain rule that

$\displaystyle c_{1}=(f\circ f)^{\prime}(1)=1,\qquad$ $\displaystyle
c_{2}=(f\circ f)^{\prime\prime}(1)=0,\qquad c_{3}=(f\circ
f)^{\prime\prime\prime}(1)=-\frac{(d^{2}-1)}{d^{2}}.$

We explain more details. For $c_{1}$ and $c_{2}$, we only need to use the fact
$f(1)=1$ and $f^{\prime}(1)=-1$ by (1.12), (2.6) and $p_{c}=1-\frac{q}{d+1}$.
Then by the chain rule

$\displaystyle(f\circ f)^{\prime}(1)$
$\displaystyle=f^{\prime}(f(1))f^{\prime}(1)=1,$ $\displaystyle(f\circ
f)^{\prime\prime}(1)$
$\displaystyle=f^{\prime\prime}(1)(f^{\prime}(1))^{2}+f^{\prime}(1)f^{\prime\prime}(1)=0.$

Notice that $c_{2}$ is null, and since we assume $d\geqslant 2$, the term
$c_{3}$ does not vanish. These terms will play an important role in the
following calculation.

We put the analytic expansion back in (2.8) with a change of variable $y:=x-1$

$\displaystyle\lim_{x\searrow 1}((f\circ
f)(x)-1)^{-\alpha}-(x-1)^{-\alpha}=\lim_{y\searrow
0}\frac{y^{\alpha}-(y+\frac{c_{3}}{6}y^{3}+o(y^{3}))^{\alpha}}{y^{\alpha}(y+\frac{c_{3}}{6}y^{3}+o(y^{3}))^{\alpha}}.$

Here we use the notation $o(1)$ for $\lim_{y\to 0}o(1)=0$. Then we observe
that the numerator is of leading order $y^{2+\alpha}$

$\displaystyle
y^{\alpha}-\left(y+\frac{c_{3}}{6}y^{3}+o(y^{3})\right)^{\alpha}=y^{\alpha}-y^{\alpha}\left(1+\frac{c_{3}}{6}y^{2}+o(y^{2})\right)^{\alpha}=-\frac{\alpha
c_{3}}{6}y^{2+\alpha}+o(y^{2+\alpha}),$

while the denominator is of leading order $y^{2\alpha}$. Therefore, $\alpha=2$
is the only possible candidate to realize a non-trivial limit

(2.10) $\begin{split}\lim_{x\searrow 1}((f\circ
f)(x)-1)^{-2}-(x-1)^{-2}&=\lim_{y\searrow
0}\frac{y^{2}-(y+\frac{c_{3}}{6}y^{3}+o(y^{3}))^{2}}{y^{2}(y+\frac{c_{3}}{6}y^{3}+o(y^{3}))^{2}}\\\
&=\lim_{y\searrow
0}\frac{-\frac{c_{3}}{3}y^{4}+o(y^{4}))}{(y^{4}+\frac{c_{3}}{3}y^{6}+o(y^{6}))}\\\
&=-\frac{c_{3}}{3}.\end{split}$

_Step 2: convergence rate of $(r_{n})_{n\in\mathbb{N}}$._ By Proposition 4.1,
we have $\lim_{k\to\infty}r_{2k}=1$ and then use the telescope formula to
obtain that

$\displaystyle\lim_{n\to\infty}\frac{1}{2n+2}(r_{2n+2}-1)^{-2}$
$\displaystyle=\lim_{n\to\infty}\frac{1}{2n+2}\left(\sum_{k=1}^{n}\left((r_{2k+2}-1)^{-2}-(r_{2k}-1)^{-2}\right)\right)$
$\displaystyle=\lim_{k\to\infty}\frac{1}{2}\left((r_{2k+2}-1)^{-2}-(r_{2k}-1)^{-2}\right)$
$\displaystyle=-\frac{c_{3}}{6}=\frac{d^{2}-1}{6d^{2}}.$

From the first line to the second line, we use a classical exercise that the
limit of average coincides with the limit of sequence. This gives us the ratio
convergence rate for the even terms.

We then treat the odd terms with the mean value theorem: there exists
$z_{2k}\in(1,r_{2k})$ such that

$\displaystyle r_{2k+1}-1=f(r_{2k})-f(1)=f^{\prime}(z_{2k})(r_{2k}-1),$

and $\lim_{k\to\infty}z_{2k}=1$ by squeeze theorem. This implies
$\lim_{k\to\infty}f^{\prime}(z_{2k})=-1$ and thus we establish that

(2.11)
$\displaystyle\lim_{n\to\infty}\frac{1}{n}|r_{n}-1|^{-2}=\frac{d^{2}-1}{6d^{2}}.$

_Step 3: convergence rate of probability._ We now turn to the proof of (2.5).
We make use of the formula (2.4), Step 2 (which gives $r_{n}\to 1$) and (2.11)

$\displaystyle\lim_{n\to\infty}\frac{1}{n}\left(\left|\mu^{2}_{n,p_{c},q}[\sigma_{*}=2]-\frac{1}{q}\right|\right)^{-2}$
$\displaystyle=\lim_{n\to\infty}\frac{1}{n}\left(\left|\frac{r_{n}}{r_{n}+q-1}-\frac{1}{q}\right|\right)^{-2}$
$\displaystyle=\lim_{n\to\infty}\frac{1}{n}\left(\left|\frac{(q-1)|r_{n}-1|}{q(r_{n}+q-1)}\right|\right)^{-2}$
$\displaystyle=\left(\frac{q^{2}}{q-1}\right)^{2}\lim_{n\to\infty}\frac{1}{n}|r_{n}-1|^{-2}$
$\displaystyle=\frac{d^{2}-1}{6d^{2}}\left(\frac{q^{2}}{q-1}\right)^{2}.$

This is the desired result. ∎

##  3\. Upper bound by expansion near fixed point

The pure boundary condition analyzed in the previous section is only a very
special case. In this section we show that for evey boundary condition, the
iteration function $(f\circ f)$, where $f$ is defined in (1.12) captures the
rate of convergence near the fixed point. The main result of this section is
the following proposition.

######  Proposition 3.1.

For any integers $d,n\geqslant 1,q\geqslant 2$ and
$p\in[1-\frac{q}{d+1},1)\cap(0,1)$, there exists a constant
$\varepsilon(d,q,p)\in(0,\infty)$, such that for every
$r^{*}_{n}\in[1,1+\varepsilon)$, we have that ${r^{*}_{n+2}\leqslant(f\circ
f)(r^{*}_{n})}$.

###  3.1. Two-step iteration

We may obtain a two-step iteration by applying Lemma 2.1 twice. However, two
step iteration in the general boundary condition is much more complicated than
the one studied in the last section, so we will make a reduction to the
extremal boundary conditions, in the sense of the next proposition.

######  Proposition 3.2.

For any integers $d,n\geqslant 1,q\geqslant 2$ and
$p\in[1-\frac{q}{d+1},1)\cap(0,1)$, the ratio function satisfies the following
bound for the two-step iteration

(3.1) $\displaystyle
r^{*}_{n+2}\leqslant\max_{\mathcal{A}(r^{*}_{n})}h(\mathbf{x}).$

Here $\mathbf{x}=\\{x^{u}_{k}\\}_{u\in[d],k\in[q]}$ represents a vector, and
$h$ is a function defined as

(3.2) $\begin{split}h(\mathbf{x}):=U^{d},&\qquad
U:=\frac{\sum_{j=1}^{q}V_{j}p^{\delta_{2}(j)}}{\sum_{j=1}^{q}V_{j}p^{\delta_{1}(j)}},\\\
V_{j}:=\prod_{u=1}^{d}V^{u}_{j},&\qquad
V^{u}_{j}:=\frac{\sum_{k=1}^{q}x^{u}_{k}p^{\delta_{j}(k)}}{\sum_{k=1}^{q}x^{u}_{k}p^{\delta_{1}(k)}},\end{split}$

and $\mathcal{A}(r)$ as a reduced admissible domain for $r\geqslant 1$

(3.3) $\displaystyle\mathcal{A}(r):=\Bigg{\\{}\mathbf{x}:x^{u}_{1}=1\text{ and
}x^{u}_{k}\in\\{1,r\\},\forall k\in[q]\setminus\\{1\\},\text{ and }\forall
u\in[d]\Bigg{\\}}.$

This proposition has already been shown in [9, Lemma 2.6]. We reformulate its
proof here for the self-completeness of the paper.

###### Proof of Proposition 3.2.

_Step 1: general two-step iteration formula._ Using the recurrence (2.3)
formula, we have

$\displaystyle r_{n+2}(\xi)$
$\displaystyle=\frac{W^{\xi}_{n+2,p,q}(\sigma_{*}=2)}{W^{\xi}_{n+2,p,q}(\sigma_{*}=1)}$
$\displaystyle=\prod_{v=1}^{d}\left(\frac{\sum_{j=1}^{q}W^{\xi^{v}}_{n+1,p,q}(\sigma_{v}=j)p^{\delta_{2}(j)}}{\sum_{j=1}^{q}W^{\xi^{v}}_{n+1,p,q}(\sigma_{v}=j)p^{\delta_{1}(j)}}\right)$
$\displaystyle=\prod_{v=1}^{d}\left(\frac{\sum_{j=1}^{q}W^{\xi^{v}}_{n+1,p,q}(\sigma_{v}=j)/W^{\xi^{v}}_{n+1,p,q}(\sigma_{v}=1)p^{\delta_{2}(j)}}{\sum_{j=1}^{q}W^{\xi^{v}}_{n+1,p,q}(\sigma_{v}=j)/W^{\xi^{v}}_{n+1,p,q}(\sigma_{v}=1)p^{\delta_{1}(j)}}\right).$

We can apply once again the formula (2.3) for
$W^{\xi^{v}}_{n+1,p,q}(\sigma_{v}=j)/W^{\xi^{v}}_{n+1,p,q}(\sigma_{v}=1)$ in
order to get the general two-step iteration. We define a function $\hat{h}$

(3.4)
$\begin{split}\hat{h}(\\{\hat{x}^{vu}_{k}\\}_{u,v\in[d],k\in[q]}):=\prod_{v=1}^{d}\hat{U}^{v},&\qquad\hat{U}^{v}:=\frac{\sum_{j=1}^{q}\hat{V}^{v}_{j}p^{\delta_{2}(j)}}{\sum_{j=1}^{q}\hat{V}^{v}_{j}p^{\delta_{1}(j)}},\\\
\hat{V}^{v}_{j}:=\prod_{u=1}^{d}\hat{V}^{vu}_{j},&\qquad\hat{V}^{vu}_{j}:=\frac{\sum_{k=1}^{q}\hat{x}^{vu}_{k}p^{\delta_{j}(k)}}{\sum_{k=1}^{q}\hat{x}^{vu}_{k}p^{\delta_{1}(k)}},\end{split}$

and then by identifying that

(3.5)
$\begin{split}{\hat{U}^{v}=\frac{\sum_{j=1}^{q}W^{\xi^{v}}_{n+1,p,q}(\sigma_{v}=j)p^{\delta_{2}(j)}}{\sum_{j=1}^{q}W^{\xi^{v}}_{n+1,p,q}(\sigma_{v}=j)p^{\delta_{1}(j)}}},\qquad&\hat{V}^{v}_{j}=\frac{W^{\xi^{v}}_{n+1,p,q}(\sigma_{v}=j)}{W^{\xi^{v}}_{n+1,p,q}(\sigma_{v}=1)},\\\
{\hat{V}^{vu}_{j}=\frac{\sum_{k=1}^{q}W^{\xi^{vu}}_{n,p,q}(\sigma_{vu}=k)p^{\delta_{j}(k)}}{\sum_{k=1}^{q}W^{\xi^{vu}}_{n,p,q}(\sigma_{vu}=k)p^{\delta_{1}(k)}}},\qquad&\hat{x}^{vu}_{k}=\frac{W^{\xi^{vu}}_{n,p,q}(\sigma_{vu}=k)}{W^{\xi^{vu}}_{n,p,q}(\sigma_{vu}=1)},\end{split}$

we obtain that

(3.6) $\displaystyle
r_{n+2}(\xi)=\hat{h}\left(\left\\{\frac{W^{\xi^{vu}}_{n,p,q}(\sigma_{vu}=k)}{W^{\xi^{vu}}_{n,p,q}(\sigma_{vu}=1)}\right\\}_{u,v\in[d],k\in[q]}\right).$

The expression of $\hat{h}$ is quite close to that of $h$ defined in (3.2). In
the following steps, we see how to transform $\hat{h}$ to $h$ and restrict to
the admissible domain.

_Step 2: characterizations of $\max_{\xi}r_{n+2}(\xi)$._ In this part, we give
some characterizations of the boundary condition that realizes
$\max_{\xi}r_{n+2}(\xi)$. These characterizations are not sufficient to
identify the maximiser, but may reduce the maximiser to the admissible domain
(3.3). We focus on at first $\hat{U}^{v}$ in (3.4) and (3.5) that

(3.7)
$\displaystyle\hat{U}^{v}=\frac{\sum_{j=1}^{q}W^{\xi^{v}}_{n+1,p,q}(\sigma_{v}=j)+(p-1)W^{\xi^{v}}_{n+1,p,q}(\sigma_{v}=2)}{\sum_{j=1}^{q}W^{\xi^{v}}_{n+1,p,q}(\sigma_{v}=j)+(p-1)W^{\xi^{v}}_{n+1,p,q}(\sigma_{v}=1)}.$

As we are interested in the $\max_{\xi}r_{n+2}(\xi)$, without loss of
generality, we can suppose that for the maximiser of $\max_{\xi}r_{n+2}(\xi)$

(3.8)
$\mathbf{E_{1}}:=\left\\{\xi:\partial\mathbb{T}^{d}_{n+2}\to[q]\,\Big{|}\,\forall
v\in[d],\quad
W^{\xi^{v}}_{n+1,p,q}(\sigma_{v}=1)=\max_{j\in[q]}W^{\xi^{v}}_{n+1,p,q}(\sigma_{v}=j),\right.\\\
\left.W^{\xi^{v}}_{n+1,p,q}(\sigma_{v}=2)=\min_{j\in[q]}W^{\xi^{v}}_{n+1,p,q}(\sigma_{v}=j)\right\\}.$

Otherwise, for example suppose that $j\in[q]\setminus\\{1\\}$ is the color to
achieve the maximum, one can exchange the color between $j$ and $1$ in
$\xi^{v}$. Then the value $W^{\xi^{v}}_{n+1,p,q}(\sigma_{v}=1)$ and
$W^{\xi^{v}}_{n+1,p,q}(\sigma_{v}=j)$ exchange, and $\hat{U}^{v}$ becomes
larger.

We now go one step further and claim that for the maximiser of
$\max_{\xi}r_{n+2}(\xi)$

(3.9)
$\displaystyle\mathbf{E_{2}}:=\left\\{\xi:\partial\mathbb{T}^{d}_{n+2}\to[q]\,\Big{|}\,\forall
v,u\in[d],\quad
W^{\xi^{vu}}_{n,p,q}(\sigma_{vu}=1)=\min_{k\in[q]}W^{\xi^{vu}}_{n,p,q}(\sigma_{vu}=k)\right\\}.$

The argument is as follows. Suppose that it is not true, then there exist
$v,u\in[d]$ and $k\in[q]\setminus\\{1\\}$, such that
$W^{\xi^{vu}}_{n,p,q}(\sigma_{vu}=k)$ achieves the minimum weight on the
subtree indexed by $vu$. Then by a similar formula as (3.7)

(3.10)
$\displaystyle\hat{V}^{vu}_{j}=\frac{\sum_{k=1}^{q}W^{\xi^{vu}}_{n,p,q}(\sigma_{vu}=k)+(p-1)W^{\xi^{vu}}_{n,p,q}(\sigma_{vu}=2)}{\sum_{k=1}^{q}W^{\xi^{vu}}_{n,p,q}(\sigma_{vu}=k)+(p-1)W^{\xi^{vu}}_{n,p,q}(\sigma_{vu}=1)},$

switching the color between $k$ and $1$ on the boundary condition $\xi^{vu}$
will decrease the value of $\hat{V}^{vu}_{j}$ for $j\in[q]\setminus\\{1\\}$,
so as that of $\hat{V}^{v}_{j}$. Viewing the definition of $\hat{V}^{v}_{j}$
in (3.5), the condition (3.8) implies that

(3.11) $\begin{split}\forall v\in[d],j\in[q],\quad\hat{V}^{v}_{j}\leqslant
1=\hat{V}^{v}_{1}.\end{split}$

We then develop $\hat{U}^{v}$ in function of $\hat{V}^{v}_{j}$ like in (3.2)

$\displaystyle\hat{U}^{v}=1+\frac{(1-p)(\hat{V}^{v}_{1}-\hat{V}^{v}_{2})}{\sum_{j=1}^{q}\hat{V}^{v}_{j}+(p-1)\hat{V}^{v}_{1}}.$

Then the decrement of $\hat{V}^{v}_{j}$ for $j\in[q]\setminus\\{1\\}$ implies
the increment of $\hat{U}^{v}$.

We now propose a third characterization for the maximiser of
$\max_{\xi}r_{n+2}(\xi)$

(3.12)
$\displaystyle\mathbf{E_{3}}:=\left\\{\xi:\partial\mathbb{T}^{d}_{n+2}\to[q]\,\Big{|}\quad\forall
v_{1},v_{2}\in[d],\quad\xi^{v_{1}}=\xi^{v_{2}}\right\\}.$

That is to say, the boundary condition for the maximiser is periodic. This
comes from the AM–GM inequality,

$\displaystyle\hat{h}\left(\left\\{\frac{W^{\xi^{vu}}_{n,p,q}(\sigma_{vu}=k)}{W^{\xi^{vu}}_{n,p,q}(\sigma_{vu}=1)}\right\\}_{u,v\in[d],k\in[q]}\right)=\prod_{v=1}^{d}\hat{U}^{v}\leqslant\frac{1}{d}\sum_{v=1}^{d}(\hat{U}^{v})^{d}.$

Moreover, the upper bound on right-hand side is realizable: for a given
boundary condition $\xi$, it suffice to take the boundary condition $\xi^{v}$
of subtrees to maximize $(\hat{U}^{v})^{d}$, and then copy it to other
subtrees. Combining (3.8), (3.9), (3.12), we obtain that

(3.13) $\displaystyle
r^{*}_{n+2}=\max_{\xi\in\mathbf{E_{1}}\cap\mathbf{E_{2}}\cap\mathbf{E_{3}}}\hat{h}\left(\left\\{\frac{W^{\xi^{vu}}_{n,p,q}(\sigma_{vu}=k)}{W^{\xi^{vu}}_{n,p,q}(\sigma_{vu}=1)}\right\\}_{u,v\in[d],k\in[q]}\right).$

_Step 3: reduction of $\hat{h}$._ Then the expression of $\hat{h}$ becomes
that of $h$ once we skip the index of $v$, and then use (3.13), (3.5) to give
an upper bound

(3.14) $\displaystyle r^{*}_{n+2}\leqslant\max_{\forall
u\in[d],k\in[q],1\leqslant x^{u}_{k}\leqslant
r^{*}_{n},x^{u}_{1}=1}h(\mathbf{x}).$

Moreover, fixing the other variables, the function $x^{u}_{k}\mapsto
h(\mathbf{x})$ is of type $\frac{ax^{u}_{k}+b}{cx^{u}_{k}+d}$ with
$a,b,c,d\in\mathbb{R}$. For this mapping, the extreme value is attained at the
endpoint of the interval. Therefore, we obtain the desired result (3.1). ∎

###  3.2. Expansion of the two-step iteration near the fixed point

In this part, we study the property of the function $h(\mathbf{x})$ defined in
(3.2). Although the optimization problem
$\max_{\mathbf{x}\in\mathcal{A}(r)}h(\mathbf{x})$ is quite difficult for a
general $r$, its behavior near the fixed point $1$ is closely related to the
function $f$ defined in (1.12).

######  Proposition 3.3.

For any integers $d,n\geqslant 1,q\geqslant 2$ and
$p\in[1-\frac{q}{d+1},1)\cap(0,1)$, there exists a constant
$\varepsilon(d,q,p)\in(0,\infty)$, such that for any $r\in(1,1+\varepsilon)$,
we have

$\displaystyle\max_{\mathbf{x}\in\mathcal{A}(r)}h(\mathbf{x})=(f\circ f)(r).$

Moreover, the maximiser is attained when $x^{u}_{k}=1+(r-1)\delta_{k,2}$ for
all $u\in[d]$.

###### Proof.

Throughout the proof, for $\mathbf{x}\in\mathcal{A}(r)$, we set

$\displaystyle
x^{u}_{k}=1+(r-1)\theta^{u}_{k},\qquad\theta^{u}_{k}\in\\{0,1\\},$

with $\theta^{u}_{k}$ to be fixed later. Then the function $h(\mathbf{x})$ can
be seen as a function with respect to $r$. By the Taylor formula, for
$x\in\mathcal{A}(r)$ and $r$ close to $1$

$\displaystyle h(\mathbf{x})=1+\frac{\partial h}{\partial
r}(\mathbf{1})(r-1)+O((r-1)^{2}).$

Here $\mathbf{x}=\mathbf{1}$ means that for all $u\in[d],k\in[q],x^{u}_{k}=1$.
Since the first order dominates, the maximiser should attain the largest
possible $\frac{\partial h}{\partial r}(\mathbf{1})$. We calculate the
derivative at first using the chain rule:

$\displaystyle\frac{\partial h}{\partial r}$
$\displaystyle=\sum_{u=1}^{d}\sum_{j,k=2}^{q}d(U)^{d-1}\frac{\partial
U}{\partial V_{j}}\frac{\partial V_{j}}{\partial x^{u}_{k}}\frac{\partial
x^{u}_{k}}{\partial r}$
$\displaystyle=\sum_{u=1}^{d}\sum_{j,k=2}^{q}d(U)^{d-1}\frac{\partial
U}{\partial V_{j}}\frac{\partial V_{j}}{\partial x^{u}_{k}}\theta^{u}_{k}.$

The derivative at fixed point $\mathbf{x}=\mathbf{1}$ is

$\displaystyle\frac{\partial U}{\partial
V_{j}}(\mathbf{1})=-d^{-1}(A/B)\delta_{2,j},\qquad\frac{\partial
V_{j}}{\partial x^{u}_{k}}(\mathbf{1})=-d^{-1}(A/B)\delta_{j,k},$

where we use the following notation for the simplification

(3.15) $\displaystyle A:=d(1-p),\qquad B:=p+q-1,$

and the condition $p\in[1-\frac{q}{d+1},1)\cap(0,1)$ implies that

(3.16) $\displaystyle A\leqslant B.$

Therefore, we have

$\displaystyle\frac{\partial h}{\partial r}(\mathbf{1})$
$\displaystyle=d^{-2}(A/B)^{2}\sum_{u=1}^{d}\sum_{j,k=2}^{q}\theta^{u}_{k}\delta_{2,j}\delta_{j,k}$
$\displaystyle=d^{-2}(A/B)^{2}\sum_{u=1}^{d}\sum_{k=2}^{q}\theta^{u}_{k}\delta_{2,k}$
$\displaystyle\leqslant d^{-1}(A/B)^{2}.$

The equality is attained when $\theta^{u}_{2}=1$ for all $u\in[d]$. This
implies that for all $u\in[d]$, $x^{u}_{2}=r$.

For other variables, we need more information, so we calculate the second
derivative. Similarly, we have

$\displaystyle h(\mathbf{x})=1+\frac{\partial h}{\partial
r}(\mathbf{1})(r-1)+\frac{1}{2}\frac{\partial^{2}h}{\partial
r^{2}}(\mathbf{1})(r-1)^{2}+O((r-1)^{3}),$

and the maximiser also needs to maximize the second derivative. We calculate
it

$\displaystyle\frac{\partial^{2}h}{\partial
r^{2}}=\sum_{u_{1},u_{2}=1}^{d}\sum_{k_{1},k_{2}=2}^{q}\frac{\partial^{2}h}{\partial
x^{u_{1}}_{k_{1}}\partial
x^{u_{2}}_{k_{2}}}\theta^{u_{1}}_{k_{1}}\theta^{u_{2}}_{k_{2}}.$

The derivative $\frac{\partial^{2}h}{\partial x^{u_{1}}_{k_{1}}\partial
x^{u_{2}}_{k_{2}}}$ is

$\displaystyle\frac{\partial^{2}h}{\partial x^{u_{1}}_{k_{1}}\partial
x^{u_{2}}_{k_{2}}}$ $\displaystyle=\mathbf{I}+\mathbf{II}+\mathbf{III},$
$\displaystyle\mathbf{I}$
$\displaystyle=d(d-1)(U)^{d-2}\sum_{j_{1},j_{2}=2}^{q}\left(\frac{\partial
U}{\partial V_{j_{1}}}\right)\left(\frac{\partial U}{\partial
V_{j_{2}}}\right)\left(\frac{\partial V_{j_{1}}}{\partial
x^{u_{1}}_{k_{1}}}\right)\left(\frac{\partial V_{j_{2}}}{\partial
x^{u_{2}}_{k_{2}}}\right),$ $\displaystyle\mathbf{II}$
$\displaystyle=d(U)^{d-1}\sum_{j_{1},j_{2}=2}^{q}\left(\frac{\partial^{2}U}{\partial
V_{j_{1}}\partial V_{j_{2}}}\right)\left(\frac{\partial V_{j_{1}}}{\partial
x^{u_{1}}_{k_{1}}}\right)\left(\frac{\partial V_{j_{2}}}{\partial
x^{u_{2}}_{k_{2}}}\right),$ $\displaystyle\mathbf{III}$
$\displaystyle=d(U)^{d-1}\sum_{j=2}^{q}\left(\frac{\partial U}{\partial
V_{j}}\right)\left(\frac{\partial^{2}V_{j}}{\partial x^{u_{1}}_{k_{1}}\partial
x^{u_{2}}_{k_{2}}}\right).$

Notice that

$\displaystyle\frac{\partial^{2}U}{\partial V_{j_{1}}\partial
V_{j_{2}}}(\mathbf{1})$
$\displaystyle=d^{-1}B^{-1}(A/B)(\delta_{2,j_{1}}+\delta_{2,j_{2}}),$
$\displaystyle\frac{\partial^{2}V_{j}}{\partial x^{u_{1}}_{k_{1}}\partial
x^{u_{2}}_{k_{2}}}(\mathbf{1})$
$\displaystyle=\left\\{\begin{array}[]{cc}d^{-1}B^{-1}(A/B)(\delta_{j,k_{1}}+\delta_{j,k_{2}})&u_{1}=u_{2},\\\
d^{-2}(A/B)^{2}\delta_{j,k_{1}}\delta_{j,k_{2}}&u_{1}\neq
u_{2}.\end{array}\right.$

We put these back to the three terms $\mathbf{I},\mathbf{II}$ and
$\mathbf{III}$ and obtain that

$\displaystyle\mathbf{I}(\mathbf{1})$
$\displaystyle=d^{-2}(1-d^{-1})(A/B)^{4}\delta_{2,k_{1}}\delta_{2,k_{2}},$
$\displaystyle\mathbf{II}(\mathbf{1})$
$\displaystyle=d^{-2}B^{-1}(A/B)^{3}(\delta_{2,k_{1}}+\delta_{2,k_{2}}),$
$\displaystyle\mathbf{III}(\mathbf{1})$
$\displaystyle=\left\\{\begin{array}[]{cc}-2d^{-1}B^{-1}(A/B)^{2}&u_{1}=u_{2},\\\
-d^{-2}(A/B)^{3}\delta_{2,k_{1}}\delta_{2,k_{2}}&u_{1}\neq
u_{2}.\end{array}\right.$

We do a sum and this gives us

(3.17) $\begin{split}&\frac{\partial^{2}h}{\partial r^{2}}(\mathbf{1})\\\
&=\left(\sum_{u_{1},u_{2}=1}^{d}\theta^{u_{1}}_{2}\theta^{u_{2}}_{2}\bigg{(}d^{-2}(1-d^{-1})(A/B)^{4}-d^{-2}(A/B)^{3}(1-\delta_{u_{1},u_{2}})\bigg{)}\right)\\\
&\quad+\left(2d^{-2}B^{-1}(A/B)^{3}\sum_{u_{1},u_{2}=1}^{d}\theta^{u_{1}}_{2}\left(\sum_{k=2}^{q}\theta^{u_{2}}_{k}\right)-2d^{-1}B^{-1}(A/B)^{2}\sum_{u_{2}=1}^{d}\left(\sum_{k=2}^{q}\theta^{u_{2}}_{k}\right)^{2}\right).\end{split}$

Notice that the maximiser satisfies that $\theta^{u}_{2}=1$ for all $u\in[d]$,
the second line of (3.17) is

(3.18)
$\sum_{u_{1},u_{2}=1}^{d}\theta^{u_{1}}_{2}\theta^{u_{2}}_{2}\bigg{(}d^{-2}(1-d^{-1})(A/B)^{4}-d^{-2}(A/B)^{3}(1-\delta_{u_{1},u_{2}})\bigg{)}\\\
=(1-d^{-1})(A/B)^{4}-(1-d^{-1})(A/B)^{3},$

which is constant. For the third line of (3.17), we also use this property to
replace $\theta^{u_{1}}_{2}=1$ in it

$\displaystyle
2d^{-2}B^{-1}(A/B)^{3}\sum_{u_{1},u_{2}=1}^{d}\theta^{u_{1}}_{2}\left(\sum_{k=2}^{q}\theta^{u_{2}}_{k}\right)-2d^{-1}B^{-1}(A/B)^{2}\sum_{u_{2}=1}^{d}\left(\sum_{k=2}^{q}\theta^{u_{2}}_{k}\right)^{2}$
$\displaystyle=2d^{-2}B^{-1}(A/B)^{3}\sum_{u_{1},u_{2}=1}^{d}\left(\sum_{k=2}^{q}\theta^{u_{2}}_{k}\right)-2d^{-1}B^{-1}(A/B)^{2}\sum_{u_{2}=1}^{d}\left(\sum_{k=2}^{q}\theta^{u_{2}}_{k}\right)^{2}$
$\displaystyle=2d^{-1}B^{-1}(A/B)^{2}\sum_{u=1}^{d}\left((A/B)\left(\sum_{k=2}^{q}\theta^{u}_{k}\right)-\left(\sum_{k=2}^{q}\theta^{u}_{k}\right)^{2}\right).$

Notice that $A\leqslant B$ and
$\sum_{k=2}^{q}\theta^{u}_{k}\geqslant\theta^{u}_{2}=1$, the the quadratic
function

$\displaystyle\left(\sum_{k=2}^{q}\theta^{u}_{k}\right)\mapsto(A/B)\left(\sum_{k=2}^{q}\theta^{u}_{k}\right)-\left(\sum_{k=2}^{q}\theta^{u}_{k}\right)^{2},$

is decreasing with respect to $\left(\sum_{k=2}^{q}\theta^{u}_{k}\right)$.
Therefore, the maximum is attained when $\theta^{u}_{k}=0$ for
$k\in[d]\setminus\\{2\\}$ and all $u\in[d]$, i.e. $x^{u}_{k}=1$ for
$k\in[d]\setminus\\{2\\}$ and all $u\in[d]$. This is the desired result. ∎

###  3.3. Proof of Theorem 1.2

With the discussions above, we can now prove our main theorem.

###### Proof of Proposition 3.1.

Proposition 3.1 follows directly from Proposition 3.2 and Proposition 3.3. ∎

###### Proof of Theorem 1.2.

Using (2.10) and Proposition 3.1, we have

$\displaystyle\lim_{n\to\infty}\left((r^{*}_{n+2}-1)^{-2}-(r^{*}_{n}-1)^{-2}\right)\geqslant\lim_{n\to\infty}\left(((f\circ
f)(r^{*}_{n})-1)^{-2}-(r^{*}_{n}-1)^{-2}\right)=\frac{d^{2}-1}{3d^{2}}.$

Then we obtain an estimate

$\displaystyle\liminf_{n\to\infty}\frac{1}{2n+2}(r^{*}_{2n+2}-1)^{-2}$
$\displaystyle=\liminf_{n\to\infty}\frac{1}{2n+2}\left(\sum_{k=1}^{n}\left((r^{*}_{2k+2}-1)^{-2}-(r^{*}_{2k}-1)^{-2}\right)\right)$
$\displaystyle\geqslant\lim_{k\to\infty}\frac{1}{2}\left((r^{*}_{2k+2}-1)^{-2}-(r^{*}_{2k}-1)^{-2}\right)$
$\displaystyle=\frac{d^{2}-1}{6d^{2}}.$

Similar estimate also works for the odd terms, which implies that

(3.19)
$\displaystyle\liminf_{n\to\infty}\frac{1}{n}(r^{*}_{n}-1)^{-2}\geqslant\frac{d^{2}-1}{6d^{2}}.$

This estimate can also be integrated to that of probability. An easy
comparison gives us

$(q-1)(r^{*}_{n})^{-1}\max_{\xi}\mu^{\xi}_{n,p_{c},q}[\sigma_{*}=1]+\max_{\xi}\mu^{\xi}_{n,p_{c},q}[\sigma_{*}=1]\leqslant
1\\\
\leqslant(q-1)(r^{*}_{n})\min_{\xi}\mu^{\xi}_{n,p_{c},q}[\sigma_{*}=1]+\min_{\xi}\mu^{\xi}_{n,p_{c},q}[\sigma_{*}=1],$

which implies that

$\displaystyle\frac{1}{1+(q-1)r^{*}_{n}}\leqslant\min_{\xi}\mu^{\xi}_{n,p_{c},q}[\sigma_{*}=1]\leqslant\frac{1}{q}\leqslant\max_{\xi}\mu^{\xi}_{n,p_{c},q}[\sigma_{*}=1]\leqslant\frac{r^{*}_{n}}{r^{*}_{n}+q-1}.$

Therefore, for the maximum deviation from $\frac{1}{q}$, we have

$\displaystyle\max_{\xi}\left|\mu^{\xi}_{n,p_{c},q}[\sigma_{*}=1]-\frac{1}{q}\right|$
$\displaystyle=\max\left\\{\max_{\xi}\mu^{\xi}_{n,p_{c},q}[\sigma_{*}=1]-\frac{1}{q},\frac{1}{q}-\min_{\xi}\mu^{\xi}_{n,p_{c},q}[\sigma_{*}=1]\right\\}$
$\displaystyle\leqslant\max\left\\{\frac{(q-1)(r^{*}_{n}-1)}{q(r^{*}_{n}+q-1)},\frac{(q-1)(r^{*}_{n}-1)}{q(1+(q-1)r^{*}_{n})}\right\\}.$

This together with (3.19) gives us

$\displaystyle\liminf_{n\to\infty}\frac{1}{n}\max_{\xi}\left|\mu^{\xi}_{n,p_{c},q}[\sigma_{*}=1]-\frac{1}{q}\right|^{-2}$
$\displaystyle\geqslant\liminf_{n\to\infty}\frac{1}{n}\max\left\\{\frac{(q-1)(r^{*}_{n}-1)}{q(r^{*}_{n}+q-1)},\frac{(q-1)(r^{*}_{n}-1)}{q(1+(q-1)r^{*}_{n})}\right\\}^{-2}$
$\displaystyle=\frac{d^{2}-1}{6d^{2}}\left(\frac{q^{2}}{q-1}\right)^{2}.$

This is in fact the upper bound for the convergence rate of the marginal
probability. On the other hand, we have proved the lower bound of the
convergence rate in Proposition 2.3

$\limsup_{n\to\infty}\frac{1}{n}\max_{\xi}\left|\mu^{\xi}_{n,p_{c},q}[\sigma_{*}=1]-\frac{1}{q}\right|^{-2}\\\
\leqslant\lim_{n\to\infty}\frac{1}{n}\left(\left|\mu^{1}_{n,p_{c},q}[\sigma_{*}=1]-\frac{1}{q}\right|\right)^{-2}=\frac{d^{2}-1}{6d^{2}}\left(\frac{q^{2}}{q-1}\right)^{2}.$

Thus we finish the proof of the main theorem. ∎

######  Remark 3.4.

Follow the same proof of Theorem 1.2, we can also establish the convergence
rate for the subcritical case: under Hypothesis 1.1 for
$p\in(1-\frac{q}{d+1},1)\cap(0,1)$, we have an exponential convergence

$\displaystyle\lim_{n\to\infty}\frac{1}{n}\log\left(\max_{\xi}\left|\mu^{\xi}_{n,p,q}[\sigma_{*}=1]-\frac{1}{q}\right|\right)=\log\left(\frac{d(1-p)}{p+q-1}\right).$

##  4\. Convergence under the double periodic condition

In this section we prove Proposition 4.1, which implies that the two-step
iteration $(f\circ f)$, where $f$ is defined in (1.12), drives any initial
condition to the fixed point $r=1$. Proposition 4.1 was applied to prove the
convergence rate for pure boundary conditions in Proposition (2.3).

We give an elementary proof for Proposition 4.1 which can be read
independently from the rest of the paper. In fact, we will study the following
more general iteration $(f_{m}\circ f_{m})$, where

(4.1)
$f_{m}(x):=\left(\frac{(p+q-1)+(m-1+p)(x-1)}{(p+q-1)+m(x-1)}\right)^{d}.$

Obviously, from the definition (1.12), $f$ is the case of $f_{m}$ for $m=1$.
The definition of $f_{m}$ is not artificial, because $(f_{m}\circ f_{m})(r)$
is the mapping $\hat{h}(r)$ in (3.4) under the similar case of (3.12) and
$\mathcal{A}(r)$ in (3.3): for every $v,u\in[d]$, $\\{x^{vu}_{k}\\}_{k\in[q]}$
is the same vector, and there are $m$ entries taking the value $r$ while
$(q-m)$ entries taking the value $1$. It implies the two-step iterations under
a family of boundary conditions converges to the unique fixed point, and we
wish it will be helpful to prove the uniqueness conjecture (Hypothesis 1.1) of
the AF Potts model on trees in the future.

The main result of this part is the following proposition.

######  Proposition 4.1.

For any $x\geqslant 1$ and any integer $1\leqslant m\leqslant q-1$, we have an
estimate that $(f_{m}\circ
f_{m})^{\prime}(x)\in\left(0,\left(\frac{d(1-p)}{p+q-1}\right)^{2}\right]$,
and $(f_{m}\circ f_{m})^{\prime}(x)=\left(\frac{d(1-p)}{p+q-1}\right)^{2}$
admits a unique solution in $[1,\infty)$ that $x=1$.

From Proposition 4.1 and since we assume the subcritical or critical phase, we
have $\frac{d(1-p)}{p+q-1}\in(0,1]$. Then the iteration gives a strictly
decreasing sequence once starting from some initial value above $1$, and
eventually converges to $1$ as it is the unique fixed point; see Corollary 4.5
for details.

######  Remark 4.2.

Proposition 4.1 covers the special case of the uniqueness conjecture for a
class of the “double periodic boundary conditions”, namely, for the AF Potts
model on a regular tree of height $n$, we assume the boundary conditions are
given by $d^{2}$ identical copies of the boundary conditions for sub-trees of
height $n-2$. One strategy to prove the uniqueness conjecture in future is to
approximate any Gibbs measures on trees by double periodic Gibbs measures.

We first give the strategy of the proof of Proposition 4.1. Recall the
constant $A=d(1-p)$ and $B=p+q-1$ defined in (3.15), then we have
${f_{m}(x):=\left(\frac{B+(m-1+p)(x-1)}{B+m(x-1)}\right)^{d}}$ and

$\displaystyle(f_{m}\circ f_{m})^{\prime}(x)$
$\displaystyle=\frac{A^{2}}{B^{2}}\left(\frac{B^{2}}{(B+m(x-1))(B+m(f_{m}(x)-1))}\right)^{2}$
$\displaystyle\qquad\times\left(\frac{(B+(m-1+p)(x-1))(B+(m-1+p)(f_{m}(x)-1))}{(B+m(x-1))(B+m(f_{m}(x)-1))}\right)^{d-1}.$

We introduce two functions

(4.2)
$\begin{split}H_{m}(x)&:=\bigg{(}B+m(x-1)\bigg{)}\bigg{(}B+m(f_{m}(x)-1)\bigg{)}-B^{2},\\\
K_{m}(x)&:=\bigg{(}B+m(x-1)\bigg{)}\bigg{(}B+m(f_{m}(x)-1)\bigg{)}\\\
&\qquad-\bigg{(}B+(m-1+p)(x-1)\bigg{)}\bigg{(}B+(m-1+p)(f_{m}(x)-1)\bigg{)}.\end{split}$

Keep in mind that $A=B$ for the critical case, so $(f_{m}\circ
f_{m})^{\prime}(x)\in\left(0,\left(\frac{d(1-p)}{p+q-1}\right)^{2}\right]$ is
equivalent to prove that

(4.3) $\displaystyle
G_{m}(x):=\left(1-\frac{H_{m}(x)}{B^{2}+H_{m}(x)}\right)^{2}\left(1-\frac{K_{m}(x)}{B^{2}+H_{m}(x)}\right)^{d-1}\leqslant
1,$

and the solution of $(f_{m}\circ
f_{m})^{\prime}(x)=\left(\frac{d(1-p)}{p+q-1}\right)^{2}$ is that of
$G_{m}(x)=1$. Thus, we focus on the function $G_{m}(x)$ and resume some
elementary calculations in the following lemma. We also introduce

(4.4) $\displaystyle g_{m}(x):=\frac{B+(m-1+p)(x-1)}{B+m(x-1)},$

so it will help simplify the notation.

######  Lemma 4.3.

  1. (1)

Using the notation $g_{m}$ in (4.4), we have

(4.5) $\begin{split}f_{m}=(g_{m})^{d},\qquad
f_{m}^{\prime}=d(g_{m})^{d-1}g_{m}^{\prime},\\\
f_{m}^{\prime\prime}=d(d-1)(g_{m})^{d-2}(g_{m}^{\prime})^{2}+d(g_{m})^{d-1}g_{m}^{\prime\prime},\end{split}$

where the expression of $g_{m}^{\prime}$ and $g_{m}^{\prime\prime}$ are

(4.6) $\displaystyle g_{m}^{\prime}(x)=\frac{B(p-1)}{(B+m(x-1))^{2}},\qquad
g_{m}^{\prime\prime}(x)=\frac{2mB(1-p)}{(B+m(x-1))^{3}}.$

We also have $f_{m}(1)=1$ and $f^{\prime}_{m}(1)=-A/B$.

  2. (2)

Some properties about $H_{m}(x)$: for all $1\leqslant m\leqslant q-1$, we have

     * •

$H_{m}(1)=0$ and $H_{m}(x)>0$ for all $x>1$.

     * •

$H_{m}^{\prime}(1)=mB(1-A/B)$, $H_{m}^{\prime}(x)>0$ for all $x>1$.

     * •

The explicit expression for $H_{m}^{\prime\prime}(x)$ is

(4.7) $\displaystyle
H_{m}^{\prime\prime}(x)=m(g_{m})^{d-2}\bigg{(}B+m(x-1)\bigg{)}^{-4}\bigg{(}\gamma_{H}+\beta_{H}(x-1)\bigg{)},$

with the quantity $\beta_{H},\gamma_{H}$ defined as

(4.8) $\displaystyle\beta_{H}$ $\displaystyle:=(1-d^{-1})mA^{2}B^{2},$ (4.9)
$\displaystyle\gamma_{H}$ $\displaystyle:=(1-d^{-1})A^{2}B^{3}.$

  3. (3)

Some properties about $K_{m}(x)$: denote by

(4.10) $\displaystyle C_{m}:=2m-1+p,$

then we have

     * •

$K_{m}(1)=0$.

     * •

$K_{m}^{\prime}(1)=(1-p)B(1-A/B)$.

     * •

The explicit expression for $K_{m}^{\prime\prime}(x)$ is

(4.11) $\displaystyle
K_{m}^{\prime\prime}(x)=(1-p)(g_{m})^{d-2}\bigg{(}B+m(x-1)\bigg{)}^{-4}\bigg{(}\gamma_{K}+\beta_{K}(x-1)\bigg{)},$

with the quantity $\beta_{K},\gamma_{K}$ defined as

(4.12) $\displaystyle\beta_{K}$
$\displaystyle:=AB^{2}(-2(C_{m}-m)^{2}+(1-d^{-1})AC_{m}),$ (4.13)
$\displaystyle\gamma_{K}$ $\displaystyle:=AB^{3}(A-C_{m}).$

###### Proof.

  1. (1)

This is the direct calculation of $f_{m}$ in function of $g_{m}$.

  2. (2)

$H_{m}(1)=0$ comes direct from the fact that $f_{m}(1)=1$. We calculate the
derivative of $H_{m}$, which is

$\displaystyle H_{m}^{\prime}(x)$
$\displaystyle=m\left(\bigg{(}B+m(f_{m}(x)-1)\bigg{)}+f_{m}^{\prime}(x)\bigg{(}B+m(x-1)\bigg{)}\right)$
$\displaystyle=m\bigg{(}(B-m)(f_{m}^{\prime}(x)+1)+m(f_{m}(x)+xf_{m}^{\prime}(x))\bigg{)}.$

We evaluate it at $1$ using $f_{m}(1)=1$ and $f_{m}^{\prime}(1)=-A/B$, then we
obtain that ${H_{m}^{\prime}(1)=mB(1-A/B)}$. We calculate the second
derivative

$\displaystyle H_{m}^{\prime\prime}(x)$
$\displaystyle=m\bigg{(}(B-m)f_{m}^{\prime\prime}(x)+m(2f_{m}^{\prime}(x)+xf_{m}^{\prime\prime}(x))\bigg{)}$
$\displaystyle=m\bigg{(}(B+m(x-1))f_{m}^{\prime\prime}(x)+2mf_{m}^{\prime}(x)\bigg{)}.$

We put in the expression of $f_{m}^{\prime\prime}(x)$ in function of
$g_{m}(x)$ and its derivative and obtain that

$\displaystyle H_{m}^{\prime\prime}(x)$
$\displaystyle=m\bigg{(}(B+m(x-1))f_{m}^{\prime\prime}(x)+2mf_{m}^{\prime}(x)\bigg{)}$
$\displaystyle=m\bigg{(}(B+m(x-1))\left(d(d-1)(g_{m})^{d-2}(g_{m}^{\prime})^{2}+d(g_{m})^{d-1}g_{m}^{\prime\prime}\right)+2m(d(g_{m})^{d-1}g_{m}^{\prime})\bigg{)}$
$\displaystyle=m(g_{m})^{d-2}\bigg{(}(B+m(x-1))\left(d(d-1)(g_{m}^{\prime})^{2}+dg_{m}^{\prime\prime}g_{m}\right)+2m(dg_{m}^{\prime}g_{m})\bigg{)}.$

We keep the first factor $(g_{m})^{d-2}$, while put in the exact expression of
$g_{m},g_{m}^{\prime}$ and $g_{m}^{\prime\prime}$ in the other terms

$\displaystyle H_{m}^{\prime\prime}(x)$
$\displaystyle=m(g_{m})^{d-2}(B+m(x-1))^{-4}\times$
$\displaystyle\Bigg{(}(B+m(x-1))\bigg{(}(1-d^{-1})A^{2}B^{2}+(2m)AB\big{(}B+(m-1+p)(x-1)\big{)}\bigg{)}$
$\displaystyle\qquad\left.-(2m)AB\bigg{(}\big{(}B+(m-1+p)(x-1)\big{)}\big{(}B+m(x-1)\big{)}\Bigg{)}\right)$
$\displaystyle=m(g_{m})^{d-2}(B+m(x-1))^{-4}\bigg{(}(1-d^{-1})A^{2}B^{2}(B+m(x-1))\bigg{)}.$

This gives the expression of $\beta_{H}$ and $\gamma_{H}$, and also proves
that

$\displaystyle\forall x\geqslant 1,\qquad H_{m}^{\prime\prime}(x)\geqslant
mB^{-4}\bigg{(}(1-d^{-1})A^{2}B^{3}\bigg{)}>0.$

Combined this with the expression of $H_{m}^{\prime}(1)$, we know that
$H_{m}^{\prime}(x),H_{m}(x)>0$ for all $x>1$.

  3. (3)

The part about the $K_{m}$ is similar. $K_{m}(1)=0$ is also the result from
$f_{m}(1)=1$. We calculate its derivative that

$\displaystyle K_{m}^{\prime}(x)$
$\displaystyle=m\bigg{(}B+m(f_{m}(x)-1)\bigg{)}+mf_{m}^{\prime}(x)\bigg{(}B+m(x-1)\bigg{)}$
$\displaystyle-(m-1+p)\bigg{(}B+(m-1+p)(f_{m}(x)-1)\bigg{)}-(m-1+p)f_{m}^{\prime}(x)\bigg{(}B+(m-1+p)(x-1)\bigg{)}$
$\displaystyle=(1-p)f_{m}^{\prime}(x)\bigg{(}B+(2m-1+p)(x-1)\bigg{)}+(1-p)\bigg{(}B+(2m-1+p)(f_{m}(x)-1)\bigg{)}.$

Recall that $C_{m}=2m-1+p$, we have

(4.14)
$\begin{split}K_{m}^{\prime}(x)&=(1-p)f_{m}^{\prime}(x)\bigg{(}B+C_{m}(x-1)\bigg{)}+(1-p)\bigg{(}B+C_{m}(f_{m}(x)-1)\bigg{)}\\\
&=(1-p)\bigg{(}(B-C_{m})(f_{m}^{\prime}(x)+1)+C_{m}(f_{m}(x)+xf_{m}^{\prime}(x))\bigg{)}.\end{split}$

$K_{m}^{\prime}(1)=(1-p)B(1-A/B)$ is a direct result from
${f_{m}^{\prime}(1)=-A/B}$ and ${f_{m}(1)=1}$. Then we calculate the second
derivative that

$\displaystyle K_{m}^{\prime\prime}(x)$
$\displaystyle=(1-p)\bigg{(}(B-C_{m})f_{m}^{\prime\prime}(x)+C_{m}(2f_{m}^{\prime}(x)+xf_{m}^{\prime\prime}(x))\bigg{)}$
$\displaystyle=(1-p)\bigg{(}(B+C_{m}(x-1))f_{m}^{\prime\prime}(x)+2C_{m}f_{m}^{\prime}(x)\bigg{)}.$

We put in the expression of $f_{m}^{\prime\prime}(x)$ in function of
$g_{m}(x)$ and its derivative and obtain that

$\displaystyle K_{m}^{\prime\prime}(x)$
$\displaystyle=(1-p)\bigg{(}(B+C_{m}(x-1))\left(d(d-1)(g_{m})^{d-2}(g_{m}^{\prime})^{2}+d(g_{m})^{d-1}g_{m}^{\prime\prime}\right)+2C_{m}(d(g_{m})^{d-1}g_{m}^{\prime})\bigg{)}$
$\displaystyle=(1-p)(g_{m})^{d-2}\bigg{(}(B+C_{m}(x-1))\left(d(d-1)(g_{m}^{\prime})^{2}+dg_{m}^{\prime\prime}g_{m}\right)+2C_{m}(dg_{m}^{\prime}g_{m})\bigg{)}.$

Once again, we keep the first factor $(g_{m})^{d-2}$ and put in the exact
expression of $g_{m},g_{m}^{\prime}$ and $g_{m}^{\prime\prime}$ in the other
terms

$\displaystyle K_{m}^{\prime\prime}(x)$
$\displaystyle=(1-p)(g_{m})^{d-2}(B+m(x-1))^{-4}\times$
$\displaystyle\Bigg{(}(B+C_{m}(x-1))\bigg{(}(1-d^{-1})A^{2}B^{2}+(2m)AB\big{(}B+(m-1+p)(x-1)\big{)}\bigg{)}$
$\displaystyle\qquad\left.-(2C_{m})AB\bigg{(}\big{(}B+(m-1+p)(x-1)\big{)}\big{(}B+m(x-1)\big{)}\Bigg{)}\right).$

From this, the term $(x-1)^{2}$ vanishes and we get the desired
$\beta_{K},\gamma_{K}$.

∎

######  Remark 4.4.

We remark here that the monotonicity of $K_{m}$ is not as good as that of
$H_{m}$, because its sign of second derivative depends on the regime of $x$
and the parameters; see the expression of $\gamma_{K},\beta_{K}$.

With the preparation of Lemma 4.3, we are now ready to prove Proposition 4.1.

###### Proof of Proposition 4.1.

We aim to prove (4.3). Since we always have $H_{m}(x)\geqslant 0$ for
$x\geqslant 1$ from Lemma 4.3, the key is the sign of $K_{m}(x)$. For the
intervals $K_{m}(x)\geqslant 0$, it is clear $G_{m}(x)\leqslant 1$ from the
expression (4.3), so we are interested in the part $K_{m}(x)\leqslant 0$. We
calculate the derivative of $G_{m}(x)$ in function of $K_{m}(x)$ and
$H_{m}(x)$

(4.15)
$\begin{split}G_{m}^{\prime}&=\left(1-\frac{H_{m}}{B^{2}+H_{m}}\right)\left(1-\frac{K_{m}}{B^{2}+H_{m}}\right)^{d-2}\\\
&\qquad\times\Bigg{(}(d-1)\left(\frac{-K_{m}^{\prime}(B^{2}+H_{m})+K_{m}H_{m}^{\prime}}{(B^{2}+H_{m})^{2}}\right)\left(\frac{B^{2}}{B^{2}+H_{m}}\right)\\\
&\qquad\qquad+2\left(\frac{B^{2}+H_{m}-K_{m}}{B^{2}+H_{m}}\right)\left(\frac{-B^{2}H_{m}^{\prime}}{(B^{2}+H_{m})^{2}}\right)\Bigg{)}\\\
&=\left(1-\frac{H_{m}}{B^{2}+H_{m}}\right)\left(1-\frac{K_{m}}{B^{2}+H_{m}}\right)^{d-2}\left(\frac{B^{2}}{(B^{2}+H_{m})^{3}}\right)\times\\\
&\qquad\left(-(B^{2}+H_{m})\big{(}(d-1)K_{m}^{\prime}+2H_{m}^{\prime}\big{)}+(d+1)H_{m}^{\prime}K_{m}\right).\end{split}$

The sign of $G_{m}^{\prime}$ depends on the last line. Here one important
observation is

(4.16) $\displaystyle\forall
x>1,\qquad(d-1)K_{m}^{\prime}(x)+2H_{m}^{\prime}(x)>0.$

We verify this observation by writing the sum as integration of second order
derivative from Lemma 4.3

(4.17) $\begin{split}&(d-1)K_{m}^{\prime}(x)+2H_{m}^{\prime}(x)\\\
&=(d-1)K_{m}^{\prime}(1)+2H_{m}^{\prime}(1)\\\
&\quad+\int_{1}^{x}(g_{m})^{d-2}\bigg{(}B+m(y-1)\bigg{)}^{-4}\bigg{(}(d-1)(1-p)\big{(}\gamma_{K}+\beta_{K}(y-1)\big{)}+2m\big{(}\gamma_{H}+\beta_{H}(y-1)\big{)}\bigg{)}\,{\mathrm{d}}y.\end{split}$

From Lemma 4.3, we know that $K_{m}^{\prime}(1),H_{m}^{\prime}(1)\geqslant 0$
as $A\leqslant B$ from (3.16). Then, we apply the explicit expression (4.9),
(4.13), (4.8), (4.12)

$\displaystyle(d-1)(1-p)\gamma_{K}+2m\gamma_{H}$
$\displaystyle=(d-1)(1-p)AB^{3}(A-C_{m})+2m(1-d^{-1})A^{2}B^{3}$
$\displaystyle=(1-d^{-1})A^{2}B^{3}(A-C_{m}+2m)$ $\displaystyle>1-p>0.$

Here we use the expression $A=d(1-p)$ and ${C_{m}=2m-1+p\leqslant 2m}$ in the
last line. Similarly, for the coefficient of $(y-1)$ we have

$\displaystyle(d-1)(1-p)\beta_{K}+2m\beta_{H}$
$\displaystyle=(d-1)(1-p)AB^{2}(-2(C_{m}-m)^{2}+(1-d^{-1})AC_{m})+2m^{2}(1-d^{-1})A^{2}B^{2}$
$\displaystyle=(1-d^{-1})A^{2}B^{2}\bigg{(}2m^{2}-2(C_{m}-m)^{2}+(1-d^{-1})AC_{m}\bigg{)}$
$\displaystyle>0.$

In the last line, we use the fact $C_{m}-m=2m-1+p-m\in(0,m)$. Therefore, we
justify the observation (4.16).

We now use this observation to conclude the proof. Because $K_{m}$ is a
continuous function, the part $x\geqslant 1$ can be decomposed into the
intervals of $K_{m}(x)\geqslant 0$ and $K_{m}(x)<0$, i.e.

(4.18) $\begin{split}&x_{1}^{+}:=1,\\\ \forall
i\in\mathbb{N}^{+},\quad&x_{i}^{-}:=\inf\\{x:x\geqslant
x_{i}^{+},K_{m}(x)<0\\},\\\ \forall i\in\mathbb{N}^{+},i\geqslant
2,\quad&x_{i}^{+}:=\inf\\{x:x\geqslant x_{i-1}^{-},K_{m}(x)\geqslant 0\\},\\\
\forall i\in\mathbb{N}^{+},\quad&I_{i}^{+}:=[x_{i}^{+},x_{i}^{-}],\qquad
I_{i}^{-}:=(x_{i}^{-},x_{i+1}^{+}).\end{split}$

Then we have

$\displaystyle\\{x:x\geqslant 1,K_{m}(x)\geqslant
0\\}=\bigcup_{i\in\mathbb{N}^{+}}I_{i}^{+},\qquad\\{x:x\geqslant
1,K_{m}(x)<0\\}=\bigcup_{i\in\mathbb{N}^{+}}I_{i}^{-}.$

As stated in the previous paragraphs that, $H_{m}(x)\geqslant 0$ for
$x\geqslant 1$ from Lemma 4.3 and the expression (4.3) imply that
$G_{m}(x)\leqslant 1$ for $K_{m}(x)\geqslant 0$. The observation (4.16) and
$H_{m}^{\prime}(x)\geqslant 0$ for $x\geqslant 1$ from Lemma 4.3 give that
that, for the case $K_{m}(x)<0$, the last line in (4.15) is strictly negative,
and $G_{m}^{\prime}(x)<0$. Therefore, we obtain that

(4.19) $\displaystyle\forall i\in\mathbb{N}^{+},\forall x\in
I_{i}^{-}=(x_{i}^{-},x_{i+1}^{+}),\qquad G_{m}(x)<G_{m}(x_{i}^{-}),$

and

$\displaystyle\sup_{x\geqslant 1}G_{m}(x)=\sup_{x\geqslant 1,K_{m}(x)\geqslant
0}G_{m}(x)\leqslant 1,$

which concludes (4.3) and $(f_{m}\circ
f_{m})^{\prime}(x)\in\left(0,\left(\frac{d(1-p)}{p+q-1}\right)^{2}\right]$.

Finally, we prove the unique solution of $(f_{m}\circ
f_{m})^{\prime}(x)=\left(\frac{d(1-p)}{p+q-1}\right)^{2}$. As discussed above,
it is equivalent to $G_{m}(x)=1$ and is only possible to attain on
$K_{m}(x)\geqslant 0$ thanks to the observation (4.19). Viewing the expression
(4.3), this requires that $K_{m}(x)=0$ and $H_{m}(x)=0$. For the latter, the
unique solution is $x=1$ from (2) of Lemma 4.3, and $x=1$ also verifies the
former equation. This finishes the proof of the uniqueness. ∎

In the end, we prove the convergence of $r_{n}$ at critical and subcritical
regime as a simple application.

######  Corollary 4.5.

Let $q,d\in\mathbb{N}^{+}$ and $q\geqslant 2$. Also let
$p\in[1-\frac{q}{d+1},1)\cap(0,1)$, $(r_{n})_{n\in N^{+}}$ defined in (1.10)
converges to $1$.

###### Proof.

From Lemma 2.2, we have $r_{2n+2}=(f\circ f)(r_{2n})$ with $f=f_{1}$ in (4.1)
and for even terms $r_{2n}\geqslant 1$ by a simple induction. Then
$p\in[1-\frac{q}{d+1},1)\cap(0,1)$ implies that $(f\circ
f)^{\prime}(x)\leqslant 1$ from Proposition 4.1. Thus, by the mean value
theorem,

$\displaystyle\forall x\geqslant 1,\exists z\in(1,x),\text{ such that
}\qquad(f\circ f)(x)-1=(f\circ f)^{\prime}(z)(x-1)\leqslant x-1,$

and the mapping $(f\circ f)$ admits a fixed point $x^{*}$

We prove by contradiction that $x^{*}=1$ is the unique fixed point. Suppose
that there is another fixed point $x^{*}>1$ for $(f\circ f)$, then once again
by the mean value theorem,

$\displaystyle\exists z\in(1,x),\qquad x^{*}-1=(f\circ f)(x^{*})-1=(f\circ
f)^{\prime}(z)(x^{*}-1)\leqslant x^{*}-1,$

which implies that $(f\circ f)^{\prime}(z)=1$. This contradicts Proposition
4.1 that $1$ is the unique solution of $(f_{m}\circ
f_{m})^{\prime}(x)=\left(\frac{d(1-p)}{p+q-1}\right)^{2}$.

Finally, the limit of $(r_{2n})_{n\in\mathbb{N}^{+}}$ follows the iteration
$r_{2n+2}=(f\circ f)(r_{2n})$ and the unique fixed point of $(f\circ f)$ under
the assumption $p\in[1-\frac{q}{d+1},1)\cap(0,1)$. The limit of
$(r_{2n+1})_{n\in\mathbb{N}^{+}}$ follows that of the even terms and the
continuity of $f$. ∎

### Acknowledgements

The research of C.Gu and W.Wu are supported in part by the National Key R&D
Program of China (No. 2021YFA1002700). The research of W.Wu is supported in
part by a Shanghai Municipal Education Commission grant. K. Yang would like to
thank the NYU Shanghai and ECNU Mathematical Institute for hospitality.

## References

  * [1] V. Beffara and H. Duminil-Copin.  The self-dual point of the two-dimensional random-cluster model is critical for q $\geqslant$ 1\.  Probability Theory and Related Fields, 153(3-4):511–542, 2012.
  * [2] F. Bencs, D. de Boer, P. Buys, and G. Regts.  Uniqueness of the gibbs measure for the anti-ferromagnetic potts model on the infinite $\delta$-regular tree for large $\delta$.  arXiv preprint arXiv:2203.15457, 2022.
  * [3] G. R. Brightwell and P. Winkler.  Random colorings of a Cayley tree.  In Contemporary combinatorics, volume 10 of Bolyai Soc. Math. Stud., pages 247–276. János Bolyai Math. Soc., Budapest, 2002.
  * [4] D. de Boer, P. Buys, and G. Regts.  Uniqueness of the Gibbs measure for the $4$-state anti-ferromagnetic Potts model on the regular tree.  arXiv preprint arXiv:2010.03177, nov 2020.
  * [5] R. L. Dobrušin.  Description of a random field by means of conditional probabilities and conditions for its regularity.  Teor. Verojatnost. i Primenen, 13:201–229, 1968.
  * [6] H. Duminil-Copin, M. Harel, B. Laslier, A. Raoufi, and G. Ray.  Logarithmic variance for the height function of square-ice.  arXiv preprint arXiv:1911.00092, 2019.
  * [7] O. N. Feldheim and Y. Spinka.  Long-range order in the 3-state antiferromagnetic Potts model in high dimensions.  J. Eur. Math. Soc. (JEMS), 21(5):1509–1570, 2019.
  * [8] S. J. Ferreira and A. D. Sokal.  Antiferromagnetic potts models on the square lattice: A high-precision monte carlo study.  Journal of statistical physics, 96(3):461–530, 1999.
  * [9] A. Galanis, L. A. Goldberg, and K. Yang.  Uniqueness for the 3-state antiferromagnetic Potts model on the tree.  Electronic Journal of Probability, 23, 2018.
  * [10] L. A. Goldberg, M. Jalsenius, R. Martin, and M. Paterson.  Improved mixing bounds for the anti-ferromagnetic Potts model on ${\mathbb{Z}}^{2}$.  LMS J. Comput. Math., 9:1–20, 2006.
  * [11] R. B. Griffiths.  Correlations in ising ferromagnets. i.  Journal of Mathematical Physics, 8(3):478–483, 1967.
  * [12] G. Grimmett.  The random-cluster model, volume 333 of Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences].  Springer-Verlag, Berlin, 2006.
  * [13] J. Jonasson.  Uniqueness of uniform random colorings of regular trees.  Statist. Probab. Lett., 57(3):243–248, 2002.
  * [14] R. Peled.  High-dimensional Lipschitz functions are typically flat.  Ann. Probab., 45(3):1351–1447, 2017.
  * [15] R. Peled and Y. Spinka.  Long-range order in discrete spin systems.  arXiv preprint arXiv:2010.03177, 2020.
  * [16] F. Peruggi, F. di Liberto, and G. Monroy.  The potts model on bethe lattices. i. general results.  Journal of Physics A: Mathematical and General, 16(4):811–827, mar 1983.
  * [17] G. Ray and Y. Spinka.  Proper 3-colorings of $\mathbb{Z}^{2}$ are bernoulli.  arXiv preprint arXiv:2004.00028, 2020.
  * [18] J. Salas and A. D. Sokal.  Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem.  J. Statist. Phys., 86(3-4):551–579, 1997.