🤖 AI

Improved lower bounds for the Shannon capacity of odd cycles

تقدم هذه الورقة حدوداً دنيا محسنة لسعة شانون للدورات الفردية $C_7$ و $C_{11}$ و $C_{13}$ و $C_{15}$ من خلال إنشاء مجموعات مستقلة أكبر في نواتجها القوية عبر التعاون التكراري مع نموذج لغوي كبير.

المؤلفون الأصليون: Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, Daniel Reichman

نُشر 2026-07-31

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, Daniel Reichman

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

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

لمعرفة ذلك، يستخدم الرياضيون أداة تسمى "الرسم البياني" (graph)، وهو مجرد كلمة منمقة لوصف خريطة من النقاط المتصلة بخطوط. فكر في النقاط على أنها رسائل مختلفة يمكنك إرسالها، والخطوط على أنها أوجه التشابه المربكة بينها. إذا كانت نقطتان متصلتين، فهذا يعني أن هاتين الرسالتين قد تختلطان بسبب الضجيج. الهدف هو اختيار مجموعة من النقاط (الرسائل) التي ليست متصلة ببعضها البعض، لكي تكون جميعها متميزة وآمنة من الارتباك. وكلما كبرت هذه المجموعة، زادت كمية المعلومات التي يمكنك إرسالها.

الجزء الصعب هو أنه يمكننا دمج هذه الخرائط معاً لإنشاء خرائط أكبر وأكثر تعقيداً. ومن خلال تكديس هذه الخرائط فوق بعضها، يمكننا أحياناً العثور على مجموعات ضخمة من الرسائل الآمنة لم نكن نراها من قبل. بالنسبة لبعض الأشكال، مثل الحلقات ذات الأعداد الزوجية، نعرف الإجابة تماماً. ولكن بالنسبة للحلقات ذات الأعداد الفردية (مثل الأشكال ذات الـ 7 أو 11 أو 13 أو 15 جانباً)، ظلت الإجابة لغزاً مستعصياً لعقود. الأمر يشبه محاولة العثور على أكبر عدد من البقع غير المتلامسة على سوار ملتوي ومعقود، ولم يتمكن أحد بعد من العثور على أفضل ترتيب مطلق.

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

كانت النتائج ناجحة بشكل مفاجئ. فقد اكتشف الفريق، بالتعاون مع الذكاء الاصطناعي، مجموعات جديدة وأكبر من الرسائل الآمنة للحلقات ذات الـ 7، و11، و13، و15 جانباً. بالنسبة للحلقة ذات الـ 7 جوانب، وجدوا 134,753 رسالة آمنة، وهو رقم أكبر من الرقم القياسي السابق البالغ 367. وبالنسبة للحلقة ذات الـ 11 جانباً، وجدوا 21,909 رسالة. وللحلقة ذات الـ 13 جانباً، وجدوا 62,530، وللحلقة ذات الـ 15 جانباً، وجدوا رقماً هائلاً قدره 8,076,974.

قد تبدو هذه الأرقام وكأنها مجرد قائمة من الأرقام، لكنها تمثل تحسناً حقيقياً في فهمنا لكمية المعلومات التي يمكن إرسالها دون أخطاء. فمن خلال العثور على هذه المجموعات الأكبر، أثبت الباحثون أن الحد الأقصى للسرعة لإرسال الرسائل المثالية عبر هذه القنوات المليئة بالضجيج أعلى قليلاً مما كنا نعتقد سابقاً. فعلى سبيل المثال، أصبح من المعروف الآن أن الحد الأقصى للسرعة للحلقة ذات الـ 7 جوانب هو أكبر من 3.258020، بينما كان يُعرف سابقاً أنه أكبر من 3.257865.

ما يجعل هذه القصة مثيرة للاهتمام ليس فقط الأرقام، بل كيفية العثور عليها. فقد جرب الباحثون استخدام طرق البحث التقليدية في الحاسوب، مثل "التلدين المحاكى" (simulated annealing) - وهو ما يشبه هز صندوق من قطع الأحجية حتى تتناسب مع بعضها - لكن تلك الطرق فشلت في العثور على هذه المجموعات الجديدة والأكبر. كما أن خوارزميات البحث المحلي المبنية على الذكاء الاصطناعي لم تستطع الوصول إلى هذه الآفاق الجديدة. لم يكن الأمر ممكناً إلا من خلال حوار متبادل مع الذكاء الاصطناعي، حيث قدم الباحثون تلميحات واقترح الذكاء الاصطناعي تعديلات إبداعية على الأنماط الموجودة.

