On efficient approximation of quadratic irrationals

तकनीकी सारांश: द्विघात अपरिमेय संख्याओं का कुशल सन्निकटन (Efficient Approximation of Quadratic Irrationals)

समस्या विवरण
यह शोध पत्र द्विघात अपरिमेय संख्याओं (quadratic irrationals) के सरल सतत भिन्न विस्तार (simple continued fraction expansion) के अभिसरणों (convergents, $p_n/q_n$) की गणना कुशलतापूर्वक करने की कम्प्यूटेशनल चुनौती को संबोधित करता है। जबकि लैग्रेंज का प्रमेय गारंटी देता है कि ऐसे विस्तार अंततः आवर्ती (periodic) होते हैं, बड़े सूचकांकों $n$ के लिए मानक पुनरावृत्ति विधियों का उपयोग करके विशिष्ट अभिसरणों की गणना करने के लिए $O(n)$ ऑपरेशन्स की आवश्यकता होती है। लेखक ऐसे एल्गोरिदम विकसित करने का प्रयास करते हैं जो इस जटिलता को $O(\log n)$ तक कम कर सकें, विशेष रूप से उन सेटिंग्स में जहाँ गैलुआ का लैग्रेंज प्रमेय का परिष्कृत रूप (विशेष रूप से परिमेय संख्याओं के वर्गमूल और कुछ जटिल संख्याओं के लिए) लागू होता है।

कार्यप्रणाली और सैद्धांतिक ढांचा
लेखक द्विघात अपरिमेय संख्याओं के अभिसरण अनुक्रम और चेबिशेव बहुपदों (Chebyshev polynomials) के विभिन्न परिवारों के बीच एक गहरा संबंध स्थापित करते हैं।

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$ का पालन करते हैं।
   • "चिह्नित" (signed) चेबिशेव बहुपद ($T^l_k, U^l_k$) जो आवर्त अवधि की समता (parity) पर निर्भर करते हैं, और $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$ देता है। वे यह दिखाने के लिए केले-हैमिल्टन प्रमेय (Cayley–Hamilton theorem) का लाभ उठाते हैं कि इन मैट्रिसेस की घातों का ट्रेस (trace) परिभाषित चेबिशेव बहुपदों के अनुरूप होता है।

3. डिसिमेशन और आवर्तता (Decimation and Periodicity): शुद्ध आवर्ती या सममित आवर्त संरचना वाले द्विघात अपरिमेयों के लिए (विशेष रूप से परिमेय संख्याओं के वर्गमूल के लिए, जहाँ आवर्त $[c_0, c_1, \dots, c_1, 2c_0]$ के रूप में होता है), लेखक सिद्ध करते हैं कि अभिसरण अनुक्रम के विशिष्ट डिसिमेशन (indices $kl-1$) इन हस्ताक्षरित चेबिशेव बहुपदों द्वारा उत्पन्न होते हैं।

प्रमुख योगदान और एल्गोरिदम
शोध पत्र बड़े $m$ के लिए अभिसरण मैट्रिक्स $\Psi_m$ की गणना करने के लिए चार अलग-अलग एल्गोरिदम प्रदान करता है, जो सभी $O(\log m)$ जटिलता प्राप्त करते हैं।

• सैद्धांतिक परिणाम (प्रमेय 3.1): आवर्त के गुणकों द्वारा अलग किए गए अभिसरण मैट्रिसेस के लिए एक रैखिक पुनरावृत्ति संबंध व्युत्पन्न किया गया है। यह संबंध $\Psi_{n+2ikl}$ को $\Psi_n$ और $\Psi_{n+2ikl}$ के पदों में हस्ताक्षरित चेबिशेव बहुपदों से प्राप्त गुणांकों $t_{2ik}$ का उपयोग करके व्यक्त करता है।
• एल्गोरिदम 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$ की हाउसहोल्डर विधि लागू करने से $(kl-1)$-वाँ अभिसरण प्राप्त होता है, जहाँ$k = d+1$ है।
• विशिष्ट मामले:
  • $d=1$ (न्यूटन की विधि/बेबीलोनियन विधि) $2l-1$-वें अभिसरण को प्राप्त करती है।
  • $d=2$ (हाले की विधि/Halley's method) $3l-1$-वें अभिसरण को प्राप्त करती है।
    यह स्थापित करता है कि हाउसहोल्डर पुनरावृत्ति, जब विशिष्ट आवर्ती संरचना वाले द्विघात अपरिमेयों पर लागू की जाती है, तो वह सतत भिन्न अनुक्रम के विशिष्ट पदों पर सीधे "जंप" करने वाले ऑपरेटर के रूप में कार्य करती है।

महत्ता और दावे
शोध पत्र द्विघात अपरिमेयों के अभिसरणों की गणना करने के लिए "कुशल एल्गोरिदम" प्रदान करने का दावा करता है, जो विशेष रूप से उन सेटिंग्स के लिए अनुकूलित है जहाँ गैलुआ का प्रमेय लागू होता है।

• दक्षता: प्राथमिक महत्व अभिसरण के सूचकांक के सापेक्ष रैखिक से लघुगणकीय (logarithmic) जटिलता में कमी लाना है।
• एकीकरण: यह कार्य सतत भिन्नों, चेबिशेव बहुपदों और पुनरावृत्ति मूल-खोज विधियों (हाउसहोल्डर) के सिद्धांत को एकीकृत करता है। यह प्रदर्शित करता है कि "हस्ताक्षरित चेबिशेव अनुक्रम" केवल गणितीय जिज्ञासाएँ नहीं हैं, बल्कि द्विघात अपरिमेय सन्निकटन की संरचना में अंतर्निहित हैं।
• व्यापकता: हालांकि यह परिमेय संख्याओं के वर्गमूल (जहाँ आवर्त सममित होता है) पर केंद्रित है, लेखक नोट करते हैं कि एल्गोरिदम (3.1–3.5) अन्य जटिल संख्याओं और अन्य द्विघात अपरिमेयों के लिए भी लागू होते हैं, भले ही आवर्त की सख्त सममित संरचना (1.4) मौजूद न हो, बशर्ते कि आवर्त लंबाई $l$ ज्ञात हो।

लेखक इन कुशल गणना विधियों के प्रस्तुत गणितीय ढांचे के परे कोई नए प्रयोगात्मक अनुप्रयोग या भविष्य के अनुसंधान दिशाएँ प्रस्तावित नहीं करते हैं, और इन कुशल गणना विधियों के सैद्धांतिक व्युत्पत्ति और एल्गोरिदम कार्यान्वयन पर ध्यान केंद्रित रखते हैं।