M Saadati

P Forquin

K Weddfelt

P L Larsson

F Hild

Granite rock fragmentation at percussive drilling -experimental and numerical investigation

Keywords: Granite, percussive drilling, KST-DFH model, fragmentation

The aim of this study is to numerically model the fracture system at percussive drilling. Due to the complex behavior of rock materials, a continuum approach is employed relying upon a plasticity model with yield surface locus as a quadratic function of the mean pressure in the principal stress space coupled with an anisotropic damage model. In particular, Bohus granite rock is investigated and the material parameters are defined based on previous experiments. This includes different tests such as direct tension and compression, three point bending and quasi-oedometric tests to investigate the material behavior at both tension and confined compression stress states. The equation of motion is discretized using a FE approach and the explicit time integration method is employed. EOI (Edge-On Impact) tests are performed and the results are used to validate the numerical model. The percussive drilling problem is then modeled in 3D and the bit-rock interaction is considered using contact mechanics. The fracture mechanism in the rock and the bit penetration-resisting force response are realistically captured by the numerical model.

Introduction

Rock drilling has been extensively used in the mining industry for many decades. A sound understanding of bit-rock interaction and rock fragmentation mechanisms is essential to optimize the drilling process. The percussive drilling method is commonly used in the tunneling and mining business. The main idea is that a piston hits the drill rod at a velocity of about 10 m/s. This creates a compressive stress wave with an amplitude of about 200 MPa, which propagates along the drill rod. The stress wave is then transferred into the rock through the tool buttons. Each tool includes around ten buttons made of hard steel that facilitate the indentation process. Unlike the situation of quasi-static indentation, the stress waves and rapid indentation make percussive drilling a transient dynamic problem with high local strain rates in the rock [START_REF] Saksala | Numerical Modelling of Rock Fracture in Percussive Drilling[END_REF].

Basic defects in rocks are voids, pores and microcracks as well as other related features [START_REF] Fang | Development of a local degradation approach to the modelling of brittle fracture in heterogeneous rocks[END_REF]. Such microstructures produce heterogeneity in the strength and stiffness of the material. It is well known that rock fractures via initiation, growth and coalescence of microcracks, together with sliding between individual grains and the microcrack surfaces. Associated with these microscopic mechanisms, rock specimens exhibit non-linear stress-strain responses [START_REF] Fang | Development of a local degradation approach to the modelling of brittle fracture in heterogeneous rocks[END_REF]. Granite, which is the material studied in this work, has many pre-existing cracks, (e.g. [START_REF] Peng | Crack growth and faulting in cylindrical specimens of Chelmsford granite[END_REF] and [START_REF] Bäckström | Numerical modelling of uniaxial compressive failure of granite with and without saline porewater[END_REF]), but the porosity is very low (about 0.2%). Most rocks show a transition from brittle to ductile behavior by increasing the confined pressure [START_REF] Fang | Development of a local degradation approach to the modelling of brittle fracture in heterogeneous rocks[END_REF]. However, silicate rocks with low porosity are brittle at room temperature over the whole range of normal laboratory confining pressures up to 0.5-1.0 GPa. Some workers have reported that granite exhibits brittle fracture behavior even at confining pressures up to 3-4 GPa [START_REF] Shimada | Fracture strength of dry silicate rocks at high confining pressures and activity of acoustic emission[END_REF].

Many studies have been performed during the past years to numerically simulate rock drilling and the fragmentation process in brittle materials. Liu [START_REF] Liu | Numerical simulation of the rock fragmentation process induced by indenters[END_REF] developed a rock and tool interaction code (R-T 2D ) and studied the fragmentation process in a quasi-static situation. Wang et al. [START_REF] Wang | Numerical simulation of the rock fragmentation process induced by two drill bits subjected to static and dynamic (impact) loading[END_REF] used an in-house numerical tool to simulate the rock fragmentation process induced by indentation. Both Liu and Wang et al. restrict their analyses to 2D plain strain conditions and do not account for inelastic strains. Furthermore, Saksala [START_REF] Saksala | Damage-viscoplastic consistency model with a parabolic cap for rocks with brittle and ductile behavior under low-velocity impact loading[END_REF][START_REF] Saksala | Numerical modelling of bit-rock fracture mechanisms in percussive drilling with a continuum approach[END_REF] studied the impact indentation of rocks using an isotropic damage concept for tensile loading and a viscoplasticity consistency model for compression loading. This work is performed under 2D plane strain conditions. More recently, the model was extended to deal with 3D simulations [START_REF] Saksala | 3D numerical modelling of bit-rock fracture mechanisms in percussive drilling with a multiple-button bit[END_REF]. Chiang et al. [START_REF] Chiang | A 3D FEM methodology for simulating the impact in rock-drilling hammers[END_REF] modeled the impact of tool to the rock and rock fragmentation in drilling process using a 3D FE approach. A linear Mohr envelop together with a tension cut off plane is employed as a criterion for maximum strength of rock. The material behavior is considered linear elastic before reaching the final failure. Additionally, Thuro et al. [START_REF] Thuro | Fracture propagation in anisotropic rock during drilling and cutting[END_REF] used Particle Flow Code (PFC 2D ) to investigate the crack pattern in drilling and its correlation with existing foliations. PFC 2D code is based on discontinuum mechanics approach and is built for 2D simulations.

Forquin and Hild [START_REF] Forquin | A Probabilistic Damage Model of the Dynamic Fragmentation Process in Brittle Materials[END_REF] studied dynamic fragmentation in brittle materials in general due to impact loading by using a probabilistic approach to describe the material behavior. The constitutive equation consists of the plasticity model introduced by Krieg [14], Swenson and Taylor [START_REF] Swenson | A finite element model for the analysis of tailored pulse stimulation of boreholes[END_REF] for compressive loadings and coupled with the anisotropic damage model developed by Denoual and Hild [START_REF] Denoual | A damage model for the dynamic fragmentation of brittle solids[END_REF], Forquin and Hild [START_REF] Forquin | A Probabilistic Damage Model of the Dynamic Fragmentation Process in Brittle Materials[END_REF], in tension (here and in the sequel referred to as the KST-DFH model). It is shown how a brittle and random behavior under quasi-static tensile loading becomes deterministic and stress-rate dependent when increasing the loading rate. This type of model was able to describe the fragmentation of two grades of limestone subjected to EOI tests [START_REF] Grange | On the dynamic fragmentation of two limestones using edge-on impact tests[END_REF] and the enhancement of strength and failure pattern of a microconcrete [START_REF] Forquin | Dynamic fragmentation process in concrete under impact and spalling tests[END_REF] and a standard concrete [START_REF] Erzar | An experimental method to determine the tensile strength of concrete at high rates of strain[END_REF] in spalling tests and EOI experiments.

In this investigation, the KST-DFH model is selected as the constitutive model based on the findings in a previous study by Saadati et al [START_REF] Saadati | On the mechanical behavior of granite material with particular emphasis on the influence from pre-existing cracks and defects[END_REF]. This model is a good alternative as it deals with both dynamic fragmentation due to tensile stress waves and also plasticity-like deformation in compression. This is very similar to the situation at percussive drilling as the impact of the piston induces stress waves into the rock and initiate tensile cracks, while high compressive stresses prevail beneath the indenter and lead to crushing of the rock. The KST-DFH model parameters for Bohus granite are defined based on previously reported experimental results [START_REF] Saadati | On the mechanical behavior of granite material with particular emphasis on the influence from pre-existing cracks and defects[END_REF]. Edge-On Impact (EOI) tests, i.e. impact of an aluminum projectile onto a rock slab [START_REF] Forquin | Dynamic Fragmentation of an Ultr_ahigh-Strength Concrete during Edge-On Impact Tests[END_REF], are performed. The tests are numerically modeled and these results are compared to the experimental data to validate the constitutive model. After that, the numerical tool is used to simulate the percussive drilling problem and the results are compared with real drilling data.

Constitutive specification

KST model

The KST model has been developed to simulate the compressive behavior of geomaterials accounting for the effect of hydrostatic and deviatoric parts of the stress tensor [START_REF] Krieg | A simple constitutive description for soils and crushable foams[END_REF][START_REF] Swenson | A finite element model for the analysis of tailored pulse stimulation of boreholes[END_REF]. In the deviatoric part, the locus of the yield surface is a quadratic function of the mean pressure in the principal stress space.

where σ eq is the equivalent (von Mises) stress, P the hydrostatic stress, a 0 , a 1 and a 2 are material dependent coefficients.

Furthermore, the model includes a piece-wise linear equation of state linking the volumetric strain, ε v , to the hydrostatic stress. At the first stage of hydrostatic loading, the material behaves elastically. By increasing the pressure, collapse of pores occurs in the case of porous rocks, which is modeled by an irreversible volumetric strain. During the porosity breakage, the bulk modulus, K, decreases noticeably. When all pores are closed, the material exhibits a higher bulk modulus which corresponds to the compacted material [START_REF] Vajdova | Compaction, dilatancy, and failure in porous carbonate rocks[END_REF]. However, granite exhibits constant bulk modulus in the whole hydrostatic stress range as it includes a very small amount of porosity [START_REF] Saadati | On the mechanical behavior of granite material with particular emphasis on the influence from pre-existing cracks and defects[END_REF].

The DFH fragmentation model

The DFH fragmentation model is explained in detail in Refs. [START_REF] Forquin | A Probabilistic Damage Model of the Dynamic Fragmentation Process in Brittle Materials[END_REF] and [START_REF] Denoual | A damage model for the dynamic fragmentation of brittle solids[END_REF]. In the sequel a brief summary of the model including both single and multiple fragmentation regimes is presented.

Single fragmentation

Under low loading rate conditions, the fracture process is generally the consequence of the initiation and growth of a single crack. When the stress increases, the weakest defect is first activated. An unstable crack is initiated and propagates very quickly leading to fracture of the whole structure.

Defects with different sizes and orientations are randomly distributed within the material and consequently the failure stress is random. To model this tensile behavior, a probabilistic approach may be employed. Using a Poisson point-process framework, the weakest link theory and Weibull model, the failure probability P F is given by [START_REF] Weibull | A Statistical Theory of the Strength of Materials[END_REF][START_REF] Weibull | A statistical distribution function of wide applicability[END_REF] 1 exp[ ( )]

F eff t F PZ     (2)
where Z eff is the effective volume [START_REF] Davies | The statistical approach to engineering design in ceramics[END_REF], and λ t is the initiation density defined by 0 0 ()

m F tF S         ( 3
)
where m is the Weibull modulus,

0 0 /  m S
is the Weibull scale parameter, and σ F the maximum principal stress in the whole domain. The effective volume, Z eff , is expressed as

eff m Z ZH  ( 4
)
where Z is the size of the whole volume, and H m the stress heterogeneity factor [START_REF] Hild | Hétérogénéité des contraintes et rupture des matériaux fragiles[END_REF] written as

1 1 0 m m F F H dZ when Z            (5)
where σ 1 is the local maximum principal stress, and  Macauley's brackets. The stress heterogeneity factor characterizes the effect of the load pattern on the cumulative failure probability. Last, the average failure stress σ w and the corresponding standard deviation σ sd are written as

                    ( 7
)
where Г is the Euler function of the second kind

  0 1 exp( ) x x u u du       (8)
To characterize specific materials, 3-point bend tests are performed and the distribution of the failure stresses is obtained. One classical way to obtain the Weibull modulus m is then to look at the slope of linear interpolation in the diagram of ln[-ln(1-P F )] versus ln(σ F ) or the modified Weibull plot [START_REF] Saadati | On the mechanical behavior of granite material with particular emphasis on the influence from pre-existing cracks and defects[END_REF]. The scale parameter 0 0 /  m S can then be extracted from Eqs. ( 6) and ( 8), or the intercept in the Weibull plot.

Multiple fragmentation

Under high strain-rate conditions, several cracks are initiated and propagate from the initial defects leading to multiple fragmentation. The initial defects are assumed to be randomly distributed and activated for a random level of stress. When a crack is initiated, it propagates at a very high velocity (a portion of the stress wave velocity) and relaxes the stresses in its vicinity. This prevents activation of new defects in an obscured zone centered on this crack. At the same time the stress is increasing in the non-obscured zone and new critical defects are activated leading to new crack openings [START_REF] Forquin | A Probabilistic Damage Model of the Dynamic Fragmentation Process in Brittle Materials[END_REF][START_REF] Denoual | A damage model for the dynamic fragmentation of brittle solids[END_REF].

Therefore, dynamic fragmentation corresponds to a competition between, on the one hand, new critical defects that progressively initiate cracks with the increase of the stress level and, on the other hand, obscuration of areas of potential critical defects by cracks created before. The fragmentation process ends when the whole domain is obscured by the propagating cracks.

