% Template article for preprint document class `elsart'
% SP 2001/01/05
% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/
\documentclass{ctwart}
% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}
% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}
% The amssymb package provides various useful mathematical symbols
\usepackage[latin1]{inputenc}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{bm}
\usepackage{graphicx}
\newcommand{\Z}{ \mathbb Z}
\newcommand{\N}{ \mathbb N}
\newcommand{\R}{ \mathbb R}
\newcommand{\C}{ \mathbb C}
\newcommand{\PP}{ \mathbb P}
\newcommand{\p}[1]{\mathcal{#1}}
\newcommand{\s}[1]{\mathbf{#1}}
\newcommand{\vp}{\varphi}
\newcommand{\set}[1]{\{#1\}}
\newcommand{\detq}{{\textstyle \det_q}}
\newcommand{\detqq}{{\textstyle \det_{\s q}}}
\newcommand{\longto}{\longrightarrow}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\indeg}{indeg}
\DeclareMathOperator{\outdeg}{outdeg}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\vol}{vol}
\begin{document}
\begin{frontmatter}
% Title, authors and addresses
% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}
\title{}
% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}
\author{}
\address{}
\begin{keyword}
% keywords here, in the form: keyword \sep keyword
\end{keyword}
\end{frontmatter}
\section{Introduction}
Some combinatorial results have an easy proof via generating functions and a more elusive, but also more interesting and important, bijective proof. It would be difficult to think of a better example of this than the generalization of Euler's classical distinct/odd theorem due to George Andrews (Theorem \ref{andrews}). The proof via generating functions is a trivial one-line calculation. On the other hand, the simplest bijective proof of this result, O'Hara's algorithm, is distinctly non-trivial and has numerous fascinating properties.
\medskip
Note that a quest to find bijective proofs of partition identities goes back all to way to the pioneer work of Sylvester and his school. Despite remarkable successes in the last century (see~\cite{P3}) and some recent work of both positive and negative nature (see e.g.~\cite{P2,P4}), the problem remains ambiguous and largely unresolved. Much of this stems from the lack of clarity as to what exactly constitutes a bijective proof. Depending on whether one accentuates simplicity, ability to generalize, the time complexity, geometric structure, or asymptotic stability, different answers tend to emerge.
\medskip
In one direction, the subject of partition bijections was revolutionized by Garsia and Milne with their \emph{involution principle}~\cite{GM1,GM2}. This is a combinatorial construction which allows to use a few basic bijections and involutions to build more involved combinatorial maps. As a consequence, one can start with a reasonable analytic proof of a partition identity and trace every step to obtain a (possibly extremely complicated) bijective construction. Garsia and Milne used this route to obtain a long sought bijection proving the Rogers-Ramanujan identities, resolving an old problem in this sense~\cite{GM2}. Unfortunately, this bijection is too complex to be analyzed and has yet to lead to new Rogers-Ramanujan type partition identities.
\medskip
After Garsia-Milne paper, there has been a flurry of activity to obtain synthetic bijections for large classes of partition identities. Most of these bijections did not seem to lead anywhere with one notable exception. Remmel and Gordon found (rather involved) bijective proofs of the above-mentioned partition identity due to Andrews~\cite{R,G}. O'Hara's streamlined proof is in fact a direct generalization of Glaisher's classical bijection proving Euler's theorem. Moreover, in her thesis~\cite{O1}, O'Hara showed that her bijection is computationally efficient in certain special cases. Until now, the reason why O'Hara's bijection has a number of
nice properties distinguishing it from the other ``involution principle bijections'' remained mysterious.
\medskip
In this extended abstract, we present results of both positive and negative type. First, we analyze the complexity of O'Hara's bijection, which we view as a discrete algorithm. Theorem~\ref{main1} gives an \emph{exact} formula for the number of steps of the algorithm in certain cases. From here it follows that O'Hara's bijection is computationally efficient in many special cases. On the other hand, perhaps surprisingly, the number of steps can be (mildly) exponential in the worst case (Theorem~\ref{main4} part (\ref{main4c})). This is the first negative result of this kind, proving the analogue of a conjecture that remains open for the Garsia-Milne's ``Rogers-Ramanujan bijection'' (see Subsection~\ref{final1}).
\medskip
Second, we show that O'Hara's bijection has a rich underlying geometry. In a manner similar to that in~\cite{P1,PV}, we view this bijection as a map between integer points in polytopes which preserves certain linear functionals. We present an advanced generalization of Andrews's result and of O'Hara's bijection in this geometric setting. In a special case, the working of the map corresponds to the Euclid algorithm and, more generally, to terms in the continuing fractions.
Thus one can also think of our generalization as a version of multidimensional continuing fractions.
\medskip
Finally, by combining the geometric and complexity ideas we see that in the finite dimensional case the map defined by O'Hara's bijection is a solution of an integer linear programming problem. This implies that the map defined by the bijection can be computed in polynomial time,
i.e.\hspace{-0.07cm} much more efficiently than by O'Hara's bijection.
\medskip
The extended abstract is structured as follows. We start with definitions and notations in Section~\ref{defs}. In Section~\ref{main}, we describe the main results on both geometry and complexity. We conclude with final remarks in Section~\ref{final}.
\medskip
Due to space constraints, we present almost no proofs. An interested reader is invited to find the proofs and some other results in the paper \cite{ohara}, on which this abstract is based.
\bigskip
\section{Definitions and background} \label{defs}
\subsection{Andrews's theorem}
A \emph{partition} $\lambda$ is an integer sequence $(\lambda_1,\lambda_2,\ldots,\lambda_\ell)$ such that $\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_\ell > 0$, where the integers $\lambda_i$ are called the \emph{parts} of the partition. The sum $n=\sum_{i=1}^\ell \lambda_i$ is called the \emph{size} of $\lambda$, denoted $|\lambda|$; in this case we say that $\lambda$ is a partition of $n$, and write $\lambda \vdash n$. We can also write $\lambda=1^{m_1}2^{m_2}\cdots$, where $m_i=m_i(\lambda)$ is the number of parts of $\lambda$ equal to $i$. The \emph{support} of $\lambda=1^{m_1}2^{m_2}\cdots$ is the set $\set{i \colon m_i > 0}$. The set of all positive integers will be denoted by $\PP$.
\medskip
Denote the set of all partitions by $\p P$ and the set of all partitions of $n$ by $\p P_n$. The number of partitions of $n$ is given by Euler's formula
$$\sum_{\lambda \in \p P} t^{|\lambda|} = \sum_{n=0}^\infty |\p P_n| t^n = \prod_{i=1}^\infty \frac 1{1-t^i}.$$
For a sequence $\overline a = (a_1,a_2,\ldots)$ with $a_i \in \PP \cup \set{\infty}$, define $\p A$ to be the set of partitions $\lambda$ with $m_i(\lambda) < a_i$ for all $i$; write $\p A_n = \p A \cap \p P_n$. Denote by $\supp (\overline a) = \set{i \colon a_i < \infty}$ the \emph{support} of the sequence $\overline a$.
\medskip
Let $\overline a = (a_1,a_2,\ldots)$ and $\overline b = (b_1,b_2,\ldots)$. We say that $\overline a$ and $\overline b$ are \emph{$\varphi$-equivalent}, $\overline a \sim_\varphi \overline b$, if $\varphi$ is a bijection $\supp(\overline a) \to \supp(\overline b)$ such that $i a_i = \varphi(i) b_{\varphi(i)}$ for all $i$. If $\overline a \sim_\varphi\overline b$ for some $\varphi$, we say that $\overline a$ and $\overline b$ are equivalent, and write $\overline a \sim \overline b$.
\begin{thm}[Andrews] \label{andrews}
If $\overline a \sim \overline b$, then $|\p A_n| = |\p B_n|$ for all $n$.
\end{thm}
\textbf{Proof:}
We use the notation $t^\infty = 0$. Clearly,
$$\sum_{n = 0}^\infty |\p A_n| t^n = \prod_{i=1}^\infty \frac{1-t^{ia_i}}{1-t^i} = \prod_{j=1}^\infty \frac{1-t^{jb_j}}{1-t^j} = \sum_{n = 0}^\infty |\p B_n| t^n,$$
which means that $|\p A_n| = |\p B_n|$. $\qed$
Consider the classical Euler's theorem on partitions into distinct and odd parts. For $\overline a = (2,2,\ldots)$ and $\overline b = (\infty,1,\infty,1,\ldots)$, $\p A_n$ is the set of all partitions of $n$ into distinct parts, and $\p B_n$ is the set of partitions of $n$ into odd parts. The bijection $i \mapsto 2i$ between $\supp(\overline a)=\PP$ and $\supp(\overline b)=2\PP$ satisfies $ia_i = \varphi(i) b_{\varphi(i)}$, so $\overline a \sim_\varphi \overline b$ and $|\p A_n| = |\p B_n|$. We refer to this example as the \emph{distinct/odd case}.
\bigskip \subsection{O'Hara's algorithm}
The analytic proof of Andrews's theorem shown above does not give an explicit bijection $\p A_n \to \p B_n$. Such a bijection is, by Theorem~\ref{defs2}, given by the following algorithm.
\begin{alg}\label{defs4}
\emph{(O'Hara's algorithm on partitions)}
\begin{itemize}
\item[] \emph{\texttt{Fix:} sequences $\overline a \sim_\varphi \overline b$}
\item[] \emph{\texttt{Input:} $\lambda \in \p A$}
\item[] \emph{\texttt{Set:} $\mu \leftarrow \lambda$}
\item[] \emph{\texttt{While:} $\mu$ contains more than $b_j$ copies of $j$ for some $j$}
\begin{itemize}
\item[] \emph{\texttt{Do:} remove $b_j$ copies of $j$ from $\mu$, add $a_i$ copies of $i$ to $\mu$, where $\varphi(i)=j$}
\end{itemize}
\item[] \emph{\texttt{Output:} $\psi(\lambda) \leftarrow \mu$}
\end{itemize}
\end{alg}
\begin{thm}[O'Hara] \label{defs2}
Algorithm~\ref{defs4} stops after a finite number of steps. The resulting partition $\psi(\lambda) \in \p B$ is independent of the order of the parts removed and defines a size-preserving bijection $\p A \to \p B$.
\end{thm}
Denote by $L_\varphi(\lambda)$ the number of steps O'Hara's algorithm takes to compute $\psi(\lambda)$, and by $\p L_\varphi(n)$ the maximum value of $L_\varphi(\lambda)$ over all $\lambda \vdash n$.
%\begin{exm}
In the distinct/odd case, O'Hara's algorithm gives the inverse of Glaisher's bijection, which maps $\lambda=1^{m_1}3^{m_3}\cdots \in \p B$ to the partition $\mu \in \p A$ which contains $i 2^j$ if and only if $m_i$ has a $1$ in the $j$-th position when written in binary.
\qed %\end{exm}}
%\begin{exm} \label{defs3}
Let $\overline a = (1,1,4,5,3,1,1,\ldots)$, $\overline b = (1,1,5,3,4,1,1,\ldots)$ and $\varphi(3)=4$, $\varphi(4)=5$, $\varphi(5)=3$, $\varphi(i)=i$ for $i \neq 3,4,5$; observe that $\overline a \sim_\varphi \overline b$. Then O'Hara's algorithm on $\lambda=3^3 4^4 5^2$ runs as follows:
$$\begin{array}{cccccccccc}
& \mathbf{3^3 4^4 5^2} & \to & \scriptstyle 3^7 4^1 5^2 & \to & \scriptstyle 3^2 4^1 5^5 & \to & \scriptstyle 3^2 4^6 5^1 & \to & \scriptstyle 3^6 4^3 5^1 \\
\to & \scriptstyle 3^{10} 4^0 5^1 & \to & \scriptstyle 3^5 4^0 5^4 & \to & \scriptstyle 3^0 4^0 5^7 & \to & \scriptstyle 3^0 4^5 5^3 & \to & \mathbf{3^4 4^2 5^3}
\end{array}$$
We have $L_\varphi(\lambda) = \p L_\varphi(35) = 9$.
\qed %\end{exm}}
%\begin{exm}
Take $\overline a = (2,2,1,2,2,1,\ldots)$ and $\overline b=(3,1,3,1,\ldots)$. Here $\p A$ is the set of partitions into distinct parts $\equiv \pm 1$ mod $3$, and $\p B$ is the set of partitions into odd parts, none appearing more than twice. Define $\varphi \colon \PP \to \PP$ as follows:
\begin{equation} \label{defs1}
\varphi(i) = \left\{ \begin{array}{cl} i & \mbox{ if } i \mbox{ is divisible by 6} \\ i/3 & \mbox{ if } i \mbox{ is divisible by 3, but not by 2}\\ 2i & \mbox{ if } i \mbox{ is not divisible by 3} \end{array}\right..
\end{equation}
Clearly, $\overline a \sim_\varphi \overline b$. O'Hara's algorithm on $1^1 2^1 8^1 10^1 14^1 20^1$ runs as follows:
$$\scriptstyle
\begin{array}{ccccccccccc}
& \mathbf{1^1 2^1 8^1 10^1 14^1 20^1} & \to & \scriptstyle 1^1 2^1 8^1 10^3 14^1 & \to & \scriptstyle 1^1 2^1 7^2 8^1 10^3 & \to & \scriptstyle 1^1 2^1 5^2 7^2 8^1 10^2 \\
\to & \scriptstyle 1^1 2^1 5^4 7^2 8^1 10^1 & \to & \scriptstyle 1^1 2^1 5^6 7^2 8^1 & \to & \scriptstyle 1^1 2^1 4^2 5^6 7^2 & \to & \scriptstyle 1^1 2^3 4^1 5^6 7^2 \\
\to & \scriptstyle 1^1 2^5 5^6 7^2 & \to & \scriptstyle 1^3 2^4 5^6 7^2 & \to & \scriptstyle 1^5 2^3 5^6 7^2 & \to & \scriptstyle 1^7 2^2 5^6 7^2 \\
\to & \scriptstyle 1^9 2^1 5^6 7^2 & \to & \scriptstyle 1^{11} 5^6 7^2 & \to & \scriptstyle 1^{11} 5^3 7^2 15^1 & \to & \scriptstyle 1^{11} 7^2 15^2 \\
\to & \scriptstyle 1^8 3^1 7^2 15^2 & \to & \scriptstyle 1^5 3^2 7^2 15^2 & \to & \scriptstyle 1^2 3^3 7^2 15^2 & \to & \mathbf{1^2 7^2 9^1 15^2}
\end{array}$$
%$$1^1 2^1 8^1 10^1 14^1 20^1 \to 1^1 2^1 8^1 10^3 14^1 \to 1^1 2^1 7^2 8^1 10^3 \to 1^1 2^1 5^2 7^2 8^1 10^2 \to $$
%$$1^1 2^1 5^4 7^2 8^1 10^1 \to 1^1 2^1 5^6 7^2 8^1 \to 1^1 2^1 4^2 5^6 7^2 \to 1^1 2^3 4^1 5^6 7^2 \to 1^1 2^5 5^6 7^2 \to $$
%$$1^3 2^4 5^6 7^2 \to 1^5 2^3 5^6 7^2 \to 1^7 2^2 5^6 7^2 \to 1^9 2^1 5^6 7^2 \to 1^{11} 5^6 7^2 \to 1^{11} 5^3 7^2 15^1 \to $$
%$$1^{11} 7^2 15^2 \to 1^{8} 3^1 7^2 15^2 \to 1^{5} 3^2 7^2 15^2 \to 1^2 3^3 7^2 15^2 \to 1^2 7^2 9^1 15^2$$
The bijection $\psi$ is similar in spirit to Glaisher's bijection: given $\lambda=1^{m_1}2^{m_2}4^{m_4}5^{m_5}\cdots \in \p A$ and $j \in \PP$, the number of copies of part $2j-1$ in $\psi(\lambda)$ is equal to the $k$-th digit in the ternary expansion of $l$, where $k$ is the highest power of $3$ dividing $2j-1$, $2j-1=3^k r$, and $l = \sum_i 2^im_{r2^i}$.
\qed %\end{exm}}
\bigskip \subsection{Equivalent sequences and graphs} \label{graphs}
Choose equivalent sequences $\overline a$, $\overline b$. Define a directed graph $G_\varphi$ on $\supp (\overline a) \cup \supp (\overline b)$ by drawing an edge from $i$ to $j$ if $\varphi(j) = i$; an arrow from $i$ to $j$ therefore means that O'Hara's algorithm simulta\-neously removes copies of $i$ and adds copies of $j$. Each vertex $v$ has $\indeg v \leq 1$, $\outdeg v \leq 1$ and $\indeg v + \outdeg v \geq 1$. The graph splits into connected components of the following five types:
\begin{enumerate}
\renewcommand{\theenumi}{\roman{enumi}}
\item \label{defs5a} cycles of length $m \geq 1$;
\item \label{defs5b} paths of length $m \geq 2$;
\item \label{defs5d} infinite paths with an ending point, but without a starting point;
\item \label{defs5c} infinite paths with a starting point, but without an ending point;
\item \label{defs5e} infinite paths without a starting point or an ending point.
\end{enumerate}
%\begin{exm}
Figure~\ref{fig1} shows portions of graphs $G_\varphi$ for certain $\varphi$:
\begin{enumerate}
\item $\overline a = (1,1,4,5,3,1,1,\ldots)$, $\overline b = (1,1,5,3,4,1,1,\ldots)$, $\varphi(3)=4$, $\varphi(4)=5$, $\varphi(5)=3$, $\varphi(i)=i$ for $i \neq 3,4,5$; components of $G_\varphi$ are of type (\ref{defs5a});
\item $\overline a = (\infty,1,2,3,\infty,\infty,\infty,\ldots)$, $\overline b=(2,3,4,\infty,\infty,\infty,\infty,\ldots)$, $\varphi(2)=1$, $\varphi(3)=2$, $\varphi(4)=3$; $G_\varphi$ is of type (\ref{defs5b});
\item the distinct/odd case: $\overline a = (2,2,\ldots)$, $\overline b = (\infty,1,\infty,1,\ldots)$, $\varphi(i) = 2i$; components of $G_\varphi$ are of type (\ref{defs5d});
\item the odd/distinct case: $\overline a = (\infty,1,\infty,1,\ldots)$, $\overline b = (2,2,\ldots)$, $\varphi(i) = i/2$; components of $G_\varphi$ are of type (\ref{defs5c});
\item $\overline a = (2,2,1,2,2,1,\ldots)$ and $\overline b=(3,1,3,1,\ldots)$, $\varphi$ given by~\eqref{defs1}; components of $G_\varphi$ are of types~\eqref{defs5a} and~\eqref{defs5e}. \qed
% $$\varphi(i) = \left\{ \begin{array}{ccl} i & : & i \mbox{ divisible by 6} \\ i/3 & : & i \mbox{ divisible by 3, but not by 2}\\ 2i & : & i \mbox{ divisible by 3} \end{array}\right..$$
\end{enumerate}
%\end{exm}}
\begin{figure}[ht]
\begin{center}
% \includegraphics[width = 0.79 \textwidth]{ohara1}
\end{center}
\caption{Examples of graphs $G_\varphi$.}
\label{fig1}
\end{figure}
\bigskip \subsection{Scissor-congruence and $\Pi$-congruence}
We say that convex polytopes $A,B$ in $\R^m$ are \emph{congruent}, write $A \simeq B$, if $B$ can be obtained from $A$ by rotation and translation. For convex polytopes $P,Q \subset \R^m$, we say that they are \emph{scissor-congruent} if $P$ can be cut into finitely many polytopes which can be rearranged and assembled into $Q$, i.e.\hspace{-0.07cm} if $P$ and $Q$ are the disjoint union of congruent polytopes: $P=\cup_{i=1}^n P_i$, $Q=\cup_{i=1}^n Q_i$, $P_i \simeq Q_i$.
\medskip
Let $\pi$ be a linear functional on $\R^m$. If $Q_i$ can be obtained from $P_i$ by a translation by a vector in the hyperplane $\p H= \set{\s x \in \R^m \colon \pi(\s x) = 0}$, we say that $P$ and $Q$ are \emph{$\pi$-congruent}. If $P$ and $Q$ are $\pi$-congruent for some linear functional $\pi$, we say that they are \emph{$\Pi$-congruent}.
\medskip
If $P$ can be cut into countably many polytopes which can be translated by a vector in the hyperplane $\p H = \set{\s x \in \R^m \colon \pi(\s x) = 0}$ and assembled into $Q$, we say that $P$ and $Q$ are \emph{approximately $\pi$-congruent}. We say that they are \emph{approximately $\Pi$-congruent} if they are approximately $\pi$-congruent for some linear functional $\pi$. If $P$ and $Q$ are approximately $\pi$-congruent, there exist, for every $\varepsilon>0$, $\pi$-congruent polytopes $P_\varepsilon \subseteq P$ and $Q_\varepsilon \subseteq Q$, such that $\vol(P \setminus P_\varepsilon) < \varepsilon$ and $\vol(Q \setminus Q_\varepsilon) < \varepsilon$.
\medskip
Finally, let $\s R(a_1,\ldots,a_m)=[0,a_1) \times \cdots \times [0,a_m)$ be a box in $\R^m$, and let $R(a_1,\ldots,a_m) = \s R(a_1,\ldots,a_m) \cap \Z^m$ be the set of its integer points.
%\begin{exm}\label{ex-euclid}
Let $d=2$ and $\pi(x,y)=x+y$. Euclid's algorithm on $(a,b)$ yields a $\pi$-congruence between $\s R(a,b)$ and $\s R(b,a)$: if $b = r_1 a + s_1$ with $0 \leq s_1 < a$, divide $[0,a) \times [0,r_1 a)$ into $r_1$ squares with side $a$, and translate the square $[0,a) \times [i a, (i+1) a)$ by the vector $(i a, - i a)$ to $[i a, (i+1) a) \times [0,a)$. Then write $a = r_2 s_1 + s_2$ with $0 \leq s_2 < s_1$, divide $[0,a) \times [r_1 a, b)$ into $r_2$ squares with side $s_1$, and translate the square $[i s_1, (i+1) s_1) \times [r_1 a, b)$ by the vector $(r_1 a - i s_1,i s_1 - r_1 a)$ to $[r_1 a, b) \times [i s_1, (i+1) s_1)$. Continue until the remainder $s_i$ is equal to $0$. The first drawing of Figure~\ref{fig5} gives an example.
\smallskip
The second drawing shows that boxes $\s R(12,8)$ and $\s R(32,3)$ are $\pi$-congruent for $\pi(x,y)=x+4y$. Finally, in Figure~\ref{fig2} we give a $\pi$-congruence between $\s R(4,5,3)$ and $\s R(5,3,4)$ for $\pi(x,y,z)=3x+4y+5z$. \qed
\begin{figure}[ht]
\begin{center}
% \includegraphics[width = 0.7 \textwidth]{ohara5}
%\epsfig{file=ohara5.eps,height=5cm}
\end{center}
\caption{Two $\Pi$-congruences.}%\caption{$\Pi$-congruence between $\s R(12,26)$ and $\s R(26,12)$, and between $\s R(12,8)$ and $\s R(32,3)$.}
\label{fig5}
\end{figure}
\begin{figure}[ht]
\begin{center}
% \includegraphics[width=0.2\textwidth]{ohara2}
%\epsfig{file=ohara2.eps,height=3.3cm}
\begin{minipage}{2cm}
\begin{center}
\vspace{-2cm}
$\stackrel{\bm \psi}{\longrightarrow} \!\!$
\vspace{2cm}
\end{center}
\end{minipage}
% \includegraphics[width=0.2\textwidth]{ohara4}
%\epsfig{file=ohara4.eps,height=3.3cm}
\end{center}
\caption{$\pi$-congruence between $\s R(4,5,3)$ and $\s R(5,3,4)$.}
\label{fig2}
\end{figure}
%\end{exm}}
\bigskip
\section{Main results} \label{main}
\subsection{Continuous O'Hara's algorithm and $\Pi$-congruences}
Take the case when $G_\varphi$ is a cycle $i_1 \to i_m \to i_{m-1} \to \ldots \to i_1$. In this case, $\varphi(i_1)=i_2$, $\varphi(i_2)=i_3$, etc. Throughout this section, identify a partition $i_1^{t_1}\cdots i_m^{t_m}$ with the vector $\s t = (t_1,\ldots,t_m)$. By Theorem~\ref{defs2}, O'Hara's algorithm defines a bijection $\psi \colon R(a_1,\ldots,a_m) \to R(b_1,\ldots,b_m)$, where $i_j a_j = i_{j+1} b_{j+1}$ for all $j$, where the indices are taken cyclically. The following algorithm (see also Theorem~\ref{main1}) generalizes $\psi$ to the continuous setting. It gives a bijection ${\bm \psi} \colon \s R(a_1,\ldots,a_m) \to \s R(b_1,\ldots,b_m)$, which is defined also for non-integer $a_j,b_j$. When $a_j,b_j$ are integers, it is an extension of $\psi \colon R(a_1,\ldots,a_m) \to R(b_1,\ldots,b_m)$. As an immediate corollary, we prove that two boxes with rational coordinates and with equal volume are $\Pi$-congruent. We can use Theorem~\ref{main1} to give an alternative proof of Theorem~\ref{defs2}.
\begin{alg}\label{main7}
\emph{(continuous O'Hara's algorithm)}
\begin{itemize}
\item[] \emph{\texttt{Fix:} $\s i = (i_1,\ldots,i_m) \in \R_+^m$}
\item[] \emph{\phantom{\texttt{Fix:}} $\s a = (a_1,\ldots,a_m) \in \R_+^m$, $\s b = (b_1,\ldots,b_m) \in \R_+^m$ with $i_ja_j = i_{j+1} b_{j+1}$}
\item[] \emph{\texttt{Input:} $\s t \in \s R(a_1,\ldots,a_m)$}
\item[] \emph{\texttt{Set:} $\s s \leftarrow \s t$}
\item[] \emph{\texttt{While:} $\s s$ contains a coordinate $s_j \geq b_j$}
\begin{itemize}
\item[] \emph{\texttt{Do:} $s_j \leftarrow s_j-b_j$, $s_{j-1} \leftarrow s_{j-1}+a_{j-1}$}
\end{itemize}
\item[] \emph{\texttt{Output:} $\bm \psi(\s t) \leftarrow \s s$}
\end{itemize}
\end{alg}
It is clear that the algorithm starts with an element of $P = \s R(a_1,\ldots,a_m)$ and, if the while loop terminates, outputs an element of $Q = \s R(b_1,\ldots,b_m)$. It is not obvious, however, that the loop terminates in every case, or that the output $\bm \psi(\s t)$ and the number of steps $\s L_\varphi(\s t)$ depend only on $\s t$, not on the choices made in the while loop.
\begin{thm} \label{main1}
Algorithm~\ref{main7} has the following properties.
\begin{enumerate}
\item \label{main1a} The algorithm stops after a finite number of steps, and the resulting vector $\bm \psi(\s t)$ and the number of steps $\s L_\varphi(\s t)$ are independent of the choices made during the execution of the algorithm.
\item \label{main1b} The algorithm defines a bijection $\bm \psi \colon P \to Q$ which satisfies $\bm \psi(\s t) - \s t \in \p H$, where $\p H$ is the hyperplane defined by $i_1x_1+\ldots+i_mx_m=0$.
\item \label{main1d} We have
$$\s L_\varphi(\s t + \s t') \geq \s L_\varphi(\s t) + \s L_\varphi(\s t') \mbox{ for every } \s t,\s t',\s t+\s t' \in P.$$
In particular, $\s L_\varphi(\s t') \leq \s L_\varphi(\s t)$ if $\s t' \leq \s t$.
\item \label{main1c} Let $\s t, \s t' \in P$, $\s s = \bm \psi(\s t)$, with $t_j \leq t_j' < t_j + \varepsilon_j$, where $\varepsilon_j = b_j - s_j$. Then
$$\bm \psi(\s t')-\s t'=\bm \psi(\s t)-\s t \quad \mbox{and} \quad \s L_\varphi(\s t')=\s L_\varphi(\s t).$$
\item \label{main1e} For all $\s a, \s b \in \Z_+^m$, we have
$$\max_{\s t \in P} \s L_\varphi(\s t) \, = \, \lcm(c_1,\ldots,c_m) \cdot \left( \frac 1 {c_1} + \ldots + \frac 1 {c_m} \right) - m,$$
where $c_j = a_{1}\cdots a_{{j-1}}b_{j}\cdots b_{{m-1}}$.
\end{enumerate}
\end{thm}
We call boxes $P = \s R(a_1,\ldots,a_m)$, $Q=\s R(b_1,\ldots,b_m)$ \emph{relatively rational} if there exists $\lambda$, $\lambda \neq 0$, such that $\lambda a_j \in \Z, \lambda b_j \in \Z$. Clearly, two boxes $P$ and $Q$ with rational side-lengths are relatively rational.
\begin{cor}
Boxes $P=\s R(a_1,\ldots,a_m)$, $Q=\s R(b_1,\ldots,b_m)$ with equal volume are approximately $\Pi$-congruent. Moreover, when $P$ and $Q$ are relatively rational and have equal volume, they are $\Pi$-congruent.
\end{cor}
%\begin{proof}
For $j=1,\ldots,m$, take $i_j = a_1\cdots a_{j-1}b_{j+1}\cdots b_m$. Clearly $i_j a_j = i_{j+1} b_{j+1}$ for $j=1,\ldots,m-1$, and $a_1\cdots a_m = b_1\cdots b_m$ implies $i_m a_m = i_1 b_1$. Therefore, the numbers $i_j,a_j,b_j$ satisfy the conditions of Algorithm~\ref{main7}. By Theorem~\ref{main1} part~\eqref{main1b}, the algorithm defines a bijection $\bm \psi \colon P \to Q$. Parts~\eqref{main1c} and~\eqref{main1b} of Theorem~\ref{main1} imply that we can cut $P$ into (countably many) smaller boxes, each of which is translated by a vector in the plane $i_1x_1+\ldots+i_mx_m=0$.
\smallskip
If $P$ and $Q$ are relatively rational, we can assume without loss of generality that all $a_j,b_j$ are integers. For any integer vector $\s t$, we have $\bm \psi(\s t')-\s t' = \bm \psi(\s t)-\s t$ and $\s L_\varphi(\s t')=\s L_\varphi(\s t)$ whenever $t_j \leq t_j' < t_j + 1$, so $P$ and $Q$ are divided into a finite number (at most $a_1\cdots a_m$) of boxes.
%\end{proof}
%\begin{exm}
Even in the $3$-dimensional case the $\Pi$-congruence defined by the algorithm can be quite complex,
as the next figure suggests. Here the same shading is used for parallel translations by the same vector.
\qed
\begin{figure}[ht]
\begin{center}
% \includegraphics[width=0.55\textwidth]{ohara3}
%\epsfig{file=ohara3.eps,height=7cm}
\end{center}
\caption{The decomposition of the box $\s R(31,47,23)$ given by O'Hara's algorithm (only the top, right, and back sides are shown) .}
\label{fig3}
\end{figure} %\end{exm}}
\bigskip
\subsection{Complexity of O'Hara's algorithm}
The complexity of O'Hara's algorithm has been an open problem, with the exception of the elementary distinct/odd case (see~\cite{O1}).
\medskip
It turns out that the complexity depends heavily on the type of the graph $G_\varphi$ defined in Subsection~\ref{graphs}. Part~\eqref{main1e} of Theorem~\ref{main1} gives the maximum number of steps that O'Hara's algorithm takes when $G_\varphi$ is a cycle. The following lemma gives an estimate for $\p L_\varphi(n)$ when $G_\varphi$ is a path.
\begin{lem} \label{main2}
Let $G_\varphi$ be a finite or infinite path on $\p I \subseteq \PP$. Then $\p L_\varphi(n) \leq n (\log n + 1)$. Moreover, if
$$D = \sum_{i \in \p I} \frac 1 {i a_i} = \sum_{j \in \p I} \frac 1 {j b_j} < \infty,$$
then $\p L_\varphi(n) \leq D n$. Here, by $\log n$ we mean the natural logarithm of $n$.
\end{lem}
\begin{thm} \label{main3}
Let $\overline a,\overline b$ be $\varphi$-equivalent sequences.
\begin{enumerate}
\item \label{main3a} If $G_\varphi$ has only a finite number of cycles of length $> 2$, then $\p L_\varphi(n) = O(n \log n)$, and the constants implied by the $O$-notation are universal.
\item \label{main3b} If $G_\varphi$ has only a finite number of cycles of length $> m$ for some $m > 2$, then $\p L_\varphi(n) = O(n^{m-1})$, and the constants implied by the $O$-notation depend only on $m$.
\end{enumerate}
\end{thm}
The following theorem gives the corresponding lower bound on the worst case complexity. It shows that the estimates of Theorem~\ref{main3} are close to being sharp.
\begin{thm} \label{main4}
There exist $\varphi$-equivalent sequences $\overline a$ and $\overline b$, such that:
\begin{enumerate}
\item \label{main4a} $G_\varphi$ is a path and $\p L_\varphi(n) = \Omega(n \log \log n)$;
\item \label{main4b} $G_\varphi$ contains only cycles of length $\leq m$ and $\p L_\varphi(n) = \Omega(n^{m-1-\varepsilon})$ for every $\varepsilon>0$;
\item \label{main4c} $\p L_\varphi(n) = \exp \Omega(\sqrt[3]{n})$.
\end{enumerate}
\end{thm}
In other words, depending on the type of the graph, we have nearly matching upper and
lower bounds on $\p L_\varphi(n)$. For example, for an $m$-cycle, Theorem~\ref{main3}
shows that $\p L_\varphi(n)$ is $O(n^{m-1})$, while Theorem~\ref{main4} shows that it
is $\Omega(n^{m-1-\varepsilon})$ for every $\varepsilon>0$. Similarly, part~\eqref{main4c}
shows that O'Hara's algorithm can be very slow in general since the total number of
partitions of~$n$ is asymptotically $\exp \Theta(\sqrt n)$.
%%\begin{exm} \label{proofscxity1}
% In the distinct/odd case, the graph $G_\varphi$ is composed of infinite paths
% $$\ldots \to 8 j \to 4 j \to 2j \to j \quad \mbox{for each odd } j.$$
% A partition $\lambda \vdash n$ can be broken up into partitions $\lambda^{(j)} \vdash n_j$ such that the support of $\lambda^{(j)}$ is contained in $\set{(2j-1)2^k \colon k \in \N}$. We have
% $$\sum_{k=0}^\infty \frac 1 {2^{k+1} (2j-1)} = \frac 1 {2j-1},$$
% and Lemma~\ref{main2} implies that O'Hara's algorithm takes at most $n_j/(2j-1)$ steps to compute $\psi(\lambda^{(j)})$. This implies that
% $$L_\varphi(\lambda) \, \leq \, \sum_{j=1}^\infty \frac{n_j}{2j-1} \, \leq \, \sum_{j=1}^n n_j \, = \, n.$$
% In other words, O'Hara's algorithm takes at most $n$ steps to compute $\psi(\lambda)$. This bound is (almost) sharp since the algorithm takes $2^k-1$ steps to compute $\psi(2^k)=1^{2^k}$.
%\qed %\end{exm}}
\bigskip \subsection{O'Hara's algorithm as an integer linear programming problem} \label{linprog}
Let us now give a new description of O'Hara's algorithm.
\begin{prop} \label{main6}
Let $\s i, \s a, \s b \in$ be as above such that $i_j a_j = i_{j+1} b_{j+1}$ for $j=1,\ldots,m$. Fix a vector $\s t \in \s R(a_1,\ldots,a_m)$. Then $\s s = \bm \psi(\s t)$ satisfies the following:
$$\s s = \s t + A \s k,$$
where
$$A = \begin{pmatrix} -b_1 & a_1 & 0 & \cdots & 0 \\ 0 & -b_2 & a_2 & \cdots & 0 \\ 0 & 0 & -b_3 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_m & 0 & 0 & \cdots & -b_m\end{pmatrix}$$
and $\s k=(k_1,\ldots,k_m)$ is the unique vector minimizing
$$k_1+\ldots+k_m$$
with constraints
$$\s k \in \Z^m, \qquad \s k \geq \s 0, \qquad A \s k \geq - \s t, \qquad A \s k \leq \s b - \s 1 - \s t.$$
\end{prop}
Proposition~\ref{main6} can be used to obtain a significant speed-up of (the usual) O'Hara's algorithm, in the case when $G_\varphi$ contains only cycles of bounded length. Namely, we obtain the following result.
\begin{thm} \label{linprog2}
Let $\overline a \sim_\varphi \overline b$. If the lengths of cycles of $G_\varphi$ are bounded, there exists a deterministic algorithm which computes $\psi(\lambda)$ in $O(n \log n)$ steps for $\lambda \in \p A_n$.
\end{thm}
%\begin{proof}
Without loss of generality, the support of $\lambda \in \p A_n$ is contained in one of the connected components of $G_{\varphi}$. If this connected component is a path, O'Hara's algorithm takes $O(n \log n)$ steps by Lemma~\ref{main2}. If it is a cycle of length $m$, we can use the algorithm described in, say, \cite[Corollary 18.7b]{S} to compute $\psi(\lambda)$ in $O(\log^{c}n)$ steps for some $c$. Obviously the $O(n \log n)$ term dominates.
%\end{proof}
\bigskip
\section{Final remarks} \label{final}
\bigskip
\subsection{} \label{final1}
The polynomial time
algorithm in the proof of Theorem~\ref{linprog2} is given implicitly, by using the general results in integer linear programming. It is saying that the function $\psi: \mathcal A_n \to \mathcal B_n$ can be computed much faster, by circumventing the elegant construction of O'Hara's algorithm. It would be interesting to give an explicit construction of such an algorithm.
\medskip
In a different direction, it might prove useful to restate other involution principle bijections in the language of linear programming, such as the Rogers-Ramanujan bijection in~\cite{GM2} or in~\cite{BoP}. If this works, this might lead to a new type of a bijection between these two classes of partitions. Alternatively, this might resolve the conjecture by the second author on the mildly exponential complexity of Garsia-Milne's Rogers-Ramanujan bijection, see \cite[Conjecture 8.5]{P3}.
%\medskip
\subsection{}
Note the gap between the number $\exp \Theta(\sqrt n)$ of partitions of~$n$ and the lower
bound $\p L_\varphi(n) = \exp \Omega(\sqrt[3]{n})$ in Theorem~\ref{main4}.
It would be interesting to decide which of the two worst complexity bounds on the number of steps of O'Hara's algorithm is closer to the truth.
\medskip
Note that we applied our linear programming approach only in the bounded cycle case. We do not know if there is a way to apply the same technique to the general case. However, we believe that there are number theoretic obstacles preventing that and in fact, computing O'Hara's bijection as a function on partitions may be hard in the formal complexity sense.
%\medskip
\subsection{}
Recently, variations on the O'Hara's bijection and applications of rewrite systems were found in~\cite{SSM} and~\cite{K1,K2}. It would be interesting to see connections between our analysis and this work.
%\medskip
\subsection{}
Recall also that the $2$-dimensional case can be viewed as the Euclid algorithm
which in turn corresponds to the usual continued fractions (see Example~\ref{ex-euclid}).
Thus the geometry of~$\mathbf{\psi}$ can be viewed as a delicate multidimensional
extension of continued fractions. Given the wide variety of (different) multidimensional
continued fractions available in the literature, it would be interesting to see
if there is a connection to at least one of these notions.
\vskip 0.5cm
%\noindent
{\bf Acknowledgments.} \ We are grateful to George Andrews and Dennis Stanton
for their interest in the paper and to Kathy O'Hara for sending us a copy of her
thesis~\cite{O1}. The second named author was supported by the NSF. He would
also like to thank Vladimir Arnold, Elena Korkina and Mark Sapir for teaching
him about multidimensional continued fractions.
\begin{thebibliography}{123456}
\bibitem[A98]{A} G.~E. Andrews,
\emph{The theory of partitions} (Second ed.),
Cambridge U. Press, Cambridge, 1998.
\bibitem[BP06]{BoP}
C. Boulet and I. Pak,
A combinatorial proof of the Rogers-Ramanujan identities,
\emph{J. Combin. Theory Ser. A}~\textbf{113} (2006), 1019--1030.
\bibitem[GM81a]{GM1}
A.~M. Garsia and S.~C. Milne,
Method for constructing bijections for classical partition
identities, \emph{Proc. Nat. Acad. Sci. U.S.A.}~\textbf{78} (1981),
no.~4, 2026--2028.
\bibitem[GM81b]{GM2}
A.~M. Garsia and S.~C. Milne,
A {R}ogers-{R}amanujan bijection
\emph{J. Combin. Theory Ser. A}~\textbf{31} (1981),
289--339.
\bibitem[G83]{G}
B. Gordon,
Sieve-equivalence and explicit bijections,
\emph{J. Combin. Theory Ser. A}~\textbf{34} (1983),
90--93.
\bibitem[K04]{K1}
M. Kanovich,
Finding direct partition bijections by two-directional rewriting techniques,
\emph{Discrete Math.}~\textbf{285} (2004), 151--166.
\bibitem[K07]{K2}
M. Kanovich,
The two-way rewriting in action: removing the mystery of Euler-Glaisher's map,
\emph{Discrete Math.}~\textbf{307} (2007), 1909--1935.
\bibitem[KP]{ohara}
M. Konvalinka and I. Pak,
Geometry and complexity of O'Hara's algorithm,
to appear in \emph{Adv. Appl. Math.}
\bibitem[O84]{O1}
K.~M. O'Hara,
\emph{Structure and Complexity of the Involution Principle for Partitions},
Ph.D. thesis, UC Berkeley, California, 1984, 135 pp.
\bibitem[O88]{O2}
K.~M. O'Hara,
Bijections for partition identities,
\emph{J. Combin. Theory Ser. A}~\textbf{49} (1988), 13--25.
\bibitem[P04a]{P1}
I. Pak,
Partition identities and geometric bijections,
\emph{Proc. A.M.S.}~\textbf{132} (2004), 3457--3462.
\bibitem[P04b]{P2}
I. Pak, The nature of partition bijections I. Involutions,
\emph{Adv. Applied Math.}~\textbf{33} (2004), 263--289.
\bibitem[P06]{P3}
I. Pak, Partition bijections, a survey, \emph{Ramanujan J.}~12 (2006),
5--75.
\bibitem[P]{P4} I. Pak,
The nature of partition bijections~II. Asymptotic stability,
preprint, 32 pp., available at {\tt http://www-math.mit.edu/\~{}pak/}
\bibitem[PV05]{PV}
I. Pak and E. Vallejo,
Combinatorics and geometry of Littlewood-Richardson cones,
\emph{Europ. J. Combin.}~\textbf{26} (2005), 995--1008.
\bibitem[R82]{R}
J.~B. Remmel,
Bijective proofs of some classical partition identities.
\emph{J. Combin. Theory Ser. A}, \textbf{33} (1982), 273--286.
\bibitem[S86]{S}
A. Schrijver, \emph{Theory of linear and integer programming}, John Wiley,
Chichester, 1986.
\bibitem[SSM04]{SSM}
J.~A. Sellers, A.~V. Sills and G.~L. Mullen,
Bijections and congruences for generalizations of partition identities of Euler and Guy,
\emph{Electronic J. Combin.}~ \textbf{11} (2004), no.~1, RP~43, 19 pp.
\end{thebibliography}
% The Appendices part is started with the command \appendix;
% appendix sections are then done as normal sections
% \appendix
% \section{}
% \label{}
\begin{thebibliography}{00}
% \bibitem{label}
% Text of bibliographic item
% notes:
% \bibitem{label} \note
% subbibitems:
% \begin{subbibitems}{label}
% \bibitem{label1}
% \bibitem{label2}
% If there is a note, it should come last:
% \bibitem{label3} \note
% \end{subbibitems}
\bibitem{}
\end{thebibliography}
\end{document}