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 $x_{1}a_{1}+x_{2}a_{2}+\cdots +x_{r}a_{r}$ d'entiers non négatifs $a_{1},\ldots ,a_{r}$ à coefficients non négatifs $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 $\mathbb {N}$ l'ensemble des entiers naturel. Une partie $S$ de $\mathbb {N}$ est un demi-groupe numérique si les conditions suivantes sont vérifies :

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

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

\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 $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 $\langle A\rangle$ est numérique si et seulement si $\operatorname {pgcd} (A)=1$ ^[2].

Exemples

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

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

\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 $n$ entiers positifs $k_{1},k_{2},\ldots ,k_{n}$ est l'ensemble des trous d'un demi-groupe numérique, alors les sommes des puissances $p_{k_{1}},p_{k_{2}},\ldots ,p_{k_{n}}$ forment une base du corps $\mathbb {Q} (p_{1},p_{2},\ldots ,p_{n})$ de fonctions symétriques en $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 $S$ .

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

Par exemple, pour $S=\{0,4,7,8,11,12\}\cup \{n\mid n\geq 14\}$ , les trous sont les éléments de $\mathbb {N} \setminus S=\{1,2,3,5,6,9,10,13\}$ , le genre est $g(S)=8$ et le nombre de Frobenius est $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 $S$ est appelé la multiplicité de $S$ ;
le conducteur de $S$ est le égal à 1+ le genre de $S$ .

Pour l'exemple $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 $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 $g$ donné, il n'y a qu'un nombre fini de demi-groupes numériques de genre $g$ .

Démonstration

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

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

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

Cela montre qu’au moins la moitié des nombres entiers entre 0 et $f$ est un trou de $S$ . Or par définition même, $S$ compte $g$ trous. Il suit que $g\geq (f+1)/2$ ou encore $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é 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
$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 $S$ engendré par trois entiers $a_{1}<a_{2}<a_{3}$ de pgcd $(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 $s_{0}$ l'unique entier tel que $a_{2}s_{0}\equiv a_{3}{\bmod {a}}_{1}$ et $0\leq s_{0}<a_{1}$ .
On applique l'algorithme de développement en fraction continue au quotient $a_{1}/s_{0}$ , et on obtient successivement :

a_{1}=q_{1}s_{0}-s_{1}

avec

0\leq s_{1}<s_{0}

s_{0}=q_{2}s_{1}-s_{2}

avec

0\leq s_{2}<s_{1}

s_{1}=q_{3}s_{2}-s_{3}

avec

0\leq s_{3}<s_{2}

...

s_{m-1}=q_{m+1}s_{m}

s_{m+1}=0

où

q_{i}\geq 2

et

s_{i}\geq 0

pour tout

i

.

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

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

Alors,

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 $S$ est irréductible si et seulement si $S$ est maximal, pour l'inclusion ensembliste, dans la famille des demi-groupes numériques de même nombre de Frobenius $f(S)$ .

Un demi-groupe numérique $S$ est symétrique s'il est irréductible et si son nombre de Frobenius $f(S)$ est impair ; il est dit pseudo-symétrique s'il est irréductible et $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 $S$ est symétrique (resp. pseudo-symétrique) si et seulement si $g(S)=(f(S)+1)/2$ (resp. $g(S)=(f(S)+2)/2$ ).

Articles liés

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Numerical Semigroup » (voir la liste des auteurs).

↑ Pedro A. García-Sánchez, « Numerical semigroups minicourse » (consulté le 6 avril 2011).
↑ ^{a et b} Rosales et Garcia-Sanchez 2009.
↑ Valentina Barucci, David E. Dobbs et Marco Fontana, Maximality properties in numerical semigroups and applications to one-dimensional analytically irreducible local domains, American Mathematical Society, coll. « Memoirs of the Amer. Math. Soc. » (n^o 598), 1997, 78 p. (ISBN 978-1-4704-0183-2).
↑ Ivan Martino et Luca Martino, « On the variety of linear recurrences and numerical semigroups », Semigroup Forum, vol. 88, n^o 3,‎ 2013, p. 569–574 (DOI 10.1007/s00233-013-9551-2, arXiv 1207.0111).
↑ Sōichi Kakeya, « On fundamental systems of symmetric functions I », Jap. J. Math., vol. 2,‎ 1925, p. 69-80 et « On fundamental systems of symmetric functions II », Jap. J. Math., vol. 4,‎ 1927, p. 77-85.
↑ Gjergji Zaimi sur Math Overflow.
↑ ^{a b et c} Shalom Eliahou et Jean Fromentin, « Semigroupes numériques et nombre d'or (I) », Images de mathématiques, CNRS, 20 mars 2018 (consulté le 8 juillet 2019).
↑ Matheus Bernardini et Fernando Torres, « Counting numerical semigroups by genus and even gaps », Discrete Mathematics, vol. 340, n^o 12,‎ 2017, p. 2853-2863 (arXiv 1612.01212).
↑ Jean Fromentin et Florent Hivert, « Exploring the tree of numerical semigroups », Mathematics of Computation, vol. 85, n^o 301,‎ 2015, p. 2553–2568 (DOI 10.1090/mcom/3075, arXiv 1305.3831).
↑ Shalom Eliahou et Jean Fromentin, « Semigroupes numériques et nombre d'or (II) », Images de mathématiques, CNRS, 21 juin 2018 (consulté le 8 juillet 2019).
↑ Alex Zhai, « Fibonacci-like growth of numerical semigroups of a given genus », Semigroup Forum, vol. 86, n^o 3,‎ 2012, p. 634-662 (DOI 10.1007/s00233-012-9456-5, arXiv 1111.3142).
↑ Frank Curtis, « On formulas for the Frobenius number of a numerical semigroup. », Mathematica Scandinavica, vol. 67,‎ 1990, p. 190-192 (ISSN 1903-1807, DOI 10.7146/math.scand.a-12330).
↑ J. C. Rosales, P. A. García-Sánchez et J. I. García-García, « Every positive integer is the Frobenius number of a numerical semigroup with three generators », Mathematica Scandinavica, vol. 94, n^o 1,‎ 2004, p. 5-12 (ISSN 1903-1807, DOI 10.7146/math.scand.a-14427).
↑ Ramírez Alfonsín 2005, p. 4-6.
↑ Øystein J. Rødseth, « On a linear Diophantine problem of Frobenius », J. Reine Angew. Math., vol. 301,‎ 1978, p. 171–178
↑ Harold Greenberg, « Solution to a linear Diophantine equation for non-negative integers », Journal of Algorithms, vol. 9, n^o 3,‎ 1988, p. 343–353 (DOI 10.1016/0196-6774(88)90025-9).

Bibliographie

José Carlos Rosales et Pedro A. García-Sánchez, Numerical Semigroups, Springer-Verlag New York, 2009, ix + 181 (ISBN 978-1-4419-0159-0, DOI 10.1007/978-1-4419-0160-6).
Abdallah Assi et Pedro A. García-Sánchez, Numerical Semigroups and Applications, Springer International Publishing, coll. « RSME Springer Series », 2016, xiv + 106 (ISBN 978-1-4419-0159-0, lire en ligne).
Jorge L. Ramírez Alfonsín, The Diophantine Frobenius Problem, Oxford University Press, coll. « Oxford Lecture Series in Mathematics and Its Applications », 2005, xvi+ 243 (ISBN 978-0-19-856820-9, lire en ligne), p. 4–6
Steven Finch, « Monoids of Natural Numbers », 17 mars 2009.
Mara Hashuga, Megan Herbine et Alathea Jensen, « Numerical semigroups generated by quadratic sequences », Semigroup Forum, vol. 104,‎ 2022, p. 330–357 (DOI 10.1007/s00233-022-10263-9, arXiv 2009.01981).
Sung Hyup Lee, Christopher O’Neill et Brandon Van Over, « On arithmetical numerical monoids with some generators omitted », Semigroup Forum, vol. 98,‎ 2019, p. 315–326 (DOI 10.1007/s00233-018-9952-3, arXiv 1712.06741).

[1] Pedro A. García-Sánchez, « Numerical semigroups minicourse » (consulté le 6 avril 2011).

[Rosales-2] {a et b} Rosales et Garcia-Sanchez 2009.

[3] Valentina Barucci, David E. Dobbs et Marco Fontana, Maximality properties in numerical semigroups and applications to one-dimensional analytically irreducible local domains, American Mathematical Society, coll. « Memoirs of the Amer. Math. Soc. » (n^o 598), 1997, 78 p. (ISBN 978-1-4704-0183-2).

[4] Ivan Martino et Luca Martino, « On the variety of linear recurrences and numerical semigroups », Semigroup Forum, vol. 88, n^o 3,‎ 2013, p. 569–574 (DOI 10.1007/s00233-013-9551-2, arXiv 1207.0111).

[5] Sōichi Kakeya, « On fundamental systems of symmetric functions I », Jap. J. Math., vol. 2,‎ 1925, p. 69-80 et « On fundamental systems of symmetric functions II », Jap. J. Math., vol. 4,‎ 1927, p. 77-85.

[6] Gjergji Zaimi sur Math Overflow.

[:0-7] {a b et c} Shalom Eliahou et Jean Fromentin, « Semigroupes numériques et nombre d'or (I) », Images de mathématiques, CNRS, 20 mars 2018 (consulté le 8 juillet 2019).

[8] Matheus Bernardini et Fernando Torres, « Counting numerical semigroups by genus and even gaps », Discrete Mathematics, vol. 340, n^o 12,‎ 2017, p. 2853-2863 (arXiv 1612.01212).

[FromentinHivert2015-9] Jean Fromentin et Florent Hivert, « Exploring the tree of numerical semigroups », Mathematics of Computation, vol. 85, n^o 301,‎ 2015, p. 2553–2568 (DOI 10.1090/mcom/3075, arXiv 1305.3831).

[10] Shalom Eliahou et Jean Fromentin, « Semigroupes numériques et nombre d'or (II) », Images de mathématiques, CNRS, 21 juin 2018 (consulté le 8 juillet 2019).

[Zhai2012-11] Alex Zhai, « Fibonacci-like growth of numerical semigroups of a given genus », Semigroup Forum, vol. 86, n^o 3,‎ 2012, p. 634-662 (DOI 10.1007/s00233-012-9456-5, arXiv 1111.3142).

[12] Frank Curtis, « On formulas for the Frobenius number of a numerical semigroup. », Mathematica Scandinavica, vol. 67,‎ 1990, p. 190-192 (ISSN 1903-1807, DOI 10.7146/math.scand.a-12330).

[13] J. C. Rosales, P. A. García-Sánchez et J. I. García-García, « Every positive integer is the Frobenius number of a numerical semigroup with three generators », Mathematica Scandinavica, vol. 94, n^o 1,‎ 2004, p. 5-12 (ISSN 1903-1807, DOI 10.7146/math.scand.a-14427).

[14] Ramírez Alfonsín 2005, p. 4-6.

[15] Øystein J. Rødseth, « On a linear Diophantine problem of Frobenius », J. Reine Angew. Math., vol. 301,‎ 1978, p. 171–178

[16] Harold Greenberg, « Solution to a linear Diophantine equation for non-negative integers », Journal of Algorithms, vol. 9, n^o 3,‎ 1988, p. 343–353 (DOI 10.1016/0196-6774(88)90025-9).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]