Proof of weak Scholz conjecture

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^"n" − 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)=0By inequation (2):"l"(3) ≤ "l"(1) + 2 = 2By inequation (2):"l"(7) ≤ "l"(3) + 2 ≤ 2 + 2 = 4By 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" − 2or, in other words,:"l"(2^"n" − 1) ≤ "2n" − 2which was the result to be shown.