数理解析研究所講究録
第 1639 巻 2009 年 176-186

176

A new multidimensional continued fraction
Algorithm
鈴鹿工業高等専門学校 安富 真一 (Shin-ichi Yasutomi)(Suzuka National college of technology)
津田塾大学・特別研究員 田村 純一 (Jun-ichi Tamura)(Tsuda college)

1

最初にに関して Jacobi-Perron アルゴリズムを適用すると周1,をある実 3 次体
basis としよう。
期的になると信じられている ([12])これを ConjectureS と記すことにしよう。 ここで Jacobi-Perronアルゴリズムとは、 次の $[0,1]^{2}$ 上の次の変換から構成される。
$\alpha,$$\beta$$(\alpha, \beta)$$\mathbb{Q}-$。

(1)$\overline{T}(x,y):=(\frac{y}{x}-L\frac{y}{x}\rfloor, \frac{1}{x}-\lfloor\frac{1}{x}\rfloor)$

しかしながら現時点でその証明にいたっていない。 Bernstein[1] が周期的になるクラスを示しているが、完全な証明にはまだ遠いと思われる。 しかしながら、 ConjectureS が正しいと多くの数学者が確信してる訳ではないような感もある。 実際 Elsner, Hasse[2] は 1967 年に計算機で数値計算を行い、に対$(\sqrt[3]{n}, \sqrt[8]{n^{2}})$して Jacobi-Perron アルゴリズムで周期を確認することができないいくつかの例を報告している。従って、ConjectureS は多少懐疑で持って見られているのだが、否定するほどの材料も無く現在まで残っているように思われる。 連分数の高次元化は、 Jacobi-Perron アルゴリズムだけではなく、 多くのアルゴリズムが提案されてきた。 Schweiger[12] には, それらのアルゴリズムが整理されて紹介されている。例えば、次のアルゴリズムは,Podsypanin[11] によるもので modffied Ja obi-Perron アルゴリズムと呼ばれているものである。。

