Talteori översiktsföreläsning

1. Analytisk talteori

1.1. Primtalsräkning

1.1.1. Primtalsräknarfunktionen

\(\pi(x) = \sum_{k \le x} \mathrm{IsPrime}(k)\)

\(\pi(x) \sim \frac{x}{\log x}\) då \(x \to \infty\).

1.1.2. Hadamard

wikiHadamard.jpg
Illustration 1 Hadamard

1.1.3. Primtalens täthet

Primtalstäthetsfunktion \(\pi(x)/x\).

\(\pi(x)/x \sim 1/\log(x)\).

Följer av primtalssatsen.

Sannolikheten att ett positivt heltal \(\le 1000\) är ett primtal är \(p(1000)/1000 \approx \frac{1}{\log(1000)}\) vilket är cirka . I själva verket finns

primtal \(\le 1000\).

1.1.4. Approximation av primtalstäthet

\(p(x)/x = \sum_{k=1}^{n-1} \frac{(k-1)!}{\log(x)^k} + \mathcal{O}\left( \frac{(n-1)!}{(log(x)^n)} \right)\) as \(x \to \infty\).

prim-funk-approx.png
Illustration 2 Första tre approximationerna till primtalstäthetsfunktionen

1.2. Partitioner

Partitions.options(convention=’french’,latex=’list’)

\(n\) positivt heltal. En (heltals)partition \(\lambda \vdash n\) är en svagt avtagande heltalsföljd som summerar till \(n\).

\(\lambda=(3,3,2,1,1,1) \vdash 11\). Det finns \(\sage{Partitions(5).cardinality()}\) partitioner av \(5\), nämligen \[\sage{Partitions(5).list()}\]

  • Young-diagrammet av en partition är en hög lådor, svarande mot delarnas storlek
  • Konjugatet till en partition fås genom att svänga runt diagrammet
  • \[\begin{split} \lambda &=(4,4,2,1) =\young(~~~~,~~~~,~~,~) \\ \lambda^* & = (4,3,2,2) = \young(~~~~,~~~,~~,~~) \end{split}\]
  • Ger bijektion mellan partitioner med högst \(k\) delar och partitioner vars delar är \(\le k\)

f = 1/((1-x)*(1-x2)*(1-x3)*(1-x4))

  • Högst 4 delar, eller storlek på delar \(\le 4\)
  • \(c_j\) räknar antal sådana partitioner av \(j\)
  • \(p_4(x) = \sum_{j \ge 0}c_jx^j\) generande funktion
  • \(p_4(x) = \sage{f.series(x==0,order=7)}\)
  • Lätt att se att \( p_4(x) = \sage{f} \)
  • Partialbråksuppdelning: \( p_4(x) = \sage{f.partial_fraction()} \)
  • Ger asymptotisk växt av \(c_j\) (som funktion av \(j\))

def p(n): return Partitions(floor(n)).cardinality() def hr(n): return exp(pi*sqrt(2*n/3))/(4*n*sqrt(3))

\(p(n)\) antal partitioner av \(n\).

\[\sum_{n =0}^\infty p(n)x^n = \prod_{k=1}^\infty \frac{1}{1-x^k}\]

\(p(n) \sim \frac{1}{4n \sqrt{3}}\exp \left(\pi \sqrt{ \frac{2n}{3}} \right)\) as \(n \to \infty\).

1.2.1. G. H. Hardy

2. ”Geometry of Numbers”

2.1. Gitterpunkter i konvexa kroppar

\(D \subset {\mathbb{R}}^n\) konvex, volym \(> 2^n\), \(-D=D\). Då innehåller \(D\) gitterpunkt skild från origo.

wikikowski.png

\(A\) area av konvex polygon i planet vars hörnpunkter är gitterpunkter, \(i\) antal inre gitterpunkter, \(b\) antal randpunkter. Då \[A=i+\frac{b}{2}-1\]

2 wikiPick.png

\( i = 7, b = 8, A = i + b/2 - 1 = 10 \)

3. Aritro-algebraisk geometri

3.1. Pythagoreanska tripplar

3.1.1. We kommer att bestämma de Pythagoreanska tripplarna!

Heltalslösningar till \[a^2+b^2=c^2\] svarar mot rational punkt \((a/c,b/c)\) på enhetscirkeln, kan parametriseras med \[a=2mn,\quad b=m^2-n^2, \quad c=m^2+n^2\]

wikiPytTrip

var(”x y”)

3.1.2. Beviset går utanför kursen…

För \(n \ge 3\) så saknar ekvationen \[x^n+y^n=z^n\] icke-triviala heltalslösningar.

4. Kopplingar till algebra

4.1. Ingår i kursen:

4.1.1. Algebrarelaterade spörsmål i kursen:

  • Gruppen \({\mathbb{Z}}_n^*\) är cyclisk då \(n\) är primtalspotens
  • \({\mathbb{Z}}_{nm} \simeq {\mathbb{Z}}_m \times {\mathbb{Z}}_n\) omm \(\gcd(m,n)=1\), samma för \({\mathbb{Z}}_{mn}^*\).
  • \({\mathbb{Z}}[i] = \left\{\,{a+bi}\,\vrule\,{a,b\in {\mathbb{Z}}}\,\right\}\) är ett huvudidealområde domain
  • Hensel-lyft
  • Möbiusinversion

4.2. Inte i kursen

4.2.1. Algebra-relaterade spörsmål vi hoppar

  • Permutationer, cykeltyp, partitioner
  • Algebraiska talkroppar, deras heltal, klasstal

5. Elementär talteori

5.1. Elementär?

5.1.1. Elementär talteori

  • ”Elementär” betyder ingen avancerad analys eller algebra, ingen komplicerad kombinatorik
  • Inte samma som ”lätt”
  • Theorin byggs upp från grunden, i princip inga förkunskaper
  • Men behöver mängdlära, induktion
  • Användbart: linjär algebra

6. Denna kurs

6.1. Litteratur

6.1.1. Textbok: Rosen

  • ”Elementary Number Theory” av Rosen
  • Chapt 1.5, 2.1, 3, 4.1-4, 5.1, 6, 7.1-4, 9, 11.1-4, 12, 13.1-4, 14.
  • Definierar kursen
  • Jag kommer inte att ta upp allt på föreläsningarna
  • Kommer också att använda ”Elementary number Theory” av Stein
  • Hackman’s manuskript rekommenderas som bredvidläsning
  • Gaussiska heltal via Conrads text

6.2. Föreläsningar

6.2.1. Föreläsningar, övningsräkning

  • 19 sessioner
  • Föreläsningar
  • Övningsräkning
  • Lista på rekommenderade övningar på kurshemsidan http://courses.mai.liu.se/GU/TATA54/

6.2.2. Kursöversikt

  1. Heltal, delbarhet
  2. Unik faktorisering
  3. Sgd, Linjära Diofantiska ekvationer
  4. Kongruenser, Kinesiska restsatsen
  5. Multiplicativ ordning, Fermat, Euler
  6. Arithmetiska funktioner, Möbiusinversion
  7. Hensel-lyft
  8. Lagrange, Primitiva rrötter, Diskreta logaritmer
  9. Quadratisk Reciprocitet
  10. Kedjerbråk
  11. Pell’s ekvation
  12. Sum of squares
  13. Gaussiska heltal