%% The class cedram-ALCO is just a wrapper around amsart.cls (version 2)
%% implementing the layout of the journal, and some additionnal
%% administrative commands. 
%% You can place one option:
%% * "Unicode" if the file is UTF-8 encoded.
\documentclass[ALCO,Unicode,published]{cedram}

%% Here you might want to add some standard packages if those
%% functionnalities are required.
%\usepackage[matrix,arrow,tips,curve]{xy}
% ...
%\usepackage{amssymb}
%\usepackage{amsfonts}
%\usepackage{amsthm}
%\usepackage{amsmath}
\usepackage{amscd}
\usepackage{t1enc}
\usepackage[mathscr]{eucal}
\usepackage{indentfirst}
\usepackage{graphicx}
\usepackage{graphics}
\usepackage{pict2e}
\usepackage{epic}
\numberwithin{equation}{section}
%\usepackage[margin=2.9cm]{geometry}
%\usepackage[showframe]{geometry}
\usepackage{epstopdf} 
\usepackage{tikz}
\tikzstyle{w}=[circle, draw, fill=black, inner sep=0pt, minimum width=4pt]
\usepackage{transparent}
\usepackage{wasysym}
%\usepackage{enumerate}
%\usepackage{hyperref}
\usepackage{ytableau}

\usepackage{mathdots}
\usepackage{todonotes}
\usepackage{mathtools}

\usepackage{caption}

\colorlet{myGreen}{green!50!gray!120!}


%\theoremstyle{plain}
\equalenv{Th}{theo}%\newtheorem{Th}{Theorem}[section]
\equalenv{Lemma}{lemm}%\newtheorem{Lemma}[Th]{Lemma}
\equalenv{Cor}{coro}%\newtheorem{Cor}[Th]{Corollary}
\equalenv{Prop}{prop}%\newtheorem{Prop}[Th]{Proposition}

%\theoremstyle{definition}
\equalenv{Def}{defi}%\newtheorem{Def}[Th]{Definition}
\equalenv{Conj}{conj}%\newtheorem{Conj}[Th]{Conjecture}
%\newtheorem{?}[Th]{Problem}
\equalenv{Ex}{exam}%\newtheorem{Ex}[Th]{Example}

%\theoremstyle{remark}
\equalenv{Rem}{rema}%\newtheorem{Rem}[Th]{Remark}

\newcommand{\im}{\operatorname{im}}
\newcommand{\Hom}{{\rm{Hom}}}
\newcommand{\diam}{{\rm{diam}}}
\newcommand{\ovl}{\overline}
%\newcommand{\M}{\mathbb{M}}

