Addition Subtraction Chains

For mathematical definitions see the top-level Addition Chains.

An addition subtraction chain is a sequence of positive integers: \(1=a_0,a_1,...,a_r=n\) with \(a_i=|a_j\pm a_k|, i>j\ge k\ge 0\).

We say this chain for target \(n\) has length \(r\) and we denote the length of the smallest or optimum addition subtraction chain by \(l^-(n)\). Obviously, we have \(l^-(n)\le l(n)\).

Just like for addition chains we will define \(c^-(r)\) as the smallest number with an optimal addition subtraction chain length of \(r\). Hence \(l^-(c(r))=r\).

We denote by \(d^-(r)\) the number of optimal addition subtraction chains of length \(r\). See tables below.

The first problem to solve if we want to calculate some optimal addition subtraction chains is to get some kind of chain ordering.
We can't order the chain numerically as that would break the property that the chains are topologically sorted (elements used to construct an element are in the chain before it).
I saw this paper [1] using graph techniques for calculating optimal addition subtraction chains and I realized we can order the chain numerically assuming all the elements create by subtraction were really formed via addition.
You can make this rigorous by thinking about the total paths through the graph to a vertex from the vertex for 1. For ties we break the tie via the actual element value of the addition subtraction chain.
This minimal pruning let me calculate optimal addition subtraction chains for \(n\le 477780\). I basically let it run till windows update rebooted the machine.

You can see the data here: asc.txt.gz The format is each line has \(n\) followed by \(l^-(n)\).

I think a plan for anyone wanting to push this calculation further is to prove the Thurber Bounds [3] (or some modification of them) for addition subtraction chains. So, start by adding new entries to the table of one small step vector addition chains.
Then prove the bounds for each addition case.

Even though \(l^-(n)\) is a smoother function than \(l(n)\) (see [2] for the argument) we do see interesting structure. For example, the first case where \(l^-(2n)\le l^-(n)\) is for \(n=1389\).
We show the chains here:

1 2 4 8 16 32 64 128 256 512 448 464   463   926 1389
1 2 4 8 16 32 64   65 129 194 323 646 1292 2584 2778

Maybe this might make sense if we use Non-Adjacent Form (NAF, binary with the digits +1,0,-1). Negative digits are underlined. NAF never has adjacent digits so 11 -> 101, 11 -> 1.

1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000 1001000000 1001010000   1001010001   10010100010   101010010101
1 10 100 1000 10000 100000 1000000   1000001   10000001   101000010   101000101 1010001010 10100010100 101000101000 1010100101010

Maybe this case isn't interesting because \(l(1389)=l(2778)=14\) as well.

Let us try to construct something like the Scholz-Brauer conjecture. For this we have \(l(2^n-1)\le l(n)+n-1\). We can attempt to generalize this a bit by noting that \(l(n)=l(v(n))\) and \(\lambda(2^n-1)=n-1\).
So, we obtain \(l(2^n-1)\le l(v(2^n-1))+\lambda(2^n-1)\). The whole idea of the Scholz-Brauer was a number that had the maximal Hamming weight. We could try a high Hamming weight number in the NAF representation.
For example \({2^{2n}-1\over 3}\). From this we have the following conjecture:

\(l^-({2^{2n}-1\over 3})\le l^-(v({2^{2n}-1\over 3}))+\lambda({2^{2n}-1\over 3})\)
\(l^-({2^{2n}-1\over 3})\le l^-(n)+2n-2\)

We find the first interesting case with \(n=7\). We would expect \(l^-(5461)\le 16\). Like the original Scholz-Brauer we don't have equality since \(l^-(5461)=15\):

1 2 4 8 16 32 64 128 127 254 508 1016 1143 2159 4318 5461

In NAF:
1 10 100 1000 10000 100000 1000000 10000000 10000001 100000010 1000000100 10000001000 10010001001 100010010001 1000100100010 1010101010101

Table of \(c^-(r)\) Values

Table of \(d^-(r)\) Values

[1] Mihm, Nathan. "Optimal Addition-Subtraction Chains." https://www-users.cse.umn.edu/~reiner/HonorsTheses/Mihm_thesis.pdf
[2] Volger, Hugo. "Some results on addition/subtraction chains." Information Processing Letters 20.3 (1985): 155-160
[3] Thurber EG and Clift NM, "Addition chains, vector chains, and efficient computation", Discrete Mathematics, Volume 344, Issue 2, 2021,