Alexandre Gélin
email: alexandre.gelin@lip6.fr

Antoine Joux
email: antoine.joux@m4x.org

K Alexandre Gélin

Reducing number field defining polynomials: An application to class group computations

In this paper, we describe how to compute smallest monic polynomials that define a given number field K. We make use of the one-to-one correspondence between monic defining polynomials of K and algebraic integers that generate K. Thus, a smallest polynomial corresponds to a vector in the lattice of integers of K and this vector is short in some sense. The main idea is to consider weighted coordinates for the vectors of the lattice of integers of K. This allows us to find the desired polynomial by enumerating short vectors in these weighted lattices. In the context of the subexponential algorithm of Biasse and Fieker for computing class groups, this algorithm can be used as a precomputation step that speeds up the rest of the computation. It also widens the applicability of their faster conditional method -which requires a defining polynomial of small height -to a much larger set of number field descriptions.

Introduction

Computing the class group and the regulator of a number field are two major tasks in algorithmic algebraic number theory. The first results only addressed quadratic number fields: Shanks [START_REF] Shanks | Class number, a theory of factorization, and genera[END_REF][START_REF] Shanks | The infrastructure of a real quadratic field and its applications[END_REF] described an algorithm based on the baby-step-giant-step method which computes the class group and the regulator in exponential runtime O(|∆ K | 1 5 ) under the extended Riemann hypothesis, where ∆ K denotes the absolute discriminant of the considered number field.

The first subexponential algorithm, proposed by Hafner and McCurley [START_REF] Hafner | A rigorous subexponential algorithm for computation of class groups[END_REF], computes the class group structure of an imaginary quadratic number field in heuristic time

L |∆ K | ( 1 2 , √ 2
). This L-notation is classical when presenting index calculus algorithms with subexponential complexity. Given two constants α and c with α ∈ [0, 1] and c ≥ 0, L N (α, c) is used as a shorthand for: exp (c + o(1))(log N ) α (log log N ) 1-α , where o(1) tends to 0 as N tends to infinity.

In [START_REF] Buchmann | A subexponential algorithm for the determination of class groups and regulators of algebraic number fields[END_REF], Buchmann extended this method to all number fields, obtaining a heuristic complexity of L |∆ K | ( 1 2 , 1.7), for any arbitrary but fixed number field degree. Recently, Biasse and Fieker [START_REF] Biasse | Subexponential class group and unit group computation in large degree number fields[END_REF] obtained a subexponential complexity for all number fields, without restriction on the extension degree. They achieved a L |∆ K | ( 2 3 + ε, O(1)) complexity † in the general case and

L |∆ K | ( 1 2 , O (1)
) when the extension degree n satisfies the inequality n ≤ (log |∆ K |) 3/4-ε . Furthermore, for some restricted classes of number fields they achieve an even better L |∆ K | (a, O(1)) complexity with a possibly as low as 1 3 . More precisely, they achieve this improved complexity when the polynomial used to define the number field has small coefficients compared to the discriminant of the field. Contribution. Our main result is an algorithm that given a number field, described by some defining polynomial, computes a reduced polynomial, i.e. a monic polynomial with minimal coefficients defining this number field. The complexity of the reduction algorithm is of the form L |∆ K | where the first constant depends on the extension degree n and the second one on the size of the coefficients of any minimal defining polynomial ‡ . We are especially interested in the fields for which it is possible to find a reduced polynomial whose coefficients are small compared to the field discriminant. Indeed, for these fields, using a reduced polynomial allows the algorithm of Biasse and Fieker to run in time L |∆ K | (a, O(1)) with 1 3 ≤ a < 1 2 . Thus, by running our algorithm as a preliminary step to theirs, we generalize their approach, with its reduced complexity, to a wider class of number field descriptions.

Outline. The article is organized as follows. In Section 2, we introduce the necessary notation and tools. Section 3 presents our motivations for finding such an algorithm in the context of class group computations. In Section 4, we present the current state of the art for reducing number field defining polynomials, namely the algorithm of Cohen and Diaz y Diaz. Our new reduction algorithm is described in Section 5 and its complexity is analyzed in Section 6. Finally, some examples of its application to class group computations are shown in Section 7.

A reminder on number fields and their defining polynomials

As usual, an algebraic number field is given as the quotient of Q[X] by a preferably monic irreducible polynomial in Z[X]. Let K be a number field of degree n = [K : Q] and denote by O K the ring of integers of K. It is always possible to rewrite K as Q[θ] with θ in O K . Since θ is an algebraic integer, its minimal polynomial T is monic, moreover as θ generates K the degree of T is n. As a consequence we have rewritten:

K Q[X]/(T ), with T monic in Z[X].
In the sequel, we only consider such monic polynomials in Z[X], each of them corresponding to an integer that generates K. We denote by t k the coefficients of T and by τ j its (necessarily distinct) roots. Thus, we have:

T (X) = n k=0 t k X k = n j=1 (X -τ j ).
We also denote by H(T ) = max k {|t k |} the height of the polynomial. Our main goal is, given Q[θ], to find an algebraic integer θ in O K that minimizes the height of its minimal polynomial among the algebraic integers such that Q

[θ ] = Q[θ]
. Indeed, a defining polynomial with smaller coefficients allows for more efficient computations in the number field. A particularly relevant fact is that when bounding the norm of algebraic integers expressed as polynomials in θ , the height of the defining polynomial of θ appears in the bound.

Discriminants

In the context of number fields, two important notions of discriminant appear. The discriminant of the defining polynomial T denoted by ∆(T ) and the discriminant of the number field K denoted by ∆ K . These values are related but different in general.

Given an integral basis ω 1 , . . . , ω n of O K , i.e. a Z-basis of the free module O K , the discriminant of K is the determinant † of the n × n matrix M whose entries are M i,j = Tr K/Q (ω i ω j ). Let σ 1 , . . . , σ n denote the complex embeddings of K in C. The discriminant also can be interpreted as the square of the determinant of the matrix B whose entries are B i,j = σ i (ω j ). Indeed, the trace matrix is exactly

M = t B • B.
For a polynomial T = t k X k of degree n, its discriminant is defined as

∆(T ) = (-1) n(n-1) 2 1 t n Res(T, T ),
where Res(T, T ) is the resultant of T and its derivative. Note that, despite the fact that we only consider monic polynomials, we give here the general formula that includes the leading term t n .

The link with the discriminant of the field K comes from the fact that the discriminant of a monic polynomial T corresponds to the discriminant of the suborder † of O K defined by T , i.e. Z[θ] where θ is a root of T . This implies:

∆(T ) = C 2 ∆ K , where C ∈ N is the index of the suborder C = O K : Z[θ] .
Since we desire to find polynomials with a small height that define K, it is useful to find relations between the discriminant ∆(T ) -known up to the C 2 factor -and the height H(T ). A first relation relies on Hadamard's inequality. Indeed, the resultant of T and T can be computed as the determinant of a (2n -1) × (2n -1) matrix whose entries are all bounded by nH(T ) in absolute value. As a consequence:

|∆ K | ≤ |∆(T )| ≤ n √ 2n -1 H(T ) 2n-1 . (2.1)

Mahler measure

The Mahler measure [START_REF] Lehmer | Factorization of certain cyclotomic functions[END_REF][START_REF] Mahler | An application of Jensen's formula to polynomials[END_REF] of a polynomial T , denoted by M (T ), is defined by log M (T ) = 1 0 log |T (e 2iπt )|dt. Thanks to Jensen's formula, it can also be written in the alternative form:

M (T ) = |t n | n j=1 max (1, |τ j |) ,
which is more convenient for our purpose. Again, despite considering monic polynomials, we include t n for the sake of generality.

The link between the Mahler measure and the height of a polynomial is quite tight and can be illustrated by the two following inequalities. First, Mahler shows in [START_REF] Mahler | An application of Jensen's formula to polynomials[END_REF] that for all k ∈ {0, . . . , n}, we have |t k | ≤ n k M (T ) thus:

H(T ) ≤ n n 2 M (T ) ≤ 2 n M (T ) (2.2)
In addition, it is proven in [START_REF] Mignotte | Landau's inequality via Hadmard's[END_REF] that:

M (T ) ≤ n i=0 |t i | 2 1 2 which implies M (T ) ≤ √ n + 1 H(T ). (2.3)
Using the Mahler measure, it is possible to refine the bound on |∆(T )| we derived from Hadamard's inequality (see [START_REF] Mahler | An inequality for the discriminant of a polynomial[END_REF]Theorem 1]) and to obtain:

|∆(T )| ≤ n n M (T ) 2n-2 .
(2.4) † Here, the fact that T is monic is essential. Otherwise, Z[θ] would not be a suborder of O K .

Proposition 2.1. Let T be a monic irreducible polynomial of degree n ≥ 2. Then T defines a number field K whose discriminant ∆ K satisfies

|∆ K | ≤ |∆(T )| ≤ n 2n H(T ) 2n-2 .
Proof. It is an almost direct consequence of combining (2.3) and (2.4) which yields the improved bound for the discriminant. It remains to check the simple fact that:

∀n ∈ N * , (n + 1) n-1 ≤ n n .

Motivations and link with class group computation

Our main motivation for reducing defining polynomials of number fields is to speed up the computations performed to determine class groups. Indeed, in [START_REF] Biasse | Subexponential class group and unit group computation in large degree number fields[END_REF] Biasse and Fieker propose a complexity improvement for class group computation when the number field is defined by a polynomial with small enough coefficients. More precisely, given parameters n 0 , d 0 > 0 and 0 < α < 1 2 , they introduced the classes † C n0,d0,α of number fields

K = Q[θ] = Q[X]/(T ) such that the defining polynomial T ∈ Z[X] of K satisfies n = deg(T ) = n 0 (log |∆ K |) α (1 + o(1)) and d = log H(T ) = d 0 (log |∆ K |) 1-α (1 + o(1)), (3.1)
where ∆ K is the discriminant of K -equivalently, the discriminant of the order O K . For these classes, they state the following theorem: Theorem 3.1 ([2, Theorem 6.2]). Under GRH and smoothness heuristics about ideals, if the number field K is in C n0,d0,α , there exists an L |∆ K | (a, c) algorithm for class group and unit group computation for some c > 0 and a such that 1 -a ≥ α ≥ 1 -2a, a ≥ 1 3 and a ≥ α.

When a number field K is in C n0,d0,α , it is defined by a polynomial T verifying (3.1) so that:

log H(T ) = d 0 n 0 (1 + o(1)) n log |∆ K | i.e. H(T ) = |∆ K | κ n (3.2)
where κ = n 0 d 0 (1 + o(1)) tends to a constant. We know from Proposition 2.1 that the height of T satisfies 1) . This means that the best -i.e. the smallest -we can hope for is κ = 1 2 + o(1). Furthermore, for randomly chosen polynomial we expect to be close to this best case.

H(T ) ≥ n n n-1 |∆ K | 1 2(n-
However, as far as we know, the best theoretical bound on the minimal height of smallest defining polynomials of an arbitrary number field is far from being that good. Indeed, it is known that: Theorem 3.2. Let K be a number field of degree n. There exists θ ∈ O K \ Z whose minimal polynomial P θ satisfies

H(P θ ) ≤ 3 n |∆ K | n n 2n-2 .
Proof. The proof is provided in Appendix A.

In particular, this result allows us to conclude in the case of primitive number fields, i.e. number fields that do not contain non-trivial subfields. In this case, every element of O K \ Z corresponds to a generator of K whose minimal polynomial defines K.

Corollary 3.3. In primitive number fields, there exists a defining polynomial T whose height satisfies

H(T ) ≤ 3 n |∆ K | n n 2n-2 .
Note that this bound is much worse than we would like for our application. Indeed the bound on the height is only about the square root of the discriminant while we would like something of the order of the n-th root of the discriminant. Alternatively, we see that it corresponds to a value κ ≈ n 2 , much larger than the best case κ ≈ 1 2 . For our purpose, it is difficult to directly work with the classes C n0,d0,α . Instead, we introduce a more convenient and more general variation. More precisely, we first introduce slightly modified classes C n0,d0,α satisfying:

n = n 0 log |∆ K | log log |∆ K | α (1 + o(1)) and d = log H(T ) = d 0 (log |∆ K |) 1-α (log log |∆ K |) α (1 + o(1)) .
Introducing powers of log log |∆ K | in this way is more consistent with what is usually done for discrete logarithms computations using index calculus and simplifies the asymptotic analysis of index calculus algorithms. All the theorems of [START_REF] Biasse | Subexponential class group and unit group computation in large degree number fields[END_REF] can be readily adapted to account for this change.

This modification being done, we now generalize the definition to include more number fields. Let n 0 > 1 be a real parameter arbitrarily close to 1, d 0 > 0, α ∈ [0, 1] and γ ∈ [0, 1] such that α + γ ≥ 1, we define D n0,d0,α,γ as the set of all number fields K of discriminant ∆ K that admit a monic defining polynomial T ∈ Z[X] of degree n that satisfies:

1 n 0 log |∆ K | log log |∆ K | α ≤ n ≤ n 0 log |∆ K | log log |∆ K | α and (3.3) d = log H(T ) ≤ d 0 (log |∆ K |) γ (log log |∆ K |) 1-γ .
In addition to the modification between C and C , there are two essential differences between our classes D and the previous classes. First, we have two different exponents α and γ for log |∆ K | in n and d, rather than using γ = 1 -α. Second, instead of having a (1 + o(1)) we introduce inequalities in order to be more precise. We also have the useful property that D n0,d0,α,γ ⊂ D n 0 ,d 0 ,α,γ whenever n 0 ≤ n 0 , d 0 ≤ d 0 and γ ≤ γ .

Thanks to Corollary 3.3, we need only consider classes D n0,d0,α,γ , with γ at most 1. Moreover, the defining polynomials that appear in [START_REF] Biasse | Subexponential class group and unit group computation in large degree number fields[END_REF] essentially correspond to the lower end of the classes D where α + γ = 1. Indeed, considering the modified classes C , we see that every K in C n0,d0,α also belongs to D n0,d0,α,1-α . Thus, our broader definition of the classes include more number fields, not only those whose minimal defining polynomials satisfy α + γ = 1.

Note that, in the context of class group computations, algorithms with complexity higher than

L |∆ K | ( 1
2 ) are not of great interest. As a consequence, since the algorithm we propose is exponential in n, we can restrict ourselves to considering classes with α ≤ 1 2 ≤ γ.

The algorithm of Cohen and Diaz y Diaz for polynomial reduction

To the best of our knowledge, the only previous algorithm for reducing defining polynomials is a folklore algorithm, mentioned in particular by Cohen and Diaz y Diaz in [START_REF] Cohen | A polynomial reduction algorithm[END_REF] and in [14, Chapter V]. In the sequel, we call it the algorithm of Cohen and Diaz y Diaz.

They define the size of a monic degree-n polynomial T = (X -τ j ) as

S(T ) = n j=1 |τ j | 2
and it is the quantity they choose to minimize. Since for all k ∈ {0, . . . , n},

|t n-k | ≤ n k S(T ) n k 2 ,
the size of T is related to the size of max(|t n-k | 2/k ) and hence to the height of the polynomial. Yet this relation is both more complicated and weaker than the inequalities given by (2.2) and (2.3).

The main reason for their choice is that the size is not too hard to minimize. Indeed, computing a polynomial with the smallest size is equivalent to finding T such that the vector formed of its roots has the smallest L 2 -norm. Remembering that this vector belongs to the lattice formed of the embeddings of O K in C n , this can be done using a lattice reduction algorithm. In particular, the LLL algorithm is a good option since it finds a basis of short vectors. However, while it solves the problem for small values of n, when the dimension grows, it is not guaranteed to find the shortest vector. If needed, it is possible to use stronger lattice reduction algorithms such as BKZ whose complexity is exponential in n but remains polynomial in the size of the entries.

Thus, the first step of their method is to compute an integral basis ω 1 , . . . , ω n of O K , so that every integer θ ∈ O K can be expressed as

θ = n i=1 x i ω i ,
where the x i are in Z. Assuming that θ generates K, then its minimal polynomial coincides with its characteristic polynomial

T θ = n j=1 X - n i=1 x i σ j (ω i ) .
This turns the correspondence between algebraic integers of degree n and monic polynomials defining the field K into a correspondence between polynomials and vectors in the lattice of embeddings of O K in C n . This lattice is generated by the n vectors:

Ω i = [σ 1 (ω i ), . . . , σ n (ω i )] . (4.1)
When the field K is imprimitive, care should be taken to avoid polynomials that generate a strict subfield † of K. For an integer θ, the size of its polynomial T θ is given by a positive definite quadratic form in the x i :

S(T θ ) = n j=1 n i=1 x i σ j (ω i ) 2 = i,j n k=1 σ k (ω i )σ k (ω j ) x i x j .
Equivalently, one can remark that the coefficients n k=1 σ k (ω i )σ k (ω j ) are the entries of the Gram matrix of the above lattice. Since lattice reduction, including the LLL algorithm, only requires this Gram matrix as input, one can find a basis of short vectors in Z n corresponding to small values of S(T θ ). Finally, the algorithm of Cohen and Diaz y Diaz selects the best value of θ it can find, breaking ties in any arbitrary manner when several values are equally good.

From an implementation perspective, the lattice generated by vectors Ω i (and/or the Gram matrix of the lattice) cannot be represented exactly. Instead, it is explained in [START_REF] Cohen | A course in computational algebraic number theory[END_REF] that, in general, it should replaced by an approximation with sufficiently high precision. In fact, there is an interesting special case that occurs when K is totally real. In that case, the Gram matrix is integral and the lattice reduction can thus be performed on the exact lattice, represented by its Gram matrix. For the general case, an analysis of the necessary precision is given in [START_REF] Belabas | Topics in computational algebraic number theory[END_REF].

To summarize, the existing algorithm reduces the above lattice in order to find primitive integer of K with smallest size. However, as already noticed by Cohen in [6, Remark Algorithm 4.4.12], having the smallest size does not necessarily imply having the smallest height.

Example 1. To illustrate this fact, here are a few examples of polynomials where the application of the algorithm of Cohen and Diaz y Diaz does not return a smallest-height polynomial:

Minimal-height polynomials

Cohen/Diaz y Diaz output polynomials

x 3 + 6381x 2 + 4378x -1216 x 3 -x 2 -3537064x + 2193757452 x 3 -9681x 2 -5434x -6901 x 3 -31246021x -67226458585 x 3 -6665x 2 -4318x -2977 x 3 + 336681x -419200237 x 3 -6018x 2 -1387x + 6161 x 3 -12073495x -16147208593
Our implementation (see Section 7) certifies that the four polynomials appearing in the table have minimal heights.

An optimal algorithm for NF defining polynomial reduction

We know from Section 3 that existing bounds do not guarantee, for an arbitrary number field, the existence of a defining polynomial with coefficients small enough to allow application of Theorem 3.1. In the present section, we thus aim at the next best thing: given an arbitrary defining polynomial for a number field, try to find a monic polynomial of smallest height that defines the same number field.

Throughout this section, we assume that we are given as input a monic † irreducible polynomial T in and a factorization of the discriminant ∆(T in ) into prime factors. This allows us to precompute the discriminant ∆ K of the number field K defined by T in and an integral basis ω 1 , . . . , ω n of O K using for instance Round 2 algorithm [START_REF] Cohen | A course in computational algebraic number theory[END_REF]Algorithm 6.1.8].

With the motivations of Section 3 in mind, we now wish to find a monic polynomial of smallest height that defines K. Since such a polynomial clearly exists, let T F denote a minimal polynomial ‡ . Let θ F be a root of T F ; since T F is monic, θ F belongs to O K . Thus, we can write T F (X) = (X -σ j (θ F )) . As in the algorithm of Cohen and Diaz y Diaz, we remark that the † If the number field is initially described by a non-monic polynomial, it is possible using a linear change of variables to make it monic. The transformation can increase the height by a large factor, but it is mostly irrelevant for our purpose.

‡ Uniqueness of T F is not guaranteed. Indeed, T F (-X) also defines K and there might be others. However, any of these polynomials achieves our goal and more importantly, the minimal height H(T F ) is well-defined.

vector corresponding to θ F in the lattice associated to O K should be small in a certain sense, since the coefficients of T F , i.e. the symmetric polynomials in the coordinates of the vector are small. However, we need to replace the notion of smallness by something more adapted than the L 2 -norm of the vector. This is precisely the idea behind our algorithm, consider all small enough vectors in the lattice until we find one that defines a minimal polynomial and can prove that this polynomial is indeed of minimal height. In order to do that, let first focus on the target solution T F and the corresponding vector v(θ F ) = [σ 1 (θ F ), . . . , σ n (θ F )] . Remark that if all entries of T F have roughly the same size, then its L 2 -norm is also small. In that case, the algorithm of Cohen and Diaz y Diaz succeeds in finding T F . However, when the sizes of the entries are unbalanced, success is no longer guaranteed. For a more precise analysis, let us introduce a parameter c > 1 whose value is determined later to minimize algorithmic complexity † . Now, consider the vector

[log c |σ 1 (θ F )|, . . . , log c |σ n (θ F )|] that
c b F j -n ≤ M (T F ) ≤ c b F j .
In particular, this guarantees that:

n j=1 b F j ≤ log c M (T F ) + n ≤ log c H(T F ) + 1 2 log c (n + 1) + n, (5.1)
thanks to Equation (2.3).

Given the vector of weights b F , we can introduce a weighted copy of the lattice corresponding to O K in C n . The weighted lattice is generated by the vectors:

Ω i = σ 1 (ω i ) c b F 1 , . . . , σ n (ω i ) c b F n .
In this new lattice, θ F is associated to the vector:

ṽ(θ F ) = σ 1 (θ F ) c b F 1 , . . . , σ n (θ F ) c b F n .
Note that each coordinate of ṽ(θ F ) has norm at most 1 so that its L 2 -norm is bounded by √ n. As in Section 4, we could work with the Gram matrix of the lattice. However, as an alternative, we prefer to replace the lattice in C n by a related lattice ‡ in R n . We assume that the complex embeddings are ordered with r 1 real embeddings first and r 2 pairs of conjugate complex embeddings after that. More precisely, σ i is a real embedding for 1 ≤ i ≤ r 1 and the complex embeddings are related by σ r1+i = σ r1+i+r2 for 1 ≤ i ≤ r 2 . Using a classical idea of replacing pairs of complex numbers by their real and imaginary parts, we obtain a lattice of R n generated by n real vectors: We also remark that, thanks to the factor √ 2, the L 2 -norm of each real vector is identical to the L 2 -norm of the corresponding complex vector. Indeed, the real and imaginary parts are common to the two conjugates embeddings and it is necessary to count their squares twice in the L 2 -norm. † It is done in Appendix C and it turns out that the optimal choice is c = exp(1). ‡ A third option would be to work directly with the complex lattice as explained in [START_REF] Gan | Complex lattice reduction algorithm for low-complexity fulldiversity MIMO detection[END_REF].

Ω R i =[σ1 (
We can also do the same thing for the weighted lattice. First, remark that since σ r1+i = σ r1+i+r2 , we necessarily have b F r1+i = b F r1+i+r2 . As a consequence, only the first r = r 1 + r 2 coefficients of the weight vector b are needed to describe the weighted lattice, which is generated by: .

Ω R i = σ1(ωi) c b F 1 , . . . , σr 1 (ωi) c b F r 1 , √ 2 Re(σr 1 +1(ωi)) c b F r 1 +1 , √ 2
In Ω i , the vector corresponding to the integer θ F has all its entries of individual norm at most 1. Thus its L 2 -norm is bounded by √ n. Due to the equality of the L 2 -norm, this bound also holds in the lattice generated by the Ω R i . As a consequence, our algorithm simply aims at enumerating all the possible weighted lattices and all vectors of L 2 -norm at most √ n in these lattices. However, doing that directly would be sub-optimal, because for any integer θ in O K , we would also consider many shifted copy θ + j with j ∈ Z. To avoid that, we work instead with a lattice projected orthogonally with respect to the vector Ω R 1 to find a candidate θ. Then, finding the best θ + j has a polynomial runtime in n. The resulting algorithm can be described as follows: .

Since the lattice has real entries, algorithmically we replace it by a sufficiently precise fixed point approximation and scale it up to an integer lattice. (b) Project the vectors Ω R i for i ∈ {2, . . . , n} orthogonally with respect to Ω R 1 . (c) Enumerate all vectors of L 2 -norm at most † 1.1 √ n in this projected lattice and for each short vector v ⊥ : (1) Lift v ⊥ to the shortest possible vector v in the full lattice. (This can be done efficiently by using Gauss' algorithm on the two-dimensional lattice spanned by Ω R 1 and an arbitrary lift of v ⊥ .) (2) Reconstruct the corresponding polynomial

T v (X) = r1 j=1 (X -v j ) • r2 j=1 ((X -v r1+2j-1 -i v r1+2j ) • (X -v r1+2j-1 + i v r1+2j )) . (3) If T v is irreducible:
-Find the integer j that minimizes the height of T v (X + j) -Store T v (X + j) if it has the smallest height encountered until this point.

-When memorizing T v (X + j), update Bound to log c H(T v (X + j)) + 1 2 log c (n + 1) + n (iii) Increment k. If k ≤ Bound, goto (ii) else stop. Output: The stored polynomial, whose height is minimal among all the defining polynomials. † With an exact representation of the lattice, it would suffice to enumerate vectors of norm at most √ n. The 1.1 factor comes from the fact that we are dealing with an approximation of the lattice. See the paragraph on precision.

If the a priori bound B F is correct, we know that T F belongs to one of the weighted lattice we have encountered. Thus, the last memorized polynomial is -one of the possible -T F .

Otherwise, if the input bound does not hold, the algorithm asserts this fact.

Finding j. In the algorithm, we need to find the integer j that minimizes the height of T v (X + j). This can be done in polynomial time. Indeed, each coefficient of T v (X + j) (viewed as a polynomial in X) is a polynomial in j. We thus want to minimize (over the integers) the maximum of the absolute values of n polynomials † . This can restated as minimizing the maximum of 2n polynomials: the coefficients and their opposites. This function is a continuous positive piecewise-polynomial real function. The transition from one piece to next necessarily occurs at a root of a difference of two of the 2n polynomials. Thus, there are at most O(n 3 ) pieces. In each piece, it is easy to minimize over the reals and then over the integers by considering the two integers ‡ closest to this real minimum. As a consequence, the best value for j can be found in polynomial time.

Precision. At the beginning of the algorithm, the lattice generated by the vectors Ω R is replaced by a "sufficiently" precise fixed point approximation and then scaled up to an integer lattice. In order to make the description of the algorithm complete, we need to specify the corresponding precision. The key point is that the precision should be high enough to ensure that any short vector of the exact lattice corresponds to a short vector of the approximate lattice. Indeed, we are essentially enumerating all vectors of length bounded by √ n and we want to make sure that none of those can be overlooked. Let v be a vector of norm at most √ n of the exact lattice, we can write:

v = n i=1 ν i Ω R i with integer coeffients ν i .
In order to make sure that the vector of the approximate lattice is also short, i.e. shorter than 1.1

√ n, the precision should be good enough for the sum of products of the coefficients ν i by the approximation error to be smaller than a constant. In particular, it is enough to require that the maximum of the ν i times the approximation error is smaller than 1 10 n . As a consequence, in order to bound the necessary precision, it suffices to upper bound the coefficients ν i . A classical technique to obtain such a bound is to start from a lower bound on the orthogonalized vectors of the initial basis and remark that the coefficients ν i are upper bounded in absolute value by √ n times the inverse of this bound. To obtain a lower bound on a given b * i , we can divide the determinant of the lattice by the norms of all the vectors but the corresponding b i . The determinant of the scaled lattice of iteration k of the algorithm is √ ∆ K c -k . Thanks to Lemma 1.1 of [14, Chapter V], we know that in the basis of the ring of integers of K computed from the input polynomial T , ω i is a polynomial of degree i -1 in the roots of T . Moreover, the coefficients of this polynomial are in the interval [-1, 1]. As a consequence, the norm of b i -the lattice element corresponding to ω i -can be upper bounded by i √ n Z where Z denotes the largest complex modulus among the roots of T . In particular, Z ≤ M (T ).

Putting all this together, we can upper bound the coefficients ν i at iteration k by:

c k M (T ) n 2 n 1.5n ∆ K .
Thus, it suffices to work with a precision k log 2 (c) + n 2 log 2 M (T ) + 1.5n log 2 (n) + log 2 (10n), which is polynomial in the size of the input polynomial. This precision is also sufficient for performing the reconstruction of T v from the complex embeddings, rounding each coefficient to the nearest integer (see [1, Section 3.2] for more details).

Pseudo-canonical polynomial. For some applications, such as the construction of tables of number fields, it is useful to have a canonical polynomial that represents a given number field. In that case, it is not difficult to add in the above algorithm an arbitrary criteria such as lexicographic order on the coefficients to single out one of the possible minimal-height polynomials. Indeed, all of them are encountered during the enumeration.

Complexity analysis

Now we have described our algorithm, in order to understand its algorithmic complexity, we need to count the involved lattices and to study the cost of short vector enumeration in each of those lattices. We restrict ourselves to primitive number fields for this analysis. For imprimitive fields, the algorithm still works but its complexity may be much higher due the possibility of encountering an extremely large number of integral elements that generate subfields when doing the short vector enumerations. We leave as an open problem the adaptation of the techniques used in PARI/GP for the algorithm of Cohen and Diaz y Diaz with imprimitive fields to our method. In the complexity analysis, we ignore † the cost of computing an integral basis for the maximal order of the field K. Recall that according to [6, Section 6.1], the complexity of this step is dominated by the factorization of the discriminant of the input polynomial. Thanks to the NFS factoring algorithm, this can be done in heuristic time L ∆(Tin) 1 3 , 3 64 9 and depending on T in , it may be the most costly part of the complete computation.

Number of lattices

When the input bound B F is incorrect, the number of lattices that are explored is a function on B F . When B F is correct, thanks to the updating of the bound when a new polynomial is found, the number of lattices depends on the highest value of k that is reached and this value is at most log c H(T F ) + 1 2 log c (n + 1) + n according to Equation (5.1). Thus, the exact running time depends on the quality of the output: it is faster to find polynomials with a smaller height.

Let us consider each iteration of the outer loop: for the iteration numbered k, the number of lattices is simply the number of vectors (b 1 , . . . , b n ) ∈ N n that satisfy the two constraints b r1+i = b r1+r2+i and n j=1 b j = k. To obtain an upper bound, we can forget the first constraint ‡ and just count the number of vectors such that n j=1 b j = k. It is a classical combinatorial result that this number is k+n-1 n-1 . Hence, the total number of lattices considered by the algorithm is:

k F k=0 k + n -1 n -1 = k F + n n ≤ (k F + n) n n! , (6.1)
where k F is the value of k in the last iteration, i.e.

k F = min B F , log c H(T F ) + 1 2 log c (n + 1) + n. † The reason for ignoring this step is that it is already required for the class group computation itself. ‡ Note that, for totally real fields the first constraint is always trivially satisfied. Thus, the bound is tight.

Bound on k F and classes D n0,d0,α,γ . Given as input a number field known to be in a class D n0,d0,α,γ , we can simply set the value of B F given to the algorithm to be:

B F = d 0 log c (log |∆ K |) γ (log log |∆ K |) 1-γ .
Moreover, since we are limiting ourselves to the cases α ≤ 1 2 ≤ γ, n (and log c (n + 1)) is negligible compared to B F and thus k F + n = (1 + o(1))B F .

We conclude that the number of lattices in the enumeration is upper bounded by ((1+o(1))B F ) n n!

and thus by L |∆ K | (α, γ n 0 -α n0 ).

Cost of each enumeration

The second analysis treats of the enumeration phase for each weighted lattice. We recall that we are interested in all vectors whose euclidean norm is below √ n. A slight modification from the Kannan's SVP algorithm brings us the enumeration process and all its analysis is detailed in [START_REF] Hanrot | Improved analysis of Kannan's shortest lattice vector algorithm[END_REF]. Note that this cost of enumeration includes the HKZ reduction of the basis. Proof. The proof is a consequence of [START_REF] Hanrot | Improved analysis of Kannan's shortest lattice vector algorithm[END_REF] and is provided in Appendix B. Note that the n o(n) in particular hides a c n term which is considered in Appendix C when optimizing c.

We remark that n

n 2e +o(n) = L |∆ K | (α, α n0 2e ).
Multiplying by the number of lattices, we find that the final complexity can be expressed as

L |∆ K | α, γ n 0 - α n 0 + α n 0 2e ,
which becomes arbitrarily close to L |∆ K | (α, γ -2e-1 2e α) when n 0 is taken close to 1.

Application to class group computation

Let us get back to class group computation. We recall that Biasse and Fieker find a way to bring down the complexity of their algorithm for certain classes of -orders in -number fields. Given a number field K ∈ C n0,d0,α -defined by a polynomial T satisfying (3.1) -they are able to compute the class group and a compact representation of a fundamental system of units of this order in time L |∆ K | (a, c) for 1 3 ≤ a < 1 2 depending on the parameters of the class and c > 0.

We now want to investigate the theoretical impact of using a minimal-height defining polynomial for class group computations. Note that the existence of such a polynomial ensures that K lies in a certain class D n0,d0,α,γ with γ ∈ [1 -α, 1]. If γ reaches the lower bound γ = 1 -α, then K ∈ D n0,d0,α,1-α and we can apply the conditional improvement † of [START_REF] Biasse | Subexponential class group and unit group computation in large degree number fields[END_REF] to this field. Our idea is then to add our algorithm as a precalculation to theirs in order to find the parameters required to fit K in such a class, if possible.

Doing this enables to extend the applicability of the algorithm of Biasse and Fieker to every number field in a class D n0,d0,α,1-α , even if the number field is not initially given by a smallheight defining polynomial. It remains to check that the cost of this precalculation does not faster for finding a first candidate polynomial with small height. However, to find a minimalheight polynomial, smaller values of c are better. This can be seen on the examples given in Table 1.

Example 2. As a first benchmark, we consider the polynomial t 12 + 4t 11 -17t 10 -68t 9 + 108t 8 + 416t 7 -314t 6 -1129t 5 + 358t 4 + 1353t 3 -36t 2 -540t -72 given as an example in [START_REF] Pohst | Computational algebraic number theory[END_REF]Section V.3]. This polynomial is obtained by using the algorithm of Cohen and Diaz y Diaz to a polynomial with huge coefficients; it defines a suborder of index 670150656 of the ring of integers. More precisely, the vector corresponding to the above polynomial appears as the second vector in the reduced basis after LLL reduction. The fourth vector of the same basis yields a better polynomial with smaller height (505) and smaller index (439826112).

With our algorithm , we find an even better polynomial: whose associated order has index 419904 -and whose height is 263. In addition, this polynomial is palindromic and, thus, reveals an underlying symmetry of the corresponding number field which was not apparent from the other defining polynomials.

t
Example 3. To illustrate practically what changes in class group computation, we choose an example having smaller degree and larger coefficients:

x 5 -5843635x 4 + 931633x 2 + 6577x -8570.
Our implementation of the reduction algorithm certifies that this polynomial has minimal height.

If we give it to Magma V2.21-6 in order to compute the class group of the associated number field, it first "reduces" the polynomial as

x 5 -2x 4 -8001397580x 3 -31542753393650x 2 + 3636653302451131875x + 4818547529425280067500 and then finds the class group -assuming GRH -in about 285 seconds, on the laptop we used for all experiments. More precisely, according to the output of its verbose mode, it seems that Magma derives the relations by sieving on different polynomials. Those polynomials appear to be chosen as the minimal polynomials of algebraic integers of the form θ+b c , where θ is the second element of the LLL-reduced integral basis of O K . We reconstructed the "reduced" polynomial from this information. Magma uses 2306 different sieving polynomials: 663 lead to 0 relations, 748 to 1 relation, 498 to 2 relations and 397 to at least 3 relations. None of them produce more than 8 relations.

In Magma V2.19-10, class group computation is not as optimized as in V2.21, but there is no reducing algorithm: Magma directly works with the input polynomial. Thus, we can compare the efficiency of using either of the two polynomials:

-with x 5 -5843635x 4 + 931633x 2 + 6577x -8570, it takes about 140 seconds, -with the "reduced" one, it takes about 3240 seconds. We see that using the old version with a minimal-height polynomial even makes faster than the new version, despite the huge optimization of the class group computation code. For a more detailed comparison, using the best polynomial as input, the old version only sieves on 58 different sieving polynomials and the first already leads to 784 relations.

Note that our implementation in Magma finds this minimal-height polynomial from the "reduced" one in less than 1.5 second. It also certifies that it is indeed of minimum height. Thus, in this practical case, the reduction algorithm takes negligible time and using it as a precomputation can greatly speed up the class group computation.

Example 4. Finally, we run our implementation on sets of number fields stored in the online Class Group Database [START_REF]Class Group Database[END_REF]. For each degree n ∈ {3, 4, 5, 7}, we pick 100 number fields having discriminant about b bits and we try to reduce the polynomial T 0 given in the table. For each degree, we consider two different sizes of discriminants in order to observe how the algorithm behaves as the discriminant grows.

To illustrate the improvement compare to the previously tabulated polynomial, we compute the ratio r = log H(T F ) log H(T0) , T F denoting the output polynomial. Proof. Given the integral basis ω 1 , . . . , ω n of O K produced by the Round 2 algorithm [6, Algorithm 6.1.8], we consider the lattice L generated by (Ω 1 , . . . , Ω n ), where Ω i denotes the vector [σ 1 (ω i ), . . . , σ n (ω i )]. We know that Ω 1 is the all ones vector and that Ω 1 = √ n. In other words, Ω 1 corresponds to the integer 1 in the number field K and it generates the trivial subfield Q. Thus, elements of O K \ Z are in a one-to-one correspondence with lattice vectors not on the line through 0 and Ω 1 -i.e. with vectors that involve at least one of Ω 2 , . . . , Ω n with a non-zero coefficient.

We now consider the lattice L ⊥ spanned by the vectors

Ω ⊥ i = Ω i -k i Ω 1 ,
where k i = <Ω1,Ωi> n so that < Ω 1 , Ω ⊥ i > = 0. Hence, L ⊥ is the orthogonal projection of L with respect to Ω 1 , and its determinant † satisfies det L = Ω 1 det L ⊥ .

In this new lattice L ⊥ , of dimension n -1, Minkowski's theorem implies the existence of an element θ ⊥ of small uniform norm, namely ∃θ ⊥ ∈ L ⊥ s.t. θ ⊥ ∞ ≤ det L ⊥ 1 n-1 . † We recall that the determinant of a lattice L is the absolute value of the determinant of any matrix that defines L and this value is the same for any basis. Note that the preliminary step of computing an HKZ-reduction of the lattice before doing the enumeration does not dominate the complexity of the enumeration itself (see [START_REF] Hanrot | Improved analysis of Kannan's shortest lattice vector algorithm[END_REF]Theorem 2]).

  describes the relative sizes of the coordinates of v(θ F ). Then, round each value up to the smallest possible non negative integer, this gives a vector b F = [b F 1 , . . . , b F n ]. Since T F is monic, by definition, the Mahler measure M (T F ) is the product of the values max(1, |σ i (θ F )|) and we can write the following inequality between M (T F ) and the vector b F :

√ 2 √ 2 √ 2

 222 ωi),...,σr 1 (ωi), Re(σr 1 +1(ωi)), Im(σr 1 +1(ωi)),..., Im(σr 1 +r 2 (ωi))].

Algorithm 1 .

 1 Search for a minimal-height defining polynomial.Input: Integral basis ω 1 , . . . , ω n of O K and a priori bound B F on log c H(T F ). (i) Fix k = 0, let Bound = B F + 1 2 log c (n + 1) + n (ii) For all (b 1 , . . . , b n ) ∈ N n such that b r1+i = b r1+r2+i andn j=1 b j = k: (a) Construct the weighted lattice generated by the vectors: Ω R i = σ1(ωi) c b 1 , . . . ,

Proposition 6 . 1 .

 61 Enumerating all vectors of norm below √ n in one of our weighted lattice can be done in at most Poly (log |∆ K |) • n n 2e +o(n) binary operations.

9 , 1 |I|

 91 Theorem 3] states that for an HKZ-reduced basis, for all subsets I of [1 . . . d], we have: bAs a consequence, in terms of arithmetic operations, enumerating all vectors of L 2 -norm at most λ b 1 costs at most:2 O(d) • √ d d e • λ d .

  12 -14 t 11 + 25 t 10 + 62 t 9 -155 t 8 -50 t 7 + 263 t 6 -50 t 5 -155 t 4 + 62 t 3 + 25 t 2 -14 t + 1,

Table 1 .

 1 Gain in the size of the height after reduction, r = log H(T F ) log H(T0) n log 2 |∆ K | Early abort Proven minimal height c avg. r min r max r avg. time c avg. r min r max r avg. time Theorem. Let K be a number field of degree n. There exists θ ∈ O K \ Z whose minimal polynomial P θ satisfies H(P θ ) ≤ 3 n |∆ K | n

	3	20 40	10 0.652 0.435 0.860 10 0.635 0.381 0.741	7 ms 17 ms	2 3	0.651 0.435 0.860 0.634 0.381 0.736	49 ms 131 ms
	4	25 40	10 0.607 0.393 0.868 10 0.547 0.446 0.806	18 ms 108 ms	2 3	0.604 0.393 0.868 0.544 0.446 0.806	1.0 s 6.6 s
	5	50 80	10 0.724 0.567 0.955 10 0.698 0.555 0.852	109 ms 820 ms	3 4	0.715 0.567 0.955 0.695 0.555 0.852	4.8 s 14.7 s
	7	80 100	20 0.712 0.519 0.970 20 0.700 0.537 0.843	1.7 s 6.3 s	4 -	0.701 0.519 0.970 ---	749 s -
			Appendix A. Proof of Theorem 3.2
					n
					2n-2
						.

† The results of[START_REF] Biasse | Subexponential class group and unit group computation in large degree number fields[END_REF] are slightly more general than what we state, since they consider the computation of class groups for all orders in K. For simplicity, we only look at the maximal order O K .

† This issue is taken care of in practice in PARI/GP by restricting the enumeration in order to avoid elements that only generate subfields. In theory, since they can be an extremely large number of short bad elements, bounding the resulting complexity is difficult.

† Since Tv(X + j) is monic, we do not need to include the coefficient in front of X n in the minimization. ‡ Ignoring the integer values lying outside of the current piece.

† More precisely the adaptation of this improvement to the classes C .

This work has been supported in part by the European Union's H2020 Programme under grant agreement number ICT-644209.

outweigh the global complexity of the rest of the class group computation. We know from Section 6 that our algorithm runs in time L |∆ K | α, O [START_REF] Belabas | Topics in computational algebraic number theory[END_REF] in that case. This never dominates the cost of their class group algorithm, thus we can state that: Theorem 7.1 ([2, Theorem 6.2]). Under GRH and smoothness heuristics about ideals, for every number field K ∈ D n0,d0,α,1-α , there exists an L ∆ K (a, c) algorithm for class group and unit group computation for some c > 0 and a satisfying a ≥ max α, 1-α 2 . Furthermore, our new classes D built from four parameters allow us to generalize the work of Biasse and Fieker to all number fields having α ≤ 1 2 ≤ γ:

Theorem 7.2. Under GRH and smoothness heuristics about ideals, for every number field K ∈ D n0,d0,α,γ , there exists an L ∆ K (a, c) algorithm for class group and unit group computation for some c > 0 and a = max α, γ 2 .

Proof. This is only a generalization of the work of Biasse and Fieker. Their final result mainly depends on [START_REF] Biasse | Subexponential class group and unit group computation in large degree number fields[END_REF]Theorem 3.1]. In fact we need to adapt the bounding of norms in the proof of this theorem to our more general classes. More precisely, we find that: For all number fields K in D n0,d0,α,γ , we can find a B-smooth ideal equivalent to a |∆ K |-ideal a ⊆ O K with a decomposition in degree 1 prime ideals in time L ∆ K | (b, µ) for some µ ≥ 0 where B = L ∆ K | (a, ρ) for some ρ ≥ 0 provided that a and b satisfy:

The proof is the same except that we modify the exponent appearing in the definition of k. The value 1 -β -τ 2 in their proof becomes α + γ -β -τ 2 .

We thus conclude from this theoretical analysis that our algorithm for reducing number field defining polynomial widens the set of number fields whose class group and unit group can be computed with runtime

The experimental results below illustrate that it also offers a good behavior on practical examples.

Experimental results

We implemented a prototype of our algorithm under Magma 2.21-6. The precision and the parameter c are fixed by the user. This slightly differs from the description of Section 5 since our code enumerate all the elements of norm below √ n in each weighted lattice, instead of doing the minimization of the height of T v (X + j). Indeed, with the practical examples we considered, it is faster to proceed in that way. Furthermore, when a polynomial T (better than the input polynomial) is found, our code offers two options. The first is to stop immediately, since it appears that in practice the first polynomial to be found usually has minimal-height. Despite the fact that this early abort does not certify the minimality, it is a good practical option for class group computations. Another approach when a first polynomial is found is to directly increment k to the value log H(T ) + 1 2 log c (n + 1) + n. This skips intermediate computations which are often useless and directly goes to checking that the polynomial T has minimal height.

In our implementation, we do not fix the parameter c to exp(1) as in the asymptotic analysis. Instead, we remark that using a large c allows for smaller values of k and makes the code run Let us denote this vector by

Consider the affine line going through n i=2 t i Ω i and directed by Ω 1 . On this line, there exists a lattice vector θ = n i=1 t i Ω i of minimal length. We know that θ -θ ⊥ = βΩ 1 for a real number β with |β| ≤ 1 2 . As a consequence, θ -θ ⊥ ∞ ≤ 1 2 . This allows us to conclude that

Finally, thanks to the Minkowski's bound, we know that

Then we deduce an upper bound for the height of the minimal polynomial P θ of θ, using (2.2) and M (T ) = max(1, Proof. This is mostly a consequence of the results of [START_REF] Hanrot | Improved analysis of Kannan's shortest lattice vector algorithm[END_REF], which gives a two steps strategy for enumerating the short vectors of a lattice. The first step is to compute an HKZ-reduced basis of the lattice and the second to enumerate the short vectors using this HKZ-reduced basis. Thanks to the high quality of the reduced basis, the enumeration process is greatly speeded up. Note that this second step dominates the complexity of the process.

The complexity of the enumeration process is analyzed in [START_REF] Hanrot | Improved analysis of Kannan's shortest lattice vector algorithm[END_REF]Section 4.1]. Assume that we have a dimension d lattice given by a basis (b 1 , . . . , b d ) with Gram-Schmidt orthogonalization denoted by (b * 1 , . . . , b * d ) and that we wish to enumerate all vectors of L 2 -norm at most A. Then the complexity expressed in number of arithmetic operations is:

In [START_REF] Hanrot | Improved analysis of Kannan's shortest lattice vector algorithm[END_REF], the complexity is then expressed in terms of bit operations for the case of integer lattices given a bound on the larger integers in the lattice basis. In our case, as already explained after Algorithm 1, we work with an integer lattice approximation whose entries have size polynomial in the size of the input polynomial.

Finally, to apply the result in our case, we need to note that whenever we are enumerating on the lattice corresponding to a weight vector (b 1 , . . . , b n ), we know that the weight vector (max(b 1 -1, 0), . . . , max(b n -1, 0)) did not lead to a successful short vector during the enumeration. Thus, due to the primitivity of the field, no vector of L 2 -norm smaller than √ n exists in this lattice. As a consequence, there is no non-zero vector of L 2 -norm smaller than √ n/c in the current lattice. Thus, we are performing enumeration with a ratio factor λ compared to the short vector at most c. We conclude that the cost of enumeration in bit operations is at most:

Note that for the first lattice in the enumeration process, i.e. the Cohen and Diaz y Diaz lattice, it is also directly known that no vectors of L 2 -norm smaller than √ n exist in the lattice.

Appendix C. Optimal choice for c

Once the complexity analysis is done, it remains to more precisely study the dependence on c to minimize the constant term. Assuming that the output polynomial defines a number field K in D n0,d0,α,γ such that γ ≥ α -namely the case of application to class groups -, then the global complexity we found is bounded by


F Hadj-Hassen
email: faouzi.hadj_hassen@mines-paristech.fr

Role of Training in a Modern Mining Policy MINES ParisTech Program

During the last years, the mining sector has seen a greater involvement of the producing States to develop their own resources as well as an opening to domestic and foreign investors as part of a privatization policy. At the same time, the States sought to clarify the legislative and lawful conditions mainly regarding the questions of safety and environment. These major evolutions were particularly sensitive in the mineral producing countries and strongly increased the requests of training.

  Based on the idea that cooperation and training have a special position in its relations with mineral producing countries, France created in 1975 the Center for Advanced Studies of Mineral Resources (CESMAT) to coordinate the actions of training of foreign upper management personnel and to constitute a relation network. Created initially to encourage exchanges among the various sectors of technical mining expertise, CESMAT has constantly kept abreast of international developments and of new problems encountered by the mining industry such as market economies, environment and role of the State. With seven training programs of one year duration and thirty years of experience in providing innovative training based on exchange of experiences between professionals, a network of almost thousand eight hundred former trainees from hundred odd countries was created. Regarding Saudi Arabia, more than thirty geologists and mining engineers, coming from DMMR, SGS and MAADEN, have attained one of the CESMAT trainings. MINES ParisTech (Paris School of Mines), being very active in the CESMAT program, continues to lead its three specialized trainings covering the areas of Technical and Economic Analysis of Mining Operations (CESECO), Geostatistics (CFSG) and Public Administration of Mines (CESAM). It proposes also a catalog of short trainings. At the end of the long session trainings, successful participants are awarded a "Mastère spécialisé®" diploma and/or a national French post-graduate diploma of specialized training of MINES ParisTech.


Florian Le Manach
email: florian.le-manach@math.u-bordeaux.fr

Florian Le

Manach Cyclicity

Cyclicity in weighted ℓ p spaces

Keywords: 2000 Mathematics Subject Classification. primary 43A15; secondary 28A12, 42A38 Cyclicity, weighted p spaces, capacity

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction and main results

For p ≥ 1 and β ∈ R, we define the Banach space

p β (Z) =    u = (u n ) n∈Z ∈ C Z , u p p β = n∈Z |u n | p (1 + |n|) pβ < ∞   
endowed with the norm • p β . Notice that p 0 (Z) is the classical p (Z) space.

In this work, we are going to investigate cyclic vectors for p β (Z) when β ≥ 0. A vector u ∈ p β (Z) is called cyclic in p β (Z) if the linear span of {(u n+k ) n∈Z , k ∈ Z} is dense in p β (Z).

We denote by T the circle R/2πZ. The Fourier transform of u ∈ p (Z) is given by u : t ∈ T → n∈Z u n e int and when u is continuous, we denote by Z( u) the zero set on T of u:

Z( u) = {t ∈ T, u(t) = 0}.
The case β = 0 was already studied by Wiener, Beurling, Salem and Newman. When p = 1 or p = 2, Wiener characterized the cyclic vectors u in p (Z) by the zeros of u, with the following theorem.

Theorem 1.1 ([16]). Let u ∈ p (Z).

(1) If p = 1 then u is cyclic in 1 (Z) if and only if u has no zeros on T. (2) If p = 2 then u is cyclic in 2 (Z) if and only if u is non-zero almost everywhere.

Lev and Olevskii showed that, for 1 < p < 2 the problem of cyclicity in p (Z) is more complicated even for sequences in 1 (Z). The following Theorem of Lev and Olevskii contradicts the Wiener conjecture.

Theorem 1.2 ([8]). If 1 < p < 2, there exist u and v in 1 (Z) such that Z( u) = Z( v), u is not cyclic in p (Z), and v is cyclic in p (Z).

So we can't characterize the cyclicity of u in p (Z) in terms of only Z( u), the zero set of u. However for u ∈ 1 (Z), Beurling, Salem and Newman gave both necessary conditions and sufficient conditions for u to be cyclic in p (Z). These conditions rely on the "size" of the set Z( u) in term of it's h-measure, capacity and Hausdorff dimension.

Given E ⊂ T and h a continuous function, non-decreasing and such that h(0) = 0, we define the h-measure of E by

H h (E) = lim δ→0 inf ∞ i=0 h(|U i |), E ⊂ ∞ i=0 U i , |U i | ≤ δ
where the U i are open intervals of T and where |U i | denotes the length of U i . The Hausdorff dimension of a subset E ⊂ T is given by dim(E) = inf{α ∈ (0, 1), H α (E) = 0} = sup{α ∈ (0, 1), H α (E) = ∞}, where H α = H h for h(t) = t α (see [START_REF] Kahane | Ensembles parfaits et séries trigonométriques[END_REF], pp. 23-30). Let µ be a positive measure on T and α ∈ [0, 1). We define the α-energy of µ by

I α (µ) = n≥1 | µ(n)| 2 (1 + |n|) 1-α .
The α-capacity of a Borel set E is given by C α (E) = 1/inf{I α (µ), µ ∈ M P (E)}, where M P (E) is the set of all probability measures on T which are supported on a compact subset of E. If α = 0, C 0 is called the logarithmic capacity. An important property which connects capacity and Hausdorff dimension is that (see [START_REF] Kahane | Ensembles parfaits et séries trigonométriques[END_REF], p. 34) dim(E) = inf{α ∈ (0, 1), C α (E) = 0} = sup{α ∈ (0, 1), C α (E) > 0}. (1.1) In the following theorem, we summarize the results of Beurling [START_REF] Beurling | On a closure problem[END_REF], Salem [START_REF] Salem | On singular monotonic functions whose spectrum has a given Hausdorff dimension[END_REF] (see also [START_REF] Kahane | Ensembles parfaits et séries trigonométriques[END_REF] pp. 106-110) and Newman [START_REF] Newman | The closure of translates in p[END_REF]. The Hölder conjugate of p = 1 is noted by q = p p-1 .

Theorem 1.3 ([2, 10, 15]). Let 1 ≤ p ≤ 2.

(1) If u ∈ 1 (Z) and dim(Z( u)) < 2/q then u is cyclic in p (Z).

(2) For 2/q < α ≤ 1, there exists

E ⊂ T such that dim(E) = α and every u ∈ 1 (Z) satisfying Z( u) = E is not cyclic in p (Z). (3) There exists E ⊂ T such that dim(E) = 1 and every u ∈ 1 (Z) satisfying Z( u) = E is cyclic in p (Z) for all p > 1.
In this paper we give a generalization of the results of Beurling, Salem and Newman to p β (Z) spaces. When βq > 1, we have an analogue of (1) in Wiener's Theorem 1.1: a vector u ∈ p β (Z) is cyclic if and only if u has no zeros on T. Indeed, p β (Z) is a Banach algebra if and only if βq > 1 (see [START_REF] El-Fallah | Estimates for resolvents in Beurling-Sobolev algebras[END_REF]). When p = 2, Richter, Ross and Sundberg gave a complete characterization of the cyclic vectors u in the weighted harmonic Dirichlet spaces 2 β (Z) by showing the following result:

Theorem 1.4 ([14]). Let 0 < β ≤ 1 2 and u ∈ 1 β (Z) . The vector u is cyclic in 2 β (Z) if and only if C 1-2β (Z( u)) = 0.
Our first main result is the following theorem.

Theorem A. Let 1 < p < 2, β > 0 such that βq ≤ 1. (1) If u ∈ 1 β (Z) and dim(Z( u)) < 2 q (1 -βq) then u is cyclic in p β (Z). (2) If u ∈ 1 β (Z) and dim(Z( u)) > 1 -βq then u is not cyclic in p β (Z). (3) For 2 q (1 -βq) < α ≤ 1, there exists a closed subset E ⊂ T such that dim(E) = α and every u ∈ 1 β (Z) satisfying Z( u) = E is not cyclic in p β (Z). (4) If p = 2k 2k-1 for some k ∈ N * there exists a closed subset E ⊂ T such that dim(E) = 1 -βq and every u ∈ 1 β (Z) satisfying Z( u) = E is cyclic in p β (Z).
Note that in order to prove (2) and (4) we show a stronger result (see Theorem 3.4).

We can summarize Theorem A by the following diagram:

dim(Z( u)) 0 | 2 q (1 -βq) | 1 -βq | 1 | (1) (3) and (4) (2)
The fourth propriety shows that the bound 1 -βq obtained in (2) is optimal in the sense that there is no cyclic vector such that dim(Z( u)) > 1 -qβ, and, we can find some cyclic vector u with dim(Z( u)) = 1 -βq. However this is only proved if p = 2k 2k-1 for some positive integer k. When p is not of this form, for all positive integer k, we still prove similar results but we loose the optimality because we fail to reach the bound 1 -βq.

The "equality case" dim(Z( u)) = 2 q (1 -βq) is not treated by the previous theorem. Newman gave a partial answer to this question when β = 0, by showing that, under some additional conditions on Z( u), dim(Z( u)) = 2 q implies that u is a cyclic vector (see [START_REF] Newman | The closure of translates in p[END_REF]Theorem 1]). We need the notion of strong α-measure, α ∈ (0, 1), to state Newman's Theorem in the equality case. For E a compact subset of T, we note (a k , b k ), k ∈ N its complementary intervals arranged in non-increasing order of lengths and set

r n = 2π - n k=0 (b k -a k ).
(1.2)

We will say that E has strong α-measure 0 if

lim n→∞ r n n 1 α -1 = 0.
Notice that if E has strong α-measure 0 then H α (E) = 0. The converse is true for some particular sets like Cantor sets but in general the converse is false (for some countable sets).

Theorem 1.5. Let 1 < p < 2 and u ∈ 1 (Z).

If Z( u) has strong α-measure 0 where α = 2 q then u is cyclic in p (Z). Moreover, in [START_REF] Newman | The closure of translates in p[END_REF], Newman asked the question :

For u ∈ 1 (Z), does H 2/q (Z( u)) = 0 imply that u is cyclic in p (Z) ?
A positive answer to this question would contain Theorem 1.1 and Theorem 1.3.(1). We are not able to answer this question completely. Nevertheless, we show that if we replace 2/q-measure by h-measure where h(t) = t 2/q ln(1/t) -γ with γ > 2 q then the answer is negative. Moreover we extend Newman's Theorem to p β (Z).

Theorem B. Let 1 < p < 2, β ≥ 0 such that βq < 1.

(1) If u ∈ 1 β (Z) and Z( u) has strong α-measure 0 where α = 2 q (1βq) then u is cyclic in p β (Z).

(2) For every γ > 2 q , there exists a closed subset E ⊂ T such that every u ∈ 1 β (Z) satisfying Z( u) = E is not cyclic in p β (Z) and such that H h (E) = 0 where h(t) = t α ln(e/t) -γ with α = 2 q (1 -βq) Note that the set E constructed in part (2) of Theorem B satisfy dim(E) = 2 q (1 -βq).

Preliminaries and lemmas

Let 1 ≤ p < ∞ and β ∈ R. We denote by D (T) the set of distributions on T and M(T) the set of measures on T. For S ∈ D (T), we denote by S = ( S(n)) n∈Z the sequence of Fourier coefficients of S and we write S = n S(n)e n , where e n (t) = e int . The space A p β (T) will be the set of all distributions S ∈ D (T) such that S belongs to p β (Z). We endow A p β (T) with the norm S A p β (T) = S p β . We will write A p (T) for the space A p 0 (T). Thus the Fourier transformation is an isometric isomorphism between p β (Z) and A p β (T). We prefer to work with A p β (T) rather than p β (Z). In this section we establish some properties of A p β (T) which will be needed to prove Theorems A and B.

For 1 ≤ p < ∞ and β ≥ 0 we define the product of f ∈ A 1 β (T) and S ∈ A p β (T) by

f S = n∈Z ( f * S)(n) e n = n∈Z   k∈Z f (k) S(n -k)   e n ,
and we see that

f S A p β (T) ≤ f A 1 β (T) S A p β (T) . Note that if S ∈ A p
-β (T) we can also define the product f S ∈ A p -β (T) by the same formula and obtain a similar inequality:

f S A p -β (T) ≤ f A 1 β (T) S A p -β (T) .
For p = 1, the dual space of A p β (T) can be identified with A q -β (T) (q = p p-1 ) by the following formula

S, T = n∈Z S(n) T (-n), S ∈ A p β (T), T ∈ A q -β (T).
We denote by P(T) the set of trigonometric polynomials on T. We rewrite the definition of cyclicity in the spaces A p β (T) for β ≥ 0 : S ∈ A p β (T) will be a cyclic vector if the set {P S, P ∈ P(T)} is dense in A p β (T). It's clear that the cyclicity of S in A p β (T) is equivalent to the cyclicity of the sequence S in p β (Z). Moreover for 1 ≤ p < ∞ and β ≥ 0, S is cyclic in A p β (T) if and only if there exists a sequence (P n ) of trigonometric polynomials such that

lim n→∞ 1 -P n S A p β (T) = 0. (2.1)
We need the following lemmas which gives us different inclusions between the

A p β (T) spaces. Lemma 2.1. Let 1 ≤ r, s < ∞ and β, γ ∈ R. (1) If r ≤ s then A r β (T) ⊂ A s γ (T) ⇔ γ ≤ β. (2) If r > s then A r β (T) ⊂ A s γ (T) ⇔ β -γ > 1 s -1 r . Proof. (1) : We suppose that r ≤ s. If γ ≤ β and S ∈ A r β (T), we have n∈Z | S(n)| s (1 + |n|) γs ≤ n∈Z | S(n)| s (1 + |n|) βs . Since • s ≤ • r , we obtain S ∈ A s γ (T) and so A r β (T) ⊂ A s γ (T). Now suppose γ > β. Let S ∈ D (T) be given by S(n)(1 + |n|) β = (1 + m) -2/r if |n| = 2 m 0 otherwise.
Then we have S ∈ A r β (T) \ A s γ (T).

(2) : Now suppose that r > s. If β -γ > 1 s -1 r , we have by Hölder's inequality,

S A s γ (T) ≤ S A r β (T)   n∈Z (1 + |n|) rs r-s (γ-β)   1-s/r , S ∈ A r β (T), so that A r β (T) ⊂ A s γ (T). Now suppose that β -γ < 1 s -1 r . Let ε > 0 such that β -γ + ε < 1 s -1 r , α = -1 s -γ + ε and let S ∈ D (T) be such that S(n) = n α . We have S ∈ A r β (T) \ A s γ (T). For the case β -γ = 1 s -1 r we take S ∈ D (T) such that S(n) r (1 + |n|) βr = 1 (1 + |n|) ln(1 + |n|) 1+ε with ε = r s -1 > 0. We can show that S ∈ A r β (T) \ A s γ (T) which proves that A r β (T) ⊂ A s γ (T).
For E ⊂ T, we denote by A p β (E) the set of S ∈ A p β (T) such that supp(S) ⊂ E, where supp(S) denotes the support of the distribution S. The following lemma is a direct consequence of the definition of capacity (see [START_REF] Kahane | Ensembles parfaits et séries trigonométriques[END_REF]) and the inclusion

A q -β (T) ⊂ A 2 α-1 2 (T) when q ≥ 2 and 0 ≤ α < 2 q (1 -βq). Lemma 2.2. Let E a Borel set, β ≥ 0 and q ≥ 2. If there exists α, 0 ≤ α < 2 q (1 -βq), such that C α (E) = 0 then A q -β (E) = {0}.
We obtain the first results about cyclicity for the spaces A p β (T), when A p β (T) is a Banach algebra. More precisely, we have (see [START_REF] El-Fallah | Estimates for resolvents in Beurling-Sobolev algebras[END_REF])

Proposition 2.3. Let 1 ≤ p < ∞ and β ≥ 0. A p β (T) is a Banach algebra if and only if βq > 1. Moreover when βq > 1, a vector f ∈ A p β (T) is cyclic in A p β (T) if and only if f has no zeros on T. Let f ∈ A 1 β (T) ans S ∈ D (T). We denote by Z(f ) the zero set of the function f . Recall that e n : t → e int . Lemma 2.4. Let 1 ≤ p < ∞ and β ≥ 0. Let f ∈ A 1 β (T) and S ∈ A p -β (T). If for all n ∈ Z, S, e n f = 0 then supp(S) ⊂ Z(f ). Proof. We have S, e n f = f S, e n = 0. Hence f S = 0. Let ϕ ∈ C ∞ (T) such that supp(ϕ) ⊂ T \ Z(f ). We claim that ϕ f ∈ A 1 β (T) ⊂ A q β (T) where q = p p-1 . So we obtain S, ϕ = f S, ϕ f = 0
which proves that supp(S) ⊂ Z(f ). Now we prove the claim. Let ε = min{|f (t)|, t ∈ supp(ϕ)} > 0 and P ∈ P(T) such that f -P A 1 β (T) ≤ ε/3. By the Cauchy-Schwarz and Parseval inequalities, for every g ∈ C 1 (T), we get

g A 1 β (T) ≤ g ∞ + 2 2 -2β 1 -2β g ∞ . (2.2)
Now, as in [START_REF] Newman | A simple proof of Wiener's 1/f theorem[END_REF], by applying (2.2) to ϕ P n we see that

ϕ f = n≥1 ϕ (P -f ) n-1 P n ∈ A 1 β (T),
which finishes the proof.

Proposition 2.5. Let 1 ≤ p < ∞ and f ∈ A 1 β (T) with β ≥ 0. We have (1) If f is not cyclic in A p β (T) then there exists S ∈ A q -β (T) \ {0} such that supp(S) ⊂ Z(f ). (2) If there exists a nonzero measure µ ∈ A q -β (T) such that supp(µ) ⊂ Z(f ) then f is not cyclic in A p β (T). Proof. (1) If f is not cyclic in A p β (T), by duality there exists S ∈ A q -β (T) \ {0} such that S, e n f = 0, ∀n ∈ Z.
Thus, by lemma 2.4, we have supp(S) ⊂ Z(f ).

(

) Let µ ∈ A q (T) ∩ M(T) \ {0} such that supp(µ) ⊂ Z(f ). Since µ is a measure on T we have µ, e n f = 0, for all n ∈ Z. So f is not cyclic in A p β (T). Recall that A 1 β (T) is a Banach algebra. Let I be a closed ideal in A 1 β (T) 2
. We denote by Z I the set of common zeros of the functions of I,

Z I = f ∈I Z(f ).
We have the following result about spectral synthesis in A 1 β (T). Lemma 2.6. Let 0 ≤ β < 1/2. Let I be a closed ideal in A 1 β (T). If g is a Lipschitz function which vanishes on Z I then g ∈ I.

Proof. The proof is similar to the one given in [START_REF] Kahane | Ensembles parfaits et séries trigonométriques[END_REF] pp. 121-123. For the sake of completeness we give the important steps. Let I ⊥ be the set of all S in the dual space of A 1 β (T) satisfying S, f = 0 for all f ∈ I. Let g be a Lipschitz function which vanishes on Z I and S ∈ I ⊥ . By Lemma 2.4, supp(S) ⊂ Z I . For h > 0, we set

S h = S * ∆ h where ∆ h : t → -|t| h 2 + 1 h if t ∈ [-h, h] and 0 otherwise. We have ∆ h (0) = 1/2π and ∆ h (n) = 1 2π 4 sin(nh/2) 2 (nh) 2 for n = 0. Since S is in the dual of A 1 β (T), S h ∈ A 1 (T). Moreover we have supp(S h ) ⊂ supp(S) + supp(∆ h ) ⊂ Z h I := Z I + [-h, h]. We have | S h , g | 2 = Z h I \Z(g) S h (x)g(x)dx 2 ≤   n∈Z | S(n) ∆ h (n)| 2   Z h I \Z(g) |g(x)| 2 dx ≤ C   n∈Z S(n) 2 n 2   |Z h I \ Z(g)|
where C is a positive constant and where |E| denotes the Lebesgue measure of E. So lim h→0 S h , g = 0. By the dominated convergence theorem, we obtain that

lim h→0 S h , g = lim h→0 n∈Z S h (n) g(-n) = 1 2π n∈Z S(n) g(-n) = 1 2π S, g .
So S, g = 0. Therefore g ∈ I.

We also need the following lemma which is a consequence of Lemma 2.6. Newman gave a proof of this when β = 0 (see [START_REF] Newman | The closure of translates in p[END_REF]Lemma 2]).

Lemma 2.7. Let 0 ≤ β < 1/2 and a closed set E ⊂ T. There exists (f n ) a sequence of Lipschitz functions which are zero on E and such that

lim n→∞ f n -1 A p β (T) = 0 if and only if every f ∈ A 1 β (T) satisfying Z(f ) = E is cyclic in A p β (T).

Proof of Theorem A

Before proving Theorem A, let us recall Salem's Theorem (see [START_REF] Salem | On singular monotonic functions whose spectrum has a given Hausdorff dimension[END_REF] and [START_REF] Kahane | Ensembles parfaits et séries trigonométriques[END_REF] pp. 106-110).

Theorem 3.1. Let 0 < α < 1 and q > 2 α . There exists a compact set E ⊂ T which satisfies dim(E) = α and there exists a positive measure µ ∈ A q (T) \ {0} such that supp(µ) ⊂ E.

To prove Theorem A, we also need the following result. The case β = 0 was considered by Newman in [START_REF] Newman | The closure of translates in p[END_REF]. For k ∈ N and E ⊂ T, we denote

k × E = E + E + ... + E = k n=1 x n , x n ∈ E . Theorem 3.2. Let 1 < p < 2 and β > 0 such that βq ≤ 1, and let f ∈ A 1 β (T). (a) Let k ∈ N * be such that k ≤ q/2. If C α (k × Z(f )) = 0 for some α < 2 q (1 -βq)k, then f is cyclic in A p β (T). (b) Let k ∈ N * be such that q/2 ≤ k ≤ 1/(2β). If C α (k × Z(f )) = 0 where α = 1 -2kβ, then f is cyclic in A p β (T). Proof. Let k ∈ N * . Suppose that f is not cyclic in A p β (T)
. Then there exists L ∈ A q -β (T), the dual of A p β (T), such that L(1) = 1 and L(P f ) = 0, for all P ∈ P(T).

Since β < 1 2 , by (2.2), we get C 1 (T) ⊂ A 1 β (T) ⊂ A p β (T), and by [START_REF] Newman | Some results in spectral synthesis[END_REF] (see also [START_REF] Newman | The closure of translates in p[END_REF]Lemma 5]), there exists φ ∈ L 2 (T) such that

L(g) = T g (x)φ(x) + g(x) dx, ∀g ∈ C 1 (T).
Since L ∈ A q -β (T) which implies (L(e n )) n∈Z ∈ q -β (Z), we obtain

n∈Z |n φ(n)| q (1 + |n|) -βq < ∞. (3.1)
Moreover we have,

T (e n f ) (x)φ(x) + (e n f )(x) dx = 0, n ∈ Z,
and so φ -1, e n f = 0 where φ is defined in terms of distribution. By (3.1), φ -1 ∈ A q -β (T), so by lemma 2.4, we get supp(φ -1) ⊂ Z(f ). For m ∈ N, we denote by φ * m the result of convolving φ with itself m times. Using the fact that S * T = S * T and 1 * S = 0 for any distributions S and T , we have

(φ -1) * φ * (m-1) (m-1) + (-1) m-1 = (φ * m ) (m) + (-1) m .
So we can show by induction on m ≥ 1 and by the formula supp(T * S) ⊂ supp(T ) + supp(S) that

supp (φ * m ) (m) + (-1) m ⊂ m × Z(f ), ∀m ≥ 1. (3.2) Note that (φ * k ) (k) (n) = i k n k φ(n) k for k ≥ 1 and n ∈ Z.
(a) : Suppose that 0 < k ≤ q/2 and C α (k × Z(f )) = 0 for some α < 2 q (1 -βq)k. We rewrite (3.1) as

n∈Z |n φ(n)| k q k (1 + |n|) -q k βk < ∞.
So, if we set q = q k ≥ 2 and β = βk, we have φ * k (k) ∈ A q -β (T). By (3.2) and by Lemma 2.2 we obtain that φ * k (k) = (-1) k-1 . This contradicts the fact that (φ * k ) (k) (0) = 0.

(b) : Now suppose that k ≥ q/2 and C α (k × Z(f )) = 0 where α = 1 -2kβ. Since q ≤ 2k, we have by (3.1),

n∈Z |n φ(n)| 2k (1 + |n|) -2kβ < ∞. So φ * k (k) ∈ A 2 -kβ (T) and φ * k (k) = (-1) k-1 . Again this is absurd since (φ * k ) (k) (0) = 0.
We need to compute the capacity of the Minkowski sum of some Cantor type subset of T. We denote by [x] the integer part of x ∈ R. For λ ∈ [0, 1] and k ∈ N * , we define

K k λ = {m ∈ N, ∃j ∈ N, m ∈ [2 j , 2 j (1 + λ + 1/j) -k + 1]} and we set in R/Z [0, 1[, S k λ = x = ∞ i=0 x i 2 i+1 , (x i ) ∈ {0, 1} N such that i ∈ K k λ ⇒ x i = 0 .
We denote K λ = K 1 λ and S λ = S 1 λ . To prove (4) of Theorem A we need the following lemma.

Lemma 3.3. For all

k ≥ 1, we have (1) k × S λ ⊂ S k λ ; (2) C α (S k λ ) = 0 if and only if α ≥ 1-λ 1+λ ; (3) dim(k × S λ ) = 1-λ 1+λ and C1-λ 1+λ (k × S λ ) = 0.
Proof. (1) : We prove this by induction. If k = 1 we have S λ = S 1 λ . We suppose the result true for k -1 for some k ≥ 2 and we will show

k × S λ ⊂ S k λ . We have k × S λ ⊂ (k -1) × S λ + S λ ⊂ S k-1 λ + S λ . Let x ∈ S k-1
λ , y ∈ S λ and z = x + y. Denote by (x i ), (y i ) and (z i ) their binary decomposition. Let m ∈ K k λ . There exists

j ∈ N such that m ∈ [2 j , 2 j (1 + λ + 1/j) -k + 1]. Since m ∈ K k λ , m and m + 1 are contained in K k-1 λ ⊂ K λ , we have x m = y m = x m+1 = y m+1 = 0. Therefore we write z = x + y = m-1 i=0 x i + y i 2 i+1 + ∞ i=m+2 x i + y i 2 i+1 .
Note that for infinitely many i ≥ m + 2, x i + y i < 2, so we see that

∞ i=m+2 x i + y i 2 i+1 < 1 2 m+1 .
Therefore, we obtain by uniqueness of the decomposition that z m = 0. This proves that x + y ∈ S k λ and k × S λ ⊂ S k λ .

(2) : We will study the capacity of S k λ by decomposing it. First we show that the set S k λ is a generalized Cantor set in the sense of [START_REF] Ya | Capacities of Generalized Cantor Sets[END_REF][START_REF] Ohtsuka | Capacité d'ensembles de Cantor généralisés[END_REF].

Let ν j = [2 j (1 + λ + 1/j) -k + 1] + 1 and N 0 (depending only on k and λ) such that for all j ≥ N 0 , 2 j < ν j < 2 j+1 . We set for N ≥ N 0 ,

l N = ∞ j=N 1 2 ν j - 1 2 2 j+1 . Since 2 j (1 + λ + 1/j) -k + 1 < ν j ≤ 2 j (1 + λ + 1/j) -k + 2, we have ∞ j=N 1 2 2 j (1+λ+ 1 j ) 1 2 2-k - 1 2 2 j (1-λ-1 j ) ≤ l N ≤ ∞ j=N 1 2 2 j (1+λ+ 1 j ) 1 2 1-k - 1 2 2 j (1-λ-1 j )
On one hand, there exists C ≥ 1 such that for all j ≥ N ,

1 C ≤ 1 2 2-k - 1 2 2 j (1-λ-1 j ) ≤ 1 2 1-k - 1 2 2 j (1-λ-1 j ) ≤ C. On the other hand, for N ≥ N 0 , 1 2 2 N (1+λ+ 1 N ) ≤ ∞ j=N 1 2 2 j (1+λ+ 1 j ) ≤ 1 2 2 N (1+λ+ 1 N ) + ∞ j=0 1 2 2 N +1 (1+λ) 2 j ≤ 1 2 2 N (1+λ+ 1 N ) + ∞ j=0 1 2 2 N +1 (1+λ) j+1 ≤ 1 2 2 N (1+λ+ 1 N ) + 2 2 2 N +1 (1+λ) ≤ 3 2 2 N (1+λ+ 1 N ) .
Hence we obtain that l N is comparable to 2 -2 N (1+λ+1/N ) , that is:

1

C2 2 N (1+λ+ 1 N ) ≤ l N ≤ 3C 2 2 N (1+λ+ 1 N ) . (3.3)
Moreover we have

l N = 1 2 ν N - ∞ j=N +1 1 2 2 j - 1 2 ν j < 1 2 ν N ≤ 1 2 2 N . (3.4)
We set

E N =    2 N -1 i=0 x i 2 i+1 + l N z, z ∈ [0, 1], x i ∈ {0, 1}, i ∈ K k λ ⇒ x i = 0    .
We can see E N as a union of disjoint intervals by writing

E N = (x i )∈{0,1} 2 N i∈K k λ ⇒x i =0 E (x i ) N ,
where

E (x i ) N = 2 N -1 i=0 x i 2 i+1 + l N [0, 1].
Note that the intervals E

(x i ) N are disjoint since by (3.4), l N < 1 2 2 N . For fixed N ≥ N 0 , let (x i ) 0≤i≤2 N -1 ∈ {0, 1} 2 N and (y i ) 0≤i≤2 N +1 -1 ∈ {0, 1} 2 N +1 . Claim : E (y i ) N +1 ⊂ E (x i ) N if and only if x i = y i for all 0 ≤ i < 2 N and y i = 0 for all 2 N ≤ i < ν N . Indeed, suppose that E (y i ) N +1 ⊂ E (x i ) N and let u ∈ E (y i ) N +1 . We have u = 2 N -1 i=0 x i 2 i+1 + l N z 1 = 2 N +1 -1 i=0 y i 2 i+1 + l N +1 z 2 ,
where z 1 and z 2 are in [0, 1]. By (3.4), l N < 1 2 ν N , and using the uniqueness of the binary representation, we obtain x i = y i for all 0 ≤ i < 2 N and y i = 0 for all 2 N ≤ i < ν N . Now suppose x i = y i for all 0 ≤ i < 2 N and y i = 0 for all 2

N ≤ i < ν N . Let u ∈ E (y i ) N +1 . We write u = 2 N -1 i=0 x i 2 i+1 + 2 N +1 -1 i=ν N y i 2 i+1 + l N +1 z, where z ∈ [0, 1]. Note that 2 N +1 -1 i=ν N 1 2 i+1 + l N +1 = 1 2 ν N - 1 2 2 N +1 + l N +1 = l N . (3.5)
So we have

2 N -1 i=0 x i 2 i+1 ≤ 2 N -1 i=0 x i 2 i+1 + 2 N +1 -1 i=Z N y i 2 i+1 + l N +1 z ≤ 1 2 2 N -1 i=0 x i 2 i + l N ,
and u ∈ E

(x i )
N . This conclude the proof of the claim.

By the claim, for fixed (x i ) and for N ≥ N 0 , we have the following properties :

(i) the interval E

(x i ) N contains precisely p N = #{(y i ) ν N ≤i≤2 N +1 -1 : y i ∈ {0, 1}} = 2 2 N +1 -ν N intervals of the form E (y i ) N +1 , (ii) the intervals of the form E (y i ) N +1 contained in E (x i ) N
are equidistant intervals of length l N +1 : the distance of two consecutive intervals of the form E

(y i ) N +1 is equal to 1 2 2 N +1 -l N +1 , (iii) if we denote E (x i ) N = [a, b] then there exist (y i ) and (z i ) such that E (y i ) N +1 = [a, a + l N +1 ] and E (z i ) N +1 = [b -l N +1 , b]. Finally we can write S k λ as S k λ = N ≥N 0 E N .
This shows that S k λ is a generalized Cantor set in the sense of [START_REF] Ya | Capacities of Generalized Cantor Sets[END_REF][START_REF] Ohtsuka | Capacité d'ensembles de Cantor généralisés[END_REF]. So, by [START_REF] Ya | Capacities of Generalized Cantor Sets[END_REF][START_REF] Ohtsuka | Capacité d'ensembles de Cantor généralisés[END_REF], we have for 0

< α < 1 that C α (S k λ ) = 0 if and only if ∞ N =N 0 1 (p N 0 • • • p N -1 )l α N = ∞. Since 2 (k-2)(N -N 0 )+(2 N -2 N 0 )(1-λ)-σ N ≤ p N 0 • • • p N -1 ≤ 2 (k-1)(N -N 0 )+(2 N -2 N 0 )(1-λ)-σ N ,
where

σ N = N -1 j=N 0 2 j j ,
we have, by

(3.3), C α (S k λ ) = 0 if and only if ∞ N =N 0 2 2 N (α(1+λ)-(1-λ))+α2 N /N +σ N -(k-1)(N -N 0 )+2 N 0 (1-λ) = ∞. Therefore C α (S k λ ) = 0 if and only if α ≥ 1-λ 1+λ .
(3) immediately follows from ( 1) and ( 2) by the capacity property (1.1).

We are ready to prove Theorem A. The following Theorem is a reformulation of Theorem A in A p β (T) spaces. Theorem 3.4. Let 1 < p < 2, β > 0 such that βq ≤ 1.

(1

) If f ∈ A 1 β (T) and dim(Z(f )) < 2 q (1 -βq) then f is cyclic in A p β (T). (2) If f ∈ A 1 β (T) and C 1-βq (Z(f )) > 0 then f is not cyclic in A p β (T). (3) For 2 q (1 -βq) < α ≤ 1, there exists a closed set E ⊂ T such that dim(E) = α and every f ∈ A 1 β (T) satisfying Z(f ) = E is not cyclic in A p β (T). (4) Let k = [q/2]. For all ε > 0, there exists a closed set E ⊂ T such that dim(E) ≥ max 2 q (1 -βq)k -ε, 1 -2(k + 1)β
and such that every

f ∈ A 1 β (T) satisfying Z(f ) = E is cyclic in A p β (T). Furthermore, if p = 2k 2k-1 for some k ∈ N * , E can be chosen such that dim(E) = 1 -βq. Proof. (1) : Note that, by (1.1), dim(Z(f )) < 2 q (1 -βq) if and only if there exists α < 2 q (1 -βq) such that C α (Z(f )) = 0. If C α (Z(f )) = 0, by Lemma 2.2, there is no S ∈ A q -β (T) \ {0} such that supp(S) ⊂ Z(f ) . So, by Proposition 2.5 (1), f is cyclic in A p β (T).
(2) : Suppose that C 1-βq (Z(f )) > 0. There exists a probability measure µ of energy

I 1-βq (µ) < ∞, such that supp(µ) ⊂ Z(f ) . So µ ∈ A 2 -βq/2 (T) \ {0}. Since | µ(n)| ≤ 1
for all n ∈ Z and q ≥ 2, we have µ ∈ A q -β (T). By proposition 2.5 (2), f is not cyclic in A p β (T).

(3) : Let 2 q (1-βq) < α ≤ 1. There exists ε > 0 such that 2 q (1-βq)+ε < α. Let q such that 2 q -2β + ε = 2 q . Since β > 1 q -1 q , by Lemma 2.1, A q (T) ⊂ A q -β (T). By Theorem 3.1, as q satisfies q > 2 α , there exists a closed subset E ⊂ T such that dim(E) = α and a non zero positive measure µ ∈ A q (T)

⊂ A q -β (T) such that supp(µ) ⊂ E. Now (3) follows from proposition 2.5.(2). ( 4
) : Let k = [q/2]. Suppose first 2 q (1 -βq)k > 1 -2(k + 1)β and let 0 < ε < ε satisfying 1 -2(k + 1)β ≤ 2 q (1 -βq)k -ε . Consider the set S λ where λ verifies 2 q (1 -βq)k -ε < 1 -λ 1 + λ < 2 q (1 -βq)k. By Lemma 3.3.(3) we have dim(S λ ) = 1-λ 1+λ and C1-λ 1+λ (k × S λ ) = 0. Therefore by Theorem 3.2.(a), every f ∈ A 1 β (T) such that Z(f ) = S λ is cyclic in A p β (T). Now suppose 2 q (1 -βq)k ≤ 1 -2(k +
f ∈ A 1 β (T) such that Z(f ) = S λ is cyclic in A p β (T).
Suppose now that p = 2k 2k-1 for some k ∈ N * . As before, we consider S λ where 1-λ 1+λ = 1 -2kβ = 1 -βq. So again by Theorem 3.2.(b), every

f ∈ A 1 β (T) such that Z(f ) = S λ is cyclic in A p β (T).
Note that the set E which is considered in 3.4.( 4) verifies C α (E) = 0 where

α ≥ max 2 q (1 -βq)k -ε, 1 -2(k + 1)β .

Proof of Theorem B

In this section we investigate the sharpness of the constant 2 q (1 -βq) in Theorem A.

Before proving Theorem B, we need the following two results. The following Lemma is an extension of Newman's Lemma 3 (see [START_REF] Newman | The closure of translates in p[END_REF] pp 654-655).

f A p β (T) ≤ C 1 p f 3 2 -1 p -β A 2 (T) ( f A 2 (T) + f A 2 (T) ) 1 p -1 2 +β .
Proof. It suffices to show that there exists C > 0 such that for all sequences (c n )

∈ C N * , ∞ n=1 |c n | p (1 + |n|) pβ ≤ C ∞ n=1 |c n | 2 3 4 p-1 2 -βp 2 ∞ n=1 n 2 |c n | 2 1 2 -p 4 + βp 2 .
Then we apply this inequality to (

f (n)) n≥1 and ( f (-n)) n≥1 . Let x 2 = n≥1 |c n | 2 and x 2 y 2 = n≥1 n 2 |c n | 2 .
Note that y ≥ 1. On one hand, by the Hölder inequality,

1≤n≤y |c n | p (1 + n) pβ ≤ y n=1 |c n | 2 p/2 y n=1 (1 + n) 2pβ 2-p 1-p/2 ≤ x 2 p 2 y(1 + y) 2pβ 2-p 1-p 2 ≤ 2 βp x p y 1-p 2 +pβ .
On the other hand we set γ = 2p(1-β) 2-p . Since βq ≤ 1, γ > 1 and again by the Hölder inequality we obtain,

n>y |c n | p (1 + n) pβ ≤ 2 p   ∞ n>y n 2 |c n | 2   p 2   ∞ n>y (1 + n) 2p(β-1) 2-p   1-p 2 ≤ 2 p x 2 y 2 p 2 1 γ -1 1-p/2 y 1-γ 1-p 2 ≤ 2 p 1 γ -1 1-p/2 x p y 1-p 2 +pβ
So the conclusion of the Lemma holds with

C = max   2 βp , 2 p 1 γ -1 1-p/2  
which is a positive constant depending only on p and β.

The following theorem is due to Körner (see [START_REF] Körner | On the theorem of ivašev-musatov iii[END_REF]Theorem 1.2]).

Theorem 4.2. Let

h : [0, ∞) → [0, ∞) be an increasing continuous function with h(0) = 0 and let φ : [0, ∞) → [0, ∞) be a decreasing function. Suppose that (1) ∞ 1 φ(x) 2 dx = ∞; (2) there exist K 1 , K 2 > 1 such that for all 1 ≤ x ≤ y ≤ 2x, K 1 φ(2x) ≤ φ(x) ≤ K 2 φ(y);
(3) there exists γ > 0 such that

lim x→∞ x 1-γ φ(x) = ∞;
(4) there exist 0 < K 2 < K 3 < 1 such that for all t > 0,

K 2 h(2t) ≤ h(t) ≤ K 3 h(2t).
Then there exists a probability measure µ with support of Hausdorff h-measure zero such that

| µ(n)| ≤ φ 1 h(|n| -1 ) ln 1 h(|n| -1 ) 1/2 , ∀n = 0.
Recall Theorem B reformulated in A p β (T) space. Theorem 4.3. Let 1 < p < 2 and β ≥ 0 such that βq < 1.

(1) If f ∈ A 1 β (T) and Z(f ) has strong α-measure 0 where α = 2 q (1 -βq) then f is cyclic in A p β (T).

(2) For every γ > 2 q , there exists a closed subset E ⊂ T such that every

f ∈ A 1 β (T) satisfying Z(f ) = E is not cyclic in A p β (T) and such that H h (E) = 0 where h(t) = t α ln(e/t) γ with α = 2 q (1 -βq). Note that in (2), H h is closed to H α .
Proof. (1) : The proof of this result holds by using arguments analogous to those of Newman for β = 0 (see [START_REF] Newman | The closure of translates in p[END_REF]Theorem 1]). Denote by (a k , b k ) the complementary intervals of Z(f ) arranged in non-increasing order of lengths and set

r n = 2π - n k=0 (b k -a k ).
The set Z(f ) has strong α-measure 0 where α = 2 q (1 -βq) so lim

n→∞ r n n 1 α -1 = 0.
Let ε > 0 and n ∈ N such that r n < εn 1-1 α and εn -1 α < 1. Let the function ψ be given by

ψ(x) = max 1 - n 1 α ε ρ(x), 0 , x ∈ T, where
ρ(x) = dist x, T \ n k=1 ]a k , b k [ . Then ψ 2 A 2 (T) = T\ n k=1 ]a k ,b k [ ψ(t) 2 dt + n k=1 b k a k ψ(t) 2 χ {ρ(x)≤εn -1 α } (t) dt ≤ r n + n k=1 2εn -1 α ≤ 3εn 1-1 α . Moreover ψ 2 A 2 (T) = T ψ (t) 2 dt = n k=1 b k a k ψ (t) 2 χ {ρ(x)≤εn -1 α } (t) dt ≤ n k=1   n 1 α ε   2 2εn -1 α ≤ 2 n 1+ 1 α ε . Since εn -1 α < n 1 α ε and α = 2 q (1 -βq), by Lemma 4.1, ψ A p β (T) ≤ C 1 p 3εn 1-1 α 3 4 -1 2p -β 2   5 n 1+ 1 α ε   1 2p -1 4 + β 2 ≤ C ε 1-1 p -β
where C and C depend only on β and p. Note that 1 -ψ is a Lipschitz function and Z(f ) ⊂ Z(1 -ψ). We conclude by Lemma 2.7.

(2) : Let α = 2 q (1 -βq) and γ > 2 q . By Theorem 4.2 with φ(t) = (t ln(et)) -1/2 for t ≥ 1 and h(t) = t α ln(e/t) γ for t ∈ [0, ∞), there exists a probability measure µ with support of Hausdorff h-measure zero such that

| µ(n)| ≤ φ 1 h(|n| -1 ) ln 1 h(|n| -1 ) 1/2 ≤ (|n| α ln(e|n|) γ ) -1/2 , for n = 0. So n =0 | µ(n)| q (1 + |n|) -βq ≤ C n =0 |n| -αq/2-βq ln(e|n|) -γq/2 ≤ C n =0 1 |n| ln(e|n|) γq/2 < ∞ with C a positive constant. Hence µ ∈ A q -β (T).
We set E = supp(µ). By lemma 2.5 the result is proved.

Remarks

We say that (ω n ) ∈ R Z is a weight if w n ≥ 1 and ω n+k ≤ Cω n ω k for all k, n ∈ Z and C a positive constant. For ω a weight and 1 ≤ p < ∞ we set (1) If f ∈ A 1 ω (T) and dim(Z(f )) < 2 q then f is cyclic in A p ω (T).

A p ω (T) =    f ∈ C(T), f p A p ω (T) = n∈Z | f (n)| p ω p n < ∞    . Note that f S A p ω (T) ≤ f A 1 ω (T) S A p ω (T) for f ∈ A 1 ω (T)
(2) For 2 q < α ≤ 1, there exists a closed subset E ⊂ T such that dim(E) = α and every f ∈ A 1 ω (T) satisfying Z(f ) = E is not cyclic in A p ω (T).

(3) For all 0 < ε < 1, there exists a closed subset E ⊂ T such that dim(E) = 1 -ε and every f ∈ A 1 ω (T) satisfying Z(f ) = E is cyclic in A p ω (T). Proof. (1) : Let f ∈ A 1 ω (T) such that dim(Z(f )) < 2 q . There exists 0 < δ < 1/2 such that dim(Z(f )) < 2 q (1 -δq). By Theorem 3. 2)), there exists a closed set E ⊂ T such that dim(E) = α and every f ∈ A 1 (T) satisfying Z(f ) = E is not cyclic in A p (T). Let f ∈ A 1 ω (T) such that Z(f ) = E . Since f ∈ A 1 (T), f is not cyclic in A p (T). However • A p (T) ≤ • A p ω (T) therefore f is not cyclic in A p ω (T). (3) : Let 0 < ε < 1 and β > 0 such that 1 -2([q/2] + 1)β ≥ 1 -ε. By Theorem 3.4.( 4), there exists a closed set E ⊂ T such that dim(E) ≥ 1 -2([q/2] + 1)β ≥ 1 -ε and such that every f ∈ A 1 β (T) satisfying Z(f ) = E is cyclic in A p β (T). Since A p β (T) ⊂ A p ω (T), we obtain, by Lemma 2.7, that every f ∈ A 1 ω (T) satisfying Z(f ) = E is cyclic in A p ω (T).

