
%byrnes.tex: Chomp , Recurrence, and Chaos(?)
%
%
%a Plain TeX file by Doron Zeilberger (13 pages)
 
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\Tilde{\char126\relax}
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
 height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\W{{\cal W}}
\def\V{{\cal V}}
\parindent=0pt
\overfullrule=0in
%end macros
 
\bf
\centerline
{
CHOMP, RECURRENCES, and CHAOS(?)
}
\rm
\bigskip
\centerline{ {\it 
Doron ZEILBERGER
}\footnote{$^1$}
{\eightrm  \raggedright
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
%\break
{\eighttt zeilberg@math.rutgers.edu} \hfill \break
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/   .}
First version: June 3, 2003.  This version: June 9, 2003.
Accompanied by the Maple package {\eighttt BYRNES} available from
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/programs.html} .
Supported in part by the NSF. 
} 
}
 
{\bf \qquad\qquad\qquad\qquad
Dedicated to Saber Elaydi on his 60th Birthday}

{\bf Abstract.} 
In this article, dedicated with admiration and friendship to
Chaos and Difference (and hence Recurrence) Equations
Guru Saber Elaydi,
I give a new approach and a new algorithm for 
Chomp, David Gale's celebrated  combinatorial game.
This work is  inspired by Xinyu Sun's 
``ultimate-periodicity" conjecture and by its brilliant proof by
high-school-student Steven Byrnes.
The algorithm is implemented in a Maple package
{\tt BYRNES} accompanying this article. By looking at the output,
and inspired by previous work of Andries Brouwer, I speculate that
Chomp is Chaotic, in a yet-to-be-made-precise sense, because 
the losing positions are given by ``weird'' recurrences.


{\bf Saber Elaydi}

When Gerry Ladas asked me to write an article dedicated
to Saber Elaydi, I hesitated, since
while we both work on {\it difference equations}, our research
interests (but not our mathematical philosophies!)
are almost diametrically opposite. In particular,
the subject of my current research,
{\it Combinatorial Games}, seemed superficially to be
far removed from Saber's research interests.
On further thought, however, I realized
that this current research of mine is not as far from Saber,
after all, since
{\it recurrences} feature in it prominently.
But {\it recurrence equations} are almost synonymous with
{\it difference equations} (see the next section), and
Saber wrote {\it the} {\bf Book}[E1] on this subject, a modern
classic that I, and my students, thoroughly enjoyed.
As I dwelt even deeper into my research, I also realized that
{\bf chaos}, or something like it, also arises naturally,
and Saber is also a Chaos guru  (cf. [E2]).
So even though the 
{\it primary} ``subject classification" of this article
is ``Combinatorial Games", the {\it secondary} ones are
``Recurrence equations'' and ``Chaos'', so
I hope that Saber will find  this interesting.
Happy 60th Birthday, Saber!

{\bf  Difference vs. Recurrence Equations}

In most contexts, the notions of {\it difference equation} and
of {\it recurrence equation} are identical, and the choice of
which of them to use is merely cultural, the former preferred by
numerical analysts and the latter by combinatorialists and number
theorists.

Indeed a generic form for an $r^{th}$-order difference equation is
$$
P(n, f(n), \Delta f(n), \Delta^2 f(n), \dots, \Delta^r f(n)) \equiv 0 \quad,
$$
while a generic form for an $r^{th}$-order recurrence equation is
$$
Q(n, f(n),Ef(n),E^2f(n), E^rf(n) ) \equiv 0 \quad ,
$$
where, as usual, $\Delta f(n):=f(n+1)-f(n)$ and
$Ef(n):=f(n+1)$. Since $\Delta=E-1$ and $E=\Delta+1$, we can
write, using the binomial theorem ,
$\Delta^kf(n)=(E-1)^kf(n)$ as a linear combination of $E^if(n)$'s and
$E^kf(n)=(\Delta+1)^kf(n)$ as a linear combination of $\Delta^if(n)$'s,
thereby going from one form to the other.


