Finding an “optimal” quotient in a free group

Consider the abelian free group $G = \mathbf{Z}^n$ of rank $n$ and a finite subset $A \subset G \setminus \{0\}$. Since $G$ is residually finite, there is a subgroup $H \subset G$ such that $A \cap H = \emptyset$. Call such a subgroup optimal if it has minimal index in $G$.

Is there an efficient algorithm which computes an optimal subgroup $H$? By efficient I mean polynomial complexity in $n$ and $\mathrm{Card}\,A$.

What happens in the nonabelian case ($G$ is a nonabelian free group)? I think it should be more difficult. Is there at least an upper bound for the index of a normal subgroup $H$ such that $A \cap H = \emptyset$?

• You probably need something about $A$ itself. If $A$ is part of the input and $A$ contains a huge element (say of size $e^{e^n}$) while $card(A)\le n$, then the input is so big that asking the complexity to be polynomial is senseless. – YCor Mar 31 '16 at 22:50
• Note that the index of $H$ can be arbitrarily large even in the case where $n=1$ and $|A|=1$ (e.g. if $A = \{k!\}$), so some accounting for the size of the elements of $A$ is required. – Jim Belk Apr 1 '16 at 3:36
• Normally you want an algorithm to be polynomial in the size of the input. – Derek Holt Apr 1 '16 at 8:14
• @Jim Belk: you are right. But in most applications, the coordinates of the elements in $A$ are machine size integers. Call $B$ the matrix whose columns are the elements of $A$. Useful decompositions of $B \in M_{n,N}(\mathbb{Z})$, such as the Smith decomposition, can be achieved in $O(\max(n,N)^3 \log \|B\|_\infty)$. – vizietto Apr 1 '16 at 9:27

For abelian groups, you need to find a number $k$ with the property that at least one entry of each $a \in A$ is not divisible by $k$. In the simplest case, when $n=1$ and $A=\{m\}$ a prime of size roughly $\log|m|$ can be found -- this is a consequence of the prime number theorem. If $A=\{1,\dots,m\}$, something like $m+1$ is best possible, so it depends on the structure of the set $A$.

In general, the optimal $k$ (for a worst case $A$) will be of size $$\log({\rm lcm}(\{{\rm gcd}(a_1,\dots,a_n) \mid (a_1,\dots,a_n) \in A \})).$$

In the non-abelian case, the case $A=\{w\}$ has been studied and it is known that sometimes a quotient of size at least $n \log(n)^2$ is needed to detect $w$ of length $n$. This can be found in http://arxiv.org/abs/1508.07730. If you want to detect $A=\{w_1,w_2\}$, then this reduces to detecting $[w_1,w_2]$ (or some variation of this in case the commutator is trivial in the free group), so that one reduce (iterating this idea) the general case to the case of a single word.

An upper bound (in the non-abelian case) is $n^3$, since $SL(2,p)$ has size roughly $p^3$ and does not satisfy a law of length shorter than $p$. I believe that something like $n \log(n)^2$ should also be an upper bound, but this is an open problem.

• I don't see why detecting $\{w_1,w_2\}$ amounts to detecting $[w_1, w_2]$ – vizietto Apr 1 '16 at 17:43
• @vizietto: The only thing I wanted to say is that $[w_1,w_2] \in H$ if $w_1 \in H$ or $w_2 \in H$. – Andreas Thom Apr 2 '16 at 5:10
• @vizietto: Does that answer the question? – Andreas Thom Apr 20 '16 at 17:17

You should look up the work on 'residual finiteness growth' (aka 'Farb growth') by Khalid Bou-Rabee and his coauthors.