This paper presents fast probabilistic algorithms for verifying polynomial identities and properties of systems of polynomials. The key idea is to use probabilistic methods to test whether a polynomial identity holds, based on the fact that a non-zero polynomial can have only a limited number of roots. The algorithms are designed to work with polynomials over integer coefficients and can be adapted for rational functions as well.
The paper introduces a probabilistic algorithm for testing whether a polynomial Q is identically zero. This algorithm involves selecting a set of values for the variables of Q and evaluating Q at these points. If Q is not identically zero, then it will not be zero at most of these points. The algorithm guarantees a certain probability of correctness, which can be increased by choosing more points.
The paper also discusses the use of modular arithmetic to test polynomial identities. By choosing a set of primes and evaluating the polynomial modulo these primes, the algorithm can determine whether the polynomial is identically zero with high probability.
The paper extends these techniques to rational functions and to the problem of determining whether one polynomial divides another. It also discusses the use of resultants and Sturm sequences for these purposes.
The paper concludes by showing how these probabilistic techniques can be used to verify theorems of elementary plane geometry. By expressing geometric theorems as algebraic identities, the probabilistic algorithms can be used to verify these theorems with high probability. The paper also discusses the use of these techniques for testing the compatibility of systems of polynomial equations and inequalities.This paper presents fast probabilistic algorithms for verifying polynomial identities and properties of systems of polynomials. The key idea is to use probabilistic methods to test whether a polynomial identity holds, based on the fact that a non-zero polynomial can have only a limited number of roots. The algorithms are designed to work with polynomials over integer coefficients and can be adapted for rational functions as well.
The paper introduces a probabilistic algorithm for testing whether a polynomial Q is identically zero. This algorithm involves selecting a set of values for the variables of Q and evaluating Q at these points. If Q is not identically zero, then it will not be zero at most of these points. The algorithm guarantees a certain probability of correctness, which can be increased by choosing more points.
The paper also discusses the use of modular arithmetic to test polynomial identities. By choosing a set of primes and evaluating the polynomial modulo these primes, the algorithm can determine whether the polynomial is identically zero with high probability.
The paper extends these techniques to rational functions and to the problem of determining whether one polynomial divides another. It also discusses the use of resultants and Sturm sequences for these purposes.
The paper concludes by showing how these probabilistic techniques can be used to verify theorems of elementary plane geometry. By expressing geometric theorems as algebraic identities, the probabilistic algorithms can be used to verify these theorems with high probability. The paper also discusses the use of these techniques for testing the compatibility of systems of polynomial equations and inequalities.