betaFeedback

WorksMathematics

The asymptotic number of BCK(p)BCK(p)-terms

Abstract

A BCK(p)BCK(p)-term is a closed lambda-term in which each abstraction binds at most pp variables; for p=1p=1 these terms are related to the axiom system BCK of combinatory logic. We determine the number of BCK(p)BCK(p)-terms of size nn, up to a constant multiplicative factor, for every p≥2p\ge2. For p=2p=2 the result is fully explicit: f_n∼A n2n/52n/5e−2n/5n−3/5eP(n1/5), f\_n\sim A\,n^{2n/5}2^{n/5}e^{-2n/5}n^{-3/5}e^{P(n^{1/5})}, where PP is an explicit polynomial of degree 44. In general the asymptotic formula involves npn/(2p+1)n^{pn/(2p+1)} and an exponential of a polynomial in n1/(2p+1)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=1p=1 this comparison fails: the quadratic term then also changes the polynomial factor.

Paper details

vlnc:W_gt6j9y5s
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…