Complexity and subcomplexities, Part 2


Index



 

First three properties of complexity   \mathit{rn}

Every Ł-string features character 1 at least one time. It follows that   \mathit{rn}(n)\ge 1   for every natural number   n=1\ 2\ \ldots. On the other hand, since Ł-string   ''1''   represents   1,   it follows that   \mathit{rn}(1) \le 1,   hence:
\[ \mathit{rn}(1) = 1\]

That’s the first of the three properties. Now let   a\ b\in\mathbb N   be two arbitrary natural numbers; and let Ł-strings   ''A''\ \ ''B''   be such that:

  • \mathit{val}(''A'') = a     and     \mathit{val}(''B'') = b;
  • \mathit{rn}(a) = \mathit{RN}(''A'')     and     \mathit{rn}(b) = \mathit{RN}(''B'')

Then Ł-string   ''AB+''   represents (has value)   a\ b\ +.   It follows that:
\[ \mathit{rn}(a\ b\ +)\ \ \le\ \ \mathit{RN}(”AB+”)\ \ =\ \ \mathit{RN}(”A”)\ \mathit{RN}(”B”)\ + \]

\[ =\ \ \mathit{rn}(a)\ \mathit{rn}(b)\ + \]

We see that

\[ \forall_{a\ b\ \in\ \mathbb N}\quad \mathit{rn}(a\ b\ +)\quad\le\quad \mathit{rn}(a)\ \mathit{rn}(b)\ + \]

and this is the second property of complexity   \mathit{rn}.   A very similar proof justifies also the third property:

\[ \forall_{a\ b\ \in\ \mathbb N}\quad \mathit{rn}(a\ b\ \bullet)\quad\le\quad \mathit{rn}(a)\ \mathit{rn}(b)\ + \]



 

Subcomplexities

DEFINITION 0   A real positive function   \gamma : \mathbb N \rightarrow (0;\infty)   is called a subcomplexity   \Leftarrow:\Rightarrow   \gamma   satisfies the following three properties:

  1. \gamma(1)\le 1
  2. \forall_{a\ b\ \in\ \mathbb N}\quad \gamma(a\ b\ +)\ \le\ \gamma(a)\ \gamma(b)\ +
  3. \forall_{a\ b\ \in\ \mathbb N}\quad \gamma(a\ b\ \bullet)\ \le\ \gamma(a)\ \gamma(b)\ +

We can see from the First three properties that the complexity function   \mathit{rn}   is a subcomplexity. Furthermore, a simple induction on natural numbers shows that   \mathit{rn}   is the greatest subcomplexity, meaning that for every subcomplexity   \gamma   the following inequality holds:

\[ \forall_{n\in\mathbb N}\ \ \gamma(n)\le\mathit{rn}(n) \]



 

Ceiling of a subcomplexity

We will see that the ceiling of a subcompolexity is a subcomplexity.

Let   t\in\mathbb R   be an arbitrary real number. Then the floor   \lfloor t\rfloor   and the ceiling   \lceil t\rceil   are defined as the integers which satisfy inequalities:
\[ t-1\ <\ \lfloor t\rfloor\ \le t \] \[ t\ \le\ \lceil t\rceil\ <\ t+1 \] Such integers are unique for every real   t.   They have the following properties for every real   t   and integer   n:

  • t\ge n\qquad\Rightarrow\qquad \lfloor t\rfloor \ge n
  • t \le n\qquad\Rightarrow\qquad \lceil t\rceil \le n

We will apply the latter property. Let   \gamma   be an arbitrary subcomplexity. Let   \delta :\mathbb N\rightarrow (0;\infty)   be given by:

\[ \forall_{n\in\mathbb N}\quad \delta(n) := \lceil \gamma(n)\rceil \]

(one could write   \delta := \lceil\gamma\rceil).   Then   0 < \gamma(1)\le 1   hence   \delta(1) = 1.   Thus   \delta   has the first property of subcomplexities.

Now let   a\ b\in\mathbb N   be two arbitrary natural numbers. Then

\[\gamma(a\ b\ +)\ \ \le\ \ \gamma(a) \gamma(b)\ +\ \ \le\ \ \delta(a)\ \delta(b)\ + \]

