On the parity of $|\{(j,k):\ 1\le j<k\le\frac{p-1}2\ \&\ \ j(j+1)\ \text{mod}\ p\,>\,k(k+1)\ \text{mod}\ p\}|$ with $p$ prime

Question

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?

Answer 1

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.

Answer 2

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.