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 उपस्थित है सभी e_j > E और 0 ≤ r_j ≤ k^e_j − 1, s(k) के s^e_jn+r_j) का प्रत्येक अनुवर्ती निर्मित करता हैं R'-रैखिक संयोजन $\sum _{i}c_{ij}s(k^{f_{ij}}n+b_{ij})$ के रूप में व्यक्त किया जा सकता है, जहां c_ij एक पूर्णांक है, f_ij ≤ E, और 0 ≤ b_ij ≤ k^f_ij - 1होता हैं।

वैकल्पिक रूप से, अनुक्रम s(n) k-सममित है यदि कोई पूर्णांक r और अनुवर्ती s₁(n), ..., s_r(n) उपस्थित हैं जैसे की, सभी 1 ≤ i ≤ r और 0 ≤ a ≤ k − 1 के लिए, प्रत्येक अनुक्रम s_i(kn + a) k-कर्नेल K_k(s) अनुवर्ती s_i(n) का R′-रैखिक संयोजन है।

प्रारूपिक श्रेणी

माना x₀, ..., x_k − 1 k अरूपांतरित चर का समुच्चय बनाया और τ को श्रृंखला x_{a0 ... Xae − 1}पर कुछ प्राकृतिक संख्या n भेजने वाला मानचित्र बनाते हैं, जहां x का आधार-k प्रतिनिधित्व श्रृंखला a_e−1...a₀ है। तब एक अनुक्रम s(n) k-सममित होता है यदि और केवल यदि प्रारूपिक श्रेणी $\sum _{n\geq 0}s(n)\tau (n)$ है $\mathbb {Z}$- परिमेय होती हैं।

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

k-सममित अनुक्रम की प्रारूपिक श्रेणी शुट्ज़ेनबर्गर की आव्यूह मशीन के समान ऑटोमेटन लक्षण वर्णन की तरफ ले जाती है।

इतिहास

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

उदाहरण

रूलर अनुक्रम

माना $s(n)=\nu _{2}(n+1)$ $n+1$ का 2-अभिन्नकल्प मूल्यांकन होता हैं | रूलर अनुक्रम $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(2n+1)-<!--\; -\; -->s(n),\\ s(4n+3)& =2s\end{array}$