Demi-groupe numérique

Ensemble mathématique d'entiers

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

modifier

Définition

modifier

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

modifier

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

modifier

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   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

modifier

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é

modifier

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

modifier

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

modifier

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

modifier

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

modifier

Notes et références

modifier
  1. Pedro A. García-Sánchez, « Numerical semigroups minicourse » (consulté le ).
  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. » (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. a b et c 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

modifier