10
$\begingroup$

how to calculate the asymptotic growth rate of coefficients generating function $T(z)$ satisfied this identity

$T(z)=z+\frac{T(z)^3}{6}+\frac{T(z^2)T(z)}{2}+\frac{T(z^3)}{3}$

$\endgroup$
10
$\begingroup$

In order to analyze these type of equations one can use the methodology of Flajolet and Sedgewick (Analytic Combinatorics Book). More precisely, from the previous specification one gets that the first coefficients of $T(z)$ are

$$T(z)=z+z^3+z^5+2z^7+4z^9+8z^{11}+17z^{13}+39z^{15}+89z^{17}+211z^{19}$$

Observe now that if $T(z)$ has a finite singularity at $z=\rho<1$ (it cannot be $>1$ as this comes from a combinatorial problem: the sequence of numbers in the expansion is increasing), then both $T(z^2)$ and $T(z^3)$ are analytic functions at $z=\rho$, and hence we can approximate them by its Taylor expansion (which can be deduced from the previous expansion).

Hence, making this approximation gives an equation of the form $T(z)=F(z,T(z))$, where $F$ has positive Taylor coefficients. Under this circumstances, the singular expansion of $T(z)$ around its singularity will be of square-root type, and the position of the singularity will be at the solution of the system of equations

$$u=F(z,u),\, 1=F_u(z,u),$$

If you compute the solution you get $\rho=0.59597132592884902260$. Then $T(z)$ has a square-root type expansion around this value. You can get then the singular expansion (see Flajolet and Sedgewick), and apply the transference theorem to get that the coefficients grow like $ C n^{-3/2} \rho^{-n}$, with $\rho^{-1}$ roughly $1.6779330757926205637$. To compute the constant $C$ you need the singular expansion + application of the Transference Theorem.

$\endgroup$
  • 1
    $\begingroup$ Since only odd powers appear here, you probably also want to add in a contribution of the form $(-\rho)^{-n}$ etc. $\endgroup$ – Lucia Dec 27 '15 at 17:06
  • $\begingroup$ ah, yes, that's right, one needs to sum both contributions to get the final asymptotic estimate $\endgroup$ – gaussian-matter Dec 27 '15 at 17:08
  • $\begingroup$ Are you sure about the existence of a singularity $\rho<1$ ? From the equation I'd say that $T(z)$ has convergence radius = 1, so that the coefficients are $T_k=o(\theta^k) $ for any $\theta>1$... $\endgroup$ – Pietro Majer Dec 28 '15 at 17:35
  • $\begingroup$ Yes, this GF comes from a tree family. The smallest singularity cannot be $\rho > 1$. If $|\rho|=1$, then necessarily $\rho=1$ and also the 2nd and the 3rd root of unit. But if we assume that $\rho<1$, then necessarily the previous argument I sketched work and this singularity is smaller (after computation) than $\rho$. So this dominates. All details can be found in Flajolet & Sedgewick $\endgroup$ – gaussian-matter Dec 28 '15 at 21:54
3
$\begingroup$

Some remarks about bounding the coefficients of $T(z)$ from above and from below. I assume $T_0=0$ in $T(z)=\sum_{k=0}^\infty T_k z^k$, to which it corresponds a unique formal series solution of the functional equation for $T(z)$, e.g. obtained by iteration of the composition operator on the RHS. Let's first prove that even order coefficients vanish, and odd order coefficients increase.

The Ansatz $T(z):=zS(z^2)$ produces this equation for $S(z):=\sum_{k=0}^\infty S_k z^k$:

$$S(z)=1+\frac{1}{6}zS(z)^3 +\frac{1}{2}zS(z^2)S(z)+ \frac{1}{3}zS(z^3)\ .$$

The latter equation also have a unique formal series solution, which proves that $T$ has indeed the above form $zS(z^2)$, that is, all even order coefficients of $T$ vanish. Since $S$ can be obtained by iteration of the composition operator on the RHS, starting e.g. by $1$, it is clear that $S_k\ge0$ for all $k$, and since $S_0=1$ we also have $[z]^k S(z)^3\ge 3 [z^k]S(z)$ and $ [z^k]S(z^2) S(z)\ge [z^k]S(z)$. Thus $$S(z)\ge 1 + z S(z) \ ,$$
(coefficient-wise), proving that $S$ has increasing coefficients. Having $S(z)$ positive, increasing coefficients also implies, again from the equation, $$6S(z)\le 6 + z S(z)^3 + 3zS(z)^2+2zS(z) \ ,$$ (coefficient-wise). This implies that $S$ is dominated coefficient-wise by the power series solution $y(z)$ of $6y=6+z(y^3+3y^2+y)$. By uniqueness, $y$ is the expansion at $z=0$ of the local inverse of $$h(y)=\frac{6(y-1)}{y(y+1)(y+2)}$$ at $y=1$. This proves that $S$ has a positive radius of convergence $\rho$.

A bound from above for the coefficients of $S$ can be deduced from $$6S(z)\ge 6 + z S(z)^3 + 3zS(z) +2z \ ,$$ (coefficient-wise), which implies that the coefficients of $S(z)$ are larger than the coefficients of the local inverse at $y=1$ of $$g(y)=\frac{6(y-1)}{y^3+3y+2}\ .$$ Putting $y=x+1$, by the Lagrange inversion applied to $h(x+1)$ and $g(x+1)$ one gets, for $k\ge1$

$$\frac{1}{k}[x^{k-1}](1+x+ x^2/2 +x^3/6)^k \le S_k \le \frac{1}{k}[x^{k-1}](1+ 11x/6 +x^2 + x^3/6)^k$$

etc.

$\endgroup$
  • 1
    $\begingroup$ Just because the radius of convergence is $\rho$ does not mean that $S(z)$ goes to infinity as $z\to \rho$. For example, consider $\sum_{n=1}^{\infty} z^n/n^2$. $\endgroup$ – Lucia Dec 29 '15 at 6:56
  • $\begingroup$ I though I could exclude that, but now I see it. thank you ! $\endgroup$ – Pietro Majer Dec 29 '15 at 7:32
  • $\begingroup$ I've purged the wrong argument and left some remarks about bounding $T_k$. $\endgroup$ – Pietro Majer Dec 29 '15 at 7:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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