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?


2 Answers 2


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$ Oct 28, 2018 at 23:07
  • $\begingroup$ I think, $\{s^2 - A\} _p=p+\{s^2\} _p- A$ for $\{s^2\}_p<A$ $\endgroup$ Oct 29, 2018 at 1:19
  • $\begingroup$ Okay, it's my negligence. $\endgroup$ Oct 29, 2018 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$ Oct 29, 2018 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$ Oct 29, 2018 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .