Erdős och den probabilistiska metoden: bevisa existens med slump
Paul Erdős hade inget hem, inget jobb i vanlig mening och nästan inga ägodelar. Han tillbringade sitt liv med att resa mellan universitet med en resväska, dök upp på en kollegas tröskel med repliken "min hjärna är öppen" och lämnade efter sig en ström av satser och olösta problem som matematiker fortfarande arbetar med. Bland allt han skapade sticker en idé ut för att den ändrade hur bevis görs över huvud taget. Den kallas den probabilistiska metoden, och i dess kärna sitter ett drag som nästan låter som fusk: att bevisa att något finns genom att vägra bygga det.
Frågan: när är ordning oundviklig?
Börja med ett enkelt klingande pussel. På en fest med sex personer är vilka två som helst antingen vänner eller främlingar. Det visar sig att man bland vilka sex personer som helst alltid kan hitta tre som alla är ömsesidiga vänner, eller tre som alla är ömsesidiga främlingar. Ordning tvingar sig fram. Den gren av matematiken som studerar när detta måste hända är Ramsey-teorin, och den sätter ett tal på frågan.
Ramseys sats garanterar att dessa tal finns, men den säger inte hur stora de är. Den naturliga följdfrågan är: hur stor kan en grupp bli och ändå undvika varje enfärgat kluster av storlek k? Att svara på det betyder att bevisa att en sådan fiffig färgning finns. Och precis där blir det hopplöst att bygga en för hand, för antalet möjliga färgningar är astronomiskt.
Erdős drag: bygg den inte, räkna den
Erdős insikt, 1947, var att sluta försöka rita en bra färgning och i stället färga helt slumpmässigt, och sedan låta aritmetiken göra jobbet. Argumentet är kort nog att följa i sin helhet.
Färga varje förbindelse genom att singla slant
Ta n personer och betrakta det kompletta nätverket där varje par förenas av en kant. Färga varje kant oberoende slumpmässigt, röd eller blå, var och en med sannolikhet en halv. Ingen fiffighet, ingen design. Bara ett rättvist mynt för varje enda kant.
Mät hur sannolikt en grupp är att bli enfärgad
Fäst en viss mängd av k personer. Bland dem finns C(k,2) kanter, det vill säga förbindelser. Att alla de kanterna delar en enda färg är osannolikt: sannolikheten är , eftersom det finns två färger och var och en av de C(k,2) slantsinglingarna måste stämma. Kalla detta lilla tal p.
Addera det förväntade antalet dåliga grupper
Det finns C(n,k) olika grupper av k personer att oroa sig för. Genom lineariteten hos väntevärde är det förväntade antalet helt enfärgade grupper bara antalet grupper gånger sannolikheten för var och en: . Detta enda uttryck fångar, i genomsnitt, hur många enfärgade kluster en slumpmässig färgning innehåller.
Om genomsnittet ligger under 1 måste en felfri färgning finnas
Välj nu n ungefär . Med det valet blir det förväntade antalet ovan mindre än 1. Men en räkning av faktiska enfärgade grupper är ett heltal, och om genomsnittet över alla färgningar ligger under 1 måste minst en färgning få 0. Den färgningen har ingen enfärgad grupp av storlek k alls. Alltså är R(k,k) större än n, vilket är ungefär .
Läs det sista steget igen, för det är hela magin. Vi producerade aldrig en bra färgning. Vi beskrev aldrig en. Vi visade att den genomsnittliga färgningen ligger så nära felfri att en perfekt tvingas finnas någonstans i högen. Beviset ger dig säkerhet om ett specifikt objekt samtidigt som det inte pekar på något objekt i synnerhet.
Varför detta var revolutionerande
Före Erdős betydde att bevisa att något fanns nästan alltid att konstruera det, eller åtminstone beskriva en procedur som skulle göra det. Den probabilistiska metoden bröt den förväntningen. Den fastslog att slump själv kunde tjäna som bevis: om ett slumpmässigt försök lyckas med vilken sannolikhet över noll som helst är framgång möjlig, punkt.
Den ickekonstruktiva smaken sätter argumentet i samma familj som några av de elegantaste resultaten i matematiken. Cantors diagonalargument bevisar också existensen av något, ett tal som saknas på varje lista, genom ren logisk kraft snarare än explicit konstruktion. Båda delar den tysta, nästan oroande kraften: slutsatsen är vattentät även om den aldrig visar dig saken den utlovar. Slumpen här vilar på samma grunder som i förstå sannolikhet intuitivt, där idén om ett väntevärde, motorn i steg tre, byggs upp från grunden.
Erdős problem och deras AI-ögonblick
Erdős bevisade inte bara satser. Han ställde problem, hundratals, ofta med små kontantpriser som räckte från några dollar för en knivig övning till tusentals för en fråga han trodde var genuint djup. Många av de problemen är fortfarande öppna, och de har katalogiserats och underhålls omsorgsfullt på erdosproblems.com.
Zenen i det
Den probabilistiska metoden är vacker av samma skäl som ett bra trolleritrick: du ser varje steg, du kan inte hitta platsen där du lurades, och ändå känns resultatet omöjligt. Det finns inget handlag. Väntevärdet ligger verkligen under ett, och ett heltal under sitt eget genomsnitt måste sjunka till noll någonstans. Säkerheten är total, konstruktionen saknas, och båda de sakerna är sanna på en gång.
Det är den bestående lärdomen Erdős lämnade efter sig. Existens och konstruktion är inte samma sak. Ibland är det renaste sättet att veta att ett perfekt objekt finns därute att bevisa att genomsnittsobjektet är nästan perfekt, och låta gapet göra resten. För ett annat resultat där en enda rad knyter ihop idéer som verkar obesläktade erbjuder Eulers identitet den motsatta sortens skönhet: där Erdős trollar fram existens ur räkning, spikar Euler fast ett exakt och oundvikligt tal.
Vanliga frågor
- Vad är den probabilistiska metoden?
- Det är ett sätt att bevisa att ett objekt med en viss egenskap finns, utan att konstruera objektet direkt. Du bygger en slumpmässig version av saken, visar att sannolikheten att den har den egenskap du vill ha är större än noll, och drar slutsatsen att minst ett sådant objekt måste finnas. Paul Erdős banade väg för tekniken, och den är nu ett centralt verktyg i kombinatorik och datavetenskap.
- Vad bevisade Erdős med den?
- Hans banbrytande resultat från 1947 gav en undre gräns för Ramsey-tal: han visade att det diagonala Ramsey-talet R(k,k) är större än 2^(k/2). På vanlig svenska: det finns sätt att färga förbindelserna i ett stort nätverk med två färger så att ingen stor grupp är helt förbunden i en enda färg. Han bevisade att dessa färgningar finns utan att någonsin visa upp en, bara genom att räkna.
- Hur kan man bevisa att något finns utan att bygga det?
- Med medelvärden. Om du plockar ett objekt slumpmässigt och räknar ut det förväntade antalet brister det har, och det förväntade antalet hamnar under 1, då måste minst ett objekt i poolen ha noll brister. Ett slumpmässigt val vars genomsnittliga bristantal är mindre än ett garanterar att ett perfekt exempel sitter någonstans i samlingen, även om argumentet aldrig pekar ut vilket.
- Vad är ett Ramsey-tal?
- Ramsey-talet R(k,k) är den minsta gruppstorlek som tvingar fram ordning, hur du än arrangerar sakerna. Konkret är R(k,k) det minsta antalet personer så att, hur du än delar varje par i vänner eller främlingar, du är garanterad en grupp på k personer som alla är ömsesidiga vänner eller alla ömsesidiga främlingar. Ramseys sats säger att dessa tal finns; Erdős metod visar att de växer mycket snabbt.
- Varför är den probabilistiska metoden viktig idag?
- Den gjorde slump till en bevismetod, och den idén löper nu genom kombinatorik, algoritmdesign, kodningsteori och teoretisk datavetenskap. Många resultat om nätverk och algoritmer bevisas fortfarande genom att visa att en slumpmässig konstruktion fungerar med positiv sannolikhet. Metoden är också skälet till att en stor del av Erdős egna problem fortfarande är aktiva forskningsmål.
Öva själv nu
Tyckte du det var kul att tänka igenom det här?
Math Zen gör den här sortens intuition till daglig övning, med adaptiva uppgifter inom 24 matteområden.
