Opened 4 years ago
Closed 3 years ago
#23642 closed defect (fixed)
Factorization over some quotient rings incorrect
Reported by:  saraedum  Owned by:  

Priority:  major  Milestone:  sage8.1 
Component:  commutative algebra  Keywords:  
Cc:  swewers, roed  Merged in:  
Authors:  Julian Rüth  Reviewers:  JeanPierre Flori, David Roe 
Report Upstream:  N/A  Work issues:  failing doctests 
Branch:  b6c62d0 (Commits)  Commit:  b6c62d0d0be8add74bb92dbbd8d261c4bed2f694 
Dependencies:  #23660  Stopgaps:  #23643 
Description (last modified by )
Currently, factorization is broken over fraction fields over nonprime finite fields:
sage: k.<a> = GF(9) sage: K = k['t'].fraction_field() sage: R.<x> = K[] sage: f = x^3 + a sage: f.factor() x^3 + a sage: (x  a + 1)^3 x^3 + a
This is probably related to #17697.
As a workaround one can factor over the function field:
sage: K.<t> = FunctionField(k) sage: R.<x> = K[] sage: f = x^3 + a sage: f.factor() (x + 2*a + 1)^3
Doing this seems not to come with a performance penalty:
sage: k = GF(3) sage: K = k['t'].fraction_field() sage: small = prod([K.random_element(degree=2) for n in range(3)]) sage: medium = prod([K.random_element(degree=8) for n in range(10)]) sage: large = prod([K.random_element(degree=16) for n in range(1000)]) sage: %timeit small.factor() 1000 loops, best of 3: 389 µs per loop # before 1000 loops, best of 3: 390 µs per loop # after (the same polynomial pickled and unpickled) sage: %timeit medium.factor() 100 loops, best of 3: 2.45 ms per loop # before 100 loops, best of 3: 2.55 ms per loop # after sage: %timeit large.factor() 1 loop, best of 3: 2.62 s per loop # before 1 loop, best of 3: 2.62 s per loop # after
Change History (25)
comment:1 Changed 4 years ago by
 Description modified (diff)
comment:2 Changed 4 years ago by
 Description modified (diff)
comment:3 Changed 4 years ago by
 Stopgaps set to #23643
comment:4 Changed 4 years ago by
comment:5 Changed 4 years ago by
 Description modified (diff)
 Summary changed from Factorization over fraction fields incorrect to Factorization over some quotient rings incorrect
comment:6 Changed 4 years ago by
There seems to be nothing we can do about this while using Singular. Singular does not seem to support function fields over nonprime finite fields.
It seems that we have to fall back to our own function field factorization code here.
comment:7 Changed 4 years ago by
 Dependencies set to #23660
comment:8 Changed 4 years ago by
 Description modified (diff)
comment:9 Changed 4 years ago by
 Branch set to u/saraedum/factorization_over_some_quotient_rings_incorrect
comment:10 Changed 4 years ago by
 Branch u/saraedum/factorization_over_some_quotient_rings_incorrect deleted
 Status changed from new to needs_review
comment:11 Changed 4 years ago by
 Cc roed added
I'll try to take a look at this this week at Sage Days 88.
comment:12 Changed 4 years ago by
 Branch set to u/saraedum/factorization_over_some_quotient_rings_incorrect
 Commit set to 82338dceb541fafac98c357eefea04999c5e4002
Hoping that this branch was accidentally deleted....
New commits:
82338dc  Fix factorization over fraction fields that are isomorphic to function fields

comment:13 Changed 4 years ago by
Yes. I don't know why this happens.
comment:14 Changed 4 years ago by
Wouldn't it be better to fix the way the singular ring is created? I'l try to have a look.
comment:15 Changed 4 years ago by
I tried that but I do not think that it's possible. It seems that you can not create (k[a]/(g(a)))(t)[x]
in Singular; as far as I understand in Singular that would be Frac(k[a,t]/(g(a)))[t]
in Singular but then Singular complains that g
is not univariate. You can only realize this with a "quotient ring", but these are ignored in factorizations.
comment:16 Changed 4 years ago by
 Reviewers set to JeanPierre Flori
 Status changed from needs_review to positive_review
Ok, I'll trust you on that one as I won't have time before a couple of weeks to have a look.
comment:17 Changed 4 years ago by
Thanks. I am not a Singular expert by any means but I tried the ways that I could think of from looking at the Singular documentation and I guess there is also a reason why someone used this quotient ring construction in the first place.
comment:18 Changed 3 years ago by
 Commit changed from 82338dceb541fafac98c357eefea04999c5e4002 to 4bddab13686b137795113ffadb1a1ff4a618d299
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
64e6546  Merge branch 'develop' into t/23642/factorization_over_some_quotient_rings_incorrect

f6dd0cd  Better isomorphisms between fraction fields and function fields

38f18b8  minor docstring change

8bfe326  Merge branch 'develop' into t/23660/better_isomorphisms_between_function_fields_and_fraction_fields

746eac0  fix docstring

4bddab1  Merge branch 't/23660/better_isomorphisms_between_function_fields_and_fraction_fields' into t/23642/factorization_over_some_quotient_rings_incorrect

comment:19 Changed 3 years ago by
 Status changed from needs_review to positive_review
Just merged in the dependencies.
comment:20 Changed 3 years ago by
 Commit changed from 4bddab13686b137795113ffadb1a1ff4a618d299 to c17adf7c17f2f8bdfd209067246660d4151a8db2
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
5739955  Base change factorization to the right parent

c17adf7  Merge branch 'u/saraedum/factorization_over_some_quotient_rings_incorrect' of git://trac.sagemath.org/sage into t/23642/factorization_over_some_quotient_rings_incorrect

comment:21 Changed 3 years ago by
 Status changed from needs_review to needs_work
 Work issues set to failing doctests
comment:22 Changed 3 years ago by
 Commit changed from c17adf7c17f2f8bdfd209067246660d4151a8db2 to b6c62d0d0be8add74bb92dbbd8d261c4bed2f694
Branch pushed to git repo; I updated commit sha1. New commits:
b6c62d0  Fix doctests

comment:23 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:24 Changed 3 years ago by
 Reviewers changed from JeanPierre Flori to JeanPierre Flori, David Roe
 Status changed from needs_review to positive_review
All tests pass for me on k8s. Looks good.
comment:25 Changed 3 years ago by
 Branch changed from u/saraedum/factorization_over_some_quotient_rings_incorrect to b6c62d0d0be8add74bb92dbbd8d261c4bed2f694
 Resolution set to fixed
 Status changed from positive_review to closed
The problem really seems to boil down to the problem described in #17697:
Singular's
factorize()
is ignoring the quotient ring. However, if we omit the fraction field, then our code does not use the quotient ring construction and factorization works: