Pi-dagen idag!

Väldigt icke-originellt att tänka på pi-dagen på pi-dagen. Därav att jag tog tag i det en helt vanlig tisdag/onsdag några timmar i spridda skurar. För vad är ens pi-dagen? Ja, tack vare min lista så vet vi. Den händer flera gånger om året beroende på kalender och datumformat. Ska nämnas att det blir en dubbel perfekt-π-krock mellan gregorianska och holocene 2031-04-15. När jag insåg att dubbla π-krockar var relativt vanligt så behövde jag leta efter trippla. Min lista på kommande visar inte några trippla, så ser inte ut att bli i vår livstid. Min beräkning har varit utifrån selektivt utvalda kalendrar, och ska alltså inte läsas som "närmaste trippel-π-krocl över huvud taget". Så vill någon scanna alla kalendrar och hitta den närmaste så är det fortfarande ett problem att ta tag i

Tågrälssatsen — hur många spår räcker? (ett ärligt hårdhetsbevis)

(fortsätter i pi-tråden. Ingen pi-dag den här gången, men samma kugghjul en dimension upp. Får tolereras, hoppas jag.)

Sist visade jag att periodiska cykler med relativt prima perioder möts, tätt och för evigt. Jag har sedan mina förra inlägg blivit totalt besatt av kugghjul. Eichmann tänkte nog samma sak, och som jag inte kunnat släppa: hur många spår måste en station hålla för att alla tidtabeller ska hinna med? Frågan ser ut att ha ett rent svar. Den har det inte, och det jag tänker göra här är att bevisa att den inte har det — inte gnälla, utan visa exakt var det blir hårt och varför. Det man kan få billigt är undre gränser och ett ja/nej. Det exakta talet får man inte billigt, och det är en egenskap hos frågan, inte ett fel i metoden.

Uppställningen

Tänk er en station med X spår. X tåg får stå inne samtidigt, inte ett till. n linjer, var och en med sin egen period. Linje i har period Pᵢ (dygn) och upptar ett spår i dᵢ dygn per ankomst — dess uppehåll, med 0 < dᵢ < Pᵢ: tåget lämnar innan linjens nästa ankomst. Fasen φᵢ säger var i cykeln linjen startar.

Allt lever på heltalsgriddet — perioder, uppehåll och faser i hela dygn. Det är inte kosmetik. Tillåter man irrationella periodkvoter ligger mötena täta överallt (Kronecker) och ingen fasläggning håller isär dem; griddet är precis det som gör frågan avgörbar. Vik in allt i ringen ℤ/L, L = lcm(P₁,…,Pₙ). Beläggningen är antalet linjer inne samtidigt:


O är periodisk med L — ett L-fönster är hela framtiden. Det minsta spårantal som räcker är M = max_t O(t) under den bästa tillåtna fasläggningen. Frågan är alltså: kan man räkna ut M billigt?

Det billiga: undre gränser

Två golv på M kostar nästan ingenting, och båda är fasoberoende — inget fasspel i världen tar dig under dem.

Densiteten. Medelbeläggningen är Σᵢ dᵢ/Pᵢ, och eftersom O är heltalsvärd:


Överstiger den summan spårantalet är stationen olösbar, utan att man behöver titta på perioderna alls.

Koprimalitet (CRT). Ta en delmängd S med parvis relativt prima perioder. Kinesiska restsatsen gör resten-avbildningen t → (t mod Pᵢ) till en bijektion, så det finns ett t där alla i S just börjat sitt uppehåll samtidigt (dᵢ ≥ 1 på griddet räcker). Alltså M ≥ |S| för alla faser. Är den största parvis-prima klicken bland perioderna större än X är stationen olösbar.

Parvis kokar det ner till ett gcd och en addition: linje i och j går aldrig att fasa isär, oavsett faser, precis när dᵢ + dⱼ > gcd(Pᵢ,Pⱼ). Billigt oundviklighetscertifikat. (Och notera: parvisa krockar adderar sig inte till en samtidig — bågar på en cirkel lyder inte Helly — så CRT:s produktstruktur är genuint nödvändig för |S|-gränsen.)

Det dyra: det exakta talet — och beviset att det är hårt

Golven ger dig ett spann. När biter de inte, och man vill ha exakt M? Här kommer stinget, och det är en riktig sats, inte en känsla.

Betrakta M vid givna faser — inte ens fasvalet, bara att läsa av toppen. Bygg en konfliktgraf G: en nod per linje, en kant mellan i och j om de kan sammanfalla. Nyckeln är att perioderna kan byggas så grafen blir vilken graf man vill — och att koprimheten på kant-sidan inte är något man tilldelar, den följer. Ge varje icke-kant ett eget färskt primtal, och sätt linje i:s period till produkten av primtalen för dess icke-kanter (en nod utan icke-kanter får ett eget baslinje-primtal, så 0 < dᵢ < Pᵢ håller). Då delar två linjer ett primtal precis när de är en icke-kant — och där lägger man dem på olika rester modulo det primtalet, så de aldrig möts. Är de en kant delar de inget primtal alls, alltså koprima, och CRT låter dem mötas. Med enhetsuppehåll blir en mängd linjer samtidigt inne precis när de är parvis förbundna — en klick i G. Och här faller Helly-invändningen bort som jag själv reste nyss: en klicks perioder är parvis koprima som hel mängd (klassisk CRT, Sunzi — inte bara parvis förenliga rester), så en simultan tidpunkt finns för varje fasval. Toppbeläggningen är klickens storlek:


Och att hitta den största klicken i en godtycklig graf är ett av de klassiskt hårda problemen (NP-fullständigt, Karp 1972). Alltså: redan att läsa av hur många tåg som trängs som mest, vid fixa tidtabeller, är NP-hårt. (Att det stannar vid NP och inte värre, trots att L = lcm(Pᵢ) kan vara astronomiskt: ett vittne t har bitlängd log L ≤ Σ log Pᵢ, alltså polynomiell i indata.) Att fråga "räcker X spår?" med X i indata är coNP-fullständigt. Och det enklaste specialfallet — ett spår, enhetsuppehåll, lägg faserna så att restklasserna blir disjunkta — är den exakta periodiska varianten (Exact-Pinwheel / periodisk underhållsschemaläggning), känd NP-fullständig via reduktion från graffärgning. Inte att förväxla med den allmänna flexibla pinwheel-varianten, vars komplexitet delvis är öppen.

Det är beviset. Frågan "hur många spår räcker" har inget billigt svar i allmänhet, inte för att ingen varit smart nog, utan för att den bär en klick inuti sig, och klickar är hårda.

Vad man då faktiskt får

Man får det ärliga: två undre gränser man räknar ut på en servett, och ett avgörande — givet faserna prövas frågan "M ≤ X?" mot ett enda L-fönster, och för fixt spårantal går det i polynomtid (om än n^{X+1}). På nej-sidan ofta ett billigt certifikat (bandet, densiteten, klicken); på ja-sidan ett vittne, som i allmänhet är dyrt att ens kontrollera. Ett avgörande och certifierbara gränser — men ingen formel för det minsta X, och inget löfte om optimal packning. Att veta om något får plats är en annan fråga än att veta hur få spår som räcker — och den senare bär en NP-hård kärna man inte kan prata bort.

Ställverket, en gång till: det förutsåg aldrig en krock, det gjorde den omöjlig genom geometri. Här är geometrin aritmetisk och ärligare — den säger dig när det bevisligen inte går, ger dig golven gratis, och erkänner rakt att det exakta talet kostar. Kugghjulen snurrar deterministiskt; att sätta en undre gräns på dem är lätt, att räkna det exakta spårbehovet är hårt, och att låtsas något annat vore att skarva. Det gör jag inte.

Hmm.. det här ser ju riktigt seriöst ut. Är "tågrälssatsen" redan känd på något sätt? Annars bör du kanske publicera det på riktigt, s a s?

Och med tanke på att pi dyker upp på de ibland mest oväntade sammanhangen kanske det även gör det här i något sammanhang?

---
Eller vänta nu, detta kanske visst är väldigt nära relaterat till det du utrett om multipla pi-dagar, kanske t ex om Pᵢ är olika kalendrars antal dagar för olika månader, eller nåt sånt? Erkänner att jag famlar..

Haha nästan. Pᵢ lät jag vara kvar vid korrekturläsningen för att det kändes relevant, eller som ett väldigt osannolikt sammanträffande. Vilket man nu föredrar. Men din fråga är egentligen: "Hur är detta relevant till topic?". Och det är relevant för vi diskuterar en dag, och en dag ingår i en kalender som ju är, ett kugghjul. Så jag fortsätter med kugghjulsmatematik, denna gång i form av tågspår. Jag tänkte att det kommer en uppföljare av inlägget, eventuellt två. Sedan är det slut.

Jag har hänvisat till Karp 1972 i texten. Så detta är inget nytt. Just min metod saknade dock ett namn, och när Eichmanns teorem kändes för brutalt så blev det Tågrälssatsen istället. Det finns inget av publiceringsvärde i texten, mer än den kanal dit den är riktad: Flashback. Vilket för mig är underhållning.

Ah, nu föll den polletten ner: "kugghjulsmatematik", som ju både multipla pi-dagar och tågrälssatsen handlar om. Nice work!

Tack!

Mina förra inlägg om π-krockarna är dock genuint nytt. Inte i matematiken, det är bara bezouts identitet och kinesiska restsatsen. Men metoden och kopplingarna är nya. Fortfarande inget av publiceringsvärde. Det är så kallat ett akademiskt problem, inget verkligt. Det jag blev nöjd över var att jag fick ändra mitt tankesätt, vilket ledde till tankar om ett verkligt problem som jag tänkte försöka lösa. Samma kugghjul. Bara i fler dimensioner. Därav att jag inleder mitt senaste stora inlägg med att frågan är felställd.

Förra inlägget började med frågan:

Hur många spår måste en station hålla för att alla tidtabeller ska hinna med?

Jag kallade frågan felställd redan där. Efter att ha vridit på kugghjulen ett varv till tror jag att jag nu kan säga exakt varför.

Jag gav varje linje period Pᵢ, uppehåll dᵢ och fas φᵢ. Men när även φᵢ är given har jag redan bestämt tidtabellen. Sedan frågade jag hur många spår den behöver.

Det är inte optimering. Det är mätning.
Har vi en färdig tidtabell kan vi naturligtvis läsa av


och säga hur många tåg som som mest står inne samtidigt. Men jag har då inte hittat den bästa tidtabellen. Jag har mätt en redan vald. Det är ungefär som att först färglägga en graf och sedan fråga hur många färger färgläggningen använder.

Scramblen

Backa därför ett steg. Perioderna Pᵢ och uppehållen dᵢ är givna. Faserna är det inte. Nu finns ett riktigt beslut:

där Fᵢ är de faser linje i faktiskt får använda.Först nu kan vi fråga efter

utan att ha bakat in lösningen i indata. Men även här finns två olika saker som lätt blandas ihop.
Hur många tåg måste få plats samtidigt?
Och hur många fasta spår måste stationen ha?

De behöver inte vara samma tal.

Tre tåg, två platser, tre spår

Ta tre linjer med samma period och uppehåll:


Varje par överlappar. Men räkna beläggningen:


A och B möts.
B och C möts.
C och A möts.

Men A, B och C möts aldrig samtidigt.

Om tågen får byta spår mellan besöken räcker alltså två spår. Om varje linje däremot måste ha samma spår varje gång krävs tre. Varför?

Därför att A inte kan dela med B, B inte med C och C inte med A. Konfliktgrafen är en triangel:


Där ligger skillnaden.

Maximal samtidig belastning mäter hur många tåg som befinner sig inne vid samma tidpunkt. Det kromatiska talet mäter hur många fasta resurser som krävs för att separera alla par som någon gång kan mötas.

Och där var jag slarvig förra gången

Jag lät i praktiken


gälla generellt.
Det gör det inte.

Exemplet ovan är motbeviset. Grafen innehåller en 3-klick, men det finns ingen trippelkrock. I min speciella CRT-konstruktion fungerade slutsatsen därför att perioderna i klicken var parvis relativt prima. Då gav kinesiska restsatsen den gemensamma tidpunkten.
Det var CRT som gjorde jobbet. Inte grafen.

Det är en viktig skillnad, eftersom konfliktgrafen bara ser paren. Periodsystemet innehåller mer information än sin konfliktgraf.

Grafen kan dessutom missa åt andra hållet

Ta tre linjer med


För varje par gäller


Inget enskilt par är alltså tvingat att krocka. Två linjer kan läggas på varsin restklass. Men vi har tre linjer och bara två restklasser. Duvhålsprincipen säger att minst två måste hamna tillsammans. Samma sak syns i densiteten:

En ren pargraf kan alltså både överdriva och missa. Det är precis vad man borde förvänta sig. Den kastar bort den högre ordningens struktur.

Densiteten


ger alltid golvet


Men golvet kan vara exakt eller fullständigt uselt. Ta i stället många linjer med enhetsuppehåll och parvis relativt prima perioder.
Då kan


vara mindre än 1. Densiteten säger då bara


Men CRT säger att för vilka givna faser som helst finns en tidpunkt som samtidigt uppfyller


för samtliga i. Alla tågen möts.

Alltså:


Samma densitetsgolv kan alltså ligga precis på sanningen i ett periodsystem och n−1 steg under den i ett annat.

Det som förändrades var inte mängden trafik. Det var periodernas aritmetik.

Tre storheter, tre frågor

Vi har alltså minst tre olika storheter:


De mäter inte samma sak. ρ är ett billigt golv. M* är ett periodiskt packningsproblem.
χ(G) uppstår om varje linje dessutom måste tilldelas ett permanent spår.

Och gapen mellan dem är inte feltermer som man kan sopa undan. De är strukturen. Det är där gcd, CRT och den periodiska geometrin visar vad densiteten inte ser.

Från linje till cirkel

Det finns dessutom en geometrisk anledning till att det här blir lurigt. Vanliga intervall på en tidslinje har ett vänligt beteende. När ett intervall tar slut kan resursen återanvändas.Men periodiska tidtabeller slutar inte.

Efter

dygn är vi tillbaka där vi började.Tidslinjens ändar limmas ihop:

och intervallen blir periodiska bågar på en cirkel. Det är därför vi kan få


utan motsägelse. Ingen tidpunkt behöver tre spår. Ändå går det inte att ge de tre linjerna två permanenta spår. Det är också en betydligt renare förklaring av varför konfliktgrafen är användbar men inte hela modellen. Grafen ser vilka par som möts. Cirkeln innehåller informationen om hur de möts.

Så vad är den rätt ställda frågan?

Nu kan vi formulera problemet utan att lösningen redan ligger i indata.

Vi ger systemet


och låter lösningen välja


Sedan måste vi säga vilken fysisk modell vi menar.

Om varje ankomst får använda vilket ledigt spår som helst är frågan:


Om varje linje måste ha ett permanent spår tillkommer


och kravet att två linjer som någon gång överlappar aldrig får samma sᵢ. Nu finns ett faktiskt vittne att leta efter:


eller, med fasta spår,


Verifieringen är fortfarande helt mekanisk. Antingen fungerar konstruktionen genom hela supercykeln eller så finns ett konkret t där den spricker.

Det var taket jag saknade

Inte ett spårantal som räknas ut efter att tidtabellen redan är färdig. Ett spårantal som sätts före lösningen:


Och därefter:

Kan dessa kugghjul fasas så att de håller sig under taket för evigt?

Nu har vi en scramble där svaret inte är inbakat.

Perioderna finns.
Uppehållen finns.
Kapaciteten finns. Men arrangemanget gör det inte.

Densiteten ger ett golv.
gcd ger parvisa spärrar.
CRT kan ge globala tvång.

Och när de inte avgör frågan återstår den fulla periodiska packningen. Det var den biten som saknades i förra inlägget. Jag försökte optimera kugghjulen efter att jag redan hade skruvat fast dem. Den rätt ställda frågan lämnar dem lösa, sätter ett faktiskt tak och frågar om någon kan få hela maskinen att snurra för evigt utan att slå i det.

Vi får se om det blir en fortsättning på inlägget där jag försöker återknyta till det ursprungliga problemet, men det är såhär långt jag kommit med problemet, och jag hoppas kugghjulen är mycket tydligare nu!

Tågrälssatsen I började med frågan: hur många spår räcker? Jag vek in linjerna i supercykeln L = lcm(P₁,...,Pₙ), skrev O(t) = Σᵢχᵢ(t), fick densitetsgolvet och använde gcd och CRT för oundvikliga krockar. Men ett hål återstod: exakt vad krävs för att en godtycklig hel mängd linjer ska stå inne samtidigt?

Det är Tågrälssatsen II.

Tågrälssatsen II — simultanitet

Låt linje i ha period Pᵢ och låt Aᵢ ⊆ ℤ/Pᵢ vara de rester där linjen är aktiv. För ett vanligt tåg med fas φᵢ och uppehåll dᵢ är Aᵢ helt enkelt dᵢ sammanhängande rester. En mängd linjer J möts samtidigt om och endast om man kan välja en rest aᵢ ∈ Aᵢ för varje i ∈ J så att
När resterna väl är valda säger den generaliserade kinesiska restsatsen¹ att systemet
har en gemensam lösning. Andra riktningen är omedelbar: finns ett sådant t, sätt aᵢ = t mod Pᵢ; då följer alla parvisa gcd-kongruenser automatiskt. Alltså verkligen "om och endast om".

Det icke-triviala ligger i kvantifikatorerna. En och samma tupel (aᵢ) ska fungera för alla par:
inte
Restklasser har här Helly-tal 2²: efter val av en restklass per modulus räcker parvis förenlighet globalt. Bågarna Aᵢ har inte den egenskapen.

Ta det lilla motexemplet:
Varje par överlappar, så en vanlig konfliktgraf ser en triangel. Men gcd(6,6) = 6, så II kräver en och samma rest modulo 6. A∩B∩C är tomt. Ingen trippelkrock finns, och maxbeläggningen är 2. Grafen minns att varje par kan mötas men glömmer vilken rest som gjorde mötet möjligt.

Och nu kommer den roliga delen: det här är exakt Kalenderkrockssatsen igen.

Tillbaka till π-dagarna

Där hade kalender A period P och en mängd S ⊆ ℤ/P av de dygnsrester där 3:14:15 inträffar. Kalender B hade Q och T. Jag skrev
Det är bara II med två linjer. När gcd(P,Q) = 1 är alla val kompatibla, vilket gav dubbel-π-formeln N = |S|·|T|. Därför står krocken mellan gregoriansk och tabulär Hijri kvar.

Men i trippel-inlägget använde jag samma produktformel en gång för mycket.

Perioderna var
dygn. Jag behandlade dem som parvis relativt prima. Faktorisera:
så
Den där tian är inte en olycka. Den kommer från själva läsningen "årtal slutar på 15". Hijris strukturcykel är 30 år, men mönstret måste samtidigt återkomma modulo 100, så den effektiva årperioden blir lcm(30,100) = 300 år: tio strukturcykler. Den persiska 33-årscykeln är relativt prim mot 100, så där blir lcm(33,100) = 3300 år: hundra strukturcykler.

Generellt: har en kalender strukturcykel c med gcd(c,100) = 1 blir mönsterperioden exakt 100c år, och med D dygn per strukturcykel blir dygnsperioden 100D. Två sådana kalenderhjul delar därför minst faktorn 100. Gregorianska undslipper eftersom 400-årscykeln redan innehåller 100. Bas 10 är därför inte dekoration ovanpå matematiken; siffermönstret injicerar självt gemensamma faktorer i perioderna. Så fort flera sådana kalendrar tas med får produktformeln N = ∏|Sᵢ| inte användas utan gcd-kontroll.

Det jag gör nu är redan Tågrälssatsen III tillämpad: jag räknar inte råprodukten av möjliga rester, utan bara de tupeler som faktiskt är koherenta.

36 i stället för 396

I den tabulära Hijri-modellen finns tre 3:14:15-dagar i en 300-årig mönsterperiod: år 15, 115 och 215, alltid 14 Rabi' al-awwal. Med civil epok JDN 1 948 440³ blir deras absoluta dygntal
Därifrån kommer Hijris 3, 0, 6.

I den 33-åriga persiska modell jag använde tidigare finns 33 målår i en 3300-årig mönsterperiod. För åren 15, 115, …, 3215 blir de absoluta JDN-resterna modulo 10:
Räkna bara 0, 3 och 6: var och en förekommer tre gånger. Alltså överlever nio Hijri–Persien-par:
Gregorianska kalendern är koprim mot båda och bidrar fyra π-rester, så
Mitt gamla N = 396 var alltså fel. gcd = 10 säger vilket kompatibilitetsfilter som gäller; den säger inte hur många kombinationer som överlever. Det avgörs av de faktiska resternas fördelning.

Supercykeln hade däremot blivit rätt, eftersom den beräknades med lcm:
Därmed blir
Och det konstruerade vittnet överlever:
Datumet kan stå kvar när N faller eftersom resultaten kom från olika håll: N = 396 var en felaktig formel, medan datumet var ett explicit konstruerat och verifierat vittne. Ett giltigt vittne bevisar existens även om antalet vittnen räknats fel.

Det persiska årtalet ser dessutom först misstänkt ut: det är 39 900 år högre än det gregorianska, trots att persisk epok börjar ungefär 621 år senare. Men den 33-åriga modellen har medelåret
mot gregorianska 365,2425. Skillnaden är bara cirka 0,00007576 dygn per år, men över 195 miljarder år ackumuleras den till ungefär 40 521 kalenderår. Dra bort epokskillnaden och man får just cirka +39 900. Driften är alltså inte en blunder; den är konsekvensen av att två nästan lika solår får snurra astronomiskt länge.

En brasklapp: gcd = 10 är strukturell för periodlängderna. Tabulär Hijri har 10 631 dygn per 30-årscykel även om skottåren placeras annorlunda, och den cykliska persiska modellen 12 053 dygn per 33 år. Men N = 36, 142,37 miljarder år och vittnet ovan hör till just dessa restmängder och den 33-åriga modellen. Flyttade skottdagar kan ändra restfördelningen modulo 10, alltså N och vittnena. En ekvinoktiebunden persisk kalender är dessutom ett annat objekt. Robust är filtret gcd = 10; den exakta räkningen 36 är konventionsberoende. Storleksordningen består så länge resterna inte hamnar i en särskild lockout.

Tågrälssatsen III — vittnesrummet

Nu satsen som räkningen ovan använde. För en vald mängd periodiska system J, sätt
Låt Cⱼ vara mängden kompatibla aktiva resttupeler och Wⱼ de faktiska vittnesdygnen i ett Lⱼ-fönster:
Då är
en bijektion mellan Wⱼ och Cⱼ. Injektivitet: samma rester modulo alla Pᵢ betyder att Lⱼ delar t−t′. Surjektivitet: generaliserad CRT ger en lösning modulo Lⱼ för varje kompatibel tupel. Alltså
Efter vittnet: Nⱼ = 0 betyder lockout; Nⱼ > 0 betyder exakt Nⱼ vittnesklasser per supercykel. Varje klass t₀ fortsätter sedan för evigt som
och medelintervallet mellan alla vittnen är Lⱼ/Nⱼ. Inte en ny period — ett medelintervall.

Var tog hårdheten vägen?

Ingenstans. III är en karakterisering, inte en algoritm för Tågrälssatsen I. Den flyttar sökningen från tidsaxeln till det kombinatoriska restvalet. Bygg en nod (i,a) för varje aktiv rest a ∈ Aᵢ och koppla två noder när deras rester är gcd-kompatibla. För en vald mängd J motsvarar en samtidig krock en klick med exakt en nod från varje linje i J. Att maximera |J| är fortfarande ett multicolored max-clique-problem⁴; kombinatoriken finns kvar.

Vinsten är att vi slipper skanna L dygn. För trippel-π motsvarar L drygt fem biljoner år, medan vittnesrummet har några tiotal aktiva rester. Toppbeläggningen kan fortfarande skrivas
men satsen lovar inte att maximeringen är gratis. Den berättar bara var problemet faktiskt bor.

Och där sluter sig cirkeln. Kalenderkrockssatsen gav existensvillkoret för två π-hjul. Tågrälssatsen I gjorde samtidigheten till en kapacitetsfråga. Tågrälssatsen II gav det exakta globala kompatibilitetsvillkoret. Tågrälssatsen III räknar själva vittnesrummet — och när man applicerar den på mitt gamla trippelresultat hittar den omedelbart tian som produktformeln missade.

Det är nästan oförskämt pedagogiskt. Jag trodde att 396 möjliga kombinationer betydde 396 krockar. II säger: välj resterna och kontrollera att de faktiskt kan leva på samma dygn. III säger: räkna sedan bara de koherenta tupelerna. Resultatet är 36. Supercykeln står kvar, det explicita vittnet står kvar, men medelintervallet går från 12,94 till 142,37 miljarder år.

Det är samma läxa som i min förra kalenderrevision, fast en dimension högre: lcm säger hur lång hela maskinen är. N säger hur många gånger den klickar under varvet. Och gcd avgör vilka av de tänkta kuggarna som över huvud taget kan mötas.

Kugghjulet behöver inte snurra för att vi ska veta var det klickar.

Prior art

¹ Qin Jiushao, Shushu Jiuzhang (1247), Da Yan-regeln; modern notation: Gauss, Disquisitiones Arithmeticae (1801).

² Duchet, "Hypergraphs" (1995); Dourado–Protti–Szwarcfiter, EJC DS17 (2009). Helly-tal 2 här är ett CRT-korollarium.

³ Dershowitz & Reingold, Calendrical Calculations, 3:e uppl. (2008); persisk kalendernyans: Heydari-Malayeri (2004).

⁴ Fellows–Hermelin–Rosamond–Vialette, TCS 410 (2009), 53–61, om Multicolored Clique.

En attribution som föll bort. Exemplet med max_t O(t) = 2 men χ(G) = 3 är inte mitt — det är standard i litteraturen om cirkelbågsgrafer.

Intervall på en rak tidsaxel är snälla: kromatiskt tal = största klick, så maximal last räcker som svar på antalet spår. Gilmore & Hoffman, 1964¹.

Periodisk tid limmar ihop axeln till en cirkel. Då gäller det inte längre, och färgläggningen blir NP-svår. Garey, Johnson, Miller & Papadimitriou, 1980².

Steget från linje till cirkel är alltså ett känt komplexitetssprång, inte en egenhet hos min station. Kalendrar lever på cirkeln från början.


¹ Canadian Journal of Mathematics 16 (1964), 539–548.
² SIAM J. Alg. Disc. Meth. 1 (1980), 216–227.

Här är alla sammanhängande inlägg i serien. Två sidospår är skippade: ett som spårade ur i kryptografi, och Tolkien-kalendrarna som bara var för skojs skull. Ingen av dem förde själva lösningen vidare.

Nästan alla perfekta pi-dagar (lista)
De flesta π-dagar (lista)
Perfekta π-dagar ±200 år (lista)

Den ultimata π-dagen
Perfekta π-dagar: en sats, en självkorrigering — och nästa krock
Perfekta π-dagar, del 2: trippel-π och de döda stjärnorna

Tågrälssatsen I — hur många spår räcker? (ett ärligt hårdhetsbevis)
Tågrälssatsen II — nu ställer vi frågan rätt
Tågrälssatsen III — efter vittnet (och tian jag missade)

Och slutligen hemsida för sökningarna: https://chrono-pi1.onrender.com

Jag kallade tidigare problemet för akademiskt. Med II och III har det snarare utvecklats till ett abstrakt periodiskt schemaläggningsproblem med populärmatematisk tillämpning. Med andra ord en syntes som går att använda i både praktisk och teoretisk tillämpning det är nämligen vad min prior art-genomgång visar: att min syntes av etablerad matematik är unik. Vilket motiverar namngivning på mina egna satser.

Det här började med ett gammalt Tibia-konto.

Jag fick ett meddelande om att någon försökt logga in på ett konto jag inte använt på ungefär tjugo år. Förr använde Tibia maskinellt tilldelade kontonummer. Min första tanke var därför inte att någon sökte just mig, utan att kontot råkat ligga någonstans i ett stort men ändligt nummerutrymme som en automatisk process passerade genom.

Om gissningen var rätt spelar ingen roll här. Det viktiga var en detalj jag först förenklade bort: ett objekt kan få tre försök under en viss period och låsas först när budgeten är förbrukad.

Och då kommer frågan som måste ställas först:

Vad är det som gör ett redan använt objekt nytt igen?

Är det att P steg har gått sedan just det objektet användes? Är det att ett gemensamt datumfönster slår om och ger tre nya försök? Eller måste båda villkoren vara uppfyllda?

Först när det är definierat vet man vad det betyder att en ändlig sökrymd "tar slut".

Det är problemet jag kallar Tibiasatsen.

R försök under P steg

Vi har K distinkta objekt. Vid varje heltalssteg vill vi välja exakt X olika objekt. Under varje fönster om P steg får ett objekt användas högst R gånger.

Eftersom samma objekt högst kan väljas en gång under ett tidssteg är dess verkliga maximala budget
Under P steg måste processen göra
användningar.

Populationen kan högst leverera
användningar.

Alltså krävs
Vi behöver dessutom
eftersom de X samtidiga valen måste vara olika objekt.

De två villkoren är också tillräckliga.

Numrera objekten
Vid steg t väljer vi
modulo K.

Över vilka P steg som helst gör vi exakt X·P val. De motsvarar X·P konsekutiva heltal modulo K, så varje objekt träffas antingen
eller
gånger.

Men ur
följer
Ingen budget överskrids.

Alltså har vi en exakt gräns:

För ett enda tillåtet försök:
För analogins tre försök, när P ≥ 3:

Konstruktionen visar alltså att gränsen nås.

Och den ger mer än vad ett fast resetfönster kräver. Ta vilket rullande P-fönster som helst. De X·P valen är fortfarande X·P konsekutiva heltal modulo K, bara med en annan startpunkt. Varje objekt används därför högst ceil(X·P/K) gånger även där.

Samma optimala schema fungerar alltså både för fasta resetblock och för den starkare regeln "högst R användningar i varje P-fönster".

K = X·P i R=1-fallet är den deterministiska diskreta kusinen till Little's lag: population = genomströmning × tid.¹

Det intressanta börjar när objekten slutar vara identiska.

När varje objekt får sin egen klocka

Låt objekt j behöva vänta Pⱼ steg mellan två användningar.

Objekt j kan då långsiktigt bidra med högst
användningar per steg. För att hålla total takt X krävs därför

Men det räcker inte.

För X=1 är detta ett etablerat problem: Pinwheel Covering.² Där får objekt j användas högst en gång inom varje Pⱼ-fönster samtidigt som varje tidssteg måste täckas.

Densiteten säger hur mycket kapacitet som finns i genomsnitt, men inte om den går att placera.

Ta det kritiska fallet
Här finns ingen långsiktig slack.

Låt Nⱼ(T) vara antalet gånger objekt j används under [0,T), och låt Eⱼ(T) vara summan av hur mycket mellanrummen mellan användningarna överstiger minimiavståndet Pⱼ.

Har j använts n gånger gäller
så
Full takt kräver
Eftersom Σ1/Pⱼ = X får vi
och därmed

Det sammanlagda överskottet är alltså begränsat av en konstant under hela den oändliga körningen. Bara ändligt många mellanrum kan vara längre än sina respektive Pⱼ.

Inget objekt kan heller falla ur permanent. Tar vi bort objekt j återstår maximal långsiktig takt
vilket inte räcker.

Efter en ändlig transient måste därför varje objekt återkomma exakt var Pⱼ:e steg:

Täckningsfunktionen är periodisk modulo lcm(P₁,...,Pₖ). Är den exakt X i svansen är den därför exakt X över hela perioden och därmed över hela ℤ.

Alltså:

Vid kritisk densitet finns en självbärande återkomstloop om och endast om perioderna kan förses med rester som bildar ett exact X-cover of Z.

Omvändningen är omedelbar: en exakt X-täckning säger direkt vilka X objekt som ska användas vid varje steg.

Ta

Men någon loop finns inte.

Lägger vi period 2 på jämna steg återstår de udda, och ingen restklass modulo 3 ligger helt bland dem. Medelvärdet säger "exakt tillräckligt". Restklassgeometrin säger "omöjligt".

För Pinwheel Covering är densitet 1 alltså inte någon generell tillräcklig tröskel. Den optimala universella gränsen för X=1 är numera känd:
Vid eller över den är varje instans schemaläggbar. Kawamura och Kobayashi bestämde gränsen 2025.³

Zhi-Wei Sun visar dessutom att ett konstant exact X-cover med fler än ett objekt inte kan ha enbart distinkta moduler.⁴ Kritisk full takt tvingar alltså fram aritmetisk struktur.

Standard-Pinwheel är dessutom NP-hårt; Kleinberg och Mishra visade 2026 hårdhet för standardrepresentationen och överför resultatet till bland annat Pinwheel Covering. Jag gör inget NP-fullständighetsanspråk för den oändliga standardvarianten.⁵

Och där får Tågrälssatsen I ett syfte

Nu tillbaka till tågen.

I Tågrälssatsen I definierade jag
För tågen betydde χᵢ(t)=1 att linje i upptog ett spår. Här läser jag samma matematiska objekt som en periodisk lockout.

Låt därför objekt i ha period Pᵢ och en mängd blockerade rester
Sätt
och låt χᵢ(t)=1 precis när

Alltså är dᵢ antalet steg under varje Pᵢ-cykel som objekt i är låst.

Detta är inte nödvändigtvis samma modell som återkomsttaket ovan: där skapas spärren av våra val; här är låsmönstret redan givet.

Medelantalet låsta objekt är då
så Tågrälssatsen I ger

Nu får M ett operationellt syfte.

Har vi totalt K objekt finns vid tid t
fria. Om processen alltid måste kunna välja X objekt krävs
för alla t.

Alltså
eller

Kombinerar vi det med densitetsgolvet får vi det billiga nödvändiga villkoret

Där har golvet fått sitt jobb.

Det säger hur stor reservpopulation som minst krävs utöver de X direkt användbara objekten.

Det strikta återkomstfallet ovan går dessutom att känna igen som ett specialfall när det väl har stelnat till sin periodiska svans. Om objekt i används exakt en gång var Pᵢ:e steg och sedan är otillgängligt under de Pᵢ-1 mellanliggande stegen, då är

Som kontroll: i det kritiska exact-cover-fallet gäller
Då blir
Tågrälssatsens golv ger alltså M ≥ K-X, medan kravet på X fria objekt ger M ≤ K-X. Därför
exakt.

Samma gräns kommer från båda hållen.

Riktningen är viktig: återkomstmodellen skapar låsmönstret; Tågrälssatsen analyserar det när det finns. Andra exogena Bᵢ och dᵢ fungerar likadant.

Om faserna dessutom får väljas kommer scramblern tillbaka:
och då krävs

Nu sitter hela kedjan.

II säger vilka spärrar som kan sammanfalla.

III beskriver vittnesrummet.

I tar maximumet M.

Och Tibia säger varför vi behöver veta M:

Tågrälssatsen I hade ett golv.
Tibiasatsen ger golvet ett jobb.

Men Tibia har fortfarande en detalj kvar

Hittills har jag analyserat två rena fall. I det ena skapas spärren av att vi själva använder ett objekt.I det andra ligger spärren redan ute på tidsaxeln. Men de tre försöken som startade hela funderingen innehåller båda.

Försöksbudgeten minskar därför att vi använder objektet. Resetten kommer från klockan. Ett objekt har alltså både ett exogent och ett endogent tillstånd.
Det är där själva Tibiasatsen kommer in.

Fortsättning följer.

Prior art

¹ J. D. C. Little, "A Proof for the Queuing
Formula: L = λW", Operations Research
9(3), 1961.

² X=1 med rullande återkomsttak är
Pinwheel Covering, tidigare formulerat bl.a.
som point patrolling.

³ A. Kawamura & Y. Kobayashi,
"A Computer-Assisted Proof of the Optimal
Density Bound for Pinwheel Covering",
2025. Optimal universell tröskel:
α* ≈ 1,264.

⁴ Z.-W. Sun, "On the range of a covering
function", Journal of Number Theory
111(1), 2005, 190–196;
arXiv:math/0409279.

⁵ R. Kleinberg & A. Mishra,
"NP-Hardness and a PTAS for the Pinwheel
Problem", FOCS 2026. Standardproblemet är
NP-hårt och resultatet överförs även till
Pinwheel Covering; inget
NP-fullständighetsanspråk görs här.

Förra inlägget slutade med den detalj som tre-försöksanalogin egentligen gömde.

Försöksbudgeten minskar därför att vi själva använder objektet. Resetten kommer däremot från klockan. Ett objekt kan alltså vara spärrat av två helt olika skäl samtidigt: omvärlden tillåter det inte just nu, eller vår egen historik har gjort det otillgängligt.

Det ena är exogent, det andra endogent. När de läggs ovanpå varandra blir själva Tibiasatsen synlig.

Tre försök som tillstånd

Ta det konkreta kontrollfallet. Vi har K objekt, ett resetfönster på P steg och R försök per objekt. För Tibia-analogin är R=3.

Låt
ange var vi befinner oss i resetfönstret, och låt
vara hur många försök objekt j har kvar.

Då räcker tillståndet
för att veta vad som kan hända härnäst.

Väljer vi objekt j minskar rⱼ. När q passerar resetgränsen fylls budgeten på igen. Hela den relevanta historiken behöver alltså inte sparas; det räcker att minnas det som fortfarande kan påverka framtiden.

För R=3 finns högst
sådana råa tillstånd.

Det kan bli groteskt stort. Men det är ändligt.

Lägg på datumlockouten

Anta nu att ett objekt dessutom bara får användas i vissa exogena lägen. I kalenderfallet kan läget vara en rest modulo en period. I tågfallet kan det vara ett periodiskt blockeringsmönster. Mer generellt kan vi låta q vara vilket ändligt beskrivet omvärldstillstånd som helst.

Låt
betyda att mängden A av objekt är tillåten av omvärlden i tillstånd q.

Detta är existensmotorn. I Kalenderkrockssatsen byggdes den av kongruenser och CRT, på tågrälsen av periodiska rester. Tibiasatsen behöver bara veta vilka val som är giltiga.

Om objekt dessutom kan ha egna cooldowns låter vi
vara återstående spärrtid och skriver hela tillståndet som

Objekt j får väljas bara om omvärlden tillåter det, försöksbudgeten räcker och dess endogena spärr är noll.

Nu har vi allt.

Fulltaktsgrafen

Vi vill hålla takt X. En fulltaktsövergång från s till s' består därför av att välja en mängd A med
så att samtliga objekt i A är giltiga i s.

Därefter uppdateras budgetar, cooldowns och omvärldstillståndet. Resultatet är nästa tillstånd s'.

Bygg en riktad graf av alla sådana tillstånd och alla fulltaktsövergångar mellan dem.

Jag kallar den fulltaktsgrafen.

Varje väg i grafen är då en faktisk körning som aldrig går under X val per steg. Övergångar som kräver tomgång finns inte med.

Definition — självbärande

En ändlig population är självbärande vid takt X om det finns en oändlig körning från starttillståndet där exakt X giltiga objekt väljs vid varje tidssteg.

Nu satsen.

Tibiasatsen — ändlighetsreduktionen

Om omvärldens framtidsrelevanta tillstånd har en ändlig representation och varje objekts endogena tillstånd har ändligt minne, är systemet självbärande vid takt X om och endast om fulltaktsgrafen innehåller en riktad cykel som är nåbar från starttillståndet via enbart fulltaktsövergångar.

Beviset är nästan pinsamt kort.

