En AI:s angrepp på progressionsfria mängder: en liggare över vad som körde fast

TL;DR. En AI-assistent arbetade med två problem kring progressionsfria mängder: ett argument för det reciproka summaproblemet och en kvasipolynomiell gräns för varje fix progressionslängd. Den utgick från Bloom och Sisask...

Viktiga slutsatser

Två uppgifter, och bara en av dem gjordes någonsin anspråk på. Materialet delar upp sig i två uppgifter, och det är värt att hålla isär deras status.
Täthetsminskning är inte detsamma som summerbarhet. Det första hindret visar sig på nivån för argumentets arkitektur, före all Fourieranalys.
Att behålla struktur, och varför tre termer inte generaliseras. En föreslagen åtgärd är att behålla strukturen.
Att justera frekvenser en gång i stället för många gånger. Sekventiell justering av frekvensfunktioner är där ackumuleringsproblemet biter som hårdast.

Det mest användbara ett ofullständigt bevis kan visa är exakt var det brister, och det här brister på ett dussintal specifika ställen.

Sammanfattning för beslutsfattare

Arbetet har två uppgifter. Den första utvecklar ett argument för det reciproka summaproblemet. Den andra söker en kvasipolynomiell gräns för varje fix progressionslängd, och det målet uppnås inte.

Baslinjen är Bloom och Sisasks resultat om reciproka summor för tre termer. Kvalitativ täthetsminskning i sig ger inte den summerbarhet som argumentet behöver.

Många angreppssätt prövades: strukturerade omgivande mängder, simultan frekvensjustering, lemman för gles räkning, Croot-Sisask-utjämning, lyftning och iteration, hörn samt entropi på skalan p = log M. Vart och ett mötte ett redovisat hinder.

Den sista beräkningen lämnades ofullständig, utan ett restriktionslemma eller en princip för gles räkning.

För grundare och tekniska ledare handlar lärdomen om metod: en liggare över namngivna misslyckanden är en mer pålitlig leverans än en tvärsäker skiss.

Två uppgifter, och bara en av dem gjordes någonsin anspråk på #

Materialet delar upp sig i två uppgifter, och det är värt att hålla isär deras status. Den första utvecklar ett argument för det reciproka summaproblemet. Den andra söker en kvasipolynomiell gräns för varje fix progressionslängd. Verben spelar roll. Den första uppgiften beskrivs som att utveckla ett argument. Den andra söker bara en gräns. Ingenting i protokollet säger att det andra målet nåddes, och jag kommer att behandla det som ett mål genom hela texten.

Assistenten börjar inte från noll. Den använder Bloom och Sisasks resultat om reciproka summor för tre termer som baslinje. Allt därefter är ett försök att nå bortom baslinjen, antingen mot längre progressioner eller mot ett starkare kvantitativt påstående. Notationen slås fast tidigt. För varje k är r_k(N) den största storleken på en delmängd av {1, ..., N} utan någon icke-trivial progression med k termer. En mängd A med täthet α = |A|/N är studieobjektet, och den normaliserade funktionen är f = 1_A/α.

Den normaliseringen driver det mesta av vad som följer. Definiera μ = 1_A/α, så att E[μ] = 1, och sätt M = α^-1. Den logaritmiska glesheten är då p = log(1/α), vilket är detsamma som log M. Ju glesare mängden är, desto större blir M och p. Varje hinder nedan är, i en eller annan form, ett uttalande om vad som händer när denna gleshet växer.

Täthetsminskning är inte detsamma som summerbarhet #

Det första hindret visar sig på nivån för argumentets arkitektur, före all Fourieranalys. Protokollet säger rent ut att kvalitativ täthetsminskning i sig inte ger denna summerbarhet. Att veta att tätheter krymper när man rör sig genom skalor räcker inte. Det reciproka summaproblemet kräver att krympningen kvantifieras tillräckligt väl för att kunna summeras.

En frestande utväg är en rekursionsrelation. Anteckningarna säger att en tillräckligt stark rekursion för extremala progressionsfria tätheter skulle kunna ge summerbarhet över exponentiella skalor. Den meningen är garderat uttryckt, och bör förbli så. Den beskriver vad en hypotetisk stark rekursion skulle kunna åstadkomma. Den redovisar ingen sådan.

En andra kostnad är skild från den första. Assistenten identifierar ackumuleringen av många svaga korrelationer som en ytterligare kostnad. Varje enskild korrelation kan vara harmlös medan deras summa inte är det. Detta tema återkommer: ett steg som är billigt en gång blir dyrt när det måste upprepas.

Att behålla struktur, och varför tre termer inte generaliseras #

En föreslagen åtgärd är att behålla strukturen. Assistenten föreslår att man behåller strukturerade omgivande mängder genom på varandra följande steg. Tanken, så som den garderas i källan, är att man inte bör kasta bort den strukturerade mängd man hittade i ett steg när man går vidare till nästa.

Fallet med tre termer har en egenskap som längre progressioner saknar. Den positivitetsmekanism som är användbar för progressioner med tre termer kan inte direkt utvidgas till längre rotade räkningar. Detta är det första av flera ställen där hindret är specifikt för k större än tre. En senare anteckning gör samma poäng i allmänna ordalag: längre progressioner introducerar ytterligare hinder av högre ordning.

Protokollet innehåller en tensorproduktskiss om huruvida fixa likformighetsnormer kan kontrollera glesa normaliserade funktioner. Assistenten slutför inte skissen. Jag rapporterar hellre det än antyder att frågan är avgjord åt endera hållet.

Att justera frekvenser en gång i stället för många gånger #

Sekventiell justering av frekvensfunktioner är där ackumuleringsproblemet biter som hårdast. Om varje justering kostar lite, kostar en lång kedja av dem mycket. Assistenten föreslår att man justerar flera frekvensfunktioner samtidigt, i stället för att ackumulera förluster genom sekventiell justering. Marginalanteckningen uttrycker det rakt på sak: "Inga iterativa förluster om alla frekvenser justeras samtidigt." Precis som det förslag den sammanfattar är meningen garderad, eftersom den beskriver vad simultan justering skulle ge om den fungerade.

Anteckningen anger sedan vad som fortfarande saknas. S_h skulle behöva kunna återskapas från frekvenser med stora korrelationer, åtminstone exp(-poly). Det förblir ett krav, inte ett resultat. De korrelationer som organiseras är de för parprodukterna f(x)f(x + h), med f = 1_A/α och α = |A|/N.

Även om man antar detta behöver assistenten fortfarande bevara relativ korrelation och slutföra räkneargumentet. Idén om simultan justering har alltså en tilltalande egenskap, inga iterativa förluster, och en lista över saker som ingen har verifierat. Ett besläktat angreppssätt har en besläktad begränsning. Trunkering av sällsynta koherenta toppar fungerar för oberoende frekvenskluster, men att utvidga det argumentet till beroende kluster förblir olöst.

Sällsynta tomma delar och kostnaden för adaptiv fyllning #

När argumentet går från bokföring på Fouriersidan till att faktiskt räkna progressioner dyker ett strukturellt problem upp. Assistenten identifierar ett hinder: övre täthetsgränser på strukturerade delar tillåter sällsynta tomma delar. En övre gräns för hur mycket av A som ligger i en del säger ingenting om huruvida något av A alls ligger där. En del som är sällsynt och tom kan rymmas inom en familj av delar som alla uppfyller gränsen.

Ett svar är adaptiv fyllning, och det kommer med en egen prislapp. Adaptiv fyllning introducerar ytterligare genomförbarhetsvillkor som assistenten inte har bevisat. En majorant är ett naturligt sätt att utesluta de sällsynta dåliga delarna. Assistentens citerade text säger att en majorant på alla sällsynta atomer sannolikt är orealistisk. Anmärkningen är garderad, men den pekar bort från den mest direkta lösningen.

Detta är det mönster som förklarar resten av protokollet. Ett billigt argument behöver en undre gräns någonstans, de tillgängliga verktygen ger övre gränser, och gapet mellan dem fylls av sällsynta, glesa, tomma ting.

Att låna maskineri för gles räkning och upptäcka att det lånade inte räckte #

Assistenten vände sig till befintlig litteratur om gles räkning för att hitta en väg över. Två källor formade försöket.

Gällande Conlon-Fox-Zhao-förtätning fann assistenten att den förlitade sig på tvåsidiga uppskattningar av linjära former. Det spelar roll eftersom ramen här har en struktur med övre gränser och inte en tvåsidig sådan. En metod byggd på tvåsidig kontroll är inte tillgänglig när bara ena sidan är känd.

Det glesa grafräkningslemmat av Filmus, Hatami, Hosseini och Kelman gav modellen för asymmetriska rutnätsmoment och positivt semidefinit obalansering. Det tjänade alltså som en mall, inte som en färdig sats att sätta in. Trots det återvände samma svårighet. Övre gränser på egen hand stötte upprepade gånger på glesa hål. En ytterligare komplikation gör rutnätsmomenten svåra att tolka: stora centrerade rutnätsmoment kunde spegla saknad massa snarare än koncentration uppåt. Ett stort moment ser ut som bevis på koncentration, men det kan lika gärna skapas av massa som inte finns där. Den tvetydigheten är problemet med glesa hål sett från momentsidan.

Därefter övervägde assistenten små potensförluster i M. Den erhöll ingen lämplig räknesats. Det är ett rent negativt resultat, och det snävar in fältet: inte ens när argumentet tilläts förlora en liten potens av M hittades någon lämplig räknesats.

Utjämning var för dyr att tillämpa #

Croot-Sisask-utjämning är en standardväg för att regularisera en mängd före räkning. Assistenten övervägde den och fann att den nödvändiga noggrannheten blev för kostsam i den föreslagna tillämpningen. Metoden var inte felaktig. Dess pris översteg vad argumentet kunde betala.

Samma ekonomi styr de andra vägarna. För fiberargument multiplicerades inte fibergränser automatiskt, och sfärer med konstant norm blockerade det eftersträvade starka avtagandet över fixa sifferalfabet. En produktstruktur antyder att gränser på delar borde kombineras till en gräns för helheten, men här gjorde de inte det. Försök med lyftning och iteration förlorade fortfarande för mycket kvantitativt.

Ben-Sasson-Ron-Zewis angreppssätt med approximativ dualitet övervägdes härnäst. Assistenten fann att den tilltänkta iterationen förlorar för mycket kvantitativt. Detta är samma dom som vid lyftningsförsöket, nådd från ett annat håll, vilket antyder att problemet ligger i själva iterationen och inte i någon enskild konstruktion. Jag håller det som en observation om mönstret, inte en bevisad diagnos.

En rad av optimism, och aritmetiken som undergrävde den #

Protokollet innehåller ett ögonblick av skenbara framsteg. Assistentens citerade text hävdar att fluktuationer i produktgrad hanteras med polynomiell precision, inklusive utropstecken. Det är ett garderat påstående, citerat så som assistenten skrev det.

Assistenten lade sedan märke till problemet med det. Teckenförsedda utvecklingar kunde ha absolut massa av ordningen 2^p, vilket överväldigar polynomiell noggrannhet. Kom ihåg att p = log M. Polynomiell precision i M är ett blygsamt mål, medan en teckenförsedd utveckling med massa av ordningen 2^p är exponentiellt större. Precisionen är verklig, men den utsläckning den förlitar sig på kan inte absorbera så mycket massa.

Jag finner detta vara den mest lärorika posten i liggaren, eftersom den visar hur självkontrollen fungerar. Ett påstående som gjordes med ett utropstecken öppnades på nytt, och den aritmetik det vilade på befanns otillräcklig. Det är så ett ärligt arbetsprotokoll ser ut. Entusiasmen och korrigeringen ryms båda i samma dokument.

Hörn och lådor fogas inte samman till längre progressioner #

En annan strategi var att använda ett starkare känt resultat som språngbräda. Den kvasipolynomiella hörngränsen är det relevanta verktyget, men de resulterande hörnen fogades inte automatiskt samman till längre progressioner. Ett hörn är ett tvådimensionellt mönster och en lång progression är ett endimensionellt sådant, och övergången mellan dem sker inte automatiskt.

Lådräkningen med fyra termer uppvisar en besläktad svårighet. Positivitet hos lådräkningen med fyra termer kontrollerade inte dess exceptionella diagonal. En positiv räkning kan fortfarande domineras av degenererade konfigurationer, och diagonalen är där dessa bor.

Anteckningarna erbjuder dock en möjlig väg framåt, noggrant garderad. Fullständiga lådnormer erbjuder en möjlig mekanism för huruvida övre räkningar ensamma kan tvinga fram undre progressionsräkningar. Den frågan, huruvida ensidig information kan tvinga fram en undre gräns, är den som hela projektet kretsar kring. Ändå finns det en gräns för hur långt detta sträcker sig. Negativa kubiska bidrag hindrar en rättfram utvidgning till progressionssystem.

Övergång till entropi på skalan p = log M #

När de direkta räknevägarna var blockerade vändes undersökningen mot entropi på skalan p = log M, med inspiration från Kelley-Mekas användning av höga moment. Valet av skala är inte godtyckligt: p = log M är exakt den logaritmiska gleshet som definierades i början.

Assistentens citerade text föreslår att man använder entropi i stället för L2 genom icke-negativitet och frekvensdissociativitet (Chang). Det är ett förslag, inte ett resultat. Resonemanget är att μ = 1_A/α är icke-negativ och att Changs dissociativitet ger struktur på frekvenssidan, så entropi skulle kunna göra det arbete som en L2-storhet inte klarar.

För att detta skulle fungera behövde assistenten en specifik analytisk indata. Assistenten sökte en Fourierrestriktionsuppskattning ||g_hat||_q = O(1) för begränsat g och fixt q > 2, under lämpliga lokala övre gränser. Detta var ett mål. Det fastställdes inte.

Hindret dök upp i nästa steg. Att extrahera struktur från höga moment förlorade för mycket massa. Höga moment är där argument i Kelley-Meka-stil hämtar sin styrka, och här var de också platsen där argumentet tappade det som det behövde behålla.

Beräkningen som kom närmast #

Den sista beräkningen förtjänar en egen granskning, eftersom den rymmer både en framgång och ett misslyckande. Den når en fullständig ändpunktsgräns under sina faltningsantaganden. Det är ett verkligt resultat, angivet som ett sådant, och det bär förbehållet "under sina faltningsantaganden". Gränsen håller när dessa antaganden gör det.

Men den lyckas inte passera tröskeln vid exponent tre som krävs av det föreslagna räkneargumentet. Assistentens utdrag noterar en svag l3-gräns från faltning och tak, och att en strikt bättre exponent (under 3) krävs för interpolation. Uttryckt i klartext landar beräkningen exakt på fel sida av en gränslinje. En gräns vid exponent tre räcker inte, och interpolation kräver någonting strikt bättre.

Det är frestande att läsa en sådan nära-träff som "nästan framme". Jag skulle stå emot det. Protokollet säger inte hur långt beräkningen är från tröskeln, och ett gap som utgörs av en enda exponent kan fortfarande vara hela problemet. Vad protokollet däremot säger är att assistenten lämnade beräkningen ofullständig, utan att härleda vare sig restriktionslemmat eller principen för gles räkning. Dessa två saknade pusselbitar är projektets öppna skuld.

Vad liggaren är värd #

Det vore lätt att avfärda detta som ett misslyckat försök. Jag menar att det är att läsa bevisen fel, av ett skäl som gäller långt utanför talteorin.

Dokumentet är specifikt. Det namnger hindret vid varje vägskäl: sällsynta tomma delar, saknad massa i rutnätsmoment, tvåsidiga uppskattningar i Conlon-Fox-Zhao, teckenförsedd massa som är exponentiell i p, den exceptionella diagonalen i lådräkningen med fyra termer, negativa kubiska bidrag. Det skiljer en påvisad begränsning från en eftersträvad mekanism. Det markerar rekursionen för summerbarhet som någonting som skulle kunna fungera, och den andra uppgiften som någonting eftersökt. Det anger vad assistenten inte slutförde.

För en grundare eller teknisk ledare som utvärderar AI-assisterad forskning är det precis detta man ska leta efter. Ett system som returnerar ett tvärsäkert argument som ser komplett ut är svårt att granska. Ett system som returnerar en lista över namngivna misslyckanden, där den enda nära-framgången tydligt markeras som att den inte når över en tröskel, kan granskas rad för rad. Någon kan plocka upp problemet med exponent tre, eller problemet med beroende kluster, och veta exakt vad utgångsläget är.

Det finns också ett mönster som är värt att påpeka direkt. Många av misslyckandena är ackumuleringsmisslyckanden: svaga korrelationer som läggs ihop, sekventiella justeringar som förstärker varandra, iteration som förlorar för mycket, fibergränser som inte låter sig multipliceras. En föreslagen åtgärd riktar in sig direkt på detta genom att justera frekvenser samtidigt så att ingen iterativ förlust uppstår. Förslaget är garderat, och dess förutsättning, att återskapa S_h från frekvenser med stora korrelationer, är obevisad. Ändå är det det förslag i protokollet som svarar mest direkt på det vanligaste klagomålet.

Den öppna fråga som protokollet väcker är därför snäv och kontrollerbar. Kan en gräns som är strikt bättre än exponent tre erhållas under de faltningsantaganden som redan ger ändpunktsgränsen? Om så är fallet har interpolation någonting att arbeta med. Om inte, är vägen via Fourierrestriktion och principen för gles räkning, av vilka ingendera har härletts, de platser man bör titta på härnäst.

Vanliga frågor #

Vilka var de två matematiska problem som AI-assistenten undersökte?

Assistenten arbetade med två besläktade uppgifter rörande progressionsfria mängder: att utveckla ett argument för det reciproka summaproblemet, och att söka en kvasipolynomiell gräns för varje fix progressionslängd k. Medan den använde Bloom och Sisasks resultat om reciproka summor för tre termer som baslinje, uppnåddes inte den kvasipolynomiella gränsen för godtyckliga progressionslängder.

Varför lyckades inte övre täthetsgränser ge det nödvändiga räknelemmat?

Övre täthetsgränser på strukturerade delar tillåter sällsynta tomma delar, vilket innebär att en övre gräns för hur mycket av en mängd A som ligger inuti en del inte garanterar att några element ur A alls ligger där. Under flera försök stötte övre gränser på egen hand upprepade gånger på glesa hål, och stora centrerade rutnätsmoment kunde spegla saknad massa snarare än koncentration uppåt.

Var körde den sista beräkningen fast?

Den sista beräkningen nådde en fullständig ändpunktsgräns under sina angivna faltningsantaganden, men gav bara en svag l3-gräns som inte passerade tröskeln för en exponent strikt under tre, vilket krävs för interpolation. Assistenten lämnade beräkningen ofullständig utan att härleda vare sig Fourierrestriktionslemmat eller principen för gles räkning.

Referenser #

Thomas F. Bloom and Olof Sisask, (2020). Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions ⧉. arXiv.
Zander Kelley and Raghu Meka, (2023). Strong Bounds for 3-Progressions ⧉. arXiv.
David Conlon, Jacob Fox, and Yufei Zhao, (2014). A relative Szemerédi theorem ⧉. Geometric and Functional Analysis.
Ernie Croot and Olof Sisask, (2010). A probabilistic technique for finding almost-periods of convolutions ⧉. Geometric and Functional Analysis.

Senast granskad 2026-11-01.

Återpublicera den här artikeln

En AI:s angrepp på progressionsfria mängder: en liggare över vad som körde fast — Sebastien Rousseau

En AI-assistent arbetade med två problem kring progressionsfria mängder: ett argument för det reciproka summaproblemet och en kvasipolynomiell gräns för varje fix progressionslängd. Den utgick från Bloom och Sisask...

Den här artikeln är licensierad under Creative Commons Attribution 4.0 International. Återpublicering kräver attribution till den kanoniska URL:en.

En AI:s angrepp på progressionsfria mängder: en liggare över vad som körde fast — Sebastien Rousseau

En AI-assistent arbetade med två problem kring progressionsfria mängder: ett argument för det reciproka summaproblemet och en kvasipolynomiell gräns för varje fix progressionslängd. Den utgick från Bloom och Sisask...

Originally published at https://sebastienrousseau.com/sv/2026-10-24-angrepp-pa-progressionsfria-mangder-liggare-over/ by Sebastien Rousseau.
Licensed under CC-BY-4.0.

SEBASTIEN ROUSSEAU FOUNDER · ENGINEER