(a)Show that a + d = 0.

(b)Show that A and S are conjugated in PSL(2, ℤ).

Hint: Use the normal form Ri1S ⋅⋅ ⋅ Rim−1SRim , m ≥ 2, 1 ≤ ij ≤ 2 for j = 1, . . . , m and i1 = im, as in the proof of Theorem 8.38.

(a)If −1 is a quadratic residue modulo n, that is, −1 ≡ q2 mod n for some q ∈ ℤ, then n is a sum of two squares in ℤ, that is, n = x2 + y2 with x, y ∈ ℤ.

Hint: If −1 ≡ q2 mod n, then there exists p ∈ ℤ with q2 + pn = −1. Form A(z) = By Exercise 8.16 (b) the element A ∈ PSL(2, ℤ) is conjugated to S, that is, there exists X ∈ PSL(2, ℤ) with and XSX−1 = A.

(b)If n = x2 + y2 with x, y ∈ ℤ and gcd(x, y) = 1, then −1 is a square modulo n.

(c)Use Exercises 8.17 (a) and 8.17 (b) for showing that a prime number p is a sum of two squares if and only if p = 2 or p ≡ 1 mod 4.

–word problem

–conjugacy problem

–isomorphism problem

–residually finite monoid

–Hopfian group

–presentations of monoids and groups

–rewriting system

–confluence, termination, convergence

–Church–Rosser property

–semi-Thue system

–free group

–free product

–Baumslag–Solitar group BS(p, q)

–Waack group W

–Tietze transformation

–free partially commutative monoid

–graph group

–semidirect product

–amalgamated product

–HNN extension

–Britton reduction

–Baumslag group

–rational set

–rank

–(kernel of the) Schreier graph

–Whitehead automorphism

–Nielsen transformation

–graphical realization

–special linear group SL(2, ℤ)

–modular group PSL(2, ℤ)

–Finitely generated residually finite groups are Hopfian.

–Strong confluence ⇒confluence.

–Confluence ⇔Church–Rosser

–Local confluence and termination ⇒confluence.

–Local confluence can be tested based on critical pairs.

–If S ⊆ Γ∗ × Γ∗ is a finite convergent semi-Thue system, then the word problem in Γ∗/S is decidable.

–Residually finite, finitely presented monoids have a decidable word problem.

–Free groups are residually finite.

–Trace monoids embed into RAAGs and their word problem can be solved in linear time.

–Convergent systems for amalgamated products and HNN extensions.

–Groups embed themselves into their amalgamated products and HNN extensions.

–1 ≠ w ∈ G ∗U H or 1 ≠ w ∈ HNN(G; A, B, φ) ⇒ w is Britton reducible.

–Subgroups are rational subsets if and only if they are finitely generated.

–Benois: rational subsets of a finitely generated free group form an effective Boolean algebra.

–Free groups are isomorphic if and only if their bases have the same cardinality.

–If K(G, Σ) is the kernel of the Schreier graph with edge set E and spanning tree T, then G is isomorphic to the free group F (E+ T).

–Nielsen–Schreier theorem: subgroups of free groups are free.

–F finitely generated free group and |G F| = n < ∞, then the rank formula (rank(F) − 1) ⋅ n = rank(G) − 1 holds.

–Word / conjugacy / isomorphism problems are decidable for finitely generated free groups.

–Aut(F) is finitely generated by the Whitehead automorphisms.

–The monoid SL(2, ℕ) is free with basis {T, U}.

–SL(2, ℤ) = {R, S}∗/{S4 = R6 = S2R3 = 1} and PSL(2, ℤ) = {R, S}∗/{S2 = R3 = 1} (ping–pong argument)

–Countable free groups are subgroups of PSL(2, ℤ) and SL(2, ℤ).