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 212dd
3 file (205b) file 346dd
4 file (706b) file 4912dd
5 file (3kb) file 51831dd
6 file (10kb) file 63151dd
7 file (32kb) file 75094dd
8 file (83kb) file 875149dd
9 file (211kb) file 9108236dd
10 file (421kb) file 10149306dd
11 file (939kb) file 11200462dd
12 file (1.7Mb) file 12261609dd

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
parameterminimal polyapproximate value

Dimension 3

recurrence (order=6, degree=15, maxint: 19 digits) initial values
parameterminimal polyapproximate value
φx^3-69*x^2+183*x-125 66.3

Dimension 4

recurrence (order=11, degree=49, maxint: 74 digits) initial values
parameterminimal polyapproximate 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^40.0958

Dimension 5

recurrence (order=18, degree=133, maxint: 221 digits) initial values
parameterminimal polyapproximate value
φ-16807 + 55255*x - 68305*x^2 + 37615*x^3 - 7785*x^4 + x^57780.17
α-926912110862037001 + 16156355853887137400*x + 3996548468558029000*x^2 + 289725325976220000*x^3 - 12064954250000*x^4 + 156800000*x^50.056

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