Integer Complexity and Well-Ordering

Abstract

Define $\Vert n\Vert$ to be the complexity of $n$, the smallest number of ones needed to write $n$ using an arbitrary combination of addition and multiplication. John Selfridge showed that $\Vert n\Vert \ge 3{\log }_{3}n$ for all $n$. Define the defect of $n$, denoted $\delta (n)$, to be $\Vert n\Vert -3{\log }_{3}n$. In this paper, we consider the set $\mathcal{D}:=\{\delta (n):n\ge 1\}$ of all defects. We show that as a subset of the real numbers, the set $\mathcal{D}$ is well-ordered, of order type ${\omega }^{\omega }$. More specifically, for $k\ge 1$ an integer, $\mathcal{D}\cap [0,k)$ has order type ${\omega }^k$. We also consider some other sets related to $\mathcal{D}$, and show that these too are well-ordered and have order type ${\omega }^{\omega }$.

arXiv comment26 pages, 2 figures