%jonas.tex: a Plain TeX file by Doron Zeilberger (2 pages)
%begin macros
\def\L{{\cal L}}
\def\Tilde{\char126\relax}
\baselineskip=14pt
\parskip=10pt
\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\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm \ifodd\pageno \RightHead \else \LeftHead \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{
Another Proof that Euler Missed: Jonas Sj\"ostrand's Amazingly Simple (and Lovely!) Proof}
\centerline{
of the No-Longer-So-Amazing Loehr-Warrington Lattice Paths Conjecture
}
\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 at math dot rutgers dot edu} ,
\hfill \break
{\eighttt http://www.math.rutgers.edu/\~{}zeilberg} .
Exclusively published in the Personal Journal of
Ekhad and Zeilberger
{\eighttt http://www.math.rutgers.edu/\~{}zeilberg/pj.html} .
First version: Oct. 23, 2005.
Accompanied by Maple package {\eighttt JONAS}
downloadable from Zeilberger's website.
Supported in part by the NSF.
}
}
A few months ago Nick Loehr and Greg Warrington made a seemingly
amazing conjecture.
Let $a$ and $b$ be relatively prime positive integers and let
$n$ be a positive integer.
There are exactly ${{a+b} \choose {b}}^n$
lattice paths from $(0,0)$ to $(nab,nab)$,
with fundamental steps $(a,0)$ and $(0,b)$,
that obey the following condition:
{\it Whenever you have made a horizontal step
$(x,y)\rightarrow (x+a,y)$ you are committed, for ever after, to always choose
the horizontal-step option should you visit a site of the form $(x+jab,y+jab)$
for some $j>0$.}
Being a wordy kind of guy, I immediately translated this to a problem on
{\it words}, in the alphabet $\{a,-b\}$, avoiding factors of the
form $a[-a](-b)$ where $[-a]$ denotes a word that sums to $-a$.
This brings to mind Goulden-Jackson, alas, with infinitely many `mistakes'.
Even though the language is no longer regular, its conjectured rational
generating function suggested that it has a linear grammar, and being
a disciple of Marco Sch\"utzenberger, I tried to look for a linear grammar.
Helped by my brilliant human disciple Vince Vatter, and my electronic
disciple Shalosh B. Ekhad, we found such a grammar for the case
$a=3$ and $b=2$. The same method should, in principle, yield a proof
for every {\it specific} $a$ and $b$, but Shalosh's memory only sufficed
for this case. This was written up in [EVZ].
A human, lattice-path, proof of the more general $b=2$ case appeared
shortly after [LSW].
But neither the linguistic approach of the former
nor the lattice-path approach of the latter were the
{\it right} way.
It was the mathematical epsilon (Ph.D. student) Jonas Sj\"ostrand
who gave the {\it coup de gr\^ace} to the {\it general} conjecture [S]
by realizing that the {\it natural habitat} of this problem
is {\bf Graph Theory 101}, in fact a variant of its
inaugural theorem, Euler's K\"onigsberg Bridge Theorem.
Imagine a monkey climbing up and down, but always {\it counter-clockwise},
cylindrical monkey-bars of perimeter $(a+b)$ with one of the vertical
columns painted red and designated the $0$-column. At any point,
the monkey can go either $a$ units up or $b$ units down to
its immediate counter-clockwise-neighboring column.
It starts and ends at the same spot (let's call it the origin).
The awkward Loehr-Warrington condition now translates
to the natural condition that whenever it leaves a point in the upwards
direction, all subsequent exits from that point (if they exist) must
be upwards as well.
If the monkey travels with a string, and tapes it to each visited
site (and draws arrows in the appropriate directions),
he would naturally trace a {\it directed graph} with
multiple edges.
It is easy to see that it can never visit higher points than
the starting point on the {\bf red column}.
By construction, the monkey has travelled a Eulerian
cycle in the graph that he has just made, and hence
it is a {\bf Eulerian directed graph}, with the obvious
necessary condition that it is {\bf balanced}: each vertex
has as many incoming edges as outgoing edges.
This brings to mind the `easy part' of
(the directed version of) Euler's Seven Bridges of
K\"onigsberg Theorem. But the `hard' part (which is
almost as easy) that if a directed graph is balanced, then it has
a Eulerian cycle, goes almost verbatim.
Recall that Fleury's algorithm finds a Eulerian cycle by
avoiding bridges if it can. If you replace
`don't go over a bridge unless you have no other choice' by
`don't go up unless you have no other choice' you would
get the {\bf unique} Eulerian cycle that Nick and Greg would approve of.
So there is a natural bijection between
such legal {\bf downwards-greedy} monkey iteneraries
and such connected Eulerian graphs, for which the origin is the highest
visited site on the red column.
That's very nice, but how do we get ${{a+b} \choose {a}}^n$?
Easy! Once the first monkey formed the Eulerian graph, let another
monkey also trace a {\it downwards-greedy} cycle but now starting,
not at the origin, but at the
{\bf lowest} visited site on the {\bf red column}.
Since this is the lowest point, it will return to it
after exactly $(a+b)$ steps, forming a {\bf lap} i.e. a minimal
good cycle of length $a+b$, the number of which are
${{a+b} \choose {a}}$.
Removing the edges of this lap will not ruin Eulerianity and the other condition,
and we get a legal such graph with $(n-1)(a+b)$ edges, and we
can continue recursively. It is also clear how to go back.
Given such a Sj\"ostrand Eulerian graph, and a lap-cycle,
find the lowest point in the red column such that if we
insert that lap there it will be connected to our graph.
If you don't believe Jonas, check out my Maple package {\tt JONAS} available
from my website. In particular try out procedures {\tt J12,J21,J23,J32}.
{\bf Remarks.} {\bf 1.} The proof is all Jonas's but the analogy to
Fleury's algorithm and the monkey rendition are mine.
{\bf 2.} Jonas's proof only slightly detracts from
the interest of the Ekhad-Vatter-Zeilberger original special case,
since, first and foremost, it is a {\bf case-study} of completely
automatic yet rigorous {\bf experimental mathematics}, but
also because the method can be applied to discover and prove
linear grammars for many other languages for which we are not
so lucky to have a graph-theoretical formulation.
{\bf 3.} Jonas Sj\"ostrand's brilliant trick may be summarized as follows:
\hfill\break
{\it If you are stumped proving that $A \equiv B$ find a set $C$
such that both $A \equiv C$ and $C \equiv B$ are natural}.
{\bf References}
[EVZ] S.B. Ekhad, V. Vatter and D. Zeilberger,
{\it A Proof of the Loehr-Warrington Amazing TEN to the power n Conjecture},
preprint, available from the authors' websites.
[LSW] N. Loehr, B. Sagan, and G. Warrington,
{\it A Human Proof for a Generalization of Shalosh B. Ekhad's $10^n$ Lattice Paths Theorem},
preprint, available from arXiv.org .
[S] J. Sj\"ostrand, {\it Cylindrical Lattice Paths and The Loehr-Warrington
Ten to the Power N Conjecture}, preprint, available from arXiv.org .
\end