Coverage for local/lib/python2.7/site-packages/sage/dynamics/arithmetic_dynamics/endPN_automorphism_group.py : 79%
Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
|
r""" Automorphism groups of dynamical systems of the projective line
AUTHORS:
- Xander Faber, Michelle Manes, Bianca Viray: algorithm and original code "Computing Conjugating Sets and Automorphism Groups of Rational Functions" by Xander Faber, Michelle Manes, and Bianca Viray [FMV]_.
- Joao de Faria, Ben Hutz, Bianca Thompson (11-2013): adaptation for inclusion in Sage """
#***************************************************************************** # Copyright (C) 2012 # # Distributed under the terms of the GNU General Public License (GPL) # as published by the Free Software Foundation; either version 2 of # the License, or (at your option) any later version. # http://www.gnu.org/licenses/ #*****************************************************************************
r"""
This function will compute the automorphism group for ``rational_function`` via the method of fixed points
ALGORITHM:
See Algorithm 3 in Faber-Manes-Viray [FMV]_.
INPUT:
- ``rational_function`` - Rational Function defined over `\mathbb{Z}` or `\mathbb{Q}`
- ``return_functions`` - Boolean Value, True will return elements in the automorphism group as linear fractional transformations. False will return elements as `PGL2` matrices
- ``iso_type`` - Boolean - True will cause the classification of the finite automorphism group to also be returned
OUTPUT: a list of automorphisms that make up the Automorphism Group of ``rational_function``
EXAMPLES::
sage: F.<z> = PolynomialRing(QQ) sage: rational_function = (z^2 - 2*z - 2)/(-2*z^2 - 2*z + 1) sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import automorphism_group_QQ_fixedpoints sage: automorphism_group_QQ_fixedpoints(rational_function, True) [z, 2/(2*z), -z - 1, -2*z/(2*z + 2), (-z - 1)/z, -1/(z + 1)]
::
sage: F.<z> = PolynomialRing(QQ) sage: rational_function = (z^2 + 2*z)/(-2*z - 1) sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import automorphism_group_QQ_fixedpoints sage: automorphism_group_QQ_fixedpoints(rational_function) [ [1 0] [-1 -1] [-2 0] [0 2] [-1 -1] [ 0 -1] [0 1], [ 0 1], [ 2 2], [2 0], [ 1 0], [ 1 1] ]
::
sage: F.<z> = PolynomialRing(QQ) sage: rational_function = (z^2 - 4*z -3)/(-3*z^2 - 2*z + 2) sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import automorphism_group_QQ_fixedpoints sage: automorphism_group_QQ_fixedpoints(rational_function, True, True) ([z, (-z - 1)/z, -1/(z + 1)], 'Cyclic of order 3') """
else: R = rational_function.parent() K = R.fraction_field()
raise TypeError("coefficient ring is not the rational numbers or the integers")
#scale f,g so both have integer coefficients
else:
#check if infinity is a fixed point #find elements in W of the form (infinity, y) #where W is the set of F-rational points (x,y) such that #x is fixed by phi and phi(y)=x else:
if return_functions: elements.append(s) else: elements.append(matrix(F, 2, [zeta, alpha*(1-zeta), 0, 1]))
#now compute points in W else: elements.append(matrix(F, 2, [zeta, alpha*(1-zeta), 0, 1])) else: [(alpha - zeta*beta), - (alpha*beta)*(1 - zeta), (1 - zeta), (alpha*zeta - beta)]))
#first look at rational fixed points #Subsets is ok since we just needed unordered pairs elements.append(s) else: [(alpha - zeta*beta), - (alpha*beta)*(1 - zeta), (1 - zeta), (alpha*zeta - beta)]))
#now consider 2-periodic points zeta = -1 alpha = S[0] beta = S[1] s = ( (alpha - zeta*beta)*z - (alpha*beta)*(1 - zeta))/((1 - zeta)*z + (alpha*zeta - beta)) if s(phi(z)) == phi(s(z)): if return_functions: elements.append(s) else: elements.append(matrix(F, 2, [(alpha - zeta*beta), - (alpha*beta)*(1 - zeta), (1 - zeta), (alpha*zeta - beta)])) elements.append(s) else: elements.append(K(s)) else: if return_functions: elements.append(K(s)) else: elements.append(matrix(F, 2, [a,b, 1, d])) else:
r""" Compute the maximum height of the coefficients of an automorphism.
This bounds sets the termination criteria for the Chinese Remainder Theorem step.
Let `f` be a square-free polynomial with coefficients in `K` Let `F` be an automorphism of `\mathbb{P}^1_{Frac(R)}` that permutes the roots of `f` This function returns a bound on the height of `F`, when viewed as an element of `\mathbb{P}^3`
In [FMV]_ it is proven that `ht(F) <= 6^{[K:Q]}*M`, where `M` is the Mahler measure of `f` M is bounded above by `H(f)`, so we return the floor of `6*H(f)` (since `ht(F)` is an integer)
INPUT:
- ``polynomial`` -- a univariate polynomial
OUTPUT: a positive integer
EXAMPLES::
sage: R.<z> = PolynomialRing(QQ) sage: f = (z^3+2*z+6) sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import height_bound sage: height_bound(f) 413526 """ # first check that polynomial is over QQ or ZZ
R = K.ring() else:
raise TypeError("coefficient ring is not the rational numbers or the integers")
# scale polynomial so that it has integer coefficients with gcd 1 # this ensures that H(f) = H_infinity(f)
# compute the infinite height
r""" Take a linear fraction transformation and represent it as a 2x2 matrix.
INPUT:
- ``rational_function`` -- a linear fraction transformation
OUTPUT: a 2x2 matrix representing ``rational_function``
EXAMPLES::
sage: R.<z> = PolynomialRing(QQ) sage: f = ((2*z-1)/(3-z)) sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import PGL_repn sage: PGL_repn(f) [ 2 -1] [-1 3] """ return matrix(F, 2, [rational_function[1], rational_function[0], 0, 1]) else:
r""" Find the multiplicative order of a linear fractional transformation that has a finite order as an element of `PGL_2(R)`.
``A`` can be represented either as a rational function or a 2x2 matrix
INPUT:
- ``A`` -- a linear fractional transformation
OUTPUT: a positive integer
EXAMPLES::
sage: M = matrix([[0,2],[2,0]]) sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import PGL_order sage: PGL_order(M) 2
::
sage: R.<x> = PolynomialRing(QQ) sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import PGL_order sage: PGL_order(-1/x) 2 """
r""" Lift the given list of automorphisms to `Zmod(M)`.
Given a list of automorphisms over various `Zmod(p^k)` find a list of automorphisms over `Zmod(M)` where `M=\prod p^k` that surjects onto every tuple of automorphisms from the various `Zmod(p^k)`.
INPUT:
- ``automorphisms`` -- a list of lists of automorphisms over various `Zmod(p^k)`
- ``moduli`` -- list of the various `p^k`
OUTPUT: a list of automorphisms over `Zmod(M)`
EXAMPLES::
sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import CRT_helper sage: CRT_helper([[matrix([[4,0],[0,1]]), matrix([[0,1],[1,0]])]],[5]) ([ [4 0] [0 1] [0 1], [1 0] ], 5) """ temp, modulus = CRT_helper( [automorphisms[i] for i in range(len(automorphisms)) if i != 0], [moduli[i] for i in range(len(moduli)) if i != 0]) temp = automorphisms[1] modulus = moduli[1] else:
autos = [] for B in temp: for C in automorphisms[0]: A = matrix(Integers(modulus*moduli[0]), 2, [CRT(B[0][0].lift(), C[0][0].lift(), modulus, moduli[0]), CRT(B[0][1].lift(), C[0][1].lift(), modulus, moduli[0]), CRT(B[1][0].lift(), C[1][0].lift(), modulus, moduli[0]), CRT(B[1][1].lift(), C[1][1].lift(), modulus, moduli[0])]) autos.append(A)
return autos, modulus*moduli[0]
r""" Compute a maximal list of automorphisms over `Zmod(M)`.
Given a list of automorphisms over various `Zmod(p^k)`, a list of the elements orders, an integer degree, and a list of the `p^k` values compute a maximal list of automorphisms over `Zmod(M)`, such that for every `j` in `len(moduli)`, each element reduces mod ``moduli[j]`` to one of the elements in ``automorphisms[j]`` that has order = ``degree``
INPUT:
- ``automorphisms`` -- a list of lists of automorphisms over various `Zmod(p^k)`
- ``order_elts`` -- a list of lists of the orders of the elements of ``automorphisms``
- ``degree`` - a positive integer
- ``moduli`` -- list of prime powers, i.e., `p^k`
OUTPUT: a list containing a list of automorphisms over `Zmod(M)` and the product of the moduli
EXAMPLES::
sage: aut = [[matrix([[1,0],[0,1]]), matrix([[0,1],[1,0]])]] sage: ords = [[1,2]] sage: degree = 2 sage: mods = [5] sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import CRT_automorphisms sage: CRT_automorphisms(aut,ords,degree,mods) ([ [0 1] [1 0] ], 5) """ # restrict to automorphisms of degree `degree` [L[i] for i in range(len(L)) if order_elts[j][i] == degree])
# get list of CRT'ed automorphisms
return_functions=False): r""" Check if automorphism mod `p^k` lifts to automorphism over `\ZZ`.
Checks whether an element that is an automorphism of ``rational_function`` modulo `p^k` for various `p` s and `k` s can be lifted to an automorphism over `\ZZ`. It uses the fact that every automorphism has height at most ``ht_bound``
INPUT:
- ``automorphisms`` -- a list of lists of automorphisms over various `Zmod(p^k)`
- ``rational_function`` -- A one variable rational function
- ``ht_bound`` - a positive integer
- ``M`` -- a positive integer, a product of prime powers
- ``return_functions`` -- (default: False) boolean
OUTPUT: a list of automorphisms over `\ZZ`
EXAMPLES::
sage: R.<z> = PolynomialRing(QQ) sage: F = z^2 sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import valid_automorphisms sage: valid_automorphisms([matrix(GF(5),[[0,1],[1,0]])], F, 48, 5, True) [1/z] """
# multiply lift by appropriate scalar matrices and adjust (mod M) # to find an element of minimal height. These will have # coefficients in [-M/2, M/2) for x in init_lift] else:
r""" If an element of `Aut_{F_p}` has been lifted to `\QQ` remove that element from `Aut_{F_p}`.
We don't want to attempt to lift that element again unnecessarily.
INPUT:
- ``automorphisms`` -- a list of lists of automorphisms
- ``order_elts`` -- a list of lists of the orders of the elements of ``automorphisms``
- ``moduli`` -- a list of prime powers
- ``integral_autos`` -- list of known automorphisms
OUTPUT: a list of automorphisms
EXAMPLES::
sage: auts = [[matrix([[1,0],[0,1]]), matrix([[6,0],[0,1]]), matrix([[0,1],[1,0]]), ....: matrix([[6,1],[1,1]]), matrix([[1,1],[1,6]]), matrix([[0,6],[1,0]]), ....: matrix([[1,6],[1,1]]), matrix([[6,6],[1,6]])]] sage: ord_elts = [[1, 2, 2, 2, 2, 2, 4, 4]] sage: mods = [7] sage: R.<x> = PolynomialRing(QQ) sage: int_auts = [-1/x] sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import remove_redundant_automorphisms sage: remove_redundant_automorphisms(auts, ord_elts, mods, int_auts) [[ [1 0] [6 0] [0 1] [6 1] [1 1] [1 6] [6 6] [0 1], [0 1], [1 0], [1 1], [1 6], [1 1], [1 6] ]] """
#The return_functions boolean determines if the automorphisms #are matrices or linear fractional transformations ppsi = psi.change_ring(GF(p)) B = [ppsi[0,0], ppsi[0,1], ppsi[1,0], psi[1,1]] else:
r""" Determines the complete group of rational automorphisms (under the conjugation action of `PGL(2,\QQ)`) for a rational function of one variable.
See [FMV]_ for details.
INPUT:
- ``rational_function`` - a rational function of a univariate polynomial ring over `\QQ`
- ``prime_lower_bound`` -- (default: 4) a positive integer - a lower bound for the primes to use for the Chinese Remainder Theorem step
- ``return_functions`` -- (default: True) boolean - True returns linear fractional transformations False returns elements of `PGL(2,\QQ)`
- ``iso_type`` -- (default: False) boolean - True returns the isomorphism type of the automorphism group
OUTPUT: a complete list of automorphisms of ``rational_function``
EXAMPLES::
sage: R.<z> = PolynomialRing(QQ) sage: f = (3*z^2 - 1)/(z^3 - 3*z) sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import automorphism_group_QQ_CRT sage: automorphism_group_QQ_CRT(f, 4, True) [z, -z, 1/z, -1/z, (-z + 1)/(z + 1), (z + 1)/(z - 1), (z - 1)/(z + 1), (-z - 1)/(z - 1)]
::
sage: R.<z> = PolynomialRing(QQ) sage: f = (3*z^2 - 1)/(z^3 - 3*z) sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import automorphism_group_QQ_CRT sage: automorphism_group_QQ_CRT(f, 4, False) [ [1 0] [-1 0] [0 1] [ 0 -1] [-1 1] [ 1 1] [ 1 -1] [-1 -1] [0 1], [ 0 1], [1 0], [ 1 0], [ 1 1], [ 1 -1], [ 1 1], [ 1 -1] ] """ else: R = rational_function.parent() K = R.fraction_field()
raise TypeError("coefficient ring is not the rational numbers or the integers")
#scale f,g so both have integer coefficients
raise ValueError("rational function has degree 1")
#badprimes is an integer divisible by every prime p such that either # 1) phi has bad reduction at p or # 2) the reduction map fails to be injective #6 is because over Q, Aut(phi) has order dividing 12 #when generalizing to a number field K, 6 should be replaced with # 2*gcd(2*[K:Q] + 1, d^3 - d)
#Determining the set that is used to obtain the height bound h = h[2]*f**2 + h[1]*f*g + h[0]*g**2 psi = phi(phi(z)) f2 = psi.numerator() g2 = psi.denominator() N = lcm(f2.denominator(),g2.denominator()) f2 = f2*N g2 = g2*N N = gcd(gcd(f2.coefficients()), gcd(g2.coefficients())) f2 = f2/N g2 = g2/N h = h[1]*f2 + h[0]*g2
else:
#over QQ, elts of PGL_2 of finite order can only have order dividing 6 or 4, # and the finite subgroups can only be cyclic or dihedral (Beauville) so # the only possible groups are C_n, D_2n for n|6 or n|4 # all of these groups have order dividing 24 # compute automorphisms mod p
# check if we already found 8 or 12 automorphisms # and the gcd of orders over Fp and 24 is 24 # or if the gcd is equal to the number of automorphisms we have (gcd(orderaut + [24]) == 24 and \ (len(elements) == 12 or len(elements) == 8)): if iso_type: return(elements, which_group(elements)) return elements else: if not O in badorders]: #range over all orders # that are possible over QQ such that we haven't already # found all elements of that order
# First count number of elements of particular order # Have some elts of fixed order mod p for each p #CRT order d elements together and check if # they are an automorphism orderelts, order, primepowers) return_functions)
#found enough automorphisms # found all elements of order 'order; elif len(temp) != 0: # found some elements of order 'order' # if an element of Aut_{F_p} has been lifted to QQ # remove that element from Aut_{F_p} so we don't # attempt to lift that element again unnecessarily automorphisms=remove_redundant_automorphisms(automorphisms, orderelts, primepowers, temp) if order == 4: #have some elements of order 4 # so possible aut group is Z/4 or D_4 badorders.extend([3, 6]) elif order == 3 or order == 6:#have some elements of # order 3 or 6 so possible aut groups are Z/3, # D_3, Z/6, or D_6 badorders.append(4) else: #no elements of order d in some F_v for m in divisors(N): if m%order == 0: badorders.append(m) #no elements of that order or any order that # is a multiple of it if len([order for order in divisors(N) \ if not order in badorders]) == 0: #found all elements of every possible order if iso_type: return(elements, which_group(elements)) return elements congruence = congruence*p
p = primes.next(p)
if iso_type: return(elements, which_group(elements)) return(elements)
r""" This function computes automorphism groups over finite fields.
ALGORITHM:
See Algorithm 4 in Faber-Manes-Viray [FMV]_.
INPUT:
- ``rational_function`` -- a rational function defined over the fraction field of a polynomial ring in one variable with finite field coefficients
- ``absolute``-- (default: False) boolean - True returns the absolute automorphism group and a field of definition
- ``iso_type`` -- (default: False) boolean - True returns the isomorphism type of the automorphism group
- ``return_functions`` -- (default: False) boolean, True returns linear fractional transformations False returns elements of `PGL(2)`
OUTPUT: a list of automorphisms of ``rational_function``
EXAMPLES::
sage: R.<x> = PolynomialRing(GF(5^2, 't')) sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import automorphism_group_FF sage: automorphism_group_FF((x^2+x+1)/(x+1)) [ [1 0] [4 3] [0 1], [0 1] ]
::
sage: R.<x> = PolynomialRing(GF(2^5, 't')) sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import automorphism_group_FF sage: automorphism_group_FF(x^(5), True, False, True) [Univariate Polynomial Ring in w over Finite Field in b of size 2^5, [w, 1/w]]
::
sage: R.<x> = PolynomialRing(GF(2^5, 't')) sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import automorphism_group_FF sage: automorphism_group_FF(x^(5), False, False, True) [x, 1/x] """
else:
else: R = R.ring()
else: return G, which_group(G[1])
r""" Function for descending an element in a field E to a subfield F.
Here F, E must be finite fields or number fields. This function determines the unique image of subfield which is ``y`` by the embedding ``sigma`` if it exists. Otherwise returns ``None``. This functionality is necessary because Sage does not keep track of subfields.
INPUT:
- ``sigma``-- an embedding sigma: `F` -> `E` of fields
- ``y`` --an element of the field `E`
OUTPUT: the unique element of the subfield if it exists, otherwise ``None``
EXAMPLES::
sage: R = GF(11^2,'b') sage: RR = GF(11) sage: s = RR.Hom(R)[0] sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import field_descent sage: field_descent(s, R(1)) 1 """
return
return else:
quotient, remainder = quotient.quo_rem(f) if not remainder.is_constant(): return else: x = x+ F(remainder)*a**(steps) steps += 1
r""" Function for descending the coefficients of a rational function from field `E` to a subfield `F`.
Here `F`, `E` must be finite fields or number fields. It determines the unique rational function in fraction field of ``poly_ring`` which is the image of ``rational_function`` by ``ssigma``, if it exists, and otherwise returns ``None``.
INPUT:
- ``rational_function``--a rational function with coefficients in a field `E`
- ``sigma``-- a field embedding sigma: `F` -> `E`
- ``poly_ring``-- a polynomial ring `R` with coefficients in `F`
OUTPUT: a rational function with coefficients in the fraction field of ``poly_ring`` if it exists, and otherwise ``None``
EXAMPLES::
sage: T.<z> = PolynomialRing(GF(11^2,'b')) sage: S.<y> = PolynomialRing(GF(11)) sage: s = S.base_ring().hom(T.base_ring()) sage: f = (3*z^3 - z^2)/(z-1) sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import rational_function_coefficient_descent sage: rational_function_coefficient_descent(f,s,S) (3*y^3 + 10*y^2)/(y + 10) """
else: S = rational_function.parent()
return poly_ring(0)
#force the cancellation of common coefficient factors by scaling by f[-1] return
r""" Function for coercing a rational function defined over a ring `R` to have coefficients in a second ring ``S_polys``.
The fraction field of polynomial ring ``S_polys`` will contain the new rational function.
INPUT:
- ``rational_function``-- rational function with coefficients in `R`
- ``sigma`` -- a ring homomorphism sigma: `R` -> ``S_polys``
- ``S_polys`` -- a polynomial ring
OUTPUT: a rational function with coefficients in ``S_polys``
EXAMPLES::
sage: R.<y> = PolynomialRing(QQ) sage: S.<z> = PolynomialRing(ZZ) sage: s = S.hom([z],R) sage: f = (3*z^2 + 1)/(z^3-1) sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import rational_function_coerce sage: rational_function_coerce(f,s,R) (3*y^2 + 1)/(y^3 - 1) """ else:
else:
r""" Force Sage to divide out common factors in numerator and denominator of rational function.
INPUT:
- ``rational_function`` -- rational function `= F/G` in univariate polynomial ring
OUTPUT: rational function -- `(F/gcd(F,G) ) / (G/gcd(F,G))`
EXAMPLES::
sage: R.<z> = PolynomialRing(GF(7)) sage: f = ((z-1)*(z^2+z+1))/((z-1)*(z^3+1)) sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import rational_function_reduce sage: rational_function_reduce(f) (z^2 + z + 1)/(z^3 + 1) """
r""" Implementation of Algorithm 1 for automorphism groups from Faber-Manes-Viray [FMV]_.
INPUT:
- ``rational_function``--rational function `phi` defined over finite field `E`
- ``invariant_list``-- a list of at least `3` points of `\mathbb{P}^1(E)` that is stable under `Aut_{phi}(E)`
OUTPUT: list of automorphisms
EXAMPLES::
sage: R.<z> = PolynomialRing(GF(5^2,'t')) sage: f = z^3 sage: L = [[0,1],[4,1],[1,1],[1,0]] sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import three_stable_points sage: three_stable_points(f,L) [z, 4*z, 2/(2*z), 3/(2*z)] """ # define ground field and ambient function field else:
T[0][0]*T[1][1]*T[2][1]*T[t[0]][0]*T[t[1]][1]*T[t[2]][0] - T[0][1]*T[1][0]*T[2][1]*T[t[0]][0]*T[t[1]][0]*T[t[2]][1] + T[0][1]*T[1][0]*T[2][1]*T[t[0]][1]*T[t[1]][0]*T[t[2]][0] + T[0][1]*T[1][1]*T[2][0]*T[t[0]][0]*T[t[1]][1]*T[t[2]][0] - T[0][1]*T[1][1]*T[2][0]*T[t[0]][1]*T[t[1]][0]*T[t[2]][0])
T[0][0]*T[1][0]*T[2][1]*T[t[0]][1]*T[t[1]][0]*T[t[2]][0] - T[0][0]*T[1][1]*T[2][0]*T[t[0]][0]*T[t[1]][0] *T[t[2]][1] + T[0][0]*T[1][1]*T[2][0]*T[t[0]][1]*T[t[1]][0]*T[t[2]][0] + T[0][1]*T[1][0]*T[2][0]*T[t[0]][0]*T[t[1]][0]*T[t[2]][1] - T[0][1]*T[1][0]*T[2][0]*T[t[0]][0]*T[t[1]][1]*T[t[2]][0])
T[0][0]*T[1][1]*T[2][1]*T[t[0]][1]*T[t[1]][1]*T[t[2]][0] - T[0][1]*T[1][0]*T[2][1]*T[t[0]][0]*T[t[1]][1]*T[t[2]][1] + T[0][1]*T[1][0]*T[2][1]*T[t[0]][1]*T[t[1]][1]*T[t[2]][0] + T[0][1]*T[1][1]*T[2][0]*T[t[0]][0]*T[t[1]][1]*T[t[2]][1] - T[0][1]*T[1][1]*T[2][0]*T[t[0]][1]*T[t[1]][0]*T[t[2]][1])
T[0][0]*T[1][0]*T[2][1]*T[t[0]][1]*T[t[1]][0] *T[t[2]][1]- T[0][0]*T[1][1]*T[2][0]*T[t[0]][0]*T[t[1]][1]*T[t[2]][1] + T[0][0]*T[1][1]*T[2][0]*T[t[0]][1]*T[t[1]][1]*T[t[2]][0] + T[0][1]*T[1][0]*T[2][0]*T[t[0]][1]*T[t[1]][0] *T[t[2]][1]- T[0][1]*T[1][0]*T[2][0]*T[t[0]][1]*T[t[1]][1]*T[t[2]][0])
r""" Implementation of algorithm for determining the absolute automorphism group over a finite field, given an invariant set, see [FMV]_.
INPUT:
- ``rational_function``--a rational function defined over a finite field
OUTPUT: absolute automorphism group of ``rational_function`` and a ring of definition
EXAMPLES::
sage: R.<z> = PolynomialRing(GF(7^2,'t')) sage: f = (3*z^3 - z^2)/(z-1) sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import automorphism_group_FF_alg2 sage: automorphism_group_FF_alg2(f) [Univariate Polynomial Ring in w over Finite Field in b of size 7^2, [w, (3*b + 2)/((2*b + 6)*w)]]
::
sage: R.<z> = PolynomialRing(GF(5^3,'t')) sage: f = (3456*z^(4)) sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import automorphism_group_FF_alg2 sage: automorphism_group_FF_alg2(f) [Univariate Polynomial Ring in w over Finite Field in b of size 5^6, [w, (3*b^5 + 4*b^4 + 3*b^2 + 2*b + 1)*w, (2*b^5 + b^4 + 2*b^2 + 3*b + 3)*w, (3*b^5 + 4*b^4 + 3*b^2 + 2*b)/((3*b^5 + 4*b^4 + 3*b^2 + 2*b)*w), (4*b^5 + 2*b^4 + 4*b^2 + b + 2)/((3*b^5 + 4*b^4 + 3*b^2 + 2*b)*w), (3*b^5 + 4*b^4 + 3*b^2 + 2*b + 3)/((3*b^5 + 4*b^4 + 3*b^2 + 2*b)*w)]] """ # define ground field and ambient function field else:
raise TypeError("coefficient ring is not a finite field")
# Build an invariant set for phi
# Infinity is a fixed point # Infinity is not a fixed point else: C = minimal_fix_poly.coefficients(sparse=False) preimage = C[2]*f(z)**2 + C[1]*f(z)*g(z) + C[0]*g(z)**2 infinity_check = bool(preimage.degree() < 2*D)
else: #case n=1 # Infinity is the fixed point if bool(fix.degree() < D+1): minimal_preimage = R(prod(x[0] for x in g.factor())) if minimal_preimage.degree() + 1 >= 3: T_poly = minimal_preimage infinity_check = 1 else: T_poly = R(prod(x[0] for x in phi(phi(z)).denominator().factor() ) ) infinity_check = 1
# Infinity is not a fixed point else: y = fix.roots(multiplicities=False)[0] preimage = R(f(z) - y*g(z)) minimal_preimage = R(prod(x[0] for x in preimage.factor())) if minimal_preimage.degree() + bool(preimage.degree()<D) >= 3: T_poly = minimal_preimage infinity_check = bool(preimage.degree()<D) else: preimage2 = R(phi(phi(z)).numerator() - y*phi(phi(z)).denominator()) T_poly = R(prod(x[0] for x in preimage2.factor() ) ) infinity_check = infinity_check = bool(preimage2.degree() < D**2)
# Define a field of definition for the absolute automorphism group
# Coerce phi into the larger ring and call Algorithm 1
r""" Determine the order-p automorphisms given the input data.
This is algorithm 4 in Faber-Manes-Viray [FMV]_.
INPUT:
- ``rational_function``--rational function defined over finite field `F`
- ``pre_image``--set of triples `[x, L, f]`, where `x` is an `F`-rational fixed point of ``rational_function``, `L` is the list of `F`-rational pre-images of `x` (excluding `x`), and `f` is the polynomial defining the full set of pre-images of `x` (again excluding `x` itself)
OUTPUT: set of automorphisms of order `p` defined over `F`
EXAMPLES::
sage: R.<x> = PolynomialRing(GF(11)) sage: f = x^11 sage: L = [[[0, 1], [], 1], [[10, 1], [], 1], [[9, 1], [], 1], ....: [[8, 1], [],1], [[7, 1], [], 1], [[6, 1], [], 1], [[5, 1], [], 1], ....: [[4, 1], [], 1],[[3, 1], [], 1], [[2, 1], [], 1], [[1, 1], [], 1], ....: [[1, 0], [], 1]] sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import order_p_automorphisms sage: order_p_automorphisms(f,L) [x/(x + 1), 6*x/(x + 6), 3*x/(x + 3), 7*x/(x + 7), 9*x/(x + 9), 10*x/(x + 10), 5*x/(x + 5), 8*x/(x + 8), 4*x/(x + 4), 2*x/(x + 2), 10/(x + 2), (5*x + 10)/(x + 7), (2*x + 10)/(x + 4), (6*x + 10)/(x + 8), (8*x + 10)/(x + 10), (9*x + 10)/x, (4*x + 10)/(x + 6), (7*x + 10)/(x + 9), (3*x + 10)/(x + 5), (x + 10)/(x + 3), (10*x + 7)/(x + 3), (4*x + 7)/(x + 8), (x + 7)/(x + 5), (5*x + 7)/(x + 9), (7*x + 7)/x, (8*x + 7)/(x + 1), (3*x + 7)/(x + 7), (6*x + 7)/(x + 10), (2*x + 7)/(x + 6), 7/(x + 4), (9*x + 2)/(x + 4), (3*x + 2)/(x + 9), 2/(x + 6), (4*x + 2)/(x + 10), (6*x + 2)/(x + 1), (7*x + 2)/(x + 2), (2*x + 2)/(x + 8), (5*x + 2)/x, (x + 2)/(x + 7), (10*x + 2)/(x + 5), (8*x + 6)/(x + 5), (2*x + 6)/(x + 10), (10*x + 6)/(x + 7), (3*x + 6)/x, (5*x + 6)/(x + 2), (6*x + 6)/(x + 3), (x + 6)/(x + 9), (4*x + 6)/(x + 1), 6/(x + 8), (9*x + 6)/(x + 6), (7*x + 8)/(x + 6), (x + 8)/x, (9*x + 8)/(x + 8), (2*x + 8)/(x + 1), (4*x + 8)/(x + 3), (5*x + 8)/(x + 4), 8/(x + 10), (3*x + 8)/(x + 2), (10*x + 8)/(x + 9), (8*x + 8)/(x + 7), (6*x + 8)/(x + 7), 8/(x + 1), (8*x + 8)/(x + 9), (x + 8)/(x + 2), (3*x + 8)/(x + 4), (4*x + 8)/(x + 5), (10*x + 8)/x, (2*x + 8)/(x + 3), (9*x + 8)/(x + 10), (7*x + 8)/(x + 8), (5*x + 6)/(x + 8), (10*x + 6)/(x + 2), (7*x + 6)/(x + 10), 6/(x + 3), (2*x + 6)/(x + 5), (3*x + 6)/(x + 6), (9*x + 6)/(x + 1), (x + 6)/(x + 4), (8*x + 6)/x, (6*x + 6)/(x + 9), (4*x + 2)/(x + 9), (9*x + 2)/(x + 3), (6*x + 2)/x, (10*x + 2)/(x + 4), (x + 2)/(x + 6), (2*x + 2)/(x + 7), (8*x + 2)/(x + 2), 2/(x + 5), (7*x + 2)/(x + 1), (5*x + 2)/(x + 10), (3*x + 7)/(x + 10), (8*x + 7)/(x + 4), (5*x + 7)/(x + 1), (9*x + 7)/(x + 5), 7/(x + 7), (x + 7)/(x + 8), (7*x + 7)/(x + 3), (10*x + 7)/(x + 6), (6*x + 7)/(x + 2), (4*x + 7)/x, (2*x + 10)/x, (7*x + 10)/(x + 5), (4*x + 10)/(x + 2), (8*x + 10)/(x + 6), (10*x + 10)/(x + 8), 10/(x + 9), (6*x + 10)/(x + 4), (9*x + 10)/(x + 7), (5*x + 10)/(x + 3), (3*x + 10)/(x + 1), x + 1, x + 2, x + 4, x + 8, x + 5, x + 10, x + 9, x + 7, x + 3, x + 6] """ # define ground field and ambient function field else:
# Compute the threshold r2 for determining which algorithm to use elif len(pre_image[0][1]) > 0: r2 = len(pre_image[0][1]) case = 'F-pre_images' else: factor_list = pre_image[0][2].factor() minimal_fix_poly = R(prod(x[0] for x in factor_list)) r2 = sum(x[0].degree() for x in factor_list) # Note that infinity is F-rational, so covered by preceding case case = 'all pre_images'
# Note that r2 == 0 corresponds to having a unique F-rational fixed point # that is totally ramified
else:
elif case == 'F-pre_images': T = [x for x in pre_image[0][1]] else: T = []
# loop over all F-rational pre-images # treat case of multiple F-rational fixed points or # 1 F-rational fixed point with F-rational pre-images automorphisms_p.append(s) else: else: uy2 = u(M[i][0]) elif T==[]: # create the extension field generated by pre-images of the unique fixed point T_poly = pre_image[0][2] e = lcm([x[0].degree() for x in T_poly.factor()])*F.degree() E = GF(p**e, 'b') b = E.gen(0) sigma = F.Hom(E)[0] S = PolynomialRing(E,'w') w = S.gen(0) E_poly = rational_function_coerce(T_poly, sigma, S) # List of roots permuted by elements of order p # Since infinity is F-rational, it won't appear in this list T = [ [alpha, E(1)] for alpha in E_poly.roots(ring=E, multiplicities=False)]
# coerce the rational function and fixed point into E Phi = rational_function_coerce(phi, sigma, S) Pt = [sigma(pt[0]), sigma(pt[1])]
m = len(T) if Pt == [E(1),E(0)]: for i in range(1, m): s = w + T[i][0] - T[0][0] if s(Phi(w)) == Phi(s(w)): automorphisms_p.append(rational_function_coefficient_descent(s, sigma, R)) else: u = E(1) / (w - Pt[0]) u_inv = Pt[0] + E(1)/w for i in range(1,m): uy1 = u(T[0][0]) uy2 = u(T[i][0]) s = u_inv( u(w) + uy2 - uy1 ) if s(Phi(w)) == Phi(s(w)): s = rational_function_reduce(s) automorphisms_p.append(rational_function_coefficient_descent(s,sigma,R))
r""" Compute the set of automorphisms with order prime to the characteristic that fix the pair, excluding the identity.
INPUT:
- ``rational_function``-- rational function defined over finite field `E`
- ``pair``-- a pair of points of `\mathbb{P}^1(E)`
- ``quad``-- Boolean: an indicator if this is a quadratic pair of points
OUTPUT: set of automorphisms with order prime to characteristic defined over `E` that fix the pair, excluding the identity
EXAMPLES::
sage: R.<z> = PolynomialRing(GF(7^2, 't')) sage: f = (z^2 + 5*z + 5)/(5*z^2 + 5*z + 1) sage: L = [[4, 1], [2, 1]] sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import automorphisms_fixing_pair sage: automorphisms_fixing_pair(f, L, False) [(6*z + 6)/z, 4/(3*z + 3)] """ # define ground field and ambient function field else:
#assumes the second coordinate of the point is 1 else:
# Quadratic automorphisms have order dividing q+1 and D, D-1, or D+1 #need sqrt to get the cardinality of the base field and not the #degree 2 extension
# rational automorphisms have order dividing q-1 and D, D-1, or D+1 else:
r""" Implementation of Algorithm 3 in the paper by Faber/Manes/Viray [FMV]_ for computing the automorphism group over a finite field.
INPUT:
- ``rational_function``--a rational function defined over a finite field `F`
OUTPUT: list of `F`-rational automorphisms of ``rational_function``
EXAMPLES::
sage: R.<z> = PolynomialRing(GF(5^3,'t')) sage: f = (3456*z^4) sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import automorphism_group_FF_alg3 sage: automorphism_group_FF_alg3(f) [z, 3/(3*z)] """ # define ground field and ambient function field else:
raise TypeError("coefficient ring is not a finite field")
# For use in the quadratic extension parts of the algorithm
# Compute the set of distinct F-rational and F-quadratic # factors of the fixed point polynomial
# Compute the set of distinct F-rational fixed points
# Coerce quadratic factors into a quadratic extension
# Collect pre-image data as a list L with entries in the form # [fixed point y, F-rational pre-images z != y, polynomial defining the pre-images] # Note that we remove the fixed point from its pre-image set and its polynomial else: Fpre.append([F(1), F(0)]) # infinity is a pre-image of 0 Fpre.append([F(1), F(0)]) # infinity is a pre-image of y[0] # remove y[0] as a root of pre-image polynomial
# Initialize the set of automorphisms to contain the identity
# order p elements # An F-rational fixed point has orbit length 1 or p under the action of an element of # order p. An F-quadratic fixed point has orbit length p. The set of F-rational # pre-images of fixed points decomposes as a union of orbits of length p. # Compute total number of distinct fixed points as a final check for order p auts
## nontrivial elements with order prime to p ## # case of 2 F-rational fixed points
# case of 1 F-rational fixed point and an F-rational pre-image
# case of a pair of quadratic fixed points
# n2 = n1 + 2*len(quad_fix_factors)
# case of a pair of F-rational period 2 points y = [F(1), F(0)] y = [f.leading_coefficient() / g.leading_coefficient(), F(1)] else:
# case of a pair of quadratic period 2 points
# Descend coefficients of the quadratic guys back to the base field
r""" Given a finite subgroup of `PGL2` determine its isomorphism class.
This function makes heavy use of the classification of finite subgroups of `PGL(2,K)`.
INPUT:
- ``list_of_elements``-- a finite list of elements of `PGL(2,K)` that we know a priori form a group
OUTPUT: a string -- the isomorphism type of the group
EXAMPLES::
sage: R.<x> = PolynomialRing(GF(7,'t')) sage: G = [x, 6*x/(x + 1), 6*x + 6, 1/x, (6*x + 6)/x, 6/(x + 1)] sage: from sage.dynamics.arithmetic_dynamics.endPN_automorphism_group import which_group sage: which_group(G) 'Dihedral of order 6' """ R = PolynomialRing(list_of_elements[-1].base_ring(),'z') z = R.gen(0) G=[(t[0,0]*z+t[0,1])/(t[1,0]*z+t[1,1]) for t in list_of_elements] else:
# invalid input raise ValueError("group must have at least one element")
# define ground field and ambient function field
else: R = rational_function.parent() K = R.fraction_field()
# factor n = mp^e; set e = 0 and m = n if p = 0 (Sage sets 0^0 = 1) else:
# Determine if G is cyclic or dihedral. # This determines the maximal cyclic subgroup and the maximal cyclic # p-regular subgroup. Algorithm terminates if the order of this subgroup agrees with # the order of the group.
# Test for dihedral subgroup. A subgroup of index 2 is always normal, so the # presence of a cyclic subgroup H of index 2 indicates the group is either # H x Z/2Z or dihedral. The former occurs only if H has order 1 or 2, both of # which are dihedral. # Check the p-irregular cases. There is overlap in these cases when p^e = 2, # which is dihedral and so already dealt with above. By the classification theorem, # these are either p-semi-elementary, PGL(2,q), PSL(2,q), or A_5 when p=3. The latter # case is already covered by the remaining sporadic cases below. if e > 0: if n_reg == m: # p-semi-elementary return '{0}-semi-elementary of order {1}'.format(p, n) if n_reg == m / (p**e - 1) and m == p**(2*e) - 1: # PGL(2) return 'PGL(2,{0})'.format(p**e) if n_reg == m / (p**e - 1) and m == (1/2)*(p**(2*e) - 1): # PSL(2) return 'PSL(2,{0})'.format(p**e)
# Treat sporadic cases if n == 12: return ['A_4'] elif n == 24: return ['S_4'] else: return ['A_5'] |