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?

  • $\begingroup$ Is this a problem for somewhere or one of your own questions? It's an interesting question, but it seems rather hard to me. $\endgroup$ Sep 6 '15 at 18:50
  • $\begingroup$ 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{}$ $\endgroup$ 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.


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.


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.