Analytic Combinatorics/Singularity Analysis

Introduction This article explains how to estimate the coefficients of generating functions involving logarithms and roots. You first may need to familiarise yourself with: Converting between Cartesian and polar coordinates Parameterising a curve Theorems Standard Function Scale Theorem from Flajolet and OdlyzkoFlajolet and Odlyzko 1990, pp. 14.. If: where then: Singularity Analysis Theorem from Flajolet and SedgewickFlajolet and Sedgewick 2009, pp. 393.. If has a singularity at and: where then: The significance of the latter theorem is we only need an approximation of . Branch points 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 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. 300px 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. 400px 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 Proof due to Sedgewick, Flajolet and OdlyzkoSedgewick, pp. 16. Flajolet and Sedgewick 2009, pp. 381. Flajolet and Odlyzko 1990, pp. 4-15. 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. 200px 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 . 200px 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 . 200px 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. 200px We can calculate the integral around by turning it into an integral around . Formally: Lorenz 2011. 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 substitutionFor more details, see Flajolet and Odlyzko 1990, pp. 12-15.: We have: (as ) and: Therefore, Sedgewick, pp. 10. Putting it all together: Singularity Analysis Explanation and example from Flajolet and SedgewickFlajolet and Sedgewick 2009, pp. 392-395.. In the below Summary For the generating function : Find 's singularity . Construct the -domain at . Check that is analytic in the -domain. Create an approximation of near of the form . The estimate of or equivalently . Details As an example, we will use . It has a branch point singularity at . 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. 200px For to be analytic in the -domain: for all in the -domainLang 1999, pp. 68-69.. 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 domainLang 1999, pp. 69.. 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: the coefficients of the first term , which we get from the standard function scale. 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 Proof from Flajolet and OdlyzkoFlajolet and Odlyzko 1990, pp. 7-9., Flajolet and SedgewickFlajolet and Sedgewick 2009, pp. 390-392. and Pemantle and WilsonPemantle and Wilson 2013, pp. 59-60.. 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 . 300px 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: w:Polar_coordinate_system#Converting_between_polar_and_Cartesian_coordinates. (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 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 SedgewickFlajolet and Sedgewick 2009, pp. 398.. Assume is analytic on the disc , has a finite number of singularities on the circle and is analytic on the -domain with multiple indents, one at each singularity. If for each singularity (for ): then: Notes References Flajolet Philippe Odlyzko Andrew Singularity analysis of generating functions 1990 SIAM Journal on Discrete Mathematics 1990 3 http://www.dtc.umn.edu/~odlyzko/doc/arch/singularity.anal.pdf Flajolet Philippe Sedgewick Robert Analytic Combinatorics Cambridge University Press 2009 https://ac.cs.princeton.edu/home/AC.pdf Lang Serge Complex Analysis 4th Springer Science+Business Media, LLC 1999 https://regularize.wordpress.com/2011/11/29/substitution-and-integration-by-parts-for-functions-of-a-complex-variable/ Substitution and integration by parts for functions of a complex variable. Lorenz Dirk 2011 27 November 2022 Pemantle Robin Wilson Mark C. Analytic Combinatorics in Several Variables Cambridge University Press 2013 https://acsvproject.com/ACSV121108submitted.pdf https://ac.cs.princeton.edu/online/slides/AC06-SA.pdf 6. Singularity Analysis. Sedgewick Robert 13 November 2022 Stroud K. A. Advanced Engineering Mathematics 4th Palgrave Macmillan 2003