Abstract:
A power series is said to be D-finite (“differentially finite”) if it satisfies a linear differential equation with polynomial coefficients. D-finite power series are ubiquitous in combinatorics, number theory and mathematical physics. In his seminal article on D-finite functions [S1], Richard P. Stanley asked for “an algorithm suitable for computer implementation” to decide whether a given D-finite power series is algebraic or transcendental. Although Stanley insisted on the practical aspect of the targeted algorithm, at the time he formulated the problem it was unknown whether the task of recognizing algebraicity of D-finite functions is decidable even in theory. I will first report on such a decidability result. The corresponding algorithm has too high a complexity to be useful in practice. This is because it relies on the costly algorithm from [S2], which involves, among other things, factoring linear differential operators, solving huge polynomial systems and solving Abel’s problem. I will then present an answer to Stanley’s question based on “minimization” of linear differential equations, and illustrate it through examples coming from combinatorics and number theory. (Work in collaboration with Bruno Salvy and Michael F. Singer.)

[S1] R. P. Stanley, "Differentiably finite power series". European J. Combin. 1 (1980), no. 2, 175–188.
[S2] M. F. Singer, "Algebraic solutions of nth order linear differential equations". Proc. Queen’s Number Theory Conf. 1979, Queen's Papers in Pure and Appl. Math., 54 (1980), 379–420.