This equivalence is still true if the {\it order} of the difference
(alias recurrence) equation is infinite (i.e. to compute
$f(n)$ we need {\it all} the previous values:
 $f(n-1), f(n-2), \dots, f(1), f(0) $, but
only if the function $P$ is ``algebraic'' or ``analytic'' in some sense.
In this article we will encounter {\it weird recurrences} that
in addition to using {\it all} the previous values, also feature
{\it mex} that inputs sets of integers and outputs non-negative integers. 

{\bf Definition of mex}: Given a set of non-negative integers
$S$, $mex(S)$ is the {\it smallest} non-negative integer
that does not belong to $S$.

For example, $mex(\{0,1,2,5,7\})=3$, and $mex(\{2,3,5,7\})=0$.

{\bf Beware of Sequences Defined by mex}

{\bf Exercise:} Consider the sequence defined by the recurrence
$$
a_i:=mex(\{0,1\} \cup \{ j a_r  \,\, ; \,\, \quad j \geq 1 \,,\, 
\,\, 1 \leq r<i \})
\quad , \quad i \geq 1 \quad .
$$
Prove some obvious properties of this sequence, for example
that there are infinitely many $i$ with $a_{i+1}-a_i=2$.


{\bf How To Play CHOMP}

David Gale's famous game of Chomp ([G]) starts out with an
$M$ by $N$ chocolate bar, in which the leftmost-topmost
square is poisonous. Players take turns picking squares.
In his or her (or its) turn, a player must pick one of the remaining
squares, and eat it along with all the squares that
are ``to its right and below it''. Using matrix-notation
with the poisonous square being entry $(1,1)$, and the
initial position consisting of the whole bar
$\{ (i,j)  \,\, ; \,\, 1 \leq i \leq M, 1 \leq j \leq N \}$,
then picking the square $(i_0,j_0)$ means that one has to eat
all the remaining squares $(i,j)$ for which {\it both} $i \geq i_0$ and
$j \geq j_0$ hold. The player that
eats the poisonous (leftmost-topmost) square loses.
Of course picking $(1,1)$ kills you, so 
a non-suicidal player will not play that move unless it is
forced to. 

For example, if $M=4$ and $N=3$, then the initial game-position is
$$
\matrix{
X&X&X\cr
X&X&X\cr
X&X&X\cr
X&X&X\cr} \quad .
$$
The first player may choose to play $(4,3)$, in which case the
game-position becomes
$$
\matrix{
X&X&X\cr
X&X&X\cr
X&X&X\cr
X&X& \cr} \quad ,
$$
or he may choose to play $(2,2)$, which shrinks the chocolate bar to
$$
\matrix{
X&X&X\cr
X& & \cr
X& & \cr
X& & \cr} \quad ,
$$
and so on.



{\bf What is Chomp Good For?}

Chomp is a {\it typical} example of a {\it combinatorial game}.
The mathematical theory of combinatorial games is
one of the most {\it gorgeous} subjects in the whole of mathematics, see
[BCG] and [F] for nice expositions.
Why study Combinatorial Games? If beauty is not a good enough reason
for you, then there are numerous other reasons, since according to
Steven Byrnes [By], ``Combinatorial game theory has applications in
fields such as complexity theory, artificial intelligence, error-correcting
codes, algorithms, and surreal analysis, and of course, human
recreation (chess, for example)." All true, of course, but
Byrnes forgot to mention an even more  important application, at least
for the Byrnes family. It can pay your Harvard tuition!
([By] won {\it first prize} at the 2002 Siemens Westinghouse Competition,
worth a $\$ 10^5$ scholarship).


{\bf Chomp Positions}

Any Chomp position in a game that starts out with an $M \times N$
chocolate bar, can be described by an array of integers
$(a_1, a_2, \dots, a_M)$, with 
$N \geq a_1 \geq a_2 \geq \dots \geq a_M \geq 0$.
We will find it more convenient to set
$b_i=a_i-a_{i+1}$ for $1 \leq i < M$ and $b_M=a_M$,
and denote the same position with square brackets,
and read it from bottom to top
$[b_M, b_{M-1}, \dots, b_1]$. Note that
this means that there are $b_i$ columns with exactly $i$ squares.
The advantage of this notation is that the $b_i$ are independent
non-negative integers.



{\bf 3-Rowed Chomp}

This was studied in my previous 
article [Z], whose ``meta-motivation" was to give an example
of ``computer-generated research", where the computer first conjectures
a pattern, and then proves it rigorously, {\it all by itself}.
This work was extended, using both human and computer ingenuity
by my student Xinyu Sun[S], first for computing
the so-called {\it Sprague-Grundy function} (a.k.a. 
{\it nim-values }), 
and then for general Chomp, in which all but
the two top-rows are fixed.
Xinyu Sun[S] conjectured that the set of losing positions
(and more generally the set of positions with any given nim-value)
is either a finite set, or displays ``ultimately-periodic" behavior, 
in a sense described below.
This was further confirmed empirically, for the case of $3$-rowed Chomp,
by Andries Brouwer[Br] for the bottom row as large as 90000.
Brouwer also refuted the implicit conjecture in [Z] that for
3-rowed Chomp the period is always one (i.e. that the
sequence is ultimately-constant). Brouwer found that 
when the bottom row has exactly $120$ squares, then the period is $2$,
and found many other examples of larger periods later on.

{\bf Enter Steven Byrnes}

But neither I, nor Xinyu Sun, nor Andries Brouwer, were able to
{\it prove} Sun's ultimate-periodicity conjecture. Steve Byrnes's 
prize-winning article [By] is truly impressive!

In spite of Byrnes's breakthrough, the following is still open.

{\bf BIG PROBLEM}: Give A {\bf fast} (i.e. poly-log in $c+a+b$ ),
characterization of
the set of {\bf losing} Chomp positions $[c,a,b]$.

Here I only consider the following more modest problem,
already studied in [Z].

{\bf LITTLE PROBLEM}: For {\it any} inputted integer $C$
give a {\bf fast} (poly-log in $a+b$)
characterization of
the set of {\it losing} Chomp positions $[c,a,b]$, with $c \leq C$.

In [Z], the {\it little problem} was solved for $C=115$, and the
algorithm could be extended, in principle, for any $C$, as long
as the ultimate-periodicity phenomenon holds. Before Byrnes,
we did not know for sure that it would
always work, but now we do!

So why bother with yet another paper
and yet another Maple package? First, our new Maple package
{\tt BYRNES} accompanying this paper, is much more
efficient than the Maple package {\tt Chomp3Rows} that accompanied
[Z]. Second, {\tt BYRNES} also computes Grundy function tables
automatically. Third, this paper gives an easy {\it algorithmic}
proof of Byrnes's theorem, much easier to follow than Byrnes's
original proof. Finally, and most importantly, it is yet another
example of `taming the infinite' and using computers to
discover and {\it prove} general theorems (i.e. infinitely many facts) by
finitary means.

{\bf Set of Positions and Legal Moves}

A combinatorial game is completely determined by its 
{\it set of legal positions}, $S$, and by a set-valued
function $f:S \rightarrow 2^S$, assigning to any member of $S$ a
(possibly empty) subset of $S$ 
where $f(s)$ is the set of positions reachable from $s$ in
{\it one} move.

For 3-rowed Chomp we have

$$
S:=\{ [c,a,b] \,\,;\,\, a,b,c \geq 0 \} \backslash \{[0,0,0]\} \quad,
$$
and
$$
f([c,a,b]):=\{[c,a,b-x]  \,\, ; \,\, 0< x \leq b \}
$$
$$
\cup \,\, \{[c,a-x,0]  \,\, ; \,\,  0<x \leq a \}
$$
$$
\cup \,\, \{[c-x,0,0]  \,\, ; \,\,  0<x < c \} 
$$
$$
\cup \,\, \{[c,a-x,b+x]  \,\, ; \,\,  0<x \leq a \}
$$
$$
\cup \,\, \{[c-x,0,a+b+x]  \,\, ; \,\,  0<x \leq c \}
$$
$$
\cup \,\, \{[c-x,a+x,b]  \,\, ; \,\,  0<x \leq c \}  \quad .
\eqno(LegalMoves)
$$
The six sets on the right hand side of $(LegalMoves)$
correspond to chomping, respectively, at the \hfill\break
top row, ``columns of 1's section",\hfill\break
top row, ``columns of 2's section",\hfill\break
top row, ``columns of 3's section".\hfill\break
middle row, ``columns of 2's section",\hfill\break
middle row, ``columns of 3's section", and \hfill\break
bottom row, ``columns of 3's section" .

This description is equivalent to the usual description in terms
of a {\it directed graph}. The set of vertices is $S$ and
$f(s)=\{ t | s \rightarrow t \}$.

Yet another description of a game, more useful for our purposes, is
to state the sets $g(t):=\{ s | s \rightarrow t \}$, in other words
for each position $t$, indicate those positions from which $t$ can
be reached in one (legal) move.

In the case of $3$-rowed Chomp we have

if $a,b >0$ then

$$
g([c,a,b])= 
\{ [c,a,b+x]  \,\, ; \,\, x>0 \} 
\,\, \bigcup \,\,
\{ [c,a+x,b-x]  \,\, ; \,\, 0<x\leq b \} 
\,\, \bigcup \,\,
\{ [c+x,a-x,b]  \,\, ; \,\, 0<x\leq a \}  \quad ,
\eqno(Rule1)
$$

while if $a>0$ and $b=0$ then
$$
g([c,a,0])= 
\{ [c,a+x,y]  \,\, ; \,\, x \geq 0, y \geq 0, x+y>0  \} 
\,\, \bigcup \,\,
\{ [c+x,a-x,0]  \,\, ; \,\, 0<x \leq a  \}  \quad ,
\eqno(Rule2)
$$

while if $b>0$ and $a=0$ then
$$
g([c,0,b])= 
\{ [c+x,y,b-x-y]  \,\, ; \,\, x \geq 0, y \geq 0, 0<x+y \leq b  \}  \quad ,
\eqno(Rule3)
$$

and, finally when $a=0$ and $b=0$ then

$$
g([c,0,0])= 
\{ [c+x,y,z]  \,\, ; \,\, x \geq 0, y \geq 0, z \geq 0, 0<x+y+z \}  \quad .
\eqno(Rule4)
$$


We have the following consequences.

{\bf Lemma 1}:

if $a,b >0$ and $[c,a,b]$ is a loser then the
following are {\it guaranteed} winners
$$
\{ [c,a,b+x]  \,\, ; \,\, x>0 \} 
\eqno(1.1)
$$
$$
\{[c,a+x,b-x]  \,\, ; \,\, 0<x\leq b \} 
\eqno(1.2)
$$
$$
\{ [c+x,a-x,b]  \,\, ; \,\, 0<x\leq a \}  \quad .
\eqno(1.3)
$$


{\bf Lemma 2}: If $a>0$ and $[c,a,0]$ is a loser then the
following are {\it guaranteed} winners
$$
\{ [c,a+x,y]  \,\, ; \,\, x \geq 0 \, \, , \, \, y \geq 0
\,\, , \, \, x+y>0  \} \quad .
\eqno(2.1)
$$
$$
\{ [c+x,a-x,0]  \,\, ; \,\, 0<x \leq a  \}  \quad .
\eqno(2.2)
$$


{\bf Lemma 3}: If $b>0$ and $[c,0,b]$ is a loser then the
following are {\it guaranteed} winners
$$
\{ [c+x,y,b-x-y]  \,\, ; \,\, x>0 \,\, , \,\, y>0
\,\, , \,\, 0<x+y \leq b  \}  \quad .
$$

{\bf The `Trivial' Case of 2-Rowed Chomp}

$2$-rowed Chomp is really a piece of cake. Instead of using
a real chocolate bar, we can play this game on the lattice
$N^2$ with $[0,0]$ removed. The Chomp position $[a,b]$ can
be thought of the location of a counter.
There are three kinds of legal moves:
$$
[a,b] \rightarrow [a,b-x] \quad, \quad 1 \leq x \leq b
\eqno(LegalMove1)
$$
$$
[a,b] \rightarrow [a-x,b+x] \quad, \quad 1 \leq x \leq a
\eqno(LegalMove2)
$$
$$
[a,b] \rightarrow [a-x,0] \quad, \quad 1 \leq x < a \quad .
\eqno(LegalMove3)
$$
If a player can't move (i.e. it is at position $[0,1]$), then
it lost. Henceforth we will call positions ``points", and
refer to ``losing positions" and ``winning positions" as
{\it losers} and {\it winners} respectively.

Once we know that $[a,b]$ is a loser, we know right away many
winners, namely all those points from which $[a,b]$ may be reached
in one move, i.e. using any of $(LegalMove1-3)$.
It follows that we have the

{\bf Implied Winners Lemma:} If $[a,b]$ is a loser, 
and $b>0$, then  
$$ [a,b+x] \quad,\quad 1 \leq x  < \infty \quad ,
\eqno(ImW1)
$$
$$
[a+x,b-x] \quad ,\quad  1 \leq x \leq b \quad ,
\eqno(ImW2)
$$
are all winners.
If $[a,0]$ is a loser then
$$
[a+x,y] \quad, \quad 0 \leq x,y < \infty \quad , \quad x+y>0 \quad ,
\eqno(ImW3)
$$
are all winners.



Let's try to find the set of losers in $2$-rowed Chomp.
We already know that $[0,1]$ is a loser, hence
by $(ImW1)$, $[0,x]$, $x>1$ are winners, 
and so is $[1,0]$, by $(ImW2)$.
Crossing out $[0,1]$ and all its implied winners, the minimal
point is $[1,1]$ that must be a loser since it only leads to
previously established winners. Now $[1,1]$'s implied winners
are $[1,x]$, $x>1$, and $[2,0]$, and hence $[2,1]$ is
a loser. By induction, if $[a,1]$ is a loser, then $[a,x]$, $x>1$
and $[a+1,0]$ are winners, and hence the minimal uncovered
point, $[a+1,1]$, is a loser, since it only leads to $[a+1,0]$
$[a+1-x,x+1]$, ($x \geq 1)$, and $[x,0]$ ($x \leq a$), which are
all previously established winners. It follows that
we have the ``theorem" that the set of losing positions in
$2$-rowed Chomp is $ \{ [a,1]  \,\, ; \,\, a \geq 0 \}$.



{\bf 2-Rowed Chomp with Instant Winners}

Now consider a slight generalization. The 
positions and legal moves
are the same, {\bf but}, {\it by fiat}, 
the members of a certain
(finite or infinite) set of points are designated
{\it instant winners}, and if it is your turn to move, and
the counter is on that point, you are declared the winner.

Let's describe this set (of points $[a,b]$)
as a sequence of sets (of integers),
$I_a$ ($0 \leq a < \infty$), where $I_a$ is the set of
$b$ such that $[a,b]$ is an instant winner.
If the set of instant winners is finite then there would be
an $a_0$ such that $I_a=\emptyset$, for $a \geq a_0$, in other words
$I_a$ would be eventually the empty set.

Let's try to figure out how to determine the set of losers,
in this, more general, game.
Because of $(ImW1)$ it follows that for any
given $a$ there is at most one $b$ such that $[a,b]$ is a loser.
Let's denote it by $L_a$, if it exists.
Because of $(ImW3)$, it follows that if $[a_0,0]$ is a loser then
there are no losers with $a>a_0$. In this case there are only
finitely many losers.

The problem of finding the set of losers is equivalent to
determining the sequence 
of integers $\{L_a\}_{a=0}^{\infty}$. 
Fix an integer $a$, and
suppose that we already know 
$L_i$ for $i<a$. This means that
$[i,L_i]$ are losers for $0 \leq i<a$.
Because of $(ImW2)$, 
$$
[a,L_i-(a-i)] \quad , \quad 0 \leq i < a
$$
are implied winners.
Combining these winners-by-merit with the lazy
{\it instant winners}, it follows that $L_a$ is 
the {\it smallest non-negative} integer
that is {\it not} in the set
$$
I_a \cup \{ L_{a-1}-1, L_{a-2}-2, \dots, L_0 -a \} \quad .
$$
In particular if $L_i$ exists for $i<a$ and is never $0$, then
$L_i$ exists. We have just established the

{\bf Fundamental Recurrence for Two-Rowed Chomp with Instant Winners}

Let $\{I_a\}_{a=0}^{\infty}$ be a sequence of sets
of non-negative integers. Consider 2-rowed Chomp
with the set of Instant Winners
$$
\bigcup_{a=0}^{\infty} \{[a,b] \,\, ; \,\, b \in I_a \} \quad.
$$
Then the set of {\it losers} is the set 
$\{[a,L_a] \, \, ; \, \, a \geq 0 \}$, where
$L_a$ is given by the Recurrence
$$
L_a= mex(I_a \cup \{ L_{a-1}-1, L_{a-2}-2, \dots, L_0 -a \}) \quad ,
\eqno(FundamentalRecurrence)
$$
valid as long as $L_a>0$.
If and when $L_{a_0}=0$, then the sequence 
$\{ L_a\}_{a=0}^{\infty}$ terminates at $a=a_0$.

{\bf Example}: Suppose that 
the set of instant winners consists of $[0,0],[0,1],[0,2],[0,3]$,
$[1,0],[1,1],[1,5]$, and $[a,0],[a,1]$
($a>1$). In other words 
$I_0=\{0,1,2,3\}, I_1=\{0,1,5\} \,\, , \,\, I_a=\{0,1\} (a \geq 2)$.

We have:
$$
L_0=mex(I_0)=mex(\{ 0,1,2,3\})=4 \quad,
$$
$$
L_1=mex(I_1 \cup \{L_0-1\} )=mex(\{ 0,1,3,5\})=2 \quad,
$$
$$
L_2=mex(I_2 \cup \{L_1-1, L_0-2 \} )=mex(\{ 0,1,2\})=3 \quad,
$$
$$
L_3=mex(I_3 \cup \{L_2-1, L_1-2, L_0-3 \} )=mex(\{ 0,1,2\})=3 \quad,
$$
$$
L_4=mex(I_4 \cup \{L_3-1, L_2-2, L_1-3, L_0-4 \} )=mex(\{ 0,1,2\})=3 \quad.
$$

Now we can already {\it guess} a pattern, $L_a=3$ for $a \geq 2$.
Let's try and prove it by induction using $(FundamentalRecurrence)$.
We have just established it for $a=2,3,4$. 
For $a \geq 5$ we have, by the inductive hypothesis, that 
the set of non-negative integers in
$$
I_a \cup \{ L_{a-1}-1, L_{a-2}-2, \dots, L_0 -a \}
$$
is really finite, namely 
$$
I_a \cup \{ 3-1, 3-2, 3-3 \}= \{0,1,2\}
$$
and its $mex$ equals $3$. \halmos


{\bf The Ultimate-Periodicity Phenomenon}

Now assume that the sequence of sets $I_a$ describing the
instant winners is not arbitrary, but is
{\it ultimately-periodic}. In other words,
starting at a certain place $a_0$, there is a (minimal) period
$p$ such that $I_a=I_{a+p}$ for $a>a_0$.

Now we are on more secure grounds. Ultimately-Periodic Sequences
are {\it finite} objects, and hence meaningful. To describe such
a sequence all we have to do is specify the non-periodic head
$I_0, \dots, I_{a_0}$ followed by the period 
$I_{a_0+1},I_{a_0+2}, \dots , I_{a_0+p}$ that keeps repeating.

{\bf Two Immediate Consequences of} $(FundamentalRecurrence)$

{\bf Lemma Bounded}: If the sets $I_a$ are (uniformly) bounded,
and $M-1$ is an upper bound, (i.e. $max(I_a) \leq M-1$ for all $a >0$)
then $L_a \leq M$, for all $a>0$.

{\bf Proof}: This follows immediately from the fact that
$mex(S) \leq max(S)+1$, and induction on $a$.

{\bf Ultimate-Periodicity Theorem}: If $I_a$ is ultimately-periodic
then the sequence $L_a$ either terminates (with the last value
being $0$), or else is ultimately-periodic.

{\bf Proof:} Since $I_a$ is ultimately-periodic the set of
finite sets $\{ I_a  \,\, ; \,\, a >0  \}$ is finite, and hence bounded.
Let $M-1$ be the (least) upper bound. By Lemma {\bf Bounded},
$L_a \leq M$. Since negative integers in a set do not 
affect its $mex$ (recall that $mex(S)$ is the smallest
{\it non-negative} integer in the complement of $S$),
the hitherto ``infinite memory'' recurrence
$(FundamentalRecurrence)$, where to know the value of
$L_a$ you have to remember {\it all} your past, now
becomes a ``finite memory'' recurrence, where you only
have to remember what happened in the last $M$ days.
$$
L_a= mex(I_a \cup \{ L_{a-1}-1, L_{a-2}-2, \dots, L_{a-M}-M \}) \quad.
\eqno(BoundedFundamentalRecurrence)
$$

Introducing the `states'
$$
S_a:=(I_a \,\,;\,\,
L_{a-1},L_{a-2}, \dots, L_{a-M} )
$$

$(BoundedFundamentalRecurrence)$ induces a well-defined function
$F:=S_a \rightarrow S_{a+1}$. 
Since $L_a$ is bounded, and $I_a$ is ultimately-periodic,
it follows that there are only finitely many states.
By the venerable {\bf Pigeon-Hole} Principle, sooner or later
we must visit a previously-visited `state', i.e. there exists
an $a_0$ and a $q$ such that $S_{a_0}=S_{a_0+q}$.
But once that happens, everything repeats itself with
period $q$, and
$S_{a_0}=S_{a_0+iq}$ for all $i>0$. In particular,
$L_{a+q}=L_a$ for all $a \geq a_0 +1$. \halmos


{\bf A Posteriori Justification}


How to turn this into an algorithm? The `theoretical' upper bound
for the period is enormous, but is hardly (and perhaps never)
achieved. Once an ultimately-periodic sequence of sets $I_a$ is given
in the form 
$$
[I_0,I_1, \dots, I_{b_0}][I_{b_0+1},I_{b_0+2}, \dots, 
I_{b_0+p}]^{\infty} \quad,
$$
just keep computing $L_a$ using
$(BoundedFundamentalRecurrence)$.
Suppose that your computer detects that, after a certain
place $a_0$, the same segment $L_{a_0+1},L_{a_0+2},\dots, L_{a_0+q}$
keeps repeating (say $10$ times).
Then the computer is justified in {\it guessing} that the
$\{L_a\}_{a=0}^{\infty}$ equals.
$$
[L_0,L_1, \dots, L_{a_0}][L_{a_0+1},L_{a_0+2}, \dots, L_{a_0+q}]^{\infty}
 \quad .
$$
In order to {\it prove} this conjecture you only have
to check it for the {\bf finite} number of cases
$0 \leq a \leq max(a_0,b_0)+M+lcm(p,q)$,  since later on things
start to `repeat themselves'.

{\bf Analogy Example 1}: Guess the decimal representation of
$1/3$, and then prove it rigorously.

{\bf Solution:} 
Compute $1/3$ to ten-decimal-digits accuracy, guess
that $1/3=0.3333333333\dots$, and then prove it
rigorously by summing an infinite geometric series:
$$
3 \sum_{i=1}^{\infty} (1/10)^i = 3 {{1} \over {10-1}}={{1} \over {3}} 
\quad . \halmos
$$

{\bf Analogy Example 2}: Guess the
continued-fraction representation of $\sqrt{7}$,
and then prove it rigorously.

{\bf Solution:} Using Maple, or, if you wish, pencil-and-paper,
compute {\tt convert(evalf(sqrt(7)),confrac);}, getting
{\tt [2,1,1,1,4,1,1,1,4,1,1,1,4,1,1,1,4]}. Now {\it conjecture}
that $\sqrt{7}=[2,(1,1,1,4)^{\infty}]$. Let's call the
right side $x$. Then $x=2+1/y$, where
$y=[(1,1,1,4)^{\infty}]$. This means
$y=1+1/(1+1/(1+1/(4+1/y)))$, from which you can get a quadratic equation
satisfied by $y$, that implies the  quadratic equation satisfied by $x$,
that turns out to be $x^2-7=0$. \halmos

Note that the current algorithm for proving the conjectured
ultimately-periodic sequence $L_a$ from the input
ultimately-periodic sequence of Instant Winners $I_a$ is
perfectly valid even if we did not have the {\it a priori}
assurance that it is 
{\it always} guaranteed to work. The Ultimate-Periodicity
Theorem {\it guarantees} that we are bound to succeed at the end,
even though some of our initial guesses may prove to be wrong.

This is also true in the two elementary `analogy examples' above.
A well-known, elementary, and very easy theorem 
(that uses the pigeon-hole principle!)
asserts
that any rational number has either a terminating
or an ultimately-periodic decimal expansion. This guarantees
that the `empirical algorithm' is going to work for any
{\it rational number}.

Analogously for Example 2. A theorem of
Lagrange 
states that any 
quadratic irrationality has an ultimately-periodic continued fraction,
and the proof also uses recurrences and the pigeon-hole principle.
Hence we have an {\it a priori} guarantee
that this will work for the square-root of {\it any}
(non-perfect-square) integer.

{\bf Back to Three-Rowed Chomp}

Recall our {\bf Little Problem} of determining {\bf fast},
all the losers $[c,a,b]$ for $c \leq C$, where $C$ is a fixed,
given integer.
  
Because of the first part of $(Rule1)$, it follows 
that for any given $c$ and $a$, there is
{\it at most} one $b$ such that $[c,a,b]$ is a losing position.
Let's define $B_c(a)$ to be that $b$ (if it exists, otherwise it is
undefined). 

It follows that knowledge of the set of losers in 3-rowed Chomp
is the same as {\it knowing} the sequence of sequences 
$B_c$, and knowing it for $c \leq C$ is the same as knowing its
first $C+1$ terms.

We already know $B_0$! This is just the
case of 2-rowed Chomp, and we found that $B_0=1^{\infty}$.
Suppose that we already know $B_c$ for $c<C$ and are interested
in $B_C$. Now observe that $B_C$ is just the loser-sequence
for a $2$-rowed Chomp (since the $c$ is fixed at $C$) with
lots of Instant Winners! These Instant Winners
are those positions implied by losers from $c<C$
via $(1.3)$, $(2.2)$ and Lemma {\bf 3}.

So let's define the sequence of those Instant Winners $\W_C(a)$ as the
set of $b$ such that $[C,a,b]$ is a winner implied by some $L_c$ with $c<C$.
$\W_C(a)$ can be naturally partitioned as
$$
\W_C(a) = \bigcup_{c=0}^{C-1} \V_{C,c}(a) \quad , \quad
$$
where
$\V_{C,c}(a)$ is the set of $b$ such that $[C,a,b]$ is reachable
from {\it some} loser $[c,a',b']$.
$\V_{C,c}(a)$, in turn, can be written conveniently as
$$
\V_{C,c}(a) \,\, = \,\, \V'_{C,c}(a) \cup \V''_{C,c}(a) ,
$$
where $\V'_{C,c}(a)$ is the contribution from Lemma $3$, and
$\V''_{C,c}(a)$ is the contribution from $(1.3)$ and $(2.2)$.

From Lemma 3, $(1.3)$, and $(2.2)$, we have,

{\bf Crucial Facts}

for $a \geq 0$:
$$
\V'_{C,c}(a)=\{ B_c(0)-(C-c)-a \} \cap 
{ \bf Z}_{\geq 0} \quad ,
$$
$$
\V''_{C,c}(a)=\{ B_c(a+C-c) \} \quad .
$$

Note that each of these sets is either empty or a singleton.

We are now ready to give a new proof of

{\bf Byrnes's Theorem}: For every $C$, $B_C$ is ultimately-periodic.

{\bf Proof}: By the Ultimate-Periodicity Theorem it suffices to
show that for
each non-negative integer
$C$, the sequence of sets $\{ \W_C(a)\}_{a=0}^{\infty}$
is ultimately-periodic. 

Note that if $\{S(a)\}_{a=0}^{\infty}$ and
$\{T(a)\}_{a=0}^{\infty}$ are ultimately-periodic sequences of sets
so is 
$$
\{ (S \cup T)(a) \}_{a=0}^{\infty}:=
 \{S(a) \cup T(a)\}_{a=0}^{\infty} \quad .
$$

We proceed by induction on $C$. We already know that it is true
for $C=0$.
By induction, the sequence of sets $\{ \V''_{C,c}(a)\}_{a=0}^{\infty}$ is
ultimately-periodic, and $\{\V'_{C,c}(a)\}_{a=0}^{\infty}$ is
even better, it is ultimately empty. Hence their union,
$\{ \V_{C,c}(a)\}_{a=0}^{\infty}$ 
is ultimately-periodic for all $c<C$, and hence
so is their point-wise {\it union} 
over $c<C$, $\{\W_C(a)\}_{a=0}^{\infty}$ \halmos


{\bf Algorithm}

Now that we know that $B_c$ is ultimately-periodic, or finite, 
and hence is uniquely determined by finite data
(the non-periodic beginning, and the periodic part),
we can treat it 
as a {\it single} concrete 
{\it computational} object rather then as an
{\it infinite sequence}.

It turns out that $\W_c$ is not that different than
$\W_{c-1}$, hence it would be desirable to find
a {\it recurrence} scheme that takes advantage of
previously computed values.

Let's write
$$
\W'_C(a):= \bigcup_{c=0}^{C-1} \,\, \V'_{C,c}(a) \quad,
$$
$$
\W''_C(a):= \bigcup_{c=0}^{C-1} \,\, \V''_{C,c}(a) \quad .
$$

Of course, $\W_C(a)=\W'_C(a) \cup \W''_C(a)$.

Now
$$
\W''_C(a):= \bigcup_{c=0}^{C-1} \V''_{C,c}(a)= 
\left ( \bigcup_{c=0}^{C-2} \,\, \V''_{C,c}(a)  \right )
\cup \,\, \V''_{C,C-1}(a)
$$
$$
=
\left ( \bigcup_{c=0}^{C-2}  \{ B_c(a+1+(C-1)-c) \} \right )
\,\, \cup \,\, \{ B_{C-1}(a+1) \}
$$
$$
=\W''_{C-1}(a+1) \cup \{ B_{C-1}(a+1) \} \quad.
$$
We also have
$$
\W'_C(a):= \bigcup_{c=0}^{C-1} \V'_{C,c}(a)= 
\left ( \bigcup_{c=0}^{C-2} \V'_{C,c}(a) \right )
\cup \V'_{C,C-1}(a)=
$$
$$
\bigcup_{c=0}^{C-2} \{ B_c(0)-((C-1)-c)-a-1 \}
\cup \{ B_{C-1}(0)-1-a \}=
$$
$$
OneLess(\W'_{C-1}(a)) \cup \{ B_{C-1}(0)-1-a \} \quad,
$$
where $OneLess(S):=\{s-1 \,\, ; \,\, s \in S\}$.

In the above we make the convention that negative numbers are
discarded.

{\bf The Recurrence Scheme}

Now let's define three {\bf macros} on 
ultimately-periodic sequences of sets.

The first one is {\bf Losers} that inputs an
ultimately-periodic  sequence of sets and outputs
an ultimately-periodic, or finite, sequence of integers,
by employing $(FundamentalRecurrence)$.

The second one is {\bf OneLess} defined by
$OneLess(A)_i \, := \, OneLess(A_i)$. Of course it preserves
the ultimate-periodicity property.

The third macro is {\bf Chop} that is just a left-shift,
discarding the first member.
$Chop(A)_i=A_{i+1}$.

Using these three macros, we can rephrase the above scheme
without any mention of the argument $a$, and just
treat $B_c$, $\W'_c$, and $\W''_c$ as {\it objects} on their
own right. The union of two sequences of sets is
defined as the sequence of unions: 
$(S \cup T)_i:=S_i \cup T_i$.

{\bf Initial Conditions:} $W'_{0}=\{0\}\emptyset^{\infty}$,
$W''_{0}=\emptyset^{\infty}$.


{\bf Recurrence:} For $c \geq 0$
$$
B_c=Losers(\W'_c \cup \W''_c) \quad , 
$$
$$
W'_{c+1}=OneLess(W'_c) \cup 
[\{B_c(0)-1 \}, \{B_c(0)-2 \}, \dots, \{0\}][\emptyset]^{\infty} \quad ,
$$
$$
W''_{c+1}=Chop(W''_c) \cup Chop(B_c) \quad .
$$

{\bf The Maple package BYRNES}

Everything here is implemented in the Maple package {\tt BYRNES}
available from the author's website. 
It may be downloaded from

{\tt http://www.math.rutgers.edu/\Tilde zeilberg/mamarim/
mamarimhtml/byrnes.html} ,

where you can also find a data file called {\tt ChompData}, and
detailed instructions.

The main procedures are {\tt ChompLosers} and {\tt ChompGrudny} .

{\bf The Sprague-Grundy Values}

Losing positions are those for which the Sprague-Grundy 
function (nim-value) equals $0$.
The above can be repeated, with little modification,
to compute the set of positions that have any given
nim-value. The only difference is that for any given $g$,
one has to add to the set of  implied ``Instant Winners'',
the positions that have been already shown to have smaller
nim-values. It follows by induction on $g$ that these too
yield ultimately-periodic sequences. This is implemented
in procedure {\tt ChompGrundy} in {\tt BYRNES}. Read
the on-line help there.

{\bf Chaotic Behavior}

As first noted by Brouwer[Br] for the losing positions,
and Sun[S] for the values of the nim-values, larger periods then
$1$ do occur, and while at the beginning they are rather rare, eventually
they take over, and the periods get rather large. Also the
set of $c$ for which $B_c$ is a finite sequence (i.e. it ends
with a $0$) is rather mysterious. It seems that we have
`chaotic' behavior, but in a vague, yet-to-be-made-precise, sense.

{\bf Conclusion: Chomp is Locally Trivial But NOT Globally Trivial}

What Xinyu Sun conjectured, Byrnes proved, and I reproved is that
3-Rowed Chomp is {\it locally} trivial, since for every fixed
number of squares at the bottom row, $c$, the 
sequence coding the set of losing positions,
$B_c$, is {\it ultimately-periodic} or finite.

But it seems that as a function of $c$, $B_c$ is far from
trivial. But then again, maybe it conforms to yet-another-ansatz,
perhaps reminiscent of Wythoff's game (see [F]), but probably
much more complicated.

{\bf REFERENCES}

[BCG] E. R. Berlekamp, J. H. Conway, and R. K. Guy,
{\it ``Winning Ways for Your Mathematical Plays''},
Academic Press, London, 1982.

[Br] A. Brouwer, {\it Chomp}, on-line document,
{\tt http://www.win.tue.nl/\Tilde aeb/games/chomp.html} .

[By] S. Byrnes, {\it Poset Games Periodicity}, preprint.\hfill\break
Available from:
{\tt http://www.geocities.com/sbyrnes321/pgp.html }.

[E1] S. Elaydi, {\it ``An Introduction to Difference Equations''},
2nd edition, Springer Verlag,  1999.

[E2] S. Elaydi, {\it ``Discrete Chaos''}, CRC Press, 1999.

[F] A. S. Fraenkel,  {\it Scenic Trails Ascending from Sea-Level
Nim to Alpine Chess}, in: ``{\it Games of No Chance}'', R. J. Nowakowski,
ed., Cambridge University Press, 1996.

[G] D. Gale, {\it A Curious Nim-type game}, Amer. Math. Monthly
{\bf 81} (1974), 876-879.

[S] X.Sun, {\it Improvements on Chomp},
   Integers {\bf 2} (2002), G1, 8 pp. (electronic).

[Z] D. Zeilberger,   {\it Three-rowed Chomp},
   Adv. in Appl. Math.{\bf 26} (2001), 168--179.
Available on-line from:
{\tt http://www.math.rutgers.edu/\Tilde zeilberg/mamarim/
mamarimhtml/chomp.html} .


\bye






















