Unbounded stability of two-term recurrence sequences modulo $2^k$
Walter Carlip, Eliot T. Jacobson · Acta Arithmetica · 1996
Introduction.Let a and b be fixed integers and let {u i | i ∈ N} be the two-term recurrence sequence defined by u 0 = 0, u 1 = 1, and u i = au i-1 + bu i-2 for all i ≥ 2. For any positive integer m, consider the sequence {u i } obtained by reduction modulo m.If m and b are relatively prime, then {u i } is known to be purely periodic, and therefore it is natural to ask how often each residue occurs in one period of the sequence.This question is surprisingly difficult to answer without restrictions.Even the prerequisite problem of determining the length of the (shortest) period as a function of a, b and m is, in general, beyond reach.Consequently, most authors who consider this question either settle for rough bounds on the maximum or minimum number of occurrences of each residue in one period ([7, 8]) or else severely restrict the sequences and moduli studied ([6, 5]).In this context it is no surprise that the present paper restricts a and b to selected congruence classes of odd integers and m to powers of two.However, the tradeoff for this austerity is a complete characterization of the distribution frequencies of {u i } modulo m.For a fixed two-term recurrence sequence, as defined above, and fixed modulus m and residue r, we denote the number of occurrences (i.e. the "frequency") of the residue r in one (shortest) period of {u i } by ν a,b (m, r) (or ν(m, r), when a and b are clear).The function ν(m, r) is called the frequency distribution function of {u i } modulo m.In the early 1970s, interest in the distribution functions of two-term recurrence sequences centered on the characterization of those sequences that have constant frequency distribution functions, i.e., those sequences that are