Paper 2024/1199

On degrees of carry and Scholz's conjecture

Abstract

Exploiting the notion of carries, we obtain improved upper bounds for the length of the shortest addition chains $\iota (2^n-1)$ producing $2^n-1$. Most notably, we show that if $2^n-1$ has carries of degree at most $$\kappa (2^n-1)=\frac{1}{2}(\iota (n)-\lfloor \frac{\log n}{\log 2}\rfloor +\sum _{j=1}^{\lfloor \frac{\log n}{\log 2}\rfloor }\{\frac{n}{2^j}\})$$ then the inequality $$\iota (2^n-1)\le n+1+\sum _{j=1}^{\lfloor \frac{\log n}{\log 2}\rfloor }(\{\frac{n}{2^j}\}-\xi (n,j))+\iota (n)$$ holds for all $n\in \mathbb{N}$ with $n\ge 4$, where $\iota (\cdot )$ denotes the length of the shortest addition chain producing $\cdot$, $\{\cdot \}$ denotes the fractional part of $\cdot$ and where $\xi (n,1):=\{\frac{n}{2}\}$ with $\xi (n,2)=\{\frac{1}{2}\lfloor \frac{n}{2}\rfloor \}$ and so on.