Opened 3 years ago

Closed 3 years ago

Last modified 3 years ago

#25803 closed defect (duplicate)

problem factoring polynomial over number field

Reported by: wuthrich Owned by:
Priority: minor Milestone: sage-duplicate/invalid/wontfix
Component: factorization Keywords: pari, polynomial, factorization
Cc: cremona, jdemeyer Merged in:
Authors: Reviewers:
Report Upstream: Reported upstream. No feedback yet. Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by wuthrich)

sage: E = EllipticCurve([1,0])
sage: K.<t> = E.division_field(5)
sage: EK = E.base_extend(K)
sage: EK.isogenies_prime_degree(5)

goes boom and ends with

PariError: inconsistent concatenation t_VEC (2 elts) , t_COL (2 elts)

with the curve E = EllipticCurve("11a1") it works fine.

Change History (11)

comment:1 Changed 3 years ago by cremona

Tracking this down, it is not in the isogeny code as such:

sage: E = EllipticCurve([1,0])
sage: K.<t> = E.division_field(5)
sage: EK = E.base_extend(K)
sage: E2 = EK.short_weierstrass_model()
sage: EK.isomorphism_to(E2)

which I wrote even longer ago (10 years?). Something has gone wrong wit hthe interface to pari's factorization of polynomials over number fields.

comment:2 Changed 3 years ago by cremona

Here is code which triggers the problem which has nothing to do with elliptic curves:

x = polygen(QQ)
pol = x^32 - 40*x^31 + 2200*x^30 - 70000*x^29 + 1926760*x^28 - 47410000*x^27 + 893166000*x^26 - 15151540000*x^25 + 218980686600*x^24 - 2222863736000*x^23 + 16167594760000*x^22 - 35393484200000*x^21 - 1983124979264000*x^20 + 31818541845880000*x^19 + 32676134745200000*x^18 - 887920368940000000*x^17 - 20567097546680290000*x^16 + 428473384974975200000*x^15 - 2816072502532216000000*x^14 - 7788706298586140000000*x^13 + 252808056677292000000000*x^12 - 1002263969671718500000000*x^11 + 2230707722334140000000000*x^10 - 54420521465975000000000000*x^9 + 523500114521163406250000000*x^8 - 973463314441488125000000000*x^7 + 2944910228721053125000000000*x^6 - 25691035501284500000000000000*x^5 + 9541139003641484375000000000*x^4 + 203162239445609375000000000000*x^3 + 791581188305121093750000000000*x^2 + 187244754882460937500000000000*x + 215978078004907226562500000000
K.<a> = NumberField(pol)
y = polygen(K, 'y')
(y^4-1).roots()

comment:3 Changed 3 years ago by cremona

Note that

(y^2+1).roots()

returns two roots with no problem.

comment:4 Changed 3 years ago by wuthrich

  • Component changed from elliptic curves to factorization
  • Description modified (diff)
  • Keywords pari polynomial factorization added; isogeny removed
  • Report Upstream changed from N/A to Not yet reported upstream; Will do shortly.
  • Summary changed from fails to create isogenies on a cm curve over a number field to problem factoring polynomial over number field

Thanks for chasing. I went a bit further and found that this is likely a bug in pari:

? f = y^32 - 40*y^31 + 2200*y^30 - 70000*y^29 + 1926760*y^28 - 47410000*y^27 + 893166000*y^26 - 15151540000*y^25 + 218980686600*y^24 - 2222863736000*y^23 + 16167594760000*y^22 - 35393484200000*y^21 - 1983124979264000*y^20 + 31818541845880000*y^19 + 32676134745200000*y^18 - 887920368940000000*y^17 - 20567097546680290000*y^16 + 428473384974975200000*y^15 - 2816072502532216000000*y^14 - 7788706298586140000000*y^13 + 252808056677292000000000*y^12 - 1002263969671718500000000*y^11 + 2230707722334140000000000*y^10 - 54420521465975000000000000*y^9 + 523500114521163406250000000*y^8 - 973463314441488125000000000*y^7 + 2944910228721053125000000000*y^6 - 25691035501284500000000000000*y^5 + 9541139003641484375000000000*y^4 + 203162239445609375000000000000*y^3 + 791581188305121093750000000000*y^2 + 187244754882460937500000000000*y + 215978078004907226562500000000
%1 = y^32 - 40*y^31 + 2200*y^30 - 70000*y^29 + 1926760*y^28 - 47410000*y^27 + 893166000*y^26 - 15151540000*y^25 + 218980686600*y^24 - 2222863736000*y^23 + 16167594760000*y^22 - 35393484200000*y^21 - 1983124979264000*y^20 + 31818541845880000*y^19 + 32676134745200000*y^18 - 887920368940000000*y^17 - 20567097546680290000*y^16 + 428473384974975200000*y^15 - 2816072502532216000000*y^14 - 7788706298586140000000*y^13 + 252808056677292000000000*y^12 - 1002263969671718500000000*y^11 + 2230707722334140000000000*y^10 - 54420521465975000000000000*y^9 + 523500114521163406250000000*y^8 - 973463314441488125000000000*y^7 + 2944910228721053125000000000*y^6 - 25691035501284500000000000000*y^5 + 9541139003641484375000000000*y^4 + 203162239445609375000000000000*y^3 + 791581188305121093750000000000*y^2 + 187244754882460937500000000000*y + 215978078004907226562500000000
? g = x^2-1
%2 = x^2 - 1
? nffactor(f,g)
%3 = 
[x - 1 1]

[x + 1 1]

? g = x^4-1
%4 = x^4 - 1
? nffactor(f,g)
  ***   at top-level: nffactor(f,g)
  ***                 ^-------------
  *** nffactor: inconsistent concatenation t_VEC (2 elts) , t_COL (2 elts).

is the cause of this.

comment:5 Changed 3 years ago by cremona

  • Authors set to jdemeyer

comment:6 Changed 3 years ago by cremona

  • Authors jdemeyer deleted
  • Cc jdemeyer added

comment:7 Changed 3 years ago by wuthrich

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

comment:8 follow-up: Changed 3 years ago by jdemeyer

  • Milestone changed from sage-8.3 to sage-duplicate/invalid/wontfix
  • Resolution set to duplicate
  • Status changed from new to closed

Fixed by #25567

comment:9 in reply to: ↑ 8 Changed 3 years ago by cremona

Replying to jdemeyer:

Fixed by #25567

I believe you, despite #25567's current status "needs work".

comment:10 Changed 3 years ago by jdemeyer

To clarify: the updated PARI/GP on #25567 builds and I checked (within GP, not Sage) that the problem is fixed.

comment:11 Changed 3 years ago by cremona

Thanks.

Note: See TracTickets for help on using tickets.