19
$\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$
  • $\begingroup$ It doesn't follow directly from Hasse-Weil, 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. 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$ – 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
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$
  • $\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(n-1)$, $n^2-1$). So, I don't think the similar argument is applicable in $r>2$ case. $\endgroup$ – Sungjin Kim Apr 2 '12 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$
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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