Return to Answer

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<j\leqslant 4k):T_i+T_j\equiv a\right|=\\ \left|(0\leqslant i<j\leqslant 4k):i^2+j^2\equiv a+\frac14\right|=:g(a+\frac14).$$ 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$ is odd, so totally the parity is the same as the parity of $k$.

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<j\leqslant 4k):T_i+T_j\equiv a\right|=\\ \left|(0\leqslant i<j\leqslant 4k):i^2+j^2\equiv a+\frac14\right|=:g(a+\frac14).$$ 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$.

This proves the conjecture about differences of triangular numbers (not sums).

This proves your conjecture for this case also.

Differences

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<j\leqslant 4k):T_i+T_j\equiv a\right|=\\ \left|(0\leqslant i<j\leqslant 4k):i^2+j^2\equiv a+\frac14\right|=:g(a+\frac14).$$ 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$ is odd, so totally the parity is the same as the parity of $k$.

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<j}(\{a_j-\theta\}_p-\{a_i-\theta\}_p)$ 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<j$, 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<j\leqslant n-1} (a_i-a_j)$ (the order is inversed). This is the same as $$(-1)^{n\choose 2}\cdot {\rm sign}\, \prod_{0\leqslant i<j\leqslant n-1} (a_j-a_i)=(-1)^{n\choose 2}\cdot {\rm sign}\, \prod_{0\leqslant i<j\leqslant n-1} \left(\{j^2/2\}_p-\{i^2/2\}_p\right).$$ It is convenient to add $j=n$ and consider the product $$ \prod_{0\leqslant i<j\leqslant n} \left(\{j^2/2\}_p-\{i^2/2\}_p\right). $$ 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<j\leqslant n} \frac{\{j^2/2\}_p-\{i^2/2\}_p}{\{j^2\}_p-\{i^2\}_p}. $$ 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<j\leqslant n} \frac{\{-j^2/2\}_p-\{-i^2/2\}_p}{\{j^2\}_p-\{i^2\}_p}=1. $$ 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<n}(\{n^2/2\}_p-\{i^2/2\}_p)$. 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.

2. $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$.

This proves the conjecture about differences of triangular numbers (not sums).

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<j}(\{a_j-\theta\}_p-\{a_i-\theta\}_p)$ 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<j$, 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<j\leqslant n-1} (a_i-a_j)$ (the order is inversed). This is the same as $$(-1)^{n\choose 2}\cdot {\rm sign}\, \prod_{0\leqslant i<j\leqslant n-1} (a_j-a_i)=(-1)^{n\choose 2}\cdot {\rm sign}\, \prod_{0\leqslant i<j\leqslant n-1} \left(\{j^2/2\}_p-\{i^2/2\}_p\right).$$ It is convenient to add $j=n$ and consider the product $$ \prod_{0\leqslant i<j\leqslant n} \left(\{j^2/2\}_p-\{i^2/2\}_p\right). $$ 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<j\leqslant n} \frac{\{j^2/2\}_p-\{i^2/2\}_p}{\{j^2\}_p-\{i^2\}_p}. $$ 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<j\leqslant n} \frac{\{-j^2/2\}_p-\{-i^2/2\}_p}{\{j^2\}_p-\{i^2\}_p}=1. $$ 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<n}(\{n^2/2\}_p-\{i^2/2\}_p)$. 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.

2. $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.