متتالية منتظمة من الرتبة k

📅 آخر تحديث: ٢٤ يوليو ٢٠٢٦
✍️ نُشر في: ٢٤ يوليو ٢٠٢٦
📷 يحتوي على 73 صور
الموسوعة الحرة

في الرياضيات وعلوم الحاسوب النظرية ، تُعرف المتتالية المنتظمة من الرتبة k بأنها متتالية تحقق معادلات تكرارية خطية تعكس تمثيلات الأعداد الصحيحة في النظام العددي ذي الأساس k . وتُعمم فئة المتتاليات المنتظمة من الرتبة k فئة المتتاليات التلقائية من الرتبة k لتشمل أبجديات ذات حجم لانهائي.

تعريف

توجد عدة توصيفات للمتتاليات المنتظمة من الرتبة k ، وجميعها متكافئة. وفيما يلي بعض التوصيفات الشائعة. لكل منها، نعتبر R ′ حلقة نوثرية تبديلية ، ونعتبر R حلقة تحتوي على R ′.

نواة k

ليكن k  ≥  2. نواة k للمتتاليةs(ن)ن≥0{\displaystyle s(n)_{n\geq 0}}هي مجموعة المتتاليات الفرعية

كك(s)={s(كهـن+ر)ن≥0:هـ≥0 و 0≤ر≤كهـ-1}.{\displaystyle K_{k}(s)=\{s(k^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq k^{e}-1\}.}

التسلسلs(ن)ن≥0{\displaystyle s(n)_{n\geq 0}}تكون ( R ′, k ) منتظمة (غالباً ما يتم اختصارها إلى " منتظمة من النوع k ") إذاR′{\displaystyle R'}الوحدة النمطية المولدة بواسطة K k ( s ) هي وحدة نمطية R ′ مولدة بشكل محدود . [ 1 ]

في الحالة الخاصة عندماR′=R=سؤال{\displaystyle R'=R=\mathbb {Q} }، التسلسلs(ن)ن≥0{\displaystyle s(n)_{n\geq 0}}يكونك{\displaystyle k}-منتظام إذاكك(s){\displaystyle K_{k}(s)}محتواة في فضاء متجهي محدود الأبعاد علىسؤال{\displaystyle \mathbb {Q} }.

التركيبات الخطية

تكون المتتالية s ( n ) منتظمة من الرتبة k إذا وُجد عدد صحيح E بحيث يكون كل جزء من s على الصورة s ( kejn + rj ) قابلاً للتعبير عنه كتركيبة خطية من الرتبة R ′ ، وذلك لكل ej > E و 0 ≤ rj ≤ kej − 1.    ∑أناجأناجs(كوأناجن+بأناج){\displaystyle \sum _{i}c_{ij}s(k^{f_{ij}}n+b_{ij})}، حيث c ij عدد صحيح، و f ij ≤ E ، و 0 ≤ b ij ≤ k f ij  −  1. [ 2 ]

بدلاً من ذلك، تكون المتتالية s ( n ) منتظمة من الرتبة k إذا وُجد عدد صحيح r ومتتاليات جزئية s₁ ( n )، ...، sₚ ( n ) بحيث يكون، لكل 1 ≤ i ≤ r و 0 ≤ a ≤ k − 1 ، كل متتالية sᵢ ( kₙ + a ) في النواة k -kernel Kₖ ( s ) عبارة عن توليفة خطية من الرتبة R ′ للمتتاليات الجزئية sᵢ ( n ) . [ 2 ]    

سلسلة رسمية

لتكن x₀ , ..., xₖ₋₁ مجموعة من k متغيرات غير تبادلية ، ولتكن τ دالة تُرسل عددًا طبيعيًا n إلى السلسلة xₖ = a₀ ... xₖ = e⁻¹ ، حيث يكون تمثيل xₖ في الأساس k هو السلسلة aₖ = e⁻¹ ... a₀ . عندئذٍ ،   تكون المتتالية s ( n ) منتظمة من الرتبة k إذا وفقط إذا كانت المتسلسلة الرسمية    ∑ن≥0s(ن)τ(ن){\displaystyle \sum _{n\geq 0}s(n)\tau (n)}يكونZ{\displaystyle \mathbb {Z} }- عقلاني . [ 3 ]

نظرية الأوتوماتا

يؤدي التعريف الرسمي لسلسلة متتابعة منتظمة من الرتبة k إلى توصيف آلي مشابه لآلة المصفوفات الخاصة بشوتزنبرغر . [ 4 ] [ 5 ]

تاريخ

تم بحث مفهوم المتتابعات المنتظمة من الرتبة k لأول مرة في ورقتين بحثيتين من تأليف ألوش وشاليت. [ 6 ] وقبل ذلك، درس بيرستل ورويتناور نظرية المتسلسلات النسبية ، والتي ترتبط ارتباطًا وثيقًا بالمتتابعات المنتظمة من الرتبة k . [ 7 ]

أمثلة

تسلسل المسطرة

يتركs(ن)=ν2(ن+1){\displaystyle s(n)=\nu _{2}(n+1)}كن2{\displaystyle 2}التقييم الأدي لـن+1{\displaystyle n+1}تسلسل المسطرةs(ن)ن≥0=0،1،0،2،0،1،0،3،...{\displaystyle s(n)_{n\geq 0}=0,1,0,2,0,1,0,3,\dots }( OEIS : A007814  ) هو2{\displaystyle 2}-منتظم، و2{\displaystyle 2}-kernel

{s(2هـن+ر)ن≥0:هـ≥0 و 0≤ر≤2هـ-1}{\displaystyle \{s(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq 2^{e}-1\}}

يتم احتواؤها في فضاء المتجهات ثنائي الأبعاد الناتج عنs(ن)ن≥0{\displaystyle s(n)_{n\geq 0}}والتسلسل الثابت1،1،1،...{\displaystyle 1,1,1,\dots }تؤدي هذه العناصر الأساسية إلى علاقات التكرار.

s(2ن)=0،s(4ن+1)=s(2ن+1)-s(ن)،s(4ن+3)=2s(2ن+1)-s(ن)،{\displaystyle {\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{\displaystyle s(0)=0}وs(1)=1{\displaystyle s(1)=1}[ 8 ] ، تحديد التسلسل بشكل فريد.

متتالية ثو-مورس

متتالية ثو -مورس t ( n ) ( OEIS : A010060  ) هي النقطة الثابتة للتشاكل 0 → 01، 1 → 10. من المعروف أن متتالية ثو-مورس هي متتالية تلقائية من الدرجة 2. وبالتالي، فهي أيضًا منتظمة من الدرجة 2، ونواتها من الدرجة 2.

{ت(2هـن+ر)ن≥0:هـ≥0 و 0≤ر≤2هـ-1}{\displaystyle \{t(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq 2^{e}-1\}}

يتكون من التسلسلات الفرعيةت(ن)ن≥0{\displaystyle t(n)_{n\geq 0}}وت(2ن+1)ن≥0{\displaystyle t(2n+1)_{n\geq 0}}.

أرقام المنشد

تتألف متتالية أعداد كانتور c ( n ) ( OEIS : A005823  ) من أعداد لا تحتوي تمثيلاتها الثلاثية على الرقم 1. ومن السهل إثبات ذلك.

ج(2ن)=3ج(ن)،ج(2ن+1)=3ج(ن)+2،{\displaystyle {\begin{aligned}c(2n)&=3c(n),\\c(2n+1)&=3c(n)+2,\end{aligned}}}

وبالتالي فإن متتالية أعداد كانتور منتظمة من الدرجة الثانية. وبالمثل، فإن متتالية ستانلي

0، 1، 3، 4، 9، 10، 12، 13، 27، 28، 30، 31، 36، 37، 39، 40، ... (التسلسل A005836 في OEIS )

الأعداد التي لا تحتوي تمثيلاتها الثلاثية على الرقم 2 هي أيضًا أعداد منتظمة من الدرجة 2. [ 9 ]

فرز الأرقام

يُعد تحليل خوارزمية فرز الدمج تطبيقًا مثيرًا للاهتمام لمفهوم الانتظام من الرتبة k في دراسة الخوارزميات بشكل عام . فبالنظر إلى قائمة من n قيمة، فإن عدد المقارنات التي تُجريها خوارزمية فرز الدمج هو عدد عمليات الفرز ، والذي يخضع لعلاقة تكرارية.

تي(1)=0،تي(ن)=تي(⌊ن/2⌋)+تي(⌈ن/2⌉)+ن-1، ن≥2.{\displaystyle {\begin{aligned}T(1)&=0,\\T(n)&=T(\lfloor n/2\rfloor )+T(\lceil n/2\rceil )+n-1,\ n\geq 2.\end{aligned}}}

ونتيجة لذلك، فإن التسلسل المحدد بواسطة علاقة التكرار لفرز الدمج، T ( n )، يشكل تسلسلًا منتظمًا من الدرجة 2. [ 10 ]

تسلسلات أخرى

لوو(x){\displaystyle f(x)}إذا كانت دالة كثيرة الحدود ذات قيم صحيحة ، فإنو(ن)ن≥0{\displaystyle f(n)_{n\geq 0}}يكون k- منتظمًا لكلك≥2{\displaystyle k\geq 2}.

متتالية غليشر -غولد منتظمة من الدرجة الثانية. متتالية ستيرن-بروكوت منتظمة من الدرجة الثانية.

يقدم ألوش وشاليت عددًا من الأمثلة الإضافية على المتتاليات المنتظمة من الرتبة k في أوراقهما البحثية. [ 6 ]

ملكيات

تُظهر المتتاليات المنتظمة من النوع k عددًا من الخصائص المثيرة للاهتمام.

  • كل تسلسل تلقائي من الرتبة k هو تسلسل منتظم من الرتبة k . [ 11 ]
  • كل تسلسل متزامن من النوع k يكون منتظمًا من النوع k .
  • تأخذ المتتالية المنتظمة من الرتبة k عددًا محدودًا من القيم إذا وفقط إذا كانت تلقائية من الرتبة k . [ 12 ] هذه نتيجة مباشرة لكون فئة المتتاليات المنتظمة من الرتبة k تعميمًا لفئة المتتاليات التلقائية من الرتبة k .
  • تُعتبر فئة المتتابعات المنتظمة من الرتبة k مغلقة تحت عمليات الجمع والضرب والالتفاف لكل حد . كما تُعتبر هذه الفئة مغلقة أيضًا تحت عملية ضرب كل حد من حدود المتتابعة بعدد صحيح λ. [ 12 ] [ 13 ] [ 14 ] [ 15 ] وعلى وجه الخصوص، تُشكل مجموعة متسلسلات القوى المنتظمة من الرتبة k حلقة. [ 16 ]
  • لوs(ن)ن≥0{\displaystyle s(n)_{n\geq 0}}إذا كانت k منتظمة، فعندئذٍ لجميع الأعداد الصحيحةم≥1{\displaystyle m\geq 1}،(s(ن)تعديلم)ن≥0{\displaystyle (s(n){\bmod {m}})_{n\geq 0}}هي آلية من النوع k . ومع ذلك، فإن العكس غير صحيح. [ 17 ]
  • بالنسبة للمتتاليات المستقلة ضربيًا k و l ≥ 2، إذا كانت متتالية ما منتظمة من الرتبة k ومنتظمة من الرتبة l ، فإنها تحقق علاقة تكرارية خطية. [ 18 ] وهذا تعميم لنتيجة توصل إليها كوبهام بشأن المتتاليات التي تكون تلقائية من الرتبة k وتلقائية من الرتبة l . [ 19 ]   
  • ينمو الحد النوني من متتالية منتظمة من الأعداد الصحيحة من الرتبة k على الأكثر بشكل متعدد الحدود في n . [ 20 ]
  • لوF{\displaystyle F}هو حقل وx∈F{\displaystyle x\in F}ثم تسلسل القوى(xن)ن≥0{\displaystyle (x^{n})_{n\geq 0}}تكون منتظمة من الرتبة k إذا وفقط إذاx=0{\displaystyle x=0}أوx{\displaystyle x}هو أصل الوحدة . [ 21 ]

إثبات ودحض الانتظام من النوع k

بالنظر إلى تسلسل مرشحs=s(ن)ن≥0{\displaystyle s=s(n)_{n\geq 0}}إذا لم يكن معروفًا أن k منتظم، فيمكن عادةً إثبات انتظام k مباشرةً من التعريف عن طريق حساب عناصر نواةs{\displaystyle s}وإثبات أن جميع عناصر الشكل(s(كرن+هـ))ن≥0{\displaystyle (s(k^{r}n+e))_{n\geq 0}}معر{\displaystyle r}كبيرة بما يكفي و0≤هـ<2ر{\displaystyle 0\leq e<2^{r}}يمكن كتابتها كمجموعات خطية من عناصر النواة ذات أسس أصغر بدلاً منر{\displaystyle r}. عادةً ما يكون هذا الأمر بسيطًا من الناحية الحسابية.

من ناحية أخرى، دحض انتظام k للتسلسل المرشحs{\displaystyle s}يتطلب الأمر عادةً من المرء أن ينتجZ{\displaystyle \mathbb {Z} }مجموعة فرعية مستقلة خطيًا في نواةs{\displaystyle s}وهو أمرٌ عادةً ما يكون أكثر تعقيداً. إليك مثالٌ على هذا النوع من البراهين.

يتركهـ0(ن){\displaystyle e_{0}(n)}يشير إلى عدد0{\displaystyle 0}'s في التوسع الثنائي لـن{\displaystyle n}. يتركهـ1(ن){\displaystyle e_{1}(n)}يشير إلى عدد1{\displaystyle 1}'s في التوسع الثنائي لـن{\displaystyle n}التسلسلو(ن):=هـ0(ن)-هـ1(ن){\displaystyle f(n):=e_{0}(n)-e_{1}(n)}يمكن إثبات أن المتتالية منتظمة من الدرجة الثانية.ز=ز(ن):=|و(ن)|{\displaystyle g=g(n):=|f(n)|}إلا أنها ليست منتظمة من الدرجة الثانية، وذلك بحسب الحجة التالية. لنفترض(ز(ن))ن≥0{\displaystyle (g(n))_{n\geq 0}}هي ثنائية منتظمة. ندعي أن العناصرز(2كن){\displaystyle g(2^{k}n)}لن≥1{\displaystyle n\geq 1}وك≥0{\displaystyle k\geq 0}من النواة الثانية لـز{\displaystyle g}مستقلة خطيًا علىZ{\displaystyle \mathbb {Z} }الوظيفةن↦هـ0(ن)-هـ1(ن){\displaystyle n\mapsto e_{0}(n)-e_{1}(n)}الدالة شاملة على الأعداد الصحيحة، لذا لنفترضxم{\displaystyle x_{m}}ليكن أصغر عدد صحيح بحيثهـ0(xم)-هـ1(xم)=م{\displaystyle e_{0}(x_{m})-e_{1}(x_{m})=m}. بواسطة انتظام 2 لـ(ز(ن))ن≥0{\displaystyle (g(n))_{n\geq 0}}، هناكب≥0{\displaystyle b\geq 0}والثوابتجأنا{\displaystyle c_{i}}بحيث يكون لكلن≥0{\displaystyle n\geq 0}،

∑0≤أنا≤بجأناز(2أنان)=0.{\displaystyle \sum _{0\leq i\leq b}c_{i}g(2^{i}n)=0.}

يتركأ{\displaystyle a}أن تكون أقل قيمة والتيجأ≠0{\displaystyle c_{a}\neq 0}ثم لكلن≥0{\displaystyle n\geq 0}،

ز(2أن)=∑أ+1≤أنا≤ب-(جأنا/جأ)ز(2أنان).{\displaystyle g(2^{a}n)=\sum _{a+1\leq i\leq b}-(c_{i}/c_{a})g(2^{i}n).}

تقييم هذا التعبير عندن=xم{\displaystyle n=x_{m}}، أينم=0،-1،1،2،-2{\displaystyle m=0,-1,1,2,-2}وهكذا بالتتابع، نحصل على الجانب الأيسر

ز(2أxم)=|هـ0(xم)-هـ1(xم)+أ|=|م+أ|،{\displaystyle g(2^{a}x_{m})=|e_{0}(x_{m})-e_{1}(x_{m})+a|=|m+a|,}

وعلى الجانب الأيمن،

∑أ+1≤أنا≤ب-(جأنا/جأ)|م+أنا|.{\displaystyle \sum _{a+1\leq i\leq b}-(c_{i}/c_{a})|m+i|.}

ويترتب على ذلك أنه لكل عدد صحيحم{\displaystyle m}،

|م+أ|=∑أ+1≤أنا≤ب-(جأنا/جأ)|م+أنا|.{\displaystyle |m+a|=\sum _{a+1\leq i\leq b}-(c_{i}/c_{a})|m+i|.}

لولام≥-أ-1{\displaystyle m\geq -a-1}، يكون الطرف الأيمن من المعادلة رتيبًا لأنه على الصورةأم+ب{\displaystyle Am+B}بالنسبة لبعض الثوابتأ،ب{\displaystyle A,B}بينما الجانب الأيسر ليس كذلك، كما يمكن التحقق من ذلك عن طريق التوصيل المتتاليم=-أ-1{\displaystyle m=-a-1}،م=-أ{\displaystyle m=-a}، وم=-أ+1{\displaystyle m=-a+1}. لذلك،(ز(ن))ن≥0{\displaystyle (g(n))_{n\geq 0}}ليس منتظمًا من الدرجة الثانية. [ 22 ]

ملحوظات

  1. ↑ ألوش وشاليت (1992)، التعريف 2.1.
  2. 1 2 ألوش وشاليت (1992)، النظرية 2.2.
  3. ↑ ألوش وشاليت (1992)، النظرية 4.3.
  4. ↑ ألوش وشاليت (1992)، النظرية 4.4.
  5. ↑ شوتزنبرغر، م.-ب. (1961)، "حول تعريف عائلة من الأوتوماتا"، المعلومات والتحكم ، 4 ( 2-3 ): 245-270 ، doi : 10.1016/S0019-9958(61)80020-X.
  6. 1 2 علوش وشاليط (1992، 2003).
  7. ↑ بيرستل، جان؛ رويتناور، كريستوف (1988). المتسلسلات الكسرية ولغاتها . سلسلة دراسات الجمعية الأوروبية لعلوم الحاسوب النظرية. المجلد 12. دار نشر سبرينغر . ISBN  978-3-642-73237-9.
  8. ^ علوش وشاليط (1992)، مثال 8.
  9. ^ علوش وشاليط (1992)، الأمثلة 3 و 26.
  10. ^ علوش وشاليط (1992)، مثال 28.
  11. ↑ ألوش وشاليت (1992)، النظرية 2.3.
  12. 1 2 علوش وشاليط (2003) ص. 441.
  13. ↑ ألوش وشاليت (1992)، النظرية 2.5.
  14. ↑ ألوش وشاليت (1992)، النظرية 3.1.
  15. ^ علوش وشاليط (2003) ص. 445.
  16. ↑ ألوش وشاليت (2003) ص 446.
  17. ↑ ألوش وشاليت (2003) ص 441.
  18. ^ بيل، ج. (2006). “تعميم نظرية كوبهام للتسلسلات المنتظمة”. ندوة لوثارينجين دي كومبيناتوار . 54 أ .
  19. ↑ كوبهام، أ. (1969). "حول اعتماد مجموعات الأعداد القابلة للتمييز بواسطة الأوتوماتا المحدودة على الأساس". نظرية الأنظمة الرياضية . 3 (2): 186-192 . doi : 10.1007/BF01746527 . S2CID 19792434 . 
  20. ↑ ألوش وشاليت (1992) نظرية 2.10.
  21. ↑ ألوش وشاليت (2003) ص 444.
  22. ↑ ألوش وشاليت (1993) ص 168-169.

مراجع