# The Hillman-Grassl correspondence¶

This module implements weak reverse plane partitions and four correspondences on them: the Hillman-Grassl correspondence and its inverse, as well as the Sulzgruber correspondence and its inverse (the Pak correspondence).

Fix a partition $$\lambda$$ (see Partition()). We draw all partitions and tableaux in English notation.

A $$\lambda$$-array will mean a tableau of shape $$\lambda$$ whose entries are nonnegative integers. (No conditions on the order of these entries are made. Note that $$0$$ is allowed.)

A weak reverse plane partition of shape $$\lambda$$ (short: $$\lambda$$-rpp) will mean a $$\lambda$$-array whose entries weakly increase along each row and weakly increase along each column. (The name “weak reverse plane partition” comes from Stanley in [EnumComb2] Section 7.22; other authors – such as Pak [Sulzgr2017], or Hillman and Grassl in [HilGra1976] – just call it a reverse plane partition.)

The Hillman-Grassl correspondence is a bijection from the set of $$\lambda$$-arrays to the set of $$\lambda$$-rpps. For its definition, see hillman_grassl(); for its inverse, see hillman_grassl_inverse().

The Sulzgruber correspondence $$\Phi_\lambda$$ and the Pak correspondence $$\xi_\lambda$$ are two further mutually inverse bijections between the set of $$\lambda$$-arrays and the set of $$\lambda$$-rpps. They appear (sometimes with different definitions, but defining the same maps) in [Pak2002], [Hopkins2017] and [Sulzgr2017]. For their definitions, see sulzgruber_correspondence() and pak_correspondence().

EXAMPLES:

We construct a $$\lambda$$-rpp for $$\lambda = (3, 3, 1)$$ (note that $$\lambda$$ needs not be specified explicitly):

sage: p = WeakReversePlanePartition([[0, 1, 3], [2, 4, 4], [3]])
sage: p.parent()
Weak Reverse Plane Partitions


(This is the example in Section 7.22 of [EnumComb2].)

Next, we apply the inverse of the Hillman-Grassl correspondence to it:

sage: HGp = p.hillman_grassl_inverse(); HGp
[[1, 2, 0], [1, 0, 1], [1]]
sage: HGp.parent()
Tableaux


This is a $$\lambda$$-array, encoded as a tableau. We can recover our original $$\lambda$$-rpp from it using the Hillman-Grassl correspondence:

sage: HGp.hillman_grassl() == p
True


We can also apply the Pak correspondence to our rpp:

sage: Pp = p.pak_correspondence(); Pp
[[2, 0, 1], [0, 2, 0], [1]]
sage: Pp.parent()
Tableaux


This is undone by the Sulzgruber correspondence:

sage: Pp.sulzgruber_correspondence() == p
True


These four correspondences can also be accessed as standalone functions (hillman_grassl_inverse(), hillman_grassl(), pak_correspondence() and sulzgruber_correspondence()) that transform lists of lists into lists of lists; this may be more efficient. For example, the above computation of HGp can also be obtained as follows:

sage: from sage.combinat.hillman_grassl import hillman_grassl_inverse
sage: HGp_bare = hillman_grassl_inverse([[0, 1, 3], [2, 4, 4], [3]])
sage: HGp_bare
[[1, 2, 0], [1, 0, 1], [1]]
sage: isinstance(HGp_bare, list)
True


REFERENCES:

AUTHORS:

• Darij Grinberg and Tom Roby (2018): Initial implementation

class sage.combinat.hillman_grassl.WeakReversePlanePartition(parent, t)

A weak reverse plane partition (short: rpp).

A weak reverse plane partition is a tableau with nonnegative entries that are weakly increasing in each row and weakly increasing in each column.

EXAMPLES:

sage: x = WeakReversePlanePartition([[0, 1, 1], [0, 1, 3], [1, 2, 2], [1, 2, 3], [2]]); x
[[0, 1, 1], [0, 1, 3], [1, 2, 2], [1, 2, 3], [2]]
sage: x.pp()
0  1  1
0  1  3
1  2  2
1  2  3
2
sage: x.shape()
[3, 3, 3, 3, 1]

conjugate()

Return the conjugate of self.

EXAMPLES:

sage: c = WeakReversePlanePartition([[1,1],[1,3],[2]]).conjugate(); c
[[1, 1, 2], [1, 3]]
sage: c.parent()
Weak Reverse Plane Partitions

hillman_grassl_inverse()

Return the image of the $$\lambda$$-rpp self under the inverse of the Hillman-Grassl correspondence (as a Tableau).

Fix a partition $$\lambda$$ (see Partition()). We draw all partitions and tableaux in English notation.

A $$\lambda$$-array will mean a tableau of shape $$\lambda$$ whose entries are nonnegative integers. (No conditions on the order of these entries are made. Note that $$0$$ is allowed.)

A weak reverse plane partition of shape $$\lambda$$ (short: $$\lambda$$-rpp) will mean a $$\lambda$$-array whose entries weakly increase along each row and weakly increase along each column.

The inverse $$H^{-1}$$ of the Hillman-Grassl correspondence (see (hillman_grassl() for the latter) sends a $$\lambda$$-rpp $$\pi$$ to a $$\lambda$$-array $$H^{-1}(\pi)$$ constructed recursively as follows:

• If all entries of $$\pi$$ are $$0$$, then $$H^{-1}(\pi) = \pi$$.

• Otherwise, let $$s$$ be the index of the leftmost column of $$\pi$$ containing a nonzero entry. Write the $$\lambda$$-array $$M$$ as $$(m_{i, j})$$.

• Define a sequence $$((i_1, j_1), (i_2, j_2), \ldots, (i_n, j_n))$$ of boxes in the diagram of $$\lambda$$ (actually a lattice path made of northward and eastward steps) as follows: Let $$(i_1, j_1)$$ be the bottommost box in the $$s$$-th column of $$\pi$$. If $$(i_k, j_k)$$ is defined for some $$k \geq 1$$, then $$(i_{k+1}, j_{k+1})$$ is constructed as follows: If $$q_{i_k - 1, j_k}$$ is well-defined and equals $$q_{i_k, j_k}$$, then we set $$(i_{k+1}, j_{k+1}) = (i_k - 1, j_k)$$. Otherwise, we set $$(i_{k+1}, j_{k+1}) = (i_k, j_k + 1)$$ if this is still a box of $$\lambda$$. Otherwise, the sequence ends here.

• Let $$\pi'$$ be the $$\lambda$$-rpp obtained from $$\pi$$ by subtracting $$1$$ from the $$(i_k, j_k)$$-th entry of $$\pi$$ for each $$k \in \{1, 2, \ldots, n\}$$.

• Let $$N'$$ be the image $$H^{-1}(\pi')$$ (which is already constructed by recursion). Then, $$H^{-1}(\pi)$$ is obtained from $$N'$$ by adding $$1$$ to the $$(i_n, s)$$-th entry of $$N'$$.

This construction appears in [HilGra1976] Section 6 (where $$\lambda$$-arrays are re-encoded as sequences of “hook number multiplicities”) and [EnumComb2] Section 7.22.

hillman_grassl_inverse() for the inverse of the Hillman-Grassl correspondence as a standalone function.

hillman_grassl() for the inverse map.

EXAMPLES:

sage: a = WeakReversePlanePartition([[2, 2, 4], [2, 3, 4], [3, 5]])
sage: a.hillman_grassl_inverse()
[[2, 1, 1], [0, 2, 0], [1, 1]]
sage: b = WeakReversePlanePartition([[1, 1, 2, 2], [1, 1, 2, 2], [2, 2, 3, 3], [2, 2, 3, 3]])
sage: B = b.hillman_grassl_inverse(); B
[[1, 0, 1, 0], [0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]]
sage: b.parent(), B.parent()
(Weak Reverse Plane Partitions, Tableaux)


Applying the inverse of the Hillman-Grassl correspondence to the transpose of a $$\lambda$$-rpp $$M$$ yields the same result as applying it to $$M$$ and then transposing the result ([Gans1981] Corollary 3.4):

sage: a = WeakReversePlanePartition([[1,3,5],[2,4]])
sage: aic = a.hillman_grassl_inverse().conjugate()
sage: aic == a.conjugate().hillman_grassl_inverse()
True

pak_correspondence()

Return the image of the $$\lambda$$-rpp self under the Pak correspondence (as a Tableau).

The Pak correspondence is the map $$\xi_\lambda$$ from [Sulzgr2017] Section 7, and is the map $$\xi_\lambda$$ from [Pak2002] Section 4. It is the inverse of the Sulzgruber correspondence (sulzgruber_correspondence()). The following description of the Pak correspondence follows [Hopkins2017] (which denotes it by $$\mathcal{RSK}^{-1}$$):

Fix a partition $$\lambda$$ (see Partition()). We draw all partitions and tableaux in English notation.

A $$\lambda$$-array will mean a tableau of shape $$\lambda$$ whose entries are nonnegative integers. (No conditions on the order of these entries are made. Note that $$0$$ is allowed.)

A weak reverse plane partition of shape $$\lambda$$ (short: $$\lambda$$-rpp) will mean a $$\lambda$$-array whose entries weakly increase along each row and weakly increase along each column.

We shall also use the following notation: If $$(u, v)$$ is a cell of $$\lambda$$, and if $$\pi$$ is a $$\lambda$$-rpp, then:

• the lower bound of $$\pi$$ at $$(u, v)$$ (denoted by $$\pi_{<(u, v)}$$) is defined to be $$\max \{ \pi_{u-1, v} , \pi_{u, v-1} \}$$ (where $$\pi_{0, v}$$ and $$\pi_{u, 0}$$ are understood to mean $$0$$).

• the upper bound of $$\pi$$ at $$(u, v)$$ (denoted by $$\pi_{>(u, v)}$$) is defined to be $$\min \{ \pi_{u+1, v} , \pi_{u, v+1} \}$$ (where $$\pi_{i, j}$$ is understood to mean $$+ \infty$$ if $$(i, j)$$ is not in $$\lambda$$; thus, the upper bound at a corner cell is $$+ \infty$$).

• toggling $$\pi$$ at $$(u, v)$$ means replacing the entry $$\pi_{u, v}$$ of $$\pi$$ at $$(u, v)$$ by $$\pi_{<(u, v)} + \pi_{>(u, v)} - \pi_{u, v}$$ (this is well-defined as long as $$(u, v)$$ is not a corner of $$\lambda$$).

Note that every $$\lambda$$-rpp $$\pi$$ and every cell $$(u, v)$$ of $$\lambda$$ satisfy $$\pi_{<(u, v)} \leq \pi_{u, v} \leq \pi_{>(u, v)}$$. Note that toggling a $$\lambda$$-rpp (at a cell that is not a corner) always results in a $$\lambda$$-rpp. Also, toggling is an involution).

Note also that the lower bound of $$\pi$$ at $$(u, v)$$ is defined (and finite) even when $$(u, v)$$ is not a cell of $$\lambda$$, as long as both $$(u-1, v)$$ and $$(u, v-1)$$ are cells of $$\lambda$$.

The Pak correspondence $$\Phi_\lambda$$ sends a $$\lambda$$-array $$M = (m_{i, j})$$ to a $$\lambda$$-rpp $$\Phi_\lambda(M)$$. It is defined by recursion on $$\lambda$$ (that is, we assume that $$\Phi_\mu$$ is already defined for every partition $$\mu$$ smaller than $$\lambda$$), and its definition proceeds as follows:

• If $$\lambda = \varnothing$$, then $$\Phi_\lambda$$ is the obvious bijection sending the only $$\varnothing$$-array to the only $$\varnothing$$-rpp.

• Pick any corner $$c = (i, j)$$ of $$\lambda$$, and let $$\mu$$ be the result of removing this corner $$c$$ from the partition $$\lambda$$. (The exact choice of $$c$$ is immaterial.)

• Let $$M'$$ be what remains of $$M$$ when the corner cell $$c$$ is removed.

• Let $$\pi' = \Phi_\mu(M')$$.

