sig
  module type Univariate =
    sig
      type t
      type dim = int
      type scalar
      val equal : t -> t -> bool
      val add : t -> t -> t
      val scalar_mul : scalar -> t -> t
      val negate : t -> t
      val sub : t -> t -> t
      val dot : t -> t -> scalar
      val zero : t
      val is_zero : t -> bool
      val add_term : scalar -> dim -> t -> t
      val of_term : scalar -> dim -> t
      val enum : t -> (scalar * dim) BatEnum.t
      val of_enum : (scalar * dim) BatEnum.t -> t
      val of_list : (scalar * dim) list -> t
      val coeff : dim -> t -> scalar
      val pivot : dim -> t -> scalar * t
      val order : t -> int
      val mul : t -> t -> t
      val one : t
      val scalar : scalar -> t
      val compose : t -> t -> t
      val identity : t
      val eval : t -> scalar -> scalar
      val exp : t -> int -> t
    end
  module Uvp :
    functor (R : Linear.Ring) ->
      sig
        type t
        type dim = int
        type scalar = R.t
        val equal : t -> t -> bool
        val add : t -> t -> t
        val scalar_mul : scalar -> t -> t
        val negate : t -> t
        val sub : t -> t -> t
        val dot : t -> t -> scalar
        val zero : t
        val is_zero : t -> bool
        val add_term : scalar -> dim -> t -> t
        val of_term : scalar -> dim -> t
        val enum : t -> (scalar * dim) BatEnum.t
        val of_enum : (scalar * dim) BatEnum.t -> t
        val of_list : (scalar * dim) list -> t
        val coeff : dim -> t -> scalar
        val pivot : dim -> t -> scalar * t
        val order : t -> int
        val mul : t -> t -> t
        val one : t
        val scalar : scalar -> t
        val compose : t -> t -> t
        val identity : t
        val eval : t -> scalar -> scalar
        val exp : t -> int -> t
      end
  module QQX :
    sig
      type t
      type dim = int
      type scalar = QQ.t
      val equal : t -> t -> bool
      val add : t -> t -> t
      val scalar_mul : scalar -> t -> t
      val negate : t -> t
      val sub : t -> t -> t
      val dot : t -> t -> scalar
      val zero : t
      val is_zero : t -> bool
      val add_term : scalar -> dim -> t -> t
      val of_term : scalar -> dim -> t
      val enum : t -> (scalar * dim) BatEnum.t
      val of_enum : (scalar * dim) BatEnum.t -> t
      val of_list : (scalar * dim) list -> t
      val coeff : dim -> t -> scalar
      val pivot : dim -> t -> scalar * t
      val order : t -> int
      val mul : t -> t -> t
      val one : t
      val scalar : scalar -> t
      val compose : t -> t -> t
      val identity : t
      val eval : t -> scalar -> scalar
      val exp : t -> int -> t
      val pp : Format.formatter -> t -> unit
      val show : t -> string
      val summation : t -> t
      val factor : t -> QQ.t * (t * int) list
    end
  module Monomial :
    sig
      type t
      type dim = int
      val pp :
        (Format.formatter -> int -> unit) ->
        Format.formatter -> Polynomial.Monomial.t -> unit
      val mul :
        Polynomial.Monomial.t ->
        Polynomial.Monomial.t -> Polynomial.Monomial.t
      val one : Polynomial.Monomial.t
      val mul_term :
        Polynomial.Monomial.dim ->
        int -> Polynomial.Monomial.t -> Polynomial.Monomial.t
      val singleton : Polynomial.Monomial.dim -> int -> Polynomial.Monomial.t
      val power : Polynomial.Monomial.dim -> Polynomial.Monomial.t -> int
      val enum :
        Polynomial.Monomial.t -> (Polynomial.Monomial.dim * int) BatEnum.t
      val of_enum :
        (Polynomial.Monomial.dim * int) BatEnum.t -> Polynomial.Monomial.t
      val equal : Polynomial.Monomial.t -> Polynomial.Monomial.t -> bool
      val compare : Polynomial.Monomial.t -> Polynomial.Monomial.t -> int
      val pivot :
        Polynomial.Monomial.dim ->
        Polynomial.Monomial.t -> int * Polynomial.Monomial.t
      val div :
        Polynomial.Monomial.t ->
        Polynomial.Monomial.t -> Polynomial.Monomial.t option
      val lcm :
        Polynomial.Monomial.t ->
        Polynomial.Monomial.t -> Polynomial.Monomial.t
      val lex :
        Polynomial.Monomial.t -> Polynomial.Monomial.t -> [ `Eq | `Gt | `Lt ]
      val deglex :
        Polynomial.Monomial.t -> Polynomial.Monomial.t -> [ `Eq | `Gt | `Lt ]
      val degrevlex :
        Polynomial.Monomial.t -> Polynomial.Monomial.t -> [ `Eq | `Gt | `Lt ]
      val block :
        (Polynomial.Monomial.dim -> bool) list ->
        (Polynomial.Monomial.t ->
         Polynomial.Monomial.t -> [ `Eq | `Gt | `Lt ]) ->
        Polynomial.Monomial.t -> Polynomial.Monomial.t -> [ `Eq | `Gt | `Lt ]
      val term_of :
        'a Syntax.context ->
        (Polynomial.Monomial.dim -> 'a Syntax.term) ->
        Polynomial.Monomial.t -> 'a Syntax.term
    end
  module Mvp :
    sig
      type t
      type dim = Monomial.t
      type scalar = QQ.t
      val equal : t -> t -> bool
      val add : t -> t -> t
      val scalar_mul : scalar -> t -> t
      val negate : t -> t
      val dot : t -> t -> scalar
      val zero : t
      val is_zero : t -> bool
      val add_term : scalar -> dim -> t -> t
      val of_term : scalar -> dim -> t
      val enum : t -> (scalar * dim) BatEnum.t
      val of_enum : (scalar * dim) BatEnum.t -> t
      val of_list : (scalar * dim) list -> t
      val coeff : dim -> t -> scalar
      val pivot : dim -> t -> scalar * t
      val pp :
        (Format.formatter -> int -> unit) -> Format.formatter -> t -> unit
      val compare : t -> t -> int
      val mul : t -> t -> t
      val sub : t -> t -> t
      val one : t
      val scalar : QQ.t -> t
      val of_dim : Polynomial.Monomial.dim -> t
      val of_vec : ?const:int -> Linear.QQVector.t -> t
      val split_linear : ?const:int -> t -> Linear.QQVector.t * t
      val vec_of : ?const:int -> t -> Linear.QQVector.t option
      val term_of :
        'a Syntax.context ->
        (Polynomial.Monomial.dim -> 'a Syntax.term) -> t -> 'a Syntax.term
      val exp : t -> int -> t
      val substitute : (Polynomial.Monomial.dim -> t) -> t -> t
      val div_monomial : t -> Polynomial.Monomial.t -> t option
      val dimensions : t -> int BatEnum.t
    end
  module Rewrite :
    sig
      type t
      val pp :
        (Format.formatter -> int -> unit) ->
        Format.formatter -> Polynomial.Rewrite.t -> unit
      val mk_rewrite :
        (Polynomial.Monomial.t ->
         Polynomial.Monomial.t -> [ `Eq | `Gt | `Lt ]) ->
        Polynomial.Mvp.t list -> Polynomial.Rewrite.t
      val reduce_rewrite : Polynomial.Rewrite.t -> Polynomial.Rewrite.t
      val grobner_basis : Polynomial.Rewrite.t -> Polynomial.Rewrite.t
      val reduce :
        Polynomial.Rewrite.t -> Polynomial.Mvp.t -> Polynomial.Mvp.t
      val preduce :
        Polynomial.Rewrite.t ->
        Polynomial.Mvp.t -> Polynomial.Mvp.t * Polynomial.Mvp.t list
      val add_saturate :
        Polynomial.Rewrite.t -> Polynomial.Mvp.t -> Polynomial.Rewrite.t
      val generators : Polynomial.Rewrite.t -> Polynomial.Mvp.t list
    end
end