Opened 11 years ago

Closed 11 years ago

# factor returns a reducible factor,

Reported by: Owned by: syazdani cremona critical sage-duplicate/invalid/wontfix factorization number field pari wuthrich, was N/A

Here is a result that confuses me (appologies for not having a simpler example for this):

```sage: E = EllipticCurve('1728z');
sage: Et = E.mod5family();
sage: f=Et.discriminant().numerator().factor()[0][0];
sage: K.<alpha> = NumberField(f);
sage: f.change_ring(K).factor()[1][0].is_irreducible()
False
```

Here f turns out to be a degree 12 polynomial, and when you factor it over K, you get a linear factor and a degree 11 factor. However, degree 11 factor in this case is not irreducible. In fact, if you continue with

```sage: g = f.change_ring(K).factor()[1][0];
sage: g.factor()
```

you get a linear factor and a degree 10 factor, where both are irreducible.

I fear it is no good asking for an upstream fix, since they (pari) have already fixed it but we are not using the fixed version. See #7097 for more details.

### comment:1 Changed 11 years ago by was

Ultimately factorization over number fields are done by PARI. Looking at g.factor?? you see that the factorization is ultimately handled by PARI after some manipulations to account for denominators in the defining polynomial for the number field. So it's likely that the bug is actually in PARI. But we'll see. If I were debugging this I would put some print statements in the factor function to see exactly what is passed off to pari and see if pari is buggy. If so, report upstream, after trying the latest svn version.

William

### comment:2 Changed 11 years ago by was

• Milestone set to sage-4.3.1

### comment:3 Changed 11 years ago by was

This might be the same as #7097?

### comment:4 Changed 11 years ago by cremona

• Description modified (diff)
• Owner changed from tbd to cremona

It may well be that the short-term fix I put in at #7097 is not yet good enough. [It is short-term since the latest version of pari have fixed some bugs which arose for non-monic polynomials, which is why the patch I put in at #7097 made sure that pari was only called to factor monic ones.]

I just had a possibly worse example, and found this ticket while looking to see if I should open a new one:

```sage: E = EllipticCurve('4900a2')
sage: f = E.division_polynomial(9)
sage: K3.<z> = CyclotomicField(3)
sage: ff = f.change_ring(K3)
sage: ff.degree()
40
sage: [g.degree() for g,e in ff.factor()]
[1, 3, 9, 40]
```

I factor a degree 40 polynomial and the returned factors have degrees 1,3,9,40! Even if I make the polynomial monic (above it has leading coefficient 9) it is no better:

```sage: x = f.parent().gen()
sage: g = 9^39 * f(x/9)
sage: all([c.is_integral() for c in g.coefficients()])
True
sage: [h.degree() for h,e in g.change_ring(K3).factor()]
[1, 3, 9, 40]
```

### comment:5 Changed 11 years ago by mhansen

There's an SPKG for the new PARI at #8453 which fixes John's problem, but not the one reported in the summary.

### comment:6 Changed 11 years ago by cremona

• Keywords number field pari added

The following script confirms that all is well using either nffactor() or factornf() in

```                   GP/PARI CALCULATOR Version 2.4.3 (development svn-12471)
i686 running linux (ix86/GMP-4.2.2 kernel) 32-bit version
compiled: Jun 25 2010, gcc-4.2.4 (Ubuntu 4.2.4-1ubuntu4)
(readline v5.2 enabled, extended help enabled)
```

(latest svn pari version as of 2010-06-26):

```f = t^12 + 4811804/1884237*t^11 + 501578/1884237*t^10 + 649220/50874399*t^9 + 14465/50874399*t^8 - 12232/152623197*t^7 - 52756/1373608773*t^6 - 8536/4120826319*t^5 - 605/12362478957*t^4 - 220/333786931839*t^3 - 22/1001360795517*t^2 - 4/1001360795517*t - 1/27036741478959

fm = t^12 + 69044128098228*t^11 + 194586025985656552389748914*t^10 + 252206133278375846620611910363960279620*t^9 + 151927551892320463602482158314423242534005837551135*t^8 - 1157840316800177898179502977396915725886340880517554037247717144*t^7 - 15001507175768040071414348254147174918292469313307008195125210400587831506052*t^6 - 21875124557509546030610056365629827329300918240857885825522849089306079707691831828411736*t^5 - 13972837118332351426055337318528492766817006355033884326778630955066105801586929451124705565427318065*t^4 - 5087945924524636104869811628561988778476675586778609071619493774225875340654682413166396849224980548949885496220*t^3 - 4585382620676520885033637329085293361766727857705544672584084201955286189767281537555363181449203944664777829514827546801166*t^2 - 22540691726789566284791090059861226369539881229945431559159210204846754832348501703584277353410422860328945842151249543476507386971939308*t - 5642841249760365128848452030124057197006418321418963437144886094595692736999089907821045425216157097104588947199646188372804628704737026803780620559

d =  27036741478959
subst(fm,t,t*d) == f*d^12

F = nfinit(fm);
fmfac = nffactor(F,subst(fm,t,x));
matsize(fmfac) == [3,2]
vector(3,j,poldegree(fmfac[j,1])) == [1,1,10]

ffac = nffactor(F,subst(f,t,x));
matsize(ffac) == [3,2]
vector(3,j,poldegree(ffac[j,1])) == [1,1,10]

allocatemem()
allocatemem()
allocatemem()
fmfac2 = factornf(subst(fm,t,x),fm)
matsize(fmfac2) == [3,2]
vector(3,j,poldegree(fmfac2[j,1])) == [1,1,10]

ffac2 = factornf(subst(f,t,x),fm);
matsize(ffac2) == [3,2]
vector(3,j,poldegree(ffac2[j,1])) == [1,1,10]
```

Explanation: fm is f made monic and integral which is required for construction of number fields. We check that both f and fm factor correctly over the number field defined by f (which we have to construct using fm): factors have degrees 1,1,10. Note that we have to change variables before factoring, otherwise we get an error; and that the factornf functions require more than the default memory allocation.

This is good news since right now a few feet from me William and Robert B are spending the day making this version of pari into an new spkg (see #9343).

### comment:7 Changed 11 years ago by was

I have now checked that the work at #9343 completely fixes this bug. So when that goes in, this can be changed.

### comment:8 Changed 11 years ago by jdemeyer

• Status changed from new to needs_review

### comment:9 Changed 11 years ago by jdemeyer

• Status changed from needs_review to positive_review

### comment:10 follow-up: ↓ 11 Changed 11 years ago by mpatel

• Milestone changed from sage-4.6 to sage-duplicate/invalid/wontfix
• Resolution set to duplicate
• Status changed from positive_review to closed

I assume this is still fixed by #9343. If not, please reopen this.