Searching for intervals:
Extremely small interval images:
Error caused by overlapping intervals. The image of the red interval under its inverse blows up to cover RP1.
Gallery
Ping Pong and Beyond
Future Work
Provable algorithm:
Currently, we expand intervals in small ϵϵ steps and check for containment along the way. However, it is possible that on any given failed trial, our choosen value for ϵϵ was too large and a smaller choice would be able to identify successful Ping Pong intervals. Then, we want to implement an algorithm that will test for Ping Pong intervals to arbritary precision, giving a sure answer for whether a given set of generators generate a free group or not. This algorithm will either output successful Ping Pong intervals or run indefinetely, decreasing the ϵϵ step and testing for intervals as time goes on.
Figure 1
– Automatic Structures (some groups have faithful actions but are not free, how can we modify this algorithm to work for different groups?)
– containment is based on a graph depending on the group (used to be consistent for free groups)
– initial intervals are based on SVD instead of eigenvectors
Algorithm
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 RP1RP1. The eigenvector corresponding to the attracting eigenvalue will remain as a fixed point and pull the rest of RP1RP1 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 RP1RP1.
Given two generators that lie in the SL(2,R)SL(2,R) (the group of 2×22×2 matrices with real entries that have determinant 1), we found 2 eigenvectors for each generators. Let v0v0 and v1v1 be the components of each eigenvector. These eigenvectors were mapped from the real projective line (RP1RP1) onto the unit circle (S1S1) via the homeomorphism
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)
To create nn generators which generate a free group, we use the fact that all free groups of n≥3n≥3 generators are subgroups of a free group on 2 generators. In fact, if AA and BB generate a free group, then AkBk,k≤nAkBk,k≤n generate a free group. So we can reuse this corollary to get AA and BB and then use these to find the nn 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
Background
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 GG is equivalent to the identity, ie. if there are any relations. If a relationship is found, we will know that GG is not a free group; however, searching the Cayley graph will run forever if GG 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 GG 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.
