20
$\begingroup$

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

$\endgroup$
18
  • $\begingroup$ It doesn't follow directly from Hasse-Weil, so it's not obviously false. Do you have numerical evidence? $\endgroup$ Mar 31, 2012 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$ Mar 31, 2012 at 17:35
  • $\begingroup$ @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? $\endgroup$ Mar 31, 2012 at 18:12
  • 1
    $\begingroup$ @Jose, @Felipe: The result is true for the first 2000 primes - up to $17419$. $\endgroup$
    – user6976
    Apr 1, 2012 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$ Apr 1, 2012 at 8:44

2 Answers 2

12
$\begingroup$

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!

$\endgroup$
5
  • $\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$ Apr 2, 2012 at 1:36
  • $\begingroup$ Sure. However, for sequences of length $3$ this can be done by elementary means. $\endgroup$
    – Seva
    Apr 2, 2012 at 5:54
  • $\begingroup$ Nice. Probably the most difficult case is when (r,s) = 1. $\endgroup$ Apr 2, 2012 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$ Apr 2, 2012 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(n-1)$, $n^2-1$). So, I don't think the similar argument is applicable in $r>2$ case. $\endgroup$ Apr 2, 2012 at 23:23
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Very nice, it isn't obvious to see how to cast the problem into the form required by the theorem. $\endgroup$ Apr 3, 2012 at 13:50
  • $\begingroup$ My bound for "Sufficiently large $p$" depends on $r$. So my solution does not completely settle your question. $\endgroup$ Apr 3, 2012 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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