Elementär talteori, gruppteori och Ramanujan-grafer

Elementär talteori, gruppteori och Ramanujan-grafer är en bok i matematik vars mål är att göra konstruktionen av Ramanujan-grafer tillgänglig för matematikstudenter på grundnivå. För att göra det täcker det flera andra viktiga ämnen inom grafteori , talteori och gruppteori . Den skrevs av Giuliana Davidoff , Peter Sarnak och Alain Valette och publicerades 2003 av Cambridge University Press , som volym 55 i bokserien London Mathematical Society Student Texts.

Bakgrund

Huvudartikel: Ramanujan-graf

I grafteorin är expandergrafer oriktade grafer med hög anslutningsbarhet: varje tillräckligt liten delmängd av hörn har många kanter som förbinder den med de återstående delarna av grafen. Glesa expandergrafer har många viktiga tillämpningar inom datavetenskap, inklusive utveckling av felkorrigeringskoder , design av sorteringsnätverk och avrandomisering av randomiserade algoritmer . För dessa applikationer måste grafen konstrueras explicit, snarare än att bara få sin existens bevisad.

Ett sätt att visa att en graf är en expanderare är att studera egenvärdena för dess närliggande matris . För en $r$ - vanlig graf är dessa reella tal i intervallet $[-r,r]$ , och det största egenvärdet (motsvarande all -1s egenvektor ) är exakt $r$ . Den spektrala expansionen av grafen definieras från skillnaden mellan de största och näst största egenvärdena, spektralgapet , som styr hur snabbt en slumpmässig gång på grafen sätter sig till sin stabila fördelning ; detta gap kan vara högst $2{\sqrt {r-1}}$ . Ramanujan -graferna definieras som de grafer som är optimala ur synvinkeln av spektral expansion: de är $r$ -regelbundna grafer vars spektralgap är exakt $2{\sqrt {r- 1}}$ .

Även om Ramanujan-grafer med hög grad , såsom de fullständiga graferna , är lätta att konstruera, behövs expandergrafer av låg grad för tillämpningarna av dessa grafer. Flera konstruktioner av låggradiga Ramanujan-grafer är nu kända, varav den första var av Lubotzky, Phillips & Sarnak (1988) och Margulis (1988) . Recensenten Jürgen Elstrod skriver att "medan beskrivningen av dessa grafer är elementär, är beviset för att de har de önskade egenskaperna det inte". Elementär talteori, gruppteori och Ramanujan-grafer syftar till att göra så mycket av denna teori tillgänglig på en elementär nivå som möjligt.

Ämnen

Dess författare har delat in elementär talteori, gruppteori och Ramanujan-grafer i fyra kapitel. Den första av dessa ger bakgrund i grafteori , inklusive material om grafernas omkrets (längden på den kortaste cykeln), om graffärgning och om användningen av den probabilistiska metoden för att bevisa förekomsten av grafer för vilka både omkretsen och antalet färger som behövs är stort. Detta ger ytterligare motivation för konstruktionen av Ramanujan-grafer, eftersom de som är konstruerade i boken ger explicita exempel på samma fenomen. Detta kapitel tillhandahåller också det förväntade materialet om spektralgrafteori , som behövs för definitionen av Ramanujan-grafer.

Kapitel 2, om talteori , inkluderar summan av två kvadraters sats som karakteriserar de positiva heltal som kan representeras som summor av två kvadrater av heltal (nära kopplade till normerna för Gaussiska heltal ), Lagranges fyrkvadratsats enligt vilken alla positiva heltal kan representeras som summor av fyra kvadrater (bevisat genom att använda normerna för Hurwitz quaternions ), och kvadratisk reciprocitet . Kapitel 3 berör gruppteori , och i synnerhet teorin om de projektiva speciallinjära grupperna $PSL(2,\mathbb {F} _{q})$ och projektiva linjära grupper $PGL(2,\mathbb {F} _{q})$ över de finita fälten vars ordning är ett primtal $q$ och representationsteorin för finita grupper .

Det sista kapitlet konstruerar Ramanujan-grafen $X^{p,q}$ för två primtal $p$ och $q$ som en Cayley-graf för gruppen $PSL(2,\mathbb {F} _{q})$ eller $PGL(2,\mathbb {F} _{q})$ (beroende på kvadratisk ömsesidighet) med generatorer definierade genom att ta modulo $q$ en uppsättning $p+1$ kvaternioner som kommer från representationer av $p$ som summan av fyra kvadrater. Dessa grafer är automatiskt $(p+1)$ -regelbundna. Kapitlet ger formler för deras antal hörn och uppskattningar av deras omkrets. Även om det inte helt bevisar att dessa grafer är Ramanujan-grafer, bevisar kapitlet att de är spektralexpanderare, och beskriver hur påståendet att de är Ramanujan-grafer följer av Pierre Delignes bevis på Ramanujan-förmodan (kopplingen till Ramanujan varav namnet av dessa grafer härleddes).

Publik och mottagning

Den här boken är avsedd för avancerade studenter som redan har sett en del abstrakt algebra och verklig analys . Granskaren Thomas Shemanske föreslår att man använder det som grund för ett seniorseminarium, som en snabb väg till många viktiga ämnen och ett intressant exempel på hur dessa till synes separata ämnen går samman i denna ansökan. Å andra sidan tror Thomas Pfaff att det skulle vara svårt även för de flesta studenter på högre nivå, men det kan vara ett bra val för självständiga studier eller en valbar forskarutbildning.