range of a polynomial module prime nunbers

I guess for every polynomial $P(x)\in\mathbb{Z}[x]$ there are infinitely many prime numbers $p$ such that $$\#\{P(m) \bmod p : m\in\mathbb{Z}\}\ge\frac{p+1}{2}.$$

I prove this for monomials. But I have not any idea about general situation. Any idea?

• Is this a problem for somewhere or one of your own questions? It's an interesting question, but it seems rather hard to me. Sep 6 '15 at 18:50
• Please look at my first edit to the question. That's the way to do it. "b" stands for "binary" and indicates that the spacing should be what is appropriate for a binary operation symbol. \mod is designed for expressions like $\Big(p\equiv q\Big)\mod n$, meaning $p$ and $q$ both leave the same remainder on division by $n$. ${}\qquad{}$ Sep 6 '15 at 23:37

Consider the polynomial $$P(x)=x^4-5x^2+4=(x^2-1)(x^2-4)$$ We have that $P(-x)=P(x)$ for each $x$, and so modulo any prime $p$ we see that $P(x)$ takes at most $\frac{p+1}{2}$ values modulo $p$.

But $P(-1)=P(1)=P(-2)=P(2)=0$, and so we see that $P(x)$ actually only takes at most $\frac{p-1}{2}$ values modulo $p$ for any prime $p>3$.

So the conjecture is not true in general.

Edit

We could then, of course, ask if one can classify for which polynomials the conjecture is true. This seems like a very difficult problem and I do not have any ideas on how to approach it.

I can show the following results, however:

• If $P(x)$ satisfies the conjecture, then so does $aP(bx+c)+d$ for any integers $a,b,c$ and $d$ such that $ab \neq 0$.

This is fairly straightforward, since as long as $p$ does not divide $ab$, $ax+d$ and $bx+c$ both just permute the elements of $\mathbb{Z}_p$.

• $P(x)=x^n$ satisfies the conjecture for any $n\in\mathbb{N}^+$.

This is slightly less straightforward (as far as I can tell), and I will make use of the following results:

1. The Chinese Remainder Theorem
2. Dirichlet's Theorem on primes in arithmetic progressions
3. The existence of primitive roots modulo $p$ (i.e. that $\mathbb{Z}_p^*$ is cyclic)

For any $n$, we first show that there are infinitely many primes $p$ such that $\gcd(n, p-1)\leq 2$. If $n$ is odd then $\gcd(n, 2)=1$, and so by Dirichlet's Theorem, there are infinitely many primes $p$ such that $p \equiv 2 \mod n$. Then $p - 1 \equiv 1 \mod n$ and so $\gcd(n, p-1)=1$.

Now suppose that $n$ is even, and let $d$ be the largest odd divisor of $n$. Consider the following system of congruences:

\begin{align*} x \equiv 3 \mod 4\\ x \equiv 2 \mod d \end{align*}

By the Chinese Remainder Theorem, this has a unique solution $X$ modulo $4d$. Clearly $X$ and $4d$ are relatively prime, and so by Dirichlet's Theorem, there are infinitely many primes $p$ such that $p \equiv X \mod 4d$.

Such a prime $p$ has $p-1 \equiv 2 \mod 4$ and $p-1 \equiv 1 \mod d$, and so we see that $\gcd(n, p-1)=2$.

Now let $p$ be any prime such that $\gcd(n, p-1)\leq 2$ (we just showed that there are infinitely many), and let us consider the possible values of $x^n$ modulo $p$.

Let $g$ be a primitive root modulo $p$. Then any non-zero value of $x$ modulo $p$ can be written as $g^k$ for some $0 \leq k < p-1$, and so the non-zero values of $x^n$ modulo $p$ are precisely $g^{kn}$ for some $k$. Two such values will be equal iff $$g^{kn} \equiv g^{mn} \mod p$$ which is equivalent to $$g^{(k-m)n} \equiv 1 \mod p$$ or $$p-1\mid (k-m)n$$

Since $\gcd(n,p-1)\leq 2$, we see that this implies $$\frac{p-1}{2} \mid (k-m)$$

and so for any $k$, there can be at most one value $m\neq k$ such that $g^{kn} \equiv g^{mn} \mod p$ (Where $k$ and $m$ are each less than $p-1$)

We see that this implies that $x^n$ takes at least $\frac{p-1}{2}$ non-zero values modulo $p$. If we then include $0$, we see that $x^n$ takes at least $\frac{p+1}{2}$ values modulo $p$, and so $x^n$ satisfies the conjecture.

• Any linear polynomial and any quadratic polynomial satisfies the conjecture

This final observation is effectively just a combination of the previous $2$, but some more care is taken with the quadratic case.

For the linear case, if $P(x)=ax+b$, then for any prime $p$ such that $p$ does not divide $a$ (so any prime greater than $a$, for example) we have that $P(x)$ takes all $p$ possible values modulo $p$.

For the quadratic case, let $P(x)=ax^2+bx+c$. Let $p$ be any prime which does not divide $2a$. We can write $$P(x)=a\left(x+\frac{b}{2a}\right)^2+c-\frac{b^2}{4a^2}$$

Modulo $p$, this is equal to $$a(x+m)^2+n$$ where $m \equiv b(2a)^{-1} \mod p$ and $n \equiv c-b^2(2a)^{-2} \mod p$. $2a$ has an inverse modulo $p$ since $p$ does not divide $2a$.

But $x^2$ takes exactly $\frac{p+1}{2}$ values modulo $p$, and hence so does $(x+m)^2$, and hence also $a(x+m)^2+n$. This then implies that $P(x)$ also satisfies the conjecture.