# Convergence of Generalized Belief Propagation Algorithm on Graphs with
Motifs

Yitao Chen
Qualcomm, USA
<EMAIL_ADDRESS>
&Deepanshu Vasal
Northwestern University
<EMAIL_ADDRESS>

###### Abstract

Belief propagation is a fundamental message-passing algorithm for numerous
applications in machine learning. It is known that belief propagation
algorithm is exact on tree graphs. However, belief propagation is run on loopy
graphs in most applications. So, understanding the behavior of belief
propagation on loopy graphs has been a major topic for researchers in
different areas. In this paper, we study the convergence behavior of
generalized belief propagation algorithm on graphs with motifs (triangles,
loops, etc.) We show under a certain initialization, generalized belief
propagation converges to the global optimum of the Bethe free energy for
ferromagnetic Ising models on graphs with motifs.

##  1 Introduction

Undirected graphical models, also known as Markov Random Fields (MRF), provide
a framework for modeling high dimensional distributions with dependent
variables. Ising models are a special class of discrete pairwise graphical
models originated from statistical physics. Ising models have numerous
applications in computer vision [13], bio-informatics [7], and social networks
[3]. Explicitly, the joint distribution of Ising model is given by

$\displaystyle\mathbb{P}(X)=\frac{1}{Z}\exp\bigg{(}\beta(\sum_{i}h_{i}X_{i}+\sum_{(i,j)}J_{ij}X_{i}X_{j})\bigg{)},$
(1)

where $\\{X_{i}\\}_{i}\in\\{\pm 1\\}^{n}$ are random variables valued in a
binary alphabet (also known as "spins"), $J_{ij}$ represents the pairwise
interactions between spin $i$ and spin $j$, $h_{i}$ represents the external
field for spin $i$, $\beta=1/T$ is the reciprocal temperature, and $Z$ is a
normalization constant called _partition function_.

Historically, Ising models are proposed to study ferromagnetism. However,
researchers find the computational complexity is the main challenge of
performing sampling and inference on Ising models. In the literature, there
are multiple ways to tackle the computational complexity. One of the ways are
Markov-Chain Monte Carlo (MCMC) algorithms. A well-known example is Gibbs
sampling, which is a special case of the Metropolis–Hastings algorithm.
Basically Gibbs sampling samples a random variable conditioned on the
distribution based on the previous samples. It can be shown that Gibbs
sampling generates a reversible Markov chain of samples. Thus, the stationary
distribution of the Markov chain is the desired joint distribution over the
random variables, and it can be reached after the _burn-in period_. However,
it is also well-known that Gibbs sampling will become trapped on multi-modal
distribution. For example, Smith and Roberts [15] and Mengersen [8] show that
when the joint distribution is bi-modal, the Gibbs sampling iterations may be
trapped in one of the modes, reducing the probability of convergence.

Another popular way to go around the computational complexity is _variational
methods_ , which makes some approximation to the joint distribution. These
methods usually turn the inference problem with respect to the approximate
joint distribution into some non-convex optimization problem, and solve it
either by the standard optimization methods, e.g, gradient descent, or by
specialized algorithms like belief propagation. However, due to the non-
convexity, those methods usually do not have theoretical guarantees that the
solution converges to the global optimum.

Belief propagation (BP) is an effective numerical method for solving inference
problems on graphical models. It was originally proposed by Pearl [12] for
tree-like graphs. Ever since it plays a fundamental role in numerous
applications including coding theory [4, 14], constraint satisfaction problems
[1], and community detection in the stochastic block model [2]. It is well-
known that belief propagation is only exact for a model on a graph with
locally tree-like structures. The long haunting question is, theoretically how
does belief propagation perform on loopy graphs.

We now describe the related work and our contributions.

Related work and our contribution

In a classic work, Yedidia et al. [16] establishes the connection between
belief propagation and the Bethe free energy. He shows that there is one-to-
one correspondence between the fixed points of belief propagation and
stationary points of the Bethe free energy. Following his work, it is known
that the Bethe free energy at the critical points can be represented in terms
of fixed point messages of belief propagation [10]. In a recent work, Koehler
[6] further studies the properties of Bethe free energy at the critical
points, and shows for ferromagnetic Ising models, initialized with all one
messages, belief propagation converges to the fixed point corresponds to the
global maximum of the Bethe free energy. However, those theories consider
either asymptotic locally tree-like graphs, or loopy graphs with simple edges.
Real technological, social and biological networks have numerous short and
large loops and other complex motifs, which lead to non-tree-like structures
and essentially loopy graphs with hyper edges. Newman [11, 5] and Miller [9]
independently propose a model of random graphs with arbitrary distributions of
motifs. And Yoon et al. [17] generalizes the Belief Propagation to graphs with
motifs.

Our work builds on generalized belief propagation on graphs with motifs [17]
and the convergence of belief propagation on ferromagnetic Ising models on
loopy graphs with simple edges [6]. In this paper, we show for ferromagnetic
Ising models on graphs with motifs, with all messages initialized to one,
generalized belief propagation converges to the fixed point corresponds to the
global maximum of the Bethe free energy.

##  2 Ising Models on Graphs with Motifs

Let us introduce the concept of graphs with motifs. In graphs with motifs,
each vertex belongs to a given set of motifs. As shown in Fig.1(a) , different
motifs can be attached to vertex $i$: a simple edge $(i,j)$, a triangle, a
square, a pentagon, and other non-clique motifs. Graphs with motifs can be
viewed as hyper-graphs where motifs play a role of hyper-edges. And the number
of specific motifs attached to a vertex is equal to hyper-degree with respect
to the specific motifs. In this paper, for simplicity, we only consider simple
motifs such as simple edges, and cliques.

(a) Different motifs attached to vertex $i$

(b) Tree-like hyper-graph with triangle motifs only

Figure 1: Examples of hyper-graphs

Consider the Ising model with arbitrary order of interactions among vertices
in each motif on a hyper-graph. Let $M_{l}(i)$ denote a cluster of size $l$
attached to vertex $i$, where vertices $j_{1},j_{2},\ldots,j_{l-1}$ together
with $i$ form the motif. And let $X$ denote the random variable of spin
configurations, the Hamiltonian of the model is

$\displaystyle
E(X)=-\sum_{i}h_{i}X_{i}-\sum_{(i,j)}J_{ij}X_{i}X_{j}-\sum_{(i,j,k)}J_{ijk}X_{i}X_{j}X_{k}-\sum_{(i,j,k,l)}J_{ijkl}X_{i}X_{j}X_{k}X_{l}-\cdots$
(2)

where the first sum corresponds to the external fields at each vertex, the
second sum corresponds to the pairwise interactions on simple edges, the third
sum corresponds to the higher order interactions among spins in triangles, the
fourth sum corresponds to the higher order interactions among spins in
squares, and so on. As discussed in the previous section, most previous works
focus on Ising models with pairwise interactions. In this paper, we are
interested in Ising models with higher order interactions. For simplicity, we
consider Ising models with only external fields and higher order interactions
in triangles. Our derivation can be extended to more general cases.

Consider Ising models with only external fields and higher order interactions
in triangles, the Hamiltonian of the model is

$\displaystyle E(X)=-\sum_{i}h_{i}X_{i}-\sum_{(i,j,k)}J_{ijk}X_{i}X_{j}X_{k},$
(3)

where $(i,j,k)$ is a triangle, which can also be denoted as $M_{3}(i)$,
$M_{3}(j)$, or $M_{3}(k)$.

By Boltzmann’s law, the joint distribution is defined by

$\displaystyle P(X)=\frac{1}{Z}e^{-\beta E(X)},$ (4)

where $Z$ is the _partition function_.

Throughout this paper, we focus on _ferromagnetic_ Ising models, which is
defined below

######  Definition 1.

An Ising model is ferromagnetic if $J_{ijk}\geq 0$ for all triangle motifs
$(i,j,k)$ and $h_{i}\geq 0$ for all $i$.

We introduce a intermediate message $\mu_{M_{3}(i)}$ from a motif $M_{3}(i)$
to spin $i$.

$\displaystyle\mu_{M_{3}(i)}(X_{i})=\frac{e^{\beta\lambda_{M_{3}(i)}X_{i}}}{2\cosh{\beta\lambda_{M_{3}(i)}}}.$
(5)

In the literature, different works have different definitions of messages.
$\mu_{M_{3}(i)}$ is not the message definition we eventually work with in this
paper, but it helps to understand the connections between different works. So,
abusing the terminology a little bit, we call it ‘intermediate message’.

By the definition of generalized Belief Propagation, the probability that spin
$i$ is in a state $X_{i}$ is determined by the normalized product of incoming
intermediate messages from motifs attached to spin $i$ and the external field
factor $e^{\beta h_{i}X_{i}}$,

$\displaystyle P_{i}(X_{i})=\frac{1}{A}e^{\beta
h_{i}X_{i}}\prod_{\\{M_{3}(i)\\}}\mu_{M_{3}(i)}(X_{i}),$ (6)

where $A$ is a normalization constant. And the belief update rule is given by:

$\displaystyle\mu_{M_{3}(i)}(X_{i})=B\sum_{\\{X_{j}=\pm 1\\}}e^{-\beta
E(M_{3}(i))}\prod_{j}\prod_{\\{M_{3}(j)\neq
M_{3}(i)\\}}\mu_{M_{3}(j)}(X_{j}),$ (7)

where $E(M_{3}(i))$ is an energy of the interaction among spins in the
triangle $M_{3}(i)$, and $B$ is a normalization constant.

Multiplying Equation (7) by $X_{i}$ and summing over all spin configurations,
we obtain an equation for the effective field $\lambda_{M_{3}(i)}$,

$\displaystyle\tanh{(\beta\lambda_{M_{3}(i)})}=\frac{1}{Z(M_{3}(i))}\sum_{\\{X_{i},X_{j_{1}},\ldots=\pm
1\\}}X_{i}e^{-\beta\tilde{E}(M_{3}(i))},$ (8)

where

$\displaystyle\tilde{E}(M_{3}(i))=-\sum_{n=1}^{2}\Lambda_{t}(j_{n})X_{j_{n}}-J_{ij_{1}j_{2}}X_{i}X_{j_{1}}X_{j_{2}},$
(9) $\displaystyle\Lambda_{t}(j)=h_{j}+\sum_{\\{M_{3}(j)\neq
M_{3}(i)\\}}\lambda_{M_{3}(j)},$ (10) $\displaystyle
Z(M_{3}(i))=\sum_{\\{X_{i},X_{j_{1}},\ldots=\pm
1\\}}e^{-\beta\tilde{E}(M_{3}(i))}.$ (11)

For more detailed explanations of Equations (7) to (11), please refer to [17].

Now, define a message from a spin $i$ to motif $M_{3}(i)$ as
$\nu_{i\rightarrow M_{3}(i)}=\tanh(\lambda_{M_{3}(i)})$. More specifically, if
the motif $M_{3}(i)$ is a triangle $(i,j,k)$, the message can be alternatively
represented as $\nu_{i\rightarrow M_{3}(i)}=\nu_{i\rightarrow
jk}=\tanh(\lambda_{M_{3}(i)})$. From now on, let the reciprocal temperature
$\beta=1$, we can further simplify Equation (8) as

$\displaystyle\nu_{i\rightarrow
jk}=\tanh{\bigg{(}h_{i}+\sum_{\\{m,n\\}\in\partial
i\backslash\\{j,k\\}}\tanh^{-1}(\tanh{(J_{imn})}\nu_{m\rightarrow
in}\nu_{n\rightarrow im})\bigg{)}},$ (12)

where $\partial i$ denotes the motifs attached to spin $i$. Equation (12) is
the consistency equation for fixed point hyper-edge messages
$\nu_{i\rightarrow jk}^{*}$ of the generalized belief propagation.
Alternatively, we denote Equation (12) as $\nu_{i\rightarrow
jk}=\phi(\nu)_{i\rightarrow jk}$.

##  3 Bethe Free Energy of Higher Order Ising Models

In order to get the Bethe free energy of our higher order Ising model (3), we
need to go through the Gibbs variational principle as Yedidia et al. [16] did
for standard Ising models with pairwise interactions. Let $P^{*}$ be a joint
distribution defined by our model (4). If we have some approximate joint
distribution $P$, from Gibbs variational principle, we can write Gibbs free
energy as

$\displaystyle G(P)$ $\displaystyle=-\sum_{x}P(x)E(x)-\sum_{x}P(x)\log P(x)$
(13) $\displaystyle=-U(P)+S(P),$ (14)

where $U(P)$ is called the _average energy_ , and $S(P)$ is the _entropy_.

We would like to derive a Gibbs free energy that is a function of both the
one-node beliefs $P_{i}(x_{i})$ and the three-node beliefs
$P_{ijk}(x_{i},x_{j},x_{k})$. The beliefs should satisfy the normalization
conditions and the marginalization conditions. In other words, $P$ lies in the
following polytope of locally consistent distributions

$\displaystyle\sum_{x_{j},x_{k}}P_{ijk}(x_{i},x_{j},x_{k})$
$\displaystyle=P_{i}(x_{i})\quad\text{for all triangles $i,j,k$}$
$\displaystyle\sum_{x_{i}}P_{i}(x_{i})$ $\displaystyle=1\quad\text{for all
$i$}$ (15) $\displaystyle P_{i}(x_{i}),P_{ijk}(x_{i},x_{j},x_{k})$
$\displaystyle\geq 0\quad\text{for all triangles $(i,j,k)$, and all
$x_{i},x_{j},x_{k}$}$

Because we only consider external fields and higher order interactions with
triangles in our model, the one-node and three-node beliefs are actually
sufficient to determine the average energy. For our model (3) and for any
approximate joint probability $P$ such that one-node marginal probabilities
are $P_{i}(x_{i})$ and the three-node marginal probabilities are
$P_{ijk}(x_{i},x_{j},x_{k})$, the average energy will have the form

$\displaystyle
U(P)=-\sum_{(i,j,k)}\sum_{x_{i},x_{j},x_{k}}P_{ijk}(x_{i},x_{j},x_{k})J_{ijk}x_{i}x_{j}x_{k}-\sum_{i}\sum_{x_{i}}P_{i}(x_{i})h_{i}x_{i}$
(16)

The average energy computed with the true marginal probabilities
$P_{i}^{*}(x_{i})$ and $P_{ijk}^{*}(x_{i},x_{j},x_{k})$ will also have this
form, so if one-node and three-node beliefs are exact, the average energy
given by Equation (16) will be exact.

For computing the entropy, we usually need an approximation. We can compute
the entropy exactly if we can explicitly express the joint distribution $P(x)$
in terms of the one-node and three-node beliefs. If our graph were tree-like
hyper-graph with triangle motifs only (see Fig. 1(b) as an example), we can in
fact do that. In that case, we can represent the joint probability
distribution in the form

$\displaystyle
P(x)=\frac{\prod_{(i,j,k)}P_{ijk}(x_{i},x_{j},x_{k})}{\prod_{i}P_{i}(x_{i})^{q_{i}-1}},$
(17)

where $q_{i}$ is the hyper-degree of node $i$.

Using Equation (17), we get the Bethe approximation to the entropy as

$\displaystyle S_{\text{Bethe}}(P)$
$\displaystyle=-\sum_{(i,j,k)}\sum_{x_{i},x_{j},x_{k}}P_{ijk}(x_{i},x_{j},x_{k})\log
P_{ijk}(x_{i},x_{j},x_{k})$
$\displaystyle+\sum_{i}(q_{i}-1)\sum_{x_{i}}P_{i}(x_{i})\log P_{i}(x_{i})$
(18)

Combining Equation (16) and (3), we obtain the Bethe free energy

$\displaystyle G_{\text{Bethe}}(P)$ $\displaystyle=-U(P)+S_{\text{Bethe}}(P)$
(19)
$\displaystyle=\sum_{(i,j,k)}J_{ijk}\mathbb{E}_{P_{ijk}}[X_{i}X_{j}X_{k}]+\sum_{i}h_{i}\mathbb{E}_{P_{i}}[X_{i}]$
$\displaystyle+\sum_{(i,j,k)}H_{P_{ijk}}(X_{i},X_{j},X_{k})-\sum_{i}(q_{i}-1)H_{P_{i}}(X_{i})$
(20)

Notice when the hyper-graph is a tree, the Bethe free energy
$G_{\text{Bethe}}(P)$ will have the correct functional dependence on the
beliefs. And solving the optimization problem: maximizing
$G_{\text{Bethe}}(P)$ over the polytope of locally consistent distribution (3)
will give the true marginals. For loopy hyper-graphs, the Bethe free energy
$G_{\text{Bethe}}(P)$ is only an approximation, which is the essence of the
variational methods.

We can derive the BP equations from the first-order optimality conditions for
the aforementioned optimization problem. In other words, we can verify that _a
set of beliefs gives a BP fixed point in any hyper-graph if and only if they
are stationary points of the Bethe free energy_ for the generalized BP. To see
this, we need to add Lagrange multipliers to $G_{\text{Bethe}}(P)$ to form a
Lagrangian $L$. Let $\lambda_{i\rightarrow jk}(x_{i})$ be a multiplier that
enforces the marginalization constraint
$\sum_{x_{j},x_{k}}P_{ijk}(x_{i},x_{j},x_{k})=P_{i}(x_{i})$, and $\lambda_{i}$
be a multiplier that enforces the normalization of $P_{i}(x_{i})$. So, the
largrangian corresponding to the optimization problem is

$\displaystyle\mathcal{L}(P,\lambda)$
$\displaystyle=G_{\text{Bethe}}(P)+\sum_{(i,j,k),x_{i}}\lambda_{i\rightarrow
jk}(x_{i})(\sum_{x_{j},x_{k}}P_{ijk}(x_{i},x_{j},x_{k})-P_{i}(x_{i}))$
$\displaystyle+\sum_{i}\lambda_{i}(\sum_{x_{i}}P_{i}(x_{i})-1)$ (21)

where we ignore the constraints $P_{i}(x_{i}),P_{ijk}(x_{i},x_{j},x_{k})\geq
0$ because, given other constraints, those constraints are always satisfied at
a critical point.

The equation $\frac{\partial L}{\partial P_{ijk}(x_{i},x_{j},x_{k})}=0$ gives:

$\displaystyle\log
P_{ijk}(x_{i},x_{j},x_{k})=J_{ijk}x_{i}x_{j}x_{k}+\lambda_{i\rightarrow
jk}(x_{i})+\lambda_{j\rightarrow ik}(x_{j})+\lambda_{k\rightarrow
ij}(x_{k})-1$ (22)

Setting $\lambda_{i\rightarrow jk}^{\prime}=\frac{\lambda_{i\rightarrow
jk}(1)-\lambda_{i\rightarrow jk}(-1)}{2}$, we find that at a critical point of
the Lagrangian that

$\displaystyle P_{ijk}(x_{i},x_{j},x_{k})$
$\displaystyle\propto\exp\bigg{(}J_{ijk}x_{i}x_{j}x_{k}+\lambda_{i\rightarrow
jk}(x_{i})+\lambda_{j\rightarrow ik}(x_{j})+\lambda_{k\rightarrow
ij}(x_{k})\bigg{)}$ (23)
$\displaystyle\propto\exp\bigg{(}J_{ijk}x_{i}x_{j}x_{k}+\lambda_{i\rightarrow
jk}^{\prime}x_{i}+\lambda_{j\rightarrow
ik}^{\prime}x_{j}+\lambda_{k\rightarrow ij}^{\prime}x_{k}\bigg{)}$ (24)

And the equation $\frac{\partial L}{\partial P_{i}(x_{i})}=0$ gives:

$\displaystyle(q_{i}-1)(1+\log P_{i}(x_{i}))=\sum_{\\{j,k\\}\in\partial
i}\lambda_{i\rightarrow jk}(x_{i})-h_{i}x_{i}-\lambda_{i}$ (25)

Setting $\lambda_{i\rightarrow jk}^{\prime}=\frac{\lambda_{i\rightarrow
jk}(1)-\lambda_{i\rightarrow jk}(-1)}{2}$, we find that at a critical point of
the Lagrangian that

$\displaystyle P_{i}(x_{i})$
$\displaystyle\propto\exp\bigg{(}\frac{1}{q_{i}-1}\sum_{\\{j,k\\}\in\partial
i}\lambda_{i\rightarrow jk}(x_{i})-\frac{h_{i}}{q_{i}-1}x_{i}\bigg{)}$ (26)
$\displaystyle\propto\exp\bigg{(}\frac{1}{q_{i}-1}\sum_{\\{j,k\\}\in\partial
i}\lambda_{i\rightarrow jk}^{\prime}x_{i}-\frac{h_{i}}{q_{i}-1}x_{i}\bigg{)}$
(27)

Furthermore, by differentiating with respect to $\lambda$, we see that the
marginalization constraints are satisfied. Therefore, for any triangle
$(i,j,k)$, $\sum_{x_{j},x_{k}}P_{ijk}(x_{i},x_{j},x_{k})=P_{i}(x_{i})$. Hence,

$\displaystyle P_{i}(x_{i})^{q_{i}-1}$
$\displaystyle\propto\prod_{\\{m,n\\}\in\partial
i\backslash\\{j,k\\}}\sum_{x_{m},x_{n}}P_{imn}(x_{i},x_{m},x_{n})$ (28)
$\displaystyle\propto\sum_{x_{\partial
i\backslash\\{j,k\\}}}\exp\bigg{(}\sum_{\\{m,n\\}}(J_{imn}x_{i}x_{m}x_{n}+\lambda_{i\rightarrow
mn}^{\prime}x_{i}+\lambda_{m\rightarrow
in}^{\prime}x_{m}+\lambda_{n\rightarrow im}^{\prime}x_{n})\bigg{)}$ (29)
$\displaystyle=\exp(\sum_{\\{m,n\\}}\lambda_{i\rightarrow
mn}^{\prime}x_{i})\sum_{x_{\partial
i\backslash\\{j,k\\}}}\exp\bigg{(}\sum_{\\{m,n\\}}(J_{imn}x_{i}x_{m}x_{n}+\lambda_{m\rightarrow
in}^{\prime}x_{m}+\lambda_{n\rightarrow im}^{\prime}x_{n})\bigg{)}$ (30)

So

$\displaystyle\exp(\lambda_{i\rightarrow jk}^{\prime}x_{i}-h_{i}x_{i})$
$\displaystyle\propto\sum_{x_{\partial
i\backslash\\{j,k\\}}}\exp\bigg{(}\sum_{\\{m,n\\}}(J_{imn}x_{i}x_{m}x_{n}+\lambda_{m\rightarrow
in}^{\prime}x_{m}+\lambda_{n\rightarrow im}^{\prime}x_{n})\bigg{)}$ (31)
$\displaystyle\propto\prod_{\\{m,n\\}\in\partial
i\backslash\\{j,k\\}}\sum_{x_{m},x_{n}}\exp\bigg{(}J_{imn}x_{i}x_{m}x_{n}+\lambda_{m\rightarrow
in}^{\prime}x_{m}+\lambda_{n\rightarrow im}^{\prime}x_{n}\bigg{)}$ (32)

Define $\nu_{i\rightarrow jk}:=\tanh(\lambda_{i\rightarrow jk}^{\prime})$, we
have

$\displaystyle\frac{1+\nu_{i\rightarrow
jk}x_{i}}{2}=\frac{e^{\lambda_{i\rightarrow
jk}^{\prime}x_{i}}}{e^{\lambda_{i\rightarrow
jk}^{\prime}}+e^{-\lambda_{i\rightarrow jk}^{\prime}}}$ (33)

Let

$\displaystyle
f(x_{i})=e^{h_{i}x_{i}}\prod_{\\{m,n\\}}\sum_{x_{m},x_{n}}e^{J_{imn}x_{i}x_{m}x_{n}}e^{\lambda_{m\rightarrow
in}^{\prime}x_{m}+\lambda_{n\rightarrow im}^{\prime}x_{n}}$ (34)

Then we see

$\displaystyle\nu_{i\rightarrow jk}$
$\displaystyle=\frac{f(1)-f(-1)}{f(1)+f(-1)}$ (35)
$\displaystyle=\tanh{\bigg{(}h_{i}+\sum_{\\{m,n\\}\in\partial
i\backslash\\{j,k\\}}\tanh^{-1}(\tanh{(J_{imn})}\nu_{m\rightarrow
in}\nu_{n\rightarrow im})\bigg{)}}$ (36)

which is the BP consistency equation (12) we derived in Section 2.

Till this point, we represent the Bethe free energy in terms of beliefs
corresponds to BP fixed points. In order to analyze the behavior of the Bethe
free energy at BP fixed points, we need to represent the Bethe free energy in
terms of the hyper-edge messages $\nu_{i\rightarrow jk}$, which is called
_dual Bethe free energy_ in the literature. First, we have the following
lemma.

######  Lemma 1.

The dual Bethe free energy at a critical point can be defined by

$\displaystyle
G^{*}_{\text{Bethe}}(\lambda)=\sum_{i}F_{i}(\lambda)-\sum_{(i,j,k)}F_{ijk}(\lambda),$
(37)

where

$\displaystyle F_{i}(\lambda)$
$\displaystyle=\log\sum_{x_{i}}e^{h_{i}x_{i}}\prod_{\\{m,n\\}\in\partial
i}\sum_{x_{m},x_{n}}e^{J_{imn}x_{i}x_{m}x_{n}}e^{\lambda_{m\rightarrow
in}^{\prime}x_{m}+\lambda_{n\rightarrow im}^{\prime}x_{n}}$ (38)
$\displaystyle F_{ijk}(\lambda)$
$\displaystyle=\log\sum_{x_{i},x_{j},x_{k}}e^{J_{ijk}x_{i}x_{j}x_{k}+\lambda_{i\rightarrow
jk}^{\prime}x_{i}+\lambda_{j\rightarrow
ik}^{\prime}x_{j}+\lambda_{k\rightarrow ij}^{\prime}x_{k}}$ (39)

###### Proof.

Recall the Bethe free energy

$\displaystyle G_{\text{Bethe}}(P)$ $\displaystyle=-U(P)+S_{\text{Bethe}}(P)$
(40)
$\displaystyle=\sum_{(i,j,k)}J_{ijk}\mathbb{E}_{P_{ijk}}[X_{i}X_{j}X_{k}]+\sum_{i}h_{i}\mathbb{E}_{P_{i}}[X_{i}]$
(41)
$\displaystyle+\sum_{(i,j,k)}H_{P_{ijk}}(X_{i},X_{j},X_{k})-\sum_{i}(q_{i}-1)H_{P_{i}}(X_{i})$
(42)

By rearranging terms, we have

$\displaystyle
G_{\text{Bethe}}(P)=G^{*}_{\text{Bethe}}(\lambda)=\sum_{i}F_{i}(\lambda)-\sum_{(i,j,k)}F_{ijk}(\lambda),$
(43)

where

$\displaystyle F_{i}(\lambda)$
$\displaystyle=\mathbb{E}[h_{i}X_{i}+\sum_{\\{m,n\\}}(J_{imn}X_{i}X_{m}X_{n}+\lambda_{m\rightarrow
in}^{\prime}X_{m}+\lambda_{n\rightarrow im}^{\prime}X_{n})]$ (44)
$\displaystyle+\sum_{\\{m,n\\}\in\partial
i}H(X_{i},X_{m},X_{n})-(q_{i}-1)H(X_{i})$ (45)

and

$\displaystyle
F_{ijk}(\lambda)=\mathbb{E}[J_{ijk}X_{i}X_{j}X_{k}+\lambda_{i\rightarrow
jk}^{\prime}X_{i}+\lambda_{j\rightarrow
ik}^{\prime}X_{j}+\lambda_{k\rightarrow
ij}^{\prime}X_{k}]+H(X_{i},X_{j},X_{k})$ (46)

W.l.o.g., let us look at the term $F_{ijk}(\lambda)$, let
$f(X)=J_{ijk}X_{i}X_{j}X_{k}+\lambda_{i\rightarrow
jk}^{\prime}X_{i}+\lambda_{j\rightarrow
ik}^{\prime}X_{j}+\lambda_{k\rightarrow ij}^{\prime}X_{k}$, it can be
rewritten as

$\displaystyle F_{ijk}(\lambda)$
$\displaystyle=\mathbb{E}[f(X)]-\mathbb{E}[\log P_{ijk}(X_{i},X_{j},X_{k})]$
(47)
$\displaystyle=\mathbb{E}[\log\frac{e^{f(X)}}{P_{ijk}(X_{i},X_{j},X_{k})}]$
(48)

From Equation (4), we know

$\displaystyle P_{ijk}(X_{i},X_{j},X_{k})=\frac{1}{Z_{ijk}}e^{f(X)},$ (49)

where $Z_{ijk}$ is a normalization constant
$Z_{ijk}=\sum_{x_{i},x_{j},x_{k}}e^{f(X)}$. Substitute it back into Equation
(47), we have

$\displaystyle F_{ijk}(\lambda)$
$\displaystyle=\mathbb{E}[\log(Z_{ijk})]=\log(Z_{ijk})=\log(\sum_{x_{i},x_{j},x_{k}}e^{f(X)})$
(50)
$\displaystyle=\log\sum_{x_{i},x_{j},x_{k}}e^{J_{ijk}x_{i}x_{j}x_{k}+\lambda_{i\rightarrow
jk}^{\prime}x_{i}+\lambda_{j\rightarrow
ik}^{\prime}x_{j}+\lambda_{k\rightarrow ij}^{\prime}x_{k}}$ (51)

∎

If we use the definition $\nu_{i\rightarrow jk}:=\tanh(\lambda_{i\rightarrow
jk}^{\prime})$, and define $\theta_{ijk}=\tanh(J_{ijk})$, we have the
following corollary:

######  Corollary 1.

The dual Bethe free energy in terms of hyper-edge messages is

$\displaystyle
G^{*}_{\text{Bethe}}(\nu)=\sum_{i}F_{i}(\nu)-\sum_{(i,j,k)}F_{ijk}(\nu),$ (52)

where

$\displaystyle F_{i}(\nu)$
$\displaystyle=\log\bigg{[}e^{h_{i}}\prod_{m,n}(1+\theta_{imn}v_{m\rightarrow
in}\nu_{n\rightarrow im})-e^{-h_{i}}\prod_{m,n}(1-\theta_{imn}v_{m\rightarrow
in}\nu_{n\rightarrow im})\bigg{]}$ (53) $\displaystyle F_{ijk}(\lambda)$
$\displaystyle=\log\bigg{(}1+\theta_{ijk}\nu_{i\rightarrow
jk}\nu_{j\rightarrow ik}\nu_{k\rightarrow ij}\bigg{)}$ (54)

##  4 Optimization Landscape

Now, we can study the behavior of the Bethe free energy at critical points.
The following lemma establishes that $\phi(\nu)_{i\rightarrow jk}$ is a
concave monotone function for some non-negative $\nu$.

######  Lemma 2.

Suppose that $f(x)=\tanh(h+\sum_{(i,j)}\tanh^{-1}(x_{i}x_{j}))$ for any $h\geq
0$. Then $f$ is a concave monotone function on the domain $[x^{*},1)^{n}$.

###### Proof.

Observe that

$\displaystyle\frac{\partial f}{\partial
x_{i}}(x)=\frac{1-f(x)^{2}}{1-(x_{j}x_{i})^{2}}x_{j}\geq 0,$ (55)

which proves monotonicity, and

$\displaystyle\frac{\partial^{2}f}{\partial x_{i}x_{k}}(x)$
$\displaystyle=\frac{1-f(x)^{2}}{(1-(x_{j}x_{i})^{2})(1-(x_{l}x_{k})^{2})}\bigg{[}-2f(x)x_{j}x_{l}+\mathbbold{1}(k=j,l=i)(1+(x_{i}x_{j})^{2})$
$\displaystyle+\mathbbold{1}(k=i,l=j)2(x_{i}x_{j})^{2}\bigg{]}.$ (56)

Note that for any non-negative vector $w$, if we let

$\displaystyle
w_{i}^{\prime}=\frac{\sqrt{1-f(x)^{2}}}{1-(x_{j}x_{i})^{2}}x_{j}w_{i},\quad
w_{k}^{\prime}=\frac{\sqrt{1-f(x)^{2}}}{1-(x_{k}x_{l})^{2}}x_{l}w_{k}$ (57)

Then we have,

$\displaystyle\sum_{i,k}w_{i}\frac{\partial^{2}f}{\partial x_{i}x_{k}}w_{k}$
(58) $\displaystyle=$
$\displaystyle\sum_{i,k}w_{i}^{\prime}\bigg{[}-2f(x)+\mathbbold{1}(k=j,l=i)(\frac{1}{x_{i}x_{j}}+x_{i}x_{j})+\mathbbold{1}(k=i,l=j)2x_{i}x_{j}\bigg{]}w_{k}^{\prime}$
(59) $\displaystyle=$
$\displaystyle-2f(x)(\sum_{i}w_{i}^{\prime})^{2}+\sum_{(ij)}w_{i}^{\prime}w_{j}^{\prime}(\frac{1}{x_{i}x_{j}}+x_{i}x_{j})+\sum_{i}{w_{i}^{\prime}}^{2}2x_{i}x_{j}$
(60) $\displaystyle\leq$
$\displaystyle\sum_{i}-2(f(x)-x_{i}x_{j}){w_{i}^{\prime}}^{2}+\sum_{(ij)}w_{i}^{\prime}w_{j}^{\prime}(\frac{1}{x_{i}x_{j}}+x_{i}x_{j}-2f(x))$
(61) $\displaystyle=$
$\displaystyle\sum_{(i,j)}w_{i}^{\prime}w_{j}^{\prime}\bigg{[}\frac{1}{x_{i}x_{j}}+x_{i}x_{j}-2f(x)\bigg{(}1+(1-\frac{x_{i}x_{j}}{f(x)})(\frac{1}{q_{i}}\frac{w_{i}^{\prime}}{w_{j}^{\prime}}+\frac{1}{q_{j}}\frac{w_{j}^{\prime}}{w_{i}^{\prime}})\bigg{)}\bigg{]}$
(62)

For any edge $(i,j)$, let
$C=\frac{1}{q_{i}}\frac{w_{i}^{\prime}}{w_{j}^{\prime}}+\frac{1}{q_{j}}\frac{w_{j}^{\prime}}{w_{i}^{\prime}}$
(note $C\geq 2/\sqrt{q_{i}q_{j}}$), and

$\displaystyle g(x)=\frac{1}{x}+x-2f(x)\bigg{(}1+C(1-\frac{x}{f(x)})\bigg{)}.$
(63)

Due to the fact $x<f(x)$, we know $g(x)\rightarrow\infty$ as $x\rightarrow 0$,
and $g(1)<0$. Since $g(x)$ is continuous over $(0,1)$, if we assume
$x^{*}_{ij}$ is the largest root for $g(x)$ in $(0,1)$, we know $g(x)<0$ in
$(x^{*}_{ij},1)$. Let $x^{*}=\max_{(i,j)}x^{*}_{ij}$, we have

$\displaystyle\sum_{i,k}w_{i}\frac{\partial^{2}f}{\partial
x_{i}x_{k}}w_{k}\leq 0,$ (64)

for $x\in[x^{*},1)^{n}$. ∎

We define the set of _pre-fixpoints_ and _post-fixpoints_ messages similar as
in [6]:

$\displaystyle S_{\text{pre}}=\\{\nu:x^{*}\leq\phi(\nu)_{i\rightarrow
jk}\leq\nu_{i\rightarrow jk}\\},\quad
S_{\text{post}}=\\{\nu:x^{*}\leq\nu_{i\rightarrow
jk}\leq\phi(\nu)_{i\rightarrow jk}\\}$ (65)

From Lemma 2, we know $S_{\text{post}}$ is a convex set, while
$S_{\text{pre}}$ is typically non-convex and even disconnected. Next, we show
the gradient of the dual Bethe free energy is well-behaved on these sets:

######  Lemma 3.

If $\nu\in S_{\text{pre}}$ then $\nabla G^{*}_{\text{Bethe}}(\nu)\leq 0$ and
if $\nu\in S_{\text{post}}$ then $\nabla G^{*}_{\text{Bethe}}(\nu)\geq 0$

###### Proof.

The lemma will follow if we compute the gradient of the dual Bethe free energy
function $G^{*}_{\text{Bethe}}(\nu)$.

$\displaystyle\frac{\partial
G^{*}_{\text{Bethe}}(\nu)}{\partial\nu_{j\rightarrow ik}}=\frac{\partial
F_{i}(\nu)}{\partial\nu_{j\rightarrow ik}}-\frac{\partial
F_{ijk}(\nu)}{\partial\nu_{j\rightarrow ik}}$ $\displaystyle=$
$\displaystyle\frac{e^{h_{i}}\theta\nu_{k\rightarrow ij}\prod_{m,n\in\partial
i\backslash\\{j,k\\}}(1+\theta\nu_{m\rightarrow in}\nu_{n\rightarrow
im})-e^{-h_{i}}\theta\nu_{k\rightarrow ij}\prod_{m,n\in\partial
i\backslash\\{j,k\\}}(1-\theta\nu_{m\rightarrow in}\nu_{n\rightarrow
im})}{e^{h_{i}}\prod_{m,n}(1+\theta v_{m\rightarrow in}\nu_{n\rightarrow
im})-e^{-h_{i}}\prod_{m,n}(1-\theta v_{m\rightarrow in}\nu_{n\rightarrow
im})}$ $\displaystyle-\frac{\theta\nu_{i\rightarrow jk}\nu_{k\rightarrow
ij}}{1+\theta\nu_{i\rightarrow jk}\nu_{j\rightarrow ik}\nu_{k\rightarrow ij}}$
$\displaystyle=\frac{1}{\nu_{j\rightarrow ik}+1/(\theta\nu_{k\rightarrow
ij}\phi(\nu)_{i\rightarrow jk})}-\frac{1}{\nu_{j\rightarrow
ik}+1/(\theta\nu_{k\rightarrow ij}\nu_{i\rightarrow jk})}.$ (66)

Recall $\phi(\nu)_{i\rightarrow jk}$ is the updated message from spin $i$ to
motif $\\{j,k\\}$ based on the current messages $\nu$. If $\nu\in
S_{\text{pre}}$ or $S_{\text{post}}$, then the signs of the gradient of Bethe
free energy are determined by Equation (4) as claimed. ∎

Based on Lemma 2 and 3, we can prove our main theorem.

######  Theorem 1.

Suppose that generalized BP is run from initial messages $\nu_{i\rightarrow
jk}^{(0)}=1$ and there is at least one fixed point in $[x^{*},1)^{n}$. The
messages converge to a fixed point $\nu^{*}$ of the generalized BP equations
such that for any other fixed point $\mu$, $\mu_{i\rightarrow
jk}\leq\nu_{i\rightarrow jk}^{*}$. Furthermore

$\displaystyle G^{*}_{\text{Bethe}}(\nu^{*})=\max_{\nu\in
S_{\text{post}}}G^{*}_{\text{Bethe}}(\nu)$ (67)

###### Proof.

If there is at least one fixed point in $[x^{*},1)^{n}$, and the
initialization is $\nu_{i\rightarrow jk}^{(0)}=1$ for all hyper-edges
$\\{i,j,k\\}$. For each iteration of Belief Propagation,
$\nu^{(t)}=\phi(\nu^{(t-1)})$.

From Lemma 2, we know $\phi$ is monotonic on $[x^{*},1)^{n}$. So,
$\nu^{(0)},\nu^{(1)},\ldots,\nu^{(t)}$ is a coordinate-wise decreasing
sequence, which will converge to some fixed point. By monotonicity, we see
that for any fixed point $\mu\in[x^{*},1)^{n}$, $\mu_{i\rightarrow
jk}\leq\nu_{i\rightarrow jk}^{(t)}$ for all $t$. Hence, it holds for $\nu^{*}$
as well.

Finally, consider any other point $\nu\in S_{\text{post}}$, by convexity of
$S_{\text{post}}$, we know that the line segment from $\nu$ to $\nu^{*}$ is
entirely contained in $S_{\text{post}}$. By Lemma 3, we see that for any point
$x$ on this interpolating line segment that $\nabla
G_{\text{Bethe}}(\nu)\cdot(\nu^{*}-\nu)\geq 0$, and integrating over this line
segment gives us $G_{\text{Bethe}}(\nu)\leq G_{\text{Bethe}}(\nu^{*})$. ∎

## References

  * Achlioptas and Moore [2006] D. Achlioptas and C. Moore.  Random k-sat: Two moments suffice to cross a sharp threshold.  _SIAM Journal on Computing_ , 36(3):740–762, 2006\.
  * Decelle et al. [2011] A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová.  Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications.  _Physical Review E_ , 84(6):066106, 2011.
  * Eagle et al. [2009] N. Eagle, A. S. Pentland, and D. Lazer.  Inferring friendship network structure by using mobile phone data.  _Proceedings of the national academy of sciences_ , 106(36):15274–15278, 2009.
  * Frey et al. [1998] B. J. Frey, J. F. Brendan, and B. J. Frey.  _Graphical models for machine learning and digital communication_.  MIT press, 1998.
  * Karrer and Newman [2010] B. Karrer and M. E. Newman.  Random graphs containing arbitrary distributions of subgraphs.  _Physical Review E_ , 82(6):066118, 2010.
  * Koehler [2019] F. Koehler.  Fast convergence of belief propagation to global optima: Beyond correlation decay.  _arXiv preprint arXiv:1905.09992_ , 2019.
  * Marbach et al. [2012] D. Marbach, J. C. Costello, R. Küffner, N. M. Vega, R. J. Prill, D. M. Camacho, K. R. Allison, M. Kellis, J. J. Collins, and G. Stolovitzky.  Wisdom of crowds for robust gene network inference.  _Nature methods_ , 9(8):796–804, 2012.
  * Mengersen [1996] K. L. Mengersen.  Testing for mixtures: a bayesian entropic approach.  _Bayesian statistics_ , pages 255–276, 1996.
  * Miller [2009] J. C. Miller.  Percolation and epidemics in random clustered networks.  _Physical Review E_ , 80(2):020901, 2009.
  * Montanari [2013] A. Montanari.  Statistical mechanics and algorithms on sparse and random graphs.  _Lectures on Probability Theory and Statistics. Saint-Flour_ , 2013\.
  * Newman [2009] M. E. Newman.  Random graphs with clustering.  _Physical review letters_ , 103(5):058701, 2009\.
  * Pearl [2014] J. Pearl.  _Probabilistic reasoning in intelligent systems: networks of plausible inference_.  Elsevier, 2014.
  * Ravikumar et al. [2010] P. Ravikumar, M. J. Wainwright, J. D. Lafferty, et al.  High-dimensional ising model selection using l1-regularized logistic regression.  _The Annals of Statistics_ , 38(3):1287–1319, 2010.
  * Richardson and Urbanke [2001] T. J. Richardson and R. L. Urbanke.  The capacity of low-density parity-check codes under message-passing decoding.  _IEEE Transactions on information theory_ , 47(2):599–618, 2001.
  * Smith and Roberts [1993] A. F. Smith and G. O. Roberts.  Bayesian computation via the gibbs sampler and related markov chain monte carlo methods.  _Journal of the Royal Statistical Society: Series B (Methodological)_ , 55(1):3–23, 1993.
  * Yedidia et al. [2003] J. S. Yedidia, W. T. Freeman, and Y. Weiss.  Understanding belief propagation and its generalizations.  _Exploring artificial intelligence in the new millennium_ , 8:236–239, 2003.
  * Yoon et al. [2011] S. Yoon, A. V. Goltsev, S. N. Dorogovtsev, and J. Mendes.  Belief-propagation algorithm and the ising model on networks with arbitrary distributions of motifs.  _Physical Review E_ , 84(4):041144, 2011.


# Some Questions Around The Hilbert 16th Problem

Ali Taghavi
<EMAIL_ADDRESS>

Hilbert sixteenth problem asks for existence of uniform upper bound $H(n)$ for
the number of limit cycles of a polynomial vector field of degree n,on the
plane.This problem is open even for $n=2$.However ,it is well known that the
number of limit of a polynomial vector field on the plane is finite,see $[3]$.
Using polar Change of coordinates we replace the phenomena of limit cycle with
solution $(r,\theta)$ with the condition $r(0)=r(2\pi)$.

More generally consider the equation
$Z^{\prime}=a_{n}(t)Z^{n}+a_{n-1}(t)Z^{n-1}+\ldots$
where $Z^{\prime}=dZ/dt$ and $a_{i}(t)$ are $c^{1}$ functions of real $t$.

for a fixed $t$,put $U(t)$ for the set of all $z$ in $\mathbb{C}$ ,that
$\phi_{t}$ can be defined at $(Z,0)$,where $\phi$ is the flow of corresponding
autonomous system,adding $t^{\prime}=1$ to the equation. $U(t)$ is an open
simply connected subset of $\mathbb{C}$,further $\phi_{t}$, as a map from
$U(t)$ to $\mathbb{C}$, is a holomorphic function:if $a_{i}$ is not analytic
we approximate it with analytic map,and note that the uniform limit of
holomorphic functions is holomorph.This shows that for $n>1$ the above system
is not a complete Vector field. Because any one to one entire function must be
linear $\phi_{t}(Z)=a(t)Z+b(t)$. Differentiating in t implies $n=1$ Similarly
if $\phi_{t}$ be mobious function then n can be at most two This shows for
$n>2$ the argument of Smale described in $[6]$ is not applicable.since any
continuous function from spher to spher is holomorphic if it is holomorph on
an open and dense subset of spher.On the other hand a fixed point of a
holomorphic function has non negative Lefschetz number. In fact for n=3 there
are example of autonomous equation $z^{\prime}=f(z)$ that there are two
isochronous center with different period $T_{1}$ and $T_{2}$ and $\phi_{T}$
can not be extended even continuously to sphere.

The $Complexification$ of the Hilbert 16th problem is a beautiful idea but in
some case is not effective.In this note we suggest some different views,for
looking at the Hilbert 16th problem:

1)Let $[X,Y]=0$ and $\gamma$ is a limit cycle for X then $\gamma$ must be
invariant under Y,namely $X$ and $Y$ share on limit cycles. Since $X$ and
$fX$, for positive function f, have the same trajectories,it is interesting to
compare $C(X)$ with $C(fX)$. By $C(X)$ , centralizer of $X$ ,one means all
vector fields $Z$ with $[X,Z]=0$, Locally around a non singular point of $X$,
$C(X)$ and $C(fX)$ are isomorphic lie algebras. This local fact is no longer
true globally(for a non vanishing Vector field on arbitrary surface),and ba
false around a singularity of a vector field. For example,put
$f(x,y)=x^{2}+y^{2}+1$ and vector field $X$ as follow

$\begin{cases}\dot{x}=y\\\ \dot{y}=-x,\end{cases}$

$X$ is a non vanishing vector field on $\mathbb{R}^{2}-{0}$,on the other hand
$X$ is a vector field with singularity at origin ,in both cases,two lie
algebras $C(X)$ and $C(fX)$ are not isomorph since the operation of lie
bracket is zero in $C(fX)$ ,but it is not the case in $C(X)$.

It is also interesting that one look at the Hilbert sixteen problem in a non
analytic but smooth manner ,for example consider the following question:

Let L be the lienard polynomial Vector field

$\begin{cases}\dot{x}=y-F(x)\\\ \dot{y}=-x,\end{cases}$

without center and $S$ be a smooth vector field with $[L,S]=0$,is it
necessarily $S=kL$ for constant $k$?

Remark Non triviality of centralizer of non integrable Vector field X with
component $(P,Q)$ is equivalent to complete integrability of Hamiltonian
$zP+wQ$ in $\mathbb{R}^{4}$

Example 1 consider vector fields $X$ and $Y$ as follows,respectively :

$\begin{cases}\dot{x}=y+x(x^{2}+y^{2}-1)\\\
\dot{y}=-x+y(x^{2}+y^{2}-1),\end{cases}$

and

$\begin{cases}\dot{x}=2y+x(x^{2}+y^{2}-1)\\\
\dot{y}=-2x+y(x^{2}+y^{2}-1),\end{cases}$

$X$ and $Y$ are independent out of circle $x^{2}+y^{2}=1$.This circle is a
hyperbolic limit cycle for X and Y while we have $[X,Y]=0$

2) Choose an arbitrary homogeneous Vector field of degree $n+1$.For example:

$\begin{cases}\dot{x}=y(x^{2}+y^{2})^{\frac{n}{2}}\\\
\dot{y}=-x(x^{2}+y^{2})^{\frac{n}{2}},\end{cases}$

$Cyclicity$ of origin under perturbation of this Vector field among polynomial
Vector field of at most $n-degree$ is not less than $H(n)$.Now put X for above
Vector field and Y for the following linear center

$\begin{cases}\dot{x}=y\\\ \dot{y}=-x,\end{cases}$

$[X,Y]=0$,Is it possible that for any perturbation $X_{\epsilon}$ of $X$,one
have perturbation $Y_{\epsilon}$ with $[X_{\epsilon},Y_{\epsilon}]=0$?

Note that linear center has finite $cyclicity$ by analytic perturbation with
finite parameter(The cyclicity of a singularity of a vector field among a
family of vector fields is the maximum number of limit cycles which can be
produced around singularity,by small perturbation of the vector field in the
family,see $[5]$

3)Let we have a Vector field in $\mathbb{R}^{n}$Whose two first components
depend only on $x$ and $y$.Actually we have a planner Vector field with these
two components. Existence of invariant compact $submanifold$ of codimension at
most $2$ could lead to existence of closed orbit in planner system. since
projection of such $submanifold$ on two first component can not be a single
point.

4)Any Vector field on a surface defines a singular foliation of dimension one
and limit cycles are $seperetrix$ leaves .according to definition in [8]. It
would be interesting to produce some $C^{*}$ algebraic invariants depending
only on degree of polynomial Vector fields in the plane.

5)In $[1]$,it is given a uniform upper bound,depending only on $n$, for the
length of a closed orbit of a polynomial vector field of degree $n$,if we
replace the usual riamannian metrics of the plane by the metrics of the upper
half sphere.on the other hand,it is well known that the number of closed
geodesics of a surface with negative curvature is bounded,uniformly,by the
length of the closed geodesics.considering these two subjects,Can we equip the
phase portrait of a certain polynomial vector field,ex.lienard system,with an
appropriate riemannian metrics,which curvature is negative out of a finite
number of analytic curves,such that the trajectories be geodesics.Is it
possible to equip the punctured plane to a riemannian metric with negative
curvature such that the trajectories of the vander pol equation be
geodesics,in this case we could give another proof for the fact that the van
der pol equation can not have more than one limit cycle ,see $[2]$ for
information on the limit cycle of the vander pol equation.For a nice relation
between limit cycles and complex geometry ,see $[4]$

6)A possible relation to operator theory:In it is interpreted the number of
limit cycles of the lienard vector field $L$ in term of codimension of the
range of functional operator defined by $L$,$L(g)=L.g$,the derivative of $g$
along the trajectories of $L$.see $www.arxiv.org/abs/math.DS/0408037$ In
fact,if this operator could be bounded with a closed range,we would have a
nice interpretation of ”Fredholm index” for the number of limit cycles.what
Banach Functional space is appropriate for the domain of the operator
$L(g)=L.g$,such that the operator be a fredholm operator which index is equal
to the number of limit cycles?Can we equip the space of smooth or analytic
maps on the plane to the structure of a topological vector space such that the
corresponding operator be fredholm with the same index interpretation(I thank
A. Zeghib for his suggestion for consideration of TVS as a possible resolution
to this problem).Is the generalization of the theory of ”Fredholm Operators on
Banach space” for TVS,a trivial problem?.

Finally we give two conjectures related to subject 1:

Conjecture 1 .For analytic Vector field $X$ on the plane or sphere choose the
elements of $C(X)$ among analytic vector fields. $C(X)$ is a Vector space on
field of real number, If dimension of $C(X)$ is infinite then X is globally
analytic integrable.(Are there example of arbitrary large finite dimension
$C(X)$?)

Conjecture 2 .For a non Vanishing vector field X on the plane and positive
smooth function f, $C(X)$ is isomorph to $C(fX)$.If the the conjecture is true
we could actually assign a unique lie algebra ,up to isomorphism, to a smooth
foliation of the plane.

Example 2.Let an analytic vector field on sphere has a center and a limit
cycle Simultaneously then $C(X)$,the analytic centralizer, has dimension one.
put $V=Vanderpolvectorfeld$ then $C(V)$ has at most two dimension.(what is the
exact dimension of centralizer of van $derpol$ vector field?). In the example
1,$C(X)$ is a 2 dimensional lie algebra while the centralizer of the following
vector field(as a vector field on the plane or sphere) is a 4 dimensional
space

$\begin{cases}\dot{x}=x\\\ \dot{y}=y,\end{cases}$

## References

  * [1] J.-P. Francoise and C. C. Pugh, _Keeping track of limit cycles_ , J. Differential Equations 65, no. 2,1986.
  * [2] Hirsch, Smale, _Linear algebra, differential equations and dynamical systems_ , Academic Press, 1974.
  * [3] Yu.S.Ilyashenko, _Finiteness Theorems for Limit Cycles_ , AMS, Transl. 94, 1991.
  * [4] Yu.R.Romanovski, _Limit Cycles and Complex Geometry_ ,St.petersburg Math.J., Vol 8,No. 3 , 1997.
  * [5] R.Roussarie, _Bifurcation of planar vector fields and Hilbert’s sixteenth problem_ , Birkhauser Verlag, Basel, 1998.
  * [6] S.Shahshahan, _periodic solutions of polynomial first order Differential Equation_ , Nonlinrear Analysis theory method application,Vol 5,no 2 (1981).
  * [7] X.Wang, _On the $C^{*}$ Algebras of Foliation in the plane_, Lecture Note in Mathematics, 1257.