Proof of weak Scholz conjecture

From Wikipedia, the free encyclopedia

In mathematics, a weaker version of the Scholz conjecture about addition chains can be proven without advanced number theory. In fact, proving the inequality

l(2ⁿ − 1) ≤ 2n − 2

is simple, providing some basic observations are made.

First of all, every positive integer can be written in a unique way as a sequence of compositions of the functions

f(n) = 2n + 1

g(n) = 2n

at the point n=0. For example, to represent the integer 14, we would take g(f(f(f(0)))). For brevity, we could write 14 = gfff(0) or simply 14 = gfff.

Next, notice that this representation of an integer is equivalent to its binary representation in the following way: when the sequence is reversed (i.e. gfff becomes fffg), all g's replaced by zeros, and all f's replaced by ones, the resulting formula, when interpreted as a base-2 integer, is equal to the original integer. In our example, this means that 1110₂= 8 + 4 + 2 = 14.

Second of all, notice that the following easy relationships can be established:

(1) l(2n) ≤ l(n) + 1

(2) l(2n + 1) ≤ l(n) + 2

To establish (1), it suffices to notice that in an addition chain of length l(n) which contains n, 2n is a valid next member (because 2n = n + n). In this augmented sequence, the largest member is 2n and the length is

l(2n) = l(n) + 1,

because only one member has been added. Therefore, the maximum length needed is l(n) + 1.

To establish (2), notice that in the new addition chain for 2n with length l(2n), 2n + 1 can be added by adding 2n and 1- both members of the addition chain for 2n. Hence,

l(2n + 1) ≤ l(2n) + 1 ≤ l(n) + 2

(Note: These inequalities are not equalities in disguise. For example, l(7) = 4 but l(2*7 + 1) = l(15) = 5 ≠ 6 = l(7) + 2.)

Given the condition l(1) = 0, we can now calculate an upper bound on l(n) for ANY n. Why is this? Every positive binary integer begins with a 1, which is equivalent to the innermost function of our composition sequence always being f. From this and the fact that every integer is decomposable as a sequence of these compositions acting on 1, we can use our inequalities bounding l(f(n)) and l(g(n)) to calculate an upper bound. Let's try it for n=14:

l(1)=0

By inequation (2)

l(3) ≤ l(1) + 2 = 2

By inequation (2)

l(7) ≤ l(3) + 2 ≤ 2 + 2 = 4

By inequation (1)

l(14) ≤ l(7) + 1 ≤ 4 + 1 = 5

It turns out that the order of the compositions does not affect the upper bound, as it merely permutes the order of the 1s and 2s in the sum. Therefore, we can give an explicit upper bound for l(n) as

UB(l(n)) = d(2,0,n) + 2×(d(2,1,n) - 1)

where d(a,b,c) is the number of base-a digits of c that are equal to b.

In the case of n = 2^a − 1, we have exactly a ones and zero zeros in the binary expansion of n. Our explicit upper bound therefore gives

UB(l(2^a − 1)) = 0 + 2*(a − 1) = 2a − 2

or, in other words,

l(2ⁿ − 1) ≤ 2n − 2

which was the result to be shown.