Before we get started, let us review some definitions. Recall that a group presentation for group \(G\) is written \(G = \langle S | R\rangle\) where \(S\) is a set of generators for \(G\) and \(R\) is a set of relations \(\big(\) \((S_1)^2*(S_2)^3 = \) the identity element (\(id\)) is an example of a relation that exists within \(G\), where \(S_1, S_2 \in S\) \(\big)\). A group action is a function \(a : G \times X \rightarrow X\) where \(X\) is some space. We call a group action faithful if there are no elements of \(G\) other than the identity for which \(a(g, x) = gx = x\). In this project, we consider groups for which \(S\) is a set of matrices in \(SL(2, \mathbb{R})\) and \(X = \mathbb{RP}^1\). Recall that \(SL(2, \mathbb{R})\) is the set of \(2\times2\) matrices with real entries of determinant \(1\). It suffices to think of \(\mathbb{RP}^1\) geometrically, as the set of linear lines going through the origin. \(\mathbb{S}^1\) is the unit circle. Given matrices \(g_1, ... , g_n\) as generators, we want to determine whether the generated group has a faithful action on \(\mathbb{RP}^1\). Lastly, free groups are groups which have no relations. For generators \(A, B\), \(A^j = B^k\) for \(j,k \in \mathbb{N}\) (or equivalently \(A^jB^{-k} = id\) ) would be a relation in our group, implying that the group is not free. It is known that free groups have faithful group actions, so if \(G = \langle g_1, ... g_n \rangle\) is isomorphic to a free group on \(n\) generators, \(G\) has a faithful group action.

How can we tell if G is isomorphic to a free group?

  Method 1: Cayley graph search

The Cayley graph for \(F_n\), a free group on \(n\) generators, is a visual representation for all possible elements (or words) in \(F_n\). For example, let {\(A,B\)} be the generating set for \(F_2\). The corresponding Cayley graph is shown in Figure 1, where each vertex represents an element of \(F_2\). Each horizontal edge to the right corresponds to multiplication by \(A\), and each horizontal edge to the left corresponds to multiplication by \(A^{-1}\). Likewise, each vertical edge going up corresponds to multiplication by \(B\), and each vertical edge going down corresponds to multiplication by \(B^{-1}\). The center of the Cayley graph is the identity in \(F_2\) (or the empty word), so the points one multiplication away from the center would be \(A, B, A^{-1}, B^{-1}\) (starting from the right and moving counterclockwise).

Figure 1: Cayley graph for a free group on 2 generators.

By recursively cheking through all of the points of the Cayley graph, we can try to find if any word in \(G\) is equivalent to the identity, ie. if there are any relations. If a relationship is found, we will know that \(G\) is not a free group; however, searching the Cayley graph will run forever if \(G\) is a free group, since the algorithm has an infinite amount of words in the group to check. In other words (no pun intended), the program will continue to search for relations that do not exist. Then, we need to find another algorithm which will instead terminate in finite time when \(G\) is free. This requires the use of the Ping-Pong lemma, and a consequence of using this method is that the program will run indefinetely if the group is not free.

  Method 2: Ping Pong

  Have \(G = < a_{1},a_{2},...,a_{n} > \) be a finitely presented group acting on a set \(X\). Then the Ping Pong, or Schottky, lemma defines a set of criterion under which \(G\) isomorphic to a free group.

  Ping Pong Lemma: Suppose \(a\) and \(b\) generate a group \(G\) acting on a set \(X\). If,

\(X\) has disjoint nonempty subsets \(X_{a}\), and \(X_{b}\), and 

\(a^{k}(X_{b})\) \(\subset X_{a}\) and \(b^{k}(X_{a}) \subset X_{b}\) for all non-zero powers \(k\)

  then \(G\) is isomorphic to a free group of rank 2.

  Proof. No element \(g\) of \(G\) represented by a word of the form \(a^{*}b^{*}a^{*} \cdots b^{*} a^{*}\) is the identity since \(g(X_{b}) \subset X_{a}\). This suffices, because any element of \(G\) is conjugate to one of that form. \(\square\)

This lemma also generalizes to an arbitrary number of generators.

n-Player Ping Pong Lemma: Suppose \(a_{1},a_{2},\cdots,a_{n}\) generate a group \(G\) acting on a set \(X\). If,

\(X \) has disjoint nonempty subsets \(X_{a_{1}},X_{a_{2}}, \cdots, X_{a_{n}}\) such that

\(a_{i}^{k}(X_{a_{j}}) \subset X_{a_{i}}\) for all \(i,j = 1,\cdots,n\)

Then \(G\) is isomorphic to a free group of rank \(n\).

Proof. Suppose \(g\) is an arbitrary element of \(G\) represented by the word \(a_{I_{1}}^{*},a_{I_{2}}^{*},\cdots,a_{I_{k}}^{*}\) where \(I_{j}\) is some element of {\(1,\cdots n\)}. If \(g\) is constructed using only two of our generators, then by the Ping Pong lemma \(g\) is not equal to the identity. If not, then there exists some \(a_{I_{c}}\) in our product s.t. \(I_{c} \neq I_{1},I_{k}\). Then, since \(g(X_{a_{I_{c}}}) \subset X_{a_{I_{1}}}\), this implies that \(g\) does not fix elements of \(X_{a_{I_{c}}}\), and therefore cannot be the identity. \(\square\)

For the purposes of this project, we will be using a modified version of the n-player ping pong lemma.

Modified n-Player Ping Pong Lemma: Suppose \(a_{1},a_{2},\cdots,a_{n}\) generate a group \(G\) acting on a set \(X\). If \(X\) has disjoint nonempty subsets \(Y_{a_{1}},Y^{-1}_{a_{1}},Y_{a_{2}},Y^{-1}_{a_{2}}, \cdots Y_{a_{n}},Y^{-1}_{a_{n}}\) satisfying,

\(a_{i}*\bigg(\Big(\bigcup \limits_{k=1}^{n} (Y_{a_{k}} \cup Y_{a_{k}}^{-1}) \Big) - Y_{a_{i}}^{-1}\bigg) \subset Y_{a_{i}} \\ (a_{i}^{-1})*\bigg(\Big(\bigcup \limits_{k=1}^{n} (Y_{a_{k}} \cup Y_{a_{k}}^{-1})\Big ) - Y_{a_{i}}\bigg) \subset Y_{a_{i}}^{-1}\)

Then \(G\) is isomorphic to a free group of rank \(n\).
With \(X_{a_{i}} = Y_{a_{i}} \cup Y^{-1}_{a_{i}}\), groups satisfying the modified ping pong criteria clearly satisfy the original ping pong criteria, and therefore generate a free group of rank n. The main difference lies in the requirement that for \(c = a_{i}^{\pm 1}\)  there exists a \(Y_{c} \subset X\) s.t. \(c^{*}(Y_{c}) \subset Y_{c}\).

Our Use of Modified \(n\)-Player Ping Pong:

Let us first construct the case where \(n =2\).

Let \(a_1, a_2 \in SL(2, \mathbb{R})\) generate a group \(G\) acting on \(\mathbb{RP}^1\). Since \(\mathbb{RP}^1\) and \(\mathbb{S}^1\) are homeomorphic, we will show a visual representation of \(G\) acting on \(\mathbb{S}^1\) instead.

Let us classify three types of generators of \(G\). Recall that each generator has determinant \(1\), by definition of being an eement of \(SL(2, \mathbb{R})\). Since the product of the eigenvalues of a matrix equals its determinant, for eigenvalues \(\lambda_1, \lambda_2\), we have that \(\lambda_1 = \dfrac{1}{\lambda_2}\). Then, three natural cases arise. 

Case 1: \(\lambda_1 \neq \lambda_2\).

Case 2: \(\lambda_1 = \lambda_2 =1\).

Case 3: \((\lambda_1)^* = \lambda_2\), for complex \(\lambda_1, \lambda_2\).

Since the eigenvectors corresponding to the eigenvalues lie in the real projective line (\(\mathbb{RP}^1\)), we disregard any complex eigenvalues (and thus complex eigenvectors). Elaborate more on attracting and repelling fixed points, taking a hyperbolic element g on circle.

Let \(v = (x,y) \in \mathbb{RP}^1\). Then, define the homeomorphism \(f: \mathbb{RP}^1 \rightarrow \mathbb{S}^1\) by 

\(f(x,y) = \left( \dfrac{2xy}{x^2+y^2} , \dfrac{x^2-y^2}{x^2+y^2} \right).\)

We take the eigenvectors for \(a_1\) and \(a_2\) and map them onto \(\mathbb{S}^1\) via the homeomorphism shown above. For \(\lambda_1 >1, \lambda_1\) is the attracting fixed point and for \(\lambda_2 <1, \lambda_2\) is the repelling fixed point. Since we have only considering Case 1, where \(\lambda_1 \neq \lambda_2\), every generator will have an attracting and repelling fixed point. Note that the attracting fixed point for \(a_1\) is the repelling fixed point for \((a_1)^{-1}\), and vice-versa. Subsets of the circle can be represented by an interval of angles, so we will refer to subsets of \(\mathbb{S}^1\) as intervals.

Let there exists disjoint intervals \(Y_{a_{1}},Y^{-1}_{a_{1}},Y_{a_{2}},Y^{-1}_{a_{2}}\), where \(x_{att}\), and \(x_{att}\) represents the attracting eigenvector of the generator. Then, we have to satisfy the following containments:

1. \(Y_{a_{1}}*Y_{a_{1}} \ , \ Y_{a_{1}}*Y_{a_{2}}\ , \ Y_{a_{1}}*Y^{-1}_{a_{2}} \subset Y_{a_{1}}\)

2. \(Y_{a_{1}}*Y_{a_{1}} \ , \ Y_{a_{1}}*Y_{a_{2}}\ , \ Y_{a_{1}}*Y^{-1}_{a_{2}} \subset Y_{a_{1}}\)

3. \(Y_{a_{1}}*Y_{a_{1}} \ , \ Y_{a_{1}}*Y_{a_{2}}\ , \ Y_{a_{1}}*Y^{-1}_{a_{2}} \subset Y_{a_{1}}\)

4. \(Y_{a_{1}}*Y_{a_{1}} \ , \ Y_{a_{1}}*Y_{a_{2}}\ , \ Y_{a_{1}}*Y^{-1}_{a_{2}} \subset Y_{a_{1}}\)

Figure 2 shows an example of modified 2-Player Ping Pong, with containments satisfied.