## Polynomial solutions of non-linear recurrence relations

Digital Security Group

Institute for Computing and Information Sciences

Radboud Universiteit Nijmegen

Tuesday, 9 June 2009, 14:00 (note the unusual weekday!)

Cybernetica Bldg (Akadeemia tee 21), room B101

Slides from the talk [pdf]

**Abstract**: In this talk we discuss non-linear recurrence
relations with polynomial solutions. Such recurrent relations arise,
for instance, in time and space complexity analysis of programs.

Contrary to linear recurrences, there is no general theory for
solving non-linear equations. We notice that if we look for a
polynomial solution and its possible degree is given, one can
straightforwardly find this solution if exists, or establish absence
of a polynomial solution of this degree, otherwise. We use the fact
that any polynomial is defined by a finite number of points.

Thus, the main problem is to find the degree of a possible
solution, given a recurrence. We study recurrences for which this
problem is decidable.

(Joint work with Marko van Eekelen, Alejandro Tamalet.)

Tarmo Uustalu

Last update 15.6.2009