Alin Bostan

How to prove algorithmically

the transcendence of D-finite power series

Alin Bostan

^{SLC’79 Bertinoro} September 11, 2017

2 / 22

Algebraic and transcendental power series

In contrast with the “hard” theory of arithmetic transcendence, it is usually “easy” to establish transcendence of functions.

[Flajolet, Sedgewick, 2009]

.Definition: A power series finQ[[t]]is calledalgebraicif it is a root of some algebraic equationP(t,f(t)) =0, whereP(x,y)∈_Z[x,y]\ {0}.

Otherwise, fis calledtranscendental.

.Goal: Givenf ∈_Q[[t]], either in explicit form (by a formula), or in implicit form (by a functional equation), determine itsalgebraicityortranscendence.

Alin Bostan (Inria, France) How to prove algorithmically the transcendence of D-finite power series

Motivations

Number theory: first step towards proving the transcendence of a complex number is to prove that some power series is transcendental

Combinatorics: nature of generating functions may reveal strong underlying structures

Computer science: are algebraic power series (intrinsically) easier to manipulate?

4 / 22

An important particular case: transcendence of hypergeometric series

algebraic

hypergeom D-finite power series

f(t) =_∑^∞_n=0antⁿ∈_Q[[t]] is .algebraicifP t,f(t)=0for someP(x,y)∈_Z[x,y]\ {0}

.D-finiteifcr(t)f^(r)(t) +· · ·+c₀(t)f(t) =0for somec_i∈_Z[t], not all zero .hypergeometricif ^an+1_a

n ∈_Q(n). E.g., ln(1−t); ^arcsin(

√t)

√

t ;(1−t)^α,α∈_Q Theorem[Schwarz, 1873; Beukers, Heckman, 1989]

Characterization of{hypergeom} ∩ {algebraic} −→nice transcendence test

Alin Bostan (Inria, France) How to prove algorithmically the transcendence of D-finite power series

An important particular case: transcendence of hypergeometric series

algebraic

hypergeom D-finite power series

f(t) =_∑^∞_n=0antⁿ∈_Q[[t]] is .algebraicifP t,f(t)=0for someP(x,y)∈_Z[x,y]\ {0}

.D-finiteifcr(t)f^(r)(t) +· · ·+c₀(t)f(t) =0for somec_i∈_Z[t], not all zero .hypergeometricif ^an+1_a

n ∈_Q(n). E.g., ln(1−t); ^arcsin(

√t)

√

t ;(1−t)^α,α∈_Q Theorem[Schwarz, 1873; Beukers, Heckman, 1989]

Characterization of{hypergeom} ∩ {algebraic} −→nice transcendence test

4 / 22

An important particular case: transcendence of hypergeometric series

algebraic

hypergeom D-finite power series

f(t) =_∑^∞_n=0antⁿ∈_Q[[t]] is .algebraicifP t,f(t)=0for someP(x,y)∈_Z[x,y]\ {0}

.D-finiteifcr(t)f^(r)(t) +· · ·+c₀(t)f(t) =0for somec_i∈_Z[t], not all zero

.hypergeometricif ^an+1_a

n ∈_Q(n). E.g., ln(1−t); ^arcsin(

√t)

√

t ;(1−t)^α,α∈_Q Theorem[Schwarz, 1873; Beukers, Heckman, 1989]

Characterization of{hypergeom} ∩ {algebraic} −→nice transcendence test

Alin Bostan (Inria, France) How to prove algorithmically the transcendence of D-finite power series

An important particular case: transcendence of hypergeometric series

algebraic

hypergeom D-finite power series

f(t) =_∑^∞_n=0antⁿ∈_Q[[t]] is .algebraicifP t,f(t)=0for someP(x,y)∈_Z[x,y]\ {0}

.D-finiteifcr(t)f^(r)(t) +· · ·+c₀(t)f(t) =0for somec_i∈_Z[t], not all zero .hypergeometricif ^an+1_a

n ∈_Q(n). E.g., ln(1−t); ^arcsin(

√

√ t)

t ;(1−t)^α,α∈_Q

Theorem[Schwarz, 1873; Beukers, Heckman, 1989]

Characterization of{hypergeom} ∩ {algebraic} −→nice transcendence test

4 / 22

An important particular case: transcendence of hypergeometric series

algebraic

hypergeom D-finite power series

f(t) =_∑^∞_n=0antⁿ∈_Q[[t]] is .algebraicifP t,f(t)=0for someP(x,y)∈_Z[x,y]\ {0}

.D-finiteifcr(t)f^(r)(t) +· · ·+c₀(t)f(t) =0for somec_i∈_Z[t], not all zero .hypergeometricif ^an+1_a

n ∈_Q(n). E.g., ln(1−t); ^arcsin(

√

√ t)

t ;(1−t)^α,α∈_Q Theorem[Schwarz, 1873; Beukers, Heckman, 1989]

Characterization of{hypergeom} ∩ {algebraic} −→nice transcendence test

Alin Bostan (Inria, France) How to prove algorithmically the transcendence of D-finite power series

Stanley’s problem

Designan algorithm suitable for computer implementationswhich decides if a D-finite power series —represented by a linear differential equation with polynomial coefficients and suitable initial conditions—

is transcendental, or not.

[Stanley, 1980]

5 / 22

Stanley’s problem

Designan algorithm suitable for computer implementationswhich decides if a D-finite power series —represented by a linear differential equation with polynomial coefficients and suitable initial conditions—

is transcendental, or not.

[Stanley, 1980]

E.g.,

f =ln(1−t) =−t−^t

2

2 −^t

3

3 −^t

4

4 −^t

5

5 −^t

6

6 − · · · is D-finite and can be represented by the second-order equation

(t−1)∂²_t +∂t

(f) =0, f(0) =0,f⁰(0) =−1.

The algorithm should recognize thatf is transcendental.

Alin Bostan (Inria, France) How to prove algorithmically the transcendence of D-finite power series

Stanley’s problem

Designan algorithm suitable for computer implementationswhich decides if a D-finite power series —represented by a linear differential equation with polynomial coefficients and suitable initial conditions—

is transcendental, or not.

[Stanley, 1980]

.Notation: For a D-finite series f, we writeL^min_f for itsdifferential resolvent, i.e. the least order monic differential operator inQ(t)h∂tithat cancelsf.

5 / 22

Stanley’s problem

Designan algorithm suitable for computer implementationswhich decides if a D-finite power series —represented by a linear differential equation with polynomial coefficients and suitable initial conditions—

is transcendental, or not.

[Stanley, 1980]

.Notation: For a D-finite series f, we writeL^min_f for itsdifferential resolvent, i.e. the least order monic differential operator inQ(t)h∂tithat cancelsf. .Warning: L^min_f is not known a priori; only some multipleLof it is given.

Alin Bostan (Inria, France) How to prove algorithmically the transcendence of D-finite power series

Stanley’s problem

Designan algorithm suitable for computer implementationswhich decides if a D-finite power series —represented by a linear differential equation with polynomial coefficients and suitable initial conditions—

is transcendental, or not.

[Stanley, 1980]

.Notation: For a D-finite series f, we writeL^min_f for itsdifferential resolvent, i.e. the least order monic differential operator inQ(t)h∂_tithat cancelsf. .Warning: L^min_f is not known a priori; only some multipleLof it is given.

.Difficulty: L^min_f might not be irreducible. E.g.,L^min_ln(1−t)=∂t+_t−1¹ ∂t.

6 / 22

Three examples

(A) Apéry’s power series[Apéry, 1978](used in his proof ofζ(3)∈/_Q)

∑

∑

n k

2 n+k

k 2

tⁿ=1+5t+73t²+1445t³+33001t⁴+· · ·

(B) GF oftrident walks in the quarter plane

∑

antⁿ=1+2t+7t²+23t³+84t⁴+301t⁵+1127t⁶+· · ·, wherean=#

−walks of lengthninN²starting at(0, 0)

(C) GF of aquadrant model with repeated steps

∑

antⁿ=1+t+4t²+8t³+39t⁴+98t⁵+520t⁶+· · ·, wherean=#

−walks of lengthninN²from(0, 0)to(?, 0)

Question: How to prove that these three power series are transcendental?

Question: How to prove that these three power series are transcendental?

Question: How to prove that these three power series are transcendental?

Alin Bostan (Inria, France) How to prove algorithmically the transcendence of D-finite power series

Three examples

(A) Apéry’s power series[Apéry, 1978](used in his proof ofζ(3)∈/_Q)

∑

∑

n k

2 n+_k

k 2

tⁿ=1+5t+73t²+1445t³+33001t⁴+· · ·

(B) GF oftrident walks in the quarter plane

∑

antⁿ=1+2t+7t²+23t³+84t⁴+301t⁵+1127t⁶+· · ·, wherean=#

−walks of lengthninN²starting at(0, 0)

(C) GF of aquadrant model with repeated steps

∑

antⁿ=1+t+4t²+8t³+39t⁴+98t⁵+520t⁶+· · ·, wherean=#

−walks of lengthninN²from(0, 0)to(?, 0)

7 / 22

Main properties of algebraic series

If f=_∑nantⁿ∈_Q[[t]]is algebraic, then

• [Algebraic prop.]

f isD-finite;L^min_f has abasis of algebraic solutions [Abel, 1827; Tannery, 1875]

• [Arithmetic prop.]

f isglobally bounded [Eisenstein, 1852]

∃C∈_N^∗withanCⁿ∈_Zforn≥1

• [Analytic prop.]

(an)_nhas“nice” asymptotics [Puiseux, 1850; Flajolet, 1987]

Typically,an∼κ ρⁿn^αwithα∈_Q\_Z<0andρ∈_Qandκ·_Γ(α+1)∈_Q

Alin Bostan (Inria, France) How to prove algorithmically the transcendence of D-finite power series

. . . and resulting transcendence criteria

For f =_∑nantⁿ∈_Q[[t]], if one of the following holds

f isnot D-finite

∏

n

1 1−tⁿ

f isnot globally bounded

∑

n

1 ntⁿ

(an)_nhasincompatible asymptotics

∑

n

∑

n k

2

n+k k

2

t^n(†)

then fis transcendental

9 / 22

Singer’s algorithm (I)

Problem: Decide ifallsolutions of a given equationLof ordernare algebraic

•Starting point[Jordan, 1878]: If so, then for some solutionyofL,u=y⁰/y has alg. degree at most(49n)ⁿ²and satisfies a Riccati equation of ordern−1

Algorithm(Lirreducible)[Painlevé, 1887],[Boulanger, 1898],[Singer, 1979]

1 Decide if the Riccati equation has an algebraic solutionuof degree at most(49n)ⁿ² degree bounds + algebraic elimination

2 (Abel’s problem) Given an algebraicu, decide whethery⁰/y=uhas an algebraic solutiony [Risch 1970],[Baldassarri & Dwork 1979]

.[Singer, 1979]: generalization to any inputL −→requires ODE factoring .[Singer, 2014]: computation ofL^alg, the factor ofLwhose solution space is spanned by all algebraic solutions ofL −→requires ODE factoring

Alin Bostan (Inria, France) How to prove algorithmically the transcendence of D-finite power series

Singer’s algorithm (I)

Problem: Decide ifallsolutions of a given equationLof ordernare algebraic

•Starting point[Jordan, 1878]: If so, then for some solutionyofL,u=y⁰/y has alg. degree at most(49n)ⁿ²and satisfies a Riccati equation of ordern−1

Algorithm(Lirreducible)[Painlevé, 1887],[Boulanger, 1898],[Singer, 1979]

1 Decide if the Riccati equation has an algebraic solutionuof degree at most(49n)ⁿ² degree bounds + algebraic elimination

2 (Abel’s problem) Given an algebraicu, decide whethery⁰/y=uhas an algebraic solutiony [Risch 1970],[Baldassarri & Dwork 1979]

.[Singer, 1979]: generalization to any inputL −→requires ODE factoring

.[Singer, 2014]: computation ofL^alg, the factor ofLwhose solution space is spanned by all algebraic solutions ofL −→requires ODE factoring

9 / 22

Singer’s algorithm (I)

Problem: Decide ifallsolutions of a given equationLof ordernare algebraic

•Starting point[Jordan, 1878]: If so, then for some solutionyofL,u=y⁰/y has alg. degree at most(49n)ⁿ²and satisfies a Riccati equation of ordern−1

Algorithm(Lirreducible)[Painlevé, 1887],[Boulanger, 1898],[Singer, 1979]

1 Decide if the Riccati equation has an algebraic solutionuof degree at most(49n)ⁿ² degree bounds + algebraic elimination

2 (Abel’s problem) Given an algebraicu, decide whethery⁰/y=uhas an algebraic solutiony [Risch 1970],[Baldassarri & Dwork 1979]

.[Singer, 1979]: generalization to any inputL −→requires ODE factoring .[Singer, 2014]: computation ofL^alg, the factor ofLwhose solution space is spanned by all algebraic solutions ofL −→requires ODE factoring

Alin Bostan (Inria, France) How to prove algorithmically the transcendence of D-finite power series

Singer’s algorithm (II)

Problem: Decide if a D-finite power series f∈_Q[[t]], given by a differential equationL(f) =0 and sufficiently many initial terms, is transcendental.

1 ComputeL^alg [Singer, 2014]

2 Decide ifL^algannihilates f

.Benefit: Solves (in principle) Stanley’s problem.

.Drawbacks: Step 1 involvesimpractical bounds&requires ODE factorization .ODE factorization is effective

[Schlesinger, 1897],[Singer, 1981],[Grigoriev, 1990], [van Hoeij, 1997]

11 / 22

New method: the basic idea

Problem: Decide if a D-finite power series f∈_Q[[t]], given by a differential equationL(_f) =0 and sufficiently many initial terms, is transcendental.

Basic remark: IfL^min_f has a logarithmic singularity, then fis transcendental.

.Pros and cons:Avoids factorization ofL, but requires to computeL^min_f .

Alin Bostan (Inria, France) How to prove algorithmically the transcendence of D-finite power series

Ex. (A): Apéry’s power series

f(t) =

∑

n

antⁿ, wherean=

∑

n k

2 n+k

k 2

.Creative telescoping:

(n+1)³a_n−(2n+3)(17n²+51n+39)a_n+1+ (n+2)³a_n+2=0, a₀=1, a₁=5 .Conversionfrom recurrence to differential equationL(f) =0, where

L= (t⁴−34t³+t²)∂³_t + (6t³−153t²+3t)∂²_t + (7t²−112t+1)∂_t+t−5 .L^min_f = ¹

t⁴−34t³+t²L usingLirreducible, or cf. new algorithm .Basis of formal solutionsofL^min_f att=0:

n

1+5t+O(t²), ln(t) + (5 ln(t) +12)t+O(t²), ln(t)²+ (5 ln(t)²+24 ln(t))t+O(t²)^o

13 / 22

Ex. (B): D-Finite quadrant models

OEIS S nature ODE size OEIS S nature ODE size

1 A005566 T (3, 4) 13 A151275 T (5, 24)

2 A018224 T (3, 5) 14 A151314 T (5, 24)

3 A151312 T (3, 8) 15 A151255 T (4, 16)

4 A151331 T (3, 6) 16 A151287 T (5, 19)

5 A151266 T (5, 16) 17 A001006 A (2, 3)

6 A151307 T (5, 20) 18 A129400 A (2, 3)

7 A151291 T (5, 15) 19 A005558 T (3, 5)

8 A151326 T (5, 18)

9 A151302 T (5, 24) 20 A151265 A (4, 9)

10 A151329 T (5, 24) 21 A151278 A (4, 12)

11 A151261 T (4, 15) 22 A151323 A (2, 3)

12 A151297 T (5, 18) 23 A060900 A (3, 5)

.Computer-driven discovery and proof; no human proof yet

._{Proof uses}creative telescoping,ODE factorization,Singer’s algorithm .For models 5–10, asymptotics do not conclude. E.g. an∼ ⁴

3√ π

4ⁿ n^1/2

Alin Bostan (Inria, France) How to prove algorithmically the transcendence of D-finite power series

Ex. (B): D-Finite quadrant models

OEIS S nature asympt OEIS S nature asympt

1 A005566 T _π⁴⁴_nⁿ 13 A151275 T ¹²

√ 30 π

(2√ 6)ⁿ n²

2 A018224 T _π²⁴_nⁿ 14 A151314 T

√ 6λµC^5/2

5π (2C)ⁿ

n²

3 A151312 T

√ 6 π

6ⁿ

n 15 A151255 T ²⁴

√ 2 π

(2√ 2)ⁿ n²

4 A151331 T _3π^{8 8}_nⁿ 16 A151287 T ²

√ 2A^7/2

π (2A)ⁿ

n²

5 A151266 T ¹₂

q3 π

3ⁿ

n^1/2 17 A001006 A ³₂ q3

π 3ⁿ n^3/2

6 A151307 T ¹₂

q 5 2π 5ⁿ

n^1/2 18 A129400 A ³₂ q3

π 6ⁿ n^3/2

7 A151291 T ₃^√4

π 4ⁿ

n^1/2 19 A005558 T _π⁸⁴_nⁿ2

8 A151326 T ^√2

3π 6ⁿ n^1/2

9 A151302 T ¹₃

q 5 2π 5ⁿ

n^1/2 20 A151265 A ²

√ Γ(1/4)2 3ⁿ

n^3/4

10 A151329 T ¹₃

q 7 3π 7ⁿ

n^1/2 21 A151278 A ³

√

√ 3

2Γ(1/4) 3ⁿ n^3/4

11 A151261 T ¹²

√ 3 π

(2√ 3)ⁿ

n² 22 A151323 A

√ 23^3/4 Γ(1/4)

6ⁿ n^3/4

√ √

14 / 22

Ex. (C): two difficult quadrant models with repeated steps

Case A Case B

Theorem[B., Bousquet-Mélou, Kauers, Melczer, 2016]

GF is D-finite and transcendental in Case A.

GF is algebraic in Case B.

.Computer-driven discovery and proof; no human proof yet.

.Proof usesGuess’n’Proveandnew algorithm for transcendence.

.All other criteria and algorithms fail or do not terminate.

Alin Bostan (Inria, France) How to prove algorithmically the transcendence of D-finite power series

The new method: a first version

Input: f(_t)∈Q[[_t]], given as the generating function of a binomial sum Output:Tif f(t)is transcendental,Aif f(t)is algebraic

1 Compute an ODELfor f(t) Creative telescoping

2 ComputeL^min_f degree bounds + diff. Hermite-Padé

3 Decide ifL^min_f has only algebraic solutions; if so returnA, else returnT.

[Singer, 1979]

16 / 22

The new method: an efficient version

Input: f(t)∈_Q[[t]], given as the generating function of a binomial sum Output:Tif f(t)is transcendental,Aif f(t)is algebraic

1 Compute an ODELfor f(t) Creative telescoping

2 ComputeL^min_f degree bounds + diff. Hermite-Padé

3 IfL^min_f has a logarithmic singularity, returnT; otherwise returnA

.This algorithm is always correct when it returnsT;conjecturally, it is also always correct when it returnsA

._Usingp-curvatures and the Grothendieck-Katz conjecture (proved by [Katz, 1972]forPicard-Fuchs systems) yields anunconditionalalgorithm.

Alin Bostan (Inria, France) How to prove algorithmically the transcendence of D-finite power series

Central sub-task: computation of L

Problem: Given a D-finite power seriesf ∈_Q[[t]]by a differential equation L(f) =0 and sufficiently many initial terms, compute its resolventL^min_f .

.Why isn’t this easy? After all, it is just a differential analogue of:

Given an algebraic power series f ∈_Q[[t]]

by an algebraic equation P(t,f) =0and sufficiently many initial terms, compute its minimal polynomial P^min_f .

.L^min_f is a factor ofL, but contrary to the commutative case:

factorization of diff. operators is not unique ∂²_t = (∂t+_t−c¹ )(∂t−_t−c¹ ) . . . and it is difficult to compute

18 / 22

Central sub-task: computation of L

.Strategy(inspired by the approach in[van Hoeij, 1997], itself based on ideas from[Chudnovsky, 1980],[Bertrand & Beukers, 1982],[Ohtsuki, 1982])

1 L^min_f is Fuchsian, so it can be written

L^min_f =∂ⁿ_t +^an−1(t) A(t) ^∂

n−1

t +· · ·+ ^a0(t)

A(t)^{n, n}≤ord(L) withA(t)squarefree and deg(an−i)≤deg(Aⁱ)−i.

2 deg(A)can be bounded in terms ofnand (local) data ofL (viaapparent singularitiesandFuchs’ relation)

3 Guess and Prove: Forn=1, 2, . . . ,

1 Guess differential equation of ordernforf (use bounds and linear algebra)

2 Once found a nontrivial candidate, certify it, or go to previous step.

Alin Bostan (Inria, France) How to prove algorithmically the transcendence of D-finite power series

Ex. (C): a difficult quadrant model with repeated steps

Theorem[B., Bousquet-Mélou, Kauers, Melczer, 2016]

Letan=#

−walks of lengthninN²from(0, 0)to(?, 0)

. Then f(t) =_∑nantⁿ=1+t+4t²+8t³+39t⁴+98t⁵+· · · is transcendental.

19 / 22

Ex. (C): a difficult quadrant model with repeated steps

Theorem[B., Bousquet-Mélou, Kauers, Melczer, 2016]

Leta_n=#

−walks of lengthninN²from(0, 0)to(?, 0)

. Then f(t) =_∑nantⁿ=1+t+4t²+8t³+39t⁴+98t⁵+· · · is transcendental.

Proof:

1 Discover and certify a differential equationLfor f(t)of order 11 and

degree 73 high-tech Guess’n’Prove

2 If ord(L^min_f )≤10, then deg_t(L^min_f )≤580 apparent singularities

3 Rule out this possibility differential Hermite-Padé approximants

4 Thus,L^min_f =L

5 Lhas a log singularity att=0, and so fis transcendental

Alin Bostan (Inria, France) How to prove algorithmically the transcendence of D-finite power series

Ex. (C): a difficult quadrant model with repeated steps

Theorem[B., Bousquet-Mélou, Kauers, Melczer, 2016]

Leta_n=#

−walks of lengthninN²from(0, 0)to(?, 0)

. Then f(t) =_∑nantⁿ=1+t+4t²+8t³+39t⁴+98t⁵+· · · is transcendental.

Proof:

1 Discover and certify a differential equationLfor f(t)of order 11 and

degree 73 high-tech Guess’n’Prove

2 If ord(L^min_f )≤10, then deg_t(L^min_f )≤580 apparent singularities

3 Rule out this possibility [Beckermann, Labahn, 1994]

4 Thus,L^min_f =L

5 Lhas a log singularity att=0, and so fis transcendental

20 / 22

Conclusions

• Simple,efficientandrobustalgorithmic method for transcendence

• Central sub-task:computation ofL^min_f −→useful in other contexts!

• Basic theoretical tool:Fuchs’ relation

• Basic algorithmic tool:Guess’n’ProveviaHermite-Padé approximants+ efficient computer algebra

• Brute-force / naive algorithms =hopelesson combinatorial examples

Alin Bostan (Inria, France) How to prove algorithmically the transcendence of D-finite power series

Open problem

Find ahuman proof for the following statement

Theorem[B., Bousquet-Mélou, Kauers, Melczer, 2016]

Letan=#

−walks of lengthninN²from(0, 0)to(0, 0)

(an)_n≥0= (1, 0, 3, 0, 26, 0, 323, 0, 4830, 0, 80910, . . .) Then

a_2n= ⁶(6n+1)!(2n+1)! (3n)!(4n+3)!(n+1)!.

22 / 22

Thanks for your attention!

Alin Bostan (Inria, France) How to prove algorithmically the transcendence of D-finite power series