text:
# Explicit Solution of the Time Evolution of the Wigner Function†

## 1 Introduction

It is a great pleasure for me to participate in the Wigner Centennial Conference at Pecs, Hungary in honor of the Centennial of Professor Eugene Wigner’s birthday. I first met Professor Wigner in 1959 when I was an undergraduate student at Princeton. Professor Wigner taught us and our fellow graduate school classmates Curtis Callen, Stephen Adler, and Alfred Goldhaber a course in Advanced Quantum Mechanics in 1961. We were at the celebration party at the Graduate College when Professor Wigner was awarded the Nobel Prize in Physics in 1963. After I obtained my Ph. D. degree at Princeton, I came to work at Oak Ridge National Laboratory, for which Professor Wigner was the founding Scientific Director. I saw Professor Wigner from time to time at Oak Ridge when he came to work on his civil defense project. It is therefore particularly meaningful to me to come and celebrate his centennial in his native land to commemorate his many important contributions.

As a part of the “Junior Paper” research project at Princeton University, I went to see Professor Wigner in his office in Fine Hall in 1959 and inquired about the early history of Quantum Mechanics. He told me that the great thing about Schrödinger was that his wave equation was formulated in configuration space. However, to Professor Wigner, who was trained as a chemical engineer, dynamics could also be described in phase space. His formulation of quantum mechanics in phase space in 1932 led to the well-known Wigner description of quantum systems . The joint function of coordinate and momentum $`f(𝒓𝒑)`$ introduced in 1932, now known as the Wigner function, is analogous with the classical distribution function. This analogy has provided new insights and useful applications to many quantum systems. It is deservedly a subject of intense interest in this Wigner Centennial Conference .

The Wigner function is, however, not identical to the classical distribution function. The classical distribution function is always non-negative and can be described in terms of a collection of cell points with positive weights in phase space. The evolution of the classical distribution function can be followed by tracking these cell points using classical equations of motion .

The Wigner function can assume negative as well as positive values in some regions of phase space. How does a Wigner function with regions of negative values evolve as a function of time? The concept of a probability distribution function with positive weights is clearly not applicable here. The difficulty of propagating the Wigner function with negative values has been a barrier to the study of the dynamics of the Wigner function using the equation of motion of the Wigner function directly.

Previously, I formulated a simple method to propagate the Wigner function in time . The ability to propagate the Wigner function with negative values arises from the fact that one deals with amplitudes in this method, and one does not need to use the concept of probabilities. The method contains three important components. First, one employs an auxiliary variable $`𝒔`$, which is allowed to span the whole configuration space. Second, using this auxiliary variable $`𝒔`$, the Wigner function can be represented in terms of auxiliary phase space coordinates $`𝑹`$ and $`𝑷`$. The equations of motion for these auxiliary coordinates $`𝑹`$ and $`𝑷`$ are quite simple. They are analogous with, but not identical to, the classical equations of motion, as $`𝑷/t`$ depends on the auxiliary coordinate $`𝒔`$. They can be solved easily and their solutions can be utilized to construct the Wigner function at the next time step. The third component consists of providing the correct amplitude function for the evolution. For each value of $`𝒔`$ and the evolution of phase space coordinates, one associates an amplitude factor $`\mathrm{exp}\{i𝒔(𝒑𝑷)/\mathrm{}\}`$. After the amplitudes for all possible values of $`𝒔`$ have been obtained at the end of one time step, one adds all these amplitudes together coherently (Huygen Principle) to give the Wigner function $`f(𝒓𝒑)`$ at the next time step. This explicit solution overcomes the difficulty of propagating a Wigner function with negative values.

Recently, with the rapid advances in quantum information technology and the reduction in the size of micro-electronic devices, there has been renewed interest in experimental and theoretical studies of the Wigner function -. Experimental measurements of the Wigner function have been carried out using many different techniques -. Regions of negative Wigner function were observed in many experiments . The time evolution of the Wigner function has been studied by many authors $``$. It is instructive to review the explicit solution for the time evolution of the Wigner function obtained previously and to demonstrate its usefulness by a numerical example. We choose to examine an example in which the time evolution of the Wigner function can be ready evaluated by using wave functions and eigenvalues. The Wigner function in the example should have significant spatial and temporal variations as well as regions of negative values to test whether the explicit solution obtained previously is capable of treating these non-classical features. The success in providing a correct time evolution of the Wigner function using this explicit solution will pave the way for its applications in the future.

As an approximation of the explicit solution, a pseudoparticle method was developed previously  to obtain the time evolution of the Wigner function by following the trajectories of the phase space coordinates, using classical equations of motion . It is instructive to review this pseudoparticle method and assess its accuracy by comparing with the correct results. Furthermore, it is useful to develop systematic ways to improve the accuracy of the pseudoparticle method to assist its future applications.

## 2 Explicit Solution of the Time Evolution of the Wigner Function

We shall first review the explicit solution obtained in 1982 . We consider a particle in the potential $`V`$

$`i\mathrm{}{\displaystyle \frac{}{t}}\psi (𝒓,t)=\left\{{\displaystyle \frac{\mathrm{}^2}{2m}}^2+V(𝒓,t)\right\}\psi (𝒓,t).`$ (1)
The Wigner function is

$`f(𝒓𝒑,t)={\displaystyle 𝑑𝒔e^{i𝒑𝒔/\mathrm{}}\psi (𝒓\frac{𝒔}{2},t)\psi ^{}(𝒓+\frac{𝒔}{2},t)}.`$ (2)
From the Schrödinger equation, we obtain the equation of motion for the Wigner function

$`{\displaystyle \frac{f(𝒓𝒑,t)}{dt}}+{\displaystyle \frac{𝒑}{m}}_rf(𝒓𝒑,t){\displaystyle \frac{2}{\mathrm{}}}\mathrm{sin}\left\{{\displaystyle \frac{\mathrm{}}{2}}_r^V_p^f\right\}V(𝒓,t)f(𝒓𝒑,t)=0,`$ (3)
where $`_r^V`$ acts on the potential $`V`$ and $`_p^f`$ acts on the Wigner function $`f`$.

Given the Wigner function $`f(𝒓_0𝒑_0,t_0)`$ at time $`t_0`$, we wish to obtain the Wigner function at the next time step at $`t=t_0+\delta t`$ with a small $`\delta t`$. To solve for the dynamics, we divide the phase space into cells (pseudoparticles). Consider one such cell centered at $`\{𝒓_0`$ $`𝒑_0\}`$ at time $`t_0`$ with volume element $`d𝒓_0d𝒑_0`$ and amplitude $`f(𝒓_0𝒑_0,t_0)`$. We retain the auxiliary coordinate $`𝒔`$ and follow the time dependence of each cell in the Lagrangian sense. For the phase space coordinates $`\{𝒓_0𝒑_0\}`$ initially at time $`t_0`$, we label their phase space coordinates at subsequent time $`t`$ by $`\{𝑹(𝒓_0𝒑_0𝒔,t)𝑷(𝒓_0𝒑_0𝒔,t)\}`$. In classical dynamics, the evolution of the phase space coordinates will not depend on $`𝒔`$. In quantum dynamics, they will depend on $`𝒔`$. The momentum coordinate $`𝑷`$ can jump to the momentum coordinate $`𝒑`$ at time $`t`$. We associate an amplitude of $`\mathrm{exp}\{i𝒔[𝒑𝑷(𝒓_0𝒑_0𝒔,t)]/\mathrm{}\}`$ for this momentum jump. This amplitude factor is chosen because for the classical case where $`𝑷`$ is independent of $`𝒔`$ this amplitude leads to the correct delta function propagator $`\delta (𝒑𝑷\mathbf{(}𝒓_\mathrm{𝟎}𝒑_\mathrm{𝟎}\mathbf{,}𝒕))`$ after we integrate over $`𝒔`$ \[see Eq. (14)\]. We therefore express the Wigner function $`f(𝒓𝒑,t)`$ at the next time step as

$`f(𝒓𝒑,t)={\displaystyle \frac{d𝒓_0d𝒑_0d𝒔}{(2\pi \mathrm{})^3}\mathrm{exp}\{i𝒔[𝒑𝑷(𝒓_0𝒑_0𝒔,t)]/\mathrm{}\}\delta [𝒓𝑹(𝒓_0𝒑_0𝒔,t)]f(𝒓_0𝒑_0,t_0)}.`$ (4)
Our task is to find solutions for the phase space coordinates $`𝑹(𝒓_0𝒑_0𝒔,t)`$ and $`𝑷(𝒓_0𝒑_0𝒔,t)`$ with initial conditions $`𝑹(𝒓_0𝒑_0𝒔,t_0)=𝒓_0`$ and $`𝑷(𝒓_0𝒑_0𝒔,t_0)=𝒑_0`$. If we can find these coordinates at the next time step, the above integral can then be carried out to give the Wigner function at the new time $`t`$.

To obtain the equations of motion for $`𝑹(𝒓_0𝒑_0𝒔,t)`$ and $`𝑷(𝒓_0𝒑_0𝒔,t)`$, we substitute Eq. (4) into Eq. (3). For the first term in Eq. (3), we get

$`{\displaystyle \frac{f(𝒓𝒑,t)}{t}}={\displaystyle \frac{d𝒓_0d𝒑_0d𝒔}{(2\pi \mathrm{})^3}f(𝒓_0𝒑_0,t_0)}`$
$`\times [{\displaystyle \frac{(i𝒔)}{\mathrm{}}}{\displaystyle \frac{𝑷}{t}}\mathrm{exp}\{i𝒔[𝒑𝑷(𝒓_0𝒑_0𝒔,t)]/\mathrm{}\}\delta [𝒓𝑹(𝒓_0𝒑_0𝒔,t)]`$
$`+\mathrm{exp}\{i𝒔[𝒑𝑷(𝒓_0𝒑_0𝒔,t)]/\mathrm{}\}(_𝑹\delta [𝒓𝑹(𝒓_0𝒑_0𝒔,t)])𝑹(𝒓_0𝒑_0𝒔,t)/t].`$ (5)
Noting that

$`_𝑹\delta [𝒓𝑹(𝒓_0𝒑_0𝒔,t)]=_𝒓\delta [𝒓𝑹(𝒓_0𝒑_0𝒔,t)],`$ (6)
we can rewrite the second term inside the square bracket as

$`{\displaystyle \frac{d𝒓_0d𝒑_0d𝒔}{(2\pi \mathrm{})^3}f(𝒓_0𝒑_0,t_0)}`$
$`\times \mathrm{exp}\{i𝒔[𝒑𝑷(𝒓_0𝒑_0𝒔,t)]/\mathrm{}\}(_𝒓\delta [𝒓𝑹(𝒓_0𝒑_0𝒔,t)]𝑹(𝒓_0𝒑_0𝒔,t)/t`$
$`={\displaystyle \frac{𝑹(𝒓_0𝒑_0𝒔,t)}{t}}_𝒓f(𝒓𝒑,t),`$ (7)
where we have used Eq. (4) to obtain the right-hand side. For the last term in Eq. (3), we substitute (4) into this term and find

$`{\displaystyle \frac{2}{\mathrm{}}}\mathrm{sin}\left\{{\displaystyle \frac{\mathrm{}}{2}}_r^V_p^f\right\}V(𝒓,t)f(𝒓𝒑,t)={\displaystyle \frac{1}{\mathrm{}}}{\displaystyle \frac{d𝒓_0d𝒑_0d𝒔}{(2\pi \mathrm{})^3}f(𝒓_0𝒑_0,t_0)}`$
$`\times \mathrm{exp}\{i𝒔[𝒑𝑷(𝒓_0𝒑_0𝒔,t)]/\mathrm{}\}\delta [𝒓𝑹(𝒓_0𝒑_0𝒔,t)]){\displaystyle \frac{[V(𝒓\frac{𝒔}{2},t)V(𝒓+\frac{𝒔}{2},t)]}{i}}.`$ (8)
Putting Eqs. (2)-(2) into Eq. (3), we obtain

$`\left[{\displaystyle \frac{𝑹(𝒓_0𝒑_0𝒔,t)}{t}}+{\displaystyle \frac{𝒑}{m}}\right]_rf(𝒓𝒑,t)`$
$`+{\displaystyle \frac{d𝒓_0d𝒑_0d𝒔}{(2\pi \mathrm{})^3}f(𝒓_0𝒑_0,t_0)\left[\frac{(i𝒔)}{\mathrm{}}\frac{𝑷}{t}\frac{[V(𝒓\frac{𝒔}{2},t)V(𝒓+\frac{𝒔}{2},t)]}{i\mathrm{}}\right]}`$
$`\times \mathrm{exp}\{i𝒔[𝒑𝑷(𝒓_0𝒑_0𝒔,t)]/\mathrm{}\}\delta [𝒓𝑹(𝒓_0𝒑_0𝒔,t)]=0.`$ (9)
By comparing similar terms, the above equation leads to the equations of motion for $`𝑹`$ and $`𝑷`$ ,

$`{\displaystyle \frac{𝑹}{t}}={\displaystyle \frac{𝒑}{m}},`$ (10)
$`𝒔{\displaystyle \frac{𝑷}{t}}=V(𝑹{\displaystyle \frac{𝒔}{2}},t)V(𝑹+{\displaystyle \frac{𝒔}{2}},t).`$ (11)
In the above equations, $`𝒓`$ and $`𝑹`$ are interchangeable, because of the $`\delta `$-function $`\delta (𝒓𝑹)`$ in Eq. (4). It is interesting to note that these two equations were used recently by Morawetz to study the quantum response of a finite fermion system .

Equation (4) combined with the equations of motion (10) and (11) gives an explicit and exact solution of the time evolution of the Wigner function . The equation of motion for $`𝑹`$ is the same as the classical equation of motion. The equation of motion for $`𝑷`$ coincides with the classical equation of motion for small $`𝒔`$ but differs from the classical equation when $`𝒔`$ is large. The latter difference distinguishes a quantum system from a classical system.

We note that if (1) we expand Eq. (11) in $`𝒔`$ and we keep only the lowest order term, or if (2) we take the limit $`\mathrm{}0`$ so that the dominant contributions in Eq. (4) come from regions of small $`𝒔`$, then Eqs. (10) and (11) becomes the classical equations of motion

$`{\displaystyle \frac{𝑹}{t}}={\displaystyle \frac{𝒑}{m}}`$ (12)
and

$`{\displaystyle \frac{𝑷}{t}}=_RV(R,t).`$ (13)
The function $`𝑷(𝒓_0𝒑_0𝒔,t)`$ is then independent of $`𝒔`$, and Eq. (4) gives

$`f(𝒓𝒑,t)={\displaystyle 𝑑𝒓_0𝑑𝒑_0\delta [𝒓𝑹(𝒓_0𝒑_0,t)]\delta [𝒑𝑷(𝒓_0𝒑_0,t)]f(𝒓_0𝒑_0,t_0)},`$ (14)
which is the same as solution of the evolution of the classical distribution function.

## 3 Implementation of the Explicit Solution

The explicit solution of Eqs. (4), (10) and (11) given in the previous section allows one to propagate the Wigner function from one time to another. One considers a small time increment $`\delta t=tt_0`$, and solves Eqs. (10) and (11). One obtains

$`𝒓=𝑹(𝒓_0𝒑_0𝒔,t)=𝒓_0+{\displaystyle \frac{𝒑}{m}}\delta t.`$ (15)
and

$`𝑷=𝒑_0+𝒆_s{\displaystyle \frac{V(𝒓\frac{𝒔}{2},t)V(𝒓+\frac{𝒔}{2},t)}{s}}\delta t,`$ (16)
where $`𝒆_s`$ is the unit vector in the $`𝒔`$ direction. After $`𝒓(𝑹)`$ and $`𝑷`$ for different $`𝒔`$ have been obtained, we can substitute them in Eq. (4) and carry out the integration to give the new Wigner function at the next time step. Eqs. (15) and (16) lead to

$`f(𝒓𝒑,t)={\displaystyle 𝑑𝒓_0𝑑𝒑_0\frac{d𝒔}{(2\pi \mathrm{})^3}\mathrm{exp}\left[i\left\{\frac{𝒔(𝒑𝒑_0)}{\mathrm{}}\left(V(𝒓\frac{𝒔}{2},t)V(𝒓+\frac{𝒔}{2},t)\right)\frac{\delta t}{\mathrm{}}\right\}\right]}`$
$`\times \delta (𝒓𝒓_0{\displaystyle \frac{𝒑}{m}}\delta t)f(𝒓_0,𝒑_0,t_0).`$ (17)
We shall first consider the one-dimensional case for which the factor $`(2\pi \mathrm{})^3`$ becomes $`2\pi \mathrm{}`$. The integration over $`x_0(𝒓_0)`$ can be easily carried out. the above equation for the one-dimensional case becomes

$`f(xp,t)={\displaystyle 𝑑p_02_0^{\mathrm{}}\frac{ds}{2\pi \mathrm{}}\mathrm{cos}\left[\frac{s(pp_0)}{\mathrm{}}\left(V(x\frac{s}{2},t)V(x+\frac{s}{2},t)\right)\frac{\delta t}{\mathrm{}}\right]}`$
$`\times f(x{\displaystyle \frac{p}{m}}\delta t,p_0,t_0).`$ (18)
This explicit solution of the time evolution of the Wigner function can be written as

$`f(xp,t)={\displaystyle 𝑑p_0\left\{F_c(x,pp_0)+F_s(x,pp_0)\right\}f(x\frac{p}{m}\delta t,p_0,t_0)},`$ (19)
where $`F_c(x,pp_0)`$ and $`F_s(x,pp_0)`$ are cosine and sine transforms given by

$`F_c(x,pp_0)=2{\displaystyle _0^{\mathrm{}}}{\displaystyle \frac{ds}{2\pi \mathrm{}}}\mathrm{cos}\left[{\displaystyle \frac{s(pp_0)}{\mathrm{}}}\right]\mathrm{cos}\left[\left(V(x{\displaystyle \frac{s}{2}},t)V(x+{\displaystyle \frac{s}{2}},t)\right){\displaystyle \frac{\delta t}{\mathrm{}}}\right]`$ (20)
and

$`F_s(x,pp_0)=2{\displaystyle _0^{\mathrm{}}}{\displaystyle \frac{ds}{2\pi \mathrm{}}}\mathrm{sin}\left[{\displaystyle \frac{s(pp_0)}{\mathrm{}}}\right]\mathrm{sin}\left[\left(V(x{\displaystyle \frac{s}{2}},t)V(x+{\displaystyle \frac{s}{2}},t)\right){\displaystyle \frac{\delta t}{\mathrm{}}}\right].`$ (21)
The above set of equations (19)-(21) provide a simple implementation of the explicit solution (4), (11), and (10) of the time evolution of a one-dimensional Wigner function.

If one keeps only terms up to first order in $`\delta t`$ for small values of $`\delta t`$, the Wigner function evolution equation becomes

$`f(xp,t)=f(x{\displaystyle \frac{p}{m}}\delta t,p,t_0)+{\displaystyle \frac{\delta t}{\mathrm{}}}{\displaystyle 𝑑p_0V_s(x,pp_0)f(x\frac{p}{m}\delta t,p_0,t_0)},`$ (22)
where

$`V_s(x,pp_0)=2{\displaystyle _0^{\mathrm{}}}{\displaystyle \frac{ds}{(2\pi \mathrm{})^3}}\mathrm{sin}\left[{\displaystyle \frac{s(pp_0)}{\mathrm{}}}\right]\left\{V(x{\displaystyle \frac{s}{2}},t)V(x+{\displaystyle \frac{s}{2}},t)\right\}.`$ (23)
We shall now discuss the three-dimensional case for which the integration over $`𝒔`$ in Eq. (3) is rather complicated. It can be simplified if one makes the following approximation

$`V(𝒓{\displaystyle \frac{𝒔}{2}},t)V(𝒓+{\displaystyle \frac{𝒔}{2}},t){\displaystyle \underset{j=1}{\overset{3}{}}}\left(V(𝒓{\displaystyle \frac{s_j𝒆_j}{2}},t)V(𝒓+{\displaystyle \frac{s_j𝒆_j}{2}},t)\right),`$ (24)
where the righthand side contains all terms of the lefthand side except the cross terms involving products of different $`s_j`$ and $`s_j^{}`$$`(j^{}j)`$ with high-order derivatives of $`V(𝒓)`$, when one expand the above functions in powers of $`s_j`$. If one uses this approximation by neglecting these cross terms, Eq. (3) for the three-dimensional case becomes

$`f(𝒓𝒑,t)={\displaystyle 𝑑𝒑_0\underset{j=1}{\overset{3}{}}2_0^{\mathrm{}}\frac{ds_j}{2\pi \mathrm{}}\mathrm{cos}\left[\frac{s_j(p_jp_{0j})}{\mathrm{}}\left(V(𝒓\frac{s_j𝒆_j}{2},t)V(𝒓+\frac{s_j𝒆_j}{2},t)\right)\frac{\delta t}{\mathrm{}}\right]}`$
$`\times f(𝒓{\displaystyle \frac{𝒑}{m}}\delta t,𝒑_0,t_0).`$ (25)
The explicit solution of the time evolution of the Wigner function can be written as

$`f(𝒓𝒑,t)={\displaystyle 𝑑𝒑_0\underset{j=1}{\overset{3}{}}\left\{F_{cj}(𝒓,p_jp_{0j})+F_{sj}(𝒓,p_jp_{0j})\right\}f(𝒓\frac{𝒑}{m}\delta t,𝒑_0,t_0)},`$ (26)
where $`F_{cj}(𝒓,p_jp_{0j})`$ and $`F_{sj}(𝒓,p_jp_{0j})`$ are cosine and sine transforms given by

$`F_{cj}(𝒓,p_jp_{0j})=2{\displaystyle _0^{\mathrm{}}}{\displaystyle \frac{ds_j}{2\pi \mathrm{}}}\mathrm{cos}\left[{\displaystyle \frac{s_j(p_jp_{0j})}{\mathrm{}}}\right]\mathrm{cos}\left[\left(V(𝒓{\displaystyle \frac{s_j𝒆_j}{2}},t)V(𝒓+{\displaystyle \frac{s_j𝒆_j}{2}},t)\right){\displaystyle \frac{\delta t}{\mathrm{}}}\right]`$
and

$`F_{sj}(𝒓,p_jp_{0j})=2{\displaystyle _0^{\mathrm{}}}{\displaystyle \frac{ds_j}{2\pi \mathrm{}}}\mathrm{sin}\left[{\displaystyle \frac{s_j(p_jp_{0j})}{\mathrm{}}}\right]\mathrm{sin}\left[\left(V(𝒓{\displaystyle \frac{s_j𝒆_j}{2}},t)V(𝒓+{\displaystyle \frac{s_j𝒆_j}{2}},t)\right){\displaystyle \frac{\delta t}{\mathrm{}}}\right].`$
The above set of equations (26)-(3) provide a simple and approximate implementation of the explicit solution (4), (11), and (10) of the time evolution of a three-dimensional Wigner function.

## 4 An Example of the Evolution of the Wigner Function

It is of interest to consider an explicit example to test whether the solutions in Eqs. (19)-(21) or (22)-(23) leads to the correct results. For this purpose we study the dynamics of the Wigner function for a case that can be easily evaluated and compared with the Wigner function obtained by using the explicit solution.

We examine a particle in a one-dimensional attractive Gaussian potential well. We express physical quantities in dimensionless units, with a Schrödinger equation given by

$`H\mathrm{\Psi }(x)=\left\{{\displaystyle \frac{1}{2}}{\displaystyle \frac{d^2}{dx^2}}e^{x^2/2\sigma ^2}\right\}\mathrm{\Psi }(x).`$ (29)
The wave function $`\mathrm{\Psi }(x)`$ can be expanded in terms of a set of non-orthogonal Gaussian wave functions with different widths,

$`\mathrm{\Psi }(x)={\displaystyle \underset{n=1}{\overset{n_{\mathrm{max}}}{}}}a_n\psi _n(x),`$ (30)
where the normalized basis function $`x|n=\psi _n(x)`$ is taken to be

$`\psi _n(x)={\displaystyle \frac{e^{x^2/2\beta _n^2}}{(\sqrt{\pi }\beta _n)^{1/2}}},`$ (31)
and $`\beta _n^2=n\beta _0^2`$. The Hamiltonian matrix in this basis set can be easily constructed. Specifically, one calculates the matrix element of the overlap matrix $`B`$ for this set of basis states

$`B_{nm}=n|m=\sqrt{{\displaystyle \frac{2\beta _n\beta _m}{\beta _n^2+\beta _m^2}}},`$ (32)
the matrix element of the kinetic energy matrix $`T`$

$`T_{nm}=n|\left\{{\displaystyle \frac{1}{2}}{\displaystyle \frac{d^2}{dx^2}}\right\}|m={\displaystyle \frac{1}{2}}\sqrt{{\displaystyle \frac{2\beta _n\beta _m}{\beta _n^2+\beta _m^2}}}{\displaystyle \frac{1}{\beta _n^2+\beta _m^2}},`$ (33)
and the matrix element for potential energy matrix $`V`$

$`V_{nm}=n|(e^{x^2/2\sigma ^2})|m=\sqrt{{\displaystyle \frac{2\beta _n\beta _m}{\beta _n^2+\beta _m^2}}{\displaystyle \frac{\sigma ^2}{\beta _{nm}^2+\sigma ^2}}},`$ (34)
where

$`\beta _{nm}^2={\displaystyle \frac{\beta _n^2\beta _m^2}{\beta _n^2+\beta _m^2}}.`$ (35)
The eigenvalue equation becomes

$`(T+V)a=EBa,`$ (36)
where $`a`$ is the column matrix of the coefficients $`\{a_n\}`$ of Eq. (30). This eigenvalue equation can be diagonalized to yield the eigenenergies $`E_\lambda `$ and eigenfunctions $`\mathrm{\Psi }_\lambda (x)`$ represented by the set of coefficients $`\{a_{\lambda n}\}`$. We normalize $`\mathrm{\Psi }_\lambda (x)`$ by $`𝑑x|\mathrm{\Psi }_\lambda (x)|^2=1`$.

A simple non-stationary state $`\mathrm{\Phi }(x)`$ of the system can be constructed as a linear combination of the eigenstates $`\mathrm{\Psi }_\lambda (x)`$ with amplitudes $`b_\lambda `$,

$`\mathrm{\Phi }(x,t=0)={\displaystyle \underset{\lambda }{}}b_\lambda \mathrm{\Psi }_\lambda (x).`$ (37)
The time dependence of this non-stationary system is

$`\mathrm{\Phi }(x,t)={\displaystyle \underset{\lambda }{}}b_\lambda e^{iE_\lambda t}\mathrm{\Psi }_\lambda (x).`$ (38)
The Wigner function of the system is then given by

$`f(xp,t)={\displaystyle \underset{nm}{}}c_n(t)c_m^{}(t)f_{nm}(xp),`$ (39)
where

$`c_n(t)={\displaystyle \underset{\lambda }{}}b_\lambda e^{iE_\lambda t}a_{\lambda n},`$ (40)
$`f_{nm}(xp)=2\sqrt{{\displaystyle \frac{2\beta _n\beta _m}{\beta _n^2+\beta _m^2}}}e^{\nu _{nm}},`$ (41)
$`\nu _{nm}={\displaystyle \frac{(\beta _n^2+\beta _m^2)(x^2\mu _{nm}^2/4)}{2\beta _n^2\beta _m^2}},`$ (42)
and

$`\mu _{nm}=4{\displaystyle \frac{\beta _n^2\beta _m^2}{\beta _n^2+\beta _m^2}}\left[x\left({\displaystyle \frac{1}{2\beta _n^2}}{\displaystyle \frac{1}{2\beta _m^2}}\right)+ip\right].`$ (43)
In our numerical example, we study the dynamics of a system in a potential with a width parameter $`\sigma =3`$. The two lowest energy even-parity eigenstates $`\mathrm{\Psi }_0(x)`$ and $`\mathrm{\Psi }_1(x)`$ have eigenvalues $`E_0=0.844`$ and $`E_1=0.312`$ respectively. As a test, we construct a non-stationary wave function with equal amplitudes in these two eigenstates at $`t=0`$,

$`\mathrm{\Phi }(x,t=0)={\displaystyle \frac{1}{\sqrt{2}}}\{\mathrm{\Psi }_0(x)+\mathrm{\Psi }_1(x)\}.`$ (44)
The time dependence of the wave function is then

$`\mathrm{\Phi }(x,t)={\displaystyle \frac{1}{\sqrt{2}}}\{e^{iE_0t}\mathrm{\Psi }_0(x)+e^{iE_1t}\mathrm{\Psi }_1(x)\}.`$ (45)
The time dependence of the Wigner function can be evaluated using Eq. (39). The Wigner functions for different values of $`p`$ and $`t`$ are shown in Figs. (1a), (1b), and (1c) on the left panel of Fig. 1. The Wigner function has both positive and negative values in different regions of phase space. The eigenfunctions and eigenvalues give a correct representation of the Wigner function as it depends only on the accuracy of the eigenvalues and eigenfunctions, and not on the accuracy of the method of propagating forward in time.

The non-stationary state we have used leads to an initial Wigner function with significant spatial and temporal variations as well as regions of negative values. These properties provide a stringent test of the methods of using Eqs. (19)-(21) or Eqs. (22)-(23) to propagate the Wigner function.

For our tests we take the initial Wigner function for our non-stationary state Eq. (44) at time $`t=0`$, and evolve the Wigner function using the explicit solution. We carry out the time evolution using small time increments. We can choose either Eqs. (19)-(21) or Eqs. (22)-(23) to evolve the Wigner function. The former includes higher order effects in $`\delta t`$, and can be used with a larger time increment than the second approach. We choose to use Eqs. (19)-(21), and the results for the time evolution from $`t=0`$ to $`t=3`$ in Figs. (1a’), (1b’), and (1c’) were calculated using 30 time steps. The cosine and sine transforms can be calculated using the method of fast Fourier transforms. The numerical integration over $`p_0`$ in Eq. (19) can then be carried out to yield the Wigner function at the next time step. This process is repeated in a stepwise manner to propagate forward in time. The resulting time evolution of the Wigner function is shown in Figs. (1a’), (1b’), and (1c’) on the right panel of Fig. 1.

A comparison of the left and the right panels indicates that the explicit solution of Eqs. (19)-(21) gives an excellent reproduction of the time evolution of the Wigner function obtained by using eigenvalues and eigenfunctions. The phases and the negative regions of the Wigner function are correctly reproduced. The difference between the eigenfunction solution and the explicit solution is small. For example, for $`p=0.6`$ at $`t=3`$, the maximum value of the eigenfunction solution of the Wigner function is 0.9313 at $`x=1.692`$, and the explicit solution gives 0.9206 at $`x=1.692`$. For this momentum $`p`$ and $`t=3`$, the minimum of the eigenfunction solution of the Wigner function is $`0.3888`$ at $`x=1.1667`$, and the the explicit solution gives $`0.3735`$ at $`x=1.1667`$. The positions of the maxima and minima in the two methods are the same, and the magnitudes differ by about 1%. The explicit solution of Eqs. (19)-(21) thus leads to an accurate determination of the time evolution of the Wigner function, even if it contains regions of negative or oscillating values.

## 5 Pseudoparticle Method and Approximations

As an approximation to obtain the explicit solution of Eqs. (4), (10) and (11), a pseudoparticle method was presented previously to calculate the time evolution of the Wigner function . It is useful to test the pseudoparticle method with our numerical example to assess its usefulness and accuracy.

To introduce the pseudoparticle method, we rewrite Eq. (3) in the form

$`f(𝒓𝒑,t)={\displaystyle 𝑑𝒓_0𝑑𝒑_0\mathrm{\Delta }(𝒑𝒑_0+_rV(𝒓,t)\delta t)\delta (𝒓𝒓_0\frac{𝒑}{m}\delta t)f(𝒓_0,𝒑_0,t_0)},`$ (46)
where

$`\mathrm{\Delta }(𝝅)={\displaystyle \frac{d𝒔}{(2\pi \mathrm{})^3}\mathrm{exp}\left[i\left\{\frac{𝒔𝝅}{\mathrm{}}+\frac{2\delta t}{\mathrm{}}\underset{n=1}{\overset{\mathrm{}}{}}\frac{1}{(2n+1)!}\left(\frac{𝒔_r^V}{2}\right)^{2n+1}V(𝒓,t)\right\}\right]},`$ (47)
and $`𝝅=𝒑𝒑_0+_rV(𝒓,t)\delta t`$. One notes that the second term in the exponential function is a sum involving third and higher powers of $`𝒔`$. If one neglects these higher-order terms in the exponential function, then one obtains the approximation

$`\mathrm{\Delta }(𝒑𝒑_0+_rV(𝒓,t)\delta t)\delta (𝒑𝒑_0+_rV(𝒓,t)\delta t)`$ (48)
and the time evolution of the Wigner function becomes

$`f(𝒓𝒑,t)f_{LO}(𝒓𝒑,t)={\displaystyle 𝑑𝒓_0𝑑𝒑_0\delta (𝒑𝒑_0+_rV(𝒓,t)\delta t)\delta (𝒓𝒓_0\frac{𝒑}{m}\delta t)f(𝒓_0,𝒑_0,t_0)}`$ (49)
which leads to

$`f(𝒓𝒑,t)f_{LO}(𝒓𝒑,t)=f(𝒓𝒑\delta t/m,𝒑+_rV(𝒓,t)\delta t,t_0).`$ (50)
The above equation provides the basis for the lowest-order (LO) pseudoparticle approximation of the time evolution of the Wigner function . One divides the phase space into cells (pseudoparticles) and follows the trajectories of these pseudoparticles using classical equations of motion, Eqs. (12) and (13). Eq. (50) specifies that the Wigner function at the new phase space point $`(𝒓𝒑)`$ at $`t=t_0+\delta t`$ is approximately the same as the initial Wigner function at the initial classical trajectory phase space point $`(𝒓𝒑\delta t/m,𝒑+_rV(𝒓,t)\delta t)`$ at $`t_0`$. The subscript $`LO`$ in $`f_{LO}(𝒓𝒑,t)`$ is to indicate that it is the solution of the lowest-order pseudoparticle approximation obtained by following classical trajectories. This method was used in  where it was found that the lowest-order pseudoparticle approximation reproduces quite well the general features of the time-dependent Hartree-Fock approximation. The use of classical trajectories to obtain an approximate time evolution of the Wigner function was also emphasized by Zachos and Curtright .

How good is the lowest-order pseudoparticle approximation? The accuracy of the pseudoparticle approximation depends on the potential $`V(𝒓,t)`$. If the potential is a constant, a linear, or a harmonic oscillator potential, then even the LO pseudoparticle method gives the exact solution, as is clearly indicated in Eq. (47). The LO pseudoparticle solution deviates from the correct solution if the third and higher order spatial derivatives of the potential do not vanish.

For the non-stationary state in a Gaussian potential in our test, we show the results of the LO pseudoparticle approximation in Figs. (2a’), (2b’), and (2c’), to be compared with the correct results from the eigenfunction method in Figs. (2a), (2b), and (2c). In our calculations, we specify the Wigner function at phase space coordinates of a fixed lattice. The Wigner function at the phase space points on the righthand side of Eq. (50) is obtained by interpolation using the Wigner function $`f(𝒓_0,𝒑_0,t_0)`$ at the earlier time $`t_0`$. As one observes, the general features of the oscillations are approximately reproduced. However, there are deviations from the correct results as time increases. For example, the Wigner function values for $`p=0`$, $`t=3`$, and $`|x|2`$ obtained in the LO pseudoparticle approximation in Fig. (2a’) are much larger than the corresponding correct values in Fig. (2a). The values of the Wigner function for $`p=0.6`$, $`t=3`$, and $`x1`$ in the LO pseudoparticle approximation in Fig. (2c’) are much smaller than the corresponding correct values in Fig. (2c).

We can correct for the deviations of the LO pseudoparticle approximation. For a small time increment $`\delta t`$, we can keep terms up to the first order in $`\delta t`$ in Eq. (47). The function $`\mathrm{\Delta }(𝝅)`$ becomes

$`\mathrm{\Delta }(𝝅)={\displaystyle \frac{d𝒔}{2\pi \mathrm{}}e^{i𝒔𝝅/\mathrm{}}\left[1+\frac{2i\delta t}{\mathrm{}}\underset{n=1}{\overset{\mathrm{}}{}}\frac{1}{(2n+1)!}\left(\frac{𝒔_r^V}{2}\right)^{2n+1}V(𝒓,t)\right]}.`$ (51)
The integration over $`𝒔`$ can be easily carried out and we obtain

$`\mathrm{\Delta }(𝝅)=\left[1+\delta t{\displaystyle \underset{n=1}{\overset{\mathrm{}}{}}}{\displaystyle \frac{1}{(2n+1)!}}\left({\displaystyle \frac{\mathrm{}}{2i}}\right)^{2n}(_r^V_p^\delta )^{2n+1}V(𝒓,t)\right]\delta (𝝅),`$ (52)
where $`_r^V`$ acts on $`V(𝒓,t)`$ and $`_p^\delta `$ acts on $`\delta (𝝅)`$. The corrected pseudoparticle solution of the time evolution of the Wigner function is then

$`f(𝒓𝒑,t)=\left[1+\delta t{\displaystyle \underset{n=1}{\overset{\mathrm{}}{}}}{\displaystyle \frac{1}{(2n+1)!}}\left({\displaystyle \frac{\mathrm{}}{2i}}\right)^{2n}(_r^V_p^f)^{2n+1}V(𝒓,t)\right]f_{LO}(𝒓,𝒑,t),`$ (53)
where $`_p^f`$ acts on $`f_{LO}(𝒓,𝒑,t)`$. It should be emphasized that no odd powers of $`\mathrm{}`$ and even powers of $`(_r^V_p^f)`$ are present in the above expansion. We can improve upon the pseudoparticle approximation by including additional contributions in powers of $`\mathrm{}^2`$ involving higher-order derivatives of $`V(𝒓,t)`$ and $`f_{LO}(𝒓,𝒑,t)`$.

We show in Figs. (2a”), (2b”), and (2c”) the results in the next-to-lowest order approximation obtained by including the correction term of order $`\mathrm{}^2`$, which involves the third derivatives of the potential and the Wigner function. In this calculation, we propagate the Wigner function from $`t_0`$ to $`t=t_0+\delta t`$ for a small time increment $`\delta t`$ following classical trajectories as in Eq. (49). The Wigner function is then corrected at time $`t`$ using Eq. (53). The corrected Wigner function at $`t`$ is used in Eq. (49) to propagate to time $`t+\delta t`$ by following classical trajectories. It is then corrected at time $`t+\delta t`$ using Eq. (53). These steps are repeated to obtain the time evolution of the Wigner function in this pseudoparticle approximation. To avoid numerical instability in the time evolution, we use the Wigner function $`f_{LO}(𝒓𝒑,t)`$ obtained in the lowest-order approximation to calculate the third momentum derivative, when we evaluate the $`\mathrm{}^2`$ correction term in Eq. (53).

Results in Fig. 2 indicate that the inclusion of the $`\mathrm{}^2`$ correction term in the next-to-lowest (NLO) order improves the pseudoparticle approximation. In particular, the NLO values of the Wigner function at $`p=0`$, $`t=3`$, and $`|x|2`$ obtained with $`\mathrm{}^2`$ corrections Fig. (2a”) are now closer to the values obtained with eigenfunctions. The NLO values of the Wigner function at $`p=0.6`$, $`t=3`$, and $`x1`$ in Fig. (2c’) are also closer to the corresponding values obtained with eigenfunctions. Although small deviations remain in the NLO solution, the general features of the Wigner function are reasonably well reproduced.

We give here an alternative method to evaluate the correction terms in the pseudoparticle method. As one notes in Eq. (52), the correction terms involve high-order derivatives of the $`\delta `$-function. They can be evaluated approximately by expressing the $`\delta `$-function in terms of known functions. Making use of the othonormality of the harmonic oscillator wave functions $`\{\varphi _m(x)\}`$, we can represent a one-dimensional delta function $`\delta (x)`$ by

$`\delta (x)={\displaystyle \underset{m=0}{\overset{\mathrm{}}{}}}\varphi _m^{}(x)\varphi _m(0)={\displaystyle \frac{\alpha }{\sqrt{\pi }}}e^{\frac{\alpha ^2x^2}{2}}{\displaystyle \underset{m=0}{\overset{\mathrm{}}{}}}H_{2m}(\alpha x){\displaystyle \frac{(1)^m}{2^{2m}m!}},`$ (54)
where $`H_{2m}(\alpha x)`$ is the Hermite polynomial of order $`2m`$, and $`\alpha `$ is a width parameter. In practice, the summation in the above equation is carried out up to an order $`M`$, and the delta function $`\delta (x)`$ can be approximated by the distribution

$`\delta (x)D(x)=A_M{\displaystyle \frac{\alpha }{\sqrt{\pi }}}e^{\frac{\alpha ^2x^2}{2}}{\displaystyle \underset{m=0}{\overset{M}{}}}H_{2m}(\alpha x){\displaystyle \frac{(1)^m}{2^{2m}m!}},`$ (55)
where $`A_M`$ is

$`A_M=\left[\sqrt{2}{\displaystyle \underset{m=0}{\overset{M}{}}}(1)^m{\displaystyle \frac{(2m)!}{2^{2m}m!m!}}\right]^1,`$ (56)
and $`A_M`$ is so chosen that $`D(x)`$ is normalized to $`D(x)𝑑x=1`$. A three-dimensional generalization of this $`D`$-function, $`D(𝒙)`$, can be obtained as the product of three one-dimensional $`D`$-functions of their respective component coordinates, $`D(x_x)D(x_y)D(x_z)`$. Using a distribution function of this type, we can write the explicit solution of the Wigner function as

$`f(𝒓𝒑,t)=f_{LO}(𝒓,𝒑,t)+\delta t{\displaystyle 𝑑𝒓_0𝑑𝒑_0\delta (𝒓𝒓_0\frac{𝒑}{m}\delta t)f(𝒓_0,𝒑_0,t_0)}`$
$`\times {\displaystyle \underset{n=1}{\overset{\mathrm{}}{}}}{\displaystyle \frac{1}{(2n+1)!}}\left({\displaystyle \frac{\mathrm{}}{2i}}\right)^{2n}\left[(_r^V_p^D)^{2n+1}V(𝒓,t)D(𝒑𝒑_0+\delta t_rV(𝒓,t))\right],`$ (57)
where $`_p^D`$ applies to $`D(𝒑𝒑_0+\delta t_rV(𝒓,t))`$. As $`D`$ is a known analytical function of $`𝒑`$, $`(_p^D)^{2n+1}D(𝒑𝒑_0+\delta t_rV(𝒓,t))`$ can be obtained analytically. The higher-order derivatives of the Wigner function in Eq. (53) can be converted into an integration over $`𝒑_0`$.

The pseudoparticle method utilizes classical trajectories and is easy to use. It is even exact for a constant, linear, or harmonic oscillator potential. The development of systematic higher-order corrections to the pseudoparticle method for a general potential in Eq. (53) allows one to improve on the approximate solution to make the pseudoparticle method a useful tool for future applications.

In applying the pseudoparticle method, one can use the Eulerian picture with a fixed lattice or alternatively the Lagrangian picture with a set of pseudoparticle phase space coordinates, as in molecular dynamics. The distribution $`D`$ of Eq. (55) can be used to go from one picture to the other. For example, if one starts with a Wigner function in the Eulerian picture, one divides the phase space into pseudoparticle cells with volume element $`\mathrm{\Delta }𝒓_i\mathrm{\Delta }𝒑_i`$ and specifies the phase space coordinates $`(𝒓_i𝒑_i)`$ and its Wigner function $`f(𝒓_i𝒑_i)`$. The set of variables $`(𝒓_i𝒑_i)`$ and $`f_L(𝒓_i𝒑_i)`$$`(=f(𝒓_i𝒑_i))`$ can be used in the Lagrangian picture to evolve the phase space dynamics. Conversely, if one is given the set of variables $`(𝒓_i𝒑_i)`$ and $`f_L(𝒓_i𝒑_i)`$ in the Lagrangian picture, then the Wigner function in the Eulerian picture $`f_E(𝒓𝒑)`$ at coordinates $`(𝒓𝒑)`$ is given by

$`f_E(𝒓𝒑)={\displaystyle \underset{i}{}}D_r(𝒓𝒓_i)D_p(𝒑𝒑_i)f_L(𝒓_i𝒑_i)\mathrm{\Delta }𝒓_i\mathrm{\Delta }𝒑_i,`$ (58)
where the width parameter $`\alpha `$ in $`D_r`$ (and $`D_p`$) depends on the magnitude of $`\mathrm{\Delta }𝒓_i`$ (and $`\mathrm{\Delta }𝒑_i`$). These transcriptions between the two pictures facilitate the application of the pseudoparticle method.

## 6 Conclusions and Discussions

We have reviewed and applied here the explicit solution of the time evolution of the Wigner function obtained previously in 1982 . The basic idea is to represent the Wigner function in terms of auxiliary phase space coordinates, which obey simple equations of motion. These equations are similar to the classical equations of motion. They can be solved easily. The solutions of these equations of motion can then be used to evaluate the time evolution of the Wigner function. We have demonstrated the usefulness of the explicit solution using a numerical example. We find that the explicit solution leads to the correct time evolution of the Wigner function, even for a Wigner function with strong spatial and temporal variations and regions of negative values.

We have also reviewed and tested the pseudoparticle method for the evaluation of the time evolution of the Wigner function. For our example of a non-stationary state in a Gaussian potential, the lowest-order pseudoparticle approximation gives the correct features of the time evolution, but there are deviations from the correct results. We have developed a systematic way to improve the pseudoparticle method involving correction terms in powers of $`\mathrm{}^2`$ containing high-order derivatives of the potential and the Wigner function.

The simplicity of the different methods discussed here will facilitate their application to quantum dynamics in phase space. They can be used to study quantum particle dynamics in a time-dependent, multi-dimensional potential. They can also be applied to study the one-body Wigner function of a many-particle system in a time-dependent mean-field potential, as in . With the addition of a collision term, they can be used to describe the dynamics of a quantum Boltzmann equation. The explicit solution of Eqs. (19)-(21) or (22)-(23) is probably best handled in a lattice of phase space points, as the sine and cosine transforms are simplest in such a lattice. On the other hand, the pseudoparticle method of Eqs. (49) and (53) can be investigated both in terms of pseudoparticle phase space coordinates in the Lagrangian picture or alternatively in a fixed lattice of phase space points in the Eulerian picture. The use of pseudoparticle coordinates may provide substantial saving of computer storage capacity when a significant fraction of the phase space is empty. Future research using these methods will allow us to explore further the richness of quantum dynamics in phase space, which Professor Wigner first pioneered for us.

The author would like to thank Drs. E. Pollak and P. G. Reinhard for helpful discussions and communications. This research was supported by the Division of Nuclear Physics, Department of Energy, under Contract No. DE-AC05-00OR22725 managed by UT-Battelle, LLC.

## References


format: text

text:
# Global and local Complexity in weakly chaotic dynamical systems11footnote 1AMS: 37B99, 37B40, 37A35.

## 1 Introduction

Weakly chaotic phenomena are widely studied in the physical literature. There are connections with many physical phenomena: self organized criticality, the anomalous diffusion processes and many others.

In the literature a precise definition of weak chaos is not given and many different examples are studied. Roughly speaking a weakly chaotic system is a system that is chaotic in some sense (for example it has sensitive dependence to initial conditions) but it has zero entropy (KS-entropy or topological entropy) in this work we will mainly consider systems having zero topological entropy.

For the classification of weakly chaotic systems there have been proposed many invariants. Some of them are defined by a generalization of K-S entropy (,,) orbit complexity () or based on growth rate of the number of different orbits with respect to a partition and an invariant measure ().

Generalized orbit complexity associates to each point an indicator of the complexity of its orbit. This is a measure of the growth rate of the information that is necessary to describe the orbit while time increases.

In this sense orbit complexity can be viewed as a local version of the entropy, where a global (average) notion of information (the Shannon information) is replaced by a local one (the algorithmic information content). This is also confirmed by the relation (Theorem 10) between entropy and orbit complexity that can be proved in the positive entropy case.

Let us consider an orbit of a discrete time dynamical system. The definition of orbit complexity associates to the orbit a set of strings by a geometrical construction and then the information content of the strings is considered to define the complexity of the orbit. For this purpose we need an intrinsic (pointwise) notion of information content of a string.

Such an intrinsic notion of information content is is given for example by the Algorithmic Information Content ( also called Kolmogorov-Chaitin complexity). Other notions of information content can be considered ( ) but for the purposes of this paper we will only consider AIC as a measure for the information content that is contained in a string.

