Samfurin OpenAI na cikin gida ya tantance saurin raguwar Cohn-Elkies

TL;DR. Samfurin OpenAI na cikin gida ya tantance ainihin saurin raguwar shirin Cohn-Elkies na sphere packing: ingantawar exponent ta farko tun 1978, da lower bound mai dacewa.

Mahimman Bayanai

Mene ne wannan tarin, kuma me ya sa sakamako ɗaya ya yi fice. Takardar ta fara cikin tawali'u.
Shirin Cohn-Elkies da abin da yake iyakancewa. Sphere packing tana tambayar yadda ƙwallaye da ba sa haɗuwa da juna za su iya cika sarari da yawa.
Abin da tsarin ya riga ya cimma. Kafin mu juya zuwa sabon theorem, yana da kyau mu fayyace abin da tsarin linear programming na Fourier analysis ya riga ya bayar, domin sabon sakamakon a wani ɓangare bayani ne game da nisan da zai iya ƙara kaiwa.
Babban theorem. Babban theorem na takardar ya tabbatar da saurin exponential da aka yi hasashe a cikin Conjectures 3.1 da 3.2 na wannan takardar ta 2020.

Tarin sakamakon lissafi daga wani samfurin OpenAI na cikin gida ya warware ƙarfin asymptotic na linear program na Cohn-Elkies don sphere packing, yana ba da ingantawa ta farko ga babban exponent na sphere packing tun 1978, tare da lower bound mai dacewa daidai.

Mene ne wannan tarin, kuma me ya sa sakamako ɗaya ya yi fice #

Takardar ta fara cikin tawali'u. Ta gabatar da tarin sakamakon da wani samfurin OpenAI na cikin gida ya samu, kuma ta ce sun shafi lissafi da kimiyyar kwamfuta ta ka'ida. Wannan bayani ne na asali da kuma iyaka, kuma bai faɗi yadda aka yi amfani da samfurin ba ko yadda aka duba abin da ya fitar. Waɗannan tambayoyi suna da muhimmanci, kuma tushen kamar yadda aka taƙaita shi a nan ya bar su ba amsa, don haka wannan labarin ba zai yi kamar ba haka ba ne. Abin da iƙirarin suka goyi baya a zahiri shi ne jerin sakamakon da aka bayyana, kuma jerin ya yi tsawo har tambayar mai ban sha'awa ba ita ce ko wani abu ɗaya ya burge ba. Tambayar ita ce me ya sa ɗaya daga cikinsu ya cancanci mafi yawan hankali.

Dalilin shi ne sakamakon sphere packing shi kaɗai ne a cikin tarin da ya rufe wani gibin adadi a cikin shirin bincike mai dogon tarihi da sunaye sanannu. Sauran ma suna da ban mamaki a nasu matsayin. Wata ƙungiya bayyananniya da ba sofic ba (nonsofic group) ta amsa wata tsohuwar tambaya. Ƙaryata hasashen Connes ya warware wani abu da wani sanannen masanin lissafi ya gabatar. Amma sakamakon sphere packing yana zaune ne a ƙarshen wata sarƙa da ta fara daga tsarin Fourier analysis, ta wuce ta hanyar mafita biyu masu shahara a girma na musamman, har ta kai ga wata tambaya game da manyan girma da ta kasance a buɗe tsawon shekaru. Fahimtarsa na nufin fahimtar wannan sarƙa.

Saboda haka mafi yawan abin da ke biye ya shafi linear program na Cohn-Elkies: mene ne shi, me aka sani game da shi, me sabon theorem ɗin ya ce, da yadda aka gina ɓangaren sign uncertainty na hujjar. Sannan wani gajeren sashe ya duba sauran sakamakon da ke cikin tarin, kowanne kamar yadda aka bayyana shi ba tare da ƙari ba.

Shirin Cohn-Elkies da abin da yake iyakancewa #

Sphere packing tana tambayar yadda ƙwallaye da ba sa haɗuwa da juna za su iya cika sarari da yawa. Takardar ta kafa alamomi don haka. Ga cibiyoyin da tazararsu ba ta ƙasa da 1 ba, ∆d shi ne supremum na upper densities na ƙwallaye masu radius 1/2 a cikin Rd. A wata ma'anar, ∆d yana nufin mafi girman yawan sphere packing a cikin Rd. Duk abin da ke cikin babi na farko na tarin ana auna shi da wannan adadi.

Shirin Cohn-Elkies yana ba da upper bound ga ∆d. Ana rubuta mafi kyawun sakamakonsa LPd, wanda aka ayyana a matsayin mafi kyawun iyakar yawa da shirin ke bayarwa. Hanyar ita ce iyakar Gorbachev–Cohn-Elkies, wadda ke ba kowane f a cikin wani rukuni mai suna Ad upper bound na yawa vd f(0)/(2d f̂(0)). A taƙaice, za ka zaɓi auxiliary function f daga rukunin da aka yarda da shi, ka lissafa ƙimarsa a asali da ƙimar Fourier transform ɗinsa a asali, ka samar da wannan rabo tare da abubuwan girma da sikeli, kuma sakamakon zai iyakance yawan packing daga sama. Linear program ɗin yana neman f da zai sa wannan iyaka ta zama ƙarama gwargwadon iko.

Wannan tsari ne da dukan wahalarsa take a zaɓen f da kyau. Function da aka zaɓa da hikima yana ba da iyaka matsatsiya, kuma wanda aka zaɓa ba da kyau ba yana ba da iyaka mai rauni wadda har yanzu take da inganci. Shi ya sa lower bound mai dacewa a cikin sabon sakamako yake da muhimmanci haka. Yana magana ne game da kowane function da aka yarda da shi a lokaci guda, kuma yana mayar da neman functions mafi kyau zuwa tambaya rufaffiya.

Abin da tsarin ya riga ya cimma #

Kafin mu juya zuwa sabon theorem, yana da kyau mu fayyace abin da tsarin linear programming na Fourier analysis ya riga ya bayar, domin sabon sakamakon a wani ɓangare bayani ne game da nisan da zai iya ƙara kaiwa.

Viazovska ta yi amfani da wannan tsari don tabbatar da cewa lattice ɗin E8 yana ba da mafi kyawun packing a girma na takwas. Sannan Cohn, Kumar, Miller, Radchenko da Viazovska suka tabbatar da cewa lattice ɗin Leech shi ne mafi kyau a girma na ashirin da huɗu. Waɗannan sakamako ne daidai a girma ɗaya-ɗaya, kuma su ne dalilin da tsarin ya sami suna fiye da aikinsa na kayan aikin iyakancewa. A girma biyu na musamman, yana kaiwa ga ainihin amsa.

Hoton manyan girma ya fi duhu. Cohn da Zhao sun tabbatar da cewa linear program ɗin a koyaushe yana da ƙarfi aƙalla kamar iyakar spherical code ta Kabatianskii–Levenshtein. Wannan tabbaci ne mai amfani, domin iyakar Kabatianskii–Levenshtein ita ce mafi kyawun babban exponent da aka sani. Amma “aƙalla da ƙarfi kamar” yana barin dama biyu a buɗe: shirin zai iya dacewa da wannan exponent daidai, ko kuma ya fi shi. Takardar ta bayyana sakamakon a fili. Ko linear program ɗin yana inganta exponent na gargajiya na sphere packing a manyan girma ya kasance a buɗe.

Afkhami-Jeddi, Cohn, Hartman, de Laat da Tajdini sun yi hasashen saurin linear program ɗin a manyan girma. Hasashe abu ne mai sharaɗi, kuma tushen yana ɗaukarsa haka. Hasashe ne, da shaidar da marubutansa suke da ita ke goyon bayansa, kuma ba wanda ya tabbatar da shi. Sabon sakamakon ya canza matsayinsa.

Babban theorem #

Babban theorem na takardar ya tabbatar da saurin exponential da aka yi hasashe a cikin Conjectures 3.1 da 3.2 na wannan takardar ta 2020. A matakin da iƙirarin suka goyi baya: marubutan sun tantance ainihin saurin raguwar exponential na linear program na Cohn-Elkies don sphere packing. Ƙarfin asymptotic na shirin, a kalmomin tushen, an tantance shi daidai.

Sakamako biyu sun biyo kai tsaye daga tushen. Na farko shi ne ingantacciyar babbar iyakar packing a manyan girma. Na biyu shi ne an warware matsalar Fourier sign uncertainty mai dacewa ta hanyar asymptotic. Waɗannan sakamako ne na iri daban-daban. Ɗaya game da geometry ne ɗayan kuma game da analysis, kuma kasancewar theorem ɗaya ya ba da duka biyun shi ne alama ta farko cewa matsalar sphere packing da matsalar uncertainty fuskoki biyu ne na tsari ɗaya.

Tushen ya kuma sanya nasarar a gaban tarihi. Ya bayyana sakamakon a matsayin ingantawa ta farko tun 1978 ga babban exponent na sphere packing. Exponent na gargajiya na Kabatianskii–Levenshtein shi ne 0.59905576..., kuma wannan adadi shi ne ma'auni. Takardar ta rubuta cewa gyare-gyaren spherical code na baya sun inganta abubuwan ƙananan mataki kaɗai. A wata ma'anar, ga exponent ɗin kansa, wanda shi ne adadin babban mataki, babu abin da ya motsa.

Ina ganin wannan tsarin kallo shi ne daidai don tantance sakamakon. Ingantawa a ƙaramin mataki tana gyara constants da polynomial factors yayin da take barin saurin exponential a inda yake. Ingantawar exponent tana canza saurin. Iƙirarin sun goyi bayan wannan bambanci daidai, kuma sun goyi bayan cewa gyare-gyaren da suka gabata sun faɗa ne a ɓangaren ƙaramin mataki.

Girma / Tsari	Tushe na Gargajiya (1978)	Linear Program na Cohn-Elkies	Sabuwar Hujjar Samfurin
Exponent na Sphere Packing	Iyakar Kabatianskii–Levenshtein: 0.59905576...	Aƙalla da ƙarfi kamar iyakokin spherical code (Cohn–Zhao)	An tabbatar da ainihin saurin asymptotic da Afkhami-Jeddi et al. (2020) suka yi hasashe
Ƙarshen Iyaka	Gyare-gyaren ƙananan mataki kaɗai	Tambaya a buɗe kan gibin asymptotic a manyan girma	Lower bound mai dacewa daidai: babu auxiliary function da zai fi wannan sauri
Fourier Sign Uncertainty	Iyakokin alama daban-daban ($A^+(d) < A^-(d)$)	Yana da alaƙa da anti-self-Fourier test functions	An warware ta asymptotic; Mellin reflection ke tafiyar da sign uncertainty
Lambobin Gyaran Kuskure	Iyakokin gargajiya na spherical da binary codes	Suna haɗe ta asymptotic da iyakokin packing	Ingantawa da abubuwan exponential ga dukan sigogin tazara tabbatacciya
Rufin Hanya	Inganta polynomial factors ta lambobi	Buɗaɗɗen inganta auxiliary test functions $f \in \mathcal{A}_d$	An tabbatar da rufin lissafi: ƙarin riba na bukatar hanyoyin da ba na Cohn-Elkies ba

Me ya sa lower bound mai dacewa ya canza tambayar #

Ingantawar upper bound ita kaɗai za ta zama labari mai daɗi. Abin da ya sa wannan sakamako ya zama na ƙarshe ta hanyar da ba a saba ba shi ne rabinsa na biyu. Lower bound mai dacewa ya nuna cewa babu wani auxiliary function na Cohn-Elkies da zai iya inganta wannan exponent.

Ka yi tunanin abin da wannan ke yi wa shirin bincike. Kafin sakamakon, mai bincike da ke da kyakkyawan ra'ayi na gina auxiliary function yana da hanya mai ma'ana zuwa exponent mafi kyau na sphere packing. Bayansa, an rufe wannan hanya a matakin exponents. Duk wani ƙarin ci gaba a exponent dole ne ya fito daga wajen tsarin Cohn-Elkies, domin a cikinsa saurin yanzu ya zama daidai.

Ba na son in wuce gona da iri a kan wannan. Iƙirarin ba su ce sabon exponent shi ne ainihin exponent na sphere packing ba, kuma ba su ce sphere packing kanta ba za ta iya yin abin da ya fi ba. Bayanin ya shafi linear program ɗin: an tantance exponent ɗinsa, kuma ba za a iya fin sa ta hanyar canza auxiliary function ba. Ko wata dabara daban za ta iya fin sa tambaya ce da iƙirarin ba su taɓa ba. Wannan iyaka ce bayyananniya, kuma irin iyakar ce da ke gaya wa wani fanni inda zai duba gaba.

Akwai kuma karatu mai alaƙa da aiki a kan wannan, ga masu karatu da ke damuwa da inda ƙoƙari ke zuwa. Sanin rufin wata hanya daidai bayani ne mai amfani. Yana gaya maka ka daina ingantawa a cikin wannan hanya. Ga duk wanda ke raba lokacin bincike, sauyawa daga “wannan zai iya inganta” zuwa “wannan ba zai iya inganta ba” yana da daraja kamar sakamako mai kyau matsakaici.

Spherical codes da binary codes #

Tarin bai tsaya a packing ba. Upper bounds na gargajiya na binary da spherical codes masu tazara tabbatacciya sun inganta da abubuwan exponential ga dukan sigogi. Wannan jumla tana ɗauke da quantifier mai ƙarfi. Ingantawar ta abubuwan exponential ce, kuma tana aiki ga dukan sigogi, wanda bayani ne mafi faɗi fiye da ingantawa a wani yanki mai sauƙi.

Akwai kuma alaƙa da ke komawa zuwa Babi na 1. Ginin spherical code yana kuma dawo da exponent na sphere packing na Babi na 1. Don haka zaren biyu sun haɗu: ginin a ɓangaren codes yana sake samar da exponent na ɓangaren packing. Iƙirarin ba su bayyana hanyar wannan dawowa ba, kuma ba zan ƙirƙiri ɗaya ba. Abin da suka tabbatar shi ne alaƙar tana tafiya a wannan hanya, inda ginin spherical ke ba da exponent ɗaya da babin packing.

Yana da kyau mu tuna me ya sa wannan alaƙa ke da muhimmanci idan aka yi la'akari da tarihin da ke sama. Iyakar spherical code ta Kabatianskii–Levenshtein ita ce wurin kwatanta linear program ɗin, kuma theorem na Cohn da Zhao ya ce shirin a koyaushe yana da ƙarfi aƙalla kamarta. Sabbin sakamakon suna inganta iyakokin codes da na packing, kuma suna yin haka daga gini da ke komawa zuwa exponent na packing. Ana motsa ɓangarorin biyu tare.

Matsalar sign uncertainty #

Sakamako na biyu na babban theorem ya shafi Fourier sign uncertainty, kuma takardar ta ba da isassun ma'anoni don zana siffarsa.

Ga function g, an ayyana r(g) a matsayin infimum na R ≥ 0 da ke sa g(x) ≥ 0 ga |x| ≥ R. A sauƙaƙe, r(g) shi ne radius da bayansa g ba ta da ƙima mara kyau a ko'ina. Idan babu irin wannan radius, r(g) = ∞. Matsalar uncertainty ta shafi yadda za a iya ƙanƙantar da wannan radius ga functions da ke da wata dangantaka da aka ƙayyade da Fourier transforms ɗinsu.

Wannan dangantaka alama ce. Sharaɗin ĝ = ςg yana ɗaure function da Fourier transform ɗinsa har zuwa alamar. Alamomin +1 da −1 suna ba da matsalar uncertainty ta asali da ta cikawa, bi da bi. Cohn da Gonçalves sun gabatar da takwararta ta anti-self-Fourier, wadda ita ce matsalar cikawa, kuma sun haɗa ta da sphere packing. Wannan haɗi shi ne gadar da sakamakon sphere packing ke warware matsalar uncertainty ta asymptotic ta cikinta.

Matsalar cikawa ba abin mamaki ne kawai na analysis zalla ba. A cikin spinless modular bootstrap, modular S-antisymmetry tana samar da anti-self-Fourier test functions waɗanda alamarsu ta ƙarshe ke sarrafa spectral gap. Tushen ya ambaci Hartman, Mazáč da Rastelli da kuma takardar Afkhami-Jeddi et al. kan wannan. Don haka tambayar da ta fara a matsayin bayani game da functions da transforms ɗinsu ta kuma bayyana a wani yanayi mai suna da ke kama da physics, wato spectral gap. Iƙirarin ba su wuce hanyar layi ɗaya ba, ni ma ba zan wuce ba, amma tunatarwa ce cewa matsalar uncertainty tana da abokai a wajen sphere packing.

Appendix A ya ƙara kwatanta tsakanin matsalolin biyu. Ya lura cewa A+(d) < A−(d) ga dukan d. Wannan bayani ne cewa matsalolin biyu sun bambanta a kowane girma, inda adadi na farko ya fi na biyu ƙanƙanta sosai. Iƙirarin ba su ba da ƙarin fassara ba, kuma inequality ɗin ya cancanci a lura da shi kawai saboda yana aiki ga dukan d ba tare da wani banbanci ba.

Cikin hujjar: matsakaici, ɓacewa da ƙididdigar nauyi #

Takardar ta ƙunshi bayanai na fasaha da dama da ke ba da jin yadda aka gina nazarin uncertainty. Gutsure ne, kuma zan gabatar da su a matsayin gutsure, amma tare suna zana wata hanya.

Mu fara da symmetry. An ayyana matsakaicin juyawa (rotational average) ta amfani da normalised Haar measure a kan O(d). Ɗaukar matsakaicin function a kan juyawa yana samar da radial function, kuma manufar yin haka ita ce tana sauƙaƙa matsalar ba tare da karya ƙuntatawa ba. Tushen ya ce rotational averaging yana kiyaye kowane sharaɗin alama a cikin jerin ƙuntatawar matsalar, mai lamba (2). Ya ƙara da cewa idan ĝ = ςg, to r(Rg) ≤ r(g), inda Rg shi ne rotational average na g. Don haka matsakaici ba ya taɓa ɓata sign radius. Haka kuma, a kalmomin tushen, Rg ≠ 0 duk lokacin da g ≠ 0 ta zama ba ta da ƙima mara kyau a ƙarshe, don haka matsakaici ba ya share function da ke da halin alama daidai a nesa.

Waɗannan gaskiya uku tare suna tabbatar da ragewa zuwa radial functions. Ragewar ba ta ci komai a radius ba, tana kiyaye sharuɗɗan alama, kuma ba ta mayar da function zuwa sifili ba. Wannan ita ce siffar hujjar symmetry ta yau da kullum, kuma iƙirarin sun tabbatar da kowane sinadari nata.

Na gaba, asalin. Function g = h − ĥ yana ɓacewa a asali. Wannan irin ƙaramar gaskiya ce da ke yin babban aiki a cikin hujja, domin iyakar Cohn-Elkies ta ƙunshi ƙima a asali kai tsaye, kuma function da ke ɓacewa a can yana nuna hali daban da wanda ba ya ɓacewa. An kuma rubuta wani mataki na gyara mai alaƙa: function da aka gyara gn yana cika gn(0) = 0 da gn → g a cikin L1. Don haka jerin functions da aka gyara, kowannensu yana ɓacewa a asali, suna kusantar g a ma'anar L1. Wannan yana bar hujjar ta yi aiki da functions da ke cika sharaɗin asali daidai yayin da har yanzu suke kusantar abin da ake nufi.

Sannan akwai ƙuntatawa ta adadi. Ƙididdigar nauyi (mass estimate) tana tilasta 1/a ≥ (1/π − o(1))√d. Iƙirarin ba su ayyana a ba, don haka ba zan iya faɗi abin da yake aunawa ba, kuma ba zan yi hasashe ba. Abin da za a iya faɗi shi ne siffar ƙarshen: lower bound a kan 1/a da ke girma kamar square root na girma, tare da constant 1/π da gyara mai ɓacewa. Sikelin square root na girma yana kama da girma na halitta ga geometry na manyan girma, amma wannan lura ce tawa game da siffar furucin, kuma iƙirarin ba su gabatar da shi a matsayin hanya ba.

Hoton Mellin #

Wani ɓangare ɗaya na kayan aiki ya bayyana a cikin takardar, kuma shi ne ya fi bayyana a fili me ya sa radial Fourier analysis ke da sauƙin sarrafawa a nan. Bayan Mellin transform, radial Fourier transform yana nuna Mellin variable a madubi (reflection). Wannan bayani ne a taƙaice game da yadda wani transform ke aiki. Fourier transform na radial function, wanda yawanci integral operator ne mai wahalar tunani kai tsaye, yana zama reflection a cikin Mellin variable. Reflections suna cikin mafi sauƙin operators da ake da su.

Wannan sashe ɗaya ya rubuta wani sharaɗin analytic a ɗaya ɓangaren. Schwartz decay na g yana ba da saurin decay na Φg yayin da v → +∞. A nan Φg shi ne abin da aka samu a nazarin Mellin, kuma v shi ne variable ɗinsa. Haɗin yana da ilimi: halin reflection yana kula da tsari, kuma Schwartz decay yana kula da sarrafawa a infinity. Hujja a wannan salo tana bukatar duka biyun, domin tsari ba tare da decay ba yana barin integrals da ƙila ba za su kusanta ba, kuma decay ba tare da tsari ba ba ya barin komai na lissafawa.

Takardar ta kuma lura cewa Sd shi ne fadin unit sphere, wanda ke shiga a matsayin normalising factor lokacin da ake canza radial integrals tsakanin sphere da layi. Wannan batu ne na ma'ana, kuma irin lissafin ne da ke tantance ko constants a cikin iyakar ƙarshe za su fito daidai.

Ina so in bayyana a fili mene ne waɗannan gutsure. Ba su ne hujjar ba. Iƙirarin suna ba da bayanai, ba derivations ba, kuma bai kamata wani mai karatu ya sake gina cikakkiyar hujjar daga gare su ba. Abin da suke nunawa shi ne nazarin ya haɗa ragewa ta symmetry, sharaɗi a asali, ƙididdigar nauyi ta adadi, da transform da aikinsa ke sauƙaƙa bayan canza variables. Wannan haɗin ya zama ruwan dare a matsalolin extremal na Fourier analysis, wanda ke sa ainihin daidaiton sakamakon ƙarshe ya fi cancantar a lura da shi, ba ƙasa ba. Kayan aiki masu kama da na yau da kullum sun isa don kaiwa ga amsa mai kaifi.

Sauran tarin #

Babin sphere packing ɓangare ɗaya ne kawai na takardar, kuma sauran sakamakon sun cancanci bayani na adalci. An bayyana kowanne a nan daidai kamar yadda iƙirarin suka ba da shi.

A ka'idar ƙungiyoyi (group theory), an gina wata ƙungiya bayyananniya da ba sofic ba, wadda ta amsa tsohuwar tambayar ko kowace ƙungiya mai iya ƙidaya sofic ce. Hujjar ta haɗa ayyukan Kun da Kun–Thom da wata hujjar combinatorial ta expander-matching, wadda aka cimma ta amfani da binary Leavitt algebra da ƙungiyar V ta Thompson. Kalmar “bayyananniya” tana da nauyi a nan: sakamakon gini ne ba hujjar wanzuwa ba.

A operator algebras, an gina ƙungiyoyi marasa iyaka waɗanda ba su da isomorphism tsakanin kowane biyu, masu property (T), kuma masu group von Neumann algebra ɗaya. Wannan ya ƙaryata hasashen Connes kuma ya amsa wata tambaya mai alaƙa ta finite-to-one ta Popa. Tambayoyi biyu sanannu sun faɗi da gini ɗaya.

A sarƙaƙiyar lissafi (arithmetic complexity), takardar ta ba da lower bounds ga permanent. Division-free circuits suna bukatar Ω(n² log log n) gates, yayin da formulas ke bukatar Ω(n⁴ / log n) leaves. Waɗannan iyakoki biyu ne ga samfuran lissafi biyu, kuma takardar ta bayyana su gefe da gefe.

A quantum information, an tabbatar da exponential parallel repetition ga kowane wasan entangled na 'yan wasa biyu mai iyaka. Tushen ya ce wannan yana faɗaɗa ƙa'idar repetition ta gargajiya fiye da rukunan musamman na wasannin quantum da aka yi nazari a baya. Quantifier ɗin ya sake yin fice: kowane wasan entangled na 'yan wasa biyu mai iyaka, ba tare da takaitawa ga wani rukuni na musamman ba.

A hardness of approximation, ragewa kai tsaye daga 3SAT tana ba da wahala ta n^(1/400)-factor ga Euclidean closest vector problem, tare da sakamako masu alaƙa ga binary decoding da sauran lattice norms. Exponent 1/400 ƙarami ne, kuma na fi son in ruwaito shi kamar yadda aka rubuta maimakon in ƙawata shi. Iƙirarin sun kira ragewar kai tsaye kuma sun haɗa ta da sakamako ga binary decoding da sauran norms.

A convex geometry, an tabbatar da kaifaffen volume upper bound (n + 1)^n / n! a kowane girma ga convex bodies waɗanda barycentre ɗinsu shi ne kaɗai interior lattice point ɗinsu. Kaifi da gamewa a dukan girma duka ɓangare ne na iƙirarin.

A Ramsey theory, sabon lower bound na superexponential ya nuna cewa Rk(3) yana girma kamar k^Θ(k). Kuma a extremal graph theory, gine-ginen bipartite graph daban-daban sun ƙaryata hasashe biyu: hasashen compactness na Erdős da Simonovits da kuma wani hasashen degeneracy na Erdős.

Karanta tarin gaba ɗaya #

Zai yi sauƙi a ɗauki wannan jerin kamar kabad ɗin kofuna, don haka yana da kyau a faɗi abin da za a iya da wanda ba za a iya yankewa daga gare shi ba.

Abin da za a iya faɗi shi ne takardar ta ruwaito sakamako a aƙalla fannoni takwas, cewa an bayyana da yawa daga cikinsu a matsayin masu amsa ko ƙaryata hasashe sanannu, kuma cewa babin sphere packing ya zo da lower bound mai dacewa da ke sa sakamakonsa ya zama na ƙarshe a cikin tsarinsa. Hasashen da abin ya shafa suna ɗauke da sunayen Connes, Popa, Erdős da Simonovits, kuma Afkhami-Jeddi, Cohn, Hartman, de Laat da Tajdini ne suka yi hasashen saurin sphere packing. Sakamakon da ke warware tambayoyi sanannu suna da sauƙin tantancewa domin an yi tambayar kafin amsar ta wanzu.

Abin da ba za a iya faɗi ba, bisa waɗannan iƙirari kaɗai, shi ne komai game da yadda samfurin ke aiki, ƙoƙari nawa ya bukata, yadda aka tabbatar da abin da ya fitar, ko yadda yake kwatantuwa da ƙoƙarin ɗan adam. Tushen ya ce wani samfurin OpenAI na cikin gida ne ya samu sakamakon, kuma iƙirarin sun tsaya a nan. Mai karatu da ke son auna muhimmancin tarin a matsayin shaida game da lissafin na'ura yana bukatar bayanan da iƙirarin ba su ƙunsa ba. Zan ƙi jarabar cike wannan gibi da labari mai kama da gaskiya.

Duk da haka akwai matsayin da ya cancanci a ɗauka. Sakamakon sun bambanta a dabara: ƙungiyar da ba sofic ba tana amfani da binary Leavitt algebra da ƙungiyar V ta Thompson, sakamakon sphere packing yana amfani da Fourier analysis da Mellin transforms, kuma wahalar closest vector tana amfani da ragewa daga 3SAT. Tarin da ya shafi irin wannan faɗin ƙasa ta fasaha ba sakamakon dabara ɗaya ba ne da aka yi amfani da ita akai-akai. Duk abin da ya samar da waɗannan sakamako yana aiki ne a cikin yarukan lissafi da dama, kuma iƙirarin sun goyi bayan aƙalla haka.

Abin da Wannan ke Nufi ga Kowane Fanni #

Ainihin tantance saurin raguwar Cohn-Elkies a manyan girma da sakamakon lissafi da ke tare da shi suna shafar fannonin lissafi na ka'ida da na amfani da dama.

Lissafi zalla da discrete geometry #

Ga masana lissafi da ke aiki a geometry na manyan girma da harmonic analysis, tantance ainihin saurin raguwar Cohn-Elkies yana canza yanayin bincike. Saboda lower bound mai dacewa ya tabbatar da cewa babu auxiliary function a cikin $\mathcal{A}_d$ da zai iya fin sabon exponent, masu bincike za su iya daina neman radial test functions mafi kyau a cikin tsarin linear programming na gargajiya. Ci gaba zuwa sphere packings masu yawa ko universal bounds masu matsatsi yanzu dole ne ya bincika dabarun non-linear programming, semidefinite hierarchies na mataki mafi girma, ko gine-ginen geometry da suka bambanta gaba ɗaya.

Cryptography da tsaro na lattice #

Lattice-based cryptography, wadda ke zama ginshiƙin ma'aunan post-quantum kamar ML-KEM da ML-DSA, ta dogara sosai a kan wahalar da ake hasashe ta nemo mafi gajeru ko mafi kusa vectors a cikin Euclidean lattices na manyan girma. Ragewa kai tsaye daga 3SAT da ke tabbatar da wahala ta $n^{1/400}$-factor ga Euclidean Closest Vector Problem (CVP), tare da rufin exponential masu matsatsi a kan sphere packings da spherical codes, yana ƙarfafa tushen ka'ida na lattice reductions daga worst-case zuwa average-case ba tare da raunana ainihin security parameters ba.

Tabbatar da theorem ta atomatik da foundation models #

Ga ƙungiyoyin bincike da ke haɓaka reasoning systems da automated theorem provers, faɗi da zurfin fasaha na tarin suna ba da ma'auni mai ban mamaki. Maimakon samar da kwaikwayon hujjoji da aka sani, samfurin na cikin gida ya tunkari matsaloli a buɗe a group theory (gina ƙungiya bayyananniya da ba sofic ba ta hanyar ƙungiyar V ta Thompson), operator algebras (ƙaryata hasashen Connes), da arithmetic complexity (lower bounds na permanent). Yana nuna cewa neural architectures za su iya ratsa zurfin Fourier analysis da combinatorial matching, matuƙar tabbatarwa da duba hujja sun kasance masu tsauri.

Kammalawa #

Tantance ainihin saurin raguwar linear program na Cohn-Elkies don sphere packing ya rufe wani babban babi a geometric analysis. Ta hanyar tabbatar da hasashen 2020 na Afkhami-Jeddi, Cohn, Hartman, de Laat da Tajdini da kuma kafa ingantawa ta farko ga babban exponent na sphere packing tun 1978, aikin ya kafa tushen lissafi mai ƙarfi. Tare da lower bound mai dacewa da ke tabbatar da cewa babu auxiliary function na Cohn-Elkies da zai iya ba da ƙarin ribar exponential, theorem ɗin ya warware ƙarfin asymptotic na linear program ɗin kuma ya karkata makomar geometry na manyan girma zuwa sabbin sararin analytic gaba ɗaya.

Tambayoyin da Ake Yawan Yi #

Mene ne muhimmancin iyakar Kabatianskii–Levenshtein?

An kafa ta a 1978, iyakar Kabatianskii–Levenshtein ta ba da asymptotic upper bound exponent na 0.59905576... a kan yawan sphere packing a manyan girma. Fiye da shekaru arba'in, gyare-gyaren da suka biyo baya sun inganta algebraic factors na ƙananan mataki kaɗai, suna barin babban saurin exponential ba a taɓa ba har zuwa wannan sakamako.

Me ya sa lower bound mai dacewa ke da muhimmanci haka?

Upper bound shi kaɗai yana nuna abin da linear program ɗin ke cimmawa, amma lower bound mai dacewa yana tabbatar da cewa babu zaɓin auxiliary function f a cikin rukunin da Cohn-Elkies suka yarda da shi A(d) da zai iya ba da exponent mafi ƙanƙanta. Wannan yana kafa cikakken rufi a kan tsarin linear programming kansa.

Ta yaya matsalar Fourier sign-uncertainty ke da alaƙa da sphere packing?

Cohn da Gonçalves sun tabbatar da cewa matsalar cikawa ta Fourier sign-uncertainty (inda g_hat = -g) tana da haɗi na kusa da iyakokin sphere packing. Ta hanyar rotational averaging da reflections na Mellin transform, mafitar asymptotic ga shirin Cohn-Elkies tana warware matsalar Fourier sign-uncertainty kai tsaye.

Shin wannan sakamako yana raunana lattice-based cryptography?

A'a. Ko da yake theorem ɗin yana ƙara kaifin upper bounds kan yadda ƙwallaye za su iya cunkushewa a manyan girma kuma yana tabbatar da wahala ta $n^{1/400}$-factor ga Closest Vector Problem, ba ya ba da algorithms na lattice reduction a polynomial time. Lattice cryptosystems na aiki suna nan lafiya daga sanannun hare-haren quantum da na gargajiya.

Manazarta #

Nima Afkhami-Jeddi et al., (2020). Sphere packings na manyan girma da modular bootstrap ⧉. Journal of High Energy Physics.
Henry Cohn and Noam Elkies, (2003). Sabbin upper bounds a kan sphere packings I ⧉. Annals of Mathematics.
Henry Cohn and Felipe Gonçalves, (2019). Ƙa'idar uncertainty mafi kyau a Fourier analysis ⧉. PNAS.
Henry Cohn and Yufei Zhao, (2014). Iyakokin sphere packing ta hanyar spherical codes ⧉. Duke Mathematical Journal.
G. A. Kabatianskii and V. I. Levenshtein, (1978). Iyakoki ga packings a kan sphere da cikin sarari ⧉. Problems of Information Transmission.
Maryna S. Viazovska, (2017). Matsalar sphere packing a girma na 8 ⧉. Annals of Mathematics.

Bita ta ƙarshe 2026-10-05.

Bita ta ƙarshe 2026-10-27.

Sake buga wannan labari

Samfurin OpenAI na cikin gida ya tantance saurin raguwar Cohn-Elkies — Sebastien Rousseau

Samfurin OpenAI na cikin gida ya tantance ainihin saurin raguwar shirin Cohn-Elkies na sphere packing: ingantawar exponent ta farko tun 1978, da lower bound mai dacewa.

An lasisin wannan labari a karkashin Creative Commons Attribution 4.0 International. Sake bugawa na bukatar nuna asalin URL na asali.

Samfurin OpenAI na cikin gida ya tantance saurin raguwar Cohn-Elkies — Sebastien Rousseau

Samfurin OpenAI na cikin gida ya tantance ainihin saurin raguwar shirin Cohn-Elkies na sphere packing: ingantawar exponent ta farko tun 1978, da lower bound mai dacewa.

Originally published at https://sebastienrousseau.com/ha/2026-10-05-samfurin-openai-cikin-gida-tantance-saurin/ by Sebastien Rousseau.
Licensed under CC-BY-4.0.

SEBASTIEN ROUSSEAU FOUNDER · ENGINEER