Some results on addition/subtraction chains

Let ?(n) (respectively $\text{?}$(n)) be the length of the shortest addition chain respectively addition/subtraction chain for n. We shall present several results on $\text{?}$(n). In particular, we determine $\text{?}$(n) for all n satisfying $\text{s}\text{(}\text{n}\text{) ? 3}$ and show $\text{?}\text{log n}\text{? + 2 ?}\text{?}\text{(}\text{n}\text{)}$ for all n satisfying $\text{s}\text{(}\text{n}\text{) ? 3}$, where $\text{s}\text{(}\text{n}\text{)}$ is the extended sum of digits of n. These results are based on analogous results for ?(n) and on the following two inequalities: |n| ? 2^d?1F_f+3 < 2^k?b and $\text{f + b}\text{?}\text{log}\text{s}\text{(n)}$ for a chain of length k = d + f + b with d doublings, f short steps, and b back steps for n. Moreover, we show that the difference $\text{?(}\text{n}\text{)?}\text{?}\text{(}\text{n}\text{)}$ (respectively $\text{?}\text{(}\text{n}\text{)??}\text{log n}\text{?}$) can be made arbbitrarily large. In addition, we prove that $\text{?}\text{(}\text{m}\text{) ?}\text{?}\text{(?}\text{m}\text{) ?}\text{?}\text{(}\text{m}\text{) + 1}\text{for m}\text{> 0}$ and characterize the case $\text{?}\text{(?}\text{m}\text{) =}\text{?}\text{(}\text{m}\text{)}$. Finally, we determine $\text{?}{}_{\mathrm{<mtext>k</mtext>}}\text{(}\text{n}{}_1\text{,…,}\text{n}{}_{\mathrm{k}}\text{)}$, the k-dimensional generalization of $\text{?}$, with the help of $\text{?}\text{(}\text{n}{}_1\text{,…,}\text{n}{}_{\mathrm{k}}\text{)}$, the k-element generalization of $\text{?}$.