K-सममित अनुक्रम

गणित और सैद्धांतिक कंप्यूटर विज्ञान में, k-सममित अनुक्रम रैखिक पुनरावृत्ति समीकरणों को संतुष्ट करने वाला अनुक्रम है जो पूर्णांकों के आधार-k निरूपण को परावर्तित करता हैं। k-सममित अनुक्रमों का वर्ग स्वचालित अनुक्रम के वर्ग को अनंत आकार के अक्षरों में सामान्यीकृत करता है|

परिभाषा

k-सममित अनुक्रमों के कई लक्षण उपस्थित हैं, जो सभी समतुल्य हैं। कुछ सामान्य लक्षण इस प्रकार हैं। प्रत्येक के लिए, हम R' को क्रमविनिमेय नोथेरियन वलय के रूप में लेते हैं और हम R को R' युक्त वलय (गणित) के रूप में लेते हैं।

k-कर्नेल

चलो k ≥ 2. अनुक्रम का k-कर्नेल $s(n)_{n\geq 0}$ अनुवर्ती का समुच्चय है

$K_{k}(s)=\{s(k^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq k^{e}-1\}.$

क्रम $s(n)_{n\geq 0}$ (R′, k)-नियमित है (अक्सर केवल k-नियमित तक छोटा किया जाता है) यदि $R'$-के द्वारा उत्पन्न मॉड्यूल_k(s) एक परिमित रूप से उत्पन्न मॉड्यूल है|परिमित रूप से उत्पन्न R′-मॉड्यूल (गणित)। विशेष मामले में जब $R'=R=\mathbb {Q}$, क्रम $s(n)_{n\geq 0}$ है $k$-नियमित यदि $K_{k}(s)$ एक परिमित-आयामी वेक्टर स्थान में समाहित है $\mathbb {Q}$.

रैखिक संयोजन

एक अनुक्रम s(n) k-नियमित है यदि सभी e के लिए एक पूर्णांक E मौजूद है_j > ई और 0 ≤ आर_j ≤ क^e_j − 1, फॉर्म s(k) के s का प्रत्येक अनुवर्ती^e_jn+r_j) R'-रैखिक संयोजन के रूप में व्यक्त किया जा सकता है $\sum _{i}c_{ij}s(k^{f_{ij}}n+b_{ij})$, जहां सी_ij एक पूर्णांक है, एफ_ij ≤ ई, और 0 ≤ बी_ij ≤ क^f_ij - 1. वैकल्पिक रूप से, एक अनुक्रम s(n) k-नियमित है यदि कोई पूर्णांक r और अनुवर्ती s मौजूद है₁(एन), ..., एस_r(n) ऐसा कि, सभी 1 ≤ i ≤ r और 0 ≤ a ≤ k − 1 के लिए, प्रत्येक अनुक्रम s_i(kn + a) k-कर्नेल K में_k(s) अनुवर्ती s का एक R′-रैखिक संयोजन है_i(एन)।

औपचारिक शृंखला

चलो एक्स₀, ..., एक्स_k − 1 k नॉन-कम्यूटिंग वेरिएबल्स का एक सेट बनें और τ को स्ट्रिंग x पर कुछ प्राकृतिक संख्या n भेजने वाला एक मानचित्र बनने दें_{a0</उप>...एक्स उप>एe − 1}, जहां x का आधार-k प्रतिनिधित्व स्ट्रिंग a है_e − 1...ए₀. तब एक अनुक्रम s(n) k-नियमित होता है यदि और केवल यदि औपचारिक शक्ति श्रृंखला हो $\sum _{n\geq 0}s(n)\tau (n)$ है $\mathbb {Z}$-तर्कसंगत श्रृंखला.

ऑटोमेटा-सैद्धांतिक

के-नियमित अनुक्रम की औपचारिक श्रृंखला परिभाषा मार्सेल-पॉल शुट्ज़ेनबर्गर | शुट्ज़ेनबर्गर की मैट्रिक्स मशीन के समान एक ऑटोमेटन लक्षण वर्णन की ओर ले जाती है।

इतिहास

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

उदाहरण

रूलर अनुक्रम

होने देना $s(n)=\nu _{2}(n+1)$ पी-एडिक मूल्यांकन हो | $2$- का आदिक मूल्यांकन $n+1$. शासक क्रम $s(n)_{n\geq 0}=0,1,0,2,0,1,0,3,\dots$ (OEIS: A007814) है $2$-नियमित, और $2$-कर्नेल

$\{s(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq 2^{e}-1\}$

द्वारा उत्पन्न द्वि-आयामी वेक्टर स्थान में समाहित है $s(n)_{n\geq 0}$ और निरंतर क्रम $1,1,1,\dots$. ये आधार तत्व पुनरावृत्ति संबंधों की ओर ले जाते हैं

${\begin{aligned}s(2n)&=0,\\s(4n+1)&=s(2n+1)-s(n),\\s(4n+3)&=2s(2n+1)-s(n),\end{aligned}}$

जो, प्रारंभिक शर्तों के साथ $s(0)=0$ और $s(1)=1$, अनुक्रम को विशिष्ट रूप से निर्धारित करें।

गुरु-मोर्स अनुक्रम

थ्यू-मोर्स अनुक्रम t(n) (OEIS: A010060) रूपवाद 0 → 01, 1 → 10 का निश्चित बिंदु (गणित) है। यह ज्ञात है कि थ्यू-मोर्स अनुक्रम 2-स्वचालित है। इस प्रकार, यह 2-नियमित भी है, और इसका 2-कर्नेल भी है

$\{t(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq 2^{e}-1\}$

अनुवर्ती से मिलकर बनता है $t(n)_{n\geq 0}$ और $t(2n+1)_{n\geq 0}$.

कैंटर संख्या

कैंटर सेट का क्रम c(n) (OEIS: A005823) में वे संख्याएँ शामिल होती हैं जिनके टर्नरी अंक प्रणाली विस्तार में कोई 1 नहीं होता है। यह दिखाना सीधा है

${\begin{aligned}c(2n)&=3c(n),\\c(2n+1)&=3c(n)+2,\end{aligned}}$

और इसलिए कैंटर संख्याओं का क्रम 2-नियमित है। इसी प्रकार स्टेनली अनुक्रम

0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, ... (sequence A005836 in the OEIS)

उन संख्याओं की संख्या जिनके त्रिक विस्तार में कोई 2s नहीं है, वह भी 2-नियमित है।

संख्याओं को क्रमबद्ध करना

एल्गोरिदम के व्यापक अध्ययन के लिए के-नियमितता की धारणा का कुछ दिलचस्प अनुप्रयोग मर्ज़ सॉर्ट एल्गोरिदम के विश्लेषण में पाया जाता है। एन मानों की एक सूची को देखते हुए, मर्ज सॉर्ट एल्गोरिदम द्वारा की गई तुलनाओं की संख्या सॉर्टिंग संख्याएं हैं, जो पुनरावृत्ति संबंध द्वारा नियंत्रित होती हैं

${\begin{aligned}T(1)&=0,\\T(n)&=T(\lfloor n/2\rfloor )+T(\lceil n/2\rceil )+n-1,\ n\geq 2.\end{aligned}}$

परिणामस्वरूप, मर्ज सॉर्ट, टी(एन) के लिए पुनरावृत्ति संबंध द्वारा परिभाषित अनुक्रम, 2-नियमित अनुक्रम का गठन करता है।

अन्य अनुक्रम

अगर $f(x)$ तो, एक पूर्णांक-मूल्यवान बहुपद है $f(n)_{n\geq 0}$ प्रत्येक के लिए k-नियमित है $k\geq 2$.

गोल्ड का अनुक्रम|ग्लेशर-गोल्ड अनुक्रम 2-नियमित है। स्टर्न-ब्रोकॉट अनुक्रम 2-नियमित है।

अल्लोचे और शैलिट अपने पेपर में के-रेगुलर अनुक्रमों के कई अतिरिक्त उदाहरण देते हैं।

गुण

के-नियमित अनुक्रम कई दिलचस्प गुण प्रदर्शित करते हैं।

• प्रत्येक स्वचालित अनुक्रम|k-स्वचालित अनुक्रम k-नियमित है।
• प्रत्येक k-सिंक्रोनाइज़्ड अनुक्रम|k-सिंक्रोनाइज़्ड अनुक्रम k-नियमित है।
• एक k-नियमित अनुक्रम सीमित रूप से कई मान लेता है यदि और केवल यदि यह k-स्वचालित है। यह k-नियमित अनुक्रमों के वर्ग का k-स्वचालित अनुक्रमों के वर्ग का सामान्यीकरण होने का तात्कालिक परिणाम है।
• के-रेगुलर अनुक्रमों का वर्ग टर्मवाइज जोड़, टर्मवाइज गुणन और कनवल्शन के तहत बंद है। के-नियमित अनुक्रमों का वर्ग भी अनुक्रम के प्रत्येक पद को एक पूर्णांक λ द्वारा स्केल करने के तहत बंद किया जाता है। विशेष रूप से, के-नियमित पावर श्रृंखला का सेट एक रिंग बनाता है।
• अगर $s(n)_{n\geq 0}$ k-नियमित है, तो सभी पूर्णांकों के लिए $m\geq 1$, $(s(n){\bmod {m}})_{n\geq 0}$ k-स्वचालित है. हालाँकि, बातचीत कायम नहीं है। *गुणात्मक रूप से स्वतंत्र k, l ≥ 2 के लिए, यदि कोई अनुक्रम k-नियमित और l-नियमित दोनों है, तो अनुक्रम एक रैखिक पुनरावृत्ति को संतुष्ट करता है। यह उन अनुक्रमों के संबंध में कोबम के कारण परिणाम का सामान्यीकरण है जो के-स्वचालित और एल-स्वचालित दोनों हैं।
• पूर्णांकों के k-नियमित अनुक्रम का nवाँ पद n में अधिकतम बहुपद रूप से बढ़ता है।
• अगर $F$ एक क्षेत्र है और $x\in F$, फिर शक्तियों का क्रम $(x^{n})_{n\geq 0}$ k-नियमित है यदि और केवल यदि $x=0$ या $x$ एकता की जड़ है.

के-नियमितता को सिद्ध और असिद्ध करना

एक उम्मीदवार अनुक्रम दिया गया $s=s(n)_{n\geq 0}$ इसे k-नियमित नहीं माना जाता है, k-नियमितता को आम तौर पर कर्नेल के तत्वों की गणना करके सीधे परिभाषा से सिद्ध किया जा सकता है $s$ और यह सिद्ध करना कि प्रपत्र के सभी तत्व $(s(k^{r}n+e))_{n\geq 0}$ साथ $r$ पर्याप्त रूप से बड़ा और $0\leq e<2^{r}$ के स्थान पर छोटे घातांक वाले कर्नेल तत्वों के रैखिक संयोजन के रूप में लिखा जा सकता है $r$. यह आमतौर पर कम्प्यूटेशनल रूप से सीधा है।

दूसरी ओर, उम्मीदवार अनुक्रम की k-नियमितता को अस्वीकार करना $s$ आमतौर पर एक का उत्पादन करने की आवश्यकता होती है $\mathbb {Z}$-के कर्नेल में रैखिक रूप से स्वतंत्र उपसमुच्चय $s$, जो आम तौर पर पेचीदा है। ऐसे प्रमाण का एक उदाहरण यहां दिया गया है।

होने देना $e_{0}(n)$ की संख्या को निरूपित करें $0$के द्विआधारी विस्तार में है $n$. होने देना $e_{1}(n)$ की संख्या को निरूपित करें $1$के द्विआधारी विस्तार में है $n$. क्रम $f(n):=e_{0}(n)-e_{1}(n)$ 2-नियमित दिखाया जा सकता है। क्रम $g=g(n):=|f(n)|$ हालाँकि, निम्नलिखित तर्क के अनुसार, 2-नियमित नहीं है। कल्पना करना $(g(n))_{n\geq 0}$ 2-नियमित है. हम दावा करते हैं कि तत्व $g(2^{k}n)$ के लिए $n\geq 1$ और $k\geq 0$ के 2-कर्नेल का $g$ पर रैखिक रूप से स्वतंत्र हैं $\mathbb {Z}$. कार्यक्रम $n\mapsto e_{0}(n)-e_{1}(n)$ पूर्णांकों पर विशेषण है, तो चलिए $x_{m}$ ऐसा सबसे छोटा पूर्णांक बनें $e_{0}(x_{m})-e_{1}(x_{m})=m$. 2-नियमितता से $(g(n))_{n\geq 0}$, वहां है $b\geq 0$ और स्थिरांक $c_{i}$ ऐसा कि प्रत्येक के लिए $n\geq 0$,

$\sum _{0\leq i\leq b}c_{i}g(2^{i}n)=0.$

होने देना $a$ जिसके लिए न्यूनतम मूल्य हो $c_{a}\neq 0$. फिर हर एक के लिए $n\geq 0$,

$g(2^{a}n)=\sum _{a+1\leq i\leq b}-(c_{i}/c_{a})g(2^{i}n).$

इस अभिव्यक्ति का मूल्यांकन पर $n=x_{m}$, कहाँ $m=0,-1,1,2,-2$ और इसी तरह क्रमिक रूप से, हम बायीं ओर प्राप्त करते हैं

$g(2^{a}x_{m})=|e_{0}(x_{m})-e_{1}(x_{m})+a|=|m+a|,$

और दाहिनी ओर,

$\sum _{a+1\leq i\leq b}-(c_{i}/c_{a})|m+i|.$

यह प्रत्येक पूर्णांक के लिए इसका अनुसरण करता है $m$,

$|m+a|=\sum _{a+1\leq i\leq b}-(c_{i}/c_{a})|m+i|.$

लेकिन के लिए $m\geq -a-1$, समीकरण का दाहिना भाग नीरस है क्योंकि यह फॉर्म का है $Am+B$ कुछ स्थिरांक के लिए $A,B$, जबकि बाईं ओर नहीं है, जैसा कि क्रमिक रूप से प्लग इन करके जांचा जा सकता है $m=-a-1$, $m=-a$, और $m=-a+1$. इसलिए, $(g(n))_{n\geq 0}$ 2-नियमित नहीं है.

संदर्भ

• Allouche, Jean-Paul; Shallit, Jeffrey (1992), "The ring of k-regular sequences", Theoret. Comput. Sci., 98 (2): 163–197, doi:10.1016/0304-3975(92)90001-v.
• Allouche, Jean-Paul; Shallit, Jeffrey (2003), "The ring of k-regular sequences, II", Theoret. Comput. Sci., 307: 3–29, doi:10.1016/s0304-3975(03)00090-2.
• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015.