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.
