Let $p=2n+1$ be an odd prime, and let $a_1<\ldots<a_{n}$ be all the quadratic residues mod $p$ among $1,\ldots,p-1$. For $a\in\mathbb Z$ let $\{a\}_p$ be the least nonnegative residue of $a$ modulo $p$. It is well known that the list $\{1^2\}_p,\ldots,\{n^2\}_p$ is a permutation of $a_1,\ldots,a_n$. Recently, I determined the sign of this permutation for $p\equiv3\pmod4$ in the preprint arXiv:1809.07766 (available from http://arxiv.org/abs/1809.07766). Motivated by this, here I ask the following question.

QUESTION. Is it true that for each prime $p\equiv3\pmod4$ we have \begin{align*}&\left|\left\{(j,k):\ 1\le j<k\le\frac{p-1}2\ \text{and}\ \{j(j+1)\}_p> \{k(k+1)\}_p\right\}\right| \\&\quad\qquad\equiv\left\lfloor\frac{p+1}8\right\rfloor\pmod 2\ ? \end{align*}

I have verified this for all primes $p<20000$ with $p\equiv 3\pmod4$. Based on this, I conjecture that the question has a positive answer. Any ideas towards its solution?


Denote $(p-1)/2=n$ and replace the condition to $0\leqslant j<k\leqslant \frac{p-1}2$, this does not add new pairs satisfying $\{j(j+1)\}_p>\{k(k+1)\}_p$. Now denote $j=n-s$, $k=n-t$, we have $n\geqslant s>t\geqslant 0$ and our condition rewrites as $$\{(n-s)(n-s+1)\}_p>\{(n-t)(n-t+1)\}_p.$$ Note that $(n-s)(n-s+1)\equiv n(n+1)+s^2\equiv s^2-1/4$ modulo $p$. Denote $A=(p+1)/4$, then we have to count the number of pairs $s>t$ such that $\{s^2-A\}_p>\{t^2-A\}_p$. Note that in general $$ {\rm sign}\, \left(\{s-A\}_p-\{t-A\}_p\right)={\rm sign}\, \left(\{s\}_p-\{t\}_p\right)\cdot (-1)^{\chi(\{s\}_p<A)+{\chi(\{t\}_p<A)}}. $$ This observation reduces the sign we are interested in to two signs:

at first, the product $\prod_{n\geqslant s>t\geqslant0}(\{s^2\}_p-\{t^2\}_p)$ which is your product $S_p$ from equation (1.4) in the cited paper;

at second, $(-1)^{M+1}$, where $M$ is the number of quadratic residues less than $(p+1)/4$.

The first guy is calculated by you, the second looks very classical. Namely, what remains to prove is the following:

if $p=8k+3$, then $(\frac{(2k)!}p)=(-1)^k$, that is, if the set $\{1,2,\dots,2k\}$ contains $k+x$ quadratic residues and $k-x$ quadratic non-residues, then $x$ is even;

if $p=8k-1$, the same holds for the set $\{2k,\dots,4k-1\}$, that is, $(\frac{(4k-1)!/(2k-1)!}p)=(-1)^k$.

That must be known and not hard. Well, I did not find exactly the same fact, but something morally similar for $p=4k+1$ (in Yamamoto's paper "On Gaussian sums with biquadratic residue characters", Crelle 1965). Actually for $p=8k+3$ we always have equally many quadratic residues and non-residues in the set $\{1,2,\dots,2k\}$, the same for $p=8k-1$ and the set $\{2k,\dots,4k-1\}$. UPDATE: As Zhi-Wei remarks in the comments, this was proved in 1974 by B.C.Berndt and S. Chowla. For sake of completeness I leave the short proof below.

The proof is simple as that. Let $p=8k+3$. Take all quadratic residues less than $p/2$. Some of them are odd and some are even. Divide them all by -2, we get quadratic residues again. The even quadratic residues transform to quadratic residues between $3p/4$ and $p$, the odd quadratic residues transform (by the map $x\mapsto (p-x)/2$) to quadratic residues between $p/4$ and $p/2$. Therefore we get the identity |residues(from 0 to $p/2$)|=|residues(from $3p/4$ to $p$)|+|residues(from $p/4$ to $p/2$)|. But the first summand is exactly |non-residues(from 0 to $p/4$)| (due to the map $x\mapsto p-x$) and we celebrate.

For $p=8k+7$ use 2 instead of -2.

  • $\begingroup$ How do you get the equality for signs? If $\{s^2\}_p<A<\{t^2\}_p$ then $$\{s^2-A\}_p-\{t^2-A\}_p=A-\{s^2\}_p-(\{t^2\}_p-A)=\frac{p+1}2-\{s^2\}_p-\{t^2\}_p.$$ $\endgroup$ – Zhi-Wei Sun Oct 28 '18 at 23:07
  • $\begingroup$ I think, $\{s^2 - A\} _p=p+\{s^2\} _p- A$ for $\{s^2\}_p<A$ $\endgroup$ – Fedor Petrov Oct 29 '18 at 1:19
  • $\begingroup$ Okay, it's my negligence. $\endgroup$ – Zhi-Wei Sun Oct 29 '18 at 1:27
  • $\begingroup$ In 1974 B.C.Berndt and S. Chowla[Nordisk Mat. Tidskr. 22(1974), 5-8] proved that $\sum_{k=1}^{\lfloor p/4\rfloor}(\frac kp)=0$ for any prime $p\equiv3\pmod 8$. So the case $p=8k+3$ has been solved. $\endgroup$ – Zhi-Wei Sun Oct 29 '18 at 2:21
  • $\begingroup$ For prime $p\equiv7\pmod 8$, Berndt and Chowla showed that $\sum_{k=\lfloor p/4\rfloor}^{\lfloor p/2\rfloor}(\frac kp)=0$. Note also that $\sum_{k=1}^{\lfloor p/2\rfloor}(\frac kp)=h(-p)$. So the case $p=8k-1$ has been solved as well. $\endgroup$ – Zhi-Wei Sun Oct 29 '18 at 2:24

Let $p$ be a prime with $p\equiv3\pmod4$. Fedor Petrov has reduced my conjecture to the determination of $(-1)^M$, where $M$ is the number of quadratic residues in the interval $(0,p/4)$. Note that $$\frac{p-3}4+\sum_{k=1}^{(p-3)/4}\left(\frac kp\right)=\sum_{k=1}^{(p-3)/4}\left(1+\left(\frac kp\right)\right)=2M.$$ So, it suffices to determine $N_p:=\sum_{k=1}^{\lfloor p/4\rfloor}(\frac kp)$. B. C. Berndt and S. Chowla [ Zero sums of the Legendre symbol, Nordisk Mat. Tidskr. 22(1974), 5-8] proved that $N_p=0$ if $p\equiv3\pmod 8$, and that $$\sum_{k=1}^{\lfloor p/2\rfloor}\left(\frac kp\right)-N_p=\sum_{k=\lceil p/4\rceil}^{\lfloor p/2\rfloor}\left(\frac kp\right)=0$$ when $p\equiv 7\pmod 8$. By Dirichlet's class number formula, $h(-p)=\sum_{k=1}^{(p-1)/2}(\frac kp)$ for $p\equiv7\pmod 8$. So we have determined the value of $N_p$ and hence the conjecture has been proved by combining Fedor Petrov's idea and my above supplement.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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