Alexis Canette
email: alexis.canette@jouy.inra.fr

Priscilla Branchu
email: priscilla.branchu@ifr.ac.uk

Régis Grimaud
email: regis.grimaud@univ-pau.fr

Murielle Naïtali Affiliation

Murielle Naïtali
email: murielle.naitali@agroparistech.fr

Imaging bacterial cellsand biofilms adhering to hydrophobic organic compounds-water interfaces Authors

Keywords: Hydrocarbons, lipids, adhesion, biofilm, oleolytic bacteria, CLSM, TEM

Assimilation of Hydrophobic Organic Compound (HOC) entails frequently the formation of biofilm at the HOC-water interface.Knowledge on the behavior of cells at the oil-water interface and within the structured biofilm is therefore important to understand the degradation of the HOC in ecosystems. The adhesion and biofilm formation on oil-water interface is best documented by microscopic observations. In this chapter we thus describe two methods for observation of bacterial cells and biofilms growing at the HOC-water interface. The first method uses CLSM (confocal laser scanning microscopy) to obtain in situ images of biofilm developing on thin paraffin strip which offers a flat transparent surface allowing imaging directly through the bottom of the culture dish without sampling.

Alternatively, the biofilm can be grown on a paraffin strip deposited on a glass microscope slide and then imaged from the top when high resolution is needed. The second method addresses the problematic of the ultrastructure of biofilm developing on HOC. It enables to obtain by TEM (transmission electron microscopy) images of cross sections of biofilms with identification of the side in contact with the HOC.

Introduction

Hydrophobic Organic Compounds (HOC), includingthe chemical classes of lipids and hydrocarbons are ubiquitous components of the organic matter in ecosystems. The so called oleolytic bacteria have the ability to use members of either one or both classes as a substrate [START_REF] Klein | Cytoplasmic wax ester accumulation during biofilm-driven substrate assimilation at the alkane-water interface by Marinobacter hydrocarbonoclasticus SP17[END_REF][START_REF] Tanaka | Acinetobacter sp. Ud-4 efficiently degrades both edible and mineral oils: isolation and characterization[END_REF].However, they have to face the very low water solubility of these substrates. Adhesion to the HOC-water interface and the subsequent formation of biofilms (3D-architectures of bacterial cells embedded within matrixes of biopolymers) are strategies shared by many oleolytic bacteria to overcome the low solubility of their substrates [START_REF] Bouchez-Naïtali | Diversity of bacterial strains degrading hexadecane in relation to the mode of substrate uptake[END_REF][START_REF] Grimaud | Biofilm development at interfaces between hydrophobic organic compounds and water[END_REF][START_REF] Mounier | The marine bacterium Marinobacter hydrocarbonoclasticus SP17 degrades a wide range of lipids and hydrocarbons through the formation of oleolytic biofilms with distinct gene expression profiles[END_REF]. Different mechanisms have been proposed for the stimulation of the rate of mass transfer from the oily phase to cell surface. The localization of cell in the vicinity of the interface results in reduction of the length of the diffusion pathway of the hydrocarbon from the interface to the cell surface which in turn increases the mass transfer rate (6). Extracellar matrixes of biofilms provide confined environments where biosurfactants can be accumulated and contribute to hydrocarbons uptake by substrate emulsification or pseudo-solubilization. A direct contact of bacteria with hydrocarbons is also possible via the modification of the cell surface (7)offering the possibility of direct uptake from the hydrocarbon-water interface, although this remained to be demonstrated. In the case of lipids which must undergo hydrolysis into fatty acids by extracellular lipases before uptake by the cell, adhesionand biofilm formation at the water-lipidinterface provide the advantage to retain together the exo-enzymes, the lipids, the hydrolysis productsand the cells thus preventing them from rapid transportation to bulk water. The behavior of cells at the oil-water interface and within the structured biofilm is therefore one important aspect of the degradation of the HOCs in ecosystems.

The adhesion and biofilm formation at the oil-water interface is best studied by microscopic observations. Although a huge number of HOCs degrading strains have been isolated over the past decades, adhesion of these strains to their substrate is rarely documented. Only few authors provided images of bacteria cells adhered to HOC-water interfaceusing light microscopy, scanning electron microscopyand confocal laser scanning microscopy (CLSM) [START_REF] Whyte | Physiological adaptations involved in alkane assimilation at a low temperature by Rhodococcus sp. strain Q15[END_REF][START_REF] Eriksson | Bacterial growth and biofilm production on pyrene[END_REF][START_REF] Wick | Responses of Mycobacterium sp. LB501T to the low bioavailability of solid anthracene[END_REF][START_REF] Rodrigues | Fluorene and phenanthrene uptake by Pseudomonas putida ATCC 17514: Kinetics and physiological aspects[END_REF][START_REF] Macedo | Three stages of a biofilm community developing at the liquid-liquid interface between polychlorinated biphenyls and water[END_REF][START_REF] Wouters | A noninvasive fluorescent staining procedure allows Confocal Laser Scanning Microscopy based imaging of Mycobacterium in multispecies biofilms colonizing and degrading polycyclic aromatic hydrocarbons[END_REF]. Studies of the behavior of bacteria at the HOC-water interface and within biofilms often involve examination and comparison of different strains (wild type versus mutants or different species).This can be only achieved if the HOC-water interfaces generated are compatible with the quantitative measurement of the adhesion or biofilm formation that is hardly the case with spherical or hemispherical droplets of HOC and crystals of irregular shape. To fulfill these requirements, we propose a methodology using thin films of paraffin (15 µm) to generate a substratum togrow biofilms. Ultrathin paraffinfilmsare obtained by slicing solid paraffin with a microtome. Paraffin films pasted to the bottom of a culture dishoffer a flat surface and are thin enough to allow in situobservation through the bottom of the culture dish avoiding thus disruption of the biofilm structure. A better definition of imaging can be obtained using a microscope glass slide as solid substratum to paste the paraffin; the biofilm is then observed upside-down through a coverslip.

Determination of the ultrastructure of biofilms adhered to HOC-water interface are also of great interest. In general, biofilm cells exhibitheterogeneity in their physiology which can be reflected by the presence of different morphotypes. In the case of biofilm developing on hydrocarbons,intracellular inclusions of storage lipids have been often observed [START_REF] Manilla-Perez | Analysis of lipid export in hydrocarbonoclastic bacteria of the Genus Alcanivorax: Identification of lipid export-negative mutants of Alcanivorax borkumensis SK2 and Alcanivorax jadensis T9[END_REF].For instance, biofilm cells of Marinobacter hydrocarbonoclasticusSP17 growing on hexadecane accumulate wax ester in their cytoplasm. These storage lipids persistafter detachment from the biofilm and provide cells with energy for colonization ofunoccupied interfaces (15). Lipid inclusions can be investigated using CLSM using specific fluorescent dye (figure 1). However, the ultrastructure of growing cells on HOCs is best studied using transmission electron microscopy (TEM) [START_REF] Klein | Cytoplasmic wax ester accumulation during biofilm-driven substrate assimilation at the alkane-water interface by Marinobacter hydrocarbonoclasticus SP17[END_REF][START_REF] Kalscheuer | Analysis of storage lipid accumulation in Alcanivorax borkumensis: Evidence for alternative triacylglycerol biosynthesis routes in bacteria[END_REF]. The distribution and arrangement of cells containing inclusions within the biofilm can be investigated by TEMprovided that the biofilm structure is preserved and the orientation of the biofilm in respect to the HOC surface is traceable. Here, we describe a method where the biofilm is grown in a petri dish whose the bottom has been coated with paraffin. TEM requires sectioning the biofilm included in epoxy resin. As paraffin is incompatible with epoxy resin, the biofilm is removed from the paraffin surface by embedding it in agarose. Then agarose pieces are processed for TEM by paying attention to keep track of the side bearing the biofilm. This procedure enables to obtain images of cross sections of biofilms with identification of the side in contact with the paraffin. The imaging methods were both applied on a marine gram negative bacterium, Marinobacter hydrocarbonoclasticusSP17 and on a gram positive bacteriumRhodococcus equi NapRu1. 16. HT7700 transmission electron microscope (Hitachi, Japan) equipped with an8 million pixels format CCD camera driven by the image capture engine software AMT version 6.02. Strips must be transported on ice (for example in a Petri dish) then stored at 4 °C until use.A thin strip of paraffin is placed on a microscopeglass slide within a Petri dish (90 mm) or directly on the bottom of a Petri dish (55 mm). Put the Petri dish in an incubator at 45 °C for 10 min to soften the paraffin and make it adhere to the solid support. Before use, decontaminate by exposing the Petri dishtoUV lightfor 5 min.

Materials

Observation of biofilms grown on paraffin by CLSM

Methods

3.1Observation of biofilms grown on paraffin by CLSM

2.Inoculate the solid support

Pour 30 mL of the bacterial suspension (OD 600nm =0.01) in the Petri dish (90 mm) containing the thin paraffin stripstuck on a microscopic slide or 5 mL in a Petri dish (55 mm) containing the thin paraffin strip stuck on the bottom. Make sure thatthe bacterial suspension covers the whole surface of the solid substratum.Incubate at 30° C without shaking for 5 days (Note 14). Remove the culture medium leaving about 1 mL to keep the biofilm wet. It is important to avoid dehydration to conserve the biofilm structure. Add the selected fluorescent makers to the recommended concentration (see manufacturer's instructions) and incubate at room temperature in dark for 15 min. Here, either Syto®9 (diluted 1:1000) or the mixture Syto®61 (1:1000)/BODIPY® (final concentration 0.05 mg.mL -1 ) are used.

2.Biofilm observation

Biofilms grown on paraffin thin film deposited on the bottom of the petri dish are imaged directly, without mounting, through the bottom of the Petri dish with an inverted microscope. This approach is preferred when biofilms are loosely attached to paraffin and mounting would result in loss in the biofilm integrity. However, if a maximal resolution is desired, the biofilm is grown on paraffin film pasted on a microscope slide. Then the biofilm is mounted between the slide and a coverslip with a silicon spacer to avoid compressing it and observed upside down on the inverted microscope.Biofilms mounted or not are observed with a water immersion HCX APO L, 0.80 NA, W U-V-I, Leica 40 X objective with a working distance of 3.3 mm.Adjust the laser excitation and fluorescence signal recuperation according to the characteristic of the markers (absorption and fluorescence emission maxima Syto®9 482/500 nm, Syto®61 628/645 nm, BODIPY® 493/503 nm).

3.Aquire xy image or 3D xyz-stack and process the image series using IMARIS 7.7.2 software and Fiji (Figure 1).

3.2Observation of biofilms grown on paraffin by TEM

The basic principles and techniques of electron microscopy for biological applications are described elsewhere [START_REF] Hayat | Principles and Techniques of Electron Microscopy -Biological Applications[END_REF]. This protocol is designed to visualize more specifically the spatial distribution in the biofilm of cells containing intracytoplasmic inclusions. In order to visualize the extracellular matrix, bacterial capsules or appendixes, other fixative cocktails and other electron microscopy techniques have to be used (19, 20).

Pre-culture of bacteria

See subheading 3.1.1.

Biofilm culture

1.Coat the bottom of petri dishes with paraffin by pouring 15 mL of liquid paraffin heated at 50 °C.

Let the paraffin solidify by cooling at room temperature.

2.Twenty milliliters of bacterial suspension prepared as described in 3.1.1 areused to inoculate the paraffin coated Petri dishes. Make sure that the whole surface of the solid paraffin is covered by the cell suspension.Incubate at 30 °C without shaking for 5 days (Note 14).

TEM observation of the biofilm

To prevent dehydration, the samples must be kept immersed in solution during the allprocedure, except for step 3. During the change of solutions, it is therefore recommended to not discard all the solution from the previous step. Addition and removal of solutions must be performed with extreme care to avoid biofilm alteration. Be aware of the toxicity of the compounds used (Note 16).

1.Fix the biofilm

Remove the culture medium from the petri dish and pour 20 mL of the fixative solution, incubate at room temperature for 1 h. The cacodylate buffer concentration in fixative solution is 0.15 mol.L -1 for M. hydrocarbonoclasticusSP17 and 0.10 mol.L -1 for R. equi NapRu1. At this stage samples can be stored few months in the fixative solution, at 4°C. Wash three times during 5 min with the cacodylate bufferat the corresponding concentration.

2.Post-fix the biofilm

Remove the fixative solution,add 20 mL of post-fixative solution and incubate at room temperature for 1 h. Wash twice for 10 min in distillated water. At this stage samples can be stored few days maximum, at 4 °C.

3.Embed the biofilm in agarose

Discard the distilled water and quickly embed the fixedbiofilm in 30 mL of a 2.5% agarose solution maintained above its gelling point at 50 °C (Note 9). Tilt the Petri dish and carefully swirl the melted agarose to obtain a homogenous surface. Let the agarose gellify for1 h at 4 °C.

Detach the agarose gel from the petri dish wall by moving all around the edges of the dish a thin blade inserted between the agarose and the dish wall. Unmold carefully the agarose by detachingit from the paraffin. The biofilm normally separates easily from the paraffin staying in the agarose layer.

Checkvisually that all the biofilm has been removed from the surface of the paraffin.Transfer the agarose slab, biofilm facing down, in a Petri dish containing the first solution of dehydration (30% ethanol). Make sure that the biofilm bearing face is always immersed in the solution. Cut the agarose slab into big pieces(1 cm 3 ) with a scalpel and choose pieces where the biofilm seems thicker and homogeneous.

4.Dehydrate the agarose pieces in ethanol solutions series: 50%, 70%, 90% and 2x100% v/v, 15 min for each step at room temperature. Removal and addition of ethanol solution must be carried out with care to not damage the biofilm. Dehydration procedure can be stopped at the stage of 70% ethanol.

Samples are stable for few days maximum, at 4°C. After dehydration reduce the thickness of the agarose layer above the biofilm to 1 mm and cut small pieces of 3 mm long by 1 mm wide. Transfer each piece in an Eppendorf™ microcentrifuge tube containing 700 µL of a 100% ethanol (third bath).

5. Impregnate successively the dehydrated samples with epoxy resin solutions in ethanol of increasing concentrations: 25% and 33% for 10 min, 50% overnight, then 66% and 75% for 10 min.

Impregnations are performed at room temperature under rotary shaking (Notes 17and 18).Then impregnate with pure (100%) fresh resin, for 10 min up to few hours, with the caps of the microcentrifuge tubes opened to let evaporate the last traces of ethanol. Impregnate once more with pure fresh resin overnighton rotary shaking.Finally, impregnate with pure fresh resin with the caps of the microcentrifuge tubes opened inunder vacuum to maximize resin penetration (from 10 min to few hours). After dehydration and impregnation the biofilm bearing face of agarose pieces can be easily recognized by their black coloration.

6.Include samples in epoxy resin.

Pour a thin layer of pure fresh epoxy resin into TEM moldsand allow to polymerize for 2 hat 60 °C.

Place each impregnated sample, in a mold, on the top of the polymerized epoxy layer in such a way that the biofilm black layer is below and parallel to the bottom of mold. The viscous thin layer of resin in the bottom of the mold will help to stabilize the sample during polymerization (Note 19).

Fill completely the cavity with pure fresh epoxy resin, considering volume reduction during polymerization. Put the mold under vacuum for 10 min up to few hours to maximize resin penetration and eliminate air bubbles.Polymerize at 60 °C, during 16 to 18 h, depending on the resin hardness preferred for the cutting. Resin blocks can be stored ad vitam aeternam in a temperate and dry place. 8.Observe in a TEM microscope between 80 to 120 kV (Figure 2). Contrast increases when accelerating voltage is decreased and objective aperture is more closed (21).

Notes

Note 1. Although this method was originally developed for M. hydrocarbonaclasticus SP17 and R. equi NapRu1, it can be adapted, by using the appropriated culture medium, to any strain that is able to form biofilm on paraffin or other HOCs, hydrocarbon or lipidsthat are solid at the growth temperature.

The HOC must be soft enough to be cut in very thin slices. Crystalized compounds (such as pure alkanes or aromatics) are not suitable since they are not sliceable. Note 2. Any other medium that allows the studied strain to grow,adhere and form biofilm on HOCcan be employed. Note 3. Classical Petri dishes are employed. Other diameters can be used. If the biofilm is observed directly through the bottom of the dish, specific Petri dishes with a bottom designed for high-end microscopic analyses have to be used (µ-Dish50 mm, low, Ibidi) for higher resolution imaging. Note 9. The agarose solution is maintained at the liquid state at a temperature above its gel point but not too high to avoid the paraffin from melting or any damage to the biofilm. Note 10. This resin is prepared accordingly to the manufacturer's instructions, aliquotedand stored at -20°C. Only the bottom of the R. equi NapRu1 biofilm (i.e. the side in contact with paraffin during growth) is shown as the biofilm is very thickwith no stratification within the ultrastructure of cells. The R. equi NapRu1biofilm (Fig. 2B) contain few cells, as compared with the M. hydrocarbonoclasticusSP17 biofilm (Fig. 2A), and probably a lot of extracellular matrix. Numbers of cells of M. hydrocarbonoclasticusSP17 contained big inclusions in contrast to R. equi NapRu1cells. These observations are in agreement withCLSM imaging (Fig. 1B,D).

2. 1 . 1 2 .

 112 Strains, culture media and substratum for biofilm growth 1.The protocol described here has been developed with the bacterial strainsM. hydrocarbonaclasticus SP17[START_REF] Gauthier | Marinobacter hydrocarbonoclasticus gen. nov., sp. nov., a new, extremely halotolerant, hydrocarbondegrading marine bacterium[END_REF]and R.equiNapRu1 (3) (Note 1) 2.Synthetic Sea Water (SSW): NaCl 0,2 mol.L -1 , KCl 10 mmol.L -1 , Tris-HCl 50 mmol.L -1 pH 7,8, NH 4 Cl 56 mmol.L -1 , K 2 HPO 4 427 μmol.L -1 , FeSO 4 8 μmol.L -1 , MgSO 4 65 mmol.L -1 et CaCl 2 13 mmol.L -1 ) (Note 2) 3. Sodium lactate 2 mol.L -1 adjusted to pH 7 4. Paraffin Normal Q Path® (VWR International, France) 5. Petri dishes (55 and 90 mm diameter) (Note 3) 6. Washed glass microscopic slides(25x75 mm) (Note 4) 7. Ultramicrotome (UC6, Leica microsystems, Germany) 2.1.2 CLSM observation of the biofilm 1.Fluorescent dye: Syto®9 (L-10316, Life Technologies, France), Syto®61 (S-11343, Life Technologies), BODIPY® (D-3922, Life technologies) (Note 5) 2. Glass coverslips N° 1.5 (Knittel Gläser, Germany) 3. Silicon spacer for coverslip, Press-to-Seal™, 1 mm thick (Invitrogen™, Life Technologies) 4.Inverted Confocal Laser Scanning Microscope, Leica TCS SP8 AOBS (Leica Microsystems, Germany) (Note 6) 5. Image analysis software IMARIS 7.7.2 software (Bitplane, Switzerland) and Fiji (Fiji.sc/Fiji)(Note 7) 2Observation of biofilms grown on paraffin by TEM 2.2.1 Strains, culture media and substratum for biofilm growth See subheading 2.1.1 2.2.2 TEM observation of the biofilm 1. Sodium cacodylate buffer 0.15 or 0.1 mol.L -1 , pH 7.4 (Sigma-Aldrich, France) (Note 8). The pH is adjusted with HCl 2.Fixative solution (preparedextemporaneously): 2.5% glutaraldehyde (from glutaraldehyde solution Grade I, 25% in H 2 O, Sigma-Aldrich) in 0.15 M sodium cacodylate buffer at pH 7.4 or 0.10 M sodium cacodylate buffer at pH 7.4 (Note 8) 3.Post-fixative solution (preparedextemporaneously): 1% osmium tetroxide (Electron Microscopy Sciences, France) in 0.15 M sodium cacodylate buffer at pH 7.4 or 0.10 M sodium cacodylate buffer pH 7.4 (accordingly to the fixative solution) 4.2.5% agarose solution in distilled water (Seakem® LE agarose, Lonza, France).Agarose solution must be maintained at 50 °Cinan incubator for example(Note 9) 5.Ethanol 99.8% (AnalaR NORMAPUR, VWR International) 6.Fresh or thawed epoxy resin (R1165, Low Viscosity Resin -Medium grade, Agar Scientific, France) (Note 10) 7.A filtered solution of 0.05% oolong tea extract (OTE) in distillated water (OTE, Eloïse, France) (Note 11) 9.Whatman® grade n°1 cellulose filter paper (Sigma-Aldrich) 10.2 mL Eppendorf®microcentrifuge tubes (Eppendorf, France) (Note 12) 11.Rotator for Eppendorf microcentrifuge tubes 12.Vacuum desiccator 13.Diamond knife for ultrathin sectioning (35 ° angle, DU3520 Diatome 2 mm) and ultramicrotome (UC6, Leica microsystems, Germany) 14.200 and 300 mesh copper grids (G200-Cu and G300-Cu, Electron Microscopy Sciences) 15.Flat embedding molds for TEM (70900 silicone clear Electron Microcopy Sciences or 70907 Dykstra blue, Electron Microscopy Sciences) (Note 13)

3. 1 . 1 .

 11 Pre-culture of bacteria 1.Inoculate 100 µL of a glycerol stock of bacteria (strain SP17 or NapRu1) stored at -80 °C into 10 mL of SSW supplemented with 20 mmol.L -1 sodium lactate as a carbon source in a 50 mL tubeand incubate overnight at 180 rpm, 30 °C.2.Transfer 100 µL of the culture in 10 mL of SSW plus 20 mmol.L -1 sodium lactate andincubate overnight at 180 rpm, 30 °C.3.Centrifuge the overnight culture at 20 °C, 10 000 g for15 min, wash the cell pellet twice in SSW and resuspend the cells in SSW at an OD 600nm =0.01.3.1.2. Biofilm culture 1. Prepare the substratumMelt the paraffin at 65 °C and pour it into cassettes for microtome. Let the paraffin cooled-down on a cool top board to allow solidification. Cut the solid paraffin with a microtome in 15 µm thick strips.

3. 1 . 3 .

 13 CLSM observation of the biofilm 1.Biofilm staining with fluorescent markers (Note 15)

7 .

 7 Make ultrathin sections (60 to 80 nm) with a diamond knife and an ultramicrotome. Deposit on 200 or 300 mesh copper grids (Note 20). Stain each grid with onedrop of 0.05% OTE solution for 30 min, washed with 4 successive drops of distilled water and dried on Whatman grade n°1 cellulose filter paper.

Note 4 .

 4 Microscopic slides and coverslips are cleaned by acetone/ethanol (50/50 V/V), dried and stored in sterile conditions in Petri dishes until used. Note 5. Syto®9 (green fluorescent dye) and Syto®61 (red fluorescent dye) are nucleic acid stains and nonpolar BODIPY® (green fluorescent dye) labels neutral and non-polar lipid components. Other fluorescent dyes can be used according to the structures to be observed as previously described (22). Note 6. The use of an inverted CLSM is required to observe directly biofilms in situ without perturbing their architecture during staining and mounting. Note 7. Various softwares can be used as previously described (22). Note 8. Adapt and control the osmolarity of the buffer for each type of sample.

Figure 1 .

 1 Figure 1.Observation of paraffin-grown biofilms by CLSM

Figure 2 .

 2 Figure 2.TEM observation of M. hydrocarbonoclasticus SP17 (A) and R. equiNapRu1 (B).

Acknowledgement

We thank the MIMA2 platform (www.jouy.inra.fr/mima2) for its expertise and access to microscopy equipments.

 Note 11. OTE is a non-hazardous reagent used instead of the hazardous uranyl acetate(23). Note 12. Smaller microcentrifuge tubes are not suitable for dehydration and next steps. They can be adapted in case of troubles during the sample cutting (block too soft to an ultrathin cut, dissolution of the ultrathin section in the water tank of the knife) or during TEM observations (holes visible in the ultrathin section). Other standardized protocols describing impregnation steps with other resins can be found (24). Note 19. When placing the samples into the cavities of the molds, it is possible to reference them by adding a small paper with a printed code (pen ink diffuses in the resin) on the opposite side of the sample. Note 20. Use the lowest possible mesh copper grids to maximize the observation area (i.e. 200 mesh copper grids). Use 300 mesh copper grids for unstable sections under electron beam.


Guillaume Rollin

José Lages

Dima L Shepelyansky

Fractal structures for the Jacobi Hamiltonian of restricted three-body problem

Keywords: Chaos, Celestial mechanics, Binaries, Galaxies: spiral

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The restricted three-body problem was at the center of studies of dynamics in astronomy starting from the works of [START_REF] Euler | Theoria motuum lunae, nova methodo pertractata una cum tabulis astronomicis[END_REF], [START_REF] Jacobi | Sur le mouvement d'un point et sur un cas particulier du problème des trois corps[END_REF] and [START_REF] Poincaré | Sur le problème des trois corps et les équations de la dynamique[END_REF]. The progress in the understanding of this complex problem in XXth and XXIth centuries is described in the fundamental books [START_REF] Szebehely | Theory of orbits. The restricted problem of three bodies[END_REF][START_REF] Hénon | Generating Families in the Restricted Three-body Problem[END_REF][START_REF] Hénon | Generating Families in the Restricted Three-Body Problem: II. Quantitative Study of Bifurcations[END_REF][START_REF] Valtonen | The Three-Body Problem[END_REF]. As it was proven by [START_REF] Poincaré | Sur le problème des trois corps et les équations de la dynamique[END_REF] in the general case this system is not integrable and only the Jacobi integral is preserved by the dynamics [START_REF] Jacobi | Sur le mouvement d'un point et sur un cas particulier du problème des trois corps[END_REF]. Thus a general type of orbits has a chaotic dynamics with a divided phase space where islands of stability are embedded in a chaotic sea [START_REF] Chirikov | A universal instability of many-dimensional oscillator systems[END_REF][START_REF] Lichtenberg | Regular and chaotic dynamics[END_REF][START_REF] Ott | Chaos in Dynamical Systems[END_REF].

In this work we consider the Planar Circular Restricted Three-Body Problem (PCRTBP). This is an example of a conservative Hamiltonian system (in a synodic or rotating reference frame of two binaries) with two degrees of freedom. However, this is an open system since some trajectories can escape to infinity (be ionized) so that the general theories of leaking systems [START_REF] Altmann | Leaking chaotic systems[END_REF] and naturally open systems (e.g. [START_REF] Contopoulos | Escapes and recurrence in a simple hamiltonian system[END_REF]) find here their direct applications. It is known that such open systems are characterized by strange repellers related to non-escaping orbits and by an exponential time decay of probability to stay inside the system. However, as we show, in the PCRTBP system with a divided phase space one generally finds an algebraic decay of probability of stay related to an algebraic statistics of Poincaré recurrences in Hamiltonian systems (see e.g. [START_REF] Chirikov | Statistics of Poincare recurrences and the structure of the stochastic layer of a nonlinear resonance[END_REF][START_REF] Karney | Long-time correlations in the stochastic regime[END_REF][START_REF] Chirikov | Correlation properties of dynamical chaos in Hamiltonian systems[END_REF][START_REF] Meiss | Markov-tree model of intrinsic transport in Hamiltonian systems[END_REF][START_REF] Chirikov | Asymptotic statistics of Poincaré recurrences in Hamiltonian systems with divided phase space[END_REF][START_REF] Cristadoro | Universality of algebraic decays in Hamiltonian systems[END_REF][START_REF] Shevchenko | Hamiltonian intermittency and Lévy flights in the three-body problem[END_REF]Frahm, K. M. and Shepelyansky, D. L., 2010, and Refs. therein). This Email addresses: rollin@obs-besancon.fr (G. Rollin), jose.lages@utinam.cnrs.fr (J. Lages), dima@irsamc.ups-tlse.fr (D. L. Shepelyansky) effect appears due to long sticking of trajectories in a vicinity of stability islands and critical Kolmogorov-Arnold-Moser (KAM) curves. Thus an interplay of fractal structures and algebraic decay in the PCRTBP deserves detailed studies.

Among the recent studies of the PCRTBP we point out the advanced results of [START_REF] Nagler | Crash test for the Copenhagen problem[END_REF][START_REF] Nagler | Crash test for the restricted three-body problem[END_REF] where the crash probability dependence on the size of large bodies has been studied and the fractal structure of non-escaping orbits has been seen even if the fractal dimensions were not determined. This research line was extended in [START_REF] Astakhov | Capture and escape in the elliptic restricted three-body problem[END_REF]; [START_REF] Astakhov | Formation of kuiper-belt binaries through multiple chaotic scattering encounters with low-mass intruders[END_REF] with a discussion of possible applications to the Kuiper-belt and analysis of various types of orbits in [START_REF] Barrio | Periodic, escape and chaotic orbits in the Copenhagen and the (n + 1)-body ring problems[END_REF]; [START_REF] Zotos | Crash test for the Copenhagen problem with oblateness[END_REF]. The analysis of orbits in three dimensional case is reported in [START_REF] Makó | Stable and unstable orbits around Mercury[END_REF] and basin of escaping orbits around the Moon has been determined in de [START_REF] De Assis | Escape dynamics and fractal basin boundaries in the planar earthmoon system[END_REF].

In this work we determine the fractal dimension of nonescaping orbits for the PCRTBP with comparable masses of heavy bodies and consider the properties of Poincaré recurrences and the decay probability of stay in this system. The system description is given in Section 2, the structure of strange repeller is analyzed in Section 3, the decay of Poincaré recurrences and probability of stay are studied in Section 4, a symplectic map description of the dynamics is given in Section 5, discussion of the results is presented in Section 6.

System description

The PCRTBP system is composed of a test particle evolving in the plane of a circular binary whose primaries have masses m 1 = 1 -µ and m 2 = µ with m 1 > m 2 . In the synodic frame the dynamics of the test particle is given by the Hamiltonian where x and y are the test particle coordinates, p x = ẋy and p y = ẏ + x are the corresponding canonically conjugated momenta, and

H(p x , p y , x, y) = 1 2 p 2 x + p 2 y + yp x -xp y + V(x, y) (1)
V(x, y) = - (1 -µ) (x -µ) 2 + y 2 1/2 - µ (x + (1 -µ)) 2 + y 2 1/2 (2)
is the gravitational potential of the two primaries. Here the distance between primaries is 1, the total mass m 1 + m 2 = 1, the gravitational constant G = 1, consequently the rotation period of the binary is 2π. Hamiltonian (1) with potential (2) represents the Jacobi integral of motion [START_REF] Jacobi | Sur le mouvement d'un point et sur un cas particulier du problème des trois corps[END_REF]. In the following we define the Jacobi constant as C = -2H. This Jacobi Hamiltonian describes also the planar dynamics of an electrically charged test particle experiencing a perpendicular magnetic field and a classical hydrogen-like atom with a Coulomblike potential (2).

We aim to study the dynamics of particles evolving on escaping and non-escaping orbits around the binary. We perform intensive numerical integration of the equations of motion derived from Hamiltonian (1) using an adaptive time step 4th order Runge-Kutta algorithm with Levi-Civita regularization in the vicinity of the primaries [START_REF] Levi-Civita | Sur la régularisation du problme des trois corps[END_REF]. The achieved accuracy is such as the integral of motion relative error is less than 10 -9 (10 -5 ) for more than 91% (99%) of integration steps. For different Jacobi constants C, we randomly inject up to 10 8 test particles in the 1.3 ≤ r ≤ 2.5 ring with initial radial velocity ṙ = 0 and initial angular velocity φ < 0 (r and φ are polar coordinates in the synodic frame). Each test particle trajectory is followed until the integration time attains t S = 10 4 or until the region r > R S = 10 is reached where we consider that test particles are escaped (ionized) from the binary.

Strange repeller structures

In phase space, orbits are embedded in a three-dimensional surface defined by the Jacobi constant C. In order to monitor particle trajectories we choose a two-dimensional surface defined by an additional condition. Here we choose either the condition (ṙ = 0, φ < 0) to represent Poincaré section as a (x, y)plane (Figs. 1,5,6,7 and 10) or the condition (y = 0, p y > 0) to represent Poincaré section as a (p x , x)-plane (Fig. 2). A similar approach was also used in [START_REF] Nagler | Crash test for the Copenhagen problem[END_REF][START_REF] Nagler | Crash test for the restricted three-body problem[END_REF].

We show in Fig. 1 (panels a, b, c) an example of (x, y) -Poincaré section of the Jacobi Hamiltonian (1) for mass parameter µ = 0.3 and Jacobi constant C = 3. Red regions correspond to forbidden zones where particles would have imaginary velocities. Inside central islands in the close vicinity of primaries blue points mark out regular and chaotic orbits of bounded motion. In particular, the KAM invariant curves [START_REF] Lichtenberg | Regular and chaotic dynamics[END_REF]) can be seen e.g. in Fig. 1c. In Fig. 1a, the trace of non-escaped chaotic orbits (black points) remaining inside the disk r < R S = 10 after time t = 10 defines a set of points forming two spiral arms centered on the binary center of mass. This set has a spiral structure of strange repeller since orbits in its close vicinity rapidly move away from the set and consequently from the binary. The fractal property results in a self-similar structure clearly seen by zooming to smaller and smaller scales (see Fig. 1a,b,c). This fractal structure remains stable in respect to moderate variation of mass ratio µ as it is illustrated in Fig. 1 The fractal dimension of the strange repeller is determined using box-counting method [START_REF] Lichtenberg | Regular and chaotic dynamics[END_REF][START_REF] Ott | Chaos in Dynamical Systems[END_REF] as D = lim b→0 ln N b / ln (1/b) where N b is at scale b the number of at least once visited boxes in the Poincaré section. The box-counting fractal dimension of the strange repeller presented in Fig. 1a, b, c is D ≈ 1.87 (Fig. 3a). This fractal dimension value is computed from the strange repeller structure formed by orbits staying in the disk r < R S = 10 after time t = 10. We see from Fig. 3 that the fractal dimension remains practically the same for the parameters considered here µ = 0.3, 0.4 and C = 2.6, 3, 3.4. When the escape radius is increased up to R S = 100 (Fig. 4) the fractal dimension value is the same as for an escape radius R S = 10 (Fig. 3). Thus the obtained value of D is not affected by the escape cut-off distance R S . Also, as seen in Fig. 4, the fractal dimension remains practically the same if we consider strange repeller structures obtained after time t = 3, 10, 30 and 50. Hence even for short times the strange repeller structure is already well defined and perdures for greater times since D is constant (at least here up to t = 50). Throughout this work, for the sake of clarity we choose to present Poincaré sections for orbits staying in the r < R S = 10 disk after time t = 10. Fig. 5 shows (x, y) -Poincaré sections for the mass parameter µ = 0.3 and for different Jacobi constants from C = 2.6 to C = 4. The strange repeller structure constituted by nonescaping orbits is progressively expelled from the primaries vicinity as C increases. At C = 2.6, 3, 3.2, 3.4 (Fig. 5a,b,c,d) non-escaping trajectories may still pass close by each one of the primaries. The strange repeller still dominates the phase portrait with a fractal dimension decreasing down to D ≈ 1.84 for C = 3.4 (Fig. 3d). For greater values C = 3.6, 4 (Fig. 5e,f ) the forbidden zone insulates the immediate vicinity of the primaries from trajectories coming from regions beyond r ∼ 1. Regular and chaotic trajectories corresponding to particles gravitating one or the two primaries are confined in the very central region [START_REF] Valtonen | The Three-Body Problem[END_REF]. The strange repeller is confined in a narrow ring located in the region r ∼ 1.5. Beyond that region we observe nearly stable circular orbits (blue dots) corresponding to particles gravitating the whole binary with a radius r ∼ 2. For these orbits stable means that these orbits have not escaped from the disk r < R S during the whole integration duration t S .

Unless otherwise stated, we have deliberately omitted the class of orbits crashing primaries. According to [START_REF] Nagler | Crash test for the Copenhagen problem[END_REF][START_REF] Nagler | Crash test for the restricted three-body problem[END_REF] the crash basin scales as a power law r α b where r b is the 3 radius of the primary mass and α ∼ 0.5. In this work we choose a radius of r b = 10 -5 for the two primaries which gives two percent of crashing orbits and an area of about one percent for crash basin not visible in the presented Poincaré sections. The sets of non-escaping orbits shown in Fig. 1 are also distinguishable in the studies [START_REF] Nagler | Crash test for the Copenhagen problem[END_REF][START_REF] Nagler | Crash test for the restricted three-body problem[END_REF] devoted to crashing orbits but not studied in details. For example Fig. 1d presents a Poincaré section for the Copenhagen problem case (µ = 0.5) with C = 3 which is similar to the Poincaré section presented in the study [START_REF] Nagler | Crash test for the Copenhagen problem[END_REF] The time evolution of density of non-escaped particles is shown in Fig. 6 for µ = 0.5 and Fig. 7 for µ = 0.3 for the case of primary bodies of relatively large radius r b = 0.01 (such a size is also available in Fig. 5 in [START_REF] Nagler | Crash test for the Copenhagen problem[END_REF]). These data clearly show that the strange repeller structure is established on rather short time scales with t ∼ 1. We also see that for such a value of r b the measure of crashed orbits gives a visible contribution to the measure of non-escaping orbits of strange repeller.

Finally we note that in our computations we determined the fractal dimension D of trajectories non-escaping in future (see a similar situation considered for the Chirikov standard map with absorption in Ermann, L. and Shepelyansky, D. L., 2010). According to the general relations known for the strange fractal sets in dynamical systems the fractal dimension D 0 of the invariant repeller set (orbits non-escaping neither in the future nor in the past) satisfies the relation D 0 = 2(D -1) [START_REF] Ott | Chaos in Dynamical Systems[END_REF]. Thus for the typical value we have in Fig. 1 at µ = 0.3 with D ≈ 1.87 we obtain D 0 ≈ 1.74.

We can expect that the spiral fractal structure, clearly present in the plane (x, y) of the Poincaré sections (see e.g. Fig. 1), will give somewhat similar traces for the surface (or area) density ρ s = dN t /dxdy of particles N t remaining in the system at an instant moment of time t. A typical example of surface density, corresponding to Fig. 1a,b,c, is shown in Fig. 8. Indeed, we find a clear spiral structure of ρ s (x, y) similar to the spiral structure of the strange repeller of Fig. 1a,b,c. Of course, here in Fig. 8 we have the projected density of particles in (x, y) plane taken at all values of ṙ (and not only at ṙ = 0 as in Fig. 1), This 1) with ṙ = 0 and φ < 0 for primary bodies with radius r b = 0.01 and for µ = 0.3 and C = 3. The panels show (a) all points after t = 0, (b) all points after t = 0.01, (c) all points after t = 1, (d) all points after t = 10. The gray scale bar shows the time when particles pass through the Poincaré section. Light gray (dark gray) points have been obtained at t ≈ 1 (t ≈ 10 3 ). Red (blue) points have been obtained from orbits crashing on the µ (1-µ) primary mass. Initially 10 5 particles have been randomly distributed in the 1.3 ≤ r ≤ 2.5 ring.

leads to a smoothing of the fractal structure of the Poincaré section but the spiral distribution of density ρ s remains well visible. We also note that the angle averaged density of remaining particles < ρ s (r) >∝ 1/r 3/2 has a radial dependence on r being similar to those found for the dark matter density obtained in the symplectic simulations of scattering and capture of dark matter particles on binary system (see e.g. Fig. 4a in [START_REF] Lages | Dark matter chaos in the solar system[END_REF]Rollin et al., 2015b).

Poincaré recurrences and probability decay

