Prime counting function as ratio of polynomials.

Question

I came across this interesting question in an advanced Analytic number theory book

Prove that there are no polynomials $M(x)$ and $N(x)$ such that $\pi(x) = \frac{M(x)}{N(x)}$ for all $x = 1,2,3,\dots$

Suppose there are polynomials $M$ and $N$ such that $\pi(x) = M(x)/N(x)$ , since prime number theorem says that

$$\lim_{x \to \infty} \frac{\pi(x)\log(x)}{x} = 1.$$

Now using this and our previous assumed expression and by using elementary method to calculate limits, we can conclude following things about $M$ and $N$.

1. $M$ and $N$ have same degree.
2. $M$ and $N$ have same leading coefficient and obviously $N$ should divide $M$ for each $x$.

This would force me to conclude prime counting function is a constant polynomial since $M$ is multiple of $N$ and they have same degree which is a contradiction to infinitude of prime numbers.

Is this rigorous enough to solve the problem?

I observe here that we used prime number theorem which is very sophisticated tool and certainly non intuitive. Is there any method that doesn't use PNT to solve this problem?

Answer 1

It is elementary to prove that there are arbitrarily long stretches of consecutive composite numbers, e.g., $n!+2, n!+3,n!+4,\ldots,n!+n$ for any $n\ge2$. So if $\pi(x)=M(x)/N(x)$ for all positive integers $x$, with polynomials $M$ and $N$, and $\{k,k+1,k+2,\ldots,k+n\}$ is a prime-free stretch of numbers, then

$$N(k+x)\pi(k)-M(k+x)=0$$

for $x\in\{0,1,2,\ldots,n\}$. Now we cannot have $\pi(k)=M(k+x)/N(k+x)$ for all integers $x$; for example $M(k+(2-k))/N(k+(2-k))=M(2)/N(2)=\pi(2)=1\not=\pi(k)$ in general. Thus $N(k+x)\pi(k)-M(k+x)$ is a nonzero polynomial (in $x$) of degree at most $\max\{\deg(M),\deg(N)\}$. But if the length of our prime-free stretch, $n+1$, exceeds this degree, we have a contradiction.

Remark: This proof has little to do with the infinitude of primes; quite the opposite in fact. It really amounts to showing that any nonconstant rational function has an upper bound (given by the larger degree of its numerator and denominator) on the number of times it can assume any given value. The only relevant properties of the prime counting function that come into play are the fact that $\pi(x)$ is nonconstant but has no upper bound on the number of times it takes the same value (in particular, is constant over arbitrarily long stretches).

Answer 2

Yes. There is an easy way to do this.

Let $m$ and $n$ be the degree of $M$ and $N$. Then clearly $m \geq n$. Now we know that $\pi(x) < x $. So $\frac{M(x)}{N(x)} < x $ implies that $m \leq n + 1$.

So we must have $m = n$ or $m = n + 1$. If $m =n$ then as you pointed out we will have a contradiction. If $\pi(x)$ is linear polynomial then it is certainly not possible since $\pi(0) = 0$ implies that the constant term is $0$ and $\pi(2) = 1$ implies that the coefficient of $x$ is half which is certainly not possible.

More generally if $\pi(x)$ is some $p^{th}$ degree polynomial, since there are infinite number of primes certainly there will be more than $p+1$ number of linear equations in terms of coefficients of the polynomial and there will be no solution to this system of linear equations. So $\pi(x)$ cannot be represented by any polynomial.