Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

It seems like there is no polynomial with finite variables known, which could generate all prime numbers, by integer assignments. Is there a proof that such polynomial can not exist and does anyone have one in his/her stack?

share|improve this question
    
You might be interested in: mathworld.wolfram.com/Prime-GeneratingPolynomial.html –  Amzoti Sep 10 '12 at 22:28
2  
It is confusing to ask one question in the title and a different question in the body (in the body you don't specify what the coefficients should be). The body of the question should be self-contained (I usually don't go back up to the title to see if there's any extra information there and I'm sure I'm not the only one). –  Qiaochu Yuan Sep 11 '12 at 3:34
    
There is a polynomial $f(p,x_1,\ldots,x_n)$ with coefficients in $\mathbb Z$ such that $p$ is a positive prime number if an only if $\exists x_1\in\mathbb Z\ \cdots\ \exists x_n\in\mathbb Z\ f(p,x_1,\ldots,x_n)=0$. If I recall correctly it can be done with $\deg f=4$ and $n=14$. ${}\qquad{}$ –  Michael Hardy Aug 9 at 12:44

2 Answers 2

up vote 5 down vote accepted

In fact there does not even exist a non-constant polynomial $f$ (I assume you want integer coefficients) which only takes prime values with integer inputs. It suffices to prove this for polynomials in one variable. By the hypothesis that $f$ is non-constant, it takes arbitrarily large values, so without loss of generality $|f(0)| > 1$; in particular, $f(0)$ is divisible by some prime $p$. Then $f(kp)$ is always divisible by $p$, hence cannot be prime for sufficiently large $k$.

However, remarkably there do exist polynomials in more than one variable all of whose positive values are prime.

share|improve this answer
    
The question asked for rational coefficients, and the argument fails in this case. For example, $f(x)=(x^2+x+4)/2$ is integer-valued with rational coefficients, and $f(0)=2$ is divisible by the prime, 2, but $f(2)=5$ is not divisible by 2. –  Gerry Myerson Sep 11 '12 at 3:16
1  
@Gerry: oh, I see; rational is specified in the title. That's confusing. In any case, rational coefficients is not a problem: just ensure in addition that $k$ is divisible by the least common denominator of the coefficients. In your example, $f(4)$ is divisible by $2$. –  Qiaochu Yuan Sep 11 '12 at 3:33

An all prime-generating polynomial with rational coefficients can be built. The point the degree will be infinity, because each time we add a prime we increase the degree. I send you some examples for x>1

f:{2,3} for x>1

f(x)=x

f:{2,3,5} for x>1

f(x)=1/2 x^2-3/2x+3

f:{2,3,5,7} for x>1

f(x)= -1/6 x^3+2x^2-35/6 x+7

f:{2,3,5,7,11} for x>1

f(x)= 1/8 x^4- 23/12 x^3+87/8 x^2-301/12 x+22

f:{2,3,5,7,11,13} for x>1

f(x)=-3/40 x^5+13/8 x^4- 325/24 x^3+435/8 x^2-6203/60x+76

f:{2,3,5,7,11,13,17} for x>1

f(x)=23/720 x^6-15/16 x^5+1591/144 x^4-3203/48 x^3+78271/360x^2-2159/6x+237

f:{2,3,5,7,11,13,17,19} for x>1

f(x)=-53/5040 x^7+2/5 x^6-284/45x^5+427/8x^4-187541/720x^3+29249/40x^2-228523/210x+661

f:{2,3,5,7,11,13,17,19,23} for x>1

f(x)=23/8064x^8-457/3360x^7+7937/2280x^6- 3709/120x^5+241049/1152x^4-139643/160x^3+2444957/1120x^2-2504197/840x+1696

f:{2,3,5,7,11,13,17,19,23,29} for x>1

f(x)=-79/120960x^9+1537/40320x^8-2773/2880x^7+7939/576x^6-708043/5760x^5+ 4068679/5760x^4-39421933/15120x^3+3992225/672x^2-936341/120x+4066

share|improve this answer
    
Consider your answer to format properly in math mode for better readability. Also please refrain from adding "Best regards" and your name (it is posted automatically) at the end. –  pushpen.paul Aug 10 at 12:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.