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 y^2 - y - 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 y^2 - y - 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 a with defining polynomial y^2 - y - 1 with
a = 1.618033988749895?
REFERENCES:
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.
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
Michael Baake, Natalie Priebe Frank, Uwe Grimm. Three variations on a theme by Fibonacci. arXiv 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 y^2 - y - 1 with root = 1.618033988749895?
- classmethod from_two_dimensional_substitution(s, inflation=None, stone_inflation_shapes=None)¶
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 substitutioninflation
– None or (Algebraic) numberstone_inflation_shapes
– None or dict, from letters to tuple of rectangular dimension of the tilebox associated to each letter. IfNone
, it is computed automaticaly from left eigenvectors of horizontal and vertical 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 a with defining polynomial y^2 - y - 1 with a = 1.618033988749895? edge (0,3): [a 0] [0] x |-> [0 a] x + [0] edge (1,3): [a 0] [0] x |-> [0 a] x + [0] edge (1,2): [a 0] [a] x |-> [0 a] x + [0] edge (2,3): [a 0] [0] x |-> [0 a] x + [0] edge (2,1): [a 0] [0] x |-> [0 a] x + [a] edge (3,3): [a 0] [0] x |-> [0 a] x + [0] edge (3,1): [a 0] [0] x |-> [0 a] x + [a] edge (3,2): [a 0] [a] x |-> [0 a] x + [0] edge (3,0): [a 0] [a] x |-> [0 a] x + [a]
We can provide the rectangular shapes associated to each letter (useful when they are not properly defined automatically):
sage: z = polygen(QQ, 'z') sage: K.<phi> = NumberField(z**2-z-1, 'phi', embedding=RR(1.6)) sage: shapes = {0:(1,1), 1:(phi,1), 2:(1,phi), 3:(phi,phi)} sage: GIFS.from_two_dimensional_substitution(s, inflation=phi, stone_inflation_shapes=shapes) GIFS defined by 9 maps on Vector space of dimension 2 over Number Field in phi with defining polynomial z^2 - z - 1 with phi = 1.618033988749895?
- 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 y^2 - y - 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 a with defining polynomial y^2 - y - 1 with a = 1.618033988749895?
- inverse()¶
Return the inverse of this GIFS
EXAMPLES:
Fibonacci substitution:
sage: from slabbe import GraphDirectedIteratedFunctionSystem as GIFS sage: m = WordMorphism('a->ab,b->a') sage: g = GIFS.from_one_dimensional_substitution(m) sage: g.inverse() GIFS defined by 3 maps on Vector space of dimension 1 over Number Field in root with defining polynomial y^2 - y - 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.inverse() GIFS defined by 9 maps on Vector space of dimension 2 over Number Field in a with defining polynomial y^2 - y - 1 with a = 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
- path_to_map(path)¶
Return the map obtained by the composition of the applications along the
path
.INPUT:
path
- a path represented as a list of integers
- periodic_point(cycle)¶
Return the periodic point associated to
cycle
.The periodic point associated to a given cycle in the graph is the attractor of that cycle.
INPUT:
cycle
- a cycle in the graph represented as a list of integers
EXAMPLES:
We can realize the interval \([0,1]\) as an IFS for which the cycle corresponds to the ternary expansion:
sage: from slabbe import GraphDirectedIteratedFunctionSystem as GIFS sage: F = AffineGroup(1, QQ) sage: f0 = F(1/3, vector([0/3])) sage: f1 = F(1/3, vector([1/3])) sage: f2 = F(1/3, vector([2/3])) sage: cantor_IFS = GIFS(QQ^1, [(0,0,f0), (0,0,f1), (0,0,f2)]) sage: cantor_IFS.periodic_point([0]) (0) sage: cantor_IFS.periodic_point([1]) (1/2) sage: cantor_IFS.periodic_point([2]) (1) sage: cantor_IFS.periodic_point([0,1,0,2]) (57/80) sage: (57./80).str(base=3) '0.20102010201020102010201020102010202' sage: cantor_IFS.periodic_point([2,1,2,2]) (77/80) sage: (77./80).str(base=3) '0.22122212221222122212221222122220000'
- periodic_points(start, max_length)¶
EXAMPLES:
sage: from slabbe import GraphDirectedIteratedFunctionSystem as GIFS sage: m = WordMorphism('a->ab,b->ac,c->a') sage: tribo = GIFS.from_one_dimensional_substitution(m) sage: for c, v in tribo.periodic_points('a', 5): ....: print(c, v) sage: from slabbe import GraphDirectedIteratedFunctionSystem as GIFS sage: from slabbe import Substitution2d sage: d = {0:[[3]], ....: 1:[[4],[2]], ....: 2:[[3,1]], ....: 3:[[4,1],[2,0]], ....: 4:[[3,1],[2,0]]} sage: s = Substitution2d(d) sage: ifs = GIFS.from_two_dimensional_substitution(s) sage: P3 = point2d([p for _,p in ifs.periodic_points(3, 5)], color='blue') sage: P4 = point2d([p for _,p in ifs.periodic_points(4, 5)], color='red') sage: P3 + P4 Graphics object consisting of 2 graphics primitives
- plot(S=None, n_iterations=1, projection=None, vertices=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 spacevertices
– list (default:None
), list of vertices to plot
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)
Draw only few vertices:
sage: G = ifs.plot(n_iterations=7, vertices=[0,3])
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
- to_line_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_line_digraph() Looped digraph on 2 vertices
- 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] sage: f = F(identity_matrix(2), (phi,0)) sage: galois_conjugate(f) [1 0] [-phi + 1] x |-> [0 1] x + [ 0]
It is not always defined:
sage: F = AffineGroup(2, AA) sage: entries = [1/2*sqrt(5) + 1/2, 0, 0, 0, sqrt(2) + 1, 0, 0, 0, 1] sage: M = matrix(3, entries) sage: f = F(M) sage: galois_conjugate(f) Traceback (most recent call last): ... ValueError: can't take the galois conjugate of value 1.618033988749895? with parent Algebraic Real Field