\documentclass[12pt]{article}
\newcommand{\sign}{{\rm sign}}
\newcommand{\Z}{{\bf Z}}
%\pagestyle{empty}
\begin{document}
\begin{center}
Math 192r, Problem Set \#20 \\
(due 12/11/01)
\end{center}
\medskip
\begin{enumerate}
\item
Let $f(\cdot)$ be some polynomial (in one variable),
and define a sequence of rational functions
$r_n = r_n(x,y)$ with the initial conditions
$r_0 = x$, $r_1 = y$ and the recurrence
$r_{n+2} = f(r_{n+1}) / r_n$ ($n \geq 0$).
Here $x$ and $y$ are formal indeterminates,
so you don't need to worry about ill-definedness
arising from a vanishing denominator.
\begin{itemize}
\item[(a)]
Find an $f$
such that the sequence of polynomials $r_n$
is periodic with period 5.
\item[(b)] Find an $f$ (of degree at least 3, and with at least two terms)
for which each of the rational functions $r_2,r_3,\dots$
is a Laurent polynomial in $x$ and $y$,
such that the one-dimensional recurrence associated with $f$
is a special case of a two-dimensional recurrence
(analogous to frieze patterns or number walls)
that also has the Laurentness property.
(Proofs are not required for this part of the problem.)
\item[(c)]
Find a two-variable polynomial $f(\cdot,\cdot)$
that genuinely involves both of its variables
such that the sequence of rational functions
$r_n$ with the initial conditions
$r_0 = x$, $r_1 = y$, $r_2 = z$ and the recurrence
$r_{n+3} = f(r_{n+1},r_{n+2}) / r_n$
is not periodic,
and such that each $r_n$ is a Laurent polynomial in $x$, $y$ and $z$.
(Proofs are not required for this problem.)
\end{itemize}
\item
Given formal indeterminates $x_{i,j}$ and $y_{i,j}$,
define $f(i,j,k)$ to be $x_{i,j}$ if $k=0$ and $y_{i,j}$ if $k=1$,
and for $k>1$ recursively define
$$
f(i,j,k)=
\scriptstyle
\frac{f(i-1,j-1,k-1)f(i+1,j+1,k-1)+
f(i-1,j+1,k-1)f(i+1,j-1,k-1)}{f(i,j,k-2)}.$$
\noindent
(Note that this is Dodgson condensation
with the minus-sign replaced by a plus-sign.)
\begin{center}
(more)
\end{center}
\begin{itemize}
\item[(a)] Submit code that demonstrates
that $f(i,j,k)$ is a Laurent polynomial in the $x$- and $y$-variables
for $k=2,3,4$,
and that all coefficients in this Laurent polynomial equal $+1$.
(To say that code ``demonstrates'' the truth of a proposition,
I don't mean that it generates output which a human could look over
in order to convince herself/himself that the proposition is true.
I mean that the code evaluates a boolean expression
that encodes the proposition in question,
and the proposition evaluates to {\tt{true}}.)
\item[(b)] Give a conjectural pairing
between the terms of the Laurent polynomial $f(i,j,k)$
and domino tilings of the Aztec diamond of order $k-1$,
and verify it for $k \leq 3$.
\item[(c)] For $k \leq 6$,
count how many terms there are in the Laurent polynomial obtained
from $f(i,j,k)$ by replacing all the $x$-variables by 1.
Repeat, this time instead replacing all the $y$-variables by 1.
\end{itemize}
\end{enumerate}
\end{document}