Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Teoria Automatów


The Skolem Problem for Simple Linear Recurrence Sequences

Prelegent: David Purser

2022-04-27 14:15

The Skolem Problem, asks to decide whether a linear recurrence sequence has a zero term. The Skolem-Mahler-Lech theorem states that the set of zeros of a linear recurrence sequence is the union of a finite set and finitely many arithmetic progressions. Although the result is almost 90 years old, the finite set is still not effective, so decidability of the Skolem Problem remains open. The talk will present an algorithm to solve the Skolem Problem for simple linear recurrence sequences (those without repeated characteristic roots). Whenever the algorithm terminates, it produces a certificate that its output is correct---either the zeros of the sequence or a witness that no zero exists. The algorithm terminates assuming two well-known number-theoretic conjectures: the Skolem Conjecture (also known as the exponential local-global principle) and the p-adic Schanuel conjecture.