^{1}

^{2}

^{3}

^{1}

This paper presents a brief demonstration of Schulz’s first conjecture, which sets the upper and lower limits on the length of the shortest chain of addition. Two methods of the upper limit are demonstrated; the second one is based on the algorithm of one of the most popular methods for obtaining addition chains of a number, known as the binary method.

With the development of the Internet and adding chain applications in the development of cryptography―which permits safe handling of data over the Internet―the theme began with the publication in 1937 of Arnold Scholz’s paper [

The first conjecture presented by Scholz was:

In addition to setting maximum and lower bounds for the minimum length of addition chains, this conjecture induces a partition of our study space, in this case the natural numbers. The bounded sets defined by Schulz

We will begin our discussion with the following definitions:

Definition 2.1. Let

I.

II.

Definition 2.2. Let

index of the sequence r is called length of the chain

Definition 2.3. The minimum length of all addition chains of a natural number e is denoted by

Definition 2.4. Let us consider the family

The set

Definition 2.5. For every ith generation with

Definition 2.6. For every

Proposition 3.1. The dominant chains are of maximum growth. That is to say, for every x if

Proof. As

same) in such a way that

Proposition 3.2. Dominant chains are addition chains defined on the numbers of the form

Proof. By definition

From the definition of dominant chain:

Let us have a look at the second property, that is:

clearly

Finally, since

To underline this last fact we will state the following in this corollary:

Corollary 3.3. The numbers of the form

Proof. The Proposition (3.2) assures that

Another important result:

Corollary 3.4. If

Proof. If

Proposition 3.5. If

Proof. If we assume that (3.5) is not true, then there exists

Proposition 3.6. If

Proof. As

Proposition 3.7. If

Proof. As x is an even number and lower than the upper limit of

Let

Proposition 3.8. If

Proof. By definition

such a way that

Proposition 3.9. For every

Proof. We have to demonstrate that for every

a)^{ }

b)

For

are true.

Proposition 3.10. The number 3 only has an addition chain of length equal to 2.

Proof. The only addition chain of the number 3 is:

It is an addition chain since it begins with 1, it has increasing terms and it ends with the number 3, from where it satisfies the property I of the definition of the chain addition.

Clearly

We will demonstrate now that it is unique. Let us suppose that it is not, then there exists

chain of the number 3. Let

tion of chain forces

The only possible value for

In terms of the given definitions, Scholz’s first conjecture is equivalent to:

If we make a change of variables

As

The new formulation would be:

Theorem 4.1. If

Proof. The Proposition (3.5) guarantees the first part of the inequality, that is: if

We will now demonstrate the second part of the inequality.

The Proposition (3.6) guarantees us that if

Let

As

which proves that if

An alternative way of deriving the upper bound established in Schulz’s first conjecture is obtainable by using the binary analysis methods for constructing the addition chains [

i | j | Comment | |
---|---|---|---|

0 | 0 | The sequence would not be strictly increasing | |

0 | 1 | Possible value | |

1 | 1 | The last value must be 3, there can’t be higher numbers |

Input: an integer:

Output: Addition chain

Start:

for i=1 to m

If

End

Therefore the length of the obtained chain depends on the length of the binary expression of the number and the quantity of ones that it has, as for each one, without taking into account the first one, is added another number to the output chain; for example see

Description | Example |
---|---|

Input: integer: e | 77 |

Write | 77 = 1001101 |

Output: Addition Chain U | |

While | While |

As | As |

Repeat: Step | As |

As | As |

As | As |

e_{i}’s equal to one. | As |

As | As |

The output chain has the same number of elements that the number of bytes of the expression, in base 2, of the input number e, plus the quantity of ones of the binary expression, minus one, which is at the beginning of the binary expression. In this case: 77 = 1001101, the length of the binary expression is of 7 bytes and the number of ones minus the first one is 3. Hence the length of the output chain is 7 + 3 = 10; U = {1, 2, 4, 8, 9, 18, 19, 38, 76, 77}. Therefore the length of the addition chain is 9. This fact is expressed in the next proposition, as follows:

Proposition 5.1. The length of the addition chain generated by the binary method of a number e is equal to the last sub-index of the binary expression

Proof: Take_{i}’s equal to one. Therefore, according to Definition 2.2 the length of the addition chain is equal to the last sub-index of the chain, in this case

Q.E.D.

Note that the numbers belonging to the generation G_{i}, for

Note that the upper bound of the generation is given by 2^{n}; its minimum addition chain is n, because of Proposition 3.2. Then we do not take i into account. The maximum expected length of a chain, belonging to the generation n, is given by the number whose binary expression is equal to n, corresponding to

Corollary 5.1. The length of the longest addition chain generated by the binary method in

Generation | Limits of the partition | Limits of the partition expressed in binary | Size of the partition | |||
---|---|---|---|---|---|---|

G_{0} | 1 | 1 | 1 | 1 | 1 | |

G_{1} | 2 | 2 | 10 | 10 | 1 | |

G_{2} | 3 | 4 | 11 | 100 | 2 | |

G_{3} | 5 | 8 | 101 | 1000 | 4 | |

G_{4} | 9 | 16 | 1001 | 10000 | 8 | |

G_{5} | 17 | 32 | 10001 | 100000 | 16 | |

G_{6} | 33 | 64 | 100001 | 1000000 | 32 | |

G_{7} | 65 | 128 | 1000001 | 10000000 | 64 | |

G_{8} | 129 | 256 | 10000001 | 100000000 | 128 | |

G_{9} | 257 | 512 | 100000001 | 1000000000 | 256 | |

G_{10} | 513 | 1024 | 1000000001 | 10000000000 | 512 | |

…. | ||||||

G_{n} | 2^{n}^{−1} | |||||

Theorem 5.1. The binary method for the generation of addition chains proofs the right hand side of the First Schulz’s Conjecture that is:

If

Proof. If

This fact proofs that all the chains generated with this method are not larger than

JoséM. Sautto,AgustínSantiago,Carlos N.Bouza,VerónicaCampos, (2016) Scholz’s First Conjecture: A Brief Demonstration. Applied Mathematics,07,70-76. doi: 10.4236/am.2016.71006