Integer Complexity, Addition Chains, and Well-Ordering.

Abstract

In this dissertation we consider two notions of the "complexity" of a natural number, one being addition chain length, the other known as "integer complexity".

The integer complexity of n, denoted ||n||, is the smallest number of 1's needed to write n using an arbitrary combination of addition and multiplication. It is known that n>=3log_3(n) for all n.

We consider the difference delta(n):=||n||−3log_3(n), which we call the defect of n. We consider the set of all defects - the set D:={delta(n) : n>=1}. We show that, as a set of real numbers, D is well-ordered, with order type omega^omega; we also show the same for several variants of D. Moreover, we show that, for k>=1 a natural number, the intersection of D with [0, k) has order type omega^k.

We also use the defect to prove stabilization results about ||n||. Specifically, for any n, there exists K=K(n) such that for k>=K, we have delta(3^k*n)=delta(3^K*n). We call K(n) the stabilization length of n.

Finally, we provide a way of, given r>0, computing all numbers n with delta(n)<r. We use this to show that K(n) is effectively computable. The algorithm is also, empirically, much faster than existing methods for computing ||2^k||, and we use it to prove that ||2^k*3^l||=2k+3l for 0<=k<=48 and l>=0 with k+l>0.

In parallel to our results for integer complexity, we also consider addition chain length. An addition chain for n is a sequence (a_0,a_1,...,a_r) such that a_0=1, a_r=n, and, for any k with 1<=k<=r, there exist 0<=i,j<=k such that a_k=a_i+a_j; the number r is the length of the chain. The shortest length among addition chains for n, the addition chain length of n, is denoted l(n). The number l(n) is always at least log_2(n).

We consider the difference delta^l(n):=l(n)-log_2(n), which we call the addition-chain defect of n, and the set of all addition-chain defects D^l := {delta^l(n) : n>=1}. We show that D is also a well-ordered set with order type omega^omega. We also use the defect to prove stabilization results about l(n); specifically, for any n, there exists K'=K'(n) such that for k>=K', we have delta^l(2^k*n)=delta^l(2^K'*n).