%% 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]{FPSAC2023}
\articlenumber{91}
%% 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}{Lemma}
\newtheorem{conjecture}{Conjecture}

\usepackage{todonotes}
\newcommand{\Stephan}[1]{\todo[size=\tiny,inline,color=orange!30]{#1 \\ \hfill --- Stephan}}
\newcommand{\alex}[1]{\todo[size=\tiny,inline,color=cyan!30]{#1 \\ \hfill --- Alex}}
%\newcommand{\alex}[1]{\footnote{{\color{red}{Kommentar von Alex:}} #1}}

\usepackage[all,cmtip]{xy}

\usepackage{xspace}
\newcommand{\Dfn}[1]{\emph{\color{blue}#1}} % to highlight and collect definitions
\newcommand{\GL}{\mathrm{GL}}

\newcommand{\ttFindStat}{{\tt FindStat}\xspace}%
\newcommand{\ttSageMath}{{\tt SageMath}\xspace}%
\newcommand{\ttOEIS}{{\tt OEIS}\xspace}%
\newcommand{\ttmathoverflow}{{\tt mathoverflow}\xspace}%
\newcommand{\FindStat}[1]{%
  \ifx&#1&%
  \url{www.findstat.org}% #1 is empty
  \else \url{www.findstat.org/#1}% #1 is nonempty
  \fi}%
\newcommand{\mathoverflow}[1]{%
  \ifx&#1&%
  \url{www.mathoverflow.net}% #1 is empty
  \else \url{www.mathoverflow.net/q/#1}% #1 is nonempty
  \fi}%

\newcommand{\OEIS}[1]{\url{www.oeis.org/#1}}
\newlength{\Stwidth}
\settowidth{\Stwidth}{\tt{St000000:}}
\newcommand{\stat}[3]%
{{\tt \makebox[\Stwidth][r]{#1:} #2 $\to\ZZ$}\\{\small #3}}
\newcommand{\map}[4]%
{{\tt \makebox[\Stwidth][r]{#1:} #2 $\xrightarrow{\text{#3}}$ #4}}

\newcommand{\newmap}[5]%
{\tt{#1}: & \tt{#2} & $\xrightarrow{\makebox[#5]{\tt{\scriptsize #3}}}$ & \tt{#4}}

\newcommand{\opgreek}[1]{\begingroup\mathgroup-1 #1\endgroup}
\DeclareMathOperator{\Mp}{\opgreek{\phi}}% I think we should use Mp here
\DeclareMathOperator{\St}{\opgreek{\beta}}% I think we should use St here

\DeclareMathOperator{\rot}{rot}%
\DeclareMathOperator{\maj}{maj}%
\DeclareMathOperator{\inv}{inv}%
\newcommand{\NN}{\mathbb N}
\newcommand{\ZZ}{\mathbb Z}
\newcommand{\QQ}{\mathbb Q}

%% define your title in the usual way
\title{A bijectionist's toolkit}


\author{Alexander Grosz\thanks{\href{mailto:alexander.grosz@tum.de}{alexander.grosz@tum.de}. Alexander Grosz was supported by the Austrian Science Fund (FWF) P29275 and the Alexander von Humboldt Foundation with funds from the German Federal Ministry of Education and Research (BMBF).}\addressmark{1},
Tobias Kietreiber\thanks{\href{mailto:tobias.kietreiber@tuwien.ac.at}{tobias.kietreiber@tuwien.ac.at}. Tobias Kietreiber was supported by the Austrian Science Fund (FWF) P29275.}\addressmark{2},\\
Stephan Pfannerer\thanks{\href{mailto:stephan.pfannerer@tuwien.ac.at}{stephan.pfannerer@tuwien.ac.at}. Stephan Pfannerer was supported by the Austrian Science Fund (FWF) P29275 and is a recipient of a DOC Fellowship of the Austrian Academy of Sciences.}\addressmark{2}, \and
Martin Rubey\thanks{\href{mailto:martin.rubey@tuwien.ac.at}{martin.rubey@tuwien.ac.at}. Martin Rubey was supported by the Austrian Science Fund (FWF) P29275.}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Technical University of Munich, Germany
\\ \addressmark{2}Institute of Discrete Mathematics and Geometry,
Technische Universität Wien, Austria}

%% put the date of submission here
\received{March 15, 2023}

%% 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 present a tool, integrated into \ttSageMath 10.0, which
  supports the combinatorialist in the discovery of an explicit
  bijection between two finite sets given various constraints, or by
  demonstrating that no such bijection can exist.  As an application
  we present a conjecture which may have been hard to discover otherwise.}

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

%% 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; i.e., [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{main.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}

Let $\mathcal A=(A_i)_{i\in I}$ and $\mathcal B=(B_i)_{i\in I}$ be
two sequences of finite sets of the same size.  One commonly employed
approach for finding an explicit bijection between the two sets is to
refine the problem by introducing new parameters or by stipulating
that the bijection has other additional properties.  For example, one
may want to require that it intertwines
natural actions or operations on $\mathcal A$ and $\mathcal B$
respectively or, provided $\mathcal A = \mathcal B$, that it is an involution.
Also, one may want to find a parameter on $\mathcal A$ which
has the same distribution as a natural parameter on $\mathcal B$ but satisfies
additional constraints.

Thus, the first task is to discover such properties, and then determine
experimentally whether the requirements can be met at all.
To the
best of the authors' knowledge, this is usually done by ad-hoc
methods.  For example, one might list the first few objects in
$\mathcal A$ and $\mathcal B$ with pencil and paper or perhaps using
a computer program and then inspect them manually.

While it is straightforward to check whether there are natural
subsets of $A_i$ and $B_i$ that are still in bijection, other
constraints may be very hard to verify or falsify.  Moreover,
databases like the \ttOEIS~\cite{oeis} and \ttFindStat~\cite{FindStat} now enable us, in principle,
to generate a huge number of conjectural refinements, but it is infeasible to
look into them by hand.  The program we describe here seeks to
simplify and automate this task.

The \lq bijectionist's toolkit\rq\ is included in \ttSageMath~\cite{sagemath} beginning with version 10.0.\footnote{The full documentation is available at \url{https://doc.sagemath.org/html/en/reference/combinat/sage/combinat/bijectionist.html}}

\section{Motivation}

Before we present the features of the program in detail, let us
describe the problem that originally motivated the development of
the tool.  Let $A=B=\mathfrak S_n$
and let
$\rot:\mathfrak S_n\to\mathfrak S_n$ the \lq rotation\rq-action on
$A$, that is, conjugation with the long cycle $(1,\dots,n)$.  Explicitly:
\[
  \rot(\pi)(i) =
  \begin{cases}
    \pi(i+1)-1&\text{if $\pi(i+1)\neq 1$},\\
    n&\text{otherwise,}
  \end{cases}
\]%\alex{Kommata?} Martin: passt
where we set $\pi(n+1) = \pi(1)$.  Additionally, let
$\tau: B\to\NN$ be the length of a longest increasing
subsequence in a permutation, that is, the largest number $k$ such
that $\pi(i_1) < \dots < \pi(i_k)$ for some sequence
$1 \leq i_1 < \dots < i_k \leq n$.

Then, driven by a problem from invariant theory, we want to find a
statistic on permutations, that is, a function $s: A\to\NN$,
which has the same distribution as $\tau$ but is additionally
invariant under $\rot$:
\begin{align*}
  \sum_{\pi\in\mathfrak S_n} q^{s(\pi)} &= \sum_{\pi\in\mathfrak S_n} q^{\tau(\pi)},\text{ and}\\
  s(\rot(\pi)) &= s(\pi)\quad\text{for all $\pi\in\mathfrak S_n$}.
\end{align*}

Given these constraints the program is then able to produce a
complete list of minimal subdistributions, that is, non-empty inclusion-wise minimal subsets
$\tilde A$ of $A$ together with subsets
$\tilde Z\subset \NN$ of the same cardinality, such that
necessarily
\[
  \sum_{\pi\in\tilde A} q^{s(\pi)} = \sum_{z\in\tilde Z} q^z.
\]
To illustrate, the program finds that the set of four permutations
\[
  [1, 2, 3, 4], [2, 3, 4, 1], [3, 4, 1, 2]\text{ and } [4, 1, 2, 3]
\]
must be mapped by $s$ to the four values $1, 2, 3$ and $4$, in some
order.  A part of this is easy to explain: these are exactly the four
permutations which are invariant under rotation, so all other orbits
of $\rot$ have cardinality at least $2$.  However, there is only a
single permutation with length of longest increasing subsequence
equal to $1$ and a single permutation with the length of a longest
increasing subsequence equal to $4$.  Thus, these two values can only
be images of permutations which are invariant under rotation.

Somewhat to our disappointment, even with the help of our tool we
were unable to find an explicit description of the statistic $s$.
Still, possibly encouraged by the fact that the program demonstrated
that the statistic exists for $n\leq 9$, the existence eventually
could be proven~\cite{MR4264212}.

Note that the existence of such a statistic is equivalent to the existence of a bijection $S:\mathfrak S_n\to \mathfrak S_n$ such that $(\tau\circ S)(\rot \pi) = (\tau\circ S)(\pi)$.

\section{Features}

Let us now describe the main features of the tool in full generality.
All types of constraints can be combined.
\subsection*{Basic setup}
Let $A$ and $B$ be finite sets of equal size, and let $\tau: B\to Z$
for an arbitrary set $Z$.  Then
\begin{verbatim}
sage: bij = Bijectionist(A, B, tau)
\end{verbatim}
initializes \verb|bij| to represent all functions $s: A\to Z$ such
that there is a bijection $S: A\to B$, such that the following
diagram commutes:

\[
    \xymatrix{
        A \ar[d]_S \ar[rd]^s \\
        B \ar[r]_\tau & Z
    }
\]

As a special case we allow $\tau$ to be the identity map on $B$.  In
this case \verb|bij| represents all bijections $S: A\to B$, and we must have $Z = B$ and $S = s$. %\alex{Nicht eher $s = S$?} Martin: nein, scheint mir consistent.

\subsection*{Constraints}
\subsubsection*{Statistics}
We may supply a pair (or several pairs) of statistics
$\alpha: A\to W$ and $\beta: B\to W$ on $A$ and $B$ respectively into
an arbitrary set $W$:
\begin{verbatim}
sage: bij.set_statistics((alpha, beta))
\end{verbatim}
Doing so, we stipulate that the following diagram commutes:
\[
    \xymatrix{
        A \ar[d]_S \ar[rd]^\alpha \\
        B \ar[r]_\beta & W
    }
\]
In words, we require that $S$ is an intertwining bijection between
the statistics $\alpha$ and $\beta$.

\subsubsection*{Intertwining relations}
We may supply a pair (or several pairs) of $k$-ary maps
$\pi: A^k\to A$ and $\rho: Z^k\to Z$, thus requiring that they are
intertwined by $s$:
\begin{verbatim}
sage: bij.set_intertwining_relations((k, pi, rho))
\end{verbatim}
Put differently, the following diagram must then commute:

\[
    \xymatrix{
        A^k \ar[d]_{s^k} \ar[r]^\pi & A \ar[d]^s \\
        Z^k \ar[r]_\rho & Z
    }
\]

One may want to think of $\pi$ as a map which composes objects in
$A$, and $\rho$ as the effect this should have on the statistic we
are looking for.

\subsubsection*{Quadratic relations}
We may supply a pair (or several pairs) of maps $\phi: A\to Z$ and
$\psi: Z\to A$,
\begin{verbatim}
sage: bij.set_quadratic_relations((phi, psi))
\end{verbatim}
thus requiring that the following diagram commutes:

\[
    \xymatrix{
        A \ar[d]_\phi \ar[r]^s & Z \ar[d]^\psi \\
        Z  & A \ar[l]^s
    }
\]

In particular, if $\phi$ and $\psi$ are the identity maps (and
therefore $Z = A = B$ and $S = s$), this requires that $S$ is an
involution on $A$.

\subsubsection*{Constant blocks}
For a set partition $P$ of $A$, setting
\begin{verbatim}
sage: bij.set_constant_blocks(P)
\end{verbatim}
we stipulate that $s:A\to Z$ is constant on the blocks of $P$.  Note
that this makes sense only if $\tau$ is not injective.  To
illustrate, this accommodates the condition of the motivating example
that the statistic should be invariant under $\rot$, by letting $P$
be the corresponding orbit decomposition.

\subsubsection*{Homomesy constraints}
For a set partition $Q$ of $A$, setting
\begin{verbatim}
sage: bij.set_homomesic(Q)
\end{verbatim}
we assert that the average of $s$ on each block of $Q$ should be
constant.  Of course, this requires that $Z$ is a field.

\subsection*{Solutions}
The three most important ways to explore the solution space are as
follows.

\subsubsection*{Fibers of the statistics}
The instruction
\begin{verbatim}
sage: bij.statistics_fibers()
\end{verbatim}
simply returns the preimages of $\alpha:A\to W$ and $\beta:B\to W$.
Note that it does not assert that a statistic $s$ exists.

\subsubsection*{All solutions}
Issuing
\begin{verbatim}
sage: list(bij.solutions_iterator())
\end{verbatim}
the program lists all functions $s:A\to Z$ which satisfy all the
given constraints, or raises an error if no such map exists.  Frequently, however, the number of such functions will be very large.  Thus, and in particular if one is only interested in checking whether the constraints can be satisfied at all, it is more useful to use \verb|next(bij.solutions_iterator())|, which only outputs a single solution, if it exists.  In any case, this is computationally expensive.

\subsubsection*{Minimal subdistributions}
\begin{verbatim}
sage: list(bij.minimal_subdistributions_iterator())
\end{verbatim}
lists all minimal subdistribution implied by the given
constraints, or raises an error if no
solution exists.  More precisely, it returns all non-empty inclusion-wise minimal subsets $\tilde A$ of $A$ of
together with submultisets $\tilde Z\subset Z$
of the same cardinality, such that we have $s(\tilde A) = \tilde Z$ as multisets for all possible solutions.  In particular, if $\tau$ is
the identity map on $B$, then we obtain a pair of subsets of minimal
cardinality of $A$ and $B$ respectively which are in bijection for all
maps $s$ satisfying the given constraints.  This is computationally
expensive.

\section{A sample application}

A treasure trove for the experimental combinatorialist is the
database \ttFindStat.  It should not come as a surprise that
combining the toolkit with \ttFindStat yields some potentially
interesting conjectures.

Recently, Elder, Lafrenière, McNicholas, Striker and Welch
\cite{arXiv220613409} used the database to find homomesies on
permutations, that is, statistics $s:\mathfrak S_n\to\ZZ$ and
bijections $m:\mathfrak S_n\to\mathfrak S_n$ such that there exists a
constant $c\in\QQ$ with
\[
  \frac{1}{|\mathcal O|}\sum_{\pi\in\mathcal O} s(\pi) = c
\]
for all orbits $\mathcal O$ of $m$.  Using a brute force search, they
discovered more than a hundred combinations of maps and conjecturally
homomesic statistics.  Remarkably, they were then able to prove that
all of these conjectures are actually true.

Using our toolkit, we can take this a step further and look for
statistics $\tau$ which are \emph{equidistributed} to a homomesic
statistic, given a map $m$:
\begin{verbatim}
sage: n = 5
sage: A = B = Permutations(n)
sage: Q = DiscreteDynamicalSystem(A, m).cycles()
sage: bij = Bijectionist(A, B, tau)
sage: bij.set_homomesic(Q)
sage: next(bij.solutions_iterator())
\end{verbatim}
If this yields a solution, we can be quite confident that $s$ exists.
For example, if $m$ is the rotation action $\rot$ considered before,
iterating through the statistics in \ttFindStat yields
\FindStat{St001377}, \lq The major index minus the number of
inversions of a permutation\rq\, as a candidate.

As a next step, we can use \ttFindStat again to refine our
conjecture, by iterating over all pairs of equidistributed statistics
$\alpha$ and $\beta$, such that
\begin{verbatim}
sage: bij.set_statistics((alpha, beta))
sage: next(bij.solutions_iterator())
\end{verbatim}
still gives a solution.  In the case at hand, there are very many
such pairs.  One particularly natural refinement is to use the major
index for both $\alpha$ and $\beta$.  We now look at the minimal
subdistributions in the refined setting, for $n=4$:
\begin{verbatim}
sage: list(bij.minimal_subdistributions_iterator())
 [([[4, 3, 2, 1]], [0]),
  ([[4, 1, 2, 3]], [0]),
  ([[3, 4, 1, 2]], [0]),
  ([[2, 3, 4, 1]], [0]),
  ([[2, 1, 4, 3]], [0]),
  ([[1, 2, 3, 4]], [0]),
  ([[2, 1, 3, 4], [3, 1, 2, 4]], [-2, -1]),
 ...
\end{verbatim}
We can, in fact, query \ttFindStat again with this data:
\begin{verbatim}
sage: findstat(list(bij.minimal_subdistributions_iterator()))
 0: St001377oMp00064oMp00073 (quality [100, 100])
 ...
\end{verbatim}
Although this is a plausible result, it turns out that this statistic
is not homomesic with respect to rotation.  However, we can make the
following conjecture, which we tested up to and including $n=6$.

\begin{conjecture}
  Let $\maj:\mathfrak S_n\to\NN$ be the major index and let
  $\inv:\mathfrak S_n\to\NN$ be the number of inversions of a
  permutation.  Furthermore, let $\rot:\mathfrak S_n\to\mathfrak S_n$
  be the conjugation of a permutation with the long cycle
  $(1,\dots,n)$.

  There is a statistic $s:\mathfrak S_n\to\ZZ$ which is homomesic
  with respect to $\rot$, and such that the pairs of statistics
  $(s, \maj)$ and $(\maj-\inv, \maj)$ are equidistributed, that is,
  \begin{align*}
    \sum_{pi\in\mathfrak S_n} q^{s(\pi)} t^{\maj(\pi)} =
    \sum_{pi\in\mathfrak S_n} q^{\maj(\pi)-\inv(\pi)} t^{\maj(\pi)}.
  \end{align*}    
\end{conjecture}

\section{Implementation details}

In this section, we outline the basic ideas behind the implementation.
We model the problem as a $0$-$1$ integer linear program that represents the statistic $s$.
Given a (possibly trivial) set partition $P$ of $A$ and given $Z$, we define binary variables $x_{p, z}$ for each $p\in P$ and $z\in Z$.  The assignment $x_{p, z} = 1$ then indicates that $\forall a\in p: s(a) = z$, thereby encoding that $s$ is constant on the blocks of $P$.

To ensure that $s$ and $\tau$ have the same distribution, and that the bijection $S:A\to B$ realising this equidistribution respects the statistics $\alpha: A\to W$ and $\beta: B \to W$ we add the following constraints:
\begin{align*}
    \sum_{p\in P} m_w(p) x_{p, z} &= n_w(z),&\forall w\in W\;\forall z\in Z\\
    \sum_{z\in Z} x_{p, z} &= 1, &\forall p\in P
\end{align*}
where $m_w(p) = \left|\{a\in p: \alpha(a)=w\}\right| $ and $n_w(z) = \left| \{ b\in B: \beta(b)=w \text{ and }\tau(b)=z\}\right|$.

A solution to this integer program immediately yields a solution for $s: A\to Z$.
To generate all possible solutions for $s$, we iteratively prohibit the current solution by adding the linear constraint $\sum_{p\in P} x_{p, s(p)} < |P|$, where $s(p)$ denotes the common image of all $a\in p$.

The minimal subdistributions can be algorithmically determined by means of a dynamic optimization problem that interacts with the model above. In every iteration, we guess a smallest subset of blocks $p$ that potentially defines a minimal subdistribution. By an auxiliary integer program we find a minimal selection of blocks with compatible distributions according to all the solutions of the base problem we have encountered so far. We then attempt to confirm the conjecture that the incumbent subdistribution holds for any solution by testing the feasibility of the base problem after prohibiting the specific guess at hand. In case of infeasibility, we terminate with the given guess; otherwise we add the information of the new solution to create a new guess for a minimal selection of blocks.
Analogously, we can determine an improved partition $P'$ of $A$ that is implicitly forced by other restrictions of the statistic.

\acknowledgements{We want to thank Matthias Köppe and Travis
  Scrimshaw for reviewing the code and thus allowing integration into
  the upcoming version 10.0 of \ttSageMath.

%% 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}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