When p > 2 the search for cyclic vectors in A p (T) seems extremely difficult. Newman in [START_REF] Newman | The closure of translates in p[END_REF] shows that for all α < 2π there exists E ⊂ T which has a Lebesgue measure |E| > α and such that every f ∈ A 1 (T) satisfying Z(f ) = E is cyclic in A p (T). See also [START_REF] Newman | The closure of translates in p[END_REF]Theorem 6] for the existence of non cyclic functions under some conditions. We also have a characterization of the cyclic vectors in term of the zeros of the Fourier transform when p > 2 but it's not very effective : A function f ∈ A 1 (T) is cyclic in A p (T) if and only if Z(f ) does not support any non-zero function g ∈ A q (T) where q = p p-1 .

When ω n = log(e + |n|) β where 0 < β < 1, for all p > 2 1-β and for all α < 2π, Nikolskii shows in [START_REF] Nikolskii | Lectures on the shift operator IV[END_REF]Corollary 6], there exists E ⊂ T which has a Lebesgue measure |E| > α and such that every f ∈ A 1 β (T) satisfying Z(f ) = E is cyclic in A p β (T).

  1)β. We consider S λ where 1-λ 1+λ = 1 -2(k + 1)β. By lemma 3.3.(3) we have dim(S λ ) = 1-λ 1+λ = 1 -2(k + 1)β and C1-λ 1+λ ((k + 1) × S λ ) = 0. So by Theorem 3.2.(b), every

Lemma 4 . 1 .

 41 Let p ∈ [1, 2[, β ≥ 0 such that βq ≤ 1.There exists C > 0 such that for all f ∈ A 2 1 (T),

Theorem 5 . 1 .

 51 and S ∈ A p ω (T). So we have the same result as (2.1) to characterize cyclicity in A p ω (T) by norm.Whenω n = O((1 + |n|) ε) for all ε > 0, for example ω n = ln(e + |n|) β where β ≥ 0, we can show the same result as Lemma 2.7. So by noting that for all p ≥ 1 and δ > 0,A p δ (T) ⊂ A p ω (T) ⊂ A p (T)we obtain by Theorem A the following result: Let 1 < p < 2 and ω = (ω n ) n∈Z a weight satisfying ω n = O((1 + |n|) ε ) for all ε > 0.

  4.(1), every g∈ A 1 δ (T) satisfying Z(g) = Z(f ) is cyclic in A p δ (T). Therefore by Lemma 2.7, there exist (f n ) a sequence of Lipschitz functions which are zero on Z(f ) and such that limn→∞ f n -1 A p δ (T) = 0. Moreover ω n = O((1 + |n|) δ ) so lim n→∞ f n -1 A p ω (T) = 0. Again by Lemma 2.7 in A p ω (T), we obtain that f is cyclic in A p ω (T). (2) : By the theorem of Salem (see Theorem 3.1 and Theorem 1.3.(

Acknowledgements

I would like to acknowledge my doctoral advisors, K. Kellay and M. Zarrabi.