# Asymptotics of several-partition Hurwitz numbers.

1 Introduction

In the end of the XIXth century, Hurwitz computed the number of ways to factorise in the symmetric group [S.sub.n] a permutation of given cyclic type [lambda] into a product of a minimal number of transpositions which generate a transitive subgroup. If one denotes by [h.sup.0.sub.n]([lambda]) that number divided par n!, Hurwitz proved that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

A fruitful generalisation of Hurwitz's original question (see [5] and [6]) is to seek such factorisation numbers [h.sup.g.sub.n] ([??]) with prescribed number of transpositions (the minimal case corresponds to g = 0), by remplacing the single permutation [sigma] by a product of an arbitrary number of permutations of given types [??] = ([[lambda].sub.1], ..., [[lambda].sub.k]) (see Section 2.2 for reminders on partitions), and by adding a transitiveness condition--without the latter, such "disconnected" Hurwitz numbers would be given by Frobenius's formula. Section 2.3 recalls the definitions of the numbers [h.sup.g.sub.n]([??])] and of their corresponding generating fonction [H.sup.g]([??]). Section 2.2 defines convenient renormalisations [h.sup.g.sub.n] ([??]) and [H.sup.g.sub.n] ([??]).

In genera 0 and 1, some considerations from algebraic geometry (more precisely the ELSV formula, see [3]) yield explicit formula for [h.sup.0.sub.n]([lambda]) and [h.sup.1.sub.n]([lambda]), whence closed formula for series [H.sup.0]([lambda]) and [H.sup.1]([lambda]) (see Section 2.4). Moreover, Kazarian [4] used the integration frame of the ELSV formula to give an explicit formula for the series [H.sup.g] when g [greater than or equal to] 2 (see Section 2.5). However, very little is known on the numbers [h.sup.g.sub.n]([??]) when the number of partitions is strictly greater than 1. In this paper, we will only be concerned with determining the asymptotics of [h.sup.g.sub.n]([??]) when n grows to [infinity].

Zvonkine introduced in [7] an algebra of power series A := Q [Y, Z] which has the following properties (see [8] and [9] for details):

1. the asymptotics of the leading coefficient of a series lying in A is determined by the leading coefficient in Z (see Claim 1 in Section 2.1);

2. all series [H.sup.g]([[lambda].sub.1], ..., [[lambda].sub.k]) but [H.sup.1] (0) lay in the algebra A (see [7]).

Zvonkine proved the latter by induction on the number k of partitions, relying when k = 1 on alreadyknown formula for spherical and toric genera (see Section 2.4) and on Kazarian's formula for higher genera (see Section 2.5). However, Zvonkine did not make explicit the formula he used; since we want to precisely compute the Z-degree of [H.sup.g]([??]), we will carry out the explicitation of this reduction formula (see Theorem 10 in Section 3.1). Then, we will be able to prove our main result (Theorem 8) by induction (see Section 3.2), hence the sought asymptotics of all numbers [h.sup.g.sub.n]([??]) (see Corollary 9). Both Theorem 8 and Corollary 9 are stated in Section 2.6.

The constants in the obtained asymptotics involve some rationnal-valued intersection numbers whose generating function, up to some renormalisation, satisfy Painleve's equation I([d.sup.2]f/[dq.sup.2] + f [(q).sup.2] = q, see [5]) and can hence be recursively computed (see last lines of [1]). Section 2.6 recalls such a recursion formula, allowing one to retrieve the map asymptotics constants [t.sub.g] defined in [2].

For sake of conciseness, we will use throughout the paper the genus-notation

g' := g - 1.

2 Hurwitz numbers and the algebra A

2.1 The algebra A = Q [[summation].sub.n[greater than or equal to]1][n.sup.n-1]/n! [q.sup.n], [[summation].sub.n[greater than or equal to]1] [n.sup.n]/n! [q.sup.n]

Let us define an algebra A := Q [Y, Z] where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Define also a pseudo-inverse [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The combinatorial identity Y = [qe.sup.Y] allows one to linearise the product YZ = Z - Y, whence the description A = Q [Y] + Q [Z]. The latter entitles one to assign to every series in [A.sup.Z] := A\Q[Y] a polynomial in Z (up to the constant coefficient) that completly describes the asymptotics of the corresponding series thanks to the following claim:

Claim 1 (asymptotics in the algebra A). One has for any positive integers i and k

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Two series S and T in AZ have therefore the same asymptotics if and only if their Z-leading terms are equal, which we will denote by a Z-equality [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For instance, one has [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any polynomials P and Q and the equality [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

2.2 Reminders on partitions

Recall that a partition of an integer a is any finite non-increasing sequence [lambda] = ([d.sub.1] [greater than or equal to] [d.sub.2] [greater than or equal to] ... [greater than or equal to] [d.sub.p]) of positive integers (the parts of [lambda]) summing up to a. Define the length l([lambda]) := p, the size [absolute value of [lambda]] := a, the multiplicity [m.sub.k]([lambda]) := Card {i; [d.sub.i] = k} of any integer k, the ramification r([lambda]) := [absolute value of [lambda]] - l([lambda]), the number of symmetries [absolute value of Aut[lambda]] = [[PI].sub.k[greater than or equal to]1][m.sub.k]([lambda])!, the reduction [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the (n-th) completion [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any integer n [greater than or equal to] [m.sub.1] ([lambda]). A partition [lambda] is called reduced if [m.sub.1]([lambda]) = 0. The concatenation [lambda] [??] [mu] of two partitions [lambda] and [mu] is the partition whose parts are those of [lambda] union those of [mu]. The length, size and ramification are morphisms from the concatenation to the addition and can therefore be extended to a tuple of partitions by concatenating the latter. At last, it will be convenient to use the following notations and renormalisations (see Definition 2 to define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Let n [greater than or equal to] 1 an integer and [sigma] a permutation in [S.sub.9]. Its support is the complement S[sigma] = Supp[sigma] in [1, n] of all [sigma]-fixed points and its type is the partition type ([sigma]) whose parts are the lengths of the cycles of [sigma] (including fixed cycles). For instance, the type of the disjoint product of two permutations is the concatenation of their types and the cardinality of the support of a permutation equals the size of the reduction of its type. Recall that conjugacy classes in [G.sub.n] are indexed by n-sized partitions.

2.3 Constellations and Hurwitz numbers

Let n and k be positive integers. Define a k-constellation of degree n to be a k-tuple [??] [member of] [S.sup.k.sub.n] such that [[sigma].sub.1] ... [[sigma].sub.k] = Id and that the subgroup <[[sigma].sub.1], [[sigma].sub.k]> acts transitively on [1, n]. The type of a k-constellation [??] is the k-tuple of the types of the [[sigma].sub.i]. Its ramification r is the sum of those of the [[sigma].sub.i]'s. Its genus g [greater than or equal to] 0 is defined by the Riemann-Hurwitz formula r = 2n + 2g'. (Recall that g' = g - 1).

Definition 2 (Hurwitz numbers [h.sup.g.sub.n]([??]) and Hurwitz series [H.sup.g]([??]). Let g and n be two nonnegative integers and [[lambda].sub.1],[[lambda].sub.k] be partitions of non-negative integers.

Define T = [T.sub.n] = [T.sup.g.sub.n]([[lambda].sub.1], ..., [[lambda].sub.k]) := 2n + 2g' - r where r := [summation] r ([[lambda].sub.i]).

Define [h.sup.g.sub.n]([[lambda].sub.1], ..., [[lambda].sub.k]) by 1/n! times the number of pairs (C, F) where C is a constellation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Define Hurwitz series by the following generating functions:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By choosing first the constellation then the fixed parts, one obtains the relation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

2.4 Hurwitz series in genera 0 and 1

In spherical or toric genus, one has closed formula stemming from the ELSV formula for one-partition Hurwitz numbers. When one sees these relations in the series [H.sup.g]([lambda]), one obtains the following claim, which is a reformulation of unpublished results already known by Kazarian in [4]. We will need to define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any partition [lambda] = ([d.sub.1], [d.sub.p]) and any integer k [member of] [0,p].

Claim 3 (Hurwitz series in genera 0 and 1). Set a partition [lambda] of an integer a [greater than or equal to] 0 in p [greater than or equal to] 0 parts.

Then, one has the identities [H.sup.0]([lambda] = [D.sup.p-3] ([Y.sup.a-1]Z) and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Examples. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

for any [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Corollary 4 (asymptotics of one-partition Hurwitz numbers in genera 0 and 1). For any partition [lambda] and any genus g [member of] {0,1}, one has the following asymptotics

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof of Corollary 4. In null genus, one has the relation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Its leading coefficient is therefore equivalent to [n.sup.p-3] times [C.sub.1][e.sup.n]/n [[square root of n].sup.1] thanks to Claim 1. In toric genus, the first term [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has degree 2 + 2(p - 1) = 2p whereas the following terms [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for x [greater than or equal to] 1 have Z-degrees x + 2 (p - x) < 2p. One has therefore [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], whose leading coefficient is equivalent to [n.sup.p.-1] times [C.sub.2][e.sup.n]/n [[square root of n].sup.2].

2.5 Kazarian's formulae, and the asymptotics of one-partition Hurwitz numbers

Considering integration theory on the moduli space of complex curves with some marked points led Kazarian to the following formula (see [9]). The latter involves some rational-valued intersection numbers <[[tau].sup.u.sub.0][[tau].sup.v.sub.2]> defined (in [10]) for some integers u, v [greater than or equal to] 0. We will simply write <[[tau].sup.v.sub.2]> for <[[tau].sup.0.sub.0][[tau].sup.v.sub.2]>.

Theorem 5 (Kazarian's formula). Let [mu] = ([d.sub.1], ..., [d.sub.p]) be a partition of an integer a [greater than or equal to] 0 and g [greater than or equal to] 0 be a genus. Then, whenever n + 2g' > 0, one has [H.sup.g]([mu]) = [Y.sup.a] [(Z + 1).sup.2g'+p]P(Z) where P(Z) is a polynomial of leading term [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Corollary 6 (Kazarian's Z-formula). For any partition [lambda] and genus g [greater than or equal to] 0 such that p + 2g' > 0, one has the Z-equality [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Combining Corollary 6 with Claim 1 immediately yields the asymptotics of all [h.sup.g.sub.n]([lambda])'s when g [greater than or equal to] 2:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

A little more work (use the string and dilaton equations in [10]) on the numbers <[[tau].sup.u.sub.2][[tau].sup.v.sub.0]> can show that the constant [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is actually [lambda]-free, as we already know in genus 0 and 1 thanks to Corollary 4, hence the following.

Theorem 7 (asymptotics of one-partition Hurwitz numbers in any genus). For any partition [lambda] and any genus g [greater than or equal to] 0, one has the asymptotics

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

2.6 The main theorem and the general asymptotics of Hurwitz numbers

We can now state our main result, proven in section 3.2, which reduces the understanding of the asymptotics of several-partition Hurwitz numbers to that of single-partition Hurwitz numbers. Recall from [7] that all series [DH.sup.g] ([[lambda].sub.1], [[lambda].sub.k]) lie in the algebra A (it is a consequence of the conjunction of Claim 3, Theorem 5 and Theorem 10).

Theorem 8. For any partitions [[lambda].sub.1], ..., [[lambda].sub.k] and any genus g [greater than or equal to] 0, one has the following Z-equality in the algebra [A.sup.Z] :

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Corollary 9 (general asymptotics of Hurwitz numbers). For any partitions [[lambda].sub.1], ..., [[lambda].sub.k] and any genus g [greater than or equal to] 0, one has the following asymptotics for some constant [c.sub.g]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof of Corollary 9. If one sets [m.sub.1] := [summation][m.sub.1] ([[lambda].sub.i]) and p := [summation]l ([[lambda].sub.i]), Theorem 8 states the Z-equality [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], whence the asymptotics

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Remark. The constants <[[tau].sup.3g'.sub.2]> can recursively be computed thanks to Witten's conjecture (see [10] and [6]): if one sets [[alpha].sub.0] := 1/12 and [[alpha].sub.k]/5k(5k+2) := <[[tau].sup.3k.sub.2]>/(3k)! for any k [greater than or equal to] 1, then one will obtain the recursion

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The latter being very similar to that in [2] which defines the map asymptotics constants [t.sub.g], it is then easy to derive the identity [c.sub.g] = [[square root of 2].sup.g-3][t.sub.g] for any integer g [greater than or equal to] 0.

3 Reduction formulae

Zvonkine proved in [7] that all series [H.sup.g] ([[lambda].sub.1], ..., [[lambda].sub.k]) but [H.sup.1] (0) lay in the algebra A by induction on the number k of partitions, the case k = 1 being an immediate corollary from Theorem 5. We explicit the (unexplicited) induction formula used by Zvonkine so as to control the leading coefficients in Z of the series [H.sup.g] ([[lambda].sub.1], ..., [[lambda].sub.k]) and derive their asymptotics.

3.1 The reduction formula

Let us first carry out an analysis of what becomes a constellation after merging its first two permutations. We reproduce mostly what is explained in [7] but retain some more information.

Let ([sigma], [rho], [[sigma].sub.3], [[sigma].sub.4], ..., [[sigma].sub.k]) be a constellation and denote [pi] := [sigma][rho]. One gets k - 1 permutations [pi], [[sigma].sub.3], ..., [[sigma].sub.k] whose product is the identity, but one generally loses the transitivity condition. Denote [[OMEGA].sup.1], ..., [[OMEGA].sup.N] the orbits of our new group <[pi], [[sigma].sub.3], ..., [[sigma].sub.k]> and set [[sigma].sup.j.sub.i] for the permutation [[sigma].sub.i] induced on [[OMEGA].sub.j]. One thus obtains for any j a constellation ([[pi].sup.j], [[sigma].sup.j.sub.3], ..., [[sigma].sup.j.sub.k]) on the orbit [[OMEGA].sup.j]. A factor 1/N! will be needed to take into account the labelling of the orbits.

Notice that one always has [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This is trivial when S[sigma] [union] S[rho] is empty (since one then has [sigma] = Id and N = 1) and let us explain why, when S[sigma] [union] S[rho] is non-empty, every orbit must intersect it (hence N [less than or equal to] [absolute value of [lambda]] + [absolute value of [mu]]): if the group <[sigma], [rho], [[sigma].sub.3], ..., [[sigma].sub.k]> stabilised an orbit disjoint from S[sigma] [union] S[rho], then so would the group <[sigma], [rho], [[sigma].sub.3], ..., [[sigma].sub.k]> since [sigma] and [rho] acts trivially out of S[sigma] [union] S[rho], but the latter group is by assumption transitive, so the mentioned orbit must equal all [1, n], consequently intersecting S[sigma] [union] S[rho].

The genera [g.sup.j]'s satisfy the Riemann-Hurwitz relation [2n.sup.j] + [2g.sup.j'] = r([[pi].sup.j]) + [[summation].sup.k.sub.i=3] r([[sigma].sup.j.sub.i]). By summing up these relations and recalling that of our first constellation, one gets [summation][g.sup.j'] = g' - r([lambda])+r([mu])-r([pi])/2.

Furthermore, since S[pi] [subset] S[sigma] [union] S[rho], one can consider the type v of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as a partition of an integer smaller than [absolute value of S[sigma] [union] S[rho]] [less than or equal to] [absolute value of [lambda]]] + [absolute value of [mu]]. Let us be more precise and set [v.sup.j] for the type of the permutation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] induced of [[OMEGA].sup.j]: the [v.sup.j]'s are all non-empty (unless S[sigma] [union] S[rho] = 0, namely unless [??] = [??] = 0) and their sizes always sum up to that of [absolute value of v]. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has [m.sub.1] ([v.sup.j]) fixed points in [[OMEGA].sup.j] and the knowledge of these fixed points for all j's allows one to rebuild S[sigma] [union] S[rho] (add for any j these [m.sub.1]([v.sup.j]) points to the support of [[pi].sup.j]).

Finally, when one wants to factorise back [pi] = [sigma][rho], one has to choose [sigma] and [rho] satisfying the three following conditions: [sigma] and [rho] have respective types [bar.[lambda]] and [[bar.[mu]]; the union S[sigma] [union] S[rho] equals S[pi] union the preceedingly-chosen point; the group <[sigma], [rho], [[sigma].sub.3], ..., [[sigma].sub.k], [[tau].sub.1], ..., [[tau].sub.T]} acts transitively. A conjugation argument shows that the number [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of such choices depends only on the partitions [lambda], [mu], [??] it is besides not hard to show that the transitiveness condition amounts to a junction condition on the orbits [[OMEGA].sup.j] by the cycles of [sigma] or [rho] (see Definition 11).

By collecting constellations according to the datas above (N, [??], [??]), one can explicit the formula used by Zvonkine in [7] to prove that all series [H.sup.g] ([??]) but [H.sup.1] (0) lay in the algebra A. (Consider the above analysis as a sketch of proof). The reduction formula thus obtained relies on a family [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of non-negative integers that we will define just after stating the reduction formula.

Theorem 10 (reduction formula). Let g [greater than or equal to] 0 be a genus and [??] = ([lambda], [mu], [[lambda].sub.3], [[lambda].sub.4], [[lambda].sub.k]) be k partitions where k [greater than or equal to] 2 is an integer. One then has the following formula

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where one sums over: integers N [greater than or equal to] 1 smaller or equal to [absolute value of [??]] + [absolute value of [??]] + 1; the N-tuples ([??], [??]) such that 2g' = r([lambda]) + r([mu]) - r([??]) + [summation] [2g.sup.j'] (all [v.sup.j]'s being non-empty unless [??] = [??] = 0); for any i = 3, ..., k partitions (i) ([[lambda].sup.1.sub.i], ..., [[lambda].sup.N.sub.i]) whose concatenation is [[lambda].sub.i].

Definition 11 (the numbers [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]). Let N be a positive integer and set N + 2 partitions [lambda], [mu], [??]. For any j, consider [[OMEGA].sup.j] a [absolute value of [v.sup.j]]-sized set and [[pi].sup.j] a [v.sup.j]-typed permutation in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to be the number of factorisations in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of the permutation [PI] [[pi].sup.j] in a product [sigma] [rho] satisfying the three conditions:

1. the types of [sigma] and [rho] are respectively [bar.[lambda]] and [bar.[mu]];

2. the supports of [sigma] and [rho] cover all [??] [[OMEGA].sup.j], namely Fix[sigma] [intersection] Fix[rho] = 0;

3. (junction condition) for any j [not equal to] j', there is a finite sequence j = [j.sub.0], ..., [j.sub.L] = j' such that, for any p = 1, ..., L, there is a cycle of [sigma] or [rho] which intersects both orbits [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Remarks. The first condition shows that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] while the second condition yields the implication [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which ensures that the sum in Theorem 10 is finite.

When v is made with the only one partition [lambda] [??] [mu], the above inequality implies that [lambda] and [mu] are reduced and supports S[sigma] and S[rho] are disjoint. Then, choosing a factorisation amounts to choosing for any k [greater than or equal to] 2 which k-lengthed cycles of [pi] will appear in [sigma]. Therefore, one has [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which can be rewritten in a more convient way (for future application) as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

3.2 Proof of Theorem 8

We restate Theorem 8: for any partitions [[lambda].sub.1], ..., [[lambda].sub.k] and any genus g [greater than or equal to] 0, one has the following Z-equality in the algebra [A.sup.Z] for M large enough:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For the wondering reader, the exponent M is a trick to get rid of the exceptional cases.

As a first example, the information about the Z-degree in Kazarian's formulae can be stated without the condition p + 2g' > 0 by the simple equality [deg.sub.Z] [D.sup.3][H.sup.g] ([lambda]) = 5g + 2p + 1.

Let us prove the following generalisation for any M [greater than or equal to] 0: if the series [D.sup.M][H.sup.g] [lambda] lies in [A.sup.Z], then it has degree [deg.sub.Z] [D.sup.M][H.sup.g]([lambda]) = 2M + 5g' + 2p. Indeed, setting S := [H.sup.g]([lambda]), one can write on the one hand [D.sup.3] ([D.sup.M]S) = 2 x 3 + [deg.sub.Z] [D.sup.M]S and on the other hand [D.sup.M] ([D.sup.3]S) = 2M + 5g' + 2p + 6; equalling both members leads to the conclusion.

Let us now prove for any S [member of] A, S [member of] [A.sup.Z] [??] [for all]M [greater than or equal to] 0, [deg.sub.Z] [D.sup.M] S [greater than or equal to] 2M. The arrow [??] stems from DP (Z) [??] [Z.sup.3]P'(Z). Conversely, if S is a polynomial P(Y), then DS = P'(Y) Z has Z-degree [less than or equal to] 1 and hence [D.sup.M]S = [D.sup.M-1]DS has degree [greater than or equal to] 1 + 2(M - 1) < 2M.

Finally, let us prove the following corollary of Theorem 8.

Corollary 12 (which series [H.sup.g] lie in [A.sup.Z]). For any non-empty partitions [[lambda].sub.1], ..., [[lambda].sub.k], [lambda], [mu]:

1. [H.sup.g] ([[lambda].sub.1], ..., [[lambda].sub.k]) always lies in [A.sup.Z] when k [greater than or equal to] 3.

2. [H.sup.g] ([lambda], [mu]) does not lie in [A.sup.Z] if and only if g = 0 and if both [lambda] and [mu] have one part.

3. [H.sup.g] ([lambda]) does not lie in [A.sup.Z] if and only if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof. Take the Z-degree in the given Z-equality and use Corollary 6:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Since all lengths are [greater than or equal to] 1, the above degree is [greater than or equal to] 2M when k [greater than or equal to] 3. When k = 2, the above degree is < 2M if and only if g = 0 and l([[lambda].sub.i]) = 1 for i = 1, 2. When k = 1, one retrieves the already-known exceptional cases of Kazarian's formulae.

We now proceed with the proof of Theorem 8, by induction on the number k of partitions. The case k = 1 is immediate from Corollary 6. Because of the number of exceptional cases, the case k = 2 will be the longest to deal with, the case k = 3 much similar and much easier, and greater k's will be almost straightforward. We start with k [greater than or equal to] 4 to get used to the idea, then k = 3 and finally k = 2, the induction hypothesis allowing one to use the corresponding parts of Corollary 12.

To derive the wanted Z-equality from Theorem 10, one has to analyse the contribution in Z of each product [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; one will eventually prove the following Z-equality:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(notice it already stands as a plain equality when [??] = [??] = 0, the reason for which we will leave that case aside below). It is then easy to derive the Z-equality of Theorem 8: remove the bars on top of [lambda] and [mu] by multiplying by the binomials [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; since D strictly increases [deg.sub.Z], one can multiply instead by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and still get a Z-equality [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; to get from H to H, divide both sides by [lambda][mu][[lambda].sub.3] ... [[lambda].sub.k]; to conclude, use the identity [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the induction hypothesis.

Case k [greater than or equal to] 4. One has [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by Theorem 10 where every factor [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] lies in [A.sup.Z] by Corollary 12 for k - 1 partitions (recall all [v.sup.j]'s are non-empty since we left aside the case [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has therefore Z-degree

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Everything is constant except 5[absolute value of v] - l[v]/2. Lemma 13 then shows that the above quantity is maximal if and only if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; since this implies N = 1 and [??] = (g), one gets the announced Z-reduction formula.

Case k = 3. We go along the same idea. Fix a genus g [greater than or equal to] 0 and three partitions [lambda], [mu], [xi]. Let p :=l (v) + l([xi]) and [p.sup.j] defined alike for all j. Theorem 10 then implies for any integer M [greater than or equal to] 0

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the sum over [??] is taken over the N-tuples of Pon-negative integers [M.sup.j]'s which sum up to M. By the induction hypothesis for k = 2, the term [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] lies in [A.sup.Z] for M large enough. Fix such an M. We then show that all other terms have Z-degree smaller than the latter.

By Corollary 12 for two partitions, a factor [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] will belong to Q[Y] if and only if ([g.sup.j], [p.sup.j], [M.sup.j]) = (0, 2, 0); multiplying by such an element will decrease (ii) the Z-degree. As for the other factors, the D-trick combined with Corollary 12 for two partitions shows that their Z-degree is [5g.sup.j'] + [2p.sup.j] + [2M.sup.j]. The product [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has therefore Z- degree [less than or equal to] [[summation].sub.Z] [5g.sup.j'] + [2p.sup.j] + [2M.sup.j] where the index Z means that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] lies in [A.sup.Z].

Set e := # {j; ([g.sup.j], [p.sup.j], [M.sup.j]) = (0,2,0)} for the number of exceptional factors with no Z. The three previous Z-sums can be linked to the same sums without restriction:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

One can thus derive the majoration

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Like when k [greater than or equal to] 4, everything is constant except 5[absolute value of v] - l(v)/2 + e; since there is at least one [M.sup.j] [greater than or equal to] 1 (thanks to the trick of applying D), one has e < N - 1 < 3 (N - 1) and Lemma 13 still holds: the maximal-Z-degreed term [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in the sum [D.sup.M] [H.sup.g] ([bar.[lambda]], [bar.[mu]], [xi]) is precisely [D.sup.M] [H.sup.g] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Case k = 2. The proof goes as above. Fix g [greater than or equal to] 0 any genus and [lambda], [mu] two partitions. For any M [greater than or equal to] 0, Theorem 10 implies that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By Corollary 12 for one partition (namely Corollary 6), a factor [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] will belong to Q[Y] if and only if ([g.sup.j], [p.sup.j], [M.sup.j]) [member of] {(0,1,1), (0,1,0), (0,2,0)}. For the other factors, we have already stated that their degrees were [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The product [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has therefore Z-degree [less than or equal to] [[summation].sub.Z] 5[g.sup.j]' + 2[p.sup.j] + 2[M.sup.j]. After linking the Z-sums to the (no Z)-sums, one obtains the majoration

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The three sets whose cardinalities are involved being mutually disjoint, the corresponding sum is [less than or equal to] N and one can even replace N by N - 1 if there is at least one [M.sup.j] [greater than or equal to] 2, which can be realised by choosing M [greater than or equal to] 2 ([absolute value of [??]] + [absolute value of [??]] + 1) [greater than or equal to] 2N. Therefore, one can still apply Lemma 13 and conclude, which finishes the proof of Theorem 8.

Lemma 13. Let [lambda], [mu] be two partitions and [sigma], [rho] two permutation in [S.sub.[infinity]] of type ([bar.[lambda]],[bar.[mu]]). Denote v the partition of [sigma][rho] induced on S[sigma] [union] S[rho]. Cluster the cycles of v into N orbits such that the junction condition of Definition 11 is satisfied. Then the quantity 5[absolute value of v]-l(v)/2 + 3 (N - 1) is maximal if and only if [sigma] and [rho] have disjoint supports. (And, in that case, one has N = 1.)

Proof. Call a cycle of [sigma] or [rho] to be interlaced if it encounters another cycle of [sigma] or [rho] (and two such cycles will be called interlaced with each other). Set c for the number of interlaced cycles and c' for the number of cycles (included fixed cycles) of the product [sigma] [rho] induced on the interlaced cycles (of [sigma] and [rho]).

A crucial remark is the following: for the junction condition to be satisfied, every cycle of v must lie in the same orbit as an interlaced cycle, whence the inequality N [less than or equal to] c'.

If one sets k := [absolute value of S[sigma] [intersection] S[rho]] for the number of contact points of the supports, one can write

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

When S[sigma] [intersection] S[rho] = [??], all variables c, c', k, N - 1 equal 0 and so does Q. One has therefore to show Q < 0, namely -2Q [greater than or equal to] 1, for any other v than [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By the crucial remark, it suffices to show the same inequality 5k + c' - c - 2 (3N - 3) [greater than or equal to] 1 with some N's been replaced by the same number of c''s: so as to kill the c' in the inequality, we remplace one N out of six, which lead us to wonder if the inequality 5 (k + 1 - N) [greater than or equal to] c holds. We are going to show by induction on [absolute value of S[sigma]] + [absolute value of S[rho]] the stronger inequality

2(k - N + 1) [greater than or equal to] c.

When [sigma] = [rho] = Id, then all three quantitites c, k, N - 1 equal 0, whence the above inequality.

Suppose now [absolute value of [??]] + [absolute value of [??]] > 0. Because of the assumption [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], one has k [greater than or equal to] 1: take one contact point x in S[sigma] [intersection] S[rho], set y := [sigma](x) and [tau] := (x, y) the transposition exchanging these points. Finally, write [sigma] = [tau][[sigma].sub.*], where [[sigma].sub.*] := [tau][sigma] fixes x and therefore satisfies [absolute value of [[sigma].sup.*] < [absolute value of [lambda]]. Thus, one obtains the cycle decomposition of [sigma][rho] by multiplying that of [[sigma].sub.*][rho] by the transposition [tau] on the left (and conversely). Denote by a *-subscript the quantities [c.sub.*], [k.sub.*], [N.sub.*] associated to the product of [[sigma].sub.*] and [rho]; notice that [N.sub.*] is not well-defined and can be chosen arbitrarily as long as the junction condition is satisfied. For such an [N.sub.*], one has the induction hypothesis [c.sub.*] [less than or equal to] 2 ([k.sub.*] - [N.sub.*] + 1). What we want is to dispose of the *'s.

Since x is fixed by [[sigma].sub.*], it disappears from the contact points, hence [k.sub.*] < k. Besides, [[sigma].sub.*] loses at most one interlaced cycle (it can only be the [sigma]-orbit of x) and [rho] loses at most two interlaced cycles (those maybe interlaced with [tau]), hence [c.sub.*] [greater than or equal to] c - 3. But the case [c.sub.*] = c - 3 implies x's [sigma]-orbit to be a transposition interlaced with two [rho]-cycles, each of which not being interlaced with another [sigma]-cycle; since [sigma] and [rho] play symmetric roles (set y := [rho](x) instead of [sigma](x)), one can avoid this case and hence assume [c.sub.*] [greater than or equal to] c - 2.

Let us look at what happens to the cycles of [sigma][rho] when composing (on the left) by [tau]. If a ([sigma][rho]-)cycle [gamma] is split in two cycles, cluster them in the same orbit as [gamma]'s orbit (hence [N.sub.*] = N). If two cycles are joined, either both cycles were in the same orbit (then, do not change the orbits, hence [N.sub.*] = N) or they were in distinct orbits (then, merge these orbits and do not change the others, hence [N.sub.*] = N - 1). Whenever [N.sub.*] = N, one can conclude by writing

c [less than or equal to] [c.sub.*] + 2 [less than or equal to] 2([k.sub.*] - [N.sub.*] + 1) + 2 [less than or equal to] 2((k - 1) - N + 1) + 2 = 2(k - N + 1).

We can consequently assume [N.sub.*] = N - 1 and hence [tau] joining two [sigma][rho]-cycles, which goes the same as saying x and y not to lie in the same [sigma][rho]-orbit. But that implies both [sigma]- and [rho]-orbits of x to remain interlaced for [[sigma].sub.*] and [rho] (if not, iterate [sigma][rho] in a not-interlaced orbit to join x and y), hence [c.sub.*] = c and the induction hypothesis yields

c = [c.sub.*] [less than or equal to] 2([k.sub.*] - [N.sub.*] + 1) [less than or equal to] 2((k - 1) - (N - 1) + 1) = 2(k - N + 1).

References

[1] G. CHAPUIS, Combinatoire bijective des cartes en genre superieur, PhD thesis, June 9th 2009.

[2] E. A. BENDER, Z. GAO AND L. R. RICHMOND, The Map Asymptotics Constant [t.sub.g], The Electronic Journal of Combinatorics, Mar 27, 2008; Corrigendum Jul 28, 2008.

[3] T. EKEDAHL, S. K. LANDO, M. SHAPIRO AND A. VAINSHTEIN, Hurwitz numbers and intersections on moduli spaces of curves, arxiv:math.AG/0004096, 2004.

[4] M. KAZARIAN, On computations of Hurwitz numbers, work in preparation (in Russian).

[5] S. LANDO and A. Zvonkin, Graphs on surfaces and their applications, Springer, 2004.

[6] A. OKOUNKOV and R. Pandharipande, Gromov-Witten theory, Hurwitz numbers, and Matrix models, I, arXiv:math.AG/0101147v2, 2001.

[7] D. ZVONKINE, Counting ramified coverings and intersection theory on Hurwitz spaces II, arxiv:math.AG/0304251, 2003.

[8] D. ZVONKINE, An algebra ofpower series arising in the intersection theory of the moduli spaces of curves ans in the enumeration of ramified coverings of the sphere, arxiv:math.AG/0403092, 2007.

[9] D. ZVONKINE, Enumeration of ramified coverings of the sphere and 2-dimensional gravity, arxiv:math.AG/0506248, 2005.

[10] D. ZVONKINE, Intersection theory of moduli spaces of stable curves, Lecture given in the Journees mathematiques de Glanon, March 1st 2007.

Marc Sage ([dagger])

Institut Gaspard Monge--University Paris-Est Marne-La-Vallee--Marne-La-Vallee--France

([dagger]) sage@phare.normalesup.org

(i) when k = 2, one sums (not over nothing but) over the empty list

(ii) strictly if and only if its (Y-)coefficients sum up to zero