WorksMathematics
The asymptotic number of -terms
Abstract
A -term is a closed lambda-term in which each abstraction binds at most variables; for these terms are related to the axiom system BCK of combinatory logic. We determine the number of -terms of size , up to a constant multiplicative factor, for every . For the result is fully explicit: where is an explicit polynomial of degree . In general the asymptotic formula involves and an exponential of a polynomial in . The proof combines a linearization of the defining functional equation, the analysis of the Borel transform of the linearized generating function, which satisfies a linear differential equation with an irregular singularity at infinity, the saddle point method for Hayman-admissible functions, and positivity arguments comparing the original and the linearized sequences. For this comparison fails: the quadratic term then also changes the polynomial factor.