Integer Complexity, Addition Chains, and Well-Ordering.
Harry Altman · Deep Blue (University of Michigan) · 2014
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) =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=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).