Notes on Computational Group Theory (2010) [pdf] | Hacker News Reader

Notes on Computational Group Theory (2010) [pdf]

math.colostate.edu

64 pointslainon5 comments

Having just finished a geometric group theory course I was hoping to see something about the word problem for automatic groups, or at least an algorithm to compute Dehn presentations of f.g. hyperbolic groups, but it looks like a cool resource with plenty of interesting topics.

Another book the HN crowd might like is Shoup's "a computational introduction to number theory and algebra"[0], it is much more broad and with litte focus on implementations, but a very interesting book nonetheless

[0]https://shoup.net/ntb/

Nice! Similar recommendation: William Stein's "Algebraic Number Theory, A Computational Approach" got me excited about studying math again. I would recommend it to anybody reading this thread.

https://github.com/williamstein/stein-ant

Please go easy on me, but is there a list of applications of CGT somewhere?

As far as I know CGT is mostly of interest to mathematicians, because there are some groups whose study require calculations that are absolutely impractical to carry out by hand, such as presentations of the sporadic groups. Or maybe you need to know how many nonabelian groups of order 2652 are there and throwing it to a computer is just the fastest way to find out or you need to compute conjugacy classes or stuff like that.

Computational algebra more broadly however has many applications to cryptography for example

I am not aware of such a (comprehensive) list but if it existed it would be a very long one for such a relatively little known field. The few survey papers on Computational Group Theory (CGT) focus mainly on applications in pure mathematics and to a less extent in theoretical computer science.

Nevertheless, CGT has numerous applications in a very wide area. I try to list a few below, consider them just samples, this is far from being comprehensive.

In pure mathematics CGT used as a kind of "experimental mathematics" tool. That is finding, enumerating, constructing certain (class of) mathematical objects.

* group theory (obviously)

* combinatorics

* graph theory

* design theory (combinatorial and statistical)

* finite projective geometries

* coding theory

* topology

* in general, where computing with automorphism group of the mathematical structure at hand may be of interest.

Theoretical computer science, in particular complexity theory. The main reason why computer scientist are interested in CGT is that the Graph Isomorphism problem is not known to be either in P or NP-complete and for a certain class of graphs the known polynomial graph-iso algorithm based on heavy CGT machinery.

Also many problems in CGT are undecidable, the best known ones are the word problem, the conjugacy problem and the isomorphism problem.

Here are some examples on the more applied side where CGT is heavily used.

* Statistics: the design of statistical experiences.

* Computational Chemistry

* Computational Biology (for example protein folding)

* Computational Pharmacology (Currently there is a trending news on HN about it titled "Virtual Pharmacology ...")

* Combinatorial Optimization

* Solving Constraint Satisfaction problems; the application of CGT here called "symmetry breaking".

* and as a further application of the two above: Robotics

* SAT/SMT solvers (came up here a few days ago)

* finding God's Number for the Rubik's cube is pure CGT

Finally, just to avoid the impression that CGT is so esoteric high level mathematics that it cannot be of interest for the working programmer. Any programmer who solved a combinatorial puzzle by finding all unique solutions but avoiding searching and listing the "basically same" ones more than once used and invented (!) a bit of CGT without noticing.

Reply on news.ycombinator.com