We determine numerically the probability P(t) to stay inside the system for time larger than t. For that N particles are randomly distributed in the range 1.3 ≤ r ≤ 2.5 and then the survival probability P(t) is defined as the ratio P(t) = N t /N, where N t is the number of particles remained inside the system with r < R S = 10 at times larger than t. This survival probability is proportional to the integrated probability of Poincaré recurrences (see e.g. [START_REF] Chirikov | Asymptotic statistics of Poincaré recurrences in Hamiltonian systems with divided phase space[END_REF][START_REF] Frahm | Ulam method for the Chirikov standard map[END_REF].

The typical examples of the decay P(t) are shown in Fig. 9. At relatively small time scales with t < 100 the decay can be approximately described by an exponential decay with a decay time τ s ∼ 10. Indeed, for the strange dynamical sets (e.g. strange attractors) one obtains usually an exponential decay since there are no specific sticking regions in such strange sets [START_REF] Chirikov | Correlation properties of dynamical chaos in Hamiltonian systems[END_REF].

However, at larger time scales t > 100 we see the appearance of the algebraic decay of probability corresponding to the algebraic statistics of Poincaré recurrences discussed for symplectic maps (see e.g. [START_REF] Chirikov | Asymptotic statistics of Poincaré recurrences in Hamiltonian systems with divided phase space[END_REF][START_REF] Cristadoro | Universality of algebraic decays in Hamiltonian systems[END_REF][START_REF] Frahm | Ulam method for the Chirikov standard map[END_REF]. When the decay time is measured in number of crossings of the Poincaré section n we obtain the Poincaré exponent β of this decay β = 1.49 being close to the values β ≈ 1.5 found in the symplectic maps. However, if the time is measured in number of rotations of binaries t/2π then we find a somewhat large value of β (see Fig. 9). We explain this deviation a bit later.

The properties of orbits surviving in the system for long times are shown in Fig. 10. We see that such orbits are concentrated in the vicinity of critical KAM curves which separate the orbits of strange repeller from the integrable islands with KAM curves. This is exactly the situation discussed in the symplectic maps (see e.g. [START_REF] Chirikov | Asymptotic statistics of Poincaré recurrences in Hamiltonian systems with divided phase space[END_REF][START_REF] Cristadoro | Universality of algebraic decays in Hamiltonian systems[END_REF][START_REF] Frahm | Ulam method for the Chirikov standard map[END_REF]. Thus the asymptotic decay of survival probability is determined by long time sticking orbits in the vicinity of critical KAM curves. The detail analytical explanation of this generic phenomenon is still under debates (see e.g. [START_REF] Meiss | Thirty years of turnstiles and transport[END_REF]. At fixed µ = 0.3 the variation of decay properties of P(t) with the Jacobi constant C is shown in Fig. 11. For C = 3.4 the exponential decay of P(t) is much slower than for the cases C = 3.6 and C = 3 (there is a factor 3.5 between corresponding characteristic time scales τ s ). We attribute this behavior to the Red regions are forbidden since there ẋ2 + ẏ2 < 0. Black dots represent nonescaped orbits staying inside the r < R S = 10 region after time t = 10. Blue dots represent bounded orbits on KAM curves inside integrable islands. Green plain circles mark out non-escaped orbits remaining inside the disk r < R s after time t = 500. The red (blue) star * ( * ) gives the position of the primary (secondary) mass. Each of Poincaré sections is obtained from orbits of N = 10 7 particles initially placed in the 1.3 ≤ r ≤ 2.5 region; these particles are considered as escaped once r > R s . fact that the forbidden zone encloses almost completely binary components letting for particles only a small route to binary components in comparison with cases C = 2.6 and C = 3 for which the route to gravitational perturbers is not constrained. Meanwhile, particles have a limited access to the chaotic component (see Fig. 5d where it forms a narrow peanut shell around central stability islands) so that the sticking in the vicinity of critical KAM curves is reduced emphasizing the exponential decay. For C = 2.6, 3 at long time scales (Fig. 11d) we have a well visible algebraic decay P(n) with β ∼ 1.5 (we may assume that increasing sufficiently the number of initially injected particle for the case C = 3.4, blue line in Fig. 11d would also exhibit at large time scales the same β ∼ 1.5 algebraic decay). However, algebraic decay of P(t) for C = 2.6, 3 at large time scale (Fig. 11b) still have somewhat different value of β.

The origin of this difference for P(t) becomes clear from Fig. 12 where we show the data similar to those of Figs. 9,11 at µ = 0.3 but with the escape radius R S = 100. We see that the decay properties of P(n) remain practically unchanged that confirms the generic features of obtained results for β (indeed, stability islands do not affect dynamics at r ∼ R S = 100). However, the value of β for P(t) is significantly reduced to β ≈ 1.1. We explain this by the fact that in the usual time units the measure of chaotic component at large distances becomes dominant and the escape time is determined simply by a Kepler rotation period which becomes larger for large r values. This leads to the decay exponent β = 2/3 for P(t) as discussed in [START_REF] Borgonovi | Long-time decay properties of Kepler map[END_REF] and explains the variation of β with R S . However, when the time is counted in the number of orbital periods the divergence of the orbital period at large r values (or small coupling energies) does not affect the decay and we obtain the Poincaré exponent β ≈ 1.5 being independent of R S . We note that the recent studies of survival probability decay in the PCRTBP also report the value of β ≈ 1.5 [START_REF] Kovács | Transient chaos and fractal structures in planetary feeding zones[END_REF].

Symplectic map description

Finally we discuss the case when particles in the sidereal reference frame scatter on the binary with relatively large values of perihelion distance q 1. Such a case corresponds to large |C| 1. For q 1 the dynamics of particle in the field of two binaries is approximately described by the symplectic map of the form w = w + F(x); x = x + w-3/2 where w = -2E is the particle energy, x is the phase of binary rotation (in units of 2π) when the particle is located at its perihelion and F(x) ∝ µ is a periodic function of x [START_REF] Petrosky | Chaos and cometary clouds in the solar system[END_REF][START_REF] Chirikov | Chaotic dynamics of Comet Halley[END_REF][START_REF] Shevchenko | The Kepler map in the three-body problem[END_REF]Rollin et al., 2015a,b); bars above w and x mark new values after one rotation around the binary. The amplitude F max decreases exponentially with increasing q. Usually, one considers the case of µ 1 (e.g. Sun and Jupiter) but our studies show that this form remains valid even for µ ∼ 0.5 if q 1. At µ 1 we have F max 1 and the escape time t i becomes very large t i ∝ 1/F max 2 being much larger than the Lyapunov time scale. In this situation the fractal dimensions D and D 0 are very close to D = D 0 = 2 [START_REF] Ott | Chaos in Dynamical Systems[END_REF][START_REF] Ermann | Ulam method and fractal Weyl law for Perron-Frobenius operators[END_REF] and the fractal effects practically disappear. Due to that this case is not interesting for the fractal analysis.

Discussion

We analyzed the PCRTBP dynamical system and showed that for moderate mass ratio of primary bodies µ ∼ 0.5 the Poincaré section is characterized by a strange repeller with the fractal dimension having typical values D ≈ 1.87 (D 0 ≈ 1.74) at moderate values of the Jacobi constant C ∼ 2. At the same time certain islands of integrable motion are still present. Such a struc-ture of the Poincaré section leads to an exponential decay of survival probability in the system on short time scales followed by the algebraic decay with the Poincaré exponent β ≈ 1.5 being similar to the values known for the statistics of Poincaré recurrences in generic symplectic maps. For the small mass ratio µ 1 the escape times becomes very large and the fractal dimension becomes close to the usual value D = 2.

It is interesting to note that the strange repeller structure (see Figs. 1,5,6,7,10) reminds the structure of spiral galaxies (see e.g. Milky Way representation at European Southern Observatory website, 2013). In fact the fractal features of galaxies have been studied extensively by various groups [START_REF] Elmegreen | Fractal structure in galactic star fields[END_REF][START_REF] Sánchez | The nature of the Gould belt from a fractal analysis of its stellar population[END_REF][START_REF] Sánchez | The fractal dimension of star-forming regions at different spatial scales in m33[END_REF] which obtained from observation data the fractal dimensions for the plane density being around D g ≈ 1.3 -1.7 for different galaxies. Some of these values (e.g. [START_REF] Sánchez | The nature of the Gould belt from a fractal analysis of its stellar population[END_REF], with D g ≈ 1.7) are similar to those obtained here for the Poincaré section of PCRTBP. Our results show that the spiral fractal structure of the Poincaré section of PCRTBP leads to a spiral structure of global density of particles ρ s remaining in the system (see Fig. 8). Thus we make a conjecture that the spiral structure of certain galaxies can be linked to the underlying spiral fractals appearing in the dynamics of particles in binary systems. Of course, such a conjecture requires more detailed analysis beyond the present paper such as taking into account the third dimension. Also whether or not the spiral structure remains in the steady state is an important question. To bring some elements of response to the latter question we have injected at r = 100 particles with close-to-parabolic hyperbolic trajectories in 2-body paradigm. We use a Maxwellian distribution for initial velocities f (v)dv = √ 54/π v 2 /u 3 exp -3v 2 /2u 2 dv with u = 0.035 and a homogeneous distribution for perihelion q ∈ [0; 3] parameters. We checked that our results in steady state are independent of initial distributions. We present on Fig. 13 the surface density of particles ρ s (x, y) in the steady state attained around t 0 ∼ 10 3 (Fig. 13a). We clearly see that the two arms spiral structure remains in the steady state, we show examples for particles with trajectories characterized by (b) C = 2.6, (c) C = 3.4, (e) C = 4 (example not shown for C = 3 is analogous to Fig 8a). However when all injected particles are considered independently of the Jacobi constant C we obtain a blurred spiral (Fig. 13f). The contributions of different Jacobi constants are consequently mixed according to the distribution Fig. 13d. We remark that the results presented in Fig. 13 share similarities with those obtained in the study of chaotic trajectories in spiral galaxies [START_REF] Harsoula | Asymptotic orbits in barred spiral galaxies[END_REF]Contopoulos andHarsoula, 2012, 2013). On the basis of obtained results we make a conjecture about existence of certain links between observed fractal dimensions of galaxies [START_REF] Elmegreen | Fractal structure in galactic star fields[END_REF][START_REF] Sánchez | The nature of the Gould belt from a fractal analysis of its stellar population[END_REF][START_REF] Sánchez | The fractal dimension of star-forming regions at different spatial scales in m33[END_REF] and fractal spiral repeller structure studied here. We think that the further studies of fractal structures in binary systems will bring new interesting results.

Figure 1 :

 1 Figure 1: (x, y) -Poincaré sections of the Jacobi Hamiltonian (1) with ṙ = 0 and φ < 0. Poincaré sections for a binary with µ = 0.3, C = 3 are shown in panels: (a) at a large scale, (b) at an intermediate scale, (c) close-up in the vicinity of the primary mass. Panel (d) shows the Poincaré section for µ = 0.5 and C = 3. Red regions are forbidden since there ẋ2 + ẏ2 < 0. Black dots represent nonescaped orbits staying inside the r < R s = 10 region after time t = 10. Invariant KAM curves (blue dots) are obtained choosing initial conditions inside KAM islands. The red (blue) star * ( * ) gives the position of the 1 -µ mass (µ mass). The Poincaré section is obtained with orbits of N = 10 7 test particles initially placed at random in the region 1.3 ≤ r ≤ 2.5. Particles as escaped once r > R S .

Figure 2 :

 2 Figure 2: (p x , x) -Poincaré section of the Jacobi Hamiltonian (1) with y = 0 and p y > 0 for a binary with µ = 0.3, C = 3 (corresponding to Fig. 1a, b, c). Panel (a): Poincaré section at large scale; panel (b): zoom in the vicinity of primaries. Black dots represent non-escaped orbits staying inside the r < R s = 10 region after time t = 10. Blue dots represent bounded orbits inside stability islands. The red (blue) star * ( * ) gives the position of the primary (secondary) mass as in Fig. 1. The Poincaré section is obtained with the same orbits as in Fig. 1.

Figure 3 :

 3 Figure 3: Number of boxes N b covering at scale b non-escaped orbits structure (strange repeller) appearing in (x, y) -Poincaré section of the Jacobi Hamiltonian (1). Box-counting computation is performed in an annulus square consisting in a square region -3.9 ≤ x, y ≤ 3.9 deprived of its central square region -1.3 ≤ x, y ≤ 1.3. The annulus square is divided into 8 equal square areas of linear size dl 0 = 1.3. We average the box counting N b over the 8 squares. At scale b each square is divided into 1/b 2 boxes of linear size dl = b dl 0 . Box-counting results are shown for Poincaré section of orbits staying in the r < R S = 10 disk after t = 3 (black crosses), t = 10 (red squares), t = 30 (green circles), t = 50 (blue triangles). The fractal dimension D of the strange repeller is the slope of the affine function log 2 N b = f (log 2 (1/b)). Keeping orbits staying in the r < R S disk after time t = 10 (t = 3) we obtain a strange repeller fractal dimension (a) D = 1.8711 ± 0.0100 (D = 1.8732 ± 0.0105) for µ = 0.3 and C = 3 (see Fig. 1a, b, c), (b) D = 1.8657 ± 0.0117 (D = 1.8690 ± 0.0129) for µ = 0.4 and C = 3 (see Fig. 10b), (c) D = 1.8700 ± 0.0077 (D = 1.8722±0.0084) for µ = 0.3 and C = 2.6 (see Fig. 5a), (d) D = 1.8349±0.0484 (D = 1.8464 ± 0.0436) for µ = 0.3 and C = 3.4 (see Fig. 5d). Fits have been performed in the scale range 2 4 ≤ 1/b ≤ 2 8 . We used N = 10 8 (a, b, c), N = 10 6 (d) test particles initially distributed at random in the 1.3 ≤ r ≤ 2.5 ring. The fractal dimension has been computed with (a) N t>3 = 39526570, N t>10 = 9933333, N t>30 = 768282, N t>50 = 83290 points, (b) N t>3 = 26743797, N t>10 = 6550163, N t>30 = 372871, N t>50 = 25037 points, (c) N t>3 = 37610948, N t>10 = 8721338, N t>30 = 419296, N t>50 = 39891 points, (d) N t>3 = 8569720, N t>10 = 5447406, N t>30 = 2245927, N t>50 = 1083887 points. The curves bend down for the smallest scales b when 1/b 2 becomes of the order of the number of collected points in Poincaré section.

Figure 4 :

 4 Figure 4: Number of boxes N b covering at scale b non-escaped orbits structure (strange repeller) appearing in (x, y) -Poincaré section of the Jacobi Hamiltonian (1). Box-counting computation is performed as in Fig.3. Box-counting results are shown for Poincaré section of orbits staying in the r < R S = 100 disk after t = 3 (black crosses), t = 10 (red squares), t = 30 (green circles), t = 50 (blue triangles). Keeping orbits staying in the r < R S = 100 disk after time t = 3, 10, 30, 50 we obtain a strange repeller fractal dimension (a) D = 1.8908 ± 0.00876, 1.8900 ± 0.00858, 1.8874 ± 0.00754, 1.8799 ± 0.00480 for µ = 0.3 and C = 3 (see Fig.1a, b, c), (b) D = 1.8916 ± 0.0129, 1.8911 ± 0.0127, 1.8869 ± 0.0110, 1.8786 ± 0.0086 for µ = 0.4 and C = 3 (see Fig.10b). Fits have been performed in the scale range 2 4 ≤ 1/b ≤ 2 8 . We used N = 10 8 test particles initially distributed at random in the 1.3 ≤ r ≤ 2.5 ring. The fractal dimension has been computed with (a) N t>3 = 38090345, N t>10 = 18470667, N t>30 = 7588914, N t>50 = 4574705 points, (b) N t>3 = 27206778, N t>10 = 14259496, N t>30 = 6542192, N t>50 = 4286763 points.

Figure 5 :

 5 Figure 5: (x, y) -Poincaré sections of the Jacobi Hamiltonian (1) with ṙ = 0 and φ < 0 for µ = 0.3 and Jacobi constant (a) C = 2.6, (b) C = 3, (c) C = 3.2, (d) C = 3.4, (e) C = 3.6, and ( f ) C = 4. Red regions are forbidden since there ẋ2 + ẏ2 < 0. Black dots represent non-escaped orbits staying inside the r < R s = 10 region after time t = 10. Blue dots represent bounded orbits. The red (blue) star * ( * ) gives the position of the primary (secondary) mass as in Fig. 1. Poincaré sections have been obtained analyzing orbits of N = 10 7 (a, b, c) and N = 10 5 (d, e, f ) particles initially placed in the 1.3 ≤ r ≤ 2.5 region. Particles are considered as escaped once r > R S .

  Fig. 3 right column middle row for C = 2.85.

Figure 6 :

 6 Figure 6: (x, y) -Poincaré sections of the Jacobi Hamiltonian (1) with ṙ = 0 and φ < 0 for primary bodies with radius r b = 0.01 and for µ = 0.5 and C = 1. The panels show traces of orbits associated with particles escaping at time (a) t esc > 0 (i.e. all computed orbits are shown), (b) t esc > 0.01, (c) t esc > 1, (d) t esc > 10. The gray scale bar shows the time when particles pass through the Poincaré section. Light gray (dark gray) points have been obtained at t ≈ 1 (t ≈ 10 3 ). Red (blue) points have been obtained from orbits crashing on the µ (1-µ) primary mass. Initially 10 6 particles have been randomly distributed in the 1.3 ≤ r ≤ 2.5 ring. Fig. 5 (4th panel for r b = 0.01) in Nagler (2004) is similar to panel (a).

Figure 7 :

 7 Figure 7: (x, y) -Poincaré sections of the Jacobi Hamiltonian (1) with ṙ = 0 and φ < 0 for primary bodies with radius r b = 0.01 and for µ = 0.3 and C = 3. The panels show (a) all points after t = 0, (b) all points after t = 0.01, (c) all points after t = 1, (d) all points after t = 10. The gray scale bar shows the time when particles pass through the Poincaré section. Light gray (dark gray) points have been obtained at t ≈ 1 (t ≈ 10 3 ). Red (blue) points have been obtained from orbits crashing on the µ (1-µ) primary mass. Initially 10 5 particles have been randomly distributed in the 1.3 ≤ r ≤ 2.5 ring.

Figure 8 :

 8 Figure 8: (a) Snapshot of the remaining particles at t = 10 for µ = 0.3 and C = 3. The number of particles initially injected in the 1.3 ≤ r ≤ 2.5 ring is N = 10 8 , at time t = 10 there are N t = 13302225 particles remaining inside the circle r ≤ R S = 10, colors show the surface density of particles ρ s in the plane (x, y), color bar gives the logarithmic color scale of density with levels corresponding to a proportion of the N t remaining particles; (b) same as panel (a) but on a smaller scale; (c) linear density ρ(r) = dN t /dr; (d) angle averaged surface density ρ(r)/r = 2π < ρ s (r) >, the dashed line shows the slope ∝ 1/r 3/2 .

Figure 9 :

 9 Figure 9: Survival probability P of particles as a function of time t (left panels, binary period is 2π) and as a function of the number n of successive Poincaré section crossings (right panels) for C = 3 and binaries with mass parameter µ = 0.3 (black curve), µ = 0.4 (red curve), µ = 0.5 (blue curve). Survival probabilities are shown in semi-log scale (top panels) and in log-log scale (bottom panels). Dashed lines show (a) exponential decay P ∝ exp(-t/τ s ) with 1/τ s = 0.13, (b) algebraic decay P(t) ∝ 1/t β with the Poincaré exponent β = 1.82, (c) exponential decay P(n) ∝ exp(-n/τ s ) with 1/τ s = 0.07, (d) algebraic decay P(n) ∝ 1/n β with β = 1.49. Initially 10 8 particles have been randomly distributed in the 1.3 ≤ r ≤ 2.5 ring. Escape radius is R S = 10.

Figure 10 :

 10 Figure 10: (x, y) -Poincaré sections of the Jacobi Hamiltonian (1) with ṙ = 0 and φ < 0 for C = 3 in the case of (a) a µ = 0.3 binary and (b) a µ = 0.4 binary.Red regions are forbidden since there ẋ2 + ẏ2 < 0. Black dots represent nonescaped orbits staying inside the r < R S = 10 region after time t = 10. Blue dots represent bounded orbits on KAM curves inside integrable islands. Green plain circles mark out non-escaped orbits remaining inside the disk r < R s after time t = 500. The red (blue) star * ( * ) gives the position of the primary (secondary) mass. Each of Poincaré sections is obtained from orbits of N = 10 7 particles initially placed in the 1.3 ≤ r ≤ 2.5 region; these particles are considered as escaped once r > R s .

Figure 11 :

 11 Figure 11: Survival probability P of particles as a function of time t (left panels, binary period is 2π) and as a function of the number n of successive Poincaré section crossings (right panels) for µ = 0.3 and C = 2.6 (black curve), C = 3 (red curve), C = 3.4 (blue curve). Survival probabilities are shown in lin-log scale (top panels) and in log-log scale (bottom panels). Blue dashed lines show exponential decay P(t) ∝ exp(-t/τ s ) with 1/τ s = 0.04 (a,b) and P(n) ∝ exp(-n/τ s ) with 1/τ s = 0.03 (c,d). Gray dashed lines show (a) exponential decay P(t) with 1/τ s = 0.14, (b) algebraic decay P(t) with β = 1.87, (c) exponential decay P(n) with 1/τ s = 0.09, (d) algebraic decay P(n) with β = 1.6. Initially 10 8 particles have been randomly distributed in the 1.3 ≤ r ≤ 2.5 ring. Escape radius is R S = 10.

Figure 12 :

 12 Figure 12: Survival probability P of particles as a function of time t (left panels, binary period is 2π) and as a function of the number n of successive Poincaré section crossings (right panels) for µ = 0.3, C = 3 in the case of an escape radius R S = 100. Dashed curves show (a) exponential decay P(t) with 1/τ s = 0.012, (b) algebraic decay P(t) with β = 1.11, (c) exponential decay P(n) with 1/τ s = 0.062, (d) algebraic decay P(n) with β = 1.40. Initially 10 8 particles have been randomly distributed in the 1.3 ≤ r ≤ 2.5 ring.

Figure 13 :

 13 Figure 13: Density of particles in the steady state. (a) Number N of particles in the r < 100 region of the binary as a function of time t. We have continuously injected N = 10 8 particles placed randomly on r = 100 circle with close to parabolic but hyperbolic trajectories in the 2-body paradigm. Steady state is achieved around t ∼ t 0 = 10 3 . The surface density of particles ρ s (x, y) is shown for Jacobi constants C = 2.6 (b), C = 3.4 (c) and C = 4 (e). Each surface density has been obtained from 1000 surface density snapshots taken at regular time interval after t 0 = 10 3 once steady state is attained. Color bar gives the logarithmic color scale of density with levels corresponding to the ratio of N C /N 10 where N C is the number of particles in a given cell of size 0.1 × 0.1 and N 10 is the number of particles in the r < 10 region. Panel (d) shows the normalized steady state distribution of Jacobi constants of particles present in the r < 100 region. Panel (f) shows the steady state surface density build with all particles in r < 100 region.


Eric Goles

Nicolas Ollinger

Guillaume Theyssier

Introducing Freezing Cellular Automata

We introduce the class of freezing cellular automata (CA): those where the state of a cell can only increase according to some order on states. It contains some well-studied examples like the bootstrap percolation CA or "life without death", but here we aim at studying the class as a whole and deriving general properties of freezing CA. Our focus is mainly on the complexity of these CA and we show that, if their definition imposes strong constraints on their possible dynamics, they still can produce complex computational behaviors, even in dimension 1. Our main results are that the prediction problem of these CA can be P-complete in dimension 2 or more, but is always NL in dimension 1. Moreover its communication complexity is always at most O(n d-1 log(n)) in dimension d (while it can be Ω(n d ) for a CA in general). As another dimension-sensitive property, we show that the nilpotency problem is decidable in dimension 1 but not in higher dimension. Finally, although simpler, we show that one-dimensional freezing CA can still be Turing universal.

Definition and Examples

). Equivalently, it can be define locally by a neighborhood V (a finite subset of Z d ) and a local transition function f :

In this paper we focus on a particular class of CA defined by a simple condition on its local transition function as follows.

Definition 1. A CA F is a freezing CA, for some (partial) order ≥ on states, if the state of any cell can only increase, i.e. F (c) z ≥ c z for any configuration c and any cell z.

In a freezing CA, a cell can change at most a finite number of time during its evolutions, precisely at most n-1 times for a CA with n states. Conversely, a CA with a uniformly bounded number of state change at each cell is not necessarily freezing. For instance, the following nilpotent CA over {0, 1, 2} is not freezing:

f (a, b) = 1 if b = 0 2 else.
because both 2 → 1 and 1 → 2 are possible state changes in one cell (but after 2 steps all cells are in state 2). However, it is easy to simulate any CA with state set Q and at most k changes per cell by a freezing CA on Q × {0, . . . , k}: the {0, . . . , k} component is increased each time the original CA generate a state change in the Q component, and when the value k is reached, any state change is prohibited. The resulting CA is freezing for the order on states Q × {0, . . . , k} defined by: (q, i) (q , j) ⇔ q = q ∧ i ≤ j CA with a bounded number of state change have been as language recognizer [START_REF] Vollmar | Parallel Processes and Related Automata / Parallele Prozesse und damit zusammenhängende Automaten[END_REF] (see also [START_REF] Kutrib | Cellular automata with sparse communication[END_REF] for CA with bounded communications). Here we study freezing CA as dynamical systems.

Particular freezing cellular automata have already been considered in the literature, in particular the threshold growth models in 2D [START_REF] Gravner | Cellular automaton growth on z2: Theorems, examples, and problems[END_REF]: they are CA with states 0, 1 where 0 becomes 1 if the number of 1s in the neighborhood is above some threshold, and 1s stay unchanged forever. They were in particular considered as theoretical models of bootstrap percolation and a lot of work was dedicated to the experimental and rigorous analysis of the phase transitions they exhibit (see for instance [START_REF] Holroyd | Sharp metastability threshold for two-dimensional bootstrap percolation[END_REF]).

Another freezing 2D CA with 2 states called "life without death" receive a lot of attention and was in particular shown P -complete [START_REF] Griffeath | Life without death is P-complete[END_REF].

Finally, other well-studied models which are not exactly deterministic cellular automata but of similar kind fulfill the freezing paradigm, for instance:

self-assembly tilings [START_REF] Patitz | An introduction to tile-based self-assembly and a survey of recent results[END_REF]: tiles are added in empty places but never removed; -SIR epidemic propagation models [START_REF] Fuentes | Cellular automata and epidemiological models with spatial dependence[END_REF]: a Susceptible person can become Infected, and then Recover and acquire immunity so that it nether goes back to susceptible or infected states.

Basic Dynamical Properties

The family of freezing CA is closed under iterations, Cartesian product, subautomaton, local factor and grouping, but not under composition by shifts: the identity automaton is freezing, but the shift automaton is not.

The main property of these CA is that they progressively "freeze" any initial configuration.

Proposition 1. Given a freezing CA F and any configuration c, the sequence F t (c) t converges in the Cantor metric to some limit configuration F ∞ (c) which is a fixed point for F .

Proof. Since the state of any cell can only increase, each cell can only change its state a finite number of times. Therefore, starting from configuration x, for any n ≥ 0 there exists a time t such that no cell at distance n from the center will change of state after time t. This is equivalent to the convergence of the sequence F t (x) t .

This "freezing" behavior is intrinsically irreversible except in the trivial case of the identity.

Proposition 2. If a freezing CA is surjective then it is the identity map.

Proof (Proof sketch). Suppose that F is a freeezing CA which is not the identity map. Then there must exist two configurations c and d such that F (c) = d but c 0 = d 0 . Let's choose such a pair (c, d) that minimizes (for the order ≤ on states) the state d 0 . Because F is freezing, we have c 0 ≤ d 0 . Having chosen d 0 minimal, this implies that for any c , d with F (c ) = d and d 0 = c 0 , we must also have

c 0 = c 0 .
Therefore, state c 0 can only be produced from state c 0 but in at least one context (appearing in configuration c), c 0 changes to another state (d 0 ): the CA F cannot be balanced and therefore is not surjective [START_REF] Maruoka | Condition for Injectivity of Global Maps for Tessellation Automata[END_REF].

Proposition 1 says that every orbit converges to a fixed point. This does not imply that the limit set is made of fixed points, however we can prove the following proposition which is not true for CA in general. Proposition 3. Let F be a freezing CA which is not nilpotent. Then it possesses two distinct fixed points.

Proof. Let M be a maximal state for the order ≤ on states coming from the freezingness of F , and denote by c M the uniform configuration everywhere equal to M . Since F is freezing, c M must be a fixed point for F . Now, since F is not nilpotent, for any t ≥ 0, there is some configuration c t such that F t (c t ) 0 = M . Because F is freezing, for any fixed k ≥ 0, the value of the cells at distance k of the center can change at most φ(k) times in any orbit. Therefore choosing t > φ(k), there must be some step t ≤ t in the orbit of c t at which these cells do not change, formally:

∀i, i ≤ k ⇒ F t (c t ) i = F t +1 (c t ) i .
Denote by d k = F t (c t ). For any k we have:

-∀i, i ≤ k, F (d k )(i) = d k (i) -d k (0) = M (because F t (c t ) 0 = M , F is freezing and M is a maximal state).
By compactness, we can extract a limit point d from the sequence (d k ) k . Finally, by the properties of the d k stated above, we have:

F (d) = d and d = c M .
As a corollary, we get the following dimension-sensitive decidability result.

Theorem 1. The nilpotency problem for freezing CA is:

decidable (in polynomial time) for 1D CA; undecidable for CA in higher dimension.

Proof. First, in dimension 2 and more, the classical proof of undecidability of nilpotency (see [START_REF] Kari | The Nilpotency Problem of One-dimensional Cellular Automata[END_REF]) works without any modification for freezing CA: given a Wang tile set, we build a freezing CA with a spreading error state, that checks locally if the configuration is a valid tiling and produces the error state in case of local error detection. This CA is nilpotent if and only if the tile set does not tile the plane.

In dimension 1, from Proposition 3, we know that nilpotency is equivalent to the following first-order property

∀x∀y x = F (x) ∧ y = F (y) ⇒ x = y .
From [START_REF] Sutner | Model checking one-dimensional cellular automata[END_REF], it follows that it is decidable.

Computational Complexity

Definition 2. Let F be any CA of radius r and dimension d. The prediction problem PRED F is defined as follows:

input: a square pattern u of size (2rt + 1) d ouput: the state F t (u) Proposition 4. 2D freezing CA are Turing-universal and there exists a 2D freezing CA with a P-complete prediction problem.

Proof. Any 1D CA F with states Q and neighborhood V can be simulated by a 2D freezing CA with states Q ∪ { * } as follow. Let V = {(v, -1) : v ∈ V }. A cell in a state from Q never changes. A cell in states * look at cells in its V neighborhood: if they are all in a state from Q then it updates to the state given by applying F on them, otherwise it stays * . Starting from a all- * configuration except on one horizontal line where it is a Q-configuration c 0 , this 2D freezing CA will compute step by step the space-time diagram of F on configuration c 0 . The proposition follows.

The following result for freezing CA was present in [START_REF] Vollmar | Parallel Processes and Related Automata / Parallele Prozesse und damit zusammenhängende Automaten[END_REF] in a different formalism for bounded-change CA.

Proposition 5. The prediction problem of any 1D freezing CA is NLOGSPACE.

Proof (Proof sketch). Consider (without loss of generality) a 1D freezing CA F of radius 1 with k states. To know that F gives state q after n steps on some input u of size 2n + 1 it is sufficient to guess a sequence of 2n + 1 columns of states (C i ) -n≤i≤n , where C i is of height n -|i| + 1, and to check that they form a (triangular) valid space-time diagram of F on input u that leads to state q (last letter of C 0 ).

The key observation is that, since F is freezing, at most k changes of state can occur in any column, hence a column of height n can be represented in space O(log(n)) (constant list of changes, each given by the time step at which it occurs and the new state).

We give the non-deterministic LOGSPACE algortihm to solve the prediction problem of F :

-initialization: guess columns C -n and C -n+1 and set current position to -n + 1; -main loop: if at current position p, guess column C p+1 with the condition C p+1 [0] = u p+1 and check that each position in C p is compatible with the neighboring columns C p-1 and C p+1 , formally, for all i with 0

≤ i < |C p | check that f (C p-1 [i], C p [i], C p+1 [i]) = C p [i + 1] where f is the local function of F ; increment current position; -termination: if current position is n + 1 return C 0 [n]
Note that the compatibility test between neighboring columns in the main loop can be done using the compact log-space representation of columns.

Theorem 2. 1D freezing CA are Turing-universal.

Proof. Any k-counter Minsky machine [START_REF] Minsky | Computation: Finite and Infinite Machines[END_REF] with states Q can be simulated by a 1D freezing CA encoding the evolution of both the state and counter values on signals moving through the space-time diagram, one transition per space unit. The control of the machine is represented as a signal of equation 0 y -2x 1 where both cells in column x carry the state of the counter machine and an emptiness flag for each counter at time x. Each of the k counters is represented as a signal of the same slope so that the distance to the control in column x encodes the value of the counter at time x. A counter can easily be tested for equality to zero. Incrementation corresponds to a local deceleration of the signal and decrementation to a local acceleration. Incrementation, decrementation or no-operations decisions are carried from the control to the counter as a simple vertical signal. Such a simulation can be implemented by a CA with neighborhood {-1, 0} and 1 + 8|Q| + (3 + 3 + 1) k states, as depicted on Fig. 1. The Turing-universality is then a consequence of the universality of Minsky machines.

To see that the constructed CA is indeed freezing, let us consider a typical column in the simulation: blank symbols are followed by the two control states, followed by k independent counter column. Each counter column contains an operation followed by one to three counter encoding followed by a new blank symbol. A partial order is naturally derived from there where the independent counter columns are treated by a product order.

2++w -- -- -- -- -- -- -- -- -- -- -- -- -- 2++ -- -- -- -- -- -- -- -- -- -- -- -- -- (+-) 2++w -- -- -- -- -- -- -- -- -- -- -- -- (+-) 2++ -- -- -- -- -- -- -- -- -- -- -- -- (+-) (+-) 2++w -- -- -- -- -- -- -- -- -- -- -- (+-) (+-) 2++ -- -- -- -- -- -- -- -- -- -- -- (k-) (+-) (+-) 2++w -- -- -- -- -- -- -- -- -- -- (C-) (+-) (+-) 2++ -- -- -- -- -- -- -- -- -- -- (c-) (+-) (+-) (+-) 2++w -- -- -- -- -- -- -- -- -- (.c) (k-) (+-) (+-) 2++ -- -- -- -- -- -- -- -- -- (..) (Cc) (+-) (+-) (+-) 2++w -- -- -- -- -- -- -- -- (..) (c.) (+c) (+-) (+-) 2++ -- -- -- -- -- -- -- -- (..) (..) (k.) (+c) (+-) (+-) 2++w -- -- -- -- -- -- -- (..) (..) (C.) (+.) (+c) (+-) 2++ -- -- -- -- -- -- -- (..) (..) (c.) (+.) (+.) (+c) (+-) 2++w -- -- -- -- -- -- (..) (..) (..) (k.) (+.) (+.) (+c) 2++ -- -- -- -- -- -- (..) (..) (..) (C.) (+.) (+.) (+.) (+c) 2++w -- -- -- -- -- (..) (..) (..) (c.) (+.) (+.) (+.) (+.) 2+z -- -- -- -- -- (..) (..) (..) (..) (k.) (+.) (+.) (+.) ( .) 0+zw -- -- -- -- (..) (..) (..) (..) (C.) (+.) (+.) (+.) ( .) 0+z -- -- -- -- (..) (..) (..) (..) (c.) (+.) (+.) (+.) ( .) (-.) 1+zw -- -- -- (..) (..) (..) (..) (..) (k.) (+.) (+.) ( .) (-.) 1+z
------(..) (..) (..) (..) (..) (C.) (+.) (+.) ( .) (-.) (-C) 0++w ----(..) (..) (..) (..) (..) (c.) (+.) (+.) ( .) (-.) (-c) 0++ ----(..) (..) (..) (..) (..) (..) (k.) (+.) ( .) (-.) (-.) (-C) 1++w --(..) (..) (..) (..) (..) (..) (C.) (+.) ( .) (-.) (-.) (-c) 1++

--(..) (..) (..) (..) (..) (..) (c.) (+.) ( .) (-.) (-.) (-.) (-k) 0++w (..) (..) (..) (..) (..) (..) (..) (k.) ( .) (-.) (-.) (-.) (-C) 0++ (..) (..) (..) (..) (..) (..) (..) (C.) ( .) (-.) (-.) (-.) (-c) (-) (..) (..) (..) (..) (..) (..) (..) (c.) ( .) (-.) (-.) (-.) (-.) (-C) (..) (..) (..) (..) (..) (..) (..) (..) (C.) (-.) (-.) (-.) (-.) (-c) (..) (..) (..) (..) (..) (..) (..) (..) (c.) (-.) (-.) (-.) (-.) (-.) (..) (..) (..) (..) (..) (..) (..) (..) (..) (c.) (-.) (-.) (-.) (-.) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (c.) (-.) (-.) (-.) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (c.) (-.) (-.) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (c.) (-.) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (c.) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) (..) Fig. 1. A 1D freezing CA simulating a 2-CM Communication complexity was introduced by Yao [START_REF] Yao | Some complexity questions related to distributive computing (preliminary report)[END_REF] to study distributed computing. We first briefly recall the classical definition of communication complexity for any function (see [START_REF] Kushilevitz | Communication complexity[END_REF] for general reference), and then apply it to the prediction problem of cellular automata (for more details see [START_REF] Ch | Communication complexity and intrinsic universality in cellular automata[END_REF]). The goal of this section is to show that freezing CA have a lower communication complexity than CA in general.

