Analytic Combinatorics/Meromorphic Functions with Multiple Dominant Singularities

Introduction The theorem for meromorphic functions only applies when there is a single dominant singularity. However, if the generating function has multiple singularities equidistant to the origin, the behaviour of the coefficients will fluctuate. Periodic fluctuations The generating function has radius of convergence , but the coefficients cancel out completely for . It has three singularities of equal modulus: .Flajolet and Sedgewick 2009, pp. 264. The generating function also has radius of convergence , but the coefficients completely cancel out for odd and oscillate between and for even . It has two singularities of equal modulus: .Flajolet and Sedgewick 2009, pp. 264. The periodic behaviour is even more interesting when the two above generating functions are added together:Flajolet and Sedgewick 2009, pp. 264. The coefficients are: Span For a generating function the support of is definedFlajolet and Sedgewick 2009, pp. 266.Mishna 2020, pp. 103. is said to admit a span of if for some Flajolet and Sedgewick 2009, pp. 266. The largest possible span is called the period.Flajolet and Sedgewick 2009, pp. 266. Daffodil lemma Lemma Let be analytic in whose Taylor series expansion around 0 has non-negative coefficients, that it is not a monomial and for some non-zero and non-positive satisfying we have . Then the argument of is a rational multiple of , i.e. , and has span .Flajolet and Sedgewick 2009, pp. 266.Mishna 2020, pp. 104. Example thumb|Polar plot of for . Reproduction of a graph from Flajolet and Sedgewick Analytic Combinatorics pp. 267. Take the generating function with power series expansion In this case, , meaning it has 5 as a span. If we draw a polar plot of , where the angle around the circle is and distance from the origin is and each colour of line represents a different , we see that the tips of the largest petals happen at . Proof thumb|The first five terms of the power series expansion of for as steps in a walk. Notice how if (represented by black and blue arrows) our walk takes us the same distance from the origin. Imaging standing on an empty plane stretching off in all directions to infinity. You are given the power series where each term represents a step you must take, telling you the direction of the step and telling you the length of the stride. Assume that and all are fixed (you cannot modify the length of the stride) but you can modify (the direction of the strides). If your goal is to walk as far away as possible from where you started, i.e. you want to maximise , all your steps need to be in the same direction, i.e. choose a such that all the s are equal for all (mod ). An example of one such walk would be to take the modulus of , i.e. so that which is to say all the steps are forward along the positive real axis. Therefore, any other such that would also need to have all steps in the same direction. Therefore, for all we have or . By assumption is not a monomial, therefore there exists at least two such and so must be a rational multiple of . Moreover, if then we have above that, for all , meaning divides and is thus a span for .Flajolet and Sedgewick 2009, pp. 266-267.Mishna 2020, pp. 104-105. Notes References Flajolet Philippe Sedgewick Robert Analytic Combinatorics Cambridge University Press 2009 https://ac.cs.princeton.edu/home/AC.pdf Mishna Marni Analytic Combinatorics: A Multidimensional Approach Taylor & Francis Group, LLC 2020