Sara Checcoli
email: sara.checcoli@gmail.com

Pierre D Èbes
email: pierre.debes@univ-lille1.fr

TCHEBOTAREV THEOREMS FOR FUNCTION FIELDS

Keywords: Mathematics Subject Classification. Primary 11R58, 12F10, 12E25, 12E30; Secondary 14Gxx, 14E20 specialization of Galois extensions, function fields, Tchebotarev property, Hilbert's irreducibility theorem, local and global fields

We prove Tchebotarev type theorems for function field extensions over various base fields: number fields, finite fields, padic fields, PAC fields, etc. The Tchebotarev conclusion -existence of appropriate cyclic residue extensions -also compares to the Hilbert specialization property. It is more local but holds in more situations and extends to infinite extensions. For a function field extension satisfying the Tchebotarev conclusion, the exponent of the Galois group is bounded by the l.c.m. of the local specialization degrees. Further local-global questions arise for which we provide answers, examples and counter-examples.

Introduction

The central theme is the specialization of algebraic function field extensions, finite or infinite, and our main results are Tchebotarev type statements, for certain base fields (possibly infinite).

Fix a field K, a smooth projective and geometrically integral Kvariety B (typically B = P 1 K ) and a Galois extension F/K(B) of group G. For every overfield k ⊃ K and each point t 0 ∈ B(k), there is a notion of k-specialization of F/K(B) at t 0 ( §2.1.2); it is a Galois extension F t 0 of k of group contained in G, well-defined up to conjugation by elements of G. For example, if B = P 1 K and F/K(B) is finite and given by an irreducible polynomial P (T, Y ) ∈ K(T )[Y ], then for all but finitely many t 0 ∈ P 1 (k), the k-specialization F t 0 /k is the extension of k associated with the polynomial

P (t 0 , Y ) ∈ k[Y ].
The leading question is to compare the Galois groups of the specializations with the "generic" Galois group G. The Hilbert specialization property is that the "special" groups equal G for "many" specializations over k = K. Standard situations with the Hilbert property have the base field K hilbertian (e.g. a number field), the base variety B K-rational (e.g. B = P 1 ) and concerns finite extensions F/K(B).

We introduce another specialization property, which we call the Tchebotarev existence property (definition 2.4). For finite extensions, it is a function field analog of the existence part in the Tchebotarev density theorem for number field extensions. Namely we request that every conjugacy class of cyclic subgroups of G be the Frobenius class of some suitable specialization F t 0 /k of F/K(B) in some local field over K. By "suitable" we mean "unramified and cyclic" and "the Frobenius class of F t 0 /k " is "the conjugacy class of Gal(F t 0 /k)". Our property is weaker than the Hilbert property in the sense that it only preserves the "local" structures, but it allows more general base fields and base varieties and still encapsulates a good part of the Hilbert property; and it is also defined for infinite extensions.

A main feature of an extension F/K(B) with the Tchebotarev property is that it has suitable specializations with any prescribed cyclic subgroup of G as Galois group; see §2 for precise statements. We have this practical consequence (proposition 2.8): if (Ub-loc-d) the local degrees of F/K(B) are uniformly bounded, where by local degrees we mean the degrees of all the "suitable local specializations" of F/K(B), then (exp-f) the exponent of G is finite.

Furthermore the converse (exp-f) ⇒ (Ub-loc-d) holds too under some standard assumptions on K. Finally if G is abelian, (Ub-loc-d) implies not only (exp-f) but the following stronger condition: (d) for some integer d ≥ 1.

F ⊂ K(B)
where given an integer d ≥ 1, K(B) (d) denotes the compositum of all finite extensions of K(B) of degree ≤ d (corollary 2.9).

These results were established by the first author and U. Zannier in the situation F/K(B) is a number field extension F/K [START_REF] Checcoli | On fields of algebraic numbers with bounded local degree[END_REF], [START_REF] Checcoli | Fields of algebraic numbers with bounded local degree and their properties[END_REF]. It turns out that the core of their arguments is the Tchebotarev property that we have identified. §2 offers a formal set-up around the property and its consequences which includes both the original number field and the new function field situations.

Then in §3 we prove our "Tchebotarev theorems for function fields", which provide concrete situations where the property holds. Theorem 3.1 and corollary 3.2 show that a finite regular extension F/K(T ) (here B = P 1 for simplicity) always has the Tchebotarev existence property if K is a number field or a finite field or a PAC field 1 with cyclic extensions of any degree or a rational function field κ(x) with κ a finite field of prime-to-|G| order, etc. With some extra good reduction condition on F/K(B), the property is also shown to hold if K is a p-adic field or a formal Laurent series field with coefficients in a finite field, etc. To our knowledge only the finite field case was covered in the literature.

In §4, we compare our Tchebotarev property with the classical Hilbert specialization property. The situation is clear for PAC fields for which both properties correspond to well-identified properties of the absolute Galois group of the base field K (proposition 4.1). The general situation is more complex; some of the PAC conclusions still hold, others do not, and some are unclear ( §4.2). Still we prove that the Hilbert property is somehow squeezed between two variants of the Tchebotarev property (proposition 4.3).

§5 is devoted to another natural question about the above conditions (Ub-loc-d) and (F ⊂ K(B) (d) for some d), which is whether the former implies the latter in general, i.e., without assuming G abelian. The answer is "No"; counter-examples are given in the context of number field extensions in the Checcoli-Zannier papers. We construct other counter-examples in the situation where dim(B) > 0. One of them is re-used in a remark on a geometric analog of the Bogomolov property (definition recalled in §5.4.1).

Acknowledgments. We are grateful to Lior Bary-Soroker for his help with §4. Our thanks also go to Moshe Jarden and Lorenzo Ramero for their interest in the paper and several valuable references.

The Tchebotarev existence property

We define the Tchebotarev existence property for finite and infinite extensions and investigate its implications.

2.1. Preliminaries. Given a field k, we fix an algebraic closure k and denote the separable closure of k in k by k sep and its absolute Galois group by G k .

2.1.1. Local fields. Given a field K, what we call a local field over K is a finite extension k v of some completion K v of K for some discrete valuation v on K. The field k v is complete with respect to the unique prolongation of v to k v , which we still denote by v.

Fields K will be given with a set M of finite places of K (i.e. of equivalence classes of discrete valuations on K) called a localization set of K. A local field k v over K with v ∈ M is called a M-local field over K. When the context is clear, we will drop the reference to M.

Here are some typical examples.

Example 2.1. (a) A complete valued field K v for a non trivial discrete valuation v will be implicitly given with the localization set M = {v}. The M-local fields over K v are K v and its finite extensions.

(b) A number field K will be implicitly given with the localization set M consisting of all the finite places of K. The M-local fields over K are the non-archimedean completions of K and its finite extensions.

(c) If κ is a field and x an indeterminate, the rational function field κ(x) will be implicitly given with the localization set M consisting of all the (x -x 0 )-adic valuations where x 0 ranges over P 1 (κ) (with the usual convention that x -∞ = 1/x). The M-local fields over κ(x) are the fields κ((x -x 0 )) of formal Laurent series in x -x 0 with coefficients in κ and their finite extensions (x 0 ∈ P 1 (κ)).

(d) A field K, without any specification, will be implicitly given with the localization set M consisting of the sole trivial discrete valuation, denoted 0. The M-local fields over K are K and its finite extensions.

2.1.2. Local specializations and Frobenius subgroups. Suppose given a base field K, a smooth projective and geometrically integral K-variety B and a Galois extension F/K(B) of Galois group G.

The following notions are classical when the extension F/K(B) is finite and extend naturally to infinite extensions by writing F/K(B) as the union of an increasing sequence of finite Galois extensions.

Given a point t 0 ∈ B(K), we denote by F t 0 /K the specialization of F/K(B) at t 0 : if Spec(A) ⊂ B is some affine neighborhood of t 0 , A ′ F the integral closure of A in F , then F t 0 /K is the residue extension of the integral extension A ′ F /A at some prime ideal above the maximal ideal corresponding to t 0 in Spec(A). It is a normal extension well-defined up to conjugation by elements of G. Definition 2.2. Given an overfield k of K and t 0 ∈ B(k), the exten-

sion (F k) t 0 /k is called a k-specialization of F/K(B). If k v is a local field over K, points t 0 ∈ B(k v ) are called local points of B, the associ- ated k v -specializations (F k v ) t 0 /k v local specializations and the degrees [(F k v ) t 0 : k v ] local degrees of F/K(B).
Local degrees are to be understood as supernatural numbers [FJ04,

§22.8] if F/K(B) is infinite.
Denote the branch locus of F/K(B) by D, i.e., the formal sum of all hypersurfaces of B ⊗ K K sep such that the associated discrete valuations are ramified in the field extension F K sep /K sep (B). If the extension F/K(B) is finite, D is an effective divisor; in general D is an inductive limit of effective divisors.

Definition 2.3. Given a local field k v over K and a local point

t 0 ∈ B(k v ) \ D, the Galois group Gal((F k v ) t 0 /k v ) is called the Frobenius subgroup of F/K(B) at t 0 over k v . The local point t 0 ∈ B(k v ) \ D is said to be k v -unramified for the extension F/K(B) if the associated k v -specialization (F k v ) t 0 /k v is unramified 2 .
The Frobenius subgroup is a subgroup of G well-defined up to conjugation by elements of G. Its order is the local degree

[(F k v ) t 0 : k v ].
We use the phrase unramified local degree for this degree when t 0 is k v -unramified for F/K(B).

2.2.

The Tchebotarev existence property.

Finite extensions.

Definition 2.4. (a) If K is given with a localization set M, a finite Galois extension F/K(B) of group G is said to have the Tchebotarev existence property with respect to M if for every element g ∈ G, there exists a M-local field k v over K and a local point t 0 ∈ B(k v ) \ D, k vunramified for F/K(B), such that the Frobenius subgroup of F/K(B) at t 0 over k v is cyclic and conjugate to the subgroup g ⊂ G.

(b) We say further that F/K(B) has the strict Tchebotarev existence property if in addition to the above, the M-local fields k v can be taken to be completions K v of K (i.e., no finite extension is necessary).

Remark 2.5. If K is a number field or if K = κ(x) with G κ pro-cyclic, the Frobenius subgroups of F/K(B) at local points t 0 ∈ B(k v ) \ D, k v -unramified for F/K(B), are automatically cyclic as quotients of the pro-cyclic group Gal(k ur v /k v ) (with k ur v the unramified closure of k v ). Definition 2.4 is modelled upon the situation of number field extensions F/K. It is in fact a generalization: take B = Spec(K); for every finite place of K, there is only one point in B(K v ) = Spec(K v ) and the corresponding local specialization of F/K is the v-completion of F/K. From the classical Tchebotarev density theorem, Galois extensions of number fields indeed have the strict Tchebotarev existence property. 3 In this paper we will be more interested in function field extensions F/K(B) with dim(B) > 0. Concrete situations where the Tchebotarev existence property is satisfied are given in §3.

2.2.2. Infinite extensions. Definition 2.4 extends to infinite extensions. Definition 2.6. A Galois extension F/K(B) (possibly infinite) is said to have the Tchebotarev existence property (w.r.t. a localization set M of K) if F/K(B) is the union of an increasing sequence of finite Galois extensions F n /K(B) that all have the Tchebotarev existence property (w.r.t. M); and similarly for the strict Tchebotarev existence property.

This definition does not depend on the choice of the increasing sequence (F n /K(B)) n≥1 such that n≥1 F n = F . This follows from the fact (left as an exercise) that given two finite Galois extensions E/K(B) and

E ′ /K(B) such that E ′ ⊃ E, if E ′ /K(B)
has the Tchebotarev existence property (strict or not), then so does E/K(B).

2.3.

A local-global conclusion for infinite extensions. An immediate consequence of the Tchebotarev existence property is that for a finite Galois extension F/K(B) of group G, (*) the orders of elements of G are exactly the unramified M-local degrees of F/K(B) corresponding to cyclic Frobenius subgroups.

In particular the exponent of G is the l.c.m. of these local degrees. Proposition 2.8 below shows that conclusion (*) extends in some form to infinite extensions. The following definitions will be used.

Definition 2.7. A localization set M of a field K is said to be standard if the local fields k v are perfect and the absolute Galois groups G kv are of uniformly bounded rank (v ∈ M).

This holds in particular in the following situations: K is a number field, a p-adic field, a perfect field with absolute Galois group of finite rank (e.g. a finite field), a field K = κ(x) or K = κ((x)) with κ of characteristic 0 and with absolute Galois group G κ of finite rank, etc.

We also say that a family (d v ) v of positive integers indexed by v is uniformly bounded if there is a constant δ depending on F/K(B) but not on v such that all integers d v are ≤ δ. The special case of proposition 2.8 for which F/K(B) is a Galois extension F/K of number fields was proved in [START_REF] Checcoli | On fields of algebraic numbers with bounded local degree[END_REF] and [START_REF] Checcoli | Fields of algebraic numbers with bounded local degree and their properties[END_REF].

Proof of proposition 2.8. Write F/K(B) as an increasing union of finite Galois extensions F n /K(B) (n ≥ 1). Let g ∈ G. For each n ≥ 1, let g n be the projection of g onto Gal(F n /K(B)). From statement (*), for each n ≥ 1, the order of g n is the unramified local degree [(F n k v ) t 0 : k v ] for some place v ∈ M and some point t 0 ∈ B(k v )\D. In particular this order divides the local degree [(F k v ) t 0 : k v ]. This yields the following which compares to (*) above.

(**) the set of orders of elements of G is a subset of the set of all M-local degrees of F/K(B).

Implication (Ub-loc-d) ⇒ (exp-f) is an immediate consequence.
For the converse, we borrow an argument from [START_REF] Checcoli | Fields of algebraic numbers with bounded local degree and their properties[END_REF]. Let k v be a M-local field over K and

t 0 ∈ B(k v ). Fix n ≥ 1. Assume k v is perfect. Then (F n k v ) t 0 /k v is a finite Galois extension and the local degree [(F n k v ) t 0 : k v ] is the order of the group Gal((F n k v ) t 0 /k v ).
Assume further that there is a constant N depending only of F/K(B) such that G kv is of rank ≤ N. Then the finite group Gal((F n k v ) t 0 /k v ), a quotient of G kv , has a generating set with at most N elements. The group Gal((

F n k v ) t 0 /k v ) is also of exponent ≤ exp(G) (as a subgroup of Gal(F n /K(B)) which itself is a quotient of G). If exp(G)
is finite, it follows from the Restricted Burnside's Problem solved by Zelmanov (see e.g. [START_REF] Vaughan-Lee | The restricted Burnside problem[END_REF]) that the order of the group Gal((F n k v ) t 0 /k v ) can be bounded by a constant only depending on exp(G) and N.

The strict variant of implication (exp-f) ⇒ (Ub-loc-d) for which only the M-local degrees corresponding to completions of K are considered holds too if F/K(B) has the strict Tchebotarev property. The proof above can easily be adjusted.

A refined question. A special situation where the exponent of

G = Gal(F/K(B)) is finite is when F ⊂ K(B) (d) for some integer d ≥ 1. (Indeed the Galois group Gal(F/K(B)) is then a quotient of the group Gal((K(B) (d) /K(B)), which is of exponent ≤ d!).
The question then arises as to whether (Ub-loc-d) implies that F ⊂ K(B) (d) for some d. For number fields, counter-examples were given in [START_REF] Checcoli | On fields of algebraic numbers with bounded local degree[END_REF], [START_REF] Checcoli | Fields of algebraic numbers with bounded local degree and their properties[END_REF]. Constructing other counter-examples with dim(B) > 0 was a motivation for this work. §5 is devoted to this subtopic.

However the answer to the question is "Yes" if the group G is abelian. For number field extensions this was first proved in [START_REF] Checcoli | On fields of algebraic numbers with bounded local degree[END_REF].

Corollary 2.9. Let F/K(B) be a Galois extension with the Tchebotarev existence property. Assume that condition (Ub-loc-d) holds and that G = Gal(F/K(B) is abelian. Then F ⊂ K(B) (d) for some d. (d) for any d (as Z is of infinite exponent). This shows that the assumption that F/K(B) has the Tchebotarev property cannot be removed in corollary 2.9 or in implication (Ub-loc-d) ⇒ (exp-f).

Proof. From proposition 2.8, exp(G) is finite. As noted in [CZ11, prop. 2.1], this implies F ⊂ K(B) (d) for some d if G is abelian. If F = Q(T 1/∞ ) is the field generated over Q(T ) by all d-th roots of T , with d ∈ N * , the extension F/Q(T ) is abelian of group G ≃ Z, it satisfies condition (Ub-loc-d) (as Q is algebraically closed) but F ⊂ K(B)

Situations with the Tchebotarev property

Unless otherwise specified, we assume dim(B) > 0 in this section. In this function field context, we will mostly consider extensions F/K(B) that are regular over K (i.e. F/K(B) is separable and F ∩ K = K).

Main statements.

3.1.1. Main situations. Theorem 3.1 below is a central result of this paper: it provides various situations where the Tchebotarev existence property is satisfied. The proof of theorem 3.1 is given in §3.2.

Statement (c) uses the notion of a good place for the extension F/K(B). It is defined, in definition 3.5, by a set of conditions which classically guarantee good reduction of F/K(B) (residue characteristic prime to |G|, etc.).

Theorem 3.1. Let K be a field given with a localization set M. A finite regular Galois extension F/K(B) has the Tchebotarev existence property in each of the three following situations: (a) K is a field that is PAC and has cyclic extensions of any degree (with M = {0}), (b) K is a finite field (with M = {0}), (c) there exists a non trivial discrete valuation v ∈ M that is good for the extension F/K(B) and such that the residue field κ v is finite, or is PAC, perfect and has cyclic extensions of any degree.

On the other hand, there are examples for which the Tchebotarev existence property does not hold in general: for instance if K is algebraically closed or if K = R, as then, for any regular Galois extension F/K(B), all specializations are of degree 1 or 2.

More concrete examples in situations (a)-(c).

Situation (a). Recall that a field k is said to be PAC if every nonempty geometrically irreducible k-variety has a Zariski-dense set of k-rational points. Classical results show that in some sense PAC fields are "abundant" [FJ04, theorem 18.6.1] and a concrete example is the field Q tr ( √ -1) (with Q tr the field of totally real numbers (algebraic numbers such that all conjugates are real)).

There are many fields as in situation (a) of theorem 3.1. For example, it is a classical result [FJ04, corollary 23.1.3] that (*) for every projective profinite group G, there exists a PAC field K such that G K ≃ G. For G chosen so that Z is a quotient, the field K satisfies condition (a) of theorem 3.1. Any non-principal ultraproduct of distinct finite fields is a specific example of a perfect PAC field with absolute Galois group isomorphic to Z [FJ04, proposition 7.9.1].

Examples of subfields of Q can be given. The PAC field Q tr ( √ -1) is one: indeed it is also known to hilbertian and, consequently (see proposition 4.1), its absolute Galois group is a free profinite group of countable rank. It is also known that for every integer e ≥ 1, for almost

all σ = (σ 1 , . . . , σ e ) ∈ G e Q , the fixed field Q σ of σ in Q is PAC and G Q σ
is isomorphic to the free profinite group F e of rank e [FJ04, theorems 18.5.6 & 18.6.1]; here "almost all" is to be understood as "off a subset of measure 0" for the Haar measure on G e Q . We note that for such fields Q σ , a related Tchebotarev property already appeared in [START_REF] Jarden | An analogue of Ĉebotarev density theorem for fields of finite corank[END_REF].

Situation (b). The situation "K finite" is rather classical. There even exist quantitative forms of the property, similar to the Tchebotarev density property for number fields; see [START_REF] Weil | Sur les courbes algébriques et les variétés algébriques qui s'en déduisent[END_REF], [START_REF] Serre | Zeta and L-functions[END_REF], [START_REF] Michael | On Hilbert's irreducibility theorem[END_REF], [START_REF] Ekedahl | An effective version of Hilbert's irreducibility theorem[END_REF], [START_REF] Michael | Field arithmetic, volume 11 of Ergebnisse der Mathematik und ihrer Grenzgebiete[END_REF]§6]. Our approach also leads in fact to the quantitative forms; see [DG11, §3.5] and [DL12, §4.2]. We focus here on the existence part which also applies to infinite fields.

Situation (c). The following statement provides examples. By the phrase used in (c1) and (c2) that the branch locus D is good (over K), we mean that it is a sum of irreducible smooth divisors with normal crossings over K. This is automatic if B is a curve, or if, as in (c3) and (c4), K has a place that is good for the extension F/K(B) (definition 3.5).

Corollary 3.2. A finite regular Galois extension F/K(B) has the Tchebotarev existence property in each of the following situations:

(c1) K is a number field and the branch locus D is good,

(c2) K = κ(x), char(κ) = p | |G|,
the branch locus D is good, and (c2-finite) κ is a finite field, or (c2-PAC) κ is perfect, PAC and has cyclic extensions of any degree. (c3) K = K v is the completion of a number field at some finite place v that is good for F/K(B), (c4) K = κ((x)), the x-adic valuation is good for F/K(B) and

(c4-finite) κ is a finite field, or (c4-PAC) κ is perfect, PAC and has cyclic extensions of any degree.

Proof. (c3) and (c4) are obvious special cases of theorem 3.1 (c). This is true too for (c1) and (c2): the main point is that in these cases, the localization set M contains infinitely many places and that only finitely many can be bad, which is clear from definition 3.5 (under the assumption that the branch locus D is good over K).

3.1.3. The strict variant.

Addendum 3.3 (to theorem 3.1). The strict Tchebotarev existence property is satisfied in the number field situation (c1) and the PAC situations (a), (c2-PAC), (c4-PAC) from theorem 3.1 and corollary 3.2.

Finite fields are typical examples over which the non-strict variant holds but the strict variant does not: for example if p is an odd prime, the extension F/F p (T ) given by the polynomial Y 2 -Y -(T p -T ) has trivial specializations at all points t 0 ∈ F p and so at all unbranched points t 0 ∈ P 1 (F p ) (∞ is a branch point). A similar argument (given in §4.2) shows that over Q p the strict variant does not hold either. However we do not know whether the non-strict variant holds over Q p , i.e. if the condition "v good" can be removed in corollary 3.2 (c3).

3.1.4. Equivalence between (Ub-loc-d) and (exp-f). Proposition 2.8 provides general links between conditions (Ub-loc-d) and (exp-f). Combining it with theorem 3.1 and corollary 3.2, we obtain the following statement, in the case dim(B) > 0.

Corollary 3.4. For a regular Galois extension F/K(B), conditions (Ub-loc-d) and (exp-f) are equivalent in each of the following situations: (a ♯) K is a PAC perfect field such that G K is of finite rank and has every cyclic group as a quotient, (b) K is a finite field, (c1) K is a number field and the branch locus D is good, (c2-PAC ♯) K = κ(x) with κ a PAC field of characteristic 0 such that G κ is of finite rank and has every cyclic group as a quotient, and the branch locus D is good, (c3) K = K v is the completion of a number field at some finite place v that is good for F/K(B), (c4-PAC ♯) K = κ((x)) if the x-adic valuation is good for F/K(B) and for κ a PAC field of characteristic 0 such that G κ is of finite rank and has every cyclic group as a quotient.

Proof. Each situation corresponds to the conjunction of the corresponding situation in theorem 3.1 or corollary 3.2 and the condition from proposition 2.8 that the localization set M is standard (definition 2.7). It is well-known that for κ of characteristic p > 0, G κ((x)) is not of finite type: for example, if κ is algebraically closed, the Galois group of

X p n -X -(1/x) over κ((x)) is (Z/pZ) n (n ≥ 1)
. That is why situations (c2-finite) and (c4-finite) from corollary 3.2 do not appear here and κ is of characteristic 0 in (c2-PAC ♯) and (c4-PAC ♯).

3.2.

Proof of theorem 3.1 and of its addendum 3.3. A central ingredient will be [START_REF] Dèbes | Galois covers and the Hilbert-Grunwald property[END_REF]. We will notably use two statements called there twisting lemma and local specialization result. Both are answers to the question as to whether a Galois extension E/k is a specialization of a Galois k-cover f : X → B.

Fix a finite Galois extension F/K(B), regular over K, with group G and branch locus D. Through the function field functor, it corresponds to a regular Galois K-cover f : X → B. We use the cover viewpoint in the proof. From the Purity of Branch Locus, f is étale above B \ D.

3.2.1. Good places. Given a local field k v over K, denote the valuation ring by A v , the valuation ideal by p v , the residue field by κ v , assumed to be perfect, its order |κ v | by q v and its characteristic by p v . Denote also the k

v -cover f ⊗ K k v by f v : X v → B v .
If B has an integral smooth projective model B v over A v , we denote by

F v : X v → B v the morphism corresponding to the normalization of B v in k v (X), its special fiber by F v,0 : X v,0 → B v,0 and the Zariski closure of D in B v by D v .
Also recall that f is said to have no vertical ramification at v if

F v : X v → B v is unramified above p v viewed as a prime divisor of B v . Definition 3.5. A place v of K is said to be good for F/K(B) if (a) B has an integral smooth projective model B v over A v , (b) p v = 0 or p v does not divide the order of G, (c) each irreducible component of D v is smooth over A v and D v ∪ B v,0
is a sum of irreducible regular divisors with normal crossings over A v , (d) there is no vertical ramification at v in the cover f . The regular k v -cover f v has then good reduction at v: specifically, the special fiber F v,0 : X v,0 → B v,0 is a regular cover over the residue field κ v with group G and branch divisor D v,0 ; this follows from classical results of Grothendieck as explained in [DG12, § §2.4.1-2.4.4].

In the typical situation k v = Q p and B = P 1 Zp , condition (c) amounts to the branch divisor t being étale at p, and more specifically to no two branch points t i , t j ∈ Q p ∪ {∞} coalescing at v; and coalescing at v means that

|t i | v ≤ 1, |t j | v ≤ 1 and |t i -t j | v < 1, or else |t i | v ≥ 1, |t j | v ≥ 1 and |t -1 i -t -1 j | v < 1
, where v is any prolongation of v to Q p . As to the non-vertical ramification condition (d), a practical test is this: if an affine equation P (t, y) = 0 of X is given with t corresponding to f and P ∈ Z p [t, y] monic in y, there is no vertical ramification if the discriminant ∆(t) of P with respect to y is non-zero modulo p.

3.2.2.

Proof of theorem 3.1 and of addendum 3.3. Let g ∈ G. The strategy is to construct a M-local field k v over K such that (i) there exists an unramified Galois extension E/k v with Galois group isomorphic to the subgroup g ⊂ G, and (ii) the extension E/k v is a specialization of the extension

F k v /k v (B) at some point t 0 ∈ B(k v ) \ D.
We will conclude that the group Gal((F k v ) t 0 /k v ), i.e., the Frobenius subgroup of F/K(B) at t 0 over k v , is cyclic and conjugate to g in G.

To achieve (ii) we will use the twisting lemma from [START_REF] Dèbes | Galois covers and the Hilbert-Grunwald property[END_REF], which says the following. Let ϕ : G kv → g be an epimorphism such that the fixed field (k sep v ) ker(ϕ) is an extension E of k v as in (i). Then there is a regular

k v -cover f ϕ v : X ϕ v → B v (with B v = B ⊗ K k v
) such that (*) condition (ii) holds if and only if there exists a k v -rational point on X ϕ v not lying above any point in the branch locus D.

The cover f ϕ v : X ϕ v → B v is obtained by "twisting" F k v /k v (B), viewed as a regular Galois k v -cover f v : X v → B v ,
by the epimorphism ϕ, whence the terminology and the notation.

The proof of (a) follows at once. Take for v the trivial valuation on K (for which K v = K). From the assumption an extension E/K as in (i) exists, and by definition of PAC fields, the set X ϕ v (K) is Zariski-dense, and so (ii) holds as well4 . Furthermore it is the strict Tchebotarev existence property (and so addendum 3.3 (a)) that has been proved.

Remark 3.6. The non-strict Tchebotarev existence property holds under a weaker condition: the argument above shows that it is sufficient that every cyclic subgroup C be the Galois group of some finite extension E C /k C with k C a finite extension of K.

The proof of (b) goes along similar principles but with the Lang-Weil estimates replacing the PAC property. More precisely assume that K is the field F q 0 with q 0 elements. Pick a suitably large integer m; more specifically q = q m 0 should be bigger than the constant c from [DG11, corollary 3.5], which depends only on G, B and D. Then from that result, if d is the order of g, the extension F q d /F q is the specialization of F F q /F q (B) at some point t 0 ∈ B(F q )\D. So the extension F F q /F q (B) satisfies conditions (i) and (ii) above for v the trivial place on K = F q 0 and k v = F q . We note that we have used a scalar extension (from F q 0 to F q ) and only proved the (non-strict) Tchebotarev property.

The proof of (c) relies on proposition 2.2 from [START_REF] Dèbes | Galois covers and the Hilbert-Grunwald property[END_REF], which we apply to the k v -cover f v ⊗ Kv k v and to the unramified homomorphism ϕ : G kv → g ⊂ G defined as follows. If the residue field κ v is PAC, take k v = K v and if it is a finite field F q 0 with q 0 elements, take k v equal to the unique unramified extension of K v with residue extension F q m 0 /F q 0 with q = q m 0 bigger than the constant c from [DG12, lemma 2.4] (which is some version of the constant c used above). In both cases, denote the residue field of k v by κv . From the hypotheses, the field κv has a Galois extension ε v /κ v of group g . Let E v /k v be the unique unramified extension with residue extension ε v /κ v and ϕ : G kv → g be an epimorphism such that the fixed field (k sep v ) ker(ϕ) is E v . Proposition 2.2 from [START_REF] Dèbes | Galois covers and the Hilbert-Grunwald property[END_REF] has two assumptions which are labelled (good-red) and (κ-big-enough). The former is here covered by the assumption that v is good for F/K(B). The latter holds as well: this follows from the PAC property if κ v is PAC, and from [DG12, lemma 2.4] if κ v is finite of order > c. Conclude then from [DG12, proposition 2.2] that there exists

t 0 ∈ B(k v ) \ D such that the specialization (F k v ) t 0 /k v is conjugate to E v /k v . In particular Gal((F k v ) t 0 /k v )
is cyclic and conjugate to g in G. Furthermore we have proved the strict Tchebotarev property in the case of a PAC residue field (and so addendum 3.3 (c2-PAC) and (c4-PAC)) but only the non-strict Tchebotarev property in the case of a finite residue field.

It remains to show addendum 3.3 (c1). That is, to prove the strict Tchebotarev property assuming that K is a number field and the branch locus D is good. Denote by B an integral projective model of B over the ring R of integers of K; B is smooth over the completion R v for all finite places of K but in a finite subset S 0 . Pick a place v of K that is good (in particular v / ∈ S 0 ) and has a residue field κ v of order bigger than the constant C(f, B) from [DG12, lemma 3.1]. As above, assumptions (good-red) and (κ-big-enough) from [DG12, proposition 2.2] are guaranteed and it can be concluded that there exists t 0 ∈ B(k v ) \ D such that the specialization (F K v ) t 0 /K v is conjugate to the unique unramified extension E v /K v of degree the order of g.

3.3.

A further example. We illustrate our method with a last situation where the residue fields are neither PAC nor finite. A typical example we have in mind in the statement below is this: K is the field k 0 ((θ))(x) with x and θ two indeterminates and the localization set consists of all (x -x 0 )-adic valuations with x 0 ∈ P 1 (k 0 ((θ))).

Theorem 3.7. Assume K is given with a localization set M that contains a non trivial discrete valuation v ∈ M such that (a) the residue field κ v is a complete field for a non trivial discrete valuation w with a residue field κ v,w that is perfect, PAC and has cyclic extensions of any degree. Then a finite regular Galois extension F/K(B) has the strict Tchebotarev existence property if G is of trivial center and B has an integral smooth projective A v -model B v such that (b) v is good for this model of F/K(B), (c) the place w is good for the extension κ v (X v,0 )/κ v (B v,0 ) (i.e., the function field extension of the special fiber of F v : X v → B v ).

For K = k 0 ((θ))(x), condition (a) holds if k 0 is a perfect PAC field with cyclic extensions of any degree. For all but finitely many x 0 ∈ P 1 (k 0 ((θ))), the (x -x 0 )-adic valuation v x 0 is good for F/K(B), i.e. condition (b) holds. The special fiber is a k 0 ((θ))-cover and condition (c) requires that the θ-adic valuation on k 0 ((θ)) be good for it.

Proof. Fix g ∈ G. The proof follows the same strategy as in §3.2.2 and uses again [DG12, proposition 2.2], applied here to the K v -cover f v = f ⊗ K K v and the unramified homomorphism ϕ : G Kv → g ⊂ G defined as follows. From assumption (a), there exists a Galois extension of κ v,w of group isomorphic to g . This extension lifts to an unramified (w.r.t. w) extension of κ v with the same group, which in turn lifts to an unramified (w.r.t. v) extension E v /K v with the same group g . Let ϕ : G Kv → g ⊂ G be an associated representation of G Kv , i.e., the fixed field of ker(ϕ) in K v is E v .

The K v -cover f v satisfies condition (good-red) from [DG12, proposition 2.2]; this is guaranteed by assumption (b).

To check condition (κ-big-enough) from [DG12, proposition 2 [START_REF] Dèbes | Galois covers and the Hilbert-Grunwald property[END_REF], i.e., a finite and flat morphism

.2], we give ourselves what is called an

A v -model of (f v ⊗ Kv K sep v , F v,0 ⊗ κv κ v ) in
F ′ : X ′ → B v with X ′ normal and such that F ′ ⊗ Av K v is a K v -cover that is K sep v -isomorphic to f v ⊗ Kv K sep v and the special fiber F ′ 0 : X ′ 0 → B v,0 is a κ v -cover that is κ v -isomorphic to F v,0 ⊗ κv κ v .
And we have to find κ v -rational points on X ′ 0 not lying above any point in D 0 ⊗ κv κ v . Denote the valuation ring of w by A v,w . From assumption (c), the κ vvariety B v,0 has an integral smooth projective model B 0 over A v,w , and w is good for this model of κ v (X v,0 )/κ v (B v,0 ). It follows that w is also good for κ v (X ′ 0 )/κ v (B v,0 ). Indeed conditions (a), (b), (c) from definition 3.5 are equivalently satisfied by the place w for either one of the two extensions. As to condition (d), we resort to a result of S. Beckmann [START_REF] Beckmann | On extensions of number fields obtained by specializing branched coverings[END_REF] that says that non-vertical ramification is automatic under (a), (b), (c) if G is of trivial center. It follows that F ′ 0 has good reduction (at w). As κ v,w is PAC, there exist κ v,w -rational points on the reduction (at w) of X ′ 0 that are not in the branch locus of the reduction (at w) of F ′ 0 . Using Hensel's lemma, these points can be lifted to κ v -rational points on X ′ 0 as desired. Proposition 2.1 from [START_REF] Dèbes | Galois covers and the Hilbert-Grunwald property[END_REF] can then be applied to conclude that the unramified extension E v /K v , cyclic of group g , is a K v -specialization of the extension F/K(B).

Remark 3.8. A non-strict variant of theorem 3.7 can be proved if the residue field κ v,w is assumed to be finite instead of PAC. The modifications are similar to those in the proof of theorem 3.1 (for (b) vs. (a)): the Lang-Weil estimates replace the PAC property, a finite extension of K v is needed to insure that the finite residue field κ v,w is big enough, etc. We leave the reader adjust the proof.

Tchebotarev versus Hilbert

We compare the Tchebotarev existence property and the Hilbert specialization property. For short we say that a field K given with a localization set M is Tchebotarev (resp. strict Tchebotarev) if every finite regular Galois extension F/K(T ) has the Tchebotarev (resp. strict Tchebotarev) existence property.

From §2.2, PAC fields and number fields are strict Tchebotarev, finite fields are Tchebotarev, but not strict Tchebotarev.

Recall that a finite extension F/K(T ) is said to have the Hilbert specialization property if it has infinitely many specializations F t 0 /K at points t 0 ∈ P 1 (K) of degree equal to [F : K(T )] and that a field K is called hilbertian if the Hilbert specialization property holds for every finite extension F/K(T ) and RG-hilbertian if it holds for every finite regular Galois extension F/K(T ).

4.1.

The PAC situation gives a first idea of these notions hierarchy. Recall the following definition that is used in statement (a) below: a field K is ω-free if every embedding problem for G K is solvable [FJ04, §27.1]. From a theorem of Iwasawa, if G K is of at most countable rank, K is ω-free if and only if G K is isomorphic to the free profinite group Fω with countably many generators [FJ04, theorem 24. Proposition 4.1. Let K be a field given with the trivial localiza-

tion set M = {0}. (a) K is hilbertian iff K is ω-free. (b) K is RG-hilbertian iff every finite group is a quotient of G K . (c) K is strict Tchebotarev iff every cyclic group is a quotient of G K . (d) K is Tchebotarev iff every cyclic group C is a quotient of some open subgroup U C of G K .
In particular we have this chain of implications:

hilbertian ⇒ RG-hilbertian ⇒ strict Tchebotarev ⇒ Tchebotarev Furthermore none of the reverse implications holds.

Proof. The if part in (c) is theorem 3.1 (a). For the only if part, let G be a cyclic group. Classically every cyclic group G is the group of some regular Galois extension F/K(T ). If K is strict Tchebotarev, then a specialization F t 0 /K of group G does exist. Similar arguments lead to the non-strict variant (d) of (c) (use remark 3.6 for the if part).

Using the classical result (*) recalled in §3.1.2, the search of counterexamples to the reverse implications can be reduced to that of projective profinite groups G with appropriate properties. For a counterexample to "strict Tchebotarev ⇒ RG-hilbertian", take G = Z and a PAC field K such that G K ≃ G. From statements (b) and (c), K is strict Tchebotarev but is not RG-hilbertian. For a counter-example to "RG-hilbertian ⇒ hilbertian", see [START_REF] Michael | The embedding problem over a Hilbertian PAC-field[END_REF]§2]. Finally for the implication "Tchebotarev ⇒ strict Tchebotarev", we have the following counter-example, provided to us by Bary-Soroker. Take for G the universal Frattini cover [FJ04, §22.6] of the group n≥5 A n and a PAC field K such that G K ≃ G. From [FJ04, lemma 22.6.3], if a cyclic subgroup C is a quotient of G, then C is a Frattini 5 [FV92] assumes K of characteristic 0 and countable, but these hypotheses have been removed in subsequent works; see [START_REF] Pop | Embedding problems over large fields[END_REF] for (a) and [Dèb99, §3.3] for (b). cover of a quotient D of n≥5 A n . But then from [FJ04, lemma 25.5.3], D is a direct product of alternating groups A n : a contradiction if C is non-trivial. Conclude via statement (d) that K is not strict Tchebotarev. Now as we explain below, K is Tchebotarev. For every integer m ≥ 1, the alternating group A 2m is a quotient of G. Denote by K 2m /K the corresponding Galois extension, of group A 2m . If σ m ∈ A 2m is the product of two m-cycles and k the fixed field of σ m in K 2m , then k/K is finite and K 2m /k is Galois of group σ m . As m is arbitrary, this indeed shows that every cyclic subgroup is a quotient of some open subgroup of G K and so via (d) that K is Tchebotarev. 4.2. The general situation over non PAC fields K and for not necessarily trivial localization sets M is more complex. We explain in this subsection what remains in general of the first four equivalences of proposition 4.1 and in the next one how some implications between the various properties can still be obtained.

Assume K is an arbitrary field.

4.2.1. Implication (⇒) in proposition 4.1 (a) does not hold: for example, Q is hilbertian but not ω-free.6 Implication (⇒) in proposition 4.1 (c) and (d) still holds: the argument is the same as for PAC fields (and this argument also shows that implication (⇒) in proposition 4.1 (b) also holds if every finite group is the Galois group of some regular Galois extension; see also [Dèb99, §3.3.2]).

4.2.2. None of the converses hold in general. For (a), see [BSP09, remark 2.14]. For (b) and (c), take a prime p and consider the field Q tp of all totally p-adic algebraic numbers. It is known that every finite group is a quotient of G Q tp [START_REF] Efrat | Absolute Galois groups of p-adically maximal ppc fields[END_REF]. But if F/Q tp (T ) is the extension given by the polynomial

P (T, Y ) = Y 2 -Y -(pT /T 2 -p), then for every t 0 ∈ P 1 (Q tp ), the polynomial P (t 0 , Y ) is split in Q tp [Y ] [DH99, example 5.2]. Therefore F/Q tp (T ) has no Q tp -
specialization with Galois group Z/2Z and so Q tp is not strict Tchebotarev. This example also shows that Q p is not strict Tchebotarev and so yields another counterexample to the converse in (c). One may think that Q p is not even Tchebotarev; it would then also be a counter-example to (⇐) in (d).

4.3. Tchebotarev versus Hilbert: general case. Proposition 4.3 below shows that the Hilbert property is squeezed between a strong and a weak variant of the Tchebotarev property.

Definition 4.2. If K is given with a localization set M, a finite Galois extension F/K(B) is said to have the strong Tchebotarev existence property with respect to M if for every element g ∈ G, there exist infinitely many places v ∈ M with corresponding points t v ∈ B(K v )\D k v -unramified for F/K(B) and such that the Frobenius subgroup of F/K(B) at t 0 over K v is cyclic and conjugate to the subgroup g ⊂ G.

We also say that K is strong Tchebotarev if every finite regular Galois extension F/K(T ) has the strong Tchebotarev existence property. Proof. (a) Definition 4.2 makes it possible to construct a family of places (v g ) g∈G , pairwise distinct and with the property that for each g ∈ G, there exists t vg ∈ P 1 (K vg ) \ D k v -unramified for F/K(T ) and such Gal(F tv g K vg /K vg ) is conjugate to g . For each g ∈ G, the set of such points t vg is a v g -adic subset of P 1 (K vg ) \ D; this follows from the twisting lemma recalled in §3.2.2 (*). Using the approximation Artin-Whaples theorem, the collection of points (t vg ) g∈G can be approximated by some point

t 0 ∈ P 1 (K) \ D such that Gal(F t 0 K vg /K vg ) is conjugate to g for each g ∈ G. As Gal(F t 0 K vg /K vg ) is a subgroup of Gal(F t 0 /K), conclude that Gal(F t 0 /K) meets each conjugacy class of G. By a classical lemma of Jordan [Jor72], Gal(F t 0 /K) is all of G. (b)
The following proof is due to L. Bary-Soroker. From [FJ04, theorem 18.10.2], the countable hilbertian field K can be embedded in some field E, Galois over K, PAC and ω-free. From proposition 4.1, E is hilbertian, and consequently is strict Tchebotarev w.r.t. M = {0}. It readily follows that F/K(T ) has the Tchebotarev existence property (and that K is Tchebotarev w.r.t. M = {0}). Indeed given any g ∈ Gal(F/K(T )) = Gal(F E/E(T )), there exists t 0 ∈ P 1 (E) such that g = Gal((F E) t 0 /E) and a standard argument shows that the same is true with E replaced by some finite extension k of K.

The proof shows that proposition 4.3 (a) still holds if F/K(T ) is replaced by an extension F/K(B) with B satisfying the weak approximation property (and even the weak weak approximation property [Ser92, définition 3.5.6]).

A question on infinite extensions

This section is devoted to the question which arose in §2.4. Fix a field K with a localization set M, assumed to be standard (the definition and a list of examples are given in §2.3). Fix also a smooth projective and geometrically integral K-variety B.

5.1. The question and the main result. Given a Galois extension F/K(B) of group G, the following conditions were introduced in §2.4

(Ub-loc-d) the M-local degrees of F/K(B) are uniformly bounded.

F ⊂ K(B) (d) for some integer d ≥ 1.

Under the assumption that F/K(B) has the Tchebotarev existence property, we showed that if G is abelian, (Ub-loc-d) implies F ⊂ K(B) (d) for some d (corollary 2.9) and that for G arbitrary, (Ub-loc-d) only implies that the exponent of G is finite (proposition 2.8). The question remains whether (Ub-loc-d) implies F ⊂ K(B) (d) for some d in general. We will produce several examples showing that it does not.

Our examples will even satisfy this stronger variant of (Ub-loc-d):

(Ub-dec-d) the M-local decomposition degrees of F/K(B) are uniformly bounded.

where by local decomposition degree at some M-local point t 0 ∈ B(k v ), we mean the order of the decomposition group of F k v /k v (B) at t 0 (while the local degree is the degree of the residue extension). More specifically we will prove the following.

Theorem 5.1. In the following situations, there exists an infinite Galois extension F/K(T ) satisfying (Ub-dec-d) but such that F ⊂ K(B) (d) for any integer d: (a) The RIGP holds over K and the localization set M is standard. Furthermore the constructed extension F/K(T ) is regular over K.

(b) K is a finite field and B = P 1 .

Recall that the RIGP (Regular Inverse Galois Problem) is the condition that every finite group is the Galois group of some regular Galois extension F/K(T ). The RIGP is known to hold over PAC fields and complete valued fields. So such fields with a standard localization set are examples of fields as in (a). Conjecturally the RIGP holds over every field and so all fields K with a standard localization set, e.g. number fields, are other examples. 5.2. Proof of theorem 5.1. We will adjust to our function field context a construction given in [START_REF] Checcoli | On fields of algebraic numbers with bounded local degree[END_REF]§3] in the context of number fields.

5.2.1.

Strategy. The construction uses extra-special groups. We recall their definition and refer to [DH92, §A.20] for more details. Definition 5.2. Given a prime number ℓ, a finite ℓ-group E is said to be extra-special if its center Z(E) and its commutator subgroup E ′ have both order ℓ (and then Z(E) = E ′ ).

Fix two odd primes ℓ and q such that ℓ | q-1. Then for every positive integer m ≥ 1, is known to exist an extra-special group of order ℓ 2m+1 , of exponent ℓ and of rank 2m. Fix one such group E m (m ≥ 1). Moreover there exists an irreducible E m -module of dimension ℓ m over the finite field F q . Fix such an E m -module W m , and finally denote by

G m the semi-direct product W m ⋊ E m (m ≥ 1).
The following statement summarizes the strategy from [CZ11, §3].

Proposition 5.3. Assume B is a curve and for each m ≥ 1, G m is the group of a Galois extension F m /K(B). Let F/K(B) be the compositum of all extensions F m /K(B). Then F is not contained in K(B) (d) for any d but F/K(B) satisfies the tame variant of (Ub-dec-d) for which the decomposition degrees are requested to be uniformly bounded at all M-local points

t 0 ∈ B(k v ) that are tamely branched in F k v /k v (B).
Proof. The proof is given in [START_REF] Checcoli | On fields of algebraic numbers with bounded local degree[END_REF] in the case dim(B) = 0 and can be used in the more general case dim(B) ≥ 0 with almost no changes. Proposition 3.1 and proposition 3.3 of [START_REF] Checcoli | On fields of algebraic numbers with bounded local degree[END_REF] show that F is not contained in K(B) (d) for any integer d ≥ 1 and that G = Gal(F/K(B)) is of finite exponent. From proposition 2.8, this implies that the local degrees of F/K(B) are uniformly bounded. For each t 0 ∈ B(k v ) the local degree of F/K(B) at t 0 is the degree of the residue field extension above the point t 0 . Thus it remains to prove that the inertia subgroups at all M-local points t 0 ∈ B(k v ) that are tamely branched in the extension F k v /k v (B) are of uniformly bounded orders. By definition of "tame branching", these inertia subgroups are pro-cyclic subgroups of G, and so are of order ≤ exp(G).

5.2.2. End of proof of theorem 5.1. We use the construction from §5.2.1 with the primes ℓ, q distinct from p. Under the hypotheses of theorem 5.1, for each m ≥ 1, we have a Galois extension F m /K(T ) of group G m . This is clear in case (a) of theorem 5.1; the extension F m /K(T ) can further be taken to be regular over K. In case (b) for which K is finite, we resort to Shafarevich's theorem [START_REF] Neukirch | Cohomology of number fields[END_REF]: the group G m is solvable, having odd order, and therefore it is the Galois group of some extension F m of the global field K(T ). Note next that the groups G m are of prime-to-p order. In particular branching is automatically tame and so the original and the tame versions of (Ub-dec-d) are equivalent. Proposition 5.3 concludes the proof.

5.3. Bounding the branch point set.

5.3.1.

A second question. Here we show that (Ub-dec-d) does not imply that F ⊂ K(B) (d) for some d even if we assume further that the branch point set is finite. However the base field will be algebraically closed in our counter-examples (and so the Tchebotarev property will not hold). Remark 5.5. (a) For g = 0, the construction leads to an extension F/K(T ) that is only branched at one point, say the point ∞. There is necessarily wild branching and proposition 5.3 guarantees that the decomposition degrees at all t 0 ∈ P 1 (K) \ {∞} are uniformly bounded.

(b) We took ℓ = p. If ℓ = p, then if q = p, p(G m ) is trivial and G m /p(G m ) = G m and, if q = p, p(G m ) = q(G m ) = W m . So G m /p(G m
) cannot be generated by less than 2m generators (E m is of rank 2m) and G m cannot be realized with branch points in a fixed finite set S. 5.3.3. Proof of case (b): fields of characteristic 0. Assume that K is an algebraically closed field of characteristic 0 and B = P 1 .

Fix an odd prime p. For each m ≥ 1, take for G m the dihedral group Z/p m Z⋊Z/2Z of order 2p m . The projective limit G = lim ←-m≥1 G m is the pro-dihedral group Z p ⋊ Z/2Z. Denote by C m (resp. C) the conjugacy class of G m (resp. of G) of all elements (x, 1) with x ∈ Z/p m Z (resp. with x ∈ Z p ). These are conjugacy classes of elements of order 2.

Pick two elements σ, τ ∈ C and denote by σ m and τ m their images in C m via the projection map G → G m . We have σ m σ m τ m τ m = 1 and G m = σ m , τ m (m ≥ 1). By the Riemann existence theorem, if we choose four distinct points t 1 , t 2 , t 3 , t 4 ∈ P 1 (K), there is a Galois extension F m /K(T ), with group G m , branch points t 1 , t 2 , t 3 , t 4 and corresponding inertia groups σ n and its conjugates for t 1 , t 2 and τ n and its conjugates for t 3 , t 4 (m ≥ 1). Furthermore, by a classical compactness argument based on the fact that for each m ≥ 1 and each 4-tuple (t 1 , t 2 , t 3 , t 4 ) as above, there are only finitely many choices of the extension F m /K(T ), one can perform the construction compatibly, i.e., so that F m /K(T ) is obtained from F m+1 /K(T ) via the epimorphism G m+1 → G m (m ≥ 1).

Set F = lim -→m≥1 F m . The extension F/K(T ) is Galois of group G. For each m ≥ 1, the exponent of G m is ≥ p m and so G is not of finite exponent. As already noticed ( §2.4), this implies that F cannot be a subfield of K(B) (d) for any d. As K is algebraically closed, for each t 0 ∈ P 1 (k v ), the local decomposition degree at t 0 is the branching index. By construction, it is 1 or 2. So condition (Ub-dec-d) holds. 5.4. Three final remarks. The following three remarks relate to case (b) of theorem 5.4. As in this statement assume that K is an algebraically closed field of characteristic 0. 5.4.1. On the geometric Bogomolov property. Consider the (smooth projective) curves C m corresponding to the function fields F m from the proof above (m ≥ 1). The degrees [F m : K(T )] go to infinity and the Riemann-Hurwitz formula shows that the curves C m are all of genus 1.

We explain below that this provides a counter-example to a geometric analog of a result of Bombieri and Zannier around the Bogomolov property. The "geometric Bogomolov property" as presented below is stated by J. Ellenberg in [Ell].

Recall that the gonality of some K-curve C is the least degree of a non constant function x ∈ K(C) and that the gonality of a curve is bounded above in terms of its genus. Consequently in our example above, we have that there is no real constant c > 0 such that (GB) the gonality of C m is ≥ c [F m : K(T )] (m ≥ 1). Condition (GB) can be rewritten in terms of the absolute logarithmic height on K(T ). Given a non constant function x ∈ K(T ), the absolute logarithmic height of x, denoted by h(x), is defined as follows: if L/K(T ) is any finite extension such that x ∈ L, h(x) is the ratio [L : K(x)]/[L : K(T )]. Noting that if C is a curve corresponding to the function field L, then [L : K(x)] is the degree of x on C (equivalently, the number of zeroes (or poles) on C), condition (GB) rewrites:

(GB) for every non constant function x in F , h(x) ≥ c.

In [Ell], J. Ellenberg says that an infinite algebraic extension F/K(T ) has the geometric Bogomolov property if there exists some c > 0 such condition (GB) holds. This is his geometric analog of the Bogomolov property of an algebraic extension F/Q (introduced in [BZ01]), which requests that there exists some c > 0 such that if x ∈ F is neither zero nor a root of unity, then h(x) ≥ c, where h(x) is the classical Weil logarithmic height on Q.

For the Bogomolov property of algebraic extensions F/Q, we have the following criterion due to Bombieri-Zannier [BZ01, theorem 2], which has several interesting consequences (for example that the field Q tp of totally p-adic numbers has the Bogomolov property, just as the field Q tr of totally reals does (a result of Schinzel [START_REF] Schinzel | On the product of the conjugates outside the unit circle of an algebraic number[END_REF])).

(Bombieri-Zannier criterion) If F/Q is an algebraic extension with finite local degrees at some prime p, then F has the Bogomolov property.

Our original example -an infinite extension F/K(T ) which has uniformly bounded local decomposition degrees (here they are just the ramification indices) but does not satisfy property (GB) -shows that the geometric analog of the Bombieri-Zannier criterion does not hold, even if all decomposition degrees are assumed to be bounded (and not just the local degrees above one prime). 5.4.2. A generalization using universal p-Frattini covers. The construction from §5.3.3 extends to the following more general context; we refer to [START_REF] Michael | Introduction to modular towers: generalizing dihedral group-modular curve connections[END_REF], [FJ04, §22], [START_REF] Dèbes | An introduction to the modular tower program[END_REF], for details.

A group G 1 is given with a prime p such that p| |G 1 | and G 1 is p-perfect, i.e. G 1 is generated by its elements of prime-to-p order. Take for G the p-universal Frattini cover of G 1 (which generalizes the pro-dihedral group Z p ⋊ Z/2Z) and for (G m ) m≥1 the natural collection of finite characteristic quotients of G (which generalize the dihedral groups Z/p m Z ⋊ Z/2Z, m ≥ 1). Select r elements of G 1 of prime-to-p order generating G 1 . The conjugacy class of each of these elements can be lifted to a conjugacy class C i of G with the same order, i = 1, . . . , r (the lifting lemma). Pick an element σ i ∈ C i , i = 1, . . . r and consider the 2r-tuple (σ 1 , σ -1 1 . . . , σ r , σ -1 r ); its entries generate G (the Frattini property) and are of product one.

Extensions F m /K(T ) can then be constructed as in §5.3.3 with the 2r-tuple above replacing the 4-tuple (σ, σ, τ, τ ) and 2r distinct points of P 1 (K) replacing the 4 chosen points t 1 , . . . , t 4 ∈ P 1 (K) in §5.3.3. Set F = lim -→m≥1 F m . The extension F/K(T ) is Galois of group G and it satisfies (Ub-dec-d) but is not contained in K(B) (d) for any d. The main point is that G is still of infinite exponent in this more general context. Indeed the p-Sylow subgroups of G are known to be free pro-p groups and so cannot have non trivial elements of finite order. 5.4.3. In the abelian situation the following can be added.

Proposition 5.6. Let F/K(T ) be an abelian extension, with finitely many branch points and such that condition (Ub-dec-d) holds. Then not only F ⊂ K(B) (d) but F/K(T ) is finite.

Proof. Denote the branch points of F/K(T ) by t 1 , . . . , t r . Let F 0 /K(T ) be a finite Galois sub-extension of F/K(T ) of group G 0 . From the Riemann existence theorem, G 0 is generated by r elements σ 1 , . . . , σ r such that σ 1 • • • σ r = 1; moreover σ i is a generator of some inertia group above t i . From assumption (Ub-dec-d), the order of σ i is bounded by some constant δ, independent of i. Since G 0 is abelian we have |G 0 | ≤ δ r-1 . As all finite sub-extensions of F/K(T ) are abelian and the argument holds for any of them, conclude that F/K(T ) is finite and that [F : K(T )] ≤ δ r-1 .

Proposition 2. 8 .

 8 Let F/K(B) be a Galois extension (possibly infinite) with Galois group G and with the Tchebotarev existence property. Then if (Ub-loc-d) the M-local degrees of F/K(B) are uniformly bounded, then (exp-f) the exponent of G is finite. Furthermore the converse (exp-f) ⇒ (Ub-loc-d) holds too if the localization set M is standard (independently of the Tchebotarev property).

  8.1]. Conclusions (a) and (b) below are classical; see [FJ04, corollary 27.3.3] for the if part in (a), [FV92, theorem A] for the only if part, and [FV92, theorem B] for (b) 5 . We have included them in the statement to put the new conclusions (c) and (d) in perspective.

