Radoslaw Adamczak

Djalil Chafaï

AND Pawel L Wolff

DJALI L CHAFA Ï Rados Law Adamczak

Circular law for random matrices with exchangeable entries

Keywords: Winter Random permutations, Random matrices, Combinatorial Central Limit Theorem, exchangeable distributions, concentration of measure, smallest singular value, spectral analysis

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

Introduction

The spectral measure of an n × n matrix A with real or complex entries is defined by

ν A = 1 n n k=1 δ λ k ,
where λ 1 , . . . , λ n are the eigenvalues of A, in other words the roots in C of the characteristic polynomial, counted with their algebraic multiplicities, and where δ x is the Dirac mass at the point x. Thus ν A is a Borel probability measure on C, supported on R if A is Hermitian. If A is a random matrix, then ν A is a random discrete probability measure. An extensive body of work has been devoted to the study of the behavior of the spectral measure of large dimensional random matrices. While Wigner [START_REF] Wigner | On the distribution of the roots of certain symmetric matrices[END_REF] considered Hermitian matrices, the non-Hermitian case has also attracted attention, starting with the early work by Mehta [22], who proved, by using explicit formulas due to Ginibre [START_REF] Ginibre | Statistical ensembles of complex, quaternion, and real matrices[END_REF], that the average spectral measure of n × n matrices with i.i.d. standard complex Gaussian entries scaled by √ n converges to the uniform measure on the unit disc. We will call this measure the circular law. In a series of subsequent developments [START_REF] Girko | The circle law[END_REF][START_REF]The strong circular law. Twenty years later. I, Random Oper[END_REF][START_REF] Bai | Circular law[END_REF][START_REF] Pan | Circular law, extreme singular values and potential theory[END_REF][START_REF] Götze | The circular law for random matrices[END_REF], culminating with the work of Tao and Vu [32], this result has been strengthened to almost sure convergence and to sequences of random matrices with i.i.d. entries of unit variance. The Tao-Vu theorem is an instance of the universality phenomenon, which has become one of the main themes of Random Matrix Theory. Namely the limiting spectral object depends on the actual distribution of the entries of the random matrix only via a global scale parameter such as the variance. It is natural to ask whether this universal behavior extends to models of random matrices with heavy-tailed entries or with dependent entries. It has been recently shown [START_REF] Bordenave | Spectrum of non-Hermitian heavy tailed random matrices[END_REF]10] that the spectral measure of matrices with independent entries in the domain of attraction of an α-stable distribution with 0 < α < 2 converges to a measure which depends only on α and is supported on the whole complex plane. In particular the limiting distribution is not the circular law. Regarding the independence assumption, several classes of random matrices have been discussed in the literature, starting from models with i.i.d. rows such as random Markov matrices [START_REF]Circular law theorem for random Markov matrices[END_REF], random matrices with i.i.d. log-concave rows [START_REF] Law | On the Marchenko-Pastur and circular laws for some classes of random matrices with dependent entries[END_REF]2], and random ±1 matrices with i.i.d. rows of given sum [25]. The circular law still holds for models with dependent rows, for instance for blocs of Haar unitary matrices [START_REF] Jiang | Approximation of Haar distributed matrices and limiting distributions of eigenvalues of Jacobi ensembles[END_REF][START_REF] Dong | Circular law and arc law for truncation of random unitary matrix[END_REF], for random doubly stochastic matrices following the uniform distribution on the Birkhoff polytope [START_REF] Nguyen | Random doubly stochastic matrices: the circular law[END_REF], for random matrices with log-concave unconditional distribution [START_REF] Law | Circular law for random matrices with unconditional logconcave distribution[END_REF], and for random matrices with i.i.d. quaternionic entries [START_REF] Anderson | An introduction to random matrices[END_REF] (seen as 2 × 2 i.i.d. real blocks with possible dependencies inside the blocks). The present work introduces first a model of random matrices with exchangeable entries, obtained by shuffling a globally constrained deterministic matrix using a random uniform permutation. Such random matrices have dependent entries, rows, and columns. We show that the asymptotic behavior of the spectral measure is governed by the circular law. The precise formulation is given in Theorem 1.2 below. This first result is then used to deduce the circular law for a larger class of random matrices with exchangeable entries, as stated in Theorem 1.3 below. This second result can be seen as a counterpart of the one of Chatterjee [START_REF] Chatterjee | A generalization of the Lindeberg principle[END_REF], who proved that the spectral measure of symmetric random matrices with exchangeable entries in the upper triangle converges to Wigner's semi-circular law, which is the universal limit for random matrices with i.i.d. entries of finite variance. Our model of random matrices with exchangeable entries, like all the available models belonging to the universality class of the circular law, has symmetries related to the canonical basis. On the other hand, we stress that the sole invariance under permutation of rows and columns, which is weaker than full exchangeability, is not sufficient, as shown by the simple example of Haar unitary random matrices for which the limiting spectral distribution is the uniform distribution on the unit circle (not the unit disc!) often referred to as the arc law [START_REF] Dong | Circular law and arc law for truncation of random unitary matrix[END_REF]. On the other hand, note that the uniform law on the Birkhoff polytope of doubly stochastic matrices is invariant by permutations of rows or columns, but is not exchangeable globally.

A main tool in our proof is a lower bound on the smallest singular value of random matrices with exchangeable entries, formulated in Theorem 1.1. In recent years, an extensive amount of work has been devoted to the analysis of the smallest singular value of random matrices with (partially) independent entries or rows, in connection with the circular law, but also with numerical analysis or geometry, which makes our result of independent interest. Our approach follows the path introduced by Rudelson and Vershynin in [START_REF] Rudelson | The Littlewood-Offord problem and invertibility of random matrices[END_REF] for random matrices with i.i.d. entries, more precisely what they call the "soft approach" (nothing more is needed for the purpose of the circular law). However several technical problems related to the lack of independence among the entries have to be overcome.

Main results. For any

n ≥ 1, let x (n) = (x (n) ij ) 1≤i,j≤n be a deterministic real matrix, with (A1) n i,j=1 x (n) ij = 0; (A2) n i,j=1 |x (n) ij | 2 = n 2 .
Thanks to assumption (A2) we have

K n := max 1≤i,j≤n |x (n) ij | ≥ 1.
(

) 1
Of course, the entries of x (n) depend typically on n, hence the notation. The assumption (A2) puts also a constraint on the sparsity of the vector x (n) , depending on K n .

Let now π n be a uniform random permutation of the set [n]×[n] = {(i, j) : 1 ≤ i, j ≤ n}, where [n] = {1, . . . , n}. We consider the random matrix

X (n) = (X (n) ij ) 1≤i,j≤n where X (n) ij := x (n) πn(i,j) .
(2)

The matrix X (n) inherits the structure of x (n) . Namely, from (A1-A2) we get

n i,j=1 X (n) ij = 0 and n i,j=1 |X (n) ij | 2 = n 2 and max 1≤i,j≤n |X (n) ij | = K n .
Since the uniform law on the symmetric group is invariant under translation (it is a normalized Haar measure), it follows that the law of X (n) is invariant under any deterministic permutation of its n 2 coordinates, i.e. the random vector (X

(n) ij : (i, j) ∈ [n] × [n]
) of R n 2 has exchangeable coordinates. In other words, for every permutation σ of

[n] × [n], (X (n) σ(i,j) ) 1≤i,j≤n = (x (n) (πn•σ)(i,j) ) 1≤i,j≤n d = (x (n) πn(i,j) ) 1≤i,j≤n = (X (n) i,j ) 1≤i,j≤n .
It follows that for every (i, j) ∈ [n] × [n], and for every (k, l)

∈ [n] × [n] with (i, j) = (k, l), E(X (n) ij ) = 0 and E(|X (n) ij | 2 ) = 1 and E(X (n) ij X (n) kl ) = - 1 n 2 -1 . (3)
Except for special choices of x (n) , the random matrix X (n) is non-Hermitian, and even nonnormal with high probability. Normality means here commutation with the transposeconjugate. The random matrix X (n) has exchangeable entries obtained by shuffling the globally constrained deterministic matrix x (n) using the random uniform permutation π n . Such random matrices have dependent entries, dependent rows, and dependent columns. The simulation of a random uniform permutation such as π n amouts to approximately 2n 2 log 2 (n) bits. The randomness in X (n) is the one of π n , which should be compared with the n 2 bits needed for a standard random n × n symmetric Bernoulli ±1 matrix.

Our first main result is a bound on the smallest singular value of the matrix X (n) . For an n × n real or complex matrix A we denote by

s 1 (A) ≥ • • • ≥ s n (A)
the singular values of A, i.e. eigenvalues of √ AA * where A * = A ⊤ (transpose-conjugate).

The operator norm of A is A = max |x|=1 |Ax| = s 1 (A), where |x| denotes the Euclidean norm in C n or in R n . We have s n (A) = min |x|=1 |Ax|. The matrix A is invertible iff s n (A) > 0 and in this case s n (A) = A -1 -1 . The Hilbert-Schmidt norm or the Frobenius norm of A is

A HS = tr(AA * ) = s 1 (A) 2 + • • • + s n (A) 2 .
Theorem 1.1 (Smallest singular value). If X (n) is as in (2) then for every z ∈ C, there exists a constant C Kn,z > 0 depending only on K n (defined in (1)) and z such that for every ε > 0,

P s n (X (n) -z √ nId) ≤ εn -1/2 ≤ C Kn,z ε + 1 n 1/2 .
An explicit dependence of C K,z on K and z is given in Theorem 4.1. Let (ν n ) n≥1 be a sequence of random probability measures on E with E = C or E = R, and let ν be a probability measure on E. We say that the sequence (ν n ) n≥1 tends as n → ∞ weakly in probability to ν, and we denote

ν n n→∞ ν, if for any f ∈ C(E, R) and ε > 0, lim n→∞ P f dν n -f dν ≥ ε = 0,
where C(E, R) is the class of all bounded continuous real valued functions on E. This is equivalent to saying that (ν n ) n≥1 , seen as a sequence of random variables in the space of Borel probability measures on E, converges in probability to ν (see [32, Definition 1.2]). We denote by ν circ the uniform law on the unit disk of C, with density z → π -1 1 {z∈C:|z|≤1} . Our second main result concerns the limiting behavior of the spectral measure of X (n) . Theorem 1.2 (Circular law for shuffled matrices). Let A

(n) = 1 √ n X (n) where X (n) is as in (2). If K n = O(n 1/(10+δ) ) for some δ > 0, then ν A (n) n→∞ ν circ .
One can check easily that the normalization by n -1/2 ensures tightness, namely

|λ| 2 dν A (n) (λ) = 1 n n k=1 |λ k (A (n) )| 2 ≤ 1 n 2 n k=1 s k (X (n) ) 2 = 1 n 2 X (n) 2 HS = 1 n 2 n i,j=1 |X (n) ij | 2 = 1.
Theorem 1.2 leads to the following result concerning more general random matrices with exchangeable entries, beyond model (2). Namely, for every n ≫ 1, let

Y (n) = (Y (n) ij ) 1≤i,j≤n (4)
be an n × n matrix with exchangeable real entries, and define

µ n := 1 n 2 n i,j=1 Y (n) ij and σ 2 n := 1 n 2 n i,j=1 (Y (n) ij -µ n ) 2 .
Theorem 1.3 (Circular law for matrices with exchangeable entries). Let Y (n) be as in (4). If for n ≫ 1, σ 2 n > 0 a.s. and for some δ > 0,

lim sup n→∞ E σ -1 n |Y (n) 11 -µ n | 20+δ < ∞,
then, denoting

B (n) = 1 √ nσ n (Y (n) ij -µ n ) 1≤i,j≤n , we have ν B (n) n→∞ ν circ .
Discussion and open problems.

Assumptions. It is not enough to assume in Theorem 1.2 that K n = O( √ n), since one could construct a matrix with at most n/2 nonzero entries, which would create a substantial atom at zero in the spectral measure. It is tempting to conjecture that

K n = O(n 1/(2+δ)
) is sufficient for the circular law to hold. This would allow to prove Theorem 1.3 under the assumption on moments of order 4 + δ. On the other hand, Chatterjee's counterpart [START_REF] Chatterjee | A generalization of the Lindeberg principle[END_REF] to Theorem 1.3 in the Hermitian case works under the assumption which when translated to our setting would be E(|Y

(n) 11 -µ n |/σ n ) 4 = o(n 2/3
). Operator norm. One way to improve our growth/integrability assumptions would be to obtain a better bound on the operator norm of X (n) defined in (2). The simple bound we use

(Lemma 4.2) is E X (n) ≤ CK n √ n.
By analogy with the available results for matrices with i.i.d. entries, one may ask if for some α < 1/2 and a universal constant C,

E X (n) ? ≤ √ 2n + CKn α .
Another way of weakening our assumptions would be to improve the factor 1/ √ n in the probability bound on the smallest singular value. This factor comes from the Combinatorial Central Limit Theorem and cannot be further improved by our methods. In the i.i.d. case it has been strengthened to e -cn by relating the bound on the smallest singular value to the Littlewood-Offord problem [START_REF] Rudelson | The Littlewood-Offord problem and invertibility of random matrices[END_REF][START_REF] Tao | The condition number of a randomly perturbed matrix[END_REF][START_REF]From the Littlewood-Offord problem to the circular law: universality of the spectral distribution of random matrices[END_REF]. While certain ingredients of this approach can be transferred to the exchangeable setting, an important step seems to rely on a Fourier analytic argument, related to Esseen's inequality, involving independence of the entries of the matrix. It would be interesting to develop tools which would allow to use similar ideas in the exchangeable case. Note that since the right hand side in Theorem 1.1 is not summable in n, one cannot use the first Borel-Cantelli lemma in order to get an almost sure lower bound on s n (X (n)z √ nId).

Other models. One can consider a model of the form

M n = n -1/2 (X (n) + F n )
, where F n is deterministic with rank F n = o(n), satisfying a bound on the operator norm. An inspection of the proof of Theorem 1.2 reveals that if F n = O( √ n), then one can obtain the convergence to the circular law for the spectral measure of M n without changing the assumptions on K n . On the other hand if F n = o(n/ log 3/2 n), then an adaptation of our proof gives the result for K n = O(1). We remark that for matrices with i.i.d. entries with mean zero and variance one it is enough to assume that F n HS = O(n) [START_REF] Chafaï | Circular law for noncentral random matrices[END_REF]. Improving this part in the exchangeable case would allow to treat e.g. the adjacency matrices of uniform random directed graphs D(n, m n ). More precisely, consider a sequence m n of positive integers. Let D n be the adjacency matrix of the random graph D(n, m n ), i.e. a graph chosen uniformly from the set of all directed random graphs on n vertices, with m n directed edges (including possible loops). One may ask about the limiting spectral behavior of D n (depending on the behavior of m n as n → ∞). In some sense, this random graph model lies between the oriented Erdős-Rényi random graph model [START_REF]Spectrum of Markov generators on sparse random graphs[END_REF], and the uniform random oriented regular graph model [10]. The singular values of D n (as well as its shifts by multiples of identity) may be analyzed using Theorem 2.1 below. More generally, one may think about a Boltzmann-Gibbs probability distribution on the set of oriented graphs with n vertices, with density with respect to the counting measure proportional to exp(-β n H n ) where H n is a symmetric functional, and β n > 0.

Outline. In Section 2 we analyze the limiting distribution of the singular values of shifts by √ nzId n for the model (2), which is essential for the proof of Theorem 1.3, and which may be actually of independent interest. Section 3 is devoted to the derivation of a combinatorial version of the Talagrand concentration inequality for convex functions and product measures, which may be also of independent interest. This inequality is an important tool in the proof of Theorem 1.1 and Theorem 1.3. Theorems 1.1, 1.2, 1.3 are proved in Sections 4, 5, 6 respectively.

Notations. We will frequently write K, x, X instead of K (n) , x (n) , X (n) for convenience, when no confusion is possible. In the whole article by C, c we denote universal constants and by C a , c a constants depending only on the parameter a. In both cases the values of constants may differ between occurrences.

Limiting distribution of the singular values of shifts

This section is devoted to the proof of the following result.

Theorem 2.1 (Limiting singular values distribution of shifted matrices). For every z ∈ C, there exists a unique probability measure ν z on R + , absolutely continuous with respect to the Lebesgue measure, depending only on z, such that if

X (n) is as in (2) with K n = o(n 1/2 ), and if A (n) = 1 √ n X (n) , then, for every z ∈ C, (j) ν √ (A (n) -zIdn) * (A (n) -zIdn) = 1 n n k=1 δ s k (A (n) -zIdn) n→∞ ν z ; (jj) U(z) = - R + log(s) ν z (ds) = -log |z| if |z| > 1; 1-|z| 2 2 otherwise.
Furthermore, for z = 0, the probability distribution ν 0 is the so-called Marchenko-Pastur quarter circular law of Lebesgue density

x → 1 π √ 4 -x 2 1 [0,2] (x).
Theorem 2.1 is not valid if we only assume that K n = O(n 1/2 ). Indeed, one can construct x (n) in (2) in such a way that K n = O(n 1/2 ) while 0 is an eigenvalue of X (n) of multiplicity at least cn, which would contradict the fact that ν z is absolutely continuous.

Proof of Theorem 2.1. First of all, note that since K n = o(n 1/2 ), we have

E|X (n) 11 | 4 = o(n) and E|X (n) 11 | 3 = o(n 1/2 ). ( 5
)
If K n = O(1), the result follows from [2, Theorem 2.11 and Proposition 2.12]. In fact one can check that the proof given there works for K n being a small power of n.

However, to get larger range of K n we will adapt the proof by Chatterjee [START_REF] Chatterjee | A generalization of the Lindeberg principle[END_REF], who obtained the semi-circular law for symmetric random matrices with exchangeable entries, by using the Cauchy-Stieltjes trace-resolvent transform, and a generalization of the Lindeberg principle for the Central Limit Theorem.

For a probability measure µ supported on R, we denote by m µ its Cauchy-Stieltjes transform, defined for ξ

∈ C + = {z ∈ C : ℑ(z) > 0} as (see Theorem 2.4.4 in [4]) m µ (ξ) = R 1 λ -ξ µ(dλ).
If M is a n × n matrix with real spectrum and

ξ ∈ C + , then m ν M (ξ) is the normalized trace of the resolvent G = (M -ξId n ) -1 of M at point ξ, namely m ν M (ξ) = 1 n n k=1 (λ k (M) -ξ) -1 = 1 n tr(G).
Fix z ∈ C. We start by the usual linearization trick, which consists in constructing a Hermitian matrix, depending linearly on A (n) -zId n , and for which the eigenvalues are the singular values of A (n) -zId n . Namely, we consider the 2n × 2n Hermitian matrix

B n = 0 A (n) -zId n (A (n) -zId n ) * 0 .
The eigenvalues of B n are the singular values of A (n) -zId multiplied with ±1. More precisely, if λ > 0 is a singular value of A (n) -zId n of multiplicity m, then ±λ are both eigenvalues of B n of multiplicity m, and if zero is a singular value of A (n) -zId n of multiplicity m then it is also an eigenvalue of B n of multiplicity 2m. Thus, to prove the proposition it is enough to show that the spectral measure of B n converges weakly in probability to the same measure as the spectral measure of the matrix Dn = 0

1 √ n G n -zId n ( 1 √ n G n -zId n ) * 0 ,
where

G n = (g ij ) 1≤i,j≤n is an n × n matrix with i.i.d. N (0, 1) coefficients, as it is known [6, 10] that ν √ (n -1/2 Gn-zIdn) * (n -1/2 Gn-zIdn) converges to the measure ν z satisfying (jj). Let b = n -2
1≤i,j≤n g ij and let 1 n ⊗ 1 n be the n × n matrix with all elements equal to one. Define now the matrix

D n = 0 1 √ n G n -b1 n ⊗ 1 n -zId n ( 1 √ n G n -b1 n ⊗ 1 n -zId n ) * 0 .
Since D n is a rank two additive perturbation of Dn , it is well known by using interlacing inequalities [START_REF] Chafaï | Interactions between compressed sensing, random matrices, and high dimensional geometry[END_REF] that the Kolmogorov distance between ν Dn and ν Dn is at most 2/n. Thus it is enough to prove that ν Bnν Dn → 0 weakly in probability, which will follow if we prove that for each ξ ∈ C + , m ν Bn (ξ)m ν Dn (ξ) → 0 in probability as n → ∞. Since m ν Dn (ξ) converges in probability to the deterministic quantity m νz (ξ), it is enough to show that for every smooth function g with compact support we have

|Eg(ℜm ν Bn (ξ)) -Eg(ℜm ν Dn (ξ))| → 0
and that an analogous statement holds for the imaginary parts of m ν Bn and m ν Dn .

To this end we will use the following Theorem, which is [13, Theorem 1.2].

Theorem 2.2 (Chatterjee-Lindeberg principle). Suppose X is a random vector in R n with exchangeable components of finite fourth moments and let Z be a standard Gaussian vector in R n , independent of X. Define

μ = 1 n n i=1 X i , σ2 = 1 n n i=1 (X i -μ) 2 , Z = 1 n n i=1 Z i , Y i = μ + σ(Z i -Z).
Let f : R n → R be a C 3 function, and let L ′ r (f ) be a uniform bound on all r-th partial derivatives of f , including mixed partials. For each p, let

w p = E|X 1 -μ| p . Then |Ef (X) -Ef (Y )| ≤ 9.5w 1/2 4 L ′ 2 (f )n 1/2 + 13w 3 L ′ 3 (f )n.
It is easy to check that for any matrix valued differentiable function M of x ∈ R with values in the space of Hermitian matrices and G(x) = (M(x) -ξId) -1 (ξ ∈ C + ), we have

d dx G = -G dM dx G. (6)
Consider now for x ∈ R n×n the 2n×2n matrix M(x) = (M ij (x)) 1≤i,j≤2n , where

M ij (x) = 0 if i, j ≤ n or i, j > n, M ij (x) = 1 √ n x i,j-n -z1 {i=j} for i ≤ n, j > n and M ij (x) = 1 √ n x i-n,j -z1 {i=j} for i > n, j ≤ n.
As in [START_REF] Chatterjee | A generalization of the Lindeberg principle[END_REF] we will write ∂ α for ∂/∂x α for α = (i, j), 1 ≤ i, j ≤ n. From (6) we get

∂ α 1 2n trG = - 1 2n tr G(∂ α M)G .
Differentiating two more times and using again (6) together with the observation that for any α 1 , α 2 , ∂ α 1 ∂ α 2 M = 0, we get

∂ α 1 ∂ α 2 1 2n trG = 1 2n 1≤i =j≤2 tr G(∂ α i M)G(∂ α j M)G , ∂ α 1 ∂ α 2 ∂ α 3 1 2n trG = - 1 2n 1≤i =j =k≤3 tr G(∂ α i M)G(∂ α j M)G(∂ α k M)G .
Note that ∂ α M has two nonzero entries, each equal to n -1/2 . Moreover G ≤ (ℑξ) -1 . Thus

∂ α 1 2n trG = 1 2n tr (∂ α M)G 2 ≤ 1 n 3/2 (ℑξ) -2 .
As for higher order derivatives, using the inequalities |trAB| ≤ A HS B HS and AB HS ≤ A B HS , we get

|∂ α 1 ∂ α 2 1 2n trG| ≤ 1 2n 1≤i =j≤2 G∂ α i M HS G(∂ α j M)G HS ≤ 1 2n 1≤i =j≤2 G 3 ∂ α i M HS ∂ α j M HS ≤ 2 n 2 (ℑξ) -3
and similarly

|∂ α 1 ∂ α 2 ∂ α 3 1 2n trG| ≤ 6 √ 2 n G 4 n -3/2 ≤ 9n -5/2 (ℑξ) -4 .
Moreover, since x ij are real, we have ∂ α ℜG = ℜ(∂ α G) and a similar equality for the imaginary parts. Using this together with the above estimates on the derivatives, we get that for any smooth function g on R, with compact support, the function f : R n 2 → R, defined as f (x) = g( 12n ℜtrG(x)), satisfies

L ′ 2 (f ) ≤ C g,ξ n -2 , L ′ 3 (f ) ≤ C g,ξ n -5/2 .
Thus, by Theorem 2.2 (applied with n 2 instead of n) and (5),

|Eg(ℜm ν Bn (ξ)) -Eg(ℜm ν Dn (ξ))| ≤ C g,ξ (n -1 (E|X (n) 11 | 4 ) 1/2 + n -1/2 E|X (n) 11 | 3 ) → 0
as n → ∞. Since an analogous convergence holds for the imaginary parts, this ends the proof of Theorem 2.1.

Remark 2.3 (Assumptions). One can see from the above proof that the theorem remains true under an assumption weaker than K n = o(n 1/2 ), since it is enough to assume (5).

Combinatorial Talagrand's concentration inequality

The following result is a combinatorial analogue of the Talagrand concentration of measure inequality for convex functions under product measures. It plays a crucial role in our approach, and may be of independent interest. We give a proof for completeness. Theorem 3.1 (Concentration inequality for convex functions). Let x 1 , . . . , x n ∈ [0, 1] and let ϕ : [0, 1] n → R be an L-Lipschitz convex function. Let π be a random uniform permutation of the set [n] and let Z = ϕ(x π(1) , . . . , x π(n) ). Then for all t > 0,

P(|Z -EZ| ≥ t) ≤ 2 exp(-ct 2 /L 2 ). ( 7
)
Proof of Theorem 3.1. The randomness of Z comes entirely from π. Let P n be the uniform measure on the symmetric group S n . The proof follows closely the original argument given by Talagrand in the case of product measures [START_REF]A new look at independence[END_REF] and is based on the following theorem.

Theorem 3.2 (Talagrand [START_REF] Talagrand | Concentration of measure and isoperimetric inequalities in product spaces[END_REF]). For π ∈ S n and A ⊆ S n define

U A (π) = {s ∈ {0, 1} n : ∃ τ ∈A ∀ l≤n s l = 0 =⇒ τ (l) = π(l)}. Let V A (π) = ConvexHull(U A (π)) and f (A, π) = inf{|s| 2 : s ∈ V A (π)}. Then Sn exp 1 16 f (A, π) dP n (π) ≤ 1 P n (A)
.

In what follows, for τ ∈ S n and x ∈ R n , we will denote x τ = (x τ (1) , . . . , x τ (n) ). It is well known that up to universal constants it is enough to prove [START_REF] Bordenave | Spectrum of non-Hermitian heavy tailed random matrices[END_REF] with the median instead of the mean [START_REF] Ledoux | The concentration of measure phenomenon[END_REF]. Let Z(τ ) = ϕ(x τ ) and A = {τ ∈ S n : Z(τ ) ≤ Med Z}. We have P n (A) ≥ 1/2, so by Theorem 3.2 and Chebyshev's inequality we get

P n (π : f (A, π) ≥ t 2 ) ≤ 2 exp(-ct 2 ).
If f (A, π) < t 2 , then there exist s 1 , . . . , s m ∈ U A (π), p 1 , . . . , p m ≥ 0,

p 1 + • • • + p m = 1, such that m i=1 s i p i < t.
Let τ i ∈ A be such that s i j = 0 =⇒ τ i (j) = π(j). We have for j = 1, . . . , n,

x π(j) - m i=1 x τ i (j) p i ≤ m i=1 |x π(j) -x τ i (j) |p i ≤ 2 m i=1 s i j p i , so x π - m i=1 p i x τ i ≤ 2 m i=1 s i p i < 2t.
Moreover, by convexity ϕ( i p i x τ i ) ≤ m i=1 p i ϕ(x τ i ) ≤ Med Z and so by the Lipschitz condition ϕ(x π ) < Med Z + 2Lt. This shows that

P n (π : ϕ(x π ) ≥ Med Z + 2Lt) ≤ P n (π : f (A, π) ≥ t 2 ) ≤ 2 exp(-ct 2 ).
To prove the bound on the lower tail let us now denote

A = {τ ∈ S n : Z(τ ) ≤ Med Z -2Lt}.

By Theorem 3.2 we have

Sn

exp cf (A, π) dP n (π) ≤ 1 P n (A) But if f (A, π) < t 2 ,
then by a similar argument as above ϕ(x π ) < Med Z, so the left hand side above is bounded from below by 1 2 exp(ct 2 ), which gives P n (A) ≤ 2 exp(-ct 2 ).

Using integration by parts and the triangle inequality in L p , we obtain the following.

Corollary 3.3 (Moments).

In the setting of Theorem 3.1 we have for any p ≥ 2,

Z p ≤ Z 1 + CL √ p.
4. Proof of Theorem 1.1 (smallest singular value)

Throughout this section, X (n) is as in (2). We will prove the following more precise version of Theorem 1.1, which is actually used in the proof of Theorem 1.2. Theorem 4.1. Under the assumptions of Theorem 1.1, for any ε ∈ (0, 1),

P(s n (X (n) - √ nzId) ≤ 1 K n + |z| εn -1/2 ) ≤ CK 2 n (K n + |z|) log(1 + K n + |z|)ε + C K 4 n (K n + |z|) log 3/2 (1 + K n + |z|) n 1/2 .
Let us first introduce some tools we will need in the proof of Theorem 4.1. One of our main tools is a version of Talagrand's concentration inequality for convex functions stated in Theorem 3.1, and Corollary 3.3. The next two lemmas are rather standard corollaries. We denote by S n-1

C = {z ∈ C n : |z| = 1} the unit Euclidean ball in C n .
Lemma 4.2 (Operator norm). For all t > 0 with probability at least

1 -exp(-ct 2 /K 2 n ), X (n) ≤ CK n √ n + t.
Proof of Lemma 4.2. Let us consider a (1/4)-net N in S n-1

C

of cardinality 9 2n (it exists by standard volumetric estimates). We have

X (n) ≤ 16 7 sup x,y∈N | X (n) x, y |.
Note that E X (n) x, y = 0. Since for x, y ∈ S n-1 C , A → | Ax, y | is a 1-Lipschitz function with respect to the Hilbert-Schmidt norm, we get by Theorem 3.1 and the union bound

∀t ≥ CK n , P( X (n) ≥ t √ n) ≤ 2 • 9 4n exp(-ct 2 n/K 2 n ) ≤ exp(-ct 2 n/K 2 n ).
Integrating the above inequality by parts, we get E X (n) ≤ CK n √ n. The lemma now follows by another application of Theorem 3.1, this time to the function X → X .

Let Sparse(δ) = {x ∈ C n : n k=1 1 x k =0 ≤ δn} be the set of δn sparse vectors in C n . Similarly as in [START_REF] Rudelson | The Littlewood-Offord problem and invertibility of random matrices[END_REF] we partition the unit sphere S n-1 C into compressible vectors and incompressible vectors:

Comp(δ, ρ) = {x ∈ S n-1 C : dist(x, Sparse(δ)) ≤ ρ} and Incomp(δ, ε) = S n-1 C \Comp(δ, ε). If M = (M ij
∈ C, if n ≥ C α K 2 n , then a) for any x ∈ S n-1 C , with probability at least 1 -exp(c α n/K 2 n ), |X (n) |I x - √ nzx |I | ≥ c α √ n, b) with probability at least 1 -exp(-c α n/K 2 n ), for all x ∈ Comp(δ, ρ), |X (n) |I x - √ nzx |I | ≥ c α √ n, where ρ = c ′ α K n + |z| and δ = c ′′ α K 2 n log(1 + K n + |z|) . ( 8
)
Proof of Lemma 4.3. We abridge K n and X (n) into X and K. Consider first an arbitrary x ∈ S n-1 C . Using (3) and

|x| 1 := |x 1 | + . . . + |x n | ≤ √ n, we get E|X |I x - √ nzx |I | 2 = i∈I E n j=1 X ij x j - √ nzx i 2 ≥ i∈I E n j=1 X ij x j 2 = i∈I n j=1 EX 2 ij |x j | 2 + i∈I 1≤j =k≤n EX ij X ik x j xk ≥ #I - #I n 2 -1 |x| 2 1 ≥ #I/3.
Since the function X → |X |I xzx |I | is convex and 1-Lipschitz with respect to the Hilbert-Schmidt norm, by Corollary 3.3 and the assumption on I we get, for n

≥ C α K 2 , E|X |I x - √ nzx |I | ≥ c √ αn -CK ≥ c α √ n.
By Theorem 3.1 we get

P(|X |I x - √ nzx |I | ≤ c α √ n ≤ 2 exp(-c α n/K 2 ), (9)
which proves the first part of the lemma. Now, for each δ, ρ ∈ (0, 1], the set Sparse(δ) ∩ S n-1 C admits a ρ-net of cardinality

n ⌊δn⌋ (3/ρ) 2δn ≤ C ρ 2 δ δn .
Thus for ρ = c ′ α K+|z| and δ = c ′′ α K 2 log(1+K+|z|) by the union bound, the inequality (9), Lemma 4.2, the estimate K ≥ 1, and the triangle inequality, we get with probability at least

1 -exp(-c α n/K 2 ), for all x ∈ Comp(δ, ρ), |X |I x - √ nzx |I | ≥ c α √ n -Cρ(CK + |z|) √ n ≥ 1 2 c α √ n.
The final ingredient is a Berry-Esseen type estimate for linear combinations of exchangeable random variables.

Lemma 4.4 (Berry-Esseen type estimate for exchangeable variables). Consider two sequences of real numbers x = (x 1 , . . . , x n ) and a = (a 1 , . . . , a n ), such that for some constants K, L > 0,

• n i=1

x i = 0, n i=1 x 2 i = n, |x i | ≤ K, • |a i | ≤ L|a| √ n , a = ±n -1/2 (|a|, . . . , |a|).
Let π be a random (uniform) permutation of [n] and define

W := n i=1 a i x π(i) . Then σ 2 := EW 2 = 1 n-1 (n n i=1 a 2 i -( n i=1 a i ) 2 ) > 0 and sup t∈R P(W ≤ t) - 1 √ 2πσ t -∞ e -x 2 /2σ 2 dx ≤ 34LK|a| σ √ n . ( 10
)
Proof of Lemma 4.4. The result follows from the combinatorial Central Limit Theorem (CLT) [14, equation (4.105) and Theorem 6.1]. Namely, let (c ij ) i,j≤n be an array of real numbers and let

W = n i=1 c iπ(i) ,
where π is a random (uniform) permutation of [n]. Then

σ 2 := Var W = 1 n -1 n i,j=1 c ij - 1 n n k=1 c ik - 1 n n k=1 c kj + 1 n 2 n k,l=1 c kl 2 .
Moreover, if σ > 0, then for every ε > 0,

sup t∈R P(σ -1 (W - 1 n n i,j=1 c ij ) ≤ t) - 1 √ 2π t -∞ exp(-x 2 /2)dx) ≤ 16.3A σ ,
where

A = max 1≤i,j≤n c ij - 1 n n k=1 c ik - 1 n n k=1 c kj + 1 n 2 n k,l=1 c kl .
The lemma follows by setting c ij = a i x j and elementary calculations. ) \ E, measurable with respect to F ′ = σ((π(i, j)) (i,j)∈E ). One can then consider the σ-field F = σ(F ′ , (π(i, j)) (i,j)∈F ) and the random vector π ′ = (π(i, j)) (i,j)∈(E∪F ) c (this notation is slightly informal as the set F itself is random, but this should not lead to misunderstanding). One can then see that conditionally on F , (π(i, j)) (i,j)∈(E∪F ) c is distributed as a random (uniform) bijection from the set (E∪F ) c to the set

([n]×[n])\{π(i, j) : (i, j) ∈ E∪F }.
In particular the vector (X ij ) (i,j)∈(E∪F ) c is distributed as a random permutation of the sequence obtained from (x ij ) n i,j=1 after removing the elements (X ij ) (i,j)∈E∪F and one can apply to it conditionally e.g. Theorem 3.1 or Lemma 4.4.

Proof of Theorem 4.1. Again we will write X instead of X (n) and K instead of K n . We may and will assume that

n ≥ CK 2 log(1 + K + |z|) (11)
(otherwise the bounds of the theorem become trivial as the right-hand side exceeds one). Let B = X -√ nzId and s n = s n (B). Since

s n = inf x∈S n-1 C
|Bx|, it is enough to bound from below the quantities

β = inf x∈Comp(δ,ρ) |Bx|, ζ = inf x∈Incomp(δ,ρ)
|Bx| for some δ = δ K,z , ρ = ρ K,z . By Lemma 4.3 for

ρ = c K + |z| and δ = c K 2 log(1 + K + |z|) , (12)
we have for n ≥ CK 2 ,

β ≥ c √ n ( 13
)
with probability at least 1exp(-cn/K 2 ). By Lemma 3.5 from [START_REF] Rudelson | The Littlewood-Offord problem and invertibility of random matrices[END_REF],

P(ζ ≤ ρεn -1/2 ) ≤ 1 δn n i=1 P(dist(X i -z √ ne i , H i ) ≤ ε),
where X i 's are the columns of X and H i = span(X k : k = i).

Let now η i be a random (unit) normal to H i defined as a measurable function of (X 1 , . . . , X i-1 , X i+1 , . . . , X n ). We have dist(X iz

√ ne i , H i ) ≥ | X i -z √ ne i , η i |, so by
exchangeability of the entries of X,

P(ζ ≤ ρεn -1/2 ) ≤ 1 δ P(| X n , η n -z √ n e n , η n | ≤ ε). ( 14
)
To estimate the right hand side we will use Lemma 4.4. To be able to apply it, we have to prove certain properties of the vector η = η n . Let us define for θ, r ∈ [0, 1],

G(θ, r) = I⊆[n],#I≥(1-θ)n G I (θ, r),
where

G I (θ, r) = {x ∈ S n-1 C : ∃ ξ∈C,|ξ|≤1 |x |I - ξ √ #I 1 I | ≤ r}
(here 1 I = (u i ) #I i=1 with u i = 1 for all i). We will show that with high probability η / ∈ G(θ, r) for certain r = r K,z and θ = θ K,z . Note that if #I ≥ (1θ)n, then G I (θ, r) admits a 3r-net N I , such that

#N I ≤ C r 2 3 r 2θn .
Indeed, for any x ∈ G I (θ, r), x |I can be approximated up to 2r by one of the vectors ξ √ #I 1 I , where ξ comes from an r-net in the unit disk in C, whereas x |I c can be approximated by a vector from an r-net in the unit ball of C I c . Thus the set G(θ, r) admits a 3r net N of cardinality

#N ≤ ⌊θn⌋ k=0 n k C r 2 3 r 2θn ≤ C r 2 en ⌊θn⌋ θn 3 r 2θn ≤ exp Cnθ log 2 θr for n ≥ 1/θ. Let B ′′ = (B ′ ) *
, where B ′ is the matrix obtained by removing the last column of B. By exchangeability, B ′′ has the same distribution as (X -z√ nId) |{1,...,n-1} and so by the first part of Lemma 4.3, the union bound and Lemma 4.2 we get with probability at least 1exp(-cn/K 2 ), inf

x∈G(θ,r) |B ′′ x| ≥ c √ n for r = c K + |z| , θ = c K 2 log(1 + K + |z|) (15)
(note that [START_REF] Chafaï | Circular law for noncentral random matrices[END_REF] implies that n ≥ 1/θ). We may and will assume that θ ≤ 1/2. Combining the above estimate with the equality B ′′ η = 0, we get that with probability at least 1exp(-cn/K 2 ),

η / ∈ G(θ, r). (16)
Now let

I = {i ∈ [n] : |η i | ≤ 1 √
θn } and note that by Markov's inequality #I ≥ n(1θ). Let F ′ be the σ-field generated by (π(i, j)) 1≤i≤n,1≤j≤n-1 . In particular η is F ′ -measurable. Let also F = σ(F ′ , {π(i, n)} i / ∈I ). Note that i∈I X in and i∈I X 2 in are F -measurable. We will use this fact together with Remark 4.5 to estimate the conditional distribution

P(| X n , η -Y | ≤ ε|F ),
where Y is any F -measurable random variable, by another random variable measurable with respect to F . To this end we will use Lemma 4.4.

Let us define μ =

1 #I i∈I X in , Σ2 = 1 #I i∈I (X in -μ) 2 .
Let γ be a small constant which will be fixed later on. Note that by Theorem 3.1 we have

P(| n i=1 X in | ≥ γn) ≤ 2 exp(-cγ 2 n/K 2 ). (17)
Now, by exchangeability of X in , i = 1, . . . , n with respect to P(•|F ′ ), we get that on the set

∆ 1 = {| n i=1 X in | ≤ γn} ∈ F ′ , |E( i∈I X in |F ′ )| = | #I n n i=1 X in | ≤ γn.
Thus, again by Theorem 3.1 we get on ∆ 1 ,

P(| i∈I X in | ≥ 2γn|F ′ ) ≤ 2 exp(-cγ 2 n 2 /(K 2 #I)) ≤ 2 exp(-cγ 2 n/K 2 ). ( 18
)
Let now ∆ 2 = {|μ| ≤ 4γ} ∈ F . Combining [START_REF] Girko | The circle law[END_REF], [START_REF]The strong circular law. Twenty years later. I, Random Oper[END_REF] and the inequality #I ≥ (1θ)n ≥ n/2, we get

P(∆ 2 ) ≥ 1 -4 exp(-cγ 2 n/K 2 ). (19)
Now, by Corollary 3.

3 applied to Z = n i=1 X 2 in , for n ≥ 4C 2 K 2 we get √ n = E n i=1 X 2 in ≥ E n i=1 X 2 in ≥ √ n -CK ≥ 1 2 √ n
and by Theorem 3.

1 the set ∆ 3 = {Cn ≥ n i=1 X 2 in ≥ cn} ∈ F ′ satisfies P(∆ 3 ) ≥ 1 -2 exp(-cn/K 2 ). ( 20
) On ∆ 3 , E( i∈I X 2 in |F ′ ) ≥ c(1 -θ)n and by Corollary 3.3, E( i∈I X 2 in |F ′ ) ≥ c(1 -θ)n -CK ≥ c √ n,
for n ≥ C ′ K 2 , so yet another application of Theorem 3.1 yields that on ∆ 3 ,

P( i∈I X 2 in ≤ cn|F ′ ) ≤ 2 exp(-cn/K 2 ).
Combining this with (20) we get

P(Cn ≥ i∈I X 2 in ≥ cn) ≥ 1 -2 exp(-cn/K 2 ). (21)
Since Σ2 = 1 #I i∈I X 2 in -μ2 , by the above inequality and ( 19) (applied with a sufficiently small universal constant γ adjusted to the constant c in ( 21)) we get

P( Σ2 ≥ c) ≥ 1 -2 exp(-cn/K 2 ). Let ∆ = { i∈I X 2 ni ≤ Cn, Σ2 ≥ c, μ ≤ 1 and η / ∈ G(θ, r)) ∈ F .
By the above inequality together with ( 16),( 19),( 21) we have

P(∆) ≥ 1 -2 exp(-cn/K 2 ). (22)
On ∆ we have dist(η |I , { ξ

√ #I 1 I : ξ ∈ C, |ξ| ≤ 1}) ≥ r.
Let η ′ and η ′′ be resp. the real and imaginary part of η. Thus at least one of the vectors η ′ |I , η ′′ |I is at distance at least r/ √ 2 from {ξ1 I : ξ ∈ R}). Indeed, otherwise we would have We will consider the case

|η ′ |I -ξ ′ √ #I 1 I |, |η ′′ |I -ξ ′′ √ #I 1 I | ≤ r/ √ 2 for some ξ ′ , ξ ′′ ∈ R, and so |η |I - ξ ′ + iξ ′′ √ #I 1 I | ≤ r,
dist(η ′ |I , {ξ1 I : ξ ∈ R}) ≥ r/ √ 2, ( 23
)
the other one is analogous. Assume now that for some F -measurable complex random variable

Y = Y ′ + iY ′′ , | η, X n -Y | ≤ ε. Then | η ′ , X n -Y ′ | ≤ ε. Define x i = (X in -μ) Σ-1 for i ∈ I.
Since η ′ , X in , i / ∈ I and μ are F -measurable we have on ∆,

P(| η, X n -Y | ≤ ε|F ) ≤ sup u∈R P(| i∈I η ′ i x i -u| ≤ ε Σ-1 |F ) ≤ sup u∈R P(| i∈I η ′ i x i -u| ≤ Cε|F ), (24)
where in the second inequality we used the fact that on ∆, Σ2 ≥ c. Moreover, by Remark 4.5, the right-hand side above equals

sup u∈R P(| i∈I η ′ i x τ (i) -u| ≤ Cε|F ),
where τ is a random permutation of I, distributed (conditionally on F ) uniformly, and so we are in position to use Lemma 4.4. Denote W = i∈I η ′ i x τ (i) , σ 2 = E(W 2 |F ). Note that i∈I x i = 0 and i∈I x 2 i = #I. Moreover on ∆ we have |x i | ≤ CK. Using the fact that the density of a Gaussian distribution with variance σ 2 is bounded from above by σ -1 and #I ≥ n/2, we get by Lemma 4.4 that on ∆,

P(| i∈I η ′ i x τ (i) -u| ≤ ε|F ) ≤ Cεσ -1 + C KL|η ′ |I | σn 1/2 , where L = max i∈I √ #I|η ′ i |/|η ′ |I | ≤ max i∈I √ n|η ′ i |/|η
P(| i∈I η ′ i x τ (i) -u| ≤ ε|F ) ≤ Cεσ -1 + C K σθ 1/2 n 1/2 . ( 25
)
It remains to estimate σ from below on the set ∆. By Lemma 4.4 we have

σ 2 = #I #I -1 i∈I η ′2 i - 1 #I ( i∈I η ′ i ) 2 ≥ i∈I η ′2 i - 1 #I ( i∈I η ′ i ) 2 . The function t → √ t is C/|η ′ |I | Lipschitz on (|η ′ |I | 2 /2, ∞), so we get that if i∈I (η ′ i ) 2 - 1 #I ( i∈I η i ) 2 ≤ κ with κ < |η ′ |I | 2 /4, then ( i∈I (η ′ i ) 2 ) 1/2 - 1 √ #I | i∈I η i | ≤ C κ |η ′ |I |
, which can be rewritten as

|η ′ |I | -| η ′ |I , 1 √ #I 1 I | ≤ C κ |η ′ |I | .
Multiplying both sides by 2|η ′ |I | and using that

| 1 I √ #I | = 1, we get |η ′ |I - h √ #I 1 I | 2 ≤ Cκ (26)
where

h = |η ′ |I |sgn( η ′ |I , 1 √ #I 1 I ). From (23) it follows, that |η ′ |I | 2 ≥ r 2 /2.
For κ = cr 2 with a sufficiently small absolute constant c (in particular we want to assure that κ ≤ |η ′ |I | 2 /4), the right hand side of ( 26) is smaller than r 2 /2 and so (again by [START_REF] Nguyen | Random doubly stochastic matrices: the circular law[END_REF]) the inequality [START_REF] Pan | Circular law, extreme singular values and potential theory[END_REF] cannot hold on ∆.

Thus, on ∆ we have σ ≥ cr, which, when combined with (25) gives

P(| i∈I η ′ i x τ (i) -u| ≤ ε|F ) ≤ C ε r + C K rθ 1/2 n 1/2
on ∆. Going now back to [START_REF] Anderson | An introduction to random matrices[END_REF], ( 22) and ( 14) we get

P(ζ ≤ ρεn -1/2 ) ≤ C ε δr + C K δrθ 1/2 n 1/2 + 2 δ exp(-cn/K 2 ).
Together with [START_REF] Chatterjee | A generalization of the Lindeberg principle[END_REF] this gives (after adjusting c)

P(s n (B) ≤ ρεn -1/2 ) ≤ C ε δr + C K δrθ 1/2 n 1/2 + 2 exp(-cn/K 2 ).
Plugging in the values of ρ, δ (equation ( 12)) and θ, r (equation ( 15)) we get

P(s n (B) ≤ 1 K + |z| εn -1/2 ) ≤2 exp(-cn/K 2 ) + CK 2 (K + |z|) log(1 + K + |z|)ε + C K 4 (K + |z|) log 3/2 (1 + K + |z|) n 1/2 ,
which ends the proof (we again adjust the constants to remove the first term on the right-hand side).

5. Proof of Theorem 1.2 (circular law for the first model) By [7, Lemma A2] or [10], to prove that ν A (n) converges weakly in probability to the uniform measure on the unit disc, it is enough to show that the following is true: (i) Singular values of shifts. For all z ∈ C, there exists a non random probability measure ν z on R + , absolutely continuous with respect to the Lebesgue measure, depending only on z, and such that

ν z,n := 1 n n k=1 δ s k (A (n) -zIdn) n→∞ ν z .
Moreover, for almost all z ∈ C,

U(z) := - R + log(s)ν z (ds) = -log |z| if |z| > 1, 1
P R + | log s|1 {| log s|>t} dν z,n (s) > ε = 0.
The first item (i) is settled by Theorem 2.1. It remains to prove assertion (ii), which is the aim of the rest of this section. We follow the Tao and Vu approach [32]. We will combine estimates on the smallest singular value coming from Section 4 with a rougher bound on intermediate singular values of the matrix, obtained in the following lemmas.

-2 exp(-c(n - k)/K 2 n ), dist(Z k+1 , H) ≥ c √ n -k.
Proof of Lemma 5.1. In what follows we will suppress the superscript (n) and write simply X ij for the entries of the matrix X (n) . The rows of X (n) will be denoted by X 1 , . . . , X n . We can assume that k ≤ n-CK 2 n for some absolute constant C, otherwise the estimate on probability given in the lemma becomes trivial for c sufficiently small. Consider the σ-field F generated by (π(i, j)) 1≤i≤k,1≤j≤n .

We will first replace H by H = span(H, 1, Y ) where 1 is the vector of ones and Y is the (k + 1)-st row of R. We can assume that with probability one H is of dimension l = k + 2 (otherwise we may enlarge H to a subspace of dimension l in an F -measurable way). Let X = X k+1 -μ1, where μ =

1 n(n-k) n i=k+1 n j=1 X ij (note that μ is F -measurable) and denote the coordinates of X by x 1 , . . . , x n . Note that dist(Z k+1 , H) ≥ dist(Z k+1 , H) = dist(X, H).
We have E(x i |F ) = 0. Moreover, since Eμ = 0, by Theorem 3.1 we have

P(|μ| ≥ γ) ≤ 2 exp(-cγ 2 n(n -k)/K 2 n ). ( 27
)
Consider now M 2 := n i=k+1 n j=1 X 2 ij (which is F -measurable) and note that by Corollary 3.3, EM ≥ √ EM 2 -CK n ≥ 2 -1 n(nk) (where we used the assumption nk ≥ CK 2 n ). Thus again by Theorem 3.1 we have

P(M 2 ≤ cn(n -k)) ≤ 2 exp(-cn(n -k)/K 2 n ). ( 28
) Define Σ2 = E(x 2 j |F ) = 1 n(n-k) n i=k+1 n j=1 (X ij -μ) 2 = 1 n(n-k) M 2 -μ2 and ∆ = { Σ ≥ c}.
Combining ( 28) and ( 27) with γ small enough we obtain

P(∆) ≥ 1 -2 exp(-cn(n -k)/K 2 n ). (29)
Let P be the orthogonal projection on H⊥ and let e 1 , . . . , e n-l be an orthonormal basis in H⊥ . Denote e i = (e ij ) 1≤j≤n . We have

E(dist(X, H) 2 |F ) = E(|P X| 2 |F ) = n-l i=1 E n j=1 x j ēij 2 |F = n-l i=1 n j=1 |e ij | 2 E(x 2 j |F ) + n-l i=1 1≤j =t≤n ēij e it E(x j x t |F ).
We have E(x 2 j |F ) = Σ2 and for j = t,

E(x j x t |F ) = 1 n(n -k)[n(n -k) -1] (a,b) =(r,s) k+1≤a,r≤n,1≤b,s≤n (X ab -μ)(X rs -μ) = - 1 n(n -k)[n(n -k) -1] n a=k+1 n b=1 (X ab -μ) 2 = - 1 n(n -k) -1 Σ2 . Thus E(dist(X, H) 2 |F ) = Σ2 n-l i=1 n j=1 |e ij | 2 - 1 n(n -k) -1 1≤j =t≤n ēij e it = Σ2 n-l i=1 n j=1 |e ij | 2 - 1 n(n -k) -1 n j=1 ēij 2 + 1 n(n -k) -1 n j=1 |e ij | 2 ≥ Σ2 n-l i=1 n(n -k) n(n -k) -1 - n n(n -k) -1 = Σ2 (n -l) n 2 -kn -n n 2 -kn -1 .
Thus, using the assumption that k ≤ n -C we get for n ≥ C that on ∆,

E(dist(X, H) 2 |F ) ≥ c(n -k).
Using now Corollary 3.3, the fact that P is 1-Lipschitz and the assumption nk ≥ CK 2 n , we get on ∆, E(dist(X, H)|F ) ≥ c √ nk. Applying Theorem 3.1 we obtain on ∆,

P(dist(X, H) ≥ c √ n -k|F ) ≥ 1 -2 exp(-c(n -k)/K 2 n )
, which when combined with [START_REF]A new look at independence[END_REF] gives

P(dist(X, H) ≥ c √ n -k) ≥ 1 -2 exp(-c(n -k)/K 2 n ).
(n) -zId n . If K n = O(n 1/(2+δ)
) for some δ > 0, then there exists γ ∈ (0, 1) such that for every z ∈ C we have

lim n→∞ P ∃ n γ ≤i≤n-1 s n-i ≤ c i n = 0.
Proof of Lemma 5.2. The proof follows an argument due to Tao and Vu [32]. Let R = -√ nzId and recall the notation of Lemma 5.1. For some γ ∈ (0, 1) to be chosen later on, consider i ≥ n γ . Let k = n -⌊i/2⌋ and let B be the k × n matrix with rows Z 1 , . . . , Z k . By Cauchy interlacing inequalities we have √ ns n-j = s n-j (X (n) + R) ≥ s n-j (B) for j ≥ ⌊i/2⌋. Let H j , j = 1, . . . , k be the subspace of C n spanned by all the rows of B except for the j-th one. By [32, Lemma A4], dist(Z j , H j ) -2 .

By Lemma 5.1, for each j ≤ k, dist(Z j , H j ) ≥ c √ nk + 1 ≥ c √ i with probability at least 1 -2 exp(-ci/K 2 n ) ≥ 1 -2 exp(-cn γ /K 2 n ). (Note that we can use the lemma here thanks to exchangeability of the rows of the matrix). By the union bound, with probability at least 1 -2n exp(-cn γ /K 2 n ), we get

k j=1 s j (B) -2 ≤ C k i .
On the other hand, the left-hand side above is at least s n-i (B) -2 (k-n+i) ≥ s n-i (B) -2 i/2. This gives that with probability at least 1 -2n exp(-cn γ /K 2 n ), ns 2 n-i ≥ s n-i (B) 2 ≥ c i 2 n -⌊n γ /2⌋ , which implies that s n-i ≥ c i n . Taking another union bound over all i ≥ n γ we obtain that s n-i ≥ c i n for all n γ ≤ i ≤ n -1 with probability at least 1 -2n 2 exp(-cn γ /K 2 n ). For some γ ∈ (0, 1), we have γ -2/(2 + δ) > 0 and so by the assumption on K n , 2n 2 exp(-cn γ /K 2 n ) → 0, which ends the proof.

Conclusion of the proof of Theorem 1.2. Recall that we have to prove (ii). By Markov's inequality it suffices to show that for some α > 0 and some constant C z , (s α i + s -α i ).

Note also that for all α ∈ (0, 2] we have

1 n n i=1 s α i 2/α ≤ 1 n n i=1 s 2 i = n -1 A (n) -zId n 2 HS ≤ 2|z| 2 + 2n -2 n i,j=1 |x (n) ij | 2 = 2|z| 2 + 2. ( 30
)
As for the other sum, by the estimate of Theorem 4.1 together with the assumption on K n we have with probability tending to one for some finite constant β > 0, s n ≥ n -β .

Combining this with Lemma 5.2 we get with probability tending to one,

1 n n i=1 s -α i = 1 n ⌊n γ ⌋ i=0 s -α n-i + 1 n n-1 i=⌊n γ ⌋+1 s -α n-i ≤ 1 n n βα n γ + 1 n C n-1 i=⌊n γ ⌋+1 n i α ≤ n βα+γ-1 + C α n α-1 n 1-α ≤ C α
for α small enough. Together with [START_REF] Tao | The condition number of a randomly perturbed matrix[END_REF] this gives (ii), and Theorem 1.2 is proved.

6. Proof of Theorem 1.3 (circular law for the second model)

Proof of Theorem 1.3. Let d be any distance metrizing the weak convergence of probability measures on C, such as the bounded-Lipschitz distance (also referred to as the Fortet-Mourier distance by some authors). Let M n (δ) be the set of all n × n matrices x, satisfying (A1-A2) with K n ≤ n 1/(10+δ/3) . Let us denote by A (n) (x) = n -1/2 X (n) (x) the matrix constructed from x as in (2). Theorem 1.2 implies that for any δ > 0 and ε > 0 sup x∈Mn(δ) P(d(ν A (n) (x) , ν circ ) > ε) → 0 as n → ∞. Indeed if for some ε there exists a sequence n k → ∞ and n k × n k matrices

x n k such that P(d(ν A (n k ) (xn k ) , ν circ ) > ε) > ε, then we can complete this sequence to a sequence x n , n ≥ 1, violating Theorem 1.2. Consider now the matrices B (n) and for any n define the event

∆ n = {max i,j≤n σ -1 n |Y (n) ij -µ n | ≤ n 1/(10+δ/3) }.
Note that by the union bound, Markov's inequality and exchangeability

P(∆ ′ n ) ≤ n 2 sup m E σ -1 m |Y (

  distribution of the singular values of shifts 6 3. Combinatorial Talagrand's concentration inequality 9 4. Proof of Theorem 1.1 (smallest singular value) 10 5. Proof of Theorem 1.2 (circular law for the first model) 17 6. Proof of Theorem 1.3 (circular law for the second model) 20 References 21

  ) 1≤i≤n,1≤j≤k and I ⊆ [n], then we denote by M |I the submatrix (M ij ) i∈I,1≤j≤k of M formed by the rows of M labeled by I.

Lemma 4. 3 (

 3 Compressible vectors). For all α ∈ (0, 1], for all I ⊆ [n], such that #I ≥ αn, for every z

Remark 4. 5 (

 5 Conditional expectation). Before we proceed with the proof let us make a comment concerning conditional expectation. Namely, in the proof of Theorem 4.1 as well as in other proofs in the article we will encounter a situation in which a deterministic set E ⊂ [n] × [n] is given and in addition one considers a random set F ⊆ ([n] × [n]

√#I 1 I

 1 which implies that dist(η |I , y) ≤ r, where y is the orthogonal projection of η |I onto span(1 I ). Since |η |I | ≤ 1 we have |y| ≤ 1, so y = ξ for some ξ with |ξ| ≤ 1, which gives a contradiction.

Lemma 5 . 1 (

 51 Distance to a random subspace). Let R be a deterministic n × n matrix. Denote the rows of X (n) + R by Z 1 , . . . , Z n . Consider k ≤ n -1 and let H be the random subspace of C n spanned by Z 1 , . . . , Z k . Then with probability at least 1

Lemma 5 . 2 (

 52 Lower bound on the intermediate singular values). Let s 1 ≥ . . . ≥ s n be the singular values of A

  + s -α )dν z,n (s) > C z = 0.Note that, using the notation of Lemma 5.2, we have∞ 0 (s α + s -α )dν z,n (s) = 1 n n i=1

  π n be a random (uniform) permutation of[n] × [n], independent of B (n) . Since B(n) = 1 √ nσ n (Y (n) πn(i,j)µ n ) 1≤i,j≤nhas the same distribution as B(n) , it is enough to show that ν B(n) converges weakly in probability to the circular law. By the Fubini theorem we have for any ε > 0,P(d(ν B(n) , ν circ ) > ε) ≤ P(∆ ′ n ) + E B P πn (d(ν B(n) , ν circ ) > ε)1 ∆n ≤ P(∆ ′ n ) + sup x∈Mn(δ) P(d(ν A (n) (x) , ν circ ) > ε) → 0.

  Uniform integrability. For all z ∈ C, the function s → log(s) is uniformly integrable in probability with respect to the family of measures {ν z,n } n≥1 , i.e.

		2 (1 -|z| 2 ) otherwise;
	(ii) ∀ε > 0, lim t→∞	lim sup n→∞


Francesco Amoroso
email: amoroso@math.unicaen.fr

Filippo A E Nuccio
email: nuccio@mat.uniroma1.it

Algebraic Numbers of Small Weil's height in CM-fields: on a Theorem of Schinzel

Introduction

Let K be a CM-field. A. Schinzel proved ([Sch 1973]) that the Weil height of non-zero algebraic numbers in K is bounded from below by an absolute constant C outside the set of algebraic numbers such that |α| = 1 (since K is CM, |α| = 1 for some archimedean place guarantees |α| = 1 for all archimedean places). More precisely, his result reads as follows: for any α ∈ K × , |α| = 1, we have

h(α) ≥ C := 1 2 log 1 + √ 5 2 .
E. Bombieri and U. Zannier, motivated also by the above result, asked (private communication to the first author) for an absolute lower bound for the height of non-zero algebraic numbers lying in a complex abelian extension outside the set of roots of unity. This question was solved by R. Dvornicich and the first author (see [AmoDvo 2000]), who proved that for any α in a complex abelian extension, α = 0 and α not a root of unity, we have h(α) ≥ C ab := log 5 12 .

In the same paper it was shown that C ab cannot be replaced by any constant > (log 7)/12, since there exists an element α in a cyclotomic field such that h(α) = (log 7)/12; we note that (log 7)/12 < C.

One may now ask wether the abelianity condition is necessary for this latter lower bound or if this bound holds in general for CM fields. As a first step towards an answer, in his Master Thesis ([Nuc 2004]) the second author uses the classification of all dihedral principal CM fields given by S. Louboutin and R. Okazaky (see [LouOka 1994]) to prove the following: Theorem 1.1 There exists a normal CM-field L (of degree 8 and such that Gal(L/Q) ∼ = D 4 , the dihedral group of order 8) whose ring of integers O L contains an element γ of height

h(γ/γ) = log |N L Q (γ)| [L : Q] = log 2 8 < C ab .
Motivated by this example, we formulate the following natural question in this contest:

Question 1.2 Does there exist an absolute constant C CM ∈ (0, C ab ) such that for every CM field K and for every α ∈ K × \ K tors , h(α) > C CM holds?

We prove the following theorem, which gives a negative answer to the previous question:

Theorem 1.3 There exists an infinite sequence (α k ) of algebraic numbers such that the fields Q(α k ) are CM-fields, α k is not a root of unity,

d k = [Q(α k ) : Q] → +∞ and h(α k ) ∼ log(d k ) d k = o(1) as k → +∞.
As an application of the main theorem in [AmoDvo 2000], a lower bound for the norm of algebraic integers γ such that γ/γ is not a root of unity was given (see [AmoDvo 2000], Corollary 1):

Theorem (Amoroso-Dvornicich) Let γ be an integer lying in an abelian extension L of Q. Then, if γ/γ is not a root of unity,

log |N L Q (γ)| [L : Q] ≥ log 5 12 .
Our result allows us to show that also this bound is not anymore true if the abelianity condition is dropped (see Theorem 5.1).

Our proof relies on elementary facts about reciprocal polynomials and on an operator δ introduced by the first author (see [Amo 1995]). We will construct two families of polynomials having all their roots on the unit circle and with "small" leading coefficient. We will eventually show that these polynomials are either irreducible or have a (non monic) irreducible factor of high degree: this will ensure their roots have small height. Moreover, having all their roots on the unit circle, the fields defined by those polynomials are CM-fields.

The paper is organized as follows: in section 2 we recall some basic facts on Weil's height and on CM-fields and we introduce δ. The third section is devoted to the dihedral example. In the two following sections, we produce the two families mentioned above. Finally, in the last section, we propose a conjecture about polynomials defining CM-fields.

Acknowledgement. We are indebted to D. Simon for a useful discussion about Theorem 5.1. The second author is also grateful to J. Cougnard for enlightening comments on Section 3. We are finally indebted to the Referee for several useful suggestions, specially for the remark following conjecture 6.1.

Auxiliary results

Weil's height

Let α ∈ Q and let K be a number field containing α. We denote by M K the set of places of K. For v ∈ K, let K v be the completion of K at v and let | • | v be the (normalized) absolute value of the place v. Hence, if v is an archimedean place associated with the embedding σ :

K ֒→ Q |α| v = |σα|,
and, if v is a non archimedean place associated with the prime ideal p over the rational prime p,

|α| v = p -λ/e ,
where e is the ramification index of p over p and λ is the exponent of p in the factorization of the ideal (α) in the ring of integers of K. This standard normalization agrees with the product formula

v∈M K |α| [Kv:Qv] v = 1
which holds for α ∈ K × . We define the (Weil) height of α by

h(α) = 1 [K : Q] v∈M K [K v : Q v ] log max{|α| v , 1}.
It is easy to check that h(ζ) = 0 for every root of unity ζ ∈ Q: it is in fact equivalent to Kronecker's Theorem.

For further references we also need (see for instance [Wal 2000], chapitre 3):

Remark 2.1 Let α be a non-zero algebraic number and let P (X) ∈ Z[X] be its minimal polynomial over the integers, i.e. P (α) = 0 and P is irreducible admitting a factorization (in

Q) P (X) = ℓ i (X -α i ). Let K = Q(α); then log ℓ i max(1, |α i |) [K : Q] = 1 [K : Q] v∈M K , v∤∞ [K v : Q v ] log max{|α| v , 1} = h(α).

Reciprocal polynomials and CM fields

We now recall some basic facts about reciprocal and antireciprocal polynomials.

Definition 2.2 Let P (X) ∈ C[X] be a polynomial of degree d. If P (X) = X d P (X -1 ), then P is said to be reciprocal. If P (X) = -X d P (X -1 ), it is said to be antireciprocal.
Let us emphasise that the factors of a reciprocal or antireciprocal polynomial with real coefficients should have specific form. Firstly, if P (X) ∈ R[X] is a reciprocal (or antireciprocal) polynomial of degree d and α is a root of P , then α = 0 and α -1 is still a root of P . If now P (±1) = 0, the distinct values {α, α -1 } are two roots of the polynomial having the same multiplicity and the polynomial is reciprocal of even degree, all of its roots being "coupled". We can then factorise a general reciprocal (or antireciprocal) polynomial P as

P (X) = (X -1) a (X + 1) b Q(X)
where Q(X) is reciprocal not vanishing at ±1 of degree 2k and d = a+b+2k. Moreover, a ≡ 1 mod 2 if P is antireciprocal and b ≡ 1 mod 2 if P is reciprocal of odd degree or if it is antireciprocal of even degree.

A totally imaginary quadratic extension K of a totally real number field K + is said to be a CM-field. As mentioned in the introduction, one of the main properties of CM-fields is the following: let α ∈ K and assume that |τ α| = 1 for some embedding τ ; then for any embedding σ we have |σα| = 1. Indeed, the complex conjugation induces an automorphism on K which is independent of the embedding into C (see [Was 1982], p.38). The following characterisation of CM-fields will be useful in our main construction:

Proposition 2.3 A number field K = Q is CM if and only if there exists a monogenic 1 element α ∈ K such that |σα| = 1 for all embedding σ.
Proof : Let K be a CM-field and let γ ∈ K be a monogenic element. For n ∈ Z we put

α n = γ + n γ + n .
Clearly, |σα n | = 1 for every σ. In order to show that some α n is monogenic, let us point out that there are two different integers n, m ∈ Z such that

α n = α m and Q(α n ) = Q(α m ), since the number of subfields of K is finite. Therefore, γ = mα n (1 -α m ) -nα m (1 -α n ) α m -α n ∈ Q(α n ) and K = Q(α n ).
Conversely, let us assume that K = Q(α) where |σα| = 1 for all embedding σ. Put

K + = Q(α + α -1 ) ;
then K + is a totally real field and [K :

K + ] = 2, because α / ∈ R and K = Q. Q.E.D.
Thus, a CM field can be defined by an irreducible polynomial P ∈ Q[X] vanishing only on the unit circle. We also remark that such a polynomial must be reciprocal, since |α| = 1 ⇒ ᾱ = α -1 .

A Differential Operator

We now introduce an operator δ (see [Amo 1995]) over C[X] which has all the properties of a derivation but linearity: if P (X) ∈ C[X] is a polynomial with complex coefficients of degree d (we set deg(0) = 0), we define

δ(P )(X) = X dP dX (X) - d 2 P (X) .
It is obvious that, if we denote by p d the leading coefficient of P , the leading coefficient of δ(P ) is dp d /2, and that δ(P ) and P have the same degree. Moreover, a classical property of a derivation is satisfied:

δ(P Q) = δ(P )Q + δ(Q)P ; therefore, for n ∈ N, δ(P n ) = nP n-1 δ(P ) .
The following remark (due to D. Simon) can also be useful. Let D the derivation

D(F ) = 1 2 X ∂F ∂X -Y ∂F ∂Y on C[X, Y ]. Then for any P ∈ C[X] we have δ(P )(X) = D( h P )(X, 1), where h P (X, Y ) = Y deg(P ) P (X/Y ) is the homogenization of P .
Having recalled all these basic facts, we can prove the main property of the operator δ (see also [Amo 1995], Prop. 1): Lemma 2.4 Let P (X) ∈ C[X] be a reciprocal polynomial (resp. antireciprocal) having all its roots on the unit circle. Then δ(P )(X) is an antireciprocal (resp. reciprocal) polynomial whose roots still lie on the unit circle. Moreover, if α 1 , . . . , α k are the distinct roots of P (X) of multiplicity m 1 , . . . , m k , then δ(P )(X) vanishes at α j with multiplicity m j -1 for j = 1, . . . , k, and at certain β 1 , . . . , β k with multiplicity equal to 1. Finally, the set {α 1 , . . . , α k } and {β 1 , . . . , β k } are intercalated. 2Proof : We begin by showing that δ transforms reciprocal polynomials to antireciprocal ones, and vice versa: directly from the definition, it is clear that the condition of being reciprocal (resp. antireciprocal) for a polynomial

P (X) = d j=0 a j X j
turns out to be a j = a d-j (resp. a j = -a d-j ). Looking closely at the definition of δ and setting

δ(P )(X) = d j=0 b j X j ,
it is clear that for j = 1, . . . , d we have b j = (j -d/2)a j and therefore

b d-j = (d -j -d/2)a d-j = (d/2 -j)a d-j .
Thus, when P is reciprocal, a j = a d-j implies b j = -b d-j and so δ(P ) is antireciprocal; and when P is antireciprocal, a j = -a d-j implies b j = b d-j and so δ(P ) is reciprocal.

Let us now suppose P to be a reciprocal polynomial of degree d and let α j = e iϑ j : then

f (t) = e -i d 2 t P (e it )
is a periodic real function (in fact f (t) = e i d 2 t P (e -it ) = f (t)) of period equal to 2π which vanishes at {ϑ 1 , . . . , ϑ k } ⊂ [0, 2π). Thanks to Rolle's Theorem, f ′ (t) vanishes at certain {φ 1 , . . . , φ k } and the sets {e iϑ 1 , . . . , e iϑ k } and {e iφ 1 , . . . , e iφ k } are intercalated. But

f ′ (t) = d dt e -i d 2 t P (e it ) = e -i d 2 t dP (e it ) dt -i d 2 e -i d 2 t P (e it ) = ie it-i d 2 t P ′ (e it ) -i d 2 e -i d 2 t P (e it ) = ie -i d 2 t e it P ′ (e it ) - d 2 P (e it ) = ie -i d 2 t δ(P )(e it ), (2.1)
and so {e iφ 1 , . . . , e iφ k } are roots of δ(P ). But, if e iϑ j is a root of P (X) having multiplicity m j , then e iϑ j is a root of P ′ (X) having exact multiplicity equal to m j -1; hence we see, from (2.1), that e iϑ j is a root of δ(P )(X) having multiplicity m j -1. Finally deg δ(P ) = deg(P ) = d, and so the relation

d = k + (m 1 -1) + • • • + (m k -1)
shows that δ(P )(X) can have no other roots, and that {e iφ 1 , . . . , e iφ k } are simple roots.

If P were antireciprocal the same argument would lead to our conclusion, using the function g(t) = if (t).

Q.E.D.

A Dihedral Example

The main idea for this construction is the relation between the norm and the height of certain algebraic numbers pointed out in [AmoDvo 2000], Corollary 1: if γ is an algebraic integer of a CM-field K such that the ideals (γ) and (γ) are coprime (and then γ/γ is not a root of unity), then

h(γ/γ) = log |N K Q (γ)| [K : Q] . (3.1)
Working in principal fields one has elements of norm p for each prime p|p, provided its inertial degree equals 1, and relation (3.1) may therefore be easily employed. We shall then consider (letting notations be as in [LouOka 1994]), the fields L p,q , which are the unique cyclic quartic extensions of Q( √ pq) unramified at the finite places and are dihedral octic CM-fields. In the sequel e K F (f), f K F (f) (or simply e(f), f (f) when there is no ambiguity) will denote ramification index and inertial degree, respectively, of a prime ideal f ⊆ O K in an extension K/F: moreover, we will feel free to write e(ℓ), f (ℓ) for some rational prime ℓ when considering normal extensions K/Q.

Looking for elements whose height is smaller than the constant C ab quoted in the introduction, we want log ℓ 8 < log 5 12 , that forces ℓ = 2; since we should require f (2) = 1 in order to use (3.1), we need f

Q( √ pq) Q
= 1, i.e. either p, q ≡ 1 mod 2 or p = 2 and q ≡ 1 mod 2. Compairing these conditions with the list of all dihedral octic principal CMfields given in the paper [START_REF] Louoka | [END_REF], the only fields we can consider are the L p,q with p < q and (p, q) ∈ (2, 17), (2, 73), (2, 89), (2, 233), (2, 281), (17, 137), (73, 97) .

Claim 3.1 f L 2,17 Q (2) = 1.
We shall prove Claim 3.1 later on, and use it now to prove Theorem 1.1: from now on, we set L := L 2,17 .

Proof of Theorem 1.1: First of all, e L Q (2) = 2, because L/Q( √ 34
) is unramified at the finite places; indeed, Claim 3.1 implies that the prime 2 is factorised in

O L as 2O L = (p 1 p 2 p 3 p 4 ) 2 .
and we will fix the four primes {p i } 4 i=1 from now on. Let us emphasize that, having Gal(L/Q) ∼ = D 4 , the Galois structure of the extension is as follows:

L o o o o o o o o o o o o o o o o o o o o o o o o o o o o o
x x x x x x x x x x x x x x x x x x x 2 q q q q q q q q q q q q q q q q q q q q

K 1 T T T T T T T T T T T T T T K 2 Q( √ 2, √ 17
F 1 F 2 × × × × × × × × × × × × × × Q( √ 2
Q( √ 34) 2 Q( √ 17)
w w w w w w w w w w w w w w w w w w w Q where K 1 ∼ = K 2 ≇ F 1 ∼ = F 2 are non-normal quartic CM-fields. If D i denotes the decomposition subgroup at p i for i = 1, . . . , 4, the conditions f (2) = 1 and e(2) = 2 imply that |D i | = 2 for i = 1, . . . , 4. We need only to show that for at least one (and then for all) index i, the complex conjugation χ does not belong to D i , because then the ideals p i and χ(p i ) = p i will be coprime. If L i := L D i are the decomposition subfields and we fix an index i, it is well known that

p i ∩ O L i is unramified in L i /Q and that e(p i ∩ O L i ) = e(p i ) = 2 in L/L i : since L/Q( √ 34
) is unramified at the finite places, we cannot have

L ⊃ L i ⊃ Q( √ 34)
and therefore L i = L + = L {e,χ} , showing that χ / ∈ D i for all i. Therefore, if (γ) = p 1 , the ideals (γ) and (γ) are coprime, and (3.1) gives

h(γ/γ) = log |N L Q (γ)| [L : Q] = log 2 8 < C ab .
Q.E.D.

Concerning Claim 3.1, an easy computation made with Pari-GP allows one to obtain much more: (2, 17) is the only pair of primes such that f Lp,q Q (2) = 1. But within the scope of our construction, it is enough to show that the inertial degree of (2) in L 2,17 equals 1 since examples in other fields would not have smaller height, because [L p,q : Q] = 8 for all (p, q) and this can be shown in a much more theoretical way, as follows.

Theorem (7) of [START_REF] Louoka | [END_REF]] explicitly gives the construction of L p,q , defining them as the unique cyclic quartic extension of Q( √ qp) unramified at finite places. In particular, they are precisely the ray class fields for the modulus m = ∞ of Q( √ qp): therefore, Class Field Theory gives an isomorphism between their Galois groups over Q( √ qp) and the narrow class group C + of Q( √ qp) via Artin recpirocity map:

ϕ : C + ∼ = -→ Gal(L p,q /Q( √ qp)) p -→ (p, Gal(L p,q /Q( √ qp)))
where (p, Gal(L p,q /Q( √ qp))) is the Frobenius of the prime p in the abelian extension L p,q /Q( √ qp). Since inertial degree of a prime coincides with the order of its Frobenius, it suffices to verify that the primes over (2) in Q( √ pq)

become trivial in the narrow class group -i.e. they have a totally positive generator -to establish Claim 3.1. Throughout we fix (p, q) = (2, 17) and we set L := L 2,17 . It is well known (see, for instance, [Coh 1980 ) is totally positive, so that ϕ(6 + √ 34) = 1 and Claim 3.1 is established. Actually, the same computation may be performed to show that L is the only field satisfying our condition, but it becomes much longer: the key point is that 34 is the only product pq of primes in our list being ≡ -2 modulo a perfect square.

]) that (2)O Q( √ 34) = (2, √ 34

A First Family

We are now ready to produce the first family of polynomials that we have mentioned in the introduction. Proof of Theorem 1.3:

For n ∈ N, n ≥ 2 we put Φ n (X) = m≤n φ m (X),
(where φ m (X) is the m-th cyclotomic polynomial) and let 2s(n) = 2s denote its degree. An elementary estimate (see for instance [START_REF] Harwri | [END_REF]

define R n (X) = (X -1) 2r Φ n (X) ∈ Z[X] . Claim 4.1 At most one cyclotomic polynomial φ ν (X) = X -1 may divide δ(R n ), in which case n ≤ ν ≤ c 1 n log n
, where c 1 is some positive absolute constant.

Lemma 2.4 gives φ ν ∤ R n for ν = 2, . . . n. On the other hand, assume ν > c 1 n log n and let p be the smallest prime not dividing ν. Then, by elementary number theory, p ≤ c 2 log n for some absolute constant c 2 > 0. Therefore, if c 1 is sufficiently large, ν/p > n. If we had φ ν | δ(R n ), then the polynomial δ(R n ) would have two roots e 2πi/ν and e 2pπi/ν lying on the unit circle and such that no root of R n would lie between them all along the unit circle (since 0 < 1/ν < p/ν < 1/n) , thus contradicting Lemma 2.4. For the same argument, if we had φ l φ ν | δ(R n ), with l > ν, we would find two roots {e 2πi/ν , e 2πi/l } having no root of R n between them, which is also absurd by Lemma 2.4. Finally, again by the same Lemma, φ 2 ν ∤ δ(R n ) for ν > n, because of the bound for roots multiplicity of δ(R n ). Claim 4.1 is then established.

We may therefore factorise δ(R n ) as

δ(R n )(X) = (X -1) 2r φ ν (X) ǫ P n (X),
where n < ν < c 1 n log n and ǫ ∈ {0, 1}. Moreover, the leading coefficient δ(R n ) is equal to the prime ℓ = r + s, and so P n (X) is an irreducible polynomial of degree d, where for n → +∞. Let α n be a root of P n ; the field

d = 2s -ǫϕ(ν) ∈ 2s -c 1 n log n, 2s . But s ≤ ℓ <
K n = Q(α n ),
is a CM-field (by Proposition 2.3). Moreover, since the only contribution to Weil's height of α n (of absolute value 1) comes from the non-archimedean places and since P n has leading coefficient ℓ,

h(α n ) = log ℓ d ∼ log d d (see remark 2.1).
Q.E.D.

A Second Family

Although the preceding construction already shows the impossibility of finding an absolute lower bound for Weil's height in non necessarily normal CMfields (the case of a normal non-abelian CM-field being still open), we shall present a second family of polynomials which shows that also the bound given by the theorem of Dvornicich and the first author quoted in the introduction is not anymore true if the abelianity condition is dropped.

Theorem 5.1 There exists a sequence (α p ) (p prime ≥ 5) of algebraic numbers such that:

• the fields E p = Q(α p ) are CM-fields of degree p -1;

• we have h(α p ) = (log p)/(p -1);

• γ p = 1/(α p -1) is an algebraic integer, γp /γ p = -α p and

N Ep Q (γ p ) = p .
Proof : Let p ≥ 5 be a prime number. Since (X -1)φ 2p (X) is antireciprocal of odd degree, Lemma 2.4 and the remarks following Definition 2.2 ensure that R p (X) := 2δ (X -1)φ 2p (X) X + 1 .

is a polynomial with integer coefficients, not vanishing at ±1.

Claim 5.2 The polynomials R p are irreducible.

Reducing R p mod p is an easy task, which we can fulfill by simply pointing out that φ 2p (X) ≡ (X + 1) p-1 mod p and so (p -1)(X + 1) p-2 2δ(X + 1) ≡ 2δ φ 2p (X) ≡ -(X + 1) p-2 (X -1) mod p ,

We finally remark that γp /γ p = (α p -1)/( ᾱp -1) = -α p , since |α p | = 1.

Q.E.D.

Remark 5.3 The existence of the element γ p shows that in the trivial class of the ideals class group of E p there are always two primes over p. More precisely, it could be proved (using for instance the results of [START_REF] Deldvosim | [END_REF]) that the prime p splits in the ring of integers of E p as p 1 p 2 p p-3

3
where p 1 = (1/(α p -1)) and p 2 = p 1 = (α p /(α p -1)): the fields E p are therefore far from being normal over Q.

6 A Conjecture on polynomials defining CM-fields

Let Cycl = φ e 1 1 • • • φ e k k
, such that k ∈ N and e 1 , . . . , e k ∈ N . be the set of products of cyclotomic polynomials. The possibility of finding these families of CM-fields defined by polinomials in the image δ Cycl leads us to suppose that every CM-field may be otained in such a fashion. Some computations suggest thus to propose the following conjecture: Conjecture 6.1 Let K be a CM-field defined by a root of an irreducible polynomial P ∈ Z[X]. Then there exist Φ, Φ ∈ Cycl and a rational r such that δ(Φ) = r ΦP .

Moreover, we can perhaps choose r = ±1.

Let P as in conjecture 6.1 and assume that there exist Φ, Φ ∈ Cycl and a rational r such that δ(Φ) = r ΦP .

Let m ∈ N and put P m (X) = P (X m ), Φ m (X) = Φ(X m ) and Φm (X) = Φ(X m ). Then the polynomial P m defines again a CM field and δ(Φ m ) = rm Φm P m , which gives some evidence to conjecture 6.1.

  2s and thus, thanks to (4.1), ℓ = d + O( √ d) : then we have log ℓ ∼ log d

  )

	p p p p p p p p p p p p p p p p p p p

  Postulate (op. cit., Theorem 418), for all n there exists a natural integer r < s such that r + s := ℓ is a prime number: we

			], Theorem
	330) gives
	2s =	3n 2 π 2 + O n log n .	(4.1)
	According to Bertrand's

We say that α in a number field K is monogenic when K = Q(α).

Two finite sets S, T ⊂ {z ∈ C, |z| = 1} are intercalated if they have the same cardinality and if there is one, and only one, α ∈ S between each pair of consecutive β, β ′ ∈ T along the unit circle.

which finally gives (X + 1)R p (X) = 2δ(X -1)φ 2p (X) + 2(X -1)δ φ 2p (X) ≡ (X + 1) p -(X + 1) p-2 (X -1) 2 mod p ≡ 4X(X + 1) p-2 mod p and the factorization of

(5.1)

Since the leading coefficient of R p is precisely p, the irreducibility of R p will follow as soon as we show that it has no cyclotomic factors. Indeed, let us suppose that φ n (X) | R p (X). Since R p (±1) = 0, we have n ≥ 3; but then equation (5.1) forces the condition φ n (-1) ≡ 0 mod p. It is well known (see [Apo 1970]) that this condition is verified if and only if n = 2p m , while

, which is absurd by Lemma 2.4. Claim 5.2 follows.

The arguments of Section 4 now imply that the polynomials R p define CM-fields E p of degree p -1 which contain elements α p (the roots of R p (X)) whose heights are

We now prove that γ p = 1/(α p -1) is an algebraic integer of norm p. Indeed, γ p is a root of

The leading coefficient of (α i -1) -1 = pR p (1) -1 = p .