Paper 2023/051

On the Scholz conjecture on addition chains

Abstract

Applying the pothole method on the factors of numbers of the form $2^n-1$, we prove the stronger inequality $$\iota (2^n-1)\le n+1-\sum _{j=1}^{\lfloor \frac{\log n}{\log 2}\rfloor }\xi (n,j)+3\lfloor \frac{\log n}{\log 2}\rfloor$$ for all $n\in \mathbb{N}$ with $n\ge 64$ for $0\le \xi (n,j)<1$, where $\iota (\cdot )$ denotes the length of the shortest addition chain producing $\cdot$. This inequality is stronger than $$\iota (r)<\frac{\log r}{\log 2}(1+\frac{1}{\log \log r}+\frac{2\log 2}{(\log r{)}^{1-\log 2}})$$ in the case $r=2^n-1$ but slightly weaker than the conjectured inequality $$\iota (2^n-1)\le n-1+\iota (n).$$