علماء الرياضيات يبدأون بترويض "مشكلة عباد الشمس"

هناك تقدم كبير في حل الفرضية البالغة من العمر 60 عامًا يلقي الضوء على كيفية بدء ظهور النظام فيها مع نمو الأنظمة العشوائية

أظهر فريق من علماء الرياضيات وعلماء الكمبيوتر أخيرًا تقدمًا في حل ، للوهلة الأولى ، مهمة بسيطة ابتليت بها الباحثين لمدة ستة عقود تقريبًا.

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

"في هذا العمل ، تظهر فكرة رياضية بطريقة جديدة ، والتي ستصبح الفكرة الرئيسية في عصرنا. وقال جيل كالاي من الجامعة العبرية في القدس "النتيجة بحد ذاتها مذهلة".

تشير فرضية عباد الشمس إلى مجموعات أو مجموعات من الكائنات. من الأسهل تخيلها باستخدام مثال لمجموعة من النقاط على المستوى xy. أولاً ، حدد عددًا ثابتًا من النقاط التي سيتم تضمينها في كل مجموعة. ثم ارسم حلقات عشوائية بحيث تتضمن كل حلقة أو مجموعة عددًا محددًا من النقاط. يمكن أن تتقاطع الحلقات ، ويمكن أن تقع بعض النقاط في عدة مجموعات ، تشبه مخطط Venn.

إذا قمت برسم الكثير من الحلقات التي تحتوي على عدد كبير من النقاط ، فسوف تتقاطع معظمها وتشبه تعقيدات الكرمات. لكن Erdös و Rado توقعا أن ينتج عن البنية المكررة أيضًا: تتقاطع ثلاث مجموعات أو أكثر مع بعضها البعض ، تاركة نفس المجموعة الفرعية من النقاط عند التقاطع ، بينما لن تتقاطع أي من هذه المجموعات مع أي مجموعات أخرى.

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



اقترح Erdös و Rado أنه كلما زاد عدد الحلقات ، ستظهر عباد الشمس هذه حتما ، إما في شكل مجموعات منفصلة ، أو في شكل مجموعات متراكبة على بعضها البعض بالطريقة المشار إليها. تعتبر فرضية عباد الشمس جزءًا من مجال أكثر عمومية في الرياضيات يطلق عليه نظرية رامزي ، والتي تدرس كيفية بدء ظهور النظام فيها مع زيادة حجم الأنظمة العشوائية.

وقال شاشار لوفت من جامعة كاليفورنيا في سان دييغو ، مؤلف مشارك للعمل الجديد الذي عمل عليه ريان ألويس من جامعة برينستون ، كيفن وو: "إذا كان لديك كائن رياضي كبير بما فيه الكفاية ، فيجب إخفاء بنية معينة فيه". و Jiapeng Zhang من جامعة هارفارد.

أراد Erdös و Rado معرفة عدد المجموعات بالضبط وما هو الحجم المطلوب لضمان عباد الشمس. لقد اتخذوا الخطوة الأولى المتواضعة نحو حل المشكلة عن طريق تحديد المعلمة w ، مع الإشارة إلى عدد النقاط في كل مجموعة. ثم أثبتوا أن الأمر يتطلب حوالي w ^من مجموعات من الحجم w لضمان أن عباد الشمس الذي يتكون من ثلاث مجموعات مضمون للظهور فيها. لذلك ، إذا كنت تريد استخدام مجموعات من 100 نقطة ، فستحتاج إلى ¹⁰⁰ إلى ¹⁰⁰ مجموعة لضمان ظهور عباد الشمس.

في الوقت نفسه ، اقترح Erdös و Rado أن عدد المجموعات التي تضمن عباد الشمس في الواقع أقل بكثير من w ^w - ^وأشبه بثابت في درجة w (على سبيل المثال ، 3 ^w أو 80 ^w أو 5 000 000 ^w ). ومع ذلك ، لم يتمكنوا من إيجاد طريقة لإثبات تخمينهم.

"قالوا إن المهمة تبدو بسيطة للغاية ، وفوجئوا أنهم لم يتمكنوا من تحقيق تقدم في ذلك" ، قال Alveys.

ولم يكونوا وحدهم. في الفترة من نتيجتها الأولى وهذا العمل الجديد ، الذي ظهر بعد 60 عامًا ، أحرز اثنان فقط من علماء الرياضيات بعض التقدم على الأقل في هذه المسألة - ثم ذهبوا تدريجياً ، واتخذوا خطوة واحدة في عام 1997 ، والثاني هذا العام .

وقال أنوب راو من جامعة واشنطن: "لقد جرب الجميع بالفعل جميع الأفكار التي يشعر بها الناس" ، وقد نشر أعمالًا إضافية تبسيط الأساليب التي تم الحصول عليها في النتيجة الجديدة. "ولم يتمكن أي شخص من تحسين خط الأساس الذي وضعه أردوس ورادو".

لكن الأدلة الجديدة حققت طفرة كبيرة.

تمكن أربعة باحثين ، بمن فيهم علماء الرياضيات وعلماء الكمبيوتر ، من القيام بذلك عن طريق تقسيم المهمة إلى سيناريوهين مختلفين. في الأولى ، أسهل ، نظروا إلى ما يمكن أن يحدث عندما تتقاطع المجموعات بشكل كبير مع بعضها البعض ، مما يجعل من السهل فهم متى يجب أن يظهر عباد الشمس هناك.

وقال لوفت "عندما يكون لديك مجموعة من العناصر التي تنتمي إلى مجموعة أكبر من المجموعات ، يمكنك استخدام هذا الهيكل" ، للبحث عن عباد الشمس.

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

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

هذا هو المكان الذي يلعب دور علوم الكمبيوتر. يحاول مؤلفان مشاركان ، Lovet و Zhang ، منذ عدة سنوات تحليل مشكلة عباد الشمس باستخدام نفس الأدوات التي يستخدمها علماء الكمبيوتر لدراسة وظائف Boolean. هذه الوظائف تؤدي عمليات على سلسلة من البتات - تلك والأصفار - وتنتج بت واحد في النهاية ، وهو ما يتوافق مع ما إذا كانت العبارة الحسابية صحيحة أم خاطئة. على سبيل المثال ، يمكن برمجة وظيفة Boolean لإرجاع 1 إذا كان واحد على الأقل من وحدات بت الإدخال هو 1 ، و 0 إذا كان أي من وحدات بت الإدخال هو 1.

قبل ثلاث سنوات ، أدرك Lovet و Zhang أنه يمكن طرح نفس السؤال حول ما إذا كانت هناك ثلاث مجموعات منفصلة بين مجموعة من مجموعات غير متقاطعة بشدة. أولاً ، قم بتعيين تسمية لكل نقطة في المجموعة: 1 إذا كانت موجودة فقط في هذه المجموعة ، و 0 في حالة أخرى. تقوم دالة Boolean بإرجاع 1 (صواب) إذا كانت كل نقطة في الإدخال تساوي 1 - أي أن كل نقطة في المجموعة موجودة بشكل حصري في هذه المجموعة ، مما يجعل هذه المجموعة غير متصلة. تشير النتيجة الحقيقية إلى وجود ظروف مناسبة لإيجاد عباد الشمس.

لإثبات هذه المراسلات بشكل صارم ، استخدم الباحثون معرفة واسعة فيما يتعلق بوظائف Boolean لمهاجمة مشكلة عباد الشمس التي كانت تفتقر إلى الموارد في السابق. لقد أثبتوا أن مجموعات (log w) ^w كافية للحصول على عباد الشمس. هذه النتيجة ليست كافية لإثبات الفرضية القائلة بأن ثابتًا معينًا في الدرجة w يكفي للحصول على عباد الشمس. لكن هذا الترتيب من حيث الحجم هو نتيجة أفضل من w التي حصل عليها Erdös و Rado ، وهو يتزامن تقريبًا مع عدد المجموعات التي تنبأ بها.

بعد نصف قرن من الإخفاقات ، يشير العمل الجديد إلى أننا سنرى قريباً حلاً كاملاً. كما أنه يحسن فهم كيفية ظهور أشكال خاصة لا محالة في الطبيعة الرياضية البرية للصدفة.