Computer Algebra 2006

PREFACE.

CONTENTS.

We consider hypergeometric sequences, i.e., the sequences which satisfy linear first-order homogeneous recurrence equations with relatively prime polynomial coefficients. Some results related to necessary and sufficient conditions are discussed for validity of discrete Newton-Leibniz formula when u(k) = R(k)t(k) and R(k) is a rational solution of Gosper's equation.

The following sections are included:

• Explicit Formulas vs. Algorithms

• The Holonomic Ansatz

• Why this Paper?

• The Maple packages AppsWZ and AppsWZmulti

• Asymptotics

• First Application: Rolling a Die

• Second Application: How many ways to have r people chip in to pay a bill of n cents

• Third Application: Hidden Markov Models

• Fourth Application: Lattice Paths Counting

• Fifth Application: Random Walk in Higher Dimensions

• References

We present a simple method for computing factorizations for a large class of matrix equations (matrix pseudo-linear equations) that includes, in particular, systems of linear differential, difference and q–difference equations. The approach is based on the characterization of the properties (reducibility, decomposability, etc.) of matrix pseudo-linear equations in terms of their eigenrings.

We give a modular algorithm to perform row reduction of a matrix of Ore polynomials with coefficients in ℤ[t]. Both the transformation matrix and the transformed matrix are computed. The algorithm can be used for finding the rank and left nullspace of such matrices. In the special case of shift polynomials, we obtain algorithms for computing a weak Popov form and for computing a greatest common right divisor (GCRD) and a least common left multiple (LCLM) of matrices of shift polynomials. Our algorithms improve on existing fraction-free algorithms and can be viewed as generalizations of the work of Li and Nemes on GCRDs and LCLMs of Ore polynomials. We define lucky homomorphisms, determine the appropriate normalization, as well as bound the number of homomorphic images required. Our algorithm is output-sensitive, such that the number of homomorphic images required depends on the size of the output. Furthermore, there is no need to verify the result by trial division or multiplication. When our algorithm is used to compute a GCRD and a LCLM of shift polynomials, we obtain a new output-sensitive modular algorithm.

This paper is based on a talk given at WWCA (Waterloo Workshop on Computer Algebra) held at Wilfird Laurier University, April 2006. This paper gives a history of beta-expansions, and surveys some of the computational aspects of beta-expansions. Special attention is given to how these beta-expansions relate to Pisot and Salem numbers. This paper also gives an overview of the computational issues that arose in the recent investigation of Allouche, Frougny and Hare,² upon which the talk at WWCA was based.

This article is devoted to the (one-dimensional) logarithmic functional with argument being one-dimensional cycle in the group (ℂ*)². This functional generalizes usual logarithm, that can be viewed as zero-dimensional logarithmic functional. Logarithmic functional inherits multiplicative property of the logarithm. It generalizes the functional introduced by Beilinson for topological proof of the Weil reciprocity law. Beilinson's proof is discussed in details in this article.

Logarithmic functional can be easily generalized for multidimensional case. It's multidimensional analog (see Ref. 6) proves multidimensional reciprocity laws of Parshin. I plan to return to this topic in upcoming publications.

We summarize some recent results on partial linear functional systems. By associating a finite-dimensional linear functional system to a Laurent–Ore module, Picard–Vessiot extensions are generalized from linear ordinary differential (difference) equations to finite-dimensional linear functional systems. A generalized Beke's method is also presented for factoring Laurent–Ore modules and it will allow us to find all "subsystems" whose solution spaces are contained in that of a given linear functional system.

The final step of some algebraic algorithms is to reconstruct the common denominator d of a collection of rational functions v_*/d from their polynomial images modulo m. Using elementwise rational reconstruction requires that deg m > N + D, where N and D are such that deg v_* ≤ N and deg d ≤ D. We present an algorithm, based on minimal approximant basis computation, that can perform the reconstruction for many problem instances even when the modulus has considerably smaller degree, for example deg m > N + D/k for k a small constant.

The differential equation for the product of Legendre polynomials provides a recursive algorithm for calculation succeeding multipole matrix elements with them. Non-multipole matrix elements as, for instance, particular Clebsh-Gordon coefficients also can be computed on the basis of this algorithm.

Considering an arbitrary family of hypergeometric polynomials {P_n} and a linear differential operator with polynomial coefficients L, we present an algorithm, based on the manipulation of hypergeometric families, that generates a recurrence relation for the coefficient sequence {c_n} satisfying L(∑c_nP_n(x)) = 0.

We describe a method of obtaining closed-form complete solutions of certain second-order linear partial differential equations with more than two independent variables. This method generalizes the classical method of Laplace transformations of second-order hyperbolic equations in the plane and is based on an idea given by Ulisse Dini in 1902.

We consider multivariate polynomials with exponents that are themselves integer-valued multivariate polynomials, and we present algorithms to compute their GCD and factorization. The algorithms fall into two families: algebraic extension methods and interpolation methods. The first family of algorithms uses the algebraic independence of x, xⁿ, xⁿ², x^nm, etc, to solve related problems with more indeterminates. Some subtlety is needed to avoid problems with fixed divisors of the exponent polynomials. The second family of algorithms uses evaluation and interpolation of the exponent polynomials. While these methods can run into unlucky evaluation points, in many cases they can be more appealing. Additionally, we also treat the case of symbolic exponents on rational coefficients (e.g. 4ⁿ²⁺ⁿ - 81) and show how to avoid integer factorization.

AUTHOR INDEX.