search

aidevnn / FastGoat

What C# can do for studying Finite Groups, quotient groups, semi-direct products, homomorphisms, automorphisms group, characters table, minimalistic rings and fields manipulations, polynomials factoring, fields extensions and many more...
MIT No Attribution
10 stars 1 forks source link

Graph theory tools for finite groups presentation #54

Closed aidevnn closed 4 months ago

aidevnn commented 5 months ago

The current implementations of the Todd-Coxeter and J. Cannon algorithms for managing finite group presentations do not incorporate graph theory, presenting an opportunity for enhancement. For instance, these methods are currently unable to handle the Symmetric group of order 7.

aidevnn commented 5 months ago

A proper implementation of the J.J. Cannon algorithm for defining relators is now complete. This allows for the computation of permutation groups of order 7 in just one second. By leveraging newly discovered methods, we can enhance the previous implementation of the Todd-Coxeter algorithm.

aidevnn commented 5 months ago

There are some concerns with the current implementation of the Todd-Coxeter algorithm. Specifically, it struggles to handle coincidences when the relators are not properly structured. Additionally, there seems to be some redundant or ‘dead’ code present that needs to be addressed.

aidevnn commented 5 months ago

We have implemented a new version of the Todd-Coxeter algorithm, which computes permutation groups of order 7 more efficiently than the previous one. This version can also be applied to the J.J.Cannon algorithm for defining relators, and both algorithms can be integrated into a single structure.

aidevnn commented 5 months ago

Common Graph tools* can handle both TC-algo and JJCan-algo. The remaining task is to integrate it with WordGroup and to rerun all unit tests and examples.

*: implementation is independant from other part of the project and can be reused (copy-paste) without change or migrated to another programming language.

aidevnn commented 5 months ago

A possible integration of the Todd-Coxeter algorithm and Cannon’s algorithm has been done, and it works very well.

John J. Cannon also provided many other useful algorithms for finite groups, such as computing all subgroups of a given group, or finding transitive groups of higher degree. It would be interesting to write them in C# as well and to add them to the project.