Opened 5 years ago

Closed 5 years ago

# Factorization over some quotient rings incorrect

Reported by: Owned by: Julian Rüth major sage-8.1 commutative algebra Stefan Wewers, David Roe Julian Rüth Jean-Pierre Flori, David Roe N/A failing doctests b6c62d0 b6c62d0d0be8add74bb92dbbd8d261c4bed2f694 #23660 #23643

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
```

### comment:1 Changed 5 years ago by Julian Rüth

Description: modified (diff)

### comment:2 Changed 5 years ago by Julian Rüth

Description: modified (diff)

### comment:3 Changed 5 years ago by Julian Rüth

Stopgaps: → #23643

### comment:4 Changed 5 years ago by Julian Rüth

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 5 years ago by Julian Rüth (previous) (diff)

### comment:5 Changed 5 years ago by Julian Rüth

Description: modified (diff) Factorization over fraction fields incorrect → Factorization over some quotient rings incorrect

### comment:6 Changed 5 years ago by Julian Rüth

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 5 years ago by Julian Rüth

Dependencies: → #23660

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

Authors: → Julian Rüth modified (diff)

### comment:9 Changed 5 years ago by Julian Rüth

Branch: → u/saraedum/factorization_over_some_quotient_rings_incorrect

### comment:10 Changed 5 years ago by Julian Rüth

Branch: u/saraedum/factorization_over_some_quotient_rings_incorrect new → needs_review

### comment:11 Changed 5 years ago by David Roe

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

### comment:12 Changed 5 years ago by David Roe

Branch: → u/saraedum/factorization_over_some_quotient_rings_incorrect → 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 5 years ago by Julian Rüth

Yes. I don't know why this happens.

### comment:14 Changed 5 years ago by Jean-Pierre Flori

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 Julian Rüth

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 Jean-Pierre Flori

Reviewers: → Jean-Pierre Flori 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 Julian Rüth

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 git

Commit: 82338dceb541fafac98c357eefea04999c5e4002 → 4bddab13686b137795113ffadb1a1ff4a618d299 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 Julian Rüth

Status: needs_review → positive_review

Just merged in the dependencies.

### comment:20 Changed 5 years ago by 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`

### comment:21 Changed 5 years ago by Julian Rüth

Status: needs_review → needs_work → failing doctests

### comment:22 Changed 5 years ago by git

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

 ​b6c62d0 `Fix doctests`

### comment:23 Changed 5 years ago by Julian Rüth

Status: needs_work → needs_review

New commits:

 ​b6c62d0 `Fix doctests`

New commits:

 ​b6c62d0 `Fix doctests`

### comment:24 Changed 5 years ago by David Roe

Reviewers: Jean-Pierre Flori → Jean-Pierre Flori, David Roe needs_review → positive_review

All tests pass for me on k8s. Looks good.

### comment:25 Changed 5 years ago by Volker Braun

Branch: u/saraedum/factorization_over_some_quotient_rings_incorrect → b6c62d0d0be8add74bb92dbbd8d261c4bed2f694 → fixed positive_review → closed
Note: See TracTickets for help on using tickets.