🔢 mathematics

Bounds for Greedy $B_h$ -sets

Dit artikel stelt nieuwe niet-triviale onder- en bovengrenzen vast voor het $k$ -de element van de gulzige $B_h$ -verzameling, waarbij specifiek nauwkeurige asymptotische schattingen wordt geboden voor $k \ge 5$ en een algemene ondergrens voor alle $k \ge 1$ , terwijl ook een conjectuur wordt voorgesteld voor het exacte asymptotische gedrag van het vijfde element.

Oorspronkelijke auteurs: Kevin O'Bryant

Gepubliceerd 2026-07-09

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Kevin O'Bryant

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 toren bouwt van genummerde blokken, maar je hebt een zeer strikte regel: geen twee verschillende groepen blokken mogen samen tot hetzelfde totaal optellen. Als je $h$ blokken kiest en ze bij elkaar optelt, moet die som uniek zijn voor die specifieke groep blokken. Wiskundigen noemen deze speciale collecties $B_h$ -sets.

Stel je voor dat je de kleinst mogelijke toren wilt bouwen die aan deze regel voldoet. Je begint met blok 0, en dan zoek je naar het eerstvolgende kleinste getal dat je kunt toevoegen zonder de regel te breken. Daarna zoek je het eerstvolgende kleinste getal na dat, en zo verder. Dit wordt het Greedy Algoritme genoemd. Het is alsof je een spel speelt waarbij je altijd het goedkoopste, kleinste item beschikbaar kiest dat niet buiten je budget gaat.

De paper van Kevin O'Bryant gaat over het bepalen van hoe groot deze "volgende" blokken worden naarmate de toren hoger wordt. De auteur probeert de grootte van de 5e, 6e, 7e en zelfs hogere blokken te voorspellen, afhankelijk van hoe streng de "geen dubbele sommen" regel is (weergegeven door het getal $h$ ).

De Grote Ontdekking: Het 5e Blok

De belangrijkste prestatie van de auteur is het eindelijk plaatsen van stevige hekken rond de grootte van het 5e blok in deze toren (aangeduid als $\gamma_5$ ).

Voordat deze paper bestond, wisten we dat het 5e blok ergens tussen 0 en een zeer groot getal lag, maar hadden we geen strakke grip op het. Deze paper bewijst twee dingen:

De Ondergrens (De Vloer): Het 5e blok is zeker minstens zo groot als $\frac{1}{8}h^4 + \frac{1}{2}h^3$ . Zie dit als een betonnen vloer waar je niet onderdoor kunt graven. Hoe je het ook probeert, het 5e blok zal niet kleiner zijn dan dit.
De Bovengrens (Het Plafond): Het 5e blok is definitief kleiner dan ongeveer $0.467214 \times h^4$ (plus wat kleinere termen). Dit is een plafond dat het blok niet kan bereiken.

Zo weten we nu dat het 5e blok in een specifiek "appartement" leeft tussen deze twee getallen.

Het Grotere Plaatje: Blokken 6 en Hoger

Voor het 6e blok en alles daarna ( $k \ge 6$ ) geeft de auteur nog geen enkele perfecte formule. In plaats daarvan geeft hij een recept om een "plafond" te berekenen voor hoe groot deze blokken kunnen worden.

De paper introduceert een reeks getallen genaamd $\alpha_k$ (zoals $\alpha_6 = 0.382978$ , $\alpha_7 = 0.269877$ , enzovoort). Deze getallen fungeren als een krimpende limiet. De auteur bewijst dat voor elk bloknummer $k$ (waar $k \ge 5$ ), de grootte van dat blok nooit de volgende waarde zal overschrijden:
$\alpha_k \times h^{k-1}$
plus een beetje extra ruis die kleiner wordt naarmate $h$ enorm groot wordt.

De paper geeft een specifieke formule om het volgende $\alpha$ -getal te berekenen als je het huidige weet, maar deze recursieve stap werkt specifiek voor het 7e blok en verder (het berekenen van $\alpha_{k+1}$ uit $\alpha_k$ vereist $k \ge 7$ ). Voor het 6e blok biedt de paper een specifieke constante waarde afgeleid van eerdere stappen. Het is als een wiskundische lopende band: je voert de limiet voor het 6e blok in, en de machine spuugt de limiet voor het 7e blok uit, enzovoort.

