<< . .

. 9
( : 11)



. . >>

First of all, as I already claimed, guessing can be largely automatized. This is due to
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
( : 11)



. . >>