2025-11-10T03:15:48.044021

Balanced Fibonacci word rectangles, and beyond

Shallit, Vukusic
Following a recent paper of Anselmo et al., we consider $m \times n$ rectangular matrices formed from the Fibonacci word, and we show that their balance properties can be solved with a finite automaton. We also generalize the result to every Sturmian characteristic word corresponding to a quadratic irrational. Finally, we also examine the analogous question for the Tribonacci word.
academic

كلمات فيبوناتشي المتوازنة المستطيلة، وما وراءها

المعلومات الأساسية

  • معرّف الورقة: 2509.25994
  • العنوان: كلمات فيبوناتشي المتوازنة المستطيلة، وما وراءها
  • المؤلفون: جيفري شاليت (جامعة ووترلو)، إنجريد فوكوسيتش (جامعة يورك)
  • التصنيفات: math.NT cs.DM cs.FL math.CO
  • تاريخ النشر: 15 أكتوبر 2025 (نسخة ArXiv التمهيدية)
  • رابط الورقة: https://arxiv.org/abs/2509.25994

الملخص

تستند هذه الورقة إلى البحث الحديث لأنسيلمو وآخرين، وتدرس مصفوفات مستطيلة m×nm \times n مكونة من كلمات فيبوناتشي، وتثبت أن خصائصها المتوازنة يمكن حلها باستخدام الأتمتة المحدودة. يمتد البحث كذلك النتائج إلى كل كلمة ستيرميان المميزة المقابلة للأعداد غير النسبية التربيعية، ويفحص المشاكل المماثلة لكلمات تريبوناتشي.

الخلفية البحثية والدافع

تعريف المشكلة

المشكلة الأساسية التي تدرسها هذه الورقة هي التوازن في مصفوفات الكلمات: بالنظر إلى متتالية لا نهائية (ai)i≥0(a_i)_{i≥0}، نبني مصفوفة لا نهائية A=(ak,ℓ)k,ℓ≥0A = (a_{k,\ell})_{k,\ell≥0}، حيث ak,ℓ=ak+ℓa_{k,\ell} = a_{k+\ell}. بالنسبة لمصفوفة جزئية m×nm \times n بحجم A(i,m,n)A(i,m,n)، يكون مجموع جميع العناصر: T(i,m,n):=∑k=0m−1∑ℓ=0n−1ai+k+ℓT(i,m,n) := \sum_{k=0}^{m-1}\sum_{\ell=0}^{n-1} a_{i+k+\ell}

مشكلة التوازن هي: لأي أزواج (m,n)(m,n)، تحتوي جميع قيم T(i,m,n)T(i,m,n) على قيمتين مختلفتين على الأكثر؟

الدافع البحثي

  1. الأهمية النظرية: كلمات فيبوناتشي هي كائنات كلاسيكية في الرياضيات التوافقية، وترتبط خصائصها المتوازنة ارتباطاً وثيقاً بنظرية الأعداد ونظرية الأتمتة
  2. القيود الموجودة: أثبت أنسيلمو وآخرون أن المستطيلات متوازنة عندما يكون max⁡(m,n)\max(m,n) عدد فيبوناتشي، لكن التوصيف الكامل لا يزال ناقصاً
  3. الابتكار في الطريقة: استخدام الأتمتة المحدودة لحل هذه الفئة من المشاكل يوفر أدوات حسابية جديدة

المساهمات الأساسية

  1. التوصيف الكامل: توفير توصيف أتمتة محدود كامل لتوازن مستطيلات كلمات فيبوناتشي (النظرية 2 والنتيجة 3)
  2. النتائج المعممة: تعميم النتائج على جميع كلمات ستيرميان المقابلة للأعداد غير النسبية التربيعية (النظرية 2)
  3. التنفيذ الخوارزمي: توفير تنفيذ محدد والتحقق بناءً على برنامج Walnut
  4. نتائج الكثافة: إثبات خصائص كثافة الأزواج المتوازنة (m,n)(m,n) (القضية 6)
  5. توسيع تريبوناتشي: دراسة المشاكل المماثلة لكلمات تريبوناتشي (النظرية 10)

شرح الطريقة

تعريف المهمة

بالنظر إلى متتالية لا نهائية (ai)i≥0(a_i)_{i≥0}، نبني مصفوفة هانكل:

a_i & a_{i+1} & \cdots & a_{i+n-1} \\ a_{i+1} & a_{i+2} & \cdots & a_{i+n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{i+m-1} & a_{i+m} & \cdots & a_{i+m+n-2} \end{pmatrix}$$ الهدف: تحديد أي أزواج $(m,n)$ تجعل جميع قيم $T(i,m,n)$ تحتوي على قيمتين مختلفتين على الأكثر. ### الإطار النظري الأساسي #### خصائص كلمات ستيرميان بالنسبة لكلمات ستيرميان، نعرّف $\Delta(i,m,n) := T(i+1,m,n) - T(i,m,n)$، لدينا: $$\Delta(i,m,n) \in \{-1, 0, 1\}$$ **اللمة الأساسية 1**: $(m,n)$ متوازن إذا وفقط إذا كانت المتتالية $(\Delta(i,m,n))_{i≥0}$ لا تحتوي على كتل من الشكل $1,0,0,\ldots,0,1$ أو $-1,0,0,\ldots,0,-1$. #### طريقة الأتمتة بالنسبة للعدد غير النسبي التربيعي $\alpha$، توجد أتمتة محدودة $M$، مدخلاتها هي تمثيل أوستروفسكي $\alpha$-الأساسي للعدد $n$ و $x$، وتقبل إذا وفقط إذا كان $x = \lfloor n\alpha \rfloor$. **النظرية الرئيسية 2**: توجد خوارزمية، بالنظر إلى عدد غير نسبي تربيعي $\alpha \in (0,1)$، تبني أتمتة محدودة، مدخلاتها هي تمثيل أوستروفسكي $\alpha$-الأساسي لأزواج $(m,n)$، وتقبل إذا وفقط إذا كانت كتلة $m \times n$ متوازنة. ### نقاط الابتكار التقني 1. **تنفيذ معايير التوازن بالأتمتة**: تحويل شروط اللمة 1 إلى صيغة منطقية من الدرجة الأولى، ثم تحويلها إلى أتمتة 2. **معالجة تمثيل زيكندورف**: معالجة ماهرة لمشكلة الأعداد السالبة، باستخدام $T(i+1,m,n) - T(i,m,n) + 1 \in \{0,1,2\}$ 3. **تنفيذ Walnut**: توفير تنفيذ كامل للكود، ينتج أتمتة بـ 15 حالة ## إعداد التجارب ### الأدوات والتنفيذ - **برنامج Walnut**: أداة متخصصة لبناء الأتمتة والتحقق منها - **تمثيل زيكندورف**: نظام التمثيل القياسي لأعداد فيبوناتشي - **تمثيل تريبوناتشي**: المستخدم لتحليل كلمات تريبوناتشي ### طرق التحقق 1. **بناء الأتمتة**: توليد أتمتة bal من خلال Walnut (15 حالة) 2. **التحقق من النظريات**: التحقق من نتائج أنسيلمو وآخرين كحالات خاصة 3. **تحليل الكثافة**: حساب خصائص توزيع الأزواج المتوازنة ## نتائج التجارب ### النتائج الرئيسية لكلمات فيبوناتشي **النتيجة 3**: الأتمتة ذات 15 حالة في الشكل 1 تحل بشكل كامل مشكلة التوازن في مستطيلات كلمات فيبوناتشي. **النتيجة 4**: التحقق من نظرية أنسيلمو وآخرين: إذا كان $\max(m,n)$ عدد فيبوناتشي، فإن مصفوفة $m \times n$ متوازنة. ### الخصائص الهيكلية **القضية 5**: بالنسبة لـ $n ≥ 2$: - $(i,j)$ متوازن إذا وفقط إذا كان $(i',j)$ متوازن، حيث $F_{n+1} < i,i' < F_{n+2}$ و $j ≥ F_{n-1}$ - $(F_{n+1}+i,j)$ متوازن إذا وفقط إذا كان $(F_{n+2}-i,j)$ متوازن **القضية 6** (نتيجة الكثافة): إذا كان $F_i < m ≤ F_{i+1}$، فإنه لجميع $n ≥ 1$ يوجد $j$، $1 ≤ j ≤ F_{i+1}$ بحيث يكون $(m,n+j)$ متوازن. ### نتائج التنوع **النظرية 8**: بالنسبة لـ $m = n = F_{3k}/2$، عدد القيم المختلفة لـ $T(i,m,n)$ على الأقل $k+1$. **النتيجة 9**: عدد القيم المختلفة لـ $T(i,F_{3n}/2,F_{3n}/2)$ هو $\Theta(n)$. ### نتائج كلمات تريبوناتشي **النظرية 10**: بافتراض $m ≤ n$: - إذا كان $m = 1$، فإن جميع مستطيلات $m \times n$ هي 2-متوازنة - إذا كان $m = 2$، توجد أتمتة بـ 77 حالة تقبل جميع $n$ التي تجعل مستطيل $m \times n$ هو 2-متوازن - إذا كان $m ≥ 3$، لا توجد $n$ تجعل مستطيل $m \times n$ هو 2-متوازن ## الأعمال ذات الصلة 1. **نظرية كلمات ستيرميان**: مبنية على الأعمال الكلاسيكية لبيرستيل وبراون وآخرين 2. **أبحاث التوازن**: توسيع أبحاث فويون حول توازن الكلمات 3. **طريقة الأتمتة**: الاستفادة من نظرية بروييير وآخرين حول المجموعات القابلة للتعرف p 4. **خصائص كلمات فيبوناتشي**: بناءً على أبحاث واسعة عن كلمات فيبوناتشي ## الخلاصة والمناقشة ### الاستنتاجات الرئيسية 1. حل كامل لمشكلة التوازن في مستطيلات كلمات فيبوناتشي، مع توفير توصيف أتمتة بـ 15 حالة 2. يمكن تعميم الطريقة على جميع كلمات ستيرميان المقابلة للأعداد غير النسبية التربيعية 3. حالة كلمات تريبوناتشي أكثر تعقيداً، وتتطلب أتمتة بـ 77 حالة لمعالجة حالة $m=2$ ### القيود 1. الطريقة تنطبق فقط على كلمات ستيرميان المقابلة للأعداد غير النسبية التربيعية 2. التوصيف الكامل لكلمات تريبوناتشي لا يزال معقداً 3. الحالات ذات الرتبة العليا (مثل تريبوناتشي مع $m≥3$) قد لا تكون لها حل ### الاتجاهات المستقبلية 1. التعميم على كلمات morphic أكثر عمومية 2. دراسة الحالات ذات الأبعاد العليا 3. تحسين عدد حالات الأتمتة ## التقييم المتعمق ### المميزات 1. **الاكتمال النظري**: توفير حل كامل لمشكلة التوازن في كلمات فيبوناتشي 2. **ابتكار الطريقة**: دمج ماهر بين نظرية الأتمتة والرياضيات التوافقية 3. **قوة التطبيق**: توفير تنفيذ خوارزمي محدد وأدوات تحقق 4. **عمق النتائج**: الكشف عن الارتباط العميق بين التوازن والخصائص النظرية للأعداد ### أوجه القصور 1. **التعقيد**: طريقة الأتمتة، رغم اكتمالها، قد لا تكون بديهية بما يكفي 2. **قيود التعميم**: تنطبق فقط على أنواع محددة من الأعداد غير النسبية 3. **التعقيد الحسابي**: لم يتم تحليل تعقيد الوقت للأتمتة بالتفصيل ### التأثير 1. **المساهمة النظرية**: توفير أفكار جديدة للبحث المتقاطع بين الرياضيات التوافقية ونظرية الأتمتة 2. **القيمة العملية**: تنفيذ Walnut يجعل النتائج قابلة للتحقق والتوسع 3. **الأهمية المنهجية**: إظهار كيفية استخدام الأتمتة لحل مشاكل توافقية معقدة ### السيناريوهات المطبقة 1. دراسة التوازن في الرياضيات التوافقية 2. تطبيقات نظرية الأتمتة 3. دراسة خصائص الأعداد غير النسبية في نظرية الأعداد 4. مشاكل القرار في تصميم الخوارزميات ## المراجع تستشهد الورقة بـ 19 مرجعاً مهماً، تشمل بشكل أساسي: - الأعمال الكلاسيكية لألوش وشاليت حول المتتاليات الآلية - أعمال بيرستيل الأساسية حول كلمات فيبوناتشي وكلمات ستيرميان - البحث الحديث لأنسيلمو وآخرين ذي الصلة - المراجع المتعلقة بنظرية الأتمتة ونظرية الأعداد --- تحقق هذه الورقة توازناً جيداً بين العمق النظري والقيمة العملية، حيث لا تحل فقط مشكلة توافقية محددة، بل تظهر أيضاً قوة طريقة الأتمتة في التعامل مع هذه الفئة من المشاكل. يجعل التنفيذ الكامل والتحقق من النتائج درجة عالية من الموثوقية والقيمة العملية.