The Skolem Problem for Simple Linear Recurrence Sequences

Prelegent(ci)

David Purser

Afiliacja

MIM UW

Termin

27 kwietnia 2022 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

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.

---