The largest 5th pivot may be the root of a 61st degree polynomial

यहाँ जेम्स चेन, एलन एडलमैन और जॉन उर्सचेल के शोध पत्र "The Largest 5th Pivot May Be the Root of a 61st Degree Polynomial" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या का विवरण (Problem Statement)

यह शोध पत्र संख्यात्मक रैखिक बीजगणित (numerical linear algebra) के एक मौलिक प्रश्न को संबोधित करता है: एक $n \times n$ वास्तविक आव्यूह (real matrix) पर पूर्ण पिवोटिंग (complete pivoting) के साथ गॉसियन एलिमिनेशन करने पर अधिकतम संभावित ग्रोथ फैक्टर ($g$) क्या हो सकता है?

• संदर्भ: ग्रोथ फैक्टर $g(A)$, मूल आव्यूह $A$ के सबसे बड़े तत्व और $L$ तथा $U$ कारकों के सबसे बड़े तत्व के अनुपात को मापता है। एक बड़ा ग्रोथ फैक्टर संभावित संख्यात्मक अस्थिरता (numerical instability) को दर्शाता है।
• ज्ञात अनुक्रम: आयाम $n=1, 2, 3, 4$ के लिए, अधिकतम ग्रोथ फैक्टर्स क्रमशः $1, 2, 2.25, 4$ ज्ञात हैं।
• खुली समस्या: $n=5$ के लिए, सटीक अधिकतम मान अत्यंत मायावी रहा है। 1988 से, संख्यात्मक अनुकूलन (numerical optimization) (NPSOL, LANCELOT, और JuMP जैसे उपकरणों का उपयोग करके) लगातार लगभग 4.1325 का अधिकतम मान सुझाता रहा है। हालाँकि, इस बात का कोई प्रमाण नहीं था कि यह वास्तव में वास्तविक अधिकतम है, न ही इस संख्या का सटीक बीजगणितीय रूप ज्ञात था।
• ऊपरी सीमाएँ (Upper Bounds): इस कार्य से पूर्व, $n=5$ के लिए ज्ञात सर्वोत्तम सैद्धांतिक ऊपरी सीमा $4\frac{17}{18} \approx 4.94$ (टॉर्नहेम, 1969) थी।

2. कार्यप्रणाली (Methodology)

लेखक संख्यात्मक अनुकूलन (numerical optimization) को सटीक प्रतीकात्मक बीजगणित (exact symbolic algebra) और इंटरवल अंकगणित (interval arithmetic) के साथ जोड़ने वाला एक अभिनव हाइब्रिड दृष्टिकोण पेश करते हैं। कार्यप्रणाली को दो मुख्य भागों में विभाजित किया गया है: सटीक निचली सीमा (अनुमानित अधिकतम) खोजना और सैद्धांतिक ऊपरी सीमा में सुधार करना।

A. "JuMP + Groebner Basis + Discriminant" दृष्टिकोण (निचली सीमा)

इस तकनीक का उपयोग $n=5$ (और $n=6, 7, 8$) के लिए अधिकतम ग्रोथ फैक्टर की सटीक बीजगणितीय प्रकृति निर्धारित करने के लिए किया जाता है।

1. संख्यात्मक अनुकूलन (Numerical Optimization): लेखक गैर-रैखिक अनुकूलन करने के लिए JuMP (Julia for Mathematical Programming) पैकेज का उपयोग करते हैं। यह एक संभावित आव्यूह संरचना की पहचान करता है और सुझाव देता है कि इष्टतम (optimum) पर कौन सी बाधाएं (constraints) "सख्त" (tight/active equalities) हैं।
2. बाधा निर्धारण (Constraint Fixing): संख्यात्मक आउटपुट के आधार पर, लेखक समानता बाधाओं (जैसे कि आव्यूह के विशिष्ट प्रविष्टियाँ या मध्यवर्ती शूर कॉम्प्लीमेंट्स (Schur complements) का $\pm 1$ के बराबर होना) को स्थिर करते हैं।
3. प्रतीकात्मक विलोपन (Symbolic Elimination - Groebner Bases): शेष चरों (variables) को अज्ञात माना जाता है। लेखक चरों को समाप्त करने और बहुपद समीकरणों के निकाय (system of polynomial equations) को कम करने के लिए ग्रोबनर बेसिस (Groebner basis) गणना (Mathematica के माध्यम से) का उपयोग करते हैं। यह समस्या को उच्च-आयामी गैर-रैखिक अनुकूलन से बहुपद समीकरणों के एक निकाय में बदल देता है।
4. सटीक अनुकूलन (Exact Optimization - Discriminant Polynomials): ग्रोथ फैक्टर $g$ के अधिकतम मान को खोजने के लिए, वे $g$ को बहुपद निकाय में एक चर के रूप में मानते हैं। वे शेष चरों के सापेक्ष परिणामी बहुपद के डिस्क्रिमिनेंट (discriminant) की गणना करते हैं। इस डिस्क्रिमिनेन्ट बहुपद के मूल (roots), निकाय के स्थिर बिंदुओं (stationary points/potential maxima) का प्रतिनिधित्व करते हैं।
5. सत्यापन (Verification): वे सत्यापित करते हैं कि विशिष्ट मूल (root) एक वैध, पूरी तरह से पिवोट किए गए आव्यूह के अनुरूप है।

B. इंटरवल अंकगणित और ब्रांच-एंड-बाउंड (ऊपरी सीमा)

ऊपरी सीमा में सुधार करने के लिए, लेखक गणितीय विश्लेषण को कठोर इंटरवल अंकगणित के साथ जोड़ते हैं।

1. विघटन (Decomposition): लेखक $5 \times 5$ ग्रोथ फैक्टर $g(A)$ को तीसरे पिवोट ($p_3$) और परिणामी $3 \times 3$ उप-आव्यूह के ग्रोथ फैक्टर ($g(C)$) के गुणनफल के रूप में विश्लेषित करते हैं।
2. कवरिंग सेट्स (Covering Sets): इंटरवल अंकगणित का उपयोग करते हुए, वे "डायडिक बॉक्स" (हाइपर-रेक्टेंगल) का निर्माण करते हैं जो निश्चित थ्रेसहोल्ड (जैसे, $g(C) \ge 2.15$ और $g(C) \ge 2.2$) के ऊपर ग्रोथ फैक्टर वाले सभी संभावित $3 \times 3$ पूर्णतः पिवोट किए गए आव मैट्रिक्स के स्थान को कवर करते हैं।
3. असंभवता परीक्षण (Infeasibility Test): वे सिद्ध करते हैं कि $5 \times 5$ आव्यूह के लिए $4.84$से अधिक ग्रोथ फैक्टर प्राप्त करने के लिए, मध्यवर्ती$3 \times 3$ आव मैट्रिक्सों को रैंक-2 सन्निकटन (rank-2 approximations) से जुड़ी एक विशिष्ट असमानता को संतुष्ट करना होगा। कवरिंग सेट्स के विरुद्ध इन असमानताओं की जाँच करके, वे प्रदर्शित करते हैं कि ऐसे आव मैट्रिक्स मौजूद नहीं हैं।

3. मुख्य योगदान और परिणाम

A. $n=5$ के लिए सटीक मान

यह शोध पत्र स्थापित करता है कि $4.1325\dots$ का मान, जो संख्यात्मक रूप से देखा गया था, कोई संयोग नहीं है बल्कि एक सटीक बीजगणितीय संख्या है।

• बहुपद: $n=5$ के लिए अधिकतम ग्रोथ फैक्टर पूर्णांक गुणांकों वाले एक 61वें घात के बहुपद, जिसे $P_5(g)$ के रूप में नामित किया गया है, का अंतराल $[4, 5]$ में अद्वितीय वास्तविक मूल है।
• मान:
  $$g \approx 4.13251707863247285422\dots$$
• अनुमान (Conjecture): लेखक अनुमान लगाते हैं कि यह मान $n=5$ के लिए वास्तविक वैश्विक अधिकतम (global maximum) है (अनुमान 2.1)। जबकि संभावित बाधा संरचनाओं का कॉम्बिनेटरियल विस्फोट (combinatorial explosion) पूर्ण वैश्विक इष्टतमता के पूर्ण प्रमाण को रोकता है, वे यह सिद्ध करते हैं कि यह मान विशिष्ट समानता बाधाओं के सेट के दिए गए होने पर अधिकतम है (प्रमेय 2.2)।

B. $n=6, 7, 8$ के लिए परिणाम

लेखक उच्च आयामों के लिए अपनी तकनीक लागू करते हैं:

• $n=6$: अधिकतम ग्रोथ ठीक 5 है।
• $n=7$: अधिकतम ग्रोथ एक 6ठे घात के बहुपद का मूल है, जो लगभग 6.0569 है।
• $n=8$: अधिकतम ग्रोथ 8 है (जो सिल्वेस्टर के हैडामार्ड आव मैट्रिक्स द्वारा भी प्राप्त किया जाता है, लेकिन गैर-हैडामार्ड आव मैट्रिक्स द्वारा भी)।

C. $n=5$ के लिए बेहतर ऊपरी सीमा

यह शोध पत्र $n=5$ के मामले के लिए सैद्धांतिक ऊपरी सीमा को कम करता है:

• पूर्व सीमा: $4\frac{17}{18} \approx 4.944$।
• नई सीमा: 4.84।
• महत्व: यह 50 से अधिक वर्षों में ऊपरी सीमा में पहला सुधार है, जो निचली सीमा (4.1325) और ऊपरी सीमा (4.84) के बीच के अंतर को कम करता है।

4. महत्व

• संख्यात्मक और प्रतीकात्मक का मिलन: यह शोध पत्र एक शक्तिशाली वर्कफ़्लो प्रदर्शित करता है जहाँ संख्यात्मक अनुकूलन सही बीजगणितीय संरचना की खोज का मार्गदर्शन करता है, जिसे बाद में सटीक अंकगणित का उपयोग करके कठोरता से हल किया जाता है। यह फ्लोटिंग-पॉइंट त्रुटियों के खतरों से बचता है और उच्च-आयामी गैर-रैखिक प्रणालियों की जटिलता को प्रबंधित करता है।
• बीजगणितीय जटिलता: यह प्रकट करता है कि संख्यात्मक विश्लेषण की एक क्लासिक समस्या का समाधान आश्चर्यजनक रूप से उच्च डिग्री (61) की एक बीजगणितीय संख्या है, जो इस अंतर्ज्ञान को चुनौती देता है कि ऐसे समस्याओं के सरल परिमेय या निम्न-डिग्री बीजगणितीय समाधान हो सकते हैं।
• कार्यप्रणालीगत प्रगति: ग्रोबनर बेसिस, डिस्क्रिमिनेन्ट पॉलिनोमियल और इंटरवल अंकगणित का संयोजन एक नया टूलकिट प्रदान करता है जिसका उपयोग संख्यात्मक रैखिक बीजगणित में कठिन अनुकूलन समस्याओं को हल करने के लिए किया जा सकता है जो पहले दुर्गम थीं।
• श्रद्धांजलि: यह कार्य निक हाईम को समर्पित है, जो गॉसियन एलिमिनेशन स्थिरता के अध्ययन के अग्रणी हैं, जो ग्रोथ फैक्टर समस्या के स्थायी महत्व को रेखांकित करता है।

ग्रोथ फैक्टर्स की सारांश तालिका ($n=1$ से $8$ तक)

$n$	अधिकतम ग्रोथ फैक्टर	रूप (Form)
1	1	पूर्णांक (Integer)
2	2	पूर्णांक (Integer)
3	2.25	परिमेय (Rational - $9/4$)
4	4	पूर्णांक (Integer)
5	$\approx 4.1325$	61वें घात के बहुपद का मूल
6	5	पूर्णांक (Integer)
7	$\approx 6.057$	6ठे घात के बहुपद का मूल
8	8	पूर्णांक (Integer)

शोध पत्र निष्कर्ष निकालता है कि हालांकि संभावित बाधा विन्यासों (constraint configurations) की विशाल संख्या के कारण $n=5$ के लिए पूर्ण वैश्विक अधिकतम अभी भी एक अनुमान (conjecture) बना हुआ है, लेकिन सटीक बीजगणितीय समाधान और कड़े की गई ऊपरी सीमा से प्राप्त साक्ष्य दृढ़ता से संकेत देते हैं कि 61वें घात के बहुपद का मूल ही वास्तविक उत्तर है।