From: rusin@math.niu.edu (Dave Rusin)
Subject: Re: generating functions
Date: 14 Jan 2000 19:10:03 GMT
Newsgroups: sci.math.research
Summary: [missing]

In article <Pine.GSO.4.10.10001131516460.25736-100000@cochiti.santafe.edu>,
Cris Moore  <moore@santafe.edu> wrote:
>our generating function H(z) is a fixed point of a nice transcendental
>recurrence,
>
>H(z) = G(z e^(q H(z)-1)) 
>
>where q is a constant and G is a rational function.

If  q  is constant, wouldn't be simpler to deal with  K(z) = q H(z) - 1  ?
We then have the functional equation
   K(z) = L(z e^K(z))
where  L(u) = q G(u) - 1  is another rational function.

At least locally, we may invert  L  and write this as  
   L^(-1) ( K(z) ) = z e^K(z)
   L^(-1) ( K(z) ) / e^K(z) = z
in other words,  M(K(z)) = z  where  M(u) = L^(-1)(u)/e^u. So your  K
is the inverse of this function  M.

We can get a sense of the global behaviour of  K  (and thus  H)   by 
considering its graph; this suggests  H  is not uniquely defined.
Since  G  is rational, the graph of  L  has a fairly tame shape; reflect
across a diagonal to graph the relation  L^(-1). By dividing by  e^u
we get some wiggles which seem overall to flow inward to the right. 
Reflect again to see the graph of  K, and thus of  H,  will include some
wiggles flowing together as we travel up the vertical axis. But there
are many special cases depending on the locations of vertical and
horizontal axes for  G.


>2. by iterating the recurrence k times, we can get the first k terms of
>H's Taylor expansion.  However, we're interested in how the coefficients
>behave for large k.  Is there some way to deduce this from the form of H,
>or from this recurrence?  In general, how do we get the large-k behavior
>of a generating functions' coefficients?

Dunno. Maybe Cauchy integral formula, with successive substitutions and
the occasional integration by parts. (Just from the graph it looks to me
like if  G  doesn't have a pole at  0, the division by  e^u  will have
little impact locally, so that the graphs of  K  and  L  will be similar,
giving the Taylor coefficients of  H  an (exponential) growth rate like 
those of  G, albeit with a different base for the exponent. I tried one
example through the 20th term, at which point the linear growth of
log(|coefficient_k|) was obvious. That means it's true, right? :-)


>I'm doing a nice generating function for a percolation problem on 
>"small world" networks,
 ^^^^^^^^^^^^

Does this phrase have a precise mathematical meaning? I can't shake the
image of little Disney characters dressed up in kilts and kimonos.


dave