The interaction law between cracks already initiated and the critical defects of the material is given by the concept of probability of non-obscuration [START_REF] Denoual | A damage model for the dynamic fragmentation of brittle solids[END_REF]. If the initiation density is a continuous function, the probability of non-obscuration of point M at time T in a domain Ω is described by [START_REF] Forquin | A Probabilistic Damage Model of the Dynamic Fragmentation Process in Brittle Materials[END_REF] (

( , ) ( , ) exp

t no x t horizon of M T xt P M T dVdt t               (9)
where the horizon is defined by

  ( , ) , [ ( ) ( ( )) ] n o horizon of M T x t Z T t S kC T t        . ( 10
)
In Eq. ( 10), Z o is the obscured zone, k a constant parameter (k = 0.38 when the crack length becomes significantly larger than the initial size), C the 1D wave speed, T the current time and t the crack initiation time, S a shape parameter (equal to 4π/3 when the obscuration volume is similar to a sphere in 3D) and n the medium dimension (n = 3 in 3D).

The single fragmentation process occurs at quasi-static conditions and the probability of obscuration P o = 1P no ≡ P F corresponds to the failure probability, Eq.( 2), expressed by Weibull's model. Therefore the initiation density for dynamic fragmentation (see Eq. ( 9)) is identical to that used in the analysis of quasi-static cases as described in Eq.

(3).

In the case of multiple fragmentation, the interaction between the horizon and the boundary of the domain Ω is small and if a uniform stress field is assumed, the obscuration probability in multiple fragmentation is written as [START_REF] Denoual | A damage model for the dynamic fragmentation of brittle solids[END_REF] ( ) 1

( ) 1 exp [ ( )] ( ) 0 o no o T d t P T P T t Z T t dt dt                  (11)
The non-obscuration probability provides an indication for the fraction of initiated cracks that correspond to the critical defects activated in the non-obscured volumes. The increment of the crack density  cracks is associated with the obscuration probability and the increment of initiation density

cracks no t P dt dt      (12)
Eq. ( 12) expresses the fact that cracks will initiate only if a defect exists in a non-obscured zone of the volume. The probability of obscuration is defined for each principal direction i and the evolution of P i is expressed in a differential form in order to be employed in a FE code using Eq. ( 11)

  2 3 0 2 1 3! [ ( )] 0 0 1 i i t i i i dP d d S kC t when and P dt dt dt            ( 13
)
where σ i is the local principal stress component.

The KST-DFH model is also combined with a cohesive model in order to describe the cohesive strength in the obscured zone and the softening behavior of geomaterials in dynamic tension [START_REF] Sallier | Influence of the Confined Behaviour and the Tensile Strength of Concrete Slabs Under Projectile-Impact[END_REF]. In the cohesive model, an extra term is added to the macroscopic stress  i as

(1 ) ( ) ( ) (1 )
D i i i i coh i i P P D            (14)
where is the residual strength in the obscuration zone In the principal stress frame, the compliance tensor is defined by

D ED D                                                 (16)
where ε 1 , ε 2 , ε 3 are the principal strains, E Young's modulus and ν Poisson's ratio of the undamaged material. At the inception of damage growth, the principal damage frame coincides with the principal stress tensor frame and the eigen directions may change at each time step until the first damage variable D 1 reaches a threshold value of 0.2. Then the direction of D 1 is locked and the other directions D 2 , and D 3 follow the eigen directions with the constraint to be perpendicular to D 1 . When the second damage variable reaches the threshold value, the whole directions are locked.

The material model parameters

The KST-DFH model parameters for Bohus granite, see Table legends Table 1, are obtained based on previous experimental work [START_REF] Saadati | On the mechanical behavior of granite material with particular emphasis on the influence from pre-existing cracks and defects[END_REF]. In 1, and in particular the experimental data at high levels of hydrostatic pressure for which there is a considerable amount of inelastic strains (as the specimen mainly deforms elastically at the initial stage of loading). Presently, the equation of state linking the volumetric strain to the hydrostatic stress is taken to be piece-wise linear and determined by the points (ε v (i) , P (i) ) specified in Table legends Table 1.

It deserves to mention that in the model, rate dependency is negligible in case of single fragmentation and the strength of the material is then considered to be probabilistic. At higher stress rates (i.e. when multiple fragmentation occurs) the mechanical behavior is deterministic and the strength increases with increasing loading rates. At low stress-rates, Weibull law plays also a regularization role. The smaller the FE elements the higher the mean failure stress based on Weibull size effect. Furthermore, the rate dependency at high stress rates works as a regularization in the model and decreases mesh dependency. More details concerning this behavior are found in Ref. [START_REF] Forquin | A Probabilistic Damage Model of the Dynamic Fragmentation Process in Brittle Materials[END_REF].

The parameters of the cohesive law are here determined based on preliminary results from spall tests. All the material parameters used hereafter are summarized in

Edge-on impact experiments and computations

Experiments

In order to validate the numerical model and also to investigate the fracture pattern after impact, Edge-on Impact (EOI) tests [START_REF] Forquin | Dynamic Fragmentation of an Ultr_ahigh-Strength Concrete during Edge-On Impact Tests[END_REF] with a special sarcophagus configuration [START_REF] Denoual | A damage model for the dynamic fragmentation of brittle solids[END_REF] are performed (see Fig. 2). In the experimental set-up, two cylindrical steel confinements of size 52 mm in length and 60 mm in diameter are used close to the impact point on both faces of the rock specimen. This helps to increase the level of confining pressure and accordingly the strength of the rock material in order to reduce compressive damage beneath the projectile. A more complete description of the EOI test can be found in Ref. [START_REF] Forquin | Dynamic Fragmentation of an Ultr_ahigh-Strength Concrete during Edge-On Impact Tests[END_REF].

In the present experiments, a granite slab of size 200 × 120 × 15 mm 3 is impacted by an aluminum alloy projectile (21 mm in diameter and 40 mm in length) at a speed of 150 m/s. Two tests are performed with similar results and the crack pattern after impact is indicated in Fig. 3.

There are different types of damaged zones in the target with respect to crack density and orientation (see Fig. 3). In the first region (marked (1) in Fig. 3(b)) in front of the projectile there is a small zone consisting of a very large number of cracks in random directions. The material in this region can be considered as crushed due to high compressive stresses beneath the projectile. The second region (marked (2) in Fig. 3(b)) includes a few hoop cracks mostly located close to the confinement. The reason behind the formation of these cracks is not totally clear. However, they presumably form because of wave reflections. The third region (marked (3) in Fig. 3(b)) includes long macroscopic radial cracks, which initiate because of the circumferential motion of the material. The cracks in the second and third region are marked in Fig. 3(b) for the sake of clarity. It is likely that these are mode I cracks initiated by high tensile stresses. In the remaining part of the specimen, outside the above regions, there are an enormous number of cracks, of size up to a few millimeters, in different directions. Most of these cracks are formed along the grain boundaries and some of them are only visible under a microscope. It should be noted that in the region close to the free boundaries, the amount of macroscopic cracks locally increases due to reflections of the compressive wave (spallation).

By observing the surface of the specimen under a microscope, a large number of small cracks can be observed (see Fig. 4). The black color in the micrographs indicates the points where the material is missing, i.e. the cracks. A small part of one of the long macrocracks in Fig. 3(b) is visible in Fig. 4(b), the bold curved line crossing the whole image, together with small cracks oriented in different directions. Note that the amount of damage is decreasing with the distance from the impact point.

In order to evaluate the crack density from the experiment, a line is traced across the micrographs (Fig. 4) and the average distance between the cracks, d, is obtained by dividing the line length by the number of crossed cracks. The crack density is then roughly evaluated as (1/d) 3 , which in this case is about 1.5 × 10 9 and 10 9 cracks/m 3 in Fig. 4 (b) and (c) respectively. It should be emphasized that these numbers are rough estimates.

A representative micrograph of the intact specimen is also shown in Fig. 5. A typical feature of the granite material studied herein is the large number of pre-existing cracks, both at the grain boundaries and also across the grains [START_REF] Peng | Crack growth and faulting in cylindrical specimens of Chelmsford granite[END_REF], [START_REF] Bäckström | Numerical modelling of uniaxial compressive failure of granite with and without saline porewater[END_REF]. When compared to Fig. 4, the amount of damage is noticeably increasing after impact.

Numerical modeling

The equation of motion is discretized using the FE method and the explicit time integration method is employed. The numerical simulation is carried through utilizing in full the KST-DFH material model described above and implemented as a VUMAT subroutine in the Abaqus explicit software [START_REF] Forquin | A Probabilistic Damage Model of the Dynamic Fragmentation Process in Brittle Materials[END_REF]28]. The strain increments are given as input whereas final stress tensor and state variables are computed as output variables of the routine. In the subroutine, the integration scheme is mainly composed of two steps. In the first one, a microscopic stress tensor is calculated considering the KST constitutive law alone. The level of pressure is calculated from the volumetric strain increment considering a piece-wise linear relationship between the volumetric strain and the hydrostatic pressure. The microscopic deviatoric stress tensor is calculated considering the isotropic pressure dependent yield stress criterion defined in Eq. ( 1). In the second step, the three eigen values of microscopic stress tensor are computed. In case of positive microscopic eigen stresses, a damage variable is calculated according to Eq.( 13) and the macroscopic stress is derived (see Eq.( 14). Finally, the macroscopic stress tensor is written in the initial basis.

The numerical simulation of the EOI test is performed in 3D. The quarter-symmetry model consists of 8node linear elements (hexahedra) with reduced integration. The element edge size is 0.5 mm in the rock specimen (see Fig. 6). Surface to surface contact is used in the numerical simulation and all of the KST-DFH model variables are evaluated and extracted during the analysis.

The damage variable, D 1 , field is shown in Fig. 7. When the damage variable reaches unity, it indicates that the element is totally damaged, the physical interpretation being that single or multiple cracks normal to the maximum principal stress direction are open. Similar to D 1 , the second and third damage components grow during the analysis by increasing the load.

Near the impact point, the material behaves plastically due to high levels of confining pressure. Thus the hydrostatic compressive stresses in this region prevent the fragmentation process. The radial cracks due to hoop tensile stresses induced by the particle motion in the radial direction are also shown in Fig. 7. The compressive stress wave is reflected from the specimen boundaries as a relaxation wave and creates some cracks close to the rear face. Some cracks are also formed due to Rayleigh wave propagation along the free surface of the impact side. It should be emphasized that in the model, crack initiation and growth is solely due to positive principal tensile stresses including the possible contribution from shear stresses. Fracturing due to high compressive stresses (for example in the compacted zone close to the region of impact) is indicated in the model by high values on the accumulated plastic strain.

The crack density, due to the maximum principal stress, predicted by the model is compared to the experimental results. The crack density from the numerical simulation is illustrated in Fig. 8. The results are in logarithmic scale. The crack density in the same region as in Fig. 4 (b) and(c) is about 10 11 and 10 10.5 crack/m 3 respectively which is higher than the experimental results. This difference will be explained in more detail below.

The number of radial cracks in the numerical results is very large while there are not that many long radial macrocracks visible in the experimental results. This is most likely due to the presence of large so called structural cracks in the specimen introduced during fabrication of the EOI specimen [START_REF] Saadati | On the mechanical behavior of granite material with particular emphasis on the influence from pre-existing cracks and defects[END_REF]. This feature can indeed be of significant importance for EOI testing of granite as the fabrication of samples requires substantial processing of the material.

To investigate the effect of the structural cracks, the specimen is first impacted at 20 m/s, in a numerical simulation, in order to produce an initial damage. The specimen is subsequently impacted at 150 m/s (similarly as in the experiment). As can be seen in Fig. 9, the damage pattern changes considerably and the number of the radial cracks decreases. The initial cracks prevent some new cracks to form. This effect leads to more realistic results when compared to the experimental observations. The effect of these initial cracks, however, will be further investigated in future studies by introducing these cracks in a more appropriate way. This analysis is only preliminary and leads to a qualitative agreement between experiments and simulations. Furthermore, the crack density decreases when initial cracking is present and becomes much closer to the experimental results (see Fig. 10). Accordingly, the results shown in Figs. 9 and 10 give some confidence in the present numerical approach and an analysis of percussive drilling is then performed below.

A mesh study for the model is reported by Forquin and Hild before [START_REF] Forquin | A Probabilistic Damage Model of the Dynamic Fragmentation Process in Brittle Materials[END_REF]. The boundary between single and multiple fragmentations is affected by the FE size. The smaller the element size, the smaller the region for which multiple fragmentation occurs in the numerical results, because for the same stress rate level, it is more likely for a smaller element to reach failure due to a single crack.

Modeling of percussive drilling

The same numerical tools as above are used to model the percussive drilling problem. Again, the KST-DFH material model is utilized via a VUMAT subroutine in the Abaqus explicit software [START_REF] Forquin | A Probabilistic Damage Model of the Dynamic Fragmentation Process in Brittle Materials[END_REF]28]. A typical drill bit has about ten buttons made of hard steel. To simplify the problem, only one hemispherical button from the bit is considered. Initial damage is not considered in detail as most often in a practical situation there is no preparation of the rock before drilling. Consequently, as discussed previously in the context of the EOI test and in detail in Ref. [START_REF] Saadati | On the mechanical behavior of granite material with particular emphasis on the influence from pre-existing cracks and defects[END_REF], the formation of large structural cracks should be of less importance. Some simulations relevant to repeated impact are performed. The incident stress pulse has a level of 200 MPa with duration of 2 × 10 -4 s and with a rising and descending time of 10 -5 s. A hemispherical indenter (5 mm in radius) is chosen. The steel drill rod is 1 m in length and 6 mm in radius. In a real tool the drill rod cross sectional area is a bit larger than the sum the cross sectional areas of all buttons. Accordingly, the drill rod radius is taken a bit larger than the button in order to take into account the geometric impedance difference between them. Both the drill rod and the button are assumed to be elastically deformable with elastic moduli equal to 200 GPa and 800 GPa respectively. A block of rock with a size of 200 × 200 × 100 mm 3 is exposed to impact. The finite element mesh used in the simulation is shown in Fig. 11. 8-node linear elements with reduced integration are used in the simulations. Infinite elements are used at the rock boundaries to eliminate the wave reflection.

Selected simulation results for the damage variable, induced by the maximum tensile principal stress, are shown in Fig. 12. Firstly, it is compared to cracking under quasi-static conditions. A typical fracture pattern in a rock material due to quasi-static indentation has been determined by Tan et al. [START_REF] Tan | Application of the DDM and fracture mechanics model on the simulation of rock breakage by mechanical tools[END_REF] It includes different types of cracks and also a high compressive part under the indenter called the crushed zone, see Fig. 13.

Although being dynamically loaded, similar types of cracks are captured from the numerical results (Fig. 12). In the region ahead of the indenter, a crushed zone develops. The hydrostatic pressure in this region reaches more than 2 GPa according to the numerical results. It should be emphasized that the high hydrostatic stresses will lead to high values on the effective plastic strain and the damage formed in the crushed zone is a consequence of tensile stresses due to a gradual increase of the contact area. Radial cracks, or radial and median cracks combined, are formed during loading and propagate even more during the unloading phase, see Fig. 12(b). Side cracks, which are mainly formed during the unloading stage and are considered as the most efficient way of removing rock material, are also captured. Fig. 14 shows the damage state in a view cut of the rock block 5 mm beneath the indenter at the end of the loading and unloading stages. The side cracks are marked. These cracks interact with similar types from neighboring buttons and a significant part of the material is removed when they coalesce. In this context, it should also b) be mentioned that all the three damage variables, in the KST-DFH material model, grow during the simulations.

The penetration resistance is obtained from the indentation bit force (P b ) versus indentation penetration (h) response. The force-penetration (P b -h) curve of the drill bit is shown in Fig. 15. By accounting for the symmetric boundary conditions and the number of buttons per drill bit, the penetration stiffness, K s , value is 340 kN/mm. The values of penetration per impact and also the penetration stiffness K s obtained from the numerical simulations are in good agreement with real drilling results [START_REF] Saksala | 3D numerical modelling of bit-rock fracture mechanisms in percussive drilling with a multiple-button bit[END_REF].

If the KST model is considered without any damage in the same drilling simulation as above, the penetration rate decreases considerably with a penetration stiffness of about 548 KN/mm, see Fig. [START_REF] Swenson | A finite element model for the analysis of tailored pulse stimulation of boreholes[END_REF]. This means that in the absence of damage as a dissipation mechanism, the rock behaves as a stronger material and becomes more resistant to the tool indentation.

Mesh size effect on the fracture pattern and the penetration stiffness of the above explained percussive drilling problem have been investigated. It is concluded that the very small details of the crack pattern may be considered as mesh dependent in a sense that the cracks are more likely follow the mesh patterns. However, the size of the damaged zone and the general features of the material response are mainly meshindependent.

As discussed above, initial damage is not explicitly considered in the present drilling analyses based on the fact that structural cracking is expected to be very limited prior to first impact. It should be emphasized that a controlled introduction of such cracks can be of major importance from a drilling efficiency point of view and, accordingly, this feature will be investigated in detail in future studies. However, as mentioned above, some simulations relevant to repeated impact were performed. In short, it was then found that the cracks formed at first impact continued to grow to a very limited extent while a large zone of crushed material was formed below the indenter leading to a less effective drilling procedure. Based on this result a controlled introduction of structural cracks, in order improve drilling efficiency, becomes an even more desirable feature.

Conclusions

Percussive drilling in granite has been investigated experimentally and numerically using finite element simulations. The KST-DFH material model was used to describe the material constitutively and the material parameters are calibrated for Bohus granite by a set of previously performed experiments [START_REF] Saadati | On the mechanical behavior of granite material with particular emphasis on the influence from pre-existing cracks and defects[END_REF]. The numerical simulations were performed using a VUMAT subroutine in the commercial software Abaqus [START_REF] Forquin | A Probabilistic Damage Model of the Dynamic Fragmentation Process in Brittle Materials[END_REF]28].

Edge-On Impact (EOI) tests were performed to validate the numerical model. The fracture pattern and the crack density from the numerical analysis were in qualitative agreement with the experimental results. It was found that effects due to large initial (structural) cracks must be carefully accounted for. These cracks can prevent subsequent initiations and considerably decrease the number of large cracks.

A 3D numerical simulation was then performed to model the percussive drilling problem. It was shown that the fracture pattern at drilling resembles that found under quasi-static indentation of rock materials. In particular, side cracks, which are the most preferable type for removing material, were mainly formed during the unloading stage. The force-penetration curve and the corresponding value on the penetration stiffness, K s , were in a good agreement with real drilling data. The possibility of introducing initial cracks in the material, in order to improve the drilling efficiency, was briefly investigated and discussed.

Table legends

  where α D , , , n d are material-dependent parameters, and D i the damage variable defined for each principal direction. The cohesive term can be seen as an extra contribution related to the fracture energy of the material. It enforces the final failure of an element to occur when the dissipated energy due to the damage process reaches the fracture energy of the material.

Fig.

  Fig.1, and in particular the experimental data at high levels of hydrostatic pressure for which there is a considerable amount of inelastic strains (as the specimen mainly deforms elastically at the initial stage of loading). Presently, the equation of state linking the volumetric strain to the hydrostatic stress is taken to be piece-wise linear and determined by the points (ε v

Fig. 1 .

 1 Fig.1. Quasi-oedometric test results together with the KST model (after[START_REF] Saadati | On the mechanical behavior of granite material with particular emphasis on the influence from pre-existing cracks and defects[END_REF]).

Fig. 2 .

 2 Fig. 2. Schematic of the EOI test with the sarcophagus configuration.

Fig. 3 .

 3 Fig.3. Granite specimen after impact by an aluminum projectile (a), damage pattern is marked to be observable (b). Specific regions (1), (2) and (3), are also shown.

Fig. 4 .

 4 Fig.[START_REF] Bäckström | Numerical modelling of uniaxial compressive failure of granite with and without saline porewater[END_REF]. Granit specimen after impact by the aluminum projectile (a), micrograph of the specimen at a distance of 25 mm (b), and 50 mm (c) from the impact point. The dashed yellow boxes will be used to compare the model predictions with the experimentally evaluated crack density.

Fig. 5 .

 5 Fig. 5. Micrograph of the intact specimen.

Fig. 6 .

 6 Fig.6. FE mesh used in the simulations of the EOI test. Quarter-symmetry model with 775000 8-node linear elements.

Fig. 7 .

 7 Fig. 7. FE simulation results of the EOI test. Damage variable D 1 20 μs (a), and 40 μs (b) after impact (velocity: 150 m/s).

Fig. 8 .

 8 Fig. 8. FE simulation results of the EOI test. Crack density (1/m 3 , logarithmic scale) due to the maximum principal stress 20 μs (a), and 40 μs (b) after impact (velocity 150 m/s).

Fig. 9 .

 9 Fig. 9. FE simulation results of the EOI test. Damage variable D 1 at the end of the first impact at 20 m/s (a), and 40 μs (b) after the second impact at 150 m/s.

Fig. 10 .Fig. 11 .

 1011 Fig. 10. FE simulation results of the EOI test. Crack density (1/m 3 , logarithmic scale) due to the maximum principal stress at end of first impact at 20 m/s (a), and 40 μs (b) after the second impact at 150 m/s.Fig. 11. FE mesh used in the simulations of percussive drilling. Due to symmetries only a quarter of the problem is modeled with 400000 8-node elements.

Fig. 12 .

 12 Fig. 12. FE simulation results of percussive drilling. Damage variable D 1 at the end of loading (a) and at the end of unloading (b) phases.

Fig. 13

 13 Fig.[START_REF] Forquin | A Probabilistic Damage Model of the Dynamic Fragmentation Process in Brittle Materials[END_REF] Cracking pattern in rocks at quasi-static indentation[START_REF] Tan | Application of the DDM and fracture mechanics model on the simulation of rock breakage by mechanical tools[END_REF].

Fig. 14 .

 14 Fig. 14. FE simulation results of percussive drilling. Side crack formation in a view cut 5 mm beneath the indenter at the end of loading (a) at the end of unloading (b).

Fig. 15 .

 15 Fig. 15. FE simulation results of percussive drilling. Force-penetration (P b -h) curve of the drill bit based on the KST-DFH and KST material models.

Fig. 1 20 '

 20 Fig. 1

Fig. 3 22

 3 Fig. 3

Fig. 5

 5 Fig. 5

Fig. 6 25

 6 Fig. 6

  Fig. 8

  Fig. 9

  Fig. 10

Fig. 12 Fig

 12 Fig. 12

Fig. 15

 15 Fig. 14

Table legends Table 1 ,

 legends1 the mechanical properties (E and ν) are determined from direct tensile and compression tests while the DFH model parameters are obtained mainly from flexural experiments. The KST model is calibrated based on quasi-oedometric test results, see Figure legends

Table legends Table 1 .

 legends1

Table 1

 1 Parameters used in the KST-DFH material model. Details regarding the parameters are found in Section 2 above.

	Mechanical parameters
	E (GPa)	52
	 ρ (kg/m 3 )	0.15 2630
	DFH model parameters
	Weibull parameters
	m	23
	σ w (MPa)	18.7
	Z eff (mm 3 )	195
	Obscuration volume parameter
	S	3.74
	k	0.38
	C (m/s)	4400
	KST model parameters
	Parameters for hydrostatic
	behavior
	K (GPa)	31.7
	ε v (i)	0; -0.028
	P (i) (MPa)	0; 860
	Parameters for deviatoric
	behavior
	a 0 (MPa 2 )	23,500
	a 1 (MPa)	465
	a 2	1.51
	Cohesive model parameter
	α D	1.5
	(MPa)	11
		0.004
	n d	1

Table 1

 1


ARNAUD P ÊCHER Christine Bachoc
email: christine.bachoc@math.u-bordeaux1.fr

Alain Thi Éry
email: alain.thiery@math.u-bordeaux1.fr

ON THE THETA NUMBER OF POWERS OF CYCLE GRAPHS

Keywords: 1991 Mathematics Subject Classification. 05C15, 05C85, 90C27 theta number, circular complete graphs, circular perfect graphs

We give a closed formula for Lovász's theta number of the powers of cycle graphs C d-1 k and of their complements, the circular complete graphs K k/d . As a consequence, we establish that the circular chromatic number of a circular perfect graph is computable in polynomial time. We also derive an asymptotic estimate for the theta number of C d k .

INTRODUCTION

Let G = (V, E) be a finite graph with vertex set V and edge set E. The clique number ω(G) and the chromatic number χ(G) are classical invariants of G which can be defined in terms of graph homomorphisms.

A homomorphism from a graph G = (V, E) to a graph G ′ = (V ′ , E ′ ) is a mapping f : V → V ′ which preserves adjacency: if ij is an edge of G then f (i)f (j) is an edge of G ′ . If there is a homomorphism from G to G ′ , we write G → G ′ . Then, the chromatic number of G is the smallest number k such that G → K k , where K k denotes the complete graph with k vertices. Similarly, the clique number is the largest number k such that K k → G.

In the seminal paper [START_REF] Lovász | On the Shannon capacity of a graph[END_REF], Lovász introduced the so-called theta number ϑ(G) of a graph. On one hand, this number provides an approximation of ω(G) and of χ(G) since (this is the celebrated Sandwich Theorem)

ω(G) ≤ ϑ(G) ≤ χ(G),
where G stands for the complement of G. On the other hand, this number is the optimal value of a semidefinite program [START_REF] Vandenberghe | Semidefinite programming[END_REF], and, as such, is computable in polynomial time with polynomial space encoding accuracy [START_REF] Vandenberghe | Semidefinite programming[END_REF], [START_REF] Grötschel | The ellipsoid method and its consequences in combinatorial optimization[END_REF]. In contrast, the computation of either the clique number or the chromatic number is known to be NP-hard.

By definition, a graph G is perfect, if for every induced subgraph H, ω(H) = χ(H) [START_REF] Berge | Färbungen von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind, Wiss[END_REF]. As, for a perfect graph, ϑ(G) = χ(G) and χ(G) is an integer, we have Theorem 1.1. (Grötschel, Lovász and Schrijver) [START_REF] Grötschel | The ellipsoid method and its consequences in combinatorial optimization[END_REF] For every perfect graph, the chromatic number is computable in polynomial time.

There are very few families of graphs for which an explicit formula for the theta number is known. In [START_REF] Lovász | On the Shannon capacity of a graph[END_REF], the theta numbers of the cycles C k and of the Kneser graphs K(n, r) are explicitly computed. In particular, it is shown that, if k is an odd number, xy ∈ E k if the distance in G between x and y is at most k).

In this paper, we give a closed formula for the theta number of the complement K k/d of the circular complete graph. Because the automorphism group of K k/d is vertex transitive (it contains the cyclic permutation (0, 1, . . . , k -1)), we have (see

3) ϑ K k/3 = k 1 - 1 2 -cos 2π k ⌊ k 3 ⌋ -cos 2π k ⌊ k 3 ⌋ + 1 cos 2π k ⌊ k 3 ⌋ -1 cos 2π k ⌊ k 3 ⌋ + 1 -1 . (
In Section 3, we prove the following:

Theorem 1.2. Let d ≥ 2, k ≥ 2d, with gcd(k, d) = 1. Let, for 0 ≤ n ≤ d -1, c n := cos 2nπ d , a n := cos nk d 2π k . Then (4) ϑ(K k/d ) = k d d-1 n=0 d-1 s=1 c n -a s 1 -a s .
The notions of clique and chromatic numbers and of perfect graphs have been refined using circular complete graphs. The circular chromatic number χ c (G) of a graph G was first introduced by Vince in [START_REF] Vince | Star chromatic number[END_REF]. It is the minimum of the fractions k/d for which G → K k/d . Later, Zhu defined the circular clique number ω c (G) of G to be the maximum of the k/d for which K k/d → G and introduced the notion of a circular perfect graph, a graph with the property that every induced subgraph [START_REF] Zhu | Recent developments in circular colouring of graphs[END_REF] for a survey on this notion).

H satisfies ω c (H) = χ c (H) (see Section 7 in
The class of circular perfect graphs extends in a natural way the one of perfect graphs. So one can ask for the properties of perfect graphs that generalize to this larger class. In this paper, we prove that Theorem 1.1 still holds for circular perfect graphs:

Theorem 1.3. For every circular perfect graph, the circular chromatic number is computable in polynomial time.

In previous works, the polynomial time computability of the chromatic number of circular perfect graphs was established in [START_REF] Pêcher | Clique and chromatic number of circular-perfect graphs[END_REF] and of the circular chromatic number of strongly circular perfect graphs (i.e. circular perfect graphs such that the complementary graphs are also circular perfect) was proved in [START_REF] Pêcher | Polynomial time computability of some graph parameters for superclasses of perfect graphs[END_REF].

In contrary to perfect graphs, ϑ(G) does not give directly the result, as ϑ(G)

is not always sandwiched between ω c (G) and χ c (G): for instance, ϑ(C 5 ) = √ 5

and ω c (C 5 ) = χ c (C 5 ) = 5/2. To bypass this difficulty, we make use of the following basic observation: by definition, for every graph G with n vertices such

that ω c (G) = χ c (G) = k/d, we have ϑ(G) = ϑ(K k/d ),
where k, d ≤ n (see the next section for more details). Hence, to ensure the polynomial time computability of χ c (G), it is sufficient to prove that the values ϑ(K k/d ) with k, d ≤ n are all distinct and separated by at least ǫ for some ǫ with polynomial space encoding.

This paper is organized as follows: Section 2 gathers the needed definitions and properties of Lovász theta number and of circular numbers. Section 3 proves Theorem 1.2, while Section 4 proves Theorem 1.3. In Section 5, the asymptotic

estimate ϑ(K k/d ) = k d + O 1 k is obtained (Theorem 5.1).

PRELIMINARIES

The theta number ϑ(G) of a graph G = (V, E) was introduced in [START_REF] Lovász | On the Shannon capacity of a graph[END_REF], where many equivalent formulations are given. The one of [START_REF] Lovász | On the Shannon capacity of a graph[END_REF]Theorem 4] has the form of a semidefinite program:

(5)

ϑ(G) = max (x,y)∈V 2 B(x, y) : B ∈ R V ×V , B 0, x∈V B(x, x) = 1, B(x, y) = 0 xy ∈ E
where B 0 stands for: B is a symmetric, positive semidefinite matrix. For a survey on semidefinite programming, we refer to [START_REF] Vandenberghe | Semidefinite programming[END_REF]. The dual program gives another formulation for ϑ(G) (there is no duality gap here because the identity matrix divided by |V | is a strictly feasible solution of (5) so the Slater condition is fulfilled): ( 6)

ϑ(G) = inf t : B ∈ R V ×V , B 0, B(x, x) = t -1, B(x, y) = -1 xy / ∈ E From (6) one can easily derive that, if G → G ′ , then ϑ(G) ≤ ϑ(G ′ ). Indeed, if
B ′ is an optimal solution of the dual program defining ϑ(G ′ ), then the matrix B defined by B(x, y)

:= B ′ (f (x), f (y)) is feasible for ϑ(G).
The circular complete graphs K k/d have the property that [START_REF] Bondy | A note on the star chromatic number[END_REF]). Thus the theta number ϑ(K k/d ) only depends on the quotient k/d, and we later conveniently assume that k and d are coprime.

