Lektioner 1 och 2 (3/11/00)

Målen med dagens lektioner är (i) att ge en översikt av hela kursen och ämnet som kallas för ‘talteori’, (ii) att bevisa aritmetikens fundamental sats.

Vi slösar inte bort någon tid med att diskutera Peano’s axiom för aritmetik, men nöjer oss med en intuitiv beskrivning av heltalen Z. Den algebraiska strukturen hos Z sammanfattas med

Proposition 1. (Z, +, ×) är en kommutativ ring med enhet.

De naturliga talen N har en viktig mängd-teoretisk egenskap som ofta utnytas i bevis inom talteori, nämligen

Faktum. N är välordnad.

Kom ihåg att en ordnad mängd kallas för välordnad om varje icke-tom delmängd har ett första element.

T.ex., induktion och Fermat’s metod av infinite descent beror på väl-ordningen av N.

Addition i Z är inte så ‘algebraiskt’ interessant, för Z genereras som en additiv grupp av ett enda element, nämligen 1 (eller -1). Multiplikation, däremot, är mycket mer fascinerande. Det mest fundamentala icke-triviala resultatet i talteori är

Aritmetikens fundamentalsats (Euclid). Det finns en delmängd P ⊂ N med följande egenskaper :

(i) Låt S ⊆ N. Varje element av N kan skrivas som en produkt av element från S om och endast om P ⊆ S.

(ii) Varje element av N har en unik representation som en produkt av element från P.

Talen i mängden P kallas för primtalen.

Bevis : Idéen bakom beviset är begreppet av dividerbarhet. Kom ihåg att talet a sägs dela talet b om det finns ett tal c så att b = ca. Man skriver a | b. Man säger lätt att (N, |) är en partiellt ordnad mängd. Euclid observerade att den faktiskt är ett gitter. Mer precist, bevisade han följande

Proposition 2. Låt a, b ∈ N. Då finns det (ett unikt) d ∈ N med följande två egenskaper :

(i) d | a och d | b. (ii) om c | a och c | b då måste c | d.

Dessutom är d det minsta positiva tal som kan uttryckas i formen

αa + βb

för något α, β ∈ Z.

Talet d kallas för den största gemensamma delaren (eng.: = greatest common divisor) av a och b och betecknas gcd(a, b), eller helt enkelt (a, b) när kontexten är klar. Det är en glb för a och b i po-mängden (N, |).

Man definierar på ett liknande sätt den minsta gemensamma multiplen (eng.: = least common multiple) av a och b som är en lub för a, b i gittret. Man bevisar lätt att

lcm(a, b) = \frac{ab}{gcd(a, b)}.  (1)

Det är naturligt att fråga hur många primtal det finns. I sin enklaste form, löstes detta problem redan av Euclid.

Sats (Euclid). Det finns oändligt många primtal.

Bevis : Som i boken, s. 4.

I detta läge är det naturligt att studera funktionen

π(x) = antal primtal ≤ x,  (2)

och försöka ge en precis beskrivning av funktionens beteende. Det tog 2000 år från Euclid’s tid för att ge en tillfredställande lösning av detta problem. Den är den ‘crowning achievement’ av 1800-talets talteori, när analytiska metoder först infördes för att attackera aritmetiska problem (se också Dirichlet’s sats nedan).

Primtalssatsen (Hadamard o. de la Vallée Poussin 1896).

π(x) = li(x) + O(xe^{−c\sqrt{log x}}),  (3)

där

li(x) = ∫_{2}^{x} \frac{dt}{log t} ∼ \frac{x}{log x}.  (4)

The proof uses extraordinary complex-analytical properties of the so-called Riemann zeta function, which is defined in a half-plane by the series

ζ(s) = ∑_{n=1}^{∞} \frac{1}{n^{s}} , Re(s) > 1.  (5)

In a groundbreaking and notorious paper from 1860 [1], Riemann showed how this function can be continued to a meromorphic function in the whole complex plane (with only a simple pole at s = 1) and that it satisfies a so-called functional equation, namely

π^{− \frac{s}{2}} Γ(\frac{s}{2})ζ(s) = π^{− \frac{1−s}{2}} Γ(\frac{1 − s}{2})ζ(1 − s).  (6)

The notoriety of the paper is due to the fact that in it Riemann made a conjecture about the zeroes of ζ(s) which remains unproven to this day, namely

Riemann hypothesis. If ζ(s) = 0, then either s = −2n for a non-negative integer n or Re(s) = 1/2.

The central importance of RH in number theory has only become clear over time. If we could prove it, or rather in many cases a generalistion of it called the generalised Riemann hypothesis (GRH), then many other impressive results would follow. The oldest of these is an improvement in the error term in the Prime Number Theorem, namely RH would imply that

π(x) = li(x) + O(x^{1/2} log x).  (7)

We may come back to these things later. We finish this section by mentioning two very famous unsolved problems, which also have something to do with the distribution of the prime numbers.

Twin primes conjecture. There exist infinitely many primes p such that p + 2 is also prime. More strongly, if π_{2}(x) denotes the number of such primes ≤ x, then

π_{2}(x) ∼ \frac{x}{log^{2} x}.  (8)

Goldbach conjecture. Every even number is the sum of two primes.

Most of the methods used to tackle these two problems can be brought under the heading of sieve methods. At their most basic, these are purely combinatorial methods, but at the more advanced level there is a lot of analysis. I hope we will have some time later to discuss at least some simple combinatorial sieves.

The crowning achievement so far of sieve methods is

Chen’s theorem (1974). (i) There are infinitely primes p such that p + 2 is either prime or a product of two primes. (ii) Every sufficiently large integer can be written as a sum of two numbers, one of which is prime and the other of which is either prime or a product of two primes.

Construction of prime numbers

One of the oldest problems in the study of primes has been the attempt to find some kind of formula for generating prime numbers. More precisely, we may seek a function f : N → N, which can be described as simply as possible, and such that f(n) is prime for all n. Two classic candidate functions were proposed by Fermat and Mersenne respectively. We denote them by f_{F} and f_{M} and they are given by the formulas

f_{F} (n) = 2^{2^{n}} + 1,  (9)
f_{M}(n) = 2^{p_{n}} − 1 (where p_{n} is the nth prime).  (10)

Motivation for these suggestions is provided by the following easy result

Proposition 3. (i) If x^{n} + 1 is prime then 2 | x and n is a power of 2. (ii) If x^{n} − 1 is prime then x = 2 and n is prime.

Fermat conjectured that f_{F} was always prime and it was one of his biggest mistakes because one can show by hand that 641 divides f_{F} (5).

Open Problem. Are there infinitely many n for which f_{F} (n) (resp. f_{M}(n)) is (not) prime ?.

Perhaps the simplest type of formula one can write down (at least if one is an algebraist !) is that given by a polynomial in one variable. However, the following is not hard to prove

Proposition 4. There is no polynomial f(x) with integer coefficients such that f(n) is prime for all n ∈ N^{1}.

Proof : A proof similar to the one I gave is on p.5 of the book.

On the other hand, Euclid’s theorem says that the polynomial f(x) = x generates infinitely many primes. That the same is true for any linear function (with certain restrictions) was first proven by Dirichlet :

Dirichlet’s theorem on AP’s (1837). Let f(x) = ax + b where a, b ∈ Z and (a, b) = 1. Then f(n) is prime for infinitely many n.

This is a huge result in number theory, not only because of its’ intrinsic interest, but because it was the first time that analytic methods were used in number theory and thereby it gave birth to a whole new field in mathematics. The objects studied by Dirichlet, namely the zeta function (later named after Riemann) and its’ generalisations, the so-called L-functions, are still of basic importance in the subject today. I hope to prove Dirichlet’s theorem in this course.

Wide open problem. Does there exist a polynomial f(x) of degree higher than 1, with integer coefficients whose gcd is 1, such that f(n) is prime for infinitely many n ?

Applied / algorithmic problems concerning primes

Primality testing : The problem is to find an efficient algorithm for deciding whether a randomly chosen positive integer n is prime. Most of the suggested algorithms basically rely on Fermat’s little theorem (which we’ll prove soon) and the concept of a pseudoprime. An algorithm is known which can be proven to run in polynomial time in log n provided that GRH is true ! We’ll come back to this.

1The situation is quite different for polynomials of many (at least 12) variables - see p.5 of book.

Factorisation : None other than Bill Gates is on record as having said that he thought the search for a fast algorithm for factoring large numbers was one of the most important problems in mathematics. The reason he said this is presumably because many public-key cryptosystems rely for their security on the assumption that no such fast algorithm is likely to be found in the near future. The most famous of these is the so-called RSA (= Rivest, Shamir and Adleman) system which dates from 1976 and is still in use today. We will talk more about cryptography during the course.

What’s there to study other than the primes ?

Well, there’s a lot, but much of the remaining research in number theory throughout history has been concerned with the problem of solving algebraic equations, specifically polynomial equations, in Z. It should come as no surprise that it is in tackling this problem that the subject nowadays known as algebraic number theory was developed.

To be precise, we are interested in solving equations

p(x_{1}, ..., x_{n}) = 0,  (11)

where p is a polynomial with integer coefficients. The case n = 1 is not very interesting but the case n = 2 already opens up a whole can of worms. To break the problem down into more manageable pieces, we first consider polynomials of low degree. For degree 1, things are still not interesting as equation (1) above can easily be used to prove

Proposition 5. The equation ax + by = c has a solution if and only if gcd(a, b) divides c.

For degree 2 though, there is an extensive theory usually referred to as Gauβ’ theory of binary quadratic forms. This theory takes up a substantial portion of Baker’s book^{2}.

2There is also an extensive theory for polynomials of degree 2 in more than 2 variables,

For degree higher than 2, there is the following famous theorem of the Norwegian mathematician Thue :

Thue’s theorem (1909). Let f(x, y) be a homogeneous polynomial with integer coefficients, of degree at least 3, and n ∈ Z. Then the equation f(x, y) = n has finitely many solutions.

Proof : Baker, section 8.2.

Thue’s result was extended by Siegel (1929) to cover all functions f(x, y) such that the associated projective curve f(x, y) = 0 over C has genus greater than 0. In particular it covers all functions f(x, y) = y^{2} − f(x), where f(x) is a polynomial with integer coefficients, of degree at least 3^{3}. Much later, Baker (1968) gave an ‘effective’ version of Thue’s theorem ; that is, he gave explicit upper bounds on |x|, |y| such that f(x, y) = n, which depended only on f. In practice, these bounds are generally too large to allow for the computation of all solutions, for a given f and n, but can be improved in specific cases.

The methods employed by all these authors use techniques of so-called Diophantine approximation which, informally, is the study of how well one can approximate a given irrational number by rationals ; that is, you want to get as close as possible to the irrational number while the denominators of your rationals grow as slowly as possible. Embedded in this subject is the very old conept of continued fractions. A very extensive introduction to this area is given in Chapter 6 of Baker’s book.

One such type of equation which has received an enormous amount of attention is the equation

y^{2} + a_{1}xy + a_{3}y = x^{3} + a_{2}x^{2} + a_{4}x + a_{6}.

The associated projective curve over C is called an elliptic curve, and has genus 1. In fact, every curve of genus 1 is given by such an equation, called a Weierstraβ equation. There is a voluminous literature about elliptic curves. Much of this deals, not only with the study of solutions over Z, but over Q or more general fields. While there are usually no longer finitely many solutions in these cases, there turns out to be a tremendous amount of interesting mathematical structure. For example, the points (x, y) on an elliptic curve, where x, y belong to any given field, can be ‘added’ in such a way that they form an abelian group. There is the famous theorem of Mordell and Weil (1920s) which says that, in the case of Q, this group is finitely-generated. We will not have time in this course to study elliptic curves - a proper study would require a full course in itself, and would draw on methods from several fields : number theory, algebraic geometry, complex analysis and topology.

but the results are not complete. If you’d like to hear more about this you should come to my graduate course.

3In separate work during the 1940s, Siegel used complicated analytical methods to study solutions of quadratic equations (genus 0 curves), and his methods actually apply to any number of variables. We’ll come back to this later.

By the way, the study of polynomial equations over Q instead of just Z turns out to be fruitful in other instances also. Most notable is the case of quadratic forms (in any number of variables). There is the classic theorem of Hasse and Minkowski (1930s) which, in essence, says that solving a quadratic equation over Q is equivalent to solving a finite list of congruences. Once again, the interesting thing here is the algebraic structure, since there’s no issue of actually ‘counting’ solutions. We’ll say more about this when we come to study binary quadratic forms, though the H-M theorem applies to forms in arbitrarily many variables.

For more than 2 variables, a certain amount is known in degree 2 (quadratic forms), as has already been indicated above. For degree higher than 2, very little is known in general, but there are many famous results (and problems) of a seemingly isolated nature. We mention only two of the most famous here :

Waring’s Problem. For each n there exists k_{n} >> 0 such that every positive integer can be written as the sum of no more than k_{n} nth powers.

The case n = 2 of this theorem was already solved by Lagrange in 1770 (the same year that the problem was stated), who proved that k_{2} = 4. It is perhaps his most famous result. The first general solution was given by Hilbert in 1909 and a later solution by Hardy and Littlewood (1920s) used the so-called circle method of analytic number theory, which has proved a very useful tool for the unravelling of many other problems.

Fermat’s Last Theorem. If n > 2 and x^{n} + y^{n} = z^{n} then xyz = 0.

Fermat himself actually wrote down a proof for the case n = 4 and it is a famous example of the use of his method of infinite descent. The case n = 3 was settled by Euler, and the ideas in his proof initiated the use of algebraic methods to tackle the problem, namely the development of the theory of finite field extensions of Q (what is now called algebraic number theory). The pinnacle of success for these methods was reached by Kummer in 1850 who used the theory of so-called cyclotomic fields (fields of the form Q(ζ) where ζ is a root of unity) to prove FLT for so-called regular primes^{4}.

As everyone knows, the eventual proof of Fermat’s theorem, accomplished by Wiles in 1994, employs rather different methods. It exploits some deep connections between two apparently quite different types of mathematical objects, namely modular forms and the aforementioned elliptic curves. The relevant connections were formally summarised in a conjecture of Shimura, Taniyama and Weil from the late 1960s. In the mid 1980s, work of Frey, Serre and Ribet established that FLT would follow from the STW conjecture. It then took Wiles eight years to prove the latter (for semistable elliptic curves).

What else ?

We mention two things :

Transcendental numbers : A complex number is called transcendental if it does not lie in any finite field extension of Q. Otherwise it is called algebraic, because in that case it is a root of some polynomial with rational coefficients. There are many classic problems (both solved and unsolved) surrounding the issue of whether certain numbers are transcendental or algebraic. Two of the most famous transcendental numbers are e and π. Two of the most famous numbers which are not known to be either transcendental or algebraic are Euler’s constant γ and the value ζ(3) of the Riemann ζ-function. A famous result of Lindemann (1844) gave a general method for constructing transcendental numbers (though it doesn’t work for e or π !). Lindemann’s theorem is about Diophantine approximation of algebraic numbers, and is also the basic ingredient in the proof of Thue’s theorem mentioned above. The improvements on Thue’s theorem by Siegel et al also rely on corresponding improvements on Lindemann’s theorem.

4This material is discussed well in, for example, the book of Stewart and Tall. I don’t know yet how much of it we will have time to do.

Combinatorial number theory : There are many interesting problems about whole numbers of a purely combinatorial flavour (see [2]). At this point, we mention just one such open problem, due to Paul Erdös, and worth 500 to the solver :

Open problem. There exists an absolute constant C > 0 such that if S ⊆ {1, ..., N} is such that all subset-sums from S are distinct, then |S| ≤ log_{2} N + C.

The trivial lower bound for C is C = 1, as is seen by considering N = 2^{k} and S = {2^{j} : 0 ≤ j ≤ k}. In 1969, Conway and Guy found an example where C = 2. Nothing better is known !

References

[1] G. Riemann, Über die Anzahl der Primzahlen unter einer gegebenen Grösse, Gesammelte werke 145-155.

[2] Handbook of Combinatorics, North-Holland, 1995.

Lektion 3 (6/11/00)

En mycket effektiv algoritm för att beräkna gcd av två naturliga tal gavs redan av Euclid och kallas efter honom.

Euclid’s algoritm. Låt a, b ∈ N. Antag att b > a. Sätt r_{−1} = b, r_{0} = a. Definiera successivt en avtagande följd (r_{j}) av icke-negativa tal genom

r_{j−1} = q_{j}r_{j} + r_{j+1}, där 0 ≤ q_{j}, 0 ≤ r_{j+1} < r_{j}.  (12)

Låt k vara det första indexet så att r_{k} = 0. Då är gcd(a, b) = r_{k−1}.

Bevis : Ungefär som i boken, s.3.

Man kan visa att algoritmen har komplexitet O(log^{3} b). Komplexiteten av en algoritm är max. antalet så kallade bit operationer som behövs för att genomföra den. En algoritm som har polynom komplexitet i log av beloppet av dess inputs (? svenska) betraktas ‘bra’ eller ‘effektiv’. För en mer komplett introduktion till dessa idéer, se t.ex. boken ‘A course in number theory and cryptography’, av Neal Koblitz.

Kongruenser

När man letar efter heltalslösningar till en polynomekvation av formen (11), är det ett vanlig trick att först reducera ekvationen modulo n, för olika n, och i stället studera kongruenserna

p(x_{1}, ..., x_{n}) ≡ 0 (mod n).  (13)

Intuitivt är det klart att (13) är lättare att lösa än (11) för det finns bara ändliga många möjligheter för en lösning. Dessutom, om n är prim då har Z/nZ mer algebraisk struktur än Z, nämligen att den är en kropp (se nedan).

Visst finns det oändligt många ekvationer (13) svarande mot en enda ekvation av formen (11), men t.ex. om kongruensen inte har någon lösning för något n då har den urprungliga ekvationen ingen lösning heller. I den andra riktningen finns det också situationer där existensen av en lösning till kongruensen för varje n räcker till existensen av en lösning i Q, men inte nödvändigtvis i Z. Men även sådana satser brukar vara mycket svårare att bevisa. Den mest berömda är kanske Hasse-Minkowski satsen som säger att om p(x_{1}, ..., x_{n}) är en kvadratisk form, då har (11) en lösning i Q omm den har en lösning i R och en lösning modulo p för varje primtal p. För ett bevis av denna sats, se t.ex. Kap. IV av Serre’s bok ‘A course in arithmetic’.

Nu börjar vi från början.

Definition : Fixera n ∈ N. Låt a, b ∈ Z. Säg att a är kongruent till b modulo n, och skriv a ≡ b (mod n), om n | a − b.

Proposition 6. ≡ (mod n) är en ekvivalens relation på Z.

Ekvivalensklassen av ett tal x betecknas x̄. Mängden av ekvivalensklasser betecknas Z/nZ och dess element kallas för residue klasser modulo n. Det är lätt att se att

Z/nZ = {x̄ : 0 ≤ x < n}, #(Z/nZ) = n.  (14)

Proposition 7. Fixera n. Avbildningen x → x̄ är en surjektiv ring homomorfism från Z till Z/nZ med kärna nZ = {x ∈ Z : n | x}.

Låt R vara en ring med enhet. Kom ihåg att x ∈ R kallas för en unit om det finns y ∈ R så att xy = yx = 1. Mängden av units betecknas R^{×}. Den är en multiplikativ grupp. Låt nu R_{1}, ..., R_{n} vara ringar med enheter. Deras direkt produkt är en ring som, som en mängd, är den Cartesiska produkten av R_{i}, och där addition och multiplikation definieras komponentvis. Den betecknas ∏_{i} R_{i}.

Proposition 8. Låt x ∈ Z. Då är x̄ en unit i Z/nZ omm (x, n) = 1.

Korollarium 9. Z/nZ är en kropp omm n är prim.

Vi definierar

ϕ(n) := #(Z/nZ)^{×} = #{x : 0 ≤ x < n och (x, n) = 1}.  (15)

ϕ kallas för Euler’s ϕ-funktion. Under kommande lektioner skall vi studera den vidare. Den stora satsen för idag är Chinese Remainder Theorem (CRT). Låt n = ∏_{i=1}^{k} p_{i}^{α_{i}}. Då är

Z/nZ ≅ ∏_{i=1}^{k} Z/p_{i}^{α_{i}}Z,  (16)

där ≅ betyder isomorfism av ringar. Bevis : Mer eller mindre som i boken, s.19. Korollarium 10.

(Z/nZ)^{×} ≅ ∏_{i=1}^{k}(Z/p_{i}^{α_{i}}Z)^{×},  (17)

där ≅ betyder isomorfism av grupper. Bevis : Ett element av en direkt produkt av ringar är en unit omm alla dess komponenter är units.

I dagens lektion använder vi flera resultat från elementär gruppteori i bevisen av några satser. Eftersom det kan vara länge sedan några av er tog kursen Algebraiska Strukturer, först gör jag en lista här av de definitioner och resultat som vi behöver. Ni uppmuntras att kolla upp denna material innan kommande lektioner.

En kort återblick på lite gruppteori

(i) Låt G vara en ändlig grupp. Antalet element i G betecknas |G| och kallas för ordningen av G. Enhetselementet i G kan betecknas med e, men 1 är mer vanligt.

(ii) Låt x ∈ G. Eftersom G är ändlig, potenserna x^{n} kan inte alla vara olika element i G. Det följer att det finns n > 0 så att x^{n} = 1. Det minsta sådana n kallas för ordningen av x och betecknas ord(x). Tydligen är ord(x) ≤ |G|.

(iii) Lagrange’s sats säger att om H är en delgrupp av G, då är |H| en delare av |G|.

(iv) En grupp kallas för cyklisk om det finns x ∈ G så att varje element av G är någon potens av x. En sådan x kallas för en generator av G. Alltså är G cyklisk omm det finns x ∈ G med ord(x) = |G|.

(v) För varje n > 0 är den additiva gruppen i ringen Z/nZ en cyklisk grupp av ordning n som genereras av ¯1. Varje cyklisk grupp av ordning n är isomorfisk med Z/nZ så att man får prata om DEN cykliska gruppen av ordning n. Den betecknas oftast med antingen Z/nZ eller C_{n}.

(vi) För godtyckligt G och x ∈ G, potenserna av x utgör en delgrupp av G som betecknas < x > och kallas för den cykliska delgruppen genererad av x. Om vi tillämpar Lagrange’s sats till delgruppen < x > då ser vi att ord(x) är en delare av |G| för alla x ∈ G.

(vii) Den direkta produkten av grupper definieras som för ringar (se lektion 3). Alltså låt G_{1}, ..., G_{n} vara grupper. Deras direkt produkt är en grupp som, som en mängd, är den Cartesiska produkten av G_{i}, och där multiplikation definieras komponentvis. Den betecknas G_{1} × ... × G_{n} eller, mer concis ∏_{i=1}^{n} G_{i}.

(viii) Låt G vara en grupp. En delgrupp A ⊆ G kallas för en direkt faktor av G om det finns en delgrupp B av G så att G = A × B.

(ix) I en abelsk grupp betraktas oftast grupp operationen som en ‘addition’ i stället för en ‘multiplikation’. Dvs, man skriver 0 i stället för 1 för enhetselementet, och nx i stället för x^{n}.

(x) För ändliga abelska grupper har vi följande två fundamentala fakter. Den första brukar användas i beviset av den andra, faktiskt. Notera att Faktum 2 är en generalisering av CRT (se lektion 3), eftersom den ger den senare när G ≅ Z/nZ. Den kallas för den fundamentala satsen om ändliga abelska grupper.

Faktum 1 : Låt G vara en ändlig abelsk grupp och g ∈ G. Då är den cykliska gruppen < g > en direkt faktor av G omm, för varje n ∈ N och x ∈ G,

nx = g ⇒ x ∈ < g > och x = mg med mn ≡ 1 (mod ord(g)).

I så fall säger man att elementet g är inte dividerbar i G.

Faktum 2 : Varje ändlig abelsk grupp G är den direkta produkten av cykliska delgrupper av primpotens ordningar (det kan vara fler än en faktor för ett givet primtal p som delar |G|). Antalet faktorer och deras ordningar i en sådan faktorisering av G är unika.

Nu förtsätter vi med lektionen.

En välkänd faktum till från algebra är

Proposition 11. Den multiplikativa gruppen av en ändlig kropp är cyklisk.

Särskilt då ser vi från Korollarium 9 att (Z/pZ)^{×} är en cyklisk grupp av ordning p − 1 för varje primtal p. Gruppteori antyder direkt att

Fermat’s (lilla) sats. Låt p vara ett primtal och a ett heltal så att (a, p) = 1. Då är

a^{p−1} ≡ 1 (mod p).  (18)

Mer allmänt, om vi tillämpar samma gruppteoretiska idéerna till gruppen (Z/nZ)^{×} då får vi

Euler’s sats. Låt a, n ∈ Z med (a, n) = 1. Då är

a^{ϕ(n)} ≡ 1 (mod n).  (19)

Anmärkning : Talet n kallas för ett pseudoprimtal om

(x, n) = 1 ⇒ x^{n−1} ≡ 1 (mod n).  (20)

Det finns pseudoprimtal som inte är primtal (se supplementära övningarna). Från Euler’s sats, ser vi att n är ett pseudoprimtal om ϕ(n) | n−1, men detta villkor är inte nödvändigt. Å andra sidan är sådana tal ganska sällsynta. Därför finns det många primalitets provningar som börjar med att testa om (20) stämmer. Ganska effektiva algoritmer för att bestämma om ett givet tal är prim är kända, trots att de bästa algoritmerna antar GRH för deras maximal effektivitet. Se Koblitz’ bok för vidare diskussion.

Korollarium 10 reducerar problemet av att ange strukturen av (Z/nZ)^{×} som en abstrakt abelsk grupp till fallet där n är en primpotens. Följande sats löser då sista delen av problemet.

Sats 12. (i) Om p är ett udde primtal, då är (Z/p^{n}Z)^{×} cyklisk av ordning ϕ(p^{n}) = p^{n−1}(p − 1) för alla n.

(ii) (Z/2Z)^{×} = < ¯1 > ≅ C_{1}.

(Z/2^{n}Z)^{×} = < ¯−1 > × < ¯5 > ≅ C_{2} × C_{2^{n−2}}, för n > 1.

Bevis : För del (i) och n = 1 använder man Prop. 11. Annars samma idéer som i boken s.23-25, men notera att flera av de mer ‘gory’ detaljerna utelämnas där.

Följande klassiska faktum kan också bevisas mycket lätt med hjälp av gruppteori :

Proposition 13. Låt p vara ett udde primtal. Då har kongruensen x^{2} ≡ −1 (mod p) en lösning omm p ≡ 1(mod 4).

Bevis : En lösning finns omm \overline{−1} är en kvadrat i den multiplikativa gruppen (Z/pZ)^{×}. Men denna grupp är cyklisk av ordning p − 1 och \overline{−1} är ett element av ordning 2, så det är en kvadrat i gruppen omm (p − 1)/2 är ett jämt tal, dvs omm p ≡ 1 (mod 4).

Vi ger två klassiska tillämpningar av denna proposition (vars bevis inte finns i boken !).

Proposition 14. Det finns oändligt många primtal av formen 4n + 3.

Bevis : Idé : Låt N > 1 och m = (N!)^{2} + 1. Varje prim delare p av m satisfierar p > N och p ≡ 1(mod 4).

Notera att det är en övning på inlämningsuppgiften att bevisa samma sak för tal av formen 4n + 1. Alltså, kan vissa enkla fall av Dirichlet’s sats (se lektion 1) bevisas utan analytiska metoder. För fler exempel se boken ‘Theory of Numbers’ av W. Sierpiński.

Sats 15 (Fermat 1654). Låt p vara ett udde primtal. Ekvationen

x^{2} + y^{2} = p  (21)

har en lösning (x, y) ∈ Z^{2} omm p ≡ 1(mod 4).

Bevis : Om p ≡ 3 (mod 4), finns det ingen lösning, eftersom kvadraten av varje heltal är kongruent till 0 eller 1 modulo 4, så att en summa av två kvadrater är kongruent till 0,1 eller 2 modulo 4.

Antag nu att p ≡ 1 (mod 4). Enligt Prop. 13, finns det ett heltal x så att x^{2} ≡ −1 (mod p). Fixera ett sådant x och betrakta funktionen f : Z → Z som ges av

f(u, v) = u + xv.

Låt K = [\sqrt{p}] så att K < \sqrt{p} < K + 1. Det finns (K + 1)^{2} > p par (u, v) av heltal så att 0 ≤ u, v ≤ K. Alltså, måste det finnas två olika par (u_{1}, v_{1}), (u_{2}, v_{2}) så att

f(u_{1}, v_{1}) ≡ f(u_{2}, v_{2}) (mod p) ⇒ (u_{1} − u_{2}) ≡ −x(v_{1} − v_{2}) (mod p).

Låt a := u_{1} − u_{2}, b := v_{1} − v_{2}. Eftersom x^{2} ≡ −1 (mod p), har vi då att a^{2} + b^{2} ≡ 0 (mod p). Minst ett av a, b ≠ 0 - annars skulle (u_{1}, v_{1}) = (u_{2}, v_{2})

- så att a^{2} + b^{2} ≠ 0. Men eftersom alla u_{i}, v_{i} ligger i intervallen [0, K], måste då både a, b ligga i intervallen [−K, K], så att a^{2} + b^{2} ≤ 2K^{2} < 2p.

Därför, har vi bevisat att a^{2} + b^{2} är en multipel av p, och ligger strängt mellan 0 och 2p. Det följer att a^{2} + b^{2} = p.

Lektion 5 (10/11/00)

Definition : En funktion f : N → Z kallas för en aritmetisk funktion. Definition : En funktion f : N → C kallas för multiplikativ om

(m, n) = 1 ⇒ f(mn) = f(m)f(n).  (22)

Vi är interesserad av att studera multiplikativa aritmetiska (MA) funktioner. Korollarium 10 ger följande formel för Euler’s ϕ-funktion :

ϕ(n) = ∏_{p|n} (1 − \frac{1}{p}) .  (23)

Då ser man direkt att ϕ är MA. Aside : Det finns ett annat sätt att bevisa (23) som är ett mycket lätt exempel av en så -kallad sieve metod. Kom ihåg Inklusion-exklusion principen. Låt A_{1}, ..., A_{k} vara ändliga mängder. Då är

|A_{1} ∪ ... ∪ A_{k}| = ∑_{r=1}^{k}(−1)^{r−1} ∑_{1≤i_{1}< ... <i_{r}≤k} |A_{i_{1}} ∩ ... ∩ A_{i_{r}}|.  (24)

Om vi skriver n = ∏_{i=1}^{k} p_{i}^{α_{i}} då får man (23) genom att tillämpa I-E principen till mängderna

A_{i} = {x : 0 ≤ x < n, p_{i} | x},

eftersom

ϕ(n) = n − |A_{1} ∪ ... ∪ A_{k}|.

Vad man gör har kan beskrivas som att ‘sifting out’ de tal i intervallen [0, n) som inte är relativt prima med n. Nu förtsätter vi med att ge fler exempel av MA funktioner. Exempel 1 (dumma exempel) : f(n) = 0, f(n) = 1, f(n) = n^{k} för något fixerad k.

Exempel 2 : Den Möbius funktionen definieras genom

