Logo

Chapter 9: Polynomial Rings

9.1 Definitions and Basic Properties

Proposition 1: Let RR be an integral domain. Then

Proposition 2: Let II be an ideal of the ring RR and let (I)=I[x](I)=I[x] denote the ideal of R[x]R[x] generated by II (polynomials with coefficients in II). Then R[x]/(I)≅(R/I)[x]R[x]/(I)\cong(R/I)[x]. In particular, if II is a prime ideal of RR then (I)(I) is a prime ideal of R[x]R[x].
Fact: If II is as described above and II is a maximal ideal of RR, (I,x)⊆R[x](I,x)\subseteq R[x] is a maximal ideal too. (I)(I) is not necessarily maximal in R[x]R[x].
Definition: The polynomial ring in variables x1,…,xnx_{1},\dots,x_{n} with coefficients in RR is denoted R[x1,…,xn]R[x_{1},\dots,x_{n}] and defined inductively by R[x1,…,xn]=R[x1,…,xn−1][xn]R[x_{1},\dots,x_{n}]=R[x_{1},\dots,x_{n-1}][x_{n}].
Fact: The degree of a multivariate monomial is the largest sum of the degrees of each variable taken individually. The degree of a multivariate polynomial is the maximum degree of its monomials. The subsum of a polynomial ff including only the monomial terms of degree kk is denoted the homogeneous component of ff of degree kk. If ff has degree dd, it is possible to express f=∑i=0dfif=\sum_{i=0}^{d}f_{i} for homogeneous components fif_{i} of degree ii.

9.2 Polynomial Rings over Fields I

Theorem 3: Let FF be a field. The polynomial ring F[x]F[x] is a Euclidean Domain. That is, letting a(x),b(x)∈F[x]a(x),b(x)\in F[x] with b(x)≠0b(x) \neq 0, then there exist unique q(x),r(x)∈F[x]q(x),r(x)\in F[x] such that a(x)=q(x)b(x)+r(x)a(x)=q(x)b(x)+r(x) with r(x)=0r(x)=0 or deg  r(x)<deg  b(x)\mathrm{deg\;}r(x)<\mathrm{deg\;}b(x). (deg\mathrm{deg} is the norm).
Corollary 4: If FF is a field, then F[x]F[x] is a PID and UFD (since it is already a Euclidean Domain).

9.3 Polynomial Rings that are Unique Factorization Domains

Proposition 5: (Gauss's Lemma) Let RR be a UFD with field of fractions FF and let p(x)∈R[x]p(x)\in R[x]. If p(x)p(x) is reducible in F[x]F[x] then p(x)p(x) is reducible in R[x]R[x]. More precisely, if p(x)=A(x)B(x)p(x)=A(x)B(x) for some nonconstant polynomials A(x),B(x)∈F[x]A(x),B(x)\in F[x], then ∃r,s∈F\exists r,s \in F with r,s≠0r,s \neq 0 such that rA(x)=a(x)rA(x)=a(x) and sB(x)=b(x)sB(x)=b(x), a(x),b(x)∈R[x]a(x),b(x)\in R[x], and p(x)=a(x)b(x)p(x)=a(x)b(x) is a factorization in RR.
Corollary 6: Let RR be a UFD, FF be its fields of fractions, and p(x)∈R[x]p(x)\in R[x]. Suppose the gcd of the coefficients of p(x)p(x) is 11. Then p(x)p(x) is irreducible in R[x]R[x]   ⟺  \iff it is irreducible in F[x]F[x]. In particular, if p(x)p(x) is monic and irreducible in R[x]R[x] then p(x)p(x) is irreducible in F[x]F[x]. An important implication of this is that a monic polynomial in Z[x]\mathbb{Z}[x] is irreducible   ⟺  \iff it is irreducible over Q[x]\mathbb{Q}[x]. (Can also be applied to polynomials in Q[x]\mathbb{Q}[x] with only integer coefficients).
Theorem 7: RR is a UFD   ⟺  \iff R[x]R[x] is a UFD.
Corollary 8: If RR is a UFD, then a multivariate polynomial ring with coefficients in RR is also a UFD.

9.4 Irreducibility Criteria

Proposition 9: Let FF be a field and let p(x)∈F[x]p(x)\in F[x]. Then p(x)p(x) has a factor of degree 11   ⟺  \iff ∃α∈F\exists\alpha \in F with p(α)=0p(\alpha)=0.
Proposition 10: A polynomial with deg=2\mathrm{deg}=2 or 33 over a field FF is reducible   ⟺  \iff it has a root in FF.
Proposition 11: (Rational Root Theorem) Let p(x)=anxn+⋯+a0∈Z[x]p(x)=a_{n}x_{n}+\dots+a_{0}\in \mathbb{Z}[x]. If rs∈Q\frac{r}{s}\in \mathbb{Q} in the lowest terms and p(rs)=0p\left( \frac{r}{s} \right) = 0, then rr divides the constant term and ss divides the leading coefficient of p(x)p(x): r∣a0r \mid a_{0} and s∣ans\mid a_{n}. In particular, if p(x)p(x) is monic with integer coefficients and p(d)≠0,  ∀d∈Zp(d) \neq 0,\;\forall d\in \mathbb{Z} such that d∣a0d \mid a_{0}, then p(x)p(x) has no roots in Q\mathbb{Q}. More precisely, if p(x)∈Z[x]p(x)\in \mathbb{Z}[x] and is monic, all rational roots must be integers.
Proposition 12: Let II be a proper ideal in the integral domain RR and let p(x)p(x) be a nonconstant monic polynomial in R[x]R[x]. If the image of p(x)p(x) in (R/I)[x](R/I)[x] cannot be factored in (R/I)[x](R/I)[x] into two polynomials of smaller degree, then p(x)p(x) is irreducible in R[x]R[x].
Proposition 13: (Eisenstein's Criterion) Let PP be a prime ideal of the integral domain RR and let f(x)=xn+an−1xn−1+⋯+a0∈R[x]f(x)=x^{n}+a_{n-1}x^{n-1}+\dots+a_{0}\in R[x] (n≥1n\geq1). Suppose an−1,…,a0∈Pa_{n-1},\dots,a_{0}\in P and a0∉P2a_{0}\not\in P^{2}. Then f(x)f(x) is irreducible in R[x]R[x].
Corollary 14: (Eisenstein's Criterion for Z[x]\mathbb{Z}[x]) Let prime p∈Zp \in \mathbb{Z} and f(x)=xn+an−1xn−1+⋯+a0∈Z[x]f(x)=x^{n}+a_{n-1}x^{n-1}+\dots+a_{0}\in \mathbb{Z}[x], n≥1n\geq1. Suppose p∣ai, ∀i∈{0,…,n−1}p \mid a_{i},\ \forall i\in \{ 0,\dots,n-1 \} but p2∤a0p^{2} \nmid a_{0}. Then f(x)f(x) is irreducible in both Z[x]\mathbb{Z}[x] and Q[x]\mathbb{Q}[x].

9.5 Polynomial Rings over Fields II

Let FF be a field.
Proposition 15: The maximal ideals in F[x]F[x] are the ideals (f(x))(f(x)) generated by irreducible polynomials f(x)f(x). In particular, F[x]/(f(x))F[x]/(f(x)) is a field   ⟺  \iff f(x)f(x) is irreducible.
Proposition 16: Let g(x)g(x) be a nonconstant monic element of F[x]F[x] and let g(x)=f1(x)n1…fk(x)nkg(x)=f_{1}(x)^{n_{1}}\dots f_{k}(x)^{n_{k}} be its irreducible factorization. Then we have the following ring isomorphism: F[x]/(g(x))≅F[x]/(f1(x)n1)×⋯×F[x]/(fk(x)nk)F[x]/(g(x))\cong F[x]/(f_{1}(x)^{n_{1}})\times\dots \times F[x]/(f_{k}(x)^{n_{k}}).
Proposition 17: If the polynomial f(x)f(x) has roots α1,…,αk∈F\alpha_{1},\dots,\alpha_{k}\in F (not necessarily distinct), then (x−α1)…(x−αk)∣f(x)(x-\alpha_{1})\dots(x-\alpha_{k}) \mid f(x). In particular, a univariate polynomial of degree nn over FF has at most nn roots in FF, even with multiplicity.
Proposition 18: A finite subgroup of the multiplicative group of a field is cyclic. In particular, if FF is a finite field, then the multiplicative group F×F^{\times} of nonzero elements of FF is a cyclic group.
Corollary 19: Let pp be a prime. The multiplicative group (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^{\times} of nonzero residue classes mod pp is cyclic. (Since (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^{\times} is a finite field).
Corollary 20: Let n≥2n\geq 2 be an integer with factorization n=p1α1..prαrn=p_{1}^{\alpha_{1}}..p_{r}^{\alpha_{r}} in Z\mathbb{Z}, where p1,…prp_{1},\dots p_{r} are distinct primes. Then, the following isomorphisms of multiplicative groups exist:

9.6 Polynomials in Several Variables over a Field and Gröbner Bases

Definition: A commutative ring RR with 11 is called Noetherian if every ideal of RR is finitely generated.
Theorem 21: (Hilbert's Basis Theorem) If RR is a Noetherian ring then so is the polynomial ring R[x]R[x].
Corollary 22: Every ideal in the polynomial ring F[x1,…,xn]F[x_{1},\dots,x_{n}] with coefficients from a field FF is finitely generated.
Definition: A monomial ordering is a well ordering "≥\geq" on the set of monomials that satisfies mm1≥mm2mm_{1}\geq mm_{2} whenever m1≥m2m_{1}\geq m_{2} for monomials m,m1,m2m,m_{1},m_{2}. Equivalently, a monomial ordering may be specified by defining a well ordering on the nn-tuples α=(a1,…,an)∈Zn\alpha=(a_{1},\dots,a_{n})\in \mathbb{Z}^{n} of multidegrees of monomials Ax1a1…xnanAx_{1}^{a_{1}}\dots x_{n}^{a_{n}} that satisfies α+γ≥β+γ\alpha+\gamma\geq\beta+\gamma if α≥β\alpha\geq\beta.
Definition: Fix a monomial ordering on the polynomial ring F[x1,…,xn]F[x_{1},\dots,x_{n}].

Fact: LT(fg)=LT(f)+LT(G)LT(fg)=LT(f)+LT(G). The ideal LT(I)LT(I) is also generated by monomials; such ideals are denoted as monomial ideals. A polynomial is contained in a monomial ideal   ⟺  \iff each of its monomial terms is a multiple of one of the ideal's generators.
Definition: A Gröbner basis for an ideal II in the polynomial ring F[x1,…,xn]F[x_{1},\dots,x_{n}] is a finite set of generators {g1,…,gm}\{ g_{1},\dots,g_{m} \} for II whose leading terms generate the ideal of all leading terms in II, i.e. I=(g1,…,gm)I=(g_{1},\dots,g_{m}) and LT(I)=(LT(g1),…,LT(gm))LT(I)=(LT(g_{1}),\dots,LT(g_{m})).
Fact: Every element in II is a linear combination of the generators that is not necessarily unique.
General Polynomial Division: Fix a monomial ordering on F[x1,…,xn]F[x_{1},\dots,x_{n}] and suppose g1,…,gmg_{1},\dots,g_{m} is a set of nonzero polynomials in F[x1,…,xn]F[x_{1},\dots,x_{n}]. If f∈F[x1,…,xn]f\in F[x_{1},\dots,x_{n}], start with a set of quotients q1,…,qmq_{1},\dots,q_{m} and a remainder rr all equal to 00. Then, recursively test if the leading term of ff is divisible by the any of the leading terms of the divisors g1,…,gmg_{1},\dots,g_{m} in that order.

Theorem 23: Fix a monomial ordering on R=F[x1,…,xn]R=F[x_{1},\dots,x_{n}] and suppose {g1,…,gm}\{ g_{1},\dots,g_{m} \} is a Gröbner basis for the nonzero ideal II in RR. Then

Proposition 24: Fix a monomial ordering on R=F[x1,…,xn]R=F[x_{1},\dots,x_{n}] and let II be a nonzero ideal in RR.

Fact: Let MM be the monic LCM of LT(f1)LT(f_{1}) and LT(f2)LT(f_{2}). Define S(f1,f2)=MLT(f1)f1−MLT(f2)f2S(f_{1},f_{2})=\frac{M}{LT(f_{1})}f_{1}-\frac{M}{LT(f_{2})}f_{2}. Then S(f1,f2)S(f_{1},f_{2}) is a polynomial where the leading terms of f1f_{1} and f2f_{2} have been canceled.
Lemma 25: Suppose f1,…,fm∈F[x1,…,xn]f_{1},\dots,f_{m}\in F[x_{1},\dots,x_{n}] are polynomials with the same multidegree α\alpha and that the linear combination h=a1f1+⋯+amfmh=a_{1}f_{1}+\dots+a_{m}f_{m} with constants ai∈Fa_{i}\in F has a multidegree strictly smaller than α\alpha. Then h=∑i=2mbiS(fi−1,fi)h=\sum_{i=2}^{m}b_{i}S(f_{i-1},f_{i}) for some constants bi∈Fb_{i}\in F.
Fact: For a fixed monomial ordering on R=F[x1,…,xn]R=F[x_{1},\dots,x_{n}] and ordered set of polynomials G={g1,…,gm}G=\{ g_{1},\dots, g_{m} \} in RR, write f≡r  (mod  G)f\equiv r\; (\text{mod} \; G ) if rr is the remainder of general polynomial division of f∈Rf\in R by g1,…,gmg_{1},\dots,g_{m} in that order.
Proposition 26: (Buchberger's Criterion) Let R=F[x1,…,xn]R=F[x_{1},\dots,x_{n}] and fix a monomial ordering on RR. If I={g1,…,gm}I=\{ g_{1},\dots,g_{m} \} is a nonzero ideal in RR, then G={g1,…,gm}G=\{ g_{1},\dots,g_{m} \} is a Gröbner basis for II   ⟺  S(gi,gj)≡0  (mod  G), 1≤i<j≤m\iff S(g_{i},g_{j})\equiv 0\; (\text{mod} \; G ),\ 1\leq i<j\leq m.
Buchberger's Algorithm: Let ideal I=(g1,…,gm)I=(g_{1},\dots,g_{m}) and G={g1,…,gm}G=\{ g_{1},\dots,g_{m} \}. Let S(gi,gj)S(g_{i},g_{j}) have r≠0r \neq 0 for some ordered pair (i,j)(i,j). (Otherwise, if S(gi,gj)=0, ∀(i,j)S(g_{i},g_{j})=0,\ \forall (i,j), then GG is a Gröbner basis). Modify GG to be G′=G∪{r}G'=G\cup \{ r \}. Iterate until done. Note that this will always terminate after a finite number of sets since there exist finitely many ordered pairs (i,j)(i,j).
Fact: If G={g1,…,gm}G=\{ g_{1},\dots,g_{m} \} is a Gröbner basis for the ideal II and LT(gi)∣LT(gj)LT(g_{i}) \mid LT(g_{j}) for some j≠ij \neq i, then G−{gj}G-\{ g_{j} \} is still a valid Gröbner basis. Therefore, we may assume that the LT(gi), ∀iLT(g_{i}),\ \forall i is monic. Then, a Gröbner basis G={g1,…,gm}G=\{ g_{1},\dots,g_{m} \} for II is called minimal if LT(gi)LT(g_{i}) is monic ∀i\forall i and LT(gi)∤LT(gj), ∀(i,j)LT(g_{i}) \nmid LT(g_{j}),\ \forall(i,j). (This is analogous to a linear independent basis in vector spaces). Note also that while a minimal Gröbner basis is not necessarily unique, the number of elements and their leading terms are unique.
Definition: Fix a monomial ordering on R=F[x1,…,xn]R=F[x_{1},\dots,x_{n}]. A Gröbner basis {g1,…,gm}\{ g_{1},\dots,g_{m} \} for a nonzero ideal II in RR is called a reduced Gröbner basis if (a) LT(gi)LT(g_{i}) is monic ∀i\forall i and (b) no term in gjg_{j} is divisible by LT(gi), ∀(i,j)LT(g_{i}),\ \forall (i,j) where i≠ji \neq j.
Fact: A reduced Gröbner basis is also clearly minimal.
Theorem 27: Fix a monomial ordering on R=F[x1,…,xn]R=F[x_{1},\dots,x_{n}]. Then there is a unique reduced Gröbner basis for every nonzero ideal II in RR.
Corollary 28: Let I,JI,J be ideals in F[x1,…,xn]F[x_{1},\dots,x_{n}]. Then I=J  ⟺  I=J\iff II and JJ have the same reduced Gröbner basis with respect to any fixed monomial ordering on F[x1,…,xn]F[x_{1},\dots,x_{n}].
Definition: If II is an ideal in F[x1,…,xn]F[x_{1},\dots,x_{n}] then Ii=I∩F[xi+1,…,xn]=I_{i}=I\cap F[x_{i+1},\dots,x_{n}]= set of polynomials in II that do not involve the variables x1,…,xix_{1},\dots,x_{i} is called the iith elimination ideal of II with respect to the lexicographic monomial ordering x1>⋯>xnx_{1}>\dots>x_{n}.
Proposition 29: (Elimination) Suppose G={g1,…,gm}G=\{ g_{1},\dots,g_{m} \} is a Gröbner basis for the nonzero ideal II in F[x1,…,xn]F[x_{1},\dots,x_{n}] with respect to the above ordering. Then G∩F[xi+1,…,xn]G\cap F[x_{i+1},\dots,x_{n}] is a Gröbner basis of the iith elimination ideal defined above. In particular, I∩F[xi+1,…,xn]=0  ⟺  G∩F[xi+1,…,xn]=∅I\cap F[x_{i+1},\dots,x_{n}]=0\iff G\cap F[x_{i+1},\dots,x_{n}]=\emptyset.
Fact: Let I,JI,J b e ideals in F[x1,…,x)n]F[x_{1},\dots,x)_{n}] with I=(f1,…,fs)I=(f_{1},\dots,f_{s}) and J=(h1,…,ht)J=(h_{1},\dots,h_{t}). Then I+J=(f1,…,fs,h1,…,ht)I+J=(f_{1},\dots,f_{s},h_{1},\dots,h_{t}) and IJ=(f1h1,…,fihj,…,fsht)IJ=(f_{1}h_{1},\dots,f_{i}h_{j},\dots,f_{s}h_{t}).
Proposition 30: IF I,JI,J are ideals in F[x1,…,xn]F[x_{1},\dots,x_{n}] then tI+(1−t)JtI+(1-t)J is an ideal in F[t,x1,…,xn]F[t,x_{1},\dots,x_{n}] and I∩J=(tI+(1−t)J)∩F[x1,…,xn]I\cap J=(tI+(1-t)J)\cap F[x_{1},\dots,x_{n}]. In particular, I∩JI\cap J is the first elimination ideal of tI+(1−t)JtI+(1-t)J with respect to the ordering t>x1>⋯>xnt>x_{1}>\dots>x_{n}.