Opened 4 years ago
Closed 4 years ago
#21996 closed enhancement (fixed)
Factorization in iterated extensions of finite fields
Reported by:  saraedum  Owned by:  

Priority:  major  Milestone:  sage7.5 
Component:  finite rings  Keywords:  factorization, finite field, sd86.5, sd87 
Cc:  jpflori  Merged in:  
Authors:  Julian Rüth, Hanson Smith, Edouard Rousseau  Reviewers:  Hanson Smith, Edouard Rousseau, Aly Deines 
Report Upstream:  N/A  Work issues:  
Branch:  d585fdb (Commits, GitHub, GitLab)  Commit:  d585fdbe3fb82c88546c1aa4344715d01bc31839 
Dependencies:  #21998, #22001  Stopgaps: 
Description (last modified by )
At the moment there is no factorization implemented in iterated extensions of finite fields:
sage: K = GF(2) sage: R.<x> = K[] sage: L.<x> = K.extension(x^2 + x + 1) sage: R.<y> = L[] sage: M.<y> = L.extension(y^2 + y + x) sage: R.<T> = M[] sage: (T^2 + T + x).factor() NotImplementedError
The reason is that M
in the above example is just a quotient of a polynomial ring over L
.
Here, we implement isomorphisms (for this special case) to a simple extensions of a prime field over which factorization is implemented. We also implement univariate factorization for polynomial quotient rings if an isomorphism to a field which supports such factorization is known.
Change History (33)
comment:1 Changed 4 years ago by
 Description modified (diff)
comment:2 Changed 4 years ago by
 Dependencies set to #21998
comment:3 Changed 4 years ago by
 Branch set to u/saraedum/factorization_in_iterated_extensions_of_finite_fields
comment:4 Changed 4 years ago by
 Commit set to 1a3cb94b126040085044a697d368b9c1950c9c21
comment:5 Changed 4 years ago by
 Status changed from new to needs_review
comment:6 Changed 4 years ago by
 Commit changed from 1a3cb94b126040085044a697d368b9c1950c9c21 to 1c9f1c62cf964998e7e97776e4fca478091bc9c4
Branch pushed to git repo; I updated commit sha1. New commits:
ca050d3  Refine quotient ring category to Fields()

f9e393b  Improve categories of quotient ring morphisms

80a0e1f  Refine category of quotient rings isomorphic to number fields

1c9f1c6  Make quotient ring morphisms inherit from the correct category type

comment:7 Changed 4 years ago by
I added some __make_element_class__
around the SetMorphism
. They make no difference because SetMorphism
is an extension type, but morally they should be there (if it were not an extension type) so that the result inherits the right methods from the category.
comment:8 Changed 4 years ago by
 Dependencies changed from #21998 to #21998, #22001
comment:9 Changed 4 years ago by
 Commit changed from 1c9f1c62cf964998e7e97776e4fca478091bc9c4 to b2dfab45249f3e6c02d179c37ed71b5d4ba38321
Branch pushed to git repo; I updated commit sha1. New commits:
b2dfab4  Do not pass in category explicitly

comment:10 Changed 4 years ago by
 Commit changed from b2dfab45249f3e6c02d179c37ed71b5d4ba38321 to 725ad0f73a793c5e9c8386f3289498ceef914073
Branch pushed to git repo; I updated commit sha1. New commits:
725ad0f  Merge branch 'develop' into u/saraedum/factorization_in_iterated_extensions_of_finite_fields

comment:11 Changed 4 years ago by
I'll have a closer look soon but right now this looks like a good addition.
The only thing that I find disturbing is the method name _isomorphic_ring
.
Maybe it's not descriptive enough?
comment:12 Changed 4 years ago by
You've got this simple model stuff for function fields.
comment:13 Changed 4 years ago by
 Commit changed from 725ad0f73a793c5e9c8386f3289498ceef914073 to 87b2f6581cacee954d81a9b89ff97732308da3e4
Branch pushed to git repo; I updated commit sha1. New commits:
87b2f65  Merge branch 'develop' into t/21996/factorization_in_iterated_extensions_of_finite_fields

comment:14 followup: ↓ 28 Changed 4 years ago by
 Status changed from needs_review to needs_work
Jens Bauch reported that the factorization does not work here:
K = GF(3) R.<x> = K[] L.<x> = K.extension(x^2 + x + 1) R.<y> = L[] M.<y> = L.extension(y^2 + y + x) R.<T> = M[] (T^2 + T + x).factor()
comment:15 Changed 4 years ago by
 Work issues set to merge conflicts, factorization incorrect
comment:16 Changed 4 years ago by
 Keywords sd86.5 added
comment:17 Changed 4 years ago by
 Commit changed from 87b2f6581cacee954d81a9b89ff97732308da3e4 to 0b44d334b44240d21681c6cb34c178f41f8ee81a
Branch pushed to git repo; I updated commit sha1. New commits:
0b44d33  Merge branch 'develop' into t/21996/factorization_in_iterated_extensions_of_finite_fields

comment:18 Changed 4 years ago by
 Work issues changed from merge conflicts, factorization incorrect to factorization incorrect
comment:19 Changed 4 years ago by
 Branch changed from u/saraedum/factorization_in_iterated_extensions_of_finite_fields to u/erousseau/factorization_in_iterated_extensions_of_finite_fields
