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

[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

[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.

[roed]

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

[roed]

Hoping that this branch was accidentally deleted....

---

New commits:

​82338dc

Fix factorization over fraction fields that are isomorphic to function fields

[saraedum]

Yes. I don't know why this happens.

[jpflori]

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

[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.

[jpflori]

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

[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.

[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

[saraedum]

Just merged in the dependencies.

[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

[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

[roed]

All tests pass for me on k8s. Looks good.