分形/數學/群

這裡可以找到分形和群之間關係的例子。

介紹

"群論非常有用，因為它透過抽象的力量找到了不同事物之間的共同點。"

自相似群的代數結構和多項式的動力學性質之間存在著重要的聯絡。

群論 

• 幾何的
• 組合的
• 計算的

定義

字母表

字母表 $X$ 它是一組有限的符號 x 

$X=\left\{x_{1},x_{2},..,x_{n}\right\}$

自動機

自動機是順序機器的基本抽象數學模型。 不同型別的自動機 

• 識別自動機,
• 圖靈機
• 摩爾機
• 米利機,
• 元胞自動機
• 下推自動機

自動機有兩種視覺呈現

• 一個狀態表，描述了到下一個狀態的轉換和輸出，
• 一個狀態圖。

類

等價類 集合 X 中的元素 a 是集合 X 中所有與 a 等價的元素的子集

$[a]_{X}=\{x\in X|x\sim a\}.$

擴充套件

p-adic 數字是 0 到 p − 1（含）之間的自然數。

一個 p-adic 整數是一個 p-adic 數字的序列 

$..a_{i}..a_{1}a_{0}$

數字的 n-adic 擴充套件

二進位制整數或二元整數或 2-adic 整數 

$\sum _{i=0}^{n}a_{i}2^{i}$

其中 a 是二進位制字母表 X ={0,1} = (0, .. ,2-1) 的一個元素

圖

施賴爾圖

自動機的摩爾圖（或摩爾機的狀態圖）它是一個有向帶標籤的圖，它有 

• 頂點（節點）用自動機/基本群的生成元的狀態來識別
• 邊（帶箭頭的線）顯示狀態轉換，
• 標籤 : (輸入, 輸出) 是 X 中元素的有向對

群

"群是服從一組嚴格規則的物體集合，這些規則在操作作用於它們時適用。"

一個群 $G$ 是代數結構 

$G=\{A,\perp \}$

, 其中 

• $A$ 是一個非空集合
• $\perp$ 表示一個稱為群運算的二元運算

$\perp :A\times {}A\rightarrow {}A,$

它必須服從以下規則（或公理） 

• 封閉性，
• 結合律
• 單位元
• 逆元
• 交換律

單位元 : "群必須有一個元素充當單位元。單位元的特徵是它與群運算下的任何其他成員組合時，都不會改變該成員。"

逆元 : "群的每個成員或元素必須有一個逆元。當一個成員與它的逆元在群運算下組合時，結果是單位元" 封閉性 : "這意味著每當兩個群成員在群運算下組合時，結果都是群的另一個成員"

結合律 : "如果我們取三個或更多群成員的列表並將其兩個兩個地組合，那麼從列表的哪一端開始並不重要"

自動機群 = 由自動機生成的群

FR = 泛遞迴群

IMG = 迭代單值群

IMG

迭代單值群透過 自同構 作用於原像的 有根樹

$T_{f}:=\bigsqcup _{n\geq 0}f^{-n}(t),$

其中頂點 $z\in f^{-n}(t)$ 透過邊與 $f(z)\in f^{-(n-1)}(t)$ 相連。

機器

有限狀態機

• 米利機
• 摩爾機

多項式

後臨界有限多項式 : 臨界點的軌道是有限的。當臨界點是週期性的或前週期性的時，就會出現這種情況。

關係

等價關係 ~ 在集合 X 上

• 它是在 X 上的一個二元關係，是自反的、對稱的和傳遞的
• 它在集合 X 上誘匯出一個劃分 P，劃分為幾個不相交的子集，稱為等價類

序列

ks = 揉捏序列（s）

詞語

在字母表 X 上的詞語 w 是字母表 X 中的任何符號序列。詞語可以是 

• 無限的
• 有限 $w=x_{1}x_{2}..x_{n}$
• 空詞 = 長度為零的詞： $w=\varnothing =\epsilon$

$0w$ 表示以 $0$ 開頭的詞。

示例

"二次有理對映的迭代單夢群，其中後臨界集的大小最多為 3，排列成表格。

大多數的代數結構尚未得到很好的理解。"

f(z)	標準作用	核	機器	群	註釋
$z^{2}$	$t=(1,t)\sigma$		加法機	二進位制加法群
$z^{2}-1$				巴西利卡群
$z^{2}-2$					與切比雪夫多項式 T2 共軛
$-{\frac {z^{3}}{2}}+{\frac {3z}{2}}$				漢諾塔群
$z^{2}+-{\frac {16}{27z}}$				謝爾賓斯基三角形
$z^{2}+i$				湯普森類群	中間增長

其中

• $\sigma$ 是一個排列

軟體

• CoxeterTilings in JS：Coxeter 群萬花筒

Group Explorer

Group Explorer 是抽象代數課堂的數學視覺化軟體。

GAP

GAP 是一個 CAS 軟體。 執行

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

如果系統無法載入包，請安裝庫、包並編譯它們（nq、pargap、fr）。執行測試

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

載入 Laurent Bartholdi 的 fr 包

LoadPackage("fr");

執行 fr 測試

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

GAP 和 fr 包可以使用 Mandel、ImageMagic、graphviz 或 rsvg-view 等外部程式繪製和顯示影像。

繪製

繪製

 Draw(NucleusMachine(BasilicaGroup));

• 建立 m（米利機或元素 m）的圖描述。 它使用 graphviz 包 中的 dot 程式轉換為 Postscript。
• 使用命令列程式 display（來自 ImageMagick）或 rsvg-view 在單獨的 X 視窗中顯示影像。 這在 UNIX 系統上有效。

可以右鍵單擊影像以檢視顯示程式的本地選單。

如果 Draw 函式的第二個引數（檔名）存在，則圖將以 dot 格式儲存到該檔名下。

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

將輸出儲存到 a.dot 檔案。dot 檔案是一個描述圖的文字檔案，以 dot 語言編寫。

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

或 png 檔案

dot -Tpng a.dot -o a.png

或 svg

dot -Tsvg a.dot -o a.svg

外部角

來自 FR 包的函式

ExternalAngle(machine)

返回：識別機器的外部角。

如果機器是單臨界多項式的 IMG 機器，則該函式計算落在臨界值的外部角。

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 ]

另一個例子

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 ]

機器

PolynomialIMGMachine

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

此函式建立一個 IMG 機器，它描述一個拓撲多項式。該多項式在外部角語言中以符號方式描述。

d 是多項式的次數。

per 是角度列表

pre 是預角度列表。

角度是理性數，以模 1 計。per 或 pre 中的每個條目都是一個理性數（解釋為一個角度），或者是一個角度列表 [a1，...，ai]，使得 da1 = ... = dai。per 中的角度是落在法圖分量根部的角度，而 pre 中的角度落在 Julia 集的其他點上。

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

PostCriticalMachine(f)

返回：f 的後臨界軌道的米利機。該函式在字母表 [1] 上構建一個米利機 P，它描述了 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 ]

它實際上是一個具有恆定出度的定向圖 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 序列

KneadingSequence(angle)

"此函式將理性角轉換為 kneading 序列， 用於描述二次多項式。 "（來自 fr 文件）

KneadingSequence(1/7);

給出

[ 1, 1 ]

"如果角度在 [1/7, 2/7] 之間，並且設定了標記選項，則 kneading 序列將用 A、B、C 中的標記進行裝飾。"（來自 fr 文件）

KneadingSequence(1/5:marked);

給出

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

根點的射線

ExternalAnglesRelation(degree, n)

"此函式返回...所有落在度數乘以角乘法下共同週期點的所有外部角對。"（來自 fr 文件）換句話說，它給出了落在曼德布羅特集的週期 n 雙曲分量的根點的外部射線轉彎中的角度。

對於復二次多項式（度數 = 2）和週期 3

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

它需要一個額外的命令

EquivalenceRelationPartition(last);

並給出

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

此列表有 4 個元素

• 3 對週期 3 角 i/7
• 1 對週期 2 角 i/3

內部地址

"此函式返回所有在角度加倍下週期最多為 n 的週期點的內部地址。這些內部地址描述了從著陸點到曼德布羅特集中的主心形路徑上的突出雙曲分量。"（來自 fr 文件）

將其與 **角度內部地址** 進行比較

注意角度是分母為（奇數）的分數

$d=(2^{n}-1)$

其中 n 是週期，d 是分母

週期 2

對於 $f_{c}(z)=z^{2}-1$ 的巴西利卡 Julia 集，外部射線 1/3 和 2/3 落在排斥不動點 alpha 上

AllInternalAddresses(2);
[ [  ], [ [ 1/3, 2/3, 2 ] ] ]

對於週期 1，列表為空。

[]

對於週期 2，它給出

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

其中包含一個子列表

[1/3, 2/3, 2]

它描述了曼德布羅特集的週期 2 雙曲分量，外部射線 1/3 和 2/3 落在其根點上。

週期 3

兔形 Julia 集，有 3 條外部射線： ${\mathcal {R}}_{\frac {1}{7}},{\mathcal {R}}_{\frac {2}{7}},{\mathcal {R}}_{\frac {4}{7}}\,$ 落在不動點 $z=\alpha _{c}\,$ 上

兔形 Julia 集的分層

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 ] ] ]

對於週期 3，我們有之前的週期 2 地址和週期 3 的新列表

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

它有 3 個元素（子列表）。

第一個元素

[ 1/7, 2/7, 3 ] 

描述了週期 3 雙曲分量，射線 1/7 和 2/7 落在其根 c=0.64951905283833*%i-0.125 上，它位於主心形的邊界上，內部角 = 1/3

第二個元素

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

描述了週期 3 分量，射線 3/7 和 4/7 落在其根點上。要找到它，必須透過週期 2 分量。

因為對於醒著的 c 在 (3/7, 4/7) 中，動態射線 3/7 和 4/7 在一個排斥週期點處一起著陸，所以它也描述了飛機 Julia 集，其著陸角為 [1/3, 2/3]，週期為 2。

第三個元素

[ 5/7, 6/7, 3 ]

描述週期為 3 的雙曲分量，其射線 5/7 和 6/7 在其根點處著陸（它是 c=-0.64951905283833*%i-0.125，位於主心形邊界上，內部角 = 2/3）。

蜘蛛演算法

蜘蛛演算法 構造了具有指定組合學的多項式。

論文

• 蜘蛛演算法 - John H. Hubbard 和 Dierk Schleicher 的論文
• Claude Heiland-Allen 的線上文章
• Yuval Fisher 的原始論文
• Tore Moller Jonassen 的論文
• Gregory A. Kelsey 的論文
• SUZANNE HRUSKA BOYD 和 CHRISTIAN HENRIKSEN 的多項式匹配的 MEDUSA 演算法

另請參閱程式

• Yuval Fisher 的蜘蛛程式
• Wolf Jung 的 Mandel

谷歌搜尋："蜘蛛演算法" 多項式

有理函式

RationalFunction(m)

它返回一個有理函式 f，其關聯的機器為 m，或者描述 f 可實現性的 Thurston 障礙的記錄。

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 三角剖分

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);

或者

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);

在球體上繪製動態平面，並標記 Delaunay 三角剖分。可以用滑鼠即時旋轉球體。

參考文獻

書籍

• 群論探險：魔方、梅林機和其他數學玩具 作者：David Joyner

另請參閱

• 視覺群論 作者：Nathan Carter