代数数是否可以相互表示的问题

mathe

整系数方程的根都是代数数.
比如对于三次方程$f(x)=x^3+x+1=0$的一个根$\alpha$
那么先行组合$a\alpha^2+b\alpha+c$,其中a,b,c为有理数构成了有理数域Q的一个扩充域Q[f].
如果我们考虑变量$\beta=\alpha^2$,那么
$\beta=\alpha^2$
$\beta^2=-\alpha^2-\alpha$
$\beta^3=\alpha^2+2\alpha+1$
所以我们得到$\beta$满足方程$g(x)=x^3+2x^2+x-1=0$
于是我们可以知道域Q[f]和域Q[g]是完全相等的.
或者换句话说,多项式g的解都在Q[f]上,或者说g可以在Q[f]上完全因子分解.

而我的问题就是给定两个不可约整系数多项式f,g,如果通过计算机判断g是否在Q[f]上可约
特别的,当f,g都是3次或4次多项式时,是否有比较简单的计算方法

mathabc

看来mathe是学数论出身的（所述内容属代数数论）。

sunwukong

是 $g(x)=x^3+2x^2+x-1=0$ 吧?

设              $f(x)=\sum_{i=0}^nf_ix^i$,   $g(x)=\sum_{i=0}^mg_ix^i$, $beta$ 是 $g(x)=0$ 的一个根。
如果 `g(x)` 在 `Q[f]`上 可约，则\[\beta=\sum_{i=0}^{n-1}{a_ix^i}\]这里 $a_i$ 是待定系数。

根据这个设定可以算出：\[\begin{align*}\beta^2&=\sum a_{2,i}x^i\\\beta^3&=\sum a_{3,i}x^i\\&\cdots\\\beta^m&=\sum a_{m,i}x^i\end{align*}(i=0,1,\cdots,n-1)\]其中$a_{j,i}$ 是 `a_0,a_1,\cdots,a_n` 的一个表达式\[a_{j,i}=\sum_{i=0}^n{k_{j,i}a_i}\]这里$k_{j,i}$ 是 $f_0$、$f_1$、…$f_n$ 的一个表达式

于是\[\begin{align*}g(\beta)&=\sum_{i=0}^mg_i\beta^i=(g_0,g_1,...,g_m)\cdot(1,\beta^1,...,\beta^m)\\&=(g_0,g_1,...,g_m)\begin{pmatrix}a_0&a_1&...&a_{n-1}\\a_{2,0}&a_{2,1}&...&a_{2,n-1}\\...&...&...&...\\a_{m,0}&a_{m,1}&...&a_{m,n-1}\end{pmatrix}\begin{pmatrix}1\\x^1\\...\\x^{n-1}\end{pmatrix}\end{align*}\]由 g 在 Q[f]上 可约，则\[(g_0,g_1,...,g_m)\begin{pmatrix}a_0&a_1&...&a_{n-1}\\a_{2,0}&a_{2,1}&...&a_{2,n-1}\\...&...&...&...\\a_{m,0}&a_{m,1}&...&a_{m,n-1}\end{pmatrix}=(f_0,f_1,...,f_n)\]有解

mathe

$a_{j,i}$不是$a_i$的线性组合,而是高次多项式.
所以最终的表达式会变成一个高次方程.
也就是你将判断g是否可约的问题转化为另外一个次数更高的多变量方程的求解问题

zgg___

