# EkEkstar: Geometric substitutions¶

EkEkStar

AUTHORS:

• Milton Minervino, 2017, initial version

• Sébastien Labbé, July 6th 2017: added doctests, package, improve object oriented structure of the classes, multiplicity stored in the patch not in the faces. Fixed the creation of patches (linear time instead of quadratic time). Added a dozen of doctests.

• Sébastien Labbé, March 28th, 2018: projection and plot of k-faces from a projection matrix. Computation of the projection on the contracting and expanding spaces directly from Minkowski embedding.

• Sébastien Labbé, February 16th, 2021: Imported the module into slabbe package

EXAMPLES:

The Tribonacci example:

sage: from slabbe import GeoSub, kPatch, kFace
sage: sub = {1:[1,2], 2:[1,3], 3:[1]}
sage: geosub = GeoSub(sub,2, presuf='prefix', dual=True)
sage: P = kPatch([kFace((0,0,0),(1,2),dual=True),
....:             kFace((0,0,1),(1,3),dual=True),
....:             kFace((0,1,0),(2,1),dual=True),
....:             kFace((0,0,0),(3,1),dual=True)])
sage: Q = geosub(P, 6)
sage: Q
Patch of 32 faces
sage: _ = Q.plot()
sage: Q.projection_matrix()
[  1.00000000000000  -1.41964337760708 -0.771844506346038]
[ 0.000000000000000  0.606290729207199  -1.11514250803994]


Hokaido example:

sage: sub = {1:[1,2], 2:[3], 3:[4], 4:[5], 5:[1]}
sage: geosub = GeoSub(sub, 3, dual=True)
sage: F = kFace((0,0,0,0,0), (1,2,3), dual=True)
sage: P = 1*F
sage: P
Patch: 1[(0, 0, 0, 0, 0), (1, 2, 3)]*
sage: Q = geosub(P, 5)
sage: Q
Patch: 1[(1, 1, 0, 0, 0), (1, 2, 3)]* + -1[(1, 1, 0, 0, 0), (1, 2, 4)]* + 1[(1, 1, 0, 0, 0), (1, 2, 5)]*
sage: _ = Q.plot()
sage: Q.projection_matrix()
[  1.00000000000000  -1.66235897862237  0.784920145499027 0.215079854500973 -0.877438833123346]
[ 0.000000000000000  0.562279512062301  -1.30714127868205 1.30714127868205  -0.744861766619744]

class slabbe.EkEkstar.GeoSub(sigma, k, presuf='prefix', dual=False)

Bases: sage.structure.sage_object.SageObject

INPUT:

• sigma – dict, substitution

• k – integer

• presuf – string (default: "prefix"), "prefix" or "suffix"

• dual – bool (default: False)

EXAMPLES:

sage: from slabbe import GeoSub
sage: sub = {1:[1,2], 2:[1,3], 3:[1]}
sage: E = GeoSub(sub, 2)
sage: E
E_2(1->12, 2->13, 3->1)

base_iter()

EXAMPLES:

sage: from slabbe import GeoSub
sage: sub = {1:[1,2], 2:[1,3], 3:[1]}
sage: E = GeoSub(sub,2)
sage: E.base_iter()
{(1, 2): [[(0, 0, 0), (1,)],
[(1, 0, 0), (2,)],
[(0, 0, 0), (1, 1)],
[(1, 0, 0), (1, 3)],
[(1, 0, 0), (2, 1)],
[(2, 0, 0), (2, 3)]],
(1, 3): [[(0, 0, 0), (1,)],
[(1, 0, 0), (2,)],
[(0, 0, 0), (1, 1)],
[(1, 0, 0), (2, 1)]],
(2, 3): [[(0, 0, 0), (1,)],
[(1, 0, 0), (3,)],
[(0, 0, 0), (1, 1)],
[(1, 0, 0), (3, 1)]]}

complex_embeddings()

EXAMPLES:

