THE NUMBER OF TREES HALF OF WHOSE

VERTICES ARE LEAVES AND ASYMPTOTIC

ENUMERATION OF PLANE REAL ALGEBRAIC CURVES

V.M. Kharlamov, S.Yu. Orevkov

Abstract. The number of topologically different plane real algebraic curves of a given degree d has the form exp(Cd^{2} + o(d^{2})). We determine the best available upper bound for the constant C. This bound follows from Arnold inequalities on the number of empty ovals. To evaluate its rate we show its equivalence with the rate of growth of the number of trees half of whose vertices are leaves and evaluate the latter rate.

Introduction

0.1. Plane projective curves and rooted trees. Recall that a rooted tree is a tree with a distinguished vertex. The distinguished vertex is called the root. The multiplicity or the valence of a vertex is the number of edges which are incident to it. A vertex of multiplicity one is called a leaf. By convention, we assume that the root is a leaf if the tree has no other vertices. Otherwise, the root is not considered as a leaf even if its multiplicity is one. The vertices of multiplicity > 1 are called internal.

In this paper we work exclusively with unlabeled finite trees and use them to encode the topology of nonsingular curves in the real projective plane.

By a nonsingular curve we mean a closed one-dimensional, not necessarily connected, compact sub-manifold. Each connected component of such a curve is a topological circle smoothly embedded in ℝP^{2}. There are two species of embedded circles: one-sided circles, which, similar to a projective line, do not decompose ℝP^{2}, and two-sided circles, which, similar to a standard circle, decompose ℝP^{2} in a disc and a Moebius band. Following the real algebraic geometry tradition, the two-sided components are called ovals even though they may be nonconvex. The number of one-sided components is at most one. By analogy with the algebraic case (see Section 0.2), if all the curve components are ovals, we say that the curve is of even degree, and otherwise, that it is of odd degree.

To encode the topology of a curve we prefer to use the connected components of the complement of the curve. If the degree is even, one of the components of the complement is nonorientable and the other components are orientable as well as their closures. If the degree is odd, all the components of the complement are orientable but the closure of one and only one of them is nonorientable (this is the complement component adjacent to the one-sided component of the curve).

Typeset by AMS-TEX

First author is a member of Research Training Networks EDGE and RAAG, supported by the European Human Potential Program.

Finally, our encoding will look as follows. We associate the vertices with the connected components of the complement of the curve. The root will correspond to the component with non-oriented closure and the tree will represent the adjacency relations between the components (see Figure 1). The fact that this graph is a tree follows from the Jordan curve theorem. It is finite since our curves are compact. The number of edges is equal to the number of ovals, so that the number of vertices is the same as the number of components of the curve if the degree is odd, and it is greater by 1 if the degree is even.

even degree odd degree

Figure 1. Rooted tree and the corresponding plane curves

Two curves have the same encoding and the same degree parity if and only if there is an ambient isotopy transforming one into another, so that these two invariants, the tree and the degree parity, describe completely the isotopy class of a curve. In classical terminology, the isotopy classes are called arrangements. (If one likes, he can speak of ambient homeomorphisms and ambient homeomorphism classes instead of isotopies and isotopy classes; in the case of curves in ℝP^{2} it is an equivalent setting.)

Let us notice that the ovals corresponding to leaves are called empty ovals.

0.2. Statement of results. In this paper we are interested in algebraic nonsingular curves. More precisely, a nonsingular algebraic (real plane) curve of degree d is a curve given, in homogeneous coordinates, by a polynomial equation p(x, y, z) = 0, where p is a real homogeneous polynomial in 3 variables such that its partial derivatives have no common zeros in ℝ^{3} \ 0. It is worth noticing that d is even if and only if all the curve components are two-sided, so that in the case of algebraic curves the degree parity introduced above and the parity of the algebraic degree d coincide.

Even if the curves are algebraic, there is no any restriction on the encoding tree as long as no condition on the curve is imposed. The situation is changing as soon as we fix the degree d of the curve. Then, already the number of connected components, and thus the number of the vertices in the encoding tree, is not arbitrary. As is known, the number of components of the curve is ≤ \frac{(d−1)(d−2)}{2} +1. Introduce, thus, the following notation which provides the sharp upper bound for the number of the vertices:

N_{d} = \{ \begin{matrix}(d − 1)(d − 2)/2 + 1, & if d is odd, \\ (d − 1)(d − 2)/2 + 2, & if d is even. \end{matrix}

TREES HALF OF WHOSE VERTICES ARE LEAVES AND CURVES ENUMERATION 3

Starting from d = 4, not any tree with ≤ N_{d} vertices can be realized by a curve of degree d. Let I_{d} be the number of the trees which can be realized by curves of degree d. No direct formula or functional equation for these numbers is known; moreover, their exact values are available only for d ≤ 7. Very few is known even on the rate of growth of I_{d}.

As is shown in [5],

I_{d} ≍_{e} exp(d^{2}),

where a_{n} ≍_{e} b_{n} means that log a_{n} = O(log b_{n}) and log b_{n} = O(log a_{n}). On the other hand, due to Otter [6] (see also [3; Section 9.5]), one has the following exponential equivalence for the number T_{n} of rooted unlabeled trees with n vertices

T_{n} ∼_{e} C^{n},  C = 2.95576 …,  (1)

where the latter means that log T_{n} ∼ n log C. This implies that

T_{1} + ⋯ + T_{n} ∼_{e} C^{n},

hence,

I_{d} ≤ C^{\frac{d^{2}}{2} +o(d^{2})}.  (2)

The aim of the present note is to correct one erroneous remark from [5] and to show that the so-called Arnold inequalities [1] allow to reduce the constant C in the estimate (2). Namely, we prove that according to these inequalities

I_{d} ≤ C_{1}^{\frac{d^{2}}{2} +o(d^{2})}, C_{1} = 2.9193800 …  (3)

More precisely, (log C_{1})d^{2}/2 is asymptotically equivalent to log A_{d} where A_{d} is the number of unlabeled trees with n ≤ N_{d} vertices not excluded by the Arnold inequalities. According to [5], it implies that the Arnold inequalities exclude more arrangements of ≤ N_{d} closed simple circuits than any other known property of plane algebraic curves, including the consequences of the Bezout theorem.

Let us recall that the principal Arnold inequalities concern the curves of even degree d = 2k exclusively. They state that

even^{∗} ≤ \frac{(k − 1)(k − 2)}{2} + 1, odd^{∗} ≤ \frac{(k − 1)(k − 2)}{2},  (4)

where even^{∗} is the number of internal vertices of odd distance from the root, and odd^{∗} is the number of internal vertices of even non-zero distance from the root. These inequalities imply the following lower bounds on the number l of leaves whatever is the parity of d:

l ≥ n − 1 − [\frac{d − 1}{2}] ([\frac{d − 1}{2}] − 1)  (5)

where n is the total number of vertices. If d is even it is a straightforward consequence of (4) and if d is odd it follows from (5) for d + 1. In particular, for the maximal value n = N_{d} of n, the right hand side is approximately the half of n:

N_{d} − 1 − [\frac{d − 1}{2}] ([\frac{d − 1}{2}] − 1) ∼ \frac{1}{2}N_{d}.  (6)

According to results of this note, it is the trees with n = N_{d} and l ∼ \frac{1}{2}N_{d} which determine the asymptotical impact of Arnold bounds: A_{d} has the same ≍_{e}-rate of growth as the number of the trees with N_{d} vertices half of which are leaves. In particular, the upper bound for I_{2k} deduced from the sole inequality (5) has the same ≍_{e}-rate of growth as the upper bound which can be deduced from (4).

In fact, what is important in the coefficient 1/2 in (6) is that 1/2 > 0.438156 … If the Arnold inequalities were not known but someone proved only that l > 0.43N_{d}, this fact would not reduce the constant C in (2) because the most of trees have about 43.8% leaves (see Appendix for details and references).

The note is organized as follows. The asymptotic growth of the number of the trees half of whose vertices are leaves is established in Section 1 in Theorem 7. The asymptotic impact of the Arnold inequalities is deduced from this theorem in Section 2: Theorem 9 takes into account only the bound (5) and Theorem 13 shows that (4) does not improve the rate. In Appendix we compare the result with the limiting distribution and show that the central limit theorem is not sufficient for our purpose: the range of values we treat is outside the range of a suitably good convergence.

1. On trees half of whose vertices are leaves.

1.1. Functional equation. Let us denote the number of rooted unlabeled trees with n vertices and m leaves by a_{n,m} and consider the associated bi-variant generating function (a formal power series)

T (x, z) = ∑_{n,m} a_{n,m}x^{n}z^{m} = ∑_{n=1}^{∞} a_{n}(z)x^{n}.  (7)

We get (see Figure 2)

T (x, z) = zx + zx^{2} + (z + z^{2})x^{3} + (z + 2z^{2} + z^{3})x^{4} + (z + 4z^{2} + 3z^{3} + z^{4})x^{5}+

(z + 6z^{2} + 8z^{3} + 4z^{4} + z^{5})x^{6} + (z + 9z^{2} + 18z^{3} + 14z^{4} + 5z^{5} + z^{6})x^{7} + … For technical reasons, we introduce also

T̃(x, z) = T (x, z) − zx + x = ∑_{n=1}^{∞} ã_{n}(z)x^{n},  ã_{n}(z) = \{ \begin{matrix}1, & n = 1 \\ a_{n}(z), & n > 1, \end{matrix}

which is the generating function under the convention that the vertex of the onevertex tree is not considered as a leaf.

Using Pólya enumeration theorem as it is done in [8] one can prove that T (x, z) satisfies the (formal) functional equation

T̃(x, z) = T (x, z) − zx + x = x exp (∑_{k=1}^{∞} \frac{T (x^{k}, z^{k})}{k}) .  (8)

The specialization T (x) = T (x, 1) is the classical generating function for the number of rooted unlabeled trees and substituting of z = 1 into (8) turns it into the classical Pólya equation, see [7].

It may be worth noticing that to prove (8), one can use as well the following bi-variant analog of the Cayley product formula for T (x), cf. [4, formula 2.3.4.4-(3)],

T̃(x, z) = \frac{x}{∏(1 − x^{n}z^{m})^{a_{n,m}}} .

Figure 2. Threes with n ≤ 7 vertices

1.2. Recurrent relation. Taking the logarithmic derivatives of the both sides of (8), we get

\frac{T̃_{x}(x, z)}{T̃(x, z)} = \frac{∂}{∂x} (log x + ∑_{k=1}^{∞} \frac{T (x^{k}, z^{k})}{k}) = \frac{1}{x} + ∑_{k=1}^{∞} x^{k−1}T_{x}(x^{k}, z^{k})

Multiplying the both sides by x T̃(x, z) and subtracting T̃(x, z), this gives

xT̃_{x}(x, z) − T̃(x, z) = T̃(x, z) ∑_{k=1}^{∞} x^{k}T_{x}(x^{k}, z^{k}).

Hence,

∑_{n=1}^{∞} nã_{n+1}x^{n+1} = ∑_{p=1}^{∞} ã_{p}x^{p} ∑_{k=1}^{∞} ∑_{j=1}^{∞} ja_{j}(z^{k})x^{jk} = ∑_{n=1}^{∞} x^{n+1} ∑_{p+jk=n+1} ja_{j}(z^{k})ã_{p}(z).

Thus, we obtain the recurrence relation (cf. [6] and [8])

na_{n+1}(z) = nã_{n+1}(z) = ∑_{j=1}^{n} j ∑_{k=1}^{[n/j]} a_{j}(z^{k})ã_{n+1−jk}(z).  (9)

Together with the initial conditions a_{1}(z) = z, ã_{1}(z) = 1, the relation (9) gives a rather fast way to compute a_{n}(z).

1.3. Analytic properties of T (x, z). If before we treated the generating functions as formal series, now we need to study their analytic behavior.

Let α be the radius of convergence of the power series T (x). Using Polya’s approach, see [7], i.e., resolving the equation x exp (1+∑_{k=2}^{∞} \frac{T (x^{k})}{k}) = 1 (for instance, by Newton’s method), one can compute α with any given precision. Indeed, any finite number of coefficients of the involved series can be computed using (9) and the number of terms to be summated, can be found from some rough estimate of α. Performing this computation, one gets

α = 0.33832185689920769519611262571701705318 …

This constant is sometimes called Otter constant because the first seven digits were computed in [6] (using the above approach from [7]).

Let us denote by D the domain of convergence of the series (7). Here, we follow the classical tradition and mean by the domain of convergence the interior of the set where the series is convergent. As is known, it coincides with the interior of the set of points (x, z) ∈ ℂ^{2} such that sup_{n,m} |a_{n,m}x^{n}z^{m}| < ∞. An important, also well known, consequence is that the logarithmic image

log |D| = {(log |x|, log |z|) : (x, z) ∈ D} ⊂ ℝ^{2}

of any convergence domain is convex (in other words, the convergence domains are logarithmically convex).

Lemma 1. There exists a continuous function ζ ↦ r(ζ), ℝ_{>0} = {ζ > 0} → ℝ_{>0}, such that D = {(x, z) : |x| < r(|z|)}. Moreover, α/ζ ≤ r(ζ) ≤ α for ζ ≥ 1 and r(ζ) < min\{1, \frac{1}{|ζ|}\} for any ζ.

The series T (x, z) converges at each point x = r(z), z > 0, of ∂D ∩ ℝ_{>0}^{2}.

Proof. The existence statement and the nonsharp bounds follow from the logarithmic convexity of D combined with the cited above convergency properties of T (x) = T (x, 1) and with the fact that D ⊂ {|xz| ≤ 1}; in its turn, this inclusion follows from a_{n,m} ≥ 1 for any n > m. The strict inequality r(z) < \frac{1}{|z|} is a consequence of the convergence of T (x, z) at the boundary points. To prove this convergence it sufficient to notice that

T (x, z) = xz − x + xe^{T (x,z)+...} > xz − x + xe^{T (x,z)}

for 0 < x < r(z), z > 0; it implies the boundedness of T on the interval x ∈ [0, r(z)[ and, by Abel theorem, its convergence at x = r(z). □

Lemma 2. The transformations (x, z) ↦ (x^{k}, z^{k}), k ≥ 2, map D into itself. For any point (x, z), z ≠ 0, in the closure of D the series

h(x, z) = ∑_{k=2}^{∞} \frac{T (x^{k}, z^{k})}{k}

is absolutely convergent and defines a function holomorphic at such a point.

Proof. The invariance property follows from the logarithmic convexity and the bounds on r(z) given by Lemma 1. In addition, due to this Lemma, for all (x, z) in a small neighborhood of any point in the closure of D we have bounds |x^{k}| ≤ a^{k}, |z^{k}| ≤ b^{k} with a < 1, ab < 1 whatever is k ≥ 1. These bounds provide a bounded convergence of the series:

∑_{k≥2} ∑_{n,m} \frac{|a_{n,m}x^{nk}z^{mk}|}{k} ≤ ∑_{n,m} ∑_{k≥2} \frac{a_{n,m}a^{nk}b^{mk}}{k} ≤ λ ∑_{n,m} a_{n,m}a^{2n}b^{2m} = λT (a^{2}, b^{2}). □

In what follows we study the boundary values a(z) = T (r(z), z), z > 0 of T and use an auxiliary function

F (x, y, z) = z − 1 + e^{y+h(x,z)} − \frac{y}{x}.

By (8), we have F (x, T (x, z), z) = 0 at any point of the closure of D with x ≠ 0, z ≠ 0. In particular, the real curve x = r(z), z > 0, satisfies the equation

F (x, a(z), z) = 0.

Lemma 3. The function r(ζ) is analytic. The function F (x, y, z) is analytic near the real curve x = r(z), z > 0. We have

F_{y}(r(z), a(z), z) = 0,  (10)
a(z) = 1 + r(z)(z − 1).  (11)

Proof. The analyticity of F follows from Lemma 2, and then all the other statements, except the relation (11), follow from the implicit function theorem.

Let us show that a(z) = 1 + r(z)(z − 1). By the definition of F, we have F_{y} = e^{y+h(x,z)} − \frac{1}{x}. Hence, for x = r(z) and y = a(z) we have

0 = F_{y} = e^{y+h(x,z)} − \frac{1}{x}  and  0 = F = z − 1 + e^{y+h(x,z)} − \frac{y}{x}.

Thus, \frac{y}{x} = \frac{1}{x} + z − 1 and y = 1 + x(z − 1). □

Due to Lemma 3, the function x = r(z) can be found by resolving the equation

x exp(1 + (z − 1)x + h(x, z)) = 1

This allows one to compute r(z) with any given precision.

Let us define

\begin{matrix}a_{n}^{+}(z) = ∑_{m>n/2} a_{n,m}z^{m}, a_{n}^{−}(z) = ∑_{m≤n/2} a_{n,m}z^{m}, T_{±}(x, z) = ∑_{n=1}^{∞} a_{n}^{±}(z)x^{n}; \\ T̂(x, z) = T̂(xz^{−1/2}, z), T̂_{±}(x, z) = T̂_{±}(xz^{−1/2}, z), r̂(ζ) = r(ζ)\sqrt{ζ}. \end{matrix}

and denote by D̂ and D̂_{±} the domain of convergence of T̂ and T̂_{±}, respectively. It is clear that D̂ = {(x, z) : |x| < r̂(|z|)}.

Lemma 4. The function r̂(ζ) has a single critical point, this point is a point of maximum.

Proof. The logarithmic map (x, z) ↦ (log |x|, log |z|) transforms xz^{− \frac{1}{2}} in a linear function. Therefore, due to the convexity of log |D|, the critical points of r̂(ζ) form a convex set. If it is not reduced to a single point, then, since r is real analytic, r(ζ) = cζ^{− \frac{1}{2}} , c > 0, which contradicts to the bounds from Lemma 1.

It is a point of maximum, since the domains of convergence are Reinhardt domains, i.e., (x, z) ∈ D as soon as there exists (x_{0}, z_{0}) ∈ D with |x| < |x_{0}|, |z| < |z_{0}|. □

Denote by z_{0} ∈ ℝ_{+} the point where the maximum of r̂(ζ) is attained and put x_{0} = r̂(z_{0}).

Proposition 5. D̂_{±} = {(x, z) : |x| < r̂_{±}(|z|)}, where

r̂_{−}(ζ) = max_{ω≤ζ} r̂(ω) = \{ \begin{matrix}r̂(ζ), & ζ ≤ z_{0}, \\ x_{0}, & ζ ≥ z_{0}, \end{matrix} and r̂_{+}(ζ) = max_{ω≥ζ} r̂(ω) = \{ \begin{matrix}r̂(ζ), & ζ ≥ z_{0}, \\ x_{0}, & ζ ≤ z_{0}. \end{matrix}

Proof. For a point p = (u_{0}, v_{0}) ∈ ℝ^{2}, let us denote ℝ_{+−}^{2}(p) = {(u, v) | u ≤ u_{0}, v ≥ v_{0}} and ℝ_{++}^{2}(p) = {(u, v) | u ≤ u_{0}, v ≤ v_{0}}. The result follows from the following properties:

(a) log |D̂| and log |D̂_{±}| are convex;

(b) If p ∈ log |D̂_{±}| then ℝ_{+±}^{2}(p) ⊂ log |D̂_{±}|;

(c) log |D̂| = log |D̂_{+}| ∩ log |D̂_{−}|. □

1.4. Rate of growth.

Theorem 6.

∑_{m>n/2} a_{n,m} ∼_{e} C_{1}^{n}, where C_{1} = \frac{1}{x_{0}} = 2.919380017448416911265032583985 …

Proof. The coefficients a_{n}^{+}(1) = ∑_{m>n/2} a_{n,m} of the power series T̂_{+}(x, 1) satisfy the following relation

log a_{n+m+2}^{+}(1) ≥ log a_{n}^{+}(1) + log a_{m}^{+}(1) − log 2

(to prove this relation it is sufficient to plant two trees over a new root and to add a leaf growing from the root). Hence, the sequence n^{−1} log a_{n}^{+}(1) has a limit and, by the Cauchy rule,

∑_{m>n/2} a_{n,m} = a_{n}^{+}(1) ∼_{e} r̂_{+}(1)^{−n}.  (12)

To compute r̂_{+}(1), we must find z_{0}. We compute it as the root of the equation r̂′(z) = 0 (the root is unique by the convexity of log D). To find it by Newton’s method, we need r̂′(z) and r̂′′(z). They can be found as follows. Derivating the identity F (r(z), a(z), z) = 0 and using (10), we get

F_{x}(r(z), a(z), z)r′ + F_{z}(r(z), a(z), z) = 0.  (13)

Derivating again, we see that at points (r(z), a(z), z) one has

F_{xx}r′^{2} + F_{xy}r′a′ + 2F_{xz}x′ + F_{yz}a′ + F_{zz} + F_{x}r′′ = 0.  (14)

Note that a′ can be found from (11).

The partial derivatives of F at a point (r(z), a(z), z) are

F_{x} = (h_{x}/r) + (a/r^{2}), F_{y} = 0, F_{z} = 1 + (h_{z}/r),

F_{xx} = (h_{xx}+h_{x}^{2})/r−2(a/r^{3}),  F_{xy} = (h_{x}/r)+(1/r^{2}),  F_{xz} = (h_{xz} +h_{x}h_{z})/r,
F_{yz} = h_{z}/r, F_{zz} = (h_{zz} + h_{z}^{2})/r

Solving the equation r̂′(z) = 0 by Newton’s method, we find

z_{0} = 1.48491739577413809587489 …

and

x_{0} = r̂(z_{0}) = 0.3425384821514313844959919944869 …

Since z_{0} > 1, we have r̂_{+}(1) = r̂(z_{0}) = x_{0}. Now, the desired asymptotic relation follows from (12) and

C_{1} = 1/x_{0} = 2.919380017448416911265032583985 … □

Theorem 7. There is a continuous function λ ↦ C(λ), ℝ_{≥0} → ℝ_{≥0}, such that

∑_{m>λn} a_{n,m} ∼_{e} C(λ)^{n} for any λ ≥ 0.

For each λ > \frac{1}{2} one has C(λ) < C(\frac{1}{2}) = C_{1}.

Proof. Let z_{0,λ} be the critical point of r(ζ)ζ^{λ}. By the same arguments as in the proof of Proposition 5 and Theorem 6,

∑_{m>λn} a_{n,m} ∼_{e} r̂_{+,λ}(1)^{−n},

where r̂_{+,λ}(1) is equal to r(z_{0,λ})z_{0,λ}^{λ} if 1 < z_{0,λ} and to r(1) otherwise. Due to the logarithmic convexity of D,

z_{0,λ} > z_{0} and r(z_{0,λ})z_{0,λ}^{λ} > r(z_{0})z_{0}^{λ} > r(z_{0})z0^{\frac{1}{2}} ,

if λ > \frac{1}{2}. □

2. On the impact of Arnold inequalities.

2.1. Impact of the bound on the number of nonempty ovals. Consider first the case of curves of degree d with (d − 1)(d − 2)/2 + 1 connected components and denote by L_{d} the number of the trees which satisfy the Arnold bound (5). Namely, L_{d} is the number of rooted unlabeled trees with n = N_{d} vertices and ≥ M_{d} leaves where M_{d} = N_{d} − 1 − [\frac{d−1}{2}]([\frac{d−1}{2}] − 1). Recall that N_{d} ∼ \frac{d^{2}}{2} (see also (6)).

Proposition 8.

L_{d} ∼_{e} C1^{\frac{d^{2}}{2}} .

Proof. We apply Theorem 7. Since C(λ) is continuous at λ = \frac{1}{2}, we find for any ϵ > 0 such δ > 0 that for any sufficiently big n it holds

(C_{1} + ϵ)^{(1+ϵ)n} ≥ ∑_{m>( \frac{1}{2} −δ)n} a_{n,m} and ∑_{m>( \frac{1}{2} +δ)n} a_{n,m} ≥ (C_{1} − ϵ)^{(1−ϵ)n}.

It remains to put n = N_{d} ∼ \frac{d^{2}}{2} and to note that for any sufficiently big d

∑_{m>( \frac{1}{2} −δ)n} a_{n,m} ≥ L_{d} ≥ ∑_{m>( \frac{1}{2} +δ)n} a_{n,m}. □

Now, consider the general case and denote, in accordance with the Arnold bound on the number of empty ovals, by L′_{d} the number of rooted unlabeled trees with n ≤ N_{d} vertices and ≥ n − [\frac{d−1}{2}]([\frac{d−1}{2}] − 1) leaves.

Theorem 9.

L′_{d} ∼_{e} C1^{\frac{d^{2}}{2}} .

Proof. In view of (1) and Proposition 8, it is sufficient to prove that L′_{d} ≤ (k̂^{2} − k̂)T_{k̂^{2}−k̂} + k^{2}L_{d} where k̂ = [\frac{d−1}{2}] and k = [\frac{d}{2}]. Clearly, the first term bounds from above the total number of trees with n ≤ k̂^{2} − k̂ vertices. In the range k̂^{2} − k̂ < n ≤ N_{d} the number of the trees excluded by the Arnold bound (5) is increasing, from 0 to L_{d}, when n grows, since a_{n,m} ≤ a_{n+1,m+1} (to prove such an inequality it is sufficient to add a leaf to a branch with a maximal number of leaves). The coefficient k^{2} before L_{d} is due to

N_{d} − 1 − [\frac{d − 1}{2}]([\frac{d − 1}{2}] − 1) = k^{2}. □

2.2. Auxiliary lemmas.

Let v be a vertex of a tree t. A branch of t at v is a connected component of the graph obtained from t by removing v and the (open) edges adjacent to v.

Lemma 10. Let t be a tree with N vertices. Then there exists a vertex v such that any branch of t at v has at most N/2 vertices.

Proof. Suppose that any vertex has a branch with more than N/2 vertices. Choose any vertex v_{1} and define the sequence of vertices v_{1}, v_{2}, … as follows. Assume that v_{i} is already defined. Let t_{i} be the branch of t at v_{i} which has more than N/2 vertices. Then v_{i+1} is defined as the vertex of t_{i} which is nearest to v_{i}. Moving from v_{1} to v_{2}, then from v_{2} to v_{3} and so on, we can never turn back. Indeed, if v_{i+1} coincides with v_{i−1} then removing from t the (open) edge connecting v_{i} with v_{i+1} we would obtain two subtrees of t each having more than N/2 vertices. Since t has no loops, this means that our sequence has no repeatings. Contradiction. □

Lemma 11. Let c_{1} ≥ ⋯ ≥ c_{r} ≥ 0 and |c| ≤ c_{1} + ⋯ + c_{r}. Then there exist ε_{1}, …, ε_{r} ∈ {±1} such that |(ε_{2}c_{2} + ⋯ + ε_{r}c_{r}) − c| ≤ c_{1}.

Proof. Set ε_{k+1} = sign_{+}(c − (ε_{2}c_{2} + ⋯ + ε_{k}c_{k})) where sign_{+}(x) = 1 for x ≥ 0 and sign_{+}(x) = −1 for x < 0. This means that we walk along the real axis starting from the origin so that the absolute values of the steps are successively c_{2}, c_{3}, … and each step is directed towards the point c. Then c′ = ε_{2}c_{2} + ⋯ + ε_{r}c_{r} is the final point of our walk. It is easy to see that |c′ − c| ≤ c_{1}. □

In accordance with the terminology coming from the geometry of plane curves, let us say that a vertex of a rooted tree t is even (resp. odd) if the minimal path relating it to the root consists of an odd (resp. even) number of edges. Let us denote by p(t) (resp. n(t)) the number of even (resp. odd) vertices, including the root, of t and put χ(t) = p(t) − n(t).

For example, the root is an odd vertex, the vertices connected to the root by an edge are even etc. Note, that when we change the root, |χ(t)| does not change.

We say that a rooted tree t′ is obtained from a rooted tree t by contracting an edge if t′ is obtained from t by replacing some edge with a single vertex v (see Figure 3). If one of the ends of the edge which we contracted was the root of t, then v is declared the root of t′. This operation reduces the number of vertices and the edges by one. The operation of inserting an edge at v is to be thought of as an inverse operation. When one of the ends of the inserted edge is a leaf, this is called the attachment of an edge.

Figure 3. Edge contracting

Lemma 12. Let t_{0} be a rooted tree with N vertices and let c be any integer such that |c| ≤ |χ(t_{0})|. Then there exists a sequence of rooted trees t_{1}, …, t_{k} such that

(1) χ(t_{k}) = c;

(2) t_{i−1}, i = 1, …, k, is obtained from t_{i} by contracting an edge;

(3) k ≤ 3 + 3 log_{2} N.

Proof. Apply the induction by N. The case N = 1 is trivial. Assume that the statement is true for any tree which has less than N > 1 vertices. By Lemma 10, there exists a vertex v such that any branch of t_{0} has at most N/2 vertices. Let us denote the branches of t at v by b_{1}, …, b_{r}. We choose the root of each branch at the vertex nearest to v. Let c_{i} = |χ(b_{i})| and δ_{i} = sign χ(b_{i}). Let us number the branches so that c_{1} ≥ c_{2} ≥ ⋯ ≥ c_{r}. By Lemma 11, there exist ε_{2}, …, ε_{r} ∈ {±1} such that |c′ − c| ≤ c_{1} where c′ = ε_{2}c_{2} + ⋯ + ε_{r}c_{r}. By the induction hypothesis, we can insert ≤ 3 + 3 log(N/2) = 3 log N edges to b_{1} so that c_{1}^{∗} = χ(b_{1}^{∗}) = c − c′ for the resulting tree b_{1}^{∗}. Let t_{0}^{∗} be the tree obtained from t_{0} by replacing b_{1} with b_{1}^{∗}.

Let t_{1}^{∗} be obtained from t_{0}^{∗} by inserting an edge e at v so that b_{1}^{∗} and the branches b_{i}, i ≥ 1, with ε_{i}δ_{i} = sign(c − c′) are on one side of e and the branches b_{i} with ε_{i}δ_{i} = − sign(c − c′) are on the other side. Then we have |χ(t_{1}^{∗})| = |c_{1}^{∗} + c′| = |c|. Now, we may return to counting |χ| with respect to the initial root of t_{0} and respective roots of t_{i}, i ≥ 1. If χ(t_{1}^{∗}) = −c, we attach an edge to the root, choose the obtained leaf as the new root and then attach an edge to the new root. □

2.3. Impact of the bounds on the number of even and odd nonempty ovals.

Let us recall that A_{d} denotes the number of rooted unlabeled trees with n ≤ N_{d} vertices which satisfy the Arnold bounds (4).

Theorem 13.

A_{d} ∼_{e} C1^{\frac{d^{2}}{2}} .

Proof. If a tree with n ≤ N_{d} vertices satisfies the weak Arnold bound (5), we apply to it, removing its leaves, Lemma 12 with c = 0, and then put the leaves back, getting thus a tree with n + 3[log_{2} n] + 3 ≤ N_{d} + 3[log_{2} N_{d}] + 3 ≤ N_{d+6} vertices which satisfies the stronger Arnold bounds (4). Therefore,

\frac{L′_{d}}{A_{d+6}} ≤ ∑_{n=1}^{N_{d}} \binom{n + 3[log_{2} n] + 3}{3[log_{2} n] + 3} ≤ N_{d}\binom{N_{d} + 3[log_{2} N_{d}] + 3}{3[log_{2} N_{d}] + 3} = e^{o(N_{d})}

and the theorem follows now from Theorem 9 and A_{d} ≤ L′_{d}. □

Appendix. Limit distribution

Let us consider a_{n,m}/a_{n}(1) as a probability distribution of a random variable X_{n}, i.e. P (X_{n} = m) = a_{n,m}/a_{n}(1). As is known, see f.e. [2], the following central limit theorem holds: this random sequence X_{n}, once normalized, tends to a normal distribution:

P (a < \frac{X_{n} − μn}{σ\sqrt{n}} < b) → \frac{1}{2π} ∫_{a}^{b} e^{− \frac{x^{2}}{2}} dx.

where

μ = −r′(1)/α = 0.4381562356643746639684921638628797837055 …

and

σ^{2} = \frac{r′(1)^{2}}{α^{2}} − \frac{r′(1) + r′′(1)}{α} = 0.150044811672846981980699640444640111071 …

In particular, this means that approximately 43.8% of vertices of a big random tree are leaves. The fact that the mean value of the number of leaves is ∼ μn, μ = 0.438156235664 … was established by Robinson and Schwenk [8] by the Polya-Otter method, and its extension to the other moments was given by Schwenk in [9].

In view of the above limit theorem, it is natural to replace a_{n,m} by its approximation by the normal distribution

a_{n,m}^{∗} = \frac{a_{n}(1)}{σ\sqrt{2π}} exp (−\frac{(m − μn)^{2}}{2σ^{2}n} ) .

Then, we get

∑_{m>n/2} a_{n,m}^{∗} ∼_{e} α^{−n} exp (−\frac{(1/2 − μ)^{2}n}{2σ^{2}}) = C_{2}^{n}

where

C_{2} = α^{−1} exp (−\frac{(1/2 − μ)^{2}}{2σ^{2}} ) = 2.91833301345955740149786987821329181193 …

We see that C_{2} differs from C_{1} in the fourth digit. This is not a contradiction with the central limit theorem because this just means that the convergence to the normal distribution is not good far from the center. It shows that the central limit theorem is not sufficient for a search of the rate of growth of ∑_{m>n/2} a_{n,m}.

To conclude, let us notice that the constants r′(1) and r′′(1) (needed to find μ and σ^{2}) can be computed much faster than the constants z_{0} and x_{0} from Section 2 because the double summation over n, m may be replaced with the single summation by use of the following recurrent formulas for the coefficients of the series T_{z}(x, 1) and T_{zz}(x, 1). Similarly to (9), one can obtain

a′_{n+1}(1) = ∑_{j=1}^{n} a′_{j}(1) ∑_{k=1}^{[n/j]} a_{n+1−kj}(1)

\begin{aligned}a′′_{n+1}(1) = & ∑_{j=1}^{n} \{a′_{j}(1)( ∑_{k=1}^{[(n−1)/j]} a′_{n+1−kj}(1)) \\ & + a′_{j}(1)( ∑_{k=1}^{[n/j]}(k − 1)a_{n+1−kj}(1)) + a′′_{j}(1)( ∑_{k=1}^{[n/k]} ka_{n+1−kj}(1))\} \end{aligned}

References

1. V.I. Arnold, On arrangement of ovals of real plane algebraic curves, the involutions of four-dimensional smooth manifolds, and the arithmetic of integer-valued quadratic forms, Funkcional. Anal. i Priložen 5 (1971), 1–9 (Russian); English transl., Funct. Anal. and Appl. 5 (1971), 169–176.

2. M. Drmota, B. Gittenberger, The distribution of nodes of given degree in random trees, J. of Graph Theory 31 (1999), 227-253.

3. F. Harary, E. Palmer, Graphical enumeration, Academic Press, New York, London, 1973.

4. D. Knuth, The art of computer programming, vol. 1, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont, 1968.

5. S.Yu. Orevkov, V.M. Kharlamov, Asymptotic growth of the number of classes of real plane algebraic curves as the degree grows, Zapiski Nauchn. Semin. POMI 266 (2000), 218–233 (Russian); English transl., J. of Math. Sciences 113 (2003), 666–674.

6. R. Otter, The number of trees, Ann. Math. 49 (1948), 583–599.

7. G.Pólya, Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen, Acta Math. 49 (1937), 145–254.

8. R.W.Robinson, A.J.Schwenk, The distribution of degrees in a large random tree, Discrete Math. 12 (1975), 359–372.

9. A.J. Schwenk, An asymptotic evaluation of the cycle index of a symmetric group, Discrete Math. 18 (1977), 71–78.

First author: Université Louis Pasteur et IRMA (CNRS), 7 rue René Descartes 67084 Strasbourg Cedex, France

  E-mail address: kharlam@math.u-strasbg.fr

Second author: Laboratoire Emile Picard, UFR MIG, Univ. Paul Sabatier, 118 route de Narbonne, 31062 Toulouse, France

  E-mail address: orevkov@picard.ups-tlse.fr