Algorithmic aspects of Newman polynomials and their divisors

यहाँ एम. इदरीस और जे.-एम. सैक-एपे द्वारा लिखित शोध पत्र "Algorithmic aspects of Newman polynomials and their divisors" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र बीजगणितीय संख्या सिद्धांत (algebraic number theory) के एक मौलिक प्रश्न को संबोधित करता है जो न्यूमैन बहुपदों (Newman polynomials) (जिनके गुणांक $\{0, 1\}$ में होते हैं और स्थिर पद 1 होता है) से संबंधित है। विशेष रूप से, यह इस बात की जांच करता है कि किन परिस्थितियों में एक पूर्णांक-गुणांक वाला बहुपद $p(x)$, एक न्यूमैन बहुपद को विभाजित करता है।

मुख्य जांच यह है कि क्या कोई सार्वभौमिक स्थिरांक (universal constant) $\sigma$ मौजूद है, जिससे कोई भी पूर्णांक बहुपद $p(x)$ जो:

1. में कोई गैर-ऋणात्मक वास्तविक मूल (non-negative real roots) नहीं हैं, और
2. जिसका माहलर माप (Mahler measure) $M(p) < \sigma$ है,
   अनिवार्य रूप से एक न्यूमैन बहुपद को विभाजित करता है।

पिछले कार्यों ने स्थापित किया था कि यदि $M(p) < 2$ है, तो $p(x)$ एक ऐसे बहुपद को विभाजित करता है जिसके गुणांक $\{-1, 0, 1\}$ में होते हैं। हालाँकि, गुणांकों को $\{0, 1\}$ तक सीमित करना एक बहुत अधिक सख्त स्थिति है। जबकि गोल्डन रेशियो ($g \approx 1.618$) को प्रारंभ में एक स्वाभाविक सीमा माना गया था, लगभग 1.556 के माहलर माप वाले प्रति-उदाहरण (counterexamples) पाए गए थे। यह शोध पत्र इस सीमा को परिष्कृत करने और कम माहलर माप वाले बहुपदों के विभाज्यता गुणों को निर्धारित करने का लक्ष्य रखता है।

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

लेखक दो अलग-अलग समस्याओं को हल करने के लिए मिश्रित-पूर्णांक रैखिक प्रोग्रामिंग (Mixed-Integer Linear Programming - MILP) और एल्गोरिद्मिक प्रमाणन (algorithmic certification) के संयोजन का उपयोग करते हैं: न्यूमैन गुणकों की खोज करना और ऐसे गुणकों के अस्तित्व न होने को प्रमाणित करना।

A. न्यूमैन गुणकों की खोज (MILP दृष्टिकोण)

यह निर्धारित करने के लिए कि क्या कोई दिया गया बहुपद $p(x)$ एक न्यूमैन बहुपद को विभाजित करता है, लेखक इसे रैखिक असमानताओं (linear inequalities) की एक प्रणाली के रूप में तैयार करते हैं।

• प्रारूप (Formulation): $2d$ घात वाले एक मोनिक बहुपद $p(x)$ के लिए, वे एक बहुपद $q(x)$ की खोज करते हैं ताकि गुणनफल $N(x) = p(x)q(x)$ के गुणांक $\{0, 1\}$ में हों।
• प्रतिबंध (Constraints): चूंकि $p$ और $q$ के स्थिर पद 1 हैं, इसलिए $N$ का स्थिर पद 1 है। $N(x)$ के गुणांक $q(x)$ के अज्ञात गुणांकों के रैखिक संयोजन होते हैं। यह शर्त कि $N(x)$ के सभी गुणांक 0 या 1 होने चाहिए, पूर्णांक अज्ञातों के साथ रैखिक असमानताओं की एक प्रणाली बनाती है।
• कार्यान्वयन: लेखकों ने इसे Julia में JuMP मॉडलिंग भाषा और Gurobi ऑप्टिमाइज़र का उपयोग करके लागू किया। उन्होंने ऐसे समाधानों की खोज की जहाँ परिणामी न्यूमैन बहुपद की घात 1000 से अधिक नहीं थी।

B. अविभाज्यता का प्रमाणन (Reachability दृष्टिकोण)

यह सिद्ध करने के लिए कि एक बहुपद किसी भी न्यूमैन बहुपद को विभाजित नहीं करता है, लेखक हेयर (Hare) और मॉसिंगहॉफ (Mossinghoff) द्वारा प्रस्तुत एक एल्गोरिद्मिक विधि का उपयोग करते हैं।

