Scholz–Brauer inequality for multiplication chains
Let $\ell(n)$ be the length of a shortest addition chain for $n$, with $\ell(1) = 0$; an addition chain of length $r$ for $n$ computes $A^n$ from a matrix $A$ with $r$ multiplications. Brauer proved $\ell(2^n - 1) \le n - 1 + \ell^*(n)$, where $\ell^*(n)$ is the length of a shortest star chain for $n$: an addition chain $1 = a_0 < a_1 < \dots < a_r = n$ in which every $a_i$ with $i > 0$ is $a_{i-1} + a_j$ for some $j < i$. So the inequality below holds whenever $\ell^*(n) = \ell(n)$. Clift showed by computer that it holds for every $n < 5784689$, with equality for every $n \le 64$.
Problem. Is $\ell(2^n - 1) \le n + \ell(n) - 1$ for every $n \ge 1$?
Source: Scholz (1937), Aufgabe 253, in the form Brauer (1939) gives it; see Bläser (2013), Research Problem 2.9.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NT — Number Theory
- Secondary
- CO, NA
- Keywords
- addition chains, exponentiation, OpenProblemsInNLA
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{scholz1937,
author = {Scholz, Arnold},
title = {Aufgabe 253},
journal = {Jahresber. Deutsch. Math.-Verein.},
volume = {47},
year = {1937},
pages = {41--42},
note = {Abt. II},
}
@article{brauer1939,
author = {Brauer, Alfred},
title = {On addition chains},
journal = {Bull. Amer. Math. Soc.},
volume = {45},
number = {10},
year = {1939},
pages = {736--739},
doi = {10.1090/S0002-9904-1939-07068-7},
}
@article{clift2011,
author = {Clift, Neill Michael},
title = {Calculating optimal addition chains},
journal = {Computing},
volume = {91},
number = {3},
year = {2011},
pages = {265--284},
doi = {10.1007/s00607-010-0118-8},
}
@book{blaser2013,
author = {Bl{\"a}ser, Markus},
title = {Fast Matrix Multiplication},
series = {Theory of Computing Library, Graduate Surveys},
number = {5},
publisher = {Theory of Computing Library},
year = {2013},
pages = {1--60},
doi = {10.4086/toc.gs.2013.005},
}
@misc{openproblemsinnla-ac07,
author = {Townsend, Alex},
title = {{AC-07}: Scholz–Brauer inequality for multiplication chains},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/arithmetic-and-complexity/AC-07/README.md},
note = {Read at commit b8c7852, 2026-10-07},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00183, "Scholz–Brauer inequality for multiplication chains", clopen.solutions.