\documentclass[ALCO,ThmDefs,Unicode,epreuves]{cedram}
\newcommand{\ph}{\varphi}
\newcommand{\R}{\mathbb{R}}
\renewcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\mc}{\mathcal}
\newcommand{\sur}{\twoheadrightarrow}
\DeclareMathOperator{\abs}{Abs}
\DeclareMathOperator{\pre}{\mc{P}}
\DeclareMathOperator{\co}{\mc{C}}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\codim}{codim}
\DeclareMathOperator{\id}{id}
\renewcommand{\hat}{\widehat}
\renewcommand{\bar}{\overline}
\renewcommand{\tilde}{\widetilde}
%%%%%%%%% a placer avant \begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}
\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}
\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{DefTralics}
\newcommand{\abs}{\mathrm{Abs}}
\end{DefTralics}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% Auteur
%%%1
\author{\firstname{Christian} \lastname{Gaetz}}
\address{Department of Mathematics\\
Massachusetts Institute of Technology\\
Cambridge, MA\\
USA}
\email{gaetz@mit.edu}
\thanks{C.~G. was partially supported by an NSF Graduate Research Fellowship under grant no. 1122374.}
%%%2
\author{\firstname{Yibo} \lastname{Gao}}
\address{Department of Mathematics\\
Massachusetts Institute of Technology\\
Cambridge, MA\\
USA}
\email{gaoyibo@mit.edu}
%%%%% Sujet
\keywords{Absolute order, Sperner property, antichain, normalized flow, reflection group.}
\subjclass{20F55, 06A11, 06A07}
%%%%% Gestion
\DOI{10.5802/alco.114}
\datereceived{2019-10-01}
\daterevised{2020-02-06}
\dateaccepted{2020-02-12}
%%%%% Titre et résumé
\title[On the Sperner property for the absolute order]
{On the Sperner property for the absolute order on complex reflection groups}
\begin{abstract}
Two partial orders on a reflection group $W$, the \emph{codimension order} and the \emph{prefix order}, are together called the \emph{absolute order} $\abs(W)$ when they agree. We show that in this case the absolute order on a complex reflection group has the strong Sperner property, except possibly for the Coxeter group of type $D_n$, for which this property is conjectural. The Sperner property had previously been established for the \emph{noncrossing partition lattice $NC_W$}~\cite{Muhle, Reiner}, a certain maximal interval in $\abs(W)$, but not for the entire poset, except in the case of the symmetric group~\cite{Harper2019}. We also show that neither the codimension order nor the prefix order has the Sperner property for general complex reflection groups.
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\maketitle
\section{Introduction} \label{sec:intro}
A ranked poset $P$ with rank decomposition $P_0 \sqcup P_1 \sqcup \cdots \sqcup P_r$ is \emph{$k$-Sperner} if no union of $k$ antichains of $P$ is larger than the union of the largest $k$ ranks of $P$ (see~\cite{Engel} for an introduction to Sperner theory). It is \emph{strongly Sperner} if it is $k$-Sperner for $k=1,2,\ldots ,r+1$.
The \emph{absolute order} on a Coxeter group $W$ has two equivalent descriptions: one in terms of the reflection lengths of its elements, and the other in terms of the codimensions of their fixed spaces. The maximal intervals $[\id, c]$ in $\abs(W)$, where $c$ is a \emph{Coxeter element}, are known as the \emph{noncrossing partition lattices} $NC_W$. They appeared in work of Brady and Watt~\cite{Brady} on $K(\pi,1)$'s for Artin braid groups and have been studied combinatorially by Reiner~\cite{Reiner} and Armstrong~\cite{Armstrong}, among others. The posets $NC_W$ are known to be strongly Sperner~\cite{Muhle, Reiner}; this paper follows recent work of Harper and Kim~\cite{Harper2019} in studying the problem of whether the whole absolute order $\abs(W)$ is strongly Sperner.
We choose to work in the setting of general complex reflection groups, rather than just Coxeter groups. In this generality, the two orders (the \emph{prefix} and \emph{codimension} orders) do not always agree. We reserve the term \emph{absolute order} for the situation when they do agree (these cases have been classified by Foster-Greenwood~\cite{Foster-Greenwood}, see Proposition~\ref{prop:codim-equals-prefix}). It is a common feature of work in this area that the two orders are better-behaved when they agree; and Theorem~\ref{thm:main-theorem} and Conjecture~\ref{conj:type-D} below make the case that this is true in regard to the Sperner property.
Our main result follows; see Section~\ref{sec:background} for background and definitions, Section~\ref{sec:proof} for the proof, and Section~\ref{sec:counterexamples} for examples showing that the strong Sperner property does not hold in general for either the prefix order or codimension order when they disagree. Conjecture~\ref{conj:type-D} is discussed in Section~\ref{sec:type-D}.
\begin{theorem} \label{thm:main-theorem}
Let $W=W_1 \times \cdots \times W_k$ be a finite complex reflection group, where each $W_i$ is in the family $G(m,1,n)$ or is an irreducible Coxeter group of type other than type $D$; then $\abs(W)$ is strongly Sperner.
\end{theorem}
\begin{remark}
Theorem~\ref{thm:main-theorem} in the case where all $W_i$ are symmetric groups follows from a result of Harper and Kim~\cite{Harper2019}. The type $B$ case was proven independently by Harper, Kim, and Livesay~\cite{Harper2019b} while this paper was in preparation.
\end{remark}
\begin{conj} \label{conj:type-D} \text{}
\begin{enumerate}[(\alph*)]
\item %[\normalfont{(a)}]
Let $W$ be the Coxeter group of type $D_n$, then $\abs(W)$ has a normalized flow with $\nu \equiv 1$ (see Section~\ref{sec:normalized-flow}). And, therefore,
\item %[\normalfont{(b)}]
$\abs(W)$ is strongly Sperner for any finite complex reflection group $W$ such that the prefix order $\pre(W)$ is equal to the codimension order $\co(W)$.
\end{enumerate}
\end{conj}
\section{Background and definitions} \label{sec:background}
\subsection{Complex reflection groups} \label{sec:reflection-groups}
For $V$ an $n$-dimensional complex vector space, a finite group $W \subset GL(V)$ is a \emph{complex reflection group} of \emph{rank $n$} if it is generated by its set of \emph{reflections} $T=\{w \in W \: | \: \dim(V^w)=n-1\}$, where $V^w$ denotes the fixed subspace of $w$. We say $W$ is \emph{irreducible} if $V$ is irreducible as a representation of $W$. Any finite reflection group is a product of irreducible reflection groups. The finite irreducible complex reflection groups were famously classified by Shephard and Todd~\cite{Shephard}. They consist of the following groups:
\begin{itemize}
\item A 3-parameter infinite family of groups $G(m,p,n)$ where $p | m$ and $n,m \geq 1$, with the exception that $G(2,2,2)$ is reducible. $G(m,p,n)$ has rank $n$ except when $m=1$, in which case $G(1,1,n)\cong S_n$ has rank $n-1$.
\item 34 exceptional groups usually denoted $G_4,G_5,...,G_{37}$.
\end{itemize}
Among these, the groups which can be realized over a \emph{real} vector space $V$ are exactly the finite Coxeter groups. These too have a familiar classification into Cartan--Killing types:
\begin{itemize}
\item Type $A_{n-1}$: the symmetric groups $S_n = G(1,1,n)$,
\item Type $B_n$: the hyperoctahedral groups $(\Z/2 \Z) \wr S_n =G(2,1,n)$,
\item Type $D_n$: the groups $G(2,2,n)$, index-2 subgroups of the hyperoctahedral groups,
\item Type $I_2(m)$: the dihedral groups $G(m,m,2)$, and
\item The exceptional finite Coxeter groups of types $H_3, H_4, F_4, E_6, E_7, E_8$ (which coincide with $G_{23},G_{30},G_{28},G_{35},G_{36}$ and $G_{37}$ respectively).
\end{itemize}
\subsection{The absolute order on a reflection group} \label{sec:absolute-order}
Given $W$ a reflection group, the \emph{reflection length} $\ell_R(w)$ of an element $w \in W$ is defined to be the smallest $k$ such that $w=t_1 \cdots t_k$ with each $t_i \in T$, where $T$ denotes the set of all reflections in $W$. In this case, we say $t_1\cdots t_k$ is a \textit{reduced word} or \textit{reduced decomposition} for $w$. The \emph{prefix order} $\pre(W)$ is the partial order on $W$ such that $u \leq v$ if and only if
\begin{equation} \label{eq:prefix-order}
\ell_R(u)+\ell_R(u^{-1}v) = \ell_R (v).
\end{equation}
$\pre(W)$ is a ranked poset with rank function $\ell_R$.
\begin{remark}
The prefix order should not be confused with the \emph{weak order} on $W$ when $W$ is a Coxeter group. The weak order is defined by an equation similar to~\eqref{eq:prefix-order}, but with the reflection length $\ell_R$ replaced by the more classical length $\ell$, which records the shortest decomposition of an element of $W$ as a product of \emph{simple} reflections. The strong Sperner property for the weak order in type $A_n$ was previously established by the authors~\cite{weak-order-sperner}. Another related order, the (strong) Bruhat order, is known to be strongly Sperner for all Coxeter groups by work of Stanley~\cite{Stanley1980}.
\end{remark}
The \emph{codimension order} $\co(W)$ is defined so that $u \leq v$ if and only if
\begin{equation} \label{eq:codimension-order}
\codim(V^u)+\codim(V^{u^{-1}v})=\codim(V^v),
\end{equation}
where $V^w$ denotes the subspace of $V$ fixed by the action of $w$ given by the inclusion $W \subset GL(V)$.
\looseness-1
It was first proven by Carter~\cite{Carter} that when $W$ is a Coxeter group, we have $\ell_R(w)=\codim(V^w)$ for all $w \in W$, so that in particular $\co(W)=\pre(W)$. Foster-Greenwood has classified the complex reflection groups for which this coincidence continues to hold:
\begin{prop}[Foster-Greenwood~\cite{Foster-Greenwood}] \label{prop:codim-equals-prefix}
For $W$ an irreducible complex reflection group, $\co(W)=\pre(W)$ if and only if $W$ is a Coxeter group or is in the family $G(m,1,n)$.
\end{prop}
We follow Huang, Lewis, and Reiner's convention~\cite{Huang} by using the term \emph{absolute order} to refer to the codimension and prefix orders when they agree (in other parts of the literature, ``absolute order'' is used to refer to what we call the prefix order).
The functions $\ell_R(w)$ and $\codim(V^{w})$ are both \emph{subadditive}; this means that for any $u,v \in W$
\begin{align} \label{eq:subadditive}
\ell_R(uv) &\leq \ell_R(u) + \ell_R(v), \\
\codim(V^{uv}) & \leq \codim(V^u) + \codim(V^v).
\end{align}
Now, for a reducible reflection group $W \times W' \subset GL(V \oplus V')$ it is clear that $\ell_R((w,w'))=\ell_R(w)+\ell_R(w')$ and $\codim((V \oplus V')^{(w,w')})=\codim(V^w)+\codim(V^{w'})$. This implies that for either the prefix or codimension order, if $u \leq v$ and $u' \leq v'$ then $(u,u') \leq (v,v')$. The reverse implication then follows by subadditivity. Together these facts imply:
\begin{prop} \label{prop:product-of-groups-has-product-order}
Let $W \times W' \subset GL(V \oplus V')$ be a reducible reflection group. Then $\pre(W \times W') \cong \pre(W) \times \pre(W')$ and $\co(W \times W') \cong \co(W) \times \co(W')$.
\end{prop}
\subsection{Rank generating functions} \label{subsec:rank-functions}
For $P$ a finite ranked poset, we let
\[
F(P,q)=\sum_{i=0}^{\rank(P)} |P_i| \cdot q^i
\]
denote the rank generating function of $P$. It is known that for any complex reflection group $W$ the codimension generating function
\begin{equation} \label{eq:codimension-generating-function}
C(W,q)=\sum_{i=0}^{\rank(W)} |\{w \in W | \codim(V^w)=i\}| \cdot q^i
\end{equation}
is equal to $(1+e_1q)\cdots (1+e_nq)$ where the $e_i$'s are positive integer invariants of $W$ called the \emph{exponents} (see Solomon~\cite{Solomon} for a uniform proof). For general complex reflection groups, the rank of $w$ in $\co(W)$ is not necessarily equal to $\codim(V^w)$ (for example, Foster-Greenwood~\cite{Foster-Greenwood} gives examples of elements in rank one of $\co(W)$ with fixed-space codimension two), so that $C(W,q) \neq F(\co(W),q)$ in general. However, $\pre(W)$ is always ranked by $\ell_R$, and thus when $\pre(W)=\co(W)$ we have
\begin{equation} \label{eq:rank-generating-function}
F(\abs(W),q)=\prod_{i=1}^{n} \left(1+e_iq \right).
\end{equation}
This fact demonstrates the common theme that both $\pre(W)$ and $\co(W)$ are more tractable when they agree.
\subsection{The normalized flow property} \label{sec:normalized-flow}
The main tool that we will be using to establish the Sperner property of a poset is the theory of normalized flows, developed by Harper~\cite{Harper1974}, and we will be mainly following his notation in this section.
Let $G=(V=A \sqcup B,E)$ be a bipartite graph, equipped with a weight function $\nu:V\rightarrow\R_{\geq0}$. We consider $\nu$ as a measure. Namely, for any subset $ X \subset V$, let $\nu(X):=\sum_{x\in X}\nu(x)$. A \textit{normalized flow} on $G$, with respect to $\nu$, is a map $f:E\rightarrow \R_{\geq0}$ defined on the set of edges of $G$, such that for any $a\in A$ we have
\[
\sum_{b\in D(a)}f(a,b)=\nu(a)/\nu(A),
\]
and for any $b\in B$ we have
\[
\sum_{a\in D(b)}f(a,b)=\nu(b)/\nu(B),
\]
where $D(x)$ denote the set of neighbors of $x$.
Now let $P$ be a ranked poset with rank decomposition $P_0 \sqcup P_1 \sqcup \cdots \sqcup P_r$, with a weight function $\nu:P\rightarrow\R_{\geq0}$. We say that $f:E\rightarrow\R_{\geq0}$ is a \textit{normalized flow} on $P$ with respect to $\nu$, if the restriction of $f$ to the bipartite graph consisting of $P_i$ and $P_{i+1}$ and the covering relations between them is a normalized flow for each $i$. Normalized flows will be useful to us thanks to the following theorem:
\begin{theorem}[Corollary to Theorem III of~\cite{Harper1974}]\label{thm:nfsperner}
If a ranked poset $P$ has a normalized flow with respect to the weights $\nu \equiv 1$, then $P$ is strongly Sperner.
\end{theorem}
An important advantage of using normalized flows is that they behave well under product. Let $P$ and $Q$ be two ranked posets with weight functions $\nu_P$ and $\nu_Q$ respectively. Their \textit{(Cartesian) product} $P\times Q$ is $\{(p,q):p\in P,\ q\in Q\}$ where the partial order is defined as $(p,q)\leq (p',q')$ if $p\leq p'$ in $P$ and $q\leq q'$ in $Q$, with a weight function $\nu_{P\times Q}((p,q))=\nu_P(p)\cdot \nu_Q(q)$. We say that a ranked poset $P$ with rank decomposition $P_0 \sqcup P_1 \sqcup \cdots \sqcup P_r$ is \textit{log-concave} with respect to a weight function $\nu$, if $\nu(P_i)^2\geq \nu(P_{i-1})\nu(P_{i+1})$ for all $i$.
\begin{theorem}[Theorem I.C of~\cite{Harper1974}]\label{thm:nfproduct}
Let $P$ and $Q$ be two ranked posets that are log-concave with respect to weight functions $\nu_P$ and $\nu_Q$. If both of them have normalized flows, then their product also has a normalized flow and is log-concave.
\end{theorem}
Another useful property of normalized flow is described as ``the Fundamental Lemma'' by Harper~\cite{Harper1974}; we reformulate it here:
\begin{theorem}[Lemma I.B of~\cite{Harper1974}]\label{thm:fundlemma}
Let $\ph:P\rightarrow Q$, with weight functions $\nu_P$ on $P$ and $\nu_Q$ on $Q$, be a surjective, measure-preserving and rank-preserving map of ranked posets. If $Q$ admits a normalized flow with weights $\nu_Q$ and for each covering relation $q\lessdot q'$ on $Q$, the induced bipartite graph on $\ph^{-1}(\{q\})$ and $\ph^{-1}(\{q'\})$ admits a normalized flow with weights $\nu_P$, then $P$ admits a normalized flow with weights $\nu_P$.
\end{theorem}
\section{Proof of Theorem~\ref{thm:main-theorem}} \label{sec:proof}
\subsection{The generalized symmetric groups \texorpdfstring{$G(m,1,n)$}{G(m,1,n)}}\label{sec:m1n}
We first review some background on the complex reflection groups $G(m,p,n)$. Any $w\in G(m,p,n)$ can be expressed in the form $w=[a_1,\ldots,a_n|\sigma]$ where each $a_i \in\Z/m\Z$ and $p$ divides $\sum_{i=1}^na_i$. Note that we always require $p|m$. Naturally, we can view such $w=[a_1,\ldots,a_n|\sigma]$ as an element in $GL(\C^n)$ that sends the $k^{th}$ coordinate vector $v_k$ to $\exp(\frac{2\pi\sqrt{-1}a_k}{m})v_{\sigma(k)}.$ Correspondingly, we can also think of such $w$ as a permutation on $(\Z/m\Z)\times[n]$ such that $w(b,k)=(b+a_k,\sigma(k))$. There are two types of reflections in $G(m,p,n)$, which we call \textit{type (1)} and \textit{type (2)}:
\begin{enumerate}
\item $\sigma=(i,j)$ is a transposition for some $in-1$, a contradiction.
\end{proof}
Proposition~\ref{prop:DnoProd} shows that the approach used in Theorem~\ref{thm:m1n} doesn't work for the absolute order in type $D$. However, we still conjecture that the absolute order of type $D_n$ admits a normalized flow (Conjecture~\ref{conj:type-D}), and have verified this conjecture using computer search up to $n=8$.
\longthanks{The authors wish to thank Richard Stanley for suggesting this problem, and Gene B. Kim and Larry Harper for helpful correspondence.}
\bibliographystyle{amsplain-ac}
\bibliography{ALCO_Gaetz_366}
\end{document}