Proof of the q-TSPP Conjecture

(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,j =πj,i

• cyclically symmetric 3D Ferrers diagram is invariant under the action ofS₃.

(3)

T CS

PP

Totally

Cyclically Symmetric

Plane Partition

(3D Ferrers diagram) 17 =

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

|π|=P π_i,j

• πi,j =πj,i

(4)

T CS

PP

Totally

Cyclically Symmetric

Plane Partition (3D Ferrers diagram)

17 =

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

|π|=P π_i,j

• πi,j =πj,i

(5)

T C

SPP

Totally Cyclically

Symmetric Plane Partition

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

|π|=P π_i,j

• π_i,j =π_j,i

(6)

T

CSPP

Totally

Cyclically Symmetric Plane Partition

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

|π|=P π_i,j

• πi,j =πj,i

• cyclically symmetric

3D Ferrers diagram is invariant under the action ofS₃.

(7)

T

C

SPP

Totally

Cyclically

Symmetric Plane Partition

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

|π|=P π_i,j

• π_i,j =π_j,i

(8)

TSPP Count

Theorem: There are Y

1≤i≤j≤k≤n

i+j+k−1

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

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]³.

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.

q⁰ + q¹ + q² + q³ + q⁴ =

= 1 +q+q²+q³+q⁴ = 1−q⁵ 1−q

q-TSPP conjecture: X

π∈T(n)

q^|π/S³^| = Y

1≤i≤j≤k≤n

1−q^i+j+k−1 1−q^i+j+k−2

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

1≤i≤j≤k≤n

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

(53)

q⁰

q¹ q² q³ q⁴

+ + + + =

= 1 +q+q²+q³+q⁴ = 1−q⁵ 1−q

π∈T(n)

q^|π/S³^| = Y

1≤i≤j≤k≤n

1−q^i+j+k−1 1−q^i+j+k−2

1≤i≤j≤k≤n

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

(54)

q⁰ q¹

q² q³ q⁴

+ + + + =

= 1 +q+q²+q³+q⁴ = 1−q⁵ 1−q

π∈T(n)

q^|π/S³^| = Y

1≤i≤j≤k≤n

1−q^i+j+k−1 1−q^i+j+k−2

1≤i≤j≤k≤n

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

(55)

q⁰ q¹

q² q³ q⁴

+ + + + =

= 1 +q+q²+q³+q⁴ = 1−q⁵ 1−q

π∈T(n)

q^|π/S³^| = Y

1≤i≤j≤k≤n

1−q^i+j+k−1 1−q^i+j+k−2

1≤i≤j≤k≤n

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

(56)

q⁰ q¹ q²

q³ q⁴

+ + + + =

= 1 +q+q²+q³+q⁴ = 1−q⁵ 1−q

π∈T(n)

q^|π/S³^| = Y

1≤i≤j≤k≤n

1−q^i+j+k−1 1−q^i+j+k−2

1≤i≤j≤k≤n

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

(57)

q⁰ q¹ q²

q³ q⁴

+ + + + =

= 1 +q+q²+q³+q⁴ = 1−q⁵ 1−q

π∈T(n)

q^|π/S³^| = Y

1≤i≤j≤k≤n

1−q^i+j+k−1 1−q^i+j+k−2

1≤i≤j≤k≤n

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

(58)

q⁰ q¹ q²

q³ q⁴

+ + + + =

= 1 +q+q²+q³+q⁴ = 1−q⁵ 1−q

π∈T(n)

q^|π/S³^| = Y

1≤i≤j≤k≤n

1−q^i+j+k−1 1−q^i+j+k−2

1≤i≤j≤k≤n

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

(59)

q⁰ q¹ q² q³

q⁴

+ + + + =

= 1 +q+q²+q³+q⁴ = 1−q⁵ 1−q

π∈T(n)

q^|π/S³^| = Y

1≤i≤j≤k≤n

