Petite introduction

Ma thèse s'intitule "Sur des propriétés stochastiques de la variation de la somme-des-chiffres en additionnant un entier fixé", elle est disponible en pdf ici. Dans celle-ci, je me suis intéressé à un problème lié à l'écriture des nombres. Ici, je vais me concentrer sur le système d'écriture binaire mais dans la thèse, j'ai travaillé avec d'autres systèmes de numération. De plus, j'étudie un problème lié à la fonction somme-des-chiffres, que je note \(s\), qui a un entier donné renvoie la somme des chiffres qui composent son écriture en base 2. Pour être bref, si je me fixe un entier \(r\) alors je me suis intéressé au comportement de la suite

Pour l'exemple également, je vais fixer \(r\) à 1. Pour commencer l'étude de \(\Delta^{(1)}\), je propose de calculer les premiers termes. Voici le rendu graphique des 100 premiers termes de \(\Delta^{(1)}\) en base 2 (Python).

On voit que beaucoup d'entiers vont prendre la valeur 1 par \(\Delta^{(1)}\) alors que peu d'entre eux vont prendre la valeur -4. Mais comment quantifier cette observation ? Assez naturellement, on se voit amené à s'intéresser à l'évolution de la proportion des entiers prenant une valeur atteignable par \(\Delta^{(1)}\) ou, autrement dit, à la quantité (pour un certain entier relatif \(d\))

En appliquant à l'exemple que je propose de suivre, cela donne

On peut conjecturer graphiquement que les proportions convergent en l'infini vers une valeur entre 0 et 1 que l'on notera \(\mu^{(1)}(d)\). Par exemple, on conjecture que \(\Delta^{(1)}\) prend la valeur 1 pour, en proportion, un entier sur deux (c'est à dire \(\mu^{(1)}(1)=\frac{1}{2}\)) ou la valeur 0 pour, en proportion, un entier sur 4 (c'est à dire \(\mu^{(1)}(0)=\frac{1}{4}\)). Notre conjecture pousse à tracer le diagramme en bâtons suivant, qui donne les valeurs de \(\mu^{(1)}\).

En vérité, la conjecture sur la convergence des proportions a été démontrée par des arguments d'arithmétiques (présence d'un nombre fini de suites arithmétiques dans les lignes de niveaux) dans les années 1970 par Jean Bésineau (son papier) avec une base entière et un entier \(r\) quelconques. Caché dans ses démonstrations, on peut discerner le lien entre l'étude des variations de la somme-des-chiffres et celle des créations de retenues pendant une addition dans le système d'écriture. En base entière, la valeur de la variation caractérise le nombre de retenues créées. Par conséquent, la variation peut prendre des valeurs aussi petites que l'on souhaite. Dans l'exemple que j'ai développé, la variation vaut 1 si et seulement l'addition avec 1 ne fait pas apparaître de retenues ; elle vaut 0 si et seulement si l'addition fait apparaître une retenue ; elle vaut -5 si et seulement si l'addition possède 6 retenues.

Mieux encore, Jean Bésineau donne un moyen de calculer les limites de ses proportions par une sorte de récurrence. En binaire, cela donne

C'est en fait une formule de récurrence où le nombre de chiffres de \(r\) diminue à chaque étape. En appliquant cette formule, on peut donc tracer plusieurs rendus graphiques de \(\mu^{(r)}\) en base 2 pour plusieurs choix de \(r\).

On peut conjecturer que le diagramme prend de plus en plus l'allure d'une courbe en cloche. Je nuance en précisant qu'en vérité les entiers servant dans l'animation (1, 3, 11, 375 et 489335) sont bien choisis car ils satisfont une relation que je cache pour l'instant. Un des objectifs de ma thèse est en fait de démontrer ce phénomène.

Une nouvelle approche (en binaire)

Le premier point a été de placer ce problème dans un cadre probabiliste. Il faut donc un espace d'états sur lequel je vais choisir des éléments uniformément au hasard. Étant donné la dépendance de notre problème au système de numération (binaire ici), il est naturel de considérer comme espace d'états, non pas \(\mathbb{N}\) sur lequel il est impossible de choisir uniformément au hasard, mais l'ensemble \(\mathbb{X} :=\{0,1\}^{\infty}\). C'est un ensemble qui généralise les entiers naturels écrits en base 2, mais avec une infinité de chiffres. Les éléments de cet ensemble sont appelés "entiers 2-adiques". L'ensemble \(\mathbb{X}\) est également muni d'une transformation naturelle pour notre problème et que l'on appelle "odomètre". Il s'agit de l'application \(T:\mathbb{X}\rightarrow \mathbb{X}\) qui a un élément \(x\) associe \(x+1\) où l'opération \(+\) est simplement la généralisation de l'opération d'addition existant sur les entiers naturels. Maintenant, comment choisir au hasard des éléments de \(\mathbb{X}\) ? C'est à dire, comment choisir au hasard une suite infinie de \(0\) et de \(1\) ? Il y a pleins de manières de procéder mais, pour refléter l'uniformité que l'on souhaite avoir, la bonne manière est de choisir chacun des termes de la suite identiquement et indépendamment : un terme a une chance sur deux de valoir \(1\) et une sur deux de valoir \(0\). Appelons cette probabilité \(\mathbb{P}\).

Il s'agit maintenant de voir \(\Delta^{(r)}\), non plus comme une suite définie sur \(\mathbb{N}\), mais comme une variable aléatoire sur \(\mathbb{X}\). Des arguments de théorie ergodique (notamment par l'usage de tour de Rokhlin) permettent de justifier que le pont que je construis entre le point de vue arithmétique et le point de vue probabiliste est très solide. En effet, dans la thèse, je montre que la limite des proportions précédemment évoquée est en fait la même quantité que la probabilité de cet évènement, c'est à dire que

Les mêmes arguments de théorie ergodique donnent que \(\Delta^{(r)}\) est à moyenne nulle et possède des moments finis de tous ordres.

Maintenant que je peux voir \(\Delta^{(r)}\) comme une variable aléatoire, je peux réfléchir à la conjecture énoncée tout à l'heure sur l'allure du diagramme bâton. On veut montrer que son allure ressemble de plus en plus à une courbe en cloche autrement à une loi normale. Pour cela, il faut que je fasse tendre quelque chose vers l'infini. Je pourrais, en premier lieu, penser que \(r\) serait l'élèment à faire tendre vers l'infini. Malheureusement, ce ne peut pas être le bon choix (\(\mu^{(2^n)}=\mu^{(1)}\) fournirait alors un contre-exemple). En second lieu, je pourrais penser au nombre de chiffre de \(r\) en binaire ? Idem, le même contre-exemple rend cela invalide. La bonne quantité à faire croître est en fait le nombre de blocs de \(1\) dans l'écriture binaire de \(r\). En effet, les nombres de l'animation (1, 3, 11, 375 et 489335) sont justement des nombres dont l'écriture en binaire contient de plus en plus de blocs de \(1\).