%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2021}
\articlenumber{82}
\usepackage{amssymb}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{thm}{Theorem}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}

\theoremstyle{definition}
\newtheorem{remark}[thm]{Remark}
\newtheorem{defn}[thm]{Definition}

\usepackage{lipsum}
\usepackage{todonotes}
\usepackage{mathtools}
\newcommand{\Red}{\mathcal{R}}
\newcommand{\Ans}{{\mathcal{M}}}
\newcommand{\AnsD}{{\mathcal{\bar{M}}}}

%% define your title in the usual way
\title{The maximum multiplicity of a generator in a reduced word}
%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Christian Gaetz \thanks{\href{mailto:crgaetz@gmail.com}{crgaetz@gmail.com}. C.G. was partially supported by an NSF Graduate Research Fellowship under grant no. 1122374.}\addressmark{1}, Yibo Gao\thanks{\href{mailto:gaoyibo@mit.edu}{gaoyibo@mit.edu}.}\addressmark{1}, Pakawut Jiradilok\thanks{\href{mailto:pakawut@mit.edu}{pakawut@mit.edu}.}\addressmark{1}, Gleb Nenashev\thanks{\href{mailto:nenashev@brandeis.edu}{nenashev@brandeis.edu}. G.N. was supported by the Knut and Alice Wallenberg Foundation, KAW\,2017.0394}\addressmark{2}, \and Alexander Postnikov\thanks{\href{mailto:apost@math.mit.edu}{apost@math.mit.edu}.}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Massachusetts Institute of Technology \\ \addressmark{2}Department of Mathematics, Brandeis University}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We study the maximum multiplicity $\Ans(k,n)$ of a simple transposition $s_k=(k \: k+1)$ in a reduced word for the longest permutation $w_0=n \: n-1 \: \cdots \: 2 \: 1$, a problem closely related to much previous work on sorting networks and on the "$k$-sets" problem.  After reinterpreting the problem in terms of monotone weakly separated paths, we show that, for fixed $k$ and growing $n$, the optimal collections are periodic in a precise sense, so that  
\[
\Ans(k,n)=c_k n + p_k(n)
\]
for a periodic function $p_k$ and constant $c_k$.  In fact we show that $c_k$ is always rational, and compute several bounds and exact values for this quantity.
}

%% put your French abstract here, or comment this out if you don't have one
%% \resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{reduced word, wiring diagram, $k$-set, weakly separated.}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{82Gaetz.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}
\label{sec:intro}

Write $s_k=(k \: k+1)$ for the adjacent transpositions in the symmetric group $S_n$.  A \emph{reduced word} for a permutation $w \in S_n$ is an expression $w=s_{i_1}\cdots s_{i_{\ell}}$ of minimal length, and in this case $\ell=\ell(w)$ is called the \emph{length} of $w$; we write $\Red(w)$ for the set of reduced words of $w$.  

There is a unique permutation $w_0=n \: n-1 \: \cdots \: 2 \: 1$ of maximum length ${n \choose 2}$, called the \emph{longest permutation}.  Reduced words of $w_0$ have been extensively studied, as maximal chains in the weak Bruhat order \cite{Edelman-Greene}, in total positivity and cluster algebras, and in the context of random sorting networks \cite{Angel}.  It is not hard to see that the minimum multiplicity of $s_k$ in a reduced word for $w_0$ is $\min(k,n-k)$, while the average multiplicity can be computed using the Edelman--Greene bijection \cite{Edelman}.  In this extended abstract we outline our study of the quantity $\Ans(k,n)$, the \emph{maximum} multiplicity of $s_k$ among all reduced words of $w_0$.  This problem is considerably more difficult, as evidenced by its close connection to the well-known $k$-sets problem.

Throughout much of the abstract we consider \emph{monotone weakly separated paths} instead of reduced words themselves.  From this perspective certain periodicity phenomena appear which are obscured when considering reduced words or their associated pseudoline arrangements.

\subsection{Relation to the $k$-sets problem}

Given a collection $A$ of $n$ distinct points in $\mathbb{R}^2$, a \emph{$k$-set} is a subset $B \subseteq A$ of size $k$ which can be separated from $A - B$ by a straight line in $\mathbb{R}^2$.  The \emph{$k$-set problem}, studied since work of Lov\'{a}sz \cite{Lovasz} and Erd\H{o}s--Lov\'{a}sz--Simmons--Straus \cite{Erdos} in the 1970s, asks for the maximum number of $k$-sets admitted by any collection $A$.  This problem has since found application in the analysis of some geometric algorithms.

A common approach to this problem proceeds by first applying projective duality to recast the problem in terms of regions of height $k$ in an arrangement of $n$ lines, and then relaxing it by considering arrangements of $n$ \emph{pseudolines} (curves in the plane such that each pair crosses exactly once).  Many of the strongest known results for the $k$-sets problem work with this relaxation, and all available data \cite{Abrego} indicates that the answers in fact agree for lines and for pseudolines.  An arrangement of $n$ pseudolines can equivalently be thought of as the \emph{wiring diagram} for a reduced word of $w_0$, and in this context the problem becomes to maximizing the total number of $s_k$'s and $s_{n-k}$'s appearing.  We show in Section~\ref{sec:rationality} that the slope $c_k$ defined by $M(k,n) \sim c_k n$ is the same whether we consider the total multiplicity of $s_k$ and $s_{n-k}$ or just that of $s_k$, so that our original problem is very closely linked to the (pseudoline version of) the $k$-sets problem.  

\subsection{Outline}

In Section~\ref{sec:prelim} we introduce monotone weakly separated paths and establish an equivalent version of the main problem in these terms.  Section~\ref{sec:bounds} introduces \emph{arc diagrams} and applies these to give bounds on $\Ans(k,n)$.  In Section~\ref{sec:rationality} we show that the quantity
\[
c_k \coloneqq \lim_{n \to \infty} \frac{\Ans(k,n)}{n}
\]
exists, is rational, and is equal to the corresponding limit which counts multiplicities of both $s_k$ and $s_{n-k}$.  Rationality is a corollary of a stronger property: optimal monotone weakly separated paths are actually periodic in a precise sense.  We also give exact values for $c_1,c_2,$ and $c_3$.  Finally, in Section~\ref{sec:other-types} we discuss the problem (which is easy for the symmetric group) of \emph{minimizing} the multiplicity of $s_k$ in a reduced word for the longest element $w_0$ in other finite Coxeter groups.


\section{Preliminaries}\label{sec:prelim}
In this section, we establish relations between reduced words and monotone weakly separated paths. We say that two different sets $I,J\subset[n]$ are \emph{weakly separated} if $\max I- J<\min J- I$ or $\max J- I<\min I- J$, and that a collection of sets is \emph{weakly separated} if each pair of sets is weakly separated. Note that being weakly separated is not a transitive relation.  Weakly separated collections are fundamental objects in the theory of the totally nonnegative Grassmannian and related cluster algebras (see, e.g.\ \cite{Postnikov-icm}). A sequence of subsets $(A_0,A_1,\ldots,A_N)$ is a \emph{monotone weakly separated path} if the collection $\{A_0,\ldots,A_N\}$ is weakly separated and for each $i=1,\ldots,N$, both $A_{i}- A_{i-1}=:\{x_i\}$ and $A_{i-1}- A_i=:\{y_i\}$ are singleton sets with $x_i>y_i$. 

