The Computational Challenge of Enumerating High-Dimensional Rook Walks

By Manuel Kauers and Doron Zeilberger. (See also Zeilberger's version of this website.)

Below are given experimentally discovered recurrence equations for the main diagonal a(n,n,...,n) of the multivariate rational series

(1 - x1/(1-x1) - x2/(1-x2) - ... - xd/(1-xd))-1 = sumn1...nd a(n1,...,nd) x1n1...x1n1.

The challenge consists of computing the corresponding certificates.

The column maxint refers to the length of the longest integer appearing in the recurrence, measured in decimal digits.

 dimension recurrence initial values order degree maxint 2 file (51b) file 2 1 2dd 3 file (205b) file 3 4 6dd 4 file (706b) file 4 9 12dd 5 file (3kb) file 5 18 31dd 6 file (10kb) file 6 31 51dd 7 file (32kb) file 7 50 94dd 8 file (83kb) file 8 75 149dd 9 file (211kb) file 9 108 236dd 10 file (421kb) file 10 149 306dd 11 file (939kb) file 11 200 462dd 12 file (1.7Mb) file 12 261 609dd

Here is the 500000th term of the 12D-diagonal. It has 6.6Mio decimal digits starting with 3281988146201855739941174675728... and ending with ...0771375698627198709248000.

Queens Walks

Here we consider the main diagonal of the power series
(1 - x1/(1-x1) - x2/(1-x2) - ... - xd/(1-xd) - x1...xd/(1-x1...xd))-1.

The asymptotic formula for dimension d is then

sqrt(α)/(nπ)((d - 1)/2)φn
for some constants φ and α which depend on the dimension d.

Guessed recurrence equations and asymptotic constants for dimensions up to 5 are as follows.

Dimension 2

recurrence (order=3, degree=3, maxint: 3 digits) initial values
 parameter minimal poly approximate value φ x^2-12*x+16 10.47 α 256*x^2+400*x-125 0.266907

Dimension 3

recurrence (order=6, degree=15, maxint: 19 digits) initial values
 parameter minimal poly approximate value φ x^3-69*x^2+183*x-125 66.3 α 24300*x^3+87156*x^2+83232*x-15625 0.1598

Dimension 4

recurrence (order=11, degree=49, maxint: 74 digits) initial values
 parameter minimal poly approximate value φ x^4-632*x^3+2392*x^2-3040*x+1296 628.2 α 16483714833083-164482823224832*x -77121798336512*x^2-17203445891072*x^3 -37748736*x^4 0.0958

Dimension 5

recurrence (order=18, degree=133, maxint: 221 digits) initial values
 parameter minimal poly approximate value φ -16807 + 55255*x - 68305*x^2 + 37615*x^3 - 7785*x^4 + x^5 7780.17 α -926912110862037001 + 16156355853887137400*x + 3996548468558029000*x^2 + 289725325976220000*x^3 - 12064954250000*x^4 + 156800000*x^5 0.056

Manuel Kauers
Last modified: Sat Nov 20 19:08:23 CET 2010