EQUATIONS IN FINITE SEMIGROUPS

Explicit enumeration and asymptotics of solution numbers

C. KRATTENTHALER^{†} AND T. W. MÜLLER

Abstract. We study the number of solutions of the general semigroup equation in one variable, X^{α} = X^{β}, as well as of the system of equations X^{2} = X, Y^{2} = Y, XY = Y X in H ≀ T_{n}, the wreath product of an arbitrary finite group H with the full transformation semigroup T_{n} on n letters. For these solution numbers, we provide explicit exact formulae, as well as asymptotic estimates. Our results concerning the first mentioned problem generalize earlier results by Harris and Schoenfeld (J. Combin. Theory Ser. A 3 (1967), 122–135) on the number of idempotents in T_{n}, and a result of Dress and the second author (Adv. in Math. 129 (1997), 188–221). Among the asymptotic tools employed are Hayman’s method for the estimation of coefficients of analytic functions and the Poisson summation formula.

1. Introduction

For a finite group G and for a positive integer d, denote by s_{G}(d) the number of subgroups in G of index d. It is well known that the number | Hom(G, S_{n})| of G-actions on an n-set satisfies the identity

∑_{n=0}^{∞} | Hom(G, S_{n})|\frac{z^{n}}{n!} = exp (∑_{d|m} \frac{s_{G}(d)}{d}z^{d}) , |G| = m;  (1.1)

cf., for instance, [12, Prop. 1] or [6, Prop. 1]. Formula (1.1), which exhibits the exponential generating function of the sequence | Hom(G, S_{n})| as a rather simple type of entire function, can be made the starting point for the asymptotic enumeration of finite group actions; cf. [13, Sec. 1] or [14].

Of course, after choosing a finite presentation for G, | Hom(G, S_{n})| can be interpreted as the number of solutions in S_{n} of a certain system of equations (corresponding to the set of relations in this presentation). For instance, denoting by ι_{H}(m) the number of solutions of the equation X^{m} = 1 in a finite group H, the case G = C_{m} of (1.1) yields the formula

∑_{n=0}^{∞} ι_{S_{n}}(m)\frac{z^{n}}{n!} = exp (∑_{d|m} z^{d}/d) ,  (1.2)

first proved in [4].

2000 Mathematics Subject Classification. Primary 05A16; Secondary 05A15 05E99 16W22 20M20. Key words and phrases. Equations in semigroups, wreath products, asymptotics of solution num-

bers, Hayman asymptotics, multinomial sum.

†Research partially supported by the Austrian Science Foundation FWF, grants P12094-MAT and P13190-MAT, and by EC’s IHRP Programme, grant HPRN-CT-2001-00272, “Algebraic Combinatorics in Europe”.

Moreover, let G and H be finite groups. Then it is shown (among other things) in [15] that

∑_{n=0}^{∞} | Hom(G, H ≀ S_{n})|\frac{z^{n}}{n!} = exp (∑_{d|m} \frac{|H|^{d−1}s_{G}^{H}(d)}{d}z^{d}) ,  (1.3)

where

s_{G}^{H}(d) := ∑_{(G:U)=d} | Hom(U, H)|,

this formula leading to corresponding asymptotic estimates for | Hom(G, H ≀S_{n})| by the methods developed in [14]. A noteworthy special case, originally due to Chigira [3], is the formula

∑_{n=0}^{∞} ι_{H≀S_{n}}(m)\frac{z^{n}}{n!} = exp (∑_{d|m} \frac{|H|^{d−1}ι_{H}(m/d)}{d}z^{d}) .  (1.4)

In this case, the main result of [14] provides an asymptotic expansion for ι_{H≀S_{n}}(m), whose main term yields the asymptotic formula

ι_{H≀S_{n}}(m) ∼ K(|H|n)^{(1−1/m)n} exp (−(1 − \frac{1}{m})n + ∑_{d|m} \frac{ι_{H}(m/d)}{d |H|^{1−d/m}} n^{d/m}) ,  (1.5)

where

K = \begin{cases}\sqrt{m}, & m odd, \\ \sqrt{m} exp (−\frac{|H|^{m−2}(ι_{H}(2))^{2}}{2|H|^{m−1}m} ) , & m even. \end{cases}

The present paper arose out of an attempt to establish analogues of (1.1)–(1.5) for the number of solutions of equations (or systems of equations) in the transformation semigroups T_{n}, and, more generally, in wreath products H ≀T_{n}, where H is a fixed finite monoid.

Our first result, Theorem 1, computes the exponential generating function for the number s(n) of solutions in H ≀ T_{n} of the most general semigroup equation in one variable, that is,

X^{α} = X^{β}, 0 ≤ α ≤ β,

in the case where H is a finite group. We find that

∑_{n≥0} s(n) \frac{z^{n}}{n!} = exp (\frac{1}{|H|} ∑_{γ|β−α} γ^{−1} ι_{H}(\frac{β−α}{γ})((Δ_{α}(|H|z))^{γ}), ),  (1.6)

where the sequence of functions {Δ_{α}(z)}_{α≥0} is recursively defined via

\begin{aligned}Δ_{0}(z) & = z, \\ Δ_{α}(z) & = z exp(Δ_{α−1}(z)), α ≥ 1. \end{aligned}  (1.7)

Moreover, Theorem 1 also computes in closed terms certain refinements of the series ∑_{n≥0} s(n) z^{n}/n!. Thus, it extends a previous result by Dress and the second author [6, Prop. 2] from transformation semigroups to wreath products of groups with transformation semigroups. The special case of (1.6) where H = {1} answers a question of Stanley’s posed in [21, Ex. 6.9]. We list several other interesting specializations as examples after the proof of Theorem 1.

Combining (1.6) with Hayman’s machinery [11] and some detailed asymptotic calculations then leads to our first main result, namely an asymptotic formula for s(n) in terms of the real root of a certain transcendental equation; cf. Theorem 3. Formulae (1.6) and (3.12) should be seen as semigroup analogues of Formulae (1.4) and (1.5) in the group case. We conclude the first part of the paper by applying this general formula in the special case α = 1; see the example after the proof of Theorem 3. In particular, we recover the result by Harris and Schoenfeld [9, Eq. (29)] concerning the asymptotics of the number of solutions of X^{2} = X in the transformation semigroup T_{n}.

For systems of equations, the situation appears to be considerably more involved. The (larger) second part of our paper is concerned exclusively with an analysis of the particularly simple system of equations

X^{2} = X,  (1.8)
Y^{2} = Y,  (1.9)
XY = Y X.  (1.10)

We begin by combinatorially characterising the solutions of (1.8)–(1.10) in H ≀ T_{n}, where H is a finite group, and then use this characterisation to explicitly compute the exponential generating function for the number a(n) of these solutions. The result is

∑_{n≥0} a(n)\frac{z^{n}}{n!} = exp (∑_{n≥0} |H|^{n−1}c(n)\frac{z^{n}}{n!} ) ,  (1.11)

where c(n) is equal to

c(n) = ∑_{0≤r,s,t≤n} \frac{n!}{r! s! t! (n − r − s − t)!}r^{n−r−s−t}s^{n−r−s+1};  (1.12)

cf. Corollary 7.

The second main result of our paper is the determination of the asymptotics for a(n). In Theorem 10 we find that

a(n) = |H|^{n−1}c(n) (1 + O (\frac{1}{n})) ,  as n → ∞,  (1.13)

the function c(n) being the one in (1.12), its asymptotics being given by

c(n) ∼ e^{\frac{n}{sn} (n−r_{n}+ \frac{1}{2} )−3n+2r_{n}+2s_{n}+t_{n}+1} (\frac{n}{s_{n}} )^{n} \frac{r_{n}^{1/2}s_{n}^{3/2}}{n} ,  as n → ∞,  (1.14)

where (r_{n}, s_{n}, t_{n}) is the unique solution for large n of the system of transcendental equations (7.5)–(7.7). The functions r_{n}, s_{n}, and t_{n} are only implicitly defined, and their asymptotic description naturally involves iterated logarithms as gauge functions. They are, hence, difficult to approximate. We prove (1.13) by determining the asymptotics of the triple sum (1.12) (leading to (1.14)), and then combining the latter result and the generating function identity (1.11) with Bender’s transfer method [1]. The hardest part of this argument concerns the asymptotic estimation of c(n), the reason being that classical analytic methods based on generating functions appear not to be applicable. Instead, we work directly from the triple sum (1.12), determine the location of those (r, s, t) which provide the main contribution to the sum, and compute its value by applying the Poisson summation formula; see the proof of Theorem 8.

Comparison of our result for the asymptotics of a(n), the number of solutions of (1.8)–(1.10) in H ≀ T_{n}, with our result for the asymptotics of the number of solutions of X^{2} = X in H ≀ T_{n} reveals that, not very surprisingly, the effect of commutativity is rather strong, more precisely, out of all pairs (X, Y) satisfying (1.8) and (1.9), the proportion of those satisfying also the commutative law (1.10) is exponentially small; compare Remark 5 in Section 6.

Our paper is organised as follows. In Section 2, we consider the exact enumeration of solutions of the equation X^{α} = X^{β} in H ≀ T_{n}, where H is a finite group. We solve the problem in Theorem 1 by providing a compact formula for the exponential generating function of (a refined version of) these solution numbers. The subsequent section, Section 3, is devoted to determining the asymptotics of these solution numbers, which we accomplish in Theorem 3. The remaining sections deal with the problem of enumerating solutions (X, Y) of the system of equations (1.8)–(1.10). In Section 4, we concentrate on solutions in T_{n}, and solve the problem of exact enumeration of these solutions in Theorems 4 and Corollary 5 by studying carefully the combinatorial structure of such solutions. Then, in Section 5, we extend these findings to the enumeration of solutions of this system of equations in H ≀ T_{n}, where H is a finite group; see Theorems 6 and Corollary 7. Sections 6–8 deal with the asymptotics of these solution numbers. The “opening” section, Section 6, provides an overview of the results, the main result being Theorems 8 and 10, and outlines their proofs. Missing details of these proofs are then supplied in Sections 7 and 8.

2. The equation X^{α} = X^{β} in H ≀ T_{n}

For a non-negative integer n let T_{n} denote the full transformation semigroup (or symmetric semigroup) on n letters, that is, the set of all maps on the standard n-set [n] = {1, 2, …, n} with multiplication given by (τ_{1} · τ_{2})(j) := τ_{2}(τ_{1}(j)). For a (finite) semigroup H with unit element 1 we form the semigroup

H ≀ T_{n} = {(f, τ) : f ∈ H^{[n]}, τ ∈ T_{n}},

with multiplication given by

(f_{1}, τ_{1}) · (f_{2}, τ_{2}) = (f, τ_{1} · τ_{2}),
f(j) = f_{1}(j)f_{2}(τ_{1}(j)), j ∈ [n].

Under this multiplication rule, H ≀ T_{n} is a semigroup with unit element (1, id), called the wreath product of H with T_{n}, the map 1 being identically 1. In what follows, H will always be taken as a finite group.

Given τ ∈ T_{n}, we may view τ as a directed graph on [n], by drawing an arrow from i to j if and only if τ(i) = j. See Figure 1 for the directed graph corresponding to the transformation τ_{0} given by τ_{0}(1) = 12, τ_{0}(2) = 6, τ_{0}(3) = 11, τ_{0}(4) = 5, τ_{0}(5) = 16, τ_{0}(6) = 2, τ_{0}(7) = 6, τ_{0}(8) = 12, τ_{0}(9) = 16, τ_{0}(10) = 8, τ_{0}(11) = 6, τ_{0}(12) = 5, τ_{0}(13) = 5, τ_{0}(14) = 11, τ_{0}(15) = 13, τ_{0}(16) = 1. It is a well-known fact (see for example [2, p. 41, Eq. (1)]), and easy to see, that the directed graph corresponding to a τ ∈ T_{n} is a set of unicyclic graphs, that is, every connected component of the graph is a directed cycle with trees attached to the vertices of the cycles.

2 6 3 7  11 14  1 4 5  8 9  10 12 13 15 16 Figure 1

Clearly, the vertices in a connected component form a τ-invariant subset. If we denote the sets of these vertices S_{1}, S_{2}, …, S_{k}, then the set [n] decomposes into a disjoint union [n] = S_{1} ˙∪ S_{2} ˙∪ ⋯ ˙∪ S_{k}, the sets S_{j} being non-empty τ-invariant sets which are indecomposable, that is, S_{j} itself is not the union of two disjoint non-empty τ-invariant subsets. Evidently, this decomposition of [n] is uniquely determined by these requirements. Formally, the equivalence relation inducing this decomposition of [n] is given by

j_{1} ∼ j_{2} :⇔ there exist integers k, l ≥ 0 such that τ^{k}(j_{1}) = τ^{l}(j_{2}).

We call S_{1}, S_{2}, …, S_{k} the components of τ, the numbers |S_{1}|, |S_{2}|, …, |S_{k}| are the decomposition numbers, and k is the decomposition length of τ. Given a pair of sets Λ, M, where Λ ⊆ ℕ and M ⊆ ℕ_{0}, a map τ : [n] → [n] is termed (Λ, M)-admissible if the decomposition numbers of τ are in Λ and the decomposition length is in M.

Given a finite group H, integers α and β with 0 ≤ α < β, and sets Λ ⊆ ℕ and M ⊆ ℕ_{0}, we write s_{Λ}^{M}(n) for the number of (Λ, M)-admissible solutions of

X^{α} = X^{β}  (2.1)

in H ≀ T_{n}.

Our first result computes the exponential generating function for the numbers s_{Λ}^{M}(n) in the case where H is a finite group. It extends a previous result by Dress and the second author [6, Prop. 2] from T_{n} to wreath products H ≀ T_{n}. For a power series f(z) = ∑_{k≥0} f_{k}z^{k} and a set K of non-negative integers we define the restriction (f(z))_{K} to be the series ∑_{k∈K} f_{k}z^{k}.

Theorem 1. Let H be a finite group. Then we have

∑_{n≥0} s_{Λ}^{M}(n) \frac{z^{n}}{n!} = e_{M}(\frac{1}{|H|} ∑_{γ|β−α} γ^{−1} ι_{H}(\frac{β−α}{γ})((Δ_{α}(|H|z))^{γ})_{Λ}),  (2.2)

where ι_{H}(m) is the number of solutions in H of the equation x^{m} = 1, e_{M}(z) := (exp(z))_{M}, and with Δ_{α} as in (1.7).

Proof. A pair (f, τ) ∈ H ≀ T_{n} satisfies (2.1) if and only if (i) τ satisfies (2.1) in T_{n}, and

(ii) for all j ∈ [n] the equation ∏_{ν=0}^{α−1} f(τ^{ν}(j)) = ∏_{ν=0}^{β−1} f(τ^{ν}(j)) holds in H. Since H is a group, (ii) is equivalent to

(ii’) ∏_{ν=α}^{β−1} f(τ^{ν}(j)) = 1 for all j ∈ [n]. A solution τ of (2.1) in T_{n} is the disjoint union of oriented cycles of lengths dividing β − α, with ingoing trees of height at most α (possibly 0) attached to each cycle point; and conversely, each map τ ∈ T_{n} of this form is a solution of (2.1). See [6, Sec. 3.2] for more details.

We have to determine, for each such τ, how many f ∈ H^{[n]} satisfy (ii’). Fix τ. If j ∈ [n] occurs in one of the trees of τ, then f(j) can be chosen arbitrarily in H, since such a vertex does not occur in (ii’). If c is a cycle of length γ in τ, and if x_{1}, x_{2}, …, x_{γ} denote the images of the vertices of c under f, then Equation (ii’) for these vertices is equivalent to the condition that

(x_{1}x_{2} ⋯ x_{γ})^{(β−α)/γ} = 1.  (2.3)

The problem of solving (2.3) can be decomposed into first choosing x ∈ H such that x^{(β−α)/γ} = 1, and then solving the equation x_{1}x_{2} ⋯ x_{γ} = x. Hence, Equation (2.3) has precisely

|H|^{γ−1} ι_{H}(\frac{β−α}{γ})

solutions. It follows that each solution τ of (2.1) in T_{n} can be paired with

∏_{K} |H|^{|K|−1} ι_{H}(\frac{β−α}{|c(K)|})  (2.4)

maps f ∈ H^{[n]} such that (f, τ) satisfies (2.1) in H≀T_{n}, where K runs over the components of τ, and c(K) is the cycle of K. Hence, writing |τ| := n if τ ∈ T_{n}, we have

∑_{n≥0} s_{Λ}^{M}(n) \frac{z^{n}}{n!} = ∑_{τ}′ \frac{z^{|τ|}}{|τ|!}  ∏_{K component of τ}|H|^{|K|−1} ι_{H}(\frac{β−α}{|c(K)|}),  (2.5)

where the sum is over all τ whose number of components is in M, where the sizes of the components are in Λ, and where the lengths of the cycle in the components divides β − α.

The best way to get a manageable expression for the exponential generating function of the numbers s_{Λ}^{M}(n) in (2.5) is to think in species-theoretic terms (cf. [2] for an in-depth exposition of “species theory”). The transformations τ which appear in the sum on the right-hand side of (2.5) belong to the (species-theoretic) composition Sets_{M}(Cycles_{β−α}(Trees_{≤α})), where Sets_{M} denotes the species of sets with cardinality in M, Cycles_{β−α} denotes the species of cycles of length dividing β − α, and where Trees_{≤α} denotes the species of trees of height ≤ α. The species Sets_{M}(Cycles_{β−α} (Trees_{≤α})) contains in fact a larger class of objects, since the condition that the sizes of components should be in Λ is not yet taken into account. So, let (Cycles_{β−α}(Trees_{≤α}))_{Λ} denote the subspecies of Cycles_{β−α}(Trees_{≤α}) which consists only of those objects having a size which is contained in Λ. Then to compute the right-hand side of (2.5) amounts to computing the (weighted) exponential generating function for the species Sets_{M}((Cycles_{β−α}(Trees_{≤α}))_{Λ}), where the weight of an object from that species is given by (2.4).

Clearly, the exponential generating function for Sets_{M} is e_{M}(x), the one for Cycles_{β−α} is ∑_{γ|β−α} z^{γ}/γ, and the one for Trees_{≤α} is Δ_{α}(z) with Δ_{α}(z) as defined in (1.7); the last assertion following inductively from the exponential principle (cf. e.g. [2, Theorem 1.4.2(a) with F = E, the species of sets, so that F (x) = exp(x)]). Hence, by the substitution theorem for species (cf. e.g. [2, Theorem 1.4.2(a)]), the exponential generating function for Cycles_{β−α}(Trees_{≤α}) is

∑_{γ|β−α} \frac{(Δ_{α}(z))^{γ}}{γ} .  (2.6)

However, we need a weighted enumeration of objects K from that species with the weight

|H|^{|K|−1} ι_{H}(\frac{β−α}{|c(K)|})  (2.7)

depending on the size |K| of the object and the size |c(K)| of the (unique) cycle of K. Hence, we have to modify (2.6) appropriately. Indeed, the weighted generating function for Cycles_{β−α}(Trees_{≤α}) with weight (2.7) is

\frac{1}{|H|} ∑_{γ|β−α} ι_{H}(\frac{β−α}{γ})\frac{(Δ_{α}(|H|z))^{γ}}{γ} .

Now, this series has to be restricted to powers z^{m} with m ∈ Λ to obtain the (weighted) generating function for (Cycles_{β−α}(Trees_{≤α}))_{Λ}, which, upon using the substitution theorem once more, must then be substituted into e_{M}(z), the generating function for Sets_{M}. This will give the weighted generating function (2.5) for the species Sets_{M} ((Cycles_{β−α}(Trees_{≤α}))_{Λ}) that we are looking for. The result is exactly the right-hand side of (2.2). □

Examples. For Λ = ℕ, M = ℕ_{0}, and H = {1}, Formula (2.2) specializes to the formula [8, Sect. 3.3.15, Ex. 3.3.31] of Goulden and Jackson, which in turn answers a question posed in [21]. However, the right-hand side of (2.2) is readily calculated for every choice of Λ, M, and H; for instance, we find for α = 1 that

∑_{n≥0} s_{Λ}^{M}(n)\frac{z^{n}}{n!} = e_{M}( ∑_{γ|β−1} γ^{−1} |H|^{γ−1} ι_{H}(\frac{β−1}{γ}) z^{γ} e_{(Λ−γ)∩ℕ_{0}}(γ|H|z)).  (2.8)

As a further illustration, let us take a closer look at the case α = 1, β = 2 of idempotents in H ≀ T_{n}. Setting s_{Λ}^{M}(n) = U_{n}(Λ, M, H), we find from (2.8) that

∑_{n≥0} U_{n}(Λ, M, H) \frac{z^{n}}{n!} = e_{M}(z e_{Λ−1}(|H|z)).  (2.9)

Taking M = 2ℕ_{0} and Λ = 2ℕ − 1, the right-hand side of (2.9) becomes

cosh(z cosh(|H|z)) = 1 + \frac{1}{2!}(|H|z)^{2} + \frac{13}{4!}(|H|z)^{4} + \frac{181}{6!}(|H|z)^{6} + \frac{3865}{8!}(|H|z)^{8} + ⋯,

while choosing M = 2ℕ_{0} + 1 and Λ = 2ℕ yields

sinh(z sinh(|H|z))

= \frac{2}{2!}(|H|z)^{2} + \frac{4}{4!}(|H|z)^{4} + \frac{126}{6!}(|H|z)^{6} + \frac{3368}{8!}(|H|z)^{8} + \frac{95770}{10!}(|H|z)^{10} + · · · .

As a final example, let us take M = 2ℕ_{0} and

Λ = Λ_{0} = {n ∈ ℕ : n ≡ 1 (3) and n ≥ 4}.

By (2.9), the exponential generating function of the number U_{n}(Λ_{0}, 2ℕ_{0}, H) of idempotent elements in H ≀ T_{n} with an even number of components all of whose lengths are congruent to 1 mod 3 and ≥ 4 is given by

∑_{n=0}^{∞} U_{n}(Λ_{0}, 2ℕ_{0}, H)\frac{z^{n}}{n!} = cosh (∑_{κ=1}^{∞} \frac{(|H|z)^{3κ+1}}{(3κ)!} )

= 1 + \frac{560}{8!}(|H|z)^{8} + \frac{9240}{11!}(|H|z)^{11} + \frac{124124}{14!}(|H|z)^{14} + \frac{672672000}{16!}(|H|z)^{16} + · · · .

3. Asymptotics of the solution numbers for X^{α} = X^{β} in H ≀ T_{n}

Here we shall combine Theorem 1 with analytic machinery developed by Hayman to analyse the asymptotic behaviour of the function s(n) := s_{ℕ}^{ℕ_{0}}(n) counting the number of the solutions of (2.1) in H ≀ T_{n}. Setting Λ = ℕ and M = ℕ_{0} in (2.2), the exponential generating function of s(n) is seen to be equal to

Ψ(z) := ∑_{n≥0} s(n) \frac{z^{n}}{n!} = exp (\frac{1}{|H|} ∑_{γ|β−α} γ^{−1} ι_{H}(\frac{β−α}{γ})(Δ_{α}(|H|z))^{γ}).

The version of Hayman’s result best suited for our purposes is the following.

Theorem 2. (Hayman) If f(z) = ∑_{n≥0} f_{n}z^{n} is admissible in |z| < R in the sense of [11], then

f_{n} ∼ \frac{f(r_{n})}{r_{n}^{n}\sqrt{2πb(r_{n})}} as n → ∞,  (3.1)

where r_{n} is the unique solution for large n of the equation a(r) = n in (R_{0}, R), with a(r) = rf′(r)/f(r), b(r) = ra′(r), and a suitably chosen constant R_{0} > 0.

This is [11, Cor. II, p. 69] (see also [18, Cor. 12.6]).

It follows immediately from Hayman’s definition of admissibility that zf(z) is admissible in |z| < R provided f(z) is admissible in this range. Combining this observation with the facts that e^{z} is admissible with R = ∞ (see [18, Example 12.7]) and that admissibility is preserved under exponentiation ([11, Theorem VI]; [18, Theorem 12.8]), we see that the functions Δ_{α}(z) defined in (1.7) are admissible, for each α ≥ 1, in the whole complex plane . The Corollary to [11, Theorem IX] (see also [18, Theorem 12.8]) combined with the above exponentiation rule now shows that Ψ(z) itself is admissible in the complex plane.

From now on we shall assume that α ≥ 1. Setting f(z) = Ψ(z) in the context of Theorem 2, we find that

a(r) = r ∑_{γ|β−α} ι_{H}(\frac{β−α}{γ})(Δ_{α}(|H|r))^{γ−1}Δ′_{α}(|H|r),  (3.2)

and that

b(r) = a(r) + |H|r^{2} ∑_{γ|β−α} ι_{H}(\frac{β−α}{γ})

× [(γ − 1)(Δ_{α}(|H|r))^{γ−2}(Δ′_{α}(|H|r))^{2} + (Δ_{α}(|H|r))^{γ−1}Δ′′_{α}(|H|r)]. (3.3)

As in Theorem 2, let r_{n} be the real root of the equation a(r) = n. Next, we shall obtain an asymptotic estimate for r_{n}. Clearly, r_{n} → ∞ as n → ∞; hence, for r = r_{n}, the dominating term on the right-hand side of (3.2) is the term with γ = β − α, and thus

n ∼ r_{n}(Δ_{α}(|H|r_{n}))^{β−α−1}Δ′_{α}(|H|r_{n}) as n → ∞.  (3.4)

Taking logarithms, this gives

log n ∼ log r_{n} + (β − α − 1) log Δ_{α}(|H|r_{n}) + log Δ′_{α}(|H|r_{n}).

Moreover, it follows by induction on α that

Δ′_{α}(|H|r_{n}) = Δ_{α}(|H|r_{n})g(n),

where exp(g(n)) = O(Δ_{α}(|H|r_{n})). This leads to

log n ∼ log r_{n} + (β − α) log Δ_{α}(|H|r_{n}).

Since α > 0, we may also neglect the term log r_{n}, thus obtaining

log Δ_{α}(|H|r_{n}) ∼ \frac{1}{β − α} log(n).

Substituting Δ_{α}(|H|r_{n}) = |H|r_{n} exp (Δ_{α−1}(|H|r_{n})) , we get

log(|H|r_{n}) + Δ_{α−1}(|H|r_{n}) ∼ \frac{1}{β − α} log(n).

Neglecting the first term on the left-hand side and taking logarithms gives

log Δ_{α−1}(|H|r_{n}) ∼ log (\frac{1}{β − α} log(n)).

For convenience, let us write log^{(m)}(z) for the “m-th iterate” of the logarithm, that is, log^{(m)}(z) := log(log^{(m−1)}(z)) and log^{(0)}(z) := z. Then, iterating the above procedure, we find that

Δ_{0}(|H|r) ∼ log^{(α−1)} (\frac{1}{β − α} log(n)),

and thus, finally,

r_{n} ∼ \frac{1}{|H|} log^{(α−1)} (\frac{1}{β − α} log(n)), α ≥ 1.  (3.5)

Note that the factor 1/(β − α) in (3.5) can be dropped for α ≥ 2.

Putting r = r_{n} in (3.3), and using (3.4) as well as the fact that the dominating term on the right-hand side of (3.3) is the summand for γ = β − α, we find that, as n → ∞,

b(r_{n}) ∼ n [1 + |H|r_{n} ((β − α − 1)\frac{Δ′_{α}(|H|r_{n})}{Δ_{α}(|H|r_{n})} + \frac{Δ′′_{α}(|H|r_{n})}{Δ′_{α}(|H|r_{n})})] .  (3.6)

By definition of Δ_{α}(z) we have

\frac{Δ′_{α}(z)}{Δ_{α}(z)} = z^{−1} + Δ′_{α−1}(z), α ≥ 1.

This gives

\frac{Δ′_{α}(z)}{Δ_{α}(z)} ∼ \frac{Δ′_{α−1}(z)}{Δ_{α−1}(z)}Δ_{α−1}(z) as z → ∞.  (3.7)

Iterating (3.7) and using the fact that

Δ′_{1}(z) ∼ Δ_{1}(z) as z → ∞,

we find that

\frac{Δ′_{α}(z)}{Δ_{α}(z)} ∼ Δ_{1}(z)Δ_{2}(z) ⋯ Δ_{α−1}(z) as z → ∞.  (3.8)

Again, by the definition of Δ_{α},

Δ′′_{α}(z) = −z^{−2}Δ_{α}(z) + z^{−1}Δ′_{α}(z) + Δ_{α}(z)Δ′′_{α−1}(z) + Δ′_{α−1}(z)Δ′_{α}(z).

Dividing both sides of this equation by Δ′_{α}(z), and using (3.7), we get

\frac{Δ′′_{α}(z)}{Δ′_{α}(z)} ∼ \frac{Δ′′_{α−1}(z)}{Δ′_{α−1}(z)} + \frac{Δ′_{α}(z)}{Δ_{α}(z)} as z → ∞.

Iterating the last equation, using (3.8) and ignoring negligible terms, we obtain

\frac{Δ′′_{α}(z)}{Δ′_{α}(z)} ∼ Δ_{1}(z)Δ_{2}(z) ⋯ Δ_{α−1}(z) as z → ∞.  (3.9)

Setting z = |H|r_{n} in (3.8) and (3.9), and using the resulting relation in (3.6), as well as (3.5), we obtain

b(r_{n}) ∼ (β − α)n log^{(α−1)} (\frac{1}{β − α} log(n))Δ_{1}(|H|r_{n})Δ_{2}(|H|r_{n}) ⋯ Δ_{α−1}(|H|r_{n}). (3.10)

Using (3.2) and the fact that a(r_{n}) = n allows us to rewrite Ψ(r_{n}) as

Ψ(r_{n}) = exp(\frac{nΔ_{α}(|H|r_{n})}{(β − α)|H|r_{n}Δ′_{α}(|H|r_{n})}

+ \frac{1}{|H|} ∑_{γ|β−α} (\frac{1}{γ} − \frac{1}{β − α}) ι_{H}(\frac{β−α}{γ})(Δ_{α}(|H|r_{n}))^{γ}). (3.11)

Inserting this equation and (3.10) in Hayman’s formula (3.1) finally gives the following result. (We remark that, using the main result by Harris and Schoenfeld in [10], we could also obtain a full asymptotic expansion, which we, however, omit for the sake of brevity.)

Theorem 3. Let H be a finite group, and let α and β be integers satisfying 0 < α < β. Then, as n → ∞, the number s(n) of solutions of the equation X^{α} = X^{β} in H ≀ T_{n} is asymptotically equal to

s(n) ∼ \frac{1}{r_{n}^{n}\sqrt{(β − α)Δ_{1}(|H|r_{n})Δ_{2}(|H|r_{n}) ⋯ Δ_{α−1}(|H|r_{n}) log^{(α−1)} (\frac{1}{β−α} log(n))}}

× exp((\frac{Δ_{α}(|H|r_{n})}{(β − α)|H|r_{n}Δ′_{α}(|H|r_{n})} + log n − 1)n

+ \frac{1}{|H|} ∑_{γ|β−α} (\frac{1}{γ} − \frac{1}{β − α}) ι_{H}(\frac{β−α}{γ})(Δ_{α}(|H|r_{n}))^{γ}), (3.12)

where r_{n} is the unique solution for large n of the equation

r ∑_{γ|β−α} ι_{H}(\frac{β−α}{γ})(Δ_{α}(|H|r))^{γ−1}Δ′_{α}(|H|r) = n.

Remark 1. For α = 0, the function s(n) in Theorem 3 counts the number of solutions of the equation X^{β} = 1 in the group H ≀ S_{n}. The asymptotics for this case, and, indeed, for the more general case of the function Hom(G, H ≀ S_{n}) with finite groups G and H, can be found in [15, Theorem 4]; cf. also [16, Eq. (30)] or [17, Eq. (49)].

Example. For α = 1, the statement of Theorem 3 simplifies, and we find that the number s(n) of solutions in H ≀ T_{n} of the equation X^{β} = X is asymptotically equal to

(\frac{n}{e r_{n}} )^{n} \frac{e^{\frac{n}{(β−1)(1+|H|r_{n})}}}{\sqrt{log n}} exp(\frac{1}{|H|} ∑_{γ|β−1} (\frac{1}{γ} − \frac{1}{β − 1}) ι_{H}(\frac{β−1}{γ})(|H|r_{n})^{γ}e^{|H|γr_{n}}),

where r_{n} is the unique solution for large n of

r ∑_{γ|β−1} ι_{H}(\frac{β−1}{γ})(|H|r)^{γ−1}(1 + |H|r)e^{γ|H|r} = n.

If we further specialize to the case where β = 2, the last formula simplifies further to

s(n) ∼ (\frac{n |H|}{e r_{n}})^{n} \frac{e^{\frac{n}{1+r_{n}}}}{\sqrt{log n}},

where r_{n} is the unique solution for large n of

r(1 + r)e^{r} = n |H|.

In the case that H = {1}, this result has been previously obtained by Harris and Schoenfeld; cf. [9, Eq. (29)]. For later use we observe that asymptotically, as n → ∞, we have

r_{n} = log n − 2 log log n + O (\frac{log log n}{log n}) ,

and, thus,

s(n) = n log (n)−n log (log n)−n+2\frac{n log (log n)}{log n}+\frac{n}{log n}+O (\frac{n (log (log n))^{2}}{(log n)^{2}} ) . (3.13)

4. The system of equations X^{2} = X, Y^{2} = Y, XY = Y X in T_{n}

In this section we consider the system of equations (1.8)–(1.10), and we ask for the number of solutions (X, Y) of this system in T_{n}^{2}.

Setting α = 1 and β = 2 in the proof of Theorem 1, we see that a solution X of (1.8) in T_{n}, when regarded as a directed graph on [n], is the disjoint union of loops with arrows pointing to the vertex of the loop; see Figure 2 for such a component. Of course, the same applies to any solution Y of (1.9).

v Figure 2

Let (X, Y) be a solution of the system (1.8)–(1.10). We regard such a pair (X, Y) as a directed graph on [n], where the edges can occur in two colours: the colour red, say, associated with the edges of the graph corresponding to X, the other colour, blue say, corresponding to the edges of the graph corresponding to Y.

As a first step, we are going to enumerate the solutions (X, Y) in T_{n}^{2} whose directed graph is connected, by which we mean that any two vertices can be reached from each other by travelling along edges of either colour and regardless of the direction of the edges. A typical example is displayed in Figure 3, where red edges are symbolized by fully drawn arrows, and blue edges are symbolized by dashed arrows. Let us write c(n) for this number.

Theorem 4. For n ≥ 1, the number c(n) of connected solutions (X, Y) ∈ (T_{n})^{2} of the system (1.8)–(1.10) is given by

c(n) = ∑_{0≤r,s,t≤n} \frac{n!}{r! s! t! (n − r − s − t)!}r^{n−r−s−t}s^{n−r−s+1},  (4.1)

where 0^{0} has to be interpreted as 1, and where m! is interpreted as ∞ for negative values of m, so that the sum in (4.1) is actually restricted to r + s + t ≤ n.

Proof. As we already observed, we may regard any solution (X, Y) of the system (1.8)– (1.10) as a graph with red and blue edges, where the “X-components” (connected components consisting of red arrows only) are loops with arrows pointing to the vertex of the loop, which are “connected” by blue arrows.

We first observe that the set of X-fixed points is invariant under the action of Y. To see this, let X(v) = v. Then X(Y (v)) = Y (X(v)) = Y (v).

Our second observation is that whenever vertices which are not X-fixed points are mapped to each other under Y, then the X-fixed points in the corresponding Xcomponents must be mapped to each other. That is, if X(w) = v and Y (w) = t, then Y (v) = Y (X(w)) = X(Y (w)) = X(t), where X(t) is the X-fixed point in the X-component containing t.

Consequently, if (X, Y) is connected, then there is exactly one X-fixed point, v_{0} say, with the property that it is also a fixed point of Y, and all other fixed points of X are mapped to v_{0} under Y. Thus, the typical form of a connected solution (X, Y) is as shown in Figure 3. There are several X-components, K_{0}, K_{1}, …, K_{r}, say, whose X-fixed points (in the figure these are v_{0}, v_{1}, …, v_{r}) are mapped under Y to the same X-fixed point v_{0}. In the X-component K_{0}, the component containing v_{0}, there may be some vertices different from v_{0} which are mapped to themselves under Y. (For example, in Figure 3, the vertex u_{1} is such a vertex.) Let the number of these vertices be s − 1 with some s ≥ 1, and let the number of the remaining vertices in K_{0} (including v_{0}) be t + 1. Out of the latter, the t vertices different from v_{0} are mapped under Y to one of the s fixed points under Y (including v_{0}). This is indicated in Figure 3 by the dashed lines going out of u_{2} and u_{3}. Finally, the vertices in the other X-components K_{1}, …, K_{r} which are not fixed points under X can be freely mapped under Y to the s fixed points under Y in K_{0}. Examples in Figure 3 are the vertices u_{4}, u_{6}, or u_{8}. (The reader must imagine that also the unfinished edges in Figure 3 lead to one of the s fixed points under Y in K_{0}.)

K_{0} K_{1}  K_{r} v^{0} v_{1}  v_{r} u_{1}  u_{2}  u_{3} u_{4} u_{5}  u_{6}  u_{7}  u_{8} Figure 3

Now let r, s, and t be fixed. How many such connected solutions of (1.8)–(1.10) are there (that is, configurations with n vertices such as in Figure 3), which have exactly r+1 X-components, which have s+t vertices in the X-component containing the vertex which is at the same time a fixed point for X and Y, and which have s fixed points of Y in that X-component (including the vertex which is fixed under X and Y)?

Firstly, out of n possible vertices, we have to choose the r fixed points under X which are not at the same time fixed under Y (in Figure 3 these are the vertices v_{1}, …, v_{r}), we have to choose the s fixed points under Y in the X-component K_{0} (in Figure 3 these are v_{0} and, e.g., u_{1}), we have to choose the t other vertices in K_{0} (in Figure 3 these are, e.g., u_{2} and u_{3}), and we have to choose the remaining (n − r − s − t) vertices. The number of these choices equals the multinomial coefficient

\frac{n!}{r! s! t! (n − r − s − t)!}.

Next, having made this choice, we must mark v_{0}, the vertex which is to be the fixed point under both X and Y, out of the s fixed points under Y in K_{0}. Clearly, this allows for s possible choices. Having done all that, the only freedom left for X- and Y -images of vertices is to determine the X- and Y -images of the (n − r − s − t) “remaining” vertices and the Y -images of the t vertices in K_{0} different from the Y -fixed points. The candidates for the X-images of the (n − r − s − t) “remaining” vertices are v_{1}, …, v_{r}. Hence, there are exactly r^{n−r−s−t} choices. The candidates for the Y -images of the (n − r − s − t) “remaining” vertices and the t vertices in K_{0} different from the Y -fixed points are the s fixed points under Y in K_{0}. Hence, there are exactly s^{n−r−s} choices.

In total, we obtain

\frac{n!}{r! s! t! (n − r − s − t)!} · s · r^{n−r−s−t} · s^{n−r−s}

choices. If we sum this term over all possible values of r, s, and t, then we obtain the expression in the statement of the theorem. □

Corollary 5. Let b(n) denote the number of all solutions (X, Y) ∈ (T_{n})^{2}, of the system (1.8)–(1.10). Then

∑_{n≥0} b(n)\frac{z^{n}}{n!} = exp (∑_{n≥0} c(n)\frac{z^{n}}{n!} ) ,

where c(n) is the number determined in Theorem 4.

Proof. This follows immediately from the exponential principle (cf. e.g. [2, Theorem 1.4.2(a) with F = E, the species of sets, so that F (x) = exp(x)]) and Theorem 4. □

5. The system of equations X^{2} = X, Y^{2} = Y, XY = Y X in H ≀ T_{n}

Here, we shall generalize the result of the previous section from the symmetric semigroup T_{n} to the wreath product H ≀T_{n}, where H is a finite group; cf. Section 2 for the definition of the wreath product.

Our next theorem determines the number d(n) of connected solutions (X, Y) of the system of equations (1.8)–(1.10) in H ≀ T_{n}. Being connected here means that, if X = (f, σ) and Y = (g, τ), then the pair (σ, τ) is connected in the sense of Section 4. As in Section 4, we denote by c(n) the number of solutions in T_{n} of the system (1.8)–(1.10).

Theorem 6. The number of connected solutions (X, Y) ∈ (H ≀ T_{n})^{2} of the system (1.8)–(1.10) is given by d(n) = |H|^{n−1}c(n), where c(n) is the number determined in Theorem 4.

Proof. Let (X, Y) ∈ (H ≀T_{n})^{2} be a solution of the system (1.8)–(1.10). By the definition of the wreath product, this is equivalent to

σ^{2} = σ, τ^{2} = τ, στ = τσ,  (5.1)

and

f(i) · f(σ(i)) = f(i),  (5.2)
g(i) · g(τ(i)) = g(i),  (5.3)
f(i) · g(σ(i)) = g(i) · f(τ(i)),  (5.4)

the latter equations being required for all i ∈ [n]. Equation (5.2) is equivalent to f(j) = 1 for j ∈ Im σ. Similarly, Equation (5.3) is equivalent to g(j) = 1 for j ∈ Im τ.

If i ∈ Im σ, i = σ(j) say, then (5.4) becomes

f(i) · g(σ(σ(j))) = g(i) · f(τ(σ(j))).

Since σ^{2} = σ, στ = τσ, and in view of our previous observations, this equation becomes 1 · g(i) = g(i) · 1, a tautology. Similarly, if i ∈ Im τ, Equation (5.4) is automatically satisfied by our previous findings.

We assign arbitrary values to f(i) for i ∈ Im τ\ Im σ and to g(i) for i ∈ Im σ\ Im τ. If we write r = | Im τ\ Im σ| and s − 1 = | Im σ\ Im τ| (which is in accordance with the notation in the proof of Theorem 4), then these are r + (s − 1) assignments, for which we have |H|^{r+s−1} possibilities. We shall see that no contradiction arises if this is done.

Now let i ∉ Im σ ∪ Im τ. We claim that f(i) can be chosen freely, and determines g(i) uniquely. Indeed, in Equation (5.4) the values g(σ(i)) and f(τ(i)) have been already assigned, and therefore f(i) determines g(i). Since every element in Im σ is in fact a σ-fixed point, and similarly for τ, and since we are considering a connected solution, the intersection Im σ ∩ Im τ consists of exactly one element (compare the proof of Theorem 4). Hence, we have | Im σ ∪ Im τ| = r + s, and, consequently, there are |H|^{n−r−s} possibilities for assigning values of f and g for i ∉ Im σ ∪ Im τ.

In total, given a connected pair (σ, τ) satisfying (5.1), there are

|H|^{r+s−1}|H|^{n−r−s} = |H|^{n−1}

possibilities to assign values for f and g. The claim of the theorem now follows immediately. □

Corollary 7. Let a(n) denote the number of all solutions (X, Y) ∈ (H ≀ T_{n})^{2}, of the system (1.8)–(1.10). Then

∑_{n≥0} a(n)\frac{z^{n}}{n!} = exp (∑_{n≥0} |H|^{n−1}c(n)\frac{z^{n}}{n!} ) ,

where c(n) is the number determined in Theorem 4.

Proof. This follows immediately from the exponential principle (cf. e.g. [2, Theorem 1.4.2(a) with F = E, the species of sets, so that F (x) = exp(x)]) and Theorem 6. □

6. Asymptotics of the solution numbers for the system X^{2} = X, Y^{2} = Y, XY = Y X in H ≀ T_{n}

In the remainder of this paper our aim is to establish an asymptotic estimate for the number a(n) of solutions (X, Y) ∈ (H ≀ T_{n})^{2} of the system of equations (1.8)–(1.10). Note first that the exponential generating function of the sequence c(n) (and hence also that of a(n)) diverges outside the origin. Indeed, by considering the summand in (4.1) with r = s = ⌊n/(2 log n)⌋ and t = 0, and applying Stirling’s formula, one sees that

log \frac{c(n)}{n!} ≫ \frac{1}{2}n log n.

Furthermore, attempts to use other types of generating functions, for instance

∑_{n≥0} c(n)\frac{z^{n}}{n!^{2}} ,

appear to lead to intractable analytic functions. Thus, complex analytic tools like Hayman’s in Theorem 2 do not seem to be applicable in this context. Instead, we will work directly from the sum formula for c(n) given in Theorem 4, and, in combination with a theorem of Bender, we shall obtain a compact asymptotic expression for a(n); see Theorem 10 below.

The crucial point is the proof of the following result, the main steps of which will be described below, leaving technical details for later sections.

Theorem 8. We have

c(n) ∼ e^{\frac{n}{sn} (n−r_{n}+ \frac{1}{2} )−3n+2r_{n}+2s_{n}+t_{n}+1} (\frac{n}{s_{n}} )^{n} \frac{r_{n}^{1/2}s_{n}^{3/2}}{n}  (6.1)
∼ e^{\frac{n}{sn} (n−r_{n}+ \frac{1}{2} )−3n+2r_{n}+2s_{n}+t_{n}+1} (\frac{n}{s_{n}} )^{n} \frac{n}{4 log^{2} n},  as n → ∞,  (6.2)

where (r_{n}, s_{n}, t_{n}) is the unique solution for large n of the system of equations (7.5)–(7.7).

Outline of proof. Given a large positive integer n, consider the function

F (r, s, t) = \frac{Γ(n + 1) r^{n−r−s−t} s^{n−r−s+1}}{Γ(r + 1) Γ(s + 1) Γ(t + 1) Γ(n − r − s − t + 1)}  (6.3)

for r, s, t ∈ Ω̃_{n}, where

Ω̃_{n} = {(r, s, t) ∈ ℝ^{3} : r ≥ 0, s ≥ 0, t ≥ 0, r + s + t ≤ n}.

In Lemmas 14 and 15 we demonstrate that F (r, s, t), which is nothing but an extension to real numbers of the summand in (4.1), attains its global maximum at a unique point (r_{n}, s_{n}, t_{n}) in the interior of Ω̃_{n}. This maximum point (r_{n}, s_{n}, t_{n}) is the solution of the system of transcendental equations (7.5)–(7.7), and Lemma 14 also provides the estimates

r_{n} ∼ s_{n} ∼ \frac{n}{2 log n}, as well as t_{n} ∼ 2 log n.  (6.4)

Next, in Lemma 23, we show that contributions to the sum (4.1), which in our present notation is

c(n) = ∑_{0≤r,s,t≤n} F (r, s, t),

which come from outside of a certain box Q_{n} containing (r_{n}, s_{n}, t_{n}) in its centre, are of the order of magnitude

o(F (r_{n}, s_{n}, t_{n}) n/ log^{2} n).  (6.5)

On the other hand, the summands of the “smaller” sum of summands coming from Q_{n},

∑_{(r,s,t)∈Q_{n}} F (r, s, t),

can be approximated in terms of more tractable functions, so that a consequence of the Poisson summation formula, given in Lemma 20, can be applied to obtain the compact estimate

F (r_{n}, s_{n}, t_{n})\frac{(2π)^{3/2}r_{n}s_{n}\sqrt{t_{n}}}{n}

for the latter sum; cf. Theorem 24. By (6.4), this term dominates the one in (6.5). The final step consists then in finding an asymptotic expression for F (r_{n}, s_{n}, t_{n}), which we do in Proposition 25. If everything is combined, the first line of formula (6.2) results. Obviously, the second line is a simple consequence, if one uses (6.4). □

Remark 2. As was said at the end of the last proof, the somewhat more explicit expression in the second line in (6.2) follows immediately from the expression in the first line, given the asymptotic information on r_{n}, s_{n}, and t_{n} provided by (6.4). We have stated the first expression, since the second one has considerably worse approximation behaviour, due to the fact that the quotient of r_{n} by its asymptotic equivalent n/(2 log n) converges to 1 only at a sub-logarithmic rate, with a similar statement applying to s_{n}. More details can be found in Remark 4 and Equations (7.9)–(7.11).

Remark 3. We expect the relative error of the asymptotic formulae in Theorem 8 to be of order O(1/n). A proof of this would require considerable extra work: at various places in the proofs of the Lemmas in Sections 7 and 8 the effects of higher terms in the occurring expansions would have to be taken into account, leading to a massive calculational effort.

The translation of (6.2) into an asymptotic estimate for the function a(n) is made possible by the main results of Bender [1] (see also [18, Theorem 7.3 with F (x, y) = exp(y)], as well as [23, 24]).

Lemma 9. If the power series A(x) = ∑_{n≥1} a_{n}x^{n} and B(x) = ∑_{n≥1} b_{n}x^{n} satisfy (i) B(x) = exp(A(x)), (ii) a_{n−1} = o(a_{n}) as n → ∞,

(iii) ∑_{k=1}^{n−1} |\frac{a_{k}a_{n−k}}{a_{n−1}} | = O(1),

then

b_{n} = a_{n} + O(a_{n−1}).

We are now in the position to state the second main result of this paper, and to describe the main steps of its proof, again leaving technical details for later sections.

Theorem 10. Let H be a finite group, and let a(n) denote the number of solutions in H ≀ T_{n} of the system of equations (1.8)–(1.10). Then

a(n) = |H|^{n−1}c(n) (1 + O (\frac{1}{n})) , as n → ∞,

with the asymptotics of c(n) being provided by Theorem 8.

Outline of proof. We use Lemma 9 with a_{n} = c(n)|H|^{n−1}/n! and b_{n} = a(n)/n!. In view of Corollary 7, the corresponding series A(x) and B(x) satisfy (i). It remains to verify the conditions (ii) and (iii).

We first consider (ii). Using the approximation (6.2) in Theorem 8, we obtain

\frac{a_{n−1}}{a_{n}} = \frac{n c(n − 1)}{|H| c(n)}

∼ \frac{1}{|H|} exp(\frac{n − 1}{s_{n−1}} ((n − 1) − r_{n−1} + \frac{1}{2}) − 3(n − 1) + 2r_{n−1} + 2s_{n−1} + t_{n−1} + 1

+ (n − 1) log(n − 1) − (n − 1) log s_{n−1} + log(n − 1) − 2 log log(n − 1)

−\frac{n}{s_{n}} (n − r_{n} + \frac{1}{2}) + 3n − 2r_{n} − 2s_{n} − t_{n} − 1

− n log n + n log s_{n} + 2 log log n).  (6.6)

We now appeal to the asymptotic information on r_{n}, s_{n}, t_{n} provided by Lemmas 14 and 17, which we substitute in the expression (6.6). The result is then simplified; for instance, one would estimate the term (n − 1)^{2}/s_{n−1} − n^{2}/s_{n}, occurring in the exponent in (6.6), as follows:

\frac{(n − 1)^{2}}{s_{n−1}} − \frac{n^{2}}{s_{n}} = \frac{(n − 1)^{2}s_{n} − n^{2} (s_{n} − \frac{1}{2 log n} + o (\frac{1}{log n}))}{s_{n−1}s_{n}}

= \frac{n^{2} \frac{1}{2 log n}}{s_{n−1}s_{n}} + \frac{1 − 2n}{s_{n−1}} + o (log n)

= (2 log n + o(log n)) − (4 log n + o(log n)) + o(log n)

= −2 log n + o(log n).  (6.7)

After a tedious but straightforward computation, we obtain that

\frac{a_{n−1}}{a_{n}} ∼ \frac{C_{1}}{n} ,  as n → ∞,  (6.8)

with an explicit constant C_{1}, whose exact value is of no relevance here. This establishes (ii).

In order to estimate the sum

∑_{k=1}^{n−1} \frac{a_{k}a_{n−k}}{a_{n−1}}  (6.9)

occurring in (iii), we observe first that it suffices to consider the sum from k = 2 to k = ⌊n/2⌋, since the sum is symmetric with respect to the substitution k → (n − k), and since the term for k = 1 is just 1. Now we divide the latter range into two parts, the interval I_{1} := {k : 2 ≤ k ≤ log log n} and the interval I_{2} := {log log n < k ≤ n/2}.

By Theorem 8 and Lemma 14, we have

a_{m} = exp(m log m + o(m log m)),  as m → ∞.  (6.10)

Therefore, if k ∈ I_{1}, then a_{k} ≲ exp ((log log n)(log log log n)) ≪ \sqrt{n}. This implies

\frac{a_{k}a_{n−k}}{a_{n−1}} ≪ \frac{\sqrt{n}a_{n−k}}{a_{n−1}} ≲ \frac{1}{\sqrt{n}},

the last inequality being due to (6.8). Therefore, the sum

∑_{k∈I_{1}} \frac{a_{k}a_{n−k}}{a_{n−1}}

is bounded.

If k ∈ I_{2}, then, using Theorem 8, we have

a_{k}a_{n−k} = |H|^{n} \frac{c(k) c(n − k)}{k! (n − k)!} ∼ |H|^{n} exp (Φ_{n}(k) − 2n + 2 − 2 log 4 − \frac{1}{2} log(2π)) ,

with Φ_{n}(k) the function defined in Lemma 19. Hence, uniformly in k and n, it is true that

a_{k}a_{n−k} < C_{2} |H|^{n} exp (Φ_{n}(k) − 2n) ,

for some constant C_{2}. Now, by Lemma 19, we have Φ_{n}(k) < Φ_{n}(2) for k ∈ I_{2}. Using Theorem 8 again, and the definition of Φ_{n}(2), it follows that

\frac{a_{k}a_{n−k}}{a_{n−1}} < C_{2}|H| \frac{(n − 1)! exp (Φ_{n}(2) − 2n)}{c(n − 1)}

< C_{3} exp(\frac{n − 2}{s_{n−2}} (n − r_{n−2} − \frac{3}{2}) + 2r_{n−2} + 2s_{n−2} + t_{n−2}

− (n − 2) log s_{n−2} + \frac{1}{2} log(n − 2) − 2 log log(n − 2)

− \frac{n − 1}{s_{n−1}} (n − r_{n−1} − \frac{1}{2}) − 2r_{n−1} − 2s_{n−1} − t_{n−1}

+ (n − 1) log s_{n−1} − \frac{1}{2} log(n − 1) + 2 log log(n − 1)),

for some constant C_{3}. By a similar calculation as the one which showed that the expression (6.7) is of the order of magnitude 1/n, we deduce that a_{k}a_{n−k}/a_{n−1} < C_{4}/n, for some constant C_{4}. Hence, the sum

∑_{k∈I_{2}} \frac{a_{k}a_{n−k}}{a_{n−1}}

is also bounded, and, thus, the complete sum (6.9), as required. □

Remark 4. Combining Theorems 8 and 10, we obtain an asymptotic formula for a(n) in terms of the transcendental functions r_{n}, s_{n}, t_{n}. In view of the speculative Remark 3, this formula should give an approximation with a relative error of O(1/n). On the other hand, by inserting the asymptotic expansions (7.9)–(7.11) for r_{n}, s_{n}, t_{n} into Equation (6.1), one obtains an asymptotic expansion for the exponent of a(n) in terms of elementary functions. The first terms of the latter expansion are

a(n) = |H|^{n−1} exp (2n log n − 2n log log n − 2 (log 2 + 1) n + 3\frac{n log log n}{log n}

+ (3 log 2 + 1)\frac{n}{log n} + O (\frac{n (log log n)^{4}}{(log n)^{2}} ) ). (6.11)

The gauge functions occurring in the exponent of (6.11) decay at a sub-logarithmic rate; hence, while providing a rough idea of the order of magnitude of a(n), Equation (6.11) is not useful for numerical purposes (whereas (6.1) in combination with Theorem 10 is).

Remark 5. It is interesting to compare the asymptotics for the number of solutions of (1.8)–(1.10) in H ≀ T_{n} on the one hand, and the square of the number of solutions of X^{2} = X in the same sequence of semigroups, since it allows us to estimate to what extent the commutative law (1.10) restricts solutions of (1.8) and (1.9). Using the expansions (6.11) and (3.13) we find that the quotient of these two numbers is asymptotically

\frac{a(n)}{s(n)^{2}} = exp (−(2 log 2)n − \frac{n log log n}{log n} + (3 log 2 − 1)\frac{n}{log n} + O (\frac{n(log log n)^{4}}{(log n)^{2}} )) ,

hence the commutative law effects a restriction of exponential order, on a sample space growing roughly like n^{2n}.

7. Auxiliary lemmas I: existence, uniqueness, and asymptotic properties of (r_{n}, s_{n}, t_{n})

The main results of this section are Lemma 15, where we prove uniqueness and determine the location of the global maximum (r_{n}, s_{n}, t_{n}) for the function F (r, s, t) defined in (6.3), Lemma 19, in which we prove that the auxiliary function Φ_{n}(k) defined there has a unique minimum and no maxima, and the asymptotic information on r_{n}, s_{n}, t_{n} gathered in (7.8) and Lemma 17. All other results in this section are of a preliminary nature, leading to the proofs of the aforementioned results.

Our first two lemmas deal with location and asymptotics of the maxima for an auxiliary function f(r, s).

Lemma 11. Given n ∈ ℕ, consider the function

f(r, s) = \frac{Γ(n + 1) r^{n−r−s} s^{n−r−s+1}}{Γ(r + 1) Γ(s + 1) Γ(n − r − s + 1)}

for (r, s) ∈ Ω_{n}, where Ω_{n} := {(r, s) ∈ ℝ^{2} : r ≥ 0, s ≥ 0, r + s ≤ n}. Then, for sufficiently large n, f(r, s) attains its maximum in the interior of Ω_{n}.

Proof. Since Ω_{n} is compact and f(r, s) is continuous on Ω_{n}, f attains a global maximum on Ω_{n}. We will show that

f(r, s) < f (\frac{n}{2 log n}, \frac{n}{2 log n})

for (r, s) ∈ ∂Ω_{n} and n large, which implies our claim.

Application of Stirling’s formula shows that

f (\frac{n}{2 log n}, \frac{n}{2 log n}) = exp (2n log n + O(n log log n)),  as n → ∞.  (7.1)

On the other hand, we have

f(0, s) ≤ \frac{Γ(n + 1) s^{n−s+1}}{Γ(s + 1) Γ(n − s + 1)} < 2^{n}n^{n+1} ≪ f (\frac{n}{2 log n}, \frac{n}{2 log n}) ,

and an analogous estimate holds for f(r, 0). If r + s = n, then

f(r, s) = \frac{Γ(n + 1) s}{Γ(r + 1)Γ(s + 1)} < 2^{n}n ≪ f (\frac{n}{2 log n}, \frac{n}{2 log n}) .

□

Lemma 12. Let (ξ_{n}, η_{n}) ∈ Ω_{n} be such that f(ξ_{n}, η_{n}) is maximal on Ω_{n}. Then

ξ_{n} ∼ η_{n} ∼ \frac{n}{2 log n}, as n → ∞.

Proof. Since f attains a maximum at (ξ_{n}, η_{n}), and as (ξ_{n}, η_{n}) ∉ ∂Ω_{n} by Lemma 11, the point (ξ_{n}, η_{n}) satisfies the equation (▽f)(ξ_{n}, η_{n}) = 0, which is equivalent to the system of equations

− log ξ_{n} + \frac{n − ξ_{n} − η_{n}}{ξ_{n}} − log η_{n} − ψ(ξ_{n} + 1) + ψ(n − ξ_{n} − η_{n}) = 0,  (7.2)
− log ξ_{n} + \frac{n − ξ_{n} − η_{n} + 1}{η_{n}} − log η_{n} − ψ(η_{n} + 1) + ψ(n − ξ_{n} − η_{n}) = 0,  (7.3)

where ψ(x) denotes the digamma function.

Suppose first that ξ_{n} ≫ n/ log n. Then the term (n − ξ_{n} − η_{n})/ξ_{n} in (7.2) is ≪ log n, whereas the remaining terms give a negative contribution of absolute value ≫ log n, which is seen upon recalling the asymptotic behaviour

ψ(x) = log x − \frac{1}{2x} − \frac{1}{12x^{2}} + O (\frac{1}{x^{4}} ) ,  as x → ∞,  (7.4)

of the digamma function (cf. [7, 1.18(7)]). But this contradicts (7.2). Hence, ξ_{n} ≲ n/ log n, and a similar argument based on Equation (7.3) shows that η_{n} ≲ n/ log n.

Now suppose that ξ_{n} ≪ n/ log n. Then the term (n − ξ_{n} − η_{n})/ξ_{n} in (7.2) is ≫ log n, whereas the remaining terms are at most O(log n), again contradicting (7.2). Hence we have ξ_{n} ≍ n/ log n, and the analogous argument based on Equation (7.3) shows that η_{n} ≍ n/ log n.

Now let ξ_{n} = α_{n} (n/ log n) with bounded α_{n}. Then another glance at Equation (7.2) gives

\frac{log n}{α_{n}} = 2 log n + O(log log n), as n → ∞,

that is, α_{n} = \frac{1}{2} + o(1), and thus ξ_{n} ∼ n/(2 log n).

The same argument with Equation (7.3) yields η_{n} ∼ n/(2 log n). □

Our next two results are analogues of Lemmas 11 and 12 for the function F (r, s, t).

Lemma 13. Given n ∈ ℕ, consider the function

F (r, s, t) = \frac{Γ(n + 1) r^{n−r−s−t} s^{n−r−s+1}}{Γ(r + 1) Γ(s + 1) Γ(t + 1) Γ(n − r − s − t + 1)}

for r, s, t ∈ Ω̃_{n}, where

Ω̃_{n} = {(r, s, t) ∈ ℝ^{3} : r ≥ 0, s ≥ 0, t ≥ 0, r + s + t ≤ n}.

Then, for sufficiently large n, F (r, s, t) attains its global maximum at points in the interior of Ω̃_{n}.

Proof. We argue in a similar fashion as in the proof of Lemma 11. In view of (7.1) we have

F (\frac{n}{2 log n}, \frac{n}{2 log n}, 0) = f (\frac{n}{2 log n}, \frac{n}{2 log n}) = exp (2n log n + O(n log log n)).

On the other hand, we have

F (0, s, t) ≤ \frac{Γ(n + 1) s^{n−s+1}}{Γ(s + 1) Γ(t + 1) Γ(n − s − t + 1)} ≤ 3^{n}n^{n+1} ≪ F (\frac{n}{2 log n}, \frac{n}{2 log n}, 0) ,

and an analogous estimate holds for F (r, 0, t). If r + s + t = n, then

F (r, s, t) = \frac{Γ(n + 1) s^{t+1}}{Γ(r + 1) Γ(s + 1) Γ(t + 1)} ≤ 3^{n}n^{n+1} ≪ F (\frac{n}{2 log n}, \frac{n}{2 log n}, 0) .

Finally, we have

F (r, s, 0) = \frac{r}{n − r − s}F (r, s, 1).

In Lemma 11 we proved that the left-hand side attains its maximum in the interior of Ω_{n}. Furthermore, by Lemma 12, any such point (ξ_{n}, η_{n}) satisfies ξ_{n} ∼ η_{n} ∼ n/(2 log n). Hence, for large n,

F (r, s, 0) ≤ F (ξ_{n}, η_{n}, 0) = \frac{ξ_{n}}{n − ξ_{n} − η_{n}} F (ξ_{n}, η_{n}, 1) < F (ξ_{n}, η_{n}, 1).

Thus, we have shown that, for n large, F (r, s, t) cannot attain its maximum on the boundary of Ω̃_{n}. This establishes the claim. □

Lemma 14. Let (r_{n}, s_{n}, t_{n}) ∈ Ω̃_{n} be such that F (r_{n}, s_{n}, t_{n}) is maximal on Ω̃_{n}. Then

− log r_{n} − log s_{n} + \frac{n − r_{n} − s_{n} − t_{n}}{r_{n}} − ψ(r_{n} + 1) + ψ(n − r_{n} − s_{n} − t_{n} + 1) = 0, (7.5)
− log r_{n} − log s_{n} + \frac{n − r_{n} − s_{n} + 1}{s_{n}} − ψ(s_{n} + 1) + ψ(n − r_{n} − s_{n} − t_{n} + 1) = 0, (7.6)
− log r_{n}  − ψ(t_{n} + 1) + ψ(n − r_{n} − s_{n} − t_{n} + 1) = 0. (7.7)

Moreover, we have

r_{n} ∼ s_{n} ∼ \frac{n}{2 log n} and t_{n} ∼ 2 log n.  (7.8)

Proof. Since F attains a maximum at (r_{n}, s_{n}, t_{n}), and since (r_{n}, s_{n}, t_{n}) ∉ ∂Ω̃_{n} by Lemma 13, the point (r_{n}, s_{n}, t_{n}) satisfies the equation (▽F)(r_{n}, s_{n}, t_{n}) = 0, which is equivalent to the system (7.5)–(7.7).

To obtain the claimed asymptotic estimates, we first assume that t_{n} ≍ n. Then Equation (7.7) implies that r_{n} = O(1). On the other hand, the term (n−r_{n}−s_{n}−t_{n})/r_{n} in (7.5) must be ≲ log n, because by (7.4) all the other terms in (7.5) are. Thus, the left-hand side of (7.7) is in fact ≤ − log n + O(log log n), a contradiction. Hence, we have t_{n} ≪ n.

Now the arguments from the second half of the proof of Lemma 12 can be used again, where instead of Equations (7.2) and (7.3) one considers Equations (7.5) and (7.6), to show that r_{n} ∼ s_{n} ∼ n/(2 log n).

Assuming that t_{n} = O(1), the left-hand side in (7.7) would be asymptotically equal to log log n + o(log log n), a contradiction. Hence t_{n} ≫ 1. If we now substitute all this information in (7.7), then we obtain log t_{n} = log(2 log n)+o(1), whence t_{n} ∼ 2 log n. □

Remark 6. Further terms in the asymptotic expansions of r_{n}, s_{n}, t_{n} can be obtained by an iterative procedure. Having already obtained the first few terms in the expansions, one adds, for each of r_{n}, s_{n}, t_{n}, a further indeterminate. This “extended” expansion is then substituted into Equations (7.5)–(7.7). Subsequently, asymptotic expansions are determined for the left-hand sides of these equations. Inspection of leading terms then yields a system of linear equations for the three indeterminates, which is solved. Thereafter, the next loop of the procedure can be started. Clearly, it is not advisable to do this by hand. However, with the help of Salvy’s Maple programme gdev [19, 20], these calculations are conveniently performed. The first terms, obtained in this way, turn out to be as follows:

r_{n} = \frac{1}{2} \frac{n}{log n} + \frac{3}{4} \frac{n log(log n)}{(log n)^{2}} + \frac{(3 log 2 − 2)}{4} \frac{n}{(log n)^{2}} + \frac{9}{8} \frac{n (log(log n))^{2}}{(log n)^{3}}

+ \frac{(18 log 2 − 21)}{8} \frac{n log(log n)}{(log n)^{3}} + \frac{(9(log 2)^{2} − 21 log 2 + 8)}{8} \frac{n}{(log n)^{3}}

+ \frac{27}{16} \frac{n (log(log n))^{3}}{(log n)^{4}} + \frac{(162 log 2 − 243)}{32} \frac{n (log(log n))^{2}}{(log n)^{4}}

+ \frac{(81(log 2)^{2} − 243 log 2 + 135)}{16} \frac{log(log n)}{(log n)^{4}}

+ \frac{(54(log 2)^{3} − 243(log 2)^{2} + 270 log 2 − 80)}{32} \frac{n}{(log n)^{4}} + O (\frac{n (log(log n))^{4}}{(log n)^{5}} ) , (7.9)

s_{n} = \frac{1}{2} \frac{n}{log n} + \frac{3}{4} \frac{n log(log n)}{(log n)^{2}} + \frac{3 log 2 − 2}{4} \frac{n}{(log n)^{2}} + \frac{9}{8} \frac{n (log(log n))^{2}}{(log n)^{3}}

+ \frac{(18 log 2 − 21)}{8} \frac{n log(log n)}{(log n)^{3}} + \frac{(9(log 2)^{2} − 21 log 2 + 8)}{8} \frac{n}{(log n)^{3}}

+ O (\frac{n (log(log n))^{4}}{(log n)^{4}} ) , (7.10) t_{n} = 2 log n − 3 log(log n) − 3 log 2 − 1 + \frac{9}{2} \frac{log(log n)}{log n} + \frac{(9 log 2 − 4)}{2} \frac{1}{log n}

+ \frac{27}{8} (log(log n))^{2} ; (log n)^{2} + \frac{(27 log 2 − 39)}{4} \frac{log(log n)}{(log n)^{2}} + O (\frac{1}{(log n)^{2}} ) . (7.11)

Lemma 15. For n large enough, the function F (r, s, t) attains its global maximum on Ω̃_{n} at a unique point in the interior of Ω̃_{n}.

Proof. Let (r, s, t) be a point in the interior of Ω̃_{n} with r ∼ s ∼ n/(2 log n) and t ∼ 2 log n, and let e = (a, b, c) be a unit vector in ℝ^{3}. We consider the function F along the line segment (r, s, t) + λe, with λ varying over a suitable interval containing 0. Differentiating twice with respect to λ we find

\frac{d^{2}}{dλ^{2}} ( log F (r + λa, s + λb, t + λc))
= − 2(a + b + c)\frac{a}{r + λa} − \frac{a^{2}}{(r + λa)^{2}} (n − r − s − t − (a + b + c)λ)

− 2(a + b)\frac{b}{s + λb} − \frac{b^{2}}{(s + λb)^{2}} (n − r − s − (a + b)λ + 1)

− a^{2}ψ^{(1)}(r + λa + 1) − b^{2}ψ^{(1)}(s + λb + 1) − c^{2}ψ^{(1)}(t + λc + 1)

− (a + b + c)^{2}ψ^{(1)}(n − r − s − t − (a + b + c)λ + 1),  (7.12)

where ψ^{(1)}(x) is the first polygamma function.

For λ ≪ n/ log n the second and fourth term on the right-hand side of (7.12) have order of magnitude (log n)^{2}/n, while all other terms are O(log n/n), which is seen upon making again use of the asymptotic expansion for the first polygamma function (cf. [7, 1.16(9) and 1.18(9)]),

ψ^{(1)}(x) = \frac{1}{x} + O (\frac{1}{x^{2}} ) ,  as x → ∞.  (7.13)

Hence, for large n and λ ≪ n/ log n, we have

\frac{d^{2}}{dλ^{2}} ( log F (r + λa, s + λb, t + λc)) < 0.

This shows that along each line segment

L = \{(r, s, t) + λe : λ ≪ \frac{n}{log n}\}

the function F attains at most one maximum for n large enough.

Now suppose that F attains its maximum at two different points (r_{1}, s_{1}, t_{1}) and (r_{2}, s_{2}, t_{2}). Then, by Lemma 14, r_{1} ∼ r_{2} ∼ s_{1} ∼ s_{2} ∼ n/(2 log n) and t_{1} ∼ t_{2} ∼ 2 log n. Considering the line segment through (r_{1}, s_{1}, t_{1}) and (r_{2}, s_{2}, t_{2}) we obtain r_{1} = r_{2}, s_{1} = s_{2}, and t_{1} = t_{2}, contradicting our assumption that (r_{1}, s_{1}, t_{1}) ≠ (r_{2}, s_{2}, t_{2}). □

In the sequel we write r′_{n} for the derivative of r_{n} with respect to n, regarding n as a real variable. (It can be checked that the proofs of Lemmas 11–15 concerning existence and uniqueness of the solution (r_{n}, s_{n}, t_{n}) for large n of the system of equations (7.5)– (7.7) remain valid for real n. Hence, r_{n}, s_{n}, and t_{n} are well-defined for large real n.)

Similarly, the symbol r′′_{n} denotes the second derivative of r_{n} with respect to n. We use the notation s′_{n}, s′′_{n}, t′_{n}, and t′′_{n} with analogous meaning.

The next two lemmas, Lemma 16 and 18, provide asymptotic estimates for r′_{n}, s′_{n}, t′_{n} and r′′_{n}, s′′_{n}, t′′_{n}, respectively. These are needed in the proofs of Corollary 17 and Lemma 19, the latter two being crucial for the proof of Theorem 10.

Lemma 16. Let (r_{n}, s_{n}, t_{n}) ∈ Ω̃_{n} be such that F (r_{n}, s_{n}, t_{n}) is maximal on Ω̃_{n}. Then

r′_{n} ∼ s′_{n} ∼ \frac{1}{2 log n} and t′_{n} ∼ \frac{2}{n},  as n → ∞.  (7.14)

Moreover, we have

(r_{n} − nr′_{n}) ∼ (s_{n} − ns′_{n}) ∼ \frac{n}{2 log^{2} n},  as n → ∞.  (7.15)

Proof. We consider the system of equations (7.5)–(7.7) for real n. Then, by the implicit function theorem, the system will have a (local) solution (r_{n}, s_{n}, t_{n}) as long as the determinant of the Jacobi matrix of the system is non-zero. Now, with E_{1}, E_{2}, E_{3} denoting respectively the left-hand side of (7.5), (7.6), and (7.7), and writing r, s, t for r_{n}, s_{n}, respectively t_{n}, the Jacobi matrix J of the system is

J = (\begin{matrix}\frac{∂E_{1}}{∂r} & \frac{∂E_{1}}{∂s} & \frac{∂E_{1}}{∂t} \\ \frac{∂E_{2}}{∂r} & \frac{∂E_{2}}{∂s} & \frac{∂E_{2}}{∂t} \\ \frac{∂E_{3}}{∂r} & \frac{∂E_{3}}{∂s} & \frac{∂E_{3}}{∂t} \end{matrix} ) .

Here,

\frac{∂E_{1}}{∂r} = \frac{s}{r^{2}} − \frac{1}{r} − \frac{n}{r^{2}} + \frac{t}{r^{2}} − ψ^{(1)}(r + 1) − ψ^{(1)}(n − r − s − t + 1),
\frac{∂E_{1}}{∂s} = −\frac{1}{s} − \frac{1}{r} − ψ^{(1)}(n − r − s − t + 1),
\frac{∂E_{1}}{∂t} = −\frac{1}{r} − ψ^{(1)}(n − r − s − t + 1),
\frac{∂E_{2}}{∂r} = −\frac{1}{r} − \frac{1}{s} − ψ^{(1)}(n − r − s − t + 1),
\frac{∂E_{2}}{∂s} = \frac{r}{s^{2}} − \frac{1}{s} − \frac{1}{s^{2}} − \frac{n}{s^{2}} − ψ^{(1)}(s + 1) − ψ^{(1)}(n − r − s − t + 1),
\frac{∂E_{2}}{∂t} = −ψ^{(1)}(n − r − s − t + 1),
\frac{∂E_{3}}{∂r} = −\frac{1}{r} − ψ^{(1)}(n − r − s − t + 1),
\frac{∂E_{3}}{∂s} = −ψ^{(1)}(n − r − s − t + 1),
\frac{∂E_{3}}{∂t} = −ψ^{(1)}(t + 1) − ψ^{(1)}(n − r − s − t + 1).

Using the asymptotic information on r_{n}, s_{n}, t_{n} provided by Lemma 14 and the asymptotic expansion (7.13) for the first polygamma function, it is straightforward to check that det J ∼ 2/ log n as n → ∞. This implies that det J must be non-zero for almost all n. Hence, again by the implicit function theorem, for all n ≥ N (where N is an appropriate real number) the solution (r_{n}, s_{n}, t_{n}) of the system (7.5)–(7.7) exists and is differentiable, and the derivatives r′ = r′_{n}, s′ = s′_{n}, t′ = t′_{n} satisfy

J · (\begin{matrix}r′ \\ s′ \\ t′ \end{matrix}) = (\begin{matrix}−\frac{1}{r} − ψ^{(1)}(n − r − s − t + 1) \\ −\frac{1}{s} − ψ^{(1)}(n − r − s − t + 1) \\ −ψ^{(1)}(n − r − s − t + 1) \end{matrix}) .  (7.16)

Solving this system for r′, s′ and t′, and using again the asymptotic information on r_{n}, s_{n}, t_{n} coming from Lemma 14, as well as the asymptotic expansion (7.13) for ψ^{(1)}(x), one sees that r′ ∼ 1/(2 log n) and s′ ∼ 1/(2 log n) as n → ∞.

It is slightly more delicate to determine the asymptotics of t′, because a cancellation of largest terms occurs in the numerator determinant of the formula

det (\begin{matrix}\frac{∂E_{1}}{∂r} & \frac{∂E_{1}}{∂s} & −\frac{1}{r} − ψ^{(1)}(n − r − s − t + 1) \\ \frac{∂E_{2}}{∂r} & \frac{∂E_{2}}{∂s} & −\frac{1}{s} − ψ^{(1)}(n − r − s − t + 1) \\ \frac{∂E_{3}}{∂r} & \frac{∂E_{3}}{∂s} & −ψ^{(1)}(n − r − s − t + 1) \end{matrix})/ det J  (7.17)

for t′ that results from Cramer’s rule. In this case, in addition to Lemma 14 and (7.13), we use the expansion

ψ^{(1)}(n − r − s − t + 1) = \frac{1}{n − r − s − t + 1} + O (\frac{1}{n^{2}} )

= \frac{1}{n} (1 + \frac{r}{n} + \frac{s}{n} + (\frac{r}{n} + \frac{s}{n})^{2}) + O (\frac{1}{n log^{3} n}) ,

the first line coming from (7.13), the second resulting from expanding the fraction on the right-hand side up to two terms and using the already known fact that t ∼ 2 log n. If this is substituted in the numerator of (7.17), the claimed estimate t′ ∼ 2/n is obtained after a (tedious) routine calculation.

For the proof of (7.15), we consider the first and second component in (7.16). The first component yields the equation

\frac{1}{r} − \frac{nr′}{r^{2}} = \frac{r′}{r} + \frac{s′}{s} + \frac{s′}{r} − \frac{r′s}{r^{2}} + \frac{t′}{r} − \frac{r′t}{r^{2}} + r′ψ^{(1)}(r + 1) − ψ^{(1)}(n − r − s − t + 1)

+ r′ψ^{(1)}(n − r − s − t + 1) + s′ψ^{(1)}(n − r − s − t + 1) + t′ψ^{(1)}(n − r − s − t + 1).

Using the asymptotic information (7.8) and (7.14) that is already available to us, and, in addition, the asymptotic expansion (7.13) for the first polygamma function, we infer that, as n → ∞, we have

\frac{1}{r} − \frac{nr′}{r^{2}} ∼ \frac{2}{n},

which, again in view of (7.8), is equivalent to the first claim in (7.15). The proof of the second claim starts with the second component of (7.16), and is otherwise completely analogous. □

As an immediate consequence of (7.14) and the mean value theorem, we can asymptotically estimate the differences r_{n} − r_{n−1} and s_{n} − s_{n−1}.

Corollary 17. Let (r_{n}, s_{n}, t_{n}) ∈ Ω̃_{n} be such that F (r_{n}, s_{n}, t_{n}) is maximal on Ω̃_{n}. Then

r_{n} − r_{n−1} = \frac{1}{2 log n} + o (\frac{1}{log n})  (7.18)

and

s_{n} − s_{n−1} = \frac{1}{2 log n} + o (\frac{1}{log n}) .  (7.19)

Next, we derive asymptotic estimates for the second derivatives of r_{n}, s_{n}, and t_{n}.

Lemma 18. Let (r_{n}, s_{n}, t_{n}) ∈ Ω̃_{n} be such that F (r_{n}, s_{n}, t_{n}) is maximal on Ω̃_{n}. Then

r′′_{n} ∼ s′′_{n} ∼ −\frac{1}{2n log^{2} n} and t′′_{n} ∼ −\frac{2}{n^{2}} ,  as n → ∞.  (7.20)

Proof. We proceed in a manner analogous to the proof of Lemma 16. Differentiating both sides of (7.16) with respect to n, we obtain

J · (\begin{matrix}r′′ \\ s′′ \\ t′′ \end{matrix}) = (\begin{matrix}\frac{r′}{r^{2}} − (1 − r′ − s′ − t′)ψ^{(2)}(n − r − s − t + 1) \\ \frac{s′}{s^{2}} − (1 − r′ − s′ − t′)ψ^{(2)}(n − r − s − t + 1) \\ −(1 − r′ − s′ − t′)ψ^{(2)}(n − r − s − t + 1) \end{matrix}) − J′ · (\begin{matrix}r′ \\ s′ \\ t′ \end{matrix}) , (7.21)

where J′ is the derivative of J with respect to n. Using the asymptotic information on r_{n}, s_{n}, t_{n} and r′_{n}, s′_{n}, t′_{n} from Lemmas 14 and 16, as well as the asymptotic expansion

ψ^{(2)}(x) = −\frac{1}{x^{2}} + O (\frac{1}{x^{3}} ) ,

one finds that the right-hand side of (7.21) is asymptotically equal to

( \frac{2}{n^{2}} ; \frac{2}{n^{2}} ; \frac{2}{n^{2} log n} ) .

Solving the system (7.21) for r′′, s′′ and t′′, and using the above estimate, the fact that det J ∼ 2/ log n from the proof of Lemma 16, and again the asymptotic information on r_{n}, s_{n}, t_{n} provided by Lemma 14, we obtain the claimed estimates for r′′_{n}, s′′_{n}, and t′′_{n}. □

Lemma 19. Given n ∈ ℕ, consider the function Φ_{n}(k) of a real variable k ranging over 1 ≤ k ≤ n − 1, given by Φ_{n}(k) := g(k) + g(n − k), where

g(k) = \frac{k^{2}}{s_{k}} − \frac{kr_{k}}{s_{k}} + \frac{k}{2s_{k}} + 2r_{k} + 2s_{k} + t_{k} − k log s_{k} + \frac{1}{2} log k − 2 log log k. (7.22)

Then, for sufficiently large n, Φ_{n}(k) has no local maxima in the range (1, n − 1), and it attains its unique local minimum in [1, n − 1] at k = n/2, which is at the same time the global minimum in this range.

Proof. We begin by gathering information on extremal points of the function Φ_{n}(k). Its derivative is Φ′_{n}(k) = g′(k) − g′(n − k), where

g′(k) = \frac{2k}{s_{k}} − \frac{k^{2}s′_{k}}{s_{k}^{2}} − \frac{r_{k}}{s_{k}} − \frac{kr′_{k}}{s_{k}} + \frac{kr_{k}s′_{k}}{s_{k}^{2}} + \frac{1}{2s_{k}} − \frac{ks′_{k}}{2s_{k}^{2}}

+ 2r′_{k} + 2s′_{k} + t′_{k} − log s_{k} − \frac{ks′_{k}}{s_{k}} + \frac{1}{2k} − \frac{2}{k log k} .

Using the asymptotic information on r_{k}, s_{k}, t_{k} and r′_{k}, s′_{k}, t′_{k} provided by Lemmas 14 and 16, respectively, we see that

g′(k) ∼ log k, as k → ∞.

Now let k_{n} be a solution of the equation Φ′_{n}(k) = 0. If k_{n} ≪ n, then g(n − k_{n}) dominates g(k_{n}), hence Φ′_{n}(k_{n}) = g′(k_{n}) − g′(n − k_{n}) cannot be 0 for large n, a contradiction to the definition of k_{n}. On the other hand, if k_{n} ≍ n, then we infer that 0 = g′(k_{n}) − g′(n − k_{n}) ∼ log k_{n} − log(n − k_{n}), whence k_{n} ∼ n/2.

Next, we claim that, for large n, any such solution k_{n} is a local minimum. To see this, we must compute the second derivative of Φ_{n}(k). We have Φ′′_{n}(k) = g′′(k) + g′′(n − k), where

g′′(k) = \frac{2}{s_{k}} − \frac{4ks′_{k}}{s_{k}^{2}} − \frac{k^{2}s′′_{k}}{s_{k}^{2}} + \frac{2k^{2}(s′_{k})^{2}}{s_{k}^{3}} − \frac{2r′_{k}}{s_{k}} + \frac{2r_{k}s′_{k}}{s_{k}^{2}} − \frac{kr′′_{k}}{s_{k}} + \frac{2kr′_{k}s′_{k}}{s_{k}^{2}}

+ \frac{kr_{k}s′′_{k}}{s_{k}^{2}} − \frac{2kr_{k}(s′_{k})^{2}}{s_{k}^{3}} − \frac{s′_{k}}{s_{k}^{2}} − \frac{ks′′_{k}}{2s_{k}^{2}} + \frac{k(s′_{k})^{2}}{s_{k}^{3}} + 2r′′_{k} + 2s′′_{k} + t′′_{k} − 2\frac{s′_{k}}{s_{k}}

− \frac{ks′′_{k}}{s_{k}} + \frac{k(s′_{k})^{2}}{s_{k}^{2}} − \frac{1}{2k^{2}} + \frac{2}{k^{2} log k} + \frac{2}{k^{2}(log k)^{2}} . (7.23)

Using the asymptotic information on r_{k}, s_{k}, t_{k}, r′_{k}, s′_{k}, t′_{k}, and r′′_{k}, s′′_{k}, t′′_{k} provided by Lemmas 14, 16, and 18, respectively, we see that

g′′(k) ∼ \frac{1}{k}, as k → ∞.

In particular, the estimate (7.15) has to be used to approximate the terms

\frac{2}{s_{k}} − \frac{4ks′_{k}}{s_{k}^{2}} + \frac{2k^{2}(s′_{k})^{2}}{s_{k}^{3}} = \frac{2}{s_{k}^{3}} (s_{k} − ks′_{k})^{2}

occurring in (7.23). Thus, if k_{n} ∼ n/2, we have

Φ′′_{n}(k_{n}) = g′′(k_{n}) + g′′(n − k_{n}) ∼ 2/k_{n} ∼ 4/n.

It follows that Φ′′_{n}(k_{n}) > 0 for sufficiently large n, which establishes our claim.

Now we suppose that there were two sequences (k_{n}) and (k̃_{n}) of local minima of Φ_{n}(k), with the property that there is no n_{0} such that the subsequences (k_{n})_{n≥n_{0}} and (k̃_{n})_{n≥n_{0}} are identical. Then there exists a sequence (n_{j})_{j≥0} with k_{n_{j}} ≠ k̃_{n_{j}} for all j. Since both k_{n_{j}} and k̃_{n_{j}} are local minima, there must be a local maximum in between, m_{n_{j}} say. This gives a sequence (m_{n_{j}})_{j≥0} of local maxima of Φ_{n_{j}}(k). Since all these m_{n_{j}} must be solutions of Φ′_{n_{j}}(k) = 0, this contradicts our previous finding that solutions to Φ′_{n}(k) = 0 satisfy Φ′′_{n}(k) > 0 for all sufficiently large n. Therefore, there cannot be two essentially different sequences of local minima.

Trivially, we have Φ′(n/2) = 0. Hence, for large n, the only local minimum of Φ(k) is k = n/2. Since the above argument also shows that there cannot be a local maximum for large n, this local minimum is at the same time the global minimum. □

8. Auxiliary lemmas II: Approximation of the sum ∑ F (r, s, t)

In the previous section we determined the location of the point (r_{n}, s_{n}, t_{n}) where the function F (r, s, t), which we defined in (6.3), and which is equal to the summand of the sum (4.1) that we want to approximate, attains its maximum. Furthermore, we derived asymptotic properties of r_{n}, s_{n}, and t_{n}. In this section we now embark on approximating the sum itself, thereby heavily relying on the information found in the previous section.

We begin by stating (well-known) approximations for sums of exponentials of quadratic expressions in the summation indices. We provide proofs, which take advantage of the Poisson summation formula, for the sake of completeness.

Lemma 20. (i) Let α, β ∈ ℝ with α > 0. Then we have

∑_{n=−∞}^{∞} exp(−αn^{2} − βn) = e^{\frac{β^{2}}{4α}} \sqrt{\frac{π}{α}} (1 + O(α)), as α → 0,

with an implied constant depending only on α.

(ii) Let α, β, γ ∈ ℝ with α > 0 and β^{2} − 4αγ < 0. Then we have

∑_{n=−∞}^{∞} ∑_{m=−∞}^{∞} exp(−αn^{2} − βnm − γm^{2}) = \frac{2π}{\sqrt{4αγ − β^{2}}} (1 + O(α + γ)), as α, γ → 0,

with an implied constant depending only on α and γ.

Proof. We use the Poisson summation formula

∑_{n=−∞}^{∞} f(n + a) = ∑_{μ=−∞}^{∞} exp(2πiμa) ∫_{−∞}^{∞} f(t) exp(−2πiμt) dt,  (8.1)

which holds in particular for continuous f of bounded variation such that f(t) → 0 as t → ∞ and ∫_{−∞}^{∞} |f(t)| dt < ∞; cf. [22, Thm. 45], [5, (3.12.1)], or [18, (5.75)].

(i) Setting f(t) = exp(−αt^{2} − βt) and a = 0 in (8.1), and using the Gauß integral evaluation, we obtain

∑_{n=−∞}^{∞} exp(−αn^{2} − βn) = ∑_{μ=−∞}^{∞} ∫_{−∞}^{∞} exp(−αt^{2} − βt − 2πiμt) dt

= \sqrt{\frac{π}{α}} ∑_{μ=−∞}^{∞} exp (\frac{(β + 2πiμ)^{2}}{4α} )

= \sqrt{\frac{π}{α}} e^{\frac{β^{2}}{4α}} (1 + O(α)),

where the last line results from isolating the term for μ = 0 from the rest of the sum in the next-to-last line.

(ii) This follows by applying part (i) successively to the summations over n and m. □

The next two lemmas are of a technical nature. They are needed in the upcoming estimations.

Lemma 21. For τ > \frac{1}{2} and T > 0 we have

g(T) := T (1 + \frac{1}{2τ} ) − (τ + T + \frac{1}{2}) log (1 + \frac{T}{τ} ) < 0.

Moreover, for any fixed τ, the function g(T) is monotone decreasing in T.

Proof. We compute

g′(T) = \frac{T}{2τ(τ + T)} − log (1 + \frac{T}{τ} )

and

g′′(T) = \frac{1 − 2τ − 2T}{2(τ + T)^{2}} .

Our assumptions on τ and T imply g′′(T) < 0 for all T > 0. This, together with g′(0) = 0, implies g′(T) < 0 for T > 0. Since also g(0) = 0, the latter fact implies g(T) < 0 for all T > 0. □

Lemma 22. Let r = r_{n} + R, s = s_{n} + S, and t = t_{n} + T. Then we have

\frac{F (r + 1, s, t)}{F (r, s, t)} = (1 + \frac{1}{r})^{n−r−s−t} \frac{(n − r − s − t)}{s(r + 1)^{2}}

= exp( − \frac{R}{r_{n}(r_{n} + R)}(n − r_{n} − s_{n} − t_{n}) − \frac{R + S + T}{r_{n} + R}

− 2 log (1 + \frac{R + 1}{r_{n}}) − log (1 + \frac{S}{s_{n}} ) + log (1 − \frac{R + S + T}{n − r_{n} − s_{n} − t_{n}} )

+ O (\frac{n}{(r_{n} + R)^{2}} + \frac{1}{r_{n}} + \frac{1}{n − r_{n} − s_{n} − t_{n} − R − S − T} ) ),  (8.2)

\frac{F (r, s + 1, t)}{F (r, s, t)} = (1 + \frac{1}{s})^{n−r−s+1} \frac{(n − r − s − t)}{r(s + 1)^{2}}

= exp( − \frac{S}{s_{n}(s_{n} + S)}(n − r_{n} − s_{n} + 1) − \frac{R + S}{s_{n} + S}

− log (1 + \frac{R}{r_{n}} ) − 2 log (1 + \frac{S + 1}{s_{n}}) + log (1 − \frac{R + S + T}{n − r_{n} − s_{n} − t_{n}} )

+ O (\frac{n}{(s_{n} + S)^{2}} + \frac{1}{s_{n}} + \frac{1}{n − r_{n} − s_{n} − t_{n} − R − S − T} ) ),  (8.3)

and

\frac{F (r, s, t + 1)}{F (r, s, t)} = \frac{(n − r − s − t)}{r(t + 1)}

= exp(\frac{1}{2t_{n}} − log (1 + \frac{R}{r_{n}} ) − log (1 + \frac{T + 1}{t_{n}})

+ log (1 − \frac{R + S + T}{n − r_{n} − s_{n} − t_{n}} ) + O (\frac{1}{n} + \frac{1}{n − r_{n} − s_{n} − t_{n}} ) ). (8.4)

Proof. All formulae result from a straightforward application of Stirling’s formula, combined with Equations (7.5)–(7.7) and Equation (7.4). □

We shall now estimate the contributions to the sum ∑_{0≤r,s,t≤n} F (r, s, t) which come from triples (r, s, t) that are “far away” from (r_{n}, s_{n}, t_{n}). The precise statement is as follows.

Lemma 23. Given n ∈ ℕ, let

Q_{n} := \{(r, s, t) ∈ ℝ^{3} : |r − r_{n}| ≤ \sqrt{n}, |s − s_{n}| ≤ \sqrt{n}, |t − t_{n}| ≤ \sqrt{log n} log log n\}.

Then we have

∑_{(r,s,t)∈Ω̃_{n}\Q_{n}} F (r, s, t) = \frac{n}{log^{2} n}F (r_{n}, s_{n}, t_{n}) o(1),  as n → ∞.  (8.5)

Proof. In the subsequent computations we set r = r_{n} + R , s = s_{n} + S, and t = t_{n} + T. Using Stirling’s formula and Equations (7.5)–(7.7), together with the estimate (7.4) for the digamma function, we find that as n → ∞

F (r_{n} + R, s_{n} + S, t_{n} + T) = F (r_{n}, s_{n}, t_{n})
× exp( − \frac{R}{r_{n}} (n − r_{n} − s_{n} − t_{n})

+ (n − 2r_{n} − s_{n} − t_{n} − 2R − S − T − \frac{1}{2}) log (1 + \frac{R}{r_{n}} ) − \frac{S}{s_{n}} (n − r_{n} − s_{n} + 1)

+ (n − r_{n} − 2s_{n} − t_{n} − R − 2S + \frac{1}{2}) log (1 + \frac{S}{s_{n}} )

+ \frac{T}{2t_{n}} − \frac{T}{12t_{n}^{2}} − (t_{n} + T + \frac{1}{2}) log (1 + \frac{T}{t_{n}} )

− (n − r_{n} − s_{n} − t_{n} − R − S − T + \frac{1}{2}) log (1 − \frac{R + S + T}{n − r_{n} − s_{n} − t_{n}} )

+ O(\frac{1}{r_{n} + R} + \frac{1}{s_{n} + S} + \frac{1}{t_{n} + T}

+ \frac{1}{n − r_{n} − s_{n} − t_{n} − R − S − T} + \frac{R}{r_{n}} + \frac{S}{s_{n}} + \frac{T}{t_{n}^{3}} )),

as long as r, s, t → ∞ for n → ∞.

We shall use this formula mainly for R ≪ r_{n}, S ≪ s_{n} and T ≪ n, in which case we may write

log (1 + \frac{R}{r_{n}} ) = \frac{R}{r_{n}} − \frac{R^{2}}{2r_{n}^{2}} + O (\frac{R^{3}}{r_{n}^{3}} ) ,

and similarly for log(1 + \frac{S}{s_{n}}) and log(1 − \frac{R+S+T}{n−r_{n}−s_{n}−t_{n}}). Thus we obtain

F (r_{n} + R, s_{n} + S, t_{n} + T) = F (r_{n}, s_{n}, t_{n})
× exp( − \frac{R^{2}}{2r_{n}^{2}} (n − 2r_{n} − s_{n} − t_{n} − 2R − S − T − \frac{1}{2})

− \frac{S^{2}}{2s_{n}^{2}} (n − r_{n} − 2s_{n} − t_{n} − R − 2S + \frac{1}{2}) − \frac{R(2R + S + T + \frac{1}{2})}{r_{n}}

− \frac{S(R + 2S − \frac{1}{2})}{s_{n}} − \frac{(R + S + T)(R + S + T − \frac{1}{2})}{n − r_{n} − s_{n} − t_{n}}

+ T (1 + \frac{1}{2t_{n}} ) − (t_{n} + T + \frac{1}{2}) log (1 + \frac{T}{t_{n}} ) − \frac{T}{12t_{n}^{2}}

+ O(\frac{1}{r_{n} + R} + \frac{1}{s_{n} + S} + \frac{1}{t_{n} + T} + \frac{1}{n − r_{n} − s_{n} − t_{n} − R − S − T}

+ \frac{R}{r_{n}} + \frac{S}{s_{n}} + \frac{T}{t_{n}^{3}} + \frac{nR^{3}}{r_{n}^{3}} + \frac{nS^{3}}{s_{n}^{3}} + \frac{(R + S + T)^{2}}{n} )). (8.6)

In order to establish our claim, we have to cut the region Ω̃_{n}\Q_{n} into several pieces, which we consider separately.

First, let R = \sqrt{n}, |S| ≤ \sqrt{n} and 0 ≤ T ≤ log^{2} n. Then it follows from (8.6) together with Lemmas 14 and 21 that

F (⌊r_{n} + R⌋, ⌊s_{n} + S⌋, ⌊t_{n} + T ⌋) = F (r_{n} + R′, s_{n} + S′, t_{n} + T′)

≤ F (r_{n}, s_{n}, t_{n}) exp (−\frac{n^{2}}{2r_{n}^{2}} + O (\frac{n}{r_{n}} ))

≤ F (r_{n}, s_{n}, t_{n}) exp (−2 (log n)^{2}(1 + o(1))) . (8.7)

Furthermore, for R = \sqrt{n}, |S| ≤ \sqrt{n}, and T > log^{2} n, we have, for large n, that

\frac{F (r, s, t + 1)}{F (r, s, t)} = \frac{n − r − s − t}{r(t + 1)} < 1,  (8.8)

and, thus, by induction on t, it follows that (8.7) holds for all T ≥ 0.

Next we let T < 0, but such that t = t_{n} + T ≫ 1. Still assuming R = \sqrt{n} and |S| ≤ \sqrt{n}, we obtain from (8.6) again the conclusion (8.7).

Finally, if R = \sqrt{n}, |S| ≤ \sqrt{n}, but t ≪ log n (which now also includes very small t), then, by Lemma 14,

\frac{F (r, s, t + 1)}{F (r, s, t)} = \frac{n − r − s − t}{r(t + 1)} > 1

for n large enough. Hence, the inequality (8.7) will be true for all t = t_{n} +T ≤ log log n, say, once it is true for t = t_{n} + T = log log n, which however we already know to be the case.

In summary, up to now we have established (8.7) for R = \sqrt{n}, |S| ≤ \sqrt{n}, and all T. Now, for R ≥ \sqrt{n}, |S| ≤ \sqrt{n}, and all T, by (8.2) and Lemma 14 we have

\frac{F (r + 1, s, t)}{F (r, s, t)} < exp (−\frac{4 log^{2} n}{\sqrt{n}}(1 + o(1))) < 1.

Thus, by induction on r, we see that (8.7) holds for R ≥ \sqrt{n}, |S| ≤ \sqrt{n}, and all T. Since there at most O(n^{3}) such triples (R, S, T), we obtain

∑_{r−r_{n}≥\sqrt{n}} ; |s−s_{n}|≤\sqrt{n} ; 0≤t≤nF (r, s, t) = o(F (r_{n}, s_{n}, t_{n})).  (8.9)

A similar inductive argument using (8.2) and (8.3) shows that

F (r_{n} + R, s_{n} + S, t_{n} + T) ≤ F (r_{n} + \sqrt{n}, s_{n} + \sqrt{n}, t)

for R ≥ \sqrt{n} and S ≥ \sqrt{n}, and hence, because (8.7) holds for R = S = \sqrt{n} and arbitrary T, that (8.7) also holds for R ≥ \sqrt{n}, S ≥ \sqrt{n}, and all T. Again, there are at most O(n^{3}) such triples (R, S, T), and thus

∑_{r−r_{n}≥\sqrt{n}} ; s−s_{n}≥\sqrt{n} ; 0≤t≤nF (r, s, t) = o(F (r_{n}, s_{n}, t_{n})).  (8.10)

A completely analogous argument shows that (8.7) also holds for R = −\sqrt{n}, |S| ≤ \sqrt{n}, and arbitrary T. Now, for R ≤ −\sqrt{n}, |S| ≤ \sqrt{n}, and T ≤ \sqrt{n}, by (8.2) and Lemma 14, we have

\frac{F (r + 1, s, t)}{F (r, s, t)} > exp (\frac{4 log^{2} n}{\sqrt{n}}(1 + o(1))) > 1.

Thus, by a reverse induction on r, we see that (8.7) holds for R ≤ −\sqrt{n}, |S| ≤ \sqrt{n} and T ≤ \sqrt{n}. If, on the other hand, R ≤ −\sqrt{n}, |S| ≤ \sqrt{n}, but T > \sqrt{n}, then in (8.6) the term −T/12t_{n}^{2} is of asymptotic order ≳ \sqrt{n}/ log^{2} n. By repeating previous arguments, it then follows that

F (r_{n} + R, s_{n} + S, t_{n} + T) ≤ F (r_{n}, s_{n}, t_{n}) exp (−\frac{T}{12t_{n}^{2}} (1 + o(1)))
≤ F (r_{n}, s_{n}, t_{n}) exp (−2 log^{2} n(1 + o(1))) .

That is, inequality (8.7) holds for R ≤ −\sqrt{n}, |S| ≤ \sqrt{n}, and all T. Since there are at most O(n^{3}) such triples (R, S, T), we obtain

∑_{r−r_{n}≤−\sqrt{n}} ; |s−s_{n}|≤\sqrt{n} ; 0≤t≤nF (r, s, t) = o(F (r_{n}, s_{n}, t_{n})).  (8.11)

A similar argument using (8.2) and (8.3) shows that

F (r_{n} + R, s_{n} + S, t_{n} + T) ≤ F (r_{n} − \sqrt{n}, s_{n} − \sqrt{n}, t)

for R ≤ −\sqrt{n} and S ≤ −\sqrt{n}, and hence, because (8.7) holds for R = S = −\sqrt{n} and arbitrary T, that (8.7) also holds for R ≤ −\sqrt{n}, S ≤ −\sqrt{n}, and all T. Thus,

∑_{r−r_{n}≤−\sqrt{n}} ; s−s_{n}≤−\sqrt{n} ; 0≤t≤nF (r, s, t) = o(F (r_{n}, s_{n}, t_{n})).  (8.12)

The term F (r, s, t) is almost symmetric in r and s. It is not difficult to convince oneself that minor modifications in the above arguments lead to the conclusion that

∑_{|r−r_{n}|≤\sqrt{n}} ; |s−s_{n}|≥\sqrt{n} ; 0≤t≤nF (r, s, t) +_{∑_{r−r_{n}≤−\sqrt{n}} ; s−s_{n}≥\sqrt{n} ; 0≤t≤n}F (r, s, t) +_{∑_{r−r_{n}≥\sqrt{n}} ; s−s_{n}≤−\sqrt{n} ; 0≤t≤n}F (r, s, t) = o(F (r_{n}, s_{n}, t_{n})). (8.13)

The range which remains to be considered is |R| ≤ \sqrt{n}, |S| ≤ \sqrt{n}, |T | > \sqrt{log n} log log n. From (8.6) we obtain

F (r_{n} + R, s_{n} + S, t_{n} ± \sqrt{log n} log log n)

< F (r_{n}, s_{n}, t_{n}) exp( − \frac{R^{2}}{2r_{n}^{2}} (n − 2r_{n} − s_{n} − t_{n})

− \frac{S^{2}}{2s_{n}^{2}} (n − r_{n} − 2s_{n}) − \frac{R(2R + S)}{r_{n}} − \frac{S(R + 2S)}{s_{n}} − \frac{log n(log log n)^{2}}{t_{n}} + O(1)).

(8.14)

Furthermore, if |R| ≤ \sqrt{n}, |S| ≤ \sqrt{n}, and T ≥ \sqrt{log n} log log n, we have

\frac{F (r, s, t + 1)}{F (r, s, t)} < exp (−\frac{\sqrt{log n} log log n}{t_{n}}(1 + o(1))) ,  (8.15)

and if T ≤ −\sqrt{log n} log log n,

\frac{F (r, s, t + 1)}{F (r, s, t)} > exp (\frac{\sqrt{log n} log log n}{t_{n}}(1 + o(1))) .

Hence, writing q for the right-hand side of (8.15), we see that

F (r, s, t) < F (r, s, t_{n} + \sqrt{log n} log log n) q^{t−t_{n}−\sqrt{log n} log log n}

for t > t_{n} + \sqrt{log n} log log n and

F (r, s, t) < F (r, s, t_{n} − \sqrt{log n} log log n) q^{t_{n}−\sqrt{log n} log log n−t}

for t < t_{n} − \sqrt{log n} log log n. In combination with (8.14) this implies that, for fixed r and s with |R| ≤ \sqrt{n} and |S| ≤ \sqrt{n}, we have

∑_{|t−t_{n}|≥\sqrt{log n} log log n}F (r, s, t)

< F (r_{n}, s_{n}, t_{n}) exp( − \frac{R^{2}}{2r_{n}^{2}} (n − 2r_{n} − s_{n} − t_{n})

− \frac{S^{2}}{2s_{n}^{2}} (n − r_{n} − 2s_{n}) − \frac{R(2R + S)}{r_{n}} − \frac{S(R + 2S)}{s_{n}} + O(1))

× exp (−\frac{log n(log log n)^{2}}{t_{n}} ) \frac{2}{1 − q} .

Using the definition of q to approximate the term 2/(1 − q), we find that the last line in the above expression is

exp (−\frac{(log log n)^{2}}{2} (1 + o(1))) .

Therefore, we obtain

∑_{|r−r_{n}|≤\sqrt{n}} ; |s−s_{n}|≤\sqrt{n} |t−t_{n}|≥\sqrt{log n} log log nF (r, s, t)

< F (r_{n}, s_{n}, t_{n}) ∑_{0≤r,s≤n} exp( − \frac{R^{2}}{2r_{n}^{2}} (n − 2r_{n} − s_{n} − t_{n}) − \frac{S^{2}}{2s_{n}^{2}} (n − r_{n} − 2s_{n})

− \frac{R(2R + S)}{r_{n}} − \frac{S(R + 2S)}{s_{n}})o(1).

Applying Lemma 20.(ii), and using again Lemma 14, we obtain

∑_{|r−r_{n}|≤\sqrt{n}} ; |s−s_{n}|≤\sqrt{n} |t−t_{n}|≥\sqrt{log n} log log nF (r, s, t) < F (r_{n}, s_{n}, t_{n})\frac{2πn}{log^{2} n} o(1).  (8.16)

Finally, if we add up (8.9), (8.10), (8.11), (8.12), (8.13), and (8.16), the claim follows.

□

The benefit of Lemma 23 is that

∑_{0≤r,s,t≤n} F (r, s, t) = ∑_{(r,s,t)∈Q_{n}} F (r, s, t) + F (r_{n}, s_{n}, t_{n})\frac{n}{log^{2} n}o(1).  (8.17)

As we shall see presently, the first term on the right-hand side dominates the second. More precisely, we now prove the following statement.

Theorem 24. We have

c(n) ∼ F (r_{n}, s_{n}, t_{n})\frac{(2π)^{3/2}r_{n}s_{n}\sqrt{t_{n}}}{n} , as n → ∞,

where (r_{n}, s_{n}, t_{n}) is the unique solution of the system of equations (7.5)–(7.7).

Proof. If (r, s, t) ∈ Q_{n}, then we deduce from (8.6) that

F (r, s, t) = F (r_{n}, s_{n}, t_{n}) exp( − \frac{R^{2}}{2r_{n}^{2}} (n + 2r_{n} − s_{n} − t_{n} + O (\frac{r_{n}^{2}}{n} ))

− \frac{S^{2}}{2s_{n}^{2}} (n − r_{n} + 2s_{n} + O (\frac{s_{n}^{2}}{n} )) − RS (\frac{1}{r_{n}} + \frac{1}{s_{n}} + O (\frac{1}{n}))

− \frac{T^{2}}{2t_{n}} (1 + o(1)) + o(1)).

As long as (r, s, t) ∈ Q_{n}, we have for |ε_{r}|, |ε_{s}|, |ε_{t}| < 1 that

F (r+ε_{r}, s + ε_{s}, t + ε_{t})

= F (r_{n}, s_{n}, t_{n}) exp( − \frac{(R + ε_{r})^{2}}{2r_{n}^{2}} (n + 2r_{n} − s_{n} − t_{n} + O (\frac{r_{n}^{2}}{n} ))

− \frac{(S + ε_{s})^{2}}{2s_{n}^{2}} (n − r_{n} + 2s_{n} + O (\frac{s_{n}^{2}}{n} ))

− (R + ε_{r})(S + ε_{s}) (\frac{1}{r_{n}} + \frac{1}{s_{n}} + O (\frac{1}{n})) − \frac{(T + ε_{t})^{2}}{2t_{n}} (1 + o(1)) + o(1))

= F (r_{n}, s_{n}, t_{n}) exp( − \frac{R^{2}}{2r_{n}^{2}} (n + 2r_{n} − s_{n} − t_{n} + O (\frac{r_{n}^{2}}{n} ))

− \frac{S^{2}}{2s_{n}^{2}} (n − r_{n} + 2s_{n} + O (\frac{s_{n}^{2}}{n} )) − RS (\frac{1}{r_{n}} + \frac{1}{s_{n}} + O (\frac{1}{n}))

− \frac{T^{2}}{2t_{n}} (1 + o(1)))(1 + o(1)).

Thus, on the right-hand side of (8.17), instead of summing over (r, s, t) ∈ Q_{n}, we may sum over (R, S, T) ∈ ℤ^{3} with |R| ≤ \sqrt{n}, |S| ≤ \sqrt{n}, |T | ≤ \sqrt{log n} log log n. Therefore, the first term on the right-hand side of (8.17) is equal to

F (r_{n}, s_{n}, t_{n})_{∑_{|R|≤\sqrt{n}} ; |S|≤\sqrt{n} |T |≤\sqrt{log n} log log n} exp( − \frac{R^{2}}{2r_{n}^{2}} (n + 2r_{n} − s_{n} − t_{n} + O (\frac{r_{n}^{2}}{n} ))

− \frac{S^{2}}{2s_{n}^{2}} (n − r_{n} + 2s_{n} + O (\frac{s_{n}^{2}}{n} )) − RS (\frac{1}{r_{n}} + \frac{1}{s_{n}} + O (\frac{1}{n}))

− \frac{T^{2}}{2t_{n}} (1 + o(1)))(1 + o(1)).  (8.18)

Next we argue that we may extend this sum to all (R, S, T) ∈ ℤ^{3} without introducing significant errors. More precisely, we claim that

∑′ exp( − \frac{R^{2}}{2r_{n}^{2}} (n + 2r_{n} − s_{n} − t_{n} + O (\frac{r_{n}^{2}}{n} ))

− \frac{S^{2}}{2s_{n}^{2}} (n − r_{n} + 2s_{n} + O (\frac{s_{n}^{2}}{n} )) − RS (\frac{1}{r_{n}} + \frac{1}{s_{n}} + O (\frac{1}{n}))

− \frac{T^{2}}{2t_{n}} (1 + o(1)))(1 + o(1)) = o (\frac{n}{log^{2} n}) ,  (8.19)

where ∑ ′ is over all (R, S, T) ∈ ℤ^{3} which violate at least one of |R| ≤ \sqrt{n}, |S| ≤ \sqrt{n} and |T | ≤ \sqrt{log n} log log n. This can be proved by using arguments similar to but significantly simpler than those in the proof of Lemma 23. We leave the details to the reader.

Finally, we collect our findings. By the definition of c(n), (8.17), (8.18), and (8.19), we have

c(n) = ∑_{0≤r,s,t≤n} F (r, s, t)

= F (r_{n}, s_{n}, t_{n}) ∑_{−∞<R,S,T <∞} exp( − \frac{R^{2}}{2r_{n}^{2}} (n + 2r_{n} − s_{n} − t_{n} + O (\frac{r_{n}^{2}}{n} ))

− \frac{S^{2}}{2s_{n}^{2}} (n − r_{n} + 2s_{n} + O (\frac{s_{n}^{2}}{n} )) − RS (\frac{1}{r_{n}} + \frac{1}{s_{n}} + O (\frac{1}{n}))

− \frac{T^{2}}{2t_{n}} (1 + o(1)))(1 + o(1))

+ F (r_{n}, s_{n}, t_{n})\frac{n}{log^{2} n}o(1).

Now we apply Lemma 20(i) to the sum over T and Lemma 20(ii) to the sums over R and S. Little simplification then yields that

c(n) = F (r_{n}, s_{n}, t_{n})\frac{(2π)^{3/2}r_{n}s_{n}\sqrt{t_{n}}}{n} (1 + o(1)) + F (r_{n}, s_{n}, t_{n})\frac{n}{log^{2} n}o(1).

By the asymptotic information on r_{n}, s_{n}, t_{n} provided by Lemma 14, we see that the first term on the right-hand side dominates the second, whence the claimed result. □

By the preceding theorem, we have now expressed the asymptotics of c(n) in terms of the solutions r_{n}, s_{n}, t_{n} of the system of equations (7.5)–(7.7) and the value of the function F (r, s, t) at (r, s, t) = (r_{n}, s_{n}, t_{n}). While the asymptotics of r_{n}, s_{n}, t_{n} is already known from Lemma 14, the missing step in the proof of Theorem 8 is to find an explicit expression of the asymptotics of F (r_{n}, s_{n}, t_{n}). This is done in the next proposition.

Proposition 25. We have

F (r_{n}, s_{n}, t_{n}) = exp(n(log n − log s_{n}) + \frac{n}{s_{n}} (n − r_{n} + \frac{1}{2}) − 3n + 2r_{n} + 2s_{n} + t_{n}

− \frac{1}{2} log \frac{(2π)^{3}r_{n}t_{n}}{s_{n}} + 1 + o(1)) as n → ∞.

Proof. We apply Stirling’s formula to the defining expression for F (r_{n}, s_{n}, t_{n}) to obtain

F (r_{n}, s_{n}, t_{n}) = exp( (n + \frac{1}{2}) log n + (n − r_{n} − s_{n} − t_{n}) log r_{n}

+ (n − r_{n} − s_{n} + 1) log s_{n} − (r_{n} + \frac{1}{2}) log r_{n} − (s_{n} + \frac{1}{2}) log s_{n}

− (t_{n} + \frac{1}{2}) log t_{n} − (n − r_{n} − s_{n} − t_{n} + \frac{1}{2}) log(n − r_{n} − s_{n} − t_{n})

− \frac{1}{2} log(2π)^{3} + o(1)).

Now we make use of the Equations (7.5)–(7.7), of Equation (7.4) for the digamma function, and of the expansion log(1 + x) = x + O(x^{2}). This gives

F (r_{n}, s_{n}, t_{n}) = exp (\frac{r_{n}}{2r_{n}} − n + r_{n} + s_{n} + t_{n} + O (\frac{1}{r_{n}} ) + O (\frac{r_{n} + s_{n}}{n − r_{n} − s_{n} − t_{n}} )

+ \frac{s_{n}}{2s_{n}} − n + r_{n} + s_{n} − 1 + O (\frac{1}{s_{n}} ) + \frac{t_{n}}{2t_{n}} + O (\frac{1}{t_{n}} )

+ \frac{n(n − r_{n} − s_{n} + 1)}{s_{n}} − n log s_{n} − \frac{n}{2s_{n}} + \frac{1}{2} + O (\frac{r_{n}}{n} )

+ n log n − \frac{1}{2} log \frac{(2π)^{3}r_{n}t_{n}}{s_{n}} + o(1)).

The result follows now upon appealing to the asymptotic information on r_{n}, s_{n}, t_{n} provided by Lemma 14. □

References

[1] E. A. Bender, An asymptotic expansion for the coefficients of some formal power series, J. London Math. Soc. 9 (1975), 451–458.

[2] F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge University Press, Cambridge, UK, 1997.

[3] N. Chigira, The solutions of x^{d} = 1 in finite groups, J. Algebra 180 (1996), 653–661.

[4] S. Chowla, I. N. Herstein, and W. R. Scott, the solutions of x^{d} = 1 in symmetric groups, Norske Vid. Selsk. 25 (1952), 29–31.

[5] N. G. de Bruijn, Asymptotic Methods in Analysis, Dover Publ., New York, 1981.

[6] A. Dress and T. Müller, Decomposable functors and the exponential principle, Adv. in Math. 129 (1997), 188–221.

[7] A. Erdélyi, V. Magnus, F. Oberhettinger and F. Tricomi, Higher Transcendental Functions, vol. 1, McGraw–Hill, New York, 1953.

[8] I. Goulden and D. Jackson, Combinatorial Enumeration, Wiley, New York, 1983.

[9] B. Harris and L. Schoenfeld, The number of idempotent elements in symmetric semigroups, J. Combin. Theory Ser. A 3 (1967), 122–135.

[10] B. Harris and L. Schoenfeld, Asymptotic expansion for the coefficients of analytic functions, Illinois J. Math. 12 (1968), 264–277.

[11] W. K. Hayman, A generalization of Stirling’s formula, J. reine u. angew. Math. 196 (1956), 67–95.

[12] T. Müller, Combinatorial aspects of finitely generated virtually free groups, J. London Math. Soc. (2) 44 (1991), 75–94.

[13] T. Müller, Subgroup growth of free products, Invent. math. 126 (1996), 111–131.

[14] T. Müller, Finite group actions and asymptotic expansion of e^{P (z)}, Combinatorica 17 (1997), 523–554.

[15] T. Müller, Enumerating representations in finite wreath products, Adv. in Math. 153 (2000), 118–154.

[16] T. Müller, Representations in finite wreath products: enumerative theory and applications, in: Groups–Korea ’98 (Pusan), Y. G. Baik, D. L. Johnson, and Ann Chi Kim, eds., de Gruyter, Berlin, 2000, pp. 243–290.

[17] T. Müller, Five lectures on generalized permutation representations, Mat. Contemp. 20 (2001), 227–272.

[18] A. M. Odlyzko, Asymptotic enumeration methods, in: “Handbook of Combinatorics,” vol. 2, R. L. Graham, M. Grötschel, L. Lovász, eds., Elsevier, Amsterdam, 1995, pp. 1063–1229.

[19] B. Salvy, gdev, a Maple package for series expansions and limits; available at

http://algo.inria.fr/libraries/libraries.html#gdev.

[20] B. Salvy, Examples of automatic asymptotic expansions, SIGSAM Bulletin 25 (1991), 4–17.

[21] R. P. Stanley, Generating functions, in: MAA Stud. Mathematics, vol. 17, G.-C. Rota, ed., Math. Assoc. Am., Washington, 1978.

[22] E. C. Titchmarsh, Introduction to the Theory of Fourier Integrals, Clarendon Press, Oxford, 1937.

[23] E. M. Wright, A relationship between two sequences, Proc. London Math. Soc. 17 (1967), 296–304.

[24] E. M. Wright, Asymptotic relations between enumerative functions in graph theory, Proc. London Math. Soc. 20 (1970), 558–572.

Institut Girard Desargues, Université Claude Bernard Lyon-I, 21, avenue Claude Bernard, F-69622 Villeurbanne Cedex, France. E-mail: kratt@igd.univ-lyon1.fr. WWW:

http://igd.univ-lyon1.fr/~kratt.

School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London E1 4NS, United Kingdom.

E-mail: T.W.Muller@qmul.ac.uk. WWW: http://www.maths.qmw.ac.uk/~twm/.