Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra

---

Chapter 1

Section 1

-Field: set defined for +, -, *, / with the usual properties, (eg. Q, R, and C)

-A monomial in x₁,...,x_n is a product of the form x₁^alp1*x₂^alp2*...*x_n^alpn, where alp₁,...alp_n=0. The total degree of the monomial is alp₁+alp₂+...+alp_n

-alp=(alp₁,...,alp_n) and |alp|=alp₁+alp₂+...+alp_n

-A polynomial f in x₁,...,x_n with coefficients in and field k is a finite linear combination of monomials. f is written in the form E_alp A_alpx^alp, A_alp contained in k, where the sum over a finite number of n-tuples alp=(alp₁,...alp_n). The set of all polynomials in x₁,...,x_n with coefficients in k is denoted k[x₁,...,x_n]
-Let f=E_alp A_alp*x^alp be a polynomial in k[x₁,...,x_n]. Then (1)A_alp is the coefficient of the monomial x^alp; (2)If A_alp does not =0, then A_alp*x^alp is a term of f; (3)The total degree of f, deg(f), is the maximum |alp| such that A_alp does not =0

- k[x1,...xn] is a polynomial ring (no multiplicative inverse)
-The n-dimensional affine space of a field k is the set kⁿ={(a₁, ...a_n):a₁,a₂,...,a_n contained in k}

-A field k is algebraically closed if every nonconstant polynomial in k[x] has a root in k

Section 2

-Let k be a field, and let f₁,...,f_s be polynomials in k[x₁,...,x_n]. Then V(f₁,...,f_s)={(a₁,...,a_n)contained in k:f₁(a₁,...,a_n)=0 for all 1<=i<=s}. V(f₁,...,f_s) is the affine variety defined by f₁,...,f_s.

-V(f₁,...,f_s) is the set of solutions of f₁(x₁,...,x_n)=...=f_s(x₁,...,x_n)=0

-affine varieties in R:graphs of polynomials f, etc.

Circle, R²: V(x²+y²-1)

R³: V(x²-y²*z²+z³)

Twisted Cubic: V(y-x², z-x³)

-Robot Arm:

Section 3

-parametrization: find x₁,...,x_n in terms of t₁,...,t_m

-A rational function in t₁,...,t_m with coefficients in k is a quotient f/g of two polynomials f,g contained in k[t₁,...,t_m], where g is not the zero polynomial.

-Two rational functions f/g and h/k are equal if k*f=g*h in k[t₁,...,t_m].

-The set of all rational functions in t₁,...,t_m with coefficients in k is denoted k(t₁,...,t_m), which is a field.

Section 4

-A subset I of k[x₁,...,x_n] is an ideal if: (1)0 is contained in I; (2)If f,g and contained in I, then f+g is also contained in I; (3)If fis contained in I and h is contained in k[x₁,...,x_n], then h*f is contained in I

-Let f₁,...,f_s be polynomials in k[x1,...,xn], then set ={E_i=1^s h_i*f_i: h1,...,hs contained in k[x1,...,xn]}; < f₁,...,f_s> is an ideal.

-if f₁,...,f_s contained in k[x₁,...,x_n], then < f₁,...,f_s> is an ideal of k[x₁,...,x_n]. < f₁,...,f_s> is an ideal generated by f₁,...,f_s

-< f₁,...,f_s> are all the polynomial consequences of f₁,...,f_s

-An ideal I is finitely generated if there exists f₁,...,f_s contained in k[x₁,...,x_n] such that I=< f₁,...,f_s> and f₁,...,f_s are a basis of I

-Let V subset of kⁿ be an affine variety. Then set I(V)={f contained in k[x₁,...,x_n]: f(a₁,...a_n)=0 for all (a₁,...,a_n)contained in V}; I(V) is an ideal, the ideal of V.

Section 5

-Given a nonzero polynomial f contained in k[x], let f=a₀x^m+a₁x^m-1+...+a_m, where a_i is contained in k and a₀ does not equal 0 [m=deg(f)]. Then a₀x^m is the leading term of f, LT(f)=a₀x^m

