2025-11-16T20:37:12.974994

Low complexity binary words avoiding $(5/2)^+$-powers

Currie, Rampersad
Rote words are infinite words that contain $2n$ factors of length $n$ for every $n \geq 1$. Shallit and Shur, as well as Ollinger and Shallit, showed that there are Rote words that avoid $(5/2)^+$-powers and that this is best possible. In this note we give a structure theorem for the Rote words that avoid $(5/2)^+$-powers, confirming a conjecture of Ollinger and Shallit.
academic

कम जटिलता वाले बाइनरी शब्द (5/2)+(5/2)^+-शक्तियों से बचते हुए

मूल जानकारी

  • पेपर ID: 2506.19050
  • शीर्षक: Low complexity binary words avoiding (5/2)+(5/2)^+-powers
  • लेखक: James Currie, Narad Rampersad
  • वर्गीकरण: math.CO (संयोजक गणित), cs.FL (औपचारिक भाषा)
  • प्रकाशन समय: 13 अक्टूबर 2025 (arXiv प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2506.19050

सारांश

Rote अनुक्रम अनंत अनुक्रम हैं जो प्रत्येक n≥1n \geq 1 के लिए लंबाई nn के बिल्कुल 2n2n कारकों को शामिल करते हैं। Shallit और Shur तथा Ollinger और Shallit ने प्रमाणित किया कि (5/2)+(5/2)^+-शक्तियों से बचने वाले Rote अनुक्रम मौजूद हैं, और यह इष्टतम है। यह पेपर (5/2)+(5/2)^+-शक्तियों से बचने वाले Rote अनुक्रमों का एक संरचनात्मक प्रमेय प्रदान करता है, जो Ollinger और Shallit के एक अनुमान की पुष्टि करता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

मूल समस्या

यह अनुसंधान संयोजक शब्द सिद्धांत में दो मूल अवधारणाओं पर केंद्रित है: शक्ति-परिहार और कारक जटिलता। विशेष रूप से, समस्या यह है कि सभी (5/2)+(5/2)^+-शक्तियों से बचने वाले और न्यूनतम जटिलता (2n2n) वाले बाइनरी अनंत अनुक्रमों की संरचना को चिन्हित करना।

समस्या की महत्ता

  1. सैद्धांतिक महत्व: शक्ति-परिहार और कारक जटिलता संयोजक शब्द सिद्धांत की मौलिक अवधारणाएं हैं, और उनका पारस्परिक संबंध इस क्षेत्र की मूल अनुसंधान दिशा है
  2. संरचनात्मक सिद्धांत: Restivo-Salemi के अतिव्यापन-मुक्त अनुक्रमों पर शास्त्रीय संरचनात्मक प्रमेय के समान, यह अनुसंधान एक नया संरचनात्मक प्रमेय स्थापित करता है
  3. अनुमान सत्यापन: Ollinger और Shallit द्वारा प्रस्तावित Rote अनुक्रमों की संरचना के बारे में महत्वपूर्ण अनुमान की पुष्टि करता है

मौजूदा अनुसंधान की सीमाएं

  • Shallit और Shur तथा Ollinger और Shallit ने हालांकि (5/2)+(5/2)^+-शक्तियों से बचने वाले Rote अनुक्रमों के अस्तित्व और इष्टतमता को प्रमाणित किया, लेकिन संपूर्ण संरचनात्मक चिन्हन की कमी है
  • मौजूदा कार्य केवल ठोस निर्माण उदाहरण देते हैं, सामान्य संरचनात्मक प्रमेय नहीं

अनुसंधान प्रेरणा

एक संपूर्ण संरचनात्मक प्रमेय स्थापित करना, जैसे Restivo-Salemi प्रमेय अतिव्यापन-मुक्त बाइनरी अनुक्रमों के लिए, कम जटिलता वाले अनुक्रमों की शक्ति-परिहार गुणों को समझने के लिए सैद्धांतिक आधार प्रदान करना।

मूल योगदान

  1. उचित और अनुचित अनुक्रमों की अवधारणा प्रस्तुत की: त्रिगुण अनुक्रमों के दो महत्वपूर्ण उप-वर्गों को परिभाषित किया
  2. पहला संरचनात्मक प्रमेय स्थापित किया: उचित और अनुचित अनुक्रमों की पुनरावर्ती संरचना को चिन्हित किया
  3. दूसरा संरचनात्मक प्रमेय प्रमाणित किया: (5/2)+(5/2)^+-शक्तियों से बचने वाले Rote अनुक्रमों की संरचना को पूरी तरह से चिन्हित किया
  4. Ollinger-Shallit अनुमान सत्यापित किया: रूपांतरण ff और gg से संबंधित संपूर्ण संरचनात्मक चिन्हन प्रदान किया
  5. कम्प्यूटेशनल सत्यापन प्रदान किया: बैकट्रैकिंग खोज के माध्यम से मुख्य लेम्मा की सत्यता सत्यापित की

विधि विवरण

कार्य परिभाषा

इनपुट: बाइनरी अनंत अनुक्रम wwबाधा शर्तें:

  1. ww एक Rote अनुक्रम है (कारक जटिलता 2n2n है)
  2. ww (5/2)+(5/2)^+-शक्तियों से बचता है

आउटपुट: ww की संरचनात्मक चिन्हन, अर्थात् ww को उचित या अनुचित अनुक्रमों पर कार्य करने वाले विशिष्ट रूपांतरणों के रूप में प्रदर्शित किया जा सकता है

मुख्य परिभाषाएं

उचित और अनुचित अनुक्रम

त्रिगुण अनुक्रम u∈Σ3∗u \in \Sigma_3^* के लिए, Parikh वेक्टर π(u)=[∣u∣0,∣u∣1,∣u∣2]\pi(u) = [|u|_0, |u|_1, |u|_2] को परिभाषित करें।

उचित अनुक्रम निम्नलिखित को संतुष्ट करते हैं:

  1. कारक xyxyxxyxyx नहीं रखते, जहां π(x)>π(y)\pi(x) > \pi(y)
  2. कारक नहीं रखते: 00,11,22,20,10101,2121,1021021000, 11, 22, 20, 10101, 2121, 10210210

अनुचित अनुक्रम: जिनका विपरीत क्रम उचित अनुक्रम है

मुख्य रूपांतरण

रूपांतरण f:Σ3∗→Σ3∗f: \Sigma_3^* \to \Sigma_3^* और h:Σ3∗→Σ3∗h: \Sigma_3^* \to \Sigma_3^* को परिभाषित करें:

  • f(0)=0121f(0) = 0121, f(1)=021f(1) = 021, f(2)=01f(2) = 01
  • h(0)=1210h(0) = 1210, h(1)=120h(1) = 120, h(2)=10h(2) = 10

रूपांतरण g:Σ3∗→Σ2∗g: \Sigma_3^* \to \Sigma_2^* को परिभाषित करें:

  • g(0)=011g(0) = 011, g(1)=0g(1) = 0, g(2)=01g(2) = 01

मूल तकनीकी विधि

1. कारक विश्लेषण विधि

(5/2)+(5/2)^+-शक्तियों से बचने वाले बाइनरी अनुक्रमों द्वारा शामिल किए जाने वाले लंबाई 4 के कारकों का विस्तृत विश्लेषण करके, इस वर्ग के अनुक्रमों की मौलिक संरचनात्मक बाधाओं को निर्धारित किया।

मुख्य लेम्मा:

  • लेम्मा 1: कोई भी (5/2)+(5/2)^+-शक्तियों से बचने वाला अनंत बाइनरी अनुक्रम कारक 01100110 और 10011001 को शामिल करना चाहिए
  • लेम्मा 3: कारक जटिलता ≤2n\leq 2n वाले और (5/2)+(5/2)^+-शक्तियों से बचने वाले अनुक्रमों को कारक 00110011 और 11001100 को शामिल करना चाहिए

2. बैकट्रैकिंग खोज सत्यापन

मुख्य लेम्मा को सत्यापित करने के लिए कंप्यूटर प्रोग्राम का उपयोग करके, रचनात्मक प्रमाण के माध्यम से बाधा शर्तों की आवश्यकता को निर्धारित किया।

3. पुनरावर्ती संरचना विश्लेषण

प्रमाणित किया कि उचित और अनुचित अनुक्रमों में स्व-समान पुनरावर्ती संरचना है, जिसे रूपांतरण ff और hh के माध्यम से चिन्हित किया जा सकता है।

प्रायोगिक सेटअप

कम्प्यूटेशनल सत्यापन विधि

पेपर ने मुख्य लेम्मा को सत्यापित करने के लिए Python में बैकट्रैकिंग खोज एल्गोरिदम लागू किया:

def fhpf(w): # जांचें कि क्या अनुक्रम w 5/2+ शक्तियों से बचता है
    p=1
    while (5*p<2*len(w)):
        if (w[(-(p+1)//2)-p:]==w[(-(p+1)//2)-2*p:-p]):
            return(False)
        p=p+1
    return(True)

सत्यापन सामग्री

  1. लेम्मा 1 सत्यापन: 01100110 न रखने वाले और (5/2)+(5/2)^+-शक्तियों से बचने वाले सबसे लंबे अनुक्रम की लंबाई 14 है
  2. लेम्मा 2 सत्यापन: समुच्चय C={0010,0100,1011,1101}C = \{0010, 0100, 1011, 1101\} में कम से कम 3 तत्वों के दिखाई देने की पुष्टि की
  3. लेम्मा 3 सत्यापन: समुच्चय AA में प्रत्येक तत्व का विस्तृत सत्यापन किया
  4. लेम्मा 4 सत्यापन: 17 लंबाई-9 विशिष्ट अनुक्रमों की बाधा शर्तों की पुष्टि की

प्रायोगिक परिणाम

मुख्य परिणाम

प्रमेय 1 (पहला संरचनात्मक प्रमेय)

  1. उचित अनुक्रम u∈Σ3ωu \in \Sigma_3^{\omega} के लिए, इसका कुछ प्रत्यय f(v)f(v) का रूप है, जहां vv एक उचित अनुक्रम है
  2. अनुचित अनुक्रम u∈Σ3ωu \in \Sigma_3^{\omega} के लिए, इसका कुछ प्रत्यय h(v)h(v) का रूप है, जहां vv एक अनुचित अनुक्रम है

प्रमेय 2 (दूसरा संरचनात्मक प्रमेय)

(5/2)+(5/2)^+-शक्तियों से बचने वाले Rote अनुक्रम ww के चार मामले हैं, जिनके लंबाई-4 कारक समुच्चय क्रमशः हैं:

  1. F={0110,1001,0011,1100,0010,0100,1101,1010}F = \{0110, 1001, 0011, 1100, 0010, 0100, 1101, 1010\}
  2. Fˉ\bar{F} (FF का पूरक)
  3. FRF^R (FF का विपरीत क्रम)
  4. FR‾\overline{F^R} (FF विपरीत क्रम का पूरक)

प्रत्येक मामले में, ww का कुछ प्रत्यय g(fn(u))g(f^n(u)) या g(hn(u))g(h^n(u)) का रूप है, जहां uu एक उचित अनुक्रम है।

कम्प्यूटेशनल सत्यापन परिणाम

  • 01100110 न रखने वाले सबसे लंबे (5/2)+(5/2)^+-शक्ति-परिहार अनुक्रम: लंबाई 14
  • CC में दो तत्वों को न रखने वाले सबसे लंबे अनुक्रम: लंबाई 44
  • 00110011 और AA में किसी तत्व को न रखने वाले सबसे लंबे अनुक्रम: लंबाई 31
  • विभिन्न बाधा शर्तों के तहत सबसे लंबे अनुक्रमों की लंबाई सभी अपेक्षित सीमा में हैं

संबंधित कार्य

शास्त्रीय परिणाम

  1. Restivo-Salemi प्रमेय: अतिव्यापन-मुक्त बाइनरी अनुक्रमों की संरचना को चिन्हित करता है, Thue-Morse रूपांतरण का उपयोग करता है
  2. Sturmian अनुक्रम सिद्धांत: Fibonacci अनुक्रम (5+5)/2(5+\sqrt{5})/2-शक्तियों से बचते हैं, यह Sturmian अनुक्रमों में इष्टतम परिणाम है

हाल की प्रगति

  1. Shallit-Shur कार्य: शक्ति-परिहार और कारक जटिलता संबंध अनुसंधान के लिए ढांचा स्थापित किया
  2. Ollinger-Shallit कार्य: (5/2)+(5/2)^+-शक्तियों से बचने वाले Rote अनुक्रमों के ठोस उदाहरण निर्मित किए
  3. Dvořáková आदि का कार्य: प्रमाणित किया कि g(fω(0))g(f^{\omega}(0)) (5/2)+(5/2)^+-शक्तियों से बचता है और Rote अनुक्रम है

इस पेपर का योगदान

यह पेपर संपूर्ण संरचनात्मक प्रमेय प्रदान करता है, जो Restivo-Salemi प्रमेय के अतिव्यापन-मुक्त अनुक्रमों में स्थिति के समान है, सैद्धांतिक अंतराल को भरता है।

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. संपूर्ण चिन्हन: सभी (5/2)+(5/2)^+-शक्तियों से बचने वाले Rote अनुक्रमों की संपूर्ण संरचना प्रदान की
  2. अनुमान सत्यापन: रूपांतरण ff और gg की कार्रवाई पर Ollinger-Shallit अनुमान की पुष्टि की
  3. विधि नवाचार: संयोजक तर्क और कम्प्यूटेशनल सत्यापन को जोड़ा, कठोर प्रमाण प्रदान किया

सीमाएं

  1. कम्प्यूटेशनल निर्भरता: कुछ मुख्य लेम्मा कंप्यूटर सत्यापन पर निर्भर हैं, हालांकि परिणाम विश्वसनीय हैं लेकिन शुद्ध सैद्धांतिक प्रमाण की कमी है
  2. विशिष्ट घातांक: परिणाम केवल (5/2)+(5/2)^+-शक्तियों पर लागू होते हैं, अन्य घातांकों के लिए सामान्यीकरण को आगे के अनुसंधान की आवश्यकता है
  3. बाइनरी प्रतिबंध: मुख्य परिणाम बाइनरी अनुक्रमों पर केंद्रित हैं, त्रिगुण स्थिति अभी भी अन्वेषण के लिए खुली है

भविष्य की दिशाएं

  1. त्रिगुण सामान्यीकरण: त्रिगुण अनुक्रमों में जटिलता 2n+12n+1 और शक्ति-परिहार के संबंध की खोज करना
  2. अन्य घातांक: अन्य घातांक शक्तियों से बचने वाले कम जटिलता वाले अनुक्रमों की संरचना का अनुसंधान करना
  3. एल्गोरिदमिक अनुप्रयोग: संरचनात्मक प्रमेय को अनुक्रम निर्माण और पहचान एल्गोरिदम में लागू करना

गहन मूल्यांकन

शक्तियां

  1. सैद्धांतिक पूर्णता: संपूर्ण संरचनात्मक चिन्हन प्रदान करता है, एक महत्वपूर्ण खुली समस्या को हल करता है
  2. विधि कठोरता: सैद्धांतिक विश्लेषण और कम्प्यूटेशनल सत्यापन को जोड़ता है, प्रमाण प्रक्रिया सुसंगत और विश्वसनीय है
  3. तकनीकी नवाचार: उचित/अनुचित अनुक्रमों की अवधारणा मौलिक है
  4. व्यावहारिक मूल्य: संरचनात्मक प्रमेय संबंधित अनुक्रमों के निर्माण और विश्लेषण के लिए सैद्धांतिक उपकरण प्रदान करता है

कमियां

  1. प्रमाण जटिलता: कुछ लेम्मा के प्रमाण बड़े पैमाने पर केस विश्लेषण पर निर्भर हैं, अधिक सुंदर विधि संभव हो सकती है
  2. कम्प्यूटेशनल सत्यापन: मुख्य चरण कंप्यूटर खोज पर निर्भर हैं, सैद्धांतिक शुद्धता कुछ हद तक कम है
  3. सामान्यीकरण: परिणामों के अन्य पैरामीटर या वर्णमाला में सामान्यीकरण की संभावना पर्याप्त रूप से स्पष्ट नहीं है

प्रभाव

  1. सैद्धांतिक योगदान: संयोजक शब्द सिद्धांत के लिए नया संरचनात्मक प्रमेय प्रदान करता है, महत्वपूर्ण सैद्धांतिक मूल्य है
  2. पद्धति महत्व: सैद्धांतिक विश्लेषण और कम्प्यूटेशनल सत्यापन के संयोजन की प्रभावशीलता प्रदर्शित करता है
  3. अनुवर्ती अनुसंधान: संबंधित समस्याओं के अनुसंधान के लिए नए विचार और उपकरण प्रदान करता है

लागू परिदृश्य

  1. सैद्धांतिक अनुसंधान: संयोजक शब्द सिद्धांत, औपचारिक भाषा सिद्धांत अनुसंधान
  2. अनुक्रम विश्लेषण: विशिष्ट गुणों वाले अनंत अनुक्रमों का निर्माण और विश्लेषण
  3. एल्गोरिदम डिजाइन: विशिष्ट पैटर्न से बचने वाले अनुक्रम निर्माण एल्गोरिदम

संदर्भ

पेपर इस क्षेत्र के महत्वपूर्ण कार्यों का हवाला देता है, जिनमें शामिल हैं:

  • अतिव्यापन-मुक्त अनुक्रमों पर Restivo & Salemi का शास्त्रीय संरचनात्मक प्रमेय
  • शक्ति-परिहार और जटिलता संबंध पर Shallit & Shur का अग्रणी कार्य
  • Rote अनुक्रमों की पुनरावृत्ति सीमा पर Ollinger & Shallit का नवीनतम अनुसंधान
  • Sturmian अनुक्रमों पर Carpi & de Luca का शास्त्रीय परिणाम

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