Wat de Paper Niet Zegt (en wat het uitsluit)

Het is erg belangrijk om te weten wat deze paper niet doet, want de auteur is hier zeer voorzichtig over:

Het lost de hele puzzel niet op. De auteur stelt expliciet dat hoewel ze de grenzen van het 5e blok hebben gevonden, ze de exacte formule voor het 5e blok nog niet hebben gevonden.
Het beweert niet dat het 5e blok exact $\frac{1}{3}h^4$ is. De auteur conjectureert (vermoedt op basis van patronen) dat het 5e blok voor grote $h$ precies $\frac{1}{3}h^4$ zou kunnen zijn, maar geeft toe dat dit slechts een gok is. Ze hebben dit niet bewezen.
Het zegt niet dat de blokken eenvoudige polynomen zijn. De auteur is sceptisch over de vraag of alle blokken voor altijd een eenvoudig, vloeiend polynomiaal patroon volgen. Hoewel de eerste paar blokken (0 tot en met 4) "quasi-polynomialen" zijn (polynomialen die licht veranderen op basis van de restwaarde van $h$ gedeeld door een getal), twijfelt de auteur eraan of dit patroon voor elk blok voor altijd standhoudt.

De "Verboden" Zone

De paper legt ook een "verboden zone" uit voor het volgende blok. Als je een toren van blokken hebt, zijn er slechts een eindig aantal gehele getallen die je kunt proberen toe te voegen die de regels zouden breken. De paper berekent exact hoeveel "slechte" getallen bestaan die je niet kunt kiezen. Het blijkt dat er voor elke bestaande toren slechts een beperkt aantal "valstrik"-getallen zijn die de $B_h$ -eigenschap zouden verruineren, en al deze getallen bevinden zich binnen een specifiek bereik.

Het Mysterie van het 6e Blok

De auteur bevat een tabel met getallen voor het 6e blok ( $\gamma_6$ ) voor verschillende waarden van $h$ , berekend door een computer. Echter, kijkend naar deze getallen, geeft de auteur toe: "Er is nog geen formule geraden." Dit is een beetje alsoordat je naar een reeks getallen kijkt en zegt: "We weten wat ze zijn, maar we hebben geen idee wat de regel is die ze genereert." De auteur vermeldt zelfs de eerste 33 waarden van $\gamma_6$ en merkt op dat niemand nog een patroon voor hen heeft gevonden.

De Openstaande Vragen

De paper eindigt met het opsommen van de mysteries die onopgelost blijven:

Kunnen we bewijzen dat het 5e blok exact $\frac{1}{3}h^4$ is?
Kunnen we formules vinden voor het 6e, 7e en hogere blokken?
Zijn deze blokken in een wiskundige zin gelijkmatig verdeeld, of klonteren ze op vreemde manieren samen? (De auteur merkt op dat voor het 2e blok, ze lijken te klonteren op een manier die niet willekeurig is).
Is er een specifiek getal (zoals 33) dat nooit het verschil kan zijn tussen twee blokken in de toren? (De auteur merkt op dat voor het 2e blok, elk getal van 1 tot 87 voorkomt als verschil, behalve 33, wat een vreemde toevalligheid is).

Kortom, deze paper bouwt een stevig hek rond het 5e blok en geeft een krimpende ladder voor alle blokken daarboven, maar de exacte vorm van de toren en de geheime formules voor de hogere blokken blijven een mysterie dat wacht op de volgende ontdekkingsreiziger.

Technische Samenvatting: Grenzen voor de Greedy $B_h$ -verzameling

