Extra Sections to Our paper

Manuel KAUERS and Doron ZEILBERGER

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 computeralgebra 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 = ∑_{i=0}^{m} a_{i}x^{i} ,

and

B = ∑_{i=0}^{n} b_{i}x^{i} ,

a certain polynomial R of degree mn as follows. If the roots of A are α_{i}, α_{n} and the roots of B are β_{i}, β_{m} , then the roots of A ⊗ B are, of course

{ α_{i}β_{j} | 1 ≤ i ≤ m , 1 ≤ j ≤ n } .

Let p_{r}(A) := ∑_{i=1}^{m} α_{i}^{r} be the power-sum symmetric functions ([Macdonald]), then of course

p_{r}(AB) = p_{r}(A)p_{r}(B) , 1 ≤ r ≤ nm .

Now using 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 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 ⊗ 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 ⊗ B for some non-trivial polynomials A(x) and B(x) then C ⊗ C^{∗}(x) has repeated roots, and the repetition profile can be easily predicted as above, or “experimentally”. So using this approach it is easy to 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

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/Cfac.html .

The tensor product operation is procedure Mul and the testing procedure is TestFact.

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) References [Macdonald] Ian Macdonald, “Symmetric Functions and Hall Polynomials”, second ed., Clarendon Press, Oxford, 1995.