3
$\begingroup$

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

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ This is not actually a mathematical question. There is no reasonable or accepted mathematical notion of what "random integer", or "random polynomial with integer coefficients" means. What is the probability that a random integer = 0, 1, 2, ... etc? Since there are infinitely many integers, the probability should be 0 --- but then there is 0 probability of anything. $\endgroup$
    – Bill Thurston
    Commented Sep 23, 2010 at 12:27
  • 3
    $\begingroup$ @Bill: I want to make a pedantic and narrow point: there are many reasonable notions of a random integer, all depending on a choice of finite measure. I think it is more fair to say that there is not an obvious choice of measure appropriate to the present context. $\endgroup$
    – Steve Huntsman
    Commented Sep 23, 2010 at 12:35
  • $\begingroup$ Also, suitably amended over finite fields (but I will not be the one to make the edit), the question has a nontrivial answer. $\endgroup$
    – Steve Huntsman
    Commented Sep 23, 2010 at 12:40
  • 2
    $\begingroup$ @Steve Huntsman: Perhaps I worded it too strongly. I'm aware how one can fix up the statement to make it mathematical, but it's too big a guessing game to try to guess what is intended. I'm used to hearing people talk about "random integers" without being aware there's a question what it means. I'll lay out a bit of how I see it in an actual answer. $\endgroup$
    – Bill Thurston
    Commented Sep 23, 2010 at 13:01
  • $\begingroup$ You shouldn't say "K > deg(P+Q)" as, if P(x) = x and Q(x) = -x, deg(P+Q) = 0 but checking 1 point (for example at x = 0) doesn't prove P = Q. You need "k > max{deg(P), deg(Q)}". $\endgroup$
    – Mark Bell
    Commented Sep 23, 2010 at 14:51

7 Answers 7

Reset to default
23
$\begingroup$

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

  1. $P(1)=Q(1)$, and
  2. $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

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

See my comments below for an explanation.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ Why does this work? $\endgroup$
    – Steve Huntsman
    Commented Sep 23, 2010 at 14:29
  • 8
    $\begingroup$ Note that $P(1)$ is just the sum of the coefficients of $P$. If the coefficients are all non-negative, then in particular they are all at most $P(1)$. So, if we express $P(P(1)+1)$ in base $P(1)+1$ we completely recover the coefficients of $P$. $\endgroup$
    – Tony Huynh
    Commented Sep 23, 2010 at 14:43
  • 2
    $\begingroup$ Consider the case when P(1) is a power of 10 to make it particularly transparent. $\endgroup$
    – JBL
    Commented Sep 23, 2010 at 14:57
  • 3
    $\begingroup$ Sure, instead of taking P(1)+1, we can let n be a power of 10 that is bigger than P(1). Then if we compute P(n), we can 'just read off' the coefficients of P. $\endgroup$
    – Tony Huynh
    Commented Sep 23, 2010 at 15:39
  • 1
    $\begingroup$ That's a cute fact! $\endgroup$
    – Nate Eldredge
    Commented Sep 23, 2010 at 18:14
17
$\begingroup$

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

Improve this answer
$\endgroup$
12
  • 4
    $\begingroup$ Hmm... this would probably require high precision if the degrees are large enough (pop quiz: how many digits of $\pi$ would be needed for a given degree $n$?). I'm afraid that even with the upvotes this answer received, this isn't very practical. $\endgroup$
    – J. M. isn't a mathematician
    Commented Sep 23, 2010 at 12:56
  • 4
    $\begingroup$ Yet another thing: if you end up having to use so many digits of $\pi$ for a "guaranteed-correct" check of this identity Gerry proposed, it may well be much slower than checking $n+1$ values in mere single-precision arithmetic. :P I guess this is the "disconnect between theory and practice" I have been hearing so much about. $\endgroup$
    – J. M. isn't a mathematician
    Commented Sep 23, 2010 at 13:26
  • 7
    $\begingroup$ @J.M. I think Gerry's main point is that the question is imprecise :-) $\endgroup$
    – Felipe Voloch
    Commented Sep 23, 2010 at 13:55
  • 3
    $\begingroup$ @qwerty1793: Indeed, any transcendental number. Since $P-Q$ is also a polynomial with integer coefficients, if $P-Q$ is not the zero polynomial, then any root $t$ of $P-Q$ is by definition algebraic. So if $P-Q$ has a transcendental root, then $P=Q$. $\endgroup$
    – Nate Eldredge
    Commented Sep 23, 2010 at 14:33
  • 2
    $\begingroup$ I accept all the critical comments, but Felipe has hit the nail on the head. You can't give a reasonable answer to an unreasonable question. All you can do is push the questioner to thinking about what question he/she really means to ask, so as to rule out the unreasonable answers. Bill Thurston has done well to sketch out some of the territory here, but in the end it's the questioner's job to give us a question that can be answered without mind-reading. $\endgroup$
    – Gerry Myerson
    Commented Sep 24, 2010 at 0:25
8
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ +1 for Bill; even without considering the coefficient distribution, unless you have some guarantee like all the signs of the coefficients being identical, computations with polynomials of high enough degree will be affected by subtractive cancellation. Personally I'd rather have $n+1$ reliable witnesses for cheap than one expensive witness. $\endgroup$
    – J. M. isn't a mathematician
    Commented Sep 23, 2010 at 13:32
  • $\begingroup$ I was supposing computation at an integer with integer arithmetic, so overflow rather than subtractive cancellation is the issue. But the computing environment might be one that handles large integers efficiently; calculating for one integer might be essentially equivalent to calculating mod several machine-size primes. There's too much under the surface about this to admit a good answer rather than an essay. $\endgroup$
    – Bill Thurston
    Commented Sep 23, 2010 at 13:53
  • $\begingroup$ @Bill Thurston: Thanks for your clarifying comments. $\endgroup$
    – Balaji
    Commented Sep 24, 2010 at 5:50
  • $\begingroup$ @Balaji: I appreciate your remark, which suggests that you accept the discussion in good spirit, not in the wrong way. I read your question as a genuine question about a topic where many people have fuzzy ideas. It is a good seed for the start of a discussion, even though it is not precisely formulated mathematics. When such a question is posed, it helps crystallize and clarify people's thoughts. I've been surprised how many diverse and interesting things people have had to say in response. Whether MathOverflow is not the place for discussion, as the FAQ states, is an independent issue. $\endgroup$
    – Bill Thurston
    Commented Sep 24, 2010 at 8:10
7
$\begingroup$

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.

Improve this answer
$\endgroup$
6
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks, but I am interested in knowing if we can evaluate the polynomials at fewer than n+1 points and conclude with high probability that they are identical. $\endgroup$
    – Balaji
    Commented Sep 23, 2010 at 12:27
  • $\begingroup$ @J.M. Technical point, actually all you need to know is that they both have degree at most $n$. $\endgroup$
    – Mark Bell
    Commented Sep 23, 2010 at 14:35
  • $\begingroup$ qwerty: Yes, it's a weaker condition than what I said; thanks for pointing it out. $\endgroup$
    – J. M. isn't a mathematician
    Commented Sep 23, 2010 at 14:51
2
$\begingroup$

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)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .