9
$\begingroup$

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.


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(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] 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.
$\endgroup$

2 Answers 2

4
$\begingroup$

This question has been answered in CS.Theory Stack Exchange . Here I provide a brief summary of the discussion.

The answer to the problem is "yes".

  • First, there is a simple efficient classical algorithm for testing-membership in an abelian subgroup in the prescribed set-up [2]. In short, the algorithm is the following.

    Algorithm

    (a) Compute a generating-set of the orthogonal [1, 2] subgroup $H^{\perp}$ of $H$.

    (b) Check whether or not the element $b$ is orthogonal to $H^{\perp}$.

    The algorithm is correct since, by definition [1, 2], $b$ belongs to $H$ if and only if $\chi_{b}(g_i)=1$ for all generators of $H^{\perp}$.

    Moreover, there are efficient clasical algorithms to solve problems (a) and (b). The algorithm for (a) is based on Smith normal forms [1, 2]. (b) can be requires only evaluating the quantities $\chi_b(g_i)$ for all generators $g_i$ of the orthogonal [2]. Since there are a O(polylog($|G|$)) number of them and this can be done efficiently using modular arithmetic we are done .

  • 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}$ (cf. [2]). Tiny integers are exponentially small with the input size: $O(\log\log|A|)$.

Confer the original discusion for more details.

$\endgroup$
3
$\begingroup$

It seems there is an algorithm, implemented in Sage (for example). The following link is to a Sage worksheet with a small example. Please let me know if I've mis-interpreted the original question, but I believe this answers it.


Updated

Sorry about the link not working; I don't know what could be the issue. Here are the sage commands I found relating to your question.

G. = AbelianGroup(4, invfac=[3,5,9,45])

This creates the group $\mathbb{Z}/3 \mathbb{Z} \times \mathbb{Z}/5\mathbb{Z} \times \mathbb{Z}/9\mathbb{Z}\times \mathbb{Z}/45\mathbb{Z}$, with specified generators, $a, b, c, d$.

H = G.subgroup([a*b, c^3])

a*b in H

--returns true

a*b*c in H

--returns false.


I don't have the full details, but I know that sage uses the DHSW algorithm when computing SNF (reference: Dumas, Heckenbach, Saunders, Welker, “Computing simplicial homology based on efficient Smith normal form algorithms,” in “Algebra, geometry, and software systems” (2003), 177-206.) As I understand it, the time-complexity is polynomial.

$\endgroup$
7
  • $\begingroup$ Sorry if the link got corrupted, but this is a script right? Maybe I was not clear, but I am trying to see wheter or not the worst-cse time computational complexity is polynomial (in a classical computer). So I am looking for a proof that some procedure, like the one I explain in the easy case, works or, otherwise, that the problem is hard. So, maybe I should rephrase my question as, are this type of problems efficiently solvable with: * Smith normal forms? * Integer gaussian elimination? * Something else? Thanks for your help. $\endgroup$ Nov 19, 2011 at 12:48
  • $\begingroup$ And thanks you a lot for your help :) $\endgroup$ Nov 19, 2011 at 13:32
  • $\begingroup$ I've updated the posted solution. Hope this helps! :) $\endgroup$
    – Shaun Ault
    Nov 19, 2011 at 18:33
  • $\begingroup$ Also, concerning the transformation matrices, $U$, and $V$, such that $D = UAV$, this is an open area of research, and there do not seem to be efficient algorithms for finding them in general. The DHSW algorithm uses modular arithmetic, hence losing info needed to reconstruct $U$ and $V$. On the other hand, the straightforward non-destructive algorithms experience integer-blowup. $\endgroup$
    – Shaun Ault
    Nov 19, 2011 at 18:38
  • $\begingroup$ You have a point there, I think these difficulties are hard to avoid. $\endgroup$ Nov 19, 2011 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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