Coverage for local/lib/python2.7/site-packages/sage/categories/algebra_functor.py : 48%

# -*- coding: utf-8 -*- 

r""" 

Group algebras and beyond: the Algebra functorial construction 

Introduction: group algebras 

============================ 

Let `G` be a group and `R` be a ring. For example:: 

sage: G = DihedralGroup(3) 

sage: R = QQ 

The *group algebra* `A = RG` of `G` over `R` is the space of formal 

linear combinations of elements of `group` with coefficients in `R`:: 

sage: A = G.algebra(R); A 

Algebra of Dihedral group of order 6 as a permutation group 

over Rational Field 

sage: a = A.an_element(); a 

() + 4*(1,2,3) + 2*(1,3) 

This space is endowed with an algebra structure, obtained by extending 

by bilinearity the multiplication of `G` to a multiplication on `RG`:: 

sage: A in Algebras 

True 

sage: a * a 

5*() + 8*(2,3) + 8*(1,2) + 8*(1,2,3) + 16*(1,3,2) + 4*(1,3) 

In particular, the product of two basis elements is induced by the 

product of the corresponding elements of the group, and the unit of 

the group algebra is indexed by the unit of the group:: 

sage: (s, t) = A.algebra_generators() 

sage: s*t 

(1,2) 

sage: A.one_basis() 

() 

sage: A.one() 

() 

For the user convenience and backward compatibility, the group algebra 

can also be constructed with:: 

sage: GroupAlgebra(G, R) 

Algebra of Dihedral group of order 6 as a permutation group 

over Rational Field 

Since :trac:`18700`, both constructions are strictly equivalent:: 

sage: GroupAlgebra(G, R) is G.algebra(R) 

True 

Group algebras are further endowed with a Hopf algebra structure; see 

below. 

Generalizations 

=============== 

The above construction extends to weaker multiplicative structures 

than groups: magmas, semigroups, monoids. For a monoid `S`, we obtain 

the monoid algebra `RS`, which is defined exactly as above:: 

sage: S = Monoids().example(); S 

An example of a monoid: the free monoid generated by ('a', 'b', 'c', 'd') 

sage: A = S.algebra(QQ); A 

Algebra of An example of a monoid: the free monoid generated by ('a', 'b', 'c', 'd') 

over Rational Field 

sage: A.category() 

Category of monoid algebras over Rational Field 

This construction also extends to additive structures: magmas, 

semigroups, monoids, or groups:: 

sage: S = CommutativeAdditiveMonoids().example(); S 

An example of a commutative monoid: 

the free commutative monoid generated by ('a', 'b', 'c', 'd') 

sage: U = S.algebra(QQ); U 

Algebra of An example of a commutative monoid: 

the free commutative monoid generated by ('a', 'b', 'c', 'd') 

over Rational Field 

Despite saying "free module", this is really an algebra, whose 

multiplication is induced by the addition of elements of `S`:: 

sage: U in Algebras(QQ) 

True 

sage: (a,b,c,d) = S.additive_semigroup_generators() 

sage: U(a) * U(b) 

B[a + b] 

To catter uniformly for the use cases above and some others, for `S` a 

set and `K` a ring, we define in Sage the *algebra of `S`* as the 

`K`-free module with basis indexed by `S`, endowed with whatever 

algebraic structure can be induced from that of `S`. 

.. WARNING:: 

In most use cases, the result is actually an algebra, hence the 

name of this construction. In other cases this name is 

misleading:: 

sage: A = Sets().example().algebra(QQ); A 

Algebra of Set of prime numbers (basic implementation) 

over Rational Field 

sage: A.category() 

Category of set algebras over Rational Field 

sage: A in Algebras(QQ) 

False 

Suggestions for a uniform, meaningful, and non misleading name are 

welcome! 

To achieve this flexibility, the features are implemented as a 

:ref:`sage.categories.covariant_functorial_construction` that is 

essentially a hierarchy of categories each providing the relevant 

additional features:: 

sage: A = DihedralGroup(3).algebra(QQ) 

sage: A.categories() 

[Category of finite group algebras over Rational Field, 

... 

Category of group algebras over Rational Field, 

... 

Category of monoid algebras over Rational Field, 

... 

Category of semigroup algebras over Rational Field, 

... 

Category of unital magma algebras over Rational Field, 

... 

Category of magma algebras over Rational Field, 

... 

Category of set algebras over Rational Field, 

...] 

Specifying the algebraic structure 

================================== 

Constructing the algebra of a set endowed with both an 

additive and a multiplicative structure is ambiguous:: 

sage: Z3 = IntegerModRing(3) 

sage: A = Z3.algebra(QQ) 

Traceback (most recent call last): 

... 

TypeError: `S = Ring of integers modulo 3` is both 

an additive and a multiplicative semigroup. 

Constructing its algebra is ambiguous. 

Please use, e.g., S.algebra(QQ, category=Semigroups()) 

This ambiguity can be resolved using the ``category`` argument 

of the construction:: 

sage: A = Z3.algebra(QQ, category=Monoids()); A 

Algebra of Ring of integers modulo 3 over Rational Field 

sage: A.category() 

Category of finite dimensional monoid algebras over Rational Field 

sage: A = Z3.algebra(QQ, category=CommutativeAdditiveGroups()); A 

Algebra of Ring of integers modulo 3 over Rational Field 

sage: A.category() 

Category of finite dimensional commutative additive group algebras 

over Rational Field 

In general, the ``category`` argument can be used to specify which 

structure of `S` shall be extended to `KS`. 

Group algebras, continued 

========================= 

Let us come back to the case of a group algebra `A=RG`. It is endowed 

with more structure and in particular that of a *Hopf algebra*:: 

sage: G = DihedralGroup(3) 

sage: A = G.algebra(R); A 

Algebra of Dihedral group of order 6 as a permutation group 

over Rational Field 

sage: A in HopfAlgebras(R).FiniteDimensional().WithBasis() 

True 

The basis elements are *group-like* for the coproduct: 

`\Delta(g) = g \otimes g`:: 

sage: s 

(1,2,3) 

sage: s.coproduct() 

(1,2,3) # (1,2,3) 

The counit is the constant function `1` on the basis elements:: 

sage: A = GroupAlgebra(DihedralGroup(6), QQ) 

sage: [A.counit(g) for g in A.basis()] 

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 

The antipode is given on basis elements by `\chi(g) = g^{-1}`:: 

sage: A = GroupAlgebra(DihedralGroup(3), QQ) 

sage: s 

(1,2,3) 

sage: s.antipode() 

(1,3,2) 

By Maschke's theorem, for a finite group whose cardinality does not 

divide the characteristic of the base field, the algebra is 

semisimple:: 

sage: SymmetricGroup(5).algebra(QQ) in Algebras(QQ).Semisimple() 

True 

sage: CyclicPermutationGroup(10).algebra(FiniteField(7)) in Algebras.Semisimple 

True 

sage: CyclicPermutationGroup(10).algebra(FiniteField(5)) in Algebras.Semisimple 

False 

Coercions 

========= 

Let `RS` be the algebra of some structure `S`. Then `RS` admits the 

natural coercion from any other algebra `R'S'` of some structure `S'`, 

as long as `R'` coerces into `R` and `S'` coerces into `S`. 

For example, since there is a natural inclusion from the dihedral 

group `D_2` of order 4 into the symmetric group `S_4` of order 4!, and 

since there is a natural map from the integers to the rationals, there 

is a natural map from `\ZZ[D_2]` to `\QQ[S_4]`:: 

sage: A = DihedralGroup(2).algebra(ZZ) 

sage: B = SymmetricGroup(4).algebra(QQ) 

sage: a = A.an_element(); a 

() + 3*(3,4) + 3*(1,2) 

sage: b = B.an_element(); b 

() + 2*(1,2) + 4*(1,2,3,4) 

sage: B(a) 

() + 3*(3,4) + 3*(1,2) 

sage: a * b # a is automatically converted to an element of B 

7*() + 3*(3,4) + 5*(1,2) + 6*(1,2)(3,4) + 12*(1,2,3) + 4*(1,2,3,4) + 12*(1,3,4) 

sage: parent(a * b) 

Symmetric group algebra of order 4 over Rational Field 

There is no obvious map in the other direction, though:: 

sage: A(b) 

Traceback (most recent call last): 

... 

TypeError: do not know how to make x (= () + 2*(1,2) + 4*(1,2,3,4)) 

an element of self 

(=Algebra of Dihedral group of order 4 as a permutation group 

over Integer Ring) 

If `S` is a unital (additive) magma, then `RS` is a unital algebra, 

and thus admits a coercion from its base ring `R` and any ring that 

coerces into `R`. :: 

sage: G = DihedralGroup(2) 

sage: A = G.algebra(ZZ) 

sage: A(2) 

2*() 

If `S` is a multiplicative group, then `RS` admits a coercion from `S` 

and from any group which coerce into `S`:: 

sage: g = DihedralGroup(2).gen(0); g 

(3,4) 

sage: A(g) 

(3,4) 

sage: A(2) * g 

2*(3,4) 

Note that there is an ambiguity if `S'` is a group which coerces into 

both `R` and `S`. For example) if `S` is the additive group `(\ZZ,+)`, 

and `A = RS` is its group algebra, then the integer `2` can be coerced 

into `A` in two ways -- via `S`, or via the base ring `R` -- and *the 

answers are different*. It that case the coercion to `R` takes 

precedence. In particular, if `\ZZ` is the ring (or group) of 

integers, then `\ZZ` will coerce to any `RS`, by sending `\ZZ` to `R`. 

In generic code, it is therefore recommented to always explicitly use 

``A.monomial(g)`` to convert an element of the group into `A`. 

TESTS: 

Given a group and a base ring, the corresponding group algebra is 

unique:: 

sage: A = GL(3, QQ).algebra(ZZ) 

sage: B = GL(3, QQ).algebra(ZZ) 

sage: A is B 

True 

sage: C = GL(3, QQ).algebra(QQ) 

sage: A == C 

False 

Equality tests:: 

sage: AbelianGroup(1).algebra(QQ) == AbelianGroup(1).algebra(QQ) 

True 

sage: AbelianGroup(1).algebra(QQ) == AbelianGroup(1).algebra(ZZ) 

False 

sage: AbelianGroup(2).algebra(QQ) == AbelianGroup(1).algebra(QQ) 

False 

sage: A = KleinFourGroup().algebra(ZZ) 

sage: B = KleinFourGroup().algebra(QQ) 

sage: A == B 

False 

sage: A == A 

True 

Properties of group algebras:: 

sage: SU(2, GF(4, 'a')).algebra(IntegerModRing(12)).category() 

Category of finite group algebras over Ring of integers modulo 12 

sage: SymmetricGroup(2).algebra(QQ).is_commutative() 

True 

sage: SymmetricGroup(3).algebra(QQ).is_commutative() 

False 

sage: G = DihedralGroup(4) 

sage: A = G.algebra(QQ['x']) 

sage: A(1) 

() 

sage: A(2) 

2*() 

sage: A(0) 

0 

sage: A(int(2)).coefficients() 

[2] 

sage: A(int(2)).coefficients()[0].parent() 

Univariate Polynomial Ring in x over Rational Field 

sage: g = G.an_element() 

sage: A(g) 

(1,2,3,4) 

Hopf algebra structure:: 

sage: D4 = DihedralGroup(4) 

sage: kD4 = D4.algebra(GF(7)) 

sage: kD4 in HopfAlgebras 

True 

sage: a = kD4.an_element(); a 

() + 4*(1,2,3,4) + 2*(1,4)(2,3) 

sage: a.antipode() 

() + 4*(1,4,3,2) + 2*(1,4)(2,3) 

sage: a.coproduct() 

() # () + 4*(1,2,3,4) # (1,2,3,4) + 2*(1,4)(2,3) # (1,4)(2,3) 

Coercions from the base ring:: 

sage: A = GL(3, GF(7)).algebra(ZZ); A 

Algebra of General Linear Group of degree 3 over Finite Field of size 7 

over Integer Ring 

sage: A.has_coerce_map_from(GL(3, GF(7))) 

True 

Coercion from the group:: 

sage: G = GL(3, GF(7)) 

sage: ZG = G.algebra(ZZ) 

sage: c, d = G.random_element(), G.random_element() 

sage: zc, zd = ZG(c), ZG(d) 

sage: zc * d == zc * zd # d is automatically converted to an element of ZG 

True 

sage: G = SymmetricGroup(5) 

sage: x,y = G.gens() 

sage: A = G.algebra(QQ) 

sage: A( A(x) ) 

(1,2,3,4,5) 

sage: G = KleinFourGroup() 

sage: f = G.gen(0) 

sage: ZG = GroupAlgebra(G) 

sage: ZG(f) # indirect doctest 

(3,4) 

sage: ZG(1) == ZG(G(1)) 

True 

Coercion from the base ring takes precedences over coercion from the 

group:: 

sage: G = GL(2,7) 

sage: OG = GroupAlgebra(G, ZZ[sqrt(5)]) 

sage: OG(2) 

2*[1 0] 

[0 1] 

sage: OG(G(2)) 

[2 0] 

[0 2] 

sage: OG(FormalSum([ (1, G(2)), (2, RR(0.77)) ]) ) 

Traceback (most recent call last): 

... 

TypeError: Attempt to coerce non-integral RealNumber to Integer 

sage: OG(OG.base_ring().basis()[1]) 

sqrt5*[1 0] 

[0 1] 

Coercions from other group algebras:: 

sage: P = RootSystem(['A',2,1]).weight_lattice() 

sage: W = RootSystem(['A',2,1]).weight_space() 

sage: PA = P.algebra(QQ) 

sage: WA = W.algebra(QQ) 

sage: WA.coerce_map_from(PA) 

Generic morphism: 

From: Algebra of the Weight lattice of the Root system of type ['A', 2, 1] over Rational Field 

To: Algebra of the Weight space over the Rational Field of the Root system of type ['A', 2, 1] over Rational Field 

Using the functor `R \mapsto RG` to build the base ring extension 

morphism:: 

sage: G = SymmetricGroup(3) 

sage: A = G.algebra(ZZ) 

sage: h = GF(5).coerce_map_from(ZZ) 

sage: functor = A.construction()[0]; functor 

GroupAlgebraFunctor 

sage: hh = functor(h) 

sage: hh 

Generic morphism: 

From: Symmetric group algebra of order 3 over Integer Ring 

To: Symmetric group algebra of order 3 over Finite Field of size 5 

sage: a = 2 * A.an_element(); a 

2*() + 4*(1,2) + 8*(1,2,3) 

sage: hh(a) 

2*() + 4*(1,2) + 3*(1,2,3) 

Conversion from a formal sum:: 

sage: G = AbelianGroup(1) 

sage: ZG = G.algebra(ZZ) 

sage: f = G.gen() 

sage: ZG(FormalSum([(1,f), (2, f**2)])) 

f + 2*f^2 

AUTHORS: 

- David Loeffler (2008-08-24): initial version 

- Martin Raum (2009-08): update to use new coercion model -- see 

:trac:`6670`. 

- John Palmieri (2011-07): more updates to coercion, categories, etc., 

group algebras constructed using CombinatorialFreeModule -- see 

:trac:`6670`. 

- Nicolas M. Thiéry (2010-2017), Travis Scrimshaw (2017): 

generalization to a covariant functorial construction for 

monoid algebras, and beyond -- see e.g. :trac:`18700`. 

""" 

