Förstaårsstudent finner paradoxala taluppsättningar | Quanta Magazine

Matematiker gläds när de bevisar att till synes omöjliga saker existerar. Så är fallet med en nytt bevis publicerades online i mars av Cédric Pilatte, en förstaårsstudent vid University of Oxford.

Pilatte bevisade att det är möjligt att skapa en uppsättning - en samling siffror - som uppfyller två till synes inkompatibla egenskaper. Den första är att inga två par av nummer i uppsättningen summerar till samma summa. Lägg till exempel ihop två valfria nummer i {1, 3, 5, 11} så får du alltid ett unikt nummer. Det är lätt att konstruera små "Sidon"-uppsättningar som den här, men när antalet element ökar, ökar också sannolikheten att summorna kommer att sammanfalla, vilket förstör uppsättningens Sidon-het.

Det andra kravet är att setet måste vara mycket stort. Det måste vara oändligt, och du bör kunna generera ett tillräckligt stort tal genom att lägga ihop högst tre tal i mängden. Denna egenskap, som gör mängden till en "asymptotisk grund av ordning 3", kräver en stor, tät uppsättning tal. "De drar i motsatta riktningar," sade Pilatte. "Sidon-uppsättningar är begränsade till att vara små, och en asymptotisk grund är begränsad till att vara stor. Det var inte självklart att det kunde fungera.”

Frågan om en sådan uppsättning existerar har dröjt i decennier, ända sedan den ställdes av den produktive ungerske matematikern Paul Erdős och två kollaboratörer 1993. Erdős fascination för Sidon-uppsättningar kan spåras till ett samtal han hade 1932 med deras uppfinnare Simon Sidon, som vid den tiden var intresserad av att förstå tillväxthastigheten för dessa uppsättningar. (Erdős skulle senare beskriva Sidon som "galnare än en genomsnittlig matematiker", vilket han nästan säkert menade som en komplimang.)

Sidon-uppsättningar uppstår i en mängd olika matematiska sammanhang, inklusive talteori, kombinatorik, harmonisk analys och kryptografi, men den enkla frågan om hur stora de kan bli har varit ett bestående mysterium som Erdős funderat på under stora delar av sin karriär. Erdős insåg tidigt att Sidon-set är extremt svåra att skala. 1941 han och en annan matematiker visat att den största möjliga Sidon-mängden vars medlemmar alla är mindre än något heltal N måste vara mindre än kvadratroten av N plus en term som växer i proportion till den fjärde roten av N. (Senast 1969 skulle Bernt Lindström visa att den är mindre än $latex sqrt{N}+sqrt[4]{N}+1$, och 2021 en annan grupp matematiker spände gränsen till $latex sqrt{N}+0.998 gånger sqrt[4]{N}$.) Sidon-uppsättningar måste med andra ord vara glesa.

Det har länge varit känt att en Sidon-uppsättning inte kan vara en asymptotisk grund av ordning 2, där vilket heltal som helst kan uttryckas som summan av högst två tal. (De udda talen utgör till exempel en grund för ordning 2.) Som Pilatte förklarade är detta så enkelt att visa att matematiker inte brydde sig om att skriva ner det: "Att ordning 2 är omöjligt var förmodligen känt mycket tidigare än det uttryckligen skrevs i litteraturen." Han förklarade att detta beror på att "Sidon-sekvenser inte kan överstiga en viss densitet, medan asymptotiska baser av ordning 2 alltid är tätare än den tröskeln, så de två egenskaperna kan inte hålla på en gång."

Man trodde allmänt att en asymptotisk grund av ordning 3 kunde konstrueras från en Sidon-uppsättning, men att bevisa detta var en annan sak. "Folk trodde att detta borde vara sant," sa Pilattes rådgivare James Maynard. "Men det fanns en svårighet med de tekniker vi använde."

Vissa framsteg hade gjorts innan Pilatte antog utmaningen. 2010, den ungerske matematikern Sándor Kiss visade att en Sidon-mängd kan vara en asymptotisk grund av ordning 5 — vilket betyder att vilket tillräckligt stort heltal som helst kan skrivas som summan av högst fem element i mängden — och 2013 Kiss och två av hans kollegor visat gissningen om en asymptotisk grund av ordning 4. Två år senare, den spanske matematikern Javier Cilleruelo tog dessa resultat ett steg längre genom att bevisa att det är möjligt att konstruera en Sidon-mängd som är en asymptotisk grund av ordning 3+ e, vilket betyder att ett tillräckligt stort heltal N kan skrivas som summan av fyra medlemmar av Sidon-mängden, med en av dem mindre än N^e för godtyckligt liten positiv e.

