数理解析研究所講究録920 巻 1995 年 25-30

25Abstract:

In this paper, we first give a brief introduction to Ritt-Wu Method, thenshow the posibility of doing some computations over successive algebraic extension field by Ritt-Wu method. At the end of this paper, the relation
between factorization of polynomials and the computation of primitive element is also discussed.

3.1 Introduction to)$\mathrm{R}\mathrm{i}\mathrm{t}\mathrm{t}- \mathrm{W}\mathrm{u}\mathrm{S}$methoda set of variables
be a field of characteristic zero,Letof a non-zero polynomialwith a fixed ordering $y_{1}<\cdots<y_{n}$ . The classis defined to be the largest subscript ofin the ringis called the main varable
indeed occurring in if any, otherwise , andof if $c=cl_{S}(f)\neq 0$ . The coefficient of the term of highest degree of themain variable is called the initial of , denoted by Init $(f)$ .
$I\backslash ^{\nearrow}$$y_{1},$ $y_{2},$$\cdots,$$y_{n}$$n$$\mathrm{c}1_{\mathrm{S}}(f)$$f$$y_{i}’s$$I\mathrm{t}^{\nearrow}[y1, y2, \cdots, y_{n,x}]$

$0$

$f$

$f$

$f$

$y_{c}$

26$c=cl_{S}(f)\neq$
Let and be two polynomials in the ring
. We say that is reduced with respect to if $cls(g)<cl_{S}(f)$ or $cls(g)\geq$$cl_{S}(f)$ but.
$f$$K[y_{1}, y_{2}, \cdots, y_{n}],$

$g$

$0$

$f$

$g$

$deg_{y_{\mathbb{C}}}g<deg_{y}cf$

Apparently, if is not reduced with respect tosuch that
$g$

$f$

, we can find $I,$ $Q,$ $R\in$$I\backslash ^{J}[\prime y1, y_{2}, \cdots , y_{n}]$$I\cdot g=Q\cdot f+R$

with $cls(I)<cl_{S}(f)$ and$R$

reduced with respect to .
$f$

The polynomial
above is called the pseudo-remainder of withrespect to , denoted by prem $(f, g)$ , and the procedure to get from andis called pseudo-division.
$R$

$g$

$R$

$f$

$f$

$g$

Remark: In practice, in order to control the growth of the degree andthe number of terms of polynomials, we should choose the polynomial inpseudo-division carefully.
$I$

A finite set $A$ of polynomials
is called an ascending set
if $r=1$ and $A_{1}\neq 0$ or $r>1,0<cls(A_{1})<\cdots<cls(A_{r})$ andis reducedwith respect tofor all $j>i$ . Furthermore, if all the polynomials of $A$
exceptare linear with respect to their own main variables, then it is called
quasi-linear ascending set.
$A_{1},$ $A_{2},$$\cdots,$$A_{r}$$A_{j}$$A_{i}$$A_{1}$

If a polynomial is reduced with respect to any polynomial of an asending set $A$ , then we say it is reduced with respect to $A$ , otherwise, we candefine the pseudo-remainder prem $(f, A)$ of with respect to $A$ inductively
$f$

$f$

asprem $(f, A_{1}, \cdots , A_{s})=p_{\Gamma}em(prem(f, A1, \cdots, AS-1), A_{S})$For any polynomial set , we denote the set of common zeros of polyby Zeronomials in. If is another (non-zero) polynomial, we writeZerofor.
$\mathcal{F}$$\mathcal{F}$$(\mathcal{F}/G)$$G$$(\mathcal{F})$$Zero(\mathcal{F})\backslash Zero(c)$For any polynomial set , we can find an ascending set
the ideal
Ideal
generated by the polynomials in such that any polynomial of$\mathcal{F}$$(\mathcal{F})$$C\mathrm{f}\mathrm{r}\mathrm{o}\mathrm{n}\mathrm{l}$$\mathcal{F}$$\mathcal{F}$27

has pseudo-remainder$0$with respect to , and so$C$Zero $(C/J)\subset Zero(PS)\subset Zero(C)$where is the product of initials of plolynomials in . The ascending set
having such properties is called characteristic set of .
$J$

$C$

$\mathcal{F}$,Let $A:A_{1}(y_{1}),$ $A_{2}(y1, y_{2}),$be an ascending set. $A$ is, as a polynomial in, is irreducible,
said to be irreducible ifis the fieldwhere
obtained from the fieldby theof . The fieldis called successive algebraic
adjunction of a root,
extension field of { with adjoining polynomials
or simply $A$ .
$\cdots$$A_{r}(y_{1}, \cdots, y_{r})$$A_{i+1}$$I\backslash ^{\nearrow}0=I\{,$$I\mathrm{f}_{i}[y_{i+1}]$$I<_{i-1}$$K_{i-1}(\alpha_{i})$$K_{i}$$\alpha_{i}$$A_{i}$$I\{_{r}$$I$$A_{1},$ $\cdots$$A_{r}$In the present paper, we will discuss some computations over such successive algebraic extension field.

3.2 Some Computations over Successive Algebraic Extenslon Field
In this section, we first discuss the computations of miminal polynomial
and primitive element based on Ritt-Wu method, then discuss the relation
between the polynomial factorization and the compuation of primitive elements.
$A_{r}(yr)$ be an irrducible ascending set.
LetAs discussed in last section, we can get a successively algebraic extension field,by adjoining the polynomials
to the ground field. In fact, we have$\mathrm{A}_{1}(y_{1}),$$A_{2}(y_{2}),$ $\cdots,$$E$$A_{1}(y_{1}),$ $A_{2}(y_{2}),$$\cdots$$A_{r}(y_{r})$$I\backslash ^{r}’$Proposition: $E\simeq K[y_{1}, y2, \cdots , y_{r}]/<A_{1},$is the ideal generated by.
$A_{1},$$\cdots,$$\cdots$, $A_{r}>$ , where $<A_{1},$$\cdots,$$A_{r}>$$A_{r}$

can be treated as a multivariate polynimial. And the computations in can be considered as thosewith, $A_{r}>$ .
of polynomials modulo $<A_{1},$So each element of$E$$e(y_{1}, \cdots, y_{r})$$E$$deg_{y}.\cdot e<deg_{y_{i}}A_{i}$$\cdots$

Proposition: Let
be an irreducible ascending set, then the set of all the polynomials which have pseudo-remainder$A:\mathrm{A}_{1}(y_{1}),$ $A_{2}(y_{2}),$ $\cdots,$ $A_{r}(y_{r})$28with respect to $A$ is a prime ideal of polynomial ringunder
the ordinary polynomial addition and multiplication. Furthermore, it is also
a maximal ideal if $r=n$ .
$0$$I<[y_{1}, \cdots, y_{n}]$In fact,

Proposition Let
be an irreducible ascending set. Then the ideal of
all the polynomials which have pseudo-remainder with respect tois thesame with the ideal generated by the polynomials of .
$A$

$A$

$0$

$A$

The above proposition tell us that it is possible to carry out the computations in $E$ by Ritt-Wu method.

Proposition Let $f(y_{1}, \cdots, y_{r}, y)$ and $g(y_{1}, \cdots, yr’ y)$ be two polynomial$f(y1, \cdots, yr’ y),$ $g(y1, \cdots, y_{r}, y)\}$over $E,$ be the characteristic set ofunder order $y_{1}<\cdots<y_{r}<y$ . Then the polynomial of which containing only the variable is the greatest common divisor of $f(y_{1}, \cdots, y_{r}, y)$ andover .
$C$$\mathrm{f}^{A_{1},\cdots,A_{r}},$

$C$

$y$

$E$

$g(y_{1}, \cdots , y_{r}, y)$

Proposition Let $f(y_{1}, \cdots, y_{r}, y)$ be a non-zero polynomial of over ,then the characteristic set ofunder order $y<$$y_{1}<\cdots<y_{r}$ must contains a polynomial with only
as its variable.
$y$

$E$

$\{f(y1, \cdots, y_{\Gamma}, y), A_{1}, \cdots, A_{r}\}$

$y$

Let
then$e(y_{1}, \cdots, y_{r})$be an element in $E$ and let $g(y_{1}, \cdots, yr’ y)=y-e(y_{1}, \cdots, y_{r})$ ,Proposition Let $m(y)$ be the polynomial ofin the characteristic
set of $\{g(y1, \cdots, y_{r}, y), A_{1,r}\ldots, A\}$ under ordering $y<y_{1}<\cdots<y_{r}$ . If$m(y)=m_{1}(z)\cdots m_{t}(z)$ , then there is one and only one
having pseudoremainder with respect to the ascending set $\{A_{1}, \cdots, A_{r}, g(y_{1}, \cdots, y_{r}, y)\}$ .
In fact, this $m_{i}(z)$ is the minimal polynomial of the elment.
$y$$m_{i}(z)$$0$$e(y_{1}, \cdots, y_{r})$As we know, any seperable finite extension is a simple extension, soProposition$E$

is a simple extension of $K$ .

The following proof to this proposition is belong to Van de Waerdan.
Since some facts from this proof will fit our purpose, we repeat it here.

29. Let $f(x)$Proof: First we prove the proposition for two elments
and $g(x)$ be the minimal polynomials of and respectively. We take a fieldin which $f(x),$ $g(x)$ split. Let the distinct zeros of $f(x)$ be.
and let those of $g(x)$ be$\alpha,$$\alpha$$\beta$$\beta$$\alpha_{1}=\alpha,$$\beta_{1}=\beta,$$\beta_{2},$$\cdots,$For $k\neq 1$ , the equationfor every and every $k\neq 1$ . If we takelinear equations, we have$\alpha_{2},$$\alpha_{r}$$,$$\beta_{S}$has at most one root in $K$
different from the roots of all thesefor every and $k\neq 1$ .

$\alpha_{i}+x\beta_{k}=\alpha_{1}+x\beta_{1}$$i$$\cdot\cdot,$

$c$

$x$

$\alpha_{i}+c\beta_{k}\neq\alpha_{1}+c\beta_{1}$$i$Let $\theta=\alpha_{1}+c\beta_{1}=\alpha+c\beta$ , then we can assert that would be a
. In fact, satisfies the equations $g(\beta)=0$
primitive element of. The polynomial $g(x)$ ,and $f(\theta-c\beta)=f(\alpha)=0$ , with coefficients in$f(\theta-cx)$ have only the rootin common by the choice of . But is a
simple root of $g(x)$ , therefore, $g(x)$ and $f(\theta-cx)$ have but one linear factor$x-\beta$ in common. The coefficients of this greatest common divisor and so. Thus we have $I<(\alpha, \beta)=I<(\theta)$ .
must lie in$\theta$$K(\alpha, \beta)$$\beta$$I<(\theta)$$c$$\beta$$\beta$$\beta$$I\{’(\theta)$

This completes the proof of theorem for $r=2$ . Once it is proved for $r-$$1(\geq 2)$ , we haveand soaccording to the already proved part of theorem.
$I\{’(\alpha_{1}, \cdots, \alpha_{r-1})=I<(\eta)$$I<(\alpha_{1}, \cdots, \alpha_{r})=I\{’(\eta, \alpha)r=$$I\{(\theta)$$i$

From the proof, we can see that,

Proposition For almost all vectors
a primitive element of$(C_{1}, \cdots, C_{\Gamma})\in I<^{n},$$\sum_{t}ci\alpha_{i}$would give$E$

is to choose a vector
So the task to find a primitive element forand check if it is a primive element, this is equivalent to check if.
its miminal polynomial has degree$E$$(C_{1}, \cdots, C_{\Gamma})$$\Pi deg_{y}.\cdot A_{i}$The above technique for finding the primitive elements is not new, buteach author has their own method to check the primitiveness of the element,
here we want tell the Ritt-Wu method can also fit this purpose.
From now on, we suppose we have found a primitive element for the.
successive algebraic exension field of and its minimal polynomial$\theta$$i$$E$$I\backslash ^{\nearrow}$$\uparrow n(x)$Without loss of generality, we can consider $E$ as an extension field of’$I\backslash ’$

30

by adjoining $m(x)$ . Let
be a squarefree polynomial of variable
over , then it can be writen into the form $f(x, y)$ .
$f(y_{1}, \cdots , y_{r}, y)$

$E$

$y$

Proposition If $f(x, y)$ is irreducible over , then for almost all
in $K$ ), the characteristic set of $\{m(x), f(x, y), z-(y+cx)\}$ is quasi-linear.
$E$$c\in E(\mathrm{o}\mathrm{r}$Proposition Suppose $f(x, y)=f_{1}(x, y)\cdots f_{\ell}(x, y)$ , where $f_{i}(x, y)$ are
irreducible polynomials over . Then for almost all integer $c\in E$ , a elementof the form $y+cx$ would be a primitive elementof the extension
fields of obtained by adjoining the polynomials $f_{i}(x, y)$ respectively.
$E$$(0\mathrm{e}\mathrm{r}I\{)$$E$

Proposition Let $y+cx$ be the form mentioned in the above proposition,
its minimal polynomial
as a primitive element of the extension
field ofobtained by adjoining polynomial $f_{i}(x, y)$ . Then if $g(z)$ be thepolynomial of in the characteristic set of $\{m(x), f(x, y), z-(y+cx)\}$ underorder $z<x<y$ , we have $g_{i}(z)|g(z)$ for all .
$g_{i}(z)$$(\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}I\{)$

$E$

$z$

$i$

Proposition Let $g(z)$ as above. Suppose $g(z)=\Pi_{i}g_{i}’(z)$ , where
are the irreducible factors of $g(z)$ over , then $gcd(g_{i}’(y-cx), f(x, y))$ is anirreducible factor of $f(x, y)$ over if it is not equal to 1. Furthermore, suchgreatest common divisors can give out all the irreducible factors of $f(x, y)$over .
$g_{i}’(z)$$I\{’$$E$$E$

References:
1. B. L. Van der Waerden, Modern Algebra, Revised English Edition (1953),
2. Dongming Wang, A Mehod for Facorizing Multivariate Polynomials
over Successive Algebraic Extension Fields
3. Yokoyama, K., Noro, M., and Takeshima,. Computing
Primitive Elements of Extension Fields. J. Symb. Comp. 8/6, 553-580.
$\mathrm{T}.(1990)$