Optimized Representation for Number Fields
William Stein
Jan 20, 2016 (part 1)
# An "ugly" number field: R.<x> = QQ[] K.<a> = NumberField(828729821457*x^3 + 92110500756/3919*x^2 + 3412589616/15358561*x - 120338256926/60190200559)
K
Number Field in a with defining polynomial 828729821457*x^3 + 92110500756/3919*x^2 + 3412589616/15358561*x - 120338256926/60190200559
show(K)
Q[a]/(828729821457a3+391992110500756a2+153585613412589616a−60190200559120338256926)
Looks messy...
L, from_L, to_L = K.optimized_representation()
show(L)
Q[a1]/(a13−2)
That's much better!
to_L(a)
1/9393*a1 - 116/12270389
from_L(L.gen())
9393*a + 348/3919
Source code of K.optimized_representation:
K.optimized_representation??
File: /projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/rings/number_field/number_field.py Source: def optimized_representation(self, names=None, both_maps=True): """ Return a field isomorphic to self with a better defining polynomial if possible, along with field isomorphisms from the new field to self and from self to the new field. EXAMPLES: We construct a compositum of 3 quadratic fields, then find an optimized representation and transform elements back and forth. :: sage: K = NumberField([x^2 + p for p in [5, 3, 2]],'a').absolute_field('b'); K Number Field in b with defining polynomial x^8 + 40*x^6 + 352*x^4 + 960*x^2 + 576 sage: L, from_L, to_L = K.optimized_representation() sage: L # your answer may different, since algorithm is random Number Field in a14 with defining polynomial x^8 + 4*x^6 + 7*x^4 + 36*x^2 + 81 sage: to_L(K.0) # random 4/189*a14^7 - 1/63*a14^6 + 1/27*a14^5 + 2/9*a14^4 - 5/27*a14^3 + 8/9*a14^2 + 3/7*a14 + 3/7 sage: from_L(L.0) # random 1/1152*a1^7 + 1/192*a1^6 + 23/576*a1^5 + 17/96*a1^4 + 37/72*a1^3 + 5/6*a1^2 + 55/24*a1 + 3/4 The transformation maps are mutually inverse isomorphisms. :: sage: from_L(to_L(K.0)) b sage: to_L(from_L(L.0)) # random a14 Number fields defined by non-monic and non-integral polynomials are supported (:trac:`252`):: sage: K.<a> = NumberField(7/9*x^3 + 7/3*x^2 - 56*x + 123) sage: K.optimized_representation() (Number Field in a1 with defining polynomial x^3 - 7*x - 7, Ring morphism: From: Number Field in a1 with defining polynomial x^3 - 7*x - 7 To: Number Field in a with defining polynomial 7/9*x^3 + 7/3*x^2 - 56*x + 123 Defn: a1 |--> 7/225*a^2 - 7/75*a - 42/25, Ring morphism: From: Number Field in a with defining polynomial 7/9*x^3 + 7/3*x^2 - 56*x + 123 To: Number Field in a1 with defining polynomial x^3 - 7*x - 7 Defn: a |--> -15/7*a1^2 + 9) """ return self.optimized_subfields(degree=self.degree(), name=names, both_maps=both_maps)[0]
K.optimized_subfields??
File: /projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/rings/number_field/number_field.py Source: def optimized_subfields(self, degree=0, name=None, both_maps=True): """ Return optimized representations of many (but *not* necessarily all!) subfields of self of the given degree, or of all possible degrees if degree is 0. EXAMPLES:: sage: K = NumberField([x^2 + p for p in [5, 3, 2]],'a').absolute_field('b'); K Number Field in b with defining polynomial x^8 + 40*x^6 + 352*x^4 + 960*x^2 + 576 sage: L = K.optimized_subfields(name='b') sage: L[0][0] Number Field in b0 with defining polynomial x - 1 sage: L[1][0] Number Field in b1 with defining polynomial x^2 - 3*x + 3 sage: [z[0] for z in L] # random -- since algorithm is random [Number Field in b0 with defining polynomial x - 1, Number Field in b1 with defining polynomial x^2 - x + 1, Number Field in b2 with defining polynomial x^4 - 5*x^2 + 25, Number Field in b3 with defining polynomial x^4 - 2*x^2 + 4, Number Field in b4 with defining polynomial x^8 + 4*x^6 + 7*x^4 + 36*x^2 + 81] We examine one of the optimized subfields in more detail:: sage: M, from_M, to_M = L[2] sage: M # random Number Field in b2 with defining polynomial x^4 - 5*x^2 + 25 sage: from_M # may be slightly random Ring morphism: From: Number Field in b2 with defining polynomial x^4 - 5*x^2 + 25 To: Number Field in a1 with defining polynomial x^8 + 40*x^6 + 352*x^4 + 960*x^2 + 576 Defn: b2 |--> -5/1152*a1^7 + 1/96*a1^6 - 97/576*a1^5 + 17/48*a1^4 - 95/72*a1^3 + 17/12*a1^2 - 53/24*a1 - 1 The to_M map is None, since there is no map from K to M:: sage: to_M We apply the from_M map to the generator of M, which gives a rather large element of `K`:: sage: from_M(M.0) # random -5/1152*a1^7 + 1/96*a1^6 - 97/576*a1^5 + 17/48*a1^4 - 95/72*a1^3 + 17/12*a1^2 - 53/24*a1 - 1 Nevertheless, that large-ish element lies in a degree 4 subfield:: sage: from_M(M.0).minpoly() # random x^4 - 5*x^2 + 25 TESTS: Number fields defined by non-monic and non-integral polynomials are supported (:trac:`252`):: sage: K.<a> = NumberField(2*x^4 + 6*x^2 + 1/2) sage: K.optimized_subfields() [ (Number Field in a0 with defining polynomial x - 1, Ring morphism: From: Number Field in a0 with defining polynomial x - 1 To: Number Field in a with defining polynomial 2*x^4 + 6*x^2 + 1/2 Defn: 1 |--> 1, None), (Number Field in a1 with defining polynomial x^2 - 2*x + 2, Ring morphism: From: Number Field in a1 with defining polynomial x^2 - 2*x + 2 To: Number Field in a with defining polynomial 2*x^4 + 6*x^2 + 1/2 Defn: a1 |--> a^3 + 7/2*a + 1, None), (Number Field in a2 with defining polynomial x^2 - 2*x + 2, Ring morphism: From: Number Field in a2 with defining polynomial x^2 - 2*x + 2 To: Number Field in a with defining polynomial 2*x^4 + 6*x^2 + 1/2 Defn: a2 |--> -a^3 - 7/2*a + 1, None), (Number Field in a3 with defining polynomial x^2 - 2, Ring morphism: From: Number Field in a3 with defining polynomial x^2 - 2 To: Number Field in a with defining polynomial 2*x^4 + 6*x^2 + 1/2 Defn: a3 |--> a^2 + 3/2, None), (Number Field in a4 with defining polynomial x^2 + 1, Ring morphism: From: Number Field in a4 with defining polynomial x^2 + 1 To: Number Field in a with defining polynomial 2*x^4 + 6*x^2 + 1/2 Defn: a4 |--> a^3 + 7/2*a, None), (Number Field in a5 with defining polynomial x^2 + 2, Ring morphism: From: Number Field in a5 with defining polynomial x^2 + 2 To: Number Field in a with defining polynomial 2*x^4 + 6*x^2 + 1/2 Defn: a5 |--> 2*a^3 + 5*a, None), (Number Field in a6 with defining polynomial x^4 + 1, Ring morphism: From: Number Field in a6 with defining polynomial x^4 + 1 To: Number Field in a with defining polynomial 2*x^4 + 6*x^2 + 1/2 Defn: a6 |--> a^3 + 1/2*a^2 + 5/2*a + 3/4, Ring morphism: From: Number Field in a with defining polynomial 2*x^4 + 6*x^2 + 1/2 To: Number Field in a6 with defining polynomial x^4 + 1 Defn: a |--> -1/2*a6^3 + a6^2 - 1/2*a6) ] """ return self._subfields_helper(degree=degree,name=name, both_maps=both_maps,optimize=True)
K._subfields_helper??
File: /projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/rings/number_field/number_field.py Source: def _subfields_helper(self, degree=0, name=None, both_maps=True, optimize=False): """ Internal function: common code for optimized_subfields() and subfields(). TESTS: Let's make sure embeddings are being respected:: sage: K.<a> = NumberField(x^4 - 23, embedding=50) sage: K, CDF(a) (Number Field in a with defining polynomial x^4 - 23, 2.1899387030948425) sage: Ss = K.subfields(); len(Ss) # indirect doctest 3 sage: diffs = [ S.coerce_embedding()(S.gen()) - CDF(S_into_K(S.gen())) for S, S_into_K, _ in Ss ] sage: all(abs(diff) < 1e-5 for diff in diffs) True sage: L1, _, _ = K.subfields(2)[0]; L1, CDF(L1.gen()) # indirect doctest (Number Field in a0 with defining polynomial x^2 - 23, -4.795831523312721) If we take a different embedding of the large field, we get a different embedding of the degree 2 subfield:: sage: K.<a> = NumberField(x^4 - 23, embedding=-50) sage: L2, _, _ = K.subfields(2)[0]; L2, CDF(L2.gen()) # indirect doctest (Number Field in a0 with defining polynomial x^2 - 23, -4.795831523312721) Test for :trac:`7695`:: sage: F = CyclotomicField(7) sage: K = F.subfields(3)[0][0] sage: K Number Field in zeta7_0 with defining polynomial x^3 + x^2 - 2*x - 1 """ if name is None: name = self.variable_names() name = normalize_names(1, name)[0] try: return self.__subfields[name, degree, both_maps, optimize] except AttributeError: self.__subfields = {} except KeyError: pass f = self.pari_polynomial() if optimize: v = f.polred(2) elts = v[0] polys = v[1] else: v = f.nfsubfields(degree) elts = [x[1] for x in v] polys = [x[0] for x in v] R = self.polynomial_ring() embedding = None ans = [] for i in range(len(elts)): f = R(polys[i]) if not (degree == 0 or f.degree() == degree): continue a = self(elts[i], check=False) if self.coerce_embedding() is not None: embedding = self.coerce_embedding()(a) # trac 7695 add a _ to prevent zeta70 etc. if name[-1].isdigit(): new_name= name+ '_' + str(i) else: new_name = name + str(i) K = NumberField(f, names=new_name, embedding=embedding) from_K = K.hom([a]) # check=False here ?? would be safe unless there are bugs. if both_maps and K.degree() == self.degree(): g = K['x'](self.polynomial()) v = g.roots() a = from_K(K.gen()) for i in range(len(v)): r = g.roots()[i][0] to_K = self.hom([r]) # check=False here ?? if to_K(a) == K.gen(): break else: to_K = None ans.append((K, from_K, to_K)) ans = Sequence(ans, immutable=True, cr=ans!=[]) self.__subfields[name, degree, both_maps, optimize] = ans return ans