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
Doron Zeilberger's Home Page