# Compaction of Church Numerals
## 1 Introduction  
The goal of this study is to obtain a compact lambda term (\(\lambda\)-term) that leads to the Church numeral of a given natural number. Church numerals are unary representations of natural numbers on \(\lambda\)-terms. Let \(\mathcal{C}(n)\) be the Church numeral for natural number \(n\); then \(\mathcal{C}(n)\) is as follows:  
\[\mathcal{C}(n)=\lambda f.\lambda x\overbrace{f\;(f\;\cdots\;(f\;x)\cdots)}^{n}.\]  
Namely, the length of the Church numeral increases linearly with \(n\). We want a more compact representation for \(n\) in the scheme of \(\lambda\)-terms. We refer to this task as the _compaction of Church numerals_. Using a binary representation for \(n\) is a natural idea, which enables to obtain a \(\lambda\)-term whose size is \(\Theta(\log n)\). Another idea is to decompose \(n\) into an arithmetic expression and to represent it as a corresponding \(\lambda\)-term of the expression. This may reduce the size of the \(\lambda\)-term. For example, \(n=500\) can be decomposed into \(5\times 10\times 10\). The \(\lambda\)-term corresponding to this expression is given as \((\lambda p.\lambda q.\lambda f.\lambda x.p\;(q\;(q\;(f))\;x)\;\mathcal{C}(5)\; \mathcal{C}(10)\), which is much smaller than \(\mathcal{C}(500)\). In this idea, _tetration_ can be used for the decomposition. Tetration is the next hyperoperation after exponentiation; it is defined as iterated exponentiation, e.g., the third tetration of two \({}^{3}2=2^{2^{2}}=16\). Since a function for calculating \({}^{i}k\) on Church numerals is written as a \(\lambda\)-term whose size is \(\mathcal{O}(i+k)\), the size of the \(\lambda\)-term for \(n={}^{i}k\) achieves \(o(\log n)\).  
In this paper, we propose the _Recursive tetrational partitioning_ (RTP) method to decompose a natural number using tetration. We also present an algorithm to generate a compact \(\lambda\)-term by using RTP. Moreover, we prove that the size of the obtained \(\lambda\)-term is \(\mathcal{O}((\text{slog}_{2}n)^{\log n/\log\log n})\), where \(\text{slog}_{2}n\) is super-logarithm, which is the inverse operation of tetration. It is slightly worse than \(\mathcal{O}(\log n)\), but we also prove that the size of the \(\lambda\)-term achieves \(\mathcal{O}(\text{slog}_{2}n)\) in some cases, and our experimental result shows that our method outperforms a binary representation on \(\lambda\)-term on average, when \(n\) is less than approximately 10,000.  
The compaction of Church numerals can be applied to data compression. [PERSON] et al. [1] proposed a compression method called higher-order compression that uses extended \(\lambda\)-terms as the data model. Their method translates an input data to a compact \(\lambda\)-term and then encodes the obtained \(\lambda\)-term. When a pattern consecutively appears \(n\) times in the input, such a part can be represented as a \(\lambda\)-term with \(\mathcal{C}(n)\). Thus efficient compaction of \(\mathcal{C}(n)\) will help for higher-order compression when the data contains many repetitive patterns.  
[PERSON] et al. [2] recently proposed an efficient algorithm for higher-order compression. They utilized a simply typed \(\lambda\)-term for efficient modeling and encoding. Differing from [PERSON] et al.'s method where each context occurring more than once in an input is extracted, [PERSON] et al.'s method extracts the most frequent context up to a certain size. They state in [2] that their method often achieves better performance than a grammar compression [3] with regard to compression ratio. Of course, their method can also be applied to the compaction of \(\mathcal{C}(n)\), while it takes time for repeating context extraction. We confirmed via experiments that our method tends to produce more compact \(\lambda\)-terms for Church numerals than [PERSON] et al.'s method. Note that our method can be easily incorporated into [PERSON] et al.'s method.