Title: Guessing with little data
| Speaker: | Manuel Kauers |
| Affiliation: | Johannes Kepler University |
| Zoom: | Please email Emma Watson |
Abstract:
A popular and powerful technique in experimental mathematics takes as input the first few terms of an infinite sequence and returns plausible candidates for recurrence equations that the sequence may satisfy. In a way, the search for such candidates is a generalization of polynomial interpolation. For polynomial interpolation, it is well known and easy to see that d+1 sample points are needed in order to recover a polynomial of degree d. Similarly, it turns out that (r+1)*(d+2) consecutive terms of a sequence are needed in order to detect a linear recurrence of order r with polynomial coefficients of degree at most d. In the talk, we will report on some ideas recently developed together with Christoph Koutschan about what can be done if not enough data points are known. These ideas are useful because for sequences that are not (yet) known to satisfy a recurrence, it can be very expensive to compute more terms.