Fractals/Mathematics/group

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Here one can find examples of relation between fractals and groups.[1]

Introduction[edit | edit source]

"Group theory is very useful in that it finds commonalities among disparate things through the power of abstraction."[2]

There are important connections between the algebraic structure of self-similar groups and the dynamical properties of the polynomials .

Group theory :

  • geometric
  • combinatorial
  • Computational

Definitions[edit | edit source]

Alphabet[edit | edit source]

Alphabet it is a finite set of symbols x :

Automaton[edit | edit source]

Automaton is the basic abstract mathematical model of sequential machine. Different types of automata :

  • recognition automata,
  • Turing machines
  • Moore machines
  • Mealy machines,
  • cellular automata
  • pushdown automata

Automaton has two visual presentations:

  • a flow table, which describes the transitions to the next states and the outputs,
  • a state diagram.

Class[edit | edit source]

equivalence class of an element a in the set X is the subset of all elements x of the set X which are equivalent to a

Expansion[edit | edit source]

p-adic digit a natural number between 0 and p − 1 (inclusive).

A p-adic integer is a sequence of p-adic digits :

n-adic expansion of number [3]

binary integer or dyadic integer or 2-adic integer :

where a is an element of binary alphabet X ={0,1} = (0, .. ,2-1)

Graph[edit | edit source]

The Schreier graphs

Moore diagram of the automaton ( or the state diagram for a Moore machine) it is a directed labeled graph with :

  • the vertices ( nodes) identified with the states of automaton / generators of the fundamental group
  • the edges (lines with arrows) show the state transition,
  • labels : (input,output) are a directed pair of elements in X

Group[edit | edit source]

"A group is a collection of objects that obey a strict set of rules when acted upon by an operation."[4]

A group is the algebraic structure :

, where :

  • is a non-empty set
  • denotes a binary operation called the group operation:

which must obey the following rules (or axioms) :

  • Closure,
  • Associativity
  • Identity
  • Inverse
  • Commutativity[5]

Identity : " the group must have an element that serves as the Identity. The characteristic feature of the Identity is that when it is combined with any other member under the group operation, it leaves that member unchanged." [6]

Inverse : " each member or element of the group must have an inverse. When a member is combined with its inverse under the group operation, the result is the Identity "[7] Closure : "This means that whenever two group members are combined under the group operation, the result is another member of the group"[8]

Associativity : "if we take a list of three or more group members and combine them two at a time, it doesn’t matter which end of the list we start with"[9]

Automaton group = Group generated by automaton

FR = Functionally Recursive Group

IMG = Iterated Monodromy Group[edit | edit source]

IMG[10][11]

The iterated monodromy group acts by automorphism on the rooted tree of preimages

where a vertex is connected by an edge with .


Self-similar group[edit | edit source]

Machine[edit | edit source]

Finite State Machines[12]

  • Mealy machine[13]
  • Moore machine

Polynomial[edit | edit source]

postcritically finite polynomial : the orbit of the critical point is finite. It is when critical point is periodic or preperiodic.[14]

Relation[edit | edit source]

Equivalence relation ~ over/on the set X

  • it is a binary relation relation on X which is reflexive, symmetric, and transitive
  • it induces partition P of a set X[15] into several disjoint subsets, called equivalence classes

Sequence[edit | edit source]

ks = kneading sequence(s)

Word[edit | edit source]

Word w over alphabet X is any sequence of symbols from alphabet X. Word can be :

  • infinite
  • finite
  • empty = the word of length zero :

denotes word beginning with

Examples[edit | edit source]

"The iterated monodromy groups of quadratic rational maps with size of postcritical set at most 3, arranged in a table.

The algebraic structure of most of them is not yet well understood." [16]

f(z) standard actions nucleus machine group comment
The adding machine Binary adding group
Basilica group
conjugate to the Chebyshev polynomial T2
[17] the Hanoi Towers group
the Sierpinski gasket
Thompson-Like Group[18] intermediate growth

Where :

  • is a permutation

Software[edit | edit source]


Group Explorer[edit | edit source]

Group Explorer is mathematical visualization software for the abstract algebra classroom.[19]

GAP[edit | edit source]

GAP[20] is a CAS software.[21] To run :

/usr/share/gap/bin/gap.sh

If the system failed to load packages install libraries, packages and compile them ( nq, pargap, fr). Run test :

 Read( Filename( DirectoriesLibrary( "tst" ), "testinstall.g" ) );

Load package fr by Laurent Bartholdi [22]

LoadPackage("fr");

Run fr test :

Read( Filename( DirectoriesLibrary( "pkg/fr/tst" ), "testall.g" ) );

GAP and fr package can use external programs like Mandel, ImageMagic, graphviz or rsvg-view to draw and display images.

