Upper and lower estimates for integer complexity
Pith reviewed 2026-05-15 06:58 UTC · model grok-4.3
The pith
Integer complexity of almost all n satisfies ||n|| ≤ C_avg log n + o(log n) as n tends to infinity.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Let ||n|| denote the least number of 1's required to write the positive integer n using additions, multiplications, and parentheses. We prove that ||n|| ≤ C_avg log n + o(log n) as n → ∞, which in particular yields lim sup ||n||/log n ≤ C_avg. We also prove that ||n|| ≥ 3.06 log_3 n for almost all positive integers n.
What carries the argument
The complexity function ||n|| together with density estimates on the count of integers expressible with a bounded number of 1's.
If this is right
- lim sup ||n||/log n ≤ C_avg ≈ 3.236
- Almost all n obey the lower bound ||n|| ≥ 3.06 log_3 n
- The typical growth rate of complexity is asymptotically controlled by the average-case constant
- The worst-case bound 3 log_2 n is superseded for all but o(1) density of integers
Where Pith is reading between the lines
- Numbers attaining near-maximal complexity must form a zero-density set
- Further sharpening of the 3.06 constant would pin down the typical growth rate more precisely
- The same density techniques could apply to related problems such as minimal length of addition-multiplication expressions in other semirings
Load-bearing premise
The constant C_avg is taken as given from earlier average-complexity results, and the counting arguments apply uniformly outside a negligible set of integers.
What would settle it
An infinite sequence of n where ||n|| exceeds C_avg log n by more than any o(log n) term, or a positive-density set of n where ||n|| falls below 3.06 log_3 n.
read the original abstract
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 all numbers $n$, the better inequality $\|n\|\leq C_{avg}\log n$ holds, where, importantly, $C_{avg}\approx 3.236<\sup_{n} \frac{\|n\|}{\log n}$. We show that in fact $\|n\|\leq C_{avg}\log n+o(\log n)$ as $n\to\infty$, which, in particular, yields that $\limsup\limits_{n\to\infty}\frac{\|n\|}{\log n}\leq C_{avg}$. We also obtain the first nontrivial lower bound $\|n\|\geq 3.06\log_3 n$ for almost all numbers $n$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves that the integer complexity ||n|| satisfies ||n|| ≤ C_avg log n + o(log n) as n→∞ for every positive integer n, where C_avg≈3.236 is the constant appearing in the known average-case upper bound for almost all n; this immediately yields lim sup ||n||/log n ≤ C_avg. It also establishes the first nontrivial lower bound ||n|| ≥ 3.06 log_3 n that holds for almost all n.
Significance. If the o(log n) error term is rigorously justified, the result shows that the average-case constant C_avg governs the worst-case growth of ||n|| up to lower-order terms, closing the gap between the known average and the lim sup. The new lower bound for typical integers is a concrete improvement over the universal 3 log_3 n bound and supplies the first quantitative statement about the complexity of a density-1 set.
major comments (2)
- [§3, Theorem 3.1] §3, Theorem 3.1 (uniform upper bound): the passage from the average-case inequality ||n|| ≤ C_avg log n (valid for almost all n) to the uniform statement with additive o(log n) error invokes asymptotic counting arguments from the literature without an explicit estimate on the size or complexity of the exceptional set; any non-uniformity in that set could produce deviations larger than o(log n), which would invalidate both the uniform bound and the consequent lim sup claim.
- [§5] §5, proof of the lower bound: the constant 3.06 is obtained by optimizing a parameter in a counting argument over residue classes or factorizations, but the manuscript does not display the explicit optimization or the resulting error term; it is therefore unclear whether 3.06 is the best constant obtainable by the method or merely a convenient numerical value.
minor comments (2)
- Throughout the paper the base of the logarithm in the upper bound is left implicit; while C_avg is defined with respect to a specific base in the cited literature, an explicit statement (e.g., “log denotes the natural logarithm”) would remove ambiguity.
- [Abstract] The abstract states “log n” in the upper bound but “log_3 n” in the lower bound; consistent notation (or a clarifying sentence) would improve readability.
Simulated Author's Rebuttal
We thank the referee for the thorough review and constructive feedback on our paper. We respond to the major comments point by point, indicating where revisions will be made to address the concerns.
read point-by-point responses
-
Referee: [§3, Theorem 3.1] §3, Theorem 3.1 (uniform upper bound): the passage from the average-case inequality ||n|| ≤ C_avg log n (valid for almost all n) to the uniform statement with additive o(log n) error invokes asymptotic counting arguments from the literature without an explicit estimate on the size or complexity of the exceptional set; any non-uniformity in that set could produce deviations larger than o(log n), which would invalidate both the uniform bound and the consequent lim sup claim.
Authors: The referee correctly identifies that the manuscript relies on asymptotic results from the literature for the exceptional set without providing explicit bounds. To resolve this, we will revise the proof in §3 to incorporate explicit estimates on the size and complexity of the exceptional set, ensuring that the additive error is indeed o(log n) for all n. This addition will also solidify the lim sup result. revision: yes
-
Referee: [§5] §5, proof of the lower bound: the constant 3.06 is obtained by optimizing a parameter in a counting argument over residue classes or factorizations, but the manuscript does not display the explicit optimization or the resulting error term; it is therefore unclear whether 3.06 is the best constant obtainable by the method or merely a convenient numerical value.
Authors: We will update §5 to include the explicit optimization details for the parameter in the counting argument. This will show the function being minimized, the numerical optimization process, and confirm the error term, demonstrating that 3.06 is the value derived from the method rather than an arbitrary choice. revision: yes
Circularity Check
No significant circularity in derivation of uniform upper bound or almost-all lower bound
full rationale
The paper takes the constant C_avg as an independently established quantity from prior literature for the average-case bound on almost all n, then derives the new uniform bound ||n|| ≤ C_avg log n + o(log n) via asymptotic counting arguments that control the exceptional set. This extension does not reduce by construction to a self-definition, fitted input, or self-citation chain within the paper; the o(log n) term is obtained from uniform estimates on counting measures rather than re-fitting C_avg. The new lower bound ||n|| ≥ 3.06 log_3 n for almost all n is obtained separately via direct probabilistic or density arguments without reference to the upper-bound results or C_avg. No load-bearing self-citations, ansatzes smuggled via citation, or renamings of known results appear in the central claims. The derivation remains self-contained against external benchmarks for C_avg.
Axiom & Free-Parameter Ledger
free parameters (1)
- C_avg =
3.236
axioms (1)
- standard math Standard properties of logarithms and asymptotic notation for counting constructions in the addition-multiplication semigroup.
Lean theorems connected to this paper
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
Theorem 1. For any positive integer n≥3, ||n|| ≤ C_avg log n + C(log n)^{2/3}(log log n)^{4/3}
-
IndisputableMonolith/Foundation/ArithmeticFromLogic.leanembed_injective unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
C ≤ (1/b log b) ∑_{r=0}^{b-1} D(b,r) for any b≥2
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Reference graph
Works this paper leans on
-
[1]
Altman,Integer complexity: representing numbers of bounded defect, Theor
H. Altman,Integer complexity: representing numbers of bounded defect, Theor. Comput. Sci. 652 (2016), 64–85
work page 2016
-
[2]
Altman,Integer complexity: algorithms and computational results, Integers 18(45) (2018)
H. Altman,Integer complexity: algorithms and computational results, Integers 18(45) (2018)
work page 2018
- [3]
-
[4]
Amano,Integer complexity and mixed binary-ternary representation, Leibniz Int
K. Amano,Integer complexity and mixed binary-ternary representation, Leibniz Int. Proc. Inform. (LIPIcs) 248(29) (2022), 1–16
work page 2022
-
[5]
J. Arias de Reyna,Complexity of integer numbers, Integers 24 (2024) (translation fromComplejidad de los n´ umeros naturales, Gaceta R. Soc. Mat. Esp. 3 (2000), 230–250). 3Access the code “defect check local.py” via thelink . 13
work page 2024
-
[6]
Algorithms for determining integer complexity
J. Arias de Reyna, J. van de Lune,Algorithms for determining integer complexity, arXiv:1404.2183
work page internal anchor Pith review Pith/arXiv arXiv
-
[7]
K. Cordwell, A. Epstein, A. Hemmady, S. J. Miller, E. Palsson, A. Sharma, S. Steinerberger, Y. N. T. Vu,On algorithms to calculate integer complexity, Integers 19 (2019), A12
work page 2019
-
[8]
Guy,Some suspiciously simple sequences, Amer
R.K. Guy,Some suspiciously simple sequences, Amer. Math. Monthly 93(3) (1986), 186–190
work page 1986
-
[9]
Q. He,Improved algorithms for integer complexity, Proceedings of 2024 Symposium on Simplicity in Algorithms (SOSA), 107–114
work page 2024
-
[10]
Integer Complexity: Experimental and Analytical Results
J. Iraids, K. Balodis, J. ˘Cer¸ nenoks, M. Opmanis, R. Opmanis, K. Podnieks,Integer complexity: experimental ana analytical results, arXiv:1203.6462, Scientific Papers University of Latvia, Comp. Sci. and Inf. Tech. 787 (2012), 153– 179
work page internal anchor Pith review Pith/arXiv arXiv 2012
- [11]
-
[12]
L. Kuipers, H. Niederreiter,Uniform distribution of sequences, Wiley, New York, 1974
work page 1974
- [13]
-
[14]
Rawsthorne,How many1’s are needed?, Fibonacci Quart
D.A. Rawsthorne,How many1’s are needed?, Fibonacci Quart. 27(1) (1989), 14–17
work page 1989
-
[15]
An Application of Markov Chain Analysis to Integer Complexity
C. Shriver,An application of Markov chain analysis to integer complexity, arXiv:1511.07842
work page internal anchor Pith review Pith/arXiv arXiv
-
[16]
Sloane,The on-line encyclopedia of integer sequences
N.J.A. Sloane,The on-line encyclopedia of integer sequences. The complexity ofn: number of1’s required to buildn using+and·, https://oeis.org/A005245
-
[17]
Steinerberger,A short note on integer complexity, Contrib
S. Steinerberger,A short note on integer complexity, Contrib. Discrete Math. 9(1) (2014)
work page 2014
-
[18]
Zelinsky,Upper bounds on integer complexity, arXiv:2211.02995
J. Zelinsky,Upper bounds on integer complexity, arXiv:2211.02995. Sergei Konyagin, Steklov Mathematical Institute, Gubkina Str. 8, Moscow 119991, Russia Email address:konyagin@mi-ras.ru Kristina Oganesyan, Steklov Mathematical Institute, Gubkina Str. 8, Moscow 119991, Russia Email address:kristina.oganesyan@mi-ras.ru 14
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.