# Is $|\{(j,k):\ 1\le j<k\le\frac{p-1}2:\ \&\ (j^{16}\ \text{mod}\ p)>(k^{16}\ \text{mod}\ p)\}|$ even for each prime $p\equiv1\pmod {16}$?

In my paper http://arxiv.org/abs/1809.07766, I determined the parity of $$\left|\left\{(j,k):\ 1\le j(k^2\ \text{mod}\ p)\right\}\right|$$ for any prime $$p\equiv3\pmod4$$, where $$(a\ \text{mod}\ p)$$ denotes the least nonnegative residue of $$a$$ modulo $$p$$.

Based on my computation, I have the following three conjectures.

Conjecture 1. For any prime $$p\equiv1\pmod4$$, we have $$\left|\left\{(j,k):\ 1\le j(k^4\ \text{mod}\ p)\right\}\right|\equiv\left\lfloor \frac{p-1}8\right\rfloor\pmod2.$$

Conjecture 2. For any prime $$p\equiv1\pmod8$$, we have $$\left|\left\{(j,k):\ 1\le j(k^8\ \text{mod}\ p)\right\}\right|\equiv\left|\left\{1\le k<\frac p4:\ \left(\frac kp\right)=1\right\}\right|\pmod2.$$

Conjecture 3. For any prime $$p\equiv1\pmod{16}$$, we have $$\left|\left\{(j,k):\ 1\le j(k^{16}\ \text{mod}\ p)\right\}\right|\equiv0\pmod2.$$

QUESTION. How to prove Conjectures 1-3?

The conjectures might not be very difficult. Maybe some of you could prove them. Your comments are welcome!

• A mathematical situation where $a \mod p$ genuinely means an integer, not just an element of $\mathbb Z/p\mathbb Z$, seems very rare. Why is it the right thing to do here? Aug 2 '19 at 21:48

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 Note that the multiset $$(1^4)_p,\ldots,(m^4)_p$$ consists of all $$4$$-th powers $$r_1<\ldots modulo $$p$$, each counted 2 times. Therefore the fraction $$B:=\frac{A}{\prod_{1\leqslant j 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. 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 Look at the product of $$k^{2}+j^{2}$$. Let $$0 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, we get once all the multiples $$\pm q_i\pm q_j$$, $$1\leqslant i. Their product is $$\prod_{1\leqslant i 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 is in the denominator for $$B$$, thus one such expression remains in the denominator.

Next, $$\prod_{1\leqslant j 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. 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, for which $$(j^{2}+k^2)_p=0$$. Assume that we have $$\alpha$$ pairs $$j 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 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 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]}$$.

• Thank you for the proof of Conjecture 1. Note that $\prod_{1\le j<k\le m\atop p\nmid j^2+k^2}(j^2+k^2)\equiv (-1)^{\lfloor(p-5)/8\rfloor}\pmod p$ for any prime $p\equiv 1\pmod 4$, by (1.7) of my paper (arXiv:1809.07766). Jul 7 '19 at 21:45
• Ah, indeed. By the way, Conjecture 2 may be proved in the same spirit, we need only to express the parity this number of residues in RHS via $2^{(p-1)/4}$ that is known (I guess belongs to Yamamoto). Jul 7 '19 at 22:17
• Conjecture 3 also follows. We get the same additional multiple as in Conjecture 2, and it cancels out. It looks like for 32 we again get the same parity as in conjecture 2, for 64 again 0 and so on. Jul 8 '19 at 9:44