The asymptotic number of $BCK(p)$-terms
A $BCK(p)$-term is a closed lambda-term in which each abstraction binds at most $p$ variables; for $p=1$ these terms are related to the axiom system BCK of combinatory logic. We determine the number of $BCK(p)$-terms of size $n$, up to a constant multiplicative factor, for every $p\ge2$. For $p=2$ the result is fully explicit: \[ f\_n\sim A\,n^{2n/5}2^{n/5}e^{-2n/5}n^{-3/5}e^{P(n^{1/5})}, \] where $P$ is an explicit polynomial of degree $4$. In general the asymptotic formula involves $n^{pn/(2p+1)}$ and an exponential of a polynomial in $n^{1/(2p+1)}$. 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 $p=1$ this comparison fails: the quadratic term then also changes the polynomial factor.
Authors
- Olivier Bodini (ORCID: https://orcid.org/0000-0002-1867-667X)
Institutions
- Laboratoire Analyse, Géométrie et Applications (FR)
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-12
- DOI
- https://doi.org/10.48550/arxiv.2611.16554
- Primary Topic
- Advanced Combinatorial Mathematics
- Type
- preprint