Delphi.science

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

Source: arxiv.org/abs/2611.16554

Olivier Bodini

arXivarxiv/2611.16554Nov 12, 2026math.COscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.16554
curl -X POST /api/v1/records/arxiv/2611.16554/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.16554/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'