sage: from slabbe import GeoSub
sage: sub = {1:[1,2], 2:[1,3], 3:[1]}
sage: E = GeoSub(sub,2)
sage: E.complex_embeddings()
[-0.419643377607081 - 0.606290729207199*I,
-0.419643377607081 + 0.606290729207199*I,
1.83928675521416]

contracting_eigenvalues_indices()

EXAMPLES:

sage: from slabbe import GeoSub
sage: sub = {1:[1,2], 2:[1,3], 3:[1]}
sage: E = GeoSub(sub,2)
sage: E.contracting_eigenvalues_indices()
[0, 1]

dilating_eigenvalues_indices()

EXAMPLES:

sage: from slabbe import GeoSub
sage: sub = {1:[1,2], 2:[1,3], 3:[1]}
sage: E = GeoSub(sub,2)
sage: E.dilating_eigenvalues_indices()
[2]

dominant_left_eigenvector()

EXAMPLES:

sage: from slabbe import GeoSub
sage: sub = {1:[1,2], 2:[1,3], 3:[1]}
sage: E = GeoSub(sub,2)
sage: E.dominant_left_eigenvector()
(1, b - 1, b^2 - b - 1)

dominant_right_eigenvector()

EXAMPLES:

sage: from slabbe import GeoSub
sage: sub = {1:[1,2], 2:[1,3], 3:[1]}
sage: E = GeoSub(sub,2)
sage: E.dominant_right_eigenvector()
(1, b^2 - b - 1, -b^2 + 2*b)

field()

EXAMPLES:

sage: from slabbe import GeoSub
sage: sub = {1:[1,2], 2:[1,3], 3:[1]}
sage: E = GeoSub(sub,2)
sage: E.field()
Number Field in b with defining polynomial x^3 - x^2 - x - 1


When the characteristic polynomial is reducible (Hokaido example):

sage: sub = {1:[1,2], 2:[3], 3:[4], 4:[5], 5:[1]}
sage: geosub = GeoSub(sub, 3, dual=True)
sage: geosub.field()
Number Field in b with defining polynomial x^3 - x - 1

gen()

EXAMPLES:

sage: from slabbe import GeoSub
sage: sub = {1:[1,2], 2:[1,3], 3:[1]}
sage: E = GeoSub(sub,2)
sage: E.gen()
b^2 - b - 1

is_dual()
matrix()

EXAMPLES:

sage: from slabbe import GeoSub
sage: sub = {1:[1,2], 2:[1,3], 3:[1]}
sage: E = GeoSub(sub,2)
sage: E.matrix()
[1 1 1]
[1 0 0]
[0 1 0]

minkowski_embedding_with_left_eigenvector()

EXAMPLES:

sage: from slabbe import GeoSub
sage: sub = {1:[1,2], 2:[1,3], 3:[1]}
sage: E = GeoSub(sub,2)
sage: E.minkowski_embedding_with_left_eigenvector()
[ -1.00000000000000 -0.839286755214161 -0.543689012692076]
[ -1.00000000000000   1.41964337760708  0.771844506346038]
[ 0.000000000000000 -0.606290729207199   1.11514250803994]

sage: E = GeoSub(sub, 2, dual=True)
sage: E.minkowski_embedding_with_left_eigenvector()
[  1.00000000000000  0.839286755214161  0.543689012692076]
[  1.00000000000000  -1.41964337760708 -0.771844506346038]
[ 0.000000000000000  0.606290729207199  -1.11514250803994]

prefix_suffix_automaton()

EXAMPLES:

sage: from slabbe import GeoSub
sage: sub = {1:[1,2], 2:[1,3], 3:[1]}
sage: E = GeoSub(sub,2)
sage: E.prefix_suffix_automaton()
{1: [(1, []), (2, [1])], 2: [(1, []), (3, [1])], 3: [(1, [])]}

projection_matrix(prec=None)

Return the Minkowski projection to the contracting (or expanding) space.

INPUT:

• prec – integer (default:None), the precision. The computations will use RealField(prec) or RDF if prec is None or the field of algebraic numbers QQbar (or it subfield AA of algebraic reals) if prec is infinity.

EXAMPLES:

sage: from slabbe import GeoSub
sage: sub = {1:[1,2], 2:[1,3], 3:[1]}
sage: GeoSub(sub, 2).projection_matrix()      # tol
[ -1.00000000000000 -0.839286755214161 -0.543689012692076]
sage: GeoSub(sub, 2, dual=True).projection_matrix()
[  1.00000000000000  -1.41964337760708 -0.771844506346038]
[ 0.000000000000000  0.606290729207199  -1.11514250803994]


With algebraic coefficients:

sage: GeoSub(sub, 2, dual=True).projection_matrix(prec=oo)
[                   1  -1.419643377607081?  -0.7718445063460381?]
[                   0  0.6062907292071993?   -1.115142508039938?]

slabbe.EkEkstar.abelian(L, alphabet)

EXAMPLES:

sage: from slabbe.EkEkstar import abelian
sage: abelian([1,0,1,2,3,1,1,2,2], [0,1,2,3])
(1, 4, 3, 1)

class slabbe.EkEkstar.kFace(v, t, dual=False, color=None)

Bases: sage.structure.sage_object.SageObject

INPUT:

• v – vector

• t – tuple, type

• dual – bool (default:False)

• color – string (default:None)

EXAMPLES:

Face based at (0,0,0) of type (1,2):

sage: from slabbe import kFace
sage: F = kFace((0,0,0),(1,2))
sage: F
[(0, 0, 0), (1, 2)]


Face based at (0,0,0) of type (3,1):

sage: kFace((0,0,0),(3,1))
[(0, 0, 0), (3, 1)]


Dual face based at (0,0,0,0) of type (1):

sage: kFace((0,0,0,0),(1), dual=True)
[(0, 0, 0, 0), (1,)]*


Operations:

sage: F = kFace((0,0,0),(1,2))
sage: F
[(0, 0, 0), (1, 2)]
sage: -2 * F.dual()
Patch: -2[(0, 0, 0), (1, 2)]*


Color of a face:

sage: F = kFace((0,0,0),(1,2))
sage: F.color()
RGB color (1.0, 0.0, 0.0)

sage: F = kFace((0,0,0),(1,2),color='green')
sage: F.color()
RGB color (0.0, 0.5019607843137255, 0.0)

color()
contour()

Return the face contour.

If this is an edge, it returns the two end points. If this is a losange, it returns the four corners.

OUTPUT:

• list of vectors in the Z-module

EXAMPLES:

sage: from slabbe import kFace
sage: kFace((0,0,0),(1,3)).contour()
[(0, 0, 0), (1, 0, 0), (1, 0, 1), (0, 0, 1)]
sage: kFace((0,0,0),(2,)).contour()
[(0, 0, 0), (0, 1, 0)]
sage: kFace((0,0,0),(2,), dual=True).contour()
[(0, 0, 0), (1, 0, 0), (1, 0, 1), (0, 0, 1)]
sage: kFace((0,0,0),(2,3), dual=True).contour()
[(0, 0, 0), (1, 0, 0)]


A 2-dimensional dual face in $$\RR^5$$:

sage: F = kFace((0,0,0,0,0), (1,2,3), dual=True)
sage: F
[(0, 0, 0, 0, 0), (1, 2, 3)]*
sage: F.contour()
[(0, 0, 0, 0, 0), (0, 0, 0, 1, 0), (0, 0, 0, 1, 1), (0, 0, 0, 0, 1)]

contour_projection(M)

Return the projection of the face contour.

INPUT:

• M – projection matrix

EXAMPLES:

sage: from slabbe import kFace, GeoSub
sage: sub = {1:[1,2], 2:[1,3], 3:[1]}
sage: geosub = GeoSub(sub,2, dual=True)
sage: M = geosub.projection_matrix()


This illustrates the case with faces of dimension 1 with a field with one complex embedding:

sage: kFace((10,21,33), (1,2), dual=True).contour_projection(M)
[(-45.2833796391679, -24.0675974519667),
(-46.0552241455140, -25.1827399600067)]


This illustrates the case with faces of dimension 2 with a field with one complex embedding:

sage: kFace((10,21,33), (1,), dual=True).contour_projection(M)
[(-45.2833796391679, -24.0675974519667),
(-46.7030230167750, -23.4613067227595),
(-47.4748675231211, -24.5764492307995),
(-46.0552241455140, -25.1827399600067)]


Brun substitutions [123,132,213,231] gives a incidence matrix with totally real eigenvalues:

sage: from slabbe.mult_cont_frac import Brun
sage: algo = Brun()
sage: S = algo.substitutions()
sage: sub = prod([S[a] for a in [123,132,213,231]])
sage: sub
WordMorphism: 1->1323, 2->23, 3->3231323


This illustrates the case with faces of dimension 1 with totally real field projected in a contracting space of dimension 2:

sage: sub = {1: [1,3,2,3], 2: [2,3], 3: [3,2,3,1,3,2,3]}
sage: geosub = GeoSub(sub, 2, dual=True)
sage: M = geosub.projection_matrix()
sage: kFace((10,21,33), (1,2), dual=True).contour_projection(M)
[(6.690365529225190287265975075034, -1.500190036950057598982635871389),
(5.443385925507723226215965307025, -1.055148169037428790404830742396)]


This illustrates the case with faces of dimension 1 with totally real field projected in a contracting space of dimension 1:

sage: sub = {1:[1,2,3,3,3,3], 2:[1,3], 3:[1]}
sage: geosub = GeoSub(sub,2, dual=True)
sage: M = geosub.projection_matrix()
sage: kFace((7,-3,4),(1,2), dual=True).contour_projection(M)
[(-65.28494960003319740280849294991),
(-70.02977567771512068843031399068)]


This illustrates the case with faces of dimension 2 with a field with one complex embedding:

sage: sub = {1:[1,1,4],
....:   2:[1,2,4,1,2,4,1,3,4],
....:   3:[1,2,4,1,3,4,],
....:   4:[1,2,4,1,2,4,1,3,4,1,4]}
sage: geosub = GeoSub(sub, 2)
sage: M = geosub.projection_matrix()
sage: kFace((10,21,33,-7), (1,2)).contour_projection(M)
[(21.18350167207436655863368355998, -150.7254323268995855552615832997),
(20.18350167207436655863368355998, -151.7254323268995855552615832997),
(21.08776078027425227765222077178, -155.8643948778810657648963968540),
(22.08776078027425227765222077178, -154.8643948778810657648963968540)]


This illustrates the case with faces of dimension 2 in a totally real field:

sage: sub = {1:[1,2,4], 2:[1,2,2,4], 3:[1,2,4,3,3,4], 4:[1,2,4,3,4]}
sage: geosub = GeoSub(sub, 2)
sage: M = geosub.projection_matrix()
sage: kFace((10,21,33,-7), (1,2)).contour_projection(M)
[(32.57858448022453517201706283181, -112.0669861296918881523709190477),
(31.57858448022453517201706283181, -113.0669861296918881523709190477),
(29.38505739489348123345652443465, -114.3619490289834872642844850711),
(30.38505739489348123345652443465, -113.3619490289834872642844850711)]


The next example illustrates the case where the dilating space is of dimension one (Pisot case) and the faces are of dimension 2 in R^3 so the faces are projected on a one-dimensional space:

sage: sub = {1: [1,3,2,3], 2: [2,3], 3: [3,2,3,1,3,2,3]}
sage: geosub = GeoSub(sub, 2)
sage: M = geosub.projection_matrix()
sage: kFace((10,13,27), (1,2)).contour_projection(M)
[(-64.43786314959480732826099193032),
(-65.43786314959480732826099193032),
(-65.88290501750743613683879705932),
(-64.88290501750743613683879705932)]

dimension()

Return the dimension of the ambiant space.

EXAMPLES:

sage: from slabbe import kFace
sage: F = kFace((0,0,0),(1,2))
sage: F.dimension()
3

dual()

Return the dual face.

EXAMPLES:

sage: from slabbe import kFace
sage: kFace((0,0,0),(1,3))
[(0, 0, 0), (1, 3)]
sage: kFace((0,0,0),(1,3)).dual()
[(0, 0, 0), (1, 3)]*
sage: kFace((0,0,0),(1,3)).dual().dual()
[(0, 0, 0), (1, 3)]

face_dimension()

Return the dimension of the face.

EXAMPLES:

sage: from slabbe import kFace
sage: F = kFace((0,0,0),(1,2))
sage: F.face_dimension()
2

sage: F = kFace((0,0,0), (1,2), dual=True)
sage: F.face_dimension()
1

is_dual()
plot(M, color=None)

INPUT:

• M – projection matrix

• color – string or None

EXAMPLES:

sage: from slabbe import kFace, GeoSub
sage: sub = {1:[1,2], 2:[1,3], 3:[1]}
sage: geosub = GeoSub(sub,2, dual=True)
sage: M = geosub.projection_matrix()
sage: _ = kFace((10,21,33), (1,2), dual=True).plot(M)

sign()

EXAMPLES:

sage: from slabbe import kFace
sage: kFace((0,0,0,0,0),(1,2,3,4,5)).sign()
1
sage: kFace((0,0,0,0,0),(1,2,3,4,4)).sign()
0
sage: kFace((0,0,0,0,0),(1,2,3,5,4)).sign()
-1

sorted_type()
type()
vector()
class slabbe.EkEkstar.kPatch(faces)

Bases: sage.structure.sage_object.SageObject

EXAMPLES:

sage: from slabbe import kPatch, kFace
sage: P = kPatch([kFace((0,0,0),(1,2),dual=True),
....:             kFace((0,0,1),(1,3),dual=True),
....:             kFace((0,1,0),(2,1),dual=True),
....:             kFace((0,0,0),(3,1),dual=True)])
sage: P
Patch: 1[(0, 0, 0), (1, 2)]* + -1[(0, 0, 0), (1, 3)]* + 1[(0, 0, 1), (1, 3)]* + -1[(0, 1, 0), (1, 2)]*

dimension()

EXAMPLES:

sage: from slabbe import kFace, kPatch
sage: P = kPatch([kFace((0,0,0),(1,2),dual=True),
....:             kFace((0,0,1),(1,3),dual=True),
....:             kFace((0,1,0),(2,1),dual=True),
....:             kFace((0,0,0),(3,1),dual=True)])
sage: P.dimension()
3

dual()

EXAMPLES:

sage: from slabbe import kPatch, kFace
sage: P = kPatch([kFace((0,1,0),(1,2)), kFace((0,0,0),(1,3))])
sage: P
Patch: 1[(0, 0, 0), (1, 3)] + 1[(0, 1, 0), (1, 2)]
sage: P.dual()
Patch: 1[(0, 0, 0), (1, 3)]* + 1[(0, 1, 0), (1, 2)]*

plot(M=None, color=None)

INPUT:

• M – projection matrix or None. If None, it uses the default projection matrix.

• color – string or None

EXAMPLES:

sage: from slabbe import kFace, kPatch, GeoSub
sage: sub = {1:[1,2], 2:[1,3], 3:[1]}
sage: geosub = GeoSub(sub,2, dual=True)
sage: P = kPatch([kFace((0,0,0),(1,2),dual=True),
....:             kFace((0,0,1),(1,3),dual=True),
....:             kFace((0,1,0),(2,1),dual=True),
....:             kFace((0,0,0),(3,1),dual=True)])
sage: M = geosub.projection_matrix()
sage: _ = P.plot(M)