Draw[edit | edit source]

Draw[23]

 Draw(NucleusMachine(BasilicaGroup));
  • creates graph description of the m (Mealy machine or element m ). It is converted to Postscript using the program dot from the graphviz package[24]
  • displays image in a separate X window using the command lin program display ( from ImageMagic) or rsvg-view.[25] This works on UNIX systems.

One can right click on image to see local menu of display program.

If a second argument of Draw function ( filename) is present, the graph is saved, in dot format, under that filename :

Draw(NucleusMachine(BasilicaGroup),"a.dot");

Saves output to a.dot file. Dot file is a text file describing graph in dot language.

digraph MealyMachine {
a [shape=circle]
b [shape=circle]
c [shape=circle]
d [shape=circle]
e [shape=circle]
f [shape=circle]
g [shape=circle]
 a -> a [label="1/1",color=red];
 a -> a [label="2/2",color=blue];
 b -> a [label="1/1",color=red];
 b -> d [label="2/2",color=blue];
 c -> a [label="1/1",color=red];
 c -> e [label="2/2",color=blue];
 d -> a [label="1/2",color=red];
 d -> b [label="2/1",color=blue];
 e -> c [label="1/2",color=red];
 e -> a [label="2/1",color=blue];
 f -> a [label="1/2",color=red];
 f -> g [label="2/1",color=blue];
 g -> f [label="1/2",color=red];
 g -> a [label="2/1",color=blue];
}
This a.dot file can be converted to other formats using command line program dot. For example in ps file :

dot -Tps a.dot -o a.ps

or png file :

dot -Tpng a.dot -o a.png

or svg :

dot -Tsvg a.dot -o a.svg

External angle[edit | edit source]

Function from FR package :

ExternalAngle(machine)

Returns: The external angle identifying machine .

In case machine is the IMG machine of a unicritical polynomial, this function computes the external angle landing at the critical value.

gap> z := Indeterminate(COMPLEX_FIELD,"z");
z
gap> r := P1MapRational(z^2-1); #  Basilica Julia set
<P1 mapping of degree 2>
gap> m:=IMGMachine(r);
<FR machine with alphabet [ 1, 2 ] and adder FRElement(...,f3) on Group( [ f1, f2, f3 ] )/[ f2*f1*f3 ]>
gap> ExternalAngle(m); 
{2/3}
Elements(last); # More precisely, it computes the equivalence class of that external angle under ExternalAnglesRelation
[ 1/3, 2/3 ]

Another example :

gap> m:= PolynomialIMGMachine(2,[1/7]); # the machine descibing the rabbit : degree=2, 
gap> ExternalAngle(m); 
{2/7}
gap> Elements(last);
[ 1/7, 2/7 ]

Machine[edit | edit source]

PolynomialIMGMachine[edit | edit source]

PolynomialIMGMachine(d, per[, pre[, formal]])

This function creates a IMG machine that describes a topological polynomial. The polynomial is described symbolically in the language of external angles.

d is the degree of the polynomial.

per is the list of angles

pre is the list of preangles.

angles are rational numbers, considered modulo 1. Each entry in per or pre is either a rational (interpreted as an angle), or a list of angles [a1 , . . . , ai ] such that da1 = . . . = dai . The angles in per are angles landing at the root of a Fatou component, and the angles in pre land at the other points of Julia set.

gap> m:=PolynomialIMGMachine(2,[1/3],[]); # the Basilica
<FR machine with alphabet [ 1, 2 ] and adder FRElement(...,f3) on Group( [ f1, f2, f3 ] )/[ f3*f2*f1 ]>
gap> Display(m);
 G  |      1         2   
----+---------+---------+
 f1 | f1^-1,2   f2*f1,1  
 f2 |    f1,1    <id>,2  
 f3 |    f3,2    <id>,1  
----+---------+---------+
Adding element: FRElement(...,f3)
Relator: f3*f2*f1
gap> Display(PolynomialIMGMachine(2,[],[1/6])); # z^2+I
 G  |      1            2
----+---------------+---------+
 f1 | f1^-1*f2^-1,2   f2*f1,1
 f2 |          f1,1   f3,2
 f3 |          f2,1   <id>,2
 f4 |          f4,2   <id>,1
----+---------------+---------+
Adding element: FRElement(...,f4)
Relator: f4*f3*f2*f1

PostCriticalMachine[edit | edit source]

PostCriticalMachine(f)

Returns: The Mealy machine of f ’s post-critical orbit. This function constructs a Mealy machine P on the alphabet [1], which describes the post-critical set of f .

gap> z := Indeterminate(Rationals,"z");;
gap> m := PostCriticalMachine(z^2);
<Mealy machine on alphabet [ 1 ] with 2 states>
gap> Display(m);
   | 1 
---+-----+
 a | a,1
 b | b,1
---+-----+
gap> Correspondence(m);
[ 0, infinity ]

It is in fact an oriented graph with constant out-degree 1.

Draw(m);
gap> m := PostCriticalMachine(z^2-1);; Display(m); Correspondence(m);
   | 1
---+-----+
 a | c,1
 b | b,1
 c | a,1
---+-----+
[ -1, infinity, 0 ]

Kneading Sequence[edit | edit source]

KneadingSequence(angle)

"This function converts a rational angle to a kneading sequence,[26] to describe a quadratic polynomial.[27]" ( from fr doc )

KneadingSequence(1/7);

gives :

[ 1, 1 ]

"If angle is in [1/7, 2/7] and the option marked is set, the kneading sequence is decorated with markings in A,B,C." ( from fr doc )

KneadingSequence(1/5:marked);

gives :

[ "A1", "B1", "B0" ]

Rays of root points[edit | edit source]

ExternalAnglesRelation(degree, n)

" This function returns ... all pairs of external angles that land at a common point of period up to n under angle multiplication by by degree ." ( from fr doc) In other words it gives angles in turns of external rays landing on root points of period n hyperbolic components of Mandelbrot set.[28]

For complex quadratic polynomials ( degree = 2) and period 3 :

ExternalAnglesRelation(2,3);
<equivalence relation on Rationals >

It needs one more command :

EquivalenceRelationPartition(last);

and gives :

[ [ 1/7, 2/7 ], [ 1/3, 2/3 ], [ 3/7, 4/7 ], [ 5/7, 6/7 ] ]

This list has 4 elements :

  • 3 pairs of period 3 angles i/7
  • 1 pair of period 2 angles i/3

Internal Adress[edit | edit source]

"This function returns internal addresses for all periodic points of period up to n under angle doubling. These internal addresses describe the prominent hyperbolic components along the path from the landing point to the main cardioid in the Mandelbrot set." (from fr doc )

Compare it with angled internall adresses [29]

Note that angle is a fraction with denominator ( odd number ) :

where n is period and d denominator

Period 2[edit | edit source]

Basilica Julia set for with external rays 1/3 and 2/3 landing on repelling fixed point alpha
AllInternalAddresses(2);
[ [  ], [ [ 1/3, 2/3, 2 ] ] ]

For period 1 list is a empty.

[]

For period 2 it gives :

[ [ 1/3, 2/3, 2 ] ]

which contain one sublist :

[1/3, 2/3, 2]

It describe period 2 hyperbolic component of Mandelbrot set with external rays 1/3 and 2/3 landing on its root point [30]

Period 3[edit | edit source]

Rabbit Julia set with 3 external rays : landing on fixed point
lamination of Rabbit Julia set
AllInternalAddresses(3);
[ [  ], [ [ 1/3, 2/3, 2 ] ], [ [ 1/7, 2/7, 3 ], [ 3/7, 4/7, 3, 1/3, 2/3, 2 ], [ 5/7, 6/7, 3 ] ] ]

For period 3 we have previous period 2 adress and new list for period 3 :

[ [ 1/7, 2/7, 3 ], [ 3/7, 4/7, 3, 1/3, 2/3, 2 ], [ 5/7, 6/7, 3 ] ]

It has 3 elements ( sublists).

First element :

[ 1/7, 2/7, 3 ] 

describes period 3 hyberbolic component with rays 1/7 and 2/7 landing on its root c=0.64951905283833*%i-0.125, which lays on the boundary of main cardioid with internal angle = 1/3

Second element :

[ 3/7, 4/7, 3, 1/3, 2/3, 2 ]

describes period 3 component with rays 3/7 and 4/7 landing on its root point. To find it one must go thru period 2 component.

Because for c in wake (3/7, 4/7) dynamic rays 3/7 and 4/7 land together at a repelling periodic point then it also describes the airplane Julia set [31][32]" with landing angles [1/3, 2/3] and period 2.

Third element :

[ 5/7, 6/7, 3 ]

describe period 3 hyberbolic component with rays 5/7 and 6/7 landing on its root point ( it is c=-0.64951905283833*%i-0.125, which lays on the boundary of main cardioid with internal angle = 2/3 ).

Spider algorithm[edit | edit source]

The Spider algorithm [33] constructs polynomials with assigned combinatorics.

Papers :

See also programs :

Goole search : "spider algorithm" polynomial

RationalFunction[edit | edit source]

RationalFunction(m)

It returns a rational function f whose associated machine is m or a record describing the Thurston obstruction to realizability of f.

gap> m := PolynomialIMGMachine(2,[1/3],[]); # the basilica
<FR machine with alphabet [ 1, 2 ] and adder FRElement(...,f3) on Group( [ f1, f2, f3 ] )/[ f3*f2*f1 ]>
gap>  RationalFunction(m);
z^2-1.
gap> m:=PolynomialIMGMachine(2,[1/7]); # the rabbit
<FR machine with alphabet [ 1, 2 ] and adder FRElement(...,f4) on Group( [ f1, f2, f3, f4 ] )/[ f4*f3*f2*f1 ]>
gap> RationalFunction(m);
z^2 + (-0.12256116687667946+I*0.74486176661942738)

Delaunay triangulation[edit | edit source]

gap> LoadPackage("fr");
gap> z := Indeterminate(COMPLEX_FIELD);
x_1
gap> f := z^2-1;
x_1^2-1.
gap> m := IMGMachine(f);
<FR machine with alphabet [ 1, 2 ] and adder FRElement(...,f3) on Group( [ f1,\ f2, f3 ] )/[ f2*f1*f3 ]>
gap> Spider(m);
<marked sphere on <triangulation with 6 vertices, 24 edges and 8 faces> marked by [ f1, f2, f3 ] -> [ f1^-1*f2^-1, f1, f2 ]>
gap> Draw(last:julia);

or

gap> LoadPackage("fr");
gap>z := Indeterminate(COMPLEX_FIELD,"z");
gap> r := P1MapRational(z^2-1);
<P1 mapping of degree 2>
gap> IMGMachine(r); #I  Post-critical points at [ P1Point("-1+0i"), P1Point("0+0i"), P1Point("P1infinity") ]
<FR machine with alphabet [ 1 .. 2 ] and adder FRElement(...,f3) on Group( [ f1, f2, f3 ] )/[ f2*f1*f3 ]>
gap> Spider(last);
<marked sphere on <triangulation with 6 vertices, 24 edges and 8 faces> marked by [ f1, f2, f3 ] -> [ f1^-1*f2^-1, f\  1, f2 ]>
gap> Draw(last:julia);

Draws dynamical plane on the sphere with marked Delaunay triangulation. One can rotate sphere with mouse in real time.


References[edit | edit source]

  1. Group theory at wikipedia
  2. mathilluminated : Unit 6 The Beauty of Symmetry
  3. wikipedia : p-adic number
  4. learner.org course : mathilluminated - symmetry
  5. Elementary group theory
  6. learner.org course : mathilluminated - symmetry
  7. learner.org course : mathilluminated - symmetry
  8. learner.org course : mathilluminated - symmetry
  9. learner.org course : mathilluminated - symmetry
  10. Iterated monodromy group at wikipedia
  11. Introduction to Iterated Monodromy Groups by Sébastien Godillon
  12. Computer Science Logo Style Volume 3: Beyond Programming Brian Harvey
  13. wikipedia : Mealy_machine
  14. Alfredo Poirier : On Post Critically Finite Polynomials Part One: Critical Portraits
  15. wikipedia : Equivalence relation
  16. From fractal groups to fractal sets Authors: Laurent Bartholdi, Rostislav I. Grigorchuk, Volodymyr V. Nekrashevych
  17. From self-similar groups to self-similar sets and spectra by Rostislav Grigorchuk, Volodymyr Nekrashevych, Zoran Sunic
  18. Groups for Dendrite Julia Sets by Will Smith
  19. Explorer
  20. GAP software at wikipedia
  21. CAS at wikipedia
  22. FR package by Laurent Bartholdi for GAP CAS
  23. Draw function from fr package by Laurent Bartholdi
  24. graphviz - - Graph Visualization Software
  25. librsvg - free, open source SVG rendering library
  26. Unimodal Maps and Kneading Theory by Warren Weckesser
  27. ADMISSIBILITY OF KNEADING SEQUENCES AND STRUCTURE OF HUBBARD TREES FOR QUADRATIC POLYNOMIALS by HENK BRUIN AND DIERK SCHLEICHER
  28. Parameter rays of root points of period p components of Mandelbrot set
  29. Internal addresses in the Mandelbrot set and irreducibility of polynomials by Dierk Schleicher
  30. Parameter rays of root points of period p components of Mandelbrot set
  31. The Julia midgets scaling. The "Airplane" structure by Evgeny Demidov
  32. The n-Category Café discussion on Benoit Mandelbrot
  33. spider algorithm
  34. Algorithm - paper by John H. Hubbard and Dierk Schleicher
  35. Resurrecting Spiders by Claude Heiland-Allen
  36. original paper by Yuval Fisher
  37. Tore Møller Jonassen
  38. papers by Gregory A. Kelsey


Books:

See also[edit | edit source]