Gröbner Bases

• Introduction
• Representation and Monomial Orders
  • Lexicographical: lex
  • Graded Lexicographical: glex
  • Graded Reverse Lexicographical: grevlex
  • Graded Reverse Lexicographical (Weighted): grevlexw
  • Elimination (k): elim
  • Elimination List: elim
  • Inverse Block: invblock
  • Univariate: univ
  • Weight: weight
• Polynomial Rings and Ideals
  • Creation of Polynomial Rings and Accessing their Monomial Orders
    • PolynomialRing(R, n): Rng, RngIntElt → RngMPol
    • PolynomialAlgebra(R, n): Rng, RngIntElt → RngMPol
    • PolynomialRing(R, n, order): Rng, RngIntElt, MonStgElt, ... → RngMPol
    • PolynomialAlgebra(R, n, order): Rng, RngIntElt, MonStgElt, ... → RngMPol
    • PolynomialRing(R, n, T): Rng, RngIntElt, Tup → RngMPol
    • PolynomialAlgebra(R, n, T): Rng, RngIntElt, Tup → RngMPol
    • MonomialOrder(P): RngMPol → Tup
    • MonomialOrderWeightVectors(P): RngMPol → [ [ FldRatElt ] ]
    • SetSparseMonomialMinRank(R): RngIntElt
    • GetSparseMonomialMinRank() → RngIntElt
    • Example: Polynomial Rings with Different Orders
  • Creation of Graded Polynomial Rings
    • PolynomialRing(R, Q): Rng, [ RngIntElt ] → RngMPol
    • PolynomialAlgebra(R, Q): Rng, [ RngIntElt ] → RngMPol
    • Grading(P): RngMPol → [ RngIntElt ]
    • VariableWeights(P): RngMPol → [ RngIntElt ]
    • HomogeneousWeightsSearch(S): [ RngMPol ] → BoolElt, [ RngIntElt ]
  • Element Operations Using the Grading
    • Degree(f): RngMPolElt → RngIntElt
    • WeightedDegree(f): RngMPolElt → RngIntElt
    • LeadingWeightedDegree(f): RngMPolElt → RngIntElt
    • IsHomogeneous(f): RngMPolElt → BoolElt
    • HomogeneousComponent(f, d): RngMPolElt, RngIntElt → RngMPolElt
    • HomogeneousComponents(f): RngMPolElt → [ RngMPolElt ]
    • MonomialsOfDegree(P, d): RngMPolElt, RngIntElt → {@ RngMPolElt @}
    • MonomialsOfWeightedDegree(P, d): RngMPolElt, RngIntElt → {@ RngMPolElt @}
    • Example: Operations in a Graded Polynomial Ring
  • Creation of Ideals and Accessing their Bases
    • ideal<P | L>: RngMPol, List → RngMPol
    • Ideal(B): [ RngMPolElt ] → RngMPol
    • Ideal(B): { RngMPolElt } → RngMPol
    • Ideal(f): RngMPolElt → RngMPol
    • IdealWithFixedBasis(B): [ RngMPolElt ] → RngMPol
    • Basis(I): RngMPol → [ RngMPolElt ]
    • BasisElement(I, i): RngMPol, RngIntElt → RngMPolElt
• Gröbner Bases
  • Gröbner Bases over Fields
  • Gröbner Bases over Euclidean Rings
  • Construction of Gröbner Bases
    • Groebner(I: parameters): RngMPol
    • GroebnerBasis(I: parameters): RngMPol → [ RngMPolElt ], [ RngIntElt ]
    • GroebnerBasis(S: parameters): [ RngMPolElt ] → [ RngMPolElt ], [ RngIntElt ], []
    • GroebnerBasis(S: parameters): { RngMPolElt } → [ RngMPolElt ]
    • GroebnerBasisUnreduced(S: parameters): [ RngMPolElt ] → [ RngMPolElt ]
    • GroebnerBasisUnreduced(S: parameters): { RngMPolElt } → [ RngMPolElt ]
    • GroebnerBasis(S, d: parameters): [ RngMPol ], RngInt → RngMPolElt
    • SetGBGlobalModular(f): BoolElt
    • SetFaugereModular(f): BoolElt
  • The Dense Variant of the \(F_4\) algorithm
  • Related Functions
    • HasGroebnerBasis(I): RngMPol → BoolElt
    • EasyIdeal(I): RngMPol → RngMPol, [ RngIntElt ]
    • EasyBasis(I): RngMPol → [ RngMPolElt ]
    • SmallBasis(I): RngMPol → [ RngMPolElt ]
    • MarkGroebner(I): RngMPol
    • IsGroebner(S): { RngMPolElt } → BoolElt
    • IsGroebner(S): [ RngMPolElt ] → BoolElt
    • Coordinates(I, f): RngMPol, RngMPolElt → [ RngMPolElt ]
    • CoordinateMatrix(I): RngMPol → Matrix
    • NormalForm(f, I): RngMPolElt, RngMPol → RngMPolElt
    • NormalForm(f, S): RngMPolElt, [ RngMPolElt ] → RngMPolElt, [ RngMPolElt ]
    • SPolynomial(f, g): RngMPolElt, RngMPolElt → RngMPolElt
    • Reduce(S): [ RngMPolElt ] → [ RngMPolElt ]
    • Reduce(S): { RngMPolElt } → [ RngMPolElt ]
    • ReduceGroebnerBasis(S): [ RngMPolElt ] → [ RngMPolElt ]
    • ReduceGroebnerBasis(S): { RngMPolElt } → [ RngMPolElt ]
  • Gröbner Bases of Boolean Polynomial Rings
    • BooleanPolynomialRing(n): RngIntElt → RngMPolBool
    • BooleanPolynomialRing(n, order): RngIntElt, MonStgElt → RngMPolBool
    • BooleanPolynomialRing(B, Q): RngMPolBool, [RngIntElt] → RngMPolBoolElt
  • Construction of Input Systems
    • MinRankSystem(K, n, k, r): FldFin, RngIntElt, RngIntElt, RngIntElt → [ RngMPolBool ]
  • Verbosity
    • SetVerbose("Groebner", v): MonStgElt, RngIntElt
    • SetVerbose("Buchberger", v): MonStgElt, RngIntElt
    • SetVerbose("Faugere", v): MonStgElt, RngIntElt
    • SetVerbose("FGLM", v): MonStgElt, RngIntElt
    • SetVerbose("GroebnerWalk", v): MonStgElt, RngIntElt
    • Example: Groebner Basis of the Cyclic-6 Ideal
    • Example: Runge-Kutta 2 System
    • Example: Solving a Boolean Polynomial System
    • Example: Groebner Bases over the Integers
    • Example: Finding Primes via Groebner Bases
    • Example: Groebner Bases over a Quadratic Order
    • Example: Coordinates with Respect to an Ideal Basis
    • Example: Groebner Bases over a Valuation Ring
  • Degree-\(d\) Gröbner Bases
    • GroebnerBasis(S, d : parameters): [ RngMPolElt ], RngInt → RngMPolElt
    • Example: Degree-d Groebner Bases
• Changing Coefficient Ring
  • ChangeRing(I, S): RngMPol, Rng → RngMPol
  • Example: Groebner Basis over a Smaller Field
• Changing Monomial Order
  • ChangeOrder(I, Q): RngMPol, RngMPol → RngMPol, Map
  • ChangeOrder(I, order): RngMPol, ... → RngMPol, Map
  • ChangeOrder(I, T): RngMPol, Tup → RngMPol
  • Example: Univariate Generators by Change of Order
• Hilbert-driven Gröbner Basis Construction
  • HilbertGroebnerBasis(S, H): [ RngMPolElt ], FldFunRatUElt → BoolElt, [ RngMPolElt ]
  • HilbertGroebnerBasis(S, N): [ RngMPolElt ], RngUPolElt → BoolElt, [ RngMPolElt ]
  • SetVerbose("HilbertGroebner", v): MonStgElt, RngIntElt
  • Example: Hilbert-Driven Groebner Basis for Invariants
• SAT solver
  • SAT(B): [ RngMPolBoolElt ] → BoolElt, [ FldFinElt ]
  • SAT(B): [ RngMPolElt ] → BoolElt, [ FldFinElt ]
  • Example: Solving a Boolean System with SAT
• Bibliography