Lecture 16

Automatic Groups.

Definition 1. Finite State Automata is a finite directed graph Γ, labeled by some alphabet S ⊂ {a_{1}, …, a_{n}, a_{1}^{−1}, …, a_{n}^{−1}}. Vertices are called states. One vertex is a start state. Some vertices are accept states.

Example. (figure)

Language L accepted by the FSA is set of all words in M = M(S) (a free monoid) that can be “read off” from Γ starting at a start state, ending at an accept state.

So accepted words correspond to labels of directed paths starting at start, ending at accept state.

The FSA Γ is deterministic if there is at most one outgoing edge labeled s at each state.

Languages L accepted by a FSA are called regular.

(figure) L = {a^{n}|n ≥ 0, n =_{3} 2}.

S = {0, 1}.

Any finite subset is regular. (figure)

Lemma 1. Any regular language is actually given by a deterministic FSA.

Proof. Make a new FSA whose states are collections of states in Γ. (Endpoint of arrow starting at a collection is collection of corresponding endpoints.)

Lemma 2. If L is regular then L^{C} (compliment) is also regular.

Proof. Let Γ be DFSA such that L = Accept (Γ). Let Γ^{C} be FSA on the same labeled directed graph as Γ with the same start state, but with accept states concluding compliment set to set of accept states Γ. Then language accepted by Γ^{C} is L^{C}.

(figure: example of Γ^{C})

Consider Cayley graph J of group ℤ × ℤ.

(figure: Cayley graph) Finite geodesics are given by the rule “never go back”. Set of all finite geodesics is regular language.

(figure: corresponding FSA)

Theorem 1. (A Sample Theorem) Suppose L = L(S) is a regular language in some alphabet S. Let ϕ : S → G be a map to finitely presented group. Let ϕ : L → G be the induced map. Suppose ϕ : L → G is surjective and finite-to-one, i.e. |f^{−1}(g)| < ∞. Then G has solvable word problem.

Proof. Given a word w in generators ϕ(s_{1}), …, ϕ(s_{k}) of G we can recognize w = 1_{G} by enumerating possibilities.

How to recognize w ≠ 1_{G}? There are finitely many words {u_{1}, … u_{k}} such that ϕ(u_{i}) = 1. By brute searching we eventually determine that w = ϕ(l) for some word l ∈ L (since we can enumerate all words in L). Then check if l ∈ {u_{1}, …, u_{k}}.

Automatic Structure for a Group G.

Definition 2. Automatic structure for a group G, S (S is set of monoid generators) a regular language L in S = {s_{1}, …, s_{k}} such that:

1) the map L → G is surjective,

2) ∃K such that if u, v ∈ L and d_{g}(u, v) ≤ 1 then the paths u, v in Γ(G, S) K-fellow travel.

(figure: fellow traveling) d(u_{i}, v_{i}) < k Example. ℤ × ℤ. L = {a^{n}b^{m}|n, m ∈ ℤ} (figure) Example. “Diagonal, then straight”. (ab)^{n}a^{m}, (ab)^{n}b^{m}, (ba)^{n}a^{m}, (ba)^{n}b^{m}, etc. (figure)

Theorem 2. (ECHLPT) Let G be word-hyperbolic with monoid generating set S.

1) Then set of all geodesics in S form a regular language.

2) L is the regular language of an automatic structure for (G, S).

Proof. 1) Holds since σ not a geodesic ⇔ ∃w_{i} ⊂ σ such that w_{i} ∈ {w_{1}, …, w_{k}} (w_{1}, …, w_{k} are forbidden set, i.e. larger part of relators).

Exercise. Set of words not containing any {w_{1}, …, w_{k}} is regular.

2) Thin triangles. (figure) □ In particular, this applies to finite groups. Fact. If A, B are automatic, then A × B is automatic. But it is unknown

whether A × B automatic implies A, B automatic.

Theorem 3. Finitely presented C(4) − T (4), C(6) − T (3), C(3) − T (6) groups are automatic.

Theorem 4. If G is automatic, then its isoperimetric function is ≤ n^{2}.

So in some sense it’s “nonpositive” curvature.