For prime $p > 7$ with $p1=rs$, $r>1$, $s>1$, let $A=\{x^rx \in \mathbb{Z}_p\}$ and $B = \{x^sx \in \mathbb{Z}_p\}$. If $g$ is a primitive root mod $p$ then $A = \{0\} \cup \{g^{ir}0 \leq i < s \}$ and $B = \{0\} \cup \{g^{js}0 \leq j < r \}$. Is it always true that $\mathbb{Z}_p \neq A + B$?

$\begingroup$ It doesn't follow directly from HasseWeil, so it's not obviously false. Do you have numerical evidence? $\endgroup$ – Felipe Voloch Mar 31 '12 at 16:16

1$\begingroup$ If you take $r=2$, then you're asking if, for any $p$, there are $n, n+1, n+2$ which are not quadratic residues. Is that true? $\endgroup$ – Zack Wolske Mar 31 '12 at 17:35

$\begingroup$ @Felipe: Yes, so far it appears to hold numerically. I just tried p = 113117 for fun. p1 = 4*28279. When r = 2, s= 2*28279 I get A+B = 98903. If r = 4, s = 28279 then A+B = 86330. The gap between A+B and Z_p seems to grow larger and larger as p increases. Moreover it also appears that for given p and different factorizations of p1 = rs, as r and s get closer, A+B gets smaller, so the largest A+B seems to occur when r = 2, s = (p1)/2. Maple is just too slow, I need to write a program to test larger cases and see a trend. @Zack: Forgive my ignorance, how do you get that? $\endgroup$ – Jose A Rodriguez Mar 31 '12 at 18:12

1$\begingroup$ @Jose, @Felipe: The result is true for the first 2000 primes  up to $17419$. $\endgroup$ – Mark Sapir Apr 1 '12 at 1:45

2$\begingroup$ @Seva: I don't see that the statement follows from elementary properties of the Legendre symbol, I am very interested to see the proof, can you show me? $\endgroup$ – Sungjin Kim Apr 1 '12 at 8:44
This is a very partial answer, addressing the extreme cases $r=2$ and $r=s$ only.
For $r=s$ we have $A=B$ and $A=B=r+1$. Hence $$ A+B\le \binom{r+1}2+(r+1)=\frac{p+3r+1}{2} < p, $$ implying $A+B\ne{\mathbb F_p}$.
This trivial argument extends onto the case where $r$ and $s$ have a sufficiently large greatest common divisor. Namely, writing $d=(r,s)$, we have $A\cap B=d+1$; it follows that at least $(d+1)^2\binom{d+1}2=(d+1)(d+2)/2$ sums $a+b$ are wasted on double representations. Therefore $$ A+B\le AB\frac{(d+1)(d+1)}2=p+r+s\frac{(d+1)(d+2)}2; $$ as a result, if $(d+1)(d+2)>2(r+s)$, then $A+B\ne{\mathbb F}_p$.
For $r=2$ the problem reduces to showing that for any sufficiently large prime $p$, there is a run of three consecutive quadratic nonresidues $\mod p$. This is easy to prove using Weil's bound, but can be done in an elementary way, as follows. The following argument actually works for all $p\ge 11$. Suppose, for a contradiction, that for any $z\in{\mathbb F}_p$, at least one of $z,z1$, and $z+1$ is a square. Then $$ \Big(\Big(\frac{z1}p\Big)1\Big) \Big(\Big(\frac{z}p\Big)1\Big) \Big(\Big(\frac{z+1}p\Big)1\Big) = 0 $$ for every $z\in{\mathbb F}_p$, except that if $\Big(\frac{1}p\Big)=\Big(\frac{2}p\Big)=1$, then for $z=1$ this product is equal to $4$. Letting $\delta=1$ in this case and $\delta=0$ otherwise, we thus have $$ \sum_{z\in\mathbb F_p} \Big(\Big(\frac{z1}p\Big)1\Big) \Big(\Big(\frac{z}p\Big)1\Big) \Big(\Big(\frac{z+1}p\Big)1\Big) = 4\delta. $$ Opening the parentheses and evaluating "quadratic sums" yields $$ \sum_{z\in{\mathbb F}_p} \Big(\frac{(z1)z(z+1)}p\Big) = (p3)  4\delta. $$ This shows that for all $z\in{\mathbb F}_p\setminus\{1,0,1\}$, writing for brevity $f(z)=(z1)z(z+1)$, we have $\Big(\frac{f(z)}p\Big)=1$, save for exactly $2\delta$ exceptional values of $z$. Observing that $f(z)=f(z)$, we conclude that $\Big(\frac{1}p\Big)=1$; hence $\delta=0$, meaning that, indeed, $\Big(\frac{f(z)}p\Big)=1$ for all $z\in{\mathbb F}_p\setminus\{1,0,1\}$, without any exceptions.
What we have shown so far is that $f(z)$ is a quadratic residue for each $z\in{\mathbb F}_p\setminus\{1,0,1\}$. Consequently, so is $f(z+1)/f(z)=(z+2)/(z1)=1+3/(z1)$, an evident nonsense!

$\begingroup$ That's very clever. Thank you for the nice solution. Thinking about the use of Weil's bound, the reference paper by R. Peralta gives much stronger assertion: For large enough p, there exists any "R(quadratic residue)" "N(quadratic nonresidue" sequence of length $u\log_2 p$ where $u<1/2$. $\endgroup$ – Sungjin Kim Apr 2 '12 at 1:36

$\begingroup$ Sure. However, for sequences of length $3$ this can be done by elementary means. $\endgroup$ – Seva Apr 2 '12 at 5:54

$\begingroup$ Nice. Probably the most difficult case is when (r,s) = 1. $\endgroup$ – Jose A Rodriguez Apr 2 '12 at 17:17

1$\begingroup$ A similar argument should show that, for fixed $r$, the statement is true for all sufficiently large $p$ with $p \equiv 1 \mod r$. $\endgroup$ – David E Speyer Apr 2 '12 at 20:23

$\begingroup$ @David Speyer: A similar argument will be involving character sums of polynomial of degree $r$. This argument for $r=2$ was easy because the other terms were character sums of quadratic polynomial(e.g. $n(n+1)$, $n(n1)$, $n^21$). So, I don't think the similar argument is applicable in $r>2$ case. $\endgroup$ – Sungjin Kim Apr 2 '12 at 23:23
For fixed $r>1$, use of Weil's bound will give the result. We refer to Theorem 5.1 from chapter 2 of W.M.Schmidt, Equations over Finite Fields: An Elementary Approach.
Theorem Let $f_1,\cdots, f_n$ be polynomials with coefficients in $\mathbb{F}_q$ and of degree $\leq m$. Put $\delta=\textrm{lcm}(d_1,\cdots,d_n)$, and $d=d_1d_2\cdots d_n$. Let X be a variable and let $\eta_1,\cdots,\eta_n$ be algebraic quantities with \begin{equation} \eta_1^{d_1}=f_1(X), \cdots, \eta_n^{d_n}=f_n(X).\ \end{equation} Suppose \begin{equation} [\overline{\mathbb{F}}_q(X, \eta_1,\cdots,\eta_n):\overline{\mathbb{F}}_q(X)]=d. \end{equation} Then if $q>100\delta^3m^2n^2$, the number $N$ of solutions $(x,y_1,\cdots,y_n)\in\mathbb{F}_q^{n+1}$ of the equations $y_1^{d_1}=f_1(X),\cdots,y_n^{d_n}=f_n(X)$ satisfies \begin{equation} Nq<5mnd\delta^{5/2}q^{1/2}. \end{equation} We will use this theorem to solve the problem for fixed $r>1$. We have $q=p$ prime number. Let $g$ be a primitive root modulo $p$. We put $n=r+1$, $m=1$, $d_1=\cdots=d_n=r$, $\delta=r$, $d=r^{r+1}$, $f_i(X)=g(Xg^{is})$ for $0\leq i \leq r1$, and $f_r(X)=gX$. Then the condition is satisfied, and the number $N$ of solutions to the system $Y_i^r=f_i(X)$ ($0\leq i \leq r$) is \begin{equation} Np<5(r+1) r^{r+1+5/2}p^{1/2}. \end{equation}
We look for the number $N^{*}$ of solutions with no $Y_i$ being zero. Then we have $$N^{*}\geq p5(r+1) r^{r+1+5/2}p^{1/2}(r+1)r^{r+1}.$$ This is in fact greater than zero for sufficiently large $p$. For any such solution $(X,Y_0,\cdots, Y_r)\in \mathbb{F}_p^{r+2}$, we obtain that $$X\in \mathbb{Z}_p(A+B).$$ This proves the result.

$\begingroup$ Very nice, it isn't obvious to see how to cast the problem into the form required by the theorem. $\endgroup$ – Jose A Rodriguez Apr 3 '12 at 13:50

$\begingroup$ My bound for "Sufficiently large $p$" depends on $r$. So my solution does not completely settle your question. $\endgroup$ – Sungjin Kim Apr 3 '12 at 14:15