This module lets you compute with finitely generated Abelian groups of the form
It is customary to denote the infinite cyclic group as having
order
, so the data defining the Abelian group can be written as an
integer vector
where there are zeroes and
non-zero values. To construct this
Abelian group in Sage, you can either specify all entries of
or only the non-zero entries together with the total number of
generators:
sage: AbelianGroup([0,0,0,2,3])
Multiplicative Abelian group isomorphic to Z x Z x Z x C2 x C3
sage: AbelianGroup(5, [2,3])
Multiplicative Abelian group isomorphic to Z x Z x Z x C2 x C3
It is also legal to specify as the order. The corresponding
generator will be the neutral element, but it will still take up an
index in the labelling of the generators:
sage: G = AbelianGroup([2,1,3], names='g')
sage: G.gens()
(g0, 1, g2)
Note that this presentation is not unique, for example . The orders of the generators
has previously been called
invariants in Sage, even though they are not necessarily the (unique)
invariant factors of the group. You should now use
gens_orders() instead:
sage: J = AbelianGroup([2,0,3,2,4]); J
Multiplicative Abelian group isomorphic to C2 x Z x C3 x C2 x C4
sage: J.gens_orders() # use this instead
(2, 0, 3, 2, 4)
sage: J.invariants() # deprecated
(2, 0, 3, 2, 4)
sage: J.elementary_divisors() # these are the "invariant factors"
(2, 2, 12, 0)
sage: for i in range(J.ngens()):
... print i, J.gen(i), J.gen(i).order() # or use this form
0 f0 2
1 f1 +Infinity
2 f2 3
3 f3 2
4 f4 4
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
,
for some positive integers
with
. For example, a finite abelian group has a
decomposition
where , for some primes
and some
positive integers
,
. GAP calls the
list (ordered by size) of the
the abelian invariants.
In Sage they will be called invariants.
In this situation,
and
is the map
,
for
. The matrix of relations
is the matrix
whose rows generate the kernel of
as a
-module.
In other words,
is a
diagonal matrix with
. Consider now the
subgroup
generated by
, ...,
.
The kernel of the map
defined by
,
for
, is the kernel of the matrix
regarded as a map
.
In particular,
. If
then the
Smith normal form (SNF) of a generator matrix of
and the SNF of
are the same. The diagonal entries
of the
SNF
,
are called determinantal divisors of
.
where
is the rank. The {it invariant factors} of A are:
Sage supports multiplicative abelian groups on any prescribed finite
number of generators. Use the AbelianGroup()
function to create an abelian group, and the
gen() and gens()
methods 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:
Warning
Many basic properties for infinite abelian groups are not implemented.
AUTHORS:
Create the multiplicative abelian group in generators
with given orders of generators (which need not be prime powers).
INPUT:
from gens_orders.
, typically written in increasing
order. This list is padded with zeros if it has length less
than n. The orders of the commuting generators, with
denoting an infinite cyclic factor.
names – (optional) names of generators
Alternatively, you can also give input in the form AbelianGroup(gens_orders, names="f"), where the names keyword argument 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 that ‘s are prepended if necessary:
sage: G = AbelianGroup(5, [2,3,4]); G
Multiplicative Abelian group isomorphic to Z x Z x C2 x C3 x C4
sage: G.gens_orders()
(0, 0, 2, 3, 4)
The invariant list must not be longer than the number of generators:
sage: AbelianGroup(2, [2,3,4])
Traceback (most recent call last):
...
ValueError: gens_orders (=(2, 3, 4)) must have length n (=2)
Bases: sage.structure.unique_representation.UniqueRepresentation, sage.groups.group.AbelianGroup
The parent for Abelian groups with chosen generator orders.
Warning
You should use AbelianGroup() to construct Abelian groups and not instantiate this class directly.
INPUT:
EXAMPLES:
sage: Z2xZ3 = AbelianGroup([2,3])
sage: Z6 = AbelianGroup([6])
sage: Z2xZ3 is Z2xZ3, Z6 is Z6
(True, True)
sage: Z2xZ3 is Z6
False
sage: Z2xZ3 == Z6
True
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)
sage: F.category()
Category of finite commutative groups
TESTS:
sage: AbelianGroup([]).gens_orders()
()
sage: AbelianGroup([1]).gens_orders()
(1,)
sage: AbelianGroup([1,1]).gens_orders()
(1, 1)
sage: AbelianGroup(0).gens_orders()
()
alias of AbelianGroupElement
Returns the dual group.
INPUT:
OUTPUT:
The ~sage.groups.abelian_gps.dual_abelian_group.DualAbelianGroup_class
EXAMPLES:
sage: G = AbelianGroup([2])
sage: G.dual_group()
Dual of Abelian Group isomorphic to Z/2Z over Cyclotomic Field of order 2 and degree 1
sage: G.dual_group().gens()
(X,)
sage: G.dual_group(names='Z').gens()
(Z,)
sage: G.dual_group(base_ring=QQ)
Dual of Abelian Group isomorphic to Z/2Z over Rational Field
TESTS:
sage: H = AbelianGroup(1)
sage: H.dual_group()
Traceback (most recent call last):
...
ValueError: the group must be finite
This returns the elementary divisors of the group, using Pari.
Note
Here is another algorithm for computing the elementary divisors
, of a finite abelian group (where
are composed of prime powers dividing the invariants of the group
in a way described below). Just factor the invariants
that
define the abelian group. Then the biggest
is the product
of the maximum prime powers dividing some
. In other words, the
largest
is the product of
, where
).
Now divide out all those
‘s into the list of invariants
,
and get a new list of “smaller invariants””. Repeat the above procedure
on these “”smaller invariants”” to compute
, and so on.
(Thanks to Robert Miller for communicating this algorithm.)
OUTPUT:
A tuple of integers.
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.gens_orders()
(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)
sage: AbelianGroup([3,4,5]).elementary_divisors()
(60,)
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
The -th generator of the abelian group.
EXAMPLES:
sage: F = AbelianGroup(5,[],names='a')
sage: F.0
a0
sage: F.2
a2
sage: F.gens_orders()
(0, 0, 0, 0, 0)
sage: G = AbelianGroup([2,1,3])
sage: G.gens()
(f0, 1, f2)
Return the generators of the group.
OUTPUT:
A tuple of group elements. The generators according to the chosen gens_orders().
EXAMPLES:
sage: F = AbelianGroup(5,[3,2],names='abcde')
sage: F.gens()
(a, b, c, d, e)
sage: [ g.order() for g in F.gens() ]
[+Infinity, +Infinity, +Infinity, 3, 2]
Return the orders of the cyclic factors that this group has been defined with.
Use elementary_divisors() if you are looking for an invariant of the group.
OUTPUT:
A tuple of integers.
EXAMPLES:
sage: Z2xZ3 = AbelianGroup([2,3])
sage: Z2xZ3.gens_orders()
(2, 3)
sage: Z2xZ3.elementary_divisors()
(6,)
sage: Z6 = AbelianGroup([6])
sage: Z6.gens_orders()
(6,)
sage: Z6.elementary_divisors()
(6,)
sage: Z2xZ3.is_isomorphic(Z6)
True
sage: Z2xZ3 is Z6
False
TESTS:
sage: F = AbelianGroup(3, [2], names='abc')
sage: map(type, F.gens_orders())
[<type 'sage.rings.integer.Integer'>,
<type 'sage.rings.integer.Integer'>,
<type 'sage.rings.integer.Integer'>]
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
Return the orders of the cyclic factors that this group has been defined with.
For historical reasons this has been called invariants in Sage, even though they are not necessarily the invariant factors of the group. Use gens_orders() instead:
sage: J = AbelianGroup([2,0,3,2,4]); J
Multiplicative Abelian group isomorphic to C2 x Z x C3 x C2 x C4
sage: J.invariants() # deprecated
(2, 0, 3, 2, 4)
sage: J.gens_orders() # use this instead
(2, 0, 3, 2, 4)
sage: for i in range(J.ngens()):
... print i, J.gen(i), J.gen(i).order() # or use this
0 f0 2
1 f1 +Infinity
2 f2 3
3 f3 2
4 f4 4
Use elementary_divisors() if you are looking for an invariant of the group.
OUTPUT:
A tuple of integers. Zero means infinite cyclic factor.
EXAMPLES:
sage: J = AbelianGroup([2,3])
sage: J.invariants()
(2, 3)
sage: J.elementary_divisors()
(6,)
TESTS:
sage: F = AbelianGroup(3, [2], names='abc')
sage: map(type, F.gens_orders())
[<type 'sage.rings.integer.Integer'>,
<type 'sage.rings.integer.Integer'>,
<type 'sage.rings.integer.Integer'>]
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
Return True if the group is a cyclic group.
EXAMPLES:
sage: J = AbelianGroup([2,3])
sage: J.gens_orders()
(2, 3)
sage: J.elementary_divisors()
(6,)
sage: J.is_cyclic()
True
sage: G = AbelianGroup([6])
sage: G.gens_orders()
(6,)
sage: G.is_cyclic()
True
sage: H = AbelianGroup([2,2])
sage: H.gens_orders()
(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
sage: B = AbelianGroup([3,4,5])
sage: B.is_cyclic()
True
Check whether left and right are isomorphic
INPUT:
OUTPUT:
Boolean. Whether left and right are isomorphic as abelian groups.
EXAMPLES:
sage: G1 = AbelianGroup([2,3,4,5])
sage: G2 = AbelianGroup([2,3,4,5,1])
sage: G1.is_isomorphic(G2)
True
sage: G1 == G2 # syntactic sugar
True
Test whether left is a subgroup of right.
EXAMPLES:
sage: G = AbelianGroup([2,3,4,5])
sage: G.is_subgroup(G)
True
sage: H = G.subgroup([G.1])
sage: H.is_subgroup(G)
True
sage: G.<a, b> = AbelianGroup(2)
sage: H.<c> = AbelianGroup(1)
sage: H < G
False
Return whether the group is trivial
A group is trivial if it has precisely one element.
EXAMPLES:
sage: AbelianGroup([2, 3]).is_trivial()
False
sage: AbelianGroup([1, 1]).is_trivial()
True
Return tuple 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,)
The number of free generators of the abelian group.
EXAMPLES:
sage: F = AbelianGroup(10000)
sage: F.ngens()
10000
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
Return the permutation group isomorphic to this abelian group.
If the invariants are then the
generators of the permutation will be of order
, 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 [(3,4,5), (1,2)]
Return a random element of this group.
EXAMPLES:
sage: G = AbelianGroup([2,3,9])
sage: G.random_element()
f1^2
Create a subgroup of this group. The “big” group must be defined using “named” generators.
INPUT:
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 subgroup isomorphic to C2 x C3 generated by {a*b, a}
sage: H < G
True
sage: F = G.subgroup([a,b^2])
sage: F
Multiplicative Abelian subgroup isomorphic to C2 x C3 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 subgroup isomorphic to Z x Z generated by {a, b}
sage: F.subgroup([c,e])
Multiplicative Abelian subgroup isomorphic to C2 x C3 x C5 x C729 generated by {c, e}
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 subgroup isomorphic to C2 x C4
generated by {f0, f0*f1^2}
sage: AbelianGroup([4,4]).subgroup_reduced( [ [1,0], [1,2] ])
Multiplicative Abelian subgroup isomorphic to C2 x C4
generated by {f1^2, f0}
Compute all the subgroups of this abelian group (which must be finite).
TODO: This is many orders of magnitude slower than Magma.
INPUT:
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 subgroup isomorphic to C2 x C3 generated by {f0*f1^2},
Multiplicative Abelian subgroup isomorphic to C2 generated by {f0},
Multiplicative Abelian subgroup isomorphic to C3 generated by {f1},
Trivial Abelian subgroup]
sage: len(AbelianGroup([2,4,8]).subgroups())
81
TESTS:
sage: AbelianGroup([]).subgroups()
[Trivial Abelian group]
Bases: sage.groups.abelian_gps.abelian_group.AbelianGroup_class
Subgroup subclass of AbelianGroup_class, so instance methods are inherited.
TODO:
Return the ambient group related to self.
OUTPUT:
A multiplicative Abelian group.
EXAMPLES:
sage: G.<a,b,c> = AbelianGroup([2,3,4])
sage: H = G.subgroup([a, b^2])
sage: H.ambient_group() is G
True
Check whether left and right are the same (sub)group.
INPUT:
OUTPUT:
Boolean. If right is a subgroup, test whether left and right are the same subset of the ambient group. If right is not a subgroup, test whether they are isomorphic groups, see is_isomorphic().
EXAMPLES:
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 subgroup isomorphic to C2 x C3 generated by {a, b^2}
sage: F<G
True
sage: A = AbelianGroup(1, [6])
sage: A.subgroup(list(A.gens())) == A
True
sage: G.<a,b> = AbelianGroup(2)
sage: A = G.subgroup([a])
sage: B = G.subgroup([b])
sage: A.equals(B)
False
sage: A == B # sames as A.equals(B)
False
sage: A.is_isomorphic(B)
True
Return the nth generator of this subgroup.
EXAMPLE:
sage: G.<a,b> = AbelianGroup(2)
sage: A = G.subgroup([a])
sage: A.gen(0)
a
Return the generators for this subgroup.
OUTPUT:
A tuple of group elements generating the subgroup.
EXAMPLES:
sage: G.<a,b> = AbelianGroup(2)
sage: A = G.subgroup([a])
sage: G.gens()
(a, b)
sage: A.gens()
(a,)
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
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
(indeed, these
will all be prime powers), fix a
generating set
(with
), for
,
for the group
, and let
be
an element of the direct product
. Find, if they
exist, integers
such that
. In other words, solve
the equation
for
, where
is the matrix whose rows are the
‘s. Of
course, it suffices to restrict the
‘s to the range
, where
denotes the least
common multiple of the integers
.
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