Complexity and subcomplexities, Part 1

Simply put, testosterone is the boss who gives orders to your muscles to grow! As we age, our body’s own production of testos decline accordingly and in prescription viagra the aging population, this hormone is a fountain of youth that might result in glowing, younger and Beautiful Skin and true Beauty From Within, it’s a Weight Loss Product and a Healthy Aphrodisiac. http://djpaulkom.tv/dj-paul-takes-it-to-the-penthouse-check-his-interview-on-penthouse-radio/ generic for levitra You will find a number of different hair loss products available n the marketplace. It cheapest levitra pills is also much faster than the tedious process which is followed for fixing huge damages in case of reactive maintenance. This enables its user to have a decent erection . viagra lowest prices

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 *