Systèmes de numération abstraits et coefficients binomiaux

En 2001, Michel Rigo et moi-même introduisions la notion de système de numération abstrait(*), vaste généralisation des systèmes de numérations « classiques », et en particulier des systèmes de numération de position à base entière.

Nous étions, entre autres, motivés par un remarquable, et difficile, théorème de A. Cobham selon lequel les ensembles de nombres simultanément reconnaissables(**) dans deux bases multiplicativement indépendantes sont exactement les unions finies de progressions arithmétiques (à rapprocher de nos bons vieux caractères de divisibilité).

Dans un système abstrait, les progressions arithmétiques sont également reconnaissables. Par contre, il n’y a pas de « base » et rien que la formulation d’une généralisation du théorème posait problème. Il n’a pas fallu moins de 10 ans pour obtenir cette généralisation, qui a nécessité un changement radical de cadre et de méthode pour voir le jour. En particulier, il a fallu reformuler les propriétés de reconnaissabilité en termes de substitutions, ce qu’ a bien compris Fabien Durand à qui l’on doit la forme la plus aboutie du théorème(***).

Durant ces dix années, les systèmes de numération abstraits ont fait l’objet de nombreuses recherches et ont progressivement gagné leurs lettres de noblesse. Au-delà des objectifs initiaux qui ont motivés leur introduction, ils se sont révélés être des outils efficaces pour résoudre certains problèmes. Je vais illustrer ceci dans ce billet à propos de la propriété suivante dans laquelle l>1 est un entier :

(1) Tout entier non négatif n s’écrit de façon unique sous la forme

n={m_1 \choose 1}+\cdots+{m_l \choose l}

avec 0\leqslant m_1<m_2<\cdots <m_l

Pour cela, je vais d’abord donner brièvement la définition d’un système de numération abstrait, vous renvoyant au chapitre 3 de Combinatorics, automata and number theory, Encyclopedia of Mathematics and its Applications, V. Berthé and M. Rigo ed., 135, Cambridge University Press, 2010, pour en savoir plus à leur propos ou encore à ces pages. Ensuite, je vous montrerai le système qui règle le problème comme expliqué dans (****).

Les systèmes de numération « classiques » ont ceci en commun que la fonction associant à un nombre sa représentation est strictement croissante, le langage des mots sur l’alphabet des chiffres de la numération étant ordonné selon l’ordre généalogique. En particulier, la numération est complètement déterminée par le langage formé des représentations de tous les nombres et, notamment, ne dépend nullement de tel ou tel algorithme utilisé éventuellement pour déterminer la représentation des entiers.

Je dois bien entendu rappeler la définition de l’ordre généalogique associé à un ordre donné sur un alphabet. Un ordre sur un alphabet se prolonge en un ordre sur l’ensemble des mots sur cet alphabet, dit généalogique : deux mots de longueurs différentes sont ordonnés selon celles-ci et deux mots de même longueur sont rangés comme la première lettre en laquelle ils diffèrent, étant lus de gauche à droite. Par exemple, en convenant que a<b alors aab<bbab car aab comporte une lettre de moins que bbab tandis que pour bab, bba qui sont de même longueur mais diffèrent dès la seconde lettre, on a bab<bba.

Un alphabet A étant muni d’un ordre <, un ensemble dénombrable L de mots sur cet alphabet peut être énuméré de façon croissante pour l'ordre généalogique : L=\{w_n|n\in \mathbb N\} avec

w_0<w_1<\ldots<w_k<\ldots

La donnée de S=(A,<,L) fournit ainsi un système de numération dans lequel la représentation \mathrm{rep}_S(n) de n\in \mathbb{N} est le mot w_n. L’application \mathrm{rep}_S: n\in\mathbb N \mapsto w_n\in L est une bijection strictement croissante. Sa réciproque \mathrm{val_S} associe à un élément de L sa valeur à savoir l’entier qu’il représente : \mathrm{val}_S(w_n)=n.

Lorsque L est un langage régulier sur A, on dit que S=(A,<,L) est un système de numération abstrait. Les systèmes de numérations S ne satisfaisant pas cette hypothèse sont, bien entendu, dignes d’intérêt — ils ont d’ailleurs déjà fait l’objet de quelques publications. Cependant, en vue d’une généralisation du théorème de Cobham, il nous fallait des sytèmes de numération dans lesquels les progressions arithmétiques sont reconnaissables. Or il se fait que la régularité de L est une condition nécessaire et suffisante pour que les progressions arithmétiques soient reconnaissables dans le système S. La nécessité de la condition est claire : \mathbb N est une progression arithmétique. La réciproque, par contre, est moins immédiate — c’est un vrai théorème.

Considérons alors le système abstrait SA=\{a_1,\ldots,a_l\} avec a_1<a_2<\cdots<a_l et

L=a_1^*\cdots a_l^*=\{a_1^{n_1}\cdots a_l^{n_l}|n_1,\ldots, n_l\in\mathbb N\}

On démontre dans (****) que

(2) \mathrm{val}_S(a_1^{n_1}\cdots a_l^{n_l})=\sum_{k=1}^l{n_k+\cdots+n_l+l-k\choose l-k+1}

La vérification de cette formule n’est pas bien compliquée mais elle repose sur certains faits relatifs aux systèmes de numération abstraits que je n’envisage pas d’exposer ici, faute de place. Le cas l=2 est particulièrement simple (voir ici par exemple).

Naturellement, (1) résulte immédiatement de (2).

😉

__________
(*) P. B. A. Lecomte, M. Rigo, Numeration systems on a regular language, Theory Comput Syst. 34 (2001), 27–44.
(**) Un ensemble de nombres est reconnaissable dans un système de numération si l'ensemble des représentations de ses éléments dans ce système est un langage régulier.
(***) F. Durand, Cobham’s theorem for substitutions, J. Eur. Math. Soc. 13(6) (2011), 1799-1814.
(****) E. Charlier, M. Rigo, W. Steiner, Abstract numeration systems on bounded langages and multiplication by a constant, INTEGERS, electronic journal of combinatorial number theory 8(1) (2008), A35.

Publicités

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s