Opened 5 years ago

Closed 5 years ago

Last modified 5 years ago

#16681 closed defect (fixed)

Random doctest failures in sage/rings/algebraic_closure_finite_field.py

Reported by: vbraun Owned by:
Priority: major Milestone: sage-6.4
Component: number theory Keywords: random_fail
Cc: pbruin, defeo, vdelecroix, mmarco, jpflori Merged in:
Authors: Vincent Delecroix Reviewers: Volker Braun
Report Upstream: N/A Work issues:
Branch: f6dc356 (Commits) Commit:
Dependencies: #16682 Stopgaps:

Description (last modified by vbraun)

This is caused by #15390

sage -t --long src/sage/rings/algebraic_closure_finite_field.py
**********************************************************************
File "src/sage/rings/algebraic_closure_finite_field.py", line 940, in sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField_generic._factor_univariate_polynomial
Failed example:
    for d in xrange(10):
        p = R.random_element(degree=randint(2,8))
        assert p.factor().prod() == p
Exception raised:
    Traceback (most recent call last):
      File "/Users/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 480, in _run
        self.execute(example, compiled, test.globs)
      File "/Users/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 839, in execute
        exec compiled in globs
      File "<doctest sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField_generic._factor_univariate_polynomial[4]>", line 3, in <module>
        assert p.factor().prod() == p
    AssertionError
**********************************************************************
1 item had failures:
   1 of   6 in sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField_generic._factor_univariate_polynomial

First of all, you should use a form of assert that gives some minimal information when it can fail, e.g. in the form below. The following fails occasionally and makes it easy enough to reproduce:

sage: K = GF(3).algebraic_closure()
sage: R = PolynomialRing(K, 'T')
sage: T = R.gen()
sage: for d in xrange(1000):
....:         p = R.random_element(degree=8)
....:         assert p.factor().prod() == p, p.factor()
....:     
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-22-f31a401fb53b> in <module>()
      1 for d in xrange(Integer(1000)):
      2         p = R.random_element(degree=Integer(8))
----> 3         assert p.factor().prod() == p, p.factor()
      4 

AssertionError: T * (T + 1) * (T + z5 + 1) * (T + z5^3 + 1) * (T + 2*z5^4 + z5) * (T + 2*z5^4 + 2*z5^2) * (T + 2*z5^4 + 2*z5^3 + z5^2 + z5)

On a related note, a random element can be zero:

sage: K = GF(3).algebraic_closure()
sage: R = PolynomialRing(K, 'T')
sage: T = R.gen()
sage: for d in xrange(1000):
....:         p = R.random_element(degree=randint(2,8))
....:         assert p.factor().prod() == p, p
....:     
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-15-db4aacba08d5> in <module>()
      1 for d in xrange(Integer(1000)):
      2         p = R.random_element(degree=randint(Integer(2),Integer(8)))
----> 3         assert p.factor().prod() == p, p
      4 

/home/release/Sage/local/lib/python2.7/site-packages/sage/rings/polynomial/polynomial_element.so in sage.rings.polynomial.polynomial_element.Polynomial.factor (build/cythonized/sage/rings/polynomial/polynomial_element.c:23530)()

ValueError: factorization of 0 not defined

Change History (28)

comment:1 Changed 5 years ago by vbraun

  • Cc pbruin defeo vdelecroix mmarco added
  • Description modified (diff)

comment:2 Changed 5 years ago by vdelecroix

Hi,

Nice catch! I am on it.

For the "related note", if a polynomial with degree between 2 and 8 can be zero there is definitely a bug but not caused by #15390.

Vincent

comment:3 Changed 5 years ago by vdelecroix

  • Dependencies set to #16682

comment:4 Changed 5 years ago by vdelecroix

I do not understand...

sage: K = GF(5).algebraic_closure()
sage: R = PolynomialRing(K, 'T')
sage: while True:
....:     p = R.random_element(degree=(2,10))
....:     fac = p.factor()
....:     assert fac.prod() == p, (p,fac)
Traceback (most recent call last):
...
AssertionError: (2*T^6 + 2*T^5 + 4*T^4 + 2*T^2 + 2*T + 2, (2) * (T + 3) * (T + 3*z5^3 + 2*z5^2 + 1) * (T + 2*z5^4 + 3*z5^2 + 4*z5 + 1) * (T + 2*z5^4 + z5^3 + z5^2 + 3) * (T + 2*z5^4 + 2*z5^3 + 2) * (T + 2*z5^4 + 4*z5^3 + z5^2 + 3*z5 + 2))
sage: p == fac.prod()          # fine
False
sage: p.factor() == fac        # What!?
False
sage: p.factor().prod() == p   # What again!?
True

