Anni Määttänen
email: anni.maattanen@latmos.ipsl.fr

Franck Montmessin

Brigitte Gondet

H Hoffmann

F Scholten

E Hauber

F Gonzalez-Galindo

A Spiga

François Forget

Jean-Pierre Bibring

G Neukum

Three Martian Years of Observations of Mesospheric CO2 Clouds on Mars with OMEGA/MEX and HRSC/MEX

teaching and research institutions in France or abroad, or from public or private research centers.

Introduction:

During the last half a decade Mars has revealed a new phenomenon high in its atmosphere whose existence has been suggested already decades ago, but no observational proof had not been acquired before the Mars Global Surveyor and Mars Express missions. The condensation of CO 2 as clouds at high altitudes of the Martian atmosphere was already suggested as an explanation of observations by the Mariner probes [START_REF] Herr | Evidence for solid carbon dioxide in the upper atmosphere of Mars[END_REF], as well as the substance composing the blue clouds observed by Mars Pathfinder in twilight [START_REF] Schofield | The Mars Pathfinder Atmospheric Structure Investigation/Meteorology (ASI/MET) Experiment[END_REF][START_REF] Clancy | CO 2 ice clouds in the upper atmosphere of Mars[END_REF]. However, these observations could not be confirmed as CO 2 ice clouds and, in the case of Mariners, was quite probably an observation of CO 2 fluorescence [START_REF] Lellouch | The 2.4-45 µm spectrum of Mars observed with the infrared space observatory[END_REF][START_REF] Drossart | Limb observations of infrared fluorescence of CO 2 from OME-GA/Mars Express[END_REF].

The first observations of very high-altitude haze layers came from SPICAM/MEx stellar occultations [START_REF] Montmessin | Subvisible CO 2 clouds detected in the mesosphere of Mars[END_REF]: in these observations the haze layers were observed near supersaturated regions of the temperature profile and were thus concluded to be probably composed of CO 2 ice crystals. Around the same time [START_REF] Formisano | Observations of non-LTE emission at 4-5 microns with the planetary Fourier spectrometer abord the Mars Express mission[END_REF] suggested that a part of the reflectance observed in MEx/PFS spectra in near-infrared near the fluorescence peak at 4.3 microns might be coming from CO 2 clouds, but the authors did not explain the formation of the feature. The first spectroscopic identification of these clouds came from observations of OMEGA/MEx [START_REF] Montmessin | Hyper-spectral imaging of convective CO 2 ice clouds in the equatorial mesosphere of Mars[END_REF]). In the presence of a cloud, the latter show a distinctive scattering peak inside a CO 2 absorption band around 4.3 microns that was shown by the authors to be the unambiguous signature of CO 2 ice. The OMEGA dataset was supported by limb observations of MOC and TES (on MGS) [START_REF] Clancy | Mars equatorial mesospheric clouds: Global occurrence and physical properties from Mars Global Surveyor Thermal Emission Spectrometer and Mars Orbiter Camera limb observations[END_REF] of high-altitude aerosol layers with very similar spatial and temporal distribution as the clouds observed by OMEGA. [START_REF] Inada | High-resolution atmospheric observations by the Mars Odyssey Thermal Emission Imaging System[END_REF] also reported the detection of mesospheric clouds in THEMIS-VIS data.

After the confirmation of the formation of CO 2 clouds in the Martian mesosphere by these first publications, additional climatologies were published in 2010 with several datasets from different instruments. [START_REF] Scholten | Concatenation of HRSC colour and OMEGA data for the determination and 3D-parameterization of high-altitude CO 2 clouds in the Martian atmosphere[END_REF] presented the MEx/HRSC dataset of high-altitude (>70 km) clouds that were discovered thanks to a distinct parallax of high-altitude atmospheric features in the stereo images of the instrument. [START_REF] Scholten | Concatenation of HRSC colour and OMEGA data for the determination and 3D-parameterization of high-altitude CO 2 clouds in the Martian atmosphere[END_REF] were able to show in some cases that the clouds HRSC observed were indeed CO 2 by comparing with simultaneous observations and spectroscopic identification by OMEGA. Määttänen et al. (2010a) published a companion study on OMEGA and HRSC data presenting 3 Martian Years (MY 27-29) of OMEGA observations of CO 2 clouds complemented by a selection of HRSC high-altitude cloud observations. Recently a large THEMIS-VIS dataset has been published as well (McConnochie et al. 2010). The climatology that can be compiled from all the aforementioned datasets covers altogether 6 Martian Years of data on high-altitude (CO 2 ) clouds.

Methods:

In this paper we will focus on the OMEGA and HRSC observations of high-altitude CO 2 clouds [START_REF] Scholten | Concatenation of HRSC colour and OMEGA data for the determination and 3D-parameterization of high-altitude CO 2 clouds in the Martian atmosphere[END_REF]Määttänen et al. 2010a). We will also present the latest extension of this dataset with highlights of the observations from the first half of the present Martian Year (MY 30).

The CO 2 clouds can be observed in OMEGA data thanks to a specific spectral signature at 4.26µm, where a spectral peak of strong (resonant) scattering by CO 2 ice is observed inside a strong absorption band of gaseous CO 2 . Sometimes this main peak is accompanied by a secondary peak at 4.32 µm that shows sensitivity to different parameters of the cloud (altitude, opacity, particle size).

The HRSC observes the surface in stereo through 9 different channels or filters looking at nadir or slightly inclined off nadir. It sees highaltitude atmospheric features through the parallax (in the direction of the orbit) they exhibit in the images taken through two filters at different angles and at slightly differing times. The parallax enables determination of the cloud altitude and the shift perpendicular to the orbit of the cloud features in the different images gives an estimate of the cloud (wind) speeds.

OMEGA dataset of MY 27-29:

Statistics Analysis of OMEGA data has revealed the spectroscopic signature of CO 2 ice clouds at 3-sigma level on 51 orbits (in 64 individual images). The clouds are mostly observed near the equator (+/-20°), but some exceptional cases of midlatitude clouds were observed as well. The observation times vary between 08LT-17.30LT, depending on the satellite orbit, and the clouds are mostly found in a limited longitudinal range that spans from -120°E through the prime meridian to 25°E, with some clouds observed at around 230-245°E.

Near-equatorial clouds The near-equatorial clouds are typically observed during the first half of the Martian year, the first clouds appearing right at the spring equinox (Ls=0°) or immediately after. An exceptionally early start of the cloud season was observed at the end of MY 29 when the first cloud of the new equatorial cloud season formed at Ls= 330°. The clouds are observed until Ls=60°, after which a pause of about 30 degrees of Ls has been observed in the dataset of MY 27-29. The clouds reappear at Ls=90° or slightly before, and continue to form until Ls=135°. We are as of now unable to clearly distinguish interannual variations based on the OMEGA dataset because of uneven spatial and temporal coverage during different years, but at least we can state that the seasonality and spatial distribution of the positive cloud observations agree well with previous studies [START_REF] Clancy | Mars equatorial mesospheric clouds: Global occurrence and physical properties from Mars Global Surveyor Thermal Emission Spectrometer and Mars Orbiter Camera limb observations[END_REF]), pointing to small interannual variations on average. The clouds are mostly daytime clouds, with the exception of 10 cases observed in the morning (8-11 LT), but the observational coverage in local time is quite limited.

Midlatitude clouds OMEGA has observed two midlatitude clouds: one in the southern hemisphere (MY 27, reported already by [START_REF] Montmessin | Hyper-spectral imaging of convective CO 2 ice clouds in the equatorial mesosphere of Mars[END_REF], and observed simultaneously by HRSC, [START_REF] Scholten | Concatenation of HRSC colour and OMEGA data for the determination and 3D-parameterization of high-altitude CO 2 clouds in the Martian atmosphere[END_REF]) and another in the northern one (Määttänen et al. 2010a). Both clouds formed around 45-50° latitude during the local autumn (Ls=54° at 50°S, Ls=250° at 45°N). Local times of these clouds vary, the southern one being observed at 08 LT and the northern one at 14 LT.

Shadow observations OMEGA has observed twice the shadow of clouds, which enables, as shown by [START_REF] Montmessin | Hyper-spectral imaging of convective CO 2 ice clouds in the equatorial mesosphere of Mars[END_REF], the estimation of the cloud altitude, opacity and the effective radii of the particles from the observed attenuation of sunlight in the shadow. [START_REF] Montmessin | Hyper-spectral imaging of convective CO 2 ice clouds in the equatorial mesosphere of Mars[END_REF] performed the calculations for the cloud on average, and Määttänen et al. (2010a) refined the study by calculating the properties (opacity and effective radius) for each cloud pixel. The cloud opacities go up to 0.5-0.6 with mean values of 0.14 and 0.25 for the two observations, and the effective radii are compatible with a unimodal distribution with sizes mainly comprised between 1 and 3µm.

OMEGA dataset of MY 30: Statistics In the first half of the MY 30 OME-GA has observed near-equatorial CO 2 clouds on 11 orbits. The clouds are, as usual, confined very close to the equator and at the same longitudinal range as in the previous years. One new cloud shadow observation has been acquired, but the shadow is so faint that decent contrasts, required for the opacity and effective radius analysis, are difficult to identify.

Differences One cloud was observed already in very early spring, at Ls=330° in MY 29, as expected based on the LMD/MGCM [START_REF] Forget | Improved general circulation models of the martian atmosphere from the surface to above 80 km[END_REF][START_REF] Forget | The density and temperatures of the upper martian atmosphere measured by stellar occultations with Mars Express SPICAM[END_REF]) simulations that show the cold season at the cloud altitudes starting at this time of the year. Thus we think this cloud was indeed one of the first clouds of the MY 30 cloud season. The equatorial cloud formation is divided in two distinct periods around the aphelion, the first one ending by Ls=55° in MY 27-29. In MY 30 the cloud formation continued up until Ls=65°. This is the closest observation to the aphelion made so far, and thus the first part of this cloud season was exceptionally long, starting at Ls=330° and continuing up to Ls=65°.

Selected HRSC observations of MY 27-29:

Dataset and statistics The HRSC observations were checked for high-altitude clouds in all orbits during a limited period in the beginning of MY 29, and in addition in all the orbits of MY 27-28 where OMEGA had observed CO 2 clouds. The whole HRSC dataset adds up to 28 high-altitude cloud observations with 11 simultaneous observations with OMEGA. The near-equatorial clouds were observed in the same latitude-longitude ranges as the OMEGA clouds, with the addition of a simultaneous observations of the southern midlatitude cloud with OMEGA, and a new midlatitude cloud at 45°S (Ls=73°, 08 LT).

Altitudes The altitudes of the clouds were analyzed in all but one HRSC observation: the clouds form mainly at 59-87 km altitudes with a slight trend for higher altitudes towards the equator. The midlatitude clouds were observed at the lower end of the range, at 53-62 km. The clouds seem to be forming at higher altitudes in early spring than later in spring and summer. However, the dataset is compiled with observations from different years, all the early spring observations being from MY 29, so we cannot yet state if this is a real trend or an interannual effect.

Cloud speeds The cloud speeds (comparable to the mesospheric wind speeds) were analyzed in 20 cases. The equatorial winds blow from the east with varying, but fairly high speeds, going up to 110m/s. In one case of the midlatitude clouds the wind speeds were westerly with lower magnitudes (5-42 m/s). The wind directions and speeds are in the range expected by Mars General Circulation Model predictions.

Comparison with other datasets:

Statistics of near-equatorial clouds The three extensive equatorial cloud datasets, TES&MOC [START_REF] Clancy | Mars equatorial mesospheric clouds: Global occurrence and physical properties from Mars Global Surveyor Thermal Emission Spectrometer and Mars Orbiter Camera limb observations[END_REF], OMEGA (Määttänen et al. 2010a), and HRSC [START_REF] Scholten | Concatenation of HRSC colour and OMEGA data for the determination and 3D-parameterization of high-altitude CO 2 clouds in the Martian atmosphere[END_REF], agree well on the spatial and temporal distribution of these clouds with minor differences in the timing and length of the aphelion pause, which might be due to interannual variations or merely to differences in observational coverage. THEMIS observed a handful of equatorial clouds that fit well the climatology derived from the other instruments (McConnochie et al. 2010). The altitudes observed by MOC&TES and by HRSC agree, even if the observed range of HRSC altitudes is larger. THE-MIS altitude range is of the same scale as the one observed by HRSC. The wind speeds from THE-MIS and HRSC agree pretty well: both instruments observe easterly winds with THEMIS range being 5-90 m/s, nearly the same as HRSC. The effective radii from OMEGA (2 µm) are in the same range as one THEMIS observation (1.5 µm), with its other two being in a lower range of 50-100 nm. The latter daytime observations fit pretty well with the SPICAM stellar occultation particle sizes (80-130 nm) of clouds observed at 01 LT in the southern subtropics at 90-100 km altitude. The dataset is still too small and it is still too early to say anything conclusive about the differing particle sizes and any local time variations, but the comparison of daily variations of cloud altitude and particle sizes may turn out fruitful (Määttänen et al. 2010b, DPS abstract;Määttänen et al. 2011b, this conference).

