I’m trying to brush up on my Algebra before taking an Algebra class (NT) this semester. Basically, I should go reread Artin, or find my notes. Or I can just wikipedia things as they come up. Anyways, here’s a place to write stuff down.
- group
- ex: \(S_n, A_n, D_n\)
- more exs: \(SL_n, GL_n, U_n\)
- abelian group: all elements commute
- normal subgroup: subgroup invariant under conjugation
- conjugacy class: a set of elements that are all conjugate to each other (conjugacy is an equivalence relation)
- coset: if \(g\in G\) and \(H\) is a subgroup of \(G\) then \(gH\) is called a coset.
Theorem. Lagrange’s theorem: Let \(H\) be a subgroup of \(G\). Then \(|H| \mid |G|\).
Proof. We claim that the relation “\(x\sim y\) if \(xH = yH\)” is an equivalence relation. I.e., left cosets form a partition of \(G\).
This is true because if \(xh_1 = yh_2\) then \(x=y h_2h_1^{-1}\).
- ring
- ex: \(\mathbb{Z}[x]\)
- we spend quite a bit of time talking about when polynomials are irreducible iirc. You can do things like Einstein criterion I guess.
- module: like a vector space but scalars are from a ring rather than a field. These can be wacky.
- ex: \(\mathbb{Z}[x]\)
- ideal
\(I\subseteq R\) satisfying:
If \(s_1,s_2\in I, r_1,r_2\in R\) then \(s_1r_1+s_2r_2\in I\).
- principal ideal: generated by a single element
- maximal ideal: no other proper ideals contain it
- field
- algebraicly closed field: all non-constant polynomials have roots.
- field extensions where important
- you can get an extension, e.g., by adjoining an element
- in general an extension is just a superset field
- the degree of an extension \([K: F]\) is the dimension of \(K\) as an \(F\) vector space.
- multiplicative property of field extensions
- splitting field: a finite field extension in which some given polynomial factors
- here’s a cool fact that I had forgotten:
Proposition. Let \(F\subset K\) be fields and let \(f,g\in F[x]\). Suppose that \(\exists h\in L[x]\) such that \(fh = g\). Then in fact \(\exists h\in F[x]\) such that \(fh=g\). Said another way, \(f\mid g\) is “unambiguous”.
Proposition. Splitting theorem:
An irreeducible polynomial over \(F\) with one root in \(K\) splits completely in \(K\).
- vector space
- ex: \(\mathbb{R}\) is a \(\mathbb{Q}\) vector space
- representation of a group
- \(\rho: G\to GL(V)\)
- character of a representation: trace
- reducible: can write as direct sum
- 1D chars
- regular rep
- Shur’s lemma
- irreducible characters are orthonormal
- number of irreps equals number of conjugacy classes
- Integral Domain: Commutative ring with no zero divisors
- ex \(\mathbb{Z}[x]\)
- non-example: \(\mathbb{Z}[x,y]/(xy)\) (not an integral domain because \(x\cdot y = 0\))
- Euclidean Domain
- an integral domain endowed with a norm function that allows you to divide via the euclidean algorithm
- ex: \(\mathbb{Z}[i]\) with norm the complex norm or \(\mathbb{Z}[x]\) with norm being the degreee of the polynomial
- PID
- integral domain where every ideal is principal (generated by a single element)
- UFD
- integral domain where you can uniquely factor (modulo units)
- Prime Ideal
- \(ab\in P \implies a\in P \lor b\in P\)
- Galois Group
- Let \(K,K'\) be field extensions of \(F\). An \(F\)-isomorphism \(\phi: K\to K'\) is an isomorphism that fixes \(F\) (is the identity map when restricted to \(F\) ).
- If \(K\supseteq F\), then the Galois group \(G(K/F)\) is the group of \(F\)-automorphisms of \(K\).
- some deep theorem about a bijection between subgroups of the galois group and intermediate field extensions.
- irreducible polynomial
- Gauss’ lemma: a primitive polynomial (gcd of coefficients is a unit) is irreducible over the integers iff irreducible over the rationals.
- another thing: if a polynomial is irreducible over \(\mathbb{F}_p[X]\) then it is also irreducible over \(\mathbb{Z}[X]\)
- minimal polynomial:
- given \(\alpha\in K\supset F\) the minimal polynomial of \(\alpha\) over \(F\) is the (unique, irreducible) polynomial of minimum degree in \(F[x]\) that has \(\alpha\) as a root.
Theorem. Let \(\alpha\in K\) be algebraic over \(F\). Then we say that a monic polynomial \(f\in F[x]\) with \(\alpha\) as a root is the (unique) minimal polynomial for \(\alpha\) over \(F\) if the following equivalent conditions hold:
- \(f\) is the poly of minimum degree in \(F[x]\) with \(\alpha\) as a root.
- \(f\) is an irreducible polynomial in \(F[x]\).
- \((f)\) is a maximal ideal in \(F[x]\).
- For all \(g\in F[x]\) with \(g(\alpha) = 0\) we have \(f\mid g\).
Theorem. Let \(f\) be the minimal poly for \(\alpha\in K\supset F\) over \(F\). Then \[F[x]/(f) = F[\alpha] = F(\alpha).\]
Proof. We have the natural evaluation isomorphism \(f(x)\mapsto f(\alpha)\).
\((f)\) is irreducible means that \((f)\) is a maximal ideal which means that \(F[x]/(f)\) is a field.
\(F(\alpha)\) is just defined to be the smallest extension of \(F\) containing \(\alpha\), so we are done.
Theorem. Some important facts:
- If \(F\) is a field then \(F[x]\) is a euclidean domain.
- If \(F\) is a field then \(F[x]\) is a PID.
- \(f\) is an irreducible poly iff \((f)\) is a maximal ideal.
- \(I\) is a maximal ideal iff \(F[x]/I\) is a field.
Proof.
We define the norm to be the degree of a polynomial. You can do Euclidean algorithm because we are working in a field.
Suppose we have an ideal \(I\) in \(F[x]\). Let \(f\in I\) be a polynomial of minimum non-zero degree in \(I\). We claim that \((f) = I\). If there is any \(g\in I\setminus (f)\) then \(g\mod f\) would have degree smaller than that of \(f\) (this is well defined because \(F[x]\) is a euclidean domain), a contradiction.
Well it’s quite clear that if \(f\) factors then \((f)\) is not maximal: \((f) = (gh)\subset (g)\). And the PID-ness of \(F[x]\) means that if \((f)\) were not maximal there would be a \((g)\) such that \((f)\subset (g) \subsetneq F[x].\) But then \(g\mid f\) contradicting the fact that \(f\) is irreducible.
Suppose \(I\) is a maximal ideal of ring \(R\). Let \(f\in R\). claim: \(I+Rf\) is an ideal of \(R\). pf: \[R(I+Rf) = I+Rf, (I+Rf)+(I+Rf)= I+Rf.\]
Also, \[I\subseteq I+Rf\subseteq R.\] If \(f\in I\) then we don’t need to produce an inverse for \(f\) in \(R/I\). If \(f\notin I\) then \(I\subsetneq I+Rf\). But \(I\) is maximal so we then get \(I+Rf = R\). In particular this means that there is \(g\in R\) such that \[fg\in I+1.\] So we can set \(g\) to be the inverse of \(f\) in \(R/I\) and its clear that \(R/I\) is a ring, so having mult inverses completes the pf that it’s a field.
- separable polynomial
- roots are distinct in an algebraic closure
- you can tell if a minimal poly has repeated roots based on whether its formal derivative is the zero polynomial. Or actually maybe the relevant detail is whether the gcd of the derivative and the original function is one or not.
- separable extension:
- for every \(\alpha\in L\) which is algebraic over \(K\) the minimal poly of \(\alpha\) over \(K\) is separable.
- splitting field of a poly: smallest field extension in which the poly factors
- the splitting field is unique up to iso
- constructing the splitting field: adjoin roots to split up non-linear factors
- exact sequence:
- image of one morphism is the kernel of the next.
- \(im(f_i) = ker(f_{i+1})\)
- ex: \(0\to X \to Y \to 0\) means that \(X,Y\) is an isomorphism
Definition. algebraic closure:
I think the following is a reasonable way to think about the algebraic closure of \(\mathbb{F}_p\):
\[\Omega = \bigcup_{k=1}^{\infty} \mathbb{F}_{p^{k}}.\]
Basically, if you have \(x,y\in \Omega\), then you can find \(k\) such that \(x,y\in \mathbb{F}_{p^{k}}\) because \(\mathbb{F}_{p^{k}}\subset \mathbb{F}_{p^{kc}}\) for integer \(c\) where this is maybe slight abuse of notation because finite fields are only defined up to isomorphism but you get the idea.
Anyways, this shows that \(x+y,x\cdot y, x^{-1},-x\) are well defined objects in \(\Omega\).
Why does \(\Omega\) have solutions to all the polynomials over Fp?
oh, hmm. still not clear to me why this is algebraicly closed.
Maybe a better way to think about the existence of \(\overline{\mathbb{F}_p}\) is that there are a countable infinity of finite polynomials and then just repeatedly adjoin roots of them.
NT 1.1 existence
- An Algebraicly Closed Field of characteristic \(p\):
- the existence of this is somehow tied to axiom of choice / zorn’s lemma.
- vaguely speaking the idea is to make a poset with “K is a field extension of F being the order relation” and then finding an upper bound
Throughout the post we take \(p\) prime and \(q\) a power of \(p\).
Note: \(x\mapsto x^{p}\) is an automorphism of \(\mathbb{F}_q\), because if \(x^{p}=y^{p}\) then \((x-y)^{p} = 0\) and hence \(x=y\).
- Field have prime characteristic (or else it violates the fact that fields have no zero-divisors).
If \(\mathbb{F}_q\) has characteristic \(p\) then the size of \(\mathbb{F}_q\) is a power of \(p\), becuase \(\mathbb{F}_q\) is a vector space over \(\mathbb{F}_p\). So, we could just repeatedly project off subspaces of \(\mathbb{F}_q\).
- Let \(\Omega\) be algebraicly closed. Then \(x\mapsto x^{q}\) is an automorphism of \(\Omega\). Thus, the set of elements fixed by this automorphism, i.e., the roots of \(x^{q}-x\) form a field (you can check that inverses, sums, etc must lie in the set).
Observe that the derivative of \(x^{q}-x\) is nowhere zero. This means that it has no repeated roots. Thus it has \(q\) distinct roots.
For the uniqueness part, if \(K\) is a subfield of \(\Omega\) with \(q\) elements, then for any \(x\in K^{*}\) we have \(x^{q-1}=1\), by Lagrange’s theorem: the multiplicative group \(K^*\) is a group with \(q-1\) elements so the order of each element must divide into \(q-1\). Hence \(x^{q}=x\) for all \(x\in K\). But then \(K\subseteq \mathbb{F}_q\). They have the same cardinality so are actually equal.
Theorem. \(\mathbb{F}_q\) is unique.
Proof. Take \(K/\mathbb{F}_p\) of order \(q\). So we can embed \(K\) in \(\Omega\). But we said already there is a unique subfield of \(\Omega\) with \(q\) elements.
Proof. Take \(K_1,K_2\) both fields of order \(q\). Let \(\alpha\) be a generator for \(K_1^{*}\), and let \(f\) be the minimal polynomial for \(\alpha\) over \(\mathbb{F}_p\).
Then \(f\mid x^{q}-x\).
Thus, \(f\) must split in \(K_2\). Thus, there is \(\beta \in K_2\) which is a root of \(f\).
Thus, \[K_1=\mathbb{F}_p(\alpha) = \mathbb{F}_p[x]/(f) = \mathbb{F}_p(\beta) = K_2.\]
NT 1.2 cyclic
Theorem. \(\mathbb{F}_q^{*}\) is cyclic.
Proof. The number of \(x\) with \(x^{d}=1\) is at most \(d\) because we are working in a field. Suppose that \(x^{d}=1\). Then \((x)\) is an order \(d\) subgroup of the group, and consists of \(d\) (i.e., all) solutions to the equation \(x^{d}=1\). Suppose that \(y\) is an element of order \(d\). Then we must have \(y = x^{i}\) for some \(i\in \mathbb{Z}_d^{*}\). Hence, there are at most \(\phi(d)\) elements of order \(d\) in \(\mathbb{F}_q^{*}\).
Then of course \[|\mathbb{F}_q^{*}| \le \sum_{d\mid q-1} \phi(d) = q-1.\] But then we must have equality in all the cases. In particular, there are \(\phi(q-1)\ge 1\) elements of order \(q-1\).
Recall that the lemmma \(\sum_{d\mid n}\phi(d) = n\) is true because we can partition \([n]\) based on the gcd of numbers with \(n\) into classes of size \(\phi(n/d)\).
NT 2.1 sums
Lemma. For any positive integer \(c\) we have \[\sum_{x\in K} x^{(q-1)c} = -1.\]
For any positive integer \(u\notin (q-1)\mathbb{Z}\) we have \[\sum_{x\in K} x^{u} = 0.\] In fact \(\sum_{x\in K} x^{0} = 0\) is also true, using the convention that \(x^{0}=1\) for all \(x\).
Proof.
The first statement is clear: all the values that we are summing are \(1\) and there are \(q-1\) many values.
For the second statement we use the fact that there must be a generator \(g\) satisfying \(g^{u}\neq 1\). Hence,
\[\sum_{x\in K} x^{u} = \sum_{x\in K} (gx)^{u} = g^{u}\sum_{x\in K} x^{u}.\] But this means \(\sum_{x\in K}x^{u} = 0.\)
Theorem. Suppose you have a set of polynomials \(f_\alpha \in [X_1,\ldots, X_n]\) with \(\sum_\alpha \deg f_\alpha < n\), and let \(V\) be the set of common zeros of your polynomials. Then \(|V|\in p\mathbb{Z}.\)
Proof.
The function \(P=\prod_\alpha (1-f_\alpha^{q-1})\) indicates \(V\) (i.e., is 1 on \(V\) and zero elsewhere).
Observe that \(\deg P < n(q-1)\). Hence \(P\) is a linear combination of monomials, where in each monomial there is some variable \(X_i\) whose degree is smaller than \(q-1\).
Hence, \(\sum_{X\in K^{n}} X_i^{u} = 0\) by the earlier lemma. But this actually means \(\sum_{X\in K^{n}} P(X) = 0\) as well.
Now observe that \(\sum_{X\in K^{n}}P(X)\) is exactly \(|V| \mod p\). So we have the desired result.
Corollary. If \(\sum_\alpha \deg f_\alpha < n\) and the \(f_\alpha\)’s don’t have constant terms then the \(f_\alpha\)’s have a nontrivial common zero.
NT 3.1 QR
Theorem. If \(p=2\) then all elements of \(\mathbb{F}_q\) are squares.
If \(p\neq 2\) then the \(QR_q\) forms a subgroup of \(\mathbb{F}_q^{*}\) of index \(2\). Specifically, \(QR_q = \ker (x\mapsto x^{(q-1)/2})\)
Proof.
For the case \(p=2\) recall that the Frobenius map \(x\mapsto x^2\) is an automorphism. Thus, all elements of \(\mathbb{F}_q\) are squares.
For the case \(p\neq 2\) take any \(x \in K\) and let \(y\) be the solution to the equation \(y^2=x\) (\(y\) lives in the algebraic closure of \(\mathbb{F}_q\) not necessarily \(\mathbb{F}_q\) itself).
Then we have that \(y^{q-1} = x^{(q-1)/2}\in \pm 1\). If \(y^{q-1} = -1\) then clearly that is bad, \(x\) is not a QR. If \(y^{q-1}=1\) then clearly that is good, \(y\in K\) because \(K\) is literally defined as the roots of \(X^{q}-X\). Thus, \(x\) would indeed by a QR in this case.
Why are half the numbers QRs? We can invoke the cyclicity of \(\mathbb{F}_q^{*}\).
NT 3.2 Legendre
Theorem. Fix odd prime \(p\).
\(-1\) is a QR iff \(p\equiv 1 \mod 4\). \(2\) is a QR iff \(p\equiv \pm 1 \mod 8\).
Proof. Only analyze the case of \(2\).
Let \(\alpha\) be a primitive 8th root of unity (i.e., its an 8th root of unity but not a \(4\)th root of unity). Then \(y=\alpha+\alpha^{-1}\) is a square root of \(2\), where \(y\) is an element of the algebraic closure of \(\mathbb{F}_p\). Then, \(y^{p} = \alpha^{p}+\alpha^{-p}\).
If \(p\equiv \pm 1 \mod 8\) then we find \(y^{p} = y\) and \(y\in \mathbb{F}_q\). Else we find \(y\notin \mathbb{F}_q\).
NT 3.3 Quadratic reciprocity
Let \(m(x)\) be \(0\) if \(x\equiv 1\mod 4\) and \(1\) if \(x\equiv 3\mod 4\).
Theorem. Let \(p,r\) be odd primes. Then \[\genfrac{(}{)}{}{}{r}{p} = \genfrac{(}{)}{}{}{p}{r} \cdot (-1)^{m(r)m(p)}.\]
For primitive \(r\)-th root of unity \(w\in \overline{\mathbb{F}_p}\) define the “Gauss Sum” \[y = \sum_{x\in \mathbb{F}_r} \genfrac{(}{)}{}{}{x}{r} w^{x}.\]
Example. Ok to see why the Gauss sum is a good candidate square-root we really just need to try some examples.
\(p=3\). Let \(w\) be a primite third root of unity. Then \(y = w-w^2\), and \[y^2 = w^2-w^3-w^3+w^{4} = w+w^2+w^3-3w^3 = -3w^{3}.\]
How about for \(p=5\). Let \(w\) be a fifth root of unity. \(y = w+w^{4}-w^2-w^3\). Then \[y^2 = -w-w^2-w^{3}-w^{4}-w^{5}+5w^{5} = 5w^{5}.\]
So. Somehow this is just good.
Lemma. \[y^2=r\cdot (-1)^{m(r)}.\]
Proof. \[y^2 = \sum_{x,z}\genfrac{(}{)}{}{}{xz}{r} w^{x+z} = \sum_{u} w^{u} \sum_{t} \genfrac{(}{)}{}{}{t(u-t)}{r}.\]
Let \[C_u = \sum_{t\in \mathbb{F}_r^*} \genfrac{(}{)}{}{}{t^2}{r}\genfrac{(}{)}{}{}{1-ut^{-1}}{r},\] where of course \[\genfrac{(}{)}{}{}{t^2}{r}=1\] for all \(t\in \mathbb{F}_r^*\). Then we have \[y^2 = (-1)^{m(r)}\sum_{u\in\mathbb{F}_r} w^{u} C_u.\]
When \(u=0\) we have \(C_0 = r-1\). When \(u\neq 0\) we have \(C_u = -1\) because the sum is basically just the difference between number of QRs and non-QRs, except minus \(1\). Then we use the lemma from earlier to understand \(\sum_{u}w^u\), and conclude.
Lemma. \[y^{p-1} = \genfrac{(}{)}{}{}{p}{r}.\]
Proof. We have \[y^{p} = \sum_{x\in \mathbb{F}_r} \genfrac{(}{)}{}{}{x}{p} w^{xp} = \sum_{z\in \mathbb{F}_r} \genfrac{(}{)}{}{}{zp^{-1}}{r} w^{z} = \genfrac{(}{)}{}{}{p^{-1}}{r} y = \genfrac{(}{)}{}{}{p}{r}y.\]
Proof. By the first lemma \((-1)^{m(r)} r\) is a square modulo \(p\) iff \(y\in \mathbb{F}_p\), which is true iff \(y^{p-1}=1\). By the second lemma we know that \(y^{p-1} = \genfrac{(}{)}{}{}{p}{r}\)
This gives \[\genfrac{(}{)}{}{}{(-1)^{m(r)}r}{p} = \genfrac{(}{)}{}{}{p}{r}.\] Finally, we have \[\genfrac{(}{)}{}{}{r}{p} (-1)^{m(r)m(p)} = \genfrac{(}{)}{}{}{p}{r}.\]
Remark. We can compute Legendre symbols in euclid algo esque manner.
my lecture notes!
@importpdf: images/lec1