#***************************************************************************** 

# Copyright (C) 2010-2017 Nicolas M. Thiéry <nthiery at users.sf.net> 

# 

# Distributed under the terms of the GNU General Public License (GPL) 

# http://www.gnu.org/licenses/ 

#***************************************************************************** 

from sage.categories.pushout import ConstructionFunctor 

from sage.categories.morphism import SetMorphism 

from sage.categories.covariant_functorial_construction import CovariantFunctorialConstruction, CovariantConstructionCategory, FunctorialConstructionCategory 

from sage.categories.category_types import Category_over_base_ring 

# TODO: merge the two univariate functors below into a bivariate one 

class AlgebraFunctor(CovariantFunctorialConstruction): 

r""" 

For a fixed ring, a functor sending a group/... to the 

corresponding group/... algebra. 

EXAMPLES:: 

sage: from sage.categories.algebra_functor import AlgebraFunctor 

sage: F = AlgebraFunctor(QQ); F 

The algebra functorial construction 

sage: F(DihedralGroup(3)) 

Algebra of Dihedral group of order 6 as a permutation group 

over Rational Field 

""" 

_functor_name = "algebra" 

_functor_category = "Algebras" 

def __init__(self, base_ring): 

""" 

EXAMPLES:: 

sage: from sage.categories.algebra_functor import AlgebraFunctor 

sage: F = AlgebraFunctor(QQ); F 

The algebra functorial construction 

sage: TestSuite(F).run() 

""" 

