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$?
 A: 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.
A: You should look up the work on 'residual finiteness growth' (aka 'Farb growth') by Khalid Bou-Rabee and his coauthors.