Statistics of midlatitude clouds OMEGA and HRSC observed altogether 3 midlatitude clouds, one in the northern and two in the southern hemisphere. Only the two HRSC-observed clouds in the southern hemisphere have associated altitude determinations (53-62 km), and the speed of only one of them has been determined (5-42 m/s). McConnochie et al. (2010) published an extensive THE-MIS-VIS dataset of northern midlatitude clouds with altitude and speed determinations. Their midlatitude clouds are observed in a range of 45-70 km with associated westerly wind speeds of 0-120 m/s.

Summary of 6 Martian Years of data

The datasets listed in the Introduction and above sum up to 6 Martian years of CO 2 cloud observations. We are still far from a complete coverage giving the possibility for drawing definitive conclusions on interannual variations, but the main features of the equatorial clouds and their properties are emerging. With scarse determinations of cloud particle sizes and opacities, we are still lacking information on the cloud properties that could be inferred from further analysis of OMEGA data and data from other instruments as well. These datasets will continue to grow with the continuing Mars Express observations and will be completed with analyses from other instruments and missions.

Conclusions

We have presented a dataset of 3 Martian Years of observations of high-altitude CO 2 clouds with OMEGA and HRSC on Mars Express and compared these observations to other published work. The clouds seem to have a quite regular seasonal behavior, even though we cannot draw definitive conclusions on interannual variability in the lack of full observational coverage. Extensions of existing datasets as well as analyses of new ones will help in filling the gaps and improving our knowledge on the cloud properties. The cloud observation dataset provides a rare source of information on mesospheric variables, such as temperature and winds, and can be used to constrain Global Climate Models.

Figure 1 :

 1 Figure 1: An example of a simultanous observation by OMEGA and HRSC. The green and blue images of HRSC are projected at the Martian surface, revealing the high-altitude clouds as misaligned green and blue hazes. We have superposed the simultaneous OMEGA data at 4.26µm in red.

Figure 2 :

 2 Figure 2: Global map of high-altitude cloud observations by OMEGA (in green) and HRSC (violet). Included are also observations of subfreezing temperatures by SPICAM (in blue, Forget et al. 2009).


Janis Janusevskis
email: janusevskis@emse.fr

Rodolphe Le Riche
email: leriche@emse.fr

Robust optimization of a 2D air conditioning duct using kriging Deliverable WP.2.2.2.B of the ANR / OMD2 project

The design of systems involving fluid flows is typically based on computationally intensive Computational Fluid Dynamics (CFD) simulations. Kriging based optimization methods, especially the Efficient Global Optimization (EGO) algorithm, are now often used to solve deterministic optimization problems involving such expensive models. When the design accounts for uncertainties, the optimization is usually based on double loop approaches where the uncertainty propagation (e.g., Monte Carlo simulations, reliability index calculation) is recursively performed inside the optimization iterations. We have proposed in a previous work a single loop kriging based method for minimizing the mean of an objective function: simulations points are calculated in order to simultaneously propagate uncertainties, i.e., estimate the mean objective function, and optimize this mean.

In this report this method has been applied to the shape optimization of a 2D air conditioning duct. For comparison purposes, deterministic designs were first obtained by the EGO algorithm. Very high performance designs were obtained designs, but they are also very sensitive to numerical model parameters such as mesh size, which suggests a bad consistency between the physics and the numerical model.

The 2D duct test case has then been reformulated by introducing shape uncertainties. The mean of the duct performance criteria with respect to shape uncertainties has been maximized with the simultaneous optimization and sampling method. The solutions found were not only robust to shape uncertainties but also to the CFD model numerical parameters. These designs show that the method is of practical interest in engineering tasks.

Introduction

The analysis of systems involving fluid flows often is assisted with Computational Fluid Dynamics (CFD) simulation models. Solving procedures of such models usually involve computationally intensive algorithms, therefore to reduce time needed for optimization, metamodels (also known as approximations, response surfaces or surrogate models) are used. Kriging or Gaussian Process (GP) regression [START_REF] Sacks | Design and analysis of computer experiments[END_REF][START_REF] Rasmussen | Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning[END_REF] has become a popular metamodeling tool for computationally expensive simulators as it provides surfaces of tunable complexity (possibly interpolative) within a probabilistic framework. The Efficient Global Optimization (EGO) algorithm [START_REF] Jones | Efficient global optimization of expensive black-box functions[END_REF][START_REF] Donald | A taxonomy of global optimization methods based on response surfaces[END_REF] is based on kriging metamodels which allow formulate Expected Improvement (EI) criterion for optimization of deterministic simulators.

However, real life problems are almost always non-deterministic. Uncertainties appear for example due to model errors, manufacturing tolerances, changing environments and noisy measurements. A kriging based method allowing to minimize mean response has been proposed in [START_REF] Janusevskis | Simultaneous kriging-based sampling for optimization and uncertainty propagation[END_REF]. In this report this method is applied to the shape optimization of a 2D air conditioning duct. The uncertainties affect the pipe shape. The mean response, expressed in terms of pressure drop and velocity variation at the duct outlet, is minimized in order to obtain a design robust to shape variations.

Problem formulation

The kriging based method for optimizing the mean of a perturbed objective function proposed in [START_REF] Janusevskis | Simultaneous kriging-based sampling for optimization and uncertainty propagation[END_REF] is applied to a CFD problem: to optimize in two dimensions the shape of an air conditioner pipe subject to shape uncertainties. This is the test case 1 of the ANR / OMD2 project [START_REF]ANR OMD2 project[END_REF] with added uncertainties.

The shape of the pipe is described by line segments and Bezier curves. The pipe consists of 3 parts, visible in both Figures 1 and3: the input pipe (P1-P2-P4-P3), the inner block, joining P3-P4 to P9-P10 and described by the shape variables x, and the output pipe (P9-P10-P12-P11). Two sets of shape parameters x will be discussed in Sections 3 and 4, respectively.

The CFD model is created and solved using the OpenFoam package [START_REF]OpenFoam package[END_REF]. The duct is discretized in 19000 finite elements with the OpenFoam mesher, with 50 cells along the X direction and a single cell along the Z direction. Table 2: Bounds on the design variables boundary conditions impose a uniform velocity along the Y direction at the input (P2P1) and zero pressure at the output (P11P12) of the pipe. The steady-state solver simpleFoam for the Navier-Stokes equations of an incompressible, non-turbulent flow is used with kinematic fluid viscosity of 1.6e-04 m 2 s -1 . The deterministic optimization formulation, which overlooks shape uncertainties, has two objectives. The first objective is to maximize flow uniformity at the exit block (P10P9) or, more precisely, to minimize the standard deviation of the scalar projection of the flow velocity on the vector perpendicular to the P10P9,

min x∈D FlowSD(x) such that x l ≤ x ≤ x u (1)
where x l and x u are lower and upper bounds on x.

The second objective is to minimize the pressure difference between input (P1-P2) and output (P11-P12)

min x∈D PressureLoss(x) such that x l ≤ x ≤ x u . (2)
The robust optimization problem additionally considers that some of the CFD model parameters are uncertain, and should therefore be described as random variables, U . A double set of parameters, x for the deterministic optimization variables and U for the random, uncontrolled parameters, is general as has been previously discussed in [START_REF] Pujol | L'incertitude en conception: formalisation, estimation[END_REF][START_REF] Williams | Sequential design of computer experiments to minimize integrated response functions[END_REF][START_REF] Taguchi | System of experimental designs, volumes 1 and 2[END_REF]. In the case of the air duct, U is a perturbation of the position of the outlet. A more precise description of U will be given in Section 4.2. The robust optimization problem is formulated as

min x∈D E U [flowSD(x, U )] such that x l ≤ x ≤ x u (3) or min x∈D E U [pressureLoss(x, U )] such that x l ≤ x ≤ x u . (4)
In both deterministic and robust formulations, the two performance criteria (pressure loss and flow standard deviation) are handled separately i.e. two shape optimization problems are solved.

The deterministic optimization problem is tackled with an EGO algorithm [START_REF] Jones | Efficient global optimization of expensive black-box functions[END_REF] while the mean response optimization is solved by the specialized "simultaneous optimization and sampling" EGO algorithm described in [START_REF] Janusevskis | Simultaneous kriging-based sampling for optimization and uncertainty propagation[END_REF]. Both algorithms create x iterates by maximizing expected improvements (EI), although these EIs are different in both methods. Bounds on x variables are handled during the EI maximization : our implementation, which makes the Scilab KRISP toolbox (KRIging based regression and optimization Scilab Package, [START_REF] Janusevskis | KRIging Scilab Package[END_REF]), maximizes the EIs with a CMA-ES algorithm [START_REF] Hansen | The CMA evolution strategy: a comparing review[END_REF]. CMA-ES produces new x's by sampling a Gaussian distribution. To handle bounds on x, the sampling is repeated until points are in-bounds.

Deterministic optimization with the original set of shape parameters

A sketch of the original shape parameters definition, i.e., the parameters such as described in the initial test case of the OMD2 project [START_REF]ANR OMD2 project[END_REF], is given in fig. 1. Coordinates of the shape points can be found in table 1. The shape geometry is defined by 13 parameters. The first 5 variables determine the rectangular inner block. The next 8 parameters determine the curvatures of the Bezier curves that connect the inner block to the P3-P4 input and the P10-P9 output parts. The bounds on the design variables are shown in table 2.

The original 13 parameter optimization problem is solved using the EGO algorithm. The initial random Latin Hypercube design (RLHD) [START_REF] Audze | New approach for design of experiments[END_REF][START_REF] Mckay | A comparison of three methods for selecting values of input variables in the analysis of output from a computer code[END_REF] consists of 200 points. 300 additional points are generated by EGO. The obtained optimum designs and associated criterion values are shown in table 3. The design shapes are drawn in fig. 2.

Two observations stem from these original optimizations. Firstly, as can be seen by comparing table 3 and table 2, the optimal designs are obtained for shapes where some of the variables are on the boundary of the design space. For Table 3: Criteria values and design variables of the optimal designs obtained from the original parameter definition. These designs solve eq. ( 1) (first row) and eq. ( 2) (second row). minimum standard deviation of velocity all of the variables are on the boundary of the design space, for minimum pressure drop 6 out of 13 parameters are on the boundary of the design space. Secondly, the current parametrization allows only subset of designs where the extensions of P4P3 and P5P6 cross each other in the positive x direction (it is possible to achieve only shapes where the block P5P6P8P7 is tilted counter clockwise). For these reasons, a new set of shape parameters is defined in the next section.

Optimization with new shape parameters

Anticipating the introduction of uncertain parameters U , we have sought when defining a new set of shape variables x to keep the numerical complexity of the test case limited by reducing the number of variables. A sensitivity analysis has been performed which, in concordance with the rest of this work, is based on kriging. Table 4 shows the scale hyper-parameters θ i estimated by likelihood maximization on the 2D air conditioning duct problem with the initial set of variables. In the current context of Gaussian kernels, the correlation between the performance F at two points x 1 and x 2 is

Corr(F (x 1 ), F (x 2 )) = exp - n i=1 |x 1 i -x 2 i | 2 2θ 2 i
One can see in table 4 that the 8 last θ's estimates are large (actually on their upper bound), suggesting that the correlations are near 1 along these dimensions, i.e. the functions are almost flat in these directions. These last 8 variables correspond to the curvatures of the Bezier curves. In the new set of parameters, Bezier curvatures are therefore removed from the optimization and kept constant to a value such that connections between the inner quadrilateral and the entry and exhaust ducts are almost linear.

The five remaining variables are redefined as illustrated in fig. 3. The pipe consists of 3 rectangular blocks: B1 is a fixed input block, B3 is a fixed output block and B2 is a rectangular block of variable size and position that determines the shape of the pipe. The five shape parameters determine the size and position of the inner block (B2) and are optimized. Such re-parametrization of the problem leads to a more interesting test case as the domain of possible shapes is enlarged. In particular, it should be noticed that the designs of minimum flow standard deviation may only be achieved in the re-parametrized formulation, because their inner block B2 makes a negative angle with the X axis, see fig. 4 and fig. 5.

Deterministic design

Solutions to eq. ( 1) and eq. ( 2) are sought in a design space D ⊂ R 5 with the bounds given in table 5. These problems are approached with the EGO algorithm. During the optimization two practical problems have to be addressed.

Firstly, some of the design points requested by the optimizer cannot be simulated due to geometrical infeasibility or CFD solver errors. We call such points non calculable (infeasible may be confusing as it is often used for points that do not satisfy optimization constraints). For example, geometrical infeasibility occurs when a part of B2 intersects B3 (x 5 is large and simultaneously x 2 and x 4 are small). During the optimization procedure, infeasible geometries should be diagnosed by the automatic mesher and/or the CFD solver software and the optimizer should be updated so as to move away from such non calculable designs. A typical solution is to penalize the performance of such points to force the optimizer away from the non calculable region. For example in the EGO optimizer of [START_REF] Forrester | Optimization with missing data[END_REF], non calculable points are assigned a penalized performance equal to the sum of predicted kriging mean and variance. Here non calculable designs are assigned the predicted kriging 90th percentile, E (Y t (ω))+ 1.282 VAR (Y t (ω)), where Y t (ω) is the conditional gaussian process (the kriging model). At every iteration we learn kriging hyper-parameters without non calculable points. For calculation of EI we use the updated kriging model (with the newly estimated hyper-parameters) and all sampled points, including the non calculable ones with the 90th percentile as performance Table 6: Criteria increase for optimal designs of deterministic formulations when doubling the mesh size.

value.

The second endemic problem is simulation inaccuracies that create false high performance designs: in some cases, our CFD model estimates that a design has a high performance, but the simulation does not properly describe the underlying physics. Examples of such designs are shown in fig. 4. The optimizer is fooled and attracted by these false designs. They are more complicated to diagnose on-line as non calculable designs. A possible test is to modify the numerical model (increase mesh size) and recalculate these designs. Table 6 shows that doubling the mesh size on the deterministic numerical optima of fig. 4 increases their objective functions considerably. The first row in table 6 gives the ever best standard deviation of flow velocity found. The value of 0.1422137 increases to 0.5320028 as the mesh size is doubled. The second row provides the ever best calculated pressure loss criterion which increases from 0.6040481 to 2.355656 as the mesh size is doubled. This fact shows that the first simulations of these designs do not correctly capture the involved physical phenomena. An often useful yet computationally costly test is thus to change the mesh and check that the simulation output is sufficiently stable. It is costly because the simulation needs to be repeated and it is not trivial to decide during an optimization what is "sufficiently stable". Because false designs are also sensitive to shape variations, robust optimization techniques are another way of avoiding them as will be seen in the next section.

Duct design with uncertainties

We now address the problems eq. ( 3) and eq. ( 4) where the uncertain parameter U is introduced and where the mean response is minimized to obtain robust designs.

Definition of the uncertainties

Several definitions of the uncertain parameter U have been tried. At first, we have perturbed the air velocity at the input of the pipe. The perturbation was either a Gaussian noise added to the y velocity component (the x component is zero), or a Gaussian noise added to the x velocity component. Both definitions did not lead to an interesting test case as the designs are not sensitive to perturbations of the input velocity: the deterministic designs, even the false ones of fig. 4, remain optimal. In the final version of the test case, uncertainties affect the duct shape. A gaussian noise is added to the x position of the exit tube B3, cf. fig. 3. The mean and standard deviation of this noise are µ = 0 and σ = 3 (5% of the width of the exit tube), respectively.

Definition of what is the best design in the presence of uncertainties

The definition of the best design at the end of the search deserves further explanations because its performance is not directly observed : during the optimization, the mean performance is estimated through a conditioned and averaged Gaussian process. We define as "best design" that which minimizes the 90% quantile of the mean and which has received at least one observation in deterministic x variable space :

x = arg min x∈X E Z t (x) (ω) + 1.282 VAR Z t (x) (ω) . ( 5
)
where Z t (x) is the mean process

Z t (x) = E U Y t (x,U )
and Y t (x,u) is the kriging (conditional process) build from t observations of the response function, here either the pressure loss or the velocity variation. X is the subset of already calculated deterministic variables, {x 1 , . . . , x t }. Again, more details on the mean process Z can be found in [START_REF] Janusevskis | Simultaneous kriging-based sampling for optimization and uncertainty propagation[END_REF]. By such a procedure the obtained solutions have been observed at least once for the given x and the quantile favors designs that are well known under the kriging usual assumptions. Table 7: Robust designs performance criteria and variation under mesh changes. These designs are solutions to eq. ( 3) and eq. ( 4).

Results

The initial random latin hypercube design of the simultaneous optimization and sampling algorithm [START_REF] Janusevskis | Simultaneous kriging-based sampling for optimization and uncertainty propagation[END_REF] consists of 200 points in six dimensions ((x, u) parameter space made of five x's and one u). The optimization is run for 400 additional points (i.e., 400 iterations).

Using such formulation and optimization approach, the designs represented in fig. 5 are obtained. The performance criteria values of these designs are shown in table 7. By definition, these designs solve the mean performance problems, eq. (3) or eq. ( 4), and thus have better mean objective functions in comparison to the deterministic designs of fig. 4.

In addition, as can be seen in table 7, the robust designs are less sensitive to the mesh sizes. Compared to the deterministic optimization solutions, fig. 4, the obtained shapes, pressure and velocity plots appear smoother without high concentration at isolated locations, suggesting a better correspondence with the actual physical processes. The simultaneous optimization and sampling method for optimization of the mean therefore appears as a way to avoid what we have called false optima. The approach is numerically more efficient than doubling the mesh size at simulated points because, thanks to the kriging, design points do not have to be evaluated twice.

Conclusions

In this report, the simultaneous optimization and sampling method presented in [START_REF] Janusevskis | Simultaneous kriging-based sampling for optimization and uncertainty propagation[END_REF] has been applied to the shape optimization of two-dimensional air conditioning duct. For comparison purposes, the design was first carried out by the EGO algorithm through a deterministic optimization problem formulation. Very high performance designs were calculated, thus confirming that EGO is an appropriate approach for the optimization of computationally expensive models such as CFD. However the obtained designs are very sensitive to the parameters of the numerical model (here the mesh size), which suggests a bad consistency between the physics and the numerical model. The 2D air duct test case has then been reformulated by introducing shape uncertainties. The mean of the duct performance criteria with respect to shape uncertainties have been maximized with the simultaneous optimization and sampling method. The solutions found were not only robust to shape uncertainties but also the CFD model numerical parameters. These

Figure 1 :

 1 Figure 1: Description of the initial shape optimization variables for a 2D air conditioning duct. The first 5 variables determine the position and shape of the rectangular inner block. The next 7 parameters determine the curvature of the Bezier curves (1,2,3,4).

Figure 2 :

 2 Figure 2: Optimal designs of the deterministic problem with the initial 13 shape parameters.

Figure 3 :

 3 Figure 3: Sketch of the 2D air conditioning duct new parameters. 5 variables determine the position and size of the inner block B2. One variable, U 1 , randomly perturbs the horizontal positions of the exit block B3.

  (a) Design maximizing flow uniformity (b) Zoomed in design maximizing flow uniformity (c) Design minimizing pressure loss (d) Zoomed in desing minimizing pressure loss

Figure 4 :

 4 Figure4: Numerically optimal or false designs of deterministic formulation. High performance values are due to locally highly distorted meshes. The performance of these designs is not stable to meshes changes and small shape perturbations.

Figure 5 :

 5 Figure 5: Optimal duct for mean performance under shape uncertainties. Compare them to the deterministic designs in fig. 4. Predicted mean by mean process Original mesh size (19000 cells) Double mesh size (38000 cells) FlowSD 0.1747401 0.1694480 0.2326873 Pressure Loss 1.6154491 1.9856566 2.0780128

Table 1 :

 1 Coordinates of shape points x 8 x 9 x 10 x 11 x 12 x 13

	The

  ).

	FlowSD Pr.Loss	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9	x 10	x 11	x 12 x 13
	0.415	2.024	6.11 31.962 10.146 9.125 65.4	1.6 1.6	36	24	36	36	4	4
	0.481	1.855

6.11 31.962 10.156 8.257 54.45 1.77 2 34.443 24 25.926 27.398 4 4

Table 4 :

 4 Kriging scale hyper-parameters θ i for Gaussian covariance kernel for 498 points LHD. Estimation based on likelihood maximization. Parameters are rescaled to (0, 1].

	x 1 x 2	x 3	x 4 x 5
	Lower bound 10 160 80 160	1
	Upper bound 79 210 149 210 50

Table 5 :

 5 Bounds on new design variables.

Table 8 :

 8 Shape parameters for obtained optimal designs using uncertainty formulation.For designs obtained by minimizing mean response see table8.

	Optimization criteria	x 1	x 2	x 3	x 4	x 5	OpenFoam folder for design
	FlowSD	23.919734	210.	141.33995 180.32402 37.224836	./OpenFoam/rego x 1
	Pressure Loss	66.519997 180.24888 116.82942 198.99101	17.905	./OpenFoam/rego x 2
	6.2 Running robust optimization
	rego OpenFoam.sce
	6.3 Optimal robust designs

design show that the method is of practical interest in engineering tasks.

Appendix: conditioner test case implementation

The test case was implemented using OpenFoam and Scilab code which is submitted along with this report as a deliverable.

Assumptions about OpenFoam installation

The attached code is working with Scilab version 5.2 and OpenFOAM version 1.6. It uses OpenFoam executables blockMesh for mesh generation and simpleFoam for solving. The OpenFoam case is defined under folder ./OpenFoam/. The Scilab scripts for generating test case are located in forlder ./scilab/. The Scilab code implementing the minimization of mean response is located in folder ./rego toolbox/. It uses Scilab kriging package KRISP [START_REF] Janusevskis | KRIging Scilab Package[END_REF] and CMAES toolbox [START_REF] Hansen | CMA-ES Source Code[END_REF].


Benoît Rittaud

Laurent Vivier
email: laurent.vivier@univ-orleans.fr

Keywords: 2010 Mathematics Subject Classification. Primary 68R15, Secondary 11A63, 11E95, 37B10 Fibonacci numeration system, words, Fibonacci substitution, adic representation

  L'archive ouverte pluridisciplinaire

CIRCULAR WORDS AND THREE APPLICATIONS: FACTORS OF THE FIBONACCI WORD, F -ADIC NUMBERS, AND THE SEQUENCE 1,5,16,45,121,320,. . .

BENO ÎT RITTAUD AND LAURENT VIVIER

Abstract. We introduce the notion of circular words with a combinatorial constraint derived from the Zeckendorf (Fibonacci) numeration system, and get explicit group structures for these words. As a first application, we give a new result on factors of the Fibonacci word abaababaabaab . . .. Second, we present an expression of the sequence A004146 of [S] in terms of a product of expressions involving roots of unity. Third, we consider the equivalent of p-adic numbers that arise by the use of the numeration system defined by the Fibonacci sequence instead of the usual numeration system in base p. Among such F -adic numbers, we give a characterization of the subset of those which are rational (that is: a root of an equation of the form qX = p, for integral values of p and q) by a periodicity property. Eventually, with the help of circular words, we give a complete description of the set of roots of qX = p, showing in particuler that it contains exactly q F -adic elements.

Classically, a (finite) word is a finite sequence of elements (or letters) of a given set, the alphabet. Here, we mean by circular word a finite word w 0 . . . w n in which the last letter, w n , is assumed to be followed by the first one, w 0 . This definition gives rise to interesting properties when circular words are assumed to be admissible, that is, made of letters in the alphabet {0, 1} without any two successive letters equal to 1. These properties derive from an underlying algebraic structure: the set of admissible circular words of fixed even length is an abelian group, which can be explicitely written as a product of finite monogenetic groups.

One of the properties of circular admissible words of length 2ℓ is that their cardinality c ℓ is given by the sequence A004146 of [S] (which starts by 1, 5, 16, 45, 121, 320,. . . ), which has many important combinatorial properties (see [R]). The link between this sequence and admissible circular words appears also in the sequence of determinants of a sequence of linear operators we consider for our study. This fact gives rise to a formula that expresses each element of the sequence A004146 as an explicit product of expressions of the form 1 -α -α 2 , where α is a root of unity.

Another application of circular words is the study of factors of the Fibonacci word M = abaababaabaab . . ., defined as the only fixed point of the substitution a → ab and b → a. It appears that admissible circular words are closely linked to this word, and the underlying arithmetic on these objects allows to write the word bM in the form A (1) . . . A (q) M ′ , where all the A (q) s are of length k and contain the same number of a (and, thus, also the same number of b), where k and q are explicit (and non-trivial) numbers.

A third application of circular words deals with what we call F -adic numbers. For any integer p > 1, the set of p-adic integers is obtained by considering the projective limit of the sequence of sets (Z/p n Z) n . In an intuitive way, it corresponds to numbers whose "integral part" is made of infinitely many digits in base p. Such a projective limit still makes sense for other numeration systems, as for example numeration systems in non-integers bases (see [AF]). We consider here the case of the Zeckendorf numeration system: define the Fibonacci sequence (F n ) n by F 0 = 1, F 1 = 2 and F n = F n-1 +F n-2 for any n ≥ 2. For any integer N, there exists a unique sequence (w n ) n≥0 of 0s and 1s such that w n w n+1 = 0 for any n (this property makes the sequence an admissible one) and such that N = n w n F n . Such a sequence has the property that, for some n 0 , w n = 0 for all n ≥ n 0 . Considering a sequence (w n ) n without this latter property leads to F -adic numbers. It is worth noting that, contrarily to the case of p-adic numbers, we do not need to consider any "fractional part" to deal with F -adic numbers.

In [GLT], Peter Grabner, Pierre Liardet and Robert Tichy investigated F -adic numbers and generalizations by taking a dynamical standpoint. Here, we take a number-theoretic perspective, considering the set of Fadic numbers as a number set. We define an addition on the set of F -adic numbers and investigate the properties of rational F -adic numbers, that is, F -adic numbers X such that, for some integers p and q, qX = p. Circular words, then, appear to be a natural tool to investigate such rational F -adic numbers, since their set corresponds to the set of F -adic numbers whose expansion is ultimately periodic. The proof involves tools from algebra and combinatorics on words. As an application of circular words, together with the use of some more algebra, we show that the equation qX = p (with X F -adic number and p, q integers) has q or (q + 1) F -adic roots, depending only on whether p/q is an integer or not.

Of course, it would be possible to consider other constraints on circular words or F -adic numbers than the Zeckendorf one. We will not address here a general theory, and postpone to another paper some results in some of these more general cases.

General definitions and notations

1.1. Words. A word W is a sequence of elements of some fixed set, called the alphabet, which will be always made of integral numbers (with only one exception in section 3.1). A word can be finite or infinite, and we usually write it as W = w 0 . . . w n = w n 0 for a finite word, W = w ∞ 0 = w 0 . . . w n . . . for an infinite word (note that the set of indices always starts at 0). The w i s are the letters of W , w i is the letter of rank i in W . The notation ∅ stands for the empty word. The length |W | of a word W is the number of its letters (so

|w n 0 | = n + 1 and |w ∞ 0 | = +∞).
For W a word and a a letter of its alphabet, |W | a stands for the number of occurrences of a in W (which may be infinite). For any word on an alphabet A, we have

|W | = a∈A |W | a .
For W = w n 0 , we write Σ(W ) := n i=0 w i = a∈A a|W | a . Two words W and W ′ being given with W finite, the notation W W ′ stands for the concatenation of W and W ′ . We also put W 0 := ∅, W 1 := W and, for any n ≥ 2, W n := W W n-1 . We write W ∞ for the infinite word made of infinitely many copies of W . The word W ∞ (resp. V W ∞ for a finite word V ) is periodic (resp. ultimately periodic), and W is its period. Frequently in the sequel, a finite word W of length ℓ will have to be considered as a word of length ℓ + ℓ ′ , or even as an infinite word of period 0, by identifying W with W 0 ℓ ′ or W 0 ∞ . Let V and W be two words, with V finite. We say that V is a factor of W if there exists two words X and Y such that W = XV Y . The word V is a prefix (resp. suffix) of W if X = ∅ (resp. Y = ∅, which implies that W is finite). The notation W n stands for the prefix of length n of the word W , with W 0 := ∅.

A finite word W = w n 0 is palindromic iff, for any 0 ≤ i ≤ n, we have

w i = w n-i .
Let W := w n 0 and W ′ := w ′ n ′ 0 be two words with (without loss of generality) n ≥ n ′ (with n and n ′ possibly infinite). The sum W + W ′ is the word such that its i-th letter is w i + w ′ i for i from 0 to n (the letter w ′ i for i > n ′ being defined as 0, identifying W with W 0 n ′ -n as said previously).

Admissible words.

A word W = w n 0 or w ∞ 0 on the alphabet {0, 1} is admissible iff w i w i+1 = 11 for any i.

We define (F n ) n as the following Fibonacci sequence: F 0 = 1, F 1 = 2 and, for any n ≥ 2, F n := F n-1 + F n-2 . The Zeckendorf numeration system is the function that associates to each nonnegative integer k the only finite admissible word

Z(k) = w n(k) 0 satisfying k = n(k)
i=0 w i F i with w n(k) = 1. A classical result asserts that the word Z(k) is obtained by the natural greedy algorithm, and that Z is one-to-one from the set of nonnegative integers to the set of finite admissible words ending with a 1. The reciprocal function of Z is written N.

Two finite words W := w n 0 and W ′ := w ′ 0 n ′ on the alphabet N are equiv-

alent iff i w i F i = i w ′ i F i .
We write W ≡ W ′ in this case. What precedes indicates that to any finite word W corresponds a unique admissible word equivalent to it, again written Z(W ). For infinite words W and W ′ , we write W ≡ W ′ iff there exists two finite words X and X ′ and an infinite word Y such that X ≡ X ′ , W = XY and W ′ = X ′ Y .

For any finite admissible word V , we write V for the unique finite admissible word such that Z(V + V ) = 0 |V | 1. (Of course, we cannot use the identification of V and V 0 n when considering V .)

Let W be a word on the alphabet {0, 1}, finite or infinite, different from the null sequence. The valuation of W is the value

Val(W ) := min(n ≥ 0 : W n = 0 n ).
Define the following transformations on words W = w n 0 on the alphabet N:

τ 1 (W ) :
   w 0 := w 0 -2, w 1 := w 1 + 1, w i unchanged for i ≥ 2; and, for k ≥ 2:

τ k (W ) :        w k := w k + 1, w k-1 := w k-1 -1, w k-2 := w k-2 -1, w i unchanged for i / ∈ {k -2, k -1, k}.
Let W := w n 0 be an admissible word, and let m ≥ 0. The following reduction algorithm takes W and m as input, and returns W := Z(W +0 m 1) as an output (the proof is a routine):

• Initialization: put w m := w m + 1, and i := m; • while w i = 2 and i ≥ 1, do

-put W := τ i+1 • τ -1 i (W ); -put i := i -2; • if w 0 = 2 then put w 0 w 1 := 01; • while E := {k : w k-1 w k-2 = 11} is non empty, do -put i := max(E); -put W := τ i (W ).
We will very often make implicit use of the following result:

Proposition 1.1. [Ultimate stationnarity principle] For any finite word W on the alphabet N there exists a finite admissible word A(W ) and a value a(W ) ≥ 0 such that, for any n ≥ a(W ), we have Z(0 n W ) = 0 n-a(W ) A(W ).

Proof. Assume that the ultimate stationnarity principle is true for any word W such that Σ(W ) ≤ j for some j, and consider a word W such that Σ(W ) = j + 1. We find m ≥ 0 such that W = W ′ + 0 m 1, where W ′ is a word on N. By induction hypothesis, for some admissible word A = A(W ′ ) and some a = a(W ′ ) ≥ 0, for any n ≥ a, we have Z(0 n W ′ ) = 0 n-a A. Hence, we have Z(0 n W ) = Z(0 n-a A + 0 m+n 1).

Observe that, for any finite word W , any i ≥ 2 and any m ≥ 0, we have τ i+m (0 m W ) = 0 m τ i (W ), so the ultimate stationnary principle is true for the finite word W iff it is true for τ i (W ) (i ≥ 2). Hence, if, in the execution of the previous reduction algorithm (when applied to the word 0 n-a A and the value m + n), we always get i ≥ 2, then the proposition is true for W .

The case for which the algorithm leads to i = ε ∈ {0, 1} is when we get this equality just after the end of the iteration of the first while loop. A simple verification shows that this occurs only if 0 n-a A + 0 m+n 1 is of the form 0 ε (10) k 20X with X admissible and k ≥ 0. We hence have 0 (n+2)-a A + 0 m+(n+2) 1 of the form 0 2+ε (10) k 20X, for which the reduction algorithm does never leads to w 0 = 2 or w 1 = 2. We thus have proved that a(W ) ≤ a(W ′ ) + 2.

Lemma 1.1. If W and W ′ are finite admissible words, then Val(Z(W W ′ )) ≥ Val(W ). Moreover, Val(Z(W W ′ )) > Val(W ) iff W = 0 n 1 for some n ≥ 0 and Val(W ′ ) = 0.

Proof. Immediate.

Lemma 1.2. Let V and V ′ be two finite admissible words. We have

|Z(V + V ′ )| ≤ 2 + max(|V |, |V ′ |).
Proof. Since V and V ′ are admissible, we have

N(V ) < F |V | and N(V ′ ) < F |V ′ | , so, assuming without loss of generality that |V | ≥ |V ′ |, we get N(V + V ′ ) ≤ 2(F |V | -1) < F |V |+2
, so we get the lemma.

Lemma 1.3. Let W be a finite word on the alphabet {0, 1}. We have Val(Z(W )) ≥ Val(W ). Moreover, Val(Z(W )) -Val(W ) is even.

Proof. To get Z(W ) from W , we can apply the second loop of the previous algorithm. Each time we apply some τ i , the valuation either remains constant or increases by two units, so we get the result.

Proposition 1.2. Let W be a finite admissible word such that Val(W ) ≥ 2, let m ≥ 2. There exists an integer n ≥ -1 such that Val(Z(W + 0 m 1)) = Val(W ) + 2n. Moreover, n = -1 iff W + 0 m 1 is of the form 0 r (10) s 20W ′ with W ′ admissible.

Proof. For any i ≥ 2, Val(τ i (W )) is equal either to Val(W ) or to Val(W ) + 2 (and, so, Val(τ -1 i (W )) equal either to Val(W ) or to Val(W ) -2). By the previous algorithm, we then get that Val(Z(W + 0 m 1)) ∈ Val(W ) + 2Z. The inequality Val(Z(W + 0 m 1)) < Val(W ) can occur only if we need to go into the first loop of the algorithm, to apply some τ -1 i . Consider the first iteration of this loop for which the valuation of W decreases (of two units). This means that, at that moment of the algorithm, W is of the form 0 u 20W ′ (with W ′ a word on {0, 1}) and becomes 0 u-2 1001W ′ . There is then no letter 2 anymore, and the iteration of the second loop will only involve the part 1W ′ of the word and will not change the valuation. Hence, we have proved that n ≥ -1.

Finally, if Val(Z(W + 0 m 1)) = Val(W ) -2, then we must have went through the first loop to get the form 0 u 20W ′ ; a simple induction shows that this forces W + 0 m 1 to be of the required form.

Corollary 1.4. Let W and W ′ be two finite admissible words such that m := min(Val(W ), Val(W ′ )) ≥ 2. There exists an integer i ≥ -1 such that Val(Z(W + W ′ )) = m + 2i. Moreover, we have

Val(Z(W + W ′ )) = m -2 ⇐⇒ W + W ′ = 0 m (10) n 20(U + U ′ )
where n ≥ 0 and U (resp.

U ′ ) is the suffix of W (resp. of W ′ ) of length max(0, |W | -(m + 2n + 2)) (resp. max(0, |W ′ | -(m + 2n + 2))).
The proof is left as an exercice.

Circular words

2.1. Generalities. A finite word W := w n 0 being given (on some alphabet), we denote by σ(W ) the word w n w 0 . . . w n-1 . Define the circular equivalence ≈ between finite words by:

W ≈ W ′ ⇐⇒ σ k (W ) = W ′ for some k.
A circular word is an ordered set of the form [W, σ(W ), . . . , σ |W |-1 (W )], for a chosen finite word W . For any finite word W , we denote by W the circular word containing W as a first element. Its length, | W |, is defined as the length of W . A circular word is a power if we can write it of the form X k for some word X and some integer k > 1. It is primitive if it is not a power. A circular word W := w n 0 on the alphabet {0, 1} is admissible if w i mod (n+1) w (i+1) mod (n+1) = 11 for any i.

For W and W ′ two circular words, we put W W ′ := W W ′ . We define the transformations τi on circular words W on the alphabet N and of length at least 3 (with

W = w |W |-1 0 ) by τi ( W ) = W ′ , where W ′ = w ′ |W |-1 0 is defined by: w ′ j :=        w i mod |W | + 1 for j = i mod |W |; w (i-1) mod |W | -1 for j = (i -1) mod |W |; w (i-2) mod |W | -1 for j = (i -2) mod |W |; w j
for any other j.

For W and W ′ belonging to the same orbit under the τ i s, we write W ≡ W ′ and say that these words are equivalent.

For any circular word W , we define Ñ( W ) := N(W ).

Proposition 2.1. Let W be a circular word on N of length at least 2 and not equivalent to 1 2n+3 (n ≥ 0). There exists a unique admissible circular word Z( W ) equivalent to W , assuming the identification (01) n = (10) n for any n.

If W = 1 2n+3 , then its orbit under the τ i s does not contains any admissible circular word.

