مجموعة أغطية

يؤدي حل بيليغرينو لمسألة مجموعة الغطاء رباعية الأبعاد أيضًا إلى حدود دنيا أكبر من${\displaystyle 2^{n}}$لأي بُعد أعلى، والذي تم تحسينه بشكل أكبر إلى${\displaystyle 2.2173^{n}}$بواسطة إيدل (2004) ^{[ 2 ]} ثم إلى${\displaystyle 2.2180^{n}}$بقلم تيريل (2022) . ^{[ 10 ]} في ديسمبر 2023، نشر فريق من الباحثين من ديب مايند التابعة لشركة جوجل ورقة بحثية قاموا فيها بربط نموذج لغوي كبير (LLM) بمُقيِّم، وتمكنوا من تحسين الربط بـ${\displaystyle 2.2202^{n}}$[ ^{11 ]} تم تحسين الحد لاحقًا ^إلى${\displaystyle 2.2203^{n}}$مع نموذج لغوي كبير آخر ^{[ 12 ]} و${\displaystyle (2.2203+\varepsilon )^{n}}$بواسطة Hametner–Tyrrell (2026) خطأ harvtxt: لا يوجد هدف: CITEREFHametner–Tyrrell2026 ( مساعدة ) ^{[ 13 ]} .

في عام 1984، أثبت توم براون وجو بولر ^{[ 9 ]} أن أكبر حجم ممكن لمجموعة غطاء في${\displaystyle \mathbb {Z} _{3}^{n}}$يكون${\displaystyle o(3^{n})}$مثل${\displaystyle n}$يزداد؛ وبصورة عامة، هذا يعني أن مجموعات الغطاء لها كثافة صفرية. وقد أظهر بيتر فرانكل ، ورونالد غراهام ، وفويتيك رودل ^{[ 14 ]} في عام 1987 أن نتيجة براون وبوهلر تتبع بسهولة من مبرهنة إزالة المثلث لروزا - سزيميريدي ، وتساءلوا عما إذا كان هناك ثابت ${\displaystyle c<3}$بحيث يكون ذلك صحيحًا لجميع القيم الكبيرة بما فيه الكفاية لـ ${\displaystyle n}$أي غطاء مثبت في${\displaystyle \mathbb {Z} _{3}^{n}}$حجمه في أقصى حد${\displaystyle c^{n}}$أي ما إذا كانت أي مجموعة في${\displaystyle \mathbb {Z} _{3}^{n}}$بحجم يتجاوز${\displaystyle c^{n}}$يحتوي على خط أفيني. وقد ورد هذا السؤال أيضًا في ورقة بحثية ^{[ 15 ]} نشرها نوغا ألون وموشيه دوبينر عام 1995. وفي العام نفسه، أثبت روي ميشولام ^{[ 16 ]} أن حجم مجموعة الأغطية لا يتجاوز ${\displaystyle 2\cdot 3^{n}/n}$قام مايكل بيتمان ونيتس كاتز ^{[ 17 ]} بتحسين الحد إلى${\displaystyle O(3^{n}/n^{1+\varepsilon })}$بثابت موجب${\displaystyle \varepsilon }$.

تحديد ما إذا كان من الممكن تحسين حد مشولام إلى ${\displaystyle c^{n}}$مع ${\displaystyle c<3}$اعتُبرت هذه المسألة واحدة من أكثر المسائل المفتوحة إثارةً للاهتمام في التوافقية الجمعية ونظرية رامزي لأكثر من عشرين عامًا، وقد سُلِّط الضوء عليها، على سبيل المثال، من خلال منشورات مدونة حول هذه المسألة من قِبَل الحائزين على ميدالية فيلدز، تيموثي جاورز ^{[ 18 ]} وتيرينس تاو ^{[ 19 ]} . في منشور مدونته، يشير تاو إليها على أنها "ربما مسألتي المفتوحة المفضلة"، ويقدم برهانًا مبسطًا للحد الأسي على مجموعات الأغطية، أي أنه لأي قوة أولية${\displaystyle p}$، مجموعة فرعية${\displaystyle S\subset F_{p}^{n}}$التي لا تحتوي على متتالية حسابية من حيث الطول${\displaystyle 3}$حجمه في أقصى حد${\displaystyle c_{p}^{n}}$بالنسبة للبعض${\displaystyle c_{p}<p}$[ ^{19 ]​}

تم حل تخمين مجموعة الغطاء في عام 2016 بفضل سلسلة من الإنجازات في طريقة كثيرات الحدود. وقد نشر كل من إرني كروت ، وفيسيفولود ليف، وبيتر بال باتش ورقة بحثية أولية حول المشكلة ذات الصلة بالمجموعات الجزئية الخالية من التتابع.${\displaystyle \mathbb {Z} _{4}^{n}}$وقد استخدم جوردان إيلينبيرغ وديون غيسويت هذه الطريقة لإثبات حد أعلى لـ${\displaystyle 2.756^{n}}$في مسألة مجموعة الأغطية. ^{[ 5 ] [ 6 ] [ 20 ] [ 21 ] [ 22 ]} في عام 2019، قام كل من ساندر داهمن ويوهانس هولز وروب لويس بصياغة برهان هذا الحد الأعلى في برنامج إثبات نظرية لين . ^{[ 23 ]}

حتى مارس 2023، لم يطرأ أي تحسن أُسّي على الحد الأعلى الذي وضعه إلينبيرغ وجيسفيت. وقد بيّن جيانغ أنه من خلال الفحص الدقيق للمعاملات متعددة الحدود التي تظهر في برهان إلينبيرغ وجيسفيت، يمكن الحصول على عامل قدره${\displaystyle {\sqrt {n}}}$[ ^{24 ] يحدث} هذا التوفير للأسباب نفسها التي تجعل هناك${\displaystyle {1/{\sqrt {n}}}}$ضع في الاعتبار معامل ذي الحدين المركزي .

يمكن أيضًا استخدام حل مشكلة مجموعة الغطاء لإثبات شكل جزئي من حدسية عباد الشمس ، أي أنه إذا كانت عائلة من المجموعات الجزئية من${\displaystyle n}$إذا لم يكن للمجموعة المكونة من n عنصرًا ثلاث مجموعات جزئية تكون جميع تقاطعاتها متساوية، فإن عدد المجموعات الجزئية في هذه المجموعة يكون على الأكثر${\displaystyle c^{n}}$لثابت${\displaystyle c<2}$[ ^{5 ] [ 26 ] [ 6 ] [ 27 ]​}

تشير الحدود العليا لمجموعات الغطاء إلى حدود دنيا لأنواع معينة من الخوارزميات لضرب المصفوفات . ^{[ 28 ]}

يُعدّ مخطط الألعاب مخططًا منتظمًا بقوة، يتكون من 729 رأسًا. ينتمي كل ضلع إلى مثلث فريد، لذا فهو مخطط خطي محليًا ، وهو أكبر مخطط خطي محليًا منتظم بقوة معروف. يعتمد بناؤه على مجموعة الغطاء الفريدة المكونة من 56 نقطة في الفضاء الإسقاطي الثلاثي خماسي الأبعاد (بدلاً من الفضاء الأفيني الذي تُعرَّف فيه مجموعات الغطاء عادةً). ^{[ 29 ]}