1.1 Algorithms in algebraic number theory| Hendrik Lenstra, Universiteit Leiden
heel erg voor de introductie en ook dankzij de organisatoren voor me invijten om dit shortcourse op algoritmes in algebraische nummertheorie te houden. Laten we beginnen met wat logistische noten. Eerst zijn er lecturenoten, including exercises and it was a moment ago still a stack of them sitting up here, but they are also digitally available or at least they should be. These notes were written by, let me write down his name, Dan van Gent, who is my TA, he's a graduate student at Leiden. Dan, en als je welke imperfecties in de noten ziet, voel je ervaring om te communiceren met Dan. Dan, misschien moet je opnemen en zorgen dat mensen weten wie je bent. Ik heb dan ook aan Dan gehaald om me te helpen in een andere manier. Ik krijg het heel doodig, dus je moet zeker voelen om mij te interrompen of er iets is ongelooflijk is, maar het kan gebeuren dat ik je vraag niet vermoedt, zodat je dan kan horen zodat hij je vraag aan mij kan communiceren en ik kan mijn best opnemen om de vraag te vragen, misschien weer met Dan's help natuurlijk. De laatste jaar waren de coronamezen nog steeds in plaats, maar ik was nog steeds opnieuw inviteerd om een preparatiekurs op de achtergrond voor mijn kurs te kopen, en dat is iets dat ik echt op deze kans vond. Dus ik heb 4 of 5 keer een auxiliermateriaal dat zou behoorlijk zijn om deze presente kurs te weten, en deze materiaal is ook in de lecturenode geïnteresseerd, maar ik ben gewoon geïnteresseerd hoe veel van je hebt dit kurs vorig jaar aangepakt. Oké, goed. Dus dat is een fijn nummer. En de aarders kunnen uiteindelijk de kurs opnemen, maar wat ik zou willen beginnen met vandaag is een brief summary van wat ik lastig jaar deed, zodat je niet verloopt, als je dat materiaal niet volgt. Je kunt zien dat de titel van de lecturenode is een beetje langer, het is polynomial-time algorithms in algebraische nummertheorie, maar dit subject is zo groot dat ik voelde dat ik had om mezelf te limiten, en als je het polynomial-time algorithms aanbiedt, dan is het gewoon de juiste kwaliteit van materiaal voor tekening voor een hele week over dit.  En laat me gewoon te remind je van de laatste jaar van een van de theorems die ik gevoelde door de manier van motivatie voor deze kurs, en dat is de volgende, en ik zal de woorden van deze theorem misschien aansluiten, dus dit is over de existentie van algorithms en dit is een polynomial-time algoritme. En wat doet het? Nou, het compuutt, het testt gewoon een multiplicatieve kwaliteit tussen de rationale nummers, dus de input naar deze algoritme is een sequence van een soort lengte, T, en dat sequence is van rationale nummers, die ik call A1 door AT, en die zijn non-zero rationale nummers, dus Q star, dat is de multiplicatieve groep van rationale nummers, en de algoritme zegt ook als input een sequence van dezelfde lengte, een consistie van interges, en wat de algoritme doet, is eigenlijk heel simpel, het is yes of no, het decide whether the corresponding multiplicative relation is satisfied, whether the product of over i is 1 to T, from A i to the power n i is equal to 1, en in particular, je kunt dit ook gebruiken om te testen of twee soort expressions zijn gelijk, simpel om een expressie te divideren door de andere, dus dit ziet zondergelijk simpel, maar het is ook simpel genoeg, zodat als je niet weet al wat in praktijk maakt iets in een polynomial-time algoritme, dat je het uiteindelijk van dit exemplaar hebt. Dus laat me uitleggen wat al deze woorden betekenen, er is, ik denk dat je weet wat dat betekent, en dat is niet een abstract existentieproef, soms typologisch analisering van de spas van algoritmes, dit is perfect constructief en dat zal echt zijn voor elke algoritme dat ik de existentie van betekent, de proef zal altijd explicitly of implicitelijk vertellen wat de algoritme is.  polynomial-time, dat betekent dat de tijd is gebouwd door een constant tijd, een constant voordeur van wat mensen proeven de lengte van de ingang, en de lengte van de ingang, dat betekent natuurlijk op de manier waar de ingang is presenteerd, wel, dit t dat je ook wel kan representeren in unie, omdat de lengte van de ingang zeker gaat worden, at least t, de a's, de ai, je specifieert ze met nummerator en denominator, waar je bijvoorbeeld op basis schrijft, dus de lengte van zo'n nummerator zal essentieel zijn, het algoritme, en dan in de aandacht natuurlijk, je hebt ook een aandacht, een additie, en in dezelfde manier, deze ingang zijn representeren, en dan start de algoritme werken en in tijd geen meer, dan, wel, essentieel, de aandacht van de algoritmes, de aansluiten die je moet proberen, van alle deze nummers geïnvolgd, het decideer of of niet deze relatie is gevoeligd en ik heb ook een proef van dit lastig jaar en wat is misschien meer belangrijk dan de proef is hoe niet te proeven het en laat me gewoon om dit uit te sketchen, assume en dat is echt zonder los van generatie, dat al mijn ai zijn eigenlijk ingang, maar nog niet 0, gelijk kan je een ai verplaatsen door een nummerator en een denominator en dubbel de nummer t, dus let's gewoon assume dat de ai's zijn ingang en dan wat je kunt doen in deze expressie is dat je de negatieve exponentie aan de andere kant gaat, zodat je kunt assume dat alle n's, de exponentie en i zijn positief, laten we zeggen, strikt positief en dan heb je gewoon twee zo'n expressie en je kunt zeggen, wel, je speelt ze gewoon en bedrijf of ze een beetje by beetje zijn en dat is iets dat niet het polynomial tijd is, want zelfs computeren een zo'n nummer zoals 13 tot de grond een groot nummer, de nummer van digiten zal beproporten tot dat nummer zelf en niet tot het logaritam, dus dat zal gewoon te veel tijd nemen en dan kun je proberen om wat van de standaard devices dat mensen gebruiken in zo'n circumstantie, bijvoorbeeld kun je zeggen dat je testen dat een kwaliteitmodul, een bunch van auxilie nummers is en wel, je kunt denken over het en je zal ontdekken dat het nog niet snel is genoeg, een andere manier is gebruiken transcendentale nummertheorie en gebruiken theorems van bakeltheorie, zeggen dat als twee zo'n expressie zijn verschillende dan ze eigenlijk hebben een grotere verschil, zodat je kan misschien doen deze computering in alleen limiterende accuële en ik heb al de computeren daar veel jaren geleden en ik geloof dat ik bedacht dat dat had een goede kans om te werken als T is fix, maar dan als de nummer van nummers gaat, dan stopt het te zijn polynomiale tijd.  Er is een tweede manier waarin een niet proeft deze theorem en dat is om alle AI in naar prime nummers en dan wat je doet is dat je gewoon bedacht dat deze kwaliteit wel een part kan zijn van de checken dat de signaal is geweldig om simpelijks de prime factorisaties van deze nummers te compareren en dan de dependentie op de exponentie is nu inderdaad wel een bepaalde model om er gewoon wat arithmetic met de exponentie te doen, maar je niet opnemen deze grote nummers, maar nu is de probleem echt zitten in de AI zelf, omdat prime factorisatie is een probleem waarin geen polynomiale tijd algoritme wordt nog niet inventeerd. In de toekomst natuurlijk als jullie hard genoeg werken, kan dat veranderen. Dus de reale manier waarin een theorem proeft is, zoals met zoveel dingen, door terug naar Euclid, vorige week in mijn lectie heb ik discussieerd met meerdere subjecten die terug naar Euclid gaan en zo heeft Joe Silverman, veel van jullie moeten het boek Spacen, ik denk dat het is genoeg, is dat true, door Jordan Ellenberg en als je ook het open hebt je kunt zien dat het titel van de eerste chapter is ik vote voor Euclid. Dus laten we vote voor Euclid en als je naar Euclid gaat, als je naar Euclid kijkt naar Euclid's nummertheorie dan zie je dat zelfs hij ingebouwt de prime nummers en hij bedrijft een paar van zijn basisproporten en in feite de Merzene primes van vorige week waren ze ook in zijn werk maar er is één ding die conspicuus in Euclid is en dat is de uniekheid van prime factorisatie. Er is de fameuse theorem over er zijn infinitief veel primes en sommige mensen denken dat Euclid dit proefde als je alleen finitief veel primes hebt en dat je ze allemaal opgemaakt hebt en je er een opgemaakt hebt. Nou dat is niet wat Euclid deed. Euclid heeft nooit meer dan drie nummers opgemaakt omdat een nummer is in lengte en de product van twee nummers is een gebouw en de product van drie nummers is een volume en product van meer nummers was gewoon niet gebeurd in Euclid's vocabulaar en wat hij did doen voor de proef van de existentie van infinitief veel primes is dat hij niet de product van alle primes opgemaakt heeft hij neemt de meest gewone multiple.  Dat is iets dat hij veel deed en in feite notions zoals gcd's, de meest gewone multiples primairiteit zijn veel meer belangrijk in de theorie dat Euclid opgemaakt is dan de prime nummers zijn. Misschien was hij wel ervaring van prime factorisatie als geen polynomial tijd. Misschien wist hij dat al, dus dat zijn futielse contributies aan het subject kunnen voelen. 