def __init__(self, coxeter_matrix, base_ring, index_set):
"""
Initialize ``self``.
EXAMPLES::
sage: W = CoxeterGroup([[1,3,2],[3,1,3],[2,3,1]])
sage: TestSuite(W).run() # long time
sage: W = CoxeterGroup([[1,3,2],[3,1,4],[2,4,1]], base_ring=QQbar)
sage: TestSuite(W).run() # long time
sage: W = CoxeterGroup([[1,3,2],[3,1,6],[2,6,1]])
sage: TestSuite(W).run(max_runs=30) # long time
sage: W = CoxeterGroup([[1,3,2],[3,1,-1],[2,-1,1]])
sage: TestSuite(W).run(max_runs=30) # long time
"""
self._matrix = coxeter_matrix
self._index_set = index_set
n = ZZ(coxeter_matrix.nrows())
MS = MatrixSpace(base_ring, n, sparse=True)
# FIXME: Hack because there is no ZZ \cup \{ \infty \}: -1 represents \infty
if base_ring is UniversalCyclotomicField():
val = lambda x: base_ring.gen(2*x) + ~base_ring.gen(2*x) if x != -1 else base_ring(2)
else:
from sage.functions.trig import cos
from sage.symbolic.constants import pi
val = lambda x: base_ring(2*cos(pi / x)) if x != -1 else base_ring(2)
gens = [MS.one() + MS({(i, j): val(coxeter_matrix[i, j])
for j in range(n)})
for i in range(n)]
FinitelyGeneratedMatrixGroup_generic.__init__(self, n, base_ring,
gens,
category=CoxeterGroups())
def matA(n):
A = []
n2 = n.quo_rem(2)[0]
for j in range(n2+2):
MS0 = MatrixSpace(F, j, j)
I = MS0.identity_matrix()
O = MS0(j*j*[1])
A.append(I+O)
return A
def __init__(self, modulus, dimension):
self.modulus = int(modulus) #The modulus p
self.dimension = int(dimension) #The dimension d
self.field = FiniteField(modulus) #The underlying field
self.space = MatrixSpace(self.field, 1, dimension) #The space of vectors in Z_p^d viewed as matrices
self.elements = list(self.space) #An actual list of those vectors
self.basis = self.space.basis() #The standard basis for the vector space
def to_matrix(self):
r"""
Return ``self`` as a matrix.
We define a matrix `M_{xy} = \alpha(x, y)` for some element
`\alpha \in I_P` in the incidence algebra `I_P` and we order
the elements `x,y \in P` by some linear extension of `P`. This
defines an algebra (iso)morphism; in particular, multiplication
in the incidence algebra goes to matrix multiplication.
EXAMPLES::
sage: P = posets.BooleanLattice(2)
sage: I = P.incidence_algebra(QQ)
sage: I.moebius().to_matrix()
[ 1 -1 -1 1]
[ 0 1 0 -1]
[ 0 0 1 -1]
[ 0 0 0 1]
sage: I.zeta().to_matrix()
[1 1 1 1]
[0 1 0 1]
[0 0 1 1]
[0 0 0 1]
TESTS:
We check that this is an algebra (iso)morphism::
sage: P = posets.BooleanLattice(4)
sage: I = P.incidence_algebra(QQ)
sage: mu = I.moebius()
sage: (mu*mu).to_matrix() == mu.to_matrix() * mu.to_matrix()
True
"""
P = self.parent()
MS = MatrixSpace(P.base_ring(), P._poset.cardinality(), sparse=True)
L = P._linear_extension
M = copy(MS.zero())
for i, c in self:
M[L.index(i[0]), L.index(i[1])] = c
M.set_immutable()
return M
def RandomLinearCode(n,k,F):
r"""
The method used is to first construct a `k \times n`
matrix using Sage's random_element method for the MatrixSpace
class. The construction is probabilistic but should only fail
extremely rarely.
INPUT: Integers n,k, with `n>k`, and a finite field F
OUTPUT: Returns a "random" linear code with length n, dimension k
over field F.
EXAMPLES::
sage: C = codes.RandomLinearCode(30,15,GF(2))
sage: C
Linear code of length 30, dimension 15 over Finite Field of size 2
sage: C = codes.RandomLinearCode(10,5,GF(4,'a'))
sage: C
Linear code of length 10, dimension 5 over Finite Field in a of size 2^2
AUTHORS:
- David Joyner (2007-05)
"""
MS = MatrixSpace(F,k,n)
for i in range(50):
G = MS.random_element()
if G.rank() == k:
V = span(G.rows(), F)
return LinearCodeFromVectorSpace(V) # may not be in standard form
MS1 = MatrixSpace(F,k,k)
MS2 = MatrixSpace(F,k,n-k)
Ik = MS1.identity_matrix()
A = MS2.random_element()
G = Ik.augment(A)
return LinearCode(G) # in standard form
def HS_all_minimal_p(p, f, m=None, return_transformation=False):
r"""
Find a representative in each distinct `SL(2,\ZZ)` orbit with
minimal `p`-resultant.
This function implements the algorithm in Hutz-Stoll [HS2018]_.
A representatives in each distinct `SL(2,\ZZ)` orbit with minimal
valuation with respect to the prime ``p`` is returned. The input
``f`` must have minimal resultant in its conguacy class.
INPUT:
- ``p`` -- a prime
- ``f`` -- dynamical system on the projective line with minimal resultant
- ``m`` -- (optional) `2 \times 2` matrix associated with ``f``
- ``return_transformation`` -- (default: ``False``) boolean; this
signals a return of the ``PGL_2`` transformation to conjugate ``vp``
to the calculated minimal model
OUTPUT:
List of pairs ``[f, m]`` where ``f`` is a dynamical system and ``m`` is a
`2 \times 2` matrix.
EXAMPLES::
sage: P.<x,y> = ProjectiveSpace(QQ,1)
sage: f = DynamicalSystem([x^5 - 6^4*y^5, x^2*y^3])
sage: from sage.dynamics.arithmetic_dynamics.endPN_minimal_model import HS_all_minimal_p
sage: HS_all_minimal_p(2, f)
[Dynamical System of Projective Space of dimension 1 over Rational Field
Defn: Defined on coordinates by sending (x : y) to
(x^5 - 1296*y^5 : x^2*y^3),
Dynamical System of Projective Space of dimension 1 over Rational Field
Defn: Defined on coordinates by sending (x : y) to
(4*x^5 - 162*y^5 : x^2*y^3)]
sage: cl = HS_all_minimal_p(2, f, return_transformation=True)
sage: all([f.conjugate(m) == g for g,m in cl])
True
"""
count = 0
prev = 0 # no exclusions
F = copy(f)
res = ZZ(F.resultant())
vp = res.valuation(p)
MS = MatrixSpace(ZZ, 2)
if m is None:
m = MS.one()
if f.degree() % 2 == 0 or vp == 0:
# there is only one orbit for even degree
# nothing to do if the prime doesn't divide the resultant
if return_transformation:
return [[f, m]]
else:
return [f]
to_do = [[F, m, prev]] # repns left to check
reps = [[F, m]] # orbit representatives for f
while to_do:
F, m, prev = to_do.pop()
# there are at most two directions preserving the resultant
if prev == 0:
count = 0
else:
count = 1
if prev != 2: # [p,a,0,1]
t = MS([1, 0, 0, p])
F1 = F.conjugate(t)
F1.normalize_coordinates()
res1 = ZZ(F1.resultant())
vp1 = res1.valuation(p)
if vp1 == vp:
count += 1
# we have a new representative
reps.append([F1, m*t])
# need to check if it has any neighbors
to_do.append([F1, m*t, 1])
for b in range(p):
if not (b == 0 and prev == 1):
t = MS([p, b, 0, 1])
F1 = F.conjugate(t)
F1.normalize_coordinates()
res1 = ZZ(F1.resultant())
vp1 = res1.valuation(p)
if vp1 == vp:
count += 1
# we have a new representative
reps.append([F1, m*t])
# need to check if it has any neighbors
to_do.append([F1, m*t, 2])
if count >= 2: # at most two neighbors
break
if return_transformation:
return reps
else:
return [funct for funct, matr in reps]
def HS_minimal(f, return_transformation=False, D=None):
r"""
Compute a minimal model for the given projective dynamical system.
This function implements the algorithm in Hutz-Stoll [HS2018]_.
A representative with minimal resultant in the conjugacy class
of ``f`` returned.
INPUT:
- ``f`` -- dynamical system on the projective line with minimal resultant
- ``return_transformation`` -- (default: ``False``) boolean; this
signals a return of the `PGL_2` transformation to conjugate
this map to the calculated models
- ``D`` -- a list of primes, in case one only wants to check minimality
at those specific primes
OUTPUT:
- a dynamical system
- (optional) a `2 \times 2` matrix
EXAMPLES::
sage: P.<x,y> = ProjectiveSpace(QQ,1)
sage: f = DynamicalSystem([x^3 - 6^2*y^3, x^2*y])
sage: m = matrix(QQ,2,2,[5,1,0,1])
sage: g = f.conjugate(m)
sage: g.normalize_coordinates()
sage: g.resultant().factor()
2^4 * 3^4 * 5^12
sage: from sage.dynamics.arithmetic_dynamics.endPN_minimal_model import HS_minimal
sage: HS_minimal(g).resultant().factor()
2^4 * 3^4
sage: HS_minimal(g, D=[2]).resultant().factor()
2^4 * 3^4 * 5^12
sage: F,m = HS_minimal(g, return_transformation=True)
sage: g.conjugate(m) == F
True
"""
F = copy(f)
d = F.degree()
F.normalize_coordinates()
MS = MatrixSpace(ZZ, 2, 2)
m = MS.one()
prev = copy(m)
res = ZZ(F.resultant())
if D is None:
D = res.prime_divisors()
# minimize for each prime
for p in D:
vp = res.valuation(p)
minimal = False
while not minimal:
if (d % 2 == 0 and vp < d) or (d % 2 == 1 and vp < 2 * d):
# must be minimal
minimal = True
break
minimal = True
t = MS([1, 0, 0, p])
F1 = F.conjugate(t)
F1.normalize_coordinates()
res1 = F1.resultant()
vp1 = res1.valuation(p)
if vp1 < vp: # check if smaller
F = F1
vp = vp1
m = m * t # keep track of conjugation
minimal = False
else:
# still search for smaller
for b in range(p):
t = matrix(ZZ,2,2,[p, b, 0, 1])
F1 = F.conjugate(t)
F1.normalize_coordinates()
res1 = ZZ(F1.resultant())
vp1 = res1.valuation(p)
if vp1 < vp: # check if smaller
F = F1
m = m * t # keep track of transformation
minimal = False
vp = vp1
break # exit for loop
if return_transformation:
return F, m
return F
def BM_all_minimal(vp, return_transformation=False, D=None):
r"""
Determine a representative in each `SL(2,\ZZ)` orbit with minimal
resultant.
This function modifies the Bruin-Molnar algorithm ([BM2012]_) to solve
in the inequalities as ``<=`` instead of ``<``. Among the list of
solutions is all conjugations that preserve the resultant. From that
list the `SL(2,\ZZ)` orbits are identified and one representative from
each orbit is returned. This function assumes that the given model is
a minimal model.
INPUT:
- ``vp`` -- a minimal model of a dynamical system on the projective line
- ``return_transformation`` -- (default: ``False``) boolean; this
signals a return of the ``PGL_2`` transformation to conjugate ``vp``
to the calculated minimal model
- ``D`` -- a list of primes, in case one only wants to check minimality
at those specific primes
OUTPUT:
List of pairs ``[f, m]`` where ``f`` is a dynamical system and ``m`` is a
`2 \times 2` matrix.
EXAMPLES::
sage: P.<x,y> = ProjectiveSpace(QQ,1)
sage: f = DynamicalSystem([x^3 - 13^2*y^3, x*y^2])
sage: from sage.dynamics.arithmetic_dynamics.endPN_minimal_model import BM_all_minimal
sage: BM_all_minimal(f)
[Dynamical System of Projective Space of dimension 1 over Rational Field
Defn: Defined on coordinates by sending (x : y) to
(x^3 - 169*y^3 : x*y^2),
Dynamical System of Projective Space of dimension 1 over Rational Field
Defn: Defined on coordinates by sending (x : y) to
(13*x^3 - y^3 : x*y^2)]
::
sage: P.<x,y> = ProjectiveSpace(QQ,1)
sage: f = DynamicalSystem([x^3 - 6^2*y^3, x*y^2])
sage: from sage.dynamics.arithmetic_dynamics.endPN_minimal_model import BM_all_minimal
sage: BM_all_minimal(f, D=[3])
[Dynamical System of Projective Space of dimension 1 over Rational Field
Defn: Defined on coordinates by sending (x : y) to
(x^3 - 36*y^3 : x*y^2),
Dynamical System of Projective Space of dimension 1 over Rational Field
Defn: Defined on coordinates by sending (x : y) to
(3*x^3 - 4*y^3 : x*y^2)]
::
sage: P.<x,y> = ProjectiveSpace(QQ,1)
sage: f = DynamicalSystem([x^3 - 4^2*y^3, x*y^2])
sage: from sage.dynamics.arithmetic_dynamics.endPN_minimal_model import BM_all_minimal
sage: cl = BM_all_minimal(f, return_transformation=True)
sage: all([f.conjugate(m) == g for g,m in cl])
True
"""
mp = copy(vp)
mp.normalize_coordinates()
BR = mp.domain().base_ring()
MS = MatrixSpace(QQ, 2)
M_Id = MS.one()
d = mp.degree()
F, G = list(mp) #coordinate polys
aff_map = mp.dehomogenize(1)
f, g = aff_map[0].numerator(), aff_map[0].denominator()
z = aff_map.domain().gen(0)
dg = f.parent()(g).degree()
Res = mp.resultant()
##### because of how the bound is compute in lemma 3.3
from sage.dynamics.arithmetic_dynamics.affine_ds import DynamicalSystem_affine
h = f - z*g
A = AffineSpace(BR, 1, h.parent().variable_name())
res = DynamicalSystem_affine([h/g], domain=A).homogenize(1).resultant()
if D is None:
D = ZZ(Res).prime_divisors()
# get the conjugations for each prime independently
# these are returning (p,k,b) so that the matrix is [p^k,b,0,1]
all_pM = []
for p in D:
# all_orbits used to scale inequalities to equalities
all_pM.append(Min(mp, p, res, M_Id, all_orbits=True))
# need the identity for each prime
if [p, 0, 0] not in all_pM[-1]:
all_pM[-1].append([p, 0, 0])
#combine conjugations for all primes
all_M = [M_Id]
for prime_data in all_pM:
#these are (p,k,b) so that the matrix is [p^k,b,0,1]
new_M = []
#.........这里部分代码省略.........
#.........这里部分代码省略.........
Free module of degree 10 and rank 10 over Integer Ring
User basis matrix:
[ 0 0 1 1 0 -1 -1 -1 1 0]
[-1 1 0 1 0 1 1 0 1 1]
[-1 0 0 0 -1 1 1 -2 0 0]
[-1 -1 0 1 1 0 0 1 1 -1]
[ 1 0 -1 0 0 0 -2 -2 0 0]
[ 2 -1 0 0 1 0 1 0 0 -1]
[-1 1 -1 0 1 -1 1 0 -1 -2]
[ 0 0 -1 3 0 0 0 -1 -1 -1]
[ 0 -1 0 -1 2 0 -1 0 0 2]
[ 0 1 1 0 1 1 -2 1 -1 -2]
REFERENCES:
.. [A96] Miklos Ajtai.
Generating hard instances of lattice problems (extended abstract).
STOC, pp. 99--108, ACM, 1996.
.. [GM02] Daniel Goldstein and Andrew Mayer.
On the equidistribution of Hecke points.
Forum Mathematicum, 15:2, pp. 165--189, De Gruyter, 2003.
.. [LM06] Vadim Lyubashevsky and Daniele Micciancio.
Generalized compact knapsacks are collision resistant.
ICALP, pp. 144--155, Springer, 2006.
.. [R05] Oded Regev.
On lattices, learning with errors, random linear codes, and cryptography.
STOC, pp. 84--93, ACM, 2005.
"""
from sage.rings.finite_rings.integer_mod_ring import IntegerModRing
from sage.matrix.constructor import identity_matrix, block_matrix
from sage.matrix.matrix_space import MatrixSpace
from sage.rings.integer_ring import IntegerRing
if seed is not None:
from sage.misc.randstate import set_random_seed
set_random_seed(seed)
if type == 'random':
if n != 1: raise ValueError('random bases require n = 1')
ZZ = IntegerRing()
ZZ_q = IntegerModRing(q)
A = identity_matrix(ZZ_q, n)
if type == 'random' or type == 'modular':
R = MatrixSpace(ZZ_q, m-n, n)
A = A.stack(R.random_element())
elif type == 'ideal':
if quotient is None:
raise ValueError('ideal bases require a quotient polynomial')
try:
quotient = quotient.change_ring(ZZ_q)
except (AttributeError, TypeError):
quotient = quotient.polynomial(base_ring=ZZ_q)
P = quotient.parent()
# P should be a univariate polynomial ring over ZZ_q
if not is_PolynomialRing(P):
raise TypeError("quotient should be a univariate polynomial")
assert P.base_ring() is ZZ_q
if quotient.degree() != n:
raise ValueError('ideal basis requires n = quotient.degree()')
开发者ID:Babyll，项目名称:sage，代码行数:67，代码来源:lattice.py
示例12: __init__
def __init__(self, coxeter_matrix, base_ring, index_set):
"""
Initialize ``self``.
EXAMPLES::
sage: W = CoxeterGroup([[1,3,2],[3,1,3],[2,3,1]])
sage: TestSuite(W).run() # long time
sage: W = CoxeterGroup([[1,3,2],[3,1,4],[2,4,1]], base_ring=QQbar)
sage: TestSuite(W).run() # long time
sage: W = CoxeterGroup([[1,3,2],[3,1,6],[2,6,1]])
sage: TestSuite(W).run(max_runs=30) # long time
sage: W = CoxeterGroup([[1,3,2],[3,1,-1],[2,-1,1]])
sage: TestSuite(W).run(max_runs=30) # long time
We check that :trac:`16630` is fixed::
sage: CoxeterGroup(['D',4], base_ring=QQ).category()
Category of finite coxeter groups
sage: CoxeterGroup(['H',4], base_ring=QQbar).category()
Category of finite coxeter groups
sage: F = CoxeterGroups().Finite()
sage: all(CoxeterGroup([letter,i]) in F
....: for i in range(2,5) for letter in ['A','B','D'])
True
sage: all(CoxeterGroup(['E',i]) in F for i in range(6,9))
True
sage: CoxeterGroup(['F',4]).category()
Category of finite coxeter groups
sage: CoxeterGroup(['G',2]).category()
Category of finite coxeter groups
sage: all(CoxeterGroup(['H',i]) in F for i in range(3,5))
True
sage: all(CoxeterGroup(['I',i]) in F for i in range(2,5))
True
"""
self._matrix = coxeter_matrix
self._index_set = index_set
n = ZZ(coxeter_matrix.nrows())
# Compute the matrix with entries `2 \cos( \pi / m_{ij} )`.
MS = MatrixSpace(base_ring, n, sparse=True)
MC = MS._get_matrix_class()
# FIXME: Hack because there is no ZZ \cup \{ \infty \}: -1 represents \infty
if base_ring is UniversalCyclotomicField():
val = lambda x: base_ring.gen(2 * x) + ~base_ring.gen(2 * x) if x != -1 else base_ring(2)
else:
from sage.functions.trig import cos
from sage.symbolic.constants import pi
val = lambda x: base_ring(2 * cos(pi / x)) if x != -1 else base_ring(2)
gens = [
MS.one() + MC(MS, entries={(i, j): val(coxeter_matrix[i, j]) for j in range(n)}, coerce=True, copy=True)
for i in range(n)
]
# Compute the matrix with entries `- \cos( \pi / m_{ij} )`.
# This describes the bilinear form corresponding to this
# Coxeter system, and might lead us out of our base ring.
base_field = base_ring.fraction_field()
MS2 = MatrixSpace(base_field, n, sparse=True)
MC2 = MS2._get_matrix_class()
self._bilinear = MC2(
MS2,
entries={
(i, j): val(coxeter_matrix[i, j]) / base_field(-2)
for i in range(n)
for j in range(n)
if coxeter_matrix[i, j] != 2
},
coerce=True,
copy=True,
)
self._bilinear.set_immutable()
category = CoxeterGroups()
# Now we shall see if the group is finite, and, if so, refine
# the category to ``category.Finite()``. Otherwise the group is
# infinite and we refine the category to ``category.Infinite()``.
is_finite = self._finite_recognition()
if is_finite:
category = category.Finite()
else:
category = category.Infinite()
FinitelyGeneratedMatrixGroup_generic.__init__(self, n, base_ring, gens, category=category)
def __init__(self, coxeter_matrix, base_ring, index_set):
"""
Initialize ``self``.
EXAMPLES::
sage: W = CoxeterGroup([[1,3,2],[3,1,3],[2,3,1]])
sage: TestSuite(W).run() # long time
sage: W = CoxeterGroup([[1,3,2],[3,1,4],[2,4,1]], base_ring=QQbar)
sage: TestSuite(W).run() # long time
sage: W = CoxeterGroup([[1,3,2],[3,1,6],[2,6,1]])
sage: TestSuite(W).run(max_runs=30) # long time
sage: W = CoxeterGroup([[1,3,2],[3,1,-1],[2,-1,1]])
sage: TestSuite(W).run(max_runs=30) # long time
We check that :trac:`16630` is fixed::
sage: CoxeterGroup(['D',4], base_ring=QQ).category()
Category of finite irreducible coxeter groups
sage: CoxeterGroup(['H',4], base_ring=QQbar).category()
Category of finite irreducible coxeter groups
sage: F = CoxeterGroups().Finite()
sage: all(CoxeterGroup([letter,i]) in F
....: for i in range(2,5) for letter in ['A','B','D'])
True
sage: all(CoxeterGroup(['E',i]) in F for i in range(6,9))
True
sage: CoxeterGroup(['F',4]).category()
Category of finite irreducible coxeter groups
sage: CoxeterGroup(['G',2]).category()
Category of finite irreducible coxeter groups
sage: all(CoxeterGroup(['H',i]) in F for i in range(3,5))
True
sage: all(CoxeterGroup(['I',i]) in F for i in range(2,5))
True
"""
self._matrix = coxeter_matrix
n = coxeter_matrix.rank()
# Compute the matrix with entries `2 \cos( \pi / m_{ij} )`.
MS = MatrixSpace(base_ring, n, sparse=True)
one = MS.one()
# FIXME: Hack because there is no ZZ \cup \{ \infty \}: -1 represents \infty
E = UniversalCyclotomicField().gen
if base_ring is UniversalCyclotomicField():
def val(x):
if x == -1:
return 2
else:
return E(2 * x) + ~E(2 * x)
elif is_QuadraticField(base_ring):
def val(x):
if x == -1:
return 2
else:
return base_ring((E(2 * x) + ~E(2 * x)).to_cyclotomic_field())
else:
from sage.functions.trig import cos
from sage.symbolic.constants import pi
def val(x):
if x == -1:
return 2
else:
return base_ring(2 * cos(pi / x))
gens = [one + MS([SparseEntry(i, j, val(coxeter_matrix[index_set[i], index_set[j]]))
for j in range(n)])
for i in range(n)]
# Make the generators dense matrices for consistency and speed
gens = [g.dense_matrix() for g in gens]
category = CoxeterGroups()
# Now we shall see if the group is finite, and, if so, refine
# the category to ``category.Finite()``. Otherwise the group is
# infinite and we refine the category to ``category.Infinite()``.
if self._matrix.is_finite():
category = category.Finite()
else:
category = category.Infinite()
if all(self._matrix._matrix[i, j] == 2
for i in range(n) for j in range(i)):
category = category.Commutative()
if self._matrix.is_irreducible():
category = category.Irreducible()
self._index_set_inverse = {i: ii
for ii, i in enumerate(self._matrix.index_set())}
FinitelyGeneratedMatrixGroup_generic.__init__(self, ZZ(n), base_ring,
gens, category=category)
def HS_all_minimal(f, return_transformation=False, D=None):
r"""
Determine a representative in each `SL(2,\ZZ)` orbit with minimal resultant.
This function implements the algorithm in Hutz-Stoll [HS2018]_.
A representative in each distinct `SL(2,\ZZ)` orbit is returned.
The input ``f`` must have minimal resultant in its conguacy class.
INPUT:
- ``f`` -- dynamical system on the projective line with minimal resultant
- ``return_transformation`` -- (default: ``False``) boolean; this
signals a return of the ``PGL_2`` transformation to conjugate ``vp``
to the calculated minimal model
- ``D`` -- a list of primes, in case one only wants to check minimality
at those specific primes
OUTPUT:
List of pairs ``[f, m]``, where ``f`` is a dynamical system and ``m``
is a `2 \times 2` matrix.
EXAMPLES::
sage: P.<x,y> = ProjectiveSpace(QQ,1)
sage: f = DynamicalSystem([x^3 - 6^2*y^3, x^2*y])
sage: from sage.dynamics.arithmetic_dynamics.endPN_minimal_model import HS_all_minimal
sage: HS_all_minimal(f)
[Dynamical System of Projective Space of dimension 1 over Rational Field
Defn: Defined on coordinates by sending (x : y) to
(x^3 - 36*y^3 : x^2*y),
Dynamical System of Projective Space of dimension 1 over Rational Field
Defn: Defined on coordinates by sending (x : y) to
(9*x^3 - 12*y^3 : 9*x^2*y),
Dynamical System of Projective Space of dimension 1 over Rational Field
Defn: Defined on coordinates by sending (x : y) to
(4*x^3 - 18*y^3 : 4*x^2*y),
Dynamical System of Projective Space of dimension 1 over Rational Field
Defn: Defined on coordinates by sending (x : y) to
(36*x^3 - 6*y^3 : 36*x^2*y)]
sage: HS_all_minimal(f, D=[3])
[Dynamical System of Projective Space of dimension 1 over Rational Field
Defn: Defined on coordinates by sending (x : y) to
(x^3 - 36*y^3 : x^2*y),
Dynamical System of Projective Space of dimension 1 over Rational Field
Defn: Defined on coordinates by sending (x : y) to
(9*x^3 - 12*y^3 : 9*x^2*y)]
::
sage: P.<x,y> = ProjectiveSpace(QQ,1)
sage: f = DynamicalSystem([x^3 - 6^2*y^3, x*y^2])
sage: from sage.dynamics.arithmetic_dynamics.endPN_minimal_model import HS_all_minimal
sage: cl = HS_all_minimal(f, return_transformation=True)
sage: all([f.conjugate(m) == g for g,m in cl])
True
"""
MS = MatrixSpace(ZZ, 2)
m = MS.one()
F = copy(f)
F.normalize_coordinates()
if F.degree() == 1:
raise ValueError("function must be degree at least 2")
if f.degree() % 2 == 0:
#there is only one orbit for even degree
if return_transformation:
return [[f, m]]
else:
return [f]
if D is None:
res = ZZ(F.resultant())
D = res.prime_divisors()
M = [[F, m]]
for p in D:
# get p-orbits
Mp = HS_all_minimal_p(p, F, m, return_transformation=True)
# combine with previous orbits representatives
M = [[g.conjugate(t), t*s] for g,s in M for G,t in Mp]
if return_transformation:
return M
else:
return [funct for funct, matr in M]
#.........这里部分代码省略.........
[ 0 0 0 0 0 11 0 0 0 0]
[ 0 0 0 0 11 0 0 0 0 0]
[ 0 0 0 1 -5 -2 -1 1 -3 5]
[ 0 0 1 0 -3 4 1 4 -3 -2]
[ 0 1 0 0 -4 5 -3 3 5 3]
[ 1 0 0 0 -2 -1 4 2 5 4]
* Relation of primal and dual bases ::
sage: B_primal=sage.crypto.gen_lattice(m=10, q=11, seed=42)
sage: B_dual=sage.crypto.gen_lattice(m=10, q=11, seed=42, dual=True)
sage: B_dual_alt=transpose(11*B_primal.inverse()).change_ring(ZZ)
sage: B_dual_alt.hermite_form() == B_dual.hermite_form()
True
REFERENCES:
.. [A96] Miklos Ajtai.
Generating hard instances of lattice problems (extended abstract).
STOC, pp. 99--108, ACM, 1996.
.. [GM02] Daniel Goldstein and Andrew Mayer.
On the equidistribution of Hecke points.
Forum Mathematicum, 15:2, pp. 165--189, De Gruyter, 2003.
.. [LM06] Vadim Lyubashevsky and Daniele Micciancio.
Generalized compact knapsacks are collision resistant.
ICALP, pp. 144--155, Springer, 2006.
.. [R05] Oded Regev.
On lattices, learning with errors, random linear codes, and cryptography.
STOC, pp. 84--93, ACM, 2005.
"""
from sage.rings.finite_rings.integer_mod_ring \
import IntegerModRing
from sage.matrix.constructor import matrix, \
identity_matrix, block_matrix
from sage.matrix.matrix_space import MatrixSpace
from sage.rings.integer_ring import IntegerRing
if seed != None:
from sage.misc.randstate import set_random_seed
set_random_seed(seed)
if type == 'random':
if n != 1: raise ValueError('random bases require n = 1')
ZZ = IntegerRing()
ZZ_q = IntegerModRing(q)
A = identity_matrix(ZZ_q, n)
if type == 'random' or type == 'modular':
R = MatrixSpace(ZZ_q, m-n, n)
A = A.stack(R.random_element())
elif type == 'ideal':
if quotient == None: raise \
ValueError('ideal bases require a quotient polynomial')
x = quotient.default_variable()
if n != quotient.degree(x): raise \
ValueError('ideal bases require n = quotient.degree()')
R = ZZ_q[x].quotient(quotient, x)
for i in range(m//n):
A = A.stack(R.random_element().matrix())
elif type == 'cyclotomic':
from sage.rings.arith import euler_phi
from sage.misc.functional import cyclotomic_polynomial
# we assume that n+1 <= min( euler_phi^{-1}(n) ) <= 2*n
found = False
for k in range(2*n,n,-1):
if euler_phi(k) == n:
found = True
break
if not found: raise \
ValueError('cyclotomic bases require that n is an image of' + \
'Euler\'s totient function')
R = ZZ_q['x'].quotient(cyclotomic_polynomial(k, 'x'), 'x')
for i in range(m//n):
A = A.stack(R.random_element().matrix())
# switch from representatives 0,...,(q-1) to (1-q)/2,....,(q-1)/2
def minrep(a):
if abs(a-q) < abs(a): return a-q
else: return a
A_prime = A[n:m].lift().apply_map(minrep)
if not dual:
B = block_matrix([[ZZ(q), ZZ.zero()], [A_prime, ZZ.one()] ], \
subdivide=False)
else:
B = block_matrix([[ZZ.one(), -A_prime.transpose()], [ZZ.zero(), \
ZZ(q)]], subdivide=False)
for i in range(m//2): B.swap_rows(i,m-i-1)
if not ntl:
return B
else:
return B._ntl_()
def __init__(self, coxeter_matrix, base_ring, index_set):
"""
Initialize ``self``.
EXAMPLES::
sage: W = CoxeterGroup([[1,3,2],[3,1,3],[2,3,1]])
sage: TestSuite(W).run() # long time
sage: W = CoxeterGroup([[1,3,2],[3,1,4],[2,4,1]], base_ring=QQbar)
sage: TestSuite(W).run() # long time
sage: W = CoxeterGroup([[1,3,2],[3,1,6],[2,6,1]])
sage: TestSuite(W).run(max_runs=30) # long time
sage: W = CoxeterGroup([[1,3,2],[3,1,-1],[2,-1,1]])
sage: TestSuite(W).run(max_runs=30) # long time
We check that :trac:`16630` is fixed::
sage: CoxeterGroup(['D',4], base_ring=QQ).category()
Category of finite coxeter groups
sage: CoxeterGroup(['H',4], base_ring=QQbar).category()
Category of finite coxeter groups
sage: F = CoxeterGroups().Finite()
sage: all(CoxeterGroup([letter,i]) in F
....: for i in range(2,5) for letter in ['A','B','D'])
True
sage: all(CoxeterGroup(['E',i]) in F for i in range(6,9))
True
sage: CoxeterGroup(['F',4]).category()
Category of finite coxeter groups
sage: CoxeterGroup(['G',2]).category()
Category of finite coxeter groups
sage: all(CoxeterGroup(['H',i]) in F for i in range(3,5))
True
sage: all(CoxeterGroup(['I',i]) in F for i in range(2,5))
True
"""
self._matrix = coxeter_matrix
n = coxeter_matrix.rank()
# Compute the matrix with entries `2 \cos( \pi / m_{ij} )`.
MS = MatrixSpace(base_ring, n, sparse=True)
MC = MS._get_matrix_class()
# FIXME: Hack because there is no ZZ \cup \{ \infty \}: -1 represents \infty
if base_ring is UniversalCyclotomicField():
val = lambda x: base_ring.gen(2*x) + ~base_ring.gen(2*x) if x != -1 else base_ring(2)
else:
from sage.functions.trig import cos
from sage.symbolic.constants import pi
val = lambda x: base_ring(2*cos(pi / x)) if x != -1 else base_ring(2)
gens = [MS.one() + MC(MS, entries={(i, j): val(coxeter_matrix[index_set[i], index_set[j]])
for j in range(n)},
coerce=True, copy=True)
for i in range(n)]
category = CoxeterGroups()
# Now we shall see if the group is finite, and, if so, refine
# the category to ``category.Finite()``. Otherwise the group is
# infinite and we refine the category to ``category.Infinite()``.
if self._matrix.is_finite():
category = category.Finite()
else:
category = category.Infinite()
FinitelyGeneratedMatrixGroup_generic.__init__(self, ZZ(n), base_ring,
gens, category=category)
#.........这里部分代码省略.........
raise ValueError('the coefficient ring must be a field')
# The following are all dictionaries indexed by dimension.
# For each n, gens[n] is an ordered list of the n-cells generating the complex M.
gens = {}
pi_data = {}
phi_data = {}
iota_data = {}
for n in range(-1, K.dimension()+1):
gens[n] = []
C = K.chain_complex(base_ring=base_ring)
n_cells = []
pi_cols = []
iota_cols = {}
for dim in range(K.dimension()+1):
# old_cells: cells one dimension lower.
old_cells = n_cells
# n_cells: the standard basis for the vector space C.free_module(dim).
n_cells = C.free_module(dim).gens()
diff = C.differential(dim)
# diff is sparse and low density. Dense matrices are faster
# over finite fields, but for low density matrices, sparse
# matrices are faster over the rationals.
if base_ring != QQ:
diff = diff.dense_matrix()
rank = len(n_cells)
old_rank = len(old_cells)
# Create some matrix spaces to try to speed up matrix creation.
MS_pi_t = MatrixSpace(base_ring, old_rank, len(gens[dim-1]))
pi_old = MS_pi_t.matrix(pi_cols).transpose()
iota_cols_old = iota_cols
iota_cols = {}
pi_cols_old = pi_cols
pi_cols = []
phi_old = MatrixSpace(base_ring, rank, old_rank, sparse=(base_ring==QQ)).zero()
phi_old_cols = phi_old.columns()
phi_old = conditionally_sparse(phi_old)
to_be_deleted = []
zero_vector = vector(base_ring, rank)
pi_nrows = pi_old.nrows()
for c_idx, c in enumerate(n_cells):
# c_bar = c - phi(bdry(c)):
# Avoid a bug in matrix-vector multiplication (trac 19378):
if not diff:
c_bar = c
pi_bdry_c_bar = False
else:
if base_ring == QQ:
c_bar = c - phi_old * (diff * c)
pi_bdry_c_bar = conditionally_sparse(pi_old) * (diff * c_bar)
else:
c_bar = c - phi_old * diff * c
pi_bdry_c_bar = conditionally_sparse(pi_old) * diff * c_bar
# One small typo in the published algorithm: it says
# "if bdry(c_bar) == 0", but should say
# "if pi(bdry(c_bar)) == 0".
if not pi_bdry_c_bar:
客服电话
APP下载
官方微信
请发表评论