A patch created from the application of a geometric substitution remembers the canonical projection matrix of the geo. subst. as its default projection. So plot may be called with no argument:

sage: Q = geosub(P)
sage: _ = Q.plot()


The default projection matrix in this case is:

sage: Q.projection_matrix()
[  1.00000000000000  -1.41964337760708 -0.771844506346038]
[ 0.000000000000000  0.606290729207199  -1.11514250803994]

projection_matrix(M=None)

Set or get the default projection matrix

INPUT:

• M – projection matrix or None

OUTPUT:

• None or a matrix

EXAMPLES:

sage: from slabbe import kFace, kPatch
sage: P = kPatch([kFace((0,0,0),(1,2),dual=True),
....:             kFace((0,0,0),(3,1),dual=True)])
sage: P.projection_matrix() is None
True
sage: L = [-0.866025403784439, 0.866025403784439, 0.000000000000000,
....:      -0.500000000000000, -0.500000000000000, 1.00000000000000]
sage: M = matrix(2, L)
sage: P.projection_matrix(M)
sage: P.projection_matrix()
[-0.866025403784439  0.866025403784439  0.000000000000000]
[-0.500000000000000 -0.500000000000000   1.00000000000000]

union(other)

INPUT:

• other – a face, a patch or a list of faces

EXAMPLES:

sage: from slabbe import kFace, kPatch
sage: P = kPatch([kFace((0,0,0),(1,2),dual=True),
....:             kFace((0,0,1),(1,3),dual=True)])
sage: f = kFace((0,1,0),(2,1),dual=True)
sage: g = kFace((0,0,0),(3,1),dual=True)


A patch union with a face:

sage: P.union(f)
Patch: 1[(0, 0, 0), (1, 2)]* + 1[(0, 0, 1), (1, 3)]* + -1[(0, 1, 0), (1, 2)]*


A patch union with a patch:

sage: P.union(P)
Patch: 2[(0, 0, 0), (1, 2)]* + 2[(0, 0, 1), (1, 3)]*


A patch union with a list of faces:

sage: P.union([f,g])
Patch: 1[(0, 0, 0), (1, 2)]* + -1[(0, 0, 0), (1, 3)]* + 1[(0, 0, 1), (1, 3)]* + -1[(0, 1, 0), (1, 2)]*

slabbe.EkEkstar.ps_automaton(sub, presuf)

Return the prefix or suffix automaton

(related to the prefix-suffix automaton).

INPUT:

• sub – dict, 1 dimensional substitution

• presuf – string, "prefix" or "suffix"

OUTPUT:

dict

EXAMPLES:

sage: from slabbe.EkEkstar import ps_automaton
sage: m = {1:[2,1], 2:[2,1,1]}
sage: ps_automaton(m, "prefix")
{1: [(2, []), (1, [2])], 2: [(2, []), (1, [2]), (1, [2, 1])]}
sage: ps_automaton(m, 'suffix')
{1: [(2, [1]), (1, [])], 2: [(2, [1, 1]), (1, [1]), (1, [])]}

slabbe.EkEkstar.ps_automaton_inverted(sub, presuf)

Return the prefix or suffix automaton with inverted edges.

(related to the prefix-suffix automaton).

INPUT:

• sub – dict, 1 dimensional substitution

• presuf – string, "prefix" or "suffix"

OUTPUT:

dict

EXAMPLES:

sage: from slabbe.EkEkstar import ps_automaton_inverted
sage: m = {2:[2,1,1], 1:[2,1]}
sage: ps_automaton_inverted(m, "prefix")
{1: [(1, [2]), (2, [2]), (2, [2, 1])], 2: [(1, []), (2, [])]}
sage: ps_automaton_inverted(m, 'suffix')
{1: [(1, []), (2, []), (2, [1])], 2: [(1, [1]), (2, [1, 1])]}