Kamal Hammani

Brandon G Bale

Sonia Boscolo

Christophe Finot
email: christophe.finot@u-bourgogne.fr

New developments in the study of optical parabolic pulses in normally dispersive fibers

Keywords: nonlinear pulse shaping, Raman amplification, self-similarity, coherent supercontinuum

We report two recent studies dealing with the evolution of parabolic pulses in normally dispersive fibers. On the one hand, the nonlinear reshaping from a Gaussian intensity profile towards the asymptotic parabolic shape is experimentally investigated in a Raman amplifier. On the other hand, the significant impact of the fourth order dispersion on a passive propagation is theoretically discussed: we numerically demonstrate flat-top, coherent supercontinuum generation in an all-normal dispersion-flattened photonic crystal fiber. This shape is associated to a strong reshaping of the temporal profile what becomes triangular.

INTRODUCTION

Over the past decade there has been large interest in ultrafast optical fiber amplifiers operating in the normal dispersion regime because of the discovery that, high-energy pulses with a parabolic intensity profile and linear frequency chirp are the asymptotic solution to the system for arbitrary initial conditions [START_REF] Fermann | Self-similar propagation and amplification of parabolic pulses in optical fibers[END_REF]. These so-called "similariton" solutions propagate in a self-similar manner, holding certain relations (scaling) between pulse power, duration, and chirp parameter and can remarkably resist to the deleterious effects of optical wavebreaking, both in active and passive propagation [START_REF] Dudley | Self-similarity in ultrafast nonlinear optics[END_REF]. Therefore, several applications in the field of high energy pulse generation or high-speed optical telecommunications have benefited from those properties (see for example review [START_REF] Finot | Optical parabolic pulse generation and applications[END_REF]).

In this present work, we report two new studies that further explore the dynamics of those nonlinear structures. We first describe experimental results dealing with the transition from a low-energy Gaussian pulse to the asymptotic state. The nonlinear reshaping is clearly evidenced as well as the gain saturation of the amplifier. We then discuss the impact of fourth order dispersion and we numerically demonstrate flat-top, coherent supercontinuum generation in an all-normal dispersion-flattened photonic crystal fiber. This shape is associated to a strong reshaping of the temporal profile that becomes triangular.

TRANSITION DYNAMICS IN NORMALLY-DISPERSIVE OPTICAL FIBER AMPLIFIERS

Transition dynamics of the normally-dispersive fiber amplifiers has been the subject of a limited number of theoretical works but only one experimental set of data is currently available to confirm the different mechanisms: in 2005, Billet et al. have investigated the longitudinal evolution of a picosecond pulse in an erbium-doped fiber amplifier (EDFA) [START_REF] Dudley | Self-similarity in ultrafast nonlinear optics[END_REF] with special emphasis on the evolution of the wings of the pulse characteristic of the intermediate regime when plotted on a logarithmic scale [START_REF] Boscolo | Self-similar parabolic optical solitary waves[END_REF].

Here we experimentally analyze a Raman fiber amplifier operating at normal dispersion [START_REF] Finot | Influence of the pumping configuration on the generation of optical similaritons in optical fibers[END_REF] using initial lowenergy Gaussian pulses. The system under investigation is sketched in Fig. 1. The experimental set-up is based on commercially available telecommunication devices. A 10 GHz modelocked fiber laser delivers initial picosecond hyperbolic secant pulses that are then linearly shaped to obtain 6.8 ps Gaussian pulses (such a temporal duration has been chosen in order to clearly observe the transition at the output of the fiber). The repetition rate of the source is decreased down to 5 GHz in order to limit the depletion effects. The pulses are pre-amplified by an EDFA and an optical variable attenuator is used to vary the input power.

Figure 1. Experimental set-up.

The Raman amplifier is based on a 6.1-km long non-zero dispersion shifted fiber (NZ-DSF) having a dispersion coefficient D = -2.58 ps/km/nm and a nonlinear coefficient  = 1.7 W -1 .km -1 . The pump is a continuous wave delivered by a Raman fiber laser and a backward pumping scheme is favored to limit the deleterious transfer of the noise of pump to the signal [START_REF] Hammani | Optical rogue-wave fluctuations in fiber Raman amplifiers[END_REF]. A pumping power up to 2 W is used, which enables a gain in the small signal limit of 25 dB.

Experimental temporal intensity profiles are recorded for initial peak powers ranging from 2 to 650 mW and are summarized in Figure 2. Results plotted on a linear scale clearly exhibit the transition from a low power Gaussian pulse affected mainly by second order dispersion towards a parabolic self-similar pulse. As the peak power grows, the nonlinearity induces a phase change that is proportional to the difference between the intensity profile and a parabolic profile. This in turn reshapes the intensity towards a parabolic form. Such an evolution has been found in agreement with an approach based on the use of a self-similar ansatz and a standard amplitude-phase decomposition [START_REF] Boscolo | Self-similar parabolic optical solitary waves[END_REF] : reduced equations for the key pulse parameters (peak amplitude, pulse duration and chirp coefficient) along with a known hydrodynamic-type system of equations have been shown to accurately reproduce the experimental trends.

Figure 2. (a) Experimental results showing the temporal profile of output pulse for initial Gaussian pulses with varied initial peak powers. Circles represent a parabolic fit of the temporal intensity profile obtained for initial pulses having an initial peak power of 200 mW.. (b) Results for initial peak powers up to 650 mW. Experimental intensity profiles have been recorded using an ultrafast optical sampling oscilloscope (ps temporal resolution).

Results also demonstrate clearly the saturation of the amplifier for initial peak-powers above 200 mW (the limiting factor is not here the spectral gain bandwidth but the pump energy). The output peak power saturates and does not follow anymore the typical law of the self-similar pulses. The parabolic shape is maintained with a significant increase of the temporal duration, which is in qualitative agreement with previous theoretical predictions [START_REF] Zhang | Self-similar parabolic pulses in optical fiber amplifiers with gain dispersion and gain saturation[END_REF][START_REF] Bale | Strong spectral filtering for a mode-locked similariton fiber laser[END_REF]. Therefore, this result constitutes the first direct experimental observation of the effect of gain saturation. Let us however note that if a co-propagating pumping scheme would have been used, longitudinal evolution would have been also affected by additional temporal depletion of the pump [START_REF] Finot | Influence of the pumping configuration on the generation of optical similaritons in optical fibers[END_REF].

IMPACT OF FOURTH-ORDER DISPERSION ON PASSIVE PROPAGATION

The spectral dispersion profile of a fiber is known to be a critical parameter for the generation of broadband light sources. The broadest spectra are generated when pumping occurs in the anomalous dispersion regime of the fiber. However, this results in decreased spectral coherence and flatness, especially when picosecond pump pulses are used. Previous attempts have been made to overcome this drawback by using dispersion-flattened fibers continuously tapered from anomalous to normal dispersion. However, due to limited availability of such fiber tapers, there is a recent renewed interest to consider fibers with longitudinally constant dispersion profiles, where a sufficiently broad, stable and flat-top spectrum can still be achieved [START_REF] Heidt | Coherent octave spanning near-infrared and visible supercontinuum generation in allnormal dispersion photonic crystal fibers[END_REF][START_REF] Hooper | Coherent supercontinuum generation in photonic crystal fiber with all-normal group velocity dispersion[END_REF].

We propose here a new method for generating coherent and flat-top SC spectra which relies on the effect of fourth-order dispersion (FOD) on parabolically-shaped pulses in an all-normal dispersion (ANDi) -flattened PCF. We numerically demonstrate that compact and remarkably flat spectra can be achieved while a triangular temporal profile is formed.

For our numerical simulations we use an ANDi PCF with flattened dispersion characteristics around 1060 nm, similar to what has been demonstrated in [START_REF] Tse | Supercontinuum generation at 1.06 um in holey fibers with dispersion flattened profiles[END_REF] (Fig. 3a). The third-order dispersion, which can degrade the selfsimilar pulse propagation [START_REF] Bale | Impact of third order dispersion on the evolution of parabolic optical pulses[END_REF] is zero at the pump wavelength. Pulse propagation in the PCF is described by the standard nonlinear Schrödinger equation including the effects of second-order dispersion, FOD and Kerr nonlinearity. Linearly chirped parabolic pulses with pulse energy 12 nJ, full-width half-maximum 2.6 ps and chirp parameter 3.35 THz 2 generated in an ytterbium-doped fibre amplifier [START_REF] Fermann | Self-similar propagation and amplification of parabolic pulses in optical fibers[END_REF] were used as initial conditions for pulse propagation in the PCF. To examine the impact of FOD we compare the evolution obtained in the concave dispersion-profiled PCF to that occurring in an equivalent fiber with spectrally constant dispersion (β 4 =0). The temporal and spectral profiles after a propagation distance of 1.5 m are shown in Fig. 3(b-c). We can see that in the absence of FOD, the pulse evolves self-similarly maintaining its parabolic shape both in the time and frequency domains, while undergoing a continuous, nonlinearity-dominated temporal and spectral broadening (Fig. 4(a-c)) [START_REF] Finot | Beneficial impact of wave-breaking or coherent continuum formation in normally dispersive nonlinear fibers[END_REF]. These results are consistent with the well-known, intrinsic resistance of similaritons to the optical wave breaking phenomenon [START_REF] Fermann | Self-similar propagation and amplification of parabolic pulses in optical fibers[END_REF][START_REF] Finot | Optical parabolic pulse generation and applications[END_REF]. In the presence of FOD, significant temporal and spectral reshaping of the parabolic pulse occurs over short propagation distances. In the temporal domain, the wings of the pulse, where the outermost instantaneous frequencies are located (given the linear chirp), experience enhanced broadening due to the large local dispersion. This effect generates a triangular shape which is maintained over a non-negligible propagation distance. The use of the FOD effect in a normally dispersive nonlinear fiber thus provides a new, alternative passive method for generating triangular-shaped pulses with respect to that introduced in [START_REF] Boscolo | Passive nonlinear pulse shaping in normally dispersive fiber systems[END_REF].

In the spectral domain, the power after 1.5 m propagation has very rapidly falling edges and a ripple-free top over 50 THz (190 nm) span (Fig. 3(c)). However, this flat-top spectrum is only a transient state and for further propagation distance the spectral power evolves into an M-shape (Fig. 4(d)). This typical shape can be linked to the self-phase modulation induced by the triangular temporal intensity profile. In the presence of FOD, the spectral bandwidth stabilizes more rapidly, typically leading to narrower spectrums since the pulse experiences both enhanced temporal broadening peak power reduction.

CONCLUSIONS

In this report we have studied two issues dealing directly with the specific features of optical parabolic pulses evolving in normally dispersive fibers. On the one hand, we have focused on the transition from low-energy Gaussian pulses to parabolic pulses in a Raman amplifier. A detailed experimental study coupled with a theoretical analysis highlights the various stages of the nonlinear reshaping. Further, the impact of the energy saturation of the amplifier is also clearly shown. On the other hand, we have proposed a new method for generating coherent, ultra-flat SC spectra based on the effect of the FOD on picosecond parabolic seed pulses in an ANDi PCF. We have numerically shown that compact spectra with ripple-free top over approximately 190 nm wavelength range can be achieved, while triangular pulses are formed in the time domain. We have also checked that the use of initial parabolic pulses provides substantially better performance as compared to conventional Gaussian pulses. These two studies and other recent results dealing with improved spectral compression [START_REF] Andresen | Transform-limited spectral compression by self-phase modulation of amplitude shaped pulses with negative chirp[END_REF] demonstrate that even though optical parabolic pulses have been highlighted as soon as 2000, there are still some aspects of the nonlinear pulse shaping that are not fully explored and that many applications, such as optical pulse processing, may benefit from a better understanding.

Figure 3 .

 3 Figure 3. (a) Dispersion profile of the PCF considered. (b) Temporal and (c) spectral power after propagation distance of 1.5 m with (blue solid line) and without (grey solid line) FOD. Initial pulse is plotted with a dotted black line.

Figure 4 .

 4 Figure 4. Longitudinal temporal (a-b) and spectral (c-d) evolutions of a parabolic pulse without (a,c) and with (b,d) FOD.

ACKNOWLEDGEMENTS

The authors would like to acknowledge support from the Engineering and Physical Sciences Research Council (Grant No. EP/FO2956X/1), the British Council (Alliance Grant No. 10.002), the Region Bourgogne (PARI PHOTCOM), the Agence Nationale de la Recherche (ANR SOFICARS, ANR-07-RIB-013-03) and the Ministère des Affaires étrangères et européenne (Alliance grant 22836ZJ).


Mathieu Hoyrup
email: mathieu.hoyrup@loria.fr

Randomness and the ergodic decomposition

Keywords: computable analysis, Martin-Löf randomness, ergodic decomposition, Birkhoff's ergodic theorem

The interaction between algorithmic randomness and ergodic theory is a rich field of investigation. In this paper we study the particular case of the ergodic decomposition. We give several positive partial answers, leaving the general problem open. We shortly illustrate how the effectivity of the ergodic decomposition allows one to easily extend results from the ergodic case to the non-ergodic one (namely Poincaré recurrence theorem). We also show that in some cases the ergodic measures can be computed from the typical realizations of the process.

Introduction

The goal of the paper is to study the interaction between the theory of algorithmic randomness, started by Martin-Löf [9], and ergodic theory (i.e. restricting to shift-invariant measures). The first results in this direction were obtained by V'yugin [START_REF] V'yugin | Ergodic theorems for individual random sequences[END_REF], who proved that Birkhoff's ergodic theorem and a weak form of Shannon-McMillan-Breiman theorem hold for each Martin-Löf random sequence. Recently several improvements of the first result have been achieved [START_REF] Nandakumar | An effective ergodic theorem and some applications[END_REF]6,[START_REF] Bienvenu | Ergodic-type characterizations of algorithmic randomness[END_REF].

A classical result from ergodic theory, called the ergodic decomposition, states that given a stationary process, almost every realization is actually a typical realization of an ergodic process. The full process can be decomposed as the combination of a collection of ergodic processes. It is natural to ask the question whether every Martin-Löf random sequence (with respect to the stationary measure) statistically induces an ergodic measure, and if the sequence is Martin-Löf random with respect to it.

We give three orthogonal cases in which we can give a positive answer: (i) when the decomposition of the measure is computable, (ii) when the decomposition of the measure is supported on an effective compact class of ergodic measures, (iii) when the decomposition of the measure is finite. Observe that the three cases are mutually incomparable. We leave the general problem open.

As a side result, we give sufficient conditions to infer the statistics of the system from the observation; formally we give a sufficient condition on an ergodic measure to be computable relative to its random elements.

In Section 2 we give the necessary background on computability and randomness. In Section 3 we develop results about randomness and combinations of measures that will be applied in the sequel, but are of independent interest (outside ergodic theory). We start Section 4 with a reminder on the ergodic decomposition and then we present our results relating it to randomness.

Preliminaries

We assume familiarity with algorithmic randomness and computability theory.

All the results stated in this paper hold on effectively compact computable metric spaces X and for computable maps T : X → X (as defined in computable analysis, see [START_REF] Weihrauch | Computable Analysis[END_REF]), but for the sake of simplicity we formulate them only on the Cantor space X = {0, 1} N and for the shift transformation T : X → X defined by T (x 0 x 1 x 2 . . .) = x 1 x 2 x 3 . . .. The Cantor space is endowed with the product topology, generated by the cylinders [w], w ∈ {0, 1} * . Implicitly, measures are probability measures defined on the Borel σ-algebra, and ergodic measures are stationary (i.e., shift-invariant) ergodic Borel probability measures. The set P(X) of probability measures over X is endowed with the weak* topology, given by the notion of weak convergence: measures P n converge to P if for every w ∈ {0, 1} * ,

P n [w] → P [w].
A name for a real number r is an infinite binary sequence encoding, in some canonical effective way, a sequence of rational numbers q n such that |q n -r| < 2 -n for all n. A name for a probability measure P is the interleaving, in some canonical effective way, of names for the numbers P [w], w ∈ {0, 1} * . A computable probability measure is a measure admitting a computable name: in other words, the numbers P [w] are uniformly computable.

Let X, Y be any spaces among {0, 1} N , R and P(X). A function f : X → Y is computable if there is an oracle machine that, given a name of x ∈ X as an oracle, outputs a name of f (x) (the computation never halts). Computable functions are continuous. f is computable on a set A ⊆ X if the same holds for all x ∈ A (nothing is required to the machine when x / ∈ A). An object y is computable relative to an object x if the function x → y is computable on {x}, i.e. if there is an oracle machine that on any name of x as oracle, produces a name of y.

An open subset U of the Cantor space is effective if there is a (partial) computable function ϕ : N → {0, 1} * such that U = n∈N [ϕ(n)]. An effective compact set is the complement of an effective open set. Let K ⊆ X be an effective compact set and f : K → Y a function computable on K.

Fact 1 (Folklore) f (K) is an effective compact set. Fact 2 (Folklore) If f is moreover one-to-one then f -1 : f (K) → K is com- putable on f (K).
The product of two computable metric spaces has a natural structure of computable metric space.

Fact 3 (Folklore) If K ⊆ X is an effective compact set and f : K × Y → R is lower semi-computable, then the function g : Y → R defined by g(y) = inf x∈K f (x, y) is lower semi-computable.
If f, g are real-valued functions, f * < g means that there exists c ≥ 0 such that f ≤ cg. f * = g means that f * < g and g * < f .

Effective randomness

Martin-Löf [9] was the first one to define a sound individual notion of random infinite binary sequence. He developed his theory for any computable probability measure on the Cantor space. This theory was then extended to non-computable measures by Levin [8], and later by [START_REF] Gács | Uniform test of algorithmic randomness over a general space[END_REF][START_REF] Hoyrup | Computability of probability measures and Martin-Löf randomness over metric spaces[END_REF] on general spaces ( [START_REF] Hertling | Random elements in effective topological spaces with measure[END_REF] was an extension to topological spaces, but for computable measures).

We will use the most general theory: we will be interested in randomness on the Cantor space and on the space of Borel probability measures over the Cantor space, for arbitrary (i.e. not necessarily computable) probability measures. In particular, we will use the notion of uniform test of randomness, introduced by Levin [8] and further developed in [START_REF] Gács | Uniform test of algorithmic randomness over a general space[END_REF]4,[START_REF] Hoyrup | Computability of probability measures and Martin-Löf randomness over metric spaces[END_REF].

On a computable metric space X endowed with a probability measure P , there is a set R P of P -random elements satisfying P (R P ) = 1, together with a canonical decomposition (coming from the universal P -test) R P = n R n P where R n P are uniformly effective compact sets relative to P , R n P ⊆ R n+1 P and P (R n P ) > 1 -2 -n . The sets X \ R n P constitute a universal Martin-Löf test. A P -test is a function t : X → [0, +∞] which is lower semi-computable relative to P , such that t dP ≤ 1.

A function f : X → Y is P -layerwise computable if there is an oracle machine that, given n as input and a name of x ∈ R n P as an oracle, outputs a name of f (x) (the computation never halts). Nothing is required to the machine when x is not P -random. When f is P -layerwise computable, for every P -random x, f (x) is computable relative to x in a way that is not fully uniform, but uniform on each set R n P . Such a machine can be thought of as a probabilistic algorithm, but here the randomness is not part of the algorithm but of the input. Formally, it is the same notion, but usually, "succeeding with high probability" means that if we run the program on a given input several times, independently, it will succeed most of the times; here, the algorithm is deterministic and it will succeed on most inputs.

Lemma 1. Let P be a computable measure, f : X → Y a P -layerwise computable function and Q = f * P the push-forward of P under f .

1. Q is computable and f : R P → R Q is onto. 2. If f : X → Y is moreover one-to-one then f : R P → R Q is one-to-one and f -1 is Q-layerwise computable.
Proof. We only prove that

f -1 is Q-layerwise computable, the other statements are proved in [6]. There is c ∈ N such that R n Q ⊆ f (R n+c P ) for all n. Let n ∈ N. f : R n+c P → Y is one-to-one and computable so by Fact 2, f -1 : f (R n+c P ) → X is computable. As R n Q ⊆ f (R n+c P ), f -1 : R n Q → X is computable. This is uniform in n.

Randomness and continuous combination of measures

The material developed here will be used to investigate the algorithmic content of the ergodic decomposition.

Given a countable class of probability measures P i and real numbers α i ∈ [0, 1] such that i α i = 1, the convex combination P = i α i P i is again a probability measure. This can be generalized to continuous classes of measures, as we briefly recall now.

Let m be a probability measure over P(X). The set function P defined by

P (A) = Q(A) dm(Q) for measurable sets A is a probability measure over X, called the barycenter of m. It satisfies f dP = ( f dQ) dm(Q) for f ∈ L 1 (X, P ).
When m is computable, so is P . We can think of P as the measure describing the following process: first pick some measure Q at random according to m; then run the process with distribution Q.

Probabilistically, picking a sequence according to P or decomposing into these two steps are equivalent. We are interested in whether the algorithmic theory of randomness fits well with this intuition: are the P -random sequences the same as the sequences that are Q-random for some m-random Q?

Remark 1. Let f : X → [0, +∞] be a lower semi-computable function. Let F : P(X) → [0, +∞] be defined by F (Q) = f dQ. F is lower semi-computable and F dm = f dP . As a result, F is a m-test if and only if f is a P -test.
Theorem 1. Let m ∈ P(P(X)) be computable, and P be the barycenter of m. For x ∈ X, the following are equivalent:

1. x is P -random, 2. x is Q-random for some m-random Q.
In other words,

R P = Q∈Rm R Q . Proof. Let f (x) = inf Q t m (Q).t Q (x). f is lower semi-computable by Fact 3 (P(X) is ef- fectively compact). As f dP = ( f dQ) dm(Q) ≤ t m (Q)( t Q dQ) dm(Q) ≤ 1, f is a P -test, so if x is P -random then it is Q-random for some m-random measure Q. Conversely, let T P (Q) = t P dQ where t P is a universal P -test. By Remark 1, T P is an m-test so if Q is m-random then T P (Q) < ∞, so t P is a (multiple of a) Q-test. As a result, R Q ⊆ R P .

Randomness and ergodic decomposition

Background from ergodic theory

A sequence x ∈ {0, 1} N is generic if for each w ∈ {0, 1} * , the frequency of occurrences of w in x converges. If x is generic, we denote by Q x the set function which maps each cylinder [w] to the limit frequency of occurrences of w in x. Q x extends to a probability measure over the Cantor space, which we also denote by Q

x . If x is generic then Q x is stationary, i.e. Q x (A) = Q x (T -1 (A))
for every measurable set A. Birkhoff's ergodic theorem states that given a stationary measure P , P -almost every x is generic. A stationary measure P is ergodic if the only invariant sets have measure 0 or 1. Formally, if T -1 (A) = A then P (A) = 0 or 1, for every measurable set A. If P is stationary ergodic then Q x = P for P -almost every x.

The ergodic decomposition theorem states that given a stationary probability measure P , the measure Q x is ergodic for P -almost every x. There are mainly two proofs of this fact. One of them uses Choquet theorem from convex analysis (see [START_REF] Phelps | Lectures on Choquet's Theorem[END_REF]): the set of stationary probability measures is a convex compact set whose extreme points are exactly the ergodic measures. Then any point in that set, i.e. any invariant measure, can be expressed as a barycenter over the ergodic measures. More precisely, for any invariant measure P there is a unique probability measure m P over P(X) which gives full weight to the ergodic measures, and such that P (A) = Q(A) dm P (Q) for every Borel set A. We will call m P the Choquet measure associated to P .

Randomness and ergodic theorems

An algorithmic version of Birkhoff's ergodic theorem was eventually proved by V'yugin [START_REF] V'yugin | Ergodic theorems for individual random sequences[END_REF]: given a shift-invariant probability measure P , every P -random sequence is generic, and if P is moreover ergodic then Q x = P for every Prandom sequence x (it was proved for computable measures, but it still works for non-computable measures). The proof was not immediate to obtain from the classical proof of Birkhoff's theorem, which is in a sense not constructive. In this paper we are interested in an algorithmic version of the ergodic decomposition theorem, which again cannot be proved directly.

More precisely, given a stationary measure P , we are interested in the following questions:

-if x is P -random, is Q x ergodic? -if x is P -random, is x also Q x -random? -if x is P -random, is Q x an m P -random measure?
-does any converse implication hold?

We give positive partial answers to these questions, leaving the general problem open. We will use the following lemmas (the first one was proved in [START_REF] V'yugin | Ergodic theorems for individual random sequences[END_REF]).

Lemma 2. Let P be an ergodic stationary probability measure. For every x ∈ R P , Q x = P . Lemma 3. Let P be a stationary probability measure and m P the associated Choquet measure. Every m P -random measure is ergodic and stationary.

Proof. It is known that the set of ergodic stationary measure is a G δ -set. It is moreover effective, i.e. it is an intersection of effective open sets. As it has m P -measure one, it contains R m P .

First answer: effective decomposition

A stationary probability measure P is always computable relative to its associated Choquet measure m P . The converse does not always hold (see Section 4.4 for a counter-example). Definition 1. A computable stationary probability measure P is effectively decomposable if its Choquet measure is computable.

As an application of Theorem 1, we directly get a result when P is effectively decomposable (i.e. when m := m P is computable).

Corollary 1. Let P be a computable stationary probability measure that is effectively decomposable. For x ∈ X, the following are equivalent:

1. x is P -random, 2. x is Q-random for some m-random Q.
In other words, the following are equivalent:

1. x is P -random, 2. x is generic, Q x -random and Q x is m-random.
We also have the following characterization.

Theorem 2. Let P be a computable stationary probability measure. The following are equivalent.

1. P is effectively decomposable, 2. the function X → P(X), x → Q x is P -layerwise computable.

Proof. 1 ⇒ 2. In any probability space (Y, µ) with random elements R µ = n R n µ , we define d µ (y) = min{n :

y ∈ R n µ } (d µ (y) = +∞ if y is not µ-random). d : P(Y ) × Y → [0, +∞] which maps (µ, y) to d µ (y) is lower semi-computable. Let C n = {(Q, x) : d m (Q) ≤ n and d Q (x) ≤ n}. The second projection π 2 : n C n → X is one-to-one. Indeed, if (Q i , x i ) ∈ n C n , i = 1, 2 and π 2 (Q 1 , x 1 ) = π 2 (Q 2 , x 2 ) then (i) x 1 = x 2 , (ii) Q 1 , Q 2 are m-random hence ergodic, (iii) x i is Q i -random so Q xi = Q i ; as a result, Q 1 = Q x1 = Q x2 = Q 2 . C n is effectively compact so π -1
2 is computable on each π 2 (C n ) (uniformly in n) by Fact 2. We know from the proof of Theorem 1 that there exists a constant c such that for all n and all x ∈ R n P , (Q

x , x) ∈ C n+c , hence R n P ⊆ π 2 (C n+c ). It implies that π -1 2 is computable on each R n P , uniformly in n, i.e. π -1 2 is P -layerwise com- putable. Finally, π 1 • π -1 2 , which maps x ∈ R P to Q x is P -layerwise computable. 2 ⇒ 1. Conversely, if ψ : x → Q x is P -layerwise computable, then m = ψ * P
is the push-forward of P under ψ, so it is computable by Lemma 1, item 1.

Remark 2. For f ∈ L 1 (X, P ), we denote by f * the limit of the Birkhoff averages of f . One can also prove that if P is computable then P is effectively decomposable if and only if the function

L 1 (X, P ) → L 1 (X, P ) f → f * is computable.
The effectivity of the ergodic decomposition enables one to extend results from ergodic systems to non-ergodic ones. Let us illustrate it. It was proved in [START_REF] Bienvenu | Ergodic-type characterizations of algorithmic randomness[END_REF] that when P is an ergodic measure, every P -random sequence eventually visits every effective compact set of positive measure under shift iterations. When the decomposition is effective, this theorem can be generalized to non-ergodic measures, giving a version of Poincaré recurrence theorem for random sequences.

Corollary 2. Let P be a stationary measure that is effectively decomposable. Let F be an effective compact set such that P (F ) > 0. Every P -random x ∈ F falls infinitely often in F under shift iterations.

Proof. x is Q x -random and Q x is ergodic. As all random sequences belong to effective open sets of measure one and x ∈ F , Q x (F ) > 0. Hence we can apply the result in [START_REF] Bienvenu | Ergodic-type characterizations of algorithmic randomness[END_REF] to the ergodic measure Q x (strictly speaking their result was proved for computable ergodic measures, but it can be relativized without difficulty).

The result actually holds as soon as for every P -random x, Q x is ergodic and

x is Q x -random.

V'yugin's example

In [START_REF] V'yugin | Ergodic theorems for individual random sequences[END_REF], V'yugin constructed a computable stationary measure for which the convergence of Birkhoff's average is not effective. We give a simpler construction and show that this measure is not effectively decomposable.

Let M i be some effective enumeration of the Turing machines. For each i, let p i = 2 -ti if M i halts in time t i , p i = 0 if t i does not halt. The real numbers p i are computable uniformly in i (while they are not uniformly computable as rational numbers). Let P i be the Markovian stationary measure defined by

P i [0] = P i [1] = 1 2 and Pi[w01] Pi[w0] = Pi[w10]
Pi[w1] = p i for all w ∈ {0, 1} * (the probability of changing between states 0 and 1 is p i ). Let P = i 2 -i P i . P is computable. We now show that x → Q x is not P -layerwise computable (which will imply that P is not effectively decomposable by Theorem 2). Let

f = χ [1] . Let α = i:Mi halts 2 -i . f * (x) = 0 for x = 0 N , f * (x) = 1 for x = 1 N and f * (x) = 1 2 for P - almost all x / ∈ {0 N , 1 N }. By definition of Q x , f * (x) = Q x [1]
for every P -random x. If f * were P -layerwise computable, then P (f * -1 [0, 1/4)) = (1 -α)/2 would be lower semi-computable by basic properties of layerwise computable functions (see [6]).

While P is not effectively decomposable, we can still get a result about random elements. Proposition 1. For every P -random x, Q x is ergodic and x is Q x -random.

Proof. The decomposition P = i 2 -i P i is partial in the sense that some P i are not ergodic (when M i does not halt). However we can apply Theorem 1 to this decomposition: P is the barycenter of the computable measure m ′ = i 2 -i δ Pi , so every P -random x is random for some P i . (i) If M i halts, then P i is ergodic. (ii) If M i does not halt then P i = 1 2 (δ 0 + δ 1 ) (where δ 0 is the measure concentrated on 0 N , δ 1 on 1 N ). In turn, P i , which is non-ergodic is effectively decomposable. Hence as

x is P i -random, Q x = δ 0 or δ 1 and x is Q x -random.
As a result, Corollary 2 also holds for the measure P .

4.5 A particular case: effective compact classes of ergodic measures Proposition 2. Let P be a computable stationary probability measure. If m P is supported on an effective compact class of ergodic measures, then P is effectively decomposable.

Proof. Let C be an effective compact class of stationary ergodic probability measures. Let P(C ) be the set of probability measures m over P(X) such that m(C ) = 1. P(C ) is an effective compact subset of P(X): indeed, it is the preimage of [1, +∞] under the upper semi-computable function m → m(C ). If m ∈ P(C ), the barycenter P of m is defined by P (A) = Q(A) dm(Q) for every measurable set A. The function ψ which maps m to P is computable. Let I C be the class of invariant measures that are barycenters of C , i.e. the image of P(C ) under ψ: I C is an effective compact class too. By existence and uniqueness of the ergodic decomposition, ψ : P(C ) → I C is onto and one-to-one; as it is computable and P(C ) is an effective compact set, its inverse is also computable by Fact 2.

The above proposition implies the computability of De Finetti measures on the Cantor space (see [START_REF] Freer | Computable exchangeable sequences have computable de finetti measures[END_REF]).

Example 1. Let m be a computable probability measure over the real interval [0, 1]. Pick a real number p at random according to m, and then generate an infinite sequence of 0, 1 tossing a coin with probability of heads p. As an application of the preceding proposition, we get that the function which maps a random sequence generated by the process to the number p that was picked is P -layerwise computable: it can be computed from the observed outcomes with high probability. We also learn that the algorithmic theory of randomness fits well with this example: obviously, we expect a random sequence for the whole process to be random for some Bernoulli measure B p , which is not immediate.

In Section 2.1, we define P -layerwise computable function when P is a computable probability measure. This can be extended straightforwardly to any effective compact class of measures C . The universal C -test induces a decomposition n R C n of the sequences that are random for some measure in

C . A function f : X → Y is C -layerwise computable if it is computable on each R C
n , uniformly in n. It means that one can compute f (x) if x is random for some measure P ∈ C , with probability of error bounded by 2 -n , whatever P is (as long as it is in C ), and for any n.

From Proposition 2 and Corollary 1 we know that for every P ∈ I C and every x ∈ R P , Q x is m-random, hence ergodic and x is Q x -random. We also prove a quantitative version of this fact. We recall that if A is an effective compact class of measures, t A := inf P ∈A t P is a universal A-test, i.e. (i) it is lower semi-computable, (ii) t A dP ≤ 1 for every P ∈ A and (iii) t A multiplicatively dominates every function satisfying (i) and (ii) (see [4] for more details about such class tests). We will consider the class tests t C and t I C . Theorem 3. Let C be an effective compact class of stationary ergodic probability measures. One has:

1. t C (x) * = t I C (x) 2. The function x → Q x is I C -layerwise
(x) = inf Q∈C t Q (x), if x ∈ R n C then Q x ∈ R n+c m . Again, π 2 : R n+c m × R n C → R n
C is computable and bijective so its inverse is computable and maps

x to (Q x , x). Hence π 1 • π -1 2 is computable on R n C , uniformly in n, i.e. it is C -layerwise computable. As t C * < t I C , it is also I C -layerwise computable.
Observe that for generic sequences x, t C (x) * = t Qx (x). Indeed, t C (x) = inf P ∈C t P (x) = t Qx (x) as t P (x) = +∞ for every P ∈ C \ {Q x }.

A weaker answer: finitely decomposable measures

In the two preceding results, we need the effectivity of the ergodic decomposition. In particular situations, we still get a (weaker) result without this assumption. Proposition 3. Let P be a stationary measure such that m P is supported on a closed set C of stationary ergodic measures. For every P -random x, Q x is ergodic.

To prove it we use the following lemma.

Lemma 4. Let X, Y be computable metric spaces. Let f n : X → Y be uniformly computable functions that converge P -a.e. to a function f . Let A ⊆ Y be a closed set such that f (x) ∈ A for P -a.e. x. For every P -random x, lim f n (x) ∈ A.

Proof. It is already known if f is constant P -almost everywhere. Let x 0 be a P -random point such that lim f n (x 0 ) / ∈ A. Let B(y, r) be a ball with computable center and radius, containing lim f n (x 0 ) and disjoint from A. Let g n (x) = max(0, r -d(f n (x), y)). For P -almost every x, the sequence g n (x) converges to 0, but lim g n (x 0 ) = r -d(lim f n (x 0 ), y) > 0.

Proof (Proof of Proposition 3). For every n, define Q n : X → P(X) by Q n (x) = 1 n (δ x + . . . + δ T n-1 x ). A sequence x is generic if and only if Q n (x) is weakly convergent, and in that case Q x is the limit of Q n (x). The functions Q n are uniformly computable. As Q x ∈ C for P -almost every x, Q x ∈ C for every P -random x by Lemma 4.

For instance, if P has a finite decomposition, i.e. if P = n i=1 α i P i where α i ∈ [0, 1], i α i = 1 and all P i are ergodic, then regardless of the computability of P, α i , P i , for every P -random x, Q x ∈ {P 1 , . . . , P n } as the latter set is closed. In this particular case, Q x is always m-random.

We do not know whether every finitely decomposable measure is effectively decomposable. For instance, are there distinct non-computable ergodic measures P 1 , P 2 such that P := 1 2 (P 1 + P 2 ) is computable? Such a measure P would be a finitely, non-effectively decomposable measure.

If a finitely, but non-effectively, decomposable measure P exists, and if x is P -random, we do not know whether x is Q x -random and we do not know whether Q x is m P -random. We only know that Q x is ergodic.

  computable and C -layerwise computable. Proof. 1. Of course, t I C * < t C as C ⊆ I C . Conversely, the P ∈ I C : t C dP = ( t C dQ) dm(Q) ≤ 1 as m is supported on measures in Q ∈ C , and t C dQ ≤ 1 for such measures. As a result, t C is a I C -test, so t C * < t I C . 2. The proof is similar to the proof of Theorem 2. As t C


Mathieu Hoyrup
email: mathieu.hoyrup@loria.fr

Cristobal Rojas
email: cristobal.rojas@utoronto.ca

Klaus Weihrauch
email: klaus.weihrauch@fernuni-hagen.de

Cristóbal Rojas

Computability of the Radon-Nikodym derivative

est destinée au dépôt

Introduction

Theorem 1 (Radon-Nikodym). Let (Ω, A, λ) be a measured space where λ is σ-finite. Let µ be a finite measure that is absolutely continuous w.r.t. λ. There exists a unique function h ∈ L 1 (λ) such that for all f ∈ L 1 (µ),

f dµ = f h dλ.
h is called the Radon-Nikodym derivative, or density, of µ w.r.t. ν.

Is this theorem computable? Can h be computed from µ and λ? In [START_REF] Hoyrup | The Radon-Nikodym operator is not computable[END_REF] a negative answer was given.

In this paper we investigate to what extent this theorem is non-computable. We first give an upper bound for its non-computability, showing that it can be computed using a single application of the operator EC (which transforms enumerations of sets of natural numbers into their characteristic functions). In proving this result we use two classical theorems: Levy's zero-one law and Radon-Nikodym Theorem itself. We then give a sufficient condition on the measures to entail the computability of the RN derivative: this condition is the computability of the norm of a certain integral operator associated to the measures.

Preliminaries

Little bit of Computability via Representations

To carry out computations on infinite objects we encode those objects into infinite symbolic sequences, using representations (see [START_REF] Weihrauch | Computable Analysis[END_REF] for a complete development). Let Σ = {0, 1}. A represented space is a pair (X, δ) where X is a set and δ ⊂ Σ N → X is an onto partial map. Every p ∈ dom(δ) such that δ(p) = x is called a δ-name of x (or name of x when δ is clear from the context).

Let (X, δ X ) be a represented space. An element x ∈ X is computable if it has a computable name. Let (Y, δ Y ) be another represented space. A realizer for a function f :

X → Y is a (partial) function F : Σ N → Σ N such that f • δ X = δ Y • F (
with the expected compatibilities between domains). f is computable if it has a computable realizer. Of course the image of a computable element by a computable function is computable.

Example 1. Let 2 N be the powerset of N. The classical notions of recursive and recursively enumerable sets can be grasped as the computable elements of the space 2 N endowed with two representations, Cf and En respectively, defined by:

En(p) = {n ∈ N : 100 n 1 is a subword of p} Cf(p) = {n ∈ N : p n = 1}
where p ∈ Σ N , p n is the nth symbol in p. En, Cf : Σ N → 2 N are total functions. We define the operator EC as the identity from represented space (2 N , En) to represented space (2 N , Cf). It transforms an enumeration of a set into its characteristic function. EC is not computable.

The non-computability of functions f, g between represented spaces can be compared using a notion of reducibility introduced in [5]: f ≤ W g if there are computable (partial) functions K, H such that for every realizer G of g, p → K(p, G • H(p)) is a realizer of f . In other words, f ≤ W g if f can be computed using one single application of g (provided by an oracle) in the computation. 4

Computable Measurable Spaces

We start by briefly recalling some basic definitions from measure theory. See for example [4,2,1] for a complete treatment. A ring R over a set Ω is a collection of subsets of Ω which contains the empty set and is closed under finite unions and relative complementation (B \ A ∈ R, for A, B ∈ R). A σ-algebra A (over the set Ω) is a collection of subsets of Ω which contains Ω and is closed under complementation and countable unions (and therefore also closed under countable intersections). A ring R generates a unique σ-algebra, denoted by σ(R), and defined as the smallest σ-algebra containing R.

In this paper we will work with the measurable space (Ω, A), where A is a σ-algebra generated by a countable ring R. Members of A = σ(R) will be referred to as measurable sets.

A measure over a collection C (which is at least closed by finite unions) of subsets of Ω is a function µ

: C → R ∞ (= R ∪ {∞}) such that i) µ(∅) = 0, µ(E) ≥ 0 for all E ∈ C, and ii) µ( i E i ) = i µ(E i ) for pairwise disjoint sets E 0 , E 1 , . . . ∈ C such that i E i ∈ C. A measure µ over a collection C is said to be σ-finite, if there are sets E 0 , E 1 , . . . ∈ C such that µ(E i ) < ∞ for all i and Ω = i E i .
It is well known that a σ-finite measure over ring R has a unique extension to a measure over the σ-algebra σ(R). For measures µ and λ, we say that µ is absolutely continuous w.r.t. λ, and write µ ≪ λ, if (λ(A) = 0 =⇒ µ(E) = 0) for all measurable sets E.

We now introduce the effective counterparts.

Definition 1. A computable measurable space is a tuple (Ω, A, R, α) where 1. (Ω, A) is a measurable space, R is a countable ring such that ∪R = Ω and A = σ(R), 2. α : N → R is a computable enumeration such that the operations (A, B) → A ∪ B and (A, B) → A \ B are computable w.r.t. α.
In the following (Ω, A, R, α) will be a computable measurable space. We will consider only measures µ :

A → [0; ∞] such that µ(E) < ∞ for every E ∈ R.
Observe that such a measure µ is σ-finite, and therefore well-defined by its values on the ring R. Conversely if a measure µ over A is σ-finite, one can choose a countable generating R such that µ(E) < ∞ for all E ∈ R.

Computability on the space of measures over (Ω, A, R) will be expressed via representations.

Definition 2. Let M be the set of measures µ such that µ(E) < ∞ for all E ∈ R and let M <∞ be the set of all finite measures. Define representations δ M : Σ N → M and δ M<∞ : Σ N → M <∞ as follows:

1. δ M (p) = µ, iff p is (more precisely, encodes) a list of all (l, n, u) ∈ Q 3 such that l < µ(E n ) < u, for every E n ∈ R. 2. δ M<∞ (p) = µ, iff p = p 1 , p 2 such that δ M (p 1 ) = µ and p 2 is (more precisely, encodes) a list of all (l, u) ∈ Q 2 such that l < µ(Ω) < u.

Thus, a δ M -name p allows to compute µ(A) for every ring element A with arbitrary precision. A δ M<∞ -name allows additionally to compute µ(Ω). Obviously, δ M<∞ ≤ δ M and δ M<∞ ≡ δ M if Ω ∈ R. But in general, not even the restriction of δ M to the finite measures is reducible to δ M<∞ .

We will also work with the spaces L 1 of integrable functions and L 2 of squareintegrable functions (w.r.t. some measure). A rational step function is a finite sum

s = p k=1 1(E i k )q j k , where E i k ∈ R and q j k ∈ Q.
The computable numberings of the ring R = (E 0 , E 1 , ...) and of the rational numbers Q = (q 0 , q 1 , ...) induce a canonical numbering of the the collection RSF = (s 0 , s 1 , ...) of rational step functions. Since the collection RSF is dense in the spaces L 1 and L 2 , we can use it to handle computability over these spaces via the following representations:

Definition 3. For every µ ∈ M define Cauchy representations δ k µ : Σ N → L k (µ) of L k (µ) (k = 1, 2) by: δ k µ (p) = f iff p is (encodes) a sequence (s n0 , s n1 , . . .) of rational step functions such that s ni -f k µ ≤ 2 -i for all i ∈ N.
3 Effective Radon-Nikodym Theorem

An upper bound

In the following, we present our first main result which, in words, says that computability of the Radon-Nikodym derivative is reducible to a single application of the (non-computable) operator EC.

Theorem 2. The function mapping every σ-finite measure λ ∈ M and every finite measure µ such that µ ≪ λ to the function h ∈ L 1 (λ) such that µ(E) = E h dλ for all E ∈ σ(R) is computable via the representations δ M , δ M<∞ and δ 1 λ with a single application of the operator EC.

For the proof, we will use the following classical result on convergence of conditional expectations, which is a consequence of the more general Doob's martingale convergence theorems (see for example [START_REF] Dudley | Real Analysis and Probability[END_REF], Section 10.5). We recall that a filtration (F n ) n is an increasing sequence of σ-algebras on a measurable space. In some sense, F n represents the information available at time n. In words, the following result says that if we are learning gradually the information that determines the outcome of an event, then we will become gradually certain what the outcome will be.

Theorem 3 (Levy's zero-one law). Consider a measured space (Ω, σ(R), λ)

with λ finite. Let h ∈ L 1 (λ). Let (F n ) n be any filtration such that σ(R) = σ( n F n ). Then E(h|F n ) -→ n→∞ h
both λ-almost everywhere and in L 1 (λ).

Proof (of Theorem 2). We start by proving the result for finite measures.

Lemma 1. From descriptions of finite measures µ ≪ λ, one can compute a sequence {h n } n∈N of L 1 (λ)-computable functions which converges in L 1 (λ) to the Radon-Nikodym derivative h = dµ dλ ∈ L 1 (λ).

Proof. Consider the computable enumeration E 0 , E 1 , . . . of R. For every n, consider the partition P n of the space given by the cells:

-all the possible E * 0 ∩ E * 1 ∩ . . . ∩ E * n where E * is either E or (E 0 ∪ . . . ∪ E n ) \ E, -all the E k+1 \ (E 0 ∪ . . . ∪ E k ) for every k ≥ n.
Observe that all the cells are elements of the ring R. The partitions P n induce a filtration which generates the σ-algebra σ(R). Let h be the RN-derivative 5 of µ w.r.t. λ. h ∈ L 1 (λ) so by Levy's zero-one law, E(h|P n ) -→ n→∞ h both λ-almost everywhere and in L 1 (λ). Now, h n := E(h|P n ) is constant on each cell C of P n , with value µ(C) λ(C) if λ(C) > 0 and 0 otherwise. We now show that the functions h n are (uniformly) computable elements of L 1 (λ). For a given ǫ, one can find cells C 1 , ..., C k in P n such that λ(C i ) > 0 for all i = 1, ..., k and k i=1 µ(C i ) > µ(Ω)-ǫ. Define h ǫ n to be constant with value µ(Ci) λ(Ci) for i = 1, ..., k and 0 on the other cells. As these values are uniformly computable, the functions h ǫ n are uniformly

L 1 (λ)-computable. Moreover |h n -h ǫ n | dλ = Ω\ S k i=1 Ci h n dλ < ǫ
and thus, the functions h n are (uniformly) computable elements of L 1 (λ), and converge to h in L 1 (λ). The lemma is proved.

Assume now that µ ∈ M <∞ and λ ∈ M. Let once again (E 0 , E 1 , . . .) be the computable numbering of the ring R. Let F 0 := E 0 and F n+1 := E n+1 \ {F 0 , . . . , F n }. Then (F i ) i is a computable numbering of ring elements such that (

F i ∩ F j = ∅ for i = j and Ω = i F i . Since i → µ(F i ) is computable,
) 1
for all E ∈ R. Then ν is a finite measure, which is equivalent to λ (i.e. ν ≪ λ ≪ ν) and such that a δ M -name of ν can be computed from a δ M -name of λ. Apply Lemma 1 to µ and ν: one can compute a sequence of L 1 (ν)-computable functions {h ′ n } whose limit (in L 1 (ν)) is the density h ′ = dµ dν . The sequence {h ′ n w} is computable and converges (in L 1 (λ)) to h = dµ dλ = wh ′ . At this point we use the operator EC to extract a fast convergent subsequence, and hence to compute (a δ 1 λ -name of) h. The proof is complete.

The above theorem shows that the Radon-Nikodym theorem is reducible to the (non-computable) operator EC. On the other hand, it was shown in [START_REF] Hoyrup | The Radon-Nikodym operator is not computable[END_REF] that

  there is a computable function d :N → N such that d(i) > µ(F i ) • 2 i . Define a function w : Ω → R by w(x) := 1/d(i) if x ∈ F i . Then w dλ = i µ(F i )/d(i) < 2.Define a new measure ν by ν(E) := E w dλ.

the relation is denoted ≤W as it is a generalization of Wadge reducilibility.

there exists a computable measure on the unit interval, absolutely continuous w.r.t. Lebesgue measure, and such that the operator EC can be reduced to the computation of the density (which is therefore not L 1 -computable). This give us the following corollary.

Corollary 1. For nontrivial computable measurable spaces, the Radon-Nikodym operator and EC are equivalent: RN ≡ W EC.

This result characterize the extent to which the Radon-Nikodym theorem is non-computable. However, it doesn't give us much information on "where" is the non-effectivity. In what follows we present a result which gives an explicit condition (in terms of the computability of the norm of a certain linear operator involving the two measures) allowing to compute the Radon-Nikodym derivative. The proof of this result is somewhat more involved, and some preparation will be required.

Locating the non-computability

Let µ ∈ M <∞ be a finite measure over (Ω, A, R). Let u : L 2 (µ) → R be a linear functional. Classically we have that the following are equivalent:

The smallest bound for u is called the norm of u and is denoted by u . That is,

Suppose that the operator u is computable in the sense that one can compute the real number u(f ) from (a δ M -name of) µ and (a δ 2 µ -name of) f . Consider now the numbered collection RSF = {r n } n∈N . Since the sequence s i := ri ri 2 is uniformly computable (from µ) and dense in {f ∈ L 2 (µ) : f 2 = 1}, it follows that the norm u of a computable operator u is always a lower-computable (from µ) number. It is not, in general, computable. In case it is computable, we will say that the operator u is computably normable.

The following result is an effective version of Riesz-Fréchet Representation Theorem. For simplicity, we state the result in the particular Hilbert space L 2 (µ), but the same proof works for any Hilbert Space provided that the inner product is computable. Theorem 4. Let u be a non-zero computably normable (from µ) linear functional over L 2 (µ). Then from µ one can compute a name of (the unique) g ∈ L 2 (µ) such that

Proof. In the following, all what we will compute will be from a δ M -name of µ. Chose any computable x ∈ L 2 (µ) out of ker(u). As u is computable, from the classical formula d(x, ker(u)) = |u(x)| u , it follows that d(x, ker(u)) is computable too. We can then enumerate a sequence of points

we can compute a subsequence y ni converging effectively to z 0 which is therefore computable. Put z = z0 z0 so that z = 1. All what remains is to show that g = u(z)z (which is computable) satisfies the required property. This is done as in the classical proof, namely: z has the property of being orthogonal to ker(u). That is, zf dµ = 0 for any f ∈ ker(u). Put

We have u(r) = u(f )u(z)u(z)u(f ) = 0 so that r ∈ ker(u) and then rz dµ = 0. This gives,

and hence g = u(z)z, as was to be shown.

Remark 1. Let µ be a finite measure. For f, g in L 2 (µ), Hölder's inequality implies that f g ∈ L 1 (µ) and:

so that, in particular, since µ is finite, if f ∈ L 2 then f ∈ L 1 (taking g ≡ 1). Moreover, from a δ 2 µ -name of f one can compute a δ 1 µ -name. Now, let µ and λ be finite measures and consider a new measure ϕ := µ + ν. Let L µ : L 2 (ϕ) → R be defined by L µ (f ) := f dµ. This is a bounded operator and it is easy to see that from δ M -names of µ and λ and from a δ 2 ϕ -name of f , one can compute the value L µ (f ). Definition 4. A finite measure µ is said to be computably normable relative to some other finite measure λ, if the norm of the operator L µ (as defined above) is computable from µ and λ.

At this point, we are ready to state our second main result.

Theorem 5. Let µ, λ ∈ M <∞ be such that:

Then the Radon-Nikodym derivative dµ dλ can be computed as an element of L 1 (λ), from µ and λ.

Proof. We follow Von Neumann's proof. The measure ϕ := µ + λ is computable and by hypothesis the operator L µ : L 2 (ϕ) → R defined by L µ (f ) := f dµ is computably normable. Hence, by Theor. 4 one can compute a name of g ∈ L 2 (ϕ) (and hence a name of g as a point in L 1 (λ)) such that for all f ∈ L 2 (ϕ) the equality:

holds. This relation can be rewritten as:

Note that (4) holds for any f ≥ 0 (take f n = f 1 {f <n} and apply monotone convergence theorem). Taking f = 1 {g=1} in (4) we see that λ({g = 1}) = 0. Hence the following function is defined λ-almost everywhere:

Taking f = 1 {g<0} and 1 {g>1} in (4) we see that 0 ≤ g ≤ 1 λ-a.e., so h ≥ 0 λ-a.e. Therefore,

= f dµ. Now, taking f to be the constant function equal to 1, we conclude that h dλ = 1 and then it is in L 1 (λ). This shows that h is the Radon-Nikodym derivative.

It remains to show that the function h = g 1-g is L 1 (λ)-computable. As g is L 1 (λ)-computable, we can effectively produce a sequence u i of rational step functions such that u ig λ < 2 -i . As g ≥ 0 λ-a.e. we can assume w.l.o.g. that u i ≥ 0 (otherwise replace u i with max(u i , 0)).

For n ∈ N let

Since the function x → x/(1x) is nondecreasing over (0, +∞),

Given a rational number ǫ > 0 we show how to compute n and i such that

v in will then be a rational step function approximating h up to ǫ, in L 1 (λ). As a result, it will enable to compute a δ 1 µ -name of h. To find n and i, we use the following inequality

We first make the first term small. As for all n, 0 ≤ h n ≤ h, one has hh n λ = h λh n λ . As h λ = µ(Ω) is given as input and h n λ can be computed from n, one can effectively find n such that h λh n λ < ǫ/2.

We then make the second term in (5) small:

We then compute i such that 2 -i • 2 2n < ǫ/2. One finally gets the expected inequality hv in λ ≤ hh n λ + h nv in λ < ǫ and the result follows.


R Bachelard
email: bachelard.romain@gmail.com

T Dauxois

G De Ninno

S Ruffo

F Staniscia
email: fabio.staniscia@elettra.trieste.it

Vlasov equation for long-range interactions on a lattice

We show that, in the continuum limit, the dynamics of Hamiltonian systems defined on a lattice with long-range couplings is well described by the Vlasov equation. This equation can be linearized around the homogeneous state and a dispersion relation, that depends explicitly on the Fourier modes of the lattice, can be derived. This allows one to compute the stability thresholds of the homogeneous state, which turn out to depend on the mode number. When this state is unstable, the growth rates are also function of the mode number. Explicit calculations are performed for the α-HMF model with 0 ≤ α < 1, for which the mean-field mode is always found to dominate the exponential growth. The theoretical predictions are successfully compared with numerical simulations performed on a finite lattice.

INTRODUCTION

Long-range interactions are found in many different domains of physics: self-gravitating systems, unscreened Coulomb systems, plasmas, cold atoms, two-dimensional fluids [1][START_REF]Dynamics and Thermodynamics of Systems with Long-Range Interactions[END_REF][START_REF]Dynamics and Thermodynamics of systems with long range interactions: theory and experiments[END_REF][START_REF]Long-Range Interacting Systems[END_REF][START_REF] Bouchet | [END_REF]. Systems with long-range interactions have interesting properties at equilibrium, such as ensemble inequivalence [6]. In this paper we will be concerned with their dynamical out-of-equilibrium behavior.

In the continuum limit, where the number of particles, N , goes to infinity, the dynamics of these systems is well described by the Vlasov equation [START_REF] Balescu | Statistical Dynamics: Matter out of Equilibrium[END_REF][START_REF] Nicholson | Introduction to Plasma Theory[END_REF]. It has been found that stable stationary states of this equation correspond to quasi-stationary states (QSS) of the finite-N system [START_REF] Yamaguchi | [END_REF]. Long-range systems generically show a rapid evolution towards QSS, where the system remains trapped for a time that increases algebraically with N . In the long time limit the system eventually relaxes to Boltzmann-Gibbs equilibrium. This complex relax-ation process was first described in pioneering papers of Henon [10] and Lynden-Bell [11].

The Vlasov equation is usually derived for Hamiltonians of the form

H = N j=1 p 2 j 2 + 1 2 N j =k=1 V (|q j -q k |) , (1)
where q j denotes the position of the j-th particle in threedimensional space, p j its conjugate momentum and V (x) the potential function.

In this paper, we will show that systems defined on a one-dimensional lattice with N sites can also be described by a Vlasov equation, if the coupling constant decays algebraically with the distance between two sites of the lattice.

We consider Hamiltonians of the following form

H = N j=1 p 2 j 2 + 1 2 Ñ N j,k=1 v(q j , q k ) |x j -x k | α , (2)
where x j = ja is the fixed coordinate of the j-th site on a one-dimensional lattice (the lattice constant a will be set to unity) and Ñ = N j=1 j -α ∼ N 1-α , with 0 ≤ α < 1, is a normalization constant which makes the potential energy extensive in N [17]. We choose periodic boundary conditions, x 1 = x N +1 ,q 1 = q N +1 , p 1 = p N +1 .

The vector variable q j has now a different physical interpretation: it represents the internal degrees of freedom attached to site j. These degrees of freedom are assumed to be still described by a Hamiltonian structure with a momentum vector p j conjugate to q j . The dimension D of these vectors is not the dimension of the physical space in which the motion of the particles takes place, but the dimension of the space of internal degrees freedom, so that it can take values different from D = 3.

Models of this kind were introduced by Dyson [12,13], Thouless [14] in the 60's with the aim of understanding phase transitions in one dimension, and were also connected to the physics of Kondo effect [15,16]. However, the internal degrees of freedom were discrete Ising variables while, following [18], we here generalize the model to continuous variables representing, e.g., XY spins. Moreover, the addition of a kinetic term in the Hamiltonian allows us to treat the microcanonical dynamics.

To be concrete, let us consider the case in which we attach to site j a two-dimensional vector pointing to the unit circle: q j = (cos q j , sin q j ), with -π ≤ q j < π an angle. This vector physically represents an XY rotor with conjugate angular momentum p j pointing towards the Z-direction. For example, let the function v(x, y) be the scalar product of the two arguments v(q j , q k ) = -Jq j • q k = -J cos(q j -q k ), where the coupling constant J can be positive (ferromagnetic coupling) or negative (antiferromagnetic coupling). This coupling has been already considered in the literature [18][19][20][21] and the corresponding model goes under the name of α-HMF, where the acronym stands for Hamiltonian Mean Field. Indeed, when α = 0 the model reduces to the HMF model [22][23][24]: the lattice structure is removed in this limit and the rotors are coupled with equal strength.

Two kinds of results were obtained for the ferromagnetic α-HMF model. On the one hand, it was shown analytically that the statistical equilibrium is the same as the one of the all-equally-coupled α = 0 case, both in the canonical and in the microcanonical ensemble [20,21]. These results were anticipated by numerical simulations performed in the microcanical ensemble [18,19]. On the other hand, simulations performed in out-of-equilibrium conditions have shown that no significant difference is observed in the features of the QSS with respect to the α = 0 case [19,25,26]. This raises the question of the full equivalence between the model with all-to-all coupling and the lattice model (see also [27]).

We will here show that the Vlasov formalism can be actually generalized to long-range interactions on a lattice. In the N → ∞ limit, each infinitesimal element of the lattice contains an infinity of sites, to which a local distribution function in phase-space f (q, p; x, t), depending also on the spatial coordinate x along the lattice, can be associated. A Vlasov equation for this local distribution function can be then derived, and the long-range interaction determines a global coupling between these local distributions at different spatial locations. A linear stability analysis of a state which is both uniform in the internal degrees of freedom and along the lattice will be performed and the stability thresholds will be determined analytically. When this state is unstable, different Fourier modes grow with different rates and the zero mode, i.e. the mean-field mode of the α = 0 model, is found to dominate the instability process, indicating that, indeed, the dynamics shows similar features with the HMF model. This paper is organized as follows: Section 2 is devoted to the derivation of the Vlasov equation for long-range interacting systems on a lattice. In Section 3 we discuss the linearization around the uniform state and we find a dispersion relation expressed in terms of lattice Fourier modes. In Section 4 we derive the stability thresholds and the growth rates of the Fourier modes for the α-HMF model, which are tested against numerical simulations performed with finite N in Section 5. Finally, in Section 6 we draw some conclusions.

VLASOV EQUATION ON A LATTICE

In order to simplify the derivation, we restrict to onedimensional internal degrees of freedom attached to the lattice site j. These degrees of freedom are represented by the canonically conjugate pair (q j , p j ). The Hamiltonian is the following

H = j p 2 j 2 + 1 2 Ñ N j,k=1 v(q j , q k ) |x j -x k | α , (3)
where v(x, y) is symmetric in the two arguments. The equations of motion are then

qj = p j , (4) ṗj
= - 1 Ñ k v ′ (q j , q k ) |x j -x k | α , (5)
where the prime denotes the derivative with respect to one of the two arguments. Since we have chosen periodic boundary conditions, we use the closest distance convention, i.e. the distance

|x j -x k | actually corresponds to min(|x j -x k |, 1 -(|x j -x k |)).
In the continuum limit, the lattice (which for periodic boundary conditions can be thought to be a circle) is densely filled with sites: each infinitesimal lattice element dx contains a diverging number of sites as N goes to infinity. Therefore, one can define in this limit a distribution function f (q, p; x, t), which depends both on the internal variables (q, p) and on the coordinate x along the lattice, which is confined to the interval [0, 1]. In the continuum limit, the equations of motion become q = p,

= -κ α f (q ′ , p ′ ; x ′ , t) v ′ (q, q ′ ) |x -x ′ | α dq ′ dp ′ dx ′ , (6) ṗ
where

κ α is such that 1/ Ñ ----→ N →∞
κ α /N . The latter limit can be shown to yield κ -1 α = +1/2 -1/2 dx/|x| α . Equation [START_REF] Balescu | Statistical Dynamics: Matter out of Equilibrium[END_REF] naturally leads to the definition of the long-range potential

V x [f ](q, t) = κ α dq ′ dp ′ dx ′ f (q ′ , p ′ ; x ′ , t) v(q, q ′ ) |x -x ′ | α , (8)
which determines the motion of the conjugate variables (q, p) at point x. This definition allows us to write the following Vlasov equation

∂f ∂t + p ∂f ∂q -V ′ x [f ](q, t) ∂f ∂p = 0, (9)
where the prime refers to ∂/∂q. It is interesting to note that this equation also derives from the following Hamiltonian

H[f ] = dq ′ dp ′ dx ′ f (q ′ , p ′ ; x ′ , t) p ′2 2 + 1 2 V x [f ](q ′ ) .
(10) Thus, Eq. ( 9) actually represents a continuum of Vlasov equations along the lattice, globally coupled through the potential [START_REF] Nicholson | Introduction to Plasma Theory[END_REF]. The absence of a spatial derivative ∂ x in Eq. ( 9) reminds us that the lattice sites are fixed.

More rigorously, one should follow a procedure that begins with the definition of the so-called empirical measure

f e (q, p; x, t) = 1 N j δ(q -q j (t))δ(p -p j (t))δ(x -x j ) , (11)
and then derive the Klimontovich equation as done in [START_REF] Braun | [END_REF]36]. The Vlasov equation could be then derived using a convenient averaging method.

It is also important to stress that definition (8) is consistent only for α < 1, since the integral dx ′ /|x -x ′ | α is convergent around x only for such values of α. For α = 1 the integral diverges logarithmically, we will not consider this case.

Let us comment about the normalization of f , an issue linked to the density of sites along the lattice. Since we are here considering a homogeneous lattice, each infinitesimal element dx contains the same number of particles. Hence the norm of f (q, p; x, t) has to be the same at any position x f (q, p; x, t)dqdp = 1.

(

) 12
Yet, our formalism is also suitable for heterogeneous lattices with non-uniform density of sites ρ(x), for which the normalization is given by

f (q, p; x, t)dqdp = ρ(x). (13)
The density ρ(x) enters as a weight when deriving the local potential

V x [f ].
Finally, we note that the generalization to higherdimensional lattices and to higher dimensional spaces of internal degrees of freedom is straightforward. For Ddimensional conjugate variables (q, p) defined at position r on a d-dimensional lattice, the 1/|x j -x k | α coupling turns into 1/|r j -r k | α , and the distribution function f (q, p; r, t) obeys a Vlasov equation at each site r.

THE DISPERSION RELATION

As anticipated in the introduction, the emergence of a Vlasov equation in long-range systems is of particular importance for their dynamics, since it is responsible for the long-lasting out-of-equilibrium regimes for finite N , the so-called QSS. This phenomenon is however bounded to the existence of Vlasov stationary stable states. We shall now turn to determine the conditions for such states to be present for the Vlasov equation on a lattice [START_REF] Yamaguchi | [END_REF]. Let us consider a stationary solution f 0 of Eq. ( 9)

p∂ q f 0 -V ′ x [f 0 ](q)∂ p f 0 = 0. ( 14
)
From the above relation, it appears that the motion of a test-particle at position x can be derived from the following Hamiltonian

h x (q, p) = p 2 2 + V x [f 0 ](q) . (15)
Following the observation that h x (q, p) is a conserved quantity for stationary solutions f 0 , several authors [START_REF] Binney | Galactic Dynamics[END_REF][29][30][31][32][33][START_REF] Bachelard | Stability of inhomogeneous states in mean-field models with a local potential[END_REF]37] studied inhomogeneous Vlasov equilibria expressing the stability problem in action-angle variables. However, for the sake of simplicity, we will here focus on homogeneous stationary states, both in position x along the lattice and in the internal variable q. This implies that f 0 = f 0 (p) and V ′ x [f 0 ](q) = 0 for all x. The stability of f 0 can be studied by considering a small perturbation of the stationary distribution f (q, p; x, t) = f 0 (p) + δf (q, p; x, t).

(

) 16
Inserting the above expression into the Vlasov equation ( 9) and dropping the quadratic term in δf leads to the linearized Vlasov equation

∂ t (δf ) + p∂ q (δf ) -f ′ 0 (p)V ′ x [δf ](q, t) = 0. ( 17
)
If we now focus on an eigenmode δf t (q, p; x) = e λt f (q, p; x) of the linearized dynamics, we get

(λ + p∂ q ) f (q, p; x) -f ′ 0 (p)V ′ x [ f ](q) = 0, (18)
which can be rewritten as

∂ q e λ q p f - e λ q p p f ′ 0 (p)V ′ x [ f ](q) = 0. ( 19
)
The integration over q yields the dispersion relation

f (q, p; x) -f ′ 0 (p) e -λ q p p q q0 e λ q ′ p V ′ x [ f ](q ′ )dq ′ = 0, ( 20
)
where we have assumed the integration constant to be zero. The solution of this dispersion relation depends on the form of the local potential V x [f ]. If we restrict to the derivation of the stability threshold, we can set λ = 0 in the previous expression and perform the integral over q ′ , which gives f (q, p; x) -

f ′ 0 (p) p V x [ f ](q, p; x) = 0. ( 21
)
This is indeed a set of equations for each position x, all coupled together by the V x [ f ] term. Now, since we have considered a lattice with periodic boundary conditions, it is natural to introduce the Fourier operator

F k [ f ](q, p) = 1 2π dx e -2iπkx f (q, p; x) = fk (q, p), (22)
and rewrite the distribution f as a sum of Fourier modes

f (q, p; x) = k fk (q, p)e 2iπkx . ( 23
)
The potential V x [ f ] exhibits the interesting property of being diagonal in Fourier space [39]. Indeed, inserting the sum (23) into the definition (8) results into

V x [ f ](q) = κ α k dx ′ e 2iπkx |x -x ′ | α (24)
× dq ′ dp ′ fk (q ′ , p ′ )v(q, q ′ ).

Recalling the definition of the nearest distance on the periodic lattice, the above integral over x ′ is actually performed from x -1/2 to x + 1/2, so that it is appropriate to introduce the change of variables x ′ → y = x ′ -x. One gets

x+1/2 x-1/2 dx ′ e 2iπkx ′ |x ′ -x| α = e 2iπkx +1/2 -1/2 dy e 2iπky |y| α = e 2iπkx c k (α) +1/2 -1/2 dy |y| α ,( 25
)
where c k (α) is defined as

c k (α) = κ α +1/2 -1/2 e 2iπky |y| α dy = +1/2 -1/2 e 2iπky |y| α dy +1/2 -1/2 1 |y| α dy . (26)
Equation ( 24) leads us to define the mean-field potential V (q) for a distribution g(q, p), which does not depend neither on α nor on the position on the lattice V [g](q) = dq ′ dp ′ g(q ′ , p ′ )v(q, q ′ ) .

Remark that in the limit α = 0, when the long-range potential V x in formula [START_REF] Nicholson | Introduction to Plasma Theory[END_REF] does not depend any more on the position x along the lattice, one has V [ f ] = dq ′ dp ′ f (q ′ , p ′ )v(q, q ′ ), exactly as in mean-field models. Equation ( 27) allows us to rewrite the dispersion relation (20)

as 0 = k fk (q, p)e 2iπkx - k ′ c k ′ (α)e 2iπk ′ x ×f ′ 0 (p) e -λ q p p q q0 e λ q ′ p V ′ [ fk ](q ′ )dq ′ .( 28
)
Thus, applying the inverse Fourier transform leads to the following set of decoupled dispersion relations for each Fourier mode fk

fk (q, p) -c k (α)f ′ 0 (p) e -λ k q p p q q0 e λ k q ′ p V ′ [ fk ](q ′ )|dq ′ | = 0. ( 29
)
The quantity λ k represents the eigenvalue associated to mode k. It is interesting to note that, although the solution of these equations will generically depend on the specific form of the potential V [f ], the dependence on the specific Fourier mode only appears through the coefficient c k (α). We shall see in the next Section that this allows us to derive the growth rate for all Fourier modes in the case of the α-HMF model.

STABILITY THRESHOLDS AND GROWTH RATES FOR THE α-HMF MODEL

As a test-bed for systems of rotators on a ring-lattice with long-range couplings, we now turn to analyzing the dispersion relations for each Fourier mode of the α-HMF model [18][19][20][21]. The rotators are thus coupled through a two-body potential v(q, q ′ ) = -cos(q -q ′ ), which is tuned down by a decay over the distance along the lattice 1/|x -x ′ | α . The potential V , defined in Eq. ( 27) reads

