Pells ekvation

cow_and_archimedes

Pells ekvation är min favoritekvation. Jag tänker inte försöka förklara varför så är fallet (vissa saker gillar man bara, och ibland är det nog bäst att inte fundera så mycket över varför) men jag ska i alla fall skriva några rader om denna fascinerande ekvation, vars rika historia spänner över tusentals år och som, för min del, just nu är av särskilt intresse emedan den figurerar i den kurs i talteori som jag för närvarande läser, där den användas för att i en kvadratisk talkropp K=\mathbb{Q}(\sqrt{d}) finna den enhet (modulo enhetsrötterna) som genererar heltalsringen \mathcal{O}_K. Detta är den idag kanske viktigaste tillämpningen av Pells ekvation, men var knappast något man hade i åtanke när man började studera dess lösningar i Indien och Grekland för över två tusen år sedan.

Så hur ser Pells ekvation ut? Svaret på den frågan är att Pells ekvation faktiskt är ett samlingsnamn för en särskild typ av ekvationer, nämligen de kvadratiska diofantiska ekvationer som kan skrivas på formen x^2-ny^2=1, där n är ett positivt, kvadratfritt heltal. De nära besläktade ekvationerna x^2-ny^2=-1 och x^2-ny^2=\pm 4 kallas ibland också för Pells ekvation. (Varför \pm 4? Lugn, vi kommer till det snart.)

Denna ofullständiga sammanställning är skriven i läsning hast och lika mycket för min egen skull som för någon annans. Även om framställningen är bristfällig så hoppas jag innehållet, tillsammans med de tillhandahållna länkarna, kan bjuda på intressant läsning.

Brahmagupta, Bhaskara och Chakravalametoden

Brahmagupta var en mycket framstående matematiker som levde på 600-talet i den del av Indien som idag går under namnet Rajasthan. Han gav sig i kast med Pells ekvation, och nådde viss framgång då han med hjälp av identiteten (kallad Brahmaguptas identitet)

(x_1^2-ny_1^2)\cdot(x_2^2-ny_2^2)=(x_1x_2+ny_1y_2)^2-n(x_1y_2+x_2y_1)^2

dels kunde generera oändligt många lösningar till en given Pells ekvation givet att en icke trivial sådan (det vill säga en lösning skild från (x,y)=(1,0)) fanns att tillgå, dels ofta kunde finna en lösning genom att utgå från en lösning till en ekvation på formen x^2-ny^2=k och sedan kombinera den med andra lösningar och försöka reducera resultatet till en lösning till Pells ekvation genom division.

Omkring femhundra år senare lyckades Bhaskara, en annan framstående indisk matematiker, hitta en generell metod för att lösa Pells ekvation. Hans metod, den så kallade Chakravalametoden, utgår från Brahmaguptas identitet och letar sig sedan stegvis fram mot en lösning. Givet en lösning (a,b,k) till a^2-nb^2=k och den triviala lösningen (c,1,c^2-n) så erhålls en ny lösning (ac+nb, a+bc,k(c^2-n)). Denna nya lösning kan sedan reduceras till

\left( \dfrac{ac+nb}{k}, \dfrac{a+bc}{k},\dfrac{c^2-n}{k} \right).

Om man nu väljer cc^2-n är minimal givet att (a+bc)/k är ett heltal, så följer att den reducerade lösningen är en heltalslösning. Denna process repeteras sedan till dess att en lösning på formen (\alpha,\beta,1) erhålles. Att metoden alltid fungerar visades 1768 av Joseph-Louis Lagrange.

Problema bovinum

Ett tidigt problem relaterat till Pells ekvation, som brukar tillskrivas Arkimedes, är det så kallade problema bovinum (koproblemet). Problemet går ut på att beräkna antalet djur i solgudens boskapshjord, som en gång i tiden betade på Sicilien. Hjorden består av kor och tjurar i fyra olika teckningar: vit (som mjölk!), svart, brokig och gul. Låt T_V, T_S, T_B och T_G beteckna antalet tjurar i de olika färgerna och låt på samma sätt K_V, K_S, K_B och K_G beteckna antalet kor. Arkimedes problema bovinum kan då formuleras som ett ekvationssystem på följande sätt

\begin{aligned} T_V&=\frac{5}{6}T_S+T_G, & K_V&=\frac{7}{12}(T_S+K_S),\\T_S&=\frac{9}{20}T_B+T_G, & K_S&=\frac{9}{20}(T_B+K_B),\\T_B&=\frac{13}{42}T_V+T_G, & K_B&=\frac{11}{30}(T_G+K_G),\\&&K_G&=\frac{13}{42}(T_V+K_V), \end{aligned}

men med det intressanta tillägget att T_V+T_S ska vara en kvadrat samt att T_B+T_G ska vara ett triangeltal. Bortser man från detta tillägg, så kan vi använda enkla metoder från linjär algebra för att finna den minsta positiva lösningen till ekvationssystemet (som är underbestämt och har oändligt många lösningar). Om inga misstag begås blir resultatet då följande

\begin{aligned} T_V&=10\;366\;482=k\cdot2\;226,  & K_V&=7\;206\;360,\\T_S&=7\;460\;514=k\cdot1\;602, & K_S&=4\;893\;246,\\T_B&=7\;358\;060=k\cdot1\;580, & K_B&=3\;515\;820,\\T_G&=4\;149\;387=k\cdot891, & K_G&=5\;439\;213, \end{aligned}

k=4\;657, vilket ger totalt 50\;389\;082 djur i hjorden. Man får samtliga lösningar genom att ta heltalsmultipler av ovanstående lösning. Nu inflikar Arkimedes att den som finner en sådan lösning förvisso kan en hel del om siffror, men ändå inte kan anses särskilt begåvad. För att imponera på Arkimedes är man nämligen tvungen att lösa problemet i sin helhet, det vill säga med det kluriga tillägget som vi hittills har bortsett från. Vi kan i efterhand konstatera att Arkimedes knappast var lätt att imponera på. Åren gick, och fler än två tusen av dem hann passera innan en tysk matematiker vid namn A. Amthor år 1880 slutligen löste problemet (åtminstone om man har överseende med att hans lösning innehöll ett avrundningsfel).

Vi ska här presentera den holländske matematikern Hendrik Lenstras lösningsmetod, som också går att läsa om i hans artikel Solving the Pell Equation. Vi letar alltså efter ett positivt heltal a sådant att vi får en lösning till det fullständiga problemet då vi multiplicerar vår ovanstående, partiella lösning med a. Emedan T_V+T_S har primtalsfaktoriseringen

T_V+T_S=2^2\cdot3\cdot11\cdot29\cdot4\;657,

så följer att a=by^2, där b=3\cdot11\cdot29\cdot4\;657 och y är ett heltal. Vidare så är T_B+T_G ett triangeltal endast om 8\cdot(T_B+T_G)+1 är en kvadrat, vilket leder oss till att

8\cdot(T_B+T_G)+1=8\cdot2\;471\cdot4\;657\cdot by^2+1=x^2.

där x är ett heltal. Ansätt nu

n=8\cdot2\;471\cdot4\;657\cdot b=2\cdot3\cdot7\cdot11\cdot29\cdot353\cdot(2\cdot4657)^2.

Då har vi reducerat problema bovinum till att lösa Pells ekvation x^2-ny^2=1. Eftersom n inte är en kvadrat så har denna ekvation oändligt många lösningar, och så är alltså också fallet med problema bovinum. Den minsta lösningen ger att storleken på hjorden är ungefär 7,76\cdot10^{206544} djur. Huruvida dessa djur faktiskt ryms på Sicilien, och huruvida detta är en aspekt av problemet som bör tas i beaktande, lämnar jag åt läsaren att ta ställning till.

Kedjebråk

I Europa återupptäckte man, lyckligt oventade om de framsteg som gjorts i Indien, Pells ekvation på 1600-talet, och roade sig med att försöka lösa den fram till dess att Lagrange slutligen lyckades reda ut kopplingen mellan dess lösningar och kedjebråk under andra halvan av 1700-talet.

Utan att gå in på några detaljer så ska jag här kortfattat beskriva hur kedjebråk kan användas för att lösa Pells ekvation. Ett kedjebråk är ett sätt att skriva ett tal x (i vårt fall ett reellt, algebraiskt tal) på formen

x=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{\ddots+\cfrac{1}{a_n}}}}

(ett sådant kedjebråk kallas ändligt) eller på formen

x=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\ddots}}

varvid man kallar det för ett oändligt kedjebråk. Ofta förkortas ovanstående uttryck till x=[a_0;a_1,a_2,\hdots,a_n] i det ändliga fallet och till x=[a_0;a_1,a_2,\hdots] i det oändliga fallet.

Låt d vara ett positivt heltal som inte är en kvadrat. Då är kedjebråket \sqrt{d}=[a_0,a_1,a_2,\hdots] unikt (i bemärkelsen att samtliga koefficienter är unikt bestämda av d) och oändligt, och därutöver periodiskt, vilket innebär att a_i=a_{i+p} för i>N och p.

Det var Lagrange som gjorde redde ut sambandet mellan Pells ekvation och kedjebråk. Låt d=[a_0,a_1,a_2,\hdots] vara som ovan, och låt m_i/n_i=[a_0,a_1,a_2,\cdots,a_i] vara ett bråk i reducerad form. Då finns, för varje positiv lösning (a,b) till x^2-dy^2=1, i\in\mathbb{N} så att (b,a)=(m_i,n_i). Om kedjebråket [a_0,a_1,a_2,\cdots] har udda periodlängd (vi talar här om den minsta periodlängden) så finner man på liknande sätt lösningar till x^2-dy^2=-1.

Algebraisk talteori

I en reell kvadratisk talkropp \mathbb{Q}(\sqrt{d}) kan varje algebraiskt heltal skrivas på formen

x=a+b\sqrt{d},\; a,b\in\mathbb{Z},

om d\not\equiv1\;(\hspace{-0.7em}\mod\;4), och på formen

x=\dfrac{a+b\sqrt{d}}{2},\; a,b\in\mathbb{Z},\;a\equiv b\;(\hspace{-0.7em}\mod\;2),

om d\equiv1\;(\hspace{-0.7em}\mod\;4). Det följer av Dirichlets enhetssats att det finns en unik minsta enhet större än 1 (den fundamentala enheten) sådan att denna enhet genererar samtliga enheter större än 1. I  det första fallet är den fundamentala enhenten a_1+b_1\sqrt{d}, där (a_1,b_1) är den minsta lösningen till a_1^2-db_1^2=\pm1, och i det andra fallet är den fundamentala enheten \frac{1}{2}(a_1+b_1\sqrt{d}), där (a_1,b_1) är den minsta lösningen till a_1^2-db_1^2=\pm4.

Så vem var Pell?

John Pell var en engelsk matematiker som levde och verkade på 1600-talet. Att hans har fått ge namn åt Pells ekvation är resultatet av ett missförstånd av Leonard Euler. Euler blandade nämligen ihop Pell med dennes samtida landsman, och tillika matematiker, William Brouncker. Den senare av de två hade nämligen löst Pells ekvation. Euler fick nys om dennes lösning, men tillskrev den av misstag till Pell, vars namn sedan dess även namnger ekvationen.

Matroider

De senaste veckorna har jag haft nöjet att stifta bekantskap med teorin om matroider, som har starka kopplingar till linjär algebra och grafteori, och även till ändliga geometrier (ett ämne som jag är mycket förtjust i). Teorin hämtar sin motivation i och generaliserar studiet av linjärt beroende hos vektorer. Givet en matris M med kolonnvektorer v_1, v_2, \hdots, v_n och en mängd I \subseteq \{1, 2, \hdots, n\}, så kan vi ställa oss frågan huruvida vektorerna i multimängden \{v_i \;|\; i \in I\} är linjärt beroende eller inte. Matroidteorin har uppkommit genom försök att generalisera vissa grundläggande egenskaper hos sådana multimängder.

Bland de första att studera matroider var Hassler Whitney, som 1935 lade grunden till teorin (samt myntade begreppet matroid) i den mycket läsvärda artikeln On the Abstract Properties of Linear Dependence, där han introducerar matroider genom att ge flera olika, till synes väsensskilda men likväl ekvivalenta, definitioner (detta lyfts ofta fram som ett särdrag hos matroidteorin, och dylika definitioner kallas ibland kryptomorfa för att understryka denna, till sin natur svårdefinierade, egenskap).

Whitney var dock inte ensam om att tidigt intressera sig för linjärt beroende. Bland pionjärerna kan nämnas Garrett Birkhoff, Takeo Nakasawa, Saunders Mac Lane och Bartel van der Waerden. Själv introducerades jag till teorin om matroider av Michel Pocchiola, emedan den ingår som ett moment i hans kurs Combinatoire et optimisation som jag läser nu under vårterminen. För den som är intresserad kan jag varmt rekommendera James Oxleys introduktion What is a matroid?, som finns fritt tillgänglig på hans hemsida.

Autoroute du Nord mot Bryssel

bruxelles_midi

I lördags morse tog jag spårvagnen från Cité Universitaire till Porte de Bagnolet varifrån jag promenerade den sista, korta biten längs Avenue Ibsen till busstationen Gare routière internationale de Paris-Gallieni. En stund senare satt jag på en buss på väg norrut längs Autoroute du Nord mot Bryssel, för att spendera helgen hos en släkting som bor och jobbar där.

Bussresan tog närmare fyra timmar, och den tiden ägnade jag åt att sätta mig in i några bevis som figurerar i de kurser som jag för närvarande läser. Bland annat kikade jag på ett bevis av Riemann-Rochs sats samt ett bevis av kvadratiska reciprocitetssatsen via gaussummor.

Bryssel bjöd på god mat, trevligt sällskap och förrädiskt aprilväder med sol, regn och hagel om vartannat. Resan hem, som jag företog idag efter lunch, blev dock inte lika produktiv som utresan: efter att förstrött ha bläddrat lite i en bok om talteori lät jag mig vaggas till sömns av den gungande bussen, som i rask fart forsade fram genom ett regnigt Flandern på väg mot Paris.

Marathon de Paris

För en vecka sedan (söndagen den 3:e april) gick startskottet för Marathon de Paris. Jag var en av tusentals anmälda löpare (omkring 57 000 anmälda, varav över 41 000 kom till start), och hade följaktligen snörat löparskorna på morgonen och tagit linje 4, därefter linje 6, från Porte d’Orléans till Charles de Gaulle – Étoile, för att sedan knata ner till startområdet mitt på Champs-Élysees och leta reda på mitt startled. Vädret var utsökt och publikstödet gick knappast att klaga på, men dessvärre hade något jävulskap satt klorna i mig dagarna innan, och kroppens krafter var som bortblåsta. Det som var tänkt som en hyggligt rask och åtminstone någorlunda dräglig färd längs stadens gator förvandlades snabbt till en utdragen kamp för att över huvud taget nå fram till målområdet. Efter målgången kändes det hur som helst bra att ha genomfört loppet, och jag tröstade mig med att den långsamma tiden i alla fall till viss del vägdes upp av att jag vunnit en (åtminstone i sammanhanget) ny erfarenhet: ibland går det inte riktigt som man har tänkt sig.

Veckan som gått sedan loppet har bjudit på fortsatt fint väder. Våren är nu här i full kraft, och i parker och på uteserveringar njuts det till fullo under vårsolens värmande lampa. Även jag, som vanligtvis föredrar vinterhalvåret, har uppskattat väderomslaget. För mycket kan sägas om Paris, men påstår man att staden bjuder på fina vintrar, då får man nog se över sina premisser!

Fjärilar, biljard och en triangulerad tjur

Idag gick jag på en lunchföreläsning på temat fjärilar och biljard. Den gavs av Jean-Pierre Marco som en del av UPMC:s föreläsningsserie Aromaths, och gav en kort introduktion till matematisk biljard och topologisk entropi i dynamiska system (därav kopplingen till fjärilar). Även om temat var något bekant sedan tidigare, så var föreläsningen i högsta grad en ögonöppnare.

För den som är road av djur och topologi kan jag vidare rekommendera ett besök på sidan Analysis Situs (uppkallad efter Henri Poincarés berömda artikel), som har som syfte att på ett pedagogiskt sätt illustrera och visualisera olika topologiska koncept. En av sidans höjdpunkter utgörs av en animation av en kompakt, triangulerad tjur, misstänkt lik skulpturen Charging Bull, som elegant reduceras till normalform för att enkelt kunna klassificeras. Den återfinns här.

Något om determinanter

Låt u_1=(1,2,\hdots,n)\in\mathbb{R}^n, och låt u_k=\pi_k\cdot u_1 för k=1,2,\hdots,n, där \pi_k\in S_n är den transposition som byter plats på elementen k och (k-1). Vi ska undersöka determinanten till den kvadratiska n\times n-matrisen U_n vars kolonnvektorer utgörs av u_1,u_2,\hdots,u_n. Några exempel får tydligaregöra konstruktionen:

U_3=\begin{pmatrix}1&2&1\\ 2&1&3\\ 3&3&2\end{pmatrix}, U_4=\begin{pmatrix}1&2&1&1\\ 2&1&3&2\\ 3&3&2&4\\ 4&4&4&3\end{pmatrix}, U_5=\begin{pmatrix}1&2&1&1&1\\ 2&1&3&2&2\\ 3&3&2&4&3\\ 4&4&4&3&5\\ 5&5&5&5&4\end{pmatrix}.

Innan vi gör något annat introducerar vi n\times n-matrisen A_n, som vi definierar enligt följande:

A_n=\begin{pmatrix}0&1&1& &1\\ 1&0&0&\hdots&0\\ 0&0&0& &0\\ &\vdots& &\ddots&\vdots\\ 0&0&0&\hdots&0\end{pmatrix} + \begin{pmatrix}1& & & & \\ -1&1& & & \\ &-1&1& & \\ & &\ddots&\ddots& \\ & & &-1&1\end{pmatrix}.

Att beräkna determinanten till A_n görs enkelt genom att alternerande laplaceutveckla längs första kolonnen och första raden. Man finner då att |A_n|=1. Vi kommer strax att ha nytta av detta resultat.

Åter till beräkningen av |U_n|. Vi konstaterar först att |U_1|=1. Låt därför n>1 och betrakta |U_n|. Radreducering ger oss följande identitet:

|U_n|=\begin{vmatrix}1&2&1& &1\\ 2&1&3&\hdots&2\\ 3&3&2& &3\\ &\vdots& &\ddots&\vdots\\ n&n&n&\hdots&n-1\end{vmatrix}=\begin{vmatrix}1&2&1& &1\\ 0&-3&1&\hdots&0\\ 0&-3&-1& &0\\ &\vdots& &\ddots&\vdots\\ 0&-n&0&\hdots&-1\end{vmatrix}.

Genom att laplaceutveckla determinanten längs den n:e raden ser vi att

|U_n|=n(-1)^{n+1}|A_n|-|U_{n-1}|=n(-1)^{n+1}-|U_{n-1}|.

Eftersom |U_1|>0 och n(-1)^{n+1} är positivt för udda n och negativt annars, så ser vi att |U_n| också är positiv för udda n och negativ annars, emedan n(-1)^{n+1} och -|U_{n-1}| alltid har samma tecken. Därav följer också att \text{abs}(|U_n|)=n+\text{abs}(U_{n-1}), d.v.s. \text{abs}(|U_n|) ges av den aritmetiska summan

1+2+3+\hdots+n=\dfrac{n(n+1)}{2}.

Vi kan därför slutligen konstatera att

|U_n|=(-1)^{n+1}\cdot\dfrac{n(n+1)}{2}.

Problemet att bestämma |U_n| är hämtat från en övningsuppgift från kursen Combinatoire et optimisation, som jag läser vid UPMC under våren 2015 och som ges av Michel Pocchiola.

 

Algebraisk topologi

covering_spaces

I fredags avslutades kursen Groupe fondamental et revêtements, 6 hp, med buller och brak med en tenta, som skrevs under tre timmar efter lunch. Som namnet antyder handlade kursen om algebraisk topologi, vilket innebär att man använder algebraiska metoder för att studera topologiska rum. Då fransmännen inte verkar ha för vana att studera generella topologiska rum på kandidatnivå (de lägger istället krutet på metriska rum) så inleddes kursen med en snabb genomgång av grundläggande definitioner och resultat, varefter fokus förflyttades till fundamentalgruppen och dess kopplingar till covering spaces (på franska revêtements, men något svenskt namn för dessa objekt har jag ännu inte sett). Kursen kulminerade sedan i ett bevis av Seifert-van Kampens sats, som är ytterst behjälplig då man behöver beräkna den till ett givet topologiskt rum hörande fundamentalgruppen.

Kursen gavs, som tidigare nämnts (se inlägget Vårens kursutbud), av Ilia Itenberg, som gjorde en förnämlig insats. Ilia sysslar annars med tropisk geometri, som kan beskrivas som algebraisk geometri med en twist (bildligt talat). För den intresserade kan jag rekommendera den korta introduktionen What is… a Tropical Curve av Grigory Mikhalkin. Ytterst behjälplig var också Maxim Wolff, som höll i kursens övningstillfällen. Maxim spenderade för övrigt ett utbytesår i Uppsala under sin studietid, och lärde sig algebraisk topologi av ingen mindre än Ryszard Rubinsztein.

Sammanfattningsvis måste jag säga att kursen gav mersmak. Algebraisk topologi är ett fascinerande ämne, och av naturliga skäl hinner man under en introduktionskurs bara skrapa lite på ytan. Men möjligheten att tänka och resonera visuellt, för att sedan befästa sina resonemang i algebraisk formalism, tilltalar mig starkt. Förhoppningsvis blir det mer av den varan framöver.