Jakten på fyrdimensionella tripletter av iso- spektrala, icke-isometriska platta torusar The search for four-dimensional triplets of isospectral, non- isometric flat tori Kandidatarbete inom civilingenjörsutbildningen vid Chalmers tekniska högskola Madicken Astorsdotter Filippa Hultin William Karlsson Institutionen för Matematiska vetenskaper CHALMERS TEKNISKA HÖGSKOLA GÖTEBORGS UNIVERSITET Göteborg, Sverige 2024 Jakten på fyrdimensionella tripletter av isospektrala, icke- isometriska platta torusar Kandidatarbete i matematik inom civilingenjörsprogrammet Teknisk matematik vid Chalmers Madicken Astorsdotter Filippa Hultin William Karlsson Handledare: Julie Rowlett Matematiska vetenskaper, Chalmers tekniska högskola Gustav Mårdby Matematiska vetenskaper, Chalmers tekniska högskola Felix Rydell Institutionen för matematik, Kungliga tekniska högskolan Institutionen för Matematiska vetenskaper CHALMERS TEKNISKA HÖGSKOLA GÖTEBORGS UNIVERSITET Göteborg, Sverige 2024 Förord Inledningsvis vill vi tacka våra handledare Julie Rowlett, Gustav Mårdby och Felix Rydell för deras ovärdeliga stöd genom projektet. De har genom projektets alla faser varit mycket engagerade och intresserade av vår utveckling. Deras tålamod och vägledning har varit avgörande för vårt angripande av den komplexa natur som projektets outforskade matematiska mark innebär. Stort, innerligt tack! Vi vill särskilt tacka Julie för hennes initiativtagande till projektet och hennes kontinuerliga en- gagemang genom alla faser. Tack vare Gustavs pedagogiska förklaringar och specialkonstruerade uppgifter har vår förståelse ständigt fördjupats. Slutligen, tack till Felix för hans innovativa idéer och matematiska synvinklar. Vi är väldigt tacksamma för det engagemang och den tid de avvarat för att vägleda oss. En tabell nedan tilldelar varje del till en specifik huvudförfattare, men alla författare har gjort ändringar i hela rapporten. Dessutom har vi fört en loggbok över enskilda prestationer och en tidslogg. Avsnitt och deras författare: Populär vetenskaplig presenta- tion William Abstract och Sammanfattning Madicken 1. Inledning William och Filippa 1.1 Problemformulering William 1.2 Syfte William 1.3 Rapportens uppbyggnad Filippa 2. Den platta torusen Filippa 2.1 Platta torusars olika definitioner Madicken 2.2 Samma form och samma spektrum - isometri och isospektralitet Filippa 2.3 En tredje representation med hjälp av kvadratiska former Madicken 2.4 Tidigare forskning Madicken 3. Teoretisk bakgrund till algorit- men William 3.1 Gruppteori Madicken 3.2 Linjära koder Madicken 3.3 RREF-matriser Filippa 3.4 Antal kodord i en linjär kod William 3.5 Tecknad permutation William 3.6 Linjära koders viktfördelning William 3.7 Omvandling från linjära koder till rutnät William 4. Metod Madicken 4.1 Steg i algoritmen Madicken 4.2 Avgränsningar William 5. Resultat 5.1 Antal linjära koder givet n och q William och Filippa 5.2 Antal ekvivalensklasser för vissa n och q William 6. Diskussion William Bilder och deras skapare: Figur 2 och 5 Filippa Figur 6 och 7 William Populärvetenskaplig presentation Är det möjligt att höra formen av en trumma? Denna fråga populariserades under 60-talet då Mark Kac publicerade en artikel vid samma namn. Flera matematiker har sedan dess, i en slags kapplöpning, försökt lösa problemet för olika typer av trummor. En av de betraktade trummorna är den så kallade platta torusen, som kan liknas vid ett papper som rullats ihop till en cylinder och sedan vikts runt till en ring. Till utseendet jämförs ofta den platta torusen med en munk eller en badring. I själva verket är definitionen av en platt torus naturligtvis betydligt mer komplex än dessa förenklade visualiseringar. Dessutom fungerar trummorna, med deras ljud och form, endast som en musikanalogi för ett matematiskt mycket djupare problem. Att två trummor har samma ljud är en analogi för så kallad isospektralitet mellan platta torusar. På samma sätt är två trummor med samma form en analogi för att två platta torusar är isometriska. Figur 1: Visualisering av en tvådimensionell platt torus. Bilden är hämtad från ett projekt kallat Hevea project [1]. År 1964 hittade John Milnor ett exempel på två 16-dimensionella platta torusar som producerar samma ljud trots att de har helt olika form. Efter den första upptäckten har liknande par hittats i lägre dimensioner, varav det senast funna paret är i fyra dimensioner. Upptäckterna leder oss till problemformuleringen för arbetet. Ännu finns inte något exempel på en triplett av fyrdimensionella platta torusar som uppfyller dessa villkor. Därför är huvudfrågan i arbetet om det är möjligt att, med hjälp av en algoritm, hitta en sådan triplett. En algoritm är en samling instruktioner som i detta fall talar om för datorn vad som ska utföras och i vilken ordning. För att förstå funktionen av en algoritm kan den liknas vid ett bakrecept som beskriver i vilken ordning och på vilket sätt ingredienser ska användas. Utöver att hitta tripletter, kan denna algoritm även ge andra relevanta resultat som ej nödvändigtvis är kopplade till huvudfrågan. Den triplett-sökande algoritmen som skapas under arbetet bygger på programmering av så kallade linjära koder. Detta eftersom varje platt torus kan kopplas till en linjär kod. Linjära koder används i industrin för att bland annat korrigera fel i dataöverföring. Felkorrigeringstekniken säkerställer pålitlig dataöverföring för vanliga datorer såväl som nyteknologiska kvantdatorer. Tekniken är i ständigt behov av utveckling. Detta ihop med den pågående kapplöpningen efter kombinationer av platta torusar med de önskade egenskaperna, gör problemet särskilt intressant. Forskningen från arbetet har potential att dels bidra med ny kunskap, och dels möjliggöra en utökning av sökningen från tripletter till exempelvis kvartetter i fyra dimensioner. Sökningen kan även utökas till högre dimensioner. Dessutom är förhoppningen att algoritmen kan vara till nytta inom industrin. Sökningen efter tripletter av platta torusar med samma ljud och olika form görs inom ett mindre, mer lätthanterligt urval. De platta torusarna kvalificerar in i urvalet baserat på om de följer ett särskilt villkor eller ej. Slutsatsen från sökningsresultatet är att urvalet inte innehåller någon sådan triplett. För att en slutsats ska kunna dras kring om sådana tripletter existerar i fyra dimensioner, behöver urvalet först utökas. Alternativt kan problemet betraktas från andra hållet, nämligen att existensen istället motbevisas. Motbeviset kräver ännu djupare förståelse av matematiken bakom platta torusar, men är ett möjligt framtida projekt. Däremot gav algoritmen användbara resultat som inte är kopplade till frågan i sig. Bland annat bestämmer algoritmen exakt hur många platta torusar som följer urvalets villkor och därmed räknas till urvalet. För att återkoppla till musikana- login kan algoritmen även dela upp trummorna i olika grupper med varsitt ljud och räkna antalet grupper. I viss utsträckning kan algoritmen på liknande sätt dela in trummor i grupper efter form samt räkna antalet grupper. Sammandrag Detta kandidatarbete undersöker om det existerar tripletter av isospektrala icke-isometriska platta torusar i fyra dimensioner. År 1994 visade matematikern Alexander Schiemann att det inte finns några par av platta torusar i tre dimensioner, vilket även gäller för en och två dimensioner. Tidigare har det hittats par av isospektrala icke-isometriska platta torusar i fyra dimensioner, men inga fyrdimensionella tripletter har hittats. Denna rapport undersöker existensen av dessa tripletter med en algoritm programmerad i Python. Vår metod använder radreducerade trappstegsmatriser och linjära koder, som är delgrupper till Zn modulo q, för ett primtal q. Sökningen i fyra dimensioner med algoritmen identifierade varken tripletter eller par. I framtiden är det möjligt att utöka sökningen till högre primtal q eller med sammansatta tal q. Det är även möjligt att utöka algoritmen till högre dimensioner. Abstract This bachelor’s thesis investigates whether there exist triplets of isospectral non-isometric flat tori in four dimensions. In 1994, mathematician Alexander Schiemann showed that there are no pairs of flat tori in three dimensions, which also holds for one and two dimensions. Previously various examples have been found of pairs of isospectral non-isometric flat tori in four dimensions, but no four-dimensional triplets have been found. This report examines the existence of the aforementioned triplets using an algorithm programmed in Python. Our method utilizes matrices in row-reduced echolon form and linear codes, which are subgroups of Zn modulo q, for a prime number q. The search in four dimensions with this algorithm yielded neither triplets nor pairs. In the future, it is possible to extend the search to higher prime values of q or composite numbers q. It is also possible to extend the algorithm to higher dimensions. Innehåll 1 Inledning 1 1.1 Problemformulering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Syfte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.3 Rapportens uppbyggnad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Den platta torusen 2 2.1 Den platta torusens olika representationer . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Samma form och samma spektrum - isometri och isospektralitet . . . . . . . . . . 4 2.3 En tredje representation med kvadratiska former . . . . . . . . . . . . . . . . . . . 6 2.4 Tidigare forskning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3 Teoretisk bakgrund till den triplettsökande algoritmen 7 3.1 Gruppteori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2 Linjära koder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.3 RREF-matriser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.3.1 Omvandling från rutnät till linjära koder . . . . . . . . . . . . . . . . . . . 11 3.3.2 RREF-matriser för sammansatta q . . . . . . . . . . . . . . . . . . . . . . . 11 3.4 Antal kodord i en linjär kod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.5 Tecknad permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.6 Linjära koders viktfördelning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.7 Omvandling från linjära koder till rutnät . . . . . . . . . . . . . . . . . . . . . . . . 15 4 Metod 16 4.1 Steg i algoritmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.2 Avgränsningar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5 Resultat 17 5.1 Antal linjära koder givet n och q . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5.2 Antal ekvivalensklasser för vissa n och q . . . . . . . . . . . . . . . . . . . . . . . . 19 6 Diskussion 20 A Appendix 1 - Notationslista i B Appendix 2 - Teori i B.1 Bézouts identitet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i B.2 Bézouts utökade identitet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i C Appendix 3 - Källkod ii 1 Inledning Är det möjligt att höra formen av en trumma? Denna fråga populariserades år 1966 i en artikel med samma namn, Can one hear the shape of a drum?, skriven av Mark Kac [2]. Sedan dess har problemet lösts för olika slags trummor. En av de betraktade trummorna är den så kallade platta torusen, som förenklat kan liknas vid ett papper som rullats ihop till en cylinder och sedan vikts runt till en ring. Själva definitionen av en platt torus är mer komplex än så och kommer att tas upp i avsnitt 2.1. Dessutom fungerar trummor, med deras ljud och form, endast som en musikanalogi för ett matematiskt djupare problem. Att två trummor har samma ljud är en analogi för isospektralitet mellan platta torusar. Kortfattat handlar isospektralitet om ett objekts spektrum. Analogin är särskilt relevant då det från vågekvationen kan härledas att ett objekts spektrum motsvarar precis de frekvenser som formen kan producera. Två trummor med samma form är en analogi för att två platta torusar är isometriska. Isometri handlar istället om objektets geometriska form. De två begreppen isometri och isospektralitet diskuteras noggrannare i 2.2. Hypotesen bland matematiker var att det för platta torusar gäller att isospektralitet medför iso- metri. Ett motexempel gavs samma år av Milnor som hittade ett par isospektrala, icke-isometriska platta torusar i 16 dimensioner [3, s.542]. Efter att Milnor upptäckt det 16-dimensionella paret blev frågan vilken den lägsta dimensionen är där ett sådant par kan existera. Kneser hittade ett par i 12 dimensioner år 1967 [4, s.31-39], och Kitaoka [5, s.495-497] hittade ett annat exempel i åtta dimensioner år 1977. Tillsammans med Sloane reducerade Conway problemet till sex och sedan fem dimensioner. I dagsläget har par hittats i fyra dimensioner [6, s.372-375]. I de lägre dimensionerna, det vill säga för n = 1, 2, 3, är det bevisat att platta torusars isospektralitet medför isometri mellan de platta torusarna. Problemet är inte begränsat till att endast hitta par av isospektrala, icke-isometriska platta torusar, utan är även relevant för tripletter och större grupperingar. Det är allmänt känt att det finns tripletter i 8 dimensioner och högre, till följd av [7, Sats 6.7]. Intuitivt kan det tolkas som att de skapas av att sätta ihop par från lägre dimensioner. Därför blir en intressant fråga huruvida det existerar tripletter av isospektrala, icke-isometriska platta torusar i fyra dimensioner. 1.1 Problemformulering Arbetets huvudfråga är huruvida det existerar fyrdimensionella tripletter av isospektrala, icke- isometriska platta torusar. Frågan har hämtats direkt från studien The isospectral problem for flat tori from three perspectives av Nilsson, Rowlett och Rydell, där den presenteras som en öppen fråga [7, Kap. 6.2]. Fokus i detta arbete är att försöka bevisa existensen av dessa tripletter. 1.2 Syfte Syftet med arbetet är att genom tillämpning av teori bakom platta torusar skapa och programmera en triplett-sökande algoritm. Huvudmålet med algoritmen är att besvara den centrala frågan och därmed fylla i detta vetenskapliga gap inom området. Ett delsyfte är att med hjälp av algoritmen upptäcka nya samband som svarar på relaterade frågor. I det optimala fallet kan delar av algoritmen komma till användning inom industrin eller i framtida forskning. Syftet är därmed även att främja potentiell utveckling av ämnesrelaterad teknologi samt att möjliggöra fler studier inom området. 1.3 Rapportens uppbyggnad Rapportens första del, kapitel 2, ämnar att ge läsaren den teoretiska bakgrunden som är nöd- vändig för att senare förstå angripandet av huvudproblemet. Där definieras viktiga begrepp som platt torus, isometri, isospektralitet och olika matematiska representationer av den platta torusen. Delkapitel 2.4 ger en överblick av de tidigare upptäckter som gjorts inom forskningsområdet. Den övergripande bilden av den triplettsökande algoritmen som utvecklats ges i kapitel 3, där delkapitlen går igenom all nödvändig teori för att förstå algoritmens olika ingående delar. I kapitel 1 4 används teorin sedan för att ge en sammanfattning av stegen i algoritmen, samt de avgränsningar som gjorts. Slutligen presenteras resultaten från studien i kapitel 5, och de diskuteras sedan i kapitel 6. I appendix A presenteras en notationslista med matematisk notation som används i rapporten. 2 Den platta torusen I detta arbete utforskas fyrdimensionella platta torusar. Med hänsyn till den svårighetsgrad som fyrdimensionella objekt innebär för den visuella förståelsen, börjar vi med att betrakta endimen- sionella och tvådimensionella platta torusar. En platt torus i en dimension kan konceptualiseras som en endimensionell linje med identiska änd- punkter. Om en punkt rör sig längs denna linje och når en av ändpunkterna, kommer den tillbaka genom den andra änden. Detta möjliggör en tvådimensionell visualisering av den endimensionella platta torusen, då de identiska ändarna möts genom att linjen viks runt. Denna vikning kallas för ett endimensionellt objekts inbäddning i två dimensioner, se figur 2. Figur 2: En endimensionell platt torus, samt en inbäddning av denna i två dimensioner. Matematiskt förklaras den platta torusen med hjälp av periodiska randvillkor. Om vi betraktar en funktion f på en endimensionell platt torus T med sidlängd l gäller att f(x) = f(x+ kl), k ∈ Z [7, Kap.1]. I två dimensioner kan en platt torus betraktas som en parallellogram vars motsatta sidor är iden- tiska. En inbäddning av en tvådimensionell platt torus i tre dimensioner kan visualiseras genom att vika ihop parallellogrammen så att två motsatta sidor möts och skapar en ihålig cylinder. Cy- linderns ändar dras sedan runt så att de två andra motsatta sidorna möts. Figur 3 illustrerar en sådan inbäddning av en kvadratisk platt torus i tre dimensioner. Figur 3: Visualisering av en tvådimensionell platt torus som inbäddas i tre dimensioner. Bilden är skapad i ett projekt kallat Hevea project [1]. Ett problem med denna visualisering är att den inte bevarar avstånden mellan objektets punkter. I figur 4 visas en isometrisk inbäddning av en tvådimensionell platt torus i ett tredimensionellt rum, där avstånden mellan punkterna bevarats. 2 På samma sätt som en platt torus i en dimension kan representeras av en linje som viks ihop till en cirkel, och en platt torus i två dimensioner kan representeras av en parallellogram som viks ihop till en form som liknar en badring, kan samma sak göras i högre dimensioner. Nedan presenteras den formella definitionen på en n-dimensionell platt torus, samt dess olika representationer. 2.1 Den platta torusens olika representationer Ofta kan matematiska objekt ses från flera olika synvinklar. Till exempel kan en linje representeras på flera sätt, bland annat genom dess ekvation som en rät linje eller på parameterform. Trots att dessa representationer kan skilja sig åt, beskriver de i grund och botten samma geometriska struktur. På samma sätt kan en platt torus representeras på tre olika sätt: • Rutnät: Att representera den platta torusen som ett rutnät möjliggör vidare analys av denna i en diskret struktur. • Kvotgrupp: Kvotgruppen är den geometriska representationen av en platt torus. Den platta torusen är en slät, kompakt, så kallad Riemannmångfald. Denna skapas genom att ta kvoten av Rn och det tidigare nämnda rutnätet. Mängden Rn är utrustat med platt euklidisk metrik. Den platta torusen ärver metriken, vilket gör att även den beskrivs som platt. • Kvadratisk form: Slutligen kan en platt torus representeras av en kvadratisk form, vilken är en speciell typ av andragradspolynom. Detta möjliggör analys av den platta torusen från ett algebraiskt och talteoretiskt perspektiv. De olika representationerna tillåter undersökning av den platta torusen från olika synvinklar och med olika tillvägagångssätt. Nedan presenteras närmare hur den platta torusen kan representeras med hjälp av rutnät och kvotgrupper. Med dessa perspektiv förklaras sedan vad som menas med isometri och isospektralitet av platta torusar. Sist i avsnittet presenteras även den sista represen- tationen av den platta torusen, med hjälp av kvadratiska former. Ett rutnät är ett vanligt sätt att representera den platta torusen. Begreppet används i abstrakt algebra för att definiera en diskret delgrupp Γ ⊂ Rn, vilken har egenskapen att den består av alla linjärkombinationer över heltalen av en bas (v1, v2, ..., vn) av Rn [8, s.1]. Heltalsplanet Z2 är ett exempel på en sådan struktur och ger en intuitiv bild av att representationen i Rn är just ett rutnät. Generellt uttrycks ett n-dimensionellt rutnät Γ ⊂ Rn av full rang som en mängd Γ := AZn där A är en inverterbar n× n-matris med reella koefficienter [7, Def. 1.1]. Exempel 1. Ett exempel på ett rutnät i en dimension är Γ = 7Z, Γ = {. . . ,−14,−7, 0, 7, 14, . . .}. Med en kvotgrupp kan vi beskriva Riemannmångfalden som är den platta torusen. I denna repre- sentation skrivs den platta torusen som en kvotgrupp av det reella n-dimensionella rummet Rn och rutnätet Γ enligt TΓ := Rn/Γ [7, Kap. 1]. Eftersom rutnätet är en delgrupp av den additiva grup- pen Rn får vi ett kvotrum Rn/Γ genom att identifiera element x, y ∈ Rn som skiljer sig med något element i Γ. Elementen x och y representerar alltså samma element i kvotrummet om x − y ∈ Γ. Informationen om kvotrum har hämtats från en konversation med Rowlett (privat konversation, maj, 2024). Se avsnitt 6, 7, för definitioner av grupp och delgrupp. Att ta kvoten av Rn med rutnätet kan visuellt ses som att rulla ihop Rn med dessa identifieringar. Denna ihoprullning är inte helt korrekt eftersom den platta torusen ärver den euklidiska platta metriken på Rn och förblir just det - platt. Att visualisera detta är inte enkelt. Det är enbart möjligt att göra en isometrisk inbäddning av en (n− 1)-dimensionell platt torus i ett n-dimensionellt rum med ändlig reguljäritet [9, s.7218-7223]. I figur 4 finns ett exempel på en sådan inbäddning och en visualisering av en platt torus. 3 Figur 4: Ett exempel på en inbäddning av en tvådimensionell platt torus i ett tredimesionellt euklidiskt rum [9, s.7218-7223]. Denna bild är likt figur 3 skapad i projektet Hevea project. Exempel 2. Kvotgruppen R/Γ där Γ = 7Z som i exempel 1, kan visualiseras på samma sätt som i figur 2, med l = 7. Här identifierar vi de punkter i Rn som skiljer sig från varandra med något element i Γ. Vi ser alltså de punkter som skiljer sig med 7k, k ∈ Z, som samma punkt. 2.2 Samma form och samma spektrum - isometri och isospektralitet Detta avsnitt redogör för betydelsen av att platta torusar är isometriska, eller enligt musikanalogin att de har samma form. Dessutom diskuteras innebörden av att de är isospektrala, vilket är analogt med att de har samma ljud. Generellt är en isometri en avbildning som vid verkan på ett objekt inte ändrar dess form eller storlek. I isometrier ingår förflyttningar, speglingar och rotationer, samt sammansättningar av dessa [10]. Definition 1. Två objekt är isometriska om det existerar en isometri mellan dem. Om två objekt är isometriska innebär det att det ena objektet går att skapa från det andra, och vice versa, genom att låta en isometri verka på det ena objektet. Visuellt kan vi tänka oss ett tvådimensionellt objekt som kastas runt i ett tredimensionellt rum utan att ändra form eller storlek, se figur 5. Figur 5: Former som är isometriska. Då den platta torusen är en Riemannmångfald med en speciell typ av metrik, är en isometri på denna inte samma sak som en isometri på ett objekt i det euklidiska rummet. Ett tillvägagångssätt för att studera isometri mellan platta torusar är att betrakta deras respektive rutnät. Vi börjar med att definiera den ortogonala gruppen On(R), för att sedan betrakta de platta torusarnas isometri 4 i deras representation som rutnät. Här ges endast definitionen för två rutnät i samma dimension, men det är även möjligt att jämföra två rutnät med olika dimension på ett liknande sätt. Definition 2. Mängden On(R) kallas den ortogonala gruppen och består av alla inverterbara n×n- matriser med reella koefficienter sådana att inversen och transponatet av matrisen är identiska, [7, Kap. 2.1]. Definition 3. Två rutnät Γ1, Γ2 ⊂ Rn är kongruenta om det existerar en matris D ∈ On(R) så att Γ2 = DΓ1, [7, Def. 2.4]. Enligt [7, Sats 2.5] är rutnäten Γ1, Γ2 ⊂ Rn kongruenta om och endast om de platta torusarna Rn/Γ1 och Rn/Γ2 är isometriska. Det räcker alltså att hitta en ortogonal matris som omvandlar den ena platta torusens rutnät till den andra torusens rutnät för att kunna dra slutsatsen att de är isometriska. Två isometriska objekt är även isospektrala, vilket de kallas om de har samma spektrum. Vid studie av den platta torusen syftas spektrumet till mängden av alla egenvärden, inklusive multiplicitet, för Laplace-operatorn på den platta torusen [7, Def. 2.9]. Om denna mängd av egenvärden är samma för två platta torusar, då är de alltså isospektrala. Nedan presenteras vad som avgör den platta torusens spektrum i en dimension och n dimensioner. Betrakta först en endimensionell platt torus av längd l, se figur 2. Dess egenvärden λ, samt egen- funktioner f , är de som uppfyller ekvationen:  −f ′′(x) = λf(x), f(x+ l) = f(x), f ′(x+ kl) = f ′(x), ∀k ∈ Z. (1) Den endimensionella platta torusens spektrum är mängden av alla λ sådana att det finns en nollskild funktion f som uppfyller ekvation 1, [7, Kap.1]. Observera att Laplaceoperatorn i det endimensionella fallet är en andraderivata. I det mer generella fallet, då vi har en n-dimensionell platt torus som definieras av ett rutnät Γ, ges egenfunktionerna f och egenvärdena λ av lösningarna till följande ekvation:  ∆f(x) = λf(x), f(x+ l) = f(x), ∇f(x+ l) = ∇f(x), ∀l ∈ Γ, x ∈ Rn. (2) Den n-dimensionella platta torusens spektrum är mängden av alla λ sådana att det finns en nollskild funktion f som uppfyller ekvation 2, [7, Kap. 1]. Om två objekt är isometriska är de även isospektrala, men det omvända behöver inte vara sant. Hu- vudproblemet i detta arbete är att söka fyrdimensionella tripletter av isospektrala, icke-isometriska platta torusar. Det är för närvarande okänt om sådana existerar. Liknande frågeställningar för and- ra objekt har tidigare utforskats, bland annat av Gordon, Webb och Wolpert. År 1992 konstruerade de ett exempel på två icke-isometriska områden i R2 där Laplace-operatorn har samma spektrum [11, s.134-138]. 1996 konstruerade Gordon och Webb ytterligare ett exempel på isospektrala, icke- isometriska områden [12, s.46-55], se figur 6. I detta fall gavs objektens egenfunktioner f , samt spektrum av egenvärden λ av lösningarna till Dirichletproblemet, ∆f = −λf, (3) f |δD = 0, (4) 5 där δD är objektens rand. Figur 6: Former som är isospektrala men inte isometriska. [13] Att bestämma ett objekts spektrum utifrån dess geometriska form är ett välkänt problem, som exemplifieras av Laplaces egenvärdesproblem. Se ekvation 2 och 3. I de flesta fall utgör den mate- matiska beräkningen av ett objekts spektrum en betydande utmaning, där det ofta är omöjligt att härleda en lösning enbart genom analytiska metoder. Den platta torusen är däremot ett undantag. Det fascinerande med den platta torusen är att vi i någon mån analytiskt kan härleda de exakta egenvärdena till den [7]. 2.3 En tredje representation med kvadratiska former Som tidigare nämnts kan platta torusar representeras med hjälp av rutnät och kvotgrupper. Den tredje representationen av en platt torus presenteras i detta kapitel: en kvadratisk form. Definition 4. En kvadratisk form är en polynomfunktion definierad på Rn med en symmetrisk n× n-matris Q så att x ∈ Rn 7→ xTQx. I detta fall är x en kolonnvektor och multiplikationen vanlig matrismultiplikation [7, Kap. 2.3]. Ett exempel med koordinaterna (x, y) i R2 är: (x, y) 7→ ( x y )(1 0 0 1 )( x y ) = x2 + y2. En kvadratisk form är alltså ett polynom som enbart har termer av grad två. Nedan presenteras exempel på kvadratiska former i två och fyra dimensioner. Exempel 3. Ett exempel på en kvadratisk form i två dimensioner är: x2 − 3xy + 2y2. (5) Exempel 4. Ett exempel i fyra dimensioner är: 3x2 + 5y2 + 2z2 + 4w2 + 2xy + 6xz + 8yz. (6) Två kvadratiska former kallas integralekvivalenta om de med två olika baser representerar samma funktion på ett rutnät. I boken The sensual quadratic form presenterar Conway ett sådant exem- pel [14, s.4-5]. Att de är integralekvivalenta innebär även att de motsvarande platta torusarna är isometriska [7, Kap. 2.3]. Problemformuleringen i detta arbete, om det existerar tre fyrdimensio- nella isospektrala, icke-isometriska platta torusar, är ekvivalent med att fråga om det existerar tre positivt definita kvadratiska former i fyra variabler som ger samma värden över heltalen men inte är integralekvivalenta. Nedan definieras vad det innebär för en kvadratisk form att vara positivt definit. 6 Definition 5. En kvadratisk form h(x, y) är positivt definit om h(x, y) ≥ 0 för alla (x, y) ∈ R2 med likhet om och endast om (x, y) = (0, 0). [7, Def. 2.16] En kvadratisk form antar olika värden beroende på vilka tal som sätts in. I det här arbetet söker vi tre positivt definita kvadratiska former i fyra variabler som utan att vara integralekvivalenta antar samma värden över heltalen. Matematikern Alexander Schiemann använde sig av icke-integralekvivalenta kvadratiska former i tre dimensioner för att bevisa att det inte existerar sådana par som antar samma värden då heltal sätts in i dem [15], [16, s.507-517]. Han sökte igenom ett stort antal kvadratiska former som var icke-integralekvivalenta. På detta sätt visade han att det inte existerar två isospektrala, icke-isometriska platta torusar i tre dimensioner. 2.4 Tidigare forskning År 1994 besvarades, som tidigare nämnts, frågan om isospektrala icke-isometriska platta torusar i tre dimensioner. Schiemann bevisade genom en avancerad datoralgoritm att två tredimensionella isospektrala platta torusar också måste vara isometriska [15], [16, s.507-517]. Detta innebär att det inte kan existera par av isospektrala icke-isometriska platta torusar i en, två eller tre dimensioner. Jakten efter par av isospektrala, icke-isometriska platta torusar har pågått i flera årtionden. År 1964 hittades ett sådant par av Milnor i 16 dimensioner [3, s.542]. Efter att Milnor upptäckt paret i 16 dimensioner blev frågan vilken den lägsta dimensionen är för att ett sådant par ska kunna existera. Kneser reducerade 16 dimensioner till 12 [4, 31-39] år 1967 och Kitaoka [5, s.495-497] hittade ett annat exempel i åtta dimensioner år 1977. Tillsammans med Sloane, reducerade Conway problemet till sex och sedan fem dimensioner. Paret i sex dimensioner hittade Sloane med hjälp av linjära koder [17, s.93-96], ett tillvägagångssätt som kommer diskuteras närmre i avsnitt 3.2. Alexander Schiemann som tidigare nämnts, tog fram ett fyrdimensionellt exempel [6, s.372-375]. Han är också skaparen av datoralgoritmen, som motbevisat existensen av par i tre dimensioner. Conway och Sloane lyckades senare även hitta en familj av par i fyra dimensioner [17, s.93-96], [18, s.153-166]. Tabellen nedan visar upptäckterna i kronologisk ordning. Årtal Dimension där par av isospektrala Person ickeisometriska platta torusar upptäckts 1964 16 Milnor 1967 12 Kneser 1977 8 Kitaoka 1986 5 och 6 Conway och Sloane 1990 4 Schiemann 1992 Familj, 4 Conway och Sloane 3 Teoretisk bakgrund till den triplettsökande algoritmen Bakgrundsinformationen är nu tillräcklig för att kunna introducera den triplett-sökande algoritmen. Detta avsnitt hanterar teorin bakom algoritmen, medan nästa avsnitt, vilket motsvarar metoden, handlar om de konkreta stegen i algoritmen. För att lättare följa med i algoritmens olika delar presenteras i figur 7 ett övergripande flödesschema. 7 Figur 7: Flödesschema över teorin bakom algoritmen samt dess olika steg. 8 De ovala delarna i diagrammet motsvarar dels den nödvändiga teorin som lagts fram tidigare, och dels ny teori som bygger upp algoritmen. Rektanglarna utgör metoden och de olika stegen i algoritmen. Genom att följa den röda tråden i figur 7, är målet att slutligen hitta eventuella tripletter av platta torusar med de önskade egenskaperna. 3.1 Gruppteori Nedan presenteras olika definitioner och satser inom gruppteori som är centrala för rapporten. Grupper används vid ett flertal tillfällen i rapporten, bland annat vid användningen av linjära koder 3.2. Nedan följer definitionen av en additiv grupp [19, s.30]. Notera att det finns grupper med andra operationer. Definition 6. En additiv grupp G är en mängd utrustad med en operation + : G ×G → G som uppfyller följande tre axiom: - Identitetselement Det finns ett element 0 i gruppen så att för varje element a i G är a+ 0 = 0 + a = a. - Inverser För varje element a i G finns en additiv invers −a i G så att a+(−a) = (−a)+a = 0. - Associativitet För varje a, b och c i G är (a+ b) + c = a+ (b+ c). Eftersom operationens målmängd är G, innebär detta att gruppen är sluten. Detta betyder att om a och b är element i G är även a+ b ett element i G. Baserat på definitionen av en additiv grupp kan vi nu definiera en additiv delgrupp [19, s. 41]. Vi introducerar även Lagranges sats [19, s. 88], som beskriver samband mellan en grupp och dess delgrupper. Denna sats är mycket användbar vid undersökning av linjära koder. Slutligen ges även definitionen av ordningen av ett element i en additiv grupp [19, s. 78]. Definition 7. En delmängd H till en grupp G är en additiv delgrupp av G om H själv med avseende på operationen + bildar en grupp. Sats 1. Om H är en delgrupp av en ändlig grupp G, då är antalet element i H en delare till antalet element i G. Definition 8. Ordningen av ett element g i en additiv grupp definieras som det minsta positiva heltalet k så att kg = 0, och skrivs som ord(g). Ett steg i algoritmen använder sig av tecknade permutationer som gör det möjligt att dela in matriserna i olika ekvivalensklasser [19, s.54]. För att kunna definiera en ekvivalensklass behöver vi först definiera en ekvivalensrelation [19, s.53]. Definition 9. En relation ∼ på en icke-tom mängd S är en ekvivalensrelation på S om den uppfyller följande tre krav: - Om a ∈ S, då gäller a ∼ a (reflexiv) - Om a, b ∈ S och a ∼ b, då gäller b ∼ a (symmetrisk) - Om a, b, c ∈ S och a ∼ b och b ∼ c , då gäller a ∼ c (transitiv) Definition 10. Låt ∼ vara en ekvivalensrelation på en mängd S och låt s ∈ S. Låt [s] = {x ∈ S : s ∼ x}. Denna delmängd [s] av S är ekvivalensklassen av s, med avseende på ∼. Ekvivalensklasserna bildar en partition av S [19, Sats 9.7] . 3.2 Linjära koder Linjära koder är ett verktyg för att jämföra platta torusars isospektralitet i ett ändligt utrymme, som möjliggör en mer strategisk och omfattande sökning än med andra metoder. Den matema- tiska definitionen av linjära koder baseras på abstrakt algebra och presenteras i [7, Def. 3.8]. Här presenteras en ekvivalent formulering. 9 Definition 11. En linjär kod C med längd n är en samling av kodord, där varje kodord är en sekvens av n element från ringen av heltal modulo q, där q är ett positivt heltal. Dessa kodord utgör en delgrupp av modulen (Z/qZ)n. Exempel 5. Ett exempel på en linjär kod i dimension n = 2, där q = 6 är0 0 2 4 4 2  . En linjär kod kan förstås som en struktur där varje rad är ett kodord. Denna kod är en grupp inom gruppteorin enligt Definition 6. En linjär kod består av olika kodord som uppfyller specifika egenskaper. Varje kodord består av en sekvens av så kallade bokstäver, vilka är de grundläggande byggstenarna för kodorden. Dimensionen n bestämmer längden på alla ord i den linjära koden och q bestämmer vilka värden alla bokstäver kan anta. Den linjära koden, vilken består av kodorden, är en delgrupp till (Z/qZ)n. Alltså kommer till exempel, då q = 6 alla bokstäver anta heltal z ∈ {0, . . . , 5}. Detta innebär att det till exempel istället för 8 kommer att vara bokstaven 2 i den linjära koden, vilket liknar exempel 5 där alla bokstäver är heltal mellan 0 och 5. Till exempel är [2 4] ett kodord som består av bokstäverna 2 och 4. Denna strukturerade uppsättning av kodord ger oss en möjlighet att få fram unika representanter av linjära koder. För att vara en linjär kod behöver kodorden stämma överens med varandra så att den linjära koden uppfyller kraven för att vara en grupp. Varje linjär kod kommer att ha ett identitetselement med längd n där alla bokstäver är 0, i exemplet ovan är alltså identiteselementet [0 0]. Slutenheten syns också då till exempel [2 4]+[2 4] = [4 2] då q = 6 samt [2 4]+[4 2] = [0 0]. Vi ser också att [2 4] och [4 2] är varandras inverser enligt den förra likheten. Associativiteten följer från associativiteten hos heltal. Eftersom de olika kraven uppfylls är den linjära koden också en grupp. 3.3 RREF-matriser En RREF-matris är en viss typ av matris som här är nödvändig för att omvandla ett rutnät till en linjär kod. Nedan ges definitionen av en RREF-matris. Några exempel ges även på omvandlingar från rutnät till linjära koder genom RREF-matriser. I slutet av avsnittet ges en utökning av definitionen från RREF-matriser i (Z/qZ)n där q är ett primtal till att involvera RREF-matriser i (Z/qZ)n där q är ett sammansatt tal. Matriserna vi kallar för RREF-matriser är radreducerade trappstegsmatriser. På engelska säger vi att en matris är på row reduced echelon form, därav förkortningen RREF-matris. Vi betraktar här enbart kvadratiska RREF-matriser med element från ringen (Z/qZ)n då RREF-matrisen är i n dimensioner. Exempelvis då q = 5 är ett matriselement xi ∈ {0, 1, 2, 3, 4}. Vi antar till att börja med att q är ett primtal. Definition 12. En n× n-matris är en RREF-matris om följande håller [20, Kap.2]: 1. Alla rader i matrisen med enbart nollor som element är på den nedersta raden eller de nedersta raderna av matrisen, 2. Pivotelementet är det första nollskilda värdet i varje rad från vänster till höger, om ett sådant finns. Om en rad har ett pivotelement är det till höger om pivotelementen i raderna ovanför. 3. I varje rad som ej enbart innehåller nollor är pivotelementet 1. 4. Varje kolonn som innehåller ett pivotelement har nollor på alla andra platser. Varje n × n-matris går att, genom Gausseliminering, omvandla till en unik RREF-matris. Detta innebär även att vi inte kan omvandla en given RREF-matris till en annan genom radoperationer [20, Kap.2]. Entydigheten kommer vara viktig för att kunna koppla en linjär kod till varje RREF- matris. Som tidigare nämnt kan vi från ett rutnät framställa en RREF-matris, från vilken vi kan framställa en linjär kod. Detta gör vi genom att betrakta rutnätet som en matris, vilken vi radreducerar genom 10 Gausseliminering. Sedan byter vi ut talen i matrisen till deras motsvarande tal i ringen (Z/qZ)n. Vi framställer en linjär kod från RREF-matrisen genom att betrakta raderna i RREF-matrisen som generatorer för den linjära koden. Metoden illustreras med ett exempel: 3.3.1 Omvandling från rutnät till linjära koder Exempel 6. Vi antar här att n = 2, q = 5, alltså att dimensionen är 2 och de värden som är möjliga att antas i RREF-matrisen är {0, 1, 2, 3, 4}. Låt säga att det rutnät vi vill undersöka är Γ := AZ2: Γ = [ 1 5 12 0 ] Z2. Vi vill först transponera A: AT = [ 1 12 5 0 ] . RREF-matrisen får enbart ta värden i (Z/5Z)2. Vi applicerar därmed avbildningen π : Z2 → (Z/5Z)2 som verkar elementvis z → z (mod 5). Eftersom 1 ≡ 1 (mod 5), 12 ≡ 2 (mod 5) och 5 ≡ 0 (mod 5) är den resulterande RREF-matrisen: [ 1 2 0 0 ] . Vi vill nu omvandla RREF-matrisen till en linjär kod. Matrisen har raderna [1, 2] och [0, 0]. Addition av [0, 0] till vilket element som helst skulle ge upphov till elementet självt och [0, 0] ger därmed endast upphov till identitetskoden [0, 0]. Däremot ger [1, 2] upphov till följande element vid addition: [1, 2], [2, 4], [3, 1], [4, 3] och [0, 0]. Den totala linjära koden som RREF-matrisen genererar är därför: [1, 2], [2, 4], [3, 1], [4, 3] och [0, 0]. Raderna i en RREF-matris genererar alltså dess linjära kod. Eftersom RREF-matriser är sinsemel- lan unika innebär det att även deras respektive linjära koder är unika. 3.3.2 RREF-matriser för sammansatta q Klassiskt definieras RREF-matriser för fall då q är ett primtal. Här ges en ytterligare definition för fallet då q är ett sammansatt tal, vilken presenterades under ett möte (Rydell, privat konversation, mars, 2024). Notera att villkor 1 och 2 i Definition 13 är samma som i Definition 12. Definition 13. En RREF-matris där q är ett sammansatt tal är en matris som uppfyller: 1. Alla rader i matrisen med enbart nollor som element är på den nedersta raden eller de nedersta raderna av matrisen. 2. Pivotelementet är det första nollskilda värdet i varje rad från vänster till höger, om ett sådant finns. Om en rad har ett pivotelement är det till höger om pivotelementen i raderna ovanför. 3. Varje pivotelementet p är en äkta delare av q. 4. Låt pivotelementet på en rad av längd n vara på position i. Låt värdena på samma rad på position i + 1 till n bilda en vektor r. Då tillhör q p · r spannet av de vektorer som bildas av de undre raderna då vi av dem bildar vektorer av längd n− i räknat från höger till vänster i varje rad. 5. Ett värde x som i en kolonn är över ett pivotelement p kan enbart anta värden x ∈ {0, 1, 2, ..., p− 1}. 11 Notera att vi i RREF-matriserna för sammansatta q inte kräver att kolonnerna med pivotelement ska vara nollskilda utöver pivotelementet. Dessa RREF-matriser för sammansatta q är unika och ger därmed unika linjära koder för sammansatta q (Rydell, privat konversation, april 2024), vilket visas nedan. Sats 2. Låt q vara ett sammansatt tal. För varje linjär kod C med kodord av längd n, C ∈ (Z/qZ)n, existerar en unik generatormatris som dessutom är en RREF-matris. Bevis. Detta visas med hjälp av induktion på dimension n. Basfall, n = 1: Betrakta en linjär kod C ∈ Z/qZ med kodord av längd 1. Antag att C genereras av en generator- matris G = [x] av storlek 1× 1. Vi vill visa att G kan reduceras till en unik RREF-matris [y] som genererar samma linjära kod C. I detta fall krävs antingen att y delar q eller att y = 0 för att [y] ska vara en RREF-matris enligt definition. Låt y = SGD(x, q). Detta innebär att y delar både x och q. Låt Cy vara koden som genereras av [y]. Då y är en delare till både x och q måste C ⊆ Cy. Då SGD(x, q) = y existerar a, b ∈ Z sådana att ax+ bq = y enligt Bézouts identitet 4, så ax ≡ y (mod q), och Cy ⊆ C. Alltså måste C = Cy. Entydigheten följer från att y = SGD(x, q). Induktionsantagande Antag nu att det för varje linjär kod med kodord av längd n − 1 existerar en unik RREF-matris som genererar denna. Gäller det då att det för varje linjär kod med kodord av längd n existerar en unik RREF-matris som generator? Antag att en linjär kod med kodord av längd n kan genereras av en generatormatris G, vilken vi delar upp enligt följande: G =   v1 v2 ... vn  [ r ][ A ]  . Vektorn v = [v1, v2, ..., vn] är kolonnen längst till vänster. r är den översta raden, förutom v1. Matrisen A är de övriga elementen, vilka kan betraktas som en (n− 1)× (n− 1)-matris längst ned till höger i G. Vi vill först visa att G kan reduceras till en RREF-matris. Vi antar att alla element i G ∈ {0, 1, 2, ..., q − 1}. Låt y = SGD(v1, v2, . . . , vn, q). Om y = 0 är alla element i första kolonnen = 0, och då vi kollar på resterande n − 1 kolonner följer det från induktion att G kan reduceras till en unik RREF-matris. Elementen i den nedersta raden kommer i detta fall genom radreduktion bli = 0. Vi antar därmed att y ̸= 0. Bézouts identitet kan utökas till fler än två variabler 5, och ger i detta fall då SGD(v1, v2, . . . , vn, q) = y att det existerar a1, a2, . . . , an, b ∈ Z sådana att y = a1v1 + a2v2 + · · ·+ anvn + bq ≡ a1v1 + a2v2 + · · ·+ anvn (mod q). Låt gij vara elementet i G på rad i, kolonn j. Betrakta vektorn w som fås genom att summera ai kopior av rad i: w := [a1g11 + a2g12 + · · ·+ ang1n, . . . , a1gn1 + a2gn2 + · · ·+ angnn]. Observera att första elementet i w är y då [g11, ..., g1n] = [v1, ..., vn]. Genom att sätta w över G skapar vi en (n+ 1)× n-matris: 12 [ w ]  v1 v2 ... vn  [ r ][ A ]  . Genom elementära radoperationer kan vi reducera kolonnen längst till vänster så att alla element i den kolonnen blir 0, förutom y. Låt r vara vektorn q y · w. Betrakta den linjära koden som spänns av r och n × (n − 1)-matrisen längst ned till höger. Dessa n + 1 rader genererar en linjär kod med kodord av längd n − 1. Av induktion har vi att det existerar en unik (n − 1) × (n − 1)-RREF-matris som genererar denna. Den nedersta raden kan därmed reduceras så alla element blir = 0, och vi kan plocka bort den så G blir en n× n-matris med (n− 1)× (n− 1)-RREF-matrisen längst ned till höger. Vi kan sedan med hjälp av (n− 1)× (n− 1)-RREF-matrisen reducera den första raden så att även den uppfyller kraven för att G ska bli en RREF-matris. Vi vill nu visa att G kan reduceras till en unik RREF-matris. Antag att det existerar två RREF- matriser, R1 och R2 av dimension n× n som genererar samma linjära kod: R1 =  y1 [ r1 ] v12 ... v1n  [ A1 ]  , R2 =  y2 [ r2 ] v22 ... v2n  [ A2 ]  . Som tidigare kan vi reducera så att v12 , v 1 3 , . . . , v 1 n och v22 , v 2 3 , . . . , v 2 n alla blir 0. Sätter vi första koordinaten till 0 genereras den linjära koden av A1 och A2, vilket av induktion ger att A1 = A2 := A. Dessutom måste y1 = y2 då både y1 och y2 är delare av q. Skulle y1 ̸= y2 skulle mängderna av elementen i de resulterande linjära kodernas element längst till vänster vara olika. Det enda som kan skilja sig är nu r1 och r2. Vi vet att R1 och R2 ger samma linjära kod, vilket innebär att det existerar vektorer z1, z2 sådana att r1 + z1A = r2 + z2A. Detta ger att r1 − r2 = (z1−z2)A. r1 och r2 skiljer sig alltså med multiplar av A. Reduktionskravet ger därmed att r1 = r2. 3.4 Antal kodord i en linjär kod Antalet element |A| i en mängd A, även kallat kardinaliteten av A inom mängdlära, är enkelt att räkna ut för en linjär kod. Kardinaliteten är lika med antalet kodord i den linjära koden. För att istället räkna ut kardinaliteten från en RREF-matris behöver man ta hänsyn till ordningen av pivotelementen i matrisen, som vi får från Definition 8. Kardinaliteten K ges av, K = ∏ i∈I ord(pi), (7) där I är mängden rader med pivotelement i RREF-matrisen, och pi är pivotelementets värde i rad i. Formeln fastställdes under ett möte (G. Mårdby, F. Rydell, J.Rowlett, privat kommunikation, mars, 2024). Den kommer till användning i det stadie i algoritmen där RREF-matriserna ännu inte har omvandlats till linjära koder. Omvandlingen i sig är en process av hög komplexitet och görs först när det verkligen är nödvändigt. Kardinaliteten hos linjära koder är viktig eftersom de endast kan ha samma viktfördelning om de har samma kardinalitet. Detta blir mer uppenbart i avsnitt 3.6, där viktfördelning förklaras djupare. Där diskuteras även vad som följer av att linjära koder har samma viktfördelning. 13 3.5 Tecknad permutation Tecknade permutationer är specialfall av matriser tillhörande mängden On(R). Från Definition 2 får vi därmed att två rutnät är isometriska om deras respektive linjära koder är tecknade per- mutationer av varandra. För att hitta eventuella tripletter är det därför väsentligt att kontrollera att inga utav koderna är tecknade permutationer av varandra. Den tecknade permutationen av en linjär kod får vi från att matrismultiplicera kodens RREF-matris med en permutationsmatris. En permutationsmatris i detta fall består av en identitetsmatris där kolonnerna har bytt platser på godtyckligt sätt, och ettorna antar värdena ±1 i varje kolonn. Därmed skapas en tecknad per- mutation [21]. På grund av tecken och omordning av kolonner finns det för n = 4 totalt 24 · 4! stycken permutationsmatriser att kontrollera för varje RREF-matris. Däremot blir resultatet av matrismultiplikationen inte alltid en ny RREF-matris, utan måste först gå igenom Gausselimine- ring. Efter Gausselimineringen kan RREF-matriser jämföras med varandra för att se om de är tecknade permutationer av varandra eller ej. Ett resultat av detta är att RREF-matriser av samma kardinalitet kan indelas i olika ekviva- lensklasser, där varje klass innehåller RREF-matriser som är permutationer av varandra. Detta är avgörande för komplexiteten av algoritmen, eftersom det även är känt från Proposition 1 att alla koder i samma klass har samma viktfördelning. Propositionen följer från konstruktionen av viktfördelning i Definition 14. Proposition 1. Viktfördelningen för en linjär kod är oberoende av tecknad permutation. För varje ekvivalensklass räcker det därmed att beräkna viktfördelningen för en enda linjär kod. Det är även viktigt att notera att rutnät kan vara isometriska trots att deras RREF-matriser inte är permutationer av varandra. Permutationer löser endast en liten del av isometri-problemet. En slutlig heltäckande kontroll av icke-isometri görs i slutet av algoritmen under avsnitt 3.7. 3.6 Linjära koders viktfördelning I en konversation via e-post fastställde Rydell (personlig kommunikation, april, 2024) att viktför- delningen för en linjär kod kan definieras på följande sätt. Definition 14. Låt C vara en linjär kod och låt c1, . . . , ck vara dess kodord. Varje bokstav i kodordet, modulo q, tillhör heltalsmängden {−⌊ q−1 2 ⌋, . . . , ⌊ q 2⌋}. Låt |ci| vara vektorn bestående av absolutbeloppet av varje bokstav i ci. Två linjära koder har samma viktfördelning om det finns en bijektion ϕ mellan kodorden så att för varje kodord ci har |ci| och |ϕ(ci)| lika många av varje bokstav i {0, 1, ..., ⌊ q 2⌋}. Exempel 7. För n = 3 och q = 5 har följande två linjära koder, CA =  0 0 0 0 1 3 0 2 1 0 3 4 0 4 2  , CB =  0 0 0 2 1 0 4 2 0 1 3 0 3 4 0  , (8) samma viktfördelning eftersom värdena 3 och 4 i detta fall istället antar värdena −2 respektive −1 enligt definitionen. Denna egenskap mellan linjära koder är avgörande i algoritmen för att kunna hitta tripletter som är isospektrala. Isospektraliteten följer från Proposition 2 [7, Proposition 3.12]. Proposition 2. Låt C1, C2 vara linjära koder modulo q, och låt Li = π−1 q (Ci), i = 1, 2 vara deras motsvarande rutnät. Om C1 och C2 har samma viktfördelning så är L1 och L2 isospektrala. Bevis. För i = 1, 2, låt c (i) 1 , . . . , c (i) m vara listor av kodord definierade enligt Definition 14, med samma viktfördelning. Låt c̃ (i) 1 , . . . , c̃ (i) m vara motsvarande listor av kodord, i vilka bokstäverna antar absolutbeloppet av värdena {−⌊ q−1 2 ⌋, . . . , ⌊ q 2⌋} enligt samma definition. 14 Observera att π−1 q (C(i)) är den disjunkta unionen av c (i) j + qZn. Låt Σj vara den tecknade permu- tationen som tar c̃ (1) j till c̃(2)j , som vi får av Definition 14. Vi skapar en längdbevarande bijektion från c (1) j + qZn till c(2)j + qZn som ges av Σj . Detta är ett tillräckligt villkor eftersom de inversa avbildningarna av kodorden partitionerar π−1 q (C(i)). Σj är en ortogonal permutationsmatris. Där- med är x 7→ Σx längdbevarande och en bijektion mellan π−1 q (c (1) j ) och π−1 q (c (2) j ). Då gäller att L1 och L2 har samma längdspektrum och därmed är de isospektrala [7, Korollarium 2.15]. När algoritmen söker efter tripletter söker den alltså efter tre linjära koder som har samma vikt- fördelning trots att de tillhör olika ekvivalensklasser med avseende på tecknad permutation. På så sätt försäkrar vi oss om att de är isospektrala och att de inte är isometriska genom tecknad permutation. 3.7 Omvandling från linjära koder till rutnät Som sagt är det inte möjligt att helt utesluta isometri mellan linjära koder trots att de har de- lats upp i ekvivalensklasser med avseende på tecknad permutation. Därför behövs en heltäckande isometri-kontroll, vilket genomförs på potentiella tripletter. För att göra den slutliga kontrollen behöver linjära koder först omvandlas tillbaka till rutnät, och för att förtydliga omvandlingen återanvänder vi CA från exempel 7. I omvandlingen används de generativa kodorden i den linjära koden, det vill säga motsvarande RREF-matris R som vi tagit fram i början av algoritmen. RREF-matrisen för CA är, R = 0 1 3 0 0 0 0 0 0  , eftersom elementet [0, 1, 3] genererar alla andra element i CA. Rutnätet spänns upp av de nollskilda kolonnerna av RT , det vill säga [0, 1, 3]T i detta fall. Lägg även i rutnätet till kolonner av qI som motsvarar raderna i RT utan pivotelement. Den första och sista raden av RT har inget pivotelement i vårt fall. Därför får vi rutnätet, L = 0 5 0 1 0 0 3 0 5 Z3. Omvandlingen baseras på [7, Korollarium 3.10], men har förenklats av Mårdby och Rydell (privat konversation, maj, 2024). Den är korrekt för såväl primtal som sammansatta q. Den slutliga isometri-kontrollen mellan de framställda rutnäten i en potentiell triplett, går ut på att tillämpa följande sats [7, Korollarium 3.3]. Sats 3. Låt Q1 och Q2 vara två positivt definita n×n-matriser. Låt λmin vara det minsta egenvärdet hos Q1. Om B = [bj ] är en matris med kolonnvektorer bj och BTQ1B = Q2, då gäller att, bTj Q1bj = (Q2)jj , j = 1, . . . , n. (9) Dessutom gäller att ||bj ||2 ≤ (Q2)jj/λmin for varje j = 1, . . . , n. För rutnäten AiZn, i = 1, 2, 3 i tripletten associerar vi klassen av kvadratiska former som är integralekvivalenta till Qi = AT i Ai för varje i. Rutnäten är kongruenta och därmed isometriska om och endast om dessa ekvivalensklasser är identiska. Ekvivalensklasserna är i sin tur identiska om och endast om det finns en kvadratisk matris B med determinant ±1 så att BTQ1B = Q2 [7, Kap 3.1]. 15 4 Metod Algoritmen från flödesschemat i figur 7 utgör hela metoden. Algoritmen har programmerats med programeringsspråket Python. I detta arbete ges ingen källkod för programmeringen av algoritmen, vilket förklaras i Appendix C. Nedan följer hur teorin är kopplad till algoritmen och stegen för denna. 4.1 Steg i algoritmen För att undersöka antalet isospektrala icke-isometriska platta torusar i fyra dimensioner har vi utvecklat en algoritm för att genomföra sökningen. För att ge en klarare överblick följs nedan den röda tråden i figur 7. Välj tal q och dimension n Algoritmen är utformad i ett generellt format, vilket i teorin gör det möjligt att anpassa till dimensionen n och primtalet q. Dessa parametrar bestämmer vilka värden bokstäverna i våra linjära koder kan anta och påverkar strukturen hos de linjära koderna. Se avsnitt 3.2 för mer information om linjära koder. I detta arbete använder vi som tidigare nämnt olika primtal q och dimension n = 4. Radreducerade trappstegsmatriser För att generera de möjliga linjära koderna börjar vi med att konstruera alla RREF-matriser för de valda värdena på q och n, enligt avsnitt 3.3. Dessa matriser fungerar som representanter för de linjära koderna. Antal kodord När RREF-matriserna är framtagna beräknar vi utifrån dem de linjära kodernas kardinaliteter enligt avsnitt 3.4 och sorterar dem med avseende på detta. Tecknad permutation Vi granskar sedan varje indelning av RREF-matriser separat, där varje grupp innehåller matri- ser med samma kardinalitet för deras korresponderande linjära koder. Genom att jämföra dessa grupper kan vi identifiera RREF-matriser som är tecknade permutationer av varandra. Om två matriser är tecknade permutationer vet vi att de också är isometriska, enligt avsnitt 3.5. Detta effektiviserar vår kod, eftersom vi undviker att översätta alla RREF-matriser till linjära koder och endast fokuserar på att hitta icke-isometriska platta torusar. Indelning i ekvivalensklasser Genom att undersöka de tecknade pemutationerna har vi delat in RREF-matriserna i olika ekvi- valensklasser. Se avsnitt 3.1. Varje klass innehåller RREF-matriser som representerar isometriska platta torusar. Ekvivalensklassen kommer alltså från att två RREF-matriser eller dess korrespon- derande linjära koder definieras som ekvivalenta då de skiljer sig med en tecknad permutation. Detta innebär att vi bara behöver undersöka en representant från varje ekvivalensklass. Viktfördelning När vi har valt ut en representant för varje klass översätts dess RREF-matris till en linjär kod. Därefter analyserar vi dess viktfördelning som i avsnitt 3.6. Detta görs för att avgöra om RREF- matriserna och deras korresponderande platta torusar är isospektrala eller inte. 16 Isometrikontroll Slutligen utförs, om potentiella tripletter har hittats, en sista isometrikontroll för att säkerställa icke-isometri, då de kan vara isometriska trots att de inte är tecknade permutationer av varandra. Detta görs med hjälp av rutnät och kvadratiska former. Se avsnitt 3.7. När denna process är avslutad återstår endast icke-isometriska isospektrala tripletter, och algoritmen är klar. 4.2 Avgränsningar Avgränsningarna i projektet är främst ett resultat av tidsbegränsningar. En stor sådan avgränsning är reduceringen till att endast försöka bevisa existensen av tripletterna. Tidigare var strategin att dels försöka hitta tripletter och dels även, ifall att inga tripletter upptäcks, motbevisa deras existens. Till en början hade arbetet två tillvägagångssätt; att söka tripletter med linjära koder och att genomföra en helteckande sökning med Schiemanns algoritm som också kunde leda till ett motbevis. Motbeviset baserades på teorier skrivna av matematikern Alexander Schiemann, och idén var att utöka hans motbevis för existensen i de tre första dimensionerna, till fjärde dimensionen. Mycket tid lades på Schiemanns motbevis och det var en del av metoden långt in i arbetet. Däremot valdes till slut motbeviset bort. Anledningen är att matematiken bakom teorierna blev för komplex och tidskrävande. En annan central avgränsning är begränsningen av vår metod till algoritmen baserad på linjära koder. Det finns flera satser om isometri och isospektralitet mellan platta torusar, kvadratiska former eller rutnät, som potentiellt kan användas till att skapa en triplett-sökande algoritm. Valet att endast fokusera på rutnät och deras linjära koder baseras på råd från handledare, samt att dessa teorier är lättare att tillämpa i programmering. I arbetet används endast algoritmen för att undersöka existensen i fyra dimensioner, med låga värden på q. Algoritmen har potential att söka efter tripletter i godtycklig dimension och för god- tyckligt modulo-tal q, men programmeringsmässigt begränsas den ännu av dess höga komplexitet. Därför används endast n = 4 och 2 ≤ q ≤ 11 i detta arbete. 5 Resultat Sökningen efter tripletter med de önskade egenskaperna gjordes i fyra dimensioner och för primtal q ≤ 11. Inga tripletter hittades. Det gjordes även sökningar, för samma värden på n och q, efter par med samma egenskaper, men inga par hittades heller. Trots detta hittades relevanta samband som kan vara intressanta för vidare undersökning av frågan. Nedan följer dessa resultat. 5.1 Antal linjära koder givet n och q I ett tidigt skede i algoritmen tog vi fram alla RREF-matriser och därmed alla linjära koder, givet n och q. För dessa värden kunde antalet linjära koder enkelt beräknas. Se tabell 2 för resultaten. Antalet linjära koder växer både då n ökar och då q ökar. De värden på q som är sammansatta ger upphov till betydligt högre antal RREF-matriser än primtal. Om vi bortser från sammansatta q, ser vi att antalet linjära koder följer ett mönster som beror på n och q. I de första fyra dimensionerna följer antalet linjära koder, αn för primtal q närmre bestämt följande ekvationer, α1 = 2, (10) α2 = q + 3, (11) α3 = 2q2 + 2q + 4, (12) α4 = q4 + 3q3 + 4q2 + 3q + 5. (13) 17 n 1 2 3 4 q 2 2 5 16 67 3 2 6 28 212 4 3 15 129 1983 5 2 8 64 1120 6 4 30 448 14204 7 2 10 116 3652 8 4 37 802 43339 9 3 23 445 24033 10 4 40 1024 75040 11 2 14 268 19156 13 2 16 368 35872 17 2 20 616 99472 19 2 22 764 152404 Tabell 2: Antalet linjära koder för några q < 20 och för dimensionerna n ≤ 4. Under arbetets gång upptäcktes en ny proposition för vad antalet linjära koder är för en generell dimension n och ett primtal q. Proposition 3. Låt αn vara antalet linjära koder i (Z/qZ)n där q är ett primtal. Då är α1 = 2 och αn = αn−1 + 1 + n−1∑ k=1 ( n−k∑ x1=1 n−k∑ x2=x1 · · · n−k∑ xk=xk−1 q ∑k i=1 xi). (14) Bevis. Vi visar här endast att formeln i 4 dimensioner ger samma resultat som andra teoretiska resultat. Läsaren får vid intresse testa formeln för fler dimensioner. Vi använder oss av att linjära koder är grupper. En linjär kod av längd qn där q är ett primtal, har delgrupper av storlek 1, q, q2, ..., qn . Vi är intresserade av fallet då n = 4. Vi fixerar q. Antalet linjära koder givet q kan då finnas av storlek 1, q, q2, q3 och q4, där den enda linjära koden av storlek 1 är identitetskoden och den enda linjära koden av storlek q4 är koden med alla möjliga kodord. Eftersom den linjära koden av storlek q4 innehåller alla möjliga kodord är alla linjära koder (givet samma q) delgrupper av denna. Antalet delgrupper av gruppen (Z/qmZ)4 fås genom att sätta m = 1 i formeln [22, Sats 3.2]: (q2 + q + 1)3(q2 + 1)q4m+2 − ((2m+ 3)q3 − 2m− 1)(q3 + q)(q + 1)3q3m (q2 − 1)2(q3 − 1)2 − 4mq4 + 4mq3 + 7q4 + 9q3 − 4mq + 6q2 − 4m+ q − 1 (q2 − 1)2(q3 − 1)2 . Insättning av m = 1 och förkortning av polynomet ger q4 + 3q3 + 4q2 + 3q + 5. Formeln 14 ger α2 = q + 3, α3 = 2q2 + 2q + 4. Beräkning av α4 ger: 18 α4 = α3 + 1 + 3∑ k=1 ( 4−k∑ x1=1 · · · 4−k∑ xk=xk−1 q ∑k i=1 xi) = = α3 + 1 + 3∑ x1=1 qx1 + 2∑ x1=1 2∑ x2=x1 q ∑2 i=1 xi + 1∑ x1=1 1∑ x2=x1 1∑ x3=x2 q ∑3 i=1 = = α3 + 1 + q1 + q2 + q3 + q1+1 + q1+2 + q2+2 + q1+1+1 = = q4 + 3q3 + 4q2 + 3q + 5, vilket är detsamma som antalet delgrupper nämnt ovan. Vi misstänker även att antal linjära koder kan ges av följande icke-rekursiva formel: Förmodan 1. Låt αn vara antalet linjära koder i (Z/qZ)n, där q är ett primtal. Då gäller att: αn = 1 + n+ n−1∑ p=1 n−p∑ j=1 ( p∑ x1=1 p∑ x2=x1 · · · p∑ xj=xj−1 q ∑j i=1 xi). Ett sista resultat angående antalet linjära koder för primtal q, är hur de linjära koderna är fördelade efter deras kardinalitet. Kardinaliteten antar alltid något värde i mängden {q0, q1, ..., qn} då q är ett primtal, enligt Sats 1. Antalet linjära koder, αn blir som högst då kardinaliteten närmar sig qn/2. Dessutom är antalet linjära koder symmetriskt kring qn/2, det vill säga att qi ger lika många linjära koder som qn−i, för i = 0, . . . , n. Detta gäller för alla dimensioner n av kombinatoriska skäl. Ett exempel på detta ges i figur 8, där q = 2. Figur 8: Bild över antalet linjära koder av en särskild kardinalitet qk, för q = 2 och n ≤ 4. Antalet linjära koder fördelas över kardinaliteterna i en triangelstruktur. 5.2 Antal ekvivalensklasser för vissa n och q I algoritmen delas de olika linjära koderna in i ekvivalensklasser med avseende på tecknad permuta- tion. Om två linjära koder är tecknade permutationer av varandra så tillhör de samma ekvivalens- klass. Resultatet av att räkna antalet ekvivalensklasser för varje primtal q och dess kardinaliteter, är att fördelningen blir symmetrisk. På samma sätt som för antalet linjära koder, har vi att kar- dinaliteten qi ger lika många ekvivalensklasser som qn−i för i = 0, . . . , n. Detta illustreras i tabell 3. Om istället q fixeras och n ändras får vi dessutom återigen en fördelning av triangelstruktur. 19 Kardinalitet q0 q1 q2 q3 q4 q 2 1 4 6 4 1 3 1 4 7 4 1 5 1 8 18 8 1 7 1 12 38 12 1 Tabell 3: Antalet ekvivalensklasser för olika primtal q ≤ 7 och dess kardinaliteter, med fixerad dimension n = 4. 6 Diskussion Resultatet kopplat till huvudfrågan är att algoritmen inte lyckades hitta fyrdimensionella tripletter av isospektrala, icke-isometriska platta torusar. Trots detta går det inte att dra någon slutsats om existensen. Detta beror på att sökningen gjorts inom ett mindre urval och för linjära koder där q är primtal. Däremot kan en hypotes bildas utifrån arbetets resultat, att det inte existerar fyrdimensionella tripletter vid sökning genom linjära koder med primtalsvärden på q. Hypotesen motiveras av att dessa linjära koder är mycket lika varandra i strukturen oavsett storleksordningen på primtalet som används. Varje nollskilt element i koden får alltid full ordning, medan det för sammansatta q skapas mer intressanta delgrupper av lägre ordning. De är särskilt intressanta eftersom de ger upphov till fler sätt för två linjära koder att ha samma viktfördelning. Dessutom kan pivotelementen i respektive RREF-matris anta andra värden än 1. Istället för att söka bland linjära koder där q är primtal, hade ett framtida arbete exempelvis kunnat undersöka om det finns tripletter för sammansatta q. Denna slags sökning var inte möjlig i detta arbete på grund av algoritmens begränsningar och på grund av omprioriteringar. Den resulterande algoritmen utvecklades tillräckligt för att kunna söka efter tripletter med önskade egenskaper, i godtycklig dimension n. Däremot är den endast anpassad för inmatning av låga primtal q. När höga primtal q > 11 matades in blev körtiden flera timmar lång. Orsaken är att flera delar i algoritmen fortfarande är baserad på kod med hög komplexitet. Om mer tid hade lagts vid att undersöka hur algoritmen kan skrivas på ett beräkningsmässigt snabbare sätt, hade körtiden kunnat förkortas. Istället behövde andra delar i arbetet prioriteras. En annan orsak till den höga körtiden är urvalet av linjära koder. Urvalet av linjära koder som söktes igenom i algoritmen är litet i jämförelse med den teoretiskt sett oändliga mängden linjära koder som går att undersöka. Trots det innehåller urvalet några tiotusental olika linjära koder som alla jämfördes med varandra efter önskade egenskaper. Ett mer noggrant utvalt urval hade därmed också kunnat korta ner körtiden. Algoritmen utvecklades heller inte till att kunna söka efter tripletter bland linjära koder med sammansatta q, eftersom algoritmen hade fått ännu högre komplexitet samt eftersom andra delar i arbetet behövde prioriteras. Sammanfattningsvis har algoritmen fortfarande stor utvecklingspotential. Troligtvis hade algoritmen hunnit bli snabbare och bidragit med fler slags resultat om metoden från början hade begränsats till utvecklingen av algoritmen. I det tidiga stadiet av arbetet var det däremot svårt att avgöra om Schiemanns algoritm eller algoritmen baserad på linjära koder skulle bidra med mest nytta. Generellt sett blev antalet linjära koder då q är sammansatt avsevärt fler än för primtal q . Orsaken till detta är de tidigare nämnda delgrupperna av lägre ordning som skapas för sammansatta q. Pivotelementen i RREF-matriserna kan anta fler värden vilket skapar fler kombinationer. Det gäller även att ju fler delare talet q har, desto fler linjära koder skapas. Därför fick vi exempelvis i tabell 2 att antalet blev större för q = 8 än för q = 9. Däremot upptäcktes ingen generell formel för antalet linjära koder, beroende av n och q, då q är sammansatt. Att konstruera en sådan formel, liksom generella formeln för primtal, skulle vara en intressant uppgift i ett framtida arbete. En fortsättning av arbetet hade även kunnat handla om att vidare utforska om det finns en generell formel för spridningen av antalet ekvivalensklasser över olika kardinaliteter. Speciellt för sammansatta q skulle denna formel ha varit av särskilt intresse. 20 Referenser [1] V. Borrelli et al. The folder: flat tori finally visualised!, u.å. [2] M. Kac. Can one hear the shape of a drum? The American Mathematical Monthly, 1966. [3] J. Milnor. Eigenvalues of the laplace operator on certain manifolds. Proc. Nat. Acad. Sci., 51, 1964. [4] M. Kneser. Lineare relationen zwischen darstellungszahlen quadratischer formen, mathe- matische annalen. Mathematische Annalen, 168, 1967. [5] Y. Kitaoka. Positive definite quadratic forms with same representation numbers. Archiv der Mathematik, 28, 1977. [6] A. Schiemann. Ein beispiel positiv definiter quadratischer formen der dimension 4 mit gleichen darstellungszahlen. Archiv der Mathematik, 54, 1990. [7] E. Nilsson, J. Rowlett och F. Rydell. The isospectral problem for flat tori from three per- spectives. American Mathematical Society, 60, 2023. [8] W. Ebeling. Lattices and codes. Springer, 2013. [9] V. Borrelli et al. Flat tori in three-dimensional space and convex integration. Proc. Natl. Acad. Sci., 109(19), 2012. [10] N. Lee. Geometry: from Isometries to Special relativity. Springer, 2020. [11] S. Wolpert C. Gordon, D. L. Webb. One cannot hear the shape of a drum. Bulletin of the American Mathematical society, 27, 1992. [12] D. L. Webb C. Gordon. You can’t hear the shape of a drum. American scientist, 84, 1996. [13] Jitse Niesen. Isospectral drums.svg. Hämtad 2 Maj 2024. [14] Conway, J.H. The sensual quadratic form. The Mathematical Association of America, 1997. [15] A. Schiemann. Ternäre positiv definite quadratische formen mit gleichen darstellungszahlen. PhD thesis, Mathematischen Institut der Universität, 1994. Dissertation zur erlangung des doktorgrades, Nr. 268. [16] A. Schiemann. Ternary positive definite quadratic forms are determined by their theta series. Mathematische Annalen, 308, 1997. [17] N. J. A. Sloane J. H. Conway. Four-dimensional lattices with the same theta series. Interna- tional Mathematics Research Notices, 4, 1992. [18] J.M. Cervino G. Hein. The conway-sloane tetralattice pairs are non-isometric. Advances in Mathematics, 228, 2011. [19] J. R. Durbin. Modern Algebra: An Introduction. Wiley, Hoboken, NJ, 6th edition, 2009. [20] C. D. Meyer. Matrix analysis and applied linear algebra. Society for Industrial and Applied Mathematics, 2000. [21] S. James Gates Jr. et al. N = 4 and n = 8 susy quantum mechanics and klein’s vierergruppe. opublicerad, 2018. [22] A. Sehgal F. Admasu. Counting subgroups of fixed order in finite abelian groups. opublicerad, 2018. [23] I. Cucurezeanu T. Andreescu, D. Andrica. An Introduction to Diophantine Equations. Birk- häuser, 2010. 21 A Appendix 1 - Notationslista n Dimension. Z Mängden av alla heltal. R Mängden av alla reeltal. q Modulo-tal som används för att begränsa linjära koder. Γ Rutnät TΓ Platta torusen med korresponderande rutnät Γ. R/Γ Kvotgruppen för platta torusen med korresponderande rutnät Γ. λ Egenvärde ∆ Laplaceoperatorn ∇ Gradient ∼ Ekvivalensrelation ord(g) Ordningen av elementet g. [s] Ekvivalensklassen av s. C Linjär kod Z/qZ Mängden och grupp av heltal modulo q. (Z/qZ)n Mängden och grupp av heltal modulo i n dimensioner. RREF Förkortning för row reduced echelon form som översätts till radreducerad trapp- stegsform. On(R) Ortogonala gruppen. K Kardinalitet. Mängden element i en grupp. αn Antalet linjära koder för dimension n. SGD Största gemensamma delaren. B Appendix 2 - Teori B.1 Bézouts identitet Sats 4. Låt m,n ∈ Z, m,n ≥ 0. Då existerar det x, y ∈ Z sådana att mx+ ny = SGD(m,n). [23] (15) B.2 Bézouts utökade identitet Sats 5. Låt a1, a2, . . . , an ∈ Z, a1, a2, . . . , an ≥ 0. Då existerar det x1, x2, . . . , xn ∈ Z sådana att a1x1 + a2x2 + · · ·+ anxn = SGD(a1, a2, . . . , an). (16) Bevis. Detta visas genom induktion. Basfallet är fallet med Bézouts identitet ovan 4. Induktionsantagande Om det existerar x1, . . . , xn ∈ Z sådana att a1x1+· · ·+anxn = SGD(a1, . . . , an), existerar det då x1, . . . , xn, xn+1 ∈ Z sådana att a1x1+· · ·+anxn+an+1xn+1 = SGD(a1, . . . , an, an+1)? SGD(a1, . . . , an, an+1) = SGD(SGD(a1, . . . , an), an+1) vilket innebär av Bézouts identitet att det existerar y1, y2 ∈ Z sådana att y1SGD(a1, . . . , an) + y2an+1 = SGD(SGD(a1, . . . , an), an+1). Med hjälp av induktionsantagandet kan vi skriva om detta till y1(a1x1 + · · ·+ anxn) + y2an+1 = SGD(a1, . . . , an, an+1). Multiplicering av y1 med x1, . . . xn ger heltal, vilket slutför beviset. i C Appendix 3 - Källkod För att skydda en eventuell patentansökan så gjordes valet att inte dela källkoden till arbetet. Att behålla kontrollen över koden är avgörande för att undvika obehörig användning eller kopiering. Detta är en del av strategin för att skydda intellektuell egendom och möjliggöra säkra licensierings- och partnerskapsmöjligheter. ii Inledning Problemformulering Syfte Rapportens uppbyggnad Den platta torusen Den platta torusens olika representationer Samma form och samma spektrum - isometri och isospektralitet En tredje representation med kvadratiska former Tidigare forskning Teoretisk bakgrund till den triplettsökande algoritmen Gruppteori Linjära koder RREF-matriser Omvandling från rutnät till linjära koder RREF-matriser för sammansatta q Antal kodord i en linjär kod Tecknad permutation Linjära koders viktfördelning Omvandling från linjära koder till rutnät Metod Steg i algoritmen Avgränsningar Resultat Antal linjära koder givet n och q Antal ekvivalensklasser för vissa n och q Diskussion Appendix 1 - Notationslista Appendix 2 - Teori Bézouts identitet Bézouts utökade identitet Appendix 3 - Källkod