Jump to content

Analytic Combinatorics/Singularity Analysis

From Wikibooks, open books for an open world

Introduction

[edit | edit source]

This article explains how to estimate the coefficients of generating functions involving logarithms and roots.

You first may need to familiarise yourself with:

Theorems

[edit | edit source]

Standard Function Scale

[edit | edit source]

Theorem from Flajolet and Odlyzko[1].

If:

where then:

Singularity Analysis

[edit | edit source]

Theorem from Flajolet and Sedgewick[2].

If has a singularity at and:

where then:

The significance of the latter theorem is we only need an approximation of .

Branch points

[edit | edit source]

Before going into the proof, I will explain what it is about roots and logarithms that mean we have to treat them differently to meromorphic functions.

Polar coordinates

[edit | edit source]

Complex numbers can be expressed in two forms: Cartesian coordinates () or polar coordinates , where is the distance from the origin or modulus and is the angle relative to the positive axis or argument.

For complex functions of complex variables we can draw a 3-dimensional graph where the and axes are the real and imaginary components respectively of the variable and the axis is either the the modulus or the argument of the function .

For roots and logarithms, if we use the argument of the function for the axis, we see a discontinuity that restricts where we can draw the contour when we want to integrate the function.

The gap you can see along the negative axis is the discontinuity.

Root and logarithmic functions do not have poles about which we can do a Laurent expansion. Instead, we need to draw our contours to avoid these gaps or discontinuities. This is why in what follows we use contours with slits or wedges taken out of them.

Proof of standard function scale

[edit | edit source]

Proof due to Sedgewick, Flajolet and Odlyzko[3]

The proof for the estimate of the coefficient of the first term.

By Cauchy's coefficient formula

where is a circle centred at the origin.

It is possible to deform without changing the value of the contour integral above.

We will deform by putting a slit through it along the real axis from 1 to .

We increase the radius of the circle to , which reduces its contribution to the integrand to 0.

Therefore, the contour integration around above is equivalent to the contour integration around the contour which starts at , winds around 1 and ends at , which we will call .

While we don't know much about the behaviour of the integral around the contour , we do know about a similar contour (the Hankel contour) which winds around the origin at a distance of 1.

We can calculate the integral around by turning it into an integral around . Formally:

[4]

Such that .


Informally this means we want to find a function which turns the contour into . Geometrically, we move the contour to the left by 1 and multiply it by :

But, we still want the integrand around to be equivalent to the integrand around . We do this by dividing the variable by and adding 1:

Therefore, we get the following substitution[5]:

We have:

(as )

and:

Therefore,

[6]

Putting it all together:

Singularity Analysis

[edit | edit source]

Explanation and example from Flajolet and Sedgewick[7].

In the below

Little o

[edit | edit source]

We will be making use of the "little o" notation.

as

which means

It also means for each there exists such that[8]

a fact we will use in the proof.

It is also useful to note

Summary

[edit | edit source]

For the generating function :

  1. Find 's singularity .
  2. Construct the -domain at .
  3. Check that is analytic in the -domain.
  4. Create an approximation of near of the form .
  5. The estimate of or equivalently .

Details

[edit | edit source]

To find the singularity, find the value of for which the function equals [9].

As an example, we will use .

It has a singularity at , because

The -domain at 1 is a circle centred at the origin with radius with a triangle cut out of it with one vertex at 1 and edges of angles and . See image below. We use this domain as it allows us to make a proof later.

For to be analytic in the -domain:

for all in the -domain[10].

Our example is analytic in the -domain because

  • is an entire function (i.e. has no singularities), which means it is analytic everywhere.
  • is analytic except for the slit along the real axis for .
  • The product of two analytic functions is an analytic function on the same domain[11]. Therefore, is analytic on the entire complex domain, including the -domain, except for the real axis .

We want an approximation of the form (where in our example we set and ).

Normally, this will be in the form of a Taylor series expansion.

For our example, doing the Taylor Expansion near to 1:

Therefore:

Then .

Therefore, in our example:

The proof of this comes from the fact that:

  1. the coefficients of the first term , which we get from the standard function scale.
  2. and the coefficients of the second term which we do in #Proof of error term. This is also the reason why we need to use the -domain.

Proof of error term

[edit | edit source]

Proof from Flajolet and Odlyzko[12], Flajolet and Sedgewick[13] and Pemantle and Wilson[14].

We get the estimate of the coefficient for the second term from Cauchy's coefficient formula:

where is any closed contour inside the -domain. See the red line in the image below.

We split into four parts such that .

Contribution of :

The maximum of on is when

The maximum of on is

The maximum of on is

Contribution of and :

We parameterise the contour by converting to polar form by , so that is a function of from to . is the positive solution to the equation , so that the contour joins :

But, remember that the little o relation only holds within a particular of . We know that tends to zero as increases, and therefore, for any , we choose an big enough so that . We split the integral above into two at , so that :

The first term in the sum:

[15] (where is the real part of x).

This converges to a constant . Therefore:

The second term in the sum:

grows faster with than , so as . Therefore:

A similar argument applies to .

Contribution of :

By Cauchy's inequality

meaning the contribution of the integral around is exponentially small as and can be discarded.

Formula for multiple singularities

[edit | edit source]

The above assumes only one singularity . But, it can be generalised for functions with multiple singularities.

In the case of multiple singularities, the separate contributions from each of the singularities, as given by the basic singularity analysis process, are to be added up.
Flajolet and Sedgewick 2009, pp. 398.

Theorem from Flajolet and Sedgewick[16].

If is analytic on the disc , has a finite number of singularities on the circle and is analytic on the -domain with multiple indents at each singularity.

If for each singularity (for ):

then:

Notes

[edit | edit source]
  1. Flajolet and Odlyzko 1990, pp. 14.
  2. Flajolet and Sedgewick 2009, pp. 393.
  3. Sedgewick, pp. 16. Flajolet and Sedgewick 2009, pp. 381. Flajolet and Odlyzko 1990, pp. 4-15.
  4. Lorenz 2011.
  5. For more details, see Flajolet and Odlyzko 1990, pp. 12-15.
  6. Sedgewick, pp. 10.
  7. Flajolet and Sedgewick 2009, pp. 392-395.
  8. Flajolet and Odlyzko 1990, pp. 8.
  9. This is a bit of an over-simplification. For further information, see Stroud 2003, pp. 863-867, 915 and w:Mathematical_singularity.
  10. Lang 1999, pp. 68-69.
  11. Lang 1999, pp. 69.
  12. Flajolet and Odlyzko 1990, pp. 7-9.
  13. Flajolet and Sedgewick 2009, pp. 390-392.
  14. Pemantle and Wilson 2013, pp. 59-60.
  15. w:Polar_coordinate_system#Converting_between_polar_and_Cartesian_coordinates.
  16. Flajolet and Sedgewick 2009, pp. 398.

References

[edit | edit source]
  • Flajolet, Philippe; Odlyzko, Andrew (1990). "Singularity analysis of generating functions" (PDF). SIAM Journal on Discrete Mathematics. 1990 (3).
  • Flajolet, Philippe; Sedgewick, Robert (2009). Analytic Combinatorics (PDF). Cambridge University Press.
  • Lang, Serge (1999). Complex Analysis (4th ed.). Springer Science+Business Media, LLC.
  • Lorenz, Dirk (2011). "Substitution and integration by parts for functions of a complex variable". Retrieved 27 November 2022.
  • Pemantle, Robin; Wilson, Mark C. (2013). Analytic Combinatorics in Several Variables (PDF). Cambridge University Press.
  • Sedgewick, Robert. "6. Singularity Analysis" (PDF). Retrieved 13 November 2022.
  • Stroud, K. A. (2003). Advanced Engineering Mathematics (4th ed.). Palgrave Macmillan.