6
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 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
    Commented Mar 31, 2016 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
    Commented Apr 1, 2016 at 3:36
  • 4
    $\begingroup$ Normally you want an algorithm to be polynomial in the size of the input. $\endgroup$
    – Derek Holt
    Commented Apr 1, 2016 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
    Commented Apr 1, 2016 at 9:27

2 Answers 2

Reset to default
2
$\begingroup$

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.

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

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .