原始根③ 原始根とDirichlet指標 ~最小原始根について~

過去二回の記事において原始根や指数計算について紹介しました。

この記事では原始根とDirichlet指標との関係性について紹介し、応用として最小原始根の問題について考察します。

参考文献
Dirichlet指標について
Dirichlet指標とべき乗剰余
Dirichlet指標と原始根
最小原始根について
- 上からの評価
- 下からの評価
終わりに

参考文献

(1) Multiplicative Number Theory (Graduate Texts in Mathematics 74) (Graduate Texts in Mathematics, 74)

リンク

(2) Kearnes, K. "Solution of Problem 6420." Amer. Math. Monthly 91, 521, 1984.
当時学生だったKearnesによるTheorem 12の証明です。リンク先の記事はJSTORにGoogleアカウントなどでログインすれば読めます。
リンク : https://www.jstor.org/stable/2322590#metadata_info_tab_contents

Dirichlet指標について

Dirichlet指標については過去の記事で詳しく紹介しましたが、今回は新たに定義を与えることとします。
ここでは原始根と指数を使って素数を法とするDirichlet指標を定義します。以下 $p$ は素数、 $g$ を $\text{mod} \; p$ の原始根とし、実数 $\alpha$ に対して
\begin{equation*}
e(\alpha):=e^{2\pi i \alpha}
\end{equation*}と定めます。

Definition 1

整数 $k$ に対して $p\nmid n$ のとき
\begin{equation*}
\chi_k(n)=e \left(\frac{\text{ind}_g(n)}{p-1}k\right)
\end{equation*}と定め、 $p|n$ のとき $\chi_k(n)=0$ と定める。このとき各 $k$ に対して $\chi_k(n)$ をmod $p$ のDirichlet指標と呼ぶ。

定義から $k\equiv k' \; (\text{mod} \; p-1)$ ならば $\chi_k = \chi_{k'}$ が成立することが分かります。従って $k=1,\dots , p-1$ に対して $\chi_k$ は異なる関数となります。このことからDirichlet指標は全部で $p-1$ 個あることが分かります。

次の性質は簡単に確かめることが出来ます。

Proposition 2

$\chi$ が $\text{mod}\; p$ のDirichlet指標なら次が成立する。

$\chi(nm)=\chi(n)\chi(m) \quad (\forall n,m \in \mathbb{Z})$
$\chi(n)\neq 0 \; \Leftrightarrow \; p\nmid n \quad (\forall n\in \mathbb{Z})$
$n\equiv m \; (\text{mod} \; p) \; \Rightarrow \; \chi(n) =\chi(m) \quad (\forall n,m \in \mathbb{Z})$

原始根の話題に入る前に一つDirichlet指標についての補題を示しておきます。

Lemma 3

$d|p-1$ に対して
\begin{equation*}
\sum_{\substack{\chi \; (\text{mod} \; p) \\ \chi^d=\chi_0}}1 =d
\end{equation*} が成立。ここで和は条件を満たすmod $p$ のDirichlet指標を走る。

証明整数 $k$ に対して
\begin{equation*}
\chi_k^d(n) =e \left(\frac{\text{ind}_g(n)}{p-1}kd\right) =1 =\chi_0(n)\quad (\forall n, \; p\nmid n)
\end{equation*}となるには $p-1|kd$ であれば良い。 $p-1=dl$ と書くとこれは $l|k$ と同値である。 $k=1,\dots , p-1$ のうち $l$ の倍数は
\begin{equation*}
l, \; 2l , \; \dots \; , \; \frac{p-1}{l}\; l
\end{equation*}で全てなので $\chi^d=\chi_0$ を満たすDirichlet指標は全部で $(p-1)/l=d$ 個である。(QED)

Dirichlet指標とべき乗剰余

正整数 $d$ と $p\nmid a$ なる整数 $a$ に対して
\begin{equation*}
x^d \equiv a \; (\text{mod}\; p)
\end{equation*}の解が存在するとき $a$ はmod $p$ の $d$ 乗剰余であると言います。

$d|p-1$ のとき、指数を用いることで $d$ 乗剰余を次のように記述できます。

Proposition 4

$p\nmid a, d|p-1$ とする。このとき

$a$ は $d$ 乗剰余 $\Leftrightarrow$ $d|\text{ind}_g(a)$ が成立する。

証明過去記事のProposition 3を適用すればよい。(QED)

$d$ 乗剰余とDirichlet指標には次のような関係があります。

Proposition 5

$p\nmid a$ , $d|p-1$ とする。このとき
\begin{equation*}
\frac{1}{d}\sum_{\substack{\chi \; (\text{mod}\; p) \\ \chi^d=\chi_0}}\chi(a) =
\begin{cases}
1 \quad (a\text{が}\;d\text{乗剰余}) \\
0 \quad (a\text{が}\;d\text{乗剰余でない})
\end{cases}
\end{equation*}が成立する。

証明 $a$ が $d$ 乗剰余であるとき、ある $x$ が存在して
\begin{equation*}
x^d \equiv a \; (\text{mod}\; p)
\end{equation*}となる。従ってDirichlet指標の乗法性とProposition 2から
\begin{equation*}
\sum_{\substack{\chi \; (\text{mod}\; p ) \\ \chi^d=\chi_0}}\chi(a) =\sum_{\substack{\chi \; (\text{mod}\; p) \\ \chi^d=\chi_0}}\chi(x)^d =d
\end{equation*}が成立する。
$a$ が $d$ 乗剰余でないとする。 $p-1=dl$ と書くと $\chi^d=\chi_0$ を満たすDirichlet指標は $p\nmid n$ に対して(Lemma 3の証明と同様に)
\begin{equation*}
\chi (n)=e \left( \frac{\text{ind}_g(n)}{d} m\right) \quad (m=1,\dots ,d)
\end{equation*}と書ける。したがって
\begin{equation*}
\sum_{\substack{\chi \; (\text{mod}\; ) \\ \chi^d=\chi_0}}\chi(a) = \sum_{m=1}^d e\left(\frac{\text{ind}_g(a)}{d}m\right)
\end{equation*}Prop3より $d\nmid \text{ind}_g(a)$ であることに注意すると最後の和は1の $d$ 乗根にわたる和になっているが、これは $0$ になる(この記事のLem 1)。(QED)

Proposition 5における等式とDirichlet指標に関する性質を合わせるとべき乗剰余についての計算ができますが、今回は原始根がメインターゲットなのでこのまま原始根の話題に引き継ぐことにします。

Dirichlet指標と原始根

整数 $a$ がmod $p$ の原始根とは
\begin{equation*}
\text{ord}_p(a)=p-1
\end{equation*}が成立することを言いました。これはMöbius関数 $\mu(n)$ とDirichlet指標を用いて次のように言い換えることが出来ます。

Proposition 6

$p\nmid a$ とする。このとき
\begin{equation*}
\sum_{d|p-1} \frac{\mu(d)}{d} \sum_{\substack{\chi \; (\text{mod}\; p) \\ \chi^d =\chi_0}}\chi(a)=
\begin{cases}
1 \; &(a\text{がmod} \; p \text{の原始根}) \\
0 \; &(a\text{がmod} \; p \text{の原始根でない})
\end{cases}
\end{equation*}が成立する。

証明原始根の定義とMöbius関数の基本公式から
\begin{equation*}
\sum_{d|\frac{p-1}{\text{ord}_p(a)}}\mu(d)=
\begin{cases}
1 \quad &(a\text{がmod} \; p \text{の原始根}) \\
0 \quad &(a\text{がmod} \; p \text{の原始根でない})
\end{cases}
\end{equation*}が成立。また、過去記事のProposition 4から $d|p-1$ のとき
\begin{equation*}
(\text{ind}_g(a),p-1)=\frac{p-1}{\text{ord}_p(a)}
\end{equation*}なのでProposition 4から $d|p-1$ に対して
\begin{equation*}
d|\frac{p-1}{\text{ord}_p(a)} \; \Leftrightarrow \; d|\text{ind}_g(a) \;
\Leftrightarrow \; a:d \text{乗剰余}
\end{equation*}がわかる。これらの結果とProposition 5から
\begin{equation*}
\sum_{d|\frac{p-1}{\text{ord}_p(a)}}\mu(d)=\sum_{d|p-1}\frac{\mu(d)}{d}\sum_{\substack{\chi \; (\text{mod}\; p) \\ \chi^d =\chi_0}}\chi(a)
\end{equation*}が成立する。(QED)

最小原始根について

応用として最小原始根について紹介します。

Problem 7

$1, \dots , p-1$ のなかで $\text{mod}\; p$ の原始根であって最小の整数を $g(p)$ と書く。このとき $g(p)$ の大きさを評価せよ。

上からの評価

$g(p)$ の上からの評価を得るためにProposition 6を応用します。そのためにDirichlet指標に関する有名な不等式を紹介します(証明略)。

Lemma 8 (Pólya-Vinogradovの不等式)

$\chi \neq \chi_0$ をmod $p$ のDirichlet指標とし、 $M>0$ とする。このとき
\begin{equation*}
\sum_{1\le a\le M} \chi(n) \ll \sqrt{p}(\log p)
\end{equation*}が成立する。

証明参考文献(1)の23章を参照。(QED)

Theorem 9

任意の $\varepsilon >0$ に対して
\begin{equation*}
g(p)\ll p^{1/2+\varepsilon}
\end{equation*}が成立。

証明 $0 < H \le p$ とする。Proposition 6の和を $\chi=\chi_0$ の時とそれ以外で分割すると
\begin{align*}
&\{ 1\le a \le H: a \text{はmod}\; p \text{の原始根} \}　\notag \\
&=\sum_{1\le a \le H}\sum_{d|p-1} \frac{\mu(d)}{d} \sum_{\substack{\chi \; (\text{mod}\; p) \\ \chi^d =\chi_0}}\chi(a) \notag \\
&=\sum_{d|p-1}\frac{\mu(d)}{d}\sum_{1\le a\le H}\chi_0(a) \notag \\
&\quad +\sum_{d|p-1} \frac{\mu(d)}{d} \sum_{\substack{\chi \neq \chi_0 \\
\chi^d =\chi_0}}\sum_{1\le a\le H} \chi(a) \label{eq3}
\end{align*}と書ける。ここで最後の第二項の和はLemma 8から
\begin{align*}
\ll \sqrt{p}(\log p) \sum_{d|p-1} 1 \ll p^{1/2+\varepsilon/2}
\end{align*}ただしLemma3及び
\begin{equation*}
\log p \ll p^{\varepsilon/4}, \quad \sum_{d|p-1} 1 \ll p^{\varepsilon/4}
\end{equation*}を用いた*1。従って
\begin{align*}
&\{ 1\le a \le H: a \text{はmod}\; p \text{の原始根} \} \\
&= \sum_{d|p-1}\frac{\mu(d)}{d}\sum_{1\le a\le H}\chi_0(a) +O\left(p^{1/2+\varepsilon/2} \right) \\
&=\frac{\phi(p-1)}{p-1}H+O\left(p^{1/2+\varepsilon/2} \right)
\end{align*} が得られる。最後の式は適当な定数 $C>0$ に対して
\begin{equation*}
H=Cp^{1/2+\varepsilon}
\end{equation*}と取れば正になる。したがって
\begin{equation*}
g(p) \le H \ll p^{1/2+\varepsilon}
\end{equation*}が成立する。

下からの評価

上からの評価はDirichlet指標を用いましたが、下からの評価は平方剰余の相互法則を用いて初等的に証明することが出来ます。

Lemma 11

$M>2$ とする。このとき $M$ 以下のすべての素数の列 $2=q_1 < q_2 < \dots < q_n\le M$ に対して
\begin{equation*}
\left( \frac{q_i}{p}\right)=1
\end{equation*}を満たす素数 $p$ が無限に存在する。ここで $(q/p)$ はLegendre記号とする。

証明正整数 $k$ に対して $p=1+4q_1 q_2 \cdots q_n k$ の形で表される素数を考える。平方剰余の相互法則の第二補充法則から
\begin{equation*}
\left( \frac{q_1}{p} \right) =\left(\frac{2}{p} \right) =(-1)^{(p^2-1)/8}=1
\end{equation*}が成立。また平方剰余の相互法則から
\begin{equation*}
\left(\frac{q_i}{p} \right) \left( \frac{p}{q_i} \right) =(-1)^{(p-1)(q_i-1)/4}=1 \quad (2\le i \le n)
\end{equation*}が成立する。ここで $p\equiv 1 \; (\text{mod} \; q_i)$ に注意して
\begin{equation*}
\left( \frac{p}{q_i} \right) =\left(\frac{1}{q_i} \right) =1 \quad (2 \le i \le n)
\end{equation*}が得られるので
\begin{equation*}
\left( \frac{q_i}{p}\right)=1 \quad (2\le i \le n)
\end{equation*}が成立する。従ってこの $p$ は要求される性質を満たしているが、Dirichletの素数定理からこのような形の素数、すなわち
\begin{equation*}
p \equiv 1 \; (\text{mod} \; 4q_1 q_2 \cdots q_n)
\end{equation*}を満たす素数 $p$ は無限に存在する。(QED)

Theorem 12

任意の $M>0$ に対して
\begin{equation*}
g(p)>M
\end{equation*}を満たす素数 $p$ が無限に存在する。

証明 Lemma 11の条件を満たす素数 $p>M$ を取る。整数 $r$ が $1\le r \le M$ を満たすなら $r$ の素因数分解は
\begin{equation*}
r=q_1^{t_1} q_2^{t_2} \cdots q_n^{t_n} \quad (0\le t_i )
\end{equation*}で与えられる。従ってLegendre記号の完全乗法性から
\begin{equation*}
\left(\frac{r}{p}\right) =\left(\frac{q_1}{p}\right)^{t_1} \left( \frac{q_2}{p}\right)^{t_2} \cdots \left(\frac{q_n}{p}\right)^{t_n}=1
\end{equation*}が成立する。すなわち $1\le r\le M$ を満たす整数 $r$ は全てmod $p$ の平方剰余であり、原始根にはならない。つまり $g(p)>M$ が得られる。Lemma 11からこのような素数 $p$ は無限に存在するので主張が証明される。(QED)