Add a splitting field function for polynomials over a finite field

[abrochard]

The purpose of this patch is to add the splitting_field() function to polynomial elements with coefficients in a finite field.

See also #2217, the number field analogue of this ticket.

[roed]

Is this waiting on something, or should it be marked as needs review?

[roed]

I haven't taken a look, but I'll just note that there are some whitespace issues: you added a TAB character in polynomial_element.pyx and there's trailing whitespace as well. See the report from the patchbot.

[robharron]

For p a prime and q = pⁿ, the field F_q is Galois over F_p, i.e. it is the splitting field of any irreducible polynomial of degree n over F_p. Moreover, the field with pⁿ elements contains the one with p^m elements if and only if m divides n. Thus, starting from a polynomial over F_p, the splitting field is simply given by taking the lcm of the degrees of the factors. This would be quicker than what you are doing. If you start with a polynomial over F_q, a simple modification of what I've said would work too.

[mmasdeu]

I think that the whole point is to return an embedding of F_q into its splitting field. For that, one has to be careful when constructing the extensions: either choosing the given polynomial (or a factor of it) to define the extension, or using some root finding algorithm.

Also, the patch fails in the last couple of Sage releases...

Replying to robharron:

For p a prime and q = pⁿ, the field F_q is Galois over F_p, i.e. it is the splitting field of any irreducible polynomial of degree n over F_p. Moreover, the field with pⁿ elements contains the one with p^m elements if and only if m divides n. Thus, starting from a polynomial over F_p, the splitting field is simply given by taking the lcm of the degrees of the factors. This would be quicker than what you are doing. If you start with a polynomial over F_q, a simple modification of what I've said would work too.

[robharron]

But have you looked at the code? It doesn't do anything special with regards to the embedding. (Do you see something I don't?) In the end it simply says F.Hom(K)[0] (for instance, I think the code only runs when the polynomial is defined over a prime field, in which case the embedding returned is simply the canonical one sending 1 to 1). I just quickly wrote a function that does what I suggested and it works just fine and is quite quick.

Replying to mmasdeu:

I think that the whole point is to return an embedding of F_q into its splitting field. For that, one has to be careful when constructing the extensions: either choosing the given polynomial (or a factor of it) to define the extension, or using some root finding algorithm.

Also, the patch fails in the last couple of Sage releases...

Replying to robharron:

For p a prime and q = pⁿ, the field F_q is Galois over F_p, i.e. it is the splitting field of any irreducible polynomial of degree n over F_p. Moreover, the field with pⁿ elements contains the one with p^m elements if and only if m divides n. Thus, starting from a polynomial over F_p, the splitting field is simply given by taking the lcm of the degrees of the factors. This would be quicker than what you are doing. If you start with a polynomial over F_q, a simple modification of what I've said would work too.

[mmasdeu]

Yes, I agree that for polynomials defined over F_p the function should be simplified. As for F_q one definitely needs to fix the code, since that calling of Hom won't work...

Replying to robharron:

But have you looked at the code? It doesn't do anything special with regards to the embedding. (Do you see something I don't?) In the end it simply says F.Hom(K)[0] (for instance, I think the code only runs when the polynomial is defined over a prime field, in which case the embedding returned is simply the canonical one sending 1 to 1). I just quickly wrote a function that does what I suggested and it works just fine and is quite quick.

Replying to mmasdeu:

I think that the whole point is to return an embedding of F_q into its splitting field. For that, one has to be careful when constructing the extensions: either choosing the given polynomial (or a factor of it) to define the extension, or using some root finding algorithm.

Also, the patch fails in the last couple of Sage releases...

Replying to robharron:

For p a prime and q = pⁿ, the field F_q is Galois over F_p, i.e. it is the splitting field of any irreducible polynomial of degree n over F_p. Moreover, the field with pⁿ elements contains the one with p^m elements if and only if m divides n. Thus, starting from a polynomial over F_p, the splitting field is simply given by taking the lcm of the degrees of the factors. This would be quicker than what you are doing. If you start with a polynomial over F_q, a simple modification of what I've said would work too.

[robharron]

No, for F_q the calling of Hom works:

sage: F = GF(3^4, 'z')
sage: K = GF(3^12, 'zz')
sage: F.Hom(K)
Set of field embeddings from Finite Field in z of size 3^4 to Finite Field in zz of size 3^12
sage: F.Hom(K)[0]
Ring morphism:
  From: Finite Field in z of size 3^4
  To:   Finite Field in zz of size 3^12
  Defn: z |--> 2*zz^10 + zz^8 + 2*zz^7 + zz^6 + 2*zz^5 + zz^4 + 2*zz^3 + 2*zz^2 + zz + 2

The problem over F_q is elsewhere: some coercion problem when calling poly.change_ring().

Replying to mmasdeu:

Yes, I agree that for polynomials defined over F_p the function should be simplified. As for F_q one definitely needs to fix the code, since that calling of Hom won't work...

Replying to robharron:

But have you looked at the code? It doesn't do anything special with regards to the embedding. (Do you see something I don't?) In the end it simply says F.Hom(K)[0] (for instance, I think the code only runs when the polynomial is defined over a prime field, in which case the embedding returned is simply the canonical one sending 1 to 1). I just quickly wrote a function that does what I suggested and it works just fine and is quite quick.

[pbruin]

rewritten, based on 5.11.rc0 + #8335

[pbruin]

I was going to review this, but ended up wanting to change almost everything, so here is a new version. The doctests are the same as in the original, up to cosmetic changes.

The new implementation of this function is very short, as suggested by the above comments. It just computes the degree of the splitting field over the base field, and then calls the FiniteField_base.extension() method implemented by #8335.

The map flag from the original patch is currently not understood, but for more flexibility, any additional arguments are now passed to FiniteField_base.extension(), which would be the right place to implement the map parameter.

The currently unused parameters have been removed; this ticket will probably be merged before #2217, and that one might change dramatically for all we know.

[jdemeyer]

Conflicts with #2217.

[pbruin]

The map option now also works for finite fields, based on a new method FiniteFieldHomset._an_element_().

---

New commits:

​3058ab2

Trac 13379: splitting field function for polynomials over finite fields

[jdemeyer]

You should add doctests for the map parameter in extension.

[git]

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

​cc3e508

document "map" flag of FiniteField.extension()