Opened 14 months ago
Closed 13 months ago
#23333 closed enhancement (fixed)
Improve calculation of sigma invariants for projective morphisms
Reported by:  bhutz  Owned by:  

Priority:  minor  Milestone:  sage8.1 
Component:  dynamics  Keywords:  
Cc:  gjorgenson  Merged in:  
Authors:  Ben Hutz  Reviewers:  Grayson Jorgenson 
Report Upstream:  N/A  Work issues:  
Branch:  6709c77 (Commits)  Commit:  6709c7746c3236518ca25b04178a9f2f55abd64e 
Dependencies:  Stopgaps: 
Description
The sigma invariants are the elementary symmetric functions evaluated at the multipliers. Currently they are computed over QQbar which can be very time consuming. They can be computed via resultants which is much faster and includes maps defined over polynomial rings.
Change History (23)
comment:1 Changed 14 months ago by
 Branch set to u/bhutz/sigma_inv
 Commit set to 66160ebb2a2bec65c0fc85f5dfd82f01cdf7401b
comment:2 Changed 14 months ago by
 Status changed from new to needs_review
This is ready for a review.
comment:3 Changed 14 months ago by
 Status changed from needs_review to needs_work
err. I think the definition here is not right. There should be one multiplier per periodic point (with multiplicity), not one per cycle?
comment:4 Changed 14 months ago by
 Cc gjorgenson added
well, it seems both definitions are used in the world.
 define the sigma using every period n point (McMullen?, Silverman). Really they define it from the fixed points of the nth iterate.
 define the sigma via cycles (Milnor)
In both cases they define invariants of the moduli space, so it's not that one is right or wrong, they are just different. I'm tempted to introduce a 'type' parameter that takes values 'cycles' or 'points' to both this function and multiplier_spectrum.
What do you think?
comment:5 Changed 14 months ago by
 Commit changed from 66160ebb2a2bec65c0fc85f5dfd82f01cdf7401b to 225bfdd18033d3bd57b8ea1107d1f8696e5f6202
Branch pushed to git repo; I updated commit sha1. New commits:
225bfdd  23333: add parameter for type

comment:6 Changed 14 months ago by
 Status changed from needs_work to needs_review
I implemented it with the 'type' switch since both version appear in the literature.
comment:7 Changed 14 months ago by
That seems good to me also. I'll get started on reviewing the functionality.
comment:8 Changed 14 months ago by
 Reviewers set to Grayson Jorgenson
Ok I looked this over and did some testing. The new method of computing the sigma invariants appears to be correct (and much nicer than the previous implementation!), and everything seems to be working properly. I only found a few really minor issues:
In sigma_invariants:
 line 3725, multiplicity is spelled incorrectly (also occurs line 3565 in multiplier_spectra)
 line 3750, add another space around the hyphen (also occurs line 3579)
 line 3780, there is an extra newline
 need an input check in place to make sure the base ring is (or has its coefficients in) a number field
 perhaps put the "type" input check on line 3897 that can raise a value error with the other input checks at the beginning (same comment for multiplier_spectra)
 it also might be good to add an example with formal=True illustrating the different options type='cycle', 'point'
comment:9 Changed 13 months ago by
 Commit changed from 225bfdd18033d3bd57b8ea1107d1f8696e5f6202 to 8467dc6b9a6ea4f7e0588369640d65fe70783144
Branch pushed to git repo; I updated commit sha1. New commits:
8467dc6  23333: fixes from review

comment:10 Changed 13 months ago by
I think I fixed all those, so you can take another look.
comment:11 Changed 13 months ago by
Those changes look good. However I don't think the part of sigma_invariants that looks for a conjugation to avoid the point at infinity makes sense in positive characteristic:
sage: P.<x,y> = ProjectiveSpace(GF(3),1) sage: H = End(P) sage: f = H([x^2  2*y^2, y^2]) sage: f.sigma_invariants(1) Traceback (click to the left of this block for traceback) ... ZeroDivisionError: Inverse does not exist.
When working over a finite field, if it is possible to construct a morphism P1>P1 that has every point of P1 as a nperiodic point that seems like it could also be a problem.
comment:12 Changed 13 months ago by
 Status changed from needs_review to needs_work
Good catch. I'll need to rethink how I deal with that case.
comment:13 Changed 13 months ago by
 Commit changed from 8467dc6b9a6ea4f7e0588369640d65fe70783144 to f9f8aed9f07e99d230840304f55e612ee21cd883
Branch pushed to git repo; I updated commit sha1. New commits:
f9f8aed  23333: change how periodic infinity is dealt with

