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

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ This appears to say nothing at all about $T^{0}.$ $\endgroup$
    – Igor Rivin
    Oct 20, 2011 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, 2011 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, 2011 at 22:37
  • $\begingroup$ unless $tdeg=\infty$, that is, all $T^m$ are identically zero, as said. $\endgroup$
    – Pietro Majer
    Oct 21, 2011 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, 2011 at 20:49

1 Answer 1

Reset to default
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$..

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Does this make some sort of philosophical statement about lambda calculus? $\endgroup$
    – Igor Rivin
    Oct 21, 2011 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.