\newcommand{\op}{\mathcal{O}(P)}
\newcommand{\cp}{\mathcal{C}(P)}
\newcommand{\ST}{ST}
\newcommand{\red}[1]{\textcolor{red}{#1}}

\newcommand{\parallelsum}{\:\ \mathclap{\|}\mathclap{-}\ \:}

\makeatletter
\newcommand\bigDiamond{\mathop{\mathpalette\bigDi@mond\relax}}
\newcommand\bigDi@mond[2]{%
  \vcenter{\hbox{\m@th
    \scalebox{\ifx#1\displaystyle 2\else1.2\fi}{$#1\Diamond$}%
  }}%
}

%% The production will anyway use amsmath (all ams utilities except
%% amscd for commutative diagrams which you need to load explicilty if
%% required), hyperref, graphicx, mathtools, enumitem...

%% User definitions if necessary...  Such definitions are forbidden
%% inside titles, abstracts or the bibliography.
\DeclarePairedDelimiter\abs{\lvert}{\rvert} %Something useful only for this sample's sake: you can erase this line in your file (or find it useful...)
%% The title of the paper: amsart's syntax. 
\title
%% The optionnal argument is the short version for headings.
[Rowmotion and the octahedron recurrence]
%% The mandatory argument is for the title page, summaries, headings
%% if optionnal void.
{Birational rowmotion and the octahedron recurrence}

%% Authors according to amsart's syntax + distinction between Given
%% and Proper names:
\author[\initial{J.} Johnson]{\firstname{Joseph} \lastname{Johnson}}
%\author[\initial{J.} \middlename{W.} Johnson]{\firstname{Joseph} \middlename{W.} \lastname{Johnson}}

%% Do not include any other information inside \author's argument!
%% Other author data have special commands for them:
\address{KTH Royal Institute of Technology\\ 
Department of Mathematics\\
Stockholm\\
114 28 (Sweden)}

%% Current address, if different from institutionnal address
%\curraddr{Coll\`ege Royal Henri-Le-Grand\\
%Prytan\'ee National Militaire\\
%72000 La Fl\`eche, Sarthe (France)}

%% e-mail address
\email{josjohn@kth.se}

%% possibly home page URL (not encouraged by journal's style)
%\urladdr{https://en.wikipedia.org/wiki/Marin\_Mersenne}

%% Authors according to amsart's syntax + distinction between Given
%% and Proper names:
\author[\initial{R.} \middlename{I.} Liu]{\firstname{Ricky} \middlename{Ini} \lastname{Liu}}

%% Do not include any other information inside \author's argument!
%% Other author data have special commands for them:
\address{University of Washington\\
Department of Mathematics\\
Seattle\\
WA 98195 (USA)}

%% Current address, if different from institutionnal address
% \curraddr{Coll\`ege Royal Henri-Le-Grand\\
% Prytan\'ee National Militaire\\
% 72000 La Fl\`eche, Sarthe (France)}

%% e-mail address
\email{riliu@uw.edu}

%% possibly home page URL (not encouraged by journal's style)
%\urladdr{https://en.wikipedia.org/wiki/Marin\_Mersenne}

%% Acknowledgements are not a footnote in
%% \author, but are given apart:
\thanks{R.\ I.\ Liu was partially supported by National Science Foundation grants DMS-1700302 and CCF-1900460.}


%% If co-authors exist, add them the same way, in alaphabetical order
%\author{\firstname{Joseph}  \lastname{Fourier}}
%\address{Universit\'e de  Grenoble\\
% Institut Moi-m\^eme\\
% BP74, 38402 SMH Cedex (France)}
%\email{fourier@fourier.edu.fr}

% Key words and phrases:
\keywords{rowmotion, RSK correspondence, octahedron recurrence, Stanley--Thomas words}
  

%% Mathematical classification (2010)
%% This will not be printed but can be useful for database search
\subjclass{05E18, 05A05}

\datepublished{2024-10-31}
\begin{document}
%% Abstracts must be placed before \maketitle
\begin{abstract}
We use the octahedron recurrence to give a simplified statement and proof of a formula for iterated birational rowmotion on a product of two chains, first described by Musiker and Roby. Using this, we show that weights of certain chains in rectangles shift in a predictable way under the action of rowmotion. We then define generalized Stanley--Thomas words whose cyclic rotation uniquely determines birational rowmotion on the product of two chains. We also discuss the relationship between rowmotion and birational RSK and give a birational analogue of Greene's theorem in this setting.
\end{abstract}


\maketitle

% First paragraph after a section is not indented. If there is text
% below the title before the first section, it should be unindented
% like this.

\section{Introduction}

For any poset $P$, \emph{(combinatorial) rowmotion} is the action on the set of order ideals of $P$ that sends $I$ to the ideal generated by the minimal elements of $P \setminus I$. This action is well studied in the dynamical algebraic combinatorics literature; for background on rowmotion, see \cite{strikerwilliams}. %Since rowmotion is a bijection of a finite sets, it is guaranteed to have a finite period. 
On certain classes of posets (triangles, skeletal posets, rectangles, root posets, and others), rowmotion has a surprisingly small period, and it also sometimes exhibits other interesting phenomena such as homomesy and cyclic sieving: see \cite{einsteinpropp1,hopkins3,josephroby1,musikerroby,propproby,thomaswilliams}.

Rowmotion also has a description in terms of local, involutive transformations called \emph{toggles} \cite{cameronfonderflaass}. Reinterpreting these toggles as acting on lattice points in $\mathbb R^n$, one can lift toggles and hence rowmotion to piecewise-linear maps. One can then lift these further to the birational realm by replacing $\max$ with addition, addition with multiplication, and subtraction with division \cite{einsteinpropp2,einsteinpropp1}. Surprisingly, many results from the combinatorial level remain true on the birational level. For instance, for some posets, the period of birational rowmotion remains small, even though a priori it need not even be finite \cite{grinbergroby2,grinbergroby1}.

The main poset of interest in this paper is the product of two chains, called the \emph{rectangle poset}. Grinberg and Roby \cite{grinbergroby2} show that birational rowmotion on the $r \times s$ rectangle has the same order as combinatorial rowmotion, $r+s$.  Musiker and Roby~\cite{musikerroby} then give an explicit combinatorial formula for all powers of birational rowmotion on rectangles in terms of nonintersecting lattice paths. However, their impressive formula is notationally dense, and their proof requires a rather intricate bijection on lattice paths. The main result of this paper is a simplified statement and proof of Musiker and Roby's iterated birational rowmotion formula for rectangles. (This essentially gives a new proof of periodicity of birational rowmotion on rectangles.) Our proof relies mainly on the connections between rowmotion, the octahedron recurrence, the solid minors of a matrix, and nonintersecting lattice paths via the Lindstr\"om--Gessel--Viennot Lemma.

We also touch upon a number of topics related to this work. For instance, associated to any antichain of the $r \times s$ rectangle poset is a certain $0/1$-sequence of length $r+s$ called the \emph{Stanley--Thomas word}. Rowmotion on order ideals equivariantly induces a rowmotion action on antichains, which cyclically shifts the Stanley--Thomas word \cite{propproby,stanley1}. Previously, the Stanley--Thomas word has been defined in the birational realm to prove homomesy results \cite{josephroby1}, but this word alone is not enough to uniquely specify a general labeling of a rectangle. In this article, we define \emph{generalized Stanley--Thomas words} in terms of certain sums of weights of chains and show that birational rowmotion is the unique function that cyclically shifts all of them. 

Finally, we discuss the relationship between the birational version of the \emph{Robinson--Schensted--Knuth (RSK) correspondence} \cite{danilovkoshevoy, noumiyamada} and rowmotion by defining birational RSK in terms of toggles. We use the iterated birational rowmotion formula to show that this definition satisfies a birational version of Greene's theorem and also compare it to existing constructions in the literature.

\phantomsection
\subsection*{Road map of the paper} In Section~\ref{section:background} we review background on birational rowmotion, the octahedron recurrence, and the relationship between the two. In Section~\ref{section:rowmotiononrectangles} we state and prove our main result, the iterated birational rowmotion formula on rectangles, using the Lindstr\"om--Gessel--Viennot Lemma and the octahedron recurrence. Using this framework we prove a chain shifting lemma in Section~\ref{section:chainshifting} and define generalized Stanley--Thomas words. Finally in Section~\ref{section:greenestheorem} we define birational RSK and prove a birational analogue of Greene's theorem, which we then use to show that the cyclic shifting of the generalized Stanley--Thomas words uniquely determines birational rowmotion.

\section{Background} \label{section:background}

\subsection{Posets and rectangles}
\label{subsection:posets}

We first review some basic terminology about posets. Typically we represent a finite poset $P=(P, \leq)$ by its \emph{Hasse diagram}, a directed graph with vertex set $P$ and edges $x \to y$ when $y$ covers $x$, which we denote $x \lessdot y$. Since all edges are directed upward in the Hasse diagram, we omit the direction in figures.

\begin{Def}
Let $P$ be a poset. A \emph{chain} in $P$ is a sequence of elements $p_1 < p_2 < \dots < p_k$. An \emph{antichain} in $P$ is a set $A \subseteq P$ such that for any distinct $p,q \in A$, neither $p \leq q$ nor $q \leq p$.
\end{Def}

The antichains are related to the order ideals (and order filters) of a poset. 


\begin{Def} Let $P$ be a finite poset.
\begin{enumerate}
    \item An \emph{order ideal} of $P$ is a set $I \subseteq P$ such that if $p \leq q$ in $P$ and $q \in I$, then $p \in I$. %We will denote by $\Lambda_q = \{p \mid p \leq q\}$ the \emph{principal order ideal} generated by $q$.
    \item An \emph{order filter} of $P$ is a set $F \subseteq P$ such that if $p \leq q$ in $P$ and $p \in F$, then $q \in F$. %We will denote by $V_p = \{q \mid q \geq p\}$ the \emph{principal order filter} generated by $p$.
    \item An \emph{interval} of $P$ is a subset of the form $[p,q]=\{ x \mid p \leq x \leq q \}$.
\end{enumerate}
\end{Def}

Let $[r]$ be the chain with $r$ elements $1 < 2 < \cdots < r$. Of particular interest is the \emph{rectangle poset} given by the Cartesian product of two chains $R = [r] \times [s]$. We will distinguish between a rectangle poset and general posets by using $R$ exclusively for the rectangle. 

\begin{Def}
Let $R = [r] \times [s]$ be a rectangle poset.
\begin{itemize}
    \item For fixed $i$, the $i$th \emph{row} of $R$ is the set of all elements in $R$ of the form $(i,j)$. 
    \item For fixed $j$, the $j$th \emph{column} of $R$ is the set of all elements in $R$ of the form $(i,j)$. 
    \item The $k$th \emph{rank} of $R$ is the set of all elements $(i,j)$ such that $i+j=k$.
    \item The $k$th \emph{file} of $R$ is the set of all elements $(i,j)$ such that $j-i=k$.
\end{itemize}
\end{Def}
We will typically draw rectangles oriented as in Figure~\ref{squareposet}, so that rows run southwest to northeast, columns run southeast to northwest, ranks are aligned horizontally, and files are aligned vertically. (As a word of caution, note that the minimum element has rank $2$.)

\begin{figure}
\captionsetup{justification=centering}
\begin{tikzpicture}[rotate=45,scale=1.1]
%ROWS
\draw (0,0)--(2,0);
\draw (0,1)--(2,1);
%COLUMNS
\draw (0,0)--(0,1);
\draw (1,0)--(1,1);
\draw (2,0)--(2,1);

%POSET NODES
\draw [fill=black] (0,0) circle [radius=0.1cm];
\draw [fill=black] (1,0) circle [radius=0.1cm];
\draw [fill=black] (2,0) circle [radius=0.1cm];

\draw [fill=black] (0,1) circle [radius=0.1cm];
\draw [fill=black] (1,1) circle [radius=0.1cm];
\draw [fill=black] (2,1) circle [radius=0.1cm];

\node at (0.4,-0.4) {$(1,1)$};
\node at (1.4,-0.4) {$(1,2)$};
\node at (2.4,-0.4) {$(1,3)$};

\node at (0.4,0.6) {$(2,1)$};
\node at (1.4,0.6) {$(2,2)$};
\node at (2.4,0.6) {$(2,3)$};
\end{tikzpicture}

\caption{The rectangle $[2] \times [3]$.}
 \label{squareposet}
\end{figure}

\subsection{Rowmotion}

An important object of study in dynamical algebraic combinatorics is a certain dynamical process on order ideals called combinatorial rowmotion.

\begin{Def}
Let $I$ be an order ideal of $P$. \textit{Combinatorial rowmotion} is the map $\rho$ that sends $I$ to the order ideal generated by the minimal elements of $P \setminus I$.
\end{Def}

Cameron and Fon-der-Flaass \cite{cameronfonderflaass} give another description of rowmotion in terms of \textit{combinatorial toggles}. Let $J(P)$ denote the set of order ideals of $P$. For each $p \in P$, we associate a \emph{toggle map} $t_p \colon J(P) \to J(P)$ by
\[t_p(I) = \begin{cases} I \cup \{p\} &\text{ if } p \not\in I \text{ and } I \cup \{p\} \in J(P), \\
I \setminus \{p\} &\text{ if } p \in I \text{ and } I \setminus \{p\} \in J(P), \\
I &\text{ otherwise.} \end{cases}\]
Combinatorial rowmotion can then be defined as the composition of toggles on $P$ in the order of a linear extension $\mathcal L \colon P \to [n]$ (where $n=|P|$) from top to bottom, that is,
\[\rho = t_{\mathcal{L}^{-1}(1)} \circ \dots \circ t_{\mathcal{L}^{-1}(n)}.\]
We note that $t_p \circ t_q = t_q \circ t_p$ if and only if $p$ and $q$ do not form a cover relation. Consequently this description is independent of the choice of linear extension.

In \cite{stanley1}, Stanley gives a bijection (also discovered independently by Thomas) between the order ideals of $R = [r] \times [s]$ and 0/1-sequences with $r$ zeroes and $s$ ones.

\begin{Def}
Let $A$ be an antichain of $R = [r] \times [s]$. The \emph{Stanley--Thomas word} of $A$ is $w(A) = (w_1, \dots, w_{r+s})$, where

\[w_i = \begin{cases} 1 &\text{ if } 1\leq i \leq r \text{ and } A \text{ has an element in row } i, \\ 
1 &\text{ if } r+1 \leq i \leq r+s \text{ and } A \text{ has no element in column } i-r, \\ 
0 &\text{ otherwise.} \end{cases}\]
\end{Def}

Rowmotion performs a cyclic shift of the Stanley--Thomas word \cite{propproby}. Since the map $w$ is a bijection, this gives a simple proof of the following result, originally proved by %Fon-der-Flaass \cite{fonderflaass}.
Brouwer and Schrijver \cite{brouwerschrijver}.

\begin{Th}[\cite{brouwerschrijver}]
The order of $\rho$ on $R=[r] \times [s]$ is $r+s$.
\end{Th}

Note that $r+s$ is one more than the number of distinct ranks of $R$. This is the smallest possible order that rowmotion can have on a graded poset: iteratively applying rowmotion to the empty order ideal simply adds one rank of elements at a time to the order ideal until arriving at the entire poset, which is then mapped back to the empty order ideal.

\subsection{Piecewise-linear rowmotion}

In \cite{stanley2}, Stanley defines two polytopes related to a finite poset.

\begin{Def}
Let $P$ be a finite poset. 

\begin{enumerate}
    \item The \emph{order polytope} $\op \subseteq \mathbb{R}^P$ is the set of all $x \in \mathbb{R}^P$ satisfying the inequalities $0 \leq x_p \leq 1$ for all $p \in P$, and $x_p \leq x_q$ for all $p,q \in P$ satisfying $p \leq q$.
    \item The \emph{chain polytope} $\cp \subseteq \mathbb{R}^P$ is the set of all $x \in \mathbb{R}^P$ satisfying  the inequalities $x_p \geq 0$ for all $p \in P$, and $\sum_{p \in C} x_p \leq 1$ for all (maximal) chains $C \subseteq P$.
\end{enumerate}
\end{Def}
The vertices of $\op$ and $\cp$ are the indicator vectors of the order filters and antichains of $P$, respectively. We may also identify the vertices of $\op$ with the order ideals of $P$ by complementation.

In \cite{stanley2}, Stanley defines a piecewise-linear, continuous, and volume-preserving bijection $\phi \colon \op \to \cp$ called the \emph{transfer map}, defined by
\[\phi(x)_p = x_p - \max\limits_{q \lessdot p} x_q,\]
where we interpret an empty $\max$ as $0$.
The inverse of this map is given by
\[\phi^{-1}(x)_p = \max\limits_{c_1 < c_2 < \dots < c_k = p} \left( \sum\limits_{i=1}^k x_{c_i} \right).\]
The transfer map can be thought of as a piecewise-linear extension of the map that sends an order filter to its minimal elements.

Combinatorial rowmotion permutes order ideals and so can also be thought of as a permutation of the vertices of $\op$. As is the case with the transfer map, there is a natural piecewise-linearization of this bijection described by Einstein and Propp \cite{einsteinpropp1}.

\begin{Def}
The \textit{piecewise-linear toggle} on the order polytope $\op$ corresponding to an element $p \in P$ is the map $t_p\colon \op \to \op$ that changes the $p$th coordinate by
\[x_p \mapsto \min\limits_{q \gtrdot p} x_q + \max\limits_{q \lessdot p} x_q - x_p\]
and fixes all other coordinates, where an empty $\min$ is interpreted as $1$ and an empty $\max$ is interpreted as $0$.
\end{Def}
(We will abuse notation and use the same symbol for combinatorial toggles and piecewise-linear toggles.)
Note that $t_p$ only depends on the coordinates in the neighborhood of $p \in P$ in the Hasse diagram. Consequently for $p,q \in P$, $t_p \circ t_q = t_q \circ t_p$ if and only if neither $p \lessdot q$ nor $p \gtrdot q$ as in the combinatorial realm.

We then define \textit{piecewise-linear rowmotion} $\rho\colon \op \to \op$ using piecewise-linear toggles by
\[\rho = t_{\mathcal{L}^{-1}(1)} \circ \cdots \circ t_{\mathcal{L}^{-1}(|P|)},\]
where $\mathcal{L}$ is any linear extension of $P$.

\subsection{Birational rowmotion}

Piecewise-linear rowmotion can be lifted even further to a birational analogue that uses addition, multiplication, and division in place of $\max$, addition, and subtraction, respectively. This lifting process is called \emph{detropicalization}. (See \cite{einsteinpropp2,einsteinpropp1,noumiyamada} for more detailed discussion.) The functions resulting from detropicalization are generally \emph{subtraction-free} and therefore well-defined on positive labelings of $P$.

As an example, the \emph{birational transfer map} $\phi$ acts on positive labelings $x \in \mathbb R^P_{>0}$ via coordinate functions
\[\phi(x)_p = \frac{x_p}{\sum\limits_{q \lessdot p} x_q}\]
where an empty sum is interpreted as $1$.

Since $\min(a,b) = -\max(-a,-b)$, detropicalizing $\min$ yields the \textit{parallel sum}~$\parallelsum$ defined by
\[a \parallelsum b = \frac{1}{\frac{1}{a} + \frac{1}{b}} = \frac{ab}{a+b}.\]
Parallel sum is associative and commutative. For a finite multiset $S \subseteq \mathbb{R}_{>0}$, we denote the parallel sum of all elements in $S$ by $\sideset{}{^{\parallelsum}} \sum\limits_{s \in S} s$.


\begin{Def}
The \textit{birational toggle} on $\mathbb{R}^{P}_{>0}$ corresponding to an element $p \in P$ is the birational map $t_p\colon \mathbb{R}^{P}_{>0} \to \mathbb{R}^{P}_{>0}$ that changes the $p$th coordinate by
\[x_p \mapsto \left( \sideset{}{^{\parallelsum}} \sum\limits_{q \gtrdot p} x_q \right) \left( \sum\limits_{q \lessdot p} x_q \right) \cdot \frac{1}{x_p}\]
and fixes all other coordinates, where an empty sum or parallel sum is interpreted as $1$.
\end{Def}
(We again abuse notation by using the same notation for birational toggles as piecewise-linear toggles.) Similarly to piecewise-linear rowmotion, we define \textit{birational rowmotion} as
\[\rho = t_{\mathcal{L}^{-1}(1)} \circ \cdots \circ t_{\mathcal{L}^{-1}(|P|)}\]
for any linear extension $\mathcal{L}$ of $P$. From the birational setting, we can obtain the piecewise-linear analogue via a \textit{valuation} or \emph{tropicalization}: see, for instance, \cite{einsteinpropp2,einsteinpropp1}. 

For any poset, one can compute birational rowmotion in terms of the dual transfer map.

\begin{Def}
Let $P$ be a poset and $x \in \mathbb{R}_{>0}^{P}$ be a labeling. The \emph{dual transfer map} is the birational function $\phi^*\colon\mathbb{R}_{>0}^{P} \to \mathbb{R}_{>0}^{P}$ with coordinate functions
\[\phi^*(x)_p = \frac{x_p}{\sum\limits_{q \gtrdot p} x_q}\]
for all $p \in P$, where an empty sum is interpreted as $1$.
\end{Def}

In other words, $\phi^*$ acts on labelings of $P$ in the same way that $\phi$ acts on the associated labeling of the dual of $P$. 

The following lemma is due to Einstein and Propp (see for instance \cite{einsteinpropp2,josephroby2}). We include a short proof for completeness.

\begin{Lemma} \label{lemma:dualtransfer}
Let $P$ be a finite poset. Then for any $x \in \mathbb{R}_{>0}^{P}$ and $p \in P$,
\[ \rho \circ \phi^{-1}(x)_p = \frac{1}{\left(\phi^*\right)^{-1}(x)_p}.\]
\end{Lemma}
\begin{proof}
Let $y = \phi^{-1}(x)$ and $z = (\phi^*)^{-1}(x)$. For any $p \in P$, suppose that $\rho(y)_q = \frac{1}{z_q}$ for all $q > p$. When applying the toggle at $p$ in the computation of $\rho(y)$, the elements at or below $p$ are labeled as in $y$ while those above $p$ are labeled as in $\rho(y)$. Hence by the definition of $t_p$,
\[
    \rho(y)_p =  \left( \sideset{}{^{\parallelsum}} \sum\limits_{q \gtrdot p} \frac{1}{z_q} \right) \left(\sum\limits_{q \lessdot p} y_q \right) \cdot \frac{1}{y_p}  = \frac{1}{\sum\limits_{q \gtrdot p}z_q} \cdot \frac{1}{x_p} = \frac{1}{z_p}.
\]
The result follows easily by induction starting at the top of $P$.
\end{proof}

Computing iterated applications of rowmotion is more difficult. However, one can sometimes prove results about rowmotion using an associated combinatorial construction instead. As mentioned previously, one such example is the Stanley--Thomas word, which lifts to the birational level.

\begin{Def}
Let $R = [r] \times [s]$. The \emph{birational Stanley--Thomas word} $w$ for $x$ is the word of length $r+s$ defined by
\[w_i = \begin{cases} \prod\limits_{j=1}^s x_{ij} &\text{ if } 1\leq i \leq r, \\ \prod\limits_{j=1}^r x_{j,i-r}^{-1} &\text{ if } r+1\leq i \leq r+s.\end{cases}\]
\end{Def}

In \cite{josephroby1} it is shown that $\phi \circ \rho \circ \phi^{-1}$ cyclically shifts the birational Stanley--Thomas word. Though this is not sufficient to show that the order of birational rowmotion on the product of two chains has finite order, it can be used to extend other results (such as instances of homomesy) to the birational level. In Section \ref{section:chainshifting} we  will define a collection of \emph{generalized Stanley--Thomas words}, and in Section \ref{section:greenestheorem} we show that the cyclic rotation of these words uniquely determines rowmotion.

\subsection{Dodgson condensation and the octahedron recurrence} \label{sec:octahedron}

Given a matrix $A=(a_{ij})_{i,j=1}^{n}$, let $A_{ij}^{(k)}$ denote the $k \times k$ submatrix of $A$ formed by the intersection of rows $i$ through $i+k-1$ and columns $j$ through $j+k-1$ whenever $1 \leq i,j \leq n-k+1$. These minors satisfy the following algebraic relation known as the \emph{Desnanot-Jacobi identity}, which forms the basis of a recursive algorithm for computing the determinant of a matrix called \emph{Dodgson condensation}.

\begin{Prop} \label{prop:dodgson}
%desnanot-jacobi identity
For $k \geq 0$,
\[\det(A_{ij}^{(k+1)}) \det(A_{i+1,j+1}^{(k-1)})=\det(A_{ij}^{(k)})\det(A_{i+1,j+1}^{(k)})-\det(A_{i,j+1}^{(k)})\det(A_{i+1,j}^{(k)}).\]
(By convention, we set $\det(A_{ij}^{(0)})=1$ and $\det(A_{ij}^{(-1)})=0$ for all integers $i$ and $j$.)
\end{Prop}

We visualize this relation by placing the values $\det(A_{ij}^{(k)})$ into a three-dimensional array. In all figures containing such an array, we place the entries $\det(A_{ij}^{(k)})$ at height $k$ so that, for $k>1$, $\det(A_{ij}^{(k)})$ lies directly above the center of the submatrix at height $1$ for which it is the determinant. See Figure~\ref{fig:octahedron}.

%Consider the lattice of points $(x,y,z)$ such that $x \equiv y \equiv 0$ mod $2$. If $A \in \mathbb{R}^{r+1 \times s+1}$, define a function $f$ on the subset of the lattice of points (2i, 2j, k) where $0 \leq i \leq r$, $0 \leq j \leq s$, and $0 \leq k \leq \min(r,s)$ by setting
%\begin{align*}
%    f(2i,2j,k) &= \det(A_{ij}^{(k)}).
%\end{align*}
%Visually the point $(x,y,z)$ lies above the center of the submatrix for which $f(x,y,z)$ is the determinant. In Figure~\ref{fig:octahedron}, the top of the pyramid is the determinant of the $2 \times 2$ matrix beneath it.


%Given a matrix $A = (a_{ij})_{i,j = 0}^{r,s}$, we initialize a function on the lattice with $f(2x,2y,0) = 1$ and $f(2i+1, 2j+1, 1) = a_{ij}$. 


%\begin{Def}
%The \emph{Dodgson condensation} is the following recurrence relation: 

%\[f(x-1,y-1,z+1) = \frac{f(x,y,z)f(x-2,y-2,z) - f(x-2,y,z)f(x,y-2,z)}{f(x-1,y-1,z-1)}.\]
%\end{Def}

%Applying Dodgson condensation assigns values to points in a pyramid shape. The value of $f(x,y,z)$ is the solid minor given by the $a_{ij}$ satisfying $\frac{x-z}{2} \leq i \leq \frac{x+z}{2}-1$ and $\frac{y-z}{2} \leq j \leq \frac{y+z}{2}-1$. 



\begin{figure}
\begin{tikzpicture}[scale = 0.5]

%DOTTED LINES
\draw [dotted] (0,0)--(-4,1)--(-2,2)--(2,1)--cycle;
\draw [dotted] (-0.5,3.5)--(-2.5,4)--(-1.5,4.5)--(0.5,4)--cycle;

\draw [dotted] (0,0)--(-1,7);
\draw [dotted] (-4,1)--(-1,7);
\draw [dotted] (-2,2)--(-1,7);
\draw [dotted] (2,1)--(-1,7);

\draw [red, thick] (-1,1)--(-2.5,4)--(-1,7)--(0.5,4)--cycle;
\draw [red, thick] (-1,1)--(-0.5,3.5)--(-1,7);
\draw [red, thick] (-2.5,4)--(-0.5,3.5)--(0.5,4);

\draw [->] (0,0)--(-1.88,0.47);
\draw [->] (0,0)--(0.9,0.45);
\draw [->] (0,0)--(-0.45,3.36);

\node at (0.7,-0.1) {$i$};
\node at (-1.05,-0.15) {$j$};
\node at (0.3,1) {$k$};
\draw [red, dashed, thick](-1,1)--(-1.5,4.5)--(-1,7);
\draw [red, dashed, thick] (-2.5,4)--(-1.5,4.5)--(0.5,4);


%LAYER 1
\draw [fill=black] (0,0) circle [radius=0.08cm];
\draw [fill=black] (-2,0.5) circle [radius=0.08cm];
\draw [fill=black] (-4,1) circle [radius=0.08cm];

\draw [fill=black] (1,0.5) circle [radius=0.08cm];
\draw [fill=black] (-1,1) circle [radius=0.08cm];
\draw [fill=black] (-3,1.5) circle [radius=0.08cm];

\draw [fill=black] (2,1) circle [radius=0.08cm];
\draw [fill=black] (0,1.5) circle [radius=0.08cm];
\draw [fill=black] (-2,2) circle [radius=0.08cm];

%LAYER 2
\draw [fill=black] (-0.5,3.5) circle [radius=0.08cm];
\draw [fill=black] (-2.5,4) circle [radius=0.08cm];

\draw [fill=black] (0.5,4) circle [radius=0.08cm];
\draw [fill=black] (-1.5,4.5) circle [radius=0.08cm];

%LAYER 3
\draw [fill=black] (-1,7) circle [radius=0.08cm];

\begin{scope}[shift={(9,-1)}]
    \draw [red, thick] (-2,2)--(-3.5,5)--(-2,8)--(-0.5,5)--cycle;
    \draw [red, thick] (-2,2)--(-1.5,4.5)--(-2,8);
    \draw [red, thick] (-3.5,5)--(-1.5,4.5)--(-0.5,5);
    \draw [red, dashed, thick](-2,2)--(-2.5,5.5)--(-2,8);
    \draw [red, dashed, thick] (-3.5,5)--(-2.5,5.5)--(-0.5,5);
    \node at (-1.2,4.3) {$x$};
    \node at (-2.2,5.2) {$x'$};
    \node at (-2.4,2) {$a$};
    \node at (-0.1,5) {$b$};
    \node at (-4,5) {$c$};
    \node at (-1.6,8) {$d$};
    \draw [fill=black] (-2,2) circle [radius=0.08cm];
    \draw [fill=black] (-1.5,4.5) circle [radius=0.08cm];
    \draw [fill=black] (-3.5,5) circle [radius=0.08cm];
    \draw [fill=black] (-0.5,5) circle [radius=0.08cm];
    \draw [fill=black] (-2.5,5.5) circle [radius=0.08cm];
    \draw [fill=black] (-2,8) circle [radius=0.08cm];
    \node at (-2,1){$xx'=ad+bc$};
\end{scope}

\end{tikzpicture}
\caption{The coordinate system we will use for figures depicting three-dimensional arrays $(M_{ij}^{(k)})$. (Note that the $k$ direction does not point vertically but rather along the edge of the pyramid.) 
The octahedron recurrence involves the vertices of translations of the octahedron as shown on the right.
}
\label{fig:octahedron}
\end{figure}


Proposition~\ref{prop:dodgson} then implies that the entries $M_{ij}^{(k)} = \det(A_{ij}^{(k)})$ satisfy the following \emph{octahedron recurrence}:
\[M_{ij}^{(k)}M_{i+1,j+1}^{(k)} = M_{i+1,j+1}^{(k-1)}M_{ij}^{(k+1)}+M_{i+1,j}^{(k)}M_{i,j+1}^{(k)}.\]
The elements in this relation lie at the vertices of an octahedron that is a translation of the one shown in Figure~\ref{fig:octahedron}. By convention, we extend the array $M=(M_{ij}^{(k)})$ to all integers $i$, $j$, and $k$ by setting any undefined values equal to $0$, which does not violate the octahedron recurrence.

%\[f(x,y,z) = \frac{f(x,y,z-1)f(x-2,y-2,z+1)+f(x-2,y,z)f(x,y-2,z)}{f(x-2,y-2,z)}.\]

%\[f(x,y,z) = \frac{f(x-1,y-1,z+1)f(x-1,y-1,z-1) + f(x-2,y,z)f(x,y-2,z)}{f(x-2,y-2,z)}.\]

%For any octahedron shape, if we know 5 of the values of $f$, then we can compute the 6th by solving for it in the Dodgson condensation formula.  Solving for $f(x,y,z)$ yields
%\[f(x,y,z) = \frac{f(x-1,y-1,z+1)f(x-1,y-1,z-1) + f(x-2,y,z)f(x,y-2,z)}{f(x-2,y-2,z)}.\]
%which is called the \emph{octahedron recurrence}. In TODO:CITE HOPKINS, Hopkins used the octahedron recurrence to prove a special case of the rowmotion formula. 

We now demonstrate the known relationship between toggles and the octahedron recurrence appearing in  \cite{grinbergroby2}. A visualization of this lemma is shown in Figure~\ref{fig:toggle}. If part of the rectangle poset is labeled via the quotients $z_{ij}^{(k)}$ as shown, then Lemma~\ref{lemma:arraytoggle} shows that a toggle at $(i,j)$ transforms $z_{ij}^{(k-1)}$ to $z_{ij}^{(k)}$.

\begin{Lemma}\label{lemma:arraytoggle}
Suppose $M = (M_{ij}^{(k)})$ is an array of indeterminates satisfying the octahedron recurrence, and let $z_{ij}^{(k)} = \frac{M_{k+2,i+k+1}^{(j-1)}}{M_{k+1,i+k+1}^{(j)}}$.
Then as rational functions in the entries of $M$, \[z_{ij}^{(k)} = \frac{(z_{i,j-1}^{(k)}+z_{i-1,j}^{(k)})(z_{i+1,j}^{(k-1)}\parallelsum z_{i,j+1}^{(k-1)})}{z_{ij}^{(k-1)}}.\]



%Let $R = [0,r] \times [0,s]$ and let $z \in \mathbb{R}_{>0}^{R}$ be a positive labeling of $R$. 


%If a function $f$ of the form described above satisfies the octahedron recurrence and if 
%\begin{align*}
%    &z_{i+1,j} = \frac{f(2,2i+4,j)}{f(0,2i+4,j+1)} & &z_{i,j+1} = \frac{f(2,2i+2,j+1)}{f(0,2i+2,j+2)} \\
%    & &z_{ij} = \frac{f(2,2i+2,j)}{f(0,2i+2,j+1)} \\
%    &z_{i,j-1} = \frac{f(4,2i+4,j-1)}{f(2,2i+4,j)}& &z_{i-1,j} = \frac{f(4,2i+2,j)}{f(2,2i+2,j+1)} \\
%\end{align*}
%\noindent then,
%\[t_{ij}(z)_{ij} = \frac{f(4,2i+4,j)}{f(2,2i+4,j+1)}.\]
\end{Lemma}




\begin{figure}
\begin{tikzpicture}[scale = 0.6]

\draw [red, thick] (-2,2)--(-3.5,5)--(-2,8)--(-0.5,5)--cycle;
\draw [red, thick] (-2,2)--(-1.5,4.5)--(-2,8);
\draw [red, thick] (-3.5,5)--(-1.5,4.5)--(-0.5,5);
\draw [red, dashed, thick](-2,2)--(-2.5,5.5)--(-2,8);
\draw [red, dashed, thick] (-3.5,5)--(-2.5,5.5)--(-0.5,5);

\draw [blue, thick] (-3.5,5)--(-5,8)--(-3.5,11)--(-2,8)--cycle;
\draw [blue, thick] (-3.5,5)--(-3,7.5)--(-3.5,11);
\draw [blue, thick] (-5,8)--(-3,7.5)--(-2,8);
\draw [blue, dashed, thick](-3.5,5)--(-4,8.5)--(-3.5,11);
\draw [blue, dashed, thick] (-5,8)--(-4,8.5)--(-2,8);

\draw [green, thick] (-1.5,4.5)--(-3,7.5);
\draw [black, thick] (-2.5,5.5)--(-4,8.5);

%LAYER 1
\draw [fill=black] (-2,2) circle [radius=0.08cm];

%LAYER 2
\draw [fill=black] (-1.5,4.5) circle [radius=0.08cm];
\draw [fill=black] (-3.5,5) circle [radius=0.08cm];

\draw [fill=black] (-0.5,5) circle [radius=0.08cm];
\draw [fill=black] (-2.5,5.5) circle [radius=0.08cm];

%LAYER 3
\draw [fill=black] (-3,7.5) circle [radius=0.08cm];
\draw [fill=black] (-5,8) circle [radius=0.08cm];

\draw [fill=black] (-2,8) circle [radius=0.08cm];
\draw [fill=black] (-4,8.5) circle [radius=0.08cm];

%LAYER 4
\draw [fill=black] (-3.5,11) circle [radius=0.08cm];

\node at (-1.2,4.3) {$x$};
\node at (-2.2,5.2) {$x'$};

\node at (-2.6,7.3) {$y$};
\node at (-3.55,8.8) {$y'$};

\node at (-2.4,2) {$a$};
\node at (-0.1,5) {$b$};
\node at (-4,5) {$c$};
\node at (-1.6,8) {$d$};
\node at (-5.4,8) {$e$};
\node at (-3.1,11) {$f$};

\end{tikzpicture}
\begin{tikzpicture}
\transparent{0.0}
\draw (0,-2.7)--(0,2.7);
\transparent{1.0}

\draw (-1,-1)--(1,1);
\draw (-1,1)--(1,-1);

\draw [fill=black] (-1,-1) circle [radius=0.1cm];
\draw [fill=black] (1,-1) circle [radius=0.1cm];

\draw [fill=black] (0,0) circle [radius=0.1cm];

\draw [fill=black] (-1,1) circle [radius=0.1cm];
\draw [fill=black] (1,1) circle [radius=0.1cm];

\node at (-2.05,-1) {$z_{i,j-1}^{(k)} = \frac{a}{c}$};
\node at (2.05,-1) {$z_{i-1,j}^{(k)} = \frac{b}{d}$};

\node at (2.25,0) {$z_{i,j}^{(k-1)} = \frac{x}{y}\to z_{i,j}^{(k)} = \frac{x'}{y'}$};

\node at (-2.05,1) {$z_{i+1,j}^{(k-1)} = \frac{c}{e}$};
\node at (2.05,1) {$z_{i,j+1}^{(k-1)} = \frac{d}{f}$};
\end{tikzpicture}
\caption{The relationship between the octahedron recurrence and birational toggles as described in Lemma~\ref{lemma:arraytoggle}. Two labelings of the poset by quotients of entries in the octahedron recurrence are related by a birational toggle at the central element.}
\label{fig:toggle}
\end{figure}

\begin{proof} For ease of notation, we relabel the relevant part of the array as in Figure~\ref{fig:toggle}. (For instance, $x = M_{k+1,i+k}^{(j-1)}$ and $y = M_{k,i+k}^{(j)}$, so $z_{ij}^{(k-1)} = \frac{x}{y}$.) Applying the octahedron recurrence to the two octahedra shown and dividing gives
%We will show that if the array satisfies the octahedron recurrence, then $t_{ij}(z)_{ij} = \frac{x'}{y'}$. Indeed: %Thus applying rowmotion gives the labeling stored in the edges after shifting by the vector (2,2,0).
%Let $z \in \mathbb{R}_{>0}^{|R|}$. 
%Given a portion of the array as shown in Figure~\ref{fig:toggle}, consider a point $z \in \mathbb{R}_{>0}^{|R|}$ labeled by:
%\begin{align*}
%    z_{i+1,j} &= \tfrac{c}{e} \\
%    z_{i,j+1} &= \tfrac{d}{f} \\
%    z_{i,j} &= \tfrac{x}{y} \\
%    \rho^{-1}(z)_{i,j-1} = \tfrac{a}{c} \\
%    \rho^{-1}(z)_{i-1,j} = \tfrac{b}{d}
%    z_{i,j-1} &= \tfrac{a}{c} \\
%    z_{i-1,j} &= \tfrac{b}{d}
%\end{align*}
\begin{align*}
    \frac{xx'}{yy'} &= \frac{ad+bc}{cf+de} 
%    &= \frac{cd\left( \frac{a}{c} + \frac{b}{d} \right)}{cd\left(\frac{f}{d} + \frac{e}{c}\right)} \\
= \frac{\frac{a}{c} + \frac{b}{d}}{\frac{f}{d} + \frac{e}{c}}
%    &= \frac{ \frac{a}{c} + \frac{b}{d} }{\frac{1}{ \left(\frac{d}{f}\right) } + \frac{1}{ \left(\frac{c}{e}\right) } } \\
    = \left( \frac{a}{c} + \frac{b}{d} \right) \left(\frac{d}{f} \parallelsum  \frac{c}{e} \right).  
\end{align*}
Solving for $\frac{x'}{y'}$ yields the desired identity
%\[\frac{x'}{y'}=  \left( \frac{a}{c} + \frac{b}{d} \right) \left(\frac{d}{f} \parallelsum  \frac{c}{e} \right)\left(\frac{y}{x} \right) =  \left( z_{i,j-1} + z_{i-1,j} \right) \left(z_{i,j+1} \parallelsum  z_{i+1,j} \right)\frac{1}{z_{i,j}} = t_{ij}(z)_{ij}\]
\[\frac{x'}{y'}=  \frac{\left( \frac{a}{c} + \frac{b}{d} \right) \left(\frac{c}{e} \parallelsum  \frac{d}{f} \right)}{\frac xy}.\qedhere\]
\end{proof}

\begin{Rem} \label{rem:arraytoggle}
In most cases when we apply Lemma~\ref{lemma:arraytoggle}, all quantities will specialize to well-defined values. There are two exceptions: if we set $e = M_{k,i+k+1}^{(j)} = 0$ (which would make $\frac ce = z_{i+1,j}^{(k-1)}$ undefined), then in the proof we instead have
\begin{align*}
    \frac{xx'}{yy'} &= \frac{ad+bc}{cf} 
%    &= \frac{cd\left( \frac{a}{c} + \frac{b}{d} \right)}{cd\left(\frac{f}{d} + \frac{e}{c}\right)} \\
= \frac{\frac{a}{c} + \frac{b}{d}}{\frac{f}{d}}
%    &= \frac{ \frac{a}{c} + \frac{b}{d} }{\frac{1}{ \left(\frac{d}{f}\right) } + \frac{1}{ \left(\frac{c}{e}\right) } } \\
    = \left( \frac{a}{c} + \frac{b}{d} \right) \left(\frac{d}{f} \right),  
\end{align*}
which yields the same result as Lemma~\ref{lemma:arraytoggle} but with the undefined term $z_{i+1,j}^{(k-1)}$ removed from the parallel sum.
%\[z_{ij}^{(k+1)} = \frac{(z_{i,j-1}^{(k+1)}+z_{i-1,j}^{(k+1)})(z_{i,j+1}^{(k)})}{z_{ij}^{(k)}}.\]
%Note that if in the proof above we set $e = M_{k,i+k+2}^{(j+1)} = 0$ (which would make $\frac ce = z_{i+1,j}^{(k)}$ undefined), we instead arrive at 
%\[z_{ij}^{(k+1)} = \frac{(z_{i,j-1}^{(k+1)}+z_{i-1,j}^{(k+1)})(z_{i,j+1}^{(k)})}{z_{ij}^{(k)}}.\]
A similar result holds if we instead set $f = M_{k,i+k}^{(j+1)}=0$ (which would make $\frac{d}{f} = z_{i,j+1}^{(k-1)}$ undefined).
\end{Rem}


Lemma~\ref{lemma:arraytoggle} suggests that toggling/rowmotion should be thought of as translation with respect to the octahedron recurrence. In the next section, we will see how this relationship can be used to prove the iterated birational rowmotion formula for rectangles.

\section{Birational rowmotion in the rectangle poset} \label{section:rowmotiononrectangles}

In this section, we will use the relationship between the octahedron recurrence and toggles to prove a formula for any power of birational rowmotion on a rectangle similar to one given by Musiker--Roby \cite{musikerroby}. This formula will be described in terms of nonintersecting paths inside a certain graph $\mathcal G_R$. We will begin by proving a lemma that relates nonintersecting paths in $\mathcal G_R$ to nonintersecting paths in $R$.

\subsection{Nonintersecting paths} \label{sec:paths}
Let $R=[r] \times [s]$, and let the element $(i,j)$ have weight $x_{ij}$. For $1 \leq k \leq s$, define $\mathcal P^{(k)}_R$ to be the set of all collections $\mathcal L$ of $k$ nonintersecting (i.e. vertex disjoint) paths traveling up along the edges of the Hasse diagram of $R$, starting at $\{(1,1), (1,2), \dots, (1,k)\}$ and ending at $\{(r,s-k+1),\dots,(r,s)\}$. The \emph{weight} $w(\mathcal L)$ is the product of the weights of the elements in the paths of $\mathcal L$. We will write $w_R^{(k)} = w_R^{(k)}(x)$ for the sum of the weights of all collections of paths in $\mathcal P^{(k)}_R$.  We also write $w_R = w_R^{(s)}$ for the product of all weights in $R$.   Similarly, if $I$ is any interval in $R$, then we define $\mathcal P_I^{(k)}$, $w_I^{(k)}(x)$, and $w_I$ in an analogous manner.

Note that while the definition of $\mathcal P_R^{(k)}$ is asymmetric in $r$ and $s$, if $k \leq \min\{r,s\}$, then the paths in any $\mathcal L \in \mathcal P_R^{(k)}$ must pass through all $k$ elements at rank $k+1$ as well as those at rank $r+s-k+1$. Thus in this case $w_R^{(k)}$ will remain unchanged if we transpose $R$. %(In addition, it is simple to verify that $w_R^{(k)} = w_R$ if $k \geq \min\{r,s\}$.)
We will generally assume that $k \leq \min\{r,s\}$ when considering $\mathcal P_R^{(k)}$.

Define $\mathcal{G}_R$ to be the graph with vertex set $[r+1] \times [s]$, directed edges from $(i,j)$ to $(i+1,j)$ of weight $x_{ij}^{-1}$, and directed edges from $(i,j)$ to $(i+1,j-1)$ of weight 1. (The vertices of $R$ are in bijection with the edges of $\mathcal{G}_R$ whose weights are not $1$.)
As an example, Figure~\ref{fig:poset_and_graph} shows $R = [2] \times [3]$ and the corresponding graph $\mathcal G_R$.

We label the vertices on the boundary of $\mathcal G_R$ as follows: for $1 \leq i \leq r$ and $1 \leq j \leq s$, define
\[P_j = (1, j), \quad P_{s+i} = (i+1, s), \quad Q_i = (i,1), \quad Q_{r+j} = (r+1, j).\]
We then define $\mathcal S^{(k)}_{ij}$ to be the set of all collections $\mathcal L'$ of $k$ nonintersecting paths starting from $\{P_i, \dots, P_{i+k-1}\}$ and ending at $\{Q_j, \dots, Q_{j+k-1}\}$. The \emph{weight} $w(\mathcal L')$ of $\mathcal L'$ is the product of the weights of the edges in the paths of $\mathcal L'$. Let $W_{ij}^{(k)} = W_{ij}^{(k)}(x)$ be the total weight of all $\mathcal L' \in \mathcal S^{(k)}_{ij}$. (By convention, $W_{ij}^{(0)} = 1$ and $W_{ij}^{(k)} = 0$ when $k < 0$.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{figure}
\begin{tikzpicture}[scale = 1.3, rotate = 135]
\transparent{0.0};
\draw [blue] (-0.7,0.2)--(0.5,-1);
\draw [blue] (0.5,-1)--(-0.5,-2);
\transparent{1.0};

%EDGES
\draw (0,0)--(1,0);
\draw [red,thick] (0,-1)--(1,-1);
\draw (0,-2)--(1,-2);

\draw [thick, red] (0,0)--(0,-1);
\draw (0,-1)--(0,-2);
\draw (1,0)--(1,-1);
\draw [thick, red] (1,-1)--(1,-2);

%NODES
\draw [red, fill=red] (0,0) circle [radius=0.08cm];
\draw [fill=black] (1,0) circle [radius=0.08cm];

\draw [red, fill=red] (0,-1) circle [radius=0.08cm];
\draw [red, fill=red] (1,-1) circle [radius=0.08cm];

\draw [fill=black] (0,-2) circle [radius=0.08cm];
\draw [red, fill=red] (1,-2) circle [radius=0.08cm];

\begin{scriptsize}
\node at (-0.3,-0.25) {$x_{11}$};
\node at (-0.3,-1.25) {$x_{12}$};
\node at (-0.3,-2.25) {$x_{13}$};

\node at (0.7,-0.25) {$x_{21}$};
\node at (0.7,-1.25) {$x_{22}$};
\node at (0.7,-2.25) {$x_{23}$};
\end{scriptsize}

\end{tikzpicture}
% \begin{tikzpicture}[scale = 1.3]
% \transparent{0.0}
% \draw [blue] (2,0)--(2,-1.7);
% \draw [blue] (1.6,0)--(3.7,0);
% \transparent{1.0};
% \draw (2,0.1)--(3,0.1)--(3,0.2)--(3.5,0)--(3,-0.2)--(3,-0.1)--(2,-0.1)--cycle;
% \end{tikzpicture}
\qquad
\begin{tikzpicture}[scale = 1.3, rotate = 135]
%EDGES
\draw (0,0)--(1,0);
\draw [blue, thick] (1,0)--(2,0);
\draw (0,-1)--(2,-1);
\draw [blue, thick] (0,-2)--(1,-2);
\draw (1,-2)--(2,-2);

\draw [blue, thick] (0,-1)--(1,0);
\draw (0,-2)--(2,0);
\draw [blue, thick] (1,-2)--(2,-1);

%NODES
\draw [fill=black] (0,0) circle [radius=0.08cm];
\draw [blue, fill=blue] (1,0) circle [radius=0.08cm];
\draw [blue, fill=blue] (2,0) circle [radius=0.08cm];

\draw [blue, fill=blue] (0,-1) circle [radius=0.08cm];
\draw [fill=black] (1,-1) circle [radius=0.08cm];
\draw [blue, fill=blue] (2,-1) circle [radius=0.08cm];

\draw [blue, fill=blue] (0,-2) circle [radius=0.08cm];
\draw [blue, fill=blue] (1,-2) circle [radius=0.08cm];
\draw [fill=black] (2,-2) circle [radius=0.08cm];

\begin{scriptsize}
\node at (-0.2,-0.2) {$P_1$};
\node at (-0.2,-1.2) {$P_2$};
\node at (-0.2,-2.2) {$P_3$};
\node at (0.8,-2.2) {$P_4$};
\node at (1.8,-2.2) {$P_5$};

\node at (0.2,0.2) {$Q_1$};
\node at (1.2,0.2) {$Q_2$};
\node at (2.2,0.2) {$Q_3$};
\node at (2.2,-0.8) {$Q_4$};
\node at (2.2,-1.8) {$Q_5$};

\node at (0.35,-0.23) {$x_{11}^{-1}$};
\node at (1.35,-0.23) {$x_{21}^{-1}$};

\node at (0.35,-1.23) {$x_{12}^{-1}$};
\node at (1.35,-1.23) {$x_{22}^{-1}$};

\node at (0.35,-2.23) {$x_{13}^{-1}$};
\node at (1.35,-2.23) {$x_{23}^{-1}$};
\end{scriptsize}
\end{tikzpicture}
\caption{The poset $R$ and graph $\mathcal G_R$ for $r=2$ and $s=3$. Edges are directed up and to the left in $\mathcal{G}_{R}$, and unlabeled edges have weight $1$. The highlighted paths correspond via the bijection in Lemma~\ref{pathsinideal}.}
\label{fig:poset_and_graph}
\end{figure}

The following result relates paths in $R$ to paths in $\mathcal{G}_R$.

\begin{Lemma} \label{lemma:gr}
%There exists a bijection that sends each $\mathcal L \in \mathcal P_R^{(k)}$ to $\mathcal L' \in \mathcal S_{k,r+1}^{(s-k+1)}$ such that $w(\mathcal L') = \frac{w(\mathcal L)}{w(R)}$.
There exists a bijection from $\mathcal P_R^{(k)}$ to $\mathcal S_{k+1,r+1}^{(s-k)}$ that divides weight by $w_R$.
%collections $\mathcal L$ of nonintersecting lattice paths in $R$ from $A = \{(0,0),\dots ,(0,k)\}$ to $B = \{(r,s-k),\dots,(r,s)\}$ and collections $\mathcal L'$ of nonintersecting paths in $\mathcal{G}_R$ from $A' = \{P_{k+1},\dots, P_s\}$ to $B' = \{Q_{r+1},\dots,Q_{r+s-k}\}$. Under this bijection, the weight of $\mathcal L$ corresponds to the inverse weight of $\mathcal L'$.
\end{Lemma}

\begin{figure}
    \centering
    \begin{tikzpicture}[scale=0.9]
        \tikzstyle{w}=[circle, draw, fill=black, inner sep=0pt, minimum width=2.5pt]
        \begin{scope}[rotate=45,scale=.7]
        \draw[dotted,red] (0,0) grid (4,5);
        \draw[gray,thin,shift={(-.5,-.5)}] (0,0) grid (5,6);
        \draw[red, ultra thick] (0,-.5)--(0,3)--(1,3)--(1,4)--(2,4)--(2,5)--(3,5)--(3,5.5);
        \draw[red, ultra thick] (1,-.5)--(1,1)--(2,1)--(2,3)--(4,3)--(4,5.5);
        \foreach \x in {0,...,4}
            \foreach \y in {0,...,5}
                \node(\x\y)[w] at (\x,\y){};
        \foreach \x/\y in {0/0,0/1,0/2,0/3,1/3,1/4,2/4,2/5,3/5,1/0,1/1,2/1,2/2,2/3,3/3,4/3,4/4,4/5}
            \node[w] at (\x,\y){};
        \end{scope}
        
        \begin{scope}[shift={(3.5,4.5)},scale=.495]
        \draw[gray, thin] (0,0)--(1,1)--(0,2)--(-1,1)--(0,0);
        \node[w] at (0,1){};
        \draw[gray, thin] (2.5,0)--(3.5,1)--(2.5,2)--(1.5,1)--(2.5,0);
        \draw[blue, ultra thick] (3,.5)--(2,1.5);
        \node[w] at (3,.5){};
        \node[w] at (2,1.5){};
        \end{scope}
        \begin{scope}[shift={(3.5,3.1)},scale=.495]
        \draw[gray, thin] (0,0)--(1,1)--(0,2)--(-1,1)--(0,0);
        \draw[red, ultra thick] (.5,.5)--(-.5,1.5);
        \node[w] at (0,1){};
        \draw[gray, thin] (2.5,0)--(3.5,1)--(2.5,2)--(1.5,1)--(2.5,0);
        %\draw[blue, ultra thick] (3,.5)--(2,1.5);
        \node[w] at (3,.5){};
        \node[w] at (2,1.5){};
        \end{scope}
        \begin{scope}[shift={(3.5,1.7)},scale=.495]
        \draw[gray, thin] (0,0)--(1,1)--(0,2)--(-1,1)--(0,0);
        \draw[red, ultra thick] (.5,.5)--(0,1)--(.5,1.5);
        \node[w] at (0,1){};
        \draw[gray, thin] (2.5,0)--(3.5,1)--(2.5,2)--(1.5,1)--(2.5,0);
        \draw[blue, ultra thick] (3,1.5)--(2,1.5);
        \node[w] at (3,.5){};
        \node[w] at (2,1.5){};
        \end{scope}
        \begin{scope}[shift={(3.5,0.3)},scale=.495]
        \draw[gray, thin] (0,0)--(1,1)--(0,2)--(-1,1)--(0,0);
        \draw[red, ultra thick] (-.5,.5)--(0,1)--(-.5,1.5);
        \node[w] at (0,1){};
        \draw[gray, thin] (2.5,0)--(3.5,1)--(2.5,2)--(1.5,1)--(2.5,0);
        \draw[blue, ultra thick] (3,.5)--(2,.5);
        \node[w] at (3,.5){};
        \node[w] at (2,1.5){};
        \end{scope}
        \begin{scope}[shift={(3.5,-1.1)},scale=.495]
        \draw[gray, thin] (0,0)--(1,1)--(0,2)--(-1,1)--(0,0);
        \draw[red, ultra thick] (-.5,.5)--(0,1)--(.5,1.5);
        \node[w] at (0,1){};
        \draw[gray, thin] (2.5,0)--(3.5,1)--(2.5,2)--(1.5,1)--(2.5,0);
        \draw[blue, ultra thick] (3,1.5)--(2,1.5) (3,.5)--(2,.5);
        \node[w] at (3,.5){};
        \node[w] at (2,1.5){};
        \end{scope}
        
        \begin{scope}[shift={(8.7,0)},rotate=45,scale=.7]
        \draw[gray,thin,shift={(-.5,-.5)}] (0,0) grid (5,6);
        \foreach \x in {0,...,4}
            \draw[dotted,blue] (\x,-.5)--(\x,5.5);
        \foreach \x in {0,...,3}
            \foreach \y in {1,...,6}
                \draw[dotted,blue] (\x,\y-.5)--(\x+1,\y-1.5);
        \draw[blue, ultra thick] (2,-.5)--(2,.5)--(1,1.5)--(1,2.5)--(0,3.5)--(0,5.5);
        \draw[blue, ultra thick] (3,-.5)--(3,2.5)--(1,4.5)--(1,5.5);
        \draw[blue, ultra thick] (4,-.5)--(4,2.5)--(3,3.5)--(3,4.5)--(2,5.5);
        \foreach \x in {0,...,4}
            \foreach \y in {0,...,6}
                \node(\x\y)[w] at (\x,\y-.5){};
        \end{scope}
    \end{tikzpicture}
    \caption{Bijection between $\mathcal P_R^{(k)}$ and $\mathcal S_{k+1,r+1}^{(s-k)}$ as in Lemma~\ref{lemma:gr}. Tiles on the left are replaced with the corresponding tiles on the right.}
    \label{fig:5-vertex}
\end{figure}

\begin{proof}
In the drawing of $\mathcal L \in \mathcal P^{(k)}_R$, extend the start and end of each path by a half-edge from northwest to southeast. Such a drawing can be built by piecing together square tiles centered at each vertex showing the five ways in which the paths can pass through that vertex in such a way that the tiles match along sides---see Figure~\ref{fig:5-vertex}. We can replace each tile with a new tile containing edges/half-edges parallel to the edges of $\mathcal G_R$ in a way that preserves the exits along the southwest and northeast sides but inverts the exits along the southeast and northwest sides as shown in Figure~\ref{fig:5-vertex}. Placing vertices on the southeast and northwest edges of these new tiles, the resulting drawing will then depict a collection of paths $\mathcal L'$ in $\mathcal G_R$ that forms an element of $\mathcal S_{k+1,r+1}^{(s-k)}$. (This bijection also has the following alternate description: when the two drawings are overlaid, each of the $k$ horizontal steps in the $i$th path in $\mathcal L'$ crosses the $i$th northeast step in one of the $k$ paths in $\mathcal L$.)

The weighted edges in $\mathcal L'$ correspond to elements of $R$ not lying in any path of $\mathcal L$. Thus $w(\mathcal L')$ is the inverse of the weight of the complement of $\mathcal L$ in $R$, which is exactly $\frac{w(\mathcal L)}{w_R}$.
\end{proof}


% \begin{proof}
% We overlay $R$ and $\mathcal G_R$ so that $(i,j) \in R$ coincides with $(i,j) \in \mathcal G_R$. Let $\mathcal L = \{L_1, \dots, L_k\}$ be a collection of nonintersecting paths from $A = \{(0,0),\dots ,(0,k-1)\}$ to $B = \{(r,s-k+1),\dots,(r,s)\}$ in $R$. We construct paths $\mathcal L' = \{L_{k}', \dots, L_s'\}$ starting at the elements of $A' = \{P_{k},\dots, P_s\}$ in $\mathcal G_R$ as follows: starting each path $L_i'$ at $P_i$, repeatedly extend each path to the northwest if its current endpoint does not lie in any path of $\mathcal L$, otherwise extend it to the west. In other words, in the overlaid diagrams, each $L_i'$ contains a horizontal step immediately after crossing some $L_j$ (i.e. touching the endpoint of a northeast step in $\mathcal L$). See Figure~\ref{fig:overlay}. Note that a path $L_i'$ cannot cross $L_j$ at the endpoint of a northwest step in $L_j$ since the first time this happens would require both a northwest and northeast step starting at the same point in $\mathcal L$.

% After a fixed number of steps, $L_p'$ must cross at least as many paths in $\mathcal L$ as $L_q'$ if $p < q$. Therefore $L_p'$ will have taken at least as many horizontal steps, so the paths in $\mathcal L'$ do not intersect. Since the paths in $\mathcal L$ must together contain all elements in the top $k$ ranks of $R$, no path in $\mathcal L'$ can contain any point in the top $k-1$ ranks of $R$, so each path in $\mathcal L'$ must cross each path in $\mathcal L$. It follows that $\mathcal L'$ is a collection of nonintersecting paths starting from $A'$ and ending at $B' = \{Q_{r+1},\dots,Q_{r+s-k+1}\}$.

% The inverse map is constructed similarly: given $\mathcal L'$, start paths at the elements of $A$ and step to the northwest unless the new point lies in one of the $L_i'$ (i.e. at the end of a horizontal step in $L_i'$), in which case step to the northeast instead. A similar argument as above shows that this defines a collection of nonintersecting paths $\mathcal L$ from $A$ to $B$ in $R$. These maps are inverses because $\mathcal L'$ and $\mathcal L$ are determined by their horizontal and northeast steps, respectively, which are constructed to be incident in both cases.

% By construction, no northwest step in $\mathcal L'$ can start at the beginning or end of any northwest step in $\mathcal L$. Thus the inverse weight of any edge used in $\mathcal L'$ is not the weight of any vertex used in $\mathcal L$. A simple counting argument then shows that every variable $x_{ij}$ appears in exactly one $w(\mathcal L)$ and $w(\mathcal L')^{-1}$, which proves the claim.
% \end{proof}



% \begin{proof}
% We overlay $R$ and $\mathcal{G}_R$ such that $(i,j) \in R$ coincides with $(i,j) \in \mathcal{G}_R$. Let $(V,E)$ be the sets of vertices and edges in a set of nonintersecting lattice paths in $R$. We define $V'$ to be the set of vertices $(i,j)$ in $\mathcal{G}_R$ such that there is no edge $(i-1,j) \to (i,j) \in E$. We claim that there exists a unique set of edges $E'$ in $\mathcal{G}_R$ such that $(V',E')$ forms a collection of nonintersecting paths. The uniqueness is clear, so we need only prove existence.



% Let $E'$ be the set of edges in $\mathcal{G}_R$ starting at $(i,j) \in V'$ of the form $(i,j) \to (i+1,j-1)$ if $(i,j-1) \to (i,j) \in E$ and $(i,j) \to (i+1,j)$ otherwise. It follows that from each $(i,j)$ with $i \leq r$, there is exactly one edge in $E'$ exiting $(i,j)$. 

% \begin{figure}[h]
%     \centering
% \begin{tikzpicture}
% \draw [very thick, red] (0,0)--(1,1);
% \draw [very thick, blue] (1,1)--(-1,1);

% \draw [fill=black] (-1,1) circle [radius=0.1cm];
% \draw [fill=black] (1,1) circle [radius=0.1cm];
% \draw [fill=black] (0,0) circle [radius=0.1cm];
% \draw [fill=black] (0,2) circle [radius=0.1cm];

% \begin{scriptsize}
% \node at (1,1.3) {$(i,j)$};
% \node at (-1,1.3) {$(i+1,j-1)$};
% \node at (-0.8,0) {$(i,j-1)$};
% \end{scriptsize}




% \foreach \x in {4}{
% \draw [xshift = \x cm, very thick, blue] (1,1)--(0,2);

% \draw [xshift = \x cm, fill=black] (-1,1) circle [radius=0.1cm];
% \draw [xshift = \x cm, fill=black] (1,1) circle [radius=0.1cm];
% \draw [xshift = \x cm, fill=black] (0,2) circle [radius=0.1cm];
% \draw [xshift = \x cm, fill=black] (0,0) circle [radius=0.1cm];

% \begin{scriptsize}
% \node [xshift = \x cm] at (-1,1.3) {$(i+1,j-1)$};
% \node [xshift = \x cm] at (1.1,2) {$(i+1,j)$};
% \node [xshift = \x cm] at (1,0.7) {$(i,j)$};
% \end{scriptsize}
% }
% \end{tikzpicture}
%     \caption{The blue edges in $E'$ are determined by the red edges of $E$}
%     \label{fig:my_label}
% \end{figure}

% If $(i,j) \to (i+1,j-1) \in E'$, then $(i,j-1) \to (i,j) \in E$ and so we cannot have $(i,j-1) \to (i+1,j-1) \in E'$ (because the lattice paths are not intersecting). If $(i,j) \to (i+1,j) \in E'$, then $(i,j-1) \to (i,j) \not\in E$. If $(i+1,j) \not\in V'$, then there must be an edge $(i,j) \to (i+1,j) \in E$. This edge must be preceded by an edge of the form $(i-1,j) \to (i,j) \in E$, so $(i,j) \not\in V'$, a contradiction. Hence the edges of $E'$ end in $V'$.

% If we have both $(i-1,j) \to (i,j) \in E'$ and $(i-1,j+1) \to (i,j) \in E'$, then we have $(i-1,j) \to (i-1,j+1) \in E$ and $(i-1,j-1) \to (i-1,j) \not\in E$. Consequently $(i-2,j) \to (i-1,j) \in E$, and so $(i-1,j) \not \in V'$, a contradiction.

% If we have neither of these edges in $E'$, then there are $r+s-k$ points at which paths can end and more than $r+s-k$ paths. By the pigeonhole principle two paths must both enter the same point, which we said was not possible. Hence the pair $(V',E')$ forms a set of nonintersecting lattice paths in $\mathcal{G}_R$. The inverse is similar.
% \begin{figure}
% \begin{tikzpicture}[scale = 1]
% \draw [very thick, blue] (0,0)--(-1,1);
% \draw [very thick, blue] (0,0)--(-2,0);

% \draw [fill=black] (0,0) circle [radius=0.1cm];
% \draw [fill=black] (-1,1) circle [radius=0.1cm];
% \draw [fill=black] (-2,0) circle [radius=0.1cm];

% \begin{small}
% \node at (0.55,0) {$(i,j)$};
% \node at (-1.9,1) {$(i+1,j)$};
% \node at (-3.2,0) {$(i-1,j+1)$};
% \end{small}

% \node at (0.6,0.8) {$\substack{ \text{ Traversed if} \\ (i,j-1) \to (i,j) \not\in E }$};
% \node at (-1,-0.35) {$\substack{ \text{ Traversed if} \\ (i,j-1) \to (i,j) \in E }$};

% \foreach \x in {6}{
% \draw [very thick, blue, xshift = \x cm] (0,1)--(-2,1)--(-1,0);

% \draw [very thick, red, xshift = \x cm] (0,-1)--(-1,0)--(0,1);

% \draw [fill=black, xshift = \x cm] (0,1) circle [radius=0.1cm];
% \draw [fill=black, xshift = \x cm] (-2,1) circle [radius=0.1cm];
% \draw [fill=black, xshift = \x cm] (-1,0) circle [radius=0.1cm];
% \draw [fill=black, xshift = \x cm] (0,-1) circle [radius=0.1cm];

% \draw [thick, xshift = \x cm] (-1.3,-0.5)--(-1,-0.5)--(-1,0);

% \begin{small}
% \node [xshift = \x cm] at (-2.5,1) {$(i,j)$};
% \node [xshift = \x cm] at (1.2,1) {$(i-1,j+1)$};

% \node [xshift = \x cm] at (-1.9,0) {$(i-1,j)$};

% \node [xshift = \x cm] at (0.55,-1) {$(i,j)$};
% \end{small}

% \node [xshift = \x cm] at (0.75,0.4) {$\substack{ \text{ Lies in E since} \\ (i-1,j+1) \to (i,j) \in E' }$};
% \node [xshift = \x cm] at (0.9,-0.4) {$\substack{ \text{ Lies in E since a path} \\ \text{must enter } (i-1,j) }$};

% \node [xshift = \x cm] at (-2.2,-0.5) {$\substack{\text{both in } V' \\ \text{and not in } V'}$};
% };
% \end{tikzpicture}
% \caption{Two distinct edges in $E'$ cannot both enter or both exit a common vertex.}
% \end{figure}
% \end{proof}

%As a corollary, we obtain an analogous result on the order ideals and the order filters of $R$.

%\begin{Cor}
%Let $R = [0,r] \times [0,s]$ and let $(i,j) \in R$. Then the weight of all nonintersecting paths from $\{P_0,\dots,P_j\}$ to $\{Q_{i+1},\dots,Q_{i+j+1}\}$ is $\prod\limits_{z \in \Lambda_{i,j}} x_z^{-1}$. For order filters, the weight of all nonintersecting paths from $\{P_{i+j},\dots,P_{s+j}\}$ to $\{Q_{r+i+1},\dots,Q_{r+s+1}\}$ is $\prod\limits_{z \in \text{V}_{i,j}} x_z^{-1}$.
%\label{pathsinideal}
%\end{Cor}

%\begin{proof} From $P_0$, a path can only take diagonal steps, and may only end at $Q_{i+1}$. For each subsequent $P_\ell$, diagonal steps are again forced until reaching $(i,\ell)$. At this point, any diagonal steps will prevent $Q_{i+\ell+1}$ from being the end of some set nonintersecting paths, so horizontal steps are forced. Thus there is a unique set of nonintersecting paths from $\{P_0,\dots,P_j\}$ to $\{Q_{i+1},\dots,Q_{i+j+1}\}$ and the diagonal steps are exactly those corresponding to elements of the order ideal $\Lambda_{i,j}$. See Figure \ref{fig:pathsinorderideal} for an example. A similar argument proves the result for order filters.
%\end{proof}



Let $A=(a_{ij})_{i,j=1}^{r+s}$ be the square matrix such that $a_{ij} = W_{ij}^{(1)}$, the total weight of all paths from $P_i$ to $Q_j$ in $\mathcal G_R$. By the Lindstr\"om--Gessel--Viennot Lemma  \cite{gesselviennot,lindstrom}, each minor $\det(A_{ij}^{(k)})$ is equal to $W_{ij}^{(k)}$, the total weight of $\mathcal S_{ij}^{(k)}$, the set of all collections of nonintersecting paths from $\{P_i, P_{i+1}, \dots, P_{i+k-1}\}$ to $\{Q_j, Q_{j+1}, \dots, Q_{j+k-1}\}$. By the discussion in Section~\ref{sec:octahedron}, the three-dimensional array $W=(W_{ij}^{(k)})$ formed by these minors satisfies the octahedron recurrence. See Figure~\ref{fig:array} for a depiction of $W$ when $R=[2] \times [3]$.

We will need a few simple properties of the array $W$.

\begin{Prop}\label{prop:wproperties}
Let $R=[r]\times [s]$, and let $W = (W_{ij}^{(k)})$ be the corresponding three-dimensional array. Assume $k > 0$ and $0 \leq i,j \leq r+s+1-k$.
\begin{enumerate}[(a)]
    \item If $W_{ij}^{(k)} \neq 0$, then $i \leq j \leq i+r$.
    \item If $i = j$, then $W_{ij}^{(k)}=1$.
    \item If $i < j$ and $k > s$, then $W_{ij}^{(k)}=0$.
\end{enumerate}
\end{Prop}
\begin{proof}
All of these follow from the description of $W_{ij}^{(k)}$ as the total weight of $\mathcal S_{ij}^{(k)}$. For (a), there are no paths from $P_i$ to $Q_j$ if $i > j$ or $j-i>r$. For (b), if $i=j$, then $\mathcal S_{ij}^{(k)}$ has only one element consisting only of horizontal steps of weight $1$.

For (c), if $i < j$ and $k > s$, then the first $s+1$ starting points $P_i, \dots, P_{i+s}$ all lie at or below row $i+1$, while the ending points for these paths lie at or above row $j \geq i+1$. But row $i+1$ only has $s$ vertices, so it is impossible for there to be $s+1$ nonintersecting paths passing through it.
\end{proof}

We can translate Lemma~\ref{lemma:gr} into a statement expressing weights of certain collections of nonintersecting paths in $R$ in terms of the array of minors $W=(W_{ij}^{(k)})$. In fact, we can formulate a similar result for paths inside certain intervals $I \subseteq R$, specifically those for which the leftmost point of $I$ lies on the left boundary of $R$ and the rightmost point of $I$ lies on the right boundary of $R$.

\begin{Cor}\label{pathsinideal}
Let $R = [r] \times [s]$, and let $I=[i_1,i_2] \times [j_1,j_2]$ be an interval in $R$ such that $i_1=1$ or $j_2=s$, and $j_1=1$ or $i_2=r$.
\begin{enumerate}[(a)]
    \item %There exists a bijection that sends each $\mathcal L \in \mathcal P_I^{(k)}$ to $\mathcal L' \in \mathcal S_{i_1+j_1+k,i_2+j_1+1}^{(j_2-j_1-k+1)}$ such that $w(\mathcal L') = \frac{w(\mathcal L)}{w(I)}$.
    There exists a bijection from $\mathcal P_I^{(k)}$ to $\mathcal S_{i_1+j_1+k-1,i_2+j_1}^{(j_2-j_1-k+1)}$ that divides weight by $w_I$, so that
    \[W_{i_1+j_1+k-1,i_2+j_1}^{(j_2-j_1-k+1)} = \frac{w_I^{(k)}}{w_I}.\]
    %collection of nonintersecting paths in $\mathcal G_R$ from $\{P_{i_1+j_1+k}, \dots, P_{i_1+j_2}\}$ to\\ $\{Q_{i_2+j_1+1}, \dots, Q_{i_2+j_2-k+1}\}$ whose weight is the inverse weight of $I \setminus \mathcal L$.
    \item The following equality holds:
    %The total weight of collections of paths in $\mathcal P_{i_1j_1}^{i_2j_2}(k)$ is
%\[\sum_{\mathcal L \in \mathcal P_{i_1j_1}^{i_2j_2}(k)} \prod_{z \in \mathcal L} x_z 
%= \frac{\displaystyle\sum_{\mathcal L \in \mathcal P_{i_1j_1}^{i_2j_2}(k)} \prod_{z \in I \setminus \mathcal L}x_z^{-1}}{\displaystyle\prod_{z \in I}x_z^{-1}}
\[w_I^{(k)} 
= \frac{W_{i_1+j_1+k-1,i_2+j_1}^{(j_2-j_1-k+1)}}{W_{i_1+j_1-1,i_2+j_1}^{(j_2-j_1+1)}}.\]
\end{enumerate}
\end{Cor}
\begin{proof}
Any nonintersecting paths in $\mathcal G_R$ starting at $P_{i_1+j_1+k-1}, \dots, P_{i_1+j_2-1}$ must begin with horizontal steps until reaching row $i_1$ at points $(i_1, j_1+k), \dots, (i_1,j_2)$. See Figure~\ref{fig:pathsinorderideal}. (This statement is trivial if $i_1 = 1$.) Similarly, any nonintersecting paths ending at $Q_{i_2+j_1}, \dots, Q_{i_2+j_2-k}$ must pass through row $i_2+1$ at $(i_2+1, j_1), \dots, (i_2+1, j_2-k)$ and end with horizontal steps. (This is trivial if $i_2=r$.) The remaining parts of the paths lie inside the subgraph of $\mathcal G_R$ from rows $i_1$ through $i_2+1$ and columns $j_1$ through $j_2$, which is isomorphic as a weighted graph to $\mathcal G_I$. Part (a) follows by applying Lemma~\ref{lemma:gr} to $I$ and summing over all paths.

For part (b), 
%using part (a), the numerator of the right hand side is 
%$\sum_{\mathcal L'} w(\mathcal L') = w(I)^{-1} \cdot \sum_{\mathcal L} w(\mathcal L)$. 
%the sum of $\frac{w(\mathcal L)}{w_I}$ for collections of paths $\mathcal L \in \mathcal P_I^{(k)}$. 
%$\frac{w_I^{(k)}}{w_I}$. 
setting $k=0$ in part (a) gives $W^{(j_2-j_1+1)}_{i_1+j_1-1,i_2+j_1} = \frac{1}{w_I}$. Combining  with part (a) gives the result.
%$w(I)^{-1}$, so their quotient is $\sum_{\mathcal L} w(\mathcal L) = w_I^{(k)}$, as desired.
%Thus their quotient is $w_I^{(k)}$, as desired.
%the total weight of all possible $\mathcal L \in P_I^{(k)}$, as desired.
\end{proof}

% \begin{Cor}\label{pathsinideal}
% Let $R = [0,r] \times [0,s]$ and let $(i,j) \in R$.

% \begin{enumerate}[(a)]
% \item There is a bijection between nonintersecting lattice paths in $\Lambda_{i,j}$ from $\{(0,0),\dots,(0,k)\}$ to $\{(i,j-k),\dots,(i,j)\}$ to nonintersecting paths in $\mathcal{G}_R$ from $\{P_{k+1},\dots,P_j\}$ to $\{Q_{i+1},\dots,Q_{i+j-k}\}$.
% \item There is a bijection between nonintersecting lattice paths in $\text{V}_{i,j}$ from $\{(i,j),\dots,(i,j+k)\}$ to $\{(r,s-k),\dots,(r,s)\}$ to nonintersecting paths in $\mathcal{G}_R$ from $\{P_{i+j+k+1},\dots,P_{s+i}\}$ to $\{Q_{r+j+1},\dots,Q_{r+s-k}\}$.
% \end{enumerate}

% In either case, the weight of the complement of such a collection of nonintersecting lattice paths in $R$ is mapped to its inverse. 
% \end{Cor}

% \begin{proof} Any set of paths ending at $\{Q_{i+1},\dots,Q_{i+j-k}\}$ must end in horizontal steps from $\{Q_{i+1}',\dots,Q_{i+j-k}'\}$, where $Q_\ell' = (i+1,\ell-i-1)$. The lattice paths from $\{P_{k+1},\dots,P_j\}$ to $\{Q_{i+1}',\dots,Q_{i+j-k}'\}$ in $\mathcal{G}_R$ are exactly the lattice paths associated to the same set of points in $\mathcal{G}_{\Lambda_{i,j}}$. By Lemma \ref{lemma:gr}, the weight of each system of paths is the inverse of the weight of the complement of nonintersecting lattice paths from $\{(0,0),\dots,(0,k)\}$ to $\{(i,j-k),\dots,(i,j)\}$ in $\Lambda_{i,j}$. A similar argument shows the result for order filters.
% \end{proof}

\begin{figure}
\begin{tikzpicture}[scale = .8, rotate = 135]
%EDGES
\tikzset{v/.style={circle, draw, inner sep=0pt, minimum width=4pt}}
\foreach \i in {1,...,6}
    \foreach \j in {1,...,7}
        \node[v,fill=black] at (\i,-\j){};
\foreach \i in {1,...,5}
    \foreach \j in {1,...,7}
        \draw (\i,-\j)--(\i+1,-\j);
\foreach \i in {1,...,5}
    \foreach \j in {2,...,7}
        \draw (\i,-\j)--(\i+1,-\j+1);
\foreach \i/\j in {3/7,3/6,3/5,3/4,2/7,2/6,2/5,1/7,1/6,6/2,6/3,6/4,6/5}
    \node[v,draw=red,fill=red] at (\i,-\j){};
\draw[ultra thick,red] (2,-7)--(3,-6) (1,-7)--(3,-5) (1,-6)--(3,-4);
\draw[dotted] (2.75,-1.75) rectangle (6.25,-7.25);
\node at (.5,-6.5) {$P_6$};
\node at (.5,-7.5) {$P_7$};
\node at (1.5,-7.5) {$P_8$};
\node at (2.5,-7.5) {$P_9$};
\node at (6.7,-2) {$Q_7$};
\node at (6.7,-3) {$Q_8$};
\node at (6.7,-4) {$Q_9$};
\node at (6.7,-5) {$Q_{10}$};
% \draw [red,very thick] (0,0)--(1,0);
% \draw [very thick] (1,0)--(2,0);
% \draw [red,very thick] (0,-1)--(1,-1);
% \draw [very thick] (1,-1)--(2,-1);
% \draw [red, very thick] (0,-2)--(1,-2);
% \draw [very thick] (1,-2)--(2,-2);

% \draw [very thick] (0,-1)--(1,0);
% \draw [very thick] (0,-2)--(1,-1);
% \draw [red, very thick] (1,-1)--(2,0);
% \draw [red, very thick] (1,-2)--(2,-1);

% %NODES
% \draw [red, fill=red] (0,0) circle [radius=0.08cm];
% \draw [red, fill=red] (1,0) circle [radius=0.08cm];
% \draw [red, fill=red] (2,0) circle [radius=0.08cm];

% \draw [red, fill=red] (0,-1) circle [radius=0.08cm];
% \draw [red, fill=red] (1,-1) circle [radius=0.08cm];
% \draw [red, fill=red] (2,-1) circle [radius=0.08cm];

% \draw [red, fill=red] (0,-2) circle [radius=0.08cm];
% \draw [red, fill=red] (1,-2) circle [radius=0.08cm];
% \draw [fill=black] (2,-2) circle [radius=0.08cm];

% \begin{scriptsize}
% \node at (-0.2,-0.2) {$P_0$};
% \node at (-0.2,-1.2) {$P_1$};
% \node at (-0.2,-2.2) {$P_2$};

% \node at (1.2,0.2) {$Q_1$};
% \node at (2.2,0.2) {$Q_2$};
% \node at (2.2,-0.8) {$Q_3$};

% \node at (0.35,-0.23) {$x_{0,0}^{-1}$};
% \node at (1.35,-0.23) {$x_{1,0}^{-1}$};

% \node at (0.35,-1.23) {$x_{0,1}^{-1}$};
% \node at (1.35,-1.23) {$x_{1,1}^{-1}$};

% \node at (0.35,-2.23) {$x_{0,2}^{-1}$};
% \node at (1.35,-2.23) {$x_{1,2}^{-1}$};
% \end{scriptsize}
\end{tikzpicture}
\caption{Illustration of $\mathcal G_R$ and $\mathcal G_I$ (dotted) for $R = [5] \times [7]$ and $I = [3,5] \times [2,7]$ with $k=2$ as in Corollary~\ref{pathsinideal} (note $j_2=s$ and $i_2=r$). Nonintersecting paths from $\{P_6, \dots P_9\}$ to $\{Q_7, \dots, Q_{10}\}$ in $\mathcal G_R$ must contain the horizontal steps shown.}
\label{fig:pathsinorderideal}
\end{figure}

In particular, note that the conditions of Corollary~\ref{pathsinideal} hold whenever $I$ is an order ideal (when $i_1=j_1=1$) or order filter (when $i_2=r$ and $j_2=s$) of $R$.


\subsection{Birational rowmotion formula}

Using the relation between the octahedron recurrence and toggles, we will prove the following birational rowmotion formula.

\begin{Th}
\label{birationalrowmotionformula}
Let $R = [r] \times [s]$, $x \in \mathbb{R}_{>0}^{R}$, and $y = \phi^{-1}(x)$. %Label the edges of $(i,j) \to (i+1,j)$ in $\mathcal{G}_R$ with $x_{ij}^{-1}$ and all other edges in $\mathcal{G}_R$ with label 1. 
Fix $(i,j) \in R$.

%Label the edges of $\mathcal G_R$ with respect to $x$ as described above, and let $(i,j) \in R$.

%For $0 \leq u,v \leq r+s+1$ let $P_u = (\max(u-s,0), \min(u,s))$ and $Q_v = (\min(v,r), \max(v-r,0))$. Let $y \in \mathbb{R}_{>0}^{R}$ and let $x = \phi(y)$. Label $\mathcal{G}_R$ as above using the labelling $x$ of the rectangle. Let $W_a^b(c)$ denote the sum of the weights of all non-intersecting lattice paths from $(P_a,...,P_{a+c-1})$ to $(Q_b,...,Q_{b+c-1})$. If $0 \leq k \leq r+s+1$ and $i+j \leq r+s-k$, then

\begin{enumerate}[(a)]
\item If $0 \leq k \leq r+s-i-j$, then
\[\rho^{-k}(y)_{ij} = \frac{W_{k+2,i+k+1}^{(j-1)}}{W_{k+1,i+k+1}^{(j)}}.\]
\item For all $k \in \mathbb{Z}$,
\[\rho^{k}(y)_{ij} = \frac{1}{\rho^{k-i-j+1}(y)_{r+1-i,s+1-j}}.\]
In particular, if $0 < k < i+j$, then the right hand side can be computed using part (a).
%In particular, if $0 \leq k \leq r+s+1$ and $i+j > r+s-k$, then $\rho^{k-i-j}(y)_{r-i,s-j}$ can be calculated from part (a).
\item For all $k \in \mathbb Z$, $\rho^{k+r+s}(y) = \rho^k(y)$. In other words, the action of rowmotion on $R$ has order $r+s$.
\end{enumerate}
\end{Th}

%In the array, each labelling is of the form $W_a^b(c)$ and the value of $\rho^{-k}(y)_{i,j}$ is stored in pairs of labellings. To obtain $y_{i,j}$ from $M$, we claim that $y_{i,j} = \frac{M_{2,2i+2,j}}{M_{0,2i+2,j+1}}$, and that applying inverse rowmotion yields the array shifted by $(2,2,0)$. Note that in the figure below, shifting the array of edges by $(2,2,0)$ causes part of the edge corresponding to the label of $(r,s)$ to exit the array, and so Part A cannot compute this coordinate. Indeed, after each application of $\rho^{-k}$ and each shift by $(2,2,0)$, we lose the ability to compute the value at yet another rank.

%Label the rectangle $R = [0,r] \times [0,s]$ as below (this is the labeling obtained after applying the transfer map).

% \begin{figure}
% \begin{tikzpicture}[scale = 1.3, rotate = 135]
% \transparent{0.0};
% \draw [blue] (-0.7,0.2)--(0.5,-1);
% \draw [blue] (0.5,-1)--(-0.5,-2);
% \transparent{1.0};

% %EDGES
% \draw (0,0)--(1,0);
% \draw (0,-1)--(1,-1);
% \draw (0,-2)--(1,-2);

% \draw (0,0)--(0,-2);
% \draw (1,0)--(1,-2);

% %NODES
% \draw [fill=black] (0,0) circle [radius=0.08cm];
% \draw [fill=black] (1,0) circle [radius=0.08cm];

% \draw [fill=black] (0,-1) circle [radius=0.08cm];
% \draw [fill=black] (1,-1) circle [radius=0.08cm];

% \draw [fill=black] (0,-2) circle [radius=0.08cm];
% \draw [fill=black] (1,-2) circle [radius=0.08cm];

% \begin{small}
% \node at (-0.2,-0.2) {$a$};
% \node at (-0.2,-1.2) {$c$};
% \node at (-0.2,-2.2) {$e$};

% \node at (0.8,-0.2) {$b$};
% \node at (0.8,-1.2) {$d$};
% \node at (0.8,-2.2) {$f$};
% \end{small}

% \end{tikzpicture}
% \caption{}
% \label{fig:rectangle}
% \end{figure}

\begin{figure}
\begin{tikzpicture}[scale = 0.85]

%R
\begin{scope}[scale=1.2,shift={(-6,7.5)},rotate=135]
%EDGES
\draw (0,0)--(1,0);
\draw (0,-1)--(1,-1);
\draw (0,-2)--(1,-2);

\draw (0,0)--(0,-2);
\draw (1,0)--(1,-2);

%NODES
\draw [fill=black] (0,0) circle [radius=0.08cm];
\draw [fill=black] (1,0) circle [radius=0.08cm];

\draw [fill=black] (0,-1) circle [radius=0.08cm];
\draw [fill=black] (1,-1) circle [radius=0.08cm];

\draw [fill=black] (0,-2) circle [radius=0.08cm];
\draw [fill=black] (1,-2) circle [radius=0.08cm];

\begin{small}
\node at (-0.2,-0.2) {$a$};
\node at (-0.2,-1.2) {$c$};
\node at (-0.2,-2.2) {$e$};

\node at (0.8,-0.2) {$b$};
\node at (0.8,-1.2) {$d$};
\node at (0.8,-2.2) {$f$};
\end{small}
\end{scope}

\begin{scope}[scale = 1.2, shift={(3,7.0)}, rotate = 135]
%EDGES
\draw (0,0)--(1,0);
\draw (1,0)--(2,0);
\draw (0,-1)--(2,-1);
\draw (0,-2)--(1,-2);
\draw (1,-2)--(2,-2);

\draw (0,-1)--(1,0);
\draw (0,-2)--(2,0);
\draw (1,-2)--(2,-1);

%NODES
\draw [fill=black] (0,0) circle [radius=0.08cm];
\draw [fill=black] (1,0) circle [radius=0.08cm];
\draw [fill=black] (2,0) circle [radius=0.08cm];

\draw [fill=black] (0,-1) circle [radius=0.08cm];
\draw [fill=black] (1,-1) circle [radius=0.08cm];
\draw [fill=black] (2,-1) circle [radius=0.08cm];

\draw [fill=black] (0,-2) circle [radius=0.08cm];
\draw [fill=black] (1,-2) circle [radius=0.08cm];
\draw [fill=black] (2,-2) circle [radius=0.08cm];

\begin{scriptsize}
\node at (-0.2,-0.2) {$P_1$};
\node at (-0.2,-1.2) {$P_2$};
\node at (-0.2,-2.2) {$P_3$};
\node at (0.8,-2.2) {$P_4$};
\node at (1.8,-2.2) {$P_5$};

\node at (0.2,0.2) {$Q_1$};
\node at (1.2,0.2) {$Q_2$};
\node at (2.2,0.2) {$Q_3$};
\node at (2.2,-0.8) {$Q_4$};
\node at (2.2,-1.8) {$Q_5$};

\node at (0.39,-0.18) {$\overline{a}$};
\node at (1.39,-0.18) {$\overline{b}$};

\node at (0.39,-1.18) {$\overline{c}$};
\node at (1.39,-1.18) {$\overline{d}$};

\node at (0.39,-2.18) {$\overline{e}$};
\node at (1.39,-2.21) {$\overline{f}$};
\end{scriptsize}
\end{scope}


\draw [red,thick] (-1.625,-0.25)--(-2,0.5);
\draw [red,thick] (-3.625,0.25)--(-4,1);

\draw [red,thick] (-1,1)--(-2.5,4);
\draw [red,thick] (-3,1.5)--(-4.5,4.5);

\draw [red,thick] (-1.5,4.5)--(-3,7.5);
\draw [red,thick] (-3.5,5)--(-5,8);

\draw [blue,thick] (-2.625,0.75)--(-3,1.5);
\draw [blue,thick] (-4.625,1.25)--(-5,2);

\draw [blue,thick] (-2,2)--(-3.5,5);
\draw [blue,thick] (-4,2.5)--(-5.5,5.5);

\draw [blue,thick] (-2.5,5.5)--(-4,8.5);
%\draw [blue,thick] (-4.5,6)--(-6,9);

%LAYER 1
\draw [fill=black] (0,0) circle [radius=0.08cm];
\draw [fill=black] (-2,0.5) circle [radius=0.08cm];
\draw [fill=black] (-4,1) circle [radius=0.08cm];
\draw [fill=black] (-6,1.5) circle [radius=0.08cm];
\draw [fill=black] (-8,2) circle [radius=0.08cm];

\draw [fill=black] (1,0.5) circle [radius=0.08cm];
\draw [fill=black] (-1,1) circle [radius=0.08cm];
\draw [fill=black] (-3,1.5) circle [radius=0.08cm];
\draw [fill=black] (-5,2) circle [radius=0.08cm];
\draw [fill=black] (-7,2.5) circle [radius=0.08cm];

\draw [fill=black] (2,1) circle [radius=0.08cm];
\draw [fill=black] (0,1.5) circle [radius=0.08cm];
\draw [fill=black] (-2,2) circle [radius=0.08cm];
\draw [fill=black] (-4,2.5) circle [radius=0.08cm];
\draw [fill=black] (-6,3) circle [radius=0.08cm];

\draw [fill=black] (3,1.5) circle [radius=0.08cm];
\draw [fill=black] (1,2) circle [radius=0.08cm];
\draw [fill=black] (-1,2.5) circle [radius=0.08cm];
\draw [fill=black] (-3,3) circle [radius=0.08cm];
\draw [fill=black] (-5,3.5) circle [radius=0.08cm];

\draw [fill=black] (4,2) circle [radius=0.08cm];
\draw [fill=black] (2,2.5) circle [radius=0.08cm];
\draw [fill=black] (0,3) circle [radius=0.08cm];
\draw [fill=black] (-2,3.5) circle [radius=0.08cm];
\draw [fill=black] (-4,4) circle [radius=0.08cm];

%LAYER 2
\draw [fill=black] (-0.5,3.5) circle [radius=0.08cm];
\draw [fill=black] (-2.5,4) circle [radius=0.08cm];
\draw [fill=black] (-4.5,4.5) circle [radius=0.08cm];
\draw [fill=black] (-6.5,5) circle [radius=0.08cm];

\draw [fill=black] (0.5,4) circle [radius=0.08cm];
\draw [fill=black] (-1.5,4.5) circle [radius=0.08cm];
\draw [fill=black] (-3.5,5) circle [radius=0.08cm];
\draw [fill=black] (-5.5,5.5) circle [radius=0.08cm];

\draw [fill=black] (1.5,4.5) circle [radius=0.08cm];
\draw [fill=black] (-0.5,5) circle [radius=0.08cm];
\draw [fill=black] (-2.5,5.5) circle [radius=0.08cm];
\draw [fill=black] (-4.5,6) circle [radius=0.08cm];

\draw [fill=black] (2.5,5) circle [radius=0.08cm];
\draw [fill=black] (0.5,5.5) circle [radius=0.08cm];
\draw [fill=black] (-1.5,6) circle [radius=0.08cm];
\draw [fill=black] (-3.5,6.5) circle [radius=0.08cm];

%LAYER 3
\draw [fill=black] (-1,7) circle [radius=0.08cm];
\draw [fill=black] (-3,7.5) circle [radius=0.08cm];
\draw [fill=black] (-5,8) circle [radius=0.08cm];

\draw [fill=black] (0,7.5) circle [radius=0.08cm];
\draw [fill=black] (-2,8) circle [radius=0.08cm];
\draw [fill=black] (-4,8.5) circle [radius=0.08cm];

\draw [fill=black] (1,8) circle [radius=0.08cm];
\draw [fill=black] (-1,8.5) circle [radius=0.08cm];
\draw [fill=black] (-3,9) circle [radius=0.08cm];

%LAYER 4
\draw [fill=black] (-1.5,10.5) circle [radius=0.08cm];
\draw [fill=black] (-3.5,11) circle [radius=0.08cm];

\draw [fill=black] (-2.5,11.5) circle [radius=0.08cm];
\draw [fill=black] (-0.5,11) circle [radius=0.08cm];

%LAYER 5
\draw [fill=black] (-2,14) circle [radius=0.08cm];

%DOTTED LINES
\draw [dotted] (0,0)--(-8,2)--(-4,4)--(4,2)--cycle;
\draw [dotted] (-0.5,3.5)--(-6.5,5)--(-3.5,6.5)--(2.5,5)--cycle;
\draw [dotted] (-1,7)--(-5,8)--(-3,9)--(1,8)--cycle;
\draw [dotted] (-1.5,10.5)--(-3.5,11)--(-2.5,11.5)--(-0.5,11)--cycle;


%\draw [dotted] (0,0)--(-1,7);
%\draw [dotted] (-8,2)--(-5,8);
%\draw [dotted] (-4,4)--(-3,9);
%\draw [dotted] (4,2)--(1,8);

\draw [dotted] (0,0)--(-2,14);
\draw [dotted] (-8,2)--(-2,14);
\draw [dotted] (-4,4)--(-2,14);
\draw [dotted] (4,2)--(-2,14);

\begin{footnotesize}
%LAYER 1
\node at (0.4,0) {$1$};
\node at (-1.5,0.5) {$\overline{a}$};
\node at (-3.5,1) {$\overline{ab}$};
\node at (-5.6,1.5) {$0$};
\node at (-7.6,2) {$0$};

\node at (1.3,0.5) {$0$};
\node at (-0.7,1) {$1$};
\node at (-2.4,1.5) {$\overline{b} + \overline{c}$};
\node at (-4.6,2) {$\overline{cd}$};
\node at (-6.6,2.5) {$0$};

\node at (2.3,1) {$0$};
\node at (0.3,1.5) {$0$};
\node at (-1.7,2) {$1$};
\node at (-3.4,2.5) {$\overline{d} + \overline{e}$};
\node at (-5.6,3) {$\overline{ef}$};

\node at (3.3,1.5) {$0$};
\node at (1.3,2) {$0$};
\node at (-0.7,2.5) {$0$};
\node at (-2.7,3) {$1$};
\node at (-4.7,3.5) {$\overline{f}$};

\node at (4.3,2) {$0$};
\node at (2.3,2.5) {$0$};
\node at (0.3,3) {$0$};
\node at (-1.7,3.5) {$0$};
\node at (-3.7,4) {$1$};

%LAYER 2
\node at (-0.2,3.5) {$1$};
\node at (-2.1,4) {$\overline{ac}$};
\node at (-4.0,4.5) {$\overline{abcd}$};
\node at (-6.1,5) {$0$};

\node at (0.8,4) {$0$};
\node at (-1.2,4.5) {$1$};
\node at (-2.3,5) {$\overline{bd} + \overline{be} + \overline{ce}$};
\node at (-4.9,5.5) {$\overline{cdef}$};

\node at (1.8,4.5) {$0$};
\node at (-0.2,5) {$0$};
\node at (-2.2,5.5) {$1$};
\node at (-4.1,6) {$\overline{df}$};

\node at (2.8,5) {$0$};
\node at (0.8,5.5) {$0$};
\node at (-1.1,6) {$0$};
\node at (-3.2,6.5) {$1$};

%LAYER 3
\node at (-0.7,7) {$1$};
\node at (-2.6,7.5) {$\overline{ace}$};
\node at (-4.3,8) {$\overline{abcdef}$};

\node at (0.3,7.5) {$0$};
\node at (-1.7,8) {$1$};
\node at (-3.6,8.5) {$\overline{bdf}$};

\node at (1.3,8) {$0$};
\node at (-0.7,8.5) {$0$};
\node at (-2.7,9) {$1$};

%LAYER 4
\node at (-1.2,10.5) {$1$};
\node at (-3.2,11) {$0$};

\node at (-0.2,11) {$0$};
\node at (-2.2,11.5) {$1$};

%LAYER 5
\node at (-1.7,14) {$1$};


%P's and Q's
\node at (-0.4,-0.2) {$Q_1$};
\node at (-2.4,0.3) {$Q_2$};
\node at (-4.4,0.8) {$Q_3$};
\node at (-6.4,1.3) {$Q_4$};
\node at (-8.4,1.8) {$Q_5$};

\node at (0.6,-0.3) {$P_1$};
\node at (1.6,0.2) {$P_2$};
\node at (2.6,0.7) {$P_3$};
\node at (3.6,1.2) {$P_4$};
\node at (4.6,1.7) {$P_5$};
\end{footnotesize}
\end{tikzpicture}
\caption{$R=[2] \times [3]$, $\mathcal G_R$, and the corresponding array $W=W_{ij}^{(k)}$ for $1 \leq k \leq 5$, where $\overline{a}$ denotes $a^{-1}$ for readability. (All entries at height $0$ equal $1$, and all other entries not shown are $0$.) Red and blue lines indicate quotients used to compute $\rho^0(y)=y=\phi^{-1}(x)$ and $\rho^{-1}(y)$ (apart from the topmost label), respectively.}
\label{fig:array}
\end{figure}


Theorem~\ref{birationalrowmotionformula} can be used to find an explicit formula for the entries of any power of $\rho$ applied to $y$. (Using parts (a) and (b) one can compute $\rho^{k}(y)_{ij}$ whenever $i+j-r-s \leq k < i+j$, and part (c) can be used to bring $k$ into this range.) While the birational rowmotion formulas given in \cite{musikerroby} are stated in terms of complements of paths in $R$, the formulation given here can be seen to be equivalent using Corollary~\ref{pathsinideal}.

Geometrically, Theorem~\ref{birationalrowmotionformula}(a) states that one can find the values of $\rho^{-k}(y)_{ij}$ as quotients of nearby entries inside the array $W$, and increasing the value of $k$ corresponds to a translation in the direction $(1,1,0)$ as long as these entries remain inside the defined pyramidal region of $W$. Upon passing outside this region, one needs to use part (b) to relocate inside the pyramid to the entries corresponding to the antipodal point of $R$. See Figure~\ref{fig:array}.

\begin{Ex}
Let $R = [2] \times [3]$. Let $x$ be the labeling of $R$ as in Figure~\ref{fig:array} with the array $(W_{ij}^{(k)})$ as previously described. When $(i,j)=(2,2)$, Theorem \ref{birationalrowmotionformula}(a) gives
%We construct the matrix $A$ from the induced labeling on $\mathcal{G}_R$ such that $a_{ij}$ is the sum of the weights of all paths from $P_{i}$ to $Q_{j}$. Using the Dodgson condensation formula, we construct the array in Figure \ref{fig:array}. The missing labels in the pyramid form the identity matrix at each height. We will use the array to compute the powers of rowmotion on $R = [0,1] \times [0,2]$ at $(1,1)$.
\begin{align*}
    \rho^{0}(y)_{22} &= \frac{W_{23}^{(1)}}{W_{13}^{(2)}} =  \frac{b^{-1} + c^{-1}}{(abcd)^{-1}} = acd + abd,\\
    \rho^{-1}(y)_{22} &= \frac{W_{34}^{(1)}}{W_{24}^{(2)}} = \frac{d^{-1} + e^{-1}}{(cdef)^{-1}} = cef + cdf.
\end{align*}

To compute $\rho^{-2}(y)_{22}$, $r+s-i-j = 1 < 2$, so part (a) does not apply. Instead, we apply parts (c) and (b) first to obtain
\begin{align*}
    \rho^{-2}(y)_{22} &= \rho^{3}(y)_{22} = \frac{1}{\rho^{0}(y)_{12}} = \frac{W_{12}^{(2)}}{W_{22}^{(1)}}\\
    &= (ac)^{-1}, \\
    \rho^{-3}(y)_{22} &= \rho^2(y)_{22} = \frac{1}{\rho^{-1}(y)_{12}} = \frac{W_{23}^{(2)}}{W_{33}^{(1)}} \\&= (bd)^{-1}+(be)^{-1}+(ce)^{-1},\\
    \rho^{-4}(y)_{22} &= \rho(y)_{22} = \frac{1}{\rho^{-2}(y)_{12}} =
    \frac{W_{34}^{(2)}}{W_{44}^{(1)}} \\&= (df)^{-1}.
\end{align*}
\end{Ex}

We will prove each part of Theorem~\ref{birationalrowmotionformula} separately. Part (a) follows primarily from Lemma~\ref{lemma:arraytoggle}, though some care is needed along the boundary of $R$.


\begin{proof}[Proof of Theorem~\ref{birationalrowmotionformula}(a)]
Let $z_{ij}^{(k)} = \frac{W_{k+2,i+k+1}^{(j-1)}}{W_{k+1,i+k+1}^{(j)}}$, which we wish to equal $\rho^{-k}(y)_{ij}$ for $0 \leq k \leq r+s-i-j$. We proceed by induction on $k$. When $k = 0$, $\rho^0(y)_{ij} = y_{ij} = \phi^{-1}(x)_{ij}$ is the total weight of all maximal chains in $[i] \times [j]$ (with respect to the labeling $x$). By Corollary~\ref{pathsinideal}(b), this is $\frac{W_{2,i+1}^{(j-1)}}{W_{1,i+1}^{(j)}} = z_{ij}^{(0)}$, as desired.

% consider the denominator $W_{0,i+1}^{(j+1)}$. This is the total weight of systems of nonintersecting paths in $\mathcal{G}_R$ from $P_0,\dots,P_j$ to $Q_{i+1},\dots,Q_{i+j+1}$. By Corollary~\ref{pathsinideal} this weight is $\prod\limits_{p \in \Lambda_{ij}} x_p^{-1}$.

% %Note that in any collection of nonintersecting lattice paths, the path starting at $P_\ell$ must travel to $Q_{i+\ell+1}$. Since $i \leq r$, there is a unique path from $P_0 = (0,0)$ to $Q_{i+1} = (i+1,0)$ given by traversing diagonal edges. This forces the path from $P_1$ to $Q_{i+2}$ to traverse the first $i$ diagonal edges available to it (See the figure below). After this, the only path available to the destination is horizontal edges. Continuing to construct paths in this fashion gives a unique set of nonintersecting lattice paths, which has weight $\prod\limits_{p \in \Lambda_{i,j}} x_p^{-1}$.

% The numerator $W_{1,i+1}^{(j)}$ is the weight of nonintersecting paths in $\mathcal{G}_R$ from $P_1,\dots,P_j$ to $Q_{i+1},\dots, Q_{i+j}$. By Corollary \ref{pathsinideal} the weight of each system of paths is the inverse weight of the complement of a path from $(0,0)$ to $(i,j)$ in $R$. Dividing by $\prod\limits_{p \in \Lambda_{i,j}} x_p^{-1}$ gives the sum of weights of all nonintersecting lattice paths from $(0,0)$ to $(i,j)$ in $R$. This value is $y_{i,j} = \phi^{-1}(x)_{i,j}$ as desired.

%Paths must end at the $Q_\ell$, which must end in horizontal steps after leaving the last edge in $\Lambda_{i,j}$. Letting $Q_\ell' = (i+1,\ell)$, the set of nonintersecting lattice paths from $P$ to $Q'$ are in bijection with lattice paths from $(0,0)$ to $(i,j)$ in $R$. So the weights of nonintersecting lattice paths from $P$ to $Q$ are complements of paths from $(0,0)$ to $(i,j)$ in $R$. Dividing by $\prod\limits_{p \in \Lambda_{i,j}} x_p^{-1}$ gives the sum of weights of all nonintersecting lattice paths from $(0,0)$ to $(i,j)$ as desired. 

For the inductive step, assume $k > 0$ and suppose that the claim is true for $\rho^{-k+1}(y)$ as well as for $\rho^{-k}(y)_{i'j'}$ when $(i',j') < (i,j)$. The value of $\rho^{-k}(y)$ is obtained by applying toggles from bottom to top on $\rho^{-k+1}(y)$, so the toggle at $(i,j)$ gives
\[\rho^{-k}(y)_{ij} = \left(\sum_{(i',j')\lessdot (i,j)} \rho^{-k}(y)_{i'j'}\right)\left(\;\;\;\sideset{}{^{\parallelsum}}\sum_{(i',j') \gtrdot (i,j)}\rho^{-k+1}(y)_{i'j'}\right) \cdot \frac{1}{\rho^{-k+1}(y)_{ij}}, \tag{$*$} \label{eq:toggle}\]
where an empty sum is replaced with $1$. 

We claim that we can replace the first sum in \eqref{eq:toggle} with $z_{i,j-1}^{(k)}+z_{i-1,j}^{(k)}$. If $i > 1$ and $j > 1$, then this is immediate by induction. Otherwise note that
\[
    z_{i0}^{(k)} = \frac{W_{k+2,i+k+1}^{(-1)}}{W_{k+1,i+k+1}^{(0)}} = \frac01= 0,\qquad
    z_{0j}^{(k)} = \frac{W_{k+2,k+1}^{(j-1)}}{W_{k+1,k+1}^{(j)}} = \frac{\delta_{j1}}{1} = \delta_{j1}
\]
by Proposition~\ref{prop:wproperties}(a) and (b).
Thus if exactly one of $i$ and $j$ is $1$, then one of $z_{i,j-1}^{(k)}$ and $z_{i-1,j}^{(k)}$ equals $0$ while the other is the only term in the first sum in \eqref{eq:toggle} by induction. If instead $i=j=1$, then the empty sum in \eqref{eq:toggle} is replaced with $1=0 + \delta_{11} = z_{10}^{(k)} + z_{01}^{(k)}$ as needed.

Similarly, we claim that we can replace the second (parallel) sum in \eqref{eq:toggle} with either $z_{i,j+1}^{(k-1)} \parallelsum z_{i+1,j}^{(k-1)}$, or just one of these terms if the other is undefined. If $i < r$ and $j < s$, then this is again immediate by induction (since the inequality $k-1 \leq r+s-(i+j+1)$ holds). If $i=r$ and $j < s$, then $z_{r+1,j}^{(k-1)}$ is undefined since $W_{k,r+k+1}^{(j)}=0$ by Proposition~\ref{prop:wproperties}(a), so we are left with $z_{r,j+1}^{(k-1)} = \rho^{-k+1}(y)_{r,j+1}$ by induction. If instead $i < r$ and $j=s$, then $z_{i,s+1}^{(k-1)}$ is undefined since $W_{k,i+k}^{(s+1)} = 0$ by Proposition~\ref{prop:wproperties}(c), which leaves just $z_{i+1,s}^{(k-1)} = \rho^{-k+1}(y)_{i+1,s}$ by induction. Finally, $i=r$ and $j=s$ cannot both occur since $0 < k \leq r+s-i-j$.

The final factor in \eqref{eq:toggle} is equal to $\frac{1}{z^{(k-1)}_{ij}}$ by induction. The result then follows by comparing \eqref{eq:toggle} to Lemma~\ref{lemma:arraytoggle}, using Remark~\ref{rem:arraytoggle} when needed.
%
%
% determined by applying the toggle $t_{ij}$ to the following labeling (where some elements may be missing if $(i,j)$ lies on the outer boundary of $R$):
% \[\begin{tikzpicture}
% \node(1)[w,label=below left:{$\rho^{-k}(y)_{i,j-1}$}] at (-1,-1){};
% \node(2)[w,label=below right:{$\rho^{-k}(y)_{i-1,j}$}] at (1,-1){};
% \node(3)[w,label=right:{$\rho^{-k}(y)_{ij}$}] at (0,0){};
% \node(4)[w,label=above left:{$\rho^{-k+1}(y)_{i+1,j}$}] at (-1,1){};
% \node(5)[w,label=above right:{$\rho^{-k+1}(y)_{i,j+1}$}] at (1,1){};
% \draw (1)--(3)--(2) (4)--(3)--(5);
% \end{tikzpicture}
% \]
%
% If $(i,j)$ covers 2 elements and is covered by 2 elements and if $i+j \leq r+s-k$, then we have
%
% \begin{align*}
%     &\rho^{-k+1}(y)_{i+1,j} = \frac{M_{2k,2i+2k+2,j}}{M_{2k-2,2i+2k+2,j+1}}& & \rho^{-k+1}(y)_{i,j+1} = \frac{M_{2k,2i+2k,j+1}}{M_{2k-2,2i+2k,j+2}}\\
%     & &\rho^{-k+1}(y)_{i,j} = \frac{M_{2k,2i+2k,j}}{M_{2k-2,2i+2k,j+1}} & \\
%     &\rho^{-k}(y)_{i,j-1} = \frac{M_{2k+2,2i+2k+2,j-1}}{M_{2k,2i+2k+2,j}}& & \rho^{-k}(y)_{i-1,j} = \frac{M_{2k+2,2i+2k,j}}{M_{2k,2i+2k,j+1}} \\
% \end{align*}
% Note that here the inequality condition is required to use the array to compute $\rho^{-k+1}(y)_{i+1,j}$ and $\rho^{-k+1}(y)_{i,j+1}$ with the array. Shifting the array by the vector $(2-2k,2-2k,0)$ yields:
%
% \begin{align*}
%     &z_{i+1,j} = \frac{M_{2,2i+4,j}}{M_{0,2i+4,j+1}}& & z_{i,j+1} = \frac{M_{2,2i+2,j+1}}{M_{0,2i+2,j+2}}\\
%     & &z_{i,j} = \frac{M_{2,2i+2,j}}{M_{0,2i+2,j+1}} & \\
%     &z_{i,j-1} = \frac{M_{4,2i+4,j-1}}{M_{2,2i+4,j}}& & z_{i-1,j} = \frac{M_{4,2i+2,j}}{M_{2,2i+2,j+1}} \\
% \end{align*}
% Thus by Lemma \ref{lemma:arraytoggle},
%
% \[\frac{M_{2k+2,2i+2k+2,j}}{M_{2k,2i+2k+2,j+1}} = t_{i,j}\left(\rho^{-k+1}(y)\right)_{i,j} = \rho^{-k}(y)_{i,j}\]
% %Note that in Lemma \ref{lemma:arraytoggle} we showed that this toggle did not require all of these elements covering and covered by $(i,j)$ to exist; we only need one element covering $(i,j)$ to be computable via the induction step. Consequently Part A can be used to compute $\rho^{-k}(y)_{i,j}$ if and only if $i+j \leq r+s-k$.
%
% If $(i,j)$ lies on the boundary of $R$, we claim that the octahedron recurrence still simulates toggles. Label the unlabeled elements in the lattice $x \equiv y \equiv 0$ mod $2$ by $0$. If $(i,j)=(0,0)$, let
% \begin{align*}
%     z_{0,-1} = \frac{f(4,4,-1)}{f(2,4,0)} = 0& &z_{-1,0} = \frac{f(4,2,0)}{f(2,2,1)} = 1
% \end{align*}
% which are informally the ratios of the edges of the octahedron which correspond to the nonexistent elements covered by $(0,0)$. We subsitute these into the toggle expression that we computed from the octahedron recurrence in Lemma \ref{lemma:arraytoggle}:
%
% \begin{align*}
%     &\left(z_{0,-1} + z_{-1,0}\right)\left(\rho^{-k+1}(y)_{1,0} \parallelsum \rho^{-k+1}(y)_{0,1}\right)\frac{1}{\rho^{-k+1}(y)_{0,0}} \\
%     &= \left(\rho^{-k+1}(y)_{1,0} \parallelsum \rho^{-k+1}(y)_{0,1}\right)\frac{1}{\rho^{-k+1}(y)_{0,0}} \\
%     &= \rho^{-k}(y)_{0,0}
% \end{align*}
%
% The case of join irreducibles is similar. Now consider the case of $(r,j)$ where $r+j \leq r+s-k$, so that $\rho^{-k+1}(y)_{r,j+1}$ is computable by induction. The edge corresponding to the nonexistent element $(r+1,j)$ exits the array from above. Let $\frac{1}{z_{r+1,j}} = 0$. From the parallel sum in the toggle relation yielded by the octahedron recurrence, we have
%
% \[\frac{1}{ \frac{1}{\rho^{-k+1}(y)_{r,j+1}} + \frac{1}{z_{r+1,j}}} = \rho^{-k+1}(y)_{r,j+1}\]
% Substituting this into the toggle expression yields the toggle at $(r,j)$.
%
% Finally, if $i+j = r+s-k+1$, then by induction $\rho^{-k+1}$ is not computable via Part A of the rowmotion formula at any element covering $(i,j)$. In fact, the associated edges of the octahedron exit the top of the array. In this case, the parallel sum in the toggle relation yields division by 0. Hence Part A cannot compute $\rho^{-k}(y)_{i,j}$.
\end{proof}

Next we prove part (b). In some sense, this reflects two symmetries: toggling is respected by dualizing a poset and inverting each label, and the octahedron recurrence is respected by reflecting over the plane perpendicular to the main diagonal.

\begin{proof}[Proof of Theorem~\ref{birationalrowmotionformula}(b)]
Note that if $0 < k < i+j$, then $0 \leq i+j-k-1 \leq r+s-(r+1-i)-(s+1-j)$, so the right hand side of (b) will satisfy the condition of part (a), as claimed.

Via the change of coordinates $z = \rho^{k-1}(y)$, it suffices to prove the case when $k=1$. %, that is,
%\[\rho(y)_{i,j} = \frac{1}{\rho^{-i-j}(y)_{r-i,s-j}}.\]
By part (a),
\[\rho^{2-i-j}(y)_{r+1-i,s+1-j} = 
    \frac{W_{i+j,r+j}^{(s-j)}}{W_{i+j-1,r+j}^{(s-j+1)}}.\]
%The denominator is the sum of the weights of all nonintersecting lattice paths in $\mathcal{G}_R$ from $P_{i+j},\dots,P_{i+s}$ to $Q_{r+j+1},\dots,Q_{r+s+1}$. By Corollary \ref{pathsinideal} the weight of these paths is $\prod\limits_{z \in V_{i,j}} x_z^{-1}$. The numerator is the sum of the weights of all nonintersecting lattice paths in $\mathcal{G}_R$ from $P_{i+j+1},\dots, P_{i+s}$ to $Q_{r+j+1},\dots,Q_{r+s}$. 
%By Corollary~\ref{pathsinideal}, the weight of these paths is the sum of the inverse weights of complements of paths from $(i,j)$ to $(r,s)$ in $V_{i,j}$ (i.e. maximal chains). Let $\mathcal{P}$ denote paths in $V_{i,j}$ from $(i,j)$ to $(r,s)$ in $R$. Then
By Corollary~\ref{pathsinideal}, this is the total weight of all maximal chains in $[i,r] \times [j,s]$ in $R$ (with respect to the labeling $x$). Thus
%\[\rho^{-i-j}(y)_{r-i,s-j} = \frac{\sum\limits_{L \in \mathcal{P}} \prod\limits_{z \in V_{i,j} \setminus L} x_z^{-1}}{\prod\limits_{z \in V_{i,j}} x_z^{-1}} = \sum\limits_{L \in \mathcal{P}} \prod\limits_{z \in L} x_z = \left(\phi^*\right)^{-1}(x)_{i,j} = \frac{1}{\rho(y)_{i,j}}.\qedhere\]
\[\rho^{2-i-j}(y)_{r+1-i,s+1-j} = \left(\phi^*\right)^{-1}(x)_{ij} = \frac{1}{\rho(y)_{ij}}\]
by Lemma~\ref{lemma:dualtransfer}.
\end{proof}

%\begin{figure}
%\begin{tikzpicture}
%DIAGONAL EDGES
%\foreach \x in {0,...,3}{
%\draw (\x,\x)--(-2+\x,2+\x);
%}

%HORIZONTAL EDGES
%\draw (1,1)--(-1,1);
%\draw (2,2)--(-2,2);
%\draw (3,3)--(-1,3);
%\draw (2,4)--(-0,4);

%CIRCLES
%\draw [fill=black] (0,0) circle [radius=0.08cm];
%\draw [fill=black] (-1,1) circle [radius=0.08cm];
%\draw [red, fill=red] (-2,2) circle [radius=0.08cm];

%\draw [fill=black] (1,1) circle [radius=0.08cm];
%\draw [red, fill=red] (0,2) circle [radius=0.08cm];
%\draw [red, fill=red] (-1,3) circle [radius=0.08cm];

%\draw [red, fill=red] (2,2) circle [radius=0.08cm];
%\draw [red, fill=red] (1,3) circle [radius=0.08cm];
%\draw [red, fill=red] (0,4) circle [radius=0.08cm];

%\draw [red, fill=red] (3,3) circle [radius=0.08cm];
%\draw [red, fill=red] (2,4) circle [radius=0.08cm];
%\draw [fill=black] (1,5) circle [radius=0.08cm];

%LABELS
%\node at (2.4,2.3) {$P_2$};
%\node at (3.4,3.3) {$P_3$};
%\node at (2.4,4.3) {$P_4 = P'_4$};

%\node at (0.4,2.3) {$P'_2$};
%\node at (1.4,3.3) {$P'_3$};

%\node at (-1.6,2.3) {$Q_1$};
%\node at (-0.6,3.3) {$Q_2$};
%\node at (0.4,4.3) {$Q_3$};

%\draw [red, thick] (2,2)--(0,2);
%\draw [red, thick] (3,3)--(1,3);
%\end{tikzpicture}
%\caption{WHICH FIGURE IS IT}
%\end{figure}




%$i+j > r+s-k$, then 
%
%\[I+J = r-i+s-j \leq r-i+s-j+k = r+s-K\]
%
%\noindent where $I = r-i$, $J = s-j$, and $K = i+j-k$, so %$\rho^{k-i-j}(y)_{r-i,s-j}$ satisfies the condition in Part A of the birational rowmotion formula. \pushQED{\qed} \qedhere \popQED

Finally, we deduce part (c) from part (b).
%For completeness, we close this section with the computation appearing in \cite{musikerroby} of the period of birational rowmotion on the rectangle.
%
%\begin{Cor}
%Let $R = [0,r] \times [0,s]$. Then $\rho$ has period $r+s+2$.
%\end{Cor}

\begin{proof} [Proof of Theorem~\ref{birationalrowmotionformula}(c)]
Apply Theorem~\ref{birationalrowmotionformula}(b) twice:
\begin{align*}
    \rho^{k}(y)_{i,j} &= \left(\rho^{k-i-j+1}(y)_{r+1-i,s+1-j}\right)^{-1}\\ 
    &= \left[\left(\rho^{k-i-j+1-(r+1-i)-(s+1-j)+1}(y)_{i,j}\right)^{-1}\right]^{-1}\\
    & = \rho^{k-r-s}(y)_{i,j}.\qedhere
\end{align*}
\end{proof}

In the next two sections, we will show how to use the perspective relating rowmotion and the octahedron recurrence to prove various identities about rowmotion.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{A chain shifting lemma} \label{section:chainshifting}

In this section we will use the birational rowmotion formula to derive a chain shifting lemma, which is a birational generalization of the rowmotion action on the Stanley--Thomas word appearing in \cite{josephroby1}. %This result is subtraction-free, so tropicalizing easily gives the piecewise linear analogue. 

\subsection{Chain shifting}

Recall from Section~\ref{sec:paths} that if $I$ is an interval of $R$ and $x$ is a labeling of $R$, then $w_I^{(k)}(x)$ is the total weight of the collections of $k$ nonintersecting paths in $\mathcal P_I^{(k)}$. We will prove the following lemma relating these sums in two labelings $x$ and $\phi \circ \rho^{-1} \circ \phi^{-1}(x)$.

%For $u_1 \leq u_2$ and $v_1 \leq v_2$, let $\mathcal{P}_{u_1,v_1}^{u_2,v_2}(k)$ denote the set of all unions of $k$ nonintersecting lattice paths from $(u_1,v_1), (u_1+1,v_1),\dots,(u_1+k-1,v_1)$ to $(u_2-k+1,v_2),(u_2-k+2,v_2),\dots,(u_2,v_2)$.

\begin{Lemma}[Chain shifting] \label{chainshift}
Let $R = [r] \times [s]$ and let $1 < u \leq v \leq s$. Define intervals $I = [r] \times [u,v]$ and $I' = [r] \times [u-1,v-1]$ of $R$. Then for any labeling $x \in \mathbb R^{R}_{>0}$, \[w_{I}^{(k)}(x) = w_{I'}^{(k)}(\phi \circ \rho^{-1} \circ \phi^{-1}(x)).\]
(The symmetric statement obtained by reflecting $R$ also holds.)
%
%\[\sum\limits_{ \mathcal{L} \in \mathcal{P}_{0,u}^{r,v}(k) } \prod\limits_{z \in L} x_z = \sum\limits_{ \mathcal{L} \in \mathcal{P}_{0,u-1}^{r,v-1}(k)} \prod\limits_{z \in L} \left( \phi \circ \rho^{-1} \circ \phi^{-1} \right)(x)_z \]
%
%\noindent for any $x \in \mathbb{R}_{> 0}^{|R|}$.
\end{Lemma}

%\begin{Lemma}[Chain Shifting] %\label{chainshift}
%Let $R = [0,r] \times [0,s]$ and let $0 \leq u \leq u + v \leq s$. Then

%\[\sum\limits_{ \mathcal{L} \in \mathcal{P}_{0,u}^{r,u+v}(k) } \prod\limits_{\substack{L \in \mathcal{L} \\ z \in L}} x_z = \sum\limits_{ \mathcal{L} \in \mathcal{P}_{0,0}^{r,v}(k)} \prod\limits_{\substack{L \in \mathcal{L} \\ z \in L} } \left( \phi \circ \rho^{-u} \circ \phi^{-1} \right)(x)_z \]

%\noindent for any $x \in \mathbb{R}_{> 0}^{|R|}$.
%\end{Lemma}

%On the left hand side we have the sum of all weights among all chains from $(u,0)$ to $(u+v,s)$. On the right hand side we see that after applying the inverse of rowmotion $u$ times conjugated by the transfer map, the chains we sum over to obtain this same value have shifted $u$ units in the rectangle.

%On the left hand side we have the sum of all weights of all nonintersecting lattice paths from $\{(0,u),\dots,(0,u+k-1)\}$ to $\{(r,v-k+1),\dots,(r,v)\}$. On the right hand side we see that after applying $\phi \circ \rho^{-1} \circ \phi^{-1}$, the paths we sum over to obtain this same value travel from $\{(0,u-1),\dots,(0,u+k-2)\}$ to $\{(r,v-k),\dots,(r,v-1)\}$, so the endpoints of these paths have shifted 1 unit in the rectangle.
Note that the intervals $I$ and $I'$ differ only by shifting by one unit in $R$.

\begin{Ex}


\begin{figure}
\begin{tikzpicture}[scale = 0.7]

\foreach \x in {0,10.4}{
%HORIZONTAL LINES
\draw (0+\x,0)--(2+\x,2);
\draw (-1+\x,1)--(1+\x,3);

%VERTICAL LINES
\draw (0+\x,0)--(-1+\x,1);
\draw (1+\x,1)--(0+\x,2);
\draw (2+\x,2)--(1+\x,3);

%POSET NODES
\draw [fill=black] (0+\x,0) circle [radius=0.1cm];
\draw [fill=black] (1+\x,1) circle [radius=0.1cm];
\draw [fill=black] (2+\x,2) circle [radius=0.1cm];

\draw [fill=black] (-1+\x,1) circle [radius=0.1cm];
\draw [fill=black] (0+\x,2) circle [radius=0.1cm];
\draw [fill=black] (1+\x,3) circle [radius=0.1cm];
};

\node at (0.35,0) {$a$};
\node at (1.45,1) {$c$};
\node at (2.3,2) {$e$};

\node at (-0.6,1) {$b$};
\node at (0.4,2) {$d$};
\node at (1.4,3) {$f$};

%ARROW
%\draw [xshift=4.25 cm, yshift=1.5cm] (0,0.1)--(1,0.1)--(1,0.2)--(1.5,0)--(1,-0.2)--(1,-0.1)--(0,-0.1)--cycle;
\draw[->] (3,1.5)--node[above]{$\phi \circ \rho^{-1} \circ \phi^{-1}$}(7,1.5);
%\node at (5.25,2.1) {$\phi \circ \rho^{-1} \circ \phi^{-1}$};

\node at (11,0) {$\frac{bc}{b+c}$};
\node at (12.5,1) {$\frac{de(b+c)}{bd+cd+ce}$};
\node at (13.8,2) {$\frac{f(bd+cd+ce)}{ce}$};

\node at (8.6,1) {$\frac{d(b+c)}{b}$};
\node at (8.95,2) {$\frac{f(bd+cd+ce)}{d(b+c)}$};
\node at (9.8,3.1) {$\frac{1}{af(bd+cd+ce)}$};
\end{tikzpicture}
\caption{Two labelings $x$ and $z = \phi \circ \rho^{-1} \circ \phi^{-1}(x)$.}
\label{fig:shifting}
\end{figure}

Consider the labeling $x$ of $R = [2] \times [3]$ and its image $z = \phi \circ \rho^{-1} \circ \phi^{-1}(x)$ in Figure~\ref{fig:shifting}. Then
\[z_{11}z_{21} = \frac{bc}{b+c}\cdot \frac{d(b+c)}{b} = cd = x_{12}x_{22}.\]
Similarly, we can compute all of the products along the rows and columns of $R$:
\begin{align*}
    z_{12}z_{22} &= x_{13}x_{23} & z_{13}z_{23} &= (x_{11}x_{12}x_{13})^{-1} \\
    (z_{11}z_{12}z_{13})^{-1} &= (x_{21}x_{22}x_{23})^{-1}&(z_{21}z_{22}z_{23})^{-1} &= x_{11}x_{21}
\end{align*}

%\[z_{0,1}z_{1,1} = \frac{de(b+c)}{bd+cd+ce} \frac{f(bd+cd+ce)}{d(b+c)} = ef = x_{0,2}x_{1,2}\]
%\[z_{0,2}z_{1,2} = \frac{f(bd+cd+ce)}{ce} \frac{1}{af(bd+cd+ce)} = \frac{1}{ace} = \frac{1}{x_{0,0}x_{0,1}x_{0,2}}\]
%\[\frac{1}{z_{0,0}z_{0,1}z_{0,2}} = \frac{b+c}{bc}\frac{bd+cd+ce}{de(b+c)}\frac{ce}{f(bd+cd+ce)} = \frac{1}{bdf} = \frac{1}{x_{1,0}x_{1,1}x_{1,2}}\]
%\[\frac{1}{z_{1,0}z_{1,1}z_{1,2}} = \frac{b}{d(b+c)}\frac{d(b+c)}{f(bd+cd+ce)}af(bd+cd+ce) = ab = x_{0,0}x_{1,0}\]

From the above computation, we see that $\phi \circ \rho^{-1} \circ \phi^{-1}$ rotates the birational Stanley--Thomas word
\[(x_{11}x_{21}, \quad x_{12}x_{22}, \quad x_{13}x_{23},\quad  (x_{11}x_{12}x_{13})^{-1},\quad (x_{21}x_{22}x_{23})^{-1} ).\]
%\[\left(ab, cd, ef, \frac{1}{ace}, \frac{1}{bdf} \right).\]

However, the shifting of chain sums happens more generally for sums of chains within subrectangles of $R$. For instance, if $I = [2] \times [2,3]$, $I' = [2] \times [1,2]$, and $k=1$, then we have
\begin{align*}
    z_{11}z_{21}z_{22}+z_{11}z_{12}z_{22} &= \frac{bc}{b+c}\cdot \frac{f(bd+cd+ce)}{d(b+c)} \left( \frac{d(b+c)}{b} + \frac{de(b+c)}{bd+cd+ce} \right) \\
    &= \frac{cf(bd+cd+ce)}{b+c} + \frac{bcef}{b+c}\\
    &= cdf+cef \\
    &= x_{12}x_{22}x_{23}+x_{12}x_{13}x_{22}.
\end{align*}
\end{Ex}

We now prove Lemma \ref{chainshift}. As we will see, it can be thought of as a manifestation of the translation invariance of the octahedron recurrence.

\begin{proof}[Proof of Lemma~\ref{chainshift}] Let $x$ be a labeling of $R$, let $y = \phi^{-1}(x)$, and let $(W_{ij}^{(k)})$ be the corresponding three-dimensional array. Also define $\widetilde x = \phi \circ \rho^{-1}\circ \phi^{-1}(x)$, $\widetilde y = \phi^{-1}(\widetilde x) = \rho^{-1}(y)$, and $(\widetilde W_{ij}^{(k)})$ the corresponding array.

%Label the edges of $\mathcal{G}_R$ such that $(i,j) \to (i+1,j)$ is labeled $x_{i,j}^{-1}$ and $(i,j) \to (i+1,j-1)$ is labeled 1. Let $A$ be the matrix with entries $A_{ij}$ given by the sum of weights of all paths from $P_i$ to $Q_j$. Similarly, let $y' = \rho^{-1}(y)$, let $x' = \phi(y')$, and $A'$ be the associated matrix for this labeling.

We claim that $\widetilde W_{ij}^{(k)} = W_{i+1,j+1}^{(k)}$ for $1 \leq i,j \leq r+s-k$. Note that by the octahedron recurrence/Dodgson condensation formula, it suffices to prove the case $k=1$ since the entries for $k > 1$ are determinants of submatrices of these entries at height $1$. 

Assume $k=1$. If $i \geq j$, then the claim follows by Proposition~\ref{prop:wproperties}. If $i < j$, then applying Theorem~\ref{birationalrowmotionformula} twice gives
\[\widetilde W_{ij}^{(1)} = \frac{1}{\rho^{-i+1}(\widetilde y)_{j-i,1}} = \frac{1}{\rho^{-i}(y)_{j-i,1}} = W^{(1)}_{i+1,j+1},\] which proves the claim.

To complete the proof, we need only observe that applying Corollary~\ref{pathsinideal}(b) to the two sides of the desired equality expresses them as quotients of two entries of the form $W_{i+1,j+1}^{(k)}$ or $\widetilde W_{ij}^{(k)}$, respectively, which are then equal by the claim.
% For $r+s+1 > i > j$, there are no paths in $\mathcal{G}_R$ from $P_i$ to $Q_j$, so $A'_{i,j} = 0$. Via the same argument, $A_{i+1,j+1}=0$, so in particular $A_{i+1,j+1} = A'_{i,j}$. When $i=j < r+s+1$, the only path from $P_i$ to $Q_j$ is the path of horizontal steps, so $A'_{i+1,j+1} = 1$. Similarly $A_{i,j} = 1$, so in particular $A_{i+1,j+1} = A'_{i,j}$.
%
% If $i < j$, let $K = i$, $I=j-i-1$, and $J=0$. Let $M'$ denote the array generated by $A'$ and the Dodgson condensation formula and analogously define $W'_a^b(c)$. Then
%
%\begin{align*}
%     \frac{M'_{2i+2,2j,0}}{M'_{2i,2j,1}} &=\frac{1}{A'_{ij}} \\
%     &= \frac{W'_{K+1}^{I+K+1}(J)}{W'_K^{I+K+1}(J+1)} \\
%     &=\rho^{-K}(y')_{I,J} \\
%     &=\rho^{-K-1}(y)_{I,J}\\
%     &= \frac{W'_{K+2}^{I+K+2}(J)}{W'_{K+1}^{I+K+2}(J+1)} \\
%     &= \frac{1}{A_{i+1,j+1}}
%\end{align*}
%In summary, $A_{i+1,j+1}=A'_{i,j}$ whenever $i+j < r+s+1$. By Dodgson condensation, $M'_{2i,2j,k} = M_{2i+2,2j+2,k}$ whenever $i+j < r+k+1-k$. This implies that if $1 \leq b \leq a$ and $b+k \leq r+s+1$, then the weight of all paths from some $P_a,\dots,P_{a+k}$ to $Q_b,\dots,Q_{b+k}$ with graph weighted by $x$ is equal to the weight of all paths from $P_{a-1},\dots,P_{a+k-1}$ to $Q_{b-1},\dots,Q_{b+k-1}$ with graph weighted by $x'$. Note that this in particular implies that
%
%\[\prod\limits_{z \in [(0,b),(r,a+k)]} x_z = \prod\limits_{z \in [(0,b-1),(r,a+k-1)]} x'_z.\]
%
%Multiplying the weights of the nonintersecting paths in $\mathcal{G}_R$ by these monomials yields the result on lattice paths in $R$.
\end{proof}

%\begin{proof}
%For $k=1$, we know that $\rho^{0}(y)_{r,v} = \sum\limits_{\mathcal{L} \in \mathcal{P}_{0,0}^{r,v}(1)} \prod\limits_{z \in \mathcal{L}} x_z$. Each application of inverse rowmotion increases the subscript and superscript on $W$ in part A of the rowmotion formula. This corresponds to shifting the region the lattice paths lie in in the $(0,1)$ direction in $R$. 

%Let $x \in \mathbb{R}_{>0}^{R}$ and let $y = \phi^{-1}(x)$. Let $0 \leq u \leq u+v \leq s$. We note that the right hand side of the equation simplifies to $\rho^{-u}(y)_{r,v}$. Since $i+j = r+v \leq r+s-u = r+s-k$, we use part A of the inverse rowmotion formula:

%\[\rho^{-u} = \frac{W_{1+u}^{r+1+u}(v)}{W_{u}^{r+1+u}(v+1)}.\]

%The denominator is the sum of the weights of all nonintersecting lattice paths from $(0,u),\dots,(0,u+v)$ to $(r+1,u),\dots,(r+1,u+v)$. These steps must all be diagonal steps, so the weight is $\prod\limits_{z \in \lozenge_{u,0}^{r,u+v}} x_z^{-1}$.

%Meanwhile, the numerator is the sum of the weights of all nonintersecting lattice paths from $(0,u+1),\dots,(0,u+v)$ to $(r+1,u),\dots,(r+1,u+v-1)$ in $\mathcal{G}_R$. The weight of each such set of paths is the complement of the weight of a single path in $R$ from $(0,u)$ to $(r,u+v)$. Consequently,

%\[\rho^{-u}(y)_{r,v} = \frac{ \sum\limits_{\mathcal{L} \in \mathcal{P}_{0,u}^{r,u+v}(1)} \prod\limits_{z \in \lozenge_{0,u}^{r,u+v} \setminus \mathcal{L}} x_z^{-1} }{ \prod\limits_{z \in \lozenge_{u,0}^{r,u+v}} x_z^{-1} } = \sum\limits_{\mathcal{L} \in \mathcal{P}_{0,u}^{r,u+v}(1)} \prod\limits_{z \in \mathcal{L}} x_z \]

%For the case of $k$ nonintersecting lattice paths, let $a_i = (u+i-1,0)$ and let $b_i = (u+v-k+i,s)$. Let $a_i' = (i-1,0)$ and let $b_i' = (v-k+i,s)$. Then the case of a single lattice path gives $e(a_i,b_j) = e(a_i',b_j')$, so the matrices in the Lindstr\"om lemma given by these are the same. The result follows.
%\end{proof}

%Also, as an easy consequence of the chain shifting lemma, $\rho^{-1}$ shifts this sum downward in the poset by 1. That is, if $1 \leq u \leq v \leq s$, then

%$$\sum\limits_{ \mathcal{L} \in \mathcal{P}_{0,u}^{r,v}(k) } \left( \prod\limits_{L \in \mathcal{L}} \prod\limits_{z \in L} x_z \right) = \sum\limits_{ \mathcal{L} \in \mathcal{P}_{0,u-1}^{r,v-1}(k)} \left( \prod\limits_{L \in \mathcal{L} } \prod\limits_{z \in L } \left( \phi \circ \rho^{-1} \circ \phi^{-1} \right)(x)_z \right).$$

%TODO: FIX THE REST OF THE SECTION AND MAKE IT NOT ABSOLUTELY TERRIBLE


%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Generalized Stanley--Thomas words}
Given Lemma~\ref{chainshift}, it is natural to want to generalize the definition of the Stanley--Thomas word to include more words that are cyclically shifted by the action of rowmotion. 

The usual birational Stanley--Thomas word is obtained as the orbit of $\prod_{j=1}^s x_{1j} = \phi^{-1}(x)_{1s}$ under the action of $\phi \circ \rho \circ \phi^{-1}$ on $x$, or, put another way, the orbit of $y_{1s}$ under the action of $\rho$ on $y=\phi^{-1}(x)$. We can generalize this by replacing $y_{1s}$ with any other value $y_{is}$ or $y_{rj}$ lying on the upper boundary of $R$.

\begin{Def}
Let $x \in \mathbb R^R_{>0}$, and let $y=\phi^{-1}(x)$. A \emph{generalized Stanley--Thomas word} for $x$ is a sequence of one of the following two forms:
\begin{align*}
    ST_{i}(x)&=(y_{is}, \quad \rho^{-1}(y)_{is}, \quad \rho^{-2}(y)_{is}, \quad \dots, \quad \rho^{-r-s+1}(y)_{is}),\\
    \overline{ST}_j(x)&=(y_{rj}, \quad \rho^{-1}(y)_{rj}, \quad \rho^{-2}(y)_{rj}, \quad \dots, \quad \rho^{-r-s+1}(y)_{rj}).
\end{align*}
\end{Def}

The usual birational Stanley--Thomas word is therefore $ST_{1}$. The reason for choosing these words in particular is that they have a clean description in terms of $x$. We consider the case of $ST_i$ below; the other case is similar.


Recall that $y_{is} = \phi^{-1}(x)_{is} = w^{(1)}_{[i]\times [s]}(x)$. By Lemma~\ref{chainshift}, 
\[\rho^{-1}(y)_{is} = w^{(1)}_{[i] \times [s]}(\phi \circ \rho^{-1}(y)) = w^{(1)}_{[2,i+1] \times [s]}(x).\]
Iterating, we find that for $0 \leq k \leq r-i$,
\[\rho^{-k}(y)_{is} = w^{(1)}_{[k+1,k+i] \times [s]}(x).\]
To find the remaining coordinates, we apply Theorem~\ref{birationalrowmotionformula} (c), (b), and (a) in order to find that, for $r-i<k<r+s$,
\[\rho^{-k}(y)_{is} = \rho^{r+s-k}(y)_{is} = \frac{1}{\rho^{r-i-k+1}(y)_{r+1-i,1}} = W_{k+i-r,k+1}^{(1)}.\]

While $W_{k+i-r,k+1}^{(1)}$ is defined in terms of paths in $\mathcal G_R$, it is also easy to describe it in terms of the labeling $x$ directly. Choosing the northwest edges in a path in $\mathcal G_R$ from $P_{k+i-r}$ to $Q_{k+1}$ corresponds to choosing elements of $R$ at ranks $k+i-r+1,\dots, k+1$ traveling to the northwest (i.e. with increasing first coordinate), not necessarily using the edges of $R$. In other words, define
\[\omega_{ab} = \omega_{ab}(x) = \sum (x_{i_aj_a}x_{i_{a+1}j_{a+1}} \cdots x_{i_bj_b})^{-1},\]
where the sum ranges over all sequences $(i_a,j_a), (i_{a+1},j_{a+1}), \dots, (i_b,j_b) \in R$ such that $i_t+j_t = t$ for all $t$, and $i_a < i_{a+1} < \cdots < i_b$ (or equivalently $j_a \geq j_{a+1} \geq \cdots \geq j_b$). Then we have proved the following proposition.

\begin{Prop} \label{prop:st}
For any $x \in \mathbb R^R_{>0}$, the generalized Stanley--Thomas word $ST_i = ST_i(x)$ is given by
\begin{equation*}
    ST_i = (w^{(1)}_{[1,i] \times [s]}, \; w^{(1)}_{[2,i+1] \times [s]}, \; \dots, \; w^{(1)}_{[k+1,k+i] \times [s]}, \;
    \omega_{2,r-i+2}, \; \omega_{3,r-i+3}, \; \dots, \; \omega_{i+s,r+s}).
\end{equation*}
\end{Prop}
An analogous formula for $\overline{ST}_j$ can be obtained by reflecting $R$.

\begin{Ex} \label{ex:st}
Let $R = [3] \times [3]$ and $x \in \mathbb R^R_{>0}$. The generalized Stanley--Thomas word $ST_2$ is 
\[\ST_2 = (w^{(1)}_{[1,2] \times [3]}, \;w^{(1)}_{[2,3] \times [3]}, \;\omega_{23},\; \omega_{34},\; \omega_{45},\; \omega_{56}).\]
In the $x$-coordinates we have the following:
\begin{align*}
    w^{(1)}_{[1,2] \times [3]} &= x_{11}x_{21}x_{22}x_{23}+x_{11}x_{12}x_{22}x_{23}+x_{11}x_{12}x_{13}x_{23},
    \\
    w^{(1)}_{[2,3] \times [3]} &= x_{21}x_{31}x_{32}x_{33}+x_{21}x_{22}x_{32}x_{33}+x_{21}x_{22}x_{23}x_{33},\\
    \omega_{23} &= \frac{1}{x_{11}x_{21}}, \\
    \omega_{34} &= \frac{1}{x_{12}x_{22}} + \frac{1}{x_{12}x_{31}} + \frac{1}{x_{21}x_{31}}, \\
    \omega_{45} &= \frac{1}{x_{13}x_{23}} + \frac{1}{x_{13}x_{32}} + \frac{1}{x_{22}x_{32}}, \\
    \omega_{56} &= \frac{1}{x_{23}x_{33}}.
\end{align*}
See Figure~\ref{fig:st} for a visualization of this example.
\end{Ex}

\begin{figure}
    \centering
    \begin{tikzpicture}[scale=.82]
        \begin{scope} [shift={(3.8,4)},rotate=45]
            \draw (1,1) grid (3,3);
            \foreach \x in {1,...,3}
                \foreach \y in {1,...,3}
                    \node[w,label=right:{$x_{\x\y}$}] (\x\y) at (\y,\x){};
            \draw[very thick,blue] (1,1) grid (3,2);
            \foreach \z in {11,12,13,21,22,23}
                \node[w,blue] at (\z){};
        \end{scope}
        \begin{scope} [shift={(8.2,4)},rotate=45]
            \draw (1,1) grid (3,3);
            \foreach \x in {1,...,3}
                \foreach \y in {1,...,3}
                    \node[w] (\x\y) at (\y,\x){};
            \draw[very thick,blue] (1,2) grid (3,3);
            \foreach \z in {21,22,23,31,32,33}
                \node[w,blue] at (\z){};
        \end{scope}
        \begin{scope} [rotate=45]
            \draw (1,1) grid (3,3);
            \foreach \x in {1,...,3}
                \foreach \y in {1,...,3}
                    \node[w] (\x\y) at (\y,\x){};
            \draw[very thick,red] (11)--(21);
            \foreach \z in {11,21,12}
                \node[w,red] at (\z){};
        \end{scope}
        \begin{scope} [shift={(4,0)},rotate=45]
            \draw (1,1) grid (3,3);
            \foreach \x in {1,...,3}
                \foreach \y in {1,...,3}
                    \node[w] (\x\y) at (\y,\x){};
            \draw[very thick,red] (22)--(12)--(31)--(21);
            \foreach \z in {22,12,31,21,13}
                \node[w,red] at (\z){};
        \end{scope}
        \begin{scope} [shift={(8,0)},rotate=45]
            \draw (1,1) grid (3,3);
            \foreach \x in {1,...,3}
                \foreach \y in {1,...,3}
                    \node[w] (\x\y) at (\y,\x){};
            \draw[very thick,red] (23)--(13)--(32)--(22);
            \foreach \z in {23,13,32,22,31}
                \node[w,red] at (\z){};
        \end{scope}
        \begin{scope} [shift={(12,0)},rotate=45]
            \draw (1,1) grid (3,3);
            \foreach \x in {1,...,3}
                \foreach \y in {1,...,3}
                    \node[w] (\x\y) at (\y,\x){};
            \draw[very thick,red] (23)--(33);
            \foreach \z in {23,33,32}
                \node[w,red] at (\z){};
        \end{scope}
    \end{tikzpicture}
    \caption{Computation of $ST_2$ in $R=[3] \times [3]$ as in Example~\ref{ex:st}. In the first two diagrams, the sums of the weights of the maximum length chains in the blue posets are $w_{[1,2] \times [3]}^{(1)}$ and $w_{[2,3] \times [3]}^{(1)}$, respectively. In the remaining four diagrams, the sums of the reciprocals of the weights of the maximum length chains in the red posets are $\omega_{23}$, $\omega_{34}$, $\omega_{45}$, and $\omega_{56}$, respectively.}
%   
%    The first two diagrams indicate the total weight of maximal chains in intervals that shift according to Lemma~\ref{chainshift}. The last four diagrams indicate the total inverse weight of northwesterly collections of elements at specified ranks used to find $\omega_{ab}$.}
    \label{fig:st}
\end{figure}

As noted in \cite{josephroby1}, the cyclic rotation of $ST_1$ is not sufficient to uniquely determine birational rowmotion. However, the cyclic rotation of all $ST_i$ and $\overline{ST}_j$ does uniquely determine birational rowmotion, and in fact the chain shifting lemma alone nearly suffices. We make this statement precise in Section \ref{section:greenestheorem}.


\iffalse
\subsection{old Generalized Stanley--Thomas words}

Given Lemma~\ref{chainshift}, it is natural to want to generalize the definition of the Stanley--Thomas word to include more words that are cyclically shifted by the action of rowmotion. 
%Let $0 \leq i_1,i_2 \leq r$ and $0 \leq j_1,j_2 \leq s$ and let $0 \leq k \leq \min(i_2-i_1,j_2-j_1)$. Let
%\[S_{i_1,j_1}^{i_2,j_2}(k) = \sum\limits_{\mathcal{L} \in \mathcal{P}_{i_1,j_1}^{i_2,j_2}(k)} \prod\limits_{z \in \mathcal{L}} x_z\]
%and
%\[\widetilde{S}_{i_1,j_1}^{i_2,j_2}(k) = \sum\limits_{\mathcal{L} \in \mathcal{P}_{i_1,j_1}^{i_2,j_2}(k)} \prod\limits_{z \not\in \mathcal{L}} \frac{1}{x_z}.\]
%If $k = 1$, we supress the $k$ from the notation.


\begin{Def}
Let $x \in \mathbb{R}^R_{>0}$. For $1 \leq j \leq s$, the $j$th \emph{generalized Stanley--Thomas word} is
\[\ST_j(x)_k = \begin{cases} \frac{ W_{k+1,r+k}^{(j-1)} }{ W_{k,r+k}^{(j)} } &\text{if } 1 \leq k \leq s-j+1, \\ W_{k-s+j-1,k-s+j}^{(s-j+1)} &\text{if } s-j+1 < k \leq r+s. \end{cases}\]
\end{Def}

%\rho^(r+s+1-k)(y)_{rj} = 1/\rho^{s+2-k-j}(y)_{1,s+1-j} = 1/(W^{s-j}_{k+j-s,k+j-s}/W^{s-j+1}_{k+j-s-1,k+j-s})
%1 <= r+s+1-k < r+j

Note that if we set $j=1$, then by Corollary~\ref{pathsinideal},
\[\frac{ W_{k+1,r+k}^{(0)} }{ W_{k,r+k}^{(1)} } = w^{(1)}_{[r]\times\{k\}} = \prod_{i=1}^r x_{ik},\]
while
\[W_{k-s,k-s+1}^{(s)} = \frac{1}{w_{\{k-s\}\times [s]}^{(1)}} = \prod_{i=1}^s (x_{k-s,i})^{-1}.\]
%we obtain
%\[\text{ST}_0(x)_k = \begin{cases} \frac{ W_{k+1,r+k+1}^{(0)} }{ W_{k,r+k+1}^{(1)} } &\text{if } 0 \leq k \leq s, \\ W_{k-s-1,k-s}^{(s+1)} &\text{if } s+1 \leq k \leq r+s+1. \end{cases}\]
%By convention $W_{k+1,r+k+1}^{(0)} = 1$. There exists a unique path in $\mathcal{G}_R$ from $P_k$ to $Q_{r+k+1}$, which consists of all diagonal edges weighted $\frac{1}{x_{ik}}$. So $W_{k,r+k+1}^{(1)} = \prod\limits_{i=0}^r \frac{1}{x_{ik}}$. 
%
%
%To compute the last sum, if $I = [(k-s-1,0),(k-s-1,s)]$, then by Corollary~\ref{pathsinideal} $w_I^{(1)} = \frac{1}{W_{k-s-1,k-s}^{(s+1)}}$. Computing $w_I^{(1)}$ yields $W_{k-s-1,k-s}^{(s+1)} = \prod\limits_{i=0}^s \frac{1}{x_{ki}}$. We substitute all of these into the formula for ST$_0$:
%\[\text{ST}_0(x)_k = \begin{cases} \prod\limits_{i=0}^r x_{ik} &\text{if } 0 \leq k \leq s \\ \prod\limits_{i=0}^s \frac{1}{x_{ki}} &\text{if } s+1 \leq k \leq r+s+1 \end{cases}\]
Hence $\ST_1$ is the original Stanley--Thomas word. We assert that these are natural generalizations in that (by Corollary~\ref{pathsinideal}) the first entry of $\ST_j$ is
\[\ST_j(x)_1 = \frac{ W_{2,r+1}^{(j-1)} }{ W_{1,r+1}^{(j)} } = w_{[r] \times [j]}^{(1)}.\]
Hence the generalized Stanley--Thomas words will describe the rowmotion orbits of sums of weights of paths in subrectangles of width greater than $1$.

%\begin{Def}
%Let $x \in \mathbb{R}^R_{>0}$. The $i$th \emph{generalized Stanley--Thomas word} ST$_i(x)$ is the unique cyclic word of length $r+s+2$ cyclically shifted by the action induced by rowmotion and containing $S_{i,0}^{r,s}$ as an entry for some $i \in [0,r]$.
%If $i \leq s-r$ (so that $r-i \leq s$) then for $0 \leq j \leq r+s+1$
%\[ST(i)_j = \begin{cases} S_{i-j,0}^{r-j,s} &\text{if } 0 \leq j \leq i \\
%\widetilde{S}_{r-j+1,s+i-j+1}^{r,s} &\text{if } i+1 \leq j \leq r+1 \\
%\widetilde{S}_{0,s-(r-i)+r+1-j}^{r,s+r+1-j} &\text{if } r+2 \leq j \leq s+i+1 \\
%S_{r+s+i-j+1,r+s-j+1}^{r,s} &\text{if } s+i+2 \leq j \leq r+s+1 \\
%\end{cases}\]
%\end{Def}

%Since birational rowmotion has order $r+s+2$, such a Stanley--Thomas word is guaranteed to exist. Note that ST$_r(x)$ is the birational lifting of the original Stanley--Thomas word, as shown in \cite{josephroby1}. We now compute part of the Stanley--Thomas word.

%\begin{Lemma} Let $0 \leq i \leq r$ and let $1 \leq k \leq \min(i+1,s+1)$. %Let $y = \phi^{-1}(x)$. Then
%\[\rho^k(y)_{i,s} = \widetilde{S}_{r-i-k+1,s-k+1}^{r,s}.\]
%\end{Lemma}

%Before we prove that rowmotion cyclically shifts the generalized Stanley--Thomas words, we will compute such a word in an example.

\begin{Ex}
Let $R = [0,2] \times [0,2]$. Let $x$ be a labeling of $R$. The first generalized Stanley--Thomas word is
\[\ST_1 = \left(  w_{\lozenge_{0,0}^{2,1}}^{(1)}, w_{\lozenge_{0,1}^{2,2}}^{(1)}, \frac{w_{\lozenge_{0,0}^{0,1}}^{(0)}}{w_{\lozenge_{0,0}^{0,1}}}, \frac{w_{\lozenge_{0,0}^{1,2}}^{(1)}}{w_{\lozenge_{0,0}^{1,2}}}, \frac{w_{\lozenge_{1,0}^{2,2}}^{(1)}}{w_{\lozenge_{1,0}^{2,2}}}, \frac{w_{\lozenge_{2,1}^{2,2}}^{(0)}}{w_{\lozenge_{2,1}^{2,2}}}\right)\]
in terms of paths in $R$. In the $x$-coordinates we have the following:
\begin{align*}
    \ST_1(x)_0 &= x_{00}x_{21}\left(x_{10}x_{20} + x_{10}x_{11} + x_{01}x_{11}\right) \\
    \ST_1(x)_1 &= x_{01}x_{22}\left(x_{11}x_{21} + x_{11}x_{12} + x_{02}x_{12}\right) \\
    \ST_1(x)_2 &= \frac{1}{x_{00}x_{01}} \\
    \ST_1(x)_3 &= \frac{1}{x_{10}x_{11}} + \frac{1}{x_{10}x_{02}} + \frac{1}{x_{01}x_{02}} \\
    \ST_1(x)_4 &= \frac{1}{x_{20}x_{21}} + \frac{1}{x_{20}x_{12}} + \frac{1}{x_{11}x_{12}} \\
    \ST_1(x)_5 &= \frac{1}{x_{21}x_{22}}
\end{align*}
See Figure~\ref{fig:shiftingOffThePage} for a visualization of part of this example.
\end{Ex}

\begin{figure}
    \centering
\begin{tikzpicture}[scale = 0.8]
%NE POINTING LINES
\foreach \x in {0,...,2}{
\foreach \y in {2}{
\draw (-\x,\x)--(-\x+\y,\x+\y);
};
};

%NW POINTING LINES
\foreach \x in {2}{
\foreach \y in {0,...,2}{
\draw (\y,\y)--(-\x+\y,\x+\y);
};
};

\foreach \x in {0,...,2}{
\foreach \y in {0,...,2}{
\draw [fill=black] (-\x+\y,\x+\y) circle [radius=0.1cm];
\node at (-\x+\y+0.67,\x+\y) {$x_{\x,\y}$};
};
};

\draw [red,fill=red] (-1,3) circle [radius=0.101cm];
\draw [red,fill=red] (0,4) circle [radius=0.1cm];

%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%SECOND ROW
%%%%%%%%%%%%%%%%%%%%%%

\foreach \s in {-5,0,5}{
\foreach \t in {5}{
%NE POINTING LINES
\foreach \x in {0,...,2}{
\foreach \y in {2}{
\draw [xshift = \s cm, yshift = -\t cm] (-\x,\x)--(-\x+\y,\x+\y);
};
};

%NW POINTING LINES
\foreach \x in {2}{
\foreach \y in {0,...,2}{
\draw [xshift = \s cm, yshift = -\t cm] (\y,\y)--(-\x+\y,\x+\y);
};
};

\foreach \x in {0,...,2}{
\foreach \y in {0,...,2}{
\draw [fill=black, xshift = \s cm, yshift = -\t cm] (-\x+\y,\x+\y) circle [radius=0.1cm];
};
};

};
};

%FIRST PATH
\draw [xshift = -5cm, yshift = -5cm, blue, very thick] (-1,1)--(-2,2)--(0,4);

\draw [blue, fill=blue, xshift = -5cm, yshift = -5cm] (-1,1) circle [radius=0.1cm];
\draw [blue, fill=blue, xshift = -5cm, yshift = -5cm] (-2,2) circle [radius=0.1cm];
\draw [blue, fill=blue, xshift = -5cm, yshift = -5cm] (-1,3) circle [radius=0.1cm];
\draw [blue, fill=blue, xshift = -5cm, yshift = -5cm] (0,4) circle [radius=0.1cm];

\draw [red, fill=red, xshift = -5cm, yshift = -5cm] (0,2) circle [radius=0.1cm];
\draw [red, fill=red, xshift = -5cm, yshift = -5cm] (1,3) circle [radius=0.1cm];

\node [xshift = -4.8cm, yshift = -4.8cm] at (1.7,3) {$x_{1,1}$};
\node [xshift = -4.8cm, yshift = -4.8cm] at (2.7,4) {$x_{1,2}$};

%SECOND PATH
\draw [xshift = 0cm, yshift = -5cm, blue, very thick] (-1,1)--(0,2)--(-1,3)--(0,4);

\draw [blue, fill=blue, xshift = 0cm, yshift = -5cm] (-1,1) circle [radius=0.1cm];
\draw [blue, fill=blue, xshift = 0cm, yshift = -5cm] (0,2) circle [radius=0.1cm];
\draw [blue, fill=blue, xshift = 0cm, yshift = -5cm] (-1,3) circle [radius=0.1cm];
\draw [blue, fill=blue, xshift = 0cm, yshift = -5cm] (0,4) circle [radius=0.1cm];

\draw [red, fill=red, xshift = 0cm, yshift = -5cm] (-2,2) circle [radius=0.1cm];
\draw [red, fill=red, xshift = 0cm, yshift = -5cm] (1,3) circle [radius=0.1cm];

\node [xshift = 0cm, yshift = -4.8cm] at (-1.3,3) {$x_{2,0}$};
\node [xshift = 0cm, yshift = -4.8cm] at (1.7,4) {$x_{1,2}$};

%THIRD PATH
\draw [xshift = 5cm, yshift = -5cm, blue, very thick] (-1,1)--(1,3)--(0,4);

\draw [blue, fill=blue, xshift = 5cm, yshift = -5cm] (-1,1) circle [radius=0.1cm];
\draw [blue, fill=blue, xshift = 5cm, yshift = -5cm] (0,2) circle [radius=0.1cm];
\draw [blue, fill=blue, xshift = 5cm, yshift = -5cm] (1,3) circle [radius=0.1cm];
\draw [blue, fill=blue, xshift = 5cm, yshift = -5cm] (0,4) circle [radius=0.1cm];

\draw [red, fill=red, xshift = 5cm, yshift = -5cm] (-2,2) circle [radius=0.1cm];
\draw [red, fill=red, xshift = 5cm, yshift = -5cm] (-1,3) circle [radius=0.1cm];

\node [xshift = 4.8cm, yshift = -4.8cm] at (-2.3,3) {$x_{2,0}$};
\node [xshift = 4.8cm, yshift = -4.8cm] at (-1.3,4) {$x_{2,1}$};

\end{tikzpicture}
    \caption{Complements of paths needed to compute rowmotion at $(2,1)$ in $R = [0,2] \times [0,2]$. The red in the top row is the complement of the empty path in $V_{2,1}$, yielding $\rho(y)_{2,1}$. The red in the bottom row is the set of complements of paths from $(1,0)$ to $(2,2)$ in $V_{1,0}$, needed for computing $\rho^2(y)_{2,1}$.}
    \label{fig:shiftingOffThePage}
\end{figure}




















%\begin{Ex}
%Let $R = [0,3] \times [0,2]$. Let $x$ be a labeling of $R$ with $y = \phi^{-1}(x)$. The claim is that
%\[\rho(y)_{2,2} = \frac{1}{x_{2,2}x_{3,2}},\]
%which is the inverse weight of the complement of the set of empty paths in V$_{2,2}$. See Figure \ref{fig:shiftingOffThePage} to visualize this. Note that $\rho^0(y)_{2,2}$ is the sum of weights of all paths from $(0,0)$ to $(2,2)$. Morally $\rho(y)_{2,2}$ is where this sum of chains is stored after $\rho^{-1}$ has chain shifted it off of the bottom right edge of the rectangle.

%Computing further powers of rowmotion, \[\rho^2(y)_{2,2} = \widetilde{S}_{1,1}^{3,2}.\]
%This is the sum of inverse weights of complements of paths from $(1,1)$ to $(3,2)$ in V$_{1,1}$. From Figure \ref{fig:shiftingOffThePage}, we see that
%\[\rho^2(y)_{2,2} = \frac{1}{x_{1,2}x_{2,2}} + \frac{1}{x_{1,2}x_{3,1}} + \frac{1}{x_{1,2}x_{3,1}}.\]
%\end{Ex}

%\begin{figure}
%    \centering
%\begin{tikzpicture}[scale = 0.8]
%NE POINTING LINES
%\foreach \x in {0,...,3}{
%\foreach \y in {2}{
%\draw (-\x,\x)--(-\x+\y,\x+\y);
%};
%};

%NW POINTING LINES
%\foreach \x in {3}{
%\foreach \y in {0,...,2}{
%\draw (\y,\y)--(-\x+\y,\x+\y);
%};
%};

%\foreach \x in {0,...,3}{
%\foreach \y in {0,...,2}{
%\draw [fill=black] (-\x+\y,\x+\y) circle [radius=0.1cm];
%\node at (-\x+\y+0.67,\x+\y) {$x_{\x,\y}$};
%};
%};

%\draw [red,fill=red] (0,4) circle [radius=0.101cm];
%\draw [red,fill=red] (-1,5) circle [radius=0.1cm];

%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%SECOND ROW
%%%%%%%%%%%%%%%%%%%%%%

%\foreach \s in {-6,0,6}{
%\foreach \t in {6}{
%NE POINTING LINES
%\foreach \x in {0,...,3}{
%\foreach \y in {2}{
%\draw [xshift = \s cm, yshift = -\t cm] (-\x,\x)--(-\x+\y,\x+\y);
%};
%};

%NW POINTING LINES
%\foreach \x in {3}{
%\foreach \y in {0,...,2}{
%\draw [xshift = \s cm, yshift = -\t cm] (\y,\y)--(-\x+\y,\x+\y);
%};
%};

%\foreach \x in {0,...,3}{
%\foreach \y in {0,...,2}{
%\draw [fill=black, xshift = \s cm, yshift = -\t cm] (-\x+\y,\x+\y) circle [radius=0.1cm];
%};
%};

%};
%};

%FIRST PATH
%\draw [xshift = -6cm, yshift = -6cm, blue, very thick] (0,2)--(-2,4)--(-1,5); 
%\draw [blue, fill=blue, xshift = -6cm, yshift = -6cm] (0,2) circle [radius=0.1cm];
%\draw [blue, fill=blue, xshift = -6cm, yshift = -6cm] (-1,3) circle [radius=0.1cm];
%\draw [blue, fill=blue, xshift = -6cm, yshift = -6cm] (-2,4) circle [radius=0.1cm];
%\draw [blue, fill=blue, xshift = -6cm, yshift = -6cm] (-1,5) circle [radius=0.1cm];

%\draw [red, fill=red, xshift = -6cm, yshift = -6cm] (1,3) circle [radius=0.1cm];
%\draw [red, fill=red, xshift = -6cm, yshift = -6cm] (0,4) circle [radius=0.1cm];

%\node [xshift = -4.8cm, yshift = -4.8cm] at (1.7,3) {$x_{1,2}$};
%\node [xshift = -4.8cm, yshift = -4.8cm] at (0.7,4) {$x_{2,2}$};

%SECOND PATH
%\draw [xshift = 0cm, yshift = -6cm, blue, very thick] (0,2)--(-1,3)--(0,4)--(-1,5); 
%\draw [blue, fill=blue, xshift = 0cm, yshift = -6cm] (0,2) circle [radius=0.1cm];
%\draw [blue, fill=blue, xshift = 0cm, yshift = -6cm] (-1,3) circle [radius=0.1cm];
%\draw [blue, fill=blue, xshift = 0cm, yshift = -6cm] (0,4) circle [radius=0.1cm];
%\draw [blue, fill=blue, xshift = 0cm, yshift = -6cm] (-1,5) circle [radius=0.1cm];

%\draw [red, fill=red, xshift = 0cm, yshift = -6cm] (1,3) circle [radius=0.1cm];
%\draw [red, fill=red, xshift = 0cm, yshift = -6cm] (-2,4) circle [radius=0.1cm];

%\node [xshift = 0cm, yshift = -4.8cm] at (1.7,3) {$x_{1,2}$};
%\node [xshift = 0cm, yshift = -4.8cm] at (-1.3,4) {$x_{3,1}$};

%THIRD PATH
%\draw [xshift = 6cm, yshift = -6cm, blue, very thick] (0,2)--(1,3)--(-1,5); 
%\draw [blue, fill=blue, xshift = 6cm, yshift = -6cm] (0,2) circle [radius=0.1cm];
%\draw [blue, fill=blue, xshift = 6cm, yshift = -6cm] (1,3) circle [radius=0.1cm];
%\draw [blue, fill=blue, xshift = 6cm, yshift = -6cm] (0,4) circle [radius=0.1cm];
%\draw [blue, fill=blue, xshift = 6cm, yshift = -6cm] (-1,5) circle [radius=0.1cm];

%\draw [red, fill=red, xshift = 6cm, yshift = -6cm] (-1,3) circle [radius=0.1cm];
%\draw [red, fill=red, xshift = 6cm, yshift = -6cm] (-2,4) circle [radius=0.1cm];

%\node [xshift = 4.8cm, yshift = -4.8cm] at (-0.3,3) {$x_{1,2}$};
%\node [xshift = 4.8cm, yshift = -4.8cm] at (-1.3,4) {$x_{3,1}$};

%\end{tikzpicture}
%    \caption{Complements of paths needed to compute rowmotion at $(2,2)$ in $R = [0,3] \times [0,2]$. The red in the top row is the complement of the empty path in V$_{2,2}$, yielding $\rho(y)_{2,2}$. The red in the bottom row is the set of complements of paths from $(1,1)$ to $(3,2)$ in V$_{1,1}$, needed for computing $\rho^2(y)_{2,2}$.}
%    \label{fig:shiftingOffThePage}
%\end{figure}

Proving that rowmotion rotates the generalized Stanley--Thomas words is a simple application of Theorem~\ref{birationalrowmotionformula}.

\begin{Th}
The map $\phi \circ \rho \circ \phi^{-1}$ cyclically shifts all generalized Stanley--Thomas words.
\end{Th}

\begin{proof}
Let $x \in \mathbb{R}_{>0}^R$ and let $y = \phi^{-1}(x)$. Since birational rowmotion has order $r+s+2$, it suffices to show that the orbit of $\ST_j(x)_0$ matches the generalized Stanley--Thomas word. As stated previously, 
%$ST_j(x)_0 = y_{rj} = \frac{ W_{1,r+1}^{(j)} }{ W_{0,r+1}^{(j+1)} }$.
$\ST_j(x)_0 = w_{\Lambda_{r,j}}^{(1)} = y_{rj}$.
If $0 \leq k \leq s-j$, then by Lemma~\ref{chainshift},
\[\ST_j( \phi \circ \rho^{-k}(y) ) = \frac{ W_{k+1,r+k+1}^{(j)} }{ W_{k,r+k+1}^{(j+1)} }.\]

If $k = s-j+1$, then we apply parts (c), (b), and (a) of Theorem~\ref{birationalrowmotionformula} in that order:
\[\rho^{-(s-j+1)}(y)_{rj} = \rho^{r+s+2-(s-j+1)}(y)_{rj} = \frac{1}{\rho^{0}(y)_{0,s-j}} = \frac{W_{0,1}^{(s-j+1)}}{W_{1,1}^{(s-j)}}.\]
By Proposition~\ref{prop:wproperties}(b) the denominator is 1.

Finally, if $k>s-j+1$, then we note that rowmotion shifts the array, as we saw in the proof of Lemma~\ref{chainshift}. So if $s-j+1 < k \leq r+s+1$, then applying $\rho^{-(s-j+1)}$ yields
\[\rho^{-(s-j+1)}(y)_{rj} = W_{0,1}^{(s-j+1)}\]
and applying $\rho^{-k-(s-j+1)}$ gives
\[\rho^{-k}(y)_{rj} = W_{k-s+j-1,k-s+j}^{(s-j+1)}.\]
Since birational rowmotion has order $r+s+2$, we have computed the entire orbit, which is exactly $\ST_j(x)$.
\end{proof}

%\begin{proof}
%Note that $0 \leq k-1 \leq \min(i,s) \leq i+s$. By Part B of the rowmotion formula we have
%\[\rho^k(y)_{i,s} = \frac{1}{\rho^{k-i-s-1}(y)_{r-i,0}} = %\frac{W_{s+i+1-k,r+s+2-k}^{(1)}}{W_{s+i-k+2,r+s+2-k}^{(0)}}.\]
%Recall that by convention, $W_{s+i-k+2,r+s+2-k}^{(0)} = 1$. Then
%\[\rho^k(y)_{i,s} = W_{s+i+1-k,r+s+2-k}^{(1)}.\]
%This is sum of the weights of all paths in $\mathcal{G}_R$ from $(i-k+1,s)$ to $(r+1, s-k+1)$. Letting $I = i-k+1$, $J = s-k+1$, and $K = s-i+k-1$, by Corollary TODO: REFERENCE COROLLARY 3.2, The sum of the weights of paths in $\mathcal{G}_R$ from $P_{I+J+K+1} = P_{s+i-k+1}$ to $Q_{r+J+1} = Q_{r+s+2-k}$ is $\widetilde{S}_{i-k+1,s-k+1}^{r,s}$.
%\end{proof}

As noted in \cite{josephroby1}, the cyclic rotation of $ST_0$ is not sufficient to uniquely determine birational rowmotion. However, the cyclic rotation of all $ST_i$ for $0 \leq i \leq r$ does uniquely determine birational rowmotion, and in fact the chain shifting lemma alone nearly suffices. We make this statement precise in Section \ref{section:greenestheorem}.

%TODO: NOTE/SHOW THAT THE ORBITS OF $S_{0,j}^{r,s}$ ARE DETERMINED BY THE ORBITS OF $S_{i,0}^{r,s}$



\fi

























\section{Birational RSK and Greene's theorem} \label{section:greenestheorem}

In this section, we will define birational RSK in terms of toggles and show how our perspective gives a simple proof of the birational version of Greene's theorem.

\subsection{Classical RSK} \label{sec:classical-rsk}

We first review some background on the classical RSK correspondence, which gives a bijection between nonnegative integer matrices $A$ and pairs of semistandard tableaux $(P,Q)$ of the same shape $\lambda$. (See, for instance, \cite{sagan} for more details.)

In the case when $A$ is the matrix of a permutation $\pi$, Greene's theorem \cite{greene} states that $\lambda_1 + \cdots + \lambda_k$ is the maximum size of a union of $k$ increasing subsequences of $\pi$. In fact, one can use Greene's theorem to compute not just the shape of $P$ and $Q$ but the entire tableaux: the shape $P^{\leq m}$ formed by the entries at most $m$ in $P$ corresponds to the permutation formed by the letters $1, \dots, m$ in $\pi$, while the shape $Q^{\leq m}$ corresponds to the permutation formed by the first $m$ letters of $\pi$.

When $A$ is a general $n \times n$ nonnegative integer matrix, a routine standardization argument gives the following generalization of Greene's theorem: $\lambda_1 + \cdots + \lambda_k$ is the maximum weight of $k$ nonintersecting paths (traveling weakly southeast) from $(1,1), \dots, (1,k)$ to $(n,n-k+1), \dots, (n,n)$ in $A$, where the weight of a path is the sum of the entries it contains. (As noted in \cite{farberhopkinstrongsiriwat}, this result appears to be somewhat folklore, but see \cite[Thm.\ 2.5]{noumiyamada} as well as \cite[Thm.\ 12]{krattenthaler}, \cite[Thm.\ 4.8.10]{sagan}.)
As in the permutation case, this can be used to characterize the entire $P$ and $Q$ tableaux since $P^{\leq m}$ (resp.\ $Q^{\leq m}$) corresponds to the submatrix formed by the first $m$ columns (resp.\ rows) of $A$. 

One way to see the impact of Greene's theorem more directly is to transform $P$ and $Q$ into Gelfand-Tsetlin patterns and glue them along their top rows to form an $n \times n$ matrix with weakly increasing rows and columns that we denote by $RSK(A)$. By construction, this matrix has the property that, for $1 \leq k \leq i,j \leq n$ with either $i=n$ or $j=n$, 
\[\sum_{t=0}^{k-1} RSK(A)_{i-t,j-t}\] is the maximum weight of $k$ nonintersecting paths from $(1,1), \dots, (1,k)$ to $(i,j-k+1), \dots, (i,j)$ in $A$.


\ytableausetup{smalltableaux,centertableaux}
\begin{figure}
    \centering
    \begin{tikzpicture}
        \node at (0,0){$A=\begin{bmatrix}0&0&0&2\\2&0&1&0\\0&1&1&1\\1&1&0&0\end{bmatrix}$};
        \draw[->] (2,0)--(2.8,0);
        \node at (4.5,0){$P=\ytableaushort{11124,23,34,4}$};
        \node at (7.5,0){$Q=\ytableaushort{11233,22,34,4}$};
        \draw[->] (6,-1)--(6,-1.8);
        \node at (4.5,-3){$\setlength{\tabcolsep}{2pt}\begin{tabular}{ccccccc}5&&2&&2&&1\\&4&&2&&1\\&&4&&1\\&&&3\end{tabular}$};
        \node at (7.5,-3){$\setlength{\tabcolsep}{2pt}\begin{tabular}{ccccccc}5&&2&&2&&1\\&5&&2&&1\\&&3&&2\\&&&2\end{tabular}$};
        \draw[->] (2.8,-3)--(2,-3);
        \node at (-.56,-3){$RSK(A)=\begin{bmatrix}1&1&2&2\\1&2&2&3\\1&2&2&5\\3&4&4&5\end{bmatrix}$};
    \end{tikzpicture}
    \caption{An example of the map $A \mapsto RSK(A)$ in the classical setting. See Example~\ref{ex:rsk}.}
    \label{fig:rsk}
\end{figure}


\begin{Ex}\label{ex:rsk}
    Figure~\ref{fig:rsk} depicts a $4 \times 4$ matrix $A=(a_{ij})$ and its image under the classical RSK correspondence as a pair of semistandard tableaux $P$ and $Q$ of the same shape. These tableaux are then turned into triangular Gelfand-Tsetlin patterns (the rows of which give the shapes of the tableaux $P^{\leq m}$ and $Q^{\leq m}$ for $m=4, 3, 2, 1$). These two Gelfand-Tsetlin patterns are then glued together to form the matrix $RSK(A)$.

    By Greene's theorem, the entries of $RSK(A)$ tell us about weights of nonintersecting paths in $A$. For example:
    \begin{itemize}
    \item $RSK(A)_{34} = 5$ is the maximum weight of a path from $a_{11}$ to $a_{34}$; 
    \item $RSK(A)_{34}+RSK(A)_{23} = 5+2 = 7$ is the maximum weight of two nonintersecting paths from $a_{11}$ and $a_{12}$ to $a_{33}$ and $a_{34}$; and
    \item $RSK(A)_{34}+RSK(A)_{23}+RSK(A)_{12} = 5+2+1 = 8$ is the maximum weight of three nonintersecting paths from $a_{11}, a_{12}, a_{13}$ to $a_{32}, a_{33}, a_{34}$, which is just the sum of all the entries in the first three rows of $A$.
    \end{itemize}
\end{Ex}

In the next section, we will see how the map $A \mapsto RSK(A)$ can be generalized to the birational setting.

\subsection{Birational RSK}

For any interval $I \subseteq R$, denote by $\rho_I$ the map on labelings of $R$ given by the composition of toggles at the elements of $I$ (applied in the order of a linear extension from top to bottom).

\begin{Def} \label{def:rsk}
Let $R = [r] \times [s]$, and let $m = \min\{r,s\}-1$. The \emph{birational RSK map} on labelings of $R$ is given by
\[RSK = \rho_{[r-m]\times[s-m]}^{-1} \circ \dots \circ \rho_{[r-2] \times [s-2]}^{-1} \circ \rho_{[r-1] \times [s-1]}^{-1} \circ \phi^{-1}.\]
\end{Def}

We will compare this to other formulations of birational RSK below, but for now, this can be treated as a definition. We will abuse notation and denote the piecewise-linear version of this map by $RSK$ as well.

\begin{Ex} \label{ex:rsk3x4}
    Let $R = [3] \times [4]$, and let $x \in \mathbb R_{>0}^R$ and $y = \phi^{-1}(x)$. Then \[RSK(x) = \rho^{-1}_{[1] \times [2]} \circ \rho^{-1}_{[2] \times [3]} (y) = (t_{12} \circ t_{11}) \circ (t_{23} \circ t_{22} \circ t_{21} \circ t_{13}\circ t_{12} \circ t_{11})(y).\]
    See Figure~\ref{fig:birationalrsk}. Note that each toggle involves essentially the same calculation that is done when applying some power of $\rho^{-1}$ to $y$. As a result, each label of $RSK(x)$ is equal to a label in some $\rho^{-k}(y)$. These can then be computed using Theorem~\ref{birationalrowmotionformula}.
\end{Ex}


\tikzstyle{v}=[circle, draw, fill=black, inner sep=0pt, minimum width=4pt]
\begin{figure}
    \centering
    \begin{tikzpicture}[scale=.6,transform shape]
        \filldraw[blue!20] (0,1.5)--(-1.5,3)--(1,5.5)--(2.5,4)--cycle;
        \foreach \x in {1,...,3}
            \foreach \y in {1,...,4} {
                \node[v,label=right:$y_{\x\y}$](\x\y) at (\y-\x,\y+\x){};
                }
        \draw (11)--(14) (21)--(24) (31)--(34) (11)--(31) (12)--(32) (13)--(33) (14)--(34);
        \draw[->](3.5,4)--node[above]{$\rho^{-1}_{[2] \times [3]}$}(5,4);
        \begin{scope}[shift={(7.5,0)}]
                \filldraw[blue!20] (0,1.5)--(-.5,2)--(1,3.5)--(1.5,3)--cycle;
        \foreach \x/\y in {3/1,3/2,3/3,3/4,2/4,1/4}
            \node[v,label=right:$y_{\x\y}$](\x\y) at (\y-\x,\y+\x){};
        \foreach \x/\y in {1/1,1/2,1/3,2/1,2/2,2/3}
            \node[v,label=right:$\rho^{-1}(y)_{\x\y}$](\x\y) at (\y-\x,\y+\x){};
        \draw (11)--(14) (21)--(24) (31)--(34) (11)--(31) (12)--(32) (13)--(33) (14)--(34);
        \end{scope}
        \draw[->](11.5,4)--node[above]{$\rho^{-1}_{[1] \times [2]}$}(13,4);
        \begin{scope}[shift={(15.5,0)}]
        \foreach \x/\y in {3/1,3/2,3/3,3/4,2/4,1/4}
            \node[v,label=right:$y_{\x\y}$](\x\y) at (\y-\x,\y+\x){};
        \foreach \x/\y in {1/3,2/1,2/2,2/3}
            \node[v,label=right:$\rho^{-1}(y)_{\x\y}$](\x\y) at (\y-\x,\y+\x){};
        \foreach \x/\y in {1/1,1/2}
            \node[v,label=right:$\rho^{-2}(y)_{\x\y}$](\x\y) at (\y-\x,\y+\x){};
        \draw (11)--(14) (21)--(24) (31)--(34) (11)--(31) (12)--(32) (13)--(33) (14)--(34);
        \end{scope}
    \end{tikzpicture}
    \caption{Computing $RSK(x)$ by applying toggles to $y = \phi^{-1}(x)$. At each step, the highlighted elements are toggled from bottom to top.}
    \label{fig:birationalrsk}
\end{figure}




In general, one can always describe the entries of $RSK(x)$ using the action of rowmotion on all of $R$ as in the following proposition. 

\begin{Prop}
$RSK(x)_{r-i,s-j} = \rho^{-\min\{i,j\}} \circ \phi^{-1}(x)_{r-i,s-j}.$
\label{Cor:RSKasRowmotion}
\end{Prop}

\begin{proof} 
Let $y = \phi^{-1}(x)$. We claim that $\rho_{[r-k]\times[s-k]}^{-1} \circ \cdots \circ \rho^{-1}_{[r-1]\times[s-1]}(y)$ and $\rho^{-k} (y)$ agree on $[r-k]\times[s-k]$. Indeed, suppose inductively that the claim holds for $k-1$. Since any neighbor of an element in $[r-k] \times [s-k]$ lies in $[r-k+1] \times [s-k+1]$, applying $\rho^{-1}_{[r-k,s-k]}$ to both $\rho_{[r-k+1]\times[s-k+1]}^{-1} \circ \cdots \circ \rho^{-1}_{[r-1]\times[s-1]}(y)$ and $\rho^{-k+1} (y)$ yields labelings that agree on $[r-k]\times[s-k]$. Then applying the remaining toggles in $\rho^{-1}$ (at elements of $R \setminus ([r-k] \times [s-k])$) to the latter also does not affect any of these values, proving the claim.

If $\min\{i,j\} = k$, then $\rho_{[r-k']\times[s-k']}^{-1}$ does not affect the label at $(r-i,s-j)$ for any $k'>k$, so the result follows from the claim.
\end{proof}


We are now ready to prove the following theorem, which will serve as a birational analogue to Greene's theorem as described in Section~\ref{sec:classical-rsk}.

\begin{Th}[Birational Greene's theorem] \label{plGreene}
Let $R = [r] \times [s]$, and choose $(i,j) \in R$ such that either $i = r$ or $j = s$. Then for any $x \in \mathbb R^{R}_{>0}$ and $1\leq k \leq \min \{i,j\}+1$,
\[\prod_{t=0}^{k-1} RSK(x)_{i-t,j-t} = w_{[i]\times[j]}^{(k)}(x).\]
%For $(i_1,j_1),(i_2,j_2) \in R$, let $\mathcal{P}_{i_1,j_1}^{i_2,j_2}(k)$ denote the set of all unions of $i$ nonintersecting lattice paths in $R$ from $(i_1,j_1),\dots,(i_1,j_1+k-1)$ to $(i_2,j_2-k+1),\dots,(i_2,j_2)$. Then 
% For any $x \in \mathbb{R}_{> 0}^{|R|}$ and any $k \leq \min(r,j)$ (or $k \leq \min(j,s)$ respectively) we have
% \[\prod\limits_{i=0}^{k-1} \emph{RSK}(x)_{r-i,j-i} = \sum\limits_{\mathcal{L} \in \mathcal{P}_{0,0}^{r,j}(k)} \prod\limits_{z \in \mathcal{L}} x_z \quad \text{and} \quad \prod\limits_{i=0}^{k-1} \emph{RSK}(x)_{j-i,s-i} = \sum\limits_{\mathcal{L} \in \mathcal{P}_{0,0}^{j,s}(k)} \prod\limits_{z \in \mathcal{L}} x_z\]
\end{Th}


\begin{proof}
Let $x \in \mathbb{R}_{>0}^{R}$ and let $y = \phi^{-1}(x)$. By Proposition \ref{Cor:RSKasRowmotion}, since \[\min\{r-(i-t),s-(j-t)\} = \min\{r-i,s-j\}+t = t,\] 
we have
\[RSK(x)_{i-t,j-t} = \rho^{-t}(y)_{i-t,j-t}.\] Theorem~\ref{birationalrowmotionformula}(a) then gives
%If $I = r-i$, $J = j-i$, and $K=i$, then
%\[I+J = r-i+j-i \leq r-i+s = r+s-K.\]
%Hence $\rho^{-i}(y)_{r-i,j-i}$ satisfies the condition for part A of the birational rowmotion formula. Then
\[\rho^{-t}(y)_{i-t,j-t} = \frac{W_{t+2,i+1}^{(j-t-1)}}{W_{t+1,i+1}^{(j-t)}}.\]
We then have the telescoping product
\[\prod_{t=0}^{k-1} RSK(x)_{i-t,j-t}=\prod_{t=0}^{k-1} \rho^{-t}(y)_{i-t,j-t} = \frac{W_{k+1,i+1}^{(j-k)}}{W_{1,i+1}^{(j)}} = w_{[i]\times[j]}^{(k)}(x)\]
by Corollary~\ref{pathsinideal}.
%\[\prod\limits_{i=0}^{k-1} \rho^{-i}(y)_{r-i,j-i} = \frac{W_{k+1}^{r+1}(s-k)}{W_0^{r+1}(s+1)}\]
%
% The denominator is the sum of the weights of all nonintersecting lattice paths in $\mathcal{G}_R$ from $(0,0),\dots,(0,j)$ to $(r+1,0),\dots,(r+1,j)$. There is a unique set of lattice paths connecting these points (comprised of only diagonal edges) and so their weight is $\prod\limits_{z \in \Lambda_{r,j}} x_z^{-1}$.
%
% The numerator is the sum of the weights of all nonintersecting lattice paths in $\mathcal{G}_R$ from $(0,k+1),\dots,(0,j)$ to $(r+1,j),\dots,(r+j-k,j)$. The weights of these paths are the weights of complements of nonintersecting lattice paths in $R$ from $(0,0),\dots, (0,k)$ to $(r-k+1,j),\dots,(r,j)$. So
%
% \[\prod\limits_{i=0}^{k-1} \rho^{-i}(y)_{r-i,j-i} = \frac{ \sum\limits_{\mathcal{L} \in \mathcal{P}_{0,0}^{r,j}(k)} \prod\limits_{z \in \Lambda_{r,j} \setminus \mathcal{L}} x_z^{-1} }{ \prod\limits_{z \in \Lambda_{r,j}} x_z^{-1} } = \sum\limits_{\mathcal{L} \in \mathcal{P}_{0,0}^{r,j}(k)} \prod\limits_{z \in \mathcal{L}} x_z\]
%
\end{proof}

Note that Theorem~\ref{plGreene} uniquely characterizes the map $RSK$ in terms of the values of $w_{[i]\times[j]}^{(k)}(x)$ where $i=r$ or $j=s$. To see why this can be considered to be a birational version of Greene's theorem, consider the tropicalization of Theorem~\ref{plGreene}:
\[\sum_{t=0}^{k-1} RSK(x)_{i-t,j-t} = \max_{\mathcal{L} \in \mathcal{P}_{[i]\times[j]}^{(k)}} \sum_{z \in \mathcal{L}} x_z.\]
This corresponds directly to the description of $RSK(A)$ given in Section~\ref{sec:classical-rsk}. We can therefore treat this as a proof that the map $RSK$ as defined above is a birational analogue to the classical RSK correspondence.

\begin{Ex} \label{ex:rsk2}
    Suppose $R = [4] \times [4]$ and $x \in \mathbb R_{>0}^R$. According to Theorem~\ref{plGreene}, we can compute the labels of $RSK(x)$ in terms of the weights of nonintersecting paths in $x$. For instance,
    \begin{align*}
        w_{[3] \times [4]}^{(1)}(x) &= RSK(x)_{34},\\
        w_{[3] \times [4]}^{(2)}(x) &= RSK(x)_{34} \cdot RSK(x)_{23}, \\
        w_{[3] \times [4]}^{(3)}(x) &= RSK(x)_{34} \cdot RSK(x)_{23} \cdot RSK(x)_{12},
    \end{align*}
    from which these three labels of $RSK(x)$ can easily be determined by taking quotients. Note that these three equations tropicalize to the description of the corresponding entries of the classical RSK map using Greene's theorem as in Section~\ref{sec:classical-rsk}. (Compare to the bullet points in Example~\ref{ex:rsk}.) 
    
    This implies that we can compute the classical RSK map by using the piecewise-linear version of Definition~\ref{def:rsk}. For instance,
    treating the matrix $A$ in Figure~\ref{fig:rsk} as a labeling of the rectangle $R=[4] \times [4]$, we can compute $RSK(A)$ as follows. First apply the inverse transfer map $\phi^{-1}$:
    \[A=\begin{bmatrix}0&0&0&2\\2&0&1&0\\0&1&1&1\\1&1&0&0\end{bmatrix} \xrightarrow{\phi^{-1}} \begin{bmatrix}0&0&0&2\\2&2&3&3\\2&3&4&5\\3&4&4&5\end{bmatrix}.\]
    Then successively apply the partial rowmotion maps as indicated. (At each step, the red entries are toggled starting in the upper left corner.)
    \[\begin{bmatrix}\red0&\red0&\red0&2\\\red2&\red2&\red3&3\\\red2&\red3&\red4&5\\3&4&4&5\end{bmatrix}
    \xrightarrow{\rho_{[3] \times [3]}^{-1}} \begin{bmatrix}\red0&\red0&2&2\\\red0&\red1&2&3\\1&2&2&5\\3&4&4&5\end{bmatrix}
    \xrightarrow{\rho_{[2] \times [2]}^{-1}} \begin{bmatrix}\red0&1&2&2\\1&2&2&3\\1&2&2&5\\3&4&4&5\end{bmatrix}
    \xrightarrow{\rho_{[1] \times [1]}^{-1}} \begin{bmatrix}1&1&2&2\\1&2&2&3\\1&2&2&5\\3&4&4&5\end{bmatrix}.
    \]
    The resulting matrix $RSK(A)$ is the same as in Figure~\ref{fig:rsk}.
\end{Ex}

\subsection{Relation to prior work}

Our construction of birational RSK using the octahedron recurrence is very similar to the approach taken by Danilov--Koshevoy \cite{danilovkoshevoy} (although their construction differs from the standard one by a symmetry of $A$). Our construction is also necessarily equivalent to the description of ``tropical RSK'' (sometimes also ``geometric RSK'') given by Noumi--Yamada \cite{noumiyamada} (motivated by Kirillov \cite{kirillov}) since their map is also constructed to satisfy Theorem~\ref{plGreene}. An analysis of the Noumi--Yamada construction via local toggles can also be found in \cite{osz}.



% For the rectangle $R$, the elements of the domain and range of the piecewise-linear transfer map are matrices, so we see that $\phi$ is a map from nonnegative matrices with weakly increasing rows and columns to nonnegative matrices. Another map of this form is RSK$^{-1}$, so we will review some of the results and definitions associated to RSK. 

% A \emph{generalized permutation} is a pair of positive integer sequences $\{a_i\}_{i = 1}^{k}$ and $\{b_i\}_{i=1}^k$ such that $a_i \leq a_{i+1}$ for all $1 \leq i \leq k-1$ and if $b_i > b_{i+1}$, then $a_i < a_{i+1}$. We typically write a generalized permutation in parentheses with the first sequence on top and the second beneath it, as in the example below.

% \[\begin{pmatrix} 1 & 1 & 1 & 2 & 3 & 3 \\ 1 & 1 & 2 & 3 & 1 & 3 \end{pmatrix}\]

% Classical RSK maps a generalized permutation to a pair of semistandard Young tableaux ($P,Q)$ of the same shape, called the \emph{insertion tableau} and the \emph{recording tableau} respectively. The version of RSK that we are most interested in is the toggle version that appears in \cite{hopkins}, so we will not define classical RSK. Given a generalized permutation, we form a matrix $A$ with entries $A_{i,j}$ given by the number of columns in our generalized permutation with $i$ in the first row and $j$ in the second. Note that from $A$ we can recover the generalized permutation. So far we have the following correspondence.


% \[A \mapsto w \mapsto (P,Q)\]

% \noindent where $A$ is a nonnegative integer matrix. To complete this analogue of RSK, we need to map $(P,Q)$ to a nonnegative integer matrix with weakly increasing rows and columns. We map $P$ and $Q$ to their \textit{Gelfand-Tsetlin patterns}.



% \begin{Def}
% A Gelfand-Tsetlin pattern is a triangular array of nonnegative integers
% \[
% \begin{tikzpicture}
% \node at (0,0) {$g_{1,1}$};
% \node at (1.8,0) {$g_{1,2}$};
% \node at (3.6,0) {$g_{1,3}$};
% \node at (5.4,0) {$\cdots$};
% \node at (7.2,0) {$g_{1,n}$};

% \node at (0.9,-0.5) {$g_{2,2}$};
% \node at (2.7,-0.5) {$g_{2,3}$};
% \node at (4.5,-0.5) {$\cdots$};
% \node at (6.3,-0.5) {$g_{2,n}$};

% \node at (1.8,-1) {$g_{3,3}$};
% \node at (3.6,-1) {$\cdots$};
% \node at (5.4,-1) {$g_{3,n}$};

% \node at (2.7,-1.5) {$\ddots$};
% \node at (4.5,-1.5) {$\iddots$};

% \node at (3.6,-2) {$g_{n,n}$};

% \end{tikzpicture}
% \]
% such that $g_{i,j} \geq g_{i+1,j+1} \geq g_{i,j+1}$ for all $1 \leq i,j < n$.
% \end{Def}

% Let $P$ be a semistandard Young tableau. We let $P^i$ denote the subtableau of $P$ consisting of boxes with label at most $i$. The Gelfand-Tsetlin pattern associated to $P$ has row $i$ given by sh$(P^{n-i+1})$. Since $RSK$ maps a generalized permutation to two semistandard Young tableaux of the same shape, the Gelfand-Tsetlin patterns of these tableaux have the same first row. We form a matrix from the Gelfand-Tsetlin patterns by gluing the patterns together along their common first row. The inequalities in the definition of the Gelfand-Tsetlin pattern imply that the rows and columns of the resulting matrix are weakly increasing.

In \cite{farberhopkinstrongsiriwat}, a birational version of RSK is described using the following piecewise-linear analogue of RSK defined in \cite{hopkins,pak}.
Let $x \in \mathcal{C}(R)$ be a point in the chain polytope of $R=[r]\times[s]$. We construct $y = rsk(x) \in \mathcal O(R)$ in the order polytope of $R$ using the following procedure.

\begin{enumerate}
    \item Set $y_{11} = x_{11}$.
    \item Choose an element $p \in R$ such that $y_q$ has been defined for all $q < p$. Set $y_p = x_p + \max\limits_{q \lessdot p} y_q$, and then toggle $y$ at all elements below $p$ in the same file.
    \item Repeat the previous step until all coordinates of $y$ have been defined.
\end{enumerate}
In step (2), the elements $p$ can be considered in the order of any linear extension of $R$. It is straightforward to verify that the result is independent of the choice of linear extension. We can also extend $rsk$ in the obvious way to all of $\mathbb R_{\geq 0}^R$.

\begin{Ex}
Consider the matrix $A$ from Examples~\ref{ex:rsk} and \ref{ex:rsk2}. We compute $rsk(A)$ by considering elements in order of rank, taking the elements at each rank simultaneously (entries colored in red are toggled at the following step):
\begin{align*}
    \begin{bmatrix}
    0&&&\\&\phantom0\\&&\phantom0\\&&&\phantom0
\end{bmatrix} &\to 
\begin{bmatrix}
    \red{0}&0&&\\
    2\\
    &&\phantom0\\
    &&&\phantom0
\end{bmatrix} \to
\begin{bmatrix}
    0&\red0&0&\\
    \red2&2\\
    2\\
    &&&\phantom0
\end{bmatrix} \to
\begin{bmatrix}
    \red0&0&\red0&2\\
    0&\red2&3\\
    \red2&3\\
    3
\end{bmatrix}\\
&\to
\begin{bmatrix}
    0&\red0&2&2\\
    \red0&1&\red3&3\\
    1&\red3&4\\
    3&4
\end{bmatrix}
\to
\begin{bmatrix}
    \red0&1&2&2\\
    1&\red1&2&3\\
    1&2&\red4&5\\
    3&4&4
\end{bmatrix}
\to
\begin{bmatrix}
    1&1&2&2\\
    1&2&2&3\\
    1&2&2&5\\
    3&4&4&5
\end{bmatrix}.
\end{align*}
Note that the result agrees with the computations of $RSK(A)$ from earlier.
\end{Ex}

In fact, this map is the same as the piecewise-linear version of the map $RSK$ defined in the previous section.

\begin{Prop}
$RSK=rsk$.
\end{Prop}

\begin{proof}
When performing step (2) above, none of the toggled elements form a cover relation with any element that has yet to be considered. Since the value of each new $y_p$ depends only on the values $y_q$ for $q \lessdot p$, the toggles at the previous steps do not affect the initial value of $y_p$. Hence we can apply all the toggles after first assigning all $y_p$, which is equivalent to first applying $\phi^{-1}$ to $x$.

Without loss of generality, we may assume $r \leq s$. If $r = 1$, then the rectangle is a chain and no toggles are applied, so $rsk = \phi^{-1} = RSK$.

Suppose inductively that on $[r-1]\times[s]$, $rsk = \rho_{[1] \times [s-r+2]}^{-1} \circ \dots \circ \rho_{[r-2]\times[s-1]}^{-1} \circ \phi^{-1}$, and consider the rectangle $R=[r] \times [s]$ for $r \leq s$. After applying $rsk$ on the order ideal $[r-1] \times [s]$, to complete $rsk$ for $R$ we must apply toggles at all elements in $[r-1]\times[s]$ that lie in files $2-r, 3-r,\dots, s-r$. Since toggles at elements that are not adjacent commute, we can toggle row by row instead of file by file. Write $I_i = \{i\} \times [s-r+i] \subseteq R$ for $i < r$. We then find that on $R$,
% \begin{align*}
%     RSK &= \left( \rho_{\lozenge_{0,0}^{0,s-r-1} }^{-1} \circ \dots \circ \rho^{-1}_{\lozenge_{r,0}^{r,s-1}}  \right) \circ \rho_{\Lambda_{0,s-r}}^{-1} \circ \dots \circ \rho_{\Lambda_{r-1,s-1}}^{-1} \circ \phi^{-1} \\
%     &= \left( \rho_{\lozenge_{0,0}^{0,s-r-1}}^{-1} \right) \circ \left( \rho_{\lozenge_{1,0}^{1,s-r}}^{-1} \circ \rho_{\Lambda_{0,s-r}}^{-1} \right) \circ \dots \circ \left( \rho_{\lozenge_{r,0}^{r,s-1}}^{-1} \circ \rho_{\Lambda_{r-1,s-1}}^{-1} \right) \circ \phi^{-1} \\
%     &= \rho_{\Lambda_{0,s-(r+1)}}^{-1} \circ \rho_{\Lambda_{1,s-r}}^{-1} \circ \dots \circ \rho_{\Lambda_{(r+1)-1,s-1} }^{-1} \circ \phi^{-1}.\qedhere
% \end{align*}
\begin{align*}
    rsk &= \left( \rho_{I_1}^{-1} \circ \rho_{I_2}^{-1} \dots \circ \rho^{-1}_{I_{r-1}}  \right) \circ \rho_{[1] \times[s-r+2]}^{-1} \circ \dots \circ \rho_{[r-2]\times[s-1]}^{-1} \circ \phi^{-1} \\
    &= \left( \rho_{I_1}^{-1} \right) \circ \left( \rho_{I_2}^{-1} \circ \rho_{[1]\times[s-r+2]}^{-1} \right) \circ \dots \circ \left( \rho_{I_{r-1}}^{-1} \circ \rho_{[r-2]\times[s-1]}^{-1} \right) \circ \phi^{-1} \\
    &= \rho_{[1]\times[s-r+1]}^{-1} \circ \rho_{[2]\times[s-r+2]}^{-1} \circ \dots \circ \rho_{[r-1]\times[s-1]}^{-1} \circ \phi^{-1}\\
    &= RSK.\qedhere
\end{align*}
\end{proof}

% Note that the value at $(i,j)$ after a toggle depends only on $(i,j)$ and the elements of $R$ that form cover relations with it. Then
% \begin{align*}
%     &\rho_{\Lambda_{r-\min(r,s),s-\min(r,s)}}^{-1} \circ \dots \circ \rho_{\Lambda_{r-1,s-1}}^{-1} \circ \phi^{-1}(x)_{r-i,s-j} \\
%     &= \rho_{\Lambda_{r-\min(r,s),s-\min(r,s)}}^{-1} \circ \dots \circ \rho_{\Lambda_{r-\min(i,j)-1,s-\min(i,j)-1}}^{-1} \circ \rho_{\Lambda_{r-\min(i,j),s-\min(i,j)}}^{-1} \circ \dots \circ  \rho_{\Lambda_{r-1,s-1}}^{-1} \circ \phi^{-1}(x)_{r-i,s-j} \\
%     &= \rho_{\Lambda_{r-\min(r,s),s-\min(r,s)}}^{-1} \circ \dots \circ \rho_{\Lambda_{r-\min(i,j)-1,s-\min(i,j)-1}}^{-1} \circ  \rho^{-\min(i,j)} \circ \phi^{-1}(x)_{r-i,s-j} \\
% \end{align*}
% The remaining applications of rowmotion on order ideals do not change the value of this element.

\subsection{Relation to chain sums and Stanley--Thomas words}



% The left hand side is the sum of the top $k$ labels of $RSK(x)$ in the file containing the maximum element. 

% But by the definition of $RSK$, this central file has entries $\lambda_1,\dots, \lambda_r$ since the central file is the top row of the associated Gelfand-Tsetlin patterns of RSK$(x)$. Consequently

% \[\sum\limits_{i=0}^{k-1} \text{RSK}(x)_{r-i,s-i} = \sum\limits_{i=1}^k \lambda_i.\]

% If the labeling of $R$ is a permutation matrix, then the maximum weight collection of $k$ disjoint chains (the right hand side above) corresponds to the maximum size of $k$ disjoint increasing subsequences in the associated permutation. We note that the maximum weight attained by $k$ disjoint chains is attained by a collection of $k$ nonintersecting lattice paths that contain the $k$ chains. Hence this restricts to the original Greene's theorem.


Since $RSK$ is invertible, any $x \in \mathbb R^R_{>0}$ is uniquely determined by $RSK(x)$. From Theorem~\ref{plGreene}, it follows that the values of $w_{I}^{(k)}(x)$, where $I$ has the form $[r]\times[j]$ or $[i]\times[s]$, determine $x$.

Perhaps even more relevant for our work with rowmotion, we can also characterize $x$ using the types of chain sums that appear in Lemma~\ref{chainshift} with $k=1$.

\begin{Th} \label{thm:chainsums}
Let $x \in \mathbb{R}^R_{>0}$. The chain sums $w_I^{(1)}(x)$, where $I$ ranges over intervals of the form $[r] \times [u,v]$ and $[u,v] \times [s]$, uniquely determine $x$.
\end{Th}
\begin{proof}
By the Lindstr\"om--Gessel--Viennot Lemma on $R$ (using vertex weights), we can express any $w_{[r] \times [j]}^{(k)}$ as a determinant of a matrix with entries of the form $w_{[r] \times [u,v]}^{(1)}$, and similarly any $w_{[i] \times [s]}^{(k)}$  is determined by the values $w_{[u,v] \times [s]}^{(1)}$.
By Theorem~\ref{plGreene}, each entry of $RSK(x)$ is a quotient of (or equal to) entries of the form $w_{[r]\times[j]}^{(k)}$ or $w_{[i]\times[s]}^{(k)}$, so the result follows.

(In fact, we do not even need $w_{[r] \times [u,s]}^{(1)}$ for $2 \leq u \leq s$ since $w_{[r] \times [s]}^{(k)}$ can be computed from the other chain sums.)
\end{proof}

% \begin{Th}
% Let $x \in \mathbb{R}^R_{>0}$. Then the collection $\{\emph{ST}_i\}_{0 \leq i \leq r}$ of generalized Stanley--Thomas words uniquely determines $x$. 
% \end{Th}

% \begin{proof}
% We will show that the set $\{\text{ST}_i(x)\}_{0 \leq i \leq r}$ uniquely determines RSK$(x)$. By TODO: REFERENCE SOMETHING, we know the Stanley--Thomas words determine $S_{i,0}^{r,s}$ where $0 \leq i \leq r$ and $S_{0,j}^{r,s}$ where $0 \leq j \leq s$. For $(i,j) \in R$, we proceed by induction on $\min(r-i,s-j)$. 

% For the base case, if $\min(r-i,s-j) = 0$, then
% \[\text{RSK}(x)_{ij} = \phi^{-1}(x)_{ij}.\]
% Note that this quantity is of the form $S_{0,0}^{r-i,s}$ or $S_{0,0}^{r,s-j}$. 

% For the induction step suppose that the generalized Stanley--Thomas words determine RSK$(x)_{ij}$ when $\min(r-i,s-j) \leq k-1$ for some $k \geq 1$. Let $(i,j) \in R$ such that $\min(r-i,s-j) = k$. Without loss of generality, suppose $r-i =k$. Since
% \[\text{RSK}(x)_{ij} = \frac{\prod\limits_{\ell = 0}^k RSK(x)_{i+\ell,j+\ell}}{\prod\limits_{\ell = 0}^{k-1} RSK(x)_{i+\ell,j+\ell}}\]
% by birational Greene's theorem, it suffices to compute $S_{0,0}^{r-i,s}(k)$ using the Stanley--Thomas words. Define a graph $G$ to have vertices $(a,b)$ such that $0 \leq a \leq r$ and $0 \leq b \leq s+1$ and edges of the form $(a,b) \to (a+1,b)$ if $a <r$ and $b \leq s$, $(a,b) \to (a,b+1)$ if $b \leq s$. Weight the edges $(a,b) \to (c,d)$ of $G$ by $x_{a,b}$ (See TODO: INSERT FIGURE for a visual example), so that the weight of all nonintersecting lattice paths from $A_a$ to $B_b$ is $S_{a,0}^{r-k+1+b}$. Let $A_\ell = (\ell,0)$ let $B_{\ell} = (r-k+1+\ell,s+1)$ for for $0 \leq \ell \leq k-1$. Define a $k \times k$ matrix $M$ such that $M_{ab} = S_{a,0}^{r-k+1+b}$. By the Lindstr\"om lemma
% \[\det(M) = S_{0,0}^{r-i,s}(k).\]
% Hence RSK$(x)_{ij}$ is uniquely determined by the Stanley--Thomas words.
% \end{proof}

\begin{Ex}
    Let $R = [2] \times [3]$, and take $x \in \mathbb R_{>0}^R$ to be labeled as in Figure~\ref{fig:shifting}. From Theorem~\ref{thm:chainsums}, $x$ is uniquely determined by the following chain sums:
    \[
    w_{[2] \times [1,1]}^{(1)} = ab, \quad w_{[2] \times [1,2]}^{(1)} = abd+acd,\quad w_{[2] \times [2,2]}^{(1)} = cd, \]\[w_{[1,1] \times [3]}^{(1)} = ace, \quad w_{[1,2] \times [3]}^{(1)} = abdf+acdf+acef, \quad w_{[2,2] \times [3]}^{(1)} = bdf.\]
    Indeed, from these we can compute
    \begin{align*}
        w_{[2] \times [1,2]}^{(2)} &= \left|\begin{matrix}w_{[2] \times [1,1]}^{(1)} & w_{[2] \times [1,2]}^{(1)}\\0&w_{[2] \times [2,2]}^{(1)}\end{matrix}\right|  = abcd,\\
        w_{[1,2] \times [3]}^{(2)} &= \left|\begin{matrix}w^{(1)}_{[1,1] \times [3]} &w^{(1)}_{[1,2] \times [3]}\\0& w^{(1)}_{[2,2] \times [3]}\end{matrix}\right| = abcdef.
    \end{align*}
    We can then compute $RSK(x)$ using Theorem~\ref{plGreene}:
    \begin{align*}
        RSK(x)_{11} &= \frac{w_{[2] \times [1,2]}^{(2)}}{w_{[2] \times [1,2]}^{(1)}} = \frac{abcd}{abd+acd},\\
        RSK(x)_{12} &= \frac{w_{[1,2] \times [3]}^{(2)}}{w_{[1,2] \times [3]}^{(1)}} = \frac{abcdef}{abdf+acdf+acef},\\
        RSK(x)_{13} &= w_{[1,1] \times [3]}^{(1)} = ace,\\
        RSK(x)_{21} &=  w_{[2] \times [1,1]}^{(1)} = ab,\\
        RSK(x)_{22} &=  w_{[2] \times [1,2]}^{(1)} = abd+acd,\\
        RSK(x)_{23} &= w_{[1,2] \times [3]}^{(1)} = abdf+acdf+acef.
    \end{align*}
    It follows that $RSK(x)$ and hence $x$ are uniquely determined.
\end{Ex}

In particular, since these chain sums all appear in the generalized Stanley--Thomas words, the following corollary is immediate.

\begin{Cor}
The map $\phi \circ \rho \circ \phi^{-1}$ is the unique function on $\mathbb R^R_{>0}$ that cyclically shifts the generalized Stanley--Thomas words $ST_i$ and $\overline{ST}_j$.
\end{Cor}

It follows that the cyclic shifting of the generalized Stanley--Thomas words could be used to prove periodicity of birational rowmotion on rectangles. Of course, presently our method of proving this cyclic shifting yielded a proof of periodicity more directly. However, the techniques in our follow-up work \cite{johnsonliu3} can be used to derive this cyclic shifting in a manner that is more independent of periodicity.

By Lemma~\ref{chainshift}, most of the chain sums $w_I^{(1)}$ considered above get sent to other such sums. It follows that the chain shifting lemma determines ``most'' of rowmotion in the following sense.

%sense that we can use it to determine $RSK(\phi \circ \rho^{-1} \circ \phi^{-1}(x))_{ij}$ whenever $j-i \neq s-r$. Indeed, to compute the $(i,j)$th coordinate of the $RSK$ map where $j-i<s-r$, we need only compute the values of $w_{[r] \times [j+r-i]}^{(k)}$ for $k \leq r-i+1$ by Theorem~\ref{plGreene}. Since $j+r-i<s$, by Lemma~\ref{chainshift}, $w_{[r] \times [j+r-i]}^{(k)}(\phi \circ \rho^{-1} \circ \phi^{-1}(x)) = w_{[r],[2,j+r-i+1]}^{(k)}(x)$. (The entries with $j-i>s-r$ can likewise be obtained using the reflected version of Lemma~\ref{chainshift}.)


\begin{Cor}
The chain shifting property of $\phi \circ \rho^{-1} \circ \phi^{-1}$ (stated in Lemma~\ref{chainshift})
uniquely determines $RSK(\phi \circ \rho^{-1} \circ \phi^{-1}(x))_{ij}$, where $j-i \neq s-r$.
\end{Cor}

\begin{proof}
To compute the $(i,j)$th coordinate of the $RSK$ map where $j-i<s-r$, we need only compute the values of $w_{[r] \times [j+r-i]}^{(k)}$ for $k \leq r-i+1$ by Theorem~\ref{plGreene}. Since $j+r-i<s$, by Lemma~\ref{chainshift}, $w_{[r] \times [j+r-i]}^{(k)}(\phi \circ \rho^{-1} \circ \phi^{-1}(x)) = w_{[r],[2,j+r-i+1]}^{(k)}(x)$.

The entries with $j-i>s-r$ can likewise be obtained using the reflected version of Lemma~\ref{chainshift}.
\end{proof}









 
\longthanks{The authors would like to thank Sam Hopkins, Alexander Postnikov, Darij Grinberg, and Tom Roby for useful conversations, as well as the anonymous referees for their helpful comments.}




%Other references
%Gessel-Viennot Citation
%\nocite{*}
\bibliographystyle{mersenne-plain-nobysame}
\bibliography{ALCO_Johnson_795}
\end{document}