55

p 進数体上の連分数アルゴリズムとその周期性

公立はこだて未来大学

システム情報科学部

斉藤朝輝(Asaki Saito) *School of Systems Information Science, Future University Hakodate

津田塾大学・数学・計算機科学研究所

田村 純一(Jun‐ichi Tamura)Institute for Mathematics and Computer Science, Tsuda College

東邦大学 理学部

安冨 真一(Shin‐ichi Yasutomi)

Faculty of Science, Toho University

1

はじめにp を素数,\mathb {Q}_{p} を p 進数体, \mathb {Z}_{p} を p 進整数環とする.

実数の連分数展開の周期性に関しては,次の定理がよく知られている [3].
定理1.1 (Lagrange の定理). 実数 \alpha が2次無理数であることの必要十分条件は,\alphaが周期的連分数展開をもつことである.
p進数の世界でも,様々な連分数アルゴリズムが考えられてきたが [6, 4, 2, 1] , 任意の \mathb {Q} 上2次の \mathb {Q}_{p} の元に対して,周期的展開をあたえる p 進連分数アルゴリズムは,これまで存在しなかった.

我々は, cr\in \mathbb{Q}_{p} に対して,次の形の連分数を生成するアルゴリズムをいくつか構成した [5].

d_{0}+\frac{1p}{d_{1}+\frac{t_{2}p^{k_{2}A_{1}\wedge\wedge}{t_3}p^{k_{3} (k_{71}\in\mathb {Z}_{>0},t_{n}\in\mathb {Z}\backslashp\mathb {Z},d_{n}\in\ {1,\ldots,p-l\}(n\geq1) .
d_{2}+-

ただし,d_{0} は d_{0}=[\alpha]_{p} をみたす有理数である(1)(\alpha\in \mathbb{Q}_{p} の p 進整数部分 [\alpha]_{p} の定義については (2) を参照のこと) . さらに,これらのアルゴリズムが, \mathb {Q} 上2次の \mathb {Q}_{p} の元に対して周期的展開をあたえ,有理数に対して有限の展開をあたえることを示した.また,それぞれのアルゴリズムに関して,純周期的展開をもつ元を完全に特徴づけた.本稿では,これらの [5] の結果を紹介する.

2p 進連分数展開

以 \triangleright では,特に断らない限り,\alphaは \mathb {Q}_{p} の元とする.また,. の p 進展開を0

\alpha=\sum_{i,=-\infty}^{\infty}e_{i}p^{i} (e_{i}=e_{i}( 1)\in\{0,1, \ldots,p -1\})
Email: saito@fun.ac.jp

56とする (ただし, e_{i}(i\leq 0) については,高々有限個の i でしか e_{i}\neq 0 にならない).
および p 進小数部分 \langle\alpha\rangle_{p} をと定義する.この章では,\alphaを

aの p 進整数部分 [0‐ ]_{p}[ a]_{p}:=\sum_{i=-\infty}^{0}e_{i}p^{i_{!} . \langle\alpha\rangle_{p}:=\sum_{i =1}^{\infty}e_{i}p^{i}(2)d_{0}+\frac{t_1}p^{た:_{1} {d_1}+\frac{t_2}p^{A_{2}\wedge}{t_3}p^{k_3} } (k_{i}\n\mathb {Z}_{>0},t_{i}.,d_{i}\n\mathb {Z}_{p}\backsla hp\mathb {Z}_{p}(i\geq1)
d_{\underline{Q}}+-という形の連分数に展開することを考える.ただし, d_{0}\in \mathbb{Q} は d_{0}=[t\ovalbox{\t \smal REJECT}^{\ovalbox{\t \smal REJECT} ]_{p} をみたすとする.このような連分数のクラスは,(1) の形の連分数を含むことを注意しておく.
t を p\mathbb{Z}_{p}\backslash \{0\} から \mathbb{Z}_{p}\backslash p\mathbb{Z}_{p} への写像とする.また, v_{p}(cv) を,0の p 進付値とする.ここで,T:p\mathbb{Z}_{p}\backslash \{0\}arrow p\mathbb{Z}_{P\prime}.
(3)

T(x):= \frac{t(x)p^{v_{I},(x)}}{x}-d(x)という形の写像の族を考える.ただし,d は,p\mathbb{Z}_{p}\backslash \{0\} から \mathb {Z}_{p}\backslash p\mathb {Z}_{p} への写像とする.ここで, [d(x)]_{p}=[\frac{t(x)p^{1\ovalbox{\t \smal REJECT}_{l},(x)} {x}] ア \in\{1, p-1\} となることは容易にわかる.よって, の像 {\rm Im}(d) が, {\rm Im}(d)\subset\{1, p-1\}d)をみたすならば,d }よ一意的に定まる.

T^{n-1}(\langle\alpha\}_{p})\neq 0(n\in \mathbb{Z}_{>0}) ならば, T^{n.-1}(\langle\alpha\}_{p}) は T^{n}(\langle 0^{\ovalbox{\t \smal REJECT} \rangle_{p}) を使ってT^{n-\imath}(\langle\alpha\rngle_{p})=\frac{f.(T^{n-1}(\langler_{-} \ve \rangle_{P})p^{1_7'}(T^{21- }(\langle0\rangle)}{d(T^{?\prime.-1} (\langle0^{\ovalbox{\t smal REJ CT}\rangle_{p})+T^{7l} \cdot(\langle\alpha\rngle_{p'})と表せる.

i\in\{1 n\} に対して,

t_{i}=t(T^{i-1}(\langle\alpha\rangle_{p})k_{i}=v_{p}(T^{i-1}(\langle\alpha\rangle_{p})d_{i}=d(T^{i-1}(\langle(1.\rangle_{p}),,とおくと,\alpha=[\alpha]_{p}+\frac{t_1}p^{k_{1} {d_{1}+\frac{t_2}p^{k_{\underline{9} } {d_{2}+\underline{t_3}p^{k_{3} }十となる.
\alpha(i)\frac{t_n-1}p^{k,.-1}{d_lt.-1}+\frac{t_n}p^{k_n} {d_7}.+T^{r\iota} (\lange\alph\rangle_{I},)の連分数展開に関して,以 \triangleright の3つの場合が起こりうる.

\langle c\iota^{\ovalbox{\t \smal REJECT} \rangle_{p}=0.
\alphaの展開は \alpha=[\alpha]_{p} となる ( \langle\alpha\rangle_{p}=0 は展開しない) .

57(ii) T^{N}(\langle \mathfrak{a}\rangle_{)})=0 かつ 0\leq n<N で T^{71}(\{\alpha\rangle_{p})\neq 0 となる N\in \mathbb{Z}_{>0} が存在する.
このとき Q^{0} は以 \triangleright の有限連分数に展開される.

Q=[\alpha]_{p}+\frac{}d_{1}+\frac{t_1}p^{A_1}t_{2}p^{た\underline{\cdot)} {d_2}+\underline{t_3}p^{k_3}.

(4)+ \frac{t_{N}p^{A_{N} {d_{N}(iii) 全ての n\in \mathbb{Z}\geq 0 で, T^{?1}(\langle C1^{t}\rangle_{p})\neq 0.
このとき \mathfrak{a} は以 \vdash の無限連分数に展開される.

[\mathfrak{}]_{p}+\frac{1p}d_{1}+\frac{t._2}p^{A_2}k_{1}\sim}{t_3}p^{k_ {3}.

(5)d_{2}+-

ここで,次の2点について注意しておく.

(i) 写像 T としては様々なものを考えることができる.実際,5章では,異なる3つの連分数アルゴリズムをあたえる.すなわち, 0'\in \mathbb{Q}_{p} に対して,(4) および(5) の連分数展開は一意的に定まらない.

(ii) t(x)\equiv 1 かつ Im(d)\subset\{1, . . . :p-1\} とすると,生成される連分数は Schneider の連分数 [6] となる.

3連分数の収束性
2章で述べた連分数の収束性を議論する上では, p\mathbb{Z}_{p}\backslash \{0\} の元の展開だけを考えても一般性を失わない.

(5) のち, k_{i}, d_{i} を使って,数列 \{p_{71}\}_{71\cdot\geq-1} および \{q_{\ovalbox{\t \smal REJECT} .\}_{7l.\geq-1} を,漸化式\{ begin{ar ay}{l p-\~{I}=1,p_{0}=0,p_{\mathfrak{n}=d_{\upar ow\tau}.p_{\tau-1}+t_{71}.pたnp_ {n-2}(n\geq1), q_{-1}=0,qo=1、q_{n}=d,q_{7,.-1}+t_{n}p^{k_{\Gam a1}q)1-2(n\geq1). \end{ar ay}
によって定める.有限展開 (4) の場合には,-1\leq n\leq N の範囲の n に対して,以 \triangleright の関係が成り立つことは容易に示せる.

\frac{1p}{d_1}+\frac{t_2}p^{た_}2\kap :_{1}\backslah}{d_2}+\underline {t_3}p^{A:_3} =\frac{p_?1}{q_n} (n\geq1)+\frac{t_?t}p^{A\wedge}{d_{71}c \}^{\ovalbox{\t \smal REJECT} =\frac{p_{?l}+T^{71}(0)p_{7l.-1} {q_{\tilde{\~ {i} 1}+T'(c\nu)q_{r1- } (n\geq 1),,pと q_{\iota}. を定める.

58

p_{??-1}q_{\eta}-p_{\eta}q_{n-1}=H(-t_{i}p^{k_{i} )i=1?t (n\geq 1)|q_{7?}|_{p}=1 (n\geq 0)
ただし,,.

|0^{:}|_{p} は, \alpha\in \mathbb{Q}_{p} の p 進絶対値を表す (つまり, |\alpha|_{p}:=1/p^{\iota\ovalbox{\t \small REJECT}, (0\cdot)} ).

2章で述べた連分数の収束性に関して,以 \triangleright の定理を示すことができる.
定理3.1.

(i)n\geq 1 を整数とする.ただし,T^{N}(cr)=0 となる整数 N\geq 1 が存在する場合には,1\leq n\leq N とする.このときとなる.特に, T^{??}((\gamma)\neq 0 ならば,|\mathfrak{a}-\frac{p_{?1}{q_{\gam at}|_{p}=\frac{|T^{? }(\alpha)|_{p}{p^{ \Sigma_{;=1}^{n}h_{i}|0- \frac{p_{?1} {q_{7?} |_{p}=\frac{1}{p^{\Sigma_{;_{=} ^{n+1}A_{j}となる.

(刎 全ての n\geq 1 で, T^{\uparrow\prime}\cdot(C1)\neq 0 とする.このとき\lim_{?1ar ow\infty}\frac{p_{7?} {q_{71} =rvとなる.ただし,極限は, \mathb {Q}_{p} の通常の非アルキメデス的距離に関する極限を意味する.

4

基本写像男と乃
A_{p} を, p\mathbb{Z}_{p} の \mathb {Q} 上代数的な元で次数が高々2のもの全てからなる集合とする.以 \vdash では,“ \mathb {Q} 上代数的”を“代数的“ , : \mathbb{Q} 上2次” を ’2次” と略すことにする.ここでは,代数的な元 \alpha の最小多項式として,最高次係数が正の整数係数多項式で,(\nuを根としてもつもののうち次数が最小で,かつ,係数の最大公約数が1であるものを考える. x\in A_{p} が2次のとき, x の最小多項式を aX^{2}+bX+c と表す.また,ときは,最小多項式を bX+c と表すことにする. x\in A_{p}\backslash \{0\} に対してxが有理数のu(x):=c|c|_{p}\in \mathbb{Z}\backslash p\mathbb{Z}を対応させることにより,写像 u:A_{p}\backslash \{0\}arrow \mathbb{Z}\backslash p\mathbb{Z} を定義する. A_{p}\backslash \{0\} から A_{p} への写像 T_{1} と T_{2} を,次のように定義する.

T_{1}(x):= \frac{u(x)p^{v_{p}(x)} {x}-d_{1}(x)T_{\underline{9} (x):= \frac{-u(x)p^{U}\rho(z:)}{x}-d_{2}(x),.

ただし, d_{1} と d_{2} は A_{p}\backslash \{0\} から {1 , . . . ,p—l} への写像で,一意的に定まる.定義域を考慮しなければ,
T_{1} と T_{2} は写像 (3) の族に所属することを注意しておく.
次章で導入する連分数アルゴリズムは, \mathb {Q}_{p} の高々2次の代数的な元の展開を,以 \triangleright の補題で存在が保証されている p\mathbb{Z}_{p} の元の展開に帰着させる.

59
補題4.1 (Hensel の補題). n\in \mathbb{Z}_{>0}, a_{1}\in \mathbb{Z}\backslash p\mathbb{Z}, a_{0}\in p\mathbb{Z} として f(X) :=X^{\tau l}+a_{7i-1}X^{?1-1}+\cdots+a_{1}X+a_{0}\in\mathbb{Z}[X] とする.このとき, f(\alpha)=0 となる \alpha\in p\mathbb{Z}_{p} がただ一つ存在する.
以 \vdash では, b\in \mathbb{Z}\backslash p\mathbb{Z}, c\in p\mathbb{Z} である既約多項式 X^{2}+bX+c\in \mathbb{Z}[X] の根となる p\mathbb{Z}_{p} の元を,2次Hensel根と呼ぶことにする.同様に, c\in p\mathbb{Z} である多項式 X+c\in \mathbb{Z}[X] の根となる p\mathbb{Z}_{p} の元 (つまり, -c ) を,1次Hensel 根と呼ぶことにする.
T_{1} と T_{2} は,2次Hensel 根を2次Hensel 根にうつすことが証明できる.

5連分数アルゴリズム
前章で導入した T_{1} と乃を用いて,2次の \mathb {Q}_{p} の元に対しては周期的展開をあたえ,有理数に対しては有限の展開をあたえる連分数アルゴリズムを構成できる.このようなアルゴリズムとしては様々なものを考えることができるが,本稿では3つのアルゴリズムを扱う.

前章と同様に , x\in A_{p} の最小多項式を,xが2次の場合には aX^{2}+bX+c\in \mathbb{Z}[X] で表し,xが有理数の場合には bX+c\in \mathbb{Z}[X] で表す.我々のアルゴリズムでは,あたえられた x\in A_{p}\backslash \{0\} に対して, T_{1} もしくは乃のどちらかが適用される.どちらが適用されるかは,xの次数にかかわらず,xの最小多項式の2つの係数 b と c とで決まる.以 \triangleright では,各アルゴリズムで使用される写像 T : A_{p}\backslash \{0\}arrow A_{p} を指定する
ことにより,3つのアルゴリズムを指定する.

アルゴリズムA:

T(x):=T_{2}(x).

アルゴリズム B :T(x):=\{ begin{ar ay}{l T_{\underline{9}(x)ifb\geq0, T_{1}(x)ifb<0. \end{ar ay}
アルゴリズム C :T(x):=\{\begin{ar ay}{l} T_{2}(x) if b\geq 0 and c>0, T_{1}(x) otherwise. \end{ar ay}
6

2次の \mathb {Q}_{p} の元の展開
2次Hensel 根のアルゴリズム A, B, C による連分数展開の周期性に関して,以 \triangleright の定理を示すことができる.

定理6.1.

(i) アルゴリズム

A(つまり, T_{2} ) から得られる任意の2次Hensel 根の展開は,周期1もしくは2で純周期的である.

(ii) アルゴリズム B から得られる任意の2次Hensel 根の展開は,周期1で終局周期的 (eventually periodic)である.

60(iii) アルゴリズム
次に,\alphaC から得られる任意の2次 Hen6el 根の展開は,終局周期的である.

を任意の2次の \mathb {Q}_{p} の元とし,\alpha^{\sigma} を \alpha 以外の \alpha の共役元とする.以ドの6つの場合に分けて考

える.
Case

1A:|a\cdot|_{p}<|\alpha^{\sigma}|_{p}f_{J^{i}D}|a|_{p}\leq p^{-1_{:}}
B:|(\}'|_{1)}<|(Y'|_{P} かつ |cr|_{p}\geq 1_{:}

A:|cr|_{p}>|(\nu^{\sigma}|_{p}i^{1}D|c\}^{\ovalbox{\tt\small REJECT}}|_{p}\leq p^{-1},

Case 2

B:|0\cdot\ovalbox{\t \small REJECT}|_{p}>|\alpha^{\sigma}|_{p} かつ |(j1|_{p}\geq 1,
Case 3

A:|a|_{p}=|\alpha^{\sigma}|_{p}\hslash^{1}0|a} |_{p}\leq p^{-1,}.
B:|(\supset|_{p}=|\alpha^{\sigma}|_{p} かつ |\alpha|_{p}\geq 1.

それぞれの場合について,以 \triangleright のことが示せる.
Case

1A:|\alpha|_{p}<|a^{\sigma}|_{p}\ovalbox{\t \smal REJECT}_{\ovalbox{\t \smal REJECT}}D|\alpha|_{T^{\ovalbox{\t \smal REJECT}} \leq p^{-{\imath}

T_{1} もしくは T_{2} を1回適用することにより,Casec\nuは2次Hensel 根にうつる.

1B:|(v|_{p}<|(1‐ \sigma|_{p}\ovalbox{\t \smal REJECT}^{\ovalbox{\t \smal REJECT}}D|(y|_{T)} \geq 1|\langle\alpha\rangle_{p}|_{p}\leq p^{-{\imath} かつ |\langle\alpha\rangle_{p}|_{p}<|\langle\alpha\rangle_{p}^{\sigma}|_{p} より,Case 1B はCase IA に帰着する.
Case2A:|\alpha|_{p}>|\alpha^{\sigma}|_{p}\ovalbox{\t \small REJECT} ^{\ovalbox{\t \small REJECT}}0|\alpha|_{p}\leq p-1

T_{1} もしくは乃を1回適用することにより,Case 2A はCase IA に帰着する.
Case 2B:|\alpha|_{p}>|\alpha^{\sigma}|_{p}\ovalbox{\t \small REJECT} ^{\ovalbox{\t \small REJECT}}0|\alpha|_{p}\geq 1|\langle\alpha\rangle_{p}|_{p}\leq p^{-1} かつ |\langle\alpha\rangle_{p}|_{p}<|\langle \mathfrak{a}\cdot\rangle_{p}^{\sigma}|_ {p} より,Case 2B はCase IA に帰着する.
Case

3A:|\alpha|_{p}=|0^{\sigma}|_{p}h^{\ovalbox{\tt\small REJECT}}o|a\cdot|_{p}\leq p^{-1}

T_{1} と乃を十分な回数反復適用することにより,Case 3A は,Case 1A もしくはCase 2A のどちらかに帰着する.
Case

3B:|\alpha|_{p}=|a^{\sigma}|_{p}\ovalbox{\t \small REJECT}^{\ovalbox{\t \small REJECT}}0|\alpha|_{p}\geq ı|\langle\alpha\rangle_{p}|_{p}\neq|\langle\alpha\rangle_{p}^{\sigma}|_{p} ならば,Case 3B はCase IA もしくはCase 2A に帰着する.そうでない場合は,Case 3BはCase 3A に帰着する.

結局 , 全ての場合で, T_{1} と乃を何回か適用することにより,は T_{1} と T_{2} を適用する順番によらない) .

\langle0^{\ovalbox{\t smal REJ CT}\rangle_{p} は2次Hensel 根にうつる (このことよって,定理6.1と合わせて次の結果が得られる.

定理6.2. アルゴリズム A, B, C は,任意の \mathb {Q} 上2次の \mathb {Q}_{p} の元に対して,周期的展開をあたえる.

7

有理数の展開Q^{\ovalbox{\t \small REJECT}}=0 は1次Hensel 根であるが,2章で述べたように,\alpha=0 はこれ以上展開しない.また,0 以外の任意の1次Hensel 根に対して,どのアルゴリズムも有限の展開をあたえることが示せる.すなわち

61
61
定理7.1. アルゴリズム A, B,次に,Case A :Case(rC は,任意の1次Hensel 根に対して,有限展開をあたえる.

を任意の有理数とする.以 \triangleright^{-} の2つの場合に分けて考える.

|a|_{p}\leq p^{-1},

B:|\mathfrak{a}|_{p}\geq 1.

それぞれの場合について,以 \triangleright のことが示せる.
Case\alphaA:|(k|_{p}\leq p^{-1}

が1次Hensel 根である場合には,我々のアルゴリズムは \alpha に対し有限展開をあたえる (定理7.1) .

が1次Hensel 根でない場合には, T_{1} もしくは T_{2} を1回適用することにより,Casec\ovalbox{\t smal REJ CT}\alpha. は1次Hensel 根にうつる.

B:|(} |_{p}\geq 1\langle\alpha\rangle_{p}\in \mathb {Q} かつ |\langle \mathfrak{a}\rangle_{p}|_{p}\leq p^{-1} より,Case B はCase A に帰着する.
結局 , 有理数の展開は1次Hensel 根の展開に帰着する.よって,定理7. ı と合わせて次の結果が得られる.
定理7.2. アルゴリズム A, B,

8

C は,任意の有理数に対して,有限展開をあたえる.

純周期点の特徴づけ
最後に,それぞれのアルゴリズムに関して,純周期的展開をもつ元を特徴づけてみよう.ただし,純周期的展開においては,(1) の d_{0} は 0 と考える.よって,純周期的展開をもつ元は p\mathbb{Z}_{p} に含まれることになる.
定理7.2より,どのアルゴリズムでも,有理数の展開は周期的にならない.また,6章で述べたように,2次の p\mathbb{Z}_{p} の元は T_{1} と T_{2} を何回か適用することにより2次Hensel 根にうつる.よって,どのアルゴリズムでも,純周期的展開をもつ元の集合 (既約集合) は,純周期的展開をもつ2次Hensel 根の集合と一致する.
ここで,いくつか2次Hensel 根の集合を定義する.2次Hensel 根 a^{\ } を指定する際には,

C1

多項式 X^{2}+bX+c の係数の組 (b, c) とを同一視すると便利なので,そうすることにする.と,\alphaの最小S を,全ての2次Hensel 根の集合,すなわちS={ (b, c)\in \mathbb{Z}^{2}|b\in \mathbb{Z}\backslash p\mathbb{Z}, c\in p\mathbb{Z}, X^{2}+bX+c は既約}とする.また,集合 S_{1}, S_{3}, S_{4}, R, R_{1}, P_{1} を以 \triangleright のように定義する.

:=\{(b, c)\in S|b>0, c>0\},SĨ

S_{3}:=\{(b, c)\in S|b<0, c<0\},S_{4}:=\{(b, c)\in S|b>0, c<0\},R.

:=\{(b, c)\in S| {\imath} \leq b\leq p-1\},

R_{1} :=\{(b, c)\in S_{1}|1\leq b\leq p-{\imath}\},P_{1} :=\{(b, c)\in S_{1}\backslash R_{1}|c<[b]_{p}\{b\rangle_{p}\}.
アルゴリズムゴリズム

A は,全ての2次Hensel 根に対して純周期的展開をあたえる

B による展開が純周期的となる2次Hensel 根の集合は,アルゴリズム(定理6,1 (i)). また,アルR であることが簡単に示せる.さらに,

C による展開が純周期的となる2次Hensel 根の集合は,P_{1}\cup R_{1}\cup S_{3}\cup S_{4} であることが証明できる.すなわち定理8.1. アルゴリズム A, B,

C の既約集合は,それぞれ S , R., PĨ \cup R_{1}\cup S_{3}\cup S_{4} である.

62
謝辞
本研究は JSPS 科研費 JP15K00342 の助成を受けたものです.

参考文献[1] H. Bekki, On periodicity of geodesic continued fractions, J. Number Theory 177 (2017), 181‐2ı0.
[2] T. Browkin, Con t inued fraction) s in] local fields, II, MMath. Comp. 70 (2001), 1281‐ı2Q.2.
[3] J.‐L. Lag_{1^{\backslash } ange, Additions an mčmoire snr la rc'\backslash solution des equations numčriques. hI'(^{\backslash }m . Bcrl. 24(1770).

[4] A. A. Ruban, Certain metric properties of p‐adic numbers (Russian): Sibirsk. Mat. Zh. 11 (1970),
222‐227.

[5] A. Saito, J.‐I. Tamura, S. Yasutomi, Continued fraction algorithms and La.grange^{:}s theorem in \mathbb{Q}_{p:}arXiv: 170ı.046l5vl [math.NT].

[6] T. Schneider, Über p‐adische Kettenbrüche, Symp. Math. 4 (1968/69), 181‐ı89.