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