Consider a function f : A × B → C where A, B and C are finite sets. The communication complexity of f is the amount of information that need to be exchanged in the worst case between two parties (say Alice and Bob) in order to decide the value f (x, y) when one of the parties knows only x and the other only y (both know f and they have unlimited computing power). Intuitively, the communication complexity of f is defined as the cost of the best protocol that solves f . A protocol is an agreement between the two parties on how to communicate by rounds until one knows the correct value f (x, y). The cost of a protocol is the total amount of information (in bits) exchanged in the worst case over all inputs. We refer to [START_REF] Kushilevitz | Communication complexity[END_REF][START_REF] Ch | Communication complexity and intrinsic universality in cellular automata[END_REF] for more precise definitions.

For any CA F we consider the communication complexity of the prediction problem by dividing the space into two parts through an hyperplane: given some i, Alice has access to all cells whose first coordinate is less than i and Bob to all the others. The upper-bound that we give does not depend on this choice of i. Proof (Proof sketch). Let r be the radius of F . The cells that Alice and Bob respectively have access to are separated by an hyperplane at position i. We distinguish two zones of the space that play an important role: the A-zone is the set of cells (known by Alice) between the hyperplane at position i -r and the one at position i, the B-zone is the set of cells (known by Bob) between hyperplane i and i + r. The general idea is that Alice (resp. Bob) only needs to know the content of the B-zone (resp. A-zone) in addition to its own cells in order to correctly compute one step of F on its part of the space. The protocol is as follows: first, as an initialization step, Alice and Bob exchange the content of the A and B-zones and initialize their time counter at 0. Then, they repeat as much as necessary the following loop:

1. Alice (resp. Bob) separately compute the evolution step by step on its own half-space supposing that nothing changes in the B-zone (resp. A-zone) and until a state change is observed in the A-zone (resp. B-zone); 2. Alice (resp. Bob) send a "diff report" which contains the time step reached and the list of cell changes that occurred in its A-zone (resp. B-zone); 3. Alice (and symmetrically for Bob) receives the other "diff report" and updates its knowledge as follows:

sets its time counter as the min t m of the time values present in the two reports;

if the time in the received diff report is strictly larger than her own time, then ignore the report and keep its previous knowledge of the B-zone, otherwise updates her knowledge of the B-zone according to the diff report; if the time in the received diff report is strictly smaller than her own time, then revert its knowledge of her half-space to what it was at time t m (which she can do without any further information from Bob).

This protocol allows Alice and Bob to correctly compute the evolution of F as far as they need (without even supposing that it is freezing) and thus allows to solve the prediction problem of F . Indeed, the fact that they retrospectively jump back in time to the step of the first change in the A/B-zones ensures that the hypothesis of no change in the A/B-zone is correct for all the retained computation steps. Let's now upper bound its cost on an input of size n d :

the initialization costs O(n d-1 ) (the sizes of the A-zone and the B-zone restricted to the input are n d-1 ); each cell change notification in the diff reports costs at most O(log(n))

(log(n) for the time step, O(log(n)) for communicating the position of the cell, a constant to describe the new state); since F is freezing, the total number of changes in the A-zone and B-zone is O(n d-1 ) (each cell can change a constant number of times).

Therefore the total cost of the protocol is at most O n d-1 log(n) .

Theorem 3 .

 3 For any freezing CA F of dimension d the communication complexity of PRED F on inputs of size n d is O n d-1 log(n) .

This work has been supported by ECOS Sud -CONICYT project C12E05