source: sage/rings/polynomial/multi_polynomial_ring_generic.pyx @ 6374:e7f77b443129

Revision 6374:e7f77b443129, 16.7 KB checked in by William Stein <wstein@…>, 6 years ago (diff)

more algebraic number theory work.
Line 
1include '../../ext/stdsage.pxi'
2
3from sage.structure.parent_gens cimport ParentWithGens
4import sage.misc.latex
5import multi_polynomial_ideal
6from term_order import TermOrder
7from sage.rings.integer_ring import ZZ
8from sage.rings.polynomial.polydict import PolyDict
9import multi_polynomial_element
10import polynomial_ring
11
12def is_MPolynomialRing(x):
13    return bool(PY_TYPE_CHECK(x, MPolynomialRing_generic))
14
15cdef class MPolynomialRing_generic(sage.rings.ring.CommutativeRing):
16    def __init__(self, base_ring, n, names, order):
17        order = TermOrder(order,n)
18        if not isinstance(base_ring, sage.rings.ring.CommutativeRing):
19            raise TypeError, "Base ring must be a commutative ring."
20        n = int(n)
21        if n < 0:
22            raise ValueError, "Multivariate Polynomial Rings must " + \
23                  "have more than 0 variables."
24        self.__ngens = n
25        self.__term_order = order
26        self._has_singular = False #cannot convert to Singular by default
27        ParentWithGens.__init__(self, base_ring, names)
28
29    def is_integral_domain(self):
30        """
31        EXAMPLES:
32            sage: ZZ['x,y'].is_integral_domain()
33            True
34            sage: Integers(8)['x,y'].is_integral_domain()
35            False
36        """
37        return self.base_ring().is_integral_domain()
38
39    def is_noetherian(self):
40        """
41        EXAMPLES:
42            sage: ZZ['x,y'].is_noetherian()
43            True
44            sage: Integers(8)['x,y'].is_noetherian()
45            True
46        """
47        return self.base_ring().is_noetherian()
48       
49    def construction(self):
50        """
51        Returns a functor F and basering R such that F(R) == self.
52
53        In the multi-variate case, R is a polynomial ring with one
54        less variable, and F knows to adjoin the variable in the
55        correct way.
56       
57        EXAMPLES:
58            sage: S = ZZ['x,y']
59            sage: F, R = S.construction(); R
60            Univariate Polynomial Ring in x over Integer Ring
61            sage: F(R) == S
62            True
63            sage: F(R) == ZZ['x']['y']
64            False
65           
66        """
67        from sage.rings.polynomial.polynomial_ring import PolynomialRing
68        from sage.categories.pushout import PolynomialFunctor
69        vars = self.variable_names()
70        if len(vars) == 1:
71            return PolynomialFunctor(vars[0], False), self.base_ring()
72        else:
73            return PolynomialFunctor(vars[-1], True), PolynomialRing(self.base_ring(), vars[:-1])
74           
75    def completion(self, p, prec=20, extras=None):
76        try:
77            from sage.rings.power_series_ring import PowerSeriesRing
78            return PowerSeriesRing(self.remove_var(p), p, prec)
79        except ValueError:
80            raise TypeError, "Cannot complete %s with respect to %s" % (self, p)
81           
82    def remove_var(self, var):
83        vars = list(self.variable_names())
84        vars.remove(str(var))
85        from sage.rings.polynomial.polynomial_ring import PolynomialRing
86        return PolynomialRing(self.base_ring(), vars)
87           
88    cdef _coerce_c_impl(self, x):
89        """
90        Return the canonical coercion of x to this multivariate
91        polynomial ring, if one is defined, or raise a TypeError.
92
93        The rings that canonically coerce to this polynomial ring are:
94            * this ring itself
95            * polynomial rings in the same variables over any base ring that
96              canonically coerces to the base ring of this ring
97            * polynomial rings in a subset of the variables over any base ring that
98              canonically coerces to the base ring of this ring
99            * any ring that canonically coerces to the base ring of this
100              polynomial ring.
101
102        TESTS:
103        This fairly complicated code (from Michel Vandenbergh) ends up
104        imlicitly calling _coerce_c_impl:
105            sage: z = polygen(QQ, 'z')
106            sage: W.<s>=NumberField(z^2+1)
107            sage: Q.<u,v,w> = W[]
108            sage: W1 = FractionField (Q)
109            sage: S.<x,y,z> = W1[]
110            sage: u + x
111            x + u
112            sage: x + 1/u
113            x + 1/u
114        """
115        try:
116            P = x.parent()
117            # polynomial rings in the same variable over the any base that coerces in:
118            if is_MPolynomialRing(P):
119                if P.variable_names() == self.variable_names():
120                    if self.has_coerce_map_from(P.base_ring()):
121                        return self(x)
122                elif self.base_ring().has_coerce_map_from(P._mpoly_base_ring(self.variable_names())):
123                    return self(x)
124                   
125            elif polynomial_ring.is_PolynomialRing(P):
126                if P.variable_name() in self.variable_names():
127                    if self.has_coerce_map_from(P.base_ring()):
128                        return self(x)
129                       
130        except AttributeError:
131            pass
132
133        # any ring that coerces to the base ring of this polynomial ring.
134        return self._coerce_try(x, [self.base_ring()])
135       
136    def _extract_polydict(self, x):
137        """
138        Assuming other_vars is a subset of self.variable_names(),
139        convert the dict of ETuples with respect to other_vars to
140        a dict with respect to self.variable_names()
141        """
142        # This is probably horribly innefficient
143        from polydict import ETuple
144        other_vars = list(x.parent().variable_names())
145        name_mapping = [(other_vars.index(var) if var in other_vars else -1) for var in self.variable_names()]
146        K = self.base_ring()
147        D = {}
148        var_range = range(len(self.variable_names()))
149        for ix, a in x.dict().iteritems():
150            ix = ETuple([0 if name_mapping[t] == -1 else ix[name_mapping[t]] for t in var_range])
151            D[ix] = K(a)
152        return D
153
154    def __richcmp__(left, right, int op):
155        return (<ParentWithGens>left)._richcmp(right, op)
156   
157    cdef int _cmp_c_impl(left, Parent right) except -2:
158        if not is_MPolynomialRing(right):
159            return cmp(type(left),type(right))
160        else:
161            return cmp((left.base_ring(), left.__ngens, left.variable_names(), left.__term_order),
162                       (right.base_ring(), (<MPolynomialRing_generic>right).__ngens, right.variable_names(), (<MPolynomialRing_generic>right).__term_order))
163
164    def __contains__(self, x):
165        """
166        This definition of containment does not involve a natural
167        inclusion from rings with less variables into rings with more.
168        """
169        try:
170            return x.parent() == self
171        except AttributeError:
172            return False
173
174    def _repr_(self):
175        return "Polynomial Ring in %s over %s"%(", ".join(self.variable_names()), self.base_ring())
176
177    def _latex_(self):
178        vars = str(self.latex_variable_names()).replace('\n','').replace("'",'')
179        return "%s[%s]"%(sage.misc.latex.latex(self.base_ring()), vars[1:-1])
180
181
182    def _ideal_class_(self):
183        return multi_polynomial_ideal.MPolynomialIdeal
184   
185    def _is_valid_homomorphism_(self, codomain, im_gens):
186        try:
187            # all that is needed is that elements of the base ring
188            # of the polynomial ring canonically coerce into codomain.
189            # Since poly rings are free, any image of the gen
190            # determines a homomorphism
191            codomain._coerce_(self.base_ring()(1))
192        except TypeError:
193            return False
194        return True
195
196    def _magma_(self, magma=None):
197        """
198        Used in converting this ring to the corresponding ring in MAGMA.
199
200        EXAMPLES:
201            sage: R.<y,z,w> = PolynomialRing(QQ,3)
202            sage: magma(R) # optional
203            Polynomial ring of rank 3 over Rational Field
204            Graded Reverse Lexicographical Order
205            Variables: y, z, w
206
207            sage: magma(PolynomialRing(GF(7),4, 'x')) #optional
208            Polynomial ring of rank 4 over GF(7)
209            Graded Reverse Lexicographical Order
210            Variables: x0, x1, x2, x3
211
212            sage: magma(PolynomialRing(GF(49,'a'),10, 'x')) #optional
213            Polynomial ring of rank 10 over GF(7^2)
214            Graded Reverse Lexicographical Order
215            Variables: x0, x1, x2, x3, x4, x5, x6, x7, x8, x9
216
217            sage: magma(PolynomialRing(ZZ['a,b,c'],3, 'x')) #optional
218            Polynomial ring of rank 3 over Polynomial ring of rank 3 over Integer Ring
219            Graded Reverse Lexicographical Order
220            Variables: x0, x1, x2
221        """
222        if magma == None:
223            import sage.interfaces.magma
224            magma = sage.interfaces.magma.magma
225       
226        try:
227            if self.__magma is None:
228                raise AttributeError
229            m = self.__magma
230            m._check_valid()
231            if not m.parent() is magma:
232                raise ValueError
233            return m
234        except (AttributeError,ValueError):
235            B = magma(self.base_ring())
236            R = magma('PolynomialRing(%s, %s, %s)'%(B.name(), self.ngens(),self.term_order().magma_str()))
237            R.assign_names(self.variable_names())
238            self.__magma = R
239            return R
240
241    def _magma_init_(self):
242        """
243        Return a string representation of self MAGMA can understand.
244        """
245        try: # we need that for GF(q) arithmetic
246            B = self.base_ring()._magma_().name()
247        except (RuntimeError,TypeError):
248            B = self.base_ring()._magma_init_()
249        R = 'PolynomialRing(%s, %s, %s)'%(B, self.ngens(),self.term_order().magma_str())
250        return R
251   
252    def is_finite(self):
253        if self.ngens() == 0:
254            return self.base_ring().is_finite()
255        return False
256   
257    def is_field(self):
258        """
259        Return True if this multivariate polynomial ring is a field, i.e.,
260        it is a ring in 0 generators over a field.
261        """
262        if self.ngens() == 0:
263            return self.base_ring().is_field()
264        return False
265
266    def term_order(self):
267        return self.__term_order
268
269    def characteristic(self):
270        """
271        Return the characteristic of this polynomial ring.
272
273        EXAMPLES:
274            sage: R = MPolynomialRing(QQ, 'x', 3)
275            sage: R.characteristic()
276            0
277            sage: R = MPolynomialRing(GF(7),'x', 20)
278            sage: R.characteristic()
279            7
280        """
281        return self.base_ring().characteristic()
282
283    def gen(self, n=0):
284        if n < 0 or n >= self.__ngens:
285            raise ValueError, "Generator not defined."
286        return self._gens[int(n)]
287
288    def gens(self):
289        return self._gens
290       
291    def variable_names_recursive(self, depth=sage.rings.infinity.infinity):
292        r"""
293        Returns the list of variable names of this and its baserings, as if
294        it were a single multi-variate polynomial.
295       
296        EXAMPLES:
297            sage: R = QQ['x,y']['z,w']
298            sage: R.variable_names_recursive()
299            ('x', 'y', 'z', 'w')
300            sage: R.variable_names_recursive(3)
301            ('y', 'z', 'w')
302
303        """
304        if depth <= 0:
305            all = ()
306        elif depth == 1:
307            all = self.variable_names()
308        else:
309            my_vars = self.variable_names()
310            try:
311               all = self.base_ring().variable_names_recursive(depth - len(my_vars)) + my_vars
312            except AttributeError:
313                all = my_vars
314        if len(all) > depth:
315            all = all[-depth:]
316        return all
317
318    def _mpoly_base_ring(self, vars=None):
319        """
320        Returns the basering if this is viewed as a polynomial ring over vars.
321        See also MPolynomial._mpoly_dict_recursive
322        """
323        if vars is None:
324            vars = self.variable_names_recursive()
325        vars = list(vars)
326        my_vars = list(self.variable_names())
327        if vars == list(my_vars):
328            return self.base_ring()
329        elif not my_vars[-1] in vars:
330            return self
331        elif not set(my_vars).issubset(set(vars)):
332            while my_vars[-1] in vars:
333                my_vars.pop()
334            from polynomial_ring_constructor import PolynomialRing
335            return PolynomialRing(self.base_ring(), my_vars)
336        else:
337            try:
338                return self.base_ring()._mpoly_base_ring(vars[:vars.index(my_vars[0])])
339            except AttributeError:
340                return self.base_ring()
341
342
343    def krull_dimension(self):
344        return self.base_ring().krull_dimension() + self.ngens()
345
346    def ngens(self):
347        return self.__ngens
348
349    def _monomial_order_function(self):
350        raise NotImplementedError
351
352    def latex_variable_names(self):
353        """
354        Returns the list of variable names suitable for latex output.
355
356        All '_SOMETHING' substrings are replaced by '_{SOMETHING}' recursively
357        so that subscripts of subscripts work.
358
359        EXAMPLES:
360            sage: R, x = PolynomialRing(QQ,'x',12).objgens()
361            sage: x
362            (x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11)
363            sage: print R.latex_variable_names ()
364            ['x_{0}', 'x_{1}', 'x_{2}', 'x_{3}', 'x_{4}', 'x_{5}', 'x_{6}', 'x_{7}', 'x_{8}', 'x_{9}', 'x_{10}', 'x_{11}']
365            sage: f = x[0]^3 + 15/3 * x[1]^10
366            sage: print latex(f)
367            5 x_{1}^{10} + x_{0}^{3}
368        """
369        if self._latex_names is not None:
370            return self._latex_names
371        names = []
372        for g in self.variable_names():
373            i = len(g)-1
374            while i >= 0 and g[i].isdigit():
375                i -= 1
376            if i < len(g)-1:
377                g = '%s_{%s}'%(g[:i+1], g[i+1:])
378            names.append(g)
379        self._latex_names = names
380        return names
381
382    def __reduce__(self):
383        """
384        """
385
386        base_ring = self.base_ring()
387        n = self.ngens()
388        names = self.variable_names()
389        order = self.term_order()
390       
391        return unpickle_MPolynomialRing_generic_v1,(base_ring, n, names, order)
392
393
394    def random_element(self, degree=2, terms=5, *args, **kwds):
395        r"""
396        Return a random polynomial in this polynomial ring.
397       
398        INPUT:
399            degree -- maximum total degree of resulting polynomial
400            terms  -- maximum number of terms to generate
401
402        OUTPUT: a random polynomial of total degree \code{degree}
403                and with \code{term} terms in it.
404
405        EXAMPLES:
406            sage: [QQ['x,y'].random_element() for _ in range(5)]
407            [-1/14*x*y + 1/2*x, x*y + x - y + 1, 3*x*y + x - 1/2, 1/3*x*y - 5*x + 1/2*y + 7/6, 2*x*y + 1/2*x + 1]
408            sage: R = MPolynomialRing(ZZ, 'x,y',2 );
409            sage: R.random_element(2)          # random
410            -1*x*y + x + 15*y - 2
411            sage: R.random_element(12)         # random
412            x^4*y^5 + x^3*y^5 + 6*x^2*y^2 - x^2
413            sage: R.random_element(12,3)       # random
414            -3*x^4*y^2 - x^5 - x^4*y
415            sage: R.random_element(3)          # random
416            2*y*z + 2*x + 2*y
417
418            sage: R.<x,y> = MPolynomialRing(RR)
419            sage: R.random_element(2)          # random
420            -0.645358174399450*x*y + 0.572655401740132*x + 0.197478565033010
421
422            sage: R.random_element(41)         # random
423            -4*x^6*y^4*z^4*a^6*b^3*c^6*d^5 + 1/2*x^4*y^3*z^5*a^4*c^5*d^6 - 5*x^3*z^3*a^6*b^4*c*d^5 + 10*x^2*y*z^5*a^4*b^2*c^3*d^4 - 5*x^3*y^5*z*b^2*c^5*d
424
425        AUTHOR:
426            -- didier deshommes
427        """
428        # General strategy:
429        # generate n-tuples of numbers with each element in the tuple
430        # not greater than  (degree/n) so that the degree
431        # (ie, the sum of the elements in the tuple) does not exceed
432        # their total degree
433       
434        n = self.__ngens         # length of the n-tuple
435        max_deg = int(degree/n)  # max degree for each term
436        R = self.base_ring()
437       
438        # restrict exponents to positive integers only
439        exponents = [ tuple([ZZ.random_element(0,max_deg+1) for _ in range(n)])
440                       for _ in range(terms) ]
441        coeffs = []
442        for _ in range(terms):
443            c = R.random_element(*args,**kwds)
444            while not c:
445                c = R.random_element(*args,**kwds)
446            coeffs.append(c) # allow only nonzero coefficients
447
448        d = dict( zip(tuple(exponents), coeffs) )
449        return self(multi_polynomial_element.MPolynomial_polydict(self, PolyDict(d)))
450       
451       
452####################
453# Leave *all* old versions!
454
455def unpickle_MPolynomialRing_generic_v1(base_ring, n, names, order):
456    from sage.rings.polynomial.multi_polynomial_ring import MPolynomialRing
457    return MPolynomialRing(base_ring, n, names=names, order=order)
458
459
460def unpickle_MPolynomialRing_generic(base_ring, n, names, order):
461    from sage.rings.polynomial.multi_polynomial_ring import MPolynomialRing
462   
463    return MPolynomialRing(base_ring, n, names=names, order=order)
Note: See TracBrowser for help on using the repository browser.