comment:20 Changed 4 years ago by
 Commit changed from 0b44d334b44240d21681c6cb34c178f41f8ee81a to 560893257955242d9367f360b142e4b9b9181d4e
 Reviewers set to Hanson Smith, Edouard Rousseau
 Status changed from needs_work to needs_review
If the fix is OK, then I think it is ready for positive review.
Edouard
New commits:
5608932  Fixed a bug in polynomial factorisation

comment:21 Changed 4 years ago by
 Status changed from needs_review to positive_review
comment:22 Changed 4 years ago by
 Status changed from positive_review to needs_work
$ sage t long warnlong 68.9 src/sage/rings/polynomial/polynomial_quotient_ring.py # 4 doctests failed Running doctests with ID 201706100008570afdacb4. Git branch: develop Using optional=mpir,python2,sage Doctesting 1 file. sage t long warnlong 68.9 src/sage/rings/polynomial/polynomial_quotient_ring.py ********************************************************************** File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 267, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic Failed example: isinstance(Q.an_element(),Q.element_class) Expected: True Got: False ********************************************************************** File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 269, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic Failed example: [s for s in dir(Q.category().element_class) if not s.startswith('_')] Expected: ['cartesian_product', 'is_idempotent', 'is_one', 'is_unit', 'lift', 'powers'] Got: ['cartesian_product', 'euclidean_degree', 'factor', 'gcd', 'is_idempotent', 'is_one', 'is_unit', 'lcm', 'lift', 'powers', 'quo_rem', 'xgcd'] ********************************************************************** File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 281, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic Failed example: first_class == Q.__class__ Expected: False Got: True ********************************************************************** File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 834, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.is_field Failed example: F2.is_field() Expected: Traceback (most recent call last): ... NotImplementedError Got: False ********************************************************************** 2 items had failures: 3 of 29 in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic 1 of 13 in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.is_field [410 tests, 4 failures, 2.37 s]  sage t long warnlong 68.9 src/sage/rings/polynomial/polynomial_quotient_ring.py # 4 doctests failed  Total time for all tests: 2.5 seconds cpu time: 2.2 seconds cumulative wall time: 2.4 seconds
comment:23 Changed 4 years ago by
 Branch changed from u/erousseau/factorization_in_iterated_extensions_of_finite_fields to u/saraedum/factorization_in_iterated_extensions_of_finite_fields
comment:24 Changed 4 years ago by
 Branch changed from u/saraedum/factorization_in_iterated_extensions_of_finite_fields to u/erousseau/factorization_in_iterated_extensions_of_finite_fields
 Status changed from needs_work to needs_review
comment:25 Changed 4 years ago by
 Branch changed from u/erousseau/factorization_in_iterated_extensions_of_finite_fields to u/saraedum/factorization_in_iterated_extensions_of_finite_fields
comment:26 Changed 4 years ago by
 Cc jpflori added
 Commit changed from 560893257955242d9367f360b142e4b9b9181d4e to 439b9afd3eb061983342f9ae235522b1f5b5d65f
comment:27 Changed 4 years ago by
 Keywords sd87 added
comment:28 in reply to: ↑ 14 ; followup: ↓ 29 Changed 4 years ago by
Should the following example work with this branch? It does not for me. I get a not implemented error.
All examples in ticket have fields with cardinality a power of 2.
Replying to saraedum:
Jens Bauch reported that the factorization does not work here:
K = GF(3) R.<x> = K[] L.<x> = K.extension(x^2 + x + 1) R.<y> = L[] M.<y> = L.extension(y^2 + y + x) R.<T> = M[] (T^2 + T + x).factor()
comment:29 in reply to: ↑ 28 Changed 4 years ago by
Replying to aly.deines:
Should the following example work with this branch? It does not for me. I get a not implemented error.
All examples in ticket have fields with cardinality a power of 2.
Replying to saraedum:
Jens Bauch reported that the factorization does not work here:
K = GF(3) R.<x> = K[] L.<x> = K.extension(x^2 + x + 1) R.<y> = L[] M.<y> = L.extension(y^2 + y + x) R.<T> = M[] (T^2 + T + x).factor()
That's expected. L is not a field in this example.
comment:30 Changed 4 years ago by
 Work issues factorization incorrect deleted
comment:31 Changed 4 years ago by
 Commit changed from 439b9afd3eb061983342f9ae235522b1f5b5d65f to d585fdbe3fb82c88546c1aa4344715d01bc31839
Branch pushed to git repo; I updated commit sha1. New commits:
d585fdb  Merge branch 'develop' into t/21996/factorization_in_iterated_extensions_of_finite_fields

comment:32 Changed 4 years ago by
 Reviewers changed from Hanson Smith, Edouard Rousseau to Hanson Smith, Edouard Rousseau, Aly Deines
 Status changed from needs_review to positive_review
comment:33 Changed 4 years ago by
 Branch changed from u/saraedum/factorization_in_iterated_extensions_of_finite_fields to d585fdbe3fb82c88546c1aa4344715d01bc31839
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
fix typo in any_root()
Merge branch 't/21998/any_root___sometimes_fails_over_finite_fields' into t/21996/factorization_in_iterated_extensions_of_finite_fields
fix doctests for _isomorphic_ring
extend _isomorphic_ring to handle number fields