Let $P$ be a polynomial with integer coefficients. We say $P$ is good if there exist infinitely many prime numbers $q$ such that the set $$X=\left\{P(n) \mod q : \quad n\in \mathbb N\right\}$$has at least $\frac{q+1}{2}$ members. Prove that the polynomial $x^3+x$ is good.
Problem
Source: Iranian 3rd round 2016 first number theory exam
Tags: number theory, algebra, polynomial
15.08.2016 17:21
More stronger, there exists infinitely prime $p$ such that set $X$ has at least $\tfrac{2p-1}{3}$ elements. I will prove this stronger version. Note that for any $x \not\equiv y \pmod{p}$ then $x^3+x \equiv y^3+y \pmod{p} \iff p \mid x^2+xy+y^2+1$ or $p \mid (2y+x)^2+3x^2+4$. This means for each $x$: If $\left( \tfrac{-3x^2-4}{p} \right)=-1$ then there doesn't exist $y \not\equiv x$ such that $p \mid x^2+xy+y^2+1$ or $x^3+x \equiv y^3+y \pmod{p}$. If $\left( \tfrac{-3x^2-4}{p} \right)=1$ then there exists two values of $x_1 \not\equiv x_2 \not\equiv x$ such that $x^3+x \equiv x_1^3+x_1 \equiv x_2^3+x_2 \pmod{p}$. These three values are distinct if and only if $p \nmid 3x^2+4$ and $p \nmid x^2+1$. From this, we will pick $p$ such that $p \nmid 3x^2+4$ or $\left( \tfrac{-3}{p} \right)=-1$ or $p \equiv 5 \pmod{6}$ and $p \nmid x^2+1$ or $p \equiv 3 \pmod{4}$. Now, from this well-known lemma we find $$\sum_{i=1}^{p-1} \left( \frac{-3x^2-4}{p} \right)= - \left( \frac{-3}{p} \right)=1,$$which implies there are $\tfrac{p+1}{2}$ values of $x$ such that $-3x^2-4$ is quadratic residue modulo $p$ and $\tfrac{p-1}{2}$ values of $x$ such that $-3x^2-4$ is quadratic non-residue modulo $p$. Thus, for $p \equiv 11 \pmod{24}$, there are exactly $\frac{p-1}{2}+\frac 13 \cdot \frac{p+1}{2}=\frac{2p-1}{3}$ elements in set $X$.
10.01.2017 19:11
I will show that for $p\equiv_3 1$ we can achieve $\frac{q+3}{2}$ numbers in the set. As $3\mid p-1$ polynomial $X^3-1$ has exactly 3 roots in $\mathbb{F}_p$,namely let those be $1,\omega_1,\omega_2$ but we will be truly interested in last two.Lets determine the number of ordered pairs $(x,y)$ so that $x\not =y$.Notice that $x^3+x=y^3+y$ (we work in $\mathbb{F}_p$ from this point onwards) implies $x^2+xy+y^2=-1$ i.e: $$(x-\omega_1y)(x-\omega_2y)=-1$$Let $u:=x-\omega_1y,v:=x-\omega_2y$ which determines $y=\frac{u-v}{\omega_2-\omega_1},x=\frac{u\omega_2-v\omega_1}{\omega_2-\omega_1}$ where we don't have to worry for $\omega_2=\omega_1$ as $x^3-1$ has no double roots.So by previous if we select $u$ on $p-1$ ways $v$ is already determined which leads to $p-1$ pairs.However we counted: $(x,y)$ and $(y,x)$ as different pairs as well as $(x,x)$.First to deal with the $(x,x)$ thing,equation $3x^2=-1$ has two solutions as by our selection we have $\left(\frac{-3}{p}\right)=1$ so that settles it.As for the other point notice that the pair $(u',v')=\left(\frac{u(1-\omega_2\omega_1)-v(1-\omega^2_1)}{\omega_2-\omega_1},\frac{u(1-\omega^2_2)+v(\omega_2\omega_1-1)}{\omega_2-\omega_1}\right)$ maps the same pair $(x,y)$ and is bijectively mapped from $(u,v)$.Hence by everything above the number of solutions is $\frac{p-3}{2}$. Now form a graph where $G(V,E)$ where the vertices are elements are numbers from $\mathbb{F}_{p}$ and the edge between 2 numbers exists iff $P(x)=P(y)$.We're interested in number of connected components of $G$.At the beginning there are $p$ of the, adding an edge decreases the number of components by at most $1$.This implies that after adding $\frac{p-3}{2}$ edges the number of components is at least $\frac{p+3}{2}$.
13.04.2017 13:41
shinichiman wrote: $x_1 \not\equiv x_2 \not\equiv x$ such that $x^3+x \equiv x_1^3+x_1 \equiv x_2^3+x_2 \pmod{p}$. These three values are distinct if and only if $p \nmid 3x^2+4$ and $p \nmid x^2+1$. Why does $p \nmid x^2+1$ for them to be distinct?
13.04.2017 15:18
Achillys wrote: Why does $p \nmid x^2+1$ for them to be distinct? You are right. We don't need $p \nmid x^2+1$. Only $p \equiv 5 \pmod{6}$ is enough.
07.08.2020 13:30
let $q \equiv 11(mod {12}) $ a prime number .$ \rightarrow 3 \equiv a^2 (mod {q})$ $\forall b^2 \neq 0 , \exists x_{b^2}^2 \rightarrow$ $ 4a^2b^2 . x_{b^2}^2 \equiv (b^2-4)^2 (mod q) $ $\rightarrow 3x_{b^2}^2 \equiv Y^2 (mod q ) $ We want to count $x_{b^2}$ if $b^2 \not\equiv 4,0 (mod q ) $ we have two $x_{b^2}$ but we can see $x_{b^2} = x_{c^2} \leftrightarrow b^2.c^2 \equiv 16 (mod q) $ so at all we have $\frac{q-1}{2} $ distinct number $mod q$ such that $3x^2 +4 \equiv Y^2 (mod q )$ , name this $A$ . for every $ a \in A$ we can see that there is no $x$ such that $ a^3+a =x^3+x , x\neq a $ so with others we have at least one more answer , so we have at least $\frac{q+1}{2} $ answer $\blacksquare$
16.05.2022 18:42
shinichiman wrote: $$\sum_{i=1}^{p-1} \left( \frac{-3x^2-4}{p} \right)= - \left( \frac{-3}{p} \right)=1,$$which implies there are $\tfrac{p+1}{2}$ values of $x$ such that $-3x^2-4$ is quadratic residue modulo $p$ and $\tfrac{p-1}{2}$ values of $x$ such that $-3x^2-4$ is quadratic non-residue modulo $p$. Thus, for $p \equiv 11 \pmod{24}$, there are exactly $\frac{p-1}{2}+\frac 13 \cdot \frac{p+1}{2}=\frac{2p-1}{3}$ elements in set $X$. Sorry for reviving this post, but can anybody explain for me the reason why from the lemma, we have that and there are exactly ... elements?