\documentclass{article}
\usepackage{axiom}
\begin{document}
\title{\$SPAD/src/algebra polycat.spad}
\author{Manuel Bronstein}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{category AMR AbelianMonoidRing}
<<category AMR AbelianMonoidRing>>=
)abbrev category AMR AbelianMonoidRing
++ Author:
++ Date Created:
++ Date Last Updated:
++ Basic Functions:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ Abelian monoid ring elements (not necessarily of finite support)
++ of this ring are of the form formal SUM (r_i * e_i)
++ where the r_i are coefficents and the e_i, elements of the
++ ordered abelian monoid, are thought of as exponents or monomials.
++ The monomials commute with each other, and with
++ the coefficients (which themselves may or may not be commutative).
++ See \spadtype{FiniteAbelianMonoidRing} for the case of finite support
++ a useful common model for polynomials and power series.
++ Conceptually at least, only the non-zero terms are ever operated on.

AbelianMonoidRing(R:Ring, E:OrderedAbelianMonoid): Category ==
        Join(Ring,BiModule(R,R)) with
    leadingCoefficient: % -> R
      ++ leadingCoefficient(p) returns the coefficient highest degree term of p.
    leadingMonomial: % -> %
      ++ leadingMonomial(p) returns the monomial of p with the highest degree.
    degree: % -> E
      ++ degree(p) returns the maximum of the exponents of the terms of p.
    map: (R -> R, %) -> %
      ++ map(fn,u) maps function fn onto the coefficients
      ++ of the non-zero monomials of u.
    monomial?: % -> Boolean
      ++ monomial?(p) tests if p is a single monomial.
    monomial: (R,E) -> %
      ++ monomial(r,e) makes a term from a coefficient r and an exponent e.
    reductum: % -> %
         ++ reductum(u) returns u minus its leading monomial
         ++ returns zero if handed the zero element.
    coefficient: (%,E) -> R
         ++ coefficient(p,e) extracts the coefficient of the monomial with
         ++ exponent e from polynomial p, or returns zero if exponent is not present.
    if R has Field then "/": (%,R) -> %
         ++ p/c divides p by the coefficient c.
    if R has CommutativeRing then
       CommutativeRing
       Algebra R
    if R has CharacteristicZero then CharacteristicZero
    if R has CharacteristicNonZero then CharacteristicNonZero
    if R has IntegralDomain then IntegralDomain
    if R has Algebra Fraction Integer then Algebra Fraction Integer
  add
    monomial? x == zero? reductum x

    map(fn:R -> R, x: %) ==
          -- this default definition assumes that reductum is cheap
       zero? x => 0
       r:=fn leadingCoefficient x
       zero? r => map(fn,reductum x)
       monomial(r, degree x) + map(fn,reductum x)

    if R has Algebra Fraction Integer then
      q:Fraction(Integer) * p:% == map(q * #1, p)

@
\section{category FAMR FiniteAbelianMonoidRing}
<<category FAMR FiniteAbelianMonoidRing>>=
)abbrev category FAMR FiniteAbelianMonoidRing
++ Author:
++ Date Created:
++ Date Last Updated: 14.08.2000 Exported pomopo! and binomThmExpt [MMM]
++ Basic Functions:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description: This category is
++ similar to AbelianMonoidRing, except that the sum is assumed to be finite.
++ It is a useful model for polynomials,
++ but is somewhat more general.

FiniteAbelianMonoidRing(R:Ring, E:OrderedAbelianMonoid): Category ==
   Join(AbelianMonoidRing(R,E),FullyRetractableTo R) with
    ground?: % -> Boolean
      ++ ground?(p) tests if polynomial p is a member of the coefficient ring.
                    -- can't be defined earlier, since a power series
                    -- might not know if there were other terms or not
    ground: % -> R
      ++ ground(p) retracts polynomial p to the coefficient ring.
    coefficients: % -> List R
      ++ coefficients(p) gives the list of non-zero coefficients of polynomial p.
    numberOfMonomials: % -> NonNegativeInteger
      ++ numberOfMonomials(p) gives the number of non-zero monomials in polynomial p.
    minimumDegree: % -> E
      ++ minimumDegree(p) gives the least exponent of a non-zero term of polynomial p.
      ++ Error: if applied to 0.
    mapExponents: (E -> E, %) -> %
      ++ mapExponents(fn,u) maps function fn onto the exponents
      ++ of the non-zero monomials of polynomial u.
    pomopo!: (%,R,E,%) -> %
         ++ \spad{pomopo!(p1,r,e,p2)} returns \spad{p1 + monomial(e,r) * p2}
         ++ and may use \spad{p1} as workspace. The constaant \spad{r} is
         ++ assumed to be nonzero.
    if R has CommutativeRing then
       binomThmExpt: (%,%,NonNegativeInteger) -> %
         ++ \spad{binomThmExpt(p,q,n)} returns \spad{(x+y)^n}
         ++ by means of the binomial theorem trick.
    if R has IntegralDomain then
       "exquo": (%,R) -> Union(%,"failed")
       ++ exquo(p,r) returns the exact quotient of polynomial p by r, or "failed"
       ++ if none exists.
    if R has GcdDomain then
       content: % -> R
         ++ content(p) gives the gcd of the coefficients of polynomial p.
       primitivePart: % -> %
         ++ primitivePart(p) returns the unit normalized form of polynomial p
         ++ divided by the content of p.
  add
    pomopo!(p1,r,e,p2) == p1 + r * mapExponents(#1+e,p2)

    if R has CommutativeRing then 
       binomThmExpt(x,y,nn) ==
               nn = 0 => 1$%
               ans,xn,yn: %
               bincoef: Integer
               powl: List(%):= [x]
               for i in 2..nn repeat powl:=[x * powl.first, :powl]
               yn:=y; ans:=powl.first; i:=1; bincoef:=nn
               for xn in powl.rest repeat
                  ans:= bincoef * xn * yn + ans
                  bincoef:= (nn-i) * bincoef quo (i+1);  i:= i+1
                  -- last I and BINCOEF unused
                  yn:= y * yn
               ans + yn
    ground? x ==
      retractIfCan(x)@Union(R,"failed") case "failed" => false
      true
    ground x == retract(x)@R
    mapExponents (fn:E -> E, x: %) ==
         -- this default definition assumes that reductum is cheap
       zero? x => 0
       monomial(leadingCoefficient x,fn degree x)+mapExponents(fn,reductum x)
    coefficients x ==
      zero? x => empty()
      concat(leadingCoefficient x, coefficients reductum x)

    if R has Field then
       x/r == map(#1/r,x)
    if R has IntegralDomain then
       x exquo r ==
          -- probably not a very good definition in most special cases
          zero? x => 0
          ans:% :=0
          t:=leadingCoefficient x exquo r
          while not (t case "failed") and not zero? x repeat
            ans:=ans+monomial(t::R,degree x)
            x:=reductum x
            if not zero? x then t:=leadingCoefficient x exquo r
          t case "failed" => "failed"
          ans
    if R has GcdDomain then
       content x ==       -- this assumes  reductum is cheap
          zero? x => 0
          r:=leadingCoefficient x
          x:=reductum x
--          while not zero? x and not one? r repeat
          while not zero? x and not (r = 1) repeat
            r:=gcd(r,leadingCoefficient x)
            x:=reductum x
          r
       primitivePart x ==
          zero? x => x
          c := content x
          unitCanonical((x exquo c)::%)

@
\section{category POLYCAT PolynomialCategory}
<<category POLYCAT PolynomialCategory>>=
)abbrev category POLYCAT PolynomialCategory
++ Author:
++ Date Created:
++ Date Last Updated:
++ Basic Functions: Ring, monomial, coefficient, differentiate, eval
++ Related Constructors: Polynomial, DistributedMultivariatePolynomial
++ Also See: UnivariatePolynomialCategory
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ The category for general multi-variate polynomials over a ring
++ R, in variables from VarSet, with exponents from the
++ \spadtype{OrderedAbelianMonoidSup}.

PolynomialCategory(R:Ring, E:OrderedAbelianMonoidSup, VarSet:OrderedSet):
        Category ==
  Join(PartialDifferentialRing VarSet, FiniteAbelianMonoidRing(R, E),
       Evalable %, InnerEvalable(VarSet, R),
       InnerEvalable(VarSet, %), RetractableTo VarSet,
       FullyLinearlyExplicitRingOver R) with
    -- operations
    degree : (%,VarSet) -> NonNegativeInteger
      ++ degree(p,v) gives the degree of polynomial p with respect to the variable v.
    degree : (%,List(VarSet)) -> List(NonNegativeInteger)
      ++ degree(p,lv) gives the list of degrees of polynomial p
      ++ with respect to each of the variables in the list lv.
    coefficient: (%,VarSet,NonNegativeInteger) -> %
      ++ coefficient(p,v,n) views the polynomial p as a univariate
      ++ polynomial in v and returns the coefficient of the \spad{v**n} term.
    coefficient: (%,List VarSet,List NonNegativeInteger) -> %
      ++ coefficient(p, lv, ln) views the polynomial p as a polynomial
      ++ in the variables of lv and returns the coefficient of the term
      ++ \spad{lv**ln}, i.e. \spad{prod(lv_i ** ln_i)}.
    monomials: % -> List %
      ++ monomials(p) returns the list of non-zero monomials of polynomial p, i.e.
      ++ \spad{monomials(sum(a_(i) X^(i))) = [a_(1) X^(1),...,a_(n) X^(n)]}.
    univariate   : (%,VarSet) -> SparseUnivariatePolynomial(%)
      ++ univariate(p,v) converts the multivariate polynomial p
      ++ into a univariate polynomial in v, whose coefficients are still
      ++ multivariate polynomials (in all the other variables).
    univariate   : % -> SparseUnivariatePolynomial(R)
        ++ univariate(p) converts the multivariate polynomial p,
        ++ which should actually involve only one variable,
        ++ into a univariate polynomial
        ++ in that variable, whose coefficients are in the ground ring.
        ++ Error: if polynomial is genuinely multivariate
    mainVariable  : % -> Union(VarSet,"failed")
           ++ mainVariable(p) returns the biggest variable which actually
           ++ occurs in the polynomial p, or "failed" if no variables are
           ++ present.
           ++ fails precisely if polynomial satisfies ground?
    minimumDegree : (%,VarSet) -> NonNegativeInteger
      ++ minimumDegree(p,v) gives the minimum degree of polynomial p
      ++ with respect to v, i.e. viewed a univariate polynomial in v
    minimumDegree : (%,List(VarSet)) -> List(NonNegativeInteger)
      ++ minimumDegree(p, lv) gives the list of minimum degrees of the
      ++ polynomial p with respect to each of the variables in the list lv
    monicDivide : (%,%,VarSet) -> Record(quotient:%,remainder:%)
       ++ monicDivide(a,b,v) divides the polynomial a by the polynomial b,
       ++ with each viewed as a univariate polynomial in v returning
       ++ both the quotient and remainder.
       ++ Error: if b is not monic with respect to v.
    monomial : (%,VarSet,NonNegativeInteger) -> %
        ++ monomial(a,x,n) creates the monomial \spad{a*x**n} where \spad{a} is
        ++ a polynomial, x is a variable and n is a nonnegative integer.
    monomial : (%,List VarSet,List NonNegativeInteger) -> %
        ++ monomial(a,[v1..vn],[e1..en]) returns \spad{a*prod(vi**ei)}.
    multivariate : (SparseUnivariatePolynomial(R),VarSet) -> %
        ++ multivariate(sup,v) converts an anonymous univariable
        ++ polynomial sup to a polynomial in the variable v.
    multivariate : (SparseUnivariatePolynomial(%),VarSet) -> %
        ++ multivariate(sup,v) converts an anonymous univariable
        ++ polynomial sup to a polynomial in the variable v.
    isPlus: % -> Union(List %, "failed")
        ++ isPlus(p) returns \spad{[m1,...,mn]} if polynomial \spad{p = m1 + ... + mn} and
        ++ \spad{n >= 2} and each mi is a nonzero monomial.
    isTimes: % -> Union(List %, "failed")
        ++ isTimes(p) returns \spad{[a1,...,an]} if polynomial \spad{p = a1 ... an}
        ++ and \spad{n >= 2}, and, for each i, ai is either a nontrivial constant in R or else of the
        ++ form \spad{x**e}, where \spad{e > 0} is an integer and x in a member of VarSet.
    isExpt: % -> Union(Record(var:VarSet, exponent:NonNegativeInteger),_
                       "failed")
        ++ isExpt(p) returns \spad{[x, n]} if polynomial p has the form \spad{x**n} and \spad{n > 0}.
    totalDegree : % -> NonNegativeInteger
        ++ totalDegree(p) returns the largest sum over all monomials
        ++ of all exponents of a monomial.
    totalDegree : (%,List VarSet) -> NonNegativeInteger
        ++ totalDegree(p, lv) returns the maximum sum (over all monomials of polynomial p)
        ++ of the variables in the list lv.
    variables : % -> List(VarSet)
        ++ variables(p) returns the list of those variables actually
        ++ appearing in the polynomial p.
    primitiveMonomials: % -> List %
        ++ primitiveMonomials(p) gives the list of monomials of the
        ++ polynomial p with their coefficients removed.
        ++ Note: \spad{primitiveMonomials(sum(a_(i) X^(i))) = [X^(1),...,X^(n)]}.
    if R has OrderedSet  then OrderedSet
    -- OrderedRing view removed to allow EXPR to define abs
    --if R has OrderedRing then OrderedRing
    if (R has ConvertibleTo InputForm) and
       (VarSet has ConvertibleTo InputForm) then
         ConvertibleTo InputForm
    if (R has ConvertibleTo Pattern Integer) and
       (VarSet has ConvertibleTo Pattern Integer) then
         ConvertibleTo Pattern Integer
    if (R has ConvertibleTo Pattern Float) and
       (VarSet has ConvertibleTo Pattern Float) then
         ConvertibleTo Pattern Float
    if (R has PatternMatchable Integer) and
       (VarSet has PatternMatchable Integer) then
         PatternMatchable Integer
    if (R has PatternMatchable Float) and
       (VarSet has PatternMatchable Float) then
         PatternMatchable Float
    if R has CommutativeRing then
      resultant : (%,%,VarSet) -> %
         ++ resultant(p,q,v) returns the resultant of the polynomials
         ++ p and q with respect to the variable v.
      discriminant : (%,VarSet) -> %
         ++ discriminant(p,v) returns the disriminant of the polynomial p
         ++ with respect to the variable v.
    if R has GcdDomain then
      GcdDomain
      content: (%,VarSet) -> %
        ++ content(p,v) is the gcd of the coefficients of the polynomial p
        ++ when p is viewed as a univariate polynomial with respect to the
        ++ variable v.
        ++ Thus, for polynomial 7*x**2*y + 14*x*y**2, the gcd of the
        ++ coefficients with respect to x is 7*y.
      primitivePart: % -> %
        ++ primitivePart(p) returns the unitCanonical associate of the
        ++ polynomial p with its content divided out.
      primitivePart: (%,VarSet) -> %
        ++ primitivePart(p,v) returns the unitCanonical associate of the
        ++ polynomial p with its content with respect to the variable v
        ++ divided out.
      squareFree: % -> Factored %
        ++ squareFree(p) returns the square free factorization of the
        ++ polynomial p.
      squareFreePart: % -> %
        ++ squareFreePart(p) returns product of all the irreducible factors
        ++ of polynomial p each taken with multiplicity one.

    -- assertions
    if R has canonicalUnitNormal then canonicalUnitNormal
             ++ we can choose a unique representative for each
             ++ associate class.
             ++ This normalization is chosen to be normalization of
             ++ leading coefficient (by default).
    if R has PolynomialFactorizationExplicit then
       PolynomialFactorizationExplicit
 add
    p:%
    v:VarSet
    ln:List NonNegativeInteger
    lv:List VarSet
    n:NonNegativeInteger
    pp,qq:SparseUnivariatePolynomial %
    eval(p:%, l:List Equation %) ==
      empty? l => p
      for e in l repeat
        retractIfCan(lhs e)@Union(VarSet,"failed") case "failed" => 
             error "cannot find a variable to evaluate"
      lvar:=[retract(lhs e)@VarSet for e in l]
      eval(p, lvar,[rhs e for e in l]$List(%))
    monomials p ==
--    zero? p => empty()
--    concat(leadingMonomial p, monomials reductum p)
--    replaced by sequential version for efficiency, by WMSIT, 7/30/90
      ml:= empty$List(%)
      while p ^= 0 repeat
        ml:=concat(leadingMonomial p, ml)
        p:= reductum p
      reverse ml
    isPlus p ==
      empty? rest(l := monomials p) => "failed"
      l
    isTimes p ==
      empty?(lv := variables p) or not monomial? p => "failed"
      l := [monomial(1, v, degree(p, v)) for v in lv]
--      one?(r := leadingCoefficient p) =>
      ((r := leadingCoefficient p) = 1) =>
        empty? rest lv => "failed"
        l
      concat(r::%, l)
    isExpt p ==
      (u := mainVariable p) case "failed" => "failed"
      p = monomial(1, u::VarSet, d := degree(p, u::VarSet)) =>
        [u::VarSet, d]
      "failed"
    coefficient(p,v,n) == coefficient(univariate(p,v),n)
    coefficient(p,lv,ln) ==
       empty? lv =>
         empty? ln => p
         error "mismatched lists in coefficient"
       empty? ln  => error "mismatched lists in coefficient"
       coefficient(coefficient(univariate(p,first lv),first ln),
                   rest lv,rest ln)
    monomial(p,lv,ln) ==
       empty? lv =>
         empty? ln => p
         error "mismatched lists in monomial"
       empty? ln  => error "mismatched lists in monomial"
       monomial(monomial(p,first lv, first ln),rest lv, rest ln)
    retract(p:%):VarSet ==
      q := mainVariable(p)::VarSet
      q::% = p => q
      error "Polynomial is not a single variable"
    retractIfCan(p:%):Union(VarSet, "failed") ==
      ((q := mainVariable p) case VarSet) and (q::VarSet::% = p) => q
      "failed"
    mkPrim(p:%):% == monomial(1,degree p)
    primitiveMonomials p == [mkPrim q for q in monomials p]
    totalDegree p ==
        ground? p => 0
        u := univariate(p, mainVariable(p)::VarSet)
        d: NonNegativeInteger := 0
        while u ^= 0 repeat
          d := max(d, degree u + totalDegree leadingCoefficient u)
          u := reductum u
        d
    totalDegree(p,lv) ==
        ground? p => 0
        u := univariate(p, v:=(mainVariable(p)::VarSet))
        d: NonNegativeInteger := 0
        w: NonNegativeInteger := 0
        if member?(v, lv) then w:=1
        while u ^= 0 repeat
          d := max(d, w*(degree u) + totalDegree(leadingCoefficient u,lv))
          u := reductum u
        d

    if R has CommutativeRing then
        resultant(p1,p2,mvar) ==
          resultant(univariate(p1,mvar),univariate(p2,mvar))
        discriminant(p,var) ==
          discriminant(univariate(p,var))

    if R has IntegralDomain then
      allMonoms(l:List %):List(%) ==
        removeDuplicates_! concat [primitiveMonomials p for p in l]
      P2R(p:%, b:List E, n:NonNegativeInteger):Vector(R) ==
        w := new(n, 0)$Vector(R)
        for i in minIndex w .. maxIndex w for bj in b repeat
          qsetelt_!(w, i, coefficient(p, bj))
        w
      eq2R(l:List %, b:List E):Matrix(R) ==
        matrix [[coefficient(p, bj) for p in l] for bj in b]
      reducedSystem(m:Matrix %):Matrix(R) ==
        l := listOfLists m
        b := removeDuplicates_!
                           concat [allMonoms r for r in l]$List(List(%))
        d := [degree bj for bj in b]
        mm := eq2R(first l, d)
        l := rest l
        while not empty? l repeat
          mm := vertConcat(mm, eq2R(first l, d))
          l := rest l
        mm
      reducedSystem(m:Matrix %, v:Vector %):
       Record(mat:Matrix R, vec:Vector R) ==
        l := listOfLists m
        r := entries v
        b : List % := removeDuplicates_! concat(allMonoms r,
                          concat [allMonoms s for s in l]$List(List(%)))
        d := [degree bj for bj in b]
        n := #d
        mm := eq2R(first l, d)
        w := P2R(first r, d, n)
        l := rest l
        r := rest r
        while not empty? l repeat
          mm := vertConcat(mm, eq2R(first l, d))
          w := concat(w, P2R(first r, d, n))
          l := rest l
          r := rest r
        [mm, w]

    if R has PolynomialFactorizationExplicit then
       -- we might be in trouble if its actually only
       -- a univariate polynomial category - have to remember to
       -- over-ride these in UnivariatePolynomialCategory
       PFBR ==>PolynomialFactorizationByRecursion(R,E,VarSet,%)
       gcdPolynomial(pp,qq) ==
          gcdPolynomial(pp,qq)$GeneralPolynomialGcdPackage(E,VarSet,R,%)
       solveLinearPolynomialEquation(lpp,pp) ==
         solveLinearPolynomialEquationByRecursion(lpp,pp)$PFBR
       factorPolynomial(pp) ==
         factorByRecursion(pp)$PFBR
       factorSquareFreePolynomial(pp) ==
         factorSquareFreeByRecursion(pp)$PFBR
       factor p ==
         v:Union(VarSet,"failed"):=mainVariable p
         v case "failed" =>
           ansR:=factor leadingCoefficient p
           makeFR(unit(ansR)::%,
                  [[w.flg,w.fctr::%,w.xpnt] for w in factorList ansR])
         up:SparseUnivariatePolynomial %:=univariate(p,v)
         ansSUP:=factorByRecursion(up)$PFBR
         makeFR(multivariate(unit(ansSUP),v),
                [[ww.flg,multivariate(ww.fctr,v),ww.xpnt]
                 for ww in factorList ansSUP])
       if R has CharacteristicNonZero then
          mat: Matrix %
          conditionP mat ==
            ll:=listOfLists transpose mat   -- hence each list corresponds to a
                                            -- column, i.e. to one variable
            llR:List List R := [ empty() for z in first ll]
            monslist:List List % := empty()
            ch:=characteristic()$%
            for l in ll repeat
                mons:= "setUnion"/[primitiveMonomials u for u in l]
                redmons:List % :=[]
                for m in mons repeat
                    vars:=variables m
                    degs:=degree(m,vars)
                    deg1:List NonNegativeInteger
                    deg1:=[ ((nd:=d:Integer exquo ch:Integer)
                               case "failed" => return "failed" ;
                                nd::Integer::NonNegativeInteger)
                           for d in degs ]
                    redmons:=[monomial(1,vars,deg1),:redmons]
                    llR:=[[ground coefficient(u,vars,degs),:v] for u in l for v in llR]
                monslist:=[redmons,:monslist]
            ans:=conditionP transpose matrix llR
            ans case "failed" => "failed"
            i:NonNegativeInteger:=0
            [ +/[m*(ans.(i:=i+1))::% for m in mons ]
              for mons in monslist]

    if R has CharacteristicNonZero then
          charthRootlv: (%,List VarSet,NonNegativeInteger) -> Union(%,"failed")
          charthRoot p ==
            vars:= variables p
            empty? vars =>
              ans := charthRoot ground p
              ans case "failed" => "failed"
              ans::R::%
            ch:=characteristic()$%
            charthRootlv(p,vars,ch)
          charthRootlv(p,vars,ch) ==
            empty? vars =>
              ans := charthRoot ground p
              ans case "failed" => "failed"
              ans::R::%
            v:=first vars
            vars:=rest vars
            d:=degree(p,v)
            ans:% := 0
            while (d>0) repeat
               (dd:=(d::Integer exquo ch::Integer)) case "failed" =>
                      return "failed"
               cp:=coefficient(p,v,d)
               p:=p-monomial(cp,v,d)
               ansx:=charthRootlv(cp,vars,ch)
               ansx case "failed" => return "failed"
               d:=degree(p,v)
               ans:=ans+monomial(ansx,v,dd::Integer::NonNegativeInteger)
            ansx:=charthRootlv(p,vars,ch)
            ansx case "failed" => return "failed"
            return ans+ansx

    monicDivide(p1,p2,mvar) ==
       result:=monicDivide(univariate(p1,mvar),univariate(p2,mvar))
       [multivariate(result.quotient,mvar),
        multivariate(result.remainder,mvar)]


    if R has GcdDomain then
      if R has EuclideanDomain and R has CharacteristicZero then
       squareFree p == squareFree(p)$MultivariateSquareFree(E,VarSet,R,%)
      else
        squareFree p == squareFree(p)$PolynomialSquareFree(VarSet,E,R,%)
      squareFreePart p ==
        unit(s := squareFree p) * */[f.factor for f in factors s]
      content(p,v) == content univariate(p,v)
      primitivePart p ==
        unitNormal((p exquo content p) ::%).canonical
      primitivePart(p,v) ==
        unitNormal((p exquo content(p,v)) ::%).canonical
    if R has OrderedSet then
      p:% < q:% ==
        (dp:= degree p) < (dq := degree q) => (leadingCoefficient q) > 0
        dq < dp => (leadingCoefficient p) < 0
        leadingCoefficient(p - q) < 0
      if (R has PatternMatchable Integer) and
         (VarSet has PatternMatchable Integer) then
           patternMatch(p:%, pat:Pattern Integer,
            l:PatternMatchResult(Integer, %)) ==
              patternMatch(p, pat,
                l)$PatternMatchPolynomialCategory(Integer,E,VarSet,R,%)
      if (R has PatternMatchable Float) and
         (VarSet has PatternMatchable Float) then
           patternMatch(p:%, pat:Pattern Float,
            l:PatternMatchResult(Float, %)) ==
              patternMatch(p, pat,
                l)$PatternMatchPolynomialCategory(Float,E,VarSet,R,%)

    if (R has ConvertibleTo Pattern Integer) and
       (VarSet has ConvertibleTo Pattern Integer) then
         convert(x:%):Pattern(Integer) ==
           map(convert, convert,
              x)$PolynomialCategoryLifting(E,VarSet,R,%,Pattern Integer)
    if (R has ConvertibleTo Pattern Float) and
       (VarSet has ConvertibleTo Pattern Float) then
         convert(x:%):Pattern(Float) ==
           map(convert, convert,
            x)$PolynomialCategoryLifting(E, VarSet, R, %, Pattern Float)
    if (R has ConvertibleTo InputForm) and
       (VarSet has ConvertibleTo InputForm) then
         convert(p:%):InputForm ==
           map(convert, convert,
                    p)$PolynomialCategoryLifting(E,VarSet,R,%,InputForm)

@
\section{POLYCAT.lsp BOOTSTRAP}
{\bf POLYCAT} depends on itself. We need to break this cycle to build
the algebra. So we keep a cached copy of the translated {\bf POLYCAT}
category which we can write into the {\bf MID} directory. We compile 
the lisp code and copy the {\bf POLYCAT.o} file to the {\bf OUT} directory.
This is eventually forcibly replaced by a recompiled version. 

Note that this code is not included in the generated catdef.spad file.

<<POLYCAT.lsp BOOTSTRAP>>=

(/VERSIONCHECK 2) 

(DEFPARAMETER |PolynomialCategory;CAT| 'NIL) 

(DEFPARAMETER |PolynomialCategory;AL| 'NIL) 

(DEFUN |PolynomialCategory| (&REST #0=#:G1406 &AUX #1=#:G1404)
  (DSETQ #1# #0#)
  (LET (#2=#:G1405)
    (COND
      ((SETQ #2#
             (|assoc| (|devaluateList| #1#) |PolynomialCategory;AL|))
       (CDR #2#))
      (T (SETQ |PolynomialCategory;AL|
               (|cons5| (CONS (|devaluateList| #1#)
                              (SETQ #2#
                                    (APPLY #'|PolynomialCategory;| #1#)))
                        |PolynomialCategory;AL|))
         #2#)))) 

(DEFUN |PolynomialCategory;| (|t#1| |t#2| |t#3|)
  (PROG (#0=#:G1403)
    (RETURN
      (PROG1 (LETT #0#
                   (|sublisV|
                       (PAIR '(|t#1| |t#2| |t#3|)
                             (LIST (|devaluate| |t#1|)
                                   (|devaluate| |t#2|)
                                   (|devaluate| |t#3|)))
                       (COND
                         (|PolynomialCategory;CAT|)
                         ('T
                          (LETT |PolynomialCategory;CAT|
                                (|Join| (|PartialDifferentialRing|
                                         '|t#3|)
                                        (|FiniteAbelianMonoidRing|
                                         '|t#1| '|t#2|)
                                        (|Evalable| '$)
                                        (|InnerEvalable| '|t#3| '|t#1|)
                                        (|InnerEvalable| '|t#3| '$)
                                        (|RetractableTo| '|t#3|)
                                        (|FullyLinearlyExplicitRingOver|
                                         '|t#1|)
                                        (|mkCategory| '|domain|
                                         '(((|degree|
                                             ((|NonNegativeInteger|) $
                                              |t#3|))
                                            T)
                                           ((|degree|
                                             ((|List|
                                               (|NonNegativeInteger|))
                                              $ (|List| |t#3|)))
                                            T)
                                           ((|coefficient|
                                             ($ $ |t#3|
                                              (|NonNegativeInteger|)))
                                            T)
                                           ((|coefficient|
                                             ($ $ (|List| |t#3|)
                                              (|List|
                                               (|NonNegativeInteger|))))
                                            T)
                                           ((|monomials|
                                             ((|List| $) $))
                                            T)
                                           ((|univariate|
                                             ((|SparseUnivariatePolynomial|
                                               $)
                                              $ |t#3|))
                                            T)
                                           ((|univariate|
                                             ((|SparseUnivariatePolynomial|
                                               |t#1|)
                                              $))
                                            T)
                                           ((|mainVariable|
                                             ((|Union| |t#3| "failed")
                                              $))
                                            T)
                                           ((|minimumDegree|
                                             ((|NonNegativeInteger|) $
                                              |t#3|))
                                            T)
                                           ((|minimumDegree|
                                             ((|List|
                                               (|NonNegativeInteger|))
                                              $ (|List| |t#3|)))
                                            T)
                                           ((|monicDivide|
                                             ((|Record|
                                               (|:| |quotient| $)
                                               (|:| |remainder| $))
                                              $ $ |t#3|))
                                            T)
                                           ((|monomial|
                                             ($ $ |t#3|
                                              (|NonNegativeInteger|)))
                                            T)
                                           ((|monomial|
                                             ($ $ (|List| |t#3|)
                                              (|List|
                                               (|NonNegativeInteger|))))
                                            T)
                                           ((|multivariate|
                                             ($
                                              (|SparseUnivariatePolynomial|
                                               |t#1|)
                                              |t#3|))
                                            T)
                                           ((|multivariate|
                                             ($
                                              (|SparseUnivariatePolynomial|
                                               $)
                                              |t#3|))
                                            T)
                                           ((|isPlus|
                                             ((|Union| (|List| $)
                                               "failed")
                                              $))
                                            T)
                                           ((|isTimes|
                                             ((|Union| (|List| $)
                                               "failed")
                                              $))
                                            T)
                                           ((|isExpt|
                                             ((|Union|
                                               (|Record|
                                                (|:| |var| |t#3|)
                                                (|:| |exponent|
                                                 (|NonNegativeInteger|)))
                                               "failed")
                                              $))
                                            T)
                                           ((|totalDegree|
                                             ((|NonNegativeInteger|) $))
                                            T)
                                           ((|totalDegree|
                                             ((|NonNegativeInteger|) $
                                              (|List| |t#3|)))
                                            T)
                                           ((|variables|
                                             ((|List| |t#3|) $))
                                            T)
                                           ((|primitiveMonomials|
                                             ((|List| $) $))
                                            T)
                                           ((|resultant| ($ $ $ |t#3|))
                                            (|has| |t#1|
                                             (|CommutativeRing|)))
                                           ((|discriminant|
                                             ($ $ |t#3|))
                                            (|has| |t#1|
                                             (|CommutativeRing|)))
                                           ((|content| ($ $ |t#3|))
                                            (|has| |t#1| (|GcdDomain|)))
                                           ((|primitivePart| ($ $))
                                            (|has| |t#1| (|GcdDomain|)))
                                           ((|primitivePart|
                                             ($ $ |t#3|))
                                            (|has| |t#1| (|GcdDomain|)))
                                           ((|squareFree|
                                             ((|Factored| $) $))
                                            (|has| |t#1| (|GcdDomain|)))
                                           ((|squareFreePart| ($ $))
                                            (|has| |t#1| (|GcdDomain|))))
                                         '(((|OrderedSet|)
                                            (|has| |t#1|
                                             (|OrderedSet|)))
                                           ((|ConvertibleTo|
                                             (|InputForm|))
                                            (AND
                                             (|has| |t#3|
                                              (|ConvertibleTo|
                                               (|InputForm|)))
                                             (|has| |t#1|
                                              (|ConvertibleTo|
                                               (|InputForm|)))))
                                           ((|ConvertibleTo|
                                             (|Pattern| (|Integer|)))
                                            (AND
                                             (|has| |t#3|
                                              (|ConvertibleTo|
                                               (|Pattern| (|Integer|))))
                                             (|has| |t#1|
                                              (|ConvertibleTo|
                                               (|Pattern| (|Integer|))))))
                                           ((|ConvertibleTo|
                                             (|Pattern| (|Float|)))
                                            (AND
                                             (|has| |t#3|
                                              (|ConvertibleTo|
                                               (|Pattern| (|Float|))))
                                             (|has| |t#1|
                                              (|ConvertibleTo|
                                               (|Pattern| (|Float|))))))
                                           ((|PatternMatchable|
                                             (|Integer|))
                                            (AND
                                             (|has| |t#3|
                                              (|PatternMatchable|
                                               (|Integer|)))
                                             (|has| |t#1|
                                              (|PatternMatchable|
                                               (|Integer|)))))
                                           ((|PatternMatchable|
                                             (|Float|))
                                            (AND
                                             (|has| |t#3|
                                              (|PatternMatchable|
                                               (|Float|)))
                                             (|has| |t#1|
                                              (|PatternMatchable|
                                               (|Float|)))))
                                           ((|GcdDomain|)
                                            (|has| |t#1| (|GcdDomain|)))
                                           (|canonicalUnitNormal|
                                            (|has| |t#1|
                                             (ATTRIBUTE
                                              |canonicalUnitNormal|)))
                                           ((|PolynomialFactorizationExplicit|)
                                            (|has| |t#1|
                                             (|PolynomialFactorizationExplicit|))))
                                         '((|Factored| $) (|List| $)
                                           (|List| |t#3|)
                                           (|NonNegativeInteger|)
                                           (|SparseUnivariatePolynomial|
                                            $)
                                           (|SparseUnivariatePolynomial|
                                            |t#1|)
                                           (|List|
                                            (|NonNegativeInteger|)))
                                         NIL))
                                . #1=(|PolynomialCategory|))))) . #1#)
        (SETELT #0# 0
                (LIST '|PolynomialCategory| (|devaluate| |t#1|)
                      (|devaluate| |t#2|) (|devaluate| |t#3|))))))) 
@
\section{POLYCAT-.lsp BOOTSTRAP}
{\bf POLYCAT-} depends on {\bf POLYCAT}. We need to break this cycle to build
the algebra. So we keep a cached copy of the translated {\bf POLYCAT-}
category which we can write into the {\bf MID} directory. We compile 
the lisp code and copy the {\bf POLYCAT-.o} file to the {\bf OUT} directory.
This is eventually forcibly replaced by a recompiled version. 

Note that this code is not included in the generated catdef.spad file.

<<POLYCAT-.lsp BOOTSTRAP>>=

(/VERSIONCHECK 2) 

(DEFUN |POLYCAT-;eval;SLS;1| (|p| |l| $)
  (PROG (#0=#:G1420 #1=#:G1414 #2=#:G1421 #3=#:G1422 |lvar| #4=#:G1423
            |e| #5=#:G1424)
    (RETURN
      (SEQ (COND
             ((NULL |l|) |p|)
             ('T
              (SEQ (SEQ (EXIT (SEQ (LETT |e| NIL |POLYCAT-;eval;SLS;1|)
                                   (LETT #0# |l| |POLYCAT-;eval;SLS;1|)
                                   G190
                                   (COND
                                     ((OR (ATOM #0#)
                                       (PROGN
                                         (LETT |e| (CAR #0#)
                                          |POLYCAT-;eval;SLS;1|)
                                         NIL))
                                      (GO G191)))
                                   (SEQ
                                    (EXIT
                                     (COND
                                       ((QEQCAR
                                         (SPADCALL
                                          (SPADCALL |e| (QREFELT $ 11))
                                          (QREFELT $ 13))
                                         1)
                                        (PROGN
                                          (LETT #1#
                                           (|error|
                                            "cannot find a variable to evaluate")
                                           |POLYCAT-;eval;SLS;1|)
                                          (GO #1#))))))
                                   (LETT #0# (CDR #0#)
                                    |POLYCAT-;eval;SLS;1|)
                                   (GO G190) G191 (EXIT NIL)))
                        #1# (EXIT #1#))
                   (LETT |lvar|
                         (PROGN
                           (LETT #2# NIL |POLYCAT-;eval;SLS;1|)
                           (SEQ (LETT |e| NIL |POLYCAT-;eval;SLS;1|)
                                (LETT #3# |l| |POLYCAT-;eval;SLS;1|)
                                G190
                                (COND
                                  ((OR (ATOM #3#)
                                    (PROGN
                                      (LETT |e| (CAR #3#)
                                       |POLYCAT-;eval;SLS;1|)
                                      NIL))
                                   (GO G191)))
                                (SEQ (EXIT
                                      (LETT #2#
                                       (CONS
                                        (SPADCALL
                                         (SPADCALL |e| (QREFELT $ 11))
                                         (QREFELT $ 14))
                                        #2#)
                                       |POLYCAT-;eval;SLS;1|)))
                                (LETT #3# (CDR #3#)
                                      |POLYCAT-;eval;SLS;1|)
                                (GO G190) G191 (EXIT (NREVERSE0 #2#))))
                         |POLYCAT-;eval;SLS;1|)
                   (EXIT (SPADCALL |p| |lvar|
                             (PROGN
                               (LETT #4# NIL |POLYCAT-;eval;SLS;1|)
                               (SEQ (LETT |e| NIL
                                     |POLYCAT-;eval;SLS;1|)
                                    (LETT #5# |l|
                                     |POLYCAT-;eval;SLS;1|)
                                    G190
                                    (COND
                                      ((OR (ATOM #5#)
                                        (PROGN
                                          (LETT |e| (CAR #5#)
                                           |POLYCAT-;eval;SLS;1|)
                                          NIL))
                                       (GO G191)))
                                    (SEQ
                                     (EXIT
                                      (LETT #4#
                                       (CONS
                                        (SPADCALL |e| (QREFELT $ 15))
                                        #4#)
                                       |POLYCAT-;eval;SLS;1|)))
                                    (LETT #5# (CDR #5#)
                                     |POLYCAT-;eval;SLS;1|)
                                    (GO G190) G191
                                    (EXIT (NREVERSE0 #4#))))
                             (QREFELT $ 18)))))))))) 

(DEFUN |POLYCAT-;monomials;SL;2| (|p| $)
  (PROG (|ml|)
    (RETURN
      (SEQ (LETT |ml| NIL |POLYCAT-;monomials;SL;2|)
           (SEQ G190
                (COND
                  ((NULL (SPADCALL
                             (SPADCALL |p| (|spadConstant| $ 21)
                                 (QREFELT $ 24))
                             (QREFELT $ 25)))
                   (GO G191)))
                (SEQ (LETT |ml|
                           (CONS (SPADCALL |p| (QREFELT $ 26)) |ml|)
                           |POLYCAT-;monomials;SL;2|)
                     (EXIT (LETT |p| (SPADCALL |p| (QREFELT $ 27))
                                 |POLYCAT-;monomials;SL;2|)))
                NIL (GO G190) G191 (EXIT NIL))
           (EXIT (REVERSE |ml|)))))) 

(DEFUN |POLYCAT-;isPlus;SU;3| (|p| $)
  (PROG (|l|)
    (RETURN
      (COND
        ((NULL (CDR (LETT |l| (SPADCALL |p| (QREFELT $ 29))
                          |POLYCAT-;isPlus;SU;3|)))
         (CONS 1 "failed"))
        ('T (CONS 0 |l|)))))) 

(DEFUN |POLYCAT-;isTimes;SU;4| (|p| $)
  (PROG (|lv| #0=#:G1446 |v| #1=#:G1447 |l| |r|)
    (RETURN
      (SEQ (COND
             ((OR (NULL (LETT |lv| (SPADCALL |p| (QREFELT $ 32))
                              |POLYCAT-;isTimes;SU;4|))
                  (NULL (SPADCALL |p| (QREFELT $ 33))))
              (CONS 1 "failed"))
             ('T
              (SEQ (LETT |l|
                         (PROGN
                           (LETT #0# NIL |POLYCAT-;isTimes;SU;4|)
                           (SEQ (LETT |v| NIL |POLYCAT-;isTimes;SU;4|)
                                (LETT #1# |lv| |POLYCAT-;isTimes;SU;4|)
                                G190
                                (COND
                                  ((OR (ATOM #1#)
                                    (PROGN
                                      (LETT |v| (CAR #1#)
                                       |POLYCAT-;isTimes;SU;4|)
                                      NIL))
                                   (GO G191)))
                                (SEQ (EXIT
                                      (LETT #0#
                                       (CONS
                                        (SPADCALL (|spadConstant| $ 34)
                                         |v|
                                         (SPADCALL |p| |v|
                                          (QREFELT $ 37))
                                         (QREFELT $ 38))
                                        #0#)
                                       |POLYCAT-;isTimes;SU;4|)))
                                (LETT #1# (CDR #1#)
                                      |POLYCAT-;isTimes;SU;4|)
                                (GO G190) G191 (EXIT (NREVERSE0 #0#))))
                         |POLYCAT-;isTimes;SU;4|)
                   (LETT |r| (SPADCALL |p| (QREFELT $ 39))
                         |POLYCAT-;isTimes;SU;4|)
                   (EXIT (COND
                           ((SPADCALL |r| (|spadConstant| $ 35)
                                (QREFELT $ 40))
                            (COND
                              ((NULL (CDR |lv|)) (CONS 1 "failed"))
                              ('T (CONS 0 |l|))))
                           ('T
                            (CONS 0
                                  (CONS (SPADCALL |r| (QREFELT $ 41))
                                        |l|)))))))))))) 

(DEFUN |POLYCAT-;isExpt;SU;5| (|p| $)
  (PROG (|u| |d|)
    (RETURN
      (SEQ (LETT |u| (SPADCALL |p| (QREFELT $ 43))
                 |POLYCAT-;isExpt;SU;5|)
           (EXIT (COND
                   ((OR (QEQCAR |u| 1)
                        (NULL (SPADCALL |p|
                                  (SPADCALL (|spadConstant| $ 34)
                                      (QCDR |u|)
                                      (LETT |d|
                                       (SPADCALL |p| (QCDR |u|)
                                        (QREFELT $ 37))
                                       |POLYCAT-;isExpt;SU;5|)
                                      (QREFELT $ 38))
                                  (QREFELT $ 24))))
                    (CONS 1 "failed"))
                   ('T (CONS 0 (CONS (QCDR |u|) |d|))))))))) 

(DEFUN |POLYCAT-;coefficient;SVarSetNniS;6| (|p| |v| |n| $)
  (SPADCALL (SPADCALL |p| |v| (QREFELT $ 48)) |n| (QREFELT $ 50))) 

(DEFUN |POLYCAT-;coefficient;SLLS;7| (|p| |lv| |ln| $)
  (COND
    ((NULL |lv|)
     (COND
       ((NULL |ln|) |p|)
       ('T (|error| "mismatched lists in coefficient"))))
    ((NULL |ln|) (|error| "mismatched lists in coefficient"))
    ('T
     (SPADCALL
         (SPADCALL (SPADCALL |p| (|SPADfirst| |lv|) (QREFELT $ 48))
             (|SPADfirst| |ln|) (QREFELT $ 50))
         (CDR |lv|) (CDR |ln|) (QREFELT $ 53))))) 

(DEFUN |POLYCAT-;monomial;SLLS;8| (|p| |lv| |ln| $)
  (COND
    ((NULL |lv|)
     (COND
       ((NULL |ln|) |p|)
       ('T (|error| "mismatched lists in monomial"))))
    ((NULL |ln|) (|error| "mismatched lists in monomial"))
    ('T
     (SPADCALL
         (SPADCALL |p| (|SPADfirst| |lv|) (|SPADfirst| |ln|)
             (QREFELT $ 38))
         (CDR |lv|) (CDR |ln|) (QREFELT $ 55))))) 

(DEFUN |POLYCAT-;retract;SVarSet;9| (|p| $)
  (PROG (#0=#:G1472 |q|)
    (RETURN
      (SEQ (LETT |q|
                 (PROG2 (LETT #0# (SPADCALL |p| (QREFELT $ 43))
                              |POLYCAT-;retract;SVarSet;9|)
                        (QCDR #0#)
                   (|check-union| (QEQCAR #0# 0) (QREFELT $ 9) #0#))
                 |POLYCAT-;retract;SVarSet;9|)
           (EXIT (COND
                   ((SPADCALL (SPADCALL |q| (QREFELT $ 57)) |p|
                        (QREFELT $ 24))
                    |q|)
                   ('T (|error| "Polynomial is not a single variable")))))))) 

(DEFUN |POLYCAT-;retractIfCan;SU;10| (|p| $)
  (PROG (|q| #0=#:G1480)
    (RETURN
      (SEQ (EXIT (SEQ (SEQ (LETT |q| (SPADCALL |p| (QREFELT $ 43))
                                 |POLYCAT-;retractIfCan;SU;10|)
                           (EXIT (COND
                                   ((QEQCAR |q| 0)
                                    (COND
                                      ((SPADCALL
                                        (SPADCALL (QCDR |q|)
                                         (QREFELT $ 57))
                                        |p| (QREFELT $ 24))
                                       (PROGN
                                         (LETT #0# |q|
                                          |POLYCAT-;retractIfCan;SU;10|)
                                         (GO #0#))))))))
                      (EXIT (CONS 1 "failed"))))
           #0# (EXIT #0#))))) 

(DEFUN |POLYCAT-;mkPrim| (|p| $)
  (SPADCALL (|spadConstant| $ 35) (SPADCALL |p| (QREFELT $ 60))
      (QREFELT $ 61))) 

(DEFUN |POLYCAT-;primitiveMonomials;SL;12| (|p| $)
  (PROG (#0=#:G1485 |q| #1=#:G1486)
    (RETURN
      (SEQ (PROGN
             (LETT #0# NIL |POLYCAT-;primitiveMonomials;SL;12|)
             (SEQ (LETT |q| NIL |POLYCAT-;primitiveMonomials;SL;12|)
                  (LETT #1# (SPADCALL |p| (QREFELT $ 29))
                        |POLYCAT-;primitiveMonomials;SL;12|)
                  G190
                  (COND
                    ((OR (ATOM #1#)
                         (PROGN
                           (LETT |q| (CAR #1#)
                                 |POLYCAT-;primitiveMonomials;SL;12|)
                           NIL))
                     (GO G191)))
                  (SEQ (EXIT (LETT #0#
                                   (CONS (|POLYCAT-;mkPrim| |q| $) #0#)
                                   |POLYCAT-;primitiveMonomials;SL;12|)))
                  (LETT #1# (CDR #1#)
                        |POLYCAT-;primitiveMonomials;SL;12|)
                  (GO G190) G191 (EXIT (NREVERSE0 #0#)))))))) 

(DEFUN |POLYCAT-;totalDegree;SNni;13| (|p| $)
  (PROG (#0=#:G1488 |d| |u|)
    (RETURN
      (SEQ (COND
             ((SPADCALL |p| (QREFELT $ 63)) 0)
             ('T
              (SEQ (LETT |u|
                         (SPADCALL |p|
                             (PROG2 (LETT #0#
                                     (SPADCALL |p| (QREFELT $ 43))
                                     |POLYCAT-;totalDegree;SNni;13|)
                                    (QCDR #0#)
                               (|check-union| (QEQCAR #0# 0)
                                   (QREFELT $ 9) #0#))
                             (QREFELT $ 48))
                         |POLYCAT-;totalDegree;SNni;13|)
                   (LETT |d| 0 |POLYCAT-;totalDegree;SNni;13|)
                   (SEQ G190
                        (COND
                          ((NULL (SPADCALL
                                     (SPADCALL |u|
                                      (|spadConstant| $ 64)
                                      (QREFELT $ 65))
                                     (QREFELT $ 25)))
                           (GO G191)))
                        (SEQ (LETT |d|
                                   (MAX |d|
                                    (+ (SPADCALL |u| (QREFELT $ 66))
                                     (SPADCALL
                                      (SPADCALL |u| (QREFELT $ 67))
                                      (QREFELT $ 68))))
                                   |POLYCAT-;totalDegree;SNni;13|)
                             (EXIT (LETT |u|
                                    (SPADCALL |u| (QREFELT $ 69))
                                    |POLYCAT-;totalDegree;SNni;13|)))
                        NIL (GO G190) G191 (EXIT NIL))
                   (EXIT |d|)))))))) 

(DEFUN |POLYCAT-;totalDegree;SLNni;14| (|p| |lv| $)
  (PROG (#0=#:G1496 |v| |w| |d| |u|)
    (RETURN
      (SEQ (COND
             ((SPADCALL |p| (QREFELT $ 63)) 0)
             ('T
              (SEQ (LETT |u|
                         (SPADCALL |p|
                             (LETT |v|
                                   (PROG2
                                    (LETT #0#
                                     (SPADCALL |p| (QREFELT $ 43))
                                     |POLYCAT-;totalDegree;SLNni;14|)
                                    (QCDR #0#)
                                     (|check-union| (QEQCAR #0# 0)
                                      (QREFELT $ 9) #0#))
                                   |POLYCAT-;totalDegree;SLNni;14|)
                             (QREFELT $ 48))
                         |POLYCAT-;totalDegree;SLNni;14|)
                   (LETT |d| 0 |POLYCAT-;totalDegree;SLNni;14|)
                   (LETT |w| 0 |POLYCAT-;totalDegree;SLNni;14|)
                   (COND
                     ((SPADCALL |v| |lv| (QREFELT $ 71))
                      (LETT |w| 1 |POLYCAT-;totalDegree;SLNni;14|)))
                   (SEQ G190
                        (COND
                          ((NULL (SPADCALL
                                     (SPADCALL |u|
                                      (|spadConstant| $ 64)
                                      (QREFELT $ 65))
                                     (QREFELT $ 25)))
                           (GO G191)))
                        (SEQ (LETT |d|
                                   (MAX |d|
                                    (+
                                     (* |w|
                                      (SPADCALL |u| (QREFELT $ 66)))
                                     (SPADCALL
                                      (SPADCALL |u| (QREFELT $ 67))
                                      |lv| (QREFELT $ 72))))
                                   |POLYCAT-;totalDegree;SLNni;14|)
                             (EXIT (LETT |u|
                                    (SPADCALL |u| (QREFELT $ 69))
                                    |POLYCAT-;totalDegree;SLNni;14|)))
                        NIL (GO G190) G191 (EXIT NIL))
                   (EXIT |d|)))))))) 

(DEFUN |POLYCAT-;resultant;2SVarSetS;15| (|p1| |p2| |mvar| $)
  (SPADCALL (SPADCALL |p1| |mvar| (QREFELT $ 48))
      (SPADCALL |p2| |mvar| (QREFELT $ 48)) (QREFELT $ 74))) 

(DEFUN |POLYCAT-;discriminant;SVarSetS;16| (|p| |var| $)
  (SPADCALL (SPADCALL |p| |var| (QREFELT $ 48)) (QREFELT $ 76))) 

(DEFUN |POLYCAT-;allMonoms| (|l| $)
  (PROG (#0=#:G1508 |p| #1=#:G1509)
    (RETURN
      (SEQ (SPADCALL
               (SPADCALL
                   (PROGN
                     (LETT #0# NIL |POLYCAT-;allMonoms|)
                     (SEQ (LETT |p| NIL |POLYCAT-;allMonoms|)
                          (LETT #1# |l| |POLYCAT-;allMonoms|) G190
                          (COND
                            ((OR (ATOM #1#)
                                 (PROGN
                                   (LETT |p| (CAR #1#)
                                    |POLYCAT-;allMonoms|)
                                   NIL))
                             (GO G191)))
                          (SEQ (EXIT (LETT #0#
                                      (CONS
                                       (SPADCALL |p| (QREFELT $ 78))
                                       #0#)
                                      |POLYCAT-;allMonoms|)))
                          (LETT #1# (CDR #1#) |POLYCAT-;allMonoms|)
                          (GO G190) G191 (EXIT (NREVERSE0 #0#))))
                   (QREFELT $ 80))
               (QREFELT $ 81)))))) 

(DEFUN |POLYCAT-;P2R| (|p| |b| |n| $)
  (PROG (|w| |bj| #0=#:G1514 |i| #1=#:G1513)
    (RETURN
      (SEQ (LETT |w|
                 (SPADCALL |n| (|spadConstant| $ 22) (QREFELT $ 83))
                 |POLYCAT-;P2R|)
           (SEQ (LETT |bj| NIL |POLYCAT-;P2R|)
                (LETT #0# |b| |POLYCAT-;P2R|)
                (LETT |i| (SPADCALL |w| (QREFELT $ 85)) |POLYCAT-;P2R|)
                (LETT #1# (QVSIZE |w|) |POLYCAT-;P2R|) G190
                (COND
                  ((OR (> |i| #1#) (ATOM #0#)
                       (PROGN
                         (LETT |bj| (CAR #0#) |POLYCAT-;P2R|)
                         NIL))
                   (GO G191)))
                (SEQ (EXIT (SPADCALL |w| |i|
                               (SPADCALL |p| |bj| (QREFELT $ 86))
                               (QREFELT $ 87))))
                (LETT |i|
                      (PROG1 (+ |i| 1)
                        (LETT #0# (CDR #0#) |POLYCAT-;P2R|))
                      |POLYCAT-;P2R|)
                (GO G190) G191 (EXIT NIL))
           (EXIT |w|))))) 

(DEFUN |POLYCAT-;eq2R| (|l| |b| $)
  (PROG (#0=#:G1518 |bj| #1=#:G1519 #2=#:G1520 |p| #3=#:G1521)
    (RETURN
      (SEQ (SPADCALL
               (PROGN
                 (LETT #0# NIL |POLYCAT-;eq2R|)
                 (SEQ (LETT |bj| NIL |POLYCAT-;eq2R|)
                      (LETT #1# |b| |POLYCAT-;eq2R|) G190
                      (COND
                        ((OR (ATOM #1#)
                             (PROGN
                               (LETT |bj| (CAR #1#) |POLYCAT-;eq2R|)
                               NIL))
                         (GO G191)))
                      (SEQ (EXIT (LETT #0#
                                       (CONS
                                        (PROGN
                                          (LETT #2# NIL
                                           |POLYCAT-;eq2R|)
                                          (SEQ
                                           (LETT |p| NIL
                                            |POLYCAT-;eq2R|)
                                           (LETT #3# |l|
                                            |POLYCAT-;eq2R|)
                                           G190
                                           (COND
                                             ((OR (ATOM #3#)
                                               (PROGN
                                                 (LETT |p| (CAR #3#)
                                                  |POLYCAT-;eq2R|)
                                                 NIL))
                                              (GO G191)))
                                           (SEQ
                                            (EXIT
                                             (LETT #2#
                                              (CONS
                                               (SPADCALL |p| |bj|
                                                (QREFELT $ 86))
                                               #2#)
                                              |POLYCAT-;eq2R|)))
                                           (LETT #3# (CDR #3#)
                                            |POLYCAT-;eq2R|)
                                           (GO G190) G191
                                           (EXIT (NREVERSE0 #2#))))
                                        #0#)
                                       |POLYCAT-;eq2R|)))
                      (LETT #1# (CDR #1#) |POLYCAT-;eq2R|) (GO G190)
                      G191 (EXIT (NREVERSE0 #0#))))
               (QREFELT $ 90)))))) 

(DEFUN |POLYCAT-;reducedSystem;MM;20| (|m| $)
  (PROG (#0=#:G1530 |r| #1=#:G1531 |b| #2=#:G1532 |bj| #3=#:G1533 |d|
            |mm| |l|)
    (RETURN
      (SEQ (LETT |l| (SPADCALL |m| (QREFELT $ 93))
                 |POLYCAT-;reducedSystem;MM;20|)
           (LETT |b|
                 (SPADCALL
                     (SPADCALL
                         (PROGN
                           (LETT #0# NIL
                                 |POLYCAT-;reducedSystem;MM;20|)
                           (SEQ (LETT |r| NIL
                                      |POLYCAT-;reducedSystem;MM;20|)
                                (LETT #1# |l|
                                      |POLYCAT-;reducedSystem;MM;20|)
                                G190
                                (COND
                                  ((OR (ATOM #1#)
                                    (PROGN
                                      (LETT |r| (CAR #1#)
                                       |POLYCAT-;reducedSystem;MM;20|)
                                      NIL))
                                   (GO G191)))
                                (SEQ (EXIT
                                      (LETT #0#
                                       (CONS
                                        (|POLYCAT-;allMonoms| |r| $)
                                        #0#)
                                       |POLYCAT-;reducedSystem;MM;20|)))
                                (LETT #1# (CDR #1#)
                                      |POLYCAT-;reducedSystem;MM;20|)
                                (GO G190) G191 (EXIT (NREVERSE0 #0#))))
                         (QREFELT $ 80))
                     (QREFELT $ 81))
                 |POLYCAT-;reducedSystem;MM;20|)
           (LETT |d|
                 (PROGN
                   (LETT #2# NIL |POLYCAT-;reducedSystem;MM;20|)
                   (SEQ (LETT |bj| NIL |POLYCAT-;reducedSystem;MM;20|)
                        (LETT #3# |b| |POLYCAT-;reducedSystem;MM;20|)
                        G190
                        (COND
                          ((OR (ATOM #3#)
                               (PROGN
                                 (LETT |bj| (CAR #3#)
                                       |POLYCAT-;reducedSystem;MM;20|)
                                 NIL))
                           (GO G191)))
                        (SEQ (EXIT (LETT #2#
                                    (CONS
                                     (SPADCALL |bj| (QREFELT $ 60))
                                     #2#)
                                    |POLYCAT-;reducedSystem;MM;20|)))
                        (LETT #3# (CDR #3#)
                              |POLYCAT-;reducedSystem;MM;20|)
                        (GO G190) G191 (EXIT (NREVERSE0 #2#))))
                 |POLYCAT-;reducedSystem;MM;20|)
           (LETT |mm| (|POLYCAT-;eq2R| (|SPADfirst| |l|) |d| $)
                 |POLYCAT-;reducedSystem;MM;20|)
           (LETT |l| (CDR |l|) |POLYCAT-;reducedSystem;MM;20|)
           (SEQ G190
                (COND
                  ((NULL (SPADCALL (NULL |l|) (QREFELT $ 25)))
                   (GO G191)))
                (SEQ (LETT |mm|
                           (SPADCALL |mm|
                               (|POLYCAT-;eq2R| (|SPADfirst| |l|) |d|
                                   $)
                               (QREFELT $ 94))
                           |POLYCAT-;reducedSystem;MM;20|)
                     (EXIT (LETT |l| (CDR |l|)
                                 |POLYCAT-;reducedSystem;MM;20|)))
                NIL (GO G190) G191 (EXIT NIL))
           (EXIT |mm|))))) 

(DEFUN |POLYCAT-;reducedSystem;MVR;21| (|m| |v| $)
  (PROG (#0=#:G1544 |s| #1=#:G1545 |b| #2=#:G1546 |bj| #3=#:G1547 |d|
            |n| |mm| |w| |l| |r|)
    (RETURN
      (SEQ (LETT |l| (SPADCALL |m| (QREFELT $ 93))
                 |POLYCAT-;reducedSystem;MVR;21|)
           (LETT |r| (SPADCALL |v| (QREFELT $ 98))
                 |POLYCAT-;reducedSystem;MVR;21|)
           (LETT |b|
                 (SPADCALL
                     (SPADCALL (|POLYCAT-;allMonoms| |r| $)
                         (SPADCALL
                             (PROGN
                               (LETT #0# NIL
                                     |POLYCAT-;reducedSystem;MVR;21|)
                               (SEQ (LETT |s| NIL
                                     |POLYCAT-;reducedSystem;MVR;21|)
                                    (LETT #1# |l|
                                     |POLYCAT-;reducedSystem;MVR;21|)
                                    G190
                                    (COND
                                      ((OR (ATOM #1#)
                                        (PROGN
                                          (LETT |s| (CAR #1#)
                                           |POLYCAT-;reducedSystem;MVR;21|)
                                          NIL))
                                       (GO G191)))
                                    (SEQ
                                     (EXIT
                                      (LETT #0#
                                       (CONS
                                        (|POLYCAT-;allMonoms| |s| $)
                                        #0#)
                                       |POLYCAT-;reducedSystem;MVR;21|)))
                                    (LETT #1# (CDR #1#)
                                     |POLYCAT-;reducedSystem;MVR;21|)
                                    (GO G190) G191
                                    (EXIT (NREVERSE0 #0#))))
                             (QREFELT $ 80))
                         (QREFELT $ 99))
                     (QREFELT $ 81))
                 |POLYCAT-;reducedSystem;MVR;21|)
           (LETT |d|
                 (PROGN
                   (LETT #2# NIL |POLYCAT-;reducedSystem;MVR;21|)
                   (SEQ (LETT |bj| NIL |POLYCAT-;reducedSystem;MVR;21|)
                        (LETT #3# |b| |POLYCAT-;reducedSystem;MVR;21|)
                        G190
                        (COND
                          ((OR (ATOM #3#)
                               (PROGN
                                 (LETT |bj| (CAR #3#)
                                       |POLYCAT-;reducedSystem;MVR;21|)
                                 NIL))
                           (GO G191)))
                        (SEQ (EXIT (LETT #2#
                                    (CONS
                                     (SPADCALL |bj| (QREFELT $ 60))
                                     #2#)
                                    |POLYCAT-;reducedSystem;MVR;21|)))
                        (LETT #3# (CDR #3#)
                              |POLYCAT-;reducedSystem;MVR;21|)
                        (GO G190) G191 (EXIT (NREVERSE0 #2#))))
                 |POLYCAT-;reducedSystem;MVR;21|)
           (LETT |n| (LENGTH |d|) |POLYCAT-;reducedSystem;MVR;21|)
           (LETT |mm| (|POLYCAT-;eq2R| (|SPADfirst| |l|) |d| $)
                 |POLYCAT-;reducedSystem;MVR;21|)
           (LETT |w| (|POLYCAT-;P2R| (|SPADfirst| |r|) |d| |n| $)
                 |POLYCAT-;reducedSystem;MVR;21|)
           (LETT |l| (CDR |l|) |POLYCAT-;reducedSystem;MVR;21|)
           (LETT |r| (CDR |r|) |POLYCAT-;reducedSystem;MVR;21|)
           (SEQ G190
                (COND
                  ((NULL (SPADCALL (NULL |l|) (QREFELT $ 25)))
                   (GO G191)))
                (SEQ (LETT |mm|
                           (SPADCALL |mm|
                               (|POLYCAT-;eq2R| (|SPADfirst| |l|) |d|
                                   $)
                               (QREFELT $ 94))
                           |POLYCAT-;reducedSystem;MVR;21|)
                     (LETT |w|
                           (SPADCALL |w|
                               (|POLYCAT-;P2R| (|SPADfirst| |r|) |d|
                                   |n| $)
                               (QREFELT $ 100))
                           |POLYCAT-;reducedSystem;MVR;21|)
                     (LETT |l| (CDR |l|)
                           |POLYCAT-;reducedSystem;MVR;21|)
                     (EXIT (LETT |r| (CDR |r|)
                                 |POLYCAT-;reducedSystem;MVR;21|)))
                NIL (GO G190) G191 (EXIT NIL))
           (EXIT (CONS |mm| |w|)))))) 

(DEFUN |POLYCAT-;gcdPolynomial;3Sup;22| (|pp| |qq| $)
  (SPADCALL |pp| |qq| (QREFELT $ 105))) 

(DEFUN |POLYCAT-;solveLinearPolynomialEquation;LSupU;23| (|lpp| |pp| $)
  (SPADCALL |lpp| |pp| (QREFELT $ 110))) 

(DEFUN |POLYCAT-;factorPolynomial;SupF;24| (|pp| $)
  (SPADCALL |pp| (QREFELT $ 115))) 

(DEFUN |POLYCAT-;factorSquareFreePolynomial;SupF;25| (|pp| $)
  (SPADCALL |pp| (QREFELT $ 118))) 

(DEFUN |POLYCAT-;factor;SF;26| (|p| $)
  (PROG (|v| |ansR| #0=#:G1589 |w| #1=#:G1590 |up| |ansSUP| #2=#:G1591
             |ww| #3=#:G1592)
    (RETURN
      (SEQ (LETT |v| (SPADCALL |p| (QREFELT $ 43))
                 |POLYCAT-;factor;SF;26|)
           (EXIT (COND
                   ((QEQCAR |v| 1)
                    (SEQ (LETT |ansR|
                               (SPADCALL (SPADCALL |p| (QREFELT $ 39))
                                   (QREFELT $ 121))
                               |POLYCAT-;factor;SF;26|)
                         (EXIT (SPADCALL
                                   (SPADCALL
                                    (SPADCALL |ansR| (QREFELT $ 123))
                                    (QREFELT $ 41))
                                   (PROGN
                                     (LETT #0# NIL
                                      |POLYCAT-;factor;SF;26|)
                                     (SEQ
                                      (LETT |w| NIL
                                       |POLYCAT-;factor;SF;26|)
                                      (LETT #1#
                                       (SPADCALL |ansR|
                                        (QREFELT $ 127))
                                       |POLYCAT-;factor;SF;26|)
                                      G190
                                      (COND
                                        ((OR (ATOM #1#)
                                          (PROGN
                                            (LETT |w| (CAR #1#)
                                             |POLYCAT-;factor;SF;26|)
                                            NIL))
                                         (GO G191)))
                                      (SEQ
                                       (EXIT
                                        (LETT #0#
                                         (CONS
                                          (VECTOR (QVELT |w| 0)
                                           (SPADCALL (QVELT |w| 1)
                                            (QREFELT $ 41))
                                           (QVELT |w| 2))
                                          #0#)
                                         |POLYCAT-;factor;SF;26|)))
                                      (LETT #1# (CDR #1#)
                                       |POLYCAT-;factor;SF;26|)
                                      (GO G190) G191
                                      (EXIT (NREVERSE0 #0#))))
                                   (QREFELT $ 131)))))
                   ('T
                    (SEQ (LETT |up|
                               (SPADCALL |p| (QCDR |v|) (QREFELT $ 48))
                               |POLYCAT-;factor;SF;26|)
                         (LETT |ansSUP| (SPADCALL |up| (QREFELT $ 115))
                               |POLYCAT-;factor;SF;26|)
                         (EXIT (SPADCALL
                                   (SPADCALL
                                    (SPADCALL |ansSUP| (QREFELT $ 132))
                                    (QCDR |v|) (QREFELT $ 133))
                                   (PROGN
                                     (LETT #2# NIL
                                      |POLYCAT-;factor;SF;26|)
                                     (SEQ
                                      (LETT |ww| NIL
                                       |POLYCAT-;factor;SF;26|)
                                      (LETT #3#
                                       (SPADCALL |ansSUP|
                                        (QREFELT $ 136))
                                       |POLYCAT-;factor;SF;26|)
                                      G190
                                      (COND
                                        ((OR (ATOM #3#)
                                          (PROGN
                                            (LETT |ww| (CAR #3#)
                                             |POLYCAT-;factor;SF;26|)
                                            NIL))
                                         (GO G191)))
                                      (SEQ
                                       (EXIT
                                        (LETT #2#
                                         (CONS
                                          (VECTOR (QVELT |ww| 0)
                                           (SPADCALL (QVELT |ww| 1)
                                            (QCDR |v|) (QREFELT $ 133))
                                           (QVELT |ww| 2))
                                          #2#)
                                         |POLYCAT-;factor;SF;26|)))
                                      (LETT #3# (CDR #3#)
                                       |POLYCAT-;factor;SF;26|)
                                      (GO G190) G191
                                      (EXIT (NREVERSE0 #2#))))
                                   (QREFELT $ 131))))))))))) 

(DEFUN |POLYCAT-;conditionP;MU;27| (|mat| $)
  (PROG (|ll| #0=#:G1627 |z| #1=#:G1628 |ch| |l| #2=#:G1629 #3=#:G1630
              #4=#:G1599 #5=#:G1597 #6=#:G1598 #7=#:G1631 |vars| |degs|
              #8=#:G1632 |d| #9=#:G1633 |nd| #10=#:G1626 #11=#:G1606
              |deg1| |redmons| #12=#:G1634 |v| #13=#:G1636 |u|
              #14=#:G1635 |llR| |monslist| |ans| #15=#:G1637
              #16=#:G1638 |mons| #17=#:G1639 |m| #18=#:G1640 |i|
              #19=#:G1622 #20=#:G1620 #21=#:G1621)
    (RETURN
      (SEQ (EXIT (SEQ (LETT |ll|
                            (SPADCALL (SPADCALL |mat| (QREFELT $ 138))
                                (QREFELT $ 93))
                            |POLYCAT-;conditionP;MU;27|)
                      (LETT |llR|
                            (PROGN
                              (LETT #0# NIL
                                    |POLYCAT-;conditionP;MU;27|)
                              (SEQ (LETT |z| NIL
                                    |POLYCAT-;conditionP;MU;27|)
                                   (LETT #1# (|SPADfirst| |ll|)
                                    |POLYCAT-;conditionP;MU;27|)
                                   G190
                                   (COND
                                     ((OR (ATOM #1#)
                                       (PROGN
                                         (LETT |z| (CAR #1#)
                                          |POLYCAT-;conditionP;MU;27|)
                                         NIL))
                                      (GO G191)))
                                   (SEQ
                                    (EXIT
                                     (LETT #0# (CONS NIL #0#)
                                      |POLYCAT-;conditionP;MU;27|)))
                                   (LETT #1# (CDR #1#)
                                    |POLYCAT-;conditionP;MU;27|)
                                   (GO G190) G191
                                   (EXIT (NREVERSE0 #0#))))
                            |POLYCAT-;conditionP;MU;27|)
                      (LETT |monslist| NIL |POLYCAT-;conditionP;MU;27|)
                      (LETT |ch| (SPADCALL (QREFELT $ 139))
                            |POLYCAT-;conditionP;MU;27|)
                      (SEQ (LETT |l| NIL |POLYCAT-;conditionP;MU;27|)
                           (LETT #2# |ll| |POLYCAT-;conditionP;MU;27|)
                           G190
                           (COND
                             ((OR (ATOM #2#)
                                  (PROGN
                                    (LETT |l| (CAR #2#)
                                     |POLYCAT-;conditionP;MU;27|)
                                    NIL))
                              (GO G191)))
                           (SEQ (LETT |mons|
                                      (PROGN
                                        (LETT #6# NIL
                                         |POLYCAT-;conditionP;MU;27|)
                                        (SEQ
                                         (LETT |u| NIL
                                          |POLYCAT-;conditionP;MU;27|)
                                         (LETT #3# |l|
                                          |POLYCAT-;conditionP;MU;27|)
                                         G190
                                         (COND
                                           ((OR (ATOM #3#)
                                             (PROGN
                                               (LETT |u| (CAR #3#)
                                                |POLYCAT-;conditionP;MU;27|)
                                               NIL))
                                            (GO G191)))
                                         (SEQ
                                          (EXIT
                                           (PROGN
                                             (LETT #4#
                                              (SPADCALL |u|
                                               (QREFELT $ 78))
                                              |POLYCAT-;conditionP;MU;27|)
                                             (COND
                                               (#6#
                                                (LETT #5#
                                                 (SPADCALL #5# #4#
                                                  (QREFELT $ 140))
                                                 |POLYCAT-;conditionP;MU;27|))
                                               ('T
                                                (PROGN
                                                  (LETT #5# #4#
                                                   |POLYCAT-;conditionP;MU;27|)
                                                  (LETT #6# 'T
                                                   |POLYCAT-;conditionP;MU;27|)))))))
                                         (LETT #3# (CDR #3#)
                                          |POLYCAT-;conditionP;MU;27|)
                                         (GO G190) G191 (EXIT NIL))
                                        (COND
                                          (#6# #5#)
                                          ('T
                                           (|IdentityError|
                                            '|setUnion|))))
                                      |POLYCAT-;conditionP;MU;27|)
                                (LETT |redmons| NIL
                                      |POLYCAT-;conditionP;MU;27|)
                                (SEQ (LETT |m| NIL
                                      |POLYCAT-;conditionP;MU;27|)
                                     (LETT #7# |mons|
                                      |POLYCAT-;conditionP;MU;27|)
                                     G190
                                     (COND
                                       ((OR (ATOM #7#)
                                         (PROGN
                                           (LETT |m| (CAR #7#)
                                            |POLYCAT-;conditionP;MU;27|)
                                           NIL))
                                        (GO G191)))
                                     (SEQ
                                      (LETT |vars|
                                       (SPADCALL |m| (QREFELT $ 32))
                                       |POLYCAT-;conditionP;MU;27|)
                                      (LETT |degs|
                                       (SPADCALL |m| |vars|
                                        (QREFELT $ 141))
                                       |POLYCAT-;conditionP;MU;27|)
                                      (LETT |deg1|
                                       (PROGN
                                         (LETT #8# NIL
                                          |POLYCAT-;conditionP;MU;27|)
                                         (SEQ
                                          (LETT |d| NIL
                                           |POLYCAT-;conditionP;MU;27|)
                                          (LETT #9# |degs|
                                           |POLYCAT-;conditionP;MU;27|)
                                          G190
                                          (COND
                                            ((OR (ATOM #9#)
                                              (PROGN
                                                (LETT |d| (CAR #9#)
                                                 |POLYCAT-;conditionP;MU;27|)
                                                NIL))
                                             (GO G191)))
                                          (SEQ
                                           (EXIT
                                            (LETT #8#
                                             (CONS
                                              (SEQ
                                               (LETT |nd|
                                                (SPADCALL |d| |ch|
                                                 (QREFELT $ 143))
                                                |POLYCAT-;conditionP;MU;27|)
                                               (EXIT
                                                (COND
                                                  ((QEQCAR |nd| 1)
                                                   (PROGN
                                                     (LETT #10#
                                                      (CONS 1 "failed")
                                                      |POLYCAT-;conditionP;MU;27|)
                                                     (GO #10#)))
                                                  ('T
                                                   (PROG1
                                                    (LETT #11#
                                                     (QCDR |nd|)
                                                     |POLYCAT-;conditionP;MU;27|)
                                                     (|check-subtype|
                                                      (>= #11# 0)
                                                      '(|NonNegativeInteger|)
                                                      #11#))))))
                                              #8#)
                                             |POLYCAT-;conditionP;MU;27|)))
                                          (LETT #9# (CDR #9#)
                                           |POLYCAT-;conditionP;MU;27|)
                                          (GO G190) G191
                                          (EXIT (NREVERSE0 #8#))))
                                       |POLYCAT-;conditionP;MU;27|)
                                      (LETT |redmons|
                                       (CONS
                                        (SPADCALL (|spadConstant| $ 34)
                                         |vars| |deg1| (QREFELT $ 55))
                                        |redmons|)
                                       |POLYCAT-;conditionP;MU;27|)
                                      (EXIT
                                       (LETT |llR|
                                        (PROGN
                                          (LETT #12# NIL
                                           |POLYCAT-;conditionP;MU;27|)
                                          (SEQ
                                           (LETT |v| NIL
                                            |POLYCAT-;conditionP;MU;27|)
                                           (LETT #13# |llR|
                                            |POLYCAT-;conditionP;MU;27|)
                                           (LETT |u| NIL
                                            |POLYCAT-;conditionP;MU;27|)
                                           (LETT #14# |l|
                                            |POLYCAT-;conditionP;MU;27|)
                                           G190
                                           (COND
                                             ((OR (ATOM #14#)
                                               (PROGN
                                                 (LETT |u| (CAR #14#)
                                                  |POLYCAT-;conditionP;MU;27|)
                                                 NIL)
                                               (ATOM #13#)
                                               (PROGN
                                                 (LETT |v| (CAR #13#)
                                                  |POLYCAT-;conditionP;MU;27|)
                                                 NIL))
                                              (GO G191)))
                                           (SEQ
                                            (EXIT
                                             (LETT #12#
                                              (CONS
                                               (CONS
                                                (SPADCALL
                                                 (SPADCALL |u| |vars|
                                                  |degs|
                                                  (QREFELT $ 53))
                                                 (QREFELT $ 144))
                                                |v|)
                                               #12#)
                                              |POLYCAT-;conditionP;MU;27|)))
                                           (LETT #14#
                                            (PROG1 (CDR #14#)
                                              (LETT #13# (CDR #13#)
                                               |POLYCAT-;conditionP;MU;27|))
                                            |POLYCAT-;conditionP;MU;27|)
                                           (GO G190) G191
                                           (EXIT (NREVERSE0 #12#))))
                                        |POLYCAT-;conditionP;MU;27|)))
                                     (LETT #7# (CDR #7#)
                                      |POLYCAT-;conditionP;MU;27|)
                                     (GO G190) G191 (EXIT NIL))
                                (EXIT (LETT |monslist|
                                       (CONS |redmons| |monslist|)
                                       |POLYCAT-;conditionP;MU;27|)))
                           (LETT #2# (CDR #2#)
                                 |POLYCAT-;conditionP;MU;27|)
                           (GO G190) G191 (EXIT NIL))
                      (LETT |ans|
                            (SPADCALL
                                (SPADCALL
                                    (SPADCALL |llR| (QREFELT $ 90))
                                    (QREFELT $ 145))
                                (QREFELT $ 147))
                            |POLYCAT-;conditionP;MU;27|)
                      (EXIT (COND
                              ((QEQCAR |ans| 1) (CONS 1 "failed"))
                              ('T
                               (SEQ (LETT |i| 0
                                     |POLYCAT-;conditionP;MU;27|)
                                    (EXIT
                                     (CONS 0
                                      (PRIMVEC2ARR
                                       (PROGN
                                         (LETT #15#
                                          (GETREFV (SIZE |monslist|))
                                          |POLYCAT-;conditionP;MU;27|)
                                         (SEQ
                                          (LETT #16# 0
                                           |POLYCAT-;conditionP;MU;27|)
                                          (LETT |mons| NIL
                                           |POLYCAT-;conditionP;MU;27|)
                                          (LETT #17# |monslist|
                                           |POLYCAT-;conditionP;MU;27|)
                                          G190
                                          (COND
                                            ((OR (ATOM #17#)
                                              (PROGN
                                                (LETT |mons| (CAR #17#)
                                                 |POLYCAT-;conditionP;MU;27|)
                                                NIL))
                                             (GO G191)))
                                          (SEQ
                                           (EXIT
                                            (SETELT #15# #16#
                                             (PROGN
                                               (LETT #21# NIL
                                                |POLYCAT-;conditionP;MU;27|)
                                               (SEQ
                                                (LETT |m| NIL
                                                 |POLYCAT-;conditionP;MU;27|)
                                                (LETT #18# |mons|
                                                 |POLYCAT-;conditionP;MU;27|)
                                                G190
                                                (COND
                                                  ((OR (ATOM #18#)
                                                    (PROGN
                                                      (LETT |m|
                                                       (CAR #18#)
                                                       |POLYCAT-;conditionP;MU;27|)
                                                      NIL))
                                                   (GO G191)))
                                                (SEQ
                                                 (EXIT
                                                  (PROGN
                                                    (LETT #19#
                                                     (SPADCALL |m|
                                                      (SPADCALL
                                                       (SPADCALL
                                                        (QCDR |ans|)
                                                        (LETT |i|
                                                         (+ |i| 1)
                                                         |POLYCAT-;conditionP;MU;27|)
                                                        (QREFELT $ 148))
                                                       (QREFELT $ 41))
                                                      (QREFELT $ 149))
                                                     |POLYCAT-;conditionP;MU;27|)
                                                    (COND
                                                      (#21#
                                                       (LETT #20#
                                                        (SPADCALL #20#
                                                         #19#
                                                         (QREFELT $
                                                          150))
                                                        |POLYCAT-;conditionP;MU;27|))
                                                      ('T
                                                       (PROGN
                                                         (LETT #20#
                                                          #19#
                                                          |POLYCAT-;conditionP;MU;27|)
                                                         (LETT #21# 'T
                                                          |POLYCAT-;conditionP;MU;27|)))))))
                                                (LETT #18# (CDR #18#)
                                                 |POLYCAT-;conditionP;MU;27|)
                                                (GO G190) G191
                                                (EXIT NIL))
                                               (COND
                                                 (#21# #20#)
                                                 ('T
                                                  (|spadConstant| $ 21)))))))
                                          (LETT #17#
                                           (PROG1 (CDR #17#)
                                             (LETT #16# (QSADD1 #16#)
                                              |POLYCAT-;conditionP;MU;27|))
                                           |POLYCAT-;conditionP;MU;27|)
                                          (GO G190) G191 (EXIT NIL))
                                         #15#))))))))))
           #10# (EXIT #10#))))) 

(DEFUN |POLYCAT-;charthRoot;SU;28| (|p| $)
  (PROG (|vars| |ans| |ch|)
    (RETURN
      (SEQ (LETT |vars| (SPADCALL |p| (QREFELT $ 32))
                 |POLYCAT-;charthRoot;SU;28|)
           (EXIT (COND
                   ((NULL |vars|)
                    (SEQ (LETT |ans|
                               (SPADCALL (SPADCALL |p| (QREFELT $ 144))
                                   (QREFELT $ 152))
                               |POLYCAT-;charthRoot;SU;28|)
                         (EXIT (COND
                                 ((QEQCAR |ans| 1) (CONS 1 "failed"))
                                 ('T
                                  (CONS 0
                                        (SPADCALL (QCDR |ans|)
                                         (QREFELT $ 41))))))))
                   ('T
                    (SEQ (LETT |ch| (SPADCALL (QREFELT $ 139))
                               |POLYCAT-;charthRoot;SU;28|)
                         (EXIT (|POLYCAT-;charthRootlv| |p| |vars| |ch|
                                   $)))))))))) 

(DEFUN |POLYCAT-;charthRootlv| (|p| |vars| |ch| $)
  (PROG (|v| |dd| |cp| |d| #0=#:G1661 |ans| |ansx| #1=#:G1668)
    (RETURN
      (SEQ (EXIT (COND
                   ((NULL |vars|)
                    (SEQ (LETT |ans|
                               (SPADCALL (SPADCALL |p| (QREFELT $ 144))
                                   (QREFELT $ 152))
                               |POLYCAT-;charthRootlv|)
                         (EXIT (COND
                                 ((QEQCAR |ans| 1) (CONS 1 "failed"))
                                 ('T
                                  (CONS 0
                                        (SPADCALL (QCDR |ans|)
                                         (QREFELT $ 41))))))))
                   ('T
                    (SEQ (LETT |v| (|SPADfirst| |vars|)
                               |POLYCAT-;charthRootlv|)
                         (LETT |vars| (CDR |vars|)
                               |POLYCAT-;charthRootlv|)
                         (LETT |d| (SPADCALL |p| |v| (QREFELT $ 37))
                               |POLYCAT-;charthRootlv|)
                         (LETT |ans| (|spadConstant| $ 21)
                               |POLYCAT-;charthRootlv|)
                         (SEQ G190 (COND ((NULL (< 0 |d|)) (GO G191)))
                              (SEQ (LETT |dd|
                                    (SPADCALL |d| |ch| (QREFELT $ 143))
                                    |POLYCAT-;charthRootlv|)
                                   (EXIT
                                    (COND
                                      ((QEQCAR |dd| 1)
                                       (PROGN
                                         (LETT #1# (CONS 1 "failed")
                                          |POLYCAT-;charthRootlv|)
                                         (GO #1#)))
                                      ('T
                                       (SEQ
                                        (LETT |cp|
                                         (SPADCALL |p| |v| |d|
                                          (QREFELT $ 155))
                                         |POLYCAT-;charthRootlv|)
                                        (LETT |p|
                                         (SPADCALL |p|
                                          (SPADCALL |cp| |v| |d|
                                           (QREFELT $ 38))
                                          (QREFELT $ 156))
                                         |POLYCAT-;charthRootlv|)
                                        (LETT |ansx|
                                         (|POLYCAT-;charthRootlv| |cp|
                                          |vars| |ch| $)
                                         |POLYCAT-;charthRootlv|)
                                        (EXIT
                                         (COND
                                           ((QEQCAR |ansx| 1)
                                            (PROGN
                                              (LETT #1#
                                               (CONS 1 "failed")
                                               |POLYCAT-;charthRootlv|)
                                              (GO #1#)))
                                           ('T
                                            (SEQ
                                             (LETT |d|
                                              (SPADCALL |p| |v|
                                               (QREFELT $ 37))
                                              |POLYCAT-;charthRootlv|)
                                             (EXIT
                                              (LETT |ans|
                                               (SPADCALL |ans|
                                                (SPADCALL (QCDR |ansx|)
                                                 |v|
                                                 (PROG1
                                                  (LETT #0# (QCDR |dd|)
                                                   |POLYCAT-;charthRootlv|)
                                                   (|check-subtype|
                                                    (>= #0# 0)
                                                    '(|NonNegativeInteger|)
                                                    #0#))
                                                 (QREFELT $ 38))
                                                (QREFELT $ 150))
                                               |POLYCAT-;charthRootlv|)))))))))))
                              NIL (GO G190) G191 (EXIT NIL))
                         (LETT |ansx|
                               (|POLYCAT-;charthRootlv| |p| |vars| |ch|
                                   $)
                               |POLYCAT-;charthRootlv|)
                         (EXIT (COND
                                 ((QEQCAR |ansx| 1)
                                  (PROGN
                                    (LETT #1# (CONS 1 "failed")
                                     |POLYCAT-;charthRootlv|)
                                    (GO #1#)))
                                 ('T
                                  (PROGN
                                    (LETT #1#
                                     (CONS 0
                                      (SPADCALL |ans| (QCDR |ansx|)
                                       (QREFELT $ 150)))
                                     |POLYCAT-;charthRootlv|)
                                    (GO #1#)))))))))
           #1# (EXIT #1#))))) 

(DEFUN |POLYCAT-;monicDivide;2SVarSetR;30| (|p1| |p2| |mvar| $)
  (PROG (|result|)
    (RETURN
      (SEQ (LETT |result|
                 (SPADCALL (SPADCALL |p1| |mvar| (QREFELT $ 48))
                     (SPADCALL |p2| |mvar| (QREFELT $ 48))
                     (QREFELT $ 158))
                 |POLYCAT-;monicDivide;2SVarSetR;30|)
           (EXIT (CONS (SPADCALL (QCAR |result|) |mvar|
                           (QREFELT $ 133))
                       (SPADCALL (QCDR |result|) |mvar|
                           (QREFELT $ 133)))))))) 

(DEFUN |POLYCAT-;squareFree;SF;31| (|p| $)
  (SPADCALL |p| (QREFELT $ 161))) 

(DEFUN |POLYCAT-;squareFree;SF;32| (|p| $)
  (SPADCALL |p| (QREFELT $ 164))) 

(DEFUN |POLYCAT-;squareFree;SF;33| (|p| $)
  (SPADCALL |p| (QREFELT $ 164))) 

(DEFUN |POLYCAT-;squareFreePart;2S;34| (|p| $)
  (PROG (|s| |f| #0=#:G1684 #1=#:G1682 #2=#:G1680 #3=#:G1681)
    (RETURN
      (SEQ (SPADCALL
               (SPADCALL
                   (LETT |s| (SPADCALL |p| (QREFELT $ 165))
                         |POLYCAT-;squareFreePart;2S;34|)
                   (QREFELT $ 166))
               (PROGN
                 (LETT #3# NIL |POLYCAT-;squareFreePart;2S;34|)
                 (SEQ (LETT |f| NIL |POLYCAT-;squareFreePart;2S;34|)
                      (LETT #0# (SPADCALL |s| (QREFELT $ 169))
                            |POLYCAT-;squareFreePart;2S;34|)
                      G190
                      (COND
                        ((OR (ATOM #0#)
                             (PROGN
                               (LETT |f| (CAR #0#)
                                     |POLYCAT-;squareFreePart;2S;34|)
                               NIL))
                         (GO G191)))
                      (SEQ (EXIT (PROGN
                                   (LETT #1# (QCAR |f|)
                                    |POLYCAT-;squareFreePart;2S;34|)
                                   (COND
                                     (#3#
                                      (LETT #2#
                                       (SPADCALL #2# #1#
                                        (QREFELT $ 149))
                                       |POLYCAT-;squareFreePart;2S;34|))
                                     ('T
                                      (PROGN
                                        (LETT #2# #1#
                                         |POLYCAT-;squareFreePart;2S;34|)
                                        (LETT #3# 'T
                                         |POLYCAT-;squareFreePart;2S;34|)))))))
                      (LETT #0# (CDR #0#)
                            |POLYCAT-;squareFreePart;2S;34|)
                      (GO G190) G191 (EXIT NIL))
                 (COND (#3# #2#) ('T (|spadConstant| $ 34))))
               (QREFELT $ 149)))))) 

(DEFUN |POLYCAT-;content;SVarSetS;35| (|p| |v| $)
  (SPADCALL (SPADCALL |p| |v| (QREFELT $ 48)) (QREFELT $ 171))) 

(DEFUN |POLYCAT-;primitivePart;2S;36| (|p| $)
  (PROG (#0=#:G1687)
    (RETURN
      (QVELT (SPADCALL
                 (PROG2 (LETT #0#
                              (SPADCALL |p|
                                  (SPADCALL |p| (QREFELT $ 173))
                                  (QREFELT $ 174))
                              |POLYCAT-;primitivePart;2S;36|)
                        (QCDR #0#)
                   (|check-union| (QEQCAR #0# 0) (QREFELT $ 6) #0#))
                 (QREFELT $ 176))
             1)))) 

(DEFUN |POLYCAT-;primitivePart;SVarSetS;37| (|p| |v| $)
  (PROG (#0=#:G1693)
    (RETURN
      (QVELT (SPADCALL
                 (PROG2 (LETT #0#
                              (SPADCALL |p|
                                  (SPADCALL |p| |v| (QREFELT $ 178))
                                  (QREFELT $ 179))
                              |POLYCAT-;primitivePart;SVarSetS;37|)
                        (QCDR #0#)
                   (|check-union| (QEQCAR #0# 0) (QREFELT $ 6) #0#))
                 (QREFELT $ 176))
             1)))) 

(DEFUN |POLYCAT-;<;2SB;38| (|p| |q| $)
  (PROG (|dp| |dq|)
    (RETURN
      (SEQ (LETT |dp| (SPADCALL |p| (QREFELT $ 60))
                 |POLYCAT-;<;2SB;38|)
           (LETT |dq| (SPADCALL |q| (QREFELT $ 60))
                 |POLYCAT-;<;2SB;38|)
           (EXIT (COND
                   ((SPADCALL |dp| |dq| (QREFELT $ 181))
                    (SPADCALL (|spadConstant| $ 22)
                        (SPADCALL |q| (QREFELT $ 39)) (QREFELT $ 182)))
                   ((SPADCALL |dq| |dp| (QREFELT $ 181))
                    (SPADCALL (SPADCALL |p| (QREFELT $ 39))
                        (|spadConstant| $ 22) (QREFELT $ 182)))
                   ('T
                    (SPADCALL
                        (SPADCALL (SPADCALL |p| |q| (QREFELT $ 156))
                            (QREFELT $ 39))
                        (|spadConstant| $ 22) (QREFELT $ 182))))))))) 

(DEFUN |POLYCAT-;patternMatch;SP2Pmr;39| (|p| |pat| |l| $)
  (SPADCALL |p| |pat| |l| (QREFELT $ 187))) 

(DEFUN |POLYCAT-;patternMatch;SP2Pmr;40| (|p| |pat| |l| $)
  (SPADCALL |p| |pat| |l| (QREFELT $ 193))) 

(DEFUN |POLYCAT-;convert;SP;41| (|x| $)
  (SPADCALL (ELT $ 196) (ELT $ 197) |x| (QREFELT $ 201))) 

(DEFUN |POLYCAT-;convert;SP;42| (|x| $)
  (SPADCALL (ELT $ 203) (ELT $ 204) |x| (QREFELT $ 208))) 

(DEFUN |POLYCAT-;convert;SIf;43| (|p| $)
  (SPADCALL (ELT $ 211) (ELT $ 212) |p| (QREFELT $ 216))) 

(DEFUN |PolynomialCategory&| (|#1| |#2| |#3| |#4|)
  (PROG (|dv$1| |dv$2| |dv$3| |dv$4| |dv$| $ |pv$|)
    (RETURN
      (PROGN
        (LETT |dv$1| (|devaluate| |#1|) . #0=(|PolynomialCategory&|))
        (LETT |dv$2| (|devaluate| |#2|) . #0#)
        (LETT |dv$3| (|devaluate| |#3|) . #0#)
        (LETT |dv$4| (|devaluate| |#4|) . #0#)
        (LETT |dv$|
              (LIST '|PolynomialCategory&| |dv$1| |dv$2| |dv$3| |dv$4|) . #0#)
        (LETT $ (GETREFV 226) . #0#)
        (QSETREFV $ 0 |dv$|)
        (QSETREFV $ 3
            (LETT |pv$|
                  (|buildPredVector| 0 0
                      (LIST (|HasCategory| |#2|
                                '(|PolynomialFactorizationExplicit|))
                            (|HasAttribute| |#2|
                                '|canonicalUnitNormal|)
                            (|HasCategory| |#2| '(|GcdDomain|))
                            (|HasCategory| |#2| '(|CommutativeRing|))
                            (|HasCategory| |#4|
                                '(|PatternMatchable| (|Float|)))
                            (|HasCategory| |#2|
                                '(|PatternMatchable| (|Float|)))
                            (|HasCategory| |#4|
                                '(|PatternMatchable| (|Integer|)))
                            (|HasCategory| |#2|
                                '(|PatternMatchable| (|Integer|)))
                            (|HasCategory| |#4|
                                '(|ConvertibleTo|
                                     (|Pattern| (|Float|))))
                            (|HasCategory| |#2|
                                '(|ConvertibleTo|
                                     (|Pattern| (|Float|))))
                            (|HasCategory| |#4|
                                '(|ConvertibleTo|
                                     (|Pattern| (|Integer|))))
                            (|HasCategory| |#2|
                                '(|ConvertibleTo|
                                     (|Pattern| (|Integer|))))
                            (|HasCategory| |#4|
                                '(|ConvertibleTo| (|InputForm|)))
                            (|HasCategory| |#2|
                                '(|ConvertibleTo| (|InputForm|)))
                            (|HasCategory| |#2| '(|OrderedSet|)))) . #0#))
        (|stuffDomainSlots| $)
        (QSETREFV $ 6 |#1|)
        (QSETREFV $ 7 |#2|)
        (QSETREFV $ 8 |#3|)
        (QSETREFV $ 9 |#4|)
        (COND
          ((|testBitVector| |pv$| 4)
           (PROGN
             (QSETREFV $ 75
                 (CONS (|dispatchFunction|
                           |POLYCAT-;resultant;2SVarSetS;15|)
                       $))
             (QSETREFV $ 77
                 (CONS (|dispatchFunction|
                           |POLYCAT-;discriminant;SVarSetS;16|)
                       $)))))
        (COND
          ((|HasCategory| |#2| '(|IntegralDomain|))
           (PROGN
             (QSETREFV $ 96
                 (CONS (|dispatchFunction|
                           |POLYCAT-;reducedSystem;MM;20|)
                       $))
             (QSETREFV $ 103
                 (CONS (|dispatchFunction|
                           |POLYCAT-;reducedSystem;MVR;21|)
                       $)))))
        (COND
          ((|testBitVector| |pv$| 1)
           (PROGN
             (QSETREFV $ 106
                 (CONS (|dispatchFunction|
                           |POLYCAT-;gcdPolynomial;3Sup;22|)
                       $))
             (QSETREFV $ 113
                 (CONS (|dispatchFunction|
                           |POLYCAT-;solveLinearPolynomialEquation;LSupU;23|)
                       $))
             (QSETREFV $ 117
                 (CONS (|dispatchFunction|
                           |POLYCAT-;factorPolynomial;SupF;24|)
                       $))
             (QSETREFV $ 119
                 (CONS (|dispatchFunction|
                           |POLYCAT-;factorSquareFreePolynomial;SupF;25|)
                       $))
             (QSETREFV $ 137
                 (CONS (|dispatchFunction| |POLYCAT-;factor;SF;26|) $))
             (COND
               ((|HasCategory| |#2| '(|CharacteristicNonZero|))
                (PROGN
                  (QSETREFV $ 151
                      (CONS (|dispatchFunction|
                                |POLYCAT-;conditionP;MU;27|)
                            $))))))))
        (COND
          ((|HasCategory| |#2| '(|CharacteristicNonZero|))
           (PROGN
             (QSETREFV $ 153
                 (CONS (|dispatchFunction| |POLYCAT-;charthRoot;SU;28|)
                       $)))))
        (COND
          ((|testBitVector| |pv$| 3)
           (PROGN
             (COND
               ((|HasCategory| |#2| '(|EuclideanDomain|))
                (COND
                  ((|HasCategory| |#2| '(|CharacteristicZero|))
                   (QSETREFV $ 162
                       (CONS (|dispatchFunction|
                                 |POLYCAT-;squareFree;SF;31|)
                             $)))
                  ('T
                   (QSETREFV $ 162
                       (CONS (|dispatchFunction|
                                 |POLYCAT-;squareFree;SF;32|)
                             $)))))
               ('T
                (QSETREFV $ 162
                    (CONS (|dispatchFunction|
                              |POLYCAT-;squareFree;SF;33|)
                          $))))
             (QSETREFV $ 170
                 (CONS (|dispatchFunction|
                           |POLYCAT-;squareFreePart;2S;34|)
                       $))
             (QSETREFV $ 172
                 (CONS (|dispatchFunction|
                           |POLYCAT-;content;SVarSetS;35|)
                       $))
             (QSETREFV $ 177
                 (CONS (|dispatchFunction|
                           |POLYCAT-;primitivePart;2S;36|)
                       $))
             (QSETREFV $ 180
                 (CONS (|dispatchFunction|
                           |POLYCAT-;primitivePart;SVarSetS;37|)
                       $)))))
        (COND
          ((|testBitVector| |pv$| 15)
           (PROGN
             (QSETREFV $ 183
                 (CONS (|dispatchFunction| |POLYCAT-;<;2SB;38|) $))
             (COND
               ((|testBitVector| |pv$| 8)
                (COND
                  ((|testBitVector| |pv$| 7)
                   (QSETREFV $ 189
                       (CONS (|dispatchFunction|
                                 |POLYCAT-;patternMatch;SP2Pmr;39|)
                             $))))))
             (COND
               ((|testBitVector| |pv$| 6)
                (COND
                  ((|testBitVector| |pv$| 5)
                   (QSETREFV $ 195
                       (CONS (|dispatchFunction|
                                 |POLYCAT-;patternMatch;SP2Pmr;40|)
                             $)))))))))
        (COND
          ((|testBitVector| |pv$| 12)
           (COND
             ((|testBitVector| |pv$| 11)
              (QSETREFV $ 202
                  (CONS (|dispatchFunction| |POLYCAT-;convert;SP;41|)
                        $))))))
        (COND
          ((|testBitVector| |pv$| 10)
           (COND
             ((|testBitVector| |pv$| 9)
              (QSETREFV $ 209
                  (CONS (|dispatchFunction| |POLYCAT-;convert;SP;42|)
                        $))))))
        (COND
          ((|testBitVector| |pv$| 14)
           (COND
             ((|testBitVector| |pv$| 13)
              (QSETREFV $ 217
                  (CONS (|dispatchFunction| |POLYCAT-;convert;SIf;43|)
                        $))))))
        $)))) 

(MAKEPROP '|PolynomialCategory&| '|infovec|
    (LIST '#(NIL NIL NIL NIL NIL NIL (|local| |#1|) (|local| |#2|)
             (|local| |#3|) (|local| |#4|) (|Equation| 6) (0 . |lhs|)
             (|Union| 9 '"failed") (5 . |retractIfCan|)
             (10 . |retract|) (15 . |rhs|) (|List| 9) (|List| $)
             (20 . |eval|) (|List| 221) |POLYCAT-;eval;SLS;1|
             (27 . |Zero|) (31 . |Zero|) (|Boolean|) (35 . =)
             (41 . |not|) (46 . |leadingMonomial|) (51 . |reductum|)
             |POLYCAT-;monomials;SL;2| (56 . |monomials|)
             (|Union| 17 '"failed") |POLYCAT-;isPlus;SU;3|
             (61 . |variables|) (66 . |monomial?|) (71 . |One|)
             (75 . |One|) (|NonNegativeInteger|) (79 . |degree|)
             (85 . |monomial|) (92 . |leadingCoefficient|) (97 . =)
             (103 . |coerce|) |POLYCAT-;isTimes;SU;4|
             (108 . |mainVariable|)
             (|Record| (|:| |var| 9) (|:| |exponent| 36))
             (|Union| 44 '"failed") |POLYCAT-;isExpt;SU;5|
             (|SparseUnivariatePolynomial| $) (113 . |univariate|)
             (|SparseUnivariatePolynomial| 6) (119 . |coefficient|)
             |POLYCAT-;coefficient;SVarSetNniS;6| (|List| 36)
             (125 . |coefficient|) |POLYCAT-;coefficient;SLLS;7|
             (132 . |monomial|) |POLYCAT-;monomial;SLLS;8|
             (139 . |coerce|) |POLYCAT-;retract;SVarSet;9|
             |POLYCAT-;retractIfCan;SU;10| (144 . |degree|)
             (149 . |monomial|) |POLYCAT-;primitiveMonomials;SL;12|
             (155 . |ground?|) (160 . |Zero|) (164 . =)
             (170 . |degree|) (175 . |leadingCoefficient|)
             (180 . |totalDegree|) (185 . |reductum|)
             |POLYCAT-;totalDegree;SNni;13| (190 . |member?|)
             (196 . |totalDegree|) |POLYCAT-;totalDegree;SLNni;14|
             (202 . |resultant|) (208 . |resultant|)
             (215 . |discriminant|) (220 . |discriminant|)
             (226 . |primitiveMonomials|) (|List| 6) (231 . |concat|)
             (236 . |removeDuplicates!|) (|Vector| 7) (241 . |new|)
             (|Integer|) (247 . |minIndex|) (252 . |coefficient|)
             (258 . |qsetelt!|) (|List| 220) (|Matrix| 7)
             (265 . |matrix|) (|List| 79) (|Matrix| 6)
             (270 . |listOfLists|) (275 . |vertConcat|) (|Matrix| $)
             (281 . |reducedSystem|) (|Vector| 6) (286 . |entries|)
             (291 . |concat|) (297 . |concat|)
             (|Record| (|:| |mat| 89) (|:| |vec| 82)) (|Vector| $)
             (303 . |reducedSystem|)
             (|GeneralPolynomialGcdPackage| 8 9 7 6)
             (309 . |gcdPolynomial|) (315 . |gcdPolynomial|)
             (|Union| 108 '"failed") (|List| 49)
             (|PolynomialFactorizationByRecursion| 7 8 9 6)
             (321 . |solveLinearPolynomialEquationByRecursion|)
             (|Union| 112 '"failed") (|List| 47)
             (327 . |solveLinearPolynomialEquation|) (|Factored| 49)
             (333 . |factorByRecursion|) (|Factored| 47)
             (338 . |factorPolynomial|)
             (343 . |factorSquareFreeByRecursion|)
             (348 . |factorSquareFreePolynomial|) (|Factored| $)
             (353 . |factor|) (|Factored| 7) (358 . |unit|)
             (|Union| '"nil" '"sqfr" '"irred" '"prime")
             (|Record| (|:| |flg| 124) (|:| |fctr| 7) (|:| |xpnt| 84))
             (|List| 125) (363 . |factorList|)
             (|Record| (|:| |flg| 124) (|:| |fctr| 6) (|:| |xpnt| 84))
             (|List| 128) (|Factored| 6) (368 . |makeFR|)
             (374 . |unit|) (379 . |multivariate|)
             (|Record| (|:| |flg| 124) (|:| |fctr| 49) (|:| |xpnt| 84))
             (|List| 134) (385 . |factorList|) (390 . |factor|)
             (395 . |transpose|) (400 . |characteristic|)
             (404 . |setUnion|) (410 . |degree|) (|Union| $ '"failed")
             (416 . |exquo|) (422 . |ground|) (427 . |transpose|)
             (|Union| 102 '"failed") (432 . |conditionP|) (437 . |elt|)
             (443 . *) (449 . +) (455 . |conditionP|)
             (460 . |charthRoot|) (465 . |charthRoot|) (470 . |Zero|)
             (474 . |coefficient|) (481 . -)
             (|Record| (|:| |quotient| $) (|:| |remainder| $))
             (487 . |monicDivide|) |POLYCAT-;monicDivide;2SVarSetR;30|
             (|MultivariateSquareFree| 8 9 7 6) (493 . |squareFree|)
             (498 . |squareFree|) (|PolynomialSquareFree| 9 8 7 6)
             (503 . |squareFree|) (508 . |squareFree|) (513 . |unit|)
             (|Record| (|:| |factor| 6) (|:| |exponent| 84))
             (|List| 167) (518 . |factors|) (523 . |squareFreePart|)
             (528 . |content|) (533 . |content|) (539 . |content|)
             (544 . |exquo|)
             (|Record| (|:| |unit| $) (|:| |canonical| $)
                 (|:| |associate| $))
             (550 . |unitNormal|) (555 . |primitivePart|)
             (560 . |content|) (566 . |exquo|) (572 . |primitivePart|)
             (578 . <) (584 . <) (590 . <) (|PatternMatchResult| 84 6)
             (|Pattern| 84)
             (|PatternMatchPolynomialCategory| 84 8 9 7 6)
             (596 . |patternMatch|) (|PatternMatchResult| 84 $)
             (603 . |patternMatch|) (|PatternMatchResult| (|Float|) 6)
             (|Pattern| (|Float|))
             (|PatternMatchPolynomialCategory| (|Float|) 8 9 7 6)
             (610 . |patternMatch|) (|PatternMatchResult| (|Float|) $)
             (617 . |patternMatch|) (624 . |convert|) (629 . |convert|)
             (|Mapping| 185 9) (|Mapping| 185 7)
             (|PolynomialCategoryLifting| 8 9 7 6 185) (634 . |map|)
             (641 . |convert|) (646 . |convert|) (651 . |convert|)
             (|Mapping| 191 9) (|Mapping| 191 7)
             (|PolynomialCategoryLifting| 8 9 7 6 191) (656 . |map|)
             (663 . |convert|) (|InputForm|) (668 . |convert|)
             (673 . |convert|) (|Mapping| 210 9) (|Mapping| 210 7)
             (|PolynomialCategoryLifting| 8 9 7 6 210) (678 . |map|)
             (685 . |convert|)
             (|Record| (|:| |mat| 219) (|:| |vec| (|Vector| 84)))
             (|Matrix| 84) (|List| 7) (|Equation| $)
             (|Union| 84 '"failed") (|Union| 224 '"failed")
             (|Fraction| 84) (|Union| 7 '"failed"))
          '#(|totalDegree| 690 |squareFreePart| 701 |squareFree| 706
             |solveLinearPolynomialEquation| 711 |retractIfCan| 717
             |retract| 722 |resultant| 727 |reducedSystem| 734
             |primitivePart| 745 |primitiveMonomials| 756
             |patternMatch| 761 |monomials| 775 |monomial| 780
             |monicDivide| 787 |isTimes| 794 |isPlus| 799 |isExpt| 804
             |gcdPolynomial| 809 |factorSquareFreePolynomial| 815
             |factorPolynomial| 820 |factor| 825 |eval| 830
             |discriminant| 836 |convert| 842 |content| 857
             |conditionP| 863 |coefficient| 868 |charthRoot| 882 < 887)
          'NIL
          (CONS (|makeByteWordVec2| 1 'NIL)
                (CONS '#()
                      (CONS '#()
                            (|makeByteWordVec2| 217
                                '(1 10 6 0 11 1 6 12 0 13 1 6 9 0 14 1
                                  10 6 0 15 3 6 0 0 16 17 18 0 6 0 21 0
                                  7 0 22 2 6 23 0 0 24 1 23 0 0 25 1 6
                                  0 0 26 1 6 0 0 27 1 6 17 0 29 1 6 16
                                  0 32 1 6 23 0 33 0 6 0 34 0 7 0 35 2
                                  6 36 0 9 37 3 6 0 0 9 36 38 1 6 7 0
                                  39 2 7 23 0 0 40 1 6 0 7 41 1 6 12 0
                                  43 2 6 47 0 9 48 2 49 6 0 36 50 3 6 0
                                  0 16 52 53 3 6 0 0 16 52 55 1 6 0 9
                                  57 1 6 8 0 60 2 6 0 7 8 61 1 6 23 0
                                  63 0 49 0 64 2 49 23 0 0 65 1 49 36 0
                                  66 1 49 6 0 67 1 6 36 0 68 1 49 0 0
                                  69 2 16 23 9 0 71 2 6 36 0 16 72 2 49
                                  6 0 0 74 3 0 0 0 0 9 75 1 49 6 0 76 2
                                  0 0 0 9 77 1 6 17 0 78 1 79 0 17 80 1
                                  79 0 0 81 2 82 0 36 7 83 1 82 84 0 85
                                  2 6 7 0 8 86 3 82 7 0 84 7 87 1 89 0
                                  88 90 1 92 91 0 93 2 89 0 0 0 94 1 0
                                  89 95 96 1 97 79 0 98 2 79 0 0 0 99 2
                                  82 0 0 0 100 2 0 101 95 102 103 2 104
                                  49 49 49 105 2 0 47 47 47 106 2 109
                                  107 108 49 110 2 0 111 112 47 113 1
                                  109 114 49 115 1 0 116 47 117 1 109
                                  114 49 118 1 0 116 47 119 1 7 120 0
                                  121 1 122 7 0 123 1 122 126 0 127 2
                                  130 0 6 129 131 1 114 49 0 132 2 6 0
                                  47 9 133 1 114 135 0 136 1 0 120 0
                                  137 1 92 0 0 138 0 6 36 139 2 79 0 0
                                  0 140 2 6 52 0 16 141 2 84 142 0 0
                                  143 1 6 7 0 144 1 89 0 0 145 1 7 146
                                  95 147 2 82 7 0 84 148 2 6 0 0 0 149
                                  2 6 0 0 0 150 1 0 146 95 151 1 7 142
                                  0 152 1 0 142 0 153 0 8 0 154 3 6 0 0
                                  9 36 155 2 6 0 0 0 156 2 49 157 0 0
                                  158 1 160 130 6 161 1 0 120 0 162 1
                                  163 130 6 164 1 6 120 0 165 1 130 6 0
                                  166 1 130 168 0 169 1 0 0 0 170 1 49
                                  6 0 171 2 0 0 0 9 172 1 6 7 0 173 2 6
                                  142 0 7 174 1 6 175 0 176 1 0 0 0 177
                                  2 6 0 0 9 178 2 6 142 0 0 179 2 0 0 0
                                  9 180 2 8 23 0 0 181 2 7 23 0 0 182 2
                                  0 23 0 0 183 3 186 184 6 185 184 187
                                  3 0 188 0 185 188 189 3 192 190 6 191
                                  190 193 3 0 194 0 191 194 195 1 9 185
                                  0 196 1 7 185 0 197 3 200 185 198 199
                                  6 201 1 0 185 0 202 1 9 191 0 203 1 7
                                  191 0 204 3 207 191 205 206 6 208 1 0
                                  191 0 209 1 9 210 0 211 1 7 210 0 212
                                  3 215 210 213 214 6 216 1 0 210 0 217
                                  2 0 36 0 16 73 1 0 36 0 70 1 0 0 0
                                  170 1 0 120 0 162 2 0 111 112 47 113
                                  1 0 12 0 59 1 0 9 0 58 3 0 0 0 0 9 75
                                  1 0 89 95 96 2 0 101 95 102 103 2 0 0
                                  0 9 180 1 0 0 0 177 1 0 17 0 62 3 0
                                  188 0 185 188 189 3 0 194 0 191 194
                                  195 1 0 17 0 28 3 0 0 0 16 52 56 3 0
                                  157 0 0 9 159 1 0 30 0 42 1 0 30 0 31
                                  1 0 45 0 46 2 0 47 47 47 106 1 0 116
                                  47 119 1 0 116 47 117 1 0 120 0 137 2
                                  0 0 0 19 20 2 0 0 0 9 77 1 0 210 0
                                  217 1 0 185 0 202 1 0 191 0 209 2 0 0
                                  0 9 172 1 0 146 95 151 3 0 0 0 16 52
                                  54 3 0 0 0 9 36 51 1 0 142 0 153 2 0
                                  23 0 0 183)))))
          '|lookupComplete|)) 
@
\section{package POLYLIFT PolynomialCategoryLifting}
<<package POLYLIFT PolynomialCategoryLifting>>=
)abbrev package POLYLIFT PolynomialCategoryLifting
++ Author: Manuel Bronstein
++ Date Created:
++ Date Last Updated:
++ Basic Functions:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ This package provides a very general map function, which
++ given a set S and polynomials over R with maps from the
++ variables into S and the coefficients into S, maps polynomials
++ into S. S is assumed to support \spad{+}, \spad{*} and \spad{**}.

PolynomialCategoryLifting(E,Vars,R,P,S): Exports == Implementation where
  E   : OrderedAbelianMonoidSup
  Vars: OrderedSet
  R   : Ring
  P   : PolynomialCategory(R, E, Vars)
  S   : SetCategory with
           "+" : (%, %) -> %
           "*" : (%, %) -> %
           "**": (%, NonNegativeInteger) -> %

  Exports ==> with
    map: (Vars -> S, R -> S, P) -> S
      ++ map(varmap, coefmap, p) takes a
      ++ varmap, a mapping from the variables of polynomial p into S,
      ++ coefmap, a mapping from coefficients of p into S, and p, and
      ++ produces a member of S using the corresponding arithmetic.
      ++ in S

  Implementation ==> add
    map(fv, fc, p) ==
      (x1 := mainVariable p) case "failed" => fc leadingCoefficient p
      up := univariate(p, x1::Vars)
      t  := fv(x1::Vars)
      ans:= fc 0
      while not ground? up repeat
        ans := ans + map(fv,fc, leadingCoefficient up) * t ** (degree up)
        up  := reductum up
      ans + map(fv, fc, leadingCoefficient up)

@
\section{category UPOLYC UnivariatePolynomialCategory}
<<category UPOLYC UnivariatePolynomialCategory>>=
)abbrev category UPOLYC UnivariatePolynomialCategory
++ Author:
++ Date Created:
++ Date Last Updated:
++ Basic Functions: Ring, monomial, coefficient, reductum, differentiate,
++ elt, map, resultant, discriminant
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ The category of univariate polynomials over a ring R.
++ No particular model is assumed - implementations can be either
++ sparse or dense.

UnivariatePolynomialCategory(R:Ring): Category ==
 Join(PolynomialCategory(R, NonNegativeInteger, SingletonAsOrderedSet),
      Eltable(R, R), Eltable(%, %), DifferentialRing,
      DifferentialExtension R) with
    vectorise        : (%,NonNegativeInteger) -> Vector R
      ++ vectorise(p, n) returns \spad{[a0,...,a(n-1)]} where
      ++ \spad{p = a0 + a1*x + ... + a(n-1)*x**(n-1)} + higher order terms.
      ++ The degree of polynomial p can be different from \spad{n-1}.
    makeSUP: % -> SparseUnivariatePolynomial R
      ++ makeSUP(p) converts the polynomial p to be of type
      ++ SparseUnivariatePolynomial over the same coefficients.
    unmakeSUP: SparseUnivariatePolynomial R -> %
      ++ unmakeSUP(sup) converts sup of type \spadtype{SparseUnivariatePolynomial(R)}
      ++ to be a member of the given type.
      ++ Note: converse of makeSUP.
    multiplyExponents: (%,NonNegativeInteger) -> %
      ++ multiplyExponents(p,n) returns a new polynomial resulting from
      ++ multiplying all exponents of the polynomial p by the non negative
      ++ integer n.
    divideExponents: (%,NonNegativeInteger) -> Union(%,"failed")
      ++ divideExponents(p,n) returns a new polynomial resulting from
      ++ dividing all exponents of the polynomial p by the non negative
      ++ integer n, or "failed" if some exponent is not exactly divisible
      ++ by n.
    monicDivide: (%,%) -> Record(quotient:%,remainder:%)
      ++ monicDivide(p,q) divide the polynomial p by the monic polynomial q,
      ++ returning the pair \spad{[quotient, remainder]}.
      ++ Error: if q isn't monic.
-- These three are for Karatsuba
    karatsubaDivide: (%,NonNegativeInteger) -> Record(quotient:%,remainder:%)
      ++ \spad{karatsubaDivide(p,n)} returns the same as \spad{monicDivide(p,monomial(1,n))}
    shiftRight: (%,NonNegativeInteger) -> %
      ++ \spad{shiftRight(p,n)} returns \spad{monicDivide(p,monomial(1,n)).quotient}
    shiftLeft: (%,NonNegativeInteger) -> %
      ++ \spad{shiftLeft(p,n)} returns \spad{p * monomial(1,n)}
    pseudoRemainder: (%,%) -> %
       ++ pseudoRemainder(p,q) = r, for polynomials p and q, returns the remainder when
       ++ \spad{p' := p*lc(q)**(deg p - deg q + 1)}
       ++ is pseudo right-divided by q, i.e. \spad{p' = s q + r}.
    differentiate: (%, R -> R, %) -> %
       ++ differentiate(p, d, x') extends the R-derivation d to an
       ++ extension D in \spad{R[x]} where Dx is given by x', and returns \spad{Dp}.
    if R has StepThrough then StepThrough
    if R has CommutativeRing then
      discriminant: % -> R
        ++ discriminant(p) returns the discriminant of the polynomial p.
      resultant: (%,%) -> R
        ++ resultant(p,q) returns the resultant of the polynomials p and q.
    if R has IntegralDomain then
        Eltable(Fraction %, Fraction %)
        elt  : (Fraction %, Fraction %) -> Fraction %
             ++ elt(a,b) evaluates the fraction of univariate polynomials \spad{a}
             ++ with the distinguished variable replaced by b.
        order: (%, %) -> NonNegativeInteger
             ++ order(p, q) returns the largest n such that \spad{q**n} divides polynomial p
             ++ i.e. the order of \spad{p(x)} at \spad{q(x)=0}.
        subResultantGcd: (%,%) -> %
           ++ subResultantGcd(p,q) computes the gcd of the polynomials p and q
           ++ using the SubResultant GCD algorithm.
        composite: (%, %) -> Union(%, "failed")
           ++ composite(p, q) returns h if \spad{p = h(q)}, and "failed" no such h exists.
        composite: (Fraction %, %) -> Union(Fraction %, "failed")
           ++ composite(f, q) returns h if f = h(q), and "failed" is no such h exists.
        pseudoQuotient: (%,%) -> %
           ++ pseudoQuotient(p,q) returns r, the quotient when
           ++ \spad{p' := p*lc(q)**(deg p - deg q + 1)}
           ++ is pseudo right-divided by q, i.e. \spad{p' = s q + r}.
        pseudoDivide: (%, %) -> Record(coef:R, quotient: %, remainder:%)
           ++ pseudoDivide(p,q) returns \spad{[c, q, r]}, when
           ++ \spad{p' := p*lc(q)**(deg p - deg q + 1) = c * p}
           ++ is pseudo right-divided by q, i.e. \spad{p' = s q + r}.
    if R has GcdDomain then
        separate: (%, %) -> Record(primePart:%, commonPart: %)
           ++ separate(p, q) returns \spad{[a, b]} such that polynomial \spad{p = a b} and
           ++ \spad{a} is relatively prime to q.
    if R has Field then
        EuclideanDomain
        additiveValuation
          ++ euclideanSize(a*b) = euclideanSize(a) + euclideanSize(b)
        elt      : (Fraction %, R) -> R
            ++ elt(a,r) evaluates the fraction of univariate polynomials \spad{a}
            ++ with the distinguished variable replaced by the constant r.
    if R has Algebra Fraction Integer then
      integrate: % -> %
        ++ integrate(p) integrates the univariate polynomial p with respect
        ++ to its distinguished variable.
  add
    pp,qq: SparseUnivariatePolynomial %
    variables(p) ==
      zero? p or zero?(degree p) => []
      [create()]
    degree(p:%,v:SingletonAsOrderedSet) == degree p
    totalDegree(p:%,lv:List SingletonAsOrderedSet) ==
       empty? lv => 0
       totalDegree p
    degree(p:%,lv:List SingletonAsOrderedSet) ==
       empty? lv => []
       [degree p]
    eval(p:%,lv: List SingletonAsOrderedSet,lq: List %):% ==
      empty? lv => p
      not empty? rest lv => error "can only eval a univariate polynomial once"
      eval(p,first lv,first lq)$%
    eval(p:%,v:SingletonAsOrderedSet,q:%):% == p(q)
    eval(p:%,lv: List SingletonAsOrderedSet,lr: List R):% ==
      empty? lv => p
      not empty? rest lv => error "can only eval a univariate polynomial once"
      eval(p,first lv,first lr)$%
    eval(p:%,v:SingletonAsOrderedSet,r:R):% == p(r)::%
    eval(p:%,le:List Equation %):% == 
      empty? le  => p
      not empty? rest le => error "can only eval a univariate polynomial once"
      mainVariable(lhs first le) case "failed" => p
      p(rhs first le)
    mainVariable(p:%) ==
      zero? degree p =>  "failed"
      create()$SingletonAsOrderedSet
    minimumDegree(p:%,v:SingletonAsOrderedSet) == minimumDegree p
    minimumDegree(p:%,lv:List SingletonAsOrderedSet) ==
       empty? lv => []
       [minimumDegree p]
    monomial(p:%,v:SingletonAsOrderedSet,n:NonNegativeInteger) ==
       mapExponents(#1+n,p)
    coerce(v:SingletonAsOrderedSet):% == monomial(1,1)
    makeSUP p ==
      zero? p => 0
      monomial(leadingCoefficient p,degree p) + makeSUP reductum p
    unmakeSUP sp ==
      zero? sp => 0
      monomial(leadingCoefficient sp,degree sp) + unmakeSUP reductum sp
    karatsubaDivide(p:%,n:NonNegativeInteger) == monicDivide(p,monomial(1,n))
    shiftRight(p:%,n:NonNegativeInteger) == monicDivide(p,monomial(1,n)).quotient
    shiftLeft(p:%,n:NonNegativeInteger) == p * monomial(1,n)
    if R has PolynomialFactorizationExplicit then
       PFBRU ==>PolynomialFactorizationByRecursionUnivariate(R,%)
       pp,qq:SparseUnivariatePolynomial %
       lpp:List SparseUnivariatePolynomial %
       SupR ==> SparseUnivariatePolynomial R
       sp:SupR

       solveLinearPolynomialEquation(lpp,pp) ==
         solveLinearPolynomialEquationByRecursion(lpp,pp)$PFBRU
       factorPolynomial(pp) ==
         factorByRecursion(pp)$PFBRU
       factorSquareFreePolynomial(pp) ==
         factorSquareFreeByRecursion(pp)$PFBRU
       import FactoredFunctions2(SupR,S)
       factor p ==
         zero? degree p  =>
           ansR:=factor leadingCoefficient p
           makeFR(unit(ansR)::%,
                  [[w.flg,w.fctr::%,w.xpnt] for w in factorList ansR])
         map(unmakeSUP,factorPolynomial(makeSUP p)$R)

    vectorise(p, n) ==
      m := minIndex(v := new(n, 0)$Vector(R))
      for i in minIndex v .. maxIndex v repeat
        qsetelt_!(v, i, coefficient(p, (i - m)::NonNegativeInteger))
      v
    retract(p:%):R ==
      zero? p => 0
      zero? degree p => leadingCoefficient p
      error "Polynomial is not of degree 0"
    retractIfCan(p:%):Union(R, "failed") ==
      zero? p => 0
      zero? degree p => leadingCoefficient p
      "failed"

    if R has StepThrough then
       init() == init()$R::%
       nextItemInner: % -> Union(%,"failed")
       nextItemInner(n) ==
         zero? n => nextItem(0$R)::R::% -- assumed not to fail
         zero? degree n =>
           nn:=nextItem leadingCoefficient n
           nn case "failed" => "failed"
           nn::R::%
         n1:=reductum n
         n2:=nextItemInner n1 -- try stepping the reductum
         n2 case % => monomial(leadingCoefficient n,degree n) + n2
         1+degree n1 < degree n => -- there was a hole between lt n and n1
           monomial(leadingCoefficient n,degree n)+
             monomial(nextItem(init()$R)::R,1+degree n1)
         n3:=nextItem leadingCoefficient n
         n3 case "failed" => "failed"
         monomial(n3,degree n)
       nextItem(n) ==
         n1:=nextItemInner n
         n1 case "failed" => monomial(nextItem(init()$R)::R,1+degree(n))
         n1

    if R has GcdDomain then

      content(p:%,v:SingletonAsOrderedSet) == content(p)::%

      primeFactor: (%, %) -> %

      primeFactor(p, q) ==
        (p1 := (p exquo gcd(p, q))::%) = p => p
        primeFactor(p1, q)

      separate(p, q) ==
        a := primeFactor(p, q)
        [a, (p exquo a)::%]

    if R has CommutativeRing then
      differentiate(x:%, deriv:R -> R, x':%) ==
        d:% := 0
        while (dg := degree x) > 0 repeat
          lc := leadingCoefficient x
          d := d + x' * monomial(dg * lc, (dg - 1)::NonNegativeInteger)
                 + monomial(deriv lc, dg)
          x := reductum x
        d + deriv(leadingCoefficient x)::%
    else
      ncdiff: (NonNegativeInteger, %) -> %
      -- computes d(x**n) given dx = x', non-commutative case
      ncdiff(n, x') ==
        zero? n => 0
        zero?(n1 := (n - 1)::NonNegativeInteger) => x'
        x' * monomial(1, n1) + monomial(1, 1) * ncdiff(n1, x')

      differentiate(x:%, deriv:R -> R, x':%) ==
        d:% := 0
        while (dg := degree x) > 0 repeat
          lc := leadingCoefficient x
          d := d + monomial(deriv lc, dg) + lc * ncdiff(dg, x')
          x := reductum x
        d + deriv(leadingCoefficient x)::%
    differentiate(x:%, deriv:R -> R) == differentiate(x, deriv, 1$%)$%
    differentiate(x:%) ==
        d:% := 0
        while (dg := degree x) > 0 repeat
          d := d + monomial(dg * leadingCoefficient x, (dg - 1)::NonNegativeInteger)
          x := reductum x
        d
    differentiate(x:%,v:SingletonAsOrderedSet) == differentiate x
    if R has IntegralDomain then
      elt(g:Fraction %, f:Fraction %) == ((numer g) f) / ((denom g) f)

      pseudoQuotient(p, q) ==
        (n := degree(p)::Integer - degree q + 1) < 1 => 0
        ((leadingCoefficient(q)**(n::NonNegativeInteger) * p
          - pseudoRemainder(p, q)) exquo q)::%

      pseudoDivide(p, q) ==
        (n := degree(p)::Integer - degree q + 1) < 1 => [1, 0, p]
        prem := pseudoRemainder(p, q)
        lc   := leadingCoefficient(q)**(n::NonNegativeInteger)
        [lc,((lc*p - prem) exquo q)::%, prem]

      composite(f:Fraction %, q:%) ==
        (n := composite(numer f, q)) case "failed" => "failed"
        (d := composite(denom f, q)) case "failed" => "failed"
        n::% / d::%

      composite(p:%, q:%) ==
        ground? p => p
        cqr := pseudoDivide(p, q)
        ground?(cqr.remainder) and
          ((v := cqr.remainder exquo cqr.coef) case %) and
            ((u := composite(cqr.quotient, q)) case %) and
              ((w := (u::%) exquo cqr.coef) case %) =>
                v::% + monomial(1, 1) * w::%
        "failed"

      elt(p:%, f:Fraction %) ==
        zero? p => 0
        ans:Fraction(%) := (leadingCoefficient p)::%::Fraction(%)
        n := degree p
        while not zero?(p:=reductum p) repeat
          ans := ans * f ** (n - (n := degree p))::NonNegativeInteger +
                    (leadingCoefficient p)::%::Fraction(%)
        zero? n => ans
        ans * f ** n

      order(p, q) ==
        zero? p => error "order: arguments must be nonzero"
        degree(q) < 1 => error "order: place must be non-trivial"
        ans:NonNegativeInteger := 0
        repeat
          (u  := p exquo q) case "failed" => return ans
          p   := u::%
          ans := ans + 1

    if R has GcdDomain then
      squareFree(p:%) ==
        squareFree(p)$UnivariatePolynomialSquareFree(R, %)

      squareFreePart(p:%) ==
        squareFreePart(p)$UnivariatePolynomialSquareFree(R, %)

    if R has PolynomialFactorizationExplicit then

      gcdPolynomial(pp,qq) ==
            zero? pp => unitCanonical qq  -- subResultantGcd can't handle 0
            zero? qq => unitCanonical pp
            unitCanonical(gcd(content (pp),content(qq))*
                   primitivePart
                      subResultantGcd(primitivePart pp,primitivePart qq))

      squareFreePolynomial pp ==
         squareFree(pp)$UnivariatePolynomialSquareFree(%,
                                    SparseUnivariatePolynomial %)

    if R has Field then
      elt(f:Fraction %, r:R) == ((numer f) r) / ((denom f) r)

      euclideanSize x ==
            zero? x =>
              error "euclideanSize called on 0 in Univariate Polynomial"
            degree x
      divide(x,y) ==
            zero? y => error "division by 0 in Univariate Polynomials"
            quot:=0
            lc := inv leadingCoefficient y
            while not zero?(x) and (degree x >= degree y) repeat
               f:=lc*leadingCoefficient x
               n:=(degree x - degree y)::NonNegativeInteger
               quot:=quot+monomial(f,n)
               x:=x-monomial(f,n)*y
            [quot,x]
    if R has Algebra Fraction Integer then
      integrate p ==
        ans:% := 0
        while p ^= 0 repeat
          l := leadingCoefficient p
          d := 1 + degree p
          ans := ans + inv(d::Fraction(Integer)) * monomial(l, d)
          p := reductum p
        ans

@
\section{UPOLYC.lsp BOOTSTRAP}
{\bf UPOLYC} depends on itself. We need to break this cycle to build
the algebra. So we keep a cached copy of the translated {\bf UPOLYC}
category which we can write into the {\bf MID} directory. We compile 
the lisp code and copy the {\bf UPOLYC.o} file to the {\bf OUT} directory.
This is eventually forcibly replaced by a recompiled version. 

Note that this code is not included in the generated catdef.spad file.

<<UPOLYC.lsp BOOTSTRAP>>=

(/VERSIONCHECK 2) 

(DEFPARAMETER |UnivariatePolynomialCategory;CAT| 'NIL) 

(DEFPARAMETER |UnivariatePolynomialCategory;AL| 'NIL) 

(DEFUN |UnivariatePolynomialCategory| (#0=#:G1424)
  (LET (#1=#:G1425)
    (COND
      ((SETQ #1#
             (|assoc| (|devaluate| #0#)
                      |UnivariatePolynomialCategory;AL|))
       (CDR #1#))
      (T (SETQ |UnivariatePolynomialCategory;AL|
               (|cons5| (CONS (|devaluate| #0#)
                              (SETQ #1#
                                    (|UnivariatePolynomialCategory;|
                                     #0#)))
                        |UnivariatePolynomialCategory;AL|))
         #1#)))) 

(DEFUN |UnivariatePolynomialCategory;| (|t#1|)
  (PROG (#0=#:G1423)
    (RETURN
      (PROG1 (LETT #0#
                   (|sublisV|
                       (PAIR '(|t#1|) (LIST (|devaluate| |t#1|)))
                       (|sublisV|
                           (PAIR '(#1=#:G1421 #2=#:G1422)
                                 (LIST '(|NonNegativeInteger|)
                                       '(|SingletonAsOrderedSet|)))
                           (COND
                             (|UnivariatePolynomialCategory;CAT|)
                             ('T
                              (LETT |UnivariatePolynomialCategory;CAT|
                                    (|Join|
                                     (|PolynomialCategory| '|t#1| '#1#
                                      '#2#)
                                     (|Eltable| '|t#1| '|t#1|)
                                     (|Eltable| '$ '$)
                                     (|DifferentialRing|)
                                     (|DifferentialExtension| '|t#1|)
                                     (|mkCategory| '|domain|
                                      '(((|vectorise|
                                          ((|Vector| |t#1|) $
                                           (|NonNegativeInteger|)))
                                         T)
                                        ((|makeSUP|
                                          ((|SparseUnivariatePolynomial|
                                            |t#1|)
                                           $))
                                         T)
                                        ((|unmakeSUP|
                                          ($
                                           (|SparseUnivariatePolynomial|
                                            |t#1|)))
                                         T)
                                        ((|multiplyExponents|
                                          ($ $ (|NonNegativeInteger|)))
                                         T)
                                        ((|divideExponents|
                                          ((|Union| $ "failed") $
                                           (|NonNegativeInteger|)))
                                         T)
                                        ((|monicDivide|
                                          ((|Record| (|:| |quotient| $)
                                            (|:| |remainder| $))
                                           $ $))
                                         T)
                                        ((|karatsubaDivide|
                                          ((|Record| (|:| |quotient| $)
                                            (|:| |remainder| $))
                                           $ (|NonNegativeInteger|)))
                                         T)
                                        ((|shiftRight|
                                          ($ $ (|NonNegativeInteger|)))
                                         T)
                                        ((|shiftLeft|
                                          ($ $ (|NonNegativeInteger|)))
                                         T)
                                        ((|pseudoRemainder| ($ $ $)) T)
                                        ((|differentiate|
                                          ($ $ (|Mapping| |t#1| |t#1|)
                                           $))
                                         T)
                                        ((|discriminant| (|t#1| $))
                                         (|has| |t#1|
                                          (|CommutativeRing|)))
                                        ((|resultant| (|t#1| $ $))
                                         (|has| |t#1|
                                          (|CommutativeRing|)))
                                        ((|elt|
                                          ((|Fraction| $)
                                           (|Fraction| $)
                                           (|Fraction| $)))
                                         (|has| |t#1|
                                          (|IntegralDomain|)))
                                        ((|order|
                                          ((|NonNegativeInteger|) $ $))
                                         (|has| |t#1|
                                          (|IntegralDomain|)))
                                        ((|subResultantGcd| ($ $ $))
                                         (|has| |t#1|
                                          (|IntegralDomain|)))
                                        ((|composite|
                                          ((|Union| $ "failed") $ $))
                                         (|has| |t#1|
                                          (|IntegralDomain|)))
                                        ((|composite|
                                          ((|Union| (|Fraction| $)
                                            "failed")
                                           (|Fraction| $) $))
                                         (|has| |t#1|
                                          (|IntegralDomain|)))
                                        ((|pseudoQuotient| ($ $ $))
                                         (|has| |t#1|
                                          (|IntegralDomain|)))
                                        ((|pseudoDivide|
                                          ((|Record| (|:| |coef| |t#1|)
                                            (|:| |quotient| $)
                                            (|:| |remainder| $))
                                           $ $))
                                         (|has| |t#1|
                                          (|IntegralDomain|)))
                                        ((|separate|
                                          ((|Record|
                                            (|:| |primePart| $)
                                            (|:| |commonPart| $))
                                           $ $))
                                         (|has| |t#1| (|GcdDomain|)))
                                        ((|elt|
                                          (|t#1| (|Fraction| $) |t#1|))
                                         (|has| |t#1| (|Field|)))
                                        ((|integrate| ($ $))
                                         (|has| |t#1|
                                          (|Algebra|
                                           (|Fraction| (|Integer|))))))
                                      '(((|StepThrough|)
                                         (|has| |t#1| (|StepThrough|)))
                                        ((|Eltable| (|Fraction| $)
                                          (|Fraction| $))
                                         (|has| |t#1|
                                          (|IntegralDomain|)))
                                        ((|EuclideanDomain|)
                                         (|has| |t#1| (|Field|)))
                                        (|additiveValuation|
                                         (|has| |t#1| (|Field|))))
                                      '((|Fraction| $)
                                        (|NonNegativeInteger|)
                                        (|SparseUnivariatePolynomial|
                                         |t#1|)
                                        (|Vector| |t#1|))
                                      NIL))
                                    . #3=(|UnivariatePolynomialCategory|)))))) . #3#)
        (SETELT #0# 0
                (LIST '|UnivariatePolynomialCategory|
                      (|devaluate| |t#1|))))))) 
@
\section{UPOLYC-.lsp BOOTSTRAP}
{\bf UPOLYC-} depends on {\bf UPOLYC}. We need to break this cycle to build
the algebra. So we keep a cached copy of the translated {\bf UPOLYC-}
category which we can write into the {\bf MID} directory. We compile 
the lisp code and copy the {\bf UPOLYC-.o} file to the {\bf OUT} directory.
This is eventually forcibly replaced by a recompiled version. 

Note that this code is not included in the generated catdef.spad file.

<<UPOLYC-.lsp BOOTSTRAP>>=

(/VERSIONCHECK 2) 

(DEFUN |UPOLYC-;variables;SL;1| (|p| $)
  (COND
    ((OR (SPADCALL |p| (QREFELT $ 9))
         (ZEROP (SPADCALL |p| (QREFELT $ 11))))
     NIL)
    ('T (LIST (SPADCALL (QREFELT $ 13)))))) 

(DEFUN |UPOLYC-;degree;SSaosNni;2| (|p| |v| $)
  (SPADCALL |p| (QREFELT $ 11))) 

(DEFUN |UPOLYC-;totalDegree;SLNni;3| (|p| |lv| $)
  (COND ((NULL |lv|) 0) ('T (SPADCALL |p| (QREFELT $ 17))))) 

(DEFUN |UPOLYC-;degree;SLL;4| (|p| |lv| $)
  (COND ((NULL |lv|) NIL) ('T (LIST (SPADCALL |p| (QREFELT $ 11)))))) 

(DEFUN |UPOLYC-;eval;SLLS;5| (|p| |lv| |lq| $)
  (COND
    ((NULL |lv|) |p|)
    ((NULL (NULL (CDR |lv|)))
     (|error| "can only eval a univariate polynomial once"))
    ('T
     (SPADCALL |p| (|SPADfirst| |lv|) (|SPADfirst| |lq|)
         (QREFELT $ 21))))) 

(DEFUN |UPOLYC-;eval;SSaos2S;6| (|p| |v| |q| $)
  (SPADCALL |p| |q| (QREFELT $ 24))) 

(DEFUN |UPOLYC-;eval;SLLS;7| (|p| |lv| |lr| $)
  (COND
    ((NULL |lv|) |p|)
    ((NULL (NULL (CDR |lv|)))
     (|error| "can only eval a univariate polynomial once"))
    ('T
     (SPADCALL |p| (|SPADfirst| |lv|) (|SPADfirst| |lr|)
         (QREFELT $ 26))))) 

(DEFUN |UPOLYC-;eval;SSaosRS;8| (|p| |v| |r| $)
  (SPADCALL (SPADCALL |p| |r| (QREFELT $ 29)) (QREFELT $ 30))) 

(DEFUN |UPOLYC-;eval;SLS;9| (|p| |le| $)
  (COND
    ((NULL |le|) |p|)
    ((NULL (NULL (CDR |le|)))
     (|error| "can only eval a univariate polynomial once"))
    ('T
     (COND
       ((QEQCAR (SPADCALL (SPADCALL (|SPADfirst| |le|) (QREFELT $ 33))
                    (QREFELT $ 35))
                1)
        |p|)
       ('T
        (SPADCALL |p| (SPADCALL (|SPADfirst| |le|) (QREFELT $ 36))
            (QREFELT $ 24))))))) 

(DEFUN |UPOLYC-;mainVariable;SU;10| (|p| $)
  (COND
    ((ZEROP (SPADCALL |p| (QREFELT $ 11))) (CONS 1 "failed"))
    ('T (CONS 0 (SPADCALL (QREFELT $ 13)))))) 

(DEFUN |UPOLYC-;minimumDegree;SSaosNni;11| (|p| |v| $)
  (SPADCALL |p| (QREFELT $ 40))) 

(DEFUN |UPOLYC-;minimumDegree;SLL;12| (|p| |lv| $)
  (COND ((NULL |lv|) NIL) ('T (LIST (SPADCALL |p| (QREFELT $ 40)))))) 

(DEFUN |UPOLYC-;monomial;SSaosNniS;13| (|p| |v| |n| $)
  (SPADCALL (CONS #'|UPOLYC-;monomial;SSaosNniS;13!0| (VECTOR $ |n|))
      |p| (QREFELT $ 45))) 

(DEFUN |UPOLYC-;monomial;SSaosNniS;13!0| (|#1| $$)
  (SPADCALL |#1| (QREFELT $$ 1) (QREFELT (QREFELT $$ 0) 43))) 

(DEFUN |UPOLYC-;coerce;SaosS;14| (|v| $)
  (SPADCALL (|spadConstant| $ 48) 1 (QREFELT $ 49))) 

(DEFUN |UPOLYC-;makeSUP;SSup;15| (|p| $)
  (COND
    ((SPADCALL |p| (QREFELT $ 9)) (|spadConstant| $ 52))
    ('T
     (SPADCALL
         (SPADCALL (SPADCALL |p| (QREFELT $ 53))
             (SPADCALL |p| (QREFELT $ 11)) (QREFELT $ 54))
         (SPADCALL (SPADCALL |p| (QREFELT $ 55)) (QREFELT $ 56))
         (QREFELT $ 57))))) 

(DEFUN |UPOLYC-;unmakeSUP;SupS;16| (|sp| $)
  (COND
    ((SPADCALL |sp| (QREFELT $ 59)) (|spadConstant| $ 60))
    ('T
     (SPADCALL
         (SPADCALL (SPADCALL |sp| (QREFELT $ 61))
             (SPADCALL |sp| (QREFELT $ 62)) (QREFELT $ 49))
         (SPADCALL (SPADCALL |sp| (QREFELT $ 63)) (QREFELT $ 64))
         (QREFELT $ 65))))) 

(DEFUN |UPOLYC-;karatsubaDivide;SNniR;17| (|p| |n| $)
  (SPADCALL |p| (SPADCALL (|spadConstant| $ 48) |n| (QREFELT $ 49))
      (QREFELT $ 68))) 

(DEFUN |UPOLYC-;shiftRight;SNniS;18| (|p| |n| $)
  (QCAR (SPADCALL |p|
            (SPADCALL (|spadConstant| $ 48) |n| (QREFELT $ 49))
            (QREFELT $ 68)))) 

(DEFUN |UPOLYC-;shiftLeft;SNniS;19| (|p| |n| $)
  (SPADCALL |p| (SPADCALL (|spadConstant| $ 48) |n| (QREFELT $ 49))
      (QREFELT $ 71))) 

(DEFUN |UPOLYC-;solveLinearPolynomialEquation;LSupU;20| (|lpp| |pp| $)
  (SPADCALL |lpp| |pp| (QREFELT $ 77))) 

(DEFUN |UPOLYC-;factorPolynomial;SupF;21| (|pp| $)
  (SPADCALL |pp| (QREFELT $ 83))) 

(DEFUN |UPOLYC-;factorSquareFreePolynomial;SupF;22| (|pp| $)
  (SPADCALL |pp| (QREFELT $ 86))) 

(DEFUN |UPOLYC-;factor;SF;23| (|p| $)
  (PROG (|ansR| #0=#:G1509 |w| #1=#:G1510)
    (RETURN
      (SEQ (COND
             ((ZEROP (SPADCALL |p| (QREFELT $ 11)))
              (SEQ (LETT |ansR|
                         (SPADCALL (SPADCALL |p| (QREFELT $ 53))
                             (QREFELT $ 89))
                         |UPOLYC-;factor;SF;23|)
                   (EXIT (SPADCALL
                             (SPADCALL (SPADCALL |ansR| (QREFELT $ 91))
                                 (QREFELT $ 30))
                             (PROGN
                               (LETT #0# NIL |UPOLYC-;factor;SF;23|)
                               (SEQ (LETT |w| NIL
                                     |UPOLYC-;factor;SF;23|)
                                    (LETT #1#
                                     (SPADCALL |ansR| (QREFELT $ 95))
                                     |UPOLYC-;factor;SF;23|)
                                    G190
                                    (COND
                                      ((OR (ATOM #1#)
                                        (PROGN
                                          (LETT |w| (CAR #1#)
                                           |UPOLYC-;factor;SF;23|)
                                          NIL))
                                       (GO G191)))
                                    (SEQ
                                     (EXIT
                                      (LETT #0#
                                       (CONS
                                        (VECTOR (QVELT |w| 0)
                                         (SPADCALL (QVELT |w| 1)
                                          (QREFELT $ 30))
                                         (QVELT |w| 2))
                                        #0#)
                                       |UPOLYC-;factor;SF;23|)))
                                    (LETT #1# (CDR #1#)
                                     |UPOLYC-;factor;SF;23|)
                                    (GO G190) G191
                                    (EXIT (NREVERSE0 #0#))))
                             (QREFELT $ 99)))))
             ('T
              (SPADCALL (ELT $ 64)
                  (SPADCALL (SPADCALL |p| (QREFELT $ 56))
                      (QREFELT $ 100))
                  (QREFELT $ 104)))))))) 

(DEFUN |UPOLYC-;vectorise;SNniV;24| (|p| |n| $)
  (PROG (|v| |m| |i| #0=#:G1515 #1=#:G1511)
    (RETURN
      (SEQ (LETT |m|
                 (SPADCALL
                     (LETT |v|
                           (SPADCALL |n| (|spadConstant| $ 106)
                               (QREFELT $ 108))
                           |UPOLYC-;vectorise;SNniV;24|)
                     (QREFELT $ 110))
                 |UPOLYC-;vectorise;SNniV;24|)
           (SEQ (LETT |i| (SPADCALL |v| (QREFELT $ 110))
                      |UPOLYC-;vectorise;SNniV;24|)
                (LETT #0# (QVSIZE |v|) |UPOLYC-;vectorise;SNniV;24|)
                G190 (COND ((> |i| #0#) (GO G191)))
                (SEQ (EXIT (SPADCALL |v| |i|
                               (SPADCALL |p|
                                         (PROG1
                                          (LETT #1# (- |i| |m|)
                                           |UPOLYC-;vectorise;SNniV;24|)
                                           (|check-subtype| (>= #1# 0)
                                            '(|NonNegativeInteger|)
                                            #1#))
                                         (QREFELT $ 111))
                               (QREFELT $ 112))))
                (LETT |i| (+ |i| 1) |UPOLYC-;vectorise;SNniV;24|)
                (GO G190) G191 (EXIT NIL))
           (EXIT |v|))))) 

(DEFUN |UPOLYC-;retract;SR;25| (|p| $)
  (COND
    ((SPADCALL |p| (QREFELT $ 9)) (|spadConstant| $ 106))
    ((ZEROP (SPADCALL |p| (QREFELT $ 11)))
     (SPADCALL |p| (QREFELT $ 53)))
    ('T (|error| "Polynomial is not of degree 0")))) 

(DEFUN |UPOLYC-;retractIfCan;SU;26| (|p| $)
  (COND
    ((SPADCALL |p| (QREFELT $ 9)) (CONS 0 (|spadConstant| $ 106)))
    ((ZEROP (SPADCALL |p| (QREFELT $ 11)))
     (CONS 0 (SPADCALL |p| (QREFELT $ 53))))
    ('T (CONS 1 "failed")))) 

(DEFUN |UPOLYC-;init;S;27| ($)
  (SPADCALL (|spadConstant| $ 117) (QREFELT $ 30))) 

(DEFUN |UPOLYC-;nextItemInner| (|n| $)
  (PROG (|nn| |n1| |n2| #0=#:G1536 |n3|)
    (RETURN
      (SEQ (COND
             ((SPADCALL |n| (QREFELT $ 9))
              (CONS 0
                    (SPADCALL
                        (PROG2 (LETT #0#
                                     (SPADCALL (|spadConstant| $ 106)
                                      (QREFELT $ 120))
                                     |UPOLYC-;nextItemInner|)
                               (QCDR #0#)
                          (|check-union| (QEQCAR #0# 0) (QREFELT $ 7)
                              #0#))
                        (QREFELT $ 30))))
             ((ZEROP (SPADCALL |n| (QREFELT $ 11)))
              (SEQ (LETT |nn|
                         (SPADCALL (SPADCALL |n| (QREFELT $ 53))
                             (QREFELT $ 120))
                         |UPOLYC-;nextItemInner|)
                   (EXIT (COND
                           ((QEQCAR |nn| 1) (CONS 1 "failed"))
                           ('T
                            (CONS 0
                                  (SPADCALL (QCDR |nn|) (QREFELT $ 30))))))))
             ('T
              (SEQ (LETT |n1| (SPADCALL |n| (QREFELT $ 55))
                         |UPOLYC-;nextItemInner|)
                   (LETT |n2| (|UPOLYC-;nextItemInner| |n1| $)
                         |UPOLYC-;nextItemInner|)
                   (EXIT (COND
                           ((QEQCAR |n2| 0)
                            (CONS 0
                                  (SPADCALL
                                      (SPADCALL
                                       (SPADCALL |n| (QREFELT $ 53))
                                       (SPADCALL |n| (QREFELT $ 11))
                                       (QREFELT $ 49))
                                      (QCDR |n2|) (QREFELT $ 65))))
                           ((< (+ 1 (SPADCALL |n1| (QREFELT $ 11)))
                               (SPADCALL |n| (QREFELT $ 11)))
                            (CONS 0
                                  (SPADCALL
                                      (SPADCALL
                                       (SPADCALL |n| (QREFELT $ 53))
                                       (SPADCALL |n| (QREFELT $ 11))
                                       (QREFELT $ 49))
                                      (SPADCALL
                                       (PROG2
                                        (LETT #0#
                                         (SPADCALL
                                          (|spadConstant| $ 117)
                                          (QREFELT $ 120))
                                         |UPOLYC-;nextItemInner|)
                                        (QCDR #0#)
                                         (|check-union| (QEQCAR #0# 0)
                                          (QREFELT $ 7) #0#))
                                       (+ 1
                                        (SPADCALL |n1| (QREFELT $ 11)))
                                       (QREFELT $ 49))
                                      (QREFELT $ 65))))
                           ('T
                            (SEQ (LETT |n3|
                                       (SPADCALL
                                        (SPADCALL |n| (QREFELT $ 53))
                                        (QREFELT $ 120))
                                       |UPOLYC-;nextItemInner|)
                                 (EXIT (COND
                                         ((QEQCAR |n3| 1)
                                          (CONS 1 "failed"))
                                         ('T
                                          (CONS 0
                                           (SPADCALL (QCDR |n3|)
                                            (SPADCALL |n|
                                             (QREFELT $ 11))
                                            (QREFELT $ 49))))))))))))))))) 

(DEFUN |UPOLYC-;nextItem;SU;29| (|n| $)
  (PROG (|n1| #0=#:G1549)
    (RETURN
      (SEQ (LETT |n1| (|UPOLYC-;nextItemInner| |n| $)
                 |UPOLYC-;nextItem;SU;29|)
           (EXIT (COND
                   ((QEQCAR |n1| 1)
                    (CONS 0
                          (SPADCALL
                              (PROG2 (LETT #0#
                                      (SPADCALL (|spadConstant| $ 117)
                                       (QREFELT $ 120))
                                      |UPOLYC-;nextItem;SU;29|)
                                     (QCDR #0#)
                                (|check-union| (QEQCAR #0# 0)
                                    (QREFELT $ 7) #0#))
                              (+ 1 (SPADCALL |n| (QREFELT $ 11)))
                              (QREFELT $ 49))))
                   ('T |n1|))))))) 

(DEFUN |UPOLYC-;content;SSaosS;30| (|p| |v| $)
  (SPADCALL (SPADCALL |p| (QREFELT $ 123)) (QREFELT $ 30))) 

(DEFUN |UPOLYC-;primeFactor| (|p| |q| $)
  (PROG (#0=#:G1555 |p1|)
    (RETURN
      (SEQ (LETT |p1|
                 (PROG2 (LETT #0#
                              (SPADCALL |p|
                                        (SPADCALL |p| |q|
                                         (QREFELT $ 125))
                                        (QREFELT $ 126))
                              |UPOLYC-;primeFactor|)
                        (QCDR #0#)
                   (|check-union| (QEQCAR #0# 0) (QREFELT $ 6) #0#))
                 |UPOLYC-;primeFactor|)
           (EXIT (COND
                   ((SPADCALL |p1| |p| (QREFELT $ 127)) |p|)
                   ('T (|UPOLYC-;primeFactor| |p1| |q| $)))))))) 

(DEFUN |UPOLYC-;separate;2SR;32| (|p| |q| $)
  (PROG (|a| #0=#:G1561)
    (RETURN
      (SEQ (LETT |a| (|UPOLYC-;primeFactor| |p| |q| $)
                 |UPOLYC-;separate;2SR;32|)
           (EXIT (CONS |a|
                       (PROG2 (LETT #0#
                                    (SPADCALL |p| |a| (QREFELT $ 126))
                                    |UPOLYC-;separate;2SR;32|)
                              (QCDR #0#)
                         (|check-union| (QEQCAR #0# 0) (QREFELT $ 6)
                             #0#)))))))) 

(DEFUN |UPOLYC-;differentiate;SM2S;33| (|x| |deriv| |x'| $)
  (PROG (|dg| |lc| #0=#:G1566 |d|)
    (RETURN
      (SEQ (LETT |d| (|spadConstant| $ 60)
                 |UPOLYC-;differentiate;SM2S;33|)
           (SEQ G190
                (COND
                  ((NULL (< 0
                            (LETT |dg| (SPADCALL |x| (QREFELT $ 11))
                                  |UPOLYC-;differentiate;SM2S;33|)))
                   (GO G191)))
                (SEQ (LETT |lc| (SPADCALL |x| (QREFELT $ 53))
                           |UPOLYC-;differentiate;SM2S;33|)
                     (LETT |d|
                           (SPADCALL
                               (SPADCALL |d|
                                   (SPADCALL |x'|
                                    (SPADCALL
                                     (SPADCALL |dg| |lc|
                                      (QREFELT $ 131))
                                     (PROG1
                                      (LETT #0# (- |dg| 1)
                                       |UPOLYC-;differentiate;SM2S;33|)
                                       (|check-subtype| (>= #0# 0)
                                        '(|NonNegativeInteger|) #0#))
                                     (QREFELT $ 49))
                                    (QREFELT $ 71))
                                   (QREFELT $ 65))
                               (SPADCALL (SPADCALL |lc| |deriv|) |dg|
                                   (QREFELT $ 49))
                               (QREFELT $ 65))
                           |UPOLYC-;differentiate;SM2S;33|)
                     (EXIT (LETT |x| (SPADCALL |x| (QREFELT $ 55))
                                 |UPOLYC-;differentiate;SM2S;33|)))
                NIL (GO G190) G191 (EXIT NIL))
           (EXIT (SPADCALL |d|
                     (SPADCALL
                         (SPADCALL (SPADCALL |x| (QREFELT $ 53))
                             |deriv|)
                         (QREFELT $ 30))
                     (QREFELT $ 65))))))) 

(DEFUN |UPOLYC-;ncdiff| (|n| |x'| $)
  (PROG (#0=#:G1584 |n1|)
    (RETURN
      (COND
        ((ZEROP |n|) (|spadConstant| $ 60))
        ((ZEROP (LETT |n1|
                      (PROG1 (LETT #0# (- |n| 1) |UPOLYC-;ncdiff|)
                        (|check-subtype| (>= #0# 0)
                            '(|NonNegativeInteger|) #0#))
                      |UPOLYC-;ncdiff|))
         |x'|)
        ('T
         (SPADCALL
             (SPADCALL |x'|
                 (SPADCALL (|spadConstant| $ 48) |n1| (QREFELT $ 49))
                 (QREFELT $ 71))
             (SPADCALL
                 (SPADCALL (|spadConstant| $ 48) 1 (QREFELT $ 49))
                 (|UPOLYC-;ncdiff| |n1| |x'| $) (QREFELT $ 71))
             (QREFELT $ 65))))))) 

(DEFUN |UPOLYC-;differentiate;SM2S;35| (|x| |deriv| |x'| $)
  (PROG (|dg| |lc| |d|)
    (RETURN
      (SEQ (LETT |d| (|spadConstant| $ 60)
                 |UPOLYC-;differentiate;SM2S;35|)
           (SEQ G190
                (COND
                  ((NULL (< 0
                            (LETT |dg| (SPADCALL |x| (QREFELT $ 11))
                                  |UPOLYC-;differentiate;SM2S;35|)))
                   (GO G191)))
                (SEQ (LETT |lc| (SPADCALL |x| (QREFELT $ 53))
                           |UPOLYC-;differentiate;SM2S;35|)
                     (LETT |d|
                           (SPADCALL
                               (SPADCALL |d|
                                   (SPADCALL (SPADCALL |lc| |deriv|)
                                    |dg| (QREFELT $ 49))
                                   (QREFELT $ 65))
                               (SPADCALL |lc|
                                   (|UPOLYC-;ncdiff| |dg| |x'| $)
                                   (QREFELT $ 134))
                               (QREFELT $ 65))
                           |UPOLYC-;differentiate;SM2S;35|)
                     (EXIT (LETT |x| (SPADCALL |x| (QREFELT $ 55))
                                 |UPOLYC-;differentiate;SM2S;35|)))
                NIL (GO G190) G191 (EXIT NIL))
           (EXIT (SPADCALL |d|
                     (SPADCALL
                         (SPADCALL (SPADCALL |x| (QREFELT $ 53))
                             |deriv|)
                         (QREFELT $ 30))
                     (QREFELT $ 65))))))) 

(DEFUN |UPOLYC-;differentiate;SMS;36| (|x| |deriv| $)
  (SPADCALL |x| |deriv| (|spadConstant| $ 47) (QREFELT $ 135))) 

(DEFUN |UPOLYC-;differentiate;2S;37| (|x| $)
  (PROG (|dg| #0=#:G1593 |d|)
    (RETURN
      (SEQ (LETT |d| (|spadConstant| $ 60)
                 |UPOLYC-;differentiate;2S;37|)
           (SEQ G190
                (COND
                  ((NULL (< 0
                            (LETT |dg| (SPADCALL |x| (QREFELT $ 11))
                                  |UPOLYC-;differentiate;2S;37|)))
                   (GO G191)))
                (SEQ (LETT |d|
                           (SPADCALL |d|
                               (SPADCALL
                                   (SPADCALL |dg|
                                    (SPADCALL |x| (QREFELT $ 53))
                                    (QREFELT $ 131))
                                   (PROG1
                                    (LETT #0# (- |dg| 1)
                                     |UPOLYC-;differentiate;2S;37|)
                                     (|check-subtype| (>= #0# 0)
                                      '(|NonNegativeInteger|) #0#))
                                   (QREFELT $ 49))
                               (QREFELT $ 65))
                           |UPOLYC-;differentiate;2S;37|)
                     (EXIT (LETT |x| (SPADCALL |x| (QREFELT $ 55))
                                 |UPOLYC-;differentiate;2S;37|)))
                NIL (GO G190) G191 (EXIT NIL))
           (EXIT |d|))))) 

(DEFUN |UPOLYC-;differentiate;SSaosS;38| (|x| |v| $)
  (SPADCALL |x| (QREFELT $ 138))) 

(DEFUN |UPOLYC-;elt;3F;39| (|g| |f| $)
  (SPADCALL
      (SPADCALL (SPADCALL |g| (QREFELT $ 141)) |f| (QREFELT $ 143))
      (SPADCALL (SPADCALL |g| (QREFELT $ 144)) |f| (QREFELT $ 143))
      (QREFELT $ 145))) 

(DEFUN |UPOLYC-;pseudoQuotient;3S;40| (|p| |q| $)
  (PROG (|n| #0=#:G1639 #1=#:G1641)
    (RETURN
      (SEQ (LETT |n|
                 (+ (- (SPADCALL |p| (QREFELT $ 11))
                       (SPADCALL |q| (QREFELT $ 11)))
                    1)
                 |UPOLYC-;pseudoQuotient;3S;40|)
           (EXIT (COND
                   ((< |n| 1) (|spadConstant| $ 60))
                   ('T
                    (PROG2 (LETT #1#
                                 (SPADCALL
                                     (SPADCALL
                                      (SPADCALL
                                       (SPADCALL
                                        (SPADCALL |q| (QREFELT $ 53))
                                        (PROG1
                                         (LETT #0# |n|
                                          |UPOLYC-;pseudoQuotient;3S;40|)
                                          (|check-subtype| (>= #0# 0)
                                           '(|NonNegativeInteger|) #0#))
                                        (QREFELT $ 147))
                                       |p| (QREFELT $ 134))
                                      (SPADCALL |p| |q|
                                       (QREFELT $ 148))
                                      (QREFELT $ 149))
                                     |q| (QREFELT $ 126))
                                 |UPOLYC-;pseudoQuotient;3S;40|)
                           (QCDR #1#)
                      (|check-union| (QEQCAR #1# 0) (QREFELT $ 6) #1#))))))))) 

(DEFUN |UPOLYC-;pseudoDivide;2SR;41| (|p| |q| $)
  (PROG (|n| |prem| #0=#:G1647 |lc| #1=#:G1649)
    (RETURN
      (SEQ (LETT |n|
                 (+ (- (SPADCALL |p| (QREFELT $ 11))
                       (SPADCALL |q| (QREFELT $ 11)))
                    1)
                 |UPOLYC-;pseudoDivide;2SR;41|)
           (EXIT (COND
                   ((< |n| 1)
                    (VECTOR (|spadConstant| $ 48) (|spadConstant| $ 60)
                            |p|))
                   ('T
                    (SEQ (LETT |prem|
                               (SPADCALL |p| |q| (QREFELT $ 148))
                               |UPOLYC-;pseudoDivide;2SR;41|)
                         (LETT |lc|
                               (SPADCALL (SPADCALL |q| (QREFELT $ 53))
                                   (PROG1
                                    (LETT #0# |n|
                                     |UPOLYC-;pseudoDivide;2SR;41|)
                                     (|check-subtype| (>= #0# 0)
                                      '(|NonNegativeInteger|) #0#))
                                   (QREFELT $ 147))
                               |UPOLYC-;pseudoDivide;2SR;41|)
                         (EXIT (VECTOR |lc|
                                       (PROG2
                                        (LETT #1#
                                         (SPADCALL
                                          (SPADCALL
                                           (SPADCALL |lc| |p|
                                            (QREFELT $ 134))
                                           |prem| (QREFELT $ 149))
                                          |q| (QREFELT $ 126))
                                         |UPOLYC-;pseudoDivide;2SR;41|)
                                        (QCDR #1#)
                                         (|check-union| (QEQCAR #1# 0)
                                          (QREFELT $ 6) #1#))
                                       |prem|)))))))))) 

(DEFUN |UPOLYC-;composite;FSU;42| (|f| |q| $)
  (PROG (|n| |d|)
    (RETURN
      (SEQ (LETT |n|
                 (SPADCALL (SPADCALL |f| (QREFELT $ 141)) |q|
                     (QREFELT $ 153))
                 |UPOLYC-;composite;FSU;42|)
           (EXIT (COND
                   ((QEQCAR |n| 1) (CONS 1 "failed"))
                   ('T
                    (SEQ (LETT |d|
                               (SPADCALL (SPADCALL |f| (QREFELT $ 144))
                                   |q| (QREFELT $ 153))
                               |UPOLYC-;composite;FSU;42|)
                         (EXIT (COND
                                 ((QEQCAR |d| 1) (CONS 1 "failed"))
                                 ('T
                                  (CONS 0
                                        (SPADCALL (QCDR |n|) (QCDR |d|)
                                         (QREFELT $ 154)))))))))))))) 

(DEFUN |UPOLYC-;composite;2SU;43| (|p| |q| $)
  (PROG (|cqr| |v| |u| |w| #0=#:G1675)
    (RETURN
      (SEQ (COND
             ((SPADCALL |p| (QREFELT $ 157)) (CONS 0 |p|))
             ('T
              (SEQ (EXIT (SEQ (LETT |cqr|
                                    (SPADCALL |p| |q| (QREFELT $ 158))
                                    |UPOLYC-;composite;2SU;43|)
                              (COND
                                ((SPADCALL (QVELT |cqr| 2)
                                     (QREFELT $ 157))
                                 (SEQ (LETT |v|
                                       (SPADCALL (QVELT |cqr| 2)
                                        (QVELT |cqr| 0)
                                        (QREFELT $ 159))
                                       |UPOLYC-;composite;2SU;43|)
                                      (EXIT
                                       (COND
                                         ((QEQCAR |v| 0)
                                          (SEQ
                                           (LETT |u|
                                            (SPADCALL (QVELT |cqr| 1)
                                             |q| (QREFELT $ 153))
                                            |UPOLYC-;composite;2SU;43|)
                                           (EXIT
                                            (COND
                                              ((QEQCAR |u| 0)
                                               (SEQ
                                                (LETT |w|
                                                 (SPADCALL (QCDR |u|)
                                                  (QVELT |cqr| 0)
                                                  (QREFELT $ 159))
                                                 |UPOLYC-;composite;2SU;43|)
                                                (EXIT
                                                 (COND
                                                   ((QEQCAR |w| 0)
                                                    (PROGN
                                                      (LETT #0#
                                                       (CONS 0
                                                        (SPADCALL
                                                         (QCDR |v|)
                                                         (SPADCALL
                                                          (SPADCALL
                                                           (|spadConstant|
                                                            $ 48)
                                                           1
                                                           (QREFELT $
                                                            49))
                                                          (QCDR |w|)
                                                          (QREFELT $
                                                           71))
                                                         (QREFELT $ 65)))
                                                       |UPOLYC-;composite;2SU;43|)
                                                      (GO #0#))))))))))))))))
                              (EXIT (CONS 1 "failed"))))
                   #0# (EXIT #0#)))))))) 

(DEFUN |UPOLYC-;elt;S2F;44| (|p| |f| $)
  (PROG (|n| #0=#:G1681 |ans|)
    (RETURN
      (SEQ (COND
             ((SPADCALL |p| (QREFELT $ 9)) (|spadConstant| $ 161))
             ('T
              (SEQ (LETT |ans|
                         (SPADCALL
                             (SPADCALL (SPADCALL |p| (QREFELT $ 53))
                                 (QREFELT $ 30))
                             (QREFELT $ 162))
                         |UPOLYC-;elt;S2F;44|)
                   (LETT |n| (SPADCALL |p| (QREFELT $ 11))
                         |UPOLYC-;elt;S2F;44|)
                   (SEQ G190
                        (COND
                          ((NULL (SPADCALL
                                     (SPADCALL
                                      (LETT |p|
                                       (SPADCALL |p| (QREFELT $ 55))
                                       |UPOLYC-;elt;S2F;44|)
                                      (QREFELT $ 9))
                                     (QREFELT $ 163)))
                           (GO G191)))
                        (SEQ (EXIT (LETT |ans|
                                    (SPADCALL
                                     (SPADCALL |ans|
                                      (SPADCALL |f|
                                       (PROG1
                                        (LETT #0#
                                         (- |n|
                                          (LETT |n|
                                           (SPADCALL |p|
                                            (QREFELT $ 11))
                                           |UPOLYC-;elt;S2F;44|))
                                         |UPOLYC-;elt;S2F;44|)
                                         (|check-subtype| (>= #0# 0)
                                          '(|NonNegativeInteger|) #0#))
                                       (QREFELT $ 164))
                                      (QREFELT $ 165))
                                     (SPADCALL
                                      (SPADCALL
                                       (SPADCALL |p| (QREFELT $ 53))
                                       (QREFELT $ 30))
                                      (QREFELT $ 162))
                                     (QREFELT $ 166))
                                    |UPOLYC-;elt;S2F;44|)))
                        NIL (GO G190) G191 (EXIT NIL))
                   (EXIT (COND
                           ((ZEROP |n|) |ans|)
                           ('T
                            (SPADCALL |ans|
                                (SPADCALL |f| |n| (QREFELT $ 167))
                                (QREFELT $ 165)))))))))))) 

(DEFUN |UPOLYC-;order;2SNni;45| (|p| |q| $)
  (PROG (|u| #0=#:G1695 |ans|)
    (RETURN
      (SEQ (EXIT (COND
                   ((SPADCALL |p| (QREFELT $ 9))
                    (|error| "order: arguments must be nonzero"))
                   ((< (SPADCALL |q| (QREFELT $ 11)) 1)
                    (|error| "order: place must be non-trivial"))
                   ('T
                    (SEQ (LETT |ans| 0 |UPOLYC-;order;2SNni;45|)
                         (EXIT (SEQ G190 NIL
                                    (SEQ
                                     (LETT |u|
                                      (SPADCALL |p| |q|
                                       (QREFELT $ 126))
                                      |UPOLYC-;order;2SNni;45|)
                                     (EXIT
                                      (COND
                                        ((QEQCAR |u| 1)
                                         (PROGN
                                           (LETT #0# |ans|
                                            |UPOLYC-;order;2SNni;45|)
                                           (GO #0#)))
                                        ('T
                                         (SEQ
                                          (LETT |p| (QCDR |u|)
                                           |UPOLYC-;order;2SNni;45|)
                                          (EXIT
                                           (LETT |ans| (+ |ans| 1)
                                            |UPOLYC-;order;2SNni;45|)))))))
                                    NIL (GO G190) G191 (EXIT NIL)))))))
           #0# (EXIT #0#))))) 

(DEFUN |UPOLYC-;squareFree;SF;46| (|p| $)
  (SPADCALL |p| (QREFELT $ 171))) 

(DEFUN |UPOLYC-;squareFreePart;2S;47| (|p| $)
  (SPADCALL |p| (QREFELT $ 173))) 

(DEFUN |UPOLYC-;gcdPolynomial;3Sup;48| (|pp| |qq| $)
  (COND
    ((SPADCALL |pp| (QREFELT $ 175)) (SPADCALL |qq| (QREFELT $ 176)))
    ((SPADCALL |qq| (QREFELT $ 175)) (SPADCALL |pp| (QREFELT $ 176)))
    ('T
     (SPADCALL
         (SPADCALL
             (SPADCALL (SPADCALL |pp| (QREFELT $ 177))
                 (SPADCALL |qq| (QREFELT $ 177)) (QREFELT $ 125))
             (SPADCALL
                 (SPADCALL (SPADCALL |pp| (QREFELT $ 178))
                     (SPADCALL |qq| (QREFELT $ 178)) (QREFELT $ 179))
                 (QREFELT $ 178))
             (QREFELT $ 180))
         (QREFELT $ 176))))) 

(DEFUN |UPOLYC-;squareFreePolynomial;SupF;49| (|pp| $)
  (SPADCALL |pp| (QREFELT $ 183))) 

(DEFUN |UPOLYC-;elt;F2R;50| (|f| |r| $)
  (SPADCALL (SPADCALL (SPADCALL |f| (QREFELT $ 141)) |r|
                (QREFELT $ 29))
            (SPADCALL (SPADCALL |f| (QREFELT $ 144)) |r|
                (QREFELT $ 29))
            (QREFELT $ 185))) 

(DEFUN |UPOLYC-;euclideanSize;SNni;51| (|x| $)
  (COND
    ((SPADCALL |x| (QREFELT $ 9))
     (|error| "euclideanSize called on 0 in Univariate Polynomial"))
    ('T (SPADCALL |x| (QREFELT $ 11))))) 

(DEFUN |UPOLYC-;divide;2SR;52| (|x| |y| $)
  (PROG (|lc| |f| #0=#:G1707 |n| |quot|)
    (RETURN
      (SEQ (COND
             ((SPADCALL |y| (QREFELT $ 9))
              (|error| "division by 0 in Univariate Polynomials"))
             ('T
              (SEQ (LETT |quot| (|spadConstant| $ 60)
                         |UPOLYC-;divide;2SR;52|)
                   (LETT |lc|
                         (SPADCALL (SPADCALL |y| (QREFELT $ 53))
                             (QREFELT $ 188))
                         |UPOLYC-;divide;2SR;52|)
                   (SEQ G190
                        (COND
                          ((NULL (COND
                                   ((SPADCALL |x| (QREFELT $ 9)) 'NIL)
                                   ('T
                                    (SPADCALL
                                     (< (SPADCALL |x| (QREFELT $ 11))
                                      (SPADCALL |y| (QREFELT $ 11)))
                                     (QREFELT $ 163)))))
                           (GO G191)))
                        (SEQ (LETT |f|
                                   (SPADCALL |lc|
                                    (SPADCALL |x| (QREFELT $ 53))
                                    (QREFELT $ 189))
                                   |UPOLYC-;divide;2SR;52|)
                             (LETT |n|
                                   (PROG1
                                    (LETT #0#
                                     (- (SPADCALL |x| (QREFELT $ 11))
                                      (SPADCALL |y| (QREFELT $ 11)))
                                     |UPOLYC-;divide;2SR;52|)
                                     (|check-subtype| (>= #0# 0)
                                      '(|NonNegativeInteger|) #0#))
                                   |UPOLYC-;divide;2SR;52|)
                             (LETT |quot|
                                   (SPADCALL |quot|
                                    (SPADCALL |f| |n| (QREFELT $ 49))
                                    (QREFELT $ 65))
                                   |UPOLYC-;divide;2SR;52|)
                             (EXIT (LETT |x|
                                    (SPADCALL |x|
                                     (SPADCALL
                                      (SPADCALL |f| |n| (QREFELT $ 49))
                                      |y| (QREFELT $ 71))
                                     (QREFELT $ 149))
                                    |UPOLYC-;divide;2SR;52|)))
                        NIL (GO G190) G191 (EXIT NIL))
                   (EXIT (CONS |quot| |x|))))))))) 

(DEFUN |UPOLYC-;integrate;2S;53| (|p| $)
  (PROG (|l| |d| |ans|)
    (RETURN
      (SEQ (LETT |ans| (|spadConstant| $ 60) |UPOLYC-;integrate;2S;53|)
           (SEQ G190
                (COND
                  ((NULL (SPADCALL
                             (SPADCALL |p| (|spadConstant| $ 60)
                                 (QREFELT $ 127))
                             (QREFELT $ 163)))
                   (GO G191)))
                (SEQ (LETT |l| (SPADCALL |p| (QREFELT $ 53))
                           |UPOLYC-;integrate;2S;53|)
                     (LETT |d| (+ 1 (SPADCALL |p| (QREFELT $ 11)))
                           |UPOLYC-;integrate;2S;53|)
                     (LETT |ans|
                           (SPADCALL |ans|
                               (SPADCALL
                                   (SPADCALL
                                    (SPADCALL |d| (QREFELT $ 192))
                                    (QREFELT $ 193))
                                   (SPADCALL |l| |d| (QREFELT $ 49))
                                   (QREFELT $ 194))
                               (QREFELT $ 65))
                           |UPOLYC-;integrate;2S;53|)
                     (EXIT (LETT |p| (SPADCALL |p| (QREFELT $ 55))
                                 |UPOLYC-;integrate;2S;53|)))
                NIL (GO G190) G191 (EXIT NIL))
           (EXIT |ans|))))) 

(DEFUN |UnivariatePolynomialCategory&| (|#1| |#2|)
  (PROG (|dv$1| |dv$2| |dv$| $ |pv$|)
    (RETURN
      (PROGN
        (LETT |dv$1| (|devaluate| |#1|)
              . #0=(|UnivariatePolynomialCategory&|))
        (LETT |dv$2| (|devaluate| |#2|) . #0#)
        (LETT |dv$|
              (LIST '|UnivariatePolynomialCategory&| |dv$1| |dv$2|) . #0#)
        (LETT $ (GETREFV 202) . #0#)
        (QSETREFV $ 0 |dv$|)
        (QSETREFV $ 3
            (LETT |pv$|
                  (|buildPredVector| 0 0
                      (LIST (|HasCategory| |#2|
                                '(|Algebra| (|Fraction| (|Integer|))))
                            (|HasCategory| |#2| '(|Field|))
                            (|HasCategory| |#2| '(|GcdDomain|))
                            (|HasCategory| |#2| '(|IntegralDomain|))
                            (|HasCategory| |#2| '(|CommutativeRing|))
                            (|HasCategory| |#2| '(|StepThrough|)))) . #0#))
        (|stuffDomainSlots| $)
        (QSETREFV $ 6 |#1|)
        (QSETREFV $ 7 |#2|)
        (COND
          ((|HasCategory| |#2| '(|PolynomialFactorizationExplicit|))
           (PROGN
             (QSETREFV $ 81
                 (CONS (|dispatchFunction|
                           |UPOLYC-;solveLinearPolynomialEquation;LSupU;20|)
                       $))
             (QSETREFV $ 85
                 (CONS (|dispatchFunction|
                           |UPOLYC-;factorPolynomial;SupF;21|)
                       $))
             (QSETREFV $ 87
                 (CONS (|dispatchFunction|
                           |UPOLYC-;factorSquareFreePolynomial;SupF;22|)
                       $))
             (QSETREFV $ 105
                 (CONS (|dispatchFunction| |UPOLYC-;factor;SF;23|) $)))))
        (COND
          ((|testBitVector| |pv$| 6)
           (PROGN
             (QSETREFV $ 118
                 (CONS (|dispatchFunction| |UPOLYC-;init;S;27|) $))
             NIL
             (QSETREFV $ 122
                 (CONS (|dispatchFunction| |UPOLYC-;nextItem;SU;29|) $)))))
        (COND
          ((|testBitVector| |pv$| 3)
           (PROGN
             (QSETREFV $ 124
                 (CONS (|dispatchFunction| |UPOLYC-;content;SSaosS;30|)
                       $))
             NIL
             (QSETREFV $ 129
                 (CONS (|dispatchFunction| |UPOLYC-;separate;2SR;32|)
                       $)))))
        (COND
          ((|testBitVector| |pv$| 5)
           (QSETREFV $ 133
               (CONS (|dispatchFunction|
                         |UPOLYC-;differentiate;SM2S;33|)
                     $)))
          ('T
           (PROGN
             (QSETREFV $ 133
                 (CONS (|dispatchFunction|
                           |UPOLYC-;differentiate;SM2S;35|)
                       $)))))
        (COND
          ((|testBitVector| |pv$| 4)
           (PROGN
             (QSETREFV $ 146
                 (CONS (|dispatchFunction| |UPOLYC-;elt;3F;39|) $))
             (QSETREFV $ 150
                 (CONS (|dispatchFunction|
                           |UPOLYC-;pseudoQuotient;3S;40|)
                       $))
             (QSETREFV $ 152
                 (CONS (|dispatchFunction|
                           |UPOLYC-;pseudoDivide;2SR;41|)
                       $))
             (QSETREFV $ 156
                 (CONS (|dispatchFunction| |UPOLYC-;composite;FSU;42|)
                       $))
             (QSETREFV $ 160
                 (CONS (|dispatchFunction| |UPOLYC-;composite;2SU;43|)
                       $))
             (QSETREFV $ 168
                 (CONS (|dispatchFunction| |UPOLYC-;elt;S2F;44|) $))
             (QSETREFV $ 169
                 (CONS (|dispatchFunction| |UPOLYC-;order;2SNni;45|) $)))))
        (COND
          ((|testBitVector| |pv$| 3)
           (PROGN
             (QSETREFV $ 172
                 (CONS (|dispatchFunction| |UPOLYC-;squareFree;SF;46|)
                       $))
             (QSETREFV $ 174
                 (CONS (|dispatchFunction|
                           |UPOLYC-;squareFreePart;2S;47|)
                       $)))))
        (COND
          ((|HasCategory| |#2| '(|PolynomialFactorizationExplicit|))
           (PROGN
             (QSETREFV $ 181
                 (CONS (|dispatchFunction|
                           |UPOLYC-;gcdPolynomial;3Sup;48|)
                       $))
             (QSETREFV $ 184
                 (CONS (|dispatchFunction|
                           |UPOLYC-;squareFreePolynomial;SupF;49|)
                       $)))))
        (COND
          ((|testBitVector| |pv$| 2)
           (PROGN
             (QSETREFV $ 186
                 (CONS (|dispatchFunction| |UPOLYC-;elt;F2R;50|) $))
             (QSETREFV $ 187
                 (CONS (|dispatchFunction|
                           |UPOLYC-;euclideanSize;SNni;51|)
                       $))
             (QSETREFV $ 190
                 (CONS (|dispatchFunction| |UPOLYC-;divide;2SR;52|) $)))))
        (COND
          ((|testBitVector| |pv$| 1)
           (QSETREFV $ 195
               (CONS (|dispatchFunction| |UPOLYC-;integrate;2S;53|) $))))
        $)))) 

(MAKEPROP '|UnivariatePolynomialCategory&| '|infovec|
    (LIST '#(NIL NIL NIL NIL NIL NIL (|local| |#1|) (|local| |#2|)
             (|Boolean|) (0 . |zero?|) (|NonNegativeInteger|)
             (5 . |degree|) (|SingletonAsOrderedSet|) (10 . |create|)
             (|List| 12) |UPOLYC-;variables;SL;1|
             |UPOLYC-;degree;SSaosNni;2| (14 . |totalDegree|)
             |UPOLYC-;totalDegree;SLNni;3| (|List| 10)
             |UPOLYC-;degree;SLL;4| (19 . |eval|) (|List| $)
             |UPOLYC-;eval;SLLS;5| (26 . |elt|)
             |UPOLYC-;eval;SSaos2S;6| (32 . |eval|) (|List| 7)
             |UPOLYC-;eval;SLLS;7| (39 . |elt|) (45 . |coerce|)
             |UPOLYC-;eval;SSaosRS;8| (|Equation| 6) (50 . |lhs|)
             (|Union| 12 '"failed") (55 . |mainVariable|) (60 . |rhs|)
             (|List| 198) |UPOLYC-;eval;SLS;9|
             |UPOLYC-;mainVariable;SU;10| (65 . |minimumDegree|)
             |UPOLYC-;minimumDegree;SSaosNni;11|
             |UPOLYC-;minimumDegree;SLL;12| (70 . +) (|Mapping| 10 10)
             (76 . |mapExponents|) |UPOLYC-;monomial;SSaosNniS;13|
             (82 . |One|) (86 . |One|) (90 . |monomial|)
             |UPOLYC-;coerce;SaosS;14| (|SparseUnivariatePolynomial| 7)
             (96 . |Zero|) (100 . |leadingCoefficient|)
             (105 . |monomial|) (111 . |reductum|) (116 . |makeSUP|)
             (121 . +) |UPOLYC-;makeSUP;SSup;15| (127 . |zero?|)
             (132 . |Zero|) (136 . |leadingCoefficient|)
             (141 . |degree|) (146 . |reductum|) (151 . |unmakeSUP|)
             (156 . +) |UPOLYC-;unmakeSUP;SupS;16|
             (|Record| (|:| |quotient| $) (|:| |remainder| $))
             (162 . |monicDivide|) |UPOLYC-;karatsubaDivide;SNniR;17|
             |UPOLYC-;shiftRight;SNniS;18| (168 . *)
             |UPOLYC-;shiftLeft;SNniS;19| (|Union| 74 '"failed")
             (|List| 75) (|SparseUnivariatePolynomial| 6)
             (|PolynomialFactorizationByRecursionUnivariate| 7 6)
             (174 . |solveLinearPolynomialEquationByRecursion|)
             (|Union| 79 '"failed") (|List| 80)
             (|SparseUnivariatePolynomial| $)
             (180 . |solveLinearPolynomialEquation|) (|Factored| 75)
             (186 . |factorByRecursion|) (|Factored| 80)
             (191 . |factorPolynomial|)
             (196 . |factorSquareFreeByRecursion|)
             (201 . |factorSquareFreePolynomial|) (|Factored| $)
             (206 . |factor|) (|Factored| 7) (211 . |unit|)
             (|Union| '"nil" '"sqfr" '"irred" '"prime")
             (|Record| (|:| |flg| 92) (|:| |fctr| 7) (|:| |xpnt| 109))
             (|List| 93) (216 . |factorList|)
             (|Record| (|:| |flg| 92) (|:| |fctr| 6) (|:| |xpnt| 109))
             (|List| 96) (|Factored| 6) (221 . |makeFR|)
             (227 . |factorPolynomial|) (|Mapping| 6 51)
             (|Factored| 51) (|FactoredFunctions2| 51 6) (232 . |map|)
             (238 . |factor|) (243 . |Zero|) (|Vector| 7) (247 . |new|)
             (|Integer|) (253 . |minIndex|) (258 . |coefficient|)
             (264 . |qsetelt!|) |UPOLYC-;vectorise;SNniV;24|
             |UPOLYC-;retract;SR;25| (|Union| 7 '"failed")
             |UPOLYC-;retractIfCan;SU;26| (271 . |init|) (275 . |init|)
             (|Union| $ '"failed") (279 . |nextItem|) (284 . |One|)
             (288 . |nextItem|) (293 . |content|) (298 . |content|)
             (304 . |gcd|) (310 . |exquo|) (316 . =)
             (|Record| (|:| |primePart| $) (|:| |commonPart| $))
             (322 . |separate|) (328 . |Zero|) (332 . *)
             (|Mapping| 7 7) (338 . |differentiate|) (345 . *)
             (351 . |differentiate|) |UPOLYC-;differentiate;SMS;36|
             |UPOLYC-;differentiate;2S;37| (358 . |differentiate|)
             |UPOLYC-;differentiate;SSaosS;38| (|Fraction| 6)
             (363 . |numer|) (|Fraction| $) (368 . |elt|)
             (374 . |denom|) (379 . /) (385 . |elt|) (391 . **)
             (397 . |pseudoRemainder|) (403 . -)
             (409 . |pseudoQuotient|)
             (|Record| (|:| |coef| 7) (|:| |quotient| $)
                 (|:| |remainder| $))
             (415 . |pseudoDivide|) (421 . |composite|) (427 . /)
             (|Union| 142 '"failed") (433 . |composite|)
             (439 . |ground?|) (444 . |pseudoDivide|) (450 . |exquo|)
             (456 . |composite|) (462 . |Zero|) (466 . |coerce|)
             (471 . |not|) (476 . **) (482 . *) (488 . +) (494 . **)
             (500 . |elt|) (506 . |order|)
             (|UnivariatePolynomialSquareFree| 7 6)
             (512 . |squareFree|) (517 . |squareFree|)
             (522 . |squareFreePart|) (527 . |squareFreePart|)
             (532 . |zero?|) (537 . |unitCanonical|) (542 . |content|)
             (547 . |primitivePart|) (552 . |subResultantGcd|)
             (558 . *) (564 . |gcdPolynomial|)
             (|UnivariatePolynomialSquareFree| 6 75)
             (570 . |squareFree|) (575 . |squareFreePolynomial|)
             (580 . /) (586 . |elt|) (592 . |euclideanSize|)
             (597 . |inv|) (602 . *) (608 . |divide|) (|Fraction| 109)
             (614 . |coerce|) (619 . |inv|) (624 . *)
             (630 . |integrate|) (|Symbol|) (|List| 196) (|Equation| $)
             (|Union| 109 '"failed") (|Union| 191 '"failed")
             (|OutputForm|))
          '#(|vectorise| 635 |variables| 641 |unmakeSUP| 646
             |totalDegree| 651 |squareFreePolynomial| 657
             |squareFreePart| 662 |squareFree| 667
             |solveLinearPolynomialEquation| 672 |shiftRight| 678
             |shiftLeft| 684 |separate| 690 |retractIfCan| 696
             |retract| 701 |pseudoQuotient| 706 |pseudoDivide| 712
             |order| 718 |nextItem| 724 |monomial| 729 |minimumDegree|
             736 |makeSUP| 748 |mainVariable| 753 |karatsubaDivide| 758
             |integrate| 764 |init| 769 |gcdPolynomial| 773
             |factorSquareFreePolynomial| 779 |factorPolynomial| 784
             |factor| 789 |eval| 794 |euclideanSize| 828 |elt| 833
             |divide| 851 |differentiate| 857 |degree| 881 |content|
             893 |composite| 899 |coerce| 911)
          'NIL
          (CONS (|makeByteWordVec2| 1 'NIL)
                (CONS '#()
                      (CONS '#()
                            (|makeByteWordVec2| 195
                                '(1 6 8 0 9 1 6 10 0 11 0 12 0 13 1 6
                                  10 0 17 3 6 0 0 12 0 21 2 6 0 0 0 24
                                  3 6 0 0 12 7 26 2 6 7 0 7 29 1 6 0 7
                                  30 1 32 6 0 33 1 6 34 0 35 1 32 6 0
                                  36 1 6 10 0 40 2 10 0 0 0 43 2 6 0 44
                                  0 45 0 6 0 47 0 7 0 48 2 6 0 7 10 49
                                  0 51 0 52 1 6 7 0 53 2 51 0 7 10 54 1
                                  6 0 0 55 1 6 51 0 56 2 51 0 0 0 57 1
                                  51 8 0 59 0 6 0 60 1 51 7 0 61 1 51
                                  10 0 62 1 51 0 0 63 1 6 0 51 64 2 6 0
                                  0 0 65 2 6 67 0 0 68 2 6 0 0 0 71 2
                                  76 73 74 75 77 2 0 78 79 80 81 1 76
                                  82 75 83 1 0 84 80 85 1 76 82 75 86 1
                                  0 84 80 87 1 7 88 0 89 1 90 7 0 91 1
                                  90 94 0 95 2 98 0 6 97 99 1 7 84 80
                                  100 2 103 98 101 102 104 1 0 88 0 105
                                  0 7 0 106 2 107 0 10 7 108 1 107 109
                                  0 110 2 6 7 0 10 111 3 107 7 0 109 7
                                  112 0 7 0 117 0 0 0 118 1 7 119 0 120
                                  0 75 0 121 1 0 119 0 122 1 6 7 0 123
                                  2 0 0 0 12 124 2 6 0 0 0 125 2 6 119
                                  0 0 126 2 6 8 0 0 127 2 0 128 0 0 129
                                  0 75 0 130 2 7 0 10 0 131 3 0 0 0 132
                                  0 133 2 6 0 7 0 134 3 6 0 0 132 0 135
                                  1 6 0 0 138 1 140 6 0 141 2 6 142 0
                                  142 143 1 140 6 0 144 2 140 0 0 0 145
                                  2 0 142 142 142 146 2 7 0 0 10 147 2
                                  6 0 0 0 148 2 6 0 0 0 149 2 0 0 0 0
                                  150 2 0 151 0 0 152 2 6 119 0 0 153 2
                                  140 0 6 6 154 2 0 155 142 0 156 1 6 8
                                  0 157 2 6 151 0 0 158 2 6 119 0 7 159
                                  2 0 119 0 0 160 0 140 0 161 1 140 0 6
                                  162 1 8 0 0 163 2 140 0 0 109 164 2
                                  140 0 0 0 165 2 140 0 0 0 166 2 140 0
                                  0 10 167 2 0 142 0 142 168 2 0 10 0 0
                                  169 1 170 98 6 171 1 0 88 0 172 1 170
                                  6 6 173 1 0 0 0 174 1 75 8 0 175 1 75
                                  0 0 176 1 75 6 0 177 1 75 0 0 178 2
                                  75 0 0 0 179 2 75 0 6 0 180 2 0 80 80
                                  80 181 1 182 82 75 183 1 0 84 80 184
                                  2 7 0 0 0 185 2 0 7 142 7 186 1 0 10
                                  0 187 1 7 0 0 188 2 7 0 0 0 189 2 0
                                  67 0 0 190 1 191 0 109 192 1 191 0 0
                                  193 2 6 0 191 0 194 1 0 0 0 195 2 0
                                  107 0 10 113 1 0 14 0 15 1 0 0 51 66
                                  2 0 10 0 14 18 1 0 84 80 184 1 0 0 0
                                  174 1 0 88 0 172 2 0 78 79 80 81 2 0
                                  0 0 10 70 2 0 0 0 10 72 2 0 128 0 0
                                  129 1 0 115 0 116 1 0 7 0 114 2 0 0 0
                                  0 150 2 0 151 0 0 152 2 0 10 0 0 169
                                  1 0 119 0 122 3 0 0 0 12 10 46 2 0 19
                                  0 14 42 2 0 10 0 12 41 1 0 51 0 58 1
                                  0 34 0 39 2 0 67 0 10 69 1 0 0 0 195
                                  0 0 0 118 2 0 80 80 80 181 1 0 84 80
                                  87 1 0 84 80 85 1 0 88 0 105 3 0 0 0
                                  12 0 25 3 0 0 0 14 22 23 3 0 0 0 14
                                  27 28 3 0 0 0 12 7 31 2 0 0 0 37 38 1
                                  0 10 0 187 2 0 142 0 142 168 2 0 7
                                  142 7 186 2 0 142 142 142 146 2 0 67
                                  0 0 190 3 0 0 0 132 0 133 2 0 0 0 132
                                  136 1 0 0 0 137 2 0 0 0 12 139 2 0 10
                                  0 12 16 2 0 19 0 14 20 2 0 0 0 12 124
                                  2 0 119 0 0 160 2 0 155 142 0 156 1 0
                                  0 12 50)))))
          '|lookupComplete|)) 
@
\section{package UPOLYC2 UnivariatePolynomialCategoryFunctions2}
<<package UPOLYC2 UnivariatePolynomialCategoryFunctions2>>=
)abbrev package UPOLYC2 UnivariatePolynomialCategoryFunctions2
++ Author:
++ Date Created:
++ Date Last Updated:
++ Basic Functions:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ Mapping from polynomials over R to polynomials over S
++ given a map from R to S assumed to send zero to zero.

UnivariatePolynomialCategoryFunctions2(R,PR,S,PS): Exports == Impl where
  R, S: Ring
  PR  : UnivariatePolynomialCategory R
  PS  : UnivariatePolynomialCategory S

  Exports ==> with
    map: (R -> S, PR) -> PS
     ++ map(f, p) takes a function f from R to S,
     ++ and applies it to each (non-zero) coefficient of a polynomial p
     ++ over R, getting a new polynomial over S.
     ++ Note: since the map is not applied to zero elements, it may map zero
     ++ to zero.

  Impl ==> add
    map(f, p) ==
      ans:PS := 0
      while p ^= 0 repeat
        ans := ans + monomial(f leadingCoefficient p, degree p)
        p   := reductum p
      ans

@
\section{package COMMUPC CommuteUnivariatePolynomialCategory}
<<package COMMUPC CommuteUnivariatePolynomialCategory>>=
)abbrev package COMMUPC CommuteUnivariatePolynomialCategory
++ Author: Manuel Bronstein
++ Date Created:
++ Date Last Updated:
++ Basic Functions:
++ Related Constructors:
++ Also See:
++ AMS Classifications:
++ Keywords:
++ References:
++ Description:
++ A package for swapping the order of two variables in a tower of two
++ UnivariatePolynomialCategory extensions.

CommuteUnivariatePolynomialCategory(R, UP, UPUP): Exports == Impl where
  R   : Ring
  UP  : UnivariatePolynomialCategory R
  UPUP: UnivariatePolynomialCategory UP

  N ==> NonNegativeInteger

  Exports ==> with
    swap: UPUP -> UPUP
      ++ swap(p(x,y)) returns p(y,x).

  Impl ==> add
    makePoly: (UP, N) -> UPUP

-- converts P(x,y) to P(y,x)
    swap poly ==
      ans:UPUP := 0
      while poly ^= 0 repeat
        ans  := ans + makePoly(leadingCoefficient poly, degree poly)
        poly := reductum poly
      ans

    makePoly(poly, d) ==
      ans:UPUP := 0
      while poly ^= 0 repeat
        ans  := ans +
             monomial(monomial(leadingCoefficient poly, d), degree poly)
        poly := reductum poly
      ans

@
\section{License}
<<license>>=
--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
--All rights reserved.
--
--Redistribution and use in source and binary forms, with or without
--modification, are permitted provided that the following conditions are
--met:
--
--    - Redistributions of source code must retain the above copyright
--      notice, this list of conditions and the following disclaimer.
--
--    - Redistributions in binary form must reproduce the above copyright
--      notice, this list of conditions and the following disclaimer in
--      the documentation and/or other materials provided with the
--      distribution.
--
--    - Neither the name of The Numerical ALgorithms Group Ltd. nor the
--      names of its contributors may be used to endorse or promote products
--      derived from this software without specific prior written permission.
--
--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
@
<<*>>=
<<license>>

<<category AMR AbelianMonoidRing>>
<<category FAMR FiniteAbelianMonoidRing>>
<<category POLYCAT PolynomialCategory>>
<<package POLYLIFT PolynomialCategoryLifting>>
<<category UPOLYC UnivariatePolynomialCategory>>
<<package UPOLYC2 UnivariatePolynomialCategoryFunctions2>>
<<package COMMUPC CommuteUnivariatePolynomialCategory>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}