Lecture 17

Theorem 1. Let G be finitely presented C(4) − T (4) group. Then G is automatic.

Proof. We prove special case when G = π_{1}X with X a (4, 4) complex. Without loss of generality, each 2-cell is a square (obtain this by subdividing). Without loss of generality, X has one 0-cell (treat general case using “A∗B is automatic ⇔ A, B are automatic” and π_{1}(X/X^{0}) ≅ π_{1}X ∗ f_{|X^{0}|−1}).

The regular language L consists of geodesic paths in (X̃)′ which do not contain certain subpaths. (X̃ = Cayley graph of G.)

Forbidden paths:

(figure) no “backtracks” (in fact, already forbidden by geodesic

requirement), (figure) no “wrap around” a single 2-cell (in fact, already forbidden

by geodesic requirement), (figure) no “postponed turns.”

We need to show that for each v ∈ X̃^{0} there is a nonforbidden geodesic path from 1 to v. Show that starting with a geodesic γ.

(figure) Gradually transforming the geodesic obtain nonforbidden one. Process stops because each transformation yields a geodesic less with respect to lexicographical order, induced by assigning “t” to turn vertices and “n” to non-turn vertices.

Obtained a language L that surjects to G. Interestingly, it is language we were talking about last time. (figure)

Prove fellow travelling property. Suppose U, V are paths in L such that d_{G}(u, v) ≤ 1.

(figure)

Then there is a disc diagram for uev^{−1} where e = 1 or a single edge.

Combinatorial Gauss–Bonet theorem: curvature argument implies D is a ladder, so U, V fellow travel. Namely, note that curvature given by the top path is at most \frac{π}{2} , as is curvature given by the bottom. Indeed,

path can’t have \frac{π}{2} curvature right after 0 (figure),

path can’t have two \frac{π}{2} in a row (figure),

can’t happen (figure),

after string of 0, there is a negative curvature before positive (figure).

(figure) Sum is 2π, so at the “end” we have two positive angles, which gives a ladder.

Note that π curvature at the “start” may be ignored, as language is closed under subpath (figure), and note also that \frac{π}{2} curvature at the “start” gives nonpositive curvature on the top and bottom (figure).

□

Definition 1. G is biautomatic if there is a language in monoid generators S of G such that

1) L → G is a surjection,

2) K-fellow travelling property between the paths U, V such that initial and end points of U, V are at distance ≤ 1 in Γ(G, S).

Definition 2. A combing of a group G with monoid generators S is a map ϕ : G → M (M = M(S)) such that with ρ : M → G induced by generators, ρ ∘ ϕ = Id (i.e. it’s assignment of normal form for each g ∈ G). (figure)

Require that:

1) |ϕ(g)| ≤ Kd(1, g) for some universal constant,

2) if d(g, h) ≤ 1, then ϕ(g), ϕ(h) K-fellow travel. 1’) ϕ(g) is quasigeodesic.

For bicombing, require 2’) left + right fellow travel.

CAT(0) groups are combable, automatic groups are combable. Unknown if a combable group is always automatic.

If G is combable then 1) G is finitely presented,

2) G has a quadratic isoperimetric function. Draw all combings, use fellow travelling.

(figure)