| Proof of a Conjecture of Amitai Regev about Three-Rowed Young Tableaux (and much more!) (2008) | |||||||||||||
Abstract | |||||||||||||
| Consider lattice paths in the three-dimensional cubic lattice, with unit positive steps, that always stay in the region x ≥ y ≥ z. Let Ab1,b2,b3(n) be the number of such walks of length n−(b1 +b2 +b3) that start at [b1, b2, b3]. For example, A0,0,0(n) is the number of 3D-ballot paths (trivially isomorphic to ≤ 3-rowed Standard Young Tableaux with n cells). In 1981 Amitai Regev[R1] (see also [S]) famously proved that A0,0,0(n) is given by the Motzkin numbers: M(n): = �n/2 n! k=0 k!(k+1)!(n−2k)!. A quarter-century later[R2], he conjectured (essentially) the following statement: Regev’s Conjecture: A2,1,0(n) = M(n − 1) − M(n − 3). In this note we prove this conjecture. More generally, we present an algorithm to (automatically!) conjecture and then, immediately, rigorously (and automatically!) prove such statements for any given starting point [b1, b2, b3]. It turns out that for all the starting points we looked at (b3 ≤ b2 ≤ b1 ≤ 20), there are similar expressions as linear combination of negative shifts of the Motzkin sequence M(n) (with constant coefficients). Note that any such statement, in any dimension, once conjectured, is decidable via Wilf-Zeilberger theory and the holonomic ansatz, at least in principle. In practice, however, because of the multisums (or multi-integrals), it becomes unwieldy. We do know, however, that for any such conjecture, there exists a (computable!) number N0 (depending on the conjecture, of course) such that if we verify our conjecture for n ≤ N0, then it is true for ever after. Since we are too lazy to actually find the N0, we are content to verify the conjecture for say, n ≤ 200, and call that verification a semi-rigorous proof. All our proofs for the three-dimensional case are fully rigorous, but the analogous statements for four dimensions are only semi-rigorous. In the four-dimensional case it turns out that for all the starting points we looked at (b4 ≤ b3 ≤ b2 ≤ b1 ≤ 10), there are expressions as linear combination of negative shifts of the sequence A0,0,0,0(n) (with coefficients that are polynomials of degree 1 in n). k-dimensions | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||