On deciding transcendence of power series

Abstract

It is well known that algebraic power series are differentially finite (D-finite): they satisfy linear differential equations with polynomial coefficients. The converse problem---determining whether a given D-finite power series is algebraic or transcendental---is notoriously difficult. We prove that this problem is decidable: we give two theoretical algorithms and a transcendence test that results in an efficient Maple implementation.

31 pages. To appear in L'Enseignement Mathématique