Lower Bounds for Lucas Chains
Martin Kutz · SIAM Journal on Computing · 2002
Lucas chains are a special type of addition chains satisfying an extra condition: for the representation a k = a j + a i of each element a k in the chain, the difference a j - a i must also be contained in the chain. In analogy to the relation between addition chains and exponentiation, Lucas chains yield computation sequences for Lucas functions, a special kind of linear recurrences. We show that the great majority of natural numbers n does not have Lucas chains shorter than $(1-\epsilon)\log_\phi n$ for any $\epsilon > 0$, where $\phi$ is the golden ratio. Peter L. Montgomery was the first to consider Lucas chains, in the early eighties. He discovered a decomposition theorem for Lucas chains and a lower bound on their length in terms of Fibonacci numbers. His work was not published. Therefore several of Montgomery's original ideas are represented in this paper.