# [Resource Topic] 2024/1199: On degrees of carry and Scholz's conjecture

Welcome to the resource topic for 2024/1199

Title:
On degrees of carry and Scholz’s conjecture

Authors: Theophilus Agama

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 \limits_{j=1}^{\lfloor \frac{\log n}{\log 2}\rfloor}{\frac{n}{2^j}})$$ then the inequality $$\iota(2^n-1)\leq n+1+\sum \limits_{j=1}^{\lfloor \frac{\log n}{\log 2}\rfloor}\bigg({\frac{n}{2^j}}-\xi(n,j)\bigg)+\iota(n)$$ holds for all n\in \mathbb{N} with n\geq 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.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.