<p>After some time, I managed to find a perhaps not-optimal but simple algorithm that proves that the complexity of the problem is polynomial. </p>

<blockquote>
  <p><strong>Algorithm</strong></p>
  
  <p>(a) Compute a generating-set of the orthogonal subgroup $H^{\perp}$ of $H$. </p>
  
  <p>(b) Check whether or not the element $b$ is orthogonal to $H^{\perp}$. </p>
</blockquote>

<p>There are efficient clasical algorithms for problems (a) and (b) (see analysis below). This gives an efficient membership-test since an element $b$ is orthogonal to $H^\perp$ if and only if $h\in H$.</p>

<hr>

<p><strong>Analysis</strong></p>

<p>The orthogonal subgroup  $H^{\perp}$ is defined via the character group of $G$ as:
$$H^{\perp}:= \{g\in G : \chi_g(h)=1\quad \forall h\in H \}$$
Main properties:</p>

<ol>
<li>$H^{\perp}$ is a subgroup of $G$.</li>
<li>$H^{\perp^\perp}=H$</li>
</ol>

<p>Algorithm for <strong>(a)</strong>:</p>

<p>I follow an algorithm from [<a href="http://arxiv.org/abs/quant-ph/0411037" rel="nofollow">1</a>] with minor variations. $g$ belongs to $H^{\perp}$ if and only if $\chi_{g}(h)=1$ for all $h\in H$, but, by linearity it is enough to show $\chi_{b}(h_i)=1$ for each generator of $H$. Expanding the character in terms of exponentials (here I implicitly use the cyclic factor decomposition) this condition is equivalent to
\begin{eqnarray}
\exp \left\lbrace 2\pi i \left( \frac{g(1)h_{i}(1)}{d_1}+\ldots + \frac{g(m) h_{i}(m)}{d_m} \right) \right\rbrace=1
\end{eqnarray}
To solve these equations, compute $M:= \text{lcm}(N_1,\ldots,N_d)$ using the Euclidean algorithm and the numbers $\alpha_i:=M/d_i$.   We can re-write the conditions above for every $i$ as a system of linear modular equations.</p>

<p>$$
\begin{pmatrix}
\alpha_1 h_1(1) &amp; \alpha_2 h_1(2) &amp; \ldots &amp; \alpha_m h_1(m)\\
\alpha_1 h_2(1) &amp; \alpha_2 h_2(2) &amp; \ldots &amp; \alpha_m h_2(m)\\
\vdots &amp; \vdots &amp; \cdots &amp; \vdots\\
\alpha_1 h_n(1) &amp; \alpha_2 h_n(2) &amp; \ldots &amp; \alpha_m h_n(m)
\end{pmatrix}
\begin{pmatrix}
g(1)\\
g(2)\\
\vdots\\
g(n)
\end{pmatrix}
=
\begin{pmatrix}
0 \\
0 \\
\vdots\\
0
\end{pmatrix}
\begin{matrix}
\mod M\\
\mod M\\
\vdots\\
\mod M
\end{matrix}
$$
As it is proven in <a href="http://arxiv.org/abs/quant-ph/0411037" rel="nofollow">1</a>, if we sample $t+\lceil\log|G|\rceil$ random solutions of this system of equations we will obtain a generating set of $H^{\perp}$ with probability exponentially close to one $p\geq 1 -1/2^{t}$. Now to sample from this equations write them in matrix form $AX=0 \pmod M$. Here $A$ is a rectangular matrix over the integers modulo $M$ for which an algorithm given in <a href="http://www.cs.uwaterloo.ca/research/tr/1996/03/CS-96-03.pdf" rel="nofollow">2</a> allows to efficiently compute its Smith normal decomposition. The algorithm returns a diagonal matrix $D$ and two invertible matrices $U$, $V$ such that $D=UAV$. Using this formula the system of equations can be written as $DY=0 \pmod M$ with $X=VY$. Now it is possible to randomly compute solutions of $DY=0\pmod M$ using Euclid's algorithm, since this is a system of equations of the form $d_i y_i =0 \pmod M$. Finally, computing $X=VY$ one obtains a random element of the orthogonal group $H^{\perp}$ as desired.</p>

<p>Algorithm for <strong>(b)</strong>:</p>

<p>Since we already know how to compute a generating-set of $H^{\perp}$, it is easy to check if a given element $b$ belongs to $H$. First compute a generating-set $\langle g_1,\ldots, g_s \rangle$ of $H^{\perp}$. Then, by definition, $b$ belongs to $H$ if and only if $\chi_{b}(g_i)=1$ for all generators of $H^{\perp}$. Since there are a O(polylog($|G|$)) number of them and  this can be done efficiently using modular arithmetic we are done.</p>

CC BY-SA 3.0
2011-11-20T06:02:46.903Z
it's fine to add your own answer if you've made discoveries in the mean time. However, it seems like you need to do some more investigation (based on your comment) before you decide which answer to accept.
Suresh Venkat
CC BY-SA 3.0
2011-11-20T14:10:11.753Z
Thanks. I would like to keep the discussion further to see if we put everything into one picture. Also, I think there could be a more practical algorithm that could pop-up.
Juan Bermejo Vega
CC BY-SA 3.0
2011-11-20T03:16:21.277Z
2012-02-15T15:37:37.223Z
2012-02-15T15:37:37.223Z
Juan Bermejo Vega
<p>Verifying whether $b \in \langle h_1, \ldots, h_n\rangle$ (where $h_i$ are vectors according to the OP's comments) is equivalent to verifying whether there is a solution to this system:
$$
\begin{pmatrix}
h_{1}(1) &amp; \cdots &amp; h_{n}(1) &amp; d_1^{e_1}      &amp; 0 &amp; \cdots &amp; 0 \\\\
\vdots  &amp; \ddots &amp; \vdots  &amp; \vdots &amp; \vdots  &amp; \vdots &amp; \vdots  \\\\
h_{1}(m) &amp; \cdots &amp; h_{n}(m) &amp; 0      &amp; 0 &amp; \cdots &amp; d_m^{e_N}
\end{pmatrix}
\begin{pmatrix}
x(1) \\\\
\vdots \\\\
x(n) \\\\
y(1) \\\\
\vdots \\\\
y(m)
\end{pmatrix}
\equiv
\begin{pmatrix}
b(1) \\\\
\vdots \\\\
b(m)
\end{pmatrix}
$$</p>

<p>In your case $e_1, \ldots, e_N$ are tiny numbers (ie. their value is logartihmic in the input size). Unfortunately, it doesn't seem like we can assume that $d_1, \ldots, d_n$ are tiny.</p>

<p>If they are, then you can find a solution to the system in $\text{NC}^3$ from a result of McKenzie &amp; Cook <a href="http://dl.acm.org/citation.cfm?id=33386" rel="nofollow">[1]</a>. This paper shows that solving linear congruences modulo an integer with tiny factors (LCON) is in $\text{NC}^3$. Moreover, this problem is $\text{NC}^1$-equivalent to the abelian permutation group membership problem (AGM). McKenzie's doctoral thesis is fully devoted to those problems <a href="http://books.google.ca/books/about/Parallel_complexity_and_permutation_grou.html?id=P1BmtwAACAAJ" rel="nofollow">[1]</a>. More recently, those problems were considered by Arvind &amp; Vijayaraghavan <a href="http://dl.acm.org/citation.cfm?id=1746281" rel="nofollow">[3]</a>.</p>

<p><a href="http://dl.acm.org/citation.cfm?id=33386" rel="nofollow">[1]</a> Pierre McKenzie &amp; Stephen A. Cook. The parallel complexity of Abelian permutation group problems. 1987.</p>

<p><a href="http://books.google.ca/books/about/Parallel_complexity_and_permutation_grou.html?id=P1BmtwAACAAJ" rel="nofollow">[2]</a> Pierre McKenzie. Parallel complexity and permutation groups. 1984.</p>

<p><a href="http://dl.acm.org/citation.cfm?id=1746281" rel="nofollow">[3]</a> V. Arvind &amp; T. C. Vijayaraghavan. Classifying Problems on Linear Congruences and Abelian Permutation Groups Using Logspace Counting Classes. 2010.</p>

CC BY-SA 3.0
2011-11-19T17:44:49.630Z
Thanks, unfortunatley I have no access to this papers until Monday. It surprises me that this works for any abelian group. For $Z_N^*$, which is abelian, determining wether $b$ belongs to $\langle a \rangle$ involves deciding wether $b=a^i\mod \varphi(N)$ has a solution. I see two problems here: 1) Classically it is hard to compute the Euler totient function 2) Its the decision version of a discrete logarithm. The problem reduces to solving modular equations if the cyclic decomposition is given. How do you go around this problem? Am I missing something important here?
Juan Bermejo Vega
CC BY-SA 3.0
2011-11-19T18:29:43.233Z
Actually, it's for any abelian *permutation* group.
Michael Blondin
CC BY-SA 3.0
2011-11-19T19:45:27.857Z
I will take a look at these papers and try to organise everything a bit. Thanks.
Juan Bermejo Vega
CC BY-SA 3.0
2011-11-20T21:19:47.583Z
Could you provide more details on the encoding of the input? This way, I might be able to improve my answer.
Michael Blondin
CC BY-SA 3.0
2011-11-20T23:33:31.747Z
The group decomposition $A=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_N}$ as input (these would be a string with several numbers and the length I guess). Then, each element of the group is of the form $(g_1,\ldots,g_n)$ and can be represented by a tuple of numbers. To store it you need $n:= \lceil log_2 |A|\rceil$ bits. Does this answer it?
Juan Bermejo Vega
CC BY-SA 3.0
2011-11-22T18:03:42.510Z
Can you assume that the $d_i$s are written in unary (i.e. are $d_i$s tiny?, i.e. much smaller than the input size)?
Michael Blondin
CC BY-SA 3.0
2011-11-22T20:22:13.587Z
The $d_i$s can be arbitrarily big. In some cases they could be much smaller than the order of $A$ like $A:=\mathbb{Z}_2^n$ but they can also be comparable to the order of $A$, like $A:=\mathbb{Z}_N$.

Apparently there are algorithms to deal with this systems treating them either as linear-systems of diophantine equations or using smith normal forms. We are looking for a good reference, as soon as we have it I will post it.
Juan Bermejo Vega
CC BY-SA 3.0
2011-11-22T21:35:49.800Z
I've updated my answer. You mentioned earlier those group membership problems to arise from quantum computing problems. You might want to verify whether the $d_i$s are tiny given the input of those problems.
Michael Blondin
CC BY-SA 3.0
2011-11-22T23:43:17.300Z
In quantum computation you consider arbitrary abelian groups, thus, the decomposition can be anything. It is very interesting however that for small $d_i$s the complexity is quite low.

I am pretty sure that the general case is in P or BPP anyway. I will try to update my answer as well and maybe we can learn something about the differences between big and small $d_i$s.

I want to thank you personally for your effort and interest.
Juan Bermejo Vega
CC BY-SA 3.0
2011-11-19T16:32:04.560Z
2012-02-15T14:57:52.233Z
2012-02-15T14:57:52.233Z
Michael Blondin
<p>Consider the following abelian-subgroup membership-testing <strong>problem</strong>.</p>

<blockquote>
  <p><strong>Inputs:</strong></p>
  
  <ol>
  <li><p>A finite abelian group $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ with arbitrary-large $d_i$.</p></li>
  <li><p>A generating-set $\lbrace h_1,\ldots,h_n\rbrace$ of a subgroup $H\subset G$.</p></li>
  <li><p>An element $b\in G$.</p></li>
  </ol>
  
  <p><strong>Output:</strong> 'yes' if $b\in H$ and 'no' elsewhere'.</p>
</blockquote>

<p><strong>Question:</strong> Can this problem be solved <em>efficiently</em> in a classical computer? I consider an algorithm efficient if it uses $O(\text{polylog}|G|)$ time and memory resources in the usual sense of classical Turing machines. Notice that we can assume $n= O(\log|G|)$ for any subgroup $H$. The <em>input-size</em> of this problem is $\lceil \log|G|\rceil$.</p>

