Skip to content

Instantly share code, notes, and snippets.

@seewoo5

seewoo5/sage-lecture-beamer.pdf

Last active October 11, 2024 20:08
Show Gist options
  • Save seewoo5/400dbb69b8a4a7831ea6f035d35ad08d to your computer and use it in GitHub Desktop.
Save seewoo5/400dbb69b8a4a7831ea6f035d35ad08d to your computer and use it in GitHub Desktop.
Download ZIP
Number theory tutorial with Sage
Display the source blob
Display the rendered blob
Raw
sage-lecture-beamer.pdf
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Display the source blob
Display the rendered blob
Raw
sage-nt.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Number theory with Sage\n",
"\n",
"This is a jupyter notebook that introduces several examples in Sage, focus on number theory.\n",
"Written by Seewoo Lee ([email protected]), for Math254A guest lecture at UC Berkeley (October 9).\n",
"\n",
"Version >= 10.3 required (maybe)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Basic mathematics\n",
"\n",
"Something you learned before."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Pre-undergraduate\n",
"\n",
"Basic arithmetic, solve polynomial equations, pre-calculus"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"3 * 7"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Compute $\\sum_{i=1}^{100} i$:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"s = 0\n",
"for i in range(1, 101):\n",
" s += i\n",
"print(s) # Gauss did this when he was an elementary school student"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now product, $50!$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# 50!\n",
"s = 1\n",
"for i in range(1, 51):\n",
" s = s * i\n",
"print(s)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# In fact, you can just\n",
"factorial(50)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Number of trailing zeros\n",
"zs = 0\n",
"N = 50\n",
"while N > 1:\n",
" zs += N // 5\n",
" N //= 5\n",
"print(zs)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You can factor a reasonably large number."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a = 2357111317192329 # Your favorite (large) number\n",
"factor(a)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You can also solve equations."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"solve([2 * x + 5 == 7], x)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Solving polynomial equations\n",
"solve([x^2 - 5*x + 6 == 0], x)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Sage can solve these exactly\n",
"solve([x^3 - 5*x + 6 == 0], x)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"solve([x^4 - 5*x + 6 == 0], x)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# But not this\n",
"solve([x^5 - 5*x + 6 == 0], x)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now, let's do some pre-calculus, e.g. differentiation."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Pre-calculus\n",
"t = var('t')\n",
"print(t)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"f1 = exp(t) * sin(2 * t) * (t^2)\n",
"f2 = (log(t + 1) - (t - t^2 / 2 + t^3 / 3)) / t^4\n",
"f3 = f1 * f2"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"df1 = f1.derivative(t)\n",
"df2 = f2.derivative(t)\n",
"df3 = f3.derivative(t)\n",
"print(df1)\n",
"print(df2)\n",
"print(df3)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We have a chain rule:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"e = df3 - (df1 * f2 + f1 * df2)\n",
"print(e)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"e.simplify_full()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can also plot a graph of a function."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"plot(f2, t, -0.5, -0.01) + plot(f2, t, 0.01, 0.5)\n",
"# plot(f2, t, -0.5 ,0.05) does not work well because of t = 0"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"...and even limits! Don't tell this to your 1A students..."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"limit(f2, t=0)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"f4 = 1 / t^2\n",
"limit(f4, t=0)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Some partial fractions?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"h = (t^5 + 2 * t^3 - 3 * t^2 - 1) / (t^4 - 1)\n",
"print(h.partial_fraction(t))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Exercise. How many square-free numbers are there between 1 and 1M?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# `factor(N)` gives a list of prime factors and their powers\n",
"list(factor(60))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Using this, define a function that detects whether a given number is square-free or not\n",
"def is_square_free(n):\n",
" factors = list(factor(n))\n",
" for p, e in factors:\n",
" if e > 1:\n",
" return False\n",
" return True"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"is_square_free(2 * 3 * 5 * 7 * 11)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"cnt = 0\n",
"M = 10^6\n",
"for n in range(1, M + 1):\n",
" if is_square_free(n):\n",
" cnt += 1\n",
"print(cnt)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In fact, we already have `is_squarefree` in Sage, which is faster."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"cnt = 0\n",
"M = 10^6\n",
"for n in range(1, M + 1):\n",
" if is_squarefree(n):\n",
" cnt += 1\n",
"print(cnt)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Note that `is_squarefree` even works for general UFD: see [here](https://doc.sagemath.org/html/en/reference/rings_standard/sage/arith/misc.html#sage.arith.misc.is_squarefree)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Undergraduate\n",
"\n",
"Linear algebra, group theory"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"m = matrix([[1, 0, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0], [1, 2, 1, 0, 0, 0], [1, 3, 3, 1, 0, 0], [1, 4, 6, 4, 1, 0], [1, 5, 10, 10, 5, 1]])\n",
"m"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"m^(-1)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"m^20"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You may found some patterns above, try to prove it by hand."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For Math54 students: solve linear equation, diagonalize a matrix."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Solve a system of linear equations\n",
"A = matrix([[1,2,3],[3,2,1],[1,1,1]])\n",
"Y = vector([0, -4, -1])\n",
"X = A.solve_right(Y) # AX = Y\n",
"print(X)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Diagonalize a matrix\n",
"A = matrix([[1, 1], [1, 0]])\n",
"print(A.eigenvalues())\n",
"D, P = A.eigenmatrix_right()\n",
"print(\"D:\", D)\n",
"print(\"P:\", P)\n",
"print(P * D * P^(-1))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# This may remind you a famous sequence\n",
"A^10"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can even do some group theory. As far as I know, Sage uses [GAP](https://www.gap-system.org/) as a backbone. See GAP's documentation to see how they actually implemented groups.\n",
"\n",
"Try to guess the answers before you run the codes."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Group theory\n",
"S4 = SymmetricGroup(4)\n",
"print(S4.order())\n",
"print(S4.is_abelian())\n",
"print(S4.is_solvable())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"S5 = SymmetricGroup(5)\n",
"print(S5.order())\n",
"print(S5.is_abelian())\n",
"print(S5.is_solvable())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"A4 = AlternatingGroup(4)\n",
"A5 = AlternatingGroup(5)\n",
"print(A4.is_simple())\n",
"print(A5.is_simple())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"cs = S5.composition_series() # Randomized algorithm\n",
"for H in cs:\n",
" print(H)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"S100 = SymmetricGroup(100)\n",
"print(S100.order())\n",
"sigma = S100(\"(1,2,3,4) (5,6,7,8,9) (10,11,12) (13,93,94,95,96,97)\")\n",
"print(sigma.order())\n",
"print(sigma.sign())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(SymmetricGroup(3).cayley_table())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"S3 = SymmetricGroup(3)\n",
"g1 = S3(\"(1, 2, 3)\")\n",
"g2 = S3(\"(2, 3)\")\n",
"print(g1 * g2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can also check some Sylow theory. For each prime $p$ divides $\\#G$, there exists a unique subgroup of order $p^e$ with $p^e \\| \\#G$ up to conjugation. We can enumerate all conjugacy classes of a given $G$, you can find that there are two conjugacy classes with unique orders, which are Sylow subgroups."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Sylow p-subgroup\n",
"D20 = DihedralGroup(20)\n",
"print(D20.order())\n",
"subgps = D20.conjugacy_classes_subgroups()\n",
"print([H.order() for H in subgps])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Exercise. How many 2 by 2 integer matrices with determinant 1 and absolute value of each entry at most $N = 100$ are there?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You can loop over all $a, b, c, d \\in [-N, N]$, but this is not efficient. In fact, you only need to loop over $a, b, c$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"N = 100\n",
"cnt = 0\n",
"for a in range(-N, N + 1):\n",
" for b in range(-N, N + 1):\n",
" for c in range(-N, N + 1):\n",
" if a == 0:\n",
" if b * c == 1:\n",
" # All d in [-N, N] are possible\n",
" cnt += (2 * N + 1)\n",
" elif (b * c + 1) % a == 0:\n",
" cnt += 1\n",
"print(cnt)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You can make it faster by only considering $(a, b)$ with $\\gcd(a, b) = 1$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"N = 100\n",
"cnt = 0\n",
"for a in range(-N, N + 1):\n",
" for b in range(-N, N + 1):\n",
" if gcd(a, b) == 1:\n",
" for c in range(-N, N + 1):\n",
" if a == 0:\n",
" if b * c == 1:\n",
" # All d in [-N, N] are possible\n",
" cnt += (2 * N + 1)\n",
" elif (b * c + 1) % a == 0:\n",
" cnt += 1\n",
"print(cnt)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Finding a good asymptote as $N \\to \\infty$ is not an easy problem."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Basic number theory"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Undergraduate number theory\n",
"\n",
"Modular arithmetic, Euclid's algorithm (Bezout's identity), quadratic residue and reciprocity, primitive root."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"12345678987654321 % 37"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"a = 8839268127\n",
"b = 1490210333\n",
"g = gcd(a, b)\n",
"print(g)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Bezout's identity\n",
"g, c1, c2 = xgcd(a, b)\n",
"print(g, c1, c2)\n",
"print(a * c1 + b * c2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You can compute Legendre symbole, which is the function `kronecker(a, b)` for $\\left(\\frac{a}{b}\\right)$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"p = 81373\n",
"q = 86753\n",
"print(p % 4, q % 4)\n",
"print(kronecker(p, q))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Can you guess the answer for the following code?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(kronecker(q, p))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"F$\\ell$T (Fermat's $\\ell$ittle Theorem)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"Zmodq = IntegerModRing(q)\n",
"p_ = Zmodq(p)\n",
"print(p_^(q-1))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Primitive root and discrete logarithm."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Primitive root exists when modulus = 2, 4, p^n or 2 * p^n\n",
"g = primitive_root(q)\n",
"g_q = Zmodq(g)\n",
"e = p_.log(g_q)\n",
"print(g_q, e, g_q^e)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Exercise.\n",
"\n",
"1. Understand how RSA cryptosystem works (see [Wikipedia](https://en.wikipedia.org/wiki/RSA_(cryptosystem))).\n",
"2. Write a code to crack RSA cryptosystem. Now we have public keys $(n, e) = (6700238097692010877, 4751936151942303811)$ and encrypted message $c = 6154760121873467048$. Find the message $m$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def break_RSA(n, e, c):\n",
" factors = factor(n)\n",
" p, q = factors[0][0], factors[1][0]\n",
" ln = lcm(p-1, q-1)\n",
"\n",
" R1 = IntegerModRing(n)\n",
" R2 = IntegerModRing(ln)\n",
"\n",
" # Find decryption key\n",
" d_ = R2(e)^(-1)\n",
" d = ZZ(d_)\n",
"\n",
" # Decrypt\n",
" c_ = R1(c)\n",
" m_ = c_^d\n",
" m = ZZ(m_)\n",
" return m"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"break_RSA(6700238097692010877, 4751936151942303811, 6154760121873467048)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### $p$-adic numbers\n",
"\n",
"Here are some examples with $p$-adic numbers: basic arithmetic, polynomials, and special functions."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You can define $\\mathbb{Z}_{p}$ and $\\mathbb{Q}_{p}$ with `Zp` and `Qp`."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Choose your favorite prime number p\n",
"p = 7\n",
"Z_p = Zp(p, prec=10)\n",
"Q_p = Qp(p, prec=10)\n",
"v = Q_p.valuation()\n",
"print(Z_p)\n",
"print(Q_p)\n",
"print(v)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(Z_p(1000))\n",
"print(Z_p(-1000))\n",
"a = 1 / Z_p(1 - p)\n",
"print(a, \"valuation:\", v(a)) # 1 + p + p^2 + p^3 + ..."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"b = 1 / Z_p(p)\n",
"print(b, \"valuation:\", v(b))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You can also define polynomials over $\\mathbb{Q}_{p}$ (in fact, over any rings)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Polynomials\n",
"Qpx.<x> = Q_p[]\n",
"f = x^2 + 1\n",
"factors = list(f.factor())\n",
"print(\"number of factors:\", len(factors)) # 1 or 2?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Newton polygon of a polynomial."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Newton polygon\n",
"g = 1 + p * x + (1 / p) * x^2 + p * x^3 + x^6 + p^2 * x^6 + p * x^7\n",
"print(g.newton_polygon())\n",
"degs = [fac[0].degree() for fac in g.factor()]\n",
"print(degs) # degree of factors\n",
"g.newton_polygon().plot()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Field extension can be also defined. Note that only unramified and Eisenstein extensions are implemented in Sage now (Oct 11, 2024)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Field extension\n",
"# Unramified extension\n",
"q = p^5\n",
"Z_q.<u> = Zq(q)\n",
"Q_q.<v> = Qq(q)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(Z_q.uniformizer())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(Z_q.residue_class_field())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(Z_q.has_pth_root())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Eisenstein extension\n",
"x = var('x')\n",
"f = x^4 + p^2 * x^3 + p * x^2 - p\n",
"R_f.<u> = Z_p.ext(f)\n",
"print(u, u.valuation())\n",
"print((u+1)^6)\n",
"print(R_f.residue_ring(1))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can compute special $p$-adic functions, e.g. exponential and logarithm."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Special functions\n",
"a = Z_p(p)\n",
"print(\"exp(a) =\", a.exp())\n",
"print(\"log(1 + a) =\", (1 + a).log())\n",
"\n",
"# exponential diverges when |a| > p^(-1/(p-1)), the following line gives an error message\n",
"# print(exp(Z_p(1 + p^2)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Exercise. How many quadratic extensions of $\\mathbb{Q}_{p}$ are there? Construct them with Sage."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For $p > 2$, we have three: $\\mathbb{Q}_{p}(\\sqrt{u}), \\mathbb{Q}_{p}(\\sqrt{p}), \\mathbb{Q}_{p}(\\sqrt{up})$ where $u$ is a non-quadratic residue modulo $p$. The first extension is unramified."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Example: p = 101\n",
"u = 0\n",
"for i in range(2, p):\n",
" if kronecker(i, p) == -1:\n",
" u = i\n",
" break\n",
"print(\"Non-quadratic-residue\", u)\n",
"\n",
"Q_p = Qp(p)\n",
"K1.<a1> = Q_p.ext(x^2 - u)\n",
"K2.<a2> = Q_p.ext(x^2 - p)\n",
"K3.<a3> = Q_p.ext(x^2 - u * p)\n",
"print(K1) # Unramified\n",
"print(K2)\n",
"print(K3)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For $p = 2$, we have seven (this happens because $2$ is \"small\").\n",
"\n",
"$$\n",
"\\mathbb{Q}_{2}(\\sqrt{- 1}), \\mathbb{Q}_{2}(\\sqrt{\\pm 2}), \\mathbb{Q}_{2}(\\sqrt{\\pm 5}), \\mathbb{Q}_{2}(\\sqrt{\\pm 10})\n",
"$$\n",
"\n",
"(Which one is unramified?) You can find a proof [here](https://github.com/seewoo5/math-notes/blob/main/number-theory/p-adic_numbers/padicprop.pdf).\n",
"\n",
"Unfortunately, extension of $\\mathbb{Q}_{p}$ by general polynomials are not implemented yet. So you need to replace those with Eisenstein polynomials.\n",
"\n",
"$$\n",
"\\begin{align*}\n",
"\\mathbb{Q}_{2}(\\sqrt{-1}) &= \\mathbb{Q}_{2}(-1 + \\sqrt{-1}) = \\mathbb{Q}_{2}[x] / (x^2 + 2x + 2)\\\\\n",
"\\mathbb{Q}_{2}(\\sqrt{5}) &= \\mathbb{Q}_{2}[\\zeta_3] = \\mathbb{Q}_{2}[x] / (x^2 + x + 1) \\\\\n",
"\\mathbb{Q}_{2}(\\sqrt{-5}) &= \\mathbb{Q}_{2}(-1 + \\sqrt{-5}) = \\mathbb{Q}_{2}[x] / (x^2 + 2x + 6)\\\\\n",
"\\end{align*}\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"Q_2 = Qp(2)\n",
"T1.<b1> = Q_2.ext(x^2 + 2*x + 2)\n",
"T2.<b2> = Q_2.ext(x^2 - 2)\n",
"T3.<b3> = Q_2.ext(x^2 + 2)\n",
"T4.<b4> = Q_2.ext(x^2 + x + 1)\n",
"T5.<b4> = Q_2.ext(x^2 + 2*x + 6)\n",
"T6.<b6> = Q_2.ext(x^2 - 10)\n",
"T7.<b7> = Q_2.ext(x^2 + 10)\n",
"print(T1)\n",
"print(T2)\n",
"print(T3)\n",
"print(T4)\n",
"print(T5)\n",
"print(T6)\n",
"print(T7)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Number fields"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Number fields can be defined using `NumberField` via polynomials."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"K.<sq2> = NumberField(x^2 - 2)\n",
"print(K)\n",
"print(sq2^10)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(K.is_galois())\n",
"print(K.galois_group())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(K.discriminant())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Of course, we can do higher degree."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Cubic field\n",
"L.<b> = NumberField(x^3 - p)\n",
"print(L)\n",
"print(L.is_galois())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can take a Galois closure."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"L2.<c> = L.galois_closure()\n",
"print(L2)\n",
"print(L2.is_galois())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"What is the Galois group $\\mathrm{Gal}(L_2 / \\mathbb{Q})$?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(L2.galois_group()) # https://people.maths.bris.ac.uk/~matyd/GroupNames/T15.html#6t2"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Factorization of an ideal can be done. For example, we'll solve one of the exercise from Marcus' *Number Fields*.\n",
"\n",
"Exercise 13 from Chapter 3:\n",
"\n",
"1. Let $S = \\mathbb{Z}[a] / (a^3 - a - 1)$. Verify $(23) = (23, a - 10)^2 (23, a - 3)$.\n",
"2. Show $(23, a - 10, a - 3) = S$, hence two ideals $(23, a - 10), (23, a - 3)$ are relatively prime"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"M.<a> = NumberField(x^3 - x - 1) # M = Frac(S)\n",
"I1 = M.ideal(23)\n",
"I2 = M.ideal([23, a - 10])\n",
"I3 = M.ideal([23, a - 3])\n",
"print(I1)\n",
"print(I2)\n",
"print(I3)\n",
"print(I1.is_integral())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We get different representations of the ideals. In fact, $S$ is PID."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(I1.factor())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(I2 + I3)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(I2.is_prime())\n",
"print(I3.is_prime())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Class group is trivial."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(M.class_group())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can compute class group of other number fields."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(K.class_group())\n",
"print(L.class_group())\n",
"print(L2.class_group())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# You can find some details here: https://math.stackexchange.com/questions/2958900/ideal-class-group-of-k-mathbbqx-x3-11x-21\n",
"L3.<d> = NumberField(x^3 + 11 * x + 21)\n",
"print(L3.class_group())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Try to find a number field with interesting class group, and prove it yourself (with a help of Sage, but without using `class_group()` directly)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Advanced number theory"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Elliptic curve"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Elliptic curves can be defined via their Weierstrass equations. `EllipticCurve([a, b, c, d, e])` corresponds to the equation $y^2 + axy + by = x^3 + cx^2 + dx + e$. By default, they are defined over $\\mathbb{Q}$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# https://www.lmfdb.org/EllipticCurve/Q/30/a/6\n",
"E = EllipticCurve([1, 0, 1, -19, 26])\n",
"print(E)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can compute conductor, torsion subgroup, integral poitns, etc."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"E.conductor()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"E.torsion_subgroup()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"E.torsion_subgroup().gens()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"E.integral_points()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We add two points of an elliptic curve."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"P = E.integral_points()[0]\n",
"Q = E.integral_points()[1]\n",
"R = E.integral_points()[2]\n",
"print(P, Q)\n",
"print(P + Q)\n",
"print(2 * P)\n",
"print(6 * Q)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For certain cases, we can even compute rank!"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"E.rank()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here's another elliptic curve, which is more interesting."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# https://www.lmfdb.org/EllipticCurve/Q/389/a/1\n",
"E2 = EllipticCurve([0, 1, 1, -2, 0])\n",
"print(E2.torsion_subgroup())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(E2.rank())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(E2.integral_points())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The following point has an infinite order (because $E_2(\\mathbb{Q})_{\\mathrm{tor}} = \\{1\\}$)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"P = E2.integral_points()[0]\n",
"for n in range(1, 8):\n",
" print(n, n * P)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Modular form"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"You can do some computations on modular forms. The following `MFR` is the ring of modular forms of level 1, generated by $E_4$ and $E_6$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"MFR = ModularFormsRing(1)\n",
"print(MFR)\n",
"print(MFR.gens())"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"E4 = MFR.gens()[0]\n",
"E6 = MFR.gens()[1]\n",
"print(E4, E6)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can multiply modular forms. In fact, we have $E_4^2 = E_8$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"print(E4 * E4)\n",
"print((E4 * E4)[10])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can even find modular forms attached to elliptic curves over $\\mathbb{Q}$ (modularity theorem!)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Modular forms correspond to elliptic curves\n",
"f_E = E.modular_form()\n",
"print(f_E.weight(), f_E.level())\n",
"print(f_E)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$E$ and $f_E$ are related via $p + 1 - \\# E(\\mathbb{F}_{p}) = a_f(p)$ for $p$ not dividing the conductor of $E$ (or equivalently, level of $f_E$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"p = 107\n",
"Ep = EllipticCurve(GF(p), [1, 0, 1, -19, 26])\n",
"print(Ep)\n",
"print(Ep.cardinality())\n",
"print(p + 1 - Ep.cardinality())\n",
"print(f_E[p])"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "SageMath 10.3",
"language": "sage",
"name": "sagemath-10.3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.11.8"
}
},
"nbformat": 4,
"nbformat_minor": 4
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment