QUESTION: Is my following conjecture (formulated in 2016) true? How to solve it?
Conjecture. For any non-constant polynomials $P(x)，Q(x)\in\mathbb Z[x]$, there is a positive integer $N(P,Q)$ depending on $P(x)$ and $Q(x)$ such that for any prime $p>N(P,Q)$ the set $$\{P(x)+Q(y):\ x,y=0,1,\ldots,p-1\}$$ contains a complete system of residues modulo $p$.
For example, it seems that we may take $$N(x^4,x^2)=5,\ N(x^5,x^2)=11,\ N(x^3,x^3)=7,\ N(x^6,x^3)=31.$$
$(x^2 + 1)^2 + (y^2 + 1)^2$ doesn't represent $0$ if $p \equiv 3 \bmod 4$.
At least, it is easy to see that for any three non-constant polynomials $P_1,P_2,P_3\in\mathbb Z[x]$, the sum
$$ \{ P_1(x_1)+P_2(x_2)+P_3(x_3)\colon x_1,x_2,x_3\in\mathbb Z \} $$
covers all residue classes modulo $p$. Indeed, restricting $x_1,x_2,x_3$ to the range $[0,p-1]$, the number of representations of $a\in\mathbb F_p$ is
$$ T(a) = \sum_{x_1,x_2,x_3=0}^{p-1} \frac1p \sum_{z=0}^{p-1} e^{2\pi i \frac{P_1(x_1)+P_2(x_2)+P_3(x_3)-a}p\,z} = p^2 + R, $$
where
$$ R = \frac1p\sum_{z=1}^{p-1} e^{-2\pi i\frac{az}p} \prod_{j=1}^3 \sum_{x=0}^{p-1}e^{2\pi i \frac{P_j(x)}p\,z}. $$
Letting $d_j:=\deg P_j$ and applying Weil's bound, we get
$$ |R| < (d_1-1)(d_2-1)(d_3-1) p^{3/2}. $$
Therefore, $T(a)>0$ provided that $p\ge (d_1-1)^2(d_2-1)^2(d_3-1)^2$.
Also, the conjecture is true in the special case where the two polynomials are $P_1(x)=x^m$ and $P_2(x)=x^n$, with $m,n>0$. To see this, notice that the image of each of these polynomials contains the image of the polynomial $x^{mn}$, and that, reduced modulo $p$, this latter image consists of $0$ and the multiplicative subgroup of $\mathbb F_p$ of index $d:=\gcd(mn,p-1)$. It is know, however, that for any multiplicative subgroup $H\le \mathbb F_p$ of size $|H|>p^{3/4}$, one has $H+H=\mathbb F_p$. Elaborating sightly on this argument, one can get an explicit estimate like $N(x^m,x^n)\le(\min\{m,n\})^4$.
The conjecture is true when the degrees of $P(x)$ and $Q(y)$ are relatively prime. For general polyomials $F(x,y)$ in two variables, a variant of the conjecture is true.
Theorem 1. Let $P(x)\in\mathbb{Z}[x]$ and $Q(y)\in\mathbb{Z}[y]$ be two polynomials of relatively prime degrees. For any prime $p$, and for all residues $r$ modulo $p$, the congruence $P(x)+Q(y)\equiv r\pmod p$ has $p+O(p^{1/2})$ solutions. The implied constant depends only on $P(x)$ and $Q(y)$.
Sketch of proof. Without loss of generality, the prime $p$ exceeds the leading coefficients of $P(x)$ and $Q(y)$. Then, for all residues $r$ modulo $p$, the polynomial $P(x)+Q(y)-r$ is absolutely irreducible over $\mathbb{F}_p$, hence the congruence $P(x)+Q(y)\equiv r\pmod p$ has $p+O(p^{1/2})$ solutions by the celebrated theorem of Weil (1940). For more details on the quoted results, see Theorems 1A and 1B in Section III.1 of Schmidt: Equations over finite fields (Springer, 1976).
Theorem 2. Let $F(x,y)\in\mathbb{Q}[x,y]$ be an absolutely irreducible polynomial. There exists a positive integer $N(F)$ depending on $F(x,y)$ such that for any prime $p>N(F)$, and for all but $O(1)$ residues $r$ modulo $p$, the congruence $F(x,y)\equiv r\pmod p$ has $p+O(p^{1/2})$ solutions. The implied constants depend only on the degree of $F(x,y)$.
Sketch of proof. It follows from a theorem of Noether (1922) that there exists a positive integer $N(F)$ depending on $F(x,y)$ such that for any prime $p>N(F)$, and for all but $O(1)$ residues $r$ modulo $p$, the polinomial $F(x,y)-r$ is absolutely irreducible over $\mathbb{F}_p$. From here we finish as in the previous proof. For more details on Noether's theorem, see Theorem 2A in Section V.2 of Schmidt: Equations over finite fields (Springer, 1976).
