Skip to main content
added 35 characters in body
Source Link
Fedor Petrov
  • 108.8k
  • 9
  • 264
  • 459

Start with Conjecture 1. Two other look similar, but possibly require additional ideas (UPDATE: they do not actually).

Write $(x)_p\in \{0,\ldots,p-1\}$ for the remainder of integer $x$ modulo $p$. Denote $p=2m+1$. We have to calculate the sign of $$ A:=\prod_{1\leqslant j<k\leqslant m,(j^4-k^4)_p\ne 0} ((k^4)_p -(j^4)_p). $$ Note that the multiset $(1^4)_p,\ldots,(m^4)_p$ consists of all $4$-th powers $r_1<\ldots<r_{m/2}\in \{1,\ldots,p-1\}$ modulo $p$, each counted 2 times. Therefore the fraction $$ B:=\frac{A}{\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{4}} $$ equals to $\pm 1$. Hence the sign of $A$ equals to $B$. And it suffices to calculate $B$ modulo $p$ (we already know that $B\in \{1,-1\}$).

We start with calculating the product $\prod_{j<k} (r_k-r_j)^2$. It is the discriminant of the polynomial $h(x)=x^{m/2}-1$, which equals $$(-1)^{{m/2\choose 2}}\prod_i h'(r_i)= (-1)^{{m/2 \choose 2}} (m/2)^{m/2}\prod r_i^{-1}=(-1)^{{m/2\choose 2}+m/2+1} (m/2)^{m/2}.$$ Since $m/2=-1/4$ modulo $p$, we get $(-1)^{{m/2\choose 2}+1}2^m$.

Start with the numerator. It is $$ A:=\prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0} (k^{2} -j^{2})(k^{2}+j^{2}). $$ Look at the product of $k^{2}+j^{2}$. Let $0<q_1<\dots<q_{m}<p$ be all non-zero squares modulo $p$. Of course $q_i+q_{m+1-i}=p$ for $i=1,\ldots,m$. Therefore among the sums $k^{2}+j^{2}$, $1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0$, we get once all the multiples $\pm q_i\pm q_j$, $1\leqslant i<j\leqslant m/2$. Their product is $$\prod_{1\leqslant i<j\leqslant m/2} (q_i^2-q_j^2)^{2}=\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{2},$$ since $q_i^2,1\leqslant i\leqslant m/2$, are exactly $r_1,\ldots,r_{m/2}$. The square of this product $\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{2}$ is in the denominator for $B$, thus one such expression remains in the denominator.

Next, $$ \prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0} (k^{2} -j^{2})= \prod_{1\leqslant j<k\leqslant m} (k^{2} -j^{2}) \cdot \prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2^{-1}k^{-2}. $$ The first product in RHS is known (see (1.5) in your paper) to be congruent to $-m!$ modulo $s$. Now about $\prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2k^{2}$. Fix a square root $w$ of -1. The residues $1,\ldots,m$ modulo $p$ are partitioned onto $m/2$ pairs with ratio $\pm w$, and these are exactly the pairs $1\leqslant j<k\leqslant m$, for which $(j^{2}+k^2)_p=0$. Assume that we have $\alpha$ pairs $j<k$ with ratio $k/j$ congruent to $-w$ modulo $p$, thus $m/2-\alpha$ pairs with ratio $+w$. Note that $k^2=(k/j)\cdot kj$. It yields
$$ \prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2k^{2}=(2w)^{m/2}(-1)^\alpha m! $$ For evaluating $(-1)^\alpha$, we use the following (I guess, known as everything related to quadratic reciprocity proofs)

Lemma. Let $\eta\in \{2,\ldots,p-1\}$ be a residue modulo prime number $p=2m+1$ ($m$ may be odd here), and $T$ is the number of pairs $1\leqslant j<k\leqslant m$ for which $j\equiv \eta\cdot k \pmod p$. $$1\leqslant j<k\leqslant m\,\,\,\text{for which}\,\,\, j\equiv \eta\cdot k \pmod p.\quad (\ast)$$ Then $$(-1)^T= \left(\frac{\eta(\eta-1)}p\right).$$

Proof of the lemma. For given $k$, the number of appropriate $j$ (it is either 0 or 1 of course) equals to the number of points divisible by $p$ in the segment exists if $[\eta\cdot k,(\eta-1)k]$: if $p\cdot z\in [\eta\cdot k,(\eta-1)k]$, then $j=\eta\cdot k-p\cdot z\in [0,k]$ workssatisfies $(\ast)$. So, it equals to $[\eta\cdot k/p]-[(\eta-1)k/p]$. Summing up by $k=1,2,\ldots,m$, we get $$ (-1)^T=(-1)^{\sum_{k=1}^m [\eta k/p]-\sum_{k=1}^m [(\eta-1) k/p]}=\left(\frac{\eta}p\right)\cdot \left(\frac{\eta-1}p\right) $$ by Gauss proof of Quadratic Reciprocity Law. Lemma is proved.

In our situation $\eta=-w$, $\eta^2-\eta=w-1$, $(w-1)^2=-2w$ and $$ (-1)^\alpha=\left(\frac{\eta(\eta-1)}p\right)=(w-1)^m=(-2w)^{m/2}. $$

Totally we get for $B$ the expression $(-1)^{m/2\choose 2}=(-1)^{[m/4]}$.

Start with Conjecture 1. Two other look similar, but possibly require additional ideas (UPDATE: they do not actually).

Write $(x)_p\in \{0,\ldots,p-1\}$ for the remainder of integer $x$ modulo $p$. Denote $p=2m+1$. We have to calculate the sign of $$ A:=\prod_{1\leqslant j<k\leqslant m,(j^4-k^4)_p\ne 0} ((k^4)_p -(j^4)_p). $$ Note that the multiset $(1^4)_p,\ldots,(m^4)_p$ consists of all $4$-th powers $r_1<\ldots<r_{m/2}\in \{1,\ldots,p-1\}$ modulo $p$, each counted 2 times. Therefore the fraction $$ B:=\frac{A}{\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{4}} $$ equals to $\pm 1$. Hence the sign of $A$ equals to $B$. And it suffices to calculate $B$ modulo $p$ (we already know that $B\in \{1,-1\}$).

We start with calculating the product $\prod_{j<k} (r_k-r_j)^2$. It is the discriminant of the polynomial $h(x)=x^{m/2}-1$, which equals $$(-1)^{{m/2\choose 2}}\prod_i h'(r_i)= (-1)^{{m/2 \choose 2}} (m/2)^{m/2}\prod r_i^{-1}=(-1)^{{m/2\choose 2}+m/2+1} (m/2)^{m/2}.$$ Since $m/2=-1/4$ modulo $p$, we get $(-1)^{{m/2\choose 2}+1}2^m$.

Start with the numerator. It is $$ A:=\prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0} (k^{2} -j^{2})(k^{2}+j^{2}). $$ Look at the product of $k^{2}+j^{2}$. Let $0<q_1<\dots<q_{m}<p$ be all non-zero squares modulo $p$. Of course $q_i+q_{m+1-i}=p$ for $i=1,\ldots,m$. Therefore among the sums $k^{2}+j^{2}$, $1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0$, we get once all the multiples $\pm q_i\pm q_j$, $1\leqslant i<j\leqslant m/2$. Their product is $$\prod_{1\leqslant i<j\leqslant m/2} (q_i^2-q_j^2)^{2}=\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{2},$$ since $q_i^2,1\leqslant i\leqslant m/2$, are exactly $r_1,\ldots,r_{m/2}$. The square of this product $\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{2}$ is in the denominator for $B$, thus one such expression remains in the denominator.

Next, $$ \prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0} (k^{2} -j^{2})= \prod_{1\leqslant j<k\leqslant m} (k^{2} -j^{2}) \cdot \prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2^{-1}k^{-2}. $$ The first product in RHS is known (see (1.5) in your paper) to be congruent to $-m!$ modulo $s$. Now about $\prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2k^{2}$. Fix a square root $w$ of -1. The residues $1,\ldots,m$ modulo $p$ are partitioned onto $m/2$ pairs with ratio $\pm w$, and these are exactly the pairs $1\leqslant j<k\leqslant m$, for which $(j^{2}+k^2)_p=0$. Assume that we have $\alpha$ pairs $j<k$ with ratio $k/j$ congruent to $-w$ modulo $p$, thus $m/2-\alpha$ pairs with ratio $+w$. Note that $k^2=(k/j)\cdot kj$. It yields
$$ \prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2k^{2}=(2w)^{m/2}(-1)^\alpha m! $$ For evaluating $(-1)^\alpha$, we use the following (I guess, known as everything related to quadratic reciprocity proofs)

Lemma. Let $\eta\in \{2,\ldots,p-1\}$ be a residue modulo prime number $p=2m+1$ ($m$ may be odd here), and $T$ is the number of pairs $1\leqslant j<k\leqslant m$ for which $j\equiv \eta\cdot k \pmod p$. Then $$(-1)^T= \left(\frac{\eta(\eta-1)}p\right).$$

Proof of the lemma. For given $k$, the number of appropriate $j$ (it is either 0 or 1 of course) equals to the number of points divisible by $p$ in the segment exists if $[\eta\cdot k,(\eta-1)k]$: if $p\cdot z\in [\eta\cdot k,(\eta-1)k]$, then $j=\eta\cdot k-p\cdot z\in [0,k]$ works. So, it equals to $[\eta\cdot k/p]-[(\eta-1)k/p]$. Summing up by $k=1,2,\ldots,m$, we get $$ (-1)^T=(-1)^{\sum_{k=1}^m [\eta k/p]-\sum_{k=1}^m [(\eta-1) k/p]}=\left(\frac{\eta}p\right)\cdot \left(\frac{\eta-1}p\right) $$ by Gauss proof of Quadratic Reciprocity Law. Lemma is proved.

In our situation $\eta=-w$, $\eta^2-\eta=w-1$, $(w-1)^2=-2w$ and $$ (-1)^\alpha=\left(\frac{\eta(\eta-1)}p\right)=(w-1)^m=(-2w)^{m/2}. $$

Totally we get for $B$ the expression $(-1)^{m/2\choose 2}=(-1)^{[m/4]}$.

Start with Conjecture 1. Two other look similar, but possibly require additional ideas (UPDATE: they do not actually).

Write $(x)_p\in \{0,\ldots,p-1\}$ for the remainder of integer $x$ modulo $p$. Denote $p=2m+1$. We have to calculate the sign of $$ A:=\prod_{1\leqslant j<k\leqslant m,(j^4-k^4)_p\ne 0} ((k^4)_p -(j^4)_p). $$ Note that the multiset $(1^4)_p,\ldots,(m^4)_p$ consists of all $4$-th powers $r_1<\ldots<r_{m/2}\in \{1,\ldots,p-1\}$ modulo $p$, each counted 2 times. Therefore the fraction $$ B:=\frac{A}{\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{4}} $$ equals to $\pm 1$. Hence the sign of $A$ equals to $B$. And it suffices to calculate $B$ modulo $p$ (we already know that $B\in \{1,-1\}$).

We start with calculating the product $\prod_{j<k} (r_k-r_j)^2$. It is the discriminant of the polynomial $h(x)=x^{m/2}-1$, which equals $$(-1)^{{m/2\choose 2}}\prod_i h'(r_i)= (-1)^{{m/2 \choose 2}} (m/2)^{m/2}\prod r_i^{-1}=(-1)^{{m/2\choose 2}+m/2+1} (m/2)^{m/2}.$$ Since $m/2=-1/4$ modulo $p$, we get $(-1)^{{m/2\choose 2}+1}2^m$.

Start with the numerator. It is $$ A:=\prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0} (k^{2} -j^{2})(k^{2}+j^{2}). $$ Look at the product of $k^{2}+j^{2}$. Let $0<q_1<\dots<q_{m}<p$ be all non-zero squares modulo $p$. Of course $q_i+q_{m+1-i}=p$ for $i=1,\ldots,m$. Therefore among the sums $k^{2}+j^{2}$, $1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0$, we get once all the multiples $\pm q_i\pm q_j$, $1\leqslant i<j\leqslant m/2$. Their product is $$\prod_{1\leqslant i<j\leqslant m/2} (q_i^2-q_j^2)^{2}=\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{2},$$ since $q_i^2,1\leqslant i\leqslant m/2$, are exactly $r_1,\ldots,r_{m/2}$. The square of this product $\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{2}$ is in the denominator for $B$, thus one such expression remains in the denominator.

Next, $$ \prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0} (k^{2} -j^{2})= \prod_{1\leqslant j<k\leqslant m} (k^{2} -j^{2}) \cdot \prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2^{-1}k^{-2}. $$ The first product in RHS is known (see (1.5) in your paper) to be congruent to $-m!$ modulo $s$. Now about $\prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2k^{2}$. Fix a square root $w$ of -1. The residues $1,\ldots,m$ modulo $p$ are partitioned onto $m/2$ pairs with ratio $\pm w$, and these are exactly the pairs $1\leqslant j<k\leqslant m$, for which $(j^{2}+k^2)_p=0$. Assume that we have $\alpha$ pairs $j<k$ with ratio $k/j$ congruent to $-w$ modulo $p$, thus $m/2-\alpha$ pairs with ratio $+w$. Note that $k^2=(k/j)\cdot kj$. It yields
$$ \prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2k^{2}=(2w)^{m/2}(-1)^\alpha m! $$ For evaluating $(-1)^\alpha$, we use the following (I guess, known as everything related to quadratic reciprocity proofs)

Lemma. Let $\eta\in \{2,\ldots,p-1\}$ be a residue modulo prime number $p=2m+1$ ($m$ may be odd here), and $T$ is the number of pairs $$1\leqslant j<k\leqslant m\,\,\,\text{for which}\,\,\, j\equiv \eta\cdot k \pmod p.\quad (\ast)$$ Then $$(-1)^T= \left(\frac{\eta(\eta-1)}p\right).$$

Proof of the lemma. For given $k$, the number of appropriate $j$ (it is either 0 or 1 of course) equals to the number of points divisible by $p$ in the segment $[\eta\cdot k,(\eta-1)k]$: if $p\cdot z\in [\eta\cdot k,(\eta-1)k]$, then $j=\eta\cdot k-p\cdot z\in [0,k]$ satisfies $(\ast)$. So, it equals to $[\eta\cdot k/p]-[(\eta-1)k/p]$. Summing up by $k=1,2,\ldots,m$, we get $$ (-1)^T=(-1)^{\sum_{k=1}^m [\eta k/p]-\sum_{k=1}^m [(\eta-1) k/p]}=\left(\frac{\eta}p\right)\cdot \left(\frac{\eta-1}p\right) $$ by Gauss proof of Quadratic Reciprocity Law. Lemma is proved.

In our situation $\eta=-w$, $\eta^2-\eta=w-1$, $(w-1)^2=-2w$ and $$ (-1)^\alpha=\left(\frac{\eta(\eta-1)}p\right)=(w-1)^m=(-2w)^{m/2}. $$

Totally we get for $B$ the expression $(-1)^{m/2\choose 2}=(-1)^{[m/4]}$.

added 35 characters in body
Source Link
Fedor Petrov
  • 108.8k
  • 9
  • 264
  • 459

Start with Conjecture 1. Two other look similar, but possibly require additional ideas (UPDATE: they do not actually). 

Write $(x)_p\in \{0,\ldots,p-1\}$ for the remainder of integer $x$ modulo $p$. Denote $p=2m+1$. We have to calculate the sign of $$ A:=\prod_{1\leqslant j<k\leqslant m,(j^4-k^4)_p\ne 0} ((k^4)_p -(j^4)_p). $$ Note that the multiset $(1^4)_p,\ldots,(m^4)_p$ consists of all $4$-th powers $r_1<\ldots<r_{m/2}\in \{1,\ldots,p-1\}$ modulo $p$, each counted 2 times. Therefore the fraction $$ B:=\frac{A}{\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{4}} $$ equals to $\pm 1$. Hence the sign of $A$ equals to $B$. And it suffices to calculate $B$ modulo $p$ (we already know that $B\in \{1,-1\}$).

We start with calculating the product $\prod_{j<k} (r_k-r_j)^2$. It is the discriminant of the polynomial $h(x)=x^{m/2}-1$, which equals $$(-1)^{{m/2\choose 2}}\prod_i h'(r_i)= (-1)^{{m/2 \choose 2}} (m/2)^{m/2}\prod r_i^{-1}=(-1)^{{m/2\choose 2}+m/2+1} (m/2)^{m/2}.$$ Since $m/2=-1/4$ modulo $p$, we get $(-1)^{{m/2\choose 2}+1}2^m$.

Start with the numerator. It is $$ A:=\prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0} (k^{2} -j^{2})(k^{2}+j^{2}). $$ Look at the product of $k^{2}+j^{2}$. Let $0<q_1<\dots<q_{m}<p$ be all non-zero squares modulo $p$. Of course $q_i+q_{m+1-i}=p$ for $i=1,\ldots,m$. Therefore among the sums $k^{2}+j^{2}$, $1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0$, we get once all the multiples $\pm q_i\pm q_j$, $1\leqslant i<j\leqslant m/2$. Their product is $$\prod_{1\leqslant i<j\leqslant m/2} (q_i^2-q_j^2)^{2}=\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{2},$$ since $q_i^2,1\leqslant i\leqslant m/2$, are exactly $r_1,\ldots,r_{m/2}$. The square of this product $\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{2}$ is in the denominator for $B$, thus one such expression remains in the denominator.

Next, $$ \prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0} (k^{2} -j^{2})= \prod_{1\leqslant j<k\leqslant m} (k^{2} -j^{2}) \cdot \prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2^{-1}k^{-2}. $$ The first product in RHS is known (see (1.5) in your paper) to be congruent to $-m!$ modulo $s$. Now about $\prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2k^{2}$. Fix a square root $w$ of -1. The residues $1,\ldots,m$ modulo $p$ are partitioned onto $m/2$ pairs with ratio $\pm w$, and these are exactly the pairs $1\leqslant j<k\leqslant m$, for which $(j^{2}+k^2)_p=0$. Assume that we have $\alpha$ pairs $j<k$ with ratio $k/j$ congruent to $-w$ modulo $p$, thus $m/2-\alpha$ pairs with ratio $+w$. Note that $k^2=(k/j)\cdot kj$. It yields
$$ \prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2k^{2}=(2w)^{m/2}(-1)^\alpha m! $$ For evaluating $(-1)^\alpha$, we use the following (I guess, known as everything related to quadratic reciprocity proofs)

Lemma. Let $\eta\in \{2,\ldots,p-1\}$ be a residue modulo prime number $p=2m+1$ ($m$ may be odd here), and $T$ is the number of pairs $1\leqslant j<k\leqslant m$ for which $j\equiv \eta\cdot k \pmod p$. Then $$(-1)^T= \left(\frac{\eta(\eta-1)}p\right).$$

Proof of the lemma. For given $k$, the number of appropriate $j$ (it is either 0 or 1 of course) equals to the number of points divisible by $p$ in the segment exists if $[\eta\cdot k,(\eta-1)k]$: if $p\cdot z\in [\eta\cdot k,(\eta-1)k]$, then $j=\eta\cdot k-p\cdot z\in [0,k]$ works. So, it equals to $[\eta\cdot k/p]-[(\eta-1)k/p]$. Summing up by $k=1,2,\ldots,m$, we get $$ (-1)^T=(-1)^{\sum_{k=1}^m [\eta k/p]-\sum_{k=1}^m [(\eta-1) k/p]}=\left(\frac{\eta}p\right)\cdot \left(\frac{\eta-1}p\right) $$ by Gauss proof of Quadratic Reciprocity Law. Lemma is proved.

In our situation $\eta=-w$, $\eta^2-\eta=w-1$, $(w-1)^2=-2w$ and $$ (-1)^\alpha=\left(\frac{\eta(\eta-1)}p\right)=(w-1)^m=(-2w)^{m/2}. $$

Totally we get for $B$ the expression $(-1)^{m/2\choose 2}=(-1)^{[m/4]}$.

Start with Conjecture 1. Two other look similar, but possibly require additional ideas. Write $(x)_p\in \{0,\ldots,p-1\}$ for the remainder of integer $x$ modulo $p$. Denote $p=2m+1$. We have to calculate the sign of $$ A:=\prod_{1\leqslant j<k\leqslant m,(j^4-k^4)_p\ne 0} ((k^4)_p -(j^4)_p). $$ Note that the multiset $(1^4)_p,\ldots,(m^4)_p$ consists of all $4$-th powers $r_1<\ldots<r_{m/2}\in \{1,\ldots,p-1\}$ modulo $p$, each counted 2 times. Therefore the fraction $$ B:=\frac{A}{\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{4}} $$ equals to $\pm 1$. Hence the sign of $A$ equals to $B$. And it suffices to calculate $B$ modulo $p$ (we already know that $B\in \{1,-1\}$).

We start with calculating the product $\prod_{j<k} (r_k-r_j)^2$. It is the discriminant of the polynomial $h(x)=x^{m/2}-1$, which equals $$(-1)^{{m/2\choose 2}}\prod_i h'(r_i)= (-1)^{{m/2 \choose 2}} (m/2)^{m/2}\prod r_i^{-1}=(-1)^{{m/2\choose 2}+m/2+1} (m/2)^{m/2}.$$ Since $m/2=-1/4$ modulo $p$, we get $(-1)^{{m/2\choose 2}+1}2^m$.

Start with the numerator. It is $$ A:=\prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0} (k^{2} -j^{2})(k^{2}+j^{2}). $$ Look at the product of $k^{2}+j^{2}$. Let $0<q_1<\dots<q_{m}<p$ be all non-zero squares modulo $p$. Of course $q_i+q_{m+1-i}=p$ for $i=1,\ldots,m$. Therefore among the sums $k^{2}+j^{2}$, $1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0$, we get once all the multiples $\pm q_i\pm q_j$, $1\leqslant i<j\leqslant m/2$. Their product is $$\prod_{1\leqslant i<j\leqslant m/2} (q_i^2-q_j^2)^{2}=\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{2},$$ since $q_i^2,1\leqslant i\leqslant m/2$, are exactly $r_1,\ldots,r_{m/2}$. The square of this product $\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{2}$ is in the denominator for $B$, thus one such expression remains in the denominator.

Next, $$ \prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0} (k^{2} -j^{2})= \prod_{1\leqslant j<k\leqslant m} (k^{2} -j^{2}) \cdot \prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2^{-1}k^{-2}. $$ The first product in RHS is known (see (1.5) in your paper) to be congruent to $-m!$ modulo $s$. Now about $\prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2k^{2}$. Fix a square root $w$ of -1. The residues $1,\ldots,m$ modulo $p$ are partitioned onto $m/2$ pairs with ratio $\pm w$, and these are exactly the pairs $1\leqslant j<k\leqslant m$, for which $(j^{2}+k^2)_p=0$. Assume that we have $\alpha$ pairs $j<k$ with ratio $k/j$ congruent to $-w$ modulo $p$, thus $m/2-\alpha$ pairs with ratio $+w$. Note that $k^2=(k/j)\cdot kj$. It yields
$$ \prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2k^{2}=(2w)^{m/2}(-1)^\alpha m! $$ For evaluating $(-1)^\alpha$, we use the following (I guess, known as everything related to quadratic reciprocity proofs)

Lemma. Let $\eta\in \{2,\ldots,p-1\}$ be a residue modulo prime number $p=2m+1$ ($m$ may be odd here), and $T$ is the number of pairs $1\leqslant j<k\leqslant m$ for which $j\equiv \eta\cdot k \pmod p$. Then $$(-1)^T= \left(\frac{\eta(\eta-1)}p\right).$$

Proof of the lemma. For given $k$, the number of appropriate $j$ (it is either 0 or 1 of course) equals to the number of points divisible by $p$ in the segment exists if $[\eta\cdot k,(\eta-1)k]$: if $p\cdot z\in [\eta\cdot k,(\eta-1)k]$, then $j=\eta\cdot k-p\cdot z\in [0,k]$ works. So, it equals to $[\eta\cdot k/p]-[(\eta-1)k/p]$. Summing up by $k=1,2,\ldots,m$, we get $$ (-1)^T=(-1)^{\sum_{k=1}^m [\eta k/p]-\sum_{k=1}^m [(\eta-1) k/p]}=\left(\frac{\eta}p\right)\cdot \left(\frac{\eta-1}p\right) $$ by Gauss proof of Quadratic Reciprocity Law. Lemma is proved.

In our situation $\eta=-w$, $\eta^2-\eta=w-1$, $(w-1)^2=-2w$ and $$ (-1)^\alpha=\left(\frac{\eta(\eta-1)}p\right)=(w-1)^m=(-2w)^{m/2}. $$

Totally we get for $B$ the expression $(-1)^{m/2\choose 2}=(-1)^{[m/4]}$.

Start with Conjecture 1. Two other look similar, but possibly require additional ideas (UPDATE: they do not actually). 

Write $(x)_p\in \{0,\ldots,p-1\}$ for the remainder of integer $x$ modulo $p$. Denote $p=2m+1$. We have to calculate the sign of $$ A:=\prod_{1\leqslant j<k\leqslant m,(j^4-k^4)_p\ne 0} ((k^4)_p -(j^4)_p). $$ Note that the multiset $(1^4)_p,\ldots,(m^4)_p$ consists of all $4$-th powers $r_1<\ldots<r_{m/2}\in \{1,\ldots,p-1\}$ modulo $p$, each counted 2 times. Therefore the fraction $$ B:=\frac{A}{\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{4}} $$ equals to $\pm 1$. Hence the sign of $A$ equals to $B$. And it suffices to calculate $B$ modulo $p$ (we already know that $B\in \{1,-1\}$).

We start with calculating the product $\prod_{j<k} (r_k-r_j)^2$. It is the discriminant of the polynomial $h(x)=x^{m/2}-1$, which equals $$(-1)^{{m/2\choose 2}}\prod_i h'(r_i)= (-1)^{{m/2 \choose 2}} (m/2)^{m/2}\prod r_i^{-1}=(-1)^{{m/2\choose 2}+m/2+1} (m/2)^{m/2}.$$ Since $m/2=-1/4$ modulo $p$, we get $(-1)^{{m/2\choose 2}+1}2^m$.

Start with the numerator. It is $$ A:=\prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0} (k^{2} -j^{2})(k^{2}+j^{2}). $$ Look at the product of $k^{2}+j^{2}$. Let $0<q_1<\dots<q_{m}<p$ be all non-zero squares modulo $p$. Of course $q_i+q_{m+1-i}=p$ for $i=1,\ldots,m$. Therefore among the sums $k^{2}+j^{2}$, $1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0$, we get once all the multiples $\pm q_i\pm q_j$, $1\leqslant i<j\leqslant m/2$. Their product is $$\prod_{1\leqslant i<j\leqslant m/2} (q_i^2-q_j^2)^{2}=\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{2},$$ since $q_i^2,1\leqslant i\leqslant m/2$, are exactly $r_1,\ldots,r_{m/2}$. The square of this product $\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{2}$ is in the denominator for $B$, thus one such expression remains in the denominator.

Next, $$ \prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0} (k^{2} -j^{2})= \prod_{1\leqslant j<k\leqslant m} (k^{2} -j^{2}) \cdot \prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2^{-1}k^{-2}. $$ The first product in RHS is known (see (1.5) in your paper) to be congruent to $-m!$ modulo $s$. Now about $\prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2k^{2}$. Fix a square root $w$ of -1. The residues $1,\ldots,m$ modulo $p$ are partitioned onto $m/2$ pairs with ratio $\pm w$, and these are exactly the pairs $1\leqslant j<k\leqslant m$, for which $(j^{2}+k^2)_p=0$. Assume that we have $\alpha$ pairs $j<k$ with ratio $k/j$ congruent to $-w$ modulo $p$, thus $m/2-\alpha$ pairs with ratio $+w$. Note that $k^2=(k/j)\cdot kj$. It yields
$$ \prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2k^{2}=(2w)^{m/2}(-1)^\alpha m! $$ For evaluating $(-1)^\alpha$, we use the following (I guess, known as everything related to quadratic reciprocity proofs)

Lemma. Let $\eta\in \{2,\ldots,p-1\}$ be a residue modulo prime number $p=2m+1$ ($m$ may be odd here), and $T$ is the number of pairs $1\leqslant j<k\leqslant m$ for which $j\equiv \eta\cdot k \pmod p$. Then $$(-1)^T= \left(\frac{\eta(\eta-1)}p\right).$$

Proof of the lemma. For given $k$, the number of appropriate $j$ (it is either 0 or 1 of course) equals to the number of points divisible by $p$ in the segment exists if $[\eta\cdot k,(\eta-1)k]$: if $p\cdot z\in [\eta\cdot k,(\eta-1)k]$, then $j=\eta\cdot k-p\cdot z\in [0,k]$ works. So, it equals to $[\eta\cdot k/p]-[(\eta-1)k/p]$. Summing up by $k=1,2,\ldots,m$, we get $$ (-1)^T=(-1)^{\sum_{k=1}^m [\eta k/p]-\sum_{k=1}^m [(\eta-1) k/p]}=\left(\frac{\eta}p\right)\cdot \left(\frac{\eta-1}p\right) $$ by Gauss proof of Quadratic Reciprocity Law. Lemma is proved.

In our situation $\eta=-w$, $\eta^2-\eta=w-1$, $(w-1)^2=-2w$ and $$ (-1)^\alpha=\left(\frac{\eta(\eta-1)}p\right)=(w-1)^m=(-2w)^{m/2}. $$

Totally we get for $B$ the expression $(-1)^{m/2\choose 2}=(-1)^{[m/4]}$.

Source Link
Fedor Petrov
  • 108.8k
  • 9
  • 264
  • 459

Start with Conjecture 1. Two other look similar, but possibly require additional ideas. Write $(x)_p\in \{0,\ldots,p-1\}$ for the remainder of integer $x$ modulo $p$. Denote $p=2m+1$. We have to calculate the sign of $$ A:=\prod_{1\leqslant j<k\leqslant m,(j^4-k^4)_p\ne 0} ((k^4)_p -(j^4)_p). $$ Note that the multiset $(1^4)_p,\ldots,(m^4)_p$ consists of all $4$-th powers $r_1<\ldots<r_{m/2}\in \{1,\ldots,p-1\}$ modulo $p$, each counted 2 times. Therefore the fraction $$ B:=\frac{A}{\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{4}} $$ equals to $\pm 1$. Hence the sign of $A$ equals to $B$. And it suffices to calculate $B$ modulo $p$ (we already know that $B\in \{1,-1\}$).

We start with calculating the product $\prod_{j<k} (r_k-r_j)^2$. It is the discriminant of the polynomial $h(x)=x^{m/2}-1$, which equals $$(-1)^{{m/2\choose 2}}\prod_i h'(r_i)= (-1)^{{m/2 \choose 2}} (m/2)^{m/2}\prod r_i^{-1}=(-1)^{{m/2\choose 2}+m/2+1} (m/2)^{m/2}.$$ Since $m/2=-1/4$ modulo $p$, we get $(-1)^{{m/2\choose 2}+1}2^m$.

Start with the numerator. It is $$ A:=\prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0} (k^{2} -j^{2})(k^{2}+j^{2}). $$ Look at the product of $k^{2}+j^{2}$. Let $0<q_1<\dots<q_{m}<p$ be all non-zero squares modulo $p$. Of course $q_i+q_{m+1-i}=p$ for $i=1,\ldots,m$. Therefore among the sums $k^{2}+j^{2}$, $1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0$, we get once all the multiples $\pm q_i\pm q_j$, $1\leqslant i<j\leqslant m/2$. Their product is $$\prod_{1\leqslant i<j\leqslant m/2} (q_i^2-q_j^2)^{2}=\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{2},$$ since $q_i^2,1\leqslant i\leqslant m/2$, are exactly $r_1,\ldots,r_{m/2}$. The square of this product $\prod_{1\leqslant j<k\leqslant m/2}(r_k-r_j)^{2}$ is in the denominator for $B$, thus one such expression remains in the denominator.

Next, $$ \prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p\ne 0} (k^{2} -j^{2})= \prod_{1\leqslant j<k\leqslant m} (k^{2} -j^{2}) \cdot \prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2^{-1}k^{-2}. $$ The first product in RHS is known (see (1.5) in your paper) to be congruent to $-m!$ modulo $s$. Now about $\prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2k^{2}$. Fix a square root $w$ of -1. The residues $1,\ldots,m$ modulo $p$ are partitioned onto $m/2$ pairs with ratio $\pm w$, and these are exactly the pairs $1\leqslant j<k\leqslant m$, for which $(j^{2}+k^2)_p=0$. Assume that we have $\alpha$ pairs $j<k$ with ratio $k/j$ congruent to $-w$ modulo $p$, thus $m/2-\alpha$ pairs with ratio $+w$. Note that $k^2=(k/j)\cdot kj$. It yields
$$ \prod_{1\leqslant j<k\leqslant m,(j^{2}+k^2)_p=0} 2k^{2}=(2w)^{m/2}(-1)^\alpha m! $$ For evaluating $(-1)^\alpha$, we use the following (I guess, known as everything related to quadratic reciprocity proofs)

Lemma. Let $\eta\in \{2,\ldots,p-1\}$ be a residue modulo prime number $p=2m+1$ ($m$ may be odd here), and $T$ is the number of pairs $1\leqslant j<k\leqslant m$ for which $j\equiv \eta\cdot k \pmod p$. Then $$(-1)^T= \left(\frac{\eta(\eta-1)}p\right).$$

Proof of the lemma. For given $k$, the number of appropriate $j$ (it is either 0 or 1 of course) equals to the number of points divisible by $p$ in the segment exists if $[\eta\cdot k,(\eta-1)k]$: if $p\cdot z\in [\eta\cdot k,(\eta-1)k]$, then $j=\eta\cdot k-p\cdot z\in [0,k]$ works. So, it equals to $[\eta\cdot k/p]-[(\eta-1)k/p]$. Summing up by $k=1,2,\ldots,m$, we get $$ (-1)^T=(-1)^{\sum_{k=1}^m [\eta k/p]-\sum_{k=1}^m [(\eta-1) k/p]}=\left(\frac{\eta}p\right)\cdot \left(\frac{\eta-1}p\right) $$ by Gauss proof of Quadratic Reciprocity Law. Lemma is proved.

In our situation $\eta=-w$, $\eta^2-\eta=w-1$, $(w-1)^2=-2w$ and $$ (-1)^\alpha=\left(\frac{\eta(\eta-1)}p\right)=(w-1)^m=(-2w)^{m/2}. $$

Totally we get for $B$ the expression $(-1)^{m/2\choose 2}=(-1)^{[m/4]}$.