لا تدعي هذه الورقة البحثية أنها حلت لغز "سعة شانون" لجميع الحلقات الفردية؛ فهذه المشكلة لا تزال قائمة. ومع ذلك، فهي توضح أنه من خلال الجمع بين الحدس الرياضي البشري وقوة مطابقة الأنماط للذكاء الاصطناعي الحديث، يمكننا دفع حدود ما نعرفه. لقد تحقق الباحثون من صحة كل مجموعة رسائل جديدة وجدوها لضمان دقتها رياضياً، مما أثبت أن الذكاء الاصطناعي لم يقم بمجرد التخمين، بل وجد بالفعل حلولاً صالحة وأكبر مما فات الخبراء البشر. وهذا يشير إلى أن مستقبل حل الألغاز الرياضية المعقدة قد يتضمن فريقاً من البشر والذكاء الاصطناعي يعملان معاً، حيث يعمل الذكاء الاصطناعي كشرارة إبداعية تساعدنا على رؤية الخطوة التالية في رقصة الأرقام.

ملخص تقني: تحسين الحدود الدنيا لسعة شانون للدورات الفردية

بيان المشكلة
تقيس سعة شانون $\Theta(G)$ لـرسم بياني $G$ أقصى معدل اتصال خالي من الخطأ عبر قناة مشوبةة معرفة بـ $G$ . وتُعرف بـ $\Theta(G) = \sup_{d \in \mathbb{N}} \alpha(G^d)^{1/d}$ ، حيث $\alpha(G^d)$ هو عدد الاستقلال (independence number) للمنتج القوي رقم $d$ للرسم البياني $G$ . وبينما $\Theta(C_p) = p/2$ للدورات الزوجية و $\Theta(C_5) = \sqrt{5}$ ، تظل قيم الدورات الفردية $C_{2r+1}$ عندما يكون $r > 2$ غير معروفة. ويعد تحديد $\Theta(C_7)$ مسألة مفتوحة وصعبة للغاية. إن النهج القياسي لتحديد الحدود الدنيا يتضمن بناء مجموعات مستقلة كبيرة في المنتجات القوية $C_k^d$ لتعظيم الكمية $\alpha(C_k^d)^{1/d}$ .

المنهجية
يستخدم المؤلفون تفاعلاً تكرارياً مع نموذج لغوي كبير (LLM)، وتحديداً ChatGPT-5.6 Sol Pro، لاكتشاف بناءات توافقية صريحة للمجموعات المستقلة. تختلف المنهجية عن عمليات البحث الاستدلالي التقليدية (مثل التلدين المحاكي أو خوارزميات البحث المحلي) التي لاحظ المؤلفون أنها فشلت في الوصول إلى الحدود المذكورة رغم المحاولات المكثفة.

تضمنت العملية:

التلقين (Prompting): زود المؤلفون النموذج اللغوي الكبير بمعاملات محددة: طول الدورة ( $k$ )، بُعد المنتج ( $d$ )، أفضل بناء موجود حالياً، والهدف المطلوب لزيادة الحجم.
التوليد والتنفيذ: قام النموذج بتوليد برامج بحث، ونفذها داخل بيئته، وأعاد مجموعات مستقلة مرشحة.
التحسين التكراري: انخرط المؤلفون في مطالبات متابعة لدفع حجم المجموعة إلى ما وراء النتائج الأولية التي وجدها النموذج.
التحقق: تم التحقق من جميع المجموعات المنشأة بدقة من قبل المؤلفين لضمان أنها تشكل مجموعات مستقلة صالحة (أي لا يختلف أي متجهين عن بعضهما بمقدار 1 أو أقل في كل إحداثي بمقدار modulo $k$ ).

المساهمات والنتائج الرئيسية
يقدم البحث حدوداً دنيا محسنة لسعة شانون لأربع دورات فردية محددة من خلال بناء مجموعات مستقلة أكبر في منتجاتها القوية:

$C_7$ (دورة طول 7): أنشأ المؤلفون مجموعة مستقلة بحجم 134,753 في المنتج القوي العاشر $C_7^{10}$ . وهذا يحسن الحد الأدنى السابق البالغ $367^{1/5}$ (من مجموعة بحجم 367 في $C_7^5$ ).
- الحد الأدنى الجديد: $\Theta(C_7) \geq 134753^{1/10} > 3.258020$ (سابقاً $> 3.257865$ ).
- استراتيجية البناء: تم اشتقاق المجموعة من المجموعة المعروفة ذات الحجم 367 المنسوبة لـ Polak وSchrijer. قام المؤلفون بحذف متجهات محددة من $R$ لتشكيل مجموعة فرعية $B$ ، ثم أنشأوا المجموعة النهائية $I$ باستخدام المنتج الديكارتي $B \times B$ مع إضافة متجهات أخرى مشتقة من $R وتحويلات محددة.
$C_{11}$ (دورة طول 11): تم العثور على مجموعة مستقلة بحجم 21,909 في $C_{11}^6$ .
- الحد الأدنى الجديد: $\Theta(C_{11}) \geq 21909^{1/6} > 5.289773$ (سابقاً $148^{1/3} > 5.289572$ ).
- استراتيجية البناء: بدءاً من المجموعة ذات الحجم 148 في $C_{11}^3$ ، حدد المؤلفون مجموعات فرعية معينة ( $DL, DR, BL, BR$ ) ومتجهات مساعدة ( $F_A, F_B, \dots$ ) لبناء المجموعة في المنتج السادس.
$C_{13}$ (دورة طول 13): تم العثور على مجموعة مستقلة بحجم 62,530 في $C_{13}^6$ .
- الحد الأدنى الجديد: $\Theta(C_{13}) \geq 62530^{1/6} > 6.300109$ (سابقاً $247^{1/3} > 6.274305$ ).
- استراتيجية البناء: نفذ النموذج اللغوي بحثاً محلياً عشوائياً على رسم بياني مساعد $G_A$ (بـ 134 رأساً) لإيجاد مجموعة مستقلة كبيرة $S$ مكونة من 370 متجهاً في $\mathbb{Z}_{13}^4$ . تم تعريف المجموعة النهائية $I$ كـ $\{x \in \mathbb{Z}_{13}^6 : Ax \in S\}$ .
$C_{15}$ (دورة طول 15): تم العثور على مجموعة مستقلة بحجم 8,076,974 في $C_{15}^8$ .
- الحد الأدنى الجديد: $\Theta(C_{15}) \geq 8076974^{1/8} > 7.301399$ (سابقاً $2842^{1/4} > 7.301397$ ).
- استراتيجية البناء: بدءاً من المجموعة ذات الحجم 2842 في $C_{15}^4$ ، حذف المؤلفون متجهات محددة وأضافوا أخرى لتشكيل مجموعة أساس $R$ . تم تشكيل المجموعة النهائية من $B \times B$ (حيث $B \subset R$ ) مضافاً إليها متجهات محددة بواسطة جداول البحث ( $W_0, W_1$ ) بناءً على شروط التجاور.

بالإضافة إلى ذلك، يبلغ البحث عن حدود دنيا محسنة لأعداد الاستقلال لعدة منتجات قوية فردية لا تحسن مباشرة حدود سعة شانون (على سبيل المثال، $\alpha(C_{11}^4) \geq 766$ ، $\alpha(C_{15}^3) \geq 383$ ).

الأهمية والادعاءات
يزعم البحث أن هذه النتائج تمثل تحسينات متواضعة للحدود الدنيا المعروفة لـ $\Theta(C_7)$ و $\Theta(C_{11})$ و $\Theta(C_{15})$ ، وتحسيناً أكثر أهمية لـ $\Theta(C_{13})$ .

تكمن الأهمية الأساسية للعمل في المنهجية:

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

يظل المؤلفون متواضعين فيما يتعلق بحجم التحسينات العددية (على سبيل المثال، الزيادة في $\Theta(C_{15})$ هي في المرتبة السادسة بعد الفاصلة العشرية) لكنهم يؤكدون على حداثة عملية الاكتشاف. جميع البناءات والأكواد متاحة في مستودع عام.

أبحاث مشابهة