The most well-known example of a linear recurrence is the Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, ... in which each term after the second is the sum of the two preceding terms. More generally, a linear recurrence is a sequence of numbers (r_n) such that r_n = a_1 * r_{n-1} + ... + a_k * r_{n-k} for every integer n >= k, where a_1,…, a_k are fixed constants. Linear recurrences play an important role in both pure and applied mathematics. For example, the following objects can all be expressed as the nth term of a suitable linear recurrence: - the number of paths of length n between two vertices in a finite graph, - the coefficient of z^n in the Taylor expansion of a rational function of z, - the minimum number of moves to solve the Hanoi tower puzzle with n discs, - the number of ways to write n as an ordered sum of 1s and 2s, - the nth Chebyshev polynomial, - the probability that a discrete Markov chain returns to the initial state after n steps. This course provides an overview of the key properties and fundamental results on linear recurrences and shows their applications in various areas.

Basic linear algebra (matrices, vector spaces, linear maps) and basic algebra (fields, commutative rings, ideals). More advanced algebraic tools will be developed during the course.

The topics of the course are approximately the following. They might be slightly adapted depending on the audience. - Linear recurrences over an arbitrary field: the three main points of view (matrices, sums of powers, and rational generating functions), operations with linear recurrences (sum, product, and convolution). - Linear recurrences over a finite field: periodicity, maximum period sequences, uniform distribution. - Linear recurrences over a number field: the structure of the set of zeros (Skolem theorem), ratios of linear recurrences (Hadamard quotient theorem), growth and asymptotic. - Linear recurrences over the integers: prime values, prime factors, conjectures and heuristics. - Miscellaneous applications: pseudorandom number generators, combinatorics, graph theory, continued fractions, numeration system, diophantine equations.

In presenza

Presentazione orale

P.D.2-2 - Marzo