Opened 14 years ago

Closed 13 years ago

#1867 closed defect (fixed)

[with patch; positive review] -- factoring multivariate polynomials over finite fields is broken in Singular

Reported by: was Owned by: malb
Priority: major Milestone: sage-3.3
Component: commutative algebra Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by was)

NOTE: This ticket depends on #5068, which is done.

There is a standard algorithm to factor polynomials over a non-prime field that reduces the problem to factoring over a prime field and using gcd over the non-prime field. It seems that gcd works fine over non-prime fields in Singular, as does factoring over prime fields, so this should work for us. Probably singular doesn't do this because either it is slower or it is too much of a pain to implement in Singular (which isn't much of a language), or maybe they just don't care about this problem.

Anyway, to start this off, here is a sample session that illustrates the idea:

sage: k.<a> = GF(9)
sage: R.<x,y> = PolynomialRing(k)
sage: f = (x-a)*(y-a)
sage: f.factor()
Traceback (most recent call last):
...
NotImplementedError: factorization of multivariate polynomials over non-prime fields explicitly disabled due to bugs in Singular
sage: singular(f)
sage: x*y+(-a)*x+(-a)*y+(a+1)
x*y + ( - a)*x + ( - a)*y + (a + 1)
sage: singular(f).factorH()
[1]:
   _[1]=1
   _[2]=x*y+(-a)*x+(-a)*y+(a+1)
[2]:
   1,1
sage: g = f*(x-a^3)*(y-a^3); g
x^2*y^2 - x^2*y - x*y^2 - x^2 + x*y - y^2 + x + y + 1
sage: gg = GF(3)['x,y'](repr(g))    # why doesn't change ring or coerce work
sage: F = gg.factor()
sage: factor1 = R(F[0][0])
sage: factor2 = R(F[1][0])
sage: factor1.gcd(f)
(a)*y + ( - a - 1)
sage: factor2.gcd(f)
(a)*x + ( - a - 1)

Attachments (2)

trac_1867.patch (5.8 KB) - added by was 13 years ago.
trac_1867-part2.patch (3.1 KB) - added by was 13 years ago.
this fixes the other problems in the doctests

Download all attachments as: .zip

Change History (10)

comment:1 Changed 13 years ago by was

Change ring being broken, e.g.,

g.change_ring(GF(3))

in the above example, is now trac #5068.

comment:2 Changed 13 years ago by was

  • Description modified (diff)

I have attached a patch that:

  • fully implements this idea. This works with dramatically higher probability than singular itself. Singular usually gives wrong answers, whereas with this code it seems right "about 99% of the time". E.g., this runs for a long time before finding a problem:
    k.<a> = GF(3^2); R.<x,y> = PolynomialRing(k)
    for i in range(500):
        v = [R.random_element() for _ in range(3)]; print i; assert prod(v).factor(proof=False).prod() == prod(v)
    
    1
    ...
    328
    boom!
    AssertionError: bug in Singular factoring an auxiliary polynomial over GF(p): bad multiplicity (1, 2)
    

and

  • found bugs in factorization over GF(p) -- see ticket #5068. Added a proof flag, and *only* allow factoring if proof=False.

I think this should go into sage because:

  1. It works massively better than singular currently does over GF(q).
  2. Even if singular does fix say factoring, maybe they will only fix GF(p) factorization and not GF(pe). Then this code will make factoring over GF(pe) work too.
  3. If we ever implement our own factorization then this code means we only have to implement GF(p), at least for starters. It would be very nice if we at least had *some* implementation that works, even if is slow.
  4. This patch adds some useful functions such as map_coefficients (which has the same api as the corresponding function in sage-combinat), and _norm_over_nonprime_finite_field.

---

TEST CODE:

k.<a> = GF(3^5); R.<x,y> = PolynomialRing(k)
for i in range(100):
    v = [R.random_element() for _ in range(2)]; print i; assert prod(v).factor(False).prod() == prod(v)
#good


k.<a> = GF(997^2); R.<x,y> = PolynomialRing(k)
for i in range(100):
    v = [R.random_element() for _ in range(2)]; print i; assert prod(v).factor(False).prod() == prod(v)
#good


k.<a> = GF(4); R.<x,y,z> = PolynomialRing(k)
for i in range(100):
    v = [R.random_element() for _ in range(2)]; print i; assert prod(v).factor(False).prod() == prod(v)

# HORRIBLE: 
sage: k.<a> = GF(4); R.<x,y,z> = PolynomialRing(k)
sage: for i in range(100):
....:         v = [R.random_element() for _ in range(2)]; print i; assert prod(v).factor(False).prod() == prod(v)
....: 
0
1
...
30
convertFacCF2NTLGF2X: coefficient not immidiate!
[immediately exits sage!]


k.<a> = GF(7^2); R.<x,y> = PolynomialRing(k)
for i in range(100):
    v = [R.random_element() for _ in range(3)]; print i; assert prod(v).factor(False).prod() == prod(v)
#good


k.<a> = GF(7^2); R.<x,y,z> = PolynomialRing(k)
for i in range(100):
    v = [R.random_element() for _ in range(2)]; print i; assert prod(v).factor(False).prod() == prod(v)
#good

k.<a> = GF(3^6); R.<x,y> = PolynomialRing(k)
for i in range(100):
    v = [R.random_element() for _ in range(2)]; print i; assert prod(v).factor(False).prod() == prod(v)
#good

Changed 13 years ago by was

comment:3 Changed 13 years ago by was

  • Summary changed from suggested way to fix #1705 -- factoring multivariate polynomials over finite fields is broken in Singular to [with patch; needs review] -- factoring multivariate polynomials over finite fields is broken in Singular

comment:4 Changed 13 years ago by kedlaya

  • Summary changed from [with patch; needs review] -- factoring multivariate polynomials over finite fields is broken in Singular to [with patch; negative review] -- factoring multivariate polynomials over finite fields is broken in Singular

Almost, but

	sage -t  "devel/sage-dev1/sage/rings/polynomial/multi_polynomial_libsingular.pyx"

fails a few doctests when I try it because of missing proof=False arguments. See lines 3432, 3461, 3491, 3502.

Changed 13 years ago by was

this fixes the other problems in the doctests

comment:5 Changed 13 years ago by was

  • Summary changed from [with patch; negative review] -- factoring multivariate polynomials over finite fields is broken in Singular to [with patch; needs review] -- factoring multivariate polynomials over finite fields is broken in Singular

comment:6 Changed 13 years ago by was

NOTE (from Noam Elkies):

Maxima can factor multivariate polynomials mod p. However it sometimes will fail, as the example below illustrates.

sage: R.<x,y> = GF(5)[]

sage: f = 2*x^2*y^2 + 2*y^4 + x^3 - 2*x^2*y + x*y^2 + y^3 + x^2 - x*y - y^2 - 2*x - 2*y - 2

sage: maxima.eval('modulus:5')
sage: maxima(f).factor()
Not enough choices for substitution.

This is a known issue.

comment:7 Changed 13 years ago by kedlaya

  • Summary changed from [with patch; needs review] -- factoring multivariate polynomials over finite fields is broken in Singular to [with patch; positive review] -- factoring multivariate polynomials over finite fields is broken in Singular

All doctests pass now. Positive review.

comment:8 Changed 13 years ago by mabshoff

  • Milestone changed from sage-3.4.1 to sage-3.3
  • Resolution set to fixed
  • Status changed from new to closed

Merged both patches in Sage 3.3.alpha3.

Cheers,

Michael

Note: See TracTickets for help on using tickets.