Balanced Fibonacci word rectangles, and beyond

1. بيان المشكلة

يستقصي البحث خصائص التوازن للمصفوفات الفرعية المستطيلة (مستطيلات الكلمات) المستمدة من متتاليات لانهائية.

• السياق: بالنظر إلى متتالية لانهائية $(a_i)_{i \ge 0}$ فوق المجموعة $\{0, 1\}$، تُعرف مصفوفة لانهائية $A$ حيث $A_{k,\ell} = a_{k+\ell}$. تمثل المصفوفة الفرعية $A(i, m, n)$ بأبعاد $m \times n$ والبدء من المؤشر $i$ "نافذة" للمتتالية.
• تعريف التوازن: يُعتبر الزوج من الأبعاد $(m, n)$ متوازناً إذا كان مجموع المدخلات $T(i, m, n)$ عبر جميع مواضع البداية الممكنة $i$ يأخذ قيمتين متمايزتين على الأكثر.
• السؤال الجوهري: بالنسبة لكلمات محددة (فيبوناتشي، تريبوناتشي، ثيو-مورس)، حدد بالضبط أي أزواج الأعداد الطبيعية $(m, n)$ تؤدي إلى مستطيلات متوازنة.
• الخلفية: أثبتت أعمال سابقة لـ Anselmo وآخرون أنه إذا كان $\max(m, n)$ هو عدد فيبوناتشي، فإن مستطيلات فيبوناتشي ذات الأبعاد $m \times n$ تكون متوازنة. ومع ذلك، فإن هذا الشرط كافٍ ولكنه ليس ضرورياً (على سبيل المثال، الزوج $(4,3)$ متوازن). يهدف هذا البحث إلى تقديم توصيف كامل.

2. المنهجية

يستخدم المؤلفون نظرية الأوتوماتا (الآلات ذاتية التشغيل) والقابلية للتقرير المنطقي كمنهجيتهم الأساسية، مستعينين بالأداة البرمجية Walnut.

• بناء الأوتوماتا المحدودة:

  • بالنسبة لـ كلمة فيبوناتشي (كلمة ستورميان تقابل العدد غير النسبي التربيعي $\gamma = (3-\sqrt{5})/2$)، يستخدم المؤلفون نظام الترقيم أوسطري $\alpha$ (تحديداً تمثيل زيكندورف).
  • يضعون معياراً (Lemma 1) ينص على أن المستطيلات تكون متوازنة إذا وفقط إذا كانت متتالية الفروقات $\Delta(i, m, n) = T(i+1, m, n) - T(i, m, n)$ لا تحتوي على أنماط محددة (كتل من $1, 0, \dots, 0, 1$ أو $-1, 0, \dots, 0, -1$).
  • بما أن الشرط $x = \lfloor n\alpha \rfloor$ يمكن التعبير عنه في المنطق من الدرجة الأولى للأعداد غير النسبية التربيعية، يمكن ترجمة معيار التوازن إلى صيغة من الدرجة الأولى.
  • باستخدام Walnut، يتم تحويل هذه الصيغة إلى أوتوماتا محدودة تقبل الأزواج $(m, n)$ (الممثلة بصيغة زيكندورف) إذا وفقط إذا كانت متوازنة.

• التعميم على كلمات أخرى:

  • كلمة تريبوناتشي: يكيف المؤلفون النهج باستخدام نظام ترقيم تريبوناتشي. يقومون ببناء أوتوماتا لحساب تكرارات الرموز $0, 1, 2$ في المستطيلات الفرعية والتحقق من شرط التوازن الثنائي (2-balance).
  • كلمة ثيو-مورس: نظراً للتماثل المحدد لمتتالية ثيو-مورس ($t_{2k} + t_{2k+1} = 1$)، يستخدم المؤلفون حجة التزاوج لتحديد حدود المجاميع. يقومون بتنفيذ ذلك باستخدام تمثيل الأساس (-2) في Walnut للتعامل مع الفروقات السالبة بشكل طبيعي، ومن ثم تحويل النتيجة في النهاية إلى أوتوماتا ذات أساس 2 قياسي.

• التمثيلات الخطية: لإثبات نتائج الكثافة والتنوع (Theorem 8)، يستخدم المؤلفون التمثيلات الخطية (ثلاثيات من المصفوفات/المتجهات) لحساب القيم الدقيقة لـ $T(i, m, n)$ لمتتاليات محددة من $m$ و $n$، والتحقق من المتطابقات عبر برنامج Maple.

3. المساهمات والنتائج الرئيسية

أ. كلمة فيبوناتشي

