How to recover a permutation group amidst errors

Abstract

We consider the problem of recovering a permutation group $G\le S_n$ from an error-prone sampling process $X$. We model $X$ as an $S_n$-valued random variable, defined as a mixture of the uniform distributions on $G$ and $S_n$ . Our suite of tools recovers properties of $G$ from $X$ and bolsters our main method for recovering $G$ itself. Our algorithms are motivated by the numerical computation of monodromy groups, a setting where such error-prone sampling procedures occur organically.

31 pages, 14 Figures