• 検索結果がありません。

Proof of the q-TSPP Conjecture

N/A
N/A
Protected

Academic year: 2022

シェア "Proof of the q-TSPP Conjecture"

Copied!
121
0
0

読み込み中.... (全文を見る)

全文

(1)

Proof of the q-TSPP Conjecture

Christoph Koutschan

(collaboration with Manuel Kauers and Doron Zeilberger)

Research Institute for Symbolic Computation (RISC) Johannes Kepler Universit¨at Linz, Austria

13.09.2010

S´eminaire Lotharingien de Combinatoire 65

(2)

T CSP

P

Totally

Cyclically Symmetric Plane

Partition

(3D Ferrers diagram)

17 =

5 + 4 + 3 + 2 + 1 + 1 + 1

two-dimensional array π = (πi,j)1≤i,j

πi,j ∈Nwith finite sum

|π|=P πi,j

πi,j ≥πi+1,j and πi,j ≥πi,j+1

πi,jj,i

cyclically symmetric 3D Ferrers diagram is invariant under the action ofS3.

(3)

T CS

PP

Totally

Cyclically Symmetric

Plane Partition

(3D Ferrers diagram) 17 =

5 + 4 + 3 + 2 + 1 + 1 + 1

two-dimensional array π = (πi,j)1≤i,j

πi,j ∈Nwith finite sum

|π|=P πi,j

πi,j ≥πi+1,j and πi,j ≥πi,j+1

πi,jj,i

cyclically symmetric 3D Ferrers diagram is invariant under the action ofS3.

(4)

T CS

PP

Totally

Cyclically Symmetric

Plane Partition (3D Ferrers diagram)

17 =

5 + 4 + 3 + 2 + 1 + 1 + 1

two-dimensional array π = (πi,j)1≤i,j

πi,j ∈Nwith finite sum

|π|=P πi,j

πi,j ≥πi+1,j and πi,j ≥πi,j+1

πi,jj,i

cyclically symmetric 3D Ferrers diagram is invariant under the action ofS3.

(5)

T C

SPP

Totally Cyclically

Symmetric Plane Partition

(3D Ferrers diagram) 17 =

5 + 4 + 3 + 2 + 1 + 1 + 1

two-dimensional array π = (πi,j)1≤i,j

πi,j ∈Nwith finite sum

|π|=P πi,j

πi,j ≥πi+1,j and πi,j ≥πi,j+1

πi,jj,i

cyclically symmetric 3D Ferrers diagram is invariant under the action ofS3.

(6)

T

CSPP

Totally

Cyclically Symmetric Plane Partition

(3D Ferrers diagram) 17 =

5 + 4 + 3 + 2 + 1 + 1 + 1

two-dimensional array π = (πi,j)1≤i,j

πi,j ∈Nwith finite sum

|π|=P πi,j

πi,j ≥πi+1,j and πi,j ≥πi,j+1

πi,jj,i

cyclically symmetric

3D Ferrers diagram is invariant under the action ofS3.

(7)

T

C

SPP

Totally

Cyclically

Symmetric Plane Partition

(3D Ferrers diagram) 17 =

5 + 4 + 3 + 2 + 1 + 1 + 1

two-dimensional array π = (πi,j)1≤i,j

πi,j ∈Nwith finite sum

|π|=P πi,j

πi,j ≥πi+1,j and πi,j ≥πi,j+1

πi,jj,i

cyclically symmetric 3D Ferrers diagram is invariant under the action ofS3.

(8)

TSPP Count

Theorem: There are Y

1≤i≤j≤k≤n

i+j+k−1

i+j+k−2 TSPPs in [0, n]3.

Example: (n= 2)

Y

1≤i≤j≤k≤2

i+j+k−1 i+j+k−2 = 2

1 ·3 2·4

3 ·5 4 = 5.

(9)

TSPP Count

Theorem: There are Y

1≤i≤j≤k≤n

i+j+k−1

i+j+k−2 TSPPs in[0, n]3.

Proof: See

John Stembridge,The enumeration of totally symmetric plane partitions, Advances in Mathematics 111 (1995), 227–243.

George E. Andrews, Peter Paule, and Carsten Schneider, Plane Partitions VI. Stembridge’s TSPP theorem, Advances in Applied Mathematics 34(2005), 709–739.

Christoph Koutschan, Eliminating Human Insight: An Algorithmic Proof of Stembridge’s TSPP Theorem, Contemporary Mathematics517 (2010), 219–230.

(10)

Example: TSPP and orbits

(11)

Example: TSPP and orbits

(12)

Example: TSPP and orbits

(13)

Example: TSPP and orbits

(14)

Example: TSPP and orbits

(15)

Orbits

(16)

Orbits

(17)

Orbits

(18)

Orbits

(19)

Orbits

(20)

Orbits

(21)

Orbits

(22)

Orbits

(23)

Orbits

(24)

Orbits

(25)

Orbits

(26)

Orbits

(27)

Orbits

(28)

Orbits

(29)

Orbits

(30)

Orbits

(31)

Orbits

(32)

Orbits

(33)

Orbits

(34)

Orbits

(35)

Orbits

(36)

Orbits

(37)

Orbits

(38)

Orbits

(39)

Orbits

(40)

Orbits

(41)

Orbits

(42)

Orbits

(43)

Orbits

(44)

Orbits

(45)

Orbits

(46)

Orbits

(47)

Orbits

(48)

Orbits

(49)

Orbits

(50)

Orbits

(51)

36 Orbits

(52)

LetT(n) denote set of TSPPs with largest part at mostn.

q0 + q1 + q2 + q3 + q4 =

= 1 +q+q2+q3+q4 = 1−q5 1−q

q-TSPP conjecture: X

π∈T(n)

q|π/S3| = Y

1≤i≤j≤k≤n

1−qi+j+k−1 1−qi+j+k−2

Stembridge’s theorem: |T(n)| = Y

1≤i≤j≤k≤n

i+j+k−1 i+j+k−2

(53)

LetT(n) denote set of TSPPs with largest part at mostn.

q0

q1 q2 q3 q4

+ + + + =

= 1 +q+q2+q3+q4 = 1−q5 1−q

q-TSPP conjecture: X

π∈T(n)

q|π/S3| = Y

1≤i≤j≤k≤n

1−qi+j+k−1 1−qi+j+k−2

Stembridge’s theorem: |T(n)| = Y

1≤i≤j≤k≤n

i+j+k−1 i+j+k−2

(54)

LetT(n) denote set of TSPPs with largest part at mostn.

q0 q1

q2 q3 q4

+ + + + =

= 1 +q+q2+q3+q4 = 1−q5 1−q

q-TSPP conjecture: X

π∈T(n)

q|π/S3| = Y

1≤i≤j≤k≤n

1−qi+j+k−1 1−qi+j+k−2

Stembridge’s theorem: |T(n)| = Y

1≤i≤j≤k≤n

i+j+k−1 i+j+k−2

(55)

LetT(n) denote set of TSPPs with largest part at mostn.

q0 q1

q2 q3 q4

+ + + + =

= 1 +q+q2+q3+q4 = 1−q5 1−q

q-TSPP conjecture: X

π∈T(n)

q|π/S3| = Y

1≤i≤j≤k≤n

1−qi+j+k−1 1−qi+j+k−2

Stembridge’s theorem: |T(n)| = Y

1≤i≤j≤k≤n

i+j+k−1 i+j+k−2

(56)

LetT(n) denote set of TSPPs with largest part at mostn.

q0 q1 q2

q3 q4

+ + + + =

= 1 +q+q2+q3+q4 = 1−q5 1−q

q-TSPP conjecture: X

π∈T(n)

q|π/S3| = Y

1≤i≤j≤k≤n

1−qi+j+k−1 1−qi+j+k−2

Stembridge’s theorem: |T(n)| = Y

1≤i≤j≤k≤n

i+j+k−1 i+j+k−2

(57)

LetT(n) denote set of TSPPs with largest part at mostn.

q0 q1 q2

q3 q4

+ + + + =

= 1 +q+q2+q3+q4 = 1−q5 1−q

q-TSPP conjecture: X

π∈T(n)

q|π/S3| = Y

1≤i≤j≤k≤n

1−qi+j+k−1 1−qi+j+k−2

Stembridge’s theorem: |T(n)| = Y

1≤i≤j≤k≤n

i+j+k−1 i+j+k−2

(58)

LetT(n) denote set of TSPPs with largest part at mostn.

q0 q1 q2

q3 q4

+ + + + =

= 1 +q+q2+q3+q4 = 1−q5 1−q

q-TSPP conjecture: X

π∈T(n)

q|π/S3| = Y

1≤i≤j≤k≤n

1−qi+j+k−1 1−qi+j+k−2

Stembridge’s theorem: |T(n)| = Y

1≤i≤j≤k≤n

i+j+k−1 i+j+k−2

(59)

LetT(n) denote set of TSPPs with largest part at mostn.

q0 q1 q2 q3

q4

+ + + + =

= 1 +q+q2+q3+q4 = 1−q5 1−q

q-TSPP conjecture: X

π∈T(n)

q|π/S3| = Y

1≤i≤j≤k≤n

1−qi+j+k−1 1−qi+j+k−2

Stembridge’s theorem: |T(n)| = Y

1≤i≤j≤k≤n

i+j+k−1 i+j+k−2

(60)

LetT(n) denote set of TSPPs with largest part at mostn.

q0 q1 q2 q3

q4

+ + + + =

= 1 +q+q2+q3+q4 = 1−q5 1−q

q-TSPP conjecture: X

π∈T(n)

q|π/S3| = Y

1≤i≤j≤k≤n

1−qi+j+k−1 1−qi+j+k−2

Stembridge’s theorem: |T(n)| = Y

1≤i≤j≤k≤n

i+j+k−1 i+j+k−2

(61)

LetT(n) denote set of TSPPs with largest part at mostn.

q0 q1 q2 q3

q4

+ + + + =

= 1 +q+q2+q3+q4 = 1−q5 1−q

q-TSPP conjecture: X

π∈T(n)

q|π/S3| = Y

1≤i≤j≤k≤n

1−qi+j+k−1 1−qi+j+k−2

Stembridge’s theorem: |T(n)| = Y

1≤i≤j≤k≤n

i+j+k−1 i+j+k−2

(62)

LetT(n) denote set of TSPPs with largest part at mostn.

q0 q1 q2 q3

q4

+ + + + =

= 1 +q+q2+q3+q4 = 1−q5 1−q

q-TSPP conjecture: X

π∈T(n)

q|π/S3| = Y

1≤i≤j≤k≤n

1−qi+j+k−1 1−qi+j+k−2

Stembridge’s theorem: |T(n)| = Y

1≤i≤j≤k≤n

i+j+k−1 i+j+k−2

(63)

LetT(n) denote set of TSPPs with largest part at mostn.

q0 q1 q2 q3 q4

+ + + + =

= 1 +q+q2+q3+q4 = 1−q5 1−q

q-TSPP conjecture: X

π∈T(n)

q|π/S3| = Y

1≤i≤j≤k≤n

1−qi+j+k−1 1−qi+j+k−2

Stembridge’s theorem: |T(n)| = Y

1≤i≤j≤k≤n

i+j+k−1 i+j+k−2

(64)

LetT(n) denote set of TSPPs with largest part at mostn.

q0 + q1 + q2 + q3 + q4 =

= 1 +q+q2+q3+q4 = 1−q5 1−q

q-TSPP conjecture: X

π∈T(n)

q|π/S3| = Y

1≤i≤j≤k≤n

1−qi+j+k−1 1−qi+j+k−2

Stembridge’s theorem: |T(n)| = Y

1≤i≤j≤k≤n

i+j+k−1 i+j+k−2

(65)

The q -TSPP conjecture

Conjectured independently by

George Andrews and David Robbins (ca. 1983) Last surviving conjecture of the collection by Richard Stanley:

A baker’s dozen of conjectures concerning plane partitions(1986) (alternating sign matrix conjecture, TSPP conjecture, etc.)

All these problems had been solved, except one: q-TSPP.

(66)

The q -TSPP conjecture

Conjectured independently by

George Andrews and David Robbins (ca. 1983) Last surviving conjecture of the collection by Richard Stanley:

A baker’s dozen of conjectures concerning plane partitions(1986) (alternating sign matrix conjecture, TSPP conjecture, etc.)

All these problems had been solved, except one: q-TSPP.

(67)

Determinantal formulation

Also in Stanley’s paper, we find:

(68)

Okada’s determinant

Soichi Okada: On the generating functions for certain classes of plane partitions, Journal of Combinatorial Theory, Series A (1989).

Rewrite “the sum of all minors” as a single determinant!

Theq-TSPP conjecture is true if

det (ai,j)1≤i,j≤n= Y

1≤i≤j≤k≤n

1−qi+j+k−1 1−qi+j+k−2

2

=:bn.

where

ai,j :=qi+j−1

i+j−2 i−1

q

+q

i+j−1 i

q

!

+(1+qii,j−δi,j+1.

(69)

Zeilberger’s holonomic ansatz

Doron Zeilberger: The HOLONOMIC ANSATZ II. Automatic DISCOVERY(!) and PROOF(!!) of Holonomic Determinant Evaluations, Annals of Combinatorics (2007).

Problem: Given ai,j and bn6= 0. Show det (ai,j)1≤i,j≤n=bn. Method: “Pull out of the hat” a functioncn,j and prove

cn,n= 1 (n≥1),

n

X

j=1

cn,jai,j = 0 (1≤i < n),

n

X

j=1

cn,jan,j = bn

bn−1

(n≥1).

Thendet (ai,j)1≤i,j≤n=bn holds.

(70)

Zeilberger’s holonomic ansatz

Laplace expansion w.r.t. then-th row:

bn

bn bn−1

= det (ai,j)1≤i,j≤n

det (ai,j)1≤i,j≤n

bn−1

(q2n;q)2n (qn;q2)2n

=

n

X

j=1

an,j(−1)n+jMn,j

n

X

j=1

an,j (−1)n+jMn,j bn−1

| {z }

=:cn,j

n

X

j=1

an,jcn,j

cn,n = (−1)n+nMn,n bn−1

1

Now copy thei-th row (1≤i < n) into then-th row:

0 =

n

X

j=1

ai,j(−1)n+jMn,j n

X

j=1

ai,j

(−1)n+jMn,j

bn−1

| {z }

=cn,j

n

X

j=1

ai,jcn,j

(71)

Zeilberger’s holonomic ansatz

Laplace expansion w.r.t. then-th row:

bn

bn bn−1

=

det (ai,j)1≤i,j≤n

det (ai,j)1≤i,j≤n

bn−1

(q2n;q)2n (qn;q2)2n

=

n

X

j=1

an,j(−1)n+jMn,j

n

X

j=1

an,j (−1)n+jMn,j bn−1

| {z }

=:cn,j

n

X

j=1

an,jcn,j

cn,n = (−1)n+nMn,n bn−1

1

Now copy thei-th row (1≤i < n) into then-th row:

0 =

n

X

j=1

ai,j(−1)n+jMn,j n

X

j=1

ai,j

(−1)n+jMn,j

bn−1

| {z }

=cn,j

n

X

j=1

ai,jcn,j

(72)

Zeilberger’s holonomic ansatz

Laplace expansion w.r.t. then-th row:

bn

bn bn−1

=

det (ai,j)1≤i,j≤n

det (ai,j)1≤i,j≤n

bn−1

(q2n;q)2n (qn;q2)2n

=

n

X

j=1

an,j(−1)n+jMn,j

n

X

j=1

an,j (−1)n+jMn,j bn−1

| {z }

=:cn,j

n

X

j=1

an,jcn,j

cn,n = (−1)n+nMn,n bn−1

1

Now copy thei-th row (1≤i < n) into then-th row:

0 =

n

X

j=1

ai,j(−1)n+jMn,j n

X

j=1

ai,j

(−1)n+jMn,j

bn−1

| {z }

=cn,j

n

X

j=1

ai,jcn,j

(73)

Zeilberger’s holonomic ansatz

Laplace expansion w.r.t. then-th row:

bn

bn bn−1

=

det (ai,j)1≤i,j≤n

det (ai,j)1≤i,j≤n

bn−1

(q2n;q)2n (qn;q2)2n

=

n

X

j=1

an,j(−1)n+jMn,j

n

X

j=1

an,j (−1)n+jMn,j bn−1

| {z }

=:cn,j

n

X

j=1

an,jcn,j

cn,n =

(−1)n+nMn,n bn−1

1

Now copy thei-th row (1≤i < n) into then-th row:

0 =

n

X

j=1

ai,j(−1)n+jMn,j n

X

j=1

ai,j

(−1)n+jMn,j

bn−1

| {z }

=cn,j

n

X

j=1

ai,jcn,j

(74)

Zeilberger’s holonomic ansatz

Laplace expansion w.r.t. then-th row:

bn

bn bn−1

=

det (ai,j)1≤i,j≤n

det (ai,j)1≤i,j≤n

bn−1

(q2n;q)2n (qn;q2)2n

=

n

X

j=1

an,j(−1)n+jMn,j

n

X

j=1

an,j (−1)n+jMn,j bn−1

| {z }

=:cn,j

n

X

j=1

an,jcn,j

cn,n =

(−1)n+nMn,n bn−1

1

Now copy thei-th row (1≤i < n) into then-th row:

0 =

n

X

j=1

ai,j(−1)n+jMn,j

n

X

j=1

ai,j

(−1)n+jMn,j

bn−1

| {z }

=cn,j

n

X

j=1

ai,jcn,j

(75)

Zeilberger’s holonomic ansatz

Laplace expansion w.r.t. then-th row:

bn

bn bn−1

=

det (ai,j)1≤i,j≤n

det (ai,j)1≤i,j≤n

bn−1

(q2n;q)2n (qn;q2)2n

=

n

X

j=1

an,j(−1)n+jMn,j

n

X

j=1

an,j (−1)n+jMn,j bn−1

| {z }

=:cn,j

n

X

j=1

an,jcn,j

cn,n =

(−1)n+nMn,n bn−1

1

Now copy thei-th row (1≤i < n) into then-th row:

0 =

n

X

j=1

ai,j(−1)n+jMn,j

n

X

j=1

ai,j

(−1)n+jMn,j

bn−1

| {z }

=cn,j

n

X

j=1

ai,jcn,j

(76)

Zeilberger’s holonomic ansatz

Laplace expansion w.r.t. then-th row:

bn

bn bn−1

=

det (ai,j)1≤i,j≤n

det (ai,j)1≤i,j≤n

bn−1

(q2n;q)2n (qn;q2)2n

=

n

X

j=1

an,j(−1)n+jMn,j

n

X

j=1

an,j (−1)n+jMn,j bn−1

| {z }

=:cn,j

n

X

j=1

an,jcn,j

cn,n =

(−1)n+nMn,n bn−1

1

Now copy thei-th row (1≤i < n) into then-th row:

0 =

n

X

j=1

ai,j(−1)n+jMn,j n

X

j=1

ai,j

(−1)n+jMn,j

bn−1

| {z }

=cn,j

n

X

j=1

ai,jcn,j

(77)

Zeilberger’s holonomic ansatz

Laplace expansion w.r.t. then-th row:

bn

bn bn−1

=

det (ai,j)1≤i,j≤n

det (ai,j)1≤i,j≤n

bn−1

(q2n;q)2n

(qn;q2)2n =

n

X

j=1

an,j(−1)n+jMn,j

n

X

j=1

an,j (−1)n+jMn,j bn−1

| {z }

=:cn,j

n

X

j=1

an,jcn,j

cn,n =

(−1)n+nMn,n bn−1

1

Now copy thei-th row (1≤i < n) into then-th row:

0 =

n

X

j=1

ai,j(−1)n+jMn,j n

X

j=1

ai,j

(−1)n+jMn,j

bn−1

| {z }

=cn,j

n

X

j=1

ai,jcn,j

(78)

Zeilberger’s holonomic ansatz

Problem: Given ai,j and bn6= 0. Show det (ai,j)1≤i,j≤n=bn. Method: “Pull out of the hat” a functioncn,j and prove

cn,n= 1 (n≥1),

n

X

j=1

cn,jai,j = 0 (1≤i < n),

n

X

j=1

cn,jan,j = bn

bn−1

(n≥1).

Thendet (ai,j)1≤i,j≤n=bn holds.

(79)

Advocatus Diaboli

What if det (ai,j)1≤i,j≤m = 0 for somem???

Thencn,j is not uniquely deter- mined!

Proof is wrong!

No! Argue by induction onn.

(80)

Advocatus Diaboli

What if det (ai,j)1≤i,j≤m = 0 for somem???

Thencn,j is not uniquely deter- mined!

Proof is wrong!

No! Argue by induction onn.

(81)

Holonomic systems

Of course, it is unlikely to get a closed-form description forcn,j!

Instead we aim at some “suitable description”, viz. implicitly via linear recurrences (“holonomic system”) plus initial values. Example: The binomial coefficientfn,k = nk

can be described by (n−k+ 1)fn+1,k = (n+ 1)fn,k

(k+ 1)fn,k+1 = (n−k)fn,k f0,0 = 1

Analogously, we get for theq-binomial coefficientf¯n,k =n

k

q: (qn+1−qk) ¯fn+1,k = (qk+n+1−qk) ¯fn,k

(q2k+1−qk) ¯fn,k+1 = (qn−qk) ¯fn,k0,0 = 1

All linear combinations of shifts are again valid recurrences: (n−k)fn+1,k+1−(n+ 1)fn,k+1 = 0

(k+ 1)fn+1,k+1−(n−k+ 1)fn+1,k= 0

(n+ 1)fn+1,k+1−(n−k+ 1)fn+1,k−(n+ 1)fn,k+1 = 0 They form a left ideal in some noncommutative operator algebra. But there is no reason whycn,j should admit such a recursive description.

(82)

Holonomic systems

Of course, it is unlikely to get a closed-form description forcn,j! Instead we aim at some “suitable description”, viz. implicitly via linear recurrences (“holonomic system”) plus initial values.

Example: The binomial coefficientfn,k = nk

can be described by (n−k+ 1)fn+1,k = (n+ 1)fn,k

(k+ 1)fn,k+1 = (n−k)fn,k f0,0 = 1

Analogously, we get for theq-binomial coefficientf¯n,k =n

k

q: (qn+1−qk) ¯fn+1,k = (qk+n+1−qk) ¯fn,k

(q2k+1−qk) ¯fn,k+1 = (qn−qk) ¯fn,k0,0 = 1

All linear combinations of shifts are again valid recurrences: (n−k)fn+1,k+1−(n+ 1)fn,k+1 = 0

(k+ 1)fn+1,k+1−(n−k+ 1)fn+1,k= 0

(n+ 1)fn+1,k+1−(n−k+ 1)fn+1,k−(n+ 1)fn,k+1 = 0 They form a left ideal in some noncommutative operator algebra. But there is no reason whycn,j should admit such a recursive description.

(83)

Holonomic systems

Of course, it is unlikely to get a closed-form description forcn,j! Instead we aim at some “suitable description”, viz. implicitly via linear recurrences (“holonomic system”) plus initial values.

Example: The binomial coefficientfn,k = nk

can be described by (n−k+ 1)fn+1,k = (n+ 1)fn,k

(k+ 1)fn,k+1 = (n−k)fn,k f0,0 = 1

Analogously, we get for theq-binomial coefficientf¯n,k =n

k

q: (qn+1−qk) ¯fn+1,k = (qk+n+1−qk) ¯fn,k

(q2k+1−qk) ¯fn,k+1 = (qn−qk) ¯fn,k0,0 = 1

All linear combinations of shifts are again valid recurrences: (n−k)fn+1,k+1−(n+ 1)fn,k+1 = 0

(k+ 1)fn+1,k+1−(n−k+ 1)fn+1,k= 0

(n+ 1)fn+1,k+1−(n−k+ 1)fn+1,k−(n+ 1)fn,k+1 = 0 They form a left ideal in some noncommutative operator algebra. But there is no reason whycn,j should admit such a recursive description.

(84)

Holonomic systems

Of course, it is unlikely to get a closed-form description forcn,j! Instead we aim at some “suitable description”, viz. implicitly via linear recurrences (“holonomic system”) plus initial values.

Example: The binomial coefficientfn,k = nk

can be described by (n−k+ 1)fn+1,k = (n+ 1)fn,k

(k+ 1)fn,k+1 = (n−k)fn,k f0,0 = 1

Analogously, we get for theq-binomial coefficientf¯n,k =n

k

q: (qn+1−qk) ¯fn+1,k = (qk+n+1−qk) ¯fn,k

(q2k+1−qk) ¯fn,k+1 = (qn−qk) ¯fn,k0,0 = 1

All linear combinations of shifts are again valid recurrences: (n−k)fn+1,k+1−(n+ 1)fn,k+1 = 0

(k+ 1)fn+1,k+1−(n−k+ 1)fn+1,k= 0

(n+ 1)fn+1,k+1−(n−k+ 1)fn+1,k−(n+ 1)fn,k+1 = 0 They form a left ideal in some noncommutative operator algebra. But there is no reason whycn,j should admit such a recursive description.

(85)

Holonomic systems

Of course, it is unlikely to get a closed-form description forcn,j! Instead we aim at some “suitable description”, viz. implicitly via linear recurrences (“holonomic system”) plus initial values.

Example: The binomial coefficientfn,k = nk

can be described by (n−k+ 1)fn+1,k = (n+ 1)fn,k

(k+ 1)fn,k+1 = (n−k)fn,k f0,0 = 1

Analogously, we get for theq-binomial coefficientf¯n,k =n

k

q: (qn+1−qk) ¯fn+1,k = (qk+n+1−qk) ¯fn,k

(q2k+1−qk) ¯fn,k+1 = (qn−qk) ¯fn,k0,0 = 1

All linear combinations of shifts are again valid recurrences:

(n−k)fn+1,k+1−(n+ 1)fn,k+1 = 0 (k+ 1)fn+1,k+1−(n−k+ 1)fn+1,k= 0

(n+ 1)fn+1,k+1−(n−k+ 1)fn+1,k−(n+ 1)fn,k+1 = 0 They form a left ideal in some noncommutative operator algebra.

But there is no reason whycn,j should admit such a recursive description.

(86)

Holonomic systems

Of course, it is unlikely to get a closed-form description forcn,j! Instead we aim at some “suitable description”, viz. implicitly via linear recurrences (“holonomic system”) plus initial values.

Example: The binomial coefficientfn,k = nk

can be described by (n−k+ 1)fn+1,k = (n+ 1)fn,k

(k+ 1)fn,k+1 = (n−k)fn,k f0,0 = 1

Analogously, we get for theq-binomial coefficientf¯n,k =n

k

q: (qn+1−qk) ¯fn+1,k = (qk+n+1−qk) ¯fn,k

(q2k+1−qk) ¯fn,k+1 = (qn−qk) ¯fn,k0,0 = 1

All linear combinations of shifts are again valid recurrences: (n−k)fn+1,k+1−(n+ 1)fn,k+1 = 0

(k+ 1)fn+1,k+1−(n−k+ 1)fn+1,k= 0

(n+ 1)fn+1,k+1−(n−k+ 1)fn+1,k−(n+ 1)fn,k+1 = 0 They form a left ideal in some noncommutative operator algebra.

But there is no reason whycn,j should admit such a recursive description.

(87)

Guessing

Manuel Kauers guessed some recurrences forcn,j.

Their Gr¨obner basis has the form

cn,j+4 = cn,j +cn,j+1+cn,j+2+cn,j+3 +cn+2,j+cn+2,j+1

cn+1,j+3 = cn,j +cn,j+1+cn,j+2+cn,j+3 +cn+1,j+cn+1,j+1+cn+1,j+2 +cn+2,j+cn+2,j+1+cn+3,j cn+2,j+2 = cn,j +cn,j+1+cn,j+2+cn,j+3

+cn+2,j+cn+2,j+1

cn+3,j+1 = cn,j +cn,j+1+cn,j+2+cn,j+3 +cn+1,j+cn+1,j+1+cn+1,j+2 +cn+2,j+cn+2,j+1+cn+3,j cn+4,j = cn,j +cn,j+1+cn,j+2+cn,j+3

+cn+2,j+cn+2,j+1

where eachis a polynomial inQ[q, qj, qn]of total degree≤100. The staircase of the Gr¨obner basis:

The total size is 244MB (several 1000 pages of paper)!

Great! We found the certificate for the determinant evaluation!

(88)

Guessing

Manuel Kauers guessed some recurrences forcn,j. Their Gr¨obner basis has the form

cn,j+4 = cn,j +cn,j+1+cn,j+2+cn,j+3 +cn+2,j+cn+2,j+1

cn+1,j+3 = cn,j +cn,j+1+cn,j+2+cn,j+3 +cn+1,j+cn+1,j+1+cn+1,j+2 +cn+2,j+cn+2,j+1+cn+3,j cn+2,j+2 = cn,j +cn,j+1+cn,j+2+cn,j+3

+cn+2,j+cn+2,j+1

cn+3,j+1 = cn,j +cn,j+1+cn,j+2+cn,j+3 +cn+1,j+cn+1,j+1+cn+1,j+2 +cn+2,j+cn+2,j+1+cn+3,j cn+4,j = cn,j +cn,j+1+cn,j+2+cn,j+3

+cn+2,j+cn+2,j+1

where eachis a polynomial inQ[q, qj, qn]of total degree≤100.

The staircase of the Gr¨obner basis:

The total size is 244MB (several 1000 pages of paper)!

Great! We found the certificate for the determinant evaluation!

(89)

Guessing

Manuel Kauers guessed some recurrences forcn,j.

Their Gr¨obner basis has the form

cn,j+4 = cn,j +cn,j+1+cn,j+2+cn,j+3 +cn+2,j+cn+2,j+1

cn+1,j+3 = cn,j +cn,j+1+cn,j+2+cn,j+3 +cn+1,j+cn+1,j+1+cn+1,j+2 +cn+2,j+cn+2,j+1+cn+3,j cn+2,j+2 = cn,j +cn,j+1+cn,j+2+cn,j+3

+cn+2,j+cn+2,j+1

cn+3,j+1 = cn,j +cn,j+1+cn,j+2+cn,j+3 +cn+1,j+cn+1,j+1+cn+1,j+2 +cn+2,j+cn+2,j+1+cn+3,j cn+4,j = cn,j +cn,j+1+cn,j+2+cn,j+3

+cn+2,j+cn+2,j+1

where eachis a polynomial inQ[q, qj, qn]of total degree≤100.

The staircase of the Gr¨obner basis:

The total size is 244MB (several 1000 pages of paper)!

Great! We found the certificate for the determinant evaluation!

(90)

Guessing

Manuel Kauers guessed some recurrences forcn,j.

Their Gr¨obner basis has the form

cn,j+4 = cn,j +cn,j+1+cn,j+2+cn,j+3 +cn+2,j+cn+2,j+1

cn+1,j+3 = cn,j +cn,j+1+cn,j+2+cn,j+3 +cn+1,j+cn+1,j+1+cn+1,j+2 +cn+2,j+cn+2,j+1+cn+3,j cn+2,j+2 = cn,j +cn,j+1+cn,j+2+cn,j+3

+cn+2,j+cn+2,j+1

cn+3,j+1 = cn,j +cn,j+1+cn,j+2+cn,j+3 +cn+1,j+cn+1,j+1+cn+1,j+2 +cn+2,j+cn+2,j+1+cn+3,j cn+4,j = cn,j +cn,j+1+cn,j+2+cn,j+3

+cn+2,j+cn+2,j+1

where eachis a polynomial inQ[q, qj, qn]of total degree≤100. The staircase of the Gr¨obner basis:

The total size is 244MB (several 1000 pages of paper)!

Great! We found the certificate for the determinant evaluation!

(91)

Advocatus Diaboli

The guessed recurrences can be artifacts, that do not describe the true functioncn,j!!!

(92)

Artifacts?

The guessed recurrences are very unlikely to be artifacts for several reasons:

solutions of a dense overdetermined linear systems

many polynomial coefficients factor nicely

recurrences produce correct values for cn,j that were not used for guessing

(93)

Advocatus Diaboli

Convincing, but not a proof!

And even if the recursive de- scription of cn,j is correct, this wouldn’t prove anything yet!!!

Show:

cn,n = 1

n

X

j=1

cn,jai,j = 0

n

X

j=1

cn,jan,j = bn

bn−1

(94)

The first identity

Prove the identities using the recursive description ofcn,j. How to provecn,n= 1 for all n≥1?

We find an element in the annihilating ideal of cn,j of the form pvcn+v,j+v =pv−1cn+v−1,j+v−1+· · ·+p1cn+1,j+1+p0cn,j

with v∈Nandpi ∈Q[q, qj, qn].

Substituting j→nyields a recurrence for the diagonal sequencecn,n.

Show that the corresponding operator factors into P1P2 where P2 corresponds tocn+1,n+1=cn,n.

Show that c1,1=· · ·=cv,v = 1.

−→works with v= 7.

(95)

The first identity

Prove the identities using the recursive description ofcn,j. How to provecn,n= 1 for all n≥1?

We find an element in the annihilating ideal of cn,j of the form pvcn+v,j+v =pv−1cn+v−1,j+v−1+· · ·+p1cn+1,j+1+p0cn,j

with v∈Nandpi ∈Q[q, qj, qn].

Substituting j→nyields a recurrence for the diagonal sequencecn,n.

Show that the corresponding operator factors into P1P2 where P2 corresponds tocn+1,n+1=cn,n.

Show that c1,1=· · ·=cv,v = 1.

−→works with v= 7.

(96)

Advocatus Diaboli

The leading coefficient p7 could have singularities!!!

Forn≥7we havep7(q, qn)6= 0.

(97)

Advocatus Diaboli

The leading coefficient p7 could have singularities!!!

Forn≥7we havep7(q, qn)6= 0.

(98)

The third identity

Recall:

n

X

j=1

cn,jan,j = bn bn−1

with

ai,j =qi+j−1

i+j−2 i−1

q

+q

i+j−1 i

q

!

+ (1 +qii,j−δi,j+1.

gives

(1 +qn)−cn,n−1+

n

X

j=1

c0n,j = bn

bn−1

with

c0n,j =qn+j−1

n+j−2 n−1

q

+q

n+j−1 n

q

! cn,j

(99)

The third identity

How to prove (1 +qn)−cn,n−1+

n

X

j=1

c0n,j = bn

bn−1

?

Compute an annihilating ideal for c0n,j via closure properties.

Find a relation in this ideal of the form

pvc0n+v,j+· · ·+p1c0n+1,j+p0c0n,j =tn,j+1−tn,j where thepv, . . . , p0 are rational functions inQ(q, qn)andtn,j is aQ(q, qj, qn)-linear combination of certain shifts of c0n,j.

Creative telescoping yields a recurrence for the sum.

Closure properties yield a recurrence for the left-hand side.

Recurrence for right-hand side is a right factor.

Compare finitely many initial values (again v= 7).

(100)

The third identity

How to prove (1 +qn)−cn,n−1+

n

X

j=1

c0n,j = bn

bn−1

?

Compute an annihilating ideal for c0n,j via closure properties.

Find a relation in this ideal of the form

pvc0n+v,j+· · ·+p1c0n+1,j+p0c0n,j =tn,j+1−tn,j where thepv, . . . , p0 are rational functions inQ(q, qn)andtn,j is aQ(q, qj, qn)-linear combination of certain shifts of c0n,j.

Creative telescoping yields a recurrence for the sum.

Closure properties yield a recurrence for the left-hand side.

Recurrence for right-hand side is a right factor.

Compare finitely many initial values (again v= 7).

(101)

A computational challenge

How to find the certificate

pv(q, qn)c0n+v,j+· · ·+p0(q, qn)c0n,j =tn,j+1−tn,j wheretn,j =r1(q, qn, qj)c0n+3,j+2+· · ·+r10(q, qn, qj)c0n,j?

Zeilberger’s slow algorithm: eliminate (e.g. with Gr¨obner bases) the variableqj.

Input recurrences have j-degrees between 24 and 30 (in the q= 1 case). After 48h, this was reduced to 23.

Estimate: 1677721600 days

Takayama’s algorithm: a faster variant which is also based on elimination.

Estimate: 52428800 days

Chyzak’s algorithm: ansatz with unknown pi(q, qn) and rk(q, qn, qj). Leads to a coupled first-order parametrized linear system of q-difference equations.

Estimate: ∞?

CK’s polynomial ansatz: refine

rk(q, qn, qj) =

L

X

l=0

rk,l(q, qn)(qj)l.

Leads to a linear system over Q(q, qn).

We used this ansatz for proving TSPP (took about 40 days). Estimate: 4000 days

CK’s rational ansatz: ansatz with rk(q, qn, qj) =

PL

l=0rk,l(q, qn)(qj)l dk(q, qn, qj)

where the denominators dk can be “guessed” by looking at the leading coefficients of the Gr¨obner basis.

Leads to a linear system over Q(q, qn) with 377 unknowns.

(102)

A computational challenge

How to find the certificate

pv(q, qn)c0n+v,j+· · ·+p0(q, qn)c0n,j =tn,j+1−tn,j wheretn,j =r1(q, qn, qj)c0n+3,j+2+· · ·+r10(q, qn, qj)c0n,j?

Zeilberger’s slow algorithm: eliminate (e.g. with Gr¨obner bases) the variableqj.

Input recurrences have j-degrees between 24 and 30 (in the q= 1 case). After 48h, this was reduced to 23.

Estimate: 1677721600 days

Takayama’s algorithm: a faster variant which is also based on elimination.

Estimate: 52428800 days

Chyzak’s algorithm: ansatz with unknown pi(q, qn) and rk(q, qn, qj). Leads to a coupled first-order parametrized linear system of q-difference equations.

Estimate: ∞?

CK’s polynomial ansatz: refine

rk(q, qn, qj) =

L

X

l=0

rk,l(q, qn)(qj)l.

Leads to a linear system over Q(q, qn).

We used this ansatz for proving TSPP (took about 40 days). Estimate: 4000 days

CK’s rational ansatz: ansatz with rk(q, qn, qj) =

PL

l=0rk,l(q, qn)(qj)l dk(q, qn, qj)

where the denominators dk can be “guessed” by looking at the leading coefficients of the Gr¨obner basis.

Leads to a linear system over Q(q, qn) with 377 unknowns.

(103)

A computational challenge

How to find the certificate

pv(q, qn)c0n+v,j+· · ·+p0(q, qn)c0n,j =tn,j+1−tn,j wheretn,j =r1(q, qn, qj)c0n+3,j+2+· · ·+r10(q, qn, qj)c0n,j?

Zeilberger’s slow algorithm: eliminate (e.g. with Gr¨obner bases) the variableqj.

Input recurrences have j-degrees between 24 and 30 (in the q= 1 case). After 48h, this was reduced to 23.

Estimate: 1677721600 days

Takayama’s algorithm: a faster variant which is also based on elimination.

Estimate: 52428800 days

Chyzak’s algorithm: ansatz with unknown pi(q, qn) and rk(q, qn, qj). Leads to a coupled first-order parametrized linear system of q-difference equations.

Estimate: ∞?

CK’s polynomial ansatz: refine

rk(q, qn, qj) =

L

X

l=0

rk,l(q, qn)(qj)l.

Leads to a linear system over Q(q, qn).

We used this ansatz for proving TSPP (took about 40 days). Estimate: 4000 days

CK’s rational ansatz: ansatz with rk(q, qn, qj) =

PL

l=0rk,l(q, qn)(qj)l dk(q, qn, qj)

where the denominators dk can be “guessed” by looking at the leading coefficients of the Gr¨obner basis.

Leads to a linear system over Q(q, qn) with 377 unknowns.

参照

関連したドキュメント

Includes some proper curves, contrary to the quasi-Belyi type result. Sketch of

The last sections present two simple applications showing how the EB property may be used in the contexts where it holds: in Section 7 we give an alternative proof of

Applying the representation theory of the supergroupGL(m | n) and the supergroup analogue of Schur-Weyl Duality it becomes straightforward to calculate the combinatorial effect

As we saw before, the first important object for computing the Gr¨ obner region is the convex hull of a set of n &gt; 2 points, which is the frontier of N ew(f ).. The basic

To be specic, let us henceforth suppose that the quasifuchsian surface S con- tains two boundary components, the case of a single boundary component hav- ing been dealt with in [5]

The theory of log-links and log-shells, both of which are closely related to the lo- cal units of number fields under consideration (Section 5, Section 12), together with the

We relate group-theoretic constructions (´ etale-like objects) and Frobenioid-theoretic constructions (Frobenius-like objects) by transforming them into mono-theta environments (and

The theory of log-links and log-shells, which arise from the local units of number fields under consideration (Section 5), together with the Kummer theory that relates