Complexity and subcomplexities, Part 1


Index



 

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.

Leave a Reply

Your email address will not be published. Required fields are marked *