Integer complexity: Stability and self-similarity

Let [Formula: see text] to be the complexity of n, the smallest number of ones needed to write n using an arbitrary combination of addition and multiplication (the smallest number of ones in a [Formula: see text]-expression for n). The set [Formula: see text] of defects, differences [Formula: see text], is known to be a well-ordered subset of [Formula: see text], with order type [Formula: see text]. This is proved by showing that, for any s, there is a finite set [Formula: see text] of certain multilinear polynomials, called low-defect polynomials, such that [Formula: see text] if and only if one can write [Formula: see text] for some [Formula: see text]. In this paper, we show that, in addition to it being true that [Formula: see text] (and thus [Formula: see text]) has order type [Formula: see text], this set satisfies a sort of self-similarity property, with [Formula: see text]. 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 three have complexity equal to the naïve upper bound most of the time. As an application, we also prove that, under appropriate conditions on a and b, numbers of the form [Formula: see text] 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.