#1359 a polynomial that puts factor() into an infinite loop.

[Satoshi Adachi]

Dear Developers of Maxima,

I met a polynomial that puts factor() into an infinite loop
if subres is used as the gcd algorithm.

Please look and see the following log:
------------------------------------------------------------------------------

\[wisdom3:~/work/283:1\] adachi% cat infinite\_loop.maxima 
/\*
\*   A polynomial that puts factor\(\) into an infinite loop
\*   if subres is used as the gcd algorithm.
\*   If spmod is used as the gcd algorithm,
\*   this polynomial is factorized normally by factor\(\).
\*/

display2d:false;

gcd:subres;

X:\(- 64\*l^3  - 240\*l^2  - 284\*l - 105 \)\*n^4
\+ \(128\*l^4  + 672\*l^3  + 1288\*l^2  + 1062\*l + 315 \)\*n^3
\+ \(- 96\*l^5  - 696\*l^4  - 1948\*l^3  - 2631\*l^2  - 1714\*l - 430 \)\*n^2
\+ \(64\*l^6  + 528\*l^5  + 1792\*l^4  + 3192\*l^3 + 3137\*l^2  + 1608\*l + 335 \)\*n
\- 32\*l^7  - 264\*l^6  - 944\*l^5 - 1894\*l^4  - 2294\*l^3  - 1669\*l^2
\- 672\*l - 115;

X:expand\(X\);

Y:factor\(X\);

difference:expand\(X-Y\);
\[wisdom3:~/work/283:2\] adachi% maxima -b infinite\_loop.maxima
Maxima 5.14.0cvs http://maxima.sourceforge.net
Using Lisp GNU Common Lisp \(GCL\) GCL 2.6.7 \(aka GCL\)
Distributed under the GNU Public License. See the file COPYING.
Dedicated to the memory of William Schelter.
The function bug\_report\(\) provides bug reporting information.
\(%i1\)                     batch\(infinite\_loop.maxima\)

batching \#p/Volumes/HFS+2/home/adachi/work/283/infinite\_loop.maxima
\(%i2\)                          display2d : false
\(%o2\) false
\(%i3\) gcd:subres
\(%o3\) subres
\(%i4\) X:-115-672\*l-1669\*l^2-2294\*l^3-1894\*l^4-944\*l^5-264\*l^6-32\*l^7
+\(335+1608\*l+3137\*l^2+3192\*l^3+1792\*l^4+528\*l^5+64\*l^6\)\*n
+\(-430-1714\*l-2631\*l^2-1948\*l^3-696\*l^4-96\*l^5\)\*n^2
+\(315+1062\*l+1288\*l^2+672\*l^3+128\*l^4\)\*n^3
+\(-105-284\*l-240\*l^2-64\*l^3\)\*n^4
\(%o4\) \(-64\*l^3-240\*l^2-284\*l-105\)\*n^4+\(128\*l^4+672\*l^3+1288\*l^2+1062\*l+315\)
\*n^3
+\(-96\*l^5-696\*l^4-1948\*l^3-2631\*l^2
-1714\*l-430\)
\*n^2
+\(64\*l^6+528\*l^5+1792\*l^4+3192\*l^3
+3137\*l^2+1608\*l+335\)
\*n-32\*l^7-264\*l^6-944\*l^5-1894\*l^4
-2294\*l^3-1669\*l^2-672\*l-115
\(%i5\) X:expand\(X\)
\(%o5\) -64\*l^3\*n^4-240\*l^2\*n^4-284\*l\*n^4-105\*n^4+128\*l^4\*n^3+672\*l^3\*n^3
+1288\*l^2\*n^3+1062\*l\*n^3+315\*n^3-96\*l^5\*n^2-696\*l^4\*n^2
-1948\*l^3\*n^2-2631\*l^2\*n^2-1714\*l\*n^2-430\*n^2+64\*l^6\*n
+528\*l^5\*n+1792\*l^4\*n+3192\*l^3\*n+3137\*l^2\*n+1608\*l\*n+335\*n
-32\*l^7-264\*l^6-944\*l^5-1894\*l^4-2294\*l^3-1669\*l^2-672\*l-115
\(%i6\) Y:factor\(X\)
^CMaxima encountered a Lisp error:

