Another Proof that Euler Missed: Jonas Sjöstrand’s Amazingly Simple (and Lovely!) Proof of the No-Longer-So-Amazing Loehr-Warrington Lattice Paths Conjecture

Doron ZEILBERGER^{1}

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 \binom{a+b}{b}^{n} lattice paths from (0, 0) to (nab, nab), with fundamental steps (a, 0) and (0, b), that obey the following condition:

Whenever you have made a horizontal step (x, y) → (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 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ützenberger, 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 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 right way. It was the mathematical epsilon (Ph.D. student) Jonas Sjöstrand who gave the coup de grâce to the general conjecture [S] by realizing that the natural habitat of this problem is Graph Theory 101, in fact a variant of its inaugural theorem, Euler’s Königsberg Bridge Theorem.

Imagine a monkey climbing up and down, but always 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 directed graph with multiple edges. It is easy to see that it can never visit higher points than the starting point on the red column. By construction, the monkey has travelled a Eulerian cycle in the graph that he has just made, and hence it is a Eulerian directed graph, with the obvious necessary condition that it is 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önigsberg 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 unique Eulerian cycle that Nick and Greg would approve of. So there is a natural bijection between such legal downwards-greedy monkey iteneraries and such connected Eulerian graphs, for which the origin is the highest visited site on the red column.

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg at math dot rutgers dot edu , http://www.math.rutgers.edu/~zeilberg . Exclusively published in the Personal Journal of Ekhad and Zeilberger http://www.math.rutgers.edu/~zeilberg/pj.html . First version: Oct. 23, 2005. Accompanied by Maple package JONAS downloadable from Zeilberger’s website. Supported in part by the NSF.

That’s very nice, but how do we get \binom{a+b}{a}^{n}? Easy! Once the first monkey formed the Eulerian graph, let another monkey also trace a downwards-greedy cycle but now starting, not at the origin, but at the lowest visited site on the red column. Since this is the lowest point, it will return to it after exactly (a + b) steps, forming a lap i.e. a minimal good cycle of length a + b, the number of which are \binom{a+b}{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östrand 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 JONAS available from my website. In particular try out procedures J12,J21,J23,J32.

Remarks. 1. The proof is all Jonas’s but the analogy to Fleury’s algorithm and the monkey rendition are mine. 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 case-study of completely automatic yet rigorous 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 graphtheoretical formulation. 3. Jonas Sjöstrand’s brilliant trick may be summarized as follows: If you are stumped proving that A ≡ B find a set C such that both A ≡ C and C ≡ B are natural.

References

[EVZ] S.B. Ekhad, V. Vatter and D. Zeilberger, 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, A Human Proof for a Generalization of Shalosh B. Ekhad’s 10^{n} Lattice Paths Theorem, preprint, available from arXiv.org .

[S] J. Sjöstrand, Cylindrical Lattice Paths and The Loehr-Warrington Ten to the Power N Conjecture, preprint, available from arXiv.org .