🔢 mathematics

Bounds for Greedy $B_h$ -sets

Diese Arbeit etabliert neue nicht-triviale untere und obere Schranken für das $k$ -te Element der gierigen $B_h$ -Menge, indem sie spezifisch präzise asymptotische Abschätzungen für $k \ge 5$ sowie eine allgemeine untere Schranke für alle $k \ge 1$ liefert und zudem eine Vermutung über das exakte asymptotische Verhalten des fünften Elements vorschlägt.

Ursprüngliche Autoren: Kevin O'Bryant

Veröffentlicht 2026-07-09

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Kevin O'Bryant

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

Stellen Sie sich vor, Sie bauen einen Turm aus nummerierten Blöcken, aber Sie haben eine sehr strenge Regel: Keine zwei verschiedenen Gruppen von Blöcken dürfen die gleiche Summe ergeben. Wenn Sie $h$ Blöcke auswählen und sie zusammenzählen, muss diese Summe einzigartig für genau diese spezifische Gruppe von Blöcken sein. Mathematiker nennen solche speziellen Kollektionen $B_h$ -Mengen.

Stellen Sie sich vor, Sie wollen den kleinstmöglichen Turm bauen, der dieser Regel folgt. Sie beginnen mit dem Block 0, suchen dann nach der nächstkleinsten Zahl, die Sie hinzufügen können, ohne die Regel zu verletzen. Dann suchen Sie nach der nächstkleinsten Zahl danach, und so weiter. Dies wird als Greedy-Algorithmus bezeichnet. Es ist wie ein Spiel, bei dem man immer das günstigste, kleinste verfügbare Objekt wählt, das das Budget nicht sprengt.

Die Arbeit von Kevin O'Bryant beschäftigt sich damit, wie groß diese "nächsten" Blöcke werden, während der Turm immer höher wächst. Der Autor versucht vorherzusagen, wie groß der 5., 6., 7. und sogar höhere Blöcke sind, abhängig davon, wie streng die "keine Duplikate bei Summen"-Regel (dargestellt durch die Zahl $h$ ) ist.

Die große Entdeckung: Der 5. Block

Die Hauptleistung des Autors besteht darin, endlich feste Grenzen für die Größe des 5. Blocks in diesem Turm (bezeichnet als $\gamma_5$ ) gesetzt zu haben.

Vor dieser Arbeit wussten wir, dass der 5. Block irgendwo zwischen 0 und einer sehr großen Zahl lag, aber wir hatten keinen festen Griff auf ihn. Diese Arbeit beweist zwei Dinge:

Die untere Schranke (Der Boden): Der 5. Block ist definitiv mindestens so groß wie $\frac{1}{8}h^4 + \frac{1}{2}h^3$ . Betrachten Sie dies als einen konkreten Boden, unter den man nicht graben kann. Egal wie Sie es versuchen, der 5. Block wird nicht kleiner als dieser Wert sein.
Die obere Schranke (Die Decke): Der 5. Block ist definitiv kleiner als etwa $0,467214 \times h^4$ (plus einige kleinere Terme). Dies ist eine Decke, die der Block nicht erreichen kann.

Wir wissen also, dass der 5. Block in einem spezifischen "Apartment" zwischen diesen beiden Zahlen lebt.

Das größere Bild: Blöcke 6 und höher

Für den 6. Block und alles danach ( $k \ge 6$ ) liefert der Autor noch keine einzelne perfekte Formel. Stattdessen liefert er ein Rezept, um eine "Decke" zu berechnen, wie groß diese Blöcke werden können.

Die Arbeit führt eine Zahlenfolge namens $\alpha_k$ ein (wie $\alpha_6 = 0,382978$ , $\alpha_7 = 0,269877$ , usw.). Diese Zahlen fungieren als eine schrumpfende Grenze. Der Autor beweist, dass für jeden Block $k$ (wobei $k \ge 5$ ) die Größe dieses Blocks niemals folgendes überschreiten wird:
$\alpha_k \times h^{k-1}$
plus ein wenig zusätzliches "Rauschen", das mit steigendem $h$ kleiner wird.

Die Arbeit gibt eine spezifische Formel an, um die nächste $\alpha$ -Zahl zu berechnen, wenn man die aktuelle kennt, aber dieser rekursive Schritt funktioniert speziell für den 7. Block und darüber hinaus (die Berechnung von $\alpha_{k+1}$ aus $\alpha_k$ erfordert $k \ge 7$ ). Für den 6. Block liefert die Arbeit einen spezifischen konstanten Wert, der aus früheren Schritten abgeleitet wurde. Es ist wie ein mathematisches Fließband: Man füttert das Limit für den 6. Block ein, und die Maschine spuckt das Limit für den 7. Block aus, und so weiter.

Was die Arbeit nicht sagt (und was sie ausschließt)

Es ist sehr wichtig zu wissen, was diese Arbeit nicht tut, denn der Autor ist sehr vorsichtig dabei:

Sie löst nicht das gesamte Rätsel. Der Autor stellt explizit fest, dass er zwar die Grenzen für den 5. Block gefunden hat, aber noch nicht die exakte Formel für den 5. Block gefunden hat.
Sie behauptet nicht, dass der 5. Block exakt $\frac{1}{3}h^4$ ist. Der Autor mutmaßt (vermutet basierend auf Mustern), dass der 5. Block für große $h$ exakt $\frac{1}{3}h^4$ sein könnte, gibt aber zu, dass dies nur eine Vermutung ist. Er hat dies nicht bewiesen.
Sie behauptet nicht, dass die Blöcke einfache Polynome sind. Der Autor ist skeptisch, dass alle Blöcke ewig einem einfachen, glatten Polynom-Muster folgen. Während die ersten Blöcke (0 bis 4) als "Quasi-Polynome" bekannt sind (Polynome, die sich leicht ändern, je nachdem, welchen Rest die Division von $h$ durch eine Zahl ergibt), bezweifelt der Autor, dass dieses Muster für jeden einzelnen Block ewig anhält.

Die "verbotene" Zone

Die Arbeit erklärt auch eine "verbotene Zone" für den nächsten Block. Wenn man einen Turm aus Blöcken hat, gibt es nur eine endliche Anzahl von ganzen Zahlen, die man hinzufügen könnte, ohne die Regeln zu brechen. Die Arbeit berechnet exakt, wie viele "schlechte" Zahlen existieren, die man nicht wählen kann. Es stellt sich heraus, dass es für jede bestehende Turmkonstruktion nur eine begrenzte Anzahl von "Fallen"-Zahlen gibt, die die $B_h$ -Eigenschaft ruinieren würden, und dass sich alle in einem spezifischen Bereich befinden.

Das Geheimnis des 6. Blocks

Der Autor enthält eine Tabelle von Zahlen für den 6. Block ( $\gamma_6$ ) für verschiedene Werte von $h$ , die von einem Computer berechnet wurden. Beim Blick auf diese Zahlen muss der Autor jedoch zugeben: "Es wurde bisher keine Formel vermutet."
Dies ist ein wenig so, als würde man eine Zahlenfolge betrachten und sagen: "Wir wissen, welche sie sind, aber wir haben keine Ahnung, welche Regel sie erzeugt." Der Autor listet sogar die ersten 33 Werte von $\gamma_6$ auf und stellt fest, dass noch niemand ein Muster für sie gefunden hat.

Die offenen Fragen

Die Arbeit endet mit der Auflistung der Mysterien, die weiterhin ungelöst sind:

Kann man beweisen, dass der 5. Block exakt $\frac{1}{3}h^4$ ist?
Können wir Formeln für den 6., 7. und höhere Blöcke finden?
Sind diese Blöcke in einem mathematischen Sinne gleichmäßig verteilt oder häufen sie sich auf seltsame Weise? (Der Autor stellt fest, dass sie für den 2. Block auf eine Weise zu clustern scheinen, die nicht zufällig ist).
Gibt es eine spezifische Zahl (wie etwa 33), die niemals die Differenz zwischen zwei Blöcken im Turm sein kann? (Der Autor stellt fest, dass für den 2. Block jede Zahl von 1 bis 87 als Differenz erscheint, außer 33, was eine seltsame Koinzidenz ist).

Kurz gesagt: Diese Arbeit baut einen stabilen Zaun um den 5. Block und stellt eine schrumpfende Leiter für alle Blöcke darüber bereit, aber die exakte Form des Turms und die geheimen Formeln für die höheren Blöcke bleiben ein Geheimnis, das auf den nächsten Entdecker wartet.

Technische Zusammenfassung: Schranken für die gierige $B_h$ -Menge