$\overline{T}(x,$$y):=\{\begin{array}{l}(\frac{y}{x}, \frac{1}{x}-\lfloor\frac{1}{x}\rfloor) if x>y,(\frac{1}{y}-\lfloor\frac{1}{y}\rfloor, \frac{x}{y}) if x<y,\end{array}$$($2)

このアルゴリズムについては、 いわゆる natural extension が構成されているし、 不変測度についても具体的に分かっている。 それらが、未だに不分明な Jacobi-Perron アルゴリズムより一歩進んでいるかもしれない。 また、有理数による同時近似 (Diophantine Approximation) がどの程度実現されうるかの研究もほとんど進んでいないのが現状である。連分数アルゴリズムは最良近似を与えることは良く知られている事実であるが、 これらの Jacobi-Perron アルゴリズムなどのアルゴリズムが一般的に最良近似を与えないことは、難しいことではない。 しかしが生成する 3 次体が、 総実ではなく、 またこれらのアルゴリズムで周期$\alpha,\beta$

177

的である場合、 次のような不等式が成立する ([10])$| \alpha-\frac{p_{n}}{r_{n}}|\leq\frac{c(\alpha,\beta)}{r_{n}^{3/2}}$

ここで$L_{-}^{n}r_{n}’$$g_{\frac{n}{r_{n}}}$。

,$| \beta-\frac{q_{n}}{r_{n}}|\leq\frac{c(\alpha,\beta)}{r_{n}^{3/2}}$,(3)

は、 アルゴリズムから定まる部分分数とする。 すなわち Dirichlet の定理が保障する近似をで実現している。 この場合この有理近似が最良であることが期待できるのであるが残念ながら、反例([6]) このように高次の連分展開の研究は、一筋縄ではいかない。 しかしながら、 このような状況にはじめて本質的とも思われる発展を示したのは田村のアルゴリズム ([13]) である。 このアルゴリズムにより先ほど述べたに対してすべての例で周期的になることを示した。未だ反例は見つかってを Jacobi-Perron アルゴリズムで計算すると周期がみつかりそうない事例にすぐにぶいない。 これはつかるのとは異にしている。実際 Elsner,Hasse はのような組に関して 36 の例で Jacobi-Perronアルゴリズムで計算して 14 の例でしか周期を確認できなかったことを報告している。 したがって田村のアルゴリズム (SF,CF と名付けられている) はまさに高次連分数アルゴリズムにとって希望の星といって良いだろう。我々は、 この田村のアルゴリズム (SF,CF) を受けて、 より Jacobi-Perron アルゴリズムに近い形のアルゴリズムを考案することができた。 そのアルゴリズムも田村のアルゴリズム (SF,CF) と同様に周期性に関しては、優れた性質を持っている。 我々は、 このアルゴリズムを Algebraic Jacobi-Perron アルゴリズム (AJPA) と名付けた。 これらの結果は [15] で発表された。 この論文の結果を中心にして紹介しよう。
$\ r_{n}^{L}$’$9\simeq r_{n}$が見つかっている。

$(\alpha, \beta)$$(\alpha, \beta)$$(\sqrt[3]{n}, \sqrt[3]{n^{2}})$

2

Algebraic Jacobi-Perron アルゴリズム
一般次元で Algebraic Jacobi-Perron アルゴリズムは定義できるがここでは 2 次元で定義する。 $K$ を実 3次体とする。
$X_{K}:=\{(\alpha, \beta)\in K^{2}|1,$$\alpha,$$\beta \mathbb{Q}$上で線形独立}$\cap$

I2,(4)

where $I=[0,1)$ .
$X_{K}$

上の$T_{K}$(5)を次のように定義する。

(6)$T_{K}(\alpha, \beta):=\{\begin{array}{l}(\frac{1}{\alpha}-L\frac{1}{\alpha}\rfloor, E\alpha-L_{\alpha}^{4}\rfloor) if \frac{\alpha}{\sqrt{}|N(\alpha)|}>\frac{\beta}{\sqrt{}|N(\beta)|},(\alpha F-L_{F^{\rfloor}’\partial^{-}}^{\alpha}1L\frac{1}{\beta}\rfloor) if \frac{\alpha}{\sqrt{|N(\alpha)|}}<\frac{\beta}{\sqrt{|N(\beta)|}}\end{array}$

ここで$\lfloor x\rfloor$

は、 $x$ の整数部分とし、 $N(x)$ は $x\in K$ の$\mathbb{Q}$上の norm とする。の上で定義される。従って、通常の位相からするとすべての点に自は一見すると well-dfined然に拡張することによって、 定義より 2 つの領域で連続となることが分かる。
でないように見えるが、 次のように簡単に証明することができる。
このようにこのアルゴリズムは、代数体$K$で $T_{K}$ は不連続となる。 この意味で Jacobi-Perron アルゴリズムなどとは異なっている。 しかし$K\otimes_{Q}\mathbb{R}$$T_{K}$

補題 1. 各 $(\alpha,\beta)\in X_{K}$ に対して
証明.

$\frac{\alpha}{\sqrt{}|N(a)|}=\frac{\beta}{\sqrt{}|N(\beta)|}$$\sqrt{N\alpha H}\not\in \mathbb{Q}$$\frac{\alpha}{\sqrt{|N(\alpha)|}}\neq\frac{\beta}{\sqrt{|N(\beta)|}}$と仮定しよう。 このときであることが分かる o 従って $\sqrt{N\alpha}$となる。

$\alpha=\sqrt{\frac{|N(\alpha)|}{|N(\beta)|}}\beta$となるので$\alpha$と$\beta$の線形独立性より$\sqrt{}$は 2 次の無理数となる。一方》ENN$\alpha\#$)$\in K$となるので

178

$K$

は 3 次体であることに矛盾する。
$(\alpha,\beta)\in X_{K}$あるとする。

が $T_{K}$ によって周期的であるとはある異なる $m,n\in Z_{\geq 0}$ が存在し $T_{K}^{m}(\alpha,\beta)=T_{K}^{n}(\alpha,\beta)$ でにおいて周期的である集合を$X_{K}$$P_{K}$とおく。

現時点では、任意の $(\alpha, \beta)\in X_{K}$ に対して周期性は示されていない。 Jacobi-Perron アルゴリズムについては、 Bemstein[1] が、 いくつかのクラスで周期性を示している。 Algebraic Jacobi-Perron アルゴリズムにおいても同様な結果を得ることができる。 これらを Bernstein のように精密化していこうとは思わないが、少なくとも Jacobi-Perron アルゴリズムと同程度であることは示したい。
定理 2 ([15])とするとき.

$m\in Z_{>0}$$(\alpha, \beta)\in \mathcal{P}\kappa$

定理 3([15]).

$(\alpha, \beta)=(\sqrt[3]{m^{3}+1}-m, \sqrt[3]{(m^{3}+1)^{2}}-m^{2})$となる。

を$\delta_{m}$として $K=\mathbb{Q}(\sqrt[3]{m^{3}+1})$ とする.

$x^{3}-mx+1=0(m\in \mathbb{Z}, m\geq 3)$

とき $K=\mathbb{Q}(\delta_{m})$ は、 総実な 3 次体となり$(\delta_{m}, \delta_{m}^{2})\in \mathcal{P}_{K}$の根で $0<\delta_{m}<1$ を満たすものとする。 このとなる。

ここである種の height を定義する。 この height は最初に田村 [13] で定義されたものである。

$(\alpha_{1},\alpha_{2})$にアルゴリズムを適用したときにその大きさを観察しようというものである。
$E(p,$ $q\in Z,p,$は互いに素 に対して dhを次のように定義する。簡単に言えば 10 進数で表記したと$qq$$)$$(_{q}^{g})$きの桁数を意味する。
$dh$

dh を次のように$\mathbb{Q}[x]$$( \frac{p}{q})$$:= \max\{\lfloor\log_{10}|p|+1\rfloor, \lfloor\log_{10}|q|+1\rfloor\}$$\overline{dh},$$dh_{AJPA}$$dh$(0) $:=0$ .

(7)へ拡張する: $g(x)= \sum_{:=0}^{n}a_{i}x^{i}\in \mathbb{Q}[x]$ に対して、$dh$ $(g)$さらに,$:=_{0} \max_{\leq 1\leq n}\{dh(a_{i})\}$.

(S)および $rdh_{AJPA}$ を以下のように定義する。 $\alpha=(\alpha_{1},\alpha_{2})\in X_{K}$ および $n\in Z_{\geq 0}$ に対して
$dh$ $(\alpha)$$:= \max\{dh(p_{i})\}$ ,(9)$i\in\{1,2\}$$dh_{AJPA}(n;\alpha)$ $:=$ $dh$ $(T_{K}^{n}(\alpha))$,$rdh_{AJPA}(n;\alpha):=\frac{\overline{dh}(T_{K}^{n}(\alpha))}{\overline{dh}(\alpha)}$

(10)

,

(11)
(12)

ここで $p_{i}=$mpol $(\alpha_{i})\in \mathbb{Q}[x](i\in\{1,2\})$ は有理数体上 monic なの最小多項式とする。 さらにおよびに対してを次のように定義する:$(\alpha_{1}, \alpha_{2})\in X_{K}$$\alpha_{i}$$\overline{dh}_{AJPA}$$\alpha=$$\overline{rdh}_{AJPA}$$\overline{dh}_{AJPA}(\alpha):=\sup_{n\in Z_{\geq 0}}dh_{AJPA}(n;\alpha)$$\overline{rdh}_{AJPA}(\alpha);=\frac{\overline{dh}_{AJPA}(\alpha)}{\overline{dh}(\alpha)}$

.

,

(13)
(14)

179

今後同様な $X_{K}$ 上のアルゴリズム $A$ について同様に $dh_{A}(n;\alpha),$ $rdh_{A}(n;\alpha),$$\mathcal{P}_{K}^{A}$$\overline{dh}_{A}(\alpha),$$\overline{rdh}_{A}(\alpha)$

およびを定義するとする。

次の TABLE A は $(\sqrt[3]{29}-3, \sqrt[3]{29}^{2}-9)$ に関して AJPA を適用したものである。numbern は、$T_{AJPA}^{n}(\{\sqrt[\mathfrak{g}]{29}-$とする。周期は 46 となる。計算に利用した数式処理システムは Ginac[7]上の基底 $\{1, x,x^{2}\}$ で $T_{AJPA}^{n}(\sqrt[\theta]{29}-3, \sqrt[3]{29}^{2}-9)$ を表したとき、 その係数が、低く抑えられることが分かる。 この現象はこの例に留まらず、数値実験したすべての例で成立していた。

$3,$ $\sqrt[3]{29}^{2}-9)$とする。以下で$x=\sqrt[3]{29}$である。 この例では $\overline{dh}_{AJPA}=3$ となりまた$\mathbb{Q}(x)$TABLE A

numberO $(-3+x, -9+x^{2})$$dh_{AJPA}3$

numberl $(-17/2+1/2x^{2}+3/2x, -3+x)$$dh_{AJPA}3$

number2 $(-1S6/2S7+13/287x^{2}+40/2S7x, 74/2S7+1/2S7x^{2}-19/2S7x)$$dh_{AJPA}3$

number3 $(-11/4+1/4x^{2}+1/4x, -23/4+1/4x^{2}+5/4x)$$dh_{AJPA}2$

number4 $(-39/31+3/31x^{2}+10/31x, 18/31+1/31x^{2}-7/31x)$$dh_{AJPA}3$$—————————————-$

number5 $(-11/4+1/4x^{2}+1/4x, - 23/8+1/8x^{2}+5/8x)$$dh_{AJPA}2$

number6 $(-39/31+3/31x^{2}+10/31x, 49/62+1/62x^{2}-7/62x)$$dh_{AJPA}3$

number7 $(-2+1/6x^{2}+1/6x, 1/6+1/6x)$$dh_{AJPA}3$

number8 $(-2/5-2/5x^{2}+7/5x, -4/5+1/5x^{2}-1/5x)$$dh_{AJPA}3$

number9 $(-21/16+3/16x^{2}-1/16x, -23/16+1/16x^{2}+5/16x)$$dh_{AJPA}2$

180

number10 $(-60/31+4/31x^{2}+15/31x, 16/31+1/31x^{2}-4/31x)$$dh_{AJPA}3$

numberll $(-7/3+1/3x^{2}, -2/3+1/3x)$$dh_{AJPA}3$

number12 $(-4/7-1/7x^{2}+5/7x, -10/7+1/7x^{2}+2/7x)$$dh_{AJPA}2$

number13 $(9/37+3/37x^{2}-8/37x, -31/37+2/37x^{2}+7/37x)$$dh_{AJPA}2$

number14 $(-19/20+1/20x^{2}+9/20x, 1/10+1/10x^{2}-1/10x)$$dh_{AJPA}2$

number15 $(-5/6+1/6x^{2}-1/6x, -2/3+1/3x)$$dh_{AJPA}1$

number16 $(3/14-1/14x^{2}+5/14x, -10/7+1/7x^{2}+2/7x)$$dh_{AJPA}2$

number17 $(-10/21+2/21x^{2}+1/21x, -16/21-1/21x^{2}+10/21x)$$dh_{AJPA}2$

number18 $(-15/17+1/17x^{2}+6/17x,4/17+2/17x^{2}-5/17x)$$dh_{AJPA}2$

number19 $(-37/40+3/40x^{2}+7/40x, -1/40-1/40x^{2}+11/40x)$$dh_{AJPA}3$

number20 $(10/23-2/23x^{2}+7/23x, -15/23+3/23x^{2}+1/23x)$$dh_{AJPA}2$$number21(-5/22+1/11x^{2}+1/22x, -19/22+1/22x^{2}+3/11x)$$dh_{AJPA}2$

number22 $(-34/31+1/31x^{2}+11/31x, 25/31+2/31x^{2}-9/31x)$$dh_{AJPA}3$

181

number23 $(-10/21+2/21x^{2}+1/21x, -5/42+1/42x^{2}+11/42x)$$dh_{AJPA}2$

number24 $(13/25-2/25x^{2}+7/25x, -32/25+3/25x^{2}+2/25x)$$dh_{AJPA}3$

number25 $(-11/34+3/34x^{2}+1/34x, -19/34-1/34x^{2}+11/34x)$$dh_{AJPA}2$

number26 $(-20/21+1/21x^{2}+S/21x, 2/21+2/21x^{2}-5/21x)$$dh_{AJPA}2$

number27 $(-41/49+4/49x^{2}+9/49x, -2/49-1/49x^{2}+10/49x)$$dh_{AJPA}3$

number28 $(-3/11-1/11x^{2}+5/11x, -16/11+2/11x^{2}+1/11x)$$dh_{AJPA}2$

number29 $(1/15+1/15x^{2}-1/15x, -3/5+1/15x^{2}+4/15x)$$dh_{AJPA}2$

number30 $(-3/2+1/2x, -1/3+1/6x^{2}-1/6x)$$dh_{AJPA}2$$number31(-2/35+3/35x^{2}-S/35x, -24/35+1/35x^{2}+9/35x)$$dh_{AJPA}2$

number32 $(-3/22-1/22x^{2}+5/22x, -35/22+3/22x^{2}+7/22x)$$dh_{AJPA}3$

number33 $(-14/3+1/3x^{2}+2/3x, -3+x)$$dh_{AJPA}2$

number34 $(-39/85+6/S5x^{2}+19/S5x, 36/S5+1/S5x^{2}-11/S5x)$$dh_{AJPA}3$

number35 $(-17/14+1/14x^{2}+3/14x, -2/7+1/7x)$$dh_{AJPA}3$

number36 $(11/6-1/6x^{2}+1/6x, -14/3+1/3x^{2}+2/3x)$182$dh_{AJPA}2$

number37 $(-16/41+2/41x^{2}+3/41x, -49/41+1/41x^{2}+22/41x)$$dh_{AJPA}3$

number38 $(-19/7+1/7x^{2}+4/7x,2/7+1/7x^{2}-3/7x)$$dh_{AJPA}2$

number39 $(-5/6+1/6x^{2}-1/6x, -23/12+1/12x^{2}+5/12x)$$dh_{AJPA}2$

number40 $(-19/7+1/7x^{2}+4/7x,9/14+1/14x^{2}-3/14x)$$dh_{AJPA}2$$number41(-1+1/4x^{2}-1/4x, -1/4+1/4x)$$dh_{AJPA}3$

number42 $(-8/7-1/7x^{2}+6/7x, -6/7+1/7x^{2}+1/7x)$$dh_{AJPA}3$

number43 $(1/8+1/8x^{2}-3/8x, -23/24+1/24x^{2}+5/24x)$$dh_{AJPA}2$

number44 $(-19/5+1/5x^{2}+4/5x, 1/15+1/15x^{2}-1/15x)$$dh_{AJPA}3$

number45 $(1/2x^{2}-3/2x, -3/2+1/2x)$$dh_{AJPA}3$

number46 $(-3+x, -18+x^{2}+3x)$$dh_{AJPA}3$

number47 $(-17/2+1/2x^{2}+3/2x, -3+x)$$dh_{AJPA}3$

一方次の TABLEB は $(\sqrt[s]{29}-3, \sqrt[3]{29}^{2}-9)$ に関して MJPA を適用したもので、。 $T_{AIJPA}^{n}(\sqrt[3]{29}-3,$$9)(n=20,40,100,200)$ を示している。
このように急速に height は大きくなっていくのが観察できる。 前の AJPA と対照的である。

$\sqrt[3]{29}^{2}-$

183

TABLE
–––––––––––––––––––––

–

–

$C$––

––

–

–

––

–

–

–

–

–

–

–

– –

number20 $(-2172/547+123/547x^{2}+379/547x, -9S3/547+67/547x^{2}+202/547x)$$dh_{MJPA}5$$—————————————-$

number40 $(9111/10179S-433/10179Sx^{2}-1325/10179Sx$ ,$-158253/50899+9750/50S99x^{2}+29953/50S99x)$$dh_{MJPA}6$
–

–

–

–

––

––

–

–

––––––––––––––––––––––––––––– –number100 $(273430309/624S46571+14756220/624S46571x^{2}+45335783/624846571x$,$-653116030979/647341047556+47331S13617/647341047556x^{2}$$+145418327357/647341047556x)$$dh_{MJPA}13$
–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

–

– –

number200 $(-22645573S195255S04565S4/3799S22916SS71353120641$$+2431835731591459955051/37998229168871353120641x^{2}$$+7471369S35472494400511/3799S22916SS71353120641x$ ,$-844842561970600678711S2/1S9991145S44356765603205$$+13120414020127166628613/189991145844356765603205x^{2}$$+4031006S7540011S3115502/1S9991145S44356765603205x)$$dh_{MJPA}24$

次の例は$(\sqrt[3]{m}-\lfloor\sqrt[3]{m}\rfloor, \sqrt[8]{m}-\lfloor\sqrt[3]{m^{2}}\rfloor)(2\leq m\leq 30)$

が 25 を越えた時点で計算を打ち切り、空白とした。

に対して周期を計算したものである。 $dh_{MJPA}$184

TABLE $D$

TABLED から観察されるように、 AJPA は height が大きくならず、周期も確実に見つかっている。 MJPAは、 すぐに係数爆発に遭遇し、 周期が計算できる例は多くない。

3予想前の章で 2 次元の AJPA を紹介したが、 容易に一般次元に拡張できる。

$n$次元の AJPA は $n+1$ 次体の要素上で動かすことになる。 数値計算例やいくつかの類の例から我々は次の予想を提出する。

1. 2 次元および 3 次元 AJPA はすべて周期的となる。

185

2. 2 次元および 3 次元 AJPA に関して、 体 $K$ によらないある定数$C$が存在して任意の $\alpha\in X_{K}$ に対して(15)$\overline{rdh}_{AJPA}(\alpha)<c$

今まで、多次元連分展開の試みは、連分数の成功に比してあまりにもみすぼらしいものであった。 田村のアルゴリズム同様にこのアルゴリズムが、 この分野に暁光を与えることを望む。研究はまだ始まったばかりである。今後は、たとえば伊藤俊次氏が中心になり現在強力に進めている新数の幾何とも言える substitutionの数学とも融合をはたしていくだろう。入門としては [4] を参照願いたい。

参考文献[1] L.Bemstein;The Jacobi-Perron algorithm–Its theory and application. Lecture Notes in Mathematics, Vol. 207 Springer-Verlag, Berlin-New York (1971).
[2] L.Elsner, H.Hasse; Numerische Ergebnisse zum Jacobischen Kettenbruchalgorithmus in reinkubischen Zahlkorpern. (German) Math. Nachr. $34(1967),95- 97$ .
[3] T.Fujita, Sh.Ito, M.Keane, and M.Ohtsuki;On almost everywhere exponential convergence of modi-fied Jacobi-Perron algorithm: a corrected proof, Ergodic theory an dynamical systems. 16(1996), 1345-1352.
[4] S.Ito;Diophantine approximations, substitutions, and fractals. Substitutions in dynamics, arithmetics
and combinatorics, 253-292, Lecture Notes in Math., 1794, Springer, Berlin, 2002
[5] S.Ito, J.Fujii, H,Higashino and S.Yasutomi; On simultaneous approximation to$k\alpha-1=0_{1}J$$[6]$. Number Theory. 1 $(2003),255- 283$ .

$(\alpha, \alpha^{2})$with$\alpha^{3}+$SIto and SYasutomi; On simultan 伽科 us approximation certain periodic points related tO modified
Jacobi-Perron algorithm, to appear in Advanced Studies in Pure Mathematics.
$t\circ$[7] GiNaC web site:http://www.ginac.de/.

[8] D. N. Lehmer; On Jacobi’s Extension of the Continued Fraction Algorithm, Proc Natl Acad Sci
S A. 1918 December; 4(12): 360-364.
$[$$U$

9 C.D.Olds; Continued fractions. Random House, New York 1963.
$]$[10] O.Perron;Grundlagen f\"ur eine Theorie des Jacobischen Kettenbruchalgorithmus, Math.Ann.64$(1907),1- 76$ .

[11] E.V.Podsypanin;A generalization of continued fraction algorithm that is related to the Viggo Brunalgorithm (Russian), Studies in Number Theory $(LOMI),4.$ ,Zap. Naucn. Sem. Leningrad. Otdel. Mat.
Inst. Steklov,67(1977), 184-194.

186[12] F.Schweiger, Multidimensional continued fractions. Oxford Science Publications. Oxford UniversityPress, Oxford, 2000.

[13] J. Tamura; A new approach to higher dimensional continued fractions, preprint.
[14] J. $Tamura;A$ class of transcendental numbers having explicit g-adic and Jacobi-Perron expansionsof arbitrary dimension. Acta Arith. 71 (1995), no. 4, 301-329.

[15] J. Tamura and S. Yasutomi;A new multidimensional continued fraction Algorithm, to appear inMath. Comp.