Integer complexity: Stability and self-similarity

Abstract

Define $||n||$ to be the complexity of $n$, the smallest number of ones needed to write $n$ using an arbitrary combination of addition and multiplication. The set $\mathcal{D}$ of defects, differences $\hat{I}´(n):=||n||-3{\log }_{3}n$, is known to be a well-ordered subset of $[0,\infty )$, with order type $\ddot{I}{‰}^{\ddot{I}}‰$. This is proved by showing that, for any $r$, there is a finite set ${\mathcal{S}}_s$ of certain multilinear polynomials, called low-defect polynomials, such that $\hat{I}´(n)\le s$ if and only if one can write $n=f(3^{k_1},\dots ,3^{k_r})3^{k_{r+1}}$. In this paper we show that, in addition to it being true that $\mathcal{D}$ (and thus $\overline{\mathcal{D}}$) has order type $\ddot{I}{‰}^{\ddot{I}}‰$, this set satisifies a sort of self-similarity property with ${\overline{\mathcal{D}}}^{\prime }=\overline{\mathcal{D}}+1$. This is proven by restricting attention to substantial low-defect polynomials, ones that can be themselves written efficiently in a certain sense, and showing that in a certain sense the values of these polynomials at powers of $3$ have complexity equal to the naïve upper bound most of the time. As a result, we also prove that, under appropriate conditions on $a$ and $b$, numbers of the form $b(a{3}^k+1)3^{\ell }$ will, for all sufficiently large $k$, have complexity equal to the naïve upper bound. These results resolve various earlier conjectures of the second author.

39 pages