%cfac.tex: 
%%a Plain TeX file for an additional  section to ``Factorization of C-finite sequences''

%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\centerline
{\bf Extra Sections to Our paper}
\bigskip
\centerline
{\it Manuel KAUERS and Doron ZEILBERGER}

\bigskip


{\bf New Section: Tensor Product Without Factorization}

Sometimes our polynomials are with integer coefficients, and we prefer not to factorize them over the complex numbers. Of course, all
the roots are algebraic numbers, by definition, and computer-algebra systems know how to compute with them (without ``cheating'' and using
floating-point approximations), but it may be more convenient to find the tensor product (in the generic case) of
$$
A=\sum_{i=0}^{m} a_i x^i \quad ,
$$
and 
$$
B=\sum_{i=0}^{n} b_i x^i \quad ,
$$
a certain polynomial $R$ of degree $mn$ as follows.
If the roots of $A$ are $\alpha_i, \alpha_n$ and  the roots of $B$ are $\beta_i, \beta_m$ , then
the roots of $A \otimes B$ are, of course
$$
\{ \, \alpha_i \beta _j \, | \, 1 \leq i \leq m \, , \, 1 \leq j \leq n \, \} \quad.
$$
Let $p_r(A):=\sum_{i=1}^m \alpha_i^r$ be the {\it power-sum symmetric functions} ([Macdonald]), then of course
$$
p_r(AB)= p_r(A) p_r(B) \quad, \quad 1 \leq r \leq nm \quad .
$$
Now using {\it Newton's relations} (e.g. [Macdonald], Eq. I.(2.11') (p. 23)), one can go back and forth from
the elementary symmetric functions (essentially the coefficients of the polynomial up to sign) to the power-functions,
and {\it back}, enabling us easily to compute the tensor product without factorizing.


If you define the reverse of a polynomial $A(x)$, to be $A^{*}(x):=x^d A(1/x)$, where $d$ is the degree of $A$,
then  $A \otimes A^{*}(x)$ has, of course, the factor $(x-1)^d$ but otherwise (generically) all distinct roots,
unless it has good reasons not to.
On the other hand, if $C=A \otimes B$ for some non-trivial polynomials $A(x)$ and $B(x)$ then  $C \otimes C^{*}(x)$ has repeated roots,
and the {\it repetition profile} can be easily predicted as above, or ``experimentally''. So using
this approach it is easy to {\it test} quickly whether $C$ ``factorizes'', in the tensor-product sense.
However, to actually find the factors would take more effort.

This is implemented in the Maple package accompanying this article, linked to from

{\tt http://www.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/Cfac.html} \quad .

The tensor product operation is procedure {\tt Mul} and the testing procedure is {\tt TestFact}.

\vfill\eject

{\bf New Section: Mathematica Package}

Please briefly describe the Mathematica package that you wrote and put links to where to find it
(or refer to my page, where it is linked to)

{\bf References}

[Macdonald] Ian Macdonald, ``Symmetric Functions and Hall Polynomials'', second ed., Clarendon Press, Oxford, 1995.

\bigskip
\hrule
\bigskip


\end







