Opened 4 years ago

Closed 4 years ago

#23259 closed defect (fixed)

polredabs does not does not always return the correct transformation map

Reported by: mderickx Owned by:
Priority: major Milestone: sage-8.0
Component: number fields Keywords:
Cc: mderickx Merged in:
Authors: Maarten Derickx Reviewers: Vincent Delecroix
Report Upstream: Fixed upstream, but not in a stable release. Work issues:
Branch: d097929 (Commits, GitHub, GitLab) Commit: d0979299e4e2b40af7723a03876b147e6c200724
Dependencies: Stopgaps:

Status badges

Description

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.

Change History (13)

comment:1 Changed 4 years ago by mderickx

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)

comment:2 Changed 4 years ago by mderickx

  • Report Upstream changed from Not yet reported upstream; Will do shortly. to Reported upstream. No feedback yet.

comment:4 Changed 4 years ago by mderickx

  • Report Upstream changed from Reported upstream. No feedback yet. to Fixed upstream, but not in a stable release.

comment:5 Changed 4 years ago by mderickx

  • Branch set to u/mderickx/23259
  • Commit set to 4ac02825b1c290c2ae77137a6d3783b5eba622ba
  • Status changed from new to needs_review

comment:6 Changed 4 years ago by jdemeyer

  • Authors set to Maarten Derickx
  • Status changed from needs_review to needs_work

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

comment:7 Changed 4 years ago by git

  • Commit changed from 4ac02825b1c290c2ae77137a6d3783b5eba622ba to 72412ac25c54b3147df00c5ca3888ca4d97be801

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

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

comment:8 Changed 4 years ago by mderickx

  • Status changed from needs_work to needs_review

comment:9 follow-up: Changed 4 years ago by vdelecroix

This line is horrible

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

comment:10 Changed 4 years ago by git

  • Commit changed from 72412ac25c54b3147df00c5ca3888ca4d97be801 to d0979299e4e2b40af7723a03876b147e6c200724

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

d097929improved polredabs doctest for trac 23259

comment:11 in reply to: ↑ 9 Changed 4 years ago by mderickx

Replying to vdelecroix:

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?

comment:12 Changed 4 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to positive_review

Indeed. Thanks for this fix!

comment:13 Changed 4 years ago by vbraun

  • Branch changed from u/mderickx/23259 to d0979299e4e2b40af7723a03876b147e6c200724
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.