# 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

Let $$p=2n+1$$ be an odd prime, and let $$a_1<\ldots 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(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, 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 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.

• 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.$$ – Zhi-Wei Sun Oct 28 '18 at 23:07
• I think, $\{s^2 - A\} _p=p+\{s^2\} _p- A$ for $\{s^2\}_p<A$ – Fedor Petrov Oct 29 '18 at 1:19
• Okay, it's my negligence. – Zhi-Wei Sun Oct 29 '18 at 1:27
• 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. – Zhi-Wei Sun Oct 29 '18 at 2:21
• 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. – 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.