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 d'entiers non négatifs à coefficients non négatifs . Ce problème a été considéré par divers mathématiciens comme Frobenius (1849-1917) et Sylvester (1814-1897) à la fin du XIXe siècle[2]. Durant la deuxième partie du XXe 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 l'ensemble des entiers naturel. Une partie de est un demi-groupe numérique si les conditions suivantes sont vérifies :

  1. 0 est un élément de  ;
  2. le complément de dans est fini ;
  3. Si et sont dans , alors leur somme est dans .

Soit ensemble non vide d'entiers positifs. Le sous-demi-groupe engendré par est l'ensemble

des combinaisons linéaires, à coefficients non négatifs, d'éléments de . 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 est numérique si et seulement si [2].

Exemples

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

  • = {0, 1, 2, 3, ...} =
  • = {0, 1, 2, 3, ...} =
  • = {0, 2, 3, 4, 5, 6, ...} =
  • Pour tout entier positif , le monoïde est formé de tous les entiers supérieurs ou égal à .
  • Pour tout entier impair , on a :

Applications

Un lien existe entre l'ensemble des trous d'un demi-groupe numérique et des fonctions symmétriques. Plus précisément, Sōichi Kakeya a prouvé que[5] si une suite de entiers positifs est l'ensemble des trous d'un demi-groupe numérique, alors les sommes des puissances forment une base du corps de fonctions symétriques en 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 .

  • Les éléments de l'ensemble fini sont appelés des trous ;
  • le nombre de trous est le genre de , noté souvent ;
  • le plus grand trou est le nombre de Frobenius de , noté souvent .

Par exemple, pour , les trous sont les éléments de , le genre est et le nombre de Frobenius est . 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 est appelé la multiplicité de  ;
  • le conducteur de est le égal à 1+ le genre de .

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

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
     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 engendré par trois entiers de pgcd. 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 l'unique entier tel que et .
  • On applique l'algorithme de développement en fraction continue au quotient , et on obtient successivement :
avec
avec
avec
...
et pour tout .
  • Soient et et
  • Soit enfin l'unique indice tel que ou, de manière équivalente, l’unique indice tel que
  • Alors,

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

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

Articles liés

Notes et références

  1. Pedro A. García-Sánchez, « Numerical semigroups minicourse » (consulté le ).
  2. 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. » (no 598), , 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, no 3, , 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, , p. 69-80 et « On fundamental systems of symmetric functions II », Jap. J. Math., vol. 4, , p. 77-85.
  6. Gjergji Zaimi sur Math Overflow.
  7. Shalom Eliahou et Jean Fromentin, « Semigroupes numériques et nombre d'or (I) », Images de mathématiques, CNRS, (consulté le ).
  8. Matheus Bernardini et Fernando Torres, « Counting numerical semigroups by genus and even gaps », Discrete Mathematics, vol. 340, no 12, , p. 2853-2863 (arXiv 1612.01212).
  9. Jean Fromentin et Florent Hivert, « Exploring the tree of numerical semigroups », Mathematics of Computation, vol. 85, no 301, , 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, (consulté le ).
  11. Alex Zhai, « Fibonacci-like growth of numerical semigroups of a given genus », Semigroup Forum, vol. 86, no 3, , 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, , 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, no 1, , 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, , p. 171–178
  16. Harold Greenberg, « Solution to a linear Diophantine equation for non-negative integers », Journal of Algorithms, vol. 9, no 3, , 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, , 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 », , 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 », , xvi+ 243 (ISBN 978-0-19-856820-9, lire en ligne), p. 4–6
  • Steven Finch, « Monoids of Natural Numbers », .
  • Mara Hashuga, Megan Herbine et Alathea Jensen, « Numerical semigroups generated by quadratic sequences », Semigroup Forum, vol. 104, , 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, , p. 315–326 (DOI 10.1007/s00233-018-9952-3, arXiv 1712.06741).
  • Portail des mathématiques
  • Portail de l’algèbre
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.