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.

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.

 

Kompletteringar i Cannes

cannes

Efter några grådaskiga veckor i Paris fick jag nog. Jag packade min ryggsäck och tog en nattbuss till Marseille varifrån jag tog tåget vidare till Cannes. Egentligen var beslutet att åka till rivieran inte riktigt så spontant som min inledande mening kanske antyder. Faktum är att jag redan för någon vecka sedan anmälde mig till Semi de Cannes, ett halvmaraton som anordnas i helgen i den klassiska semesterorten, och det är därför jag för några dagar har bytt min regniga, parisiska vardag mot en solig weekend vid Medelhavet. Den faktiska resplanen spikades dock först för ett par dagar sedan, och möjligen kommer en pågående strejk i Provence-Alpes-Côte d’Azur att ytterligare påverka hemresan. Det blir som det blir med det.

Under bussresan till Marseille gjorde jag ett tappert försök att sätta mig in i konstruktionen av de p-adiska talen, som för varje primtal p utgör en kroppsutvidgning av de rationella talen \mathbb{Q}, och som betecknas \mathbb{Q}_p. Närmare bestämt är \mathbb{Q}_p en komplettering av \mathbb{Q}, vilket innebär att man till \mathbb{Q} har lagt till alla de gränsvärden av rationella talserier som inte själva är rationella. Givet standardmetriken på \mathbb{Q}, d.v.s. metriken som ges av d(x,y)=|x-y|, så utgörs kompletteringen av de rationella talen av de reella talen \mathbb{R}. I fallet med de p-adiska talen ger man istället \mathbb{Q} en metrik baserad på det så kallade p-adiska absolutbeloppet, betecknat |.|_p. Den p-adiska metriken d(x,y)=|x-y|_p har egenskapen att x och y ligger nära varandra om deras differens är delbar med p^k för ett stort heltal k. Den är en så kallad ultrametrik, vilket innebär att triangelolikheten i ett rum utrustat med den p-adiska metriken kan ersättas med den starkare olikheten d(x,z)\leq\text{max}\{d(x,y),d(x,z)\}. Detta får ett antal intressanta geometriska följdverkningar. Bland annat är alla trianglar i ett ultrametrisk rum likbenta och varje punkt i en cirkel är dess centrum.

De p-adiska talen har tillämpningar i talteori, där exempelvis Hasse-Minkowskis sats kan användas för att avgöra huruvida vissa diofantiska ekvationer är lösbara. Av den anledningen figurerar de i kursen Théorie des nobres, som jag läser under våren.

Mousse au chocolat

På UPMC hålls en gång i månaden en timmeslång lunchföreläsning i matematik där en inbjuden talare berättar om något intressant ämne på ett sätt som kan tänkas tilltala en bred publik utan särskilda förkunskaper, gärna med en liten twist. Syftet är att inspirera och väcka intresse, och målgruppen är företrädesvis mattestudenter på alla nivåer. Föreläsningsserien går under namnet Aromaths, och under hösten 2015 har ämnen som gorillor och kvadratiska former samt differentialgeometri och arkitektur tagits upp. Förra veckan var det dags för vårens första lunchföreläsning. Juliette Bavard, doktorand på UMPC vars forskningsområde innefattar bland annat lågdimensionell topologi och geometri, höll i rodret, och hon bjöd på en mycket intressant föreläsning på temat hur tillagning av chokladmousse kan förstås från ett topologiskt perspektiv.

Detta tema faller under det relativt nya ämnet topological fluid dynamics, vars mål, föga överraskande, är att studera de topologiska egenskaperna hos fluider (såsom chokladmousse) i rörelse. Tänk dig att du ska vispa chokladmousse. Till din hjälp har du en elvisp. Hur ska elvispens två vispar snurra för att på bästa sätt blanda chokladmoussen? Åt samma håll, eller åt olika håll?

Kanske var det liknande funderingar som manade Philip Boyland, Hassan Aref och Mark Stremler att tillsammans knåpa ihop den fascinerande artikeln Topological fluid mechanics of stirring, som publicerades i Journal of Fluid Mechanics år 2000 och från vilken Juliette hämtat delar av materialet till sin lunchföreläsning. Här beskrivs på ett översiktligt och lättillgängligt sätt, med flertalet illustrationer och utan att fastna i tekniska detaljer, hur topologin hos en yta under omrörning kan förstås genom att betrakta  topologiska flätor, samt genom att tillämpa Thurston-Nielsens klassifikationssats. Tanken är att man utgår från en stor disk D i vilken man placerar n vispar V_1,V_2,\hdots,V_n i form av små diskar, som sedan rör sig kontinuerligt i D (detta är själva omrörningen). Låt således V_{i,t} \subset D beteckna den plats som V_i upptar vid tidpunkten t \geq 0. Vi ställer kravet att V_{i,t} \cap \partial D = \emptyset och V_{i,t} \cap V_{j,t} = \emptyset för alla i, j \in \{ 1, 2, \hdots, n \} och för alla t \geq 0. Vår fluid är den yta i D som inte upptas av visparna, det vill säga X_t = D \setminus (V_{1,t} \cup V_{2,t} \cup \hdots \cup V_{n,t}). Vi kräver av fluiden att en punk som vid t = 0 ligger an mot antingen D eller någon av visparna, också kommer att göra det vid alla t>0 (fluiden kommer alltså att följa med visparna när de rör sig run i D). Själva omrörningen betraktas sedan som en homeomorfism från X_0 till X_t. Man begränsar sig sedan till att studera isotopiklasser av sådana homeomorfismer.

Gauss-Lucas sats

Ett intressant resultat om rötterna till polynom med komplexa koefficienter, kallat Gauss-Lucas sats, är att, givet ett icke konstant polynom P \in \mathbb{C} [X]\; av grad n vars (icke nödvändigtvis distinkta) rötter är z_1,z_2,\hdots,z_n\; så återfinns samtliga rötter till dess derivata P' i det konvexa höljet \text{Conv} (\{z_1,z_2,\hdots,z_n\}) av P:s rötter. Gauss-Lucas sats har uppenbara likheter med Rolles sats, som i sin tur är ett specialfall av medelvärdessatsen. Observera dock att Rolles sats och medelvärdessatsen inte håller för komplexvärda funktioner.

Jag blev bekant med Gauss-Lucas sats efter att dess bevis figurerat som en övningsuppgift i kursen Algèbre géométrique som jag läste under hösten 2015, och fattade genast tycke för den (antagligen just för att den har en så tydlig geometrisk tolkning).

Bevis

Algebrans fundamentalsats låter oss skriva P=c\cdot\Pi_{i=1}^n (z-z_i). Vi tar logaritmen och deriverar, och erhåller då

\frac{P'(z)}{P(z)} = \sum_{i=1}^n \frac{1}{z-z_i}.

Om z är en rot till P' som inte är en rot till P, så följer att

\frac{P'(z)}{P(z)} = \sum_{i=1}^n \frac{1}{z-z_i}=0 \;\Rightarrow\; \sum_{i=1}^n\frac{\overline{z}-\overline{z_i}}{|z-z_i|^2}=0.

Från detta följer att

\overline{z}\cdot\sum_{i=1}^n\frac{1}{|z-z_i|^2}=\sum_{i=1}^n\frac{\overline{z_i}}{|z-z_i|^2},

och genom att stuva om lite och konjugera båda leden ser vi att

z=\sum_{i=1}^n\left(\dfrac{z_i}{\sum_{j=1}^n\frac{|z-z_i|^2}{|z-z_j|^2}}\right).

Vi ser nu att z kan skrivas som summan \sum_{i=1}^n\alpha_i z_i, där 0\leq\alpha_i\; och \sum_{i=1}^n\alpha_i=1. Roten z till P' är således en konvexkombination av rötterna z_1,z_2,\hdots,z_n\; till P, vilket innebär att z \in \text{Conv} (\{z_1,z_2,\hdots,z_n\}).

Om, å andra sidan, z är en rot till P' som också är en rot till P, så ser vi genast att z \in \text{Conv} (\{z_1,z_2,\hdots,z_n\}).

\square