10 problems

Let $\|n\|_{2}$ denote the binary complexity of the positive integer $n$. Let $r$ be a positive integer and let $s$ be a nonnegative integer, with $(r,s)\ne(1,0)$. The binary analo…

Let $\mathscr{D}^{\ell}$ be the set of addition-chain defects, and let $\mathscr{D}^{\ell}_{\mathrm{st}}$ denote its stable subset. For an ordinal $1\leq\alpha<\omega^\omega$, writ…

Addition-chain defect order-type conjecture. For each whole number $k$, the set $\mathscr{D}^{\ell}\cap[0,k]$ has order type $\omega^k$. This conjecture concerns the fine structure…

Scholz's conjecture reduction. The following inequality holds:

Order-type conjecture for addition chain defects. For each whole number $k$, the set $\mathscr{D}^\ell\cap[0,k]$ has order type $\omega^k$.

For a polynomial, consider the number of additions needed to compute its values at the first $N$ integers. Dobkin and Lipton proved a lower bound of $N+N^{2/3-\varepsilon}$ additio…

Scholz–Brauer's conjecture. For all $n\geq 1$,

Let $f^\ell(k)$ and $f^\ell_{\mathrm{st}}(k)$ be the lower-bound functions for ordinary and stable addition-chain defects, and let $f^*(k)$ and $f^*_{\mathrm{st}}(k)$ be the corres…

For a positive integer $n$, let $\nu_2(n)$ denote the number of $1$'s in its binary expansion, and let $s(n)$ denote the addition-subtraction chain length used in the paper. KnuthS…

An addition chain for a positive integer $n$ is a sequence $(a_0,a_1,,a_r)$ with $a_0=1$, $a_r=n$, and, for each $1\le k\le r$, some $0\le i,j<k$ satisfy $a_k=a_i+a_j$; its length…