「平方剰余が連続する」箇所の数は？

こんにちは.

今回は, 平方剰余で遊んでみようと思います.

平方剰余とは

$a$が$\mathrm{mod}p$で平方剰余であるとは, $x^2\equiv a\mathrm{mod}p$なる$x$が存在することを言います. そうでないとき, 平方非剰余であると言います.

以下, $a=0$を含めると色々と面倒なので, $0$以外の平方剰余を考えます.

$x^2\equiv y^2⟺x\equiv \pm y$より, $p$が奇素数ならば$1^2,2^2,\dots ,(p-1{)}^2$の中に$2$つずつ等しいものがあるので, 平方剰余は${\displaystyle \frac{p-1}{2}}$個、平方非剰余も${\displaystyle \frac{p-1}{2}}$個あることがわかります.

具体的には次の表のようになります. （赤字が平方剰余）

他の性質として,
・平方剰余の積は平方剰余
・$p-1$が平方剰余$⟺$$p$は$4n+1$型の素数
・従って上の表は$p$が$4n+1$型のとき左右対称
・$2$が平方剰余$⟺$$p$は$8n\pm 1$型の素数
・$p$が$4n+3$型のとき, 平方剰余は前半の方に多い
などが知られています.

Gauss和

平方剰余記号$\left({\displaystyle \frac{a}{p}}\right)$を, $a$が平方剰余のとき$1$, そうでないとき$-1$と定めます. 例えば$(\frac{-1}{p})=(-1{)}^{\frac{p-1}{2}}$, $(\frac{2}{p})=(-1{)}^{\frac{p^2-1}{8}}$などが成り立ちます.

Gauss和$G_p$を

${\displaystyle G_p=\sum _{a=1}^{p-1}\left({\displaystyle \frac{a}{p}}\right){\zeta }_p^a}$

と定めます. ただし${\zeta }_p=\exp \frac{2\pi i}{p}$です.

この時, $G_p^2=(-1{)}^{\frac{p-1}{2}}p$が成り立つことが知られています. （例えば、子葉さんの こちらの記事 を参照）

Gauss和を分ける

Gauss和を, 係数が$1$の項と$-1$の項で分けることを考えます.　以下, 和の中身は${\mathbb{F}}_p$内で考えることにします.

すると, $\alpha +\beta =\sum _{a\ne 0}{\zeta }_p^a=-1$, $\alpha -\beta =G_p$が成り立ちます.

従って$\alpha \beta ={\displaystyle \frac{1-G_p^2}{4}}={\displaystyle \frac{1-(-1{)}^{\frac{p-1}{2}}p}{4}}$なので, $\alpha ,\beta$は$2$次方程式

$x^2+x+{\displaystyle \frac{1-(-1{)}^{\frac{p-1}{2}}p}{4}}=0$

の$2$解になっています.

平方剰余の和

とおくと,

${\displaystyle {\alpha }^2=\sum _{k=0}^{p-1}{N}_1(k){\zeta }_p^k}$
${\displaystyle \alpha \beta =\sum _{k=0}^{p-1}{N}_2(k){\zeta }_p^k}$
${\displaystyle {\beta }^2=\sum _{k=0}^{p-1}{N}_3(k){\zeta }_p^k}$

となります. また$k=0$は簡単に求めることができて,

$\begin{array}{rl}{N}_1(0)& =\mathrm{\#}\{(a,-a)|a,-a\text{は平方剰余}\}\\ & =\{\begin{array}{ll}\frac{p-1}{2}& (\frac{-1}{p})=1\text{のとき}\\ 0& (\frac{-1}{p})=-1\text{のとき}\end{array}\\ & =\frac{1+(-1{)}^{\frac{p-1}{2}}}{2}\frac{p-1}{2}\end{array}$
同様に
${\displaystyle N_2(0)=\frac{1-(-1{)}^{\frac{p-1}{2}}}{2}\frac{p-1}{2}}$
${\displaystyle N_3(0)=\frac{1+(-1{)}^{\frac{p-1}{2}}}{2}\frac{p-1}{2}}$

係数を比べる

$\{{\zeta }_p,{\zeta }_p^2,\dots ,{\zeta }_p^{p-1}\}$は$\mathbb{Q}$上独立なので,

${\alpha }^2=-\alpha -{\displaystyle \frac{1-(-1{)}^{\frac{p-1}{2}}p}{4}}$即ち
${\displaystyle \sum _{k=0}^{p-1}{N}_1(k){\zeta }_p^k=-\sum _{a:\text{平方剰余}}{\zeta }_p^a-{\displaystyle \frac{1-(-1{)}^{\frac{p-1}{2}}p}{4}}}$
の両辺の${\zeta }_p^k$の係数を比べることで$N_1(k)$を求めることができます.
$1$の${\zeta }_p^k$の係数は$-1$であることに注意して,
${\displaystyle N_1(k)-N_1(0)=-\frac{1+(\frac{k}{p})}{2}+{\displaystyle \frac{1-(-1{)}^{\frac{p-1}{2}}p}{4}}}$

同様に, $\alpha \beta ={\displaystyle \frac{1-(-1{)}^{\frac{p-1}{2}}p}{4}}$より
${\displaystyle N_2(k)-N_2(0)=-{\displaystyle \frac{1-(-1{)}^{\frac{p-1}{2}}p}{4}}}$

${\beta }^2=-\beta -{\displaystyle \frac{1-(-1{)}^{\frac{p-1}{2}}p}{4}}$より
${\displaystyle N_3(k)-N_3(0)=-\frac{1-(\frac{k}{p})}{2}+{\displaystyle \frac{1-(-1{)}^{\frac{p-1}{2}}p}{4}}}$

以上より,

「平方剰余が連続する」

もう一度定義を思い出します.

平方剰余, 非剰余が連続する箇所の数を
$n_p=\mathrm{\#}\{(a,a^{\prime })|a-a^{\prime }\equiv 1,a,a^{\prime }\text{は平方剰余}\}$
$n_p^{\prime }=\mathrm{\#}\{(b,b^{\prime })|b-b^{\prime }\equiv 1,b,b^{\prime }\text{は平方非剰余}\}$
とおくと, これらは$N_1(k)$たちを用いて表せます.

$(\frac{-1}{p})=1$つまり$p$が$4n+1$型のとき, $-a$が平方剰余$⟺$$a$が平方剰余
$(\frac{-1}{p})=-1$つまり$p$が$4n+3$型のとき, $-a$が平方剰余$⟺$$a$が平方非剰余
なので,

$n_p=\{\begin{array}{ll}{N}_1(1)& p=4n+1\\ N_2(1)& p=4n+3\end{array}$

$n_p^{\prime }=\{\begin{array}{ll}{N}_3(1)& p=4n+1\\ N_2(1)& p=4n+3\end{array}$

従って

平方剰余が連続する箇所の数は, $\frac{p}{4}-1$に最も近い整数であることがわかりました.

ちなみに, $\frac{n-1}{2}$個の〇と$\frac{n-1}{2}$個の×をランダムに並べたとき, 〇が連続する箇所の数の期待値は$\frac{n-3}{4}$になるので, この意味では平方剰余の分布はかなりランダムになっているとも言えそうです.