login
A319903
Number of ordered pairs (i,j) with 0 < i < j < prime(n)/2 such that (i^8 mod prime(n)) > (j^8 mod prime(n)).
2
0, 0, 1, 2, 7, 5, 10, 22, 45, 48, 68, 53, 104, 127, 146, 200, 203, 250, 288, 312, 387, 318, 450, 557, 536, 745, 664, 581, 722, 797, 986, 1011, 1082, 1474, 1294, 1317, 1608, 1684, 1893, 2096, 1898, 2297, 2333, 2090, 2467, 2652, 2836, 3352, 3698, 3326, 3380, 2981, 3778, 3902, 4165, 4743, 4350, 4652, 4240
OFFSET
2,4
COMMENTS
Conjecture 1: Let p be an odd prime, and let N be the number of ordered pairs (i,j) with 0 < i < j < p/2 and (i^8 mod p) > (j^8 mod p). When p == 1 (mod 8), we have 2 | N if and only if 2 is a quartic residue modulo p. Also, N is even if p == 3 (mod 8). When p == 5 (mod 8), we have N == (p-5)/8 (mod 2). If p == 7 (mod 8) then N == (h(-p)+1)/2 (mod 2), where h(-p) is the class number of the imaginary quadratic field Q(sqrt(-p)).
Conjecture 2: Let p be an odd prime, and let N' be the number of ordered pairs (i,j) with 0 < i < j < p/2 and R(i^8,p) > R(j^8,p), where R(k,p) denotes the unique integer r among 0,...,(p-1)/2 with k congruent to r or -r modulo p. When p == 9 (mod 16), we have 2 | N' if and only if 2 is a quartic residue modulo p. Also, N' == floor((p+1)/8) (mod 2) if p is not congruent to 9 modulo 16.
See also A319311, A319480, A319882 and A319894 for similar conjectures.
LINKS
Zhi-Wei Sun, Quadratic residues and related permutations, arXiv:1809.07766 [math.NT], 2018.
EXAMPLE
a(4) = 1 since prime(4) = 7, and (R(1^8,7),R(2^8,7),R(3^8,7)) = (1,3,2) with R(2^8,7) > R(3^8,7).
a(5) = 2 since prime(5) = 11, and (R(1^8,11),...,R(5^8,11)) = (1,3,5,2,4) with R(2^8,11) > R(4^8,11), R(3^8,11) > R(4^8,11) and R(3^8,11) > R(5^8,11).
MATHEMATICA
f[k_, p_]:=f[k, p]=PowerMod[k, 8, p]; Inv[p_]:=Inv[p]=Sum[Boole[f[i, p]>f[j, p]], {j, 2, (p-1)/2}, {i, 1, j-1}]; Table[Inv[Prime[n]], {n, 2, 60}]
CROSSREFS
KEYWORD
nonn
AUTHOR
Zhi-Wei Sun, Oct 01 2018
STATUS
approved