%%% Version 6, mostly final submission to FPSAC on 1 April 2014.
%%% Some changes are yet to be done.
%%% This is ipbrFPSAC*.tex, a submission to FPSAC 2014 in Chicago.
%%% It turns out that the journals class file (dmtcs.cls) wants to
%%% define \qed and a proof environment, which then stops LaTeX cold
%%% with a complaint that proof is already undefined.  The way to fix
%%% this so that DMTCS gets it the way it wants (only difference I see
%%% is whether ``Proof:'' is italicized (amsthm) or boldface (dmtcs).
%%% Anyway, it's a relief that there is a way to fix this without
%%% causing trouble to the organizers--one can ``undefine'' a macro, and
%%% even an ``environment'', which is essentially two macros. 
\RequirePackage{amsthm}
\let\qed\undefined
\expandafter\let\csname proof\endcsname\relax
\expandafter\let\csname endproof\endcsname\relax
\documentclass[submission%
% if you want to use pdftex and pdflatex doesn't do well for you,
% uncomment the following line
%,pdftex%
% if you have difficulties with hyperref uncomment the following line
%,nohyperref%
% if you have difficulties with fonts uncomment the following line
%,notimes%
]{dmtcs}

% DON'T LOAD ANY STYLES THAT CHANGE THE PAGE LAYOUT
% AND DON'T CHANGE THE PAGE LAYOUT BY HAND, EITHER.

%%%Added by TR to work with FPSAC
%%% the package ``amsthm'' conflicts with some DMTCS ``\proof'' command
%%% So I commented out the proof definitions in the latter, since
%%% otherwise it's an incredible pain to deal with the regular LaTeX
%%% versions of \newtheorem...


\usepackage{amsmath,amssymb,url}
\usepackage{color}
\usepackage{xcolor}

%%% Darij's packages
\usepackage[all,cmtip,color]{xy}
%\usepackage{lscape}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{framed}
\usepackage{amsmath}
\usepackage{comment}
\usepackage{hyperref}
%\usepackage{amsthm}%



%%\usepackage{pstcol,pst-node}

%%% Theorems\dots
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{remark}[theorem]{Remark}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}


%%%%% Old Theorems from TR
%\newtheorem{thm}{Theorem}
%\newtheorem{prop}[thm]{Proposition}
%\newtheorem{conj}[thm]{Conjecture}
%\newtheorem{cor}[thm]{Corollary}
%\newtheorem{defn}[thm]{Definition}
%\theoremstyle{definition}
%\newtheorem{eg}{Example}

\usepackage[latin1]{inputenc}
\usepackage{subfigure}

\def\id{\operatorname*{id}}

% graphicx is now loaded automatically no need to put this in here anymore.
%
%\usepackage{graphicx}

% just comment this out if you don't have natbib, or if you don't want
% to use it
%\usepackage[round]{natbib}

\author[D. Grinberg and T. Roby]{Darij Grinberg\addressmark{1}\thanks{Partially supported by
    NSF Grant \#1001905}\and Tom Roby\addressmark{2}\thanks{Partially supported by
    NSF Grant \#1001905} \\
    \textbf{Non-final version}}

% We recommend that you don't put "extended abstract" in the title
\title[The order of birational rowmotion]{The order of birational rowmotion
}
%%% REMOVE VERSION NUMBER AT END

\address{\addressmark{1}Massachusetts Institute of Technology
  Cambridge, MA 02139, USA
\addressmark{2}University of Connecticut
  Storrs, CT 06269, USA}
\keywords{
antichains,
birational actions,
birational rowmotion,
Brouwer-Schrijver map,
cluster algebras,
orbit,
order ideals,
Panyushev complementation,
poset,
product of chains,
promotion,
rowmotion,
toggle group,
Zamolodchikov conjecture. 
}
% No need to include the dates
%\received{(Some date $\leq$ 1$^{\mbox{\footnotesize{st}}}$ December 2009)}
%\revised{\today}
%\accepted{tomorrow}

\begin{document}
\maketitle
\begin{abstract}
\paragraph{Abstract.}

Various authors have studied a natural operation (under various
names) on the order ideals (equivalently antichains) of a finite poset,
here called \emph{rowmotion}.  For certain posets of interest, the order
of this map is much smaller than one would naively expect, and the
orbits exhibit unexpected properties.  In very recent work (inspired
by discussions with Berenstein) Einstein and Propp describe how
rowmotion can be generalized: first to the piecewise-linear setting of
order polytopes, then via detropicalization to the birational setting.  

In the latter setting, it is no longer \emph{a priori} clear even that
birational rowmotion has finite order, and for many posets the order
is infinite.  However, we are able to show that birational
rowmotion has the same order, $p+q$, for the poset $P=[p]\times [q]$
(product of two chains), as ordinary rowmotion. We also show
that birational (hence ordinary) rowmotion has finite order for some
other classes of posets, e.g., the upper, lower, right and left halves
of the poset above, and trees having all leaves on the same level.  Our
methods are based on those used by Volkov to resolve the type $AA$
(rectangular) Zamolodchikov Periodicity Conjecture. 

% Here goes the French abstract
\paragraph{R\'esum\'e.}

Une opération naturelle sur les idéaux d'ordre (ou, de façon
équivalente, sur les antichaînes) d'un ensemble partiellement ordonné
fini, appelée ici \emph{rowmotion}, a été étudiée par divers auteurs.
Pour certains ensembles partiellement ordonnés particulièrement
intéressants, l'ordre de cette application \emph{rowmotion} est beaucoup
plus petit que ce à quoi on peut s'attendre naïvement, et ses orbites
ont des propriétés inattendues. Dans un travail très récent (inspiré par
des conversations avec Berenstein), Einstein et Propp ont décrit comment
le \emph{rowmotion} peut être généralisé: d'abord au contexte linéaire
par morceaux des polytopes d'ordre, ensuite au contexte birationnel par
détropicalisation.

Dans ce dernier contexte, il n'est même plus clair \emph{a priori} si le
\emph{rowmotion} birationnel est d'ordre fini, et son ordre est infini
pour beaucoup d'ensembles partiellement ordonnés. Malgré tout, nous
avons pu montrer que le \emph{rowmotion} birationnel a le même ordre
$p+q$ pour l'ensemble partiellement ordonné $P=[p]\times [q]$ (produit
de deux chaînes) que le \emph{rowmotion} ordinaire. Nous montrons aussi
que le \emph{rowmotion} birationnel (et par conséquent le
\emph{rowmotion ordinaire} aussi) est d'ordre fini pour d'autres classes
d'ensembles partiellement ordonnés, par exemple les moitiés supérieure,
inférieure, droite et gauche de l'ensemble partiellement ordonné
mentionné auparavant, et les arbres dont toutes les feuilles sont au
même niveau. Nos méthodes sont basées sur celles utilisées par Volkov
pour établir la conjecture de périodicité de Zamolodchikov de type $AA$
(rectangulaire).


\end{abstract}

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

Numerous authors have studied a natural operation (under various
names) on the order ideals (equivalently antichains) of a finite poset,
here called \emph{rowmotion}, following Striker and
Williams~\cite{striker-williams}.  For certain posets of interest, the
order of this map is much smaller than one would naively
expect~\cite{brouwer-schrijver}, and its orbits exhibit further unexpected
patterns as found in \cite{propp-roby}, \cite{Pan08} and \cite{AST11}.

In very recent work, Einstein and Propp~\cite{einstein-propp} describe
how rowmotion can be generalized: first to the piecewise-linear setting
of an order polytope~\cite[Definition 1.1]{stanley-polytopes}, then via
detropicalization to the birational setting; they also find applications to
classical combinatorics of tableaux.  Much of their paper focuses
on the case where the poset $P$ is $[p]\times [q]$, a product of two
chains, generalizing earlier work of Propp and Roby in the
combinatorial setting~\cite{propp-roby}.  Their paper provides much of
the context and the motivation for our work.  

In the birational setting, it is no longer \emph{a priori} clear even
that rowmotion has finite order, since the set of possible labellings of
$P$ is infinite (unlike the set of antichains or order ideals).  Indeed,
for some simple posets (including the product of three length-$2$
chains) the order is infinite.  However, we prove as one of
our main results that birational rowmotion has the same order, $p+q$,
for the poset $P=[p]\times [q]$ as ordinary rowmotion. We have also found that
birational rowmotion has finite order for several other
classes of posets, e.g., the upper, lower, right and left halves of the
poset above, and trees which are graded (as posets).  Our methods are
based on those used by Volkov to resolve the type $AA$ (rectangular)
Zamolodchikov Periodicity Conjecture~\cite{volkov}. In the case of a rectangle,
we also demonstrate a symmetry property of birational rowmotion conjectured by
James Propp and Tom Roby.

In this extended abstract, proofs are only roughly outlined. Full arguments and further details can be found in \cite{main}. Applications of our results (specifically Theorems
\ref{thm.rect.ord} and \ref{thm.rect.antip.general}) are found in \cite{einstein-propp}. 


\subsection{Acknowledgments}

The authors are grateful to James Propp for many helpful suggestions
guiding this work and explaining his own; to
Arkady Berenstein for instruction how to generalize rowmotion to
the birational setting; to Gregg Musiker and Pavlo Pylyavskyy for
suggesting the link to Zamolodchikov's conjecture, and references to
Volkov's paper; % and (potentially) to cluster algebras; 
to David Einstein for regular communications and
many helpful suggestions; to Jessica Striker and Nathan Williams for
helping understand their work and some background notions; to Hugh
Thomas and the referees for improvements on the writing.

%Both authors have benefitted from travel funding from NSF grant \#1001905, and made
%significant use of Sage-combinat \cite{sage-combinat} in gathering
%computational evidence to the results proven below.

\section{Birational Rowmotion}\label{sec:BiRow}

Except when stated otherwise, we follow the standard notations and conventions for
posets of Stanley~\cite[Ch.~3]{stanley-ec1} (but we write our maps on
the left). We recall one definition of
classical rowmotion (\cite[Theorem 4.4]{striker-williams}, originally due to
Cameron and Fon-der-Flaass):

\begin{definition}\label{def.classicalr}

Let $P$ be a finite poset,
and $J\left(  P\right)  $ 
the set of the order 
ideals of $P$.  
(Classical) \emph{rowmotion} is a map $J\left(  P\right)  \rightarrow
J\left(  P\right)  $ which can be defined in various ways, perhaps the
simplest being as follows: For every $v\in P$, let $\mathbf{t}_{v}:J\left(
P\right)  \rightarrow J\left(  P\right)  $ be the map sending every order
ideal $S\in J\left(  P\right)  $ to $\left\{
\begin{array}
[c]{l}%
S\cup\left\{  v\right\}  \text{, if }v\notin P\text{ and }S\cup\left\{
v\right\}  \in J\left(  P\right)  ;\\
S\setminus\left\{  v\right\}  \text{, if }v\in P\text{ and }S\setminus\left\{
v\right\}  \in J\left(  P\right)  ;\\
S\text{, otherwise}%
\end{array}
\right.  $.

Let $\left(  v_{1}%
,v_{2},...,v_{m}\right)  $ be any linear extension of $P$.  Rowmotion
is then defined as the composition
$\mathbf{t}_{v_{1}}\circ\mathbf{t}_{v_{2}}\circ...\circ 
\mathbf{t}_{v_{m}} : J\left(P\right) \to J\left(P\right)$; this is
independent of the linear extension chosen. 

\end{definition}

For most of this abstract we will study an analogue of this map in the
birational setting; Definition \ref{def.classicalr} will only be used in Section~\ref{sect.classicalr}.
Let us now introduce the setting we will be working in (\cite[§1-§3]{main}).

For any poset $P$ we write $u \lessdot v$ if $u$ is \emph{covered by}
$v$, i.e., if we have have $u<v$ and there is no $w\in P$ such that $u<w<v$;
similarly we use $u \gtrdot v$ for the dual relation ``$u$ covers $v$''.
Define $\widehat{P}$
to be the poset $P$ with the addition of a minimum element $0$ and a
maximum element $1$ (even if such elements already exist within $P$
itself; in other words, $\widehat{P}$ is the ordinal sum $\left\{
0\right\} \oplus P\oplus\left\{ 1\right\} $).  

Assume $P$ is a \textrm{graded} poset, in the sense that every maximal chain in $P$ has
the same length (say $n-1$). Then $\widehat{P}$ is also a graded poset;
for every $v\in \widehat{P}$ we define the \emph{degree} ($\deg$) of 
$v$ to be the maximum length (= cardinality minus one) of a chain in
$\widehat{P}$ with highest element $v$.  This agrees with the ordinary
notion of \emph{rank} in $\widehat{P}$, but is off by 1 in $P$
itself. We say that $P$ is \emph{$n$-graded} if the degree of $1\in
\widehat{P}$ is $n+1$.  For each $i\in \{0,1,2,\dotsc , n+1\}$, let
$\widehat{P}_{i}$ denote $\{v\in \widehat{P}: \deg v = i \}$. 


\begin{definition}
\label{def.labelling}Let $P$ be a poset. We fix an infinite field
$\mathbb{K}$ for the rest of this abstract. A
$\mathbb{K}$\emph{-labelling of }$P$ will mean a map $f:\widehat{P}%
\rightarrow\mathbb{K}$. Thus, $\mathbb{K}^{\widehat{P}}$ is the set of all
$\mathbb{K}$-labellings of $P$. If $f$ is a $\mathbb{K}$-labelling of $P$ and
$v$ is an element of $\widehat{P}$, then $f\left(  v\right)  $ will be called
the \emph{label of }$f$ \emph{at }$v$.
\end{definition}

Most of the maps that we will be considering are rational maps between
algebraic varieties (specifically, between open subsets of affine or
projective spaces). We use the punctured arrow $\dashrightarrow$ to
signify rational maps (i.e., a rational map from a variety $U$ to a
variety $V$ is called a rational map $U\dashrightarrow V$). A rational
map $U\dashrightarrow V$ is said to be \emph{dominant} if its image is
dense in $V$ (with respect to the Zariski topology). 

\begin{definition}
\label{def.Tv}Let $v\in P$. We define a rational map $T_{v}:\mathbb{K}^{\widehat{P}%
}\dashrightarrow\mathbb{K}^{\widehat{P}}$ called the (birational) $v$\emph{-toggle} by%
\begin{equation}
\left(  T_{v}f\right)  \left(  w\right)  =\left\{
\begin{array}
[c]{l}%
f\left(  w\right)  ,\ \ \ \ \ \ \ \ \ \ \text{if }w\neq v;\\
\dfrac{1}{f\left(  v\right)  }\cdot
\left(\sum\limits_{\substack{u\in \widehat{P};\\u\lessdot v}}f\left(  u\right)  \right)
\left(\sum\limits_{\substack{u\in
\widehat{P};\\u\gtrdot v}}\dfrac{1}{f\left(  u\right)  }\right)^{-1}%
,\ \ \ \ \ \ \ \ \ \ \text{if }w=v
\end{array}
\right.  \ \ \ \ \ \ \ \ \ \ \text{for all }w\in\widehat{P} \label{def.Tv.def}%
\end{equation}
for all $f\in\mathbb{K}^{\widehat{P}}$ which don't render one of the denominators above zero.
%(This rational map $T_{v}$ is
%well-defined, because the right-hand side of (\ref{def.Tv.def}) is
%well-defined on a Zariski-dense subset of $\mathbb{K}^{\widehat{P}}$%
%%\ \ \ \ \footnotemark
%.) This rational map $T_{v}$ is called the
%$v$\emph{-toggle}.
\end{definition}


It is very easy to check that the maps $T_{v}$ are involutive
($T_{v}^{2}=\id$) dominant rational maps and satisfy the following ``locality
principle'':

\begin{proposition}
\label{prop.Tv.commute}Let $P$ be a finite poset. 
Let $v\in P$ and $w\in P$. Then, $T_{v}\circ T_{w}=T_{w}\circ T_{v}$, unless
we have either $v \lessdot w$ or $w \lessdot v$.
\end{proposition}

Combining this with \cite[Prop. 4.1]{ayyer-klee-schilling} (the
transposition case), we obtain:

\begin{corollary}
\label{cor.R.welldef}Let $P$ be a finite poset. 
Let $\left(  v_{1},v_{2},...,v_{m}\right)  $ be a linear extension of $P$.
Then, the dominant rational map $T_{v_{1}}\circ T_{v_{2}}\circ...\circ
T_{v_{m}}:\mathbb{K}^{\widehat{P}}\dashrightarrow\mathbb{K}^{\widehat{P}}$ is
well-defined and independent of the choice of the linear extension $\left(
v_{1},v_{2},...,v_{m}\right)  $.
\end{corollary}


\begin{definition}
\label{def.rm}Let $P$ be a finite poset. 
\emph{Birational rowmotion} is defined as the dominant rational map
$R:= T_{v_{1}}\circ T_{v_{2}}\circ...\circ T_{v_{m}}:\mathbb{K}^{\widehat{P}%
}\dashrightarrow\mathbb{K}^{\widehat{P}}$, where $\left(  v_{1},v_{2}%
,...,v_{m}\right)  $ is a linear extension of $P$. 

%This rational map is
%well-defined (in particular, it does not depend on the linear extension
%$\left(  v_{1},v_{2},...,v_{m}\right)  $ chosen) due to Corollary
%\ref{cor.R.welldef} (and also due to the fact that a linear extension of $P$
%exists; this is Theorem \ref{thm.linext.ex}). This rational map will be
%denoted by $R$.
\end{definition}

The reason for the names ``birational toggle'' and ``birational rowmotion'' is
explained in the paper \cite{einstein-propp}, in which birational rowmotion
(there defined over $\mathbb{R}_{+}$) is denoted by $\rho_{\mathcal{B}}$.


\begin{example}{}\label{}
Let $P=[2]\times [2]$, with generic initial labeling $f$ as shown (with
$(2,1)$ being the leftmost element), except
that we also assign $f(\hat{0})=f(\hat{1})=1$ in $\widehat{P}$.  Then 
applying the toggling operators $T_{(2,2)}$, $T_{(2,1)}$, $T_{(1,2)}$,
$T_{(1,1)}$ in that order (as shown) results in the final labeling $Rf$.

\xymatrixrowsep{0.4pc}
\xymatrixcolsep{0.10pc}
\SelectTips{cm}{12}
\[
\UseTips
\kern -7pt \xymatrix{
   & z\ar@{-}[rd] &    &&    &  \color{red}\frac{x+y}{z}\ar@{-}[rd] &    &&    &   \frac{x+y}{z}\ar@{-}[rd] &     &&   & \frac{x+y}{z}\ar@{-}[rd] & &&   & \frac{x+y}{z}\ar@{-}[rd] &    \\
x\ar@{-}[ru] &    & y\ar@{-}[ld] &\color{blue}\stackrel{T_{(2,2)}}{\mapsto }&x\ar@{-}[ru] &    & y\ar@{-}[ld] &\color{blue}\stackrel{T_{(2,1)}}{\mapsto }& \color{red}\frac{w(x+y)}{xz}\ar@{-}[ru] &    & y\ar@{-}[ld] &  \color{blue}\stackrel{T_{(1,2)}}{\mapsto }&\frac{w(x+y)}{xz}\ar@{-}[ru] &    &  \color{red}\frac{w(x+y)}{yz}\ar@{-}[ld] & \color{blue}\stackrel{T_{(1,1)}}{\mapsto }&\frac{w(x+y)}{xz}\ar@{-}[ru] &    &  \frac{w(x+y)}{yz}\ar@{-}[ld] \\
   & w\ar@{-}[lu] &    &&    & w\ar@{-}[lu] &    &&    &  w\ar@{-}[lu] &    &&   & w\ar@{-}[lu] & &&   & \color{red}\frac{1}{z}\ar@{-}[lu] 
}
\]

If we apply the birational rowmotion operator four times, we return to our initial
labeling: 
\xymatrixrowsep{0.64pc}
\xymatrixcolsep{0.64pc}
\SelectTips{cm}{12}
\kern -10pt
\[
\UseTips
\kern -7pt \xymatrix{
   & z\ar@{-}[rd] &    &&    & \frac{x+y}{z}\ar@{-}[rd] &    &&    &  \frac{w(x+y)}{xy}\ar@{-}[rd] &     &&   & \frac{1}{w}\ar@{-}[rd] \ar@/_2.5pc/@[blue][llllllllllll]_{\color{blue}R}&    \\
x\ar@{-}[ru] &    & y\ar@{-}[ld] &\color{blue}\stackrel{R}{\rightarrow }& \frac{w(x+y)}{xz}\ar@{-}[ru] &    & \frac{w(x+y)}{yz}\ar@{-}[ld] &\color{blue}\stackrel{R}{\rightarrow }& \frac{1}{y}\ar@{-}[ru] &    & \frac{1}{x}\ar@{-}[ld] &  \color{blue}\stackrel{R}{\rightarrow }&\frac{yz}{w(x+y)}\ar@{-}[ru] &    & \frac{xz}{w(x+y)}\ar@{-}[ld] \\
   & w\ar@{-}[lu] &    &&    & \frac{1}{z}\ar@{-}[lu] &    &&    & \frac{z}{x+y}\ar@{-}[lu] &    &&   & \frac{xy}{w(x+y)}\ar@{-}[lu]
}
\]

\end{example}

Doing toggles in the opposite order does not give anything new, just the
inverse of the above map: 

\begin{proposition}
\label{prop.R.inverse}Let $P$ be a finite poset. 
Then, birational rowmotion $R$ is invertible (as a rational map). Its inverse
$R^{-1}$ is $T_{v_{m}}\circ T_{v_{m-1}}\circ...\circ T_{v_{1}}:\mathbb{K}%
^{\widehat{P}}\dashrightarrow\mathbb{K}^{\widehat{P}}$, where $\left(
v_{1},v_{2},...,v_{m}\right)  $ is a linear extension of $P$.
\end{proposition}

Although $R$ is defined for any finite poset, we will only
consider it here for graded posets.  In this case the rowmotion map can
be factored as a product of simpler involutions: 

\begin{definition}
\label{def.Ri} Let $P$ be an $n$-graded poset. Let
$i\in\left\{  1,2,...,n\right\}  $. Then, let $R_{i}$ 
denote the dominant rational map $T_{u_{1}}\circ T_{u_{2}}\circ...\circ
T_{u_{k}}:\mathbb{K}^{\widehat{P}}\dashrightarrow\mathbb{K}^{\widehat{P}}$,
where $\left(  u_{1},u_{2},...,u_{k}\right)  $ is any list of the elements of
$\widehat{P}_{i}$ with every element of $\widehat{P}_{i}$ appearing exactly
once in the list. This map $T_{u_{1}}\circ T_{u_{2}}\circ...\circ T_{u_{k}}$
is well-defined (in particular, it does not depend on the list $\left(
u_{1},u_{2},...,u_{k}\right)  $). 
\end{definition}

\begin{remark}
\label{rmk.Ri.R}  
Let $P$ be
an $n$-graded poset. Then, $R=R_{1}\circ R_{2}\circ...\circ
R_{n}$.  
Moreover, each $R_{i}$ is an involution
(that is, $R_{i}^{2}=\operatorname*{id}$ on the set where
$R_{i}$ is defined).
\end{remark}



\section{The $\mathbf{w}_{i}(f)$ checksums}

\begin{definition}
\label{def.wi} Let $P$ be an
$n$-graded poset. Let $f\in\mathbb{K}^{\widehat{P}}$. Let $i\in\left\{
0,1,...,n\right\}  $. Then, $\mathbf{w}_{i}\left(  f\right)  $ will denote the
element of $\mathbb{K}$ defined by%
\[
\mathbf{w}_{i}\left(  f\right)  =\sum_{\substack{x\in\widehat{P}_{i}%
;\ y\in\widehat{P}_{i+1};\\y\gtrdot x}}\dfrac{f\left(  x\right)  }{f\left(
y\right)  }.
\]
(This element is not always defined, but is defined in the ``generic'' case when
$0\notin f\left(  \widehat{P}\right)  $.)
\end{definition}

The intuition behind this definition is that the $\mathbf{w}_{i}\left(  f\right)  $
is a kind of ``checksum'' for the labelling $f$ which displays how much its labels at
degree $i+1$ differ from those at degree $i$. These ``checksums'' alone are not very
informative, but combined with the so-called homogenization of $f$ (which
will be introduced in Definition \ref{def.hgeq}) and the value $f(0)$ they will
suffice to uniquely determine $f$, thus helping us ``split up'' the dynamical
system of a labelling under $R$ into three subsystems.
As for now let us see that they behave in a rather simple way under the
maps $R$ and $R_{j}$. Indeed, simple computations (\cite[§4]{main}) show:

\begin{proposition}
\label{prop.wi.Ri} Let $P$
be an $n$-graded poset. Let $i\in\left\{  1,2,...,n\right\}  $. Then, every
$f\in\mathbb{K}^{\widehat{P}}$ satisfies%
\begin{align*}
&  \left(  \mathbf{w}_{0}\left(  R_{i}f\right)  ,\mathbf{w}_{1}\left(
R_{i}f\right)  ,...,\mathbf{w}_{n}\left(  R_{i}f\right)  \right) \\
&  =\left(  \mathbf{w}_{0}\left(  f\right)  ,\mathbf{w}_{1}\left(  f\right)
,...,\mathbf{w}_{i-2}\left(  f\right)  ,\mathbf{w}_{i}\left(  f\right)
,\mathbf{w}_{i-1}\left(  f\right)  ,\mathbf{w}_{i+1}\left(  f\right)
,\mathbf{w}_{i+2}\left(  f\right)  ,...,\mathbf{w}_{n}\left(  f\right)
\right)  .
\end{align*}

\end{proposition}

From Proposition \ref{prop.wi.Ri}, and Remark~\ref{rmk.Ri.R}
we conclude:

\begin{proposition}
\label{prop.wi.R} Let $P$ be
an $n$-graded poset. Then, every $f\in\mathbb{K}^{\widehat{P}}$ satisfies%
\[
\left(  \mathbf{w}_{0}\left(  Rf\right)  ,\mathbf{w}_{1}\left(  Rf\right)
,...,\mathbf{w}_{n}\left(  Rf\right)  \right)  =\left(  \mathbf{w}_{n}\left(
f\right)  ,\mathbf{w}_{0}\left(  f\right)  ,\mathbf{w}_{1}\left(  f\right)
,...,\mathbf{w}_{n-1}\left(  f\right)  \right)  .
\]

\end{proposition}


\section{Homogeneous labellings}

In general, birational rowmotion $R$ has an ``avalanche effect'', meaning
that a change of just one label in a labelling will often ``spread'' through a
large part of the poset when $R$ is applied; the effect of such a change is
hard to track in general. However, for a graded poset $P$, if we simultaneously
multiply the labels at all vertices of a given degree with a given scalar,
then the changes this causes to the behavior of the labelling under $R$ are
rather predictable. Explicit formulas are given in \cite[§5]{main}; here we
content ourselves with introducing a notion of \emph{homogeneous equivalence}
which formalizes the idea of a ``labelling modulo scalar factors at each
degree'' (\cite[§6]{main}).

\begin{definition}
\textbf{(a)} For every $\mathbb{K}$-vector space $V$, let $\mathbb{P}\left(
V\right)  $ denote the projective space of $V$ (that is, the set
$V\setminus\left\{  0\right\}  $ modulo proportionality).

\textbf{(b)} For every $n\in\mathbb{N}$, we let $\mathbb{P}^{n}\left(
\mathbb{K}\right)  $ denote the projective space $\mathbb{P}\left(
\mathbb{K}^{n+1}\right)  $.
\end{definition}

\begin{definition}
\label{def.hgeq} Let $P$ be
an $n$-graded poset.

\textbf{(a)} Denote by $\overline{\mathbb{K}^{\widehat{P}}}$ the product
$\prod\limits_{i=1}^{n}\mathbb{P}\left(  \mathbb{K}^{\widehat{P}_{i}}\right)
$ of projective spaces\footnote{This is a Cartesian product of algebraic varieties. As a
set, it is just a Cartesian product of sets. The topology is the
quotient topology from the Zariski topology on the product of the
respective affine varieties.}.
So $\overline{\mathbb{K}^{\widehat{P}}} \cong\prod
\limits_{i=1}^{n}\mathbb{P}^{\left\vert \widehat{P}_{i}\right\vert -1}\left(
\mathbb{K}\right)  $.

Notice that $\overline{\mathbb{K}^{\widehat{P}}}=\prod\limits_{i=1}%
^{n}\mathbb{P}\left(  \mathbb{K}^{\widehat{P}_{i}}\right)  \cong%
\prod\limits_{i=0}^{n+1}\mathbb{P}\left(  \mathbb{K}^{\widehat{P}_{i}}\right)
$ (as algebraic varieties). This is because $\mathbb{K}^{\widehat{P}_{0}}$ and
$\mathbb{K}^{\widehat{P}_{n+1}}$ are $1$-dimensional vector spaces, and thus
$\mathbb{P}\left(  \mathbb{K}^{\widehat{P}_{0}}\right)  =\left\{
\operatorname*{pt}\right\}  $ and $\mathbb{P}\left(  \mathbb{K}^{\widehat{P}%
_{n+1}}\right)  =\left\{  \operatorname*{pt}\right\}  $.

\textbf{(b)} A $\mathbb{K}$-labelling $f\in\mathbb{K}^{\widehat{P}}$ is said
to be \emph{zero-free} if for every $i\in\left\{  0,1,...,n+1\right\}  $,
there exists some $v\in\widehat{P}_{i}$ satisfying $f\left(  v\right)  \neq0$.
Let $\mathbb{K}_{\neq0}^{\widehat{P}}$ be the set of all
zero-free $\mathbb{K}$-labellings. Clearly, this set $\mathbb{K}_{\neq
0}^{\widehat{P}}$ is Zariski-dense in $\mathbb{K}^{\widehat{P}}$. (Thus we do
not lose any generality from only considering zero-free labellings. The image
$R^2 f$ is not well-defined if $f$ is not zero-free anyway.)

\textbf{(c)} Identify the set $\mathbb{K}^{\widehat{P}}$ with $\prod
\limits_{i=0}^{n+1}\mathbb{K}^{\widehat{P}_{i}}$ in the obvious way (since
$\widehat{P}$, regarded as a set, is the disjoint union of the sets
$\widehat{P}_{i}$ over all $i\in\left\{  0,1,...,n+1\right\}  $). Define a
rational map $\pi:\mathbb{K}^{\widehat{P}}\dashrightarrow\overline
{\mathbb{K}^{\widehat{P}}}$ as the product of the canonical projections
$\mathbb{K}^{\widehat{P}_{i}}\dashrightarrow\mathbb{P}\left(  \mathbb{K}%
^{\widehat{P}_{i}}\right)  $ (which are defined everywhere outside of the
$\left\{  0\right\}  $ subsets) over all $i\in\left\{  0,1,...,n+1\right\}  $.
Notice that the domain of definition of this rational map $\pi$ is precisely
$\mathbb{K}_{\neq0}^{\widehat{P}}$. For every $f\in\mathbb{K}^{\widehat{P}}$,
we denote $\pi\left(  f\right)  $ as the \emph{homogenization} of the
$\mathbb{K}$-labelling $f$.

\textbf{(d)} Two zero-free $\mathbb{K}$-labellings $f\in\mathbb{K}%
^{\widehat{P}}$ and $g\in\mathbb{K}^{\widehat{P}}$ are said to be
\emph{homogeneously equivalent} if and only if they satisfy one of the
following equivalent conditions:

\emph{Condition 1:} For every $i\in\left\{  0,1,...,n+1\right\}  $ and any
$x \in \widehat{P}_{i}$ and $y \in \widehat{P}_{i}$, we have $\dfrac{f\left(
x\right)  }{f\left(  y\right)  }=\dfrac{g\left(  x\right)  }{g\left(
y\right)  }$.

\emph{Condition 2:} There exists an $\left(  n+2\right)  $-tuple $\left(
a_{0},a_{1},...,a_{n+1}\right)  \in\left(  \mathbb{K}^{\times}\right)  ^{n+2}$
such that every $x\in\widehat{P}$ satisfies $g\left(  x\right)  =a_{\deg
x}\cdot f\left(  x\right)  $.

\emph{Condition 3:} We have $\pi\left(  f\right)  =\pi\left(  g\right)  $.
\end{definition}

\begin{remark}
Homogeneous equivalence is an equivalence relation on the set
$\mathbb{K}_{\neq0}^{\widehat{P}}$ of all zero-free $\mathbb{K}$-labellings.
We can identify $\overline{\mathbb{K}^{\widehat{P}}}$ with the quotient of the
set $\mathbb{K}_{\neq0}^{\widehat{P}}$ modulo this relation. Then, $\pi$
becomes the canonical projection map $\mathbb{K}^{\widehat{P}}\dashrightarrow
\overline{\mathbb{K}^{\widehat{P}}}$.
\end{remark}

Birational rowmotion and the $R_{i}$'s respect homogeneous equivalence: 

\begin{corollary}
\label{cor.hgRi} Let $P$ be
an $n$-graded poset. Let $i\in\left\{  1,2,...,n\right\}  $. If $f\in
\mathbb{K}^{\widehat{P}}$ and $g\in\mathbb{K}^{\widehat{P}}$ are two
homogeneously equivalent zero-free $\mathbb{K}$-labellings, then $R_{i}f$ is
homogeneously equivalent to $R_{i}g$.
\end{corollary}

\begin{corollary}
\label{cor.hgR}Let $P$ be
an $n$-graded poset. If $f\in\mathbb{K}^{\widehat{P}}$ and $g\in
\mathbb{K}^{\widehat{P}}$ are two homogeneously equivalent zero-free
$\mathbb{K}$-labellings, then $Rf$ is homogeneously equivalent to $Rg$.
\end{corollary}

Corollary \ref{cor.hgRi} would not hold with
$R_{i}$ replaced by a single toggle $T_{v}$! So the operators $R_{i}$ in some sense
combine the features of $T_{v}$ (like being an involution) with the features of $R$ (like having
a simple effect on the $\mathbf{w}_{i}(f)$ checksums, cf. Proposition \ref{prop.wi.Ri},
and respecting homogeneous equivalence, cf. Corollary \ref{cor.hgRi}).

\begin{definition}
\label{def.hgRi} Let $P$ be
an $n$-graded poset. Because of
Corollary \ref{cor.hgR}, the rational map $R:\mathbb{K}^{\widehat{P}%
}\dashrightarrow\mathbb{K}^{\widehat{P}}$ descends (through the projection
$\pi:\mathbb{K}^{\widehat{P}}\dashrightarrow\overline{\mathbb{K}^{\widehat{P}%
}}$) to a partial map $\overline{\mathbb{K}^{\widehat{P}}}\dashrightarrow
\overline{\mathbb{K}^{\widehat{P}}}$. We denote this partial map
$\overline{\mathbb{K}^{\widehat{P}}}\dashrightarrow\overline{\mathbb{K}%
^{\widehat{P}}}$ by $\overline{R}$. Thus, the diagram $
\xymatrixcolsep{3pc}\xymatrixrowsep{1.5pc}\xymatrix{
\mathbb K^{\widehat P} \ar@{.>}[r]^{R} \ar@{.>}[d]_-{\pi} & \mathbb
K^{\widehat P}
\ar@{.>}[d]^-{\pi} \\
\overline{\mathbb K^{\widehat P}} \ar@{.>}[r]_{\overline{R}} & \overline
{\mathbb K^{\widehat P}}
} $
is commutative.
\end{definition}

We could similarly define maps $\overline{R_{i}} : \overline{\mathbb{K}^{\widehat{P}}}\dashrightarrow
\overline{\mathbb{K}^{\widehat{P}}}$ from the maps $R_{i}$.

Now, given a $\mathbb{K}$-labelling $f$ of an $n$-graded poset $P$, we can construct three
images of it: the value $f(0)$ at the global minimum $0$, the $(n+1)$-tuple $\left(  \mathbf{w}%
_{0}\left(  f\right)  ,\mathbf{w}_{1}\left(  f\right)  ,...,\mathbf{w}%
_{n}\left(  f\right)  \right)  $, and the projection $\pi(f)$ of $f$ on
$\overline{\mathbb{K}^{\widehat{P}}}$. These three images behave like
independent subsystems under birational rowmotion: The value $f(0)$ stays
unchanged, the $(n+1)$-tuple is cyclically shifted (Proposition~\ref{prop.wi.R}),
and the projection $\pi(f)$ undergoes the map $\overline{R}$. The thing that
makes this observation really useful is the fact that these three images more or
less determine $f$ (almost always), whence properties of the original map $R$
can be deduced by considering these three subsystems:

\begin{proposition}
\label{prop.reconstruct} Let
$P$ be an $n$-graded poset. Let $f$ and $g$ be two zero-free $\mathbb{K}%
$-labellings in $\mathbb{K}^{\widehat{P}}$ such that $\left(  \mathbf{w}%
_{0}\left(  f\right)  ,\mathbf{w}_{1}\left(  f\right)  ,...,\mathbf{w}%
_{n}\left(  f\right)  \right)  =\left(  \mathbf{w}_{0}\left(  g\right)
,\mathbf{w}_{1}\left(  g\right)  ,...,\mathbf{w}_{n}\left(  g\right)  \right)
$ and such that no $i\in\left\{  0,1,...,n\right\}  $ satisfies $\mathbf{w}%
_{i}\left(  f\right)  =0$. Also assume that $\pi\left(  f\right)  =\pi\left(
g\right)  $ and $f\left(  0\right)  =g\left(  0\right)  $. Then, $f=g$.
\end{proposition}

Proposition \ref{prop.reconstruct} is easily proven by reconstructing $f$ and
$g$ ``bottom-up'' along $\widehat{P}$. 

\begin{definition}
Let $S$ be a set. The \emph{order} $\operatorname*{ord} \varphi$ of a partial map $\varphi
:S\dashrightarrow S$ is defined to be the smallest positive integer $k$
satisfying $\varphi^{k}=\operatorname*{id}\nolimits_{S}$, if such a positive
integer $k$ exists, and $\infty$ otherwise. Here, we are disregarding the fact
that $\varphi$ is only a partial map; we will be working only with dominant
rational maps and their quotients, so nothing will go wrong.
\end{definition}

As a consequence of Proposition \ref{prop.reconstruct}, we have (\cite[§7]{main}):

\begin{proposition}
\label{prop.ord-projord} Let
$P$ be an $n$-graded poset. Then, $\operatorname*{ord}R=\operatorname{lcm}%
\left(  n+1,\operatorname*{ord}\overline{R}\right)  $. (Here,
$\operatorname{lcm}\left(  n+1,\infty\right)  $ is to be understood as
$\infty$.)
\end{proposition}

\section{Skeletal posets}

We are now going to compute the order of $R_P$ for a first large class of
posets $P$, which we call \emph{skeletal posets}. This class contains,
among other posets, all graded rooted forests (see below for more details).

\begin{definition}
Let $P$ be a finite poset. We denote the maps $R$
and $\overline{R}$ by $R_{P}$ and $\overline{R}_{P}$, respectively, so as to
make their dependence on $P$ explicit.
\end{definition}

\begin{definition}
 Let $P$ and $Q$ be two $n$-graded posets. We denote by
$PQ$ the disjoint union of the posets $P$ and $Q$. (This disjoint union is
denoted by $P+Q$ in \cite[\S 3.2]{stanley-ec1}. Its poset structure is defined
in such a way that any element of $P$ and any element of $Q$ are
incomparable.) Clearly, $PQ$ is again an $n$-graded poset.
\end{definition}

\begin{definition}
 Let $P$ be an $n$-graded poset. Let $k \in \left\{1,2,3,\ldots\right\}$.
We denote by $B_{k}P$ the result of adding $k$ new elements to the
poset $P$, and declaring these $k$ elements to be smaller than each of the
old elements of $P$ (but incomparable with each other). Clearly, $B_{k}P$ is
an $\left(n+1\right)$-graded poset. A poset $B_{k}^{\prime }P$ is defined in
the same way as $B_{k}P$ but with the new elements being higher rather than
smaller than the rest.
\end{definition}

\begin{definition}
\label{def.skeletal}We define the class of \emph{skeletal posets}
inductively by means of the following axioms:

-- The empty poset is skeletal.

-- If $P$ is an $n$-graded skeletal poset and $k \in \left\{1,2,3,\ldots\right\}$, then
the posets $B_{k}P$ and $B_{k}^{\prime}P$ are skeletal.

-- If $n$ is a positive integer and $P$ and $Q$ are two $n$-graded skeletal
posets, then the poset $PQ$ is skeletal.

Notice that every skeletal poset is graded. Also, every graded rooted
forest (seen as a poset by declaring each node smaller than its children) is a skeletal poset.
(Indeed, every such forest can be constructed from $\varnothing$ using
merely the operations $P\mapsto B_{1}P$ and $\left(  P,Q\right)  \mapsto PQ$.)
Similarly, every graded rooted arborescence (same as forest but each node is higher
than its children) is a skeletal poset.
\end{definition}

Skeletal posets turn out to be the simplest nontrivial class of posets on which
birational rowmotion can be shown to have finite order:

\begin{proposition}
\label{prop.skeletal.ords}Let $P$ be a skeletal poset. Then, $\operatorname*{ord}\left(  R_{P}\right)  $ and
$\operatorname*{ord}\left(  \overline{R}_{P}\right)  $ are finite.
\end{proposition}

The proof of this proposition (\cite[§9]{main}) follows the inductive definition of skeletal
posets, making use of several facts about $R$ and $\overline{R}$. The simplest
of these facts is:

\begin{proposition}
\label{prop.PQ.ord} Let $P$ and $Q$ be two $n$-graded
posets. Then, \newline
$\operatorname*{ord}\left(
R_{PQ}\right) = \operatorname*{ord}\left(
\overline{R}_{PQ}\right) =\operatorname{lcm}\left(  \operatorname*{ord}\left(
R_{P}\right)  ,\operatorname*{ord}\left(  R_{Q}\right)  \right)$.
\end{proposition}

It is a bit trickier but still not very difficult to track the effect of $B_{k}$ on the order of $\overline{R}$:

\begin{proposition}
\label{prop.Bk.ord} Let $P$ be an $n$-graded poset. 

\textbf{(a)} We have $\operatorname*{ord}\left(  \overline{R}_{B_{1}P}\right)
=\operatorname*{ord}\left(  \overline{R}_{P}\right)  $.

\textbf{(b)} For every integer $k>1$, we have $\operatorname*{ord}\left(
\overline{R}_{B_{k}P}\right)  =\operatorname{lcm}\left(  2,\operatorname*{ord}%
\left(  \overline{R}_{P}\right)  \right)  $.
\end{proposition}

An exact analogue of this holds for $B_{1}^{\prime }P$ and $B_{k}^{\prime }P$
instead of $B_{1}P$ and $B_{k}P$.

Using Propositions \ref{prop.PQ.ord}, \ref{prop.Bk.ord} (along with its analogue) and
\ref{prop.ord-projord}, it is easy to give an inductive proof of Proposition
\ref{prop.skeletal.ords} and even recursively compute (not just bound
from above) the orders of $R_{P}$ and $\overline{R}_{P}$ for any skeletal
poset $P$ without doing any computations in $\mathbb{K}$. (This also shows
that the orders of $R_{P}$ and $\overline{R}_{P}$ don't depend on the base
field $\mathbb{K}$ as long as $\mathbb{K}$ is infinite and $P$ is skeletal.) For
example, in the case of forests and trees, the following bound is established by
induction (exact values for orders depend on the structure of the forest):

\begin{corollary}
\label{cor.for.ord} Let $P$ be an $n$-graded poset.  Assume that $P$ is a forest (oriented in either way).
Then, $\operatorname*{ord}\left(  R_{P}\right)  \mid\operatorname{lcm}\left(
1,2,...,n+1\right)  $. Moreover, if $P$ is a tree, then $\operatorname*{ord}%
\left(  \overline{R}_{P}\right)  \mid\operatorname{lcm}\left(
1,2,...,n\right)  $.
\end{corollary}

\section{\label{sect.classicalr}Interlude: Classical rowmotion on skeletal
posets}

The above results concerning birational rowmotion on skeletal posets
suggest the question of what can be said about \textbf{classical}
rowmotion (Definition~\ref{def.classicalr})
on this class of posets. Indeed, while the
classical (as opposed to the birational) rowmotion map has been the object
of several studies \cite{striker-williams}, \cite{cameron-fon-der-flaass},
\cite{brouwer-schrijver}, it seems that this rather simple case
has never been explicitly studied before.  

Two convenient advantages of the classical setup are that we don't have to
worry about denominators becoming zero, so our maps are actual maps rather
than partial maps, and that we don't have to pass to
$\widehat{P}$. Other than this, most of the theory developed above for
birational rowmotion carries over to the case of classical rowmotion (maybe not
surprisingly seeing that classical rowmotion can be interpreted as a ``tropical
limit'' of birational rowmotion), enabling us to formulate analogues for
Corollary \ref{cor.for.ord}, Propositions \ref{prop.Bk.ord}, \ref{prop.PQ.ord},
\ref{prop.skeletal.ords} and many of the results stated
earlier. We leave the precise statements to \cite[§10]{main}, while only hinting at
the appropriate replacements for homogeneous equivalence and the
$\mathbf{w}_{i}(f)$'s here.

If $P$ is an $n$-graded poset and $S\in J\left(  P\right)  $, and $i\in\left\{  0,1,...,n\right\}  $, then
$\mathbf{w}_{i}\left(  S\right)  $ denotes the integer $
\left\{
\begin{array}
[c]{l}%
1,\text{ if }P_{i}\subseteq S\text{ and }P_{i+1}\cap S=\varnothing\\
0,\text{ otherwise}%
\end{array}
\right.  $.

Here, we are using the notation $P_{j}$ for the subset $\deg^{-1}\left(
\left\{  j\right\}  \right)  $ of $P$; this subset is empty if $j=0$ and also
empty if $j=n+1$.

These numbers $\mathbf{w}_{i}\left(  S\right)$ don't carry much information,
being $0$ for ``most'' order ideals. Nevertheless, they ``do the trick'' in the
classical rowmotion case.

To define the analogue of homogeneous equivalence, we introduce one more
notation. An order ideal of an $n$-graded poset $P$ is said to be \emph{level} if and only if it
has the form $P_{1}\cup P_{2}\cup...\cup P_{i}$ for some $i\in\left\{
0,1,...,n\right\}  $. An $n$-graded poset has precisely $n+1$ level orders,
and these form an orbit under classical rowmotion $\mathbf{r}$.
Two order ideals $S$ and $T$ of $P$ are said to be \emph{homogeneously
equivalent} if and only if either both $S$ and $T$ are level or we have $S=T$.
This is clearly an equivalence relation, and we can define
$\overline{J\left(  P\right)  }$ as the set of equivalence classes of
elements of $J\left(  P\right)  $ modulo this relation. Let $\pi$ denote the
canonical projection $J\left(  P\right)  \rightarrow\overline{J\left(
P\right)  }$. It turns out that this notion of homogeneous equivalence makes the
analogues of most of our results true, most crucially that of Proposition \ref{prop.reconstruct}:

\begin{proposition}
\label{prop.classical.reconstruct} Let $P$ be an
$n$-graded poset. Let $S$ and $T$ be two order ideals of $P$ such that \newline 
$\left(  \mathbf{w}_{0}\left(  S\right)  ,\mathbf{w}_{1}\left(  S\right)
,...,\mathbf{w}_{n}\left(  S\right)  \right)  =\left(  \mathbf{w}_{0}\left(
T\right)  ,\mathbf{w}_{1}\left(  T\right)  ,...,\mathbf{w}_{n}\left(
T\right)  \right)  $ and $\pi\left(  S\right)  =\pi\left(
T\right)  $. Then, $S=T$.
\end{proposition}

It is now straightforward to define a map $\overline{\mathbf{r}} : \overline{J\left(  P\right)  }\rightarrow\overline{J\left(
P\right)  }$ in the same way as we defined a map $\overline{R} : \overline{\mathbb{K}^{\widehat{P}}}\dashrightarrow
\overline{\mathbb{K}^{\widehat{P}}}$. This enables an analogue of Proposition
\ref{prop.ord-projord} and of all the results we stated about skeletal
posets. The analogy is strong enough to actually obtain an equality of orders:

\begin{proposition}

Let $P$ be a skeletal poset. Then, $\operatorname*{ord}\left(R_{P}\right) =
\operatorname*{ord}\left(\mathbf{r}_{P}\right)$ and $\operatorname*{ord}\left(\overline{R}_{P}\right) = \operatorname*{ord}\left(\overline{\mathbf{r}}_{P}\right)$.

\end{proposition}

This proposition does not generalize to arbitrary graded
posets.

\section{The rectangle: statements of the results}

\begin{definition}
\label{def.rect}Let $p$ and $q$ be two positive integers. The poset $\left\{  1,2,...,p\right\}
\times\left\{  1,2,...,q\right\}  $ with order defined componentwise
(that is,
$\left(  i,k\right)  \leq\left(  i^{\prime},k^{\prime}\right)  $ if and only
if $\left(  i\leq i^{\prime}\text{ and }k\leq k^{\prime}\right)  $) will be
denoted by $\operatorname*{Rect}\left(  p,q\right)  $ and called the
$p\times
q$\emph{-rectangle}. It is a $\left(  p+q-1\right)  $-graded
poset, with $\deg\left(  \left(  i,k\right)  \right)  =i+k-1$ for all $\left(
i,k\right)  \in\operatorname*{Rect}\left(  p,q\right)  $.
\end{definition}

The following two theorems (\cite[§11]{main}) were conjectured by James Propp and Tom Roby:

\begin{theorem}
\label{thm.rect.ord}We have $\operatorname*{ord}\left(
R_{\operatorname*{Rect}\left(  p,q\right)  }\right)  =p+q$.
\end{theorem}

\begin{theorem}
\label{thm.rect.antip.general} Let $f\in\mathbb{K}%
^{\widehat{\operatorname*{Rect}\left(  p,q\right)  }}$. Assume that
$R_{\operatorname*{Rect}\left(  p,q\right)  }^{\ell}f$ is well-defined for
every $\ell\in\left\{  0,1,...,i+k-1\right\}  $. Let $\left(  i,k\right)
\in\operatorname*{Rect}\left(  p,q\right)  $. Then,%
\[
f\left(  \left(  p+1-i,q+1-k\right)  \right)  =\dfrac{f\left(  0\right)
f\left(  1\right)  }{\left(  R_{\operatorname*{Rect}\left(  p,q\right)
}^{i+k-1}f\right)  \left(  \left(  i,k\right)  \right)  }.
\]

\end{theorem}

Theorem \ref{thm.rect.antip.general} is referred to as
``reciprocal symmetry property'' in \cite{einstein-propp}.

Notice that Proposition \ref{prop.ord-projord} yields that $p+q\mid
\operatorname*{ord}\left(  R_{\operatorname*{Rect}\left(  p,q\right)
}\right)  $, so all that needs to be done in order to verify Theorem
\ref{thm.rect.ord} is showing that $R_{\operatorname*{Rect}\left(  p,q\right)
}^{p+q}=\operatorname*{id}$.

\section{The crux of the proof}

We will only sketch the skeleta of the proofs of Theorems
\ref{thm.rect.ord} and \ref{thm.rect.antip.general}, leaving the details to \cite[§11-§16]{main}.

First of all, for the sake of the proofs, it can be WLOG assumed that
$f\left(0\right) = f\left(1\right) = 1$ (indeed, the general case can be
reduced to this case by applying Proposition \ref{prop.ord-projord}).
We now define a (rational) parametrization of the
space of labellings $f\in\mathbb{K}%
^{\widehat{\operatorname*{Rect}\left(  p,q\right)  }}$ satisfying $f\left(0\right) = f\left(1\right) = 1$ by certain matrices:

\begin{definition}
\label{def.minors} Let $A\in\mathbb{K}^{u\times
v}$ be a $u\times v$-matrix for some nonnegative integers $u$ and $v$.

\textbf{(a)} For every $i\in\left\{  1,2,...,v\right\}  $, let $A_{i}$ denote
the $i$-th column of $A$.

\textbf{(b)} Moreover, we extend this definition to all $i\in\mathbb{Z}$ as
follows: For every $i\in\mathbb{Z}$, let%
\[
A_{i}=\left(  -1\right)  ^{\left(  u-1\right)  \left(  i-i^{\prime}\right)
\diagup v}\cdot A_{i^{\prime}},
\]
where $i^{\prime}$ is the element of $\left\{  1,2,...,v\right\}  $ which is
$\equiv i$ modulo $v$. (Thus, $A_{v+i}=\left(  -1\right)  ^{u-1}A_{i}$
for every $i\in\mathbb{Z}$. Consequently, the sequence $\left(  A_{i}\right)
_{i\in\mathbb{Z}}$ is periodic with period dividing $2v$, and if $u$ is odd,
the period also divides $v$.)

\textbf{(c)} For any four integers $a$, $b$, $c$ and $d$ satisfying $a\leq b$
and $c\leq d$, we let $A\left[  a:b\mid c:d\right]  $ be the matrix whose
columns (from left to right) are $A_{a}$, $A_{a+1}$, $...$, $A_{b-1}$, $A_{c}%
$, $A_{c+1}$, $...$, $A_{d-1}$. (This matrix has $b-a+d-c$
columns.\footnotemark) When $b-a+d-c=u$ (note: not just $b-a+d-c\equiv
u\operatorname{mod}v$), then this matrix $A\left[  a:b\mid c:d\right]  $ is a
square matrix, and thus has a determinant $\det\left(  A\left[  a:b\mid
c:d\right]  \right)  $.
\end{definition}

\footnotetext{It is not always a submatrix of $A$. Its columns are columns of
$A$ multiplied with $1$ or $-1$; they can appear several times and need not
appear in the same order as they appear in $A$.}

\begin{example}
If $A$ is the $2\times3$-matrix $\left(
\begin{array}
[c]{ccc}%
3 & 5 & 7\\
4 & 1 & 9
\end{array}
\right)  $, then Definition \ref{def.minors} \textbf{(b)} yields
$A_{5}=\left(  -1\right)  ^{\left(  2-1\right)  \left(  5-2\right)
\diagup3}\cdot A_{2}=-A_{2}=-\left(
\begin{array}
[c]{c}%
5\\
1
\end{array}
\right)  =\left(
\begin{array}
[c]{c}%
-5\\
-1
\end{array}
\right)  $ and $A_{-4}=\left(  -1\right)  ^{\left(  2-1\right)  \left(
\left(  -4\right)  -2\right)  \diagup3}\cdot A_{2}=A_{2}=\left(
\begin{array}
[c]{c}%
5\\
1
\end{array}
\right)  $.
%
%If $A$ is the $3\times2$-matrix $\left(
%\begin{array}
%[c]{cc}%
%1 & 2\\
%3 & 2\\
%-5 & 4
%\end{array}
%\right)  $, then Definition \ref{def.minors} \textbf{(b)} yields (for
%instance) $A_{0}=\left(  -1\right)  ^{\left(  3-1\right)  \left(  0-2\right)
%\diagup2}\cdot A_{2}=A_{2}=\left(
%\begin{array}
%[c]{c}%
%2\\
%2\\
%4
%\end{array}
%\right)  $.
\end{example}


\begin{definition}
\label{def.Grasp} Let $p$ and $q$ be two positive
integers. Let $A\in\mathbb{K}^{p\times\left(  p+q\right)  }$. Let
$j\in\mathbb{Z}$.

We define a map $\operatorname*{Grasp}\nolimits_{j}A\in
\mathbb{K}^{\operatorname*{Rect}\left(  p,q\right)  }$ by%
\begin{align}
\left(  \operatorname*{Grasp}\nolimits_{j}A\right)  \left(  \left(
i,k\right)  \right)   &  =\dfrac{\det\left(  A\left[  j+1:j+i\mid
j+i+k-1:j+p+k\right]  \right)  }{\det\left(  A\left[  j:j+i\mid
j+i+k:j+p+k\right]  \right)  }\label{def.Grasp.def}\\
&  \ \ \ \ \ \ \ \ \ \ \left.  \text{for every }\left(  i,k\right)
\in\operatorname*{Rect}\left(  p,q\right)  =\left\{  1,2,...,p\right\}
\times\left\{  1,2,...,q\right\}  \right. \nonumber
\end{align}
(this is well-defined for a Zariski-generic $A$). This
map $\operatorname*{Grasp}\nolimits_{j}A$ will be considered as a
$\mathbb{K}$-labelling of $\operatorname*{Rect}\left(  p,q\right)  $, by setting
its values at $0$ and $1$ to be $1$.
\end{definition}

The notation $\operatorname*{Grasp}$ is meant to convey ``Grassmannian
parametrization'', as we will parametrize (generic) labellings on
$\operatorname*{Rect}\left(  p,q\right)  $ by matrices via this map
$\operatorname*{Grasp}\nolimits_{0}$. While we have defined
$\operatorname*{Grasp}\nolimits_{j}$ as a map from the matrix space
$\mathbb{K}^{p\times\left(  p+q\right)  }$, it actually factors through the
Grassmannian, because it is easy to see that $\operatorname*{Grasp}%
\nolimits_{j}A$ is invariant under row transformations of $A$. The idea
of using a ratio of determinants as in (\ref{def.Grasp.def}) goes back
to Volkov's proof \cite{volkov} of the Zamolodchikov periodicity conjecture.

\begin{example}
If $p=2$, $q=2$ and $A=\left(
\begin{array}
[c]{cccc}%
a_{11} & a_{12} & a_{13} & a_{14}\\
a_{21} & a_{22} & a_{23} & a_{24}%
\end{array}
\right)  $, then%
\[
\left(  \operatorname*{Grasp}\nolimits_{0}A\right)  \left(  \left(
1,1\right)  \right)  =\dfrac{\det\left(  A\left[  1:1\mid1:3\right]  \right)
}{\det\left(  A\left[  0:1\mid2:3\right]  \right)  }=\dfrac{\det\left(
\begin{array}
[c]{cc}%
a_{11} & a_{12}\\
a_{21} & a_{22}%
\end{array}
\right)  }{\det\left(
\begin{array}
[c]{cc}%
-a_{14} & a_{12}\\
-a_{24} & a_{22}%
\end{array}
\right)  }=\dfrac{a_{11}a_{22}-a_{12}a_{21}}{a_{12}a_{24}-a_{14}a_{22}}%
\]
and%
\[
\left(  \operatorname*{Grasp}\nolimits_{1}A\right)  \left(  \left(
1,2\right)  \right)  =\dfrac{\det\left(  A\left[  2:2\mid3:5\right]  \right)
}{\det\left(  A\left[  1:2\mid4:5\right]  \right)  }=\dfrac{\det\left(
\begin{array}
[c]{cc}%
a_{13} & a_{14}\\
a_{23} & a_{24}%
\end{array}
\right)  }{\det\left(
\begin{array}
[c]{cc}%
a_{11} & a_{14}\\
a_{21} & a_{24}%
\end{array}
\right)  }=\dfrac{a_{13}a_{24}-a_{14}a_{23}}{a_{11}a_{24}-a_{14}a_{21}}.
\]

\end{example}

\begin{remark}
\label{rmk.Grasp.period} Let $p$ and $q$ be two
positive integers. Let $A\in\mathbb{K}^{p\times\left(  p+q\right)  }$ be a
Zariski-generic matrix. Then, $\operatorname*{Grasp}\nolimits_{j}%
A=\operatorname*{Grasp}\nolimits_{p+q+j}A$ for every $j\in\mathbb{Z}$.
\end{remark}


\begin{remark}
\label{rmk.Grasp.antipode} Let $p$ and $q$ be two
positive integers. Let $A\in\mathbb{K}^{p\times\left(  p+q\right)  }$ be a
Zariski-generic matrix. Let $j\in\mathbb{Z}$. Then,%
\[
\left(  \operatorname*{Grasp}\nolimits_{j}A\right)  \left(  \left(
i,k\right)  \right)  =\dfrac{1}{\left(  \operatorname*{Grasp}%
\nolimits_{j+i+k-1}A\right)  \left(  \left(  p+1-i,q+1-k\right)  \right)  }.
\]

\end{remark}


Now, let us state the two facts which will combine to a proof of Theorem
\ref{thm.rect.ord}:

\begin{proposition}
\label{prop.Grasp.GraspR} Let $p$ and $q$ be two
positive integers. Let $A\in\mathbb{K}^{p\times\left(  p+q\right)  }$ be a
Zariski-generic matrix. Let $j\in\mathbb{Z}$. Then, $
\operatorname*{Grasp}\nolimits_{j}A=R_{\operatorname*{Rect}\left(  p,q\right)
}\left(  \operatorname*{Grasp}\nolimits_{j+1}A\right)  $.

\end{proposition}

\begin{proposition}
\label{prop.Grasp.generic} Let $p$ and $q$ be two
positive integers. For almost every (in the Zariski sense) reduced labelling
$f\in\mathbb{K}^{\widehat{\operatorname*{Rect}\left(  p,q\right)  }}$, there
exists a matrix $A\in\mathbb{K}^{p\times\left(  p+q\right)  }$ satisfying
$f=\operatorname*{Grasp}\nolimits_{0}A$.
\end{proposition}

Once these propositions are proven, Theorems \ref{thm.rect.ord}
and \ref{thm.rect.antip.general} easily follow (details are found in \cite{main}).

We will not dwell on the proof of Proposition \ref{prop.Grasp.generic}, it being
a rather technical ``triangularity'' argument (in the sense that the
construction of $f$ from $A$ can be done by recursively eliminating the values
of $f$ from a triangular, even if non-linear, system of equations). The details
are found in \cite[§15]{main}.

The proof of Proposition \ref{prop.Grasp.GraspR} is
computational (\cite[§14]{main}). It uses basic properties of determinants as well as what we call the \emph{Pl\"{u}cker-Ptolemy
relation}:

\begin{theorem}
\label{thm.pluecker.ptolemy} Let $A\in
\mathbb{K}^{u\times v}$ be a $u\times v$-matrix for some nonnegative integers
$u$ and $v$. Let $a$, $b$, $c$ and $d$ be four integers satisfying $a\leq b$
and $c\leq d$ and $b-a+d-c=u-2$. Then,%
\begin{align*}
&  \det\left(  A\left[  a-1:b\mid c:d+1\right]  \right)  \cdot\det\left(
A\left[  a:b+1\mid c-1:d\right]  \right) \\
&  +\det\left(  A\left[  a:b\mid c-1:d+1\right]  \right)  \cdot\det\left(
A\left[  a-1:b+1\mid c:d\right]  \right) \\
&  =\det\left(  A\left[  a-1:b\mid c-1:d\right]  \right)  \cdot\det\left(
A\left[  a:b+1\mid c:d+1\right]  \right)  .
\end{align*}

\end{theorem}

This theorem is a particular case of the Pl\"{u}cker relations, but can also be
proven in a very pedestrian way. It generalizes the well-known Dodgson condensation identity.

\section{Results for other posets}\label{sec:otherP}

In general, finite posets $P$ having a finite $\operatorname*{ord}\left(
R_{P}\right)  $ seem to be an exception rather than the rule. For instance,
$\operatorname*{ord}\left( R_{P}\right) = \infty$ when $P$ is the Boolean
lattice $[2] \times [2] \times
[2]$, as well as for some other relatively simple posets (even some ``slices''
of the otherwise well-behaved rectangles $\operatorname*{Rect}(p,q)$); see
\cite[§20]{main}. We have
not found any example of a non-graded poset $P$ for which $\operatorname*{ord}\left(
R_{P}\right) < \infty$.

There are, however, some more posets $P$ with finite $\operatorname*{ord}\left(
R_{P}\right)$ which are not covered by the skeletal and rectangle cases. Some
results are:

\begin{enumerate}
\item If $P$ is the subposet of $\operatorname*{Rect}\left(p,p\right)$ consisting of
all $\left(i,k\right)$ satisfying $i \leq k$ (that is, the left half of the
$p\times p$-square, including the diagonal, speaking in terms of Hasse diagrams),
then $\operatorname*{ord}\left(R_P\right) = 2p$. This is proven (\cite[§17]{main})
using a folding argument and the above results for rectangles.

\item If $P$ is the subposet of $\operatorname*{Rect}\left(p,p\right)$ consisting of
all $\left(i,k\right)$ satisfying $i+k > p+1$ (that is, the upper half of the
$p\times p$-square, excluding the diagonal, speaking in terms of Hasse diagrams),
then $\operatorname*{ord}\left(R_P\right) = 2p$ (if $p > 2$), and moreover,
$R_P^p$ amounts to reflecting the labelling across the vertical axis. This, again,
follows using (subtler) folding arguments (\cite[§18]{main}) from the rectangle case.
Analogous facts hold for the lower half of the square.
%
\item If $P$ is the subposet of $\operatorname*{Rect}\left(p,p\right)$ consisting of
all $\left(i,k\right)$ satisfying both $i+k > p+1$ and $i \leq k$ (this is a
rectangular triangle, in Hasse-diagram language), then we conjecture that
$\operatorname*{ord}\left(R_P\right) = p$ (for $p > 1$). We have a proof of this
for $p$ odd (\cite[§19]{main}); Nathan Williams has suggested a further conjectural
generalization to trapezoid-shaped posets.

\item It seems that root posets in ``coincidental types'' ($A$, $B$, $H_3$)
and minuscule heaps provide
examples of posets $P$ with finite $\operatorname*{ord}\left(R_P\right)$. More
precisely, the positive root poset in type $A_n$ is the poset $P$ of item 1 above
(for $p = n+1$), and the positive root poset in type $B_n$ is the poset $P$ of
item 3 above (for $p = 2n$). The ``positive root poset in type $H_3$'' (in Cuntz's sense)
satisfies $\operatorname*{ord}\left(R_P\right)=10$.
See \cite[§21]{main} for a brief review of this (largely mysterious)
connection.
%(However,
%$\operatorname*{ord}\left(R_P\right)=\infty$ for $P$ being the positive root poset
%in type $D_4$, so finite order of birational rowmotion does not seem to show the same
%type pattern as the Zamolodchikov periodicity conjecture!)
\end{enumerate}

\nocite{*}
\bibliographystyle{abbrvnat}
% use the following instead if you encounter problems 
%\bibliographystyle{alpha}
\bibliography{sample}
\label{sec:biblio}

\begin{thebibliography}{99999999}                                                                                         %


\bibitem[AKSch12]{ayyer-klee-schilling}Arvind Ayyer, Steven Klee, Anne
Schilling, \emph{Combinatorial Markov chains on linear extensions}, Journal
of Algebraic Combinatorics, September 2013, DOI 10.1007/s10801-013-0470-9.
\href{http://arxiv.org/abs/1205.7074v3}{Also available at {\tt arXiv:1205.7074v3}}.

\bibitem[AST11]{AST11}
D.~Armstrong, C.~Stump and H.~Thomas, \emph{A uniform bijection between
nonnesting and noncrossing partitions}, Trans. Amer. Math. Soc. 365 (2013),
pp. 4121--4151, DOI 10.1090/S0002-9947-2013-05729-7.
\href{http://arxiv.org/abs/1101.1277v2}{A preprint is available at {\tt arXiv:1101.1277v2}}.

\bibitem[BrSchr74]{brouwer-schrijver}Andries E. Brouwer and A. Schrijver,
\href{http://www.win.tue.nl/~aeb/preprints/zw24.pdf}{\emph{On the period of an operator, defined on antichains}, Math. Centr.
report ZW24, Amsterdam (Jun. 1974).}

\bibitem[CaFl95]{cameron-fon-der-flaass}Peter J. Cameron, Dmitry G.
Fon-der-Flaass, \href{http://www.sciencedirect.com/science/article/pii/0195669895900365}{\emph{Orbits of Antichains Revisited}, European Journal of
Combinatorics, vol. 16, Issue 6, November 1995, pp. 545--554.}

\bibitem[EiPr13]{einstein-propp}David Einstein, James Propp,
\emph{Combinatorial, piecewise-linear, and birational homomesy for products
of two chains}, \href{http://arxiv.org/abs/1310.5294v1}{{\tt arXiv:1310.5294v1} (preliminary version), October 20,
2013}.

\bibitem[Flaa93]{fon-der-flaass}Dmitry G. Fon-der-Flaass,
\href{http://www.sciencedirect.com/science/article/pii/S0195669883710036}{\emph{Orbits of
Antichains in Ranked Posets}, European Journal of Combinatorics, vol. 14,
Issue 1, January 1993, pp. 17--22.}

\bibitem[GrRo13]{main} Darij Grinberg and Tom Roby, 
\href{http://web.mit.edu/~darij/www/algebra/skeletal.pdf}{\emph{Iterative properties of birational rowmotion}, preprint}. Citations refer to version 2.0 (\href{http://arxiv.org/abs/1402.6178v2}{\tt arXiv:1402.6178v2} (not yet online, see MIT link)).

\bibitem[Pan08]{Pan08}
D.I. Panyushev, \emph{On orbits of antichains of positive roots}, Europ. J.
  Combin. \textbf{30} (2009), no.~2, pp. 586--594.
\href{arXiv:0711.3353v2}{Also available at {\tt arXiv:0711.3353v2}}.

%\bibitem[Post06]{postnikov}Alexander Postnikov, \emph{Total positivity,
%Grassmannians, and networks}, October 17, 2007 version.\newline%
%\texttt{\href{http://math.mit.edu/~apost/papers/tpgrass.pdf}{\texttt{http://math.mit.edu/\symbol{126}%
%apost/papers/tpgrass.pdf}}}

\bibitem[PrRo13]{propp-roby}James Propp and Tom Roby, \emph{
Homomesy in products of two chains}, \href{http://arxiv.org/abs/1310.5201v2}{\tt arXiv:1310.5201v2}.

%\bibitem[Rusk92]{ruskey}Frank Ruskey, \emph{Generating Linear Extensions of
%Posets by Transpositions}, Journal of Combinatorial Theory, vol. 54, Issue 1,
%January 1992, pp. 77--101.\newline%
%\texttt{\href{http://www.sciencedirect.com/science/article/pii/0095895692900678}{\texttt{http://www.sciencedirect.com/science/article/pii/0095895692900678}%
%}}

\bibitem[Sage08]{sage-combinat}The Sage-Combinat community,
\emph{Sage-Combinat: enhancing Sage as a toolbox for computer exploration in
algebraic combinatorics}, 2008.\texttt{
\href{http://combinat.sagemath.org}{\texttt{http://combinat.sagemath.org}}}

\bibitem[Stan11]{stanley-ec1}Richard Stanley, \href{http://math.mit.edu/~rstan/ec/ec1/}{\emph{Enumerative
Combinatorics, volume 1}, 2nd edition 2011}.

\bibitem[Stan86]{stanley-polytopes}Richard Stanley, \emph{Two Poset
Polytopes}, Discrete \& Computational Geometry, 1986, Volume 1, Issue 1, pp. 9--23.

\bibitem[StWi11]{striker-williams}Jessica Striker, Nathan Williams,
\emph{Promotion and Rowmotion}, European Journal of Combinatorics 33 (2012),
pp. 1919--1942, DOI 10.1016/j.ejc.2012.05.003. \href{http://arxiv.org/abs/1108.1172v3}{Also available as {\tt arXiv:1108.1172v3}}.

\bibitem[Volk06]{volkov}Alexandre Yu. Volkov, \emph{On the Periodicity
Conjecture for Y-systems}, Commun. Math. Phys. 276 (2007), pp. 509--517, DOI
10.1007/s00220-007-0343-y. \href{http://arxiv.org/abs/hep-th/0606094v1}{A
preprint is available as {\tt arXiv:hep-th/0606094v1}}.

%\bibitem[Will13]{williams-cataland}Nathan Williams, \emph{Cataland},
%dissertation at University of Minnesota, August 2013.\newline%
%\texttt{\href{https://conservancy.umn.edu/bitstream/159973/1/Williams_umn_0130E_14358.pdf}{\texttt{https://conservancy.umn.edu/bitstream/159973/1/Williams\_umn\_0130E\_14358.pdf}%
%}}
\end{thebibliography}


\end{document}
