wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Polynomial and Prime Numbers
        
(Message started by: Barukh on Sep 17th, 2003, 12:07am)
Title: Polynomial and Prime Numbers
Post by Barukh on Sep 17th, 2003, 12:07am
Prove that there does not exist a polynomial P(x) with integer coefficients such that P(n) for every natural n is a prime number.
Title: Re: Polynomial and Prime Numbers
Post by towr on Sep 17th, 2003, 1:18am
P(x)=7
Title: Re: Polynomial and Prime Numbers
Post by Barukh on Sep 17th, 2003, 2:02am

on 09/17/03 at 01:18:21, towr wrote:
P(x)=7

Sorry, my fault: I forgot to add that the polynomial is not a constant.
Title: Re: Polynomial and Prime Numbers
Post by Sir Col on Sep 17th, 2003, 2:11am
Very sneaky, Towr; although I would add that the word polynomial, which means 'many terms', is a little inappropriate for a constant function.

I've not managed to complete the proof, but maybe someone can finish it...
::[hide]
Let P(x)=a0+a1x+a2x2+...+ anxn.

For a0=0, P(x)[equiv]0 mod x, so P(x) is composite for all composite x.

Otherwise, P(a0)[equiv]0 mod a0.

For |a0|>1, P(ka0) is divisible by |a0|.

However, for |a0|=1, special consideration is required...

* hmm? *

[/hide]::
Title: Re: Polynomial and Prime Numbers
Post by TenaliRaman on Sep 17th, 2003, 3:15am
::[hide]
suppose
P(x) = a0+a1x+a2x2+.....
is a polynomial such that for every x=n P(n) is prime

now suppose that for x=m,P(m)=p (a prime)
then,
p = a0+a1m+a2m2+.....

now set x = m+pq,
then P(m+pq) = a0+a1(m+pq)+a2(m+pq)2+.....
=a0+a1m+a2m2+..... + some multiple of p
=p + a multiple of p

CONTRADICTION!!
QED!!
[/hide]::
Title: Re: Polynomial and Prime Numbers
Post by towr on Sep 17th, 2003, 5:15am

on 09/17/03 at 02:11:39, Sir Col wrote:
However, for |a0|=1, special consideration is required.
P(0)=a0 = [pm]1 [ne] prime

[edit]Oh wait, that only holds if you count 0 as a natural number, and you don't.. And maybe Barukh doesn't either..
But you must admit in this case it makes live easier if you accept 0[in][bbn] :P[/edit]
Title: Re: Polynomial and Prime Numbers
Post by Sir Col on Sep 17th, 2003, 6:14am
You got me there, Towr!  :'(

Nice proof, TenaliRaman!  8)


Not that it's needed now, but out of interest, I wonder if it is possible to extend my method for the case, |a0|=1 (without admitting 0 as natural number)?
Title: Re: Polynomial and Prime Numbers
Post by Barukh on Sep 17th, 2003, 6:44am
TenaliRaman, I like your approach. The only thing remained is that [hide] some multiple of p is not 0[/hide]
Title: Re: Polynomial and Prime Numbers
Post by TenaliRaman on Sep 17th, 2003, 7:00am

on 09/17/03 at 06:44:06, Barukh wrote:
TenaliRaman, I like your approach. The only thing remained is that [hidden]


hmm let q belong to [bbn] and q [ne] 0
since m and p belong to [bbn]
m+pq belong to [bbn]

is the proof complete now?
Title: Re: Polynomial and Prime Numbers
Post by wowbagger on Sep 17th, 2003, 7:49am
Even though you already contributed quite a few posts (and not the least interesting ones), on the occasion of your becoming a member:
Welcome to the forum, Barukh! :)
Title: Re: Polynomial and Prime Numbers
Post by Sir Col on Sep 17th, 2003, 8:48am
May I echo wowbagger's words, and welcome you too, Barukh.

TenaliRaman, it seems that your proof is incomplete...  :(

From:
P(m+pq) = a0+a1(m+pq)+a2(m+pq)2+.....
=a0+a1m+a2m2+..... + some multiple of p
=p + a multiple of p

We cannot be sure that the multiple of p, kp[ne]0. That is, we must show that P(m+pq)=p+kp, where k[ne]0.
Title: Re: Polynomial and Prime Numbers
Post by Barukh on Sep 17th, 2003, 10:36am

on 09/17/03 at 07:49:24, wowbagger wrote:
Even though you already contributed quite a few posts (and not the least interesting ones), on the occasion of your becoming a member:
Welcome to the forum, Barukh! :)

Thank you very much, wowbagger, for the appreciation!


on 09/17/03 at 08:48:27, Sir Col wrote:
May I echo wowbagger's words, and welcome you too, Barukh.

TenaliRaman, it seems that your proof is incomplete...  :(

Sir Col, thank you very much too - for welcoming and for answering TenaliRaman - that's exactly what I meant.
Title: Re: Polynomial and Prime Numbers
Post by towr on Sep 17th, 2003, 11:08am

on 09/17/03 at 08:48:27, Sir Col wrote:
We cannot be sure that the multiple of p, kp[ne]0. That is, we must show that P(m+pq)=p+kp, where k[ne]0.
Supposing we don't have an infinite order polynomial, then since P(m+pq)=p+kp for every q [in] [bbn] with some k [in] [bbn], not all those k can be 0 since there are a limited number of extreme, and thus a limited number of times any one value can be reached.
Title: Re: Polynomial and Prime Numbers
Post by Sir Col on Sep 17th, 2003, 12:00pm
Nice! I was thinking of something similar, Towr; that is, for any finite degree polynomial there is a last turning point. Hence all values beyond that (either direction) will increase to negative or positive infinity, and after exceeding the value, p, never to return.


I would still like to prove that P(x) is not prime for all x, when |a0|=1. I know we have proved it indirectly by TenaliRaman's method, as the completion of the original problem also proves this result, but I would like to prove it directly. Does anyone have any ideas how it could be done?
Title: Re: Polynomial and Prime Numbers
Post by towr on Sep 17th, 2003, 12:54pm
Actually, I'm pretty sure the polynomial that could pass through a prime for all natural n would have to be infinite, and I don't see a reason to dismis it. You can define it as some sum from i=0 to [infty] and then some stuff I won't go into because I don't remember how to actually do it.

The thing is, I think you can define a(n infinite) polynomial that goes through a prime (even the same one) for all n, just not with integer coefficients, which is what you have to prove.
Title: Re: Polynomial and Prime Numbers
Post by James Fingas on Sep 17th, 2003, 1:10pm
Yeah. Without the integer coefficients part, you could just use the Taylor series for sin([pi]x)+2.
Title: Re: Polynomial and Prime Numbers
Post by Sir Col on Sep 17th, 2003, 3:21pm
Reading around it seems that this problem is by no means trivial. It took the might of Christian Goldbach, in 1752, to prove that no polynomial with integral coefficients exists that is able to generate primes for all integer values.
Title: Re: Polynomial and Prime Numbers
Post by TenaliRaman on Sep 18th, 2003, 7:13am
hmm interesting comments made but i will put out some points that i was thinking ,
first i always thought of P(x) to be a hurwitz polynomial (only difference being the coefficients restricted to integers)

some points as to why i was thinking like that,
1>the polynomial doesn't hit zero at any point in the positive plane (and i don't think it should).
2>the polynomial has to be strictly monotonically increasing

maybe i am making a mistake here somewhere or am i??
Title: Re: Polynomial and Prime Numbers
Post by towr on Sep 18th, 2003, 8:46am
The polynomial may flail wildly between its integer values. As long as P(n)=p , for r [notin] [bbn] P(r) can be -10000 , or any other value, nobody cares.

So it may hit 0, and may not be monotonicly increasing. Unless you have some convinving argument why it is not possible if you have integer coefficients and P(n)=p.
Title: Re: Polynomial and Prime Numbers
Post by Sir Col on Sep 18th, 2003, 9:14am
TenaliRaman, there is nothing to restrict the polynomial to positive coefficients. For example, n2–79n+1601, will generate primes for n=0,1,2,...,79.

Also, by insisting that P(x) is a strictly monotonically increasing polynomial, your proof fails to consider other polynomials, for which the only required restriction is that P(x)>0 for x[in][bbn]. And as Towr, pointed out, it is quite possible for P(x) to be negative for non-integer values of x, as long as P(x) is prime for the positive integer values of x.
Title: Re: Polynomial and Prime Numbers
Post by TenaliRaman on Sep 18th, 2003, 9:29am
i have no real convincing arguments actually but i cannot imagine how a polynomial which follows P(1)<P(2)<P(3)<.... can behave in a different way in the interval (n,n+1) unless otherwise explicitly defined.

(Blame my poor knowledge for this discussion.Hope u don't mind)

ok just after i wrote this post i realised the err in my thoughts!!(sheesh!! why do i always have to learn things after embarassing myself)
Title: Re: Polynomial and Prime Numbers
Post by Sir Col on Sep 18th, 2003, 1:33pm

on 09/18/03 at 09:29:34, TenaliRaman wrote:
why do i always have to learn things after embarassing myself

I don't believe there is any better way to learn. When I was a student in school, I was always the one who always put his hand up and tried to answer every question. Obviously I hoped I was right – and very occasionally I was ;) – but I can tell you now that the things I learned best, and I remember to this day, are the suggestions/answers I gave that were wrong. I'm sure you can see the number of times I've posted erroneous ideas on this forum, and if I could rewind time, I'd do it exactly the same.

However, it seems that some people, like most others on this forum, do seem to get it right first time. Oh well.   ::)
Title: Re: Polynomial and Prime Numbers
Post by James Fingas on Sep 18th, 2003, 1:37pm

on 09/18/03 at 09:29:34, TenaliRaman wrote:
i have no real convincing arguments actually but i cannot imagine how a polynomial which follows P(1)<P(2)<P(3)<.... can behave in a different way in the interval (n,n+1) unless otherwise explicitly defined.