Console interrupt.

-------------------------------------------------------------------------------
Here, I have to terminate the program by a console interrupt.
(I extracted the above polynomial from an experence that my own library which
implements Zeilberger's algorithm did not return. I had waited for one day before
judging my program fell into an infinite loop.)

If spmod is used as the gcd algorithm (this is the default now),
the above polynomial causes no problem as follows:

\-------------------------------------------------------------------------------
\[wisdom3:~/work/283:3\] adachi% cat OK.maxima 
/\*
\*   A polynomial that puts factor\(\) into an infinite loop
\*   if subres is used as the gcd algorithm.
\*   If spmod is used as the gcd algorithm,
\*   this polynomial is factorized normally by factor\(\).
\*/

display2d:false;

gcd:spmod;

X:\(- 64\*l^3  - 240\*l^2  - 284\*l - 105 \)\*n^4
\+ \(128\*l^4  + 672\*l^3  + 1288\*l^2  + 1062\*l + 315 \)\*n^3
\+ \(- 96\*l^5  - 696\*l^4  - 1948\*l^3  - 2631\*l^2  - 1714\*l - 430 \)\*n^2
\+ \(64\*l^6  + 528\*l^5  + 1792\*l^4  + 3192\*l^3 + 3137\*l^2  + 1608\*l + 335 \)\*n
\- 32\*l^7  - 264\*l^6  - 944\*l^5 - 1894\*l^4  - 2294\*l^3  - 1669\*l^2
\- 672\*l - 115;

X:expand\(X\);

Y:factor\(X\);

difference:expand\(X-Y\);
\[wisdom3:~/work/283:4\] adachi% maxima -b OK.maxima
Maxima 5.14.0cvs http://maxima.sourceforge.net
Using Lisp GNU Common Lisp \(GCL\) GCL 2.6.7 \(aka GCL\)
Distributed under the GNU Public License. See the file COPYING.
Dedicated to the memory of William Schelter.
The function bug\_report\(\) provides bug reporting information.
\(%i1\)                          batch\(OK.maxima\)

batching \#p/Volumes/HFS+2/home/adachi/work/283/OK.maxima
\(%i2\)                          display2d : false
\(%o2\) false
\(%i3\) gcd:spmod
\(%o3\) spmod
\(%i4\) X:-115-672\*l-1669\*l^2-2294\*l^3-1894\*l^4-944\*l^5-264\*l^6-32\*l^7
+\(335+1608\*l+3137\*l^2+3192\*l^3+1792\*l^4+528\*l^5+64\*l^6\)\*n
+\(-430-1714\*l-2631\*l^2-1948\*l^3-696\*l^4-96\*l^5\)\*n^2
+\(315+1062\*l+1288\*l^2+672\*l^3+128\*l^4\)\*n^3
+\(-105-284\*l-240\*l^2-64\*l^3\)\*n^4
\(%o4\) \(-64\*l^3-240\*l^2-284\*l-105\)\*n^4+\(128\*l^4+672\*l^3+1288\*l^2+1062\*l+315\)
\*n^3
+\(-96\*l^5-696\*l^4-1948\*l^3-2631\*l^2
-1714\*l-430\)
\*n^2
+\(64\*l^6+528\*l^5+1792\*l^4+3192\*l^3
+3137\*l^2+1608\*l+335\)
\*n-32\*l^7-264\*l^6-944\*l^5-1894\*l^4
-2294\*l^3-1669\*l^2-672\*l-115
\(%i5\) X:expand\(X\)
\(%o5\) -64\*l^3\*n^4-240\*l^2\*n^4-284\*l\*n^4-105\*n^4+128\*l^4\*n^3+672\*l^3\*n^3
+1288\*l^2\*n^3+1062\*l\*n^3+315\*n^3-96\*l^5\*n^2-696\*l^4\*n^2
-1948\*l^3\*n^2-2631\*l^2\*n^2-1714\*l\*n^2-430\*n^2+64\*l^6\*n
+528\*l^5\*n+1792\*l^4\*n+3192\*l^3\*n+3137\*l^2\*n+1608\*l\*n+335\*n
-32\*l^7-264\*l^6-944\*l^5-1894\*l^4-2294\*l^3-1669\*l^2-672\*l-115
\(%i6\) Y:factor\(X\)
\(%o6\) -\(4\*l+5\)\*\(n-l-1\)^2
\*\(16\*l^2\*n^2+40\*l\*n^2+21\*n^2-16\*l^2\*n-40\*l\*n-21\*n+8\*l^4+40\*l^3
+78\*l^2+70\*l+23\)
\(%i7\) difference:expand\(X-Y\)
\(%o7\) 0

