DEFINITIONS AND NOTATIONS FOR ADDITION CHAINS

ACHIM FLAMMENKAMP

1. Introduction

An addition chain for a positive integer n is a finite ascending ordered sequence of natural numbers starting with 1 and ending with this n ∈ ℕ, i.e. 1 = a_{0} < a_{1} < … < a_{r} = n, such that each element except the first is the sum of two preceding elements of the chain. The length of an addition chain is by definition r. Formally:

Definition 1. A(n) is called an addition chain for n ∈ ℕ iff there is an r ∈ ℕ_{0} such that A(n)=(a_{0}, a_{1}, …, a_{r}) with a_{0} = 1 and a_{k} ∈ ℕ for all k with 1 ≤ k ≤ r and

(i) ∀ k with 1 ≤ k ≤ r ∃ i, j with 0 ≤ j < k and 0 ≤ i < k : a_{k} = a_{j} + a_{i} (ii) ∃ k′ with 0 ≤ k′ ≤ r : a_{k′} = n (iii) ∀ k with 1 ≤ k ≤ r : a_{k−1} < a_{k} (iv) ∀ j with 0 ≤ j < r and a_{j} ≠ n ∃ k with j < k ≤ r ∃ i < k : a_{k} = a_{j} + a_{i}

hold. Then r is unique and called the length of A(n).

Let ℓ(n) := min{r ∈ ℕ_{0} | ∃ A(n) of length r}. An addition chain A(n) is called a minimal addition chain iff its length is ℓ(n).

Condition (iv) is a restriction as practical as (iii), to ensure that an addition chain contains no superfluous elements with respect to generating n by Condition (i). Many people replace Conditions (ii) and (iv) by a_{r} = n and do not mention the technical difficulties which can arise from unneccessary elements of A(n) or the deeper concept of addition chains for sets S ⊂ ℕ. Therefore we state

Definition 2. A(S) is called an addition chain for S ⊂ ℕ iff there is an r ∈ ℕ_{0} such that A(n)=(a_{0}, a_{1}, …, a_{r}) with a_{0} = 1 and a_{k} ∈ ℕ for all k with 1 ≤ k ≤ r and

(i) ∀ k with 1 ≤ k ≤ r ∃ i, j with 0 ≤ j < k and 0 ≤ i < k : a_{k} = a_{j} + a_{i} (ii) ∀ s ∈ S ∃ k′ with 0 ≤ k′ ≤ r : a_{k′} = s (iii) ∀ k with 1 ≤ k ≤ r : a_{k−1} < a_{k} (iv) ∀ j with 0 ≤ j ≤ r and a_{j} ∉ S ∃ k with j < k ≤ r ∃ i < k : a_{k} = a_{j} + a_{i}

hold. Then r is unique and called the length of A(S).

Let ℓ(S) := min{r ∈ ℕ_{0} | ∃ A(S) of length r}. An addition chain A(S) is called a minimal addition chain iff its length is ℓ(S).

Notice that, there is no addition chain A(∅), according to Condition (iv) and we have always a_{r} = max S.

Both definitions are semantic definitions. But often it is preferable to have a syntatic definition which has no ambiguity in Condition (i). Hence let us give finally the syntatic definition for addition chains:

Definition 3. A(S) is called an addition chain for S ⊂ ℕ iff there is an r ∈ ℕ_{0} such that A(S)=((i_{1}, j_{1}), (i_{2}, j_{2}) …, (i_{r}, j_{r})) with (i_{k}, j_{k}) ∈ ℕ_{0}^{2} for all k with 1 ≤ k ≤ r and

(i) ∀ k with 1 ≤ k ≤ r : 0 ≤ i_{k} ≤ j_{k} < k Then let a_{0} := 1 and for all k with 1 ≤ k ≤ r we define a_{k} := a_{i_{k}} + a_{j_{k}}

inductively.

(ii) ∀ s ∈ S ∃ k′ with 0 ≤ k′ ≤ r : a_{k′} = s (iii) ∀ k with 1 ≤ k ≤ r : a_{k−1} < a_{k} (iv) ∀ h with 0 ≤ h ≤ r and a_{h} ∉ S ∃ k with h < k ≤ r : i_{k} = h or j_{k} = h

hold. Then r is unique and called the length of A(S).

A pair (i_{k}, j_{k}) is called a doubling, if i_{k} = j_{k} = k − 1 and it is called a star step if j_{k} = k − 1.

Definition 4. A(S) is called a star chain for S ⊂ ℕ iff it is an addition chain for S and — denoting as usual with r the length of this addition chain — for all k with 1 ≤ k ≤ r we have j_{k} = k − 1. I.e. each element of the addition chain is build up by the previous element and a further one.

Further, denote by ℓ^{∗}(S) the minimal length of all star chain for S. And finally,

Definition 5. A(S) is called a strong star chain for S ⊂ ℕ iff it is a star chain for S and — denoting as usual with r the length of this addition chain — for all k with 1 ≤ k ≤ r we have ℓ(a_{k}) = k. I.e. each element of the addition chain is build up as early as possible.

Definition 6. Call Δ(A(S)) := ∑_{k=1}^{r} k − ℓ(a_{k}) ∈ ℕ_{0} the excess of an addition chain A(S) for S ⊂ ℕ.

Obviously, if Δ(A(S)) = 0 then A(S) must be a strong star chain.

Definition 7. The associated graph G = (V, E) of an addition chain A(S) for S ⊂ ℕ is a directed graph with exactly one source (a vertex with in-degree 0) and |S| sinks (a vertex with out-degree 0). If r denotes the length of A(S), G has |V | = r + 1 vertices and |E| = 2r edges. The vertices of V correspond one-to-one to the elements a_{k} of A(S) and for each k with 1 ≤ k ≤ r there are two edges , one from v_{i_{k}} to v_{k} and one from v_{j_{k}} to v_{k}.

Hence, G has parallel edges and is connected and acylic. Further, each vertex except the source v_{0} has in-degree ≥ 2. Moreover, the number of pathes from the source to any vertex v_{k} equals a_{k} for all 1 ≤ k ≤ r. Using the syntatic definition of addition chains, there is always a unique associated graph.

Definition 8. The reduced graph G = (V, E) of an addition chain for S is a directed graph with exactly one source and |S| sinks. If h denotes the number of vertices in the associated graph G′ which have out-degree 1, the reduced graph G has |V | = r + 1 − h vertices and |E| = 2r − h edges. It may be constructed from the associated graph G′ by firstly deleting each vertex v with out-degree one together with its outgoing edge and then redirecting all edges of G′ which point to v to edges in G which point to the next sucessor of v which has out-degree ≥ 2.

Minimizing the quantity |E|−|V |+1 = r for a reduced graph G which has exactly n pathes from the source to its sink v_{r} means looking for a shortest addition chain of n. Addition chains which have the same reduced graph are called equivalent.

If we define ∀n ∈ ℕ

λ(n) := ⌊log_{2} n⌋

and

ν(n) := ∑_{i=0}^{λ(n)} ⌊\frac{n}{2^{i}} ⌋ − 2⌊\frac{n/2}{2^{i}}⌋

— ν(n) counts the 1-bits in the binary representation of n — then we get

λ(n) ≤ λ(n) + ⌈log_{2} ν(n)⌉ ≤ ℓ(n) ≤ ℓ^{∗}(n) ≤ λ(n) + ν(n) − 1 ≤ 2λ(n) .

The second term in this inequality chain is still conjectured and only proven for ν(n) ≤ 16. And the best known asymtotic which is valid for almost all n is

lim_{n→∞} ℓ(n) = λ(n)(1 + \frac{1}{λ(λ(n))}) + O(\frac{λ(n) · λ(λ(λ(n)))}{λ(λ(n))^{2}}) .

Definition 9. Each element a_{k} with 1 ≤ k ≤ r of an addition chain A(S) is called a small step, iff λ(a_{k}) = λ(a_{k−1}). Furthermore, denote by s(n) := ℓ(n) − λ(n) the number of small steps for each n ∈ ℕ.

The above conjecture would yield, for all n ∈ ℕ holds s(n) ≥ ⌈log_{2} ν(n)⌉ .

Definition 10. Let ∀ r ∈ ℕ_{0} (i) L(r) := {n ∈ ℕ | ℓ(n) = r} (ii) d(r) := #L(r) (iii) c(r) := min L(r)

and as approximation to c(r) define ξ(r) := ⌈\sqrt{ln2} · 2^{r− \frac{r}{log_{2} r}} ⌋ .

Trivially holds: max L(r) = 2^{r} for all r ∈ ℕ_{0}.

\begin{matrix}r & L(r) & d(r) & c(r) & ξ(r) \\ 0 & \{1\} & 1 & ∗ 1 & 1 \\ 1 & \{2\} & 1 & 2 & − \\ 2 & \{3, 4\} & 2 & ∗ 3 & 1 \\ 3 & \{5, 6, 8\} & 3 & 5 & 2 \\ 4 & \{7, 9, 10, 12, 16\} & 5 & ∗ 7 & 3 \\ 5 & \{11,13,14,15,17,18,...\} & 9 & 11 & 6 \\ 6 & \{… \} & 15 & 19 & 11 \\ 7 & \{… \} & 26 & ∗ 29 & 19 \\ 8 & \{… \} & 44 & 47 & 34 \\ 9 & \{… \} & 78 & 71 & 60 \\ 10 & \{… \} & 136 & ∗ 127 & 106 \\ 11 & \{… \} & 246 & 191 & 188 \\ 12 & \{… \} & 432 & 379 & 335 \\ 13 & \{… \} & 772 & 607 & 597 \\ 14 & \{… \} & 1382 & 1087 & 1066 \end{matrix}  \begin{matrix}r & d(r) & c(r) & ξ(r) \\ 15 & 2481 & ∗ 1903 & 1906 \\ 16 & 4490 & 3583 & 3410 \\ 17 & 8170 & 6271 & 6108 \\ 18 & 14866 & 11231 & 10953 \\ 19 & 27128 & 18287 & 19658 \\ 20 & 49544 & 34303 & 35316 \\ 21 & 90371 & ∗ 65131 & 63503 \\ 22 & 165432 & 110591 & 114283 \\ 23 & 303475 & 196591 & 205835 \\ 24 & 558275 & 357887 & 371014 \\ 25 & 1028508 & 685951 & 669238 \\ 26 & & 1176431 & 1208025 \\ 27 & & 2211837 & 2182044 \\ 28 & & ∗ 4169527 & 3943945 \\ 29 & & & 7132907 \end{matrix}

Table 1. Values L(r), d(r), c(r) and ξ(r) for r < 30. A ∗ preceding a number c(r) indicates that this is also the smallest n ∈ ℕ with s(n) > s(m) for all m < n.

4 ACHIM FLAMMENKAMP

Bielefeld, monday 1998-06-29.

Fakultät für Mathematik, Universität Bielefeld, 33501 Bielefeld, Germany, E-mail: achim@mathematik.uni-bielefeld.de