Composition d’applications quasi-polynomiales

Niboucha, Razika; Salinier, Alain

Journal de théorie des nombres de Bordeaux, Tome 29 (2017) no. 2, pp. 569-601.

L’objet de ce travail est l’étude de la composition des applications quasi-polynomiales de $\mathbb{Z}$ dans $\mathbb{Z}$, et plus particulièrement des applications quasi-affines, définies comme les applications quasi-polynomiales de degré au plus 1. On montre que les applications quasi-affines correspondent aux endomorphismes continus de l’algèbre des suites reconnaissables indexées par $\mathbb{Z}$. On représente les applications quasi-affines par des suites finies d’entiers, et on donne les formules explicites sur ces suites traduisant la composition ou la réversion des fonctions quasi-affines. Enfin, est étudié un problème de coloriage équivalent à la caractérisation de telles suites pour des bijections quasi-affines.

The aim of this work is to study compositional properties of quasi-polynomial maps from $\mathbb{Z}$ to $\mathbb{Z}$, and more particularly of quasi-affine maps, namely quasi-polynomial maps of degree at most 1. We show that quasi-affine maps correspond to continuous endomorphisms of the algebra of recognizable bi-infinite sequences. We represent quasi-affine maps by means of finite sequences of integers, and we give explicit formulae on these sequences which translate composition or reversion of quasi-affine maps. Finally, we consider a coloring problem equivalent to the characterization of such sequences for quasi-affine bijections.

Classification : 11B37
Mots clés : Bijections entre entiers rationnels, coloriages, quasi-polynômes, suites récurrentes linéaires

[1] Aït-Mokhtar, Ahmed Endomorphismes d’algèbres de suites, Université de Limoges, France (2008) (Ph. D. Thesis)

[2] Aït-Mokhtar, Ahmed Applications purement semi-affines et tressages, C. R., Math., Acad. Sci. Paris, Volume 348 (2010) no. 1-2, pp. 1-4 | DOI

[3] Aït-Mokhtar, Ahmed; Necer, Abdelkader; Salinier, Alain Endomorphismes d’algèbres de suites, J. Théor. Nombres Bordx., Volume 20 (2008) no. 1, pp. 1-21 | DOI

[4] Benzaghou, Benali Algèbres de Hadamard, Bull. Soc. Math. Fr., Volume 98 (1970), pp. 209-252 | DOI

[5] Berstel, Jean; Reutenauer, Christophe Noncommutative rational series with applications, Encyclopedia of Mathematics and Its Applications, 137, Cambridge University Press, 2011, xiii+248 pages

[6] Bourbaki, Nicolas Eléments de mathématique. Algèbre Commutative. Chapitres 5 à 7, Springer, 2006, 351 pages

[7] Cayley, Arthur Researches on the Partition of Numbers, Philos. Trans. Roy. Soc. London, Volume 146 (1856), pp. 127-140 | DOI

[8] Chabert, Jean-Luc Anneaux de Fatou, Enseign. Math., Volume 18 (1972), pp. 141-144

[9] Comtet, Louis Analyse combinatoire. Tome 1, Le mathématicien, 4, Presses Universitaires de France, 1970, 192 pages

[10] Ehrhart, Eugene Polynômes arithmétiques et Méthode des Polyèdres en Combinatoire, International Series of Numerical Mathematics, 35, Birkhäuser, 1977, 165 pages

[11] Engelking, Ryszard General topology. A revised and enlarged translation, Monografie Matematyczne., 60, PWN-Polish Scientific Publishers, 1977, 626 pages

[12] Everest, Graham; van der Poorten, Alf; Shparlinski, Igor; Ward, Thomas Recurrence Sequences, Mathematical Surveys and Monographs, 104, American Mathematical Society, 2003, xiii+318 pages

[13] Hansel, Georges Une démonstration simple du théorème de Skolem-Mahler-Lech, Theor. Comput. Sci., Volume 43 (1986) no. 1, pp. 91-98 | DOI

[14] Larson, Richard G.; Taft, Earl J. The algebraic structure of linearly recursive sequences under Hadamard product, Isr. J. Math., Volume 72 (1990) no. 1-2, pp. 118-132 | DOI

[15] Niven, Ivan The asymptotic density of sequences, Bull. Am. Math. Soc., Volume 57 (1951) no. 6, pp. 420-434 | DOI

[16] Pólya, George Über ganzwertige ganze Funktionen, Palermo Rend., Volume 40 (1915), pp. 1-16 | DOI

[17] Schwartz, Laurent Analyse. 2e partie : Topologie générale et analyse fonctionnelle, Collection Enseignement des Sciences, 11, Hermann, 1970, 432 pages

[18] Stanley, Richard P. Enumerative combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, 49, Cambridge University Press, 1997, xi+326 pages (Corrected reprint of the 1986 hardback edition)