Archive

Archive for the ‘algebraic geometry’ Category

Polynomials and affine space

27 March 2009 1 comment

I’m working my way through Cox, Little and O’Shea’s book [1] on computational aspects of algebraic geometry and commutative algebra. The title of the book certainly sounds abstract, but for computational oriented people the good news is that it incorporates the use of a computer algebra system (CAS) into the exposition. The bad news is that the CASs covered are Maple, Mathematica and REDUCE, well not exactly all bad news since REDUCE has recently been open sourced under a BSD-like license. The text by Greuel and Pfister [2] incorporates the open source CAS Singular into its exposition, substantially more so than [1]. Singular is a standard package of Sage so you could also work your way through any of [1] or [2] with Sage. Feeling a little adventurous, I thought I might try using Sage while studying [1].

Polynomials: from one to many

To study commutative algebra and algebraic geometry, one needs to study polynomials in n \geq 1 variables. But polynomials are made up of monomials.

Definition 1
A monomial in n variables x_1, \dots, x_n is a product

(1)
\displaystyle{\prod_{i=1}^n x_i^{\alpha_i}} = x_1^{\alpha_1} \cdot x_2^{\alpha_2} \cdots x_n^{\alpha_n}

where the exponents \alpha_i \in \mathbf{Z} are non-negative. The total degree of the monomial is the sum \sum_i \alpha_i of its exponents.

The quadratic f(x) = x^2 is certainly a monomial in 1 variable with total degree 2, and f(x,y,z) = x y^2 z^3 is a monomial in 3 variables with total degree 6. To simplify the notation for monomials, we let the n variables be an n-tuple x = (x_1, \dots, x_n) and similarly the n exponents can be packed into a tuple of the same dimension: \alpha = (\alpha_1, \dots, \alpha_n). Now (1) can be simply written as

x^{\alpha} = x_1^{\alpha_1} \cdot x_2^{\alpha_2} \cdots x_n^{\alpha_n}

with total degree |\alpha| = \sum_i \alpha_i. OK, so this isn’t always a compact way of writing a monomial, because 1 = x^{\alpha} when \alpha = (0, \dots, 0) requires two characters to express the integer 1. We can now use this shorthand notation for monomials to define polynomials with coefficients in some field k.

Definition 2
A polynomial f in n variables x_1, \dots, x_n with coefficients in a field k is a finite linear combination of monomials of the form

f = \displaystyle{\sum_{\alpha}} a_{\alpha} x^{\alpha}, \qquad a_{\alpha} \in k


where the sum is over an n-tuple \alpha = (\alpha_1, \dots, \alpha_n). The set of all polynomials in x_1, \dots, x_n with coefficients in k is denoted k[x_1, \dots, x_n].

We also have a notion of total degree similar to the case of monomials, in addition to ideas such as coefficients and terms as in the case of single variable polynomials.

Definition 3
Let f = \sum_{\alpha} a_{\alpha} x^{\alpha} be a polynomial in k[x_1, \dots, x_n]. The factor a_{\alpha} is called the coefficient of the monomial x^{\alpha}. In case a_{\alpha} \neq 0, the expression a_{\alpha} x^{\alpha} is called a term of f. The total degree of f, denoted \deg(f), is the maximum |\alpha| such that a_{\alpha} \neq 0.

The polynomial f(x,y,z) = z^3 - zx^2 + y^2 has 3 variables with total degree 3, which is also the total degree of the terms z^3 and -zx^2. The solution set of f(x,y,z) = 0 can be visualized as three cones meeting at a common point. The field k in which coefficients of a polynomial live can be any arbitrary field. For concreteness we can study multivariate polynomials with coefficients in the complex field \mathbf{C}, the real field \mathbf{R}, the rational field \mathbf{Q}, or finite fields such as the Galois fields \mathbf{F}_{p} of p \geq 2 prime number of elements. Here’s a Sage session on multivariate polynomials.