• For each positive integer $$k$$ such that $$(i-k, j-k)$$ is a cell of $$\lambda$$, toggle $$\pi'$$ at $$(i-k, j-k)$$. (All these togglings commute, so the order in which they are made is immaterial.)

• Extend the $$\mu$$-rpp $$\pi'$$ to a $$\lambda$$-rpp $$\pi$$ by adding the cell $$c$$ and writing the number $$m_{i, j} - \pi'_{<(i, j)}$$ into this cell.

• Set $$\Phi_\lambda(M) = \pi$$.

pak_correspondence() for the Pak correspondence as a standalone function.

sulzgruber_correspondence() for the inverse map.

EXAMPLES:

sage: a = WeakReversePlanePartition([[1, 2, 3], [1, 2, 3], [2, 4, 4]])
sage: A = a.pak_correspondence(); A
[[1, 0, 2], [0, 2, 0], [1, 1, 0]]
sage: a.parent(), A.parent()
(Weak Reverse Plane Partitions, Tableaux)


Applying the Pak correspondence to the transpose of a $$\lambda$$-rpp $$M$$ yields the same result as applying it to $$M$$ and then transposing the result:

sage: a = WeakReversePlanePartition([[1,3,5],[2,4]])
sage: acc = a.pak_correspondence().conjugate()
sage: acc == a.conjugate().pak_correspondence()
True

class sage.combinat.hillman_grassl.WeakReversePlanePartitions

The set of all weak reverse plane partitions.

Element
an_element()

Returns a particular element of the class.

sage.combinat.hillman_grassl.hillman_grassl(M)

Return the image of the $$\lambda$$-array M under the Hillman-Grassl correspondence.

The Hillman-Grassl correspondence is a bijection between the tableaux with nonnegative entries (otherwise arbitrary) and the weak reverse plane partitions with nonnegative entries. This bijection preserves the shape of the tableau. See hillman_grassl.

See hillman_grassl() for a description of this map.

EXAMPLES:

sage: from sage.combinat.hillman_grassl import hillman_grassl
sage: hillman_grassl([[2, 1, 1], [0, 2, 0], [1, 1]])
[[2, 2, 4], [2, 3, 4], [3, 5]]
sage: hillman_grassl([[1, 2, 0], [1, 0, 1], [1]])
[[0, 1, 3], [2, 4, 4], [3]]
sage: hillman_grassl([])
[]
sage: hillman_grassl([[3, 1, 2]])
[[3, 4, 6]]
sage: hillman_grassl([[2, 2, 0], [1, 1, 1], [1]])
[[1, 2, 4], [3, 5, 5], [4]]
sage: hillman_grassl([[1, 1, 1, 1]]*3)
[[1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6]]

sage.combinat.hillman_grassl.hillman_grassl_inverse(M)

Return the image of the $$\lambda$$-rpp M under the inverse of the Hillman-Grassl correspondence.

See hillman_grassl_inverse() for a description of this map.

EXAMPLES:

sage: from sage.combinat.hillman_grassl import hillman_grassl_inverse
sage: hillman_grassl_inverse([[2, 2, 4], [2, 3, 4], [3, 5]])
[[2, 1, 1], [0, 2, 0], [1, 1]]
sage: hillman_grassl_inverse([[0, 1, 3], [2, 4, 4], [3]])
[[1, 2, 0], [1, 0, 1], [1]]


Applying the inverse of the Hillman-Grassl correspondence to the transpose of a $$\lambda$$-rpp $$M$$ yields the same result as applying it to $$M$$ and then transposing the result ([Gans1981] Corollary 3.4):

sage: hillman_grassl_inverse([[1,3,5],[2,4]])
[[1, 2, 2], [1, 1]]
sage: hillman_grassl_inverse([[1,2],[3,4],[5]])
[[1, 1], [2, 1], [2]]
sage: hillman_grassl_inverse([[1, 2, 3], [1, 2, 3], [2, 4, 4]])
[[1, 2, 0], [0, 1, 1], [1, 0, 1]]
sage: hillman_grassl_inverse([[1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6]])
[[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]]

sage.combinat.hillman_grassl.pak_correspondence(M, copy=True)

Return the image of a $$\lambda$$-rpp M under the Pak correspondence.

The Pak correspondence is the map $$\xi_\lambda$$ from [Sulzgr2017] Section 7, and is the map $$\xi_\lambda$$ from [Pak2002] Section 4. It is the inverse of the Sulzgruber correspondence (sulzgruber_correspondence()).

See pak_correspondence() for a description of this map.

INPUT:

• copy (default: True) – boolean; if set to False, the algorithm will mutate the input (but be more efficient)

EXAMPLES:

sage: from sage.combinat.hillman_grassl import pak_correspondence
sage: pak_correspondence([[1, 2, 3], [1, 2, 3], [2, 4, 4]])
[[1, 0, 2], [0, 2, 0], [1, 1, 0]]
sage: pak_correspondence([[1, 1, 4], [2, 3, 4], [4, 4, 4]])
[[1, 1, 2], [0, 1, 0], [3, 0, 0]]
sage: pak_correspondence([[0, 2, 3], [1, 3, 3], [2, 4]])
[[1, 0, 2], [0, 2, 0], [1, 1]]
sage: pak_correspondence([[1, 2, 4], [1, 3], [3]])
[[0, 2, 2], [1, 1], [2]]
sage: pak_correspondence([[1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6]])
[[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]]


The Pak correspondence can actually be extended (by the same definition) to “rpps” of nonnegative reals rather than nonnegative integers. This implementation supports this:

sage: pak_correspondence([[0, 1, 3/2], [1/2, 3/2, 3/2], [1, 2]])
[[1/2, 0, 1], [0, 1, 0], [1/2, 1/2]]

sage.combinat.hillman_grassl.sulzgruber_correspondence(M)

Return the image of a $$\lambda$$-array M under the Sulzgruber correspondence.

The Sulzgruber correspondence is the map $$\Phi_\lambda$$ from [Sulzgr2017] Section 7, and is the map $$\xi_\lambda^{-1}$$ from [Pak2002] Section 5. It is denoted by $$\mathcal{RSK}$$ in [Hopkins2017]. It is the inverse of the Pak correspondence (pak_correspondence()).

See sulzgruber_correspondence() for a description of this map.

EXAMPLES:

sage: from sage.combinat.hillman_grassl import sulzgruber_correspondence
sage: sulzgruber_correspondence([[1, 0, 2], [0, 2, 0], [1, 1, 0]])
[[1, 2, 3], [1, 2, 3], [2, 4, 4]]
sage: sulzgruber_correspondence([[1, 1, 2], [0, 1, 0], [3, 0, 0]])
[[1, 1, 4], [2, 3, 4], [4, 4, 4]]
sage: sulzgruber_correspondence([[1, 0, 2], [0, 2, 0], [1, 1]])
[[0, 2, 3], [1, 3, 3], [2, 4]]
sage: sulzgruber_correspondence([[0, 2, 2], [1, 1], [2]])
[[1, 2, 4], [1, 3], [3]]
sage: sulzgruber_correspondence([[1, 1, 1, 1]]*3)
[[1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6]]


The Sulzgruber correspondence can actually be extended (by the same definition) to arrays of nonnegative reals rather than nonnegative integers. This implementation supports this:

sage: sulzgruber_correspondence([[1/2, 0, 1], [0, 1, 0], [1/2, 1/2]])
[[0, 1, 3/2], [1/2, 3/2, 3/2], [1, 2]]

sage.combinat.hillman_grassl.transpose(M)

Return the transpose of a $$\lambda$$-array.

The transpose of a $$\lambda$$-array $$(m_{i, j})$$ is the $$\lambda^t$$-array $$(m_{j, i})$$ (where $$\lambda^t$$ is the conjugate of the partition $$\lambda$$).

EXAMPLES:

sage: from sage.combinat.hillman_grassl import transpose
sage: transpose([[1, 2, 3], [4, 5]])
[[1, 4], [2, 5], [3]]
sage: transpose([[5, 0, 3], [4, 1, 0], [7]])
[[5, 4, 7], [0, 1], [3, 0]]