8
$\begingroup$

A conjecture was made on p.14 in "Cycle Classes of the E-O Stratification on the Moduli of Abelian Varieties" by Torsten Ekedahl (late, excellent contributor to MO) and Gerard Van Der Geer concerning number of elements of the Weyl groups defined in the initial paragraph of the paper and supposing these can be identified with OEIS A000629.

Conjecture. Fix a positive integer $g$. Let $W_g$ be the subgroup \begin{align} \left\{\sigma \in S_{2g} \mid \sigma\left(i\right) + \sigma\left(2i+1-g\right) = 2g + 1 \text{ for all } g \right\} \end{align} of the symmetric group $S_{2g}$; this is a Coxeter group of type $C_{g}$. It is isomorphic to the semi-direct product $S_g \ltimes \left( \mathbb Z / 2 \mathbb Z \right)^g$, where $S_g$ acts on $\left( \mathbb Z / 2 \mathbb Z \right)^g$ by permuting the factors.

Let $w_\varnothing \in W_g$ be the permutation that sends $1, 2, \ldots, g, g+1, g+2, \ldots, 2g$ to $g+1, g+2, \ldots, 2g, 1, 2, \ldots, g$, respectively. Let $\leq$ denote the Bruhat order on $W_g$. Then, the number of all $w \in W_g$ that satisfy $w \leq w_\varnothing$ is \begin{align} \left. \left(x \dfrac{d}{dx}\right)^g \left(\dfrac{1}{1-x}\right) \right|_{x=1/2} \end{align} (OEIS sequence A000629).

What is the status of this conjecture? Confirmed or not?

Lemma 2.14 of the paper shows that an $w \in W_g$ satisfies $w \leq w_\varnothing$ if and only if all $i \in \left\{1,2,\ldots,g\right\}$ satisfy $w\left(i\right) \leq g+i$. Thus, it is not necessary to understand the Bruhat order to approach this conjecture.

Edit (May 14, 2020):

The sequence A000629 is of some general importance in algebra and combinatorics. It is the row sums of the unsigned partition polynomials A263634 and A127672, related to the logarithmic derivative of e.g.f.s, or formal Taylor series, and, consequently, to the raising op for Appell sequences and, thence, to Weyl and Heisenberg algebras and series and integral convolutions, to the cumulant expansion theorem, and to the Faber polynomials A263916 (and, therefore, the symmetric polynomials/functions). So, any further combinatorial proofs of the conjecture would perhaps inform these constructs.

In fact, Getzler alludes to necklaces in a natural generalization of the identity above to A263634 in "The semi-classical approximation for modular operads."

$\endgroup$
14
  • $\begingroup$ This looks like a rook theory problem. $\endgroup$ Commented May 11, 2020 at 10:24
  • $\begingroup$ I think it's true, assuming that the "a(n) = Sum_{k=0..n} Stirling2(n+1, k+1)*k!. - Paul Barry, Apr 20 2005" formula on the OEIS is true. Indeed, let me rename $g$ as $n$. How many ways are there to find a permutation $w \in W_n$ satisfying $w \leq w_\varnothing$ ? Clearly, it suffices to choose the $n$ values $w\left(1\right), w\left(2\right), \ldots, w\left(n\right)$, since the other $n$ values of $w$ will then be uniquely determined by the definition of $W_n$. In choosing these $n$ values $w\left(1\right), w\left(2\right), \ldots, w\left(n\right)$, we need to satisfy the relation ... $\endgroup$ Commented May 11, 2020 at 11:00
  • $\begingroup$ $w \left(i\right) \leq n+i$ for each $i \in \left\{1,2,\ldots,n\right\}$ (by Lemma 2.14 of the paper), and furthermore ensure that $w\left(i\right) \neq w\left(j\right)$ and $w\left(i\right) + w\left(j\right) \neq 2n+1$ for any distinct $i, j \in \left\{1,2,\ldots,n\right\}$. So we can proceed as follows: In Step 1, we decide how many elements (say, $k$ many) $i$ of $\left\{1, 2, \ldots, n\right\}$ will satisfy $w\left(i\right) \leq n$. (We don't decide which ones these will be.) In Step 2, we choose these $k$ many elements $i$, calling them homebound (since they are $\leq n$ and ... $\endgroup$ Commented May 11, 2020 at 11:02
  • $\begingroup$ ... will also be sent to elements $\leq n$), and we also choose the values $w\left(i\right)$ for all non-homebound elements $i$ of $\left\{1,2,\ldots,n\right\}$. These need to be chosen subject to the requirements that $w\left(i\right) \leq n+i$ for each $i \in \left\{1,2,\ldots,n\right\}$. In Step 3, we finally choose the values $w\left(i\right)$ for all homebound elements $i$ of $\left\{1,2,\ldots,n\right\}$. These need to be chosen subject to the requirements that $w\left(i\right) \neq w\left(j\right)$ and $w\left(i\right) + w\left(j\right) \neq 2n+1$ for any ... $\endgroup$ Commented May 11, 2020 at 11:03
  • 1
    $\begingroup$ By the way, I have no idea what a "necklace of partitions of n+1 labeled beads" is. $\endgroup$ Commented May 11, 2020 at 11:07

1 Answer 1

1
$\begingroup$

The following is transcribed from @darijgrinberg's comments 1 2 3 4 5, made CW to avoid reputation, per @TomCopeland's request and absent any reply after a few days. If @darijgrinberg prefers to post it themselves, or to have it not posted at all, then I will be happy to delete it.

I think it's true, assuming that the "a(n) = Sum_{k=0..n} Stirling2(n+1, k+1)*k!. - Paul Barry, Apr 20 2005" formula on the OEIS is true. Indeed, let me rename $g$ as $n$. How many ways are there to find a permutation $w \in W_n$ satisfying $w \le w_\emptyset$? Clearly, it suffices to $w(1), \dotsc, w(n)$, since the other $n$ values of $w$ will then be uniquely determined by the definition of $W_n$. In choosing these $n$ values $w(1), w(2), \dotsc, w(n)$, we need to satisfy the relation $w(i) \le n + i$ for each $i \in \{1, 2, \dotsc, n\}$ (by Lemma 2.14 of Ekedahl and van der Geer - Cycle classes of the E-O stratification on the moduli of Abelian varieties), and furthermore ensure that $w(i) \ne w(j)$ and $w(i) + w(j) \ne 2n + 1$ for any distinct $i, j \in \{1, 2, \dotsc, n\}$. So we can proceed as follows: In Step 1, we decide how many elements (say, $k$ many) $i$ of $\{1, 2, \dotsc, n\}$ will satisfy $w(i) \le n$. (We don't decide which ones these will be.) In Step 2, we choose these $k$ many elements $i$, calling them homebound (since they are $\le n$ and will also be sent to elements $\le n$), and we also choose the values $w(i)$ for all non-homebound elements $i$ of $\{1, 2, \dotsc, n\}$. These need to be chosen subject to the requirements that $w(i) \le n + i$ for each $i \in \{1, 2, \dotsc, n\}$. In Step 3, we finally choose the values $w(i)$ for all homebound elements $i$ of $\{1, 2, \dotsc, n\}$. These need to be chosen subject to the requirements that $w(i) \ne w(j)$ and $w(i) + w(j) \ne 2n + 1$ for any distinct $i, j \in \{1, 2, \dotsc, n\}$. Note that the first of these requirements simply forces them to be distinct, while the latter forces them to avoid $n - k$ numbers corresponding to the values at the non-homebound elements chosen in Step 2; the condition $w(i) \le n + i$ will be satisfied automatically. It is now easy to see that the number of options in Step 2 is the Stirling number of the second kind $S_2(n + 1, k + 1)$, while the number of options in Step 3 will be $k!$. So the total number of $w$'s is $\sum_{k = 0}^n k! S_2(n + 1, k + 1)$, which is OEIS sequence A000629 according to the above-quoted comment by Paul Barry. Please check.

$\endgroup$
3
  • 1
    $\begingroup$ Ha, he's probably writing a short paper generalizing the results, from past experience. $\endgroup$ Commented May 15, 2020 at 1:58
  • 1
    $\begingroup$ @TomCopeland: No, not this time -- this is a combinatorial argument, not an algebraic one, so I doubt I'll find a good way of making it slick and readable. Also, Sam Hopkins has contributed to the argument (by justifying Paul Barry's formula). $\endgroup$ Commented May 21, 2020 at 22:11
  • $\begingroup$ @darijgrinberg, certainly not trying to pressure you but the refinements of this seq, as I allude to in comments, have Coxeter A written all over them and geometric alg if you take a look at the Getzler ref, so maybe on a slow day ... . $\endgroup$ Commented May 21, 2020 at 23:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .