Isomorphic gcd-graphs over polynomial rings

तकनीकी सारांश: बहुपद वलयों (Polynomial Rings) पर आइसोमोर्फिक GCD-ग्राफ

समस्या विवरण
यह शोध पत्र $F_q[x]$ के ऊपर एक एकदिष्ट बहुपद (monic polynomial) $f$ के मॉड्युलो में परिभाषित GCD-ग्राफ $G_f(D)$ के संरचनात्मक और स्पेक्ट्रल गुणों की जांच करता है। यहाँ एक GCD-ग्राफ $F_q[x]/f$ के योगात्मक समूह (additive group) पर एक केली ग्राफ (Cayley graph) है, जहाँ दो शीर्ष $a, b$ तब आसन्न (adjacent) होते हैं जब $\gcd(a-b, f) \in D$ होता है, जहाँ $D$, $f$ के विभाजकों का एक उपसमुच्चय है (स्वयं $f$ को छोड़कर)।

यह अध्ययन संख्या क्षेत्रों ($\mathbb{Z}$) और फलन क्षेत्रों ($F_q[x]$) के बीच समानता से प्रेरित है। जबकि $\mathbb{Z}$ पर GCD-ग्राफ का व्यापक रूप से अध्ययन किया गया है, विशेष रूप से उनकी पूर्णांकता (integrality) और उन स्थितियों के संबंध में जिनमें वे आइसोमोर्फिक या आइसोस्पेक्ट्रल होते हैं, बहुपद वलयों पर उनका व्यवहार विशिष्ट चुनौतियों और अवसरों को प्रस्तुत करता है। विशेष रूप से, लेखक दो केंद्रीय प्रश्नों को संबोधित करते हैं:

1. सो अनुमान (The So Conjecture): क्या $\mathbb{Z}$ पर एक GCD-ग्राफ $G_n(D)$ सेट $D$ को (आइसोमॉर्फिज्म तक) अद्वितीय रूप से निर्धारित करता है? यह शोध पत्र फलन क्षेत्र सेटिंग में इस अनुमान की समानता की जांच करता है।
2. सैंडर-सैंडर अनुमान (The Sander-Sander Conjecture): क्या सेट $D$ को GCD-ग्राफ के स्पेक्ट्रल वेक्टर (आइगेनवैल्यूज़ की सूची और उनकी बहुलता) द्वारा अद्वितीय रूप से निर्धारित किया जाता है?

कार्यप्रणाली
लेखक बीजगणितीय ग्राफ सिद्धांत (algebraic graph theory), परिमित वलयों (finite rings) के अभिलक्षण सिद्धांत (character theory) और गणनात्मक प्रयोगों के संयोजन का उपयोग करते हैं।

• बीजगणितीय ढांचा: अध्ययन $F_q[x]/f$ के अभिलक्षण सिद्धांत का उपयोग करता है, जो गैर-क्षीण फलनल (non-degenerate functionals) द्वारा निर्धारित होता है, जो $\mathbb{Z}/n\mathbb{Z}$ में प्रिमिटिव रूट्स ऑफ यूनिटी की भूमिका के समान है। यह बहुपद वलयों के लिए अनुकूलित रामानुजन योगों (Ramanujan sums) का उपयोग करके ग्राफ स्पेक्ट्रा का स्पष्ट विवरण प्रदान करने की अनुमति देता है।
• मैट्रिक्स विश्लेषण: $D$ को स्पेक्ट्रम द्वारा दिए गए मान के आधार पर विशिष्टता को संबोधित करने के लिए, लेखक रामानुजन योगों $c(g, h)$ से बना एक मैट्रिक्स $C_f$ निर्मित करते हैं। वे इस मैट्रिक्स के सारणिक (determinant) के गैर-शून्य होने को सिद्ध करते हैं, जिससे इसकी व्युत्क्रमणीयता (invertibility) स्थापित होती है।
• ग्राफ अपघटन (Graph Decomposition): उस स्थिति के लिए जहाँ $f$ एक अभाज्य घात (prime power, $f = P^k$) है, लेखक होमोजेनियस सेट्स और व्रेथ प्रोडक्ट (wreath product/lexicographic product) की अवधारणा का उपयोग करके ग्राफ संरचना का विश्लेषण करते हैं। यह जटिल GCD-ग्राफ को सरल घटकों में अपघटित करने की अनुमति देता है।
• गणनात्मक सत्यापन: लेखक प्रयोगात्मक डेटा को सत्यापित करने, सैद्धांतिक दावों की पुष्टि करने और विभिन्न जनरेटिंग सेट्स के साथ आइसोमोर्फिक ग्राफों के विशिष्ट निर्माणों की खोज करने के लिए पायथन लाइब्रेरी NetworkX का उपयोग करते हैं।

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

1. $D$ का स्पेक्ट्रल निर्धारण (The Sander-Sander Analog):
   यह शोध पत्र सिद्ध करता है कि एक निश्चित $f \in F_q[x]$ के लिए, सेट $D$ को $G_f(D)$ के स्पेक्ट्रल वेक्टर द्वारा अद्वितीय रूप से निर्धारित किया जाता है। यह यह दिखाने से प्राप्त होता है कि रामानुजन योगों का मैट्रिक्स $C_f$ व्युत्क्रमणीय है (प्रपोजिशन 2.4)। फलस्वरूप, फलन क्षेत्र सेटिंग में कमजोर सैंडर-सैंडर अनुमान सत्य सिद्ध होता है: यदि दो GCD-ग्राफ (एक ही आइगेनवैल्यूज़ और बहुलता के साथ) समान स्पेक्ट्रम रखते हैं, तो वे एक ही सेट $D$ द्वारा परिभाषित होते हैं।

2. अभाज्य घातों के लिए ग्राफ-सैद्धांतिक गुण:
   जब $f = P^k$ एक अभाज्य घात होती है, तो लेखक कई संरचनात्मक गुण स्थापित करते हैं:

• कनेक्टिविटी (Connectivity): $G_{P^k}(D)$ संबद्ध (connected) है यदि और केवल यदि $1 \in D$ है।
• बाइपार्टाइटनेस (Bipartiteness): ग्राफ बाइपार्टाइट है यदि और केवल यदि $F_q = F_2$, $\deg(P)=1$, और $D=\{1\}$ है।
• परफेक्टनेस (Perfectness): $G_{P^k}(D)$ एक परफेक्ट ग्राफ है।
• अपघटन (Decomposition): ग्राफ को $D$ में विशिष्ट विभाजकों की उपस्थिति के आधार पर एक सरल ग्राफ के व्रेथ प्रोडक्ट में अपघटित किया जा सकता है।
• स्पेक्ट्रल सीमाएं (Spectral Bounds): लेखक आइगेनवैल्यूज़ के लिए स्पष्ट सूत्र व्युत्पन्न करते हैं और सिद्ध करते हैं कि सबसे बड़ा आइगेनवैल्यू ग्राफ की डिग्री के बराबर होता है। वे यह भी दिखाते हैं कि अभाज्य घात मॉड्युली के लिए, स्पेक्ट्रम ग्राफ की संरचना को अद्वितीय रूप से निर्धारित करता है (थ्योरम 4.16)।

3. GCD-ग्राफ का आइसोमॉर्फिज्म (फलन क्षेत्रों में सो अनुमान का खंडन):
   $\mathbb{Z}$ के मामले के विपरीत, जहाँ यह अनुमान कि आइसोमोर्फिक GCD-ग्राफों में समान जनरेटिंग सेट्स होने चाहिए, खुला रहता है, यह शोध पत्र प्रदर्शित करता है कि $F_q[x]$ पर भिन्न $D$ और संभावित रूप से भिन्न मॉड्युली वाले ग्राफों के बीच गैर-तुच्छ आइसोमॉर्फिज्म मौजूद हैं।

• यूनिटरी केली ग्राफ (Unitary Cayley Graphs): लेखक यूनिटरी केली ग्राफों ($G_f(\{1\})$) के आइसोमॉर्फिज्म वर्गों को $f$ के "फैक्टरइजेशन टाइप" (प्रत्येक डिग्री के अपरिवर्तनीय कारकों की संख्या) के आधार पर वर्गीकृत करते हैं। वे दिखाते हैं कि अलग-अलग रेडिकल्स वाले बहुपदों द्वारा परिभाषित ग्राफ आइसोमोर्फिक हो सकते हैं यदि उनके फैक्टरइजेशन टाइप मेल खाते हों (प्रपोजिशन 5.4)।
• सामान्य GCD-ग्राफ: यह शोध पत्र $G_f(D_1) \cong G_f(D_2)$ जैसे आइसोमोर्फिक GCD-ग्राफों के स्पष्ट निर्माण प्रदान करता है जहाँ $D_1 \neq D_2$ है। ये निर्माण $f$ के भीतर समान डिग्री के भिन्न अपरिवर्तनीय कारकों की उपस्थिति पर निर्भर करते हैं। उदाहरण के लिए, यदि $f = f_1 f_2$ है जहाँ $\deg(f_1) = \deg(f_2)$, तो $D_1$ और $D_2$ के विशिष्ट चयन आइसोमोर्फिक ग्राफ उत्पन्न करते हैं (प्रपोजिशन 5.9, प्रपोजिशन 5.12)।
• अंतर का महत्व: लेखक $\mathbb{Z}$ और $F_q[x]$ के बीच इस तीव्र अंतर का कारण फलन क्षेत्रों में यह तथ्य बताते हैं कि भिन्न-भिन्न बहुपद $f$ और $g$ आइसोमोर्फिक कोटिएंट रिंग्स ($F_q[x]/f \cong F_q[x]/g$) उत्पन्न कर सकते हैं, जो पूर्णांक मामले में असंभव है।

महत्व और दावे
यह शोध पत्र संख्या सिद्धांत और वलय सिद्धांत से जुड़े GCD-ग्राफ के अनुसंधान को आगे बढ़ाने का दावा करता है, एक मजबूत समानता स्थापित करते हुए और महत्वपूर्ण विचलन को रेखांकित करते हुए।

• पुष्टि: यह पुष्टि करता है कि स्पेक्ट्रल वेक्टर फलन क्षेत्र सेटिंग में जनरेटिंग सेट $D$ को निर्धारित करता है, जो सैंडर-सैंडर अनुमान के एनालॉग को मान्य करता है।
• खंडन: यह फलन क्षेत्र सेटिंग ($F_q[x]$) के लिए सो अनुमान के एनालॉग का खंडन करता है, यह प्रदर्शित करते हुए कि भिन्न जनरेटिंग सेट्स वाले आइसोमोर्फिक GCD-ग्राफ इस संदर्भ में "असामान्य नहीं" हैं। शोध पत्र नोट करता है कि यह अनुमान पूर्णांक मामले ($\mathbb{Z}$) के लिए खुला है और यह प्रश्न भी खुला छोड़ता है कि क्या यह अनुमान $F_q[x]$ के प्रतिबंधित परिवार के लिए अभी भी लागू हो सकता है जहाँ मॉडुलस के अपरिवर्तनीय कारकों की डिग्री भिन्न होती है।
• नवीनता: यह शोध पत्र बहुपद वलयों पर GCD-ग्राफ के लिए व्यवस्थित अध्ययन (जैसे परफेक्टनेस, क्लिक नंबर और इंडिपेंडेंस नंबर) प्रदान करता है, यह देखते हुए कि इनमें से कई परिणाम पूर्णांक मामले के लिए भी पहले अनसुलझे थे।

लेखक अपने निष्कर्षों के दायरे के संबंध में एक विनम्र लहजा बनाए रखते हैं, यह उल्लेख करते हुए कि आइसोमोर्फिक ग्राफों के उनके निर्माण विशेष रूप से समान डिग्री के अपरिवर्तनीय कारकों की उपस्थिति पर निर्भर करते हैं। वे इस प्रश्न को खुला छोड़ देते हैं कि क्या सो अनुमान उन GCD-ग्राफों के प्रतिबंधित परिवार के लिए अभी भी लागू हो सकता है जहाँ मॉडुलस के अपरिवर्तनीय कारकों की डिग्री भिन्न होती है।