Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
r""" Multiplicative Abelian Groups
This module lets you compute with finitely generated Abelian groups of the form
.. MATH::
G = \ZZ^r \oplus \ZZ_{k_1} \oplus \cdots \oplus \ZZ_{k_t}
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
.. MATH::
\vec{k} = (0, \dots, 0, k_1, \dots, k_t)
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 :meth:`~AbelianGroup_class.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
.. MATH::
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
.. MATH::
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:
.. MATH::
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 :func:`AbelianGroup` function to create an abelian group, and the :meth:`~AbelianGroup_class.gen` and :meth:`~AbelianGroup_class.gens` methods to obtain the corresponding generators. You can print the generators as arbitrary strings using the optional ``names`` argument to the :func:`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. """
#***************************************************************************** # Copyright (C) 2006 William Stein <wstein@gmail.com> # Copyright (C) 2006 David Joyner <wdjoyner@gmail.com> # Copyright (C) 2012 Volker Braun <vbraun.name@gmail.com> # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 2 of the License, or # (at your option) any later version. # http://www.gnu.org/licenses/ #***************************************************************************** from __future__ import print_function from six.moves import range import six
from sage.rings.integer import Integer from sage.rings.integer_ring import ZZ from sage.structure.category_object import normalize_names from sage.structure.unique_representation import UniqueRepresentation from sage.rings.infinity import infinity from sage.arith.all import divisors, gcd, lcm from sage.groups.abelian_gps.abelian_group_element import AbelianGroupElement from sage.misc.cachefunc import cached_method from sage.misc.all import prod from sage.misc.mrange import mrange, cartesian_product_iterator from sage.groups.group import AbelianGroup as AbelianGroupBase from sage.categories.groups import Groups
# TODO: this uses perm groups - the AbelianGroupElement instance method # uses a different implementation. def word_problem(words, g, verbose = False): r""" 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::
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. """
def _normalize(n, gens_orders=None, names="f"): """ Helper function for :func:`AbelianGroup`. Beat some sense into the arguments.
This function is also used by some descendents of :class:`AbelianGroup_class`.
INPUT:
See :func:`AbelianGroup`
OUTPUT:
Unique data for defining a :class:`AbelianGroup_class`. Raises an exception if the input is invalid.
EXAMPLES::
sage: from sage.groups.abelian_gps.abelian_group import _normalize sage: _normalize(5, [2,1,0], names='abc') ((0, 0, 2, 1, 0), 'abc') sage: _normalize(5, (2.0, 1.0, 0/1), names=list('abc')) ((0, 0, 2, 1, 0), ('a', 'b', 'c')) sage: _normalize([0,2,1,0], names='a') ((0, 2, 1, 0), 'a')
TESTS::
sage: _normalize(5, (2.0, 1.5, 0/1), names=list('abc')) Traceback (most recent call last): ... TypeError: Attempt to coerce non-integral RealNumber to Integer sage: _normalize('1', '[2]', names='a') Traceback (most recent call last): ... TypeError: unable to convert '[' to an integer sage: _normalize(3, 'str', names='a') Traceback (most recent call last): ... TypeError: unable to convert 's' to an integer """ else:
def AbelianGroup(n, gens_orders=None, names="f"): r""" 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`` 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 `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) """
def 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 """
class AbelianGroup_class(UniqueRepresentation, AbelianGroupBase): """ The parent for Abelian groups with chosen generator orders.
.. warning::
You should use :func:`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 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
TESTS::
sage: AbelianGroup([]).gens_orders() () sage: AbelianGroup([1]).gens_orders() (1,) sage: AbelianGroup([1,1]).gens_orders() (1, 1) sage: AbelianGroup(0).gens_orders() () """ Element = AbelianGroupElement
def __init__(self, generator_orders, names): """ The Python constructor
TESTS::
sage: G = AbelianGroup([0,5,0,7],names = list("abcd")); G Multiplicative Abelian group isomorphic to Z x C5 x Z x C7 sage: TestSuite(G).run()
We check that :trac:`15140` is fixed::
sage: A = AbelianGroup([3,3]) sage: A.category() Category of finite enumerated commutative groups sage: A = AbelianGroup([3,0,7]) sage: A.category() Category of infinite commutative groups """ else:
def is_isomorphic(left, right): """ Check whether ``left`` and ``right`` are isomorphic
INPUT:
- ``right`` -- anything.
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 """
__eq__ = is_isomorphic
def __ne__(left, right): """ Check whether ``left`` and ``right`` are not isomorphic
OUTPUT:
Boolean.
EXAMPLES::
sage: G1 = AbelianGroup([2,3,4,5]) sage: G2 = AbelianGroup([2,3,4,5,1]) sage: G1 != G2 False sage: G1.__ne__(G2) False """
def is_subgroup(left, right): """ 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 """
__le__ = is_subgroup
def __ge__(left, right): """ Test whether ``right`` is a subgroup of ``left``
EXAMPLES::
sage: G.<a, b> = AbelianGroup(2) sage: H.<c> = AbelianGroup(1) sage: G >= H False """
def __lt__(left, right): """ Test whether ``left`` is a strict subgroup of ``right``
EXAMPLES::
sage: G.<a, b> = AbelianGroup(2) sage: H.<c> = AbelianGroup(1) sage: H < G False """
def __gt__(left, right): """ Test whether ``right`` is a strict subgroup of ``left``
EXAMPLES::
sage: G.<a, b> = AbelianGroup(2) sage: H.<c> = AbelianGroup(1) sage: G > H False """
def is_trivial(self): """ 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 """
def __bool__(self): """ Returns True if this group is nontrivial.
EXAMPLES::
sage: T = AbelianGroup([2, 3]) sage: bool(T) # indirect doctest True sage: bool(AbelianGroup([])) False sage: bool(AbelianGroup([1,1,1])) False """
__nonzero__ = __bool__
@cached_method def dual_group(self, names="X", base_ring=None): """ Return the dual group.
INPUT:
- ``names`` -- string or list of strings. The generator names for the dual group.
- ``base_ring`` -- the base ring. If ``None`` (default), then a suitable cyclotomic field is picked automatically.
OUTPUT:
The :class:`~sage.groups.abelian_gps.dual_abelian_group.DualAbelianGroup_class <dual abelian group>`
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: group must be finite """
@cached_method def elementary_divisors(self): r""" 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.)
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,) """
@cached_method def exponent(self): """ 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 """
def identity(self): r""" 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 """
def _group_notation(self, eldv): """ Return abstract group notation for generator orders ``eldv``
INPUT:
- ``eldv`` -- iterable of integers.
OUTPUT:
String.
EXAMPLES::
sage: G = AbelianGroup([2,2]) sage: G._group_notation([0,1,2,3]) 'Z x C1 x C2 x C3' """ else:
def _latex_(self): r""" Return latex representation of this group.
EXAMPLES::
sage: F = AbelianGroup(10, [2]*10) sage: F._latex_() '$\\mathrm{AbelianGroup}( 10, (2, 2, 2, 2, 2, 2, 2, 2, 2, 2) )$' """
def _gap_init_(self): r""" Return string that defines corresponding abelian group in GAP.
EXAMPLES::
sage: G = AbelianGroup([2,3,9]) sage: G._gap_init_() 'AbelianGroup([2, 3, 9])' sage: gap(G) Group( [ f1, f2, f3 ] )
Requires the optional ``gap_packages`` for infinite 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_() # optional - gap_packages 'AbelianPcpGroup([0, 3, 4])' """ from sage.misc.package import is_package_installed, PackageNotFoundError if is_package_installed('gap_packages'): # Make sure to LoadPackage("Polycyclic") in gap return 'AbelianPcpGroup(%s)'%list(self.gens_orders()) raise PackageNotFoundError("gap_packages")
def gen(self, 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.gens_orders() (0, 0, 0, 0, 0)
sage: G = AbelianGroup([2,1,3]) sage: G.gens() (f0, 1, f2) """ raise IndexError("Argument i (= %s) must be between 0 and %s."%(i, n-1))
def gens(self): """ Return the generators of the group.
OUTPUT:
A tuple of group elements. The generators according to the chosen :meth:`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] """
def gens_orders(self): """ Return the orders of the cyclic factors that this group has been defined with.
Use :meth:`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: list(map(type, F.gens_orders())) [<type 'sage.rings.integer.Integer'>, <type 'sage.rings.integer.Integer'>, <type 'sage.rings.integer.Integer'>] """
def invariants(self): """ 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 :meth:`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 this (0, f0, 2) (1, f1, +Infinity) (2, f2, 3) (3, f3, 2) (4, f4, 4)
Use :meth:`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: list(map(type, F.gens_orders())) [<type 'sage.rings.integer.Integer'>, <type 'sage.rings.integer.Integer'>, <type 'sage.rings.integer.Integer'>] """ # TODO: deprecate
def is_cyclic(self): """ 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 """
@cached_method def ngens(self): """ The number of free generators of the abelian group.
EXAMPLES::
sage: F = AbelianGroup(10000) sage: F.ngens() 10000 """
@cached_method def order(self): """ 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 """
cardinality = order
def permutation_group(self): r""" 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 [(3,4,5), (1,2)] """
def is_commutative(self): """ 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 """
def random_element(self): """ Return a random element of this group.
EXAMPLES::
sage: G = AbelianGroup([2,3,9]) sage: G.random_element() f1^2 """ order = 42 # infinite order; randomly chosen maximum
def _repr_(self): """ Return a string representation of ``self``.
EXAMPLES::
sage: G = AbelianGroup([2,3,9]) sage: G._repr_() 'Multiplicative Abelian group isomorphic to C2 x C3 x C9' """
def 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
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} """ raise TypeError('Subgroup generators must belong to the given group.')
def list(self): """ 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,) """ raise NotImplementedError("group must be finite")
def __len__(self): """ Return the length of ``self``.
EXAMPLES::
sage: G = AbelianGroup(2,[2,3]) sage: len(G) 6 sage: G = AbelianGroup(3,[2,3,0]) sage: len(G) Traceback (most recent call last): ... NotImplementedError: group must be finite """
def __iter__(self): """ Return an iterator over the elements of this group.
EXAMPLES::
sage: G = AbelianGroup([2,3], names = "ab") sage: [a for a in G] [1, b, b^2, a, a*b, a*b^2] sage: L = list(G); L [1, b, b^2, a, a*b, a*b^2]
The returned list is a reference; mutating it does not allow the user to (accidentally?) alter the computed generators::
sage: L[0] = 0 sage: list(G) [1, b, b^2, a, a*b, a*b^2] sage: G = AbelianGroup([1], names="a") sage: list(G) [1] sage: G = AbelianGroup([]) sage: G.list() (1,) sage: list(G) [1] """
def subgroups(self, check=False): r""" 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 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]
Check that :trac:`14196` is fixed::
sage: B = AbelianGroup([1,2]) sage: B.subgroups() [Multiplicative Abelian subgroup isomorphic to C2 generated by {f1}, Trivial Abelian subgroup] """ raise ValueError("group must be finite")
# H = the subgroup of *index* H.
from sage.interfaces.all import gap verbose("Running Gap cross-check") t = ZZ(gap.eval("Size(SubgroupsSolvableGroup(AbelianGroup(%s)))" % v)) if t != len(subgps): raise ArithmeticError("For %s Gap finds %s subgroups, I found %s" % (v, t, len(subgps))) verbose("Gap check OK for %s: %s" % (v, t))
def subgroup_reduced(self,elts, verbose=False): r""" 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.
EXAMPLES::
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} """ except ValueError as e: # can't happen? print("Vectors not LI: {}".format(elts)) raise e for i in range(d)]) for x in new_basis if x[1] != 1])
class AbelianGroup_subgroup(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. """ def __init__(self, ambient, gens, names="f"): """ EXAMPLES::
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 subgroup isomorphic to Z x Z generated by {a^3, b} sage: F.subgroup([c]) Multiplicative Abelian subgroup isomorphic to C2 x C3 x C5 generated by {c} sage: F.subgroup([a, c]) Multiplicative Abelian subgroup isomorphic to C2 x C3 x C5 x Z generated by {a, c} sage: F.subgroup([a, b*c]) Multiplicative Abelian subgroup isomorphic to Z x Z generated by {a, b*c} sage: F.subgroup([b*c, d]) Multiplicative Abelian subgroup isomorphic to C64 x Z generated by {b*c, d} sage: F.subgroup([a*b, c^6, d],names=list("xyz")) Multiplicative Abelian subgroup isomorphic to C5 x C64 x Z generated by {a*b, c^6, d} sage: H.<x,y,z> = F.subgroup([a*b, c^6, d]); H Multiplicative Abelian subgroup isomorphic to C5 x C64 x Z generated by {a*b, c^6, d} sage: G = F.subgroup([a*b, c^6, d],names = list("xyz")); G Multiplicative Abelian subgroup isomorphic to C5 x C64 x Z 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 subgroup isomorphic to C3 x C5 generated by {a, b} sage: A.subgroup([a,b,c,d^2,e]) Multiplicative Abelian subgroup 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 subgroup isomorphic to C3 x C4 x C5 x C5 x C7 generated by {a, b, c, d^2, e^2} sage: B = A.subgroup([a^3, b, c, d, e^2]); B Multiplicative Abelian subgroup isomorphic to C4 x C5 x C5 x C7 generated by {b, c, d, e^2} sage: B.gens_orders() (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.gens_orders() (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]); B Multiplicative Abelian subgroup isomorphic to C3 x C7 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 subgroup isomorphic to C2 x C3 x Z generated by {a, b^2, c}
sage: F.gens_orders() (2, 3, 0) sage: F.gens() (a, b^2, c) sage: F.order() +Infinity """ raise TypeError("ambient (=%s) must be an abelian group."%ambient) raise TypeError("gens (=%s) must be a tuple"%gens)
ambient_invs[Ggens.index(x)] != 0] ambient_invs[Ggens.index(x)] == 0] ## ^^ only look at "finite" names # computes the gens of H which do not occur ^^ in the infinite part of G # the "infinite" generators of H else: # invs0==[]: # a GAP command which returns the "invariants" of the # subgroup as an AbelianPcpGroup, RelativeOrdersOfPcp(Pcp(G)), # works if G is the subgroup declared as a AbelianPcpGroup
def __contains__(self, x): """ Test whether ``x`` is an element of this subgroup.
EXAMPLES::
sage: G.<a,b> = AbelianGroup(2) sage: A = G.subgroup([a]) sage: a in G True sage: a in A True """ return False return True x *= g**(x.list()[a]/g.list()[a]) else: for g in self._gens: if g.list()[a] == 0: continue if abs(x.list()[a]%g.list()[a])%abs(amb_inv[a]) < x.list()[a]%abs(amb_inv[a]): x *= g**((-1)*(x.list()[a]/g.list()[a])) if x.list()[a] == 0: break
def ambient_group(self): """ 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 """
def equals(left, right): """ Check whether ``left`` and ``right`` are the same (sub)group.
INPUT:
- ``right`` -- anything.
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 :meth:`~AbelianGroup_class.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 """ # right is not a subgroup return False
__eq__ = equals
def _repr_(self): """ Return a string representation
EXAMPLES::
sage: G.<a,b> = AbelianGroup(2) sage: G._repr_() 'Multiplicative Abelian group isomorphic to Z x Z' sage: A = G.subgroup([a]) sage: A._repr_() 'Multiplicative Abelian subgroup isomorphic to Z generated by {a}' """
def gens(self): """ 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,) """
def gen(self, n): """ Return the nth generator of this subgroup.
EXAMPLES::
sage: G.<a,b> = AbelianGroup(2) sage: A = G.subgroup([a]) sage: A.gen(0) a """
|