from sage.categories.rings import Rings 

assert base_ring in Rings() 

self._base_ring = base_ring 

def base_ring(self): 

""" 

Return the base ring for this functor. 

EXAMPLES:: 

sage: from sage.categories.algebra_functor import AlgebraFunctor 

sage: AlgebraFunctor(QQ).base_ring() 

Rational Field 

""" 

return self._base_ring 

def __call__(self, G, category=None): 

""" 

Return the algebra of ``G``. 

See :ref:`sage.categories.algebra_functor` for details. 

INPUT: 

- ``G`` -- a group 

- ``category`` -- a category, or ``None`` 

EXAMPLES:: 

sage: from sage.categories.algebra_functor import AlgebraFunctor 

sage: F = AlgebraFunctor(QQ) 

sage: G = DihedralGroup(3) 

sage: A = F(G, category=Monoids()); A 

Algebra of Dihedral group of order 6 as a permutation group 

over Rational Field 

sage: A.category() 

Category of finite dimensional monoid algebras over Rational Field 

""" 

return G.algebra(self._base_ring, category=category) 

class GroupAlgebraFunctor(ConstructionFunctor): 

r""" 

For a fixed group, a functor sending a commutative ring to the 

corresponding group algebra. 

INPUT: 

- ``group`` -- the group associated to each group algebra under 

consideration 

EXAMPLES:: 

sage: from sage.categories.algebra_functor import GroupAlgebraFunctor 

sage: F = GroupAlgebraFunctor(KleinFourGroup()); F 

GroupAlgebraFunctor 

sage: A = F(QQ); A 

Algebra of The Klein 4 group of order 4, as a permutation group over Rational Field 

TESTS:: 

sage: loads(dumps(F)) == F 

True 

sage: A is KleinFourGroup().algebra(QQ) 

True 

""" 

