Permutations involving squares in finite fields

1.   Introduction

Permutation is an important mathematical concept. Investigating permutations over finite fields is a classical topic in number theory, combinatorics and finite fields. Let $g(x)$ be a polynomial over a ring $R$. We say that $g(x)$ is a permutation polynomial if it acts as a permutation of all elements of the ring, i.e., the map

is a bijection over $R$. By the Lagrange interpolation formula it is easy to see that every permutation over a finite field is induced by a permutation polynomial (for the recent progress on permutation polynomial readers may refer to the survey paper ^[1]).

Now we introduce some earlier work on this topic. Let $p$ be an odd prime and let $a\in\mathbb{Z}$ with $p\nmid a$. Clearly $f_a(x) = ax$ is a permutation polynomial over $\mathbb{Z}/p\mathbb{Z} = \mathbb{F}_p$. The famous Zolotarev lemma ^[2] says that the sign of the permutation on $\mathbb{F}_p$ induced by $f_a(x)$ coincides with the Legendre symbol $(\frac{a}{p})$. This fact provides us with a different proof (see ^[3,4]) of the law of quadratic reciprocity. Later G. Frobenius ^[5] generalized Zolotarev's result to the Jacobi symbols. Readers may refer to ^[6,7] for more related information.

Let $k$ be a positive integer with $\gcd(k, p-1) = 1$. Then clearly the polynomial $g_k(x) = x^k$ is a permutation polynomial over $\mathbb{F}_p$. The authors ^[8] determined the sign of this permutation induced by $g_k(x)$ via extending the method of Zolotarev. Moreover, with the tools in group representation theory, Duke and Hopkins ^[9] generalized this result to finite groups. They also gave the law of quadratic reciprocity on finite groups.

Recently, Sun ^[10,11] studied some permutations involving squares in $\mathbb{F}_p$. For example, let $p = 2n+1$ be an odd prime and let $b_1, \cdots, b_n$ be the sequence of all the $n$ quadratic residues among $1, \cdots, p-1$ in ascending order. Then it is easy to see that the sequence

is a permutation $\tau_p$ of

where $\overline{a}$ denotes the element $a\ {\rm{mod}}\ p\mathbb{Z}$ for each $a\in\mathbb{Z}.$ Sun showed that

where $h(-p)$ is the class number of $\mathbb{Q}(\sqrt{-p})$ and ${{{{\rm{sgn}}}}}(\tau_p)$ denotes the sign of $\tau_p$. While studying this topic, Sun and his collaborator ^[10,12] also determined some products which concerns $p$th roots of unity. For instance, in the case $p\equiv3\pmod4$ Sun ^[10] obtained

Later Petrov and Sun ^[12] showed that if $p\equiv1\pmod8,$ then

and that if $p\equiv 5\pmod 8$, then

where $\#S$ denotes the cardinality of a set $S$ and $h(p)$ is the class number of $\mathbb{Q}(\sqrt{p})$. These products have close connections with permutations over $\mathbb{F}_p$. Readers may consult ^[10,12] for details.

Along this line, the first author ^[13] determined the sign of $\tau_p$ in the case $p\equiv 1\pmod4$. Motivated by Sun's work, the first author also studied some permutations on $\mathbb{F}_p$ involving primitive roots modulo $p$. In fact, let $g_p\in\mathbb{Z}$ be a primitive root modulo $p$. Then the sequence

is a permutation on the sequence (1.2). In ^[13] the first author gave the sign of this permutation in the case $p\equiv1\pmod4$.

Recently Sun posed the following problem:

In an arbitrary finite field $\mathbb{F}_q$ with $2\nmid q$, can we get an analogue of the above permutation which involves non-zero squares over $\mathbb{F}_q$?

In this paper, we mainly generalize the above permutations to $\mathbb{F}_{p^2}$. To do this, we first need to construct two sequences of non-zero squares in $\mathbb{F}_{p^2}$ which are analogues of the sequences (1.1) and (1.4). We now introduce some notations and some basic facts involving local fields.

Let $p = 2n+1$ be an odd prime, and let $\zeta_{p^2-1}$ be a primitive $(p^2-1)$th root of unity in the algebraic closure $\overline{\mathbb{Q}_p}$ of $\mathbb{Q}_p$. By [14,p.158 Propositon 7.12] it is easy to see that $[\mathbb{Q}_p(\zeta_{p^2-1}):\mathbb{Q}_p] = 2$ and that the integral closure of $\mathbb{Z}_p$ in $\mathbb{Q}_p(\zeta_{p^2-1})$ is $\mathbb{Z}_p[\zeta_{p^2-1}]$. Noting that $p\mathbb{Z}_p$ is unramified in $\mathbb{Q}_p(\zeta_{p^2-1})$, we therefore obtain $\mathbb{Z}_p[\zeta_{p^2-1}]/p\mathbb{Z}_p[\zeta_{p^2-1}]\cong \mathbb{F}_{p^2}$. Let $\Delta\equiv3\pmod4$ be an arbitrary quadratic non-residue modulo $p$ in $\mathbb{Z}$. Then clearly $p$ is inert in the field $\mathbb{Q}(\sqrt{\Delta})$. Hence $\mathbb{Z}[\sqrt{\Delta}]/p\mathbb{Z}[\sqrt{\Delta}]\cong \mathbb{F}_{p^2}.$ Since $\mathbb{Q}_p(\zeta_{p^2-1})$ and $\mathbb{Q}_p(\sqrt{\Delta})$ are both quadratic unramified extensions of $\mathbb{Q}_p$, by the local existence theorem (cf. [14,p.321 Theorem 1.4]) we have

By the structure of the unit group of a local field (cf. [14,p.136,Proposition 5.3]) we have

where $\mathbb{Z}_p[\zeta_{p^2-1}]^{\times}$ denotes the group of all invertible elements in $\mathbb{Z}_p[\zeta_{p^2-1}]$ and $\langle\zeta_{p^2-1}\rangle = \{\zeta_{p^2-1}^k: k\in\mathbb{Z}\}.$ Hence we can let $g\in\mathbb{Z}_p[\zeta_{p^2-1}]$ be a primitive root modulo $p\mathbb{Z}_p[\zeta_{p^2-1}]$ with $g\equiv \zeta_{p^2-1}\pmod {p\mathbb{Z}_p[\zeta_{p^2-1}]}$. For all $x\in\mathbb{Z}[\sqrt{\Delta}]$ and $y\in\mathbb{Z}_p[\zeta_{p^2-1}]$ we use the symbols $\bar{x}$ and $\bar{y}$ to denote the elements $x\ {\rm{mod}}\ p\mathbb{Z}[\sqrt{\Delta}]$ and $y\ {\rm{mod}}\ p\mathbb{Z}_p[\zeta_{p^2-1}]$ respectively.

Set $a_k = k+\sqrt{\Delta}$ for $0\le k\le p-1$. Then it is easy to verify that

is a complete system of representatives of

By the isomorphism

which sends $x$ mod $p\mathbb{Z}[\sqrt{\Delta}]$ to $x$ mod $p\mathbb{Z}_p[\zeta_{p^2-1}]$, we can view the sequence

as a permutation $\pi_p$ of the sequence

Clearly the above two sequences are analogues of the sequences (1.1) and (1.4). We mainly study this permutation in this paper. To state our result, let $\beta_0\in\{0, 1\}$ be the integer satisfying

We also use the symbol ${{{{\rm{sgn}}}}}(\pi_p)$ to denote the sign of $\pi_p$. Now we state the main result of this paper.

Theorem 1.1.

where $h(-p)$ is the class number of $\mathbb{Q}(\sqrt{-p})$.

The detailed proof of the above theorem will be given in next section.

2.   Proof of the main result

Recall that $a_k = k+\sqrt{\Delta}$ for $k = 0, 1, \cdots, p-1.$ We begin with several lemmas involving $a_k$. For convenience, we write $p = 2n+1$ and $p\mathbb{Z}[\sqrt{\Delta}] = \mathfrak{p}$ in this section.

Lemma 2.1. Let $A_p = \prod_{0\le k\le p-1}a_k$. Then

Proof. Since

we have

Observing that $(\sqrt{\Delta})^{p-1}\equiv-1\pmod {\mathfrak{p}}$, one may get the desired result.

Lemma 2.2. Let $B_p = \prod_{0\le k\le p-1}(1-a_k^{p-1})$. Then

Proof. For each $k = 0, \cdots, p-1$ we have

Hence we have the following congruences

Noting that

we obtain

Hence

Lemma 2.3. Let $C_p = \prod_{0 < s < t < p}\frac{1}{(t+\sqrt{\Delta})(s+\sqrt{\Delta})}$. Then

Proof. Clearly we have

Hence we obtain that $C_p^{n}\ {\rm{mod}}\ \mathfrak{p}$ is equal to

We first handle the product

Noting that

we therefore obtain

Hence

We now turn to the product

Let $n_p = \#\{(x^2, y^2): 1\le x, y\le n, x^2+y^2\equiv \Delta\pmod p\}$. Then one can easily verify that

Let $n_p' = \#\{(x^2, y^2): 1\le x, y\le n, x^2+\Delta y^2\equiv \Delta\pmod p\}$. Then

By the above we get

Therefore we have

Now our desired result follows from (2.3) and (2.6).

Lemma 2.4. Let $D_p = \prod_{0\le s < t\le p-1}(a_t^{p-1}-a_s^{p-1})$. Then $D_p^{n}\pmod {\mathfrak{p}}$ is equal to

Proof. From (2.1) one may easily verify that $D_p^{n}\pmod {\mathfrak{p}}$ is equal to

We further obtain

We first handle the product

By (2.2) we have

We turn to the product

It is clear that

is equal to

We now divide our proof into the following two cases.

Case 1. $p\equiv1\pmod4$.

Let $1\le w\le n$ be an arbitrary quadratic non-residue modulo $p$. Then

and

Hence when $p\equiv 1\pmod 4$ we have

Case 2. $p\equiv 3\pmod4$.

Let $1\le w\le n$ be an arbitrary quadratic non-residue modulo $p$ and let $1\le v\le n$ be an arbitrary quadratic residue modulo $p$. Then

and

Hence

For each $p\equiv3\pmod4$, let $h(-p)$ be the class number of $\mathbb{Q}(\sqrt{-p})$. When $p > 3$, by the class number formula (cf. [15,Chapter 5]) we have

By this one may easily verify that

The readers may also see Mordell's paper ^[16] for details.

By the above, we obtain

In view of the above, we obtain the desired result.

Let $\Phi_{p^2-1}(x)\in\mathbb{Z}[x]$ denote the $(p^2-1)$th cyclotomic polynomial. We also let

and let

Let $\zeta = e^{2\pi {\bf i}/(p^2-1)}$. The following result gives the explict value of $F(\zeta)$. As this result is the key element in the proof of our main result, we state this result as an individual theorem.

Theorem 2.5. Let $\zeta = e^{2\pi {\bf i}/(p^2-1)}$ be a primitive $(p^2-1)$th root of unity. Then

Hence $\Phi_{p^2-1}(x)\mid F(x)-T(x)$ in $\mathbb{Z}[x]$.

Proof. It is sufficient to prove that $F(\zeta) = T(\zeta)$. We first compute $F(\zeta)^2$. We have the following equalities:

Hence $F(\zeta) = \pm {\bf i}\cdot(\frac{p^2-1}{2})^{\frac{p^2-1}{2}}$. We now compute the argument of $F(\zeta)$. Note that for any $1\le s < t\le (p^2-1)/2$ we have

We therefore obtain

By this we have

Therefore

This completes the proof.

Before the proof of our main result, we first observe the following fact. Let $S = \{\alpha_1, \cdots, \alpha_n\}$ be an arbitrary subset of a finite field and let $\tau$ be a permutation on $S$. Then it follows from definition that

Hence

The next two propositions handle the numerator and the denominator respectively.

Proposition 2.6. Set $\mathfrak{P} = p\mathbb{Z}_p[\zeta_{p^2-1}]$. Then

Proof. Clearly $\Phi_{p^2-1}(x) \mod p\mathbb{Z}_p[\zeta_{p^2-1}][x]$ splits completely in $(\mathbb{Z}_p[\zeta_{p^2-1}]/\mathfrak{P})[x].$ As $g\equiv \zeta_{p^2-1}\pmod{\mathfrak{P}}$, by Theorem 2.5 we see that

is equal to

This completes the proof.

We now turn to the denominator.

Proposition 2.7.

is equal to

Proof. It is easy to verify that

is equal to

By [10,(1.5)] we have

By the above we obtain that

is equal to

This completes the proof.

Combining the above two propositions, we now state the proof of our main result.

Proof of Theorem 1.1. Set $\sqrt{\Delta}\equiv \zeta_{p^2-1}^{\alpha}\pmod{\mathfrak{P}}$ for some $\alpha\in\mathbb{Z}$. Since $(\sqrt{\Delta})^{p-1}\equiv-1\pmod{\mathfrak{P}},$ we obtain

Hence

Set $\alpha = \frac{p+1}{2}+(p+1)\beta$ for some $\beta\in\mathbb{Z}$. Then

By this we obtain

Hence $\beta\equiv\beta_0\pmod2$, where $\beta_0$ is defined as in (1.7). We divide the remaining proof into three cases.

Case 1. $p = 3$.

In this case by (2.10) and (2.11) it is easy to see that

Case 2. $p\equiv1\pmod4.$

By (2.10) and (2.11) we have

Replacing $\alpha$ by $\frac{p+1}{2}+(p+1)\beta$ and noting that $g^{\frac{p^2-1}{2}}\equiv-1\pmod{\mathfrak{P}}$, we obtain that when $p\equiv1\pmod4$

Case 3. $p\equiv3\pmod4$ and $p > 3$.

Similar to the Case 2, we have

Then via a computation we obtain

In view of the above, we complete the proof.

Acknowledgments

The first author was supported by the National Natural Science Foundation of China (Grant No. 12101321, Grant No. 11971222) and the Natural Science Foundation of the Higher Education Institutions of Jiangsu Province (Grant No. 21KJB110002). The second author was supported by the Natural Science Foundation of the Higher Education Institutions of Jiangsu Province (Grant No. 21KJB110001).

Conflict of interest

The authors declare there is no conflicts of interest.