#16681 closed defect (fixed)
Random doctest failures in sage/rings/algebraic_closure_finite_field.py
Reported by:  vbraun  Owned by:  

Priority:  major  Milestone:  sage6.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 )
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/buildslavesage/slave/sage_git/build/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 480, in _run self.execute(example, compiled, test.globs) File "/Users/buildslavesage/slave/sage_git/build/local/lib/python2.7/sitepackages/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) <ipythoninput22f31a401fb53b> 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) <ipythoninput15db4aacba08d5> 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/sitepackages/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
 Cc pbruin defeo vdelecroix mmarco added
 Description modified (diff)
comment:2 Changed 5 years ago by
comment:3 Changed 5 years ago by
 Dependencies set to #16682
comment:4 Changed 5 years ago by
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
The factorization is not cached but recomputed every time. Sometimes, it is wrong.
comment:6 Changed 5 years ago by
 Keywords random_fail added
comment:7 Changed 5 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:8 Changed 5 years ago by
 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:
a2fa480  trac #16682: fix random_element in polynomial ring

36ee521  trac #16682: the zero polynomial has degree 1

49b9331  trac #16682: merge 6.3.rc0

589caad  trac #16682: input check

6b9ac1b  trac #16682: better random element

e1b61ff  trac #16682: fix doctests

1e0f8d9  trac #16682: merge sage 6.3

975fb54  trac #16881: fix factorization

comment:9 Changed 5 years ago by
 Reviewers set to Volker Braun
 Status changed from needs_review to positive_review
lgtm
comment:10 Changed 5 years ago by
 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
 Commit changed from 975fb54a89391fcf189d336908e46be53c389f43 to f6dc3562a5b553bebaffc70c64b65ea63466ccae
Branch pushed to git repo; I updated commit sha1. New commits:
f6dc356  trac #16881: fix documentation issue

comment:12 Changed 5 years ago by
 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
 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
 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/sitepackages/sage/doctest/forker.py", line 480, in _run self.compile_and_execute(example, compiler, test.globs) File "/home/release/Sage/local/lib/python2.7/sitepackages/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
Hello,
As said on this thread on sagedevel 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
 Cc jpflori added
comment:17 Changed 5 years ago by
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
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
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
 Status changed from new to needs_review
comment:21 Changed 5 years ago by
 Status changed from needs_review to positive_review
comment:22 Changed 5 years ago by
 Branch changed from f6dc3562a5b553bebaffc70c64b65ea63466ccae to u/vdelecroix/16881
 Commit set to f6dc3562a5b553bebaffc70c64b65ea63466ccae
New commits:
a2fa480  trac #16682: fix random_element in polynomial ring

36ee521  trac #16682: the zero polynomial has degree 1

49b9331  trac #16682: merge 6.3.rc0

589caad  trac #16682: input check

6b9ac1b  trac #16682: better random element

e1b61ff  trac #16682: fix doctests

1e0f8d9  trac #16682: merge sage 6.3

975fb54  trac #16881: fix factorization

f6dc356  trac #16881: fix documentation issue

comment:23 Changed 5 years ago by
 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
 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/sagegit/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 480, in _run self.compile_and_execute(example, compiler, test.globs) File "/opt/sagegit/local/lib/python2.7/sitepackages/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
Did you try with the fix from #16885?
comment:26 Changed 5 years ago by
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
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
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.
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