Browse Prior Art Database

PROBABILISTIC ALGORITHMS FOR VERRIFICATION OF POLYNOMIAL IDENTITIES

IP.com Disclosure Number: IPCOM000128231D
Original Publication Date: 1978-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 29 page(s) / 66K

Publishing Venue

Software Patent Institute

Related People

JACOB T. SCHWARTZ: AUTHOR [+3]

Abstract

The startling success of the Rabin-S trassen-Solovay primality algorithm, together with the intriguing foundational possibility that axioms of randomness may constitute a useful foundamental source of mathematical truth independent of the standard axiomatic structure of mathematics,suggests a vigorous search for probabilistic algorithms" In illustration of this observation, we present various fast probabilistic algorithms, with probability of correctness guaranteed a priori, for testing polynomial identities and properties of systems of polynomials. Ancillary fast algorithms for calculating resultants and Sturm sequences are given. Probabilistic calculation in real arithmetic, previously considered by Davis, is justified rigorously, but only in a special case. Theorems of elementary geometry can be proved much more efficiently by the techniques presented than by any known artificial intelligence approach.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 29

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

PROBABILISTIC ALGORITHMS FOR VERRIFICATION OF POLYNOMIAL IDENTITIES

JACOB T. SCHWARTZ ,.

OCTOBER 1978

`REPORT NO. 004 `: Frobas)a3 istic Algorithms for Verification of Polynomial Identities

J. T. Schwartz Computer Science Department Courant Institute of Mathematical Sciences New York University 9

Abstract:

The startling success of the Rabin-S trassen-Solovay primality algorithm, together with the intriguing foundational possibility that axioms of randomness may constitute a useful foundamental source of mathematical truth independent of the standard axiomatic structure of mathematics,suggests a vigorous search for probabilistic algorithms" In illustration of this observation, we present various fast probabilistic algorithms, with probability of correctness guaranteed a priori, for testing polynomial identities and properties of systems of polynomials. Ancillary fast algorithms for calculating resultants and Sturm sequences are given. Probabilistic calculation in real arithmetic, previously considered by Davis, is justified rigorously, but only in a special case. Theorems of elementary geometry can be proved much more efficiently by the techniques presented than by any known artificial intelligence approach. PROBABILISTIC ALGORITHMS FOP VERIFICATION OF POLYNOMIAL

3. T. SCHWARTZ Computer Science Department Courant Institute of Mathematical Sciences * New York University '

1. Integer Probabilistic Calculations for Multivariate PolynoT,.iialE

The startling success of the Rabin-Strassen-Solovay algorithm (see Rabin [ 15 1), together with the intriguing foundational possibility that axioms of randomness may constitute a useful fundamental source of mathematical truth independent of but supplementary to the standard axiomatic structure of mathematics (see Chaitin and Schwartz [ 16 )), suggests that probabilistic algorithms ought to be sought for vigorously. As an illustration of what may be possible, this paper will present probah.iZistic algorithms for testing asserted multivariable polynomial identities Q = R, as well as other asserted or conjectured relationships between sets of polynomials, e.g. the assertion that one polynomial Q belongs to the ideal generated by finitely many others.

The technique that we use is essentially elementary. Given a purported polynomial identity, we can always write it as Q = O. We do not suppose that the Q presented to us for testing is given in standard simplified polynomial form. For example, if we did not immediately recognize its truth, we might wish to test the

New York University Page 1 Dec 31, 1978

Page 2 of 29

PROBABILISTIC ALGORITHMS FOR VERRIFICATION OF POLYNOMIAL IDENTITIES

(Equation Omitted)

. Indeed, if we write Q for the standard simplified form of Q, what we want iq precisely a test to determine whether all the coefficients of Q a_e zero. We allow our polynomials to have coefficients in any field or integral domain F. At som...