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
""" Cores
A `k`-core is a partition from which no rim hook of size `k` can be removed. Alternatively, a `k`-core is an integer partition such that the Ferrers diagram for the partition contains no cells with a hook of size (a multiple of) `k`.
Authors:
- Anne Schilling and Mike Zabrocki (2011): initial version - Travis Scrimshaw (2012): Added latex output for Core class """ #***************************************************************************** # Copyright (C) 2011 Anne Schilling <anne at math.ucdavis.edu> # Mike Zabrocki <zabrocki at mathstat.yorku.ca> # # Distributed under the terms of the GNU General Public License (GPL) # # This code is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU # General Public License for more details. # # The full text of the GPL is available at: # # http://www.gnu.org/licenses/ #****************************************************************************
from sage.structure.unique_representation import UniqueRepresentation from sage.structure.parent import Parent from sage.combinat.partition import Partitions, Partition from sage.combinat.combinat import CombinatorialElement from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets from sage.functions.other import floor from sage.combinat.combinatorial_map import combinatorial_map
class Core(CombinatorialElement): r""" A `k`-core is an integer partition from which no rim hook of size `k` can be removed.
EXAMPLES::
sage: c = Core([2,1],4); c [2, 1] sage: c = Core([3,1],4); c Traceback (most recent call last): ... ValueError: [3, 1] is not a 4-core """ @staticmethod def __classcall_private__(cls, part, k): r""" Implements the shortcut ``Core(part, k)`` to ``Cores(k,l)(part)`` where `l` is the length of the core.
TESTS::
sage: c = Core([2,1],4); c [2, 1] sage: c.parent() 4-Cores of length 3 sage: type(c) <class 'sage.combinat.core.Cores_length_with_category.element_class'>
sage: Core([2,1],3) Traceback (most recent call last): ... ValueError: [2, 1] is not a 3-core """
def __init__(self, parent, core): """ TESTS::
sage: C = Cores(4,3) sage: c = C([2,1]); c [2, 1] sage: type(c) <class 'sage.combinat.core.Cores_length_with_category.element_class'> sage: c.parent() 4-Cores of length 3 sage: TestSuite(c).run()
sage: C = Cores(3,3) sage: C([2,1]) Traceback (most recent call last): ... ValueError: [2, 1] is not a 3-core """
def __eq__(self, other): """ EXAMPLES::
sage: c = Core([4,2,1,1],5) sage: d = Core([4,2,1,1],5) sage: e = Core([4,2,1,1],6) sage: c == [4,2,1,1] False sage: c == d True sage: c == e False """ else:
def __hash__(self): """ Computes the hash of ``self`` by computing the hash of the underlying list and of the additional parameter. The hash is cached and stored in ``self._hash``.
EXAMPLES::
sage: c = Core([4,2,1,1],3) sage: c._hash is None True sage: hash(c) #random 1335416675971793195 sage: c._hash #random 1335416675971793195
TESTS::
sage: c = Core([4,2,1,1],5) sage: d = Core([4,2,1,1],6) sage: hash(c) == hash(d) False """
def _latex_(self): r""" Output the LaTeX representation of this core as a partition.
See the ``_latex_`` method of :class:`Partition`.
EXAMPLES::
sage: c = Core([2,1],4) sage: latex(c) {\def\lr#1{\multicolumn{1}{|@{\hspace{.6ex}}c@{\hspace{.6ex}}|}{\raisebox{-.3ex}{$#1$}}} \raisebox{-.6ex}{$\begin{array}[b]{*{2}c}\cline{1-2} \lr{\phantom{x}}&\lr{\phantom{x}}\\\cline{1-2} \lr{\phantom{x}}\\\cline{1-1} \end{array}$} } """
def k(self): r""" Returns `k` of the `k`-core ``self``.
EXAMPLES::
sage: c = Core([2,1],4) sage: c.k() 4 """
@combinatorial_map(name="to partition") def to_partition(self): r""" Turns the core ``self`` into the partition identical to ``self``.
EXAMPLES::
sage: mu = Core([2,1,1],3) sage: mu.to_partition() [2, 1, 1] """
@combinatorial_map(name="to bounded partition") def to_bounded_partition(self): r""" Bijection between `k`-cores and `(k-1)`-bounded partitions.
Maps the `k`-core ``self`` to the corresponding `(k-1)`-bounded partition. This bijection is achieved by deleting all cells in ``self`` of hook length greater than `k`.
EXAMPLES::
sage: gamma = Core([9,5,3,2,1,1], 5) sage: gamma.to_bounded_partition() [4, 3, 2, 2, 1, 1] """
def size(self): r""" Returns the size of ``self`` as a partition.
EXAMPLES::
sage: Core([2,1],4).size() 3 sage: Core([4,2],3).size() 6 """
def length(self): r""" Returns the length of ``self``.
The length of a `k`-core is the size of the corresponding `(k-1)`-bounded partition which agrees with the length of the corresponding Grassmannian element, see :meth:`to_grassmannian`.
EXAMPLES::
sage: c = Core([4,2],3); c.length() 4 sage: c.to_grassmannian().length() 4
sage: Core([9,5,3,2,1,1], 5).length() 13 """
def to_grassmannian(self): r""" Bijection between `k`-cores and Grassmannian elements in the affine Weyl group of type `A_{k-1}^{(1)}`.
For further details, see the documentation of the method :meth:`~sage.combinat.partition.Partition.from_kbounded_to_reduced_word` and :meth:`~sage.combinat.partition.Partition.from_kbounded_to_grassmannian`.
EXAMPLES::
sage: c = Core([3,1,1],3) sage: w = c.to_grassmannian(); w [-1 1 1] [-2 2 1] [-2 1 2] sage: c.parent() 3-Cores of length 4 sage: w.parent() Weyl Group of type ['A', 2, 1] (as a matrix group acting on the root space)
sage: c = Core([],3) sage: c.to_grassmannian() [1 0 0] [0 1 0] [0 0 1] """
def affine_symmetric_group_simple_action(self, i): r""" Returns the action of the simple transposition `s_i` of the affine symmetric group on ``self``.
This gives the action of the affine symmetric group of type `A_k^{(1)}` on the `k`-core ``self``. If ``self`` has outside (resp. inside) corners of content `i` modulo `k`, then these corners are added (resp. removed). Otherwise the action is trivial.
EXAMPLES::
sage: c = Core([4,2],3) sage: c.affine_symmetric_group_simple_action(0) [3, 1] sage: c.affine_symmetric_group_simple_action(1) [5, 3, 1] sage: c.affine_symmetric_group_simple_action(2) [4, 2]
This action corresponds to the left action by the `i`-th simple reflection in the affine symmetric group::
sage: c = Core([4,2],3) sage: W = c.to_grassmannian().parent() sage: i=0 sage: c.affine_symmetric_group_simple_action(i).to_grassmannian() == W.simple_reflection(i)*c.to_grassmannian() True sage: i=1 sage: c.affine_symmetric_group_simple_action(i).to_grassmannian() == W.simple_reflection(i)*c.to_grassmannian() True """ else:
def affine_symmetric_group_action(self, w, transposition = False): r""" Returns the (left) action of the affine symmetric group on ``self``.
INPUT:
- ``w`` is a tupe of integers `[w_1,\ldots,w_m]` with `0\le w_j<k`. If transposition is set to be True, then `w = [w_0,w_1]` is interpreted as a transposition `t_{w_0, w_1}` (see :meth:`_transposition_to_reduced_word`).
The output is the (left) action of the product of the corresponding simple transpositions on ``self``, that is `s_{w_1} \cdots s_{w_m}(self)`. See :meth:`affine_symmetric_group_simple_action`.
EXAMPLES::
sage: c = Core([4,2],3) sage: c.affine_symmetric_group_action([0,1,0,2,1]) [8, 6, 4, 2] sage: c.affine_symmetric_group_action([0,2], transposition=True) [4, 2, 1, 1]
sage: c = Core([11,8,5,5,3,3,1,1,1],4) sage: c.affine_symmetric_group_action([2,5],transposition=True) [11, 8, 7, 6, 5, 4, 3, 2, 1] """
def _transposition_to_reduced_word(self, t): r""" Converts the transposition `t = [r,s]` to a reduced word.
INPUT:
- a tuple `[r,s]` such that `r` and `s` are not equivalent mod `k`
OUTPUT:
- a list of integers in `\{0,1,\ldots,k-1\}` representing a reduced word for the transposition `t`
EXAMPLES::
sage: c = Core([],4) sage: c._transposition_to_reduced_word([2, 5]) [2, 3, 0, 3, 2] sage: c._transposition_to_reduced_word([2, 5]) == c._transposition_to_reduced_word([5,2]) True sage: c._transposition_to_reduced_word([2, 2]) Traceback (most recent call last): ... ValueError: t_0 and t_1 cannot be equal mod k
sage: c = Core([],30) sage: c._transposition_to_reduced_word([4, 12]) [4, 5, 6, 7, 8, 9, 10, 11, 10, 9, 8, 7, 6, 5, 4]
sage: c = Core([],3) sage: c._transposition_to_reduced_word([4, 12]) [1, 2, 0, 1, 2, 0, 2, 1, 0, 2, 1] """ else: range(t[1]-floor((t[1]-t[0])/k)-t[0]-1)]
def weak_le(self, other): r""" Weak order comparison on cores.
INPUT:
- ``other`` -- another `k`-core
OUTPUT: a boolean
Returns whether ``self`` <= ``other`` in weak order.
EXAMPLES::
sage: c = Core([4,2],3) sage: x = Core([5,3,1],3) sage: c.weak_le(x) True sage: c.weak_le([5,3,1]) True
sage: x = Core([4,2,2,1,1],3) sage: c.weak_le(x) False
sage: x = Core([5,3,1],6) sage: c.weak_le(x) Traceback (most recent call last): ... ValueError: The two cores do not have the same k """ else:
def weak_covers(self): r""" Returns a list of all elements that cover ``self`` in weak order.
EXAMPLES::
sage: c = Core([1],3) sage: c.weak_covers() [[1, 1], [2]]
sage: c = Core([4,2],3) sage: c.weak_covers() [[5, 3, 1]] """
def strong_le(self, other): r""" Strong order (Bruhat) comparison on cores.
INPUT:
- ``other`` -- another `k`-core
OUTPUT: a boolean
Returns whether ``self`` <= ``other`` in Bruhat (or strong) order.
EXAMPLES::
sage: c = Core([4,2],3) sage: x = Core([4,2,2,1,1],3) sage: c.strong_le(x) True sage: c.strong_le([4,2,2,1,1]) True
sage: x = Core([4,1],4) sage: c.strong_le(x) Traceback (most recent call last): ... ValueError: The two cores do not have the same k """ else:
def contains(self, other): r""" Checks whether ``self`` contains ``other``.
INPUT:
- ``other`` -- another `k`-core or a list
OUTPUT: a boolean
Returns ``True`` if the Ferrers diagram of ``self`` contains the Ferrers diagram of other.
EXAMPLES::
sage: c = Core([4,2],3) sage: x = Core([4,2,2,1,1],3) sage: x.contains(c) True sage: c.contains(x) False """
def strong_covers(self): r""" Returns a list of all elements that cover ``self`` in strong order.
EXAMPLES::
sage: c = Core([1],3) sage: c.strong_covers() [[2], [1, 1]] sage: c = Core([4,2],3) sage: c.strong_covers() [[5, 3, 1], [4, 2, 1, 1]] """
def strong_down_list(self): r""" Returns a list of all elements that are covered by ``self`` in strong order.
EXAMPLES::
sage: c = Core([1],3) sage: c.strong_down_list() [[]] sage: c = Core([5,3,1],3) sage: c.strong_down_list() [[4, 2], [3, 1, 1]] """ return []
def Cores(k, length = None, **kwargs): r""" A `k`-core is a partition from which no rim hook of size `k` can be removed. Alternatively, a `k`-core is an integer partition such that the Ferrers diagram for the partition contains no cells with a hook of size (a multiple of) `k`.
The `k`-cores generally have two notions of size which are useful for different applications. One is the number of cells in the Ferrers diagram with hook less than `k`, the other is the total number of cells of the Ferrers diagram. In the implementation in Sage, the first of notion is referred to as the ``length`` of the `k`-core and the second is the ``size`` of the `k`-core. The class of Cores requires that either the size or the length of the elements in the class is specified.
EXAMPLES:
We create the set of the `4`-cores of length `6`. Here the length of a `k`-core is the size of the corresponding `(k-1)`-bounded partition, see also :meth:`~sage.combinat.core.Core.length`::
sage: C = Cores(4, 6); C 4-Cores of length 6 sage: C.list() [[6, 3], [5, 2, 1], [4, 1, 1, 1], [4, 2, 2], [3, 3, 1, 1], [3, 2, 1, 1, 1], [2, 2, 2, 1, 1, 1]] sage: C.cardinality() 7 sage: C.an_element() [6, 3]
We may also list the set of `4`-cores of size `6`, where the size is the number of boxes in the core, see also :meth:`~sage.combinat.core.Core.size`::
sage: C = Cores(4, size=6); C 4-Cores of size 6 sage: C.list() [[4, 1, 1], [3, 2, 1], [3, 1, 1, 1]] sage: C.cardinality() 3 sage: C.an_element() [4, 1, 1] """ else: raise ValueError("You need to either specify the length or size of the cores considered!")
class Cores_length(UniqueRepresentation, Parent): r""" The class of `k`-cores of length `n`. """
def __init__(self, k, n): """ TESTS::
sage: C = Cores(3, 4) sage: TestSuite(C).run()
"""
def _repr_(self): """ TESTS::
sage: repr(Cores(4, 3)) #indirect doctest '4-Cores of length 3' """
def list(self): r""" Returns the list of all `k`-cores of length `n`.
EXAMPLES::
sage: C = Cores(3,4) sage: C.list() [[4, 2], [3, 1, 1], [2, 2, 1, 1]] """
def from_partition(self, part): r""" Converts the partition ``part`` into a core (as the identity map).
This is the inverse method to :meth:`~sage.combinat.core.Core.to_partition`.
EXAMPLES::
sage: C = Cores(3,4) sage: c = C.from_partition([4,2]); c [4, 2]
sage: mu = Partition([2,1,1]) sage: C = Cores(3,3) sage: C.from_partition(mu).to_partition() == mu True
sage: mu = Partition([]) sage: C = Cores(3,0) sage: C.from_partition(mu).to_partition() == mu True """
Element = Core
class Cores_size(UniqueRepresentation, Parent): r""" The class of `k`-cores of size `n`. """
def __init__(self, k, n): """ TESTS::
sage: C = Cores(3, size = 4) sage: TestSuite(C).run() """
def _repr_(self): """ TESTS::
sage: repr(Cores(4, size = 3)) #indirect doctest '4-Cores of size 3' """
def list(self): r""" Returns the list of all `k`-cores of size `n`.
EXAMPLES::
sage: C = Cores(3, size = 4) sage: C.list() [[3, 1], [2, 1, 1]] """
def from_partition(self, part): r""" Converts the partition ``part`` into a core (as the identity map).
This is the inverse method to :meth:`to_partition`.
EXAMPLES::
sage: C = Cores(3,size=4) sage: c = C.from_partition([2,1,1]); c [2, 1, 1]
sage: mu = Partition([2,1,1]) sage: C = Cores(3,size=4) sage: C.from_partition(mu).to_partition() == mu True
sage: mu = Partition([]) sage: C = Cores(3,size=0) sage: C.from_partition(mu).to_partition() == mu True """
Element = Core |