# Graph-directed iterated function system (GIFS)¶

Graph-directed iterated function system (GIFS)

See [JK14] or [BV20] or

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 + 
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 + 
edge (1,0):
x |-> [-root + 1] x + 
edge (0,1):
x |-> [-root + 1] x + 


Direct Product of 2 Fibonacci:

sage: from slabbe import GraphDirectedIteratedFunctionSystem as GIFS
sage: from slabbe import Substitution2d
sage: d = {0:[], 1:[,], 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 defined

• edges – 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 + 
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 space

• multiplier – real number, inflation multiplier

• d – 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:[], 1:[,], 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]     
x |-> [    0 rootX] x + 
edge (1,3):
[rootX     0]     
x |-> [    0 rootX] x + 
edge (1,2):
[rootX     0]     [rootX]
x |-> [    0 rootX] x + [    0]
edge (2,3):
[rootX     0]     
x |-> [    0 rootX] x + 
edge (2,1):
[rootX     0]     [    0]
x |-> [    0 rootX] x + [rootX]
edge (3,3):
[rootX     0]     
x |-> [    0 rootX] x + 
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:[], 1:[,], 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:[], 1:[,], 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 + 
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()


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]