Anta först att en självbärande körning finns. Den ger en oändlig väg i en ändlig graf. Något tillstånd måste därför besökas minst två gånger. Segmentet mellan två sådana besök är en riktad fulltaktscykel, och cykeln är nåbar från starten.

Omvänt: finns en nåbar fulltaktscykel följer vi först vägen dit och upprepar sedan cykeln för evigt.

∎

Den oändliga körningen har alltså ersatts av ett ändligt vittne: en väg till en cykel, plus själva cykeln.

Vad hände med oändligheten?

Samma sak som tidigare, men en dimension högre.

Kalenderkrockssatsen vek den oändliga tidsaxeln modulo en supercykel.

Tågrälssatsen III gick från tidsaxeln till ett ändligt vittnesrum av koherenta rester.

Här lägger vi dessutom på historik. Så länge den historik som kan påverka framtiden själv har ändligt många lägen kan även den vikas in i tillståndet.

Schemat är:

Periodicitet är alltså tillräckligt men inte nödvändigt. En aperiodisk omvärld passar också om dess framtidsrelevanta information genereras av en ändlig automat. Satsen behöver ändligt relevant minne.

Om framtida giltighet däremot beror på en obegränsad historik finns ingen sådan garanti.

Och där kommer Tågrälssatsen tillbaka igen

Del I gav Tågrälssatsens M ett nytt jobb.

Om O(t) är den exogena periodiska lockouten och
måste
gälla för att det ens ska finnas X fria objekt vid varje tidpunkt.

Det är nu ett förfilter till fulltaktsgrafen.

Om
är problemet dött innan vi ens behöver bygga det endogena tillståndsrummet. Det finns en exogen tidpunkt där färre än X objekt över huvud taget kan användas.

Om
har vi däremot bara klarat den statiska spärren. Våra egna val kan fortfarande förbruka försök eller skapa cooldowns på ett sätt som senare tömmer systemet.

Där tar Tibiasatsen över.

Tågrälssatsen säger:

Tibiasatsen frågar:

Skillnaden är historiken.

I, II och III får olika jobb

Nu tycker jag också att de tre Tågrälssatserna landar renare.

Tågrälssatsen II avgör vilka periodiska spärrar som kan sammanfalla.

III beskriver och räknar deras vittnen utan att skanna hela tidsaxeln.

I tar maximumet och ger peak lockout M.

Tibiasatsen lägger sedan på den endogena dynamiken och frågar om det finns en cykel som överlever den för evigt:

M kan döda ett schema direkt. Men ett bra M kan inte ensam bevisa att loopen håller. Det är Tibiasatsens jobb.

Ett konkret tre-försöksexempel

Anta för enkelhetens skull:

Från Del I vet vi att kapaciteten räcker:

Det finns alltså ett optimalt homogent schema.

Men lägg nu på ett exogent datumvillkor: under vissa q får ett av objekten inte användas.

Då räcker inte längre talet K=4 för att besvara frågan. Två scheman kan ha samma K, X, R och P men hamna i olika lägen efter några steg därför att de har förbrukat olika försöksbudgetar när datumlockouten träffar.

Därför måste tillståndet innehålla både
och

Vi frågar inte längre bara hur mycket total budget som finns.

Vi frågar om budgeten kan placeras så att processen hittar tillbaka till ett tidigare fulltaktstillstånd.

Det är cykeln.

Avgörbar betyder inte billigt

Har omvärlden |Q| tillstånd och objekt j ett ändligt internt tillståndsrum Zⱼ får den raka produktkonstruktionen upp till
tillstånd.

För bara tre försöksnivåer plus "tom" får man redan faktorn 4^K.

Oändligheten är undanröjd som logiskt problem. Tillståndsexplosionen finns kvar som algoritmiskt problem.

När grafen väl är explicit kan nåbara cykler hittas med vanliga grafalgoritmer, exempelvis via starkt sammanhängande komponenter.¹ ² Men att först konstruera grafen kan vara den dyra delen.

Hårdheten försvann inte.

Den flyttade igen.

Vad satsen inte säger

Här behandlar jag ett enspelarproblem. Omvärldens tillstånd kan vara exogent, men dess utveckling är fixerad eller ingår i den givna övergångsmodellen. Schemaläggaren gör de fria valen.

Om en motståndare i stället får välja omvärldens nästa tillstånd blir frågan ett spel på en ändlig arena. Samma tillståndsidé överlever, men kriteriet är då inte bara "finns en cykel jag kan välja".

Och om systemet kräver obegränsat minne för att avgöra framtida giltighet är vi utanför satsens antaganden.

Så vad förenar Tibiasatsen?

Kalenderkrockssatsen gav mig först ett deterministiskt existensproblem.

Tågrälssatsen gjorde existensen till samtidighet och kapacitet.

Tre-försöksanalogin lade på något som saknades i båda: återanvändning förändrar själv framtidens sökrymd.

Därför får vi nu hela kedjan:

Och det är här jag tycker att ordet "självbärande" får en exakt betydelse.

En sökrymd är inte självbärande bara för att den är stor.

Den är självbärande om det finns en väg genom dess giltiga tillstånd som till slut kommer tillbaka till sig själv utan att takten X någon gång behöver brytas.

Det är en cykel.

Nästa och sista delen blir mindre abstrakt. Då tänker jag lägga detta på den faktiska källkoden till chrono-pi och peka ut vad som motsvarar q, X, work units, verifieraren och tillståndsövergångarna. Då får vi se om matematiken faktiskt beskriver maskinen, eller bara låter snygg på ett forum.

Prior art

¹ C. Baier & J.-P. Katoen,
Principles of Model Checking,
MIT Press, 2008. Ändliga
transition systems, liveness och
cykelbaserad verifiering.

² R. Tarjan, "Depth-First Search and
Linear Graph Algorithms",
SIAM Journal on Computing
1(2), 1972, 146–160. SCC kan hittas
i linjär tid i den explicita grafen.