An Introduction to Gröbner Bases for Algebras and Modules

James A. Shepherd

Summerschool on Conjectures in Homological Algebra for Finite Dimensional Algebras, Nordforjdeid, Norway. August 12th-19th 2001.

Introduction

We use Edward Green’s paper:

Multiplicative Bases, Gröbner Bases, and Right Gröbner Bases J. Symbolic Computation (2000)

For the Linear Gröbner basis stuff see a book such as Ideals, varieties and algorithms, Cox, Little, O’Shea, Springer-Verlag.

• Why? – Always useful to have a basis,

– Can do ’concrete’ calculations,

– Explicit construction of projective resolutions,

– Solving systems of equations over algebras,

– Elimination theory.

• How? – Constructive techniques,

– Can do using symbolic computation,

– Description of algebras with a Gröbner Basis theory.

Linear Gröbner Bases

k a field. V vector space over k with a well-ordered k-basis B = {b_{i}}_{i∈I}. Def n If v = ∑_{i} α_{i}b_{i} we say b_{i} occurs in v if α_{i} ≠ 0.

Def n

Tip (v) = b_{i} iff • b_{i} occurs in v, • b_{j} occurs in v implies b_{j} ≤ b_{i}.

Def n

CTip (v) is the coefficient of Tip (v) in v. Def n Let X ⊂ V.

Tip (X) = {b ∈ B : b = Tip (x) some x ∈ X},
NonTip (X) = B \ Tip (X).

Theorem 1 Let W be a subspace of V,

V = W ⊕ Span (NonTip (W)).

Proof

• W ∩ Span (NonTip (W)) = 0: Let x ∈ Span (NonTip (W)) \ {0}. If x ∈ W then Tip (x) ∈ Tip (W).#

• W + Span (NonTip (W)) = V: Let v ∈ V s.t. Tip (v) = b is minimal w.r.t. v ∉ W + Span (NonTip (W)). Let α = CTip (v).

– Assume b ∈ NonTip (W). Then, Tip (v − αb) < Tip (v), so v − αb = w + z ∈ W + Span (NonTip (W)). v = w + [z + αb] ∈ W + Span (NonTip (W)).# – Assume b ∈ Tip (W).

Let w ∈ W s.t. Tip (w) = b. Let β = CTip (w). Then, Tip (v − (α/β)w) < Tip (v), so v − (α/β)w = w′ + z ∈ W + Span (NonTip (W)). v = [w′ + (α/β)w] + z ∈ W + Span (NonTip (W)).#

If v ∈ V then there exists unique w_{v} ∈ W N(v) ∈ Span (NonTip (W)) s.t. v = w_{v} + N(v).

Def n We call N(v) the normal form of v.

Def n Let W be a subspace of V, G ⊂ W. Then G is a linear Gröbner Basis (L.G.b.) for W w.r.t. < if:

Span (Tip (G)) = Span (Tip (W)).

Lemma 2 If G is a L.G.b. of W then,

Span (G) = W.

Proof (⊂) G ⊂ W.

(⊃) Let w = w_{1} ∈ W, Tip (w_{1}) = ∑ α_{1i}Tip (g_{1i}) by def. of G. and β_{1} = CTip (w_{1}), γ_{1i} = CTip (g_{1i}). Let w_{2} = w_{1} − β_{1} ∑(α_{1i}/γ_{1i})g_{1i}, then if w_{2} ≠ 0: Tip (w_{2}) < Tip (w_{1}). Repeat to obtain 0 = w−β_{1} ∑(α_{1i}/γ_{1i})g_{1i} −⋯−β_{l} ∑(α_{li}/γ_{li})g_{li}.

Reduced Linear Gröbner Bases

Def n

G ⊂ W is a reduced L.G.b. for W w.r.t. < if:

1. G is a L.G.b. of W

2. g ∈ G ⇒ CTip (g) = 1

3. g ≠ g′ ∈ G ⇒ Tip (g) ≠ Tip (g′)

4. g ∈ G ⇒ g − Tip (g) ∈ Span (NonTip (W)).

Lemma 3 There is a unique r.L.G.b. Proof Let T = Tip (W) and let G = {t − N(t) : t ∈ T }. By Theorem (1) t − N(t) ∈ W. Also, Tip (t − N(t)) = t. Thus G is a L.G.b. of W. Rest of properties easy.

Example

Let k^{4} ⊃ W = Span (a, b, c).

Write as matrix:

( \begin{matrix}a_{1} & a_{2} & a_{3} & a_{4} \\ b_{1} & b_{2} & b_{3} & b_{4} \\ c_{1} & c_{2} & c_{3} & c_{4} \end{matrix} )

Row reduce:

( \begin{matrix}1 & ∗ & 0 & ∗ \\ 0 & 0 & 1 & ∗ \\ 0 & 0 & 0 & 0 \end{matrix} )

Rows are a reduced L.G.b.

Algebra Gröbner Bases

R a k-algebra. Def n B is a multiplicative basis for R if B is a k-basis and ∀b_{1}, b_{2} ∈ B, b_{1}b_{2} ∈ B ∪ {0}. Def n A well-order > is an admissable order on B if ∀b_{1}, b_{2}, c, d ∈ B: A1. b_{1} > b_{2} ⇒ b_{1}c > b_{2}c if b_{1}c ≠ 0 ≠ b_{2}c A2. b_{1} > b_{2} ⇒ cb_{1} > cb_{2} if cb_{1} ≠ 0 ≠ cb_{2} A3. c = b_{1}db_{2} ⇒ c ≥ d. Def n We call (B, >) an ordered multiplicative basis in case > is an admissable order.

Let I be an ideal in R. Def n A set G ⊂ I is a Gröbner basis w.r.t. > if:

⟨Tip (G)⟩ = ⟨Tip (I)⟩.

i.e. the same two-sided ideal is generated. Note: Theorem (1) still applies in vector space sense.

2-nomial Ideals

Def n An ideal I of R is a 2-nomial ideal if it can be generated by elements of the form b_{1} − b_{2} and b, where b_{1}, b_{2}, b ∈ B.

Proposition 4 There is a 1-1 correspondence between the set of equivalence relations on B ∪ {0} and 2-nomial ideals.

Notation: Greek letters in k, b_{i} ∈ B.

Lemma 5 Let I be a 2-nomial ideal with associated relation ∼_{I}. Then ∑_{i=1}^{r} α_{i}b_{i} ∈ I iff ∀[b] of ∼_{I}, ∑_{b_{i}∈[b]}α_{i}b_{i} ∈ I.

Theorem 6 Suppose S is a k-algebra with mult. basis C. Let I be an ideal in S, π: S ⟶ S/I, and B = π(C). Then,

B is a mult. basis for S/I iff I is a 2-nomial ideal.

Proof Linear independence: Suppose ∑_{i=1}^{n} α_{i}π(c_{i}) = 0, π(c_{i}) ≠ 0. Therefore, ∑_{i=1}^{n} α_{i}c_{i} ∈ I. So, ∀[c] ∑_{c_{i}∈[c]}α_{i}c_{i} ∈ I by Lemma (5). If c_{i} ∈ [c] then π(c_{i}) = π(c). Therefore, different c_{i}’s in different [c]’s as π(c_{i}) distinct. So, α_{i}c_{i} ∈ I. Since π(c_{i}) ≠ 0, α_{i} = 0.

Quivers

A quiver Γ(Γ_{0}, Γ_{1}) is  • a set Γ_{0} of vertices

• a set Γ_{1} of arrows

[figure: •; v_{1}; a_{1}; •; v_{2}; a_{2}; b_{1}; b_{2}; b_{3}; •; v_{3}; c; •; v_{4}; a_{3}; f_{1}; •; v_{5}; g_{1}; d; •; v_{6}; •; v_{7}; f_{2}; e; g_{2}; •; v_{8}]

Initial and terminal vertex of an arrow:

ia_{1} = v_{1}, ta_{1} = v_{2}

similarly for a vertex:

iv = v, tv = v.

Path Algebras

Let a, b ∈ Γ_{0} ∪ Γ_{1}:

ab = \{ \begin{matrix}0 & ta ≠ ib \\ a & b = ta \\ b & a = ia \\ ab & otherwise. \end{matrix}

Def n A path p in Γ is a product of arrows, or a single vertex. Note: We define ip, tp, and length of a path. Def n The path algebra kΓ of Γ has k-basis the paths and multiplication as above.

Theorem 7 Let R be a k-algebra with ordered multiplicative basis (B, >). Let Γ be the graph associated to B. Then there is a surjective k-algebra homomorphism ϕ: kΓ ⟶ R s.t.:

1. If p is a directed path in Γ then ϕ(p) ∈ B ∪ {0}

2. If b ∈ B then ∃p ∈ Γ s.t. ϕ(p) = b

3. ker ϕ is a 2-nomial ideal.

Proof Let 1 = ∑_{i=1}^{n} α_{i}v_{i} with α_{i} ∈ k^{∗}, distinct v_{i} ∈ B.

• v_{1}, …, v_{n} orthogonal idempotents, α_{i} = 1.

v_{i} = v_{i}.1 = n ; ∑ ; j=1 α_{j}v_{i}v_{j}

But v_{i}v_{j} = b ∈ B if non-zero. Assume b ≠ v_{i} then must be another v_{i}v_{l} = b to cancel. Now, v_{j} > v_{l} or v_{l} > v_{j} so v_{i}v_{l} ≠ v_{i}v_{j}.#

• Cancellation: b_{1} ≠ b_{2} ∈ B, b ∈ B:

b_{1}b = b_{2}b ⇒ b_{1}b = 0 = b_{2}b
bb_{1} = bb_{2} ⇒ bb_{1} = 0 = bb_{2}.

As b_{1} > b_{2} ⇒ b_{1}b > b_{2}b.

• b ∈ B. Unique i, j s.t. v_{i}b = b, bv_{j} = b and l ≠ i means v_{l}b = 0.

b = b.1 = n ; ∑ ; i=1 bv_{i}.

• v_{i}’s minimal w.r.t > as b = bv_{i}v_{i} and A3.

• b ∈ B \ {v_{1}, …, v_{n}} ⇒ b^{2} ≠ b.

b > v_{i}, bv_{i} = b ⇒ b^{2} > b by A2.

• Γ_{0} := {v_{1}, …, v_{n}} full set of primitive orthogonal idempotents.

– 1 = ∑_{i=1}^{n} v_{i} therefore full.

– Suppose v_{i} = x + y, x, y orth. idem. x = ∑_{i} α_{i}v_{i} + ∑_{l} β_{l}b_{l}. But v_{i} = v_{i}xv_{i} + v_{i}yv_{i}. So, v_{i}b_{l} = b_{l} and,

x = α_{i}v_{i}+_{l}^{∑} β_{l}b_{l}, y = (1−α_{i})v_{i}−_{l}^{∑} β_{l}b_{l}

– Now xy = 0, b_{l}b_{j} ≠ v_{i}, so α_{i}(1 − α_{i}) = 0. Say α_{i} = 1.

– Let b denote smallest b_{l}. Now, v_{i}b = b and b < b_{l}b_{j} where non-zero. So can’t cancel v_{i}b in xy = 0 and all β_{l} = 0.

Def n b ∈ B is product indecomposible if b ∉ Γ_{0} and b ≠ b_{1}b_{2} with b_{1}, b_{2} ∈ B \ Γ_{0}.

Def n Let Γ_{1} be the set of product indecomposibles.

• ∀b ∈ B \Γ_{0} ∃b_{1} … b_{r} ∈ Γ_{1} s.t. b = b_{1} ⋯ b_{r}. If b ∉ Γ_{0} ∪ Γ_{1}, b = b_{1}b_{2} for some b_{1}b_{2} ∈ B \ Γ_{0}. b = ib_{1}b_{1}b_{2} = b_{1}b_{2}tb_{2} ⇒ b ≥ b_{1}, b ≥ b_{2} by A3. b = b_{1} ⇒ b.tb = b_{1}b_{2} = bb_{2}. Cancelling, tb = b_{2}. So, b > b_{1}, b > b_{2}, done by induction.

Open Question 8 Given a quiver Γ, what are necessary and sufficient conditions on a 2-nomial ideal I s.t. kΓ/I has a Gröbner Basis theory in the sense that the image of the paths admits an admissible order?

Admissible orders

length-lexicographic order: Order vertices and arrows arbitrarily and set vertices smaller than arrows:

a_{1} > ⋯ > a_{m} > v_{1} > ⋯ > v_{n}.

If p, q are paths of length at least 1, p > q if ℓ(p) > ℓ(q), or if p = b_{1} ⋯ b_{m} and q = c_{1} ⋯ c_{m} then b_{i} > c_{i} where i is the smallest integer s.t. b_{j} ≠ c_{j}.

weight-lexicographic order: Let W : Γ_{1} ⟶ ℕ. Extend W additively to B, so W (a_{1} ⋯ a_{r}) = ∑_{i} W (a_{i}). Order the vertices and set them smaller than arrows. Order arrows s.t. W (a) < W (b) ⇒ a < b. Define p < q if W (p) < W (q). Or if W (p) = W (q) use lexicographic order.

Theory of Right Gröbner bases

Let R be a k-algebra with (B, >). Let M be a right (unital) R-module. Let M be a k-basis of M. Def n M is a coherent basis if:

∀m ∈ M ∀b ∈ B mb ∈ M ∪ {0}. Lemma 9 If M is coherent then ∀m ∈ M ∃v ∈ Γ_{0} s.t. mv = m. Proof m = m.1 = ∑_{v∈Γ_{0}} mv.

Def n A well-order ≻ on M is right admissible if ∀m, m_{1}, m_{2} ∈ M ∀b, b_{1}, b_{2} ∈ B:

M1. m_{1} ≻ m_{2} ⇒ m_{1}b ≻ m_{2}b if m_{1}b ≠ 0 ≠ m_{2}b

M2. b_{1} > b_{2} ⇒ mb_{1} ≻ mb_{2} if mb_{1} ≠ 0 ≠ mb_{2}.

Def n (M, ≻) is an ordered basis if M is coherent and ≻ is right admissible.

Note: If m ∈ M b ∈ B \ Γ_{0} then mb ≻ m if mb ≠ 0 ≠ m.

Def n Define Tip , CTip , NonTip , and N(m) as before.

Def n Let N be a right submodule of M. Then G ⊂ N is a Right Gröbner basis for N w.r.t. ≻ if:

⟨Tip (G)⟩ = ⟨Tip (N)⟩.

Proposition 10 N submodule of M. Then:

1. There is a Right G.b. for N w.r.t. ≻

2. If G is a R.G.b. for N then G generates N as a submodule

3. As vector spaces M = N ⊕ Span (NonTip (N)).

WARNING 11 Most modules DON’T have a right Gröbner basis theory.

Def n m, m′ ∈ M. m left divides m′ if:

∃b ∈ B s.t. m′ = mb.

Def n A R.G.b. G of N is reduced if for g = ∑_{i=1}^{r} α_{i}m_{i} ∈ G and g′ ∈ G \ {g}:

• Tip (g′) doesn’t left divide m_{i}

• CTip (g) = 1

Equivalently: If g ∈ G then g − Tip (g) ∈ Span (NonTip (N)).

Def n G is tip-reduced if g, g′ ∈ G and Tip (g) left divides Tip (g′) then g = g′.

Note: reduced ⇒ tip-reduced.

Def n x ∈ M is (left) uniform if ∃v ∈ Γ_{0} s.t. xv = x.

Proposition 12 Tip-reduced uniform right Gröbner bases exist.

Projective Modules

Let R be a k-algebra with (B, >).

_{v∈Γ_{0}}^{⨁} vR = R

So vR is a projective, which we denote by P_{v}.

If X is an index set and V : X ⟶ Γ_{0} then

P = _{i∈X}^{⨁} P_{V (i)}

is a projective module.

Gröbner Bases for Projectives

Let P_{v} = {x ∈ P_{v} : x = vx, x ∈ B}. Let (P_{v}, ≻) be the restriction of (B, >). If P = ⨁_{i∈X} P_{V (i)} let:

P_{i} = {x ∈ P : x_{i} ∈ P_{V (i)}, x_{j} = 0 if j ≠ i}.

Let P = ⋃_{i∈X} P_{i}. If we have an ordering on X and then we can extend to an ordering (P, ≻).

Construction of Uniform Tip-reduced Right Gröbner

Bases

Let P = ⨁_{i∈X} P_{V (i)} as above, with (P, ≻).

If Q is a submodule of P with generating set F′, let,

F = {fv : f ∈ F′, v ∈ Γ_{0}}.

Thus, F is a set of uniform elements that generates Q.

Theorem 13 Every uniform tip-reduced generating set of Q is a R.G.b.

Algorithm 14

1. H finite uniform generating set for Q without 0.

2. T = {Tip (h) : Tip (h′) doesn’t left divide Tip (h), h′ ∈ H \ {h} }.

3. For each t ∈ T choose some h ∈ H s.t. Tip (h) = t, and renumber so these are h_{1}, …, h_{s}.

4. If s = r STOP.

5. Let Q^{∗} = ⟨h_{1}, …, h_{s}⟩.

6. For i = s + 1, …, r write h_{i} = h_{i}^{∗} + N(h_{i}) using P = Q^{∗} ⊕ Span (NonTip (Q^{∗})).

7. H = {h_{1}, …, h_{s}, N(h_{s+1} ), …, N(h_{r})}. Repeat.

Example

[figure: •; v_{0}; a; b; •; v_{2}; d; •; v_{1}; c; e; •; v_{3}]

B = \begin{aligned}\{ & v_{0} < v_{1} < v_{2} < v_{3}, \\ & < a < b < c < d < e, \\ & < ac < ae < bc < be < cd < da < db, \\ & < acd < bcd < cda < cdb < dac < dbc, \\ & < acda < acdb < acde < bcda < bcdb, \\ & < bcde < cdac < cdbc < cdbe < dacd, \\ & < dbcd < ⋯ \} \end{aligned}

P = P_{0} ⊕ P_{1} ⊕ P_{1}

P_{0} = \begin{aligned}\{ & v_{0}, \\ & < a < b, \\ & < ac < ae < bc < be, \\ & < acd < bcd, \\ & < acda < acdb < bcda < bcdb < ⋯ \} \end{aligned}

P_{1} = {v_{1} < e}

Q = ⟨F′⟩ = ⟨abc + ac + cd − acd, e_{1} − a, a − b⟩

F = {fv : f ∈ F′, v ∈ Γ_{0}}
= {0, cd − acd, −a, a, −b, abc + ac, e_{1}}

1. H = {cd − acd, −a, a, −b, abc + ac, e_{1}} 2. Tip (H) = {cd, a, b, ac, e_{1}}

T = {cd, a, b, e_{1}}

3. H = {cd − acd, a, −b, e_{1}, abc + ac, −a} 4. 4 = s ≠ r = 6

5. Q^{∗} = ⟨cd − acd, a, −b, e_{1}⟩

6. N(abc + ac) = 0 N(−a) = 0

7. H = {cd − acd, a, −b, e_{1}, 0} So, required Gröbner Basis is:

Q = {cd − acd, a, −b, e_{1}}