Generalized orbit complexity turns out to be related to another important feature of chaos: the sensitivity to initial conditions. In  quantitative relations are proved between the growth rate of the information needed to describe an orbit, quantitative indicators of sensitivity to initial conditions and the dimension of the underlying space.

In this paper we consider a notion of orbit complexity that is particularly suited for systems where the information necessary to describe an orbit increases particularly slowly as the time increases. This give a slight modification of the orbit complexity indicators defined in . We also consider a sort of generalized topological entropy defining a family of invariants of topological dynamical systems that contains the classical definition of topological entropy as a special case. This generalized topological entropy provides a family of invariants that can distinguish between topological dynamical systems with zero entropy, characterizing the global complexity of its behavior.

One of the main results (Theorem 35) of the paper is that if a system is constructive (the map can be approximated by an algorithm, see Section 5 for a precise definition) orbit complexity (the local indicator of complexity of the system) is less or equal than generalized topological entropy (the global indicator) while if the system is not constructive this inequality does not hold, proving that constructivity comes out naturally when considering Algorithmic information content based notions of complexity.

Another main result is a criterion (Proposition 14) to find systems with non trivial orbit complexity. This criterion implies for example that a system that is chaotic in the sense of Li and Yorke has nontrivial orbit complexity. This criterion implies (Remark 15) that orbit complexity provides invariants that can distinguish between dynamical systems that that are isomorphic in the measure preserving framework.

In Section 2 we give a short introduction to the concept of algorithmic information content.

In Section 3 we introduce two different notions of complexity of single orbits given by two different variants of the notion of information content of a string. After the definition of this invariants of the dynamics we give some example of its calculation in different examples of dynamical systems. We also state an easy criterion (Theorem 14) to find systems with nontrivial orbit complexity.

In Section 4 we define a global indicator of the complexity of a dynamical system. The indicator generalizes in some sense the topological entropy, taking into account different possible asymptotic behaviors of the number of substantially different orbits that appears in $`n`$ steps of the dynamics.

In Section 5 we introduce the concept of constructivity. Roughly speaking a map is constructive if the map can be approximated at any accuracy by some algorithm. A rigorous definition can be given for maps between very general metric spaces. Constructivity of the map underlying the dynamics is an assumption that implies interesting features of orbit complexity and relation with other indicators of complexity and chaos (section 6).

In Section 6 we prove that if the map is constructive then the orbit complexity of each point is less or equal than the indicator of global complexity. Constructivity is an essential assumption. An example is given to show that even in the compact case there are (non constructive) maps with big orbit complexity and low global complexity.

## 2 Algorithmic Information content

In this section we give a short introduction to algorithmic information theory. A more detailed exposition of algorithmic information theory can be found in  or .

The AIC associates to a single string a measure of the information content of a string, that depends (up to a constant) only on the given string. This is a very powerful tool and allows pointwise definitions.

Let us consider the set $`\mathrm{\Sigma }=\{0,1\}^{}`$ of finite (possibly empty) binary strings. If $`s`$ is a string we define $`|s|`$ as the length of $`s`$.

The Algorithmic Information Content (AIC) of a string is the length of the smallest program to be run by some computing machine giving the string as the output. In other words the AIC of a string is the length of its shorter algorithmic description.

For example the algorithmic information content of a $`2n`$ bits long periodic string

$$s=^{\prime \prime }1010101010101010101010\mathrm{}^{\prime \prime }$$

is small because the string is output of the short program:

repeat $`n`$ times (write (“10”)).

The AIC of the string $`s`$ then satisfies $`AIC(s)log(n)+Constant`$. This is because $`log(n)`$ bits are sufficient to code “$`n`$” (in binary notation) and the constant represents the length of the code for the computing machine representing the instructions “repeat…”. As it is intuitive the information content of a periodic string is very poor. On the other hand each $`n`$ bits long string

$$s^{}=^{\prime \prime }1010110101010010110\mathrm{}^{\prime \prime }$$

is output of the trivial program

$$write(^{\prime \prime }1010110101010010110\mathrm{}^{\prime \prime }).$$

This has length $`n+constant`$. This implies that the AIC of each string is (modulo a constant which depends on the chosen computing machine) less or equal than its length.

The concept of computing machine can be formalized by the theory of Turing machines or recursive functions. For our intuitive approach let us think that a computing machine is an every day computer $`C`$ to which it can be given some program to run. If we give it a program $`p`$ (coded by some binary string) to be run and the computation stops we obtain an output $`s`$ (another string) in this case we write $`C(p)=s`$. We can suppose that the output is a string made of digits in a finite alphabet. $`C`$ then defines a function from a subset of the set of the finite binary strings (where the computation stops) to the set of finite strings from a finite alphabet. In the language of theoretical computer science this means that $`C`$ defines a partial recursive function. If conversely the computation stops and the output is defined for each input then we say that $`C`$ defines a total recursive function. Recursive functions are functions whose values can be calculated by some algorithm. By this notations we can define more formally

###### Definition 1 (Algorithmic Information Content).

The Kolmogorov complexity or Algorithmic Information Content of a string $`s`$ given $`C`$ is the length of the smallest program $`p`$ giving $`s`$ as the output:

$$AIC_C(s)=\underset{p\mathrm{\Sigma },C(p)=s}{min}|p|,$$

if $`s`$ is not a possible output for the computer $`C`$ then $`AIC_C(s)=\mathrm{}`$ .

In the last definition the algorithmic information content of a string depends on the choice of $`C`$. To avoid this problem we require that $`C`$ is an universal machine. Roughly speaking a computing machine is called universal if it can emulate each other machine if an appropriate input is given.

In the examples above we have that the programs are written in a ”Pascal like” language and $`C`$ is represented by a system able to run such program. $`C`$ is then essentially a Pascal interpret.

Let us consider $`C`$, the above Pascal interpret and let $`D`$ be a Lisp interpret. Since using Pascal language we can write a program $`L`$ which is a Lisp interpret we have that for each Lisp program $`p`$ we have $`D(p)=C(L,p)`$ and then $`|AIC_C(s)AIC_D(s)||L|`$ for each string $`s`$.

A formal definition of universal computing machine of course can be given. In this definition we also have to specify the meaning of the “,” in “$`L,p`$”. Indeed a pair of binary strings can be encoded into a single binary string in a way that both the strings can be recovered from the encoded string whitout loosing information. For example such an encoding can be done by adding $`p`$ to a self delimiting description of $`L`$ (an encoding of $`L`$ that starts specifying its length). However we will not go into technical details, for our scope it is sufficient to think to universal computing machines as our every day computer that can be programmed for general purposes tasks. The only important difference we have to consider is that theoretical computing machines have virtually infinite memory, that is, while computing they can write (and then read) data on an infinite tape.

The important property of Universal Computing Machines (UCM) that will be used here is the following.

###### Theorem 2.

If $`𝒰`$ and $`𝒰^{}`$ are universal computing machines then

$$\left|AIC_𝒰(s)AIC_𝒰(s)\right|K(𝒰,𝒰^{})$$

where $`K(𝒰,𝒰^{})`$ is a constant which depends only on $`𝒰`$ and $`𝒰^{}`$ but not on $`s`$.

This theorem sates that if we use an UCM in the definition of the algorithmic information content then this information content does not depends on the particular machine we choose in this class up to a constant. Since we are interested to the asymptotic behavior of the quantity of information this constant is not relevant and this remark allows to not mention the chosen machine $`𝒰`$ in the notation $`AIC_𝒰(s)`$ in the future. In the remaining part of the paper the universal computing machine that is considered in the definition of AIC will be denoted by U.

We also want to consider the information that is necessary to reconstruct a string $`s`$ once another string $`s^{}`$ is known.

As it was said before there are many ways to encode a pair of strings into a single string. Let us choose such an encoding $`s^{},s<s^{},s>`$ and suppose that it is injective and recursive.

Being universal our computing machine can be also supposed to be able to recognize this encoding and recover both strings from the encoded string. Now we can define

###### Definition 3.

The conditional $`AIC`$ of $`s`$ given $`s^{}`$ is the length of the shortest program that is able to reconstruct the string $`s`$ when $`s^{}`$ is given:

$$AIC(s|s^{})=\underset{𝒰(<s^{},p>)=s}{min}|p|.$$

Up to a constant the definition is independent on the encoding that is chosen for the pair. This is because for each pair of chosen encodings there is an algorithm translating one encoding in the other for each pair of strings and this program will only add a constant in the definition of information content.

## 3 Orbit complexity

We give two definitions of orbit complexity. One is based on the plain algorithmic information content and is the definition that was given in , the other is based on the algorithmic information of a sting given its length. The latter is particularly suited for very regular orbits.

Let us consider a dynamical system $`(X,T)`$. $`X`$ is a compact metric space and $`T`$ is a function $`XX`$. Until section 4 $`T`$ is not necessarily supposed to be continuous. Let us consider a finite open cover $`\beta =\{B_0,B_1,\mathrm{},B_{N1}\}`$ of $`X`$, that is a collection of open sets whose union is the whole space.

We use this cover to code the orbits of $`(X,T)`$ into a set of infinite strings. A symbolic coding of the orbits of $`X`$ with respect to the cover $`\{B_i\}`$ is a string listing the sets $`B_1,..,B_n`$ visited by the orbit of $`x`$ during the iterations of $`T`$. Since the sets $`B_i`$ may have non empty intersection then an orbit can have more than one possible coding. More precisely, if $`xX`$ let us define the set of symbolic orbits of $`x`$ with respect to $`\beta `$ as:

$$\phi _\beta (x)=\{\omega \{0,1,\mathrm{},N1\}^𝐍:n𝐍,T^n(x)B_{\omega (n)}\}.$$

The set $`\phi _\beta (x)`$ is the set of all the possible codings of the orbit of $`x`$ relative to the cover $`\beta `$.

###### Definition 4.

The information content of $`n`$ steps of the orbit of $`x`$ with respect to $`\beta `$ is defined as

$$K(x,T,\beta ,n)=\underset{\omega \phi _\beta (x)}{min}AIC_U(\omega ^n).$$

$$\widehat{K}(x,T,\beta ,n)=\underset{\omega \phi _\beta (x)}{min}AIC_U(\omega ^n|n).$$

where $`\omega ^n`$ is the string containing the first $`n`$ digits of $`\omega `$

We are interested to the asymptotic behavior of this information content when $`n`$ goes to infinity. We give a measure of such an asymptotic behavior by comparing the quantity of information necessary to describe $`n`$ step of the orbit with a function $`f`$ whose asymptotic behavior is known. For each monotonic function $`f(n)`$ with $`\underset{n\mathrm{}}{lim}f(n)=\mathrm{}`$ we define an indicator of orbit complexity by comparing the asymptotic behavior of $`AIC_U(\omega ^n)`$ or $`AIC_U(\omega ^n|n)`$ with $`f`$. From now on, in the definition of indicators $`f`$ is always assumed to be monotonic and tends to infinity.

###### Definition 5.

The complexity of the orbit of $`xX`$ relative to $`f`$ and $`\beta `$ is defined as:

$$K^f(x,T,\beta )=\underset{n\mathrm{}}{limsup}\frac{K(x,T,\beta ,n)}{f(n)}$$

in a similar way we define

$$\widehat{K}^f(x,T,\beta )=\underset{n\mathrm{}}{limsup}\frac{\widehat{K}(x,T,\beta ,n)}{f(n)}.$$

As it is intuitive, if we refine the cover the information needed to describe the orbit increases.

###### Lemma 6.

If $`\alpha `$ and $`\beta `$ are open covers of $`X`$ and $`\alpha `$ is a refinement of $`\beta `$ then for all $`f`$

$$K^f(x,T,\beta )K^f(x,T,\alpha )$$
(1)
$$\widehat{K}^f(x,T,\beta )\widehat{K}^f(x,T,\alpha ).$$
(2)
The proof of Eq. 1 is contained in  the proof of Eq. 2 is essentially the same.

As it was said before the definition of $`\widehat{K}^f`$ is particularly suited for very regular strings. It considers the information contained in the string without considering the information contained in its length. Since this quantity is less or equal than $`log(n)`$ then $`|\widehat{K}(x,T,\beta ,n)K(x,T,\beta ,n)|logn+C`$ and this implies

###### Proposition 7.

If $`log(n)=o(f(n))`$ then $`\widehat{K}^f(x,T,\beta )=K^f(x,T,\beta )`$.

Taking the supremum over the set of all finite open covers $`\beta `$ of the metric space $`X`$ it is possible to get rid of the dependence of our definition on the choice of the cover $`\beta `$ and define the complexity of the orbit of $`x`$:

###### Definition 8.

The complexity of $`x`$ with respect to $`f`$ is defined as

$$K^f(x,T)=\underset{\beta \{Opencovers\}}{sup}(K^f(x,T,\beta )).$$

$$\widehat{K}^f(x,T)=\underset{\beta \{Opencovers\}}{sup}(\widehat{K}^f(x,T,\beta )).$$

This definition associates to a point belonging to $`X`$ and a function $`f`$ a real number which is a measure of the complexity of the orbit of $`x`$ with respect to the asymptotic behavior of $`f`$. In some sense in the above definition the function $`f`$ plays a role similar to the parameter $`d`$ in the definition of $`d`$-dimensional Hausdorff measure. Each orbit will have a class of functions $`f`$ such that $`K^f(x)`$ is finite, characterizing the asymptotic behavior of the information that is necessary to describe the orbit.

We remark that in the definition above we used two different notions of “complexity” of a string. In principle the construction we made allows to use any measure of complexity of a string. In ,  for example a computable notion of information content based on data compression algorithms is considered.

Generalized orbit complexity is invariant under topological conjugation, as it is stated in the following theorem whose proof follows directly from the definitions:

###### Theorem 9 (Invariance).

If the dynamical systems $`(X,T)`$ and $`(Y,S)`$ are topologically conjugate, $`\pi :XY`$ is the conjugating homeomorphism, and $`\pi (x)=y`$ then $`K^f(x,T)=K^f(y,S)`$ and $`\widehat{K}^f(x,T)=\widehat{K}^f(y,S)`$.

From now on in the notation $`\widehat{K}^f(x,T)`$ we will avoid to explicitly mention the map $`T`$ when it is clear from the context. We now give some example of different behaviors of $`\widehat{K}^f(x)`$.

Periodic orbits. If $`x`$ is a periodic point some of the symbolic coding of its orbit is a periodic string. An $`n`$ digit long periodic string can be generated by a program containing the first period and the length of the string. Since $`n`$ is given by the definition of conditional information content $`\widehat{K}(x,n,V)C`$, where $`C`$ is a constant not depending on $`n`$ and $`\widehat{K}^f(x)=0`$ for each $`f`$.

Positive entropy. In the positive entropy case the main result is the following

###### Theorem 10 (Brudno’s main theorem).

Let $`(X,T)`$ be a dynamical system over a compact space. If $`\mu `$ is an ergodic probability measure on $`(X,T)`$, then

$$K^{id}(x,T)=h_\mu (T)$$

for $`\mu `$-almost each $`xX`$ ($`id`$ is the identity function and $`h_\mu (T)`$ is the KS entropy).

By theorem 10 and Proposition 7 it also follows that if a system is compact, ergodic and has positive Kolmogorov entropy then for almost all points we have $`\widehat{K}^{id}(x)=h_\mu `$ (and $`\widehat{K}^f(x)=\mathrm{}`$ if $`f=o(id)`$).

Manneville map. An important example is the piecewise linear Manneville map:

$$T_z(x)=\{\begin{array}{cc}\frac{\xi _{k2}\xi _{k1}}{\xi _{k1}\xi _k}(x\xi _k)+\xi _{k1}& \xi _kx<\xi _{k1}\\ \frac{xa}{1a}& ax1\end{array}$$
(3)
with $`\xi _k=\frac{a}{(k+1)^{\frac{1}{z1}}}`$ ,$`kN,z>2`$. This is a piecewice linear version of the Manneville map $`𝒯_z(x)=x+x^z(mod1)`$.

The Manneville map was introduced in  as an extremely simplified model of intermittent behavior in turbulence, then its mathematical properties was studied by many authors, And the map was applied as a model of other physical phenomena. By  which follows from  we have that if $`ϵ`$ is small enough then

$$_{[0,1]}\widehat{K}(x,n,ϵ)𝑑xn^{\frac{z}{z1}}$$

i.e. the Lesbegue average information that is necessary to describe the orbits of the Manneville map for $`z>2`$ increases as a power law with exponent $`\frac{1}{z1}`$. We remark that the above Manneville map has positive topological entropy then it is not weakly chaotic in a topological sense. By the result above we can say that the Manneville map in some sense is weakly chaotic with respect to the Lesbegue measure.

Logistic map at the chaos threshold. Now we calculate the complexity of the orbits of this widely studied dynamical system. We state a result that, using similar techniques slightly improves a result of  about the complexity of such a map.

To understand the dynamic of the logistic map at the chaos threshold let us use a result of  (Theorem III.3.5.)

###### Lemma 11.

The logistic map $`f_\lambda _{\mathrm{}}`$ at the chaos threshold has an invariant Cantor set $`\mathrm{\Omega }`$.

(1) There is a decreasing chain of closed subsets

$$J^{(0)}J^{(1)}J^{(2)}\mathrm{},$$

each of which contains $`1/2`$, and each of which is mapped onto itself by $`f_\lambda _{\mathrm{}}`$.

(2) Each $`J^{(i)}`$ is a disjoint union of $`2^i`$ closed intervals. $`J^{(i+1)}`$ is constructed by deleting an open subinterval from the middle of each of the intervals making up $`J^{(i)}`$.

(3) $`f_\lambda _{\mathrm{}}`$ maps each of the intervals making up $`J^{(i)}`$ onto another one; the induced action on the set of intervals is a cyclic permutation of order $`2^i`$.

(4) $`\mathrm{\Omega }=_iJ^{(i)}`$. $`f_\lambda _{\mathrm{}}`$ maps $`\mathrm{\Omega }`$ onto itself in a one-to-one fashion. Every orbit in $`\mathrm{\Omega }`$ is dense in $`\mathrm{\Omega }`$.

(5) For each $`k𝐍`$, $`f_\lambda _{\mathrm{}}`$ has exactly one periodic orbit of period $`2^k`$. This periodic orbit is repelling and does not belong to $`J^{(k+1)}`$. Moreover this periodic orbit belongs to $`J^{(k)}J^{(k+1)}`$, and each point of the orbit belongs to one of the intervals of $`J^{(k)}`$.

(6) Every orbit of $`f_\lambda _{\mathrm{}}`$ either lands after a finite number of steps exactly on one of the periodic orbits enumerated in 5, or converges to the Cantor set $`\mathrm{\Omega }`$ in the sense that, for each $`k`$, it is eventually contained in $`J^{(k)}`$. There are only countably many orbits of the first type.

###### Theorem 12.

In the dynamical system $`([0,1],f_\lambda _{\mathrm{}})`$, for each $`x[0,1]`$ and each $`f`$ $`\widehat{K}^f(x)=0`$.

Proof. By the theorem above (point 6) we have that each point $`x`$ either is eventually periodic (and the statement follows immediately) either its orbit converges to the attractor, that is the orbit of $`x`$ is eventually contained in $`J_k`$ for each $`k`$. Now let us consider a cover $`V`$ and let $`ϵ_V`$ its Lesbegue constant. Let $`K_V`$ be such that each interval in $`J_k`$ has diameter less than $`ϵ_V`$. Now if $`k>K_V`$ each interval of $`J_k`$ is contained in some set of $`V`$. Moreover, by point 3 above we know that the action of the map over $`J_k`$ is periodic. This implies that in the set $`\phi _V(x)`$ of symbolic orbits of $`x`$ there is an eventually periodic string and then the statement follows easily. $`\mathrm{}`$

Chaotic maps with zero topological entropy. In  Smital showed an interval map that is continuous, it has 0-topological entropy and it is chaotic in the sense of Li and Yorke. The Smital’s weakly chaotic maps have non trivial orbit complexity, that is: there is an uncountable set of points $`S`$ such that for each $`xS`$ there is $`f`$ such that $`\widehat{K}^f(x)>0`$. This is implied by Theorem 14 below.

In order to prove it we give the definition of weak scattering set, this is a notion that is weaker than the notion of scattering set used in the Li-Yorke definition of chaotic map (see  e.g.).

###### Definition 13.

A set $`S`$ is called a weak scattering set if there is a $`\delta `$ such that for all $`x,yS,xy`$ implies $`\underset{n\mathrm{}}{limsup}d(T^n(x),T^n(y))>\delta `$.

A point is said to have nontrivial orbit complexity if $`f`$ with $`\widehat{K}^f(x)>0`$. The following is an easy criterion to find systems with nontrivial orbit complexity.

###### Theorem 14.

If $`(X,T)`$ has an uncountable weak scattering set $`S`$, then there is a set $`S^{}`$ with $`\mathrm{\#}(S^{})<\mathrm{\#}(S)`$ such that for each $`xSS^{}`$ $`x`$ has nontrivial orbit complexity.

Proof. The proof is based on a cardinality argument. First we proof that $`x,f`$ such that $`K^f(x)>0`$. Conversely let us suppose that there are not such points. This implies that given any cover $`V=\{B_1,\mathrm{},B_v\}`$ for each $`x`$ there is a finite set of programs $`P_x=\{p_{}^{1}{}_{x}{}^{},\mathrm{},p_{}^{k}{}_{x}{}^{}\}`$ such that $`n`$ the simplest symbolic orbit $`\omega ^n`$ of $`x`$ with respect to $`V`$ (that is such that $`AIC(\omega ^n|n)=\underset{\omega \phi _V(x)}{min}AIC(\omega ^n|n)`$) is such that $`\omega ^n=𝒰(p_{}^{i}{}_{x}{}^{},n)`$ for some $`p_{}^{i}{}_{x}{}^{}P_x`$. Now the set $`P=\{P_x|xX\}`$ is countable because is contained in the finite parts of a countable set (the set of all programs). This implies that there is a set $`ZS`$ with $`\mathrm{\#}(Z)=\mathrm{\#}(S)`$ such that for each $`xZ`$ the set $`S_x=\{yS,P_y=P_x\}`$ is uncountable.

Now the set of possible infinite symbolic orbits associated to the set of programs $`P_x`$ is finite. Let us consider the set $`W_{P_x}=\{\omega \{1,\mathrm{},v\}^𝐍s.t.nik,\omega ^n=𝒰(p_{x}^{}{}_{}{}^{i},n)\}`$ (that is the set of symbolic orbits that can be generated from the set of programs $`P_x`$) this set is finite and has $`\mathrm{\#}(W_{P_x})k`$. This leads to a contradiction. By the definition of $`W_{P_x}`$ each point of $`S_x`$ must be such that there is an $`\omega W_{P_x}\phi _V(x)`$ (the set $`W_{P_x}`$ is the set of the possible orbits related to $`P_x`$). But now, since $`S_xS`$ is weakly scattering if $`diam(V)<\delta `$ we have that if $`xy`$ then $`\phi _V(x)\phi _V(y)=\mathrm{}`$ because at some time the orbits of the two points will be contained in sets of $`V`$ having of course empty intersection because the distance of the two points is such that they cannot be in the same set of $`V`$. Since $`W_{P_x}`$ is finite then is not possible that $`xW_{P_x}\phi _V(x)\mathrm{}`$. This ends the first part of the proof. Now let us consider the scattering set $`S_1`$ with $`S_1=Sx`$. $`S_1`$ does not contain $`x`$ and still verifies the assumptions of the theorem, then by the first part of this proof there is $`yx`$ such that $`y`$ has nontrivial orbit complexity. In this way by induction we prove the full theorem.$`\mathrm{}`$

###### Remark 15.

By a result of Misiurewikscz () each zero entropy, continuous map on the interval is metrically hisomorphic to the adding machine for each non atomic invariant measure.

Then even the Smital’s map are hisomorphic to the adding machine from the measure preserving point of view. The orbit complexity of such maps is different from the complexity of other zero entropy continous maps of the interval (logistic map e.g.).

This implies that orbit complexity in this case is more sensitive than any invatiant constructed in the measure-preserving framework.

## 4 Generalized topological entropy

We give the definition of an indicator of the global topological complexity of the system. Similarly to the classical definition of topologial entropy. This indicator will measure the asymptotical behavior of the number of substantially different orbits that appears in the dynamics.

Let $`X`$ be a compact metric space and $`TC^0(X,X)`$. If $`x,yX`$ let us say that $`x,y`$ are $`(n,ϵ)`$ separated if $`d(T^k(x),T^k(y))>ϵ`$ for some $`k\{0,\mathrm{},n1\}`$. If $`d(T^k(x),T^k(y))ϵ`$ for each $`k\{0,\mathrm{},n1\}`$ then $`x,y`$ are said to be $`(k,ϵ)`$ near. A set $`EX`$ is called $`(n,ϵ)`$ separated if $`x,yE,xy`$ implies that $`x`$ and $`y`$ are $`(n,ϵ)`$ separated.

Moreover a set $`EX`$ is called an $`(n,ϵ)`$ net if $`xX`$ $`yEs.t.`$ $`x`$ and $`y`$ are $`(n,ϵ)`$ near.

We remark that a maximal $`(ϵ,n)`$ separated set is a $`(2ϵ,n)`$ net.

Let us consider as in the classical definition of topological entropy

$$s(n,ϵ)=max\{card(E):EXis(n,ϵ)separated\}.$$

We choose a monotone function $`f`$ such that $`\underset{n\mathrm{}}{lim}f(n)=\mathrm{}`$ as before and define

$$h^f(T,ϵ)=\underset{n\mathrm{}}{limsup}\frac{\mathrm{log}(s(n,ϵ))}{f(n)}$$

$`h^f(T,ϵ)`$ is monotone in $`ϵ`$ so we can define

$$h^f(T)=\underset{ϵ0}{lim}h^f(T,ϵ).$$

Let us consider

$$r(n,ϵ)=min\{card(E):EX,Eisa(n,ϵ)net\}.$$

Since $`r(n,ϵ)s(n,ϵ)`$ and (see  p. 268) $`s(n,ϵ)r(n,\frac{ϵ}{2})`$ in the definition of generalized topological entropy $`h^f`$ we can also consider instead of $`s(n,ϵ)`$ the number $`r(n,ϵ)`$ and obtain an equivalent definition.

We also give a third equivalent possible definition, using open covers. Let $`U`$ and $`V`$ two open covers of $`X`$. We denote by $`UV`$ the least common refinement (or join) of $`U`$ and $`V`$. If $`U`$ is an open cover, let us denote by $`N(U)`$ the minimum cardinality of the subcovers of $`U`$, and let $`H(U)=log(N(U))`$. Let us consider

$$𝚑^f(T,U)=\underset{n\mathrm{}}{limsup}\frac{H(UT^1(U)\mathrm{}T^n(U))}{f(n)}$$

and

$$𝚑^f(T)=\underset{finiteopencovers}{sup}𝚑^f(T,U).$$

We remark that (see  page 268) if $`ϵ>diam(U)`$ then

$$N(UT^1(U)\mathrm{}T^n(U))s(n,ϵ)$$

and if $`ϵ`$ is the Lesbegue number of $`U`$ then

$$N(UT^1(U)\mathrm{}T^n(U))r(n,ϵ).$$

By this it follows that

###### Proposition 16.

For each $`f`$ $`𝚑^f(T)=h^f(T)`$ and the definitions are equivalent.

By this is also follows that $`h^f`$ is invariant under isomorphisms of dynamical systems.

###### Proposition 17.

If $`(X,T)`$, $`(Y,T^{})`$ are topological dynamical systems, $`\psi :XY`$ is an homeomorphism such that

$$\begin{array}{ccccc}& & \psi & & \\ & X& & Y& \\ \hfill T& & & & T^{}\hfill \\ & X& & Y& \\ & & \psi & & \end{array}$$
(4)
commutes, then for each $`f`$ $`h^f((X,T))=h^f((Y,T^{}))`$.

Proof.  Since $`\psi `$ is an homeomorphism then it sends an open cover of $`X`$ to an open cover of $`Y`$ and it is easy to see that since the diagram commutes $`𝚑^f((X,T))=𝚑^f((Y,T^{}))`$. By Proposition 16 we also have $`h^f((X,T))=h^f((Y,T^{}))`$. $`\mathrm{}`$

Now we state a result which is useful to characterize the systems where the generalized topological entropy is null for each $`f`$.

###### Definition 18.

A system $`(X,T)`$ is said to be equicontinuous if for any $`ϵ>0`$ there is $`\eta >0`$ such that if $`x,yX`$ with $`d(x,y)<\eta `$ then for any $`n𝐍`$ one has $`d(T^n(x),T^n(y))<ϵ`$.

If $`(X,T)`$ is not equicontinuous there are $`ϵ>0`$ and a point $`xX`$ such that for any $`\eta >0`$ one can find $`yX`$ with $`d(x,y)<\eta `$ and $`n𝐍`$ such that $`d(T^n(x),T^n(y))>ϵ`$.

A point $`xX`$ is called an equicontinuity point if for any $`ϵ>0`$ there is $`\eta >0`$ such that if $`yX`$ with $`d(x,y)<\eta `$ then for any $`n𝐍`$ one has $`d(T^n(x),T^n(y))<ϵ`$; obviously a system is equicontinuous if all its points are equicontinuity points.

Let us cite the following fundamental result from  about the topological complexity of a dynamical system.

###### Theorem 19.

Let $`(X,T)`$ be a dynamical system, $`X`$ is compact, $`T`$ is continuous The two following statement are equivalent:

(1) $`(X,T)`$ is equicontinuous.

(2) For any finite open cover $`U`$ of $`X`$, $`N(UT^1(U)\mathrm{}T^n(U))`$ is bounded.

By this it follows that

###### Proposition 20.

$`(X,T)`$ is equicontinuous if and only if for each $`f`$ it holds $`h^f((X,T))=0`$.

The next result shows that for the logistic map at the chaos threshold $``$ $`f`$ such that $`\widehat{K}^f(x)<h^f(T)`$ for each $`x[0,1]`$. This is an example of a system where local and global complexity are quite different. In the following (Theorem 35) we will see that in general $`\widehat{K}^f(x)h^f(T)`$ for a wide class of dynamical systems.

###### Theorem 21.

The logistic map $`f_\lambda _{\mathrm{}}`$ is not equicontinuous and then there is some $`f`$ such that $`h^f(f_\lambda _{\mathrm{}})>0`$.

Proof. By Lemma 11 we have that either an orbit is eventually periodic or it converges to the attractor $`\mathrm{\Omega }`$ and the orbit is dense on the attractor, then let $`p`$ be periodic and $`r=d(orb(p),\mathrm{\Omega })`$. In each neighborhood of the periodic point there is a point $`x`$ that converges to the attractor and then $`limsup(d(T^n(x),T^n(p)))>r`$. The point $`p`$ cannot be an equicontinuity point. The statement follows then from Theorem 19 $`\mathrm{}`$

## 5 Computable Structures, Constructivity

In this section we give a rigorous notion of constructive map and the results about constructive mathematics that are necessary in the following. Constructive functions can be considered in some sense as algorithms acting over metric spaces. All function that can be concretely defined and effectively calculated are constructive. Algorithms works with strings, if strings are interpreted as points of a metric space we have the possibility to relate the world of continuum mathematics with the world of algorithms. This is what is currently done when expressing a point of a metric space by a symbolic notation. For example $`\frac{\pi }{2}`$ is a symbolic string that represents a point of the metric space $`𝐑`$ and allows to calculate a symbolic representation for the value of $`sin(\frac{\pi }{2})`$ by some algorithm (because $`sin`$ is a constructive function). An interpretation function is a way to interpret a string as a point of the metric space. An interpretation is said to be computable if the distance between ideal points is computable with arbitrary precision:

###### Definition 22 (Computable interpretation).

A computable interpretation function on $`(X,d)`$ is a function $`I:\mathrm{\Sigma }X`$ such that $`I(\mathrm{\Sigma })`$ is dense in $`X`$ and there exists a total recursive function $`D:\mathrm{\Sigma }\times \mathrm{\Sigma }\times 𝐍𝐐`$ such that $`s_1,s_2\mathrm{\Sigma },n𝐍`$:

$$|d(I(s_1),I(s_2))D(s_1,s_2,n)|\frac{1}{2^n}.$$

A point $`xX`$ is said to be ideal if it is the image of some string: $`x=I(s),s\mathrm{\Sigma }`$.

Two interpretations are said to be equivalent if the distance from an ideal point from the first and a point from the second is computable up to arbitrary precision.

###### Definition 23 (Equivalence of interpretations).

Let $`I_1`$ and $`I_2`$ be two computable interpretations in $`(X,d)`$; we say that $`I_1`$ and $`I_2`$ are equivalent if there exists a total recursive function $`D^{}:\mathrm{\Sigma }\times \mathrm{\Sigma }\times 𝐍𝐐`$, such that $`s_1,s_2\mathrm{\Sigma },n𝐍`$:

$$|d(I_1(s_1),I_2(s_2))D^{}(s_1,s_2,n)|\frac{1}{2^n}.$$

For example, finite binary strings $`s\mathrm{\Sigma }`$ can be interpreted as rational numbers by interpreting the string as the binary expansion of the number. Another interpretation can be given by interpreting a string as an encoding of a couple of integers whose ratio gives the rational number. If the encoding is recursive, the two interpretation are equivalent.

###### Proposition 24.

The relation defined by definition 23 is an equivalence relation.

For the proof of the above proposition see .

###### Definition 25 (Computable structure).

A computable structure $``$ on $`X`$ is an equivalence class of computable interpretations in $`X`$.

###### Remark 26.

We remark as a property of the computable structures that if $`B_r(I(s))`$ is an open ball with center in an ideal point $`I(s)`$ and rational radius $`r`$ and $`I(t)`$ is another point then there is an algorithm that verifies if $`I(t)B_r(I(s))`$. If $`I(t)B_r(I(s))`$ then the algorithm outputs “yes”, if $`I(t)B_r(I(s))`$ the algorithm outputs “no” or does not stop. The algorithm calculates $`D(s,t,n)`$ for each $`n`$ until it finds that $`D(s,t,n)+2^n<r`$ or $`D(s,t,n)2^n>r`$, in the first case it outputs “yes” and in the second it outputs “no”. If $`d(I(s),I(t))r`$ the algorithm will stop and output an answer.

We give a definition of morphism of metric spaces with computable structures. A morphism is heuristically a computable function between computable metric spaces. The definition states that if $`\mathrm{\Psi }`$ is a morphism the image of an ideal point can be calculated up to arbitrary precision by an algorithm.

###### Definition 27 (Morphism between computable structures).

If $`(X,d,)`$ and $`(Y,d^{},𝒥)`$ are spaces with computable structures; a function $`\mathrm{\Psi }:XY`$ is said to be a morphism of computable structures if $`\mathrm{\Psi }`$ is continuous and for each pair $`I,J𝒥`$ there exists a total recursive function $`D^{}:\mathrm{\Sigma }\times \mathrm{\Sigma }\times 𝐍𝐐`$, such that $`s_1,s_2\mathrm{\Sigma },n𝐍`$:

$$|d^{}(\mathrm{\Psi }(I(s_1)),J(s_2))D^{}(s_1,s_2,n)|\frac{1}{2^n}.$$

We remark that $`\mathrm{\Psi }`$ is not required to have dense image and then $`\mathrm{\Psi }(I())`$ is not necessarily an interpretation function equivalent to $`J`$.

###### Remark 28.

As an example of the properties of the morphisms, we remark that if a map $`\mathrm{\Psi }:XY`$ is a morphism then given a point $`xI(\mathrm{\Sigma })X`$ it is possible to find by an algorithm a point $`yJ(\mathrm{\Sigma })Y`$ as near as we want to $`\mathrm{\Psi }(x)`$.

The procedure is simple: if $`x=I(s)`$ and we want to find a point $`y=J(z_0)`$ such that $`d^{}(\mathrm{\Psi }(I(s)),y)2^m`$ then we calculate $`D^{}(s,z,m+2)`$ for each $`z\mathrm{\Sigma }`$ until we find $`z_0`$ such that $`D^{}(s,z_0,m+2)<2^{m1}`$. Clearly $`y=J(z_0)`$ is such that $`d^{}(\mathrm{\Psi }(x),y)2^m`$. The existence of such a $`z_0`$ is assured by the density of $`J`$ in $`Y`$. We also remark that by a similar procedure, given a point $`I(s_0)`$ and $`ϵ𝐐`$ it is possible to find a point $`I(s_1)`$ such that $`d(I(s_0),I(s_1))ϵ`$.

A constructive map is a morphism for which the continuity relation between $`ϵ`$ and $`\delta `$ is given by a recursive function.

###### Definition 29 (Uniformly constructive functions).

A function

$`\mathrm{\Psi }:XY`$ between spaces with computable structure $`(X,d,)`$, $`(Y,d^{},𝒥)`$ is said to be uniformly constructive if $`\mathrm{\Psi }`$ is a morphism between the computable structures and it is effectively uniformly continuous, i.e. there is a total recursive function $`f:𝐍𝐍`$ such that for all $`x,yX`$ $`d(x,y)<2^{f(n)}`$ implies $`d^{}(\mathrm{\Psi }(x),\mathrm{\Psi }(y))<2^n`$.

If a map between spaces with a computable structure is uniformly constructive then there is an algorithm to follow the orbit each ideal point $`x=I(s_0)`$.

###### Lemma 30.

If $`T:(X,)(X,)`$ is uniformly constructive, $`I`$ then there is an algorithm (a total recursive function) $`A:\mathrm{\Sigma }\times 𝐍\times 𝐍\mathrm{\Sigma }`$ such that $`k,m𝐍,s_0\mathrm{\Sigma }`$ $`d(T^k(I(s_0)),I(A(s_0,k,m)))<2^m`$.

Proof. Since $`T`$ is effectively uniformly continuous we define the function $`g_k(m)`$ inductively as $`g_1(m)=f(m)+1`$, $`g_i(m)=f(g_{i1}(m)+1)`$ where $`f`$ is the function of effective uniform continuity of $`T`$ (definition 29). If $`d(x,y)<2^{g_k(m)}`$ then $`d(T^i(y),T^i(x))<2^m`$ for $`i\{1,\mathrm{},k\}`$. Let us choose $`I`$. We recall that the assumption that $`T`$ is a morphism implies that there is a recursive function $`D^{}(s_1,s_2,n)`$ such that

$$|D^{}(s_1,s_2,n)d(I(s_1),T(I(s_2)))|<2^n.$$

Let us suppose that $`x=I(s_0)`$. Now let us describe the algorithm $`A`$: using the function $`D^{}`$ and the function $`f`$, $`A`$ calculates $`g_k(m)`$ and finds a string $`s_1`$ such that $`d(I(s_1),T(I(s_0)))<2^{g_k(m)}`$ as described in remark 28. This is the first step of the algorithm. Now $`d(T(I(s_1)),T^2(x))2^{(g_{k1}+1)}`$. We can use $`D^{}`$ to find a string $`s_2`$ such that $`d(I(s_2),T(I(s_1)))<2^{(g_{k1}+1)}`$. By this $`d(I(s_2),T^2(x))2^{g_{k1}}`$. This implies that $`d(T(I(s_2)),T^3(x))2^{(g_{k2}+1)}`$, then we find $`s_3`$ such that $`d(I(s_3),T(s_2))2^{(g_{k2}+1)}`$ and so on for $`k`$ steps. At the end we find a string $`s_k`$ such that $`d(I(s_k),T^k(x))2^m`$. $`\mathrm{}`$

Let us describe a certain class of nice balls covers that will be used in the following.

###### Definition 31.

If $`\alpha =\{B_1(y_1,r_1),\mathrm{},B_n(y_n,r_n)\}`$ is a ball cover of the metric space $`X`$ whose elements are balls with centers $`y_i`$ and radii $`r_i`$. We say that $`\alpha `$ is a nice cover if $`X\underset{i}{}B_i(y_i,\frac{r_i}{2})`$.

In other words $`\alpha `$ is a nice  cover if dividing the radius of the balls by $`2`$ we have again a cover.

###### Remark 32.

We remark that since the space is compact each open cover has a refinement which is a nice cover.

###### Remark 33.

If we have a nice cover $`\alpha =\{B_1(y_1,r),\mathrm{},B_n(y_n,r)\}`$ made of balls with ideal centers $`y_i=I(s_i)`$ and rational radius and we have $`xX`$ and an ideal point $`y=I(s)`$ such that $`d(x,y)<\frac{r}{2}`$ then it is possible to find a ball of $`\alpha `$ that contains $`x`$. Indeed we find by the properties of computable interpretations an $`y_i`$ such that $`d(y,y_i)<\frac{r}{2}`$ (see Remark 26). This is possible because the cover is nice. The ball in the cover with center $`y_i`$ will contain $`x`$.

By the above remark if we have an algorithm $`A()`$ to follow the orbit of ideal points as in Lemma 30 and a nice cover $`\alpha =\{B_1(y_1,r),\mathrm{},B_n(y_n,r)\}`$ made of balls with ideal centers and rational radius for each ideal point $`x`$ and $`n`$ it is possible to find by an algorithm a set $`B`$ of $`\alpha `$ such that $`T^n(x)B`$ and then we can construct a symbolic orbit of $`x`$ relative to $`\alpha `$. We remark that if $`n`$ is given (by the definition of $`AIC(s|n)`$) the lenght of a code implementing such an algorithm does not depend on $`n`$. Then we have

###### Lemma 34.

Let $`(X,)`$ is a metric space with a computable structure and

* $`\{B(x_i,r)\}_{1im}`$ is a nice cover made of balls with ideal centers and rational radius $`r`$,
* $`xX`$ is an ideal point
* $`P_{\frac{r}{2}}:𝐍\mathrm{\Sigma }`$ is such that $`k\{1,\mathrm{},n\}`$

$$d(T^k(x),I(P_{\frac{r}{2}}(k)))<\frac{r}{2}$$

is an algorithm to follow the orbit of $`x`$ with accuracy $`\frac{r}{2}`$ similar as above in Lemma 30.

then there is an algorithm $`P^{}:𝐍\{1,\mathrm{},m\}`$ such that $`ik,P^{}(i)=j`$ if $`T^i(x)B(x_j,r)`$. Moreover the length of a code implementing $`P`$ on an universal Turing machine is equal to the code for $`P^{}`$ up to a constant that does not depend on $`n`$.

## 6 Gen. Top. Entr. and Orbit complexity

###### Theorem 35.

If $`X`$ is compact and $`(X,T)`$ is constructive (for some computable structure over $`X`$) then for each $`f`$ and each $`xX`$

$$\widehat{K}^f(x)h^f(T).$$

Proof. Since the system is constructive by the use of the algorithm $`A()`$ (Lemma 30) following the orbit of an ideal point at any given accuracy and $`D()`$ approximating the distance $`d`$ at any given accuracy we have the following. If $`x,y`$ are ideal, $`I(z)=x,I(w)=y`$ and $`k𝐍,ϵ𝐐`$ then there is a procedure $`P(z,w,ϵ,k)`$ such that if there is a $`ik`$ such that $`d(T^i(x),T^i(y))>ϵ`$ then the procedure stops with output “YES”.

We also remark that if $`x=I(z)`$ is ideal $`I(z)=x`$ and there is $`yX`$ such that $`x,y`$ are $`(n,ϵ)`$ separated then we can find by a procedure $`P^{}(z,n,ϵ)`$ an ideal $`y^{}`$ such that $`x,y^{}`$ are $`(n,ϵ)`$ separated. The procedure $`P^{}`$ calculates $`P(z,v,n,ϵ)`$ for all strings $`v`$ in a “parallel” way until it finds a $`v`$ stopping the procedure with output YES. Such a $`v`$ must exist by the density of $`I`$ and the continuity of the map $`T`$.

We will prove that if $`\beta =\{B(x_1,2ϵ),\mathrm{},B(x_n,2ϵ)\}`$ is a nice cover with ideal centers and rational radius and $`ϵ`$ is small enough, then for each $`k𝐍`$ and $`xX`$ there is a program $`p_{k,ϵ}`$ such that $`𝒰(p_{k,ϵ},k)`$ is a symbolic coding of the first $`k`$ steps of the orbit of $`x`$ with respect to $`\beta `$ and $`|p_{k,ϵ}|log(s(k,\frac{ϵ}{2}))+C`$.

The idea is that by the constructivity (as it is said above) we can construct $`(n,ϵ)`$ separated sets and use them to select the points that give rise to separate orbits, moreover the number of these points is bounded by the topological entropy. Now let us see a more precise description of such a procedure.

The program $`p_{k,ϵ}`$ we want to describe now will contain a number $`n_x`$ with $`n_xs(k,\frac{ϵ}{2})`$ and a procedure to construct a symbolic orbit of $`x`$. The procedure runs as follows

First let us consider an empty list of strings: list=$`\mathrm{}`$

For each $`i𝐍,in_x`$ do :$`\{`$ by the above procedure $`P^{}()`$ find an ideal point that is $`(k,\frac{ϵ}{2})`$ separated from the points in the list and add the corresponding string to the list $`\}`$

Follow by the algorithm $`A()`$ (Lemma 30) with accuracy $`ϵ`$ the last point found in the list.

By the procedure stated in Lemma 34 produce a symbolic string associated to the cover $`\beta `$.

We remark that in the above procedure the number $`k`$ is given by the definition of $`AIC(s|k)`$.

If $`n_x`$ is big enough the previous procedure construct a maximal $`(k,\frac{ϵ}{2})`$ separated set. Now since a maximal $`(k,\frac{ϵ}{2})`$ separated set is also a $`(k,ϵ)`$ net, then each $`xX`$ is $`ϵ`$ near to some point found by the procedure above. The procedure then follows by the algorithm $`A()`$ with accuracy $`ϵ`$ the orbit of such a point and then produce the symbolic list associated with the given cover. Since $`n_xs(k,\frac{ϵ}{2})`$ then $`|p_k|log(s(k,\frac{ϵ}{2}))+C`$ and the statement follows. $`\mathrm{}`$

The assumption of constructivity in the above theorem is essential. There are examples of dynamical systems that are not constructive for any computable structure and violates the above inequality for each point.

###### Example 36.

Let us consider $`(X,T)`$ with $`X=S^1`$ and $`T(x)=x+r(mod1)`$ where $`r`$ is a non constructive number (See  for the definition of such numbers, see below for an example).

In this example, since $`T`$ is an isometry we have $`h^f(T)=0`$ for all $`f`$. But if $`r`$ is not constructive there is some $`f`$ such that $`\widehat{K}^f(x)>0`$ for all $`x`$.

The idea is that the knowledge of many steps of a symbolic orbit for $`x`$ with respect to the cover $`\beta `$ implies the knowledge of many digits of $`r`$.

In the following proposition we prove this fact when $`r=0.r_1r_2\mathrm{}`$ (binary expansion of $`r`$) is such that $`\underset{n\mathrm{}}{lim}\frac{AIC(r_1\mathrm{}r_n)}{n}=1`$ we call random such a real (this condition is satisfied for Lesbegue almost all reals). The proposition in the other cases is a straightforward generalization.

###### Proposition 37.

In the above example if $`r`$ is random we have that for each $`xX`$ $`\widehat{K}^{log}(x)>0`$ and $`h^f(T)=0`$ for each $`f`$.

Proof. Let $`xS^1`$ and $`\beta =\{B(x_1,r),\mathrm{},B(x_n,r)\}`$ a cover of $`S^1`$ with rational centers and radius. Without loss of generality we can suppose $`x=0`$.

Let $`p_k`$ be a program generating a sequence $`\omega _1,\mathrm{},\omega _{k1}`$ such that $`T^i(0)B(x_{\omega _i})`$.

By the use of $`p_k`$ it is possible to find a rational $`q`$ such that in the dynamical system $`T^{}:S^1S^1`$ defined by $`T^{}(x)=x+q(mod1)`$ the orbit of $`0`$ has the same associated $`k`$ steps symbolic orbit.

Since $`ik,d(T^i(0),T_{}^{}{}_{}{}^{i}(0))2ϵ`$ then $`|rq|\frac{2ϵ}{k}`$ and then the knowledge of $`k`$ steps of the orbit of $`0`$ with accuracy $`ϵ`$ implies the knowledge of $`r`$ up to accuracy $`\frac{2ϵ}{k}`$. This implies the knowledge of $`log(k)+C`$ binary digits of $`r`$. If $`r`$ was a random real this implies the statement. $`\mathrm{}`$

In  an example was given of a non constructive system over a non compact space having large orbit complexity while the map defining it is equicontinuous. This example showed in the non compact case that constructivity is essential to relate the complexity of the behavior of a system and chaos.

The last proposition implies that even in the compact case this is true. Constructivity comes out naturally when considering definitions of complexity which are based on the algorithmic information content.