J Abadie
email: jabadie@femto-st.fr

C Roux

E Piat

C Filiatre

C Amiot

Experimental Measurement of Human Oocyte Mechanical Properties on a Micro and Nanoforce Sensing Platform Based on Magnetic Springs

Keywords: micro and nanoforce sensor, oocyte mechanical characterisation, magnetic springs

This article presents a new micro and nanoforce sensor used to perform a mechanical characterisation of human oocytes. This device is based on the use of low-stiffness magnetic springs. The oocytes to be characterised are placed on a force-sensitive platform. A manipulator equipped with a standard micropipette is used to mechanically compress the oocyte. Some complete "force-compression length" curves associated with mechanical load-unload cycles are given. These curves show the linear, the non-linear and also the plastic mechanical behaviour of the oocytes. These characterisations must be considered as a preliminary result which illustrates that the mechanical variability and the mechanical evolution of human oocytes during their maturation process can be observed with a force sensor based on magnetic springs.

Introduction

As mentioned at the beginning of [1], palpation remains an important approach in the medical diagnosis of organ illness, and the mechanical translation of this physician's approach leads to the cited fact that "stiffness is an important parameter in determining the physical properties of living tissue" and thus to identify healthy or diseased parts of tissue during the patient diagnosis. As recently suggested, this approach should be generalized to oocyte selection in assisted reproductive technology (ART) if the physician could have the ability to feel the stiffness of the candidate oocytes. Furthermore, Woodruff emitted the hypothesis that the physical properties of the follicle environment, in vivo (in normal ovary or in ovarian disorders) or in vitro (in 3D matrices culture), modulates the follicles responsiveness to paracrine factors and hormones [2]. The study of such biomechanical signalling, particularly for in vitro culture, will require the development of new tools and new approaches. With the important development of micro-mechanical systems, the measurement of very low stiffness on biological tissues becomes possible [START_REF] Kim | Manipulation at the nanonewton level: Micrograpsing for mechanical characterization of biomaterials[END_REF][START_REF] Nishi | Measurement of the mechanical properties of living cell using micro hand and developed afm system[END_REF] and considerable biomedical attention is focused on the mechanical properties of living tissues at the single cell level [1]. Stiffness measurement at this scale requires very sensitive micro and nanoforce sensors. Many sensors have already been developed and present a force resolution compatible with the needs of ART [START_REF] Rougeot | Forces analysis for micro-manipulation[END_REF][START_REF] Beyeler | A six-axis mems force-torque sensor with micro-newton and nano-newtonmeter resolution[END_REF]. Authors have also proposed different rheology techniques used to characterise the internal or global mechanical parameters of biological cells. These techniques are based on optical techniques associated with a modelling of the cell [START_REF] Wottawah | Optical rheology of biological cells[END_REF][START_REF] Daniels | Probing single-cell micromechanics in vivo: The microrheology of c. elegans developing embryos[END_REF][START_REF] He | Analytical model for extracting mechanical properties of a single cell in a tapered micropipette[END_REF] or on the use of glass elastic microstructures [START_REF] Desprat | Microplates-based rheometer for a single living cell[END_REF]. Mechanical properties of the cytoplasm of oocytes have also been studied thanks to fluorescent microbeads microinjected inside starfish oocytes [START_REF] Pesce | Mechanical changes of living oocytes at maturation investigated by multiple particle tracking[END_REF]. This multiple-particles tracking approach has shown that the maturation process in starfish oocytes is accompanied by a change in the mechanical response of the cytoplasm. Despite its efficiency, such a technique will probably not be approved by the french Biomedecine Agency for human oocytes fertilisation using an ICSI1 protocol. This agency requires that all new manipulation techniques or tools added to the ICSI routine protocol on human oocytes, have no proven deleterious effects. As a result, none of these cited techniques have been applied to human assisted reproductive technology.

The oocyte selection plays a critical role in the initial embryo development and therefore in ART results. The attempts concern in vitro fertilization (IVF) or intra cytoplasmic sperm injection (ICSI). Oocyte quality depends on its nuclear and cytoplasmic maturation stage. The quality estimation during ICSI procedure is based on morphological criterion after the removal of the cumulus-corona cells. A mature human oocyte has a single polar body in the perivitelline space (PVS), a normal aspect of the cytoplasm and of the zona pellucida (ZP) [START_REF] Rienzi | Predictive value of oocyte morphology in human ivf: a systematic review of the literature[END_REF][START_REF]Alpha scientists in reproductive medicine and ESHRE special interest group of embryology. The istanbul consensus workshop on embryo assessment: proceedings of an expert meeting[END_REF]. Furthermore, observation of oocyte birefringent structures with polarized light microscopy is useful for observing the meiotic nuclear maturation status by displaying the meiotic spindle (MS) and analyzing the highly-ordered inner layers of the ZP [START_REF] Montag | Oocyte zona birefringence intensity is associated with embryonic implantation potential in icsi cycles[END_REF][START_REF] Ebner | Automatic user-independent zona pellucida imaging at the oocyte stage allows for the prediction of preimplantation development[END_REF]. However morphology is biologist-dependant and often fails to predict fertilizing ability and developmental competence.

During oocyte growth and maturation, both cytoplasmic modifications, and changes in the ZP structures and thickness are responsible for the variation of the oocyte stiffness. After fecundation occurs, the modification of the zona pellucida, called the zona pellucida hardening (consecutive to the release of the cortical granules from the cytoplasm of the oocyte in the PVS), participates in the change of the stiffness. Furthermore, different culture conditions which alter the ZP structure may also change the stiffness.

The oocyte characteristics have been investigated by means of mechanical measurements using micropipettes, different indenter tips, or systems consisting of pressing oocytes on a "wall" or a holding micropipette. These studies are focused on mammalian [START_REF] Nakamura | Mechanical properties of the cell surface in starfish eggs. Develop[END_REF]1,[START_REF] Sun | Mechanical property characterization of mouse zona pellucida[END_REF][START_REF] Murayama | Mouse zona pellucida dynamically changes its elasticity during oocyte maturation, fertilization and early embryo development[END_REF][START_REF] Liu | In situ mechanical characterization of mouse oocytes using a cell holding device[END_REF] or human oocytes [START_REF] Murayama | Elasticity measurement of zona pellucida using a micro tactile sensor to evaluate embryo quality[END_REF][START_REF] Wacogne | Measuring the mechanical behaviour of human oocytes with a very simple su-8 microtool[END_REF]. These previous works show that immature and mature oocytes or young and old, are mechanically different [START_REF] Wacogne | Measuring the mechanical behaviour of human oocytes with a very simple su-8 microtool[END_REF][START_REF] Liu | Elastic and viscoelastic characterization of mouse oocytes using micropipette indentation[END_REF]. Furthermore, characterisation of the cellular forces applied to the oocyte during microinjection may assess oocyte stiffness at this specific ART event. To perform these tasks, new instrumentation compatible with ART constraints and physicians' habits is necessary. With their low stiffness and their high ranges of force measurement, force sensors based on magnetic springs [START_REF] Boukallel | Passive diamagnetic levitation : theoretical foundations and application to the design of a micro-nano force sensor[END_REF][START_REF] Abadie | Modeling and experimentation of a passive low frequency nanoforce sensor based on diamagnetic levitation[END_REF][START_REF] Cherry | Microforce sensor for microbiological applications based on a floating-magnetic principle[END_REF] could be a potential solution to design such instrumentation.

This article describes a new oocyte characterisation device based on the past experience gathered on a floating platform using a magnetic spring dynamometer [START_REF] Cherry | Analysis of a passive microforce sensor based on magnetic springs and upthrust buoyancy[END_REF]. Some preliminary experimental results of mechanical characterisations done with mature and immature human oocytes are given. Rather than calculating the stiffness or Young's modulus of human oocytes, the complete force-compression length curves associated with mechanical load-unload cycles are given. These curves bring new and more complete information. They show the non-linear and also the plastic mechanical behaviour of human oocytes. These characterisations have to be considered as a preliminary result which illustrates that the mechanical variability and the mechanical evolution of human oocytes during their maturation process can be observed with a force sensor based on magnetic springs. This device has been developed at the FEMTO-ST institute by the SPECIMeN 2 group of the AS2M 3 department.

Description of the force sensing platform

The force sensor based on magnetic springs that has been prepared to characterise oocytes is a prototype that is able to measure a vertical torque and micro and nanoforces in two perpendicular horizontal directions of space [START_REF] Cherry | Analysis of a passive microforce sensor based on magnetic springs and upthrust buoyancy[END_REF]. The oocytes that have to be characterized are placed at the centre of a floating 2 Sensing strategies, Perception and Characterisation at Micro and Nanoscales

3 Automatic Control and Micro-Mechatronic Systems

Micropipette

Culture medium Special Petri dish

K x F -F

magnetic spring compression

Figure 1: Forces applied on the force sensing device when an oocyte is under a compression test. platform in a special Petri dish filled with a culture medium. An external manipulator4 equipped with an ICSI micropipette is used to apply mechanical loads on the oocyte.

Micropipette d oo

-F F

2.1. Simplified description of the force sensing platform Fig. 1 shows the principle of the force sensing platform used to characterise the mechanical response of the oocyte to a compression cycle. It is composed of a force sensor device that is used to measure the compression force F applied to the oocyte (see Fig. 2). The Eppendorf manipulator is used to generate displacements of a micropipette and control the force applied on the oocyte. The oocyte remains in a culture medium during the compression cycle to preserve it from the environment. It is pushed by the moving micropipette against a vertical surface (a machined vertical well with important dimensions com- pared to the diameter of the oocyte). When a force F is applied on the well, the magnetic spring K x is compressed (see Fig. 1). Similar to a classical dynamometer, the compression length of the magnetic spring is proportional to the force applied on it, allowing a force calculation when the spring compression length is measured. Finally, the simultaneous measurement of F and compression length d oo (see Fig. 2) provides some behaviours of the oocyte under mechanical compression that will be presented in section 4.

z x y (R o ) M t 1 M b 1 M t 2 M b 2 (bt) M f 1 M f 2 F lo a ti n g p la tf o rm L iq u id M f 1 Kx 2 Ky 2

Physical principle of the force sensing device

The force sensing device is mainly composed of a floating platform. This floating platform constitutes the mobile part of a dynamometer on which the force to be measured is applied in the plane (xOy) as shown in Fig. 3 and4. Several magnetic springs are used to create a link between the platform and the stand of the system, to which a reference frame (R o ) is attached. The fixed top and bottom magnets M t 1 and M b 1 shown in Fig. 3 generate a force field centered on the vertical line (bt) going through them. As a result, the little magnet M f 1 , which is fixed on the platform, is constrained into a concentric force field (see Fig. 5) that is modeled by two orthogonal magnetic springs of stiffness Kx 2 and Ky 2 . The same magnet configuration is reproduced at the other extremity of the platform (magnets M b 2 , M t 2 and M f 2 ) providing a 3-DOF dynamometer of stiffness K x and K y along the x and y directions and a stiffness K ψ for the rotation ψ around the z axis. The use of this axis direction is not suitable for microforce measurement because the z displacement of the platform is not measured. When an external force F = (F x , F y ) T is applied to the platform at a point A, the position of the platform's center of gravity, G p , is modified (see Fig. 4). In steady state, according to [START_REF] Cherry | Analysis of a passive microforce sensor based on magnetic springs and upthrust buoyancy[END_REF], the relationship between the force and the displacement of the platform is given by Eq.:

x (R o ) y A F M f 2 M f 1 Special Petri dish G p Platform ψ
F = K m . X ⇔     F x F y M F /Gp     =     K x 0 0 0 K y 0 0 0 K ψ         G x p G y p sin ψ     (1)
in which the vector X contains the coordinates and orientation of the platform in the reference frame (R o ) attached to the stand. K m is the stiffness matrix of the magnetic springs and M F /Gp is the zcomponent of the momentum of the force F around G p . Assuming that M f 1 M f 2 = 2 δ, for a small rotation angle ψ, the rotational stiffness of the platform is :

K ψ = δ 2 K y
With this dynamometer, all the unattended dry friction forces are eliminated thanks to the liquid and floating principle. The viscous friction forces are canceled in steady states. The liquid menisci on the floats have no detectable effect on the force measurement [START_REF] Cherry | Analysis of a passive microforce sensor based on magnetic springs and upthrust buoyancy[END_REF].

Estimation of the force applied to the platform

To determine the force F that is applied onto the platform, it is necessary to measure the position of G p in (R o ). Then, the Eq. ( 1) is used to calculate the estimation ˆ F of the applied force F :

G p Oocyte Platform 7 1 1 1 Pipet C 1 C 2 C 3 2 2 2 5 l 1 l 2 l 3 2 δ δ
ˆ F = F x F y = K x 0 0 K y Ĝx p Ĝy p (2)
To determine the stiffness K x and K y of the magnetic springs, a calibration process is performed (see Section 2.6). One can note that M F /Gp will produce a rotation ψ of the platform that has no influence on the force estimation.

Experimental setup for oocytes characterisation

High resolution chromatic confocal displacement sensors5 are used to measure the position of G p (see Section 2.5). This choice requires the platform to be fitted with three deflectors labeled 1 in Fig. 6. These are glass deflectors with nanometric roughness. The three confocal sensors 2 are targeted on them. The experimental platform also includes the following parts shown in Fig. 6 and7: This entire device is placed on an anti-vibration table and into a closed chamber to minimize ground vibration and aerial disturbances. To ensure a constant temperature in the closed chamber, the device is always turned on at least 6 hours before any measurements. It is found that T chamber is equal to 29

3 fixed permanent magnets M t 1 , M b 1 , 4 fixed permanent magnets M t 2 , M b 2 , 3 4
• C ± 1 • C with a room temperature T room equals to 23 • C ± 1 • C.
Without the opportunity to regulate the temperature to 37 • C and to inject CO 2 gas, all the measurements are time constrained and have a duration shorter than ten minutes to avoid oocyte deterioration. Similar conditions are used by Vidberd for optical characterisation of oocytes [START_REF] Vidberg | Measurement of oocyte temporal maturation process by means of a simple optical micro-system[END_REF]. A vertical microscope placed above the Petri dish provides a magnified view of the oocyte during its mechanical characterisation.

A sterilized 35 mm diameter Petri dish is used. A well of 5 mm in diameter is machined in the center of the Petri dish. The oocyte is placed in this well. The micropipette moved by the manipulator is positioned in order to push the oocyte against the vertical wall of the well, as shown in Fig. 1. When the oocyte is compressed by the micropipette, the resulting force F against the wall is measured by the platform. The culture medium is correctly filled in order to ensure that the meniscus formed on the micropipette and the vertical wall of the Petri dish have no mutual interaction. The remaining force interactions between the micropipette and the edges of the Petri dish are studied in Section 3.

Calculation of the platform displacements

The three confocal sensors C 1 , C 2 , and C 3 , provide three distance measurements l 1 , l 2 , and l 3 , that correspond to the distance between the sensors and the deflectors (see Fig. 6). The geometric transformation between the three l i distances and G p is [START_REF] Cherry | Analysis of a passive microforce sensor based on magnetic springs and upthrust buoyancy[END_REF]:

G x p = δ 2 δ l 1 -2 δ l 2 + 4 δ l 3 -l 1 2 + l 2 2 4 δ 2 + l 1 2 -2 l 1 l 2 + l 2 2 G y p = δ l 1 2 -2 l 1 l 2 + 2 l 1 l 3 + l 2 2 -2 l 2 l 3 + 2 δ l 1 + 2 δ l 2 4 δ 2 + l 1 2 -2 l 1 l 2 + l 2 2 ( 3
)
where δ is the geometric characteristic of the platform that corresponds to the distance M f 1 M f 2 = 2 δ between the magnets M 1 f and M 2 f (and also to the distance between the confocal sensor C 1 and C 2 axis) as shown in Fig. 6.

Calibration of the force sensing platform

The calibration of the force sensing platform is crucial for reliable force measurements. It consists in determining the stiffness K x and K y of the magnetic springs before any measurements on the oocyte. A second order dynamic linear model corresponding to the association of a mass, a spring and a dash-pot system is written to model the behaviour of the mass of the platform, the magnetic spring and the friction of air and liquid on the floats:

M ¨ X + K f ˙ X + K m X = F (4) M =     m 0 0 0 m 0 0 0 J z     K f =     K x f 0 0 0 K y f 0 0 0 K ψ f    
where M is a matrix including the mass m and rotational inertia J z of the platform and K f is a matrix representing the friction. K m is the same matrix as in Eq. 1. The mass m is measured with a calibrated precision balance6 with a resolution set to 0.01 mg.

A set of fixed coils have been added to the device (see Fig. 7). They are able to apply an unknown force F onto the platform and to independently control the component F x (or F y ) of F . When a component F x (resp. F y ) is applied, it provides nonzero initial conditions on the position G x p (resp. G y p ) of the platform. The position is experimentally measured during a 15 second time interval after the cancellation of F x (or F y ). This measurement corresponds to the zero-input response of the platform ( F = 0 in Eq. ( 4) with some unknown initial conditions on the position and the velocity of the platform). The Matlab Identification Toolbox7 is used to calculate the parameters of Eq. ( 4). The detailed procedure is the following:

• measurement outside the device of the mass m of the platform, with a precision balance,

• generation of a current step into the coils to produce a force component F x (resp. F y ),

• 10 seconds delay,

• cancellation of the current step ( F =0),

• 2 seconds delay,

• measurement of the platform position G x p (or G y p ) during a time interval of 15 seconds (see Fig. 8),

Platform setup

Force F applied onto the oocyte by the pipet Geometric transformation • identification of model parameters and initial conditions in x (resp. y) direction using the Matlab model identification toolbox,

  l 1 l 2 l 3   Force estimation G x p G y p K x ,K y F
• simulation of the model for an elapsed time of 15 seconds with the identified initial conditions,

• comparison of the response time of the model to the experimental data G x p (resp. G y p ) measured (see Fig. 8),

• extraction of K x and K y from the model,

• activation of the force estimation on the experimental device.

The temporal response of the model given in Fig 8 shows a good accordance with the experimental data, insuring correct reliability of the force estimation. As with every micro and nanoforce sensor, it is difficult to quantify reliability of the force estimate. (No micro and nanoforce standards are available.) The difference between the data and the model is due to force disturbances that come from the room environment where the experimental device is placed. Aerial disturbances and ground vibrations, in particular, have a great influence on the calibration quality and have to be maintained as low as possible during the calibration process, as well as during force measurements. The synopsis of the measuring chain is given in Fig. 9. Typically, the resolution of the force estimation is lower than ±20 nN.

Characterization of the culture medium

Once placed in its correct position inside the IVF medium 8 , the body of the micropipette goes through the surface of the liquid and a mechanical interaction is possible between them. Thus, prior to oocyte stiffness measurements, the sensor response in different liquid medium is analyzed. Each liquid medium is stored in a fridge at 4 • C in its primary packaging. A volume sample of 1,4 ml ±0, 1 ml is taken with a pipette and placed into the 35 mm diameter Petri dish inside the chamber. The measurement of the liquid medium is started ten minutes after to ensure that the temperature of the sample is equal to that of the chamber (29 • C). Then, the following experimental measurement protocol is used:

• positioning of the micropipette 1 mm above the surface of the medium in the center of the Petri dish,

• 20 µm/s vertical displacement of the micropipette until it reaches a position 100 µm above the bottom of the Petri dish (see Fig. 11),

• successive horizontal x displacements of the micropipette by steps of 40 µm at 20 µm/s on a displacement range that extends from 0 to 400 µm, then to -400 µm and followed by a return to zero,

• a time-delay of 10 seconds is performed before the force acquisition at the end of each step to insure a quasi-static configuration in order to cancel the viscous friction force.

All stop and go movements of the micropipette are performed automatically by the Eppendorf manipulator which has been programmed to follow this protocol. Fig. 10 shows the obtained results for four different mediums: air, water, the IVF medium and bovine serum albumin (BSA). The test without liquid (air medium) is taken as a reference. In this test, the oscillations of the curve represent the measurement noise and the maximum reached by these

8 IVF TM Vitrolife, Sweden
oscillations gives the resolution range of ±20 nN of this particular setup. The disturbances measured for a Petri dish filled with water do not show any influence of the water (same noise amplitude as in air).

The IVF medium used for oocyte characterisation is a solution composed of a bicarbonate-buffered medium containing human serum albumin and penicillin G as an antibacterial agent. Once placed in its correct position inside this IVF medium, a disturbance force is measured by the platform when the micropipette is moved in the horizontal direction (see Fig. 10). This force, which is different than the one obtained with air or liquid medium, can degrade the measurement of the force applied onto the oocyte. It is inferred that this force may be due to the surface tension of the IVF medium. Indeed, the sum of the surface tension at the junction of the micropipette, the air, and the liquid medium is equivalent to a disturbance force F st with a horizontal component F h which can be directly measured by the sensor (see Fig. 11). This force is the result of the three surface tensions between the air/liquid/solid interfaces. The albumin present in the culture medium acts as a surfactant which modifies the surface tension of the liquid [START_REF] Rienzi | Predictive value of oocyte morphology in human ivf: a systematic review of the literature[END_REF]. Surface tensions of water and IVF medium measured by the Wilhelmy plate (Kruss tensiometer) are γ water = 71 mN/m and γ IV F =54mN/m, respectively.

A test with a bovine serum albumin (BSA) prepared with a concentration of 10 g/l and presenting a surface tension γ BSA equal to γ IV F shows a force profile with the same tendency as the IVF medium with a maximum disturbance force of 100 nN for BSA versus 230 nN for IVF medium (see Fig. 10). This preliminary investigation shows that the albumin, which acts as a surfactant, plays a role in the measured force disturbance. This will degrade the force measurement on oocytes and there is no IVF medium free of albumin that could be used to avoid this force disturbance. Further experiments are under investigation to study the effect of the different compounds of the IVF solution on its surface tension. Additional investigation has been performed in order to determine the disturbance curve of the IVF medium. Measurements with culture medium coming from different packaging syringes show the same trend but the value of the disturbance force is unpredictable (see Fig. 12). A sample has been kept in the chamber at 29 • C in order to perform measurement at different time intervals and during several hours. No significant differences have been measured during the ageing of the medium for consecutive measurements at constant temperature, on a sample coming from the same packaging.

The different responses of the sensor in water, IVF, or BSA mediums should not be due to the drag force. This force is the resistance to the motion of the micropipette and depends on the viscosity of the solution, on the shape, and on the velocity of the moving object. As the measurements are carried out in static conditions (10 seconds after each displacement of the micropipette), the drag force should be negligible. However, the effect of waiting time before the force measurements has to be studied. The physical phenomenon that provides the force hysteresis in IVF medium remains unexplained. To determine the effect of the IVF medium disturbance when the oocyte is characterized, it is proposed that the disturbance after each stiffness measurement is evaluated and compensated for, as shown in Section 4.3.

Holding micropipet

Experimental measurement of oocytes stiffness

Oocytes preparation

Oocytes used in this study are immature oocytes collected during ICSI protocol. Before the microinjection, the cumulus cells surrounding the oocyte are cleared away by association of hyaluronidase digestion for about 20 seconds (80 IU Hyaluronidase in Flushing, Fertipro, Belgium), a mechanical removal of the cumulus is performed using denudation pipettes (SWEMED by Vitrolife, Sweden) and finally, oocytes are rinsed in IVF medium and individually observed under an inverted microscope (×200 magnification). The mature oocytes at the metaphase II (MII) meiotic maturation stage, with the presence of the first polar body and the absence of germinal vesicle, are reserved for the assisted reproductive technology (ART) and the injection of a single spermatozoa into the cytoplasm of the oocyte is performed.

The immature oocytes, at the germinal vesicle (GV) stage equal to the prophase stage of the first meiotic division, or at any stages between the germinal vesicle breakdown stage (GVBD) and the anaphase of the meiosis I, are dismissed and used for the present study. For technical reasons, the exact meiotic stage of these oocytes cannot be verified so they are classified as GVBD/MI immature oocytes. These immature oocytes are incubated in the usual IVF medium at 37 • C and 5% CO2 for a duration of 1 to 3 hours, until the stiffness measurement is performed. In these culture conditions, some of these oocytes can progress to the final maturation process and reach the MII stage. Two types of oocytes are individualized for this study, the group of the oocytes which reaches the MII stage and the group which does not reach the MII stage and that is classified as GVBD/MI. The use of these immature oocytes has been approved for our experiments by the clinical ethics committee of Besançon University Hospital on June 9th 2010.

The force sensing platform is prepared as follows: the special Petri dish is initially filled with IVF medium and placed onto the platform which has to be configured for force measurements (calibration already done). The measurement of the temperature of the IFV medium placed into the sensor chamber gives a temperature T IV F equals to 29 • C. After the maturation process, the oocytes are carried near the force measurement platform into an insulated box. Each oocyte is individually picked up with a Pasteur pipette and released into the machined well at 29 • C. The operator uses the Eppendorf manipulator equipped with a micropipette to push the oocyte and place it in a correct position against the well border as shown in Fig. 13. The diameter φ corresponding to the diameter of the external face of the zona pellucida is measured using the microscopic view. The diameter φ c of the cytoplasm is also measured to provide the morphology of the oocyte.

First experiment on an oocyte

The first oocyte O 1 to be characterized is classified GVBD/MI with a diameter φ equal to 160 µm (φ c = 112 µm). The micropipette used is 35 µm in diameter. Fig. 14 shows the curve obtained for a loading until the compression length of the oocyte d oo (see Fig. 2) reach 120 µm, followed by an unloading until the tip of the micropipette (P x dorf coordinate) returns to its initial position. The speed of the micropipette is held constant by the internal control of the Eppendorf manipulator and is equal to 10 µm/s for loading and unloading cycles. The entire cycle is programmed and performed automatically. The low speed insures a quasi-static behaviour. The oocyte compression length d oo is calculated from the difference of the relative displacement of the Eppendorf manipulator and the platform position. The compression length d oo is equal to zero when the micropipette tip reaches the oocyte placed against the well border without any deformation or force measured by the sensor.

The curve F x Oocyte+IVF (d oo ) given in Fig. 14 is the result obtained with the oocyte labelled O 1 . The behaviour of this oocyte during loading is not linear. When the compression length d oo reaches 120 µm, the measured force is 1.15 µN and represents the sum of the oocyte and the IVF medium contributions. During unloading, the hysteresis measured corresponds to the plastic deformation (see unloading curve in Fig. 14). The oocyte recovers its initial shape a few minutes after the test. One can notice some residual oscillations on the curve which may be due to the poor quality of the speed control law implemented inside the Eppendorf manipulator. The disturbance contribution of the IVF medium has to be removed from this curve in order to have the single oocyte contribution.

Compensation of the IVF medium disturbance

After each measurement on the oocyte, a special cycle is programmed inside the Eppendorf manipulator in order to reproduce the relative displacement of the micropipette into the IVF medium alone at the same speed as during the test on the oocyte, but this time the tip is placed beside the oocyte as shown in Fig. 15. This relative displacement is limited to d max oo , which is the maximum displacement (12 × 10 -5 m in Fig. 14) performed previously, during the oocyte O 1 characterisation. The curve F x IVF only (d oo ) corresponding to the IVF medium alone (see Fig. 15) is obtained. A second-order polynomial F x IVF f it (d oo ) is fitted to the curve F x IVF only (d oo ). Finally the curve F x Oocyte only (d oo ) corresponding to the oocyte alone is calculated with the following formula: The influence of the IVF medium disturbance is not negligible. Its compensation offers a better stiffness characterisation of the oocyte. At the end of the unloading curve corresponding to "Oocyte only", one can notice that the force becomes close to zero with a negative trend just higher than the resolution of the sensor (±20 nN). This is due to an adhesion force between the micropipette tip and the zona pellucida.

F x Oocyte only (d oo ) = F x Oocyte+IVF -F x IVF f it (5)
All the measurements presented in the next Sections include a systematic IVF medium characterisation and compensation. Only the curves F x ovo (d oo ) are given. first two are mature (metaphase II) and the others are immature (GVBD/MI). Their stiffness characteristic curves are given in Fig. 17. Two parameters, K oo and H α , are defined to quantify their mechanical behaviour (see Fig. 17). The parameter K oo is the linear stiffness of the oocyte calculated by fitting a straight line on the loading linear response, when d oo is lower than 50 µN. The second parameter H α is the maximum hysteresis amplitude between loading and unloading. It represents the oocyte's ability to recover its initial shape during the test: the greater H α , the greater the residual plastic deformation that the oocyte finally recovers a few minutes after the test.

Comparison between different oocytes

A low value of H α means that the oocyte tends to an elastic behaviour without energy dissipation. Table 1 summarizes the behaviour of each oocyte. Distinction between mature and immature oocytes cannot be made based on these mechanical criteria. A significant difference is detected between the two mature oocytes, O 2 and O 3 . The O 3 oocyte has reached its meiotic competence, but contrary to the O 2 , it has not reached its optimal terminal diameter. An interpretation of this result could be that the higher stiffness of O 3 may indicate immaturity of the cytoplasm. The stiffness of O 2 is lower than O 3 , but it has a greater capacity to recover its shape during the unloading.

Tests with an injection needle

Fig. 18 shows the results obtained for an injection cycle done on the metaphase II oocyte O 6 with a diameter of 150 µm (φ c = 108 µm). An empty (without sperm) injection needle with a diameter of 6 µm is used. On the first injection cycle, the perforation of the cytoplasmic membrane occurs for d oo = 98 µm when the force applied to the oocyte reaches F x ovo = 0.90 µN. The stiffness measured is K 1 oo = 4.8 mN/m. No sperm is expelled into the oocyte and the micropipette is simply removed from the oocyte. After a delay of 15 minutes, a second injection cycle is done on the same oocyte. This time, no perforation occurs and the stiffness measured decreases: K 2 oo = 2.8 mN/m. This phenomenon could be caused by the stress produced by the initial perforation.

4.6. Evolution of the characteristics of an oocyte placed in bad culture conditions Fig. 19 shows the results obtained for consecutive loading cycles on the GVBD/MI oocyte O 7 with a diameter of 154 µm (φ c = 111 µm). The test is performed with a standard holding micropipette with a diameter of 85 µm. 10 minutes after an initial loadunload cycle, a second identical cycle is performed. Then, new cycles are performed 1 hour later, 1h10 later and 1h20 later. The oocyte stays at chamber temperature in the same Petri dish and in the same IVF medium during the entire duration of this test. In these culture conditions, the normal maturation process is perturbed. Nevertheless, this test can provide interesting information on the oocyte evolution once placed in non-optimal conditions. It remains to establish that a single oocyte showing a similar mechanical evolution during its normal maturation could be considered evolving incorrectly. structure can be observed using repeated load-unload cycles. This increase is greater after a delay of one hour and is confirmed by the evolution of the H α parameter. Nevertheless, the question of the neutrality of these measurement cycles on the oocyte evolution (mechanical stress or fatigue), still remains to be investigated.

Conclusion and perspectives

The human oocyte selection plays a critical role in ART success rate. In order to improve this rate, new instrumentation is necessary to extend the usual protocols used by physicians to determine the oocytes' quality and maturity level. This new instrumentation must be compatible with ART constraints.

Among the new technologies available to determine the maturity level of a human oocyte, the characterisation of its mechanical properties is potentially interesting and has to be investigated. This study requires a force sensor with a very low stiffness to have a high resolution and also a large measurement range if large deformations have to be characterised. Force sensors based on magnetic springs have such characteristics and could potentially be a part of this new instrumentation. This article presents some preliminary results obtained with a floating platform using a magnetic spring dynamometer. Since the final objective is to sort human oocytes and since it is difficult to extrapolate data obtained with an animal model to human ART, these preliminary results are only carried out with human oocytes. The preliminary results demonstrate that is it possible to visualize mechanical load-unload cycles applied on human oocytes despite their very low stiffness (around 10 mN/m). The human oocyte elastic behaviour during the mechanical load (compression stage) seems linear for low loading and non-linear for high loading. After a high loading, a plastic behaviour is associated with the unload stage. The "force-compression length" curves obtained are different for different oocytes and seem to evolve with time. Two basic parameters have been suggested to quantify the oocytes' mechanical behaviour, but the question of extraction of discriminant parameters from these curves or from the raw force signal remains open and has to be investigated. The evolution of these parameters could be correlated to the global cytoplasmic and nuclear maturity of the investigated oocytes

The main drawback of the actual device used to perform these cycles of measurement is that the complex mechanical influence of the IVF medium is not negligible and has to be compensated for, which makes the experimental measurement protocol rather complex. A special Petri dish also has to be used. The development of a new force-sensing platform design, based on magnetic springs that avoid these drawbacks, is the next step to perform. To be effective, this new technology should be fully compatible with physician's protocols and constraints, but should also provide analysis methods, preferably on a multimodal basis, to improve the reliability of oocyte maturity diagnosis. Both mechanical and optical approaches are thought effective to establish a reliable diagnosis despite the variability of the oocytes' evolution [START_REF] Zeggari | A full micro-fluidic system for single oocyte manipulation including an optical sensor for cell maturity estimation and fertilisation indication[END_REF][START_REF] Wacogne | Microsensors and image processing for single oocyte qualification: towards multiparametric determination of the best moment for fertilization[END_REF]. The mechanical tests will provide the stiffness determination of oocytes for different loads. Referenced optical characterisation techniques based on Karhunen-Loeve tranform [START_REF] Pieralli | Biological qualification of oocyte maturity with the use of the karhunen-loeve transform: Computer-aided decision for selecting best oocytes before fertilization[END_REF] or a spectral absorption analysis [START_REF] André | Measuring the oocyte cytoplasmic maturation process with a white light optical microsystem[END_REF] are also promising because they have no deleterious effects on oocytes. Thus, a potentially interesting future design should be based on a modular micromechanical / optical device including a high sensitive nanoforce sensor based on magnetic springs. All parts in direct contact with the oocyte have to be low-cost, sterile and disposable.

The oocyte state at a given time can be represented by a feature vector extracted from all available multiphysics data (mechanical, optical, morphological, morphometrics) and each oocyte maturity process is then represented by a specific trajectory in the multi-dimensional parametric space associated to the feature vector components. With such representation, the maturity diagnosis could be done thanks to supervised classification approaches [START_REF] Bishop | Pattern recognition and machine learning[END_REF]. These approaches are based on a training process for which the feature vectors of some specific oocytes are labelled in time according to the different stages of maturity (set-membership approaches). After this training process, the classification algorithm goal is to provide a label affectation for each new feature vector evolving in time. In the specific case of the IFV context, the choice of the feature vector components is critical for the effectiveness of the classification and the classification algorithm should also be able to manage the unavoidable uncertainty that is associated with each labeling during the training process. Classification algorithms based on Dempster-Shafer theory of evidence that enable such framework could provide interesting methods for investigation [START_REF] Ramasso | Joint prediction of observations and states in time-series: a partially supervised prognostics approach based on belief functions and knn[END_REF].

Acknowledgement

This collaborative work has been supported by the Labex ACTION project (contract "ANR-11-LABX-01-01")

Bibliography

[1] Y. Murayama, C.E. Constantinou, and S. Omata. Micro-mechanical sensing platform for the characterization of the elastic properties of the ovum via uniaxial measurement. J. Biomech., 37:67-72, 2004.

[2] T. Woodruff and L. Shea. A new hypothesis regarding ovarian follicle development: ovarian rigidity as a regulator of selection and health. Journal of Assisted Reproduction and Genetics, 28(1):3-6, 2011.

Figure 2 :

 2 Figure 2: The compressed oocyte with the forces applied on it and the resulting compression length doo.

Figure 3 :

 3 Figure 3: Principle of the force sensing platform.

Figure 4 :

 4 Figure 4: Behaviour of the floating platform when a force F is applied on it.

Figure 5 :

 5 Figure 5: Force field generated perpendicularly to the vertical line (bt) by magnets M t 1 and M b 1 and applied to M f 1 (magnetic spring).

Figure 6 :

 6 Figure 6: Displacement measurement of the platform with confocal sensors.

Figure 7 :

 7 Figure 7: Experimental setup of the force sensor.

5

  platform permanent magnets M f 1 , M f 2 , 6 liquid tank filled with water, 7 special Petri dish filled with a culture medium in which the oocyte is placed, 8 coils used to calibrate the force measurement chain.The following elements are specially added for oocytes characterisation: 9 Eppendorf manipulator, 10 micropipette holder, 11 vertical microscope.

Figure 8 :

 8 Figure 8: Comparison between the free response of the identified model and the displacement measurement of the platform.

Figure 9 :

 9 Figure 9: Measuring chain of the force sensing platform.

Figure 10 :Figure 11 :

 1011 Figure 10: Measurement of surface tension disturbances for different liquid mediums at 29 • C.

Figure 12 :

 12 Figure 12: Measurement of surfaces tension disturbances for three different packaging syringes of IVF medium at 29 • C.

Figure 13 :

 13 Figure 13: Oocyte correctly placed against the wall and ready for a loading cycle with an holding micropipette.

Figure 14 :

 14 Figure 14: Oocyte O 1 stiffness characterisation without disturbance correction of the IVF medium.

Figure 15 :

 15 Figure 15: Oocyte O 1 stiffness characterisation including IVF medium characterisation and compensation.

O 2 :

 2 φ = 155 µm O 3 : φ = 145 µm O 4 : φ = 150 µm O 5 : φ = 154 µm MII φ c = 117 µm MII φ c = 109 µm GVDB/MI φ c = 115 µm GVDB/MI φ c = 109 µm

Figure 16 :

 16 Figure 16: Visualization of the four different oocytes.

FourFigure 17 :

 17 Figure 17: Stiffness comparison between several oocytes using holding micropipette.

6 P e r f o r a t i o nFigure 18 :

 618 Figure 18: Force measurement for two successive injection cycles on the oocyte O 6 .

7 Figure 19 :

 719 Figure 19: Evolution of the stiffness of the dying oocyte O 7 (GVBD/MI).

Table 1 :

 1 Results for the four oocyte characterisations.

	Label	K oo (mN/m) H α (µN)
	O 2 (MII)	3.1	0.26
	O 3 (MII)	11.2	0.57
	O 4 (GVBD/MI)	9.3	0.58
	O 5 (GVBD/MI)	7.2	0.38

  Table 2 shows the evolution versus time of the two parameters K oo and H α corresponding to the oocyte O 7 . An important increase of the oocyte stiffness is visible, showing that a mechanical variation of the oocyte Time K oo (mN/m) H α (µN)

	initial	7.2	0.45
	t=10min	7.6	0.43
	t=1h	9.3	0.68
	t=1h10	12.8	0.69
	t=1h20	13.4	0.67

Table 2 :

 2 Results for the consecutive loadings on the oocyte O 7 (GVBD/MI).

Intracytoplasmic Sperm Injection

Eppendorf TransferMan NK2

Stil confocal sensor, model CL4, 0.1 µm resolution

Mettler-Toledo MS105DU

provided by Mathworks

List of Figures

Forces applied on the force sensing device when an oocyte is under a compression test. . . . . 3 2

The compressed oocyte with the forces applied on it and the resulting compression length d oo .


Sébastien Gouëzel
email: sebastien.gouezel@univ-rennes1.fr

A NUMERICAL LOWER BOUND FOR THE SPECTRAL RADIUS OF RANDOM WALKS ON SURFACE GROUPS

Keywords: spectral radius, cogrowth, numerical algorithm, surface groups. 1

Estimating numerically the spectral radius of a random walk on a nonamenable graph is complicated, since the cardinality of balls grows exponentially fast with the radius. We propose an algorithm to get a bound from below for this spectral radius in Cayley graphs with finitely many cone types (including for instance hyperbolic groups). In the genus 2 surface group, it improves by an order of magnitude the previous best bound, due to Bartholdi.

Main algorithm

Let Γ be a countable group, generated by a finite symmetric set S of cardinality |S|. The simple random walk X 0 , X 1 , . . . on Γ is defined by X 0 = e the identity of Γ, and X n+1 = X n s with probability 1/ |S| for any s ∈ S. A crucial numerical parameter of this random walk is its spectral radius ρ = lim P(X 2n = e) 1/2n . Equivalently, denote by W n the number of words of length n in the generators that represent e in Γ, then P(X n = e) = W n / |S| n , so that ρ = lim W 1/2n 2n / |S|. It is equivalent to study the spectral radius or the cogrowth lim W 1/2n 2n . The spectral radius is at most 1, and ρ = 1 if and only if Γ is amenable. In the free group with d generators, the generating function W n z n can be computed explicitly (it is algebraic), and the exact value of the spectral radius follows: ρ = √ 2d -1/d. Since words that reduce to the identity in the free group also reduce to the identity in any group with the same number of generators, one infers that in any group Γ, ρ 2 |S| -1/ |S|. Moreover equality holds if and only if the Cayley graph of Γ is a tree [START_REF] Kesten | Symmetric random walks on groups[END_REF].

In general, there are no explicit formulas for ρ, and even giving precise numerical estimates is a delicate question. In this short note, we will describe an algorithm giving bounds from below on ρ in some classes of groups, particularly for the fundamental group Γ g of a compact surface of genus g 2, given by its usual presentation (1.1)

Γ g = a 1 , . . . , a g , b 1 , . . . , b g | [a 1 , b 1 ] • • • [a g , b g ] = e .
Since there are 4 generators in Γ 2 , the above trivial bound obtained by comparison to the free group gives ρ 0.661437. Our main estimate is the following result.

Theorem 1.1. In the surface group Γ 2 , one has ρ 0.662772.

This improves on the previously best known result, due to Bartholdi [Bar04], giving ρ ρ Bar = 0.662421. 1 Bartholdi's method is to study a specific class of paths from the identity to itself (called cactus trees), for which he can compute the generating function.

The radius of convergence of this generating function is a lower bound for ρ.

The best known upper bound for ρ in Γ 2 is ρ ρ Nag = 0.662816, due to Nagnibeda [START_REF] Nagnibeda | An upper bound for the spectral radius of a random walk on surface groups[END_REF]. Non-rigorous numerical estimates 2 suggest that ρ = 0.662812 . . . , so the upper bound is still sharper than our lower bound, although our lower bound is an order of magnitude better than the bound of [START_REF] Bartholdi | Cactus trees and lower bounds on the spectral radius of vertex-transitive graphs[END_REF]: indeed, ρ Nag -ρ Bar ∼ 4.10 -4 while our estimate ρ from Theorem 1.1 satisfies ρ Nag -ρ ∼ 4.10 -5 .

Nagnibeda's upper bound does not rely on a counting argument for closed paths, but on another spectral interpretation of ρ. Indeed, ρ is also the spectral radius of the Markov operator Q on ℓ 2 (Γ) corresponding to the random walk, i.e., the convolution with the probability measure µ which is uniformly distributed on S (see for instance [Woe00, Corollary 10.2]). It is also the norm of this operator, since it is symmetric. Nagnibeda gets the above upper bound by using a lemma of Gabber about norms of convolution operators on graphs and the precise geometry of Γ 2 .

Our approach to get Theorem 1.1 is very similar to Nagnibeda's. To bound from below the norm of the convolution operator Q, it is sufficient to exhibit one function u (which ought to be close to an hypothetic eigenfunction for the element ρ of the spectrum of Q) for which Qu / u is large. This is exactly what we will do.

For any α < ρ, the function u α = ∞ n=0 α n Q n δ e is in ℓ 2 , and Qu α / u α converges to ρ when α tends to ρ. Unfortunately, u α is not explicit enough. To find estimates, one should rather find an ansatz for the function u, depending on finitely many parameters, and then optimize over these parameters.

A first strategy would be the following: take a very large ball B n in the Cayley graph, and compute the function u supported in this ball such that Qu / u is largest. This gives a lower bound ρ n on ρ, and ρ n converges to ρ when n tends to infinity. However, this strategy is computationally not efficient at all: one would need to take a very large n to obtain good estimates (since most mass of u α is supported close to infinity if α is close to ρ), and the cardinality of B n grows exponentially with n. On the other hand, it can be implemented in any finitely presented group for which the word problem is solvable (see for instance [START_REF] Elder | On the cogrowth of Thompson's group F , Groups Complex[END_REF] for examples in Baumslag-Solitar and Thompson groups). We will use a 2 I obtained this estimate as follows: one can count exactly the number Wn of words of length n representing the identity in the group, for reasonable n, say up to n = 24 -for the record, W24 = 4214946994935248 -giving the first values of the sequence pn = P(X2n = e). We know rigorously from [START_REF] Gouëzel | Random walks on co-compact Fuchsian groups[END_REF] that pn ∼ Cρ 2n /n 3/2 when n → ∞. Define qn = log(n 3/2 pn)/(2n), it follows that qn → log ρ. In the free group, where pn is known very explicitly, the sequence qn has a further expansion in powers of 1/n. Assuming that the same holds in the surface group, we get qn = log ρ

+ K k=1 a k /n k + o(1/n K )
where the a k are unknown. Using the known value of q24, this gives an estimate for log ρ, with an error of the order of 1/24, which is very bad. However, it is possible to accelerate the convergence of sequences having an asymptotic expansion in powers of 1/n: there are explicit recipes (for instance Richardson extrapolation or Wynn's rho algorithm) taking such a sequence, and giving a new sequence converging to the same limit, with an expansion in powers of 1/n, but starting at 1/n 2 . Iterating this process, one can eliminate the first few terms, and get a speed of convergence O(1/n L ) for any L (but one needs to know enough terms of the initial sequence). Applying this process to our sequence qn, one gets the claimed estimate for ρ. To make this rigorous, one would need to know that an asymptotic expansion of qn exists, with explicit bounds on the a k and on the o(1/n K ) term. This seems completely out of reach. more efficient method, but which requires more assumptions on the group: it should have finitely many cone types.

To illustrate our method of construction of u, let us describe it quickly in the case of the free group F d with d generators. The sphere S n of radius n 1 has cardinality 2d(2d-1) n-1 . Fix some α < 1/ √ 2d -1, and define a function u α by u α (x) = α n for x ∈ S n , n 1. This function belongs to ℓ 2 (F d ). We write x ∼ y if x and y are neighbors in the Cayley graph of Γ, and x → y if x ∼ y and d(e, y) = d(e, x) + 1. Then

Qu α , u α = 1 2d x∼y u α (x)u α (y) = 1 d x→y u α (x)u α (y) = 1 d ∞ n=1 (2d -1)α 2n+1 |S n | , since a point in S n has 2d -1 successors in S n+1 . Since u α , u α = ∞ n=1 α 2n |S n |, we get Qu α , u α = α 2d -1 d u α , u α .
Hence, ρ = Q α(2d -1)/d. Letting α tend to 1/ √ 2d -1, we finally obtain ρ √ 2d -1/d, which is the true value of the spectral radius.

In the free group, it is natural to take a function u that is constant of the sphere S n of radius n, since all the points in such a sphere are equivalent: the automorphisms of the Cayley graph of F d fixing the identity act transitively on S n . In more general groups, for instance surface groups, this is not the case. Intuitively, we would like to take a function that decays exponentially as above, but with different values on different equivalence classes under the automorphism group. However, this automorphism group is finite in the case of surface groups, so instead of true equivalence classes (which are finite), we will consider larger classes, of points that "locally behave in the same way", and we will construct functions that are constants on such classes of points (leaving only finitely many parameters which one can optimize using a computer).

This intuition is made precise with the notion of type of the elements of the group (as in [START_REF] Nagnibeda | An upper bound for the spectral radius of a random walk on surface groups[END_REF]). Let Γ be a countable group generated by a finite symmetric set S. Assume that there are no cycles of odd length, so that any edge can be oriented from the closer point from e to the farther point. Let S(x) be the set of successors of x, i.e., the points y which are neighbors of x with d(e, y) = d(e, x) + 1. Definition 1.2. Let T be a finite set, let t be a function from Γ to T and let M be a square matrix indexed by T . We say that (T, t, M ) is a type system for (Γ, S) if, for all i and j in T , for all but finitely many x ∈ Γ with t(x) = j, one has

Card{y ∈ S(x) : t(y) = i} = M ij .
We will often simply say that t is a type system, since it determines T and M .

In other words, if one knows the type of a point x, then one knows the number of successors of each type, thanks to the matrix M . For instance, in F d , one can use one single type, with M 11 = 2d -1: every point but the identity has 2d -1 successors. Using a type system, we will be able to find a lower bound for the spectral radius of the simple random walk. While the argument works in general, it is more convenient to formulate using an additional assumption, which is satisfied for surface groups.

Definition 1.3. A type system (T, t, M ) is Perron-Frobenius if the matrix M is Perron-Frobenius, i.e., some power M n has only positive entries.

The algorithm to estimate the spectral radius follows.

Theorem 1.4. Let (Γ, S) be a countable group with a finite symmetric generating set, whose Cayley graph has no cycle of odd length. Let (T, t, M ) be a Perron-Frobenius type system for (Γ, S).

Define a new matrix M by Mij = M ij /p i , where p i is the number of predecessors of a point of type i (it is given by p j = |S|i M ij ). Since it is Perron-Frobenius, its dominating eigenvalue e v is simple. Let (A 1 , . . . , A k ) be a corresponding eigenvector, with positive entries, let D be the diagonal matrix with entries A i , and let

M ′ = D -1/2 M D 1/2 . Define (1.2) λ = max |q|=1 M ′ q, q .
Then

(1.3) ρ 2e -v/2 λ |S| . Proof. Let s n (i) = Card{x ∈ S n : t(x) = i}.
By definition of a type system, if n is large enough (say n n 0 ),

p i s n+1 (i) = y∈S n Card{x ∈ S(y) : t(x) = i} = j M ij s n (j).
This shows that s n+1 = M s n . Therefore, the cardinality of S n grows like ce nv for some c > 0. Moreover, s n (i) = c ′ A i e nv + O(e n(v-ε) ) for some ε > 0.

Take some parameters b 1 , . . . , b k > 0 to be chosen later, and let α < e -v/2 . We define a function u α by u α (x) = α n b i if x ∈ S n and t(x) = i with n n 0 . For n < n 0 , let u α (x) = 0. We have when α tends to e -v/2

Qu α , u α = 1 |S| x∼y u α (x)u α (y) = 2 |S| x y∈S(x) u α (x)u α (y) = 2 |S| n n 0 i,j s n (j)b j α n M ij b i α n+1 = 2α |S| n n 0 i,j c ′ A j e nv b j α 2n M ij b i + O(1) = 2α |S| i,j c ′ A j b j M ij b i /(1 -α 2 e v ) + O(1).
On the other hand,

u α , u α = n n 0 i s n (i)b 2 i α 2n = n n 0 i c ′ A i e nv b 2 i α 2n + O(1) = i c ′ A i b 2 i /(1 -α 2 e v ) + O(1).
We have ρ Qu α , u α / u α , u α . Comparing the above two equations and letting α tend to e -v/2 , we get

ρ 2e -v/2 |S| i,j A j b j M ij b i i A i b 2 i .
To conclude, we need to optimize in b i . Writing b i as A -1/2 i c i , this lower bound becomes

2e -v/2 |S| A 1/2 j c j M ij A -1/2 i c i c 2 i .
The maximum of the last factor is the maximum on the unit sphere of the quadratic form with matrix M ′ = D -1/2 M D 1/2 . This proves (1.3).

Remark 1.5. It follows from the formula (1.2) that λ is the maximum on the unit sphere of M ′′ q, q , where M ′′ is the symmetric matrix (M ′ + M ′ * )/2. Since any symmetric matrix is diagonal in some orthogonal basis, it also follows that λ is the maximal eigenvalue of M ′′ , i.e., its spectral radius. Hence, it is easy to compute using standard algorithms.

The formula given by Theorem 1.4 depends not only on the geometry of the group, but also on the choice of a type system: in a given group (with a given system of generators), there may be several type systems, giving different estimates. We will take advantage of this fact for surface groups in Section 3: applying Theorem 1.4 with the canonical type system for surface groups, constructed by Cannon, we obtain in (3.1) an estimate for the spectral radius which is weaker than the estimate of Theorem 1.1. This stronger estimate is proved by applying Theorem 1.4 to a different type system, constructed as a refinement of the canonical type system. This dependence on the choice of a type system should be contrasted with the upper bound of Nagnibeda in [START_REF] Nagnibeda | An upper bound for the spectral radius of a random walk on surface groups[END_REF]. Indeed, it is shown in [START_REF]Random walks, spectral radii, and Ramanujan graphs[END_REF] that this upper bound, computed using a type system, has a purely geometric interpretation (it is the spectral radius of a random walk on the tree of geodesics of the group), which does not depend on the choice of the type system. In particular, the refined type system we use to prove Theorem 1.1 can not improve the upper bound of Nagnibeda.

Acknowledgments: We thank the anonymous referee for pointing out the reference [START_REF]Random walks, spectral radii, and Ramanujan graphs[END_REF], and suggesting that there might be a possible geometric interpretation to the lower bound in Theorem 1.4, as in [START_REF]Random walks, spectral radii, and Ramanujan graphs[END_REF]. This led to Section 2 below.

Geometric interpretation

In this section, we describe a geometric interpretation of Theorem 1.4, similar to Nagnibeda's interpretation in [START_REF]Random walks, spectral radii, and Ramanujan graphs[END_REF] of the bound she obtained in [START_REF] Nagnibeda | An upper bound for the spectral radius of a random walk on surface groups[END_REF].

We first recall Nagnibeda's construction. Consider a group Γ with a finite system of generators S, whose Cayley graph has no cycle of odd length. Let X be its tree of geodesics, i.e., the graph whose vertices are the finite geodesics in Γ originating from the identity e, and where one puts an edge from a geodesic with length n to its extensions with length n + 1. There is a canonical projection π X from X to Γ, taking a geodesic to its endpoint. One can think of X as obtained from Γ by unfolding the loops based at e. Consider the random walk in X whose transitions are as follows: from x, one goes to any of its successors with probability 1/ |S|, and to its unique predecessor with probability p x / |S| where p x is |S| minus the number of successors of x (it is the number of predecessors in Γ of the projection π X (x)). This random walk on X does not project to the simple random walk on Γ, since it does not follow loops in Γ (the projected random walk is not Markov in general). The transition probabilities coincide when going towards infinity, but not when going back towards the identity. One expects that the probability to come back to the identity is higher in X than in Γ, thanks to the following heuristic: since the process in X is less random when coming back toward the identity, once the walk is in a subset where it comes back often to the identity, it can not escape easily from this subset, and therefore returns even more.

To illustrate this heuristic, suppose that two points x and x ′ in X (with p x = p x ′ = 2) have successors y and y ′ in X, and consider a new random walk in which y and y ′ are identified (this is what the projection π X does, all over the place), so that from this new point one can either jump back to x or to x ′ with probability 1/ |S|. Let u n and u ′ n be the probabilities in X to be at time n at x and x ′ . For the sake of the argument, we will assume some form of symmetry, i.e., u n and u ′ n are also the probabilities to reach e at time n starting respectively from x or x ′ . In X, one can form paths from e to itself of length 2n + 2 by jumping to x in time n, then to y, then back to x, and then from x to e. This happens with probability

u n • 1 |S| • 2 |S| • u n .
One can do the same with x ′ , giving an overall probability

a = 2 |S| 2 (u 2 n + u ′ n 2
). On the other hand, if y and y ′ are identified, then from this new point one can either jump back to x or to x ′ . The corresponding probability to come back to e at time 2n + 2 following such paths

is therefore b = 1 |S| 2 (u n + u ′ n ) 2 . As 2(v 2 + w 2 ) (v + w) 2
, we have a b, i.e., the probability of returning to e using corresponding paths is bigger in X than in the random walk where y and y ′ are identified. This explains our heuristic that more randomness in the choice of predecessors in the graph creates a mixing effect that decreases the spectral radius.

In [START_REF] Nagnibeda | An upper bound for the spectral radius of a random walk on surface groups[END_REF] and [START_REF]Random walks, spectral radii, and Ramanujan graphs[END_REF], Nagnibeda justifies this heuristic rigorously as follows. Consider a group Γ and a generating system S such that the Cayley graph of Γ with respect to S has no cycle of odd length, and finitely many cone types. By applying a spectral lemma of Gabber, she gets an upper bound ρ (given by a minimax formula, complicated to estimate in general) for the spectral radius ρ Γ of the simple random walk on (Γ, S). Since the tree of geodesics X also has finitely many cone types, she is able to compute exactly the spectral radius ρ X of the random walk in X. It turns out that this is exactly ρ. Hence, ρ Γ ρ X , the interest of this formula being that ρ X can be easily computed (it is algebraic as the tree X has finitely many cone types, see [START_REF] Nagnibeda | Random walks on trees with finitely many cone types[END_REF]). Note however that this bound does not come from a direct argument using the projection π X : X → Γ, but rather from two separate computations in X and in Γ.

We now turn to a similar geometric interpretation of the lower bound given in Theorem 1.4. We are looking for a natural random walk, related to the original random walk on Γ, whose spectral radius can be computed exactly and coincides with the lower bound given in (1.3). Following the above heuristic, this random walk should have more randomness than the original random walk regarding the choice of predecessors, to decrease the probability to return to the origin.

We use the setting and notations of Theorem 1.4. In particular, Γ is a group with a type system (T, t, M ), and (A 1 , . . . , A k ) and M are defined in the statement of this theorem. We define a random walk as follows: It is a walk on the space Y = Z × T (where T is the space of types), whose transition probabilities are given by:

(2.1) p((n, j)

→ (n + 1, i)) = M ij / |S| , p((n, j) → (n -1, i)) = e -v A i M ji A j |S| .
The spectral radius of this random walk is by definition ρ Y = lim P(X 2n = e)

= 2e -v/2 λ/ |S|.
Hence, the result of Theorem 1.4 reads ρ Γ ρ Y , and ρ Y is easy to compute. Let us first explain why this random walk is natural, and related to the random walk on Γ. Starting from a point x ∈ Γ, of type j and length n, the original random walk goes to any of its successors with probability 1/ |S|. In particular, it reaches points of type i and length n + 1 with probability M ij / |S|, just like the probability given in (2.1). On the other hand, it goes to any of its predecessors with probability 1/ |S|, but the types of these predecessors depend on x, not only on j. A random walk which is simpler to estimate may be constructed by randomizing the predecessors: from x, one chooses to go to any point of length n -1 and type i, provided that there is an edge from type i to type j, i.e., M ji > 0. The probability to go from x to such points should be given by the average number of predecessors of type i to a point of type j. Writing s n (i) = Card{x ∈ S n : t(x) = i}, this quantity is

(2.2) |x|=n,t(x)=j |y|=n-1,t(y)=i 1(x ∈ S(y)) |x|=n,t(x)=j 1 = s n-1 (i)M ji s n (j) .
As s n (i) ∼ c ′ A i e nv for some c ′ > 0 (see the proof of Theorem 1.4), the quantity in (2.2) converges when n → ∞ to e -v A i M ji /A j , giving the transition probability (2.1) in the limit. Note that, in this randomized random walk, all the points of the same length and the same type are equivalent. Hence, we may identify them, to get a smaller space and a simpler random walk. This is precisely our random walk on Y . Thus, the random walk on Y is obtained by starting from the random walk on Γ, randomizing the choice of predecessors, going in the asymptotic regime n → ∞, and identifying the points on the sphere that are equivalent. One can define a projection map π Y : Γ → Y by π Y (x) = (|x| , t(x)), under which the two random walks correspond in a loose sense (going towards infinity, the transition probabilities are the same, but coming back towards the identity they differ, just like for the projection π X in Nagnibeda's construction, with more randomness in Y than in Γ).

Proof of Theorem 2.1. We define two matrices P + and P -giving the transition probabilities of the walk on Y respectively to the right and to the left, i.e.,

P + ij = M ij / |S| , P - ij = e -v A i M ji A j |S| .
In other words, P + = M/ |S| and P -= e -v DM * D -1 / |S|, where D is the diagonal matrix with entries A i and M * is the transpose of M . Although this is clear from the geometric construction, let us first check algebraically that the transition probabilities in (2.1) indeed define probabilities, i.e., i P + ij + P - ij = 1 for all j. Let p j be the number of predecessors of a point of type j in Γ. By definition of A,

the matrix Mji = M ji /p j satisfies M A = e v A. Hence, i M ji A i = p j i Mji A i = p j e v A j . Therefore, i M ij + i e -v A i M ji A j = |S| -p j + e -v p j e v A j A j = |S| ,
proving that (2.1) defines transition probabilities.

While one can give a pedestrian proof of the equality ρ Y = 2e -v/2 λ/ |S|, it is more efficient to use available results of the literature. Define a function ϕ on R by ϕ(c) = ρ(e c P + +e -c P -) (where this quantity is the spectral radius of a bona fide finite dimensional matrix). It is proved in [Woe00, Proposition 8.20 and Theorem 8.23] that ϕ is convex, that it tends to infinity at ±∞, and that its minimum is precisely ρ Y . Since the spectral radius is invariant under transposition and conjugation, we have

|S| ϕ(c) = ρ(e c M + e -c e -v DM * D -1 ) = ρ(e c M * + e -c-v D -1 M D) = ρ(e c DM * D -1 + e -c-v M ) = |S| ϕ(-c -v).
Hence, the function c → ϕ(c) is symmetric around c = -v/2. As it is convex, it attains its minimum at c = -v/2. Therefore,

ρ Y = ϕ(-v/2) = e -v/2 |S| ρ(M + DM * D -1 ) = e -v/2 |S| ρ(D -1/2 M D 1/2 + D 1/2 M * D -1/2 ).
By Remark 1.5, the last term is equal to 2λ.

Application to surface groups

3.1. Cannon's types. Consider a countable group with the word distance coming from a finite generating set S. The cone of a point x is the set of points y for which there is a geodesic from e to y going through x. The cone type of x is the set {x -1 y}, for y in the cone of x. Note that knowing the cone type of a point determines the number of its successors, and the number of its successors having any given cone type. Cannon proved that, in any hyperbolic group, there are finitely many cone types. Therefore, such a group admits a type system in the sense of Definition 1.2. This is in particular the case of the surface groups Γ g . However, the number of cone types is too large, and it is more convenient for practical purposes to reduce them using symmetries. We obtain Cannon's canonical types for the surface groups, described in [START_REF] Cannon | The growth of the closed surface groups and the compact hyperbolic Coxeter groups[END_REF] or [START_REF] Floyd | Growth functions on Fuchsian groups and the Euler characteristic[END_REF] as follows. The hyperbolic plane can be tessellated by regular 4g-gons, with 4g of them around each vertex. The Cayley graph of Γ g (with its usual presentation (1.1)) is dual to this (self-dual) tessellation, and is therefore isomorphic to it. Define the type of a point x ∈ Γ g as the maximal length along the last 4g-gon of a geodesic starting from e and ending at x. Beware that one really has to take the maximum: for instance, in Figure 1, the thick geodesic from e to x shares only one edge with the last octagon, while the wiggly one shares two edges. Hence, the type of x is 2.

The type can also be described combinatorially as follows: write x = c 1 • • • c |x| as a product of minimal length in the generators a 1 , . . . , b g , look at the length n of its longest common suffix with a fundamental relator (i.e., a cyclic permutation of the basic relation

[a 1 , b 1 ] • • • [a g , b g ] in (1.1) or its inverse: c |x|-n+1 • • • c |x|
should be a subword of the basic relation or its inverse, up to cyclic permutation), and take the maximum of all such n over all ways to write x = c 1 • • • c |x| . It is obvious that the geometric and combinatorial descriptions are equivalent, we will mostly rely on the geometric one.

The type of a group element x can be at most 2g (otherwise, taking the same path but going the other way around the last 4g-gon, one would get a strictly shorter path, contradicting the fact that the initial path is geodesic), and it is 0 only for the identity. Points x of type i < 2g have only one predecessor, and 4g -1 successors. Among them, 2 are followers of x on the 4g-gon to its left and to its right, while the other ones correspond to newly created 4g-gons (whose closest point to e is x). It follows that those points have 4g -3 successors of type 1, one of type 2 and one of type i + 1. Points of type 2g are special, since they have two predecessors (one can reach them with a geodesic either from the left or from the right of a single 4g-gon). They have 2 successors of type 2, corresponding to the extremal outgoing edges of x (they extend the two 4g-gons adjacent to both incoming edges to x), and the 4g -4 remaining successors are on newly created 4g-gons, and are of type 1. See Figure 2 for an illustration in genus 2 (of course, additional octagons should be drawn around all outgoing edges, but since this is notoriously difficult to do in a Euclidean drawing, we have to rely on the reader's imagination).

Keeping only the types from 1 to 2g (since type 0 only happens for the identity, while Definition 1.2 allows to discard finitely many points), we obtain a type system for Γ g with T = {1, . . . , 2g}, where the matrix M has been described in the previous paragraph. For 2

2 1 1 1 1 2 2 1 111 1 2 1111 1 2 1 1 1 1 2 1111 1 2 1111 1 1 1 1 1 1 1 1111 2 1 1 1 1 1 2 1 1 1 1 1 2 2 1 1 1 1 2 2 1 1 1 1 1 2 1 1 1 1 1 1 2 11 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 2 2 1 1 1 1 2 2 1 1 1 1 1 2111 1 1 2111 1 1
M =     5 5 5 4 2 1 1 2 0 1 0 0 0 0 1 0     .
One can now apply the algorithm of Theorem 1.4 to this matrix to bound the spectral radius of the simple random walk from below. All points but points of type 4 have 1 predecessor, so the matrix M is

M =     5 5 5 4 2 1 1 2 0 1 0 0 0 0 1/2 0     .
The dominating eigenvalue of this matrix is e v = 6.979835 . . . (this is also the growth of the group), while the corresponding eigenvector is A = (0.715987 . . . , 0.246211 . . . , 0.035274 . . . , 0.002526 . . . ).

One gets that the matrix M ′′ of Remark 1.5 is This is already slightly better than Bartholdi's estimate ρ 0.662421, but much weaker than the estimate ρ 0.662772 that we claimed in Theorem 1.1 (to be compared with the "true" value ρ ∼ 0.662812).

M ′′ =     5
In the next sections, we will explain how to get better estimates by using different type systems, that distinguish between more points (but, of course, give rise to larger matrices M and therefore to more computer-intensive computations).

Remark 3.1. Using cone types instead of Cannon's canonical types does not give rise to better estimates for ρ (although the number of types is much larger). Indeed, if some type system t ′ is obtained from some type system t by quotienting by some symmetries of t, then the dominating eigenvector of M (t), being unique, is invariant by those symmetries and reduces to the dominating eigenvector of M (t ′ ). It follows that the dominating eigenvector of M ′′ (t) is also invariant by those symmetries, and that the dominating eigenvalue of M ′′ (t) is the same as that of M ′′ (t ′ ). Hence, the estimates on ρ given by Theorem 1.1 for t and t ′ are the same.

Suffix types.

There are many ways to define new type systems in surface groups, that separate more points. If a type system is finer than another one, then the estimate on the spectral radius coming from Theorem 1.4 is better, but the matrix involved in the computation is larger. To get manageable estimates, we should find the right balance.

In this paragraph, we describe a very simple extension of Cannon's canonical type systems in surface that we call suffix types. Given a point x ∈ Γ g , there can be several geodesics from e to x. Consider the longest ending that is common to all these geodesics, say x n-k+1 , . . . , x n (with x n = x), and define the suffix type of x to be

t suff (x) = (t(x n ), t(x n-1 ), . . . , t(x n-k+1 )),
where t is the canonical type of Cannon.

For any x, t suff (x) is easy to compute inductively:

• If t(x) = 0, i.e., x = e, then t suff (x) = (0).

• If x is of type 2g, it has two predecessors, so the common ending to all geodesics ending at x is simply x, and t suff (x) = (2g). • If t(x) ∈ {1, . . . , 2g -1}, then x has a unique predecessor z. The common ending to all geodesics ending at x is the common ending to all geodesics ending at z, followed with x. Hence, t suff (x) = (t(x), t suff (z)). It also follows from this description that, if one knows t suff (x), it is easy to determine t suff (y) for any successor y of x: if t(y) = 2g, then t suff (y) = (2g), otherwise x is the only predecessor of y and t suff (y) = (t(y), t suff (x)).

We have shown that t suff shares most properties of type systems as described in Definition 1.2, except that it does not take its values in a finite set. To ensure this additional property, one should truncate the suffix type. For instance, one can fix some maximal length k, and define the k-truncated suffix type t (k) suff (x) by keeping only the first k elements of t suff (x) if its length is > k.

The following proposition is obvious from the previous discussion.

Proposition 3.2. For any k 1, the k-truncated suffix type system t

(k)
suff is a (Perron-Frobenius) type system in the sense of Definition 1.2.

The matrix size increases with k, but the estimates on the spectral radius following from Theorem 1.4 get better. For instance, in Γ 2 , for k = 5, the matrix size is 148, and we get ρ 0.662694.

A drawback of this truncation process is that it truncates uniformly, independently of the likeliness of the type, while it should be more efficient to extend mostly those types that are more likely to happen. This intuition leads to another truncation process: fix a system of weights w = (w 0 , . . . , w 2g ) ∈ [0, +∞) 2g+1 , a threshold k, and truncate a suffix type (t 0 , t 1 , . . . ) at the smallest n such that t 0 + . . . + t n > k. This gives another type system denoted by t

(k,w) suff (t (k)
suff corresponds to the weights w = (1, . . . , 1) and the threshold k -1). Define for instance a weight system w by w0 = 1 and wi = i for i 1: the corresponding type system t (k, w) suff truncates more quickly the suffix types involving a lot of large types, that happen less often in the group. Hence, it should give a smaller matrix than the naive truncation only according to length, while retaining a comparatively good estimate for the spectral radius.

This intuition is correct: for instance, in Γ 2 , using t (k, w)

suff with k = 6, one gets a matrix with size 109 and an estimate ρ 0.662697: the matrix is smaller than for the naive truncation t

(5) suff , while the estimate on the spectral radius is better.

We can now push the computations, to a larger matrix size: using in Γ 2 the weight w and the truncation threshold k = 25, one obtains a type system where the matrix is of size 2, 774, 629, and the following estimate on the spectral radius.

Proposition 3.3. In Γ 2 , one has ρ 0.662757. This is definitely better than (3.1), but not yet as good as Theorem 1.1.

A few comments on the practical implementation. There are three main steps in the algorithm of Theorem 1.4:

(1) Compute the matrix M corresponding to the type system.

(2) Find the eigenvector A, to define the matrix M ′ .

(3) Find the maximal expansion rate of M ′ . Computing the matrix of the type system is a matter of simple combinatorics: we explained above all the transitions from one suffix type to the next ones. The resulting matrix M is very sparse: each type has at most 2g successors. However, it is extremely large, so that finding the eigenvector A and then the maximal expansion rate of M ′ might seem computationally expensive. This is not the case, as we explain now.

Let A (0) be the eigenvector for the original Cannon type, so that Card{x ∈ S n : t(x) = i} ∼ A (0) i e nv . Let also M (0) be the matrix for the original Cannon type. Given a new type ī = (i 0 , . . . , i m ), the entry Aī of the eigenvector A for the new type t

(w,k) suff is such that Card{x ∈ S n : t (w,k)
suff (x) = ī} ∼ Aīe nv . Such a point x can be obtained uniquely by starting from a point y ∈ S n-m with type i m , and then taking successors respectively of type i m-1 , . . . , i 0 . Hence,

(3.2) Card{x ∈ S n : t (w,k) suff (x) = (i 0 , . . . , i m )} = M (0) i 0 i 1 • • • M (0) i m-1 im Card{y ∈ S n-m : t(y) = i m }.
It follows that the new eigenvector is given by

Aī = M (0) i 0 i 1 • • • M (0) i m-1 im A (0)
im e -mv . This shows that A is very easy to compute. By Remark 1.5, to determine the maximal expansion rate λ of M ′ , it suffices the find the maximal eigenvalue of M ′′ = (M ′ +M ′ * )/2. This matrix is real, symmetric, with nonnegative coefficients, and it is Perron-Frobenius (i.e., it has one single maximal eigenvalue). It follows that, for any vector v with positive coefficients, λ = lim M ′′ n v / M ′′ n-1 v (and moreover this sequence is non-decreasing, see for instance [Woe00, Corollary 10.2]). Hence, one can readily estimate λ from below, by starting from a fixed vector v and iterating M ′′ . Again, there is no issue of instability or complexity.

Essential types.

To improve the suffix types, to separate even more points, one can for instance replace the canonical Cannon types with the true cone types. However, the matrix size increases so quickly that this is not usable in practice. Moreover, this does not solve the main problem of suffix types: they do not separate at all points with Cannon type 2g, although such points are clearly not always equivalent. In this paragraph, we introduce a new type system that can separate such points, that we call the essential type.

The basic idea (that will not work directly) is to memorize not only the common ending of all geodesics ending at a point x, but all the parts that are common to such geodesics: i.e., the sequence F ess (x) = (x 0 = e, x 1 , . . . , x n = x) (with n = |x|) where x i = * if there are two geodesics from e to x that differ at position i, and x i is the point that is common to all those geodesics at position i otherwise. We then associate to x the sequence t ess (x) = (t(x n ), t(x n-1 ), . . . , t(x 0 )) where t(x i ) is the Cannon type of x i if x i = * , and t( * ) = * . The problem with this notion is that t ess (x) does not determine t ess (y) for y a successor of x: in Figure 3, the points x and x ′ have the same essential type (3, 2, 1, 3, 2, 1, 0), while their Consider a point x, and one of its successors y. If the type of y is not 2g, then x is the unique predecessor of y, and t ess (y) = (t ′ (y), t ess (x)). Assume now that t ′ (y) = 2g (so that t ′ (x) = 2g -1). Let z 2g-1 = x, and define inductively z i as the unique predecessor of z i+1 for i 1, so that F (x) = (e, . . . , z 1 , z 2 , . . . , z 2g-1 = x). Those points are on a common 4g-gon R, and t(z i ) = i for i 2, while t(z 1 ) can be anything. In the same way, let z2g-1 , . . . , z1 be the successive preimages of y going around R in the other direction. They also satisfy t(z i ) = i for i 2. If t(z 1 ) = 2g, then z 1 has a unique preimage z 0 , which also belongs to R. Moreover, z 0 is the unique closest point to e on R. The path P = (z 0 , z 1 , . . . , z 2g-1 , y) is a geodesic path going around R in one direction, and P = (z 0 , z1 , . . . , z2g-1 , y) is also geodesic and goes around R in the other direction. If, along P , all points different from z 0 , y have type < 2g (so that they have a unique preimage), then any geodesic from e to y has to follow either P or P , so that t ess (y) = (2g, * , . . . , * , t ess (z 0 )), with 2g -1 ambiguous points. See the first part of Figure 5 for an illustration.

The only way to have a point of type 2g along P is if t(z 0 ) = 2g -1 and t(z 1 ) = 2g, since t(z i ) = i for i 2 (see the second part of Figure 5). By definition of the modified type, this happens exactly when t ′ (z 1 ) = 1 ′ and t ′ (z 2 ) = 2 ′ . In this case, a geodesic from e to y can either go through z 0 and then follow P , or go through z1 and then follow (z 2 , . . . , z2g-1 , y). In the first case, if one truncates the geodesic when it reaches z 0 and then adds the edge [z 0 z1 ], one gets a geodesic from e to z1 . It follows that the essential type of y is (2g, * , . . . , * , t ess (z 1 )), where t ess (z 1 ) is the essential type of z1 minus its first entry (i.e., the type 2g of z1 ), and where there are 2g -1 stars. Since z1 is a successor of z 0 , the induction hypothesis ensures that its essential type can be determined from that of z 0 , which is given by that of x. When t(z 1 ) = 2g, we have shown that in all situations t ess (x) determines t ess (y) in an algorithmic way.

Assume now that t(z 1 ) = 2g (see the third part of Figure 5). This case is very similar to the previous one. To reach y, one has to reach z 1 or its preimage on R, and then reach y by going around R in one direction or the other. It follows that t ess (y) = (2g, * , . . . , * , t ess (z 1 )) as above. Since t ess (z 1 ) is obtained by removing the last 2g -2 entries of t ess (x), it follows again that t ess (x) determines t ess (y).

For k > 0, let t (k) ess (x) be the truncated essential type, obtained by keeping the first k entries of the essential type of x. The above proof also shows that t (k) ess (x) determines t (k+1) ess (y) (and therefore t (k) ess (y)) for any successor y of x. In the same way, if one considers a truncation according to a weight w = (w 0 , w 1 , . . . , w 2g , w 1 ′ , w 2 ′ , w * ) and a threshold k, then t (k,w) ess (x) determines t (k,w) ess (y) for any successor y of x, if the weight w * is maximal among all weights. This last requirement is necessary for the following reason: the essential type of y can be obtained from that of x by replacing some entries with stars; if this could decrease the weight of the resulting sequence, one might need to look further to determine t (k,w) ess (y), and t (k,w) ess (x) might not be sufficient. Under these conditions, it follows that t (k) ess and t (k,w) ess are (Perron-Frobenius) type systems, in the sense of Definition 1.2. Hence, we can use Theorem 1.4 to estimate the spectral radius of the corresponding random walk. Again, it turns out that it is more efficient to truncate using weights than length.

In genus 2, taking the weights w = (1, 2, 3, 4, 1, 2, 4) and the threshold k = 25, we obtain a matrix of size 8, 999, 902. The corresponding bound on the spectral radius is ρ 0.662772, proving Theorem 1.1. Those bounds were obtained on a personal computer with a memory of 12GB (memory is indeed the main limiting factor, since one should store all truncated essential types to create the matrix M ). With more memory, one would get better estimates, but it is unlikely that those estimates converge to the true spectral radius when k tends to infinity: to recover it, it is probably necessary to distinguish even more points, for instance by using Cannon's cone types instead of the canonical types (but this would become totally impractical).

In higher genus, here are the bounds we obtain.

Theorem 3.5. In genus 3, using t (k,w) ess with w = (1, 2, 3, 4, 5, 6, 1, 2, 6) and k = 25, we get a matrix of size 7, 307, 293 and the estimate ρ 0.5527735593.

In genus 4, using t (k,w)

suff with w = (1, 2, 3, 4, 5, 6, 7, 8) and k = 24, we get a matrix of size 4, 120, 495 and the estimate ρ 0.48412292068.

When the genus increases, the groups look more and more like free groups. This means that the spectral radius is very close to that of the random walk on a tree with the corresponding number of generators (i.e., √ 4g -1/(2g) in general, specializing to 0.55277079 in genus 3 and 0.48412291827 in genus 4), and to get a significant improvement one needs to take very large matrices. The paths counting arguments of Bartholdi [Bar04], on the other hand, are more and more precise when the groups looks more and more like a free group: in genus 3, he gets ρ 0.5527735401, which is just slightly worse than our estimate, while requiring considerably less computer power. In genus 4, he gets ρ 0.48412292074, which is already better than our estimate, and the situation is certainly the same in higher genus.

In genus 3, the upper bound of Nagnibeda [START_REF] Nagnibeda | An upper bound for the spectral radius of a random walk on surface groups[END_REF] is ρ 0.552792, while our lower bound (or Bartholdi's) is much closer to the naive lower bound coming from the free group. It is unclear which one is closer to the real value of the spectral radius.

For the practical implementation, as in the end of Paragraph 3.2, it is important to know the asymptotics of the number of points on S n having a given truncated essential type. We illustrate how to compute such asymptotics in three significant examples, that can be combined to handle the general case.

• Assume first that the type (i 0 , . . . , i m ) does not contain any ambiguous letter, i.e., i ℓ = * for all ℓ. In this case, the formula (3.2) still holds. • Assume now that the type is of the form (i, * , . . . , * , j) for some types i, j = * , and some number N of stars. Let x be a point with the above truncated essential type, on a sphere S n , and let y be the point of modified type j, on the sphere S n-N -1 , such that any geodesic from e to x goes through y. Since the type 2g is the only one to have several predecessors, necessarily i = 2g. On the other hand, j can be any type in {1, 1 ′ , 2, 2 ′ , 3, . . . , 2g}.

The discussion in the proof of Proposition 3.4 (see in particular the last 2 cases of Figure 5) implies that N = (2g -1)m, for some integer m: a geodesic from e to x goes through y, and then it follows m 4g-gons.

Let us first study the case m = 1. Consider a point y of type j, and a 4g-gon R based at y (i.e., y is the closest point to e on this 4g-gon). There are 4g -2 such R if j = 2g and 4g -3 if j = 2g (since a point of type 2g has two incoming edges). On R, consider the point x that is the farthest from e: it has type 2g, and one can reach it from y by going around R in one direction or the other. It follows that Card{x ∈ S n : t (w,k) suff (x) = (2g, * , . . . , * , j) with N = 2g -1 stars} = a j Card{y ∈ S n-N -1 : t ′ (y) = j}, where a j = 4g -3 if j ∈ {2g -1, 2g}, and a j = 4g -2 otherwise. The case of a point y of type j = 2g -1 is special since, on the 4g-gon R containing the successors of y of types 1 ′ and 2 ′ , one of the geodesic paths from y to the opposite point x goes through a vertex of type 2g, giving rise to further ambiguities. Hence, this 4g-gon should be discarded from the above counting, leaving only 2g -3 suitable 4g-gons.

In the case of a general m 1, the number of points x corresponding to a given point y of type j may be obtained first by choosing a suitable 4g-gon R 1 based at y (giving a j choices). Further ambiguities can only be obtained by choosing one of the two predecessors (of type 2g -1) of the point that is opposite to y on R 1 , and then following the 4g-gon R 2 based at this point and containing its successors of type 1 ′ and 2 ′ . This gives 2 choices for R 2 , then 2 more choices for the next 4g-gon R 3 , and so on. In the end, we obtain Card{x ∈ S n : t (w,k) suff (x) = (2g, * , . . . , * , j) with N = (2g -1)m stars} = a j 2 m-1 Card{y ∈ S n-N -1 : t ′ (y) = j}.

• Finally, assume that the type is (i, * , . . . , * ) with some number N of stars (the situation is very similar to the previous one). Necessarily, as above, i = 2g. Write N = (2g -1)m + k for some k ∈ {1, . . . , 2g -1}.

For m = 0, a point of type 2g has two predecessors, so there are always ambiguities regarding his first 2g -1 ancestors. Hence, the set of points we are considering is simply the set of points of type 2g on the sphere S n , and there is nothing to do.

For m = 1, there can be further ambiguities only if x has an ancestor x ′ of generation 2g -1 that has type 2g, and x is at the tip of the 4g-gon R based at one of the two predecessors of x ′ (of type 2g -1), and containing x ′ . There are two choices for R.

Proceeding inductively in the case of a general m, we get Card{x ∈ S n : t A general truncated essential type is the concatenation of successive types of the form just described in the examples. We can thus count the number of points with a given type just by combining the above formulas.

Figure 1 .

 1 Figure 1. Two examples of geodesics from e to x

Figure 2 .

 2 Figure 2. Types of the points in (part of) the Cayley graph of Γ 2

  3.171316 . . . 0.554905 . . . 0.118814 . . . 3.171316 . . . 1 1.510223 . . . 0.101307 . . . 0.554905 . . . 1.510223 . . . 0 1.868132 . . . 0.118814 . . . 0.101307 . . . 1.868132 . . .

Figure 3 .

 3 Figure 3. The points x and x ′ have the same essential type, contrary to y and y ′ .

Figure 5 .

 5 Figure 5. Determining the essential type of y from that of x

  suff (x) = (2g, * , . . . , * ) with N = (2g -1)m + k stars} = 2 m Card{y ∈ S n-(2g-1)m : t(y) = 2g}.

  1/2n (this is not a spectral definition). Note that this random walk admits a quasi-transitive Z-action (i.e., Y is endowed with a free action of Z, with finite quotient, and the transition probabilities are invariant under Z). Such random walks are well studied, see for instance [Woe00, Section 8.B].

Theorem 2.1. With the notations of Theorem 1.4, the random walk on Y has spectral radius ρ Y

successors y and y ′ have respective essential types (4, * , * , * , 3, 2, 1, 0) and (4, * , * , * , * , * , * , 0) (this follows from the fact that the thick paths and wiggly paths are geodesics). This shows that, as we have defined it, t ess can not be used to define a type system. This problem can be solved if we do not use directly the Cannon types in the definition of t ess , but a slightly refined notion, the Cannon modified type, taking values in {1, . . . , 2g, 1 ′ , 2 ′ }. The modified type of a point is the same as its Cannon type, except for some points of Cannon types 1 and 2, that have modified types 1 ′ and 2 ′ respectively: considering any point y of type 2g -1, it has a unique successor z of type 2g, and a unique successor x of type 1 that is on the same 4g-gon as z. We say that x is of modified type 1 ′ . Moreover, x has a unique successor of type 2 that is also on the same 4g-gon as z, we say that it is of modified type 2 ′ . See Figure 4 for an example in genus 2. By definition, the modified Cannon type t ′ is also a type system. The transition matrix is the same as for the usual Cannon type, except that

• A point of type 2g -1 has one successor of type 1 ′ , one successor of type 2g, one successor of type 2, and 4g -4 successors of type 1. • A point of type 1 ′ has one successor of type 2, one successor of type 2 ′ , and 4g -3 successors of type 1. • A point of type 2 ′ has one successor of type 2, one successor of type 3, and 4g -3 successors of type 1. We define t ess (x) = (t ′ (x n ), . . . , t ′ (x 0 )) where (x 0 , . . . , x n ) = F ess (x) and t ′ ( * ) = * .

Proposition 3.4. The essential type t ess (x) of a point x determines the essential type of its successors.

Proof. We argue by induction on |x| = d(x, e).