🔢 mathematics

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

Dit artikel bestudeert het Frobeniusprobleem voor een verzameling numerieke semigruppen die repunit-semigruppen generaliseren, waarbij nieuwe formules worden afgeleid voor de Frobeniusgetallen en het genus, zelfs wanneer een parameter negatief is, en deze resultaten worden toegepast op specifieke gevallen zoals Mersenne-, Thabit- en repunit-semigruppen, evenals op een gedeeltelijke oplossing voor een open probleem betreffende Proth-semigruppen.

Oorspronkelijke auteurs: Feihu Liu, Guoce Xin, Suting Ye, Jingjing Yin

Gepubliceerd 2026-04-13

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Feihu Liu, Guoce Xin, Suting Ye, Jingjing Yin

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een enorme verzameling blokken hebt, maar je mag ze alleen in specifieke combinaties stapelen. Je hebt een set "basisblokken" met verschillende hoogtes: bijvoorbeeld een blok van 3, een van 5 en een van 7.

Met deze blokken kun je torens bouwen. Een toren van 8 is mogelijk (3 + 5), een toren van 10 ook (5 + 5), en een toren van 12 (5 + 7). Maar wat als je probeert een toren van 4 te bouwen? Of 1? Dat lukt niet. Je kunt die hoogtes niet maken met je basisblokken.

In de wiskunde noemen we dit een Numerieke Halfgroep. De "Frobeniusgetal" is simpelweg het grootste getal dat je nooit kunt bouwen, hoe hard je ook probeert. Het is de hoogste muur die je niet kunt overklimmen met je specifieke set blokken. De "Genus" is gewoon het aantal verschillende hoogtes die je missend hebt (de gaten in je muur).

Deze paper is als een bouwmeester die een nieuwe, superkrachtige formule heeft bedacht om precies te weten hoe hoog die onoverkomelijke muur is en hoeveel gaten er zijn, zelfs als de blokken heel gekke patronen volgen.

Hier is hoe ze dat doen, vertaald naar alledaagse taal:

1. Het Grote Probleem: De "Gaten" in de Muur

Voor twee blokken (bijv. 3 en 5) is het makkelijk: je kunt alles bouwen boven de 7. Maar zodra je drie of meer blokken hebt, wordt het een chaos. Wiskundigen weten al lang dat er geen simpele "één regel" formule is voor elke willekeurige set blokken. Het is alsof je probeert de perfecte route te vinden in een labyrint zonder kaart.

De auteurs van dit papier zeggen: "Wacht even, als je de blokken op een heel specifieke manier kiest, kunnen we wel een kaart maken!"

2. De Magische Set Blokken (De "Repunit" Familie)

De auteurs kijken naar een speciale familie van blokken die lijken op getallen die je krijgt als je herhaaldelijk een cijfer herhaalt (zoals 111, 1111, of 1, 11, 111 in een ander talstelsel). Ze noemen dit "Repunit-numerieke halfgroepen".

Maar ze gaan nog een stapje verder. Ze bedenken een algemene formule die niet alleen werkt voor die simpele herhalingen, maar ook voor veel complexere patronen. Ze zeggen: "Stel je voor dat je blokken hebt die er zo uitzien:

Blok 1: Een groot getal $a$ .
Blok 2: $a$ maal een getal $b$ , plus een klein beetje $d$ .
Blok 3: $a$ maal $b^2$ , plus een iets ander beetje $d$ .
En zo verder..."

Het slimme trucje hier is dat $d$ negatief kan zijn.

Analogie: Stel je voor dat je blokken bouwt, maar soms moet je een blok wegnemen (negatief) om de juiste vorm te krijgen, zolang het eindresultaat maar positief blijft. De meeste wiskundigen durfden dat niet te doen, maar deze auteurs zeggen: "Waarom niet? Laten we kijken wat er gebeurt als we die negatieve blokken toestaan."

3. De "Gierige" Strategie (De Greedy Algorithm)

Hoe vinden ze dan het grootste getal dat je niet kunt bouwen? Ze gebruiken een strategie die ze "Gierig" noemen.

De Analogie: Stel je hebt een tas met munten van 1, 3, 7 en 15. Je wilt precies 23 cent betalen.
- De "Gierige" strategie zegt: "Neem eerst het grootste muntstuk dat past!" Dus neem 15. Dan heb je 8 over. Neem 7. Dan heb je 1 over. Neem 1. Klaar! (15 + 7 + 1 = 23).
- De auteurs bewijzen dat voor hun speciale set blokken, deze "Gierige" manier van tellen altijd werkt. Je hoeft niet te gokken of te proberen; je hoeft alleen maar het grootste mogelijke blok te pakken en dan de rest op te lossen.

Omdat ze weten dat deze "Gierige" manier altijd werkt, kunnen ze een simpele rekensom maken om het "grootste onbereikbare getal" (Frobeniusgetal) en het aantal "gaten" (Genus) te berekenen.

4. Wat hebben ze precies gevonden?

Ze hebben een universele sleutel gevonden die opent voor veel verschillende soorten "muren":

Mersenne-getallen: Getallen die lijken op $2^n - 1$ (zoals 3, 7, 15, 31).
Thabit-getallen: Een ander speciaal soort getallenreeks.
Repunit-getallen: Getallen zoals 111, 1111.
Proth-getallen: Een nog complexer type, waarvoor ze een deel van een oud raadsel oplossen.

Voor al deze gevallen geven ze nu een duidelijke formule. In plaats van urenlang te rekenen of te gokken, kun je nu in één keer zeggen: "Als je blokken hebt met deze eigenschappen, dan is het grootste getal dat je niet kunt bouwen X, en je hebt Y gaten."

5. Het Oplossen van een Oud Raadsel

In het laatste deel van het papier pakken ze een specifiek raadsel aan over Proth-numerieke halfgroepen. Dit is een probleem dat al een tijdje open stond. De auteurs zeggen: "We kunnen het niet voor elk getal oplossen, maar voor een groot deel van de gevallen hebben we nu een formule."

Analogie: Het is alsof je een sleutel hebt die 90% van de deuren in een kasteel opent. Je hebt nog niet de sleutel voor de allerlaatste deur, maar je hebt wel de sleutel voor de rest, en dat is al een enorme doorbraak.

Samenvatting

Kortom, deze paper is als het vinden van een magische bouwerij.

Vroeger: "We weten niet hoe hoog de muur is die je niet kunt bouwen, tenzij je het één voor één probeert."
Nu: "Als je blokken gebruikt die in een bepaald patroon groeien (zelfs als je soms een blok moet 'aftrekken'), dan hebben we een simpele formule die je direct vertelt hoe hoog die muur is en hoeveel gaten erin zitten."

Ze hebben de wiskunde van deze specifieke blokkenpatronen zo ver doorgevoerd dat ze zelfs negatieve tussenstappen durven te gebruiken, wat leidt tot nieuwe inzichten voor oude problemen.

Titel: Over het Frobenius-getal en het genus van een verzameling semigruppen die repunit-numerieke semigruppen generaliseren

Auteurs: Feihu Liu, Guoce Xin, Suting Ye, en Jingjing Yin.
Datum: 4 maart 2025 (versie 4 van arXiv:2306.03459).

1. Probleemstelling

Het artikel richt zich op het Frobenius-probleem voor numerieke semigruppen. Gegeven een rij van onderling ondeelbare positieve gehele getallen $A = (a_1, a_2, \dots, a_n)$ , wordt de door $A$ gegenereerde numerieke semigroup aangeduid met $\langle A \rangle$ . De twee centrale invarianten die onderzocht worden zijn:

Het Frobenius-getal $F(A)$ : Het grootste gehele getal dat niet in $\langle A \rangle$ kan worden geschreven als een lineaire combinatie met niet-negatieve gehele coëfficiënten.
Het genus $g(A)$ : Het aantal positieve gehele getallen dat niet in $\langle A \rangle$ zit.

Hoewel er voor $n=2$ een gesloten formule bestaat (Sylvester, 1882), is het probleem voor $n \geq 3$ algemeen onoplosbaar in gesloten vorm (Curtis, 1990). De auteurs bestuderen een specifieke, maar zeer brede klasse van semigruppen die generalisaties zijn van bekende families zoals repunit-, Mersenne-, Thabit- en Proth-semigruppen.

De specifieke verzameling die wordt onderzocht, genaamd Collection CNS, wordt gedefinieerd door de generatorrij:
$A = \left(a, ba + d, b^2a + \frac{b^2-1}{b-1}d, \dots, b^ka + \frac{b^k-1}{b-1}d\right)$
waarbij $a, b, k \in \mathbb{P}$ , $d \in \mathbb{Z} \setminus \{0\}$ , en $\gcd(a, d) = 1$ . Een belangrijke innovatie in dit werk is dat $d$ negatief kan zijn, wat de toepasbaarheid op nieuwe families (zoals Proth-semigruppen) mogelijk maakt.

2. Methodologie

De auteurs hanteren een gestructureerde aanpak gebaseerd op de theorie van Apéry-sets en greedy algoritmen.

A. Generalisatie en Collectie GCNS

De auteurs introduceren een bredere verzameling, Collection GCNS, waarbij de coëfficiënten van $a$ en $d$ in de generatoren een recursieve structuur volgen:
$A = (a, h_1a + db_1, h_2a + db_2, \dots, h_ka + db_k)$
met $b_1=1$ , $b_{i+1} = s_i b_i + 1$ (waarbij $s_i$ een stijgende rij is) en $h_i = u b_i + 1$ .

B. Apéry-sets en Minimalisatie

Het kernidee is het gebruik van de Apéry-set van een element $w$ in een semigroup, gedefinieerd als $Ape(A, w) = \{s \in \langle A \rangle \mid s - w \notin \langle A \rangle\}$ . Voor $w=a$ geldt dat de elementen $N_r$ (het kleinste element in $\langle A \rangle$ congruent met $r \pmod a$ ) de Frobenius-getal en het genus bepalen via de formules van Brauer en Shockley:
$F(A) = \max(N_r) - a, \quad g(A) = \frac{1}{a}\sum N_r - \frac{a-1}{2}$

De auteurs reduceren het probleem tot het minimaliseren van een specifieke functie:
$OH_B(M) = \min \left\{ \sum_{i=1}^k h_i x_i \;\Big|\; \sum_{i=1}^k b_i x_i = M, x_i \in \mathbb{N} \right\}$

C. Geordende Sequenties en Greedy Algoritme

Een cruciale stap is het bewijzen dat de rij $B = (b_1, \dots, b_k)$ een geordende rij (orderly sequence) is. Dit betekent dat het greedy-algoritme (waarbij men zo veel mogelijk van het grootste element neemt) altijd de optimale oplossing levert voor het "wisselgeldprobleem" (change-making problem).
Dit wordt bewezen met behulp van de One-Point Theorem (Lemma 2.5), wat garandeert dat voor hun specifieke constructie van $b_i$ en $s_i$ , de greedy-oplossing $grdB(M)$ gelijk is aan de optimale oplossing $optB(M)$.

D. Monotonie en Gewichten

De auteurs definiëren een "gewicht" $w(r)$ voor elk restklasse $r$ gebaseerd op de greedy-presentatie. Ze bewijzen dat onder bepaalde voorwaarden (zoals $ua + d + k - 2 \geq \sum s_i$ ), de functie $N_{dr}(m)$ monotoon stijgend is in $m$ . Hierdoor is het maximum van de Apéry-set altijd te vinden bij $r = a-1$ (of een naburig punt), wat de berekening van $F(A)$ en $g(A)$ vereenvoudigt tot het analyseren van de greedy-presentatie van $a-1$ .

3. Belangrijkste Resultaten

A. Algemene Formules (Theorema 2.12 & 2.13)

Voor de verzameling GCNS worden gesloten formules afgeleid voor $F(A)$ en $g(A)$ , afhankelijk van de greedy-presentatie van $a-1$ .

Frobenius-getal: $F(A) = \sum x_i \cdot a + (a-1)(ua+d) - a$ , waarbij $(x_1, \dots, x_k)$ de greedy-coëfficiënten van $a-1$ zijn.
Genus: Een somformule die afhangt van de som van de coëfficiënten van de greedy-presentaties van alle $r < a$ .

B. Toepassingen op Specifieke Families

De algemene theorie wordt toegepast op diverse bekende en nieuwe families:

Repunit en Mersenne Semigruppen:
- Voor repunit-semigruppen $S(b, n)$ (waarbij $m=d=1$ ) worden de formules vereenvoudigd tot bekende resultaten (Corollary 3.2).
- Voor Mersenne-semigruppen ( $b=2$ ) worden de formules voor $F(S(n))$ en $g(S(n))$ bevestigd (Corollary 3.3).
- Ook het pseudo-Frobenius-getal en het type $t(A)$ worden bepaald voor deze families.
Thabit Semigruppen:
- Voor Thabit-semigruppen $T(n)$ (en hun generalisaties met parameter $d$ ) worden gesloten formules voor $F(A)$ , $g(A)$ en de verzameling pseudo-Frobenius-getallen afgeleid (Theorema 4.1 & 4.4).
Proth Semigruppen (Open Probleem Opgelost):
- De auteurs bestuderen de Proth-semigroup $P_m(n)$ gegenereerd door $\{m2^{n+i} + 1\}$ .
- Ze lossen Open Probleem 1.3 (uit [31]) gedeeltelijk op: het vinden van een formule voor het Frobenius-getal voor willekeurige oneven $m$ .
- Ze leiden formules af voor het geval $m = 2^r + q$ (waarbij $q$ oneven is), afhankelijk van de structuur van de greedy-presentatie van $(2^r+q)2^n$ .
- Voor $q < 50$ wordt een tabel (Tabel 1) gepresenteerd met expliciete formules voor verschillende gevallen van $q$ .
Nieuwe Generalisaties:
- Het artikel introduceert een nieuwe familie van semigruppen (Item 6 in Sectie 6) met generatoren van de vorm $(a, 2a+d, \dots, 2^ka + (2^k-1)d)$ waarbij $a = m(2^k-1) + 2^{k-1}-1$ . Hiervoor worden nieuwe formules voor $F(A)$ en $g(A)$ afgeleid (Theorema 6.1).

4. Significatie en Bijdrage

Unificatie: Het paper biedt een unificerende methode om het Frobenius-probleem op te lossen voor zeven verschillende, eerder losstaande families van numerieke semigruppen. Dit toont aan dat deze families allemaal onder de paraplu van de "Collection GCNS" vallen.
Negatieve Parameter $d$ : Een belangrijke innovatie is het toestaan van een negatieve $d$ . Dit maakt het mogelijk om Proth-semigruppen (waarbij de generatoren van de vorm $m2^k+1$ zijn) te behandelen binnen hetzelfde theoretische raamwerk als de positieve gevallen.
Gedeeltelijke Oplossing Open Probleem: Het artikel biedt een significante stap voorwaarts in het oplossen van het open probleem rondom het Frobenius-getal van Proth-semigruppen voor willekeurige $m$ , door een classificatie op basis van de greedy-presentatie te geven.
Efficiëntie: Door het gebruik van de eigenschap van "geordende sequenties" en het greedy-algoritme, vermijden de auteurs complexe berekeningen en leveren ze directe, gesloten formules die eenvoudig te evalueren zijn.
Pseudo-Frobenius Getallen: Naast het Frobenius-getal en het genus, worden ook de verzamelingen van pseudo-Frobenius-getallen en het type van de semigruppen voor deze families expliciet bepaald, wat zeldzaam is in de literatuur voor dergelijke complexe families.

Conclusie

Dit werk presenteert een krachtige, algemene theoretische structuur die het mogelijk maakt om de fundamentele invarianten van een breed scala aan numerieke semigruppen exact te berekenen. Het combineert combinatorische optimalisatie (greedy algoritmen) met getaltheoretische eigenschappen om zowel bestaande resultaten te bevestigen als nieuwe, complexe gevallen (zoals Proth-semigruppen) aan te pakken.