Colloquium de Mathématiques :

Le 20 février 2014 à 15:00 - Salle TD 30 - RdC Bâtiment 9

Présentée par Adamczewski Boris - Université Claude Bernard Lyon 1 & CNRS

Quelques problèmes de décision autour du théorème de Skolem-Mahler-Lech

L'étude d'équations diophantiennes, typiquement la recherche des zéros entiers ou rationnels d'un polynôme de plusieurs variables à coefficients entiers, conduit naturellement à se poser les questions suivantes : l'équation possède-t-elle au moins une solution ? Une infinité de solutions ? Peut-on les trouver/décrire toutes ? Pour une famille donnée d'équations, on souhaiterait idéalement disposer d'un algorithme permettant de répondre à ces questions. Cette problématique se situe au confluent de l'informatique théorique et de la géométrie diophantienne, comme l'illustre la résolution du dixième problème de Hilbert. Le point de départ de l'exposé sera un énoncé diophantien classique et très élémentaire : le théorème de Skolem-Mahler-Lech. Il concerne les zéros des suites à valeurs complexes (ou plus généralement dans un corps de caractéristique nulle) qui vérifient une relation de récurrence linéaire à coefficients constants. Malgré sa simplicité apparente, ce résultat se trouve déjà à la frontière entre décidabilité et indécidabilité, et aucune démonstration effective n'en est connue. Lorsque le corps des nombres complexes est remplacé par un corps de caractéristique non nulle, comme par exemple un corps de fractions rationnelles à coefficients dans un corps fini, je montrerai que la situation est très différente. La théorie des automates finis permet alors de répondre aux trois questions fondamentales évoquées précédemment.