1−q^i+j+k−1 1−q^i+j+k−2

1≤i≤j≤k≤n

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

(60)

q⁰ q¹ q² q³

q⁴

+ + + + =

= 1 +q+q²+q³+q⁴ = 1−q⁵ 1−q

π∈T(n)

q^|π/S³^| = Y

1≤i≤j≤k≤n

1−q^i+j+k−1 1−q^i+j+k−2

1≤i≤j≤k≤n

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

(61)

q⁰ q¹ q² q³

q⁴

+ + + + =

= 1 +q+q²+q³+q⁴ = 1−q⁵ 1−q

π∈T(n)

q^|π/S³^| = Y

1≤i≤j≤k≤n

1−q^i+j+k−1 1−q^i+j+k−2

1≤i≤j≤k≤n

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

(62)

q⁰ q¹ q² q³

q⁴

+ + + + =

= 1 +q+q²+q³+q⁴ = 1−q⁵ 1−q

π∈T(n)

q^|π/S³^| = Y

1≤i≤j≤k≤n

1−q^i+j+k−1 1−q^i+j+k−2

1≤i≤j≤k≤n

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

(63)

q⁰ q¹ q² q³ q⁴

+ + + + =

= 1 +q+q²+q³+q⁴ = 1−q⁵ 1−q

π∈T(n)

q^|π/S³^| = Y

1≤i≤j≤k≤n

1−q^i+j+k−1 1−q^i+j+k−2

1≤i≤j≤k≤n

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

(64)

q⁰ + q¹ + q² + q³ + q⁴ =

= 1 +q+q²+q³+q⁴ = 1−q⁵ 1−q

π∈T(n)

q^|π/S³^| = Y

1≤i≤j≤k≤n

1−q^i+j+k−1 1−q^i+j+k−2

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 (a_i,j)1≤i,j≤n= Y

1≤i≤j≤k≤n

1−q^i+j+k−1 1−q^i+j+k−2

2

=:b_n.

where

a_i,j :=q^i+j−1

i+j−2 i−1

q

+q

i+j−1 i

q

!

+(1+qⁱ)δ_i,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:

b_n

b_n bn−1

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

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

bn−1

(q²ⁿ;q)²_n (qⁿ;q²)²_n

=

n

X

j=1

a_n,j(−1)^n+jM_n,j

n

X

j=1

a_n,j (−1)^n+jM_n,j bn−1

| {z }

=:cn,j

n

X

j=1

a_n,jc_n,j

cn,n = (−1)ⁿ⁺ⁿM_n,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

b_n

b_n bn−1

=

bn−1

(q²ⁿ;q)²_n (qⁿ;q²)²_n

=

n

X

j=1

n

X

j=1

| {z }

=:cn,j

n

X

j=1

a_n,jc_n,j

1

0 =

n

X

j=1

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

b_n

b_n bn−1

=

bn−1

(q²ⁿ;q)²_n (qⁿ;q²)²_n

=

n

X

j=1

n

X

j=1

| {z }

=:cn,j

n

X

j=1

a_n,jc_n,j

1

0 =

n

X

j=1

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

b_n

b_n bn−1

=

bn−1

(q²ⁿ;q)²_n (qⁿ;q²)²_n

=

n

X

j=1

n

X

j=1

| {z }

=:cn,j

n

X

j=1

a_n,jc_n,j

cn,n =

(−1)ⁿ⁺ⁿM_n,n bn−1

1

0 =

n

X

j=1

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

b_n

b_n bn−1

=

bn−1

(q²ⁿ;q)²_n (qⁿ;q²)²_n

=

n

X

j=1

n

X

j=1

| {z }

=:cn,j

n

X

j=1

a_n,jc_n,j

cn,n =

1

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

b_n

b_n bn−1

=

bn−1

(q²ⁿ;q)²_n (qⁿ;q²)²_n

=

n

X

j=1

n

X

j=1

| {z }