def __init__(self, group): 

r""" 

See :class:`GroupAlgebraFunctor` for full documentation. 

EXAMPLES:: 

sage: from sage.categories.algebra_functor import GroupAlgebraFunctor 

sage: GroupAlgebra(SU(2, GF(4, 'a')), IntegerModRing(12)).category() 

Category of finite group algebras over Ring of integers modulo 12 

""" 

self.__group = group 

from sage.categories.rings import Rings 

ConstructionFunctor.__init__(self, Rings(), Rings()) 

def group(self): 

r""" 

Return the group which is associated to this functor. 

EXAMPLES:: 

sage: from sage.categories.algebra_functor import GroupAlgebraFunctor 

sage: GroupAlgebraFunctor(CyclicPermutationGroup(17)).group() == CyclicPermutationGroup(17) 

True 

""" 

return self.__group 

def _apply_functor(self, base_ring): 

r""" 

Create the group algebra with given base ring over ``self.group()``. 

INPUT : 

- ``base_ring`` -- the base ring of the group algebra 

OUTPUT: 

A group algebra. 

EXAMPLES:: 

sage: from sage.categories.algebra_functor import GroupAlgebraFunctor 

sage: F = GroupAlgebraFunctor(CyclicPermutationGroup(17)) 

sage: F(QQ) 

Algebra of Cyclic group of order 17 as a permutation group 

over Rational Field 

""" 