-------------------------------------------------------------------------------
This computation reuires just several seconds on my iBook.

Acoordingly, the problem which I am reporting in this email seems to be
related with the algorithm subres.

I know that subres is not anymore the default gcd algorithm
but spmod is now the the default gcd algorithm.
However, if spmod is used as the gcd algorithm,
several my programs written in maxima behave incorrectly
(I have alrealy reported it).
So, I am still using subres to run my programs.

In the past, the developer of maxima suggested that the default gcd
algorithm would be switched back to subres again in future.
If it is so, please fix the bug of subres which is reported here.

Thank you very much for developing maxima.

Sincerely yours,
Satoshi Adachi

[Dan Gildea]

Logged In: YES
user_id=1797506
Originator: NO

Fixed in rat3c.lisp rev 1.19.

(%i5) gcd:subres;
(%o5) subres
(%i6) X:(- 64*l^3 - 240*l^2 - 284*l - 105 )*n^4
+ (128*l^4 + 672*l^3 + 1288*l^2 + 1062*l + 315 )*n^3
+ (- 96*l^5 - 696*l^4 - 1948*l^3 - 2631*l^2 - 1714*l - 430 )*n^2
+ (64*l^6 + 528*l^5 + 1792*l^4 + 3192*l^3 + 3137*l^2 + 1608*l + 335
)*n
- 32*l^7 - 264*l^6 - 944*l^5 - 1894*l^4 - 2294*l^3 - 1669*l^2
- 672*l - 115;
(%o6) (-64*l^3-240*l^2-284*l-105)*n^4+(128*l^4+672*l^3+1288*l^2+1062*l+315)
*n^3
+(-96*l^5-696*l^4-1948*l^3-2631*l^2
-1714*l-430)
*n^2
+(64*l^6+528*l^5+1792*l^4+3192*l^3
+3137*l^2+1608*l+335)
*n-32*l^7-264*l^6-944*l^5-1894*l^4
-2294*l^3-1669*l^2-672*l-115
(%i7) X:expand(X);
(%o7) -64*l^3*n^4-240*l^2*n^4-284*l*n^4-105*n^4+128*l^4*n^3+672*l^3*n^3
+1288*l^2*n^3+1062*l*n^3+315*n^3-96*l^5*n^2-696*l^4*n^2
-1948*l^3*n^2-2631*l^2*n^2-1714*l*n^2-430*n^2+64*l^6*n
+528*l^5*n+1792*l^4*n+3192*l^3*n+3137*l^2*n+1608*l*n+335*n
-32*l^7-264*l^6-944*l^5-1894*l^4-2294*l^3-1669*l^2-672*l-115
(%i8) Y:factor(X);
(%o8) -(4*l+5)*(n-l-1)^2
*(16*l^2*n^2+40*l*n^2+21*n^2-16*l^2*n-40*l*n-21*n+8*l^4+40*l^3
+78*l^2+70*l+23)