Opened 4 years ago

Closed 4 years ago

# polredabs does not does not always return the correct transformation map

Reported by: Owned by: mderickx major sage-8.0 number fields mderickx Maarten Derickx Vincent Delecroix Fixed upstream, but not in a stable release. d097929 d0979299e4e2b40af7723a03876b147e6c200724

### 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.

### 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)
(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:

 ​72412ac `Merge 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: ↓ 11 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:

 ​d097929 `improved polredabs doctest for trac 23259`

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

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.