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

RationalPoints2 -- Find the rational points on a variety
********************************************************

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

RationalPoints2 is a package for enumerating rational points on a variety
defined by an ideal of a polynomial ring. The main function is
rationalPoints. Over a finite field it will list all the
rational points. Over a number field it can find all points of a 0-dimensional
ideal in its splitting field, and all points with bounded height for a positive
dimensional ideal. The package also provides some utility functions related to
field extensions, which allow the computation of rational points with
prescribed coefficient field.

An example over a finite field.

+-----------------------------------------------------------------------------+
|i1 : ZZ/2[x,y,z]; rationalPoints(ideal(y^2*z+y*z^2-x^3-x*z^2),               |
|                                                                             |
|o2 = {(1 : 0 : 1), (1 : 1 : 1), (0 : 1 : 0), (0 : 1 : 1), (0 :               |
|                                                                             |
|o2 : List                                                                    |
|-----------------------------------------------------------------------------|
|Projective=>true)                                                            |
|                                                                             |
|0 : 1)}                                                                      |
+-----------------------------------------------------------------------------+

An example over a number field: we enumerate the rational points on the unit
circle with bounded height.

+-----------------------------------------------------------------------------+
|i3 : QQ[x,y]; rationalPoints(ideal(x^2+y^2-1), Bound=>5)                     |
|                                                                             |
|                                         3    4      3    4    4    3      4 |
|o4 = {{0, -1}, {1, 0}, {-1, 0}, {0, 1}, {-, - -}, {- -, - -}, {-, - -}, {- -,|
|                                         5    5      5    5    5    5      5 |
|     ------------------------------------------------------------------------|
|       3    4  3      4  3    3  4      3  4                                 |
|     - -}, {-, -}, {- -, -}, {-, -}, {- -, -}}                               |
|       5    5  5      5  5    5  5      5  5                                 |
|                                                                             |
|o4 : List                                                                    |
+-----------------------------------------------------------------------------+

And an example of a 0-dimensional ideal.

+-----------------------------------------------------------------------------+
|i5 : QQ[x,y]; I = ideal(x^2+1,y^2-2);                                        |
|                                                                             |
|o6 : Ideal of QQ[x..y]                                                       |
+-----------------------------------------------------------------------------+
|i7 : rationalPoints(I, Verbose=>true)                                        |
|-- the following polynomials do not split                                    |
|   -- x^2-2                                                                  |
|                                                                             |
|o7 = {}                                                                      |
|                                                                             |
|o7 : List                                                                    |
+-----------------------------------------------------------------------------+
|i8 : rationalPoints(I, Split=>true, Verbose=>true)                           |
|-- base change to the field QQ[a]/(a^2-2)                                    |
|-- base change to the field QQ[a]/(a^4-2*a^2+9)                              |
|                                                                             |
|       1 3   1   1 3   5       1 3   1   1 3   5     1 3   1     1 3   5     |
|o8 = {{-a  + -a, -a  - -a}, {- -a  - -a, -a  - -a}, {-a  + -a, - -a  + -a},  |
|       6     6   6     6       6     6   6     6     6     6     6     6     |
|     ------------------------------------------------------------------------|
|        1 3   1     1 3   5                                                  |
|     {- -a  - -a, - -a  + -a}}                                               |
|        6     6     6     6                                                  |
|                                                                             |
|o8 : List                                                                    |
+-----------------------------------------------------------------------------+

Caveat
======

Currently the functionality of positive dimensional ideals over number fields
other than QQ depends on Sage (an algorithm by Doyle–Krumm for enumerating
field elements with bounded height).

Author
======

  * Jieao Song <jieao.song@imj-prg.fr>

Version
=======

This documentation describes version 0.5 of RationalPoints2.

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

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

Exports
=======

  * Types
      * ProjectivePoint -- Class of a projective point
  * Functions and commands
      * baseChange -- Perform base change for field
        extensions
      * charpoly -- Characteristic and minimal polynomials
        over the prime field
      * "minpoly" -- see charpoly, -- Characteristic and
        minimal polynomials over the prime field
      * extField -- Define field extensions
      * "setPariSize" -- see extField, -- Define field
        extensions
      * "splittingField" -- see extField, -- Define field
        extensions
      * globalHeight -- Multiplicative height function
      * hermiteNormalForm -- Compute the Hermite
        normal form of a fractional ideal in a number field
      * integers -- Compute a basis for the integers of a
        number field
      * rationalPoints -- Find the rational points on a
        variety
      * zeros -- List the zeros of a polynomial
  * Methods
      * "baseChange(InexactFieldFamily,Number)" -- see baseChange,
        -- Perform base change for field extensions
      * "baseChange(InexactFieldFamily,RingElement)" -- see baseChange,
        -- Perform base change for field extensions
      * "baseChange(Number,Ideal)" -- see baseChange, --
        Perform base change for field extensions
      * "baseChange(Number,Number)" -- see baseChange, --
        Perform base change for field extensions
      * "baseChange(Number,RingElement)" -- see baseChange,
        -- Perform base change for field extensions
      * "baseChange(Ring,Ideal)" -- see baseChange, --
        Perform base change for field extensions
      * "baseChange(Ring,Number)" -- see baseChange, --
        Perform base change for field extensions
      * "baseChange(Ring,RingElement)" -- see baseChange, --
        Perform base change for field extensions
      * "charpoly(Number)" -- see charpoly, -- Characteristic
        and minimal polynomials over the prime field
      * "charpoly(RingElement)" -- see charpoly, --
        Characteristic and minimal polynomials over the prime field
      * "minpoly(Number)" -- see charpoly, -- Characteristic
        and minimal polynomials over the prime field
      * "minpoly(Ring)" -- see charpoly, -- Characteristic and
        minimal polynomials over the prime field
      * "minpoly(RingElement)" -- see charpoly, --
        Characteristic and minimal polynomials over the prime field
      * "extField(List)" -- see extField, -- Define field
        extensions
      * "extField(Ring,List)" -- see extField, -- Define field
        extensions
      * "extField(Ring,RingElement)" -- see extField, -- Define
        field extensions
      * "extField(RingElement)" -- see extField, -- Define
        field extensions
      * "splittingField(Ring,RingElement)" -- see extField, --
        Define field extensions
      * "splittingField(RingElement)" -- see extField, --
        Define field extensions
      * "globalHeight(List)" -- see globalHeight, --
        Multiplicative height function
      * "hermiteNormalForm(List)" -- see hermiteNormalForm,
        -- Compute the Hermite normal form of a fractional
        ideal in a number field
      * "hermiteNormalForm(RingElement)" -- see hermiteNormalForm,
        -- Compute the Hermite normal form of a fractional
        ideal in a number field
      * "discriminant(Ring)" -- see integers, -- Compute a
        basis for the integers of a number field
      * "integers(Ring)" -- see integers, -- Compute a basis
        for the integers of a number field
      * "ProjectivePoint == ProjectivePoint" -- see ProjectivePoint,
        -- Class of a projective point
      * "ring(ProjectivePoint)" -- see ProjectivePoint,
        -- Class of a projective point
      * "rationalPoints(AffineVariety)" -- see rationalPoints,
        -- Find the rational points on a variety
      * "rationalPoints(Ideal)" -- see rationalPoints, --
        Find the rational points on a variety
      * "rationalPoints(ProjectiveVariety)" -- see rationalPoints,
        -- Find the rational points on a variety
      * "rationalPoints(Ring,AffineVariety)" -- see rationalPoints,
        -- Find the rational points on a variety
      * "rationalPoints(Ring,Ideal)" -- see rationalPoints,
        -- Find the rational points on a variety
      * "rationalPoints(Ring,ProjectiveVariety)" -- see rationalPoints,
        -- Find the rational points on a variety
      * "zeros(Ring,RingElement)" -- see zeros, -- List the zeros
        of a polynomial
      * "zeros(RingElement)" -- see zeros, -- List the zeros of a
        polynomial
  * Symbols
      * "Amount" -- see rationalPoints, -- Find the
        rational points on a variety
      * "Bound" -- see rationalPoints, -- Find the
        rational points on a variety
      * "KeepAll" -- see rationalPoints, -- Find the
        rational points on a variety
      * "Split" -- see rationalPoints, -- Find the
        rational points on a variety

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

The object RationalPoints2, is a package (Macaulay2Doc).

Main function that enumerates the rational points

Utility functions for handling field extensions and number fields

rationalPoints -- Find the rational points on a variety
*******************************************************

Synopsis
========

  * Usage:
        rationalPoints I
        rationalPoints(F, I)
  * Inputs:
      * I, an ideal (Macaulay2Doc), viewed as an affine variety;
        an affine variety (Macaulay2Doc), / a
        projective variety (Macaulay2Doc), can also be used
      * F, the coefficient field; if not specified then it is taken to be the
        field of definition of I
  * Optional inputs (Macaulay2Doc),:
      * Amount => a Boolean value (Macaulay2Doc), default value
        false, whether to only compute the number of rational points.
      * Projective => a Boolean value (Macaulay2Doc), default
        value false, whether to treat the ideal as a homogeneous ideal and
        consider the corresponding projective variety
      * Split => a Boolean value (Macaulay2Doc), default value
        false, whether to compute all rational points over the splitting field,
        works only if I is 0-dimensional (ignored if F is specified)
      * Verbose => a Boolean value (Macaulay2Doc), default value
        false, whether to print the polynomials computed that do not split in
        the coefficient field (if Split is set to true, it will instead print
        information when a field extension is performed)
      * Bound => a number (Macaulay2Doc), default value null,
        over a number field, specify the upper bound of the multiplicative
        height for the points to enumerate
      * KeepAll => a Boolean value (Macaulay2Doc), default value
        false, whether to keep the rational points found with height exceeding
        the bound
  * Outputs:
      * Either a list (Macaulay2Doc), of points, or the number of
        such points if Amount is set to true. In the affine case each point is
        represented by a list (Macaulay2Doc), of coordinates, and in
        the projective case each point is an instance of the type
        ProjectivePoint.

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

This method takes in an ideal I and returns a list of rational points on the
variety defined by the ideal. The algorithm uses brute force plus some
elimination. Options are available for different use cases.

Over finite fields
------------------

Over a finite field (ZZ/p or GF q), the ideal can have arbitrary dimension. By
default it will be regarded as an affine variety.

+-----------------------------------------------------------------------------+
|i1 : R = ZZ/5[x,y,z]; I = ideal(x^3-y*z, x+y);                               |
|                                                                             |
|o2 : Ideal of R                                                              |
+-----------------------------------------------------------------------------+
|i3 : rationalPoints I                                                        |
|                                                                             |
|o3 = {{0, 0, 0}, {0, 0, 1}, {-2, 2, 1}, {2, -2, 1}, {0, 0, 2}, {0, 0, -2},   |
|     ------------------------------------------------------------------------|
|     {0, 0, -1}, {-1, 1, -1}, {1, -1, -1}}                                   |
|                                                                             |
|o3 : List                                                                    |
+-----------------------------------------------------------------------------+
|i4 : #rationalPoints Spec(R/I)                                               |
|                                                                             |
|o4 = 9                                                                       |
+-----------------------------------------------------------------------------+
|i5 : #rationalPoints_(GF 25) I                                               |
|                                                                             |
|o5 = 49                                                                      |
+-----------------------------------------------------------------------------+

To consider projective varieties, one can use the option Projective=>true or
pass directly a projective variety (Macaulay2Doc). In
this case, the rational points are given in homogeneous coordinates. The first
non-zero coordinate will be normalized to 1.

For example we can take the twisted cubic, which is a smooth rational curve so
it has q+1 points over a finite field of q elements.

+-----------------------------------------------------------------------------+
|i6 : ZZ/5[x,y,z,w]; I = ideal "xz-y2,xw-yz,yw-z2";                           |
|                                                                             |
|              ZZ                                                             |
|o7 : Ideal of --[x..z, w]                                                    |
|               5                                                             |
+-----------------------------------------------------------------------------+
|i8 : rationalPoints(I, Projective => true)                                   |
|                                                                             |
|o8 = {(1 : 0 : 0 : 0), (1 : 1 : 1 : 1), (1 : -2 : -1 : 2), (1 : 2 : -1 : -2),|
|     ------------------------------------------------------------------------|
|     (1 : -1 : 1 : -1), (0 : 0 : 0 : 1)}                                     |
|                                                                             |
|o8 : List                                                                    |
+-----------------------------------------------------------------------------+
|i9 : #rationalPoints variety I                                               |
|                                                                             |
|o9 = 6                                                                       |
+-----------------------------------------------------------------------------+
|i10 : #rationalPoints_(GF 25) variety I                                      |
|                                                                             |
|o10 = 26                                                                     |
+-----------------------------------------------------------------------------+

If only the number of rational points is needed, set Amount to true can
sometimes speed up the computation.

+------------------------------------------------------------------+
|i11 : ZZ/101[u_0..u_10]; f = sum toList(u_0..u_10); I = ideal f   |
|                                                                  |
|o13 = ideal(u  + u  + u  + u  + u  + u  + u  + u  + u  + u  + u  )|
|             0    1    2    3    4    5    6    7    8    9    10 |
|                                                                  |
|                ZZ                                                |
|o13 : Ideal of ---[u ..u  ]                                       |
|               101  0   10                                        |
+------------------------------------------------------------------+
|i14 : time rationalPoints(I, Amount => true)                      |
|     -- used 0.00908627 seconds                                   |
|                                                                  |
|o14 = 110462212541120451001                                       |
+------------------------------------------------------------------+

Over number fields
------------------

Over a number field one can use the option Bound to specify a maximal
multiplicative height given by $(x_0:\dots:x_n)\mapsto \prod_{v}\max_i|x_i|_v
^{d_v/d}$ (this is also available as a method globalHeight).

+-----------------------------------------------------------------------------+
|i15 : QQ[x,y,z]; I = homogenize(ideal(y^2-x*(x-1)*(x-2)*(x-5)*(x-6)), z);    |
|                                                                             |
|o16 : Ideal of QQ[x..z]                                                      |
+-----------------------------------------------------------------------------+
|i17 : rationalPoints(variety I, Bound=>12)                                   |
|                                                                             |
|                             1            1             1            1       |
|o17 = {(1 : 0 : 1), (1 : 0 : -), (1 : 2 : -), (1 : -2 : -), (1 : 0 : -), (1 :|
|                             2            3             3            5       |
|      -----------------------------------------------------------------------|
|          1                                                                  |
|      0 : -), (0 : 1 : 0), (0 : 0 : 1)}                                      |
|          6                                                                  |
|                                                                             |
|o17 : List                                                                   |
+-----------------------------------------------------------------------------+
|i18 : globalHeight \ oo                                                      |
|                                                                             |
|o18 = {1, 2, 6, 6, 5, 6, 1, 1}                                               |
|                                                                             |
|o18 : List                                                                   |
+-----------------------------------------------------------------------------+

During the enumeration, sometimes there are rational points found with height
exceeding the bound. These are cast away by default. Use KeepAll=>true to keep
such points (this will also avoid the heavy task of computing the height
function, especially over number fields other than QQ).

