Semigroupes numériques et nombre d’or (II)

Piste rouge Le 21 juin 2018  - Ecrit par  Shalom Eliahou, Jean Fromentin Voir les commentaires

Voici la suite de l’article Semigroupes numériques et nombre d’or (I) paru en mars 2018 dans cette rubrique.

Semigroupes numériques : petit rafraîchissement de mémoire

Rappelons qu’on dénote $\mathbb{N}=\{0,1,2,\dots\}$ l’ensemble des nombres entiers positifs ou nuls, et qu’un semigroupe numérique est un sous-ensemble $S$ de $\mathbb{N}$ contenant $0$ et satisfaisant les deux conditions suivantes :

  • $S$ est stable par addition : la somme de deux éléments de $S$ est toujours un élément de $S$.
  • L’ensemble des trous de $S$, c’est-à-dire des éléments de $\mathbb{N}$ qui n’appartiennent pas à $S$, est fini.

Le semigroupe numérique le plus simple est $\mathbb{N}$ lui-même, qui satisfait les deux conditions requises sans le moindre effort. De nombreux autres exemples sont donnés dans Semigroupes numériques et nombre d’or (I).

Puisqu’un semigroupe numérique $S$ n’a qu’un nombre fini de trous, il a un plus grand trou. Ce plus grand trou s’appelle le nombre de Frobenius de $S$ et est dénoté par le symbole $f(S)$, ou parfois simplement $f$. Posons $c=f+1$. Comme $f$ est le plus grand trou de $S$, il suit que $S$ contient non seulement $c$ mais aussi tous les entiers supérieurs à $c$.

On peut ainsi décrire $S$ sous la forme

\[ S = \{s_1,s_2,\dots,s_k, c, \to\} \]

où $s_1, s_2, \dots,s_k$ est la liste des éléments de $S$ qui sont inférieurs à $c$, et où le symbole $\to$ à droite de $c$ signifie qu’à partir de $c$, tous les nombres $c,c+1,c+2,\dots$ sont dans $S$.

On appelle genre de $S$ le nombre de trous de $S$. Par exemple, le genre de $\mathbb{N}$ est $0$ puisque $\mathbb{N}$ n’a pas de trous. Dans la partie (I), on avait constaté que pour un entier naturel $g$ donné, il n’y a qu’un nombre fini de semigroupes numériques de genre $g$. Ce nombre est dénoté par le symbole $n_g$.

Trois questions

Nous aborderons ici trois questions spécifiques :

  • Comment construire tous les semigroupes numériques de genre $g$ donné ?
  • Comment se comporte la suite des $n_g$ ?
  • Comment se comparent deux termes successifs $n_g$ et $n_{g+1}$ ?

L’arbre des semigroupes numériques

Au début des années 2000, des chercheurs espagnols ont découvert que, de façon remarquable, l’ensemble de tous les semigroupes numériques peut être organisé en un superbe arbre mathématique [1]. Cet arbre est d’ailleurs loin d’avoir livré tous ses secrets. Voici un aperçu de ses cinq premiers niveaux, dans toute leur splendeur mystérieuse. Nous reprendrons et commenterons cette image plus bas.

Un procédé algorithmique, évoqué plus bas, permet de construire successivement tous les niveaux de cet arbre, et donc tous les semigroupes numériques par genre croissant.

Le père

Comme tout arbre généalogique, l’arbre des semigroupes numériques est défini à partir d’un lien de parenté.

Dans le cas présent, tout semigroupe numérique $S$ de genre $g \ge 1$, donc différent de $\mathbb{N}$, est contenu dans un semigroupe numérique bien défini $S'$ avec un trou en moins, c’est-à-dire de genre $g-1$ : pour remonter de $S$ à $S'$, il suffit de « boucher le plus grand trou » de $S$, autrement dit d’adjoindre à $S$ son nombre de Frobenius $f(S)$. On appelle $S'$ le père de $S$. Et bien sûr, dans l’arbre, on met une arête entre $S$ et $S'$.

Répétons ce que l’on vient de dire, mais de façon un peu plus formelle, et profitons-en pour en donner une démonstration accessible en cliquant sur le bloc déroulant ci-dessous. Zapper cette démonstration ne nuit en rien à la compréhension de la suite de l’article.

Proposition. Pour tout semigroupe numérique $S$ de genre $g$ non-nul, l’ensemble $S'$ obtenu en adjoignant à $S$ son plus grand trou est un semigroupe numérique de genre $g-1$. En notation mathématique, $S'=S\cup\{f(S)\}$. C’est le père de $S$ dans l’arbre.

Démonstration

Comme $S'$ contient $S$ et que $S$ contient $0$ par hypothèse, il en est de même pour $S'$. Comme $S'$ a un trou de moins que $S$ et que $S$ n’a qu’un nombre fini de trous, là encore il en est de même pour $S'$. Reste à montrer que $S'$ est stable par addition. Notons $f$ et $f'$ les plus grands trous respectifs de $S$ et $S'$. Comme $S'$ contient $S$, on a $f' < f$. Soient $x$ et $y$ deux éléments de $S'$, et posons $z=x+y$. On doit montrer que $z$ appartient aussi à $S'$. Il y a trois cas à considérer.

  • Si $x$ et $y$ sont dans $S$, alors $z$ l’est aussi par hypothèse, et donc $z$ appartient bien à $S'$.
  • Si $x$ n’appartient pas à $S$, alors forcément $x=f$ puisque $f$ est l’unique élément de $S'$ qui n’est pas dans $S$. On a donc $z\geq f >f'$. Comme $f'$ est le plus grand trou de $S'$, il suit que $z$ appartient bien à $S'$.
  • Si $y$ n’appartient pas à $S$, un raisonnement entièrement symétrique montre là encore que $z$ appartient à $S'$.

L’ensemble $S'$ est donc bien un semigroupe numérique de genre $g-1$. CQFD.

L’ensemble $\mathbb{N}$ des entiers positifs ou nuls est l’unique semigroupe numérique de genre $0$. C’est aussi le seul à ne pas avoir de père. Bref, c’est l’ancêtre commun à tous les semigroupes numériques.

Les enfants

Maintenant que nous savons construire le père d’un semigroupe numérique donné $S$, juste en bouchant son plus grand trou, peut-on renverser la construction et construire tous les enfants de $S$ ?

Oui, c’est tout à fait faisable : tout enfant de $S$ s’obtient en supprimant un élément $x$ de $S$

  • supérieur à son nombre de Frobenius $f(S)$,
  • et satisfaisant la condition naturelle que le résultat de cette suppression soit encore un semigroupe numérique.

Très peu d’éléments $x$ sont éligibles en général, parfois même aucun, comme dans le cas $\{0,3,4,6,\to\}$. Ce processus étant un peu technique, nous ne le détaillerons pas plus ici.

Par exemple, si l’on part de $\mathbb{N}$, le seul de ses éléments que l’on peut supprimer sans violer les deux conditions de semigroupes numériques, c’est $x=1$. Donc $\mathbb{N}$ a un seul enfant, à savoir $S = \{0,2,3,4,\dots\} = \{0, 2, \rightarrow\}$, comme on le voit sur l’image de l’arbre.

Reprenons cette image, justement. Pour chaque semigroupe numérique $S$, ses enfants sont situés en dessous de lui, et lui sont liés par des arêtes puisqu’il en est le père. Le nombre en bleu sur chaque arête indique quel élément de $S$ on a supprimé pour obtenir l’enfant $T$ correspondant. Symétriquement, ce nombre en bleu est le nombre de Frobenius de $T$, à lui adjoindre pour remonter à son père $S$.

Comptage

La racine de l’arbre est $\mathbb{N}$, dont on rappelle qu’il est de genre $0$ puisqu’il n’a pas de trous. Ainsi, dans cet arbre, les semigroupes numériques de genre $g$ sont exactement la $g$-ème génération des descendants de $\mathbb{N}$, et constituent donc le niveau $g$ de l’arbre.

Comme rappelé plus haut, le symbole $n_g$ désigne le nombre de semigroupes numériques de genre $g$. Le comportement de $n_g$ lorsque $g$ grandit reste très mystérieux, mais il montre quand même une certaine régularité asymptotique, lorsque $g$ tend vers l’infini.

Jusqu’à il y a dix ans, on ne connaissait la valeur exacte de $n_g$ que jusqu’au genre $g=14$. Puis en 2008, Maria Bras-Amorós, une jeune chercheure espagnole, a entrepris de déterminer ces nombres par ordinateur aussi loin que possible [2]. Remarquablement, elle est arrivée jusqu’au genre $g=50$.

Cette performance a ensuite motivé d’autres chercheurs à tenter d’aller plus loin. La limite des connaissances actuelles [3] est le genre $g=70$, pour lequel on trouve $n_{70} \approx 1.607 \times 10^{15}$. Voici pour illustration quelques valeurs exactes de la suite des $n_g$.

\[ \begin{array}{rr} g&n_g\\ 0&1\\ 1&1\\ 2&2\\ 3&4\\ 4&7\\ 5&12\\ 6&23\\ 7&39\\ 8&67\\ 9&118\\ 10&204\\ 20&37\,396\\ 30&5\,646\, 773\\ 40&774\,614\,284\\ 50&101\,090\,300\,128\\ 60&12\,841\,603\,251\,351\\ 70&1\,607\,394\,814\,170\,158 \end{array} \]

À ce jour, pour $g$ donné, le seul moyen connu de déterminer $n_g$ est d’explorer entièrement l’arbre des semigroupes numériques jusqu’au niveau $g$.

Trois conjectures

Dans son article de rupture de 2008, l’observation attentive des résultats obtenus a amené Maria Bras-Amorós à formuler trois conjectures frappantes sur le comportement des $n_g$, établissant même un lien complètement inattendu avec la suite de Fibonacci ! Ses magnifiques conjectures ont donné lieu à de nombreux travaux de recherche ultérieurs pour tenter de démontrer leur validité.

Voici les trois conjectures formulées par Maria Bras-Amorós dans [4].

Conjecture 1. Pour tout genre $g$, on a $n_{g+2}\geq n_{g+1}+n_{g}$.

Conjecture 2. Le rapport $\displaystyle \frac{n_{g+1}+n_{g}}{n_{g+2}}$ tend vers $1$ lorsque $g$ tend vers l’infini.

Conjecture 3. Le rapport $\displaystyle \frac{n_{g+1}}{n_g}$ tend vers le nombre d’or $\displaystyle \phi = \frac{1+\sqrt5}2\approx1.618$ lorsque $g$ tend vers l’infini.

Vous avez dit Fibonacci ?

On rappelle que la suite de Fibonacci $F_n$ est définie par
\[ \begin{eqnarray*} F_0 & = & 0 \\ F_1 & = & 1 \\ F_n & = & F_{n-2}+F_{n-1} \,\,\, \text{ pour } n \ge 2. \end{eqnarray*} \]
Elle est dotée d’innombrables propriétés et fait l’objet de plusieurs articles sur ce site. Voir par exemple Mystères arithmétiques de la suite de Fibonacci. Cette suite célèbre est intimement liée au nombre d’or $\phi$. À ce sujet, voir Le nombre d’or en mathématiques, toujours sur ce site. En particulier, il est bien connu que le rapport $\displaystyle \frac{F_{g+1}}{F_g}$ tend vers $\phi$ lorsque $g$ tend vers l’infini. À comparer avec la Conjecture 3 ci-dessus !

Il semble donc bien y avoir un lien entre les suites $n_g$ et $F_g$. Alors regardons-les de plus près et comparons-les. On a
\[ n_0=1=F_1\quad\text{et}\quad n_1=1=F_2. \]

Si la Conjecture 1 est vraie, elle implique que la suite des $n_g$ croît au moins aussi vite que la suite de Fibonacci. Cela est bien confirmé par les quelques valeurs numériques de $n_g$, de $F_{g+1}$ et du quotient $\displaystyle \frac{n_g}{F_{g+1}}$ données dans le tableau ci-dessous.

\[ \begin{array}{rrrr} g &n_g&F_{g+1}&{\large\frac{n_g}{F_{g+1}}}\\ 0 & 1 & 1 & 1\\ 1 & 1 & 1 & 1\\ 2 & 2 & 2 & 1\\ 3 & 4 & 3 & 1,33\\ 4 & 7 & 5 & 1,40\\ 5 & 12 & 8 & 1,50\\ 6 & 23 & 13 & 1,77\\ 7 & 39 & 21 & 1,86\\ 8 & 67 & 34 & 1,97\\ 9 & 118 & 55 & 2,15\\ 10 & 204 & 89 & 2,29\\ 20 & 37\,396 & 10\,946 & 3,42\\ 30 & 5\,646\, 773 & 1\,346\,269 & 4,19\\ 40 & 774\,614\,284 & 165\,580\,141 & 4,68\\ 50 & 101\,090\,300\,128 & 20\,365\,011\,074 & 4,96\\ 60 & 12\,841\,603\,251\,351 & 2\,504\,730\,781\,961 & 5,13\\ 70 & 1\,607\,394\,814\,170\,158 & 308\,061\,521\,170\,129 & 5,22 \end{array} \]

Le rapport $\displaystyle \frac{n_g}{F_{g+1}}$ semble augmenter avec $g$, mais comment se comporte-t-il pour $g$ très grand ? Voici une représentation graphique très suggestive de ce rapport.

Comportement asymptotique

Ce graphique suggère fortement, en effet, que le rapport $\displaystyle \frac{n_g}{F_{g+1}}$ tend à se stabiliser vers une limite finie lorsque $g$ tend vers l’infini. Cela conduit à énoncer une nouvelle conjecture.

Conjecture 4. Le rapport $\displaystyle \frac{n_g}{F_{g+1}}$ tend vers une limite finie lorsque $g$ tend vers l’infini.

Comme la suite $\displaystyle \frac{F_{g+1}}{F_g}$ tend elle-même vers le nombre d’or $\phi$ lorsque $g$ tend vers l’infini, cela donne l’équivalence entre les Conjectures 3 et 4.