• التوصيف الكامل: يبني المؤلفون أوتوماتا محدودة مكونة من 15 حالة (الشكل 1) تقبل تماماً الأزواج المتوازنة $(m, n)$ لكلمة فيبوناتشي. يثبت هذا أن مجموعة الأزواج المتوازنة هي لغة منتظمة في نظام ترقيم زيكندورف.
• المعايير القابلة للقراءة البشرية: يستنتجون Theorem 7، وهو توصيف غير معتمد على الأوتوماتا للأزواج المتوازنة بناءً على توسيعات زيكندورف لـ $m$ و $n$ (يتضمن زوجية المؤشرات والأحجام النسبية لمكونات فيبوناتشي).
• استعادة النتائج السابقة: تتحقق الأوتوماتا تلقائياً من نظرية Anselmo وآخرين (أننا إذا كان $\max(m, n)$ هو عدد فيبوناتشي، فإن الزوج يكون متوازناً).
• الكثافة والتنوع:
  • Proposition 5: يثبت خصائص الدورية والتماثل للأزواج المتوازنة ضمن فترات فيبوناتشي.
  • Proposition 6: يثبت أنه لأي $m$، يوجد $j \le F_{i+1}$ بحيث يكون $(m, n+j)$ متوازناً، مما يضع حداً أدنى لكثافة $n$ المتوازنة.
  • Theorem 8 & Corollary 9: يثبت أنه عندما يكون $m=n=F_{3k/2}$، فإن عدد القيم المتمايزة لـ $T(i, m, n)$ ينمو خطياً مع $k$ (تحديداً $\Theta(k)$)، مما يوضح أن عدد المجاميع المتمايزة ليس محدوداً بثابت لجميع قيم $m, n$.

ب. كلمة تريبوناتشي

• Theorem 10: يحدد المستطيلات المتوازنة ثنائياً (2-balanced) لكلمة تريبوناتشي (التي تستخدم الرموز $\{0, 1, 2\}$):
  • إذا كان $m=1$، فجميع قيم $n$ متوازنة.
  • إذا كان $m=2$، توجد أوتوماتا مكونة من 77 حالة تقبل قيم $n$ محددة.
  • إذا كان $m \ge 3$، لا يوجد أي $n$ يجعل المستطيلات متوازنة ثنائياً.
• يتضمن الإثبات لـ $m \ge 3$ بناء أمثلة مضادة محددة حيث يختلف عدد الرمز '2' بمقدار 3 على الأقل بين مستطيلين.

ج. كلمة ثيو-مورس

• Theorem 11: يثبت أنه لأي مستطيل $m \times n$، فإن التوازن (الانحراف عن متوسط المجموع $mn/2$) محصور في 4. وتحديداً،$|2|A(i, m, n)|_1 - mn| \le 4$.
• Theorem 12: يبني أوتوماتا مكونة من 92 حالة (في الأساس 2) التي تحدد قيمة التوازن الدقيقة (1، 2، 3، أو 4) لأي مدخل $(m, n)$.
  • ملاحظة: كانت هذه العملية ضخمة، حيث استغرقت 12834 ثانية من المعالجة و100 جيجابايت من ذاكرة الوصول العشوائي (RAM)، مع وصول أوتوماتا وسيطة إلى أكثر من 32 مليون حالة.
• Theorem 14: يثبت أنه بالنسبة لـ $m, n \ge 3$، يكون التوازن تحديداً 3 إذا وفقط إذا كان كل من $m$ و $n$ فرديين.

4. الأهمية

• النظرية العددية الخوارزمية: يوضح البحث قوة إجراءات القرار القائمة على الأوتوماتا (تحديداً باستخدام Walnut) لحل مشكلات تركيبية معقدة على الكلمات اللانهائية. ويظهر كيف يمكن اختزال خصائص الكلمات الستورمانية وغيرها من الكلمات المورفية إلى وجود مسارات في الأوتوماتا المحدودة.
• التعميم: يتجاوز البحث الحالة الخاصة لأعداد فيبوناتشي إلى إطار عام قابل للتطبيق على أي كلمة ستورمانية تقابل عدداً غير نسبي تربيعي، ويمتد المفهوم إلى الكلمات غير الثنائية (تريبوناتشي) وتعريفات مختلفة للتوازن (ثيو-مورس).
• دحض الحدس: تظهر النتائج أنه بينما تضمن بعض الشروط "الجيدة" (مثل أبعاد فيبوناتشي) التوازن، فإن المجموعة الكاملة للأزواج المتوازنة معقدة وتتطلب أوتوماتا لوصفها بدقة. علاوة على ذلك، فإن عدد المجاميع المتمايزة يمكن أن ينمو خطياً مع الأبعاد، مما يناقض الفكرة القائلة بأن هذه المجاميع تكون دائماً متجمعة بإحكام.
• التحقق مفتوح المصدر: جميع البراهين بنائية وتم التحقق منها عبر الكود (Walnut و Maple)، وهي متاحة للجمهور لضمان قابلية التكرار والسماح بمزيد من الاستكشاف لمشكلات مماثلة.

باختصار، يقدم البحث حلاً خوارزمياً نهائياً لمشكلة "المستطيل المتوازن" لعدة كلمات لانهائية أساسية، مستفيداً من الارتباط العميق بين القابلية للتقرير المنطقي، وأنظمة الترقيم، والأوتوماتا المحدودة.