Introduction

• In these notes, unless otherwise stated, all sets are considered to be proper sets as in ZFC.
• Basic (at least naive) set theory and simple combinatorics knowledge is assumed. Other than that, notes should be self-sufficient.

Note that these notes are still under construction.

Resources Used

• Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra by David Cox, John Little, and Donal O’Shea

Notation

Same as in the Group Theory and Ring Theory notes with the addition of:

• Instead of x_1, ..., x_n, we may write \bar{x} if the context is clear or the size is not a matter of importance for brevity.

Def. Monomial

A monomial in x_1, ..., x_n is a product of the form

where all of the exponents \alpha_1,...,a_\alpha are non-negative integers. The total degree of this monmial is the sum

Notation. Monomial

Let \alpha = (\alpha_1, ..., \alpha_n) be an n-tuple of non-negative integers, then we define

and for \alpha = (0, ..., 0) we have x^\alpha := 1. Moreover, we also define

which denotes the total degree of x^a.

Def. Polynomial

A polynomial f in x_1, ..., x_n with coefficients in the field \mathbb{F} is a finite linear combination of monomials, denoted:

i.e. f is the sum over a finite number of n-tuples \alpha = (\alpha_1, ..., \alpha_n).

Here k_\alpha does not have any special meaning other than the fact that it just used to index the correspoding coefficient for the n-tuple a.

The set of all all polynomials in x_1, ..., x_n with coefficients in \mathbb{F} is denoted with \mathbb{F}[x_1, ..., x_n] or simply by \mathbb{F}[\bar{x}] if the context is clear.

We usually use the lowercase letters f, g, h, p, q, r to denote polynomials.

The k_\alpha is called the coefficient of the monomial x^\alpha. Unless k_\alpha \neq 0, we say k_a x^a is called a term of the polynomial f. The total degree of f denoted by d(f) is the maximum |\alpha| such that the corresponding k_\alpha \neq 0.

So far, all the definitions we have made should be intuitive.

Thm. Polynomials form a Commutative Ring

The set of polynomials \mathbb{F}[x_1, ..., x_n] for any given field \mathbb{F} forms a commutative ring under the standard polynomial addition and multiplication.

Exercise

Def. Algebraically Closed

Given a field \mathbb{F} if every non-constant polynomial in \mathbb{F}[x] has a root in \mathbb{F} we say \mathbb{F} is algebraically closed.

Notice that, \mathbb{F}[x] is the set of polynomials with single indeterminate x unlike \mathbb{F}[x_1, ..., x_n].

Thm. Fundamental Theorem of Algebra

The field of complex numbers \mathbb{C} is algebraically closed. Therefore, every non-constant polynomial f \in \mathbb{C}[x] has a root in \mathbb{C}.

We will not prove this common theorem here. You might want to check out other resources online for a wide range of proofs. However, we will prove a more general theorem called Hilbert Nullstellensatz later on.

Note that \R is not algebraically closed as x^2 + 1 has no roots in \R

Def. Affine Space

Given a field \mathbb{F} and a positive integer n, we define the n-dimensional affine space over \mathbb{F} to be the set

In particular, we call \mathbb{F}^n the affine line for the n=1 and affine plane for n=2.

Notice that given (a_1, ..., a_n) \in \mathbb{F}^n the polynomial f \in \mathbb{F}[x_1, ..., x_n] gives a function f: \mathbb{F}^n \to \mathbb{F} if we replace each x_i by a_i. This is the fundamental idea behind our connection between the algebra and the geometry.

Thm. Infinite Field Polynomials and Zeroes

Let \mathbb{F} be an infinite field, and let f \in \mathbb{F}[x_1, ..., x_n]. Then f = 0 (in \mathbb{F}[x_1, ..., x_n]) if and only if f: \mathbb{F}^n \to \mathbb{F} is the zero function.

Corollary. Polynomial Equality in Infinite Fields

Let \mathbb{F} be an infinite field and let f,g \in \mathbb{F}[x_1, ..., x_n]. Then f=g (in \mathbb{F}[x_1, ..., x_n]) if and only if f and g are the same function.

Exercise

Exercises

Def. (Affine) Variety

Let \mathbb{F} be a field and f_1, ..., f_s \in \mathbb{F}[x_1, ..., x_n], then we define the (affine) variety of f_1, ..., f_s as:

so that \mathbf{V}(f_1, ..., f_s) \subseteq \mathbb{F}^n is the set of all solutions to:

Notice how we used \bar{a} to denote (a_1, ..., a_n) and f(\bar{a}) to denote f(a_1, ..., a_n) where each a_i \in \mathbb{F}.

IMPORTANT: From now on, unless otherwise stated, by variety we will mean the affine variety defined here.

We will commonly use the letter V, W to denote the varieties.

Notice that the graphs of polynomials functions y = f(x) is the variety \mathbf{V}(y - f(x)).

Thm. Basic Properties of Varieties

Let V, W \subseteq \mathbb{F}^n be varieties, then so are V \cup W and V \cap W. Moreover, if V = \bold{V}(f_1,...,f_s) and W = \bold{V}(g_1, ..., g_t), then

1. V \cap W = \bold{V}(f_1,...,f_s,g_1,...,g_t), and
2. V \cup W = \bold{V}(f_i g_j : i = 1,...,s \> \land \> j = 1,...,t)

Exercises

Def. Ideal

A subset S \subseteq \mathbb{F}[\bar{x}] is an (polynomial) ideal of \mathbb{F}[\bar{x}] if

1. 0 \in I
2. f,g \in I \implies f + g \in I
3. f \in I \enspace \land \enspace h \in \mathbb{F}[\bar{x}] \implies hf \in I.

Def. Ideal Generators

Let f_1, f_2, ..., f_s \in \mathbb{F}[\bar{x}], then we define the ideal generated by f_1, ..., f_s as

Exercise that \Braket{f_1, ..., f_s} is indeed an ideal.

Moreover, we say an ideal I is finitely generated if there exists f_1, ..., f_s such that I = \Braket{f_1, ..., f_s} and we say f_1, ..., f_s are a basis of I.

Notice how ideal generated by polynomials is kind of similar to the span of finite number of vectors. Especially with the further facts we will talk about talker such as every ideal in \mathbb{F}[\bar{x}] is finetely generated with a cannoncial basis called Groebner basis.

Thm. Basis and Variety

For two basis for an ideal in \mathbb{F}[\bar{x}] such that \Braket{f_1, ..., f_s} = \Braket{g_1, ..., g_t}, we have

Exercise

Def. Ideal of Variety

Let V \subseteq \mathbb{F}^n be a (affine) variety, then we define the ideal (of) variety V as

Exercise the fact that \bold{I}(V) is indeed an ideal.

Thm. Ideals and Varieties

Let f_1, ..., f_s \in \mathbb{F}[x_1, ..., x_n], then

...and the equality need not to occur (exercise).

Thm. Ideals and Varieties

Let V, W be varieties in \mathbb{F}^n, then

1. V \subseteq W if and only if \bold{I}(V) \supseteq \bold{I}(W).
2. V = W if and only if \bold{I}(V) = \bold{I}(W).

Before we proceed, here are some quetions to ponder about:

• (Ideal Membership) For a finitely generated ideal I, is there any algorithm which decides if any f \in I.
• (Nullstellensatz) What is the exact relation between \Braket{f_1, ..., f_s} and \bold{I}(\bold{V}(f_1, ..., f_s)).

Exercises

Def. Leading Term

Let 0 \neq f \in \mathbb{F}[x] such that

Notice how we indexed the coefficients

where a_i \in \mathbb{F} and a_0 \neq 0. We say a_0 x^m is the leading term of f denoted with

Notice that if f and g are nonzero polynomials we have

d(f) \leq d(g) \iff \text{LT}(f) \mid \text{LT}(g).

Thm. Division Algorithm

Let f,g \in \mathbb{F}[x] where g \neq 0, then there exists unique q,r \in \mathbb{F}[x] such that

where either r = 0 or d(r) < d(g). Moreover, the following program realizes this

<- f, g
 
q <- 0
r <- f
 
WHILE r != 0 AND (LT(g) | LT(r))
    q <- q + LT(r) / LT(g)
    r <- r - (LT(r) / LT(g))g
ENDWHILE
 
-> q, r

Thm. Maximum Number of Roots

Let 0 \neq f \in \mathbb{F}[x], then f has at most d(f) roots in \mathbb{F}.

Exercise, use induction and division fact.

Thm. Ideals of \mathbb{F}[x]

Every ideal of \mathbb{F}[x] can be written as \Braket{f} for some f \in \mathbb{F}[x]. Therefore, every ideal of \mathbb{F}[x] is principal. Moreover, such f is unique up to multiplication by a non-zero constant in \mathbb{F}.

Exercise, use the division fact for a non-zero ideal.

Def. \text{GCD}(\cdot, \cdot)

Let f,g \in \mathbb{F}[x], then we say h \in \mathbb{F}[x] is their greatest common divisor if

1. h \mid f,g
2. p \mid f,g \implies p \mid h

Such h is denoted with

Thm. Basic Properties of \text{GCD}(\cdot, \cdot)

Let f,g \in \mathbb{F}[x], then

1. \text{GCD}(f,g) always exists and is unique up to multiplication by a non-zero constant in \mathbb{F}.
2. \text{GCD}(f,g) is a generator of the ideal \Braket{f,g}.
3. The following algorithm generates h = \text{GCD}(f,g)

Exercise, for (1) and (2) use the corresponding principal ideal.

<- f, g
 
h <- f
s <- g
 
WHILE s != 0
    rem <- remainder of h/s
    h   <- s
    s   <- rem
ENDWHILE
 
-> h

Notice that the algorithm uses the division fact f = qg + r so that

since \Braket{f-qg, g} = \Braket{f,g}.

So, to find a GCD, we repeat the division algorithm until the remainder is 0.

Thm. \text{GCD}(\cdot, \cdot, \cdots)

Let f_1, ..., f_s \in \mathbb{F}[x], then a greatest common divisor of f_1, ..., f_s is defined as h \in \mathbb{F}[x] such that

1. h \mid f_1, ..., f_s
2. p \mid f_1, ..., f_s \implies p \mid h

denoted \text{GCD}(f_1, ..., f_s).

Thm. Basic Properties of Generalized \text{GCD}

Let f_1, ..., f_s \in \mathbb{F}[x], then

1. \text{GCD}(f_1, ..., f_s) exists and unique up to multiplication by a non-zero constant in \mathbb{F}.
2. \text{GCD}(f_1, ..., f_s) is a generator of the ideal \Braket{f_1, ..., f_s}.
3. For s \geq 3, we have \text{GCD}(f_1, ..., f_s) = \text{GCD}(f_1, \text{GCD}(f_2, ..., f_s)).

Exercise. The proof is similar to \text{GCD}(\cdot, \cdot).

1

Find a basis for the ideal \bold{I}(\bold{V}(x^5 − 2x^4 + 2x^2 − x, x^5 − x^4 − 2x^3 + 2x^2 + x − 1)) \subseteq \mathbb{F}[x].

1. For \mathbb{F} = \mathbb{C}, and
2. For any field.

For (2) you can consider whether the field characteristic is 2 or not to check 1 \overset{?}{=} -1.

Def. Monomial Order

A monomial order > on \mathbb{F}[x_1, ..., x_n] is any relation > on \N^n, or equivalently, any relation on the set of monomials x^\alpha that satisfies, for \alpha, \beta \in \N^n

1. > is a total (or linear) order on \N^n
2. \alpha > \beta implies \alpha + \gamma > \beta + \gamma for all \gamma \in \N^n
3. > is a well ordering on \N^n i.e. every non-empty subset of \N^n has a smallest element under >.

Due to Dickson's Lemma (which we will prove later) we could replace (3) with \alpha \geq 0 as (1) and (2) implies (3).

Def. Lexicographic Order

Let \alpha = (\alpha_1, ..., \alpha_n) and \beta = (\beta_1, ..., \beta_n) where \alpha,\beta \in \N^n. The lexiocographic (or lex) order \succ is defined as \alpha \succ \beta if and only if the leftmost non-zero entry is positive in \alpha - \beta .

For example (1,2, 0) \succ (0,3,4) since (1,2,0) - (0,3,4) = (1,-1,4).

From now on, we will write x^\alpha \succ x^\beta if \alpha \succ \beta. We will also use \succcurlyeq to denote \alpha \succ \beta or \alpha = \beta.

Thm. Lexicographic is Monomial

The lexicographic order \succ is a monomial ordering.

Def. Graded Lex Order

Let \alpha = (\alpha_1, ..., \alpha_n) and \beta = (\beta_1, ..., \beta_n) where \alpha,\beta \in \N^n. The graded lexicographic (grlex) order \gg is defined as \alpha \gg \beta if and only if |\alpha| \geq |\beta|, or |\alpha|=|\beta| and \alpha \succ \beta.

Def. Graded Reverse Lex Order

Let \alpha = (\alpha_1, ..., \alpha_n) and \beta = (\beta_1, ..., \beta_n) where \alpha,\beta \in \N^n. The graded reverse lexicographic (grevlex) order \gg is defined as \alpha \gg \beta if and only if |\alpha| \geq |\beta|, or |\alpha|=|\beta| and the rightmost non-zero entry of \alpha - \beta is negative.

Def. Fundamental Definitions

Let f = \sum_\alpha c_\alpha x^\alpha be a polynomial in \mathbb{F}[x_1, ..., x_n] and let > be a monomial order, then we define

1. multidegree of f as: md(f) := \max(\alpha : c_\alpha \neq 0)
2. leading coefficient of f as: \text{LC}(f) := c_{md(f)}
3. leading monomial of f as: \text{LM}(f) := x^{md(f)}
4. leading term of f as: \text{LT}(f) := \text{LC}(f) \cdot \text{LM}(f)

Notice that \max is w.r.t. the monomial order >.

Def. Basic Properties of Monomials

Let f, g \in \mathbb{F}[x_1, ..., x_n] be non-zero polynomials and, then

1. md(fg) = md(f) + md(g)
2. f + g \neq 0 \implies md(f+g) \leq \max(md(f), md(g)). Moreover, they are equal if in addition to f+g\neq 0, we have md(f) \neq md(g).

where < and \leq are the monomial orders. From now on, assume a fixed monomial order > is selected unless otherwise stated.

Thm. Division Algorithm in \mathbb{F}[x_1,...,x_n]

Let F = (f_1, ..., f_s) be an ordered s-tuple of polynomials in \mathbb{F}[x_1, ..., x_n], then every f \in \mathbb{F}[x_1,...,x_n] can be written as

where a_i, r \in \mathbb{F}[x_1, ..., x_n], and either the remainder

• r = 0, or
• r is a linear combination of monomials with coefficients in \mathbb{F}, none of which is divisable by any of \text{LT}(f_1), ..., \text{LT}(f_s).

Moreover, if a_i f_i \neq 0, then md(f) \geq md(a_i f_i).

The following algorithm realizes this

<- (f_1,...,f_s), f
 
(a_1,...,a_s) <- (0,...,0)
p <- f
 
WHILE p != 0
    i <- 1
    divisionOccured <- false
 
    WHILE i <= s AND divisionOccured = false
        IF LT(f_i) | LT(p)
            a_i <- a_i + LT(p) / LT(f_i)
            p   <- p  - (LT(p) / LT(f_i))f_i
            divisionOccured <- true
        ELSE
            i <- i + 1
        ENDIF
    ENDWHILE
 
    IF divisionOccured = false
        r <- r + LT(p)
        p <- p - LT(p)
    ENDIF
ENDWHILE
 
-> (a_1,...,a_s), r

Def. Monomial Ideal

An ideal I \subseteq \mathbb{F}[x_1, ..., x_n] is a monomial ideal if there exists (possibly infinite) basis of monomials so that

Lemma. Membership via Division

Let I = \Braket{x^\alpha : \alpha \in A} be a monomial ideal, then x^\beta \in I if and only if x^\alpha \mid x^\beta for some \alpha \in A.

Lemma. Membership and Equivalence

Let I be a monomial ideal and f \in \mathbb{F}[x_1,...,x_n], then the following are equivalent

1. f \in I.
2. Every term of f lies in I.
3. f is a \mathbb{F}-linear combination of the monomials in I.

Therefore, two monomial ideals are the same if and only if they contain the same monomials.

Thm. Dickson's Lemma

Let I = \Braket{x^\alpha : \alpha \in A} \subseteq \mathbb{F}[x_1,...,x_n] be a monomial ideal, then

Therefore every monomial ideal has a necessarily finite monomial basis.

Def. \text{LT}(I)

Let \Braket{0} \neq I \subseteq \mathbb{F}[x_1,...,x_n] be an ideal, then we define the set of leading terms of I as

Thm. \Braket{\text{LT}(I)}

Let I \subseteq \mathbb{F}[x_1,...,x_n] be an ideal, then

1. \Braket{\text{LT}(I)} is an monomial ideal, and
2. there exists g_1, ..., g_s \in I such that \Braket{\text{LT}(I)} = \Braket{\text{LT}(g_1), ..., \text{LT}(g_s)}.

Thm. Hilbert Basis Theorem

Every ideal I \subseteq \mathbb{F}[x_1,...,x_n] has a finite basis, so that

for some g_1, ..., g_s \in I.

Def. Groebner Basis

Fix a monomial order and let I be an ideal, then a finite subset G = \Set{g_1, ..., g_s} \subseteq I is said to be a Groebner basis (Gr-basis) or standard basis if

Equivalently, \Set{g_1, ..., g_s} is a Gr-basis of I if and only if the leading term of any element of I is divisible by one of \text{LT}(g_i).

Thm. Existence of Gr-basis

Every non-zero ideal I \subseteq \mathbb{F}[x_1,...,x_n] has a Groebner basis. Moreover, any Groebner basis of I is a basis of I.

Thm. ACC

Let I_1 \subseteq I_2 \subseteq \cdots be an asceding chain of ideals in \mathbb{F}[x_1, ..., x_n], then there exists an N \geq 1 so that I_N = I_{N+i} for all i \in \N.

Def. \bold{V}(I)

Let I \subseteq \mathbb{F}[x_1, ..., x_n] be an ideal, then we define the variety of I as

Thm. Varieties are Determined by Ideals

Let I be an ideal, then \bold{V}(I) is indeed an (affine) variety. Moreover, if I = \Braket{f_1, ..., f_s}, then

Therefore, varieties are determined by ideals.

Thm. Normal Form

Let G = \Set{g_1, ..., g_s} be a Gr-basis for an ideal I \subseteq \mathbb{F}[x_1, ..., x_n] and f \in \mathbb{F}[x_1,...,x_n], then there exists an unique r \in \mathbb{F}[x_1,...,x_n] such that

1. no term of r is divisible by any of \text{LT}(g_1), ..., \text{LT}(g_s), and
2. there exists g \in I so that f = g + r

In particular, r is the remainder on division of f by G (no matter how the elements of G are listed) using the division algorithm.

Such r is called the normal form of f.

Corollary. Membership via Division

Let G = \Set{g_1, ..., g_s} be a Gr-basis for an ideal I \subseteq \mathbb{F}[x_1, ..., x_n] and f \in \mathbb{F}[x_1, ..., x_n], then f \in I if and only if G \mid f i.e. division of f by G is zero.

Notation. Remainder

Let F = (f_1, ..., f_s) be an orderer s-tuple. We will denote the remainder of f by division of F with

Notice that if \Set{f_1, ..., f_s} is a Gr-basis for \Braket{f_1, ..., f_s}, the order of F doesn't matter.

Def. \text{LCM} of Monomials

Let f,g \in \mathbb{F}[x_1, ..., x_n] be non-zero polynomials where md(f) = \alpha and md(g) = \beta, and

We call x^\gamma the least common multiplier of \text{LM}(f) and \text{LM}(g), denoted with

Def. \bold{S}-polynomial

Let f,g \in \mathbb{F}[x_1,...,x_n], then we define their \bold{S}-polynomial as

where x^\gamma = \text{LCM}(\small \text{LM}(f), \text{LM}(g) \normalsize).

Note that we are inverting the leading coefficients here as well.

Thm. Buchberger’s Criterion

Let I be an ideal, then a basis G = \Set{g_1, ..., g_s} is a Gr-basis for I if and only if for all pairs i \neq j, we have G \mid \bold{S}(f,g).