Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #2 to TR07-052 | 21st April 2008 00:00

#### Linear and Sublinear Time Algorithms for the Basis of Abelian Groups Revision of: TR07-052 Abstract:=09It is well known that every finite abelian group G can be=20 represented as a direct product of cyclic groups: G\cong G_1\times=20 G_2\times \cdots \times G_t, where each G_i is a cyclic group of=20 order p^j for some prime p and integer j\ge 1.=20 If a_i generates the cyclic group of G_i, i=3D1,2,\cdots, t,=20 then the elements a_1,a_2,\cdots, a_t are called a basis of G. We show an= =20 a

Revision #2
Authors: Li, Chen, Fu, Ye Bin
Accepted on: 21st April 2008 00:00
Keywords:

Abstract:

Revision #1 to TR07-052 | 7th October 2007 00:00

#### Linear and Sublinear Time Algorithms for the Basis of Abelian Groups Revision of: TR07-052

Revision #1
Authors: Li Chen, Bin Fu
Accepted on: 7th October 2007 00:00
Keywords:

Abstract:

It is well known that every finite Abelian group $G$ can be
represented
as a direct product of cyclic groups: $G=G_1\circ G_2\circ\cdots \circ G_t$, where
each $G_i$ is a cyclic group of size $p^j$ for some prime $p$ and integer
$j\ge 1$.
If $a_i$ is the generator of the cyclic group of $G_i$, $i=1,2,\cdots, t$,
then the
elements a_1,a_2,\cdots, a_t$are called a basis of$G$. In this paper, we first obtain an$O(n)$-time deterministic algorithm for computing the basis of an Abelian group with$n$elements. The existing algorithms need$O(n^2)$time by Chen and$O(n^{1.5})$time by Buchmann and Schmidt. We then derive an$O((\sum_{i=1}^k _i^{n_i/2}n_i^2)(\log n)\log\log
n)$-time randomized algorithm to compute the basis of Abelian group$G$of size$n$with factorization$n=p_1^{n_1}\cdots p_t^{n_t}$, which is also a part of the input. It implies an$O(n^{1/2}(\log n)^3\log\log n)$-time randomized algorithm to compute the basis of an Abelian group$G$of size$n$. It also implies that if$n$is an integer in$\{1,2, \cdots, m\}-G(m,c)$, then the basis of an Abelian group of size$n$can be computed in$O((\log n)^{{c\over 2}+3}\log\log n)$-time, where$c$is any positive constant and$G(m,c)$is a subset of the small fraction of integers in$\{1,2,
\cdots, m\}$with${|G(m,c)|\over m}=O({1\over (\log m)^{c/2}})$for every integer$m$. ### Paper: TR07-052 | 7th May 2007 00:00 #### Linear and Sublinear Time Algorithms for the Basis of Abelian Groups TR07-052 Authors: Li Chen, Bin Fu Publication: 16th June 2007 19:32 Downloads: 2738 Keywords: Abstract: It is well known that every finite Abelian group$G$can be represented as a product of cyclic groups:$G=G_1\times
G_2\times\cdots G_t$, where each$G_i$is a cyclic group of size$p^j$for some prime$p$and integer$j\ge 1$. If$a_i$is the generator of the cyclic group of$G_i$,$i=1,2,\cdots, t$, then the elements$a_1,a_2,\cdots, a_t$are the basis of$G$. In this paper, we first obtain an$O(n)$-time deterministic algorithm for computing the basis of an Abelian group with$n$elements. This improves the previous$O(n^2)$time algorithm found by Chen. We then derive an$O((\sum_{i=1}^t p_i^{n_i-1}n_i^2\log p_i)(\log n)(\log\log n))$-time randomized algorithm to compute the basis of Abelian group$G$of size$n$with factorization$n=p_1^{n_1}\cdots p_k^{n_t}$, which is also a part of the input. This shows that for a large number of cases, the basis of a finite Abelian group can be computed in sublinear time. For example, it implies an$O(n^{1-{1\over d}}(\log n)^3\log\log
n)$-time randomized algorithm to compute the basis of an Abelian group$G$of size$n=p_1^{n_1}\cdots p_t^{n_t}$, where$d=\max\{ n_i
| i=1,\cdots, t\}$. It is a sublinear time algorithm if$\max\{ n_i
| i=1,\cdots, t\}$is bounded by a constant. It also implies that if$n$is an integer in$[1,m]-G(m,c)$, then the basis of an Abelian group of size$n$can be computed in$O((\log n)^{c+3}\log\log
n)$-time, where$c$is any positive constant and$G(m,c)$is a subset of the small fraction of integers in$[1,m]$with${|G(m,c)|\over m}=O({1\over (\log m)^{c/2}})$for every integer$m\$.

ISSN 1433-8092 | Imprint