Integer complexity: Stability and self-similarity

arXiv2111.00671MaRDI QIDQ6381817FDOQ6381817

Authors: Harry Altman, Juan Arias de Reyna Martinez 

Publication date: 31 October 2021

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 $mathscrD$ of defects, differences $delta(n):=||n||-3lo{g}_{3}n$, is known to be a well-ordered subset of $[0,infty)$, with order type $omeg{a}^{o}mega$. 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 $delta(n)les$ if and only if one can write $n=f(3^{k_1},ldots,3^{k_r})3^{k_{r+1}}$. In this paper we show that, in addition to it being true that $mathscrD$ (and thus $overlinemathscrD$) has order type $omeg{a}^{o}mega$, it satisifies a sort of self-similarity property with $overline{m}^{\prime }athscrD=overlinemathscrD+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"ive 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^{e}ll$ will, for all sufficiently large $k$, have complexity equal to the na"ive upper bound. These results resolve various earlier conjectures of the second author.

Mathematics Subject Classification ID

Other number representations (11A67)

This page was built for publication: Integer complexity: Stability and self-similarity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6381817)