ńņš. 9 |

the following tools11 :

1. Superseeker, the electronic version of the āEncyclopedia of Integer Sequencesā

[162, 161] by Neil Sloane and Simon Plouļ¬e (see Footnote 2 in the Introduction),

11

In addition, one has to mention Frank Garvanā™s qseries [54], which is designed for guessing and

computing within the territory of q-series, q-products, eta and theta functions, and the like. Procedures

like prodmake or qfactor, however, might also be helpful for the evaluation of āq-determinantsā. The

package is available from http://www.math.ufl.edu/˜frank/qmaple.html.

52 C. KRATTENTHALER

2. gfun by Bruno Salvy and Paul Zimmermann and Mgfun by Frederic Chyzak (see

Footnote 3 in the Introduction),

3. Rate by the author (see Footnote 4 in the Introduction).

If you send the ļ¬rst few elements of your sequence to Superseeker then, if it overlaps

with a sequence that is stored there, you will receive information about your sequence

such as where your sequence already appeared in the literature, a formula, generating

function, or a recurrence for your sequence.

The Maple package gfun provides tools for ļ¬nding a generating function and/or a

recurrence for your sequence. (In fact, Superseeker does also automatically invoke

features from gfun.) Mgfun does the same in a multidimensional setting.

Within the āhypergeometric paradigm,ā the most useful is the Mathematica pro-

gram Rate (āRate!ā is German for āGuess!ā), respectively its Maple equivalent GUESS.

Roughly speaking, it allows to automatically guess āclosed formsā.12 The program

is based on the observation that any āclosed formā sequence (an )nā„0 that appears

within the āhypergeometric paradigmā is either given by a rational expression, like

an = n/(n + 1), or the sequence of successive quotients (an+1 /an )nā„0 is given by a ratio-

nal expression, like in the case of central binomial coeļ¬cients an = 2n , or the sequence

n

of successive quotients of successive quotients ((an+2 /an+1 )/(an+1 /an ))nā„0 is given by

a rational expression, like in the case of the famous sequence of numbers of alternating

sign matrices (cf. the paragraphs following (3.9), and [18, 19, 111, 148, 97, 198, 199]

for information on alternating sign matrices),

nā’1

(3i + 1)!

an = , (A.1)

(n + i)!

i=0

etc. Given enough special values, a rational expression is easily found by rational

interpolation.

This is implemented in Rate. Given the ļ¬rst m terms of a sequence, it takes the

ļ¬rst m ā’ 1 terms and applies rational interpolation to these, then it applies rational

interpolation to the successive quotients of these m ā’ 1 terms, etc. For each of the

obtained results it is tested if it does also give the m-th term correctly. If it does, then

the corresponding result is added to the output, if it does not, then nothing is added

to the output.

Here is a short demonstration of the Mathematica program Rate. The output shows

guesses for the i0-th element of the sequence.

In[1]:= rate.m

In[2]:= Rate[1,2,3]

Out[2]= {i0}

In[3]:= Rate[2/3,3/4,4/5,5/6]

12

Commonly, by āclosed formā (āNICEā in Zeilbergerā™s āterminologyā) one means an expression

which is built by forming products and quotients of factorials. A strong indication that you encounter

a sequence (an )nā„0 for which a āclosed formā exists is that the prime factors in the prime factorization

of an do not grow rapidly as n becomes larger. (In fact, they should grow linearly.)

ADVANCED DETERMINANT CALCULUS 53

1 + i0

Out[3]= {------}

2 + i0

Now we try the central binomial coeļ¬cients:

In[4]:= Rate[1,2,6,20,70]

-1 + i0

2 (-1 + 2 i1)

Out[4]= { -------------}

i1

i1=1

It needs the ļ¬rst 8 values to guess the formula (A.1) for the numbers of alternating sign

matrices:

In[5]:= Rate[1,2,7,42,429,7436,218348,10850216]

-1 + i0 -1 + i1

3 (2 + 3 i2) (4 + 3 i2)

Out[5]= { 2( -----------------------)}

4 (1 + 2 i2) (3 + 2 i2)

i1=1 i2=1

However, what if we encounter a sequence where all these nice automatic tools fail?

Here are a few hints. First of all, it is not uncommon to encounter a sequence (an )nā„0

which has actually a split deļ¬nition. For example, it may be the case that the subse-

quence (a2n )nā„0 of even-numbered terms follows a āniceā formula, and that the subse-

quence (a2n+1)nā„0 of odd-numbered terms follows as well a ānice,ā but diļ¬erent, formula.

Then Rate will fail on any number of ļ¬rst terms of (an )nā„0 , while it will give you some-

thing for suļ¬ciently many ļ¬rst terms of (a2n)nā„0 , and it will give you something else

for suļ¬ciently many ļ¬rst terms of (a2n+1 )nā„0 .

Most of the subsequent hints apply to a situation where you encounter a sequence

p0 (x), p1(x), p2 (x), . . . of polynomials pn (x) in x for which you want to ļ¬nd (i.e., guess)

a formula. This is indeed the situation in which you are generally during the guessing

for āidentiļ¬cation of factors,ā and also usually when you perform a guessing where a

parameter is involved.

To make things concrete, let us suppose that the ļ¬rst 10 elements of your sequence

of polynomials are

54 C. KRATTENTHALER

1 1

6 + 31x ā’ 15x2 + 20x3 , 12 ā’ 58x + 217x2 ā’ 98x3 + 35x4 ,

1, 1 + 2x, 1 + x + 3x2 ,

6 12

1 1

20+508xā’925x2 +820x3 ā’245x4 +42x5 , 120ā’8042x+20581x2 ā’17380x3 +7645x4 ā’1518x5 +154x6 ,

20 120

1

1680 + 386012x ā’ 958048x2 + 943761x3 ā’ 455455x4 + 123123x5 ā’ 17017x6 + 1144x7 ,

1680

1

20160ā’15076944x+40499716x2 ā’42247940x3 +23174515x4 ā’7234136x5 +1335334x6 ā’134420x7 +6435x8 ,

20160

1

181440 + 462101904x ā’ 1283316876x2 + 1433031524x3 ā’ 853620201x4 + 303063726x5

181440

ā’ 66245634x6 + 8905416x7 ā’ 678249x8 + 24310x9 , . . . (A.2)

You may of course try to guess the coeļ¬cients of powers of x in these polynomials.

But within the āhypergeometric paradigmā this does usually not work. In particular,

that does not work with the above sequence of polynomials.

A ļ¬rst very useful idea is to guess through interpolation. (For example, this is what

helped to guess coeļ¬cients in [43].) What this means is that, for each pn (x) you try to

ļ¬nd enough values of x for which pn (x) appears to be āniceā (the prime factorization

of pn (x) has small prime factors, see Footnote 12). Then you guess these special eval-

uations of pn (x) (by, possibly, using Rate or GUESS), and, by interpolation, are able to

write down a guess for pn (x) itself.

Let us see how this works for our sequence (A.2). A few experiments will convince

you that pn (x), 0 ā¤ n ā¤ 9 (this is all we have), appears to be āniceā for x = 0, 1, . . . , n.

Furthermore, using Rate or GUESS, you will quickly ļ¬nd that, apparently, pn (e) = 2n+e e

for e = 0, 1, . . . , n. Therefore, as it also appears to be the case that pn (x) is of degree

n, our sequence of polynomials should be given (using Lagrange interpolation) by

n

2n + e x(x ā’ 1) Ā· Ā· Ā· (x ā’ e + 1)(x ā’ e ā’ 1) Ā· Ā· Ā· (x ā’ n)

pn (x) = . (A.3)

e(e ā’ 1) Ā· Ā· Ā· 1 Ā· (ā’1) Ā· Ā· Ā· (e ā’ n)

e

e=0

Another useful idea is to try to expand your polynomials with respect to a āsuitableā

basis. (For example, this is what helped to guess coeļ¬cients in [30] or [94, e.g., (3.15),

(3.33)].) Now, of course, you do not know beforehand what āsuitableā could be in your

situation. Within the āhypergeometric paradigmā candidates for a suitable basis are

always more or less sophisticated shifted factorials. So, let us suppose that we know

that we were working within the āhypergeometric paradigmā when we came across

the example (A.2). Then the simplest possible bases are (x)k , k = 0, 1, . . . , or (ā’x)k ,

k = 0, 1, . . . . It is just a matter of taste, which of these to try ļ¬rst. Let us try the

latter. Here are the expansions of p3 (x) and p4 (x) in terms of this basis (actually, in

terms of the equivalent basis x , k = 0, 1, . . . ):

k

6 + 31x ā’ 15x2 + 20x3 = 1 + 6 x x x

1

+ 15 + 20 ,

6 1 2 3

12 ā’ 58x + 217x2 ā’ 98x3 + 35x4 = 1 + 8 x x x x

1

+ 28 + 56 + 70 .

12 1 2 3 4

I do not know how you feel. For me this is enough to guess that, apparently,

n

2n x

pn (x) = .

k k

k=0

ADVANCED DETERMINANT CALCULUS 55

(Although this is not the same expression as in (A.3), it is identical by means of a

3 F2 -transformation due to Thomae, see [55, (3.1.1)]).

As was said before, we do not know beforehand what a āsuitableā basis is. Therefore

you are advised to get as much a priori information about your polynomials as possible.

For example, in [28] it was āknownā to the authors that the result which they wanted

to guess (before being able to think about a proof) is of the form (NICE PRODUCT) Ć—

(IRREDUCIBLE POLYNOMIAL). (I.e., experiments indicated that.) Moreover, they

knew that their (IRREDUCIBLE POLYNOMIAL), a polynomial in m, pn (m) say,

would have the property pn (ā’m ā’ 2n + 1) = pn (m). Now, if we are asking ourselves

what a āsuitableā basis could be that has this property as well, and which is built

in the way of shifted factorials, then the most obvious candidate is (m + n ā’ k)2k =

(m + n ā’ k)(m + n ā’ k + 1) Ā· Ā· Ā· (m + n + k ā’ 1), k = 0, 1, . . . . Indeed, it was very easy

to guess the expansion coeļ¬cients with respect to this basis. (See Theorems 1 and 2

in [28]. The polynomials that I was talking about are represented by the expression in

big parentheses in [28, (1.2)].)

If the above ideas do not help, then I have nothing else to oļ¬er than to try some,

more or less arbitrary, manipulations. To illustrate what I could possibly mean, let us

again consider an example. In the course of working on [90], I had to guess the result

of a determinant evaluation (which became Theorem 8 in [90]; it is reproduced here

as Theorem 43). Again, the diļ¬cult part of guessing was to guess the āuglyā part of

the result. As the dimension of the determinant varied, this gave a certain sequence

pn (x, y) of polynomials in two variables, x and y, of which I display p4 (x, y):

In[1]:= VPol[4]

2 3 4 2 3 2

Out[1]= 6 x + 11 x +6x + x + 6 y - 10 x y - 6 x y - 4 x y + 11 y -

2 2 2 3 3 4

> 6xy +6x y +6y -4xy +y

(What I subsequently describe is the actual way in which the expression for pn (x, y) in

terms of the sum on the right-hand side of (3.38) was found.) What caught my eyes was

the part of the polynomial independent of y, x4 + 6x3 + 11x2 + 6x, which I recognized

as (x)4 = x(x + 1)(x + 2)(x + 3). For the fun of it, I subtracted that, just to see what

would happen:

In[2]:= Factor[%-x(x+1)(x+2)(x+3)]

2 3 2 2 2

Out[2]= y (6 - 10 x - 6 x -4x + 11 y - 6 x y + 6 x y+6y -4xy +

3

y)

Of course, a y factors. Okay, let us cancel that:

In[3]:= %/y

2 3 2 2 2 3

Out[3]= 6 - 10 x - 6 x -4x + 11 y - 6 x y + 6 x y+6y -4xy +y

56 C. KRATTENTHALER

One day I had the idea to continue in a āsystematicā manner: Let us subtract/add an

appropriate multiple of (x)3 ! Perhaps, āappropriateā in this context is to add 4(x)3 ,

because that does at least cancel the third powers of x:

In[4]:= Factor[%+4x(x+1)(x+2)]

2 2

Out[4]= (1 + y) (6 - 2 x + 6 x + 5 y - 4 x y + y )

I assume that I do not have to comment the rest:

In[5]:= %/(y+1)

2

Out[5]= 6 - 2 x + 6 x +5y-4xy+y

In[6]:= Factor[%-6x(x+1)]

Out[6]= (2 + y) (3 - 4 x + y)

In[7]:= %/(y+2)

Out[7]= 3 - 4 x + y

In[8]:= Factor[%+4x]

Out[8]= 3 + y

What this shows is that

p4 (x, y) = (x)4 ā’ 4(x)3 (y)1 + 6(x)2 (y)2 ā’ 4(x)1 (y)3 + (y)4 .

No doubt that, at this point, you would have immediately guessed (as I did) that, in

general, we āmustā have (compare (3.38))

n

n

(ā’1)k

pn (x, y) = (x)k (y)nā’k .

k

k=0

Appendix B: Turnbullā™s polarization of Bazinā™s theorem implies most of the

identities in Section 2.2

In this appendix we show that all the determinant lemmas from Section 2.2, with the

exception of Lemmas 8 and 9, follow from the evaluation of a certain determinant of

minors of a given matrix, an observation which I owe to Alain Lascoux. This evaluation,

due to Turnbull [179, p. 505], is a polarized version of a theorem of Bazin [119, II,

pp. 206ā“208] (see also [102, Sec. 3.1 and 3.4]).

For the statement of Turnbullā™s theorem we have to ļ¬x an n-rowed matrix A, in which

we label the columns, slightly unconventionally, by a2, . . . , am , b21, b31, b32, b41, . . . , bn,nā’1 ,

x1, x2, . . . , xn , for some m ā„ n, i.e., A is an n Ć— (n + m ā’ 1 + n ) matrix. Finally, let

2

[a, b, c, . . . ] denote the minor formed by concatenating columns a, b, c, . . . of A, in that

order.

ADVANCED DETERMINANT CALCULUS 57

Proposition 59. (Cf. [179, p. 505], [102, Sec. 3.4]). With the notation as explained

above, there holds

det [bj,1, bj,2 , . . . , bj,jā’1 , xi , aj+1 , . . . , am ]

1ā¤i,jā¤n

n

= [x1, x2, . . . , xn , an+1 , . . . , am ] [bj,1, bj,2, . . . , bj,jā’1 , aj , . . . , am ]. (B.1)

j=2

Now, in order to derive Lemma 3 from (B.1), we choose m = n and for A the matrix

a2 ... an b21 b31 b32 ... bn,nā’1 x1 x2 ... xn

ļ£« ļ£¶

1 ... 1 1 1 1 ... 1 1 1 ... 1

ļ£¬ ā’A2 X2 . . . X n ļ£·

ā’An ā’B2 ā’B2 ā’B3 ā’Bn

... ... X1

ļ£¬ ļ£·

ļ£¬ (ā’A2)2 . . . (ā’An )2 X2 . . . X n ļ£· ,

(ā’B2 )2 (ā’B2 )2 (ā’B3 )2 . . . (ā’Bn )2 2 2 2

X1

ļ£¬ ļ£·

ļ£. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ļ£ø

(ā’A2 )nā’1 . . . (ā’An )nā’1 (ā’B2 )nā’1 (ā’B2 )nā’1 (ā’B3 )nā’1 . . . (ā’Bn )nā’1 X1 nā’1 nā’1 nā’1

X2 . . . Xn

with the unconventional labelling of the columns indicated on top. I.e., column bst is

ļ¬lled with powers of ā’Bt+1 , 1 ā¤ t < s ā¤ n. With this choice of A, all the minors in (B.1)

are Vandermonde determinants. In particular, due to the Vandermonde determinant

evaluation (2.1), we then have for the (i, j)-entry of the determinant in (B.1)

[bj,1, bj,2, . . . , bj,jā’1 , xi, aj+1 , . . . , am]

j n

(Bs ā’ Bt ) (As ā’ At) (At ā’ Bs )

=

2ā¤s<tā¤j j+1ā¤s<tā¤n s=2 t=j+1

j

n

Ć— (Xi + As ) (Xi + Bs ),

s=j+1 s=2

which is, up to factors that only depend on the column index j, exactly the (i, j)-entry

of the determinant in (2.8). Thus, Turnbullā™s identity (B.1) gives the evaluation (2.8)

immediately, after some obvious simpliļ¬cation.

In order to derive Lemma 5 from (B.1), we choose m = n and for A the matrix

a2 ... an b21 b31

ļ£«

1 ... 1 1 1

ļ£¬ ā’A2 ā’ C/A2 ā’An ā’ C/An ā’B2,1 ā’ C/B2,1 ā’B3,1 ā’ C/B3,1

...

ļ£¬

ļ£¬ (ā’A2 ā’ C/A2 )2 . . . (ā’An ā’ C/An )2 (ā’B2,1 ā’ C/B2,1 ) (ā’B3,1 ā’ C/B3,1 )2

2

ļ£¬

ļ£. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

(ā’A2 ā’ C/A2 )nā’1 . . . (ā’An ā’ C/An )nā’1 (ā’B2,1 ā’ C/B2,1 )nā’1 (ā’B3,1 ā’ C/B3,1 )nā’1

b32 ... bn,nā’1 x1 ... xn

ļ£¶