μ(n) = \{ \begin{matrix}1, & om n = 1. \\ 0, & om p^{2} | n för något primtal p. \\ (−1)^{k}, & om n = p_{1}...p_{k} för olika primtal p_{i}. \end{matrix} (25)

Notera att (23) kan skrivas i formen

ϕ(n) = ∑_{d|n} μ(d)\frac{n}{d}.  (26)

Exempel 3 : Vi definierar

τ(n) := ∑_{d|n} 1, σ(n) = ∑_{d|n} d.  (27)

Det är lätt att bevisa att dessa funktioner är multiplikativa. Det är också lätt att se att

τ(p^{α}) = 1 + α, σ(p^{α}) = \frac{p^{α+1} − 1}{p − 1}.  (28)

Exempel 4 : Om f är multiplikativ, så också är funktionen g som definieras av

g(n) := ∑_{d|n} f(d).

T.ex., om f(n) = n då är g(n) = σ(n). Om f(n) = μ(n) och ν(n) := ∑_{d|n} μ(n), då är ν multiplikativ och man bevisar lätt (se nästa anmärkning) att

ν(n) = \{ \begin{matrix}1, & n = 1. \\ 0, & n > 1. \end{matrix} (29)

Anmärkning : För att kunna beräkna en multiplikativ funktion f, räcker det att kunna beräkna den vid primpotenser, eftersom om n = ∏_{i} p_{i}^{α_{i}} då är

f(n) = ∏_{i} f(p_{i}^{α_{i}}).  (30)

T.ex., från (28) får vi då att

τ(n) = ∏_{p^{α}∥n}(1 + α), σ(n) = ∏_{p^{α}∥n} \frac{p^{α+1} − 1}{p − 1}.  (31)

Näst bevisar vi en sats som motiveras av exempel 4 ovan, men som gäller godtyckliga funktioner.

Sats (Möbius inversion formel). Låt f, g : N → C. Då är följande ekvivalenta

(i) g(n) = ∑_{d|n} f(d),

(ii) f(n) = ∑_{d|n} μ(d)g(\frac{n}{d}).

Bevis : Ungefär som i boken. Notera att funktionen ν från exempel 4 ovan spelar en central roll.

Om vi tillämpar inversion formeln till (26) då får vi att

∑_{d|n} ϕ(d) = n.  (32)

En mer imponerande tillämpning av formeln ges av problem 4 i de supplementära övningarna.

Ekvation (30) säger att en MA funktion f(n) kan skrivas som en produkt av ändligt många faktorer, en för varje primtal från någon mängd som beror på n. I (multiplikativ) analytisk talteori träffer man många ANALYTISKA funktioner f(s) som kan skrivas som en Oändlig produkt av faktorer, en för varje primtal från någon mängd (oftast mängden av ALLA primtal). Den mest berömda formeln av denna typ är

Sats 16 (Euler). Om Re(s) > 1, då är

\frac{1}{ζ(s)} = ∏_{p} (1 − \frac{1}{p^{s}} ) = ∑_{n=1}^{∞} \frac{μ(n)}{n^{s}}.  (33)

Bevis : Kommer nästa gång. För att förstå vad den oändliga produkten i (33) betyder, gå till s.23 av detta dokument.

Sats 16 är kanske det mest grundläggande resultatet i hela analytiska talteorin. Bland annat är det början av beviset av Dirichlet’s sats, så att vi kommer tillbaka till den senare. Just nu (dvs under nästa lektion) vill vi använda den för att bevisa den imponerande Sats 17 nedan. Först en definition :

Definition : Låt P vara en egenskap av oordnade par (p, q) av olika ickenegativa heltal. Vi definierar sannolikheten att ett sådant par har egenskapen P genom

Prob(P) := lim_{n→∞} \frac{antal par (p, q) som har egenskap P och så att p, q ≤ n}{\frac{1}{2}n(n + 1)},

om gränsvärdet existerar. Intuitivt är Prob(P) lika med sannolikheten att ett slumpligt valt par p, q av olika icke-negativa heltal har egenskapen P.

Sats 17. Låt P vara egenskapen ‘är relativt prima’. Då är Prob(P) = \frac{6}{π^{2}} .

Infinite products in complex analysis

I will only give the basic ideas without any proofs because we will only encounter essentially one simple example of an analytic function defined by an infinite product in this course. If you want to study the subject properly, please check out a good complex analysis text, for example Chapter 5 of the book by Ahlfors. In fact, if you want to study analytic number theory beyond the level of this course, you really should know everything in the first three sections of that chapter.

First, recall Weierstraβ’ theorem :

Theorem A. Suppose the sequence of functions f_{n}(z) is analytic in a domain Ω, that the sequence converges pointwise, and uniformly in each compact subset of Ω. Then f(z) := lim_{n→∞} f_{n}(z) defines an analytic function in Ω and f′_{n}(z) → f′(z), uniformly in compact subsets of Ω.

Weierstraβ’ theorem is usually applied to series whose terms are analytic functions. Uniform convergence of the series in compact sets is often easy to prove using, say, Weierstraβ’ own M-test. Let us state Weierstraβ’ theorem for series for completion^{5} :

Theorem A1. Suppose each of the functions f_{n}(z) is analytic in a region Ω and that the series

∑_{n=1}^{∞} f_{n}(z) := f(z)

converges pointwise in Ω and uniformly in compact subsets of Ω. Then the limit function f(z) is analytic in Ω and

f′(z) = ∑_{n=1}^{∞} f′_{n}(z),

where the right-hand side also converges uniformly on compact subsets of Ω.

For example, the Riemann ζ-function

ζ(s) = ∑_{n=1}^{∞} \frac{1}{n^{s}} ,

5It is worth noting that the analogue of Weierstraβ’ theorem in real analysis does NOT hold. See page 55 of my notes from flervariabelanalys (del 2) from last year.

is analytic in the half-plane Re(s) > 1 because each term in the series is obviously analytic, the series converges pointwise in the half-plane and uniformly in compact subsets of it, in fact in any smaller half-plane Re(s) ≥ 1 + δ where δ > 0. (You learned all this in flervariabelanalys). Furthermore, the series can be differentiated termwise so that

ζ′(s) = − ∑_{n=1}^{∞} \frac{log n}{n^{s}} (Re(s) > 1).

We now turn to infinite products. The following definition is not the most general one but is sufficient for our purposes.

Definition : Let (p_{n}) be a sequence of complex numbers, all different from zero. We define

∏_{n=1}^{∞} =^{def} lim_{N→∞} ∏_{n=1}^{N} p_{n},  (34)

provided that the limit exists and is different from zero (the value zero is excluded for technical reasons).

An obvious necessary condition for the convergence of an infinite product is that p_{n} → 1. It is therefore natural to write p_{n} = 1 + a_{n} and the product as ∏(1 + a_{n}). Another very natural thing to do, since we know everything about infinite series, is to take logarithms and consider the series

∑_{n=1}^{∞} log(1 + a_{n}),  (35)

where, by convention, we choose the principal branch of the logarithm at all times. The following result should come as no surprise :

Theorem B. The infinite product ∏_{n=1}^{∞}(1 + a_{n}) with 1 + a_{n} ≠ 0 converges iff the series (35) converges.

Definition : The infinite product ∏(1 + a_{n}) is said to converge absolutely if the series (35) converges absolutely.

From the formula

lim_{z→0} \frac{log(1 + z)}{z} = 1,  (36)

one easily derives

Theorem C. The infinite product ∏(1 + a_{n}) with 1 + a_{n} ≠ 0 converges absolutely iff ∑_{n=1}^{∞} |a_{n}| converges.

Now suppose we replace the complex numbers a_{n} by functions f_{n}(z), all analytic in some region Ω. Pointwise convergence of the infinite product

∏_{n=1}^{∞}(1 + f_{n}(z))  (37)

is defined in the same way as above, whenever 1 + f_{n}(z) ≠ 0 for all n and all z ∈ Ω. What about uniform convergence ?

Definition : The infinite product (37) is said to converge uniformly in a subset K of Ω if the series ∑ log(1 + f_{n}(z)) converges uniformly in K.

We have the following counterpart to Theorem C which is most often used in practice to check uniform convergence of an infinite product :

Theorem D. Suppose the functions f_{n}(z) are all analytic in a region Ω and that 1 + f_{n}(z) ≠ 0 for all n and all z ∈ Ω. Let K be a subset of Ω and suppose there exists C > 0, such that

\frac{1}{C} < |1 + f_{n}(z)| < C

for all z ∈ K. Then the infinite product (37) converges uniformly in K if and only if ∑ f_{n}(z) converges uniformly in K.

We also have a counterpart to Weierstraβ’ theorem.

Theorem E. Suppose f_{n}(z) is a sequence of functions each analytic a region Ω, that 1 + f_{n}(z) ≠ 0 for all n and all z ∈ Ω, and that the infinite product (37) converges pointwise in Ω and uniformly on compact subsets of Ω. Then f(z) := ∏(1 + f_{n}(z)) defines an analytic function in Ω.

Lektion 6 (13/11/00)

Bevis av sats 16 : Först bevisade vi att

(∑_{n=1}^{∞} \frac{μ(n)}{n^{s}}) · ζ(s) = 1,

genom att skriva

(∑_{n=1}^{∞} \frac{μ(n)}{n^{s}}) (∑_{n=1}^{∞} \frac{1}{n^{s}} ) = ∑_{n=1}^{∞} \frac{ν(n)}{n^{s}} = 1,

där ν(n) ges av ekv. (29). Näst bevisade vi att

\frac{1}{ζ(s)} = ∏_{p} (1 − \frac{1}{p^{s}} ) ,

genom att visa att, för varje N > 0,

[ ∏_{p≤N} (1 − \frac{1}{p^{s}} )] · ζ(s) = ∑_{p†n för alla p ≤ N} \frac{1}{n^{s}} .

Ett alternativt (som föreslagits av Dennis Eriksson under pausen !) är att använda binomial satsen som ger att

(1 − \frac{1}{p^{s}} )^{−1} = ∑_{m=0}^{∞} \frac{1}{p^{ms}} .

Då kan vi skriva den oändliga produkten som

∏_{p} ( ∑_{m=0}^{∞} \frac{1}{p^{ms}} ) ,

och om man multiplicerar ut detta ser man att man får, för varje n > 0, termen 1/n^{s} precis en gång. Bevis av sats 17 : Som i boken, s. 13-14.

En oändlig produkt över primtalen av formen (33) kallas för en Euler produkt. En serie av formen ∑_{1}^{∞} a_{n}/n^{s}, där a_{n} ∈ C, kallas för en Dirichlet serie. I (multiplikativ) analytisk talteori uppstår det överallt Dirichlet serier som kan uttryckas som en Euler produkt (vi skall se det viktigaste exemplet nedan). Först bevisar vi ett allmänt kriterium som garanterar att en Dirichlet serie har en Euler produkt utveckling :

Proposition 18. Låt (a_{n})_{1}^{∞} vara en följd av komplexa tal så att

a_{1} = 1 och a_{mn} = a_{m}a_{n} för alla m, n ≥ 1.  (38)

Då är

∑_{n=1}^{∞} \frac{a_{n}}{n^{s}} = ∏_{p} (1 − \frac{a_{p}}{p^{s}} )^{−1} ,  (39)

när som helst båda sidorna konvergerar och definierar analytiska funktioner.

Bevis : Det är exakt samma idé som i beviset av Sats 16.

Definition : Låt N ≥ 1. En grupp homomorfism

χ : (Z/NZ)^{×} → C^{∗}

kallas för en karaktär modulo N. χ kallas för icke-trivial om χ(x) ≠ 1 för något x ∈ (Z/NZ)^{×}. Notera att χ(x) måste a priori vara en ϕ(N):te enhetsrot.

Varje karaktär χ modulo N kan utvigas till en funktion χ̂ : Z → C genom att sätta

χ̂(n) = \{ \begin{matrix}χ(n̄), & om (n, N) = 1, \\ 0, & annars. \end{matrix} (40)

Funktionen χ̂ satisfierar (jämför med (38))

χ̂(1) = 1, χ̂(mn) = χ̂(m)χ̂(n) för alla m, n ≥ 1.  (41)

Definition : En Dirichlet serie av formen

L(s, χ) := ∑_{n=1}^{∞} \frac{χ̂(n)}{n^{s}},  (42)

där χ är en karaktär (för något N), kallas för en Dirichlet L-serie^{6}. Notera att om χ är den triviala karaktären modulo N = 1 (det finns bara den triviala karaktären modulo 1 !), då är L(s, χ) = ζ(s).

Sats 19. (i) Om χ är en trivial karaktär, då är L(s, χ) analytisk i Re(s) > 1.

(ii) Om χ är icke-trivial, då är L(s, χ) analytisk i Re(s) > 0.

(iii)

L(s, χ) = ∏_{p} (1 − \frac{χ̂(p)}{p^{s}})^{−1} ,  (43)

när båda sidor konvergerar enligt (i) eller (ii) resp.

Bevis : Beviset av (iii) följer direkt från (41) och Prop. 18. Beviset av (i) följer från jämförelse med ζ(s). För (ii) bevisar man först att, om χ är en karaktär modulo N, då är

∑_{n=1}^{N} χ̂(n) = \{ \begin{matrix}ϕ(N), & om χ är trivial, \\ 0, & annars. \end{matrix} (44)

Då tillämpar man Dirichlet’s kriterium för likformig konvergens tillsammans med Weierstraβ’ sats. Kom ihåg Dirichlet’s kriterium (från flervariabelanalys) :

‘Serien ∑_{1}^{∞} f_{n}(x)g_{n}(x) konvergerar likformigt i en mängd M om

(a) följden (g_{n}(x)) är avtagande för varje x ∈ M,

(b) g_{n}(x) → 0 likformigt i M,

(c) de partiella summorna F_{N}(x) := ∑_{1}^{N} f_{n}(x) är likformigt begränsade i M’.

Alltså, kvarstår det att bevisa (44). Eftersom χ är icke-trivial, finns det ett heltal y så att (y, N) = 1 och 0 ≠ χ̂(y) ≠ 1. När n går från 1 till N då löper yn över en komplett mängd av restklasser modulo N, ty (y, N) = 1.

6Jag tror att denna L betyder ‘Legendre’, eftersom i de första L-serierna som studerades av Dirichlet var karaktären en Legendre symbol (se lektion 7 nedan).

Då har vi att

∑_{n=1}^{N} χ̂(n) = ∑_{n=1}^{N} χ̂(yn) = χ̂(y) · ∑_{n=1}^{N} χ̂(n),

ty χ̂ är multiplikativ. Men χ̂(y) ≠ 0, 1 antyder då att summan över n måste vara noll, q.e.d.

Vi skall komma tillbaka till L-serier senare när vi diskuterar Dirichlet’s sats om primtal i aritmetiska följder.

Gauss’ teori av kvadratiska kongruenser

Tidigare bevisade vi följande två fakta :

(1) kongruensen x^{2} ≡ −1 (mod p) har en lösning omm p ≡ 1 (mod 4).

(2) x^{2} + y^{2} = p har en lösning omm p ≡ 1 (mod 4).

Dessa fakta var redan välkända mot slutet av 1600-talet, när Fermat var det stora namnet inom talteori (dvs inom matematik, modulo Newton osv !!). Det dröjade över 100 år innan arbetet av tre stora matematiker - Euler, Legendre och framför allt Gauβ - ledde till en stor generalisering av dessa två resultat, och öppnade vägen till vad som kallas nuförtiden för ‘algebraisk talteori’.

Ovanstående (1) och (2) är speciella fall av följande två problem resp.:

Problem 1 : Lös den allmäna kvadratiska kongruensen

ax^{2} + bx + c ≡ 0 (mod n).  (45)

Problem 2 : Lös (i heltalen) den allmäna kvadratiska ekvationen i två variabler

ax^{2} + bxy + cy^{2} + dx + ey + f = 0.  (46)

Problem 2 kallas för representationsproblemet för binära kvadratiska former. Båda problem kan, på ett naturligt sätt, ytterliggare delas upp i tre ‘subproblem’, nämligen Del A : ange allmäna kriteria för existens av en lösning.

Del B : ge effektiva algoritmer för att hitta en lösning.

Del C : ge allmäna (beräknabara) formler för antalet lösningar. Notera att i Problem 1 räcker det att hitta alla lösningar bland en mängd av representanter för Z/nZ. Därför är antalet lösningar alltid ändligt så länge som en ‘lösning’ betyder en lösning modulo n. Vi adopterar denna konvention framöver.

Under kommande lektioner skall vi studera dessa två problem mycket noggrant. Vi börjar med det kvadratiska kongruens problemet (Problem 1) och framför allt existens frågan (Del A). Men först, är det bra att satisfiera oss att vi förstår linjära kongruenser

Proposition 20. Kongruensen ax ≡ b (mod n) har en lösning omm (a, n) delar b.

I nästa två propositionerna reducerar vi den allmäna kvadratiska kongruensen till en mer hanterlig form.

Proposition 21. Kongruensen (45) är ekvivalent med kongruensen

y^{2} ≡ d (mod 4an),  (47)

där y = 2ax + b och d = b^{2} − 4ac.

Denna prop. säger att det räcker att betrakta kongruenser av formen x^{2} ≡ a (mod n). Nu kommer huvud reduktionssteget. Det är ganska tekniskt, men det är resultatet som är viktigt :

Proposition 22. (i) x^{2} ≡ a (mod n) har en lösning omm x^{2} ≡ a (mod p^{α}) har en lösning för varje p^{α}∥n.

(ii) Om a = p^{i}a_{1} för något i < α och (a_{1}, p) = 1, ett nödvändigt villkor för existens av en lösning till x^{2} ≡ a (mod p^{α}) är att 2 | i. I så fall ges lösningarna av x = p^{i/2}x_{1} där x_{1}^{2} ≡ a_{1} (mod p^{α−i}).

(iii) Om p > 2 och (a, p) = 1 då har x^{2} ≡ a (mod p^{α}) en lösning omm x^{2} ≡ a (mod p) har en lösning. Antalet lösningar är antingen 0 eller 2. (iv) x^{2} ≡ 1 (mod 2) har den enda lösningen x = {¯1}.

(v) x^{2} ≡ 1 (mod 4) har lösningarna x = ¯1, ¯3 och x^{2} ≡ 3 (mod 4) har inga lösningar. (vi) Om α ≥ 3 och 2 † a, då har x^{2} ≡ a (mod 2^{α}) en lösning omm a ≡ 1(mod 8), dvs omm a ≡ 5^{2λ} (mod 2^{α}) för något λ ≥ 0. I så fall finns det exakt 4 lösningar, nämligen ±x_{0}, ±5^{2^{α−3}}x_{0} där x_{0} ≡ 5^{λ} (mod 2^{α}).

Bevis av prop. 22 : Man använder CRT och Sats 12, och det hela är elementär gruppteori.

Nu har vi reducerat Problem 1 (Del A,B och C !) till att lösa kongruensen

x^{2} ≡ a (mod p),  (48)

där p är ett udda primtal och (a, p) = 1. Notera att Del C av problemet nu är trivialt - det finns antingen 0 eller 2 lösningar.

Notation : Låt p vara ett udda primtal och (a, p) = 1. Vi sätter

(\frac{a}{p}) := \{ \begin{matrix}1, & om (48) har en lösning, \\ −1, & annars. \end{matrix} (49)

Symbolen (\frac{a}{p}) kallas för en Legendre symbol.

Anmärkning : χ : a → (\frac{a}{p}) är en karaktär modulo p av ordning 2, en så-kallad kvadratisk karaktär.

Del A av Problem 1 frågar efter ett kriterium för existensen av en lösning till (48). Det enda som jag känner till är det nästan triviala

Euler’s kriterium. (\frac{a}{p}) ≡ a^{p−1/2} (mod p).

Bevis : (\frac{a}{p}) = 1 ⇔ ā är en kvadrat i (Z/pZ)^{×}.

Från den teoretiska synpunkten är detta kriterium ganska ointeressant, men från den praktiska vinkeln ger det ett effektiv sätt att lösa existens-frågan : det räcker att kunna beräkna a^{p−1/2} och det finns snabba algoritmer för att beräkna potenser av ett heltal (den klassiska använder en bas-2 utveckling av potensen).

Nu kommer vi till Gauβ’ reciprocitets lag. Den leder också till ett mycket effektivt sätt att lösa existens frågan för (48), men dess största interesse är teoretiskt. Först, är det klart att det är ett mycket vackrare och djupare resultat än Euler’s kriterium, men historien slutar inte där. Idag vet vi att Gauβ’ lag är ett specialt fall av en ‘reciprocitets lag’ av Artin (1927) som gäller för godyckliga abelska talkropps utvidningar L/K^{7}. I fallet K = Q och [L : Q] = 2 får man Gauβ’ lag. Artin’s reciprocitets lag är ett av de stora resultaten i den del av algebraisk talteori som kallas för class field theory, eller mer precist abelian class field theory^{8}.

Under 1900-talet har flera olika formuleringar av ‘class field theory’ utvecklats och vilken formulering du lär dig beror på vilken bok du läser. För en formulering i termer av så-kallade adèles och idèles (kanske den mest kända) se t.ex. [3]. För en alternativ formulering i termer av grupp kohomologi se t.ex. [4]. Den senare har också en kapitel om historien av ‘class field theory’.

Okej, tillbaka till jorden. Här är ‘what all the fuss has been about’ !

Sats (Gauss’ reciprocitets lag). Låt p, q vara udda primtal. Då är

(\frac{p}{q}) (\frac{q}{p}) = (−1)^{\frac{1}{4} (p−1)(q−1)}.  (50)

Bevis : Som i boken, s.28-30. Notera att beviset använder ett resultat av Gauβ som är interessant i sig själv, nämligen

Gauss’ lemma. Låt p vara ett udda primtal. För varje n ∈ Z, låt [n] beteckna det unika talet som satisfierar [n] ≡ n (mod p) och −\frac{1}{2}p < [n] < \frac{1}{2}p.

Låt nu (a, p) = 1 och sätt a_{j} = [aj] för varje j ∈ Z. Då är

(\frac{a}{p}) = (−1)^{l}

där

l = antalet j så att 1 ≤ j ≤ \frac{p−1}{2} och a_{j} < 0.

Anmärkning : Bokens bevis är ganska elementärt och mycket snyggt, och är ganska nära Gauβ’ ursprunlgiga idéer eftersom det använder hans lemma. Under sitt liv upptäckte Gauβ minst 8 olika bevis av sitt lag^{9}. Några av dessa har en lite mer analytisk inriktning, och beror på beräkningen av en typ av ändlig summa som kallas för en Gauβ summa. Summor av denna typ har visat sig uppstå i många olika sammanhang inom talteori (både algebraisk och analytisk), t.ex. i beviset av Dirichlet’s sats som kommer senare under kursen. Vi skall diskutera dem nästa gång.

7En kropp som är en ändlig utvidning av Q kallas för en talkropp. En utvidning av talkroppar L/K kallas för abelsk om den är Galois och Galois gruppen av L/K är abelsk.

8There is also a class field theory for non-abelian number field extensions, but it is much more difficult and highly incomplete.

9Moderna böcker betraktas innehålla ungefär 40 olika bevis. Men Urban Larsson påstår att det finns 196 stycken på nätet. Isn’t technology wonderful !

References

[3] S. Lang, ALgebraic number theory, Springer.

[4] J. Cassels and A. Fröhlich eds., Algebraic number theory, Academic Press 1967.

A little Fourier analysis

We will only state the bare minimum of information that we will require. People who have not taken a course in Fourier analysis may wish to consult a textbook on that subject for proofs and a fuller treatment, though I don’t believe it’s really necessary. Also, you have all already seen the basic Theorem A in flervariabelanalys, though without a proof (it is Sats 3.11 in the GLO kompendium).

Definition : A function f : R → R is said to be C^{1} if f is differentiable and both f and f′ are continuous.

Definition : A function f : R → R is said to be piecewise C^{1} if in every bounded open interval f is C^{1} except perhaps at a finite number of points where both f and f′ have both left- and right-hand limits.

The right- and left- hand limits of a function g at a point x are denoted g(x+) and g(x−) respectively. Hence g is continuous at x iff both limits exist and are equal.

Definition : A function f : R → R satisfying f(x + 1) = f(x) shall be called [0, 1]-periodic.

Definition : Let f be a [0, 1]-periodic Riemann integrable function. The Fourier series of f is the series

\frac{1}{2}a_{0} + ∑_{n=1}^{∞} (a_{n} cos 2πnx + b_{n} sin 2πnx) ,  (51)

where

\frac{1}{2}a_{0} = ∫_{0}^{1} f(x) dx,  (52)
\frac{1}{2}a_{n} = ∫_{0}^{1} f(x) cos 2πnx dx (n > 0),  (53)
\frac{1}{2}b_{n} = ∫_{0}^{1} f(x) sin 2πnx dx.  (54)

The fundamental result in Fourier analysis (first proved rigorously by Dirichlet in 1829) is the following Theorem A. Suppose f is piecewise C^{1} and [0, 1]-periodic. Then the Fourier series of f converges pointwise to \frac{1}{2}[f(x+) + f(x−)].

We are interested in an application of Theorem A. So now consider any piecewise C^{1} function f(x). Let f_{1}(x) be the unique [0, 1]-periodic function which coincides with f(x) for 0 ≤ x < 1. Note that f_{1} is also piecewise C^{1} because it may only pick up extra discontinuities at the integers. Applying Theorem A to the function f_{1} and evaluating at x = 0 we obtain

\frac{1}{2} [f(0) + f(1)] = \frac{1}{2}a_{0}+∑_{n=1}^{∞} a_{n} = ∑_{n=−∞}^{∞} ∫_{0}^{1} f(x) cos 2πnx dx = ∑_{n=−∞}^{∞} ∫_{0}^{1} f(x)e^{2πinx} dx,

(55)

where, to get the 2nd last equality, we have used the evenness of the cosine function, and to get the last equality oddness of the sine function.

If, for some integer t, we replace f(x) by f(x + t) and repeat the above argument, then we obtain

\frac{1}{2} [f(t) + f(t + 1)] = ∑_{n=−∞}^{∞} ∫_{t}^{t+1} f(x)e^{2πinx} dx.  (56)

Now let A, B be integers with A < B. Adding together both sides of (56) for n = A, A + 1, ..., B − 1 we obtain

∗ ∑_{t=A}^{B} f(t) = ∑_{n=−∞}^{∞} ∫_{A}^{B} f(x)e^{2πinx} dx,  (57)

where ^{∗} ∑ means that the end terms of the sum, corresponding to t = A and t = B, are to be replaced by \frac{1}{2}f(A) and \frac{1}{2}f(B).

We shall use (57) in the evaluation of a Gauβ sum next time. It is also worth remarking that (57) is a special case of the well-known Poisson summation formula.

Först noterar vi en snygg konsekvens av Gauβ’ lemma :

Proposition 23. Låt p vara ett udde primtal. Då är

(\frac{2}{p}) = (−1)^{\frac{1}{8} (p^{2}−1)} = \{ \begin{matrix}1, & om p ≡ ±1 (mod 8), \\ −1, & om p ≡ ±3 (mod 8). \end{matrix} (58)

Bevis : Som i boken, s.29.

Målet är nu att beskriva ett nytt effektivt sätt att beräkna Legendre symboler (dvs ett alternativ till Eulers kriterium), samt införa en bekväm (convenient) notation. Idéen är att utviga Legendre symbolen, på ett ‘formelt’ sätt, till udda, icke-prima moduli, så att en analog av reciprocitetslagen fortfarande stämmer.

Definition : Låt n vara ett udda positivt heltal, n = ∏_{i} p_{i}^{α_{i}}, och a ett heltal med (a, n) = 1. Då definierar vi den så kallade Jacobi symbolen (\frac{a}{n}) genom

(\frac{a}{n}) := ∏_{i} (\frac{a}{p_{i}} )^{α_{i}} .  (59)

Notera följande :

(i) Om n är ett primtal, då får vi tillbaka den vanliga Legendre symbolen. (ii) χ : a ↦ (\frac{a}{n}) är en karaktär modulo n av ordning 2. Speciellt kan vi utvidga symbolen till en multiplikativ funktion på Z genom att sätta

(\frac{a}{n}) := 0, om (a, n) > 1.  (60)

(iii) För godtyckliga n, a med (a, n) = 1, om (\frac{a}{n}) = −1 då är x^{2} ≡ a (n) ej lösbar. Detta generaliserar motsvarande egenskapen hos Legendre symboler. (iv) MEN, om (\frac{a}{n}) = 1 det betyder INTE nödvändigtvis att x^{2} ≡ a (n) är lösbar. Exempel : (\frac{−1}{9}) = 1 men x^{2} ≡ −1 (9) har ingen lösning. Alltså är det bäst att tänka på Jacobi symbolen som en ‘formel’ utvidning av Legendres symbol. Dess användbarhet kommer från följande fakta :

Sats. Låt m, n vara udda tal, med n > 0 och (m, n) = 1. Då har vi (i)

(\frac{−1}{n}) = (−1)^{\frac{1}{2} (n−1)} = \{ \begin{matrix}1, & om n ≡ 1 (mod 4), \\ −1, & om n ≡ 3 (mod 4). \end{matrix} (61)

(ii)

(\frac{2}{n}) = (−1)^{\frac{1}{8} (n^{2}−1)} = \{ \begin{matrix}1, & om n ≡ ±1 (mod 8), \\ −1, & om n ≡ ±3 (mod 8). \end{matrix} (62)

(iii)

(\frac{m}{n}) (\frac{n}{m}) = (−1)^{\frac{1}{4} (m−1)(n−1)}.  (63)

Notera att denna sats generaliserar motsvarande fakta då m, n är primtal. Bevis : Som i boken, s.32. Man använder följande lemma Lemma : Om n_{1}, ..., n_{k} är udda tal, n = ∏_{i} n_{i}, då är

\frac{1}{2}(n − 1) ≡ ∑_{i=1}^{k} \frac{1}{2}(n_{k} − 1) (mod 2).  (64)

Bevis av lemma : Induktion på k efter ett direkt bevis för k = 2 med hjälp av identiteten

n_{1}n_{2} − 1 = (n_{1} − 1)(n_{2} − 1) + (n_{1} − 1) + (n_{2} − 1).

Denna sats ger en effektiv algoritm för att beräkna Jacobi symboler (och speciellt, Legendre symboler). Repeterad tillämpning av (63) och disivion algoritmen reducerar beräkningen av (\frac{m}{n}), efter ändligt många steg, till en symbol av formen (\frac{−1}{n_{1}}) eller (\frac{2}{n_{1}} ), som kan beräknas direkt med (61), resp. (62).

Gauss summor

Definition : Låt q > 0, χ en karaktär modulo q. Summan

G(χ) := ∑_{m=1}^{q−1} χ(m)e^{2πim/q}  (65)

kallas för en Gauβ summa (modulo q).

Gauβ summor, eller ändliga summor av mer allmän ‘exponentiell typ’, uppstår i många olika sammanhang inom talteori. Vi skall se några exempel så småningom. Exakta beräkningar av sådana summor är i stortsett omöjliga och man måste nöja sig med ganska bra uppskattningar. Men det finns en viktig situation där summan kan beräknas exakt, nämligen när q är ett primtal och χ en kvadratisk karaktär modulo q, dvs en Legendre symbol. Nu koncentrerar vi oss på denna situation.

Notation : e_{q}(m) := e^{2πim/q}. Notera då att e_{q}(m_{1} + m_{2}) = e_{q}(m_{1})e_{q}(m_{2}).

Fixera nu ett udda primtal q. Vi är interesserade av att beräkna summan

G := ∑_{m=1}^{q−1} (\frac{m}{q}) e_{q}(m).  (66)

Det visar sig vara mycket lättare att i stället beräkna G^{2}. Vi har

Proposition 24. Låt G ges av (66). Då är

G^{2} = \{ \begin{matrix}q, & om q ≡ 1 (mod 4), \\ −q, & om q ≡ 3 (mod 4). \end{matrix} (67)

Bevis : Se kap.2 av den utdelade stencilen från Davenports bok [5].

Ekv. (67) räcker för att skaffa ett alternativt bevis av Gauβ’ reciprocitetslag - se den utdelade stencilen från Koblitz’ bok. Notera att den ger |G| = \sqrt{q} och G själv upp till ett tecke. Men det finns tillämpningar - t.ex. i Dirichlets bevis av sin sats om primtal i aritmetiska följder - där kunskapen av tecken är viktig, och detta visar sig faktiskt vara mycket svårare att reda ut. Det är här man kan använda lite fourieranalys. Resultatet är

Sats 25 (Gauss/Dirichlet).

G = \{ \begin{matrix}\sqrt{q}, & om q ≡ 1 (mod 4), \\ i\sqrt{q}, & om q ≡ 3 (mod 4). \end{matrix} (68)

Bevis : Se kap.2 av samma stencil från Davenports bok.

References

[5] H. Davenport, Multiplicative number theory, Springer 1980.

Dirichlet’s theorem

In today’s class we began the proof of the following fantastic result :

Theorem (Dirichlet 1837). Let a, q > 0 with (a, q) = 1. Then there are infinitely many primes p such that p ≡ a (mod q). Moreover,

∑_{p≡a (mod q)} p^{−1} = +∞.  (69)

Here I’m going to outline the main steps in the proof of this theorem. More details can be found on the handout I gave from Davenport’s book.

Step 1. Some time around 1800, Euler gave an ‘analytic’ proof of Euclid’s ancient theorem that there are infinitely many primes. More precisely, he proved

Theorem 26. There are infinitely many primes and the sum of their reciprocals diverges.

Proof : The starting point is the infinite product for the ζ-function (see p.21), valid when Re(s) > 1, namely

ζ(s) = ∏_{p} (1 − \frac{1}{p^{s}} )^{−1} .  (70)

Taking log of both sides^{10} we get, for Re(s) > 1,

log ζ(s) = − ∑_{p} log (1 − \frac{1}{p^{s}} ) .  (71)

Next recall that the Taylor series for the log function, valid when |z| < 1, is given by

− log(1 − z) = ∑_{m=1}^{∞} \frac{1}{m}z^{m}.  (72)

10At all times, unless otherwise stated, we are using the principal branch of the log function.

Substituting (72) into (71) we get, also for Re(s) > 1,

log ζ(s) = ∑_{p} ∑_{m=1}^{∞} \frac{1}{mp^{ms}} .  (73)

Now group the terms on the rhs into two groups, those with m = 1 and those with m > 1. Note that we are changing the order of summation here, but that is okay because the series is absolutely convergent when Re(s) > 1^{11}. We obtain

log ζ(s) = ∑_{p} p^{−s} + ∑_{p} ∑_{m=2}^{∞} \frac{1}{mp^{ms}} .  (74)

The idea now is to look at what happens when s → 1^{+}. The sum over m ≥ 2 does not blow up - in fact, it’s value at s = 1 can easily be shown to be less than, for example, 2ζ(2) = π^{2}/3. On the other hand, we all know from envariabelanalys (use, say, the integral test) that ζ(s) → +∞ as s → 1^{+}. This means that the lhs of (74) goes to infinity as s → 1^{+}. It follows that the same is true of the rhs, and hence that

lim_{s→1^{+}} ∑_{p} p^{−s} = ∞.  (75)

In particular, the sum must contain infinitely many terms (i.e.: there are infinitely many primes) and ∑ p^{−1} diverges. This proves Theorem 26.

Step 2. Now enter Dirichlet. Theorem 26 is the case q = a = 1 of his theorem. For a fixed q > 1 Dirichlet suggested to consider the L-series (see p.24)

L(s, χ) = ∑_{n=1}^{∞} \frac{χ(n)}{n^{s}},  (76)

where χ is a Dirichlet character modulo q. The series defines an analytic function in the half-plane Re(s) > 1. It generalises the usual ζ-function, since the latter corresponds to q = 1 and χ = χ_{0}, the trivial character. These functions also have Euler products (p.28), namely

L(s, χ) = ∏_{p} (1 − \frac{χ(p)}{p^{s}})^{−1} .  (77)

11Recall from envariabelanalys (or see p.42 of my notes on flervariabelanalys from last year) that the sum of an absolutely convergent series is independent of the ordering of the terms. This is not true for conditionally convergent series (Riemann’s theorem).

As above, take log of both sides of (77) and expand the rhs in a Taylor series to obtain, for Re(s) > 1,

log L(s, χ) = ∑_{p} ∑_{m=1}^{∞} \frac{χ(p^{m})}{mp^{ms}}.  (78)

The difference between this and the previous situation is that now we are only interested in those primes p ≡ a (mod q), for some a with (a, q) = 1. So how do we isolate these primes in the sum (78) ? The trick is to use the following lemma (Dav. p.31, ekv. (4)) :

Lemma 27. Let a, n, q > 0 with (a, q) = (n, q) = 1. Then

∑_{χ} χ̄(a)χ(n) = \{ \begin{matrix}ϕ(q), & if n ≡ a (mod q), \\ 0, & otherwise, \end{matrix} (79)

where the sum is taken over all characters modulo q.

Proof : We’ll talk about this on Wednesday. The thing to note is that Lemma 27 is the ‘dual’ result to eq. (44) on p.28, i.e.: it’s the same result, but applied to the dual group of (Z/qZ)^{×} - see ex.6 of the supplementary exercises.

From (78) and (79) we obtain, by a simple calculation,

\frac{1}{ϕ(q)} ∑_{χ} χ̄(a) log L(s, χ) = ∑_{m=1}^{∞} ∑_{p^{m}≡a (mod q)} \frac{1}{mp^{ms}} .  (80)

Here we’re still assuming that Re(s) > 1, and the sum is taken over all characters modulo q. Next, as in the proof of Theorem 26, we split the terms of the sum into two groups, those with m = 1 and those with m > 1. We observe that the latter sum is bounded as s → 1 and conclude that

lim_{s→1^{+}} \frac{1}{ϕ(q)} ∑_{χ} χ̄(a) log L(s, χ) = lim_{s→1^{+}} ∑_{p≡a (mod q)} p^{−s} + O(1).  (81)

Dirichlet’s theorem is (as in the case of Theorem 26) precisely the statement that the limit of the right-hand sum is +∞. Hence we have reduced the proof of the theorem to showing that

lim_{s→1^{+}} \frac{1}{ϕ(q)} ∑_{χ} χ̄(a) log L(s, χ) = +∞.  (82)

Step 3. If χ = χ_{0}, the trivial character, then it’s easy to see that

L(s, χ_{0}) = ∏_{p|q} (1 − \frac{1}{p^{s}} ) · ζ(s).  (83)

Since the product is finite and different from zero, and ζ(s) → +∞ as s → 1^{+}, it follows that also L(s, χ_{0}) → +∞ as s → 1^{+}. Hence, (82) would be proven if we could show that log L(s, χ) were bounded, as s → 1^{+}, for every χ ≠ χ_{0}.

But we know (Sats 19, p.28) that if χ ≠ χ_{0}, then L(s, χ) is analytic in the range Re(s) > 0. In particular, L(s, χ) is bounded as s → 1. Hence the same is true of log L(s, χ) UNLESS L(1, χ) = 0. So we have reduced the proof of Dirichlet’s theorem to showing the following :

Theorem 28. Let q > 1 and χ be a non-trivial character modulo q. Then

L(1, χ) ≠ 0.  (84)

Step 4. All known proofs of Theorem 28 (as far as I know, anyway !) start by dividing it into two cases.

Definition : A character χ is called complex if χ(m) ∉ R for some m ∈ Z. Otherwise the character is called real.

Note that if χ is real then χ(m) = ±1 for all m. If the modulus q is a prime power, say q = p^{m}, then one easily shows that the only non-trivial real character is the Legendre symbol χ(m) = (\frac{m}{q}).

As suggested by the definition, we divide the proof of Theorem 28 according as to whether χ is real or complex. The easier part seems to be

Proposition 29. If χ is complex then L(1, χ) ≠ 0.

Proof : If χ is any character modulo q, then so is χ̄ defined by χ̄(m) := \overline{χ(m)}. The point is that, if χ is complex, then χ ≠ χ̄. Why is this useful ? Well, suppose that L(1, χ) = 0. Then L(1, χ̄) = 0 also, since L(s, χ̄) = \overline{L(s, χ)} for all real s. Since L(s, χ) and L(s, χ̄) are analytic functions in a neighbourhood of s = 1, it follows from elementary complex analysis that there exist functions A(s), B(s) analytic in a neighbourhood U of s = 1 so that

L(s, χ) = (s − 1)A(s) and L(s, χ̄) = (s − 1)B(s) for all s ∈ U. (85)

The proof of Proposition 29 now follows quickly from the following two results, the second of which is of sufficient interest in itself that we list it as a theorem in its’ own right (we will also need it later in the treatment of real characters) :

Lemma 30. If Re(s) > 1 then

∏_{χ} L(s, χ) > 1,  (86)

where the product is taken over all characters modulo q.

Theorem 31. The ζ-function can be continued to a meromorphic function in the half-plane Re(s) > 0 which has a simple pole at s = 1 and no other poles.

Before we prove these two results, let us see how they give Proposition 29. If L(1, χ) = 0 for a complex χ then, as shown above, the characters χ and χ̄ together contribute at least a double zero at s = 1 to the product on the lhs of (86). But since the product is > 1 whenever s > 1 it must also be > 1 in the limit as s → 1^{+}. This means that the remaining factors in the left-hand product must contribute at least a double pole at s = 1. But the factor L(s, χ_{0}) contributes only a simple pole, by (83) and Theorem 31, and the remaining factors are bounded. This is a contradiction, and completes the proof of Prop. 29.

Proof of Lemma 30 : One uses (80). The rhs of this equation is, at the very least, real and positive for Re(s) > 1. Now put a = 1, multiply across by ϕ(q) and finally exponentiate both sides to get (86).

Proof of Theorem 31 : The argument is classic and is given at the bottom of p.32 of the handout. Note the use of Abel’s partial summation formula at the outset.

Step 5. We have reduced Dirichlet’s theorem to proving Proposition 32. If χ is real and non-trivial, then L(1, χ) ≠ 0. This will be done next time.

Lektion 10 (22/11/00)

I denna lektion löste vi övningar från den 1:a inlämningsuppgiften.

In this lecture we complete the proof of Dirichlet’s theorem by proving Proposition 32^{12}. Dirichlet’s original proof has the benefit of being very interesting but the disadvantage of being quite complicated. Below we give his proof for prime moduli q ≡ 3 (mod 4). You should read my handouts for proofs of the remaining cases - it won’t be examined ! Since Dirichlet’s time, several ‘easier’, but uniformly less interesting, proofs have been proposed. We will first of all present one such proof, due to de la Vallée Poussin (1896). For yet another ‘easy’ proof see, for example, [6], Band I, s.93ff.

de la Vallée Poussin’s proof : The proof is given on p.33-34 of the handout. But I’ll write it here anyway, with perhaps a few more details. The proof is by contradiction. We thus assume that L(1, χ) = 0, where χ is a fixed real, non-trivial character modulo q, for some q > 0. One considers

12Those who have read my spiel on elliptic curves, buried amongst the solutions to inlämningsuppgft 1, may be interested to know that there is a corresponding OPEN problem about the L-series attached to elliptic curves E/Q. As I stated there, the Euler product defining L(E, s) can be shown directly to converge and give an analytic function when Re(s) > 3/2. It is conjectured that, as in the case of ordinary Dirichlet L-functions, L(E, s) has an analytic continuation to the whole s-plane, and furthermore that it satisfies a functional equation relating the values at s and 2 − s. In fact, this conjecture is now a theorem if one believes the recent complete proof of the Shimura-Taniyama conjecture, since it has long been known that the conjecture holds for modular elliptic curves. In any case, assuming the conjecture holds, we may investigate the value L(E, 1). One of the outstanding open problems in the theory of elliptic curves is the so-called Birch and Swinnerton-Dyer conjecture. Before we state this, we have to explain another theorem : Recall from my spiel that the set of points on any elliptic curve E has the structure of an abelian group. Now suppose E is defined over Q and let E(Q) denote the set of points (x, y) ∈ E s.t. both x and y are rational numbers. One can show that E(Q) is a subgroup of E - in fact, the same is true of E(K) for any extension field K of Q. A famous theorem from the 1920s, the so-called Mordell-Weil theorem, asserts that E(Q) is always a finitely generated group, hence isomorphic to the direct sum of a finite group and a finite number, r say, of copies of Z. The number r is called the rank of E (by the way, a generalisation of the Mordell-Weil theorem to abelian varieties of arbitrary dimension was proven by Faltings in 1984, for which he won the Fields medal !). We are now in a position to state a weak form of the Birch and Swinnerton-Dyer conjecture : it says that L(E, s) has a zero at s = 1 of order equal to the rank of E (in particular L(E, 1) ≠ 0 iff the group E(Q) is finite). Note that this is more or less the complete opposite of the corresponding result for Dirichlet L-series. Finally, we remark that a special case of the conjecture was established by Wiles and Coates as part of the former’s doctoral thesis, and it was this result which first established Wiles as a big name in number theory !

the function

ψ(s) := \frac{L(s, χ)L(s, χ_{0})}{L(2s, χ_{0})}.  (87)

We claim that ψ(s) is analytic in Re(s) > 1/2 and that ψ(s) → 0 as s → \frac{1}{2}^{+}.

To see this, first note that Sats 19(ii), eq. (83) and Theorem 31 guarantee that ψ(s) is at least meromorphic in the range Re(s) > 1/2. The only possible poles are at the poles of L(s, χ_{0}) and at the zeroes of L(2s, χ_{0}). Theorem 31 implies that the former has only a single simple pole at s = 1, but by assumption this is cancelled by the zero of L(1, χ). From the Euler product for the ζ-function, one sees directly that ζ(s) ≠ 0 whenever Re(s) > 1 - in fact, this property is equivalent to convergence of the product. Hence, from (83), the function L(2s, χ_{0}) is never zero in the region Re(s) > 1/2. This proves analyticity of ψ(s) in this region^{13}. That ψ → 0 as we approach s = 1/2 follows from the fact that L(2s, χ_{0}) has a pole at s = 1/2.

The next step is to restrict attention to the range Re(s) > 1, where we can write each L-function as an Euler product. Note that all Euler factors corresponding to prime divisors p of q are equal to 1, because χ(p) = χ_{0}(p) = 0 for such primes. Thus we have

L(s, χ) = ∏_{p†q}(1 − χ(p)p^{−s})^{−1},

L(s, χ_{0}) = ∏_{p†q}(1 − p^{−s})^{−1},

L(2s, χ_{0}) = ∏_{p†q}(1 − p^{−2s})^{−1}.

Now we use the fact that the character χ is real. This implies that χ(p) = ±1 for all primes p not dividing q. A direct calculation shows that, for any p such that χ(p) = −1, the Euler factor of ψ at p is just 1, because the factors coming from the three L-functions cancel each other out. We are thus left with the factors for primes for which χ(p) = 1, and another direct calculation shows that

ψ(s) = ∏_{χ(p)=1} \frac{1 + p^{−s}}{1 − p^{−s}} , (Re(s) > 1).  (88)

13Note that, if the Riemann hypothesis were true, we would know that ζ(s) had no zeroes for Re(s) > 1/2, hence that L(2s, χ_{0}) had no zeroes for Re(s) > 1/4, so that ψ(s)

would be analytic in this larger region.

Using the binomial theorem in the form (1 − p^{−s})^{−1} = ∑_{m=0}^{∞} p^{−ms}, we may expand (88) in a Dirichlet series

ψ(s) = ∑_{n=1}^{∞} \frac{a_{n}}{n^{s}} , (Re(s) > 1).  (89)

The only properties we will require of the coefficients a_{n} are that they are all non-negative real numbers and that a_{1} = 1. These are seen to hold by direct inspection.

The next and final step is to use (89) to derive a contradiction to the fact that ψ(s) → 0 as s → \frac{1}{2}^{+}. I won’t give the details because I don’t think any are left out in the handout, except perhaps for the remark that Weierstraβ’ theorem allows us to differentiate (89) termwise at s = 2^{14}

Dirichlet’s proof for prime moduli : I followed exactly the proof given on the handout, starting near the bottom of p.7. Observe that the

14If one examines (80) and (81) closely, then one can convince oneself that we have actually proven a stronger form of Dirichlet’s theorem.

Definition : Let A be a subset of the set of primes P. The (analytic) Dirichlet density of A is defined as

d_{D}(A) = lim_{s→1} (∑_{p∈A} \frac{1}{p^{s}} ) / (log \frac{1}{s − 1}) ,

provided this limit exists. Then we’ve actually proved

Theorem 32.A Let a, q > 0 with (a, q) = 1. Let P_{a} be the set of primes p ≡ a (mod q). Then d_{D}(P_{a}) = 1/ϕ(q).

The definition of ‘density’ given above seems rather technical. A much simpler notion is

Definition : Let A ⊆ P. The natural density of A is given by

d_{N}(A) = lim_{n→∞} \frac{#\{p ∈ A : p ≤ n\}}{#\{p ∈ P : p ≤ n\}} ,

provided the limit exists. It can be proven that d_{N} = d_{D} for sets of the form P_{a} above, which is reassuring. In general, it can be shown that, for a set A of primes, d_{N}(A) = d_{D}(A) whenever the former exists. However, there are (weird) sets A having a Dirichlet density but not a natural density. An example is the set A of primes whose first decimal digit is one ! See p.76 of Serre’s ‘A course in arithmetic’ for further comment.

appearance of the Gauβ sum G in the formula for L(1, χ) in the middle of p.8, together with the fact that L(1, χ) is a real number (χ being a real character), leads one, because of Sats 25, to distinguish the cases q ≡ 3 (mod 4) and q ≡ 1 (mod 4). We only had time to finish discussing the former case. Here, I just wish to note for the record two corollaries of the proof which are very beautiful in themselves and for which to this day, as Davenport notes, no proofs are known which avoid the use of L-functions. They are

Korollarium 33. If q is a prime, q ≡ 3 (mod 4), then

∑_{m=1}^{q−1} m (\frac{m}{q}) < 0.  (90)

Korollarium 34. If q is a prime, q ≡ 3 (mod 4), then there are more quadratic residues than non-residues modulo q amongst the numbers 1, 2, ..., \frac{q−1}{2}.

Remark : These two corollaries are amongst the oldest results concerning a problem which to this day is the subject of much research, namely that of the distribution of the quadratic residues modulo p, for a given prime number p. Since even the precise formulation of some of these problems is rather difficult, I will shy away from it, and content myself with mentioning a conjecture of Vinogradov which says that, for each ϵ > 0 there esists n_{ϵ} > 0 such that there exists a quadratic non-residue n < p^{ϵ} for all primes p > n_{ϵ}. See supplementary exercise no. 7 for something much weaker.

References

[6] E. Landau, Vorlesungen über Zahlentheorie, Leipzig 1927.

Idag börjar vi studiet av kvadratiska ekvationer över Z, dvs ekvationer av formen

f(x_{1}, ..., x_{n}) = 0,  (91)

där f är ett polynom av grad 2 med heltals koefficienter. Vi söker heltalslösningar till (91).

För n = 1 är allting klart. Ekvationen

ax^{2} + bx + c = 0 (a ≠ 0)  (92)

har lösningar i C som ges av

x = \frac{−b ± \sqrt{b^{2} − 4ac}}{2a}.  (93)

Alltså, har ekvationen en lösning i Q omm b^{2} − 4ac = d_{1}^{2} är en perfekt kvadrat, och en lösning i Z omm 2a | −b ± d_{1}. Antalet lösningar i Z är då 0, 1 eller 2.

För n = 2 blir situationen redan mycket mer komplicerad att analysera. I den här kursen ska vi koncentrera mest på detta fall (för en mer allmän diskussion kom till min doktorandkurs !).

Det var framför allt Gauβ som utvecklade en allmän teori för kvadratiska ekvationer i två variabler. Den större delen av hans klassiskt arbete Disquisitiones Arithmeticae handlar om denna teori. I vår presentation ska vi, till en början, följa Gauβ, innan vi reformulerar våra resultat i mer modern algebraisk talteoretiskt språk.

Vi studerar då den allmäna kvadratiska ekvationen i två variabler, dvs en ekvation av formen

ax^{2} + bxy + cy^{2} + dx + ey + f = 0,  (94)

där koefficienterna a, b, c, d, e, f ∈ Z och (a, b, c) ≠ (0, 0, 0). Polynom som på vänster sidan av (94) ska betecknas framöver med f(x, y), g(x, y) mm. Det är ofta passande att använda en matris notation. Om vi låter

A := ( \begin{matrix}a & \frac{b}{2} \\ \frac{b}{2} & c \end{matrix} ) , g := ( \begin{matrix}d \\ e \end{matrix} ) , X := ( \begin{matrix}x \\ y \end{matrix} ) ,  (95)

då kan (94) skrivas i formen

f(x, y) = f(X) = X^{T} AX + g^{T} X + f = 0.  (96)

För att simplificerar formen av ekvationen lite, betraktar man koordinat bytningar av typen X → X′ där

( \begin{matrix}x′ \\ y′ \end{matrix} ) = X′ := UX + V, ∃ U ∈ GL_{2}(Q), V ∈ Q^{2}.  (97)

Om det(A) ≠ 0 då kontrollerar man lätt att transformationen U = I, v = −\frac{1}{2}(A^{T})^{−1}g skaffar en ekvation av formen

f′(x′, y′) = ax′^{2} + bx′y′ + cy′^{2} = n.  (98)

Här är kanske n inte ett heltal, men då behöver man bara klara nämnarna.

Fallet det(A) = 0 är speciellt. Här ser man, efter en kvadrat komplettering (se (104) nedan), att det finns en koordinat bytning som tar (94) till formen

x′^{2} + e′y′ + f′ = 0.  (99)

Denna ekvation är tämligen ointeressant eftersom det är klart att det finns två heltalslösningar för varje y′ så att −e′y′ − f′ är en perfekt kvadrat.

Alltså, i fortsättningen ska vi ägna oss åt att studera ekvationer av formen (98), där b^{2} − 4ac ≠ 0.

Definition 1 : En funktion f : Z^{2} → Z som ges av

f(x, y) = ax^{2} + bxy + cy^{2}, a, b, c ∈ Z,  (100)

kallas för en (integral) binär kvadratisk form. I matris form, ges f av

f(X) = X^{T} AX, X = ( \begin{matrix}x \\ y \end{matrix} ) , A = ( \begin{matrix}a & \frac{b}{2} \\ \frac{b}{2} & c \end{matrix} ) .  (101)

Definition 2 : Kvantiteten d := b^{2} − 4ac kallas för diskriminanten av formen f. Notera att

d_{f} = −4 det(A_{f}).  (102)

Proposition 35. An integer d is the discriminant of some binary quadratic form iff d ≡ 0 or 1 (mod 4).

Proof : The definition of d immediately implies the necessity. For sufficiency, it suffices to write down explicit forms, and we choose

x^{2} − \frac{1}{4}dy^{2},  if d ≡ 0 (mod 4),
x^{2} + xy − \frac{1}{4}(d − 1)y^{2}, if d ≡ 1 (mod 4). (103)

The forms in (103) are called the principal forms.

Definition 3 : En form kallas för degenererad om d = 0 ; annars kallas den för icke-degenererad. En form med d < 0 kallas för definit : positiv definit i fallet a > 0 och negativ definit i fallet a < 0. En form med d > 0 kallas för indefinit. Slutligen, kallas formen för faktoriserbar om d är en perfekt kvadrat.

Notera att f är positiv definit omm −f är negativ definit. Då får vi strunta i negativa former framöver.

Definition 4 : Låt n ∈ Z. En form f sägs representera n om f(x, y) = n för något (x, y) ∈ Z^{2}. En sådan representation av n kallas för egentlig (proper) om gcd(x, y) = 1.

Problemet av att lösa (98) i heltalen kallas för representationsproblemet för binära kvadratiska former. Det är det grundläggande problemet som motiverar alla idéerna som vi skall nu presentera.

Först förklarar vi terminologin i Definition 3. Kvadratkomplettering i

(100) leder till uttrycket

4af(x, y) = (2ax + by)^{2} − dy^{2}.  (104)

Då ser vi direkt att representationsproblemet är tämligen ointeressant för faktoriserbara former, eftersom det reducerar till att faktorisera 4an och då att lösa par av simultana LINJÄRA ekvationer. I fortsättningen, alltså, antar vi alltid följande

‘f är en kvadratisk form vars diskriminant d inte är en perfekt kvadrat, och om d < 0 då är f positiv definit’.

Nu leder (104) direkt till följande resultat som förklarar vår terminologi :

Proposition 36. (i) f positiv definit ⇔ f representerar bara positiva tal. (ii) f indefinit ⇔ f representerar både positiva och negativa tal.

Gauβ’ approach to the representation problem can be divided up into the following main steps :

Step 1 : Divide up all the forms according to their discriminant.

Step 2 : Define an equivalence relation on the set of forms of a given discriminant so that equivalent forms need not be distinguished as regards the representation problem, i.e.: equivalent forms represent (properly) the same integers and there is a canonical 1-1 correspondence between their (proper) representations of a given integer.

Step 3 : Show that the number of equivalence classes for a given discriminant is finite and that each class contains at least one ‘nice’ form.

Step 4 : Find a formula for the total number of representations of an integer by a representative collection of forms of a given discriminant.

We shall carry out this program. But first, some remarks are in order :

1. The process described in Steps 2-3 is called reduction theory. It turns out that a satisfactory reduction theory is far easier to obtain for definite forms than for indefinite forms. We will only present detailed proofs of the results in the former case. In both cases, the theory gives an algorithm for deciding whether two forms of a given discriminant are equivalent. The procedure is simpler in the definite case.

2. With regard to Step 4, the formula in question will be seen to be quite simple and elegant. In the case of indefinite froms, where any given integer may have infinitely many representations as we’ll see below, the formula counts representations of a certain type, called primary. It is important to note that there seems to be no such simple formula for the number of (primary) representations of an integer by a single form of a given discriminant. However, we will see that there exist, in principle, algorithms for deciding whether (98) has a solution, and for counting the number of (primary) solutions. For definite forms, this is in fact a trivial result, since f(x, y) = n implies that x and y are bounded explicitly. But for indefinite forms, this is not the case and something more clever must be done. Also, the algorithms for definite forms got by explicitly bounding x, y are obviously very slow. Finally, we observe that our algorithms here will in turn depend on those for deciding equivalence of forms, as just mentioned above.

Definition : The binary quadratic forms f and f′ are said to be equivalent, denoted f ∼ f′, if there exists a matrix M ∈ SL_{2}(Z) such that

M^{T} A_{f}M = A_{f′}.  (105)

It is readily checked that (105) does indeed define an equivalence relation on the set of all binary forms, and that equivalent forms have the same discriminant. The importance of the relation relies in the following fact :

Proposition 37. If f ∼ f′, then for each integer n, there is a 1-1 correspondence between the (proper) representations of n by f and f′.

It is convenient to write down, once and for all, the explicit relationship between the coefficients of equivalent forms. If f = {a, b, c}, f′ = {a′, b′, c′}

and M = ( \begin{matrix}p & q \\ r & s \end{matrix} ) is a matrix taking f to f′, then (105) gives

a′ = f(p, r) = ap^{2} + bpr + cr^{2},
c′ = f(q, s) = aq^{2} + bqs + cs^{2},
b′ = 2apq + b(ps + qr) + 2crs.  (106)

Reduction theory

Definition : The form {a, b, c} is said to be reduced if either

−|a| < b ≤ |a| ≤ |c| or 0 ≤ b ≤ |a| = |c|.  (107)

The main result of reduction theory is

Theorem 37 (Lagrange/Gauss). (i) Every binary form is equivalent to a reduced form. (ii) There are only finitely many reduced forms of a given discriminant. (iii) Every positive definite form is equivalent to precisely one reduced form.

Proof : A condensed version of the proof we gave in class is found on ps. 36-7 of Baker’s book.

Important remark 1 : The proof of (i) gives an algorithm for producing a reduced form equivalent to a given form (in class I considered the example of the form f(x, y) = 22x^{2} − 108xy + 133y^{2}, which I reduced to the form f′(x, y) = 2x^{2} + 5y^{2}). Because of (iii) this gives, in the case of positive definite forms, an algorithm for deciding whether two given forms are equivalent.

However, for indefinite forms, things get much more complicated. It can happen that a single equivalence class of indefinite forms contains more than one reduced member. In particular, the above algorithm for deciding equivalence of forms does not work in general. In fact, one needs a whole new (and rather different !) reduction theory in order to be able to find such an algorithm^{15}.

15We will not have time to describe this theory, but here are the main results. For detailed proofs, see my handout from Zagier’s book, ‘Zetafunktionen und quadratische Körper’.

In this new theory, a form {a, b, c} is called reduced if a > 0, c > 0 and a + c < b. We consider a special type of transformation (105). If f is the form \{a, b, c\}, set n = ⌈ \frac{b+\sqrt{d}}{2a} ⌉ and define T (f) to be the form obtained by transforming, as in (105), with the matrix M_{n} = ( \begin{matrix}n & 1 \\ −1 & 0 \end{matrix} ). Then the main result of the theory is Theorem. (i) The number of reduced forms of a given discriminant is finite.

Important remark 2 : Motivated by Theorem 38, we define H(d) to be the number of equivalence classes of binary forms of discriminant d. The theorem says that H(d) is finite, and because of the principal forms, we conclude that H(d) is a non-zero positive integer. For positive definite forms, part (iii) of the theorem implies that, in order to compute H(d), it suffices to compute the number of reduced forms of discriminant d. This can be done because, from (107) and the equation d = b^{2} − 4ac, we can easily derive explicit bounds for the coefficients of a reduced form of discriminant d, namely

0 < |a| ≤ \sqrt{−d/3}, for a reduced definite form,
0 < |a| ≤ \sqrt{d/4}, for a reduced indefinite form.  (108)

For indefinite forms, this procedure only gives, in general, an upper bound for H(d). One of the classical results of algebraic number theory is

Theorem 39 (Baker/Stark 1966.)^{16} There are only finitely many d < 0 for which H(d) = 1, and these are given explicitly by d = −3, −4, −7, −8, −11, −19, −43, −67, −163.

Likewise, one of the outstanding open problems in algebraic number theory is

Open problem. Do there exist infinitely many d > 0 for which H(d) = 1 ?

(ii) For any given form f, there exists a positive integer k, depending on f, such that T^{k}(f) is reduced.

(iii) The operator T maps reduced forms to reduced forms.

(iv) Every equivalence class of reduced forms is acted upon transitively by T.

Note that the theorem does not say that each class of forms contains a unique reduced form (this is false !), hence does not provide an algorithm for computing class numbers (see important remark no. 2 above). On the other hand, it is easy to see that (ii),(iii) and (iv) give an algorithm for deciding equivalence of any 2 given forms.

16This result is usually phrased in terms of which imaginary quadratic number fields have unique factorisation. We will explain what this means later. Likewise, the open problem following Theorem 39 is usually phrased in terms of unique factorisation for real quadratic fields.

Definition : En matris M ∈ SL_{2}(Z) sägs vara en automorfism av formen f om

M^{T} A_{f}M = A_{f}.  (109)

Notera att automorfismerna av f utgör en delGRUPP av SL_{2}(Z). Denna grupp betecknas Aut(f). Ordningen av gruppen betecknas med w(f).

Proposition 40. (i) Om X ∈ Z^{2} och M ∈ Aut(f), då är

f(MX) = f(X).  (110)

(ii) Om f ∼ g, och P är en matris så att P^{T} A_{f}P = A_{g}, då har vi en 1-1 korrespondens

\begin{matrix}Aut(f) & ↔ & Aut(g) \\ M & ↔ & P^{−1}MP. \end{matrix}  (111)

Notera att del (i) av propositionen säger att när vi räknar antalet representationer av ett heltal n med f, så måste vi inte glömma automorfiska representationer.

Del (ii) av propositonen säger att ekvivalenta former har samma antalet automorfismer.

Det viktiga begreppet för att studera automorfism frågan är

Definition : En form f = {a, b, c} kallas för primitiv om gcd(a, b, c) = 1.

Proposition 41. Låt f = {a, b, c} vara en form med gcd(a, b, c) = r. Då är formen f′ = {a/r, b/r, c/r} primitiv och Aut(f) = Aut(f′).

Bevis : Klart.

Denna proposition reducerar beräkningen av automorfismgrupper till den för primitiva former. Det visar sig nu att automorfismgrupperna av primitiva former kan beskrivas helt explicit. Vi har

Sats 42. Låt f = {a, b, c} vara en primitiv form av diskriminant d. Då består Aut(f) precist av alla matriser

M = ( \begin{matrix}\frac{1}{2}(t − bu) & −cu \\ au & \frac{1}{2}(t + bu) \end{matrix} ) ,  (112)

där (t, u) ∈ Z^{2} är en lösning av ekvationen

t^{2} − du^{2} = 4.  (113)

Bevis : Satz 202 i Landaus bok (se utdelad stencil).

Ekvation (113) kallas för Pells ekvation. I fallet d < 0 kan lösningarna ses direkt, och de är

(±2, 0), (0, ±1), om d = −4,
(±2, 0), ±(1, 1), ±(1, −1), om d = −3,
(±2, 0),  annars.

(114)

Då följer det från Sats 42 att

Korollarium 43. Låt f = {a, b, c} vara en primitiv positiv definit form av diskriminant d < 0. Då har vi att

Aut(f) = {±M_{1}, ±M_{2}}, w(f) = 4, om d = −4,
Aut(f) = {±M_{1}, ±M_{3}, ±M_{3}^{2}}, w(f) = 6, om d = −3,
Aut(f) = {±M_{1}}, w(f) = 2,  annars,

(115)

där

M_{1} = ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) , M_{2} = ( \begin{matrix}0 & 1 \\ −1 & 0 \end{matrix} ) , M_{3} = ( \begin{matrix}0 & −1 \\ 1 & 1 \end{matrix} ) .(116)

För indefinita former, är läget mycket mer interessant. Man får följande resultat

Sats 44. (i) (Lagrange 1768) Låt d vara ett positivt heltal som inte är en perfekt kvadrat. Då har Pells ekvation (113) oändligt många lösningar. Om (t_{0}, u_{0}) är den lösning med t_{0}, u_{0} > 0 och u_{0} minimal, då ges alla lösningar av

\frac{1}{2}(t + u\sqrt{d}) = ± [\frac{1}{2}(t_{0} + u_{0}\sqrt{d})]^{m} ,  (117)

där m ∈ Z.

(ii) (Gauss) Om f är en primitiv form av diskriminant d, då är w(f) = ∞ och Aut(f) ≅ Z, en oändlig cyklisk grupp.

Bevis : Kommer senare. Nuförtiden, genomförs beviset bäst i sättningen av algebraiska talkropper. Naturligtvis kan man undvika denna teori, som Lagrange tvingades göra - för en sådan synvinkel, se t.ex. Landaus Vorlesungen, Satz 111.

Vi vill säga lite mer om primitiva former innan vi går vidare.

Proposition 45. Om f är primitiv och f ∼ g, då är g också primitiv.

Definition : Vi betecknar med h(d) antalet ekvivalens klasser av primitiva former av diskriminant d. Notera att detta är väl-definierad enligt Prop. 45.

Definition : Ett heltal d ≡ 0 eller 1 (mod 4) kallas för en fundamental diskriminant om varje form av diskriminant d är primitiv.

Proposition 46. Låt d ≡ 0 eller 1 (mod 4).

(i) H(d) = h(d) ⇔ d är en fundamental diskriminant. (ii)

H(d) = ∑_{t^{2}|d} h (\frac{d}{t^{2}} ) .  (118)

(iii) d är en fundamental diskriminant omm

d är kvadratfri, om d ≡ 1 (mod 4),
d/4 är kvadratfri och ≡ 2 eller 3 (mod 4), om d ≡ 0 (mod 4).

(119)

Bevis : (i) följer direkt från definitionen av en fundamental diskriminant. För (ii) och (iii) se supplementär övning nr. 12.

Representationsproblemet

We now finally come to what we’ve really been building up to all this time, namely the analysis of the equation

f(x, y) = ax^{2} + bxy + cy^{2} = n,  (120)

where everything in sight is an integer. Any such problem has both a theoretical and a practical aspect. From the theoretical viewpoint, one seeks some ‘nice formulas’ for the numbers R(n, f) of solutions to (120). From the practical viewpoint, one is interested in having fast algorithms for computing all solutions explicitly^{17}. Obviously, these two issues are inextricably linked.

Keeping in mind what people have actually succeeded in doing with the problem, we will follow the following program :

Step 1 : As we’ve described earlier, the problem is uninteresting when the discriminant d is a perfect square. So we’ll alawys assume this is not the case. Also, we lose nothing, in the case d < 0, by assuming that f is positive definite, i.e.: that a, c > 0.

Step 2 : Right at the outest, a clear distinction presents itself between the definite and indefinite cases. In the former case, the number R(n, f) is always finite, and the coefficients (x, y) of a representation are explicitly bounded by

|x| ≤ \sqrt{4nc/|d|}, |y| ≤ \sqrt{4na/|d|}.  (121)

These bounds follow easily from completion of squares, as in (104). Note that we hereby immediately obtain a (slow) algorithm for finding all solutions of (120) in the definite case - just check all pairs x, y up to the bounds in (121).

In the indefinite case, it follows immediately from Sats 44 that R(n, f) is always either 0 or ∞. That is, each solution gives rise to an infinity of others by the application of the automorphisms of the form (see Prop. 40). It turns out that there is a fairly natural way of selecting, from each such infinite set of automorphic representations, one which is called primary. The number of primary representations then turns out to be finite, and we adopt the notation R(n, f) for this number instead. The remarkable and wonderful fact is that, with this new convention, the indefinite and definite cases become ‘unified’ : more precisely we get explicit formulas valid in both cases (see Step 3).

With regard to the algorithmic question of finding explicit (primary) representations, it should not surprise you that this reduces to finding generating solutions of Pell’s equation. This is an instance of a problem in Diophantine approximation theory, and so we’ll be lead to roam into this area. However, this will be postponed until the very end of the course, after we have done some algebraic number theory.

17The results we present in this course will only be to the extent of showing that algorithms exist. I have no idea what the state of the art is in regard to ‘fast’ algorithms, and hence will make no attempt to go into this matter.

Step 3 : It is convenient to first of all count proper representations. The number of proper representations of n by f is denoted r(n, f), with the extra condition that the representations be primary in the indefinite case. Observe that

R(n, f) = ∑_{t^{2}|n} r (\frac{n}{t^{2}} , f) .  (122)

We now come to the crucial point :

As indicated in Step 2, there are algorithms for computing the numbers r(n, f), for any given n and f. However, there seems to be NO SIMPLE FORMULAS for them. But if we sum over the forms of a fixed discriminant, then we get REALLY NICE formulas. More precisely, define, for each discriminant d,

R_{d}(n) := ∑_{f} R(n, f), r_{d}(n) := ∑_{f} r(n, f),  (123)

where the sum runs over a representative set of forms of discriminant d, one from each equivalence class. By Prop. 37, the sums are then well-defined.

The number r_{d}(n) can be expressed in terms of the number of solutions to a certain quadratic congruence (Theorems 47,50 and 51 below). But solving quadratic congruences is a relatively simple matter, as discussed earlier in this course (see, in particular, Prop. 22). In particular, this already takes care of the algorithmic issues. The resulting ‘formulas’ are simplest in the case when d is a fundamental discriminant (basically, this is because all forms of discriminant d then have the same number of automorphisms - see Korollarium 43) and (n, d) = 1. The central result, Theorem 53, is due to Dirichlet. Dirichlet was led to this result by a rather circuitous route, during his investigations concerning his theorem on arithmetic progressions. Theorem 53 was his starting point for the proof of his so-called class number formula, which relates the class number h(d) of a fundamental sicriminant d, to the value L(1, χ) of the L-function of some real character χ modulo d. The formula implies, in particular, that L(1, χ) ≠ 0, which you will remember was an essential ingredient in the proof of Dirichlet’s theorem.

From a deeper, historical perspective, the class number formula is the starting point of two important theories :

(a) the analytic theory of number fields. Dirichlet’s formula can be formulated in terms of quadratic number fields, and is then a special case of a class number formula valid for all number fields, which was first discovered by Hecke in the early 20th century. The basic analytical ingredient here is the notion of the ζ-function of a number field. Since Hecke, there has been an explosion of research into exploring the connections between analytic and algebraic aspects of number theory which, on the analytical side, usually relies on being able to extend the notion of a ζ-function to the particular realm of interest - the case of elliptic curves (see solutions to inlmningsuppgift nr. 1) being an excellent example.

(b) the analytic theory of quadratic forms. The state of the art in this area are the works of Siegel, from the 1930s and 40s, culminating in a formula which expresses the number of representations (in the indefinite case, something generalising primary representations) of an integer n by a representative set of forms Q in a given genus as an infinite product of terms over the primes (including infinity), each of which can be computed. This formula applies to quadratic forms in any number of variables. Come to my doktorandkurs if you want to learn more about this !

Representationsproblemet : the results !!

First, let’s give the basic connection between proper representations and quadratic congruences :

Theorem 47. The number n is properly represented by some binary quadratic form of discriminant d iff the congruence

h^{2} ≡ d (mod 4n)  (124)

is solvable.

Proof : As in Baker, p.37-8.

APPENDIX 1

Positive definite binary quadratic forms over R and linear fractional transformations

Linear fractional transformations

Definition 1 : Let M ∈ SL_{2}(R), say M = ( \begin{matrix}p & q \\ r & s \end{matrix} ). Let H = \{z ∈ C :

Im(z) > 0}. The map γ_{M} : H → H defined by

γ_{M}(z) = \frac{pz + q}{rz + s}  (125)

is called a linear fractional transformation (of H).

It is well-known (and proven in every complex analysis course) that every holomorphic automorphism of H is given by a linear fractional transformation.

Definition 2 : Let G be a group which is also a topological space. If the maps

\begin{aligned}μ & : & G × G & → & G \\ μ & : & (x, y) & ↦ & xy \end{aligned}  and  \begin{aligned}i & : & G & → & G \\ i & : & x & ↦ & x^{−1} \end{aligned}

are continuous (where G × G has the product topology), then G is called a topological group.

Definition 3 : A topological group G is said to act (continuously) on a topological space S if there is a continuous map

\begin{matrix}G × S & → & S \\ (g, s) & ↦ & gs \end{matrix}

(where G × S has the product topology) with the following properties :

(I) ∀ g, h ∈ G, ∀ s ∈ S, gh(s) = g[h(s)].

(II) ∀ s ∈ S, es = s.

Proposition 1. Definition 1 defines a continuous action of SL_{2}(R) on H.

Definition 4 : Let G act on S. For a point s ∈ S, the set

Gs := {gs : g ∈ G}  (126)

is called the G-orbit of s. Clearly, S is the disjoint union of its’ G-orbits. Points in the same orbit are said to be G-equivalent. If there is just one G-orbit, we say that G acts transitively on S.

Proposition 2. SL_{2}(R) acts transitively on H.

Definition 5 : A subgroup Γ of a topological group G is called a discrete subgroup if the induced topology of Γ is discrete.

Proposition 3. Γ(1) := SL_{2}(Z) is a discrete subgroup of SL_{2}(R).

Definition 6 : Let G act on S as before. A subset F ⊆ S is called a fundamental domain for the action of G if

(i) F is a connected Borel subset of S. (ii) No two points of F are G-equivalent. (iii) Every point of S is equivalent to some point in the closure of F.

Theorem 4. (i) Every discrete subgroup of SL_{2}(R) has a fundamental domain in H. (ii) A fundamental domain for Γ(1) is given explicitly by

F = \{z ∈ H : |z| > 1 and − \frac{1}{2} ≤ Re(z) < \frac{1}{2}\} ∪

\{z ∈ H : |z| = 1 and − \frac{1}{2} ≤ Re(z) ≤ 0\} .  (127)

Definition 7 : Let G act on S as before. Let s ∈ S. The subgroup G_{s} of G given by

G_{s} := {g ∈ G : gs = s}  (128)

is called the isotropy group of s.

Theorem 5. Let z ∈ H and Γ = Γ(1). Then

Γ_{z} = {±M_{1}, ±M_{2}}, |Γ_{z}| = 4, if z ∈ Γi,
Γ_{z} = {±M_{1}, ±M_{3}, ±M_{3}^{2}}, |Γ_{z}| = 6, if z ∈ Γρ,
Γ_{z} = {±M_{1}}, |Γ_{z}| = 2, otherwise,

(129)

where

ρ = e^{2πi/3}, M_{1} = ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) , M_{2} = ( \begin{matrix}0 & 1 \\ −1 & 0 \end{matrix} ) , M_{3} = ( \begin{matrix}0 & −1 \\ 1 & 1 \end{matrix} ) .

(130)

Positive definite binary quadratic forms

We consider quadratic forms with REAL coefficients !!!! Let f = {a, b, c} be a positive definite binary quadratic form of discriminant d < 0. We associate to f the point z_{f} ∈ H given by

z_{f} = \frac{−b + \sqrt{d}}{2a}.  (131)

Then the basic results of the reduction theory of positive definite forms can be phrased as follows Theorem 6. Fix an integer d < 0.

(i) Eq. (131) describes a 1-1 correspondence between positive-definite binary forms over R of discriminant d and points of H. (ii) If M ∈ Γ(1), then z_{M(f)} = Mz_{f}, where M(f) is the form with matrix A_{M(f)} = M^{T} A_{f}M, and Mz_{f} is the point of H given by (125). In particular, the group Aut(f) is isomorphic to the isotropy subgroup of z_{f}. (iii) Forms f and g are equivalent iff z_{f} and z_{g} lie in the same Γ(1)-orbit in H. (iv) A form f is reduced in the sense of (107) iff the point z_{f} lies in the fundamental domain (127).

(v) The point i ∈ F corresponds to the reduced form f_{−4} with b = 0, a = c = \frac{1}{2} \sqrt{−d}. Hence, Aut(f_{−4}) = \{±M_{1}, ±M_{2}\} and w(f_{−4}) = 4.

(vi) The point ρ ∈ F corresponds to the reduced form f_{−3} with a = b = c = \sqrt{−d/3}. Hence, Aut(f_{−3}) = \{±M_{1}, ±M_{3}, ±M_{3}^{2}\} and w(f_{−3}) = 6.

(vii) If the reduced form f corresponds to any other point of F, then Aut(f) = {±M_{1}} and w(f) = 2.

References

For proofs of most of the results listed here, see for example my handout from the book ‘Topics in number theory, Vol. II’, by W.J. LeVeque. For a (much !) more advanced discussion of the action of SL_{2}(R) and its’ discrete subgroups on H, and its’ importance in number theory, see for example the book ‘Intorduction to the arithmetic theory of automorphic functions’, by G. Shimura.

Vi börjar med en tillämpning av Sats 47.

Proposition 48. (i) Låt p vara ett udda primtal. Då finns det en form av diskriminant d som representerar p omm antingen 4p|d eller (\frac{d}{p}) = 1.

(ii) Låt p vara ett udda primtal. Då har ekvationen x^{2} − 2y^{2} = p en lösning (x, y) ∈ Z^{2} omm p ≡ ±1 (mod 8).

Bevis : (i) Enligt Sats 47, finns det en form av diskriminant d som representerar p omm kongruensen h^{2} ≡ d (mod 4p) är lösbar. Om 4p | d då är h = 0 en lösning. Annars finns det en lösning omm d är en kvadrat modulo 4p ⇔ d är en kvadrat modulo p (Prop. 22) ⇔ (\frac{d}{p}) = 1.

(ii) Formen x^{2} − 2y^{2} har diskriminant 8 och m.h.a. (107), (108) visar man lätt att den är den unika reducerade formen av diskriminant 8. Enligt Sats 37 finns det då precis en klass av former av diskriminant 8, så att i detta fall Sats 47 och del (i) antyder att x^{2} − 2y^{2} representerar udda primtalet p omm antingen 4p | 8, som är omöjligt, eller (\frac{8}{p}) = 1 ⇔ (\frac{2}{p}) = 1 ⇔ p ≡ ±1 (mod 8), enligt Sats (ii), s.38.

Under resten av lektionen, koncentrerar vi på representationsproblemet för positiv definita former. Vi skall indikera hur resultaten kan utvidgas till det indefinita fallet (där man betraktar bara primära representationer) och referera till Landaus Vorlesungen för bevis, och till och med för definitionen av en primär representation, som är lite krånglig.

Det första målet är att ge en mer precis version av Sats 47.

Notation : Låt d < 0, n > 0. Låt h ∈ Z satisfiera h^{2} ≡ d (mod 4n), säg h^{2} = d + 4nk. Den kvadratiska formen nx^{2} + hxy + ky^{2} ska betcknas med f_{n,h}. Notera att d(f_{n,h}) = d.

Lemma 49. Låt f, g vara ekvivalenta binära former. Då finns det precist w(f) matriser M ∈ SL_{2}(Z) så att M^{T} A_{f}M = A_{g}.

Bevis : Eftersom f ∼ g, finns det minst en matris N så att N^{T} A_{f}N = A_{g}.

Om N_{1}, N_{2} är två sådana matriser, sätt M = N_{1}N_{2}^{−1} och kontrollera att M^{T} A_{f}M = A_{f}, dvs att M ∈ Aut(f). Därför, {MN : M ∈ Aut(f)} är mängden av alla matriser som tar f till g. Denna mängd har w(f) element.

Sats 50. Låt f = {a, b, c} vara en positiv definit form av diskriminant d < 0. Låt n > 0. Sätt

H_{f}(n){def \atop =}#\{h : 0 ≤ h < 2n, h^{2} ≡ d (mod 4n), f_{n,h} ∼ f\}.  (132)

Då är

r(n, f) = w(f)H_{f}(n).  (133)

Bevis : Låt X vara mängden av alla former f_{n,h} så att h satisfierar villkoren i definitionen av H_{f}(n). Denna mängd innehåller då H_{f}(n) former. Enligt Lemma 49 finns det, för varje form f_{n,h} ∈ X, precis w(f) matriser M ∈ SL_{2}(Z) som tar f till f_{n,h}. Då finns det totalt w(f)H_{f}(n) matriser som tar f till någon form i X. Låt mängden av dessa matriser betecknas med Y. För att bevisa (133), räcker det nu att etablera an 1-1 korrespondens mellan matriserna i Y och egentliga representationer av n med f.

⇒ Först, välj M ∈ Y, säg M = ( \begin{matrix}α & γ \\ β & δ \end{matrix} ). Låt M(f) = f_{n,h} = nx^{2} +

hxy + ky^{2}. Från transformationsformlerna (106) ser vi att

f(α, β) = n.  (134)

Eftersom det(M) = 1 måste gcd(α, β) = 1, så att (134) är en egentlig representation av n med f.

⇐ Vi måste visa att ovanstående korrespondensen har en invers, dvs vi måste bevisa följande :

Påstående : Låt f(x, y) = n vara en egentlig representation av n med

f. Då finns det en unik matris M = ( \begin{matrix}x & ∗ \\ y & ∗ \end{matrix} ) ∈ SL_{2}(Z) så att M ∈ Y.

För att bevisa detta, först betrakta på hur många olika sätt en matris med

första kolonn ( \begin{matrix}x \\ y \end{matrix} ) kan kompletteras till ett element av SL_{2}(Z). Euclids

algoritm antyder att det finns minst ett sätt, dvs att det finns minst ett par (u, v) av heltal så att xu − yv = 1. Låt (ū, v̄) vara ett annat sådant par. Då har vi att

xu − yv = 1,
xū − yv̄ = 1.

Subtraktion ger x(ū − u) = y(v̄ − v). Men gcd(x, y) = 1, så det måste finnas t ∈ Z så att ū − u = ty, v̄ − v = tx.

Alltså ges alla matriser i SL_{2}(Z) med första kolonn ( \begin{matrix}x \\ y \end{matrix} ) av M_{t} =

( \begin{matrix}x & v + tx \\ y & u + ty \end{matrix} ), där t ∈ Z.

Nu säger påståendet att det finns precist ett t så att M_{t} ∈ Y.

Vi har redan sett i beviset av Sats 47 i fredags att varje matris M_{t} tar f till en form av typen nx^{2} + hxy + ky^{2}, där h^{2} ≡ d (mod 4n), och h^{2} = d + 4nk. Målet nu är att bevisa att det finns ett unikt t så att denna h också satisfierar villkoret 0 ≤ h < 2n.

Från transformationsformlerna (106) får vi att

h = 2ax(v + tx) + b[x(u + ty) + y(v + tx)] + 2cy(u + ty) ; \begin{matrix}= & 2t(ax^{2} + bxy + cy^{2}) & + & (2axv + bxu + byv + 2cyu) \\ = & 2tf(x, y) & + & K \\ = & 2nt & + & K, \end{matrix}

där konstanten K är oberoende av t. Då ser vi att det finns ett unikt t så att 0 ≤ h < 2n, q.e.d.

Anmärkning 1 : Om f är en primitiv, indefinit form av diskriminant d > 0, då stämmer (133) fortfarande om vi tar w(f) = 1. Se Vorlesungen, Satz 203, för ett bevis.

Anmärkning 2 : Ekv. (133) ger en ny algoritm för att beräkna r(n, f). Först, beräknar man w(f), som är lätt pga Prop. 41 och Korollarium 43. Då lösar man kongruensen h^{2} ≡ d (mod 4n), och för varje lösning kontrollerar om f_{n,h} ∼ f. Man använder reduktionsteorin för denna sista del. Notera att samma algoritm funkar i det indefinita fallet, även om reduktionsteorin är ganska mer komplicerad.

Det följer direkt från (133) att

r_{d}(n) = ∑ w(f)H_{f}(n),  (135)

där summan är över en mängd av representanter för ekvivalensklasserna av former av diskriminant d. Eftersom ∑ H_{f}(n) är antalet lösningar till en kvadratisk kongruens, misstänker man att det borde finnas en snygg formel för r_{d}(n) om w(f) är en konstant i summan (135). Från Korollarium 43 ser vi att det är så, t.ex. när d är en fundamental diskriminant^{18}. Då har vi bevisat

Sats 51. Låt d < 0 vara en fundamental diskriminant. Då är

r_{d}(n) = wN_{d}(n),  (136)

där

w = \{ \begin{matrix}2, & om d < −4, \\ 4, & om d = −4, \\ 6, & om d = −3, \end{matrix}  (137)

och

N_{d}(n) = #{h : h^{2} ≡ d (mod 4n), 0 ≤ h < 2n}.  (138)

Anmärkning : Resultatet gäller fortfarande för d > 0, om vi tar w = 1.

Vi har ett steg kvar i vår historia, nämligen att få en formel för N_{d}(n), när (n, d) = 1, i termer av så kallade Kronecker symboler (se utdelad stencil - Satz 97 von Vorlesungen). Denna formel var startpunkten för Dirichlet i beviset av hans berömda klasstals formel (se utdelad stencil från Davenports bok). Detaljerna kommer på onsdag.

18För en komplett karakterisering av vilka d satisfierar denna egenskap, se supplementär övning nr. 13.

First, we wish to describe an extension of the Jacobi symbol (\frac{d}{n}) to arbitrary n > 0. We will assume at all times that d ≡ 0 or 1 (mod 4) and is not a perfect square^{19}. We then define (\frac{d}{n}) in several steps as follows :

Step 1 : (\frac{d}{p}) := 0 if the prime p|d.

Step 2 : For odd d,

(\frac{d}{2}) := \{ \begin{matrix}1, & if d ≡ 1 (mod 8), \\ −1, & if d ≡ 5 (mod 8). \end{matrix}

Observe that (\frac{d}{2}) equals the Jacobi symbol (\frac{2}{|d|}). This follows from Sats, p.38.

Step 3 : For an odd prime p, (\frac{d}{p}) := Legendre symbol.

Step 4 : For a general n = ∏_{i} p_{i}^{α_{i}}, we set

(\frac{d}{n}) := ∏_{i} (\frac{d}{p_{i}} )^{α_{i}} .  (139)

Remark : For a given d, the function χ(n) := (\frac{d}{n}) is a real character modulo d^{20}.

19Obviously, the reason for doing this is because we’ll be interested in applications to quadratic forms, in which case d will be the discriminant of the form. In principle, the definitions we give make perfectly good sense for all d ∈ Z. However, there seems to be no application for the remaining d. See also the next footnote.

20A character χ modulo d is called primitive if there does not exist a proper divisor d_{1} of d and a character χ_{1} modulo d_{1} such that χ(n) = χ_{1}(n) for all n prime to d. One also says that χ is not an induced character. It can be shown (see, for example, Chapter 5 of Davenport) that a real primitive character exists to the modulus d iff d is a fundamental discriminant, and that all such characters are given by the Kronecker symbols (\frac{d}{n}). Recall now that, in the proof of Dirichlet’s theorem, one reduces to showing that L(1, χ) ≠ 0 for real characters χ. In Dirichlet’s original proof he first reduces further to real, primitive characters (this is easy), in other words, to Kronecker symbols. He then shows that L(1, χ) ≠ 0 for such characters, by relating the value of L(1) to the class number h(d). This is his so-called class number formula, given below in (143).

Lemma 52. Let d ≡ 0 or 1 (mod 4), not a perfect square, and n > 0 with (n, d) = 1. Then the number N_{d}(n), as defined in (138), is given by

N_{d}(n) = ∑_{m|n, m squarefree} (\frac{d}{m}) .  (140)

Bevis : Satz 97, Vorlesungen (see handout).

From Sats 51, Lemma 52 and (122) we immediately get

Theorem 53 (Dirichlet). Let n > 0, and d be a fundamental discriminant with (n, d) = 1. Then

r_{d}(n) = w ∑_{m|n, m squarefree} (\frac{d}{m}) ,  (141)

and

R_{d}(n) = w ∑_{m|n} (\frac{d}{m}) ,  (142)

where w = 2, 4, 6, 1 according as d < −4, d = −4, d = −3, d > 0 respectively.

Remark : Formula (142) was the starting point for Dirichlet’s proof of his class number formula (see handout no. 10). The formula says that

h(d) = \{ \begin{matrix}^{\frac{w\sqrt{|d|}}{2π}}L(1, χ), & if d < 0, \\ ^{\frac{\sqrt{d}}{log ϵ}}L(1, χ), & if d > 0, \end{matrix}  (143)

where d is a fundamental discriminant, χ is the character (\frac{d}{n}) and ϵ = \frac{1}{2}[t_{0} + u_{0}\sqrt{d}] is a fundamental solution of Pell’s equation. Note that the formula immediately implies that L(1, χ) > 0.

Additional remark : Nowadays, (143) is recognised as a special case of a general class-number formula in algebraic number theory. Let K be a number field. Then the formula says that

h = \frac{2^{r_{1}}(2π)^{r_{2}}R}{w\sqrt{d}}Res_{s=1}ζ_{K}(s).  (144)

Here h, R, d are the class number, regulator and discriminant of K resp., r_{1} (resp. 2r_{2}) is the number of real (resp. complex) imbeddings of K, w is the number of roots of unity in K and ζ_{K} is the Dedekind ζ-function of K. This last object is defined, for Re(s) > 1, as

ζ_{K}(s) = ∑ ; a \frac{1}{(Na)^{s}} ,  (145)

where a is an ideal in O_{K} and N : K → Q is the norm map. By the end of the course, you will hopefully understand what all these things mean ! Note that, if K = Q, then ζ_{K} = ζ, the ordinary Riemann zeta-function^{21}.

Quadratic forms in more than two variables

The general theory of quadratic forms over Z is very hard. Over Q however, things are pretty much understood (here the problem of counting representations is rather meaningless, but there is still an existence question, coupled with the problem of classifying forms up to equivalence). The methods in this latter case are algebraic. The classic Hasse-Minkowski theorem essentially reduces the study of forms over Q to the study of quadratic congruences. The methods carry over in part to arbitrary fields, and the recently proved Milnor conjecture (1996 ?) describes this procedure precisely (it is rather abstract). Over Z, we only get partial analogues of these results. These are most satisfying in the case of indefinite forms. The representation problem, though very hard, has essentially been solved by Siegel. But the problem of classification, for positive definite forms, remains an active

21In this course, we will not have time to discuss the analytic theory of the Riemann ζ-function and its’ generalisations. OK, we did a little analysis in proving Dirichlet’s theorem, but that’s just the beginning ! That one can really do full-blooded complex analysis with ζ follows from the facts, first proven by Riemann, that ζ has a meromorphic continuation to the whole s-plane and satisfies a functional eq. relating the values at s and 1 − s - see (6). These facts lead to the prime number theorem. They can be generalised to Dirichlet L-functions (for primitive characters) : this was done by Hurwitz (1872) for quadratic characters and in full by de la Vallée Poussin (1896). Hecke was the first (1910s) to extend these facts to L-functions for general number fields, in particular to the Dedekind ζ-function. He also considered more general types of ‘L-functions’, but his methods became very complicated. Around 1940, Chevalley introduced adèles and idèles into class field theory as a method of incorporating all the diverse results into a general framework. In 1947 Tate, in his thesis, defined zeta-functions as abstract integrals over idèle groups, and proved analytic continuation and a functional equation for these. In so doing, he incorporated all the results of his predecessors, from Riemann to Hecke.

A final remark : Dirichlet’s theorem on arithmetic progressions, in its’ strong form as a density statement (Theorem 32.A), extends naturally to all number fields. This is proven as in the classical case, and does not require the full analytic continuation of the Dedekind L-functions.

research area. Even for positive, integral forms of discriminant 1, the situation seems to be generally hopeless. For certain dimensions, there are well-known connections to the classical sphere-packing problem and to finite simple group theory. See, for example, Serre’s ‘A course in arithmetic’, or come to my doktorandkurs.

Here I just want to state two classical facts, and prove one of them.

Theorem 54 (Legendre/Gauss). A positive integer n is the sum of three squares if and only if it is not of the form 4^{j}(8k + 7), for some j, k ≥ 0.

Proof : Serre, Ch. IV, Appendix.

Theorem 55 (Lagrange 1770). Every positive integer is the sum of four squares.

Proof : Following Baker, p.39-40.

Remark : As with most (all ?) proofs of this theorem, Baker begins by reducing to primes via the identity in the middle of p.39. To understand where this identity really comes from, one should look at Hamilton’s quaternions H. Recall that these are defined by

H := {R+Ri+Rj +Rk : i^{2} = j^{2} = k^{2} = −1, ij = k, jk = i, ki = j}. (146)

H is thus a vector space of dimension 2 over C (or 4 over R), which can be proven to be a (non-commutative) division algebra. A classic theorem of Frobenius ([7], Theorem 7.3.1) states that every division ring, algebraic over R, is isomorphic to R, C or H.

Let α = x + yi + zj + wk := (x, y, z, w) ∈ H. The conjugate of α, denoted α^{∗}, is defined by α^{∗} := (x, −y, −z, −w). The following properties are easily verified :

[α^{∗}]^{∗} = α  (147)
αα^{∗} = x^{2} + y^{2} + z^{2} + w^{2} ∈ R  (148)
(αβ)^{∗} = β^{∗}α^{∗}.  (149)

Because of (148) we have a map N : H → R, called the norm map, given by N(α) := αα^{∗}. Eqs. (147) - (149) then easily imply that

N(αβ) = N(α)N(β),  (150)

which is equivalent to the identity used in the proof of the four-squares theorem.

Algebraic theory of number fields

For the rest of today’s class, I will just list the most important prerequisites from abstract algebra which will be required subsequently. No motivation or proofs will be provided, as you should have seen everything in the algebraic structures course.

Definition : An element π of an integral domain R is said to be irreducible if every divisor of π is of the form uπ, for some u ∈ R^{×}.

Definition : An element x of a domain R is said to be factorisable if x can be written as a product of irreducible elements in R.

We say that the domain R has the factorisation property (F) if every element in R is factorisable.

Definition : A ring R is said to be principally Noetherian if R has no infinitely ascending chain of principal ideals.

Proposition 56. If the domain R is principally Noetherian, then it has property (F).

Definition : R is called a unique factorisation domain (UFD) if R has property (F), and the factorisation of each element into irreducibles is unique up to units.

Remark : A UFD is a generalisation of Z. That Z is a UFD is the fundamental theorem of artithmetic.

An important class of UFDs are given by

Definition : A domain R is called Euclidean if there is a function d : R\{0} → N ∪ {0} such that

(i) ∀ a, b ≠ 0, d(a) ≤ d(ab).

(ii) ∀ a, b ∃ ! q, r such that a = qb + r and either r = 0 or d(r) < d(b). A Euclidean domain is also a principal ideal domain (PID), i.e.: every ideal is principal. Examples : Z is Euclidean with d(n) = |n|. For any field K, the polynomial ring K[x] is Euclidean with d(f) = degree of f. It can be shown that if R is a UFD, then so is the polynomial ring R[x]. Hence, by induction, the polynomial ring K[x_{1}, ..., x_{n}] in n variables over a field K is a UFD. However, it is only Euclidean if n = 1. Definition : An element p of a ring R is said to be prime if, for any a, b ∈ R, whenever p|ab then either p|a or p|b. Proposition 57. In any domain R, every prime element is irreducible. On the other hand Proposition 58. A domain R is a UFD if and only if R has property (F) and every irreducible element is prime. The following result gives an alternative ring-theoretic characterisation of the difference between the concepts of ‘prime’ and ‘irreducible’ : Proposition 59. (i) An element x in a ring R is prime iff R/ < x > is a domain. (ii) An element x ∈ R is irreducible ⇔ < x > is a maximal principal ideal. In particular, if R is a PID, then x ∈ R is irreducible ⇔ < x > is a maximal ideal ⇔ R/ < x > is a field. An important result now is Theorem 60. Every PID is a UFD.

Proof : This is something you may not have seen before. Let R be a PID. By Prop. 58, it suffices to show that R has property (F) and that every irreducible element is prime. The latter follows immediately from Prop.

59. The former is more tricky. By Prop. 56, it suffices to show that R is principally Noetherian. This will be proven later in the context of something more general (Prop. 77(ii)).

The basic difficulty in the algebraic study of number fields is

Proposition 61. The ring of integers in a number field is not always a UFD.

Proof : Without explaining the term ‘ring of integers’ (this will come later), consider the following well-known ring :

R = Z[\sqrt{−5}]. It can be shown that R is the ring of integers O_{K} in K = Q(\sqrt{−5}). In R we have two alternative factorisations of the number 6, namely

6 = 2 · 3 = (1 + \sqrt{−5}) · (1 − \sqrt{−5}).  (151)

One must check that all four numbers in these factorisations are irreducible in R. This is most easily done by considering the norm of each number. The norm is the function N : R → Z given by

N[a + b\sqrt{−5}] = (a + b\sqrt{−5})(a − b\sqrt{−5}) = a^{2} + 5b^{2}.  (152)

One checks readily that N(xy) = N(x)N(y) for all x, y ∈ R. Using this, one shows irreducibility of all four numbers. It follows that all four numbers are irreducible but not prime (see Prop. 58).

Note also that R is not a PID ; for example, the ideal < 2, 1 + \sqrt{−5} > is easily shown to be not principal (see supplementär övning nr. 15).

This completes the list of prerequisites.

Remark 1 : Although a ring of integers R need not be either a UFD or a PID, it is always in some sense close to being both.

First, every such R has a property called unique factorisation of ideals. This is because R is a Dedekind domain, a type of abstract commutative ring which always has this property. We will prove these facts in this course.

Second, associated to each number field K is a positve integer h_{K} called its class number. The fraction of the ideals in O_{K} which are principal is precisely 1/h_{K}. In fact one can prove (and we will do so) that

O_{K} is a UFD ⇔ O_{K} is a PID ⇔ h_{K} = 1.

The hardest part of the theory is in fact the proof that h_{K} is finite, for every number field K. We will probably not have time to do this.

Remark 2 : In 1847, Lamé gave a notorious wrong proof of Fermat’s Last Theorem^{22}. His proof assumed implicitly that one had unique factorisation in the cyclotomic fields Q(ζ_{p}) where p is an odd prime. It was subsequently shown that p = 23 is the first odd prime for which h(Q(ζ_{p})) ≠ 1^{23}. Soon after, Kummer gave a correct proof of FLT for so-called regular prime exponents. A prime p is said to be regular if p † h(Q(ζ_{p})). Intuitively, it is a prime for which Q(ζ_{p})) does not fail to be a UFD ‘too badly’. There seem to be many regular primes : the only irregular ones less than 100 are 37,59,67. Nevertheless, the following remains open to this day

Conjecture. There are infinitely many regular primes.

Remark 3 : The main tool for computing class numbers is the analytic class number formula (144). Of course, this formula also implies that h is finite, but the usual way of proving this is by using geometric ideas developed by Minkowski (see, for example, Stewart and Tall, Ch. 6 ff). Actually, Minkowksi’s motivation for developing these ideas was in order to have a ‘geometric’ reduction theory for (positive definite) quadratic forms of arbitrary rank n > 2 (see Appendix 1).

References [7] I.N. Herstein, Topics in algebra, Wiley 1975.

22Unlike most of the modern-day wrong proofs of FLT, this one was not the work of a nutcase amateur. Lamé was a professional mathematician working alongside such famous people as Cauchy at the Académie in Paris.

23I am not quite certain of the timing or sequence of events here. In one book I read that Kummer proved the failure of unique factorisation for p = 23 and published his proof for regular primes in 1847. In another book, I read that Cauchy did the former, and that Kummer’s paper came in 1850. I also read in one place that Lamé gave a correct proof of FLT for p = 7 in 1839, but somewhere else that his proof had errors which were corrected by Lebesgue in 1840. The one thing which does not seem to be in any doubt is that the main breakthrough was Kummer’s.

80 Notation : Under kommande lektioner ska följande notationer användas :

A,B,C,R,S,... ska beteckna ringar. a,b,c,I,J ska beteckna (fraktionella) idéal. p,q,... ska beteckna prima idéal. F,K,L,... ska beteckna kroppar. L,M,N,... ska beteckna moduler. V,W,... ska beteckna moduler över kroppar, dvs vektor rum. Små bokstaver, i vanlig font, ska beteckna element i dessa objekt.

Konvention : Alla ringar är kommutativa och har ettor.

Definition : Låt R vara en ring, M en abelsk grupp. M kallas för en modul över R, eller en R-modul, om det finns en avbildning

\begin{matrix}R × M & → & M \\ (r, m) & ↦ & rm, \end{matrix}

som satisfierar följande villkor

\begin{matrix}(i) & r(m_{1} + m_{2}) = rm_{1} + rm_{2}, ∀ r ∈ R, ∀ m_{1}, m_{2} ∈ M. \\ (ii) & (rs)m = r(sm), ∀ r, s ∈ R, ∀ m ∈ M. \\ (iii) & (r + s)m = rm + sm, ∀r, s ∈ R, ∀ m ∈ M. \\ (iv) & 1 · m = m, ∀ m ∈ M. \end{matrix}

Exempel : (i) R = K en kropp. Då kallas M för ett vektor rum över K.

(ii) R = Z. En Z-modul är just en vanlig abelsk grupp.

(iii) Låt A ⊆ B vara ringar. Då kan B betraktas som en A-modul.

(iv) Låt M vara en R-modul, N en delmängd till M som är sluten under modul operationerna. Då kallas N för en R-delmodul till M.

Om N ⊆ M är en delmodul, då får kvotgruppen M/N också strukturen av en R-modul genom att sätta

r(N + m) := N + rm, ∀ r ∈ R, ∀ m ∈ M.

Den kallas för kvotmodulen av M genom N.

(v) Låt A vara en ring, En delmängd I ⊆ A som är en A-delmodul under ring operationerna i A kallas för ett idéal. Kvotet A/I är då också en A-modul. Den är också en ring.

(vi) Låt M, N vara R-moduler. Deras direkt summa M ⊕ N är, som en mängd, den kartesiska produkten M × N, och den blir en R-modul genom att definiera

(m_{1}, n_{1}) + (m_{2}, n_{2}) := (m_{1} + m_{2}, n_{1} + n_{2}), ∀ m_{1}, m_{2} ∈ M, ∀ n_{1}, n_{2} ∈ N, r(m, n) := (rm, rn) ∀ r ∈ R, ∀ m ∈ M, ∀ n ∈ N.

Notation : Om M är en R-modul, då skriver man ibland M/R, när detta kan inte misstolkas som en kvotmodul.

Definition : Låt M vara en R-modul. Låt X = {x_{λ}}_{λ∈Λ} vara en delmängd till M. Man säger att X genererar M om varje element av M kan skrivas som en ändlig linjär kombination av element från X ; dvs för varje m ∈ M, finns det λ_{1}, ..., λ_{n} ∈ Λ och r_{1}, ..., r_{n} ∈ R så att

m = r_{1}x_{λ_{1}} + ⋯ + r_{n}x_{λ_{n}}.

Man säger att M/R är ändligt genererad om den kan genereras av en ändlig delmängd.

Exempel : (i) Ett vektor rum V/K är en ändligt genererad K-modul omm dim_{K}V < ∞.

(ii) Q/Z är inte ändligt genererad. För låt p_{1}/q_{1}, ..., p_{n}/q_{n} ∈ Q, där (p_{i}, q_{i}) = 1. Antag att talet r kan skrivas som en Z-linjär kombination av dessa, där r = p/q i lägsta termer. Då finns det t_{1}, ..., t_{n} ∈ Z så att

\frac{p}{q} = \frac{t_{1}p_{1}}{q_{1}} + ⋯ + \frac{t_{n}p_{n}}{q_{n}} ,
⇒ \frac{p}{q} = _{\frac{z}{∏_{i=1}^{n} q_{i}}} , för något z ∈ Z,
⇒ q| ∏_{i=1}^{n} q_{i}.

Då kan p/q ej skrivas som en Z-linjär kombination av {p_{i}/q_{i}} om q är tillräckligt stor.

Definition : En mängd X = {x_{λ}}_{λ∈Λ} kallas för en bas till R-modulen M om varje element av M har ett unikt uttryck som en R-linjär kombination av element från X.

Ekvivalent, X är en bas till M om X genererar M och, för alla λ_{1}, ..., λ_{k} ∈ Λ,

r_{1}x_{λ_{1}} + ⋯ + r_{k}x_{λ_{k}} = 0 ⇒ r_{1} = ⋯ = r_{k} = 0.  (153)

Definition : Låt M, N vara R-moduler. En avbildning ϕ : M → N kallas för en R-modul homomorfism om

∀r ∈ R, ∀m_{1}, m_{2} ∈ M, ϕ[r(m_{1} + m_{2})] = r[ϕ(m_{1}) + ϕ(m_{2})]. (154)

Om ytterligare ϕ är surjektiv då kallas det för en R-modul epimorfism. Om ϕ är bijektiv då kallas det för en R-modul isomorfism. I så fall, skriver man M ≅_{R} N.

1:a isomorfism sats för moduler. Låt M, N vara R-moduler, ϕ : M → N en R-modul homomorfism. Då,

(i) Im(ϕ) är en R-delmodul till N.

(ii) Ker(ϕ) är en R-delmodul till M.

(iii) ϕ inducerar en R-modul isomorfism M/ker(ϕ) ≅_{R} im(ϕ).

Bevis : Övning.

Definition : En R-modul M sägs vara fri av rang n ≥ 0 om M ≅_{R} R^{n}, den direkta summan av n kopior av R (notera att vi menar isomorfism av moduler här, trots att R^{n} också har en ring struktur).

Proposition 62. (i) En R-modul M är ändligt genererad omm det finns n ≥ 0 och en R-delmodul I ⊆ R^{n} så att M ≅_{R} R^{n}/I (här menar vi bara isomorfism av moduler igen).

(ii) M är fri av rang n omm den har en bas som består av n element.^{24} Obs! Modulen I i denna proposition är en R-modul, INTE ett ideal i R^{n}, dvs en R^{n}-modul.

24I allmänhet, låt ℵ vara en kardinal. Då sägs en R-modul M vara fri av rang ℵ om M har en bas av kardinalitet ℵ ; ekvivalent, är M ≅_{R} R^{ℵ}, den direkta summan av ℵ kopior av R. Notera att man tillåter bara ändliga summor av bas elementen i den direkta summan så att det är inte samma sak som den direkta produkten R̄^{ℵ}, om ℵ är en oändlig kardinal (kom ihåg att den direkta produkten R̄^{ℵ} är, som en mängd, den kartesiska produkten av

Exempel : (i) Ett vektor rum V/K är fri av rang n omm dim_{K}V = n^{25}.

(ii) En modul M/R kallas för torsion-fri om, för alla r ∈ R, m ∈ M, rm = 0 ⇒ m = 0. En fundamental sats i abstrakt algebra är att, om R är en huvudidéal domän, då är varje ändligt genererad torsion-fri R-modul faktiskt fri. Det viktigaste fallet är när R = Z^{26}. Till exempel, ska vi se senare att heltalsringen i en algebraisk talkropp är ändligt genererad som en abelsk grupp, alltså en fri Z-modul (som en delmängd till en kropp av karakteristisk noll, måste den vara torsion-fri). Men vi skall kunna bevisa frihet på ett alternativt sätt som undvikar denna allmäna satsen.

Proposition 63. Låt A, B, C vara ringar, A ⊆ B ⊆ C. Om både B/A och C/B är ändligt genererade, då gäller detsamma för C/A.

Bevis : Låt b_{1}, ..., b_{m} generera B/A, och c_{1}, ..., c_{n} generera C/B. Då bevisar man lätt att {b_{i}c_{j}} genererar C/A.

Anmärkning : Om A, B, C är kroppar eller, mer allmänt, om både B/A och C/B är fria moduler, då är C/A också fri och

[C : A] = [C : B][B : A],  (155)

där [M : N] betecknar rangen av M som en fri N-modul. Idéen av beviset är att välja baser för B/A och C/B och använda samma argument som ovan. Man måste bevisa att produkterna {b_{i}c_{j}} är linjärt oberoende över A. Jag hoppas att ni har sett formel (155) och dess bevis för kroppar i algebraiska strukturer !

ℵ kopior av R, och addition och multiplikation definieras komponentvis. Som en R-modul är den aldrig fri om ℵ ≥ ℵ_{0} (en övning !)).

Mer allmänt, kan M genereras av en delmängd X av kardinalitet ℵ omm M ≅_{R} R^{ℵ}/I för någon R-delmodul I ⊆ R^{ℵ}.

25Det kan bevisas att varje vektor rum över en kropp har en bas och att alla baser har samma kardinalitet, som kallas för dimensionen av rummet. Det krävs Valaxiomet, i formen av Zorns lemma, för att bevisa detta i allmänhet.

26Läget är mycket mer komplicerad för oändligt genererade moduler, till och med över Z. En oändligt genererad torsion-fri abelsk grupp behöver inte ens ha en icke-trivial direkt faktor. Det finns också det notoriska exemplet av en abelsk grupp A så att A ≅ A⊕A⊕A, men A ≅ A̸ ⊕ A. Se en godtycklig algebra bok på doktorandsnivån för vidare diskussion.

Integrala utvidningar

Definition : Låt A ⊆ B vara ringar. Ett element x ∈ B kallas för integral över A om x satisfierar ett moniskt polynom med koefficienter från A ; dvs,

x^{n} + a_{n−1}x^{n−1} + ⋯ + a_{1}x + a_{0} = 0,  (156)

för något n > 0, a_{0}, ..., a_{n−1} ∈ A.

Proposition 64. Låt A ⊆ B och x ∈ B. Då är följande ekvivalenta :

(i) x är integral över A. (ii) A[x]/A är ändligt genererad. (iii) Det finns en delring C ⊆ B så att A[x] ⊆ C och C/A är ändligt genererad.

Bevis : Gavs i föreläsningen. Den svåraste delen är (iii) ⇒ (i). Man tar en mängd av generatorer x_{1}, ..., x_{k} för C/A och introducerar element a_{ij} ∈ A genom xx_{i} = ∑ a_{ij}x_{j}. Då har man en matris ekvation

(xI_{k} − M) ( \begin{matrix}x_{1} \\ · \\ · \\ x_{k} \end{matrix} ) = 0,  (157)

där M = (a_{ij}). Sätt N = xI_{k} − M, och multiplicera båda sidor av (157) med adj N, så att man får att (det N)c = 0 för alla c ∈ C. Speciellt, kan man ta c = 1, som betyder att det N = 0. Detta ger ett moniskt polynom över A som satisfieras av x.

Definition : (i) Låt A ⊆ B. Mängden av element i B som är integrala över A kallas för det integrala höljet av A i B och betecknas Ā^{B}. (ii) B sägs vara en integral utvidning av A, eller integral över A, om Ā^{B} = B. (iii) A sägs vara integralt sluten i B om Ā^{B} = A. (iv) En domän A kallas helt enkelt för integralt sluten om Ā^{K} = A, där K är kvotkroppen av A.

Viktigt exempel : Z är integralt sluten (kvotkroppen är Q). För låt x ∈ Q vara integral över Z. Säg att x = p/q i lägsta termer, och att x satisfierar det moniska polynomet

(\frac{p}{q})^{n} + a_{n−1} (\frac{p}{q})^{n−1} + ⋯ + a_{1} \frac{p}{q} + a_{0} = 0, där a_{i} ∈ Z.

Multiplicera båda sidor med q^{n−1} och man får att p^{n}/q ∈ Z ⇒ q = 1 (ty (p, q) = 1) ⇒ x ∈ Z.

Nästa resultat följer (med något arbete !) från Prop. 63 och 64 :

Sats 65. (i) Låt A ⊆ B ⊆ C. Om B/A och C/B är integrala, då gäller detsamma för C/A. (ii) Låt A ⊆ B. Då är Ā^{B} en ring som innehåller A. Dessutom är Ā^{B} integralt sluten i B.

Mängden som består av alla lösningar till alla möjliga moniska polynom över en ring A kallas för DET integrala höljet av A och betecknas med \overline{A}. Det följer från Sats 65 att Ā har en väl-definierad ring struktur.

Exempel : \overline{C} = C. Detta är Algebrans Fundamentalsats.

Kroppar

När man betraktar kroppsutvidningar K ⊆ L, brukar man använda man ordet ‘algebraisk’ i stället för ‘integral’. Alltså används termerna algebraisk utvidning, algebraiskt hölja, algebraiskt sluten i stället för motsvarande termerna ovan.

Proposition 66. Låt K ⊆ L vara kroppar. Då är K̄^{L} en delKROPP av L.

Bevis : (se också Lemma 80) Vi vet redan från Sats 65(ii) att K̄^{L} är en delring till L. Låt 0 ≠ x ∈ K̄^{L}. Det kvarstår att bevisa att x^{−1} ∈ K̄^{L}. Låt

x^{n} + k_{n−1}x^{n−1} + ⋯ + k_{1}x + k_{0} = 0

vara ett moniskt polynom över K av minimal grad som satisfieras av x. Vi måste ha k_{0} ≠ 0 - annars skulle x vara en faktor av den vänstra sidan, som kunde tas ut för att få ett moniskt polynom av mindre grad som satisfieras av x. Dela nu båda sidor med k_{0}x^{n} så får man att

(x^{−1})^{n} + \frac{k_{1}}{k_{0}} (x^{−1})^{n−1} + ⋯ + \frac{k_{n−1}}{k_{0}} x^{−1} + \frac{1}{k_{0}} = 0,

som antyder att x^{−1} ∈ K̄^{L}, v.s.v.

Definition : Om K/Q är en kroppsutvidning med [K : Q] < ∞, då kallas K för en talkropp. Ett element av en talkropp kallas för ett algebraiskt tal.

Algebrans fundamentalsats antyder att \overline{Q} ⊆ C, och är faktiskt en delkropp av C enligt Prop. 66. Ett komplext tal z ∈ C är ett algebraiskt tal omm

z ∈ \overline{Q} = ⋃_{K en talkropp} K.

Definition : Ett komplext tal z som inte är algebraiskt kallas för transcendental. Vi skall diskutera transcendentala tal senare. Under kommande lektioner blir algebraiska tal vårt största intresse.

Notation : K(x) denotes the field obtained by adjoining an indeterminate x to the field K. That is,

K(x) = \{\frac{p(x)}{q(x)} : p, q ∈ K[x], q ≠ 0\} .  (158)

In other words, K(x) is the quotient field of K[x].

First, we need to recall some general facts which you learned in algebraic structures :

Let K ⊆ L be fields, α ∈ L which is algebraic over K. Let

I = {p(x) ∈ K[x] : p(α) = 0}.  (159)

Then I is an ideal in K[x], hence a principal ideal. Hence there exists a unique monic polynomial p_{0}(x) ∈ K[x] which is irreducible over K and generates the ideal I. It is called the minimal polynomial of α over K. We have

K[α] = K(α) ≅ K[x]/I.  (160)

Moreover, if α = α_{1}, α_{2}, ..., α_{n} are the roots of p_{0}(x) in some extension field of K over which p_{0} splits, then all α_{i} are distinct and each has minimal polynomial p_{0}.

Okay, that’s enough facts. An important technical result about number fields^{27} is the following :

Theorem 67. Let K ⊆ L be number fields. Then there exists α ∈ L such that L = K(α).

Remark : In other words, there exists α ∈ L such that the minimal polynomial of α over K has degree [L : K].

Proof : Since L/K is a finite-dimensional vector space, there certainly exists a finite set of elements α_{1}, ..., α_{n} ∈ L such that L = K(α_{1}, ..., α_{n}) - for example, choose a basis of L/K. Hence, it suffices to prove the result when L = K(α, β), for some PAIR of elements α, β, because we then just proceed by induction on the number of elements in a generating set.

27In fact, the result applies to any pair of infinite fields, as long as one is a finite extension of the other. In particular, it applies to fields of characteristic zero (since these contain a copy of Q). This will become clear from the proof.

Let p(x), q(x) be the minimal polynomials of α, β resp. over K, say of degrees n, m resp. Over C we have splittings

p(x) = ∏_{i=1}^{n}(x − α_{i}), α = α_{1}, α_{i} distinct,

q(x) = ∏_{j=1}^{m}(x − β_{j}), β = β_{1}, β_{j} distinct.

For each pair of indices (i, j) ≠ (1, 1), there is at most one solution x ∈ L to the equation

α_{i} + xβ_{j} = α + xβ.  (161)

As K is an infinite field, we can pick γ ∈ K which does not satisfy any of these equations. Put θ = α + γβ. We claim that L = K(θ).

To prove this, it suffices to prove that β ∈ K(θ), because then α = θ − γβ ∈ K(θ) and so L = K(α, β) ⊆ K(θ). To prove that β ∈ K(θ) it suffices to show that the minimal polynomial of β over K(θ) has degree one.

So consider the polynomials q(t), r(t) ∈ K(θ)[t] defined by

q(t) := q(x)|_{x=t},
r(t) := p(θ − γt).

Observe that q(β) = r(β) = 0. Hence the minimal polynomial of β over K(θ) must be a common divisor of q(t) and r(t). We claim that the gcd of these polynomials has degree one ; equivalently, they have no common root in C other than β.

So suppose that q(ξ) = r(ξ) = 0 with ξ ≠ β :

On the one hand, ξ is a root of q(t) so

ξ = β_{j}, for some j, 2 ≤ j ≤ m.  (162)

On the other hand, r(ξ) = p(θ − γξ) = 0, so

θ − γξ = α_{i}, for some i, 1 ≤ i ≤ m.  (163)

From (162) and (163) we deduce that γ satisfies one of the equations (161), a contradiction. This completes the proof.

Embeddings

Definition : Let K be a number field. An injective field homomorphism ϕ : K → C is called an embedding of K.

Notation : Let ϕ : K → C be an embedding. The fixed field of ϕ, denoted F_{ϕ}, is defined by

F_{ϕ} = {x ∈ K : ϕ(x) = x}.  (164)

That F_{ϕ} IS a field follows immediately from the fact that ϕ is a field homomorphism.

Proposition 68. Let K be any number field. Then

Q = ⋂ ; ϕ an embedding of K F_{ϕ}.  (165)

Proof : First we prove that Q ⊆ r.h.s. Let ϕ be an embedding of K. Then ϕ(1) = 1 since ϕ is injective. Since ϕ is additive, we thus have ϕ(n) = n for all n ∈ Z. Finally, ϕ (\frac{m}{n}) = \frac{ϕ(m)}{ϕ(n)} = \frac{m}{n}.

The proof of the reverse inclusion is postponed until after the next result, which characterises all embeddings of K.

Proposition 69. Let K be a number field, say [K : Q] = n. Pick α ∈ K so that K = Q(α). Let p(x) be the minimal polynomial of α over Q. Over C, let p(x) split as

p(x) = ∏_{i=1}^{n}(x − α_{i}), α = α_{1}, α_{i} distinct.

Let ϕ be an embedding of K. Then ϕ(α) = α_{i} for some i, and this choice completely determines ϕ. In particular, K has precisely n embeddings.

Proof : That ϕ(α) = some α_{i} follows from the fact that

ϕ(0) = 0 = ϕ(p(α)) = p(ϕ(α)),

which implies that ϕ(α) is a root of p(x). Now suppose ϕ(α) is given. Any element of K has a unique representation as a polynomial in α of degree < n, with coefficients in Q. Since Q ⊆ F_{ϕ} and ϕ is a field homomorphism, we have that

ϕ (∑ a_{i}α^{i}) = ∑ a_{i}(ϕ(α))^{i}, (a_{i} ∈ Q),

which proves that ϕ is completely determined by ϕ(α).

Definition : An embedding ϕ of the number field K is called real if ϕ(K) ⊂ R. Otherwise, ϕ is called complex.

The number of real (resp. complex) embeddings of K is denoted by r_{1} (resp. 2r_{2}). From Prop. 69 we see that

r_{1} = # real embeddings = #{i : α_{i} ∈ R},
2r_{2} = # complex embeddings = #{i : α_{i} ∉ R}.  (166)

Proof of prop. 68 (ctd.) : Let [K : Q] = n, say K = Q(α). Let θ ∈ K. Then θ has a unique expression as a polynomial in α, of degree < n, with rational coefficients, say

θ = f(α) = ∑_{i=0}^{r} a_{i}α^{i}, where r < n.

Let ϕ be an embedding of K, and suppose that ϕ(θ) = θ. In the notation of Prop. 69, there is some i, 1 ≤ i ≤ n, such that ϕ(α) = α_{i}. Hence,

f(α) = θ = ϕ(θ) = ϕ(f(α)) = f(ϕ(α)) = f(α_{i}).  (167)

Now let g(x) := f(x)−θ, so that g is polynomial of degree r with coefficients in K. From (167) we see that, if θ is fixed by every embedding of K, then g(α_{i}) = 0 for i = 1, ..., n. Thus g has at least n distinct roots, but as g is of degree r < n, this is only possible if g ≡ 0, the zero polynomial. Thus f(x) = θ is a constant polynomial with rational coefficients, so that θ ∈ Q. This completes the proof.

Definition : A number field K is said to be Galois over Q if ϕ(K) = K for every embedding ϕ of K.

If K/Q is Galois, then the embeddings of K form a group of field automorphisms of K under composition. This group is called the Galois group of K over Q and is denoted Gal(K/Q).

The discriminant

Definition : Let K be a number field, [K : Q] = n. Let ϕ_{1}, ..., ϕ_{n} be the embeddings of K, in some order. Let B = {α_{1}, ..., α_{n}} be a basis for K as a vector space over Q. The discriminant of the basis B is defined and denoted by

Δ(α_{1}, ..., α_{n}) := [det(ϕ_{i}(α_{j}))]^{2} .  (168)

Proposition 70. The discriminant of a basis is well-defined, i.e.: it does not depend on the ordering of the ϕ_{i} or of the α_{i}.

Proof : Choosing a different ordering of the ϕ’s corresponds to a permutation π of the rows of the matrix A = (ϕ_{i}(α_{j})). If A^{π} denotes the permuted matrix, then we all know from linear algebra that

det A^{π} = (−1)^{sgnπ} det A.  (169)

Since, for Δ, we take the square of the determinant, we see that the result is independent of the permutation π. The same argument applies to a permutation of the α_{i} - this corresponds to a permutation of the columns in A, q.e.d.

Theorem 71. The determinant of any basis is a non-zero rational number.

Proof : First, we show that Δ ∈ Q. We will only do this under the extra assumption that K/Q is Galois^{28}. In this case, the proof is easy. By Prop. 68, it suffices to show that ϕ(Δ) = Δ for every embedding ϕ of K. But in the Galois case, application of ϕ serves only to reorder the rows of the matrix defining Δ. The argument used to prove Prop. 70 implies that Δ is thereby left unchanged.

The second part is to show that Δ ≠ 0. This part involves two steps :

28In the general case, one first notes that the determinant (170) is a symmetric polynomial in the θ_{i}. One then applies a result on symmetric polynomials to conclude that this determinant is a rational number (see handout nr. 12). Finally, one uses (173) to conclude that the discriminant of ANY basis is rational.

Step 1 : We show that Δ ≠ 0 for a special type of basis. We pick θ ∈ K such that K = Q(θ) and consider the basis {1, θ, ..., θ^{n−1}}. Let θ = θ_{1}, θ_{2}, ..., θ_{n} be the (distinct) roots of the minimal polynomial of θ over Q. Let ϕ_{i} be the unique embedding (see Prop. 69) such that ϕ_{i}(θ) = θ_{i}. Then

Δ(1, θ, ..., θ^{n−1}) = | \begin{matrix}1 & θ_{1} & ⋯ & θ_{1}^{n−1} \\ 1 & θ_{2} & ⋯ & θ_{2}^{n−1} \\ · & · & & · \\ · & · & & · \\ 1 & θ_{n} & ⋯ & θ_{n}^{n−1} \end{matrix} |^{2} .  (170)

But this determinant is of Vandermonde type and so we have that

Δ(1, θ, ..., θ^{n−1}) = [ ∏_{1≤i<j≤n}(θ_{i} − θ_{j})]^{2} ≠ 0,  (171)

since the θ_{i} are distinct.

Step 2 : We give a formula relating the discriminants of two different bases. So let B_{1} = {α_{1}, ..., α_{n}}, B_{2} = {β_{1}, ..., β_{n}} be two different bases for K/Q. Let M = (m_{ij}) ∈ GL_{n}(Q) be the change of basis matrix from B_{1} to B_{2}, i.e.:

β_{i} = ∑_{j=1}^{n} m_{ij}α_{j}.

Applying an embedding ϕ_{i} we obtain that

ϕ_{i}(β_{j}) = ϕ_{i} (∑_{k=1}^{n} m_{jk}α_{k}) = ∑_{k=1}^{n} m_{jk}ϕ_{i}(α_{k}).  (172)

From (172) we see that the matrices B = (ϕ_{i}(β_{j})) and A = (ϕ_{i}(α_{j})) are related by

B = AM^{T} .

From this, it follows immediately that

Δ(β_{1}, ..., β_{n}) = (det M)^{2}Δ(α_{1}, ..., α_{n}).  (173)

In particular, since det M ≠ 0, we see that one discriminant is non-zero if and only if the other is. Since we have in Step 1 produced at least one basis with a non-zero discriminant, it follows that the discriminant of any basis is non-zero. This completes the proof of Theorem 71.

Remark : The discriminant of a basis need not be a POSITIVE rational number. For example, let d be an integer which is not a perfect square, and take K = Q(\sqrt{d}). Then [K : Q] = 2 since the minimal polynomial of \sqrt{d} over Q is x^{2} − d = 0. The roots of this equation are ±\sqrt{d}, so K has two embeddings completely determined by

ϕ_{1}(\sqrt{d}) = \sqrt{d}, ϕ_{2}(\sqrt{d}) = −\sqrt{d}.

In particular, K/Q is Galois. Now consider the basis \{1, \sqrt{d}\} of K as a Q-vector space. The discriminant of this basis is given by

Δ(1, \sqrt{d}) = | \begin{matrix}ϕ_{1}(1) & ϕ_{1}(\sqrt{d}) \\ ϕ_{2}(1) & ϕ_{2}(\sqrt{d}) \end{matrix} |^{2} = | \begin{matrix}1 & \sqrt{d} \\ 1 & −\sqrt{d} \end{matrix} |^{2} = 4d,  (174)

which is > 0 iff d > 0.

The ring of integers

Definition : Let K be a number field. The integral closure of Z in K is called the ring of integers of K, and is denoted O_{K}. To avoid confusion, elements of Z (i.e.: ordinary integers) are often called rational integers in algebraic number theory.

Proposition 72. (i) O_{K} IS a subring of K containing Z. (ii) O_{K} ∩ Q = Z. (iii) Let α ∈ K. Then there exists 0 ≠ n ∈ Z such that nα ∈ O_{K}.

Proof : (i) Follows from the more general Sats 65(ii).

(ii) Follows from the fact that Z is integrally closed (proven last day).

(iii) α is algebraic over Q, hence satisfies some polynomial with rational coefficients, hence (by clearing denominators) some polynomial with integer coefficients, say

a_{n}α^{n} + a_{n−1}α^{n−1} + ⋯ + a_{1}α + a_{0}, a_{i} ∈ Q, a_{n} ≠ 0.

Multiply through by a_{n}^{n−1} and you will get an equation of the form

(a_{n}α)^{n} + b_{n−1}(a_{n}α)^{n−1} + ⋯ + b_{1}(a_{n}α) + b_{0} = 0,

for some integers b_{i}. This says that a_{n}α satisfies a monic polynomial over Z, hence lies in O_{K}.

Remark : From (iii) of Prop. 72, it follows that there exist bases of K/Q consisting of elements of O_{K}. Any such basis of K/Q is called an integral basis^{29}.

The main result of today’s lecture is the following theorem giving the structure of O_{K} as an additive group.

Theorem 73. O_{K} is a free abelian group of rank [K : Q].

Proof : Let [K : Q] = n. Let B = {α_{1}, ..., α_{n}} be an integral basis for K. Let ϕ be an embedding of K. Since each α_{i} satisfies a monic polynomial over Z, by the usual type of argument the same is true of each ϕ(α_{i}). It follows that Δ(B) ∈ \overline{Z}, the integral closure of Z in C. But Theorem 71 says that Δ(B) ∈ Q^{×}. Hence, Δ(B) ∈ Q^{×} ∩ \overline{Z} = Z^{×}.

It follows that there exists an integral basis B_{0} = {θ_{1}, ..., θ_{n}} for which |Δ(B_{0})| is minimal. We claim that any such B_{0} is also a Z-basis for O_{K}.

First, since the θ_{i} form a Q-basis of K, in particular they are linearly independent over Q, hence over Z also. It remains to show that they generate the Z-module O_{K}.

We argue by contradiction. So suppose there exists w ∈ O_{K}, w ∉ Zθ_{1} ⊕ ⋯ ⊕ Zθ_{n}. Since B_{0} is a Q-basis for K, there must exist rational numbers r_{1}, ..., r_{n} such that

w = r_{1}θ_{1} + ⋯ + r_{n}θ_{n}.

WLOG, r_{1} ∉ Z. Let z_{1} := ⌊r_{1}⌋, r_{1} = z_{1} + r, where 0 < r < 1. Define a new integral basis B_{1} = {ψ_{1}, ..., ψ_{n}} by

ψ_{1} = w − r_{1}θ_{1}, ψ_{i} = θ_{i}, i = 2, ..., n.

It is easily verified that B_{1} IS, in fact, an integral basis for K. The change of basis matrix from B_{0} to B_{1} is given by

29Do not confuse an integral basis with a basis for O_{K} as a free Z-module (see Theorem 73). A basis of the latter type is always an integral basis, but not conversely. In fact, Prop. 74 gives the precise condition for an integral basis to be a Z-basis of O_{K}.

M = ( \begin{matrix}r & r_{2} ⋯ r_{n} \\ ⋮ 0 ⋮ & I_{n−1} \end{matrix} ) ,

so that det M = r. By (173), we see that Δ(B_{1}) = r^{2}Δ(B_{0}), which contradicts the minimality of |Δ(B_{0})|. This completes the proof of the theorem.

Definition : The positive integer given by the minimum absolute value of the discriminant of an integral basis is called, quite simply, the discriminant of K, and is denoted d_{K}.

The discriminat of a number field is an important invariant. Some of its’ properties will be discussed in due course, either in the main text or in the form of footnotes.

Proposition 74. Let {α_{1}, ..., α_{n}} be an integral basis for K. Then |Δ(α_{1}, ..., α_{n})| = d_{K} if and only if {α_{1}, ..., α_{n}} is a Z-basis for O_{K}.

Proof : The ‘only if’ part follows from the proof of Theorem 73.

For the ‘if’ part, let B_{0} be any integral basis which is also a Z-basis for O_{K}. Let B_{1} be a Z-basis for O_{K} for which |Δ(B_{1})| = d_{K}.

Since B_{0} and B_{1} are both Z-bases for O_{K}, the change of basis matrix M from B_{0} to B_{1} must have integer entries, and the same is true of M^{−1}. It follows that det M = ±1. From (173), it now follows that |Δ(B_{1})| = |Δ(B_{0})| = d_{K}. q.e.d.

Ideal

Notation : Låt R vara en ring. Mängden av alla ideal i R ska betecknas med I(R). Mängden av prima ideal (se definitionen nedan) i R ska betecknas Spec(R), och kallas för spektrum av R. Denna terminologi är mest vanlig i algebraisk geometri.

Definition : Låt a,b ∈ I(R). Sätt

ab := {∑_{i=1}^{n} a_{i}b_{i} : a_{i} ∈ a, b_{i} ∈ b} .  (175)

Detta är också ett ideal som kallas för produkten av idealen a och b.

Proposition 75. (i) Ideal multiplikation ger I(R) strukturen av en kommutativ monoid med enhet (unity) R själv. (ii) ab ⊆ a ∩ b.

Bevis : Del (i) säger att

1. ab = ba.

2. (ab)c = a(bc).

3. Ra = aR = a.

Alla tre egenskaper följer lätt från definitionen. Detsamma gäller för del (ii).

Ett av våra stora mål är att utvidga I(R) till en grupp, dvs att införa ‘inverser’ av ideal, i fallet där R = O_{K} för någon talkropp K. Vi återkommer till detta.

Definition : (i) Ett ideal I i en ring R kallas för prim om, för alla x, y ∈ R, xy ∈ I ⇒ x ∈ I eller y ∈ I. (ii) Idealet I kallas för maximalt om I ≠ R och, för varje ideal J så att I ⊆ J ⊆ R, antingen J = I eller J = R.

Proposition 76. (i) I prim ⇔ R/I är en domän. Speciellt, R är en domän omm {0} är ett primt ideal. (ii) I maximal ⇔ R/I är en icke-trivial kropp. Speciellt, R är en icke-trivial kropp omm {0} är ett maximalt ideal. (iii) Om p är ett primt ideal och a_{1}, ...,a_{n} är godtyckliga ideal så att p ⊇ a_{1} ⋯ a_{n}, då måste p ⊇ a_{i} för något i.

Bevis : (i) och (ii) är triviala. För (iii), antag att ingen av a_{1}, ..., a_{n−1} ⊆ p. Välj x_{i} ∈ a_{i} − p. Låt nu y ∈ a_{n}. Eftersom x_{1} ⋯ x_{n−1}y ∈ a_{1} ⋯ a_{n} ⊆ p, så måste minst en av termerna i produkten vara i p, enligt definitionen av ett prim idéal. Därför måste faktiskt y ∈ p, v.s.v.

Propositionen säger speciellt att varje maximalt ideal är prim. Existens av maximala ideal (och därför prima ideal) i en godtyclkig ring följer från Zorn’s Lemma - efterom om I_{1} ⊆ I_{2} ⊆ ⋯ utgör en växande följd av ideal, då är deras union ∪I_{n} också ett ideal.

Definition : En ring R kallas för Noetersk om R innehåller ingen oändlig strängt växande kedje av ideal.

Alternativt, säger man att R är Noetersk om varje växande kedje av ideal i A stabiliserar. Dvs, om I_{0} ⊆ I_{1} ⊆ ⋯ utgör en växande kedje av ideal i R, då måste det finnas N > 0 så att I_{m} = I_{n} för alla m, n ≥ N.

Definition : Dimensionen av en Noetersk ring R är längden n av den längsta strängt växande kedjen p_{0} ⊂ p_{1} ⊂ ⋯ ⊂ p_{n} av prima ideal i R.

Exempel : (i) Låt R vara en domän. Dim(R) = 0 ⇔ A är en kropp.

(ii) Låt R vara en domän igen. Dim(R) = 1 ⇔ varje icke-noll primt ideal i A är maximalt.

(iii) Dim K[x_{1}, ..., x_{n}] = n (se suppl. öv. nr. 17). Terminologin ‘dimension’ kommer från algebraisk geometri. Dimensionen av ett affint varietet V över en kropp K, som en hyperyta, är lika med den algebraiska dimensionen av sin koordinat ring K[V]. Detta är faktiskt definitionen av dim(V) för kroppar utom R eller C.

Definition : En integralt sluten, Noetersk domän av dimension ett kallas för en Dedekind domän.

Viktigt exempel : Z är en Dedekind domän.

Definition : Låt R vara en ring och M en R-modul. Då kallas M för en Noetersk R-modul om varje växande följd M_{1} ⊆ M_{2} ⊆ ⋯ av R-delmoduler till M stabiliserar.

Obs! EN ring R är Noetersk omm den är en Noetersk R-modul.

Proposition 77. (i) Låt A vara en ring. En A-modul M är Noetersk omm varje delmodul till M är ändligt genererad. (ii) Speciellt, en ring A är Noetersk omm varje ideal i A är ändligt genererad.

Bevis : Vi bevisar (i) ; då följer (ii) direkt.

⇒ Antag att M är Noetersk och att L ⊆ M är en delmodul som inte är ändligt genererad. Välj x_{0} ∈ L. Då genereras inte L av x_{0} så välj x_{1} ∈ L − (x_{0}). På samma sätt, genereras L inte av x_{0}, x_{1}, så vi kan välja x_{2} ∈ L − (x_{0}, x_{1}). Om vi fortsätter den här processen, då får vi en oändlig, strängt växande följd

(x_{0}) ⊂ (x_{0}, x_{1}) ⊂ (x_{0}, x_{1}, x_{2}) ⊂ ⋯

av delmoduler till M - motsägelse.

⇐ Antag att varje delmodul till M är ändligt genererad, och låt

L_{0} ⊆ L_{1} ⊆ ⋯  (176)

vara en växande följd av delmoduler till M. Låt L = ∪L_{i}. Då är L också en delmodul till M, alltså måste vara ändligt genererad. Låt x_{1}, ..., x_{n} vara en mängd av generatorer. Det måste finnas ett N > 0 så att alla x_{i} ∈ L_{N}. I så fall stabiliserar kedjan (176) vid L_{N}.

Exempel : En PID är alltid Noetersk eftersom varje ideal genereras av ett enda element. Med detta i hand, kan vi avsluta beviset av Sats 60.

Proposition 78. Låt A vara en ring, M en A-modul, N en A-delmodul till M. Då är M Noetersk omm både N och M/N är Noeterska.

Bevis : ⇒ Antag först att M är Noetersk.

Steg 1 : M/N är Noetersk.

Låt L_{0} ⊆ L_{1} ⊆ ⋯ vara en växande kedje av delmoduler till M/N. Då utgör π^{−1}(L_{0}) ⊆ π^{−1}(L_{1}) ⊆ ⋯ en växande kedje av delmoduler till M, där π : M → M/N är den naturliga projektionen. Eftersom M är Noetersk, måste den senare kedjen stabilisera. Men π(π^{−1}(L_{n})) = L_{n} för varje n, så att den ursprunliga kedjen i M/N stabiliserar också.

Steg 2 : N är Noetersk.

Låt L_{0} ⊆ L_{1} ⊆ ⋯ vara en växande kedje av delmoduler till N. Men varje L_{n} är också en delmodul till M, så kedjan måste stabilisera.

⇐ Antag nu att både N och M/N är Noeterska.

Låt L_{0} ⊆ L_{1} ⊆ ⋯ vara en växande kedje av delmoduler till M. Vi måste visa att kedjen stabiliserar. Sätt a_{k} = L_{k} ∩ N och b_{k} = π(L_{k}). Då utgör a_{0} ⊆ a_{1} ⊆ ⋯ och b_{0} ⊆ b_{1} ⋯ växande kedjor av delmoduler i N och M/N respektivt. Eftersom båda dessa moduler är Noeterska så måste båda kedjor stabilisera, dvs det finns N_{1}, N_{2} > 0 så att

a_{m} = a_{n} ∀ m, n ≥ N_{1}, b_{m} = b_{n} ∀ m, n ≥ N_{2}.

Vi påstår nu att L_{m} = L_{n} för alla m, n ≥ max{N_{1}, N_{2}}.

Så låt m > n ≥ max{N_{1}, N_{2}}. Låt x ∈ L_{m} ; vi måste visa att x ∈ L_{n}.

Först har vi att π(x) ∈ b_{m} = b_{n}. Därför finns det y ∈ L_{n} så att π(y) = π(x), som antyder att x − y ∈ a_{m}. Men a_{m} = a_{n}, så x − y = z för något z ∈ a_{n} ⊆ L_{n}. Därför är x = y + z ∈ L_{n}, som behövdes. Detta avslutar beviset.

Korollarium 79. (i) Låt A vara en Noetersk ring, M en ändligt genererad A-modul. Då är M en Noetersk A-modul.

Bevis : Från Prop. 62, vet vi att det finns n > 0 och ett A-modul I ⊆ A^{n} så att M ≅_{A} A^{n}/I.

Steg 1 : A^{n} är en Noetersk A-modul.

Eftersom A^{n} ≅ A⊕A^{n−1} räcker det att bevisa att, om M, N är två Noeterska A-moduler, så också är M ⊕ N. Då skulle man göra en induktion på n.

Så låt M, N vara Noeterska A-moduler. Avbildningen m ↦ (m, 0) identifierar M med en delmodul M^{∗} till M ⊕ N. Det är också klart att (M ⊕ N)/M^{∗} ≅ N. Då följer det från Prop. 78 att M ⊕ N är Noetersk.

Steg 2 : Så A^{n} är Noetersk, och vår ändligt genererad modul M är isomorfisk med A^{n}/I, för någon A-delmodul I. Då följer det från Prop. 78 att M är också Noetersk.

Lemma 80. Låt A ⊆ B vara domäner, B integral över A. Då är B en kropp ⇔ A är en kropp.

Bevis : ⇒ Antag att B är en kropp, och låt 0 ≠ x ∈ A. Vi vet att x^{−1} ∈ B ; vi måste visa att x^{−1} ∈ A. Efterom B/A är integral, då satisfierar x^{−1} ett moniskt polynom med koefficienter i A, säg

x^{−n} + a_{n−1}x^{−(n−1)} + ⋯ + a_{1}x^{−1} + a_{0} = 0.

Multiplicera båda sidor med x^{n−1}. Då får vi att

x^{−1} = ∑_{i=1}^{n} a_{n−i}x^{i−1} ∈ A.

⇐ Antag nu att A är en kropp. Låt 0 ≠ y ∈ B. Låt

y^{n} + a_{n−1}y^{n−1} + ⋯ + a_{1}y + a_{0} = 0  (177)

vara ett moniskt polynom av minimal grad som satisfieras av y. Om vi hade a_{0} = 0 då kunde vi ta ut en faktor y och få, eftersom B är en domän, en monisk ekvation av mindre grad som y satisfierar.

Alltså är a_{0} ≠ 0. Då finns a_{0}^{−1} ∈ A, eftersom A är en kropp. Betrakta nu

z := a_{0}^{−1} (y^{n−1} + a_{n−1}y^{n−2} + ⋯ + a_{2}y + a_{1}) ∈ B.

Man beräknar lätt att yz = zy = 1 så att z = y^{−1} ∈ B. Därför är B en kropp, och beviset är slut.

Sats 81. Låt A ⊆ B vara domäner, B ändligt genererad som en A-modul.

(i) A Noetersk ⇒ B Noetersk. (ii) dim(A) = 1 ⇒ dim(B) = 1.

Bevis : (i) följer omedelbart från Korollarium 79.

(ii) Om dim(B) = 0 då skulle dim(A) = 0 enligt Lemma 80. Då är dim(B) > 0. Det kvarstår att bevisa att varje icke-noll primt ideal i B är maximalt. Låt då q vara ett icke-noll prim ideal i B. Låt p = A ∩ q. Då är p ett prim ideal i A. Vidare är det lätt att se att B/q är integral över A/p. Antag nu att p ≠ {0}. Då är p ett maximalt ideal i A, så att A/p är en kropp. Då följer det från Lemma 80 att B/q är också en kropp, dvs att q är ett maximalt ideal i B, v.s.v.

Det räcker då att visa att p ≠ {0}. Välj 0 ≠ y ∈ B och välj, som i (177), ett moniskt polynom över A av minimal grad som satisfieras av y. Som i argumentet som följer (177), får vi att a_{0} ≠ 0. Men eftersom q är en A-modul, får vi då att

0 ≠ a_{0} = −y^{n} − ∑_{i=1}^{n−1} a_{i}y^{i} ∈ q ∩ A = p,

och beviset är slut.

Korollarium 82. Låt K vara en talkropp. Då är O_{K} en Dedekind domän.

Huvudsatsen om Dedekind domäner (svag version). I en Dedekind domän har varje icke-noll ideal a en unik decomposition som en produkt

a = p_{1}^{α_{1}} ⋯ p_{r}^{α_{r}} α_{i} ≥ 0,  (178)

av prima ideal.

Definition : Låt A vara en domän med kvotkropp K. En A-delmodul I till K kallas för ett fraktionellt ideal till A om I ≠ {0} och det finns 0 ≠ a ∈ A så att aI ⊆ A.

Om I ⊆ K är en A-modul, så också är aI för varje a ∈ A. Därför, om I är ett fraktionellt ideal och a ≠ 0 är så att aI ⊆ A, då måste aI vara ett ideal i A. Vi har då bevisat Proposition 83. Låt A vara en domän med kvotkropp K. Då är en delmängd I ⊆ K en fraktionell A-ideal omm det finns ett ideal a ⊆ A och 0 ≠ c ∈ A så att I = c^{−1}a.

Vi kan multiplicera fraktionella ideal på samma sätt som ideal, dvs

(c^{−1}a) (d^{−1}b) := (cd)^{−1}ab.  (179)

Nu har vi äntligen

Huvudsatsen om Dedekind domäner (stark version). Låt A vara en Dedekind domän med kvotkropp K. De fraktionella idealen till A i K utgör en abelsk grupp under multiplikation. Varje element a av denna grupp har en unik decomposition

a = p_{1}^{α_{1}} ⋯ p_{r}^{α_{r}} α_{i} ∈ Z,  (180)

som en produkt av prima ideal i A och deras inverser.

Lektioner 21,22,23 (18,20,22/12/00)

The goal is to prove the main theorem about Dedekind domains referred to in the previous lecture. The method we will adopt is perhaps not the simplest one, but I think it is the most fruitful, in that it illustrates a type of approach common to more advanced treatments of algebraic number theory, which also involves ideas fundamental to algebraic geometry. We will christen it the ‘local-global’ approach. Further general discussion of what this involves is postponed until after presentation of the main results.

In what follows, the ring R is always a domain and K denotes its’ quotient field. We will indicate whenever we wish to restrict to a smaller class of rings. A fractional R-ideal I will be referred to simply as a fractional ideal (no R !) when it is clear to which ring R it refers.

Definition : Let I, J be any two R-submodules of K. Their product IJ is defined by

IJ := {x ∈ K : x = ∑_{t=1}^{n} a_{t}b_{t}, where a_{t} ∈ I, b_{t} ∈ J} .  (181)

This generalises the idea of multiplying ideals in R. It is clear that IJ is also an R-submodule of K.

Definition : Let I be an R-submodule of K. We define

I^{−1} := {x ∈ K : xI ⊆ R},  (182)
R(I) := {x ∈ K : xI ⊆ I}.  (183)

Proposition 84. Both I^{−1} and R(I) are R-submodules of K. In fact, R(I) is a ring. Furthermore, we have

(i) R(I) ⊇ R ⊇ II^{−1}.

(ii) I ⊆ R ⇔ I^{−1} ⊇ R.

(iii) If I = Ra, a principal R-module, then I^{−1} = Ra^{−1}. In particular, II^{−1} = R.

Proof : Everything is immediate from the definitions, and the checking is left as an exercise.

Given the notation, one is tempted to call I^{−1} the inverse of I. However, this terminology is only used when II^{−1} = R. By part (iii) of the proposition, this is the case for principal modules over an arbitrary domain. More importantly, it is the case for any fractional ideal over a Dedekind domain (see Theorem 90, (iii)). A more fitting term for I^{−1} in general is the dual module of I (with respect to R).

Proposition 85. (i) If I_{1}, I_{2} are fractional R-ideals, then so is I_{1}I_{2}. (ii) If I is a fractional R-ideal, then so are I^{−1} and R(I).

Proof : (i) This is just a restatement of eq. (179).

(ii) More generally, we will prove that, if I_{1}, I_{2} are fractional R-ideals, then so is

J := {x ∈ K : xI_{2} ⊆ I_{1}}.

First we show that J ≠ {0}. Since I_{2} is a fractional ideal, there exists 0 ≠ a ∈ R such that aI_{2} ⊆ R. Pick any 0 ≠ b ∈ I_{1}. Then ba ∈ J and ba ≠ 0, since R is a domain.

Second, we must produce 0 ≠ r ∈ R such that rJ ⊆ R. Since I_{1} is a fractional ideal, there exists 0 ≠ c ∈ R such that cI_{1} ⊆ R. Pick any 0 ≠ d ∈ I_{2} ∩ R (such a d exists because I_{2} ≠ {0}, and if we pick any 0 ≠ d_{1} ∈ I_{2} then, as an element of K, its’ numerator is a non-zero element of I_{2} ∩ R, since I_{2} is an R-module). Then

cdJ = c(dJ) ⊆ c(I_{2}J) ⊆ cI_{1} ⊆ R,

and 0 ≠ cd ∈ R. q.e.d.

The next result is something worth keeping in mind :

Proposition 86. (i) A non-zero, finitely-generated R-submodule of K is a fractional ideal.

(ii) If R is Noetherian, then the converse is true.

Proof : (i) Suppose I is a non-zero, finitely-generated R-submodule of K, with generating set x_{1}, ..., x_{n}. Write

x_{i} = \frac{r_{i}}{s_{i}} , where r_{i}, s_{i} ∈ R and s_{i} ≠ 0.

Let s = ∏_{i=1}^{n} s_{i}. Then 0 ≠ s ∈ R and sI ⊆ R.

(ii) Suppose I is a fractional ideal. There exists 0 ≠ a ∈ R so that aI ⊆ R, and then aI is an ideal in R, by Prop. 83. By Prop. 77, aI is finitelygenerated as an R-module, say by x_{1}, ..., x_{n}. But then a^{−1}x_{1}, ..., a^{−1}x_{n} generate the R-module I. Now apply part (i).

Definition : The domain R is called a discrete valuation ring (DVR) if R is a PID and has exactly one non-zero prime ideal.

Proposition 87. (i) Let R be a DVR with prime ideal (π). Then every element x ∈ R has a unique representation as

x = uπ, where u ∈ R^{×} and 0 ≤ n ∈ Z.  (184)

In particular, every ideal of R is of the form (π)^{n} = (π^{n}), for some n ≥ 0.

(ii) Every element of K also has a unique representation of the form (184), but where we allow n ∈ Z, unrestricted. In particular, every fractional R-ideal is of the form Rπ^{n}, for some n ∈ Z.

Proof : R is a PID, hence a UFD by Theorem 60. Hence every x ∈ R has a decomposition as a product of irreducible elements, unique up to units. But every irreducible element θ ∈ R is prime (Prop. 58), hence generates a non-zero prime ideal, which must coincide with (π) since R is a DVR. Hence θ = u_{1}π for some u_{1} ∈ R^{×}. The result for R now follows, and that for K is an immediate consequence.

Let R be a DVR with prime ideal (π). By Prop. 87, there is a well-defined map ν : K → Z ∪ {+∞} given by

ν(0) = +∞,  (185)
ν(x) = n whenever x = uπ^{n} for some u ∈ R^{×}.  (186)

The map ν has the following properties :

(i) ν(K^{×}) = Z.

(ii) ν(xy) = ν(x) + ν(y), for all x, y ∈ K^{×}.

(iii) ν(x) = +∞ ⇔ x = 0.

(iv) ν(x + y) ≥ min{ν(x), ν(y)}, for all x, y ∈ K.

(v) R = {x ∈ K : ν(x) ≥ 0}.

Now let L be any field. A map ν : L → Z ∪ {+∞} with properties (i)

- (v) is called a discrete valuation (sometimes non-archimedean valuation) of L. Properties (i) - (v) then imply that the set S = {x ∈ L : ν(x) ≥ 0} is a subring of L with quotient field equal to L. S is called the valuation ring of the valuation ν. The ring S is always integrally closed (see proof of Prop. 88), and has the property that, for all x ∈ L, either x or x^{−1} lies in S. For more on (discrete) valuations of fields, see the volume edited by Cassels and Fröhlich, and/or Chapter 5 of the book of Atiyah and McDonald^{30}.

30The important points are the following. Let ν be a discrete valuation on the field L, with valuation ring S. Choose a constant c > 0 and set, for x ∈ L,

||x|| := c^{−ν(x)}.

The properties of a discrete valuation then imply that || · || is a norm on L. It is in fact an ultra-norm because it satisfies

||x + y|| ≤ max{||x||, ||y||}, ∀ x, y ∈ L,

which is stronger than the usual triangle inequality. The associated metric topology on L is independent of the choice of c > 0. It is called the ν-adic topology on L. The completion of L, as a metric space with this topology, is denoted L_{ν}. The basic theorem then is

Theorem. (i) L_{ν} is a field.

(ii) The discrete valuation ν on L can be extended in a unique manner to a discrete valuation ν^{∗} on L_{ν}.

(iii) Let S_{ν} be the valuation ring of ν^{∗} in L_{ν}. Then S_{ν} coincides with the completion of S w.r.t. ν.

(iv) S_{ν} is a discrete valuation ring.

An important problem (from the point of view of number theory) is the classification of all discrete valuations on Q. It turns out that they are in 1-1 correspondence with the prime numbers, as follows :

Let p be a fixed prime. Every element x ∈ Q has a unique representation as x = p^{n}x_{1}, where x_{1}, when written as a fraction in lowest terms, has both its’ numerator and denominator relatively prime to p. One then defines the discrete valuation ν_{p} of Q by setting

ν_{p}(p^{n}x_{1}) := n.

It is easily checked that ν_{p} IS, in fact, a discrete valuation on Q. It is called the p-adic valuation. The completion of Q w.r.t. ν_{p} is called the field of p-adic numbers, and denoted Q_{p}. The valuation ring of ν_{p}^{∗} is called the ring of p-adic integers, and denoted Z_{p}. Note that, by the above theorem, Z_{p} is just the completion of Z w.r.t. the valuation ν_{p}. For an explicit description of the ring Z_{p}, see supplementär övning nr. 18.

Proposition 88. A domain R is a DVR iff it is Noetherian, integrally closed and possesses exactly one non-zero prime ideal.

Important remark : A ring R is called local if it has exactly one maximal ideal. Here, we include the case of non-trivial fields, where the maximal ideal is {0}. Hence, Prop. 88 can be reformulated as

‘A domain R is a DVR iff it is a local Dedekind domain’.

In particular, a local Dedekind domain is a UFD. When we remove the local condition we may lose the UF property but, according to the Main Theorem, we retain unique factorisation of ideals.

Proof of prop. 88 : ⇒ Suppose R is a DVR. Then it possesses exactly one non-zero prime ideal, by our definition of a DVR. Furthermore, R is Noetherian since it is a PID (see Prop. 77). It remains to show that R is integrally closed. So let x ∈ K, the quotient field of R, and suppose x satisfies a monic polynomial over R, say

x^{n} + r_{n−1}x^{n−1} + ⋯ + r_{1}x + r_{0} = 0.

Consider the valuation ν on K. We have

ν(x^{n}) = nν(x) = ν (− ∑_{i=0}^{n−1} r_{i}x^{i})
≥ min_{0≤i<n}{ν(−r_{i}x^{i})}
= min_{0≤i<n}{ν(−r_{i}) + iν(x)}
≥ min_{0≤i<n}{iν(x)}, since ν(r) ≥ 0, ∀ r ∈ R,

from which we conclude that ν(x) ≥ 0, i.e.: that x ∈ R. This proves integral closure of R.

⇐ The proof in this direction is technical and will be accomplished in a sequence of steps. So let R denote a local Dedekind domain, with maximal ideal p, and quotient field K.

It was proven by Ostrowski that every discrete valuation of Q must be one of the ν_{p}.

Actually, Ostrowski’s theorem says more, but we defer to Cassels and Fr¨ hlich for details.

For a comprehensive introduction to the p-adic numbers, including methods of p-adic analysis, see also the book ‘P-adic numbers, p-adic analysis and zeta functions’, by N.

Koblitz.

Notation : In the following proof, ⊃ always denotes strict containment.

Step 1 : If I is any fractional R-ideal, then R(I) = R.

Proof : By Prop. 84, R(I) ⊇ R, so it remains to prove the converse. By Props. 85 and 86, R(I) is a ring, which is finitely generated as an R-module. Let x ∈ R(I). By definition, xI ⊆ I, which implies that R[x] ⊆ R(I). By Prop. 64(iii), x is integral over R. Thus x ∈ R, since R is integrally closed.

Step 2 : p^{−1} ⊃ R.

Proof : A priori, I^{−1} ⊇ R for any ideal I of R, by Prop. 84(ii). Pick 0 ≠ a ∈ p and let I = (a). Since a^{−1} ∉ R, we have that I^{−1} ⊃ R, by Prop. 84(iii).

We now consider the set A of non-zero ideals I in R such that I^{−1} ⊃ R. We’ve just shown that the set A is non-empty. Since R is Noetherian, A has a maximal element^{31}, J say. We claim that J = p. Since p is the unique non-zero prime ideal of R, it suffices to show that J is a prime ideal.

So let x, y ∈ R such that xy ∈ J, x ∉ J. We must show that y ∈ J. Pick z ∈ J^{−1} − R. Then zy(xR + J) ⊆ R, i.e.: zy ∈ (xR + J)^{−1}. Since x ∉ J, we have xR + J ⊃ J, so maximality of J implies that zy ∈ R. But then z(yR + J) ⊆ R, i.e.: z ∈ (yR + J)^{−1}. Again, maximality of J implies that yR + J = J, i.e.: that y ∈ J. q.e.d.

Step 3 : R = pp^{−1}.

Proof : By Prop. 84(ii), we have R ⊇ pp^{−1} ⊇ pR = p. Hence, pp^{−1} is an ideal of R containing p, hence must be either p or R.

But pp^{−1} = p would imply that p^{−1} ⊆ R(p), which contradicts Steps 1 and 2.

Step 4 : ∩_{n=0}^{∞}p^{n} = {0}.

Proof : If x ∈ p and y ∈ p^{−1}, then yx ∈ R. It follows that, for each n > 0, if x ∈ p^{n} then yx ∈ p^{n−1}. It follows in turn that p^{−1} ⊆ R (∩_{n=0}^{∞}p^{n}). But this contradicts Steps 1 and 2 unless ∩_{n=0}^{∞}p^{n} = {0}. q.e.d.

31Here the Noetherian hypothesis is essential, since we cannot use Zorn’s lemma. In an arbitrary domain, the ideal which is the union of the members of an ascending chain of ideals in A will in general not be in A

We can now complete the proof that R is a DVR. By Step 3, there exists π ∈ p such that p^{−1}π ⊈ p. Since p^{−1}π is an ideal of R, we must therefore have p^{−1}π = R. In particular, 1 ∈ p^{−1}π, so that π^{−1} ∈ p^{−1}.

Let x ∈ p. Then π^{−1}x ∈ R so that x ∈ (π), the principal ideal of R generated by π. Thus p ⊆ (π). But the reverse inclusion is trivial, so we must have that p = (π). Consequently, p^{n} = (π)^{n} = (π^{n}), for all n ≥ 0, where π^{0} = 1.

Finally, we claim that each r ∈ R has a unique expression as r = uπ^{n}, for some u ∈ R^{×} and n ≥ 0. Clearly, this would imply that R is a DVR. By Step 4, there is a maximal n ≥ 0 such that r ∈ p^{n}. Since p^{n} = (π^{n}), we thus have r = uπ^{n} for some u ∈ R. But we must have that u ∈ R^{×}, as otherwise u ∈ p = (π), which would imply that r ∈ (π^{n+1}) = p^{n+1}, a contradiction.

This completes the proof of Prop. 88.

Definition : Let R be a domain with quotient field K, p a prime ideal of R. We set

Rp := \{a ∈ K : a = \frac{r}{s}, where r, s ∈ R and s ∉ p\} .  (187)

Rp is called the local ring of fractions of R w.r.t. p, or simply the localisation of R at p.

Proposition 89. (i) Rp is a subring of K. (ii) Rp is a local ring. If m is its’ unique maximal ideal, then

m = pRp = \{\frac{r}{s} ∈ Rp : r ∈ p\} .

(iii) m ∩R = p. (iv) If I is any ideal in Rp then I = (I ∩ R)Rp.

Proof : All parts of this proposition are quite simple, but a notational nightmare to write down. So look in your lecture notes !

Theorem 90. The following three conditions are equivalent on an integral domain R which is not a field :

(i) R is Dedekind. (ii) R is Noetherian and, for each non-zero prime ideal p of R, the local ring Rp is a DVR. (iii) For each fractional ideal I of R, II^{−1} = R.

Proof : (i) ⇒ (ii) Suppose R is Dedekind. Then R is Noetherian. Let p be a non-zero prime ideal of R. By Prop. 88, it suffices to show that Rp is Noetherian, integrally closed, and has exactly one non-zero prime ideal.

Step (a) : Rp is Noetherian.

Let I be an ideal in Rp. By Prop. 89(iv), I = (I ∩ R)Rp. But I ∩ R is an ideal in R, hence finitely-generated, since R is Noetherian. But any generating set for I ∩R as an R-module will also be a generating set for I as an Rp-module. Hence, every ideal of Rp is finitely-generated, which proves that Rp is Noetherian.

Step (b) : Rp is integrally closed.

Suppose x ∈ K is integral over Rp, say

x^{n} + \frac{r_{n−1}}{s_{n−1}} x^{n−1} + ⋯ + \frac{r_{1}}{s_{1}} x + \frac{r_{0}}{s_{0}} = 0,  (188)

where r_{i}, s_{i} ∈ R and s_{i} ∉ p. Let s = ∏_{i=0}^{n−1} s_{i}. Multiply (188) through by s and we obtain

sx^{n} + t_{n−1}x^{n−1} + ⋯ + t_{1}x + t_{0} = 0,

for some t_{i} ∈ R. Multiplying through further by s^{n−1}, we obtain a monic polynomial over R satisfied by sx. That is, sx is integral over R. But R, being Dedekind, is integrally closed, hence sx ∈ R, say sx = r. But then x = \frac{r}{s} ∈ Rp, since s ∉ p.

Step (c) : Rp has exactly one non-zero prime ideal.

From Prop. 89(ii), we know that Rp has at least one non-zero prime ideal, namely its’ maximal ideal m. Now let I be any non-zero prime ideal of Rp ; we must show that I = m.

One sees immediately that I ∩ R is a prime ideal in R, and at the very least it is non-zero (since I is), by Prop. 89(iv). But I ⊆ m = pRp, so we must have that I ∩ R ⊆ p. But dim(R) = 1, so therefore I ∩ R = p and I = m by Prop. 89(ii).

(ii) ⇒ (iii) Let I be a fractional ideal of R. A priori, II^{−1} is an ideal of R, by Prop. 84(i). It suffices to show that, for each non-zero prime ideal p of R, II^{−1} ⊈ p.

So fix such a p. Let ν denote the discrete valuation of K corresponding to the DVR Rp. Since R is Noetherian we know, by Prop. 86, that I is finitelygenerated as an R-module, say by a_{1}, ..., a_{n} ∈ K. Order the a_{i} so that ν(a_{1}) is minimal. Then, for each i, we have that ν(a_{1}^{−1}a_{i}) = ν(a_{i}) − ν(a_{1}) ≥ 0, so that a_{1}^{−1}a_{i} ∈ Rp, the valuation ring of ν. Let

a_{1}^{−1}a_{i} = \frac{r_{i}}{s_{i}} , where r_{i}, s_{i} ∈ R and s_{i} ∉ p.

Set s = ∏ s_{i}. Then, for each i, sa_{1}^{−1}a_{i} ∈ R. Since the a_{i} generate I as an Rmodule, we may conclude that sa_{1}^{−1} ∈ I^{−1}. But then s = (sa_{1}^{−1})a_{1} ∈ I^{−1}I and s ∉ p. q.e.d.

(iii) ⇒ (i) We have to show that R is Noetherian, integrally closed and of dimension 1.

Step (a) : R is Noetherian.

Let I be an ideal of R. We’ll show that I is finitely-generated. Since II^{−1} = R we can find a_{1}, ..., a_{n} ∈ I, b_{1}, ..., b_{n} ∈ I^{−1} such that

1 = ∑_{i=1}^{n} a_{i}b_{i}.

Let x ∈ I. Then

x = 1 · x = (∑_{i=1}^{n} a_{i}b_{i}) x = ∑_{i=1}^{n} a_{i}(b_{i}x).  (189)

Since each b_{i} ∈ I^{−1}, we have that each b_{i}x ∈ R. Hence, (189) expresses x as an R-linear combination of a_{1}, ..., a_{n}. This shows that a_{1}, ..., a_{n} generate the ideal I.

Step (b) : R is integrally closed.

Let x ∈ K be integral over R. We must show that x ∈ R. Set S = R[x]. By Prop. 64(ii), S is a finitely-generated R-module, hence a fractional ideal of R, by Prop. 86. Thus SS^{−1} = R. However, S is also a ring, so that SS = S. Now we have

S = SR = S(SS^{−1}) = (SS)S^{−1} = SS^{−1} = R.

This shows that x ∈ R, as required.

Step (c) : dim(R) = 1.

dim (R) > 0 since R is not a field. It remains to show that any non-zero prime ideal is maximal. So let p be a non-zero prime ideal, m a maximal ideal containing it. Then pm^{−1} ⊆ mm^{−1} = R is an ideal of R and p = pR = p(m^{−1}m) = (pm^{−1})m. By Prop. 76(iii), we have that either m ⊆ p, exactly as required, or pm^{−1} ⊆ p. So suppose the latter holds. Then

R = mm^{−1} = mRm^{−1} = m(p^{−1}p)m^{−1} = mp^{−1}(pm^{−1}) ⊆ mp^{−1}p = mR = m,

i.e.: R ⊆ m, which is absurd.

The proof of Theorem 90 is now complete.

Proof of Main Theorem on Dedekind domains : Let R be Dedekind. Combining Prop. 75 and Theorem 90(iii), we have already shown that the fractional ideals of R generate an abelian group under multiplication. It remains to show that each element of this group has a unique expression as a product of prime ideals and their inverses. In fact, by Theorem 90(iii), it suffices to show that every non-zero IDEAL has a unique expression as a product of prime ideals. There are two things to show here : existence and uniqueness of the expression.

Existence : Let A denote the set of non-zero ideals which cannot be written as a product of prime ideals. We claim that the set A is empty. Suppose it isn’t. Then, since R is Noetherian, A must have a maximal element, I say. Then I cannot itself be prime, so let p be a prime ideal properly containing I. Consider Ip^{−1}. It is an ideal of R containing I. In fact, it properly contains I since, if we assumed that Ip^{−1} ⊆ I, then multiplying both sides by I^{−1}p would give the contradiction that R ⊆ p. Hence, by maximality of I in A, it must be possible to write Ip^{−1} as a product of prime ideals. But then multiplying both sides by p gives an expression for I as a product of prime ideals, contradiction.

Uniqueness : Same idea as in the proof of the FTA, making use of Prop. 76(iii). You are left to fill in the details for yourselves.

Ramification in number fields

From now on, let K be a number field with ring of integers O_{K}. Let p be a prime number. By the Main Theorem, the principal ideal pO_{K} can be written as a product of prime ideals in O_{K}, say

pO_{K} = q_{1}^{e_{1}} ⋯ q_{r}^{e_{r}}.  (190)

The prime ideals q_{i} are said to lie above p. The numbers e_{i} are called ramification indices. The prime p is said to be ramified in K if some e_{i} > 1 ; otherwise, it is said to be unramified. If r = e_{1} = 1, we say that p remains prime in K.

Pick some q_{i} lying over p, and consider the quotient O_{K}/q_{i}. It is a field, containing Z/pZ as a subfield. The degree of the field extension is denoted f_{i}, and is called the residue class degree at q_{i}. This means that O_{K}/q_{i} is a finite field of order p^{f_{i}}.

Theorem 91. In the above notation,

∑_{i=1}^{r} e_{i}f_{i} = [K : Q].  (191)

For the proof of this, we will require two lemmas :

Lemma 92 (real CRT !). Let R be a ring, I_{1}, ..., I_{n} ideals of R such that I_{k} + I_{l} = R for any k ≠ l. Then we have an isomorphism of rings

R/ ∩_{k=1}^{n} I_{k} ≅ ∏_{k=1}^{n} R/I_{k}.  (192)

Proof : Same idea as in the proof of the ordinary CRT (see Lektion 3). There is a natural ring homomorphism from the lhs to the rhs of (192), and the hard part is showing it is surjective. Surjectivity is equivalent to the statement that, for any x_{1}, ..., x_{n} ∈ R, there exists x ∈ R with x − x_{k} ∈ I_{k}, for k = 1, ..., n.

Lemma 93. Let R be a Dedekind domain, p be a non-zero prime ideal of R. Then, for each i ≥ 0, p^{i}/p^{i+1} is a one-dimensional R/p vector space.

Proof : Let m be the maximal ideal in Rp. By Theorem 90(ii), m is principal, and WLOG it is generated by some element π ∈ R. Then, for each n ≥ 0, m^{n} is generated by π^{n} and one easily checks that m^{n} ∩ R = p^{n}. One now easily checks that multiplication by π^{n} induces an isomorphism of vector spaces from R/p to p^{n}/p^{n+1}.

Proof of Theorem 91 : Let [K : Q] = n. Since O_{K} is a free Z-module of rank n (Theorem 73), O_{K}/pO_{K} is a free Z/pZ-module of rank n. In particular, it is a ring of order p^{n}. Suppose pO_{K} factors as in (190). By Lemma 91, there is a ring isomorphism

O_{K}/pO_{K} ≅ ∏_{i=1}^{r} O_{K}/q_{i}^{e_{i}}.  (193)

But from Lemma 92 it follows immediately that |O_{K}/q_{i}^{e_{i}}| = |O_{K}/q_{i}|^{e_{i}}. Since |O_{K}/q_{i}| = p^{f_{i}}, comparing the orders of both sides of (193) now gives the desired result.

By Theorem 91, there are at most [K : Q] prime ideals in K lying above any given prime number p. If there are exactly [K : Q] such ideals, we say that p splits completely in K. In this case e_{i} = f_{i} = 1 for i = 1, ..., n. On the other hand, if r = f = 1 and e = n we say that p is totally ramified in K.

Proposition 94. Suppose K/Q is Galois. Let p be a prime number, which factors in K as in (190). Then all e_{i} are equal, to e say, all f_{i} are equal, to f say, and efr = [K : Q].

Proof : It clearly suffices to show that the Galois group G of K over Q acts transitively on the primes lying over p. Suppose the contrary, i.e.: suppose there are two primes q_{1} and q_{2} lying over p such that σq_{1} ≠ q_{2} for all σ ∈ G. Equivalently, since G is a group, σq_{1} ≠ τq_{2} for all σ, τ ∈ G. By Lemma 92, there thus exists x ∈ O_{K} such that

x ≡ 0 (mod σq_{1}) ∀ σ ∈ G,  (194)
x ≡ 1 (mod σq_{2}) ∀ σ ∈ G.  (195)

Consider

n := ∏_{σ∈G} σx.

Since n is invariant under all elements of G, we must have that n ∈ Q, by Prop. 68. But x ∈ q_{1}, by (194), so n ∈ Q ∩ q_{1}. By the argument in the proof of Lemma 80, this intersection must be pZ. The same is true of Q∩q_{2}. But, by (195), σx ∉ q_{2} for all σ ∈ G, so that n ∉ q_{2} either, since q_{2} is a prime ideal. This is a contradiction, which completes the proof.

Terminology : If p is a prime, and K/Q is Galois, then p is said to be tamely ramified in K if p † e ; otherwise, p is said to be wildly ramified.

Norms

Let q be any non-zero prime ideal of O_{K}. As just indicated above (see also the proof of Lemma 80), there is a prime number p ∈ N such that Q ∩q = pZ. Then q lies above p. Let f be the associated residue class degree. We define the norm N(q) of q by

N(q) := p^{f}.  (196)

This defines the norm of a prime ideal. We extend the definition to an arbitrary fractional O_{K}-ideal by multiplication, i.e.:

N(q_{1}^{n_{1}} ⋯ q_{k}^{n_{k}}) := ∏_{i=1}^{k} N(q_{i})^{n_{i}}.  (197)

For any non-zero x ∈ K, we define the norm of x, N(x), by

N(x) := N[(x)],  (198)

Where (x) = xO_{K} is the principal fractional ideal generated by x.

Notice that, by Theorem 91, if p is a prime number, then

N(p) = p^{[K:Q]}.  (199)

Hence, by multiplicativity, we have

0 ≠ r ∈ Q ⇒ N(r) = |r|^{[K:Q]}.  (200)

More generally, we have

Theorem 95. Let [K : Q] = n.

(i) Let a be a non-zero ideal in O_{K}. Then

N(a) = |O_{K}/a|.  (201)

(ii) Let a ∈ O_{K}. Considering O_{K} as a Z-module with a fixed basis, let A ∈ M_{n}(Z) be the matrix of the linear transformation x ↦ ax from O_{K} to O_{K}. Then N(a) = | det A|. (iii) For any 0 ≠ a ∈ K we have

N(a) = |∏_{i=1}^{n} σ_{i}(a)| ,  (202)

where σ_{1}, ..., σ_{n} are the distinct embeddings of K. (iv) More generally, if K/Q is Galois, and a is any fractional ideal of O_{K}, then

(N(a)) = ∏_{i=1}^{n} σ_{i}(a),  (203)

where the lhs denotes the principal O_{K}-fractional ideal generated by the rational integer N(a).

(v) Let ϵ ∈ O_{K}. Then ϵ ∈ O_{K}^{×} iff N(ϵ) = 1. (vi) Let a be a non-zero ideal in O_{K}. Then a is a free Z-module of rank n. If α_{1}, ..., α_{n} is any Z-basis for a then

Δ(α_{1}, ..., α_{n}) = N(a)^{2}d_{K}.  (204)

Obs! The product on the rhs of (202) is taken, in some books, as the definition of the norm of an element. Let us denote it by n(a). As (202) indicates, it only coincides with our definition up to a sign. However, it is also multiplicative, i.e.:

n(a)n(b) = n(ab), ∀ a, b ≠ 0.  (205)

Proof : (i) For a non-zero prime ideal q of O_{K}, we have N(q) = |O_{K}/q| by definition. The result for a general ideal now follows from multiplicativity (eq. (197)) and Lemma 92.

(ii) Follows immediately by application of (i) to the principal ideal aO_{K}.

(iii) First suppose that a ∈ O_{K}. K = Q(a). Consider the characteristic equation

det(A − λI_{n}) = 0,  (206)

of the matrix A in part (ii). Notice that Aa = a · a, so that λ = a is an eigenvalue. Now let σ be any embedding of K. Applying σ to (206) and remembering that the matrix A has rational integer entries, we find that σ(λ) is an eigenvalue whenever λ is. Now since K = Q(a), the complex numbers σ_{1}(a), ..., σ_{n}(a) are all distinct. Hence, we’ve produced n distinct eigenvalues of A, and these must be all its’ eigenvalues, since A is an n × n matrix. But for any square matrix A, det A is equal to the product of its’ eigenvalues which, together with part (ii), implies (202).

For a general 0 ≠ a ∈ K, the result follows by an extension of this argument which we skip over.

(iv) Because of the multiplicativity of the norm (eq. (197)), it suffices to prove this when a is a prime ideal. But then it follows from the ideas used in the proof of Theorem 91 and Prop. 94.

(v) Fix a Z-basis of O_{K} and let A ∈ M_{n}(Z) be the matrix of ϵ, as in part (ii). Then A^{−1} is the matrix of ϵ^{−1}, and hence ϵ^{−1} ∈ O_{K} iff A^{−1} also has integer entries. This is the case iff det A = ±1. Now (v) follows from (ii).

(vi) O_{K} is a free Z-module of rank n, by Theorem 73. By part (i), a is a subgroup of this group of finite index. Hence it must also be free of rank n (see suppl. öv. nr. 16). The statement about the discriminant of a Z-basis for a follows from part (ii) and eq. (173).

Note that (204) allows us to define the discriminant of an ideal {0} ≠ a ⊆ O_{K} by

d(a) := N(a)^{2}d_{K}.  (207)

The multiplicativity of the norm implies the same property for the discriminant, i.e.:

d(ab) = d(a)d(b), ∀ a,b ≠ {0}.  (208)

We mention one more result in this connection :

Proposition 96. The prime number p ramifies in the number field K if and only if p|d_{K}, the discriminant of K.

Proof : Skipped over.

Two classical results

We wish to state two of the most important results of algebraic number theory. Proofs may be found in, for example, Stewart and Tall.

The first result is about ideals. So let K be a number field. By the main theorem on Dedekind domains, the fractional ideals of O_{K} comprise a group under ideal multiplication. Call this group I(K). It is clear that the principal fractional ideals form a subgroup, since

(a)(b) = (ab),
(a)^{−1} = (a^{−1}).  (209)

This subgroup is denoted P(K). Then we have

Class number theorem. I(K)/P(K) is a finite group.

This quotient group is called the (ideal) class group of K. Its’ order is denoted h_{K} and called the (ideal) class number of K. One important property of the class number is the following

Proposition. Let K be a number field. Then

h_{K} = 1 ⇔ K is a PID ⇔ K is a UFD.

Proof : The first equivalence follows from the definition of h_{K}. From Sats 60, we know that if K is a PID then it is a UFD. It remains to show that if K is a UFD, then it is a PID.

So assume K is a UFD. Since every ideal in O_{K} is a product of prime ideals, it suffices to show that every prime ideal is principal. So let p be a prime ideal. Pick any x ∈ p. Since K has the factorisation property (F), we can factorise x as a product of irreducible elements of O_{K}, say

x = π_{1} ⋯ π_{k}.

Since π_{1} ⋯ π_{k} ∈ p, there is at least one index i such that π_{i} ∈ p. But since K is a UFD, the principal ideal (π_{i}) is prime (Prop. 58). Hence, (π_{i}) is a non-zero prime ideal of O_{K} contained in p. Since O_{K} has dimension 1, we conclude that p = (π_{i}).

The second classical result relates to the units in O_{K}.

Dirichlet’s units theorem. The multiplicative group O_{K}^{×} is a finitelygenerated abelian group. It is of the form

T × F

where T is a finite group consisting of all the roots of unity in K, and F is a free abelian group of rank r_{1} + r_{2} − 1 (see eq. (166)).

Remark : A basis for the group F above is called a system of fundamental units for the field K.

The regulator R of a number field K is defined as follows. Let [K : Q] = n. Suppose K has real embeddings σ_{1}, ..., σ_{r_{1}} and complex embeddings σ_{r_{1}+1}, \overline{σ_{r_{1}+1}}, ..., σ_{r_{1}+r_{2}}, \overline{σ_{r_{1}+r_{2}}}, in any order. Let ϵ_{1}, ..., ϵ_{r_{1}+r_{2}−1} be a system of fundamental units for K. Then

R := |det [σ_{i}(ϵ_{j})]| , 1 ≤ i, j ≤ r_{1} + r_{2} − 1.  (210)

It’s an easy exercise to show that the definition of R is independent of the choice of a system of fundamental units, and of the ordering of the embeddings σ_{i} - for the latter, use Theorem 95 (iii),(v).

Kvadratiska kroppar

Definition : En algebraisk talkropp K kallas för en kvadratisk kropp om [K : Q] = 2.

Under resten av kursen ska vi koncentrera på dessa kroppar, och ska se hur föregående idéer och resultat om allmäna talkroppar specialiserar till denna situation. Vi ska dela upp vår analys i fem delar :

Del 1 : Klassificiering av kvadratiska kroppar. Del 2 : Heltalsringen i en kv. kropp, och diskriminanten. Del 3 : Ramificiering och sambandet med Legendre symboler. Del 4 : Enheter och sambandet med Pells ekvation. Detta ledar till ett nytt stort område inom talteori, nämligen Diophantisk approximation. Del 5 : Sambandet mellan idéal klasser i kv. kroppar och binära kvadratiska former.

Del 1 : Klassificiering

Sats 97. Det finns en 1-1 korrespondens mellan kvadratiska kroppar och heltal d som är kvadratfria. Korrespondensen ges explicit av d ↔ Q(\sqrt{d}).

Bevis : Först är det klart att om d är ett kvadratfritt heltal då är Q(\sqrt{d}) en kvadratisk kropp.

Näst antag att d_{1}, d_{2} är två kvadratfria heltal och att Q(\sqrt{d_{1}}) = Q(\sqrt{d_{2}}). Vi måste visa att d_{1} = d_{2}. Från föregående likhet vet vi att det finns x, y, z, w ∈ Q så att

x + y\sqrt{d_{1}} = z + w\sqrt{d_{2}}.  (211)

Efter uttagning av en gemensam nämnare och kryss multiplikation får vi antaga att x, y, z, w ∈ Z. Tag nu z till vänstra sidan av (211) och kvadrera båda sidor, så får man att

(x − z)^{2} + y^{2}d_{1} + 2y(x − z)\sqrt{d_{1}} = w^{2}d_{2}.

Därför är 2y(x − z)\sqrt{d_{1}} ∈ Q ⇒ y(x − z) = 0 ⇒ y = 0 eller x = z. Om y = 0 då skulle (211) säga att \sqrt{d_{2}} ∈ Q, en motsägelse.

Om x = z då säger (211) att y^{2}d_{1} = w^{2}d_{2}. Men eftersom både d_{1} och d_{2} är kvadratfria, så följer det att d_{1} = d_{2}, v.s.v.

För att avsluta beviset, måste vi visa att varje kvadratisk kropp ges av Q(\sqrt{d}) för något kvadratfritt heltal d. Alltså. låt K vara en kvadratisk kropp. Enligt Sats 67 är K = Q(α) för något α ∈ K. Eftersom K har grad 2 över Q, så måste mimimal polynomet av α över Q ha grad 2. Då satisfierar α också något polynom av grad 2 över Z, säg

aα^{2} + bα + c = 0, där a, b, c ∈ Z, a ≠ 0.

Från formeln för lösningarna till en kvadratisk ekvation får vi då att

α = \frac{−b ± \sqrt{b^{2} − 4ac}}{2a}.  (212)

Sätt d_{1} = b^{2}−4ac. Heltalet d_{1} har en unik representation i formen d_{1} = w^{2}d, där w ∈ N och d är kvadratfritt. Då kan (212) skrivas om som

α = \frac{−b}{2a} ± \frac{w}{2a}\sqrt{d}.

Det följer att K = Q(\sqrt{d}), och beviset av Sats 97 är avklarat.

Korollarium 98. Varje kvadratisk kropp är Galois över Q.

Del 2 : Heltalsringen

I detta avsnitt ska element av Z kallas för ‘rationella heltal’.

Sats 99. Låt d vara ett kvadratfritt rationellt heltal och K = Q(\sqrt{d}) vara en kvadratisk kropp.

(i) Om d ≡ 2, 3 (mod 4), då är

O_{K} = Z ⊕ Z\sqrt{d}.  (213)

(ii) Om d ≡ 1 (mod 4), då är

O_{K} = Z ⊕ Z\frac{1 + \sqrt{d}}{2}.  (214)

Anmärkning : Vi vet a priori från Sats 73 att O_{K} är en fri abelsk grupp av rang 2.

Bevis : O_{K}∩ Q = Z, eftersom Z är integralt sluten (Prop. 72(ii)). Låt nu α ∈ O_{K} − Q. Då måste α satisfiera ett moniskt polynom av grad 2 över Z, säg

α^{2} + aα + b = 0, a, b ∈ Z.  (215)

α kan skrivas (på ett unikt sätt) i formen

α = x + y\sqrt{d},

för några x, y ∈ Q. Substituera i (215), så får man att

(x^{2} + y^{2}d + ax + b) + (2xy + ay)\sqrt{d} = 0,

som antyder att

x^{2} + y^{2}d + ax + b = 0  (216)

och

2xy + ay = 0.  (217)

Från (217) får vi att antingen y = 0 eller 2x + a = 0. Men y = 0 betyder att α ∈ Q, som säger emot hypotesen. Därför måste

x = −\frac{a}{2}.  (218)

Substituera (218) i (216) och vi får att

y = ±\sqrt{\frac{a^{2} − 4b}{4d}}.

Men y ∈ Q och d är ett kvadratfritt rationellt heltal, så det måste finnas w ∈ N så att

a^{2} − 4b = dw^{2},  (219)

och då att

y = ±\frac{w}{2} .  (220)

Om d ≡ 2, 3 (mod 4), då har (219) en lösning omm både a och w är jämna. Då följer (213) från (218) och (220).

Om d ≡ 1 (mod 4), då har (219) en lösning om antingen (i) både a och w är jämna eller (ii) både a och w är udda. Alltså, följer (213) från (218) och (220) i detta fall också.

Korollairum 100. Låt d vara ett kvadratfritt rationellt heltal och K = Q(\sqrt{d}) vara en kvadratisk kropp.

(i) Om d ≡ 2, 3 (mod 4), då är

d_{K} = 4d.  (221)

(ii) Om d ≡ 1 (mod 4), då är

d_{K} = d.  (222)

Speciellt, finns det precist en kvadratisk kropp av diskriminant D för varje heltal D som är en fundamental diskriminant, i meningen av binära kvadratiska former.

Bevis : Följer från Prop. 74, Sats 99 och faktumet att de två imbäddningarna ϕ_{1}, ϕ_{2} av kroppen Q(\sqrt{d}) ges av

x + y\sqrt{d} ↦^{ϕ_{1}} x + y\sqrt{d}, x + y\sqrt{d} ↦^{ϕ_{2}} x − y\sqrt{d}.

Lektion 24 (08/01/01) Del 3 : Ramificiering

Låt K vara en kvadratisk kropp och p ∈ Z ett primtal. Från Prop. 94 och Kor. 98, finns det precis tre möjigheter för prim decompositionen av huvudidéalet pO_{K}, nämligen (I) e = f = 1, r = 2 : pO_{K} = q_{1}q_{2} och p splittrar komplett i K. (II) e = r = 1, f = 2 : pO_{K} = q och p kvarstår prim i K. (III) f = r = 1, e = 2 : pO_{K} = q^{2} och p är totalt ramifierad i K. Vilket av de tre fallen gäller för ett givet p kan ges explicit i termer av Kronecker symboler. Vi har Sats 101. Låt d vara ett kvadratfritt heltal, K = Q(\sqrt{d}). Låt p ∈ Z vara ett primtal. Då

(i) p splittrar komplett i K ⇔ p † d_{K} och (\frac{d}{p}) = 1. (ii) p kvarstår prim i K ⇔ p † d_{K} och (\frac{d}{p}) = −1. (iii) p är totalt ramifierad i K ⇔ p|d_{K}. Obs! För udda p är Kronecker symbolen samma sak som Legendre symbolen. Alltså i del (i) (resp. del (ii)) är (\frac{d}{p}) = 1 (resp. = −1) omm x^{2} ≡ d (mod p) är lösbar (resp. ej lösbar).

För p = 2, då 2 † d_{K} omm d ≡ 1 (mod 4), enligt Kor. 100. Alltså, i del (i) (resp. del (ii)) är (\frac{d}{2}) = 1 (resp. = −1) omm d ≡ 1 (mod 8) (resp. d ≡ 5 (mod 8)). Alltså, det mest koncisa sättet att formulera Sats 101 är ‘(i) p splittrar komplett i K ⇔ (\frac{d_{K}}{p} ) = 1. (ii) p kvarstår prim i K ⇔ (\frac{d_{K}}{p} ) = −1. (iii) p är totalt ramifierad i K ⇔ (\frac{d_{K}}{p} ) = 0’. Till slut, notera att del (iii) av satsen är ett speciellt fall av Prop. 96.

Bevis av sats 101 : Props. 13.1.3 och 13.1.4 på utdelade stencilen nr.

13. Vi bevisade bara 13.1.3 under föreläsningen.

Ett exempel av prim faktorisering

Vi avslutar detta avsnitt med ett explicit exempel av prim faktorisering av ett idéal i en kvadratisk kropp. Exempelt finns på utdelad stencil nr. 15, men metoden som presenteras där kan uppskattas mycket bättre i kontexten av våra resultat om ramificiering (Sats 101). Följande är alltså en alternativ (och mycket bättre !) presentation.

Exempel : Faktorisera huvudidéalet < 18 > i Z[\sqrt{−17}].

Lösning : Låt K = Q(\sqrt{−17}). Notera att −17 ≡ 3 (mod 4) så att Z[\sqrt{−17}] = O_{K} och

d_{K} = 4(−17) = −68.

Den prima faktoriseringen av 18 i Z är

18 = 2 · 3^{2},

alltså räcker det att kunna faktorisera huvudidéalen < 2 > och < 3 > i O_{K}. För detta använder vi Sats 101 och dess bevis.

(a) 2|d_{K} så 2 ramifierar i K och

< 2 > = q_{1}^{2},

där

q_{1} = < 2, 1 + \sqrt{−17} > .

(b) 3 † d_{K} och (\frac{−17}{3}) = (\frac{1}{3}) = 1, och 1^{2} ≡ −17 (mod 3), så att 3 splittrar i K och

< 3 > = q_{2}q_{3},

där

q_{2} = < 3, 1 + \sqrt{−17} >

och

q_{3} = q′_{2} = < 3, 1 − \sqrt{−17} > .

Äntligen har vi då att

< 18 > = q_{1}^{2} (q_{2}q_{3})^{2} = q_{1}^{2}q_{2}^{2}q_{3}^{2}.

Del 4 : Enheter

Låt K = Q(\sqrt{d}) vara en kvadratisk kropp, där d är ett kvadratfritt heltal. Enligt Sats 99 har ett element u ∈ O_{K} en unik representation u = x + y\sqrt{d} där

(I) d ≡ 2, 3 (mod 4) ⇒ x, y ∈ Z.

(II) d ≡ 1 (mod 4) ⇒ antingen x, y ∈ Z eller x = x_{1}/2, y = y_{1}/2 där x_{1}, y_{1} ∈ Z och är udda.

Enligt Sats 95(v) ges enheterna då av alla heltalslösningarna till ekvationerna

x^{2} − dy^{2} = ±1, om d ≡ 2, 3 (mod 4),  (223)
(x + \frac{1}{2}y)^{2} − \frac{1}{4}dy^{2} = ±1, om d ≡ 1 (mod 4).  (224)

Notera också att avbildningen

(x, y) ↦ (x − y, 2y)  (225)

ger en injektion från lösningarna till (223) till lösningarna till (224).

Vårt mål är att bevisa Dirichlets sats om enheter för kvadratiska kroppar, och att tillämpa resultatet till Pells ekvation (se Sats 42, ekv. (113)). I fallet d < 0 har kroppen K = Q(\sqrt{d}) två komplexa och inga reella inbäddningar. Då säger Dirichlets sats att O_{K}^{×} är en ändlig grupp. Beviset av detta faktum är ganska trivialt. Vi har

Proposition 102. Låt d < 0 vara kvadratfritt.

(i) Om d = −1 då har (223) fyra lösningar (±1, 0), (0, ±1). Alltså är O_{Q(i)}^{×} = {±1, ±i} ≅ Z/4Z.

(ii) Om d = −3 då har (224) sex lösningar (±1, 0), (0, ±1), ±(1, −1). Alltså är O_{Q(\sqrt{−3})}^{×} = \{±1, ±\frac{1}{2}(1 ± \sqrt{3})\} ≅ Z/6Z.

(iii) Om d ≠ −1, −3, då har (224) bara två lösningar (±1, 0), och O_{Q(\sqrt{d})}^{×} = {±1} ≅ Z/2Z.

För d > 0 har K = Q(\sqrt{d}) två reella och inga komplexa inbäddningar och Dirichlets sats säger att O_{K}^{×}, modulo en ändlig grupp av enhetsrötter, är en oändlig cycklisk grupp. Beviset av detta faktum är betydligt svårare. Vår metod ska använda idéer av en annorlunda karaktär från de som träffats hittills, speciellt följande resultat av Dirichlet, som är det enklaste (och äldste) resultatet i ett område inom talteori som kallas för Diofantisk approximation.

Dirichlets approximationsats. Låt θ_{1}, θ_{2} vara reella tal med θ_{2} > 1. Då finns det heltal p, q, med 0 < q < θ_{2} så att

|qθ_{1} − p| ≤ 1/θ_{2}.  (226)

Bevis : (Se också Baker s.43). Antag först att θ_{2} ∈ N. För värje q så att 0 < q ≤ θ_{2} sätt

r_{q} := qθ_{1} − [qθ_{1}].

Detta ger θ_{2} reella tal (kanske med repititoner) i intervallen [0, 1). Dela upp denna intervall i θ_{2} delintervaller I_{t} där

I_{t} = [\frac{t}{θ_{2}} , \frac{t + 1}{θ_{2}}) , t = 0, 1, ..., θ_{2} − 1.

Då har vi följande två möjligheter :

Fall I : Det finns q_{1} ≠ q_{2} så att både r_{q_{1}}, r_{q_{2}} ∈ I_{t} för något t. WLOG, q_{1} > q_{2}. Då har vi att

|qθ_{1} − p| < 1/θ_{2},

där q = q_{1} − q_{2}, så att 0 < q < θ_{2}, och p = [q_{1}θ_{1}] − [q_{2}θ_{2}]. Fall II : Det finns precis en r_{q} i varje I_{t}. Då finns det q_{1} ≠ q_{2} så att r_{q_{1}} ∈ I_{0} och r_{q_{2}} ∈ I_{θ_{2}−1}. Låt q = min{q_{1}, q_{2}}. Då är 0 < q < θ_{2} och |qθ_{1} − p| ≤ 1/θ_{2} där p = [qθ_{1}]. Detta avslutar beviset när θ_{2} ∈ N. För θ_{2} ∉ N, tillämpa resultatet för paret (θ_{1}, [θ_{2}] + 1). Obs! Det följer från ovanstående bevis att satsen stämmer med en STRÄNG olikhet i (226) om inte θ_{1} ∈ Q. En direkt, och imponerande tillämpning av Dirichlets sats är Sats 103. Låt d vara ett heltal som inte är en perfekt kvadrat. Då finns det oändligt många (x, y) ∈ Z^{2} så att x^{2} − dy^{2} = 1. Bevis : Kommer nästa gång.

Notation : Låt K vara en kvadratisk kropp, x ∈ K. Då ska x′ beteckna bilden av x under den unika icke-triviala automorfismen av K. Alltså, om K = Q(\sqrt{d}) och x = α + β\sqrt{d}, där α, β ∈ Q, då är x′ = α − β\sqrt{d}.

Bevis av sats 103 : (se Baker s.64-65). Låt m > 0. Tillämpa Dirichlets approximationsats till paret θ_{1} = \sqrt{d}, θ_{2} = m\sqrt{d}. Då finns det heltal p_{m}, q_{m}, med 0 < q_{m} < m\sqrt{d} så att

|p_{m} − q_{m}\sqrt{d}| < \frac{1}{m\sqrt{d}}.  (227)

Sätt α_{m} := p_{m} − q_{m}\sqrt{d}, så att |α_{m}| < 1/m\sqrt{d}. Vi har att

α′_{m} = p_{m} + q_{m}\sqrt{d} = α_{m} + 2q_{m}\sqrt{d} ⇒ |α′_{m}| ≤ |α_{m}| + 2q_{m}\sqrt{d}
< \frac{1}{m\sqrt{d}} + 2q_{m}\sqrt{d}
< 3q_{m}\sqrt{d}, säg.

Då har vi att

|n(α_{m})| = |α_{m}α′_{m}| = |α_{m}| · |α′_{m}| < \frac{1}{m\sqrt{d}} · 3q_{m}\sqrt{d} < 3\frac{q_{m}}{m} < 3\sqrt{d}.

Poängen är att |n(α_{m})| är begränsad oberoende av m.

Näst, eftersom \sqrt{d} ∉ Q då är varje α_{m} ≠ 0. Men 1/m\sqrt{d} → 0 då m → ∞, så det måste finnas oändligt många olika tal bland de α_{m}. Eftersom deras normer är begränsade, hittar vi då oändligt många olika tal av formen p − q\sqrt{d}, där p, q ∈ Z och q > 0, vars normer är alla lika, till N säg. Vidare kan vi nu välja en oändlig delmängd av dessa tal så att alla p är kongruenta till varandra modulo N, och detsamma för alla q. Välj nu två bland dessa tal, säg α_{i} = p_{i} − q_{i}\sqrt{d}, för i = 1, 2 och betrakta

η := \frac{α_{1}}{α_{2}} .

Påstående : η ≠ ±1 och η = x + y\sqrt{d}, där x, y ∈ Z och x^{2} − dy^{2} = 1.

Först, α_{1} ≠ α_{2} ⇒ η ≠ 1. Att η ≠ −1 följer från att både q_{1} och q_{2} är positiva. A priori är η = x + y\sqrt{d} för några x, y ∈ Q, och x^{2} − dy^{2} = ηη′ = n(η) = n (\frac{α_{1}}{α_{2}} ) = \frac{n(α_{1})}{n(α_{2})} = 1. Alltså, kvarstår det att bevisa att x, y ∈ Z. En explicit beräkning ger

η = \frac{α_{1}}{α_{2}} = \frac{α_{1}α′_{2}}{n(α_{2})} = \frac{(p_{1} − q_{1}\sqrt{d})(p_{2} + q_{2}\sqrt{d})}{N},

så att

x = \frac{p_{1}p_{2} − q_{1}q_{2}d}{N}, y = \frac{p_{1}q_{2} − q_{1}p_{2}}{N} .  (228)

Det följer nu från faktumet att p_{1} ≡ p_{2} och q_{1} ≡ q_{2} modulo N att täljarna i båda uttrycken i (228) är delbara med N, och alltså att x, y ∈ Z, v.s.v.

Detta räcker nu för att bevisa Sats 103, eftersom α_{1} och α_{2} valdes från en oändlig mängd, så att det finns oändligt många möjligheter för talet η.

Viktig anmärkning : Ovanstående bevis, tillsammans med beviset av Dirichlets approximationssats, är konstruktiva, men ger en ganska krånglig algoritm för att skapa lösningar till x^{2} − dy^{2} = 1. Denna algoritm kan uppfattas på ett mycket mer elegant sätt med hjälp av kedjebråk. Se Lektion 26 nedan.

Vi vill ge två tillämpningar av Sats 103. Den första är avslutningen av beviset av Dirichlets sats för kvadratiska kroppar :

Sats 104. Låt d > 0 vara kvadratfritt och K = Q(\sqrt{d}). Då är O_{K}^{×} ≅ {±1} × Z.

Bevis : (se Baker, s.65). Enligt Sats 103 är O_{K}^{×} en oändlig mängd. Speciellt, finns det en enhet η ≠ ±1. Bland de fyra enheterna ±η, ±1/η finns det precis en som är > 1 i den triviala inbäddningen av K i R, dvs den inbäddningen där vi tar den positiva roten \sqrt{d}. Vi fixerar nu denna inbäddning och betrakta mängden

S = {x ∈ O_{K}^{×} : x > 1}.

Ovanstående argument betyder att S ≠ ∅. Låt s ∈ O_{K}^{×}. Enligt Sats 99 är s = u + v\sqrt{d} där åtminstone 2u, 2v ∈ Z.

Påstående : Om s ∈ S då är u, v > 0.

Eftersom s ∈ O′_{K} så är u − v\sqrt{d} = s′ = ±1/s.

Först, eftersom s > 1 så måste s > s′, som antyder att v > 0. Alltså är v ≥ 1/2 ⇒ v\sqrt{d} ≥ 1/2.

Näst är faktiskt |s′| = 1/|s| < 1. Om u < 0 då är u ≤ −\frac{1}{2} ⇒ s′ = u − v\sqrt{d} ≤ −\frac{1}{2} − \frac{1}{2} = −1, en motsägelse.

Till slut, om u = 0 då är s = v\sqrt{d} och ss′ = ±1 = −v^{2}d som kan satisfieras (eftersom 2v ∈ Z) omm d = 1, v = ±1 eller d = 4, v = ±\frac{1}{2}. I båda fall har vi en motsägelse, eftersom d måste vara kvadratfritt.

Detta bevisar påståendet.

Från påståendet följer det att mängden S innehåller ett minsta element. Låt det betecknas med ϵ. Låt nu η vara en godtycklig enhet så att η > 0. Då finns det ett unikt bestämt m ∈ Z så att

ϵ^{m} ≤ η < ϵ^{m+1} ⇒ 1 ≤ \frac{η}{ϵ^{m}} < ϵ.

Valet av ϵ antyder nu att faktiskt η = ϵ^{m}.

Till slut, eftersom antingen η eller −η är > 0 för varje η ∈ O_{K}^{×}, så visar ovanstående argument att

O_{K}^{×} = {±1}× < ϵ >,

och att ϵ genererar en oändlig cyklisk grupp. Detta avslutar beviset av Sats 104.

Viktig anmärkning : En enhet ϵ som genererar O_{K}^{×} modulo ±1 kallas för en fundamental enhet. Ovanstående bevis är också konstruktiv, dvs ger en algoritm för att skapa en fundamental enhet. Vi har sett att en fundamental enhet ges av det minsta elementet i mängden S = {x ∈ O_{K}^{×} : x > 1}. Från påståendet i mitten av beviset vet vi att varje element av S är av formen u + v\sqrt{d} där u, v > 0. Motsatsen stämmer också, dvs om ζ = u + v\sqrt{d} är en enhet med u, v > 0, då är ζ > 1. För d > 1 och 2u, 2v ∈ Z ⇒ u, v ≥ \frac{1}{2}. Nu har vi följande algoritm för att skapa en fundamental enhet :

Steg 1 : Skapa en lösning η = x+y\sqrt{d} till ekvationen x^{2}−dy^{2} = 1 (x, y ∈ Z), enligt den krångliga algoritmen som nämnades i föregående anmärkning.

Steg 2 : Precis en av ±1, ±1/η är > 1. Låt denna kallas för ζ.

Steg 3 : Vi har att ζ = u + v\sqrt{d} för några u, v > 0 så att 2u, 2v ∈ Z. Både u och v har beräknats i Steg 1 och 2. Det finns en fundamental enhet ϵ = u_{0} + v_{0}\sqrt{d} så att

u_{0}, v_{0} > 0, 2u_{0}, 2v_{0} ∈ Z, u_{0} + v_{0}\sqrt{d} ≤ u + v\sqrt{d}, u_{0}^{2} − v_{0}^{2}d = ±1.

Det är klart att det finns bara ändligt många par (u_{0}, v_{0}) som satisfierar dessa fyra villkor. Det minsta av dem är en fundamental enhet.

Vår andra tillämpning av Sats 103 är till Pells ekvation. Först en teknisk lemma

Lemma 105. Låt d vara ett kvadratfritt heltal, K = Q(\sqrt{d}). Låt e ∈ Z och betrakta

G_{e} = \{u + v\sqrt{d} ∈ O_{K}^{×} : v = n\frac{e}{2} för något n ∈ Z\}.

Då är G_{e} en oändlig delgrupp till O_{K}^{×} som innehåller {±1}, och därför av formen

G_{e} = {±1}× < η >,  (229)

där η = ϵ^{m} är någon potens av en fundamental enhet, och genererar en oändlig cyklisk grupp.

Bevis : ±1 = ±1 + 0\sqrt{d} och 0 = 0 · \frac{e}{2} ⇒ \{±1\} ⊆ G_{e}.

Näst visar vi att om x ∈ G_{e} då är x^{−1} ∈ G_{e}. Låt x = u + v\sqrt{d} där v = n\frac{e}{2}, säg. Eftersom x är en enhet, har vi då att

x^{−1} = ±(u − v\sqrt{d}) ⇒ x^{−1} ∈ G_{e}.

Näst visar vi att G_{e} är sluten under multiplikation. Låt x_{1}, x_{2} ∈ G_{e}, säg

x_{1} = u_{1} + v_{1}\sqrt{d}, där v_{1} = n_{1} \frac{e}{2},
x_{2} = u_{2} + v_{2}\sqrt{d}, där v_{2} = n_{2} \frac{e}{2}.

Då är x_{1}x_{2} = u + v\sqrt{d}, där

v = \frac{e}{2} (u_{1}n_{2} + u_{2}n_{1}) .

Därför måste vi visa att u_{1}n_{2} + u_{2}n_{1} =: T ∈ Z.

Om u_{1}, u_{2} ∈ Z då är T ∈ Z. A priori (Sats 99) vet vi att 2u_{1}, 2u_{2} ∈ Z. Antag WLOG att u_{1} ∉ Z så att u_{1} = z_{1}/2 där z_{1} är udda. Från Stas 99 måste v_{1} vara av samma form, så att både e, n_{1} är udda.

Fall I : n_{2} udda. Då är v_{2} ∉ Z ⇒ u_{2} ∉ Z ⇒ u_{2} = z_{2}/2 där z_{2} är udda. Nu har vi att

T = \frac{1}{2} (z_{1}n_{2} + z_{2}n_{1}) ∈ Z, eftersom z_{1}, z_{2}, n_{1}, n_{2} är alla udda.

Fall II : n_{2} jämt. Då är u_{1}n_{2} ∈ Z. Oclså v_{2} ∈ Z ⇒ u_{2} ∈ Z ⇒ u_{2}n_{1} ∈ Z. Då har vi igen att T ∈ Z.

Vi har nu bevisat att G_{e} är en delgrupp till O_{K}^{×} som innehåller {±1}. Det kvarstår att bevisa att den är en oändlig mängd. Eftersom G_{e} ⊇ G_{2e}, betrakta G_{2e} i stället. Det består av alla enheter u + v\sqrt{d} så att u, v ∈ Z och e|v. Dvs, den består av alla lösningar (u, v_{1}) ∈ Z^{2} till

u^{2} − (de^{2})v_{1}^{2} = ±1.

Eftersom de^{2} inte är en perfekt kvadrat har denna ekvation oändligt många lösningar, enligt Sats 103. Detta avslutar bevisat av lemman.

Sats 106. Låt d > 0 vara ett heltal som inte är en perfekt kvadrat. Då har Pells ekvation (se (113))

t^{2} − du^{2} = 4, (t, u) ∈ Z^{2},  (230)

oändligt många lösningar. Det finns en så-kallad ‘fundamental lösning’ (t_{0}, u_{0}) så att alla lösningarna ges av

\frac{1}{2} (t + u\sqrt{d}) = ± [\frac{1}{2} (t_{0} + u_{0}\sqrt{d})]^{m} , där m ∈ Z.  (231)

Bevis : Antag först att d är kvadratfritt. Låt (t, u) vara en lösning till (230). Notera att 2|t ⇔ 2|u, eftersom 4 † d. Vidare har vi att

(\frac{t}{2})^{2} − d (\frac{u}{2})^{2} = 1.

Då ser vi att (t, u) löser Pells ekvation omm \frac{t}{2} + \frac{u}{2} \sqrt{d} är en enhet i K := Q(\sqrt{d}) av norm 1. Dessa utgör en delgrupp till O_{K}^{×} av index 1 eller 2, som innehåller {±1}. Nu följer resultatet från Sats 104.

Låt nu d vara ett godtyckligt positivt heltal som inte är en perfekt kvadrat. Då kan d skrivas i formen d = e^{2}d_{1} där d_{1} är kvadratfritt. Att (t, u) löser (230) är ekvivalent med att

(\frac{t}{2})^{2} − d_{1} (\frac{e}{2}u)^{2} = 1.

Då har vi en 1-1 korrespondens mellan lösningarna till (230) och enheterna av norm 1 i delgruppen G_{e} till O_{Q(\sqrt{d_{1}})}^{×}. Resultatet följer nu från Lemma 105.

Del 5 : Idéal klasser och binära kvadratiska former

We did not reach this material during the lecture. It is not examinable.

Let K be a number field. We denote by P_{+}(K) the collection of principal fractional ideals a of K such that a has a generator λ with n(λ) > 0.

Proposition. (i) P_{+}(K) is a subgroup of P (K). (ii) P_{+}(K) = P (K) iff either n(x) > 0 for all x ∈ K^{×}, or there exists η ∈ O_{K}^{×} with n(η) = −1. (iii) Otherwise [P (K) : P_{+}(K)] = 2.

Proof : (i), (ii) are obvious. For (iii), there exists by hypothesis x ∈ K^{×} with n(x) < 0, and every unit of K has positive norm. Hence the principal ideal (x) is not in P_{+}(K), and we have the coset decomposition

P (K) = P_{+}(K) ⊔ P_{+}(K) · (x).

Proposition. Let K = Q(\sqrt{d}), where d is a squarefree integer.

(i) There exists x ∈ K with n(x) < 0 iff d > 0. (ii) There exists η ∈ O_{K}^{×} with n(η) = −1 iff the equation x^{2} − dy^{2} = −1 has a solution (x, y) ∈ Z^{2}.

Proof : (i) Every x ∈ K can be expressed as x = a + b\sqrt{d} for some a, b ∈ Q. Then n(x) = a^{2} − b^{2}d, and it is clear that this is negative for some choice of a, b iff d > 0.

(ii) There exists η ∈ O_{K}^{×} with n(η) = −1 iff there exists an integer solution to, according to the value of d, (222) or (223), with −1 on the rhs in both cases. If d ≡ 2, 3 (mod 4), we are thus already done. Now suppose d ≡ 1 (mod 4) and that there exists a unit η with n(η) = −1. We have to show that there exists such an η in G_{2}, in the notation of Lemma 105. Let P = {ϵ ∈ O_{K}^{×} : n(ϵ) = +1}. Then [O_{K}^{×} : P] = 2. Hence, it suffices to show that [O_{K}^{×} : G_{2}] is odd. To prove this, it suffices in turn to show that, if η is a unit and η ∉ G_{2}, then η^{2} ∉ G_{2}.

That η ∉ G_{2} means that η = \frac{1}{2}(x + y\sqrt{d}), where both x, y are odd integers. Then

η^{2} = \frac{x^{2} + dy^{2}}{4} + \frac{xy}{2} \sqrt{d},

from which we immediately see that the same is true of η^{2}.

Definition : The quotient group I(K)/P_{+}(K) is called the group of strict ideal classes of K.

The main result of this section now is

Theorem. Let d be a squarefree integer, K = Q(\sqrt{d}). Then there is a 1-1 correspondence between the strict ideal classes of K and the equivalence classes of binary quadratic forms of discriminant d_{K}.

Proof : See handout 14. Chapter VII of that book is a good reference for further information on quadratic fields and binary quadratic forms.

Remarks : (i) The question of for which d > 0 there exists an integer solution to x^{2} − dy^{2} = −1 will be answered in the next lecture (Theorem 113).

(ii) The group structure on the set of strict ideal classes allows one, by the above theorem, to define a similar structure on the equivalance classes of binary forms of a given fundamental discriminant. Since the proof of the theorem gives an explicit description of the class of forms corresponding to a class of ideals, one may thus write down explicit formulas for ‘multiplying’ two forms. These are called the composition formulas for binary quadratic forms, and were already known to Gauβ.

Supplementär lektion 26 (15/01/01)

The material of this lecture is not examinable.

Continued fractions

There are two distinct ways to introduce the notion of a continued fraction, which illustrate an important philosophical difference :

(a) The constructive/intuitive approach : One starts with a real number and shows how to associate to it a sequence (which may be finite or infinite) of fractions, i.e.: rational numbers, which converge to it. These fractions will be called the convergents to the real number. Of course, there are many ways to do this, e.g.: decimal expansions, but it will be intuitively clear (I hope !) from the construction that the convergents to a real number are, in a sense we can make precise, the best approximations to it by rational numbers. Hence, continued fractions are a basic notion in the subject of Diophantine approximation.

(b) The abstract/formal approach : One begins with, in principle, any sequence (a_{n}), finite or infinite, of REAL numbers (positive if n > 0), and associates to it a sequence of ‘fractions’, which will actually be rational numbers if the terms in the sequence are integers. One then shows that under certain conditions on the a_{n}, the sequences of fractions converge, that different sequences converge to different real numbers, and that each real number is the limit of some sequence.

As in Baker (and most other books), I will begin with approach (a), because it is obviously more natural and in agreement with the historical order, and also because it makes the connection to the whole subject of Diophantine approximation immediately clear. This is an important area of number theory, not just for its’ intrinsic interest, but also because of impressive applications to, for example, (i) the theory of transcendental numbrs (ii) solution of Diophantine equations. Baker’s book is actually a very good introduction to these applications.

On the other hand, the proofs of the main results will be carried out in the more formal setting of approach (b).

Intuitive definition : Let θ ∈ R. We associate to θ a sequence a_{0}, a_{1}, ... of integers, possibly finite, by the following procedure :

θ_{0} := θ.
a_{0} := [θ_{0}].
If a_{0} = θ_{0} then stop,
else 1/θ_{1} := θ_{0} − a_{0}.
a_{1} := [θ_{1}].
If a_{1} = θ_{1} then stop,
else 1/θ_{2} := θ_{1} − a_{1}.
·
·
·

Proposition 107. (i) We have a_{n} > 0 for all n > 0 such that a_{n} is defined. (ii) The process stops if and only if θ is rational. If θ is rational, say θ = p/q(q > 0) in lowest terms, then the numbers a_{0}, ..., a_{n} which appear are precisely the quotients which appear in the Euclidean algorithm for the pair (p, q), i.e.:

p = a_{0}q + r_{0},
q = a_{1}r_{0} + r_{1},
·
·
·
r_{n−3} = a_{n−1}r_{n−2} + r_{n−1}
r_{n−2} = a_{n}r_{n−1} + 0.

Proof : (i) Clear.

(ii) ⇒ It’s clear that θ is rational if the process terminates.

⇐ If θ is rational, then the assertion about the numbers a_{n} is one of those things that’s obvious when you play around with the definition, but rather messy to write down a proof of, so I’ll leave it to yourselves.

We have the associated sequence r_{0}, r_{1}, ... of rational numbers, possibly finite, given by

\begin{matrix}r_{0} := a_{0}, \\ r_{1} := a_{0} + \frac{1}{a_{1}} , \\ r_{2} := a_{0} + _{\frac{1}{a_{1}+ \frac{1}{a_{2}}}} , \\ · \\ · \\ · \\ r_{n} := a_{0} + _{\frac{1}{a_{1}+ \frac{1}{\begin{aligned}a_{2}+ \\ & · \\ & & · \\ & & & ·\frac{1}{a_{n}} \end{aligned}}}} . \\ · \\ · \\ · \end{matrix}  (232)

The sequence of rational numbers (r_{n}) is called the continued fraction expansion of the real number θ. The term r_{n} is called the nth continued fraction corresponding to θ. The sequence r_{n} converges to θ - this is intuitively obvious and will be proven shortly.

The integers a_{n} are called the partial quotients of θ, and the numbers θ_{n} are called the complete quotients of θ.

The first thing now is to satisfy the obvious need for a more concise notation. Hence the fraction r_{n} above will henceforth be denoted by [a_{0}; a_{1}, ..., a_{n}]. We then have the recursive formula

[a_{0}] = a_{0}, [a_{0}; a_{1}, ..., a_{n}] = a_{0} + \frac{1}{[a_{1}; a_{2}, ..., a_{n}]},  (233)

which in turn suggests

Formal definition : Let a_{0}, a_{1}, ... be a sequence (possibly finite) of real numbers, with a_{n} > 0 for all n > 0. The continued fraction expansion corresponding to the sequence (a_{n}) is the sequence of numbers ([a_{0}; a_{1}, ..., a_{n}])_{n≥0} defined by the equations (233). The term [a_{0}; a_{1}, ..., a_{n}] is called the nth continued fraction in the expansion.

Obs! : The condition that a_{n} > 0 for all n > 0 ensures that each continued fraction is actually a real number - that we never get 1/0 appearing.

Notation/terminology : (i) If the sequence of continued fractions in the above definition converges, then the limit is denoted by [a_{0}; a_{1}, a_{2}, ...].

(ii) We can expand the continued fraction [a_{0}; a_{1}, ..., a_{n}] as a formal ‘fraction’ as in (232), and, collecting numerators and denominators, write it in the form p_{n}/q_{n}. Here p_{n}, q_{n} are, in general, just REAL numbers. If all a_{i} are integers, then each continued fraction is a rational number and p_{n}, q_{n} are integers. It’s not clear that p_{n}, q_{n} are in this case always relatively prime - that is, that the continued fraction [a_{0}; a_{1}, ..., a_{n}] is already expressed in lowest terms when we just collect numerators and denominators. This will be proven below. The numbers p_{n}, q_{n} are called the nth convergents in the continued fraction expansion.

Theorem 108. (i) Let (a_{n})_{n≥0} be a (finite or infinite) sequence of real numbers, with a_{n} > 0 for all n > 0. Suppose there exists ϵ > 0 such that a_{n} > ϵ for all n > 0. Then the sequence ([a_{0}; a_{1}, ..., a_{n}])_{n≥0} of continued fractions converges. (ii) Now suppose in addition that all a_{n} are integers. If the continued fractions converge to the real number θ, then the a_{n} are precisely the partial quotients of theta, in the sense of our first, intuitive, definition of continued fractions. Morevover, the convergents p_{n}, q_{n} are relatively prime.

Sketch proof (See Baker, p.45) : Directly for n = 0, 1, 2 and therefafter by induction on n, one shows that the convergents p_{n}, q_{n} satisfy the recurrence relations

p_{0} = a_{0}, q_{0} = 1,  (234)
p_{1} = a_{0}a_{1} + 1, q_{1} = a_{1},  (235)
p_{n} = a_{n}p_{n−1} + p_{n−2}, q_{n} = a_{n}q_{n−1} + q_{n−2} for n ≥ 2  (236)

and that gcd(p_{n}, q_{n}) = 1 under the conditions of part (ii). From the recurrence relations one proves by a simple induction that, for all n ≥ 0,

p_{n}q_{n+1} − q_{n}p_{n+1} = (−1)^{n+1},  (237)

and hence that

|\frac{p_{n}}{q_{n}} − \frac{p_{n+1}}{q_{n+1}} | = \frac{1}{q_{n}q_{n+1}} .  (238)

One sees easily from (234),(235),(236) that, under the conditions of part (i), q_{n} → +∞ as n → ∞, and hence (238) implies that the continued fraction expansion converges in this case.

It remains to prove that, under the conditions of part (ii), the a_{n} are the partial quotients of the limit number θ. Suppose (b_{n})_{n≥0} are the partial quotients of θ. To make life simpler, suppose θ is irrational, so that the sequence (b_{n}) is infinite, and that the sequence (a_{n}) is also infinite - remaining possibilities can be dealt with by trivial modifications of what follows.

Now suppose b_{n} ≠ a_{n} for some n, and choose the smallest such n. Observe that

θ = [b_{0}; b_{1}, ..., b_{n−1}, θ_{n}],  (239)

where θ_{n} is the nth complete quotient of θ and that

θ_{n} = [b_{n}; b_{n+1}, ...] = [a_{n}; a_{n+1}, ...].

Hence

b_{n} − a_{n} = [0; a_{n+1}, ...] − [0; b_{n+1}, ...].  (240)

But it is clear from the definitions that each term on the rhs lies in the interval [0, 1]. Since the lhs is a non-zero integer, the only possibility is that |b_{n} − a_{n}| = 1 and that one of the terms on the rhs is zero. But no continued fraction [0; c_{1}, c_{2}, ...], where the c_{i} are all positive integers, represents zero. Indeed, it also follows quickly from the definition that

[0; c_{1}, c_{2}, ...] ≥ \frac{1}{c_{1} + 1}.

This completes the proof of Theorem 108.

Rational approximations

Let θ be any irrational number. Since Q is dense in R, we can approximate θ arbitrarily well by rational numbers. However, as these rationals approach θ, their denominators (when written as fractions in lowest terms), will obviously get bigger and bigger. More precisely, given N > 0, there exists ϵ = ϵ(θ, N) > 0 such that, if p/q is any rational number written in lowest terms (i.e.: (p, q) = 1 and q > 0), then

|θ − p/q| < ϵ ⇒ q > N.

In the theory of rational approximations, one is interested in sequences of rationals converging to θ whose denominators grow ‘as slowly as possible’, such sequences of approximations being considered ‘good’. Hers’s a precise definition (mostly just for completeness : the terminology used in it is cumbersome and will generally be avoided) :

Definition : Let f : N → R^{+} be any strictly increasing function. Let θ be an irrational number. Let r = p/q be any rational number, written in lowest terms. Then r is said to approximate θ well with respect to f if

|θ − p/q| ≤ 1/f(q).  (241)

The number θ is said to be rationally approximable to order f if there exists a sequence (r_{n}) of rational numbers which converges to θ, and such that each r_{n} approximates θ well w.r.t. f.

For the remainder of this section all rational numbers, when presented as fractions, are assumed to be written in lowest terms.

Dirichlet’s approximation theorem gives a non-trivial ‘lower bound’ on how well one can rationally approximate an arbitrary irrational number. We have

Theorem 109. Let θ be any irrational number. Then there exists a sequence p_{n}/q_{n} of rational numbers converging to θ such that

|θ − \frac{p_{n}}{q_{n}} | < \frac{1}{q_{n}^{2}} .  (242)

A classical result of Lindemann (1844) places upper bounds on how well one can rationally approximate an irrational algebraic number θ. This result, and its’ subsequent improvements over the following century or so, have far-reaching consequences, for example in the theory of transcendental numbers and for the solution of certain Diophantine equations. In these notes, we will concentrate on presenting the intimate connection between ‘good’ rational approximations to an irrational number θ and the continued fraction expansion of θ.

These connections are summed up by Theorem 110. Let θ be an irrational number. Let p_{n}, q_{n} be the sequence of convergents in the continued fraction expansion of θ. Let (a_{n}) be the sequence of partial quotients.

(i) We have the following inequalitites

|θ − \frac{p_{n}}{q_{n}} | ≤ \frac{1}{q_{n}q_{n+1}} < \frac{1}{q_{n}^{2}} .  (243)
|θ − \frac{p_{n+1}}{q_{n+1}} | ≤ \frac{q_{n}}{q_{n+1}} |θ − \frac{p_{n}}{q_{n}} | .  (244)
\frac{1}{(a_{n+1} + 2)q_{n}^{2}} < |θ − \frac{p_{n}}{q_{n}} | < \frac{1}{a_{n+1}q_{n}^{2}} .  (245)

(ii) The convergents are the ‘best’ rational approximations to θ in the sense that, for each n ≥ 0, if p/q is a rational number with q < q_{n+1}, then

|qθ − p| ≥ |q_{n}θ − p_{n}|.

(iii) For each n either

|θ − \frac{p_{n}}{q_{n}} | < \frac{1}{2q_{n}^{2}} or |θ − \frac{p_{n+1}}{q_{n+1}} | < \frac{1}{2q_{n+1}^{2}} .  (246)

More impressively, if p/q is any fraction such that |θ − p/q| < 1/2q^{2}, then p = p_{n}, q = q_{n} for some n.

Proof : The first inequality (243) follows from (238) and the fact, obvious from the definition of continued fractions, that

n even ⇒ p_{n}/q_{n} < θ,
n odd ⇒ p_{n}/q_{n} > θ.

For the rest of the proof, see Baker p.46-7. Note the importance of the equation

θ = \frac{p_{n}θ_{n+1} + p_{n−1}}{q_{n}θ_{n+1} + q_{n−1}} ,  (247)

which follows from the recurrence relations (234),(235),(236). Note further that, as Baker indicates, it is possible to strengthen part (iii) considerably. We will ignore this direction.

For more on rational approximations, in particular Lindemann’s theorem, its’ improvements and consequences, see Baker, sections 6.5,6.6,6.7,8.2,8.3.

Quadratic irrationals

In this and remaining sections, we only consider ‘simple’ continued fractions, i.e.: those satisfying the conditions of Theorem 108(ii).

We wish to state the classic theorem of Lagrange on the continued fraction expansions of quadratic irrational numbers, i.e.: irrational elements of quadratic number fields. First, the required definitions :

Definition : The continued fraction [a_{0}; a_{1}, ...] is said to be ultimately periodic if there exists k ≥ 0, m > 0 such that a_{l+m} = a_{l} for all l ≥ k. The smallest such m is called the period of the continued fraction. If k = 0 we say that the continued fraction is (purely) periodic.

Theorem 111 (Lagrange). Let θ be an irrational number. The continued fraction expansion of θ is ultimately periodic if and only if θ is a quadratic irrational.

Proof : Baker, p.48-9. Note the role of (247) again.

Obs! The proof gives an algorithm for computing, for a given θ, the least numbers k, m in the above definition.

Theorem 112. (i) Let θ be a quadratic irrational. The continued fraction of θ is purely periodic iff θ > 1 and −1 < θ′ < 0. (ii) Let d be a positive integer other than a perfect square. Then the continued fractions of \sqrt{d} + [\sqrt{d}] and 1/(\sqrt{d} − [\sqrt{d}]) are purely periodic. The continued fraction of \sqrt{d} satisfies a_{l+m} = a_{l} for all l ≥ 1.

Proof : Baker, p.50.

The equations x^{2} − dy^{2} = ±1

Let d > 0 not be a perfect square. The solutions in positive integers x, y to the equations x^{2}−dy^{2} = ±1, which were studied in the previous two lectures, can be nicely characterised in terms of the continued fraction of \sqrt{d}. We have

Theorem 113. Let m be the period of the continued fraction of \sqrt{d}. Let p_{n}, q_{n} be the convergents.

(i) The positive integers x, y satisfy x^{2}−dy^{2} = 1 if and only if x = p_{n}, y = q_{n} for some odd n ≡ −1 (mod m). (ii) If m is even, then there are no solutions in positive integers to x^{2}−dy^{2} = −1. If m is odd, then all solutions are given by x = p_{n}, y = q_{n}, where n is even and n ≡ −1 (mod m).

Proof : Part (i) is proved in Baker, p.75-6, and the proof of (ii) is similar.