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: | sage-8.1 |
Component: | commutative algebra | Keywords: | |
Cc: | swewers, roed | Merged in: | |
Authors: | Julian Rüth | Reviewers: | Jean-Pierre 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 non-prime 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 non-prime 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 Jean-Pierre 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 Jean-Pierre Flori to Jean-Pierre 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: