Id: arxiv/2603.20876 Url: https://arxiv.org/abs/2603.20876 Tags: math.NT, math.CO Score: 0 Title: Upper and lower estimates for integer complexity Domain: math.NT Source: arxiv Authors: Sergei Konyagin, Kristina Oganesyan Reviews: 0 Subject: math.NT Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-03-21 Page: https://delphi.science/r/arxiv/2603.20876 Let $\|n\|$ 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\leq\|n\|\leq 3\log_2 n$ for all $n$ is well known and reveals the logarithmic behaviour of the complexity function $\|n\|$. 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…