# Compaction of Church Numerals
## 3 Proposed Method
### Further Compaction
Then, \(\#M_{\varphi^{*}}\leq\#M_{2}\) holds._  
Proof: By Definition 5, \(\#\Lambda(T_{\varphi^{*}}[n])=\#M_{\varphi^{*}}+\#\mathcal{C}(\varphi^{*})+1\) and \(\#\Lambda(T_{2}[n])=\#M_{2}+\#\mathcal{C}(2)+1\) holds. Therefore, by definition of \(\varphi^{*}\), the following holds:  
\[\#\Lambda(T_{\varphi^{*}}[n])\leq\#\Lambda(T_{2}[n]) \iff\#M_{\varphi^{*}}+\#\mathcal{C}(\varphi^{*})+1\leq\#M_{2}+ \#\mathcal{C}(2)+1\] \[\iff\#M_{\varphi^{*}}-\#M_{2}\leq\#\mathcal{C}(2)-\#\mathcal{C}( \varphi^{*})\] \[\iff\#M_{\varphi^{*}}-\#M_{2}\leq 0.\]  
The statement follows the above. Note that, by Definition 11, \(T_{\varphi}[n]\) is only defined for \(\varphi\geq 2\). Now we can prove Theorem 4. Proof of Theorem 4.: By the definition of \(\mathcal{L}(n)\), we assume that \(\mathcal{L}(n)=M_{\varphi^{*}}\mathcal{L}(\varphi^{*})\), where \(M_{\varphi^{*}}\) is the function term of \(\Lambda(T_{\varphi^{*}}[n])\). By Definition 5, the following holds:  
\[\#\mathcal{L}(n)=\#M_{\varphi^{*}}+\#\mathcal{L}(\varphi^{*})+1. \tag{11}\]  
First, we consider the size of \(M_{\varphi^{*}}\). For a given natural number \(n\), we inductively define a TAE \(\hat{T}_{2}(n)\) as follows:  
\[\hat{T}_{2}(n):=\left\{ \begin{array}{ll}n&\quad(\text{if}\;\;n\leq 2),\\ k_{2}\cdot\hat{T}_{2}(p_{k}-r_{k})+{}^{k}2+\cdots+{}^{1}2\cdot\hat{T}_{2}(p_{1} -r_{1})+{}^{1}2+2&\quad(\text{otherwise}).\end{array} \right.\]  
where \(k\) is the maximum natural number such that \({}^{k}2\leq n\), and for \(1\leq i\leq k\), each \(p_{i}\) is the natural number such that \(0\leq p_{i}\cdot{}^{i}2<{}^{i+1}2\) and \(r_{i}=p_{i}\bmod 2\). If \(p_{i}=0\) or \(1\), we omit the corresponding terms or coefficients in the TAE, similarly to \(T_{2}[n]\). While \(\hat{T}_{2}(n)\) is not \(E_{2}[n]\) (since there is a case that the evaluated result of \(\hat{T}_{2}(n)\) is not equal to \(n\)), \(\hat{T}_{2}(n)\) is clearly a TAE \(E_{\varphi}\). Therefore, by Lemma 1, a CFLT \(\Lambda(\hat{T}_{2}(n))\) exists. By Lemma 2, the upper bound of \(\#\Lambda(\hat{T}_{2}(n))\) depends on the number of the arithmetic operations occurring in \(\hat{T}_{2}(n)\). Let \(N_{a}\) and \(N_{m}\) be the numbers of addition and multiplication occurring in \(T_{2}[n]\), respectively. Also, for tetration \({}^{n_{2}}n_{1}\), we call \(n  
Second, we consider the size of \(\mathcal{L}(\varphi^{*})\). If \(\varphi^{*}\leq 8\), it is constant since \(\mathcal{L}(\varphi^{*})=\mathcal{C}(\varphi^{*})\) and \(\#\mathcal{C}(\varphi^{*})\leq\mathcal{C}(8)=19\). Otherwise, \(\#\mathcal{L}(\varphi^{*})\leq\Lambda(T_{\varphi_{1}^{*}}[\varphi^{*}])\) holds with a natural number \(\varphi_{1}^{*}\). By the definition of \(\mathcal{L}(n)\), it recursively holds until \(\varphi_{1}^{*}\leq 8\). Thus, by (11) and (15),  
\[\#\mathcal{L}(\varphi^{*})=\mathcal{O}((\operatorname{slog}_{2} \varphi^{*})^{\frac{\log\varphi^{*}}{\log\log\varphi^{*}}})+\mathcal{O}(( \operatorname{slog}_{2}\varphi_{1}^{*})^{\frac{\log\varphi_{1}^{*}}{\log\log \varphi_{1}^{*}}})+\cdots+\mathcal{O}((\operatorname{slog}_{2}\varphi_{m}^{*} )^{\frac{\log\varphi_{m}^{*}}{\log\log\varphi_{m}^{*}}})+m+C \tag{16}\]  
holds, where \(C\) is a constant and \(m\) is a natural number such that \(\varphi_{m}^{*}\leq 8\). Here, by Lemma 2, \(\varphi^{*}\leq\lfloor\sqrt{n}\rfloor,\varphi_{1}^{*}\leq\lfloor\sqrt{\varphi^ {*}}\rfloor,\varphi_{2}^{*}\leq\lfloor\sqrt{\varphi_{1}^{*}}\rfloor,\cdots, \varphi_{m}^{*}\leq\lfloor\sqrt{\varphi^{*}}_{m-1}\rfloor\) holds, then the recursion depth \(m\) is \(\mathcal{O}(\log n)\). Hence,  
\[\#\mathcal{L}(\varphi^{*})=\mathcal{O}((\operatorname{slog}_{2} \varphi^{*})^{\frac{\log\varphi^{*}}{\log\log\varphi^{*}}})+\mathcal{O}(\log n )+C \tag{17}\]  
follows (16). Note that \(\sum_{i=1}^{\infty}F(x_{i})<2F(x_{1})\) holds for function \(F(x)\) and natural number \(x\) such that \(F(x_{i})\geq 0\) and \(x_{i+1}\leq\sqrt{x_{i}}\) for \(1\leq i\).