🔢 mathematics

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

Diese Arbeit untersucht das Frobenius-Problem für eine verallgemeinerte Klasse numerischer Halbgruppen, die Repunit-Halbgruppen umfassen, indem sie Formeln für die Frobenius-Zahl und das Geschlecht herleitet, die auch negative Parameter zulassen und sich auf Spezialfälle wie Mersenne-, Thabit- und Proth-Halbgruppen anwenden lassen.

Ursprüngliche Autoren: Feihu Liu, Guoce Xin, Suting Ye, Jingjing Yin

Veröffentlicht 2026-04-13

📖 4 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Feihu Liu, Guoce Xin, Suting Ye, Jingjing Yin

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

🍕 Die Pizza-Regel: Wie man das größte "unmögliche" Stück findet

Stell dir vor, du hast eine Pizzeria, aber du darfst die Pizzen nur in bestimmten, festgelegten Größen verkaufen. Du hast keine Schere, um sie zu teilen. Du kannst nur ganze Pizzen oder Kombinationen aus deinen festen Größen anbieten.

Nehmen wir an, deine festen Größen sind 3, 5 und 7 Stück.

Du kannst eine 3er-Pizza machen.
Du kannst eine 5er-Pizza machen.
Du kannst eine 3er und eine 5er zusammenlegen (8 Stück).
Du kannst zwei 3er und eine 5er machen (11 Stück).

Aber was ist mit 4 Stück? Oder 1 Stück? Die kannst du nicht machen.
Die Frage, die sich die Autoren dieser Arbeit stellen, ist: Was ist die größte Anzahl von Stücken, die du überhaupt NICHT verkaufen kannst?

In der Mathematik nennt man das die Frobenius-Zahl.

Bei 3 und 5 ist die größte unmögliche Zahl 7 (denn 8=3+5, 9=3+3+3, 10=5+5, und alles danach geht auch).
Die Genus (ein weiterer Begriff im Text) ist einfach die Anzahl aller unmöglichen Zahlen (bei 3 und 5 sind das 1, 2, 4, 7 – also insgesamt 4 Stück).

🧩 Das große Rätsel: Wenn die Regeln kompliziert werden

Für zwei Zahlen (wie 3 und 5) gibt es eine einfache Formel. Aber sobald man drei oder mehr Zahlen hat, wird es extrem schwierig. Es gibt keine einfache "Rezept-Formel", die für alle Fälle funktioniert.

Die Autoren dieses Papiers haben sich eine spezielle Art von Zahlenreihen angesehen, die wie eine Reise mit einem Bus funktionieren:

Du startest mit einer Basiszahl $a$ (die erste Haltestelle).
Die nächsten Haltestellen sind nicht zufällig, sondern folgen einem strengen Muster:
- Die zweite Zahl ist $a$ plus etwas Kleines ( $d$ ).
- Die dritte Zahl ist $a$ plus etwas Größeres ( $b \cdot d$ ).
- Die vierte ist $a$ plus noch mehr ( $b^2 \cdot d$ ), und so weiter.

Das Besondere an dieser Arbeit ist, dass der "Bus" auch rückwärts fahren darf! Das bedeutet, das $d$ kann eine negative Zahl sein. Das ist wie eine Pizzeria, bei der du nicht nur Pizzen hinzufügen, sondern auch "Schulden" annehmen darfst, solange du am Ende wieder eine ganze Pizzeria hast.

🚀 Die Lösung: Der "Gierige" Algorithmus

Wie finden die Autoren die Lösung? Sie nutzen eine clevere Strategie, die sie "Gierige Strategie" (Greedy Algorithm) nennen.

Stell dir vor, du musst eine bestimmte Summe (z. B. 23) mit deinen Pizzagrößen (1, 3, 7, 15) erreichen.

Der "Gierige" nimmt immer zuerst die größtmögliche Pizzagröße, die noch passt.
Bei 23 nimmt er zuerst die 15. (Rest: 8).
Dann die 7. (Rest: 1).
Dann die 1. (Rest: 0).
Ergebnis: 15 + 7 + 1.

Die Autoren haben bewiesen, dass bei ihren speziellen Zahlenreihen diese "gierige" Methode immer die beste und kürzeste Kombination liefert. Das ist wie ein perfekter Fahrplan, bei dem man nie einen Umweg braucht.

🌟 Was haben sie herausgefunden?

Mit dieser "gierigen" Methode haben sie Formeln entwickelt, um für diese speziellen Pizzareihen sofort zu sagen:

Die Frobenius-Zahl: Was ist die größte Zahl, die man niemals bilden kann?
Die Genus: Wie viele Zahlen gibt es insgesamt, die man nicht bilden kann?

Sie haben gezeigt, dass ihre Formeln viele bekannte mathematische "Klassiker" abdecken, die in der Vergangenheit als separate Probleme behandelt wurden:

Mersenne-Zahlen: (Wie bei Computern: 2, 4, 8, 16...)
Repunit-Zahlen: (Zahlen wie 11, 111, 1111...)
Thabit-Zahlen: (Eine spezielle Familie von Zahlen, die in der Zahlentheorie beliebt sind).
Proth-Zahlen: (Eine noch schwierigere Gruppe, bei der sie ein Teilproblem gelöst haben, das vorher offen war).

💡 Warum ist das wichtig?

Stell dir vor, du bist ein Architekt. Früher musstest du für jedes neue Gebäude (jede neue Zahlenreihe) von vorne anfangen und mühsam jedes Steinchen einzeln prüfen.
Diese Autoren haben einen Baukasten entwickelt. Wenn du ein Gebäude aus ihren speziellen Steinen baust, kannst du sofort auf den Bauplan schauen und sagen: "Hier ist die größte Lücke, und hier ist die Gesamtzahl der Lücken."

Sie haben auch einen neuen Weg gefunden, um mit negativen Zahlen in diesen Reihen umzugehen, was wie das Entdecken einer neuen Dimension in der Mathematik ist.

Zusammenfassend:
Die Autoren haben ein komplexes mathematisches Rätsel gelöst, indem sie eine einfache Regel (die "gierige" Methode) auf eine ganze Familie von Zahlenmustern angewendet haben. Sie haben damit alte Probleme für bekannte Zahlenreihen gelöst und sogar einen neuen Weg für noch schwierigere Fälle (Proth-Zahlen) gefunden. Es ist, als hätten sie den Master-Schlüssel für eine ganze Klasse von mathematischen Schlosssystemen gefunden.

Titel:

Zur Frobenius-Zahl und zum Geschlecht einer Sammlung von Halbgruppen, die Repunit-Zahlenhalbgruppen verallgemeinern.

1. Problemstellung

Das Paper adressiert das klassische Frobenius-Problem für numerische Halbgruppen. Gegeben sei eine Folge $A = (a_1, a_2, \dots, a_n)$ teilerfremder positiver Integers.

Die Frobenius-Zahl $F(A)$ ist die größte ganze Zahl, die nicht in der von $A$ erzeugten numerischen Halbgruppe $\langle A \rangle$ liegt.
Das Geschlecht $g(A)$ ist die Anzahl der positiven ganzen Zahlen, die nicht in $\langle A \rangle$ liegen.

Für $n \ge 3$ gibt es im Allgemeinen keine geschlossenen Formeln für $F(A)$ und $g(A)$ . Das Ziel dieses Papers ist es, eine einheitliche Methode zu entwickeln, um explizite Formeln für $F(A)$ und $g(A)$ für eine breite Klasse von Folgen zu finden, die bekannte Spezialfälle wie Repunit-, Mersenne-, Thabit- und Proth-Zahlenhalbgruppen umfasst. Ein innovativer Aspekt ist die Zulassung negativer Werte für den Parameter $d$ in der Konstruktion der Erzeuger.

2. Methodik

Die Autoren führen eine verallgemeinerte Sammlung von Folgen ein, genannt Collection GCNS (Generalized Collection of Numerical Semigroups).
Die Erzeugermenge $A$ hat die Form:
$A = (a, h_1a + db_1, h_2a + db_2, \dots, h_ka + db_k)$
mit spezifischen rekursiven Bedingungen für die Sequenzen $b_i$ und $h_i$ :

$b_1 = 1$ , $b_{i+1} = s_i b_i + 1$ mit $s_i \ge s_{i-1}$ .
$h_i = u b_i + 1$ für ein $u \in \mathbb{P}$ .

Kernideen der Methode:

Apéry-Menge: Die Berechnung von $F(A)$ und $g(A)$ basiert auf der Analyse der Apéry-Menge $Ape(A, a)$ bezüglich des kleinsten Erzeugers $a$ . Nach einem bekannten Lemma von Brauer und Shockley hängen $F(A)$ und $g(A)$ direkt von den maximalen Elementen und der Summe der Elemente dieser Menge ab.
Greedy-Algorithmus und Ordnung: Die Autoren nutzen die Eigenschaft, dass die Sequenz $B = (b_1, \dots, b_k)$ unter den gegebenen Bedingungen ordnungsgemäß (orderly) ist. Das bedeutet, dass das Minimierungsproblem (Änderungsproblem) für die Darstellung von Zahlen als Linearkombination von $b_i$ durch einen Greedy-Algorithmus gelöst werden kann.
Gewichtsfunktion: Sie definieren eine Gewichtsfunktion $w(r)$ basierend auf der Greedy-Darstellung von $r$ . Ein zentrales Ergebnis ist der Nachweis, dass unter bestimmten Bedingungen ( $s_i < u+1$ ) diese Gewichte monoton mit dem Index $r$ wachsen. Dies ermöglicht es, das Maximum der Apéry-Menge direkt zu identifizieren, ohne alle Elemente explizit berechnen zu müssen.
Minimierungsproblem: Das Problem wird auf die Lösung eines vereinfachten Minimierungsproblems $OH_B(M)$ reduziert, das durch den Greedy-Algorithmus effizient lösbar ist.

3. Wichtige Beiträge und Ergebnisse

A. Allgemeine Formeln (Collection GCNS)

Unter den Bedingungen $ua + d + k - 2 \ge \sum_{i=1}^{k-1} s_i$ und $s_i < u+1$ leiten die Autoren geschlossene Formeln ab:

Frobenius-Zahl: $F(A)$ wird durch das Gewicht der Greedy-Darstellung von $a-1$ bestimmt.
$F(A) = \sum_{i=1}^k x_i \cdot a + (a-1)(ua+d) - a$
wobei $(x_1, \dots, x_k)$ die Greedy-Darstellung von $a-1$ bezüglich $B$ ist.
Geschlecht: Eine Formel für $g(A)$ wird basierend auf der Summe der Gewichte aller $r \in \{0, \dots, a-1\}$ hergeleitet.
Pseudo-Frobenius-Zahlen: Für bestimmte Fälle wird auch die Menge der pseudo-Frobenius-Zahlen $PF(A)$ und der Typ $t(A)$ bestimmt.

B. Spezialisierungen auf bekannte Halbgruppen

Die allgemeinen Formeln werden auf spezifische bekannte Familien angewendet, was zu vereinfachten, expliziten Formeln führt:

Repunit-Zahlenhalbgruppen: Für $A = \langle \{ \frac{b^{n+i}-1}{b-1} \} \rangle$ werden $F(A)$ und $g(A)$ bestätigt und erweitert.
Mersenne-Zahlenhalbgruppen: Der Spezialfall $b=2$ für Repunits wird behandelt.
Thabit-Zahlenhalbgruppen: Für Folgen der Form $3 \cdot 2^n - 1$ etc. werden neue Formeln für $F(A)$ , $g(A)$ und $PF(A)$ hergeleitet, die frühere Ergebnisse verallgemeinern.
Proth-Zahlenhalbgruppen: Dies ist ein Hauptbeitrag. Die Autoren lösen teilweise das Open Problem 1.3 aus [31]. Für $P_m(n)$ $P_{m} (n)$ mit $m = 2^r + q$ $m = 2^{r} + q$ (wobei $q$ $q$ ungerade) werden Formeln für $F(P_m(n))$ $F (P_{m} (n))$ basierend auf der Greedy-Darstellung von $(2^r+q)2^n$ $(2^{r} + q) 2^{n}$ angegeben.
- Es wird eine Tabelle (Table 1) bereitgestellt, die die Greedy-Darstellungen für $q < 50$ auflistet und damit explizite Formeln für diese Fälle ermöglicht.

C. Negative Parameter $d$

Ein wesentlicher Innovationsschritt ist die Behandlung von negativen Werten für $d$ . Viele frühere Arbeiten beschränkten sich auf $d > 0$ . Die Autoren zeigen, dass ihre Methode auch für $d < 0$ funktioniert, solange die Erzeuger positiv bleiben ( $h_i a + d b_i > 1$ ). Dies ist entscheidend für die Behandlung von Proth-Halbgruppen, wo $d = -1$ auftritt.

4. Signifikanz

Einheitlicher Rahmen: Das Paper bietet einen einheitlichen theoretischen Rahmen, der zahlreiche zuvor isoliert untersuchte Fälle (Repunit, Mersenne, Thabit, Proth) unter einer einzigen Theorie vereint.
Lösung offener Probleme: Es liefert einen signifikanten Fortschritt beim Verständnis der Proth-Zahlenhalbgruppen, indem es Formeln für die Frobenius-Zahl für eine breite Klasse von Parametern $m$ bereitstellt, für die zuvor keine allgemeinen Formeln existierten.
Algorithmische Effizienz: Die Nutzung der Ordnungseigenschaft (orderly sequences) und des Greedy-Algorithmus ermöglicht es, komplexe kombinatorische Probleme auf einfache Berechnungen der Greedy-Darstellung zurückzuführen.
Erweiterung des Gültigkeitsbereichs: Durch die Einbeziehung negativer $d$ -Werte wird der Anwendungsbereich der Theorie auf neue Klassen von Halbgruppen ausgeweitet.

Zusammenfassung

Die Autoren entwickeln eine mächtige Methode zur Berechnung der Frobenius-Zahl und des Geschlechts für eine verallgemeinerte Klasse numerischer Halbgruppen. Durch die Ausnutzung der Eigenschaften von "ordnungsgemäßen" Sequenzen und Greedy-Darstellungen leiten sie geschlossene Formeln ab, die nicht nur bekannte Ergebnisse für Repunit- und Mersenne-Halbgruppen bestätigen, sondern auch neue, explizite Formeln für Thabit- und insbesondere für Proth-Halbgruppen liefern. Die Arbeit stellt einen bedeutenden Schritt zur Lösung des Frobenius-Problems für strukturierte Folgen dar.