Given a reduced word $\mathbf{i}\in\Red(w)$ where $w=s_{i_1}\cdots s_{i_{\ell}}$, and a fixed simple generator $s_k=(k\ k+1)$, let $a_1<\cdots <a_N$ be the positions of all $s_k$'s in $\mathbf{i}$. We obtain permutations $w^{(j)}=s_{i_1}s_{i_2}\cdots s_{i_{a_j}}$ that come from subwords of $\mathbf{i}$, where $w^{(0)}=\mathrm{id}$. For $j=1,\ldots,N$, let $A_j=\{w^{(j)}(1),w^{(j)}(2),\ldots,w^{(j)}(k)\}$ and write $P_k(\mathbf{i})=(A_0,A_1,\ldots,A_N)$. 
\begin{prop}\label{prop:equivalence-between-words-monotone-path}
Let $P_k(\mathbf{i})$ be constructed as above. Then $P_k(\mathbf{i})$ is a monotone weakly separated path. Conversely, for any monotone weakly separated path $P$ that starts with $\{1,2,\ldots,k\}$, there exists a reduced word $\mathbf{i}$ such that $P_k(\mathbf{i})=P$.
\end{prop}
\begin{proof}
Let $\mathbf{i}\in\Red(w)$ and $P_k(\mathbf{i})=(A_0,\ldots,A_N)$. If some $A_j$ and $A_{j'}$ with $j<j'$ are not weakly separated, then there exists $a\in A_j- A_{j'}$ and $a'\in A_{j'}- A_j$ such that $a>a'$. By definition, $w^{(j)}<w^{(j')}$ in the right weak Bruhat order, but $(a,a')$ is a left inversion of $w^{(j)}$, not of $w^{(j')}$, contradiction. In other words, if we consider the wiring diagram associated to $\mathbf{i}$, the wires labeled $a$ and $a'$ must intersect from $A_0$ to $A_j$, and intersect again from $A_j$ to $A_{j'}$, meaning that $\mathbf{i}$ cannot be reduced. As a result, $\{A_0,\ldots,A_N\}$ is a weakly separated collection. At the same time, $A_j=A_{j-1}-\{x\}\cup\{y\}$ if we write $(x\ y)s_{i_1}\cdots s_{i_{a_j-1}}=s_{i_1}\cdots s_{i_{a_j-1}}s_{i_{a_j}}$. And $x<y$ since $\mathbf{i}$ is reduced. Thus, $P_k(\mathbf{i})=(A_0,\ldots,A_N)$ is a monotone weakly separated path.

Now suppose that we are given a monotone weakly separated path $P=(A_0,\ldots,A_N)$ with $A_0=\{1,\ldots,k\}$. Start with $w^{(0)}=\mathrm{id}$. We are going to construct $w^{(1)},w^{(2)},\ldots$ with a reduced word $\mathbf{i}$ along the way such that $P_k(\mathbf{i})=P$. Suppose that we have constructed $w^{(j)}=s_{i_1}\cdots s_{i_{m}}$ and let $x\in A_j- A_{j+1}$, $y\in A_{j+1}- A_j$ with $x<y$. Suppose that $w^{(j)}(a)=x$ and $w^{(j)}(b)=y$ with $a\leq k<b$. We can continue the construction of $\mathbf{i}$ by $w^{(j+1)}=w^j (s_{a}s_{a+1}\cdots s_{k-1})(s_{b-1}s_{b-2}\cdots s_{k+1})s_k$. Here, $s_{a}s_{a+1}\cdots s_{k-1}$ moves $x$ from position $a$ to position $k$ while $s_{b-1}s_{b-2}\cdots s_{k+1}$ moves $y$ from position $b$ to position $k+1$. In the end, the $s_k$ exchanges the values $x$ and $y$. Therefore, we automatically have $\{w^{(j+1)}(1),\ldots,w^{(j+1)}(k)\}=A_j-\{x\}\cup\{y\}=A_{j+1}$ as desired. The only thing left to show is that the word $\mathbf{i}$ coming from such construction is reduced.

If $\mathbf{i}$ is not reduced, we can without loss of generality assume that in some step when we are constructing $w^{(j+1)}$ from $w^{(j)}$, a simple generator $s_p$ exchanges a larger value at position $p$ with a smaller value at position $p+1$. Keep the notation as in the above paragraph. We can't have $p=k$ since $s_k$ always exchanges $A_{j}- A_{j+1}$ at position $k$ with $A_{j+1}- A_j$ at position $k+1$. So by symmetry, we assume $p<k$, and that such $s_p$ exchanges value $x\in A_{j+1}- A_j$ at position $p$ with value $z$ at position $p+1$, with $x>z$. Since $z<x$, the values $z$ and $x$ must have been switched before, when we are constructing $w^{(j'+1)}$ from $w^{(j')}$, with $j'<j$. By construction, we are either moving $z$ out of $A_{j'}$ to $A_{j'+1}$, or moving $x$ into $A_{j'+1}$ from out of $A_{j'}$. In both cases, $z\notin A_{j'+1}$ and $x\in A_{j'+1}$. As a result, $x\in A_{j'+1}- A_{j+1}$, $z\in A_{j+1}- A_{j'+1}$, but $z<x$. As $A_{j+1}$ and $A_{j'+1}$ are weakly separated, we must have $\max A_{j+1}- A_{j'+1}<\min A_{j'+1}- A_{j+1}$. But $j'<j$, there cannot possibly be a monotone path from $A_{j'+1}$ to $A_{j+1}$. Contradiction. Thus, this construction results in a reduced word $\mathbf{i}$ as desired.
\end{proof}

Consequently, we say that $P_k(\mathbf{i})$ is the monotone weakly separated path associated to $\mathbf{i}\in\Red(w)$. Clearly, if $P_k(\mathbf{i})$ consists of $N+1$ subsets from $A_0$ to $A_N$, then there are exactly $N$ $s_k$'s in $\mathbf{i}$. Proposition~\ref{prop:equivalence-between-words-monotone-path} allows us to translate the problem of finding the maximal number of $s_k$'s in $\Red(w)$ to finding the longest monotone weakly separated path that starts at $\{1,2,\ldots,k\}$.



\section{Bounds for $\Ans(k,n)$ and arc diagrams}
\label{sec:bounds}


\subsection{$\Ans(k,n)$ and arc diagrams}
For positive integer $1 \le k \le n-1$, let $\Ans(k,n)$ denote the maximum possible number of appearances of $s_k$'s in a reduced word of $w_0 \in S_n$. In this section, we describe known values for $\Ans(k,n)$ and, in situations where values are yet unknown, current bounds we have had.

For our purpose, by a {\em monotone separated sequence} from $\{1,2, \ldots, k\}$ to $\{n-k+\nobreak{}1, \ldots ,\allowbreak{}n-1,n\}$, we mean a finite sequence $(T_1, T_2, \ldots, T_m)$ of $k$-tuples of integers in $[n]$ which satisfies
\begin{itemize}
\item $T_1 = \{1, 2, \ldots, k\}$,
\item $T_m = \{n-k+1, \ldots, n-1, n\}$,
\item for each $i \in [m-1]$, there exist $\alpha, \beta \in [n]$ for which $T_i - T_{i+1} = \{\alpha\}$ and $T_{i+1} - T_i = \{\beta\}$ and $\alpha < \beta$, and
\item for any $1 \le i < j \le m$, every element in $T_j - T_i$ is greater than every element in $T_i - T_j$.
\end{itemize}
When $k < n$ are given, the maximum possible number of terms in a monotone separated sequence from $\{1, 2, \ldots, k\}$ to $\{n-k+1, \ldots, n-1, n\}$ is exactly $\mathcal{M}(k,n) + 1$. Therefore, we may translate the studies of the maximum number of appearances of $s_k$'s to those of monotone separated sequences.

An important tool for investigating monotone separated sequences is the arc diagram, which we define as follows. The {\em arc diagram} of a monotone separated sequence $(T_1, T_2, \ldots, T_m)$ is the simple undirected graph on the vertex set $[n]$ in which an edge $(i,j)$ appears if and only if there exists $a \in [m-1]$ such that $\{i,j\} = (T_a - T_{a+1}) \cup (T_{a+1} - T_a)$. The number of edges in an arc diagram is exactly one less than the number of terms in the monotone separated sequence. Thus, $\mathcal{M}(k,n)$ is the maximum possible number of edges in an arc diagram obtained from a monotone separated sequence from $\{1, 2, \ldots, k\}$ to $\{n-k+1, \ldots, n-1, n\}$.

It is helpful to think of arc diagrams as geometric objects embedded on the plane. We put the vertex $i \in [n]$ of the diagram at the point $(i,0) \in \mathbb{R}^2$ so that the vertices $1, 2, \ldots, n$ become collinear points in this order. Furthermore, we draw each edge $(i,j)$ on the arc diagram as a semicircle on the upper-half plane with the segment connected the points $(i,0)$ and $(j,0)$ as a diameter. We also assign {\em weights} to these edges. Imagine that each semicircular curve in an arc diagram has weight $1$. Let us further assume that for each curve, the weight is distributed uniformly across the horizontal length. For example, if we are considering the edge $e$ from $(1,0)$ to $(4,0)$, then there is weight exactly $2/3$ {\em above} the segment $[2,4]$ coming from this edge $e$. Since the weight of the whole diagram is the number of edges, we have that $\Ans(k,n)$ is the maximum possible weight in an arc diagram.

By considering the weight, we obtain the following upper bound for $\Ans(k,n)$.

\begin{prop} \label{prop:upper}
$\Ans(k,n) \le \Bigg( \underbrace{1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{3} + \frac{1}{3} + \frac{1}{3} + \frac{1}{4} + \cdots }_{k \text{ terms}} \Bigg) \cdot n$.
\end{prop}
\begin{proof}[Proof (Sketch)]
For each $i \in [n-1]$, the vertical strip above the segment $[i,i+1]$ on the plane contains at most $k$ distinct semicircle parts. Suppose there are $\ell$ parts. For each $t \in \mathbb{Z}_{\ge 1}$, there are at most $t$ of these $\ell$ parts which come from semicircles of diameter $t$. Therefore, there are at most $t$ parts which contribute the weight of $1/t$ to the segment $[i,i+1]$. This gives the desired bound.
\end{proof}
\begin{cor}
\label{cor:upper_bound}
	$\Ans(k,n) \le \sqrt{2k} \cdot  n$.
\end{cor}

We remark that one can easily improve the bound given in Proposition \ref{prop:upper} using a more careful version of the same argument as in the proof above. Namely, note that the segments $[i,i+1]$ near the {\em ends} (vertices $1$ or $n$) contribute less weight because there are fewer than $k$ pieces of curves above those segments. However, this would simply give an improvement of $O_k(1)$ and would not improve the multiplicative constant in front of $n$.

\bigskip

\subsection{Explicit formulas for $\Ans(k,n)$ for specific values of $k$}
We now describe the formulas for $\Ans(k,n)$ for $k = 1, 2, 3$. When $k=1$, it is easy to see that $\Ans(1,n) = n-1$ for each $n \in \mathbb{Z}_{\ge 2}$. Now let's consider the case when $k = 2$. A more careful version of Proposition \ref{prop:upper} gives the bound $\Ans(2,n) \le \left\lfloor \frac{3n-5}{2} \right\rfloor$, for each $n \in \mathbb{Z}_{\ge 3}$. In fact, we claim that $\Ans(2,n) = \left\lfloor \frac{3n-5}{2} \right\rfloor$ by giving explicit constructions. Let us construct an infinite sequence of ordered pairs inductively as follows. In the first step, let $\mathfrak{s}_1 := \left(\{1,2\}\right)$. In the $i$-th step, for each $i \ge 2$, suppose that the rightmost entry of $\mathfrak{s}_{i-1}$ is the ordered pair $\{a,a+1\}$, we append
\[
\{a,a+2\}, \{a+1, a+2\}, \{a+2, a+3\}
\]
in this order to the right end of $\mathfrak{s}_{i-1}$, and declare the newly constructed sequence to be $\mathfrak{s}_i$. The {\em limit} of $\mathfrak{s}_i$ as $i \to \infty$ is the infinite sequence
\[
12 - 13 - 23 - 34 - 35 - 45 - 56 - 57 - 67 - 78 - 79 - 89 - \cdots.
\]
It is straightforward to check that for each $n \in \mathbb{Z}_{\ge 3}$, the first $\left\lfloor \frac{3n-5}{2} \right\rfloor + 1$ terms of the infinite sequence above form a monotone separated sequence from $\{1, 2\}$ to $\{n-1, n\}$. This completes the proof of the formula
\[
\Ans(2,n) = \left\lfloor \frac{3n-5}{2} \right\rfloor.
\]

Let us make a remark about the construction of the infinite sequence above. We think of the infinite sequence as an infinite repetition of the {\em repeatable} pattern $12 - 13 - 23 - 34$. We start with the pattern and {\em repeat} it many times to obtain the infinite sequence. Note that not all patterns are repeatable: if we repeat some monotone separated sequence, then the resulting sequence might no longer by separated. For example, the pattern $12 - 13 - 23$ is {\em not} repeatable, since $12 - 13 - 23 - 24 - 34 - \cdots$ is not separated. (Note the interlacing between $13$ and $24$.)

Now we consider the case when $k = 3$. The upper bound in Proposition \ref{prop:upper} gives $\Ans(3,n) \le 2n - O(1)$. It turns out that the coefficient $2$ in front of $n$ is not the right constant for $\Ans(3,n)$. To see why, we give a heuristic argument as follows. For the value of $\Ans(3,n)$ to be $2n-O(1)$ as $n$ gets large, almost every segment $[i,i+1]$ in the arc diagram must contribute weight $2$ to the diagram. Each such segment must contain exactly three pieces of semicircles above it: one contributing weight $1$ that is connecting $i$ and $i+1$, one contributing weight $1/2$ that is connecting $i-1$ and $i+1$, and one contributing weight $1/2$ that is connecting $i$ and $i+2$. Such a diagram would be {\em too dense} to have come from a valid monotone separated sequence from $\{1,2,3\}$ to $\{n-2, n-1, n\}$. We have the following theorem (whose proof we currently omit here).

\begin{thm}[Decomposition Theorem for $k = 3$] \label{thm:PDT}
Let $n \ge 4$ be a positive integer. Let $\mathcal{G}$ be any arc diagram for a monotone separated sequence from $\{1, 2, 3\}$ to $\{n-2, n-1, n\}$. Then, there exist interior-disjoint closed intervals $I_1, I_2, \ldots, I_t$ such that (i) $[1,n] = \bigcup_{i=1}^t I_i$, (ii) each $I_i$ has length $\mu(I_i)$ at most $4$, and (iii) the weight of the semicircle pieces above each $I_i$ is at most $\frac{11}{6} \cdot \mu(I_i)$.
\end{thm}

Theorem \ref{thm:PDT} implies that $\Ans(3,n) \le \frac{11}{6} n - O(1)$. Like before, a more careful version of the same argument gives $\Ans(3,n) \le \left\lceil \frac{11}{6} n \right\rceil - 5$, for each $n \in \mathbb{Z}_{\ge 4}$. In fact, we claim that $\Ans(3,n) = \left\lceil \frac{11}{6} n \right\rceil - 5$. To do so, we once again find a suitable repeatable pattern. The construction for each $n \in \mathbb{Z}_{\ge 4}$ will be divided into cases according to $n$ modulo $6$. To construct the sequence for $n$ we first repeat the repeatable pattern
\[
P = 123-124-125-145-245-345-456-457-567-578-678-789
\]
many times, and we finish the sequence with a certain pattern that depends on $n$ modulo $6$ (full details of which are not shown here). The construction matches the proven upper bound, whence
\[
\Ans(3,n) = \left\lceil \frac{11}{6} n \right\rceil - 5,
\]
for all $n \in \mathbb{Z}_{\ge 4}$.







\section{Asymptotics of $\Ans(k,n)$: existence and rationality.}
\label{sec:rationality}

Let us define the constant $c_k := \lim_{n \to \infty} \frac{\Ans(k,n)}{n}$ for any $k\in \mathbb{N}$. From the arguments from previous section, we know that this limit exists for $k=1,2,3$. In particular, we have found $c_1 = 1$, $c_2 = \frac{3}{2}$, and $c_3 = \frac{11}{6}$. These constants are well defined. 

\begin{thm}
The limit $c_k$ exists and it is a rational number for any $k\in \mathbb{N}$.
\end{thm}
The prove of existence is trivial, it is based on two inequalities for $\Ans$.
\begin{lem}
For three integers $k<n\leq m,$ we have $$\Ans(k,n)\leq \Ans(k,m).$$	
\end{lem}
\begin{lem}
For three integers $k< n, m$ we have $$\Ans(k,n)+ \Ans(k,m)\leq \Ans(k,n+m).$$	
\end{lem}
\begin{proof}[Proof of existence]
By two lemmas, we know that for any $k\leq n\leq m,$ we have $$\Ans(k,m)\geq \lfloor \frac{m}{n} \rfloor \Ans(k,n).$$
Fix any $n$, then $$\frac{\Ans(k,m)}{m}\geq \lfloor \frac{m}{n}\rfloor \frac{n}{m} \frac{\Ans(k,n)}{n}.$$ Since $\lfloor \frac{m}{n}\rfloor \frac{n}{m}$ tends to $1$ when $m$ goes to infinity, any accumulation point is at least $\frac{\Ans(k,n)}{n}$.
 By Corollary~\ref{cor:upper_bound}, we know that $\frac{\Ans(k,n)}{n}<\sqrt{2k}$, i.e., the sequence $\frac{\Ans(k,n)}{n}$ is bounded. Hence, it has a limit.	
\end{proof}

Our proof of rationality is standard in combinatorics, however it is very technical. 
\begin{proof}[Sketch of the proof of rationality]
Fix $k$ for this proof.
We will work with reduced decompositions of words in $S_n$ and with its wiring diagrams (we can work with any permutation instead of the longest). The left order of wires are $(1,2,3,\ldots,n)$ (the 1st wire is on the top), we read all wire diagrams from left to right. We will change our wiring diagrams.

Given a word $W$, we construct the word $W'$ in the following way: 
\begin{itemize}
\item Start from the left and if we found an intersection of wire $i$ and $i+1$ on the level distinct from $k$, then we just forget about this intersection. This word is still reduced.	
\item If for wire $a$ we have $k$ bigger wires, which are higher than $a$, then we can immediately forget about the wire $a$. Because we can't do swaps with $a$ on the level $k$. Therefore from this moment we say that the wire $a$ has place $\infty$ ($a$ strictly goes  down).
\item Repeat the previous two steps as long as possible.
\end{itemize}

We can't repeat this simplifications forever, therefore we will stop at some moment. Wiring diagrams $W'$ and $W$ have the same number of intersections on the level $k$. Therefore, it is enough to work with these \textit{simplified} diagrams. 

Now we can say that we also have infinitely many wires instead of $n$. We read these simplified wiring diagram from the left and we can encode any configuration by natural number and some combinatorics. The natural number at the moment is the number of wires went to infinity. For the other wires it is only important their orders at the beginning and at this moment, we call this \textit{combinatorics} at this moment.  The important observation is that simplified wiring diagrams have only finitely many distinct combinatorics. Let $\mathcal{C}_k$ be the set of all such possible combinatorics (this set depends on $k$). 

We encode each wiring diagram at each moment by a pair of natural number and a combinatoric. Since the number of combinatorics is bounded, we get that $c_k$ is rational. In particular, we can prove that the size of the set $\mathcal{C}_k$ is at most $k^{k^2+2k}$, which gives to us that the denominator of $c_k$ is also bounded by $k^{k^2+2k}$. 
\end{proof}

It is natural to consider another problem, namely when we want to maximize the appearances of $s_k$ and $s_{n-k}$. Let $\AnsD(k,n)$ be the maximal number of appearances of $s_k$ and $s_{n-k}$ in the reduced words from $S_n$. The asymptotic of these numbers are the same as for the above problem. \begin{thm} For any $k\in \mathbb{N}$, there is a limit $\lim_{n\to +\infty}\frac{\AnsD(k,n)}{n}$ and it is given by
\label{thm:dk}
$$\lim_{n\to +\infty}\frac{\AnsD(k,n)}{n}=\lim_{n\to +\infty}\frac{\Ans(k,n)}{n}=c_k.$$
\end{thm}
\begin{proof}
Consider any reduced word and its wiring diagram. We say that a wire has type $(i,j,\pm)$, if its highest position is $i$ and its lowest position is $j$, and $+\ (-)$ means that the highest position is to the left (right) of the lowest position.
Note, that there is no two wires of the same type (otherwise they should intersect at least twice, but our word is reduced).
Let $a$ be the number of wires, which were at some moment at $k$ highest positions; 
Let $b$ be the number of wires, which were at some moment at $k$ lowest positions.
We counted at most $2k^2$ wires twice, then $a+b\leq n+2k^2$.
Note that the number of $s_k$ depends only on these $a$ wires
and the number of $s_{n-k}$ depends only on that $b$ wires.
Hence, the number of appearances of $s_k$ and $s_{n-k}$ in this reduced word is at most $\Ans(k,a)+\Ans(k,b)<c_k a+c_k b\leq c_k(n+2k^2) $.

Therefore $\Ans(k,n)\leq \AnsD(k,n)<c_k(n+2k^2)$. Then there is the limit $\lim_{n\to +\infty}\frac{\AnsD(k,n)}{n}$ ant it is equal to $c_k$.
\end{proof}

\section{Other types}
\label{sec:other-types}
In this section, we investigate a related question: for the longest element $w_0$ of a finite Coxeter group $W$, what is the minimum number of appearances of a generator $s_i$ in $\Red(w_0)$, the set of reduced words for $w_0$. This question is very easy in type $A_{n-1}$ where $W\simeq\mathfrak{S}_n$. Namely, the minimum number of occurrences of the simple transposition $(i\ i+1)$ in $\Red(w_0)$ is $\min\{i, n-i\}$. We will treat this matter in a type-uniform way and show that there is a surprising phenomenon with respect to these numbers and the Cartan matrix of $W$ (Theorem~\ref{thm:Vinberg-main}).

Throughout this section, let $$W=\langle s_1,\ldots,s_n\:|\: (s_is_j)^{m_{ij}}=\mathrm{id}\text{ for all }i,j\rangle$$ be a finite Coxeter group generated by a set of simple reflections $S=\{s_1,\ldots,s_n\}$. For $w\in W$, let $\ell(W)$ denote the Coxeter length of $w$. For $J \subseteq S$, the \emph{parabolic subgroup} $W_J$ is the subgroup of $W$ generated by $J$, viewed as a Coxeter group with simple reflections $J$.  Each left coset $wW_J$ of $W_J$ in $W$ contains a unique element $w^J$ of minimal length, and the set $\{w^J \: | \: w \in W\}$ of these minimal coset representatives is called the \emph{parabolic quotient} $W^J$.  Letting $w_J \in W_J$ be the unique element such that $w^Jw_J=w$, we have $\ell(w^J)+\ell(w_J)=\ell(w)$ and this is called the \emph{parabolic decomposition} of $w$. As $W$ is finite, $W^J$ is finite and it contains a unique element $w_0^J$ of maximum length. We utilize the Bruhat order on $W$ and $W^J$, where $u\leq w$ if $u$ equals a subword of a (or equivalently, any) reduced word of $w$. We refer readers to \cite{bjorner-brenti} for a detailed exposition on Coxeter groups.

We start with an algorithm to compute the minimum number of $s_i$ that appears in $\Red(w)$ for all $w$. 
\begin{prop}\label{prop:min-algorithm}
Fix $w\in W$ and $s_i\in S$. Define a sequence of Coxeter group elements $w^{(0)},w^{(1)},\ldots$ as follows: $w^{(0)}=w^{J_i}$ and $w^{(k+1)}=(w^{(k)}s_i)^{J_i}$ if $w^{(k)}\neq\mathrm{id}$, for $k\geq0$, where $J_i=S-\{s_i\}$ is a maximal subsystem of $S$. Then the minimum number of $s_i$ that appears in $\Red(w)$ is the $k$ for which $w^{(k)}=\mathrm{id}$.
\end{prop}
\begin{proof}
First notice that in this procedure, if $w^{(j)}\neq\mathrm{id}$, then as $w^{(j)}\in W^{J_i}$, it must have a single descent at $s_i$. As a result, $\ell(w^{(j+1)})\leq\ell(w^{(j)}s_i)<\ell(w^{(j)})$ so we will eventually end up at the identity. This procedure also produces a (class of) reduced word of $w$ with $k$ $s_i$'s where $w^{(k)}=\mathrm{id}$.

Let $k$ be such that $w^{(k)}=\mathrm{id}$ and take an arbitrary reduced word $s_{i_1}s_{i_2}\cdots s_{i_{\ell}}$ of $w$. Pick out the $s_i$'s in this reduced word as $i_{a_K}=i_{a_{K-1}}=\cdots=i_{a_1}=i$ where $a_K<a_{K-1}<\cdots<a_1$. For $j=0,1,\ldots,K-1$, let $u^{(j)}=s_{i_1}s_{i_2}\cdots s_{i_{a_{j+1}}}$ which is the product from $s_{i_1}$ to the $(j+1)^{th}$ $s_i$ in this reduced word counted from the right. Also say $u^{(K)}=\mathrm{id}$. 

Recall the following standard fact of Coxeter groups: if $x\leq y$, then $x^J\leq y^J$ for any subsystem $J\subset S$. This can be proved via an application of the subword property of Bruhat orders. Also see \cite{bjorner-brenti}.

We now show that $u^{(j)}\geq w^{(j)}$ for $j=0,1,\ldots,k$ in the Bruhat order by induction. For the base case, notice that both $u^{(0)}$ and $w^{(0)}$ is in the left coset $wW_{J_i}$ and since $w^{(0)}$ is the minimal coset representative, we have $u^{(0)}\geq w^{(0)}$. Now assume $u^{(j)}\geq w^{(j)}\neq\mathrm{id}$ for some $j\geq0$. By definition, both of them have a right descent at $s_i$ so we have $u^{(j)}s_i\geq w^{(j)}s_i$ by the fact in the last paragraph with $J=\{s_i\}$. With another application of this fact with $J=J_i$, we have $(u^{(j)}s_i)^{J_i}\geq (w^{(j)}s_i)^{J_i}=w^{(j+1)}$. At the same time, $u^{(j+1)}$ and $u^{(j)}s_i$ are in the same coset of $W_{J_i}$ by definition, so $u^{(j+1)}\geq (u^{(j)}s_i)^{J_i}\geq w^{(j+1)}$. The induction step goes through.

Finally, $u^{(k-1)}\geq w^{(k-1)}\neq\mathrm{id}$. This means $u^{(k-1)}\neq\mathrm{id}$ so $K>k-1$, $K\geq k$ as desired.
\end{proof}

Recall that a \emph{generalized Cartan matrix} $A$ of a Coxeter system $(W,S)$ is a real $n\times n$ matrix such that
\begin{itemize}
\item $A_{ii}=2$ for $i=1,\ldots,n$ and $A_{ij}\leq0$ for $i\neq j$,
\item $A_{ij}<0$ if and only if $A_{ji}<0$ and $A_{ij}A_{ji}=m_{ij}-2$ for $i\neq j$.
\end{itemize}
We say that a generalized Cartan matrix $A$ is \emph{restricted} if $m_{ij}=3$, or equivalently, there is a single edge between $s_i$ and $s_j$ in the Dynkin diagram, implies that $A_{ij}=A_{ji}=-1$. Note that if $(W,S)$ is simply-laced, then any restricted generalized Cartan matrix is the Cartan matrix. We now state our main result of the section.

\begin{thm}\label{thm:Vinberg-main}
Let $W$ be a finite Weyl group generated by $S=\{s_1,\ldots,s_n\}$. Let $v\in\mathbb{R}_{>0}^n$ be such that $v_i$ is the minimum number of appearances of $s_i$ in a reduced word of $w_0$. Then there exists a restricted generalized Cartan matrix $A\in\mathbb{R}^{n\times n}$ of $W$ such that $Av\geq\mathbf{0}$, where the comparison is made entry-wise.
\end{thm}



\acknowledgements{We are grateful to the participants of the MIT Combinatorics Preseminar, where some initial discussions of this problem took place, and in particular to Darij Grinberg for sharing this problem. We would like to thank Sorawee Porncharoenwase for producing useful computer code for this project.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
