🔢 mathematics

On the Frobenius Number and Genus of a Collection of Semigroups Generalizing Repunit Numerical Semigroups

Cet article résout le problème de Frobenius pour une famille de semigroupes numériques généralisant les semigroupes repunit, en établissant des formules pour le nombre de Frobenius et le genre même lorsque le paramètre $d$ est négatif, et en appliquant ces résultats à des cas particuliers tels que les semigroupes de Mersenne, Thabit et Proth.

Auteurs originaux : Feihu Liu, Guoce Xin, Suting Ye, Jingjing Yin

Publié 2026-04-13

📖 4 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Feihu Liu, Guoce Xin, Suting Ye, Jingjing Yin

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous êtes un chef cuisinier dans un restaurant très spécial. Vous avez une liste d'ingrédients de base (disons des sacs de farine de différentes tailles) et vous voulez savoir quelles quantités de farine vous pouvez mesurer en les combinant.

Si vous avez un sac de 3 kg et un sac de 5 kg, vous pouvez faire 3, 5, 6 (3+3), 8 (3+5), 9 (3+3+3), 10 (5+5), etc. Mais vous ne pouvez jamais faire exactement 1 kg, 2 kg, 4 kg ou 7 kg.

Dans le monde des mathématiques, ce problème s'appelle le problème de Frobenius. Les mathématiciens cherchent deux choses principales :

Le nombre de Frobenius : C'est le plus grand nombre que vous ne pouvez pas mesurer avec vos sacs. Dans l'exemple ci-dessus, c'est 7 kg. Au-delà de 7, vous pouvez tout faire.
Le genre : C'est simplement le nombre total de quantités impossibles à mesurer (ici, 1, 2, 4 et 7, donc 4 quantités).

Le défi du papier

Jusqu'à présent, trouver ces nombres était facile si vous n'aviez que deux ingrédients. Mais si vous en avez 3, 4, ou 10, cela devient un casse-tête terriblement difficile, comme essayer de résoudre un Sudoku géant sans règles claires.

Les auteurs de ce papier (Liu, Xin, Ye et Yin) ont décidé de regarder une famille très spécifique de "sacs" qui suivent un motif régulier, un peu comme des poupées russes ou des escaliers.

L'analogie de l'Escalier Magique

Imaginons que vos ingrédients ne sont pas n'importe quels nombres, mais qu'ils suivent une règle de construction très précise :

Le premier ingrédient est un nombre $a$ .
Le deuxième est $a$ multiplié par un nombre $b$ , plus un petit ajustement $d$ .
Le troisième est $a$ multiplié par $b$ au carré, plus un ajustement plus grand, et ainsi de suite.

C'est comme si vous construisiez un escalier où chaque marche est un peu plus haute que la précédente selon une formule mathématique précise.

La grande innovation de ce papier :
Habituellement, les mathématiciens supposent que l'ajustement $d$ est toujours positif (vous ajoutez toujours un peu de farine). Mais dans ce papier, les auteurs disent : "Et si $d$ était négatif ?"
Cela revient à dire : "Et si, au lieu d'ajouter de la farine, nous devions en retirer un peu pour obtenir la bonne taille ?" C'est contre-intuitif, mais cela ouvre la porte à de nouveaux types de problèmes, comme ceux liés aux nombres de Proth (une classe de nombres utilisés en cryptographie).

Comment ils ont résolu le problème ?

Au lieu de calculer chaque possibilité une par une (ce qui prendrait des siècles), ils ont utilisé une stratégie intelligente appelée l'algorithme gourmand (greedy algorithm).

Imaginez que vous devez payer une somme exacte avec des pièces. La stratégie "gourmande" consiste à prendre d'abord le plus grand nombre de pièces de la plus grande valeur possible, puis à passer à la suivante, et ainsi de suite.

Pour certains types de pièces, cette méthode est parfaite.
Pour d'autres, elle échoue.

