Opened 11 years ago

Closed 11 years ago

# Yet another bug in factorization over number fields

Reported by: Owned by: lftabera tbd critical sage-4.6.2 factorization factorization, number fields jdemeyer sage-4.6.2.alpha2 Jeroen Demeyer Luis Felipe Tabera Alonso Fixed upstream, but not in a stable release.

I have found several issues factoring polynomials over number fields.

```sage: K.<a> = NumberField(x^6+x^5+x^4+x^3+x^2+x+1); t=polygen(K)
sage: l = (-1/7*a^5 - 1/7*a^4 - 1/7*a^3 - 1/7*a^2 - 2/7*a - 1/7)*t^10 + (4/7*a^5 - 2/7*a^4 - 2/7*a^3 - 2/7*a^2 - 2/7*a - 6/7)*t^9 + (90/49*a^5 + 152/49*a^4 + 18/49*a^3 + 24/49*a^2 + 30/49*a + 36/49)*t^8 + (-10/49*a^5 + 10/7*a^4 + 198/49*a^3 - 102/49*a^2 - 60/49*a - 26/49)*t^7 + (40/49*a^5 + 45/49*a^4 + 60/49*a^3 + 277/49*a^2 - 204/49*a - 78/49)*t^6 + (90/49*a^5 + 110/49*a^4 + 2*a^3 + 80/49*a^2 + 46/7*a - 30/7)*t^5 + (30/7*a^5 + 260/49*a^4 + 250/49*a^3 + 232/49*a^2 + 32/7*a + 8)*t^4 + (-184/49*a^5 - 58/49*a^4 - 52/49*a^3 - 66/49*a^2 - 72/49*a - 72/49)*t^3 + (18/49*a^5 - 32/49*a^4 + 10/49*a^3 + 4/49*a^2)*t^2 + (2/49*a^4 - 4/49*a^3 + 2/49*a^2)*t
sage: factor(l)
```

```(-1/7*a^5 - 1/7*a^4 - 1/7*a^3 - 1/7*a^2 - 2/7*a - 1/7) * t^4 * (t^6 + (-19/7*a^5 - 17/7*a^4 - 15/7*a^3 - 13/7*a^2 - 11/7*a - 9/7)*t^5 + (2*a^5 - 10/7*a^4 - 16/7*a^3 + 10/7*a^2 - 2/7*a + 18/7)*t^4 + (-40/7*a^5 - 8/7*a^4 - 40/7*a^3 - 48/7*a^2 - 32/7)*t^3 + (26/7*a^5 - 6/7*a^4 + 26/7*a^3 - 6/7*a^2 - 4/7*a + 34/7)*t^2 + (-20/7*a^5 - 4/7*a^4 - 20/7*a^3 - 4/7*a^2 - 20/7*a - 16/7)*t + 2/7*a^5 - 2/7*a^4 + 2/7*a^3 - 2/7*a^2 + 2/7*a - 2/7)
```

```(-1/7*a^5 - 1/7*a^4 - 1/7*a^3 - 1/7*a^2 - 2/7*a - 1/7) * t * (t - a^5 - a^4 - a^3 - a^2 - a - 1)^4 * (t^5 + (-12/7*a^5 - 10/7*a^4 - 8/7*a^3 - 6/7*a^2 - 4/7*a - 2/7)*t^4 + (12/7*a^5 - 8/7*a^3 + 16/7*a^2 + 2/7*a + 20/7)*t^3 + (-20/7*a^5 - 20/7*a^3 - 20/7*a^2 + 4/7*a - 2)*t^2 + (12/7*a^5 + 12/7*a^3 + 2/7*a + 16/7)*t - 4/7*a^5 - 4/7*a^3 - 4/7*a - 2/7)
```

Second issue:

```sage: K.<a> = NumberField(x^6+x^5+x^4+x^3+x^2+x+1); t=polygen(K)
sage: l2 = (1/7*a^2 - 1/7*a)*t^10 + (4/7*a - 6/7)*t^9 + (102/49*a^5 + 99/49*a^4 + 96/49*a^3 + 93/49*a^2 + 90/49*a + 150/49)*t^8 + (-160/49*a^5 - 36/49*a^4 - 48/49*a^3 - 8/7*a^2 - 60/49*a - 60/49)*t^7 + (30/49*a^5 - 55/49*a^4 + 20/49*a^3 + 5/49*a^2)*t^6 + (6/49*a^4 - 12/49*a^3 + 6/49*a^2)*t^5
sage: factor(l2)  # WARNING --- eats all memory
```

It is t5 times an ireducible polynomial. GP released with Sage computes the factorization without problems, but trying to compute the factorization with Sage the program starts to eat all available RAM and you have to kill the program. GP session of what actually happens (note that `l2` is not monic):

```K = nfinit(a^6 + a^5 + a^4 + a^3 + a^2 + a + 1)
f = Mod(1, a^6 + a^5 + a^4 + a^3 + a^2 + a + 1)*x^10 + Mod(4/7*a - 6/7, a^6 + a^5 + a^4 + a^3 + a^2 + a + 1)*x^9 + Mod(9/49*a^2 - 3/7*a + 15/49, a^6 + a^5 + a^4 + a^3 + a^2 + a + 1)*x^8 + Mod(8/343*a^3 - 32/343*a^2 + 40/343*a - 20/343, a^6 + a^5 + a^4 + a^3 + a^2 + a + 1)*x^7 + Mod(5/2401*a^4 - 20/2401*a^3 + 40/2401*a^2 - 5/343*a + 15/2401, a^6 + a^5 + a^4 + a^3 + a^2 + a + 1)*x^6 + Mod(-6/16807*a^4 + 12/16807*a^3 - 18/16807*a^2 + 12/16807*a - 6/16807, a^6 + a^5 + a^4 + a^3 + a^2 + a + 1)*x^5
nffactor(K, f)
```

Second issue is PARI bug 1141. See #10430 for a fix.

Dependencies: #10430, #10279.

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

I think this is very likely a pari bug, and is the same one (http://pari.math.u-bordeaux.fr/cgi-bin/bugreport.cgi?bug=1132) that was fixed in response to #10279. If I'm right, it would be solved by #10430.

This is the simplest example (of the first problem) that I have found:

```trousseau-bash% sage-4.6/sage
----------------------------------------------------------------------
| Sage Version 4.6, Release Date: 2010-10-30                         |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
sage: PL.<y> = L[]
sage: (y*(y^2 - (1 + a)/3)*(y^2 - a/2)^2).factor()
y^3 * (y^4 + (-5/6*a - 1/3)*y^2 + 1/6*a + 1/2)
```

This is the equivalent in pari (producing the same erroneous result):

```trousseau-bash% sage-4.6/sage -gp
GP/PARI CALCULATOR Version 2.4.3 (development svn-12577:12605)
i386 running darwin (x86-64/GMP-4.2.1 kernel) 64-bit version
...
parisize = 8000000, primelimit = 500509
? K = nfinit(a^2 - 3);
? f = x*(x^2 + Mod(-(a + 1)/3, a^2 - 3))*(x^2 + Mod(-a/2, a^2 - 3))^2;
? nffactor(K, f)
%1 =
[x 3]

[x^4 + Mod(-5/6*a - 1/3, a^2 - 3)*x^2 + Mod(1/6*a + 1/2, a^2 - 3) 1]

```

But with the version of pari in sage 4.5.3 the result is correct:

```trousseau-bash% sage-4.5.3/sage -gp
GP/PARI CALCULATOR Version 2.3.5 (released)
i386 running darwin (x86-64/GMP-4.2.1 kernel) 64-bit version
...
parisize = 8000000, primelimit = 500000
? K = nfinit(a^2 - 3);
? f = x*(x^2 + Mod(-(a + 1)/3, a^2 - 3))*(x^2 + Mod(-a/2, a^2 - 3))^2;
? nffactor(K, f)
%1 =
[x 1]

[x^2 + Mod(-1/2*a, a^2 - 3) 2]

[x^2 + Mod(-1/3*a - 1/3, a^2 - 3) 1]

```

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

To the submitter of the bug: your `l` and `l2` in the report are the same and this is probably not what you meant.

I can confirm that the first bug involving `l` is indeed fixed by #10430.

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

• Description modified (diff)

Interesting, I was not able to reproduce the problem in gp. But being a pari bug makes sense.

I have corrected the second example, with gp I have no problems to factor the polynomial. Maybe the problem is with libpari.

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

• Description modified (diff)

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

• Description modified (diff)

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

• Description modified (diff)

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

• Description modified (diff)

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

• Description modified (diff)

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

• Description modified (diff)
• Status changed from new to needs_review

### comment:10 Changed 11 years ago by lftabera

• Authors set to Jeroen Demeyer
• Reviewers set to Luis Felipe Tabera Alonso
• Status changed from needs_review to positive_review

I confirm that the patch solves the problems mentioned for these cases and also some others I have found. With the latests versions of PARI we do not need to be so careful with non-monic polynomials. In the future we may consider eliminating the unit parameter from _factor_pari_helper. It is used right now in a few other places right now though.

The patch also includes some documentation corrections.

Depends on: #10430, #10279.

Positive review.

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

• Report Upstream changed from N/A to Fixed upstream, but not in a stable release.

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

• Merged in set to sage-4.6.2.alpha1
• Resolution set to fixed
• Status changed from positive_review to closed

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

• Merged in sage-4.6.2.alpha1 deleted
• Resolution fixed deleted
• Status changed from closed to new

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

• Status changed from new to needs_review

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

• Status changed from needs_review to positive_review

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

• Merged in set to sage-4.6.2.alpha2
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.