Where to begin in Computational Group Theory?

Question

I'm coding a small application that looks for periodic solutions to the gravitational n-body problem. I'm trying to better understanding the symmetries of solutions, which is made up of the product of ($d$ is the number of space dimensions, $n$ is the number of bodies) the following groups:

• Permutation of bodies $Sym(n)$.
• Isometries of ambiant space symmetry $O(d)$ (translational symmetry is easily dealt with so I'm not including it here.)
• Time shifts and time reversal (isometry group of $\mathbb{R} / \mathbb{Z}$ since I'm only looking at periodic solutions)

Given a few generators of a subgroup, I'm trying to find computationally tractable methods for the following problems:

• Is the generated group finite ?
• Given a member of new symmetry, is it in the generated group (membership problem).

I know close to nothing about Computational Group Theory, so it is hard for me to know what to look for. Can you please give me some keywords / pointers / references? Any help is appreciated.

EDIT:

A few valuable comments made it clear that I need to clarify what I'm asking. Some additional context first: like I mentioned above, I'm working on a simulation project (which you can try online at this address: https://gabrielfougeron.github.io/choreo/) that numerically solves the n-body problem. The numerical scheme is a rather standard Fourier spectral solver for the extremal action equations $\nabla S(x) = 0$. It so happens that imposing additional symmetries of the type $\sigma(x) = x$ on the sought solution where $\sigma$ is in the group described above translates directly to linear constraints on the Fourier coefficients. This allows me to reduce the number of parameters, reduce the number of computations and reduce memory footprint. This part is already implemented and works.

Very often though, a solution that was found without symmetry constraints will exhibit a certain symmetry nonetheless. I'm trying to write a piece of code that detects these additional symmetries. A simple numerical approach is to minimize $\|\sigma(x)-x\|$ given $x$, this works so well that I find lots of new $\sigma$ that leave my solutions invariant. Awesome.

My problem is that most of these symmetries are most often redundant: they can be written as combinations of other symmetries that are already known to leave my solution invariant. This is why I'd like to describe the space of symmetries that I've already considered (i.e. the group generated by the symmetries I've already found), as well as designing a numerical test for the membership problem.

Let me describe the same problem in a finite dimensional vector space setting, and not in a group theoretic setting, as well as what I would consider a possible numerical answer to give an idea of what I'm after.

Suppose that you are given a list of generators $v_1, v_2, \dots, v_m \in \mathbb{R}^n$. We can group these in a matrix $V\in M_{n,m}(\mathbb{R})$. Given a new vector $w\in\mathbb{R}^n$ you want to know whether it lies in the vector space generated by the $v$s. In matrix terms, this is equivalent to asking whether there exists an $x\in\mathbb{R}^m$ such that $V\cdot x = w$. A standard way to numerically answer this question is to find a minimum norm solution to the corresponding quadratic optimization problem. The corresponding residual to this minimization problem is the square distance to the vector space spanned by the generators. In practice, thresholding this residual is a very reasonable first step to determining whether $w$ is in this space.

This is super classical in numerical linear algebra and every respectable package does it very well, either using SVD or full QR decomposition on floating point representations of the vectors at play. Unless the problem is extremely ill-conditionned or the need for precision exceeds that of the floating point representation, there is no need to go further.

I understand that my problem is more subtle. Like Andy Putman mentioned, "in a connected Lie group the $\varepsilon$-ball around every point generates the whole group". In a sense, composition in a connected compact Lie Group like $O(n)$ loops back on itself, whereas matrix vector multiplications escapes at infinity.

Regardless, I'm certainly not the first person to ever wonder about these questions and I'm convinced there is an extensive body of literature on the subject. What I need is a few pointers, a few keywords so that I can find this literature and make my own research.

I hope I've been able to clarify the problem, please do tell me if this is still not clear.

Answer 1

As it was made quite clear in the comments, you are not at the stage where you can ask a sensible question. Thus, I am treating your question as a reference request. The first issue is that there is no canonical computability model when one deals with real numbers (or subgroups of $SL(n, \mathbb R)$). There are several ways to deal with this:

1. You can work with matrices whose entries belong to a fixed number field. (I am not sure you know what this means since your background is in physics.) Then one can work with any of the standard notions of computability.

2. Work with the Real RAM or BSS computational model, see

Blum, Leonore; Cucker, Felipe; Shub, Michael; Smale, Steve, Complexity and real computation. Foreword by Richard M. Karp, New York, NY: Springer. xvi, 453 p. (1997). ZBL0948.68068.

3. Work with the bit-computability model, see e.g.

Weihrauch, Klaus, Computable analysis. An introduction, Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer. x, 281 p. (2000). ZBL0956.68056.

Once you have some idea about questions which make sense when dealing with real computations, you can take a look here:

de Graaf, Willem Adriaan, Computation with linear algebraic groups, Monographs and Research Notes in Mathematics. Boca Raton, FL: CRC Press (ISBN 978-1-4987-2290-2/hbk; 978-1-4987-2291-9/ebook). xiv, 327 p. (2017). ZBL1518.14001.

Lastly, there are various software packages allowing you to perform computations in groups (written, say, in GAP by de Graaf, Holt and many others).