Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
The Distribution of Extremal Values of Linear Recurrences Modulo
Speaker: John Miller, Johns Hopkins University
Date: Thursday, February 16, 2017 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Consider the Fibonacci sequence modulo m, e.g. modulo 10:
1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8,...
We can also start with different initial values, e.g. (3,4):
3, 4, 7, 1, 8, 9, 7, 6, 3, 9, 2, 1, 3, 4, 7, 1, 8, 9, 7, 6, 3, 9, 2, 1,...
This sequence has a cycle of length 12. The cycle lengths of such sequences are a classical subject related to algebraic number theory. We may also consider the "extremal values" of this sequence. For example, the 2nd sequence has minimum 1 and maximum 9. In this talk we will discuss the properties of such extremal values as we vary the initial values and the modulus, for the Fibonacci recurrence and for other examples of linear recurrences. We will do some experiments, and we will connect the distribution of extremal values to questions of elementary geometry. This talk arises out of work done in Professor Zeilberger's experimental mathematics class in the spring of 2012.