|
|
${\rm PSL}_2(\mathbb{Z})$ 可以由如下三个分式线性变换生成：
$$Az=-\frac{1}{z},\quad Bz=z+1,\quad Cz=z-1.$$
这个图展示的是模群 ${\rm PSL}_2(\mathbb{Z})$ 在上半平面的作用。
${\rm PSL}_2(\mathbb{Z})$ 中的任何元素 $g$ 都可以表示为 $A,B,C$ 的乘积，这乘积是一个由 $A,B,C$ 组成的单词，但是这个单词表示不是唯一的。我们可以给 $g$ 规定一个唯一的标准形式，即最短字典序表示。在 $g$ 的所有单词表示中，我们取其长度最短的，并且是字典序 $A< B< C$ 下最小的那个单词作为其标准表示。所有 $g\in {\rm PSL}_2(\mathbb{Z})$ 的最短字典序表示构成一个“语言”，叫做由群 ${\rm PSL}_2(\mathbb{Z})$ 的最短字典序语言 (shortlex language)。
精彩的地方来了：${\rm PSL}_2(\mathbb{Z})$ 的最短字典序语言是一个正则语言，即它可以由一个有限状态机生成，群中的元素与状态机识别的单词一一对应。这个状态机由下图所示：
比如 ${\rm PSL}_2(\mathbb{Z})$ 的长度为 1 的词有 A,B,C。
长度为 2 的词有 AB, AC, BA, CA。
长度为 3 的词有 ABA, ACA, BAB, BAC, CAB, CAC。以此类推。- import itertools
- def is_accepted(word):
- state = 1
- for char in word:
- if state == 1: # Start state
- if char == 'A':
- state = 2
- elif char in ['B', 'C']:
- state = 3
- elif state == 2: # Last letter was A
- if char == 'A':
- state = 4 # Avoid A²
- elif char in ['B', 'C']:
- state = 3
- elif state == 3: # Last letter was B or C
- if char == 'A':
- state = 2
- elif char in ['B', 'C']:
- state = 4 # Avoid consecutive {B, C} that would reduce via B³=1 and C=B²
- elif state == 4: # Fail/sink state
- state = 4
- return state in [1, 2, 3]
- alph = ['A', 'B', 'C']
- accepted_by_length = {}
- rejected_by_length = {}
- for length in range(4):
- words = [''.join(combo) for combo in itertools.product(alph, repeat=length)]
- accepted = []
- rejected = []
- for w in words:
- if is_accepted(w):
- accepted.append(w)
- else:
- rejected.append(w)
- accepted_by_length[length] = accepted
- rejected_by_length[length] = rejected
- print("Accepted words by length:")
- for l, acc in accepted_by_length.items():
- print(f"Length {l}: {acc}")
- print("\nRejected words by length:")
- for l, rej in rejected_by_length.items():
- print(f"Length {l}: {rej}")
你可能要问了：${\rm PSL}_2(\mathbb{Z})$ 是自动群这个事情是不是依赖于 A,B,C 这组特殊的生成元呢？如果换一组生成元，它对应的最短字典序语言还是正则语言吗？答案是肯定的，自动群与生成元的选取无关，它不依赖于特定的群表现。Word processing in groups. David Epstein. |
|
