8
$\begingroup$

I have the following generating function, $$G(x,y)=\sum_{n,k \geq 0}a(n,k)x^ny^k = \frac{(y^2-y)x+1}{(y-y^3)x^2-(y+1)x+1}$$ and I am interested in obtaining an asymptotic for the sequence $a(n,k)$ i.e. some nice (relatively) closed form $f(n,k)$ s.t. $$\frac{a(n,k)}{f(n,k)} \rightarrow 1$$ as $(n,k) \rightarrow \infty$. From what I've been able to gather the leading person on this type of analysis in Robin Pemantle, so I have been trying to follow one of his survey papers (https://www.math.upenn.edu/~pemantle/papers/twenty.pdf) in order to compute this. All of the theorems presented in this paper, however, seem to make heavy use of algebraic geometry which I am not very familiar with, so I have been struggling to figure out exactly what I need to compute and how. If someone more familiar with the subject could give me a run down of the necessary computations and how they fit in with the theorems given by Pemantle, that'd be great. One small thing I forgot to mention: for my particular sequence, we can assume that we are in what Pemantle calls the combinatorial case i.e. a priori we know $a(n,k) \geq 0$. Thanks.

$\endgroup$

1 Answer 1

2
$\begingroup$

I was able to figure out a partial answer and few people have upvoted this so I will go ahead and give it, and maybe someone will respond with a full answer. The answer I was able to obtain is for the center of the sequence i.e. an asymptotic for $a(n,n)$. I essentially just follow Section 8.2 of Pemantle's paper a link for which is given in the question. So we write $$G(x,y)=\frac{F(x,y)}{H(x,y)}=\frac{(y^2-y)x+1}{(y-y^3)x^2-(y+1)x+1}$$ First we need to verify that the variety $V=\{H(x,y)=0\}$ is smooth. This is simply done by making sure that the equations $H(x,y)=0$, $\nabla H(x,y)=0$ do not have simultaneous solutions. This computation can be done using Gröbner basis, mainly the Mathematica command (Pemantle likes using Maple for whatever reason) $$GroebnerBasis[\{H, D[H, x], D[H, y]\}, \{x, y\}]$$ should yield a basis for the trivial ideal. Now we need to find the set of contributing critical points which Proposition 3.11 tells is given by the solutions to the equations $H(x,y)=0$, $xH_x-yH_y=0$. This again can be computed using Gröbner basis, so the Mathematica command $$GroebnerBasis[\{H, x*D[H, x] - y*D[H, y]\}, \{x, y\}]$$ gives $\{-2 + y + y^3, -1 + 2 x\}$. The roots of the first polynomial are $y=1,\frac{1}{2}(-1+i\sqrt{7}),{2}(-1-i\sqrt{7})$ and the second $x=\frac{1}{2}$, so there is only one positive, real, simultaneous solution and thus the set of contributing critical points is the singleton $\{(\frac{1}{2},1)\}$. Now we simply plug-in to the formula given by Corollary 3.21 to obatin $$a(n,n) \sim \frac{2^n}{\sqrt{\pi n}}$$

$\endgroup$
1
  • $\begingroup$ It seems you have worked out how to do it. Three notes: (1) Robin Pemantle is only one of the authors - guess who the other is. (2) We have a book published in 2013 that may be easier to follow. (3) There is a package incorporated into Sage that does many of these computations automatically. $\endgroup$ Oct 1, 2016 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.