Ça, c’était l’état des connaissances en 2013. Or cette année-là, Alex Zhai, un jeune mathématicien travaillant aux Etats-Unis, a fait des progrès très intéressants sur ces questions [5]. En effet, dans un article de 30 pages hélas plutôt obscur [6], il a démontré le résultat suivant.

Théorème. Le rapport $\displaystyle \frac{n_g}{\phi^g}$ tend vers une limite finie lorsque $g$ tend vers l’infini.

Ce résultat remarquable entraîne la validité des Conjectures 2, 3 et 4.

À propos de la Conjecture 1

Par contre, le mystère reste entier à l’heure actuelle en ce qui concerne la Conjecture 1. Les valeurs connues des $n_g$ montrent que la relation conjecturée
\[ n_{g+2} \ge n_{g+1}+n_{g} \]
est bien vraie jusqu’à $g=68$. Mais on ne sait toujours pas démontrer qu’elle est vraie pour tout $g$ !

Pire, on ne sait même pas démontrer que la suite des $n_g$ est croissante. Autrement dit, on ne sait même pas établir la relation
\[ n_{g+1}\geq n_g \]
pour tout $g$. Les résultats de Zhai entraînent que cette relation est bien vraie pour $g$ suffisamment grand, mais on voudrait la prouver pour tout $g$. On reste donc avec une nouvelle conjecture sur les bras, plus faible que la Conjecture 1, mais tout aussi coriace semble-t-il.

Conjecture 5. Pour tout genre $g$, on a $n_{g+1}\geq n_g$.

Les seuls résultats disponibles à ce sujet sont des encadrements des nombres $n_g$. Le meilleur actuellement connu a été obtenu en 2010 par Sergi Elizalde
dans [7]. Plus précisément, il introduit deux suites $a_g$ et $b_g$ vérifiant
\[ a_g\leq n_g\leq b_g \]
pour tout $g\geq 0$.

Nous ne détaillerons pas ces deux suites ici. Mais un graphique donnera une idée de l’encadrement obtenu. La croissance de ces suites étant exponentielle, c’est leurs logarithmes qu’on a représentés pour y voir plus clair. Le graphique suivant représente les valeurs de $\color{red}{\log(a_g)}$, $\color{blue}{\log(n_g)}$ et $\color{green}{\log(b_g)}$.

Malheureusement, on n’a pas $b_g\leq a_{g+1}$ pour tout $g$. La Conjecture 5, et a fortiori la Conjecture 1, restent donc ouvertes à ce jour.

Post-scriptum :

Les auteurs remercient les relecteurs de pseudonymes respectifs Cidrolin, Bedaride Nicolas et Himynameisarno, ainsi que Bruno Martin, pour leur relecture attentive et leurs commentaires très pertinents et constructifs.

Article édité par Shalom Eliahou

Notes

[1Rosales, J.C., García-Sánchez, P.A., García-García, J.I. and Madrid, J.A.J., The oversemigroups of a numerical semigroup, Semigroup Forum vol. 67 (2003) pp. 145–158.

[2Maria Bras-Amorós, Fibonacci-like behavior of the number of numerical semigroups of a given genus, Semigroup Forum vol. 76 (2008) pp. 379–384.

[3Jean Fromentin and Florent Hivert, Exploring the tree of numerical semigroups, Mathematics of computation vol. 85 (2016) pp. 2553–2568.

[4Maria Bras-Amorós, Fibonacci-like behavior of the number of numerical semigroups of a given genus, Semigroup Forum vol. 76 (2008) pp. 379–384.

[5A. Zhai, Fibonacci-like growth of numerical semigroups of a given genus, Semigroup Forum vol. 86 (2013) pp. 634–662. La prépublication correspondante est accessible publiquement ici.

[6L’auteur lui-même dit dans sa conclusion, traduite ici en français : « Finalement, la preuve du Lemme 3 donnée ici [...] est assez compliquée. [...] On espère qu’en améliorant les techniques utilisées dans cet article, des simplifications significatives de la preuve sont possibles. ». De façon générale en recherche mathématique, pour comprendre à fond un théorème déjà démontré, on essaie souvent d’en trouver de nouvelles preuves aussi transparentes que possible. Cette démarche est d’ailleurs une étape essentielle sur la voie de la découverte de nouveaux théorèmes.

[7S. Elizalde, Improved bounds on the number of numerical semigroups of a given genus, Journal of Pure and Applied Algebra vol. 214 (2010) pp. 1862–1873.

Partager cet article

Pour citer cet article :

Jean Fromentin, Shalom Eliahou — «Semigroupes numériques et nombre d’or (II)» — Images des Mathématiques, CNRS, 2018

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM