Skip to content

08 — Gröbner: general relations, completed and certified

The mathematics

A monomial ideal (Chapter 02) is easy because a basis of kQ/I is just the paths avoiding the forbidden ones. A general admissible ideal I ⊆ kQ is generated by relations that are linear combinations of parallel paths — a*b - c*d, not a single word — and now "avoid the relations" is no longer a well-defined subword test. The classical fix is a noncommutative Gröbner basis: fix an admissible order on paths, orient each relation into a rewrite rule (leading word) → (smaller tail), and complete the rules (Buchberger–Mora, the path-algebra form of Buchberger's algorithm) until the rewriting is confluent — every element reduces to a unique normal form regardless of the order of rewrites. Bergman's Diamond Lemma then says the words that no rule can touch (the irreducible words) are an exact k-basis of kQ/I, and any product is computed by concatenating and rewriting to normal form. Everything here is exact and characteristic-independent; the only inputs from the field are its arithmetic operations.

How it is represented

Every object lives in quiverlab/groebner/. Paths compose left to right throughout (Chapter 02): the word ("c", "d") is "first c, then d".

  • An element of kQ is a dict (lookup table) word -> coefficient, e.g. {("c", "d"): 1, ("a", "b"): -1}, carrying no zero coefficients; the zero element is the empty dict {}. The coefficient is an element of the exact Domain (Chapter 01), so the same code runs over QQ, CC, or GF(p). lc_add, lc_sub (reduction.py) do the arithmetic and drop any coefficient that cancels to zero.
  • The order is a PathOrder (order.py): a length-then-lexicographic well-order whose arrow ranks are the insertion order of quiver.arrows (the first arrow is smallest). Its key(word) returns the sort key (length, ranks), and leading(comb) returns the largest word in an element — the one a rule will target. path_order(quiver) builds it.
  • A rule is a frozen (immutable) ReductionRule (reduction.py) with four fields: lead (the leading word, a path tuple), tail (a tuple of (coeff, word) pairs, every word strictly smaller than lead), and source/target (the shared endpoints, so the rule is parallel). It means "rewrite any occurrence of lead into tail". rule_from_comb turns an element into a rule by dividing through by its leading coefficient.
  • An ambiguity is a frozen Ambiguity (overlap.py): two leads that clash inside one word. kind is "overlap" (a nonempty b that is a proper suffix of one lead and a proper prefix of the other — left-to-right, so suffix meets prefix) or "inclusion" (one lead a proper factor of the other); word is the clashing word and a/c its prefix/suffix context.
  • The whole thing is a frozen ReductionSystem (system.py): quiver, domain, order, rules (a confluent tuple), irreducibles (the certified basis words), degree_bound, and is_confluent. Its methods reduce, normal_form, leading_words, and ambiguities are the surface the structure-constant lowering (below) and Plan 04 (Chouhy–Solotar) consume.

How the computation runs

build_reduction_system(quiver, relations, field) (system.py) is the pipeline:

  1. Parse and orient. Relation strings are parsed (Chapter 02); any relation with a path of length < 2 is refused loudly (AdmissibilityError — an admissible ideal lives inside the square of the arrow ideal). The coefficients seen are collected into an exact Domain, and each relation becomes an initial rule via rule_from_comb: its leading word under the order becomes lead, everything else is moved to the other side as tail. A relation whose coefficients all vanish in the chosen field raises RelationError.

  2. Complete (complete.py, complete). Repeatedly: form every Ambiguity of the current rules with all_ambiguities; for each, build its S-polynomial — reduce the ambiguity word two ways (apply one rule at the front, the other in place) and subtract, so the leads cancel and only smaller words survive (s_polynomial); reduce that remainder to normal form with the current rules (reduce_comb). If it is nonzero, it is a genuinely new relation the rules could not see, so orient it into a rule and restart. When a full pass adds nothing, the system is confluent. reduce_comb always rewrites the largest reducible word first, using the leftmost matching lead (first_factor); because every rewrite replaces a word by strictly smaller ones in a well-order, reduction terminates. Only ambiguity words up to degree_bound are formed, so completion always halts; a runaway system (more than max_rules) stops with an AdmissibilityError rather than hanging. Finally _minimize_leads drops any rule whose lead contains another's as a factor, leaving the leads an antichain (this is why a completed system has only overlap ambiguities left, never inclusions).

  3. Certify (certificate.py). Let L be the longest leading word. Every overlap ambiguity word has length ≤ 2L−1, so if 2L-1 <= degree_bound then every ambiguity was actually formed and reduced to zero — confluence is proved, not assumed. If 2L-1 exceeds the bound, check_degree_bound refuses with an AdmissibilityError telling you the exact bound to raise to; it never certifies an unchecked system. Given confluence, the irreducible words are enumerated by the very same Plan-01 forbidden-word automaton as the monomial case (core.monomial.irreducible_paths, Chapter 02) with the leads as the forbidden words: finitely many ⇒ certified finite-dimensional; a cycle ⇒ NotFiniteDimensionalError naming the offending arrow cycle.

  4. Lower to structure constants (lower.py, groebner_algebra). The algebra basis is the vertex idempotents (in quiver.vertices order) followed by the certified irreducible words sorted (length, word) — exactly the ordering build_monomial_algebra uses, so on a monomial input the Gröbner route reproduces the Plan-01 Algebra elementwise. Each structure constant b_i · b_j is computed by concatenating the two words and reducing to normal form (rs.reduce); the resulting coefficient vector is one column of the multiplication table T. The output is an ordinary Algebra (Chapter 03), so Hochschild cohomology flows through the existing bar path unchanged.

A worked micro-example — completing Fixture 3

Take the two-loop quiver Q with one vertex and loops x, y (so x has rank 0, y rank 1), and the ideal generated by {y*y, x*y, y*x - x*x}. Oriented under length-lex, the three initial rules are yy → 0, xy → 0, and yx → xx (the tail xx is smaller than the lead yx because x < y at the first letter). These rules are not yet confluent:

  • The leads yy and yx overlap on the shared middle letter y: yy = (y)·(y) and yx = (y)·(x), so the ambiguity word is y·y·x = ("y","y","x") with prefix context a = ("y",) and suffix context c = ("x",).
  • Its S-polynomial reduces yyx two ways: applying yy → 0 at the front gives 0·x = 0; applying yx → xx at the back gives y·xx = ("y","x","x"). The difference is 0 - yxx = {("y","x","x"): -1} (verified by running s_polynomial).
  • Reducing yxx with the current rules fires yx → xx at position 0, giving xx·x = xxx, which no rule touches. So the normal form is -xxx ≠ 0: a new relation. Oriented, it is the monomial rule xxx → 0 (empty tail).

Completion adds exactly this rule; a second pass finds every remaining ambiguity now reduces to zero. The completed leads are {xxx, xy, yx, yy} — the same result the completion test asserts. The moral in one line: xxx was hidden in the ideal — the free-algebra identity y·(yx−xx) − (yy)·x = −yxx puts an element of I in front of us, and rewriting yx → xx turns it into −xxx, so xxx ∈ I — and completion is what makes this visible to the rewriting system.

For the structure-constant payoff, take the commutative square Q with arrows a:1→2, b:2→4, c:1→3, d:3→4 and the single non-monomial relation a*b - c*d. Here the one rule is cd → ab (ab < cd because a < c), with source 1, target 4; the longest lead has length L = 2, so 2L−1 = 3 ≤ the default bound 8 and there are no ambiguities at all. The certified irreducibles are a, b, c, d, ab, giving the basis [e_1, e_2, e_3, e_4, a, b, c, d, a*b] — dimension 9. When the table is built, the product c·d concatenates to ("c","d") and reduces to {("a","b"): 1}, so in the algebra c*d = a*b: the commutativity of the square is now a literal structure constant. (Every dim, lead, tail, and normal form in this section was produced by running the code.)

Where to look in the code

concept file function / class
element arithmetic, rules, normal form groebner/reduction.py lc_add, lc_sub, ReductionRule, rule_from_comb, first_factor, reduce_comb
admissible length-lex order groebner/order.py PathOrder, path_order
overlap / inclusion ambiguities groebner/overlap.py Ambiguity, overlaps, inclusions, all_ambiguities
S-polynomials, Buchberger–Mora completion groebner/complete.py s_polynomial, complete, _minimize_leads
finiteness certificate (2L−1 ≤ D, automaton) groebner/certificate.py default_degree_bound, check_degree_bound, certified_irreducibles
the frozen reduction system (Plan 04 surface) groebner/system.py ReductionSystem, build_reduction_system
general kQ/I → structure-constant Algebra groebner/lower.py groebner_algebra
monomial-vs-Gröbner dispatch combinat/quiver.py Quiver.algebra
loud refusals errors.py AdmissibilityError, NotFiniteDimensionalError, RelationError