In
mathematics, the Scholz conjecture is a
conjecture on the length of certain
addition chain In mathematics, an addition chain for computing a positive integer can be given by a sequence of natural numbers starting with 1 and ending with , such that each number in the sequence is the sum of two previous numbers. The ''length'' of an additi ...
s.
It is sometimes also called the Scholz–Brauer conjecture or the Brauer–Scholz conjecture, after
Arnold Scholz
Arnold Scholz (24 December 1904 in Berlin – 1 February 1942 in Flensburg) was a German mathematician who proved Scholz's reciprocity law and introduced the Scholz conjecture.
Scholz participated in the Second Conference on the Epistemology ...
who formulated it in 1937 and
Alfred Brauer who studied it soon afterward and proved a weaker bound.
Statement
The conjecture states that
:,
where is the length of the shortest
addition chain In mathematics, an addition chain for computing a positive integer can be given by a sequence of natural numbers starting with 1 and ending with , such that each number in the sequence is the sum of two previous numbers. The ''length'' of an additi ...
producing ''n''.
Here, an addition chain is defined as a sequence of numbers, starting with 1, such that every number after the first can be expressed as a sum of two earlier numbers (which are allowed to both be equal). Its length is the number of sums needed to express all its numbers, which is one less than the length of the sequence of numbers (since there is no sum of previous numbers for the first number in the sequence, 1). Computing the length of the shortest addition chain that contains a given number can be done by
dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. ...
for small numbers, but it is not known whether it can be done in
polynomial time measured as a function of the length of the
binary representation
A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" (one).
The base-2 numeral system is a positional notation ...
of . Scholz's conjecture, if true, would provide short addition chains for numbers of a special form, the
Mersenne number
In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form for some integer . They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17th ...
s.
Example
As an example, : it has a shortest addition chain
:1, 2, 4, 5
of length three, determined by the three sums
:1 + 1 = 2,
:2 + 2 = 4,
:4 + 1 = 5.
Also, : it has a shortest addition chain
:1, 2, 3, 6, 12, 24, 30, 31
of length seven, determined by the seven sums
:1 + 1 = 2,
:2 + 1 = 3,
:3 + 3 = 6,
:6 + 6 = 12,
:12 + 12 = 24,
:24 + 6 = 30,
:30 + 1 = 31.
Both and equal 7.
Therefore, these values obey the inequality (which in this case is an equality) and the Scholz conjecture is true for the case .
Partial results
By using a combination of computer search techniques and mathematical characterizations of optimal addition chains, showed that the conjecture is true for all . Additionally, he verified that for all , the inequality of the conjecture is actually an equality.
References
{{Reflist
External links
Shortest addition chains*
OEIS sequence A003313
Addition chains
Conjectures
Unsolved problems in number theory