• सिद्धांत: मान लीजिए $\beta$ एक संभावित बहुपद का मूल (root) है। वे एक सेट $N'(\beta, d)$ को परिभाषित करते हैं जो एक विशिष्ट डिस्क $I'(\beta)$ पर प्रतिबंधित, घात $\le d$ वाले सभी न्यूमैन बहुपदों के $F(\beta)$ मानों का प्रतिनिधित्व करता है।
• एल्गोरिदम: इस सेट को पुनरावर्ती (recursively) रूप से बनाया जाता है। यदि सेट स्थिर हो जाता है (अर्थात, $N'(\beta, d+1) = N'(\beta, d)$) और इस सेट के भीतर कभी भी $0$प्राप्त नहीं होता है, तो यह प्रमाणित हो जाता है कि$\beta$किसी भी न्यूमैन बहुपद का मूल नहीं है। फलस्वरूप,$\beta$ का न्यूनतम बहुपद (minimal polynomial) किसी भी न्यूमैन बहुपद को विभाजित नहीं करता है।
• कार्यान्वयन: क्रॉस-वेरिफिकेशन सुनिश्चित करने के लिए इसे स्वतंत्र रूप से Julia (Polynomials.jl और Nemo.jl का उपयोग करके) और GP/PARI में लागू किया गया था।

C. पुनरावृत्ति मूलों (Repeated Roots) वाले गुणकों का निर्माण

लेखकों ने $l(x)^2$ द्वारा विभाज्य न्यूमैन बहुपदों को खोजने के लिए MILP दृष्टिकोण को अनुकूलित किया, जहाँ $l(x)$ लेहमर (Lehmer) बहुपद का $x \to -x$ रूपांतरण है।

• विधि: असमानताओं के बजाय, उन्होंने यूक्लिडियन विभाजन शेषफल (Euclidean division remainder) $N(x) = g(x)H(x) + R(x)$ से प्राप्त रैखिक समीकरणों की एक प्रणाली को हल किया। शर्त $g(x) | N(x)$ के लिए $R(x) = 0$ होना आवश्यक है।
• अनुकूलन (Optimization): उन्होंने शेषफल शून्य होने की शर्तों को संतुष्ट करने के लिए बाइनरी गुणांक $a_i \in \{0, 1\}$ के लिए समाधान निकाला।

3. मुख्य परिणाम (Key Results)

A. छोटे माहलर माप वाले बहुपदों की विभाज्यता

लेखकों ने 8,438 ज्ञात बहुपदों के एक डेटासेट का विश्लेषण किया जिनका माहलर माप $< 1.3$ और घात $\le 180$ है (जिसे Known180 कहा जाता है)।

• निष्कर्ष: धनात्मक वास्तविक मूलों वाले बहुपदों को छोड़कर, इस सूची के सभी को छोड़कर तीन बहुपदों को पाया गया कि वे घात $\le 1000$ वाले एक न्यूमैन बहुपद को विभाजित करते हैं।
• प्रमेय (Theorem): प्रत्येक पूर्णांक-गुणांक वाला बहुपद जिसकी घात $\le 44$, माहलर माप $M(p) < 1.3$, कोई गैर-ऋणात्मक वास्तविक मूल नहीं है, और कोई साइक्लोटोमिक कारक (cyclotomic factors) नहीं है, वह एक न्यूमैन बहुपद को विभाजित करता है। यह इस तथ्य पर आधारित है कि Known180 घात 44 तक पूर्ण है।
• अनसुलझे मामले: तीन विशिष्ट बहुपद अनसुलझे रहे (घात 1000 तक कोई न्यूमैन गुणक नहीं मिला), जो यह प्रश्न खुला छोड़ते हैं कि क्या वे उच्च घात वाले न्यूमैन बहुपदों को विभाजित करते हैं।

B. सार्वभौमिक स्थिरांक $\sigma$ में सुधार

प्रमाणन विधि का उपयोग करते हुए, लेखकों ने ऐसे नए बहुपदों की पहचान की जो किसी भी न्यूमैन बहुपद को विभाजित नहीं करते हैं, जिससे काल्पनिक स्थिरांक $\sigma$ के लिए ज्ञात ऊपरी सीमा (upper bound) कम हो गई।

• नई सीमा: उन्होंने एक घात-10 का बहुपद खोजा:
  $$x^{10} - x^8 - x^5 + x + 1$$
  जिसका माहलर माप लगभग 1.419404632 है।
• महत्व: यह पिछले सर्वोत्तम ज्ञात ऊपरी सीमा $\approx 1.4366$ (ड्रंगिलास एट अल., 2023) और $\approx 1.556$ (हेयर और मॉसिंगहॉफ) से बेहतर है। यदि कोई स्थिरांक $\sigma$ मौजूद है, तो वह $\le 1.419404632$ होना चाहिए।
• डेटासेट: शोध पत्र 33 प्रमाणित उदाहरणों (घात 8–12) की एक तालिका प्रदान करता है जिनके माहलर माप $\le 1.556$ हैं और जो न्यूमैन बहुपद को विभाजित नहीं करते हैं।

C. पुनरावृत्ति मूलों वाले न्यूमैन बहुपद

लेखकों ने $l(x)^2$ द्वारा विभाज्य न्यूमैन बहुपदों की जांच की (जहाँ $l(x)$ रूपांतरित लेहमर बहुपद है)।

• परिणाम: उन्होंने घात 150 तक के $l(x)^2$ द्वारा विभाज्य न्यूमैन बहुपदों का स्पष्ट निर्माण किया।
• नकारात्मक परिणाम: उन्होंने सिद्ध किया कि घात $\le 160$ वाला कोई भी न्यूमैन बहुपद $l(x)^3$ द्वारा विभाज्य नहीं है। यह मॉसिंगहॉफ के पिछले सत्यापन (जो घात 120 तक था) का विस्तार है।
• डेटा: शोध पत्र इन बहुपदों को हेक्साडेसिमल प्रारूप में एनकोडेड करके प्रदान करता है।

4. महत्व और योगदान (Significance and Contributions)

1. सीमाओं का परिशोधन: शोध पत्र ने न्यूमैन गुणकों के अस्तित्व के संबंध में सैद्धांतिक सीमाओं को महत्वपूर्ण रूप से कम किया है, जिससे ज्ञात "निषिद्ध" माहलर माप सीमा को $\approx 1.436$ से घटाकर $\approx 1.419$ कर दिया गया है।
2. एल्गोरिद्मिक ढांचा: यह प्रतिबंधित गुणांक वाले बहुपदों से संबंधित संख्यात्मक समस्याओं को हल करने में मिश्रित-पूर्णांक रैखिक प्रोग्रामिंग (MILP) की प्रभावकारिता को प्रदर्शित करता है। यह विधि दर्शाती है कि यह असमानता बाधाओं (गुणक खोजने के लिए) और समानता बाधाओं (शेषफल रद्द करने के लिए) दोनों को संभालने के लिए कितनी लचीली है।
3. व्यापक डेटा: लेखक एक पूर्ण डेटासेट (Known180 विश्लेषण, प्रमाणित गैर-भाजक, और निर्मित गुणक) प्रदान करते हैं, जो GP/PARI में सत्यापन स्क्रिप्ट सहित आगे के अनुसंधान के लिए उपलब्ध है।
4. खुले प्रश्नों का समाधान: यह कार्य पुष्टि करता है कि कम घात वाले ($\le 44$) छोटे माहलर माप वाले बहुपदों के लिए, न्यूमैन बहुपद को विभाजित करने में बाधा लगभग पूरी तरह से धनात्मक वास्तविक मूलों की उपस्थिति है, जिसमें केवल तीन मामूली अपवाद उच्च-घात खोजों के अधीन हैं।

5. निष्कर्ष (Conclusion)

शोध पत्र निष्कर्ष निकालता है कि हालांकि एक सार्वभौमिक स्थिरांक $\sigma$ का अस्तित्व अभी भी एक खुला प्रश्न बना हुआ है, लेकिन प्रति-उदाहरणों के लिए खोज क्षेत्र को काफी हद तक कम कर दिया गया है। लेखक सुझाव देते हैं कि उनका MILP-आधारित ढांचा बोरवेइन (Borwein), लिटिलवुड (Littlewood) और न्यूमैन बहुपदों की भविष्य की जांच के लिए एक शक्तिशाली उपकरण है, जो सीमाओं में और सुधार करने और प्रतिबंधित गुणांकों वाले बहुपदों के नए संरचनात्मक गुणों की खोज करने की क्षमता रखता है।