Initial population.

1 files changed, 214 insertions, 0 deletions

diff --git a/src/algebra/galfactu.spad.pamphlet b/src/algebra/galfactu.spad.pamphlet
new file mode 100644
index 00000000..f7dacfe9
--- /dev/null
+++ b/src/algebra/galfactu.spad.pamphlet
@@ -0,0 +1,214 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra galfactu.spad}
+\author{Frederic Lehobey}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\section{package GALFACTU GaloisGroupFactorizationUtilities}
+<<package GALFACTU GaloisGroupFactorizationUtilities>>=
+)abbrev package GALFACTU GaloisGroupFactorizationUtilities
+++ Author: Frederic Lehobey
+++ Date Created: 30 June 1994
+++ Date Last Updated: 19 October 1995
+++ Basic Functions:
+++ Related Constructors:
+++ Also See:
+++ AMS Classifications:
+++ Keywords:
+++ References: 
+++ [1] Bernard Beauzamy, Products of polynomials and a priori estimates for
+++ coefficients in polynomial decompositions: a sharp result,
+++ J. Symbolic Computation (1992) 13, 463-472
+++ [2] David W. Boyd, Bounds for the Height of a Factor of a Polynomial in
+++ Terms of Bombieri's Norms: I. The Largest Factor,
+++ J. Symbolic Computation (1993) 16, 115-130
+++ [3] David W. Boyd, Bounds for the Height of a Factor of a Polynomial in
+++ Terms of Bombieri's Norms: II. The Smallest Factor,
+++ J. Symbolic Computation (1993) 16, 131-145
+++ [4] Maurice Mignotte, Some Useful Bounds,
+++ Computing, Suppl. 4, 259-263 (1982), Springer-Verlag
+++ [5] Donald E. Knuth, The Art of Computer Programming, Vol. 2, (Seminumerical
+++ Algorithms) 1st edition, 2nd printing, Addison-Wesley 1971, p. 397-398
+++ [6] Bernard Beauzamy, Vilmar Trevisan and Paul S. Wang, Polynomial 
+++ Factorization: Sharp Bounds, Efficient Algorithms,
+++ J. Symbolic Computation (1993) 15, 393-413
+++ [7] Augustin-Lux Cauchy, Exercices de Math\'ematiques Quatri\`eme Ann\'ee.
+++ De Bure Fr\`eres, Paris 1829 (reprinted Oeuvres, II S\'erie, Tome IX,
+++ Gauthier-Villars, Paris, 1891).
+++ Description: 
+++ \spadtype{GaloisGroupFactorizationUtilities} provides functions
+++ that will be used by the factorizer.
+
+GaloisGroupFactorizationUtilities(R,UP,F): Exports == Implementation where
+  R : Ring
+  UP : UnivariatePolynomialCategory R
+  F : Join(FloatingPointSystem,RetractableTo(R),Field,
+   TranscendentalFunctionCategory,ElementaryFunctionCategory)
+  N ==> NonNegativeInteger
+  P ==> PositiveInteger
+  Z ==> Integer
+ 
+  Exports ==> with
+    beauzamyBound: UP -> Z -- See [1]
+      ++ beauzamyBound(p) returns a bound on the larger coefficient of any
+      ++ factor of p.
+    bombieriNorm: UP -> F -- See [1]
+      ++ bombieriNorm(p) returns quadratic Bombieri's norm of p.
+    bombieriNorm: (UP,P) -> F -- See [2] and [3]
+      ++ bombieriNorm(p,n) returns the nth Bombieri's norm of p.
+    rootBound: UP -> Z -- See [4] and [5]
+      ++ rootBound(p) returns a bound on the largest norm of the complex roots
+      ++ of p.
+    singleFactorBound: (UP,N) -> Z -- See [6]
+      ++ singleFactorBound(p,r) returns a bound on the infinite norm of
+      ++ the factor of p with smallest Bombieri's norm. r is a lower bound
+      ++ for the number of factors of p. p shall be of degree higher or equal
+      ++ to 2.
+    singleFactorBound: UP -> Z -- See [6]
+      ++ singleFactorBound(p,r) returns a bound on the infinite norm of
+      ++ the factor of p with smallest Bombieri's norm. p shall be of degree
+      ++ higher or equal to 2.
+    norm: (UP,P) -> F
+      ++ norm(f,p) returns the lp norm of the polynomial f.
+    quadraticNorm: UP -> F
+      ++ quadraticNorm(f) returns the l2 norm of the polynomial f.
+    infinityNorm: UP -> F
+      ++ infinityNorm(f) returns the maximal absolute value of the coefficients
+      ++ of the polynomial f.
+    height: UP -> F
+      ++ height(p) returns the maximal absolute value of the coefficients of
+      ++ the polynomial p.
+    length: UP -> F
+      ++ length(p) returns the sum of the absolute values of the coefficients
+      ++ of the polynomial p.
+
+  Implementation ==> add
+
+    import GaloisGroupUtilities(F)
+
+    height(p:UP):F == infinityNorm(p)
+
+    length(p:UP):F == norm(p,1)
+
+    norm(f:UP,p:P):F ==
+      n : F := 0
+      for c in coefficients f repeat
+        n := n+abs(c::F)**p
+      nthRoot(n,p::N)
+
+    quadraticNorm(f:UP):F == norm(f,2)
+
+    infinityNorm(f:UP):F ==
+      n : F := 0
+      for c in coefficients f repeat
+        n := max(n,c::F)
+      n
+
+    singleFactorBound(p:UP,r:N):Z == -- See [6]
+      n : N := degree p
+      r := max(2,r)
+      n < r => error "singleFactorBound: Bad arguments."
+      nf : F := n :: F
+      num : F := nthRoot(bombieriNorm(p),r)
+      if F has Gamma: F -> F then
+        num := num*nthRoot(Gamma(nf+1$F),2*r)
+        den : F := Gamma(nf/((2*r)::F)+1$F)
+      else
+        num := num*(2::F)**(5/8+n/2)*exp(1$F/(4*nf))
+        den : F := (pi()$F*nf)**(3/8)
+      safeFloor( num/den )
+
+    singleFactorBound(p:UP):Z == singleFactorBound(p,2) -- See [6]
+
+    rootBound(p:UP):Z == -- See [4] and [5]
+      n := degree p
+      zero? n => 0
+      lc := abs(leadingCoefficient(p)::F)
+      b1 : F := 0 -- Mignotte
+      b2 : F := 0 -- Knuth
+      b3 : F := 0 -- Zassenhaus in [5]
+      b4 : F := 0 -- Cauchy in [7]
+      c : F := 0
+      cl : F := 0
+      for i in 1..n repeat
+        c := abs(coefficient(p,(n-i)::N)::F)
+        b1 := max(b1,c)
+        cl := c/lc
+        b2 := max(b2,nthRoot(cl,i))
+        b3 := max(b3,nthRoot(cl/pascalTriangle(n,i),i))
+        b4 := max(b4,nthRoot(n*cl,i))
+      min(1+safeCeiling(b1/lc),min(safeCeiling(2*b2),min(safeCeiling(b3/
+       (nthRoot(2::F,n)-1)),safeCeiling(b4))))
+
+    beauzamyBound(f:UP):Z == -- See [1]
+      d := degree f
+      zero? d => safeFloor bombieriNorm f
+      safeFloor( (bombieriNorm(f)*(3::F)**(3/4+d/2))/
+       (2*sqrt(pi()$F*(d::F))) )
+
+    bombieriNorm(f:UP,p:P):F == -- See [2] and [3]
+      d := degree f
+      b := abs(coefficient(f,0)::F)
+      if zero? d then return b
+       else b := b**p
+      b := b+abs(leadingCoefficient(f)::F)**p
+      dd := (d-1) quo 2
+      for i in 1..dd repeat
+        b := b+(abs(coefficient(f,i)::F)**p+abs(coefficient(f,(d-i)::N)::F)**p)
+         /pascalTriangle(d,i)
+      if even? d then
+        dd := dd+1
+        b := b+abs(coefficient(f, dd::N)::F)**p/pascalTriangle(d,dd)
+      nthRoot(b,p::N)
+
+    bombieriNorm(f:UP):F == bombieriNorm(f,2) -- See [1]
+
+@
+\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>>
+
+<<package GALFACTU GaloisGroupFactorizationUtilities>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}