Additive Complexity of Natural Numbers

We define the sequence of natural numbers by defining a first element, called "zero", and a successor-function S1 defined for every natural number -- this is the set-theoretic definition of the natural numbers with focus on algebra (choose zero as the first element because it is the neutral element of addition).

Normally you are allowed to generate each natural number by evaluation of S1 on any already defined natural number; which means simply iterating this function S1 as many (finite) times as you want on the first element. E.g. S1(S1(S1(0))) = 3 to get its fourth element.
But in our model we are restricted to iterate every function only one time. On the other hand we get granted to define as many new functions as wanted. Of course we can only define new functions Si from already defined functions Sj by nesting them one time. In general Si:= Sj(Sk) where we denote i with the value of j+k using well-known addition, because this Si is identical to an i-times nesting of S1.

How many functions Si are needed AT LEAST to get a certain natural number n, if explicit evaluation is only allowed for not nested functions on the first element?

Let us answer this question constructively for these first small numbers:

Because the indices of the functions always form an addition chain, the number of functions needed at least to generate n is exactly ℓ(n)+1 where ℓ(n) denotes the length of a shortest addition chain for n. This onetime nesting you may consider as a binary operation of concatination of functions. All these functions are recursively defined from only one original function therefore this binary operation is trivially commutative and associative. This is the justification for the above naming (better evaluation) of the index of each new defined function. These minimal number of functions which are needed to generate a certain n reflect the additive effort to reach this n. 'Additive' because Si(n)=n+i holds, if we had the usual binary operation +, which is named "addition", defined on the natural numbers. Thus we may call ℓ(n)+1 the additive complexity of a natural number n.+

Remark: If we use the classic set-theoretic definition of the natural numbers (first element is "1") which is founded on truthness of logical statements with free variables -- if and only if the cardinality of a set is positive then an element exists in the set --, then we must ask for the number of NEWLY defined functions Si in the above question. In this case we would/will define ℓ(n) as the additive complexity of a natural number n.

There is a famous conjecture of K.B. Stolarsky and D.E. Knuth (firstly stated in 1969) that always holds ℓ(n) >= floor( log2(n) ) + ceil( log2( ν(n) ) ) which connects sharply the additive complexity of n to its binary representation.

+We are forced to set ℓ(0) = -1.

Further reading for complexity measures on the natural numbers: H. Altman, "Integer Complexity, Addition Chains, and Well-Ordering", Ph.D. Thesis, University of Michigan, 2014

A different point of view

Consider sets A ⊂ ℕ with the property that ∀ a ∈ A :  a=1 ∨ ∃ x,y ∈ A : x+y=a.
Then holds ∀ n ∈ ℕ :  minA: n∈A |A| = ℓ(n)+1.

I learned that all this is old stuff already published 1979 by E.G. Belaga. I like to cite a note from his paper, that if ℓ(n) is itself an arithmetic ''projection'' of complexity in the sense of A.N. Kolmogorov, the problem of calculating it recalls the constructions of the ''universal solver'' of L. Levin.


Achim Flammenkamp
Last update: 2020-05-25 23:14:28 UTC+2