Sur la complexité des nombres algébriques
(Un exposé de Boris Adamczewski au séminaire de
théorie des nombres de Chevaleret le 7 juin 2004)
Résumé :
En 1950, E. Borel conjectura que le développement décimal de
$\sqrt{2}$ satisfait à certaines lois suivies par un nombre choisi au
hasard. Plus précisément, il est attendu que tout irrationnel algébrique
soit un nombre normal. Une mesure classique de la complexité d'une suite à
valeurs dans un ensemble fini consiste à compter le nombre $p(n)$ de mots
distincts de longueur $n$ qu'elle contient. Ainsi, la conjecture
précédente implique que, pour tout entier $b$, le développement $b$-adique
d'un nombre irrationnel algébrique doit etre de complexité maximale (i.e.,
$p(n)=b^n$).
En 1965, J. Hartmanis and R. E. Stearns ont proposé une approche
alternative de la notion de complexité pour les nombres réels en
développant l'aspect quantitatif de la notion de calculabilité introduite
par A. M. Turing. Les nombres réels les plus simples en ce sens sont dits
calculables en temps réel. Le problème de Hartmanis-Stearns, auquel une
réponse négative est attendue, est le suivant : existe-t-il des nombres
algébriques irrationnels calculables en temps réel?
Bien que ces deux conjectures soient considérées comme totalement hors
d'atteinte, nous présenterons quelques résultats très partiels obtenus a
l'aide du théorème des sous-espaces de W. M. Schmidt.