Opened 2 years ago

Closed 23 months 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 saraedum)

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 2 years ago by saraedum

  • Description modified (diff)

comment:2 Changed 2 years ago by saraedum

  • Description modified (diff)

comment:3 Changed 2 years ago by saraedum

  • Stopgaps set to #23643

comment:4 Changed 2 years ago by saraedum

The problem really seems to boil down to the problem described in #17697:

sage: k.<a> = GF(9)
sage: K = k['t'].fraction_field()
sage: R.<x> = K[]
sage: R._singular_()
polynomial ring, over a field, global ordering
// coefficients: ZZ/3(t)
// number of vars : 2
//        block   1 : ordering lp
//                  : names    a x
//        block   2 : ordering C
// quotient ring from ideal
_[1]=a2-a-1

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:

sage: R.<x> = k[]
sage: R._singular_()
polynomial ring, over a field, global ordering
// coefficients: ZZ/3[a]/(a^2-a-1)
// number of vars : 1
//        block   1 : ordering lp
//                  : names    x
//        block   2 : ordering C
Last edited 2 years ago by saraedum (previous) (diff)

comment:5 Changed 2 years ago by saraedum

  • Description modified (diff)
  • Summary changed from Factorization over fraction fields incorrect to Factorization over some quotient rings incorrect

comment:6 Changed 2 years ago by saraedum

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 2 years ago by saraedum

  • Dependencies set to #23660

comment:8 Changed 2 years ago by saraedum

  • Authors set to Julian Rüth
  • Description modified (diff)

comment:9 Changed 2 years ago by saraedum

  • Branch set to u/saraedum/factorization_over_some_quotient_rings_incorrect

comment:10 Changed 2 years ago by saraedum

  • Branch u/saraedum/factorization_over_some_quotient_rings_incorrect deleted
  • Status changed from new to needs_review

comment:11 Changed 2 years ago by roed

  • Cc roed added

I'll try to take a look at this this week at Sage Days 88.

comment:12 Changed 2 years ago by roed

  • Branch set to u/saraedum/factorization_over_some_quotient_rings_incorrect
  • Commit set to 82338dceb541fafac98c357eefea04999c5e4002

Hoping that this branch was accidentally deleted....


New commits:

82338dcFix factorization over fraction fields that are isomorphic to function fields

comment:13 Changed 2 years ago by saraedum

Yes. I don't know why this happens.

comment:14 Changed 2 years ago by jpflori

Wouldn't it be better to fix the way the singular ring is created? I'l try to have a look.

comment:15 Changed 2 years ago by saraedum

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 2 years ago by jpflori

  • 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 2 years ago by saraedum

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 2 years ago by git

  • 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:

64e6546Merge branch 'develop' into t/23642/factorization_over_some_quotient_rings_incorrect
f6dd0cdBetter isomorphisms between fraction fields and function fields
38f18b8minor docstring change
8bfe326Merge branch 'develop' into t/23660/better_isomorphisms_between_function_fields_and_fraction_fields
746eac0fix docstring
4bddab1Merge branch 't/23660/better_isomorphisms_between_function_fields_and_fraction_fields' into t/23642/factorization_over_some_quotient_rings_incorrect

comment:19 Changed 2 years ago by saraedum

  • Status changed from needs_review to positive_review

Just merged in the dependencies.

comment:20 Changed 2 years ago by git

  • 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:

5739955Base change factorization to the right parent
c17adf7Merge 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 2 years ago by saraedum

  • Status changed from needs_review to needs_work
  • Work issues set to failing doctests

comment:22 Changed 23 months ago by git

  • Commit changed from c17adf7c17f2f8bdfd209067246660d4151a8db2 to b6c62d0d0be8add74bb92dbbd8d261c4bed2f694

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

b6c62d0Fix doctests

comment:23 Changed 23 months ago by saraedum

  • Status changed from needs_work to needs_review

New commits:

b6c62d0Fix doctests

New commits:

b6c62d0Fix doctests

comment:24 Changed 23 months ago by roed

  • 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 23 months ago by vbraun

  • Branch changed from u/saraedum/factorization_over_some_quotient_rings_incorrect to b6c62d0d0be8add74bb92dbbd8d261c4bed2f694
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.