Internal Structure of Addition Chains: Well-Ordering

An addition chain for $n$ is defined to be a sequence $(a_0,a_1,\dots ,a_r)$ such that $a_0=1$, $a_r=n$, and, for any $1\le k\le r$, there exist $0\le i, j<k$suchthat$a_k = a_i + a_j$;thenumber$r$ is called the length of the addition chain. The shortest length among addition chains for $n$, called the addition chain length of $n$, is denoted $\mathrm{\ell }(n)$. The number $\mathrm{\ell }(n)$ is always at least ${\log }_{2}n$; in this paper we consider the difference ${\delta }^{\mathrm{\ell }}(n):=\mathrm{\ell }(n)-{\log }_{2}n$, which we call the addition chain defect. First we use this notion to show that for any $n$, there exists $K$ such that for any $k\ge K$, we have $\mathrm{\ell }(2^{k}n)=\mathrm{\ell }(2^{K}n)+(k-K)$. The main result is that the set of values of ${\delta }^{\mathrm{\ell }}$ is a well-ordered subset of $[0,\mathrm{\infty })$, with order type ${\omega }^{\omega }$. The results obtained here are analogous to the results for integer complexity obtained in [1] and [3]. We also prove similar well-ordering results for restricted forms of addition chain length, such as star chain length and Hansen chain length.