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.

Annonser

Återblick: terminsslut hösten 2015

Efter att ha satt min skrivare i arbete med att skriva ut ett kompendium om riemannytor, och efter att jag sedan i några minuter tankspritt stirrat ut genom fönstret bort mot platanerna som idag badar i eftermiddagssolen på andra sidan Avenue David Weill, så bestämde jag mig slutligen för att äntligen färdigställa min sammanfattning av höstterminen 2015 vid UPMC i Paris. Vad som kvarstår att berätta om är de sista veckorna innan jul; den period då de oundvikliga tentorna, som under hela hösten känts så avlägsna, plötsligt står för dörren, och det är dags att knyta ihop säcken och se efter vad det är man har lyckats fylla sitt huvud med under de gångna månaderna. Men allt i livet är inte tentor, och så var det inte heller i december 2015.

Kursen Algèbre géométrique avslutades med en gästföreläsning av Frédéric Jean (lärare vid ENSTA ParisTech) om en artikel vid namn La mécanique des sphères de Lie: un futur pour la CAO? (CAO är en förkortning av conception assistée par ordinateur, det vill säga det som på engelska kallas för computer aided design och vanligtvis förkortas CAD), som han skrivit tillsammans med Christian Arber (matematiker och mjukvaruutvecklare i CAD-branschen). Denna gästföreläsning föregicks av en förberedande föreläsning om Liegrupper och Liealgebror med fokus på den projektiva linjära gruppen SO^+(1,3) \cong PSL(2,\mathbb{C}).

Kursen Géométrie différentielle avslutades formellt med ett bevis av Stokes sats för glatta mångfalder, men fortsatte därefter med en semaine culturelle (kulturell vecka) som innefattade inspirerande och orienterande föreläsningar om sådana ämnen som förvisso är viktiga att känna till, men som av olika skäl inte hunnits med under de ordinarie föreläsningarna. Bland annat ägnades en sådan föreläsning åt en introduktion till de Rhamkohomologi.

Franskakursen FLR (Français langue étrangère) avslutades redan under första halvan av december med ett prov som omfattade en muntlig och en skriftlig del. För att bli godkänd på kursen krävdes även att man hade slutfört ett självständigt arbete, omfattande minst fyra timmar, vilket genomfördes på plats vid universitetet vid en passande tidpunkt som man själv bestämde, och som för min del gick ut på att skriva en sammanfattande och diskuterande text om Grand Paris, som är namnet på ett pågående projekt, lanserat 2007 av Nicolas Sarkozy, vars syfte är att öka sammarbetet mellan de olika administrativa enheter som utgör Parisområdet, bland annat i infrastrukturfrågor.

Veckan innan jul var det slutligen dags att skriva de två avslutande mattetentorna. Skrivtiden var i båda fallen satt till tre timmar. Den sista tentan skrev jag på förmiddagen fredagen den 18:e, och efter att jag lämnat in mina papper, samlat ihop mina pennor och borstat bort suddgummiresterna från bordet, kunde jag pusta ut tillsammans med två kursare ut på en pizzeria tvärs över gatan från universitetsområdet. För dörren stod några veckors välbehövlig ledighet. Då som nu sken solen utanför fönstret.

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!

Återblick: oktober och november 2015

notre-dame_de_reims

Sent omsider har jag nu äntligen tagit mig tid att sitta ner för att skriva ytterligare några rader om hur min hösttermin 2015 vid UPMC förflöt. Jag har i ett tidigare inlägg kortfattat berättat om de första trevande veckorna, och har nu för avsikt att fortsätta min återblick med den del av terminen som varken kan kallas för början eller slut.

Efter att ha funnit mig tillrätta i mina nya omgivningar tog, som brukligt, vardagen vid. Samtliga tre kurser som jag läste sträckte sig över hela terminen, så förutom några duggor i slutet av oktober och mitten av november, samt återkommande inlämningsuppgifter i franskakursen (mestadels bestående av korta uppsatser), bestod veckorna mestadels av föreläsningar och studier på egen hand. Mellan föreläsningarna spenderade jag mycket tid i biblioteket MIR (Mathématiques-Informatique Recherche) och emellanåt promenerade jag i angränsande Jardin des Plantes för att samla tankarna, betrakta andra tankspridda flanörer, och följa höstens framfart i raderna av planteringar.

I månadsskiftet september-oktober hade jag det stora nöjet att stifta bekantskap med Institut Henri Poincaré (IHP) under konferensen New Spaces in Mathematics & Physics, där bland annat Roger Penrose höll ett mycket intressant föredrag om twistorteori. Penrose hade grävt fram en overheadprojektor som han manövrerade med van hand, och hans handritade overheadblad gav presentationen en personlig touch som nästan kändes lite exotisk och spännande i dagens alltmer digitala tillvaro (för den som är intresserad av Penroses overheadfärdigheter kan jag rekommendera att kasta ett öga på detta klipp, där han visar några fascinerande moirémönster). IHP ligger mycket nära UPMC både fysiskt, mindre än tio minuter till fots, och administrativt, då det drivs gemensamt av UPMC och CNRS som en école interne. Dess föreståndare är sedan 2009 den karismatiske Cédric Villani.

Jag hann även med att ta mig utanför Paris vid några tillfällen. Den andra helgen i oktober tog jag en buss till Reims, i hjärtat av champagnedistriktet, där jag, förutom att äta gott och spana in den berömda gotiska katedralen, sprang ett välarrangerat, men kuperat och jobbigt, maraton på söndagen (arrangemanget är återkommande och går under namnet Run in Reims). Naturligtvis bjöds det på champagne efter målgång! I början av november spenderade jag några sköna dagar i badorten Deauville vid Engelska kanalen, känd som favorittillflyktsort för välbärgade Parisare samt som inspirationskälla till den fiktiva orten Balbec i Marcel Prousts romansvit À la recherche du temps perdu.

På det matematiska planet fick jag under hösten möjlighet att ta mitt kunnande till helt nya nivåer. Tempot var högt och kurserna var innehållsrika och utmanande. Nya samband dök upp där jag minst anade dem, och jag fick anledning att damma av mängder av gamla färdigheter som legat i träda för att sedan genast kombinera dem på nya sätt. På så vis kunde jag under hösten befästa mina tidigare kunskaper genom att i olika konstellationer låta dem samspela för att lösa nya problem. Som ett i mängden av alla tänkbara exempel kan nämnas konstruktioner av kvotmångfalder genom gruppverkan. Överlag var det en mycket angenäm och inspirerande upplevelse, som därefter utan uppehåll har fortsatt under våren.

Här väljer jag att sätta punkt för dagen. Jag har för avsikt att inom kort avsluta min återblick av höstterminen 2015 i ett tredje och sista inlägg på temat.

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.