sage: R. = RR[]; R
Multivariate Polynomial Ring in x, y, z over Real Field with 53 bits of precision
sage: f = z^3 - z*x^2 + y^2
sage: f.base_ring()
Real Field with 53 bits of precision
sage: f.coefficients()
[-1.00000000000000, 1.00000000000000, 1.00000000000000]
sage:
sage: # change the ring to the rationals
sage: f = f.change_ring(QQ)
sage: f.base_ring(); f
Rational Field
-x^2*z + z^3 + y^2
sage: f.coefficients()  # coefficients of the terms
[-1, 1, 1]
sage: f.degrees()       # degree of each term
(2, 2, 3)
sage: f.total_degree()  # the total degree
3

Note that in the latter Sage session the command

sage: R. = RR[]

constructs an object R that represents the multivariate polynomial ring \mathbf{R}[x,y,z] in three indeterminates with coefficients over \mathbf{R}. But how do we know that \mathbf{R}[x] is a polynomial ring, let alone \mathbf{R}[x,y,z]? For the case of univariate polynomials, the answer lies in Theorem 1, a proof of which can be found in [3, Appendix G]. Having established the univariate case, one can adapt the same technique to prove the multivariate case.

Theorem 1
Let R be a ring. Then there exists a ring P containing an element x \not\in R such that the following properties are satisfied:

  1. R is a subring of P.
  2. For all a \in R we have xa = ax.
  3. Every element p(x) \in P can be written in the form

    p(x) = \displaystyle{\sum_{i=0}^n} a_i x^i, \qquad a_i \in R

  4. The representation of elements p(x) \in P as p(x) = \sum_{i=0}^n a_i x^i is unique in the sense that if n \leq m and

    \displaystyle{\sum_{i=0}^n a_i x^i = \sum_{j=0}^m b_j x^j}

    then a_i = b_i for i \leq n and b_i = 0_R for each i > n. Here, we use 0_R to denote the additive identity of R.

  5. Finally \sum_{i=0}^n a_i x^i = 0_R iff a_i = 0_R for 0 \leq i \leq n.

Affine space

From calculus and linear algebra, we learn about real and complex vectors in 1, 2 and 3 dimensions and represent them as tuples of the form (v_1), (v_1, v_2) and (v_1, v_2, v_3) respectively. If each v_i \in \mathbf{R} then we have (v_1) \in \mathbf{R}, (v_1, v_2) \in \mathbf{R}^2 and (v_1, v_2, v_3) \in \mathbf{R}^3 respectively. The quadratic f(x) = 2x^2 + x - 3 \in \mathbf{R}[x] evaluates to a real number for any real value of x \in \mathbf{R}. For example, if x = 2 then

sage: f = 2*x^2 + x - 3
sage: f(2)
7

and so we obtain the map f(2) \longmapsto 7. The point is that a polynomial can be thought of as a function. For brave souls among us who deal with polynomials in more than one indeterminate, it’s handy to identify a multivariate polynomial f = \sum_{\alpha} a_{\alpha} x^{\alpha} \in k[x_1, \dots, x_n] with a function of the form

f : k^n \longrightarrow k

where k^n = \{ \left. (a_1, \dots, a_n) \;\right|\; a_i \in k \} is the n-dimensional affine space over the field k with n > 0 an integer. Evaluating a multivariate polynomial follows the same procedure as one would expect: replace each occurrence of a variable in the polynomial by its value. For example:

sage: P. = ZZ[]
sage: f = z^3 - z*x^2 + y^2
sage:
sage: def solfZZ(n):
....:     """
....:     Return positive integer solutions of z^3 - z*x^2 + y^2 = 0.
....:     """
....:     for i in xrange(1, n):
....:         for j in xrange(1, n):
....:             for k in xrange(1, n):
....:                 if f(x=i, y=j, z=k) == 0:
....:                     print "x = %s, y = %s, z = %s" % (i,j,k)
....:
sage: solfZZ(50)
x = 5, y = 6, z = 4
x = 6, y = 8, z = 2
x = 6, y = 9, z = 3
x = 15, y = 36, z = 9
x = 20, y = 48, z = 16
x = 21, y = 36, z = 3
x = 34, y = 48, z = 2

