Welcome to MathOverflow

Question

2

1

I came on this sequence of generating functions on trying to count lambda terms (in lambda calculus)

$T^{\langle m+1\rangle} = \frac{T^{\langle m \rangle}(z)}{z} - (T^{\langle m\rangle}(z))^2$

with

$T^{\langle m\rangle}(0) = 0.$

What can be said about these functions?

I would be happy to have an expression for $T^{\langle 0\rangle}(z)$ and say something about the asymptotic behavior of the coefficients $T_{n,m}$ for

$T^{\langle m\rangle}(z) = \sum_{n=0}^{\infty}\ T_{n,m} z^n.$

flag	asked Oct 20 2011 at 20:08 Pierre Lescanne 51●3

1

This appears to say nothing at all about $T^{0}.$ – Igor Rivin Oct 20 2011 at 20:11

actually it seems to me that if you really want these $T^m(z)$ to be power series with vanishing zero degree coefficient, they have to be identically zero; I post the details as an answer (though I guess it is not the answer you want) in order to clarify what I mean. – Pietro Majer Oct 20 2011 at 21:51

Something is wrong. If tdeg() denotes the tailing degree of a series (the smallest degree with nonzero coefficient), then the recurrent formula implies $$tdeg(T^{\angle m+1 \rangle}(z)) = tdeg(T^{\angle m \rangle}(z)) - 1$$ meaning that at certain point it will drop below 0. That is, for some $m$, $T^{\angle m \rangle}$ will have nonzero coefficients of negative degrees of $z$. – Max Alekseyev Oct 20 2011 at 22:37

unless $tdeg=\infty$, that is, all $T^m$ are identically zero, as said. – Pietro Majer Oct 21 2011 at 7:49

Actually my problem was underdetermined. In my problem, I also want to say that $[z]T^{\langle m\rangle}(z) = T^{\langle m\rangle}'(0) = m.$ In other word, the coefficient of $z$ in the power serie of $T^{\langle m\rangle}(z)$ is $m$. – Pierre Lescanne Oct 28 2011 at 20:49

Pietro Majer · Answer 1 · 2011-10-20 21:48:41Z UTC

We want all the (formal) power series $T^m(z)$ to be elements of the ideal $z\mathbb{R}[[z]]$ (which rephrases $T_{0,m}=0$). Also, the relation $T^m(z)=zT^{m+1}(z)+zT^m(z)^2$ implies that if for some $n$ we have $T^m(z)\in z^n\mathbb{R}[[z]]$ for all $m$, then also $T^m(z)\in z^{n+1}\mathbb{R}[[z]]$ for all $m$. By induction, we should conclude that the $T^m(z)$ are identically zero for all $m$..

A sequence of generating functions

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.