MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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!

share|cite|improve this answer
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 \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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.