"""
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
"""
from sage.misc.classcall_metaclass import ClasscallMetaclass
from sage.structure.unique_representation import UniqueRepresentation
from sage.structure.parent import Parent
from sage.structure.element import Element
from sage.combinat.partition import Partitions, Partition
from sage.combinat.combinat import CombinatorialObject
from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets
from sage.functions.other import floor
class Core(CombinatorialObject, Element):
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
"""
__metaclass__ = ClasscallMetaclass
@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
"""
if isinstance(part, cls):
return part
part = Partition(part)
if not part.is_core(k):
raise ValueError, "%s is not a %s-core"%(part, k)
l = sum(part.k_boundary(k).row_lengths())
return Cores(k, l)(part)
def __init__(self, core, parent):
"""
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
"""
k = parent.k
part = Partition(core)
if not part.is_core(k):
raise ValueError, "%s is not a %s-core"%(part, k)
CombinatorialObject.__init__(self, core)
Element.__init__(self, parent)
def _latex_(self):
"""
Outputs the LaTeX representation of this core using its Ferrers diagram.
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]{cc}
\cline{1-1}\cline{2-2}
\lr{\phantom{x}}&\lr{\phantom{x}}\\
\cline{1-1}\cline{2-2}
\lr{\phantom{x}}\\
\cline{1-1}
\end{array}$}
}
"""
return self.to_partition()._latex_()
def k(self):
r"""
Returns `k` of the `k`-core ``self``.
EXAMPLES::
sage: c = Core([2,1],4)
sage: c.k()
4
"""
return self.parent().k
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]
"""
return Partition(self)
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]
"""
k_boundary = self.to_partition().k_boundary(self.k())
return Partition(k_boundary.row_lengths())
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
"""
return self.to_partition().size()
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
"""
return self.to_bounded_partition().size()
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_class.from_kbounded_to_reduced_word` and
:meth:`~sage.combinat.partition.Partition_class.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]
"""
return self.to_bounded_partition().from_kbounded_to_grassmannian(self.k()-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
"""
mu = self.to_partition()
corners = mu.outside_corners()
corners = [ p for p in corners if mu.content(p[0],p[1])%self.k()==i ]
if corners == []:
corners = mu.corners()
corners = [ p for p in corners if mu.content(p[0],p[1])%self.k()==i ]
if corners == []:
return self
for p in corners:
mu = mu.remove_cell(p[0])
else:
for p in corners:
mu = mu.add_cell(p[0])
return Core(mu, self.k())
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]
"""
c = self
if transposition:
w = self._transposition_to_reduced_word(w)
w.reverse()
for i in w:
c = c.affine_symmetric_group_simple_action(i)
return c
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`
EXAMPLE::
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):
...
AssertionError: 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]
"""
k = self.k()
assert (t[0]-t[1])%k != 0, "t_0 and t_1 cannot be equal mod k"
if t[0] > t[1]:
return self._transposition_to_reduced_word([t[1],t[0]])
else:
return [i%k for i in range(t[0],t[1]-floor((t[1]-t[0])/k))] + [(t[1]-floor((t[1]-t[0])/k)-2-i)%(k) for i in
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):
...
AssertionError: The two cores do not have the same k
"""
if type(self) == type(other):
assert self.k() == other.k(), "The two cores do not have the same k"
else:
other = Core(other, self.k())
w = self.to_grassmannian()
v = other.to_grassmannian()
return w.weak_le(v, side='left')
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()
[[2], [1, 1]]
sage: c = Core([4,2],3)
sage: c.weak_covers()
[[5, 3, 1]]
"""
w = self.to_grassmannian()
S = w.upper_covers(side='left')
S = [x for x in S if x.is_affine_grassmannian()]
return [ x.affine_grassmannian_to_core() for x in set(S) ]
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):
...
AssertionError: The two cores do not have the same k
"""
if type(self) == type(other):
assert self.k() == other.k(), "The two cores do not have the same k"
else:
other = Core(other, self.k())
w = self.to_grassmannian()
v = other.to_grassmannian()
return w.bruhat_le(v)
def contains(self, other):
r"""
Checks whether ``self`` contains other.
INPUT:
- other - another `k`-core
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
"""
la = self.to_partition()
mu = other.to_partition()
return la.contains(mu)
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]]
"""
w = self.to_grassmannian()
S = w.bruhat_upper_covers()
S = [x for x in S if x.is_affine_grassmannian()]
return [ x.affine_grassmannian_to_core() for x in set(S) ]
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]
"""
if length is None and 'size' in kwargs:
return Cores_size(k,kwargs['size'])
elif length is not None:
return Cores_length(k,length)
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()
"""
self.k = k
self.n = n
Parent.__init__(self, category = FiniteEnumeratedSets())
def _repr_(self):
"""
TESTS::
sage: repr(Cores(4, 3)) #indirect doctest
'4-Cores of length 3'
"""
return "%s-Cores of length %s"%(self.k,self.n)
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]]
"""
return [la.to_core(self.k-1) for la in Partitions(self.n, max_part=self.k-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
"""
return Core(part, self.k)
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()
"""
self.k = k
self.n = n
Parent.__init__(self, category = FiniteEnumeratedSets())
def _repr_(self):
"""
TESTS::
sage: repr(Cores(4, size = 3)) #indirect doctest
'4-Cores of size 3'
"""
return "%s-Cores of size %s"%(self.k,self.n)
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]]
"""
k_cores = Partitions(self.n).filter(lambda x: x.is_core(self.k))
return [ Core(x, self.k) for x in k_cores ]
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
"""
return Core(part, self.k)
Element = Core