The \delta-expression on the right is an integer. Thus, by the definition of   \delta,   and by the general property of the operation ceiling (see above), we get:

\[ \delta(a\ b\ +)\ \ \le\ \ \delta(a)\ \delta(b)\ + \]

Thus   \delta   has the second property of a su8bcomplexity. A proof of the third property:

\[ \delta(a\ b\ \bullet)\ \ \le\ \ \delta(a)\ \delta(b)\ + \]

is very similar.



 

Maximum of two subcomplexities. A truncated subcomplexity.

Let   \alpha\ \beta : \mathbb N\rightarrow (0;\infty)   be two arbitrary subcomplexities. Define their maximum   \gamma : \mathbb N\rightarrow (0;\infty)   in the usual way:
\[ \forall_{n\in\mathbb N}\quad \gamma(n)\ \ :=\ \ \max(\alpha(n)\ \ \beta(n)) \]

Then, as it is easy to prove,   \gamma   is a subcomplexity too.


Let   \gamma:\mathbb N\rightarrow (0;\infty)   be an arbitrary subcomplexity. Let   M\in (0;\infty)   be an arbitrary positive real number. Define the truncated function   \gamma_M   as follows:

\[ \forall_{n\in\mathbb N}\quad \gamma_M(n)\ \ :=\ \ \min(\gamma(n)\ \ M) \]

It is easy to prove that the truncated function   \gamma_M   is a subcomplexity–call it the truncated subcomplexity.


POTENTIAL APPLICATION   Let   \gamma   be a subcomplexity, and let   M\in\mathbb N   be such that   \gamma(k) = \mathit{rn}(k)   for every   k=1\ldots M.   Then define   \delta:\mathbb N\rightarrow (0;\infty)   as follows:

  • \forall_{k\in\mathbb N\setminus\{M\}}\quad \delta(k)\ :=\ \gamma(k)
  • \delta(M)\ :=\ \mathit{zn}(M)

Then   \delta   is a subcomplexity too–call it an improved subcomplexity.



 

Subcomplexity   m_5

Let’s define function   m_5:\mathbb N\rightarrow (0;\infty)   as follows:

\[ \forall_{k\in\mathbb N}\quad m_5(k)\ \ :=\ \ \min(k\ \ 5) \]

First of all   m_5(1)=1   which means that function   m_5   has the first subcomplexity property.

Now let   a\ b\in\mathbb N   be two arbitrary natural numbers. Then

  • \max(a\ b)\le 5\qquad\Rightarrow\qquad m_5(a\ b\ +)\ \ \le\ \ a\ b\ +\ \ =\ \ m_5(a)\ m_5(b)\ +
  • \max(a\ b)\ge 5\qquad\Rightarrow\qquad m_5(a\ b\ +)\ \ \le\ \ 5\ \ \le\ \ m_5(a)\ m_5(b)\ +

which show that   m_5   has the second property of a subcomplexity:

\[ \forall_{a\ b\in \mathbb N}\quad m_5(a\ b\ +)\ \ \le\ \ m_5(a)\ m_5(b)\ + \]

Furthermore, if   \min(a\ b) = 1   then   a\ b\ \bullet\ =\ \max(a\ b)   and   \{1\ \max(a\ b)\}\ =\ \{a\ b\} ,   hence

\[ \min(a\ b) = 1\quad\Rightarrow\quad m_5(a\ b\ \bullet)\ =\ \ m_5(\max(a\ b)) \]
\[ <\ \ \ 1\ \ m_5(\max(a\ b))\ \ +\ \ \ =\ \ \ m_5(a)\ m_5(b)\ + \] -- i.e. the third subcomplexity property holds when   \min(a\ b) = 1.   Next, if     \min(a\ b) = \max(a\ b) = 2   (so that   a=b=2)   then
\[ m_5(a\ b\ \bullet)\ =\ 4\ \ =\ \ m_5(a)\ m_5(b)\ + \]

Finally, let the remaining possibility hold:   \min(a\ b)\ \ge 2   and   \max(a\ b) \ge 3.   Then   m_5(\min(a\ b))\ \ge\ 2   and   m_5(\max(a\ b))\ \ge\ 3   hence

\[ m_5(a\ b\ \bullet)\ \ \ \le\ \ \ 5\ \ \ \le\ \ \ m_5(\min(a\ b))\ \ m_5(\max(a\ b))\ \ + \]

\[ =\ \ \ m_5(a)\ m_5(b)\ + \]

We see that the third subcomplexity property holds in every case, i.e.

\[ \forall_{a\ b\in \mathbb N}\quad m_5(a\ b\ \bullet)\ \ \le\ \ m_5(a)\ m_5(b)\ + \]

We have proven that function   m_5   is a subcomplexity.

THEOREM 0   \mathit{rn}(k)=k   for every   k=1\ldots 5.

PROOF   Indeed,

\[ k\ =\ m_5(k)\ \le\ \mathit{rn}(k)\ \le\ k \]

for every   k=1\ldots 5.   END of PROOF

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.

Complexity and subcomplexities, Part 0


Sometimes one studies certain objects, where each object admits multiple representations or can be obtained by more than one procedure. We are often interested in efficiency. Thus with each representation or procedure we associate a positive real number which measures the complexity (inefficiency) of the representations or procedures. Thus for each object we can consider the minimum or at least the greatest lower bound of all complexities associated with the given object, taken over all representations or procedures which provide our object. It’s only natural that we are interested in computing (or estimating) the complexity of objects.

Given any representation (or procedure)   A   of an object   a   we obtain an upper bound on the complexity   \gamma(a)   of object   a   in terms of complexity   \Gamma(A)   of the representation   A   of object   a,   namely:

\[ \gamma(a)\le \Gamma(A) \]

Thus by providing (constructing) representations we approximate the complexity of an object from above.

But how to obtain the lower bounds for complexity (of objects)? I have provided an answer in 1981: by defining the notion of a subcomplexity function, and then by constructing subcomplexities. Each subcomplexity function provides a lower bound for the complexity of not just one object but for each of them!


I introduced a computational complexity of birational numbers \[x:=\frac k{2^n}\] in 1981-2 (I worked at Martin Marietta at the time; outside MM, Wayne Lawton was familiar with my manuscript).I did it in the context of parallel processing. The complexity of   x   was meant to be the complexity of multiplying by   x   an array (an image). I basically solved all important problems in that case. My method involved introducing subcomplexity functions. I even formulated a general theory for generalized universal algebras (just the initial trivial but basic theorem) about the complexity being the greatest of the subcomplexities. Perhaps I will have patience to write it again in this blog (and later on my ipage?). Right now I feel like going back to a silly (but fun! and full of deep number-theoretical open questions) topic of the complexity of natural numbers expressed by three symbols:   \[1\ +\ \cdot\]   and parenthesis   \[(\ \ )\] — or else one would use the Łukasiewicz notation (hm, why not?!). Yes, let me use the (reversed) Łukasiewicz Notation. Anyway, the topic was introduced (as long as I know at this time, but see the note below) by Richard Guy:

  • Richard Guy, Open Problems, “Complexity of natural numbers with respect to 1, +, *”, American Mathematical Monthly, 1986-April
  • R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
  • R. K. Guy, Unsolved Problems Number Theory, Sect. F26.
  • K. Mahler and J. Popken, Over een Maximumprobleem uit de Rekenkunde (Dutch: On a maximum problem in arithmetic), Nieuw Arch. Wiskunde, (3) 1 (1953), pp. 1-15.
  • OEIS — 1+* integer complexity

However I don’t know the content of the above paper by K.Mahler and J.Popken.

When I first saw Guy’s article in the open problems section of Monthly, I immediately duplicated most of the results listed there (it was not difficult). I’ve written about my subcomplexity approach on sci.math and on more than one occasion on pl.sci.matematyka (p.s.m.). Later, when I introduced this topic on p.s.m., one of the participants, Andrzej Komisarski also has easily duplicated most of the known results (in the old-fashion way, without using subcomplexities–I don’t know if A.K or I got any original results up to or at that time; if any of us did, it would not be anything significant). Finally, I posted on p.s.m. (in Polish) a three part post. The second part did have new results, which now I want to reproduce on this blog in English (and I wouldn’t mind to get still more results). The title of my said post on p.s.p. was

Podzlozonosci, Czesc 2 — wh, 2001-03-09