Dynamical systems on projective schemes

A dynamical system of projective schemes determined by homogeneous polynomials functions that define what the morphism does on points in the ambient projective space.

The main constructor functions are given by DynamicalSystem and DynamicalSystem_projective. The constructors function can take either polynomials or a morphism from which to construct a dynamical system. If the domain is not specified, it is constructed. However, if you plan on working with points or subvarieties in the domain, it recommended to specify the domain.

The initialization checks are always performed by the constructor functions. It is possible, but not recommended, to skip these checks by calling the class initialization directly.

AUTHORS:

  • David Kohel, William Stein
  • William Stein (2006-02-11): fixed bug where P(0,0,0) was allowed as a projective point.
  • Volker Braun (2011-08-08): Renamed classes, more documentation, misc cleanups.
  • Ben Hutz (2013-03) iteration functionality and new directory structure for affine/projective, height functionality
  • Brian Stout, Ben Hutz (Nov 2013) - added minimal model functionality
  • Dillon Rose (2014-01): Speed enhancements
  • Ben Hutz (2015-11): iteration of subschemes
  • Ben Hutz (2017-7): relocate code and create class
sage.dynamics.arithmetic_dynamics.projective_ds.DynamicalSystem_projective

A dynamical system of projective schemes determined by homogeneous polynomials that define what the morphism does on points in the ambient projective space.

Warning

You should not create objects of this class directly because no type or consistency checking is performed. The preferred method to construct such dynamical systems is to use DynamicalSystem_projective() function

INPUT:

  • morphism_or_polys – a SchemeMorphism, a polynomial, a rational function, or a list or tuple of homogeneous polynomials.

  • domain – optional projective space or projective subscheme.

  • names – optional tuple of strings to be used as coordinate names for a projective space that is constructed; defaults to 'X','Y'.

    The following combinations of morphism_or_polys and domain are meaningful:

    • morphism_or_polys is a SchemeMorphism; domain is ignored in this case.
    • morphism_or_polys is a list of homogeneous polynomials that define a rational endomorphism of domain.
    • morphism_or_polys is a list of homogeneous polynomials and domain is unspecified; domain is then taken to be the projective space of appropriate dimension over the common base ring, if one exists, of the elements of morphism_or_polys.
    • morphism_or_polys is a single polynomial or rational function; domain is ignored and taken to be a 1-dimensional projective space over the base ring of morphism_or_polys with coordinate names given by names.

OUTPUT: DynamicalSystem_projective.

EXAMPLES:

sage: P1.<x,y> = ProjectiveSpace(QQ,1)
sage: DynamicalSystem_projective([y, 2*x])
Dynamical System of Projective Space of dimension 1 over Rational Field
  Defn: Defined on coordinates by sending (x : y) to
        (y : 2*x)

We can define dynamical systems on \(P^1\) by giving a polynomial or rational function:

sage: R.<t> = QQ[]
sage: DynamicalSystem_projective(t^2 - 3)
Dynamical System of Projective Space of dimension 1 over Rational Field
  Defn: Defined on coordinates by sending (X : Y) to
        (X^2 - 3*Y^2 : Y^2)
sage: DynamicalSystem_projective(1/t^2)
Dynamical System of Projective Space of dimension 1 over Rational Field
  Defn: Defined on coordinates by sending (X : Y) to
        (Y^2 : X^2)
sage: R.<x> = PolynomialRing(QQ,1)
sage: DynamicalSystem_projective(x^2, names=['a','b'])
Dynamical System of Projective Space of dimension 1 over Rational Field
  Defn: Defined on coordinates by sending (a : b) to
        (a^2 : b^2)

Symbolic Ring elements are not allowed:

sage: x,y = var('x,y')
sage: DynamicalSystem_projective([x^2,y^2])
Traceback (most recent call last):
...
ValueError: [x^2, y^2] must be elements of a polynomial ring
sage: R.<x> = PolynomialRing(QQ,1)
sage: DynamicalSystem_projective(x^2)
Dynamical System of Projective Space of dimension 1 over Rational Field
  Defn: Defined on coordinates by sending (X : Y) to
        (X^2 : Y^2)
sage: R.<t> = PolynomialRing(QQ)
sage: P.<x,y,z> = ProjectiveSpace(R, 2)
sage: X = P.subscheme([x])
sage: DynamicalSystem_projective([x^2, t*y^2, x*z], domain=X)
Dynamical System of Closed subscheme of Projective Space of dimension
2 over Univariate Polynomial Ring in t over Rational Field defined by:
  x
  Defn: Defined on coordinates by sending (x : y : z) to
        (x^2 : t*y^2 : x*z)

When elements of the quotient ring are used, they are reduced:

sage: P.<x,y,z> = ProjectiveSpace(CC, 2)
sage: X = P.subscheme([x-y])
sage: u,v,w = X.coordinate_ring().gens()
sage: DynamicalSystem_projective([u^2, v^2, w*u], domain=X)
Dynamical System of Closed subscheme of Projective Space of dimension
2 over Complex Field with 53 bits of precision defined by:
  x - y
  Defn: Defined on coordinates by sending (x : y : z) to
        (y^2 : y^2 : y*z)

We can also compute the forward image of subschemes through elimination. In particular, let \(X = V(h_1,\ldots, h_t)\) and define the ideal \(I = (h_1,\ldots,h_t,y_0-f_0(\bar{x}), \ldots, y_n-f_n(\bar{x}))\). Then the elimination ideal \(I_{n+1} = I \cap K[y_0,\ldots,y_n]\) is a homogeneous ideal and \(f(X) = V(I_{n+1})\):

sage: P.<x,y,z> = ProjectiveSpace(QQ, 2)
sage: f = DynamicalSystem_projective([(x-2*y)^2, (x-2*z)^2, x^2])
sage: X = P.subscheme(y-z)
sage: f(f(f(X)))
Closed subscheme of Projective Space of dimension 2 over Rational Field
defined by:
  y - z
sage: P.<x,y,z,w> = ProjectiveSpace(QQ, 3)
sage: f = DynamicalSystem_projective([(x-2*y)^2, (x-2*z)^2, (x-2*w)^2, x^2])
sage: f(P.subscheme([x,y,z]))
Closed subscheme of Projective Space of dimension 3 over Rational Field
defined by:
  w,
  y,
  x
sage: T.<x,y,z,w,u> = ProductProjectiveSpaces([2, 1], QQ)
sage: DynamicalSystem_projective([x^2*u, y^2*w, z^2*u, w^2, u^2], domain=T)
Dynamical System of Product of projective spaces P^2 x P^1 over Rational Field
  Defn: Defined by sending (x : y : z , w : u) to
        (x^2*u : y^2*w : z^2*u , w^2 : u^2).
class sage.dynamics.arithmetic_dynamics.projective_ds.DynamicalSystem_projective_field(polys, domain)

Bases: sage.dynamics.arithmetic_dynamics.projective_ds.DynamicalSystem_projective, sage.schemes.projective.projective_morphism.SchemeMorphism_polynomial_projective_space_field

all_rational_preimages(points)

Given a set of rational points in the domain of this dynamical system, return all the rational preimages of those points.

In others words, all the rational points which have some iterate in the set points. This function repeatedly calls rational_preimages. If the degree is at least two, by Northocott, this is always a finite set. The map must be defined over number fields and be an endomorphism.

INPUT:

  • points – a list of rational points in the domain of this map

OUTPUT: a list of rational points in the domain of this map

EXAMPLES:

sage: P.<x,y> = ProjectiveSpace(QQ,1)
sage: f = DynamicalSystem_projective([16*x^2 - 29*y^2, 16*y^2])
sage: sorted(f.all_rational_preimages([P(-1,4)]))
[(-7/4 : 1), (-5/4 : 1), (-3/4 : 1), (-1/4 : 1), (1/4 : 1), (3/4 : 1),
(5/4 : 1), (7/4 : 1)]
sage: P.<x,y,z> = ProjectiveSpace(QQ,2)
sage: f = DynamicalSystem_projective([76*x^2 - 180*x*y + 45*y^2 + 14*x*z + 45*y*z - 90*z^2, 67*x^2 - 180*x*y - 157*x*z + 90*y*z, -90*z^2])
sage: sorted(f.all_rational_preimages([P(-9,-4,1)]))
[(-9 : -4 : 1), (0 : -1 : 1), (0 : 0 : 1), (0 : 1 : 1), (0 : 4 : 1),
 (1 : 0 : 1), (1 : 1 : 1), (1 : 2 : 1), (1 : 3 : 1)]

A non-periodic example

sage: P.<x,y> = ProjectiveSpace(QQ,1)
sage: f = DynamicalSystem_projective([x^2 + y^2, 2*x*y])
sage: sorted(f.all_rational_preimages([P(17,15)]))
[(1/3 : 1), (3/5 : 1), (5/3 : 1), (3 : 1)]

A number field example:

sage: z = QQ['z'].0
sage: K.<w> = NumberField(z^3 + (z^2)/4 - (41/16)*z + 23/64);
sage: P.<x,y> = ProjectiveSpace(K,1)
sage: f = DynamicalSystem_projective([16*x^2 - 29*y^2, 16*y^2])
sage: f.all_rational_preimages([P(16*w^2 - 29,16)])
[(-w^2 + 21/16 : 1),
 (w : 1),
 (w + 1/2 : 1),
 (w^2 + w - 33/16 : 1),
 (-w^2 - w + 25/16 : 1),
 (w^2 - 21/16 : 1),
 (-w^2 - w + 33/16 : 1),
 (-w : 1),
 (-w - 1/2 : 1),
 (-w^2 + 29/16 : 1),
 (w^2 - 29/16 : 1),
 (w^2 + w - 25/16 : 1)]
sage: K.<w> = QuadraticField(3)
sage: P.<u,v> = ProjectiveSpace(K,1)
sage: f = DynamicalSystem_projective([u^2+v^2, v^2])
sage: f.all_rational_preimages(P(4))
[(-w : 1), (w : 1)]
conjugating_set(other)

Return the set of elements in PGL that conjugates one dynamical system to the other.

Given two nonconstant rational functions of equal degree determine to see if there is an element of PGL that conjugates one rational function to another. It does this by taking the fixed points of one map and mapping them to all unique permutations of the fixed points of the other map. If there are not enough fixed points the function compares the mapping between rational preimages of fixed points and the rational preimages of the preimages of fixed points until there are enough points; such that there are \(n+2\) points with all \(n+1\) subsets linearly independent.

ALGORITHM:

Implementing invariant set algorithm from the paper [FMV2014]. Given that the set of \(n\) th preimages of fixed points is invariant under conjugation find all elements of PGL that take one set to another.

INPUT:

  • other – a nonconstant rational function of same degree as self

OUTPUT:

Set of conjugating \(n+1\) by \(n+1\) matrices.

AUTHORS:

  • Original algorithm written by Xander Faber, Michelle Manes, Bianca Viray [FMV2014].
  • Implimented by Rebecca Lauren Miller, as part of GSOC 2016.

EXAMPLES:

sage: P.<x,y> = ProjectiveSpace(QQ,1)
sage: f = DynamicalSystem_projective([x^2 - 2*y^2, y^2])
sage: m = matrix(QQbar, 2, 2, [-1, 3, 2, 1])
sage: g = f.conjugate(m)
sage: f.conjugating_set(g)
[
[-1  3]
[ 2  1]
]
sage: K.<w> = QuadraticField(-1)
sage: P.<x,y> = ProjectiveSpace(K,1)
sage: f = DynamicalSystem_projective([x^2 + y^2, x*y])
sage: m = matrix(K, 2, 2, [1, 1, 2, 1])
sage: g = f.conjugate(m)
sage: f.conjugating_set(g) # long time
[
[1 1]  [-1 -1]
[2 1], [ 2  1]
]
sage: K.<i> = QuadraticField(-1)
sage: P.<x,y> = ProjectiveSpace(K,1)
sage: D8 = DynamicalSystem_projective([y^3, x^3])
sage: D8.conjugating_set(D8) # long time
[
[1 0]  [0 1]  [ 0 -i]  [i 0]  [ 0 -1]  [-1  0]  [-i  0]  [0 i]
[0 1], [1 0], [ 1  0], [0 1], [ 1  0], [ 0  1], [ 0  1], [1 0]
]
sage: P.<x,y> = ProjectiveSpace(QQ,1)
sage: D8 = DynamicalSystem_projective([y^2, x^2])
sage: D8.conjugating_set(D8)
Traceback (most recent call last):
...
ValueError: not enough rational preimages
sage: P.<x,y> = ProjectiveSpace(GF(7),1)
sage: D6 = DynamicalSystem_projective([y^2, x^2])
sage: D6.conjugating_set(D6)
[
[1 0]  [0 1]  [0 2]  [4 0]  [2 0]  [0 4]
[0 1], [1 0], [1 0], [0 1], [0 1], [1 0]
]
sage: P.<x,y,z> = ProjectiveSpace(QQ,2)
sage: f = DynamicalSystem_projective([x^2 + x*z, y^2, z^2])
sage: f.conjugating_set(f) # long time
[
[1 0 0]
[0 1 0]
[0 0 1]
]
connected_rational_component(P, n=0)

Computes the connected component of a rational preperiodic point P by this dynamical system.

Will work for non-preperiodic points if n is positive. Otherwise this will not terminate.

INPUT:

  • P – a rational preperiodic point of this map
  • n – (default: 0) integer; maximum distance from P to branch out; a value of 0 indicates no bound

OUTPUT:

A list of points connected to P up to the specified distance.

EXAMPLES:

sage: R.<x> = PolynomialRing(QQ)
sage: K.<w> = NumberField(x^3+1/4*x^2-41/16*x+23/64)
sage: PS.<x,y> = ProjectiveSpace(1,K)
sage: f = DynamicalSystem_projective([x^2 - 29/16*y^2, y^2])
sage: P = PS([w,1])
sage: f.connected_rational_component(P)
[(w : 1),
 (w^2 - 29/16 : 1),
 (-w^2 - w + 25/16 : 1),
 (w^2 + w - 25/16 : 1),
 (-w : 1),
 (-w^2 + 29/16 : 1),
 (w + 1/2 : 1),
 (-w - 1/2 : 1),
 (-w^2 + 21/16 : 1),
 (w^2 - 21/16 : 1),
 (w^2 + w - 33/16 : 1),
 (-w^2 - w + 33/16 : 1)]
sage: PS.<x,y,z> = ProjectiveSpace(2,QQ)
sage: f = DynamicalSystem_projective([x^2 - 21/16*z^2, y^2-2*z^2, z^2])
sage: P = PS([17/16,7/4,1])
sage: f.connected_rational_component(P,3)
[(17/16 : 7/4 : 1),
 (-47/256 : 17/16 : 1),
 (-83807/65536 : -223/256 : 1),
 (-17/16 : -7/4 : 1),
 (-17/16 : 7/4 : 1),
 (17/16 : -7/4 : 1),
 (1386468673/4294967296 : -81343/65536 : 1),
 (-47/256 : -17/16 : 1),
 (47/256 : -17/16 : 1),
 (47/256 : 17/16 : 1),
 (-1/2 : -1/2 : 1),
 (-1/2 : 1/2 : 1),
 (1/2 : -1/2 : 1),
 (1/2 : 1/2 : 1)]
is_conjugate(other)

Return whether or not two dynamical systems are conjugate.

ALGORITHM:

Implementing invariant set algorithm from the paper [FMV2014]. Given that the set of \(n\) th preimages is invariant under conjugation this function finds whether two maps are conjugate.

INPUT:

  • other – a nonconstant rational function of same degree as self

OUTPUT: boolean

AUTHORS:

  • Original algorithm written by Xander Faber, Michelle Manes, Bianca Viray [FMV2014].
  • Implimented by Rebecca Lauren Miller as part of GSOC 2016.

EXAMPLES:

sage: K.<w> = CyclotomicField(3)
sage: P.<x,y> = ProjectiveSpace(K,1)
sage: D8 = DynamicalSystem_projective([y^2, x^2])
sage: D8.is_conjugate(D8)
True
sage: set_verbose(None)
sage: P.<x,y> = ProjectiveSpace(QQbar,1)
sage: f = DynamicalSystem_projective([x^2 + x*y,y^2])
sage: m = matrix(QQbar, 2, 2, [1, 1, 2, 1])
sage: g = f.conjugate(m)
sage: f.is_conjugate(g) # long time
True
sage: P.<x,y> = ProjectiveSpace(GF(5),1)
sage: f = DynamicalSystem_projective([x^3 + x*y^2,y^3])
sage: m = matrix(GF(5), 2, 2, [1, 3, 2, 9])
sage: g = f.conjugate(m)
sage: f.is_conjugate(g)
True
sage: P.<x,y> = ProjectiveSpace(QQ,1)
sage: f = DynamicalSystem_projective([x^2 + x*y,y^2])
sage: g = DynamicalSystem_projective([x^3 + x^2*y, y^3])
sage: f.is_conjugate(g)
False
sage: P.<x,y> = ProjectiveSpace(QQ,1)
sage: f = DynamicalSystem_projective([x^2 + x*y, y^2])
sage: g = DynamicalSystem_projective([x^2 - 2*y^2, y^2])
sage: f.is_conjugate(g)
False
is_polynomial()

Check to see if the dynamical system has a totally ramified fixed point.

The function must be defined over an absolute number field or a finite field.

OUTPUT: boolean

EXAMPLES:

sage: R.<x> = QQ[]
sage: K.<w> = QuadraticField(7)
sage: P.<x,y> = ProjectiveSpace(K, 1)
sage: f = DynamicalSystem_projective([x**2 + 2*x*y - 5*y**2, 2*x*y])
sage: f.is_polynomial()
False
sage: R.<x> = QQ[]
sage: K.<w> = QuadraticField(7)
sage: P.<x,y> = ProjectiveSpace(K, 1)
sage: f = DynamicalSystem_projective([x**2 - 7*x*y, 2*y**2])
sage: m = matrix(K, 2, 2, [w, 1, 0, 1])
sage: f = f.conjugate(m)
sage: f.is_polynomial()
True
sage: K.<w> = QuadraticField(4/27)
sage: P.<x,y> = ProjectiveSpace(K,1)
sage: f = DynamicalSystem_projective([x**3 + w*y^3,x*y**2])
sage: f.is_polynomial()
False
sage: K = GF(3**2, prefix='w')
sage: P.<x,y> = ProjectiveSpace(K,1)
sage: f = DynamicalSystem_projective([x**2 + K.gen()*y**2, x*y])
sage: f.is_polynomial()
False
sage: PS.<x,y> = ProjectiveSpace(QQ, 1)
sage: f = DynamicalSystem_projective([6*x^2+12*x*y+7*y^2, 12*x*y + 42*y^2])
sage: f.is_polynomial()
False
lift_to_rational_periodic(points_modp, B=None)

Given a list of points in projective space over \(\GF{p}\), determine if they lift to \(\QQ\)-rational periodic points.

The map must be an endomorphism of projective space defined over \(\QQ\).

ALGORITHM:

Use Hensel lifting to find a \(p\)-adic approximation for that rational point. The accuracy needed is determined by the height bound B. Then apply the LLL algorithm to determine if the lift corresponds to a rational point.

If the point is a point of high multiplicity (multiplier 1), the procedure can be very slow.

INPUT:

  • points_modp – a list or tuple of pairs containing a point in projective space over \(\GF{p}\) and the possible period
  • B – (optional) a positive integer; the height bound for a rational preperiodic point

OUTPUT: a list of projective points

EXAMPLES:

sage: P.<x,y> = ProjectiveSpace(QQ,1)
sage: f = DynamicalSystem_projective([x^2 - y^2, y^2])
sage: f.lift_to_rational_periodic([[P(0,1).change_ring(GF(7)), 4]])
[[(0 : 1), 2]]
There may be multiple points in the lift.
sage: P.<x,y> = ProjectiveSpace(QQ,1)
sage: f = DynamicalSystem_projective([-5*x^2 + 4*y^2, 4*x*y])
sage: f.lift_to_rational_periodic([[P(1,0).change_ring(GF(3)), 1]]) # long time
[[(1 : 0), 1], [(2/3 : 1), 1], [(-2/3 : 1), 1]]
sage: P.<x,y> = ProjectiveSpace(QQ,1)
sage: f = DynamicalSystem_projective([16*x^2 - 29*y^2, 16*y^2])
sage: f.lift_to_rational_periodic([[P(3,1).change_ring(GF(13)), 3]])
[[(-1/4 : 1), 3]]
sage: P.<x,y,z> = ProjectiveSpace(QQ, 2)
sage: f = DynamicalSystem_projective([76*x^2 - 180*x*y + 45*y^2 + 14*x*z + 45*y*z - 90*z^2, 67*x^2 - 180*x*y - 157*x*z + 90*y*z, -90*z^2])
sage: f.lift_to_rational_periodic([[P(14,19,1).change_ring(GF(23)), 9]]) # long time
[[(-9 : -4 : 1), 9]]
normal_form(return_conjugation=False)

Return a normal form in the moduli space of dynamical systems.

Currently implemented only for polynomials. The totally ramified fixed point is moved to infinity and the map is conjugated to the form \(x^n + a_{n-2} x^{n-2} + \cdots + a_{0}\). Note that for finite fields we can only remove the \((n-1)\)-st term when the characteristic does not divide \(n\).

INPUT:

  • return_conjugation – (default: False) boolean; if True, then return the conjugation element of PGL along with the embedding into the new field

OUTPUT:

  • SchemeMorphism_polynomial
  • (optional) an element of PGL as a matrix
  • (optional) the field embedding

EXAMPLES:

sage: P.<x,y> = ProjectiveSpace(QQ, 1)
sage: f = DynamicalSystem_projective([x^2 + 2*x*y - 5*x^2, 2*x*y])
sage: f.normal_form()
Traceback (most recent call last):
...
NotImplementedError: map is not a polynomial
sage: R.<x> = QQ[]
sage: K.<w> = NumberField(x^2 - 5)
sage: P.<x,y> = ProjectiveSpace(K,1)
sage: f = DynamicalSystem_projective([x^2 + w*x*y, y^2])
sage: g,m,psi = f.normal_form(return_conjugation = True);m
[     1 -1/2*w]
[     0      1]
sage: f.change_ring(psi).conjugate(m) == g
True
sage: P.<x,y> = ProjectiveSpace(QQ,1)
sage: f = DynamicalSystem_projective([13*x^2 + 4*x*y + 3*y^2, 5*y^2])
sage: f.normal_form()
Dynamical System of Projective Space of dimension 1 over Rational Field
  Defn: Defined on coordinates by sending (x : y) to
        (5*x^2 + 9*y^2 : 5*y^2)
sage: K = GF(3^3, prefix = 'w')
sage: P.<x,y> = ProjectiveSpace(K,1)
sage: f = DynamicalSystem_projective([x^3 + 2*x^2*y + 2*x*y^2 + K.gen()*y^3, y^3])
sage: f.normal_form()
Dynamical System of Projective Space of dimension 1 over Finite Field in w3 of size 3^3
      Defn: Defined on coordinates by sending (x : y) to
            (x^3 + x^2*y + x*y^2 + (-w3)*y^3 : y^3)
rational_periodic_points(**kwds)

Determine the set of rational periodic points for this dynamical system.

The map must be defined over \(\QQ\) and be an endomorphism of projective space. If the map is a polynomial endomorphism of \(\mathbb{P}^1\), i.e. has a totally ramified fixed point, then the base ring can be an absolute number field. This is done by passing to the Weil restriction.

The default parameter values are typically good choices for \(\mathbb{P}^1\). If you are having trouble getting a particular map to finish, try first computing the possible periods, then try various different lifting_prime values.

ALGORITHM:

Modulo each prime of good reduction \(p\) determine the set of periodic points modulo \(p\). For each cycle modulo \(p\) compute the set of possible periods (\(mrp^e\)). Take the intersection of the list of possible periods modulo several primes of good reduction to get a possible list of minimal periods of rational periodic points. Take each point modulo \(p\) associated to each of these possible periods and try to lift it to a rational point with a combination of \(p\)-adic approximation and the LLL basis reduction algorithm.

See [Hutz2015].

INPUT:

kwds:

  • prime_bound – (default: [1,20]) a pair (list or tuple) of positive integers that represent the limits of primes to use in the reduction step or an integer that represents the upper bound
  • lifting_prime – (default: 23) a prime integer; argument that specifies modulo which prime to try and perform the lifting
  • periods – (optional) a list of positive integers that is the list of possible periods
  • bad_primes – (optional) a list or tuple of integer primes; the primes of bad reduction
  • ncpus – (default: all cpus) number of cpus to use in parallel

OUTPUT: a list of rational points in projective space

EXAMPLES:

sage: P.<x,y> = ProjectiveSpace(QQ,1)
sage: f = DynamicalSystem_projective([x^2-3/4*y^2, y^2])
sage: sorted(f.rational_periodic_points(prime_bound=20, lifting_prime=7)) # long time
[(-1/2 : 1), (1 : 0), (3/2 : 1)]
sage: P.<x,y,z> = ProjectiveSpace(QQ,2)
sage: f = DynamicalSystem_projective([2*x^3 - 50*x*z^2 + 24*z^3,
....:                                 5*y^3 - 53*y*z^2 + 24*z^3, 24*z^3])
sage: sorted(f.rational_periodic_points(prime_bound=[1,20])) # long time
[(-3 : -1 : 1), (-3 : 0 : 1), (-3 : 1 : 1), (-3 : 3 : 1), (-1 : -1 : 1),
 (-1 : 0 : 1), (-1 : 1 : 1), (-1 : 3 : 1), (0 : 1 : 0), (1 : -1 : 1),
 (1 : 0 : 0), (1 : 0 : 1), (1 : 1 : 1), (1 : 3 : 1), (3 : -1 : 1),
 (3 : 0 : 1), (3 : 1 : 1), (3 : 3 : 1), (5 : -1 : 1), (5 : 0 : 1),
 (5 : 1 : 1), (5 : 3 : 1)]
sage: P.<x,y> = ProjectiveSpace(QQ,1)
sage: f = DynamicalSystem_projective([-5*x^2 + 4*y^2, 4*x*y])
sage: sorted(f.rational_periodic_points()) # long time
[(-2 : 1), (-2/3 : 1), (2/3 : 1), (1 : 0), (2 : 1)]
sage: R.<x> = QQ[]
sage: K.<w> = NumberField(x^2-x+1)
sage: P.<u,v> = ProjectiveSpace(K,1)
sage: f = DynamicalSystem_projective([u^2 + v^2,v^2])
sage: f.rational_periodic_points()
[(w : 1), (1 : 0), (-w + 1 : 1)]
sage: R.<x> = QQ[]
sage: K.<w> = NumberField(x^2-x+1)
sage: P.<u,v> = ProjectiveSpace(K,1)
sage: f = DynamicalSystem_projective([u^2+v^2,u*v])
sage: f.rational_periodic_points()
Traceback (most recent call last):
...
NotImplementedError: rational periodic points for number fields only implemented for polynomials
rational_preperiodic_graph(**kwds)

Determine the directed graph of the rational preperiodic points for this dynamical system.

The map must be defined over \(\QQ\) and be an endomorphism of projective space. If this map is a polynomial endomorphism of \(\mathbb{P}^1\), i.e. has a totally ramified fixed point, then the base ring can be an absolute number field. This is done by passing to the Weil restriction.

ALGORITHM:

  • Determines the list of possible periods.
  • Determines the rational periodic points from the possible periods.
  • Determines the rational preperiodic points from the rational periodic points by determining rational preimages.

INPUT:

kwds:

  • prime_bound – (default: [1, 20]) a pair (list or tuple) of positive integers that represent the limits of primes to use in the reduction step or an integer that represents the upper bound
  • lifting_prime – (default: 23) a prime integer; specifies modulo which prime to try and perform the lifting
  • periods – (optional) a list of positive integers that is the list of possible periods
  • bad_primes – (optional) a list or tuple of integer primes; the primes of bad reduction
  • ncpus – (default: all cpus) number of cpus to use in parallel

OUTPUT:

A digraph representing the orbits of the rational preperiodic points in projective space.

EXAMPLES:

sage: PS.<x,y> = ProjectiveSpace(1,QQ)
sage: f = DynamicalSystem_projective([7*x^2 - 28*y^2, 24*x*y])
sage: f.rational_preperiodic_graph()
Looped digraph on 12 vertices
sage: PS.<x,y> = ProjectiveSpace(1,QQ)
sage: f = DynamicalSystem_projective([-3/2*x^3 +19/6*x*y^2, y^3])
sage: f.rational_preperiodic_graph(prime_bound=[1,8])
Looped digraph on 12 vertices
sage: PS.<x,y,z> = ProjectiveSpace(2,QQ)
sage: f = DynamicalSystem_projective([2*x^3 - 50*x*z^2 + 24*z^3,
....:                                 5*y^3 - 53*y*z^2 + 24*z^3, 24*z^3])
sage: f.rational_preperiodic_graph(prime_bound=[1,11], lifting_prime=13) # long time
Looped digraph on 30 vertices
sage: K.<w> = QuadraticField(-3)
sage: P.<x,y> = ProjectiveSpace(K,1)
sage: f = DynamicalSystem_projective([x^2+y^2, y^2])
sage: f.rational_preperiodic_graph() # long time
Looped digraph on 5 vertices
rational_preperiodic_points(**kwds)

Determine the set of rational preperiodic points for this dynamical system.

The map must be defined over \(\QQ\) and be an endomorphism of projective space. If the map is a polynomial endomorphism of \(\mathbb{P}^1\), i.e. has a totally ramified fixed point, then the base ring can be an absolute number field. This is done by passing to the Weil restriction.

The default parameter values are typically good choices for \(\mathbb{P}^1\). If you are having trouble getting a particular map to finish, try first computing the possible periods, then try various different values for lifting_prime.

ALGORITHM:

  • Determines the list of possible periods.
  • Determines the rational periodic points from the possible periods.
  • Determines the rational preperiodic points from the rational periodic points by determining rational preimages.

INPUT:

kwds:

  • prime_bound – (default: [1, 20]) a pair (list or tuple) of positive integers that represent the limits of primes to use in the reduction step or an integer that represents the upper bound
  • lifting_prime – (default: 23) a prime integer; specifies modulo which prime to try and perform the lifting
  • periods – (optional) a list of positive integers that is the list of possible periods
  • bad_primes – (optional) a list or tuple of integer primes; the primes of bad reduction
  • ncpus – (default: all cpus) number of cpus to use in parallel

OUTPUT: a list of rational points in projective space

EXAMPLES:

sage: PS.<x,y> = ProjectiveSpace(1,QQ)
sage: f = DynamicalSystem_projective([x^2 -y^2, 3*x*y])
sage: sorted(f.rational_preperiodic_points())
[(-2 : 1), (-1 : 1), (-1/2 : 1), (0 : 1), (1/2 : 1), (1 : 0), (1 : 1),
(2 : 1)]
sage: PS.<x,y> = ProjectiveSpace(1,QQ)
sage: f = DynamicalSystem_projective([5*x^3 - 53*x*y^2 + 24*y^3, 24*y^3])
sage: sorted(f.rational_preperiodic_points(prime_bound=10))
[(-1 : 1), (0 : 1), (1 : 0), (1 : 1), (3 : 1)]
sage: PS.<x,y,z> = ProjectiveSpace(2,QQ)
sage: f = DynamicalSystem_projective([x^2 - 21/16*z^2, y^2-2*z^2, z^2])
sage: sorted(f.rational_preperiodic_points(prime_bound=[1,8], lifting_prime=7, periods=[2])) # long time
[(-5/4 : -2 : 1), (-5/4 : -1 : 1), (-5/4 : 0 : 1), (-5/4 : 1 : 1), (-5/4
: 2 : 1), (-1/4 : -2 : 1), (-1/4 : -1 : 1), (-1/4 : 0 : 1), (-1/4 : 1 :
1), (-1/4 : 2 : 1), (1/4 : -2 : 1), (1/4 : -1 : 1), (1/4 : 0 : 1), (1/4
: 1 : 1), (1/4 : 2 : 1), (5/4 : -2 : 1), (5/4 : -1 : 1), (5/4 : 0 : 1),
(5/4 : 1 : 1), (5/4 : 2 : 1)]
sage: K.<w> = QuadraticField(33)
sage: PS.<x,y> = ProjectiveSpace(K,1)
sage: f = DynamicalSystem_projective([x^2-71/48*y^2, y^2])
sage: sorted(f.rational_preperiodic_points()) # long time
[(-1/12*w - 1 : 1),
 (-1/6*w - 1/4 : 1),
 (-1/12*w - 1/2 : 1),
 (-1/6*w + 1/4 : 1),
 (1/12*w - 1 : 1),
 (1/12*w - 1/2 : 1),
 (-1/12*w + 1/2 : 1),
 (-1/12*w + 1 : 1),
 (1/6*w - 1/4 : 1),
 (1/12*w + 1/2 : 1),
 (1 : 0),
 (1/6*w + 1/4 : 1),
 (1/12*w + 1 : 1)]
class sage.dynamics.arithmetic_dynamics.projective_ds.DynamicalSystem_projective_finite_field(polys, domain)

Bases: sage.dynamics.arithmetic_dynamics.projective_ds.DynamicalSystem_projective_field, sage.schemes.projective.projective_morphism.SchemeMorphism_polynomial_projective_space_finite_field

automorphism_group(absolute=False, iso_type=False, return_functions=False)

Return the subgroup of \(PGL2\) that is the automorphism group of this dynamical system.

Only for dimension 1. The automorphism group is the set of \(PGL2\) elements that fixed the map under conjugation. See [FMV2014] for the algorithm.

INPUT:

  • absolute– (default: False) boolean; if True, then return the absolute automorphism group and a field of definition
  • iso_type – (default: False) boolean; if True, then return the isomorphism type of the automorphism group
  • return_functions – (default: False) boolean; True returns elements as linear fractional transformations and False returns elements as \(PGL2\) matrices

OUTPUT: a list of elements of the automorphism group

AUTHORS:

  • Original algorithm written by Xander Faber, Michelle Manes, Bianca Viray
  • Modified by Joao Alberto de Faria, Ben Hutz, Bianca Thompson

EXAMPLES:

sage: R.<x,y> = ProjectiveSpace(GF(7^3,'t'),1)
sage: f = DynamicalSystem_projective([x^2-y^2, x*y])
sage: f.automorphism_group()
[
[1 0]  [6 0]
[0 1], [0 1]
]
sage: R.<x,y> = ProjectiveSpace(GF(3^2,'t'),1)
sage: f = DynamicalSystem_projective([x^3,y^3])
sage: f.automorphism_group(return_functions=True, iso_type=True) # long time
([x,
  x/(x + 1),
  2*x/(x + 2),
  2/(x + 2),
  (x + 2)/x,
  (2*x + 2)/x,
  2/(x + 1),
  x + 1,
  x + 2,
  x/(x + 2),
  2*x/(x + 1),
  2*x,
  1/x,
  2*x + 1,
  2*x + 2,
  (x + 2)/(x + 1),
  2/x,
  (2*x + 2)/(x + 2),
  (x + 1)/(x + 2),
  (2*x + 1)/x,
  1/(x + 1),
  1/(x + 2),
  (2*x + 1)/(x + 1),
  (x + 1)/x],
 'PGL(2,3)')
sage: R.<x,y> = ProjectiveSpace(GF(2^5,'t'),1)
sage: f = DynamicalSystem_projective([x^5,y^5])
sage: f.automorphism_group(return_functions=True, iso_type=True)
([x, 1/x], 'Cyclic of order 2')
sage: R.<x,y> = ProjectiveSpace(GF(3^4,'t'),1)
sage: f = DynamicalSystem_projective([x^2+25*x*y+y^2, x*y+3*y^2])
sage: f.automorphism_group(absolute=True)
[Univariate Polynomial Ring in w over Finite Field in b of size 3^4,
 [
 [1 0]
 [0 1]
 ]]
cyclegraph()

Return the digraph of all orbits of this dynamical system.

Over a finite field this is a finite graph. For subscheme domains, only points on the subscheme whose image are also on the subscheme are in the digraph.

OUTPUT: a digraph

EXAMPLES:

sage: P.<x,y> = ProjectiveSpace(GF(13),1)
sage: f = DynamicalSystem_projective([x^2-y^2, y^2])
sage: f.cyclegraph()
Looped digraph on 14 vertices
sage: P.<x,y,z> = ProjectiveSpace(GF(3^2,'t'),2)
sage: f = DynamicalSystem_projective([x^2+y^2, y^2, z^2+y*z])
sage: f.cyclegraph()
Looped digraph on 91 vertices
sage: P.<x,y,z> = ProjectiveSpace(GF(7),2)
sage: X = P.subscheme(x^2-y^2)
sage: f = DynamicalSystem_projective([x^2, y^2, z^2], domain=X)
sage: f.cyclegraph()
Looped digraph on 15 vertices
sage: P.<x,y,z> = ProjectiveSpace(GF(3),2)
sage: f = DynamicalSystem_projective([x*z-y^2, x^2-y^2, y^2-z^2])
sage: f.cyclegraph()
Looped digraph on 13 vertices
sage: P.<x,y,z> = ProjectiveSpace(GF(3),2)
sage: X = P.subscheme([x-y])
sage: f = DynamicalSystem_projective([x^2-y^2, x^2-y^2, y^2-z^2], domain=X)
sage: f.cyclegraph()
Looped digraph on 4 vertices
orbit_structure(P)

Return the pair [m,n], where m is the preperiod and n is the period of the point P by this dynamical system.

Every point is preperiodic over a finite field so every point will be preperiodic.

INPUT:

  • P – a point in the domain of this map

OUTPUT: a list [m,n] of integers

EXAMPLES:

sage: P.<x,y,z> = ProjectiveSpace(GF(5),2)
sage: f = DynamicalSystem_projective([x^2 + y^2,y^2, z^2 + y*z], domain=P)
sage: f.orbit_structure(P(2,1,2))
[0, 6]
sage: P.<x,y,z> = ProjectiveSpace(GF(7),2)
sage: X = P.subscheme(x^2-y^2)
sage: f = DynamicalSystem_projective([x^2, y^2, z^2], domain=X)
sage: f.orbit_structure(X(1,1,2))
[0, 2]
sage: P.<x,y> = ProjectiveSpace(GF(13),1)
sage: f = DynamicalSystem_projective([x^2 - y^2, y^2], domain=P)
sage: f.orbit_structure(P(3,4))
[2, 3]
sage: R.<t> = GF(13^3)
sage: P.<x,y> = ProjectiveSpace(R,1)
sage: f = DynamicalSystem_projective([x^2 - y^2, y^2], domain=P)
sage: f.orbit_structure(P(t, 4))
[11, 6]
possible_periods(return_points=False)

Return the list of possible minimal periods of a periodic point over \(\QQ\) and (optionally) a point in each cycle.

ALGORITHM:

See [Hutz2009].

INPUT:

  • return_points – (default: False) boolean; if True, then return the points as well as the possible periods

OUTPUT:

A list of positive integers, or a list of pairs of projective points and periods if return_points is True.

EXAMPLES:

sage: P.<x,y> = ProjectiveSpace(GF(23),1)
sage: f = DynamicalSystem_projective([x^2-2*y^2, y^2])
sage: f.possible_periods()
[1, 5, 11, 22, 110]
sage: P.<x,y> = ProjectiveSpace(GF(13),1)
sage: f = DynamicalSystem_projective([x^2-y^2, y^2])
sage: sorted(f.possible_periods(True))
[[(0 : 1), 2], [(1 : 0), 1], [(3 : 1), 3], [(3 : 1), 36]]
sage: PS.<x,y,z> = ProjectiveSpace(2,GF(7))
sage: f = DynamicalSystem_projective([-360*x^3 + 760*x*z^2,
....:                                 y^3 - 604*y*z^2 + 240*z^3, 240*z^3])
sage: f.possible_periods()
[1, 2, 4, 6, 12, 14, 28, 42, 84]

Todo

  • do not return duplicate points
  • improve hash to reduce memory of point-table