1
$\begingroup$

I know that no non-constant polynomial function $P(n)$ with integer coefficients exists that evaluates to a prime for every integer value of $n$.

My question is - does there exist a non-constant polynomial function $P(n)$ with integer coefficients that evaluates to either a prime or a semi-prime for every integer value of $n$?

More generally - does there exist a non-constant polynomial function $P(n)$ with integer coefficients such that for every integer value of $n$, the number of prime factors with multiplication of $P(n)$ is bounded?

I assume that the answer is no, but has this been proved?

Thanks

$\endgroup$

migrated from mathoverflow.net Feb 16 '15 at 23:18

This question came from our site for professional mathematicians.

  • 2
    $\begingroup$ Use the chinese remainder theorem. Voting to migrate to MSE. $\endgroup$ – Lucia Feb 16 '15 at 15:53
  • $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$ – bmurph Feb 16 '15 at 15:56
8
$\begingroup$

The answer is no.

Suppose $f(x)$ is a nonconstant integer-valued polynomial such that $\Omega(f(n))\le B$ for all integers $n$ (for some positive integer $B$). Then there is some $m$ such that $|f(m)|>1$ (else the polynomial is constant). Define $g(x)=f(x+m)$ so that $|g(0)|>1$ and note that $g(x)$ is a nonconstant integer-valued polynomial. Now let $p$ be a prime dividing $g(0)$ and define $h(x)=g(px)/p$. Note that $h(x)$ is a nonconstant integer-valued polynomial and $\Omega(h(n))\le B-1$ for all integers $n$. This creates an infinite descending chain, showing that no such $B$ can exist.

$\endgroup$
  • $\begingroup$ This works when one counts prime factors with multiplicity. What if the condition is weaker, and only counts distinct primes? $\endgroup$ – The Masked Avenger Feb 16 '15 at 21:16
  • $\begingroup$ @TheMaskedAvenger: I believe the proof can be extended to that case as well. Instead of looking for a case where $|f(m)|>1$ you look for $f(m)$ not $p_1,\ldots,p_k$-smooth. The smooth numbers grow too quickly to be a polynomial so such an $m$ exists. $\endgroup$ – Charles Feb 16 '15 at 21:53
  • $\begingroup$ Unfortunately, the condition is weaker than being smooth. You may be right, and I may misunderstand your approach, but my reading of your comment suggests that that approach also won't work. (If the range were to be restricted to finitely many prime divisors, I could see that approach working.) $\endgroup$ – The Masked Avenger Feb 16 '15 at 21:59
  • $\begingroup$ @TheMaskedAvenger: At the n-th step in my modified process, you've found an arithmetic progression of terms in the original polynomial which are divisible by $n$ distinct primes. To get to the (n+1)-th step it suffices to find a sub-progression divisible by a number > 1 relatively prime to the $n$ primes. If no such term existed then all terms in this polynomial would be products of those $n$ primes, but there aren't enough primes to let the sequence grow polynomially. $\endgroup$ – Charles Feb 16 '15 at 22:04
  • $\begingroup$ Ah, so you are talking about restricting the domain. I am not yet convinced, but my doubt has shrunk. Clearly I need to think more on this. Thanks. $\endgroup$ – The Masked Avenger Feb 16 '15 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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