Our algorithm should take in a list of generators for a matrix group and output valid ping pong intervals if they exist, or run forever otherwise. There are a few main things this will involve: finding initial intervals to start our search with, expanding the initial intervals, and checking whether there is valid containment among the intervals for ping pong.
How do we initialize intervals?
We want to consider generators who have attracting and repelling eigenvalues. This will make the intervals easier to find since we can predict what their actions will look like on \(\mathbb{RP}^1\). The eigenvector corresponding to the attracting eigenvalue will remain as a fixed point and pull the rest of \(\mathbb{RP}^1\) closer to it. This means the eigenvector corresponding to the repelling eigenvalue will be a fixed point for the inverse of the generator. So we can choose our intervals to be some epsilon neighborhood of these eigenvectors in \(\mathbb{RP}^1\).
Given two generators that lie in the \(SL(2,\mathbb{R})\) (the group of \(2\times 2\) matrices with real entries that have determinant 1), we found 2 eigenvectors for each generators. Let \(v_{0}\) and \(v_{1}\) be the components of each eigenvector. These eigenvectors were mapped from the real projective line (\({\mathbb{R}\mathbb{P}}^{1}\)) onto the unit circle (\(S^{1}\)) via the homeomorphism
\((x,y) \mapsto (\dfrac{2v_{0} v_{1}}{v_{0}^{2} + v_{1}^{2}},\dfrac{v_{0}^{2} - v_{1}^{2}}{v_{0}^{2} + v_{1}^{2}})\)
where \((x,y)\) represent the coordinates that lie on the circle. Notice that as along as the eigenvectors are normalized (and Python normalizes them by default), the term \(v_{0}^{2} + v_{1}^{2}\) will equal 1, allowing \((x,y)\) to lie on the unit circle. Then, these four eigenvectors mapped onto \(S^{1}\) from generators \(A\) and \(B\) become the center of our intervals on the circle. One eigenvector from \(A/B\) (\(A\) or \(B\)) will act as a repelling point, and the other will act as an attracting point. That is, an interval on the circle multiplied by \(A/B\) will pull the interval closer to the attracting point and further from the repelling point.
Figure 1: Here is an example of what the initial intervals might look like along with the images of these
intervals under the other generators. (Each color corresponds to a generator and its inverse)
How do we search for intervals?
Method 1: Linear expansion of interval endpoints
We could just expand the endpoints of each interval by some amount epsilon until we find valid intervals, but we run into a problem. At some point, the intervals may intersect which will make containment of the images impossible. If, for example, the interval \(I_A\) corresponding to the generator \(A\) intersects the interval \(I_{A^{-1}}\) corresponding to \(A^{-1}\), some of the images we need to check containment for are \(A I_{A} \subset I_A\) and \(A I_{A^{-1}} \subset I_{A^{-1}}\) but if \(I_A \cap I_{A^{-1}} \neq \emptyset\), one of these images will explode. So we need some method of expanding our intervals in such a way to avoid these intersections.
Method 2: Geometric expansion of interval endpoints
One way to guarantee our intervals never intersect while searching is to only expand them by an amount that would keep them disjoint. To do this, we can write a function which finds the angle between two points on a circle and calculate the minimum distance between our interval enpoints and another interval. This is the allowable expansion distance. We can then expand by some multiple of this distance which is between 0 and 1.
How do we check containment?
After each step of interval expansion, we should check if the intervals and their meet the containment requirements of ping pong. The best way to do this is to take the vectors in \(\mathbb{RP}^1\) which represent interval enpoints and map them to angles on the circle via the homeomorphism \(\mathbb{RP}^1 \rightarrow S^{1}\). It is then easy to check containment of intervals on \(S^1\) of the form \((a, b)\).
How do we test if the algorithm works?
Since we want the algorithm to work for \(SL(2, \mathbb{R})\) generators, we can create random matrices by making random choices for 3 of the entries and then forcing the last to be one such that the determinant is one. There is no guarantee though that these matrices will generate a free group, so this could run forever. Instead, we want to find a way to generate \(SL(2, \mathbb{R})\) matrices which are guaranteed to generate a free group since in these cases we should expect our algorithm to find valid intervals. For 2 generators, we use the following corollary:
To create \(n\) generators which generate a free group, we use the fact that all free groups of \(n \geq 3\) generators are subgroups of a free group on 2 generators. In fact, if \(A\) and \(B\) generate a free group, then \(A^{k}B^{k}, k \leq n\) generate a free group. So we can reuse this corollary to get \(A\) and \(B\) and then use these to find the \(n\) generators we want.
Figure 2: Examples of valid ping pong intervals. (1): Linear expansion for 2 generators, (2): Geometric expansion for 3 generators.
See the code on GitHub here: https://github.com/CapSnCrunch/TXGL