Multiplicative Abelian Groups¶
This module lets you compute with finitely generated Abelian groups of the form
It is customary to denote the infinite cyclic group \(\ZZ\) as having order \(0\), so the data defining the Abelian group can be written as an integer vector
where there are \(r\) zeroes and \(t\) non-zero values. To construct this Abelian group in Sage, you can either specify all entries of \(\vec{k}\) 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 \(1\) 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 \(\ZZ_6 = \ZZ_2
\times \ZZ_3\). The orders of the generators
\(\vec{k}=(0,\dots,0,k_1,\dots, k_t)\) 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 \(\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
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
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:
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()
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:
- [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.
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
- Volker Braun (2012-11) port to new Parent base. Use tuples for immutables. Rename invariants to gens_orders.
-
sage.groups.abelian_gps.abelian_group.
AbelianGroup
(n, gens_orders=None, names='f')¶ Create the multiplicative abelian group in \(n\) generators with given orders of generators (which need not be prime powers).
INPUT:
n
– integer (optional). If not specified, will be derived- from
gens_orders
.
gens_orders
– a list of non-negative integers in the form- \([a_0, a_1, \dots, a_{n-1}]\), 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 \(0\) 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
isfi
, 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 \(0\)‘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)
-
sage.groups.abelian_gps.abelian_group.
AbelianGroup_class
¶ 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:
generator_orders
– list of integers. The orders of the (commuting) generators. Zero denotes an infinite cyclic generator.names
– names of the group generators (optional).
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 False sage: Z2xZ3.is_isomorphic(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 enumerated commutative groups
-
sage.groups.abelian_gps.abelian_group.
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.
-
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’.
EXAMPLES:
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
- Might have unpleasant effect when the word problem cannot be solved.
- 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.