%---------------------------------------- macros
\newcommand{\gsim}{ \raisebox{-.5ex}{\mbox{$\,\stackrel{>}{\sim}\,$}} }
\newcommand{\lsim}{ \raisebox{-.5ex}{\mbox{$\,\stackrel{<}{\sim}$\,}} }
\def\be{\begin{equation}}
\def\ee{\end{equation}}
\def\mod#1{\,({\rm mod\ }#1) }% modulus of a congruence
%---------------------------------------- format
\documentstyle[11pt]{article}
\textwidth=15truecm
\hoffset=-2.5truecm
\begin{document}
\baselineskip=17pt
\title{An algorithmic view of pseudochaos}
\author{B V Chirikov and F Vivaldi\dag \\ \\
Budker Institute of Nuclear Physics, 630090 Novosibirsk, Russia.\\
\dag \/ School of Mathematical Sciences, Queen Mary and Westfield \\
College, London E1 4NS, UK.
}
\maketitle
\begin{abstract}
The controversial concept of {\it quantum chaos\/}
---the dynamical chaos in bounded mesoscopic quantum systems---
is presented as the most important and universal instance of a
new generic dynamical phenomenon: {\it pseudochaos}.
The latter characterizes the irregular behaviour of dynamical
systems with {\it discrete\/} energy and/or frequency spectrum,
which include classical systems with {\it discrete phase space}.
The question of randomness is addressed in terms of the algorithmic
theory of dynamical systems, using the Arnold cat map for illustration.
The relationship between the algorithmic theory and
ergodic theory is discussed.
\end{abstract}
%------------------------------------------------------------------
\section{Introduction: the quantum--classical correspondence}
\label{section:Introduction}
A recent publication \cite{KrugerTroubetzkoy} has provided the
opportunity to reconsider the very controversial problem of
the so-called {\it quantum chaos,} that is, the statistical
properties of bounded mesoscopic quantum systems.
In spite of intensive studies into this problem (see, e.g., the
conference proceedings \cite{ConferenceProceedings}, and
also refs.~\cite{Zaslavsky,Sokolov,CasatiFordGuarneriVivaldi,
MixedReferencesII}) the physical meaning
and interpretation of quantum chaos remain vague, to the extent
that there is as yet no agreement even on the most basic question:
does any chaos at all exist in quantum mechanics?
We should clarify from the outset that the trivial
affirmative answer to this question (quantum mechanics is
fundamentally random) is irrelevant to our discussion.
For, even though the random element in quantum mechanics (`quantum
jumps') is unavoidable, it can be singled out and separated from
the `proper' quantum processes. The intrinsic randomness in quantum
mechanics is related only to a very specific event ---the {\it quantum
measurement}--- which is, in a sense, foreign to the quantum system
itself (see \cite{CasatiChirikov,ChirikovI,ChirikovII} for a discussion).
This allows us to divide the problem of quantum dynamics into two
qualitatively different parts:
\begin{itemize}
\item{} The proper quantum dynamics as described by the time-evolution
of the wavefunction $\psi$, which obeys some purely dynamical
(deterministic) equation, for example, the Schr\"o\-din\-ger equation.
The discussion below will be restricted to this aspect only.
\item{} The quantum measurement, which includes the registration of
the result, whence the collapse of the $\psi$-function.
Because no dynamical description of the quantum measurement is
as yet available, this issue remains vague.
In particular, there is no agreement on the question
of whether this is a real physical problem or an ill-posed one.
\end{itemize}
Recent advances in the studies of quantum `chaos'
have mostly relied on the aforementioned device
of separating out the dynamical part of quantum mechanics.
Such a philosophy is accepted ---at least implicitly--- by most
researchers in this field.
While the general aspects of quantum dynamics were
extensively studied since the early days of quantum mechanics,
the problem of quantum chaos arose only much later,
after the simpler phenomenon of classical chaos
was discovered and assimilated \cite{CasatiChirikov}.
Classical chaos has been central to the development of the
theory of dynamical systems, particularly of ergodic theory
\cite{ETBooks}.
As a general mathematical theory, ergodic theory need not
be restricted to classical mechanics only, and indeed its
application to quantum dynamics has led to surprising results.
For instance, it was discovered at an early stage
\cite{BermanZaslavsky,BerryEtAl,CasatiChirikovFordIzrailev},
and subsequently confirmed \cite{CasatiChirikov,Izrailev}, that
quantum mechanics does not typically allow `true' (classical-like) chaos.
This is because in quantum mechanics the energy and frequency spectra
of any bounded system are discrete, so that the motion is almost periodic.
Hence, according to ergodic theory, such quantum dynamics belongs to the
limiting case of regular motion, quite the opposite of dynamical chaos.
The ultimate origin of quantum almost-periodicity lies in
the discreteness of the phase space itself (or, more formally,
in the noncommutative geometry of the latter), which is the basis
of quantum physics and which is directly related to the uncertainty
principle.
At the same time, another fundamental principle ---the correspondence
principle--- requires the transition to classical mechanics in all cases,
and in particular when the classical system is chaotic.
This dichotomy lies at the heart of the present
controversy on quantum chaos.
An insight into this problem \cite{CasatiChirikov,ChirikovII,ChirikovEtAl}
was gained from the simple observation (well-known in principle,
though perhaps not in practice), that the sharp border between
discrete and continuous spectrum is physically meaningful only
in the limit $|t|\to\infty$, a regime routinely considered in ergodic theory.
The study of the {\it finite-time statistical
properties\/} of dynamical systems ---quantal as well as classical---
thus becomes a new strategic aim; accordingly, the existing ergodic theory will
require some modifications, so as to incorporate finite time explicitly.
Over a finite time, a discrete spectrum is dynamically equivalent
to a continuous one, thereby providing much stronger statistical
properties of motion than one would expect from asymptotic considerations.
In some cases, motions with discrete spectrum may exhibit
{\it all\/} the statistical properties of classical chaos,
albeit only on some {\it finite\/} time scales.
The most important time scale in quantum chaos is the
{\it relaxation time\/} $t_R$, which refers to one of
the main properties of chaos, the statistical relaxation
to some steady state.
The relaxation time is given by the following general estimate
\cite{CasatiChirikov,ChirikovEtAl}:
\be \label{eq:tR}
t_R\,\sim\,\frac{Q} {\omega}\,\sim\,\rho_0\,\leq\,\rho_H.
\ee
The quantity $Q$ stands for some appropriate quantum parameter,
which is large in the semiclassical region,
e.g., the total number of states for a bounded quantum motion:
$Q\sim\Gamma /(2\pi )^F$, where $\Gamma$ is the volume of the
phase space and $F$ is the number of degrees of freedom.
The parameters $\omega$ is a characteristic frequency of the
motion, while the meaning of $\rho_0$ and $\rho_H$ will be explained
below. (In what follows we always assume that Planck's constant
is equal to one.)
The physical meaning of the relaxation time $t_R$ originates directly
from the uncertainty principle ($\Delta t \cdot\Delta E\,\sim\,1$),
as implemented in equation (\ref{eq:tR}).
One sees that $t_R$ is bounded by the {\it Heisenberg time\/} $\rho_H$,
which is the {\it full\/} average density of energy levels.
For $t\lsim t_R$, the discrete spectrum is not resolved, and the
statistical relaxation follows the classical (limiting) behaviour.
This is precisely the regime (which is unaccounted for in ergodic theory)
where quantum pseudochaos manifests itself.
A more accurate estimate of $t_R$ can be obtained by considering
the average density $\rho_0$ restricted to the so-called
{\it operative eigenstates,} that is, those which are actually
present in a particular quantum state $\psi$, and which control its dynamics.
It is mathematical expedient to consider in place of
finite-time relations (of true physical significance), the
following {\it conditional limit\/}:
\be \label{eq:ConditionalLimitI}
t,\,Q\,\to\,\infty\,, \hskip 50pt \tau_R\,=\,\frac{t}{t_R(Q)}\,=\,const
\ee
where $\tau_R$ is a new dimensionless time.
The {\it double limit\/} (\ref{eq:ConditionalLimitI}) (unlike the
single limit $Q\to\infty$) is {\it not\/} the limit of classical
mechanics which, in this representation, holds true for
$\tau_R\lsim 1$ and with respect to the statistical relaxation only.
For $\tau_R\gsim 1$, the behaviour remains essentially quantum
even in the limit $Q\to\infty$, and it is called {\it mesoscopic}.
Specifically, the quantum steady state is generally quite different from
the classical statistical equilibrium, in that the former may be
{\it localized} (under certain conditions), that is, {\it nonergodic\/}
in spite of classical ergodicity.
Another important difference is found in the {\it fluctuations,} which are
also a characteristic property of chaotic behaviour.
By comparison with classical mechanics, the quantum $\psi (t)$ plays,
in this respect, an intermediate role between the classical
trajectory with large relative fluctuations, and the
coarse-grained classical phase-space density with no fluctuations
at all. Unlike either, the fluctuations of $\psi (t)$
(or rather, those of averages in a quantum state $\psi (t)$)
are typically of order $d_H^{-1/2}$, where $d_H\lsim Q$
---the {\it Hilbert dimension} of the state $\psi$--- is the
number of operative eigenstates associated with the quantum state $\psi$.
In other words, the chaotic wavefunction represents statistically
a {\it finite ensemble} of approximately $d_H$ statistically
independent systems, even though formally $\psi (t)$ describes
a {\it single} system in a pure state.
The relaxation time scale $t_R$ should not be confused with the
{\it Poincare recurrence time} $t_P$, which is typically much longer,
and which sharply increases when the size of the recurrence domain
decreases.
The time scale $t_P$ characterizes large fluctuations for both the
classical trajectory and the quantum $\psi$ (but not for the phase density),
of which recurrence is a particular case.
By contrast, $t_R$ characterizes the average relaxation process.
Rare recurrences (the larger the quantum parameter $Q$, the rarer),
make quantum relaxation similar to the classical non-recurrent one.
Statistical properties which are stronger than relaxation and fluctuations
are related to the local exponential instability of motion.
The importance of these stronger properties for statistical
mechanics is not completely clear. Nevertheless, in accordance
with the correspondence principle, those properties are present
in quantum chaos as well, but on a {\it much shorter random
time scale} $t_r$:
\be \label{eq:tr}
\Lambda t_r\,\sim\,\ln{Q}
\,\sim\, \ln{(\omega t_R)}\,\ll t_R
\ee
Here $\Lambda$ is the classical Lyapunov exponent characterizing
the instability rate.
This random time scale was discovered and
partly explained in \cite{BermanZaslavsky}
(see also \cite{BerryEtAl,CasatiChirikov,ChirikovEtAl}).
According to the well-known Ehrenfest theorem, the motion of a narrow
wave packet follows an ensemble of classical trajectories as long as
the packet remains narrow, and hence it is as random as in the
classical limit.
Since the instability range is limited both from below (the minimal
size of the quantum packet ---the coherent state--- is of order unity,
due to the uncertainty principle) as well as from above (for bounded motions),
the time interval $t_r$ of quantum instability is logarithmically short,
in agreement with the estimate (\ref{eq:tr}).
Nonetheless, it grows indefinitely as $Q\to\infty$, and therefore
a temporary, finite-time quantum pseudochaos converges slowly
to the classical dynamical chaos.
Again, we may consider the conditional limit
associated to the random time scale $t_r$,
\be \label{eq:ConditionalLimitII}
t,\,Q\,\to\,\infty\,, \qquad \tau_r\,=\,\frac{t}{t_r(Q)}\,=\, const ,
\ee
which gives rise to the new scaled time $\tau_r$.
Note that the latter differs from the scaled time
$\tau_R$ of equation (\ref{eq:ConditionalLimitI}).
Specifically, if we fix the time $t$, then in the limit $Q\to\infty$
we obtain the transition to the classical instability in accordance
with the correspondence principle, while for $Q$ fixed, and
$t\to\infty$ we have the proper quantum time-evolution.
For example, the quantum Lyapunov exponent $ \Lambda_q$ is given
by \cite{AlickiEtAl,CasatiChirikov}
$$
\Lambda_q(\tau_r)\,\to\,\cases{
\Lambda & if $\tau_r\,\ll\, 1$\cr
0 & if $\tau_r\,\gg\,1.$\cr}
$$
In the semiclassical region ($Q\gg 1$), the time-scale $t_r$
is much shorter that the relaxation time $t_R$.
This leads to the surprising phenomenon that quantum diffusion
and relaxation are {\it dynamically stable,} contrary to the
classical behaviour.
Therefore, the instability of motion is in general not
important {\it during\/} statistical relaxation:
what is crucial for the statistical properties of quantum
motion, is the correlation decay, that takes place during the
short {\it initial\/} random time scale $t_r$,
The dynamical stability of quantum diffusion has been demonstrated
in striking numerical experiments involving time-reversal
\cite{MixedReferencesI}.
In a classical chaotic system, the initial state cannot be
recovered by reversing the time-evolution of a sufficiently
long orbit, because the unavoidable numerical errors (not
random!), are amplified by the local instability.
By contrast, under time-reversal, a quantum state will return
to the initial state to a very high accuracy, after which the
wave packet will begin to spread again.
%------------------------------------------------------------------
\section{Chaos and pseudochaos}
A much studied model for strongly chaotic motions is the so-called
{\it Arnold cat map}, a linear dynamical system on the two-dimensional
torus \cite{ETBooks,HannayBerry,PercivalVivaldi,%
BartuccelliVivaldi,Keating,FordEtAl,DegliEspostiIsola,Nonnenmacher,%
BehrendsFiedler}.
\be \label{eq:CatMap}
\begin{array}{ll}
{q}_{t+1}\,\equiv\,2\,q_t+{p}_t &({\rm mod}\ 1) \\
{p}_{t+1}\,\equiv\,q_t+p_t &({\rm mod}\ 1).
\end{array}
\ee
The system is exponentially unstable, with positive
Lyapunov exponent $\Lambda =\ln(\lambda)$, where
$\lambda=(3+\sqrt{5})/2$ is the largest eigenvalue of the mapping.
The spectrum of the motion is continuous, implying
the decay of correlations.
The canonical variables $q$ and $p$ are real numbers.
However, the {\it periodic orbits\/} of the cat map correspond
to points with {\it rational\/} coordinates $q=x/N,\ p=y/N$,
with $N,x,y$ integers, and $x$ and $y$ reduced modulo $N$.
Clearing the denominator $N$, one arrives at the
{\it discretized\/} Arnold cat map
\be \label{eq:DiscreteCatMap}
\begin{array}{ll}
{x}_{t+1}\,\equiv\,2\,x_t+{y}_t &({\rm mod}\ N)\\
{y}_{t+1}\,\equiv\,x_t+y_t &({\rm mod}\ N).
\end{array}
\ee
The phase space is now a $N\times N$ lattice on the torus:
the dynamical and statistical properties of the motion are
completely changed, and new mathematical tools
---mainly from algebraic and probabilistic number theory---
are required for their study
\cite{VivaldiIII,Keating,DegliEspostiIsola}.
The discrete cat map may describe {\it three\/} rather
different dynamical systems:
\begin{itemize}
\item{} A {\it quantum\/} system, where the classical trajectories
lose physical meaning, but are nonetheless used for the
calculation of the time-evolution of a quantum state.
Loosely speaking, the latter corresponds to an ensemble of
discrete orbits.
\item{} A restriction of the {\it classical\/} system
(\ref{eq:CatMap}) to a discrete subset of the continuous phase space.
Its orbits are periodic orbits of the continuous system
(\ref{eq:CatMap}).
\item{} A discrete dynamical system in its own right, important
for computational theories, where arithmetical phenomena
---both deterministic and probabilistic---
gain significance at the expenses of metric and topological considerations.
\end{itemize}
The motion's spectrum for the mapping (\ref{eq:DiscreteCatMap})
is not only discrete, but equidistant, which implies periodic
recurrences for all trajectories of the quantum state
\cite{HannayBerry,FordEtAl}.
Systems of this type are regular and can possess at most
the weakest statistical property, ergodicity.
For this reason there is growing consensus that the quantum
manifestations of chaos must differ from the classical ones.
This has led many to believe that `true' chaos can only exist
in classical mechanics
(the authors of \cite{KrugerTroubetzkoy}, however, take a different
view ---see section \ref{section:OrderingOfOrbits}).
The aforementioned position is unsatisfactory, in that
physics is quantal, and hence the only {\it true physical
chaos is quantum chaos}.
Since the latter is certainly rather different from the
former, quantum chaos was termed {\it pseudochaos}
(see, e.g., \cite{ChirikovI}) to emphasize the difference.
Besides quantum mechanics, examples of pseudochaos abound in
digital computers, which behave like {\it discrete\/} classical
dynamical systems (see, e.g., \cite{ChirikovI, ChirikovII}.
Their dynamical properties are extremely important, in view
of the enormous range of applications.
In particular, many studies of classical chaos have relied
crucially on computer experiments, where in fact pseudochaos
is all one normally observes (see section 3).
Therefore it seems to us that the debate over quantum
chaos should be broadened to include considerations
about pseudochaos in discrete systems, with particular
reference to computer representations of chaotic systems
with continuous cooordinates.
The computer is, in a sense, an `overquantized' system in
that any quantity is discrete, while in quantum mechanics
only the product of two conjugated variables has that property.
The large `quantum' parameter $Q$ is here given by the largest
representable integer $N$, whereas the short time scale
$t_r\sim\ln{N}$ (\ref{eq:tr}) is the number of computer
digits \cite{ChirikovEtAl}.
Owing to discreteness, any dynamical trajectory in a computer
becomes eventually periodic, a well-known phenomenon in the
theory and design of pseudorandom number generators, from
which the term pseudochaos was borrowed \cite{ChirikovI}.
(Precautions are necessary to exclude such computer artifacts
in numerical experiments, see, e.g.,
\cite{Karney,Scovel,EarnTremaine,Maddox,Palmore}).
The question of randomness in discrete systems may be
approached from an {\it algorithmic\/} angle, whereby one
attempts to quantify the computational effort necessary
to predict the value of dynamical observables, for instance
the points of an orbit.
The amount of computations is typically measured in terms of either
the {\it size} or the {\it running time} of an `efficient'
program which is capable of performing the required calculations.
One immediately identifies two extreme situations.
On one hand, the smallest of programs may still be as large as the
data it generates, which would render such computation as ineffective
as storing a result known beforehand and printing it.
On the other hand, the fastest of programs may still take as long
as the system being simulated, in which case the computation
would be as ineffective as observing the physical system
---itself an analog computer--- evolve.
In either case, we have a {\it terminal obstruction to predictability}.
The word {\it random\/} is routinely linked to incompressibility
of information: a sequence is termed random when the shortest
program that generates it has (essentially) the same size as
the sequence itself. Developing this idea is the main concern
of {\it algorithmic complexity theory,} whose application
to dynamical systems has legitimated the use of the locution
{\it deterministic randomness} in continuous
systems \cite{Kolmogorov,Chaitin,ZvonkinLevin,White}
(for a clear informal presentation, see \cite{FordEtAl}).
Unlike time-asymptotic ergodic theory, the algorithmic theory
does include (and indeed originally developed) the notion of
{\it finite-time randomness,} which is crucial for our
discussion (see section 1).
Particularly, in both (classical) chaos as well as
pseudochaos, an orbit can be algorithmically random.
The incompressibility of information, and the resulting obstruction
to predictability, are directly related (indeed equivalent) to
the {\it complete independence\/} of different sections of
a random symbolic orbit (section 4).
These sections of orbits are independent not only statistically,
but also algorithmically (dynamically), that is, they cannot be
calculated from one another by any finite procedure (algorithm).
Whilst the above meaning of randomness is quite established
theoretically, in practice one's inability to compute
is often related to excessive computational time,
or excessive storage requirements.
Besides numerical experiment with chaotic dynamical systems,
examples abound in cryptography, where finding
computationally intractable problems is the main task.
There one typically looks for problems that can only be solved
in {\it non-polynomial time\/} \cite{Koblitz}, which make them
unassailable (see section \ref{section:TimeComplexity}).
An example of storage problems is the computation of the
mysteriously unpredictable digits of a radical (e.g., $\sqrt{2}$).
Even though this can be done by small and fast programs (i.e.
Newton's method), during the computation such programs
{\it become\/} as large as the output, due to the necessity
of storing all intermediate data \cite{Shaw}.
(Note that in a theoretical setting the latter problem does not
occur, since Turing machines feature {\it infinite\/}
storage capacity.)
An important observation is that complex phenomena, which are
best described in {\it probabilistic\/} terms, routinely emerge
alongside any of the computational difficulties mentioned above.
In the rest of the paper, we shall articulate some of these issues,
in the context of quantum and discrete dynamics, using the
discrete cat map (\ref{eq:DiscreteCatMap}) for exemplification.
Conforming to current usage, we shall reserve the word `chaos'
to denote the kind of asymptotic obstruction to computability
in dynamical systems that derives from excessive program size, while
the term (algorithmically) `random' may describe both chaos and pseudochaos.
%------------------------------------------------------------------
\section{Time complexity and period functions} \label{section:TimeComplexity}
The importance of time complexity in discrete dynamics originates
from the proximity of the latter to number theory and computer science.
In this section we discuss some obstructions to computability
that emerge in irregular discrete dynamical systems such as
(\ref{eq:DiscreteCatMap}) and (\ref{eq:BernoulliShift}).
These problems stem from algorithms with excessive (non-polynomial)
running time.
We note that the two-dimensional mapping
(\ref{eq:DiscreteCatMap}) can be rewritten as the single congruence
\cite{PercivalVivaldi}
\be\label{eq:AlgebraicCatMap}
\zeta_{t+1}\equiv \lambda\,\zeta_t \mod{N}
\ee
where both $\lambda > 1$ (the largest eigenvalue of (\ref{eq:DiscreteCatMap}))
and $\zeta=(\lambda-1)x+y$ are {\it algebraic integers}
\footnote{An algebraic integer is a root of an irreducible polynomial
with integers coefficients and first coefficient equal to 1.}
(transforming (\ref{eq:DiscreteCatMap}) into (\ref{eq:AlgebraicCatMap})
is akin to writing a two-dimensional map in complex coordinates).
Equation (\ref{eq:AlgebraicCatMap}) is structurally identical to
\be \label{eq:BernoulliShift}
x_{t+1}\equiv b\,x_t\mod{N}
\ee
where now $b>1$ and $x$ are ordinary integers. This analogy is
strong when $N$ is coprime to $b$, in which case
(\ref{eq:BernoulliShift}) is {\it invertible}.
The mapping (\ref{eq:BernoulliShift}) ---the discrete version
of the so-called Bernoulli shift \cite{Moser}--- forms the basis
for an important class of pseudo-random
number generators (\cite{Knuth}, volume 2).
In addition, it is a source of the {\it discrete logarithm problem},
a computationally intractable problem which finds widespread
use in cryptography \cite{Koblitz}.
The discrete logarithm has a simple dynamical interpretation:
it is the time required to reach a given point $x$ in an orbit,
starting from the initial condition $x_0$.
By choosing $x_0=1$ in (\ref{eq:BernoulliShift}), one sees that
$x\equiv b^t\mod{N}$, which implies that $t$ is the `logarithm'
of $x \mod{N}$ to the base $b$.
By the same token, the discrete logarithm is also closely
related to the {\it Poincare' recurrence times} in
these systems (sections \ref{section:Introduction} and
\ref{section:QuantumPseudochaos}).
The running time $T$ of the fastest algorithms known to date
is {\it non-polynomial\/} in the input size $\log(N)$
\be\label{eq:NonPolynomialTime}
T\,=\,\exp\bigg(\root 3 \of {\log(N)}+c\bigg).
\ee
Here $c$ is a constant, and the base $b$ and size $N$ are
chosen in such a way that the orbit length be of order
$N$ (see below).
The closer the run time is to a pure exponential (which in
(\ref{eq:NonPolynomialTime}) would imply $T=O(N)$), the closer
is the problem to be solvable only with the `wait-and-see'
algorithm, which amounts to {\it null\/} predictive power.
Note that in the computation of the discrete logarithm
there are no difficulties as to program {\it size}.
For this reason, the distinction between polynomial and
non-polynomial time is the criterion used in computer science
to discriminate between tractable and intractable problems.
The cryptographical significance of the discrete logarithm
lies in the fact that it is a {\it trapdoor function}:
encryption (the exponential, i.e., computing a point in the orbit) can
be performed in polynomial-time, while decryption
(the logarithm, i.e., computing the recurrence time) cannot.
Among the most complex objects found in discrete dynamics
are the {\it period functions\/} $P=P(N)$, which characterize
the maximal (or average) period of the orbits, as a
function of the system size $N$
\cite{Rannou,Kaneko,Keating,BeckRoepstorff,Vivaldi}.
They play an important role in quantum chaos as well
(see section \ref{section:DiscretePseudochaos}).
As a rule, period functions feature very large fluctuations,
which in modular systems such as (\ref{eq:DiscreteCatMap}) or
(\ref{eq:BernoulliShift}) have a crisp arithmetical significance.
For instance, in the case (\ref{eq:BernoulliShift}),
$P(N)$ is the period of the digits of the rational
number $x_0/N$, expressed in base $b$, a problem first
considered by Gauss (\cite{Gauss}, section VI).
One has the bounds
$$
\lfloor \log(N+1)\rfloor \leq P(N) \leq N-1
$$
where $\lfloor x\rfloor$ is the floor function
(the largest integer not exceeding $x$), and the maximum is
attainable (not necessarily attained!) only if $N$ is prime,
and provided that $b$ is not a square.
In the latter case one has a {\it space-filling orbit,}
reaching every point apart from zero.
For the cat map, the corresponding bound is \cite{BehrendsFiedler}
$$
\lfloor \log(\lambda)\rfloor +1 \leq P(N) \leq 3N.
$$
The maximal period is now $O(N)$, rather than $O(N^2)$, so
that space-filling orbits cannot exist: this is an arithmetical
consequence of area-preservation \cite{PercivalVivaldi}.
(However, one can still construct linear dynamical systems of the
cat map type, which are invertible on a toral lattice even if
their determinant is not unity, and which have a space-filling
orbit \cite{VivaldiII}).
The fluctuations of $P(N)$ call for averaging.
However, rigorous studies of such averages are notoriously
difficult, related as they are to a class of number-theoretic
problems, centered around the so-called {\it Artin's conjecture}
\cite{RamMurty}.
Various heuristic estimates are known, but the `actual'
asymptotic formula for the average order of $P$
\be \label{eq:AverageP}
\langle P\rangle (N)={1\over N}\,
\sum_{n=1}^N\,P(n) \sim {N\over \log(N)^{(1+O(1))\log\log\log(N)}}
\ee
can only be proved assuming the validity of the so-called
generalized Riemann hypothesis (see \cite{KrugerTroubetzkoy},
and references therein).
The wide gap existing between what is believed to be true and
what can actually be proved, underlines the difficulties in
developing an ergodic theory of discrete chaotic systems.
By contrast, the ergodic theory of the continuous version of
(\ref{eq:BernoulliShift}) is much simpler.
Unsurprisingly, the computation of the period-function of the
maps (\ref{eq:DiscreteCatMap}) and (\ref{eq:BernoulliShift}),
turns out to be {\it non-polynomial}, for it requires
performing the prime decomposition of $N$.
The run time for factorization algorithms is similar to
that of the discrete logarithm.
For this reason, factorization ---the inverse of
multiplication--- is another well-known trapdoor
function \cite{Cohen}.
The link between non-polynomial time problems, and probabilistic
phenomena in discrete dynamical systems is largely unexplored.
For the cat map, the discrete logarithm is associated to two
types of fluctuations, namely those of Poincare' recurrence times
mentioned above (see also section \ref{section:QuantumPseudochaos}),
and spectral fluctuations \cite{BartuccelliVivaldi}.
Within this context, of note is a recent result
\cite{Vladimirov} establishing a central limit theorem for
the propagation of {\it round-off errors\/} in uniform spatial
discretization of planar rotations (harmonic oscillator).
No polynomial-time algorithm has been found for the
corresponding period function, which features wild
fluctuations (\cite{Vivaldi}, see also \cite{LowensteinVivaldi}).
%------------------------------------------------------------------
\section{Discrete pseudochaos} \label{section:DiscretePseudochaos}
In this section we review the main construction of the algorithmic
theory of continuous dynamical systems, and then characterize the
extent to which the asymptotic chaos found in continuous dynamics is
suppressed in discrete dynamics.
The context is that of a discrete dynamical systems with $N$ states,
where the period function $P(N)$ introduced in section
\ref{section:TimeComplexity} plays a key role.
An alternative approach developed in \cite{KrugerEtAl,KrugerTroubetzkoy}
will be discussed in section \ref{section:OrderingOfOrbits}.
The origin of the algorithmic theory of dynamical systems can be
traced to the introduction of the notion of {\it symbolic trajectory,}
due to Hadamard \cite{Hadamard}.
We start from a partition of the phase space into $M$
cells, each labelled by an integer $m$.
We then consider an orbit $x=x_t$ in correspondence to
some discrete instants of time, again labelled by the
integers. At the time $t$, we record the label $m_t$ of
the cell to which the orbit belongs, thereby constructing
an infinite sequence of symbols
\be \label{eq:sigma}
\sigma\,=\,\sigma(x_0)\,=\,(m_{0},m_{1},...,m_{t},...).
\ee
(In an invertible system, $\sigma$ can be made doubly-infinite.)
Such symbolic trajectory is a {\it coarse-grained} representation
of the original trajectory, obtained by projecting the latter
onto a finite set.
Representing orbits as strings of symbols opened the possibility
of applying the notion of algorithmic complexity to the study of
motions (see \cite{AlekseevYakobson}, and \cite{ChirikovII},
for an informal introduction).
Following Kolmogorov \cite{Kolmogorov}, one introduces the
{\it complexity\/} $C(t,x_0)$ of the $t$-string corresponding
to $x_0$, as the length of the shortest algorithm that computes
such symbolic string.
The quantity $C$ is determined up to a machine-dependent additive
constant.
One then considers the limit
\be \label{eq:KolmogorovComplexity}
K(x_0)\,=\,\lim_{t\to\infty} \frac{C(x_0,t)}{t},
\ee
and the sequence $\sigma(x_0)$ is defined to be {\it asymptotically random\/}
(or chaotic) if such limit exists and is positive
\cite{ZvonkinLevin,AlekseevYakobson}.
Some strongly chaotic dynamical systems, when represented
symbolically with respect to a suitable partition, have the
remarkable property that the set of symbolic trajectories is
{\it complete,} that is, it contains all possible sequences
(\ref{eq:sigma}). From this it is possible to deduce that most
symbolic orbits are random \cite{Kolmogorov,ZvonkinLevin}.
Ergodic and algorithmic theories have a limited but significant overlap,
based on a prominent result linking exponential instability of
motion with randomness: the Alekseev-Brudno
theorem \cite{AlekseevYakobson,Brudno,White}.
For almost all initial conditions $x_0$ (with respect to some
invariant measure $\mu$),
we have (cf.~(\ref{eq:KolmogorovComplexity}))
\be \label{eq:AlekseevBrudnoTheorem}
K(x_0)\,=\,h_\mu
\ee
where
\be\label{eq:MetricEntropy}
h_\mu\,=\,\sum_{\Lambda_i>0}\,\Lambda_i
\ee
is called the {\it metric entropy,} which has the dimension
of a frequency and which characterizes the rate of exponential
instability of motion.
The summands in (\ref{eq:MetricEntropy}) are the positive Lyapunov
exponents. In a two-dimensional map like (\ref{eq:CatMap}), the
above sum contains only one term and one finds that $h_\mu=\Lambda$.
The remarkable relation (\ref{eq:AlekseevBrudnoTheorem})
links explicitly an algorithmic concept (left-hand side)
to a probabilistic one (right-hand side).
The positiveness of the entropy is then taken as a {\it definition\/}
of dynamical asymptotic randomness, thereby justifying the informal
inference of that from ergodic theory.
The limit (\ref{eq:AlekseevBrudnoTheorem}) says that in order
to calculate each successive segment of a symbolic trajectory,
one needs new information on the initial conditions of the orbit,
at a rate determined by the entropy.
Consequently, regardless of how much knowledge one has on the
coarse-grained past history of the motion, its future evolution
($t>0$) still remains unpredictable. Of course, this is true for a
symbolic trajectory only, as on the `exact' orbit it is sufficient
to fix a single point.
The remnants of determinism still persist in the symbolic trajectories,
in the form of some dynamical correlations which take place within
a short {\it dynamical time scale} $t_d$, which is
determined by the {\it randomness parameter} \cite{ChirikovIII}
\be \label{eq:R}
R\,=\,\frac{|t|}{t_d}\,\sim\,\frac{h\,|t|}{\ln{M}}.
\ee
This allows us to follow in time the building up of asymptotic
randomness, and to make some estimates for a finite time (see below).
In particular, we have {\it temporary determinism\/} over the time scale
$|t|\lsim t_d$ where strong dynamical correlations persist
in a symbolic code, so that information about the future evolution
of an orbit can be inferred from the result of finite-accuracy
observations of an orbit segment.
On this relatively short time scale the trajectory can hardly be termed random.
On the other hand, for $|t|\gg t_d$ almost all symbolic orbits become random,
and only a statistical description is possible.
Even though, in principle, the equations of motion can still be used
to derive all statistical properties without any {\it ad hoc\/} hypotheses,
the exact trajectory becomes an elusive entity, which can only be observed,
yet neither predicted nor reproduced in any way.
The estimate (\ref{eq:R}) may be justified as follows.
For a given partition $M$, the complexity of an individual point of
a symbolic trajectory is $C_1\sim\ln{M}$ (the number of digits
needed to specify an element of the partition).
Since successive points within the interval $\sim t_d$ are
essentially correlated, the average complexity per iteration of
the map is reduced to $\langle C_1\rangle\sim C_1/t_d\sim h$.
Hence, $t_d\sim\ln{M}/h$, in accordance with (\ref{eq:R}).
The definition of randomness as given in (\ref{eq:AlekseevBrudnoTheorem})
is somewhat weaker than the original algorithmic definition
\cite{Kolmogorov,ZvonkinLevin}, as the former allows for some dynamical
correlations over the time scale $t_d$.
This is inevitable for a continuous time system.
For a map, both definitions coincide if $t_d<1$ ($\ln{M}\lsim h$), or
if a very special partition is used \cite{ETBooks}.
The situation is altogether different for {\it discrete\/} dynamical systems.
If the size $N$ of the systems is finite, all orbits are (eventually)
periodic, and the problem is to estimate the complexity of a typical
orbit, for times $t$ not exceeding its period.
Note that, for fixed $N$, the question of asymptotic (long time)
randomness has a trivially negative answer here, since every orbit
will repeat itself, leading to a logarithmic growth of $C(t)$.
Thus, in such a system only pseudochaos is possible, at most.
As in the continuum, each orbit is still determined by its
initial point $x_0$, but specifying the latter requires no
more than $\log(N)$ bits of information, whence
\be \label{eq:DiscreteComplexity}
C(x_0,t,N) =O(\ln{N}) \hskip 30pt \hbox{\rm for} \hskip 30pt
0 \leq t < P(x_0,N)
\ee
where $P(x_0,N)$ is the period of the orbit through $x_0$.
With reference to the limiting procedure (\ref{eq:KolmogorovComplexity})
and the estimate (\ref{eq:DiscreteComplexity}), one sees that
in the present class of systems the question of randomness is intimately
related to the asymptotic growth rate of the period function $P(N)$,
to be averaged over a set of initial conditions whose density approach
unity. In particular, if the orbits have a sufficiently long period,
that is, if $P(N)$ admits a lower bound which grows faster than
the logarithm of $N$ for `typical' values of $N$ (that is, possibly
excluding a set of zero density), then one would conclude that
the discrete motions are `non-random', in the sense that the share of
random motion is negligible, i.e., logarithmic in the period
of the orbit.
This is indeed the case for systems such as (\ref{eq:DiscreteCatMap})
or (\ref{eq:BernoulliShift}), as long as one accepts
the conjectured asymptotic estimate (\ref{eq:AverageP}).
However, from a rigorous viewpoint, the question of the lack of
randomness of these discrete orbits ---as plausible as it is---
still remains unsettled (cf.~last section in \cite{KrugerTroubetzkoy}).
It seems though that proving lack of randomness (i.e., finding a
super-logarithmic lower bound for $P(N)$) should be considerably
easier than proving an asymptotic formula for the complexity, which
may well require the full force of Riemann hypothesis!
%------------------------------------------------------------------
\section{Quantum pseudochaos} \label{section:QuantumPseudochaos}
As to the quantum version of the mapping (\ref{eq:DiscreteCatMap}),
there is little to add to the analysis of the classical version
presented in section \ref{section:DiscretePseudochaos}.
The time-evolution of a quantum state (in the Wigner representation
$W(x,p,t)$) is {\it exactly} the same as the classical one \cite{FordEtAl}.
This remarkable peculiarity of a linear quantum map greatly
simplifies the studies of the quantum dynamics and chaos.
The price is the non-generic global periodicity, whence the difficult
problem of the associated period function $P(N)$ (see section
\ref{section:TimeComplexity}).
The main {\it physical\/} distinction of the quantum cat map lies
in the strict restrictions on the quantum state $W$ itself,
particularly on the initial conditions of quantum motion.
Formally, one can interpret the {\it quasiprobability\/} $W$ as
an ensemble of `trajectories' which is the analog of the classical
phase-space density, apart from possible negative values of $W$.
In this picture, each quantum `trajectory' represents a
{\it nonseparable part\/} of the quantum state, with a specific
$W$-value, which, nevertheless, follows exactly the classical trajectory!
The number $N_W$ of such elements of the ensemble of trajectories must
be sufficiently large: $N_W\gsim N$, with the lower bound corresponding to the most
localized quantum wave packet, a coherent state.
Specifically, the total number of quantum states is $Q=N$, to be
compared with the $N^2$ classical states (initial conditions),
each of which is physically distinct from all others.
The number of different (periodic) trajectories is much less, being
$\sim N^2/\langle P\rangle$, where $\langle P\rangle$
is given by (\ref{eq:AverageP}).
On the other hand, in the quantum case the initial state is
characterized not only by the initial conditions of the corresponding
`trajectories', but also by different values of $W$ on those.
Again, this is similar to the classical description in terms of
the phase-space density.
Besides these quantitative restrictions of the quantum state,
there is an additional restriction concerning the shape of the
function $W(x,p)$.
In particular, it is still unknown whether functions $W$ which are
non-negative can exist in the discrete cat map model.
With all the above allowances, the quantum dynamics of the cat map
is the same as the discrete classical one, and so all the estimates
in section \ref{section:DiscretePseudochaos} remain unchanged.
In regard to the specific problem of the motion period in both cases,
what is important from our perspective is that no matter how short is
the random time scale (\ref{eq:tr}), the latter does grow indefinitely with $N$,
thus providing the correspondence principle which is of fundamental
importance in the quantum case, and which is crucial for numerical
experiments on computer.
We finally stress that the study of globally periodic systems,
natural as for discrete representations of classical systems,
remains a degenerate case in the quantum problem.
In general, the quantum motion is almost periodic, and it is
characterized by quasiperiods or Poincare recurrences.
The latter are extremely long, and are related to very large,
and rare fluctuations. The regular statistical processes are
characterized by the relaxation time scale, whose dependence
on $N$ is given by the estimate (\ref{eq:tR}).
%-----------------------------------------------------------------------
\section{Ordering of orbits} \label{section:OrderingOfOrbits}
This final section is devoted to a discussion of the controversy
between references \cite{FordEtAl} and \cite{KrugerTroubetzkoy},
with the former disproving and the latter proving the random
character of the quantum cat map.
The authors of \cite{KrugerTroubetzkoy} observe that the
complexity analysis of periodic orbits depends crucially on
the {\it ordering\/} with which the orbits are considered.
The concern for ordering originates in ergodic theory,
where one typically computes averages with respect to some
invariant measure. The periodic orbits constitute a natural
discrete sample which may converge ---in the sense of
probability theory--- to a measure.
Not only different orderings may correspond to different
measures, but crucially, orderings corresponding to the same
measure may nonetheless give different readings when it comes
to complexity.
In \cite{FordEtAl} the orbits are ordered according to the
system size $N$, which is just the denominator of the
rational points supporting the periodic orbits.
In \cite{KrugerTroubetzkoy} instead, the orbits are
ordered according to their increasing minimal period $P$,
and then lexicographically within the same period.
Both orderings correspond to the Lebesgue measure.
The central question is to establish which portion, if any,
of a `typical' periodic trajectory is algorithmically random.
As discussed in section \ref{section:DiscretePseudochaos}, the
ordering by system size yield (essentially) a logarithmic
compressibility of information, whence lack of randomness, as long
as one accepts the validity of the estimate (\ref{eq:AverageP}).
That the ordering by period leads to randomness can be seen
from the following considerations.
To find the periodic points $x_0$ of period $P$, one solves the
(continuous version of) congruence (\ref{eq:BernoulliShift}) for
$x_0$, for fixed $P$.
One finds $x_{P}\equiv x_0\equiv b^P\,x_0\mod{1}$, whence
\be\label{eq:xZero}
x_0\,=\,{m\over b^P-1}
\ee
where $m$ is an integer in the range $0\leq m\ < b^P-1$.
When $m$ is coprime to $b^P-1$, the fraction on the right-hand side
of (\ref{eq:xZero}) is reduced, whence $N(P)=b^P-1$ is exponential
in $P$, so that such point of period $P$ requires $O(P)$ bits of
information to be specified.
The set of reduced fractions of the form (\ref{eq:xZero}) has positive
density and is uniformly distributed \cite{HardyWright}, and so
its typical member is random.
Consequently, the non-repeating part of a typical periodic orbit of
period $P$ is also random.
On the other hand, when $m$ and $b^P-1$ are not coprime, cancellation
will occur in the fraction representing $x_0$. Such values of $m$
correspond to periodic orbits of period $P$ that live on much smaller
lattices, which carry most of the weight when enumerated
by system size.
The choice between the two orderings depends on the physical system
under consideration.
In \cite{KrugerTroubetzkoy}, the {\it classical} version of the
model (\ref{eq:CatMap}) was considered, whose analysis was based
on the properties of individual trajectories.
In this case, the ordering by period emerges from ergodic-theoretic
considerations (even though enumeration by system size seems to
us preferable from the physical point of view
---see section {\ref{section:TimeComplexity}).
In quantum mechanics instead, the ordering by system
size $N$ adopted by \cite{FordEtAl} is plainly unavoidable, being
inextricably linked to the nonseparable quantum `trajectories' (section 5),
and to the semiclassical limit $N\to\infty$.
The ordering by period would instead correspond to an artificial
collection of distinct systems, each characterized by a specific value
of the parameter $N$, and united solely by the existence in each of
them of some trajectories with a given period $P$.
We see no physical meaning in such arrangement of quantum `orbits'.
It seems to us that the authors of \cite{KrugerTroubetzkoy}, apparently
unaware of the quantum chaos debate, have applied to a quantum problem
a machinery which is as impeccable mathematically as it is inappropriate
physically, and after deducing with it that the quantum model (\ref{eq:CatMap})
is chaotic, have accused the authors of \cite{FordEtAl,FordIlg} of
`misinterpretations'.
We instead believe that the misinterpretation lies with
\cite{KrugerTroubetzkoy}, and that their criticism of
\cite{FordEtAl,FordIlg} is simply irrelevant to
the question addressed by J.~Ford and coworkers.
\bigskip\noindent {\sl Acknowledgements.}
We are indebted to D.~K.~Arrowsmith and G.~Mantica for useful discussions.
\newpage
\begin{thebibliography}{99}
\bibitem{ConferenceProceedings}
G. Casati, Ed.,
{\sl Chaotic Behavior in Quantum Systems,}
Plenum,
(1985);
T. Seligman and H. Nishioka, Eds.,
{\sl Quantum Chaos and Statistical Nuclear Physics,}
Springer,
(1986);
E. Pike and S. Sarkar, Eds.,
{\sl Quantum Measurement and Chaos,}
Plenum,
(1987);
M. Giannoni, A. Voros and J. Zinn-Justin, Eds.,
{\sl Chaos and Quantum Physics,}
North-Holland,
(1991).
H. Cerdeira, R. Ramaswamy, M. Gutzwiller and G. Casati, Eds.,
{\sl Quantum Chaos,}
World Scientific,
(1991);
P. Cvitanovi\'c, I. Percival and A. Wirzba, Eds., {\sl Quantum Chaos --
Quantum Measurement,}
Kluwer,
(1992);
D. Heiss, Ed., {\sl Chaos and Quantum Chaos,}
Springer,
(1992);
G. Casati, I. Guarneri and U. Smilansky, Eds.,
{\sl Quantum Chaos,}
North-Holland,
(1993);
G. Casati and H. Cerdeira, Eds.,
{\sl Chaos in Mesoscopic Systems,}
World Scientific,
(1995).
\bibitem{ETBooks}
V.I. Arnold and A. Avez,
{\sl Ergodic Problems of Classical Mechanics,}
Benjamin,
(1968);
I. Kornfeld, S. Fomin and Ya. Sinai,
{\sl Ergodic Theory, }
Springer,
(1982);
A. Katok and B. Hasselblatt,
{\sl Introduction to the Modern Theory of Dynamical Systems, }
Cambridge Univ. Press,
(1995).
\bibitem{MixedReferencesI}
D.L. Shepelyansky,
{\sl Physica D }
{\bf 8},
208
(1983);
G. Casati, B.V. Chirikov, I. Guarneri and D.L. Shepelyansky,
{\sl Phys. Rev. Lett. }
{\bf 56},
2437
(1986);
T. Dittrich and R. Graham,
{\sl Ann.Phys. }
{\bf 200},
363
(1990).
\bibitem{MixedReferencesII}
G. Casati, B.V. Chirikov, I. Guarneri and D.L. Shepelyansky,
{Phys.~Reports}
{\bf 154},
77
(1987);
G. Casati, I.Guarneri and D.L.Shepelyansky,
{\sl IEEE J. of Quantum Electr.}
{\bf 24},
1420
(1988).
%\bibitem{TodaIkeda}
% M. Toda and K. Ikeda,
% {\sl Phys. Lett. A }
% {\bf 124},
% 165
% (1987);
% A. Bishop et al,
% {\sl Phys. Rev. B }
% {\bf 39},
% 12423
% (1989).
\bibitem{AlekseevYakobson}
V.M. Alekseev and M.V. Yakobson,
% Symbolic dynamics and hyperbolic dynamical systems,
{\sl Phys. Reports}
{\bf 75}
287 %--325
(1981).
\bibitem{AlickiEtAl}
R. Alicki, D. Makowiec and W. Miklaszewski,
{\sl Phys.~Rev.~Lett.}
{\bf 77},
838
(1996).
%\bibitem{ArtusoEtAl}
% R. Artuso, E. Aurell, and P. Cvitanovi\'c,
% Recycling strange sets: I. Cycle expansions
% {\sl Nonlinearity}
% {\bf 3}
% (1990)
% 325 %--359,
% and
% Recycling strange sets: II. Applications
% {\sl Nonlinearity}
% {\bf 3}
% 361 %--386
% (1990).
\bibitem{BartuccelliVivaldi}
M. Bartuccelli and F. Vivaldi,
% Ideal orbits of toral automorphisms,
{\sl Physica D}
{\bf 39}
194 %--204
(1989).
\bibitem{BeckRoepstorff}
C. Beck and G. Roepstorff,
% Effects of phase space discretization on the long-time
% behavior of dynamical systems,
{\sl Physica D}
{\bf 25}
173 %--180
(1987).
\bibitem{BehrendsFiedler}
E. Behrens and B. Fiedler,
% Periods of discretized linear Anosov Maps
{\sl Ergodic Theory and Dynamical Systems,}
{\bf 18}
331 %--341,
(1998).
\bibitem{BermanZaslavsky}
G. P. Berman and G. M. Zaslavsky,
{\sl Physica A }
{\bf 91},
450
(1978).
\bibitem{BerryEtAl}
M. Berry, N. Balazs, M. Tabor and A. Voros,
{\sl Ann.Phys. }
{\bf 122},
26 (1979).
\bibitem{Brudno}
A. A. Brudno,
{\sl Trudy Mosk. Mat. Obschestva}
{\bf 44},
124
(1982).
\bibitem{CasatiChirikov}
G. Casati and B.V. Chirikov,
The Legacy of Chaos in Quantum Mechanics,
in: {\sl Quantum Chaos: Between Order and Disorder,}
Eds. G. Casati and B.V. Chirikov, Cambridge Univ. Press,
(1995), p.3;
{\sl Physica D}
{\bf 86},
220
(1995).
\bibitem{CasatiChirikovFordIzrailev}
G. Casati, B.V. Chirikov, J. Ford and F.M. Izrailev,
{\sl Lecture Notes in Physics }
{\bf 93},
334
(1979).
\bibitem{CasatiFordGuarneriVivaldi}
G. Casati, J. Ford, I. Guarneri and F. Vivaldi,
{\sl Phys.~Rev.~A}
{\bf 34},
1413
(1986).
\bibitem{Chaitin}
G. Chaitin,
{\sl Information, Randomness and Incompleteness},
World Scientific
(1987).
\bibitem{ChirikovI}
B.V. Chirikov,
{\it Pseudochaos in statistical physics},
Proc. Intern. Conference `Nonlinear Dynamics, Chaotic and
Complex Systems', Eds. E. Infeld, R. Zelazny and A. Galkowski,
Cambridge Univ. Press,
(1997),
p.149.
\bibitem{ChirikovII}
B.V. Chirikov,
% Linear and nonlinear dynamical chaos,
{\sl Open Systems \& Information Dynamics}
{\bf 4},
241
(1997).
\bibitem{ChirikovIII}
B.V. Chirikov,
in {\it Proc. 2d Intern. Seminar on Group Theory Methods in Physics},
Harwood, Vol. 1, p. 553
(1985).
\bibitem{ChirikovEtAl}
B.V. Chirikov, F.M. Izrailev and D.L. Shepelyansky,
{\sl Sov. Sci. Rev. C }
{\bf 2},
209
(1981);
{\sl Physica D }
{\bf 33},
77
(1988).
\bibitem{Cohen}
H. Cohen,
{\sl A course in computational algebraic number theory,}
Springer, New York
(1996).
\bibitem{DegliEspostiIsola}
M. Degli Esposti and S. Isola,
% Distribution of closed orbits for linear automorphisms of tori,
{\sl Nonlinearity}
{\bf 8}
827 %--842
(1995).
\bibitem{EarnTremaine}
D.J.D. Earn and S. Tremaine,
% Exact numerical studies of hamiltonian maps: iterating without roundoff errors,
{\sl Physica D}
{\bf 56}
1 %--22
(1992).
\bibitem{FordEtAl}
J.~Ford, G.~Mantica and G.~Ristow,
{\sl Physica D}
{\bf 50},
493
(1991).
\bibitem{FordIlg}
J.~Ford and M.~Ilg,
{\sl Phys. Rev. A}
{\bf 45},
6164
(1992).
\bibitem{Gauss}
C. F. Gauss,
{\sl Disquisitiones Arithmeticae,}
Leipzig (1801).
(English transl.
Yale, New Haven and London
(1966),
and
Springer, New York
(1986).)
\bibitem{Hadamard}
J. Hadamard,
{\sl J. Math. Pures et Appl.}
{\bf 4},
27
(1898).
\bibitem{HannayBerry}
J.~Hannay and M.~Berry,
{\sl Physica D }
{\bf 1},
267
(1980).
\bibitem{HardyWright}
G. H.
Hardy
and
E. M.
Wright,
{\sl An introduction to the theory of numbers,}
Oxford University Press
(1979) (fifth edition).
\bibitem{Izrailev}
F.M. Izrailev,
{\sl Phys. Reports }
{\bf 196},
299
(1990).
\bibitem{Kaneko}
K. Kaneko,
% Symplectic cellular automata,
{\sl Phys. Lett. A}
{\bf 129}
9 %--16
(1988).
\bibitem{Karney}
C. F. F. Karney,
% Long time correlations in the stochastic regime,
{\sl Physica D}
{\bf 8}
360 %--380
(1983).
\bibitem{Keating}
J. P. Keating,
% Asymptotic properties of the periodic orbits of the cat maps,
{\sl Nonlinearity}
{\bf 4}
277 %--308
(1991).
\bibitem{Knuth}
D. E. Knuth,
{\sl The art of computer programming},
Addison-Wesley, Reading, {Mass.}
(1981).
\bibitem{Koblitz}
N. Koblitz,
{\sl Algebraic aspects of cryptography,}
Springer, New York
(1988).
\bibitem{Kolmogorov}
A.N. Kolmogorov,
Problemy Peredachi Informazii
{\bf 1},
3
(1965).
\bibitem{KrugerEtAl}
T. Kr\"uger, P. Seibt and S. Troubetzkoy,
% Complexity and randomness in recursive discretizations of dynamical systems,
{\sl Random and Comput. Dynamics,}
{\bf 2}
1 %--21
(1994).
\bibitem{KrugerTroubetzkoy}
T. Kr\"uger and S. Troubetzkoy,
% Complexity, randomness, discretization: some remarks on a program of J.~Ford,
{\sl Physica D }
{\bf 105}
97 %--104
(1997).
\bibitem{LowensteinVivaldi}
J. H.
Lowenstein
and
F.
Vivaldi,
% Anomalous transport in a model of hamiltonian round-off errors,
{\sl Nonlinearity}
{\bf 11}
1321 %--1350
(1998).
\bibitem{Maddox}
J. Maddox,
{\sl Nature}
{\bf 372}, 403 (1994).
\bibitem{Moser}
J. K.
Moser,
{\sl Stable and random motions in dynamical systems},
Princeton University Press, Princeton
(1973).
\bibitem{Nonnenmacher}
S. Nonnenmacher,
% Crystal properties of eigenstates for quantum cat maps,
{\sl Nonlinearity}
{\bf 10}
1569 %--1589
(1997).
\bibitem{Palmore}
J. Palmore,
{\sl Chaos, Solitons and Fractals}
{\bf 5},
1397
(1995).
\bibitem{PercivalVivaldi}
I.C. Percival and F. Vivaldi,
% Arithmetical properties of strongly chaotic motions,
{\sl Physica D}
{\bf 25}
105 %--130
(1987).
\bibitem{RamMurty}
M. Ram Murty,
% Artin's conjecture for primitive roots,
{\sl Math.~Intelligencer}
{\bf 10}
59 %--67
(1988).
\bibitem{Rannou}
F. Rannou,
% Numerical studies of discrete plane area-preserving mappings,
{\sl Astron. Astrophys.}
{\bf 31}
289 %--301
(1974).
%\bibitem{Ruelle}
% D. Ruelle,
% {\sl Thermodinamic formalism,}
% Addison-Wesley, Reading, MA
% (1978).
\bibitem{Scovel}
C. Scovel,
% On symplectic lattice maps,
{\sl Phys. Lett. A,}
{\bf 159}
396 %--400
(1991).
\bibitem{Shaw}
R.~Shaw,
correspondence with Joseph Ford
(1993).
\bibitem{Sokolov}
V.V. Sokolov,
{\sl Teor.~Mat.~Fiz.}
{\bf 61},
128
(1984).
\bibitem{VivaldiIII}
F.
Vivaldi,
% Arithmetical theory of Anosov diffeomorphisms,
{\sl Proc. R. Soc. Lond. A}
{\bf 413}
97 %--107.
(1987)
\bibitem{VivaldiII}
F.~Vivaldi,
% Geometry of linear maps over finite fields,
{\sl Nonlinearity}
{\bf 5}
133 %--147
(1992).
\bibitem{Vivaldi}
F.~Vivaldi,
% Periodicity and transport from round-off errors,
{\sl Experimental Mathematics}
{\bf 3}
303 %--315
(1994).
\bibitem{Vladimirov}
I.
Vladimirov,
Discretization of dynamical systems,
preprint, Deakin University,
Geelong, Victoria.
(1996).
[I.Vladimirov@mailbox.uq.edu.au]
\bibitem{White}
H.~White,
{\sl Ergodic Theory and Dynamical Systems}
{\bf 13}, 807 (1993).
\bibitem{Zaslavsky}
G.M. Zaslavsky,
{\sl Phys. Reports}
{\bf 80},
157
(1981).
\bibitem{ZvonkinLevin}
A.K.~Zvonkin, L.A.~Levin,
{\sl Usp. Mat. Nauk}
{\bf 25}, \#6,
85
(1970).
\end{thebibliography}
\end{document}