The slightly non-standard term variety in this section refers to the (finite) solution set of the system of polynomials that make up an ideal. It can also be thought of as the set of points of a zero-dimensional affine scheme over a specified field extension of the polynomial ring base field. For more general functionality for schemes of arbitrary dimension, see the chapters on Algebraic and Arithmetic Geometry. The functions here also work for higher-dimensional ideals if the base field is finite, when the solution set is again finite (over the base or a finite extension of the base).
The functions compute solutions over the base field of the polynomial ring or over an extension field L. Magma's algebraically closed fields (see Chapter ALGEBRAICALLY CLOSED FIELDS) may be used to get all solutions if so desired when an explicit splitting field is not known for the system. L should be an exact field over which Magma has a root-finding algorithm for univariate polynomials or a real or complex field.
For the corresponding functions with argument a zero-dimensional scheme which may not be affine, see the Section Rational Points and Point Sets in the Schemes chapter.
Al: MonStgElt Default: em "Default"
Eval: RngIntElt Default:
Given an ideal I of a polynomial ring P, return the affine variety of I over its coefficient field K as a sequence of tuples. Each tuple is of length n, where n is the rank of P, and corresponds to an assignment of the n variables of P (in order) such that all polynomials in I vanish with this assignment.If K is not a finite field then the ideal must be the full polynomial ring or be zero-dimensional so that the variety is known to be finite. If a superfield L of K is also given, the variety is computed over L instead, so the entries of the tuples lie in L.
Al := "Wiedemann": This parameter selects the Wiedemann algorithm and is applicable to computing the variety of a generic zero-dimensional ideal I over K, where K is a moderately sized finite field. The degree D of I is the dimension of the quotient algebra R/I, and as D grows large (particularly above 10000), computing the variety of I becomes very difficult since it involves computing a minimal polynomial of degree D. The Wiedemann algorithm is effective when it is impractical to store a fully dense D x D matrix in memory. See http://magma.maths.usyd.edu.au/users/allan/densef4/#CC for a very large example.
Al := "KellerGehrig": This parameter selects the Keller-Gehrig algorithm, which is similar to the Wiedemann algorithm in that it finds the minimal polynomial of a matrix to compute a variety of a zero-dimensional ideal, but it uses the Keller-Gehrig algorithm to compute this minimal polynomial by mapping the problem to several matrix multiplications. This method typically takes more memory than the Wiedemann algorithm but may be faster for dimensions in the thousands, particularly when a GPU is available.
Al := "ExhaustiveSearch": This parameter selects the Exhaustive Search algorithm for solving quadratic multivariate polynomial systems over GF(2). For a system with n variables, the algorithm simply enumerates all 2n possible assignments of the variables and determines the set of all such assignments which simultaneously satisfy all the polynomial equations. Despite the obvious exponential complexity of this brute force approach, the algorithm is highly optimised: for a quadratic input system, the algorithm covers 1010 possible solutions in 1.47 seconds on a typical 3.2GHz Intel Xeon processor and an arbitrary quadratic system with 40 variables is solved in 162 seconds. The algorithm is preferable to other algorithms for certain types of input system. For example, in the case of an arbitrary generic dense quadratic system with no structure (such as a random system), the exhaustive search algorithm is typically faster than both the Gröbner basis and SAT algorithms by a factor of more than 100. This is because all algorithms have exponential complexity for this type of input, but the associated constant is much better for the exhaustive search.
Eval := e: If Eval is set to a small positive integer e, then the function works by evaluating the input polynomials at the last e variables to all possible constants in K (so there are qe cases enumerated) and then computing the variety of each simplified ideal and combining all the results. This algorithm can be parallelised by the use of SetNthreads and StartWorkers.
Given a zero-dimensional ideal I of a polynomial ring P whose order is of lexicographic type, return the variety of I over its coefficient field K as a sequence of sequences of elements of K. Each inner sequence is of length n, where n is the rank of P, and corresponds to an assignment of the n variables of P (in order) such that all polynomials in I vanish with this assignment. The parameters and other conditions are the same as for Variety above.
Given an ideal I of a polynomial ring P over a field K, return the size of the variety of I over K. The parameters are the same as for the function Variety.
> K<w> := GF(27);
> P<x, y> := PolynomialRing(K, 2);
> I := ideal<P | x^8 + y + 2, y^6 + x*y^5 + x^2>;
> Groebner(I);
> I;
Ideal of Polynomial ring of rank 2 over GF(3^3)
Order: Lexicographical
Variables: x, y
Inhomogeneous, Dimension 0
Groebner basis:
[
x + 2*y^47 + 2*y^45 + y^44 + 2*y^43 + y^41 + 2*y^39 + 2*y^38 + 2*y^37 +
2*y^36 + y^35 + 2*y^34 + 2*y^33 + y^32 + 2*y^31 + y^30 + y^28 + y^27 +
y^26 + y^25 + 2*y^23 + y^22 + y^21 + 2*y^19 + 2*y^18 + 2*y^16 + y^15 +
y^13 + y^12 + 2*y^10 + y^9 + y^8 + y^7 + 2*y^6 + y^4 + y^3 + y^2 + y +
2,
y^48 + y^41 + 2*y^40 + y^37 + 2*y^36 + 2*y^33 + y^32 + 2*y^29 + y^28 +
2*y^25 + y^24 + y^2 + y + 1
]
> V := Variety(I);
> V;
[ <w^14, w^12>, <w^16, w^10>, <w^22, w^4> ]
> // Check that the original polynomials vanish:
> [
> <x^8 + y + 2, y^6 + x*y^5 + x^2> where x is v[1] where y is v[2]: v in V
> ];
[ <0, 0>, <0, 0>, <0, 0> ]
> // Note that the variety of I would be larger over an extension field of K:
> VarietySizeOverAlgebraicClosure(I);
48