On efficient approximation of quadratic irrationals

技術要約：二次無理数の効率的な近似

問題提起
本論文は、二次無理数の単純連分数展開における近似分数（収束分数）$p_n/q_n$ を効率的に計算するという計算上の課題に対処している。ラグランジュの定理により、これらの展開は最終的に周期性を持つことが保証されているが、標準的な反復法を用いて大きな指数 $n$ の特定の近似分数を計算するには $O(n)$ の操作を必要とする。著者らは、ガロアによるラグランジュの定理の洗練（特に有理数の平方根や特定の複素数において適用されるもの）が適用される設定において、この計算量を $O(\log n)$ に削減するアルゴリズムを求めている。

手法および理論的枠組み
著者らは、二次無理数の近似分数の数列と、様々なチェビシェフ多項式の族との間の深い関連性を確立している。

1. 多項式の定義: 本論文では、以下の多項式列を導入し、それらの関係を示している。

   • 第一種および第二種の標準的なチェビシェフ多項式 ($T_k, U_k$)。
   • 拡張型ディレーション多項式 ($\tilde{T}_k, \tilde{U}_k$) で、$T_{k+2} = xT_{k+1} - T_k$ を満たすもの。
   • 符号変更型多項式 ($\hat{T}_k, \hat{U}_k$) で、$T_{k+2} = xT_{k+1} + T_k$ を満たすもの。
   • 「符号付き」チェビシェフ多項式 ($T^l_k, U^l_k$) で、周期長 $l$ のパリティに依存し、$T^l_{k+2} = 2xT^l_{k+1} - (-1)^l T^l_k$ という形の漸化式を満たすもの。

2. 行列表現: 著者らは、連分数の行列表現（行列 $\begin{pmatrix} c_i & 1 \\ 1 & 0 \end{pmatrix}$ の積が近似分数行列 $\Psi_n$ を与えるもの）を利用している。彼らはケーリー・ハミルトンの定理を活用し、これらの行列のべき乗のトレースが、定義されたチェビシェフ多項式に対応することを示している。

3. デシメーション（間引き）と周期性: 純粋周期または対称な周期構造（特に有理数の平方根において、周期が $[c_0, c_1, \dots, c_1, 2c_0]$ の形式となる場合）を持つ二次無理数の場合、近似分数の数列の間引き（インデックス $kl-1$）が、これらの符号付きチェビシェフ多項式によって生成されることを著者らは証明している。

主要な貢献およびアルゴリズム
本論文は、大きな $m$ に対して近似分数行列 $\Psi_m$ を計算するための、すべて $O(\log m)$ の計算量を実現する4つの異なるアルゴリズムを提供している。

• 理論的結果 (定理 3.1): 周期 $l$ の倍数で隔てられた近似分数行列に関する線形漸化式が導出されている。この関係式は、符号付きチェビシェフ多項式から導かれる係数 $t_{2ik}$ を用いて、$\Psi_{n+2ikl}$ を $\Psi_{n+2ikl}$ と $\Psi_n$ の式として表す。
• アルゴリズム 3.1 (バイナリ、加法的): 周期乗数のバイナリ表現を用いる。これは線形漸化式 (3.1) に依拠しており、行列の積と行列の線形結合を必要とする。著者らは、最悪の場合、線形結合の数が $\log h$ に対して二次的に増加することを指摘している。
• アルゴリズム 3.2 (ネストされたバイナリ、加法的): 線形結合の数を最小限にするために、ネストされたバイナリ表現（ホーナー法スタイル）を用いる。これは、アルゴリズム 3.1 と比較して線形結合の計算コストを削減できるため、推奨される加法的手法として提示されている。
• アルゴリズム 3.3: 加法的手法で必要となるチェビシェフ係数 ($t_k$) を効率的に計算するための補助アルゴリズム。
• アルゴリズム 3.4 および 3.5 (乗法的): これらの手法は、中間係数の決定を行うことなく、行列の平方（積）のみに依拠している。これらは係数の決定を回避する一方で、加法的手法よりも多くの行列積（$n_q + q + 3$ 回）を必要とする。

ハウスホルダー法に関する結果
これらの間引かれた近似分数の数列が、ハウスホルダー法（Householder's method）の反復によって生成されるという、重要な理論的貢献が示されている。

• 定理 5.1: $\sqrt{N}$ の $(l-1)$ 番目の近似分数に対して、次数 $d$ のハウスホルダー法を適用すると、$k = d+1$ として $(kl-1)$ 番目の近似分数が得られる。
• 具体的なケース:
  • $d=1$ （ニュートン法／バビロニア法）は、$2l-1$ 番目の近似分数を与える。
  • $d=2$ （ハレー法）は、$3l-1$ 番目の近似分数を与える。
    これは、ハウスホルダー反復が、特定の周期構造を持つ二次無理理数の連分数列において、特定の項へと直接「ジャンプ」するオペレーターとして機能することを確立している。

意義および主張
本論文は、二次無理数の近似分数を計算するための「効率的なアルゴリズム」を提供することを主張しており、特にガロアの定理が成立する設定において最適化されている。

• 効率性: 主な意義は、近似分数のインデックスに対する計算量を線形から対数へと削減したことにある。
• 統一: 本研究は、連分数、チェビシェフ多項式、および反復的な根の探索法（ハウスホルダー法）の理論を統一している。彼らは、「符号付きチェビシェフ数列」が単なる数学的な好奇心の対象ではなく、二次無理数の近似構造に内在するものであることを示している。
• 汎用性: 焦点は有理数の平方根（周期が対称であるもの）に置かれているが、厳密な対称形式（1.4）が保持されない場合でも、周期長 $l$ が既知であれば、アルゴリズム (3.1–3.5) は複素数やその他の二次無理数にも適用可能であると著者らは述べている。

著者らは、提示された数学的枠組みを超えた新しい実験的応用や将来の研究方向を提案することはせず、これらの効率的な計算手法の理論的導出とアルゴリズムの実装に焦点を絞ったままとしている。