# 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 + [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:

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. Arxiv 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 + [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 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 y^2 - y - 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 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]

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 space

• vertices – 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