polredabs does not does not always return the correct transformation map

[koffie]

In this example I ask pari to polredabs a polynomial f and also return a transformation map h such that h(x) is a root of f in QQ[x]/g.

sage: R.<x> = QQ[]
....: f = x^12 + x^7 - 1/5*x^6 - 3*x^5 + 13/5*x^4 + 11/5*x^3 + 2/5*x^2 + 2/5*x + 1/5
....: gh = pari(f).polredabs(1)
....: print "gh", gh
....: g,h = gh[0].sage(locals={'x':x}),gh[1].lift().sage(locals={'x':x})
....: print "g",g
....: print "h",h
....: print "f(h)mod g", f(h)%g
....: 
gh [x^12 - 2*x^11 + 2*x^10 - 11*x^9 + 13*x^8 + 15*x^7 - x^6 - 5*x^5 + 5, Mod(x^11 - 2*x^10 + 2*x^9 - 11*x^8 + 13*x^7 + 15*x^6 - x^5 - 5*x^4, x^12 - 2*x^11 + 2*x^10 - 11*x^9 + 13*x^8 + 15*x^7 - x^6 - 5*x^5 + 5)]
g x^12 - 2*x^11 + 2*x^10 - 11*x^9 + 13*x^8 + 15*x^7 - x^6 - 5*x^5 + 5
h x^11 - 2*x^10 + 2*x^9 - 11*x^8 + 13*x^7 + 15*x^6 - x^5 - 5*x^4
f(h)mod g -195293748/5*x^11 + 244181236/5*x^10 - 634884076/5*x^9 + 3564400908/5*x^8 - 2539683564/5*x^7 + 166278100*x^6 - 14647209952/5*x^5 - 1269578400*x^4 + 4072182580*x^3 + 3017386300*x^2 - 1562284000*x - 7518315624/5

The above shows that f,g and h don't satisfy the promised relation.
Changing the leading term of f from 12 to 11 does give something correct.

sage: f = x^11 + x^7 - 1/5*x^6 - 3*x^5 + 13/5*x^4 + 11/5*x^3 + 2/5*x^2 + 2/5*x + 1/5
....: gh = pari(f).polredabs(1)
....: print "gh", gh
....: g,h = gh[0].sage(locals={'x':x}),gh[1].lift().sage(locals={'x':x})
....: print "g",g
....: print "h",h
....: print "f(h)mod g", f(h)%g
....: 
gh [x^11 - 2*x^10 + 2*x^9 - 11*x^8 + 13*x^7 + 15*x^6 - x^5 - 5*x^4 - 5, Mod(-1/5*x^10 + 2/5*x^9 - 2/5*x^8 + 11/5*x^7 - 13/5*x^6 - 3*x^5 + 1/5*x^4 + x^3, x^11 - 2*x^10 + 2*x^9 - 11*x^8 + 13*x^7 + 15*x^6 - x^5 - 5*x^4 - 5)]
g x^11 - 2*x^10 + 2*x^9 - 11*x^8 + 13*x^7 + 15*x^6 - x^5 - 5*x^4 - 5
h -1/5*x^10 + 2/5*x^9 - 2/5*x^8 + 11/5*x^7 - 13/5*x^6 - 3*x^5 + 1/5*x^4 + x^3
f(h)mod g 0

This error was produced on SageMath version 7.6 on OS X 10.12.

Upstream: Fixed upstream, but not in a stable release.

CC: @koffie

Component: number fields

Author: Maarten Derickx

Branch/Commit: d097929

Reviewer: Vincent Delecroix

Issue created by migration from https://trac.sagemath.org/ticket/23259

[koffie]

comment:1

The following shows that the error already occurs in pari.

                                                   GP/PARI CALCULATOR Version 2.9.1 (released)
                                           i386 running darwin (x86-64/GMP-5.1.3 kernel) 64-bit version
                                                  compiled: Apr  4 2017, gcc version 5.4.0 (GCC)
                                                             threading engine: single
                                                  (readline v6.3 enabled, extended help enabled)

                                                      Copyright (C) 2000-2016 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?15 for how to get moral (and possibly technical) support.

parisize = 8000000, primelimit = 500000
? f = x^12 + x^7 - 1/5*x^6 - 3*x^5 + 13/5*x^4 + 11/5*x^3 + 2/5*x^2 + 2/5*x + 1/5;
? gh = polredabs(f,1);
? g=gh[1];
? h=gh[2];
? subst(f,x,h)
%5 = Mod(-195293748/5*x^11 + 244181236/5*x^10 - 634884076/5*x^9 + 3564400908/5*x^8 - 2539683564/5*x^7 + 166278100*x^6 - 14647209952/5*x^5 - 1269578400*x^4 + 4072182580*x^3 + 3017386300*x^2 - 1562284000*x - 7518315624/5, x^12 - 2*x^11 + 2*x^10 - 11*x^9 + 13*x^8 + 15*x^7 - x^6 - 5*x^5 + 5)
? f = x^11 + x^7 - 1/5*x^6 - 3*x^5 + 13/5*x^4 + 11/5*x^3 + 2/5*x^2 + 2/5*x + 1/5;
? gh = polredabs(f,1);
? g=gh[1];
? h=gh[2];
? subst(f,x,h)
%10 = Mod(0, x^11 - 2*x^10 + 2*x^9 - 11*x^8 + 13*x^7 + 15*x^6 - x^5 - 5*x^4 - 5)

[koffie]

Changed upstream from Not yet reported upstream; Will do shortly. to Reported upstream. No feedback yet.

[koffie]

comment:3

Submitted at: https://pari.math.u-bordeaux.fr/archives/pari-dev-1706/msg00006.html

[koffie]

Changed upstream from Reported upstream. No feedback yet. to Fixed upstream, but not in a stable release.

[koffie]

comment:4

This has been fixed upstream in commit 1420fa40a which can be found at: https://pari.math.u-bordeaux.fr/cgi-bin/gitweb.cgi?p=pari.git;a=commit;h=1420fa40a7d7b43cf2d21c530a0a1d394bac245d

[koffie]

Commit: 4ac0282

[koffie]

Branch: u/mderickx/23259

[jdemeyer]

comment:6

Merge conflict (the patch needs to be based on 8.0.beta11).

[jdemeyer]

Author: Maarten Derickx

[sagetrac-git]

Changed commit from 4ac0282 to 72412ac

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

72412ac

Merge branch 'u/mderickx/23259' of git://trac.sagemath.org/sage into develop

[videlec]

comment:9

This line is horrible

    g,h = gh[0].sage(locals={'x':x}),gh[1].lift().sage(locals={'x':x})

[sagetrac-git]

Changed commit from 72412ac to d097929

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

d097929

improved polredabs doctest for trac 23259

[koffie]

comment:11

Replying to @videlec:

This line is horrible

    g,h = gh[0].sage(locals={'x':x}),gh[1].lift().sage(locals={'x':x})

I changed the doctest to something more elegant. Is it better now?

[videlec]

Reviewer: Vincent Delecroix

[videlec]

comment:12

Indeed. Thanks for this fix!

[vbraun]

Changed branch from u/mderickx/23259 to d097929