Commutative Algebra Module

ness01 edited this page Apr 11, 2012 · 7 revisions

This page aims to document the vision and, to a lesser extent, the usage of a commutative algebra module I am currently working on.

Introduction

Let's begin by defining some terms. First of all, "commutative algebra" here means: computational aspects of the study of commutative unital rings and their modules. The question then is, what rings? What modules? For this I shall be using the term "constructed", which is going to be recursively defined later. So the commutative algebra module will work with "constructed" modules and "constructed" rings. It aims to, for such modules, "construct" various operations of commutative algebra. For example, the tensor product of two constructed modules can be constructed, etc.

"Axioms" for construction

  • Any field implemented in the polys module is constructed, as a ring.
  • If K is a constructed field and O is a monomial order on x_1, ..., x_n, then the ring associated to O in K(x_1, ..., x_n) is constructed.
  • If a ring R is constructed, then so is any free module of finite rank over it.
  • If a module M is constructed, so is any finitely generated submodule by giving generators.
  • If a module M and a submodule N are constructed, then so is their quotient module.
  • If a ring R and an ideal I are constructed (ideal constructed as a module), then so is the quotient ring R/I.

Some remarks: being associated to O means that the ring consists of fractions where the denominator as leading monomial O. Hence in particular K[x_1, ..., x_n] is constructed, and so are certain localisations of it. It is easy to see that all constructed rings are Noetherian, and a module over a constructed ring is constructed iff it is finitely presented with explicit generators.

Examples and use cases

The most basic question in computational commutative algebra is submodule membership: if M is a constructed module and N is a (constructed) submodule, given (x \in M), decide if (x \in N). (This can be done by groebner basis computations.) Even this most basic question can be formidable to impossible to do by hand: what is the smallest power of (x) that is contained in the ideal ((x^5-y^5, y^5-z^5, z^5-x^5, x^4y + x^4z + y^4*z))? This can be tested as follows (this is currently very slow - my groebner basis code is crappy):

>>> R = QQ[x, y, z]
>>> I = R.ideal(x**5 - y**5, y**5-z**5, z**5-x**5, x**4*y + x**4*z + y**4*z)
>>> I.contains(x**12)
False
>>> I.contains(x**13)
True

The more general question if any power of (x) is contained in (I) and can be answered by ideal saturation (not yet implemented).


Another example is homological algebra: using groebner bases, free resoltions of constructed modules can be computed to any desired length. This in turn allows computation of left derived functors, like Ext and Tor. Also the free resolutions contain much information in themselves, and can be inspected in detail using pager_print.

The starting point of homologyical algebra is presenting modules via generators and relations. Suppose M is generated by f_1, ..., f_n over the ring R. Consider the homomorphism (\phi: R^n \to M), given by sending ((r_1, \dots, r_n) \to r_1 f_1 + \dots + r_n f_n). The syzygy module is defined to be the kernel of (\phi).

The syzygy module is zero iff the generators generate freely a free submodule:

>>> from sympy.abc import x
>>> from sympy import QQ
>>> QQ[x].free_module(2).submodule([1, 0], [1, 1]).syzygy_module().is_zero()
True

A slightly more interesting example:

>>> M = QQ[x, y].free_module(2).submodule([x, 2*], [y, 2*y])
>>> M.syzygy_module()
<y, -x>

It may not be (immediately) obvious how to (it is not to me), but using syzygies and groebner basis one can solve an extension of the submodule membership problem: express an element of a submodule in terms of specific generators. For example:

>>> R = QQ[x, y, z]
>>> I = R.ideal(x+y+z, x*y + x*z + y*z, x*y*z)
>>> I.contains(x**3)
True
>>> I.in_terms_of_generators(x**3)

(\left[ x^{2} - x y - x z - y z, y + z, 1\right])

And indeed:

>>> expand(sum(a*b for a, b in zip([x**2 - x*y - x*z - y*z, y+z, 1], [x+y+z, x*y+x*z+y*z, x*y*z])))
x**3

A common construction in commutative algebra is to take quotients. Currently, quotient rings of polynomial rings are implemented. For example, the field obtained by adjoining a square root of minus one to (\mathbb{Q}) is (\mathbb{Q}(i) \approx \mathbb{Q}[x]/(x^2 + 1)). We can directly compute in this ring:

>>> Qi = QQ[x]/[x**2 + 1]
>>> i = Qi.convert(x)
>>> i
x + <x**2 + 1>

Note the convenience notation for quotient rings: QQ[x]/[x**2 + 1] is sugar for QQ[x].quotient_ring(QQ[x].ideal(x**2+1)).

In this ring, computations can be carried out like in the rest of sympy:

>>> i**4
1 + <x**2 + 1>
>>> 1/(1 + i)
-x/2 + 1/2 + <x**2 + 1>
>>> 1/(1 + i**2)
NotReversible: 0 + <x**2 + 1> not a unit in QQ[x]/<x**2 + 1>

As you see, most of the time objects are automatically converted to the ring. One notable exception is equality comparison. Here the object has to be converted by hand, there are a couple of ways of doing this:

>>> i**2 == -1             # This does not work
False
>>> i**2 == i - 1 - i      # Sneaky!
True
>>> i**2 == Qi(-1)         # Works only for ints
True
>>> i**2 == Qi.convert(-1) # Works in general
True
>>> I = Qi.ideal
>>> i**2 == -1 + I         # "mathematical" notation
True

Of course, all this works over general base fields and in arbitrarily many variables.


Continuing the idea of quotients, we may also consider quotient modules. For example, let (R = \mathbb{Q}[x, y]), F the free module of rank two over R, N the submodule generated by (1, x) and (x, y), and M the quotient module. This can be expressed as follows:

>>> R = QQ[x,y]
>>> F = R.free_module(2)
>>> N = F.submodule([1, x], [x, y])
>>> M = F/N

A shorthand similar to ideals can also be used:

>>> M == F/[(1, x), (x, y)]
True

All the things you can do with "ordinary" modules you can also do with quotients. A few examples:

>>> F.convert([1 + x, x + y]) == 0
False
>>> M.convert([1 + x, x + y]) == 0
True
>>> S = M.submodule([1, 0])
>>> S.contains([0, x])
True
>>> S.in_terms_of_generators([0, x])
[-1]
>>> S.contains([x, 1])
False

To be continued.

What now?

The real aim of all of this is to be able to do computational algebraic geometry. However, this is still a long way away.

Another interesting direction is to extend the code to work over ground PIDs, not fields. This is a part of groebner basis theory which is less well known, but also quite interesting because of its applications to algebraic number theory / arithmetic scheme theory.

Clone this wiki locally
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.