we-solve (beta)

Math-573 · mathematics · Number theory

Scholz Conjecture

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Shared notation.
Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

An addition chain for $m\geq1$ is $1=a_0<a_1<\cdots<a_\ell=m$ such that each $a_i=a_j+a_k$ for some $j,k<i$, with $j=k$ allowed. Its length is $\ell$, and $\ell(m)$ is the least possible length. The conjecture is $\ell(2^n-1)\leq n-1+\ell(n)$ for every $n\geq1$. [S1] [S2]

Statement recorded in the supplied source.
Is the shortest addition chain for $2^n - 1$ at most $n - 1$ plus the length of the shortest addition chain for $n$? [S1]
Residual task reported by the archive.

The embedded review (2026-08-17) records: Prove l(2^n-1) <= n-1+l(n) for every positive integer n or find a genuine counterexample. [S1]

Short English statement

Can an efficient addition chain for n always be turned into one for two to the nth power minus one with at most n minus one extra steps?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-573-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on Math-573

Scholz's Addition-Chain Conjecture

Definitions and mathematical statement

Shared notation.
Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

An addition chain for $m\geq1$ is $1=a_0<a_1<\cdots<a_\ell=m$ such that each $a_i=a_j+a_k$ for some $j,k<i$, with $j=k$ allowed. Its length is $\ell$, and $\ell(m)$ is the least possible length. The conjecture is $\ell(2^n-1)\leq n-1+\ell(n)$ for every $n\geq1$. [S1] [S2]

Statement recorded in the supplied source.
Is the shortest addition chain for $2^n - 1$ at most $n - 1$ plus the length of the shortest addition chain for $n$? [S1]
Residual task reported by the archive.

The embedded review $2026-08-17$ records: Prove $l(2^n-1)\leq n-1+l(n)$ for every positive integer n or find a genuine counterexample. [S1]

Short English statement

Can an efficient addition chain for n always be turned into one for two to the nth power minus one with at most n minus one extra steps?

Research attempt

Scope and selected construction.
The bound involves the shortest unrestricted addition-chain length $\ell(n)$, not the length of a convenient binary chain. The traditional star-chain construction associated with Brauer [S2] is useful but has a specific limitation. Clift's account [S3], inspected 1 October 2026, discusses that limitation and more elaborate chain classes. The proof below is self-contained for star chains and is not presented as a proof that every shortest chain has the required form.
The elementary lower bound on length.
Every entry in a length-$r$ addition chain is at most $2^r$ at step $r$: at each new step the sum of two earlier entries is at most twice the current maximum. Thus \[ \ell(n)\ge\lceil\log_2n\rceil. \] The case $n=1$ has length zero and the conjectured bound reads $\ell(1)\le0$, which holds. For later constructions the number one is already available and costs no additional step.
Lifting a star chain to a Mersenne-number chain.
A star chain is an addition chain $1=a_0<a_1<\cdots<a_r=n$ in which every step is $a_i=a_{i-1}+a_{j_i}$ with $j_i<i$. Suppose that the values $M_{a_j}=2^{a_j}-1$ have already been produced for $j<i$, and the last produced value is $M_{a_{i-1}}$. The identity \[ M_{a_i}=2^{a_{j_i}}M_{a_{i-1}}+M_{a_{j_i}} \] produces the next desired value using $a_{j_i}$ doublings followed by one addition of the stored $M_{a_{j_i}}$. Every intermediate value is strictly larger than the previous one, and every addition uses earlier available entries, so this is a valid addition chain, not a computation with uncounted multiplication operations.

The cost is \[ \sum_{i=1}^r(a_{j_i}+1) =\sum_{i=1}^r(a_i-a_{i-1})+r=n-1+r. \] Writing $\ell_*(n)$ for the shortest star-chain length proves \[ \ell(2^n-1)\le n-1+\ell_*(n). \] In particular the conjecture holds for every $n$ admitting a shortest chain that is a star chain. The telescoping identity is the crucial reason this special construction has the right cost.

Infinite subcases with optimal star chains.
If $n=2^a$, the repeated-doubling chain has length $a$, which matches the lower bound and is a star chain. Thus the desired bound holds for all powers of two. More generally let $n=2^a+2^b$ with $a>b\ge0$. First build $2^{a-b}$ by $a-b$ doublings, add one, and then double $b$ times. This gives a star chain of length $a+1$. Since $2^a<n<2^{a+1}$, the lower bound is also $a+1$. The chain is shortest, so the conjecture holds whenever the binary expansion of $n$ has at most two nonzero bits.

For arbitrary $n$, the usual left-to-right binary algorithm is a star chain with length $\lfloor\log_2n\rfloor+s_2(n)-1$, where $s_2(n)$ counts the ones in the binary expansion. Each further bit costs one doubling, and each further one costs an addition of one. Consequently the lifting proves the unconditional weaker bound \[ \ell(2^n-1)\le n-2+\lfloor\log_2n\rfloor+s_2(n). \] This is a bound for every $n$, but replacing its binary-chain length by $\ell(n)$ is a further step, not an algebraic simplification.

A small worked construction.
For $n=5$ take the optimal chain $1,2,4,5$. Lifting it gives \[ 1,2,3,6,12,15,30,31. \] Its seven additions equal $5-1+\ell(5)=4+3$. The stored smaller Mersenne values are essential: at the exponent-doubling step from two to four, the value $M_2=3$ is retained and added to $12$ to obtain $15$. Merely replacing each exponent entry by $2^{a_i}-1$ would give $1,3,15,31$, which is not an addition chain on its own.
Why the same count fails for arbitrary chains.
For a general step $a_i=a_j+a_k$ with neither summand necessarily $a_{i-1}$, the identity $M_{a_i}=2^{a_k}M_{a_j}+M_{a_k}$ is still valid. But its doublings start from an older value, and the increments $a_k$ no longer telescope as $a_i-a_{i-1}$. Some newly needed intermediate values may also be less than the current maximum, requiring a reordered construction or additional stored values. This is a cost and dependency problem, not a failure of the algebraic identity.

Thus a claim that every addition-chain step lifts with total doubling cost $n-1$ must prove a global schedule or another invariant. Summing local costs without such a schedule can overcount or omit shared intermediate work. Clift [S3] gives more advanced examples where a simple common-path accounting fails; the present argument does not assume those examples prove the conjecture false, nor does it need their computational claims to establish the star-chain result.

Executed optimality and construction checks.
For every $1\le n\le32$, the script finds a shortest unrestricted chain by iterative-deepening exhaustive search. At each depth it permits the sum of any two earlier entries, not only star steps; it prunes only when repeated doubling cannot reach the target in the remaining steps. Testing all depths from the elementary lower bound up to the first success certifies optimality in this finite range. Each returned chain happens to be a star chain. The script lifts it and checks every output step and the exact cost $n-1+\ell(n)$. It therefore verifies the desired inequality through $n=32$ by explicit upper-bound certificates, without claiming to find $\ell(2^n-1)$ exactly. Files: checks.py, results.json in _Local/Erdos_problems/UnsolvedMath/attempt_audit_2026_10_01/number_theory/.
Remaining gap and outcome.
The construction proves the conjecture on the optimal-star-chain subclass and, in particular, on the two infinite binary subfamilies above. What remains is a construction with the target cost for arbitrary $n$ using its unrestricted optimum, or another argument proving that bound without lifting a shortest chain. Outcome: UNRESOLVED. No equality between $\ell_*(n)$ and $\ell(n)$ is assumed in general.

Sources

Go to contribution →