🔢 mathematics

A Distinct Covering System with Minimum Modulus 7 and Minimal Least Common Multiple 10080

Dit artikel weerlegt de conjectuur van Klein door een afwijkend dekkingssysteem te construeren met een minimum modulus 7 en een kleinste gemene veelvoud 10080, terwijl het tegelijkertijd bewijst dat een dergelijk systeem niet kan bestaan met een kleiner kleinste gemene veelvoud via een meerfasig filterargument en computationele verificatie.

Oorspronkelijke auteurs: Jiheng Zhang, Shiliang Zhang

Gepubliceerd 2026-07-22

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Jiheng Zhang, Shiliang Zhang

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 de getallenlijn voor als een eindeloze snelweg die in beide richtingen uitstrekt, bevolkt door elk geheel getal van negatief oneindig tot positief oneindig. In de wereld van de wiskunde, specifiek een tak genaamd getaltheorie, bestaat er een fascinerend puzzel over hoe je deze hele snelweg kunt "dekken" met niets anders dan een verzameling verkeersborden. Deze borden worden arithmetic progressies genoemd. Denk aan een bord dat zegt: "Elke 7e auto is een rode auto," of "Elke 12e auto is een blauwe auto." Als je genoeg van deze borden plaatst met verschillende intervallen, kun je ervoor zorgen dat elke enkele auto op de snelweg ofwel rood ofwel blauw is (of een andere kleur). Wanneer je erin slaagt om elk geheel getal te dekken met een collectie van deze herhalende patronen, heb je een dekkingssysteem gecreëerd.

De regels van het spel worden strenger wanneer wiskundigen vragen om een onderscheidend dekkingssysteem. Dit betekent dat elk bord een uniek interval moet hebben; je kunt niet twee borden gebruiken die beide zeggen: "elke 7e auto." Je moet verschillende getallen gebruiken voor je intervallen, zoals 7, 8, 9, 10, enzovoort. Een natuurlijke vraag is: hoe klein kan het kleinste interval zijn? Een tijdlang vroegen wiskundigen zich af of er een harde limiet aan hoe klein dit "minimale modulus" kon worden. Recentelijk is bewezen dat er inderdaad een limiet is, maar het mysterie dat overbleef, ging over efficiëntie. Als je het kleinste interval vastlegt (bijvoorbeeld 7), wat is dan het kleinste mogelijke "grootste getal" (het kleinste gemene veelvoud) dat je nodig hebt om het hele systeem te laten werken? Het is alsof je vraagt: als je kleinste stap 7 passen is, hoe ver moet je lopen voordat je patroon van stappen perfect uitlijnt met elke mogelijke positie op de weg?

Dit artikel behandelt precies die vraag voor het specifieke geval waarbij het kleinste interval 7 is. De auteurs, Shiliang Zhang en Jiheng Zhang, zijn op zoek gegaan naar het absolute minimale "grootste getal" vereist om een onderscheidend dekkingssysteem te bouwen met een start bij 7. Voordat dit werk werd uitgevoerd, had een wiskundige genaamd Klein een werkend systeem gebouwd met een "grootste getal" van 15.120 en vermoedde hij dat dit het best mogelijke was. De auteurs van dit artikel bewijzen dat Kleins vermoeden te hoog gegrepen was. Zij hebben een nieuw, efficiënter systeem geconstrueerd dat werkt met een "grootste getal" van slechts 10.080. Bovendien hebben zij wiskundig bewezen dat het onmogelijk is om dit te doen met een getal kleiner dan 10.080. Ze hebben niet alleen een betere oplossing gevonden; ze hebben bewezen dat het de beste oplossing is.

Het Detectiververhaal van het Getal 10.080

Om te begrijpen hoe de auteurs dit hebben opgelost, stel je voor dat je een detective bent die probeert een specifieke sleutel te vinden in een enorme, stoffige loods. De loods bevat elk mogelijk "grootste getal" (kleinste gemene veelvoud) dat een veelvoud van 7 is en tussen 5.040 en 10.080 valt. Jouw doel is om te bewijzen dat elk getal in dit bereik een "nep sleutel" is die de deur niet zal openen, terwijl het getal 10.080 de "echte sleutel" is.

Het Eerste Filter: De Reciproque Som
De auteurs beginnen door een "reciproque-som filter" toe te passen. In alledaagse termen: stel je voor dat elk mogelijk interval (zoals 7, 8, 9) een klein beetje "dekkingkracht" bijdraagt aan het systeem. De regel is dat de totale kracht van al je gekozen intervallen groter moet zijn dan 1 om de hele snelweg te dekken. Als je de "kracht" van elk beschikbaar interval voor een specifiek kandidaat-getal bij elkaar optelt en de som is minder dan 1, wordt die kandidaat onmiddellijk gediskwalificeerd. Dit filter was zeer effectief en wierp direct de meeste getallen uit de loods, waardoor er slechts 18 verdachte kandidaten overbleven.

Het Tweede Filter: De Integer Programming Test
Vervolgens gebruikten de auteurs een krachtig computertool genaamd "integer programming". Denk aan dit als een supergeorganiseerde puzzeloplosser. Voor elke van de 18 resterende kandidaten probeerde de computer de verkeersborden (residuele klassen) te rangschikken om te zien of ze de hele snelweg konden dekken zonder gaten. De computer was slim genoeg om redundante arrangementen (zoals het verschuiven van het hele patroon met één stap, wat het resultaat niet verandert) te negeren. Dit filter was meedogenloos; het elimineerde 14 van de 18 kandidaten, waarmee werd bewezen dat je, ongeacht hoe je de borden voor die getallen rangschikt, altijd enkele auto's onbedekt zult laten.

Het Derde Filter: De Partiële Som
Vier kandidaten bleven over: 5.040, 7.560, 8.400 en 9.240. Dit waren de "moeilijke noten". De auteurs realiseerden zich dat je voor sommige van deze getallen bijna de hele snelweg kunt dekken, waarbij slechts een fractie van de auto's onbedekt blijft. Dit maakte de vorige tests lastig. Om dit aan te pakken, gebruikten ze een "partiële som filter". In plaats van aan te nemen dat de borden alles perfect dekken, berekenden ze precies hoeveel van de snelweg de best mogelijke arrangement van een deelverzameling van borden zou kunnen dekken. Ze ontdekten dat voor 8.400 en 9.240, zelfs de meest optimistische arrangement van borden een gat achterliet dat te groot was om met de resterende borden te vullen. Deze twee getallen werden uitgesloten.

De Laatste Confrontatie: De Gurobi Computatie
Dit liet slechts twee hardnekkige verdachten over: 5.040 en 7.560. Deze getallen waren zo goed in het dekken van de snelweg dat ze respectievelijk meer dan 96% en 98% ervan konden dekken, waarbij slechts een klein, moeilijk te vinden gat overbleef. Om dit op te lossen, draaiden de auteurs massieve, uitputtende computersimulaties met behulp van software genaamd Gurobi. Ze gokten niet alleen; ze controleerden elke mogelijke manier om de borden voor deze twee getallen te rangschikken. De computer draaide duizenden seconden en controleerde miljoenen mogelijkheden, en verklaarde uiteindelijk: "Infeasible" (onhaalbaar). Dit betekent dat het wiskundig onmogelijk is om de snelweg te dekken met een minimumstap van 7 met 5.040 of 7.560 als het grootste getal.

De Winnaar: 10.080
Met alle kleinere getallen geëlimineerd, richtten de auteurs hun aandacht op 10.080. Ze bewezen niet alleen dat het mogelijk was; ze bouwden het eigenlijke systeem. Ze stelden de specifieke intervallen en startpunten op (zoals "elke 7e auto beginnend bij 6", "elke 8e auto beginnend bij 7", enzovoort) die de gehele getallenlijn perfect dekken. Ze verifieerden dat dit systeem werkt, waarmee bewezen werd dat 10.080 inderdaad een werkende oplossing is.

De Conclusie

Het artikel concludeert met een definitief antwoord: het kleinste mogelijke "grootste getal" voor een onderscheidend dekkingssysteem met een minimumstap van 7 is exact 10.080. Dit is een verbetering ten opzichte van het vorige record van 15.120. De auteurs hebben niet alleen een beter getal gevonden; ze hebben bewezen dat geen kleiner getal ooit zou kunnen werken. Ze deden dit door elke mogelijkheid systematisch uit te filteren, van eenvoudige wiskundige controles tot complexe computersimulaties, waarbij geen steen onomgeslagen bleef. Het resultaat is een nauwkeurig, bewezen feit in de getaltheorie, dat laat zien dat hoewel je heel dicht bij het dekken van de oneindige snelweg kunt komen met kleinere getallen, je dat simpelweg niet perfect kunt doen totdat je bij 10.080 komt.

Technische Samenvatting: Een afwijkend dekingssysteem met een minimaal modulus 7 en een minimaal kleinste gemene veelvoud 10080

Probleemstelling
Het artikel behandelt het probleem van het bepalen van het minimale kleinste gemene veelvoud (LCM), aangeduid als $L_{\min}(m)$ , voor een afwijkend dekingssysteem met een voorgeschreven minimale modulus $m$ . Een afwijkend dekingssysteem is een eindige collectie rekenkundige progressies $\{a_i \pmod{m_i}\}$ met onderling verschillende moduli $m_i$ die alle gehele getallen dekken. Hoewel Hough (2015) beweerde dat de minimale modulus in elk afwijkend dekingssysteem begrensd wordt door een absolute constante, zijn de specifieke waarden van $L_{\min}(m)$ voor kleine $m$ het onderwerp geweest van expliciete constructie en verificatie.

Vooraf aan dit werk werden de waarden voor $m \le 6$ vastgesteld: $L_{\min}(3)=120$ , $L_{\min}(4)=360$ , $L_{\min}(5)=1440$ , en $L_{\min}(6)=5040$ . Voor $m=7$ construeerde Klein (2024) een systeem met $L=15120$ en vermoedde dat dit minimaal was. Dit artikel beoogt de casus $m=7$ op te lossen door een systeem te construeren met een kleiner LCM en te bewijzen dat geen kleiner LCM mogelijk is.

Methodologie
De auteurs hanteren een strategie van opeenvolgende filtering om kandidaat-waarden voor het LCM $L$ in het bereik $5040 \le L < 10080$ te elimineren. Het bewijs rust op het "divisor-completion" principe: als een afwijkend dekingssysteem bestaat met een minimale modulus $m$ en LCM $L$ , kan men willekeurige congruentieklassen toevoegen voor elke ontbrekende deler $d$ van $L$ (waarbij $d \ge m$ ) zonder de dekkingseigenschap te vernietigen. Daarom volstaat het om aan te tonen dat de "divisor-completed" verzameling moduli $D_m(L) = \{d : d|L, d \ge m\}$ geen dekingssysteem kan vormen, om de niet-bestaan van een specifieke $L$ te bewijzen.

Het filterproces bestaat uit vier stadia:

Reciproque-som Filter: Gebaseerd op de Mirsky–Newman obstructie (Lemma 1), die stelt dat voor elk afwijkend dekingssysteem $\sum 1/m_i > 1$ . De auteurs berekenen $S_7(L) = \sum_{d|L, d \ge 7} 1/d$ . Als $S_7(L) \le 1$ , wordt $L$ onmiddellijk verworpen. Dit reduceert de zoekruimte van alle veelvouden van 7 in het bereik tot 18 kandidaten.
Integer Programmeren (IP) Filter: Voor de resterende kandidaten formuleren de auteurs een binair integer programmeren haalbaarheidsprobleem. Variabelen $x_{m,a}$ geven aan of de congruentieklasse $a \pmod m$ wordt geselecteerd. Beperkingen dwingen precies één klasse per modulus af en dekken alle residuen modulo $L$ . Om symmetrie te verminderen, passen de auteurs translatie-invariantie en residue-layer swap normalisaties toe (Lemma's 2 en 3) om specifieke congruentieklassen te fixeren (bijv. $6 \pmod 7$ , $7 \pmod 8$ ) voordat ze de problemen oplossen. Deze filter elimineert 14 van de 18 kandidaten.
Partiële-som Filter: Voor de overgebleven moeilijke gevallen (specifiek 8400 en 9240) verfijnen de auteurs het argument van de reciproque som. In plaats van aan te nemen dat alle geselecteerde klassen disjunct zijn, berekenen ze de maximale mogelijke dekking $\alpha_A(L)$ van een deelverzameling moduli $A$ via een kleinere IP, en voegen ze dan de theoretische maximale bijdrage van de resterende moduli $B$ toe. Als $\alpha_A(L) + \sum_{m \in B} 1/m < 1$ , wordt de kandidaat uitgesloten. Dit elimineert 8400 en 9240.
Volledige Gurobi Computatie: De laatste twee kandidaten, $L=5040$ en $L=7560$ , weerstaan de partiële-som filter omdat ze "near-covers" toestaan (dekking van >96% en >98% van de residuen, respectievelijk). Deze gevallen worden opgelost door volledige haalbaarheidscontroles uit te voeren met de Gurobi solver (v13.0.1) op de volledige divisor-completed systemen.

Belangrijkste Bijdragen en Resultaten

Constructie: De auteurs construeren expliciet een afwijkend dekingssysteem met minimale modulus 7 en kleinste gemene veelvoud 10080. Dit systeem bestaat uit 63 verschillende moduli, waarvan de kleinste 7 is.
Minimaliteitsbewijs: Het artikel bewijst dat $L_{\min}(7) = 10080$ . Door systematisch alle $L < 10080$ te elimineren (met name de 18 kandidaten die de initiële som-filter overleven), tonen de auteurs aan dat geen enkel afwijkend dekingssysteem met minimale modulus 7 een kleiner LCM dan 10080 kan hebben.
Weerlegging van Vermoeden: Het resultaat weerlegt de conjectuur van Klein dat 15120 het minimale LCM was voor $m=7$ .
Computationele Data: Het artikel bevat een uitgebreide tabel met Gurobi-looptijden en uitkomsten voor alle 18 kandidaten, inclusief de twee moeilijkste gevallen (5040 en 7560) die respectievelijk ongeveer 13.789 en 13.159 seconden duurden om de onhaalbaarheid te bewijzen.

Betekenis
Het artikel stelt de exacte waarde van $L_{\min}(7)$ vast, waarmee de bekende sequentie van minimale LCM's voor afwijkende dekingssystemen wordt uitgebreid. Het werk toont de effectiviteit aan van het combineren van analytische getaltheorie (reciproque sommen) met combinatorische optimalisatie (integer programmeren en branch-and-bound) om existentieproblemen in rekenkundige progressies op te lossen. De auteurs merken op dat de moeilijkheid die werd ervaren met $L=5040$ en $L=7560$ — waarbij systemen bijna alle residuen dekken maar de rest niet — suggereert dat toekomstige verbeteringen in het bewijzen van minimaliteit voor hogere moduli mogelijk scherpere hybride certificaten vereisen die in staat zijn om "near-covers" te onderscheiden van echte dekingssystemen zonder uitsluitend te vertrouwen op volledige branch-and-bound verificatie.

Het Detectiververhaal van het Getal 10.080

De Conclusie

Meer zoals dit