#15390 closed enhancement (fixed)
roots of polynomials and eigenvalues of matrices over finite fields
Reported by:  vdelecroix  Owned by:  

Priority:  major  Milestone:  sage6.3 
Component:  number theory  Keywords:  sagedays55 
Cc:  pbruin, defeo  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  Miguel Marco 
Report Upstream:  N/A  Work issues:  wait for dependency 
Branch:  1eee50b (Commits)  Commit:  
Dependencies:  #14990, #16509  Stopgaps: 
Description (last modified by )
Based on #14990 we implement root computations in the algebraic closure of finite fields.
It should be nice to also adapt eigenvectors... (but we need before algebraic conjugates)
Currently finite subfields of an algebraic closure can not talk to each other (see in particular #16509). But hopefully, it is possible to compute roots without it!
Change History (33)
comment:1 Changed 7 years ago by
 Branch set to u/vdelecroix/15390
 Commit set to feacb88c63bcf762c346cd86bbff3eec3e8cd2f0
comment:2 Changed 7 years ago by
 Summary changed from roots of polynomials and eigenvalues of matrices over finite fields to roots of polynomials and eigenvalues/eigenvectors of matrices over finite fields
comment:3 Changed 7 years ago by
 Description modified (diff)
 Summary changed from roots of polynomials and eigenvalues/eigenvectors of matrices over finite fields to roots of polynomials and eigenvalues of matrices over finite fields
comment:4 Changed 7 years ago by
 Commit changed from feacb88c63bcf762c346cd86bbff3eec3e8cd2f0 to da8ba5d7b929cee46ebeb2a56e11e1ba71e6339c
Branch pushed to git repo; I updated commit sha1. New commits:
da8ba5d  fix tests 
comment:5 Changed 7 years ago by
 Commit changed from da8ba5d7b929cee46ebeb2a56e11e1ba71e6339c to a08ad2a432b6333cfbf02945a3338105e9300b49
Branch pushed to git repo; I updated commit sha1. New commits:
a08ad2a  Merge branch 'u/vdelecroix/15390' of ssh://trac.sagemath.org:2222/sage into roots_over_Fpbar 
6a724a4  fix tests 
98104de  implement roots over algebraically closed finite field and make eigenvalues work for matrices over finite fields 
e877037  implementation of roots over algebraic closures of finite fields 
ac93a01  remove the optional name from algebraic_closure examples 
comment:6 Changed 7 years ago by
 Status changed from new to needs_review
comment:7 Changed 7 years ago by
 Cc defeo added
comment:8 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:9 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:10 Changed 7 years ago by
 Status changed from needs_review to needs_work
 Work issues set to wait for dependency
comment:11 Changed 6 years ago by
 Commit changed from a08ad2a432b6333cfbf02945a3338105e9300b49 to c65e58e4aaa404ac4a40e196d7c296f34f208cd7
Branch pushed to git repo; I updated commit sha1. New commits:
c65e58e  trac #15390: roots and eigenvalues over finite fields

comment:12 Changed 6 years ago by
 Description modified (diff)
 Status changed from needs_work to needs_review
Hello,
Needs review!
I will not do eigenspaces since it needs the implementation of algebraic conjugates... for another ticket.
Vincent
comment:13 followup: ↓ 14 Changed 6 years ago by
Is there some reason why it shouldn't work for any finite field with a fixed embedding on the algebraic closure? (or the algebraic closure itself)
comment:14 in reply to: ↑ 13 Changed 6 years ago by
Replying to mmarco:
Is there some reason why it shouldn't work for any finite field with a fixed embedding on the algebraic closure? (or the algebraic closure itself)
It is rather independent of that ticket. As soon as you make work the embeddings of finite fields into algebraic closures, then there will be nothing to change in my code to make the roots and eigenvalues work.
EDIT: For the algebraic closure itself... I will have a look.
Vincent
comment:15 Changed 6 years ago by
 Status changed from needs_review to needs_work
Ok. I had a look and the reason is because the inclusions are only implemented between the subfields:
sage: K = GF(5).algebraic_closure() sage: K2, phi2 = K.subfield(2) sage: K4, phi4 = K.subfield(4) sage: z2 = K2.gen() sage: K4(z2) Traceback (most recent call last): ... TypeError: unable to coerce from a finite field other than the prime subfield
But the following works
sage: f24 = K.inclusion(2,4) sage: f24(K2.gen()) z4^3 + z4^2 + z4 + 3
I will at least fix the _roots_univariate_polynomial
using the inclusion morphism.
Vincent
comment:16 Changed 6 years ago by
 Description modified (diff)
comment:17 Changed 6 years ago by
 Commit changed from c65e58e4aaa404ac4a40e196d7c296f34f208cd7 to 5e525eb287b5baf52b966183f3704cbd41964e64
comment:19 Changed 6 years ago by
Looks good, but... shouldn't it make more sense to implement the factorization of polynomials? (it is basically what your code does).
We should get the roots for free from the factorization.
comment:20 Changed 6 years ago by
 Dependencies changed from #14990 to #14990, #16509
You are right, I will have a look where to implement the factor stuff.
I also set #16509 as a dependency since it makes more sense to use the smallest field possible for all the coefficients...
Vincent
comment:21 Changed 6 years ago by
 Commit changed from 5e525eb287b5baf52b966183f3704cbd41964e64 to 42c5808ea1a7961a9dd22de18a36f587aacc5e03
Branch pushed to git repo; I updated commit sha1. New commits:
42c5808  trac #15390: make factorization works as well

comment:22 Changed 6 years ago by
Since you are computing a factorization to get the roots, wouldn't it make more sense to go the other way around?. That is, write a complicated method that computes the factorization, and then just call it to get the roots.
It seems that what you ar doing is computing the factorization to get the roots, and then use the roots to compute the factorization.
comment:23 Changed 6 years ago by
Hey
The two things are equivalent in an algebraically closed field, right? And from the coding point of view, it is more natural the other way around. If you look at the part of the code which actually does the computation, I do not see where it looks more like a factorisation rather than a computation of roots
roots = [] # a list of pair (root,multiplicity) for g,m in P(new_coeffs).factor(): if g.degree() == 1: r = phi(g.constant_coefficient()) roots.append((r,m)) else: ll = l * g.degree() psi = self.inclusion(l, ll) FF, pphi = self.subfield(ll) gg = PolynomialRing(FF, 'x')(map(psi, g)) for r,_ in gg.roots(): # note: we know that multiplicity is 1 roots.append((pphi(r),m))
If you have an alternative proposition, propose it, but I really do not see what you mean. The only factor
which appears above is over the field where are defined the coefficients.
Vincent
comment:24 followup: ↓ 26 Changed 6 years ago by
Ok, if you really prefear it this way, you can leave it. Just check the commas (some of them don't have a space after, but they should).
comment:25 Changed 6 years ago by
 Commit changed from 42c5808ea1a7961a9dd22de18a36f587aacc5e03 to 1eee50b9282d2b007b7435af9a866d996369dd54
Branch pushed to git repo; I updated commit sha1. New commits:
1eee50b  trac 15390: put space after comma

comment:26 in reply to: ↑ 24 Changed 6 years ago by
Replying to mmarco:
Ok, if you really prefear it this way, you can leave it.
I do not prefer it this way, I just do not see how to do the other way around. If you know and think it is better, please provide a branch.
Just check the commas (some of them don't have a space after, but they should).
Why do they should?! These are just coding conventions and I do prefer
for i,j,k in my_list
rather than for i, j, k in my_list
. But as you saw I did it.
comment:27 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:28 Changed 6 years ago by
Thanks for the review!
comment:30 Changed 6 years ago by
 Reviewers set to mmarco
 Status changed from needs_work to positive_review
comment:31 Changed 6 years ago by
 Reviewers changed from mmarco to Miguel Marco
Miguel, you are supposed to sign with your real name not the trac account name
comment:32 Changed 6 years ago by
 Branch changed from u/vdelecroix/15390 to 1eee50b9282d2b007b7435af9a866d996369dd54
 Resolution set to fixed
 Status changed from positive_review to closed
comment:33 Changed 6 years ago by
 Commit 1eee50b9282d2b007b7435af9a866d996369dd54 deleted
See #16681 for a followup
Last 10 new commits: