Factorization of C-finite Sequences

By
Manuel Kauers and Doron Zeilberger

.pdf

First Posted: Jan. 11, 2016; This version: Dec. 7, 2016.

Appeared in Advances in Computer Algebra, In Honour of Sergei Abramov's 70th Birthday, edited by C.Schneider, E.Zima, Springer.

Every fool can multiply two large integers, but only wise machines can factorize. Ditto for C-finite sequences. Here we develop an algoirthm that does factorization in the so-called C-finite ansatz, and that could have been useful to such physical giants as Lars Onsager and P.W. Kastleleyn. Who knows? Maybe it would be useful to a future physical giant?

Mathematica Package

• CFiniteMK.m, A Mathematica package (written by Manuel Kauers) implementing the algorithm in the article.

Maple Packages

• ALG.txt, A Maple package (written by Doron Zeilberger) that decides whether a polynomial is the tensor product of lower-degree polynomials

• For the examples to work, you also need the auxiliary file AlgDataFile.txt,

Some Input and Output files for the Maple package ALG.txt

• If you want to see proofs that the characteristic polynomials for the Dimer problem for a width-2i infinite strip (a certain polynomial of degree 2^i in x) is the i-fold tensor product of degree-2 polynomials
the input yields the output

• If you want to see proofs that the characteristic polynomials for the Ising problem for a width-i infinite strip (a certain polynomial of degree 2^i in x) has interesting repetition profile (it is not exactly the i-fold tensor product of degree-2 polynomials, due to dgeneracies explained in our paper) for i=2 to i=5,
the input yields the output

Doron Zeilberger's Articles Manuel Kauers Articles