🔢 mathematics

The Frobenius Formula for $A=(a,ha+d,ha+b_2d,...,ha+b_kd)$

Dit artikel breidt de "stabiele" eigenschap van het Frobeniusgetal uit van kwadratische rijen naar de meer algemene rij $A=(a, ha+d, ha+b_2d, \dots, ha+b_kd)$ , waarbij een karakterisering als congruentieklassenfunctie wordt gegeven voor voldoende grote $a$ en specifieke gevallen worden uitgewerkt.

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

Gepubliceerd 2026-04-13

📖 4 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 bak met munten hebt, maar niet van elke waarde. Je hebt munten van 1, 5, 11 en 14 euro. Je mag deze munten combineren om bedragen te betalen. Je kunt bijvoorbeeld 19 euro betalen (5 + 14) of 20 euro (5 + 5 + 5 + 5). Maar er is een groot probleem: sommige bedragen kun je nooit betalen, hoe vaak je ook probeert.

De vraag die wiskundigen al eeuwen stellen, is: Wat is het grootste bedrag dat je nooit kunt betalen? Dit noemen ze het "Frobenius-getal".

Dit artikel van Liu, Xin, Ye en Yin is als een slimme gids die een nieuwe manier vindt om dit grootste "onbetaalbare bedrag" te voorspellen, zelfs als je munten heel speciaal zijn samengesteld.

Hier is de uitleg in simpele taal, met een paar creatieve vergelijkingen:

1. Het Muntenspel (De Basis)

Stel je hebt een munt van waarde $a$ . Daarnaast heb je een setje "speciale munten" die allemaal gebaseerd zijn op een patroon:

Eén munt is $a$ plus iets kleins ( $d$ ).
De volgende is $a$ plus iets anders ( $b_2 \cdot d$ ).
Enzovoort.

Het artikel onderzoekt wat er gebeurt als je deze munten gebruikt om getallen te maken. Als je getal $a$ groot genoeg is, gedraagt het "onbetaalbare bedrag" zich op een heel voorspelbare manier.

2. De "Stabiele" Trein (Het Grote Geheim)

De auteurs ontdekten iets fascinerends: als je naar de "speciale munten" kijkt (de $b$ -waarden), gedraagt het systeem zich als een trein op een spoor.

Stel je voor dat je een trein hebt die stopt op elke kilometerpaal.

Als je ver genoeg van het begin bent (wanneer $a$ groot is), zie je dat het patroon van de "onbetaalbare bedragen" stabiel wordt.
Het is alsof de trein elke keer dat hij een bepaalde afstand ( $b_k$ ) aflegt, precies hetzelfde patroon herhaalt, alleen dan een stukje verderop.

De auteurs noemen dit de "Stabiele Eigenschap". Het betekent dat je niet elke mogelijke combinatie hoeft uit te rekenen. Je hoeft alleen maar te kijken naar een klein stukje van het spoor (de eerste paar kilometers), en dan weet je precies hoe het eruitziet voor de rest van de wereld.

3. De "Orde" van de Munten

Soms zijn de munten heel ordelijk. Stel je hebt munten van 1, 2, 5 en 10. Als je een bedrag wilt betalen, pak je altijd eerst de grootste munt die past, dan de volgende, enzovoort. Dit noemen ze een "Ordelijke Reeks".

Bij deze ordelijke munten is het voorspellen van het grootste onbetaalbare bedrag heel makkelijk. Het is alsof je een simpele formule hebt die je in je hoofd kunt houden.
Maar als de munten "chaotisch" zijn (bijvoorbeeld 1, 6, 13), werkt die simpele strategie niet altijd. Dan moet je een ingewikkelder kaart gebruiken.

De auteurs hebben bewezen dat zelfs bij deze chaotische munten, als je getal $a$ groot genoeg is, het patroon toch weer "ordelijk" wordt en voorspelbaar is.

4. De Magische Formule (De "Restklassen")

De belangrijkste ontdekking is dit:
Het grootste onbetaalbare bedrag hangt af van het getal $a$ , maar niet zomaar. Het hangt af van welke "kleur" $a$ heeft als je het deelt door het grootste getal in je setje.

Stel je voor dat je alle getallen in de wereld in 14 verschillende bakjes gooit (bakje 0, bakje 1, ..., bakje 13), afhankelijk van wat de rest is als je door 14 deelt.

Als $a$ in bakje 0 zit, is het antwoord een bepaalde formule.
Als $a$ in bakje 1 zit, is het antwoord een heel andere formule.

De auteurs hebben laten zien dat voor elk van deze 14 bakjes, het antwoord een kromme lijn is (een kwadratische formule). Het is alsof je voor elke kleur een eigen landkaart hebt, en op die kaart staat precies geschreven hoe groot het grootste onbetaalbare bedrag is.

5. Waarom is dit belangrijk?

Vroeger was het vinden van dit getal voor complexe sets munten als het zoeken naar een naald in een hooiberg. Je moest alles uitproberen.
Met deze nieuwe methode kunnen wiskundigen (en computers) dit probleem snel oplossen. Het is alsof ze van een wandeling door een doolhof zijn gegaan naar het vliegen met een helikopter: je ziet het hele patroon in één keer en kunt de uitkomst direct berekenen.

Samengevat:
Dit artikel zegt: "Als je genoeg munten hebt en je kijkt naar een groot genoeg getal $a$ , dan is het grootste bedrag dat je niet kunt betalen niet willekeurig. Het volgt een strak patroon dat je kunt beschrijven met een paar simpele formules, afhankelijk van hoe je getal $a$ zich verhoudt tot de grootste munt."

Het is een mooie combinatie van logica, patronen en een beetje wiskundige magie om het onmogelijke (het vinden van een getal) toch mogelijk te maken.

Titel: De Frobenius-formule voor $A = (a, ha + d, ha + b_2d, \dots, ha + b_kd)$

Auteurs: Feihu Liu, Guoce Xin, Suting Ye, Jingjing Yin.
Wiskundig Onderwerp: 11D07 (Lineaire Diophantische vergelijkingen), 05A15, 11B75, 11D04.

1. Probleemstelling

Het artikel richt zich op het Frobenius-getal $g(A)$ , gedefinieerd als het grootste gehele getal dat niet kan worden voorgesteld als een lineaire combinatie van de elementen van een rij $A = (a_1, a_2, \dots, a_n)$ met niet-negatieve gehele coëfficiënten, waarbij $\gcd(A) = 1$ .

Specifiek onderzoeken de auteurs de rij $A(a) = (a, ha + dB)$, waarbij:

$B = (b_1, b_2, \dots, b_k)$ een rij van positieve gehele getallen is (met $b_1 = 1$ in de hoofdsecties).
$a, h, d$ positieve gehele getallen zijn.
$\gcd(a, d) = 1$ .
De rij $A$ heeft de vorm: $(a, ha + db_1, ha + db_2, \dots, ha + db_k)$ .

Het probleem is dat er voor $n \geq 3$ geen gesloten formule bestaat voor $g(A)$ in het algemeen. Eerdere werken hebben zich gericht op specifieke gevallen, zoals kwadratische rijen ( $B = (1, 2^2, \dots, k^2)$ ). Dit werk generaliseert deze resultaten naar een bredere klasse van rijen.

2. Methodologie

De auteurs gebruiken een combinatorische aanpak gebaseerd op de theorie van numerieke semigruppen en Apéry-sets.

Apéry-set: Voor een semigrup $R$ $R$ gegenereerd door $A$ $A$ en een element $a \in A$ $a \in A$ , is de Apéry-set $Ape(A, a) = \{N_0, N_1, \dots, N_{a-1}\}$ $A p e (A, a) = {N_{0}, N_{1}, \dots, N_{a - 1}}$ , waarbij $N_r$ $N_{r}$ het kleinste element in $R$ $R$ is dat congruent is aan $r \pmod a$ $r (mod a)$ .
- Volgens een stelling van Brauer en Shockley geldt: $g(A) = \max(N_r) - a$ .
Minimalisatieprobleem: De berekening van $N_r$ wordt teruggebracht tot het minimaliseren van het aantal elementen uit $B$ nodig om een getal $M$ te vormen. Dit wordt aangeduid als $O_B(M) = \min \{ \sum x_i \mid \sum b_i x_i = M \}$ .
Genererende Functies: De auteurs introduceren een genererende functie $F(t, q)$ en een operator $\circledast$ om alleen de optimale representaties (minimale som van coëfficiënten) te extraheren. Dit stelt hen in staat om $O_B(M)$ efficiënt te berekenen.
Stabiliteitseigenschap ("Stable Property"): Een kernconcept in dit artikel is het bewijzen dat voor voldoende grote $M$ , de functie $O_B(M)$ een lineaire "stabiliteit" vertoont: $O_B(b_k + r) = O_B(r) + 1$ . Dit reduceert het probleem van het berekenen van $O_B(M)$ voor alle $M$ tot het berekenen van een eindig aantal waarden.
Ordele Sequenties (Orderly Sequences): Een rij $B$ heet "ordele" als de "greedy strategy" (altijd het grootste mogelijke element kiezen) altijd de optimale oplossing geeft, d.w.z. $O_B(M) = G_B(M)$ . Voor deze rijen zijn de grenzen voor $a$ veel scherper.

3. Belangrijkste Bijdragen en Resultaten

A. Generalisatie van de "Stable" Eigenschap

De auteurs bewijzen dat de stabiliteitseigenschap die eerder werd ontdekt voor kwadratische rijen, ook geldt voor algemene rijen $B = (1, b_2, \dots, b_k)$ .

Lemma 2.5: Er bestaat een drempelwaarde $M_0$ zodanig dat voor alle $r \geq M_0$ , geldt: $O_B(b_k + r) = O_B(r) + 1$ .
Dit leidt tot een polynoomtijd-algoritme (in $b_k$ ) om $O_B(M)$ te berekenen voor alle $M$ .

B. Karakterisering als "Congruentieklasse-functie"

Het centrale resultaat (Stelling 3.3) is dat voor voldoende grote $a$ , het Frobenius-getal $g(A(a))$ een congruentieklasse-functie modulo $b_k$ is.

De formule is onderverdeeld in $b_k$ klassen, afhankelijk van $a \pmod{b_k}$ .
Binnen elke klasse is $g(A(a))$ een kwadratische polynoom in $a$ met de leidende coëfficiënt $h/b_k$ .
De formule heeft de vorm:
$g(A(a)) = (w_j h - 1)a + r_j d + (ha + b_k d) \left( \left\lfloor \frac{a}{b_k} \right\rfloor - u - c + 1 \right)$
waarbij $w_j$ en $r_j$ sequenties zijn die afhangen van de rest $j = a \pmod{b_k}$ , en $u, c$ constanten zijn die afhangen van de structuur van $B$ .

C. Specifieke Gevallen en Scherpe Grenzen

De auteurs leiden expliciete formules af voor verschillende specifieke rijen $B$ :

Algemene rijen: Formules voor $B = (1, 2, b, b+1)$ , $B = (1, b, 2b-1)$ , en $B = (1, 2, \dots, k, K)$ .
Ordele rijen (Theorema 4.3): Als $B$ $B$ een ordele rij is, is de ondergrens voor $a$ $a$ aanzienlijk lager ( $a \geq (c-1)b_k$ $a \geq (c - 1) b_{k}$ ) en is de berekening eenvoudiger.
- Voorbeeld: Voor $B = (1, 5, 9)$ wordt een exacte formule gegeven voor $a \geq 27$ .
Geval $b_1 > 1$ : In Sectie 5 wordt aangetoond dat de methode ook werkt als de kleinste elementen van $B$ groter zijn dan 1 (bijv. $B=(4, 8, 15, 17)$ ), hoewel de berekening complexer wordt omdat niet alle getallen representeerbaar zijn.

D. Berekeningscomplexiteit

Het artikel biedt een polynoomtijd-algoritme (in termen van $b_k$ ) om de Frobenius-formule te berekenen voor de gegeven klasse van rijen. Dit is een significant verbetering ten opzichte van brute-force methoden of methoden die alleen voor zeer specifieke rijen werken.

4. Betekenis en Impact

Unificatie: Het werk verenigt eerder bekende resultaten over kwadratische rijen en andere specifieke sequenties onder één algemene theorie voor rijen van de vorm $(a, ha + dB)$.
Structuur: Het onthult een diepe structurele eigenschap: voor grote $a$ gedraagt het Frobenius-getal zich voorspelbaar en periodiek (modulo $b_k$ ) als een kwadratische functie.
Praktische Toepasbaarheid: Door de "Stable" eigenschap en het gebruik van genererende functies, kunnen onderzoekers nu efficiënt de Frobenius-getallen berekenen voor een veel bredere klasse van numerieke semigruppen dan voorheen mogelijk was.
Verwijzing naar Open Problemen: Het lost een open probleem op dat eerder werd geformuleerd door Einstein et al. (2015) voor kwadratische rijen, en generaliseert dit naar een bredere context.

Conclusie

Liu et al. hebben een krachtige theoretische raamwerk ontwikkeld om het Frobenius-getal te karakteriseren voor een uitgebreide familie van rijen. Hun belangrijkste ontdekking is dat de complexiteit van het probleem "stabiliseert" voor grote waarden van $a$ , wat leidt tot een elegante, modulaire formule. Dit biedt zowel een theoretisch inzicht als een praktisch algoritme voor de berekening van deze getallen, met name voor rijen die "ordele" eigenschappen vertonen.