Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: Factorization of C-finite Sequences
Speaker: Manuel Kauers, Johannes Kepler University, Linz, Austria
Date: Thursday, July 28, 2016 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We all know that the sum and the product of two C-finite sequences is again C-finite, and it is not hard to find recurrence equations for the sum or the product of two given C-finite sequences using linear algebra. Conversely, it is also not too difficult to decide whether a given C-finite sequence can be written nontrivially as a sum of two simpler C-finite sequences. This just requires the factorization of a univariate polynomial. In the talk, we will consider the analogous problem for the product: given a C-finite sequence, the task is to decide whether it can be written nontrivially as the product of two simpler C-finite sequences. An algorithm for solving this problem was first given by Ritt in the 1920s. We will present an alternative algorithm that is somewhat simpler and seemingly not less efficient than Ritt's approach, and we mention two applications to tiling problems and statistical mechanics. This is joint work with Doron Zeilberger.