1Function: polredabs
2Section: number_fields
3C-Name: polredabs0
4Prototype: GD0,L,
5Help: polredabs(T,{flag=0}): a smallest generating polynomial of the number
6 field for the T2 norm on the roots, with smallest index for the minimal T2
7 norm. flag is optional, whose binary digit mean 1: give the element whose
8 characteristic polynomial is the given polynomial. 4: give all polynomials
9 of minimal T2 norm (give only one of P(x) and P(-x)).
10Doc: returns a canonical defining polynomial $P$ for the number field
11 $\Q[X]/(T)$ defined by $T$, such that the sum of the squares of the modulus
12 of the roots (i.e.~the $T_2$-norm) is minimal. Different $T$ defining
13 isomorphic number fields will yield the same $P$. All $T$ accepted by
14 \tet{nfinit} are also allowed here, e.g. nonmonic polynomials, or pairs
15 \kbd{[T, listP]} specifying that a nonmaximal order may be used. For
16 convenience, any number field structure (\var{nf}, \var{bnf},\dots) can also
17 be used instead of $T$.
18 \bprog
19 ? polredabs(x^2 + 16)
20 %1 = x^2 + 1
21 ? K = bnfinit(x^2 + 16); polredabs(K)
22 %2 = x^2 + 1
23 @eprog
24
25 \misctitle{Warning 1} Using a \typ{POL} $T$ requires computing
26 and fully factoring the discriminant $d_K$ of the maximal order which may be
27 very hard. You can use the format \kbd{[T, listP]}, where \kbd{listP}
28 encodes a list of known coprime divisors of $\disc(T)$ (see \kbd{??nfbasis}),
29 to help the routine, thereby replacing this part of the algorithm by a
30 polynomial time computation But this may only compute a suborder of the
31 maximal order, when the divisors are not squarefree or do not include all
32 primes dividing $d_K$. The routine attempts to certify the result
33 independently of this order computation as per \tet{nfcertify}: we try to
34 prove that the computed order is maximal. If the certification fails,
35 the routine then fully factors the integers returned by \kbd{nfcertify}.
36 You can also use \tet{polredbest} to avoid this factorization step; in this
37 case, the result is small but no longer canonical.
38
39 \misctitle{Warning 2} Apart from the factorization of the discriminant of
40 $T$, this routine runs in polynomial time for a \emph{fixed} degree.
41 But the complexity is exponential in the degree: this routine
42 may be exceedingly slow when the number field has many subfields, hence a
43 lot of elements of small $T_2$-norm. If you do not need a canonical
44 polynomial, the function \tet{polredbest} is in general much faster (it runs
45 in polynomial time), and tends to return polynomials with smaller
46 discriminants.
47
48 The binary digits of $\fl$ mean
49
50 1: outputs a two-component row vector $[P,a]$, where $P$ is the default
51 output and \kbd{Mod(a, P)} is a root of the original $T$.
52
53 4: gives \emph{all} polynomials of minimal $T_2$ norm; of the two polynomials
54 $P(x)$ and $\pm P(-x)$, only one is given.
55
56 16: (OBSOLETE) Possibly use a suborder of the maximal order, \emph{without}
57 attempting to certify the result as in Warning 1. This makes \kbd{polredabs}
58 behave like \kbd{polredbest}. Just use the latter.
59
60 \bprog
61 ? T = x^16 - 136*x^14 + 6476*x^12 - 141912*x^10 + 1513334*x^8 \
62       - 7453176*x^6 + 13950764*x^4 - 5596840*x^2 + 46225
63 ? T1 = polredabs(T); T2 = polredbest(T);
64 ? [ norml2(polroots(T1)), norml2(polroots(T2)) ]
65 %3 = [88.0000000, 120.000000]
66 ? [ sizedigit(poldisc(T1)), sizedigit(poldisc(T2)) ]
67 %4 = [75, 67]
68 @eprog
69
70 The precise definition of the output of \tet{polredabs} is as follows.
71
72 \item Consider the finite list of characteristic polynomials of primitive
73 elements of~$K$ that are in~$\Z_K$ and minimal for the~$T_2$ norm;
74 now remove from the list the polynomials whose discriminant do not have
75 minimal absolute value. Note that this condition is restricted to the
76 original list of polynomials with minimal $T_2$ norm and does not imply that
77 the defining polynomial for the field with smallest discriminant belongs to
78 the list !
79
80 \item To a polynomial $P(x) = x^n + \dots + a_n \in \R[x]$ we attach
81 the sequence $S(P)$ given by $|a_1|, a_1, \dots, |a_n|, a_n$.
82 Order the polynomials $P$ by the lexicographic order on the coefficient
83 vectors $S(P)$. Then the output of \tet{polredabs} is the smallest
84 polynomial in the above list for that order. In other words, the monic
85 polynomial which is lexicographically smallest with respect to the absolute
86 values of coefficients, favouring negative coefficients to break ties, i.e.
87 choosing $x^3-2$ rather than $x^3+2$.
88
89Variant: Instead of the above hardcoded numerical flags, one should use an
90 or-ed combination of
91
92 \item \tet{nf_PARTIALFACT} (OBSOLETE): possibly use a suborder of the maximal
93 order, \emph{without} attempting to certify the result.
94
95 \item \tet{nf_ORIG}: return $[P, a]$, where \kbd{Mod(a, P)} is a root of $T$.
96
97 \item \tet{nf_RAW}: return $[P, b]$, where \kbd{Mod(b, T)} is a root of $P$.
98 The algebraic integer $b$ is the raw result produced by the small vectors
99 enumeration in the maximal order; $P$ was computed as the characteristic
100 polynomial of \kbd{Mod(b, T)}. \kbd{Mod(a, P)} as in \tet{nf_ORIG}
101 is obtained with \tet{modreverse}.
102
103 \item \tet{nf_ADDZK}: if $r$ is the result produced with some of the above
104 flags (of the form $P$ or $[P,c]$), return \kbd{[r,zk]}, where \kbd{zk} is a
105 $\Z$-basis for the maximal order of $\Q[X]/(P)$.
106
107 \item \tet{nf_ALL}: return a vector of results of the above form, for all
108 polynomials of minimal $T_2$-norm.
109