Polyhedron exchange transformations (PETs) and induced transformations¶
Polyhedron exchange transformations and induced transformations
EXAMPLES:
A polyhedron partition:
sage: from slabbe import PolyhedronPartition
sage: h = 1/3
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)])
sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)])
sage: s = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s})
Applying a rationnal rotation:
sage: from slabbe import PolyhedronExchangeTransformation as PET
sage: base = identity_matrix(2)
sage: translation = vector((2/3, 0))
sage: u = PET.toral_translation(base, translation)
sage: Q = u(P)
sage: Q
Polyhedron partition of 4 atoms with 4 letters
Inducing an irrationnal rotation on a subdomain:
sage: z = polygen(QQ, 'z') #z = QQ['z'].0 # same as
sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6))
sage: phi = K.gen()
sage: h = 1/phi^2
sage: p = Polyhedron([(0,h),(0,1),(h,1)])
sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)])
sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)])
sage: s = Polyhedron([(h,0), (1,0), (1,h)])
sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s}, base_ring=K)
sage: base = identity_matrix(2)
sage: translation = vector((1/phi, 0))
sage: u = PET.toral_translation(base, translation)
sage: ieq = [h, -1, 0] # x0 <= h
sage: P1,sub01 = u.induced_partition(ieq, P)
sage: P1
Polyhedron partition of 7 atoms with 7 letters
sage: sub01
{0: [0, 2],
1: [1, 2],
2: [1, 3],
3: [0, 2, 2],
4: [1, 2, 2],
5: [1, 3, 2],
6: [1, 3, 3]}
AUTHORS:
Sébastien Labbé, January 2019, added a class for polyhedron exchange transformations
- class slabbe.polyhedron_exchange_transformation.PolyhedronExchangeTransformation(partition, translations)¶
Bases:
object
Polyhedron Exchange Transformation (PET).
INPUT:
partition
– a polyhedron partitiontranslations
– list or dict
EXAMPLES:
sage: from slabbe import PolyhedronPartition, PolyhedronExchangeTransformation sage: h = 1/3 sage: p = Polyhedron([(0,0),(h,0),(h,1),(0,1)]) sage: q = Polyhedron([(1,0),(h,0),(h,1),(1,1)]) sage: P = PolyhedronPartition({0:p, 1:q}) sage: T = {0:(1-h,0), 1:(-h,0)} sage: PolyhedronExchangeTransformation(P, T) Polyhedron Exchange Transformation of Polyhedron partition of 2 atoms with 2 letters with translations {0: (2/3, 0), 1: (-1/3, 0)}
REFERENCES:
Schwartz, Richard Evan. The Octagonal PETs. First Edition edition. Providence, Rhode Island: American Mathematical Society, 2014.
- ambient_space()¶
EXAMPLES:
sage: from slabbe import PolyhedronPartition, PolyhedronExchangeTransformation sage: h = 1/3 sage: p = Polyhedron([(0,0),(h,0),(h,1),(0,1)]) sage: q = Polyhedron([(1,0),(h,0),(h,1),(1,1)]) sage: P = PolyhedronPartition({0:p, 1:q}) sage: T = {0:(1-h,0), 1:(-h,0)} sage: F = PolyhedronExchangeTransformation(P, T) sage: F.ambient_space() Vector space of dimension 2 over Rational Field
- cylinder(word, partition=None)¶
Return the region associated to the coding word.
INPUT:
word
– listpartition
– polyhedron partition (default:None
), if None, it uses the domain partition of the transformation
OUTPUT:
polyhedron partition
EXAMPLES:
sage: from slabbe import PolyhedronPartition sage: h = 1/2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (1,1), (1,h), (h,0)]) sage: r = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition([p,q,r])
sage: from slabbe import PolyhedronExchangeTransformation as PET sage: base = identity_matrix(2) sage: translation = vector((1/3, 0)) sage: u = PET.toral_translation(base, translation) sage: c = u.cylinder([2,2], P); c Polyhedron partition of 1 atoms with 1 letters sage: c.alphabet() {0}
sage: u.cylinder([1,1], P) Polyhedron partition of 2 atoms with 2 letters sage: u.cylinder([1], P) Polyhedron partition of 1 atoms with 1 letters
Cylinders of words of length 0:
sage: u.cylinder([], P).volume() 1
Cylinders of words of length 1:
sage: C1 = [u.cylinder([a], P).volume() for a in range(3)] sage: C1 [1/8, 3/4, 1/8] sage: sum(C1) 1
Cylinders of words of length 2:
sage: import itertools sage: L2 = itertools.product(range(3),repeat=2) sage: C2 = [u.cylinder([a,b], P).volume() for (a,b) in L2] sage: C2 [1/72, 1/9, 0, 1/9, 19/36, 1/9, 0, 1/9, 1/72] sage: sum(C2) 1
Cylinders of words of length 3:
sage: L3 = itertools.product(range(3),repeat=3) sage: C3 = [u.cylinder([a,b,c], P).volume() for (a,b,c) in L3] sage: sum(C3) 1
TESTS:
sage: u.cylinder([0,0,0], P) Polyhedron partition of 0 atoms with 0 letters sage: u.cylinder([2,3], P) Polyhedron partition of 0 atoms with 0 letters sage: u.cylinder([2,1], P) Polyhedron partition of 1 atoms with 1 letters sage: u.cylinder([], P) Polyhedron partition of 3 atoms with 3 letters
- cylinders(size, partition=None)¶
Return the cylinders of given size.
INPUT:
size
– nonnegative integerpartition
– polyhedron partition (default:None
), if None, it uses the domain partition of the transformation
OUTPUT:
polyhedron partition
EXAMPLES:
sage: from slabbe import PolyhedronExchangeTransformation as PET sage: base = identity_matrix(2) sage: translation = vector((1/3, 0)) sage: u = PET.toral_translation(base, translation) sage: [u.cylinders(i) for i in range(5)] [Polyhedron partition of 1 atoms with 1 letters, Polyhedron partition of 2 atoms with 2 letters, Polyhedron partition of 3 atoms with 3 letters, Polyhedron partition of 3 atoms with 3 letters, Polyhedron partition of 3 atoms with 3 letters] sage: [u.cylinders(i).alphabet() for i in range(5)] [{()}, {0, 1}, {0, 1, 2}, {0, 1, 2}, {0, 1, 2}]
- domain()¶
Return the domain of the exchange transformation.
OUTPUT:
a polyhedron
EXAMPLES:
sage: from slabbe import PolyhedronPartition, PolyhedronExchangeTransformation sage: h = 1/3 sage: p = Polyhedron([(0,0),(h,0),(h,1),(0,1)]) sage: q = Polyhedron([(1,0),(h,0),(h,1),(1,1)]) sage: P = PolyhedronPartition({0:p, 1:q}) sage: T = {0:(1-h,0), 1:(-h,0)} sage: F = PolyhedronExchangeTransformation(P, T) sage: F.domain() A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices sage: F.domain().vertices() (A vertex at (0, 0), A vertex at (0, 1), A vertex at (1, 0), A vertex at (1, 1))
- image_partition()¶
Return the partition of the image.
EXAMPLES:
sage: from slabbe import PolyhedronPartition, PolyhedronExchangeTransformation sage: h = 1/3 sage: p = Polyhedron([(0,0),(h,0),(h,1),(0,1)]) sage: q = Polyhedron([(1,0),(h,0),(h,1),(1,1)]) sage: P = PolyhedronPartition({0:p, 1:q}) sage: T = {0:(1-h,0), 1:(-h,0)} sage: F = PolyhedronExchangeTransformation(P, T) sage: F.image_partition() Polyhedron partition of 2 atoms with 2 letters
sage: h = 1/3 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)]) sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)]) sage: s = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition([(0,p), (0,q), (1,r), (1,s)]) sage: T = {0:(1-h,0), 1:(-h,0)} sage: F = PolyhedronExchangeTransformation(P, T) sage: F.image_partition() Polyhedron partition of 4 atoms with 2 letters
- induced_partition(ieq, partition=None, substitution_type='dict')¶
Returns the partition of the induced transformation on the domain.
INPUT:
ieq
– list, an inequality. An entry equal to “[-1,7,3,4]” represents the inequality 7x_1+3x_2+4x_3>= 1.partition
– polyhedron partition (default:None
), if None, it uses the domain partition of the transformationsubstitution_type
– string (default:'dict'
), if'column'
or'row'
, it returns a substitution2d, otherwise it returns a dict.
OUTPUT:
a polyhedron partition
a substitution2d or a dict
EXAMPLES:
sage: from slabbe import PolyhedronExchangeTransformation as PET sage: base = identity_matrix(2) sage: translation = vector((1/3, 0)) sage: u = PET.toral_translation(base, translation)
We compute the induced partition of a polyhedron exchange transformation on a subdomain given by an inequality:
sage: ieq = [1/3, -1, 0] # x0 <= 1/3 sage: u.induced_partition(ieq) (Polyhedron partition of 1 atoms with 1 letters, {0: [0, 0, 1]}) sage: ieq = [1/2, -1, 0] # x0 <= 1/2 sage: u.induced_partition(ieq) (Polyhedron partition of 3 atoms with 3 letters, {0: [0], 1: [0, 1], 2: [0, 0, 1]})
The second output can be turned into a column or a row Substitution2d if desired:
sage: u.induced_partition(ieq, substitution_type='row') (Polyhedron partition of 3 atoms with 3 letters, Substitution 2d: {0: [[0]], 1: [[0], [1]], 2: [[0], [0], [1]]})
Now we construct a another coding partition:
sage: from slabbe import PolyhedronPartition sage: h = 1/3 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)]) sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)]) sage: s = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s})
We use this other partition to compute the induced partition:
sage: ieq = [h, -1, 0] # x0 <= h sage: Q,sub = u.induced_partition(ieq, P) sage: Q Polyhedron partition of 4 atoms with 4 letters sage: sub {0: [0, 2, 2], 1: [1, 2, 2], 2: [1, 2, 3], 3: [1, 3, 3]}
sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s}) sage: ieq2 = [1/2, -1, 0] # x0 <= 1/2 sage: Q,sub = u.induced_partition(ieq2, P) sage: Q Polyhedron partition of 9 atoms with 9 letters sage: sub {0: [0], 1: [1], 2: [2, 2], 3: [2, 3], 4: [3, 3], 5: [0, 2, 2], 6: [1, 2, 2], 7: [1, 2, 3], 8: [1, 3, 3]}
Irrationnal rotations:
sage: z = polygen(QQ, 'z') #z = QQ['z'].0 # same as sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6)) sage: phi = K.gen() sage: h = 1/phi^2 sage: p = Polyhedron([(0,h),(0,1),(h,1)]) sage: q = Polyhedron([(0,0), (0,h), (h,1), (h,0)]) sage: r = Polyhedron([(h,1), (1,1), (1,h), (h,0)]) sage: s = Polyhedron([(h,0), (1,0), (1,h)]) sage: P = PolyhedronPartition({0:p, 1:q, 2:r, 3:s}, base_ring=K) sage: base = identity_matrix(2) sage: translation = vector((1/phi, 0)) sage: u = PET.toral_translation(base, translation) sage: ieq = [h, -1, 0] # x0 <= h sage: P1,sub01 = u.induced_partition(ieq, P) sage: P1 Polyhedron partition of 7 atoms with 7 letters sage: sub01 {0: [0, 2], 1: [1, 2], 2: [1, 3], 3: [0, 2, 2], 4: [1, 2, 2], 5: [1, 3, 2], 6: [1, 3, 3]}
We do the induction on a smaller domain:
sage: ieq2 = [1/phi^3, -1, 0] # x0 <= h sage: P2,sub02 = u.induced_partition(ieq2, P) sage: P2 Polyhedron partition of 10 atoms with 10 letters sage: sub02 {0: [0, 2, 2], 1: [1, 2, 2], 2: [1, 3, 2], 3: [1, 3, 3], 4: [0, 2, 0, 2, 2], 5: [0, 2, 1, 2, 2], 6: [1, 2, 1, 2, 2], 7: [1, 2, 1, 3, 2], 8: [1, 3, 1, 3, 2], 9: [1, 3, 1, 3, 3]}
We check that inductions commute:
sage: base = diagonal_matrix((phi^-2,1)) sage: translation = vector((phi^-3, 0)) sage: u1 = PET.toral_translation(base, translation) sage: P2_alt,sub12 = u1.induced_partition(ieq2, P1) sage: P2_alt Polyhedron partition of 10 atoms with 10 letters sage: P2_alt == P2 True
Up to a permutation of the alphabet,
sub02
andsub01*sub12
are equal:sage: s01 = WordMorphism(sub01) sage: s12 = WordMorphism(sub12) sage: s02 = WordMorphism(sub02) sage: s02 WordMorphism: 0->022, 1->122, 2->132, 3->133, 4->02022, 5->02122, 6->12122, 7->12132, 8->13132, 9->13133 sage: s01*s12 == s02 True
By chance, the above is true, but in general, we have:
sage: perm = WordMorphism(P2.keys_permutation(P2_alt)) sage: perm WordMorphism: 0->0, 1->1, 2->2, 3->3, 4->4, 5->5, 6->6, 7->7, 8->8, 9->9 sage: s01*s12*perm == s02 True
- induced_transformation(ieq)¶
Return the induced transformation on the domain.
INPUT:
ieq
– list, an inequality. An entry equal to “[-1,7,3,4]” represents the inequality 7x_1+3x_2+4x_3>= 1.
OUTPUT:
a polyhedron exchange transformation on the subdomain
a substitution (dict)
EXAMPLES:
sage: from slabbe import PolyhedronExchangeTransformation as PET sage: base = identity_matrix(2) sage: translation = vector((1/3, 0)) sage: u = PET.toral_translation(base, translation)
We compute the induced transformation of a polyhedron exchange transformation on a subdomain given by an inequality:
sage: ieq = [1/2, -1, 0] # x0 <= 1/2 sage: T,sub = u.induced_transformation(ieq) sage: T Polyhedron Exchange Transformation of Polyhedron partition of 3 atoms with 3 letters with translations {0: (1/3, 0), 1: (-1/3, 0), 2: (0, 0)} sage: sub {0: [0], 1: [0, 1], 2: [0, 0, 1]}
- inverse()¶
Return the inverse of self.
EXAMPLES:
sage: from slabbe import PolyhedronPartition, PolyhedronExchangeTransformation sage: h = 1/3 sage: p = Polyhedron([(0,0),(h,0),(h,1),(0,1)]) sage: q = Polyhedron([(1,0),(h,0),(h,1),(1,1)]) sage: P = PolyhedronPartition({0:p, 1:q}) sage: T = {0:(1-h,0), 1:(-h,0)} sage: F = PolyhedronExchangeTransformation(P, T) sage: F Polyhedron Exchange Transformation of Polyhedron partition of 2 atoms with 2 letters with translations {0: (2/3, 0), 1: (-1/3, 0)}
sage: F.inverse() Polyhedron Exchange Transformation of Polyhedron partition of 2 atoms with 2 letters with translations {0: (-2/3, 0), 1: (1/3, 0)}
- merge_atoms_with_same_translation()¶
Return a new partition into convex polyhedrons where atoms mapped by the same translation are merged if their union is convex.
EXAMPLES:
sage: from slabbe import PolyhedronPartition, PolyhedronExchangeTransformation sage: h = 1/3 sage: p = Polyhedron([(0,0),(h,0),(h,h),(0,h)]) sage: q = Polyhedron([(0,h),(h,h),(h,1),(0,1)]) sage: r = Polyhedron([(1,0),(h,0),(h,1),(1,1)]) sage: P = PolyhedronPartition({0:p, 1:q, 2:r}) sage: d = {0:(1-h,0), 1:(1-h,0), 2:(-h,0)} sage: T = PolyhedronExchangeTransformation(P, d) sage: T Polyhedron Exchange Transformation of Polyhedron partition of 3 atoms with 3 letters with translations {0: (2/3, 0), 1: (2/3, 0), 2: (-1/3, 0)} sage: T.merge_atoms_with_same_translation() Polyhedron Exchange Transformation of Polyhedron partition of 2 atoms with 2 letters with translations {0: (2/3, 0), 2: (-1/3, 0)}
- partition()¶
EXAMPLES:
sage: from slabbe import PolyhedronPartition, PolyhedronExchangeTransformation sage: h = 1/3 sage: p = Polyhedron([(0,0),(h,0),(h,1),(0,1)]) sage: q = Polyhedron([(1,0),(h,0),(h,1),(1,1)]) sage: P = PolyhedronPartition({0:p, 1:q}) sage: d = {0:(1-h,0), 1:(-h,0)} sage: T = PolyhedronExchangeTransformation(P, d) sage: T.partition() Polyhedron partition of 2 atoms with 2 letters
- plot()¶
EXAMPLES:
sage: from slabbe import PolyhedronPartition, PolyhedronExchangeTransformation sage: h = 1/3 sage: p = Polyhedron([(0,0),(h,0),(h,1),(0,1)]) sage: q = Polyhedron([(1,0),(h,0),(h,1),(1,1)]) sage: P = PolyhedronPartition({0:p, 1:q}) sage: d = {0:(1-h,0), 1:(-h,0)} sage: T = PolyhedronExchangeTransformation(P, d) sage: T.plot() Graphics object consisting of 16 graphics primitives
- classmethod toral_translation(base, translation, fundamental_domain=None)¶
Return a polyhedron exchange transformation defined by a translation on a d-dimensional torus.
INPUT:
base
– matrix, the columns are the base of a latticetranslation
– vector, translation vectorfundamental_domain
– polyhedron orNone
(default:None
), ifNone
the parallelotope defined bybase
is used.
OUTPUT:
a polyhedron exchange transformation on the fundamental domain of the lattice
EXAMPLES:
sage: from slabbe import PolyhedronExchangeTransformation as PET sage: base = diagonal_matrix((1,1)) sage: translation = vector((1/5, 1/3)) sage: T = PET.toral_translation(base, translation) sage: T Polyhedron Exchange Transformation of Polyhedron partition of 4 atoms with 4 letters with translations {0: (1/5, 1/3), 1: (1/5, -2/3), 2: (-4/5, 1/3), 3: (-4/5, -2/3)} sage: T.partition() Polyhedron partition of 4 atoms with 4 letters
Some preliminary definitions:
sage: z = polygen(QQ, 'z') #z = QQ['z'].0 # same as sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6)) sage: phi = K.gen() sage: vertices = ((-phi + 2, phi - 1), (-phi + 2, 1), (phi - 1, 1)) sage: p = Polyhedron(vertices, base_ring=K)
A translation +1 modulo phi on the x coordinate:
sage: base = diagonal_matrix((phi,phi)) sage: translation = vector((1, 0)) sage: t0 = PET.toral_translation(base, translation) sage: t0 Polyhedron Exchange Transformation of Polyhedron partition of 2 atoms with 2 letters with translations {0: ..., 1: ...} sage: t0(p).vertices() (A vertex at (-phi + 3, phi - 1), A vertex at (-phi + 3, 1), A vertex at (phi, 1))
The inverse map:
sage: t0.inverse() Polyhedron Exchange Transformation of Polyhedron partition of 2 atoms with 2 letters with translations {0: ..., 1: ...} sage: t0(p) == p False sage: t0.inverse()(t0(p)) == p True
A rotation modulo 1 on the y coordinate:
sage: base = diagonal_matrix((phi,phi)) sage: translation = vector((0, 1)) sage: t1 = PET.toral_translation(base, translation) sage: t1(p).vertices() (A vertex at (-phi + 2, 0), A vertex at (-phi + 2, -phi + 2), A vertex at (phi - 1, -phi + 2))
It works if the translation is larger than the fundamental domain:
sage: base = diagonal_matrix((1,1)) sage: translation = vector((phi, 0)) sage: t2 = PET.toral_translation(base, translation) sage: t2(p).vertices() (A vertex at (0, phi - 1), A vertex at (0, 1), A vertex at (2*phi - 3, 1))
The domain is the fundamental domain of the given lattice:
sage: base = diagonal_matrix((phi^-2,1)) sage: translation = vector((phi^-3, 0)) sage: t3 = PET.toral_translation(base, translation) sage: sorted(t3.domain().vertices()) [A vertex at (0, 0), A vertex at (0, 1), A vertex at (-phi + 2, 0), A vertex at (-phi + 2, 1)]
The fundamental domain can be given as input. For example, it can be a translated copy of the base parallelotope:
sage: base = diagonal_matrix((1,1)) sage: translation = vector((1/5, 1/3)) sage: F = polytopes.parallelotope(base) sage: T = PET.toral_translation(base, translation, F-vector((1/10,1/10)))
But it does not always work well yet, for example for other shape of fundamental domains:
sage: m = matrix(2, (1,1,0,1)) sage: mF = polytopes.parallelotope(m*base) sage: T = PET.toral_translation(base, translation, mF) Traceback (most recent call last): ... NotImplementedError: Volume of the partition is 73/75 but the fundamental domain as volume 1. The code does not handle this case properly yet.
- translate_domain(displacement)¶
Return the PET on a domain translated by some displacement.
INPUT:
displacement
– a displacement vector or a list/tuple of coordinates that determines a displacement vector.
OUTPUT:
The translated PET
EXAMPLES:
sage: from slabbe import PolyhedronPartition, PolyhedronExchangeTransformation sage: h = 4/5 sage: p = Polyhedron([(0,0),(h,0),(h,1),(0,1)]) sage: q = Polyhedron([(1,0),(h,0),(h,1),(1,1)]) sage: P = PolyhedronPartition({0:p, 1:q}) sage: T = {0:(1-h,0), 1:(-h,0)} sage: F = PolyhedronExchangeTransformation(P, T) sage: Ft = F.translate_domain((3,1)) sage: Ft Polyhedron Exchange Transformation of Polyhedron partition of 2 atoms with 2 letters with translations {0: (1/5, 0), 1: (-4/5, 0)} sage: Ft.domain().vertices() (A vertex at (3, 1), A vertex at (3, 2), A vertex at (4, 1), A vertex at (4, 2))
- translations()¶
EXAMPLES:
sage: from slabbe import PolyhedronPartition, PolyhedronExchangeTransformation sage: h = 1/3 sage: p = Polyhedron([(0,0),(h,0),(h,1),(0,1)]) sage: q = Polyhedron([(1,0),(h,0),(h,1),(1,1)]) sage: P = PolyhedronPartition({0:p, 1:q}) sage: T = {0:(1-h,0), 1:(-h,0)} sage: F = PolyhedronExchangeTransformation(P, T) sage: F.translations() {0: (2/3, 0), 1: (-1/3, 0)}