16
$\begingroup$

Let $A_n$ denote the set of noncrossing fixed point free involutions in the symmetric group $S_{2n}$. "Noncrossing" means that if $a<b<c<d$, then not both $(a,c)$ and $(b,d)$ can be cycles of $w\in A_n$. The cardinality of $A_n$ is the Catalan number $C_n =\frac{1}{n+1}{2n\choose n}$. A meander of order $n$ may be defined as a pair $(u,v)\in A_n\times A_n$ such that $uv$ has exactly two cycles (necessarily of length $n$). Let $\kappa(w)$ denote the number of cycles of the permutation $w$. The meander matrix $\mathcal{G}_{2n}(q)$ is the matrix whose rows and columns are indexed by elements of $A_n$, with $(\mathcal{G}_{2n}(q))_{u,v}$ equal to $q^{\kappa(uv)/2}$. Di Francesco has shown here that $$ \det \mathcal{G}_{2n}(q) =\prod_{m=1}^n U_m(q)^{a_{2n,2m}}, $$ where $U_m(q)$ is a Chebyshev polynomial of the second kind, and $a_{2n,2m}$ is a certain nonnegative integer. (Note: Di Francesco defines $U_m(2\cos\theta)=\frac{\sin(m+1)\theta}{\sin\theta}$, while I think it is more traditional to define $U_m(\cos\theta)=\frac{\sin(m+1)\theta}{\sin\theta}$.)

What if we refine the definition of $\mathcal{G}_{2n}(q)$ by defining $(\mathcal{H}_{2n})_{u,v}$ to be $\prod_i p_i^{\lambda_i}$, where $uv$ has $2\lambda_i$ cycles of length $i$? Here $p_i=\sum_j x_j^i$, the $i$th power sum symmetric function. Then for instance, $$ \det \mathcal{H}_6 = (p_1^3-p_3)^3 (p_1^6+3p_1^3 p_3 -6p_1^2p_2^2 +2p_3^2). $$ We don't get as much factorization as for $\mathcal{G}_6(q)$, but we do get some factorization. I was unable to compute $\det\mathcal{H}_8$.

It is also true that the irreducible factors of $\det \mathcal{H}_6$ are Schur positive, i.e., nonnegative linear combinations of the Schur functions $s_\lambda$. Does this property persist for all $n$?

The sum of the entries of $\mathcal{G}_{2n}(q)$ gives the enumeration of pairs $(u,v)\in A_n\times A_n$ by half the number of cycles of $uv$. For $n=3$ this is $5q^3+12q^2+8q$. What can be said about the sum of the entries of $\mathcal{H}_{2n}$? I have checked that it is Schur positive for $n\leq 6$.

My last question is only peripherally related to meanders. Let $R_n = \sum_{w\in A_n} w\in \mathbb{Q}S_{2n}$, where $\mathbb{Q}S_{2n}$ denotes the group algebra of $S_{2n}$ over $\mathbb{Q}$. What can be said about $R_n$? For instance, its eigenvalues (when acting by left multiplication on $\mathbb{Q}S_{2n}$), its mixing time (i.e., what is the least $k$ (asymptotically) for which $(R_n/C_n)^k$ is approximately the uniform distribution on the set of even or of odd permutations in $S_{2n}$ (whichever is appropriate)), etc? If all eigenvalues of $R_n^2$ are real and nonnegative, then can we modify the answer of Brendan Pawlowski at MO254782 to conclude that the sum of the entries of $\mathcal{H}_{2n}$ is Schur positive?

Addendum. I computed $\det\mathcal{H}_8$. (It was almost instantaneous on my home PC. I don't know why it failed on an MIT Math. Dept. server.) It factors as $a\cdot b\cdot c^2 \cdot d^2$, where $a,b,c,d$ are irreducible homogeneous symmetric functions of degrees $12, 12, 8, 8$, respectively. Each of $a,b,c,d$ is Schur positive.

Addendum2. Let $\mathrm{scp}_{2n} = \det(\mathcal{H}_{2n}+I_{2n}x)$, essentially the characteristic polynomial of $\mathcal{H}_{2n}$. I computed $\mathrm{scp}_6$ and $\mathrm{scp}_8$. It seems remarkable to me that they factor in the same way as the determinant (the case $x=0$). Moreover, for any $j$ the coefficient of $x^j$ in $\mathrm{scp}_6$ and $\mathrm{scp}_8$ is Schur positive. For $\det(\mathcal{G}_6(q)+I_6x)$, the factorization follows that of $\mathcal{H}_6$ (not $\mathcal{G}_6(q)$). For $\det(\mathcal{G}_8(q)+I_8x)$, the factorization follows that of $\mathcal{H}_8$ except that the two factors of degree 12 and multiplicity two merge into a single factor of multiplicity four.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
-1
$\begingroup$

Not a full solution (only for Schur positivity): Consider the set of pairs $(u, v) \in A_n \times A_n$. We'll define a map that associates each such pair with a semistandard Young tableau $T$ of shape $\lambda(uv)$, where $\lambda(uv)$ is the partition corresponding to the cycle type of $w = uv$.

First, we represent each $u \in A_n$ as a noncrossing matching of $2n$ points labeled $1, 2, \dots, 2n$ arranged clockwise around a circle. The matching consists of $n$ chords inside the circle connecting the paired elements. Similarly, we represent each $v \in A_n$ with chords outside the circle, again connecting the pairs in $v$.

To determine the cycles of $w = uv$, we "follow" the paths created by the chords of $u$ and $v$. Starting at a point $i$, we move along the chord in $u$ to $u(i)$, then along the chord in $v$ to $v(u(i))$, repeating this process alternately using $u$ and $v$ until we return to $i$. This traversal defines a cycle in $w$. Since $u$ and $v$ are involutive, their matchings are perfect, and every point is included in exactly one cycle.

Now, we construct the tableau $T$ as follows: For each cycle $C$ in $w$, we collect the labels of the points encountered during the traversal and arrange them in increasing order to form a row of $T$. We then order the cycles (and hence the rows of $T$) according to the minimal elements of their respective cycles, in increasing order (see example below for $n=2$).

The resulting tableau $T$ has the following properties:

  1. Its shape is $\lambda(uv)$, since the lengths of the cycles correspond to the row lengths in $T$.
  2. It is semistandard: entries in each row are strictly increasing (as they are sorted lists of labels within a cycle), and entries in each column increase strictly down the tableau (ensured by the ordering of the cycles and the noncrossing property).

The weight of each tableau $T$ corresponds to a monomial $x^{\mathrm{wt}(T)}$, where the weight $\mathrm{wt}(T)$ records the multiplicities of the entries. In our case, since the entries are distinct and range from $1$ to $2n$, and the cycles determine the entries, the total monomial corresponds to the product $\prod_{i} p_i^{\lambda_i(uv)}$.

The set of all such tableaux $T$ of shape $\lambda$ is precisely the set of SSYTs of shape $\lambda$ with entries $1,2,\dots,2n$ and distinct entries. The generating function of these tableaux is the Schur function $s_\lambda$. Therefore, we have:

$$ S_n = \sum_{\lambda \vdash 2n} c_\lambda s_\lambda $$

where $c_\lambda$ is the number of pairs $(u, v) \in A_n \times A_n$ such that $\lambda(uv) = \lambda$. Since $c_\lambda \geq 0$ (it counts the number of such pairs), $S_n$ is a nonnegative integer linear combination of Schur functions.

Example for $n = 2$

In $A_2$, we have noncrossing matchings on four points. Let $u$ pair $(1,2)$ and $(3,4)$, while $v$ pairs $(1,4)$ and $(2,3)$. Computing $w = uv$, we start at 1 and follow the path: $1 \xrightarrow{u} 2 \xrightarrow{v} 3 \xrightarrow{u} 4 \xrightarrow{v} 1$, forming a 4-cycle $(1,2,3,4)$. The resulting tableau $T$ has shape $(4)$ with entries $[1\ 2\ 3\ 4]$, which is indeed semistandard.

Improve this answer
$\endgroup$
1
  • $\begingroup$ "It is semistandard" Press X to doubt. $\endgroup$ Commented Jun 24 at 19:41

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.