Opened 5 years ago
Closed 5 years ago
#23642 closed defect (fixed)
Factorization over some quotient rings incorrect
Reported by:  Julian Rüth  Owned by:  

Priority:  major  Milestone:  sage8.1 
Component:  commutative algebra  Keywords:  
Cc:  Stefan Wewers, David Roe  Merged in:  
Authors:  Julian Rüth  Reviewers:  JeanPierre Flori, David Roe 
Report Upstream:  N/A  Work issues:  failing doctests 
Branch:  b6c62d0 (Commits, GitHub, GitLab)  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 5 years ago by
Description:  modified (diff) 

comment:2 Changed 5 years ago by
Description:  modified (diff) 

comment:3 Changed 5 years ago by
Stopgaps:  → #23643 

comment:5 Changed 5 years ago by
Description:  modified (diff) 

Summary:  Factorization over fraction fields incorrect → Factorization over some quotient rings incorrect 
comment:6 Changed 5 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 5 years ago by
Dependencies:  → #23660 

comment:8 Changed 5 years ago by
Authors:  → Julian Rüth 

Description:  modified (diff) 
comment:9 Changed 5 years ago by
Branch:  → u/saraedum/factorization_over_some_quotient_rings_incorrect 

comment:10 Changed 5 years ago by
Branch:  u/saraedum/factorization_over_some_quotient_rings_incorrect 

Status:  new → needs_review 
comment:11 Changed 5 years ago by
Cc:  David Roe added 

I'll try to take a look at this this week at Sage Days 88.
comment:12 Changed 5 years ago by
Branch:  → u/saraedum/factorization_over_some_quotient_rings_incorrect 

Commit:  → 82338dceb541fafac98c357eefea04999c5e4002 
Hoping that this branch was accidentally deleted....
New commits:
82338dc  Fix factorization over fraction fields that are isomorphic to function fields

comment:14 Changed 5 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 5 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 5 years ago by
Reviewers:  → JeanPierre Flori 

Status:  needs_review → 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 5 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 5 years ago by
Commit:  82338dceb541fafac98c357eefea04999c5e4002 → 4bddab13686b137795113ffadb1a1ff4a618d299 

Status:  positive_review → 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 5 years ago by
Status:  needs_review → positive_review 

Just merged in the dependencies.
comment:20 Changed 5 years ago by
Commit:  4bddab13686b137795113ffadb1a1ff4a618d299 → c17adf7c17f2f8bdfd209067246660d4151a8db2 

Status:  positive_review → 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 5 years ago by
Status:  needs_review → needs_work 

Work issues:  → failing doctests 
comment:22 Changed 5 years ago by
Commit:  c17adf7c17f2f8bdfd209067246660d4151a8db2 → b6c62d0d0be8add74bb92dbbd8d261c4bed2f694 

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

comment:23 Changed 5 years ago by
Status:  needs_work → needs_review 

comment:24 Changed 5 years ago by
Reviewers:  JeanPierre Flori → JeanPierre Flori, David Roe 

Status:  needs_review → positive_review 
All tests pass for me on k8s. Looks good.
comment:25 Changed 5 years ago by
Branch:  u/saraedum/factorization_over_some_quotient_rings_incorrect → b6c62d0d0be8add74bb92dbbd8d261c4bed2f694 

Resolution:  → fixed 
Status:  positive_review → 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: