परस्परांना रद्द करणाऱ्या बेरजांविषयीचे 1969 मधील एक अनुमान चुकीचे ठरले
सहा तासांचे एक घड्याळ घ्या, आणि चालींची एक यादी: “काटा 1 तास पुढे फिरवा”, “4 तास पुढे”, वगैरे. प्रत्येकी एका तासाच्या पाच चालींनी, त्यांचा कोणताही गट काटा नेमका सुरुवातीच्या जागी कधीच परत आणत नाही. सहा चालींनी, त्या कोणत्याही असोत, कोणता ना कोणता गट नेहमीच तसे करतो. गणितज्ञ हे घड्याळ-अंकगणित C₆ असे लिहितात, आणि इथे सहा ही संख्या त्या घड्याळाचा डेव्हनपोर्ट स्थिरांक (Davenport constant) आहे.
आता अशी r घड्याळे शेजारी-शेजारी ठेवा, आणि प्रत्येक चाल प्रत्येक काटा त्याच्या स्वतःच्या प्रमाणात फिरवू द्या. घड्याळांच्या या संचाचा डेव्हनपोर्ट स्थिरांक, D(C₆^r) असा लिहिला जाणारा, म्हणजे चालींची अशी लहानात लहान संख्या जी असा एक गट निश्चितपणे देते ज्याची एकूण बेरीज प्रत्येक काटा एकाच वेळी सुरुवातीच्या जागी परत आणते — शोधनिबंधाच्या शब्दांत, एक शून्य-बेरीज उपक्रम (zero-sum subsequence). हा स्थिरांक आलेख सिद्धांत, सांत भूमिती (finite geometry), संयोजनशास्त्र आणि अवयवीकरण सिद्धांत (factorization theory) यांतील प्रश्नांशी जोडलेला आहे.
1969 मधील एक सूत्र
एक सोपी निम्न सीमा (lower bound) आहे. प्रत्येक घड्याळावर, फक्त त्याच घड्याळाला स्पर्श करणाऱ्या एका तासाच्या पाच चाली घ्या: r घड्याळांसह, त्यातून 5r चाली मिळतात ज्यांपैकी कोणताही गट परस्परांना रद्द करत नाही. म्हणून किमान 5r + 1 चाली आवश्यक आहेत. सर्वसाधारणपणे, n तासांच्या घड्याळांसाठी, किमान r(n − 1) + 1.
1969 मध्ये, व्हॅन एम्डे बोआस आणि क्रॉइसवाइक (van Emde Boas and Kruyswijk) यांनी अनुमान मांडले की ही सोपी सीमा नेहमीच अचूक उत्तर असते:
D(C_n^r) = r(n − 1) + 1.
1960 च्या दशकात काही प्रकरणांसाठी हे सिद्ध झाले, जसे की ज्यांच्या तासांची संख्या एखाद्या मूळ संख्येचा घात (power of a prime) आहे अशी घड्याळे, किंवा जास्तीत जास्त दोन घड्याळे. त्यापलीकडे, अचूक मूल्य आवाक्याबाहेरच राहिले: 2018 पर्यंतसुद्धा, सहा तासांच्या चार घड्याळांचे प्रकरणही अज्ञात होते. तरीही, हे अनुमान या क्षेत्रातील “एक ठळक, दीर्घकाळ प्रलंबित समस्या” बनले, आणि ते खरे ठरेल अशी अपेक्षा होती.
कधीही रद्द न होणाऱ्या 116 चाली
वेइदोंग गाओ (Weidong Gao, तियानजिन विद्यापीठ), आल्फ्रेड गेरोल्डिंगर (Alfred Geroldinger, ग्राझ विद्यापीठ), ग्वोचिंग वांग (Guoqing Wang, तियानगोंग विद्यापीठ) आणि शियांगनेंग झेंग (Xiangneng Zeng, सन यात-सेन विद्यापीठ) आता दाखवतात की हे अनुमान अपयशी ठरते.
चमू या चाली बांधकामाच्या ठोकळ्यांसारख्या जुळवतो:
- सहा तासांच्या पाच घड्याळांवरील 24 चालींची एक यादी, एका लहान तक्त्यापासून बांधलेली: तिच्यातील ज्या कोणत्याही गटाची एकूण बेरीज तीन स्थानांच्या एका लहान संचात येते, तो नेहमी त्यांपैकी एकाच, शून्येतर स्थानावर पोहोचतो;
- अशा दोन याद्या ज्या ती तीन स्थाने सामायिक करतात, ज्यातून 48 चाली मिळतात, ज्यांचा कोणताही गट परस्परांना रद्द करत नाही;
- 20 चालींची एक स्वतंत्र यादी, जिच्यातीलही कोणताही गट परस्परांना रद्द करत नाही.
शेजारी-शेजारी ठेवल्यावर, यांतून सहा तासांच्या 23 घड्याळांवर 2 × 48 + 20 = 116 चाली मिळतात, आणि त्यांचा कोणताही गट प्रत्येक काटा सुरुवातीच्या जागी परत आणत नाही. अनुमानानुसार 23 × 5 = 115 ही अशी सर्वांत लांब शक्य यादी होती. म्हणून 23 घड्याळांसाठी डेव्हनपोर्ट स्थिरांक 116 नव्हे, तर किमान 117 आहे.
या खंडाच्या प्रती एकावर एक रचता येतात: सर्वसाधारण निष्कर्ष असा की D(C₆^r) ≥ 5r + ⌊r/23⌋ + 1, जिथे ⌊r/23⌋ हे r मध्ये 23 चे किती पूर्ण खंड मावतात ते मोजते. म्हणून सहा तासांच्या घड्याळांसाठी अनुमान r 23 पर्यंत पोहोचताच चुकीचे ठरते, आणि त्याहून मोठ्या प्रत्येक r साठीही. लेखक नमूद करतात की हेच प्रमेय आच्छादनांविषयीचा (coverings) एक अनुमानित निष्कर्षही खोडून काढते.
काय अजून खुले आहे
सिद्धता D(C₆^r) चे खरे मूल्य देत नाही, फक्त अनुमानाला अमान्य असलेली एक सीमा देते. 23 पेक्षा कमी घड्याळांसाठी, जिथे नवी सीमा जुन्या सूत्राइतकीच येते, किंवा सहा सोडून इतर तासांच्या संख्येच्या घड्याळांसाठी ती काहीही नवे सांगत नाही. टिपण पाच पानांचे आहे, आणि समकक्ष समीक्षण अजून व्हायचे आहे.