<p><strong>A bit of motivation</strong>. Intuitively it looks like the problem can be tackled with algorithms to solve linear systems of congruences or linear diophantine equations (read below). However, it seems that there are different notions of computational efficiency used in the context of computations with integers, such as: strongly versus weakly polynomial time, algebraic versus bit complexity. I am not an expert on these definitions and I can not find a reference that clearly settles down this question.</p>

<blockquote>
  <p><strong>Update:</strong> the answer to the problem is "yes".</p>
  
  <ul>
  <li><p>In a late answer, I proposed a method based on Smith normal forms which is efficient for any group with the prescribed form.</p></li>
  <li><p>An answer by Blondin shows that in the particular case where all $d_i$ are of the form $d_i= N_i^{e_i}$ and $N_i, e_i$ are "tiny integers" then the problem belongs to $\text{NC}^3\subset \text{P}$. Tiny integers are exponentially small with the input size: $O(\log\log|A|)$.</p></li>
  </ul>
  
  <p>In my answer I used "orthogonal subgroups" to solve this problem, but I believe this is not necessary. I will try to provide a more direct answer in the future based a row Echelon forms method I am reading.</p>
</blockquote>

<hr>

<h2>Some possible approaches</h2>

<p>The problem is closely related to solving linear system of congruences and/or linear diophantine equations. I briefly summarise these connection for the sake of completion.</p>

<p>Take $A$ to be the matrix whose columns are the elements of the generating set  $\lbrace h_1, \ldots, h_n \rbrace$. The following system of equations</p>

<p>$$
Ax^{T}=
\begin{pmatrix}
h_1(1) &amp; h_2(1) &amp; \ldots &amp; h_n(1)\\
h_1(2) &amp; h_2(2) &amp; \ldots &amp; h_n(2)\\
\vdots &amp; \vdots &amp; \cdots &amp; \vdots\\
h_1(m) &amp; h_2(m) &amp; \ldots &amp; h_n(m)
\end{pmatrix}

\begin{pmatrix}
x(1)\\
x(2)\\
\vdots\\
x(n)
\end{pmatrix}
=
\begin{pmatrix}
b(1) \\
b(2) \\
\vdots\\
b(m)
\end{pmatrix}
\begin{matrix}
\mod d_1\\
\mod d_2\\
\vdots\\
\mod d_m
\end{matrix}
$$</p>

<p>has a solution if and only if $b\in H$.</p>

<p>If all cyclic factors have the same dimension $d=d_i$ there is an algorithm based on Smith normal forms that solves the problem in polynomial time. In this case, an efficient algorithm from <a href="http://www.cs.uwaterloo.ca/research/tr/1996/03/CS-96-03.pdf" rel="nofollow"> [1] </a> 
finds the Smith normal form of  $A$: it returns a diagonal matrix $D$ and two invertible matrices $U$ and $V$ such that $D=UAV$. This reduced the problem to solving the equivalent system system $DY=Ub \mod d$ with $D$ diagonal. We can decide efficiently if the system has a solution using the Euclidean algorithm.</p>

<p>The above example suggest that the problem can be solved efficiently using similar techniques in the general case. We can try to solve the system doing modular operations, or by turning the system into a larger system of linear diophantine equations. Some possible techniques to approach the problem that I can think of are:</p>

<ol>
<li>Computing the Smith normal forms of $A$.</li>
<li>Computing the row Echelon form of $A$.</li>
<li>Integer Gaussian elimination.</li>
</ol>

CC BY-SA 3.0
2011-11-19T07:09:30.950Z
simultaneously crossposted on MO: http://mathoverflow.net/questions/81300/check-membership-in-an-abelian-subgroup-using-smith-normal-forms
Suresh Venkat
CC BY-SA 3.0
2011-11-19T07:10:24.273Z
It appears that you have crossposted this question *simultaneously*. While we don't mind a question being **reposted**, our [site policy](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231) is to permit a repost only after sufficient time has passed and you did not obtain the desired answer elsewhere, because simultaneous crossposting duplicates effort and fractures discussion. You may flag this question for closing now, and then reflag it for opening if necessary after summarizing relevant discussions from other sites.
Suresh Venkat
CC BY-SA 3.0
2011-11-19T12:32:23.773Z
Sorry, I did not know about this policy. I will close this section and redirect to MO.
Juan Bermejo Vega
CC BY-SA 3.0
2011-11-19T16:39:44.763Z
Closed at request of original poster (due to duplication on MO).
Dave Clarke
CC BY-SA 3.0
2011-11-19T16:43:51.603Z
I posted an answer before the post was closed. In my opinion, the question is better suited here than on mathoverflow since it was extensively studied in the complexity theory literature.
Michael Blondin
CC BY-SA 3.0
2011-11-19T21:51:57.503Z
reopened at OP request; focus on complexity makes it the right fit for here.
Suresh Venkat
CC BY-SA 3.0
2011-11-23T04:01:13.713Z
[Chapter 10](http://cs.nyu.edu/~yap/book/alge/ftpSite/l10.ps.gz) of Chee Yap's ["Fundamental Problems of Algorithmic Algebra"](http://www.amazon.com/Fundamental-Problems-Algorithmic-Algebra-Chee/dp/0195125169/ref=sr_1_1?ie=UTF8&qid=1322020801&sr=8-1) (also available [here](http://cs.nyu.edu/~yap/book/alge/ftpSite/)) gives a polynomial time algorithm to find the Smith Normal Form and it's decomposition.
user834
<ds.algorithms><time-complexity><matrices><nt.number-theory><gr.group-theory>
Complexity of Membership-Testing for finite abelian groups
Juan Bermejo Vega
# Complexity of Membership-Testing for finite abelian groups

(Asked by: username_0 on 2011-11-19)

Consider the following abelian-subgroup membership-testing **problem**.

> **Inputs:**
>
> 1. A finite abelian group $G=\mathbb{Z}\_{d\_1}\times\mathbb{Z}\_{d\_1}\ldots\times\mathbb{Z}\_{d\_m}$ with arbitrary-large $d\_i$.
> 2. A generating-set $\lbrace h\_1,\ldots,h\_n\rbrace$ of a subgroup $H\subset G$.
> 3. An element $b\in G$.
>
> **Output:** 'yes' if $b\in H$ and 'no' elsewhere'.

**Question:** Can this problem be solved *efficiently* in a classical computer? I consider an algorithm efficient if it uses $O(\text{polylog}|G|)$ time and memory resources in the usual sense of classical Turing machines. Notice that we can assume $n= O(\log|G|)$ for any subgroup $H$. The *input-size* of this problem is $\lceil \log|G|\rceil$.

**A bit of motivation**. Intuitively it looks like the problem can be tackled with algorithms to solve linear systems of congruences or linear diophantine equations (read below). However, it seems that there are different notions of computational efficiency used in the context of computations with integers, such as: strongly versus weakly polynomial time, algebraic versus bit complexity. I am not an expert on these definitions and I can not find a reference that clearly settles down this question.

> **Update:** the answer to the problem is "yes".
>
> * In a late answer, I proposed a method based on Smith normal forms which is efficient for any group with the prescribed form.
> * An answer by Blondin shows that in the particular case where all $d\_i$ are of the form $d\_i= N\_i^{e\_i}$ and $N\_i, e\_i$ are "tiny integers" then the problem belongs to $\text{NC}^3\subset \text{P}$. Tiny integers are exponentially small with the input size: $O(\log\log|A|)$.
>
> In my answer I used "orthogonal subgroups" to solve this problem, but I believe this is not necessary. I will try to provide a more direct answer in the future based a row Echelon forms method I am reading.

---

## Some possible approaches

The problem is closely related to solving linear system of congruences and/or linear diophantine equations. I briefly summarise these connection for the sake of completion.

Take $A$ to be the matrix whose columns are the elements of the generating set $\lbrace h\_1, \ldots, h\_n \rbrace$. The following system of equations

$$
Ax^{T}=
\begin{pmatrix}
h\_1(1) & h\_2(1) & \ldots & h\_n(1)\\
h\_1(2) & h\_2(2) & \ldots & h\_n(2)\\
\vdots & \vdots & \cdots & \vdots\\
h\_1(m) & h\_2(m) & \ldots & h\_n(m)
\end{pmatrix}
\begin{pmatrix}
x(1)\\
x(2)\\
\vdots\\
x(n)
\end{pmatrix}
=
\begin{pmatrix}
b(1) \\
b(2) \\
\vdots\\
b(m)
\end{pmatrix}
\begin{matrix}
\mod d\_1\\
\mod d\_2\\
\vdots\\
\mod d\_m
\end{matrix}
$$

has a solution if and only if $b\in H$.

If all cyclic factors have the same dimension $d=d\_i$ there is an algorithm based on Smith normal forms that solves the problem in polynomial time. In this case, an efficient algorithm from  [[1]](http://www.cs.uwaterloo.ca/research/tr/1996/03/CS-96-03.pdf) 
finds the Smith normal form of $A$: it returns a diagonal matrix $D$ and two invertible matrices $U$ and $V$ such that $D=UAV$. This reduced the problem to solving the equivalent system system $DY=Ub \mod d$ with $D$ diagonal. We can decide efficiently if the system has a solution using the Euclidean algorithm.

The above example suggest that the problem can be solved efficiently using similar techniques in the general case. We can try to solve the system doing modular operations, or by turning the system into a larger system of linear diophantine equations. Some possible techniques to approach the problem that I can think of are:

1. Computing the Smith normal forms of $A$.
2. Computing the row Echelon form of $A$.
3. Integer Gaussian elimination.

**Tags:** ds.algorithms, time-complexity, matrices, nt.number-theory, gr.group-theory

> **Comments:**
> **username_1**: simultaneously crossposted on MO: http://mathoverflow.net/questions/81300/check-membership-in-an-abelian-subgroup-using-smith-normal-forms  
> **username_1**: It appears that you have crossposted this question *simultaneously*. While we don't mind a question being **reposted**, our [site policy](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231) is to permit a repost only after sufficient time has passed and you did not obtain the desired answer elsewhere, because simultaneous crossposting duplicates effort and fractures discussion. You may flag this question for closing now, and then reflag it for opening if necessary after summarizing relevant discussions from other sites.  
> **username_0**: Sorry, I did not know about this policy. I will close this section and redirect to MO.  
> **username_2**: Closed at request of original poster (due to duplication on MO).  
> **username_3**: I posted an answer before the post was closed. In my opinion, the question is better suited here than on mathoverflow since it was extensively studied in the complexity theory literature.  
> **username_1**: reopened at OP request; focus on complexity makes it the right fit for here.  
> **username_4**: [Chapter 10](http://cs.nyu.edu/~yap/book/alge/ftpSite/l10.ps.gz) of Chee Yap's ["Fundamental Problems of Algorithmic Algebra"](http://www.amazon.com/Fundamental-Problems-Algorithmic-Algebra-Chee/dp/0195125169/ref=sr_1_1?ie=UTF8&qid=1322020801&sr=8-1) (also available [here](http://cs.nyu.edu/~yap/book/alge/ftpSite/)) gives a polynomial time algorithm to find the Smith Normal Form and it's decomposition.  

---

## 2 answers

### Answer by username_0 on 2011-11-20. Score: 4 | Accepted answer

After some time, I managed to find a perhaps not-optimal but simple algorithm that proves that the complexity of the problem is polynomial.

> **Algorithm**
>
> (a) Compute a generating-set of the orthogonal subgroup $H^{\perp}$ of $H$.
>
> (b) Check whether or not the element $b$ is orthogonal to $H^{\perp}$.

There are efficient clasical algorithms for problems (a) and (b) (see analysis below). This gives an efficient membership-test since an element $b$ is orthogonal to $H^\perp$ if and only if $h\in H$.

---

**Analysis**

The orthogonal subgroup $H^{\perp}$ is defined via the character group of $G$ as:
$$H^{\perp}:= \{g\in G : \chi\_g(h)=1\quad \forall h\in H \}$$
Main properties:

1. $H^{\perp}$ is a subgroup of $G$.
2. $H^{\perp^\perp}=H$

Algorithm for **(a)**:

I follow an algorithm from [[1](http://arxiv.org/abs/quant-ph/0411037)] with minor variations. $g$ belongs to $H^{\perp}$ if and only if $\chi\_{g}(h)=1$ for all $h\in H$, but, by linearity it is enough to show $\chi\_{b}(h\_i)=1$ for each generator of $H$. Expanding the character in terms of exponentials (here I implicitly use the cyclic factor decomposition) this condition is equivalent to
\begin{eqnarray}
\exp \left\lbrace 2\pi i \left( \frac{g(1)h\_{i}(1)}{d\_1}+\ldots + \frac{g(m) h\_{i}(m)}{d\_m} \right) \right\rbrace=1
\end{eqnarray}
To solve these equations, compute $M:= \text{lcm}(N\_1,\ldots,N\_d)$ using the Euclidean algorithm and the numbers $\alpha\_i:=M/d\_i$. We can re-write the conditions above for every $i$ as a system of linear modular equations.

$$
\begin{pmatrix}
\alpha\_1 h\_1(1) & \alpha\_2 h\_1(2) & \ldots & \alpha\_m h\_1(m)\\
\alpha\_1 h\_2(1) & \alpha\_2 h\_2(2) & \ldots & \alpha\_m h\_2(m)\\
\vdots & \vdots & \cdots & \vdots\\
\alpha\_1 h\_n(1) & \alpha\_2 h\_n(2) & \ldots & \alpha\_m h\_n(m)
\end{pmatrix}
\begin{pmatrix}
g(1)\\
g(2)\\
\vdots\\
g(n)
\end{pmatrix}
=
\begin{pmatrix}
0 \\
0 \\
\vdots\\
0
\end{pmatrix}
\begin{matrix}
\mod M\\
\mod M\\
\vdots\\
\mod M
\end{matrix}
$$
As it is proven in [1](http://arxiv.org/abs/quant-ph/0411037), if we sample $t+\lceil\log|G|\rceil$ random solutions of this system of equations we will obtain a generating set of $H^{\perp}$ with probability exponentially close to one $p\geq 1 -1/2^{t}$. Now to sample from this equations write them in matrix form $AX=0 \pmod M$. Here $A$ is a rectangular matrix over the integers modulo $M$ for which an algorithm given in [2](http://www.cs.uwaterloo.ca/research/tr/1996/03/CS-96-03.pdf) allows to efficiently compute its Smith normal decomposition. The algorithm returns a diagonal matrix $D$ and two invertible matrices $U$, $V$ such that $D=UAV$. Using this formula the system of equations can be written as $DY=0 \pmod M$ with $X=VY$. Now it is possible to randomly compute solutions of $DY=0\pmod M$ using Euclid's algorithm, since this is a system of equations of the form $d\_i y\_i =0 \pmod M$. Finally, computing $X=VY$ one obtains a random element of the orthogonal group $H^{\perp}$ as desired.

Algorithm for **(b)**:

Since we already know how to compute a generating-set of $H^{\perp}$, it is easy to check if a given element $b$ belongs to $H$. First compute a generating-set $\langle g\_1,\ldots, g\_s \rangle$ of $H^{\perp}$. Then, by definition, $b$ belongs to $H$ if and only if $\chi\_{b}(g\_i)=1$ for all generators of $H^{\perp}$. Since there are a O(polylog($|G|$)) number of them and this can be done efficiently using modular arithmetic we are done.

> **Comments:**
> **username_1**: it's fine to add your own answer if you've made discoveries in the mean time. However, it seems like you need to do some more investigation (based on your comment) before you decide which answer to accept.  
> **username_0**: Thanks. I would like to keep the discussion further to see if we put everything into one picture. Also, I think there could be a more practical algorithm that could pop-up.  

---

### Answer by username_3 on 2011-11-19. Score: 10

Verifying whether $b \in \langle h\_1, \ldots, h\_n\rangle$ (where $h\_i$ are vectors according to the OP's comments) is equivalent to verifying whether there is a solution to this system:
$$
\begin{pmatrix}
h\_{1}(1) & \cdots & h\_{n}(1) & d\_1^{e\_1} & 0 & \cdots & 0 \\\\
\vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \vdots \\\\
h\_{1}(m) & \cdots & h\_{n}(m) & 0 & 0 & \cdots & d\_m^{e\_N}
\end{pmatrix}
\begin{pmatrix}
x(1) \\\\
\vdots \\\\
x(n) \\\\
y(1) \\\\
\vdots \\\\
y(m)
\end{pmatrix}
\equiv
\begin{pmatrix}
b(1) \\\\
\vdots \\\\
b(m)
\end{pmatrix}
$$

In your case $e\_1, \ldots, e\_N$ are tiny numbers (ie. their value is logartihmic in the input size). Unfortunately, it doesn't seem like we can assume that $d\_1, \ldots, d\_n$ are tiny.

If they are, then you can find a solution to the system in $\text{NC}^3$ from a result of McKenzie & Cook [[1]](http://dl.acm.org/citation.cfm?id=33386). This paper shows that solving linear congruences modulo an integer with tiny factors (LCON) is in $\text{NC}^3$. Moreover, this problem is $\text{NC}^1$-equivalent to the abelian permutation group membership problem (AGM). McKenzie's doctoral thesis is fully devoted to those problems [[1]](http://books.google.ca/books/about/Parallel_complexity_and_permutation_grou.html?id=P1BmtwAACAAJ). More recently, those problems were considered by Arvind & Vijayaraghavan [[3]](http://dl.acm.org/citation.cfm?id=1746281).

[[1]](http://dl.acm.org/citation.cfm?id=33386) Pierre McKenzie & Stephen A. Cook. The parallel complexity of Abelian permutation group problems. 1987.

[[2]](http://books.google.ca/books/about/Parallel_complexity_and_permutation_grou.html?id=P1BmtwAACAAJ) Pierre McKenzie. Parallel complexity and permutation groups. 1984.

[[3]](http://dl.acm.org/citation.cfm?id=1746281) V. Arvind & T. C. Vijayaraghavan. Classifying Problems on Linear Congruences and Abelian Permutation Groups Using Logspace Counting Classes. 2010.

> **Comments:**
> **username_0**: Thanks, unfortunatley I have no access to this papers until Monday. It surprises me that this works for any abelian group. For $Z_N^*$, which is abelian, determining wether $b$ belongs to $\langle a \rangle$ involves deciding wether $b=a^i\mod \varphi(N)$ has a solution. I see two problems here: 1) Classically it is hard to compute the Euler totient function 2) Its the decision version of a discrete logarithm. The problem reduces to solving modular equations if the cyclic decomposition is given. How do you go around this problem? Am I missing something important here?  
> **username_3**: Actually, it's for any abelian *permutation* group.  
> **username_0**: I will take a look at these papers and try to organise everything a bit. Thanks.  
> **username_3**: Could you provide more details on the encoding of the input? This way, I might be able to improve my answer.  
> **username_0**: The group decomposition $A=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_N}$ as input (these would be a string with several numbers and the length I guess). Then, each element of the group is of the form $(g_1,\ldots,g_n)$ and can be represented by a tuple of numbers. To store it you need $n:= \lceil log_2 |A|\rceil$ bits. Does this answer it?  
> **username_3**: Can you assume that the $d_i$s are written in unary (i.e. are $d_i$s tiny?, i.e. much smaller than the input size)?  
> **username_0**: The $d_i$s can be arbitrarily big. In some cases they could be much smaller than the order of $A$ like $A:=\mathbb{Z}_2^n$ but they can also be comparable to the order of $A$, like $A:=\mathbb{Z}_N$.  Apparently there are algorithms to deal with this systems treating them either as linear-systems of diophantine equations or using smith normal forms. We are looking for a good reference, as soon as we have it I will post it.  
> **username_3**: I've updated my answer. You mentioned earlier those group membership problems to arise from quantum computing problems. You might want to verify whether the $d_i$s are tiny given the input of those problems.  
> **username_0**: In quantum computation you consider arbitrary abelian groups, thus, the decomposition can be anything. It is very interesting however that for small $d_i$s the complexity is quite low.  I am pretty sure that the general case is in P or BPP anyway. I will try to update my answer as well and maybe we can learn something about the differences between big and small $d_i$s.  I want to thank you personally for your effort and interest.  

---