The base ring of a multivariate polynomial can be a finite field say k = \mathbf{F}_2, in which case some polynomials in \mathbf{F}_2[x,y,z] are zero functions. Such functions have the singleton consisting of zero, or the additive identity, as their image.

sage: P. = GF(2)[]
sage: f = x * (x^2 + x) * (x - 1)
sage:
sage: def solfGF():
....:     for i in GF(2):
....:         for j in GF(2):
....:             for k in GF(2):
....:                 print "f(%s, %s, %s) = %s" % (i,j,k, f(i,j,k))
....:
sage: solfGF()
f(0, 0, 0) = 0
f(0, 0, 1) = 0
f(0, 1, 0) = 0
f(0, 1, 1) = 0
f(1, 0, 0) = 0
f(1, 0, 1) = 0
f(1, 1, 0) = 0
f(1, 1, 1) = 0

However, when the base ring k is an infinite field and f \in k[x_1, \dots, x_n], then f = 0 in k[x_1, \dots, x_n] iff f : k^n \longrightarrow k is the zero function. We can use this result to show that two polynomials f,g \in k[x_1, \dots, x_n] are equal in k[x_1, \dots, x_n] iff f : k^n \longrightarrow k and g : k^n \longrightarrow k are the same function on the affine space k^n.

Affine varieties

The idea of a variety is very simple: it is simply the solution set of a system of equations.

Definition 4
Let k be a field and let f_1, \dots, f_s be polynomials in k[x_1, \dots, x_n]. Then the set

\mathbf{V} (f_1, \dots, f_s) = \left\{ \left. (a_1, \dots, a_n) \in k^n \;\right|\; f_i (a_1, \dots, a_n) = 0 \text{ for all } 1 \leq i \leq s \right\}

is called the affine variety defined by f_1, \dots, f_s.

If our base field is k = \mathbf{R}, then the variety \mathbf{V} (x^2 + y^2 - 1) is the unit circle centred at (0,0) (see Figure 1). That is because the solution set of x^2 + y^2 - 1 = 0 consists of all points (x,y) on the unit circle whose centre is the origin of the (x,y)-plane. The unit circle in Figure 1 can be generated using the following commands:

sage: c = circle((0,0), 1, rgbcolor=(0,0,1))
sage: c.show(figsize=[5,5])



In three dimensions, the variety \mathbf{V} (z - x^2 - y^2) defines the paraboloid in Figure 2:

sage: var("x,y");
sage: f = x^2 + y^2
sage: p = plot3d(f, (x,-4,4), (y,-4,4))
sage: p.show(zoom=1.2)



One of the more familiar varieties is the linear variety arising from linear algebra. Let k be a fixed field and consider a system of m linear equations in n variables x_1, \dots, x_n with coefficients in k, that is:

a_{11} x_1 + \cdots + a_{1n} x_n = b_1
\vdots
a_{m1} x_1 + \cdots + a_{mn} x_n = b_m

The variety of this system is its solution set, which can be obtained using Gaussian elimination. A linear system can have a unique solution, infinitely many solutions, or no solutions at all. Moving on to a more complicated example, we can view the method of Lagrange multipliers in terms of affine variety. Suppose we want to find minima and maxima points of a function, say, f(x,y,z) where the variables are related by g(x,y,z) = c for some constant c in the base field k = \mathbf{R}. The method of Lagrange multipliers shows that \nabla f = \lambda \nabla g at a local minimum or maximum point, where

\nabla f = \left( \frac {\partial f} {\partial x},\; \frac {\partial f} {\partial y},\; \frac {\partial f} {\partial z} \right)

The system of equations resulting from using the method of Lagrange multipliers is an affine variety. A basic fact about affine varieties is that the intersection or union of any two affine varieties V, W \in k^n is again an affine variety.

References

  1. D. Cox, J. Little, and D. O’Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer-Verlag, 1992.
  2. G.-M. Greuel and G. Pfister. A Singular Introduction to Commutative Algebra. Springer-Verlag, 2002.
  3. T. W. Hungerford. Abstract Algebra: An Introduction. Thomson Learning, 2nd edition, 1997.
Advertisements