How to tell if two random polynomials are identical - MathOverflow

How to tell if two random polynomials are identical

2010-09-23T12:14:20Z

Let t be a positive real number. Let P(x) and Q(x) be two random polynomials with integer coefficients. If P(t) = Q(t), then what is the probability that P(x) is not identical to Q(x)?

Will it make a difference if I restrict t to be an integer?

Suppose I had a set T ={t0,t1,…tk}, can we answer a similar question --- If P(ti) = Q(ti) for all ti in the set T, what is the probability that P is identical to Q? If k > max(deg(P), deg(Q)), the probability is 1. But can we say something about how many points we need to check before we can be fairly certain that the polynomials are identical?

Thanks

Answer by J. M. for How to tell if two random polynomials are identical

2010-09-23T12:20:39Z

Verifying if two black-box polynomials are identical is easy if you know that they have the same degree $n$; simply compute values at $n+1$ points, and if those $n+1$ values agree, they're identical.

Answer by Gerry Myerson for How to tell if two random polynomials are identical

2010-09-23T12:34:28Z

If $P$ and $Q$ are polynomials with integer coefficients, and $P(\pi)=Q(\pi)$, then $P$ and $Q$ are guaranteed identical.

Answer by Steve Huntsman for How to tell if two random polynomials are identical

2010-09-23T12:37:15Z

Use probabilistic identity testing. This is noteworthy for being one of the few problems known to be in BPP but not in P.

Answer by David Harris for How to tell if two random polynomials are identical

2010-09-23T13:26:21Z

If $t$ is chosen randomly in the reals, then with probability one $t$ is transcendental, so $P(t) = Q(t)$ iff $P = Q$. (This is just a generalization of the answer from Gerry Myerson)

Answer by Bill Thurston for How to tell if two random polynomials are identical

2010-09-23T13:27:51Z

The problem as stated is not well formulated; there are different ways it could be given a precise mathematical meaning, but then the main content of the question becomes the way in which it is made precise.

One thing missing is a specification of the probability measure, or a class of probability measures, for "random integer" and "random polynomial". Also implicitly missing, although not explicitly mentioned, is either a mathematical or a practical model of computation.

If you choose any particular probability distribution on polynomials with integer coefficients, then for any $\epsilon$ there are particular integers $m$ so that the probability of two of the polynomials agreeing at $m$ is less than $\epsilon$. As an example, if you consider any set of polynomials whose coefficients are chosen with any probability measure on integers between -1,000,000 to +1,000,000, then the value for $n = 2,000,001$ is definitive. This may not help you with your actual problem, because computing the value when $n = 2,000,000$ may involve computation with integers of greater than than machine precision, depending on the degree and the machine. If it's a polynomial of degree 10, it's probably better to compute its value on all integers between -5 and 5, rather than one integer of size 2000000; but there are many possible strategies for computation, and this gets into a different set of issues.

For a probability measure that does not have finite support, you can't usually determine identity of the polynomial with absolute certainty from value at a particular integer, but it can still be made as nearly certain as you like.

Similarly, the value on any real number chosen from a distribution with no atoms, or the value on a single known-to-be transcendental real, is definitive --- but computation up to machine precision might or might not tell you equality.

Answer by Tony Huynh for How to tell if two random polynomials are identical

2010-09-23T14:00:38Z

If the coefficients are non-negative then you can always do it with at most two integer evaluations.

That is, $P$ and $Q$ are equal if and only if

$P(1)=Q(1)$, and
$P(P(1)+1)=Q(Q(1)+1)$.

Update. If we allow for negative coefficients then this won't work. However, if in addition we are told that all coefficients $c$ satisfy $|c| \leq b$, then I believe we can do it with one integer evaluation. Namely, choose $n$ satisfying $n \geq 2b+1$. Then I think $P$ and $Q$ are equal if and only if

$P(n)=Q(n)$.

See my comments below for an explanation.

Answer by Nick S for How to tell if two random polynomials are identical

2010-09-23T16:53:08Z

Sorry can't add comments yet so I have to post this way. To comment on David's last post, one doesn't even have to go to transcendental numbers.

If $P-Q$ is not zero, it only has finitelly many roots, thus the probability for a random chosen real number to be a root of $P-Q$ is zero.