Multiplicative Abelian Groups

AUTHORS:

  • William Stein, David Joyner (2008-12): added (user requested) is_cyclic, fixed elementary_divisors.
  • David Joyner (2006-03): (based on free abelian monoids by David Kohel)
  • David Joyner (2006-05) several significant bug fixes
  • David Joyner (2006-08) trivial changes to docs, added random, fixed bug in how invariants are recorded
  • David Joyner (2006-10) added dual_group method
  • David Joyner (2008-02) fixed serious bug in word_problem
  • David Joyner (2008-03) fixed bug in trivial group case
  • David Loeffler (2009-05) added subgroups method

TODO:

  • additive abelian groups should also be supported

Background on 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 \ZZ^k \rightarrow \ZZ^\ell \rightarrow A \rightarrow 1, for some positive integers k,\ell with k\leq \ell. For example, a finite abelian group has a decomposition

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:  \ZZ^\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 \ZZ^\ell. The matrix of relations M:\ZZ^k \rightarrow \ZZ^\ell is the matrix whose rows generate the kernel of \phi as a \ZZ-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:  \ZZ^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 \ZZ^m, is the kernel of the matrix

F=
\left(
\begin{array}{cccc}
f_{11} & f_{12} & \dots & f_{1m}\\
f_{21} & f_{22} & \dots & f_{2m}\\
\vdots &        & \ddots & \vdots \\
f_{\ell,1} & f_{\ell,2} & \dots & f_{\ell,m}
\end{array}
\right),

regarded as a map \ZZ^m\rightarrow (\ZZ/p_1^{c_1}\ZZ)\times ...\times (\ZZ/p_\ell^{c_\ell}\ZZ). In particular, B\cong \ZZ^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 {it invariant factors} of A are:

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

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.

Warning

Many basic properties for infinite abelian groups are not implemented.

sage.groups.abelian_gps.abelian_group.AbelianGroup(n, invfac=None, names='f')

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:

    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])
...
ValueError: invfac (=[2, 3, 4]) must have length n (=2)
class sage.groups.abelian_gps.abelian_group.AbelianGroup_class(n, invfac, names='f')

Bases: sage.groups.group.AbelianGroup

Abelian group on n generators. The invariant factors [a_1,a_2,...,a_k] need not be prime powers. divisors will be).

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: F = AbelianGroup(5,[2, 4, 12, 24, 120],names = list("abcde")); F
Multiplicative Abelian Group isomorphic to C2 x C4 x C12 x C24 x C120
sage: F.elementary_divisors()
[2, 4, 12, 24, 120]

The entry 1 in the list of invariants is ignored:

sage: F = AbelianGroup(3,[1,2,3],names='a')
sage: F.invariants()
[2, 3]
sage: F.gens()
(a0, a1)
sage: F.ngens()
2
sage: (F.0).order()
2
sage: (F.1).order()
3
sage: AbelianGroup(1, [1], names='e')
Multiplicative Abelian Group isomorphic to C1
sage: AbelianGroup(1, [1], names='e').gens()
(e,)
sage: AbelianGroup(1, [1], names='e').list()
[1]
sage: AbelianGroup(3, [2, 1, 2], names=list('abc')).list()
[1, b, a, a*b]

sage: F.category()
Category of groups
dual_group()

Returns the dual group.

EXAMPLES:

elementary_divisors()

This returns the elementary divisors of the group, using Pari.

Note

Here is another algorithm for computing the elementary divisors d_1, d_2, d_3, \ldots, of a finite abelian group (where d_1 | d_2 | d_3 | \ldots are composed of prime powers dividing the invariants of the group in a way described below). Just factor the invariants a_i that define the abelian group. Then the biggest d_i is the product of the maximum prime powers dividing some a_j. In other words, the largest d_i is the product of p^v, where v = max(ord_p(a_j) \mathrm{ for all } j). Now divide out all those p^v‘s into the list of invariants a_i, and get a new list of “smaller invariants”“. Repeat the above procedure on these “”smaller invariants”” to compute d_{i-1}, and so on. (Thanks to Robert Miller for communicating this algorithm.)

