La fonction de Collatz sur (Z/2Z)[x] — Angelot Behajaina (Université de Lille)

Le problème de Collatz est un problème ouvert célèbre. Rappelons que la fonction de Collatz envoie tout entier pair n vers n/2 et tout entier impair n vers 3n + 1. La conjecture de Collatz prédit qu'en partant d'un entier positif n, après un nombre fini d'itérations de la fonction de Collatz, on atteint la valeur 1.

En 2008, Hicks, Mullen, Yucas et Zavislak ont étudié une variante de la fonction de Collatz pour les polynômes à coefficients dans Z/2Z. Cette variante envoie un polynôme f vers f/x si f(0) = 0, et vers (x + 1)f + 1 si f(0) = 1. Ils ont démontré qu'en partant d'un polynôme f non nul, on atteint le polynôme 1 en au plus O(deg(f)^2) itérations.

Dans un travail récent avec Gil Alon et Elad Paran, nous avons amélioré cette borne à O(deg(f)^(1.5)). Dans cet exposé, je vais esquisser une preuve de ce résultat et présenter quelques problèmes ouverts.