=:cn,j

n

X

j=1

a_n,jc_n,j

cn,n =

1

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

b_n

b_n bn−1

=

bn−1

(q²ⁿ;q)²_n (qⁿ;q²)²_n

=

n

X

j=1

n

X

j=1

| {z }

=:cn,j

n

X

j=1

a_n,jc_n,j

cn,n =

1

0 =

n

X

j=1

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

b_n

b_n bn−1

=

bn−1

(q²ⁿ;q)²_n

(qⁿ;q²)²_n =

n

X

j=1

n

X

j=1

| {z }

=:cn,j

n

X

j=1

a_n,jc_n,j

cn,n =

1

0 =

n

X

j=1

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 a_i,j and b_n6= 0. Show det (a_i,j)1≤i,j≤n=b_n. Method: “Pull out of the hat” a functioncn,j and prove

cn,n= 1 (n≥1),

n

X

j=1

c_n,ja_i,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 (a_i,j)1≤i,j≤m = 0 for somem???

Thenc_n,j is not uniquely deter- mined!

Proof is wrong!

No! Argue by induction onn.

(80)

Advocatus Diaboli

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

Thenc_n,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 coefficientf_n,k = ⁿ_k

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

(k+ 1)f_n,k+1 = (n−k)f_n,k f_0,0 = 1

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

k

q: (qⁿ⁺¹−q^k) ¯fn+1,k = (q^k+n+1−q^k) ¯fn,k

(q^2k+1−q^k) ¯f_n,k+1 = (qⁿ−q^k) ¯f_n,k f¯_0,0 = 1

All linear combinations of shifts are again valid recurrences: (n−k)f_n+1,k+1−(n+ 1)f_n,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 whyc_n,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 coefficientf_n,k = ⁿ_k

(k+ 1)f_n,k+1 = (n−k)f_n,k f_0,0 = 1

k

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

(83)

Holonomic systems

(k+ 1)f_n,k+1 = (n−k)f_n,k f_0,0 = 1

k

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

(84)

Holonomic systems

(k+ 1)f_n,k+1 = (n−k)f_n,k f_0,0 = 1

k

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

(85)

Holonomic systems

(k+ 1)f_n,k+1 = (n−k)f_n,k f_0,0 = 1

k

All linear combinations of shifts are again valid recurrences:

(n−k)f_n+1,k+1−(n+ 1)f_n,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 whyc_n,j should admit such a recursive description.

(86)

Holonomic systems

(k+ 1)f_n,k+1 = (n−k)f_n,k f_0,0 = 1

k

(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 whyc_n,j should admit such a recursive description.

(87)

Guessing

Manuel Kauers guessed some recurrences forcn,j.

Their Gr¨obner basis has the form

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

c_n+1,j+3 = c_n,j +c_n,j+1+c_n,j+2+c_n,j+3 +c_n+1,j+c_n+1,j+1+c_n+1,j+2 +c_n+2,j+c_n+2,j+1+c_n+3,j c_n+2,j+2 = c_n,j +c_n,j+1+c_n,j+2+c_n,j+3

+c_n+2,j+c_n+2,j+1

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

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

where eachis a polynomial inQ[q, q^j, qⁿ]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

c_n,j+4 = c_n,j +c_n,j₊₁+c_n,j+2+c_n,j₊₃ +c_n+2,j+c_n+2,j+1

c_n+1,j+3 = c_n,j +c_n,j₊₁+c_n,j+2+c_n,j₊₃ +c_n+1,j+c_n+1,j+1+c_n+1,j+2 +c_n+2,j+c_n+2,j+1+c_n+3,j c_n+2,j+2 = c_n,j +c_n,j₊₁+c_n,j+2+c_n,j₊₃

+c_n+2,j+c_n+2,j+1

c_n+3,j+1 = c_n,j +c_n,j₊₁+c_n,j+2+c_n,j₊₃ +cn+1,j+c_n+1,j+1+c_n+1,j+2 +c_n+2,j+c_n+2,j+1+c_n+3,j c_n+4,j = c_n,j +c_n,j₊₁+c_n,j+2+c_n,j₊₃

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

where eachis a polynomial inQ[q, q^j, qⁿ]of total degree≤100.

The staircase of the Gr¨obner basis:

(89)

Guessing

+c_n+2,j+c_n+2,j+1

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

where eachis a polynomial inQ[q, q^j, qⁿ]of total degree≤100.

The staircase of the Gr¨obner basis:

(90)

Guessing

+c_n+2,j+c_n+2,j+1

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

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

(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 description of c_n,j is correct, this wouldn’t prove anything yet!!!

Show:

cn,n = 1

n

X

j=1

c_n,ja_i,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 c_n,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, q^j, qⁿ].

• 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 c_n,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, q^j, qⁿ].

• 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, qⁿ)6= 0.

(97)

Advocatus Diaboli

The leading coefficient p7 could have singularities!!!

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

(98)

The third identity

Recall:

n

X

j=1

c_n,ja_n,j = b_n bn−1

with

ai,j =q^i+j−1

i+j−2 i−1

q

+q

i+j−1 i

q

!

+ (1 +qⁱ)δi,j−δ_i,j+1.

gives

(1 +qⁿ)−cn,n−1+

n

X

j=1

c⁰_n,j = bn

bn−1

with

c⁰_n,j =q^n+j−1

n+j−2 n−1

q

+q

n+j−1 n

q

! c_n,j

(99)

The third identity

How to prove (1 +qⁿ)−cn,n−1+

n

X

j=1

c⁰_n,j = bn

bn−1

?

• Compute an annihilating ideal for c⁰_n,j via closure properties.

• Find a relation in this ideal of the form

p_vc⁰_n+v,j+· · ·+p₁c⁰_n+1,j+p₀c⁰_n,j =t_n,j+1−t_n,j where thep_v, . . . , p₀ are rational functions inQ(q, qⁿ)andt_n,j is aQ(q, q^j, qⁿ)-linear combination of certain shifts of c⁰_n,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 +qⁿ)−cn,n−1+

n

X

j=1

c⁰_n,j = bn

bn−1

?

• Compute an annihilating ideal for c⁰_n,j via closure properties.

• Find a relation in this ideal of the form

p_vc⁰_n+v,j+· · ·+p₁c⁰_n+1,j+p₀c⁰_n,j =t_n,j+1−t_n,j where thep_v, . . . , p₀ are rational functions inQ(q, qⁿ)andt_n,j is aQ(q, q^j, qⁿ)-linear combination of certain shifts of c⁰_n,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

p_v(q, qⁿ)c⁰_n+v,j+· · ·+p₀(q, qⁿ)c⁰_n,j =t_n,j+1−t_n,j wheret_n,j =r₁(q, qⁿ, q^j)c⁰_n+3,j+2+· · ·+r₁₀(q, qⁿ, q^j)c⁰_n,j?

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

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.

Chyzak’s algorithm: ansatz with unknown p_i(q, qⁿ) and r_k(q, qⁿ, q^j). Leads to a coupled first-order parametrized linear system of q-difference equations.

Estimate: ∞?

CK’s polynomial ansatz: refine

r_k(q, qⁿ, q^j) =

L

X

l=0

r_k,l(q, qⁿ)(q^j)^l.

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

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

CK’s rational ansatz: ansatz with r_k(q, qⁿ, q^j) =

PL

l=0r_k,l(q, qⁿ)(q^j)^l dk(q, qⁿ, q^j)

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

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

(102)

A computational challenge

Estimate: ∞?

r_k(q, qⁿ, q^j) =

L

X

l=0

PL

(103)

A computational challenge

Estimate: ∞?

r_k(q, qⁿ, q^j) =

L

X

l=0

PL