We claim that \[ Q(x) = 420(x^2-1)^2 \]works. Clearly, it suffices to prove the result when $n=4$ and when $n$ is an odd prime $p$. The case $n=4$ is trivial, so assume now $n=p$ is an odd prime. First, we prove the following easy claim. Claim: For any odd prime $p$, there are at least $\frac12(p-3)$ values of $a$ for which $\left( \frac{1-a^2}{p} \right) = +1$. Proof: Note that if $k \neq 0$, $k \neq \pm 1$, $k^2 \neq -1$, then $a = 2(k+k^{-1})^{-1}$ works. Also $a=0$ works. $\square$ Let $F(x) = (x^2-1)^2$. The range of $F$ modulo $p$ is contained within the $\frac12(p+1)$ quadratic residues modulo $p$. On the other hand, if for some $t$ neither of $1 \pm t$ is a quadratic residue, then $t^2$ is omitted from the range of $F$ as well. Call such a value of $t$ \emph{useful}, and let $N$ be the number of useful residues. We aim to show $N \ge \frac14 p - 2$. We compute a lower bound on the number $N$ of useful $t$ by writing \begin{align*} N &= \frac{1}{4} \left( \sum_t \left[ \left(1 - \left(\frac{1-t}{p} \right) \right) \left(1 - \left(\frac{1+t}{p} \right) \right) \right] - \left( 1- \left( \frac2p \right) \right) - \left( 1- \left( \frac{-2}p \right) \right) \right) \\ &\ge \frac{1}{4} \sum_t \left[ \left(1 - \left(\frac{1-t}{p} \right) \right) \left(1 - \left(\frac{1+t}{p} \right) \right) \right] -1 \\ &= \frac{1}{4} \left(p + \sum_t \left(\frac{1-t^2}{p} \right) \right) -1 \\ &\ge \frac14 \left( p + (+1) \cdot \tfrac12(p-3) + 0 \cdot 2 + (-1) \cdot ( (p-2) - \tfrac12(p-3)) \right) - 1 \\ &\ge \frac14 \left( p - 5 \right). \end{align*} Thus, the range of $F$ has size at most \[ \frac12(p+1) - \frac12 N \le \frac38(p+3). \]This is less than $0.499p$ for any $p \ge 11$. In fact, the computation above is essentially an equality. There are only two points where terms are dropped: one, when $p \equiv 3 \pmod 4$ there are no $k^2 = -1$ in the lemma, and secondly, the terms $1-\left( 2/p \right)$ and $1-\left( -2/p \right)$ are dropped in the initial estimate for $N$. With suitable modifications, one can show that in fact, the range of $F$ is exactly equal to \[ \frac12(p+1) - \frac12 N = \begin{cases} \frac18(3p+5) & p \equiv 1 \pmod 8 \\ \frac18(3p+7) & p \equiv 3 \pmod 8 \\ \frac18(3p+9) & p \equiv 5 \pmod 8 \\ \frac18(3p+3) & p \equiv 7 \pmod 8. \end{cases} \]

I have essentially the same construction, but I wonder if this approach could be generalized to push the constant down to any $\epsilon > 0$?

We use the polynomial \[ 4\left(\prod_{p\le N} p\right)( x^4-x^2) \]for sufficiently large $N$. It's not hard to see that it suffices to show \[ |\{x^4-x^2|x \in \mathbb{F}_p\}|\le 0.499 p \]for sufficiently large $p$. Lemma: The number of solutions to $x^2+y^2=1$ in $\mathbb{F}_p^2$ is $p-\left(\frac{-1}{p}\right)$. Proof: First, suppose $p\equiv 1 \pmod{4}$. We factor $x^2+y^2=(x+iy)(x-iy)$, where $i\in \mathbb{F}_p$. If $m=x+iy$ and $\frac{1}{m}=x-iy$ for some $m\in \mathbb{F}_p^{\times}$. Then we can uniquely solve for $x,y$ as $x=\frac{1}{2}\left(m+\frac{1}{m}\right)$ and $y=\frac{1}{2i}\left(m-\frac{1}{m}\right)$, and there are exactly $p-1$ solutions corresponding to the $p-1$ values of $m$. Now suppose $p\equiv 3 \pmod{4}$. Again factor $x^2+y^2=(x+iy)(x-iy)$ in $\mathbb{F}_{p}[i]$. We consider again the parametrization $m=x+iy$ and $\frac{1}{m}=x-iy$ (where $m\in \mathbb{F}_{p}[i]$ now) and consider the conditions on $m$ required for $x=\frac{1}{2}\left(m+\frac{1}{m}\right)\in \mathbb{F}_p$ and $y=\frac{1}{2i}\left(m-\frac{1}{m}\right)\in \mathbb{F}_p$ to hold. Note that $\alpha \in \mathbb{F}_p$ iff $\alpha^p=\alpha$, and \[ x^p = \frac{1}{2} \left(m^p+\frac{1}{m^p}\right) \]and \[ y^p= \frac{1}{2i} \left(\frac{1}{m^p}-m^p\right) \]from the Frobenius Endomorphism and the fact that $i^p = i \cdot i^{p-1} = i\cdot \left(\frac{-1}{p}\right)=-i$. It's clear then that $x^p=x$ and $y^p=y$ hold simultaneously iff $m^{p+1}=1$. Since $t^{p+1}-1\mid t^{p^2}-t$, there are $p+1$ roots of $t^{p+1}-1$ in $\mathbb{F}_p[i]$, so there are exactly $p+1$ solutions to the equation in $\mathbb{F}_p$.

Now we consider the $G$ of quadratic residues $\pmod{p}$, interpreted as vertices of a graph. It suffices to show that $|\{g^2-g|g\in G\}|<0.499 p$ for large $p$. But the equivalence relation $g_1\sim g_2$ iff $g_1^2-g_1=g_2^2-g_2$ holds iff $g_1+g_2=1$ or $g_1=g_2$. There is at most one quadratic residue $g$ satisfying $g+g=1$, so there are at least $\frac{p-1}{8}-1$ unordered pairs of quadratic residues which are equivalent under $\sim$. (The factor of $\frac{1}{8}$ comes from the fact that up to $8$ ordered solutions $(\pm x, \pm y)$ and $(\pm y, \pm x)$ correspond to a single unordered pair $\{x^2,y^2\}$ of quadratic residues summing to $1$.) Since any quadratic residue is equivalent to at most one other, the at least $\frac{p-1}{8}-1$ edges partition $G$ into at most $|G|-\frac{p-1}{8}+1 = \frac{3}{8} p + \frac{13}{8}$ equivalence classes, which for large $p$ is less than $0.499p$. So we're done.

Here is another way to count solutions to $x^2 + y^2 = 1$ in $\mathbb{F}_p$. Clearly the number of solutions to $x^2 \equiv a$ is $1 + (\frac{a}{p})$. So the number of solutions to $x^2 + y^2 = 1$ is just $\sum_{a + b = 1} (1 + (\frac{a}{p})(1 + (\frac{b}{p})) = \sum_{x \in \mathbb{F}_p} 1 + \sum_{x \in \mathbb{F}_p} (\frac{x}{p}) + \sum_{x \in \mathbb{F}_p}(\frac{x}{p}) + \sum_{x \in \mathbb{F}_p} (\frac{x(1 - x)}{p})$. The first sum is obviously $p$, the middle two sums are zero because there are the same number of quadratic residues as non-residues, and in order to evaluate the last sum, we use the fact that for any nontrivial character $\chi$ on $\mathbb{F}_p$, the Jacobi sum of $\chi$ and $\chi ^{-1} = -\chi (-1)$. Because the quadratic character only takes on real values it is equal to its own inverse. So our sum is just $p - (\frac{-1}{p})$ which is $p + 1$ is $p$ is 3 mod 4 and is $p - 1$ is p is 1 mod 4. Note that this lack of solutions corresponds to two points at infinity on the projective line. For more details on Gauss and Jacobi sums which is where I got this information, see Ireland and Rosen chapter 8

To all the above posters , how did you get the motivation for constructing such a Q(X) polynomial . What prompted you all to decide that the answer to this problem is affirmative ? (Sorry if this is trivial )

Theorem 1.6 in this paper generalizes the construction: https://arxiv.org/pdf/1409.7160v1.pdf

I claim the polynomial $Q(x) = 264(2x^{2} -1)^{4}$ works. Observe that if this condition is true for $n$, then it is true for any multiple of $n$. Therefore, we just need to prove that this polynomial holds for $n = 4$ and primes $p$. If $n = 4$, then since $4 | 264$, the only residue is $0$. If $p\equiv 1\mod 4$, then since there are $\frac{p-1}{4} + 1$ values for $a^{4}\mod p$ (use primitive roots), we can conclude that this condition satisfies $p\equiv 1\mod 4$. Thus, we just need to prove that this works for $p\equiv 3\mod 4$. Observe that $Q(a)\equiv Q(-a) \mod p$ (since this is even). Now, I claim that there are at least $\frac{p-3}{2}$ values of $a$ such that $\genfrac{(}{)}{}{}{1-a^{2}}{p} = 1$. This is because we can take \[a = \frac{k + \frac{1}{k}}{2}, k\neq 0\]and for each value of $k$, only $\frac{1}{k}$ exists such that it results in the same $a$ (but we can't have $a = \pm 1$ or else $\genfrac{(}{)}{}{}{1-a^{2}}{p} = 0$). This means there exists at least $\frac{p-3}{4}$ values of $a^{2}$ such that $1 - a^{2} = b^{2}$, or $2a^{2} -1 = -2b^{2} + 1$, where $a\not\equiv b, -b \mod p$, so there exists at least $\frac{p-3}{8}$ "groups" of $(a, -a, -b, b)$ such that $Q(a) \equiv Q(-a) \equiv Q(b) \equiv Q(-b)\mod p$. There are at most $\frac{p+3}{2}$ numbers remaining, of which they can output $\frac{p+3}{4}$ different values when plugged into $Q$ (since $Q(x)\equiv Q(-x)$). Therefore, if we let $k$ be the total number of groups of $(a, -a, -b, b)$, then we have the total number of output of $Q\mod p$ is \[k + \frac{p-4k}{2} = \frac{p}{2} - k \leq \frac{p}{2} - \frac{p-3}{8} \leq \frac{3p + 3}{8}\]For all $p\geq 7$, this value is less than or equal to $0.499p$. For $p = 3$, since $3 | 264$, the only residue is $0$. Thus, this polynomial holds for all primes $p$ and $n = 4$, and thus satisfies for all integers.

Solved with rama1728. Related to 2020 USAMO P3! If $n$ works, any multiple of $n$ works. It suffices to prove all large enough odd primes $p$ work for some $Q(x).$ Then just multiply $Q(x)$ by the finitely many primes (and $4$) left that haven't been dealt with. Take congruences $\pmod{p}.$ Let $Q(x) = (x^2-2)^2,$ so $Q(x)\equiv Q(y)$ if $x \equiv \pm y$ and/or $x^2+y^2 \equiv 4.$ So the range of $Q$ is at most $$\frac{p+1}{2} - \frac{1}{2}(|B \setminus 2|) \approx \frac{p}{2} - \frac{1}{2}|B|$$where $B$ is the set of residues $a$ where $a, 4-a$ are both QRs not congruent to $0$ or $4$. By 2020 USAMO P3 lemma, $|B| = \frac{|X|-1}{2}$ where $X$ is the set of residues $a$ where $a(4-a)$ is a QR and neither $a$ nor $4-a$ are congruent to $0$ or $4.$ Taking $a = \frac{4}{k+1}$ for any quadratic residue $k \ne 0, 1,-1$ yields $a(4-a) \equiv \frac{16k}{(k+1)^2}$ which is a QR. Thus $$|B| = \frac{|X|-1}{2} \ge \frac{\frac{p+1}{2} - 3-1}{2} \approx \frac{p}{4}$$and the range of $Q$ is at most about $$\frac{p}{2} - \frac{1}{2}|B| \approx \frac{3}{8}p,$$give or take a fixed constant. Since $\frac{3}{8} < 0.499,$ this is enough. $\blacksquare$

The key is that the polynomial $(X^2-1)^2$ basically works, tagged on with some constant to get rid of annoying small primes. For obvious reasons it suffices to solve the problem for sufficiently large $p$. Note that the number of residues that $(X^2-1)^2$ hits is equal to $\frac{p+1}2$ minus $|S|$, where $$S = \left\{y \mid \left(\frac{1+y}p\right) = -1 \text{ or } \left(\frac{1-y}p\right) = -1, 0 \leq y \leq p-1\right\}.$$This can be computed artificially as $$|S| = \frac 14 \sum_{y=2}^{p-2} \left(1-\left(\frac{1+y}p\right)\right)\left(1-\left(\frac{1-y}p\right)\right) = \frac 14\left(p-3-\sum_{y=2}^{p-2} \left(\left(\frac{1-y}p\right)+\left(\frac{1+y}p\right) - \left(\frac{1-y^2}p\right)\right)\right).$$Using some well-known Jacobi identities we obtain $$|S| = \frac 14\left(p-2+2\left(\frac 2p\right) + (-1)^{(p+1)/2}\right) \geq \frac{p-5}4,$$so the number of residues is at most $\frac{p+1}2 - \frac{p-5}8 \leq 0.499p$ for sufficiently large $p$.

We claim that $Q(X)=C(X^2-1)^2$ works for sufficiently large $C$. It suffices to prove the desired result for large primes $p$. Now we find the size $N$ of the range of $P(X)=(X^2-1)^2$ over $\mathbb{F}_p$. It is well-known that there are $\frac{1}{2}(p+1)$ quadratic residues (mod $p$), so $N \le \frac{1}{2}(p+1)$. Let $S$ be the set of quadratic residues (mod $p$) that are not in the range of $P(X)$. We can quickly compute $S$ to be $$|S| = \frac 14 \sum_{t=2}^{p-2} \left[ \left(1-\left(\frac{1+t}p\right)\right)\left(1-\left(\frac{1-t}p\right)\right) \right] = \frac{p-3}{4} - \sum_{t=2}^{p-2} \left[\left(\frac{1-t}p\right)+\left(\frac{1+t}p\right) - \left(\frac{1-t^2}p\right)\right] = \frac 14\left(p-2+2\left(\frac 2p\right) + (-1)^{(p+1)/2}\right). $$In particular, $|S| \ge \frac{p-5}{4}$, so $N\le \frac{p+1}2 - \frac{p-5}8 \le 0.499p$ for primes $p>7$, as desired.

Take $Q(x)=(x^2-1)^2$. First notice that if we prove it for all primes then we have proven it for all $n$ because of CRT. It's enough to prove it for sufficiently large primes because if it holds for $p_n$ for $n>N$ we can take $Q\mapsto Q\cdot \prod_{p\le N}p$ and it clearly holds for $p_n$ with $n\le N$ (this preserves the fact that it works for $p_n$ with $n>N$). Let $p$ be a sufficiently large prime. Work in $\mathbb{F}_p$. Construct a graph with vertices $0,1,2,\cdots,p-1$. We draw an edge between vertices $i$ and $j$ if $Q(i)=Q(j)$. The idea is that the graph will be composed of $N$ disjoint cliques. Each of these produces a unique value in the range of $Q$ so we wish to show that $N<0.499p$. Notice that there is an edge between $i,j$ if $i=-j$ or if $i^2-1=1-j^2\iff i^2+j^2=2$. Suppose there are $n$ pairs $(i,j)$ with $i^2+j^2=2$. To join two $K_2$ into a $K_4$ we need $4$ pairs. If we show $n$ is roughly $p$ then $N$ is roughly $3/8p$ which is enough. The following lemma finishes the proof: Lemma: The number of solutions to $x^2+y^2=2$ in $\mathbb{F}_p$ is $p+O(1)$. Proof: Omitted because AoPS is too slow to render it. The idea is to note the number of solutions to $x^2=a$ is $1+\left(\frac{a}{p}\right)$ and then express in two ways the number of solutions to $x^2-y^2=a$ (one with difference of squares, the other in terms of the Legendre Symbol). This identity can be used to find the number of solutions to $x^2+y^2=-a$.

Let $N$ be the product of the primes less than $1000$ and take the polynomial $Q(x)=2N(x^4+1)^2$. It suffices to prove the result for $n=4$ and when $n=p$ is an odd prime, the former of which is trivial. Now consider the case where $n$ is an odd prime $p>1000$. If $p \equiv 1 \pmod{4}$, then $x^4$ attains $\tfrac{p-1}{4}+1$ residues modulo $n$, hence $Q(x)$ clearly attains at most $0.499p$ residues. Henceforth assume $p \equiv 3 \pmod{4}$, so quadratic and quartic residues are the same thing; therefore, we will analyze the behavior of the polynomial $P(x)=(x+1)^2$ when we plug in one of the $\tfrac{p+1}{2}$ quadratic residues in $\mathbb{F}_p$. Note that this polynomial is never zero, since $(\tfrac{-1}{p})=-1$. Therefore, separate the nonzero residues mod $p$ into $\tfrac{p-1}{2}$ equivalence classes based on the value of their square (so $a$ and $-a$ are paired). The range of $P$ as $x$ ranges across QRs is then the number of equivalence classes $x+1$ hits, which is $\tfrac{p+1}{2}$ minus the number of "collisions" that occur where $x+1$ and $y+1$ are part of the same residue class for different QRs $x$ and $y$, i.e. $x+1=-(y+1) \iff x+y=-2$. We have the following lemmas. Lemma 1: The equation $x^2-y^2=1$ in $\mathbb{F}_p$ has exactly $p-1$ solutions. Proof: Write the equation as $(x-y)(x+y)=1$. Then the solutions in $x$ are precisely given by the range of $\tfrac{a+a^{-1}}{2}$ as $a$ ranges across the nonzero residues modulo $p$, since these correspond to having $x-y=a$ and $x+y=a^{-1}$. Observe that if $a \neq b$, then $$a+\frac{1}{a}=b+\frac{1}{b} \implies (ab-1)(a-b)=0 \implies b=\frac{1}{a}.$$Therefore, every nonzero element of $\mathbb{F}_p$ can be paired with its inverse, and each pair corresponds to a unique value of $\tfrac{a+a^{-1}}{2}$. Since $1$ and $-1$ are paired with themselves, it follows that there are $\tfrac{p-3}{2}+2=\tfrac{p+1}{2}$ pairs, hence $\tfrac{p+1}{2}$ solutions in $x$. Each solution in $x$ corresponds to two solutions in $y$, except those where $x^2=1 \iff y^2=0$, of which there are two. Thus, $\tfrac{p-3}{2}$ of the solutions in $x$ correspond to two solutions in $y$, and the other two correspond to a unique solution in $y$, hence we have a total of $p-1$ solutions. $\blacksquare$ Lemma 2: The equation $x^2+y^2=-2$ in $\mathbb{F}_p$ has either $p-3$ or $p+1$ solutions in nonzero $x$ and $y$ (where $p \equiv 3 \pmod{4}$). Proof: Substitute $y=ax$ where $a \neq 0$, so we want to solve $x^2=\tfrac{-2}{a^2+1}$. The number of solutions $(x,a)$ to this equation is exactly twice the number of nonzero $a$ such that $\tfrac{-2}{a^2+1}$ is a quadratic residue (clearly it's never zero). If $(\tfrac{-2}{p})=1$, then this is the number of nonzero $a$ such that $a^2+1$ is a quadratic residue, which is half the number of solutions to the equation $b^2-a^2=1$ which are nonzero in $a$. Note that $a^2+1$ can never equal $0$ since $(\tfrac{-1}{p})=-1$. Disregarding the nonzero condition, lemma 1 tells us that there are $p-1$ solutions, but two of these have $a=0$, namely $(a,b)=(0,\pm 1)$, hence the quantity we are looking for is $\tfrac{p-3}{2}$, which implies that there are $p-3$ solutions in nonzero $x$ and $y$. Otherwise, this is the number of nonzero $a$ such that $a^2+1$ is not a quadratic residue, which is $p$ minus the number of solutions to $b^2-a^2=1$ in the previous scenario, i.e. $\tfrac{p+1}{2}$, which implies that there are $p+1$ solutions as desired. $\blacksquare$ Every nonzero solution to $x+y=-2$ where $x$ and $y$ are nonzero quadratic residues corresponds to four nonzero solutions $(x,y)$ to $x^2+y^2=-2$, of which there are either $p-3$ or $p+1$, so we have either $\tfrac{p-3}{4}$ or $\tfrac{p+1}{4}$ nonzero solutions to the first equation. There are also possibly $2$ additional solutions where one variable is zero, depending on the value of $(\tfrac{-2}{p})$. Furthermore, since no solution has $x=y$, else $-1$ is a QR mod $p$, it follows that the number of collisions that occur is either $\tfrac{p-3}{8}$, $\tfrac{p+1}{8}$, or $\tfrac{p+5}{8}$ (it is not concerning that these three will not always be integers at the same time, since the value of $p \pmod{8}$ affects $(\tfrac{-2}{p})$ so things work out). Therefore, the range of $P$, and therefore $Q$, modulo $p$ contains either $\tfrac{3p+7}{8}$, $\tfrac{3p+3}{8}$, or $\tfrac{3p-1}{8}$ distinct residues, which is at most $0.499p$ for $p>1000$, so we are done. $\blacksquare$ Remark: The "motivation" behind selecting this rather convoluted polynomial as opposed to something like $2x^2-1$ was that it was the first thing which came to mind when trying to get less than $0.5p$ distinct residues mod $p$: squares are almost close enough, and actually fourth powers are good for $1 \pmod{4}$ primes, but there is no guarantee that this works for $3 \pmod{4}$ primes. However, we can ensure that $x^4+1$ is nonzero for the latter, hence when this is squared we can only get $\tfrac{p-1}{2}$ residues (i.e. the nonzero quadratic residues). Because it actually seems quite hard to get down to at most $0.5p$ residues with a different type of construction, a closer inspection of this one leads to a solution.

:yayy: FINALLY FINISHED BRU can someone check this idt its actually rigorous, and the above solutions never specified the exact details on $\sum\frac{(1-a)^2}p$ and how to get that thing and they just omitted it so could someone do a FTFY and fix the last part again, had to ACTIVELY reassure myself that i was to NOT stray away from high MOHS problems in lieu of improving.honestly, i don't get how you would come up with $(x^2-1)^2$ without just blindly guessing, could someone give me the motivation for that? because i got that part with the 20\% hint.. The answer is $(x^2-1)^2$ multiplied by a constant that can be manually checked to account for edge cases. Note that it suffices to compute it for primes p and when n=4, which can be manually checked to work. The number of residues $Q(x)$ runs over is $\frac{p+1}2-|S|$, where $2a^2-1\equiv1-2b^2$ is the overcount of QR, $\iff a^2\equiv1-b^2\pmod p\implies S=\{a:\text{ only }\left(\frac{1+a}p\right)=-1\text{ or }\left(\frac{1-a}p\right)=-1\}$, since multiplying together it's the number of NQR mod p (i know, terrible explanation). Then, compute \begin{align*} |S|=\frac14\sum_{a=2}^{p-2}\left(1-\left(\frac{1+a}p\right)\right)\left(1-\left(\frac{1-a}p\right)\right)=\frac{p-3}4-\frac14\left(\sum_{a=2}^{p-2}\left(\left(\frac{1+a}p\right)+\sum_{a=2}^{p-2}\left(\frac{p-(1-a)}p\right)-\sum_{a=2}^{p-2}\left(\frac{1-a^2}p\right)\right)\right), \end{align*}and the 2nd-to-last cancels mostly with the third-to-last sum notations (due to QRs being ``symmetric" around $\frac{p-1}2$), and we'll do some handwaving with the constant edge cases here in lieu of assuming the problem is true. Now comes the part where I needed help: Here's the hint communicated to me by Evan: ``For any odd prime $p$, there are at least $\frac12(p-3)$ values of $a$ for which $\left( \frac{1-a^2}{p} \right) = +1$. The idea is to factor $(1-a)(1+a)$ and pick $1-a=ku^2$, $1+a=kv^2$ for suitable $(k,u,v)$." Ok then, let's divide them (hint by lrjr) to need to compute $\sum_{a=2}^{p-2}\left(\frac{(1+a)(1-a)^{-1}}p\right)$ minus some constant manually computed for edge cases; this is indeed $\ge\frac{p-3}2$ (this bijects with normal legendre, because the inverse of $(1-a)^{-1}$ times (1+a) varying a forms such a complete residue set (obviously minus some constant edge cases, which, as always, i refrain from manually computing in lieu of assuming the prolem is true)). Now plugging back in and doing some handwaving with our manually computed constants which i shall not compute in lieu of assuming the problem is true, we evaluate this to be $$|S|\ge \frac14 \left( p + (+1) \cdot \tfrac12(p-3) + 0 \cdot 2+ (-1) \cdot ( (p-2) -\tfrac12(p-3)) \right) - 1\ge\frac{p - 5}4,$$which makes Q(x) run over at most $\frac{p+1}2-\frac{p-5}4\le0.499p\forall p>7$.

My writeup is so bad and it might not be correct, so if there is a mistake, let me know. We'll prove that choosing $Q(x) = 4(x^2 - 2)^2$ will satisfy the problem condition. We only need to prove the result on $n = 4$ and when $n = p$ is an odd prime. The case $n = 4$ is trivial, so we only have to consider the case $n = p$ is an odd prime. Note that the number of distinct residues in $Q(0), Q(1), \dots, Q(p-1)$ modulo $p$ is same as the number of distinct residues in $\frac{Q(0)}{4}, \frac{Q(1)}{4}, \dots, \frac{Q(p-1)}{4}$ so we can assume $Q(x) = (x^2 - 2)^2$. Now note that there are exactly $\frac{p+1}{2}$ distinct residues in $0^2 - 2, 1^2 - 2, 2^2 - 2, \dots, (p-1)^2 - 2$. Consider a multigraph on $\mathbb{F}_p^2$ with edges $(x, p-x) \to (y, p - y) \iff p \mid (x^2 + y^2 - 4)$. Draw 4 edge if $x \neq 0$, otherwise draw 2 edge. Then the number of distinct residues in $Q(0), Q(1), \dots, Q(p-1)$ is the number of connected components in $G$. Now consider the following claim: Claim: The equation $x^2 + y^2 = 4$ in $\mathbb{F}_p$ has exactly $p + (-1)^{\frac{p+1}{2}}$ solutions. Proof: For fixed $i$, the equation $x^2 + i^2 = 4$ has $1 + \left( \frac{4-i^2}{p} \right)$ solutions, so the number of solution is $\sum_{i=0}^{p-1} 1 + \left( \frac{4-i^2}{p} \right)$. Note that $\sum_{i=0}^{p-1} \left( \frac{4-i^2}{p} \right) = (-1)^{\frac{p-1}{2}}\sum_{i=0}^{p-1} \left( \frac{i^2-4}{p} \right)$ and it's well known that if $p$ doesn't divide $a$, then $\sum_{i=0}^{p-1} \left( \frac{i^2 + a}{p} \right) = -1$. (We can get this identity by counting the number of solutions of the equation $x^2 - y^2 = a$ in $\mathbb{F}_p$). Thus $(-1)^{\frac{p-1}{2}}\sum_{i=0}^{p-1} \left( \frac{i^2-4}{p} \right) = (-1)^{\frac{p+1}{2}}$, so the equation $x^2 + y^2 = 4$ has exactly $p + (-1)^{\frac{p+1}{2}}$ solutions. $\blacksquare$ Now it's not hard to see that every connected component of $G$ has either 4 or 2 edges. (Note that isolated vertex is a connected component of 0 edges) If $(a, b)$ are solution of $x^2 + y^2 = 4$ in $\mathbb{F}_p$ then $(b, a)$ is also a solution, so the number of edges in $G$ is exactly $\frac{p + (-1)^{\frac{p+1}{2}}}{2}$. Now assume $G$ has exactly $k+1$ connected components which have an edge. Then $4k + 2 = \frac{p + (-1)^{\frac{p+1}{2}}}{2}$, so $k+1 = \frac{p + (-1)^{\frac{p+1}{2}} + 4}{8}$. Thus the number of connected component in $G$ is exactly $\frac{p+1}{2} - 2(k+1) + (k+1) = \frac{3p + (-1)^{\frac{p-1}{2}}}{8} < 0.499p$, so we're done. $\blacksquare$

We claim that $Q(x) = C \cdot (x^2 - 1)^2$ works, where $C$ is chosen such that it is a multiple of each element of a finite set of small primes. If we prove the statement for all primes $p \ge N$ for some constant value of $N$, we are done by CRT (Note that primes $p < N$ are taken care of by our choice of $C$). We are essentially solving the equation $Q(x) \equiv Q(y) \pmod p$ where $x, y$ are distinct in $\mathbb{F}_p$. Form an undirected graph $\mathcal{A}$ in which $x$ and $y$ are connected iff $x \neq y$ and $Q(x) \equiv Q(y)$. It is clear that we must prove that the number of cliques $X < .499p$. It is obvious that $x \equiv -y \pmod p$ gives $Q(x) \equiv Q(y) \pmod{p}$, so the range of $Q(x) \pmod p$ is already restricted down to $\frac{p+1}{2}$ values. Connecting the vertices to update for this gives us several $K_2$ cliques and $0$ by itself. By simple manipulations the only other way that $Q(x) \equiv Q(y) \pmod p$ is if $x^2+y^2 \equiv 2 \pmod p$. Lemma: $x^2 + y^2 \equiv 2$ has exactly $p-1$ solutions in $\mathbb{F}_p$ for odd primes (MONT Theorem 8.5.1) Omitted. We can remove the redundant solutions so that the total number of solutions that are unique is $p - \mathcal{O}(1)$. Now, we must divide by $2$ to account for swapping $x$ and $y$. Now, notice that if two vertices $i$ and $j$ from different $K_2$, and they satisfy $i^2 + j^2 \equiv 2$, then these $K_2$'s must be paired with each other and "merge" to form a $K_4$. Now notice that a $K_2$ clique can only be merged with at most other $K_2$. To "merge" these $K_2$'s there are $4$ edges created, and only $1$ of them must be counted to subtract from $\frac{p+1}{2}$, which means we must divide by $4$ again. Therefore in total we are dividing by $8$. Therefore our count is \begin{align*} \frac{p+1}{2} - \frac{p}{8} + \mathcal{O}(1) \\ \approx \frac{3p}{8} + \mathcal{O}(1) < .499p \end{align*}for large $p$ $\blacksquare$