10.2 Multiplicative Abelian Groups

Module: sage.groups.abelian_gps.abelian_group

Author Log:

Background on elementary divisors, invariant factors and the Smith normal form (according to section 4.1 of [C1]): An abelian group is a group A for which there exists an exact sequence $ \mathbf{Z}^k \rightarrow
\mathbf{Z}^\ell \rightarrow A \rightarrow 1$ , for some positive integers $ k,\ell$ with $ k\leq \ell$ . For example, a finite abelian group has a decomposition

$\displaystyle A = \langle a_1\rangle \times \dots \times \langle a_\ell\rangle ,
$

where $ ord(a_i)=p_i^{c_i}$ , for some primes $ p_i$ and some positive integers $ c_i$ , $ i=1,...,\ell$ . GAP calls the list (ordered by size) of the $ p_i^{c_i}$ the abelian invariants. In SAGE they will be called invariants. In this situation, $ k=\ell$ and $ \phi: \mathbf{Z}^\ell \rightarrow A$ is the map $ \phi(x_1,...,x_\ell) = a_1^{x_1}...a_\ell^{x_\ell}$ , for $ (x_1,...,x_\ell)\in \mathbf{Z}^\ell$ . The matrix of relations $ M:\mathbf{Z}^k \rightarrow \mathbf{Z}^\ell$ is the matrix whose rows generate the kernel of $ \phi$ as a $ \mathbf{Z}$ -module. In other words, $ M=(M_{ij})$ is a $ \ell\times \ell$ diagonal matrix with $ M_{ii}=p_i^{c_i}$ . Consider now the subgroup $ B\subset A$ generated by $ b_1 = a_1^{f_{1,1}}...a_\ell^{f_{\ell,1}}$ , ..., $ b_m = a_1^{f_{1,m}}...a_\ell^{f_{\ell,m}}$ . The kernel of the map $ \phi_B: \mathbf{Z}^m \rightarrow B$ defined by $ \phi_B(y_1,...,y_m) = b_1^{y_1}...b_m^{y_m}$ , for $ (y_1,...,y_m)\in \mathbf{Z}^m$ , is the kernel of the matrix

\begin{displaymath}
F=
\left(
\begin{array}{cccc}
f_{11} & f_{12} & \dots & f_{1...
...{\ell,1} & f_{\ell,2} & \dots & f_{\ell,m}
\end{array}\right),
\end{displaymath}

regarded as a map $ Z^m\rightarrow (\mathbf{Z}/p_1^{c_1}\mathbf{Z})\times ...\times (\mathbf{Z}/p_\ell^{c_\ell}\mathbf{Z})$ . In particular, $ B\cong \mathbf{Z}^m/ker(F)$ . If $ B=A$ then the Smith normal form (SNF) of a generator matrix of $ ker(F)$ and the SNF of $ M$ are the same. The diagonal entries $ s_i$ of the SNF $ S = diag[s_1,s_2,s_3, ... s_r,0,0,...0]$ , are called determinantal divisors of $ F$ . where $ r$ is the rank. The invariant factors of A are:

$\displaystyle s_1, s_2/s_1, s_3/s_2, ... s_r/s_{r-1}.
$

The elementary divisors use the highest (non-trivial) prime powers occuring in the factorizations of the numbers $ s_1, s_2,
... s_r$ .

SAGE supports multiplicative abelian groups on any prescribed finite number $ n \geq 0$ of generators. Use the AbelianGroup function to create an abelian group, and the gen and gens functions to obtain the corresponding generators. You can print the generators as arbitrary strings using the optional names argument to the AbelianGroup function.

EXAMPLE 1: We create an abelian group in zero or more variables; the syntax T(1) creates the identity element even in the rank zero case.

sage: T = AbelianGroup(0,[])
sage: T
Trivial Abelian Group
sage: T.gens()
()
sage: T(1)
1

EXAMPLE 2: An abelian group uses a multiplicative representation of elements, but the underlying representation is lists of integer exponents.

sage: F = AbelianGroup(5,[3,4,5,5,7],names = list("abcde"))
sage: F
Multiplicative Abelian Group isomorphic to C3 x C4 x C5 x C5 x C7
sage: (a,b,c,d,e) = F.gens()
sage: a*b^2*e*d
a*b^2*d*e
sage: x = b^2*e*d*a^7
sage: x
a*b^2*d*e
sage: x.list()
[1, 2, 0, 1, 1]

REFERENCES: [C1] H. Cohen Advanced topics in computational number theory, Springer, 2000. [C2] ---, A course in computational algebraic number theory, Springer, 1996. [R] J. Rotman, An introduction to the theory of groups, 4th ed, Springer, 1995.

Module-level Functions

AbelianGroup( n, [invfac=f], [names=None])

Create the multiplicative abelian group in $ n$ generators with given invariants, which must be prime powers.

INPUT:
    n -- integer
    invfac -- (the"invariant factors") a list of non-negative integers
              in the form [a0, a1,...,a(n-1)], typically written in
              increasing order.  This list is padded with zeros if
              it has length less than n.  
    names -- (optional) names of generators

Alternatively, you can also give input in the following form:
    
    \code{AbelianGroup(invfac, names="f")},

where names must be explicitly named.
    
OUTPUT:
    Abelian group with generators and invariant type. The default name
    for generator A.i is fi, as in GAP.

sage: F = AbelianGroup(5, [5,5,7,8,9], names='abcde')
sage: F(1)
1
sage: (a, b, c, d, e) = F.gens()
sage: mul([ a, b, a, c, b, d, c, d ])
a^2*b^2*c^2*d^2
sage: d * b**2 * c**3 
b^2*c^3*d
sage: F = AbelianGroup(3,[2]*3); F
Multiplicative Abelian Group isomorphic to C2 x C2 x C2
sage: H = AbelianGroup([2,3], names="xy"); H
Multiplicative Abelian Group isomorphic to C2 x C3
sage: AbelianGroup(5)
Multiplicative Abelian Group isomorphic to Z x Z x Z x Z x Z
sage: AbelianGroup(5).order()
Infinity

Notice how 0 's are padded on.

sage: AbelianGroup(5, [2,3,4])
Multiplicative Abelian Group isomorphic to Z x Z x C2 x C3 x C4

The invariant list can't be longer than the number of generators.

sage: AbelianGroup(2, [2,3,4])
Traceback (most recent call last):
...
ValueError: invfac (=[2, 3, 4]) must have length n (=2)

is_AbelianGroup( x)

Return True if $ x$ is an abelian group.

sage: F = AbelianGroup(5,[5,5,7,8,9],names = list("abcde")); F
Multiplicative Abelian Group isomorphic to C5 x C5 x C7 x C8 x C9
sage: is_AbelianGroup(F)
True
sage: is_AbelianGroup(AbelianGroup(7, [3]*7))
True

word_problem( words, g, [verbose=False])

G and H are abelian, g in G, H is a subgroup of G generated by a list (words) of elements of G. If g is in H, return the expression for g as a word in the elements of (words).

The 'word problem' for a finite abelian group G boils down to the following matrix-vector analog of the Chinese remainder theorem.

Problem: Fix integers $ 1<n_1\leq n_2\leq ...\leq n_k$ (indeed, these $ n_i$ will all be prime powers), fix a generating set $ g_i=(a_{i1},...,a_{ik})$ (with $ a_{ij}\in \mathbf{Z}/n_j\mathbf{Z}$ ), for $ 1\leq i\leq \ell$ , for the group $ G$ , and let $ d = (d_1,...,d_k)$ be an element of the direct product $ \mathbf{Z}/n_1\mathbf{Z}\times ...\times \mathbf{Z}/n_k\mathbf{Z}$ . Find, if they exist, integers $ c_1,...,c_\ell$ such that $ c_1g_1+...+c_\ell g_\ell = d$ . In other words, solve the equation $ cA=d$ for $ c\in \mathbf{Z}^\ell$ , where $ A$ is the matrix whose rows are the $ g_i$ 's. Of course, it suffices to restrict the $ c_i$ 's to the range $ 0\leq c_i\leq N-1$ , where $ N$ denotes the least common multiple of the integers $ n_1,...,n_k$ .

This function does not solve this directly, as perhaps it should. Rather (for both speed and as a model for a similar function valid for more general groups), it pushes it over to GAP, which has optimized algorithms for the word problem. Essentially, this function is a wrapper for the GAP function 'Factorization'.

sage: G.<a,b,c> = AbelianGroup(3,[2,3,4]); G
Multiplicative Abelian Group isomorphic to C2 x C3 x C4
sage: word_problem([a*b,a*c], b*c)
[[a*b, 1], [a*c, 1]]
sage: word_problem([a*b,a*c],b*c)
[[a*b, 1], [a*c, 1]]

sage: A.<a,b,c,d,e> = AbelianGroup(5,[4, 5, 5, 7, 8])
sage: b1 = a^3*b*c*d^2*e^5
sage: b2 = a^2*b*c^2*d^3*e^3
sage: b3 = a^7*b^3*c^5*d^4*e^4
sage: b4 = a^3*b^2*c^2*d^3*e^5
sage: b5 = a^2*b^4*c^2*d^4*e^5
sage: word_problem([b1,b2,b3,b4,b5],e)
[[a^3*b*c*d^2*e^5, 1],
[a^2*b*c^2*d^3*e^3, 1],
[a^3*b^3*d^4*e^4, 3],
[a^3*b^2*c^2*d^3*e^5, 1]]

WARNINGS: (1) Might have unpleasant effect when the word problem cannot be solved.

(2) Uses permutation groups, so may be slow when group is large. The instance method word_problem of the class AbelianGroupElement is implemented differently (wrapping GAP's"EpimorphismFromFreeGroup" and "PreImagesRepresentative") and may be faster.

Class: AbelianGroup_class

class AbelianGroup_class
Free abelian group on $ n$ generators. The invariant factors [a1,a2,...,ak] must be a list of prime powers.

sage: F = AbelianGroup(5,[5,5,7,8,9],names = list("abcde")); F
Multiplicative Abelian Group isomorphic to C5 x C5 x C7 x C8 x C9
sage: F = AbelianGroup(5,[2, 4, 12, 24, 120],names = list("abcde")); F
Multiplicative Abelian Group isomorphic to C2 x C3 x C3 x C3 x C4 x C4 x C5
x C8 x C8
sage: F.elementary_divisors()
[2, 3, 3, 3, 4, 4, 5, 8, 8]

Thus we see that the "invariants" are not the invariant factors but the "elementary divisors" (in the terminology of Rotman [R]).

AbelianGroup_class( self, n, invfac, [names=f])

Functions: elementary_divisors,$  $ exponent,$  $ gen,$  $ invariants,$  $ is_commutative,$  $ ngens,$  $ order,$  $ permutation_group,$  $ random,$  $ subgroup

elementary_divisors( self)

sage: G = AbelianGroup(2,[2,6])
sage: G
Multiplicative Abelian Group isomorphic to C2 x C2 x C3
sage: G.invariants()
[2, 6]
sage: G.elementary_divisors()
[2, 2, 3]

exponent( self)

Return the exponent of this abelian group.

sage: G = AbelianGroup([2,3,7]); G
Multiplicative Abelian Group isomorphic to C2 x C3 x C7
sage: G.exponent()
42

gen( self, [i=0])

The $ i$ -th generator of the abelian group.

sage: F = AbelianGroup(5,[],names='a')
sage: F.0
a0
sage: F.2
a2
sage: F.invariants()
[0, 0, 0, 0, 0]

is_commutative( self)

Return True since this group is commutative.

sage: G = AbelianGroup([2,3,9, 0])
sage: G.is_commutative()
True
sage: G.is_abelian()
True

ngens( self)

The number of free generators of the abelian group.

sage: F = AbelianGroup(10000)
sage: F.ngens()
10000

order( self)

Return the order of this group.

sage: G = AbelianGroup(2,[2,3])
sage: G.order()
6
sage: G = AbelianGroup(3,[2,3,0])
sage: G.order()
Infinity

permutation_group( self)

Return the permutation group isomorphic to this abelian group.

If the invariants are $ q_1, \ldots, q_n$ then the generators of the permutation will be of order $ q_1, \ldots, q_n$ , respectively.

sage: G = AbelianGroup(2,[2,3]); G
Multiplicative Abelian Group isomorphic to C2 x C3
sage: G.permutation_group()
Permutation Group with generators [(1,4)(2,5)(3,6), (1,2,3)(4,5,6)]

random( self)

Return a random element of this group.

subgroup( self, gensH, [names=f])

Create a subgroup of this group. The "big" group must be defined using "named" generators.

INPUT:
 gensH -- list of elements which are products of the
          generators of the ambient abelian group G = self

sage: G.<a,b,c> = AbelianGroup(3, [2,3,4]); G
Multiplicative Abelian Group isomorphic to C2 x C3 x C4
sage: H = G.subgroup([a*b,a]); H
Multiplicative Abelian Group isomorphic to C2 x C3, which is the subgroup
of
Multiplicative Abelian Group isomorphic to C2 x C3 x C4
generated by [a*b, a]
sage: H < G
True
sage: F = G.subgroup([a,b^2])
sage: F
Multiplicative Abelian Group isomorphic to C2 x C3, which is the subgroup
of
Multiplicative Abelian Group isomorphic to C2 x C3 x C4
generated by [a, b^2]
sage: F.gens()
[a, b^2]
sage: F = AbelianGroup(5,[30,64,729],names = list("abcde"))
sage: a,b,c,d,e = F.gens()
sage: F.subgroup([a,b])
Multiplicative Abelian Group isomorphic to Z x Z, which is the subgroup of
Multiplicative Abelian Group isomorphic to Z x Z x C2 x C3 x C5 x C64 x
C729
generated by [a, b]
sage: F.subgroup([c,e])
Multiplicative Abelian Group isomorphic to C2 x C3 x C5 x C729, which is
the subgroup of
Multiplicative Abelian Group isomorphic to Z x Z x C2 x C3 x C5 x C64 x
C729
generated by [c, e]

Special Functions: __call__,$  $ __cmp__,$  $ __contains__,$  $ _gap_init_,$  $ _latex_,$  $ _repr_

__call__( self, x)

Create an element of this abelian group from $ x$ .

sage: F = AbelianGroup(10, [2]*10)
sage: F(F.2)
f2
sage: F(1)
1

__cmp__( self, right)

Compare self and right.

The ordering is the ordering induced by that on the invariant factors lists.

sage: G1 = AbelianGroup([2,3,4,5])
sage: G2 = AbelianGroup([2,3,4,5,1])
sage: G1 < G2
False
sage: G1 > G2
False
sage: G1 == G2
True

__contains__( self, x)

Return True if $ x$ is an element of this abelian group.

sage: F = AbelianGroup(10,[2]*10)
sage: F.2 * F.3 in F
True

_gap_init_( self)

Return string that defines corresponding abelian group in GAP.

sage: G = AbelianGroup([2,3,9])
sage: G._gap_init_()
'AbelianGroup([2, 3, 9])'
sage: gap(G)
<pc group of size 54 with 3 generators>

Only works for finite groups.

sage: G = AbelianGroup(3,[0,3,4],names="abc"); G
Multiplicative Abelian Group isomorphic to Z x C3 x C4
sage: G._gap_init_()
Traceback (most recent call last):
...
TypeError: abelian groups in GAP are finite, but self is infinite

_latex_( self)

Return latex representation of this group.

sage: F = AbelianGroup(10, [2]*10)
sage: F._latex_()
'${\rm AbelianGroup}( 10, [2, 2, 2, 2, 2, 2, 2, 2, 2, 2] )$'

Class: AbelianGroup_subgroup

class AbelianGroup_subgroup
Subgroup subclass of AbelianGroup_class, so instance methods are inherited.

TODO: * There should be a way to coerce an element of a subgroup into the ambient group.

AbelianGroup_subgroup( self, ambient, gens, [names=f])

sage: F = AbelianGroup(5,[30,64,729],names = list("abcde"))
sage: a,b,c,d,e = F.gens()
sage: F.subgroup([a^3,b])
Multiplicative Abelian Group isomorphic to Z x Z, which is the subgroup of
Multiplicative Abelian Group isomorphic to Z x Z x C2 x C3 x C5 x C64 x
C729
generated by [a^3, b]
sage: F.subgroup([c])
Multiplicative Abelian Group isomorphic to C2 x C3 x C5, which is the
subgroup of
Multiplicative Abelian Group isomorphic to Z x Z x C2 x C3 x C5 x C64 x
C729
generated by [c]
sage: F.subgroup([a,c])
Multiplicative Abelian Group isomorphic to Z x C2 x C3 x C5, which is the
subgroup of
Multiplicative Abelian Group isomorphic to Z x Z x C2 x C3 x C5 x C64 x
C729
generated by [a, c]
sage: F.subgroup([a,b*c])
Multiplicative Abelian Group isomorphic to Z x Z, which is the subgroup of
Multiplicative Abelian Group isomorphic to Z x Z x C2 x C3 x C5 x C64 x
C729
generated by [a, b*c]
sage: F.subgroup([b*c,d])
Multiplicative Abelian Group isomorphic to Z x C64, which is the subgroup
of
Multiplicative Abelian Group isomorphic to Z x Z x C2 x C3 x C5 x C64 x
C729
generated by [b*c, d]
sage: F.subgroup([a*b,c^6,d],names = list("xyz"))
Multiplicative Abelian Group isomorphic to Z x C5 x C64, which is the
subgroup of
Multiplicative Abelian Group isomorphic to Z x Z x C2 x C3 x C5 x C64 x
C729
generated by [a*b, c^6, d]
sage: H.<x,y,z> = F.subgroup([a*b, c^6, d]); H
Multiplicative Abelian Group isomorphic to Z x C5 x C64, which is the
subgroup of
Multiplicative Abelian Group isomorphic to Z x Z x C2 x C3 x C5 x C64 x
C729
generated by [a*b, c^6, d]
sage: G = F.subgroup([a*b,c^6,d],names = list("xyz"))
sage: G
Multiplicative Abelian Group isomorphic to Z x C5 x C64, which is the
subgroup of
Multiplicative Abelian Group isomorphic to Z x Z x C2 x C3 x C5 x C64 x
C729
generated by [a*b, c^6, d]
sage: x,y,z = G.gens()
sage: x.order()
Infinity
sage: y.order()
5
sage: z.order()
64
sage: A = AbelianGroup(5,[3, 5, 5, 7, 8], names = "abcde")
sage: a,b,c,d,e = A.gens()
sage: A.subgroup([a,b])
Multiplicative Abelian Group isomorphic to C3 x C5, which is the subgroup
of
Multiplicative Abelian Group isomorphic to C3 x C5 x C5 x C7 x C8
generated by [a, b]
sage: A.subgroup([a,b,c,d^2,e])
Multiplicative Abelian Group isomorphic to C3 x C5 x C5 x C7 x C8, which is
the subgroup of
Multiplicative Abelian Group isomorphic to C3 x C5 x C5 x C7 x C8
generated by [a, b, c, d^2, e]
sage: A.subgroup([a,b,c,d^2,e^2])
Multiplicative Abelian Group isomorphic to C3 x C4 x C5 x C5 x C7, which is
the subgroup of
Multiplicative Abelian Group isomorphic to C3 x C5 x C5 x C7 x C8
generated by [a, b, c, d^2, e^2]
sage: B = A.subgroup([a^3,b,c,d,e^2]); B
Multiplicative Abelian Group isomorphic to C4 x C5 x C5 x C7, which is the
subgroup of
Multiplicative Abelian Group isomorphic to C3 x C5 x C5 x C7 x C8
generated by [b, c, d, e^2]
sage: B.invariants()
[4, 5, 5, 7]
sage: A = AbelianGroup(4,[1009, 2003, 3001, 4001], names = "abcd")
sage: a,b,c,d = A.gens()
sage: B = A.subgroup([a^3,b,c,d])
sage: B.invariants()
[1009, 2003, 3001, 4001]
sage: A.order()
24266473210027
sage: B.order()
24266473210027
sage: A = AbelianGroup(4,[1008, 2003, 3001, 4001], names = "abcd")
sage: a,b,c,d = A.gens()
sage: B = A.subgroup([a^3,b,c,d])
sage: B
Multiplicative Abelian Group isomorphic to C3 x C7 x C16 x C2003 x C3001 x
C4001, which is the subgroup of
Multiplicative Abelian Group isomorphic to C7 x C9 x C16 x C2003 x C3001 x
C4001
generated by [a^3, b, c, d]

Infinite groups can also be handled:

sage: G = AbelianGroup([3,4,0], names = "abc")
sage: a,b,c = G.gens()
sage: F = G.subgroup([a,b^2,c]); F
Multiplicative Abelian Group isomorphic to Z x C3 x C4, which is the
subgroup of
Multiplicative Abelian Group isomorphic to Z x C3 x C4
generated by [a, b^2, c]
sage: F.invariants()
[0, 3, 4]
sage: F.gens()
[a, b^2, c]
sage: F.order()
Infinity

Functions: ambient_group,$  $ gens,$  $ invs

ambient_group( self)

Return the ambient group related to self.

gens( self)

Return the generators for this subgroup.

invs( self)

Return the invariants for this subgroup.

Special Functions: __cmp__,$  $ _repr_

__cmp__( self, right)

Compare self and other. If self and other are in a common ambient group, then self <= other precisely if self is contained in other.

sage: G = AbelianGroup(3, [2,3,4], names="abc"); G
       Multiplicative Abelian Group isomorphic to C2 x C3 x C4
sage: a,b,c = G.gens()
sage: F=G.subgroup([a,b^2]); F
       Multiplicative Abelian Group isomorphic to C2 x C3, which is the
subgroup of
       Multiplicative Abelian Group isomorphic to C2 x C3 x C4
       generated by [a, b^2]
    sage: F<G
       True

See About this document... for information on suggesting changes.