Graph-directed iterated function system (GIFS)¶
Graph-directed iterated function system (GIFS)
We allow the functions to be contracting or not. When the functions are inflations, it allows to represent inflation rules and stone inflations as in Definition 5.17 of [BG13].
EXAMPLES:
The Cantor set:
sage: from slabbe import GraphDirectedIteratedFunctionSystem as GIFS
sage: F = AffineGroup(1, QQ)
sage: f1 = F.linear(1/3); f1
x |-> [1/3] x + [0]
sage: f2 = F(1/3, vector([2/3])); f2
x |-> [1/3] x + [2/3]
sage: cantor_IFS = GIFS(QQ^1, [(0,0,f1),(0,0,f2)])
sage: cantor_IFS
GIFS defined by 2 maps on
Vector space of dimension 1 over Rational Field
Fibonacci substitution:
sage: m = WordMorphism('a->ab,b->a')
sage: fibo_ifs = GIFS.from_one_dimensional_substitution(m)
sage: fibo_ifs
GIFS defined by 3 maps on Vector space of dimension 1 over
Number Field in root with defining polynomial x^2 - x - 1 with
root = 1.618033988749895?
Its element-wise Galois conjugate is a contracting IFS:
sage: fibo_ifs.galois_conjugate().pp()
GIFS defined by 3 maps on Vector space of dimension 1 over Number Field in root with defining polynomial x^2 - x - 1 with root = 1.618033988749895?
edge (0,0):
x |-> [-root + 1] x + [0]
edge (1,0):
x |-> [-root + 1] x + [1]
edge (0,1):
x |-> [-root + 1] x + [0]
Direct Product of 2 Fibonacci:
sage: from slabbe import GraphDirectedIteratedFunctionSystem as GIFS
sage: from slabbe import Substitution2d
sage: d = {0:[[3]], 1:[[3],[2]], 2:[[3,1]], 3:[[3,1],[2,0]]}
sage: s = Substitution2d(d)
sage: fibo2_ifs = GIFS.from_two_dimensional_substitution(s)
sage: fibo2_ifs
GIFS defined by 9 maps on Vector space of dimension 2 over
Number Field in rootX with defining polynomial x^2 - x - 1 with
rootX = 1.618033988749895?
REFERENCES:
- JK14
Jolivet, Timo, et Jarkko Kari. « Undecidable Properties of Self-Affine Sets and Multi-Tape Automata ». In Mathematical Foundations of Computer Science 2014, édité par Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, et Zoltán Ésik, 8634:352‑64. Berlin, Heidelberg: Springer Berlin Heidelberg, 2014. https://doi.org/10.1007/978-3-662-44522-8_30.
- BV20
Michael Barnsley, Andrew Vince. Tilings from Graph Directed Iterated Function Systems. Geometriae Dedicata, 9 août 2020. https://doi.org/10.1007/s10711-020-00560-4
- BG13
Michael Baake, Uwe Grimm. Aperiodic order. Vol. 1. Vol. 149. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2013. http://www.ams.org/mathscinet-getitem?mr=3136260.
- BFG19(1,2,3)
Michael Baake, Natalie Priebe Frank, Uwe Grimm. Three variations on a theme by Fibonacci. http://arxiv.org/abs/1910.00988
-
class
slabbe.graph_directed_IFS.
GraphDirectedIteratedFunctionSystem
(module, edges)¶ Bases:
object
INPUT:
module
– the module on which the functions are definededges
– list, list of triples (u,v,f) where f is a function associated to the directed edge (u,v).
EXAMPLES:
The Cantor set:
sage: F = AffineGroup(1, QQ) sage: f1 = F.linear(1/3) sage: f2 = F(1/3, vector([2/3])) sage: f1 x |-> [1/3] x + [0] sage: f2 x |-> [1/3] x + [2/3] sage: from slabbe import GraphDirectedIteratedFunctionSystem as GIFS sage: GIFS(QQ^1, [(0,0,f1),(0,0,f2)]) GIFS defined by 2 maps on Vector space of dimension 1 over Rational Field
-
classmethod
from_inflation_rule
(module, multiplier, displacement_matrix)¶ Return the GIFS defined by a 2-dimensional primitive substitution
We follow the convention used in [BFG19] for the displacement matrix.
INPUT:
module
– module or vector spacemultiplier
– real number, inflation multiplierd
– dict, the displacement matrix, where each key (i,j) is mapped to a list of translations
EXAMPLES:
This examples is taken from [BFG19]:
sage: from slabbe import GraphDirectedIteratedFunctionSystem as GIFS sage: z = polygen(QQ, 'z') sage: K = NumberField(z**2-z-1, 'tau', embedding=RR(1.6)) sage: tau = K.gen() sage: import itertools sage: d = {(i,j):[] for i,j in itertools.product(range(4),repeat=2)} sage: d[(0,3)] = [vector(K, (tau,tau))] sage: d[(1,2)] = d[(1,3)] = [vector(K, (0,tau))] sage: d[(2,1)] = d[(2,3)] = [vector(K, (tau,0))] sage: d[(3,0)] = d[(3,1)] = d[(3,2)] = d[(3,3)] = [vector(K, (0,0))] sage: GIFS.from_inflation_rule(K^2, tau, d) GIFS defined by 9 maps on Vector space of dimension 2 over Number Field in tau with defining polynomial z^2 - z - 1 with tau = 1.618033988749895?
-
classmethod
from_one_dimensional_substitution
(m)¶ Return the GIFS defined by a unidimensional primitive substitution
INPUT:
m
– WordMorphism, primitive substitution
EXAMPLES:
sage: from slabbe import GraphDirectedIteratedFunctionSystem as GIFS sage: m = WordMorphism('a->ab,b->a') sage: g = GIFS.from_one_dimensional_substitution(m) sage: g GIFS defined by 3 maps on Vector space of dimension 1 over Number Field in root with defining polynomial x^2 - x - 1 with root = 1.618033988749895?
-
classmethod
from_two_dimensional_substitution
(s)¶ Return the GIFS defined by a 2-dimensional primitive substitution
The marker point associated to each rectangular tile is assumed to be in the lower left corner.
INPUT:
s
– Substitution2d, primitive substitution
EXAMPLES:
sage: from slabbe import GraphDirectedIteratedFunctionSystem as GIFS sage: from slabbe import Substitution2d sage: d = {0:[[3]], 1:[[3],[2]], 2:[[3,1]], 3:[[3,1],[2,0]]} sage: s = Substitution2d(d) sage: ifs = GIFS.from_two_dimensional_substitution(s) sage: ifs.pp() GIFS defined by 9 maps on Vector space of dimension 2 over Number Field in rootX with defining polynomial x^2 - x - 1 with rootX = 1.618033988749895? edge (0,3): [rootX 0] [0] x |-> [ 0 rootX] x + [0] edge (1,3): [rootX 0] [0] x |-> [ 0 rootX] x + [0] edge (1,2): [rootX 0] [rootX] x |-> [ 0 rootX] x + [ 0] edge (2,3): [rootX 0] [0] x |-> [ 0 rootX] x + [0] edge (2,1): [rootX 0] [ 0] x |-> [ 0 rootX] x + [rootX] edge (3,3): [rootX 0] [0] x |-> [ 0 rootX] x + [0] edge (3,1): [rootX 0] [ 0] x |-> [ 0 rootX] x + [rootX] edge (3,2): [rootX 0] [rootX] x |-> [ 0 rootX] x + [ 0] edge (3,0): [rootX 0] [rootX] x |-> [ 0 rootX] x + [rootX]
-
galois_conjugate
()¶ Return the element-wise Galois conjugate of this GIFS
INPUT:
self
– an Affine GIFS, defined on a ring where elements have a method.galois_conjugate
(e.g., quadratic number field elements)
EXAMPLES:
Fibonacci substitution:
sage: from slabbe import GraphDirectedIteratedFunctionSystem as GIFS sage: m = WordMorphism('a->ab,b->a') sage: s = GIFS.from_one_dimensional_substitution(m) sage: s.galois_conjugate() GIFS defined by 3 maps on Vector space of dimension 1 over Number Field in root with defining polynomial x^2 - x - 1 with root = 1.618033988749895?
Direct Product of 2 Fibonacci:
sage: from slabbe import Substitution2d sage: d = {0:[[3]], 1:[[3],[2]], 2:[[3,1]], 3:[[3,1],[2,0]]} sage: s = Substitution2d(d) sage: ifs = GIFS.from_two_dimensional_substitution(s) sage: ifs.galois_conjugate() GIFS defined by 9 maps on Vector space of dimension 2 over Number Field in rootX with defining polynomial x^2 - x - 1 with rootX = 1.618033988749895?
-
num_vertices
()¶ EXAMPLES:
sage: F = AffineGroup(1, QQ) sage: f1 = F.linear(1/3) sage: f2 = F(1/3, vector([2/3])) sage: from slabbe import GraphDirectedIteratedFunctionSystem as GIFS sage: cantor_ifs = GIFS(QQ^1, [(0,0,f1),(0,0,f2)]) sage: cantor_ifs.num_vertices() 1
-
plot
(S=None, n_iterations=1, projection=None)¶ Return a graphic image of the IFS after few iterations
INPUT:
S
– list or dict, list of list of points or dictionary associating a list of points to each vertex. If a list is used, we assume the vertices are integers 0,1,…,n-1.n_iterations
– integer (default:1
)projection
– matrix (default:None
), projection matrix to 2-dimensional space
OUTPUT:
Graphics object
EXAMPLES:
The Cantor set:
sage: from slabbe import GraphDirectedIteratedFunctionSystem as GIFS sage: F = AffineGroup(1, QQ) sage: f1 = F.linear(1/3) sage: f2 = F(1/3, vector([2/3])) sage: cantor_ifs = GIFS(QQ^1, [(0,0,f1),(0,0,f2)]) sage: G = cantor_ifs.plot(n_iterations=7)
Projection on the vertical y-axis instead:
sage: G = cantor_ifs.plot(n_iterations=7, projection=matrix(2,[0,1]))
The usual Fibonacci chain:
sage: m = WordMorphism('a->ab,b->a') sage: ifs = GIFS.from_one_dimensional_substitution(m) sage: G = ifs.plot(n_iterations=10)
and its contracting IFS:
sage: G = ifs.galois_conjugate().plot(n_iterations=10)
The direct product of two Fibonacci chains:
sage: from slabbe import GraphDirectedIteratedFunctionSystem as GIFS sage: from slabbe import Substitution2d sage: d = {0:[[3]], 1:[[3],[2]], 2:[[3,1]], 3:[[3,1],[2,0]]} sage: s = Substitution2d(d) sage: ifs = GIFS.from_two_dimensional_substitution(s) sage: G = ifs.plot(n_iterations=7)
This inflation rule is related to a contracting IFS whose unique solution is given in formula (4.5) of [BFG19]:
sage: G = ifs.galois_conjugate().plot(n_iterations=7)
-
pp
()¶ Prints a nicer and complete string representation.
EXAMPLES:
sage: from slabbe import GraphDirectedIteratedFunctionSystem as GIFS sage: F = AffineGroup(1, QQ) sage: ifs = f1 = F.linear(1/3) sage: f2 = F(1/3, vector([2/3])) sage: ifs = GIFS(QQ^1, [(0,0,f1),(0,0,f2)]) sage: ifs.pp() GIFS defined by 2 maps on Vector space of dimension 1 over Rational Field edge (0,0): x |-> [1/3] x + [0] edge (0,0): x |-> [1/3] x + [2/3]
-
to_digraph
()¶ EXAMPLES:
sage: from slabbe import GraphDirectedIteratedFunctionSystem as GIFS sage: F = AffineGroup(1, QQ) sage: f1 = F.linear(1/3) sage: f2 = F(1/3, vector([2/3])) sage: cantor_ifs = GIFS(QQ^1, [(0,0,f1),(0,0,f2)]) sage: cantor_ifs.to_digraph() Looped multi-digraph on 1 vertex
-
vertices
()¶ EXAMPLES:
sage: F = AffineGroup(1, QQ) sage: f1 = F.linear(1/3) sage: f2 = F(1/3, vector([2/3])) sage: from slabbe import GraphDirectedIteratedFunctionSystem as GIFS sage: cantor_ifs = GIFS(QQ^1, [(0,0,f1),(0,0,f2)]) sage: cantor_ifs.vertices() [0]
-
slabbe.graph_directed_IFS.
galois_conjugate
(f)¶ Return the element-wise Galois conjugate of an element of an affine group
INPUT:
f
– affine group element
EXAMPLES:
sage: from slabbe.graph_directed_IFS import galois_conjugate sage: z = polygen(QQ, 'z') sage: K = NumberField(z**2-z-1, 'phi', embedding=RR(1.6)) sage: phi = K.gen() sage: F = AffineGroup(2, K) sage: f = F(phi*identity_matrix(2), (phi,0)) sage: galois_conjugate(f) [-phi + 1 0] [-phi + 1] x |-> [ 0 -phi + 1] x + [ 0]