#  Cellular automata traffic flow model derived through the ultradiscrete
limit of the correlated random walk

Akiko Fukuda
Department of Mathematical Sciences,  Shibaura Institute of Technology,
Minuma, Saitama, 337-8570, Japan

Etsuo Segawa
Graduate School of Environment and Information Sciences, Yokohama National
University
Hodogaya, Yokohama 240-8501, Japan

Sennosuke Watanabe
Faculty of Informatics, The University of Fukuchiyama
Azahori, Fukuchiyama, 620-0886, Japan

Abstract. In this paper, we show that a generalization of the discrete Burgers
equation can be obtained by a kind of discrete Cole–Hopf transformation to the
discrete diffusion equation corresponding to the correlated random walk, which
is also known as a generalization of the well known random walks. By applying
the technique called ultradiscretization, we obtain the generalization of the
ultradiscrete diffusion equation, the ultradiscrete Cole–Hopf transformation
and the ultradiscrete Burgers equation. Moreover, we show that the resulting
ultradiscrete Burgers equation yields cellular automata. The relationship of
the ultradiscrete Burgers equation to the traffic flow is also discussed.

000 AMS 2000 subject classifications:  60F05, 05C50, 15A15, 05C60 000 PACS:
37B15, 39A12, 60G50. 000 Keywords:  Correlated random walk; traffic flow
model; cellular automata; discrete Burgers equation; Cole–Hopf transformation;
ultradiscretization

##  1 Introduction

It is well known that the Burgers equation can be obtained from the continuous
diffusion equation by a variable transformation called the Cole–Hopf
transformation [2, 6]. Moreover, it is shown in [5] that for the discrete
diffusion equation

$\displaystyle f_{j}^{n+1}=\dfrac{1}{2}(f_{j+1}^{n}+f_{j-1}^{n}),$ (1)

the discrete Cole–Hopf transformation

$\displaystyle u_{j}^{n}=\dfrac{f_{j+1}^{n}}{f_{j}^{n}}$ (2)

yields the discrete Burgers equation

$\displaystyle
u_{j}^{n+1}=u_{j}^{n}\dfrac{u_{j+1}^{n}+1/u_{j}^{n}}{u_{j}^{n}+1/u_{j-1}^{n}}.$
(3)

Here, the discrete diffusion equation (1) is equivalent to the evolution
equation of the isotropic random walk. Moreover, it is also known that a
similar relationship can be obtained in [11] by ultradiscretization. The
ultradiscrete diffusion equation

$\displaystyle F_{j}^{n+1}=\max\left(F_{j-1}^{n},F_{j+1}^{n}\right),$ (4)

transforms into the ultradiscrete Burgers equation

$\displaystyle
U_{j}^{n+1}=U_{j}^{n}+\min\left(U_{j-1}^{n},L-U_{j}^{n},\right)-\min\left(U_{j}^{n},L-U_{j+1}^{n}\right)$
(5)

through the ultradiscrete Cole–Hopf transformation. The ultradiscrete Burgers
equation coincides with the elementary cellular automata of rule 184, which is
regarded as a simple traffic flow model. Originating from this model, some
generalizations, interpretation as traffic flow, and their mathematical
analyses are studied in [3, 4, 11, 14, 15, 17].

The correlated random walk is a generalization of the random walk which
depends on the previous position of a particle [8, 13]. This model can be
converted to a walk model in which the walker has a two-dimensional internal
state $\mathbb{C}^{2}$ whose bases are represented by $|L\rangle=[1,0]^{\top}$
and $|R\rangle=[0,1]^{\top}$, and the moving weights to the left and right
neighbors are given by two-dimensional matrices $P$ and $Q$ so that $P+Q$ is a
transition matrix which preserves the $\ell^{1}$ norm. A quantum walk [7, 9,
12] is known as a quantum analogue of the correlated random walk in that the
matrix $P+Q$ is changed to a unitary matrix which preserves the
$\ell^{2}$-norm. In our previous work [16], we introduced an analogue of the
quantum walk over the max-plus algebra, which has a close relationship with
the ultradiscretization, and found that the Frobenius norm on the max-plus
algebra is a conservation quantity.

In this paper, we focus on the correlated random walk and discuss the related
equations and cellular automata. We here refer to the evolution equation of
the correlated random walk as the CRW-type diffusion equation. We first show
that by introducing a discrete Cole–Hopf transformation, the CRW-type
diffusion equation is transformed into an extension of the discrete Burgers
equation, which we call the CRW-type discrete Burgers equation. Secondly, by
applying the ultradiscretization to the CRW-types of the discrete diffusion
equation, discrete Cole–Hopf transformation and discrete Burgers equation, we
obtain the CRW-types of the ultradiscrete diffusion equation, ultradiscrete
Cole–Hopf transformation, and ultradiscrete Burgers equation, respectively. We
thirdly show that the resulting CRW-type ultradiscrete Burgers equation can be
regarded as a traffic flow model.

The rest of the paper is organized as follows. In Section 2, we derive the
CRW-types of the discrete diffusion equation, discrete Cole–Hopf
transformation and discrete Burgers equation. In Section 3, we discuss the
ultradiscretization of the CRW-types of the discrete diffusion equation,
discrete Cole–Hopf transformation and discrete Burgers equation. In Section 4,
we show that the CRW-type ultradiscrete Burgers equation can be regarded as
the cellular automata. In Section 5, we show that the cellular automata shown
in Section 4 can be regarded as the traffic flow. The fundamental diagram of
the traffic flow model is also discussed. Finally in Section 6, concluding
remarks are given.

##  2 Discrete diffusion equation induced by a correlated random walk and its
discrete Cole–Hopf transformation

Let us consider the random walk model on the one-dimensional lattice in which
a particle moves left and right neighbors with probabilities $1/2$ and $1/2$
respectively. The discrete diffusion equation (1) is nothing but the time
evolution of this random walk; that is, $f_{j}^{n}$ corresponds to the finding
probability at discrete time $n$ and position $j$.

Now let us consider the correlated random walk on the one-dimensional lattice
which is a generalization of the above random walk. In the correlated random
walk, the probabilities of a particle at each position associated with moving
left and right are determined by the directions that a particle comes into the
position. Then let $\mu_{L}^{n}(j)$ and $\mu_{R}^{n}(j)$ be the probabilities
that a particle moves to the position $j$ from the positions $j+1$ and $j-1$
at discrete time $n$, respectively. The time evolution of the correlated
random walk with parameters $p,q\in[0,1]$ is denoted by

$\displaystyle\begin{cases}\mu_{L}^{n+1}(j)=p\mu_{L}^{n}(j+1)+(1-q)\mu_{R}^{n}(j+1),\\\
\mu_{R}^{n+1}(j)=(1-p)\mu_{L}^{n}(j-1)+q\mu_{R}^{n}(j-1).\end{cases}$ (6)

Here, the parameter $p$ (resp. $q$) is the probability that the leftward
(resp. rightward) movement is repeated two times in a row, respectively. Note
that if $p=q=1/2$, then the discrete diffusion equation (1) is recovered.

In the following, we set $p=q$ for simplicity. Then the second equation of (6)
is reduced to

$\displaystyle\mu_{L}^{n}(j-1)=\dfrac{1}{1-p}(\mu_{R}^{n+1}(j)-p\mu_{R}^{n}(j-1)).$

Inserting this into the first equation of (6), we have the following
recurrence equation of $\mu_{R}^{(n)}(j)$:

$\displaystyle\dfrac{1}{1-p}(\mu_{R}^{n+2}(j+1)-p\mu_{R}^{n+1}(j))$
$\displaystyle\qquad=\dfrac{p}{1-p}(\mu_{R}^{n+1}(j+2)-p\mu_{R}^{n}(j+1))+(1-p)\mu_{R}^{n}(j+1).$
(7)

Let us put $f_{j}^{n}:=\mu_{R}^{n}(j)$. The equation (7) implies

$\displaystyle
f_{j+1}^{n+2}=pf_{j}^{n+1}+pf_{j+2}^{n+1}+\\{p(1-p)^{2}-p^{2}\\}f_{j+1}^{n}$

Then we obtain the following three-term recurrence equation representing the
correlated random walk:

$\displaystyle f_{j}^{n+1}=p(f_{j-1}^{n}+f_{j+1}^{n})-(2p-1)f_{j}^{n-1}.$ (8)

If $p=1/2$, the time evolution of the usual random walk (1) appears. We call
(8) the CRW-type discrete diffusion equation.

Next, let us apply a discrete Cole–Hopf transformation to the time evolution
equation of the correlated random walk (8). Through a consideration of the
usual discrete Cole–Hopf transformation (2) of the random walk (1), we define
another discrete Cole–Hopf transformation of the correlated random walk by the
following pair of the spatial and temporal ratios of the finding
probabilities:

$\displaystyle u_{j}^{n}=\dfrac{f_{j+1}^{n}}{f_{j}^{n}},\quad
v_{j}^{n}=\dfrac{f_{j}^{n+1}}{f_{j}^{n}}.$ (9)

Then, inserting (8) into (9), we see that $u_{j}^{n}$ and $v_{j}^{n}$ must
satisfy the following recursions:

$\displaystyle\begin{cases}u_{j}^{n+1}=u_{j}^{n}\cdot\dfrac{p(u_{j+1}^{n}+1/u_{j}^{n})-(2p-1)\cdot
1/v_{j+1}^{n-1}}{p(u_{j}^{n}+1/u_{j-1}^{n})-(2p-1)\cdot 1/v_{j}^{n-1}},\\\
v_{j}^{n+1}=v_{j}^{n}\cdot\dfrac{p(u_{j}^{n+1}+1/u_{j-1}^{n+1})-(2p-1)\cdot
1/v_{j}^{n}}{p(u_{j}^{n}+1/u_{j-1}^{n})-(2p-1)\cdot
1/v_{j}^{n-1}}.\end{cases}$ (10)

We call (10) the CRW-type discrete Burgers equation. Note that if we put
$p=1/2$, (10), the first equation (10) coincides with the discrete Burgers
equation (3).

##  3  Ultradiscretization of the CRW-type discrete diffusion equation and its
Cole–Hopf transformation

In this section we will give an ultradiscretization of the CRW-type discrete
diffusion equation (8) and its Cole–Hopf transformation.

Let a variable transformation be

$\displaystyle f_{j}^{n}=p^{n}e^{F_{j}^{n}/\varepsilon}.$ (11)

By applying (11) to (8), we obtain

$\displaystyle
e^{F_{j}^{n+1}/\varepsilon}=e^{F_{j-1}^{n}/\varepsilon}+e^{F_{j+1}^{n}/\varepsilon}+\dfrac{1-2p}{p^{2}}e^{F_{j}^{n-1}/\varepsilon}.$

Here, we assume that $\dfrac{1-2p}{p^{2}}\geq 0$, that is, $0\leq p\leq 1/2$,
and let

$\displaystyle\dfrac{1-2p}{p^{2}}=e^{R/\varepsilon},$

then we have

$\displaystyle
e^{F_{j}^{n+1}/\varepsilon}=e^{F_{j-1}^{n}/\varepsilon}+e^{F_{j+1}^{n}/\varepsilon}+e^{R/\varepsilon}e^{F_{j}^{n-1}/\varepsilon}.$

Taking the $\log$ and multiplying both sides of the equation by $\varepsilon$,
we have

$\displaystyle\varepsilon\log
e^{F_{j}^{n+1}/\varepsilon}=\varepsilon\log\left(e^{F_{j-1}^{n}/\varepsilon}+e^{F_{j+1}^{n}/\varepsilon}+e^{R/\varepsilon}e^{F_{j}^{n-1}/\varepsilon}\right).$

Taking a limit $\varepsilon\to+0$ on the above equation, we obtain

$\displaystyle
F_{j}^{n+1}=\max\left(F_{j-1}^{n},F_{j+1}^{n},R+F_{j}^{n-1}\right),\quad
R\geq-\infty.$ (12)

We call (12) the CRW-type ultradiscrete diffusion equation. Here, if
$R=-\infty$, then (12) coincides with the ultradiscrete diffusion equation
(4).

Next, we will apply the ultradiscretization to the discrete Cole–Hopf
transformation (9). Let us introduce new variable transformations as

$\displaystyle u_{j}^{n}=e^{(U_{j}^{n}-L/2)/\varepsilon},\quad
v_{j}^{n}=e^{(V_{j}^{n}-L/2)/\varepsilon}.$ (13)

By applying the variable transformation (13) into (9), we have

$\displaystyle
e^{(U_{j}^{n}-L/2)/\varepsilon}=\dfrac{e^{F_{j+1}^{n}/\varepsilon}}{e^{F_{j}^{n}/\varepsilon}},\quad
e^{(V_{j}^{n}-L/2)/\varepsilon}=\dfrac{e^{F_{j}^{n+1}/\varepsilon}}{e^{F_{j}^{n}/\varepsilon}}.$

Taking the ultradiscrete limit, it holds that

$\displaystyle\begin{cases}U_{j}^{n}=F_{j+1}^{n}-F_{j}^{n}+L/2,\\\
V_{j}^{n}=F_{j}^{n+1}-F_{j}^{n}+L/2.\end{cases}$ (14)

We call (14) the CRW-type ultradiscrete Cole–Hopf transformation.

Next, we apply the CRW-type ultradiscrete Cole–Hopf transformation (14) to the
CRW-type ultradiscrete diffusion equation (12). For the 1st equation of (14)
at discrete time $n+1$, substitute (12) for $F_{j}^{n+1}$

$\displaystyle U_{j}^{n+1}$
$\displaystyle=\max\left(F_{j}^{n},F_{j+2}^{n},R+F_{j+1}^{n-1}\right)-\max\left(F_{j-1}^{n},F_{j+1}^{n},R+F_{j}^{n-1}\right)+L/2$
$\displaystyle=(F_{j+1}^{n}-F_{j}^{n}+L/2)$
$\displaystyle\qquad+\max\left(F_{j}^{n}-F_{j+1}^{n},F_{j+2}^{n}-F_{j+1}^{n},R+F_{j+1}^{n-1}-F_{j+1}^{n}\right)$
$\displaystyle\qquad-\max\left(F_{j-1}^{n}-F_{j}^{n},F_{j+1}^{n}-F_{j}^{n},R+F_{j}^{n-1}-F_{j}^{n}\right)$
$\displaystyle=U_{j}^{n}+\max\left(-U_{j}^{n}+L/2,U_{j+1}^{n}-L/2,R-V_{j+1}^{n-1}+L/2\right)$
$\displaystyle\qquad-\max\left(-U_{j-1}^{n}+L/2,U_{j}^{n}-L/2,R-V_{j}^{n-1}+L/2\right)$
$\displaystyle=U_{j}^{n}+\max\left(-U_{j}^{n},U_{j+1}^{n}-L,R-V_{j+1}^{n-1}\right)-\max\left(-U_{j-1}^{n},U_{j}^{n}-L,R-V_{j}^{n-1}\right)$
$\displaystyle=U_{j}^{n}+\min\left(U_{j-1}^{n},L-U_{j}^{n},V_{j}^{n-1}-R\right)-\min\left(U_{j}^{n},L-U_{j+1}^{n},V_{j+1}^{n-1}-R\right).$

In the same way, the 2nd equation of (14) at discrete time $n+1$ is
transformed to

$\displaystyle
V_{j}^{n+1}=V_{j}^{n}+\min\left(U_{j-1}^{n},L-U_{j}^{n},V_{j}^{n-1}-R\right)-\min\left(U_{j-1}^{n+1},L-U_{j}^{n+1},V_{j}^{n}-R\right).$

Therefore, the ultradiscrete Cole–Hopf transformation (14) of CRW-type
ultradiscrete diffusion equation (12) yields

$\displaystyle\begin{cases}U_{j}^{n+1}=U_{j}^{n}+\min\left(U_{j-1}^{n},L-U_{j}^{n},V_{j}^{n-1}-R\right)-\min\left(U_{j}^{n},L-U_{j+1}^{n},V_{j+1}^{n-1}-R\right),\\\
V_{j}^{n+1}=V_{j}^{n}+\min\left(U_{j-1}^{n},L-U_{j}^{n},V_{j}^{n-1}-R\right)-\min\left(U_{j-1}^{n+1},L-U_{j}^{n+1},V_{j}^{n}-R\right).\end{cases}$
(15)

We call (15) the CRW-type ultradiscrete Burgers equation. In the case that
$R=-\infty$, the 1st equation of (15) coincides with (5).

Next we apply the ultradiscretization into the CRW-type discrete Burgers
equation (10). Let us recall (13) and introduce the new variable
transformation

$\displaystyle\dfrac{1-2p}{p}=e^{R/\varepsilon}.$

Then the 1st equation of (10) yields

$\displaystyle e^{(U_{j}^{n+1}-L/2)/\varepsilon}$
$\displaystyle\quad=e^{(U_{j}^{n}-L/2)/\varepsilon}\cdot\dfrac{(e^{(U_{j+1}^{n}-L/2)/\varepsilon}+1/e^{(U_{j}^{n}-L/2)/\varepsilon})+e^{R/\varepsilon}\cdot
1/e^{(V_{j+1}^{n-1}-L/2)/\varepsilon}}{(e^{(U_{j}^{n}-L/2)/\varepsilon}+1/e^{(U_{j-1}^{n}-L/2)/\varepsilon})+e^{R/\varepsilon}\cdot
1/e^{(V_{j}^{n-1}-L/2)/\varepsilon}}.$

Taking the ultradiscrete limit into the above equation, we obtain

$\displaystyle U_{j}^{n+1}=U_{j}^{n}$
$\displaystyle+\min(L-U_{j}^{n},~{}U_{j-1}^{n},~{}V_{j}^{n-1}-R)$
$\displaystyle-\min(L-U_{j+1}^{n},~{}U_{j}^{n},~{}V_{j+1}^{n-1}-R).$

Similarly, the 2nd equation of (10) yields

$\displaystyle V_{j}^{n+1}=V_{j}^{n}$
$\displaystyle-\min(L-U_{j}^{n+1},~{}U_{j-1}^{n+1},~{}V_{j}^{n}-R)$
$\displaystyle+\min(L-U_{j}^{n},~{}U_{j-1}^{n},~{}V_{j}^{n-1}-R).$

We can see that the ultradiscrete limit

$\displaystyle\begin{cases}U_{j}^{n+1}=U_{j}^{n}+\min(U_{j-1}^{n},~{}L-U_{j}^{n},~{}V_{j}^{n-1}-R)-\min(U_{j}^{n},~{}L-U_{j+1}^{n},~{}V_{j+1}^{n-1}-R),\\\
V_{j}^{n+1}=V_{j}^{n}+\min(U_{j-1}^{n},~{}L-U_{j}^{n},~{}V_{j}^{n-1}-R)-\min(U_{j-1}^{n+1},~{}L-U_{j}^{n+1},~{}V_{j}^{n}-R)\end{cases}$

of the CRW-type Burgers equation (10) coincides with (15) which is derived
through the CRW-type Cole–Hopf transformation (14) of the CRW-type
ultradiscrete diffusion equation (12).

##  4 The CRW-type ultradiscrete Burgers equation and cellular automata

In the CRW-type ultradiscrete Burgers equation (15), let $R=-\infty$, then the
1st equation,

$\displaystyle
U_{j}^{n+1}=U_{j}^{n}+\min(L-U_{j}^{n},~{}U_{j-1}^{n})-\min(L-U_{j+1}^{n},~{}U_{j}^{n}),$

coincides with the ultradiscrete Burgers equation (5), which is equivalent to
the elementary cellular automata of rule 184 if we set $L=1$ and the initial
values are in $\\{0,1\\}$. Let $\tilde{V}_{j}^{n}:=V_{j}^{n}-R$. Then the CRW-
type ultradiscrete Burgers equation (15) transforms into

$\displaystyle\begin{cases}U_{j}^{n+1}=U_{j}^{n}+\min(U_{j-1}^{n},~{}L-U_{j}^{n},~{}\tilde{V}_{j}^{n-1})-\min(U_{j}^{n},~{}L-U_{j+1}^{n},~{}\tilde{V}_{j+1}^{n-1}),\\\
\tilde{V}_{j}^{n+1}=\tilde{V}_{j}^{n}+\min(U_{j-1}^{n},~{}L-U_{j}^{n},~{}\tilde{V}_{j}^{n-1})-\min(U_{j-1}^{n+1},~{}L-U_{j}^{n+1},\tilde{V}_{j}^{n}),\end{cases}$
(16)

in which the parameter $R$ is deleted. For the CRW-type ultradiscrete Burgers
equation (15), let
$X_{j}^{n}=\min(U_{j-1}^{n},~{}L-U_{j}^{n},~{}\tilde{V}_{j}^{n-1})$; then (16)
can be rewritten as

$\displaystyle\begin{cases}U_{j}^{n+1}=U_{j}^{n}+X_{j}^{n}-X_{j+1}^{n},\\\
\tilde{V}_{j}^{n+1}=\tilde{V}_{j}^{n}+X_{j}^{n}-X_{j}^{n+1}.\end{cases}$ (17)

Here we assume that the sites $j$ satisfy the periodic boundary condition with
integer period $N$, i.e.,
$U_{j}^{n}=U_{j+N}^{n},\tilde{V}_{j}^{n}=\tilde{V}_{j+N}^{n}$. In the
following Theorem 4.1, we discuss the initial condition that the values of
$U_{j}^{n}$ and $\tilde{V}_{j}^{n}$ for any $j$ are in the closed interval
independent of $n$.

######  Theorem 4.1.

In the CRW-type ultradiscrete Burgers equation (16), we assume that

$\displaystyle 0\leq U_{j}^{0}\leq L,\quad
0\leq\tilde{V}_{j}^{-1}+\tilde{V}_{j}^{0}\leq L.$ (18)

Then, for any discrete time $n\geq 1$, it holds that

$\displaystyle 0\leq U_{j}^{n}\leq L,\quad 0\leq\tilde{V}_{j}^{n}\leq L.$ (19)

###### Proof.

This proof is given by induction with respect to $n$. We assume that (19)
holds true for the discrete time less than or equal to $n$. In the 1st
equation of (16), we have

$\displaystyle U_{j}^{n+1}$
$\displaystyle=U_{j}^{n}+\min(U_{j-1}^{n},~{}L-U_{j}^{n},~{}\tilde{V}_{j}^{n-1})-\min(U_{j}^{n},~{}L-U_{j+1}^{n},~{}\tilde{V}_{j+1}^{n-1})$
$\displaystyle=\min(U_{j-1}^{n}+U_{j}^{n},~{}L,~{}\tilde{V}_{j}^{n-1}+U_{j}^{n})-\min(U_{j}^{n},~{}L-U_{j+1}^{n},~{}\tilde{V}_{j+1}^{n-1}).$
(20)

The 1st term of (20) yields

$\displaystyle\min(U_{j-1}^{n}+U_{j}^{n},~{}L,~{}\tilde{V}_{j}^{n-1}+U_{j}^{n})\leq
L,$

and, from the assumption of the induction, the 2nd term holds

$\displaystyle\min(U_{j}^{n},~{}L-U_{j+1}^{n},~{}\tilde{V}_{j+1}^{n-1})\geq
0.$

Therefore we have $U_{j}^{n+1}\leq L$. On the other hand, the 1st equation of
(16) can also be written as

$\displaystyle U_{j}^{n+1}$
$\displaystyle=\min(U_{j-1}^{n},~{}L-U_{j}^{n},~{}\tilde{V}_{j}^{n-1})-\min(0,~{}L-U_{j+1}^{n}-U_{j}^{n},~{}\tilde{V}_{j+1}^{n-1}-U_{j}^{n}).$

Here, the 1st term of the right-hand side satisfies

$\displaystyle\min(U_{j-1}^{n},~{}L-U_{j}^{n},~{}\tilde{V}_{j}^{n-1})\geq 0,$

and the 2nd term satisfies

$\displaystyle\min(0,~{}L-U_{j+1}^{n}-U_{j}^{n},~{}\tilde{V}_{j+1}^{n-1}-U_{j}^{n})\leq
0.$

Hence we have $U_{j}^{n+1}\geq 0$. Therefore we obtain $0\leq U_{j}^{n+1}\leq
L$.

In the 2nd equation of (16), we have

$\displaystyle\tilde{V}_{j}^{n+1}$
$\displaystyle=\tilde{V}_{j}^{n}+\min(U_{j-1}^{n},~{}L-U_{j}^{n},~{}\tilde{V}_{j}^{n-1})-\min(U_{j-1}^{n+1},~{}L-U_{j}^{n+1},~{}\tilde{V}_{j}^{n})$
$\displaystyle=\min(U_{j-1}^{n},~{}L-U_{j}^{n},~{}\tilde{V}_{j}^{n-1})-\min(U_{j-1}^{n+1}-\tilde{V}_{j}^{n},~{}L-U_{j}^{n+1}-\tilde{V}_{j}^{n},~{}0).$
(21)

Here, from the assumption of the induction, the 1st term of (21) holds

$\displaystyle\min(U_{j-1}^{n},~{}L-U_{j}^{n},~{}\tilde{V}_{j}^{n-1})\geq 0,$

and the 2nd term holds

$\displaystyle\min(U_{j-1}^{n+1}-\tilde{V}_{j}^{n},~{}L-U_{j}^{n+1}-\tilde{V}_{j}^{n},~{}0)\leq
0.$

Hence we have $\tilde{V}_{j}^{n+1}\geq 0$. In the 2nd equation of (17), we
take the summation from $0$ to $n$ on both sides of the equation, and then we
have

$\displaystyle\sum_{p=0}^{n}(\tilde{V}_{j}^{p+1}-\tilde{V}_{j}^{p})=\sum_{p=0}^{n}(X_{j}^{p}-X_{j}^{p+1}).$

Here, the left- and right-hand sides are
$-\tilde{V}_{j}^{0}+\tilde{V}_{j}^{n+1}$ and $X_{j}^{0}-X_{j}^{n+1}$,
respectively. Therefore we have

$\displaystyle\tilde{V}_{j}^{n+1}$
$\displaystyle=X_{j}^{0}-X_{j}^{n+1}+\tilde{V}_{j}^{0}$
$\displaystyle=\min(U_{j-1}^{0},~{}L-U_{j}^{0},~{}\tilde{V}_{j}^{-1})-\min(U_{j-1}^{n+1},~{}L-U_{j}^{n+1},~{}\tilde{V}_{j}^{n})+\tilde{V}_{j}^{0}$
$\displaystyle=\min(U_{j-1}^{0}+\tilde{V}_{j}^{0},~{}L-U_{j}^{0}+\tilde{V}_{j}^{0},~{}\tilde{V}_{j}^{-1}+\tilde{V}_{j}^{0})-\min(U_{j-1}^{n+1},~{}L-U_{j}^{n+1},~{}\tilde{V}_{j}^{n}).$

From the assumption (18), the 1st term of the above equation holds

$\displaystyle\min(U_{j-1}^{0}+\tilde{V}_{j}^{0},~{}L-U_{j}^{0}+\tilde{V}_{j}^{0},~{}\tilde{V}_{j}^{-1}+\tilde{V}_{j}^{0})\leq
L$

and $0\leq U_{j}^{n+1}\leq L$, which we already proved, and the 2nd term holds

$\displaystyle\min(U_{j-1}^{n+1},~{}L-U_{j}^{n+1},~{}\tilde{V}_{j}^{n})\geq
0.$

So we have $\tilde{V}_{j}^{n+1}\leq L$. Therefore we have
$0\leq\tilde{V}_{j}^{n+1}\leq L$. $\Box$

From the Theorem 4.1, we see that the CRW-type ultradiscrete Burgers equation
(16) can be regarded as the cellular automata with state
$U_{j}^{n}\in\\{0,1,\dots,L\\}$ and $\tilde{V}_{j}^{n}\in\\{0,1,\dots,L\\}$.
From the 2nd equation of (17), we have

$\displaystyle\tilde{V}_{j}^{n}=-X_{j}^{n}+\min(U_{j-1}^{0},~{}L-U_{j}^{0},~{}\tilde{V}_{j}^{-1})+\tilde{V}_{j}^{0}.$
(22)

Here, we introduce

$\displaystyle
I_{j}^{0}:=\min(U_{j-1}^{0},~{}L-U_{j}^{0},~{}\tilde{V}_{j}^{-1})+\tilde{V}_{j}^{0},$

which is determined by the initial values of the CRW-type ultradiscrete
Burgers equation. Hence we have the following theorem.

######  Theorem 4.2.

In the CRW-type ultradiscrete Burgers equation (16), let us assume that $0\leq
U_{j}^{0}\leq L$, $\tilde{V}_{j}^{-1}\geq 0$ and $\tilde{V}_{j}^{0}\geq 0$.
Then, for any discrete time $n\geq 1$, it holds that

$\displaystyle 0\leq U_{j}^{n}\leq L,\quad 0\leq\tilde{V}_{j}^{n}\leq
I_{j}^{0}.$ (23)

###### Proof.

The first equation of (23) is already proved in Theorem 4.1. For the 2nd
equation of (23), from (22), we easily have

$\displaystyle\tilde{V}_{j}^{n}=-X_{j}^{n}+I_{j}^{0}.$ (24)

From $X_{j}^{n}\geq 0$, we have $\tilde{V}_{j}^{n}\leq I_{j}^{0}$. $\Box$

######  Corollary 4.3.

Let $M:=\displaystyle\max_{j\in\mathbb{Z}}I_{j}^{0}<\infty$; then the CRW-type
ultradiscrete Burgers equation (16) yields cellular automata of
$(U_{j}^{n},\tilde{V}_{j}^{n})\in\\{0,1,\dots,L\\}\times\\{0,1,\dots,M\\}$.

Fuzzy cellular automata are known as cellular automata that extend the range
of elementary cellular automata from $\\{0,1\\}$ to $[0,1]\subset\mathbb{R}$
[1]. It is known that the straightforward fuzzification of generalized
cellular automata whose range is $\\{0,1,\dots,L\\}$ is difficult. Recently, a
skillful fuzzification technique for generalized cellular automata was
introduced by some of authors in [10]. However, in the proof of Theorem 4.1,
$U_{j}^{n}$ and $\tilde{V}_{j}^{n}$ are not assumed to be integers. Therefore,
it is remarkable to note that the range
$(U_{j}^{n},\tilde{V}_{j}^{n})\in\\{0,1,\dots,L\\}\times\\{0,1,\dots,M\\}$ can
be directly generalized into
$(U_{j}^{n},\tilde{V}_{j}^{n})\in[0,L]\times[0,M]$ in Corollary 4.3.

##  5 The CRW-type Burgers cellular automata

Let us refer to the cellular automata derived from the CRW-type ultradiscrete
Burgers equation (16) as the CRW-type Burgers cellular automata. In this
section, we show that the CRW-type Burgers cellular automata can be regarded
as a kind of traffic flow model. We also discuss the fundamental diagram of
the traffic flow model.

###  5.1 Interpretation of the CRW-type Burgers cellular automata as a traffic
flow model

Let $U_{j}^{n}$ be the number of cars at site $j$ and discrete time $n$ and
let $\tilde{V}_{j}^{n-1}$ denote the maximum inflow, namely, the upper limit
of the number of cars that can move from site $j-1$ to $j$ in the transition
from discrete time $n$ to $n+1$. We here assume that each site contains at
most $L$ cars. Then,
$X_{j}^{n}=\min(U_{j-1}^{n},~{}L-U_{j}^{n},~{}\tilde{V}_{j}^{n-1})$ represents
the inflow toward site $j$ at discrete time $n$. Therefore the 1st equation of
the CRW-type ultradiscrete Burgers equation (17) represents the update of the
number of cars as follows.

$\displaystyle\underbrace{U_{j}^{n+1}}_{\begin{subarray}{c}{\rm
number~{}of~{}cars}\\\ {\rm at~{}discrete~{}time}~{}n+1~{}\\\ {\rm
and~{}site}~{}j\end{subarray}}=\underbrace{U_{j}^{n}}_{\begin{subarray}{c}{\rm
number~{}of~{}cars}\\\ {\rm at~{}discrete~{}time}~{}n~{}\\\ {\rm
and~{}site}~{}j\end{subarray}}+\underbrace{X_{j}^{n}}_{\begin{subarray}{c}{\rm
inflow~{}toward~{}site~{}}j\\\ {\rm
at~{}discrete~{}time~{}}n\end{subarray}}-\underbrace{X_{j+1}^{n}.}_{\begin{subarray}{c}{\rm
outflow~{}toward~{}site~{}}j+1\\\ {\rm
at~{}discrete~{}time~{}}n\end{subarray}}$

The following theorem states that the CRW-type ultradiscrete Burgers equation
(16) follows the conservation law.

######  Theorem 5.1.

Let $N$ be the number of sites and impose the periodic boundary condition on
the CRW-type ultradiscrete Burgers equation (16). Then, in (16), for any
discrete time $n$, it holds that

$\displaystyle\sum_{j=0}^{N-1}U_{j}^{n+1}=\sum_{j=0}^{N-1}U_{j}^{n}.$

###### Proof.

In the 1st equation of (17), let us take the summation from 0 to $N$. Then we
have

$\displaystyle\sum_{j=0}^{N-1}U_{j}^{n+1}=\sum_{j=0}^{N-1}U_{j}^{n}+\sum_{j=0}^{N-1}(X_{j}^{n}-X_{j+1}^{n}).$

From $\sum_{j=0}^{N-1}(X_{j}^{n}-X_{j+1}^{n})=X_{0}^{n}-X_{N}^{n}$ and
considering the periodic boundary condition, we have

$\displaystyle\sum_{j=0}^{N-1}U_{j}^{n+1}=\sum_{j=0}^{N-1}U_{j}^{n}.$

$\Box$

From Theorem 5.1, we see that the summation of the initial values
$U_{j}^{0},~{}j=0,1,\dots,N-1$ are conserved quantities, which means that the
total number of cars does not change with time.

In the following, let $\tilde{V}_{j}^{-1}=0$ for all $j$, then it holds that
$I_{j}^{0}=\tilde{V}_{j}^{0}$. Namely, for all discrete time $n\geq 1$,
$0<\tilde{V}_{j}^{n}\leq\tilde{V}_{j}^{0}$ holds in Theorem 4.2. Therefore,
under the condition $\tilde{V}_{j}^{-1}=0$, we can give arbitrary initial
values $\tilde{V}_{j}^{0}$, which means that, for each $j$, we can control the
upper bounds of $\tilde{V}_{j}^{n}$ by the initial values $\tilde{V}_{j}^{0}$.
Then the 2nd equation of the CRW-type ultradiscrete Burgers equation (17),
which is transformed into (24), can be interpreted as

$\displaystyle\underbrace{\tilde{V}_{j}^{n}}_{\begin{subarray}{c}{\rm
maximum~{}inflow~{}of}\\\ {\rm transition~{}from~{}}n+1{\rm~{}to~{}}n+2\\\
{\rm~{}at~{}site~{}}j-1{\rm~{}to~{}}j\end{subarray}}=\underbrace{V_{j}^{0}}_{\begin{subarray}{c}{\rm
potential~{}quantity}\\\
{\rm~{}of~{}movement~{}at~{}site~{}}j\end{subarray}}-\underbrace{X_{j}^{n},}_{\begin{subarray}{c}{\rm
inflow~{}toward~{}site~{}}j\\\ {\rm at~{}discrete~{}time~{}}n\end{subarray}}$

which means that the maximum inflow of transition at the next time (from
$n+1\to n+2$) can be determined by subtracting the amount of inflow to site
$j$ at the current time ($n\to n+1$) from the initially determined inflow
limit $\tilde{V}_{j}^{0}$ at site $j$. That is, whereas the maximum inflow
$\tilde{V}_{j}^{n}$ at discrete time $n$ decreases depending on the previous
inflow $\tilde{X}_{j}^{n}$, the upper bound of $\tilde{V}_{j}^{n}$ is
determined by $\tilde{V}_{j}^{0}$.

In the following, we give explanations of the movement of cars in the CRW-type
ultradiscrete Burgers equation (16) in the case of $L=1$,
$\tilde{V}_{j}^{-1}=0$ and $\tilde{V}_{j}^{0}\in\\{0,1\\}$ for all $j$. From
the 1st equation of (16) and (17) of $L=1$, the values of $X_{j}^{n}$,
$X_{j+1}^{n}$ and resulting $U_{j}^{n+1}$ according to the combinations of the
values $U_{j-1}^{n}$, $U_{j}^{n}$, $U_{j+1}^{n}$, $\tilde{V}_{j}^{n-1}$ and
$\tilde{V}_{j+1}^{n-1}$ are shown in Table 1.

Table 1: $X_{j}^{n}-X_{j+1}^{n}$ No. | $U_{j-1}^{n}$ | $U_{j}^{n}$ | $U_{j+1}^{n}$ | $\tilde{V}_{j}^{n-1}$ | $\tilde{V}_{j+1}^{n-1}$ | $X_{j}^{n}$ | $X_{j+1}^{n}$ | $U_{j}^{n+1}$ | Cases
---|---|---|---|---|---|---|---|---|---
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | I
2 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | I
3 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | I
4 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | I
5 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | I
6 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | I
7 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | I
8 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | I
9 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | VI
10 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | IV
11 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | VI
12 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | IV
13 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | II
14 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | II
15 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | II
16 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | II
17 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | V
18 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | V
19 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | III
20 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | III
21 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | V
22 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | V
23 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | III
24 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | III
25 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | VI
26 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | IV
27 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | VI
28 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | IV
29 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | II
30 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | II
31 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | II
32 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | II

In case I of Table 1, since there are no cars at site $j-1$ and $j$, there are
no movements of cars independent of the values of $\tilde{V}_{j}^{n-1}$. In
case II, there are cars at sites $j$ and $j+1$. So the cars at site $j$ can
not move to $j+1$ independent of the values of $\tilde{V}_{j}^{n-1}$. In case
III, since there is a car at site $j-1$, the site $j$ is empty, and the
maximum inflow $\tilde{V}_{j}^{n-1}=1$, the car at site $j-1$ moves to site
$j$ at discrete time $n+1$. In case IV, since there is a car at site $j$, the
site $j+1$ is empty, and the maximum inflow $\tilde{V}_{j+1}^{n-1}=1$, the car
at site $j$ moves to site $j+1$ at discrete time $n+1$. In case V, there is a
car at site $j-1$ and the site $j$ is empty. But the car at site $j-1$ can not
move because $\tilde{V}_{j}^{n-1}=0$. In case VI, there is a car at site $j$
and the site $j+1$ is empty. But the car at site $j$ can not move because
$\tilde{V}_{j+1}^{n-1}=0$.

In Figure 1, we share the figures of the time evolution of $U_{j}^{n}$ and
$\tilde{V}_{j}^{n}$ in the case that $L=1$. The horizontal and vertical axis
denote site $j=0,1,\dots,29$ and discrete time $t=-1,0,1,\dots,28$, from the
top, respectively. The white and black cells denote $0$ and $1$, respectively.
In Figure 1 the initial values of $\tilde{V}_{j}^{0}$ are set as
$\tilde{V}_{21}^{0}=0$ and $\tilde{V}_{j}^{0}=1$ for other $j$. For any $j$,
$U_{j}^{-1}$ is set to $0$ as a matter of convenience. The initial values of
$U_{j}^{0}$ are set as 0 or 1 randomly. At the point where
$\tilde{V}_{21}^{t}=0$, we can observe that the car $U_{20}^{t}$ can not move
forward and a traffic jam occurs.

Figure 1: Time evolution of $U_{j}^{n}$ (left) and $\tilde{V}_{j}^{n}$ (right)
in the case that $L=1$. Figure 2: Time evolution of $U_{j}^{n}$ (left) and
$\tilde{V}_{j}^{n}$ (right) in the case that $L=3$.

In Figure 2, we show the figure of the time evolution of $U_{j}^{n}$ and
$\tilde{V}_{j}^{n}$ in the case that $L=3$. The white, light gray, dark gray
and black cells denote 0, 1, 2 and 3, respectively. The initial values of
$\tilde{V}_{j}^{0}$ are set as $\tilde{V}_{8}^{0}=2$, $\tilde{V}_{21}^{0}=1$
and $\tilde{V}_{j}^{0}=3$ for other $j$. It can be observed that at most two
cars are allowed to move forward per unit of time at the point where
$\tilde{V}_{8}^{j}=2$, and at most one car at the point where
$\tilde{V}_{22}^{j}=1$. From the above, it can be said that the variable
$\tilde{V}_{j}^{t}$ behaves like a traffic flow controller.

###  5.2 Fundamental diagrams of the CRW-type Burgers cellular automata

Let us consider the fundamental diagrams of the CRW-type Burgers cellular
automata. The density is denoted by

$\displaystyle\rho=\dfrac{1}{NL}\sum_{j=1}^{N}U_{j}^{n}.$

The flow is defined as

$\displaystyle f_{\ell}^{n}$
$\displaystyle=\dfrac{1}{NL}\sum_{j=1}^{N}\min(V_{j+1}^{n-1},U_{j}^{n},L-U_{j+1}^{n})$
$\displaystyle=\dfrac{1}{NL}\sum_{j=1}^{N}X_{j+1}^{n}.$

Figures 3, 5 and 5 show the fundamental diagrams in the case that $L=1,2$ and
3, respectively. In these figures, we set $N=50$, and the initial values of
$U_{j}^{0}$ and $\tilde{V}_{j}^{0}$ are given randomly by integer values
between $[0,L]$ and $[1,L]$, respectively. In these figures,
$\tilde{V}_{\min}:=\min_{j=0,1,\dots,49}\tilde{V}_{j}^{0}=1$. Flows are
computed at $t=91,92,\dots,100$ and their average is plotted in the figures.

Figure 3: Fundamental diagram of $L=1$.

Figure 4: Fundamental diagram of $L=2$.

Figure 5: Fundamental diagram of $L=3$.

Figure 3 coincides with the fundamental diagram of the original traffic flow
model of the elementary cellular automata of rule 184. In Figures 5 and 5, the
values of the flow hit the ceiling and adopt a trapezoidal shape. We can see
the phase transitions at $\rho=0.25$ and 0.75 in Figure 5 and $\rho=0.1666...$
and 0.8333… in Figure 5. We can thus make the following conjecture.

######  Conjecture 5.2.

There exist two first-order phase transition densities, and their points are
given by $(\rho_{*},q_{*})$ and $(1-\rho_{*},q_{*})$, where

$\displaystyle\rho_{*}=q_{*}=\dfrac{\tilde{V}_{\min}}{2L}.$

##  6 Concluding remarks

In this paper, we focus on the correlated random walk, which is a kind of
generalization of the random walks, and we derive the related discrete and
ultradiscrete equations and cellular automata. The integrability of the
conventional diffusion equation and the Burgers equation has already been
studied, but that of our resulting equations has not yet been discussed, which
will be a subject for a future work. There are many studies on traffic flow
models based on Burgers cellular automata and its extensions, as mentioned in
Section 1. To the best of our knowledge, however, no studies have derived
cellular automata model through a generalization of the random walk, which
makes our present approach a highly original one. Consequently, we obtained an
unexpected result, that is, a new traffic flow model with functions that
control the traffic flow. In the study of the traffic flow model, it is
important to analyze the fundamental diagram, and specifically, to identify
the phase transition points. Our Conjecture 5.2 seems to be correct from an
experimental point of view. But the mathematical proof of the conjecture still
remains for a future work.

## Acknowledgments

This work was partially supported by the Grant-in-Aid for Early-Career
Scientists no.20K14367 and by the Grants-in-Aid for Scientific Research (C)
nos.19K03616 and 19K03624 from the Japan Society for the Promotion of Science
and the Research Origin for Dressed Photon.

## References

  * [1] G. Cattaneo, P. Flocchini, G. Mauri, C. Quaranta Vogliotti and N. Santoro, Cellular automata in fuzzy backgrounds, Physica D, 105 (1997), 105–120.
  * [2] J. D. Cole, On a quasilinear parabolic equation occurring in aerodynamics, Quart. Appl. Math., 9 (1951), 225–236.
  * [3] H. Emmerich and B. Kahng, A random cellular automaton related to the noisy Burgers equation, Physica A, 259 (1998), 81–89.
  * [4] M. Fukui, K. Nishinari, D. Takahashi and Y. Ishibashi, Metastable flows in a two-lane traffic model equivalent to extended Burger’s cellular automaton, Physica A, 303 (2002), 226–238.
  * [5] R. Hirota, Nonlinear Partial Difference Equations Reducible to Linear Equations, J. Phys. Soc. Jpn., 46 (1979), 312–332.
  * [6] E. Hopf, The partial differential equation $u_{t}+uu_{x}=\mu u_{xx}$, Comm. Pure Appl. Math., 3 (1950), 201–230.
  * [7] J. Kempe, Quantum random walks - an introductory overview, Contemporary Physics, 44 (2003), 307-327,
  * [8] N. Konno, Limit theorems and absorption problems for one-dimensional correlated random walks, Stoch. Models, 25 (2009), 29–49.
  * [9] N. Konno, Quantum walks, Lecture Notes in Mathematics, 1954, 309–452, Springer, 2018.
  * [10] Y. Nishida, S. Watanabe, A. Fukuda and Y. Watanabe, $q$-VFCA: $q$-state Vector-valued Fuzzy Cellular Automata, J. Cellular Automata, 15 (2020), 207–222.
  * [11] K. Nishinari and D. Takahashi, Analytical properties of ultradiscrete Burgers equation and rule-184 cellular automaton, J. Phys. A: Math. Gen., 31 (1998), 5439–5450.
  * [12] R. Portugal, Quantum Walks and Search Algorithms, Quantum Science and Technology, Springer, 2018.
  * [13] E. Renshaw and R. Henderson, The correlated random walk, J. Appl. Prob., 18 (1981), 403–414.
  * [14] J. Tian, Z. Yuan, B. Jia, M. Li and G. Jiang, The stabilization effect of the density difference in the modified lattice hydrodynamic model of traffic flow, Physica A, 391 (2012), 4476–4482.
  * [15] J. Wang, F. Sun, R. Cheng, and H. Ge, An extended car-following model considering the self-stabilizing driving behavior of headway, Physica A, 507 (2018), 347–357.
  * [16] S. Watanabe, A. Fukuda, E. Segawa and I. Sato, A walk on max-plus algebra, Lin. Alg. Appl., 598 (2020), 29–48.
  * [17] S. Xue, B. Jia, R. Jiang, X. Li, J. Shan, An improved Burgers cellular automaton model for bicycle flow, Physica A, 487 (2017), 164–177.


# On the conformal bending of a closed Riemannian manifold

Rirong Yuan  School of Mathematics, South China University of Technology,
Guangzhou 510641, China<EMAIL_ADDRESS>
###### Abstract.

In this paper, we bend a closed Riemannian manifold in the conformal class,
through solving a fully nonlinear equation. As a result, we prove that each
metric of quasi-negative Ricci curvature is conformal to a metric with
negative Ricci curvature.

##  1\. Introduction

In 1980s, Gao-Yau [5] proved that any closed three-manifold admits a metric
with negative Ricci curvature. The existence of negatively Ricci curved metric
was extended by Lohkamp [12] to higher dimensional closed manifolds.

One natural question to ask is: given a conformal class $[g]=\\{e^{2u}g:u\in
C^{\infty}(M)\\}$, is there a metric with negative Ricci curvature.

When $M$ is an open manifold, this problem has been studied by Lohkamp [13],
who proved that every Riemannian metric on an open manifold is conformal to a
complete metric of negative Ricci curvature. A new proof was given by the
author in [20].

Nevertheless, the problem is still open when $M$ is closed. In this paper, we
answer the problem when the Ricci curvature of $g$ is quasi-negative.

First we summarize some notations and notions. Let $Ric_{g}$ be the Ricci
curvature of Riemannian metric $g$. The $Ric_{g}$ is quasi-negative means that
$Ric_{g}$ is nonpositive everywhere but strictly negative somewhere.

######  Theorem 1.1.

Let $(M,g)$ be a closed connected Riemannian manifold of dimension $n\geqslant
3$ with quasi-negative Ricci curvature. Then there is a unique smooth
Riemannian metric $\tilde{g}\in[g]$ with

$\displaystyle\det(\lambda(-{\tilde{g}^{-1}}Ric_{\tilde{g}}))=1.$

In fact we prove a more general theorem for a modified Schouten tensor

$\displaystyle
A_{{g}}^{\tau,\alpha}=\frac{\alpha}{n-2}\left({Ric}_{g}-\frac{\tau}{2(n-1)}{R}_{g}\cdot{g}\right),\,$
$\displaystyle\alpha=\pm 1,\mbox{ }\tau\in\mathbb{R},$

where ${R}_{g}$ is the scalar curvature of $g$. More precisely, we can
construct a metric $\tilde{g}=e^{2{u}}g$ satisfying
$\lambda(g^{-1}A_{\tilde{g}}^{\tau,\alpha})\in\Gamma$ in $M$, through solving
a fully nonlinear equation

(1.1) $\displaystyle
f(\lambda(\tilde{g}^{-1}A_{\tilde{g}}^{\tau,\alpha}))=\psi,$

where $\lambda(\tilde{g}^{-1}A_{\tilde{g}}^{\tau,\alpha})$ are the eigenvalues
of $A_{\tilde{g}}^{\tau,\alpha}$ with respect to $\tilde{g}$, $0<\psi\in
C^{\infty}(M)$ and

(1.2) $\begin{cases}\tau<1\,&\mbox{ if }\alpha=-1,\\\
\tau>1+(n-2)(1-\kappa_{\Gamma}\vartheta_{\Gamma})\,&\mbox{ if
}\alpha=1.\end{cases}$

Here $\kappa_{\Gamma}$ and $\vartheta_{\Gamma}$ are the constants from Theorem
2.1 below.

As in [3], $f$ is a smooth, symmetric and concave function defined in an open,
symmetric and convex cone $\Gamma\subset\mathbb{R}^{n}$ with vertex at the
origin and boundary $\partial\Gamma\neq\emptyset$, containing the positive
cone $\Gamma_{n}:=\left\\{\lambda\in\mathbb{R}^{n}:\mbox{ each component
}\lambda_{i}>0\right\\}.$ We denote the closure of $\Gamma$ by
$\overline{\Gamma}=\Gamma\cup\partial\Gamma$.

Our main result can be stated as follows.

######  Theorem 1.2.

Let $(\alpha,\tau)$ satisfy (1.2). Let $M$ be a closed connected manifold of
dimension $n\geqslant 3$ and suppose a Riemannian metric $g$ with

(1.3)
$\displaystyle\lambda(g^{-1}A_{g}^{\tau,\alpha})\in\overline{\Gamma}\mbox{ in
}M,$ (1.4) $\displaystyle\lambda(g^{-1}A_{g}^{\tau,\alpha})\in\Gamma\mbox{ at
some }p_{0}\in M.$

Assume in addition that

(1.5) $\displaystyle f(t\lambda)=t^{\mathrm{\varsigma}}f(\lambda),\mbox{
}\forall\lambda\in\Gamma,\mbox{}\forall t>0,\mbox{ for some constant
}0<\mathrm{\varsigma}\leqslant 1,$ (1.6) $\displaystyle f>0\mbox{ in
}\Gamma,\quad f=0\mbox{ on }\partial\Gamma.$

Then there is a unique smooth admissible metric $\tilde{g}\in[g]$ satisfying
(1.1).

######  Remark 1.3.

For the equation (1.1), we call $g$ an admissible metric if
$\lambda(g^{-1}A_{{g}}^{\tau,\alpha})\in\Gamma$ in $M$. Meanwhile, we say
${g}$ is weakly admissible if ${g}\in C^{2}$ and
$\lambda({g}^{-1}A_{{g}}^{\tau,\alpha})\in\overline{\Gamma}\mbox{ in }M$.

The equation (1.1) include many important equations as special cases. When
$f=\sigma_{1}$, $\tau=0$ and $\psi$ is a proper constant, it is closely
related to the well-known Yamabe problem, proved by Schoen [17] with important
contributions from Aubin [1] and Trudinger [18]. For $f=\sigma_{k}^{1/k}$,
$\psi=1$ and $\tau=\alpha=1$, it was proposed by Viaclovsky [19], referred to
$k$-Yamabe problem. The $k$-Yamabe problem has been much studied in recent
years [4, 6, 7, 11, 10, 15].

We shall mention more known work [9, 16] on prescribed $\sigma_{k}$ curvature
equation

(1.7)
$\displaystyle\sigma_{k}^{1/k}(\lambda(\tilde{g}^{-1}A_{\tilde{g}}^{\tau,\alpha}))=\psi$

on a closed manifold, in which

(1.8) $\begin{cases}\tau<1\,&\mbox{ if }\alpha=-1,\\\ \tau>n-1\,&\mbox{ if
}\alpha=1.\end{cases}$

In [9] Gursky-Viaclovsky solved the equation for $\alpha=-1$ and $\tau<1$,
while the case $\tau>n-1$ and $\alpha=1$ was considered by Sheng-Zhang [16]
via a fully nonlinear flow. Notice that their approach relies crucially upon
two assumptions: one is the existence of admissible metric, the other is the
assumption (1.8). This assumption automatically ensures the uniform
ellipticity (parabolicity) of the equation.

As a contrast our result and strategy are different. We want to stress that in
Theorem 1.2 the given metric allows to be weakly admissible. To achieve this,
we construct in Section 3 an admissible metric, based on Morse theory and
differential topology. In addition, the assumption (1.2) is much more broader
than (1.8) and it allows the critical case $\tau=n-1$ (the Einstein tensor
$G_{g}=Ric_{{g}}-\frac{R_{{g}}}{2}\cdot{g}$) when $\Gamma\neq\Gamma_{n}$. To
overcome the difficulty, we use Theorem 2.1 to explore the structure of (1.1).
The critical case is fairly interesting in dimension three, since the Einstein
tensor is closely related to sectional curvature. See a formula in [8, Section
2].

##  2\. Preliminaries and Notations

###  2.1. Some formulas and reduction of equation

By the formula under the conformal change $\tilde{g}=e^{2u}g$ (see e.g. [2]),

$\displaystyle{Ric}_{\tilde{g}}=$ $\displaystyle{Ric}_{g}-\Delta
ug-(n-2)\nabla^{2}u-(n-2)|\nabla u|^{2}g+(n-2)du\otimes du.$

Thus

(2.1) $\displaystyle
A_{\tilde{g}}^{\tau,\alpha}=A_{g}^{\tau,\alpha}+\frac{\alpha(\tau-1)}{n-2}\Delta
ug-\alpha\nabla^{2}u+\frac{\alpha(\tau-2)}{2}|\nabla u|^{2}g+\alpha du\otimes
du.$

We denote

(2.2) $\displaystyle V[u]=\Delta ug-\varrho\nabla^{2}u+\gamma|\nabla
u|^{2}g+\varrho du\otimes du+A,$ (2.3)
$\displaystyle\varrho=\frac{n-2}{\tau-1},\mbox{
}\gamma=\frac{(\tau-2)(n-2)}{2(\tau-1)},\mbox{
}A=\frac{n-2}{\alpha(\tau-1)}A_{g}^{\tau,\alpha}.$

Notice that $V[u]=\frac{n-2}{\alpha(\tau-1)}A^{\tau,\alpha}_{\tilde{g}}$. The
equation (1.1) reads as follows

(2.4) $\displaystyle
f(\lambda(g^{-1}V[u]))=\frac{(n-2)^{\mathrm{\varsigma}}\psi}{\alpha^{\mathrm{\varsigma}}(\tau-1)^{\mathrm{\varsigma}}}e^{2\mathrm{\varsigma}u}.$

###  2.2. Structure of operators

In prequel [20] the author explored the structure of nonlinear operator
subject to

(2.5) $\displaystyle\lim_{t\rightarrow+\infty}f(t\lambda)>f(\mu)\mbox{ for any
}\lambda,\mbox{ }\mu\in\Gamma.$

We denote $f_{i}(\lambda)=\frac{\partial f}{\partial\lambda_{i}}(\lambda).$

######  Theorem 2.1 ([20]).

Suppose $(f,\Gamma)$ satisfies (2.5). Then

$\displaystyle f_{i}(\lambda)\geqslant 0\mbox{ in }\Gamma,\mbox{ }\forall
1\leqslant i\leqslant n,$

and for any $\lambda\in\Gamma$ with
$\lambda_{1}\leqslant\cdots\leqslant\lambda_{n}$,

$\displaystyle
f_{{i}}(\lambda)\geqslant\vartheta_{\Gamma}\sum_{j=1}^{n}f_{j}(\lambda)>0,\mbox{
}\forall 1\leqslant i\leqslant\kappa_{\Gamma}+1,$

where
${\kappa}_{\Gamma}=\max\left\\{k:({\overbrace{0,\cdots,0}^{k}},{\overbrace{1,\cdots,1}^{n-k}})\in\Gamma\right\\}$,
as well as $\vartheta_{\Gamma}=\frac{1}{n}$ for $\Gamma=\Gamma_{n}$, and

$\vartheta_{\Gamma}=\sup_{(-\alpha_{1},\cdots,-\alpha_{\kappa_{\Gamma}},\alpha_{\kappa_{\Gamma}+1},\cdots,\alpha_{n})\in\Gamma;\mbox{
}\alpha_{i}>0}\frac{\alpha_{1}/n}{\sum_{i=\kappa_{\Gamma}+1}^{n}\alpha_{i}-\sum_{i=2}^{\kappa_{\Gamma}}\alpha_{i}}\mbox{
for }\Gamma\neq\Gamma_{n}.$

Based on Theorem 2.1, the author confirmed the uniform ellipticity of (2.4).
Firstly by (1.2),

(2.6)
$\displaystyle\varrho<\frac{1}{1-\kappa_{\Gamma}\vartheta_{\Gamma}}\mbox{ and
}\varrho\neq 0.$

From [20, Proposition 3.2], we know

######  Theorem 2.2 ([20]).

Suppose (1.2), (1.5) and (1.6) hold. Then the equation (2.4) is of uniform
ellipticity at any solution $u$ with $\lambda(g^{-1}V[u])\in\Gamma$.

The following lemma plays a key role in the construction of admissible
metrics.

######  Lemma 2.3 ([20]).

For $\varrho$ satisfying (2.6), $(1,\cdots,1,1-\varrho)\in\Gamma.$

##  3\. Construction of admissible metrics and proof of main results

In this section, we construct admissible metric in $[g]$ under the assumptions
(1.3) and (1.4).

######  Theorem 3.1.

Let $(\alpha,\tau)$ satisfy (1.2). Suppose $M$ is a closed connected manifold
of dimension $n\geqslant 3$ and suppose a Riemannian metric $g$ satisfying
(1.3) and (1.4). Then there exists an admissible metric in $[g]$.

###### Proof.

We use the notation denoted in (2.2) and (2.3). For a $C^{2}$-smooth function
$w$ on $M$, we denote the critical set by

$\mathcal{C}(w)=\left\\{x\in M:dw(x)=0\right\\}.$

By the assumption (1.4) and the openness of $\Gamma$, there is a uniform
positive constant $r_{0}$ such that

(3.1) $\displaystyle\lambda(g^{-1}A)\in\Gamma\mbox{ in
}\overline{B_{r_{0}}(p_{0})}.$

Take a smooth Morse function $w$ with the critical set

$\mathcal{C}(w)=\\{p_{1},\cdots,p_{m},p_{m+1}\cdots p_{m+k}\\}$

among which $p_{1},\cdots,p_{m}$ are all the critical points being in
$M\setminus\overline{B_{r_{0}/2}(p_{0})}$. Pick
$q_{1},\cdots,q_{m}\in{B_{r_{0}/2}(p_{0})}$ but not the critical point of $w$.
By the homogeneity lemma (see e.g. [14]), one can find a diffeomorphism
$h:M\to M$, which is smoothly isotopic to the identity, such that

  * •

$h(p_{i})=q_{i}$, $1\leqslant i\leqslant m$.

  * •

$h(p_{i})=p_{i}$, $m+1\leqslant i\leqslant m+k$.

Then we obtain a Morse function

(3.2) $\displaystyle v=w\circ h^{-1}.$

One can check that

(3.3) $\displaystyle\mathcal{C}(v)=\\{q_{1},\cdots,q_{m},p_{m+1}\cdots
p_{m+k}\\}\subset\overline{B_{r_{0}/2}(p_{0})}.$

Next we complete the proof. Assume $v\leqslant-1$. Take
$\underline{u}=e^{Nv},$ $\underline{g}=e^{2\underline{u}}g,$ then

$\displaystyle V[\underline{u}]=A+N^{2}e^{Nv}\left((\Delta
vg-\varrho\nabla^{2}v)/N+(1+\gamma e^{Nv})|\nabla
v|^{2}g+\varrho(e^{Nv}-1)dv\otimes dv\right).$

Notice that

(3.4) $\displaystyle\lambda(g^{-1}((1+\gamma e^{Nv})|\nabla
v|^{2}g+\varrho(e^{Nv}-1)dv\otimes dv))$ $\displaystyle=$
$\displaystyle|\nabla v|^{2}(1,\cdots,1,1-\varrho)+e^{Nv}|\nabla
v|^{2}(\gamma,\cdots,\gamma,\gamma+\varrho).$

By Lemma 2.3 and the openness of $\Gamma$,

(3.5)
$\displaystyle(1,\cdots,1,1-\varrho)+e^{Nv}(\gamma,\cdots,\gamma,\gamma+\varrho)\in\Gamma\mbox{
for }N\gg 1.$

Case 1: $x\in\overline{B_{r_{0}}(p_{0})}$. By (3.1) and the openness of
$\Gamma$,

(3.6) $\displaystyle\lambda(g^{-1}(A+Ne^{Nv}(\Delta
vg-\varrho\nabla^{2}v)))\in\Gamma.$

Combining (3.4) and (3.5),

$\displaystyle\lambda(g^{-1}V[\underline{u}])\in\Gamma\mbox{ in
}\overline{B_{r_{0}}(p_{0})}.$

Case 2: $x\notin\overline{B_{r_{0}}(p_{0})}$. By (3.3) there is a uniform
positive constant $m_{0}$ such that $|\nabla v|^{2}\geqslant m_{0}$ in
$M\setminus\overline{B_{r_{0}}(p_{0})}$. By (3.4), (3.5), (1.3), and the
openness of $\Gamma$,

$\displaystyle\lambda(g^{-1}V[\underline{u}])\in\Gamma\mbox{ in
}M\setminus\overline{B_{r_{0}}(p_{0})}.$

This completes the proof. ∎

Using the admissible metric constructed above, together with Theorem 2.2, we
immediately derive the $C^{0}$-estimate using maximum principle.

Building on Theorem 2.2, the author derived interior estimates for (2.4).

######  Theorem 3.2 ([20]).

Let $B_{r}\subset M$ be a geodesic ball of radius $r$. Let $u\in C^{4}(B_{r})$
be a solution with $\lambda(g^{-1}V[u])\in\Gamma$ to the equation (2.4) in
$B_{r}$. Assume (1.2), (1.5) and (1.6) hold. Then

$\displaystyle\sup_{B_{{r}/{2}}}\,(|\nabla^{2}u|+|\nabla u|^{2})\leqslant C,$

where $C$ depends on $|u|_{C^{0}(B_{r})}$, $r^{-1}$, and other known data.

In conclusion, we obtain

$\displaystyle|\nabla^{2}u|\leqslant C.$

Then we can prove Theorem 1.2 via a standard continuity method.

#### Acknowledgements

The author would like to thank Professor Yi Liu for helpful discussions on the
Morse theory. The author is supported by the National Natural Science
Foundation of China grant 11801587.

## References

  * [1] T. Aubin, Équations différentielles non linéaires et problème de Yamabe concernant la courbure scalaire, J. Math. Pures Appl. 55 (1976), 269–296.
  * [2] A. Besse, Einstein manifolds. Classics in Mathematics. Springer-Verlag, Berlin, 2008.
  * [3] L. Caffarelli, L. Nirenberg, and J. Spruck, The Dirichlet problem for nonlinear second-order elliptic equations III: Functions of eigenvalues of the Hessians, Acta Math. 155 (1985), 261–301.
  * [4] S.-Y. A. Chang, M. Gursky, and P. Yang, An equation of Monge-Ampère type in conformal geometry, and four-manifolds of positive Ricci curvature, Ann. Math. 155 (2002), 709–787.
  * [5] L. Z. Gao, and S.-T. Yau, The existence of negatively Ricci curved metrics on three manifolds, Invent. Math. 85(1986), 637–652.
  * [6] Y.-X. Ge, and G.-F. Wang, On a fully nonlinear Yamabe problem, Ann. Sci. Éole Norm. Sup. 39 (2006), 569–598.
  * [7] P.-F. Guan, and G.-F. Wang, A fully nonlinear conformal flow on locally conformally flat manifolds, J. Reine Angew. Math. 557 (2003), 219–238.
  * [8] M. Gursky, J. Streets, and M. Warren, Conformally bending three-manifolds with boundary, Ann. Inst. Fourier (Grenoble) 60 (2010), 2421–2447.
  * [9] M. Gursky, and J. Viaclovsky, Fully nonlinear equations on Riemannian manifolds with negative curvature, Indiana Univ. Math. J. 52 (2003), 399–419.
  * [10] M. Gursky, and J. Viaclovsky, Prescribing symmetric functions of the eigenvalues of the Ricci tensor, Ann. Math. 166 (2007), 475–531.
  * [11] A.-B. Li, and Y.-Y. Li, On some conformally invariant fully nonlinear equations, Comm. Pure Appl. Math. 56 (2003), 1416–1464.
  * [12] J. Lohkamp, Metrics of negative Ricci curvature, Ann. Math. 140 (1994), 655–683.
  * [13] J. Lohkamp, Negative bending of open manifolds, J. Differential Geom. 40 (1994), 461–474.
  * [14] J. W. Milnor, Topology from the differentiable viewpoint. Princeton University Press, Princeton, NJ, 1997.
  * [15] W.-M. Sheng, N. Trudinger, and X.-J. Wang, The Yamabe problem for higher order curvatures, J. Differential Geom. 77 (2007), 515–553.
  * [16] W.-M. Sheng, and Y. Zhang, A class of fully nonlinear equations arising from conformal geometry, Math. Z. 255 (2007), 17–34.
  * [17] R. Schoen, Conformal deformation of a Riemannian metric to constant scalar curvature, J. Differential Geom. 20 (1984), 479–495.
  * [18] N. Trudinger, Remarks concerning the conformal deformation of Riemannian structures on compact manifolds, Ann. Scuola Norm. Sup. Pisa Cl. Sci. (3) 22 (1968), 265–274.
  * [19] J. Viaclovsky, Conformal geometry, contact geometry, and the calculus of variations, Duke Math. J. 101 (2000), 283–316.
  * [20] R.-R. Yuan, The partial uniform ellipticity and prescribed problems on the conformal classes of complete metrics, arXiv:2203.13212.