2
$\begingroup$

I would like some general feedback on an experiment I have run in the field of addition chains.

An addition chain for target integer $n$ is defined as:

$$1=a_0<a_1<\cdots<a_r=n \text{ with } a_i=a_j+a_k,i>j\ge k\ge 0$$

We define $\ell(n)=r$ as the length of the smallest (optimal) chain for $n$. We split $r$ into large and small steps by saying $\lambda(n)=\lfloor\log_2(n) \rfloor$ is the number of large steps and $s(n)=\ell(n)-\lambda(n)$ is the number of small steps. We say that $v(n)$ is the digit sum of $n$ in binary.

The conjecture states that (though often stated in terms of $\ell(n)$)

$$v(n)\le 2^{s(n)}$$

This conjecture has been proved for $s(n)\le 3$ and the proof that $v(n)>9$ requires $s(n)>3$ is very large (140 pages in the PhD thesis of Ed Thurber).

I have put together a computer program than enumerates a finite set of s,t-multi-digraphs for a given $s(n)$ limit. Each graph represents an infinite number of addition chains with similar structure. Each vertex represents a base value in the chain and and number of doublings of that value that appear directly in the chain with no other values interspersed. So for example:

$$1\;2\;4\;8\;16\;32 \mid 40 \mid 42 \mid 43 \mid 85 \mid 127$$

The vertical bars separate the strings of doublings. We would represent this addition chain and others with similar structure with an $s$,$t$-graph with 6 vertices:

$1\to 2$, $1\to 2$, $2\to 3$, $1\to 3$, $3\to 4$, $1\to 4$, $4\to 7$, $3\to 7$, $7\to 10$, $3\to 10$

We label the vertices here with the number of paths from the source $s=1$.

From the graphs I generate path-edge incidence matrices. You can use the matrices (say $A$) to find the possible addition chain targets:

$Ax=b$ and $n=2^{b_1}+\cdots+2^{b_q}$ where $b_i$ are the elements of $b$. Each $b_i$ is an edge labeling sum of a path though the graph. So for the example above the edge-path incidence matrix is:

$$A=\left( \begin{array}{cccccccccc} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \end{array} \right) $$

Again in our example we can multiply $A$ by $\{5, 3, 0, 1, 0, 0, 0, 0, 0, 0\}^T$ yielding $\{5, 3, 1, 0, 5, 3, 1, 5, 3, 1\}^T$ To construct the target we have $2^5+2^3+2^1+2^0+2^5+2^3+2^1+2^5+2^3+2^1=127$.

After some thought you realize for an optimal addition chain for 127 which has s(127)=4 if the graph has 6 vertices then at least 2 of the larger powers of two must carry to a higher position. In the example $2^5+2^5=2^6=\lambda(127)$. So the code forms the column reduction of the matrix and enumerates all possible ways the upper bits can carry and still violate the conjecture ($2^5+2^5,2^5+2^4+2^4,2^5+2^4+2^3+2^3,2^3+2^3+2^3+2^3$). It then back substitutes into the matrix the upper bit values.

In order to know which rows can take on the larger bit values the code creates a partial order from the graph using the structure of the addition chain, symmetry and some rearrangements. Amazingly after substituting the program can always tell that there will be too many carries for the graph and the chains it represents to violate the conjecture. When you cause the upper bits to carry it forces bits elsewhere to carry as well. The program can handle the cases $s(n)=4,5$. Larger cases have too large a runtime currently.

This conjecture is important for the performance of the best known algorithms for calculating optimal addition chains. So I would like to use these results but need to be confident of them. It would obviously be nice to try and extract out of the algorithm a proof of the conjecture.

I am interested in the thoughts of people who have done experiments in the past and faced similar issues. How did you get confidence in the result, extract critical ideas for a proof, find people knowledgeable in other areas to collaborate etc?

My experience to date has mostly been finding contradictions to conjectures.

Update: The way I decided to get confidence in this enumeration was to shift to actually producing the different number types that could be reached by a particular small step count. These types can then be checked against the known data (roughly any number $n \le 2^{61}$ for $s(n) \le 6$). I have enumerated the case $s(n)=4$ and this is a new result.

$\endgroup$
8
  • $\begingroup$ What is the definition of a large/small step? Is the conjecture about EVERY addition chain of length $r(n)$, or just that there exists one that satisfies $v(n)\le 2^{s(n)}$? $\endgroup$
    – domotorp
    Sep 22 at 13:43
  • $\begingroup$ We split steps in an addition chain into large (or big) steps and small steps. We have $\lambda(n)=\left\lfloor log_{2}(n)\right\rfloor$ as the number of large steps in a chain for $n$. Small steps have $\lambda(a_i)=\lambda(a_{i-1})$ and large steps have $\lambda(a_i)=\lambda(a_{i-1}) + 1$ $\endgroup$ Sep 23 at 18:14
  • $\begingroup$ I have actually managed to enumerate all addition chains for numbers with 4 small steps (their actual formats rather than just the bit counts as described above). I have covered most of the five small step space (enough to know the bit counts of possible targets. Some details here: additionchains.com/SmallStepEnumeration.html $\endgroup$ Sep 23 at 18:16
  • $\begingroup$ I didn't answer the second part of the question. I have some details here: additionchains.com. Basically, the Knuth-Stolarsky conjecture applies to all addition chains. Hence it applies to optimal (or shortest addition chains) since they have smaller small step counts than non-optimal chains. $\endgroup$ Sep 23 at 18:23
  • 2
    $\begingroup$ Schonhage uses a completely different definition of large/small steps: doi.org/10.1016/0304-3975(75)90008-0 He says that a step is large if $j=k=i-1$. Anyhow, I think that you should make your definition clear and self-contained in your question, and point out that others use different definitions. Linking to this bound on Wikipedia can also help people understand the problem: en.wikipedia.org/wiki/Addition_chain#Chain_length $\endgroup$
    – domotorp
    Sep 25 at 4:22

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy