Factorization over some quotient rings incorrect

[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

Depends on #23660

CC: @sagetrac-swewers @roed314

Component: commutative algebra

Stopgaps: #23643

Work Issues: failing doctests

Author: Julian Rüth

Branch/Commit: b6c62d0

Reviewer: Jean-Pierre Flori, David Roe

Issue created by migration from https://trac.sagemath.org/ticket/23642

[saraedum]

Stopgaps: #23643

[saraedum]

comment:4

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

[saraedum]

comment:6

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.

[saraedum]

Dependencies: #23660

[saraedum]

Author: Julian Rüth

[saraedum]

Branch: u/saraedum/factorization_over_some_quotient_rings_incorrect

[saraedum]

Changed branch from u/saraedum/factorization_over_some_quotient_rings_incorrect to none

[roed314]

comment:11

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

[roed314]

Commit: 82338dc

[roed314]

Branch: u/saraedum/factorization_over_some_quotient_rings_incorrect

[roed314]

comment:12

Hoping that this branch was accidentally deleted....

---

New commits:

82338dc

Fix factorization over fraction fields that are isomorphic to function fields

[saraedum]

comment:13

Yes. I don't know why this happens.

[jpflori]

comment:14

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

[saraedum]

comment:15

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.

[jpflori]

comment:16

Ok, I'll trust you on that one as I won't have time before a couple of weeks to have a look.

[jpflori]

Reviewer: Jean-Pierre Flori

[saraedum]

comment:17

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.

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 82338dc to 4bddab1

[saraedum]

comment:19

Just merged in the dependencies.

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 4bddab1 to c17adf7

[saraedum]

Work Issues: failing doctests

[sagetrac-git]

Changed commit from c17adf7 to b6c62d0

[sagetrac-git]

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

b6c62d0

Fix doctests

[saraedum]

New commits:

b6c62d0

Fix doctests

---

New commits:

b6c62d0

Fix doctests

[roed314]

Changed reviewer from Jean-Pierre Flori to Jean-Pierre Flori, David Roe

[roed314]

comment:24

All tests pass for me on k8s. Looks good.

[vbraun]

Changed branch from u/saraedum/factorization_over_some_quotient_rings_incorrect to b6c62d0