Demi-groupe numérique

En mathématiques, et notamment en algèbre générale et en théorie des nombres, un demi-groupe numérique est un demi-groupe particulier. C'est un sous-ensemble de l'ensemble des entiers naturels qui contient tous les entiers à un nombre fini près. L'opération binaire est l'addition des entiers. L'entier 0 doit être un élément du demi-groupe. Par exemple, l'ensemble {0, 2, 3, 4, 5, 6, ...} formé des entiers à l'exception de 1 est un demi-groupe numérique, l'ensemble {0, 1, 3, 5, 6, ...} formé de tous les entiers sauf 2 et 4 n'en est pas un parce que ni 1 + 1 = 2 ni 1 + 3 = 4 ne figurent dans l’ensemble.

Un demi-groupe numérique est un monoïde ; c'est pourquoi ils sont aussi appelés monoïdes numériques^[1]

La notion de demi-groupe numérique est intimement liée au problème des pièces de monnaie qui est, du point de vue mathématique, le calcul des entiers non négatifs qui peuvent s'exprimer sous la forme de combinaisons linéaires ${\displaystyle x_{1}a_{1}+x_{2}a_{2}+\cdots +x_{r}a_{r}}$ d'entiers non négatifs ${\displaystyle a_{1},\ldots ,a_{r}}$ à coefficients non négatifs ${\displaystyle x_{1},\ldots ,x_{r}}$. Ce problème a été considéré par divers mathématiciens comme Frobenius (1849-1917) et Sylvester (1814-1897) à la fin du XIX^e siècle^[2]. Durant la deuxième partie du XX^e siècle, l'intérêt pour l'étude des demi-groupes numériques a été ravivé par leur application en géométrie algébrique^[3],[4].

Définition et exemples

Définition

On note ${\displaystyle \mathbb {N} }$ l'ensemble des entiers naturel. Une partie ${\displaystyle S}$ de ${\displaystyle \mathbb {N} }$ est un demi-groupe numérique si les conditions suivantes sont vérifies :

1. 0 est un élément de ${\displaystyle S}$ ;
2. le complément ${\displaystyle \mathbb {N} \setminus S}$ de ${\displaystyle S}$ dans ${\displaystyle \mathbb {N} }$ est fini ;
3. Si ${\displaystyle x}$ et ${\displaystyle y}$ sont dans ${\displaystyle S}$, alors leur somme ${\displaystyle x+y}$ est dans ${\displaystyle S}$.

Soit ${\displaystyle A=\{a_{1},\ldots ,a_{r}\}}$ ensemble non vide d'entiers positifs. Le sous-demi-groupe engendré par ${\displaystyle A}$ est l'ensemble

${\displaystyle \langle A\rangle =\{x_{1}a_{1}+\cdots +x_{r}a_{r}\mid x_{1},\ldots ,x_{r}\in \mathbb {N} \}}$

des combinaisons linéaires, à coefficients non négatifs, d'éléments de ${\displaystyle A}$. Ce sous-demi-groupe contient tous les entiers naturels à un nombre fini près s'il est un demi-groupe numérique. Le résultat suivant caractérise les demi-groupes numériques : Le demi-groupe ${\displaystyle \langle A\rangle }$ est numérique si et seulement si ${\displaystyle \operatorname {pgcd} (A)=1}$^[2].

Exemples

Les demi-groupes suivants sont des demi-groupes numériques :

• ${\displaystyle \langle 1\rangle }$ = {0, 1, 2, 3, ...} = ${\displaystyle \mathbb {N} }$
• ${\displaystyle \langle 1,2\rangle }$ = {0, 1, 2, 3, ...} = ${\displaystyle \mathbb {N} }$
• ${\displaystyle \langle 2,3\rangle }$ = {0, 2, 3, 4, 5, 6, ...} = ${\displaystyle \mathbb {N} \setminus 1}$
• Pour tout entier positif ${\displaystyle a}$, le monoïde ${\displaystyle \langle a,a+1,a+2,\ldots ,2a-1\rangle }$ est formé de tous les entiers supérieurs ou égal à ${\displaystyle a}$.
• Pour tout entier impair ${\displaystyle b>1}$, on a :

${\displaystyle \langle 2,b\rangle =\{0,2,4,\ldots ,b-3,b-1,b,b+1,b+2,\ldots \}}$

Applications

Un lien existe entre l'ensemble des trous d'un demi-groupe numérique et des fonctions symétriques. Plus précisément, Sōichi Kakeya a prouvé que^[5] si une suite de ${\displaystyle n}$ entiers positifs ${\displaystyle k_{1},k_{2},\ldots ,k_{n}}$ est l'ensemble des trous d'un demi-groupe numérique, alors les sommes des puissances ${\displaystyle p_{k_{1}},p_{k_{2}},\ldots ,p_{k_{n}}}$ forment une base du corps ${\displaystyle \mathbb {Q} (p_{1},p_{2},\ldots ,p_{n})}$ de fonctions symétriques en ${\displaystyle n}$ variables. Kakeya a conjecturé que toute base de sommes de puissances de fonctions symétriques a cette propriété, mais ce problème est toujours ouvert^[6].

Genre et nombre de Frobenius

Divers paramètres sont associés à un demi-groupe numérique ${\displaystyle S}$.

• Les éléments de l'ensemble fini ${\displaystyle \mathbb {N} \setminus S}$ sont appelés des trous ;
• le nombre de trous est le genre de ${\displaystyle S}$, noté souvent ${\displaystyle g(S)}$;
• le plus grand trou est le nombre de Frobenius de ${\displaystyle S}$, noté souvent ${\displaystyle f(S)}$.

Par exemple, pour ${\displaystyle S=\{0,4,7,8,11,12\}\cup \{n\mid n\geq 14\}}$, les trous sont les éléments de ${\displaystyle \mathbb {N} \setminus S=\{1,2,3,5,6,9,10,13\}}$, le genre est ${\displaystyle g(S)=8}$ et le nombre de Frobenius est ${\displaystyle f(S)=13}$. Ce dernier nombre est étroitement lié au problème des pièces de monnaie déjà mentionné.

D'autres paramètres ont été définis :

• Le plus petit élément non nul de ${\displaystyle S}$ est appelé la multiplicité de ${\displaystyle S}$ ;
• le conducteur de ${\displaystyle S}$ est le égal à 1+ le genre de ${\displaystyle S}$.

Pour l'exemple ${\displaystyle S=\{0,4,7,8,11,12\}\cup \{n\mid n\geq 14\}}$ ci-dessus, la multiplicité est 4, et le conducteur est 14.

On considère aussi le plus petit ensemble de générateurs, et la dimension enveloppante : un ensemble de générateurs d'un demi-groupe numérique est un plus petit ensemble de générateurs si aucun de ses sous-ensembles ne génère ce demi-groupe numérique. On peut montrer que chaque demi-groupe numérique ${\displaystyle S}$ possède un système minimal de générateurs unique, et aussi que ce système minimal de générateurs est fini. La cardinalité de l'ensemble minimal de générateurs est appelée la dimension enveloppante du demi-groupe numérique S et est notée e('S).

Nombre de demi-groupes numériques de genre donné

On observe^[7] :

Proposition — Pour un entier positif ${\displaystyle g}$ donné, il n'y a qu'un nombre fini de demi-groupes numériques de genre ${\displaystyle g}$.

Démonstration

Soit ${\displaystyle S}$ un demi-groupe numérique de genre ${\displaystyle g}$. On va prouver que l’ensemble de ses trous est contenu dans l'ensemble ${\displaystyle \{1,\ldots ,2g-1\}}$. Comme l'ensemble des trous détermine ${\displaystyle S}$ et qu'il n'y a qu'un nombre fini de sous-ensembles de ${\displaystyle \{1,\ldots ,2g-1\}}$, cela montre l'assertion.

Soit ${\displaystyle f}$ le nombre de Frobenius de ${\displaystyle S}$, autrement dit le plus grand trou de ${\displaystyle S}$. L’ensemble des trous de ${\displaystyle S}$ est contenu dans ${\displaystyle \{1,\ldots ,f\}}$, et il suffit donc de montrer que ${\displaystyle f}$ est inférieur ou égal à ${\displaystyle 2g-1}$.

Pour cela, soit ${\displaystyle x}$ un entier compris entre 0 et ${\displaystyle f}$. Alors ${\displaystyle f-x}$ est aussi un entier compris entre 0 et ${\displaystyle f}$. Les entiers ${\displaystyle x}$ et ${\displaystyle f-x}$ n'appartiennent pas tous deux à ${\displaystyle S}$, car sinon leur somme ${\displaystyle x+f-x=f}$ appartiendrait aussi à ${\displaystyle S}$, contrairement à la définition de ${\displaystyle f}$ comme étant un trou. Donc soit ${\displaystyle x}$ soit ${\displaystyle f-x}$ est un trou de ${\displaystyle S}$.

Cela montre qu’au moins la moitié des nombres entiers entre 0 et ${\displaystyle f}$ est un trou de ${\displaystyle S}$. Or par définition même, ${\displaystyle S}$ compte ${\displaystyle g}$ trous. Il suit que ${\displaystyle g\geq (f+1)/2}$ ou encore ${\displaystyle f\leq 2g-1}$ comme souhaité^[7].

Le calcul du nombre de demi-groupes numériques de genre donné, et l'interprétation de la suite de nombres obtenus, a fait et fait l'objet de plusieurs études^[8]. Les premières valeurs sont données par la suite A007323 de l'OEIS :

1, 1, 2, 4, 7, 12, 23, 39, 67, 118, 204, 343, 592, 1001, 1693, 2857, 4806, 8045, 13467, 22464, 37396, 62194, 103246, 170963, 282828, 467224, 770832, 1270267, 2091030, 3437839, 5646773, 9266788, 15195070, 24896206, 40761087, 66687201, 109032500, 178158289

La limite a été poussée jusqu'au genre g=67 par Jean Fromentin et Florent Hivert^[9]. Deux articles des Images des mathématiques du CNRS en parlent en détail^{[7], [10]}. Cette suite de nombres croît comme les nombres de Fibonacci, d'après un article d'Alex Zhai^[11].

Les premiers demi-groupes de petit genre et petits nombres de Frobenius sont les suivants :

Demi-groupes avec petits paramètres

${\displaystyle n}$	Demi-groupe S    avec f(S) = n	Demi-groupe S    avec g(S) = n
1	⟨ 2, 3 ⟩	⟨ 2, 3 ⟩
2	⟨ 3, 4, 5 ⟩	⟨ 3, 4, 5 ⟩    ⟨ 2, 5 ⟩
3	⟨ 4, 5, 6, 7 ⟩    ⟨ 2, 5 ⟩	⟨ 4, 5, 6, 7, ⟩    ⟨ 3, 5, 7 ⟩    ⟨ 3, 4 ⟩    ⟨ 2, 7 ⟩
4	⟨ 5, 6, 7, 8, 9 ⟩    ⟨ 3, 5, 7 ⟩	⟨ 5, 6, 7, 8, 9 ⟩    ⟨ 4, 6, 7, 9 ⟩    ⟨ 3, 7, 8 ⟩    ⟨ 4, 5, 7 ⟩    ⟨ 4, 5, 6 ⟩    ⟨ 3, 5, ⟩    ⟨ 2, 9 ⟩

Calcul du nombre de Frobenius

Le calcul du nombre de Frobenius à partir des générateurs est détaillé dans l'article Problème des pièces de monnaie. Dès que le nombre de générateurs est plus grand que 2, le calcul est compliqué^[12]. Tout entier positif peut être le nombre de Frobenius d'un demi-groupe de dimension trois^[13].

Algorithme de Rödseth

L'algorithme suivant, attribué à Rødseth (ou Rödseth)^{[14] ,[15]}, permet de calculer le nombre de Frobenius d'un demi-groupe ${\displaystyle S}$ engendré par trois entiers ${\displaystyle a_{1}<a_{2}<a_{3}}$ de pgcd${\displaystyle (a_{1},a_{2},a_{3})=1}$. Sa complexité dans le pire des cas est plus élevée que celle d'un autre algorithme, dû à Harold Greenberg ^[16], mais il est bien plus simple à décrire.

• Soit ${\displaystyle s_{0}}$ l'unique entier tel que ${\displaystyle a_{2}s_{0}\equiv a_{3}{\bmod {a}}_{1}}$ et ${\displaystyle 0\leq s_{0}<a_{1}}$.
• On applique l'algorithme de développement en fraction continue au quotient ${\displaystyle a_{1}/s_{0}}$, et on obtient successivement :

${\displaystyle a_{1}=q_{1}s_{0}-s_{1}}$ avec ${\displaystyle 0\leq s_{1}<s_{0}}$

${\displaystyle s_{0}=q_{2}s_{1}-s_{2}}$ avec ${\displaystyle 0\leq s_{2}<s_{1}}$

${\displaystyle s_{1}=q_{3}s_{2}-s_{3}}$ avec ${\displaystyle 0\leq s_{3}<s_{2}}$

...

${\displaystyle s_{m-1}=q_{m+1}s_{m}}$

${\displaystyle s_{m+1}=0}$

où ${\displaystyle q_{i}\geq 2}$ et ${\displaystyle s_{i}\geq 0}$ pour tout ${\displaystyle i}$.

• Soient ${\displaystyle p_{-1}=0,p_{0}=1}$ et ${\displaystyle p_{i+1}=q_{i+1}p_{i}-p_{i-1}}$ et ${\displaystyle r_{i}=(s_{i}a_{2}-p_{i}a_{3})/a_{3}}$
• Soit enfin ${\displaystyle v}$ l'unique indice tel que ${\displaystyle r_{v+1}\leq 0<r_{v}}$ ou, de manière équivalente, l’unique indice tel que

${\displaystyle {\frac {s_{v+1}}{p_{v+1}}}\leq {\frac {a_{3}}{a_{2}}}<{\frac {s_{v}}{p_{v}}}}$

• Alors,

${\displaystyle f(S)=-a_{1}+a_{2}(s_{v}-1)+a_{3}(p_{v+1}-1)-\min(a_{2}s_{v+1},a_{3}p_{v})}$

Classes particulières de demi-groupes numériques

Un demi-groupe numérique est irréductible s'il ne peut être exprimé comme l'intersection de deux demi-groupes numériques le contenant correctement. Un demi-groupe numérique ${\displaystyle S}$ est irréductible si et seulement si ${\displaystyle S}$ est maximal, pour l'inclusion ensembliste, dans la famille des demi-groupes numériques de même nombre de Frobenius ${\displaystyle f(S)}$.

Un demi-groupe numérique ${\displaystyle S}$ est symétrique s'il est irréductible et si son nombre de Frobenius ${\displaystyle f(S)}$ est impair ; il est dit pseudo-symétrique s'il est irréductible et ${\displaystyle f(S)}$ est pair. Ces demi-groupes numériques admettent une caractérisation simple en termes de nombre de Frobenius et de genre : Un demi-groupe numérique ${\displaystyle S}$ est symétrique (resp. pseudo-symétrique) si et seulement si ${\displaystyle g(S)=(f(S)+1)/2}$ (resp. ${\displaystyle g(S)=(f(S)+2)/2}$).

Articles liés

• Demi-groupe
• Problème des pièces de monnaie
• Classes de demi-groupes (en)