# Complexity and subcomplexities, Part 3

## Logarithm   $\mathit {lt}$   and subcomplexity   $\mathit{C0}$

Let, as always,   $\log$   be the natural logarithmic function. For the given complexity theme we will need the base   $T:=3^\frac 13$   logarithmic function   $\mathit {lt}$,   i.e.

$$\forall_{x\in(0;\infty)}\quad \mathit{lt}(x)\ :=\ \frac {3\cdot \log(x)}{\log(3)}$$

For instance,   $\mathit {lt}(3^t)\ =\ 3\cdot t$. Now we can define a (pretty ambitious) candidate   $\mathit{C0}$   for a subcomplexity in terms of   $\mathit{lt}\,$:

• $\mathit{C0}(1)\ :=\ 1$
• $\forall_{n=2\ 3\ \ldots}\quad \mathit{C0}(n)\ :=\ \lceil\mathit{lt}(n)\rceil$.

The inequalities:

• $T^3 = 3 < 2^3 < 9 = T^6$
• $T^3 = 3$
• $T^9 = 27 < 4^3 < 81 = T^12$
• $T^{12} = 81 < 5^3 < 243 = T^{15}$
• $T^{12} = 81 < 6^3 < 243 = T^{15}$
• $T^{15} = 243 < 7^3 < 729 = T^{18}$
• $T^{15} = 243 < 8^3 < 729 = T^{18}$

(and equality   $\mathit{C0}(1)=1$)   imply

• $\mathit{C0}(1)=1$
• $\mathit{C0}(2)=2$
• $\mathit{C0}(3)=3$
• $\mathit{C0}(4)=4$
• $\mathit{C0}(5)=5$
• $\mathit{C0}(6)=5$
• $\mathit{C0}(7)=6$
• $\mathit{C0}(8)=6$

We see that   $\mathit{C0}$   has the first subcomplexity property   ($\mathit{C0}(1)\le 1$)   by definition. Next,

• $\mathit{C0}(1\ 1\ +)\ =\ 2 =\ \mathit{C0}(1)\ \mathit{C0}(1)\ +$
• $\mathit{C0}(2\ 1\ +)\ = \lceil\mathit{lt}(3)\rceil\ =\ 3\ =\ \mathit{C0}(2)\ \mathit{C0}(1)\ +$
• $\mathit{C0}(2\ 2\ +)\ = \lceil\mathit{lt}(4)\rceil\ =\ 4\ =\ \mathit{C0}(2)\ \mathit{C0}(2)\ +$
• Let   $a\ge 3$   and   $b\in\{1\ 2\}$.   Then

$$\mathit{C0}(a\ b\ +)\ = \lceil\mathit{lt}(a\ b\ +)\rceil\ \ =\ \ \left\lceil\mathit{lt}(a)\ \ \mathit{lt}(1\ \frac ba\ +)\ \ +\right\rceil\ \ \le\ \ \mathit{rn}(a)\ \ \left\lceil\frac b{a\cdot\log(T)}\right\rceil\ +$$
But    $a\cdot\log(T)\ \ge\ \log(3)\ > 1$    hence

$$\mathit{C0}(a\ b\ +)\ \le\ \mathit{C0}(a)\ b\ +\ \ =\ \ \mathit{C0}(a)\ \mathit{C0}(b)\ +$$

• Let   $\min(a\ b)\ge 3$.   Then    $a\ b\ \bullet\ >\ a\ b\ +$    hence    $\mathit{lt}(a\ b\ +)\ \le\ \mathit{lt}(a)\ \mathit{lt}(b)\ +$.

Thus we have shown the second subcomplexity property:
$$\forall_{a\ b\in\mathbb N}\quad \mathit{C0}(a\ b\ +)\ \le\ \mathit{C0}(a)\ \mathit{C0}(b)\ +$$

The third property is easier. Let   $a\ b\in\mathbb N$.   Then:

• if   $\min(a\ b)=1$   then $\mathit{C0}(a\ b\ \bullet)\ <\ \mathit{C0}(a)\ \mathit{C0}(b)\ +$;
• $\mathit{C0}(2\ 2\ \bullet)\ =\ 4\ =\ \mathit{C0}(2)\ \mathit{C0}(2)\ +$;
• if   $a\ge 3$   then

$$\mathit{C0}(a\ 2\ \bullet)\ =\ \lceil\mathit{lt}(a\ 2\ \bullet)\rceil\ =\ \lceil\mathit{lt}(a)\ \mathit{lt}(2)\ +\ \le\ \mathit{C0}(a)\ \lceil\mathit{lt}(2)\rceil\ +\ =\ \mathit{C0}(a)\ 2\ +$$
i.e.
$$\mathit{C0}(a\ 2\ \bullet)\ \le\ \mathit{C0}(a)\ \mathit{C0}(2)\ +$$

• if   $\min(a\ b)\ge 3$   then
$$\mathit{C0}(a\ b\ \bullet)\ =\ \lceil\mathit{lt}(a\ b\ \bullet)\rceil\ =\ \lceil\mathit{lt}(a)\ \mathit{lt}(b)\ +\ \rceil\ \le\ \lceil\mathit{lt}(a)\rceil\ \lceil\mathit{lt}(b)\rceil\ +\ =\ \mathit{C0}(a)\ \mathit{C0}(b)\ +$$
i.e.
$$\mathit{C0}(a\ b\ \bullet)\ \ \le\ \ \mathit{C0}(a)\ \mathit{C0}(b)\ +$$

We have shown that function   $\mathit{C0}$   is a subcomplexity.

## Complexity computations with   $\mathit{C0}$

By definition of   $\mathit{C0},$:

• $\mathit{C0}(1) := 1$
• $\mathit{C0}(2) := 2$
• $\mathit{C0}(3) := \lceil\mathit{lt}(3)\rceil = 3$
• $\mathit{C0}(4) := \lceil\mathit{lt}(4)\rceil = 4$
• $\mathit{C0}(5) := \lceil\mathit{lt}(5)\rceil = 5$
• We had all the above equalities but the last one. Since:
$$T^{12} = 81 < 125 = 5^3 < 243 = T^{15}$$ so that $$12\ \ <\ \ 3\ \mathit{lt}(5)\ \bullet\ \ <\ \ 15$$ i.e. $$4\ \ <\ \ \mathit{lt}(5)\ \ < 5$$ it follows that indeed   $\lceil\mathit{C0}(5)\rceil\ =\ 5$. We already know that: $$\forall_{k\in\mathbb N}\quad \mathit{rn}(k)\ \le\ k$$ Thus $$\forall_{k=1\ldots 5}\quad k\ =\ \mathit{C0}(k)\ \le\ \mathit{rn}(k)\ =\ k$$ Thus, applying nothing but subcomplexity   $\mathit{C0}$   we have obtained an independent demonstration of the proposition: $$\forall_{k=1\ldots 5}\quad \mathit{C0}(k)\ =\ k$$ (earlier the same was shown by subcomplexity   $m_5$). Actually, $$T^{12} = 81 < 216 = 6^3 < 243 = T^{15}$$ $$T^{15} = 243 < 343 = 7^3 < 729 = T^{18}$$ $$T^{15} = 243 < 512 = 8^3 < 729 = T^{18}$$ i.e. $$4 < \mathit{lt}(6) < 5$$ $$5 < \mathit{lt}(7) < 6$$ $$5 < \mathit{lt}(8) < 6$$ or $$\mathit{C0}(6) = 5$$ $$\mathit{C0}(7) = 6$$ $$\mathit{C0}(8) = 6$$ while we already know, due to the representations: $$6 = 1\ 1\ 1 + 1\ 1\ +\ \bullet$$ etc. that $$\mathit{rt}(6)\le 5\qquad\mathit{rt}(7)\le 6\qquad \mathit{rt}(8)\le 6$$ Thus $$\mathit{rn}(6) = 5$$ $$\mathit{rn}(7) = 6$$ $$\mathit{rn}(8) = 6$$. We also know that    $\mathit{rn}(3^n)\ \le\ 3\ n\ \bullet$,    and on the other hand    $\mathit{C0}(3^n)\ =\ 3\ n\ \bullet$.    It follows that THEOREM 0   (in infix notation!–not Łukasiewicz)

• $\mathit{rn}(1)=1\qquad\qquad\mathit{rn}(2)=2$
• $\forall_{n\in\mathbb N}\quad \mathit{rn}(n)\ \ge\ \mathit{lt}(n)$
• $\forall_{n\in\mathbb N}\quad \mathit{rn}(3^n)\ =\ 3\cdot n$
• $\forall_{K\ n\in\mathbb N}\quad \left(\ K > 3^n\quad\Rightarrow\quad \mathit{rn}\left(K\right) \ge 3\cdot n + 1\ \right)$
• $\forall_{n\in\mathbb N}\quad\mathit{rn}(3^n+1)\ =\ 3\cdot n + 1$