-Let k be a field and g be a nonzero polynomial in k[x]. Then every f in k[x] can be written as f=q*g+r, where q, r are in k[x] and either r=0, or deg(r)< deg(g). q and r are unique and there is an algorithm for finding q and r...

-Division Algorithm
Input: g,f
Output: q,r
q:=0; r:=f
WHILE r does not =0 AND LT(g) divides LT(r) DO q:=q+LT(r)/LT(g)
r:=r-(LT(r)/LT(g))/g

-If k is a field and f in k[x] is a nonzero polynomial, then f has at most deg(f) roots in k.

-If k is a field, then every ideal of k[x] can be written in the form for some f in k[x]. f is unique up to multiplication by a nonzero constant of k.

-A greatest common divisor of polynomials f,g in k[x] is a polynomial h such that: (1)h divides fand g; (2)If p is another polynomial which divides f and g, then p divides h. Then GCD(f,g)=h.

-Let f,g be in k[x]. Then (1)GCD(f,g) exists and is unique up to multiplication by a nonzero constant k; (2)GCD(f,g) is a generator of the ideal < f,g>; (3)There is an algorithm for finding GCD(f,g)...

-Input: f,g
Output:h
h:=f
s:=g
WHILE s does not =0 DO
rem:=remainder(h,s)
h:=s
s:=rem

-A greatest common divisor of polynomials f₁,...,f_s in k[x] is a polynomial such that: (1)h divides f and g; (2)If p is another polynomial which divides f₁,...,f_s, then p divides h. Then h=GCD(f₁,...,f_s)

-Let f₁,...,f_s be in k[x], where s>=2, Then: (1)GCD(f₁,...,f_s) exists and is unique up to multiplication by a nonzero constant; (2)GCD(f₁,...,f_s) is a generator of the ideal < f₁,...,f_s>; (3)If s>=3, then GCD(f₁,...,f_s)=GCD(f₁,GCD(f₂...,f_s)); (4)There is an algorithm for finding GCD(f₁,...,f_s)

Chapter 2

Section 2

-A monomial ordering on k[x₁,...,x_n] is any relation > on Zⁿ_>=0, or equivalently, any relation on the set of monomials x^alp, alp in Zⁿ_>=0, satisfying: (1) > is a total (or linear) ordering on Zⁿ_>=0; (2)If a>b and g are in Zⁿ_>=0, then a+g>b+g; (3) > is a well-ordering on Zⁿ_>=0. This means that every nonempty subset of Zⁿ_>=0 has a smallest element under >.

-An order relation > on Zⁿ_>=0 is a well ordering if and only if every strictly decreasing sequence in Zⁿ_>=0 a(1)>a(2)>a(3)>... eventually terminates

-Lexicographic Order: Let a=(a₁,...,a_n) and b=(b₁,...,b_n) are in Zⁿ_>=0. We say a >_lexb if, in the difference vector a-b in Zⁿ, the left-most nonzero entry is positive. We will write x^a >_lex x^b if a >_lexb

-Graded Lexicographic Order: Let a,b be in Zⁿ_>=0. We say a >_grlexb if |a|>|b|, or |a|>|b| and a >_lexb

-Graded Reverse Lexicographic Order: Let a,b be in Zⁿ_>=0. We say a >_grevlexb if |a|>|b| or |a|>|b| and, in a-b in Zⁿ the right-most nonzeroentry is negative

-Let f=E_alp A_alp*x^alp be a nonzero polynomial in k[x₁,...,x_n] and let > be a monomial order: (1) the multidegree of f is multideg(f)=max(alp in Zⁿ_>=0: A_alp does not =0), (the maximum is taken with respect to >); (2)The leading coefficient of f is LC(f)=A_mutideg(f) in k; (3)The leading monomial of f is LM(f)=x^multideg(f) , (with a coefficient of 1); (4)The leading term of f is LT(f)=LC(f)*LM(f)

-Let f,g in k[x₁,...,x_n] be nonzero polynomials. Then (1)multideg(fg)=multideg(f)+multideg(g); (2)If f+g does not =0, then multideg(f+g)<=max(multideg(f), multideg(g)); If, in addition, mulitdeg(f) does not = multideg(g), then equality occurs.

Section 3

Section 4

-An ideal I of k[x₁,...,x_n] is a monomial ideal if there is a subset A of Zⁿ_>=0 (possibly infinite) such that I consists of all polynomials which are finite sums of the form E_{a in A} h_ax^a, where h_a is in k[x₁,...,x_n]. We write I=< x^a: a in A >

-Let I=< x^a: a in A > be a monomial ideal. Then a monomial x^b lies in I if and only if x^b is divisible by x^a for some a in A

-Let I be a monomial ideal, and let f be in k[x₁,...,x_n]. Then the following are equivalent: (1)f is in I; (2)Every term of f ies in I; (3)f is a k-linear combination of the monomials in I

-Two monomial ideals are the same if and only if they contain the same monomials

-Dickson's Lemma: A monomial ideal I=< x^a: a in A > in k[x₁,...,x_n] can be written in the form I=< x^a(1),...,x^a(s) >, where a(1),...a(s) is in A. In particular, I has a finite basis

-Let > be a relation on Zⁿ_>=0 satisfying: (1) > is a total ordering on Zⁿ_>=0; (2)if a > b and g are in Zⁿ_>=0, then a+g > b+g; Then > is a well-ordering if and only if a>=0 for all a in Zⁿ_>=0

Section 5

-Let I a subset of k[x₁,...,x_n] be an ideal other than {0}: (1)LT(I) is the set of leading terms of elements of I, Thus LT(I)={cx^a:there exists f in I with LT(f)=cx^a}; (2) < LT(I) > is the ideal generated by the elements of LT(I)

-Let I of k[x₁,...,x_n] be an ideal: (1)< LT(I) > is a monomial ideal; (2) There are g₁,...,g_t in I such that < LT(I) >=< LT(g₁),...,LT(g_t) >

-Hilbert Basis Theorem: Every ideal I of k[x₁,...,x_n] has a finite generating set. That is, I=< g₁,...,g_t > for some g₁,...,g_t in I

-Fix a monomial order. A finite subset G={g₁,...,g_t} of an ideal I is said to be a Groebner basis (or standard basis) if < LT(g₁),...,LT(g_t) >=< LT(I) >, ie. a set {g₁,...,g_t} is a Groebner basis if and only if the leading term of any element of I is divisible by one of LT(g_i)

-Fix a monomial order. Then every ideal I of k[x₁,...,x_n] other than {0} has a Groebner basis, also, any Groebner basis for an ideal I is a basis of I

-an ascending chain of ideals is a nested, increasing sequence I₁ of I₂ of I₃ of...

-The Ascending Chain Condition: Let I₁ of I₂ of I₃ of... be an ascending chain of ideals in k[x₁,...,x_n]. Then there exists an N>=1 such that I_N=I_N+1=I_N+2=...

-Let I of k[x₁,...,x_n] be an ideal. We will denote by V(I) the set {(a₁,...,a_n) in kⁿ:f(a₁,...,a_n)=0 for all f in I}

-V(I) is an affine variety. In particular, if I=< f₁,...,f_s >, then V(I)=V(f₁,...,f_s)

Section 6

-Let G={g₁,...,g_t} be a Groebner basis for an ideal I of k[x₁,...,x_n] and let f be in I. Then there is a unique r in k[x₁,...,x_n] with the following properties: (1) No term in r is divisible by one of LT(g₁),...,LT(g_t); (2) There is a g in I such that f=g+r

-Let G={g₁,...,g_t} be a Groebner basis for an ideal I of k[x₁,...,x_n] and let f be in k[x₁,...,x_n]. Then f is in I if and only if the remainder on division of f by G is zero

