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, 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 substitution

  • inflation – None or (Algebraic) number

  • stone_inflation_shapes – None or dict, from letters to tuple of rectangular dimension of the tilebox associated to each letter. If None, 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 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