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{array}{rl}s(2n)& =0,\\ s(4n+1)& =s(\end{array}$