How to tell if two random polynomials are identical - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T07:01:24Z http://mathoverflow.net/feeds/question/39733 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/39733/how-to-tell-if-two-random-polynomials-are-identical How to tell if two random polynomials are identical Balaji 2010-09-23T12:14:20Z 2010-09-24T14:24:41Z <p>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)?</p> <p>Will it make a difference if I restrict t to be an integer?</p> <p>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?</p> <p>Thanks</p> http://mathoverflow.net/questions/39733/how-to-tell-if-two-random-polynomials-are-identical/39734#39734 Answer by J. M. for How to tell if two random polynomials are identical J. M. 2010-09-23T12:20:39Z 2010-09-23T12:20:39Z <p>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.</p> http://mathoverflow.net/questions/39733/how-to-tell-if-two-random-polynomials-are-identical/39738#39738 Answer by Gerry Myerson for How to tell if two random polynomials are identical Gerry Myerson 2010-09-23T12:34:28Z 2010-09-23T12:34:28Z <p>If $P$ and $Q$ are polynomials with integer coefficients, and $P(\pi)=Q(\pi)$, then $P$ and $Q$ are guaranteed identical. </p> http://mathoverflow.net/questions/39733/how-to-tell-if-two-random-polynomials-are-identical/39739#39739 Answer by Steve Huntsman for How to tell if two random polynomials are identical Steve Huntsman 2010-09-23T12:37:15Z 2010-09-23T12:37:15Z <p>Use <a href="http://en.wikipedia.org/wiki/Schwartz-Zippel_lemma" rel="nofollow">probabilistic identity testing</a>. This is noteworthy for being one of the few problems known to be in <strong>BPP</strong> but not in <strong>P</strong>.</p> http://mathoverflow.net/questions/39733/how-to-tell-if-two-random-polynomials-are-identical/39746#39746 Answer by David Harris for How to tell if two random polynomials are identical David Harris 2010-09-23T13:26:21Z 2010-09-23T13:26:21Z <p>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)</p> http://mathoverflow.net/questions/39733/how-to-tell-if-two-random-polynomials-are-identical/39747#39747 Answer by Bill Thurston for How to tell if two random polynomials are identical Bill Thurston 2010-09-23T13:27:51Z 2010-09-23T13:45:00Z <p>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. </p> <p>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.</p> <p>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.</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/39733/how-to-tell-if-two-random-polynomials-are-identical/39752#39752 Answer by Tony Huynh for How to tell if two random polynomials are identical Tony Huynh 2010-09-23T14:00:38Z 2010-09-24T14:24:41Z <p>If the coefficients are non-negative then you can always do it with at most two integer evaluations.</p> <p>That is, $P$ and $Q$ are equal if and only if</p> <ol> <li>$P(1)=Q(1)$, and</li> <li>$P(P(1)+1)=Q(Q(1)+1)$.</li> </ol> <p><strong>Update.</strong> 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> <ol> <li>$P(n)=Q(n)$. </li> </ol> <p>See my comments below for an explanation.</p> http://mathoverflow.net/questions/39733/how-to-tell-if-two-random-polynomials-are-identical/39774#39774 Answer by Nick S for How to tell if two random polynomials are identical Nick S 2010-09-23T16:53:08Z 2010-09-23T16:53:08Z <p>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.</p> <p>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. </p>