# Complexity and subcomplexities, Part 1

## Introduction

I’ll consider the problem of the complexity   $\mathit{rn}(n)$   of natural numbers   $n\ =\ 1\ 2\ \ldots$,   where the complexity of   $n$   is defined as the minimal number of occurences of   $1$   in arithmetical formulas (strings) which reprezent   $n$,   and which consist only of copies of three characters   $1\ +\ \bullet$   (I decided to use the reversed Łukasiewicz notation, so that no parentheses are needed). I’ll provide a pedantic definition below but first let me present the minimal formulas for the ten smallest natural numbers:

• $1\ =\ 1\qquad \qquad\mathit {rn}(1)=1$
• $2\ =\ 11+\qquad \qquad\mathit {rn}(2)=2$
• $3\ =\ 111++\qquad \qquad\mathit {rn}(3)=3$
• $4\ =\ 1111+++\ =\ 11+11+\bullet\ \qquad\mathit {rn}(4)=4$
• $5\ =\ 11111++++\qquad \qquad\mathit {rn}(5)=5$
• $6\ =\ 111++11+\bullet\qquad \qquad\mathit {rn}(6)=5$
• $7\ =\ 111++11+\bullet1+\qquad \qquad\mathit {rn}(7)=6$
• $8\ =\ 1111+++11+\bullet\qquad \qquad\mathit {rn}(6)=6$
• $9\ =\ 111++111++\bullet\qquad \qquad\mathit {rn}(9)=6$
• $10\ =\ 11111++++11+\bullet\qquad \qquad\mathit {rn}(10)=7$

The above equalities, of the   $\mathit {rn}(n)=r$   type, will be proved later; at this time we can only claim the respective inequalities   $\mathit {rn}(n)\le r$   (of course claim   $\mathit{rn}(n)=n$   for   $n=1\ 2\ 3$   is obvious).

## Ł-strings

Natural numbers will be represented by the so-called Ł-strings (and later I will show HOW natural numbers are represented by Ł-strings–it will be very easy). The Ł-strings are defined as follows:

• $''1''$   is an Ł-string;
• if   $''A''\ \ ''B''$   are Ł-strings then the concatenation   $''AB+''$   is an Ł-string;
• if   $''A''\ \ ''B''$   are Ł-strings then the concatenation   $''AB\bullet''$   is an Ł-string;
• all Ł-strings are obtained by a finite application of the above three rules (i.e. Ł-strings form the smallest set of strings of characters   $1\ +\ \bullet$   which satisfies the three rules above).

Now the value   $\mathit{val}(''X'')$   is defined simply as   $X$,   i.e.

$\mathit{val}(”X”)\ :=\ X$

E.g.

$\mathit{val}(”111++”)\ :=\ 111++\ =\ 3$

If this definition of value is too shockingly simple for you then you may accept the following equivalent inductive form of it, which is comfortingly longer:

• $\mathit{val}(''1'')\ \ :=\ \ 1$
• $\mathit{val}(''AB+'')\ \ :=\ \ \mathit{val}(''A'')\ \mathit{val}(''B'')\ +$
• $\mathit{val}(''AB\bullet'')\ :=\ \mathit{val}(''A'')\ \mathit{val}(''B'')\ \bullet$

## Complexity   $\mathit{rn}$

First we define the complexity   $\mathit{RN}$   of a Ł-strings (as the number of appearances of 1):

• $\mathit{RN}(''1''):=1$
• $\mathit{RN}(''AB+'')\ \ :=\ \ \mathit{RN}(''A'')\ \mathit{RN}(''B'')\ +$
• $\mathit{RN}(''AB\bullet'')\ \ :=\ \ \mathit{RN}(''A'')\ \mathit{RN}(''B'')\ +$

for arbitrary Ł-strings   $''A''\ \ ''B''$   (in the last two formulas above we have mixed operations   $+\ \ \bullet$   on the left, but the same   $+$   twice, i.e.   $+\ \ +$,   on the right).

Finally, the complexity   $\mathit{rn}(n)$   of an arbitrary natural number $n$   is defined as follows:

$\mathit{rn}(n)\ :=\ \min_{\qquad ”X”\ :\ \mathit{val}(”X”)=n}\ \mathit{RN}(”X”)$

## Upper bounds

It’s easy to prove (by induction) that:

$\forall_{n\in \mathbb N}\quad\mathit{rn}(n)\ \ \le\ \ n$

Moreover, now   $\mathit{rn}(a\ n\ +)\ \ \le\ \ \mathit{rn}(a)\ \mathit{rn}(n)\ +\ \ \le\ \ \mathit{rn}(a)\ n\ +$,   i.e.

$\forall_{a\ n\in \mathbb N}\quad\mathit{rn}(a\ n\ +)\ \ \le\ \ \mathit{rn}(a)\ n\ +$

which is a simple generalization of the previous inequality. Easy induction allows us also to show that:

$\forall_{a\ n\in\mathbb N}\quad\mathit{rn}(a^n)\ \ \le\ \ \mathit{rn}(a)\ n\ \bullet$

e.g. fora   $a:=3$   we obtain:

$\forall_{n\in\mathbb N}\quad\mathit{rn}(3^n)\ \ \le\ \ 3\ n\ \bullet$

We will see later that the last inequality actually can be replaced by equality, so that:

1. $\mathit{rn}(3^1)\ \ =\ \ 3$
2. $\mathit{rn}(3^2)\ \ =\ \ 6$
3. $\mathit{rn}(3^3)\ \ =\ \ 9$
4. $\mathit{rn}(3^4)\ \ =\ \ 12$
5. etc.

The selection of   $a:=3$   was especially good, as we will see soon. The goodness of natural number   $a$   in the given context is value:

$\lambda(a) := \frac{\log(a)}{\mathit{rn}(a)}$

or   $\beta(a) := e^{\lambda(a)}$,   i.e. equivalently:

$\beta(a) := a^\frac 1{\mathit{rn}(a)}$

For instance,

$\beta(2) = 8^{\frac 16} < 9^{\frac 16} = \beta(3)$ hence in this sense integer   $3$   is better than integer   $2$.   In general, let   $x := a^n$,   where   $a\ n\in\mathbb N$. Then, by our earlier inequality:

$\mathit{rn}(x)\ \ \le\ \ \mathit{rn}(a)\ \frac{\log(x)}{\log(a)}\ \bullet$

i.e.

$\frac{\mathit{rn}(x)}{\log(x)}\ \ \le\ \ \frac{\mathit{rn}(a)}{\log(a)}\ \ =\ \ \frac 1{\lambda(a)}$

We are interested in as low upper bound as possible. Thus we are especially interested in natural numbers   $a$   for which   $\lambda(a)$   is as large as possible; it is the largest for   $a:=3$   and for the powers of   $3$.   More about it later.