Galois theory
来简单介绍翻译一下galois理论的一些相关内容，选择的参考书是
GTM Galois Theory 目前也正在读，期待暑假可以更新完。
Part 1 如何解方程
一切的开始：symmetry polynomial。对称多项式的定义为：\(F(x_1,x_2,\cdots ,x_k)\)，对于任意排列 \(p\)，有 \(F(x_1,\cdots,x_k)=F(x_{p_1},\cdots,x_{p_k})\)。
为何对称多项式如此重要？
原因是韦达定理，对于每一个 \(k\) ，我们可以得到 \(\prod(\lambda-x_i)\) 的 \([\lambda^k]\)。这些系数可以表示成关于 \(x_i\) 的对称多项式。而这些最基本的对称多项式可以组成所有的对称多项式。
二阶： \(a+b\)，\(ab\)。
三阶： \(a+b+c\)，\(ab+bc+ca\)，\(abc\)。
四阶： \(a+b+c+d\)，\(ab+bc+ca+ad+bd+cd\)，\(abc+abd+acd+bcd\)，\(abcd\)。
我们假设基本循环多项式 \(g_{i,j}=[\lambda^j]\prod_{k=1}^n(\lambda-x_k)\)。
考虑有这样的递推：
\[ \begin{aligned} g_{n,0}&=g_{n-1,0}+x_n\\ g_{n,j}&=g_{n-1,j}-x_ng_{n-1,j-1}\\ \end{aligned} \]
我们可以得到一个关于 \(x_n\)，与 \(g_{n,*}\) 之间的方程关系（\(x_n\) 与 \(g_{n-1,*}\) 共同生成了 \(g_{n,*}\)，所以多一个自由元后必然会出现一个方程）
这个方程也就是：
\[ \begin{aligned} F(\lambda)&=\sum_{i=0}^{n-1 } \lambda^if_i(x):=\prod (x-x_i)\\ F(x_n)&=x_n^n+\sum_{i=0}^{n-1} x_n^i f_i(x_n)=0 \end{aligned} \]
至此，我们得到了一个降阶 \(x_n^n\) 的方法。
证明考虑归纳。如果只有一个变量 \(x_1\)，那么所有多项式都可以表示成关于 \(x_1\) 的多项式。
假设 \(n-1\) 成立，那么加入 \(x_n\) 后的多项式 \(F(x_1,\cdots,x_n)=\sum_{i=0}^{n-1} x_n^iG_i(x_1,\cdots,x_{n-1})\)。
我们知道 \(G_i\) 全都是关于 \(x_1,\cdots,x_{n-1}\) 的循环多项式（permute \(1,\cdots,n-1\) 值不变）。
我们可以将 \(G_i\) 其展开成基本循环多项式的多项式：
\[ \begin{aligned} F&=\sum_{0\le i}x_n^iA_{i}(g_{n-1,1},\cdots,g_{n-1,n-1})\\ &=\sum_{i=0}^{n-1}x_n^iB_{i}(g_{n,1},\cdots,g_{n,n})\\ \end{aligned} \]
这个等号很显然，因为存在用 \(g_{n,*}\) 去表示 \(g_{n-1,*}\) 的方式（前者对应的空间更大），此处不赘述。枚举 \(i\) 的上界变成 \(n-1\) 是由于上面提过的降幂。 考虑 \(B_i\) 全部都是关于 \(g_{n,*}\) 的多项式，所以 \(B_i\) 本身 symmetry。现在我们 permute 这个 \(F\)，我们可以得到若干个等式（置换 \(x_i\) 与 \(x_n\)）：
\[ \begin{aligned} F&=\sum_{i=0}^{n-1}x_n^iB_{i}(\cdot)\\ F&=\sum_{i=0}^{n-1}x_1^iB_{i}(\cdot)\\ \vdots\\ F&=\sum_{i=0}^{n-1}x_{n-1}^iB_{i}(\cdot)\\ \end{aligned} \]
我们记多项式 \(G(\lambda)\) 为：
\[ \begin{aligned} G(\lambda)=\sum_{i=0}^{n-1}\lambda^iB_i(g_{n,1},\cdots,g_{n,n})-F(x_1,\cdots,x_n) \end{aligned} \]
由上式，我们立即得到 \(n\) 个根：\(\forall i\in[1,n] G(x_i)=0\)。这显然是不合理的，一个非 \(0\) 的 \(n-1\) 次多项式不应有 \(n\) 个根，故这个多项式 \(G\) 必然是 \(0\)。
也就是 \(F=B_0(g_{n,1},\cdots,g_{n,n})\) 得证。
Vandermonde 的野望
以下做法由法国数学家 Vandermonde 提出，Vandermonde 曾和当时的一众数学家致力于求解多项式方程的根，并在其中做出了并非平凡的结果。不幸的，他并未将其成果进行整理与总结。如今，在提到解三次方程时，大家只会记得与他同时代的一位德国的数学家 Lagrange，而 Vandermonde 这个名字似乎也只会存在于在一个或几个与其并未有过大关系的公式或定理中。
从二次出发，我们思考该如何表示根 \(x\)：
\[ \begin{aligned} x=\frac{(x+y)+(x-y)}{2}=\frac{(x+y)+\sqrt{(x-y)^2}}{2}\\ \end{aligned} \]
我们可以发现 \((x-y)^2\) 是 symmetry
的，我们 swap \(x,y\)
后，式子的值并不会改变。它可以被表示成 \((x-y)^2=(x+y)^2-4xy\)。由此我们可以得到最为经典的求根公式。（\(\pm\) 是由于开根的多值性）
推广到 \(3\) 次方程时，我们首先考虑三次单位根 \(\omega\)：
\[ x=\frac{1}{3}\left((x+y+z)+\sqrt[3]{(x+\omega y+\omega^2z)^3}+\sqrt[3]{(x+\omega z+\omega^2y)^3}\right) \]
当然，这里的 \(u:=(x+\omega
y+\omega^2z)^3\) 与 \(v:=(x+\omega
z+\omega^2y)^3\) 并非我们所期待的 symmetry
多项式。我们观察可以得到，任何的 二元 swap 会导致 \(u\), \(v\)
值的互换。（\(v=(y+\omega
x+\omega^2z)^3\)）。对于 \(S_3\)，其可以有二元交换生成。 所以我们发现
\(uv\) 与 \(u+v\) 都是关于 \(x,y,z\) symmetry 的。
这样我们可以用二次方程的求根公式求出来对应的两个根 \(u\) 与 \(v\)。一个值得注意的地方是：我们究竟应该选取哪一个三次根？我们现在由九个不同的答案分别表示着：
\[ \begin{aligned} x=\frac{1}{3}\left((x+y+z)+\omega^i(x+\omega y+\omega^2z)+\omega^j(x+\omega z+\omega^2 y)\right) \end{aligned} \]
而其中只应有 \(3\) 个真正的根。18世纪的数学家，至少 Vandermonde 并未给出一个较好的公式，只能去对着 \(9\) 个根一一验证。
Lagrange Resolvents
上述的三次方程求根法最早是由 Vandermonde 在 1770年于巴黎数学会发表。戏剧性的是，几乎于此同时，早 Vandermonde 几个月前，来自意大利都灵的数学家 Lagrange 于普鲁士数学会上发表了著名的 Lagrange Resolvents 以解决三次方程问题。
Vandermonde 的做法直到 1774 年才被巴黎数学会公布。
我们来正式介绍著名的 Lagrange Resolvent，即拉格朗日预解式。
假设 \(t=x+\omega y+\omega^2 z\)，其中 \(x,y,z\) 是三个根。我们假设 \(3!=6\) 中排列方案对应的 \(t\) 分别为 \(t_1,t_2,\cdots,t_6\)。
考虑方程：\((x-t_1)\cdots (x-t_6)=0\) 这个是一个虚假的 \(6\) 次方程，我们可以通过：
\((x-t_1)(x-\omega t_1)(x-\omega^2 t_1)=(x^3-t_1^3)\) 来将原方程降为：
\[ \begin{aligned} (x^3-t_1^3)(x^3-t_2^3)&=0\\ (z-u)(z-v)=0\implies& z^2-(u+v)z+uv=0 \end{aligned} \]
于 Vandermonde 的想法相同，此处的 \(u+v\) 与 \(uv\) 依然是关于 \(x,y,z\) 的循环多项式，我们可以直接解出对应的 \(x^3\)。如果我们得到了一个 \(x+\omega y+\omega^2 z\) 我们该如何找到与其对应的 \(x+\omega z+\omega^2 y\) 呢？
不难发现 \((x+\omega y+\omega^2 z)\times (x+\omega z+\omega^2 y)\) 也是关于 \(x,y,z\) 的循环多项式。所以可以直接从 \(x+\omega y+\omega^2 z\) 得到对应的 \(x+\omega^2 y+\omega z\)。
对于四次方程，我们用一个更为简单的方法去做，选择 \(t=x-y+z-w\)，可以发现 \(24\) 种不同的 permute 最终会形成 \(6\) 种不同的值：
\(t_1=x-y+z-w\), \(-t_1\), \(t_2=x-y-z+w\), \(-t_2\), \(t_3=x+y-z-w\), \(-t_3\)。
对应的拉格朗日预解式形如： \[ \begin{aligned} (\lambda-t_1)(\lambda+t_1)(\lambda-t_2)(\lambda+t_2)(\lambda-t_3)(\lambda+t_3)=(\lambda^2-t_1^2)(\lambda^2-t_2^2)(\lambda^2-t_3^2) \end{aligned} \]
可以发现，若 \(p(\cdots)\) 为对称多项式，\(p(t_1,t_2,t_3)\) 也应为 \(x,y,z,w\) 的对称多项式。（为什么呢？我们可以发现，不管如何 permute 根 \(x,y,z,w\)， \(t_1\) 和 \(-t_1\) 对应的始终为相反数，也就是 permute 只会使 \(|t_1|\), \(|t_2|\), \(|t_3|\) 他们发生 permute）我们可以任意选择 \(t_1\), \(t_2\) ，然后根据 \(t_1t_2t_3\) symmetry 来算出 \(t_3\)。
相信大家再看到此处，已经能回忆起 使用 Galois 理论解释求根，与对 \(S_4\) 进行分解的内容了。
单位根
单位根是一类特殊的，形如 \(x^n=1\) 的方程的根。一些单位根有着较为简单的形式，与求解方法，例如五次单位根。
假设 \(t=x+\frac{1}{x}\)：
\[ \begin{aligned} x^4+x^3+x^2+x+1=0&\implies x^2+x+1+\frac{1}{x}+\frac{1}{x^2}=0\\ &t^2-2+t+1=0 \end{aligned} \]
解两次二次方程即可得到答案。
单位根的可解性
如何求解 \(p\) 次单位根？我们假设已经求得了 \(p-1\) 次单位根 \(\beta\), \(\beta^{p-1}=1\)。 假设 \(\bmod p\) 原根为 \(g\)，我们写出预解式：
\[ \begin{aligned} t(\alpha,\beta)&=\sum_{i=0}^{p-2}\alpha^{g^i}\beta^i\\ t(\alpha^g,\beta)&=\sum_{i=0}^{p-2}\left(\alpha^{g}\right)^{g^i} \beta^i=\sum_{i=0}^{p-2}\alpha^{g^{i+1}}\beta^i=\beta^{-1}t(\alpha,\beta) \end{aligned} \]
可以发现 \(t^{p-1}(\alpha,\beta)=t^{p-1}(\alpha,\beta)\)，可以证明，\(t^{p-1}\) 是只关于 \(\beta\) 的有理多项式。
此处我们只给出 lemma 形式，并不进行证明。（留在后面证明）
假设 \(p\) 为质数，\(\alpha\) 为 \(p\) 次单位根， \(\beta\) 为 \(p-1\) 次单位根，\(F_i(\beta)\) 为关于 \(\beta\) 的有理多项式。
假设 \(\sum_{i=1}^{p-1} \alpha^i F_i(\beta)=0\) 推出 \(F_i(\beta)=0\)。
假设 \(t^{p-1}(\alpha,\beta)=F_0(\beta)+\sum_{i=1}^{p-1}F_i(\beta)\alpha^i\)，我们列出方程：
\[ \begin{aligned} t^{p-1}(\alpha^g,\beta)=&F_0(\beta)+\sum_{i=1}^{p-1}F_i(\beta)\alpha^{gi}=F_0(\beta)+\sum_{i=1}^{p-1}F_i(\beta)\alpha^{i}\\ \implies & \sum_{i=1}^{p-1} (F_{gi}(\beta)-F_i(\beta))\alpha^i=0\\ t^{p-1}(\alpha,\beta)&=F_0(\beta)+(\alpha+\alpha^2+\cdots+\alpha^{p-1}) F_1(\beta)=F_0(\beta)-F_1(\beta) \end{aligned} \]
第二行的原因是 \(\times g\) 在 \([1,p-1]\) 上是一个置换。
第二行到第三行的推导使用了 lemma，这并不是一个十分显然的 lemma。（）
由此得证， \(t^{p-1}\) 的确是仅仅关于 \(\beta\) 的有理多项式。
回顾 Galois 理论
尝试把我们上面干的事情换个方式描述一遍，我们现在有这样一个自同构 \(S: \mathbb{Q}[\alpha]\to \mathbb{Q}[\alpha]\) 我们将生成元映射到 \(S(\alpha)=\alpha^g\)。（\(\alpha\) 为 \(p\) 次单位根）
那么假设一元素 \(x\in F:=\mathbb{Q}[\alpha]\)，那么 \(S(x)=x\) 当且仅当 \(x\in \mathbb{Q}\)。证明仿照上面的证明。
换句话说，在自同构 \(S\) 下的不动点，或者说成 (fixed field) 为 \(\mathbb{Q}\)。 同时我们考虑 \(S^{p-1}=I\) 单位映射，在单位映射下的 fixed field 为 \(\mathbb{Q}[\alpha]\) 本身。
此处的证明 要容易于 lemma，我们只需要证明：
\[ \begin{aligned} \sum_{i=1}^{p-1} f_i\alpha^i=0\implies \forall i,f_i=f_1 \end{aligned} \]
我们可以发现， \(\alpha\) 是多项式 \(f_1+f_2\alpha+f_3\alpha^2+\cdots+f_{p-1}\alpha^{p-2}\)，这与质数次单位根的最小多项式是 \(1+x+\cdots+x^{p-1}\) 矛盾。
我们使用 Eisenstein 判别法，判断 \(F(x+1)\) 在 \(\bmod p\) 的情况下：
\[ \begin{aligned} \frac{(x+1)^p-1}{x}=\frac{1}{x}\sum_{i=0}^{p}\binom{p}{i}x^i=\sum_{i=1}^{p}\binom{p}{i}x^{i-1} \end{aligned} \] 可以发现 \([x^0]\) 是 \(p\)，同时每一项都是 \(p\) 的倍数。这满足了 Eisenstein 判别法的条件，也就是 \((x^p-1)/(x-1)\) 既约。
假设整多项式 \(F\in\mathbb{Z}[x]\)，若 \([x^n]F\not=0\) 其中 \([x^n]\) 的含义是最高位。且 \(\forall i<n, [x^i]F\bmod p=0\)，且 \([x^0]F\bmod p\not=0\)。则 \(F\) 是既约的 (irreducible)。
反证法，假设 \(F=GH\)，那么 \(F\bmod p = G\bmod p\times H\bmod p\)。
\(F\bmod p=x^n\) \(\implies\) \(G=x^a, H=x^{n-a}\)，这与 \([x^0]F \bmod p^2\not = 0\) 矛盾。
欧拉证明了一个更为一般的情况，我们假设 \(D=p-1\), \(D=qd\) 其中 \(q\) 为某质数。假设 \(K_d\) 表示的为 \(S^d\) 这个自同构下的 fixed field，那么有结论： 任意 \(t\in K_D\) 可以被表示成关于 \(K_d\) 中的元素和 \(\beta\) （\(q\) 次单位根） 的代数表示（四则运算+开根）。
而这个命题的证明的关键，就是：Lagrange resolvent。
假设某一个在 \(K_d\) 中的元素为 \(\gamma\), 设： \[ \begin{aligned} t(\gamma,\beta)&=\gamma+\beta S^d\gamma+\beta^2 S^{2d}\gamma+\cdots+\beta^{q-1}S^{n-d}\gamma\\ S^d(t(\gamma,\beta))&=S^d \gamma+\beta S^{2d}\gamma +\beta^2 S^{3d}\gamma+\cdots+\beta^{q-1}\gamma=\beta^{-1}t(\gamma,\beta) \end{aligned} \]
考虑 \(t^{q}\)：
\[ \begin{aligned} S^d(t^{q})=S^d(t)^q=t^{q}\beta^{-q}=t^q \end{aligned} \]
可以发现：\(t^q\in K_d\)。
我们可以类似的发现：\(t(\gamma,\beta^i)t^{q-i}(\gamma,\beta)\) 也是 \(K_d\) 的元素。此处的证明使用“同态”的定义非常的显然。（对 \(t\) 运用一个 \(S^d\) 会产生一个对应的 \(\beta^{-i}\)）
可以发现：\(\sum_{i=0}^{q-1}t(\gamma,\beta^i)\) 本身就是在进行所谓“单位根反演”。于是，我们得到了 \(\gamma\) 的关于 \(t(\gamma,\beta^k)\) 的表示，而 \(t(\gamma,\beta^k)\) 可以表示成关于 \(K_d\) 与 \(\beta\) 的代数表示，此处 \(\beta\) 的任务是提供开 \(q\) 次根号后的结果。
我们可以直接运用此结果直接得到 Gauss 的成果。考察 \(p=17\) 的单位根，我们可以发现 \(D=p-1=16=2\times 2\times 2\times 2\) 。也就是，从 \(K_1\subset K_2\subset K_4\subset K_8\subset K_16\) 的过程中，每次扩域都只需要“二次扩域”，也就是在最终的表达式中，最多只会出现 \(\sqrt{\cdot}\) 这也是可以尺规作图的根本性原因。