Introduction

Les semigroupes numériques sont des objets mathématiques fascinants, à l’origine de nombreux défis mathématiques malgré leur apparente simplicité. À titre d’illustration, l’article Semigroupes numériques et conjecture de Wilf sur ce site présente l’une des plus fameuses conjectures à leur sujet, la conjecture de Wilf, qui résiste encore et toujours à tous les efforts de résolution depuis sa formulation par Herbert Wilf en 1978.

Dans cet article, nous nous intéresserons à des conjectures plus récentes et plus élémentaires, mais tout aussi redoutables. De façon très surprenante, elles font intervenir la suite de Fibonacci et le nombre d’or.

Que la présence de quelques symboles et opérations élémentaires n’effraie pas le lecteur : pour aborder l’article, il suffit essentiellement de savoir compter.

Semigroupes numériques

Commençons par rappeler la définition même de ces objets. Un semigroupe numérique est un ensemble $S$ d’entiers positifs vérifiant les trois conditions suivantes :

• $S$ contient $0$.
• La somme de deux éléments quelconques de $S$ appartient toujours à $S$.
• $S$ contient presque tous les entiers positifs, c’est à dire tous sauf un nombre fini d’entre eux.

Pour résumer la deuxième condition, on dira simplement que $S$ est stable par somme.

Les quelques entiers positifs qui ne sont pas dans $S$ sont appelés les trous de $S$. On notera $\overline{S}$ l’ensemble des trous de $S$. La troisième condition assure que $\overline{S}$ est fini.

Exemples et contre-exemples

Voici quelques exemples et contre-exemples qui permettront de mieux maîtriser cette notion.

• L’ensemble $\mathbb{N}=\{0,1,2,3,4,\dots\}$ de tous les entiers positifs est le plus simple des semigroupes numériques : il contient $0$, il est stable par somme, et l’ensemble $\overline{\mathbb{N}}$ des trous de $\mathbb{N}$ est vide, donc fini comme requis.

• L’ensemble $A=\{0,2,3,4,5, \dots\}$ de tous les entiers positifs sauf $1$, est-il un semigroupe numérique ? Pour le savoir, passons en revue les trois conditions. Cet ensemble contient bien $0$ ; il est stable par somme, comme cela est facile à vérifier ; et enfin, il n’admet qu’un seul trou, à savoir $1$. C’est donc bien un semigroupe numérique, puisqu’il satisfait les trois conditions requises.

• Notons $I = \{1,3,5,7,9,\dots\}$ l’ensemble de tous les entiers positifs impairs. Comme cet ensemble ne contient pas $0$, il viole déjà la première condition et n’est donc pas un semigroupe numérique. En fait il ne satisfait pas non plus les deux autres conditions, puisqu’il n’est pas stable par somme et qu’il a un nombre infini de trous, à savoir l’ensemble $P =\{0,2,4,6,8,\dots\}$ de tous les entiers positifs pairs.

• Et l’ensemble $P$ ci-dessus est-il, lui, un semigroupe numérique ? Presque ! Les deux premières conditions sont satisfaites : il contient $0$, et la somme de deux nombres pairs est toujours un nombre pair. Par contre la troisième ne l’est pas, puisque l’ensemble des trous de $P$ est $\overline{P}=I$ et que $I$ est infini. Donc $P$ n’est pas un semigroupe numérique.

• Soit $S$ l’ensemble constitué des entiers positifs
  \[0,4,7,8,11,12,14,15,16,17,18,19,...\]
  Autrement dit, $S$ contient quelques petits entiers positifs sporadiques, à savoir $0, 4, 7, 8, 11, 12$, et puis il contient tous les entiers positifs à partir de $14$. Pour une notation plus concise [1], on écrira simplement
  \[S=\{0,4,7,8,11,12,14,\rightarrow\}.\]
  Le symbole $\rightarrow$ signifie ici que tous les entiers positifs à partir de $14$ sont aussi dans $S$. On peut aussi représenter $S$ graphiquement de la façon suivante :

On vérifie sans trop de difficultés que cet ensemble $S$ est un semigroupe numérique : par exemple $4+4=8$, $4+7=11$, $4+8=12$, $7+7=14$. De plus, le plus grand trou de $S$ est $13$. Sachant que $S$ contient tous les entiers positifs à partir de $14$, notre vérification est en fait déjà complète !

• Une famille d’exemples. Soit $m$ un entier positif non nul quelconque, et considérons l’ensemble \[S=\{0,m,\rightarrow\}=\{0,m,m+1,m+2,m+3,\dots\}.\] Vérifier que $S$ est un semigroupe numérique est encore plus facile que pour l’exemple précédent. Notons que cette famille généralise le second exemple de notre liste, à savoir $A=\{0,2,3,4,5,\dots\}$, puisqu’alors $A=\{0,2,\rightarrow\}$ et correspond donc au cas $m=2$.

Avec ces quelques exemples et contre-exemples, on voit que la notion de semigroupe numérique n’est pas bien méchante en soi. Ce qui est plus surprenant c’est qu’elle conduit, comme on le verra plus loin, à des problèmes donnant énormément de fil à retordre aux chercheur-e-s [2] cherchant à les résoudre.

La famille des semigroupes numériques

Comme souvent en mathématiques, dès lors qu’on a concocté une définition apparemment intéressante, on aimerait tout savoir sur les objets auxquels celle-ci donne naissance. Comme souvent aussi, cette innocente demande peut nécessiter des siècles de travaux pour être satisfaite !

Considérons donc la famille de tous les semigroupes numériques. C’est sûrement une grande famille pleine de secrets à découvrir.

Eh bien, pour commencer, cette famille est-elle finie ?

Rappelons notre famille d’exemples ci-dessus, avec $S=\{0,m,\rightarrow\}$, où $m$ un entier positif non nul arbitraire. La réponse est donc non, la famille des semigroupes numériques est infinie puisque $m$ est arbitraire. Cela dit, ce n’est pas cette légère contrariété passagère qui va nous arrêter dans notre exploration de cette famille.

Dans cette quête, justement, les chercheur-e-s ont développé de nombreux paramètres permettant de mieux distinguer les semigroupes numériques les uns des autres. Deux de ces paramètres vont plus particulièrement retenir notre attention ici : le genre et le nombre de Frobenius.

Genre et nombre de Frobenius

Donnons-nous un semigroupe numérique $S$. Rappelons que l’ensemble des trous de $S$ est dénoté $\overline{S}$, et que cet ensemble est fini d’après la troisième condition définissant les semigroupes numériques. Du coup, il est très naturel de vouloir compter ce nombre de trous et de connaître le plus grand d’entre eux.

Reprenons notre exemple $S=\{0,4,7,8,11,12,14,\rightarrow\}$. Ses seuls trous sont $1,2,3,5,6,9,10,13$, et constituent donc un ensemble à $8$ éléments et de maximum $13$.

Soit $S$ un semigroupe numérique.

• Le nombre de trous de $S$ est appelé le genre de $S$.
• Le plus grand trou de $S$ est appelé le nombre de Frobenius de $S$.

Pour l’exemple $S=\{0,4,7,8,11,12,14,\rightarrow\}$, dont on vient de voir qu’il a $8$ trous et que le plus grand d’entre eux est $13$, il suit que le genre et le nombre de Frobenius de $S$ valent respectivement $8$ et $13$.

Quant à l’exemple $S=\{0,m,\rightarrow\}$, où $m$ un entier positif quelconque, on observe que l’ensemble des trous de $S$ est
\[\overline{S}=\{1,2,...,m-1\},\]
tout simplement. C’est un ensemble à $m-1$ éléments et de maximum $m-1$. Il suit que le genre de $S$ et son nombre de Frobenius valent tous deux $m-1$.

Fixons le genre

L’un des intérêts de la notion de genre est que, pour une valeur de $g$ donnée, on peut compter tous les semigroupes numériques de genre $g$, autrement dit tous ceux ayant exactement $g$ trous. Voici un énoncé un peu plus formel.

Proposition. Pour tout entier positif $g$ donné, il n’y a qu’un nombre fini de semigroupes numériques de genre $g$.

Une preuve est donnée dans le bloc déroulant ci-dessous, mais on peut sans dommage poursuivre la lecture de l’article sans s’y plonger.

L’intérêt de ce résultat de finitude est qu’il donne tout son sens à la question suivante.

Question. Pour un entier positif $g$ donné, combien y a-t-il de semigroupes numériques de genre $g$, autrement dit à $g$ trous ?

Pour fixer les idées, on notera $n_g$ le nombre de semigroupes numériques à $g$ trous.

Premières valeurs de $n_g$

Essayons de déterminer le nombre $n_g$ pour de petites valeurs de $g$.

• Posons $g=0$. Le seul semigroupe numérique à $0$ trous est évidemment $\mathbb{N}= \{0,1,2,\dots\}$. On a donc
  \[n_0=1.\]

• Posons $g=1$, et soit $S$ un semigroupe numérique à $1$ trou. Si $S$ contenait $1$, alors de par la seconde condition définissant les semigroupes numériques, il contiendrait $1+1=2$, et donc aussi $1+2=3$, etc. Bref, il contiendrait tous les entiers positifs et serait donc égal à $\mathbb{N}$, ce qui est absurde puisque $\mathbb{N}$ a $0$ trous. On en conclut que $1$ est un trou de $S$, et que c’est le seul trou de $S$ puisque $S$ est supposé n’en avoir qu’un. Donc forcément $S = \{0,2,\rightarrow\}$, un exemple déjà rencontré en début d’article. On a donc
  \[n_1=1.\]

• Posons $g=2$, et soit $S$ un semigroupe numérique à $2$ trous. La discussion précédente montre que $1$ est forcément un trou de $S$. Notons $t$ l’unique second trou de $S$. A priori $t$ peut valoir $2, 3, 4$, etc. Examinons ces différentes possibilités.
  • Si $t=2$, alors $S$ contient tous les entiers positifs à partir de $3$, et donc $S=\{0,3,\rightarrow\}$. C’est une première solution.
  • Si $t=3$, alors $S$ contient $2$ et tous les entiers positifs à partir de $4$, et donc $S = \{0,2,4,\rightarrow\}$. C’est une deuxième solution.
  • Par contre, si $t \ge 4$, alors $S$ contiendrait $2$ et $3$, et donc $4,6,8, \dots$ et $5,7,9, \dots$. Bref, $S$ n’aurait qu’un seul trou à savoir $1$, contrairement à notre hypothèse. Ce cas est donc impossible.

Bilan : il y a exactement deux semigroupes numériques à $2$ trous, celui avec $\overline{S}=\{1,2\}$ et celui avec $\overline{S}=\{1,3\}$, ni plus ni moins. Donc
\[n_2=2.\]

• Posons $g=3$. On affirme que les seuls semigroupes numériques à $3$ trous sont les suivants :
  \[ \begin{array}{l} \{0,2,4,6,\rightarrow\} \\ \{0,3,4,6,\rightarrow\} \\ \{0,3,5,\rightarrow\} \\ \{0,4,\rightarrow\} \end{array} \]
  À ce stade, on préfère laisser aux lectrices et lecteurs volontaires le soin de se frotter au problème et de démontrer que ce sont bien là les uniques solutions à $3$ trous. On peut procéder comme ci-dessus, en posant $\overline{S}=\{1,t_2,t_3\}$ avec $1 < t_2 < t_3$ et en analysant les diverses possibilités. Bref, on trouve
  \[n_3=4.\]

Fort bien, mais qu’en est-il de $n_4, n_5, n_6, \dots$ ? Comment cette suite évolue-t-elle ? C’est un problème extrêmement difficile et non résolu à l’heure actuelle.

Heureusement, il existe un algorithme permettant de dresser la liste complète de tous les semigroupes numériques de genre $g$ donné, pourvu que $g$ ne soit pas trop grand. Cet algorithme sera présenté lors d’une suite à cet article à paraître le 21 juin 2018.

On peut donc mettre un ordinateur au travail et lui demander de faire ce décompte pour nous. Que trouve-t-on?

Autres valeurs connues de $n_g$

À l’heure actuelle, on n’a pu déterminer la valeur exacte de $n_g$ que jusqu’à $g=70$. On tombe déjà sur des nombres énormes. Voici quelques-unes de ces valeurs.

\[ \begin{array}{rr} \underline{g} & \underline{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} \]

Pour $g=70$ par exemple, on décompte plus d’un million et demi de milliards de semigroupes numériques à $70$ trous. Les valeurs de $n_g$ pour $g \le 50$ ont été obtenues par Maria Bras-Amorós en 2008, celles pour $51 \le g \le 55$ par Manuel Delgado vers 2010, et celles pour $56 \le g \le 70$ par Jean Fromentin et Florent Hivert en 2015 grâce à une nouvelle approche et des calculs à la fois massifs et d’une grande finesse. C’est le record actuel.

La suite des nombres $n_g$ porte le numéro A007323 dans la richissime On-line Encyclopedia of Integer Sequences. On y trouve les valeurs de $n_g$ pour $0 \le g \le 60$.

Les conjectures de Maria Bras-Amorós

C’est Maria Bras-Amorós, une jeune chercheure espagnole, qui s’est lancée la première dans le décompte par ordinateur des semigroupes numériques de grand genre $g$. Elle est arrivée jusqu’à $g=50$ en 2008, un résultat remarquable pour l’époque. Ô surprise, l’observation attentive des données récoltées l’a amenée à formuler la conjecture suivante.

Conjecture. La suite des nombres $n_g$ pour $g=0,1,2,\dots$ se comporte en gros comme la suite de Fibonacci. Plus précisément, le taux de croissance de la suite des $n_g$ tend vers le nombre d’or lorsque $g$ tend vers l’infini.

En réalité, cette conjecture est un condensé simplifié de trois conjectures plus précises de Maria Bras-Amorós et sur lesquelles on reviendra prochainement.

Le nombre d’or ?

Quelle surprise ! A priori, la suite de Fibonacci et le nombre d’or n’ont rien à voir avec les semigroupes numériques ! C’est là une nouvelle instance de l’un des grands mystères des mathématiques, qui rend ses praticiens si accros à cette science : le fait totalement inattendu de retrouver certains objets mathématiques dans des contextes a priori sans lien entre eux. L’ubiquité du nombre $\pi$ et du nombre d’or $\Phi=\frac{1+\sqrt{5}}{2}$ en sont des illustrations particulièrement spectaculaires.

Dans la suite de cet article nous reviendrons plus en détail sur l’algorithme permettant de déterminer les nombres $n_g$, sur les conjectures de Maria Bras-Amorós et sur l’état actuel des connaissances à leur sujet.