Problemstellung
Die vorliegende Arbeit untersucht das asymptotische Verhalten des gierigen Algorithmus (Greedy-Algorithmus) bei der Konstruktion von $B_h$ -Mengen. Eine Menge $A$ von nichtnegativen ganzen Zahlen wird als $B_h$ -Menge definiert, wenn jede Lösung der Gleichung $a_1 + \dots + a_h = b_1 + \dots + b_h$ (wobei $a_i, b_i \in A$ ) impliziert, dass die Multimengen $\{a_1, \dots, a_h\}$ und $\{b_1, \dots, b_h\}$ identisch sind. Das primäre Untersuchungsobjekt ist die gierige $B_h$ -Menge, bezeichnet als $G(h) = \{\gamma_0, \gamma_1, \gamma_2, \dots\}$ , die lexikographisch konstruiert wird, indem $\gamma_0 = 0, \gamma_1 = 1$ gesetzt wird und $\gamma_{k+1}$ die kleinste ganze Zahl ist, so dass $\{\gamma_0, \dots, \gamma_{k+1}\}$ eine $B_h$ -Menge bleibt.

Das zentrale Problem der Arbeit besteht darin, die Wachstumsrate des $k$ -ten Elements $\gamma_k(h)$ als Funktion von $h$ für ein festes $k$ zu bestimmen. Während exakte Formeln für $k \le 4$ bekannt sind, blieb das Verhalten für $k \ge 5$ jenseits der computergestützten Enumeration weitgehend unerforscht. Die Arbeit zielt darauf ab, nicht-triviale obere und untere Schranken für $\gamma_k(h)$ zu etablieren, wobei insbesondere das fünfte Element $\gamma_5(h)$ sowie allgemeine Schranken für $k \ge 5$ im Fokus stehen.

Methodik
Der Autor verwendet eine Kombination aus kombinatorischer Analyse, rekursiver Schrankenbildung und detaillierter Fallenumeration:

Kombinatorische Schranken: Die Arbeit nutzt die Beobachtung, dass die Anzahl der distinkten $h$ -fachen Summen einer Menge der Größe $k+1$ gleich $\binom{k+h}{k}$ ist. Da diese Summen im Intervall $[h\gamma_0, h\gamma_k]$ liegen müssen, ergibt dies eine Basis-Unterschranke für $\gamma_k(h)$ .
Die „Mex“-Charakterisierung: Ein zentrales Lemma etabliert, dass $\gamma_{k+1} = \text{mex}(F^{(k)})$ , wobei $F^{(k)}$ die Menge aller ganzen Zahlen ist, die als $\frac{1}{r}\sum_{i=1}^k \gamma_i(m_i - m'_i)$ unter spezifischen Beschränkungen der Vielfachheiten $m_i, m'_i$ darstellbar sind. Diese Charakterisierung ermöglicht es dem Autor, $\gamma_{k+1}$ durch das Zählen der „verbotenen“ Werte in $F^{(k)}$ , die einen bestimmten Schwellenwert überschreiten, zu begrenzen.
Konstruktion der Untergrenze ( $\gamma_5$ ): Um die Untergrenze für $\gamma_5(h)$ zu beweisen, definiert der Autor eine spezifische Menge von Ganzzahlvektoren $\Delta$ , welche die gültigen Koeffizientenkombinationen der ersten vier Elemente repräsentiert. Durch die Ordnung dieser Vektoren nach dem lexikographischen Prinzip (basierend auf einer spezifischen „Odometer“-ähnlichen Ordnung) und die Analyse des Bildes dieser Vektoren unter dem Skalarprodukt mit $\langle \gamma_1, \gamma_2, \gamma_3, \gamma_4 \rangle$ , zeigt der Autor, dass deren Abbildungen ein zusammenhängendes Intervall bilden. Dies stellt sicher, dass das „mex“ (die erste fehlende Ganzzahl) mindestens den Maximalwert einer spezifischen Teilmenge dieser Abbilder erreichen muss.
Konstruktion der Obergrenze ( $\gamma_k$ ): Für die Obergrenze verwendet der Autor einen induktiven Ansatz. Unter der Annahme einer Schranke $\gamma_k(h) \le \alpha_k h^{k-1} + O(h^{k-2})$ schätzt der Autor die Größe der Menge $F^{(k)}$ oberhalb eines Schwellenwerts $\beta_k h^k$ . Durch die Stratifizierung der Menge $F^{(k)}$ basierend auf den Vielfachheiten des größten Elements $\gamma_k$ und der Anwendung der „Stars-and-Bars“-Methode zur kombinatorischen Zählung, leitet der Autor eine Rekursionsrelation für die Koeffizienten $\alpha_k$ ab. Die Folge $\alpha_k$ wird so konstruiert, dass sie nicht-wachsend ist und gegen Null konvergiert.

Wesentliche Beiträge und Ergebnisse

Untergrenze für $\gamma_5(h)$ : Die Arbeit etabliert eine nicht-triviale Untergrenze für das fünfte Element der gierigen $B_h$ -Menge:
$\gamma_5(h) \ge \frac{1}{8}h^4 + \frac{1}{2}h^3$
Dieses Ergebnis wird durch eine rigorose Analyse der durch die ersten vier Elemente erzeugten verbotenen Summen hergeleitet.
Obere Schranken für $\gamma_k(h)$ ( $k \ge 5$ ): Die Arbeit liefert die ersten nicht-trivialen oberen Schranken für $\gamma_k(h)$ für $k \ge 5$ . Konkret beweist sie:
$\gamma_k(h) \le \alpha_k h^{k-1} + O(h^{k-2})$
wobei die Konstanten $\alpha_k$ rekursiv definiert sind. Die Arbeit berechnet explizit:
- $\alpha_5 \approx 0,467214$
- $\alpha_6 \approx 0,382978$
- $\alpha_7 \approx 0,269877$
- Für $k \ge 7$ gilt $\alpha_{k+1} = \frac{1}{2} \alpha_k + \frac{1}{2^k k!} \sum_{j=0}^{k-1} \binom{k-1}{j} \binom{k}{j} 2^j$ .
  Die Folge $\alpha_k$ zeigt eine schnelle Abnahme, was impliziert, dass $\gamma_k(h)$ langsamer wächst, als es bisher unbewiesene Schätzungen vermuten ließen.
Vermutung zu $\gamma_5(h)$ : Basierend auf computergestützten Daten für $h \le 47$ vermutet der Autor eine präzise asymptotische Formel:
$\gamma_5(h) = \frac{1}{3}h^4 + O(h^3)$
Dies deutet darauf hin, dass die Untergrenze von $1/8$ nicht eng ist und der wahre führende Koeffizient wahrscheinlich $1/3$ beträgt.
Allgemeine Untergrenze: Die Arbeit wiederholt und kontextualisiert die allgemeine Untergrenze $\gamma_k(h) \ge \frac{1}{k!}h^{k-1} + O(h^{k-2})$ und bestätigt damit, dass der gierige Algorithmus Mengen mit der korrekten Größenordnung für ein festes $k$ erzeugt.

Bedeutung und Ansprüche
Der Autor rahmt die Bedeutung dieser Arbeit in drei Hauptbereichen ein:

Ästhetische und theoretische Notwendigkeit: $B_h$ -Mengen sind fundamentale Objekte der kombinatorischen Zahlentheorie. Der Autor argumentiert, dass das Verständnis des Outputs des gierigen Algorithmus für diese Mengen ein natürliches Problem ist, das Antworten verdient, unabhängig von unmittelbaren Anwendungen.
Machbarkeit der gierigen Analyse: Die Arbeit kontrastiert die Schwierigkeit der Analyse eines gierigen Algorithmus mit nicht-gierigen Konstruktionen (wie Singers Konstruktion mittels endlicher Körper). Während die Konstruktion einer $B_{100}$ -Menge mit 11 Elementen via endlicher Körper die Arbeit in $\mathbb{F}_{101}^{11}$ erfordern würde (was rechnerisch unplausibel ist), wird die Bestimmung einer Formel für das 10. Element der gierigen $B_{100}$ -Menge als „schwierig, aber plausibel“ beschrieben. Diese Arbeit stellt den ersten Schritt dar, um eine solche Analyse für $k \ge 5$ rigoros zu gestalten.
Verständnis des gierigen Algorithmus: Die primäre Motivation ist ein besseres Verständnis des gierigen Algorithmus für $B_2$ -Mengen (Sidon-Mengen), die reale Anwendungen haben (z. B. Golomb-Ruler, Frequenzzuweisung). Da der gierige Algorithmus eine Standardheuristik für additive Probleme ist, trägt die Etablierung von Schranken für $B_h$ -Mengen zu einem breiteren Verständnis gieriger Strategien in der additiven Zahlentheorie bei.

Die Arbeit schließt mit der Auflistung offener Probleme, darunter der Beweis von quasi-polynomiellen Formeln für $\gamma_k$ , die gleichmäßige Verteilung der Elemente in Kongruenzklassen und das Infimum von $s$ , für das die Summe der Kehrwert-Potenzen gieriger $B_h$ -Mengen konvergiert. Der Autor bleibt bescheiden und merkt an, dass die Schranken zwar nicht-trivial, aber möglicherweise nicht eng sind und die exakten Koeffizienten für $k \ge 5$ weiterhin konjekturell bleiben.