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$

    A mathjax latex test


    $ 3^2-2^3 = 1 $

    $$ 3^2-2^3 = 1 $$

    \[ 3^2-2^3 = 1 \]

    After a plug update the slash bracket latex construction stopped working on wordpress. Thus this hopeless test. (I am inserting the mathjax java scripts in a wrong place, I am afraid).

    Hey, it does work! Next worry: will the standard wordpress in-line latex construction produce a bit of junk? Say:   3^2-2^3=1.   How is it? (Do I get word latex displayed as a string of mathematical variables?)

    Wow! This works too! Will I have to add mathjax java scripts everywhere? I don’t mind the nuisance of adding them to the new posts, but to add them to the old ones feels terrible. I can’t have a nice post which will last for a long time. They have to spoil them.