我感觉mathe不是学数论出身的，就好像我也不是一样，赫赫。
问题的确是代数数论范围的，大家捉摸捉摸，真的是很好玩的问题。
这个问题在Henri Cohen的A Course in Computational Algebraic Number Theory（GTM）中有详细的论述，在其中叫做子域问题(Subfield Problem）。
这本书是我最喜欢的书之一，它的影印本被“牛人”翻译为《计算代数数值论教程》，阿门.
一次同事问我在看什么说，答曰看数值计算的问题，所以说“牛人”不光传播了知识，还帮助我避免提到“数论”这个尴尬的词。感谢呀！
好了，言归正传。

先重述一遍mathe的问题，呵呵。
设K=Q(`a`),L=Q(`b`)都是3次域，`a`和`b`分别是`f(x)=x^3+x+1`和`g(x)=x^3+2x^2+x-1`的根，`f`和`g`的系数都是整数。
问题是：K是否同构于L的某个子域？
更直白一点，`a`的某个共轭是否在L中？
更更直白一点，`a`本身能不能用1和`b`通过加减乘除凑出来？

下面介绍一种方法，可以将多项式g(x)在K中完全因式分解，从而解决上面的问题。
这种方法基于下面的4个事实。
【事实1】对于某个多项式`\color{Black}{g(x)}`，设`g`的系数在K中。定义操作`s`，叫做K在C中的嵌入，就是对于在K中的某个数，取其在C中的共轭。那么`s(g)`的操作，就是把`g`的系数都取共轭。举例说明一下：
例1：假设K和`g`如前，因K是3次的，所以`s`操作结果有3个。因为`g`的系数都是有理数，有理数在K中的共轭都是本身，所以三个操作结果都是`g`本身。
例2：设`a_1、a_2、a_3`是`f`的3个根，`g(x)=(x-a_1)^3+2(x-a_1)^2+(x-a_1)-1`，那么`s`的3个结果就是：\[\begin{align*}g_1&=g\\g_2&=(x-a_2)^3+2(x-a_2)^2+(x-a_2)-1\\g_3&=(x-a_3)^3+2(x-a_3)^2+(x-a_3)-1\end{align*}\]        记`s(g)=\{g_1,g_2,g_3\}`
例3：如果`g(x)=a_1x^2+a_2`呢？这就要看`a_2`能不能被`a_1`表示出来，如果不能，那么`g`的系数不在K中，是不满足题目假设的。
        说完了嵌入，我们把所有的嵌入乘起来，定义`N(g)`是`g`所有嵌入的乘积所得到的多项式。
        我们的第一个事实是：`N(g)`的系数总是有理数。
借用例2，`N(g)=g_1g_2g_3`，展开式为\[x^9+6x^8+18x^7+34x^6+45x^5+56x^4+93x^3+106x^2+56x+8\] 系数都是有理数吧。这个事实是容易证明的。

【事实2】如果某个多项式`g`在K中不可约，那么`N(g)`一定是某个在Q中不可约多项式的幂。
        举几个例子来说明：
例4：`g=x+a_1`在K中不可约，所以`N(g)=x^3+x-1`在Q中不可约。
例5：`g=x^3+2x^2+x-1`时，`N(g)=(x^3+2x^2+x-1)^3`，是在Q中不可约多项式的3次幂。
        赫赫，当然啥也说明不了，不能说明多项式`g`在K中不可约，因为没人说逆命题也成立。
例6：借用例2中的`g=(x-a_1)^3+2(x-a_1)^2+(x-a_1)-1`\[\begin{align*}N(g)&=x^9+6x^8+18x^7+34x^6+45x^5+56x^4+93x^3+106x^2+56x+8\\&=(x^3+2x^2+5x+1)(x^6+4x^5+5x^4+3x^3+10x^2+16x+8)\end{align*}\]说明`g`在K中是可约的，也说明`g(x+a_1)=x^3+2x^2+x-1`在K中也是可约的。看，已经有点思路了吧，而这个思路可行么，就要往下看了。

【事实3】如果某个多项式`g`在K中没有平方因子（就是没有重根啦），那么只有有限个有理数`k`，使得`N(g(x-ka))`含有平方或更高次因子（即有重根）。
【事实4】假设某个`g`（系数在K中）和`N(g)`（系数在Q中）都没有平方因子，假设`N(g)`在Q中分解成为`n`个不可约多项式`N_1,\cdots,N_n`，那么，`\gcd(g,N_i)`就是`g`在K中的`n`个不可约因子。

下面描述一下算法，设K=Q(`a`)，算法输入为首1有理系数多项式`f`（`a`是`f`的根），非零多项式`g`（系数在K中），算法输出`g`在K中的完全因式分解。
（我们用例子同步演示一下，输入为：`f(x)=x^3+x+1，g(x)=x^3+2x^2+x-1`。）

第1步，让`g`没有重根。求`\gcd(g,g')`，然后让`g=g/\gcd(g,g')`。`\gcd`可以模仿求两个整数的公因子的方法。对于复杂情况，貌似最好的方法是Collins的Sub-Resultant GCD。我们这里就凑合过去吧，赫赫。
（我们例子`g`没有重根。）
第2步，求`N(g(x-a))`。就是将`f(a)`和`g(x-a)`中`a`约掉。用Resultant方法就可以了，可以计算Sylvester矩阵的特征值。
        演示一下:\[f(a)=a^3+a+1，g(x-a)=-a^3+(3x+2)a^2+(-3x^2-4x-1)a+(x^3+2x^2+x-1)\]
它们的系数分别是：    `\{1,0,1,1\}`和`\{-1,3x+2,-3x^2-4x-1,x^3+2x^2+x-1\}`
它的Sylvester矩阵就是6×6矩阵\[\begin{pmatrix}1&0&1&1&0&0\\0&1&0&1&1&0\\0&0&1&0&1&1\\-1&3x+2&-3x^2-4x-1&x^3+2x^2+x-1&0&0\\0&-1&3x+2&-3x^2-4x-1&x^3+2x^2+x-1&0\\0&0&-1&3x+2&-3x^2-4x-1&x^3+2x^2+x-1\end{pmatrix}\]真是啰嗦呀，赫赫。然后算它的行列式的值，就可以得到上面提到的\[N(g(x-a))=x^9+6x^8+18x^7+34x^6+45x^5+56x^4+93x^3+106x^2+56x+8\]
第3步，检查刚才算的`N`。我们不停的计算`N(g(x-ka))`，其中`k`为任意有理数，我们可以依次取1、2、3……，上面算的是`k=1`时的情况。我们不停的试，一直到`N(g(x-ka))`没有重根为止……赫赫，一般来讲算一两次`N`就符合条件了。
（一次中的。）
第4步，把`N`在Q中分解。假设我们已经会这个了，先将其在有限域Fp中分解是高效的方法。
（上面提到的，`N(g(x-a)=(x^3+2x^2+5x+1)(x^6+4x^5+5x^4+3x^3+10x^2+16x+8)`。）
第5步，分别求`\gcd(g(x+ka),N_i)`。这一步也是推荐用Sub-Resultant的方法，但是我们这里用简单的辗转相除，这里的运算是在K中进行的。
（繁琐的辗转相除开始，`f1=g(x+a)=x^3+(3a+2)x^2+(3a^2+4a+5)x+(2a^2+4a)，f2=x^3+2x^2+5x+1。f3=f1%f2=(3a)x^2+(3a^3+4a+4)x+(2a^2+4a+1)`，将`f3`首项系数弄成1，即`f3=f3/(3a)=x^2+(-4/3a^2+a)x+(-1/3a^2+2/3a+1)`。然后`f4=f2%f3=(20/9a^2-16/9a+8/3)x+(-4/9a^2+4/9a-16/9)`，将`f4`首项弄成1，`f4=x+(-a^2)`。如此，就得到了`b=a^2`。大家试验一下，就会发现这一步的计算量是蛮大的，所以再次推荐Sub-Resultant。）

在这个算法中，因为答案和中间过程是整数，所以也可以先求出一定精度的`a`来（浮点的复数），然后直接运算，最后取整，这样的速度是更快的，但是误差超过1就不好了，所以要验证的。

上面的内容全部来自Cohen的书，他在书中还提到了另外的两种算法，并且都要优于上面的算法，赫赫。其中的第一种算法还涉及到了Cohen倍加推崇的LLL算法。（书中涉及的算法很广泛，比如一般数域筛GNFS、椭圆曲线ECM，所以给他夸一下是很不易的。赫赫。）

数学星空

学习了,看样子还需要多补充代数数论及计算数论的知识...

wangfeizaaq

定理1.2（阿贝尔引理）  f（x）是系数在域P中且次数为素数p的不可约多项式，α为域P上另一个不可约多项式g（x）的一个根。如果f（x）在扩域P（α）成为可约，则p必定整除g（x）的次数。
证明  在讨论数域P（α）上的多项式φ（x）时，为明确起见我们把α从φ（x）的系数中分离出来①而把φ（x）记为φ（x，α），即把φ看作系数在P中的关于未知量x和α的一个二元多项式。
    现在，由条件f（x）在P（α）上可约，应该存在P上的二元多项式φ（x，α），ψ（x，α）使得
                                  f（x）=φ（x，α）ψ（x，α）。                           （2）
既然数域P包含有理数域Q，于是对每个有理数r，我们可令
    u（x）=f（r）-φ（r，x）ψ（r，x），
则u（x）显然是P上的多项式并且u（α）=0。这表明，u（x）和不可约多项式g（x）有公共根α。由阿贝尔不可约性定理知g（x）的每个根α1=α，α2，…，αq亦是u（x）的根，即u（αi）=0（i=1，2，…，q）。从另一个角度看，多项式f（x）-φ（x，αi）ψ（x，αi）当x取每个有理数r时均为零，就是说，它有无限多个根，这只能是零多项式。于是，有下述q个恒等式：
f（x）=φ（x，α1）ψ（x，α1），
f（x）=φ（x，α2）ψ（x，α2），
…
f（x）=φ（x，αq）ψ（x，αq）。
现在，把上述q个恒等式左右两边分别相乘得到                    
f（x）q=Ф（x）•Ψ（x），
其中Ф（x）及Ψ（x）分别为q个多项式φ（x，α1），φ（x，α2），…及ψ（x，α1），ψ（x，α2），…的乘积。
注意到Ф（x）是多项式g（x）的全部根α1，α2，…，αq的对称函数，根据对称多项式的基本定理，Ф（x）可以表示为g（x）诸系数的多项式，因此Ф（x）是P[x]中的多项式。由于同样的原因，Ψ（x）也是P[x]中的多项式。
又多项式f（x）在P上不可约，所以Ф（x）和Ψ（x）都只能是f（x）的方幂（当然可能相差一个常数系数）。令
Ф（x）=f（x）u，Ψ（x）=f（x）v，
其中u+v=q。今设φ（x，α）与ψ（x，α）关于x次数分别为m与n。比较左边和右边的次数可得
mq=up，nq=vp。
又因为m与n均小于素数p，由此可知p为q的因子。至此就完成了阿贝尔引理的证明。

kastin

如果用latex编辑一下就更好了，文本排版看上去眼睛痛。