r"""
Ideals of commutative rings.
Sage provides functionality for computing with ideals. One can create
an ideal in any commutative or non-commutative ring `R` by giving a
list of generators, using the notation ``R.ideal([a,b,...])``. The case
of non-commutative rings is implemented in :mod:`~sage.rings.noncommutative_ideals`.
A more convenient notation may be ``R*[a,b,...]`` or ``[a,b,...]*R``.
If `R` is non-commutative, the former creates a left and the latter
a right ideal, and ``R*[a,b,...]*R`` creates a two-sided ideal.
"""
from types import GeneratorType
import sage.misc.latex as latex
import sage.rings.ring
import commutative_ring
from sage.structure.element import MonoidElement
from sage.interfaces.singular import singular as singular_default
import sage.rings.infinity
from sage.structure.sequence import Sequence
def Ideal(*args, **kwds):
r"""
Create the ideal in ring with given generators.
There are some shorthand notations for creating an ideal, in
addition to using the Ideal function::
-- R.ideal(gens, coerce=True)
-- gens*R
-- R*gens
INPUT:
- ``R (optional)`` - a ring (if not given, will try to
infer it from gens)
- ``gens`` - list of elements generating the ideal
- ``coerce (optional)`` - bool (default: True);
whether gens need to be coerced into ring.
OUTPUT: The ideal of ring generated by gens.
EXAMPLES::
sage: R, x = PolynomialRing(ZZ, 'x').objgen()
sage: I = R.ideal([4 + 3*x + x^2, 1 + x^2])
sage: I
Ideal (x^2 + 3*x + 4, x^2 + 1) of Univariate Polynomial Ring in x over Integer Ring
sage: Ideal(R, [4 + 3*x + x^2, 1 + x^2])
Ideal (x^2 + 3*x + 4, x^2 + 1) of Univariate Polynomial Ring in x over Integer Ring
sage: Ideal((4 + 3*x + x^2, 1 + x^2))
Ideal (x^2 + 3*x + 4, x^2 + 1) of Univariate Polynomial Ring in x over Integer Ring
::
sage: ideal(x^2-2*x+1, x^2-1)
Ideal (x^2 - 2*x + 1, x^2 - 1) of Univariate Polynomial Ring in x over Integer Ring
sage: ideal([x^2-2*x+1, x^2-1])
Ideal (x^2 - 2*x + 1, x^2 - 1) of Univariate Polynomial Ring in x over Integer Ring
sage: l = [x^2-2*x+1, x^2-1]
sage: ideal(f^2 for f in l)
Ideal (x^4 - 4*x^3 + 6*x^2 - 4*x + 1, x^4 - 2*x^2 + 1) of
Univariate Polynomial Ring in x over Integer Ring
This example illustrates how Sage finds a common ambient ring for
the ideal, even though 1 is in the integers (in this case).
::
sage: R.<t> = ZZ['t']
sage: i = ideal(1,t,t^2)
sage: i
Ideal (1, t, t^2) of Univariate Polynomial Ring in t over Integer Ring
sage: ideal(1/2,t,t^2)
Principal ideal (1) of Univariate Polynomial Ring in t over Rational Field
This shows that the issues at trac #1104 are resolved::
sage: Ideal(3, 5)
Principal ideal (1) of Integer Ring
sage: Ideal(ZZ, 3, 5)
Principal ideal (1) of Integer Ring
sage: Ideal(2, 4, 6)
Principal ideal (2) of Integer Ring
You have to provide enough information that Sage can figure out
which ring to put the ideal in.
::
sage: I = Ideal([])
Traceback (most recent call last):
...
ValueError: unable to determine which ring to embed the ideal in
sage: I = Ideal()
Traceback (most recent call last):
...
ValueError: need at least one argument
Note that some rings use different ideal implementations than the standard, even if they are PIDs.::
sage: R.<x> = GF(5)[]
sage: I = R*(x^2+3)
sage: type(I)
<class 'sage.rings.polynomial.ideal.Ideal_1poly_field'>
You can also pass in a specific ideal type::
sage: from sage.rings.ideal import Ideal_pid
sage: I = Ideal(x^2+3,ideal_class=Ideal_pid)
sage: type(I)
<class 'sage.rings.ideal.Ideal_pid'>
TESTS::
sage: R, x = PolynomialRing(ZZ, 'x').objgen()
sage: I = R.ideal([4 + 3*x + x^2, 1 + x^2])
sage: I == loads(dumps(I))
True
::
sage: I = Ideal(R, [4 + 3*x + x^2, 1 + x^2])
sage: I == loads(dumps(I))
True
::
sage: I = Ideal((4 + 3*x + x^2, 1 + x^2))
sage: I == loads(dumps(I))
True
This shows that the issue at trac ticket #5477 is fixed::
sage: R.<x> = QQ[]
sage: I = R.ideal([x + x^2])
sage: J = R.ideal([2*x + 2*x^2])
sage: J
Principal ideal (x^2 + x) of Univariate Polynomial Ring in x over Rational Field
sage: S = R.quotient_ring(I)
sage: U = R.quotient_ring(J)
sage: I == J
True
sage: S == U
True
"""
if len(args) == 0:
raise ValueError, "need at least one argument"
if len(args) == 1 and args[0] == []:
raise ValueError, "unable to determine which ring to embed the ideal in"
first = args[0]
if not isinstance(first, sage.rings.ring.Ring):
if isinstance(first, Ideal_generic) and len(args) == 1:
R = first.ring()
gens = first.gens()
else:
if isinstance(first, (list, tuple, GeneratorType)) and len(args) == 1:
gens = first
else:
gens = args
gens = Sequence(gens)
R = gens.universe()
else:
R = first
gens = args[1:]
if not commutative_ring.is_CommutativeRing(R):
raise TypeError, "R must be a commutative ring"
return R.ideal(*gens, **kwds)
def is_Ideal(x):
r"""
Returns True if object is an ideal of a ring.
EXAMPLES:
A simple example involving the ring of integers. Note
that Sage does not interpret rings objects themselves as ideals.
However, one can still explicitly construct these ideals::
sage: from sage.rings.ideal import is_Ideal
sage: R = ZZ
sage: is_Ideal(R)
False
sage: 1*R; is_Ideal(1*R)
Principal ideal (1) of Integer Ring
True
sage: 0*R; is_Ideal(0*R)
Principal ideal (0) of Integer Ring
True
Sage recognizes ideals of polynomial rings as well::
sage: R = PolynomialRing(QQ, 'x'); x = R.gen()
sage: I = R.ideal(x^2 + 1); I
Principal ideal (x^2 + 1) of Univariate Polynomial Ring in x over Rational Field
sage: is_Ideal(I)
True
sage: is_Ideal((x^2 + 1)*R)
True
"""
return isinstance(x, Ideal_generic)
class Ideal_generic(MonoidElement):
"""
An ideal.
"""
def __init__(self, ring, gens, coerce=True):
self.__ring = ring
if not isinstance(gens, (list, tuple)):
gens = [gens]
if coerce:
gens = [ring(x) for x in gens]
gens = tuple(gens)
if len(gens)==0: gens=(ring.zero_element(),)
self.__gens = gens
MonoidElement.__init__(self, ring.ideal_monoid())
def _repr_short(self):
"""
Represent the list of generators.
EXAMPLE::
sage: P.<a,b,c> = QQ[]
sage: P*[a^2,a*b+c,c^3]
Ideal (a^2, a*b + c, c^3) of Multivariate Polynomial Ring in a, b, c over Rational Field
sage: (P*[a^2,a*b+c,c^3])._repr_short()
'(a^2, a*b + c, c^3)'
If the string representation of a generator contains a line break,
the generators are not represented from left to right but from
top to bottom. This is the case, e.g., for matrices::
sage: MS = MatrixSpace(QQ,2,2)
sage: MS*[MS.1,2]
Left Ideal
(
[0 1]
[0 0],
<BLANKLINE>
[2 0]
[0 2]
)
of Full MatrixSpace of 2 by 2 dense matrices over Rational Field
"""
L = []
has_return = False
for x in self.gens():
s = repr(x)
if '\n' in s:
has_return = True
s = s.replace('\n','\n ')
L.append(s)
if has_return:
return '\n(\n %s\n)\n'%(',\n\n '.join(L))
return '(%s)'%(', '.join(L))
def __repr__(self):
return "Ideal %s of %s"%(self._repr_short(), self.ring())
def __cmp__(self, other):
S = set(self.gens())
T = set(other.gens())
if S == T:
return 0
return cmp(self.gens(), other.gens())
def __contains__(self, x):
try:
return self._contains_(self.__ring(x))
except TypeError:
return False
def _contains_(self, x):
raise NotImplementedError
def __nonzero__(self):
r"""
Return True if this ideal is not (0).
TESTS::
sage: I = ZZ.ideal(5)
sage: bool(I)
True
::
sage: I = ZZ['x'].ideal(0)
sage: bool(I)
False
::
sage: I = ZZ['x'].ideal(ZZ['x'].gen()^2)
sage: bool(I)
True
::
sage: I = QQ['x', 'y'].ideal(0)
sage: bool(I)
False
"""
for g in self.gens():
if not g.is_zero():
return True
return False
def base_ring(self):
r"""
Returns the base ring of this ideal.
EXAMPLES::
sage: R = ZZ
sage: I = 3*R; I
Principal ideal (3) of Integer Ring
sage: J = 2*I; J
Principal ideal (6) of Integer Ring
sage: I.base_ring(); J.base_ring()
Integer Ring
Integer Ring
We construct an example of an ideal of a quotient ring::
sage: R = PolynomialRing(QQ, 'x'); x = R.gen()
sage: I = R.ideal(x^2 - 2)
sage: I.base_ring()
Rational Field
And p-adic numbers::
sage: R = Zp(7, prec=10); R
7-adic Ring with capped relative precision 10
sage: I = 7*R; I
Principal ideal (7 + O(7^11)) of 7-adic Ring with capped relative precision 10
sage: I.base_ring()
7-adic Ring with capped relative precision 10
"""
return self.ring().base_ring()
def apply_morphism(self, phi):
r"""
Apply the morphism ``phi`` to every element of this ideal.
Returns an ideal in the domain of ``phi``.
EXAMPLES::
sage: psi = CC['x'].hom([-CC['x'].0])
sage: J = ideal([CC['x'].0 + 1]); J
Principal ideal (x + 1.00000000000000) of Univariate Polynomial Ring in x over Complex Field with 53 bits of precision
sage: psi(J)
Principal ideal (x - 1.00000000000000) of Univariate Polynomial Ring in x over Complex Field with 53 bits of precision
sage: J.apply_morphism(psi)
Principal ideal (x - 1.00000000000000) of Univariate Polynomial Ring in x over Complex Field with 53 bits of precision
::
sage: psi = ZZ['x'].hom([-ZZ['x'].0])
sage: J = ideal([ZZ['x'].0, 2]); J
Ideal (x, 2) of Univariate Polynomial Ring in x over Integer Ring
sage: psi(J)
Ideal (-x, 2) of Univariate Polynomial Ring in x over Integer Ring
sage: J.apply_morphism(psi)
Ideal (-x, 2) of Univariate Polynomial Ring in x over Integer Ring
TESTS::
sage: K.<a> = NumberField(x^2 + 1)
sage: A = K.ideal(a)
sage: taus = K.embeddings(K)
sage: A.apply_morphism(taus[0]) # identity
Fractional ideal (a)
sage: A.apply_morphism(taus[1]) # complex conjugation
Fractional ideal (-a)
sage: A.apply_morphism(taus[0]) == A.apply_morphism(taus[1])
True
::
sage: K.<a> = NumberField(x^2 + 5)
sage: B = K.ideal([2, a + 1]); B
Fractional ideal (2, a + 1)
sage: taus = K.embeddings(K)
sage: B.apply_morphism(taus[0]) # identity
Fractional ideal (2, a + 1)
Since 2 is totally ramified, complex conjugation fixes it::
sage: B.apply_morphism(taus[1]) # complex conjugation
Fractional ideal (2, a + 1)
sage: taus[1](B)
Fractional ideal (2, a + 1)
"""
from sage.categories.morphism import is_Morphism
if not is_Morphism(phi):
raise TypeError, "phi must be a morphism"
return phi(self)
def _latex_(self):
return '\\left(%s\\right)%s'%(", ".join([latex.latex(g) for g in \
self.gens()]),
latex.latex(self.ring()))
def ring(self):
"""
Returns the ring containing this ideal.
EXAMPLES::
sage: R = ZZ
sage: I = 3*R; I
Principal ideal (3) of Integer Ring
sage: J = 2*I; J
Principal ideal (6) of Integer Ring
sage: I.ring(); J.ring()
Integer Ring
Integer Ring
Note that ``self.ring()`` is different from
``self.base_ring()``
::
sage: R = PolynomialRing(QQ, 'x'); x = R.gen()
sage: I = R.ideal(x^2 - 2)
sage: I.base_ring()
Rational Field
sage: I.ring()
Univariate Polynomial Ring in x over Rational Field
Another example using polynomial rings::
sage: R = PolynomialRing(QQ, 'x'); x = R.gen()
sage: I = R.ideal(x^2 - 3)
sage: I.ring()
Univariate Polynomial Ring in x over Rational Field
sage: Rbar = R.quotient(I, names='a')
sage: S = PolynomialRing(Rbar, 'y'); y = Rbar.gen(); S
Univariate Polynomial Ring in y over Univariate Quotient Polynomial Ring in a over Rational Field with modulus x^2 - 3
sage: J = S.ideal(y^2 + 1)
sage: J.ring()
Univariate Polynomial Ring in y over Univariate Quotient Polynomial Ring in a over Rational Field with modulus x^2 - 3
"""
return self.__ring
def reduce(self, f):
r"""
Return the reduction of the element of `f` modulo the ideal
`I` (=self). This is an element of `R` that is
equivalent modulo `I` to `f`.
EXAMPLES::
sage: ZZ.ideal(5).reduce(17)
2
sage: parent(ZZ.ideal(5).reduce(17))
Integer Ring
"""
return f
def gens(self):
"""
Return a set of generators / a basis of self. This is usually the
set of generators provided during object creation.
EXAMPLE::
sage: P.<x,y> = PolynomialRing(QQ,2)
sage: I = Ideal([x,y+1]); I
Ideal (x, y + 1) of Multivariate Polynomial Ring in x, y over Rational Field
sage: I.gens()
[x, y + 1]
::
sage: ZZ.ideal(5,10).gens()
(5,)
"""
return self.__gens
def gen(self, i):
"""
Return the ``i``-th generator in the current basis of this ideal.
EXAMPLE::
sage: P.<x,y> = PolynomialRing(QQ,2)
sage: I = Ideal([x,y+1]); I
Ideal (x, y + 1) of Multivariate Polynomial Ring in x, y over Rational Field
sage: I.gen(1)
y + 1
sage: ZZ.ideal(5,10).gen()
5
"""
return self.__gens[i]
def ngens(self):
"""
Return the number of generators in the basis.
EXAMPLE::
sage: P.<x,y> = PolynomialRing(QQ,2)
sage: I = Ideal([x,y+1]); I
Ideal (x, y + 1) of Multivariate Polynomial Ring in x, y over Rational Field
sage: I.ngens()
2
sage: ZZ.ideal(5,10).ngens()
1
"""
return len(self.__gens)
def gens_reduced(self):
r"""
Same as gens() for this ideal, since there is currently no special
gens_reduced algorithm implemented for this ring.
This method is provided so that ideals in ZZ have the method
gens_reduced(), just like ideals of number fields.
EXAMPLES::
sage: ZZ.ideal(5).gens_reduced()
(5,)
"""
return self.gens()
def is_maximal(self):
r"""
Returns True if the ideal is maximal in the ring containing the
ideal.
TODO: This is not implemented for many rings. Implement it!
EXAMPLES::
sage: R = ZZ
sage: I = R.ideal(7)
sage: I.is_maximal()
True
sage: R.ideal(16).is_maximal()
False
sage: S = Integers(8)
sage: S.ideal(0).is_maximal()
False
sage: S.ideal(2).is_maximal()
True
sage: S.ideal(4).is_maximal()
False
"""
from sage.rings.all import ZZ
R = self.ring()
if hasattr(R, 'cover_ring') and R.cover_ring() is ZZ:
return R.quotient(self).is_field()
kd = R.krull_dimension()
if kd == 0 or (kd == 1 and R.is_integral_domain()):
return self.is_prime()
else:
raise NotImplementedError
def is_primary(self, P=None):
r"""
Returns ``True`` if this ideal is primary (or `P`-primary, if
a prime ideal `P` is specified).
Recall that an ideal `I` is primary if and only if `I` has a
unique associated prime (see page 52 in [AtiMac]_). If this
prime is `P`, then `I` is said to be `P`-primary.
INPUT:
- ``P`` - (default: ``None``) a prime ideal in the same ring
EXAMPLES::
sage: R.<x, y> = QQ[]
sage: I = R.ideal([x^2, x*y])
sage: I.is_primary()
False
sage: J = I.primary_decomposition()[1]; J
Ideal (y, x^2) of Multivariate Polynomial Ring in x, y over Rational Field
sage: J.is_primary()
True
sage: J.is_prime()
False
Some examples from the Macaulay2 documentation::
sage: R.<x, y, z> = GF(101)[]
sage: I = R.ideal([y^6])
sage: I.is_primary()
True
sage: I.is_primary(R.ideal([y]))
True
sage: I = R.ideal([x^4, y^7])
sage: I.is_primary()
True
sage: I = R.ideal([x*y, y^2])
sage: I.is_primary()
False
NOTES: Uses the list of associated primes.
REFERENCES:
.. [AtiMac] Atiyah and Macdonald, "Introduction to commutative
algebra", Addison-Wesley, 1969.
"""
try:
ass = self.associated_primes()
except (NotImplementedError, ValueError):
raise NotImplementedError
if P is None:
return (len(ass) == 1)
else:
return (len(ass) == 1) and (ass[0] == P)
def primary_decomposition(self):
r"""
Return a decomposition of this ideal into primary ideals.
EXAMPLES::
sage: R = ZZ[x]
sage: I = R.ideal(7)
sage: I.primary_decomposition()
Traceback (most recent call last):
...
NotImplementedError
"""
raise NotImplementedError
def is_prime(self):
r"""
Returns ``True`` if the ideal is prime.
EXAMPLES::
sage: R.<x, y> = QQ[]
sage: I = R.ideal([x, y])
sage: I.is_prime() # a maximal ideal
True
sage: I = R.ideal([x^2-y])
sage: I.is_prime() # a non-maximal prime ideal
True
sage: I = R.ideal([x^2, y])
sage: I.is_prime() # a non-prime primary ideal
False
sage: I = R.ideal([x^2, x*y])
sage: I.is_prime() # a non-prime non-primary ideal
False
sage: S = Integers(8)
sage: S.ideal(0).is_prime()
False
sage: S.ideal(2).is_prime()
True
sage: S.ideal(4).is_prime()
False
Note that this method is not implemented for all rings where it
could be::
sage: R = ZZ[x]
sage: I = R.ideal(7)
sage: I.is_prime() # when implemented, should be True
Traceback (most recent call last):
...
NotImplementedError
NOTES: For general rings, uses the list of associated primes.
"""
from sage.rings.all import ZZ
R = self.ring()
if hasattr(R, 'cover_ring') and R.cover_ring() is ZZ and R.is_finite():
return self.is_maximal()
try:
ass = self.associated_primes()
except (NotImplementedError, ValueError):
raise NotImplementedError
if len(ass) <> 1:
return False
if self == ass[0]:
return True
else:
return False
def associated_primes(self):
r"""
Return the list of associated prime ideals of this ideal.
EXAMPLES::
sage: R = ZZ[x]
sage: I = R.ideal(7)
sage: I.associated_primes()
Traceback (most recent call last):
...
NotImplementedError
"""
raise NotImplementedError
def minimal_associated_primes(self):
r"""
Return the list of minimal associated prime ideals of this ideal.
EXAMPLES::
sage: R = ZZ[x]
sage: I = R.ideal(7)
sage: I.minimal_associated_primes()
Traceback (most recent call last):
...
NotImplementedError
"""
raise NotImplementedError
def embedded_primes(self):
r"""
Return the list of embedded primes of this ideal.
EXAMPLES::
sage: R.<x, y> = QQ[]
sage: I = R.ideal(x^2, x*y)
sage: I.embedded_primes()
[Ideal (y, x) of Multivariate Polynomial Ring in x, y over Rational Field]
"""
ass = self.associated_primes()
min_ass = self.minimal_associated_primes()
emb = []
for p in ass:
try:
i = min_ass.index(p)
except ValueError:
emb.append(p)
emb.sort()
return emb
def is_principal(self):
r"""
Returns ``True`` if the ideal is principal in the ring containing the
ideal.
TODO: Code is naive. Only keeps track of ideal generators as set
during initialization of the ideal. (Can the base ring change? See
example below.)
EXAMPLES::
sage: R = ZZ[x]
sage: I = R.ideal(2,x)
sage: I.is_principal()
Traceback (most recent call last):
...
NotImplementedError
sage: J = R.base_extend(QQ).ideal(2,x)
sage: J.is_principal()
True
"""
if len(self.gens()) <= 1:
return True
raise NotImplementedError
def is_trivial(self):
r"""
Return True if this ideal is (0) or (1).
TESTS::
sage: I = ZZ.ideal(5)
sage: I.is_trivial()
False
::
sage: I = ZZ['x'].ideal(-1)
sage: I.is_trivial()
True
::
sage: I = ZZ['x'].ideal(ZZ['x'].gen()^2)
sage: I.is_trivial()
False
::
sage: I = QQ['x', 'y'].ideal(-5)
sage: I.is_trivial()
True
::
sage: I = CC['x'].ideal(0)
sage: I.is_trivial()
True
"""
if self.is_zero():
return True
if self.is_principal():
return self.gens()[0].is_unit()
for g in self.gens():
if g.is_unit():
return True
raise NotImplementedError
def category(self):
"""
Return the category of this ideal.
EXAMPLES:
Note that category is dependent on the ring of the
ideal.
::
sage: I = ZZ.ideal(7)
sage: J = ZZ[x].ideal(7,x)
sage: K = ZZ[x].ideal(7)
sage: I.category()
Category of ring ideals in Integer Ring
sage: J.category()
Category of ring ideals in Univariate Polynomial Ring in x
over Integer Ring
sage: K.category()
Category of ring ideals in Univariate Polynomial Ring in x
over Integer Ring
"""
import sage.categories.all
return sage.categories.all.Ideals(self.__ring)
def __add__(self, other):
if not isinstance(other, Ideal_generic):
other = self.ring().ideal(other)
return self.ring().ideal(self.gens() + other.gens())
def __radd__(self, other):
if not isinstance(other, Ideal_generic):
other = self.ring().ideal(other)
return self.ring().ideal(self.gens() + other.gens())
def __mul__(self, other):
"""
EXAMPLE::
sage: P.<x,y,z> = QQ[]
sage: I = [x*y+y*z,x^2+x*y-y*x-y^2]*P
sage: I*2 # indirect doctest
Ideal (2*x*y + 2*y*z, 2*x^2 - 2*y^2) of Multivariate Polynomial Ring in x, y, z over Rational Field
"""
if not isinstance(other, Ideal_generic):
try:
if self.ring().has_coerce_map_from(other):
return self
except (TypeError,ArithmeticError,ValueError):
pass
other = self.ring().ideal(other)
return self.ring().ideal([z for z in [x*y for x in self.gens() for y in other.gens()] if z])
def __rmul__(self, other):
"""
EXAMPLE::
sage: P.<x,y,z> = QQ[]
sage: I = [x*y+y*z,x^2+x*y-y*x-y^2]*P
sage: [2]*I # indirect doctest
Ideal (2*x*y + 2*y*z, 2*x^2 - 2*y^2) of Multivariate Polynomial Ring in x, y, z over Rational Field
"""
if not isinstance(other, Ideal_generic):
try:
if self.ring().has_coerce_map_from(other):
return self
except (TypeError,ArithmeticError,ValueError):
pass
other = self.ring().ideal(other)
return self.ring().ideal([z for z in [y*x for x in self.gens() for y in other.gens()] if z])
def norm(self):
"""
Returns the norm of this ideal.
In the general case, this is just the ideal itself, since the ring it lies in can't be implicitly assumed to be an extension of anything.
We include this function for compatibility with cases such as ideals in number fields.
EXAMPLES::
sage: R.<t> = GF(8, names='a')[]
sage: I = R.ideal(t^4 + t + 1)
sage: I.norm()
Principal ideal (t^4 + t + 1) of Univariate Polynomial Ring in t over Finite Field in a of size 2^3
"""
return self
def absolute_norm(self):
"""
Returns the absolute norm of this ideal.
In the general case, this is just the ideal itself, since the ring it lies in can't be implicitly assumed to be an extension of anything.
We include this function for compatibility with cases such as ideals in number fields.
EXAMPLES::
sage: R.<t> = GF(9, names='a')[]
sage: I = R.ideal(t^4 + t + 1)
sage: I.norm()
Principal ideal (t^4 + t + 1) of Univariate Polynomial Ring in t over Finite Field in a of size 3^2
"""
class Ideal_principal(Ideal_generic):
"""
A principal ideal.
"""
def __repr__(self):
return "Principal ideal (%s) of %s"%(self.gen(), self.ring())
def is_principal(self):
r"""
Returns True if the ideal is principal in the ring containing the
ideal. When the ideal construction is explicitly principal (i.e.
when we define an ideal with one element) this is always the case.
EXAMPLES:
Note that Sage automatically coerces ideals into
principal ideals during initialization::
sage: R = ZZ[x]
sage: I = R.ideal(x)
sage: J = R.ideal(2,x)
sage: K = R.base_extend(QQ).ideal(2,x)
sage: I
Principal ideal (x) of Univariate Polynomial Ring in x
over Integer Ring
sage: J
Ideal (2, x) of Univariate Polynomial Ring in x over Integer Ring
sage: K
Principal ideal (1) of Univariate Polynomial Ring in x
over Rational Field
sage: I.is_principal()
True
sage: K.is_principal()
True
"""
return True
def gen(self):
r"""
Returns the generator of the principal ideal. The generators are
elements of the ring containing the ideal.
EXAMPLES:
A simple example in the integers::
sage: R = ZZ
sage: I = R.ideal(7)
sage: J = R.ideal(7, 14)
sage: I.gen(); J.gen()
7
7
Note that the generator belongs to the ring from which the ideal
was initialized::
sage: R = ZZ[x]
sage: I = R.ideal(x)
sage: J = R.base_extend(QQ).ideal(2,x)
sage: a = I.gen(); a
x
sage: b = J.gen(); b
1
sage: a.base_ring()
Integer Ring
sage: b.base_ring()
Rational Field
"""
return self.gens()[0]
def __contains__(self, x):
"""
Returns True if x is in the ideal self.
EXAMPLES::
sage: P.<x> = PolynomialRing(ZZ)
sage: I = P.ideal(x^2-2)
sage: x^2 in I
False
sage: x^2-2 in I
True
sage: x^2-3 in I
False
"""
if self.gen().is_zero():
return x.is_zero()
return self.gen().divides(x)
def __cmp__(self, other):
if not isinstance(other, Ideal_generic):
other = self.ring().ideal(other)
if not other.is_principal():
return -1
if self.is_zero():
if not other.is_zero():
return -1
return 0
g0 = other.gen()
g1 = self.gen()
if g0.divides(g1) and g1.divides(g0):
return 0
return 1
def divides(self, other):
"""
Returns True if self divides other.
EXAMPLES::
sage: P.<x> = PolynomialRing(QQ)
sage: I = P.ideal(x)
sage: J = P.ideal(x^2)
sage: I.divides(J)
True
sage: J.divides(I)
False
"""
if isinstance(other, Ideal_principal):
return self.gen().divides(other.gen())
raise NotImplementedError
class Ideal_pid(Ideal_principal):
"""
An ideal of a principal ideal domain.
"""
def __init__(self, ring, gen):
Ideal_principal.__init__(self, ring, gen)
def __add__(self, other):
if not isinstance(other, Ideal_generic):
other = self.ring().ideal(other)
return self.ring().ideal(self.gcd(other))
def reduce(self, f):
"""
Return the reduction of f modulo self.
EXAMPLES::
sage: I = 8*ZZ
sage: I.reduce(10)
2
sage: n = 10; n.mod(I)
2
"""
f = self.ring()(f)
if self.gen() == 0:
return f
q, r = f.quo_rem(self.gen())
return r
def gcd(self, other):
r"""
Returns the greatest common divisor of the principal ideal with the
ideal ``other``; that is, the largest principal ideal
contained in both the ideal and ``other``
TODO: This is not implemented in the case when
``other`` is neither principal nor when the generator
of ``self`` is contained in ``other``.
Also, it seems that this class is used only in PIDs--is this
redundant? Note: second example is broken.
EXAMPLES:
An example in the principal ideal domain ZZ::
sage: R = ZZ
sage: I = R.ideal(42)
sage: J = R.ideal(70)
sage: I.gcd(J)
Principal ideal (14) of Integer Ring
sage: J.gcd(I)
Principal ideal (14) of Integer Ring
TESTS:
We cannot take the gcd of a principal ideal with a
non-principal ideal as well: ( gcd(I,J) should be (7) )
::
sage: I = ZZ.ideal(7)
sage: J = ZZ[x].ideal(7,x)
sage: I.gcd(J)
Traceback (most recent call last):
...
NotImplementedError
sage: J.gcd(I)
Traceback (most recent call last):
...
AttributeError: 'Ideal_generic' object has no attribute 'gcd'
Note::
sage: type(I)
<class 'sage.rings.ideal.Ideal_pid'>
sage: type(J)
<class 'sage.rings.ideal.Ideal_generic'>
"""
if isinstance(other, Ideal_principal):
return self.ring().ideal(self.gen().gcd(other.gen()))
elif self.gen() in other:
return other
else:
raise NotImplementedError
def is_prime(self):
"""
Returns True if the ideal is prime. This relies on the ring
elements having a method is_irreducible() implemented, since an
ideal (a) is prime iff a is irreducible (or 0)
EXAMPLES::
sage: ZZ.ideal(2).is_prime()
True
sage: ZZ.ideal(-2).is_prime()
True
sage: ZZ.ideal(4).is_prime()
False
sage: ZZ.ideal(0).is_prime()
True
sage: R.<x>=QQ[]
sage: P=R.ideal(x^2+1); P
Principal ideal (x^2 + 1) of Univariate Polynomial Ring in x over Rational Field
sage: P.is_prime()
True
"""
if self.is_zero():
return True
g = self.gen()
if hasattr(g, 'is_irreducible'):
return g.is_irreducible()
raise NotImplementedError
def is_maximal(self):
"""
Returns whether this ideal is maximal.
Principal ideal domains have Krull dimension 1 (or 0), so an ideal is maximal if and only if it's prime (and nonzero if the ring is not a field).
EXAMPLES::
sage: R.<t> = GF(5)[]
sage: p = R.ideal(t^2 + 2)
sage: p.is_maximal()
True
sage: p = R.ideal(t^2 + 1)
sage: p.is_maximal()
False
sage: p = R.ideal(0)
sage: p.is_maximal()
False
sage: p = R.ideal(1)
sage: p.is_maximal()
False
"""
if not self.ring().is_field() and self.is_zero():
return False
return self.is_prime()
def residue_field(self):
"""
Return the residue class field of this ideal, which must be prime.
TODO: Implement this for more general rings. Currently only defined
for ZZ and for number field orders.
EXAMPLES::
sage: P = ZZ.ideal(61); P
Principal ideal (61) of Integer Ring
sage: F = P.residue_field(); F
Residue field of Integers modulo 61
sage: pi = F.reduction_map(); pi
Partially defined reduction map:
From: Rational Field
To: Residue field of Integers modulo 61
sage: pi(123/234)
6
sage: pi(1/61)
Traceback (most recent call last):
...
ZeroDivisionError: Cannot reduce rational 1/61 modulo 61: it has negative valuation
sage: lift = F.lift_map(); lift
Lifting map:
From: Residue field of Integers modulo 61
To: Integer Ring
sage: lift(F(12345/67890))
33
sage: (12345/67890) % 61
33
TESTS::
sage: ZZ.ideal(96).residue_field()
Traceback (most recent call last):
...
ValueError: The ideal (Principal ideal (96) of Integer Ring) is not prime
::
sage: R.<x>=QQ[]
sage: I=R.ideal(x^2+1)
sage: I.is_prime()
True
sage: I.residue_field()
Traceback (most recent call last):
...
TypeError: residue fields only supported for polynomial rings over finite fields.
"""
if not self.is_prime():
raise ValueError, "The ideal (%s) is not prime"%self
from sage.rings.integer_ring import ZZ
if self.ring() is ZZ:
return ZZ.residue_field(self, check = False)
raise NotImplementedError, "residue_field() is only implemented for ZZ and rings of integers of number fields."
class Ideal_fractional(Ideal_generic):
def __repr__(self):
return "Fractional ideal %s of %s"%(self._repr_short(), self.ring())
def Cyclic(R, n=None, homog=False, singular=singular_default):
"""
Ideal of cyclic n-roots from 1-st n variables of R if R is
coercible to Singular. If n==None n is set to R.ngens()
INPUT:
- ``R`` - base ring to construct ideal for
- ``n`` - number of cyclic roots (default: None)
- ``homog`` - if True a homogeneous ideal is returned
using the last variable in the ideal (default: False)
- ``singular`` - singular instance to use
.. note::
R will be set as the active ring in Singular
EXAMPLES:
An example from a multivariate polynomial ring over the
rationals::
sage: P.<x,y,z> = PolynomialRing(QQ,3,order='lex')
sage: I = sage.rings.ideal.Cyclic(P)
sage: I
Ideal (x + y + z, x*y + x*z + y*z, x*y*z - 1) of Multivariate Polynomial
Ring in x, y, z over Rational Field
sage: I.groebner_basis()
[x + y + z, y^2 + y*z + z^2, z^3 - 1]
We compute a Groebner basis for cyclic 6, which is a standard
benchmark and test ideal::
sage: R.<x,y,z,t,u,v> = QQ['x,y,z,t,u,v']
sage: I = sage.rings.ideal.Cyclic(R,6)
sage: B = I.groebner_basis()
sage: len(B)
45
"""
from rational_field import RationalField
if n:
if n > R.ngens():
raise ArithmeticError, "n must be <= R.ngens()"
else:
n = R.ngens()
singular.lib("poly")
R2 = R.change_ring(RationalField())
R2._singular_().set_ring()
if not homog:
I = singular.cyclic(n)
else:
I = singular.cyclic(n).homog(R2.gen(n-1))
return R2.ideal(I).change_ring(R)
def Katsura(R, n=None, homog=False, singular=singular_default):
"""
n-th katsura ideal of R if R is coercible to Singular. If n==None n
is set to R.ngens()
INPUT:
- ``R`` - base ring to construct ideal for
- ``n`` - which katsura ideal of R
- ``homog`` - if True a homogeneous ideal is returned
using the last variable in the ideal (default: False)
- ``singular`` - singular instance to use
EXAMPLES::
sage: P.<x,y,z> = PolynomialRing(QQ,3)
sage: I = sage.rings.ideal.Katsura(P,3); I
Ideal (x + 2*y + 2*z - 1, x^2 + 2*y^2 + 2*z^2 - x, 2*x*y + 2*y*z - y)
of Multivariate Polynomial Ring in x, y, z over Rational Field
::
sage: Q.<x> = PolynomialRing(QQ,1)
sage: J = sage.rings.ideal.Katsura(Q,1); J
Ideal (x - 1) of Multivariate Polynomial Ring in x over Rational Field
"""
from rational_field import RationalField
if n:
if n > R.ngens():
raise ArithmeticError, "n must be <= R.ngens()."
else:
n = R.ngens()
singular.lib("poly")
R2 = R.change_ring(RationalField())
R2._singular_().set_ring()
if not homog:
I = singular.katsura(n)
else:
I = singular.katsura(n).homog(R2.gen(n-1))
return R2.ideal(I).change_ring(R)
def FieldIdeal(R):
"""
Let q = R.base_ring().order() and (x0,...,x_n) = R.gens() then if
q is finite this constructor returns
`< x_0^q - x_0, ... , x_n^q - x_n >.`
We call this ideal the field ideal and the generators the field
equations.
EXAMPLES:
The Field Ideal generated from the polynomial ring over
two variables in the finite field of size 2::
sage: P.<x,y> = PolynomialRing(GF(2),2)
sage: I = sage.rings.ideal.FieldIdeal(P); I
Ideal (x^2 + x, y^2 + y) of Multivariate Polynomial Ring in x, y over
Finite Field of size 2
Another, similar example::
sage: Q.<x1,x2,x3,x4> = PolynomialRing(GF(2^4,name='alpha'), 4)
sage: J = sage.rings.ideal.FieldIdeal(Q); J
Ideal (x1^16 + x1, x2^16 + x2, x3^16 + x3, x4^16 + x4) of
Multivariate Polynomial Ring in x1, x2, x3, x4 over Finite
Field in alpha of size 2^4
"""
q = R.base_ring().order()
if q is sage.rings.infinity.infinity:
raise TypeError, "Cannot construct field ideal for R.base_ring().order()==infinity"
return R.ideal([x**q - x for x in R.gens() ])
