Conference abstracts

Session B3 - Symbolic Analysis

July 15, 18:00 ~ 18:25 - Room B2

Algorithmic proof for the transcendence of D-finite power series

Alin Bostan

Inria, France   -

Given a sequence represented by a linear recurrence with polynomial coefficients and sufficiently many initial terms, a natural question is whether the transcendence of its generating function can be decided algorithmically. The question is non trivial even for sequences satisfying a recurrence of first order. An algorithm due to Michael Singer is sufficient, in principle, to answer the general case. However, this algorithm suffers from too high a complexity to be effective in practice. We will present a recent method that we have used to treat a non-trivial combinatorial example. It reduces the question of transcendence to a (structured) linear algebra problem.

View abstract PDF

FoCM 2017, based on a nodethirtythree design.