Sums of powers mod p

Question

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$?

Answer 1

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!

Answer 2

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} |N-q|<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(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 \begin{equation} |N-p|<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 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.