“We have a population of five million [in Norway], remember, so we cannot hope to have as many chess players as India,” said Agdestein.

No kidding!

Reply

“We have a population of five million [in Norway], remember, so we cannot hope to have as many chess players as India,” said Agdestein.

No kidding!

After this attempt I’ll try to advance the problem of counting pos seriously, in a new post: * pos(n)*.

Positive integers are called natural numbers. When also integer is included then they are called non-negative integers.

I’ll be concerned with the finite sets only. A *partial order* is abbreviated as *po*. Pos are in a bijective (1-1) correspondence with the -topologies. We want to count the number of pos in arbitrarily fixed (finite) set, or–what is essentially the same–the -topologies (in the same set).

Let be the number of coverings of an -element set by sets , i.e. (it’s a nice *mood improver*, i.e. a simple exercise that is easier than it looks). The sets can be empty.

The following formula:

holds for arbitrary non-negative ; here the exponentiation conventions honors equality .

A sequences of non-negative integers is called a signatures if there exists a zero element ; and .

Next, we associate a unique signature with every finite poset. If two such sets are isomorphic then they will have the same signature.

Consider a finite poset (partially ordered set) (thus ). Then let be the set of the minimal elements of ; and where and .

Let’s continue these definitions: , where:

- ;
- .

We start with *dabagrams* which are ideograms and English and Polish abr. A few of dabagrams may serve as synonyms. They have the same role.

Every dabagrams is a *dabaphrase*. (That’s a start of an axiomatic definition of a dabaphrase).

This is an introduction.

- to be soon

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.

By definition of $\mathit{C0},$:

- $\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$

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)

$ 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: . 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.

- First three properties of complexity
- Subcomplexities
- Ceiling of a subcomplexity
- Maximum of two subcomplexities. A truncated subcomplexity.
- Subcomplexity

Every Ł-string features character at least one time. It follows that for every natural number . On the other hand, since Ł-string represents , it follows that , hence:

\[ \mathit{rn}(1) = 1\]

That’s the **first** of the three properties. Now let be two arbitrary natural numbers; and let Ł-strings be such that:

- and ;
- and

Then Ł-string represents (has value) . 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 . 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)\ + \]

**DEFINITION 0** A real positive function is called a subcomplexity satisfies the following three properties:

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

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

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

Let be an arbitrary real number. Then the floor and the ceiling 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 . They have the following properties for every real and integer :

We will apply the latter property. Let be an arbitrary subcomplexity. Let be given by:

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

(one could write ). Then hence . Thus has the first property of subcomplexities.

Now let be two arbitrary natural numbers. Then

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

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

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

Thus 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.

Let be two arbitrary subcomplexities. Define their maximum in the usual way:

\[ \forall_{n\in\mathbb N}\quad \gamma(n)\ \ :=\ \ \max(\alpha(n)\ \ \beta(n)) \]

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

Let be an arbitrary subcomplexity. Let be an arbitrary positive real number. Define the truncated function as follows:

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

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

**POTENTIAL APPLICATION** Let be a subcomplexity, and let be such that for every . Then define as follows:

Then is a subcomplexity too–call it an *improved subcomplexity*.

Let’s define function as follows:

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

First of all which means that function has the first subcomplexity property.

Now let be two arbitrary natural numbers. Then

which show that 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 then and , 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 . Next, if (so that ) then

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

Finally, let the remaining possibility hold: and . Then and 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 ** ** is a subcomplexity**.

**THEOREM 0** for every .

**PROOF** Indeed,

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

for every . **END of PROOF**

I’ll consider the problem of the complexity of natural numbers , where the complexity of is defined as the minimal number of occurences of in arithmetical formulas (strings) which reprezent , and which consist only of copies of three characters (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:

The above equalities, of the type, will be proved later; at this time we can only claim the respective inequalities (of course claim for is obvious).

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:

- is an Ł-string;
- if are Ł-strings then the concatenation is an Ł-string;
- if are Ł-strings then the concatenation 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 which satisfies the three rules above).

Now the value is defined simply as , 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:

First we define the complexity of a Ł-strings (as the number of appearances of 1):

for arbitrary Ł-strings (in the last two formulas above we have mixed operations on the left, but the same twice, i.e. , on the right).

Finally, the complexity of an arbitrary natural number is defined as follows:

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

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

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

Moreover, now , 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 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:

- etc.

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

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

or , 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 is better than integer . In general, let , where . 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 for which is as large as possible; it is the largest for and for the powers of . More about it later.

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) of an object we obtain an upper bound on the complexity of object in terms of complexity of the representation of object , 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 was meant to be the complexity of multiplying by 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

**Goal:** obtain inexpensive connection for the whole building (for all floors).

**Premise:** the true cost of wireless Internet connection is low.

We need to approach companies, which provide connection, with the following offer (but the point 2 below is just for us–they don’t need to be concerned with point 2):

- The Company provides its service (for the whole building–every floor) for the first month.
- L.T. residents–only those who want to pay–contribute some $$ toward the payment for the company near the end of the consecutive month of the service. Each resident contributes as much as s/he wants to.
- The Company receives the $$ from L.T. near the end of the consecutive month (the amount may vary from month to month), and then it decides if it wants to continue for another month (the decision may go either way).
- The process described in points 2-3 is repeated a month after a month.

- This arrangment does not put any pressure on apartment rents (on L.T.’s budget).
- Nobody is forced to pay anything. You may use the service, and pay nothing. Everybody pays each month as much as they want to, possibly ZERO, possibly a different amount each month.
- If The Company gets too greedy, or L.T. residents too stingy, then the service will stop.