V [ f ](q) = -κ α M x [ f ] cos q + M y [ f ] sin q , ( 30
)
where the magnetization M [ f ] is defined as

M[ f ] = M x [ f ] + iM y [ f ] (31) = dq ′ dp ′ f (q ′ , p ′ ) cos q ′ + i dq ′ dp ′ f (q ′ , p ′ ) sin q ′ . Equation (29) turns into 0 = fk (q, p) -c k (α)f ′ 0 (p) e -λ k q p p (32) × q q0 e λ k q ′ p M x [ fk ] sin q ′ -M y [ fk ] cos q ′ |dq ′ |.
This equation can be solved by multiplying both sides by either cos q or sin q and integrating over the phasespace (q, p), which leads to a linear system of equations in M x [ fk ] and M y [ fk ]

M x [ fk ] 1 -c k (α)I λ k X,Y [f 0 ] + M y [ f ]c k (α)I λ k X,X [f 0 ] = 0, M x [ fk ]c k (α)I λ k Y,Y [f 0 ] -M y [ f ] 1 + c k (α)I λ k Y,X [f 0 ] = 0, ( 33
)
where I λ X,Y [f 0 ] is defined, for a scalar λ and two functions X(q), Y (q) (here X(q) = cos q and Y (q) = sin q), as

I λ X,Y [f 0 ] = dp f ′ 0 (p) p dq e -λ q p X(q) q q0
dq ′ e λ q ′ p Y (q ′ ).

(34) Assuming that eigenmodes f have a non-zero magnetization, the system of equations (33) implies

0 = 1 -c k (α)I λ k X,Y [f 0 ] 1 + c k (α)I λ k Y,X [f 0 ] +c k (α) 2 I λ k Y,Y [f 0 ]I λ k X,X [f 0 ]. ( 35
)
Using the following formulae

q dq ′ e λ k q ′ p sin q ′ = e λ k q p 1 + λ k 2 p 2 λ k p sin q -cos q , ( 36
)
q dq ′ e λ k q ′ p cos q ′ = e λ k q p 1 + λ k 2 p 2 sin q + λ k p cos q , ( 37
)
one can calculate the integrals [START_REF] Bachelard | Stability of inhomogeneous states in mean-field models with a local potential[END_REF], so that dispersion relation ( 35) can be finally rewritten as

0 =   1 + πc k (α) dp f ′ 0 (p) p 1 + λ k 2 p 2   2 +   πc k (α) dp f ′ 0 (p) p 2 1 + λ k 2 p 2   2 . ( 38
)
Note that in this relation only the coefficient c k (α) changes from one Fourier mode to another.

Let us now consider a waterbag distribution [START_REF] Yamaguchi | [END_REF]

f 0 (p) = 1 2π 1 2∆p (Θ(p + ∆p) -Θ(p -∆p)) , (39)
where Θ is the Heavyside function. It's first derivative is

f ′ 0 (p) = 1 2π 1 2∆p (δ(p + ∆p) -δ(p -∆p)) , (40)
where δ is the Dirac delta function. Since this distribution is symmetric in p, the last term in Eq. ( 38) vanishes, and the dispersion relation simplifies into

0 = 1 + πc k (α) dp f ′ 0 (p) p 1 + λ k 2 p 2 = 1 - c k (α) 2∆p 2 1 + λ k 2 ∆p 2 . ( 41
)
Thus, the eigenvalue of the k-th Fourier mode is given by

λ k = c k (α) 2 -∆p 2 . (42)
Hence, mode k is stable provided ∆p 2 ≥ c k (α)/2. If instead ∆p 2 < c k (α)/2 the mode is unstable and grows with the rate Re(λ k ).

NUMERICAL SIMULATIONS

We shall now compare the predictions of the previous Section concerning the stability of the waterbag initial state for the α-HMF model with numerical simulations. We integrate the equations of motion (4,5) using an optimized fourth-order symplectic scheme [38] with time step 0.1, which guarantees a good conservation of the energy during time evolution. We do not need here to perform long-time evolutions, because we have just to look at the initial growth of the Fourier modes. Hence, we can push as much as we can towards larger values of N : we report here simulations with N up to 2 18 . The reason for choosing a power of 2 for N is that we use a Fast Fourier Transform algorithm in order to compute the force in Fourier space: this allows us to perform simulations in O(N ln N ) time instead of the O(N 2 ) time needed to compute the double sum over the sites of the lattice. We recall that for the α-HMF model v(q j , q k ) = -cos(q j -q k ) and we choose here α = 0.8.

The system is initiated by spreading the particles randomly in the rectangle [0; 2π] × [-∆p; ∆p] in the phase space (q, p) attached to each site of the lattice. The time evolution of each harmonic of the magnetization is followed using the observable m k = e -ikx e iq f (q, p; x, t)dq dp (43)

= 1 N j e -ikxj e iqj . (44)
The simulations allow us to observe an exponential growth of m k (t) (see Fig. 1(a,b)), with a rate that depends on the harmonic number k, as expected from formula (42). They also confirm that some higher harmonics may be stable while lower ones are unstable: for example, for ∆p = 0.65, formula (42) predicts that Fourier modes with k ≥ 1 should be stable. Simulations indeed reveal that for such a value of ∆p, mode k = 3 does not grow exponentially any more (see Fig. 1(b)).

Let us give some further informations about the time evolution of m k (t). The harmonics are initially at a level of order 1/ √ N , as expected from a random distribution. The very short-time dynamics (t < 2 for ∆p = 0) does not allow us to observe the exponential growth, presumably because there is still a strong competition between the numerous eigenmodes, be they stable or not. The most unstable mode eventually dominates, and it is observed that the exponential growth sets in for the time range 2 < t < 7 for ∆p = 0, which is almost the same for all the harmonics (the growth rate is calculated over this time window). Remark that for ∆p = 0.65, in Fig. 1(b), although the growth is very close to an exponential one for mode k = 0, it is not for k = 1, 2, 3, as predicted by the theory.

Finally, the results of a simulation with much less particles N = 2 12 are drawn in Fig. 1(c), to illustrate the finite-size effects. In this case the Fourier modes start for t = 0 at a much higher level, so that the growth occurs on a much shorter time window. It becomes then very hard to identify the exponential character of the growth.

In order to test more thoroughly the accuracy of the theoretical predictions, simulations for homogeneous waterbags with different values of ∆p were performed. In Fig. 2 we show the growth rates as a function of ∆p for different Fourier modes. The agreement between theory and simulations is excellent for the mean-field mode (k = 0), quite good for the two following modes k = 1, 2 but it gets worse as the harmonic number increases, especially for the larger values of ∆p. This phenomenon is possibly due to the fact that higher Fourier modes are more sensitive to finite-size effects. Finally, let us comment on the choice α = 0.8 for our test: as can be evaluated from Eq.( 42), the domains of instability of k ≥ 1 modes is very narrow for smaller values of α, so that a α close to unity was best to present a stability diagram showing clearly the successive extinction of the Fourier modes.

CONCLUSIONS

The main result of this paper is the derivation of the Vlasov equation for a lattice with long-range couplings. As an application, we have studied the stability of the linearized Vlasov equation for the α-HMF model, deriving a dispersion relation which is expressed in terms of Fourier modes .

We have computed the stability thresholds for the different Fourier modes and the growth rates when the modes are unstable. We have shown that the fastest growth rate is the one corresponding to the mean-field zero mode. This agrees with the widely spread opinion that the α-HMF model with 0 ≤ α < 1 behaves in all respects as the HMF model, which corresponds to the limit α = 0.

In order to support this conjecture, we have also tried to identify states where higher harmonics would dominate, performing numerical simulations in which the system is initialized in a state which is spatially modulated with a given wave-number in order to promote the time evolution of higher modes. In all cases, we have observed the growth of other modes, including the zero mode. This latter eventually takes the lead and dominates over the

others.

A more specific remarks concerns the amplitude c k (α of the Fourier modes of the potential, given in formula (26). In the limit α = 0 all the harmonics k > 1 van- ish, giving the potential in the mean-field limit, which corresponds to the one of the HMF model. On the other hand, when going toward the limit α → 1 from below, one gets c k (α) = 1 for all k's. This means that all the Fourier modes, and thus all the length scales, become equally relevant in this limit. For α = 1, the series of Fourier modes that represents the potential is no more summable and, as a consequence, the potential ( 8) is ill-defined: it's the signature that one is leaving the long-range region.

[39] Remark that, regarding numerical simulations of such systems, this property also allows one to compute the potential in Fourier space, thus reducing the a priori N 2 complexity of the double sum to the N ln N one of the Fast Fourier Transform.

Figure 1 :

 1 Figure 1: Time evolution of the Fourier modes of the magnetization m k (t) (44) for the α-HMF model. The initial waterbag distribution is uniform in q ∈ [0, 2π] and in p ∈ [-∆p, ∆p] with ∆p = 0 in panel (a) and ∆p = 0.65 in panels (b) and (c). For these values of ∆p the homogeneous waterbag is unstable. The Fourier modes m k are plotted vs. time for k = 0 (thick full line), k = 1 (thick dash-dotted line), k = 2 (thick dashed line) and k = 3 (thick dotted line). The thin lines are exponential fits. The two upper panels have N = 2 18 , while the lower panel has N = 2 12 and shows the strong finite-size effects: the exponential growth is no more clearly visible.

Figure 2 :

 2 Figure 2: Growth rates Re(λ k ) of the first Fourier modes of the magnetization as a function of ∆p. The initial conditions are homogeneous waterbags. The lines correspond to the theoretical prediction (42) for k = 0 (full),k = 1 (dash-dotted), k = 2 (dashed) and k = 3 (dotted). The results of numerical simulations are marked by the symbols (resp. •, * , × and ).For each value of ∆p ten runs were performed: the symbols represent the average, while the error bars stand for the minimal and maximal values. The symbols for k = 1 and k = 3 are slightly shifted in ∆p for the sake of clarity.

ACKNOWLEDGEMENTS

We thank D. Mukamel for suggesting this problem and for collaboration in a first stage on this project. This work was carried out in part while S.R. was Weston Visiting Professor at the Weizmann Institute of Science. This work is also part of the ANR-10-CEXC-010-01, Chaire d'Excellence project.