🔢 mathematics

Formal Foundations and Proof-Carrying Certificates for q-ary Covering Codes in Lean 4

Dit artikel presenteert een formalisering van de elementaire theorie van q-aire dekkingscodes in Lean 4, waarmee een herbruikbare, controleerbare basis wordt gevestigd met bewijsdragende certificaten voor het verifiëren van boven- en ondergrenzen op dekkingstalen.

Oorspronkelijke auteurs: Andreas Florath

Gepubliceerd 2026-06-09

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Andreas Florath

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 probeert een gigantisch, multidimensionaal schaakbord te bedekken met een beperkt aantal "veiligheidsnetten".

In de wereld van de wiskunde is dit het probleem van Covering Codes (bedekkingscodes). Je hebt een rooster van mogelijke posities (zoals een schaakbord, maar het kan 3D, 4D of zelfs hoger dimensionaal zijn). Je wilt een klein aantal "centra" op dit rooster plaatsen. De regel is dat elk enkel vierkant op het bord binnen een bepaalde afstand moet liggen (laten we zeggen: één stap) van ten minste één van je centra.

De grote vraag is: Wat is het absolute minimale aantal centra dat je nodig hebt om het hele bord te bedekken?

Dit artikel, geschreven door Andreas Florath, probeert niet een nieuw record te vestigen voor het kleinste aantal centra. In plaats daarvan bouwt het een digitale, onkraakbare kluis om te bewijzen dat de getallen die we al kennen, correct zijn.

Hier is een uitsplitsing van de ideeën uit het artikel met behulp van eenvoudige analogieën:

1. Het "Bewijs-dragende Certificaat" (Het Gouden Ticket)

Meestal, wanneer een wiskundige zegt: "Ik heb een code gevonden met 73 centra die het bord bedekt," laat hij je een lijst met getallen zien. Je moet de auteur vertrouwen, of je moet zelf urenlang de wiskunde controleren.

Dit artikel introduceert een "Proof-Carrying Certificate" (Bewijs-dragend Certificaat). Zie dit niet alleen als een lijst met getallen, maar als een Gouden Ticket dat een ingebouwde, zelfcontrolerende magische truc bevat.

Het Ticket: Het zegt: "Hier is een verzameling van 73 centra."
De Magische Truc: Het ticket bevat een kleine, geautomatiseerde robot (geschreven in een taal die Lean 4 wordt genoemd) die onmiddellijk elk vierkant op het bord controleert om te bevestigen: "Ja, dit vierkant is bedekt. Ja, dat vierkant is bedekt. Ja, ze zijn allemaal bedekt."
Het Resultaat: Je hoeft de auteur niet te vertrouwen. Je voert gewoon de robot uit. Als de robot "Pass" zegt, is het bewijs 10er de wiskunde 100% gegarandeerd.

2. De "Twee-delige Puzzel"

Om te bewijzen dat je het perfecte (exacte) aantal centra hebt, moet je twee verschillende puzzels tegelijkertijd oplossen:

De Bovengrens (De Constructie): "Ik kan het bord bedekken met 73 centra." (Je laat de lijst zien).
De Ondergrens (De Onmogelijke Taak): "Het is onmogelijk om het bord te bedekken met 72 centra." (Je bewijst dat er, hoe je het ook probeert, altijd een gat overblijft).

Dit artikel bouwt een systeem waarbij deze twee puzzels aparte stukken zijn. Je kunt een certificaat hebben voor de "73" en een apart certificaat voor de "onmogelijkheid met 72". Wanneer deze samenkomen, klikken ze in elkaar tot een perfect, exact antwoord.

3. De "Lego" van de Wiskunde

De auteur heeft een enorme bibliotheek van Lego-stenen (formele regels) gebouwd.

Sommige stenen zijn simpel: "Als je een klein bord bedekt, kun je een groter bord bedekken door er een paar extra stukjes aan toe te voegen."
Sommige stenen zijn complex: "Als je twee verschillende soorten borden combineert, is dit precies hoe de bedekkingsregels veranderen."

De schoonheid van dit artikel is dat deze Lego-stenen uitwisselbaar zijn. Als iemand anders een nieuwe manier vindt om een bord te bedekken, kunnen ze hun nieuwe steen simpelweg in deze bestaande Lego-structuur klikken, en het hele systeem verifieert het automatisch.

4. De "Database van de Waarheid"

Het artikel bevat een Proof-Carrying Database (Bewijs-dragende Database). Stel je een bibliotheekboek voor waarbij, in plaats van alleen het antwoord "Het antwoord is 7" te printen, het boek een video-opname van het bewijs bevat.

Als je een getal in deze database opzoekt, geeft het je niet alleen een getal. Het geeft je de trace (het stapsgewijze proces) van hoe dat getal bewezen is.
Je kunt deze video opnieuw afspelen in het Lean 4-systeem, en het zal het bewijs vanaf nul opnieuw uitvoeren om te controleren of het nog steeds standhoudt.

5. Het "Voetbalpool" Voorbeeld

Het artikel gebruikt een real-world analogie om het probleem uit te leggen: De Voetbalpool.
Stel je voor dat je wedt op 8 voetbalwedstrijden. Elke wedstrijd heeft 3 mogelijke uitkomsten (Winst, Gelijk, Verlies). Je wilt een set wedtickets kopen.

Het Doel: Ongeacht de werkelijke resultaten, wil je garanderen dat ten minste één van je tickets "dichtbij" is (misschien slechts 1 voorspelling fout).
De Wiskunde: Hoeveel tickets moet je kopen om dit te garanderen?
De Rol van het Artikel: Het artikel neemt een beroemde, gepubliceerde oplossing voor dit probleem (waarbij iemand een oplossing vond met 486 tickets) en heeft dit omgezet in een machine-controleerbaar certificaat. Het bewijst zonder enig twijfel dat 486 tickets werken.

Wat dit artikel daadwerkelijk beweert (en wat het niet doet)

Het BELEGT: Het heeft een solide, herbruikbare basis (een "formele fundering") gebouwd waar bewijzen voor bedekkingscodes kunnen worden opgeslagen, gecontroleerd en gecombineerd automatisch. Het heeft verschillende specifieke, bekende getallen geverifieerd (zoals de 486 tickets voor het 8-wedstrijden probleem) met behulp van dit nieuwe systeem.
Het BELEGT NIET: Het claimt niet een nieuw record te hebben gevonden voor het kleinste aantal tickets dat nodig is. Het claimt niet het probleem voor elk mogelijk scenario op te lossen. Het is een instrument-bouwend artikel, geen record-brekend artikel.

Het Grote Plaatje

Beschouw dit artikel als het bouwen van een hoogbeveiligde kluis voor wiskundige waarheden. Voorheen, als je een complexe bedekkingscode wilde controleren, moest je een mens vertrouwen of een computerprogramma dat misschien een fout (bug) bevatte. Nu, dankzij dit artikel, heb je een systeem waarbij het bewijs zelf een stuk software is dat je kunt draaien om de waarheid onmiddellijk te verifiëren. Het verandert "Ik denk dat dit klopt" in "De computer heeft bewezen dat dit klopt."

Technische Samenvatting: Formele Fundamenten en Bewijs-dragende Certificaten voor q-aire Dekkingscodes in Lean 4

Probleemstelling
Dekkingscodes in eindige Hamming-ruimtes zoeken naar de kleinste verzameling woorden (codewoorden) zodanig dat de unie van hun Hamming-ballen met straal $r$ de gehele ruimte $A^n$ dekt. De centrale grootheid is het $q$ -aire dekkingsgetal $K_q(n,r)$ , gedefinieerd als de minimale grootte van een dergelijke code. Hoewel de definitie elementair is, berust het bepalen van exacte waarden of nauwe grenzen voor $K_q(n,r)$ doorgaans op een mengeling van expliciete constructies, telargumenten, recursieve relaties en computerzoekopdrachten. Een aanzienlijke uitdaging in het vakgebied is dat exacte beweringen $K_q(n,r) = k$ twee onafhankelijke componenten vereisen: een expliciete constructie die een bovengrens bewijst ( $K_q(n,r) \le k$ ) en een bewijs dat geen kleinere code bestaat (een ondergrens $K_q(n,r) \ge k$ ). Deze componenten komen vaak uit uiteenlopende bronnen, wat de verificatie van exacte waarden moeilijk maakt om te auditeren.

Methodologie
Het artikel presenteert een formalisering van de elementaire dekkingscode-theorie in de Lean 4 theorem prover. De methodologie wordt gekenmerkt door drie kernkeuzes in het ontwerp:

Representatie van Woorden: Woorden worden gemodelleerd als afhankelijke functies van een coördinaattype naar een alfabettype. De algemene $q$ -aire Hamming-ruimte van lengte $n$ wordt gerepresenteerd als Fin n → Fin q. Deze functionele representatie behoudt een algemene interface voor abstracte coördinaattypes terwijl het de $q$ -aire specialisatie vereenvoudigt.
Certificaat-stijl Predicaten: In plaats van $K_q(n,r)$ $K_{q} (n, r)$ te definiëren als een niet-berekenbare minimalisatiefunctie, gebruikt de formalisering logische predicaten om beweringen over de dekkingsgetallen te representeren.
- KUpper r k: Beweert het bestaan van een eindige dekkingscode van grootte hoogstens $k$ (bovengrens).
- KLower r k: Beweert dat elke eindige dekkingscode een grootte van minstens $k$ heeft (ondergrens).
- KSpec r k: Combineert beide om exactheid te beweren ( $K_q(n,r) = k$ ).
  Dit modulaire aanpak stelt in staat dat boven- en ondergrenzen uit verschillende bronnen onafhankelijk geassembleerd kunnen worden.
Bewijs-dragende Database: Het artikel implementeert een database waar opgeslagen grenzen niet louter numerieke waarden zijn, maar "bewijs-dragende" objecten. Elke invoer bevat een afleidingsspoor (derivation trace). Het herhalen van dit spoor in Lean reconstrueert een formeel bewijs van het overeenkomstige QaryKUpper of QaryKLower predicaat. Het systeem onderscheidt handgeschreven wiskundige stellingen (door de kernel gecontroleerd) van gegenereerde data (onbetrouwbare producenten wiens output gevalideerd wordt via spoor-replay).

Belangrijkste Bijdragen
Het artikel vestigt een herbruikbare, controleerbare fundering voor machine-gecontroleerde dekkingscode-certificaten. De specifieke bijdragen zijn:

Formele Infrastructuur: Een volledige Lean 4-framework voor eindige Hamming-ruimtes, Hamming-afstand, gesloten ballen en dekkingspredicaten, waarbij randgevallen (bijv. $q=0$ , $n=0$ , $r \ge n$ ) strikt binnen de definities worden afgehandeld in plaats van als informele conventies.
Analytische Resultaten: Formele bewijzen van de $q$ -aire Hamming-balvolumeformule en de klassieke sfeer-dekking ondergrens. De sfeer-dekking ondergrens is ingekapseld als een berekenbare functie sphereLower die gecertificeerde ondergrens-certificaten genereert.
Structurele Stellingen: Formalisering van elementaire exacte gevallen (bijv. $K_q(n,0) = q^n$ , $K_q(n, n-1) = q$ ) en structurele constructies, inclus[ief] een product-dekkingsstelling en diverse naburige relaties (puncturing, lengthening, alfabetprojectie en concatenatie) die grenzen tussen parameter-triplets transporteren.
Gevalsstudie (Van Laarhoven et al.): Een end-to-end workflow die de formalisering van gepubliceerde expliciete codes demonstreert. De auteurs hebben de dekkingscodes uit een artikel uit 1989 (Van Laarhoven et al.) getranscribeerd naar Lean, waarbij ze deze als gepakte arrays hebben gecodeerd om elaboratie-limieten te vermijden. Het systeem heeft de dekkingseigenschap en cardinaliteit geverifieerd, waarmee machine-gecontroleerde bovengrens-certificaten werden geproduceerd voor $K_3(6,1) \le 3$ , $K_3(7,1) \le 186$ , en $K_3(8,1) \le 486$ .
Database Implementatie: Een bewijs-dragende database met 52.822 invoer voor parameters $0 \le q \le 21$ , $0 \le n \le 48$ , en $0 \le r \le 48$ . Deze database bevat exacte certificaten voor kleine gevallen (bijv. $K_2(5,1)=7$ , $K_3(3,1)=5$ ) en intervallen afgeleid van spoor-replay.

Resultaten
De formalisering verifieert succesvol:

De $q$ -aire balvolumeformule en de sfeer-dekking ondergrens.
Elementaire exacte waarden zoals $K_2(5,1)=7$ , $K_2(6,2)=4$ , $K_3(3,1)=5$ , en $K_4(3,1)=8$ .
Bovengrenzen voor het ternaire voetbalpool-probleem afgeleid van expliciete codes, specifiek $K_3(6,1) \le 73$ , $K_3(7,1) \le 186$ , en $K_3(8,1) \le 486$ .
Een uniforme twee-blok cyclische constructie die $K_q(3,1) \le \lceil q^2/2 \rceil$ bewijst.

Het afsluitingsproces van de database heeft deze primitieve bronnen succesvol gepropageerd via gecertificeerde relatieregels om een consistente tabel van grenzen te genereren. Het systeem ondersteunt twee bewijsmodi: een "kernel mode" met standaard decide voor sterkere replay-garanties, en een "native mode" met de gecompileerde evaluator van Lean voor snellere ontwikkeling, met duidelijke vertrouwensgrenzen voor elk.

Betekenis en Claims
Het artikel stelt expliciet dat de primaire bijdrage niet de ontdekking van nieuwe recordbrekende grenzen of de reproductie van bestaande literatuurtabellen is. In plaats daarvan ligt de betekenis in het bieden van een formeel interface en een controleerbare fundering voor dekkingscode-certificaten.

Het werk overbrugt de kloof tussen de klassieke dekkingscode-literatuur en toekomstige computationele certificaten. Door de scheiding van boven-grens getuigen, onder-grens argumenten en exactheidspredicaten, maakt de formalisering het mogelijk dat resultaten uit expliciete constructies, combinatorisch tellen, en (potentieel) toekomstige SAT- of integer-programmerings-solvers, gecontroleerd en samengesteld kunnen worden binnen één enkele vertrouwde framework. Het "bewijs-dragende" karakter van de database zorgt ervoor dat elke gerapporteerde grens kan worden teruggevoerd naar een machine-gecontroleerd bewijs, wat de problemen van reproduceerbaarheid en verificatie in het vakgebied aanpakt. Het artikel positioneert zichzelf als een fundamentele stap naar een toekomst waarin computationele zoekresultaten naadloos geïntegreerd kunnen worden in formele wiskundige bibliotheken.