Opened 5 years ago

Closed 4 years ago

Last modified 4 years ago

#15390 closed enhancement (fixed)

roots of polynomials and eigenvalues of matrices over finite fields

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-6.3
Component: number theory Keywords: sage-days55
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 vdelecroix)

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 5 years ago by vdelecroix

  • Branch set to u/vdelecroix/15390
  • Commit set to feacb88c63bcf762c346cd86bbff3eec3e8cd2f0

Last 10 new commits:

feacb88implement roots over algebraically closed finite field and make eigenvalues work for matrices over finite fields
d41d092implementation of roots over algebraic closures of finite fields
2432102allow no argument for .algebraic_closure()
a197d0dMerge branch 'u/vdelecroix/14990' of ssh://trac.sagemath.org:2222/sage into 14990
f232993fix the parent in pth_root and pth_power
0f4b895add examples to .cardinality()
d95f57fmore methods to algebraic elements
081c096Trac 14990: implement algebraic closures of finite fields
31045f7fix the parent in pth_root and pth_power
3d88af6add examples to .cardinality()

comment:2 Changed 5 years ago by vdelecroix

  • 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 5 years ago by vdelecroix

  • 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 5 years ago by git

  • Commit changed from feacb88c63bcf762c346cd86bbff3eec3e8cd2f0 to da8ba5d7b929cee46ebeb2a56e11e1ba71e6339c

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

da8ba5dfix tests

comment:5 Changed 5 years ago by git

  • Commit changed from da8ba5d7b929cee46ebeb2a56e11e1ba71e6339c to a08ad2a432b6333cfbf02945a3338105e9300b49

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

a08ad2aMerge branch 'u/vdelecroix/15390' of ssh://trac.sagemath.org:2222/sage into roots_over_Fpbar
6a724a4fix tests
98104deimplement roots over algebraically closed finite field and make eigenvalues work for matrices over finite fields
e877037implementation of roots over algebraic closures of finite fields
ac93a01remove the optional name from algebraic_closure examples

comment:6 Changed 5 years ago by vdelecroix

  • Status changed from new to needs_review

comment:7 Changed 5 years ago by defeo

  • Cc defeo added

comment:8 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:9 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:10 Changed 5 years ago by rws

  • Status changed from needs_review to needs_work
  • Work issues set to wait for dependency

comment:11 Changed 4 years ago by git

  • Commit changed from a08ad2a432b6333cfbf02945a3338105e9300b49 to c65e58e4aaa404ac4a40e196d7c296f34f208cd7

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

c65e58etrac #15390: roots and eigenvalues over finite fields

comment:12 Changed 4 years ago by vdelecroix

  • 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 follow-up: Changed 4 years ago by 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)

comment:14 in reply to: ↑ 13 Changed 4 years ago by vdelecroix

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

Last edited 4 years ago by vdelecroix (previous) (diff)

comment:15 Changed 4 years ago by vdelecroix

  • 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 4 years ago by vdelecroix

  • Description modified (diff)

comment:17 Changed 4 years ago by git

  • Commit changed from c65e58e4aaa404ac4a40e196d7c296f34f208cd7 to 5e525eb287b5baf52b966183f3704cbd41964e64

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

5f574e7trac #15390: merge sage 6.3.beta4
5e525ebtrac #15390: fix the case of polynomial over algebraic closure

comment:18 Changed 4 years ago by vdelecroix

  • Status changed from needs_work to needs_review

Ok. Now it works.

comment:19 Changed 4 years ago by mmarco

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 4 years ago by vdelecroix

  • 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 4 years ago by git

  • Commit changed from 5e525eb287b5baf52b966183f3704cbd41964e64 to 42c5808ea1a7961a9dd22de18a36f587aacc5e03

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

42c5808trac #15390: make factorization works as well

comment:22 Changed 4 years ago by mmarco

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 4 years ago by vdelecroix

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 follow-up: Changed 4 years ago by mmarco

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 4 years ago by git

  • Commit changed from 42c5808ea1a7961a9dd22de18a36f587aacc5e03 to 1eee50b9282d2b007b7435af9a866d996369dd54

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

1eee50btrac 15390: put space after comma

comment:26 in reply to: ↑ 24 Changed 4 years ago by vdelecroix

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 4 years ago by mmarco

  • Status changed from needs_review to positive_review

comment:28 Changed 4 years ago by vdelecroix

Thanks for the review!

comment:29 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work

reviewer name

comment:30 Changed 4 years ago by mmarco

  • Reviewers set to mmarco
  • Status changed from needs_work to positive_review

comment:31 Changed 4 years ago by vbraun

  • 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 4 years ago by vbraun

  • Branch changed from u/vdelecroix/15390 to 1eee50b9282d2b007b7435af9a866d996369dd54
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:33 Changed 4 years ago by vbraun

  • Commit 1eee50b9282d2b007b7435af9a866d996369dd54 deleted

See #16681 for a followup

Note: See TracTickets for help on using tickets.