This mail contains a bugfix for a dangerous problem in GAP 3.4.3.
*You should apply this bugfix as soon as possible.*
The problem is in 'RationalsPolynomialsOps.Factors', and might cause it
to return reducible factors.
ACKNOWLEDGEMENT
We thank Willem A. de Graaf (Technische Universiteit Eindhoven) for
bringing this problem to our attention in a GAP forum mail of 1996/09/18.
VERSION
GAP/lib 3.4.3.0
PRIORITY
The problem is a dangerous problem, because it may cause a computation
to produce incorrect results without a warning. This the bugfix has
high priority, and we recommend that you apply it as soon as possible.
HOW TO APPLY
Go to the GAP directory (the directory with the 'lib/' subdirectory),
name this mail 'fix25lib.dif', and issue the command:patch -p0 < fix25lib.difIf 'patch' writes "I can't seem to find a patch in there" try 'patch -v'.
If 'patch -v' gives an error message or reports a version older than 2.1,
get 2.1 from 'ftp://FTP.Math.RWTH-Aachen.DE/pub/gap/utils/patch2_1.zoo'.This fix changes only the library.
Thus you need not recompile the GAP kernel.
DESCRIPTION
Polynomials with integer roots might get factored erraneously,
that is 'Factors' might return reducible factors.
CORRECT BEHAVIOUR
gap> y := Indeterminate( Rationals );; y.name := "y";; gap> f := y^33 > - 398550 * y^31 > + 66186201873 * y^29 > - 5971817014857100 * y^27 > + 319879423075055974416 * y^25 > - 10453569133068665704152000 * y^23 > + 207491014558959631527689015040 * y^21 > - 2448295340120142096293200047744000 * y^19 > + 16690739160259700445725003902608322560 * y^17 > - 62701173265160849595209547823580350464000 * y^15 > + 118869582948995926691687807245961904820322304 * y^13 > - 95752347343101572852967993673317241915126579200 * y^11 > + 22338679946180069821565185491251863734781426532352 * y^9 > - 611471306080989784227382973634662004989868009062400 * y^7 > + 5410092199316503850833490994152109788519901066952704 * y^5 > - 16075861728797055597248567344887907079321523585024000 * y^3 > + 11254997789155806098371908864638669722435410984960000 * y;; gap> Factors( f ); [ y - 324, y - 270, y - 252, y - 234, y - 216, y - 162, y - 108, y - 90, y - 72, y - 54, y - 36, y - 18, y - 4, y - 3, y - 2, y - 1, y + 1, y + 2, y + 3, y + 4, y + 18, y + 36, y + 54, y + 72, y + 90, y + 108, y + 162, y + 216, y + 234, y + 252, y + 270, y + 324, y ]
COMMENT
The implemented Hensel lifting process does not work correctly if 0 is a
root of the polynomial that is to be factored. As the factoring routine
applies an initial Tschirnhaus transform to get the norm small, this
might also affect polynomials with small absolute value integer roots.
The remedy is to treat the case of root 0 before starting the Hensel
lift. This had been introduced already in the algebraic factoring code,
thus a similar fix there is not needed.
DIFFS
Prereq: 3.31.1.2
--- lib/polyrat.g Thu Dec 21 15:30:36 1995
+++ lib/polyrat.g Mon Sep 23 12:28:24 1996
@@ -3,14 +3,17 @@
#A polyrat.g GAP library Frank Celler
#A & Alexander Hulpke
##
-#A @(#)$Id: 1.html,v 1.2 2004/04/21 15:04:29 felsch Exp $
+#A @(#)$Id: 1.html,v 1.2 2004/04/21 15:04:29 felsch Exp $
##
#Y Copyright 1990-1992, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany
##
## This file contains functions for polynomials over the Rationals.
##
#H $Log: 1.html,v $
#H Revision 1.2 2004/04/21 15:04:29 felsch
#H Corrected links in the Forum Archive pages. VF
#H
#H Revision 1.1.1.1 2004/04/20 13:39:35 felsch
#H The final GAP-Forum archive until 2003.
#H
#H Revision 1.4 2003/06/12 19:20:34 gap
#H Further update. AH
#H
#H Revision 1.3 1997/08/15 11:19:38 gap
#H New forum setup. AH
#H
#H Revision 1.2 1997/04/24 15:33:16 gap
#H These files were replaced by the versions in WWW. The content is basically the
#H same but the formatting has been much more friendly towards the HTML-Converter.
#H AH
#H
#H Revision 1.1 1996/10/30 13:07:07 gap
#H added forum archive and translation files.
#H
-#H Revision 3.31.1.2 1994/09/19 08:28:11 ahulpke
+#H Revision 3.31.1.3 1996/09/23 10:28:01 ahulpke
+#H Fixed factoring polynomials with linear factors
+#H
+#H Revision 3.31.1.2 1994/09/19 08:28:11 ahulpke
#H fixed factorization of square part
#H
#H Revision 3.31.1.1 1994/08/02 10:11:48 ahulpke
@@ -1621,7 +1624,16 @@
InfoPoly2( "#I <f> is a linear power\n" );
s := [ q ];
else
- s := R.operations.FactorsSquarefree( R, q );
+
+ # treat zeroes
+ if q.valuation>0 then
+ s:=[X(q.baseRing)];
+ q:=q/(X(q.baseRing));
+ else
+ s:=[];
+ fi;
+ s:=Concatenation(s,R.operations.FactorsSquarefree( R, q ));
+
fi;
# find factors of <g>
Prereq: 3.1
--- lib/polystff.g Thu Dec 21 15:30:36 1995
+++ lib/polystff.g Mon Sep 23 12:28:38 1996
@@ -2,7 +2,7 @@
##
#A polystff.g GAP library Alexander Hulpke
##
-#A @(#)$Id: 1.html,v 1.2 2004/04/21 15:04:29 felsch Exp $
+#A @(#)$Id: 1.html,v 1.2 2004/04/21 15:04:29 felsch Exp $
##
#Y Copyright (C) 1994, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany
##
@@ -11,7 +11,10 @@
## fit better, however, in other files.
##
#H $Log: 1.html,v $
#H Revision 1.2 2004/04/21 15:04:29 felsch
#H Corrected links in the Forum Archive pages. VF
#H
#H Revision 1.1.1.1 2004/04/20 13:39:35 felsch
#H The final GAP-Forum archive until 2003.
#H
#H Revision 1.4 2003/06/12 19:20:34 gap
#H Further update. AH
#H
#H Revision 1.3 1997/08/15 11:19:38 gap
#H New forum setup. AH
#H
#H Revision 1.2 1997/04/24 15:33:16 gap
#H These files were replaced by the versions in WWW. The content is basically the
#H same but the formatting has been much more friendly towards the HTML-Converter.
#H AH
#H
#H Revision 1.1 1996/10/30 13:07:07 gap
#H added forum archive and translation files.
#H
-#H Revision 3.1 1994/06/03 10:49:44 ahulpke
+#H Revision 3.1.1.1 1996/09/23 10:28:35 ahulpke
+#H Fixed factoring polynomials with linear factors
+#H
+#H Revision 3.1 1994/06/03 10:49:44 ahulpke
#H initial revision under RCS
#H
##
@@ -756,7 +759,7 @@
q:=[];
n:=Length(g.coefficients);
m:=Length(f.coefficients)-n;
- f:=ShallowCopy(f.coefficients);
+ f:=ShallowCopy(ShiftedCoeffs(f.coefficients,f.valuation));
if IsField(R) then
for i in [0..m] do
c:=f[(m-i+n)]/g.coefficients[n];
END OF fix25lib.dif ________________________________________________________