On a Theorem by Van Vleck Regarding Sturm Sequences

In 1900 E. B. Van Vleck proposed a very efficient method to compute the Sturm sequence of a polynomial p (x) ∈ Z[x] by triangularizing one of Sylvester’s matrices of p (x) and its derivative p′(x). That method works fine only for the case of complete sequences provided no pivots take place. In 1917, A. J. Pell and R. L. Gordon pointed out this “weakness” in Van Vleck’s theorem, rectified it but did not extend his method, so that it also works in the cases of: (a) complete Sturm sequences with pivot, and (b) incomplete Sturm sequences. Despite its importance, the Pell-Gordon Theorem for polynomials in Q[x] has been totally forgotten and, to our knowledge, it is referenced by us for the first time in the literature. In this paper we go over Van Vleck’s theorem and method, modify slightly the formula of the Pell-Gordon Theorem and present a general triangularization method, called the VanVleck-Pell-Gordon method, that correctly computes in Z[x] polynomial Sturm sequences, both complete and incomplete.

Sturm Sequences and Modified Subresultant Polynomial Remainder Sequences

ACM Computing Classification System (1998): F.2.1, G.1.5, I.1.2.

On the Remainders Obtained in Finding the Greatest Common Divisor of Two Polynomials

In 1917 Pell (1) and Gordon used sylvester2, Sylvester’s little known and hardly ever used matrix of 1853, to compute(2) the coefficients of a Sturmian remainder — obtained in applying in Q[x], Sturm’s algorithm on two polynomials f, g ∈ Z[x] of degree n — in terms of the determinants (3) of the corresponding submatrices of sylvester2. Thus, they solved a problem that had eluded both J. J. Sylvester, in 1853, and E. B. Van Vleck, in 1900. (4) In this paper we extend the work by Pell and Gordon and show how to compute (2) the coefficients of an Euclidean remainder — obtained in finding in Q[x], the greatest common divisor of f, g ∈ Z[x] of degree n — in terms of the determinants (5) of the corresponding submatrices of sylvester1, Sylvester’s widely known and used matrix of 1840. (1) See the link http://en.wikipedia.org/wiki/Anna_Johnson_Pell_Wheeler for her biography (2) Both for complete and incomplete sequences, as defined in the sequel. (3) Also known as modified subresultants. (4) Using determinants Sylvester and Van Vleck were able to compute the coefficients of Sturmian remainders only for the case of complete sequences. (5) Also known as (proper) subresultants.