# On triangular numbers modulo primes

Let $$p$$ be an odd prime. For $$a\in\mathbb Z$$ let $$\{a\}_p$$ denote the least nonnegative residue of $$a$$ modulo $$p$$. The list $$\{1^2\}_p,\ldots,\{((p-1)/2)^2\}_p$$ is a permutation of all the quadratic residues modulo $$p$$ among $$1,\ldots,p-1$$, and I used Galois theory to determine the sign of this permutation for $$p\equiv3\pmod4$$ in my preprint arXiv:1809.07766 available from http://arxiv.org/abs/1809.07766.

Now let us consider a similar problem for triangular numbers. Recall that the triangular numbers are those integers $$T_n=n(n+1)/2$$ $$(n=0,1,2,\ldots)$$. It is easy to see that for any odd prime $$p$$ those $$\{T_k\}_p\ (k=1,\ldots,(p-1)/2)$$ are pairwise distinct.

QUESTION: Is my following conjecture true?

Conjecture. Let $$p>3$$ be a prime. If $$p\equiv3\pmod4$$, then $$(-1)^{|\{(j,k):\ 1\leqslant j\{T_k\}_p\}|} =(-1)^{(h(-p)+1)/2+|\{1\leqslant k\leqslant\lfloor\frac{p+1}8\rfloor:\ (\frac kp)=1\}|},$$ where $$(j,k)$$ is an ordered pair, $$(\frac kp)$$ is the Legendre symbol, and $$h(-p)$$ is the class number of the imaginary quadratic field $$\mathbb Q(\sqrt{-p})$$. Also, \begin{align}&(-1)^{|\{(j,k):\ 1\leqslant jp\}|} \\=&\begin{cases}(-1)^{(p-1)/8}&\text{if}\ p\equiv1\pmod8, \\(-1)^{|\{1\leqslant k<\frac p4:\ (\frac kp)=-1\}|}&\text{if}\ p\equiv5\pmod 8, \\(-1)^{(h(-p)+1)/2+|\{1\leqslant k\leqslant\lfloor\frac{p+1}8\rfloor:\ (\frac kp)=-1\}|}&\text{if}\ p\equiv3\pmod4. \end{cases}\end{align}

I have checked this conjecture via a computer. It should be valid in my opinion. Any comments are welcome!

Differences

A general useful fact (compare with my answer to your previous question) is that whenever we have $$A=\{a_1,\dots,a_n\}\subset \{0,1,\dots,p-1\}$$ such that $$n=|A|$$ is odd, the sign of a product $$\prod_{i does not depend on the choice of remainder $$\theta$$ modulo $$p$$. This may be proved using the observation $${\rm sign}\, \left(\{b-\theta\}_p-\{a-\theta\}_p\right)={\rm sign}\, \left(\{b\}_p-\{a\}_p\right)\cdot (-1)^{\chi(\{b\}_p<\theta)+\chi(\{a\}_p<\theta)}.$$ When you multiply this by all pairs $$b=a_j,a=a_i,i, each multiple $$(-1)^{\chi(\{a\}_p<\theta)}$$ appears exactly $$n-1$$ times, which is even.

Now you take $$n=(p-1)/2$$, $$a_j=T_{(p-1)/2-j}=\{-1/8+j^2/2\}_p$$, $$j$$ varies from 0 to $$(p-3)/2=n-1$$ and you look for the sign of $$\prod_{0\leqslant i (the order is inversed). This is the same as $$(-1)^{n\choose 2}\cdot {\rm sign}\, \prod_{0\leqslant i It is convenient to add $$j=n$$ and consider the product $$\prod_{0\leqslant i For finding its sign we exclude $$i=0$$ which does not rely on the sign and consider two cases.

1) $$p$$ is congruent to 7 modulo 8. In this case $$2$$ is a quadratic residue and the map $$x\mapsto x/2$$ permutes the (nonzero) quadratic residues. This permutation is even, because all cycles have the same odd length (dividing odd number $$(p-1)/2$$). On the other hand the sign of this permutation equals $${\rm sign}\,\prod_{1\leqslant i Therefore the numerator and the denominator have the same sign and we reduced the problem to the already solved in your paper.

2) $$p=8k+3$$. In this case -2 is a quadratic residue and we similarly get $${\rm sign}\,\prod_{1\leqslant i It remains to note that $${\rm sign}\, (\{j^2/2\}_p-\{i^2/2\}_p)=-{\rm sign}\, (\{-j^2/2\}_p-\{-i^2/2\}_p)$$ (and mind the multiple $$(-1)^{n\choose 2}$$, but it equals 1 for $$p=8k+3$$, $$n=4k+1$$).

The last thing to do is to study what we have added: the sign of $$\prod_{0\leqslant i. We have $$n^2/2\equiv 1/8$$. Again consider two cases.

1) $$p=8k+7$$, then $$1/8\equiv (p+1)/8$$ and we look for the number of quadratic residues (recall that $$i^2/2$$ is a quadratic resdiue) greater than $$(p+1)/8$$. This has the parity different from that of the number of quadratic residues at most $$(p+1)/8$$ (since the total number of quadratic residues is odd.) But we had also a sign $$(-1)^{n\choose 2}=-1$$ before. So we get your conjecture in this case.

1) $$p=8k+3$$. Then $$1/8\equiv (5p+1)/8$$ and we look for the number of quadratic non-residues greater than $$(5p+1)/8$$. This is the same as the number of quadratic residues less than $$(3p-1)/8$$. The permutation of squares mod $$p$$ is even (proved in your paper), and $$(-1)^{(h(-p)+1)/2}\equiv (4k+1)!$$ has the same parity as the number of quadratic non-residues in $$[1,p/2]$$ (take Legendre symbol). Thus we should prove the following: the number of non-residues in $$[1,4k+1]$$ plus the number of residues in $$[1,(3p-1)/8)$$ plus the number of residues in $$[1,p/8]$$ is even. This rewrites as (Residues in $$[1,p/2]$$)+(Residues in $$[1,3p/8]$$)+(Residues in $$[1,p/8]$$) is even, or: (Residues in $$[1,p/8]\cup [3p/8,p/2]$$) is even. This is the statement of Berndt -- Chowla type. Consider all the quadratic non-residues in $$(0,p/4)$$ (there are $$k$$ of them by Berndt -- Chowla) and divide them by $$2$$. Even non-residues go to residues in $$(0,p/8)$$ and odd non-residues go to residues in $$(p/2,5p/8)$$ which correspond to non-residues in $$(3p/8,p/2)$$. Therefore we get $$k=RES(0,p/8)+NONRES[3k+2,4k+1]=RES(0,p/8)+k-RES[3k+2,4k+1]$$ and so the segments $$[1,k]$$ and $$[3k+2,4k+1]$$ simply have equally many quadratic residues.

This proves your conjecture for this case also.

Sums greater than $$p$$.

Let me concentrate here on the case $$p=8k+1$$. Other cases should be similar, let me know if they are not.

The idea is the following identity, in which we use the notation $$\{\{a\}\}_p$$ which equals $$\{a\}_p$$ whenever $$\{a\}_p\ne 0$$ and equals $$p$$ whenever $$\{a\}_p=0$$: $$\chi_{\{u\}_p+\{v\}_p>p}=\frac1p\left( \{u\}_p+\{v\}_p-\{\{u+v\}\}_p \right).\,\,\,\,(*)$$ We take the set $$T=\{T_0,T_1,\dots,T_{4k}\}$$ (again I add $$T_0$$ but it does not affect to the parity we are interested in) and apply $$(*)$$ to all non-ordered pairs $$(u,v)$$ of different elements of $$T$$ and sum up. All guys $$\{u\}_p$$ go with coefficient $$4k$$, so do not affect on the parity. It remains to find the parity of the sum of $$\{u+v\}_p$$. Again use the representation $$T_j=\frac12(j+\frac12)^2-\frac18$$. When $$j$$ goes from 0 to $$4k$$, the expression $$\frac12(j+\frac12)^2$$ goes over the set $$R_0$$ consisting of quadratic residues and 0. Therefore $$f(a):=\left|(0\leqslant i And we are interested in the parity of $$\sum_{j=0}^{p-1}\{\{j-\frac14\}\}_p g(j)$$. Well, let's find $$g(a)$$ for any $$a$$, this is standard. We have $$g(0)=2k$$; $$g(a)=k$$ for $$a$$ not divisible by $$p$$. So we are interested in the parity of $$k\{\{-\frac14\}\}_p+k\sum_{j=0}^{p-1}\{\{j\}\}_p.$$ The first summand equals $$k\cdot 2k$$ and is even, the sum equals $$1+2+\dots+p=p(p+1)/2$$ and is odd, so totally the parity is the same as the parity of $$k$$.