Module abelian_group

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 \Z/n_j\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
$\Z/n_1\Z \times ...\times \Z/n_k\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 \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'. 

EXAMPLE:
    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*c,c],a)
    [[a*c, 1], [c, -1]]
    sage: word_problem([a*c,c],a,verbose=True)
    a = (a*c)^1*(c)^-1
    [[a*c, 1], [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^2*b^4*c^2*d^4*e^5, 1]]
    sage: word_problem([a,b,c,d,e],e)
    [[e, 1]]
    sage: word_problem([a,b,c,d,e],b)
    [[b, 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.

Create the multiplicative abelian group in $n$ generators with
given invariants (which need not 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.

EXAMPLES:
    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 ], F(1))
    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)

Return True if $x$ is an abelian group.

EXAMPLES:
    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