==========================================================================
20140602 tpd books/bookvol10.4 apply Waldek's changes to imposelc in PGCD
==========================================================================

This patch changes the internal routine "imposelc" (presumably the
impose leading coefficient condition) to check for failure. This
is a preliminary step to Waldek's full patch.

The imposelc signature used to return a list of SUP
(SparseUnivariatePolynomial)

-      imposelc        : (List SUP,List OV,List R,List P) -> List SUP

Now it can also fail so it maps to a Union.

+      imposelc        : (List SUP,List OV,List R,List P) ->
+                          Union(List SUP, "failed")

In the inner loop of imposelc the change is from

-           p1:= univariate eval(leadpol,lvar,lval) * pol
-           result:= cons((p1 exquo leadingCoefficient pol)::SUP,result)

to check for a failure case. Unfortunately I don't know how to
generate a failure case. I'm just following Walkek's lead here.

+           p1 := univariate eval(leadpol, lvar, lval) * pol
+           p1u := p1 exquo leadingCoefficient pol
+           p1u case "failed" => return "failed"
+           result := cons(p1u::SUP, result)

The rest of the changes are cosmetic, adding an initial try at
documentation, an example (++E) for the )describe gcd command,
and some splitting of long lines.

==================================================================

diff --git a/books/bookvol10.4.pamphlet b/books/bookvol10.4.pamphlet
index a157e66..603c8ec 100644
--- a/books/bookvol10.4.pamphlet
+++ b/books/bookvol10.4.pamphlet
@@ -139287,13 +139287,46 @@ o )show PolynomialGcdPackage
 \cross{PGCD}{gcdPrimitive}
 \end{tabular}

+The simple Euclidean division algorithm,
+
+{\bf given} $a \ne 0$, $b \ne 0$ where $a$ and $b$ are two polynomials
+in the variable $x$, then
+
+{\bf output} $q$, the quotient and $r$, the remainder
+
+{\bf begin}
+
+{\bf Let}\\
+\quad\quad $q = 0$\\
+\quad\quad $r = a$\\
+\quad\quad $d = {\rm\ degree}(b)$\\
+\quad\quad $c = {\rm\ leadingCoefficient}(b)$\\
+
+{\bf while} ${\rm\ degree}(r) \ge d$ {\bf do}\\
+\quad\quad $e = {\rm\ degree}(r) - d$\\
+\quad\quad $s = \frac{{\rm\ leadingCoefficient}(r)}{c}x^e$\\
+\quad\quad $q = q + s$\\
+\quad\quad $r = r - sb$\\
+{\bf endwhile}
+
+{\bf return}(q,r)
+
+{\bf end}
+
+For example, given
+\begin{verbatim}
+  p1 := (x+1) * (x+6)
+  p2 := (x+1) * (x-6)
+  gcd(p1,p2) -> x+1
+\end{verbatim}
+
 \begin{chunk}{package PGCD PolynomialGcdPackage}
 )abbrev package PGCD PolynomialGcdPackage
 ++ Author: Michael Lucks, P. Gianni, Frederic Lehobey
 ++ Date Last Updated: 17 June 1996
 ++ Description:
 ++ This package computes multivariate polynomial gcd's using
-++ a hensel lifting strategy. The contraint on the coefficient
+++ a hensel lifting strategy. The constraint on the coefficient
 ++ domain is imposed by the lifting strategy. It is assumed that
 ++ the coefficient domain has the property that almost all specializations
 ++ preserve the degree of the gcd.
@@ -139312,6 +139345,10 @@ PolynomialGcdPackage(E,OV,R,P):C == T where
     C == with
       gcd               :   (P,P)    -> P
         ++ gcd(p,q) computes the gcd of the two polynomials p and q.
+        ++
+        ++E p1:=(x+1)*(x+6)
+        ++E p2:=(x+1)*(x-6)
+        ++E gcd(p1,p2)
       gcd               :   List P   -> P
         ++ gcd(lp) computes the gcd of the list of polynomials lp.
       gcd               :   (SUPP,SUPP)    -> SUPP
@@ -139347,14 +139384,16 @@ PolynomialGcdPackage(E,OV,R,P):C == T where
       monomContent    :   (SUPP)   -> SUPP
       gcdMonom        :  (SUPP,SUPP)    -> SUPP
       gcdTermList     :    (P,P)     -> P
-      good            :  (SUPP,List OV,List List R) -> Record(upol:SUP,inval:List List R)
+      good :  (SUPP,List OV,List List R) -> Record(upol:SUP,inval:List List R)

-      chooseVal       :  (SUPP,SUPP,List OV,List List R) -> Union(UTerm,"failed")
+      chooseVal :  (SUPP,SUPP,List OV,List List R) -> Union(UTerm,"failed")
       localgcd        :  (SUPP,SUPP,List OV,List List R) -> LGcd
       notCoprime      :  (SUPP,SUPP, List NNI,List OV,List List R)   -> SUPP
-      imposelc        : (List SUP,List OV,List R,List P) -> List SUP
+      imposelc        : (List SUP,List OV,List R,List P) ->
+                          Union(List SUP, "failed")

-      lift? :(SUPP,SUPP,UTerm,List NNI,List OV) -> Union(s:SUPP,failed:"failed",notCoprime:"notCoprime")
+      lift? :(SUPP,SUPP,UTerm,List NNI,List OV) -> _
+               Union(s:SUPP,failed:"failed",notCoprime:"notCoprime")
       lift  :(SUPP,SUP,SUP,P,List OV,List NNI,List R) -> Union(SUPP,"failed")

                      ---- Local  functions ----
