Demi-groupe numérique

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

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 \}}$

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 ${\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].

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})}$