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$?

  • 4
    $\begingroup$ 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. $\endgroup$ – YCor Mar 31 '16 at 22:50
  • 2
    $\begingroup$ 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. $\endgroup$ – Jim Belk Apr 1 '16 at 3:36
  • 4
    $\begingroup$ Normally you want an algorithm to be polynomial in the size of the input. $\endgroup$ – Derek Holt Apr 1 '16 at 8:14
  • $\begingroup$ @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)$. $\endgroup$ – 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.

  • $\begingroup$ I don't see why detecting $\{w_1,w_2\}$ amounts to detecting $[w_1, w_2]$ $\endgroup$ – vizietto Apr 1 '16 at 17:43
  • $\begingroup$ @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$. $\endgroup$ – Andreas Thom Apr 2 '16 at 5:10
  • $\begingroup$ @vizietto: Does that answer the question? $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.