This post continues my series on favorite theorems of the 21st century. For an overview of the categories and my previous selections, see this earlier post. In the category “Between the Centuries” in Analysis, my choice is a remarkable theorem of Evertse, Schlickewei, and Schmidt (Evertse, Schlickewei, and Schmidt 2002), which gives an explicit upper bound on the complexity of the zero set of a linear recurrence sequence.
A central theme in analysis is the study of discrete-time dynamical systems, defined by iterates of a function . One of the simplest yet most fundamental cases occurs when is linear, leading to sequences defined by linear recurrences. Concretely, consider a sequence satisfying where and with . Such a sequence is called a linear recurrence of order . Given initial values , the recurrence uniquely determines for all . We shall assume throughout that the recurrence is minimal, meaning that the same sequence cannot be generated by a recurrence of smaller order.
One of the most basic and intriguing questions about a linear recurrence sequence is to describe its zero set, The classical Skolem–Mahler–Lech theorem asserts that is always a union of a finite set and finitely many arithmetic progressions. For decades, however, it remained an open problem to bound—in terms of the order alone—the size of this finite set and the number of arithmetic progressions that can occur. This problem was resolved in 2002 by Evertse, Schlickewei, and Schmidt for linear recurrences called “simple”.
Associated with is the companion polynomial If has only simple (complex) roots , then the recurrence is called simple. In this case the sequence admits an explicit closed form: where the coefficients are determined by the initial values .
Beyond its striking explicit bound, Theorem introduced powerful new techniques and initiated rapid subsequent progress. Soon after, Schmidt (Schmidt 2000) extended the result to general (not necessarily simple) linear recurrences, obtaining a bound , which is triply exponential in . In 2009, Amoroso and Viada (Amoroso and Viada 2009) improved the bound in Theorem to , and in 2011 they further refined Schmidt’s result, proving that the zero set of a general recurrence sequence is a union of at most arithmetic progressions (Amoroso and Viada 2011).
Despite these advances, many fundamental questions about the zero sets of linear recurrences remain open. The most famous is the Skolem problem, which asks whether there exists a general algorithm that, given a linear recurrence , decides whether for some . A positive solution would yield a complete effective description of . At present, however, the Skolem problem appears extremely difficult, and such an algorithm is known only in special cases—for instance, for recurrences of order , see (Vereshchagin 1985).