वर्ग-मुक्त पूर्णांक

From Vigyanwiki
10 वर्ग-मुक्त है, क्योंकि इसके 1 से बड़े भाजक 2, 5 और 10 हैं, जिनमें से कोई भी वर्ग नहीं है (पहले कुछ वर्ग 1, 4, 9 और 16 हैं)
√120 तक अभाज्य संख्याओं के वर्गों के गुणजों को हटाने के बाद 120 तक के वर्ग-मुक्त पूर्णांक शेष रह जाते हैं

गणित में, एक वर्ग-मुक्त पूर्णांक (या वर्गमुक्त पूर्णांक) पूर्णांक होता है जो 1 के अलावा किसी भी वर्ग संख्या से विभाज्य नहीं होता है। यानी, इसके अभाज्य गुणनखंड में इसमें दिखाई देने वाले प्रत्येक अभाज्य के लिए बिल्कुल एक कारक होता है। उदाहरण के लिए, 10 = 2 ⋅ 5 वर्ग-मुक्त है, लेकिन 18 = 2 ⋅ 3 ⋅ 3 नहीं है, क्योंकि 18, 9 = 32 से विभाज्य है। सबसे छोटी धनात्मक वर्ग-मुक्त संख्याएँ हैं

1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 33, 34, 35, 37, 38, 39, ...(ओईआईएस में अनुक्रम A005117)

वर्ग-मुक्त गुणनखंडन

प्रत्येक धनात्मक पूर्णांक को एक अद्वितीय विधि से गुणनखंडित किया जा सकता है


जहां एक से भिन्न वर्ग-मुक्त पूर्णांक होते हैं जो युग्‍मानूसार सहअभाज्य होते हैं। इसे n का वर्ग-मुक्त गुणनखंडन कहा जाता है।

वर्ग-मुक्त गुणनखण्ड बनाने के लिए, आइए

का अभाज्य गुणनखंडन हो, जहां विशिष्ट अभाज्य संख्याएँ हैं। फिर वर्ग-मुक्त गुणनखंड के गुणनखंडों को इस प्रकार परिभाषित किया जाता है
पूर्णांक वर्ग-मुक्त होता है यदि और केवल यदि सभी के लिए हो। एक से बड़ा पूर्णांक दूसरे पूर्णांक की घात है यदि और केवल यदि सभी i का भाजक है जैसे कि

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

पूर्णांकों के वर्ग-मुक्त गुणनखंड

किसी पूर्णांक का मूलांक उसका सबसे बड़ा वर्ग-मुक्त गुणनखंड होता है, अर्थात पूर्ववर्ती खंड के अंकन के साथ। पूर्णांक वर्ग-मुक्त होता है यदि और केवल तभी जब वह उसके मूलांक के बराबर हो।

प्रत्येक धनात्मक पूर्णांक को अद्वितीय विधि से एक घातीय संख्या के गुणन के रूप में दर्शाया जा सकता है (यह एक ऐसा पूर्णांक है जो प्रत्येक अभाज्य गुणनखंड के वर्ग से विभाज्य है) और वर्ग-मुक्त पूर्णांक, जो सहअभाज्य हैं। इस गुणनखंड में, वर्ग-मुक्त गुणनखंड है और घातीय संख्या है।

का वर्ग-मुक्त भाग है, जो सबसे बड़ा वर्ग-मुक्त भाजक है का , जो कि के साथ सहअभाज्य है। किसी पूर्णांक का वर्ग-मुक्त भाग सबसे बड़े वर्ग-मुक्त विभाजक से अल्प हो सकता है, जो कि है।

किसी भी याच्छिक रूप से धनात्मक पूर्णांक को एक वर्ग और वर्ग-मुक्त पूर्णांक के गुणनफल के रूप में अद्वितीय विधि से दर्शाया जा सकता है:


इस गुणनखंडन में, , का सबसे बड़ा भाजक है, इस प्रकार कि , का भाजक है।