comment:5 Changed 5 years ago by vbraun

The factorization is not cached but recomputed every time. Sometimes, it is wrong.

comment:6 Changed 5 years ago by vbraun

  • Keywords random_fail added

comment:7 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:8 Changed 5 years ago by vdelecroix

  • Authors set to Vincent Delecroix
  • Branch set to u/vdelecroix/16881
  • Commit set to 975fb54a89391fcf189d336908e46be53c389f43
  • Status changed from new to needs_review

All right. The root finding algorithm from #15390 was wrong.

Vincent


New commits:

a2fa480trac #16682: fix random_element in polynomial ring
36ee521trac #16682: the zero polynomial has degree -1
49b9331trac #16682: merge 6.3.rc0
589caadtrac #16682: input check
6b9ac1btrac #16682: better random element
e1b61fftrac #16682: fix doctests
1e0f8d9trac #16682: merge sage 6.3
975fb54trac #16881: fix factorization

comment:9 Changed 5 years ago by vbraun

  • Reviewers set to Volker Braun
  • Status changed from needs_review to positive_review

lgtm

comment:10 Changed 5 years ago by vbraun

  • Status changed from positive_review to needs_work
sage -t src/sage/matrix/matrix2.pyx
**********************************************************************
File "src/sage/matrix/matrix2.pyx", line 5349, in sage.matrix.matrix2.Matrix.diagonal.eigenvalues
Failed example:
    ev = M.eigenvalues(); ev
Expected:
    [2*z3, 2*z3 + 2, 2*z3 + 1]
Got:
    [2*z3 + 1, 2*z3 + 2, 2*z3]
**********************************************************************
File "src/sage/matrix/matrix2.pyx", line 5359, in sage.matrix.matrix2.Matrix.diagonal.eigenvalues
Failed example:
    e.as_finite_field_element()
Expected:
    (Finite Field in z3 of size 3^3, 2*z3, Ring morphism:
      From: Finite Field in z3 of size 3^3
      To:   Algebraic closure of Finite Field of size 3
      Defn: z3 |--> z3)
Got:
    (Finite Field in z3 of size 3^3, 2*z3 + 1, Ring morphism:
      From: Finite Field in z3 of size 3^3
      To:   Algebraic closure of Finite Field of size 3
      Defn: z3 |--> z3)
**********************************************************************
1 item had failures:
   2 of  19 in sage.matrix.matrix2.Matrix.diagonal.eigenvalues
    [2116 tests, 2 failures, 8.52 s]
----------------------------------------------------------------------
sage -t src/sage/matrix/matrix2.pyx  # 2 doctests failed
----------------------------------------------------------------------
Total time for all tests: 9.1 seconds
    cpu time: 8.4 seconds
    cumulative wall time: 8.5 seconds

comment:11 Changed 5 years ago by git

  • Commit changed from 975fb54a89391fcf189d336908e46be53c389f43 to f6dc3562a5b553bebaffc70c64b65ea63466ccae

Branch pushed to git repo; I updated commit sha1. New commits:

f6dc356trac #16881: fix documentation issue

comment:12 Changed 5 years ago by vdelecroix

  • Status changed from needs_work to needs_review

Might be a good idea to sort the eigenvalues in .eigenvalues()...

Vincent

comment:13 Changed 5 years ago by vbraun

  • Branch changed from u/vdelecroix/16881 to f6dc3562a5b553bebaffc70c64b65ea63466ccae
  • Resolution set to fixed
  • Status changed from needs_review to closed

comment:14 Changed 5 years ago by vbraun

  • Commit f6dc3562a5b553bebaffc70c64b65ea63466ccae deleted
  • Resolution fixed deleted
  • Status changed from closed to new

Got another random failure with this ticket merged:

sage -t src/sage/rings/algebraic_closure_finite_field.py
**********************************************************************
File "src/sage/rings/algebraic_closure_finite_field.py", line 942, in sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField_generic._factor_univariate_polynomial
Failed example:
    for d in xrange(10):
        p = R.random_element(degree=randint(2,8))
        assert p.factor().prod() == p, "error in the factorization of p={}".format(p)
Exception raised:
    Traceback (most recent call last):
      File "/home/release/Sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 480, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/release/Sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 843, in compile_and_execute
        exec compiled in globs
      File "<doctest sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField_generic._factor_univariate_polynomial[4]>", line 3, in <module>
        assert p.factor().prod() == p, "error in the factorization of p={}".format(p)
    AssertionError: error in the factorization of p=T^7 + T^6 + T^5 + 2*T^4 + 2*T^3 + 2*T^2 + T + 2
**********************************************************************
1 item had failures:
   1 of   6 in sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField_generic._factor_univariate_polynomial
    [175 tests, 1 failure, 5.03 s]

comment:15 Changed 5 years ago by vdelecroix

Hello,

As said on this thread on sage-devel the bug has nothing to do with algebraic closure of finite fields.

Nevertheless, the algorithm which I implemented at a first glance was wrong so:

  • either I move the branch to another ticket
  • or I open a new ticket for the bug about factorization of polynomials over finite fields

Vincent

comment:16 Changed 5 years ago by jpflori

  • Cc jpflori added

comment:17 Changed 5 years ago by vbraun

Either way is fine with me. However you decide to split the ticket, feel free to set this branch back to positive review.

comment:18 Changed 5 years ago by vdelecroix

The new ticket to track the bug is #16885. It is in critical, I am not sure this is right.

For the current branch, what about the random failure? Should I tag the test with a #bug?

Vincent

comment:19 Changed 5 years ago by vbraun

Let's keep the test as it is for now, hopefully you can figure out what is wrong ;-)

comment:20 Changed 5 years ago by vbraun

  • Status changed from new to needs_review

comment:21 Changed 5 years ago by vbraun

  • Status changed from needs_review to positive_review

comment:22 Changed 5 years ago by vbraun

  • Branch changed from f6dc3562a5b553bebaffc70c64b65ea63466ccae to u/vdelecroix/16881
  • Commit set to f6dc3562a5b553bebaffc70c64b65ea63466ccae

New commits:

a2fa480trac #16682: fix random_element in polynomial ring
36ee521trac #16682: the zero polynomial has degree -1
49b9331trac #16682: merge 6.3.rc0
589caadtrac #16682: input check
6b9ac1btrac #16682: better random element
e1b61fftrac #16682: fix doctests
1e0f8d9trac #16682: merge sage 6.3
975fb54trac #16881: fix factorization
f6dc356trac #16881: fix documentation issue

comment:23 Changed 5 years ago by vbraun

  • Branch changed from u/vdelecroix/16881 to f6dc3562a5b553bebaffc70c64b65ea63466ccae
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:24 Changed 5 years ago by nthiery

  • Commit f6dc3562a5b553bebaffc70c64b65ea63466ccae deleted

For the record, I just got this error once, with 6.4.beta 2:

sage -t src/sage/rings/algebraic_closure_finite_field.py
**********************************************************************
File "src/sage/rings/algebraic_closure_finite_field.py", line 890, in sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField_generic._roots_univariate_polynomi
al
Failed example:
    for _ in xrange(10):
        p = R.random_element(degree=randint(2,8))
        for r in p.roots(K, multiplicities=False):
            assert p(r).is_zero(), "r={} is not a root of p={}".format(r,p)
Exception raised:
    Traceback (most recent call last):
      File "/opt/sage-git/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 480, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/opt/sage-git/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 843, in compile_and_execute
        exec compiled in globs
      File "<doctest sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField_generic._roots_univariate_polynomial[4]>", line 4, in <module>
        assert p(r).is_zero(), "r={} is not a root of p={}".format(r,p)
    AssertionError: r=4*t6^3 + 2*t6^2 + 1 is not a root of p=4*x^7 + 2*x^6 + 2*x^5 + 3*x^4 + 2*x^3 + 4*x^2 + 4*x
**********************************************************************
1 item had failures:
   1 of   6 in sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField_generic._roots_univariate_polynomial
    [175 tests, 1 failure, 5.58 s]

comment:25 Changed 5 years ago by jpflori

Did you try with the fix from #16885?

comment:26 Changed 5 years ago by nthiery

No. But also I only got biten by this once, so even if I tried a couple times with #16885, this would not necessarily mean much. But if you think that's useful, I can go for it.

comment:27 Changed 5 years ago by jpflori

Don't really know, it somehow looks related... #16885 should fix a very insidious and rarely occurring bug messing with the current characteristic and polynomial defining a finite field which might cause your error.

comment:28 Changed 5 years ago by nthiery

Ok. Ping me if you need more data point. Right now, I'll reserve the power for testing other tickets of mine. I forgot to mention: my machine is a standard Ubuntu box.

Note: See TracTickets for help on using tickets.