return self.__group.algebra(base_ring) 

def _apply_functor_to_morphism(self, f): 

r""" 

Lift a homomorphism of rings to the corresponding homomorphism 

of the group algebras of ``self.group()``. 

INPUT: 

- ``f`` -- a morphism of rings 

OUTPUT: 

A morphism of group algebras. 

EXAMPLES:: 

sage: G = SymmetricGroup(3) 

sage: A = GroupAlgebra(G, ZZ) 

sage: h = GF(5).coerce_map_from(ZZ) 

sage: hh = A.construction()[0](h); hh 

Generic morphism: 

From: Symmetric group algebra of order 3 over Integer Ring 

To: Symmetric group algebra of order 3 over Finite Field of size 5 

sage: a = 2 * A.an_element(); a 

2*() + 4*(1,2) + 8*(1,2,3) 

sage: hh(a) 

2*() + 4*(1,2) + 3*(1,2,3) 

""" 

from sage.categories.rings import Rings 

domain = self(f.domain()) 

codomain = self(f.codomain()) 

# we would want to use something like: 

# domain.module_morphism(on_coefficients=h, codomain=codomain, category=Rings()) 

return SetMorphism(domain.Hom(codomain, category=Rings()), 

lambda x: codomain.sum_of_terms((g, f(c)) for (g, c) in x)) 

class AlgebrasCategory(CovariantConstructionCategory, Category_over_base_ring): 

""" 

An abstract base class for categories of monoid algebras, 

groups algebras, and the like. 

.. SEEALSO:: 

- :meth:`Sets.ParentMethods.algebra` 

- :meth:`Sets.SubcategoryMethods.Algebras` 

- :class:`~sage.categories.covariant_functorial_construction.CovariantFunctorialConstruction` 

INPUT: 

- ``base_ring`` -- a ring 

EXAMPLES:: 

sage: C = Groups().Algebras(QQ); C 

Category of group algebras over Rational Field 

sage: C = Monoids().Algebras(QQ); C 

Category of monoid algebras over Rational Field 

sage: C._short_name() 

'Algebras' 

sage: latex(C) # todo: improve that 

\mathbf{Algebras}(\mathbf{Monoids}) 

""" 

_functor_category = "Algebras" 

def _repr_object_names(self): 

""" 

EXAMPLES:: 

sage: Semigroups().Algebras(QQ) # indirect doctest 

Category of semigroup algebras over Rational Field 

""" 

return "{} algebras over {}".format(self.base_category()._repr_object_names()[:-1], 

self.base_ring()) 

@staticmethod 

def __classcall__(cls, category=None, R=None): 

""" 

Make ``CatAlgebras(**)`` a shorthand for ``Cat().Algebras(**)``. 

EXAMPLES:: 

sage: GradedModules(ZZ) # indirect doctest 

Category of graded modules over Integer Ring 

sage: Modules(ZZ).Graded() 

Category of graded modules over Integer Ring 

sage: Modules.Graded(ZZ) 

Category of graded modules over Integer Ring 

sage: GradedModules(ZZ) is Modules(ZZ).Graded() 

True 

.. SEEALSO:: :meth:`_base_category_class` 

.. TODO:: 

The logic is very similar to the default implementation 

:class:`FunctorialConstructionCategory.__classcall__`; 

the only difference is whether the additional arguments 

should be passed to ``Cat`` or to the construction. 

Find a way to refactor this to avoid the duplication. 

""" 

base_category_class = cls._base_category_class[0] 

if isinstance(category, base_category_class): 

return super(FunctorialConstructionCategory, cls).__classcall__(cls, category, R) 

else: 

# category should now be the base ring ... 

return cls.category_of(base_category_class(), category)