# Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs
in the Non-Uniqueness Region

Zongchen Chen School of Computer Science, Georgia Institute of Technology,
Atlanta, GA 30332, USA. Email: {chenzongchen<EMAIL_ADDRESS>Research
supported in part by NSF grant CCF-2007022. Andreas Galanis Department of
Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford,
OX1 3QD, UK. Email<EMAIL_ADDRESS>Daniel Štefankovič Department
of Computer Science, University of Rochester, Rochester, NY 14627, USA. Email:
<EMAIL_ADDRESS>Research supported in part by NSF grant
CCF-2007287. Eric Vigoda⋆

###### Abstract

For spin systems, such as the $q$-colorings and independent-set models,
approximating the partition function in the so-called non-uniqueness region,
where the model exhibits long-range correlations, is typically computationally
hard for bounded-degree graphs. We present new algorithmic results for
approximating the partition function and sampling from the Gibbs distribution
for spin systems in the non-uniqueness region on random regular bipartite
graphs. We give an $\mathsf{FPRAS}$ for counting $q$-colorings for even
$q=O\big{(}\tfrac{\Delta}{\log{\Delta}}\big{)}$ on almost every
$\Delta$-regular bipartite graph. This is within a factor $O(\log{\Delta})$ of
the sampling algorithm for general graphs in the uniqueness region and
improves significantly upon the previous best bound of
$q=O\big{(}\tfrac{\sqrt{\Delta}}{(\log\Delta)^{2}}\big{)}$ by Jenssen,
Keevash, and Perkins (SODA’19). Analogously, for the hard-core model on
independent sets weighted by $\lambda>0$, we present an $\mathsf{FPRAS}$ for
estimating the partition function when
$\lambda=\Omega\big{(}\tfrac{\log{\Delta}}{\Delta}\big{)}$, which improves
upon previous results by an $\Omega(\log\Delta)$ factor. Our results for the
colorings and hard-core models follow from a general result that applies to
arbitrary spin systems. Our main contribution is to show how to elevate
probabilistic/analytic bounds on the marginal probabilities for the typical
structure of phases on random bipartite regular graphs into efficient
algorithms, using the polymer method. We further show evidence that our result
for colorings is within a constant factor of best possible using current
polymer-method approaches.

##  1 Introduction

Polymer models have recently been used to obtain algorithms for spin systems
in regimes where standard algorithmic tools (such as correlation-decay
algorithms or Gibbs sampling/Glauber dynamics) are inefficient. The
prototypical class of graphs where polymer models have been applied to are
classes of expander and random regular graphs [21, 6, 18, 1, 22, 8, 14], see
also [19, 4, 20] for applications on the grid.

Random bipartite regular graphs are particularly tantalizing [21, 22, 14],
since on the one hand there is a somewhat standard probabilistic framework to
obtain rough analysis estimates for arbitrary spin systems on them (using
first/second moment arguments [15]), but on the other hand the corresponding
algorithmic framework, and in particular the development of efficient
sampling/counting algorithms, is lacking.

This paper will focus on finding the algorithmic limits of the polymer method
for the two canonical models of interest, the $q$-colorings and the hard-core
model (weighted independent sets), though our results apply much more
generally as we will detail later. One of the main contributions of this work
is to elevate the rough guarantees obtained by analytic/probabilistic methods
into efficient approximate sampling/counting algorithms.

We begin with the colorings problem: given an integer $q\geq 3$ and a graph
$G=(V,E)$ of maximum degree $\Delta$, the goal is to approximate the number of
proper $q$-colorings of $G$, and sample a proper $q$-coloring uniformly at
random. For general graphs there is an intriguing computational phase
transition that is conjectured to occur at the statistical physics phase
transition for uniqueness/non-uniqueness of the Gibbs measure on the infinite
$\Delta$-regular tree. When $q\geq\Delta+2$ it is conjectured that the simple
single-site update Markov chain known as the Glauber dynamics is rapidly
mixing on any graph of maximum degree $\Delta$ (rapid mixing refers to a
convergence rate which is polynomial in $n=|V|$). In contrast when
$q\leq\Delta$ it is believed that the problem is intractable.

Current bounds are far from resolving this conjecture but have made
considerable progress. On the algorithmic side, recent results establish
$O(n\log{n})$ mixing time of the Glauber dynamics on an $n$-vertex graph of
maximum degree $\Delta$ when $q>(11/6-\varepsilon_{0})\Delta$ for a positive
constant $\varepsilon_{0}\approx 10^{-5}$ [3, 24, 7] and on triangle-free
graphs when $q>1.764\Delta$ [10, 12, 9]. On the negative side, it was shown in
[15] that for even $q<\Delta$ it is NP-hard to approximate the number of
$q$-colorings. The restriction that $q$ is even in this hardness result is
rather technical and is a byproduct of a certain maximisation which was
carried out in [15] for even $q$.

The above results address the problem on worst-case graphs; in this paper we
address the behavior on _typical/random_ graphs. In this vein, random regular
bipartite graphs are particularly interesting as they manifest the phase
transition of regular trees, and consequently they serve as the key gadget in
hardness results [25, 26, 16, 15, 11, 5]. However, standard approximate
counting techniques, such as Markov Chain Monte Carlo (MCMC), fail in the non-
uniqueness region; e.g., the Glauber dynamics is exponentially slow to
converge, with high probability over the choice of the random regular
bipartite graph, for even $q<\Delta$ [15].

Intriguing algorithmic results for the non-uniqueness region of $q\ll\Delta$
on random bipartite graphs were devised using the recently introduced polymer
method of [21] and [19]. Jenssen, Keevash, and Perkins [21] presented an
$\mathsf{FPTAS}$ for almost every regular bipartite graph when $q\leq
C\tfrac{\sqrt{\Delta}}{(\log\Delta)^{2}}$ for a constant $C>0$ (see also the
independent result of Liao, Lin, Lu, and Mao [22]). The running time of these
algorithms was improved to $O(n^{2}(\log n)^{3})$ in [8] using a randomized
method, see Remark 3 below.

For a graph $G=(V,E)$ and an integer $q\geq 3$, the partition function $Z_{G}$
is the number of $q$-colorings of $G$. An algorithm $\mathcal{A}$ is an
$\mathsf{FPRAS}$ for the partition function on almost all $\Delta$-regular
bipartite graphs if, with probability $1-o(1)$ over a graph $G$ chosen u.a.r.
from $n$-vertex $\Delta$-regular bipartite graphs, given $G$, an accuracy
$\epsilon>0$, and a tolerance $\delta>0$, the algorithm $\mathcal{A}$ produces
in time $poly(n,1/\epsilon,\log(1/\delta))$ an estimate $\hat{Z}$ of the
partition function $Z_{G}$ satisfying
$(1-\epsilon)Z_{G}\leq\hat{Z}\leq(1+\epsilon)Z_{G}$ with probability $\geq
1-\delta$. The algorithm is an $\mathsf{FPTAS}$ if it achieves $\delta=0$.

Here we present an $\mathsf{FPRAS}$ for $q$-colorings on almost every regular
bipartite graph for even $q=O(\tfrac{\Delta}{\log{\Delta}})$. This improves
significantly over the best previous known bound of
$q=O\big{(}\tfrac{\sqrt{\Delta}}{(\log\Delta)^{2}}\big{)}$ given in [21], and
is within only an $O(\log\Delta)$-factor from the uniqueness/hardness
threshold. In fact, we also provide strong evidence that this is the limit of
the polymer method up to the implicit constants in the given bounds, see the
upcoming Lemma 11 for details.

######  Theorem 1.

For all even $q\geq 4$ and all $\Delta\geq 100q\log q$, there is an
$\mathsf{FPRAS}$ for the number of $q$-colorings on almost all
$\Delta$-regular bipartite graphs.

We provide analogous results for the hard-core model on weighted independent
sets. For a graph $G=(V,E)$, let $\Omega_{G}$ denote the collection of
independent sets of $G$. For a parameter $\lambda>0$, let independent set
$\sigma\in\Omega_{G}$ have weight $w(\sigma)=\lambda^{|\sigma|}$. The
partition function for the hard-core model on graph $G$ at fugacity $\lambda$
is defined as $Z_{G}=\sum_{\sigma\in\Omega}w(\sigma)$ and the Gibbs
distribution is $\mu(\sigma)=w(\sigma)/Z_{G}$. The hard-core model on the
infinite $\Delta$-regular tree undergoes a phase transition corresponding to
uniqueness vs. non-uniqueness of the infinite-volume Gibbs measure at
$\lambda_{c}(\Delta)=\tfrac{(\Delta-1)^{\Delta-1}}{(\Delta-2)^{\Delta}}\sim\tfrac{\mathrm{e}}{\Delta}$.
For any graph $G$ of maximum degree $\Delta$, for all
$\lambda<\lambda_{c}(\Delta)$, the Glauber dynamics mixes in $O(n\log{n})$
time [10]. On the other side, when $\lambda>\lambda_{c}(\Delta)$, the problem
of approximating the partition function is NP-hard on $\Delta$-regular graphs
[25, 26, 16].

For random $\Delta$-regular bipartite graphs, [21] presented an
$\mathsf{FPTAS}$ for $\lambda>50\tfrac{(\log\Delta)^{2}}{\Delta}$ when
$\Delta$ is sufficiently large, and [22] for $\lambda\geq 1$ and $\Delta\geq
53$, see also [6, 1, 23] for related results on bipartite graphs. We get an
improved range of $\lambda=\Omega(\tfrac{\log{\Delta}}{\Delta})$, which is
again within an $O(\log\Delta)$-factor from the uniqueness/hardness threshold.

######  Theorem 2.

For all $\Delta\geq 53$ and all $\lambda>100\frac{\log\Delta}{\Delta}$, there
is an $\mathsf{FPRAS}$ for the partition function of the hard-core model with
parameter $\lambda$ on almost all $\Delta$-regular bipartite graphs.

######  Remark 3.

In Theorems 1 and 2, we can also obtain deterministic approximation schemes
($\mathsf{FPTAS}$) by applying the interpolation method, analogously to [21].
Here, we follow the Markov-chain framework of [8], which provides
substantially stronger running time guarantees than those we state for
convenience here. In particular, the FPRASes in Theorems 1 and 2 run in time
$O\big{(}(\tfrac{n}{\epsilon})^{2}\log^{3}(\tfrac{n}{\epsilon})\big{)}$ when
the desired accuracy error is not exponentially small (i.e.,
$\epsilon\geq\mathrm{e}^{-\Omega(n)}$). Moreover, in the same range of the
parameters, we obtain in addition approximate samplers from the Gibbs
distribution with analogous running-time guarantees.

We remark that the condition that $q$ is even in Theorem 1 is for the same
technical reasons that the hardness results of [15] were obtained for $q$ even
which we stated earlier; we conjecture that the result can be extended to odd
$q$ and our proof approach extends verbatim (once one has the analogue of the
upcoming Lemma 8).

In fact, Theorems 1 and 2 will be proved as special cases of a general
algorithmic result that applies to arbitrary spin systems on random bipartite
regular graphs. We first introduce general spin systems following the
framework of [14]. Note that the techniques in [14] were targeted to obtain
bounds for general spin system and do not yield tight results, e.g., for
colorings the bound obtained therein is roughly $q=O(\Delta^{1/4})$, cf. with
the bound on $q$ in Theorem 1. Also, to obtain the result of the hard-core
model in Theorem 2 we will also need to explicitly account for the presence of
external fields, as detailed in the next section.

##  2 Proof Outline

###  2.1 Preliminaries: general spin systems and bicliques

Let $q\geq 2$ be an integer. A general $q$-spin system
$(\mathbf{B},\boldsymbol{\lambda})$ consists of a symmetric interaction matrix
$\mathbf{B}=\\{B_{ij}\\}_{i,j\in[q]}$, whose entries are between 0 and 1, and
an activity vector $\boldsymbol{\lambda}=\\{\lambda_{i}\\}_{i\in[q]}$ with
strictly positive entries which are $\leq 1$. Note, that up to normalising, we
may assume that $\mathbf{B}$ and $\boldsymbol{\lambda}$ have each at least one
entry equal to 1.

For a graph $G=(V,E)$, an assignment $\sigma:V\rightarrow[q]$ has weight
$w_{G}(\sigma)=\prod_{(u,v)\in E}B_{\sigma(u),\sigma(v)}$. The Gibbs
distribution is given by $\mu_{G}(\sigma)=w_{G}(\sigma)/Z_{G}$, where
$Z_{G}=\sum_{\sigma:V\rightarrow[q]}w_{G}(\sigma)$ is the partition function.
We let $\Sigma_{G}$ be the set of all spin assignments. For a spin system on a
bipartite graph $G$, the following notion of _bicliques_ is relevant [14, 21,
13, 17].

######  Definition 4 (Biclique).

For a $q$-spin system with interaction matrix $\mathbf{B}$, we say that a pair
$(S,T)$ where $S,T\subseteq[q]$ is a _biclique_ if $B_{ij}=1$ for all $i\in
S,j\in T$. A biclique $(S,T)$ is _maximal_ if there is _no_ other biclique
$(S^{\prime},T^{\prime})\neq(S,T)$ satisfying $S\subseteq
S^{\prime}\subseteq[q]$ and $T\subseteq T^{\prime}\subseteq[q]$.

Note that bicliques are defined using only the interaction matrix $\mathbf{B}$
and do not depend on $\boldsymbol{\lambda}$.

######  Example 5.

For the $q$-colorings model, we have that $\mathbf{B}$ is the $q\times q$
matrix with all ones except on the diagonal where the entries are zero (and
$\boldsymbol{\lambda}$ is the all-ones vector). The bicliques $(S,T)$ are
given by pairs of disjoint sets $S,T\subseteq[q]$, whereas maximal bicliques
by pairs of $S,T\subseteq[1]$ that form a partition of $[q]$. For the hard-
core model, we have $\mathbf{B}=\big{[}\begin{smallmatrix}1&1\\\
1&0\end{smallmatrix}\big{]}$ and
$\boldsymbol{\lambda}=\big{[}\begin{smallmatrix}1\\\
\lambda\end{smallmatrix}\big{]}$. Indexing the rows/columns of $\mathbf{B}$
with $\\{0,1\\}$ (instead of $\\{1,2\\}$), the bicliques are
$\\{(0,0),(0,1),(1,0),(0,01),(01,0)\\}$ and the maximal bicliques are
$\\{(0,01),(01,0)\\}$.

###  2.2 Our approach: phase vectors and phase maximality

Let $(\mathbf{B},\boldsymbol{\lambda})$ be an arbitrary spin system and $G$ be
a $\Delta$-regular bipartite graph, whose vertex set $V$ is partitioned as
$(L,R)$ with $|L|=|R|=n$. Our approach to obtain approximation algorithms is
to consider the likely frequencies of the spins on each side of the graph in
the Gibbs distribution of $G$. Adapting methods from [14, 21], we show that we
can obtain efficient approximation schemes for those spin systems where the
“likely” frequency vectors are captured by maximal bicliques $(S,T)$, see the
upcoming Definition 7. The main new ingredient in our work is to give a tight
method to study when this condition is satisfied for general spin systems,
which ultimately yields Theorems 1 and 2 as special cases.

To formalise the above, for $q$-dimensional probability vectors
$\boldsymbol{\alpha}=\\{\alpha_{i}\\}_{i\in[q]},\boldsymbol{\beta}=\\{\beta_{i}\\}_{i\in[q]}$,
we let

$\Sigma^{\boldsymbol{\alpha},\boldsymbol{\beta}}_{G}=\\{\sigma:V\rightarrow[q]\,\big{|}\,|\sigma^{-1}(i)\cap
L|=n\alpha_{i},|\sigma^{-1}(i)\cap R|=n\beta_{i}\\}$ (1)

be the set of spin assignments where exactly $n\alpha_{i},n\beta_{i}$ vertices
are assigned the spin $i\in[q]$ on $L,R$, respectively. Denote by
$Z_{G}^{\boldsymbol{\alpha},\boldsymbol{\beta}}$ the contribution to the
partition function from configurations in
$\Sigma^{\boldsymbol{\alpha},\boldsymbol{\beta}}_{G}$, i.e.,
$Z_{G}^{\boldsymbol{\alpha},\boldsymbol{\beta}}=\sum_{\sigma\in\Sigma^{\boldsymbol{\alpha},\boldsymbol{\beta}}_{G}}w_{G}(\sigma)$.
We will be interested in those pairs
$(\boldsymbol{\alpha},\boldsymbol{\beta})$ that contribute significantly to
the partition function, as detailed below.

######  Definition 6 (Phase vectors).

Let $\eta>0$. For a $q$-spin system on an $n$-vertex regular bipartite graph
$G$, we say that a pair $(\boldsymbol{\alpha},\boldsymbol{\beta})$ of
$q$-dimensional probability vectors is an $\eta$-phase vector of $G$ if
$Z_{G}^{\boldsymbol{\alpha},\boldsymbol{\beta}}/Z_{G}\geq\mathrm{e}^{-\eta
n}$.

Understanding the phase vectors is in general a hard task. For random
bipartite regular graphs, these have been identified to lie among the set of
fixpoints $(\mathbf{r},\mathbf{c})$ of the following so-called tree recursions
on the $\Delta$-regular tree [15]:

$r_{i}\propto\lambda_{i}\left(\mbox{$\sum_{j\in[q]}$}B_{ij}c_{j}\right)^{\Delta-1}\mbox{
for $i\in[q]$};\qquad
c_{j}\propto\lambda_{j}\left(\mbox{$\sum_{i\in[q]}$}B_{ij}r_{i}\right)^{\Delta-1}\mbox{
for $j\in[q]$}.$ (2)

The underpinning principle here leading to this correspondence is that the
neighbourhood structure of a random $\Delta$-regular bipartite graph is
similar to a $\Delta$-regular tree. Nevertheless, identifying the actual phase
vectors, even among the finite-set of fixpoints in (2), has turned out to be
rather challenging. Even in the canonical case of $q$-colorings, the current
best known analysis works for even $q$ and is a result of technically intense
arguments.

Before looking into this in more detail, we first explain how to convert the
information about phase vectors into algorithms. Adapting methods from [14,
21], we show that this is feasible when the phase vectors correspond to
maximal bicliques. More precisely, for a non-empty set $S\subseteq[q]$, define
the $q$-dimensional probability vector $\mathbf{g}_{S}$ whose $i$-th entry is
given by $\frac{\lambda_{i}}{\sum_{j\in S}\lambda_{j}}$ for $i\in S$, and 0
otherwise. The following notion of “phase maximality” will be important in
what follows.

######  Definition 7 (Phase Maximality).

Let $(\mathbf{B},\boldsymbol{\lambda})$ be a $q$-spin system and $\Delta\geq
3$. For $\rho>0$ and a set of maximal bicliques $\mathcal{B}_{\Delta}$, we say
that the spin system is $\rho$-maximal with respect to $\mathcal{B}_{\Delta}$
if there is $\eta>0$ such that, for almost all $\Delta$-regular bipartite
graphs, every $\eta$-phase vector $(\boldsymbol{\alpha},\boldsymbol{\beta})$
satisfies
$\left\lVert(\boldsymbol{\alpha},\boldsymbol{\beta})-(\mathbf{g}_{S},\mathbf{g}_{T})\right\rVert_{\infty}\leq\rho$
for some maximal biclique $(S,T)\in\mathcal{B}_{\Delta}$.

The key new ingredient to prove Theorems 1 and 2 is to establish maximality
for the colorings and hard-core models in the corresponding parameter regimes,
as detailed in the following theorems.

######  Lemma 8.

For even $q\geq 4$ and $\Delta\geq 8q\log\Delta$, the $q$-colorings model is
$\tfrac{1}{12\Delta q}$-maximal with respect to the set of bicliques
$\mathcal{B}_{\Delta}=\\{(S,[q]\backslash S)\,\big{|}\,|S|=\frac{q}{2}\\}$.

######  Lemma 9.

For $\Delta\geq 50$ and $\lambda\geq\tfrac{50}{\Delta}$, the hard-core model
with fugacity $\lambda$ is $\tfrac{1}{24\Delta}$-maximal with respect to the
set of bicliques $\mathcal{B}_{\Delta}=\\{(0,01),(01,0)\\}$.

Previous approaches in [21, 14, 22] to establish the analogues of Lemmas 8 and
9 used expansion properties of random $\Delta$-regular bipartite graphs which
do not however give tight results in terms of the range of the parameters that
they apply. Instead, we follow a more direct analytical approach, using the
tree-recursions view mentioned in (2), further details are given in Section 3
with the final technical bounds obtained in Section 5. These more precise
bounds allow us to push significantly further the applicability of the polymer
method, see also the beginning of Section 4 for further explanation.

Indeed, we show that $\rho$-maximality yields approximation algorithms on
random $\Delta$-regular bipartite graphs, provided that $\rho$ is sufficiently
small and that the weight of configurations corresponding to maximal bicliques
is sufficiently big relatively to other type of configurations. To capture the
latter condition, recall that the entries of $\mathbf{B},\boldsymbol{\lambda}$
are between 0 and 1, and each of them includes at least one entry equal to 1.
We say that $\mathbf{B}$ is a $\delta$-matrix for some $\delta\in[0,1)$ if the
second largest entry of $\mathbf{B}$ is $\leq\delta$, and we denote by
$\min(\boldsymbol{\lambda})$ the minimum entry in $\boldsymbol{\lambda}$ (note
that this is strictly bigger than 0). By applying the polymer method
appropriately (inspired by [14]), we show the following in Section 4.

######  Lemma 10.

Let $(\mathbf{B},\boldsymbol{\lambda})$ be a $q$-spin system, $\Delta\geq 3$
be an integer, and $\rho=\tfrac{1}{12\Delta q}$. Suppose further that
$\mathbf{B}$ is a $\delta$-matrix for some $\delta\in[0,1)$ and that
$\Delta(1-\delta)\min(\boldsymbol{\lambda})\geq
7q\big{(}5+\log\tfrac{(q-1)\Delta^{3}}{\min(\boldsymbol{\lambda})}\big{)}$.

If the spin system is $\rho$-maximal, then there is an $\mathsf{FPRAS}$ for
the partition function for almost all $\Delta$-regular bipartite graphs. In
fact, for almost all $\Delta$-regular bipartite graphs, for
$\epsilon=\exp(-\Omega(n))$, the algorithm produces an $\epsilon$-estimate for
the partition function and an $\epsilon$-sample from the Gibbs distribution in
time $O\big{(}(\tfrac{n}{\epsilon})^{2}(\log\tfrac{n}{\epsilon})^{3}\big{)}$.

Using the above ingredients, we can prove our main Theorems 1 and 2.

###### Proof of Theorems 1 and 2.

We first prove the result for colorings, Theorem 1. We just need to combine
Lemmas 8 and 10. In the setting of Lemma 10 and Example 5, we have that the
interaction matrix for colorings is a $\delta$-matrix for $\delta=0$ and
$\min(\boldsymbol{\lambda})=1$. Hence, for $\Delta\geq 100q\log q$, we have
that $\Delta(1-\delta)\min(\boldsymbol{\lambda})\geq
7q\big{(}5+\log\tfrac{(q-1)\Delta^{3}}{\min(\boldsymbol{\lambda})}\big{)}$ as
needed. Moreover, Lemma 8 establishes the required $\rho$-maximality that is
further needed. Therefore, the conclusion of Lemma 10 applies and we obtain
the Theorem 1.

The proof for independent sets, Theorem 2, is analogous, by now combining
Lemmas 9 and 10. We may assume that $\lambda<1$, otherwise the result follows
from the FPRAS for $\Delta\geq 53$ in [22, Theorem 1]. In the setting of
Example 5, we have that $q=2$, $\delta=0$ and
$\min(\boldsymbol{\lambda})=\lambda$. Then, for
$\lambda>100\tfrac{\log\Delta}{\Delta}$, we have that
$\Delta(1-\delta)\min(\boldsymbol{\lambda})\geq
7q\big{(}5+\log\tfrac{(q-1)\Delta^{3}}{\min(\boldsymbol{\lambda})}\big{)}$,
and the result follows analogously to above. ∎

Finally, as mentioned in the introduction, we give evidence that the bounds on
$q$ in Theorem 1 capture the limit of the polymer method for colorings, by
showing that maximality fails when we go beyond the relevant range (note, some
form of maximality is either implicitly or explicitly shown in all previous
works on the problems).

######  Lemma 11.

For all even $q\geq 4$ and $\Delta=O(q\log q)$, for the $q$-colorings model,
$O(\tfrac{1}{\Delta q})$-maximality fails with respect to any set of bicliques
on almost all $\Delta$-regular bipartite graphs.

We note that Lemma 11 does not exclude the possibility of some exotic polymer
model that can perhaps break the barrier therein. It does show however that
the current approach cannot go substantially beyond the guarantee in Theorem
1, and at the very least some major refinement of the framework will be
needed. We conjecture that a similar barrier applies for the result of Theorem
2, though here the bottleneck is in Lemma 10. More precisely, for
$\lambda=O(\tfrac{\log\Delta}{\Delta})$ in the non-uniqueness region, polymers
can be of size roughly $n^{\Omega(1)}$, which is in contrast to what happens
when the polymer method applies (where the size of polymers turns out to be
logarithmic in $n$).

##  3 Phase vectors on random bipartite regular graphs

Let $(\mathbf{B},\boldsymbol{\lambda})$ be a $q$-spin system. In this section,
we use results from [15] to pinpoint the phase vectors on random
$\Delta$-regular bipartite graphs, and give a sufficient condition to conclude
maximality (Corollary 14). We will invoke this in Section 5 to prove Lemmas 8
and 9.

For $q$-dimensional probability vectors $\mathbf{r},\mathbf{c}$, we will
consider the function

$\Phi_{\mathbf{B},\boldsymbol{\lambda},\Delta}(\mathbf{r},\mathbf{c})=\frac{\mathbf{r}^{\intercal}\mathbf{B}\mathbf{c}}{\|\boldsymbol{\Lambda}^{-1}\mathbf{r}\|_{p}\|\boldsymbol{\Lambda}^{-1}\mathbf{c}\|_{p}},$

where $p=\tfrac{\Delta}{\Delta-1}$ and $\boldsymbol{\Lambda}$ is the $q\times
q$ diagonal matrix whose $i$-th diagonal entry is equal to
$\lambda_{i}^{1/\Delta}$. We will be interested in the maximizers
$(\mathbf{r},\mathbf{c})$ of $\Phi$.

######  Lemma 12.

Suppose that the interaction matrix $\mathbf{B}$ is ergodic, i.e., irreducible
and aperiodic. Then, the maximizers of
$\Phi_{\mathbf{B},\boldsymbol{\lambda},\Delta}(\mathbf{r},\mathbf{c})$ are
fixpoints of the tree recursions (2).

###### Proof.

The proof follows by a relatively standard Lagrange multiplier argument. The
assumption that $\mathbf{B}$ is ergodic is needed to exlcude maximizers at the
boundary, i.e., that some entry of $\mathbf{r},\mathbf{c}$ is equal to zero. A
closely related argument in the case $\boldsymbol{\lambda}=\mathbf{1}$ can be
found in [15, Lemma 4.11]. ∎

Let $\mathbf{L}$ denote the matrix
$\big{\\{}\tfrac{B_{ij}r_{i}c_{j}}{\sqrt{r_{i}^{\prime}c_{j}^{\prime}}}\big{\\}}_{i,j\in[q]}$,
where $r_{i}^{\prime}:=r_{i}(\sum_{j\in[q]}B_{ij}c_{j})$ for $i\in[q]$ and
$c_{j}^{\prime}:=c_{j}(\sum_{i\in[q]}B_{ij}r_{i})$ for $j\in[q]$. A maximiser
$(\mathbf{r},\mathbf{c})$ of $\Phi$ is called Hessian dominant in [15] if the
eigenvalues of the matrix $\mathbf{L}$ apart from the largest (which is equal
to 1) are less in absolute value than $\tfrac{1}{\Delta-1}$. Let
$\mathbf{f}:\mathbf{r}\mapsto\boldsymbol{\alpha}$ be the map given by
$\alpha_{i}=(\lambda^{-1/\Delta}_{i}r_{i}/\|\boldsymbol{\Lambda}^{-1}\mathbf{r}\|_{p})^{p}$
for $i\in[q]$.

######  Lemma 13 ([15]).

Let $\Delta\geq 3$ be an integer and consider a $q$-spin system
$(\mathbf{B},\boldsymbol{\lambda})$. Suppose that all the maximizers of
$\Phi_{\mathbf{B},\boldsymbol{\lambda},\Delta}$ are Hessian dominant. Then,
for every $\kappa>0$, there is $\eta>0$ such that for almost all
$\Delta$-regular bipartite graphs, every $\eta$-phase vector
$(\boldsymbol{\alpha},\boldsymbol{\beta})$ satisfies
$\|(\boldsymbol{\alpha},\boldsymbol{\beta})-(\boldsymbol{\alpha}^{*},\boldsymbol{\beta}^{*})\|_{\infty}\leq\kappa$,
where
$(\boldsymbol{\alpha}^{*},\boldsymbol{\beta}^{*})=(\mathbf{f}(\mathbf{r}^{*}),\mathbf{f}(\mathbf{c}^{*}))$
and $(\mathbf{r}^{*},\mathbf{c}^{*})$ is a maximizer of
$\Phi_{\mathbf{B},\boldsymbol{\lambda},\Delta}$.

###### Proof.

The lemma is proved in [15, Section 6.4.1] for
$\boldsymbol{\lambda}=\mathbf{1}$. To extend to general
$\boldsymbol{\lambda}$, consider the spin system
$(\widehat{\mathbf{B}},\widehat{\boldsymbol{\lambda}})$ where
$\widehat{\mathbf{B}}=\boldsymbol{\Lambda}\mathbf{B}\boldsymbol{\Lambda}$ and
$\widehat{\boldsymbol{\lambda}}=\mathbf{1}$. Note, on $\Delta$-regular
bipartite graphs and arbitrary $\eta>0$, an $\eta$-phase vector
$(\boldsymbol{\alpha},\boldsymbol{\beta})$ of the spin system
$(\mathbf{B},\boldsymbol{\lambda})$ is also an $\eta$-phase vector of the spin
system with interaction matrix $\widehat{\mathbf{B}}$ and activity vector
$\mathbf{1}$, and vice versa. Moreover, the maximizers
$(\mathbf{r}^{*},\mathbf{c}^{*})$ of
$\Phi=\Phi_{\mathbf{B},\boldsymbol{\lambda},\Delta}(\mathbf{r},\mathbf{c})$
are in 1-1 correspondence with the maximizers
$(\widehat{\mathbf{r}}^{*},\widehat{\mathbf{c}}^{*})$ of
$\widehat{\Phi}=\widehat{\Phi}_{\widehat{\mathbf{B}},\widehat{\boldsymbol{\lambda}},\Delta}$
via the relation
$(\mathbf{r}^{*},\mathbf{c}^{*})=(\boldsymbol{\Lambda}\widehat{\mathbf{r}}^{*},\boldsymbol{\Lambda}\widehat{\mathbf{c}}^{*})$.
Note also that $(\mathbf{r}^{*},\mathbf{c}^{*})$ is Hessian dominant for
$\Phi$ iff $(\widehat{\mathbf{r}}^{*},\widehat{\mathbf{c}}^{*})$ is Hessian
dominant for $\widehat{\Phi}$, therefore establishing the result for general
$\boldsymbol{\lambda}$. ∎

Using Lemma 13, we obtain the following using the definition of maximality
(cf. Definition 7).

######  Corollary 14.

Let $(\mathbf{B},\boldsymbol{\lambda})$ be a $q$-spin system and $\Delta\geq
3$ be an integer. Suppose that there is a set of maximal bicliques
$\mathcal{B}_{\Delta}$ such that all maximizers
$(\mathbf{r}^{*},\mathbf{c}^{*})$ of
$\Phi_{\mathbf{B},\boldsymbol{\lambda},\Delta}$ are Hessian dominant and
satisfy
$\|(\boldsymbol{\alpha}^{*},\boldsymbol{\beta}^{*})-(\mathbf{g}_{S},\mathbf{g}_{T})\|_{\infty}\leq\tfrac{1}{15\Delta
q}$ for some maximal biclique $(S,T)\in\mathcal{B}_{\Delta}$, where
$(\boldsymbol{\alpha}^{*},\boldsymbol{\beta}^{*})=(\mathbf{f}(\mathbf{r}^{*}),\mathbf{f}(\mathbf{c}^{*}))$.
Then, the spin system is $\tfrac{1}{12\Delta q}$-maximal with respect to
$\mathcal{B}_{\Delta}$.

##  4 Algorithms from maximality: Proof of Lemma 10

Let $\Delta\geq 3$ be an integer, and $(\mathbf{B},\boldsymbol{\lambda})$ be a
$q$-spin system, which is $\rho$-maximal for $\rho=\tfrac{1}{12\Delta q}$.
Consider also a bipartite graph $G=(V,E)$ with vertex bipartition $(L,R)$ and
$|L|=|R|=n$. The following expansion property of sets $U\subseteq V$ in random
regular bipartite graphs relaxes the previous expansion properties that were
used in [21, 22] which needed to consider bigger sets $U$; instead, whenever
the spin system is $\tfrac{1}{12\Delta q}$-maximal, we only need to consider
sets $U$ with size roughly $\tfrac{1}{\Delta}|V|$, whose expansion is
$\Omega(\Delta)$. For a set $U\subseteq V$, we use $\partial U$ to denote the
vertices in $G$ which have a neighbor in $U$ but do not belong to $U$, and by
$U^{+}$ the set $U\cup\partial U$.

######  Lemma 15.

Let $\Delta\geq 3$ be an integer. For almost all $\Delta$-regular bipartite
graphs $G=(V,E)$ with bipartition $(L,R)$, the following expansion properties
hold:

  1. 1.

every set $U\subseteq V$ with $|U\cap L|\leq\tfrac{1}{3\Delta}|L|$ and $|U\cap
R|\leq\tfrac{1}{3\Delta}|R|$ satisfies $|U^{+}|\geq\tfrac{\Delta-1}{2}|U|$.

  2. 2.

every set $U\subseteq V$ with $|U\cap L|\leq\tfrac{1}{6\Delta}|L|$ and $|U\cap
R|\leq\tfrac{1}{6\Delta}|R|$ satisfies $|\partial U|\geq\tfrac{\Delta}{7}|U|$.

###### Proof.

For the first item, consider a subset $U\subseteq V$ with $|U\cap
L|\leq\tfrac{1}{3\Delta}|L|$ and $|U\cap R|\leq\tfrac{1}{3\Delta}|R|$. We will
show that

$|\partial(U\cap L)|\geq\tfrac{\Delta-1}{2}|U\cap L|\mbox{ and
}|\partial(U\cap R)|\geq\tfrac{\Delta-1}{2}|U\cap R|.$ (3)

From this, we obtain that $|U^{+}|=|U\cup\partial U|\geq|\partial(U\cap
L)|+|\partial(U\cap R)|\geq\tfrac{\Delta-1}{2}|S|$. To verify (3), we use a
sufficient condition due to Bassalygo [2], see also [21, Theorem 22]. Namely,
for $a=\tfrac{1}{3\Delta}$, $b=\tfrac{\Delta-1}{2}$ and
$H(x)=-x\log_{2}(x)-(1-x)\log_{2}(1-x)$, we check that
$\Delta>\frac{H(a)+H(ab)}{H(a)-abH(1/b)}$, which indeed holds for all
$\Delta\geq 3$.

The proof of the second item is analogous. Consider a subset $U\subseteq V$
with $|U\cap L|\leq\tfrac{1}{6\Delta}|L|$ and $|U\cap
R|\leq\tfrac{1}{6\Delta}|R|$. We will show that

$|\partial(U\cap L)|\geq\big{(}\tfrac{\Delta}{7}+1\big{)}|U\cap L|\mbox{ and
}|\partial(U\cap R)|\geq\big{(}\tfrac{\Delta}{7}+1\big{)}|U\cap R|.$ (4)

From this, we obtain that $|\partial U|\geq|\partial(U\cap L)|+|\partial(U\cap
R)|-|U|\geq\tfrac{\Delta}{7}|U|$. The proof of (4) is by verifying again the
same condition as above, now for the values $a=\tfrac{1}{6\Delta}$ and
$b=\tfrac{\Delta}{7}+1$. ∎

Following [14], we will define a polymer model corresponding to a biclique
$(S,T)$ of the spin system. Let $G^{3}$ be the graph on vertex set $V$ where
two vertices $u,v$ are adjacent iff $\mathrm{dist}(u,v)\leq 2$. A subset
$U\subseteq V$ of vertices is said to be $G^{3}$-connected if the induced
subgraph $G^{3}[U]$ is connected. A polymer
$\gamma=(V_{\gamma},\sigma_{\gamma})$ consists of a subset of vertices of $G$,
$V_{\gamma}$, which is $G^{3}$ connected, and a spin assignment on
$V_{\gamma}$, $\sigma_{\gamma}:V_{\gamma}\rightarrow[q]$, such that every
vertex in $V_{\gamma}\cap L$ gets a spin in $[q]\backslash S$ and every vertex
in $V_{\gamma}\cap R$ gets a spin in $[q]\backslash T$. Two polymers
$\gamma_{1},\gamma_{2}$ are compatible (written as $\gamma_{1}\sim\gamma_{2}$)
if and only if $\mathrm{dist}(\gamma_{1},\gamma_{2})>3$, i.e.,
$\gamma_{1}\cup\gamma_{2}$ is not $G^{3}$-connected.

The size of a polymer $\gamma$, denoted by $|\gamma|$, is the number of
vertices it contains. We use $E_{\gamma}$ to denote the edges of $G$ whose
both endpoints lie in $\gamma$, $\partial V_{\gamma}$ to denote the vertices
in $G$ which have a neighbor in $V_{\gamma}$ but do not belong to
$V_{\gamma}$, and by $V_{\gamma}^{+}$ the set $V_{\gamma}\cup\partial
V_{\gamma}$. For a polymer $\gamma$, the weight $w^{S,T}_{G}(\gamma)$ of the
polymer is given by

$w^{S,T}_{G}(\gamma)=\frac{\prod_{u\in
V_{\gamma}}\lambda_{\sigma_{\gamma}(u)}\prod_{(u,v)\in
E_{\gamma}}B_{\sigma_{\gamma}(u),\sigma_{\gamma}(v)}\prod_{u\in\partial
V_{\gamma}}F_{u}}{\big{(}\sum_{i\in S}\lambda_{i})^{|V_{\gamma}^{+}\cap
L|}\big{(}\sum_{j\in T}\lambda_{j}\big{)}^{|V_{\gamma}^{+}\cap R|}},$ (5)

where

$F_{u}=\sum_{i\in S}\lambda_{i}\prod_{v\in V_{\gamma}\cap\partial
u}B_{i,\sigma_{\gamma}(v)}\mbox{ if }u\in\partial V_{\gamma}\cap L,\quad
F_{u}=\sum_{j\in T}\lambda_{j}\prod_{v\in V_{\gamma}\cap\partial
u}B_{j,\sigma_{\gamma}(v)}\mbox{ if }u\in\partial V_{\gamma}\cap R.$ (6)

Let $\mathcal{P}^{S,T}_{G}$ be the set of all polymers
$\gamma=(V_{\gamma},\sigma_{\gamma})$ with $|V_{\gamma}|\leq 2q\rho
n=\tfrac{n}{6\Delta}$. A configuration $\Gamma=(V_{\Gamma},\sigma_{\Gamma})$
of polymers is a collection of mutually compatible polymers
$\gamma_{1},\ldots,\gamma_{k}\in\mathcal{P}^{S,T}_{G}$ with
$V_{\Gamma}=\cup_{t\in[k]}V_{\gamma_{t}}$ and $\sigma_{\Gamma}$ the spin
assignment on $V_{\Gamma}$ which agrees with $\sigma_{\gamma_{t}}$ on
$V_{\gamma_{t}}$ for each $t\in[k]$. Let $\Omega^{S,T}_{G}$ be the set of all
possible configurations $\Gamma$. The size of a configuration is
$|\Gamma|=\sum_{\gamma\in\Gamma}|V_{\gamma}|$.

######  Lemma 16.

Every configuration $\Gamma$ satisfies $|V_{\Gamma}|\leq 12n/\Delta$.

###### Proof.

Suppose that there exists a configuration $\Gamma$ with
$|V_{\Gamma}|>12n/\Delta$. Then, we can extract greedily disjoint
configurations $\Gamma_{1},\ldots,\Gamma_{36}\subseteq\Gamma$ (which are a
collection of polymers belonging to $\Gamma$) such that
$\tfrac{n}{6\Delta}<|\Gamma_{i}|\leq\tfrac{n}{3\Delta}$. By Lemma 15, we have
that
$|V_{\Gamma_{i}}^{+}|\geq\tfrac{\Delta-1}{2}|\Gamma_{i}|>\frac{n}{6\Delta}\tfrac{\Delta-1}{2}$
and therefore
$\sum^{36}_{t=1}|V_{\Gamma_{i}}^{+}|>\frac{6n}{\Delta}\tfrac{\Delta-1}{2}\geq
2n$. Therefore, since $G$ has $2n$ vertices, the sets
$V_{\Gamma_{1}}^{+},\ldots,V_{\Gamma_{36}}^{+}$ cannot be pairwise disjoint,
contradicting the fact that the configuration $\Gamma$ consists of pairwise
compatible polymers. ∎

The weight $w^{S,T}_{G}(\Gamma)$ of a configuration $\Gamma$ is given by the
product of the weights of the polymers that $\Gamma$ consists of. We define
the partition function of the polymer model as

$Z^{S,T}_{G}=\mbox{$\sum_{\Gamma\in\Omega^{S,T}_{G}}$}\,w^{S,T}_{G}(\Gamma),\mbox{
and its Gibbs distribution by
}\mu^{S,T}_{G}(\Gamma)=w^{S,T}_{G}(\Gamma)/Z^{S,T}_{G}\mbox{ for
$\Gamma\in\Omega^{S,T}_{G}$}.$

Finally, we let
$Z^{\mathrm{pmer}}_{G}=\sum_{(S,T)\in\mathcal{B}_{\Delta}}\,\big{(}\mbox{$\sum_{i\in
S}$}\,\lambda_{i}\big{)}^{n}\big{(}\mbox{$\sum_{j\in
T}$}\,\lambda_{j}\big{)}^{n}Z^{S,T}_{G}$.

######  Lemma 17.

Let $\Delta\geq 3$ be an integer, and $(\mathbf{B},\boldsymbol{\lambda})$ be a
$q$-spin system which is $\tfrac{1}{12\Delta q}$-maximal with respect to a set
of maximal bicliques $\mathcal{B}_{\Delta}$. Suppose further that
$\Delta\min(\boldsymbol{\lambda})\geq 15q$. Then, there is
$\epsilon=\mathrm{e}^{-\Omega(n)}$ such that, for almost all $\Delta$-regular
bipartite graphs $G$ with $n$ vertices on each part, it holds that
$(1-\epsilon)Z_{G}\leq Z^{\mathrm{pmer}}_{G}\leq(1+\epsilon)Z_{G}$.

###### Proof.

By the $\tfrac{1}{12\Delta q}$-maximality of the spin system with respect to
$\mathcal{B}_{\Delta}$ (cf. Definition 7), there is an $\eta>0$ such that for
almost all $\Delta$-regular graphs $G$, every $\eta$-phase vector
$(\boldsymbol{\alpha},\boldsymbol{\beta})$ of $G$ belongs to

$\mathcal{F}_{\Delta}:=\Big{\\{}(\boldsymbol{\alpha},\boldsymbol{\beta})\,\Big{|}\,\|(\boldsymbol{\alpha},\boldsymbol{\beta})-(\mathbf{g}_{S},\mathbf{g}_{T})\|_{\infty}\leq\tfrac{1}{12\Delta
q}\mbox{ for some maximal biclique }(S,T)\in\mathcal{B}_{\Delta}\Big{\\}}.$

Let
$\Sigma_{G}^{\max}=\\{\sigma\mid\sigma\in\Sigma^{\boldsymbol{\alpha},\boldsymbol{\beta}}_{G}\mbox{
for some }(\boldsymbol{\alpha},\boldsymbol{\beta})\in\mathcal{F}_{\Delta}\\}$
where, recall from (1), that
$\Sigma^{\boldsymbol{\alpha},\boldsymbol{\beta}}_{G}$ is the set of spin
assignments where exactly $n\alpha_{i},n\beta_{i}$ vertices are assigned the
spin $i\in[q]$ on $L,R$, respectively.

We first show the lower bound on $Z^{\mathrm{pmer}}_{G}$. Consider the polymer
model corresponding to a maximal biclique $(S,T)\in\mathcal{B}_{\Delta}$.
Every configuration $\Gamma\in\Omega^{S,T}_{G}$ maps to a set of spin
assignments

$\Sigma^{S,T}_{G}(\Gamma)=\\{\sigma:V\rightarrow[q]\mid\sigma(V_{\Gamma})=\sigma_{\Gamma},\,\sigma(L\backslash
V_{\Gamma})\subseteq S,\,\sigma(R\backslash V_{\Gamma})\subseteq T\\},$

where recall that $\sigma_{\Gamma}$ is a spin assignment on $V_{\Gamma}$ that
satisfies $\sigma_{\Gamma}(V_{\Gamma}\cap L)\subseteq[q]\backslash S$ and
$\sigma_{\Gamma}(V_{\Gamma}\cap R)\subseteq[q]\backslash T$. Therefore, for
distinct $\Gamma,\Gamma^{\prime}\in\Omega^{S,T}_{G}$ we have that the sets
$\Sigma^{S,T}_{G}(\Gamma)$ and $\Sigma^{S,T}_{G}(\Gamma^{\prime})$ are
disjoint. Let
$\Sigma^{S,T}_{G}=\bigcup_{\Gamma\in\Omega^{S,T}_{G}}\Sigma^{S,T}_{G}(\Gamma)$.
Using that configurations $\Gamma$ consist of disjoint $G^{3}$-connected sets,
we obtain that the aggregate weight
$\sum_{\sigma\in\Sigma^{S,T}_{G}(\Gamma)}w_{G}(\sigma)$ equals
$\big{(}\mbox{$\sum_{i\in S}$}\,\lambda_{i}\big{)}^{n}\big{(}\mbox{$\sum_{j\in
T}$}\,\lambda_{j}\big{)}^{n}w^{S,T}_{G}(\Gamma)$ (see for example [14, Lemma
17]), and therefore

$Z^{S,T}_{G}=\sum_{\sigma\in\Sigma^{S,T}_{G}}w_{G}(\sigma).$

Moreover, note that for $(\boldsymbol{\alpha},\boldsymbol{\beta})$ with
$\|(\boldsymbol{\alpha},\boldsymbol{\beta})-(\mathbf{g}_{S},\mathbf{g}_{T})\|_{\infty}\leq\tfrac{1}{12\Delta
q}$, the number of vertices in $L$ that do not get a spin in $S$ is at most
$\tfrac{n}{12\Delta}$, and similarly for vertices in $R$ that do not get a
spin in $T$, for a total of $\tfrac{n}{6\Delta}$ vertices, giving that
$\Sigma^{\boldsymbol{\alpha},\boldsymbol{\beta}}_{G}\subseteq\Sigma^{S,T}_{G}$.
Observe now that every
$(\boldsymbol{\alpha},\boldsymbol{\beta})\notin\mathcal{F}_{\Delta}$ is not an
$\eta$-phase vector and therefore
$Z^{\boldsymbol{\alpha},\boldsymbol{\beta}}_{G}\leq\mathrm{e}^{-\eta n}Z_{G}$.
There are at most $n^{2q}$ such pairs with
$n\boldsymbol{\alpha},n\boldsymbol{\beta}\in\mathbb{Z}^{q}$ and therefore,
combining the above, it follows that

$Z_{G}-Z^{\mathrm{pmer}}_{G}\leq\sum_{(\boldsymbol{\alpha},\boldsymbol{\beta})\notin\mathcal{F}_{\Delta}}Z^{\boldsymbol{\alpha},\boldsymbol{\beta}}_{G}\leq
n^{2q}\mathrm{e}^{-\eta n}Z_{G}\leq\mathrm{e}^{-\Omega(n)}Z_{G},$

showing that $Z^{\mathrm{pmer}}_{G}\geq(1-\mathrm{e}^{-\Omega(n)})Z_{G}$.

We next show the upper bound on $Z^{\mathrm{pmer}}_{G}$. Consider
$\Sigma^{\mathrm{overlap}}_{G}=\bigcup_{(S,T)\neq(S^{\prime},T^{\prime})\in\mathcal{B}_{\Delta}}(\Sigma^{S,T}_{G}\cap\Sigma^{S^{\prime},T^{\prime}}_{G})$.
We will show shortly that
$\Sigma^{\mathrm{overlap}}_{G}\subseteq\Sigma_{G}\backslash\Sigma_{G}^{\max}$.
Assuming this for the moment, we conclude the proof by noting first that for
$(\boldsymbol{\alpha},\boldsymbol{\beta})$ which is not an $\eta$-phase vector
it holds that
$Z^{\boldsymbol{\alpha},\boldsymbol{\beta}}_{G}/Z_{G}<\mathrm{e}^{-\eta n}$.
Therefore we obtain that the aggregate weight of spin assignments in
$\Sigma^{\mathrm{overlap}}_{G}$ is at most $n^{2q}\mathrm{e}^{-\eta
n}Z_{G}=\mathrm{e}^{-\Omega(n)}Z_{G}$, yielding that
$Z_{G}\geq(1-\mathrm{e}^{-\Omega(n)})Z^{\mathrm{pmer}}_{G}$.

It remains to prove that
$\Sigma^{\mathrm{overlap}}_{G}\subseteq\Sigma_{G}\backslash\Sigma_{G}^{\max}$.
For the sake of contradiction, suppose otherwise. Then there exists a spin
assigment $\sigma$, distinct bicliques
$(S,T),(S^{\prime},T^{\prime})\in\mathcal{B}_{\Delta}$, and a biclique
$(S^{*},T^{*})\in\mathcal{B}_{\Delta}$ such that
$\sigma\in\Sigma^{S,T}_{G}\cap\Sigma^{S^{\prime},T^{\prime}}_{G}$ and
$\sigma\in\Sigma^{\boldsymbol{\alpha},\boldsymbol{\beta}}_{G}$ for some
$\|(\boldsymbol{\alpha},\boldsymbol{\beta})-(\mathbf{g}_{S^{*}},\mathbf{g}_{T^{*}})\|_{\infty}\leq\tfrac{1}{12\Delta
q}$. Since $(S,T)$ and $(S^{\prime},T^{\prime})$ are distinct and maximal, we
may assume w.l.o.g. have that $S\neq S^{*}$ and $T\neq T^{*}$. Since
$(S^{*},T^{*})$ is maximal, it cannot be the case that $S^{*}\subseteq S$ and
$T^{*}\subseteq T$, so assume w.l.o.g. that $i\in S^{*}\backslash S$. Let
$n_{i}$ be the vertices in $L$ that have the spin $i$ under $\sigma$. Since
$\sigma\in\Sigma^{S,T}_{G}(\Gamma)$ for some $\Gamma\in\Omega^{S,T}_{G}$ and
$i\notin S$, from Lemma 16 we have that $n_{i}\leq|V_{\Gamma}|\leq
12n/\Delta$. Then, using the assumption $\Delta\min(\boldsymbol{\lambda})\geq
15q$ and the fact that the entries of $\boldsymbol{\lambda}$ are $\leq 1$, we
have the crude bound $\frac{\lambda_{i}}{\sum_{i^{\prime}\in
S^{*}}\lambda_{i^{\prime}}}\geq\min(\boldsymbol{\lambda})/q\geq 15/\Delta$,
and therefore $|\frac{\lambda_{i}}{\sum_{i^{\prime}\in
S^{*}}\lambda_{i^{\prime}}}-\tfrac{n_{i}}{n}|\geq\tfrac{3}{\Delta}>\tfrac{1}{12\Delta
q}$ contradicting the choice of $(S^{*},T^{*})$. ∎

We are now ready to prove Lemma 10, which we restate here for convenience. The
proof uses the Markov chain approach for studying polymer models in [8], as
employed for general spin systems in [14].

######  Lemma 10.

Let $(\mathbf{B},\boldsymbol{\lambda})$ be a $q$-spin system, $\Delta\geq 3$
be an integer, and $\rho=\tfrac{1}{12\Delta q}$. Suppose further that
$\mathbf{B}$ is a $\delta$-matrix for some $\delta\in[0,1)$ and that
$\Delta(1-\delta)\min(\boldsymbol{\lambda})\geq
7q\big{(}5+\log\tfrac{(q-1)\Delta^{3}}{\min(\boldsymbol{\lambda})}\big{)}$.

If the spin system is $\rho$-maximal, then there is an $\mathsf{FPRAS}$ for
the partition function for almost all $\Delta$-regular bipartite graphs. In
fact, for almost all $\Delta$-regular bipartite graphs, for
$\epsilon=\exp(-\Omega(n))$, the algorithm produces an $\epsilon$-estimate for
the partition function and an $\epsilon$-sample from the Gibbs distribution in
time $O\big{(}(\tfrac{n}{\epsilon})^{2}(\log\tfrac{n}{\epsilon})^{3}\big{)}$.

###### Proof.

The main ingredient that we need to check is the so-called polymer sampling
condition [8, Definition 4] for each polymer model defined by bicliques
$(S,T)\in\mathcal{B}_{\Delta}$; this gives an $\epsilon$-counting algorithm
for $Z^{S,T}_{G}$ and an $\epsilon$-sampling algorithm for $\mu^{S,T}_{G}$
with the desired guarantees. The estimates in Lemma 17 then yield that these
algorithms can be extended to algorithms for $Z_{G}$, by the argument in [14,
Proof of Theorem 3].

The polymer sampling condition captures that the weight of the polymers as a
function of their size decays exponentially relatively to the growth rate of
the number of polymers (containing a vertex); in this case, since we are
working with $G^{3}$ whose degree is bounded by $\Delta^{3}$, the condition we
need to check, cf. [8, Definition 4], is that
$w^{S,T}_{G}\leq\mathrm{e}^{-\tau|\gamma|}$ for some constant $\tau\geq
5+3\log((q-1)\Delta^{3})$.

Let $\gamma=(V_{\gamma},\sigma_{\gamma})\in\mathcal{P}^{S,T}_{G}$. Since the
entries of $\mathbf{B},\boldsymbol{\lambda}$ are $\leq 1$, we have from (5)
that

$w^{S,T}_{G}(\gamma)\leq\frac{\prod_{u\in\partial
V_{\gamma}}F_{u}}{\big{(}\sum_{i\in S}\lambda_{i})^{|V_{\gamma}^{+}\cap
L|}\big{(}\sum_{j\in T}\lambda_{j}\big{)}^{|V_{\gamma}^{+}\cap R|}},$

Now for $u\in\partial V_{\gamma}\cap L$, recall that $F_{u}=\sum_{i\in
S}\lambda_{i}\prod_{v\in V_{\gamma}\cap\partial u}B_{i,\sigma_{\gamma}(v)}$.
We have that there exist $i\in S$ and $v\in V_{\gamma}\cap\partial u$ such
that $B_{i,\sigma_{\gamma}(v)}\leq\delta$; otherwise, since $\mathbf{B}$ is a
$\delta$-matrix, we would have that $B_{i,\sigma_{\gamma}(v)}=1$ for all $i\in
S$, and therefore $(S,T\cup\\{\sigma_{\gamma}(v)\\})$ would be a biclique,
contradicting the maximality of $(S,T)$ since $\sigma_{\gamma}(v)\notin T$ (by
the definition of $\mathcal{P}^{S,T}_{G}$). We therefore obtain that
$F_{u}\leq\sum_{i\in S}\lambda_{i}-(1-\delta)\min(\boldsymbol{\lambda})$.
Similarly, for $u\in\partial V_{\gamma}\cap R$, we have that
$F_{u}\leq\sum_{j\in T}\lambda_{j}-(1-\delta)\min(\boldsymbol{\lambda})$.
Using the crude bounds $\min(\boldsymbol{\lambda})\leq\sum_{i\in
S}\lambda_{i},\sum_{j\in T}\lambda_{j}\leq q$, we obtain that

$w^{S,T}_{G}(\gamma)\leq(\min(\boldsymbol{\lambda}))^{-|V_{\gamma}|}\Big{(}1-\frac{(1-\delta)\min(\boldsymbol{\lambda})}{q}\Big{)}^{-|\partial
V_{\gamma}|}.$

By the $\rho$-extremality assumption (or, more precisely, by the definition of
the set of polymers $\mathcal{P}^{S,T}_{G}$), we have that $|V_{\gamma}|\leq
2q\rho n\leq\tfrac{n}{6\Delta}$, and therefore, by Lemma 15, $|\partial
V_{\gamma}|\geq\tfrac{\Delta}{7}V_{\gamma}$. We therefore have that

$w^{S,T}_{G}(\gamma)\leq\mathrm{e}^{-\big{(}\log(\min{\boldsymbol{\lambda}})+\tfrac{\Delta(1-\delta)\min(\boldsymbol{\lambda})}{7q}\big{)}|V_{\gamma}|}$

Thus the polymer sampling condition is satisfied as long as
$\tfrac{\Delta(1-\delta)\min(\boldsymbol{\lambda})}{7q}+\log(\min(\boldsymbol{\lambda}))\geq
5+3\log((q-1)\Delta^{3})$, which gives the desired conclusion. ∎

##  5 Establishing phase maximality

In this section we establish phase maximality for colorings and hard-core
model. In particular, we prove Lemmas 8 and 9 from Section 2.2. Recall that
the tree-recursion on the $\Delta$-regular tree for a general $q$-spin system
with interaction matrix $\mathbf{B}$ and activity vector
$\boldsymbol{\lambda}$ is given by

$r_{i}\propto\lambda_{i}\left(\mbox{$\sum_{j\in[q]}$}B_{ij}c_{j}\right)^{\Delta-1}\mbox{
for $i\in[q]$};\qquad
c_{j}\propto\lambda_{j}\left(\mbox{$\sum_{i\in[q]}$}B_{ij}r_{i}\right)^{\Delta-1},\mbox{
for $j\in[q]$}.$ (2)

For the colorings and hard-core models, Lemma 12 shows that the fixpoints of
(2) include all maximizers of the function

$\Phi_{\mathbf{B},\boldsymbol{\lambda},\Delta}(\mathbf{r},\mathbf{c})=\frac{\mathbf{r}^{\intercal}\mathbf{B}\mathbf{c}}{\|\boldsymbol{\Lambda}^{-1}\mathbf{r}\|_{p}\|\boldsymbol{\Lambda}^{-1}\mathbf{c}\|_{p}}$

where $p=\frac{\Delta}{\Delta-1}$ and $\boldsymbol{\Lambda}$ is the diagonal
matrix whose $i$-th diagonal entry is $\lambda_{i}^{1/\Delta}$. Finally,
Corollary 14 implies that, to show $\tfrac{1}{12\Delta q}$-maximality for a
set of maximal bicliques $\mathcal{B}_{\Delta}$, it is enough to show that all
maximizers $(\mathbf{r}^{*},\mathbf{c}^{*})$ of
$\Phi_{\mathbf{B},\boldsymbol{\lambda},\Delta}$ are Hessian dominant and
satisfy that
$\|(\boldsymbol{\alpha}^{*},\boldsymbol{\beta}^{*})-(\mathbf{g}_{S},\mathbf{g}_{T})\|_{\infty}\leq\tfrac{1}{15\Delta
q}$ for some $(S,T)\in\mathcal{B}_{\Delta}$, where
$(\boldsymbol{\alpha}^{*},\boldsymbol{\beta}^{*})=(\mathbf{f}(\mathbf{r}^{*}),\mathbf{f}(\mathbf{c}^{*}))$
is given by

$\alpha^{*}_{i}=\frac{(\lambda_{i}^{-1/\Delta}r^{*}_{i})^{p}}{\|\boldsymbol{\Lambda}^{-1}\mathbf{r}^{*}\|_{p}^{p}}\quad\text{and}\quad\beta^{*}_{i}=\frac{(\lambda_{i}^{-1/\Delta}c^{*}_{i})^{p}}{\|\boldsymbol{\Lambda}^{-1}\mathbf{c}^{*}\|_{p}^{p}}\quad\text{for~{}}i\in[q].$

###  5.1 Phase maximality for colorings

In this subsection we prove Lemma 8 by showing phase maximality for colorings.

Let $q,\Delta\geq 3$ be integers and let $d=\Delta-1$. For $q$-colorings,
using the correspondence in Example 5, the tree-recursion can be written as:

$r_{i}=\frac{(1-c_{i})^{\Delta-1}}{\sum_{j\in[q]}(1-c_{j})^{\Delta-1}},\quad
c_{i}=\frac{(1-r_{i})^{\Delta-1}}{\sum_{j\in[q]}(1-r_{j})^{\Delta-1}}\quad\mbox{for~{}}i\in[q].$
(7)

Note that $(\mathbf{g}_{[q]},\mathbf{g}_{[q]})$ is a trivial solution to (7).
The following lemma summarizes results from [15, Section 7] and describes the
nontrivial fixpoints of the tree recursion (7) when $q\geq 4$ is an even
integer in the non-uniqueness region $q<\Delta$.

######  Lemma 18 ([15]).

Suppose that $q\geq 4$ is even and $\Delta>q$. Then there is a one-to-one
correspondence between all maximizers of $\Phi_{\mathbf{B},\mathbf{1},\Delta}$
and all bicliques in $\mathcal{B}_{\Delta}=\\{(S,[q]\backslash
S)\,\big{|}\,|S|=\frac{q}{2}\\}$: there exists $a=a(\Delta,q)$,
$b=b(\Delta,q)$ satisfying $0<b<a<\frac{2}{q}$ and $a+b=\frac{2}{q}$, such
that every biclique $(S,[q]\setminus S)\in\mathcal{B}_{\Delta}$ corresponds to
a maximizer $(\mathbf{r}^{*},\mathbf{c}^{*})$ of the form

$r^{*}_{i}=\left\\{\begin{aligned} a,\quad&i\in S;\\\ b,\quad&i\in[q]\setminus
S,\end{aligned}\right.\quad\text{and}\quad c^{*}_{i}=\left\\{\begin{aligned}
b,\quad&i\in S;\\\ a,\quad&i\in[q]\setminus S.\end{aligned}\right.$

Furthermore, all maximizers of $\Phi_{\mathbf{B},\mathbf{1},\Delta}$ are
Hessian dominant.

We now prove Lemma 8, which we restate here for convenience.

######  Lemma 8.

For even $q\geq 4$ and $\Delta\geq 8q\log\Delta$, the $q$-colorings model is
$\tfrac{1}{12\Delta q}$-maximal with respect to the set of bicliques
$\mathcal{B}_{\Delta}=\\{(S,[q]\backslash S)\,\big{|}\,|S|=\frac{q}{2}\\}$.

###### Proof.

Let $k=\frac{q}{2}$ and $d=\Delta-1$ for convenience. By Lemmas 12 and 18, for
a given biclique $(S,[q]\setminus S)\in\mathcal{B}_{\Delta}$, the
corresponding maximizer $(\mathbf{r}^{*},\mathbf{c}^{*})$ of
$\Phi_{\mathbf{B},\mathbf{1},\Delta}$ satisfies the tree-recursion (7) as
follows:

$\left\\{\begin{aligned}
a&=\frac{\left(ka+(k-1)b\right)^{d}}{k\left[\left(ka+(k-1)b\right)^{d}+\left((k-1)a+kb\right)^{d}\right]};\\\
b&=\frac{\left((k-1)a+kb\right)^{d}}{k\left[\left(ka+(k-1)b\right)^{d}+\left((k-1)a+kb\right)^{d}\right]},\end{aligned}\right.$

where $a,b$ are the constants given in Lemma 18. We are going to show that,
for sufficiently large $\Delta$, the constant $a$ is close to $\frac{2}{q}$
and the constant $b$ is close to $0$. Taking the ratio of $a$ and $b$, we get

$\frac{a}{b}=\left(\frac{ka+(k-1)b}{(k-1)a+kb}\right)^{d},\mbox{ and therefore
}h=\left(\frac{h+t}{th+1}\right)^{d}.$

where $h=\frac{a}{b}>1$ and $t=\frac{k-1}{k}=1-\frac{2}{q}$. Consider the
function $f(x)=\left(\frac{x+t}{tx+1}\right)^{d}$. Then $h$ is a fixpoint of
$f$ (i.e., $f(h)=h$). In fact, the function $f$ has three fixpoints: $x=h>1$,
$x=1$, and $x=\frac{1}{h}<1$. Let $h_{0}=\mathrm{e}^{\frac{d}{2q}}>3$ when
$d\geq 3q$. We show next that $h>h_{0}$. By considering the monotone intervals
of $f(x)-x$, it suffices to show that $f(h_{0})>h_{0}$. We then compute that

$\displaystyle\frac{1}{d}\log f(h_{0})$
$\displaystyle=\log\left(\frac{h_{0}+t}{th_{0}+1}\right)=\log\left(1+\frac{(1-t)(h_{0}-1)}{th_{0}+1}\right)$
$\displaystyle>\frac{(1-t)(h_{0}-1)}{2(th_{0}+1)}>\frac{1-t}{4}=\frac{1}{2q},$

where the first inequality follows from
$\log(1+\varepsilon)>\frac{\varepsilon}{2}$ for $\varepsilon\in(0,1]$ and the
second inequality is due to $h_{0}>3$ and $t<1$. Therefore,
$f(h_{0})>\mathrm{e}^{\frac{d}{2q}}=h_{0}$ and thus $h>h_{0}$.

Finally, notice that
$(\boldsymbol{\alpha}^{*},\boldsymbol{\beta}^{*})=(\mathbf{f}(\mathbf{r}^{*}),\mathbf{f}(\mathbf{c}^{*}))$
is also in the form of

$\alpha^{*}_{i}=\left\\{\begin{aligned} a^{\prime},\quad&i\in S;\\\
b^{\prime},\quad&i\in[q]\setminus
S,\end{aligned}\right.\quad\text{and}\quad\beta^{*}_{i}=\left\\{\begin{aligned}
b^{\prime},\quad&i\in S;\\\ a^{\prime},\quad&i\in[q]\setminus
S,\end{aligned}\right.$

where $0<b^{\prime}<a^{\prime}<\frac{2}{q}$,
$a^{\prime}+b^{\prime}=\frac{2}{q}$, and
$\frac{a^{\prime}}{b^{\prime}}=\left(\frac{a}{b}\right)^{p}>\frac{a}{b}=h>h_{0}=\mathrm{e}^{\frac{d}{2q}}$.
It follows that

$\left\lVert(\boldsymbol{\alpha}^{*},\boldsymbol{\beta}^{*})-(\mathbf{g}_{S},\mathbf{g}_{[q]\setminus
S})\right\rVert_{\infty}=b^{\prime}=\frac{2}{q(\frac{a^{\prime}}{b^{\prime}}+1)}<\frac{2\mathrm{e}^{-\frac{d}{2q}}}{q}\leq\frac{1}{15\Delta
q},$

where the last inequality holds for $\Delta\geq 8q\log\Delta$. The lemma then
follows from Corollary 14, using the fact from Lemma 18 that all maximizers
are Hessian dominant. ∎

Our proof of Lemma 8 can also be modified to show that $O(\frac{1}{\Delta
q})$-maximality fails when $q=\Omega(\frac{\Delta}{\log\Delta})$. This allows
us to prove Lemma 11 from Section 2.2.

###### Proof of Lemma 11.

We use the same notation and approach as in the proof of Lemma 8. In
particular, we show that $h<h_{1}$ for $h_{1}=\mathrm{e}^{\frac{4d}{q}}$,
which can be deduced from $f(h_{1})<h_{1}$. We have that

$\frac{1}{d}\log
f(h_{1})=\log\left(\frac{h_{1}+t}{th_{1}+1}\right)=\log\left(1+\frac{(1-t)(h_{1}-1)}{th_{1}+1}\right)\\\
<\frac{(1-t)(h_{1}-1)}{th_{1}+1}\leq\frac{1-t}{t}\leq\frac{4}{q},$

where the last inequality is because $t=1-\frac{2}{q}\geq\frac{1}{2}$.
Therefore, we get $f(h_{1})<\mathrm{e}^{\frac{4d}{q}}=h_{1}$ and consequently
$h<h_{1}$. It follows that
$\frac{a^{\prime}}{b^{\prime}}=h^{p}<\mathrm{e}^{\frac{4dp}{q}}=\mathrm{e}^{\frac{4\Delta}{q}}$,
and thus for $q\geq\frac{4\Delta}{\log\Delta}$ one has

$\left\lVert(\boldsymbol{\alpha}^{*},\boldsymbol{\beta}^{*})-(\mathbf{g}_{S},\mathbf{g}_{[q]\setminus
S})\right\rVert_{\infty}=b^{\prime}=\frac{2}{q(\frac{a^{\prime}}{b^{\prime}}+1)}>\frac{\mathrm{e}^{-\frac{4\Delta}{q}}}{q}\geq\frac{1}{\Delta
q}.$

Combining with Lemma 13, this gives that $\frac{1}{2\Delta q}$-maximality
fails when $q\geq\frac{4\Delta}{\log\Delta}$. ∎

###  5.2 Phase maximality for hard-core model

In this subsection we consider the hard-core model and establishes phase
maximality. The goal is to prove Lemma 9 from Section 2.2.

Let $\Delta\geq 3$ be an integer and $\lambda>0$ be a real. Recall from
Example 5 that the interaction matrix
$\mathbf{B}=\\{B_{ij}\\}_{i,j\in\\{0,1\\}}$ for the hard-core model is given
by $B_{00}=B_{01}=B_{10}=1$ and $B_{11}=0$, and the activity vector with
fugacity $\boldsymbol{\lambda}=\\{\lambda_{i}\\}_{i\in\\{0,1\\}}$ is given by
$\lambda_{0}=1$ and $\lambda_{1}=\lambda$. Hence, the tree-recursion (2)
becomes:

$r_{1}=\frac{\lambda c_{0}^{\Delta-1}}{\lambda c_{0}^{\Delta-1}+1},\quad
r_{0}=\frac{1}{\lambda c_{0}^{\Delta-1}+1},\quad c_{1}=\frac{\lambda
r_{0}^{\Delta-1}}{\lambda r_{0}^{\Delta-1}+1},\quad c_{0}=\frac{1}{\lambda
r_{0}^{\Delta-1}+1}.$

As is standard, it would be easier to work with the ratios
$x=\frac{r_{1}}{r_{0}}$ and $y=\frac{c_{1}}{c_{0}}$, so that the tree-
recursion can be equivalently written as

$x=\frac{\lambda}{(1+y)^{\Delta-1}},\quad y=\frac{\lambda}{(1+x)^{\Delta-1}}.$
(8)

Note that the function $f(x)=\frac{\lambda}{(1+x)^{\Delta-1}}$ has a unique
fixpoint $x_{0}$, and we are interested in the nontrivial solutions to (8)
(i.e., $(x,y)\neq(x_{0},x_{0})$). We restate Lemma 9 here for convenience.

######  Lemma 9.

For $\Delta\geq 50$ and $\lambda\geq\tfrac{50}{\Delta}$, the hard-core model
with fugacity $\lambda$ is $\tfrac{1}{24\Delta}$-maximal with respect to the
set of bicliques $\mathcal{B}_{\Delta}=\\{(0,01),(01,0)\\}$.

###### Proof.

Take an arbitrary maximizer $(\mathbf{r},\mathbf{c})$ of
$\Phi_{\mathbf{B},\boldsymbol{\lambda},\Delta}$ and let
$x=r^{*}_{1}/r^{*}_{0}$, $y=c^{*}_{1}/c^{*}_{0}$. It is known that $x\neq
x_{0}$, $y\neq x_{0}$, and $(\mathbf{r},\mathbf{c})$ is Hessian dominant when
$\lambda>\lambda_{c}(\Delta)$ is in the non-uniqueness region; see, e.g., [16,
15]. Suppose that $x<y$ without loss of generality.

We first show that $x\leq\frac{1}{30\lambda\Delta^{2}}$ when $\Delta\geq 50$
and $\lambda\geq\frac{50}{\Delta}$. By (8) we have

$\lambda=x(1+y)^{\Delta-1}=y(1+x)^{\Delta-1}.$

Define $f(t)=\frac{(1+t)^{\Delta-1}}{t}$, and note that $f(x)=f(y)$. The
function $f(t)$ is monotone decreasing when $t<\frac{1}{\Delta-2}$ and
monotone increasing when $t>\frac{1}{\Delta-2}$. This implies
$x<\frac{1}{\Delta-2}<y$. We then deduce from (8) that for $\Delta\geq 50$ and
$\lambda\geq\frac{50}{\Delta}$,

$y=\frac{\lambda}{(1+x)^{\Delta-1}}\geq\frac{\lambda}{(1+\frac{1}{\Delta-2})^{\Delta-1}}\geq\frac{\lambda}{3}>\frac{1}{\Delta-2}.$

Hence,

$f(x)=f(y)\geq
f\left(\frac{\lambda}{3}\right)=\frac{3}{\lambda}\left(1+\frac{\lambda}{3}\right)^{\Delta-1}.$

Meanwhile, we have

$f\left(\frac{1}{30\lambda\Delta^{2}}\right)=30\lambda\Delta^{2}\left(1+\frac{1}{30\lambda\Delta^{2}}\right)^{\Delta-1}\leq
30\lambda\Delta^{2}\mathrm{e}^{\frac{1}{30\lambda\Delta}}\leq
33\lambda\Delta^{2}.$

We claim that

$11(\lambda\Delta)^{2}\leq\left(1+\frac{\lambda}{3}\right)^{\Delta-1}$ (9)

when $\Delta\geq 50$ and $\lambda\geq\frac{50}{\Delta}$. Given (9), we get

$f\left(\frac{1}{30\lambda\Delta^{2}}\right)\leq
33\lambda\Delta^{2}\leq\frac{3}{\lambda}\left(1+\frac{\lambda}{3}\right)^{\Delta-1}\leq
f(x)$

and thus $x\leq\frac{1}{30\lambda\Delta^{2}}$ as wanted. It remains to prove
(9). We consider two cases. If $\lambda\leq 1$, then we have

$\frac{4}{3}\left(1+\frac{\lambda}{3}\right)^{\Delta-1}\geq\left(1+\frac{\lambda}{3}\right)^{\Delta}\geq\mathrm{e}^{\frac{\lambda\Delta}{3+\lambda}}\geq\mathrm{e}^{\frac{\lambda\Delta}{4}}\geq
15(\lambda\Delta)^{2},$

where the second inequality follows from
$1+\varepsilon\geq\exp(\frac{\varepsilon}{1+\varepsilon})$ for
$\varepsilon\in[0,1]$, and the last inequality holds when $\lambda\Delta\geq
50$. Meanwhile, if $\lambda>1$ then we have

$\frac{9}{\lambda^{2}}\left(1+\frac{\lambda}{3}\right)^{\Delta-1}\geq\left(1+\frac{\lambda}{3}\right)^{\Delta-3}\geq\left(\frac{4}{3}\right)^{\Delta-3}\geq
100\Delta^{2},$

where the last inequality holds when $\Delta\geq 50$. Therefore, (9) holds
when $\Delta\geq 50$ and $\lambda\geq\frac{50}{\Delta}$, and we conclude with
$x\leq\frac{1}{30\lambda\Delta^{2}}$ in this parameter regime.

Now, for a fixed $\Delta$, both the fixpoint $(\mathbf{r}^{*},\mathbf{c}^{*})$
of the tree recursion with $r^{*}_{1}/r^{*}_{0}<c^{*}_{1}/c^{*}_{0}$ and the
ground state $(\mathbf{g}_{0},\mathbf{g}_{01})$ converge to $(1,0,0,1)$ as
$\lambda$ tends to infinity. Consequently,
$(\boldsymbol{\alpha}^{*},\boldsymbol{\beta}^{*})$ converges to the same point
as well. Hence, for $3\leq\Delta<50$, there exists a universal constant $C>0$
such that
$\left\lVert(\boldsymbol{\alpha}^{*},\boldsymbol{\beta}^{*})-(\mathbf{g}_{0},\mathbf{g}_{01})\right\rVert_{\infty}\leq\frac{1}{30\Delta}$
whenever $\lambda\geq\frac{C}{\Delta}$. It remains to deal with the case that
$\Delta\geq 50$ and $\lambda\geq\frac{50}{\Delta}$. Observe that

$\left\lVert(\boldsymbol{\alpha}^{*},\boldsymbol{\beta}^{*})-(\mathbf{g}_{0},\mathbf{g}_{01})\right\rVert_{\infty}=\max\left\\{\alpha^{*}_{1},\frac{\lambda}{1+\lambda}-\beta^{*}_{1}\right\\}.$

We will upper bound the two terms using our bound on $x$. Recall that
$p=\frac{\Delta}{\Delta-1}$. First, we have

$\alpha^{*}_{1}\leq\frac{\alpha^{*}_{1}}{\alpha^{*}_{0}}=\left(\lambda^{-\frac{1}{\Delta}}\frac{r^{*}_{1}}{r^{*}_{0}}\right)^{p}=\lambda^{-\frac{1}{\Delta-1}}x^{p}\leq
2x\leq\frac{1}{15\lambda\Delta^{2}}\leq\frac{1}{30\Delta},$

where $\lambda^{-\frac{1}{\Delta-1}}\leq 2$ in our parameter regime. Next,
notice that

$\frac{\lambda}{1+\lambda}-\beta^{*}_{1}=\frac{\lambda}{1+\lambda}-\frac{\beta^{*}_{1}/\beta^{*}_{0}}{1+\beta^{*}_{1}/\beta^{*}_{0}}=\frac{\lambda-\beta^{*}_{1}/\beta^{*}_{0}}{(1+\lambda)(1+\beta^{*}_{1}/\beta^{*}_{0})}\leq\lambda-\frac{\beta^{*}_{1}}{\beta^{*}_{0}}.$

Since we have

$\frac{1}{\lambda}\frac{\beta^{*}_{1}}{\beta^{*}_{0}}=\frac{1}{\lambda}\left(\lambda^{-\frac{1}{\Delta}}\frac{c^{*}_{1}}{c^{*}_{0}}\right)^{p}=\left(\frac{y}{\lambda}\right)^{p}=\frac{1}{(1+x)^{\Delta}},$

it follows that

$\frac{\lambda}{1+\lambda}-\beta^{*}_{1}\leq\lambda\left(1-\frac{1}{(1+x)^{\Delta}}\right)\leq\lambda\left(1-\mathrm{e}^{-\Delta
x}\right)\leq\lambda\Delta x\leq\frac{1}{30\Delta}.$

This yields
$\left\lVert(\boldsymbol{\alpha}^{*},\boldsymbol{\beta}^{*})-(\mathbf{g}_{0},\mathbf{g}_{01})\right\rVert_{\infty}\leq\frac{1}{30\Delta}$.
The lemma then follows from Corollary 14. ∎

## References

  * [1] A. Barvinok and G. Regts.  Weighted counting of solutions to sparse systems of equations.  Combinatorics, Probability and Computing, 28(5):696–719, 2019.
  * [2] L. Bassalygo.  Asymptotically optimal switching circuits.  Problems of Information Transmission, 17(3):206–211, 1981.
  * [3] A. Blanca, P. Caputo, Z. Chen, D. Parisi, D. Štefankovič, and E. Vigoda.  On mixing of Markov chains: Coupling, spectral independence, and entropy factorization.  arXiv:2103.07459, 2021.
  * [4] C. Borgs, J. Chayes, T. Helmuth, W. Perkins, and P. Tetali.  Efficient sampling and counting algorithms for the Potts model on ${Z}^{d}$ at all temperatures.  In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC), pages 738–751, 2020.
  * [5] J.-Y. Cai, X. Chen, H. Guo, and P. Lu.  Inapproximability after uniqueness phase transition in two-spin systems.  In Combinatorial Optimization and Applications - 6th International Conference, COCOA 2012, volume 7402, pages 336–347, 2012.
  * [6] S. Cannon and W. Perkins.  Counting independent sets in unbalanced bipartite graphs.  In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1456–1466, 2020.
  * [7] S. Chen, M. Delcourt, A. Moitra, G. Perarnau, and L. Postle.  Improved bounds for randomly sampling colorings via linear programming.  In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2216–2234, 2019.
  * [8] Z. Chen, A. Galanis, L. A. Goldberg, W. Perkins, J. Stewart, and E. Vigoda.  Fast algorithms at low temperatures via Markov chains.  In Proceedings of the 23rd International Workshop on Randomization and Computation (RANDOM), pages 41:1–41:14, 2019.
  * [9] Z. Chen, A. Galanis, D. Štefankovič, and E. Vigoda.  Rapid mixing for colorings via spectral independence.  In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1548–1557, 2021.
  * [10] Z. Chen, K. Liu, and E. Vigoda.  Optimal mixing of Glauber dynamics: Entropy factorization via high-dimensional expansion.  In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), 2021.
  * [11] M. Dyer, A. Frieze, and M. Jerrum.  On counting independent sets in sparse graphs.  SIAM Journal on Computing, 31(5):1527–1541, 2002.
  * [12] W. Feng, H. Guo, Y. Yin, and C. Zhang.  Rapid mixing from spectral independence beyond the Boolean domain.  In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1558–1577, 2021.
  * [13] A. Galanis, L. A. Goldberg, and M. Jerrum.  Approximately counting $H$-colorings is #BIS-hard.  SIAM Journal on Computing, 45(3):680–711, 2016.
  * [14] A. Galanis, L. A. Goldberg, and J. Stewart.  Fast algorithms for general spin systems on bipartite expanders.  In Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 170, pages 37:1–37:14, 2020.
  * [15] A. Galanis, D. Štefankovič, and E. Vigoda.  Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region.  Journal of the ACM, 62(6), 2015.
  * [16] A. Galanis, D. Štefankovič, and E. Vigoda.  Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models.  Combinatorics, Probability and Computing, 25(04), 2016.
  * [17] L. A. Goldberg, S. Kelk, and M. Paterson.  The complexity of choosing an $H$-coloring (nearly) uniformly at random.  SIAM Journal on Computing, 33(2):416–432, 2004.
  * [18] T. Helmuth, M. Jenssen, and W. Perkins.  Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs.  arXiv:2006.11580, 2020.
  * [19] T. Helmuth, W. Perkins, and G. Regts.  Algorithmic Pirogov–Sinai theory.  Probability Theory and Related Fields, 176:851–895, 2020.
  * [20] J. Huijben, V. Patel, and G. Regts.  Sampling from the low temperature Potts model through a Markov chain on flows.  arXiv:2103.07360, 2021.
  * [21] M. Jenssen, P. Keevash, and W. Perkins.  Algorithms for #BIS-hard problems on expander graphs.  In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2235–2247, 2019.
  * [22] C. Liao, J. Lin, P. Lu, and Z. Mao.  Counting independent sets and colorings on random regular bipartite graphs.  In Proceedings of the 23rd International Workshop on Randomization and Computation (RANDOM), pages 34:1–34:12, 2019.
  * [23] J. Liu and P. Lu.  FPTAS for #BIS with degree bounds on one side.  In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), pages 549–556, 2015.
  * [24] K. Liu.  From coupling to spectral independence and blackbox comparison with the down-up walk.  arXiv:2103.11609, 2021.
  * [25] A. Sly.  Computational transition at the uniqueness threshold.  In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 287–296, 2010.
  * [26] A. Sly and N. Sun.  The computational hardness of counting in two-spin models on d-regular graphs.  In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 361–369, 2012.


# Adiabatic invariant approach on Friedmann cyclic universe

Narakorn Kaewkhao<EMAIL_ADDRESS>Department of Physics, Faculty of
Science, Prince of Songkla University, Hatyai 90112, Thailand  Phongpichit
Channuie<EMAIL_ADDRESS>School of Science, Walailak University, Nakhon
Si Thammarat, 80160, Thailand  College of Graduate Studies, Walailak
University, Nakhon Si Thammarat, 80160, Thailand

###### Abstract

Oscillating or cyclic models of the universe were inspired by Friedmann’s
seminal paper of 1922. The model supposes a closed universe. In this work, we
study Friedmann closed universe using the adiabatic invariant approach. We
start revisiting the cosmological force proposed by N. Rosen and derive the
Lagrangian density from Rosen’s concepts of cosmological force. Importantly,
we introduce the Noether gauge symmetry followed by the Rund-Traumann identity
(RTI) and adiabatic invariant approach to examine the cyclic models. We
consider a single component form of relativistic matter (stiff matter) at
$a(t=0)$ and $a(t=T)$, and surprisingly discover the world period is given by
$\sim 15.8$ Gy which is very close to that computed using the Friedmann’s
formula for the cyclic universe.

††preprint: APS/123-QED

Introduction: The general idea of a cyclic or oscillating universe went back
to 1922. In Friedmann’s seminal work, this was found that it was only
formulated in a mathematically precise way [1]. The conclusion was that the
physical demand of homogeneity and isotropy of space does not necessitate a
static Universe. Friedman discovered a new class of non-static solutions of GR
that is a generalization of Einstein’s $3$-dimensional hypersphere with a
constant in space but changing in time curvature radius $R(t)$. Friedmann come
up with the fundamental equation that governs the dynamics of the Universe. In
his model, Friedmann assumed that life of the Universe is finite and his
called this scenario the “periodic world”, see Ref.[2] for more detailed
discussion.

The adiabatic invariant approach has played an important role in atomic
physics. It has been so far applied to the elliptical electron orbit case of
the Sommerfeld model [3]. In this work, we are interested in investigating the
relation between the cosmological force first derived by Rosen, the adiabatic
invariant proposed by Ehrenfest, and the closed universe by Friedmann. We
starting reviewing the Rosen’s idea about the cosmological force. We introduce
the Noether gauge symmetry to express the Lagrangian density in the point-like
form. We then consider the Rund-Traumann identity (RTI) and adiabatic
invariant approach to examine the cyclic models. We focus on a single
component of the universe in a form of relativistic matter (stiff matter) at
the beginning and ending of the universe. We compute the world period of the
Friedmann’s cyclic universe.

Cosmological force revisit: In this part, we begin with the proposal of Nathan
Rosen regarding cosmological force. Consider the fluid equation given by

$\dot{\rho}+3\frac{\dot{a}}{a}(\rho+\frac{p}{c^{2}})=0,$ (1)

and the equation of state $p=w\rho c^{2}$. This gives the relation between the
energy density and the scale factor, i.e., $\rho(a)=\rho_{0}a^{-3(1+w)}$. From
the Friedmann equation (see Ref.[6], ch.4)

$\frac{\dot{a}^{2}}{a^{2}}=\frac{8\pi G_{\rm N}}{3}\rho(t)-\frac{\kappa
c^{2}}{R^{2}_{0}a^{2}}+\frac{\Lambda c^{2}}{3},$ (2)

where three values of the curvature $\kappa=0,+1$ and $-1$ are set for
spatially flat, open and closed universe respectively. The component of the
universe due to the cosmological constant is $\rho_{\Lambda}=\frac{\Lambda
c^{2}}{8\pi G_{\rm N}}.$ It should be noted that in some standard text on
cosmology $k\equiv\frac{\kappa}{R^{2}_{0}}$(see Ref.[7], ch.9) where
$R_{0}=1.4\times 10^{26}\,m$ denotes for the present radius of the universe.
Defining a critical density $\rho_{c}\equiv\frac{3c^{2}}{8\pi G_{\rm
N}}H(t)^{2}$, we define the dimensionless density parameter as

$\displaystyle\Omega(t)\equiv\frac{\rho(t)}{\rho_{c}}\,.$ (3)

Hence the Friedmann equation can be written as [6]

$\frac{\kappa
c^{2}}{R^{2}_{0}}={a(t)^{2}H(t)^{2}}{\Big{(}\Omega(t)-1\Big{)}}.$ (4)

Multiplying both sides of Eq.(2) by $\frac{1}{2}ma^{2}$ yields

$\displaystyle\frac{1}{2}ma^{2}\frac{1}{a^{2}}\dot{a}^{2}=\frac{8\pi G_{\rm
N}}{3}\rho(t)\frac{1}{2}ma^{2}$ $\displaystyle-$
$\displaystyle\frac{1}{2}\frac{m\kappa
c^{2}}{R^{2}_{0}}-\frac{1}{6}ma^{2}\Lambda c^{2}\,,$ (5)

or

$\displaystyle\frac{1}{2}m\dot{a}^{2}-\frac{4\pi G_{\rm
N}ma^{2}\rho}{3}+\frac{1}{6}ma^{2}\Lambda c^{2}$ $\displaystyle=$
$\displaystyle-\frac{1}{2}\frac{\kappa mc^{2}}{R^{2}_{0}}\,.$ (6)

Notice that the LHS of the above relation is $T+V$; while the RHS is $E$ where
$T,\,V$ and $E$ represent the kinetic energy, the potential energy and the
total energy of the system, respectively. It is worth to see the association
the concept of force with the potential energy, where $m$ can be seen as the
test mass (passive mass) which is placed on the equipotential surface of self-
gravitational system.

$\displaystyle V(a)=-\frac{4\pi G_{\rm
N}ma^{2}\rho(a)}{3}+\frac{1}{6}ma^{2}\Lambda c^{2}.$ (7)

Therefore, we obtain the cosmological force governed by

$\displaystyle F(a)$ $\displaystyle=$ $\displaystyle-\frac{\partial
V(a)}{\partial a}=\frac{4\pi G_{\rm
N}m}{3}\frac{d\Big{(}a^{2}\rho\Big{)}}{da}-\frac{1}{3}ma\Lambda c^{2},$ (8)

or

$\displaystyle F(a)=\frac{4\pi G_{\rm
N}m}{3}\Big{(}2a\rho+a^{2}\frac{d\rho}{da}\Big{)}-\frac{1}{3}ma\Lambda c^{2}.$
(9)

Such a form of force was beautifully appeared in the work of Rosen [5]. Using
the notion for $\dot{\rho}=\frac{\partial\rho}{\partial a}\frac{\partial
a}{\partial t}=-3\frac{\dot{a}}{a}(\rho+\frac{p}{c^{2}})$, we can write
$\frac{\partial\rho}{\partial a}=-\frac{3}{a}(\rho+\frac{p}{c^{2}})$. After
substituting $\frac{\partial\rho}{\partial a}$ into Eq.(9), this yields

$\displaystyle F(a)$ $\displaystyle=$ $\displaystyle\frac{4\pi G_{\rm
N}m}{3}\Big{[}2a\rho-\frac{3}{a}(\rho+\frac{p}{c^{2}})a^{2}-\frac{a\Lambda
c^{2}}{4\pi G_{\rm N}}\Big{]}$ (10) $\displaystyle=$ $\displaystyle\frac{4\pi
G_{\rm N}m}{3}\Big{[}2a\rho-3a(\rho+\frac{p}{c^{2}})-\frac{a\Lambda
c^{2}}{4\pi G_{\rm N}}\Big{]}$ $\displaystyle=$ $\displaystyle-\frac{4\pi
G_{\rm N}ma}{3}\Big{[}\rho+3\frac{p}{c^{2}}-\frac{\Lambda c^{2}}{4\pi G_{\rm
N}}\Big{]}$ $\displaystyle=$ $\displaystyle m\ddot{a}.$

We once reconfirm the acceleration equation or the Raychaudhuri equation as
follows:

$\displaystyle\frac{\ddot{a}}{a}=-\frac{4\pi G_{\rm
N}}{3}(\rho+\frac{3p}{c^{2}})+\frac{\Lambda c^{2}}{3}.$ (11)

It should be noted here as well that the acceleration equation can be obtained
from the Euler-Lagrange equation for the Lagrangian inspired from Rosen’s
concept of cosmological force, i.e.,

$\displaystyle\mathcal{L}(a,\dot{a})$ $\displaystyle=$ $\displaystyle T-V$
(12) $\displaystyle=$ $\displaystyle\frac{1}{2}m\dot{a}^{2}+\frac{4\pi G_{\rm
N}}{3}ma^{2}\rho(a)-\frac{1}{6}ma^{2}\Lambda c^{2}\,.$

The Rund-Traumann identity and adiabatic invariance: We discuss the Noether
gauge symmetry approach for the system and quantify exact cosmological
solutions with the help of the Noether symmetries of point-like Lagrangian. We
consider the first prolongation of NGS as

$\displaystyle X^{[1]}_{NGS}$ $\displaystyle=$ $\displaystyle
X_{NGS}+\dot{\alpha}\frac{\partial}{\partial\dot{a}},$ (13) $\displaystyle=$
$\displaystyle\Big{(}\tau\frac{\partial}{\partial
t}+\alpha\frac{\partial}{\partial
a}\Big{)}+\dot{\alpha}\frac{\partial}{\partial\dot{a}}$

where

$\displaystyle\dot{\alpha}(t,a)$ $\displaystyle=$ $\displaystyle
D_{t}\alpha-\dot{a}D_{t}\tau,$ (14) $\displaystyle=$
$\displaystyle\frac{\partial\alpha}{\partial
t}+\dot{a}\frac{\partial\alpha}{\partial
a}-\dot{a}\Big{(}\frac{\partial\tau}{\partial
t}+\dot{a}\frac{\partial\tau}{\partial\dot{a}}\Big{)}.$

Using the Noether gauge symmetry condition given by

$\displaystyle X^{[1]}_{NGS}{\cal L}+{\cal L}D_{t}\tau$ $\displaystyle=$
$\displaystyle D_{t}B,$ (15)

we have

$\displaystyle\tau\cancel{\frac{\partial L}{\partial t}}$ $\displaystyle+$
$\displaystyle\alpha\frac{\partial{\cal L}}{\partial
a}+\Bigg{(}\frac{\partial\alpha}{\partial
t}+\dot{a}\frac{\partial\alpha}{\partial
a}-\dot{a}\Big{(}\frac{\partial\tau}{\partial
t}+\dot{a}\frac{\partial\tau}{\partial\dot{a}}\Big{)}\Bigg{)}\frac{\partial\mathcal{L}}{\partial{\dot{a}}}$
(16) $\displaystyle+$
$\displaystyle\mathcal{L}\Big{(}\frac{\partial\tau}{\partial
t}+\dot{a}\frac{\partial\tau}{\partial a}\Big{)}=\Big{(}\frac{\partial
B}{\partial t}+\dot{a}\frac{\partial B}{\partial a}\Big{)}\,.$

Note that the first term on the left-hand side is zero because Lagrangian as
shown in Eq.(12) is not expressed in time variable explicitly. Hence we find

$\displaystyle\alpha\Big{[}\frac{8\pi G_{\rm N}ma\rho(a)}{3}+\frac{4\pi G_{\rm
N}ma^{2}}{3}\frac{d\rho(a)}{da}$ $\displaystyle-$
$\displaystyle\frac{ma\Lambda
c^{2}}{3}\Big{]}+\alpha_{t}(m\dot{a})+\alpha_{a}m\dot{a}^{2}-\tau_{t}m\dot{a}^{2}-m\tau_{a}\dot{a}^{3}+\frac{1}{2}m\dot{a}^{2}\tau_{t}+\frac{4\pi
G_{\rm N}ma^{2}\rho(a)}{3}\tau_{t}$ (17) $\displaystyle-$
$\displaystyle\frac{ma^{2}\Lambda
c^{2}}{6}\tau_{t}+\dot{a}\tau_{a}\frac{1}{2}m\dot{a}^{2}+\dot{a}\tau_{a}\Big{(}\frac{4\pi
G_{\rm N}ma^{2}\rho(a)}{3}-\frac{ma^{2}\Lambda
c^{2}}{6}\Big{)}=B_{t}+\dot{a}B_{a}.$

After separating monomial and polynomial, this gives the set of PDEs as

$\displaystyle\alpha\Big{[}\frac{8\pi G_{\rm N}ma\rho(a)}{3}+\frac{4\pi G_{\rm
N}ma^{2}}{3}\frac{d\rho(a)}{da}-\frac{ma\Lambda c^{2}}{3}\Big{]}+\frac{4\pi
G_{\rm N}ma^{2}\rho(a)}{3}\tau_{t}-\frac{ma^{2}\Lambda c^{2}}{6}\tau_{t}$
$\displaystyle=$ $\displaystyle B_{t},$ (18)
$\displaystyle\alpha_{t}m+\tau_{a}\frac{4\pi G_{\rm
N}ma^{2}\rho(a)}{3}-\tau_{a}\frac{ma^{2}\Lambda c^{2}}{6}$ $\displaystyle=$
$\displaystyle B_{a},$ (19)
$\displaystyle\alpha_{a}m-\tau_{t}m+\tau_{t}\frac{m}{2}$ $\displaystyle=$
$\displaystyle 0,$ (20) $\displaystyle-\frac{1}{2}m\tau_{a}$ $\displaystyle=$
$\displaystyle 0\,.$ (21)

It is rather straightforward to show that

$\displaystyle\tau_{a}$ $\displaystyle=$ $\displaystyle 0,$ (22)
$\displaystyle\alpha_{a}$ $\displaystyle=$ $\displaystyle\frac{\tau_{t}}{2},$
(23) $\displaystyle\alpha_{t}m$ $\displaystyle=$ $\displaystyle B_{a},$ (24)
$\displaystyle\alpha\Big{[}\frac{8\pi G_{\rm N}ma\rho(a)}{3}-4\pi G_{\rm
N}ma\rho(a)(1+w)\Big{]}+\frac{4\pi G_{\rm
N}ma^{2}\rho(a)}{3}\tau_{t}-\frac{ma^{2}\Lambda c^{2}}{6}\tau_{t}$
$\displaystyle=$ $\displaystyle B_{t}.$ (25)

We once obtain the possible solution of Eq.(22)-Eq.(25) as shown below:

$\displaystyle\tau(t)$ $\displaystyle=$ $\displaystyle 2c_{1}t+\tau_{0},$ (26)
$\displaystyle\alpha(a,t)$ $\displaystyle=$ $\displaystyle
c_{1}a+c_{2}t+\alpha_{0},$ (27) $\displaystyle B(a,t)$ $\displaystyle=$
$\displaystyle m(c_{2}a+c_{3}t)+B_{0},$ (28)

where $\tau_{0},\alpha_{0}$ and $B_{0}$ are arbitrary constants. To simplify
calculations , let’s set $c_{2}=0,\alpha_{0}=0,$ and $\tau_{0}=0.$ Therefore,
the new Lagrangian is expressed in term of the linear transformation of $t$
and $a(t)$, i.e., $t^{\prime}=t(1+2\epsilon c_{1})$ and
$a^{\prime}=a(1+\epsilon c_{1})$ which is inspired by Ref.[11] given below

$\displaystyle
L^{\prime}(a^{\prime}(t^{\prime}))=\frac{1}{2}m\dot{a^{\prime}}^{2}+\frac{4\pi
G_{\rm N}m{a^{\prime}}^{2}\rho(a^{\prime})}{3}-\frac{ma^{\prime 2}\Lambda
c^{2}}{6},$ (29)

The Rund-Trautman identity (RTI)[11]

$\displaystyle\dot{\tau}$
$\displaystyle\Big{[}\mathcal{L}-\dot{q}^{i}(\partial\mathcal{L}/\partial\dot{q}^{i})\Big{]}+\dot{\xi}^{i}(\partial\mathcal{L}/\partial\dot{q}^{i})+\tau(\partial\mathcal{L}/\partial
t)$ (30) $\displaystyle+\xi^{i}(\partial\mathcal{L}/\partial q^{i})=0.$

Actually, the Noether’s theorem can be directly derived from the RTI by using
the definition of the total derivative, i.e.

$\displaystyle\frac{d\mathcal{L}(t,q^{i},\dot{q}^{i})}{dt}=\frac{\partial\mathcal{L}}{\partial
t}+\frac{\partial\mathcal{L}}{\partial
q^{i}}\frac{dq^{i}}{dt}+\frac{\partial\mathcal{L}}{\partial\dot{q}^{i}}\frac{d\dot{q}^{i}}{dt},$
(31)

and the production rule for derivative, i.e.

$\displaystyle p_{i}\frac{d\xi^{i}}{dt}$ $\displaystyle=$
$\displaystyle\frac{d(p_{i}\xi^{i})}{dt}-\xi^{i}\frac{dp_{i}}{dt},$ (32)
$\displaystyle=$
$\displaystyle\frac{d(p_{i}\xi^{i})}{dt}-\xi^{i}\frac{d}{dt}\Big{(}\frac{\partial\mathcal{L}}{\partial\dot{q}^{i}}\Big{)},$

where $p_{i}=\frac{\partial L}{\partial\dot{q}^{i}}.$ Taking Ref.[12], we can
write Noether’s theorem as follows:

$\displaystyle(\dot{q}^{i}\tau-\xi^{i})\Big{[}\partial\mathcal{L}/\partial
q^{i}-d/dt(\partial\mathcal{L}/\partial\dot{q}^{i})\Big{]}$
$\displaystyle=\frac{d}{dt}\Bigg{\\{}\Big{[}\mathcal{L}-\dot{q}^{i}(\partial\mathcal{L}/\partial\dot{q}^{i})\Big{]}\tau+(\partial\mathcal{L}/\partial\dot{q}^{i})\xi^{i}\Bigg{\\}}.$
(33)

If the Euler-Lagrange equation

$\displaystyle\partial\mathcal{L}/\partial
q^{i}-d/dt(\partial\mathcal{L}/\partial\dot{q}^{i})=0$ (34)

is satisfied, then the Noether’s corollary written in term of the canonical
momenta $p_{i}$ and the Hamiltonian $\mathcal{H}$ as

$\displaystyle-\mathcal{H}\tau+p_{i}{\xi^{i}}=constant.$ (35)

The Hamiltonian $\mathcal{H}=q^{i}p_{i}-\mathcal{L}$. In this work, we set
$p_{a}=\frac{\partial L}{\partial\dot{a}}=m\dot{a}$ and
$\xi^{a}=\alpha=c_{1}a$. the Hamiltonian function is

$\displaystyle\mathcal{H}(a,p_{a})=\frac{p_{a}^{2}}{2m}-\frac{4\pi G_{\rm
N}}{3}ma^{2}\rho(a)+\frac{ma^{2}\Lambda c^{2}}{6}.$ (36)

The constant of motion can be obtained from

$\displaystyle\Sigma_{0}=\alpha\frac{\partial\mathcal{L}}{\partial\dot{a}}=\alpha
m\dot{a}=c_{1}ma\dot{a}.$ (37)

After replacing

$\displaystyle\tau(t)$ $\displaystyle=$ $\displaystyle 2c_{1}t,$
$\displaystyle\alpha$ $\displaystyle=$ $\displaystyle c_{1}a,$

to Eq.(35), it is easy to see that

$\displaystyle-\mathcal{H}t+\frac{1}{2}p_{a}a=constant.$ (38)

By taking the average operation on both sides of Eq.(38), we get that
$-\langle\mathcal{H}t\rangle+\frac{1}{2}\langle p_{a}a\rangle=constant.$
Following [12], in the context of cosmology, it was found that

$\displaystyle\langle p_{a}a\rangle$ $\displaystyle=$ $\displaystyle m\langle
a\dot{a}\rangle,$ (39) $\displaystyle=$ $\displaystyle
m\frac{\int_{0}^{T}a\dot{a}dt}{\int_{0}^{T}dt},$ $\displaystyle=$
$\displaystyle\frac{m}{T}\int_{0}^{T}a\frac{da}{dt}dt=\frac{m}{T}\int_{a(t=o)}^{a(t=T)}ada=0,$

where we have set $a(0)=a(T)$ for the cyclic universe. According to the
adiabatic invariant principle [4], it seems reasonable to assume that
$\rho(a)$ vary slowly with time over one cycle [13], i.e.,
$|\dot{\rho}/\rho|\ll 1/T$. Since $|\dot{a}/a|\lesssim 1/T$, we can hence
replace $\mathcal{H}$ with the average value $\langle\mathcal{H}t\rangle$.
That yields

$\displaystyle\langle\mathcal{H}t\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{T}\int_{0}^{T}\mathcal{H}tdt,$ (40) $\displaystyle=$
$\displaystyle\frac{\langle\mathcal{H}\rangle}{T}\int_{0}^{T}tdt=\frac{1}{2}\langle\mathcal{H}\rangle
T.$

The Boltzmann’s mechanical theorem can be generalized to

$\displaystyle\langle\mathcal{H}\rangle T=constant.$ (41)

From the Legendre transformation, we have

$\displaystyle\int_{t_{i}}^{t_{f}}\mathcal{L}dt=\int_{t_{i}}^{t_{f}}p_{i}\dot{q}^{i}dt-\int_{t_{i}}^{t_{f}}\mathcal{H}dt.$
(42)

Integrating over one cycle, this gives

$\displaystyle{\int_{0}^{T}\mathcal{L}dt}$ $\displaystyle=$
$\displaystyle\oint p_{a}da-\int_{0}^{T}\mathcal{H}dt,$ (43) $\displaystyle=$
$\displaystyle\oint p_{a}da-\langle\mathcal{H}\rangle T.$

Note that we use the definition of the time average, i.e.,

$\displaystyle\langle\mathcal{H}\rangle=\frac{\int_{0}^{T}\mathcal{H}dt}{T}.$
(44)

It is easy to see that $\int_{0}^{T}\mathcal{H}dt=\langle\mathcal{H}\rangle
T$. From the fact that $\int_{0}^{T}\mathcal{L}dt=0$, this gives

$\displaystyle\oint p_{a}da=\langle\mathcal{H}\rangle
T=-\frac{1}{2}\frac{\kappa mc^{2}}{R^{2}_{0}}T,$ (45)

where we have used $\langle\mathcal{H}\rangle=E$ given by Eq.(6).

Confluence of two frameworks: We combine two frameworks of Friedmann cyclic
universe and Ehrenfest’s adiabatic invariance. Due to
$F(a)=\frac{dp_{a}}{dt}=m\frac{d\dot{a}}{dt}$, this leads to $p_{a}=\int
F(a)dt$ where $F(a)$ is the cosmological force first proposed by Rosen.
Therefore we can write

$\displaystyle\oint p_{a}da$ $\displaystyle=$
$\displaystyle-\oint\int\frac{4\pi G_{\rm
N}ma}{3}\Big{[}\rho+3\frac{p}{c^{2}}\Big{]}dtda,$ (46) $\displaystyle=$
$\displaystyle-\frac{4\pi G_{\rm N}m}{3}(1+3w)\int\Big{(}\oint
a\rho(a)da\Big{)}dt,$ $\displaystyle=$ $\displaystyle-\frac{4\pi G_{\rm
N}m}{3}(1+3w)\rho_{0}\oint\Big{(}\int a^{-2-3w}da\Big{)}dt,$ $\displaystyle=$
$\displaystyle\frac{4\pi G_{\rm
N}m}{3}\frac{\cancel{(1+3w)}}{\cancel{(1+3w)}}\rho_{0}{\oint
a(t)^{-(1+3w)}dt}$

where $\rho(a)=\rho_{0}a^{-3(1+w)}$ [See Ref[6] topic 5.1]. At the starting
and ending points of the universe, it is reasonable to set $w=+1$ and
$a=(\frac{t}{t_{0}})^{\frac{2}{3+3w}}$ for the relativistic matter (stiff
matter). Then Eq.(46) becomes

$\displaystyle\oint p_{a}da$ $\displaystyle=$ $\displaystyle\frac{4\pi G_{\rm
N}m\rho_{0}}{3}(-3)t_{0}^{4/3}T^{-1/3}_{\pi}=\langle\mathcal{H}\rangle
T_{\pi},$ (47) $\displaystyle=$ $\displaystyle-\frac{1}{2}\frac{\kappa
mc^{2}T_{\pi}}{R^{2}_{0}}\,,$

where $T_{\pi}$ denotes the period for cyclic universe. This implies that

$\displaystyle T_{\pi}$ $\displaystyle=$ $\displaystyle\Bigg{[}\frac{8\pi
G_{\rm N}\rho_{0}t_{0}^{4/3}R^{2}_{0}}{c^{2}}\Bigg{]}^{3/4}=\Big{[}8\pi
G_{N}\rho_{0}\Big{]}^{4/3}\Big{[}\frac{R_{0}}{c}\Big{]}^{5/2}$ (48)
$\displaystyle\approx$ $\displaystyle 5\times
10^{17}s\times\frac{1yr}{3.156\times 10^{7}\,s}=1.58\times 10^{10}\,yrs\,.$

where $t_{0}=\frac{R_{0}}{c}=H_{0}^{-1}.$ Interestingly, this numerical value
computed using adiabatic invariance approach is in excellent agreement with
that calculated using the Friedmann formula. Let’s take a short recap about
his formula. From a mathematical perspective of Friedmann, the radius of
curvature would become a periodic function given by[1, 15, 2]

$\displaystyle T_{\pi}$ $\displaystyle=$
$\displaystyle\frac{2}{c}\int_{0}^{x_{0}}\sqrt{\frac{x}{A-x+\frac{\Lambda
x^{3}}{3c^{2}}}}\,\,dx\approx\frac{\pi A}{c}=\frac{8\pi G_{\rm
N}}{c^{2}}\cdot\frac{M}{6\pi c}$ (49) $\displaystyle=$
$\displaystyle\frac{8G_{\rm N}M}{6c^{3}}\approx 4.94\times 10^{17}s\approx
1.57\times 10^{10}yrs,$

where $M$ is the total mass of the universe $M=\frac{1.5\times
10^{53}kg}{1.989\times 10^{30}kg}\approx 7.9\times 10^{22}M_{\odot}$[14]. The
cosmic mass that we have considered is similar to that given in the Hoyle-
Carvalho formula $M\sim c^{3}/(GH)\sim 10^{53}kg$ [8, 9, 10], $A=\frac{4G_{\rm
N}M}{3\pi c^{2}}$ and $\Lambda$ is the cosmological constant.

Conclusion: In the present work, we have considered a formal framework of the
adiabatic invariant approach in cosmology and applied to the Friedmann closed
universe. We first derived the Lagrangian density from Rosen’s concepts of
cosmological force and then introduced the Noether gauge symmetry to the
system. We used the Rund-Traumann identity (RTI) and adiabatic invariant
approach to examine the cyclic models. The RTI and the Noether ’s theorem
provides a direct bridge between invariances and conserved quantities. We
considered a single component of the universe in a form of relativistic matter
(stiff matter) and discovered the world period is given by $\sim 15.8$ Gy. We
found that this value is very close to that computed using the Friedmann’s
formula for the cyclic universe. However, in this exploratory study, our
approach is minimalistic rather than aiming at great generality. Therefore, it
can be generalized by considering a scalar field component of the universe.
This would affect not only the totally mass of the universe but also the
periodic world.

Acknowledgements: P. Channuie acknowledged the Mid-Career Research Grant 2020
from National Research Council of Thailand (NRCT5-RSA63019-03).

## References

  * [1] A. Friedmann, (1922). “Uber die Krümmung des Raumes.” Zeitschrift fur Physik 10: 377-386.
  * [2] A. Belenkiy, ASP Conf. Ser. 471 (2013), 71 [arXiv:1302.1498 [physics.hist-ph]].
  * [3] A. Sommerfeld, (1916). “Zur Quantentheorie der Spektrallinien.” Annalen der Physik 356 (17):1-94.
  * [4] Ehrenfest, P. (1917) Adiabatic Invariants and the Theory of Quanta. Philosophical Magazine, 33, 500-513.
  * [5] N. Rosen, (1993). Quantum Mechanics of a Miniuniverse. International Journal of Theoretical Physics, Vol. 32, No. 8, 1993.
  * [6] B. Ryden, 2017 Introduction to Cosmology $2^{nd}$ Edition (New York: Cambridge University Press)
  * [7] W. Rindler, 1977 Essential relativity : special, general, and cosmological $2^{nd}$ Edition (New York : Springer-Verlag)
  * [8] Dimitar Valev, Estimations of total mass and energy of the universe Physics International, 2014, Vol. 5, Issue 1, pp. 15-20
  * [9] Carvalho, J.C. Derivation of the mass of the observable universe. Int J Theor Phys 34, 2507–2509 (1995).
  * [10] C. Sivaram (1982). Towards a unification of the parameters underlying elementary particles and cosmology. 88(2), 507–510.
  * [11] Dwight E. Neuenschwander, Emmy Noether’s Wonderful Theorem, 2011, The Johns Hopkins University Press : USA
  * [12] Dwight E. Neuenschwander and Shawana R. Starkey, Adiabatic invariance derived from the Rund-Trautman identity and Noether’s theorem, Am. J. Phys. 61 (11), November 1993
  * [13] R. J. Gleiser and C. N. Kozameh, A simple application of adiabatic invariance, American Journal of Physics 48, 756 (1980)
  * [14] Paul Davies (2006). The Goldilocks Enigma. First Mariner Books. p. 43–. ISBN 978-0-618-59226-5.
  * [15] O’Raifeartaigh, C., McCann, B. Einstein’s cosmic model of 1931 revisited: an analysis and translation of a forgotten model of the universe. EPJ H 39, 63–85 (2014). https://doi.org/10.1140/epjh/e2013-40038-x