1 ... 1 1 ... 1

Xn + C/Xn ļ£·

ā’B3,2 ā’ C/B3,2 ā’Bn,nā’1 ā’ C/Bn,nā’1

... X1 + C/X1 ... ļ£·

. . . (Xn + C/Xn )2 ļ£· .

(ā’B3,2 ā’ C/B3,2 ) . . . (ā’Bn,nā’1 ā’ C/Bn,nā’1 )

2 2 2

(X1 + C/X1 ) ļ£·

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .ļ£ø

(ā’B3,2 ā’ C/B3,2 )nā’1 . . . (ā’Bn,nā’1 ā’ C/Bn,nā’1 )nā’1 (X1 + C/X1 )nā’1 . . . (Xn + C/Xn )nā’1

58 C. KRATTENTHALER

(In this display, the ļ¬rst line contains columns a2, . . . , b31 of A, while the second line

contains the remaining columns.) Again, with this choice of A, all the minors in (B.1)

are Vandermonde determinants. Therefore, by noting that (S + C/S) ā’ (T + C/T ) =

(S ā’ T )(C/S ā’ T )/(ā’T ), and by writing pjā’1 (X) for

jā’1

(X + Bj,s )(C/X + Bj,s ), (B.2)

s=1

we have for the (i, j)-entry of the determinant in (B.1)

(Bj,s + C/Bj,s ā’ Bj,t ā’ C/Bj,t )

[bj,1, bj,2, . . . , bj,jā’1 , xi, aj+1 , . . . , am] =

1ā¤s<tā¤jā’1

jā’1 n

Ć— (As + C/As ā’ At ā’ C/At ) (At + C/At ā’ Bj,s ā’ C/Bj,s )

j+1ā¤s<tā¤n s=1 t=j+1

jā’1

n

As ) Aā’1 ā’1

Ć— (Xi + As )(C/Xi + pjā’1 (Xi ) Bj,s

s

s=1

s=j+1

for the (i, j)-entry of the determinant in (B.1). This is, up to factors which depend

only on the column index j, exactly the (i, j)-entry of the determinant in (2.11). The

polynomials pjā’1 (X), j = 1, 2, . . . , n, can indeed be regarded as arbitrary Laurent poly-

nomials satisfying the conditions of Lemma 5, because any Laurent polynomial qjā’1 (X)

over the complex numbers of degree at most j ā’ 1 and with qjā’1 (X) = qjā’1 (C/X) can

be written in the form (B.2). Thus, Turnbullā™s identity (B.1) implies the evaluation

(2.11) as well.

Similar choices for A are possible in order to derive Lemmas 4, 6 and 7 (which are in

fact just limiting cases of Lemma 5) from Proposition 59.

Appendix C: Jean-Yves Thibonā™s proof of Theorem 56

Obviously, the determinant in (3.64) is the determinant of the linear operator

Kn (q) := ĻāSn q maj Ļ Ļ acting on the group algebra C[Sn ] of the symmetric group.

Thus, if we are able to determine all the eigenvalues of this operator, together with

their multiplicities, we will be done. The determinant is then just the product of all

the eigenvalues (with multiplicities).

The operator Kn (q) is also an element of Solomonā™s descent algebra (because permu-

tations with the same descent set must necessarily have the same major index). The

descent algebra is canonically isomorphic to the algebra of noncommutative symmetric

functions (see [56, Sec. 5]). It is shown in [95, Prop. 6.3] that, as a noncommutative

symmetric function, Kn (q) is equal to (q; q)n Sn (A/(1 ā’ q)), where Sn (B) denotes the

complete (noncommutative) symmetric function of degree n of some alphabet B.

The inverse element of Sn (A/(1 ā’ q)) happens to be Sn((1 ā’ q)A), i.e., Sn ((1 ā’ q)A) ā—

Sn(A/(1ā’q)) = Sn(A),13 with ā— denoting the internal multiplication of noncommutative

symmetric functions (corresponding to the multiplication in the descent algebra). This

n

is seen as follows. As in [95, Sec. 2.1] let us write Ļ(B; t) = nā„0 Sn (B)t for the

13

By deļ¬nition of the isomorphism between noncommutative symmetric functions and elements in

the descent algebra, Sn (A) corresponds to the identity element in the descent algebra of Sn .

ADVANCED DETERMINANT CALCULUS 59

generating function for complete symmetric functions of some alphabet B, and Ī»(B; t) =

n

ńņš. 9 |