Dessa fynd erhölls med hjälp av variationer av en probabilistisk metod som pionjärer av Erdős som innebär att generera en slumpmässig uppsättning heltal och justera den något för att skapa en uppsättning som uppfyller båda egenskaperna.

Pilatte insåg att den probabilistiska metoden hade drivits så långt den kunde gå. "Du kan få en grund för ordning 4 genom att använda probabilistiska metoder, men du kan inte få en grund för ordning 3," sa han. "Det misslyckas bara."

Så Pilatte tog en annan väg och vände sig istället till en procedur som använder logaritmerna för primtal som byggstenar i Sidon-mängderna. Utvecklad av den ungerske talteoretikern Imre Ruzsa och CillerueloDetta tillvägagångssätt ger större, tätare Sidon-uppsättningar än den probabilistiska metoden, som Pilatte behövde för att skapa en bas av låg ordning som också lydde Sidon-egenskapen. Men metoden krävde en anläggning med primtal som även världens främsta experter saknade. "Du skulle behöva en förståelse för primtal som går utöver allt vi har," sa Pilatte. "Så det var inte bra."

Sökandet efter en lösning tog Pilatte i en oväntad riktning, bort från additiv talteorin och in i en värld av algebraisk geometri, en gren av matematiken som studerar förhållandet mellan geometriska former, som kurvor och ytor, och ekvationerna som definierar dem. Med en idé från Cilleruelo började Pilatte med att ersätta siffror med polynom, vilket omedelbart gjorde problemet mer löst.

Ett polynom är ett algebraiskt uttryck som består av en summa av termer, som var och en är en produkt av en konstant koefficient och en eller flera variabler upphöjda till icke-negativa heltalspotenser. Termerna kan kombineras med addition, subtraktion och multiplikation. Till exempel 3x² + 22x + 35 är ett polynom med tre termer. Att faktorisera ett polynom innebär att dela upp det i en produkt av andra, enklare polynom. I det här exemplet, 3x² + 22x + 35 = (x + 5)(3x + 7). Ett irreducerbart polynom - ett som inte kan faktoriseras - är analogen till ett primtal.

Att byta heltal mot variabler och koefficienter kan låta konstigt, men de har mer gemensamt än du kanske tror. "Det visar sig att polynom beter sig väldigt likt heltalen", sa Pilattes Oxford-kollega Thomas Bloom. "Jag kan addera dem, subtrahera dem, multiplicera dem, dividera dem." Och i vissa avseenden förstår matematiker polynom mycket bättre än siffror. "Alla dessa saker som, med primtal, låter som science fiction för oss är kända i polynomvärlden," sa Maynard.

Med hjälp av en nyligen resultat av Columbia University matematiker Will Sawin på fördelningen av irreducerbara polynom i aritmetiska progressioner, kunde Pilatte konstruera en uppsättning som hade precis rätt mängd slumpmässighet och precis rätt täthet av tal för att tillfredsställa Erdős begränsningar.

"Jag var extremt glad," sa Pilatte. "Jag ansluter mig till gruppen människor här som har löst ett Erdős-problem, och det är roligt."

Men det som gläder honom mest är det överraskande sättet han kom fram till lösningen på. "Det är coolt att dessa mycket djupa tekniker från algebraisk geometri också kan användas för denna enkla och konkreta fråga om uppsättningar av tal," sade han.

Erdős problem har en kuslig förmåga att avslöja kopplingar mellan förment orelaterade grenar av matematik, och de upptäckter som matematiker gör när de försöker svara på dem är ofta mer meningsfulla än själva svaren. "De är vilseledande i hur djupa de är, och Cédrics lösning är ett bra exempel på detta," sa Bloom. "Jag är säker på att Erdős skulle ha varit överlycklig."

Rättelse: Juni 5, 2023
Den här artikeln gav ursprungligen ett exempel på en Sidon-set som egentligen inte är en Sidon-set. Det exemplet har tagits bort.