comment:14 Changed 13 months ago by
 Milestone changed from sage8.0 to sage8.1
 Status changed from needs_work to needs_review
ok. Here's another try at this. I'm no longer trying to move infinity out of the fixed points and instead am dealing with the multiplier at infinity and its multiplicities as a special case.
Interestingly, it looks like this exposed an issue with one of the earlier examples and also an issue when there are cycles of different periods with the same multiplier.
comment:15 Changed 13 months ago by
 Status changed from needs_review to needs_work
on further thought, I think this still fails to do the right thing where there are cycles of different length with the same multipliers.
comment:16 Changed 13 months ago by
 Commit changed from f9f8aed9f07e99d230840304f55e612ee21cd883 to 35a1fec9aa138cabb6ddecd289e66254408fbe29
Branch pushed to git repo; I updated commit sha1. New commits:
35a1fec  23333: fix how cycle multipliers works

comment:17 Changed 13 months ago by
 Status changed from needs_work to needs_review
I solved the cycle problem by building up the sigmas by divisor of n. Since the product of the dynatomic polys is the periodic point equation, this lets me assign a specific cycle length to each multiplier. Essentially it takes the formal period as the period. This has the advantage of being computable and always returns the same number of sigmas.
comment:18 Changed 13 months ago by
 Status changed from needs_review to needs_work
The new type='cycle' functionality looks good to me. While looking over the code I noticed just a few more superficial issues:
 line 3754: add period after "Default: False"
 line 3962: there's an extra newline
 the expressions of the form
e_inf = 1 while (y**e_inf).divides(fix_poly): e_inf += 1 e_inf = 1
could be shortened slightly to
e_inf = 0 while (y**(e_inf + 1)).divides(fix_poly): e_inf += 1
 change the code starting on line 3956 from
res = fix_poly.resultant(mult_poly, S.gen(0)).univariate_polynomial() #take infinty into consideration if inf_per.divides(n): res = res*((S.gen(1)  self.multiplier(inf, n)[0,0])**e_inf) res = res.univariate_polynomial()
to
res = fix_poly.resultant(mult_poly, S.gen(0)) #take infinty into consideration if inf_per.divides(n): res = res*((S.gen(1)  self.multiplier(inf, n)[0,0])**e_inf) res = res.univariate_polynomial()otherwise there is a weird multiplication issue:
sage: P.<x,y> = ProjectiveSpace(QQ,1) sage: H = End(P) sage: f = H([x^2 + x*y + y^2, y^2 + x*y]) sage: f.sigma_invariants(1)The same issue occurs in the formal=True block version of this code starting at 3925. It looks like this actually always occurs with multiplication with elements of the original polynomial ring after calling .univariate_polynomial() for a constant polynomial:
sage: R.<s,t> = PolynomialRing(QQ, 2) sage: f = R(1) sage: f.univariate_polynomial()*tfails, but
sage: R.<s,t> = PolynomialRing(QQ, 2) sage: f = s sage: f.univariate_polynomial()*tis fine.
 the lines of the form
res = res*((S.gen(1)  self.multiplier(inf, n)[0,0])**e_inf)
could be rewritten
res *= (S.gen(1)  self.multiplier(inf, n)[0,0])**e_inf
comment:19 Changed 13 months ago by
 Commit changed from 35a1fec9aa138cabb6ddecd289e66254408fbe29 to 6709c7746c3236518ca25b04178a9f2f55abd64e
Branch pushed to git repo; I updated commit sha1. New commits:
6709c77  23333: minor code improvements

comment:20 Changed 13 months ago by
 Status changed from needs_work to needs_review
Thanks. updated.
The issue with the univariate_polynomial of a constant is actually expected behavior. If you don't pass univeraite_polynomial a polynomial ring it creates it own. There is no reason it should be able to interact well with another polynomial ring. This is actually a little bit relevant to this ticket. In the new version I'm only calling univariate_polynomial once, so I don't rely anymore on Sage trying to 'do the right thing' in the background with multiplication of univariate and multivariate polynomial rings.
comment:21 Changed 13 months ago by
 Status changed from needs_review to positive_review
Ok that makes sense. With these new changes everything looks good to me.
comment:22 Changed 13 months ago by
 Component changed from algebraic geometry to dynamics
comment:23 Changed 13 months ago by
 Branch changed from u/bhutz/sigma_inv to 6709c7746c3236518ca25b04178a9f2f55abd64e
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
23333: improve sigma invariant for projective morphism