チャクラヴァラ法

チャクラヴァラ法（サンスクリット語：चक्रवाल विधि ）は、ペル方程式を含む不定二次方程式を解く巡回アルゴリズムである。一般的にはバースカラ2世（1114年頃 – 1185年）の作とされているが^{[1] [2] 、}ジャヤデーヴァ（950年頃 ~ 1000年）の作とする者もいる。 ^{[3]ジャヤデーヴァは、この種の方程式を解く}ブラフマグプタの手法は一般化できると指摘し、この一般法について説明した。この方法は後にバースカラ2世が著書『ビジャガニタ』で改良した。ジャヤデーヴァはこれをチャクラヴァラ法と呼んだ。チャクラはサンスクリット語で「車輪」を意味し、アルゴリズムの巡回性を指している。^[4] C.-O.セレニウスは、バースカラの時代も、その後も、ヨーロッパのどの演奏も、その驚異的な数学的複雑さの頂点を超えるものはなかったと主張した。^{[1] [4]}

この方法は巡回法としても知られており、数学的帰納法の痕跡が含まれています。^[5]

チャクラはサンスクリット語で循環を意味します。一般的な伝説によると、チャクラヴァラは光と闇に制限されずに地球の周りを壁のように周回する神話上の山脈を指します。^[6]

628年にブラフマグプタはペル方程式を含む不定二次方程式を研究した。

${\displaystyle \,x^{2}=Ny^{2}+1,}$

最小の整数xとyについて。Brahmagupta はいくつかのNについてこれを解くことができましたが、すべてではありませんでした。

ジャヤデーヴァとバースカラは、チャクラヴァラ法を用いてこの方程式の完全な解を初めて提示した。 ${\displaystyle \,x^{2}=61y^{2}+1,}$

${\displaystyle \,x=1766319049,y=226153980.}$

この問題は難解なことで有名で、ヨーロッパでは1657年から1658年にかけて、フェルマーの挑戦に応えてブラウンカーが連分数を使って初めて解決した。この問題の一般解法は、1766年にラグランジュによって初めて厳密に完全に記述された。 ^{[7]しかし、ラグランジュの方法で61の}平方根を求めるには、単純な連分数の21の連続収束式を計算する必要があるのに対し、チャクラヴァラ法ははるかに簡単である。セレニウスはチャクラヴァラ法の評価で次のように述べている。

「この方法は、いくつかの最小化特性により、最小限の労力で大きな数値を避け、方程式の最良の解を自動的に生成する、最小の長さの最良の近似アルゴリズムを表しています。チャクラヴァラ法は、ヨーロッパの方法を 1000 年以上も先取りしていました。しかし、バスカラよりずっと後の時代、いや、現代までほぼ同等の時代の代数学の分野全体で、チャクラヴァラの驚くべき複雑さと独創性に匹敵するヨーロッパの業績はありませんでした。」^{[1] [4]}

ヘルマン・ハンケルはチャクラヴァラ法 と呼んでいる

「ラグランジュ以前の数論で達成された最も優れたもの」^[8]

ブラフマグプタの恒等式から、 Nが与えられた場合、

${\displaystyle (x_{1}x_{2}+Ny_{1}y_{2})^{2}-N(x_{1}y_{2}+x_{2}y_{1})^{2 }=(x_{1}^{2}-Ny_{1}^{2})(x_{2}^{2}-Ny_{2}^{2})}$

方程式の場合、 2つの解のトリプルとを「合成」（samāsa ）して、新しいトリプルを作る ことができます。${\displaystyle x^{2}-Ny^{2}=k}$${\displaystyle (x_{1},y_{1},k_{1})}$${\displaystyle (x_{2},y_{2},k_{2})}$

${\displaystyle (x_{1}x_{2}+Ny_{1}y_{2}\,,\,x_{1}y_{2}+x_{2}y_{1}\,,\,k_{1}k_{2}).}$

一般的な方法では、主要なアイデアは、任意の 3 つ組(つまり、 を満たすもの) を自明な 3 つ組と合成して、任意のmに対する新しい 3 つ組を取得できるというものです。 の 3 つ組から始めたと仮定すると、これをkだけ縮小できます(これがBhaskara の補題です)。 ${\displaystyle (a,b,k)}$${\displaystyle a^{2}-Nb^{2}=k}$${\displaystyle (m,1,m^{2}-N)}$${\displaystyle (am+Nb,a+bm,k(m^{2}-N))}$${\displaystyle \gcd(a,b)=1}$

${\displaystyle a^{2}-Nb^{2}=k\Rightarrow \left({\frac {am+Nb}{k}}\right)^{2}-N\left({\frac {a+bm}{k}}\right)^{2}={\frac {m^{2}-N}{k}}}$

四角の中の符号は重要ではないので、次の置換が可能です。

${\displaystyle a\leftarrow {\frac {am+Nb}{|k|}},b\leftarrow {\frac {a+bm}{|k|}},k\leftarrow {\frac {m^{2}-N}{k}}}$

正の整数mが選択されて ( a  +  bm )/ kが整数になると、3つの数列の他の2つの数も整数になります。このようなmの中から、この方法ではm ²  −  Nの絶対値を最小化し、したがって ( m ²  −  N )/ kの絶対値を最小化するものが選ばれます。次に、選択された値に等しいmに対して置換関係が適用されます。これにより、新しい3つの数列 ( a、b、k ) が生成されます。このプロセスは、次の数列が見つかるまで繰り返されます。この方法は常に解で終了します (1768 年にラグランジュによって証明されました)。^{[9]オプションとして、} kが ±1、±2、または ±4 の ときに停止することもできます。Brahmagupta のアプローチでは、これらの場合に解が得られるためです。 ${\displaystyle k=1}$

628年、ブラフマグプタは、kが±1、±2、または±4のときに、およびを求める一般的な方法を発見しました。 ^[10]${\displaystyle x}$${\displaystyle y}$${\displaystyle x^{2}=Ny^{2}+1,}$${\displaystyle a^{2}=Nb^{2}+k}$

Brahmagupta の恒等式を使用して、三つ組をそれ自体で構成します。 ${\displaystyle (a,b,k)}$

${\displaystyle (a^{2}+Nb^{2})^{2}-N(2ab)^{2}=k^{2}}$ ${\displaystyle \Rightarrow}$ ${\displaystyle (2a^{2}-k)^{2}-N(2ab)^{2}=k^{2}}$

新しいトリプルは として表現できます。 ${\displaystyle (2a^{2}-k,2ab,k^{2})}$

代入すると解が得られます: ${\displaystyle k=-1}$

${\displaystyle x=2a^{2}+1,y=2ab}$

については、元の解はすでに存在していました。 を代入すると、2 番目の解が得られます。 ${\displaystyle k=1}$${\displaystyle (a,b)}$${\displaystyle k=1}$

${\displaystyle x=2a^{2}-1,y=2ab}$

再び方程式を使うと、${\displaystyle (2a^{2}-k)^{2}-N(2ab)^{2}=k^{2}}$${\displaystyle \Rightarrow}$${\displaystyle \left({\frac {2a^{2}-k}{k}}\right)^{2}-N\left({\frac {2ab}{k}}\right)^{2}=1}$

を代入すると、 ${\displaystyle k=2}$

${\displaystyle x=a^{2}-1,y=ab}$

を代入すると、 ${\displaystyle k=-2}$

${\displaystyle x=a^{2}+1,y=ab}$

を式に代入すると、3 つの が作成されます。 ${\displaystyle k=4}$${\displaystyle ({\frac {2a^{2}-4}{4}})^{2}-N({\frac {2ab}{4}})^{2}=1}$${\displaystyle ({\frac {a^{2}-2}{2}},{\frac {ab}{2}},1)}$

が偶数の場合の解決策は次のとおりです。 ${\displaystyle a}$

${\displaystyle x={\frac {a^{2}-2}{2}},y={\frac {ab}{2}}}$

a が奇数の場合は、方程式とから始めます。 ${\displaystyle ({\frac {a}{2}})^{2}-N({\frac {b}{2}})^{2}=1}$${\displaystyle ({\frac {2a^{2}-4}{4}})^{2}-N({\frac {2ab}{4}})^{2}=1}$

三つ組とにつながる。三つ組を合成すると${\displaystyle ({\frac {a}{2}},{\frac {b}{2}},1)}$${\displaystyle ({\frac {a^{2}-2}{2}},{\frac {ab}{2}},1)}$${\displaystyle ({\frac {a}{2}}(a^{2}-3))^{2}-N({\frac {b}{2}}(a^{2}-1))^{2}=1}$

奇数の場合は、 ${\displaystyle a}$

${\displaystyle x={\frac {a}{2}}(a^{2}-3),y={\frac {b}{2}}(a^{2}-1)}$

のとき、 となります。 自身と合成すると となります。 ${\displaystyle k=-4}$${\displaystyle ({\frac {a}{2}})^{2}-N({\frac {b}{2}})^{2}=-1}$${\displaystyle ({\frac {a^{2}+Nb^{2}}{4}})^{2}-N({\frac {ab}{2}})^{2}=1}$${\displaystyle \Rightarrow}$${\displaystyle ({\frac {a^{2}+2}{2}})^{2}-N({\frac {ab}{2}})^{2}=1}$

再び構成すると${\displaystyle ({\frac {(a^{2}+2)^{2}+Na^{2}b^{2})}{4}})^{2}-N({\frac { ab(a^{2}+2)}{2}})^{2}=1}$${\displaystyle \Rightarrow}$ ${\displaystyle ({\frac {a^{4}+4a^{2}+2}{2}})^{2}-N({\frac {ab(a^{2}+2)}{2}})^{2}=1}$

最後に、前の式から、3つのとを合成して、 ${\displaystyle ({\frac {a^{2}+2}{2}},{\frac {ab}{2}},1)}$${\displaystyle ({\frac {a^{4}+4a^{2}+2}{2}},{\frac {ab(a^{2}+2)}{2}},1)}$

${\displaystyle ({\frac {(a^{2}+2)(a^{4}+4a^{2}+2)+Na^{2}b^{2}(a^{2}+2)}{4}})^{2}-N({\frac {ab(a^{4}+4a^{2}+3)}{2}})^{2}=1}$${\displaystyle \Rightarrow }$${\displaystyle ({\frac {(a^{2}+2)(a^{4}+4a^{2}+1)}{2}})^{2}-N({\frac {ab(a^{2}+3)(a^{2}+1)}{2}})^{2}=1}$${\displaystyle \Rightarrow }$${\displaystyle ({\frac {(a^{2}+2)[(a^{2}+1)(a^{2}+3)-2)]}{2}})^{2}-N({\frac {ab(a^{2}+3)(a^{2}+1)}{2}})^{2}=1}$。

これが解決策となる

${\displaystyle x={\frac {(a^{2}+2)[(a^{2}+1)(a^{2}+3)-2)]}{2}}y={\frac {ab(a^{2}+3)(a^{2}+1)}{2}}}$^[11]

(注意:はペル方程式の解を求めるのに役立ちますが、常に最小の整数ペアになるわけではありません。例: 。方程式 は を与え、これをペル方程式に代入すると となり、これは機能しますが、の場合も同様です。 ${\displaystyle k=-4}$${\displaystyle 36^{2}-52*5^{2}=-4}$${\displaystyle x=1093436498,y=151632270}$${\displaystyle 1195601955878350801-1195601955878350800=1}$${\displaystyle x=649,y=90}$${\displaystyle N=52}$

何世紀も後にフェルマーが挑戦状をたたきつけたn = 61の場合 （を満たす整数解を求める）は、バースカラによって例として挙げられた。^[9]${\displaystyle a^{2}-61b^{2}=1}$

まず、あらゆる手段で見つかった任意のkの解から始めます。この場合、b を1 とすることができます。したがって、 なので、3 つの が得られます。これを と合成すると3 つの が得られ、これを縮小すると (またはBhaskara の補題を直接使用して)、次の式が得られます。 ${\displaystyle a^{2}-61b^{2}=k}$${\displaystyle 8^{2}-61\cdot 1^{2}=3}$${\displaystyle (a,b,k)=(8,1,3)}$${\displaystyle (m,1,m^{2}-61)}$${\displaystyle (8m+61,8+m,3(m^{2}-61))}$

${\displaystyle \left({\frac {8m+61}{3}},{\frac {8+m}{3}},{\frac {m^{2}-61}{3}}\right).}$

3 が を割り切って最小値になるようにするには、 を選択して 3 重 を得ます。k が −4 になったので、 Brahmagupta の考えを使用できます。つまり、 を有理解 にスケールダウンできます。これは、それぞれ と 3 回自身を合成します。k が平方になり、スケーリングを適用できる場合は、 が得られます。最後に、この手順を解が見つかるまで繰り返すことができます (さらに 9 回の自己合成と 4 回の平方スケーリングが必要です)。これが最小の整数解です。 ${\displaystyle 8+m}$${\displaystyle |m^{2}-61|}$${\displaystyle m=7}$${\displaystyle (39,5,-4)}$${\displaystyle (39/2,5/2,-1)\,}$${\displaystyle m={7,11,9}}$${\displaystyle (1523/2,195/2,1)\,}$${\displaystyle (1766319049,\,226153980,\,1)}$

xとyについて解くとしよう。^[12]${\displaystyle x^{2}-67y^{2}=1}$

何らかの方法で見つかった任意のkの解から始めます。この場合、b を1 にして を作成します。各ステップで、 k がa  +  bm を割り切り、 | m ² − 67| が最小となる ようなm > 0 を見つけます。次に、 a、b、k をそれぞれとに 更新します。 ${\displaystyle a^{2}-67b^{2}=k}$${\displaystyle 8^{2}-67\cdot 1^{2}=-3}$${\displaystyle {\frac {am+Nb}{|k|}},{\frac {a+bm}{|k|}}}$${\displaystyle {\frac {m^{2}-N}{k}}}$

最初の反復

となります。kがa  +  bmを割り切る、つまり 3 が 8 + m を割り切り、| m ²  − 67| が最小となるような正の整数m が必要です。最初の条件は、 mが 3 t + 1 (つまり 1、4、7、10、… など) の形式であることを意味し、そのようなmの中で、最小値はm = 7 で達成されます。( a、  b、  k ) を に置き換えると、新しい値が得られます。つまり、新しい解が得られます。 ${\displaystyle (a,b,k)=(8,1,-3)}$${\displaystyle \left({\frac {am+Nb}{|k|}},{\frac {a+bm}{|k|}},{\frac {m^{2}-N}{k}}\right)}$${\displaystyle a=(8\cdot 7+67\cdot 1)/3=41,b=(8+1\cdot 7)/3=5,k=(7^{2}-67)/(-3)=6}$

${\displaystyle 41^{2}-67\cdot (5)^{2}=6.}$

この時点で、巡回アルゴリズムの 1 ラウンドが完了します。

2回目の反復

ここで、このプロセスを繰り返します。 となります。k がa  +  bmを割り切る、つまり 6 が 41 + 5 mを割り切り、| m ^{2 − 67| が最小となるような}m  > 0 が必要です 。 最初の条件は、m が6 t  + 5 (つまり 5、11、17、… など) の形式であることを意味し、そのようなmの中で、| m ^{2 − 67| は}m = 5 に対して最小です。 これにより、新しい解a  = (41⋅5 + 67⋅5)/6 などが得られます。 ${\displaystyle (a,b,k)=(41,5,6)}$

${\displaystyle 90^{2}-67\cdot 11^{2}=-7.}$

3回目の反復

7 で 90 + 11 m を割り切るには、 m = 2 + 7 t (つまり、2、9、16、…など)である必要があり、そのようなmの中からm = 9 を選択します。

${\displaystyle 221^{2}-67\cdot 27^{2}=-2.}$

最終解決策

この時点で、巡回法を続けることができます（そして、7回の反復後に終了します）が、右辺は±1、±2、±4の間であるため、Brahmaguptaの観察を直接使用することもできます。3つの数（221、27、-2）をそれ自体と合成すると、次のようになります。

${\displaystyle \left({\frac {221^{2}+67\cdot 27^{2}}{2}}\right)^{2}-67\cdot (221\cdot 27)^{2}=1,}$

つまり、整数解が得られます。

${\displaystyle 48842^{2}-67\cdot 5967^{2}=1.}$

この式は、約 の範囲内で を 近似 します。 ${\displaystyle {\sqrt {67}}}$${\displaystyle {\frac {48842}{5967}}}$${\displaystyle 2\times 10^{-9}}$

• フロリアン・カジョリ（1918）「数学的帰納法」の名称の由来、アメリカ数学月刊誌 25（5）、p.197-201。
• ジョージ・ゲヴェルゲーズ・ジョセフ『孔雀の紋章：数学の非ヨーロッパ的ルーツ』（1975年）。
• GR Kaye、「インドの数学」、Isis 2 :2 (1919)、326–356 ページ。
• Clas-Olaf Selenius、「JayadevaとBhaskara IIのチャクラヴァラ過程の理論的根拠」Wayback Machineに2021年11月30日にアーカイブ、Historia Mathematica 2（1975）、pp. 167–184。
• Clas-Olaf Selenius、「Kettenbruchtheoretische Erklärung der zyklischen Methode zur Lösung der Bhaskara-Pell-Gleichung」、Acta Acad。阿保。数学。物理学。 23 (10) (1963)、1 ～ 44 ページ。
• ホイバーグ、デール、ラムチャンダニ、インドゥ (2000)。学生のブリタニカ・インド。ムンバイ：人気のプラカシャン。ISBN 0-85229-760-2 
• グーナティレイク、スザンサ（1998年）。『グローバル科学に向けて：文明の知識の発掘』インディアナ州：インディアナ大学出版局。ISBN 0-253-33388-1。 
• クマール、ナレンドラ（2004）。古代インドの科学。デリー：Anmol Publications Pvt Ltd。ISBN 81-261-2056-8 
• Ploker, Kim (2007)「インドの数学」。エジプト、メソポタミア、中国、インド、イスラムの数学: 資料集 ニュージャージー: プリンストン大学出版局。ISBN 0-691-11485-4 
• エドワーズ、ハロルド（1977年）。フェルマーの最終定理。ニューヨーク：シュプリンガー。ISBN 0-387-90230-9。

• チャクラヴァラの紹介