%% 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]{FPSAC2020}
\articlenumber{18}
\addbibresource{fpsac.bib}
%% 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}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\theoremstyle{definition}
\newtheorem{problem}[thm]{Problem}
\crefname{problem}{Problem}{Problems}

%\usepackage{lipsum}
\usepackage{MnSymbol,amssymb,scalerel}

\DeclareMathOperator{\GT}{\underline{GT}}
\DeclareMathOperator{\MT}{\underline{MT}}
\DeclareMathOperator{\SGT}{\underline{SGT}}
\DeclareMathOperator{\AP}{\underline{AP}}
\DeclareMathOperator{\AR}{\underline{AR}}
\DeclareMathOperator{\DPP}{DPP}
\DeclareMathOperator{\ASM}{ASM}
\DeclareMathOperator{\B}{B}
\DeclareMathOperator{\sign}{sign}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\N}{{\mathbb N}}
\renewcommand{\u}[1]{\underline{#1}}
\newcommand{\si}[2]{\u{[#1,#2]}}
\newcommand{\q}[1]{\mathbf #1}
\newcommand{\p}[1]{\mathcal #1}
\newcommand{\seswarrow}{\swarrow \!\!\!\!\!\;\!\! \searrow}
\newcommand{\nenwarrow}{\nwarrow \!\!\!\!\!\;\!\! \nearrow}
\DeclareMathOperator{\rot}{rot}

%% define your title in the usual way
\title{The first bijective proof of the refined ASM theorem}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Ilse Fischer\thanks{\href{mailto:ilse.fischer@univie.ac.at}{ilse.fischer@univie.ac.at}. Supported by the Austrian Science Foundation FWF, SFB grant F50.}\addressmark{1} \and Matja\v z Konvalinka\thanks{\href{mailto:matjaz.konvalinka@fmf.uni-lj.si}{matjaz.konvalinka@fmf.uni-lj.si}. Supported by the Slovenian Research Agency (research core funding No. P1-0294).}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Faculty of Mathematics, University of Vienna, Vienna, Austria \\ \addressmark{2}Faculty of Mathematics and Physics, University of Ljubljana \& Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia}

%% 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{Alternating sign matrices are known to be equinumerous with descending plane partitions, totally symmetric self-complementary plane partitions and al\-ter\-nat\-ing sign tri\-angles, but a bijective proof for any of these equivalences has been elusive for almost 40 years. In this extended abstract, we provide a sketch of the first bijective proof of the enumeration formula for alternating sign matrices, and of the fact that alternating sign matrices are equinumerous with descending plane partitions. The bijections are based on the operator formula for the number of monotone triangles due to the first author. The starting point for these constructions were known ``com\-pu\-ta\-tional'' proofs, but the combinatorial point of view led to several drastic modifications and simplifications.  We also provide computer code where all of our constructions have been implemented.}

%% put your keywords here, or comment this out if you don't have them yet
%\keywords{math, maths, mathematics}

%% 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{sample.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}

An \emph{alternating sign matrix} (ASM) is a square matrix with entries in $\{0,1,-1\}$ such that in each row and each column the non-zero entries alternate and sum up to $1$. Robbins and Rumsey introduced alternating sign matrices in the 1980s \cite{lambda}  when studying their \emph{$\lambda$-determinant} (a generalization of the classical determinant) and showing that the $\lambda$-deter\-mi\-nant can be expressed as a sum over all alternating sign matrices of fixed size. The classical determinant is obtained from this by setting $\lambda=-1$, in which case the sum reduces so that it extends only over all ASMs \emph{without} $-1$'s, i.e., permutation matrices, and the well-known formula of Leibniz is recovered.
Numerical experiments led Robbins and Rumsey to conjecture that the number of $n \times n$ alternating sign matrices is given by the surprisingly simple product formula
\begin{equation}
\label{asm}
\prod_{i=0}^{n-1} \frac{(3i+1)!}{(n+i)!}.
\end{equation}



Back then the surprise was even bigger when they learned from Stanley (see \cite{BrePro99,Bre99}) that this product formula had recently also appeared in Andrews' paper \cite{And79} on his proof of the weak Macdonald conjecture, which in turn provides a formula for the number of \emph{cyclically symmetric plane partitions}. As a byproduct, Andrews had introduced \emph{descending plane partitions}
and had proved that the number of descending plane partitions (DPPs) with parts at most $n$ is also equal to \eqref{asm}. A descending plane partition is a filling of a shifted Ferrers diagram with positive integers that decrease weakly along rows and strict along columns such that the first part in each row is greater than the length of its row and less than or equal to the length of the previous row.


Since then the problem of finding an explicit bijection between alternating sign ma\-tri\-ces and descending plane partitions has attracted considerable attention from com\-bi\-na\-to\-rialists, and to many of them it is a miracle that such a bijection has not been found so far. All the more so because Mills, Robbins and Rumsey also introduced several ``statistics'' on alternating sign matrices and on descending plane partitions for which they had strong numerical evidence that the joint distributions coincide as well, see \cite{MilRobRum83}.



There were a few further surprises yet to come. Robbins introduced a new operation on plane partitions, \emph{complementation}, and had strong numerical evidence that totally symmetric self-complementary plane partitions (TSSCPPs) in a $2n \times 2n \times 2n$-box are also counted by \eqref{asm}. Again this was further supported by statistics that have the same joint distribution as well as certain refinements, see \cite{MilRobRum86,Kra96,krattsurvey,bianecheballah}. We still lack an explicit bijection between TSSCPPs and ASMs, as well as between TSSCPPs and DPPs.



In his collection of bijective proof problems (which is available from his webpage) Stanley says the following about the problem of finding all these bijections: ``\emph{This is one of the most intriguing open problems in the area of bijective proofs.}'' In Krattenthaler's survey on plane partitions \cite{krattsurvey} he expresses his opinion by saying: ``\emph{The greatest, still unsolved, mystery concerns the question of what plane partitions have to do with alternating sign matrices.}''



Many of the above mentioned conjectures have since been proved by non-bijective means. Zeilberger \cite{Zei96a} was the first who proved that $n \times n$ ASMs are counted by \eqref{asm}. Kuperberg gave another shorter proof \cite{Kup96} based on the remarkable observation that the \emph{six-vertex model} (which had been introduced by physicists several decades earlier) with domain wall boundary conditions is equivalent to ASMs, and he used the tech\- niques that had been developed by physicists to study this model. Andrews enumerated TSSCPPs in \cite{And94}. The equivalence of certain statistics for ASMs and of certain statistics for DPPs has been proved in \cite{BehDifZin13}, while for ASMs and TSSCPPs see \cite{Zei96b,FonZin08}, and note in particular that already in Zeilberger's first ASM paper \cite{Zei96a} he could deal with an important refinement.
Further work including the study of \emph{symmetry classes} has been accomplished; for a more detailed description of this we defer to \cite{BehFisKon17}. Then, in very recent work, alternating sign triangles (ASTs) were introduced in \cite{AyyBehFis16}, which establishes a fourth class of objects that are equinumerous with ASMs, and also in this case nobody has so far been able to construct a bijection.



The first author gave her ``own'' proof of the ASM theorem in \cite{Fis06,Fis07,Fis16} and expressed some speculations in the direction of converting these proofs into bijections in the final section of the last paper. Part of the objective, namely bijective proofs of the enumeration formula for the number of ASMs and of the fact that ASMs and DPPs are equinumerous, has now been achieved in \cite{PartI,PartII}, the first two papers in a planned series. This extended abstract presents the major steps in these constructions.

After having figured out how to actually convert computations and also having shaped certain useful fundamental concepts related to  \emph{signed sets} (see \cref{sec:signed}), the translation of several steps became quite straightforward; some steps were quite chal\-leng\-ing. Then a certain type of (exciting) dynamics evolved, where the combina\-to\-rial point of view led to simplifications and other (in some cases drastic) modifications, and after this process the original ``computational'' proof is in fact rather difficult to recognize.

The bijection that underlies the bijective proof of the enumeration formula of ASMs as well as the one of the refined enumeration formula involves the following sets:
\begin{itemize}
\item Let $\ASM_{n}$ denote the set of ASMs of size $n \times n$, and, for $1 \le i \le n$, let $\ASM_{n,i}$ denote the subset of $\ASM_n$ of matrices that have the unique $1$ in the first row in column $i$. There is an obvious bijection $\ASM_{n,1} \to \ASM_{n-1}$ which consists of deleting the first row and first column.
\item Let $\B_n$ denote the set of $(2n-1)$-subsets of $[3n-2]=\{1,2,\ldots,3n-2\}$ and, for $1 \le i \le n$, let $\B_{n,i}$ denote the subset of $\B_n$ of those subsets whose median is $n+i-1$. Clearly, $|\B_n| = \binom{3n-2}{2n-1}$ and $|\B_{n,i}| = \binom{n+i-2}{n-1} \binom{2n-i-1}{n-1}$.
\item Let $\DPP_n$ denote the set of descending plane partitions with parts no greater than $n$; let $\DPP_{n,i}$ the subset of descending plane partitions with $i-1$ occurrences of $n$. We clearly have $\DPP_{n,1} = \DPP_{n-1}$.
\end{itemize}

To emphasize that we are not merely interested in the fact that two signed sets have the same size, but want to use the constructed signed bijection later on, we will be using a convention that is slightly unorthodox in our field. Instead of listing our results as lemmas and theorems with their corresponding proofs, we will be using the Problem--Construction terminology. See for instance \cite{Voevodsky} and \cite{Bauer}. Our main results are the constructions solving the following two problems.

\begin{problem}(\cite[Problem 1]{PartII}) \label{prob:main}
 Given $n \in \N$, $1 \leq i \leq n$, construct a bijection
 $$\DPP_{n-1} \times \B_{n,1} \times \ASM_{n,i} \longrightarrow \DPP_{n-1} \times \ASM_{n,1} \times \B_{n,i}.$$
\end{problem}

Assume that we have constructed such bijections. Then we also have a bijection
\begin{multline*}
\DPP_{n-1} \times \B_{n,1} \times \ASM_n = \bigcup_i \left( \DPP_{n-1} \times  \B_{n,1} \times \ASM_{n,i} \right) \\
\longrightarrow \bigcup_i \left(\DPP_{n-1} \times \ASM_{n,1} \times \B_{n,i} \right) = \DPP_{n-1} \times \ASM_{n,1} \times \B_n \longrightarrow \DPP_{n-1} \times \ASM_{n-1} \times \B_n
\end{multline*}
for every $n$. But by induction, that gives a bijection
$$\DPP_{0} \times \dots \times \DPP_{n-1} \times \B_{1,1} \times \cdots \times \B_{n,1} \times \ASM_n \longrightarrow \DPP_{0} \times \dots \times \DPP_{n-1} \times \B_1 \times \cdots \times \B_n,$$
which, since $\DPP_i$ is non-empty (as it contains the empty DPP), proves the ASM theorem
$$|\ASM_n| = \frac{\prod_{i=1}^n |\B_i|}{\prod_{i=1}^n |\B_{i,1}|} = \frac{\prod_{i=1}^n \binom{3i-2}{2i-1}}{\prod_{i=1}^n \binom{2i-2}{i-1}} = \prod_{i=0}^{n-1} \frac{(3i+1)!}{(n+i)!}$$
and also the refined ASM theorem
$$|\ASM_{n,i}| = \frac{|\ASM_{n-1}| \cdot |\B_{n,i}|}{|\B_{n,1}|} = \frac{\binom{n+i-2}{n-1} \binom{2n-i-1}{n-1}}{\binom{3n-2}{2n-1}} \prod_{i=0}^{n-1} \frac{(3i+1)!}{(n+i)!}.$$

\begin{problem}(\cite[Problem 2]{PartII}) \label{prob:asmtodpp}
 Given $n \in \N$, $1 \leq j \leq n$, construct a bijection
 $$\DPP_{n-1} \times \ASM_{n,j} \longrightarrow \ASM_{n-1} \times \DPP_{n,j}.$$
\end{problem}

Once this is proven it follows that
$
|\DPP_{n-1}| \cdot |\ASM_{n,j}| = |\ASM_{n-1}| \cdot |\DPP_{n,j}|.
$
By in\-duc\-tion, we can assume $|\DPP_{n-1}|=|\ASM_{n-1}|$ and so $|\ASM_{n,j}| = |\DPP_{n,j}|$. Summing this over all $j$ implies $|\DPP_{n}|=|\ASM_{n}|$.

For several obvious reasons, we found it essential to check all our constructions with computer code\footnote{The code (in python) is available at \url{https://www.fmf.uni-lj.si/~konvalinka/asmcode.html}.}; for example, the code can possibly be used to identify new equivalent statistics. Another is that it might be possible to find some patterns in the bijection and to simplify the description.

\section{Signed sets and sijections} \label{sec:signed}

It seems that signs and cancellations in the proof are unavoidable. In this section, we briefly introduce the concepts of \emph{signed sets} and \emph{sijections}, signed bijections between signed sets. We present the basic concepts here, and refer the reader to \cite[Section 2]{PartI} for all the details and more examples.

A \emph{signed set} is a pair of disjoint finite sets: $\u S = (S^+,S^-)$ with $S^+ \cap S^- = \emptyset$. Equivalently, a signed set is a finite set $S$ together with a sign function  $\sign \colon S \to \{1,-1\}$, but we will mostly avoid the use of the sign function. Signed sets are usually underlined throughout the extended abstract with the following exception: an ordinary set $S$ always induces a signed set $\u S = (S,\emptyset)$, and in this case we identify $\u S$ with $S$. We summarize related notions.

The \emph{size} of a signed set $\u S$ is $|\u S| = |S^+| - |S^-|$. The \emph{opposite} signed set of $\u S$ is $- \u S = (S^-,S^+)$. The \emph{Cartesian product} of signed sets $\u S$ and $\u T$ is $\u S \times \u T = (S^+ \times T^+ \cup S^- \times T^-,S^+ \times T^- \cup S^- \times T^+)$. The \emph{disjoint union} of signed sets $\u S$ and $\u T$ is $\u S \sqcup \u T = (\u S \times (\{0\},\emptyset)) \cup (\u T \times (\{1\},\emptyset))$. The \emph{disjoint union of a family of signed sets} $\u S_t$ indexed with a signed set $\u T$ is
$$\bigsqcup_{t \in \u T} \u S_t = \bigcup_{t \in \u T} (\u S_t \times \u{\{t\}}).$$
Here $\u{\{t\}}$ is $(\{t\},\emptyset)$ if $t \in T^+$ and $(\emptyset,\{t\})$ if $t \in T^-$.
Most of the usual properties of Cartesian products and disjoint unions of ordinary sets extend to signed sets.

An important type of signed sets are signed intervals: for $a,b \in \Z$, define
$$\si a b = \begin{cases} ([a,b],\emptyset) & \mbox{if } a \leq b \\ (\emptyset,[b+1,a-1]) & \mbox{if } a > b \end{cases}.$$
Here $[a,b]$ stands for the usual interval in $\mathbb{Z}$. The signed sets that are of relevance in this extended abstract are usually constructed from signed intervals using Cartesian products and disjoint unions.

The role of bijections for signed sets is played by ``signed bijections'', which we call \emph{sijections}. A sijection $\varphi$ from $\u S$ to $\u T$,
$$\varphi \colon \u S \Rightarrow \u T,$$
is an involution on the set $(S^+ \cup S^-) \sqcup (T^+ \cup T^-)$ with the property $\varphi(S^+ \sqcup T^-) = S^- \sqcup T^+$. It follows that also $\varphi(S^- \sqcup T^+) = S^+ \sqcup T^-$. A sijection can also be thought of as a collection of a sign-reversing involution on a subset of $\u S$, a sign-reversing involution on a subset of $\u T$, and a {sign-preserving} matching between the remaining elements of $\u S$ with the remaining elements of $\u T$.
The existence of a sijection $\varphi \colon \u S \Rightarrow \u T$ clearly implies $|\u S| = |S^+| - |S^-| = |T^+| - |T^-| = |\u T|$.

In Proposition~2 of \cite{PartI} it is explained how to construct the Cartesian product and the disjoint union of sijections, and also how to compose two sijections using a variant of the Garsia-Milne involution principle. These constructions are fundamental for most of the constructions in this extended abstract. It follows that the existence of a sijection between $\u S$ and $\u T$ is an equivalence relation; it is denoted by ``$\approx$''.

The sijection that is underlying many of our constructions is the following.

\begin{problem}(\cite[Problem 1]{PartI}) \label{prop:alpha}
 Given $a,b,c \in \Z$, construct a sijection
 $$\alpha = \alpha_{a,b,c} \colon \si a c \Longrightarrow \si a b \sqcup \si{b+1}c.$$
\end{problem}

\begin{proof}[Construction]
 For $a \leq b \leq c$ and $c < b < a$, there is nothing to prove. For, say, $a \leq c < b$, we have $\si a b \sqcup \si{b+1}c = (\si a c \sqcup \si{c+1} b) \sqcup \si{b+1}c = \si a c \sqcup (\si{c+1} b \sqcup (-\si {c+1}{b}))$. Since there is a sijection $\si{c+1} b \sqcup (-\si {c+1}{b}) \Rightarrow \u \emptyset$, we get a sijection $\si a b \sqcup \si{b+1}c \Rightarrow \si a c$. The cases $b < a \leq c$, $b \leq c < a$, and $c < a \leq b$ are analogous.
\end{proof}

Using the map $\alpha$, it is not difficult to construct some sijections on \emph{signed boxes}, Cartesian products of signed intervals.

\begin{problem}(\cite[Problem 2]{PartI}) \label{prob:beta}
 Given $\q a =(a_1,\ldots,a_{n-1}) \in \Z^{n-1}$, $\q b=(b_1,\ldots,b_{n-1}) \in \Z^{n-1}$, $x \in \Z$, write $\u S_i = (\{a_i\},\emptyset) \sqcup (\emptyset,\{b_i+1\})$, and construct a sijection
 \begin{multline*}
  \beta = \beta_{\q a,\q b,x} \colon \si{a_1}{b_1} \times \cdots \times \si{a_{n-1}}{b_{n-1}} \\
  \Longrightarrow \bigsqcup_{\q (l_1,\ldots,l_{n-1}) \in \u S_1 \times \cdots \times \u S_{n-1}} \si{l_1}{l_2} \times \si{l_2}{l_3} \times \cdots \times \si{l_{n-2}}{l_{n-1}} \times \si{l_{n-1}} x.
\end{multline*}
\end{problem}

\begin{problem}(\cite[Problem 3]{PartI}) \label{prob:gamma}
 Given $\q k =(k_1,\ldots,k_n) \in \Z^n$ and $x \in \Z$, construct a sijection
 \begin{multline*}
   \gamma = \gamma_{\q k,x} \colon \si{k_1}{k_2} \times \cdots \times \si{k_{n-1}}{k_n} \\
   \Longrightarrow \bigsqcup_{i = 1}^n \si{k_1}{k_2} \times \cdots \times \si{k_{i-1}}{x+n-i} \times \si{x+n-i}{k_{i+1}} \times \cdots \times \si{k_{n-1}}{k_n} \\
   \sqcup \bigsqcup_{i = 1}^{n-2} \cdots \times \si{k_{i-1}}{k_i} \times \si{k_{i+1}+1}{x+n-i-1} \times \si{k_{i+1}}{x+n-i-2} \times \si{k_{i+2}}{k_{i+3}} \times\cdots .
   \end{multline*}
 \end{problem}

An important signed set is the set of all Gelfand--Tsetlin patterns, or GT patterns for short (compare with \cite{Fis05}), with a prescribed bottom row. For $k \in \Z$, define \[
{\GT(k) = (\{\cdot\},\emptyset)},
\]  
 and for $\q k = (k_1,\ldots,k_n) \in \Z^n$, define {recursively}
 $$\GT(\q k) = \GT(k_1,\ldots,k_n) = \bigsqcup_{\q l \in \si{k_1}{k_2} \times \cdots \times \si{k_{n-1}}{k_n}} \GT(l_1,\ldots,l_{n-1}).$$

In particular, $\GT(a,b) \approx \si a b$. Of course, one can think of an element of $\GT(\q k)$ in the usual way, as a triangular array $A=(A_{i,j})_{1 \leq j \leq i \le n}$ of $\binom {n+1}2$ numbers.

The following sijections are crucial for GT patterns. In the constructions, we typically use disjoint unions of previously constructed sijections on signed boxes (e.g.~\cref{prob:beta}).

\begin{problem}\cite[Problem 4]{PartI} \label{prob:rho}
  Given $\q a =(a_1,\ldots,a_{n-1}) \in \Z^{n-1}$, $\q b=(b_1,\ldots,b_{n-1}) \in \Z^{n-1}$, $x \in \Z$, construct a sijection
  $$ \rho = \rho_{\q a,\q b,x} \colon \bigsqcup_{\q l \in \si{a_1}{b_1} \times \cdots \times \si{a_{n-1}}{b_{n-1}}} \GT(\q l) \Rightarrow \bigsqcup_{\q (l_1,\ldots,l_{n-1}) \in \u S_1 \times \cdots \times \u S_{n-1}} \GT(l_1,\ldots,l_{n-1},x),$$
  where $\u S_i = (\{a_i\},\emptyset) \sqcup (\emptyset,\{b_i+1\})$.
\end{problem}

\begin{problem}\cite[Problem 5]{PartI} \label{prob:pi}
  Given $\q k =(k_1,\ldots,k_n) \in \Z^n$ and $i$, $1 \leq i \leq n-1$, construct a sijection
 $$\pi = \pi_{\q k,i} \colon \GT(k_1,\ldots,k_n) \Rightarrow -\GT(k_1,\ldots,k_{i-1},k_{i+1}+1,k_i-1,k_{i+2},\ldots,k_n).$$
 Given $\q a =(a_1,\ldots,a_n) \in \Z^n$,  $\q b =(b_1,\ldots,b_n) \in \Z^n$ such that for some $i$, $1 \leq i \leq n-1$, we have $a_{i+1} = a_i - 1$ and $b_{i+1} = b_i - 1$, construct a sijection
 $$\sigma = \sigma_{\q a,\q b,i} \colon \bigsqcup_{\q l \in \si{a_1}{b_1} \times \cdots \times \si{a_n}{b_n}} \GT(\q l) \Rightarrow \u \emptyset.$$
\end{problem}

The reason we place these two sijections in the same problem is that the proof is by induction, with the induction step for $\pi$ using $\sigma$ and vice versa.

\begin{problem}\cite[Problem 6]{PartI} \label{prob:tau}
 Given $\q k =(k_1,\ldots,k_n) \in \Z^n$ and $x \in \Z$, construct a sijection
 $$\tau = \tau_{\q k,x} \colon \GT(k_1,\ldots,k_n) \Rightarrow \bigsqcup_{i = 1}^n \GT(k_1,\ldots,k_{i-1},x+n-i,k_{i+1},\ldots,k_n).$$
\end{problem}

\section{Monotone triangles and the operator formula}

Monotone triangles with bottom row $1,2,\ldots,n$ are in easy bijective correspondence with $n \times n$ alternating sign matrices. For our purpose we need to have a notion of monotone triangles with arbitrary integer bottom rows. In order to achieve this,
suppose that $\q k = (k_1,\ldots,k_n)$ and $\q l = (l_1,\ldots,l_{n-1})$ are two sequences of integers. We say that $\q l$ \emph{interlaces} $\q k$, $\q l \prec \q k$, if the following holds:
\begin{enumerate}
  \item for every $i$, $1 \leq i \leq n-1$, $l_i$ is in the closed interval between $k_i$ and $k_{i+1}$;
  \item if $k_{i-1} \leq k_i \leq k_{i+1}$ for some $i$, $2 \leq i \leq n-1$, then $l_{i-1}$ and $l_i$ cannot both be $k_i$;
  \item if $k_i > l_i = k_{i+1}$, then $i \leq n-2$ and $l_{i+1} = l_i = k_{i+1}$;
  \item if $k_i = l_i > k_{i+1}$, then $i \geq 2$ and $l_{i-1} = l_i = k_i$.
\end{enumerate}
A \emph{monotone triangle of size $n$} is a map $T \colon \{(i,j) \colon 1 \leq j \leq i \leq n \} \to \Z$ so that line $i-1$ (i.e.~the sequence $T_{i-1,1},\ldots,T_{i-1,i-1}$) interlaces line $i$ (i.e.~the sequence $T_{i,1},\ldots,T_{i,i}$). The \emph{sign} of a monotone triangle $T$ is $(-1)^r$, where $r$ is the sum of:
\begin{itemize}
  \item the number of strict descents in the rows of $T$, i.e.~the number of pairs $(i,j)$ so that $1 \leq j < i \leq n$ and $T_{i,j} > T_{i,j+1}$, and
  \item the number of $(i,j)$ so that $1 \leq j \leq i - 2$, $i \leq n$ and $T_{i,j} > T_{i-1,j} = T_{i,j+1} = T_{i-1,j+1} > T_{i,j+2}$.
\end{itemize}

It turns out that $\MT(\q k)$ satisfies a recursive ``identity''. Let us define the signed set of \emph{arrow rows of order $n$} as $\AR_n = (\{\nearrow,\nwarrow\},\{\nenwarrow\})^{n}$.
%Alternatively, we can think of them as rows of length $n$ with elements $\nwarrow, \nearrow, \nenwarrow$, where the positive elements are precisely those with an even number of $\nenwarrow$'s.
The role of an arrow row $\mu$ of order $n$ is that it induces a deformation of $\si{k_1}{k_2} \times \si{k_2}{k_3} \times \cdots \times \si{k_{n-1}}{k_n}$ as follows. Consider
$$
\begin{array}{ccccccccccc}
 & \si{k_1}{k_2} &   & \si{k_2}{k_3} &  &  \ldots &  & \si{k_{n-2}}{k_n-1} &  & \si{k_{n-1}}{k_n} & \\
 \mu_1 & & \mu_2  & & \mu_3 &  &  \ldots &   & \mu_{n-1} & & \mu_{n} ,
 \end{array}
 $$
 and if $\mu_i \in \{\nwarrow, \nenwarrow\}$ (that is we have an arrow pointing towards $\si{k_{i-1}}{k_i}$) then
 $k_i$ is decreased by $1$ in $\si{k_{i-1}}{k_i}$, while there is no change for this $k_i$ if $\mu_i=\nearrow$. If $\mu_i \in \{\nearrow, \nenwarrow\}$ then $k_i$ is increased by $1$ in $\si{k_i}{k_{i+1}}$, while there is no change for this $k_i$ if $\mu_i=\nwarrow$. For a more formal description, we let $\delta_{\nwarrow}(\nwarrow) = \delta_{\nwarrow}(\nenwarrow) = \delta_{\nearrow}(\nearrow) = \delta_{\nearrow}(\nenwarrow) = 1$ and $\delta_{\nwarrow}(\nearrow) = \delta_{\nearrow}(\nwarrow) = 0$, and we define
 \[
 e(\q k,\mu)  = \si{k_1+\delta_{\nearrow}(\mu_1)}{k_2-\delta_{\nwarrow}(\mu_2)} \times \ldots \times \si{k_{n-1}+\delta_{\nearrow}(\mu_{n-1})}{k_n-\delta_{\nwarrow}(\mu_n)}
 \]
 for $\q k = (k_1,\ldots,k_n)$ and $\mu \in \AR_n$. The following is not difficult.

\begin{problem}\cite[Problem 7]{PartI} \label{prob:Xi}
  Given $\q k = (k_1,\ldots,k_n)$, construct a sijection
  $$\Xi = \Xi_{\q k} \colon \MT(\q k) \Rightarrow \bigsqcup_{\mu \in \AR_n} \bigsqcup_{\q l \in e(\q k,\mu)} \MT(\q l).$$
\end{problem}

Our next goal is to define other objects that satisfy the same ``recursion'' as monotone triangles.
To this end, define the signed set of \emph{arrow patterns of order $n$} as 
\[\AP_n = (\{\swarrow, \searrow\},\{\seswarrow\})^{\binom n 2}.\] 
Alternatively, we can think of an arrow pattern of order $n$ as a triangular array $T=(t_{p,q})_{1 \le p < q \le n}$ arranged as
$$T = \begin{smallmatrix} & & & & t_{1,n} & & & & \\ & & & t_{1,n-1} & & t_{2,n} & & & \\ & & t_{1,n-2} & & t_{2,n-1}& & t_{3,n} & & \\ & \vstretch{0.35}{\udots} & \vstretch{0.35}{\vdots} & \vstretch{0.35}{\ddots} & \vstretch{0.35}{\vdots} & \vstretch{0.35}{\udots} & \vstretch{0.35}{\vdots} & \vstretch{0.35}{\ddots} & \\ t_{1,2} & & t_{2,3}  & & \ldots  & & \ldots  & & t_{n-1,n}  \end{smallmatrix},$$
with $t_{p,q} \in \{\swarrow, \searrow, \seswarrow\}$, and the sign of an arrow pattern is $1$ if the number of $\seswarrow$'s is even and $-1$ otherwise.

The role of an arrow pattern of order $n$ is that it induces a deformation of $(k_1,\ldots,k_n)$, which can be thought of as follows. Add $k_1,\ldots,k_n$ as bottom row of $T$ (i.e., $t_{i,i}=k_i$), and for each $\swarrow$ or$ \seswarrow$ which is in the same $\swarrow$-diagonal as $k_i$ add $1$ to $k_i$, while for each $\searrow$ or $\seswarrow$ which is in the same $\searrow$-diagonal as $k_i$ subtract $1$ from $k_i$.
More formally, letting $\delta_{\swarrow}(\swarrow) = \delta_{\swarrow}(\seswarrow) = \delta_{\searrow}(\searrow) = \delta_{\searrow}(\seswarrow) = 1$ and $\delta_{\swarrow}(\searrow) = \delta_{\searrow}(\swarrow) = 0$, we set
$$c_i(T) = \sum_{j=i+1}^{n} \delta_{\swarrow}(t_{i,j}) - \sum_{j=1}^{i-1} \delta_{\searrow}(t_{j,i}) \mbox{ and } d(\q k,T) = (k_1+c_1(T),k_2+c_2(T),\ldots,k_n+c_n(T))$$
for $\q k = (k_1,\ldots,k_n)$ and $T \in \AP_n$.


For $\q k =(k_1,\ldots,k_n)$ define \emph{shifted Gelfand--Tsetlin patterns}, or SGT patterns for short, as the following disjoint union of GT patterns over arrow patterns of order $n$:
$$
\SGT(\q k) = \bigsqcup_{T \in \AP_n} \GT(d(\q k,T))
$$
The difficult part of \cite{PartI} is to prove that $\SGT$ indeed satisfies the same ``recursion'' as $\MT$. While the proof of the recursion was easy for monotone triangles, it is very involved for shifted GT patterns, and needs almost {all} the sijections we have mentioned so far.

\begin{problem} \cite[Problem 9]{PartI}
Given $\q k = (k_1,\ldots,k_n) \in \Z^n$ and $x \in \Z$, construct a sijection
$$\Phi = \Phi_{\q k,x} \colon \bigsqcup_{\mu \in \AR_n} \bigsqcup_{\q l \in e(\q k,\mu)} \SGT(\q l) \Rightarrow \SGT(\q k).$$
\end{problem}

From the last problem, it is easy to construct a bijective proof of the operator formula for monotone triangles. See \cite[pp.~3--4]{PartI} for a discussion of this formula.

\begin{problem} \cite[Problem 10]{PartI}
 Given $\q k = (k_1,\ldots,k_n) \in \Z^n$ and $x \in \Z$, construct a sijection
 $$\Gamma = \Gamma_{\q k,x} \colon \MT(\q k) \Rightarrow \SGT(\q k).$$
\end{problem}
\begin{proof}[Construction]
 The proof is by induction on $n$. For $n = 1$, both sides consist of one (positive) element, and the sijection is obvious. Once we have constructed $\Gamma$ for all lists of length less than $n$, we can construct $\Gamma_{\q k,x}$ as the composition of sijections
 $$\MT(\q k) \stackrel{\Xi_{\q k}}{\Longrightarrow} \bigsqcup_{\mu \in \AR_n} \bigsqcup_{\q l \in e(\q k,\mu)} \MT(\q l) \stackrel{\sqcup \sqcup \Gamma}{\Longrightarrow} \bigsqcup_{\mu \in \AR_n} \bigsqcup_{\q l \in e(\q k,\mu)} \SGT(\q l) \stackrel{\Phi_{\q k,x}}{\Longrightarrow} \SGT(\q k),$$
 where $\sqcup \sqcup \Gamma$ means $\bigsqcup_{\mu \in \AR_n} \bigsqcup_{\q l \in e(\q k,\mu)} \Gamma_{\q l,x}.$
\end{proof}

\section{Sketch of the main bijections}

Equipped with the operator formula, one can construct the following crucial sijection.

\begin{problem}(\cite[Problem 16]{PartII}) \label{prob:rot}
  Given $\q k = (k_1,\ldots,k_n)$, construct a sijection
  $$\MT(\q k) \Longrightarrow (-1)^{n-1} \MT(\rot(\q k)),$$
  where $\rot(\q k) = (k_2,\ldots,k_n,k_1-n)$.
\end{problem}

Note that the construction is far from easy, even assuming that we have the map $\Gamma$. See \cite[Section 6]{PartII} for a proof. On the other hand, the following is relatively simple.

Suppose that we are given a weakly increasing sequence $\q k = (k_1,\ldots,k_n)$ and $i \in \N$. We define
$$\MT_i(\q k) = \{ T \in \MT(\q k) \colon T_{n-i+1,1} = \ldots = T_{n,1} = k_1, T_{n-i,1} \neq k_1\}$$
as the signed subset of monotone triangles with $k_1$ in the first position in exactly the last $i$ rows. Similarly, we define
$$\MT^i(\q k) = \{ T \in \MT(\q k) \colon T_{n-i+1,n-i+1} = \ldots = T_{n,n} = k_n, T_{n-i,n-i} \neq k_n\}$$
as the signed subset of monotone triangles with $k_n$ in the last position in exactly the last $i$ rows.


\begin{problem}(\cite[Problem 21]{PartII}) \label{prob:mti}
 Given a weakly increasing $\q k = (k_1,\ldots,k_n)$ and $i \geq 1$, construct sijections
 $$\MT_i(\q k) \Longrightarrow \bigsqcup_{j = 0}^{i-1} (-1)^j \binom{[i-1]}j \times \MT(k_1+j+1,k_2,\ldots,k_n)$$
 and
 $$\MT^i(\q k) \Longrightarrow \bigsqcup_{j = 0}^{i-1} (-1)^j \binom{[i-1]}j \times \MT(k_1,k_2,\ldots,k_n-j-1).$$
\end{problem}

Based on the last two constructions, it is quite straightforward to do the following.

\begin{problem}(\cite[Problem 22]{PartII})  \label{prob:Aisijection}
  Given $n \in \N$ and $i \in [n]$, construct a sijection
  $$\bigsqcup_{j=1}^n (-1)^{j+1} \binom{[2n-i-1]}{n-i-j+1} \times \ASM_{n,j} \Longrightarrow \ASM_{n,i}. $$
\end{problem}


To complete the construction of the bijections for \cref{prob:main,prob:asmtodpp}, we need, among other results, a few more ingredients from ``bijective linear algebra''. Denote by $\u{\mathfrak S}_m$ the signed set of permutations (with the usual sign). Given signed sets $\u P_{i,j}$, $1 \leq i,j \leq m$, define the \emph{determinant} of $\u{\p P} = [\u P_{ij}]_{i,j = 1}^m$ as the signed set
$$\det(\u{\p P}) = \bigsqcup_{\pi \in \u{\mathfrak S}_m} \u P_{1,\pi(1)} \times \cdots \times \u P_{m,\pi(m)}.$$

Among other classical properties, we have the following version of Cramer's rule.

\begin{problem}(\cite[Problem 9]{PartII}) \label{prob:cramer}
 Given $\u{\p P} = [\u P_{p,q}]_{p,q = 1}^m$, signed sets $\u X_i, \u Y_i$  and sijections $\bigsqcup_{q=1}^m \u P_{i,q} \times \u X_q \Rightarrow \u Y_i$ for all $i \in [m]$, construct sijections
 $$ \det(\u{\p P}) \times \u X_j \Longrightarrow \det(\u{\p P}^j),$$
 where $\u{\p P}^j = [\u P^j_{p,q}]_{p,q = 1}^m$, $\u P^j_{p,q} = \u P_{p,q}$ if $q \neq j$, $\u P^j_{p,j} = \u Y_p$, for all $j \in [m]$.
\end{problem}

Essentially, sijections like the one in \cref{prob:cramer} tell us that ``linear equalities'' for sijections like the one in \cref{prob:Aisijection} can be used to find bijections on the sets involved. See the constructions for \cref{prob:main,prob:asmtodpp} in \cite[Section 7]{PartII} for all details.

\section{Summary}

In this extended abstract, we present the first bijective proof of the enumeration formula for alternating sign matrices. The bijection is by no means simple; the papers \cite{PartI, PartII} combined have about 40 pages, with the technical constructions taking about 20 pages. We also needed more than 2000 lines to produce a working python code. However, note that the first proof of the ASM theorem by Zeilberger was 84 pages long.
We certainly hope that our proof will be simplified and shortened in the future.

%% 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}