संक्षेप में, तीन वर्ग-मुक्त कारक हैं जो स्वाभाविक रूप से हर पूर्णांक के साथ जुड़े होते हैं: वर्ग-मुक्त भाग, उपरोक्त कारक , और सबसे बड़ा वर्ग-मुक्त कारक। प्रत्येक अगले का एक गुणनखंड है। सभी को अभाज्य गुणनखंडन या वर्ग-मुक्त गुणनखंडन से आसानी से घटाया जाता है। यदि

का अभाज्य गुणनखंडन और वर्ग-मुक्त गुणनखंडन हैं, जहां अलग-अलग अभाज्य संख्याएं हैं, तो वर्ग-मुक्त भाग है।

वर्ग-मुक्त कारक जैसे भागफल एक वर्ग है

और सबसे बड़ा वर्ग-मुक्त गुणनखंड है
उदाहरण के लिए, यदि तो 1 के पास है। वर्ग-रहित भाग 7 है, वर्ग-मुक्त गुणनखंड ऐसा है कि भागफल एक वर्ग है 3 ⋅ 7 = 21 है, और सबसे बड़ा वर्ग-मुक्त गुणनखंड 2 ⋅ 3 ⋅ 5 ⋅ 7 = 210 है।

इनमें से किसी भी वर्ग-मुक्त कारक की गणना करने के लिए कोई एल्गोरिथ्म ज्ञात नहीं है जो पूर्ण अभाज्य गुणनखंड की गणना करने से तेज़ हो। विशेष रूप से, किसी पूर्णांक के वर्ग-मुक्त भाग की गणना करने के लिए, या यहां तक कि यह निर्धारित करने के लिए कि कोई पूर्णांक वर्ग-मुक्त है या नहीं, कोई ज्ञात बहुपद-समय एल्गोरिथ्म नहीं है।[1] इसके विपरीत, बहुपद-समय एल्गोरिदम को प्रारंभिक परीक्षण के लिए जाना जाता है।[2] यह पूर्णांकों के अंकगणित और अविभाज्य बहुपदों के अंकगणित के बीच एक बड़ा अंतर है, क्योंकि बहुपद-समय एल्गोरिदम को बहुपदों के वर्ग-मुक्त गुणनखंडन के लिए जाना जाता है (संक्षेप में, एक बहुपद का सबसे बड़ा वर्ग-मुक्त गुणनखंड इसका भागफल है) बहुपद और उसके औपचारिक व्युत्पन्न के सबसे बड़े सामान्य विभाजक द्वारा)।[3]

समतुल्य लक्षण

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

धनात्मक पूर्णांक वर्ग-मुक्त होता है यदि और केवल यदि क्रम के सभी एबेलियन समूह आइसोमोर्फिक हों, जो कि मामला है यदि और केवल यदि ऐसा कोई समूह चक्रीय है। यह अंतिम रूप से उत्पन्न एबेलियन समूहों के वर्गीकरण से आता है।

पूर्णांक वर्ग-मुक्त है यदि और केवल तभी जब कारक वलय (मॉड्यूलर अंकगणित देखें) विस्तार का गुणनफल है। यह चीनी शेषफल प्रमेय और इस तथ्य से अनुसरण करता है कि के रूप की वलय विस्तार है यदि और केवल यदि अभाज्य है।

प्रत्येक धनात्मक पूर्णांक के लिए , के सभी धनात्मक विभाजकों का समुच्चय यदि हम भाजक को क्रम संबंध के रूप में उपयोग करते हैं तो आंशिक रूप से क्रमित समुच्चय बन जाता है। आंशिक रूप से ऑर्डर किया गया यह समुच्चय हमेशा एक वितरणात्मक जाली होता है। यह एक बूलियन बीजगणित (संरचना) है यदि और केवल यदि वर्ग-मुक्त है।

धनात्मक पूर्णांक वर्ग-मुक्त है यदि और केवल यदि , जहाँ मोबियस फलन को दर्शाता है।

डिरिचलेट श्रृंखला

मोबियस फ़ंक्शन का निरपेक्ष मान वर्ग-मुक्त पूर्णांकों के लिए संकेतक फ़ंक्शन है अर्थात्, |μ(n)| यदि n वर्ग-मुक्त है, तो 1 के बराबर है, और यदि नहीं है, तो 0 के बराबर है। इस सूचक फलन की डिरिचलेट श्रृंखला है।

जहाँ ζ(s) रीमैन ज़ेटा फलन है। यह यूलर गुणनफल से अनुसरण करता है।

जहां गुणनफलों को अभाज्य संख्याओं पर लिया जाता है।

वितरण

मान लें कि Q(x) 1 और x के बीच वर्ग-मुक्त पूर्णांकों की संख्या को दर्शाता है (ओईआईएस: A013928 सूचकांक को 1 से स्थानांतरित करता है)। बड़े n के लिए, n से कम 3/4 धनात्मक पूर्णांक 4 से विभाज्य नहीं हैं, इनमें से 8/9 संख्याएँ 9 से विभाज्य नहीं हैं, इत्यादि। क्योंकि ये अनुपात गुणक फलन को संतुष्ट करते हैं (यह चीनी शेषफल प्रमेय से अनुसरण करता है), हम सन्निकटन प्राप्त करते हैं:

अनुमान प्राप्त करने के लिए इस तर्क को अपूर्ण बनाया जा सकता है (बड़े O अंकन का उपयोग करके)

प्रमाण का रेखाचित्र: ऊपर दिया गया लक्षण वर्णन देता है।

यह देखते हुए कि अंतिम सारांश शून्य है , इसका परिणाम यह होता है।

रीमैन ज़ेटा फ़ंक्शन के सबसे बड़े ज्ञात शून्य-मुक्त क्षेत्र का उपयोग करके अर्नोल्ड वालफिज़ द्वारा सन्निकटन में सुधार किया गया था।[4]

कुछ धनात्मक स्थिरांक c के लिए।

रीमैन परिकल्पना के तहत, त्रुटि शब्द को कम किया जा सकता है।[5]

हाल ही में (2015) त्रुटि शब्द को और भी कम कर दिया गया है।[6]

इसलिए वर्ग-मुक्त संख्याओं का स्पर्शोन्मुख / प्राकृतिक घनत्व है।

इसलिए 3/5 से अधिक पूर्णांक वर्ग-मुक्त हैं।

इसी तरह, यदि Q(x,n) 1 और x के बीच n-मुक्त पूर्णांकों की संख्या को दर्शाता है (उदाहरण के लिए 3-मुक्त पूर्णांक घन-मुक्त पूर्णांक हैं), तो कोई प्रदर्शित कर सकता है: [7]

चूँकि 4 के गुणज का वर्ग गुणनखंड 4=22 होना चाहिए, इसलिए ऐसा नहीं हो सकता कि चार लगातार पूर्णांक सभी वर्ग-मुक्त हों। दूसरी ओर, अनंत संख्या में पूर्णांक n उपस्थित हैं जिनके लिए 4n +1, 4n +2, 4n +3 सभी वर्ग-मुक्त हैं। अन्यथा, यह देखते हुए कि 4n और 4n +1, 4n +2, 4n +3 में से कम से कम एक चार पर्याप्त रूप से बड़े n के लिए गैर-वर्ग-मुक्त हो सकते हैं, सभी धनात्मक पूर्णांकों का आधा भाग घटाकर परिमित पूर्णांकों को गैर-वर्ग-मुक्त होना चाहिए और इसलिए:

कुछ स्थिरांक C के लिए,

उपरोक्त स्पर्शोन्मुख अनुमान के विपरीत .

एकपक्षीय लंबाई के लगातार गैर-वर्ग-मुक्त पूर्णांकों के अनुक्रम उपस्थित हैं। वास्तव में, यदि n एक समकालिक सर्वांगसमता को संतुष्ट करता है।

अलग-अलग अभाज्य संख्याओं के लिए , फिर प्रत्येक pi 2 से विभाज्य है।[8] दूसरी ओर, उपर्युक्त अनुमान का तात्पर्य यह है कि, कुछ स्थिरांक c के लिए, x और धनात्मक x के लिए के बीच हमेशा एक वर्ग-मुक्त पूर्णांक उपस्थित होता है। इसके अलावा, एक प्राथमिक तर्क हमें को [9] से प्रतिस्थापित करने की अनुमति देता है। ABC अनुमान की अनुमति देगा।

Q(x) की तालिका, 6/π2x, और R(x)

तालिका दिखाती है कि कैसे और 10 की घात पर तुलना करें।

, के रूप में भी दर्शाया गया है ।

10 7 6.1 0.9
102 61 60.8 0.2
103 608 607.9 0.1
104 6,083 6,079.3 3.7
105 60,794 60,792.7 1.3
106 607,926 607,927.1 - 1.3
107 6,079,291 6,079,271.0 20.0
108 60,792,694 60,792,710.2 - 16.2
109 607,927,124 607,927,101.9 22.1
1010 6,079,270,942 6,079,271,018.5 - 76.5
1011 60,792,710,280 60,792,710,185.4 94.6
1012 607,927,102,274 607,927,101,854.0 420.0
1013 6,079,271,018,294 6,079,271,018,540.3 - 246.3
1014 60,792,710,185,947 60,792,710,185,402.7 544.3
1015 607,927,101,854,103 607,927,101,854,027.0 76.0

जैसे-जैसे अनंत की ओर बढ़ता है, अपना चिह्न अनंत बार बदलता है।[10]

का निरपेक्ष मान की तुलना में आश्चर्यजनक रूप से अल्प है।

बाइनरी संख्याओं के रूप में एन्कोडिंग

यदि हम एक वर्ग-मुक्त संख्या को अनंत गुणनफल के रूप में निरूपित करते हैं

तो हम उन्हें ले सकते हैं और उन्हें एन्कोडिंग के साथ बाइनरी संख्या में बिट्स के रूप में उपयोग करें

वर्ग-मुक्त संख्या 42 में गुणनखंडन है 2 × 3 × 7, या अनंत गुणनफल के रूप में 21 · 31 · 50 · 71 · 110 · 130 ··· इस प्रकार संख्या 42 को बाइनरी अनुक्रम के रूप में एन्कोड किया जा सकता है ...001011 या 11 दशमलव. (बाइनरी अंक अनंत गुणनफल में क्रम से व्युत्क्रम होते हैं।)

चूंकि प्रत्येक संख्या का अभाज्य गुणनखंडन अद्वितीय है, इसलिए वर्ग-मुक्त पूर्णांकों का प्रत्येक बाइनरी एन्कोडिंग भी अद्वितीय है।

इसका विपरीत भी सत्य है। चूँकि प्रत्येक धनात्मक पूर्णांक में अद्वितीय द्विआधारी प्रतिनिधित्व होता है, इसलिए इस एन्कोडिंग को उलटना संभव है ताकि उन्हें अद्वितीय वर्ग-मुक्त पूर्णांक में डिकोड किया जा सके।

पुनः, उदाहरण के लिए, यदि हम संख्या 42 से प्रारम्भ करते हैं, इस बार केवल धनात्मक पूर्णांक के रूप में, तो हमारे पास इसका द्विआधारी प्रतिनिधित्व 101010 है। यह 20 · 31 · 50 · 71 · 110 · 131 = 3 × 7 × 13 = 273. है।

इस प्रकार वर्गमुक्त संख्याओं की द्विआधारी एन्कोडिंग गैर-ऋणात्मक पूर्णांकों और धनात्मक वर्गमुक्त पूर्णांकों के सेट के बीच आक्षेप का वर्णन करती है।

(पूर्णांक अनुक्रमों के ऑन-लाइन विश्वकोश में अनुक्रम OEIS:A019565, OEIS:A048672 और OEIS:A064273 देखें।)

एर्डो का वर्गमुक्त अनुमान

केंद्रीय द्विपद गुणांक

n > 4 के लिए कभी भी वर्गमुक्त नहीं होता है। इसे 1985 में एंड्रास सरकोज़ी द्वारा सभी पर्याप्त बड़े पूर्णांकों के लिए सिद्ध किया गया था,[11] और सभी पूर्णांकों > 4 के लिए 1996 में ओलिवियर रामरे और एंड्रयू ग्रानविले द्वारा सिद्ध किया गया था।[12]

वर्गा मुक्त कोर

आइए हम "t-free" को धनात्मक पूर्णांक कहें जिसके विभाजक में कोई t घात न हो। विशेष रूप से, 2-मुक्त पूर्णांक वर्ग-मुक्त पूर्णांक हैं।

गुणक फलन प्रत्येक धनात्मक पूर्णांक n को उसके सबसे बड़े भाजक द्वारा n के भागफल में मैप करता है जो कि t घात है। वह है,

पूर्णांक t-free है, और प्रत्येक टी-मुक्त पूर्णांक को फलन द्वारा स्वयं मैप किया जाता है।

अनुक्रम का डिरिचलेट जनरेटिंग फलन है।

.

यह भी देखें

OEISA007913 (t=2), OEISA050985 (t=3) और OEISA053165 ((t=4)

टिप्पणियाँ

  1. Adleman, Leonard M.; McCurley, Kevin S. (1994). "Open problems in number theoretic complexity, II". In Adleman, Leonard M.; Huang, Ming-Deh A. (eds.). Algorithmic Number Theory, First International Symposium, ANTS-I, Ithaca, NY, USA, May 6–9, 1994, Proceedings. Lecture Notes in Computer Science. Vol. 877. Springer. pp. 291–322. doi:10.1007/3-540-58691-1_70.
  2. Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (1 September 2004). "PRIMES P में है" (PDF). Annals of Mathematics (in English). 160 (2): 781–793. doi:10.4007/annals.2004.160.781. ISSN 0003-486X. MR 2123939. Zbl 1071.11070.
  3. Richards, Chelsea (2009). परिमित क्षेत्रों पर वर्ग-मुक्त बहुपदों के गुणनखंडन के लिए एल्गोरिदम (PDF) (Master's thesis). Canada: Simon Fraser University.
  4. Walfisz, A. (1963). आधुनिक संख्या सिद्धांत में वेइल का घातीय योग. Berlin: VEB Deutscher Verlag der Wissenschaften.
  5. Jia, Chao Hua. "The distribution of square-free numbers", Science in China Series A: Mathematics 36:2 (1993), pp. 154–169. Cited in Pappalardi 2003, A Survey on k-freeness; also see Kaneenika Sinha, "Average orders of certain arithmetical functions", Journal of the Ramanujan Mathematical Society 21:3 (2006), pp. 267–277.
  6. Liu, H.-Q. (2016). "वर्गमुक्त संख्याओं के वितरण पर". Journal of Number Theory. 159: 202–222. doi:10.1016/j.jnt.2015.07.013.
  7. Linfoot, E. H.; Evelyn, C. J. A. (1929). "संख्याओं के योगात्मक सिद्धांत में एक समस्या पर". Mathematische Zeitschrift. 30: 443–448. doi:10.1007/BF01187781. S2CID 120604049.
  8. Parent, D. P. (1984). संख्या सिद्धांत में अभ्यास. Problem Books in Mathematics. Springer-Verlag New York. doi:10.1007/978-1-4757-5194-9. ISBN 978-1-4757-5194-9.
  9. Filaseta, Michael; Trifonov, Ognian (1992). "On gaps between squarefree numbers. II". Journal of the London Mathematical Society. Second Series. 45 (2): 215–221. doi:10.1112/jlms/s2-45.2.215. MR 1171549.
  10. Minoru, Tanaka (1979). "वर्गमुक्त संख्याओं के वितरण से संबंधित प्रयोग". Proceedings of the Japan Academy, Series A, Mathematical Sciences. 55 (3). doi:10.3792/pjaa.55.101. S2CID 121862978.
  11. Sárközy, A. (1985). "On divisors of binomial coefficients. I". Journal of Number Theory. 20 (1): 70–80. doi:10.1016/0022-314X(85)90017-4. MR 0777971.
  12. Ramaré, Olivier; Granville, Andrew (1996). "Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients". Mathematika. 43 (1): 73–107. doi:10.1112/S0025579300011608.

संदर्भ