Probleemstelling
Het artikel onderzoekt het asymptotische gedrag van het gulzigheidsalgoritme (greedy algorithm) toegepast op de constructie van $B_h$ -verzamelingen. Een verzameling $A$ van niet-negatieve gehele getallen wordt gedefinieerd als een $B_h$ -verzameling indien elke oplossing voor de vergelijking $a_1 + \dots + a_h = b_1 + \dots + b_h$ (waarbij $a_i, b_i \in A$ ) impliceert dat de multisets $\{a_1, \dots, a_h\}$ en $\{b_1, \dots, b_h\}$ identiek zijn. Het primaire object van studie is de greedy $B_h$ -verzameling, aangeduid als $G(h) = \{\gamma_0, \gamma_1, \gamma_2, \dots\}$ , die lexicografisch wordt geconstrueerd door $\gamma_0 = 0, \gamma_1 = 1$ te stellen, en $\gamma_{k+1}$ te definiëren als het kleinste gehele getal waarvoor $\{\gamma_0, \dots, \gamma_{k+1}\}$ een $B_h$ -verzameling blijft.

Het centrale probleem dat wordt behandeld, is het bepalen van de groeisnelheid van het $k$ -de element, $\gamma_k(h)$ , als functie van $h$ voor een vaste $k$ . Hoewel exacte formules bekend zijn voor $k \le 4$ , is het gedrag voor $k \ge 5$ grotendeels onverkend gebleven buiten computationele enumeratie. Dit artikel beoogt niet-triviale boven- en ondergrenzen vast te stellen voor $\gamma_k(h)$ , specifiek gericht op het vijfde element $\gamma_5(h)$ en algemene grenzen voor $k \ge 5$ .

Methodologie
De auteur maakt gebruik van een combinatie van combinatorische analyse, recursieve begrenzing en gedetailleerde casus-enumeratie:

Combinatorische Grenzen: Het artikel maakt gebruik van de observatie dat het aantal verschillende $h$ -voudige sommen van een verzameling van grootte $k+1$ gelijk is aan $\binom{k+h}{k}$ . Aangezien deze sommen binnen het interval $[h\gamma_0, h\gamma_k]$ moeten liggen, levert dit een basislijn ondergrens op voor $\gamma_k(h)$ .
De "Mex" Karakterisering: Een kernlemma stelt vast dat $\gamma_{k+1} = \text{mex}(F^{(k)})$ , waarbij $F^{(k)}$ de verzameling is van alle gehele getallen die representeerbaar zijn als $\frac{1}{r}\sum_{i=1}^k \gamma_i(m_i - m'_i)$ onder specifieke restricties op multipliciteiten $m_i, m'_i$ . Deze karakterisering stelt de auteur in staat om $\gamma_{k+1}$ te begrenzen door het aantal "verboden" waarden in $F^{(k)}$ te tellen die een bepaalde drempel overschrijden.
Ondergrens Constructie ( $\gamma_5$ ): Om de ondergrens voor $\gamma_5(h)$ te bewijzen, definieert de auteur een specifieke verzameling gehele vectoren $\Delta$ die geldige coëfficiëntcombinaties voor de eerste vier elementen vertegenwoordigen. Door deze vectoren lexicografisch te ordenen (gebaseerd op een specifieke "odometer"-stijl ordening) en de afbeelding van deze vectoren onder het inproduct met $\langle \gamma_1, \gamma_2, \gamma_3, \gamma_4 \rangle$ te analyseren, toont de auteur aan dat de afbeeldingen een continu interval vormen. Dit garandeert dat de "mex" (het eerste ontbrekende geheel) ten minste de maximale waarde van een specifieke deelverzameling van deze afbeeldingen moet zijn.
Bovengrens Constructie ( $\gamma_k$ ): Voor de bovengrens gebruikt de auteur een inductieve aanpak. Uitgaande van een grens $\gamma_k(h) \le \alpha_k h^{k-1} + O(h^{k-2})$ , schat de auteur de grootte van de verzameling $F^{(k)}$ boven een drempel $\beta_k h^k$ . Door de verzameling $F^{(k)}$ te stratificeren op basis van de multipliciteiten van het grootste element $\gamma_k$ , en "stars-and-bars" combinatorische telling toe te passen, leidt de auteur een recursieve relatie af voor de coëfficiënten $\alpha_k$ . De reeks $\alpha_k$ wordt geconstrueerd om niet-toenemend te zijn en naar nul te convergeren.

Belangrijkste Bijdragen en Resultaten

Ondergrens voor $\gamma_5(h)$ : Het artikel stelt een niet-triviale ondergrens vast voor het vijfde element van de greedy $B_h$ -verzameling:
$\gamma_5(h) \ge \frac{1}{8}h^4 + \frac{1}{2}h^3$
Dit resultaat is afgeleid van een rigoureuze analyse van de verboden sommen gegenereerd door de eerste vier elementen.
Bovengrenzen voor $\gamma_k(h)$ ( $k \ge 5$ ): Het artikel biedt de eerste niet-triviale bovengrenzen voor $\gamma_k(h)$ voor $k \ge 5$ . Specifiek bewijst het:
$\gamma_k(h) \le \alpha_k h^{k-1} + O(h^{k-2})$
waarbij de constanten $\alpha_k$ recursief zijn gedefinieerd. Het artikel berekent expliciet:
- $\alpha_5 \approx 0,467214$
- $\alpha_6 \approx 0,382978$
- $\alpha_7 \approx 0,269877$
- Voor $k \ge 7$ , $\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$ .
  De reeks $\alpha_k$ vertoont een snelle afname, wat impliceert dat $\gamma_k(h)$ langzamer groeit dan eerder onbewezen schattingen zouden suggereren.
Conjectuur over $\gamma_5(h)$ : Gebaseerd op computationele data voor $h \le 47$ , vermoedt de auteur een precieze asymptotische formule:
$\gamma_5(h) = \frac{1}{3}h^4 + O(h^3)$
Dit suggereert dat de ondergrens van $1/8$ niet nauwkeurig is, en de ware leidende coëfficiënt waarschijnlijk $1/3$ is.
Algemene Ondergrens: Het artikel herhaalt en contextualiseert de algemene ondergrens $\gamma_k(h) \ge \frac{1}{k!}h^{k-1} + O(h^{k-2})$ , waarmee wordt bevestigd dat het greedy algoritme verzamelingen produceert met de juiste orde van groei voor vaste $k$ .

Betekenis en Claims
De auteur kadert de betekenis van dit werk in drie hoofdgebieden:

Esthetische en Theoretische Noodzaak: $B_h$ -verzamelingen zijn fundamentele objecten in de combinatorische getaltheorie. De auteur voert aan dat het begrijpen van de output van het greedy algoritme voor deze verzamelingen een natuurlijke vraag is die antwoorden verdient, onafhankelijk van directe toepassingen.
Haalbaarheid van Greedy Analyse: Het artikel contrasteert de moeilijkheid van het analyseren van het greedy algoritme met niet-greedy constructies (zoals de Singer-constructie met behulp van eindige velden). Terwijl het construeren van een $B_{100}$ -verzameling met 11 elementen via eindige velden het werken in $\mathbb{F}_{101}^{11}$ vereist (wat computationeel onhaalbaar is), wordt het vinden van een formule voor het 10e element van de greedy $B_{100}$ -verzameling beschreven als "moeilijk maar haalbaar". Dit werk vormt de eerste stap om een dergelijke analyse voor $k \ge 5$ rigoureus te maken.
Begrip van het Greedy Algoritme: De primaire motivatie is het beter begrijpen van het greedy algoritme voor $B_2$ -verzamelingen (Sidon-verzamelingen), die fysieke toepassingen in de echte wereld hebben (bijv. Golomb-linialen, frequentietoewijzing). Aangezien het greedy algoritme een standaard heuristiek is voor additieve problemen, draagt het vaststellen van grenzen voor $B_h$ -verzamelingen bij aan een breder begrip van greedy strategieën in de additieve getaltheorie.

Het artikel sluit af met een lijst van openstaande problemen, waaronder het bewijs van quasi-polynomiale formules voor $\gamma_k$ , de uniforme verdeling van elementen in congruentieklassen, en de infimum van $s$ waarvoor de som van de reciproke machten van greedy $B_h$ -verzamelingen convergeert. De auteur blijft bescheiden en merkt op dat hoewel de grenzen niet-triviaal zijn, ze mogelijk niet nauwkeurig zijn, en dat de exacte coëfficiënten voor $k \ge 5$ nog steeds conjecturaal zijn.