-We will write f^--F for the remainder on division of f by the s-tuple F=(f₁,...,f_s). If F is a Groebner basis for < f₁,...,f_s >, then we can regard F as a set (without any particular order)

-Let f,g in k[x₁,...,x_n] be nonzero polynomials: (1)If multideg(f)=a and multideg(g)=b, then let j=(j₁,...,j_n), where j_i=max(a_i,b_i) for each i. We call x^j the least common multiple of LM(f) and LM(g), written x^j=LCM(LM(f),LM(g)); (2) The S-polynomial of f and g is the combination S(f,g)=((x^j/LT(f))*f)-((x^j/LT(g))*g))

-Let I be a polynomial ideal. Then a basis G={g₁,...,g_t} for I is a Groebner basis for I if and only if for all pairs i not = to j, the remainder on division of S(g_i,g_j) by G (listed in some order) is zero

Section 7

Let I=< f₁,...,f_s > not equal to 0 be a polynomial ideal. Then a Groebner basis for I can be constructed in a finite number of steps by the following algorithm:
Input: F=(f₁,...,f_s)
Output: a Groebner basis G=(g₁,...,g_t) for I, with F in G
G:=F
REPEAT
G':=G
FOR each pair {p,q}, p not equal to q in G' DO
S:=S(p,q)^--G'
IF S does not =0 THEN G:=G union {S}
UNTIL G=G'

-Let G be a Groebner basis for the polynomial ideal I. Let p in G be a polynomial such that LT(p) is in < LT(G-{p}) >. Then G-{p} is also a Groebner basis for I

-A minimal Groebner basis for a polynomial ideal I is a Groebner basis G for I such that: (1) LC(p)=1 for all p in G; (2) for all p in G, LT(p) is not in < LT(G-{p}) >

-A reduced Groebner basis for a polynomial I is a Groebner basis for I such that: (1) LC(p)=1 for all p in G; (2) for all p in g, no monomial of p lies in < LT(G-{p}) >

-Let I not ={0} be a polynomial ideal. Then, for a given monomial ordering, I has a unique reduced Groebner basis

-ideal equality algorithm: fix a monomial order and compute a reduced Groebner basis for < f₁,...,f_s > and < g₁,...,g_t >. Then the ideals are equal if and only if the Groebner bases are the same

Section 8

-ideal membership algorithm: given an ideal I=< f₁,...,f_s > is f in I? First find a Groebner basis G={g₁,...,g_t} for I. f is in I if and only if f^--G=0

-solving equations: lex order, find G, solve by back substitution

Section 9

-Fix a monomial order and let G={g₁,...,g_t} of k[x₁,...,x_n]. Given f in k[x₁,...,x_n], we say that f reduces to zero modulo G, written f->_G0 if f can be written in the form f=a₁g₁,...,a_tg_t such that whenever a_ig_i does not =0 we have multideg(f)>=multideg(a_ig_i)

-Let G=(g₁,...,g_s) be an ordered set of elements of k[x₁,...,x_n] and fix f in k[x₁,...,x_n]. Then f^--G=0 implies f->_G0, though the converse is false in general

-A basis G={g₁,...,g_t} for an ideal I is a Groebner basis if and only if S(g_i,g_j)->_G0 for all i not =j

-Given a finite set G of k[x₁,...,x_n] suppose f,g in G such that LCM(LM(f),LM(g))=LM(f)*LM(g). This means that the leading monomials of f and g are relatively prime. Then S(f,g)->0

-Let F=(f₁,...,f_s). A syzygy on the leading terms LT(f₁,...,LT(f_s) of F is an s-tuple of polynomials S=(h₁,...,h_s) in (k[x₁,...,x_n])^s such that the sum from i=1 to s of h_i*LT(f_i)=0. We let S(F) be the subset of (k[x₁,...,x_n])^s consisting of all syzygies on the leading terms of F.

Back to Week 1

Back to Week 2

Back to Week 2

Home