| 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 (2008) | |||||||||||||||
Abstract | |||||||||||||||
| made a seemingly amazing conjecture. Let a and b be relatively prime positive integers and let n be a positive integer. There are exactly �n lattice paths from (0, 0) to (nab, nab), with fundamental steps (a, 0) and (0, b), that obey � a+b b 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. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||