Additive Complexity of Natural Numbers

We define the sequence of natural numbers by defining a first element, called "zero", and a successor-function S₁ 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 S₁ on any already defined natural number; which means simply iterating this function S₁ as many (finite) times as you want on the first element. E.g. S₁(S₁(S₁(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 S_i from already defined functions S_j by nesting them one time. In general S_i:= S_j(S_k) where we denote i with the value of j+k using well-known addition, because this S_i is identical to an i-times nesting of S₁.

How many functions S_i 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:

If n=0 then we need none, because 0 is already given.
If n=1 then we need only one, the already given function, because S₁(0)=1
If n=2 then we need two functions. From the given S₁ define S₂ = S₁(S₁) and then evalute S₂(0).
If n=3 then we need three functions. From the given S₁ define S₂ = S₁(S₁) and then S₃ = S₂(S₁). Finally evaluate S₃(0).
If n=4 then we need three functions. From the given S₁ define S₂ = S₁(S₁) and then S₄ = S₂(S₂). Finally evaluate S₄(0).
If n=5 then we need four functions: The given S₁ and then define canonically e.g. S₂, S₄, S₅. Finally evaluate S₅(0).
If n=6 then we need four functions: The given S₁ and then define canonically e.g. S₂, S₃, S₆. Finally evaluate S₆(0).
If n=7 then we need five functions: The given S₁ and then define canonically e.g. S₂, S₃, S₄, S₇. Finally evaluate S₇(0).
If n=8 then we need four functions: The given S₁ and then define canonically e.g. S₂, S₄, S₈. Finally evaluate S₈(0).

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 S_i(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 S_i 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 ∈ ℕ : min_{A: 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