+-----------------------------------------------------------------------------+
|i19 : rationalPoints(variety I, Bound=>12, KeepAll=>true)                    |
|                                                                             |
|                             1            1             1            1       |
|o19 = {(1 : 0 : 1), (1 : 0 : -), (1 : 2 : -), (1 : -2 : -), (1 : 0 : -), (1 :|
|                             2            3             3            5       |
|      -----------------------------------------------------------------------|
|          1              1               1                                   |
|      0 : -), (1 : 12 : --), (1 : -12 : --), (0 : 1 : 0), (0 : 0 : 1)}       |
|          6             10              10                                   |
|                                                                             |
|o19 : List                                                                   |
+-----------------------------------------------------------------------------+
|i20 : globalHeight \ oo                                                      |
|                                                                             |
|o20 = {1, 2, 6, 6, 5, 6, 120, 120, 1, 1}                                     |
|                                                                             |
|o20 : List                                                                   |
+-----------------------------------------------------------------------------+

In the affine case, the height function is used on individual coordinates, so
for example {2,1/2} will be considered as of height 2 instead of 4.

+------------------------------------------------------------------+
|i21 : QQ[x,y]; rationalPoints(ideal(x-2), Bound=>2)               |
|                                                                  |
|                                                       1       1  |
|o22 = {{2, -2}, {2, -1}, {2, 0}, {2, 1}, {2, 2}, {2, - -}, {2, -}}|
|                                                       2       2  |
|                                                                  |
|o22 : List                                                        |
+------------------------------------------------------------------+

Zero-dimensional ideals
-----------------------

For a 0-dimensional ideal, all the rational points can be found, including
those in the splitting field. Set the option Verbose to true will print the
polynomials found not splitting in the coefficient field, and set Split to true
will automatically make field extensions and compute all the points over the
splitting field. The information on the splitting field can either be printed
using Verbose=>true, or be retrieved from any coordinate of the points. One can
refer to extField, and baseChange, for the
methods used in handling field extensions.

+-------------------------------------------------------+
|i23 : R = QQ[x,y]; I = ideal(x^2+y^2-1,x^3+y^3-1);     |
|                                                       |
|o24 : Ideal of R                                       |
+-------------------------------------------------------+
|i25 : rationalPoints(I, Verbose => true)               |
|-- the following polynomials do not split              |
|   -- 2*x^2+4*x+3                                      |
|                                                       |
|o25 = {{1, 0}, {0, 1}}                                 |
|                                                       |
|o25 : List                                             |
+-------------------------------------------------------+
|i26 : rationalPoints(I, Verbose => true, Split => true)|
|-- base change to the field QQ[a]/(a^2+4*a+6)          |
|                                                       |
|                          1       1     1     1        |
|o26 = {{1, 0}, {0, 1}, {- -a - 2, -a}, {-a, - -a - 2}} |
|                          2       2     2     2        |
|                                                       |
|o26 : List                                             |
+-------------------------------------------------------+
|i27 : ring \ first oo                                  |
|                                                       |
|          QQ[a]          QQ[a]                         |
|o27 = {-----------[], -----------[]}                   |
|        2              2                               |
|       a  + 4a + 6    a  + 4a + 6                      |
|                                                       |
|o27 : List                                             |
+-------------------------------------------------------+

Note that the computations over number fields of large degree are slow. In such
cases it might be better to switch to a large finite field where the program
runs much faster. One could also use numerical algorithms implemented in the
packages EigenSolver, (which uses the same strategy of
elimination) and NumericalAlgebraicGeometry,
(which uses homotopy continuation).

The next example computes the 31 nodes on a Togliatti surface (see
https://en.wikipedia.org/wiki/Togliatti_surface ). Over characteristic 0 the
splitting field has degree 8 over QQ, so the computation isn't so heavy.

+-----------------------------------------------------------------------------+
|i28 : F = toField(QQ[q]/(q^4-10*q^2+20)); R = F[x,y,z,w];                    |
+-----------------------------------------------------------------------------+
|i30 : I = ideal "64(x-w)(x4-4x3w-10x2y2-4x2w2+16xw3-20xy2w+5y4+16w4-20y2w2)- |
|                                                                             |
|o30 : Ideal of R                                                             |
|-----------------------------------------------------------------------------|
|5q(2z-qw)(4(x2+y2-z2)+(1+3(5-q2))w2)2";                                      |
+-----------------------------------------------------------------------------+
|i31 : nodes = I + ideal jacobian I;                                          |
|                                                                             |
|o31 : Ideal of R                                                             |
+-----------------------------------------------------------------------------+
|i32 : time rationalPoints(variety nodes, Split=>true, Verbose=>true);        |
|-- base change to the field QQ[a]/(a^8-40*a^6+230*a^4-200*a^2+25)            |
|     -- used 4.64554 seconds                                                 |
+-----------------------------------------------------------------------------+
|i33 : #oo                                                                    |
|                                                                             |
|o33 = 31                                                                     |
+-----------------------------------------------------------------------------+

Still it runs a lot faster when reduced to a positive characteristic.

+----------------------------------------------------------------------+
|i34 : nodes' = baseChange_32003 nodes;                                |
|                                                                      |
|o34 : Ideal of GF 1048969271299456081[x..z, w]                        |
+----------------------------------------------------------------------+
|i35 : time #rationalPoints(variety nodes', Split=>true, Verbose=>true)|
|     -- used 0.769067 seconds                                         |
|                                                                      |
|o35 = 31                                                              |
+----------------------------------------------------------------------+

Caveat
======

For a number field other than QQ, the enumeration of elements with bounded
height depends on an algorithm by Doyle–Krumm, which is currently only
implemented in Sage.

Ways to use rationalPoints :
============================

  * "rationalPoints(AffineVariety)"
  * "rationalPoints(Ideal)"
  * "rationalPoints(ProjectiveVariety)"
  * "rationalPoints(Ring,AffineVariety)"
  * "rationalPoints(Ring,Ideal)"
  * "rationalPoints(Ring,ProjectiveVariety)"

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

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

zeros -- List the zeros of a polynomial
***************************************

Synopsis
========

  * Usage:
        zeros p
        zeros(F, p)
  * Inputs:
      * p, a polynomial
      * F, the coefficient field; if not specified then it is taken to be the
        field of definition of p
  * Outputs:
      * a list (Macaulay2Doc), of zeros of p in the coefficient
        field

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

Get a list (Macaulay2Doc), of zeros of a polynomial using
factor (Macaulay2Doc), baby version of rationalPoints.

+------------------------------------------------------+
|i1 : QQ[x]; p = (x-2)^2 * (x^2-2) * (x^3-x-1); zeros p|
|                                                      |
|o3 = {2}                                              |
|                                                      |
|o3 : List                                             |
+------------------------------------------------------+
|i4 : F = toField(QQ[q]/(q^2-2)); zeros_F p            |
|                                                      |
|o5 = {2, q, -q}                                       |
|                                                      |
|o5 : List                                             |
+------------------------------------------------------+
|i6 : F = splittingField p; #zeros_F p                 |
|                                                      |
|o7 = 6                                                |
+------------------------------------------------------+

Note that when the degree is big, the expression of each zero in terms of a
primitive element is usually complicated.

+-----------------------------------------------------------------------------+
|i8 : last zeros_F p                                                          |
|                                                                             |
|          2918037   11      43736   10     176511427  9     1742239  8       |
|o8 = - ------------a   + ----------a   + ------------a  - ----------a  -     |
|       194598748990      3926880585      194598748990     2617920390         |
|     ------------------------------------------------------------------------|
|      7776041337  7    54520588  6    38282000079 5    50576753 4            |
|     ------------a  + ----------a  + ------------a  - ---------a  -          |
|     389197497980     3926880585     194598748990     436320065              |
|     ------------------------------------------------------------------------|
|     382379122373 3   1544138762 2   456488667029     137345843              |
|     ------------a  + ----------a  + ------------a + ----------              |
|     389197497980     3926880585     389197497980    1308960195              |
|                                                                             |
|o8 : F                                                                       |
+-----------------------------------------------------------------------------+
|i9 : (map(F, ring p, {oo})) p                                                |
|                                                                             |
|o9 = 0                                                                       |
|                                                                             |
|o9 : F                                                                       |
+-----------------------------------------------------------------------------+

Over finite fields.

+--------------------------------------+
|i10 : q = baseChange_13 p; zeros q    |
|                                      |
|o11 = {2}                             |
|                                      |
|o11 : List                            |
+--------------------------------------+
|i12 : F = splittingField q; describe F|
|                                      |
|o13 = GF 4826809                      |
+--------------------------------------+
|i14 : #zeros_F q                      |
|                                      |
|o14 = 6                               |
+--------------------------------------+

Ways to use zeros :
===================

  * "zeros(Ring,RingElement)"
  * "zeros(RingElement)"

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

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

ProjectivePoint -- Class of a projective point
**********************************************

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

A subclass of List (Macaulay2Doc), mainly used for pretty printing.
Can be constructed using a projective variety (Macaulay2Doc),
plus a visible list (Macaulay2Doc).

+-------------------------+
|i1 : P = Proj(QQ[x,y,z]);|
+-------------------------+
|i2 : pt = P(1,2,3)       |
|                         |
|o2 = (1 : 2 : 3)         |
|                         |
|o2 : ProjectivePoint     |
+-------------------------+
|i3 : pt == P{2,4,6}      |
|                         |
|o3 = true                |
+-------------------------+

Use ring to retrieve the coefficient field.

+------------+
|i4 : ring pt|
|            |
|o4 = QQ     |
|            |
|o4 : Ring   |
+------------+

Methods that use an object of class ProjectivePoint :
=====================================================

  * "ProjectivePoint == ProjectivePoint"
  * "ring(ProjectivePoint)"

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

The object ProjectivePoint, is a type (Macaulay2Doc),
with ancestor classes List (Macaulay2Doc), <
VisibleList (Macaulay2Doc) < BasicList (Macaulay2Doc)
< Thing (Macaulay2Doc).

globalHeight -- Multiplicative height function
**********************************************

Synopsis
========

  * Usage:
        globalHeight pt
  * Inputs:
      * pt, a list (Macaulay2Doc), representing homogeneous
        coordinates or an instance of the type ProjectivePoint,
  * Outputs:
      * the multiplicative height function

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

This method computes the multiplicative height function given by
$(x_0:\dots:x_n)\mapsto \prod_{v}\max_i|x_i|_v ^{d_v/d}$. Over rational numbers
the result will be given as a precise value.

+------------------------------------------------+
|i1 : globalHeight {1/1,2/3,5/8}                 |
|                                                |
|o1 = 24                                         |
|                                                |
|o1 : QQ                                         |
+------------------------------------------------+
|i2 : PP = Proj(QQ[x,y,z]); pt = PP(1/1,2/3,5/8);|
+------------------------------------------------+
|i4 : globalHeight pt                            |
|                                                |
|o4 = 24                                         |
|                                                |
|o4 : QQ                                         |
+------------------------------------------------+
|i5 : F = toField(QQ[u]/(u^3-5));                |
+------------------------------------------------+
|i6 : globalHeight {u,u^2/5,1_F}                 |
|                                                |
|o6 = 2.92401773821287                           |
|                                                |
|o6 : RR (of precision 53)                       |
+------------------------------------------------+

Ways to use globalHeight :
==========================

  * "globalHeight(List)"

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

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

baseChange -- Perform base change for field extensions
******************************************************

Synopsis
========

  * Usage:
        baseChange(F, -)
        baseChange(p, -)
  * Inputs:
      * F, the extension field
      * p, a prime number
      * a polynomial or an ideal (Macaulay2Doc), with coefficients
        in the base field
  * Optional inputs (Macaulay2Doc),:
      * PrimitiveElement => ..., default value FindOne, specify the image of
        the primitive element
  * Outputs:
      * a polynomial or an ideal (Macaulay2Doc), with coefficients
        in the extension field

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

The base change requires finding an image for the primitive element of the base
field, which can be specified using the option PrimitiveElement. The default is
FindOne, in which case we solve the minimal polynomial of the base field in the
extension field and take the first zero. Beware that it is well-defined only up
to the action of the Galois group.

In this example we first obtain an extension F of the rational numbers by
adding a cube root of 2, then we compute its image in the splitting field F' of
x^3-2.

+---------------------------------------+
|i1 : F = toField(QQ[c]/(c^3-2));       |
+---------------------------------------+
|i2 : QQ[x]; F' = splittingField(x^3-2);|
+---------------------------------------+
|i4 : c' = baseChange_F' c              |
|                                       |
|      1 4                              |
|o4 = --a                               |
|     18                                |
|                                       |
|o4 : F'                                |
+---------------------------------------+
|i5 : c'^3 == 2                         |
|                                       |
|o5 = true                              |
+---------------------------------------+
|i6 : F[x,y]; I = ideal(x-c, y-c^2);    |
|                                       |
|o7 : Ideal of F[x..y]                  |
+---------------------------------------+
|i8 : baseChange_F' I                   |
|                                       |
|                 1 4      1 2          |
|o8 = ideal (x - --a , y + -a )         |
|                18        3            |
|                                       |
|o8 : Ideal of F'[x..y]                 |
+---------------------------------------+

We get a different embedding by specifying the image of the primitive element.

+------------------------------------------------+
|i9 : F'[x]; c'' = last zeros(x^3-2);            |
+------------------------------------------------+
|i11 : baseChange(F', I, PrimitiveElement => c'')|
|                                                |
|                  1 4   1        1 5   1 2      |
|o11 = ideal (x + --a  + -a, y - --a  - -a )     |
|                 36     2       36     6        |
|                                                |
|o11 : Ideal of F'[x..y]                         |
+------------------------------------------------+

If a prime number p is input instead of a field, the element will be reduced to
characteristic p.

+-----------------------------------+
|i12 : QQ[x]; baseChange_7 (x^3-2)  |
|                                   |
|       3                           |
|o13 = x  - 2                       |
|                                   |
|      ZZ                           |
|o13 : --[x]                        |
|       7                           |
+-----------------------------------+
|i14 : F[x]; baseChange_7 ideal(x-c)|
|                                   |
|                 2                 |
|o15 = ideal(x - a  - a + 3)        |
|                                   |
|o15 : Ideal of GF 343[x]           |
+-----------------------------------+

We can also base change an element of a number field to the complex numbers.
Note that to avoid accumulated errors, it is better to do computations in the
field and only make the conversion once in the end.

+----------------------------------------------+
|i16 : baseChange_CC c                         |
|                                              |
|o16 = 1.25992104989487-5.51778060002121e-61*ii|
|                                              |
|o16 : CC (of precision 53)                    |
+----------------------------------------------+
|i17 : oo^3                                    |
|                                              |
|o17 = 2-2.62767921870102e-60*ii               |
|                                              |
|o17 : CC (of precision 53)                    |
+----------------------------------------------+
|i18 : baseChange_CC (c^3)                     |
|                                              |
|o18 = 2                                       |
|                                              |
|o18 : CC (of precision 53)                    |
+----------------------------------------------+

For complex numbers we only need to provide an approximate value for
PrimitiveElement.

+-------------------------------------------------------+
|i19 : baseChange(CC, c, PrimitiveElement => -.6+1.1*ii)|
|                                                       |
|o19 = -.629960524947436+1.09112363597172*ii            |
|                                                       |
|o19 : CC (of precision 53)                             |
+-------------------------------------------------------+

Ways to use baseChange :
========================

  * "baseChange(InexactFieldFamily,Number)"
  * "baseChange(InexactFieldFamily,RingElement)"
  * "baseChange(Number,Ideal)"
  * "baseChange(Number,Number)"
  * "baseChange(Number,RingElement)"
  * "baseChange(Ring,Ideal)"
  * "baseChange(Ring,Number)"
  * "baseChange(Ring,RingElement)"

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

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

extField -- Define field extensions
***********************************

Synopsis
========

  * Usage:
        extField p / extField {p, p', ...}
        extField(F, p) / extField(F, {p, p', ...})
        splittingField p
        splittingField(F, p)
  * Inputs:
      * p, a univariate polynomial or a list (Macaulay2Doc), of them
      * F, the base field; if not specified then it is taken to be the field of
        definition of p
  * Optional inputs (Macaulay2Doc),:
      * Variable => a symbol (Macaulay2Doc), default value "a",
        the variable to use for the primitive element of the extension field
  * Outputs:
      * F', an extension field over the field of definition of p, or over the
        base field F

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

Methods for defining field extensions. The method extField accepts an
irreducible polynomial p and adds one of its zeros into the base field. The
base field can itself be a simple extension represented by a primitive element,
in which case a new primitive element is computed. Use the option Variable to
specify the symbol used for the primitive element (the default is a like
GaloisField (Macaulay2Doc)). N.B. Any data previously stored in
this symbol will be lost! As is the case for GaloisField.

Here we first add i into the rational numbers. Similar to toField (Macaulay2Doc),
the variable used in the polynomial will be
set to its image in the extension, but note that this is not necessarily the
primitive element.

+-------------------------------------------------+
|i1 : QQ[x]; F = extField(4*x^2+1, Variable=>i); x|
|                                                 |
|     1                                           |
|o3 = -i                                          |
|     2                                           |
|                                                 |
|o3 : F                                           |
+-------------------------------------------------+
|i4 : baseRing F                                  |
|                                                 |
|      QQ[i]                                      |
|o4 = ------                                      |
|      2                                          |
|     i  + 1                                      |
|                                                 |
|o4 : QuotientRing                                |
+-------------------------------------------------+
|i5 : i^2 + 1 == 0                                |
|                                                 |
|o5 = true                                        |
+-------------------------------------------------+

Now we perform another field extension over F by adding the square root of 2. A
new primitive element a will be computed.

+--------------------------------------+
|i6 : QQ[q]; F' = extField(F, q^2-2); q|
|                                      |
|     1 3   5                          |
|o8 = -a  - -a                         |
|     6     6                          |
|                                      |
|o8 : F'                               |
+--------------------------------------+
|i9 : q^2 == 2                         |
|                                      |
|o9 = true                             |
+--------------------------------------+
|i10 : baseRing F'                     |
|                                      |
|          QQ[a]                       |
|o10 = ------------                    |
|       4     2                        |
|      a  - 2a  + 9                    |
|                                      |
|o10 : QuotientRing                    |
+--------------------------------------+

For elements of the base field F, we can use baseChange, to
determine their images in the extension field F'.

+-------------------------+
|i11 : j = baseChange_F' i|
|                         |
|      1 3   1            |
|o11 = -a  + -a           |
|      6     6            |
|                         |
|o11 : F'                 |
+-------------------------+
|i12 : j^2 + 1 == 0       |
|                         |
|o12 = true               |
+-------------------------+

It is also possible to do multiple extensions at the same time. Note that x is
now set to i/2, so in order to use it as a variable we need to use
symbol (Macaulay2Doc), to reclaim it.

+---------------------------------------------------------------+
|i13 : QQ[symbol x]; F' = extField {4*x^2+1, x^2-2}; baseRing F'|
|                                                               |
|          QQ[a]                                                |
|o15 = ------------                                             |
|       4     2                                                 |
|      a  - 2a  + 9                                             |
|                                                               |
|o15 : QuotientRing                                             |
+---------------------------------------------------------------+

When passing a list (Macaulay2Doc), of polynomials, the variable x
will not be set. This can also be used for one polynomial to avoid setting the
value of x.

+---------------------------+
|i16 : extField {4*x^2+1}; x|
|                           |
|o17 = x                    |
|                           |
|o17 : QQ[x]                |
+---------------------------+

Repeatedly applying extField using the same polynomial will add all its zeros
into the field. This can also be done using the method splittingField. For
example we may construct the splitting field of x^3-2 as follows.

+----------------------------------------------------+
|i18 : QQ[x]; p = x^3-2; F = extField {p}; #zeros_F p|
|                                                    |
|o21 = 1                                             |
+----------------------------------------------------+
|i22 : F' = extField {p, p}; #zeros_F' p             |
|                                                    |
|o23 = 3                                             |
+----------------------------------------------------+
|i24 : F' = splittingField p; #zeros_F' p            |
|                                                    |
|o25 = 3                                             |
+----------------------------------------------------+

Over finite fields, the degree is first computed while the rest is handled by
GaloisField (Macaulay2Doc).

+-----------------------------------------------+
|i26 : ZZ/11[x]; F = extField(x^4+1); describe F|
|                                               |
|o28 = GF 121                                   |
+-----------------------------------------------+
|i29 : x                                        |
|                                               |
|o29 = 5a + 5                                   |
|                                               |
|o29 : F                                        |
+-----------------------------------------------+
|i30 : x^4 + 1 == 0                             |
|                                               |
|o30 = true                                     |
+-----------------------------------------------+

Caveat
======

If PARI/GP is available on the system, the program will try to use the function
polredbest to reduce the minimal polynomial. This will give an equivalent but
usually much optimal result. Note that for large inputs, one could increase the
pari stack size by using setPariSize n.

Ways to use extField :
======================

  * "extField(List)"
  * "extField(Ring,List)"
  * "extField(Ring,RingElement)"
  * "extField(RingElement)"

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

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

charpoly -- Characteristic and minimal polynomials over the prime field
***********************************************************************

Synopsis
========

  * Usage:
        charpoly a
        minpoly a
  * Inputs:
      * a, an element of a field
  * Optional inputs (Macaulay2Doc),:
      * Variable => a symbol (Macaulay2Doc), default value "x",
        the variable to use for the polynomial
  * Outputs:
      * the characteristic / minimal polynomial of a over its prime field

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

Obtain the characteristic / minimal polynomial of an element over its prime
field.

+------------------------------------------------+
|i1 : QQ[x]; F = splittingField((x^2+1)*(x^2-2));|
+------------------------------------------------+
|i3 : minpoly a                                  |
|                                                |
|      4     2                                   |
|o3 = x  - 2x  + 9                               |
|                                                |
|o3 : QQ[x]                                      |
+------------------------------------------------+
|i4 : charpoly(a^2+1, Variable=>y)               |
|                                                |
|      4     3      2                            |
|o4 = y  - 8y  + 40y  - 96y + 144                |
|                                                |
|o4 : QQ[y]                                      |
+------------------------------------------------+
|i5 : minpoly(a^2+1, Variable=>y)                |
|                                                |
|      2                                         |
|o5 = y  - 4y + 12                               |
|                                                |
|o5 : QQ[y]                                      |
+------------------------------------------------+
|i6 : GF 81; minpoly(a+1)                        |
|                                                |
|      4    3                                    |
|o7 = x  + x  - x + 1                            |
|                                                |
|     ZZ                                         |
|o7 : --[x]                                      |
|      3                                         |
+------------------------------------------------+

The method minpoly can also be used on a field to recover the polynomial used
in its definition.

+-----------------+
|i8 : minpoly F   |
|                 |
|      4     2    |
|o8 = a  - 2a  + 9|
|                 |
|o8 : QQ[a]       |
+-----------------+

Ways to use charpoly :
======================

  * "charpoly(Number)"
  * "charpoly(RingElement)"

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

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

integers -- Compute a basis for the integers of a number field
**************************************************************

Synopsis
========

  * Usage:
        integers F
        discriminant F
  * Inputs:
      * F, a number field
  * Outputs:
      * return an integral basis of the algebraic integers of the field F as a
        list (Macaulay2Doc), and compute the discriminant

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

This is an implementation of the Zassenhaus' Round 2 algorithm, following the
textbook A course in computational algebraic number theory by Henri Cohen
(Algorithm 6.1.8). Given a number field $F=\mathbf Q(\theta)$ defined as a
simple extension over the rational numbers by an integral primitive element
$\theta$, it computes an integral basis of the algebraic integers, expressed as
polynomials in $\theta$.

+------------------------------------+
|i1 : integers QQ                    |
|                                    |
|o1 = {1}                            |
|                                    |
|o1 : List                           |
+------------------------------------+
|i2 : integers toField(QQ[i]/(i^2+1))|
|                                    |
|o2 = {1, i}                         |
|                                    |
|o2 : List                           |
+------------------------------------+
|i3 : integers toField(QQ[a]/(a^2+3))|
|                                    |
|         1    1                     |
|o3 = {1, -a + -}                    |
|         2    2                     |
|                                    |
|o3 : List                           |
+------------------------------------+

The discriminant is computed using the same algorithm.

+------------------------------------------+
|i4 : discriminant toField(QQ[a]/(a^2+3))  |
|                                          |
|o4 = -3                                   |
+------------------------------------------+
|i5 : discriminant toField(QQ[a]/(a^4-a+2))|
|                                          |
|o5 = 2021                                 |
+------------------------------------------+

Ways to use integers :
======================

  * "integers(Ring)"

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

The object integers, is a method function (Macaulay2Doc).

hermiteNormalForm -- Compute the Hermite normal form of a fractional ideal in a number field
********************************************************************************************

Synopsis
========

  * Usage:
        hermiteNormalForm a
        hermiteNormalForm {a, a', ...}
  * Inputs:
      * a, an element of a number field, or a list (Macaulay2Doc),
        of them
  * Outputs:
      * a matrix (Macaulay2Doc), representing the Hermite normal
        form of the fractional ideal generated by a

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

This method computes the Hermite normal form of a fractional ideal in terms of
the integral basis given by integers.

+--------------------------------+
|i1 : F = toField(QQ[q]/(q^2+3));|
+--------------------------------+
|i2 : hermiteNormalForm 1_F      |
|                                |
|o2 = | 1 0 |                    |
|     | 0 1 |                    |
|                                |
|              2        2        |
|o2 : Matrix QQ  <--- QQ         |
+--------------------------------+
|i3 : hermiteNormalForm(q/3)     |
|                                |
|o3 = | 1 1/3 |                  |
|     | 0 1/3 |                  |
|                                |
|              2        2        |
|o3 : Matrix QQ  <--- QQ         |
+--------------------------------+

Ways to use hermiteNormalForm :
===============================

  * "hermiteNormalForm(List)"
  * "hermiteNormalForm(RingElement)"

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

The object hermiteNormalForm, is a method function (Macaulay2Doc).