2
$\begingroup$

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.$

|cite|improve this question|||||
$\endgroup$
  • 1
    $\begingroup$ This appears to say nothing at all about $T^{0}.$ $\endgroup$ – Igor Rivin Oct 20 '11 at 20:11
  • $\begingroup$ 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. $\endgroup$ – Pietro Majer Oct 20 '11 at 21:51
  • $\begingroup$ 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$. $\endgroup$ – Max Alekseyev Oct 20 '11 at 22:37
  • $\begingroup$ unless $tdeg=\infty$, that is, all $T^m$ are identically zero, as said. $\endgroup$ – Pietro Majer Oct 21 '11 at 7:49
  • $\begingroup$ 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$. $\endgroup$ – Pierre Lescanne Oct 28 '11 at 20:49
3
$\begingroup$

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$..

|cite|improve this answer|||||
$\endgroup$
  • 1
    $\begingroup$ Does this make some sort of philosophical statement about lambda calculus? $\endgroup$ – Igor Rivin Oct 21 '11 at 7:55

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.