Algfield - Maple Programming Help

Home : Support : Online Help : Mathematics : Evaluation : evala : evala/Algfield

Algfield

compute an irreducible representation for a field extension

 Calling Sequence evala(Algfield(S, G))

Parameters

 S - set of algebraic numbers in RootOf notation G - (optional) set of algebraic numbers in RootOf notation (a ground field)

Description

 • Given a set of RootOfs representing algebraic numbers (see algnum) or algebraic functions (see algfun), this function attempts to compute a set of irreducible RootOfs representing the same field. The set S may also contains algebraic numbers in radical notation (see radnum), which be will converted to the RootOf notation.
 • Algebraic functions in RootOf notation (algfun) or radical notation (radfun) are also valid inputs, but in this case, this routine will usually fail to find an irreducible representation if some factorizations are found (see below).
 • A set S of RootOfs is called irreducible (or independent) if the RootOfs satisfy no non-trivial algebraic relations. In other words, the polynomial defining a RootOf R in S must be irreducible over the field generated by the RootOfs in S which do not contain R. This function is similar to Indep and radfield.
 • Typically, this function may be used to preprocess an expression involving reducible algebraic numbers in RootOf notation before invoking a procedure which requires the RootOfs to be irreducible.
 • The output is a five element list of the following form (the first three elements are the most important ones):
 [[r_1=f_1(R_1,...,R_s), r_2=f_2(R_1,....,R_s),...., r_t=f_t(R_1,...,R_s)],
 [[R_1=g_1(r_1,...,r_t), R_2=g_2(r_1,....,r_t),...., R_s=g_s(r_1,...,r_t)],
 {R_1,...,R_s},
 return_code,
 {V_1=W_1,...,V_u=W_u}]
 where the r_i's are the input RootOfs, the R_i's are the output RootOfs, the f_i's are the expressions of the r_i's in terms of the R_i's and the g_i's are the expressions of the R_i's in terms of the r_i's.
 – The first sublist is a forward substitution list meant to be used in conjunction with the eval and subs commands. The purpose of this list is to transform an expression so that it involves only a set of irreducible RootOfs.
 – The second sublist is a backward substitution list meant to restore the original RootOfs.
 – The third element is the set of irreducible RootOfs.
 – The return code can be true, if the routine could find a set of irreducible RootOfs to express the input, false if such a set could not be found and some unresolved relations exist (see example below). The latter usually happens when the input contains reducible algebraic functions.
 – The fifth element is a set of unresolved relations.
 • Note that trivial substitutions of the form R=R are omitted so that the number of elements in the forward (resp. backward) substitution list may not be t (resp. s).
 • If a second argument G is given, then the RootOfs in the set G are considered as independent.
 • WARNINGS:
 – The running time of this algorithm is, in general, exponential in the number of input RootOfs, and so is the degree of the extension generated by the input.
 – Since the ordering of objects may vary from a session to another, the output may change accordingly. The ordering may also have an influence on the running time.

Examples

 > $\mathrm{r1}≔\mathrm{RootOf}\left({\mathrm{_Z}}^{4}-4,\mathrm{index}=3\right)$
 ${\mathrm{r1}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{4}}{-}{4}{,}{\mathrm{index}}{=}{3}\right)$ (1)
 > $\mathrm{evala}\left(\mathrm{Algfield}\left(\mathrm{r1}\right)\right)$
 $\left[\left[{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{4}}{-}{4}{,}{\mathrm{index}}{=}{3}\right){=}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{2}\right)\right]{,}\left[{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{2}\right){=}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{4}}{-}{4}{,}{\mathrm{index}}{=}{3}\right)\right]{,}\left\{{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}{\mathrm{index}}{=}{2}\right)\right\}{,}{\mathrm{true}}{,}{\varnothing }\right]$ (2)
 > $\mathrm{r2}≔\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-3,\mathrm{index}=1\right)$
 ${\mathrm{r2}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{3}{,}{\mathrm{index}}{=}{1}\right)$ (3)
 > $\mathrm{r3}≔\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-6,\mathrm{index}=1\right)$
 ${\mathrm{r3}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{6}{,}{\mathrm{index}}{=}{1}\right)$ (4)
 > $\mathrm{evala}\left(\mathrm{Algfield}\left(\left\{\mathrm{r1},\mathrm{r2},\mathrm{r3}\right\}\right)\right)$
 $\left[\left[{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{4}}{-}{4}{,}{\mathrm{index}}{=}{3}\right){=}{-}\frac{{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{6}{,}{\mathrm{index}}{=}{1}\right){}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{3}{,}{\mathrm{index}}{=}{1}\right)}{{3}}\right]{,}\left[\right]{,}\left\{{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{6}{,}{\mathrm{index}}{=}{1}\right){,}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{3}{,}{\mathrm{index}}{=}{1}\right)\right\}{,}{\mathrm{true}}{,}{\varnothing }\right]$ (5)
 > $\mathrm{evala}\left(\mathrm{Algfield}\left(\left\{\mathrm{r1}\right\},\left\{\mathrm{r2},\mathrm{r3}\right\}\right)\right)$
 $\left[\left[{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{4}}{-}{4}{,}{\mathrm{index}}{=}{3}\right){=}{-}\frac{{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{6}{,}{\mathrm{index}}{=}{1}\right){}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{3}{,}{\mathrm{index}}{=}{1}\right)}{{3}}\right]{,}\left[\right]{,}\left\{{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{6}{,}{\mathrm{index}}{=}{1}\right){,}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{3}{,}{\mathrm{index}}{=}{1}\right)\right\}{,}{\mathrm{true}}{,}{\varnothing }\right]$ (6)
 > $\mathrm{alias}\left(\mathrm{s1}=\mathrm{RootOf}\left({\mathrm{_Z}}^{4}-{\left(1+\mathrm{r1}\right)}^{2},\mathrm{index}=1\right)\right):$
 > $\mathrm{alias}\left(\mathrm{s2}=\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-2,\mathrm{index}=2\right)\right):$
 > $\mathrm{evala}\left(\mathrm{Algfield}\left(\mathrm{s1}\right)\right)$
 $\left[\left[{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{4}}{-}{4}{,}{\mathrm{index}}{=}{3}\right){=}{\mathrm{s2}}{,}{\mathrm{s1}}{=}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{+}{\mathrm{s2}}{+}{1}{,}{\mathrm{index}}{=}{1}\right)\right]{,}\left[{\mathrm{s2}}{=}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{4}}{-}{4}{,}{\mathrm{index}}{=}{3}\right){,}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{+}{\mathrm{s2}}{+}{1}{,}{\mathrm{index}}{=}{1}\right){=}{\mathrm{s1}}\right]{,}\left\{{\mathrm{s2}}{,}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{+}{\mathrm{s2}}{+}{1}{,}{\mathrm{index}}{=}{1}\right)\right\}{,}{\mathrm{true}}{,}{\varnothing }\right]$ (7)

Factorization algorithms for polynomials over algebraic extension fields usually require irreducible RootOfs. In the example below, the polynomial p is transformed and its coefficients are restored after the factorization step.

 > $\mathrm{alias}\left(\mathrm{zeta}\left[3\right]=\mathrm{RootOf}\left({\mathrm{_Z}}^{3}-1,\mathrm{index}=2\right)\right):$
 > $p≔{x}^{3}+{x}^{2}\mathrm{zeta}\left[3\right]-x{\mathrm{zeta}\left[3\right]}^{2}-1+x-\mathrm{zeta}\left[3\right]$
 ${p}{≔}{{x}}^{{3}}{+}{{x}}^{{2}}{}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{1}{,}{\mathrm{index}}{=}{2}\right){-}{x}{}{{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{1}{,}{\mathrm{index}}{=}{2}\right)}^{{2}}{+}{x}{-}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{1}{,}{\mathrm{index}}{=}{2}\right){-}{1}$ (8)
 > $A≔\mathrm{evala}\left(\mathrm{Algfield}\left(\mathrm{zeta}\left[3\right]\right)\right):$
 > $\mathrm{p1}≔\mathrm{factor}\left(\mathrm{eval}\left(p,A\left[1\right]\right)\right):$
 > $\mathrm{eval}\left(\mathrm{p1},A\left[2\right]\right)$
 ${-}\left({2}{}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{1}{,}{\mathrm{index}}{=}{2}\right){}{x}{+}{{x}}^{{2}}{-}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{1}{,}{\mathrm{index}}{=}{2}\right)\right){}\left({-}{x}{+}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{1}{,}{\mathrm{index}}{=}{2}\right)\right)$ (9)

Some examples of failure:

 > $\mathrm{evala}\left(\mathrm{Algfield}\left(\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-{x}^{2},\mathrm{index}=1\right)\right)\right)$
 $\left[\left[\right]{,}\left[\right]{,}{\varnothing }{,}{\mathrm{false}}{,}\left\{{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{{x}}^{{2}}{,}{\mathrm{index}}{=}{1}\right){=}{x}{,}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{{x}}^{{2}}{,}{\mathrm{index}}{=}{1}\right){=}{-}{x}\right\}\right]$ (10)

Here, Algfield failed because none of the possible factors is equal, as a function of the complex variable x, to the input function.

 > $\mathrm{r4}≔\mathrm{RootOf}\left({\mathrm{_Z}}^{4}-4\right)$
 ${\mathrm{r4}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{4}}{-}{4}\right)$ (11)
 > $\mathrm{evala}\left(\mathrm{Algfield}\left(\mathrm{r4}\right)\right)$
 $\left[\left[\right]{,}\left[\right]{,}{\varnothing }{,}{\mathrm{false}}{,}\left\{{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{4}}{-}{4}\right){=}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{2}\right){,}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{4}}{-}{4}\right){=}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{+}{2}\right)\right\}\right]$ (12)

Algfield fails because there are two possible choices for r4. The possible relations are given by the fifth element of the list.

 > $\mathrm{r5}≔\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-3\right)$
 ${\mathrm{r5}}{≔}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{3}\right)$ (13)
 > $\mathrm{evala}\left(\mathrm{Algfield}\left(\left\{\mathrm{r2},\mathrm{r5}\right\}\right)\right)$
 $\left[\left[\right]{,}\left[\right]{,}\left\{{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{3}{,}{\mathrm{index}}{=}{1}\right)\right\}{,}{\mathrm{false}}{,}\left\{{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{3}\right){=}{-}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{3}{,}{\mathrm{index}}{=}{1}\right){,}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{3}\right){=}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{3}{,}{\mathrm{index}}{=}{1}\right)\right\}\right]$ (14)

Algfield does not know whether r2=r5 or not.