@@ -139363,7 +139402,8 @@ PolynomialGcdPackage(E,OV,R,P):C == T where
         (p1 exquo f) case "failed" or (p2 exquo f) case "failed"

     -- Choose the integers
-      chooseVal(p1:SUPP,p2:SUPP,lvr:List OV,ltry:List List R):Union(UTerm,"failed") ==
+      chooseVal(p1:SUPP,p2:SUPP,lvr:List OV,_
+                ltry:List List R):Union(UTerm,"failed") ==
         d1:=degree(p1)
         d2:=degree(p2)
         dd:NNI:=0$NNI
@@ -139406,7 +139446,8 @@ PolynomialGcdPackage(E,OV,R,P):C == T where
          --the new gcd has degree less
           du<dd => dd:=du

-      good(f:SUPP,lvr:List OV,ltry:List List R):Record(upol:SUP,inval:List List R) ==
+      good(f:SUPP,lvr:List OV, _
+           ltry:List List R):Record(upol:SUP,inval:List List R) ==
         nvr:NNI:=#lvr
         range:I:=1
         while true repeat
@@ -139416,18 +139457,37 @@ PolynomialGcdPackage(E,OV,R,P):C == T where
           ltry:=cons(lval,ltry)
           uf:=completeEval(f,lvr,lval)
           if degree gcd(uf,differentiate uf)=0 then return [uf,ltry]
-
-      -- impose the right lc
-      imposelc(lipol:List SUP,
-               lvar:List OV,lval:List R,leadc:List P):List SUP ==
+\end{chunk}
+
+In Gathen \cite{GG99} we find a discussion of applying the Euclidean
+algorithm to elements of a field. In a field every nonzero rational
+number is a unit. If we want to define a single element such that
+\[gcd(f,g) \in {\bf Q}[x]\] we choose a monic polynomial, that is, the
+element with a leading coefficient of 1. So
+\[abs(a/{\rm\ leadingCoefficent}(a))\] defines a normal form of $a$.
+\index{leadingCoefficient}
+\index{monic polynomial}
+\index{normal form}
+
+Gathen also notes that for polynomials we should modify the Euclidean
+algorithm so {\sl all} remainders are normalized. Without this
+constraint the remainders will have huge numerators and denominators.
+
+\begin{chunk}{package PGCD PolynomialGcdPackage}
+      -- impose the right leading condition, check for failure.
+      imposelc(lipol:List SUP, lvar:List OV, lval:List R,
+               leadc:List P): Union(List SUP, "failed") ==
         result:List SUP :=[]
         for pol in lipol for leadpol in leadc repeat
-           p1:= univariate eval(leadpol,lvar,lval) * pol
-           result:= cons((p1 exquo leadingCoefficient pol)::SUP,result)
+           p1 := univariate eval(leadpol, lvar, lval) * pol
+           p1u := p1 exquo leadingCoefficient pol
+           p1u case "failed" => return "failed"
+           result := cons(p1u::SUP, result)
         reverse result

     --Compute the gcd between not coprime polynomials
-      notCoprime(g:SUPP,p2:SUPP,ldeg:List NNI,lvar1:List OV,ltry:List List R) : SUPP ==
+      notCoprime(g:SUPP,p2:SUPP,ldeg:List NNI,_
+                 lvar1:List OV,ltry:List List R) : SUPP ==
         g1:=gcd(g,differentiate g)
         l1 := (g exquo g1)::SUPP
         lg:LGcd:=localgcd(l1,p2,lvar1,ltry)
@@ -139547,11 +139607,20 @@ PolynomialGcdPackage(E,OV,R,P):C == T where
       gcdMonom(m1:SUPP,m2:SUPP):SUPP ==
         monomial(gcd(leadingCoefficient(m1),leadingCoefficient(m2)),
                  min(degree(m1),degree(m2)))
+\end{chunk}

+Hensel's lifting lemma states that if a polynomial equation has a simple
+root modulo a prime number $p$, then this root corresponds to a unique root
+of the same equation modulo any higher power of $p$, which can be found
+by iteratively ``lifting'' the solution modulo successive powers of $p$.
+
+See Volume 10.1 for more details.

+\begin{chunk}{package PGCD PolynomialGcdPackage}
     --If there is a pol s.t. pol/gcd and gcd are coprime I can lift
-      lift?(p1:SUPP,p2:SUPP,uterm:UTerm,ldeg:List NNI,
-                     lvar:List OV) : Union(s:SUPP,failed:"failed",notCoprime:"notCoprime") ==
+      lift?(p1:SUPP,p2:SUPP,uterm:UTerm,ldeg:List NNI, _
+            lvar:List OV) : _
+              Union(s:SUPP,failed:"failed",notCoprime:"notCoprime") ==
         leadpol:Boolean:=false
         (listpol,lval):=(uterm.lpol,uterm.lint.first)
         d:=listpol.first
@@ -139584,7 +139653,9 @@ PolynomialGcdPackage(E,OV,R,P):C == T where
           else d:=(retract(eval(lgcd,lvar,lval)) * d exquo lcd)::SUP
           uf:=lcd*uf
         leadlist:=[lgcd,lcf]
-        lg:=imposelc([d,uf],lvar,lval,leadlist)
+        lgu := imposelc([d, uf], lvar, lval, leadlist)
+        lgu case "failed" => "failed"
+        lg := lgu::List(SUP)
         (pl:=lifting(f,lvar,lg,lval,leadlist,ldeg,pmod)) case "failed" =>
                "failed"
         plist := pl :: List SUPP