Proposition 4. 3 .

 3 Let F/K(T ) be a finite regular Galois extension. (a) If F/K(T ) has the strong Tchebotarev existence property w.r.t. a localization set M of K, then it has the Hilbert specialization property. In particular, if K is strong Tchebotarev, then it is RG-hilbertian. (b) If K is a countable hilbertian field then F/K(T ) has the Tchebotarev existence property w.r.t. the trivial localization set M = {0}. In particular, K is Tchebotarev w.r.t. M = {0}.

Theorem 5. 4 .

 4 In situation (a) or (b) below, there is an infinite Galois extension F/K(B) satisfying (Ub-dec-d) but such that F ⊂ K(B)(d) for any d and that is branched at only finitely many points: (a) K is an algebraically closed field of characteristic p > 0 and B is a curve of genus ≥ 1. (b) K is an algebraically closed field of characteristic 0 and B = P 1 . 5.3.2. Proof of case (a): fields of positive characteristic. Assume that K is an algebraically closed field of characteristic p > 0 and B is a curve of genus g. We use again the construction from §5.2.1; we retain the notation from there. From proposition 5.3, we are left with realizing all groups G m as groups of Galois extensions F m /K(B) (m ≥ 1) with controlled branching. We will use Abhyankar's Conjecture on Galois groups of function field extensions of characteristic p, which was proved by the work of M. Raynaud[START_REF] Raynaud | Revêtements de la droite affine en caractéristique p > 0 et conjecture d'abhyankar[END_REF] and D. Harbater [Har94]: (The Raynaud-Harbater theorem) A finite group G can be realized as the group of a Galois extension F/K(B) unbranched outside a finite set S if and only if the minimal number of generators of the quotient G/p(G) of G by the subgroup of G generated by all p-Sylow subgroups of G is at most |S| + 2g -1. Take ℓ = p. For each m ≥ 1, we have the following. The group p(G m ) = ℓ(G m ) is a normal subgroup of G m which properly contains the p-group E m (since E m is not normal in G m ). Consequently the group p(G m ) ∩W m is a non trivial normal subgroup of G m . But as part of the theory of extraspecial groups, W m is a minimal non trivial normal subgroup of G m . Therefore W m ⊂ p(G m ) so finally p(G m ) = G m . From the Raynaud-Harbater theorem, if g ≥ 1, then G m is the group of some Galois extension F m /K(B) unbranched everywhere.

definition recalled in §3.1.2 (a).

When v is the trivial valuation, this condition is vacuous as all finite extensions of k v are unramified.

As pointed out by M. Jarden, the weaker density property proved by Frobenius (e.g. [Jan96, p.134]), where a cyclic subgroup instead of a specific element of the Galois group is given is sufficient to prove our property for number field extensions.

For PAC fields, stronger results can be proved for which g can be replaced by any subgroup of G; see[START_REF] Dèbes | Specializations of Galois covers of the line[END_REF] corollary 3.4].

However it is conjectured that "K hilbertian" implies that every split finite embedding problem over K has a solution[START_REF] Dèbes | The regular inverse Galois problem over large fields[END_REF] (which itself implies K ω-free if in addition G K is projective and countable).


Julien Rodriguez

François Galea

François Pellegrini
email: francois.pellegrini@u-bordeaux.fr

Lilia Zaourar

Path Length-Driven Hypergraph Partitioning: An Integer Programming Approach

Circuit prototyping on multi-FPGA (Field Programmable Gate Arrays) platforms is a widely used technique in the VLSI (Very-Large-Scale Integration) context. Due to the ever-increasing size of circuits, it is necessary to use partitioning algorithms to place them on multi-FPGA platforms. Existing partitioning algorithms focus on minimizing the cut size but do not consider the critical path length, which can be degraded when mapping long paths to multiple FPGAs. However, recent studies try to consider the degradation of the critical path and the target topology but these works still use cutting minimization algorithms. In this work, we propose a mathematical model as an integer program (IP) based on the Red-Black Hypergraph model that considers the minimization of the critical path degradation and the target topology. We compare our partitioning results with KHMETIS, a min-cut algorithm, and show a better critical path for many circuit instances.

I. INTRODUCTION

O UR work concerns practical improvements of the elec- tronic circuit design chain. The typical hardware design flow includes different steps, such as floor planning, placement, and routing, that may concern very large logic circuits.

To deal with such large circuits, the methods involved may benefit from divide-and-conquer approaches that allow for working locally on separate parts of the circuit, greatly reducing the work on the global circuit. Such a divide-and-conquer approach also enables circuit prototyping on a multi-FPGA platform, where the circuit is too large (in terms of resource consumption) to be implemented on a single FPGA. In such cases, a strong constraint is to mitigate a possible increase in the signal propagation delay of the longest combinatorial path, known as the critical path. Indeed, in synchronous circuits, the critical path length determines the maximum frequency at which the circuit may operate; mapping long paths across several FPGAs is likely to degrade the critical path.

Circuit partitioning is both an essential step in the design flow of electronic circuits, and a challenging multi-constraint optimization problem. It must address both the multi-resource issue (i.e., capacity limits on each FPGA and their interconnection links) and the minimization of the critical path degradation.

Traditional partitioning tools use the now classic multi-level scheme (see Fig. 1) consisting of three phases: coarsening, initial partitioning, and refinement [START_REF] Karypis | Multilevel hypergraph partitioning: applications in VLSI domain[END_REF]. The coarsening phase C o n t r a c t i o n p h a s e R e f i n e m e n t p h a s e Initial partitioning Fig. 1. Multi-level scheme uses a recursive clustering method to transform the circuit model, a hypergraph, into a smaller one. During the second phase, an initial partitioning is computed on the smallest coarsened hypergraph. Finally, for each coarsening level, the solution for the coarser level is extended to the finer level and then refined using a local refinement algorithm. The initial partitioning algorithm presented in this paper concerns the first step of the multilevel framework described above.

Our work focuses on balanced hypergraph partitioning, in which our objective functions are both path-cost minimization and the classical min-cut objective that is still relevant to us. The hypergraph model we consider in our research context consists of a union of directed acyclic hypergraphs (DAH) [START_REF] Rodriguez | A hypergraph model and associated optimization strategies for path length-driven netlist partitioning[END_REF]. The global hypergraph is assumed to be connected; otherwise, its disconnected components are processed independently. The source and sink vertices of each DAH (which represent registers and I/O ports) are labeled red, while other vertices are black. Red vertices can be shared by multiple DAHs, which makes the global hypergraph connected. A path-cost function models the impact of a cut on the red-to-red paths during partitioning. Each partition of a hypergraph will result in cuts along some paths, inducing additional traversal costs. Our aim is to find a partition of minimum path cost, such that the size of the cut is also minimized. Our research context only considers the paths between two red vertices and a non-uniform cut cost between parts.

The classical approach is to model this problem with a hypergraph, using cost functions that minimize cut size. However, it has been shown in [START_REF] Ababei | Multiobjective circuit partitioning for cutsize and path-based delay minimization[END_REF] that the cut size does not address the path cost efficiently during the hypergraph partitioning procedure. This is why several authors proposed pre-and/or post-processing steps in order to reduce the degradation of cut paths [START_REF] Ababei | Multiobjective circuit partitioning for cutsize and path-based delay minimization[END_REF], [START_REF] Chen | Performance-driven simultaneous partitioning and routing for multi-fpga systems[END_REF], [START_REF] Liou | Timing Driven Partition for Multi-FPGA Systems with TDM Awareness[END_REF]. In this paper, we devise a dedicated integer programming model that minimizes path cost degradation during partitioning, based on the red-black hypergraph structure, which can be used as an initial partitioning method in a multilevel framework.

The remainder of the paper is organized as follows: Section 2 presents a reminder of our red-black hypergraph structure as well as previous works. Section 3 describes our coarsening scheme before the initial partitioning and the integer programming model. Our experiments are outlined in Section 4. We conclude and give perspectives in Section 5.

II. PRELIMINARIES

In this part, we define the notations and definitions used in this work.

A. Definitions and Notations

Let H def = (V, A, W v , W a ) be a directed hypergraph, defined by a set of vertices V and a set of hyperarcs A, with a vertex weight function W v : V → R + and a hyperarc weight function W a : A -→ R + . Every hyperarc a ∈ A is a subset of vertex set V: a ⊆ V. Let s + (a) be the source vertex set of hyperarc a, and s -(a) its sink (destination) vertex set. We consider here, without loss of generality, that each hyperarc has a single source, so ∀a, |s + (a)| = 1. As hyperarcs connect vertices, let Γ(v) be the set of neighbor vertices of vertex v, and Γ -(v) ⊆ Γ(v) and Γ + (v) ⊆ Γ(v) the sets of its inbound and outbound neighbors, respectively.

In the model we propose, hypergraphs that model circuits are be represented as sets of interconnected DAHs, according to a red-black vertex coloring scheme. Red vertices correspond to I/O (Inputs/Outputs) ports and registers, and black vertices to combinatorial circuit components. Let V R ⊂ V and V B ⊂ V be the red and black vertex subsets of V, such that

V R ∩V B = ∅ and V R ∪ V B = V. A hypergraph or sub-hypergraph H is a DAH iff its red vertices v R ∈ V R are either only sources or sinks (i.e., Γ -(v R ) = ∅ or Γ + (v R ) = ∅)
, and no cycle path connects a vertex to itself.

Using this definition, we can represent circuit hypergraphs as red-black hypergraphs, i.e., sets of DAHs that share some of their red vertices. Let H(V, A) def = {H i , i ∈ {1 . . . n}} be a red-black hypergraph, such that every H i is a DAH and an edge-induced sub-hypergraph of H. Consequently,

V = i V i , A = i A i , V R = i V R i , and V B = i V B i . Moreover, ∀i, j with i ̸ = j, if V i,j = V i ∩ V j ̸ = ∅,
then H i and H j share source and/or sink vertices, i.e., V i,j ⊂ V R .

In this model, the paths in H to consider when addressing the objective of minimizing path-cost degradation during partitioning are only the paths interconnecting red vertices, as these red-red paths represent register-to-register paths in combinatorial circuits. Since only red vertices are shared between DAHs in H, red-red paths only exist within a single DAH and can never span across several DAHs.

Let us define P as the set of red-red paths in H, such that P def = {p|p is a path in H ∈ H}. From these paths and a function d max (u, v), which computes the maximum distance between vertices u and v of some DAH H, we can define the longest path distance for H as:

d max (H) def = max(d max (u, v)|u, v ∈ H)
and, by extension, for H, as:

d max (H) def = max(d max (H)|H ∈ H).
A partition Π of H is a splitting of V into vertex subsets π i , called parts, such that:

(i) all parts π i , given a capacity bound M , respect the capacity constraint:

v∈πi W v (v) ≤ M
(ii) all parts are pairwise disjoint:

∀i ̸ = j, π i ∩ π j = ∅
(iii) the union of all parts is equal to V:

i π i = V
Consequently, in our model, the distance between two vertices u and v may increase during partitioning due to the additional cost of routing paths between two (or more) parts. Let D kk ′ be the penalty associated with parts k and k ′ such that if u is in part k and v is in part k ′ , then:

d Π max (u, v) ≥ d max (u, v) + D kk ′ (1)
For a given partition Π of H, the path-cost is defined by the function:

f p (H Π ) = max(d max (H Π )|H ∈ H).
Let a red-black hypergraph H and a partition Π, the connectivity λ Π (a) of some hyperarc a ∈ A is the number of parts connected by a. If λ Π (a) > 1, then a is said to be cut; otherwise, it is entirely contained within a single part and is not cut. The cut of partition Π is the set ω(Π) of cut hyperarcs, i.e., ω(Π)

def = {a ∈ A, λ Π (a) > 1}.
The cut size is defined as

f c def = a∈ω(Π) W a (a)
. If all hyperarcs have the same weight (equal to 1), the cut size is equal to |ω(Π)|. Another cut metric used by some partitioning tools to measure the quality of partitioning is called connectivity-minus-one [START_REF] Çatalyürek | More recent advances in (hyper)graph partitioning[END_REF]. The connectivityminus-one cost function f λ of some partitioned hypergraph H Π is defined as:

f λ = a∈A (λ Π (a) -1) × W a (a).

B. Previous work

Several approaches in the literature have been attempted to improve the performance of circuit partitioning. We present some recent work on circuit partitioning for rapid prototyping that considers performance constraints. Many of these works attempt to tweak existing min-cut partitioning tools, which are used as black boxes, to consider additional constraints. For example, [START_REF] Ababei | Multiobjective circuit partitioning for cutsize and path-based delay minimization[END_REF] presents a multi-objective approach based on HMETIS. The authors compute the K most critical paths at each partitioning step, using a metric cost that considers the critical path length, the cut number along critical paths, and the weight of the hyperarcs associated with the critical paths. Reference [START_REF] Chen | Performance-driven simultaneous partitioning and routing for multi-fpga systems[END_REF] compares a classical method using HMETIS for partitioning followed by a placement algorithm with a derived approach consisting of placement and routing during the partitioning step. The results show better critical path values compared to the two-step approach. More recently, [START_REF] Liou | Timing Driven Partition for Multi-FPGA Systems with TDM Awareness[END_REF] performs some pre-and post-processing on the hypergraph to capture the critical path minimization objective within the cut-size metric, using HMETIS as the partitioning tool. Reference [START_REF] Kucar | Hypergraph partitioning techniques[END_REF], presents an IP model to address the hypergraph partitioning problem. The model is not dedicated to mapping and critical path minimization but to minimize the cut cost.

III. CONTRIBUTIONS

We now present our core contribution. The first part consists of a coarsening algorithm to reduce the size of the hypergraph. In the second part, we present our IP model used as initial partitioning.

A. Coarsening method

The heavy-edge matching (HEM) approach for graph coarsening presented in [START_REF] Karypis | Analysis of multilevel graph partitioning[END_REF] is widely used in hypergraph and graph partitioning tools [START_REF] George | Hmetis: a hypergraph partitioning package[END_REF], [START_REF] Pellegrini | Scotch and PT-Scotch Graph Partitioning Software: An Overview[END_REF] and yields efficient results in many cases. Our coarsening algorithm is based on a heavyedge matching approach. It consists of reducing the instance's size while minimizing the merged vertices' weight differences as much as possible. The risk in merging vertices is to end up with disproportionate weights of vertices, which may prevent the initial partitioning from exploring different solutions. However, in the context of critical path minimization, it may be interesting to merge all vertices along the critical path into one large vertex. This method is not necessarily interesting when the circuit contains many critical or semicritical paths. It is, therefore, necessary to find a compromise between creating a large vertex by securing the cut along the critical path and balancing the fusion to allow a more practical exploration search during the initial partitioning phase. The vertex criticality model the value of the longest path traversing the vertex. Our algorithm groups vertices by criticality to favor the grouping of critical paths. Vertices with a smaller weight are selected to favor balanced coarsening.

B. Integer Program

The objective of the IP model is to minimize the degradation of the critical path, so we need to calculate the maximum degradation among all possible degradations. We also need to model the target topology to consider the different delays between each part. Cut minimization tools do not address these two aspects: path length and topology. Cut minimization tools only limit the connections between parts. As this objective is still essential in practice, we add a second objective to our model: minimizing the connectivity minus one. As the paths between two red vertices do not contain cycle, it is possible to see the chain of black vertices in a path as a sequence of operations/tasks i associated with a job l. In our model, we consider scheduling constraints to minimize the impact of partitioning on the critical path. Given a path (job) p = v 0 , v 1 , v 2 , the critical time associated with the path equals v∈p d v . If vertices (tasks) belonging to p are placed in different parts, then a time penalty must be added to the total time of p. A summary of the integer model can be found in Table I, the parameters in Table II, and the variables in Table III. Below is the integer program with two objectives 2a for critical path minimization and 2b for connectivity cost minimization:

i,i ′ vertices/operation index (i, i ′ ∈ V) j, j ′ hyperedges index (j, j ′ ∈ E) l, l ′ job index (l, l ′ ∈ J) k part index
min z max (2a) min j W j a k y jk -1 (2b)
subject to :

k x ik = 1, ∀i (2c)
h ij x ik ≤ y jk , ∀i, j, k (2d)
i q ir x ik ≤ c kr , ∀k, r (2e)
i,i ′ ∈O l d i + x ik x i ′ k ′ D kk ′ ≤ z l , ∀k, k ′ , l (2f)
z l ≤ z max , ∀l (2g) x ik , y jk ∈ {0, 1}, z l ∈ N ∀i, j, k, l (2h)
Constraint 2c states that each vertex is mapped onto one part. Constraint 2d guarantees that y jk equals the connectivity cost associated with hyperedge j. The constraint 2e ensures the Variable Definition x ik 1 iff the vertex i is mapped onto part k, 0 otherwise y jk 1 iff the hyperedge j has a vertex placed on part k z l completion time of job l zmax maximum completion time of jobs TABLE III VARIABLES DEFINITIONS capacity constraint is respected. The constraints 2f and 2g determine the value of the delay of the job (path) and the maximum delay (critical path). The constraint 2h are the nonnegativity and integrity conditions on the variable.

There are symmetries in the solution space in hypergraph partitioning for cut size minimization. Indeed, if there are ω hyperedges between parts, ω remains unchanged regardless of the labels of the parts. On the other hand, in our problem, we are trying to minimize the path cost, which is degraded by routing paths between parts that are not always fully connected. There are models for partitioning graphs and hypergraphs with symmetry-breaking constraints [START_REF] Bonami | On the solution of a graph partitioning problem under capacity constraints[END_REF]. However, these constraints are too restrictive for the solution space associated with path cost. In our problem, the target topology defines a time penalty associated with path routing. As a result, we cannot consider all partitions with the same subset of vertices but different labels, identical, from a routing point of view. An example can be found in Figure 2. Note that some symmetries exist, for example: if we take the partition a, shown in Figure 2. It is possible to create a partition a ′ by swapping the vertices of π 0 and π 3 and of π 1 and π 2 . Future work will involve improving the model to remove these symmetries.

IV. EXPERIMENTAL RESULTS

To validate our models and algorithms, we have performed experiments on benchmarks [START_REF] Corno | RT-level ITC'99 benchmarks and first ATPG results[END_REF] of logic circuits. These circuits consist of acyclic combinatorial blocks, bounded by their input and output registers. Every combinatorial block can therefore be modeled as a DAH. Their computation time is conditioned by their critical path, defined as the longest path between two registers (i.e., two red vertices). Our work aims at minimizing the degradation of the critical path during partitioning according to the target topology. For each instance, we use topology data to define a traversal cost d(v) for each vertex v, corresponding to the traversal time of a logic element. As the degradation between the parts can be non-homogeneous, we have defined several architecture topologies composed of four elements. The test architecture is a chain π 0 , π 1 , π 2 , π 3 . We did not consider the fully connected topology to highlight the advantage of our topology-aware algorithms over regular partitioners like KHMETIS. To solve the initial partitioning problem, we use Gurobi Optimiser version 9.1.2 with a time limit set to 600s. During the refinement phase, we use the DKFM [START_REF] Rodriguez | A hypergraph model and associated optimization strategies for path length-driven netlist partitioning[END_REF], a local search algorithm dedicated to minimizing path length. This algorithm is inspired by FM [START_REF] Fiduccia | A linear-time heuristic for improving network partitions[END_REF], a local search algorithm for minimising the number of hyperedges between two parts. We use KHMETIS rather than HMETIS a) b) Fig. 2. In this example, the path p = v 0 , v 1 , v 2 , v 3 , v 4 , v 5 is partitioned into 4 parts. In partition a, the path admits a routing penalty of 3D, where D is the traversal time between parts. In partition b, the routing penalty is 5D. Since there is no route between π 0 and π 2 , we must necessarily pass through π 1 to get there, which gives a cost of 2D to get from π 0 to π 2 . The same goes for π 1 to π 3 . From the point of view of the size of the cut, partition a allows a cost of 3 cut edges, as does partition b. Partitions a and b are identical and symmetrical for cut minimization.

because HMETIS is based on recursive bipartitioning methods, which often do not respect the balance constraint. We use the maximum criticality as a weight for the hyper-edges as [START_REF] Rodriguez | A hypergraph model and associated optimization strategies for path length-driven netlist partitioning[END_REF] to guide KHMETIS to minimise the number of cuts along the critical path as much as possible.

A. Results

Table IV shows that our approach gives better results. Indeed, the first coarsening step allows the grouping of the most critical vertices while maintaining a balance in the reduced hypergraph. Finally, since the initial partitioning considers the topology, it allows for finding an appropriate placement before the refinement phase. For instances B14 and B17, the time limit is not sufficient for Gurobi to find a good solution. A method needs to be found to better reduce the size of the instance while retaining sufficient criticality information for the integer program. Table V shows us a better performance of KHMETIS for the function f λ . Note that our approach sometimes allows a better solution for both f p and f λ . V. CONCLUSION

In this paper, we present a multilevel approach to the problem of red-black hypergraph (circuit) partitioning on not fully connected topologies. Our approach consists of exploiting the vertices' criticality to group the critical paths in the same part during the coarsening phase. Finally, we propose a mathematical model considering the two objectives: f p and f λ for the initial partitioning. For the refinement, we use the DKFM algorithm. Our results show that our approach is better at minimizing f p than a min-cut partitioning tool, even if it is oriented towards the criticality of hyperarcs. It may be interesting to test our approach on other more extensive benchmarks, as well as to test other coarsening algorithms to improve the results of initial partitioning based on our IP.

  ordered set of operations of job l, (i ∈ O l ), where O l1 and O ln ′ are the first and the last elements of O l

	Set	Definition
	V	set of vertices
	E	set of hyperedges
	J	set of jobs
	O l

TABLE IV RESULTS

 IV FOR PATH-COST fp IN NANO-SECONDE (NS)

	Instance	KHMETIS (ns)	Multilevel+IP+DKFM (ns)
	b01		60	50
	b02		30	30
	b03		50	40
	b04		60	60
	b05		50	50
	b06		40	30
	b07		90	60
	b08		90	70
	b09		40	40
	b10		80	80
	b11		80	70
	b12		40	40
	b13		30	20
	b14		40	100
	b17		200	215.52
			TABLE V
		RESULTS FOR CONNECTIVITY f λ
	Instance	KHMETIS	Multilevel+IP+DKFM
	b01		15604	24288
	b03		13903	10922
	b03		21297	29962
	b04		38320	103659
	b05		30753	70329
	b06		20526	19043
	b07		30372	114329
	b08		28170	44511
	b09		24830	24445
	b10		32989	41600
	b11		49883	57329
	b12		30743	99448
	b13		4567	6000
	b14		214772	1578740
	b17		846531	3149961