Proof. We start by the existence. Assume W contains only 0s and 1s. If it does contains at least one 0, then we write W as a circular concatenation of subwords of the form 10 k (with k > 1), 1 k 0 n (with k > 1 and n ≥ 1) and ( 10) n (with n ≥ 1), possibly adding the prefix 0 k (with k ≥ 1). We then make use of the τ i s to reduce each 1 k 0 n either into 0(01) k/2 0 n-1 (for k even) or into 10(01) (k-1)/2 0 n-1 (for k odd). Such an operation makes the number of 1s becoming strictly less, so its iteration eventually ends, and leads to a circular word with only 0s and 1s and free of any factor of the form 11, so an admissible word. If W = 1 2ℓ , then we have

τ 0 • τ 2 • • • • • τ 2(ℓ-1) ( W ) = (10) ℓ ; note that we also have τ 1 • τ 3 • • • • • τ 2ℓ-1 ( W ) = (01) ℓ , which justifies the identification (01) n = (10) n .
Now, let W be admissible and consider W + 0 i-1 10 i-| W | for some i > 0. This latter word is either on {0, 1} (then we are done, by what precedes), or on {0, 1, 2} with exactly one 2, surrounded by two 0s, and nowhere the factor 11. The rank of the letter 2 is i. Apply τ i+1 • τ -1 i (from now, all the indices are to be understood modulo | W |). The factor w i-2 020 of W is then replaced by (w i-2 + 1)001. If w i-2 = 0, then we are back to a word on {0, 1} and we are done. Otherwise, we iterate the same process at the rank i -2, then i -4, etc., until we get a word on {0, 1} (so we are done) or we get a 2 at the rank i + 1. In this latter case, we get that W + 0 i-1 10 | W |-i is of the form (10) n 200, which is equivalent to 1 2n+3 . Then, for any value j, we have j+2) , which is admissible.

W + 0 i-1 10 | W |-i + 0 j-1 10 | W |-j ≡ 1 j-1 21 | W |-j ≡ 0 j-3 10 | W |-(
Hence, iterating the process of adding words of the form 0 i-1 10 | W |-i and reducing the result either leads to an admissible word or leads to 1 2n+3 ; this gives us the existence part of the proposition. Now, let us consider the unicity part.

Lemma 2.1. The circular word 0 ℓ is equivalent to no other circular word on N.

Proof. Let W be a finite word on N with W = w n 0 containing at least one letter different from 0. For any τ i or τ -1 i that can be applied to W , the number of letters different from 0 cannot become null, so we are done.

Let W and X be two equivalent admissible circular words of length n + 1. Regardless of the negative values possibly involved in the following expression, write

X = τ a 0 0 • • • • • τ an n ( W )
, with integer values for all the a i s. Write A for the vector (a i ) 0≤i≤n and define the linear operator M = (m ij ) i,j on R n+1 by m i,i = 1, m i,((i+1) mod (n+1)) = -1 and m i,((i+2) mod (n+1)) = -1 for any 0 ≤ i ≤ n.

Lemma 2.2. For any i, we have -1 ≤ a i ≤ 1.

Proof. For any i, we have x i = w i + (MA) i . Hence, since w i and x i are equal to 0 or 1, we have -1 ≤ (MA) i ≤ 1 for any i. Moreover, since x i x i+1 = 11, we have (MA) i = 1 ⇒ (MA) i+1 ≤ 0 and, since w i w i+1 = 11, we have (MA) i = -1 ⇒ (MA) i+1 ≥ 0 (in the present proof, all the indices are to be understood mod n + 1).

Without loss of generality, assume a 0 =: a = ||A|| ∞ . We write MA =:

B := (b i ) n i=0 . The inequalities |a -a 1 -a 2 | = |b 0 | ≤ 1, |a 1 | ≤ a and |a 2 | ≤ a implies |a 1 | ≥ -1. The inequalities |a n -a -a 1 | = |b n | ≤ 1, |a n | ≤ a and |a 1 | ≤ a implies a 1 ≤ 1. If a 1 = 1, then b n = a n -(a + 1), so, since b n ≥ -1, we get a n = a. Hence, since a n-1 ≤ a, we get b n-1 = a n-1 -a n -a = a n-1 -2a ≤ -a < -1, which is forbidden. If a 1 = 0, then |b n | = a n -a, so a n = a or a-1. If a n = a, then b n-1 = a n-1 -2a ≤ -a < -1, a contradiction.
Hence, a n = a -1, which gives b n = -1 and b n-1 = a n-1 -2a + 1 < 0, also a contradiction.

Therefore, we have proved that a 0 = a = ||A|| ∞ implies a 1 = -1. Hence, b 1 = a + 1 -a 2 , so a 2 = a. By induction, we then get that a 2i+1 = -1 and a 2i = a for any i, so b 1 = a 1 -a 2 -a 3 = -a < -1, a contradiction, and the lemma is proved.

Lemma 2.3. Let W be a circular word of length n > 3 on N. For any i, we have

N(τ i ( W )) =      N( W ) for 2 ≤ i ≤ n; N( W ) + 1 -F n for i = 1; N( W ) + 1 -F n+1 for i = 0.
Proof. Simple verification. By Lemma 2.3, there exists two integers a 0 and a 1 such that

N( W ) = N( X)+a 0 (1-F n+1 )+a 1 (1-F n ). By Lemma 2.2, we also have max(|a 0 |, |a 1 |) ≤ 1.
Without loss of generality, we assume N( W ) ≤ N( X). Recall also that both N( W ) and N( X) are upper-bounded by F n+1 -1. All these conditions can be satisfied only in the following cases: (a 0 , a 1 ) = (0, -1), (-1, 0), (0, 0) and (-1, 1).

The case (a 0 , a 1 ) = (0, 0) gives N( W ) = N( X), that is N(W ) = N(X), which implies W = X by unicity of the Zeckendorf expansion. For (a 0 , a 1 ) = (-1, 0), we get N( X) -N( W ) = F n+1 -1, so W = 0 n+1 and X is of the form . . . 01010101 (which implies that n is even, otherwise X would not be admissible). By Lemma 2.1, W and X are not equivalent. For (a 0 , a 1 ) = (-1, 1), the condition -1 ≤ (MA) i ≤ 1 for all i gives by a simple induction that a i = (-1) i+1 for all i. This gives that x i = w i + (-1) i+1 for any i, so W = (10) (n+1)/2 and X = (01) (n+1)/2 . The last remaining case is (a 0 , a 1 ) = (0, -1), for which we have N( X) -N( W ) = F n -1. Extending the definition of the τi s to circular words on Z makes the τ i s commuting, so we can write τ a 0 0 • • • • • τ an n ( W ) = X, and we can apply the τi s in any order. Since a 0 = 0 and a 1 = -1, we get

(1) X = τ a 2 2 • • • • • τ an n ((w 0 + 1)(w 1 -1)w 2 . . . w n-1 (w n + 1
)) (in which we write circular words as classical words). Note that, for any i, the only values j for which the application of τj changes the letter of rank i are j = i, i + 1 and i + 2 mod(n + 1). Hence, if w 0 = 1 (so w 1 = 0), then Equation (1) forces a 2 = 1, which gives

X = τ a 3 3 • • • • • τ an n (1(-2)(w 2 + 1)w 3 . . . w n-1 (w n + 1)).
The value -2 at the rank number 1 cannot become 0 or 1 with the remaining τi s, since only the operator τ a 3 3 can change its value, adding at most 1 to it. Hence, we cannot have w 0 = 1, so w 0 = 0. Thus, we have

(2) X = τ a 2 2 • • • • • τ an n (1(w 1 -1)w 2 . . . w n-1 (w n + 1)).
Since the latter word starts with a 1 and ends with w n + 1 ≥ 1, and since the only operator that can still be used to avoid these two successive (circularily) positive letters is τ -1 n , we have a n = -1, and:

(3

) X = τ a 2 2 • • • • • τ a n-1 n-1 (1(w 1 -1)w 2 . . . w n-3 (w n-2 + 1)(w n-1 + 1)w n ).
The admissibility condition then gives that w n = 0. If w n-1 = 1 (then w n-2 = 0), then a simple checking show that no pair (a n-2 , a n-1 ) of numbers among -1, 0 and 1 can transform this part of the word into an admissible word (and the τi for i < n -2 are of no effect on this part of the word). Hence, we must have w n-1 = 0. Now, if w n-2 = 1, then (w n-2 + 1)(w n-1 + 1)w n = 210 and, again, a checking shows that no pair (a n-2 , a n-1 ) of numbers among -1, 0 and 1 can transform this part of the word into an admissible word. Hence, w n-2 = 0, so (w n-2 +1)(w n-1 +1)w n = 110. Thus, we cannot have

a n-1 = 1. If a n-1 = -1, then (4) X = τ a 2 2 • • • • • τ a n-2 n-2 (1(w 1 -1)w 2 . . . w n-4 (w n-3 + 1)200),
which leads to the same problem that appeared previously. Hence, a n-1 = 0, so a n-2 = -1 and

(5)

X = τ a 2 2 • • • • • τ a n-3 n-3 (1(w 1 -1)w 2 . . . w n-5 (w n-4 + 1)(w n-3 + 1)010).
Iterating the reasoning eventually leads to:

X = τ a 2 2 τ a 3 3 (1(w 1 -1)(w 2 + 1)(w 3 + 1)01010 . . . 1010) if n is even; τ a 2 2 τ a 3 3 τ a 4
4 (1(w 1 -1)w 2 (w 3 + 1)(w 4 + 1)01010 . . . 1010) if n is odd, with w i = 0 for all i ≥ 4 for n odd and all i ≥ 5 for n even.

Take n even. By the same kind of reasoning, we successively get w 3 = 0, then w 2 = 0, so 1(w 1 -1)(w 2 + 1)(w 3 + 1) = 1(w 1 -1)11. A check then shows that no pair (a 2 , a 3 ) can give an admissible circular word in the right hand side of the previous equality. Now, consider the case n odd. We also get successively w 4 = 0, then w 3 = 0, then a 4 = 0, then a 3 = -1, then a 2 = 0, then w 2 = 0 and finally w 1 = 0, so W = 0 |W | and X = (01) (n+1)/2 , a contradiction with Lemma 2.1. Hence, the unicity is proved.

Finally, let us consider the case W = 1 2n+3 . Assume that 1 2n+3 ≡ X, where X is admissible, and write

X = τ a 0 0 • • • • τ a 2n+2 2n+2 ( 1 2n+3
). Since 1 2n+3 is invariant under σ, the words σ k ( X) are admissible and equivalent circular words for any k. Moreover, since X is not of the form x 2n+3 (x = 1 would give a non-admissible word, and x = 0 would contradict Lemma 2.1), the set {σ k ( X) : k ≥ 0} has cardinality at least two, a fact which contradicts the unicity we just proved.

2.2. Group structures. We define the operator ⊕ between circular admissible words of the same even length, W and W ′ , by: W ⊕ W ′ := Z( W + W ′ ). We will also write, for any n ≥ 1, n

• W := ((n -1) • W ) ⊕ W , with 0 • W := (01) |W |/2 .
Theorem 2.4. Define the sequences (c ℓ ) ℓ≥1 and (d ℓ ) ℓ≥1 by:

c 1 := 1 c ℓ := F 2ℓ-1 + F 2ℓ-3 -2 for ℓ ≥ 2; d 1 := 1 d ℓ := F ℓ-2 if ℓ > 1 is even; F ℓ-1 + F ℓ-3 if ℓ > 1 is odd.
For any n ≥ 1, we have c 2k+1 = d 2 2k+1 and c 2k = 5d 2 2k . The set G * ℓ of circular admissible words of length 2ℓ excluding 0 2ℓ and with the identification (01) ℓ = (10) ℓ is an abelian group for the addition ⊕, with (01) ℓ = (10) ℓ as identity element. More precisely, this group has cardinality c ℓ and is isomorphic to (Z/d ℓ Z) 2 for odd ℓ, and isomorphic to (Z/5d ℓ Z) × (Z/d ℓ Z) for even ℓ.

The star * is here to recall that the word 0 2ℓ is not considered (in particular, it is not the identity element).

It is worth noting that the sequence (c ℓ ) ℓ defined in Theorem 2.4 possesses numerous combinatorial properties (see [R]); it corresponds to the integer sequence A004146 in [S].

Proof. The relations c 2k+1 = d 2 2k+1 and c 2k = 5d 2 2k are trivial consequences of the classical Binet formula F n = (ϕ n+2ϕ n+2 )/ √ 5 for any n (where

ϕ = (1 + √ 5)/2 and ϕ = (1 - √ 5)/2). By Lemma 2.1, if W and W ′ are elements of G * ℓ , then W ⊕ W ′ is also an element of G * ℓ (that is: W ⊕ W ′ = 0 2ℓ ), so ⊕ is well-defined in G * ℓ .
Observe that any element of G * ℓ can be written as a (unique and finite) sum (in the usual sense) of words of the form 0 k 10 2ℓ-k-1 . To prove that (01) ℓ = (10) ℓ is the identity element, by the associativity (and commutativity) of ⊕, it is therefore enough to show that 0 k 10 2ℓ-k-1 ⊕ (10) ℓ = 0 k 10 2ℓ-k-1 ⊕ (01) ℓ = 0 k 10 2ℓ-k-1 , and these latter equalities are obtained by straightforward computations. Also, since 0 2k 10 2(ℓ-k)-1 (resp. 0 2k+1 10 2(ℓ-k-1) ) admits (10) k 00(10) ℓ-k-1 (resp. (01) k 00(10) ℓ-k-1 ) as an opposite element, we obtain that G * ℓ is an abelian group for ⊕. Now, let us consider the cardinality of G * ℓ . We first count the number of admissible words of length 2ℓ, excluding those which starts and ends with a 1. We split this latter set in two subset: the first one is made of words not ending with a 1, its cardinality is equal to 1 + N(1(01) ℓ-1 ) = F 2ℓ-1 . The second one is made of words ending with 01 and starting with a 0, its cardinality is equal to the cardinality of admissible words of length 2ℓ-3 (by the bijection W -→ 0W 01), which is equal to F 2ℓ-3 . Hence, the number of admissible words of length 2ℓ not both starting and ending with a 1 is equal to F 2ℓ-1 + F 2ℓ-3 . To get the cardinality of G * ℓ , it only remains to suppress the word 0 2ℓ and to identify (01) ℓ with (10) ℓ , which eventually leads to the value c ℓ .

To prove the end of the theorem, note first that the circular words 10 2ℓ-1 and 010 2ℓ-2 generate the full group G * ℓ . Indeed, the relation F k-1 • ( 10 2ℓ-1 ) + F k • ( 010 2ℓ-2 ) = 0 k+2 10 2ℓ-k-5 for any k ≥ 0 (with F -1 := 1) proves that the subgroup generated by these two words contains the set of words with only one 1, which obviously generates G * ℓ itself. Hence, G * ℓ is an abelian group generated by at most two elements.

Assume ℓ = 2k + 1. By induction, we easily get that d ℓ = v ℓ , where v ℓ is defined in the proof of Lemma 4.1 (see section 4.1). By the same technique as in the proof of this lemma, we obtain that Z( d ℓ • (10 2ℓ-1 )) = ( 10 Assume ℓ = 2k. Again by the same kind of technique, we get this time that Z( 5d ℓ • (10 2ℓ-1 )) = (10) ℓ . Hence, G * ℓ is of the form (Z/aZ) × (Z/bZ) with ab = 5d 2 ℓ and max(a, b) ≤ 5d ℓ , so we are done.

In passing, a simple way to find the opposite of an element W = w 2ℓ-1 0 of G * ℓ is the following (see also the proof of Theorem 4.4): define the word W ′ as the word whose i-th letter is equal to 1 -w i (for all 0 ≤ i < 2ℓ). We then easily verify that: -W = Z( W ′ ).

We can get natural embeddings between the groups G * ℓ by making use of the following result.

Proposition 2.2. Let k and ℓ be positive integers. The application W -→ W k is a morphism from G * ℓ into G * kℓ .

Proof. Simple verification.

Let W and W ′ be circular admissible words, non necessarily of the same length. By Proposition 2.2, we can put both W and W ′ in the same G * ℓ , by a convenient choice of k for each word. This allows us to extend the definition of the operator ⊕ to words W and W ′ of possibly different (even) lengths, in the following way:

W ⊕ W ′ := Z W m/|W | + W ′ m/|W ′ | , where m = lcm(|W |, |W ′ |).
Theorem 2.5. For q ≥ 1, let P * q be the set of circular admissible words W of even length, containing at least one 1 and satisfying qW = (01) |W |/2 . Assume also the identifications (01) n = (10) n and W = W n for any n. The set P * q equipped with the addition ⊕ is an abelian group isomorphic to (Z/qZ) × (Z/qZ).

Proof. The fact that P * q is a group for ⊕ is trivial. Hence, for any ℓ, the subset of P * q made of words of length 2ℓ is a subgroup of G * ℓ .

Lemma 2.6. For any q ≥ 2, there exists an ℓ such that q divides d ℓ .

Proof. Consider the sequence of pairs (G i , G i+1 ) := (F i mod q, F i+1 mod q) for all i ≥ 0. Since there are finitely many pairs of integers between 0 and q -1, we can find two different values, i and j, such that (G i , G i+1 ) = (G j , G j+1 ), so the definition of the sequence implies that (G i , G i+1 ) i is ultimately periodic. Moreover, for any pair (a, b) of integers between 0 and q -1, the pair ((b -a) mod q, a) is the only pair (y, z) for which there can be an i such that (a, b) = (G i , G i+1 ) and (y, z) = (G i-1 , G i ). Hence, the sequence (G i , G i+1 ) i is purely periodic, and we can find a value m > 1 such that (G m+1 , G m+2 ) = (F 0 mod q, F 1 mod q) = (1, 2). We then get that

(G m , G m+1 ) = (1, 1), so (G m-2 , G m-1 ) = (-1, 0). Therefore, if m -1 is even, then q divides d ℓ := d m-1 = F m-1 , and if m -1 is odd, then q divides d ℓ := d m+2 = F m + F m-2 .
The value of q being given, we fix by Lemma 2.6 an ℓ such that q divides d ℓ . By Theorem 2.4, the maximal subgroup M ℓ of elements of G * ℓ of order q is (Z/qZ) × (Z/qZ). and b → a. For ℓ > 2, let N ℓ := bM F 2ℓ-2 . Define the words A (1) , . . . , A (k) by

N ℓ = A (1) • • • A (k) a and |A (i) | = d ℓ , where k = F 2ℓ-2 /d ℓ . The value |A (i) | a (and, hence, the value |A (i) | b ) does not depend on i ≤ k.
It is highly probable that, defining A as the word of length

d ℓ such that bM = A 1 • • • A k AM ′ , we have |A| a = |A (i) | a . Also, we can get that |A (i) | a = d ′ ℓ-2 and |A (i) | b = d ℓ-1 .
We will not prove this here. Note that the fact that F 2ℓ-2 /d ℓ is an integer is a direct consequence of Lemma 2.8.

Definition 3.2. Let W ∈ G * ℓ different from the identity element, let X ∈ {(10) ℓ , (01) ℓ , (11) ℓ }. We say that W is of type X iff Ñ( W ) + Ñ(-W ) = N(X).
We denote by T * X the set of elements of type X in G * ℓ . For X ∈ {(01) ℓ , (10) ℓ }, we also put T X := T * X ∪ {X}.

Proposition 3.1. Let W and W ′ be two elements of T * X for some X ∈ {(10) ℓ , (01) ℓ , (11) ℓ }. We have

Ñ ( W ) + Ñ ( W ′ ) = N(X) ⇐⇒ W = -W ′ .
Proof. Simple consequence of the injectivity of N. Proposition 3.2. We have

T (10) ℓ ∪ T (01) ℓ ∪ T * (11) ℓ = G * ℓ .

More precisely:

(i) The set T (10) ℓ is the set of circular words W ∈ G * ℓ such that W admits 0 2m 1 as a prefix (for some m ≥ 0) and 0 as a suffix. (ii) The set T (01) ℓ is the set of circular words W ∈ G * ℓ such that W admits 0 2m+1 1 as a prefix (for some m ≥ 0). (iii) The set T * (11) ℓ is the set of circular words W ∈ G * ℓ such that W admits 0 2m 1 as a prefix (for some m > 0) and 1 as a suffix.

In particular, we have T (01) ℓ = σ(T (10) ℓ ), and:

Card(T (10) ℓ ) = Card(T (01) ℓ ) = F n-2 and Card(T * (11) ℓ ) = F n-5 -1.
The proof of Proposition 3.2 basically consists in writing the opposite of w 2ℓ-1 0 on the form Z( w ′ 2ℓ-1 0 ), where w ′ i = 1 -w i for any i, in studying in which case the transformations τ0 and τ1 are to be considered to get the admissible form of w ′ 2ℓ-1 0 and in applying Lemma 2.3. The details are left to the reader.

The form of the element of T (10) ℓ and T (01) ℓ leads to the following characterization of the structure of these sets.

Proposition 3.3. Recall that M = abaababaabaab . . . is the Fibonacci word. We have

N(T * (10) ℓ ) = {1 + 2|M k | a + |M k | b , 0 ≤ k < F 2ℓ-2 }, N(T * (01) ℓ ) = {1 + 3|M k | a + 2|M k | b , 0 ≤ k < F 2ℓ-2 }, N(T * (11) ℓ ) = {F 2ℓ-1 + 3 + 5|M k | a + 3|M k | b , 0 ≤ k < F 2ℓ-5 -1}.
Proof. Consider for example the case of N(T * (10) ℓ ), the other ones being similar. Assume the property true until N(T * (10) ℓ-1 ) and consider N(T * (10) ℓ ). For 0 ≤ k < F 2ℓ-2 , we have either k < F 2ℓ-4 (for which we can apply the induction hypothesis), or F 2ℓ-4 ≤ k < F 2ℓ-2 . In this latter case, define k ′ by k = F 2ℓ-4 + k ′ , so 0 ≤ k ′ < F 2ℓ-3 . Recall here the classical characterization of M by blocks: if we put B (-1) := b, B (0) := a and, for any j ≥ 1, B (j) := B (j-1) B (j-2) , then we have M = lim j (B (j) ). Therefore, we have

1 + 2|M k | a + |M k | b = 1 + 2(F 2ℓ-5 + |M k ′ | a ) + (F 2ℓ-6 + |M k ′ | b ) = F 2ℓ-3 + (1 + 2|M k ′ | a + |M k ′ | b ). If k ′ < F 2ℓ-4
, then, by induction hypothesis, the value in the last parenthesis admits W 00 as a Zeckendorf representation, where W is of type (10) ℓ-1 . Moreover, we have Z(F 2ℓ-3 ) = 0 2ℓ-3 100, so we eventually get that Z(1

+ 2|M k | a + |M k | b
) has the desired form, by Proposition 2 if W admits 00 as a prefix, by a simple case study if W begins with a 1.

If F 2ℓ-4 ≤ k ′ < F 2ℓ-3 , then we put k ′ = F 2ℓ-4 + k ′′ , and the reasoning is similar.

Hence, we have otained that any number of the form 1

+ |M k | a + |M k | b for 0 ≤ k < F 2ℓ-2 belongs to N(T * (10) ℓ ).
Since we know by Proposition 3.2 that this latter set has precisely F 2ℓ-2 elements, we are done.

In passing, it is also possible to describe in similar terms the set of forbidden values for G * ℓ , that is, the set of positive integers k strictly less than F n and such that the word Z(k), assumed of length 2ℓ, admits 1 as a prefix and also as a suffix (hence does not correspond to an admissible circular word of G * ℓ ). Here is the result, without proof.

Proposition 3.4. With the notation of Proposition 3.3, the set U 2ℓ of forbidden values for G * ℓ satisfies

U 2ℓ = {F n-1 + 1 + 3|M k | a + 2|M k | b , 0 ≤ k < F 2ℓ-4 }.
Proposition 3.5. Let Π and Π ′ be the circular words defined in Theorem 2.7, for q := d ℓ . For any k ≤ q, kΠ is of type (10) ℓ and kΠ ′ is of type (01) ℓ .

Proof. This is a consequence of an observation made in the proof of Theorem 2.7: in the case q = d ℓ , we have Π = 0 ℓ-1 10 ℓ and Π ′ = 0 ℓ 10 ℓ-1 for odd ℓ, and Π = 0 ℓ-2 1010 ℓ-1 and Π ′ = 0 ℓ-1 1010 ℓ-2 for even ℓ. In any case, Π is of type (10) ℓ and Π ′ of type (01) ℓ . We also observed that, also in the case q = d ℓ , for any k < d ℓ , Val(kΠ) satisfies Val((k + 1)Π) = Val(kΠ) or Val(kΠ) -2, so the type of kΠ remains constant. The same result holds for Π ′ , so the proposition is proved in the case q = d ℓ , hence also for any divisor of d ℓ .

To end the proof of Theorem 3.1, observe that, by Theorem 2.7 and Propositions 3.2 and 3.5, we have, for any 0

< i ≤ d ℓ , N(Π) = iN(Π) -(i - 1)N(Π) = 2|A (i) | a + |A (i) | b . Moreover, it is well-known that M is balanced, that is: for a given length m and two factors V and V ′ of M of length m, we have ||V | a -|V ′ | a | ≤ 1. Together with the previous fact asserting that 2|A (i) | a + |A (i) | b is constant, this implies that |A (i) | a and |A (i) | b are constant.

3.2.

A formula for the integer sequence A004146. Recall the definition of the integer sequence defined in Theorem 2.4:

c 1 := 1 c n := F 2n-1 + F 2n-3 -2 for n ≥ 2.
The aim of this section is to prove the following result:

Theorem 3.3. For any n ≥ 0, let α n := e 2iπ/n . We have, for any n ≥ 2:

c n = - 2n-1 j=0 (1 -α j n -α 2j n ).
To this end, we consider again, for any n ≥ 2, the linear operator M = M n+1 on R n+1 defined after Lemma 2.1:

M n+1 = (m ij ) i,j with m i,i = 1, m i,((i+1) mod (n+1)) = -1 and m i,((i+2) mod (n+1)) = -1 for any 0 ≤ i ≤ n.
Lemma 3.4. For any 0 ≤ j ≤ n, the value 1 -α j -α 2j is an eigenvalue of M n+1 , associated to the vector V j := (α kj ) n k=0 .

Proof. Simple verification.

Since the family {V j , 0 ≤ j ≤ n} is a base of R n+1 (since the vectors V j make a Vandermonde matrix), we get that M n+1 is diagonalizable, and that its determinant is equal to n j=0 (1 -α j n -α 2j n ). Now, let us give another way to get this determinant.

Lemma 3.5. The characteristic polynomial P n (X) = det(M n -XI) of M n satisfies, for any n ≥ 5:

P n (X) = P n-1 (X)+(1-X)P n-2 (X)-(1+X)(1-X) n-1 +(-1) n+1 (X-1)+2•(-1) n .
Proof. For any n ≥ 2, we denote by R n (X) the determinant of the operator (r i,j ) 1≤i,j≤n of R n defined for all i for which the following expressions make sense: r i,i = -1, r i,i+1 = -1 and r i,i-1 = 1 -X. Now, take n ≥ 5. Write the expansion along the first line of the determinant

P n (X) as (1 -X)A n-1 (X) + B n-1 (X) -C n-1 (X). The expansion of A n-1 (X) along the first column gives that A n-1 (X) = (1 -X) n-1 - (-1) n R n-2 (X). Write B n-1 (X) = (-1) n D n-2 (X) -(-1) n R n-2 (X) for the expansion of B n-1 (X) along the first column; the expansion of D n-2 (X) along the last line gives that D n-2 (X) = (1-X)R n-3 (X). Write C n-1 (X) = -(1 -X)B n-2 (X) -E n-2 (X)
for the expansion of C n-1 (X) along the first line. The expansion along the first line of E n-2 (X) followed by a simple induction gives that E n-2 (X) = (-1) n .

Putting together all these results gives

P n (X) = (1 -X) n + (-1) n -(-1) n (2 -X)R n-2 (X) + (-1) n (2 -2X)R n-3 (X) -(-1) n (1 -X) 2 R n-4 (X).
It is a classical exercice to show that, for any n ≥ 4, R n (X) = (1 -X)R n-2 (X) -R n-1 (X), with R 2 (X) = 2 -X and R 3 (X) = 2X -3. Eventually, a simple calculation gives the desired result. Lemma 3.5 for X = 0 then gives that det(M n ) = det(M n-1 )+det(M n-2 )-1 + 3 • (-1) n . Then, an induction shows that, for any n, det(M 2n ) = -c n and det(M 2n+1 ) = -d 2n+1 (with the definition of (d n ) n given in Theorem 2.4). With the expression of det(M n ) obtained in Lemma 3.4, we get Theorem 3.3.

F -adic numbers

Before giving the definition that appears to be the most convenient, we feel interesting to consider first some alternative definitions and explain why we do not retain them.

First attempt.

A first quite natural idea to define the set of F -adic numbers consists in considering the set of integer sequences N N (each element of which being regarded as an infinite word on the alphabet N) equipped with the cylinder topology. Consider the quotient of this set given by the closure of equivalence classes defined by the relation ≡ (see section the words W = X(10) ∞ and W ′ = X ′ (01) ∞ , where X and X ′ are finite admissible words of the same length. It appears that this latter example contains essentially all possible contentious issues.

Definition 4.3. The set F of F -adic numbers is defined as the set of admissible infinite sequences, with the identifications (01) ∞ = (10) ∞ and V 0(01) ∞ = Z(V 10(01) ∞ ) for any admissible finite word V , and equipped with the (quotient) cylinder topology. A negative F -integer is an admissible sequence ultimately periodic with period 01 (that is: negative F -integers are the F -adic numbers admitting two different writings).

The sum of two F -adic numbers W and W ′ is defined as:

W ⊕ W ′ := lim n (Z(W n + W ′ n )).
For any word W with letters on a bounded subinterval of N, we define Z(W ) := lim n (Z(W n )).

To ensure the consistence of this definition, we have to show that the sum is well-defined (which immediately implies the consistence of the definition of Z(W )). This is done in the proof of the following result, which is a strong justification for our choice of definition. Before it, let us explain the terminology of negative F -integers. Consider a negative F -integer V 0(01) ∞ = Z(V 10(01) ∞ ), and put W := V 0 (recall that, for any finite word X, we have Z(X + X) = 0 |X| 1). Since Z(W + V 0(01) ∞ ) = Z(W + Z(V 10(01) ∞ )) = 0 ∞ , the negative F -integer can be regarded as the word corresponding to the value -N(W ). In the same way, the F -adic number (01) ∞ = (10) ∞ can be regarded as -1 (or, to avoid ambiguous notation, (-1) F ). Note also that, because of the negative F -integers, the notion of valuation is consistent only for words, and not for F -adic numbers in general. Now, let us give the main result of this section.

Theorem 4.4. (F , +) is a topologic abelian group.

Proof. Let us start by showing that the addition is well-defined. We consider first the case of two F -adic numbers, W and W ′ , which are not negative F -integers. If, for any k ≥ 0, the sequence of letters of rank k of the words Z(W n + W ′ n ) converges, then W + W ′ is well-defined. Else, let k be the smallest index such that the sequence of letters of rank k of Z(W n + W ′ n ) does not converge. The sequence of prefixes of length k (which may be ∅ if k = 0) of the sequence (Z(W n + W ′ n )) n converges to some admissible word V . Since both W and W ′ contains infinitely many 1s (to ensure the existence of k), we can find an n 0 such that N(W n 0 ) > N(V ). By replacing the word

W =: W n 0 U by the word Z(N(W n 0 ) -N(V ))0 |Wn 0 |-|Z(N (Wn 0 )-N (V ))| U, we can assume that V = 0 k .
The successive words Z(W n + W ′ n ) can be obtained by iterating the algorithm that computes Z(W +0 m 1) for finite admissible W , with a sequence of values of m going to infinity. With a little abuse in notation (since the successive m is an increasing sequence but non necessarily strictly increasing), we write X m for the successive admissible words hence obtained.

Assume k ≥ 1. By Proposition 1.2, we have, for any m, Val(X m ) = k or k + 2, and, by hypothesis, there are infinitely many values of m for which Val(X m ) = k and also infinitely many for which Val(X m ) = k + 2. Consider an m such that Val(X m ) = k + 2 and Val(X m+1 ) = k. By Proposition 2, X m is of the form 0 k+2 (10) sm Y m , with Y m admissible. When m goes to infinity, s m must go to infinity as well. Hence, the sequence (Z(W n + W ′ n )) n admits 0 k+2 (10) ∞ (the limit of the X m s) and 0 k 10(01) ∞ (the limit of the X m+1 s) as accumulation points. Since the values of m for which Val(X m ) = Val(X m+1 ) does not add any other accumulation point, we are done for this case. Now, assume k = 0. If, for all but finitely many of m such that Val(X m ) > 0, we have Val(X m ) = 2, then we can apply Proposition 1.2 as in the case k > 0. Hence, we assume that, for any big enough m such that Val(X m ) > 0, we have Val(X m ) = 1. Take m such that Val(X m ) = 1 and Val(X m+1 ) = 0. By Lemma 1.3, the computation of X m+1 from X m by the algorithm necessarily involves the first loop. Hence, we necessarily have X m+1 = Z(0(10) sm 20Y m+1 ) for some admissible Y m+1 and some s m ≥ 0. Since s m must go to infinity as m goes to infinity, the word (01) ∞ is an accumulation point of the sequence (X m ) m . The same reasoning starting from Val(X m ) = 0 and Val(X m+1 ) = 1 gives that (10) ∞ is an accumulation point as well. Since no other accumulation point arise from the cases Val(X m ) = Val(X m+1 ) (= 0 or 1), we are also done for k = 0. Now, assume that W is a negative F -integer. For some finite admissible word V , we have W = V 0(01) ∞ = Z(V 10(01) ∞ ), and the point is to verify that the result of the computation of W ⊕W ′ does not depend on the choice of the two equivalent representations of W . If W ′ is also a negative F -integer, then the result is obtained by a simple verification (and gives that, for any a, b ∈ N, we have (-a F ) ⊕ (-b F ) = (-(a + b)) F ). Therefore, from now, we assume that W ′ is not a negative F -integer. We put X n := Z(W n +W ′ n ) (with a fixed choice for the representation of W ). We then have, for any big enough n, that Z(X n + V 0) = Z(W ′ n + 0 n 1). Since W ′ is not a negative F -integer, the sequence of words Z(W ′ n +0 n 1) converges to an admissible limit word Y , which is also the limit of Z(X n +V 0). Since V 0 is a finite word, the sequence X n is also converging to an admissible limit word X, which consistently defines W ⊕ W ′ , independently of the choice of the representation of W . The same reasoning, where the F -adic numbers W and W ′ are replaced by sequences (W (n) ) n and (W ′ (n) ) n of F -adic numbers converging to W and W ′ , is easily adapted to show that ⊕ is bicontinuous. Now, let us show the associativity of ⊕. If W , W ′ , W ′′ , W ⊕ W ′ and W ′ ⊕ W ′′ are not negative F -integers, then for any n there exists an i such that the prefix of length n of (W ⊕ W ′ ) ⊕ W ′′ and of W ⊕ (W ′ ⊕ W ′′ ) is determined by the prefix of length i of W , W ′ and W ′′ . Hence, in this case, the equality (W ⊕ W ′ ) ⊕ W ′′ = W ⊕ (W ′ ⊕ W ′′ ) derives from the associativity of ⊕ in the case of finite words. The other cases, left to the reader, are essentially similar, with only some additional verifications due to the possible existence of two different representations for some of the involved expressions.

To complete the proof, it only remains to show that any F -adic number W = w ∞ 0 admits an opposite. We already know that this is the case when W is a negative F -integer, so we exclude this case in the sequel. We also exclude the case where W is ultimately periodic of period 0 (that is: W is a positive F -integer). Consider the word W ′ := w ′ ∞ 0 , where w ′ n = 1 -w n for any n. Since W ′ is a word on the alphabet {0, 1}, not ultimately periodic of period 1 (by hypothesis on W ), there exists a unique admissible word W ′′ such that, for any n, Z(W ′ n ) = W ′′ n (if 1 2i-1 is a suffix of W ′ n but not 1 2i , for some i) or W ′′ n+1 (in the other case). For any n, we have W n + W ′ n = 1 n , so Z(W n + W ′ n ) = (01) n/2 (for even n) or 1(01) (n-1)/2 (for odd n). Hence, the sequence (Z(W n + W ′′ n )) n converges to -1 F , so W ′′ ⊕ (-1 F ) is the opposite of W .

Rational F -adic numbers

A F -adic number X is rational iff there exists two integers p and q such that Z(qX) = Z(p). In the sequel, we simply write qX = p for this equation. The goal of this section consists in proving the following two theorems:

Theorem 5.1. The F -adic number X is rational iff it is ultimately periodic.

Theorem 5.2. Let p and q be two integers, with q > 0. The set of roots of qX = p is of cardinality q + 1 if p/q ∈ Z and of cardinality q otherwise. The proof of Theorem 5.2 will lead us to a simple and general expression of the set of solutions of the equation qX = p (see Theorem 5.5, at the end of this paper). 5.1. Proof of Theorem 5.1. 5.1.1. Periodic ⇒ rational.

Proposition 5.1. Let X := W P ∞ and X ′ := W ′ P ′ ∞ be two ultimately periodic F -adic numbers with |W | = |W ′ |. The sum X ⊕ X ′ is ultimately periodic, of period Q such that Q = P ⊕ P ′ .

Proof. Without loss of generality, we assume P and P ′ of the same even length 2ℓ, and take W = W ′ = 0 k with big enough k. By induction, we can also assume P ′ of the form 10 2ℓ-1 . If P ⊕ P ′ = P + P ′ , then the result is immediate. Otherwise, writing P = p 0 . . . p 2ℓ-1 , we have either p 0 = 1 or P = (01) ℓ . In this latter case, the proposition is easily verified. Assume now p 0 = 1. We either have P = (10) ℓ or, for some admissible word R and some integer j, P = 10R00(10) j . In both cases, the proposition is routinely verified.

Corollary 5.3. For any integer q and any finite admissible word P (containing at least one 1 and which first and last letters are not both equal to 1), Z(qP ∞ ) is a ultimately periodic F -adic number, and admits the word Q as a period, where Q := Z( qP ).

Proof. Immediate. Now, let X := W P ∞ be a ultimately periodic F -adic number, where W and P are finite admissible words (as well as W P ). If P = 0, then there is nothing to prove. We thus consider only the case where P contains at least one 1. Without loss of generality, we may also assume P of even length 2ℓ (otherwise, we simply replace P by P 2 ).

Since P does not contains only 0s, we have P ∈ G * ℓ . Denoting by q the order of P in G * ℓ , we get by Corollary 5.3 that, for some finite admissible word Y , Z(q(0 |W | P ∞ )) = Y (01) ∞ , which is a negative F -integer, say -r. Since qW is an integer, say s, we get that q(W P ∞ ) = qW + q(0 |W | P ∞ ) = s -r, so we are done. 5.1.2. Rational ⇒ periodic. Let X := x ∞ 0 ∈ F be a root of qX = p, where p and q are integers. By changing the value of p, we can assume that, for any chosen value k ≥ 1, we have x 0 . . . x k-1 = 0 k . ( -aσ(Π)) for any 0 ≤ a < q. Apart the possible integer solution p/q (if p ∈ qZ), the roots of the equation qX = p are pP ∞ a for 0 ≤ a < q. Denote P ′ a := aΠ ⊕ ( -aσ(Π)) for any 0 ≤ a < q. The roots of the equation qX = 0 are P ′ a for 0 ≤ a < q.

The proof is immediate.

  ) ℓ . Both generators are hence of order at most d ℓ . Hence, since G * ℓ is of cardinality strictly bigger than d ℓ , G * ℓ is necessarily of the form (Z/aZ) × (Z/bZ) with ab = d 2 ℓ ; moreover, we must have a and b both upper-bounded by d ℓ , so a = b = d ℓ .

Now, let ℓ ′ be another integer. Again by Theorem 2.4, in G * ℓ ′ , the maximal subgroup M ℓ ′ of elements of order q is isomorphic (Z/aZ)×(Z/bZ), where a and b are divisors of q. Since ℓℓ ′ divides q, we have that M ℓℓ ′ is isomorphic to (Z/qZ)×(Z/qZ). By Proposition 2.2, G * ℓ ′ and G * ℓ are subgroups of G * ℓℓ ′ , so M ℓ and M ℓ ′ are subgroups of M ℓℓ ′ . Since M ℓ = M ℓℓ ′ , the result follows.

2.3. Size of circular words of order q, and natural generators of P * q . For a given q, consider the smallest ℓ for which P * q ⊂ G * ℓ . The value 2ℓ is denoted by T (q) in the sequel. In general, the inclusion of P q in G * T (q)/2 is strict. The set of values q for which the equality arise is simply the set of q for which q 2 is equal to the cardinality of G * ℓ for some ℓ. That is: q satisfies P * q = G * ℓ for some ℓ iff q = d 2k+1 for some k (and, in this case, we have T (q) = 4k + 2). The following result gives a precise description of the function q -→ T (q). It also reveals the existence of two particular generators of P * q , denoted by Π and Π ′ , which are of great importance for the understanding of algebraic structures arising from circular words.

Theorem 2.7. For any q ≥ 2, the minimal value ℓ for which

Moreover, let Π (resp. Π ′ ) be the circular word of length 2ℓ equal to Z((F n -1)/q) (resp. Z((F n-1 -1)/q)). We have σ(Π ′ ) = Π and, for any

The circular words Π and Π ′ are the only non-trivial elements of P * q satisfying this latter property.

The following part of this section is mostly devoted to the proof of this theorem. Note first that the existence, for any q, of an even value n > 2 such that (F n mod q) = (F n-1 mod q) = 1 is proved in a similar way as Lemma 2.6.

Lemma 2.8. Define the sequence (d ′ ℓ ) ℓ as:

For any ℓ > 0, we have

Proof. Simple calculation.

Corollary 2.9. For any ℓ > 0, we have gcd(F 2ℓ -1, F 2ℓ-1 -1) = d ℓ .

Proof. For ℓ odd, the result derives from the fact that F ℓ-1 and F ℓ are mutually prime. For ℓ even, observe that any common divisor d > 0 of

and, by induction, also a divisor of F 3 +F 1 = 7 and of F 2 +F 0 = 4, so d = 1.

From now, we consider the notation of Theorem 2.7. In the sequel, we take q = d ℓ since, by Corollary 2.9, this case is enough to get Theorem 2.7. In this case, also, Lemma 2.8 gives that Π = 0 ℓ-1 10 ℓ and Π ′ = 0 ℓ 10 ℓ-1 for odd ℓ, and Π = 0 ℓ-2 1010 ℓ-1 and Π ′ = 0 ℓ-1 1010 ℓ-2 for even ℓ. Consider for example the case ℓ odd (the other case leading to the same case of study, with the help of the decomposition 0 ℓ-2 1010 ℓ-1 = 0 ℓ-2 10 ℓ+1 + 0 ℓ 10 ℓ-1 ). By Lemma 4.1 applied to the case m = ℓ -1 and n ≤ m/2, and also by Lemma 4.2, we get that, for any

and u n Π = 0 m-2n 10 4n-1 10 ℓ-2n . Hence, more generally, we get that, for any k ≤ n j=0 u j = d ℓ (this latter equality coming from a simple induction), k • Π = kΠ, and 10) ℓ . The same study for Π ′ works as well, so Theorem 2.7 is proved. Theorem 2.7 gives an explicit way to get the full set P * q that is useful in itself:

(i) Let n > 3 be the smallest even integer such that (F n mod q) = (F n-1 mod q) = 1. (ii) Let Π be the admissible word of length 2ℓ := n such that Z(Π) = (F n-1 -1)/q. (iii) We have

In passing, we conjecture that, apart for the case q = 2, the smallest value n > 3 such that (F n mod q) = (F n-1 mod q) = 1 is always even, so the assumption n even in Theorem 2.7 is useless for q > 2.

Two applications of circular words

3.1. A property of the Fibonacci word. This section is devoted to the proof of the following theorem.

Theorem 3.1. Let M := abaababaabaab . . . be the Fibonacci word, that is: the fixed point of the substitution defined on the alphabet {a, b} by a → ab 1.2). This first attempt of definition is not convenient, because all the integers would belong to the same closed equivalence class, as shown by the following Proposition 4.1. Let W = w ∞ 0 be the infinite word defined by:

The closed equivalence class of W contains all infinite words of the form X0 ∞ with X finite and admissible.

Proof. We need two lemmas first.

Lemma 4.1. Let (u n ) n be the sequence defined by u 0 = 1, u 1 = 3 and, for any n ≥ 2:

Let n ≥ 1, let m ≥ 2n. The finite word 0 m u n is equivalent to the finite word 0 m-2n 10 4n-1 1.

Proof. Define, for any n ≥ 0:

We prove the lemma by induction, adding to it the following complementary induction hypothesis: The finite word 0 m v n is equivalent to the finite word 0 m-2n (10) 2n 1.

Assuming that both the two properties are true until some value n ≥ 1, choose m ≥ 2(n+1). Since u n+1 = u n +v n , we have the following equivalence of finite words:

which is the desired property for u n+1 . Now, since v n+1 = v n + u n+1 , the induction hypothesis and the previous result for u n+1 immediately give the desired form for 0 m v n+1 .

Lemma 4.2. With the notation of Lemma 4.1, we have, for any i ≥ 2,

Proof. Simple induction with the relation u n = 3u n-1 -u n-2 . Now, by Lemmas 4.1 and 4.2, we get that: 01. . . ≡ 10 7 u 4 0 7 (u 8 -1)0 15 (u 16 -1)0 31 . . . ≡ 20 15 u 8 0 15 (u 16 -1)0 31 . . . ≡ 30 31 u 16 0 31 . . .

we get by induction that, for any finite admissible word V of length n and any integer k, there exists an infinite word X n,k such that W ≡ V 0 k X n,k . This is the desired conclusion. 4.2. Second attempt. To avoid the previous problem, one may restrict the set of integers to the subset of bounded ones, hence excluding the previous case. Unfortunately, this is still not a convenient definition, because it does not prevent us from the following problem.

Proposition 4.2. The closed equivalence class of 0 ∞ contains infinitely many admissible sequences.

Proof. Choose n 0 > 0, put X (0) := 0 2n 0 u n 0 and let W (0) := Z(X (0) ). (By Lemma 4.1, we have W (0) = 10 4n 0 -1 1.) Choose any n 1 > n 0 big enough so that, defining X (1) := 0 2n 0 u n 0 0 4n 1 -1 u n 0 , we have W (1) := Z(X (1) ) = W (0) 0 k 1 W (0) for some k 1 > 0. More generally, for any i > 0, choose any n i > n i-1 big enough so that, defining X (i) := X (i-1) 0 4n i-1 -1 X (i-1) , we have -1) for some k i > 0. Let us show that the infinite and admissible word W := lim n (W (n) ) belongs to the closed equivalence class of 0 ∞ . Define π i := u n 0 • • • u n i for any i ≥ 0. By construction and Lemma 4.1, X (1) is equivalent to 0 2(n 0 +n 1 ) π 1 and, more generally and by an immediate induction, X (i) is equivalent to 0 2(n 0 +•••+n i ) π i . Hence, the infinite word W and the null sequence belong to the same closed equivalence class in the cylinder topology. 4.3. Final definition of the set of F -adic numbers. Our aim is now to consider only admissible infinite sequences for the set of F -adic numbers. Let W and W ′ be two admissible sequences. The natural definition for their sum W + W ′ is to consider the limit lim n (Z(W n + W ′ n )). The point is to ensure that such a limit exists, which is not always the case, as the example W := (01) ∞ and W ′ := (10) ∞ shows (we have Z(W 2n + W ′ 2n ) = 00(10) n and Z(W 2n+1 + W ′ 2n+1 ) = 10(01) n ). A more general example is given by Define the application Φ: F -→ [-1, 1] by Φ(w ∞ 0 ) = +∞ n=0 w n (-ϕ) -n . Since k can be chosen big enough independently of q, we can assume that Φ(qX) = qΦ(X). Hence, we have Φ(X) = Φ(qX)/q = Φ(p)/q. This latter element belongs to Q(ϕ), and it is well-known that the elements of Q(ϕ) are exactly the ones that admit a periodic expansion in the numeration system in base -ϕ. Hence, Φ(X) has the form ∞ n=0 y n (-ϕ) -n with y ∞ 0 admissible and ultimately periodic. Since, moreover, Φ is injective, we eventually get the desired result. 5.2. Proof of Theorem 5.2. We know by Theorem 5.1 that any root of the equation is of the form W P ∞ , where W and P are finite admissible words. If P = 0, then we are back to an usual integer equation, with one root (p/q) if p/q ∈ Z and no root otherwise. So, from now, we exclude the case P = 0, and show that exactly q roots of the equation qX = p are to be found.

Let Ψ : P * q -→ Z/qZ be defined by Ψ( P ) := Z(q • P ∞ ) mod q (The function Ψ is well-defined, since we know that Z(q • P ∞ ) is ultimately periodic of period 01 by section 5.1.1, hence is a negative F -integer.) The function Ψ is a morphism of groups. Let Π ∈ P * q be the word given in the algorithm presented after the proof of Theorem 2.7. We have qΠ ∞ = (-1) F , so Ψ( Π) = q -1 = -1, so Ψ is surjective, and Ψ -1 (0) has q elements (since P * q has q 2 elements by Theorem 2.5). Let P ∈ P * q . We have Z(q •(10 ∞ ⊕P ∞ )) = Z(qP ∞ )+q and Z(q •((-1) F ⊕ P ∞ )) = Z(qP ∞ ) -q, so, with the help of the surjectivity of Ψ, we get that the number of solutions of the equation qX = p does not depend on p.

Lemma 5.4. Let X and X ′ be such that qX = 0 and qX ′ = 0, with X = W P ∞ and X ′ = W ′ P ∞ for some finite admissible words W and W ′ and some P ∈ P * q . If |W | = |W ′ |, then W = W ′ .

Proof. Immediate. Now, the desired result is a simple consequence of Lemma 5.4 and the fact that Ψ -1 (0) has exactly q elements. 5.3. An explicit expression of the roots of qX = p. As we said after the statement of Theorem 5.2, the proof of this theorem provides a full characterization of the set of F -adic solutions of qX = p.

Theorem 5.5. Let p and q be integers, with q > 0 and p = 0. Denote by Π the word defined in the end of section 2.3, and put P a := (a -1)Π ⊕