(Blame my poor knowledge for this discussion.Hope u don't mind)

ok just after i wrote this post i realised the err in my thoughts!!(sheesh!! why do i always have to learn things after embarassing myself)


So why are you leaving any evidence around?  :D
Don't worry-you'll get quicker at modifying your posts!

Theoretical Question: If you modify your post before anyone reads it, was it ever wrong?
Title: Re: Polynomial and Prime Numbers
Post by Icarus on Sep 18th, 2003, 5:03pm

on 09/18/03 at 13:37:58, James Fingas wrote:
Theoretical Question: If you modify your post before anyone reads it, was it ever wrong?


As long as the post has that tattletale "Last edit:..." on it, everybody knows you goofed up somehow!

The real trick is when you can delete your erroneous post, then post the corrected version. Unfortunately you have to be quick, or else someone will reply to your bad post before you enter the correction - making the truth evident to all! :-[
Title: Re: Polynomial and Prime Numbers
Post by Barukh on Sep 18th, 2003, 11:18pm
Getting back to the puzzle...


on 09/17/03 at 12:54:24, towr wrote:
Actually, I'm pretty sure the polynomial that could pass through a prime for all natural n would have to be infinite, and I don't see a reason to dismis it. You can define it as some sum from i=0 to [infty] and then some stuff I won't go into because I don't remember how to actually do it.

That's very interesting! I would like to get a proof...

Also, let me propose a different, but related problem:

Find a (non-constant) polynomial P(x) with integer coefficients such that (n is an integer) if P(n) > 0, than P(n) is a prime. Define |P(x)| as the number of such n's. What is the maximal value of |P(x)|?

Of course, many examples may be given at once. It seems obvious that if the degree of the polynomial is finite, than it should be even. For instance, the polynomial P(x) = -2x2 + 61 satsifies the conditions of the problem, as it evaluates to prime numbers for n = -5...+5, so |P(x)| = 11.


on 09/18/03 at 09:14:24, Sir Col wrote:
...For example, n2–79n+1601, will generate primes for n=0,1,2,...,79.

This astounding example (which, I learnt, was discovered by L. Euler), unfortunately, does not satisfy the conditions...
Title: Re: Polynomial and Prime Numbers
Post by towr on Sep 19th, 2003, 1:03am

on 09/18/03 at 23:18:57, Barukh wrote:
That's very interesting! I would like to get a proof...
The proof is allready spread around in the thread.

TenaliRaman proved that for any prime p, and natural numbers m and q
P(m+pq) = p + k*p with some integer k
And I then proved that if P is finite k can't be 0 for all m and q, and thus P(m+pq) will at some point be a multiple of p (which by definition isn't a prime).

So, even without the restriction of integer coefficients, finite order polygons can't be prime for every n, but some infinite polygons can. And thanks to James, we allready have an example of such an infinite polynomial.
Title: Re: Polynomial and Prime Numbers
Post by Barukh on Sep 19th, 2003, 6:38am

on 09/19/03 at 01:03:57, towr wrote:
So, even without the restriction of integer coefficients, finite order polygons can't be prime for every n, but some infinite polygons can. And thanks to James, we allready have an example of such an infinite polynomial.

What I had in mind, is the proof that there exists/doesn't exist a polynomial of infinite degree with integer coefficients satsifying the conditions of the problem. The polynomial in James's example isn't with integer coefficients.
Title: Re: Polynomial and Prime Numbers
Post by Icarus on Sep 19th, 2003, 4:00pm
To be convergent for all natural numbers, a power series (sorry - I don't care for calling them "infinite polynomials") must have coefficients that converge to zero. The only way this can happen and still have all integer coefficients is for the coefficients to be eventually zero. I.e. for it to be a "finite" polynomial after all!
Title: Re: Polynomial and Prime Numbers
Post by TenaliRaman on Sep 20th, 2003, 4:39am
(Sorry for Replying Late!)
Thx Sir Col!!
i agree its the best way to learn but its no fun!(and i should know because when i get some answer right in these forum, its like i have achieved something really big and compare it with the times i get my answers wrong, the ratio is just around zero)

@James,
umm now why din't i think of that ??  ;D
Title: Re: Polynomial and Prime Numbers
Post by towr on Sep 20th, 2003, 4:42am

on 09/19/03 at 06:38:35, Barukh wrote:
What I had in mind, is the proof that there exists/doesn't exist a polynomial of infinite degree with integer coefficients satsifying the conditions of the problem. The polynomial in James's example isn't with integer coefficients.
Yes, I know, but I was content to first prove it had to be infinite if it could at all satisfy the criteria of being prime for all n.


on 09/19/03 at 16:00:42, Icarus wrote:
To be convergent for all natural numbers, a power series (sorry - I don't care for calling them "infinite polynomials") must have coefficients that converge to zero. The only way this can happen and still have all integer coefficients is for the coefficients to be eventually zero. I.e. for it to be a "finite" polynomial after all!
Does it need to be convergent? It seems to me the set of primes converges, as doers the set of natural numbers..
Or, more likely, do I simpyl not grasp what you mean with convergent in this context?
Title: Re: Polynomial and Prime Numbers
Post by Sir Col on Sep 20th, 2003, 5:26am
I think he meant that for any power series to be convergent:
P(x)=a0+a1x+a2x2+... (to infinity)

It is a necessary condition that as k[to][infty], ak[to]0.

Otherwise, its value, for any n, would be undefined. E.g. P(x)=1–2x+3x2–4x3+..., what would P(3) be?

Hence it cannot both be a convergent infinite series (for natural numbers) and contain integer coefficients in every term.
Title: Re: Polynomial and Prime Numbers
Post by Barukh on Sep 20th, 2003, 7:05am

on 09/19/03 at 16:00:42, Icarus wrote:
To be convergent for all natural numbers, a power series (sorry - I don't care for calling them "infinite polynomials") must have coefficients that converge to zero. The only way this can happen and still have all integer coefficients is for the coefficients to be eventually zero. I.e. for it to be a "finite" polynomial after all!

Beautiful argument, Icarus! And such simple...
Title: Re: Polynomial and Prime Numbers
Post by Icarus on Sep 20th, 2003, 5:50pm

on 09/20/03 at 04:42:24, towr wrote:
Does it need to be convergent? It seems to me the set of primes converges, as doers the set of natural numbers..
Or, more likely, do I simpyl not grasp what you mean with convergent in this context?


Actually I do not grasp what you could possibly mean by "convergent" in those sentences!

The set of primes converges? ??? The Natural Numbers converge? ??? To what? Infinity would work, but since we are stuck in the Real numbers here, that is called "divergence".

What I meant by convergence is: The sequence of partial sums has a finite limit. Does an infinite power series need to converge? Yes, if it is going to take on any values. Since this one is required to have values for every natural number, it's radius of convergence must be [infty].


on 09/20/03 at 07:05:53, Barukh wrote:
Beautiful argument, Icarus! And such simple...


What can I say? "Simple" is my specialty. The tough ones somebody else has to handle! :D
Title: Re: Polynomial and Prime Numbers
Post by towr on Sep 21st, 2003, 8:49am

on 09/20/03 at 17:50:11, Icarus wrote:
Actually I do not grasp what you could possibly mean by "convergent" in those sentences!
What I meant with converge was diverge, obviously :P (doesn't everyone?)


Quote:
What I meant by convergence is: The sequence of partial sums has a finite limit. Does an infinite power series need to converge? Yes, if it is going to take on any values. Since this one is required to have values for every natural number, it's radius of convergence must be [infty].
Makes sense now..
Title: Re: Polynomial and Prime Numbers
Post by ecoist on Mar 1st, 2006, 7:59pm
Did anyone notice that TenaliRaman's proof suggests that polynomials are very bad prime generators?

Given any nonconstant polynomial p(x) with integer coefficients and any positive integer n, there exists an integer x_n such that p(x_n) is divisible by at least n distinct primes.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board