TODO: When somebody wants to speed this code up, please implement he
above algorithm.

EXAMPLES:

sage: G = AbelianGroup(2,[2,3])
sage: G.elementary_divisors()
[6]
sage: G = AbelianGroup(1, [6])
sage: G.elementary_divisors()
[6]
sage: G = AbelianGroup(2,[2,6])
sage: G
Multiplicative Abelian Group isomorphic to C2 x C6
sage: G.invariants()
[2, 6]
sage: G.elementary_divisors()
[2, 6]
sage: J = AbelianGroup([1,3,5,12])
sage: J.elementary_divisors()
[3, 60]
sage: G = AbelianGroup(2,[0,6])
sage: G.elementary_divisors()
[6, 0]
exponent()

Return the exponent of this abelian group.

EXAMPLES:

sage: G = AbelianGroup([2,3,7]); G
Multiplicative Abelian Group isomorphic to C2 x C3 x C7
sage: G.exponent()
42
sage: G = AbelianGroup([2,4,6]); G
Multiplicative Abelian Group isomorphic to C2 x C4 x C6
sage: G.exponent()
12
gen(i=0)

The i-th generator of the abelian group.

EXAMPLES:

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

Return the identity element of this group.

EXAMPLES:

sage: G = AbelianGroup([2,2])
sage: e = G.identity()
sage: e
1
sage: g = G.gen(0)
sage: g*e
f0
sage: e*g
f0
invariants()

Return a copy of the list of invariants of this group.

It is safe to modify the returned list.

EXAMPLES:

sage: J = AbelianGroup([2,3])
sage: J.invariants()
[2, 3]
sage: v = J.invariants(); v
[2, 3]
sage: v[0] = 5
sage: J.invariants()
[2, 3]
sage: J.invariants() is J.invariants()
False
is_commutative()

Return True since this group is commutative.

EXAMPLES:

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

Return True if the group is a cyclic group.

EXAMPLES:
sage: J = AbelianGroup([2,3]) sage: J.invariants() [2, 3] sage: J.elementary_divisors() [6] sage: J.is_cyclic() True sage: G = AbelianGroup([6]) sage: G.invariants() [6] sage: G.is_cyclic() True sage: H = AbelianGroup([2,2]) sage: H.invariants() [2, 2] sage: H.is_cyclic() False sage: H = AbelianGroup([2,4]) sage: H.elementary_divisors() [2, 4] sage: H.is_cyclic() False sage: H.permutation_group().is_cyclic() False sage: T = AbelianGroup([]) sage: T.is_cyclic() True sage: T = AbelianGroup(1,[0]); T Multiplicative Abelian Group isomorphic to Z sage: T.is_cyclic() True
list()

Return list of all elements of this group.

EXAMPLES:

sage: G = AbelianGroup([2,3], names = "ab")
sage: G.list()
[1, b, b^2, a, a*b, a*b^2]
sage: G = AbelianGroup([]); G
Trivial Abelian Group
sage: G.list()
[1]
ngens()

The number of free generators of the abelian group.

EXAMPLES:

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

Return the order of this group.

EXAMPLES:

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

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.

EXAMPLES:

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_element()

Return a random element of this group. (Renamed random to random_element.)

EXAMPLES:

sage: G = AbelianGroup([2,3,9])
sage: G.random_element()
f0*f1^2*f2
subgroup(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

EXAMPLES:

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 C30 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 C30 x C64 x C729 generated by
[c, e]
subgroup_reduced(elts, verbose=False)

Given a list of lists of integers (corresponding to elements of self), find a set of independent generators for the subgroup generated by these elements, and return the subgroup with these as generators, forgetting the original generators.

This is used by the subgroups routine.

An error will be raised if the elements given are not linearly independent over QQ.

EXAMPLE:

sage: G = AbelianGroup([4,4])
sage: G.subgroup( [ G([1,0]), G([1,2]) ])
Multiplicative Abelian Group isomorphic to C2 x C4, which is the subgroup of
Multiplicative Abelian Group isomorphic to C4 x C4
generated by [f0, f0*f1^2]
sage: AbelianGroup([4,4]).subgroup_reduced( [ [1,0], [1,2] ])
Multiplicative Abelian Group isomorphic to C2 x C4, which is the subgroup of
Multiplicative Abelian Group isomorphic to C4 x C4
generated by [f1^2, f0]
subgroups(check=False)

Compute all the subgroups of this abelian group (which must be finite).

TODO: This is many orders of magnitude slower than Magma.

INPUT:

  • check: if True, performs the same computation in GAP and checks that the number of subgroups generated is the same. (I don’t know how to convert GAP’s output back into Sage, so we don’t actually compare the subgroups).

ALGORITHM:

If the group is cyclic, the problem is easy. Otherwise, write it as a direct product A x B, where B is cyclic. Compute the subgroups of A (by recursion).

Now, for every subgroup C of A x B, let G be its projection onto A and H its intersection with B. Then there is a well-defined homomorphism f: G -> B/H that sends a in G to the class mod H of b, where (a,b) is any element of C lifting a; and every subgroup C arises from a unique triple (G, H, f).

EXAMPLES:

sage: AbelianGroup([2,3]).subgroups()
[Multiplicative Abelian Group isomorphic to C2 x C3, which is the subgroup of
Multiplicative Abelian Group isomorphic to C2 x C3
generated by [f0*f1^2],
 Multiplicative Abelian Group isomorphic to C2, which is the subgroup of
Multiplicative Abelian Group isomorphic to C2 x C3
generated by [f0],
 Multiplicative Abelian Group isomorphic to C3, which is the subgroup of
Multiplicative Abelian Group isomorphic to C2 x C3
generated by [f1],
 Trivial Abelian Group, which is the subgroup of
Multiplicative Abelian Group isomorphic to C2 x C3
generated by []]

sage: len(AbelianGroup([2,4,8]).subgroups())
81
class sage.groups.abelian_gps.abelian_group.AbelianGroup_subgroup(ambient, gens, names='f')

Bases: sage.groups.abelian_gps.abelian_group.AbelianGroup_class

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.
ambient_group()
Return the ambient group related to self.
gen(n)

Return the nth generator of this subgroup.

EXAMPLE:

sage: G.<a,b> = AbelianGroup(2)
sage: A = G.subgroup([a])
sage: A.gen(0)
a
gens()
Return the generators for this subgroup.
invs()
Return the invariants for this subgroup.
sage.groups.abelian_gps.abelian_group.is_AbelianGroup(x)

Return True if x is an abelian group.

EXAMPLES:

sage: from sage.groups.abelian_gps.abelian_group import is_AbelianGroup
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
sage.groups.abelian_gps.abelian_group.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 \mathrm{Z}/n_j\mathrm{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 \mathrm{Z}/n_1\mathrm{Z} \times ...\times \mathrm{Z}/n_k\mathrm{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 \mathrm{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 (non-deterministic) 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: w = word_problem([a*b,a*c], b*c); w #random 
[[a*b, 1], [a*c, 1]]  
sage: prod([x^i for x,i in w]) == b*c
True
sage: w = word_problem([a*c,c],a); w #random 
[[a*c, 1], [c, -1]]   
sage: prod([x^i for x,i in w]) == a 
True
sage: word_problem([a*c,c],a,verbose=True) #random
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: w = word_problem([b1,b2,b3,b4,b5],e); w #random
[[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: prod([x^i for x,i in w]) == e 
True
sage: word_problem([a,b,c,d,e],e)
[[e, 1]]
sage: word_problem([a,b,c,d,e],b)
[[b, 1]]

Warning

  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.

Previous topic

Miscellaneous generic functions

Next topic

Abelian group elements

This Page