Les auteurs ont prouvé que pour leur famille spécifique d'ingrédients (leur "Escalier Magique"), la stratégie gourmande fonctionne toujours parfaitement. Grâce à cela, ils ont pu inventer des formules magiques (des équations simples) qui donnent directement le nombre de Frobenius et le genre, sans avoir à faire des milliers de calculs.

Pourquoi est-ce important ?

Ce papier est comme un couteau suisse mathématique. Au lieu d'avoir une solution différente pour chaque type de problème, ils ont trouvé une méthode unique qui fonctionne pour plusieurs familles célèbres de nombres :

Les nombres Répunit : Des nombres comme 111, 1111, 11111 (faits de 1 répétés).
Les nombres de Mersenne : Des nombres comme 7, 15, 31 (très importants pour trouver des nombres premiers géants).
Les nombres de Thabit : Une autre famille de nombres liés à la géométrie et à l'arithmétique.
Les nombres de Proth : Des nombres utilisés pour tester la primalité (savoir si un nombre est premier).

En résumé

Ces chercheurs ont pris un problème mathématique très complexe (trouver les trous dans une grille de nombres) et ont montré que si les nombres suivent un motif spécifique (même avec des ajustements négatifs), on peut utiliser une règle simple et élégante pour prédire exactement où se trouvent les plus grands trous et combien il y en a au total.

Ils ont non seulement résolu des cas connus, mais ils ont aussi commencé à résoudre un vieux problème ouvert concernant les nombres de Proth, offrant ainsi une nouvelle clé pour comprendre ces structures numériques mystérieuses. C'est une avancée qui simplifie grandement le travail des futurs mathématiciens qui étudient ces nombres.

1. Problématique et Contexte

L'article s'attaque au problème de Frobenius pour une classe généralisée de semi-groupes numériques. Étant donné une séquence d'entiers positifs $A = (a_1, a_2, \dots, a_n)$ premiers entre eux, le problème consiste à déterminer :

Le nombre de Frobenius $F(A)$ : le plus grand entier ne pouvant pas être représenté comme une combinaison linéaire à coefficients entiers non négatifs des éléments de $A$ .
Le genre $g(A)$ : le nombre d'entiers positifs non représentables.
Les nombres pseudo-Frobenius et le type du semi-groupe.

Bien que des formules fermées existent pour $n=2$ (formule de Sylvester), le problème est NP-difficile pour $n \ge 3$ en général. L'article se concentre sur des structures spécifiques généralisant les semi-groupes numériques repunit (basés sur les nombres de la forme $\frac{b^n-1}{b-1}$ ), ainsi que les semi-groupes de Mersenne, Thabit et Proth.

2. Méthodologie

Les auteurs développent une approche unifiée basée sur l'analyse de l'ensemble d'Apéry et l'utilisation d'algorithmes gloutons pour résoudre des problèmes d'optimisation discrète.

A. Définition de la Collection Généralisée (GCNS)

Les auteurs introduisent une collection générale de semi-groupes notée Collection GCNS, définie par le générateur $A = (a, h_1a + db_1, h_2a + db_2, \dots, h_ka + db_k)$ , où :

$b_1 = 1$ et $b_{i+1} = s_i b_i + 1$ avec $s_i \ge s_{i-1}$ .
$h_i = u b_i + 1$ pour un entier $u \in \mathbb{P}$ .
$d$ peut être un entier négatif, ce qui constitue une innovation majeure par rapport aux travaux antérieurs.

B. L'Ensemble d'Apéry et la Minimisation

La clé de la méthode réside dans le calcul de l'ensemble d'Apéry $Ape(A, a) = \{N_0, N_1, \dots, N_{a-1}\}$ , où $N_r$ est le plus petit élément du semi-groupe congru à $r$ modulo $a$ .
Les auteurs montrent que $N_r$ est lié à un problème de minimisation noté $O^H_B(M)$ :
$O^H_B(M) = \min \left\{ \sum_{i=1}^k h_i x_i \;\middle|\; \sum_{i=1}^k b_i x_i = M, x_i \in \mathbb{N} \right\}$

C. Séquences Ordonnées et Algorithme Glouton

Un point central est la démonstration que la séquence $B = (b_1, \dots, b_k)$ est ordonnée (orderly) sous les conditions données (via le One-Point Theorem). Cela implique que la solution optimale du problème de minimisation ci-dessus est donnée par l'algorithme glouton (greedy algorithm).
Les auteurs définissent une présentation gloutonne unique pour chaque entier et établissent des propriétés de monotonie sur le "poids" de ces présentations, permettant de déterminer l'élément maximal de l'ensemble d'Apéry sans énumération exhaustive.

3. Contributions Clés et Résultats Principaux

A. Formules Unifiées pour $F(A)$ et $g(A)$

Sous certaines conditions techniques (notamment $ua + d + k - 2 \ge \sum s_i$ et $s_i < u+1$ ), les auteurs établissent des formules fermées pour le nombre de Frobenius et le genre :

Nombre de Frobenius :
$F(A) = \left( \sum_{i=1}^k x_i \right) a + (a-1)(ua + d) - a$
où $(x_1, \dots, x_k)$ est la présentation gloutonne de $a-1$ .
Genre : Une formule impliquant la somme des poids des présentations gloutonnes de tous les entiers de $0 $à$ a-1$.

B. Applications aux Semi-groupes Spécifiques

La généralisation permet de retrouver et de simplifier les résultats pour plusieurs classes connues :

Semi-groupes Repunit et Mersenne : En posant $b_i = \frac{b^i-1}{b-1}$ , $u=b-1$ , et $d=1$ , on retrouve les résultats de [25] et [26] pour les semi-groupes repunit et Mersenne.
Semi-groupes Thabit : En posant $b_i = 2^i-1$ , $u=1$ , et $d=1$ , on généralise les résultats pour les semi-groupes de Thabit.
Semi-groupes Proth (Résolution partielle d'un problème ouvert) :
- Le problème ouvert 1.3 de [31] demandait une formule pour le nombre de Frobenius des semi-groupes de Proth $P_m(n)$ pour un $m$ impair arbitraire.
- Les auteurs résolvent partiellement ce problème en traitant le cas où $d=-1$ .
- Ils fournissent des formules explicites pour $F(P_m(n))$ basées sur la présentation gloutonne de $(2^r+q)2^n$ , et génèrent un tableau (Tableau 1) donnant les formules pour $q < 50$ .

C. Innovation sur $d$ négatif

Contrairement à la plupart des travaux précédents qui supposent $d > 0$ , ce papier permet $d \in \mathbb{Z} \setminus \{0\}$ . Cela est crucial pour traiter les semi-groupes de Proth et de Cunningham où les générateurs sont de la forme $m2^n + 1$ (ce qui correspond à une structure avec $d=-1$ dans leur cadre général).

4. Signification et Impact

Unification : L'article offre un cadre théorique unique qui englobe et simplifie les résultats dispersés dans la littérature pour les semi-groupes de Mersenne, Thabit, Repunit et Proth.
Méthodologie Algorithmique : La démonstration que l'algorithme glouton est optimal pour cette classe de séquences permet de calculer efficacement les invariants sans avoir besoin de résoudre des problèmes d'optimisation complexes pour chaque cas.
Avancée sur les Semi-groupes de Proth : Bien que la solution pour $m$ arbitraire ne soit pas complète (elle dépend de la structure de la présentation gloutonne), l'article fournit une méthode systématique et des formules explicites pour une large gamme de paramètres, répondant partiellement à un problème ouvert récent.
Généralisation : L'introduction de la collection GCNS ouvre la voie à l'étude de nouvelles familles de semi-groupes numériques définis par des relations de récurrence similaires.

En résumé, cet article apporte des formules fermées élégantes pour des invariants fondamentaux de classes importantes de semi-groupes numériques, en exploitant la structure ordonnée de leurs générateurs et la puissance de l'algorithme glouton, tout en étendant le domaine de validité à des paramètres négatifs.