سقوط حدسية زهرة دوّار الشمس

خذ الأعداد من 1 إلى n وانظر إلى كل طرق اختيار بعضها: هناك 2ⁿ مجموعة جزئية من هذا النوع. والآن اختر بضع مجموعات جزئية تشترك في الجزء المشترك نفسه تمامًا، ولا شيء غيره. يسمّي الرياضيون هذا زهرة دوّار الشمس: الجزء المشترك هو النواة، وما يتبقى من كل مجموعة بتلةٌ لا تلمس أي بتلة أخرى.

زهور دوّار الشمس أداة أساسية في التوافقيات. وتعدّد الورقة صلاتها بحدود بعض الدوائر المنطقية، وبمسألة «مجموعة الغطاء» (cap set)، وبضرب المصفوفات السريع، وبنظرية المعلومات.

سؤال من عام 1970

يعود السؤال الأكثر طبيعية عنها، بحسب المؤلفين، إلى ورقة لبول إردوش عام 1970. ما أكبر حجم ممكن لمجموعة من المجموعات الجزئية لـ{1, …, n} إذا كانت لا تشكّل أيُّ k من مجموعاتها زهرة دوّار شمس؟

في السبعينيات، خمّن إردوش وإندره سيميريدي أن مجموعة كهذه يجب أن تكون أصغر أُسّيًا من المجموعات الجزئية الممكنة البالغ عددها 2ⁿ: على الأكثر cⁿ، لعدد ما c أصغر تمامًا من 2.

وطوال عقود، لم تقتطع أفضل الحدود إلا قليلًا، ولم يكن ذلك كافيًا قط لإنزال الأساس إلى ما دون 2. ولم تُحسم إلا حالة البتلات الثلاث (k = 3)، عام 2016، بفضل الاختراق في مسألة مجموعة الغطاء واختزال يعود إلى Alon وShpilka وUmans.

الحدّ

يبرهن Matija Bucić وFankang He (جامعة فيينا) وHyunwoo Lee (معهد KAIST ومعهد العلوم الأساسية، كوريا الجنوبية) الحدسية لكل k ≥ 3. ومبرهنتهم الرئيسية: مجموعة لا تحوي زهرة دوّار شمس ذات k بتلة لها على الأكثر

3 · (2 − 1/(16k³))ⁿ

عنصرًا. يقع الأساس تحت 2 بقليل، لكنه عدد ثابت أصغر من 2، وهذا بالضبط ما طلبه إردوش وسيميريدي. ويُظهر بناء يعود إلى عام 1997 أن القيمة الحقيقية، لقيم k الكبيرة، لا يمكن أن تكون أدنى بكثير.

من المجموعات إلى المتجهات

يمرّ البرهان عبر صيغة للمسألة باستخدام المتجهات. قسّم الأعداد إلى n كتلة من D عنصرًا، واختر عنصرًا واحدًا من كل كتلة: كل اختيار متجه. وتشكّل عدة متجهات زهرة دوّار شمس حين تكون مكوّناتها، في كل موضع، إما متساوية كلها أو مختلفة كلها.

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

وجدته آلة، وتحقّقت منه أخرى

تصريح الورقة بشأن الذكاء الاصطناعي مباشر على نحو غير معتاد. فبرهان المبرهنة 2 وجده ChatGPT 6 Astra Pro، بعد نقاش قصير بدأ بطلب تعميم الحجة المعروفة للبتلات الثلاث. وكان المؤلفون بحاجة إلى هذه الخطوة لهدف آخر: صيغة مستحثّة (induced) لمسألة في نظرية البيان طرحها سيميريدي، يعلنون عنها في مذكرة لاحقة.

كتب النموذج برهانه بلغة «رتبة الشرائح» (slice rank). وأعاد المؤلفون كتابته بلغة طريقة كثيرات الحدود، التي يرونها أيسر على القرّاء. ويصرّحون بأنهم تحققوا من كل نتيجة ويتحمّلون المسؤولية كاملة، وبأن البرهان تم التحقق منه في Lean 4.35، وهو برنامج للتحقق من البراهين، على أن يُنشر التحقق في مستودع Palomar.

ما الذي لا تحسمه

لم يحاول المؤلفون تحسين الأساس. فبالنسبة إلى البتلات الثلاث، لا يتفوق على حدّ Naslund وSawin لعام 2017، البالغ نحو 1.89. أما المسألة الشقيقة الأقوى، حدسية إردوش–رادو لزهرة دوّار الشمس، فلا تزال مفتوحة: إذ لا تزال حدودهم تعتمد اعتمادًا كبيرًا على حجم الكتلة D، وهو بالضبط ما تحظره تلك المسألة.