ذكاء اصطناعي يفك لغزًا في التلوين

خذ شبكة من النقاط تربطها خطوط — وهي ما يسميه الرياضيون مخططًا (graph). والآن لوّن النقاط بحيث لا تحمل نقطتان يربطهما خط اللون نفسه أبدًا. أصغر عدد من الألوان يحقق ذلك هو العدد اللوني للمخطط. ومن الحالات الخاصة الشهيرة مبرهنة الألوان الأربعة، التي بُرهنت عام 1977، ويقول عنوانها كل شيء: «Every planar map is four colorable» (كل خريطة مستوية قابلة للتلوين بأربعة ألوان).

رهان هادفيغر عام 1943

في عام 1943، اقترح هادفيغر (Hadwiger) قاعدة شاملة لكل المخططات. صغِّر المخطط بحذف نقاط أو خطوط، وبدمج نقطتين مترابطتين في نقطة واحدة. تسمى النتيجة قاصرًا (minor). نظر هادفيغر إلى أكبر مخطط تام — تجمّع ترتبط فيه كل نقطة بكل النقاط الأخرى — يمكن الحصول عليه بهذه الطريقة، وخمّن أن عدد الألوان اللازمة لا يتجاوز أبدًا حجم هذا التجمّع.

تصفها الورقة بأنها «من أقدم المسائل وأكثرها جوهرية في نظرية المخططات». وهي مُبرهنة فقط للحالات الصغيرة: حتى تجمّعات من خمس نقاط، حيث يتبيّن أنها تكافئ مبرهنة الألوان الأربعة أو تُختزل إليها. ومن ست نقاط فصاعدًا، تبقى مفتوحة.

الاقتراب لوغاريتمًا بعد لوغاريتم

بما أن الصيغة الدقيقة تستعصي، حاول الباحثون حصر عدد الألوان بدالة ما في حجم التجمّع، تنمو بأبطأ ما يمكن. وتستعرض الورقة التقدم المحرز. فطوال عقود، كان أفضل حدّ ينمو أسرع قليلًا من التناسب — بعامل يتضمن الجذر التربيعي للوغاريتم. وقبل بضع سنوات، كسر نورين وبوستل وسونغ (Norin وPostle وSong) هذا الحاجز. ثم حسّنه ديلكور وبوستل (Delcourt وPostle) أكثر، والأهم أنهما أثبتا أنه يكفي التعامل مع مخططات صغيرة نسبيًا. ودفع ليو ولوو (Liu وLuo) العامل الإضافي نزولًا إلى لوغاريتم ثلاثي.

نقطة الوصول الطبيعية هي حدسية هادفيغر الخطية: مضاعف ثابت لحجم التجمّع يكفي دائمًا. وهذا ما يدّعي الآن سيرغي نورين (Sergey Norin) من جامعة ماكغيل في مونتريال ورافائيل شتاينر (Raphael Steiner) من المعهد الفدرالي للتكنولوجيا في زيورخ (ETH) أنهما برهناه.

الدور الذي أدّته الآلة

المؤلفان صريحان: البرهان وجده GPT-6 Astra، وهو نموذج من OpenAI، باتباع توجيهاتهما. طلبا منه أولًا برهنة حالة المخططات الكثيفة جدًا، التي اعتقدا أنها القطعة الناقصة. فنجح، كما يكتبان، «بعد بضع ساعات فقط وشيء من التشجيع». وحين طُلب منه جعل أحد الاعتمادات صريحًا، غطّى المخططات حتى حجم معيّن — لكن ليس النطاق المطلوب تمامًا. فطلبا منه فكرة أصيلة لسدّ الفجوة، فنتجت عنها خطوة «التمهيد الذاتي» (bootstrap) في البرهان النهائي. ويقولان إنه لم يبقَ تقريبًا أي من أفكار البرهان المحددة الخاصة بهما، باستثناء اقتراح واحد بشأن عمليات الانكماش (contractions).

الصياغة بشرية. وساعد نموذج آخر من OpenAI في التدقيق وقائمة المراجع. ويذكر المؤلفان أن Codex من OpenAI أنتج نسخة صورية قابلة للتحقق آليًا من البرهان كله في مساعد البراهين Lean، نُشرت على الإنترنت مع مسودة مبكرة كتبها الذكاء الاصطناعي. ويتحملان المسؤولية الكاملة عن الرياضيات.

داخل البرهان

للحجة شطران:

1. مخططات صغيرة، ألوان قليلة. بالنسبة للمخططات التي ليست أكبر كثيرًا من حدّ التجمّع، يُبيّن المؤلفان أن نحو أربعة أضعاف حجم التجمّع يكفي. ونقطة الانطلاق نتيجة لريد وسيمور (Reed وSeymour) عام 1998: صيغة مُرخاة «كسرية» من التلوين تخضع أصلًا للقاعدة الخطية بعامل اثنين. ويحوّل العمل الجديد التلوينات الكسرية إلى تلوينات حقيقية بإضافة بضعة خطوط إضافية إلى المخطط وإيجاد توافقات (matchings) ضخمة في بنية مساعدة.
2. تمهيد ذاتي. حجة ثانية توسّع في كل خطوة نطاق أحجام المخططات المشمولة بعامل أربعة أثلاث في الأُس، مقابل ثابت أكبر. وتأخذ عشر خطوات النطاق من الثلث إلى نحو 5.92، متجاوزة العتبة 5 التي يتطلبها اختزال ديلكور-بوستل. ويستخدم هذا الشطر حيلة قديمة لغيارفاش (Gyárfás)، يقول المؤلفان إنها لم تُطبَّق قط على هذه المسألة.

يصف المؤلفان البرهان بأنه مبني من أدوات معروفة — «محتوى في الغلاف المحدّب للنتائج القائمة»، لكنه ليس على حافة واضحة منه.

ما يبقى مفتوحًا

الثابت هائل: يعطي تقدير تقريبي نحو 10¹⁰⁰. ويرى المؤلفان مجالًا لخفضه إلى ما دون 10¹⁰، لكنهما يعتقدان أن بلوغ 100 مثلًا سيحتاج إلى أفكار جديدة. أما حدسية هادفيغر الدقيقة فلم تُمَس: «لم نحسم رأينا»، يكتبان. والورقة نسخة أولية؛ وستواجه 41 صفحة من الرياضيات الجديدة الآن تمحيص خبراء آخرين.