#23333 closed enhancement (fixed)

Improve calculation of sigma invariants for projective morphisms

Reported by: bhutz Owned by:
Priority: minor Milestone: sage-8.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 bhutz

  • Authors set to Ben Hutz
  • Branch set to u/bhutz/sigma_inv
  • Commit set to 66160ebb2a2bec65c0fc85f5dfd82f01cdf7401b

New commits:

66160eb23333: improve sigma invariant for projective morphism

comment:2 Changed 14 months ago by bhutz

  • Status changed from new to needs_review

This is ready for a review.

comment:3 Changed 14 months ago by bhutz

  • 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 bhutz

  • 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 git

  • Commit changed from 66160ebb2a2bec65c0fc85f5dfd82f01cdf7401b to 225bfdd18033d3bd57b8ea1107d1f8696e5f6202

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

225bfdd23333: add parameter for type

comment:6 Changed 14 months ago by bhutz

  • 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 gjorgenson

That seems good to me also. I'll get started on reviewing the functionality.

comment:8 Changed 14 months ago by gjorgenson

  • 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 git

  • Commit changed from 225bfdd18033d3bd57b8ea1107d1f8696e5f6202 to 8467dc6b9a6ea4f7e0588369640d65fe70783144

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

8467dc623333: fixes from review

comment:10 Changed 13 months ago by bhutz

I think I fixed all those, so you can take another look.

comment:11 Changed 13 months ago by gjorgenson

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 n-periodic point that seems like it could also be a problem.

comment:12 Changed 13 months ago by bhutz

  • 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 git

  • Commit changed from 8467dc6b9a6ea4f7e0588369640d65fe70783144 to f9f8aed9f07e99d230840304f55e612ee21cd883

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

f9f8aed23333: change how periodic infinity is dealt with

comment:14 Changed 13 months ago by bhutz

  • Milestone changed from sage-8.0 to sage-8.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 bhutz

  • 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 git

  • Commit changed from f9f8aed9f07e99d230840304f55e612ee21cd883 to 35a1fec9aa138cabb6ddecd289e66254408fbe29

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

35a1fec23333: fix how cycle multipliers works

comment:17 Changed 13 months ago by bhutz

  • 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 gjorgenson

  • 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()*t

fails, but

sage: R.<s,t> = PolynomialRing(QQ, 2)
sage: f = s
sage: f.univariate_polynomial()*t

is 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 git

  • Commit changed from 35a1fec9aa138cabb6ddecd289e66254408fbe29 to 6709c7746c3236518ca25b04178a9f2f55abd64e

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

6709c7723333: minor code improvements

comment:20 Changed 13 months ago by bhutz

  • 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 gjorgenson

  • 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 bhutz

  • Component changed from algebraic geometry to dynamics

comment:23 Changed 13 months ago by vbraun

  • Branch changed from u/bhutz/sigma_inv to 6709c7746c3236518ca25b04178a9f2f55abd64e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.