# Sums of powers mod p

For prime $p > 7$ with $p-1=rs$, $r>1$, $s>1$, let $A=\{x^r|x \in \mathbb{Z}_p\}$ and $B = \{x^s|x \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$?

-
It doesn't follow directly from Hasse-Weil, so it's not obviously false. Do you have numerical evidence? –  Felipe Voloch Mar 31 '12 at 16:16
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? –  Zack Wolske Mar 31 '12 at 17:35
@Felipe: Yes, so far it appears to hold numerically. I just tried p = 113117 for fun. p-1 = 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 p-1 = rs, as r and s get closer, |A+B| gets smaller, so the largest |A+B| seems to occur when r = 2, s = (p-1)/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? –  Jose A Rodriguez Mar 31 '12 at 18:12
@Jose, @Felipe: The result is true for the first 2000 primes - up to $17419$. –  Mark Sapir Apr 1 '12 at 1:45
@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? –  i707107 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 |A||B|-\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 non-residues $\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,z-1$, and $z+1$ is a square. Then $$\Big(\Big(\frac{z-1}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{z-1}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{(z-1)z(z+1)}p\Big) = (p-3) - 4\delta.$$ This shows that for all $z\in{\mathbb F}_p\setminus\{-1,0,1\}$, writing for brevity $f(z)=(z-1)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)/(z-1)=1+3/(z-1)$, an evident nonsense!

-
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$. –  i707107 Apr 2 '12 at 1:36
Sure. However, for sequences of length $3$ this can be done by elementary means. –  Seva Apr 2 '12 at 5:54
Nice. Probably the most difficult case is when (r,s) = 1. –  Jose A Rodriguez Apr 2 '12 at 17:17
A similar argument should show that, for fixed $r$, the statement is true for all sufficiently large $p$ with $p \equiv 1 \mod r$. –  David Speyer Apr 2 '12 at 20:23
@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(n-1)$, $n^2-1$). So, I don't think the similar argument is applicable in $r>2$ case. –  i707107 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 $$\eta_1^{d_1}=f_1(X), \cdots, \eta_n^{d_n}=f_n(X).\$$ Suppose $$[\overline{\mathbb{F}}_q(X, \eta_1,\cdots,\eta_n):\overline{\mathbb{F}}_q(X)]=d.$$ 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 $$|N-q|<5mnd\delta^{5/2}q^{1/2}.$$ 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(X-g^{is})$ for $0\leq i \leq r-1$, 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 $$|N-p|<5(r+1) r^{r+1+5/2}p^{1/2}.$$

We look for the number $N^{*}$ of solutions with no $Y_i$ being zero. Then we have $$N^{*}\geq p-5(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.

-
Very nice, it isn't obvious to see how to cast the problem into the form required by the theorem. –  Jose A Rodriguez Apr 3 '12 at 13:50
My bound for "Sufficiently large $p$" depends on $r$. So my solution does not completely settle your question. –  i707107 Apr 3 '12 at 14:15