K k/d → K k ′ /d ′ if and only if k/d ≤ k ′ /d ′ (see
From the definition, it follows that

ω(G) ≤ ω c (G) ≤ χ c (G) ≤ χ(G).
Moreover, ω(G) = ⌊ω c (G)⌋, χ(G) = ⌈χ c (G)⌉, and ω c (G) and χ c (G) are attained for pairs (k, d) such that k ≥ 2d and k ≤ |V | (see [START_REF] Bondy | A note on the star chromatic number[END_REF], [START_REF] Zhu | Circular perfect graphs[END_REF]).

If G satisfies ω c (G) = χ c (G), let k, d be coprime numbers such that ω c (G) = χ c (G) = k/d. Because G and K k/d are homomorphically equivalent, ϑ(G) = ϑ(K k/d
(G) = χ c (G).
Then,

1. ω c (G) = χ c (G) = k/d for some (k, d) such that k ≥ 2d, k ≤ n, and
gcd(k, d) = 1. 2. ϑ(G) = ϑ(K k/d ).

AN EXPLICIT FORMULA FOR THE THETA NUMBER OF CIRCULAR COMPLETE GRAPHS

In this section we prove Theorem 1.2. We start with an overview of our proof:

first of all we show that ϑ(K k/d ) is the optimal value of a linear program (Proposition 3.1). This step is a standard simplification of a semidefinite program using its symmetries. In a second step, a candidate for an optimal solution of the resulting linear program is defined (Definition 3.3) as the unique solution of a certain linear system. We give an interpretation of this element, in terms of the coefficients of Lagrange interpolation polynomials on the basis of Chebyshev polynomials. Then, playing with the dual linear program, it is easy to prove that this element, if feasible, is indeed optimal (Lemma 3.5). The last step, which is also the most technical, amounts to prove that this elements is indeed feasible, i.e. essentially that its coordinates are nonnegative (Lemma 3.4). To that end, we boil down to prove that a certain polynomial L 0 (y) has nonnegative coefficients when expanded as a linear combination of the Chebyshev polynomials (Lemma 3.7).

3.1.

A linear program defining the theta number. The vertex set of G = K k/d can be identified with the additive group Z/kZ, and the additive action of this group defines automorphisms of this graph. This action allows to transform the semidefinite program (5) into a linear program, as follows:

Proposition 3.1. Let k 0 := ⌊k/2⌋. We have:

(7) ϑ(K k/d ) = max kf 0 : f j ≥ 0, k 0 j=0 f j = 1, k 0 j=0 f j cos 2jℓπ k = 0, 1 ≤ ℓ ≤ d -1
and also:

(8) ϑ(K k/d ) = min kg 0 : d-1 ℓ=0 g ℓ ≥ 1, d-1 ℓ=0 g ℓ cos 2ℓjπ k ≥ 0, 1 ≤ j ≤ k 0
Proof. Taking the average over the translations by the elements of Z/kZ, one constructs from a matrix B which is optimal for (5), another optimal matrix which is translation invariant, i.e. which satisfies B(x + z, y + z) = B(x, y) for all

x, y, z ∈ Z/kZ. Thus one can restrict in (5) to the matrices B which are translation invariant. In other words, we can assume that B(x, y) = F (x -y) for some

F : Z/kZ → R.
Then we can use the Fourier transform over Z/kZ to express F as

F (z) = k-1 j=0 f j e 2ijzπ/k .
Then B 0 if and only if f j = f k-j and f j ≥ 0 for all j = 0, . . . , k -1. After a change from f j to 2f j for j = 0, k/2, we can rewrite

B(x, y) = k 0 j=0 f j cos 2j(x -y)π k .
Then, it remains to transfer to (f 0 , . . . , f k 0 ) the constraints on B that stand in [START_REF] Delsarte | An algebraic approach to the association schemes of coding theory[END_REF].

We have

(x,y)∈(Z/kZ) 2 B(x, y) = k 2 f 0 , and x∈Z/kZ B(x, x) = k k 0 j=0 f j . The edges of K k/d are the pairs (x, y) with 1 ≤ |x -y| ≤ d -1 so the condition that B(x, y) = 0 for all edges (x, y) translates to k 0 j=0 f j cos 2jℓπ k = 0, 1 ≤ ℓ ≤ d -1.
Changing f j to f j /k leads to [START_REF] Lang | Algebraic Number Theory[END_REF]. The linear program [START_REF] Lovász | On the Shannon capacity of a graph[END_REF] is the dual formulation of (7).

Remark 3.2. The linear program [START_REF] Lang | Algebraic Number Theory[END_REF] is essentially equal to the linear program defined by Delsarte in his study of the subsets of association schemes [START_REF] Delsarte | An algebraic approach to the association schemes of coding theory[END_REF]. Here the underlying association scheme is the so-called Lee association scheme.

3.2.

A candidate for an optimal solution of [START_REF] Lang | Algebraic Number Theory[END_REF]. In order to understand the construction of this solution, it is worth to take a look at the case when d divides k.

Indeed, in this case, the system of linear equations

k 0 j=0 f j cos 2jℓπ k = δ 0,l , 0 ≤ ℓ ≤ d -1 which is equivalent to k-1 j=0 f ′ j e 2ijℓπ/k = δ 0,l , 0 ≤ ℓ ≤ d -1 where f ′ j = f ′ k-j = f j /2 for j = 0, k/2, otherwise f ′ j = f j , has an obvious solution f = (f ′ 0 , . . . , f ′ k-1
) defined as follows: take f j = 1/d for the indices j which are multiples of k/d, i.e. for j = nk/d, n = 0, . . . , d -1. Take f j = 0 for other indices. Then f has exactly d non zero coefficients, is feasible because f j ≥ 0, and its objective value equals k/d, which is also the optimal value of the linear program.

In the case when gcd(k, d) = 1, none of the rational numbers nk/d, for n = 1, . . . , d-1, are integers. Instead, we choose indices which are as close as possible, namely we choose the indices of the form ⌊ nk d ⌋ for 0 ≤ n ≤ d -1 and set all other coefficients to zero. Then, the d-tuple of coefficients which are not set to zero, satisfies a linear system with d equations, and this linear system has a unique solution. We shall prove that in this way an optimal solution of ( 7) is obtained. Now we introduce some additional notations. The Chebyshev polynomials ( [START_REF] Szegö | Orthogonal polynomials[END_REF]), denoted (T ℓ ) ℓ≥0 are defined by the characteristic property: T ℓ (cos(θ)) = cos(ℓθ).

They can be iteratively computed by the relation

T ℓ+1 (x) = 2xT ℓ (x) -T ℓ-1 (x)
and the first terms T 0 = 1, T 1 = x. These polynomials are orthogonal for the

measure dx/ √ 1 -x 2 supported on the interval [-1, 1].
The numbers a n , 0 ≤ n ≤ d -1, introduced in Theorem 1.2, come into play now. Recall that

a n = cos nk d 2π k .
We remark that the coefficients in the linear constraints of ( 7) associated to the indices ⌊ nk d ⌋ are precisely equal to T ℓ (a n ). We assume for the rest of this section that gcd(k, d) = 1. Then the real numbers a n are pairwise distinct. We introduce the Lagrange polynomials ( [START_REF] Szegö | Orthogonal polynomials[END_REF]) associated to (a 0 , . . . , a d-1 ):

(9) L n (y) := d-1 s=0 s =n y -a s a n -a s .
Now we have two bases for the space of polynomials of degree at most equal to d-1: the Chebyshev basis {T 0 , . . . , T d-1 } and the Lagrange basis {L 0 , . . . , L d-1 }.

We introduce the two d × d matrices T = (τ ℓ,n ) and L = (λ n,ℓ ) such that

(10) T ℓ (y) = τ ℓ,0 L 0 (y) + τ ℓ,1 L 1 (y) + • • • + τ ℓ,d-1 L d-1 (y) 0 ≤ ℓ ≤ d -1 and (11) L n (y) = λ n,0 T 0 (y) + λ n,1 T 1 (y) + • • • + λ n,d-1 T d-1 (y) 0 ≤ n ≤ d -1.
Obviously we have

(12) τ ℓ,n = T ℓ (a n )
and

T L = LT = I d .
In particular, the d-tuple (λ 0,0 , λ 1,0 , . . . , λ d-1,0 ) satisfies the equations:

(13) d-1 n=0 λ n,0 T ℓ (a n ) = δ ℓ,0 , 0 ≤ ℓ ≤ d -1.
Now we can define our candidate for an optimal solution of (7):

Definition 3.3.
With the above notations, let f * = (f * 0 , . . . , f * k 0 ) be defined by:

     f * j = λ n,0 if j = ± nk d mod k f * j = 0 otherwise.
It remains to prove that f * is indeed optimal for (7). It will result from the two following lemmas:

Lemma 3.4. For all j, 0 ≤ j ≤ k 0 , f * j ≥ 0.
We postpone the proof of Lemma 3.4 to the next subsection.

Lemma 3.5. f * is an optimal solution of (7).

Proof. Lemma 3.4, joined with [START_REF] Vince | Star chromatic number[END_REF] shows that f * is feasible. Thus we can derive the inequality:

kλ 0,0 ≤ ϑ(K k/d ).
Now we claim that the element g * = (λ 0,0 , λ 0,1 , . . . , λ 0,d-1 ) is a feasible solution of the dual program [START_REF] Lovász | On the Shannon capacity of a graph[END_REF]. For that we need to prove that

d-1 ℓ=0 λ 0,ℓ cos 2ℓjπ k ≥ δ j,0 , 0 ≤ j ≤ k 0
which can be rewritten as

d-1 ℓ=0 λ 0,ℓ T ℓ cos 2jπ k ≥ δ j,0 , 0 ≤ j ≤ k 0
or, taking account of ( 11), ( 14)

L 0 cos 2jπ k ≥ δ j,0 , 0 ≤ j ≤ k 0 .
For j = 0, (14) holds because L 0 (1) = L 0 (a 0 ) = 1. For j ≥ 1, we take a look at the position of cos(2jπ/k) with respect to the roots a 1 , . . . , a d-1 of L 0 . Indeed, these roots belong to the set {cos(2jπ/k), j = 1, . . . , k -1}, but it should be noticed that they go in successive pairs. More precisely, a n and a d-n are equal to the first coordinate of neighbor vertices of the regular k-gon. So either cos(2jπ/k) is equal to one of the a n , or there is an even number of roots a n , n ≥ 1, which are greater than cos(2jπ/k). In the later case, L 0 (cos(2jπ/k)) and L 0 (1) have the same sign. Since L 0 (1) = 1, we are done.

Since g * is a feasible solution of ( 8), its objective value, which is equal to kλ 0,0 , upper bounds ϑ(K k/d ). So we conclude that

ϑ(K k/d ) = kλ 0,0
and that f * is an optimal solution of (7).

3.3. The proof of Lemma 3.4. We want to prove that λ n,0 ≥ 0 for all n = 0, . . . , d -1. We first prove that this condition is equivalent to: λ 0,ℓ ≥ 0 for all 0 ≤ ℓ ≤ d -1.

Lemma 3.6. The tuples (λ n,0 , 0 ≤ n ≤ d -1) and (λ 0,ℓ , 0 ≤ ℓ ≤ d -1) are equal up to a permutation of their coordinates.

Proof. It turns out that, up to a permutation of the a n , the matrix T is symmetric.

Since gcd(k, d) = 1, one can find v, 1 ≤ v ≤ d -1,
a n ′ = cos vnk d 2π k = cos 2ntπ k .
If we set

(15) x = x(k, d) := cos 2tπ k = cos v d - 1 kd 2π ,
we have

a n ′ = T n (x).
If we reorder the a n according to the permutation n → vn mod d, which fixes 0, the coefficients of the corresponding matrix T are equal to:

τ ℓ,n = T ℓ (a n ′ ) = T ℓ (T n (x)) = T ℓn (x) = T nℓ (x) = τ n,ℓ .
Thus the new matrix T is symmetric. This reordering of the a n , permutes accordingly the coordinates of (λ n,0 , 0 ≤ n ≤ d -1). Also the matrix L = T -1 has become symmetric, so the permuted λ n,0 are equal to λ 0,n (who have not changed in the procedure because the polynomial L 0 (y) is not affected by the reordering of the a n ).

The next lemma ends the proof of Lemma 3.4:

Lemma 3.7. For all 0 ≤ ℓ ≤ d -1, λ 0,ℓ ≥ 0. Proof. Since d-1 s=1 (1 -a s ) ≥ 0, we can replace L 0 (y) by d-1 s=1 (y -a s ) = d-1 s=1 (y -T s (x))
where x is defined in [START_REF] Zhu | Recent developments in circular colouring of graphs[END_REF]. The right hand side becomes a polynomial in the variables x and y, depending only on d. This polynomial has an expansion in the Chebyshev basis:

(16)

d-1 s=1 (y -T s (x)) = d-1 ℓ=0 Q ℓ (x)T ℓ (y).
We introduce complex variables X and Y , such that 2x = X + 1/X and 2y = Y + 1/Y . Then, (16) becomes:

(17)

d-1 s=1 (Y -X s )(Y -X -s ) = Y d-1 d-1 ℓ=-(d-1) Q ′ ℓ (x)Y ℓ where Q ′ 0 = 2 d-1 Q 0 and, for ℓ = 1, . . . , d -1, Q ′ -ℓ = Q ′ ℓ = 2 d-2 Q ℓ .
We want to prove that Q ′ ℓ (x) ≥ 0 when x is given by [START_REF] Zhu | Recent developments in circular colouring of graphs[END_REF]. To that end, we will prove that this sequence of numbers is decreasing:

(18) Q ′ 0 (x) ≥ Q ′ 1 (x) ≥ • • • ≥ Q ′ d-1 (x)
and since Q ′ d-1 (x) = 1, we will be done. Now the idea is to multiply the equation ( 17) by (Y -1), so that the successive differences Q ′ ℓ-1 (x) -Q ′ ℓ (x) appear in the right hand side as the coefficients of Y ℓ . We obtain, setting

Q ′ -d = Q ′ d := 0: (19) d-1 s=-(d-1) (Y -X s ) = Y d-1 d ℓ=-(d-1) (Q ′ ℓ-1 (x) -Q ′ ℓ (x))Y ℓ .
We let:

(20)

P (Y ) := d-1 s=-(d-1) (Y -X s ) := 2d-1 j=0 C j (X)Y j .
We have:

P (XY ) = d-1 j=-(d-1) (XY -X j ) = X 2d-1 d-1 j=-(d-1) (Y -X j-1 ) = X 2d-1 Y -X -d Y -X d-1 P (Y ).
This equation leads to:

(Y -X d-1 ) 2d-1 j=0 C j (X)X j Y j = (X 2d-1 Y -X d-1 ) 2d-1 j=0 C j (X)Y j .
Comparing the coefficients of Y j in both sides, we obtain the formula:

(21) C j (X) = C j-1 (X) X j-d -X d X j -1 , 1 ≤ j ≤ 2d -1.
If X = e iθ , we obtain in (21)

(22) C j (X) = C j-1 (X) sin(( j 2 -d)θ) sin( jθ 2 ) , 1 ≤ j ≤ 2d -1.
Thus, taking account of ( 15), ( 19), ( 20) and ( 22), the inequalities (18) that we want to establish, are equivalent to the non negativity of 3.4. The end of the proof of Theorem 1.2. We have obtained an optimal solution f * of ( 7), given in Definition 3.3, with objective value equal to kλ 0,0 . So we have

sin(( j 2 -d)θ) sin( jθ 2 ) when θ = v d -1 kd 2π, 1 ≤ j ≤ d -1, and k ≥ 2d. Let us prove it now: let      N = N (k, d) := ⌊ jv d ⌋ ε = ε(k, d) := jv d -N.
(23) ϑ(K k/d ) = kλ 0,0 .
We recall that:

(24) L 0 (y) = λ 0,0 T 0 (y) + λ 0,1 T 1 (y) + • • • + λ 0,d-1 T d-1 (y).
If we plug in (24) the value y = c n and sum up for n = 0, . . . , d-1, taking account

of T 0 = 1 and d-1 n=0 T j (c n ) = d-1 n=0 cos(2jnπ/d) = 0 for 1 ≤ j ≤ d -1
, we obtain the formula (4).

Other expressions for ϑ(K k/d

). Alternatively, we can integrate (24) for the measure dy/ 1 -y 2 , for which the Chebyshev polynomials are orthogonal, leading to different expressions for ϑ(K k/d ):

Theorem 3.8. We have, with the notations of Theorem 1.2:

ϑ(K k/d ) = k π 1 -1 L 0 (y) dy 1 -y 2 (25) = (-1) d-1 k d-1 n=1 (1 -a n ) ⌊(d-1)/2⌋ j=0 1 2 2j 2j j σ d-1-2j (a 1 , . . . , a d-1 ) (26)
where σ 0 , . . . , σ d-1 denote the elementary symmetric polynomials in d -1 variables.

Proof. Integrating (24) for the measure dy/ 1 -y 2 over the interval [-1, 1] leads to (25) because the Chebyshev polynomials T n satisfy:

1 π 1 -1 T n (y) dy 1 -y 2 = δ n,0 .
Then, ( 26) is obtained from (25) with the monomial expansion of L 0 (y) and the formula

1 π 1 -1 y j dy 1 -y 2 =      0 if j is odd 1 2 j j j/2
otherwise .

Remark 3.9. The expression (4) specializes, when d = 2 and d = 3, to the expressions given respectively in [START_REF] Lovász | On the Shannon capacity of a graph[END_REF] and [START_REF] Brimkov | On the Lovász number of certain circular graphs[END_REF]. Indeed, in the case d = 2, we have c 0 = 1, c 1 = -1, and a 1 = -cos(π/k). Replacing in (4), we recover [START_REF] Berge | Färbungen von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind, Wiss[END_REF].

For d = 3, we have c 1 = c 2 = -1/2, a 1 = cos(⌊ k 3 ⌋ 2π k ) and a 2 = cos((⌊ k 3 ⌋ + 1) 2π k ).
We obtain in (4)

ϑ(K k/3 ) = k 3 1 + (c 1 -a 1 )(c 1 -a 2 ) (1 -a 1 )(1 -a 2 ) + (c 2 -a 1 )(c 2 -a 2 ) (1 -a 1 )(1 -a 2 ) = k(1/2 + a 1 a 2 ) (1 -a 1 )(1 -a 2 )
which agrees with the expression (3) given in [4, Theorem 1].

SEPARATING THE ϑ(K k/d )

In this section, we prove Theorem 1.3. Jointly with Proposition 2.1, and following the discussion in the Introduction, it will be an immediate consequence of the following theorem: Theorem 4.1. There exists an absolute and effective constant c such that for all

N ∈ N, k ≤ N, k ′ ≤ N, k ≥ 2d, k ′ ≥ 2d ′ with gcd(k, d) = gcd(k ′ , d ′ ) = 1, and k/d = k ′ /d ′ , |ϑ(K k/d ) -ϑ(K k ′ /d ′ )| ≥ 1 c N 5 .
We start with a proof of the weaker property that ϑ(

K k/d ) = ϑ(K k ′ /d ′ ) if k/d = k ′ /d ′ . Theorem 4.2. If ϑ(K k/d ) = ϑ(K k ′ /d ′ ) then k/d = k ′ /d ′ . Proof. Assume that ϑ(K k/d ) = ϑ(K k ′ /d ′ ) for k/d < k ′ /d ′ . Since ϑ(K p/q
) is an increasing function of p/q (see Section 2), it implies that ϑ(K p/q ) is constant for

all p/q ∈ [k/d, k ′ /d ′ ]
. This constant will be denoted ϑ for simplicity.

Claim 4.3. The number ϑ is rational.

Proof. Let q ≥ 5 be a prime such that 1/q < 1 4 (k ′ /d ′ -k/d). Then there exists r such that r/q, (r + 1)/q, (r + 2)/q, (r + 3)/q ∈ [k/d, k ′ /d ′ ]. Since q ≥ 5, it divides at most one of the four numbers r, r + 1, r + 2, r + 3. Hence one can find p such that p/q, (p + 1)/q ∈ [k/d, k ′ /d ′ ] and q is prime to p and p + 1.

For any positive integer a, denote ζ a = exp(2iπ/a). We refer to [START_REF] Lang | Algebraic Number Theory[END_REF] for the basic notions of algebraic number theory that will be involved next. For a number field K, we let Gal(K) denote its Galois group over Q. For number fields K ⊂ L, and x ∈ L, Trace L K (x) and Norm L K (x) denote respectively the trace and norm of x in the extension L/K.

It is well-known (see [START_REF] Lang | Algebraic Number Theory[END_REF]) that We now compute ϑ = ϑ(K p/q ) using formula [START_REF] Brimkov | On the Lovász number of certain circular graphs[END_REF]. By definition, we have

Ψ a : (Z/aZ) × -→ Gal(Q(ζ a )) n → σ n such that σ n (ζ a ) = ζ n
c n = cos(2nπ/q) = 1 2 (ζ n q + ζ -n q ) = σ n (c 1 ) for 1 ≤ n ≤ q -1. It follows that ϑ = p q (1 + Trace Q(ζpq) Q(ζp) (L 0 (c 1 ))).
It gives immediately that ϑ ∈ Q(ζ p ). The same result using (p + 1)/q leads to ϑ ∈ Q(ζ p+1 ). Since the fields Q(ζ p ) and Q(ζ p+1 ) are linearly disjoint, this proves the result.

Claim 4.4. The number ϑ is an integer.

Proof. Let ϑ = a b with a, b ∈ N coprime. Using the same arguments as in the previous lemma, for any prime p such that 1/p < 1 4 (d/k -d ′ /k ′ ), one can find q, with p coprime to q and q + 1, such that q/p, (q + 1)

/p ∈ [d/k, d ′ /k ′ ] . It means that p/q, p/(q + 1) ∈ [k/d, k ′ /d ′ ].
Using formula (4) for p/q, one sees that x = q q-1 n=1 (2 -2a n )ϑ is an algebraic integer, hence Norm

Q(ζpq) Q (x) ∈ Z.
We now compute this norm.

Since qϑ is rational, Norm pq) where φ is the Euler function. Since p is a prime, a n is a conjugate of a 1 for all 1 ≤ n ≤ q -1, hence

Q(ζpq) Q (qϑ) = (qϑ) φ(
Norm Q(ζpq) Q ( q-1 n=1 (2 -2a n )) = (Norm Q(ζpq) Q
(2 -2a 1 )) q-1 . We also have

2 -2a 1 = 2 -2 cos(⌊ p q ⌋ 2π p ) = (1 -ζ ⌊ p q ⌋ p )(1 -ζ -⌊ p q ⌋ p ). Hence Norm Q(ζpq) Q (2 -2a 1 ) = (Norm Q(ζpq) Q (1 -ζ p )) 2 . Finally, Norm Q(ζpq) Q (1 -ζ p ) = Norm Q(ζp) Q (Norm Q(ζpq) Q(ζp) (1 -ζ p )) = (Norm Q(ζp) Q (1 -ζ p )) φ(q) = p φ(q)
(see [START_REF] Lang | Algebraic Number Theory[END_REF]). Summing up all partial results, one gets (q a b ) φ(pq) p 2(q-1)φ(q) ∈ Z.

If l = p is a prime factor of b, then l divides q by the previous formula. But the same formula holds with q + 1, hence l divides also q + 1. It follows that b is a power of p. But this is true for any p large enough. Hence b = 1. This proves the result.

To finish the proof of Theorem 4.2, we use the following result from [START_REF] Pêcher | Clique and chromatic number of circular-perfect graphs[END_REF] (see also [START_REF] Grötschel | The ellipsoid method and its consequences in combinatorial optimization[END_REF]): if ϑ(K k/d ) ∈ N then k/d ∈ N. But every rational number in the interval Proof. Since α is a non zero algebraic integer , | Norm

Q(α) Q (α)| ≥ 1. It follows immediately that |α|c δ-1 ≥ 1. Let α =dd ′ d-1 n=1 (2 -2a n ) d ′ -1 n=1 (2 -2a ′ n )(ϑ(K k/d ) -ϑ(K k ′ /d ′ )) =kd ′ d ′ -1 n=1 (2 -2a ′ n ) d-1 n=0 d-1 m=1 (2c n -2a m ) -k ′ d d-1 n=1 (2 -2a n ) d ′ -1 n=0 d ′ -1 m=1 (2c ′ n -2a ′ m )
with the obvious notations c ′ n := cos

≤ kd ′ 4 d ′ -1 d4 d-1 + k ′ d4 d-1 d ′ 4 d ′ -1 ≤ 2N N 2 4 N 2 N 2 4 N 2 ≤ N 3 4 N .
It follows from Lemma 4.5 that

|α| ≥ 1 (N 3 4 N ) N 4 . Furthermore, |dd ′ d-1 n=1 (2 -2a n ) d ′ -1 n=1 (2 -2a ′ n )| ≤ N 2 4 N . This implies imme- diately that |ϑ(K k/d ) -ϑ(K k ′ /d ′ )| ≥ 1 N 2 4 N (N 3 4 N ) N 4 .
This finishes the proof of Theorem 4.1.

THE ASYMPTOTIC BEHAVIOUR OF ϑ(K k/d )

From Lovász's formula (1), the asymptotic behaviour of the theta number of odd holes C 2k+1 is (see [START_REF] Bohman | A limit theorem for the Shannon capacities of odd cycles II[END_REF] for instance):

(27) ϑ (C 2k+1 ) = 2k + 1 2 + O 1 k .
In general, we have ϑ

(K k/d ) ≤ k/d. Indeed, ϑ(K k/d ) = k/ϑ(K k/d ) ≤ k/ω(K k/d ) = k/d.
In this section, we prove:

Theorem 5.1. If d ≥ 3 and k ≥ 4d 3 /π then ϑ(K k/d ) ≥ k d -4eπ 2 3 d k . Hence, for d fixed, ϑ(K k/d ) = k d + O 1 k .
Notice that for d = 2, Theorem 5.1 agrees with Equation (27).

Proof. Let d ≥ 3 and k ≥ 4d 3 /π. For every 0 ≤ i ≤ d -1, let c i = cos(2iπ/d),

σ i = sin(2iπ/d), a i = cos ik d 2π k and δ i = c i -a i . We have a i = cos(2iπ/d- 2πǫ i ), with ǫ i = s i /kd and s i = ik mod d. Claim 5.2. For every 1 ≤ j ≤ d -1, we have d-1 i=0 i =j,d-j (c j -c i ) = -d 2 2 d σ 2 j if j = 0, d/2 (28) d-1 i=0 i =j,d-j (c j -c i ) = -d 2 2 d-1 if j = d/2 (29) d-1 i=1 1 1 -c i = d 2 -1 6 (30)
Proof. The proof of these equalities is a short computation and the details are omitted. Equation (29) (respectively (28), (30)) is obtained by taking the first derivative (respectively the second derivative, the third derivative) with respect to x of the equality T k (cos x) = cos(kx), taking into account the identity T k (x) -1 = 2 k-1 k-1 i=0 (x -c i ), then by evaluating the resulting identity at π (respectively 2jπ/q, respectively 0). Proof. Indeed,

d-1 i=1 (1 -a i ) = d-1 i=1 (1 -c i ) d-1 i=1 1 + δ i 1 -c i ≥ d 2 2 d-1 d-1 i=1 1 - 2π k(1 -c i )
due to (29).

If x 1 , . . . , x l are real numbers belonging to [0, 1], then l i=1 (1 -x i ) ≥ 1 -(x 1 + . . . + x l ). Since for every i, 2π k(1-c i ) ≤ 1, it follows:

d-1 i=1 (1 -a i ) ≥ d 2 2 d-1 1 - 2π k d-1 i=1 1 1 -c i

.

  For k ≥ 2d, the circular complete graph K k/d has k vertices {0, 1, . . . , k -1} and two vertices i and j are connected by an edge ifd ≤ |i -j| ≤ k -d. We have K k/1 = K k and K k/2 = C k . More generally, the graph K k/d is the (d -1) thpower of the cycle graph C k (here the power of a graph is not defined like in Shannon theory of the capacity of a graph; if G = (V, E), G k = (V, E k ) where

[ 8 ,

 8 Theorem 8]) (2) ϑ(K k/d )ϑ(K k/d ) = k so we also obtain a closed formula for the theta number of K k/d . Besides the case d = 2 demonstrated by Lovász, the case d = 3 and k odd was considered by Brimkov et al. who proved in [4] that, for

Since v and d are coprime and 1 ≤

 1 j < d, we have ε ∈ { 1 d , 2 d , . . . , d-1 d }. We first study the sign of sin( jθ 2 ): since jθ 2 = π(N + ε -j kd ), this number belongs to ]N π, (N + 1)π[, which means that the sign of sin( jθ 2 ) is (-1) N . Now we determine the sign of sin(( j 2 -d)θ) : we have ( j 2 -d)θ = π(N -2v+εj kd + 2 k ), from which we obtain that ( j 2 -d)θ belongs to ](N -2v)π, (N -2v+1)π[, thus the sign of sin(( j 2 -d)θ) equals (-1) N +2v .

a

  is an isomorphism. Furthermore, if a and b are coprime,(Z/abZ) × = (Z/aZ) × × (Z/bZ) ×by Chinese Remainder Theorem. It implies immediately thatGal(Q(ζ ab )) = Gal(Q(ζ a )) × Gal(Q(ζ b )),hence the fields Q(ζ a ) and Q(ζ b ) are linearly disjoint over Q.

[Lemma 4 . 5 .

 45 k/d, k ′ /d ′ ] cannot be an integer. We can now start the proof of Theorem 4.1. It is based on the following obvious lemma. Let α be a non zero algebraic integer of degree less than δ and c ≥ 1 such that the absolute values of the conjugates of α are less than c then |α| ≥ 1 c δ

Remark 4 . 6 .

 46 It should be noted that, in the proof of Theorem 4.1, we do not make use of the property ω c (H) = χ c (H) for every induced subgraph, but only of ω c (G) = χ c (G).

Claim 5 . 3 .Claim 5 . 4 . 3 k 1 i=1( 1 -

 5354311 For every 1 ≤ j ≤ d -1, we haveδ j δ d-j For every 1 ≤ j ≤ d -j, let z j ∈ [2jπ/d -2πǫ j , 2jπ/d] such that δ j = -2πǫ j sin(z j ). As | sin(z j )| ≤ |σ j | or | sin(z d-j )| ≤ |σ j |, we get |δ j δ d-j | ≤ 4π 2 |σ j |(|σ j | + 2π/k)/k 2 .Taking into account |σ j | ≥ sin π d ≥ 2/d, we obtain (31). The inequality (32) is straightforward. For every 1 ≤ j ≤ d -1, we have(33) d-1 i=1 |c j -a i | ≤ eπ 2 2 d-3 (1 -c j ) d 2 k 2 .Proof. Let m j = δ j δ d-j if j = d/2, and m d/2 = δ d/2 . We haved-1 i=1 |c j -a i | = m j d-1 i=1 i =j,d-j (c j -c i ) since |c j -c i | ≥ π 2 2d 2 for every i = j, d -j ≤ π 2 e 2 d-3 (1 -c j ) d 2 k 2 as k ≥ 4d 3 /π.Claim 5.5. We have da i ) ≥ d 2 2 d .

≥ d 2 2 dCorollary 5 . 6 .

 256 due to (30) and k ≥ 4d 3 /π. Now we are ready to prove Theorem 5.1. We have the following chain of in-5.1 shows that ϑ is close to the circular chromatic number of dense circular perfect graphs (where dense means that the clique number is large compared to the stability number): For every ǫ > 0, for every positive integer α, there is a positive integer ω such that for every circular-perfect graph G satisfying ω(G) ≥ ω and α(G) ≤ α, we have |ϑ G -χ c (G)| ≤ ǫ.

  The number α is thus an algebraic integer, and it is non zero by Theorem 4.2. Moreover it belongs to Q(ζ kdk ′ d ′ ), hence its degree is less than N 4 .Let β be a conjugate of α. Since the absolute values of the conjugates of a n , a ′

	2nπ d ′	and a ′ n := cos nk ′ d ′	2π k ′ .

n , c n and c ′ n are all less than 1, one gets |β|

Supported by the ANR/NSC project GraTel ANR-09-blan-0373-01, NSC98-2115-M-002-013-MY3 and NSC99-2923-M-110-001-MY3.