Upper and lower estimates for integer complexity

Abstract

Let $\Vert n\Vert$ stand for the integer complexity of the number $n$, i.e. for the least number of $1$'s needed to write $n$ using arbitrary many additions, multiplications, and parentheses. The two-sided inequality $3{\log }_{3}n\le \Vert n\Vert \le 3{\log }_{2}n$ for all $n$ is well known and reveals the logarithmic behaviour of the complexity function $\Vert n\Vert$. While the lower bound $3{\log }_{3}n$ is attained infinitely many times at powers of $3$, the best upper estimate is still unknown, although there are some improvements of the trivial bound $3{\log }_{2}n$. Besides, for $‘‘$typical$"$ numbers, i.e. for almost all numbers $n$, the better inequality $\Vert n\Vert \le C_{avg}\log n$ holds, where, importantly, $C_{avg}\approx 3.236<{\sup }_n\frac{\Vert n\Vert }{\log n}$. We show that in fact $\Vert n\Vert \le C_{avg}\log n+o(\log n)$ as $n\to \infty$, which, in particular, yields that $\underset{n\to \infty }{\mathrm{limsup}}\frac{\Vert n\Vert }{\log n}\le C_{avg}$. We also obtain the first nontrivial lower bound $\Vert n\Vert \ge 3.06{\log }_{3}n$ for almost all numbers $n$.

14 pages. The value of $C_{avg}$ is changed and several inaccuracies are corrected