# Mysterious symmetry - in search for a bijection

I have a mysterious symmetry that I have not managed to prove. First some definitions (see picture below)

Fix a partition that fit in a staircase shape with $n$ rows. There are $Catalan(n)$ such shapes. We can represent this with a diagram $D$, as below, where the gray squares is the partition. The yellow squares are enumerated $1,\dotsc,n$ from top to bottom, and thus any permutation in $S_n$ is seen as a labeling of the yellow squares.

Let $a+b=n$. Given a permutation in $S_n$ seen as a labeling of the yellow squares, the first block is the squares with labels $1,\dotsc,a$ and the second block is the remaining $b$ squares. Thus, the blue labels is the first block, and the red labels is the second block in my example.

A permutation $\sigma \in S_n$ is called $(D,a,b)$-good if the following holds:

• The smallest label in each of the two blocks appear lowest in its block.
• If $i$ and $i+1$ are in the same block, and $i$ below $i+1$, then the square in the same row as $i+1$ and same column as $i$ must be white.

In the diagram, the permutation $342615$ is shown, and one can verify that it is $(D,4,2)$-good. The white squares that has to be white due to the second condition has been marked with bullets.

Let $Good(D,a,b)$ denote the set of $(D,a,b)$-good permutations.

Warmup exercise

Show that $|Good(D,a,b)|=|Good(D,b,a)|$.

Finally, we define the ascent, $asc_D$-statistic on permutations as follows: For every white square $S$, we let $S_1$ be the index of the yellow square in the same row, and $S_2$ be the index of the yellow square in the same column. Then $asc_D(\sigma)$ is the number of white squares $S$, such that $\sigma(S_1)<\sigma(S_2)$. In our diagram, $asc_D(342615) = 1+1+2+0+1 = 5$, where the terms are contributions from each row.

My problem

Show (bijectively) that for every diagram $D$ and choice of $a+b=n$, $$\sum_{\sigma \in Good(D,a,b)} q^{asc_D(\sigma)} =\sum_{\sigma \in Good(D,b,a)} q^{asc_D(\sigma)}.$$

For the diagram $D$ here, we have that $|Good(D,4,2)|=|Good(D,2,4)|=20$, and that both sums above become $$1 + 3 q + 4 q^2 + 4 q^3 + 4 q^4 + 3 q^5 + q^6.$$

Comments: For some diagrams $D$, it is straightforward to produce a bijection, in particular the case when $D$ has no gray squares. One would hope that a bijection would the number ascents 'within blocks', that is, ascents where $S_1$ and $S_2$ belong to the same block. However, this cannot be done for general $D$.

One can generalize the problem to permutations with more than two blocks, but the 2-block case implies the general case.

I am quite confident this result follows (non-bijectively) from a result by C. Athanasiadis, but it requires several messy steps.

Motivation

This is related to the $p_\lambda$-expansion of certain LLT polynomials.

• Are the coefficients of the generating functions always symmetric? This is what I'm seeing for small n. – Zachary Hamaker Feb 20 '18 at 2:03
• "There are Catalan(n) such shapes" - do you mean such partitions? – Max Alekseyev Feb 20 '18 at 2:04
• Reminds of permutation tableaux (or Postnikov's Le-tableaux, more generally), but with more rules and kinds of cells. – Alexander Burstein Feb 20 '18 at 5:26
• There are two things I don't understand in the definition (or example): I would think that the upper block has labels $3,4,2,6$ and the lower block has labels $1,5$. The smallest labels in the blocks are $2$ and $1$, but these do not appear lowest. Did you mean to say 'largest labels appear lowest'? – Martin Rubey Feb 20 '18 at 6:45
• @MartinRubey - I believe the term "block" refers to the subsets [a] and [a+1,a+b], so 1 and 2 are in the same non-contiguous block. – Zachary Hamaker Feb 20 '18 at 11:52

Oliver Pechenik and I have some partial progress to report. Maybe someone else can see how to supply the remaining missing ingredients.

First, let's establish some notation. We say your ascent statistic enumerates the $D$-inversions of the permutation $\sigma$, denoted $\iota_D(\sigma)$. This makes sense since $\iota_\varnothing(\sigma)$ counts the usual inversions of $\sigma$. Let $G_D(a,b)$ be your set $Good(D,a,b)$ and define the $D$-inversion generating function $g_{D,a,b}(q) = \sum_{\sigma \in G_D(a,b)} q^{\iota_D(\sigma)}$.

As mentioned in my comment, the generating function $g_{D,a,b}$ appears to have coefficient symmetry. Let $\delta_{n}$ be the staircase partition $(n-1,n-2,\dots,1)$.

Conjecture 1: Let $a+b = n$ and $D \subset \delta_n$ and write $$g_{D,a,b}(q) = h_0 + h_1 q + h_2 q^2 + \dots + h_m q^m,$$ where $h_m \neq 0$. Then $h_i = h_{m-i}$ for all $i$.

We have extensively (but not exhaustively) computer tested this conjecture and are convinced that it is true.

Up to this unproved conjecture, we have a complete proof of your desired $a/b$ symmetry. More specifically, we can show the following.

Theorem 2: For $a+b = n$ and $D \subset \delta_{n-1}$, let $m$ be the degree of $g_{D,a,b}(q)$. There is an explicit weight-reversing bijection $\Phi_{a,b} : G_D(a,b) \to G_D(b,a)$ with $$\iota_D(\sigma) = m - \iota_D(\Phi(\sigma))$$ for all $\sigma$.

Note that the statement you wanted follows directly from combining the theorem and the conjecture above.

Before sketching the proof of Theorem 2, let me outline an example. We begin with $\sigma = 14237568 \in G_{(3,2)}(3,5)$, which has the following diagram:

.

Here, entries with values in $[a]$ are underlined (blue above) and those with values in $[a+1,n]$ are overlined (red above). The indices corresponding to underlined and overlined entries are $A=\{1,2,4\}$ and $B = \{3,5,6,7,8\}$, respectively. The $\blacksquare$'s are cells that cannot correspond to $D$-inversions due to our choice of $A$ and $B$, while the $\square$'s are cells that must have $D$-inversions because of $A$ and $B$. The $\bullet$'s are the same as in Per's diagram, while the entry marked $\star$ cannot correspond to a $D$-inversion because of the $\bullet$ above it. Finally, the entries with $\blacktriangle$ or $\triangle$ could correspond to $D$-inversions (unfilled) or not (filled).

Our map proceeds as follows:

1. Exchange $A$ and $B$, preserving relative order (this is $\Psi_{a,b}$ below), resulting in $61784235$.

.

This has the effect of exchanging $\blacksquare$'s and $\square$'s, while preserving each other entry.

1. Within $A$ and $B$, we can transform the permutation so that the number of $\triangle$'s and $\blacktriangle$'s in each row is exchanged, resulting in $\tau = 61872453 \in G_D(b,a)$.

.

This involves two applications of the map $\Phi_{n,0}$ below; one to the entries in $A$ and one to the entries in $B$. Note the position of triangles within each row changes, but the total number is preserved. Here, $\iota_D(\sigma) = 4$ while $\iota_D(\tau) = 13$. Note $4+13 = 17 = \binom{7}{2} - (|D|-1)$, which is the maximum possible number of $D$-inversions in $G_D(a,b)$ (or $G_D(b,a)$), as required by Theorem 2.

As a first step towards a proof, we sketch a bijective proof of Conjecture 1 in the special case $b=0$. We say $(i,j)$ is a $D$-inversion if $(i,j) \notin D$ and $\sigma_j > \sigma_{n+1-i}$. The $D$-code is $\textbf{c}^D(\sigma) = (c_1^D(\sigma),\dots,c_{n-1}^D(\sigma))$ where $c_k^D(\sigma)$ is the number of $D$-inversions of $\sigma$ of the form $(k,\ell)$. Note $\textbf{c}_\varnothing$ is ordinary Lehmer code. Also, $\iota_D(\sigma) = \sum c_i^D(\sigma)$.

For $\sigma \in G_D(n,0)$, observe that $\sigma_1 = 1$. Note also that $G_D(n,0) = \varnothing$ if $D \not \subset \delta_{n-1}$.

Lemma 3: For $D \subset \delta_{n-1}$, there is a unique $\tau\in G_D(n,0)$ that is maximal with respect to $\iota_D$. Moreover, $c_i^D(\tau) = n-i - D_i$.

Proof: We construct $\tau$ recursively. Set $\tau_1 = 1$. For each value $i \in [2,n]$, place $i$ as far to the right as possible in $\tau$, satisfying the constraint that the cell corresponding to $i$ and $i-1$ in $\delta_n$ is not in $D$. It is easy to check that the resulting permutation has the desired $D$-code.

To see $\tau$ is unique, we first provide an upper bound on the code of $\sigma \in G_D(n,0)$. Let $(i_1,j_1), \dots, (i_k,j_k)$ be the maximally northwest cells of $\delta_n$ that satisfy $\sigma_{i_1} = \sigma_{n+1-j_1} + 1$ (these are some of the cells labeled with $\bullet$ in Per's diagram). We can order these so that $j_1 < \dots < j_k$, hence $i_1 > \dots > i_k$. For $k \in [n-1]$, let $\ell$ be maximal so that $k \geq i_\ell$. Then $(k,j_\ell) \in \delta_n \setminus D$ and cannot correspond to a $D$-inversion. Therefore, $c^D_k(\sigma) \leq n-k-D_k$. On reflection, it becomes apparent that $\tau$ is the unique permutation attaining this bound for each $k$.

Let $\textbf{c}^D_M$ be the code defined in Lemma 3. Next, we show the $D$-code functions similarly to the ordinary Lehmer code.

Lemma 4: For $D \subset \delta_{n-1}$ and $\textbf{b} = (b_1,\dots,b_k)$ with $b_i \leq n-i-D_i$, there is a unique permutation $\sigma \in G_D(n,0)$ with $\textbf{c}_D(\sigma) = \textbf{b}$.

Proof: One can recurse down from the maximal $\tau$ constructed in Lemma 1, picking off one inversion at a time. The details are a bit technical, but we seem to understand the algorithm pictorially.

Corollary 5: The function $g_{D,n,0}(q)$ is coefficient symmetric.

Proof: By Lemma 4, we can define the bijection $\Phi_{n,0}: G_D(n,0) \to G_D(n,0)$ where $\textbf{c}^D(\Phi_{n,0}(\sigma)) = \textbf{c}^D_M - \textbf{c}^D(\sigma)$.

The bijection $\Phi_{n,0}$ is one of the key tools in our proof of Theorem 2. The other tool is a solution to the warm-up exercise.

For sets $A \sqcup B = [n]$ with $|A| = a$ and $|B| = b$, let $G_D(A,B)$ be the set of permutations in $G_D(a,b)$ with $\sigma^{-1}(A)=[a]$ (so $\sigma^{-1}(B) = [a+1,b]$). The corresponding $D$-inversion generating function is denoted $g_{D,A,B}(q)$. Clearly, $$G_D(a,b) = \bigsqcup_{A \sqcup B = [n]} G_D(A,B) \ \ \ \mbox{and}\ \ \ g_{D,a,b}(q) = \sum_{A \sqcup B = [n]} g_{D,A,B}(q),$$ where $|A| = a$ and $|B| = b$.

For fixed $A,B$ and $D$, let $\psi_{A,B}$ be the number of $D$-inversions corresponding to $(i,j) \in \delta_n\setminus D$ where $n+1-i \in A$ and $j \in B$.

Lemma 6: For $A \sqcup B = [n]$, $g_{D,A,B}(q)$ is coefficient symmetric.

Proof: The generating function $g_{D,A,B}(q)$ factors as $$g_{D,A,B} = g_{D',a,0} \cdot g_{D'',b,0} \cdot q^{\psi_{A,B}},$$ where $D'$ is given by intersecting $D$ with the rows and columns of $\delta_n$ containing an element of $[a]$ and $D''$ is similarly given by intersecting $D$ with those rows and columns containing an element of $[a+1,n]$. Since each factor is coefficient symmetric by Corollary 5, we are done.

We define the map $\Psi_{a,b}:S_n \to S_n$ where for $\tau = \Psi_{a,b}(\sigma)$ we have $$\tau_i = \begin{cases} \sigma_i+b, & \text{if } \sigma_i \leq a;\\ \sigma_i-a, & \text{if } \sigma_i > a. \end{cases}$$ We now prove the warmup exercise.

Lemma 7: The map $\Psi_{a,b}$ is a bijection from $G_D(a,b)$ to $G_D(b,a)$.

Proof: For $A\sqcup B = [n]$ with $|A|=a,|B|=b$, observe that $\Psi_{a,b}$ is a bijection from $G_D(A,B)$ to $G_D(B,A)$. The lemma follows.

The effect of $\Psi_{a,b}$ on $\iota_D$ is the key to proving Theorem 2.

Lemma 8: Fix $D \subset \delta_n$ and $A \sqcup B = [n]$ with $|A| = a$ and $|B| = b$. For $\sigma \in G_D(A,B)$ we have $\iota_D(\Psi_{a,b}(\sigma)) = \psi_{B,A} - \psi_{A,B} + \iota_D(\sigma)$.

Proof: After applying $\Psi_{a,b}$, we lose the $\psi_{A,B}$ $D$-inversions in $\sigma$ that are forced by $A$ and $B$ but gain the $\psi_{B,A}$ $D$-inversions forced by $B$ and $A$.

Lemma 9: Let $D \subset \delta_n$ and $A \sqcup B = [n]$ with $|A|=a$ and $|B|=b$. Define $D'$ and $D''$ as in the proof of Lemma 6 and fix $\ell = \binom{a-1}{2} -|D'| + \binom{b-1}{2}-|D''|$. Then $\psi_{A,B} + \psi_{B,A} +\ell = m$ where $m$ is the max degree of $g_{D,a,b}$.

Proof: Note the quantity $\ell$ is the max degree coming from inversions not forced by $A$ and $B$. Some cells in $\delta_n - D$ will never correspond to inversions for reasons similar to those in Lemma 3. The remaining cells in $\delta_n - D$ correspond either to an inversion forced by $A$ and $B$ or an inversion forced by $B$ and $A$.

Proof of Theorem 2: Let $\sigma \in G_D(a,b)$ with $\sigma^{-1}([a]) = A$ and $\sigma^{-1}([a+1,n]) = B$ (so $\sigma \in G_D(A,B)$, as well). Moreover, let $D'$ and $D''$ be as in Lemma 6. We define the map $\Phi_{a,b}$ as follows:

1. First, apply $\Phi^{D'}_{a,0}$ to the subword of $\sigma$ indexed by $A$ and $\Phi^{D''}_{b,0}$ to the subword of $\sigma$ indexed by $B$, obtaining $\tau \in G_D(A,B)$.

2. Then, apply $\Psi_{a,b}$ to $\tau$, obtaining $\rho$.

We now show $\Phi_{a,b}$ has the desired properties. First, observe that step 1 sends $\iota_D(\sigma)$ to its complement in $g_{D,A,B}(\sigma)$, as per Lemma 6. Next, we combine Lemma 8 and Lemma 9 to show $\iota_D(\rho) = m - \iota_D(\sigma)$. The theorem follows.

Some remarks:

1. Symmetry cannot be proved for general $G_D(a,b)$ using code containment. For example, $G_{(3,1)}(3,2)$ has four elements with $(3,1)$-codes $(0,1,2,0)$, $(0,1,0,1)$, $(0,0,1,0)$ and $(0,0,0,0)$.

2. There might be a simple proof of Conjecture 1 using the $b=0$ case. We thought we had one, but couldn't remember it two days later.

3. Any proof of symmetry may apply equally well to the case where there are more than two blocks. In general, it appears the max degree of $G_D(a_1,a_2,\dots,a_k)$ is $\binom{n}{2} - |D| - (n+1-k)$.

• I need some time to process this! The case b=0 is fairly easy to attack - the permutations are then actually in bijection with certain acyclic orientations, and the generating function is $\prod_i [a_i]!$, where $a_i$ is the number of white squares in row i. This gives symmetry, and one can make a bijective proof of Conjecture 1 in this case. In more generality, I believe conjecture 1 is equivalent to the statement $G_D(a,b) = G_{D'}(a,b)$, where $D'$ is the transpose/conjugate diagram. This is true due to Athanasiadis, but in a non-bijective manner.... – Per Alexandersson Mar 3 '18 at 17:34
• @PerAlexandersson I think the argument about codes is the same as the one you are describing for the $b=0$ case. I'll put some thought into showing $g_{D,a,b}(q) = g_{D',a,b}(q)$ - that seems tractable. – Zachary Hamaker Mar 3 '18 at 20:09