This is NoetherNormalization.info, produced by Macaulay2, version 1.21

NoetherNormalization -- routines related to Noether normalization
*****************************************************************

Description
===========

NoetherNormalization is a package for computing ring homomorphisms which will
place ideals in Noether normal position. The algorithms used are based on
algorithms found in A. Logar's paper: A Computational Proof of the Noether
Normalization Lemma. In: Proceedings 6th AAEEC, Lecture Notes in Computer
Science 357, Springer, 1989, 259-273.

Authors
=======

  * Bart Snapp (see http://www.math.ohio-state.edu/~snapp/ )
    <snapp@math.ohio-state.edu>
  * Nathaniel Stapleton <nstaple2@math.uiuc.edu>

Version
=======

This documentation describes version 0.9.3 of NoetherNormalization.

Source code
===========

The source code from which this documentation is derived is in the file
NoetherNormalization.m2 (see common/share/Macaulay2/NoetherNormalization.m2 ).

Exports
=======

  * Functions and commands
      * noetherNormalization -- data for Noether
        normalization
  * Methods
      * "noetherNormalization(Ideal)" -- see noetherNormalization,
        -- data for Noether normalization
      * "noetherNormalization(PolynomialRing)" -- see
        noetherNormalization, -- data for Noether
        normalization
      * "noetherNormalization(QuotientRing)" -- see noetherNormalization,
        -- data for Noether normalization
  * Symbols
      * "LimitList" -- see noetherNormalization, --
        data for Noether normalization
      * "RandomRange" -- see noetherNormalization,
        -- data for Noether normalization

For the programmer
==================

The object NoetherNormalization, is a package (Macaulay2Doc).

noetherNormalization -- data for Noether normalization
******************************************************

Synopsis
========

  * Usage:
        (f,J,X) = noetherNormalization C
  * Inputs:
      * C, which is either an ideal (Macaulay2Doc), I, or a
        quotient ring (Macaulay2Doc), R/I where R is a
        polynomial ring (Macaulay2Doc),
      * BasisElementLimit (Macaulay2Doc)
      * will take
  * Optional inputs (Macaulay2Doc),:
      * LimitList => a list (Macaulay2Doc), default value {5, 20,
        40, 60, 80, infinity}, gives the value which
      * RandomRange => an integer (Macaulay2Doc), default value 0, if
        not 0, gives a integer bound for the random coefficients. If 0, then
        chooses random elements from the coefficient field.
      * Verbose => ..., default value false
  * Outputs:
      * f, a ring map (Macaulay2Doc), an automorphism of R
      * J, an ideal (Macaulay2Doc), the image of I under f
      * X, a list (Macaulay2Doc), a list of variables which are
        algebraically independent in R/J

Description
===========

The computations performed in the routine noetherNormalization use a random
linear change of coordinates, hence one should expect the output to change each
time the routine is executed.
+-----------------------------------------------------------------------------+
|i1 : R = QQ[x_1..x_4];                                                       |
+-----------------------------------------------------------------------------+
|i2 : I = ideal(x_2^2+x_1*x_2+1, x_1*x_2*x_3*x_4+1);                          |
|                                                                             |
|o2 : Ideal of R                                                              |
+-----------------------------------------------------------------------------+
|i3 : (f,J,X) = noetherNormalization I                                        |
|                                                                             |
|                  9     9             1     1                      13 2      |
|o3 = (map (R, R, {-x  + -x  + x , x , -x  + -x  + x , x }), ideal (--x  +    |
|                  4 1   2 2    4   1  2 1   2 2    3   2            4 1      |
|     ------------------------------------------------------------------------|
|     9                 9 3     27 2 2   9   3   9 2       9   2     1 2      |
|     -x x  + x x  + 1, -x x  + --x x  + -x x  + -x x x  + -x x x  + -x x x  +|
|     2 1 2    1 4      8 1 2    8 1 2   4 1 2   4 1 2 3   2 1 2 3   2 1 2 4  |
|     ------------------------------------------------------------------------|
|     1   2                                                                   |
|     -x x x  + x x x x  + 1), {x , x })                                      |
|     2 1 2 4    1 2 3 4         4   3                                        |
|                                                                             |
|o3 : Sequence                                                                |
+-----------------------------------------------------------------------------+
The next example shows how when we use the lexicographical ordering, we can see
the integrality of R/ f I over the polynomial ring in dim(R/I) variables:
+-----------------------------------------------------------------------------+
|i4 : R = QQ[x_1..x_5, MonomialOrder => Lex];                                 |
+-----------------------------------------------------------------------------+
|i5 : I = ideal(x_2*x_1-x_5^3, x_5*x_1^3);                                    |
|                                                                             |
|o5 : Ideal of R                                                              |
+-----------------------------------------------------------------------------+
|i6 : (f,J,X) = noetherNormalization I                                        |
|                                                                             |
|                  3                  7     3         7     3                 |
|o6 = (map (R, R, {-x  + x  + x , x , -x  + -x  + x , -x  + -x  + x , x }),   |
|                  4 1    2    5   1  4 1   4 2    4  9 1   2 2    3   2      |
|     ------------------------------------------------------------------------|
|            3 2                  3  27 3     27 2 2   27 2       9   3       |
|     ideal (-x  + x x  + x x  - x , --x x  + --x x  + --x x x  + -x x  +     |
|            4 1    1 2    1 5    2  64 1 2   16 1 2   16 1 2 5   4 1 2       |
|     ------------------------------------------------------------------------|
|     9   2     9     2    4     3       2 2      3                           |
|     -x x x  + -x x x  + x  + 3x x  + 3x x  + x x ), {x , x , x })           |
|     2 1 2 5   4 1 2 5    2     2 5     2 5    2 5     5   4   3             |
|                                                                             |
|o6 : Sequence                                                                |
+-----------------------------------------------------------------------------+
|i7 : transpose gens gb J                                                     |
|                                                                             |
|o7 = {-10} | x_2^10                                                          |
|     {-10} | 12x_1x_2x_5^6-54x_2^9x_5-12x_2^9+27x_2^8x_5^2+12x_2^8x_5-9x_2^7x|
|     {-9}  | 48x_1x_2^2x_5^3-108x_1x_2x_5^5+48x_1x_2x_5^4+486x_2^9-243x_2^8x_|
|     {-9}  | 384x_1x_2^3+864x_1x_2^2x_5^2+768x_1x_2^2x_5+2916x_1x_2x_5^5-648x|
|     {-3}  | 3x_1^2+4x_1x_2+4x_1x_5-4x_2^3                                   |
|     ------------------------------------------------------------------------|
|                                                                             |
|     _5^3-12x_2^7x_5^2+12x_2^6x_5^3-12x_2^5x_5^4+12x_2^4x_5^5+16x_2          |
|     5-36x_2^8+81x_2^7x_5^2+72x_2^7x_5-108x_2^6x_5^2+108x_2^5x_5^3-          |
|     _1x_2x_5^4+576x_1x_2x_5^3+384x_1x_2x_5^2-13122x_2^9+6561x_2^8x          |
|                                                                             |
|     ------------------------------------------------------------------------|
|                                                                             |
|     ^2x_5^6+16x_2x_5^7                                                      |
|     108x_2^4x_5^4+48x_2^4x_5^3+64x_2^3x_5^3-144x_2^2x_5^5+128x_2^2x_5^4-144x|
|     _5+1458x_2^8-2187x_2^7x_5^2-2430x_2^7x_5+216x_2^7+2916x_2^6x_5^2-648x_2^|
|                                                                             |
|     ------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|     _2x_5^6+64x_2x_5^5                                                      |
|     6x_5-288x_2^6-2916x_2^5x_5^3+648x_2^5x_5^2+288x_2^5x_5+384x_2^5+2916x_2^|
|                                                                             |
|     ------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|                                                                             |
|     4x_5^4-648x_2^4x_5^3+576x_2^4x_5^2+384x_2^4x_5+512x_2^4+1152x_2^3x_5^2+ |
|                                                                             |
|     ------------------------------------------------------------------------|
|                                                                             |
|                                                                             |
|                                                                             |
|     1536x_2^3x_5+3888x_2^2x_5^5-864x_2^2x_5^4+1920x_2^2x_5^3+1536x_2^2x_5^2+|
|                                                                             |
|     ------------------------------------------------------------------------|
|                                                      |                      |
|                                                      |                      |
|                                                      |                      |
|     3888x_2x_5^6-864x_2x_5^5+768x_2x_5^4+512x_2x_5^3 |                      |
|                                                      |                      |
|                                                                             |
|             5       1                                                       |
|o7 : Matrix R  <--- R                                                        |
+-----------------------------------------------------------------------------+
If noetherNormalization is unable to place the ideal into the desired position
after a few tries, the following warning is given:
+----------------------------------------------------------------------+
|i8 : R = ZZ/2[a,b];                                                   |
+----------------------------------------------------------------------+
|i9 : I = ideal(a^2*b+a*b^2+1);                                        |
|                                                                      |
|o9 : Ideal of R                                                       |
+----------------------------------------------------------------------+
|i10 : (f,J,X) = noetherNormalization I                                |
|--warning: no good linear transformation found by noetherNormalization|
|                                                                      |
|                                  2       2                           |
|o10 = (map (R, R, {b, a}), ideal(a b + a*b  + 1), {b})                |
|                                                                      |
|o10 : Sequence                                                        |
+----------------------------------------------------------------------+
Here is an example with the option Verbose => true:
+-----------------------------------------------------------------------------+
|i11 : R = QQ[x_1..x_4];                                                      |
+-----------------------------------------------------------------------------+
|i12 : I = ideal(x_2^2+x_1*x_2+1, x_1*x_2*x_3*x_4+1);                         |
|                                                                             |
|o12 : Ideal of R                                                             |
+-----------------------------------------------------------------------------+
|i13 : (f,J,X) = noetherNormalization(I,Verbose => true)                      |
|--trying random transformation: 1                                            |
|--trying with basis element limit: 5                                         |
|--trying with basis element limit: 20                                        |
|                                                                             |
|                          7             3     7                        2     |
|o13 = (map (R, R, {7x  + --x  + x , x , -x  + -x  + x , x }), ideal (8x  +   |
|                     1   10 2    4   1  7 1   3 2    3   2             1     |
|      -----------------------------------------------------------------------|
|       7                   3     499 2 2   49   3     2        7   2         |
|      --x x  + x x  + 1, 3x x  + ---x x  + --x x  + 7x x x  + --x x x  +     |
|      10 1 2    1 4        1 2    30 1 2   30 1 2     1 2 3   10 1 2 3       |
|      -----------------------------------------------------------------------|
|      3 2       7   2                                                        |
|      -x x x  + -x x x  + x x x x  + 1), {x , x })                           |
|      7 1 2 4   3 1 2 4    1 2 3 4         4   3                             |
|                                                                             |
|o13 : Sequence                                                               |
+-----------------------------------------------------------------------------+
The first number in the output above gives the number of linear transformations
performed by the routine while attempting to place I into the desired position.
The second number tells which BasisElementLimit (Macaulay2Doc),
was used when computing the (partial) Groebner
basis. By default, noetherNormalization tries to use a partial Groebner basis.
It does this by sequentially computing a Groebner basis with the option
BasisElementLimit (Macaulay2Doc), set to predetermined
values. The default values come from the following
list:{5,20,40,60,80,infinity}. To set the values manually, use the option
LimitList:
+-----------------------------------------------------------------------------+
|i14 : R = QQ[x_1..x_4];                                                      |
+-----------------------------------------------------------------------------+
|i15 : I = ideal(x_2^2+x_1*x_2+1, x_1*x_2*x_3*x_4+1);                         |
|                                                                             |
|o15 : Ideal of R                                                             |
+-----------------------------------------------------------------------------+
|i16 : (f,J,X) = noetherNormalization(I,Verbose => true,LimitList => {5,10})  |
|--trying random transformation: 1                                            |
|--trying with basis element limit: 5                                         |
|--trying with basis element limit: 10                                        |
|                                                                             |
|                   2     5                  6                      5 2       |
|o16 = (map (R, R, {-x  + -x  + x , x , x  + -x  + x , x }), ideal (-x  +     |
|                   3 1   2 2    4   1   1   7 2    3   2           3 1       |
|      -----------------------------------------------------------------------|
|      5                 2 3     43 2 2   15   3   2 2       5   2      2     |
|      -x x  + x x  + 1, -x x  + --x x  + --x x  + -x x x  + -x x x  + x x x  |
|      2 1 2    1 4      3 1 2   14 1 2    7 1 2   3 1 2 3   2 1 2 3    1 2 4 |
|      -----------------------------------------------------------------------|
|        6   2                                                                |
|      + -x x x  + x x x x  + 1), {x , x })                                   |
|        7 1 2 4    1 2 3 4         4   3                                     |
|                                                                             |
|o16 : Sequence                                                               |
+-----------------------------------------------------------------------------+
To limit the randomness of the coefficients, use the option RandomRange. Here
is an example where the coefficients of the linear transformation are random
integers from -2 to 2:
+-----------------------------------------------------------------------------+
|i17 : R = QQ[x_1..x_4];                                                      |
+-----------------------------------------------------------------------------+
|i18 : I = ideal(x_2^2+x_1*x_2+1, x_1*x_2*x_3*x_4+1);                         |
|                                                                             |
|o18 : Ideal of R                                                             |
+-----------------------------------------------------------------------------+
|i19 : (f,J,X) = noetherNormalization(I,Verbose => true,RandomRange => 2)     |
|--trying random transformation: 1                                            |
|--trying with basis element limit: 5                                         |
|--trying with basis element limit: 20                                        |
|                                                                             |
|                                                              2              |
|o19 = (map (R, R, {2x  - x  + x , x , x  + x , x }), ideal (3x  - x x  + x x |
|                     1    2    4   1   2    3   2             1    1 2    1 4|
|      -----------------------------------------------------------------------|
|             2 2      3     2          2        2                            |
|      + 1, 2x x  - x x  + 2x x x  - x x x  + x x x  + x x x x  + 1), {x ,    |
|             1 2    1 2     1 2 3    1 2 3    1 2 4    1 2 3 4         4     |
|      -----------------------------------------------------------------------|
|      x })                                                                   |
|       3                                                                     |
|                                                                             |
|o19 : Sequence                                                               |
+-----------------------------------------------------------------------------+

This symbol is provided by the package NoetherNormalization.

Ways to use noetherNormalization :
==================================

  * "noetherNormalization(Ideal)"
  * "noetherNormalization(PolynomialRing)"
  * "noetherNormalization(QuotientRing)"

For the programmer
==================

The object noetherNormalization, is a method function with options (Macaulay2Doc).