من خلال ترجمة فرضية كيلر إلى لغة بحث بالرسوم البيانية مفهومة بالكمبيوتر ، تمكن الباحثون أخيرًا من حل مشكلة تغطية المساحات بالبلاط.
اكتشف فريق من علماء الرياضيات أخيرًا فرضية كيلر - لكن ليس بمفردهم. بدلاً من ذلك ، قاموا بتدريب أسطول كامل من أجهزة الكمبيوتر ، وقاموا بحلها.
ترتبط فرضية كيلر ، التي طرحها أوت هاينريش كيلر منذ 90 عامًا ، بمهمة تغطية المساحات ببلاط متطابق. تجادل أنه إذا قمت بتمهيد مساحة ثنائية الأبعاد ببلاطات مربعة ثنائية الأبعاد ، فسيتعين على اثنين منهم على الأقل لمس الجوانب بالكامل ، وليس جزئيًا. تقدم الفرضية نفس التنبؤ لأي أبعاد - أي عندما يتم ملء مساحة 12 بعدًا بـ "مربعات" ذات 12 بعدًا ، يجب أن يكون لاثنين منها على الأقل وجه مشترك.
لسنوات ، حارب علماء الرياضيات حول هذه الفرضية ، وأثبتوا حقيقتها في بعض الأبعاد وخطأها بالنسبة لأخرى. وبحلول الخريف الماضي ، ظل السؤال دون حل إلا بالنسبة للفضاء ذي الأبعاد السبعة.
لكن الأدلة الجديدة التي تم إنشاؤها بواسطة الكمبيوتر حلت هذه المشكلة أيضًا. الدليل ، الذي نُشر في أكتوبر الماضي ، هو أحد أحدث الأمثلة على مزيج العبقرية البشرية وقوة الحوسبة المطلقة للإجابة على الأسئلة الأكثر إثارة في الرياضيات.
مؤلفي العمل الجديد، جوشوا Breukensik ستانفورد، مارين Hijul و جون ماكي من جامعة كارنيجي ميلون، و ديفيد نارفيز من معهد روتشستر للتكنولوجيا، حل هذه المشكلة باستخدام 40 أجهزة الكمبيوتر. في 30 دقيقة فقط ، أعطت الآلات إجابة أحادية المقطع: نعم ، في سبعة أبعاد ، الفرضية صحيحة. وليس علينا حتى أن نأخذ هذا الاستنتاج على أساس الإيمان.
مرفق بالإجابة دليل طويل يشرح حقيقته. الدليل طويل جدًا بحيث يتعذر على الإنسان فهمه ، لكن يمكن لبرنامج كمبيوتر آخر التحقق منه.
بعبارة أخرى ، حتى لو لم نعرف بالضبط ما فعلته أجهزة الكمبيوتر لإثبات فرضية كيلر ، يمكننا على الأقل التأكد من أنها فعلت ذلك بشكل صحيح.
البعد السابع الغامض
من السهل أن نرى أن تخمين كيلر صحيح في بعدين. خذ قطعة من الورق وحاول تغطيتها بمربعات متساوية بدون فجوات أو تداخل. قريبًا ستدرك أنه لا يمكنك القيام بذلك إلا إذا كان لمربعين على الأقل نفس الجانب. إذا كانت لديك مكعبات في متناول اليد ، فسيكون من السهل عليك التحقق من صحة الفرضية بالنسبة للبعد الثالث. في عام 1930 ، اقترح كيلر أن هذه العلاقة تعمل مع جميع الأبعاد والبلاط المقابل لها.
دعمت النتائج المبكرة تنبؤات كيلر. في عام 1940 ، أثبت أوسكار بيرون أن الفرضية كانت صحيحة للقياسات من واحد إلى ستة. ومع ذلك، وبعد مرور أكثر من 50 عاما، ووجد جيل جديد من الرياضيين وبالدليل الأول لهذه الفرضية: في عام 1992، جيفري لاغارياس و بيتر شورأثبت أن الفرضية لا تعمل في البعد العاشر.
تتوقع فرضية كيلر أنه عند ملء فراغ بأي بُعد ، يجب أن يلمس بلاطتان على الأقل الجوانب تمامًا.
عند ملء مساحة ثنائية الأبعاد ، يكون للعديد من البلاط جوانب مشتركة (خطوط زرقاء).
عند ملء مساحة ثلاثية الأبعاد ، يكون للعديد من المكعبات وجوه مشتركة (زرقاء).
من السهل إظهار أنه إذا فشلت الفرضية في بعض الأبعاد ، فإنها لا تصمد في جميع الأبعاد العليا. لذلك ، بعد عمل Lagarias و Shor ، يبقى فقط حل المشكلة للأبعاد السابع والثامن والتاسع. في عام 2002 ، أثبت ماكي أن فرضية كيلر كانت خاطئة بالنسبة للبعد الثامن (وبالتالي تسعة).
بقي البعد السابع فقط مفتوحًا - فقد كان إما البعد الأكبر ، الذي تكون هذه الفرضية صحيحة فيه ، أو الأصغر ، حيث تكون الفرضية غير صحيحة.
قال خيول: "لا أحد يعرف بالضبط ما يجري هناك".
الربط بين النقاط
بينما كافح علماء الرياضيات مع هذه المشكلة لعدة عقود ، تغيرت أساليبهم تدريجياً. عمل بيرون على الأبعاد الستة الأولى باستخدام القلم والورق فقط ، ولكن بحلول التسعينيات ، اكتشف الباحثون كيفية ترجمة فرضية كيلر إلى شكل مختلف تمامًا - مما يسمح لهم باستخدام أجهزة الكمبيوتر لحلها.
الصياغة الأصلية لتخمين كيلر تتعلق بالفضاء المستمر السلس. في مثل هذه المساحة ، هناك عدد لا حصر له من الطرق لوضع عدد لا حصر له من البلاط. لكن أجهزة الكمبيوتر ليست جيدة في حل المشكلات مع عدد لا حصر له من الخيارات - للتعامل معها ، فهي بحاجة إلى كائنات منفصلة ومحدودة.
مارين حجول من جامعة كارنيجي ميلون
في عام 1990 ، توصل كل من Kereszteli Korradi و Sandor Shabo إلى جسم منفصل مناسب. لقد أظهروا أنه يمكن طرح الأسئلة التي تعادل فرضية كيلر حول هذا الكائن. وإذا أثبتت شيئًا متعلقًا بهذه الأشياء ، فسيتم إثبات فرضية كيلر. هذا قلل من مسألة اللانهاية إلى مسألة حسابية أقل تعقيدًا بأرقام متعددة.
وإليك كيف يعمل.
لنفترض أنك تريد التعامل مع فرضية كيلر في بعدين. توصل كورادي وشابو إلى طريقة لهذا باستخدام بناء هيكل أطلقوا عليه اسم الرسم البياني كيلر.
بادئ ذي بدء ، تخيل أن هناك 16 حجرًا على الطاولة ، وكلها لها حافة علوية بنقطتين (تشير النقطتان إلى مساحة ثنائية الأبعاد ، ولماذا يوجد 16 مكعبًا - سنرى بعد ذلك بقليل). يتم تدوير جميع المكعبات بنفس الطريقة ، بحيث توجد نقطتان متماثلتان للجميع. لوِّن كل نقطة بأربعة ألوان: أحمر أو أخضر أو أبيض أو أسود.
النقاط الموجودة على أحد المكعبات لا تغير الأماكن - دع أحدها يشير إلى إحداثي س ، والآخر - ص. بعد تلوين المكعبات ، نبدأ في رسم خطوط ، أو حواف ، بين أزواج من المكعبات إذا تم استيفاء شرطين: النقاط في نفس المكان لزوج من المكعبات لها ألوان مختلفة ، وفي الأخرى تكون مختلفة ومزدوجة ، والأزواج تعتبر حمراء مع خضراء ، أو سوداء مع الأبيض.
الرسم البياني كيلر لبعدين. عند العثور على مجموعة فرعية من أربعة مكعبات يرتبط كل منها بالمكعبات الأخرى ، ستدحض فرضية كيلر في الفضاء ثنائي الأبعاد. ومع ذلك ، لا توجد مثل هذه المجموعة الفرعية ، والفرضية صحيحة.
يوجد أدناه مثال لمجموعة مدمجة بالكامل من أربعة أحجار نرد غير موجودة في الرسم البياني.
هذا يعني ، على سبيل المثال ، إذا كان للمكعب نقطتان أحمر اللون ، والآخر به نقطتان سوداوان ، فإنهما غير متصلين بحافة. نقاطهم في نفس المواضع لها ألوان مختلفة ، لكنها لا تلبي متطلبات إقران الألوان. إذا كان أحد المكعبين يحتوي على نقطتين حمراء وسوداء ، والآخر يحتوي على نقطتين أخضر ، فإنهما متصلان بحافة ، لأنهما في أحد المواضع لهما لونان (أحمر وأخضر) ، وفي الآخر يكونان مختلفين ببساطة (الأسود والأخضر).
هناك 16 طريقة لتلوين نقطتين بأربعة ألوان (لذلك لدينا 16 مكعبًا). ضع كل هذه الاحتمالات الـ 16 أمامك. قم بتوصيل جميع أزواج المكعبات التي تلبي المتطلبات. هل هناك أربعة مكعبات في مخططك ، كل منها مدمج مع ثلاثة مكعبات أخرى؟
تسمى هذه المجموعة الفرعية من المكعبات المتصلة تمامًا بالعصبة. إذا تمكنت من العثور على واحدة ، فسوف تدحض فرضية كيلر في بعدين. ومع ذلك ، لا يمكنك - فهي ببساطة غير موجودة. وعدم وجود مثل هذه الزمرة المكونة من أربعة مكعبات يعني أن فرضية كيلر صحيحة بالنسبة لبعدين.
لا تكون هذه المكعبات حرفيًا نفس المربعات مثل فرضية كيلر ، ومع ذلك ، يمكنك افتراض أن كل مكعب يمثل بلاطة. ضع في اعتبارك أن الألوان المخصصة للنقاط هي الإحداثيات التي تضع المكعب في الفراغ. ووجود الحافة هو وصف لكيفية وضع مكعبين بالنسبة لبعضهما البعض.
إذا كانت ألوان المكعبات هي نفسها ، فإنها تمثل بلاطات متساوية التباعد في الفراغ. إذا لم يكن لديهم ألوان وأزواج ألوان مشتركة (أحدهما يحتوي على أبيض وأسود ، والآخر أخضر وأحمر) ، فإنهم يشيرون إلى مربعات متداخلة جزئيًا - وهو أمر غير مسموح به في ملء الفراغ. إذا كان للمكعبين مجموعة واحدة من الألوان المتطابقة ومجموعة واحدة من نفس اللون (أحدهما أسود - أحمر ، والآخر أخضر - أسود) ، فإنهما يمثلان مربعات ذات جانب مشترك.
أخيرًا ، والأهم من ذلك - إذا كان لديهم مجموعة واحدة من الألوان المقترنة ومجموعة أخرى من الألوان المختلفة - أي إذا كانوا متصلين بحافة - فإن المكعبات تمثل البلاط المتلامس مع بعضها البعض ، ولكن تم إزاحته قليلاً ، بسبب عدم تطابق حوافها تمامًا ... هذا هو الشرط الذي نحتاج إلى دراسته. تشير المكعبات المتصلة بحافة إلى مربعات مجاورة ليس لها جانب مشترك - وهذا هو الترتيب المطلوب لدحض فرضية كيلر.
قال خيول: "يجب أن يلمسوا ، لكن ليس بالكامل".
نفس اللون - نفس الترتيب.
ألوان مختلفة ، لا أزواج - متداخلة.
لونان متزاوجان وزوج من نفس اللون هما الجانب المشترك.
لونان متزاوجان واثنان مختلفان - اتصال جزئي من الجانبين.
تحجيم
قبل ثلاثين عامًا ، أثبت كورادي وشابو أن علماء الرياضيات يمكنهم استخدام إجراء مشابه للعمل مع فرضية كيلر في أي بُعد ، وتعديل معايير التجربة. لإثبات فرضية كيلر في ثلاثة أبعاد ، يمكنك استخدام 216 مكعبًا بثلاث نقاط على الحافة ، وربما ثلاثة أزواج من الألوان (ومع ذلك ، هناك بعض المرونة هنا). ثم عليك أن تبحث عن ثمانية مكعبات (2 3 ) ، متصلة ببعضها البعض تمامًا ، وفقًا لنفس الشروط التي قدمناها أعلاه.
بشكل عام ، لإثبات تخمين كيلر في أبعاد n ، تحتاج إلى استخدام مكعبات تحتوي على عدد n من النقاط ومحاولة العثور على زمرة بحجم 2 n فيما بينها . يمكن افتراض أنه يمثل نوعًا من البلاط الفائق (يتكون من 2 نأصغر حجما) قادرة على تغطية كامل الفضاء ذي البعد n.
إذا تمكنت من العثور على هذا البلاط الفائق (الذي لا يحتوي على بلاطات ذات جانب مشترك) ، فيمكنك استخدام نسخ منها لتغطية المساحة بأكملها بالبلاط بدون جانب مشترك ، مما سيدحض فرضية كيلر.
"إذا نجحت ، يمكنك تغطية المساحة بأكملها بنقل. قال لاجارياس ، الذي يعمل حاليًا في جامعة ميتشيغان ، "إن الكتلة التي لا تحتوي على جوانب بلاط مشتركة ستمتد إلى الطابق بأكمله.
دحض فرضية ماكي كيلر في البعد 8TH، وإيجاد زمرة من 256 مكعبات (2 8 )، لذلك بقي للتعامل مع فرضية في البعد 7TH، وإيجاد زمرة من 128 مكعبات (2 7). إن العثور على هذه الزمرة سيدحض فرضية كيلر في البعد السابع. أثبت أنه غير موجود وسوف تثبت صحة الفرضية.
لسوء الحظ ، يعد العثور على زمرة من 128 مكعبًا مهمة صعبة بشكل خاص. في الأعمال السابقة ، استفاد الباحثون من حقيقة أن الأبعاد 8 و 10 يمكن ، بمعنى ما ، "تحللها" إلى مساحات ذات أبعاد أقل ، مما يسهل العمل بها. وهنا لم ينجح هذا.
قال لاجارياس: "البعد السابع غير ملائم لأن الرقم 7 هو عدد أولي ولا يمكنك تقسيمه إلى أبعاد بترتيب أصغر". "لذلك ، لم يكن هناك مخرج سوى التعامل مع التوليفات الكاملة لهذه الرسوم البيانية."
يمكن أن يكون العثور على زمرة من 128 مكعبًا أمرًا صعبًا بالنسبة للدماغ غير المساعد - ولكن هذه هي أنواع الأسئلة التي يجيد الكمبيوتر الإجابة عليها ، خاصةً مع القليل من المساعدة.
لغة المنطق
لتحويل البحث عن النقرات إلى مهمة يمكن للكمبيوتر التعامل معها ، تحتاج إلى صياغتها من حيث المنطق الافتراضي . هذا هو مثل هذا التفكير المنطقي ، والذي يتضمن مجموعة من القيود.
لنفترض أنك ثلاثة تخطط لإقامة حفلة مع الأصدقاء. أنت تحاول إنشاء قائمة مدعوين ، ولكن هناك تضارب في المصالح. لنفترض أنك تريد إما دعوة Alexei أو استبعاد Kolya. يريد أحد أصدقائك دعوة كوليا أو فلاد أو كليهما. صديق آخر لا يريد الاتصال بأليكسي أو فلاد. مع هذه القيود ، هل من الممكن إنشاء قائمة ضيوف ترضي الثلاثة؟
في مصطلحات علوم الكمبيوتر ، تسمى هذه المشكلة مشكلة القبول. يمكن حلها عن طريق وصف الشرط في الصيغة المقترحة. في هذه الحالة ، يبدو الأمر على النحو التالي ، وتشير A و K و B إلى الضيوف المحتملين: (A OR NOT K) AND (K OR B) AND (NOT A OR NOT B).
يحسبها الكمبيوتر عن طريق استبدال 0 أو 1 في كل متغير. 0 هي قيمة المتغير "خطأ" أو متغير ، و 1 "صحيح" أو تشغيل. استبدال 0 بدلاً من A ، نقول أن Alexei لم تتم دعوته ، و 1 أنه تمت دعوته. في هذه الصيغة البسيطة ، يمكن استبدال 0 و 1 (عن طريق إنشاء قائمة ضيوف) بعدة طرق ، ومن الممكن بعد التكرار فوقهم جميعًا أن يستنتج الكمبيوتر أنه من المستحيل تلبية جميع الاهتمامات. ومع ذلك ، في هذه الحالة ، هناك طريقتان لاستبدال 1 و 0 لإرضاء الجميع: A = 1 ، K = 1 ، B = 0 (قم بدعوة Alexei و Kolya) و A = 0 ، K = 0 ، B = 1 (قم بدعوة واحد فلاد ).
يُطلق على برنامج الكمبيوتر الذي يحل مثل هذه العبارات اسم SAT solver ، حيث يكون SAT قصيرًا للرضا. يفحص جميع مجموعات المتغيرات ويعطي إجابة أحادية المقطع - إما نعم ، فهناك طريقة لتلبية متطلبات الصيغة ، أو لا ، فهي ليست كذلك.
جون ماكي من جامعة كارنيجي ميلون
"أنت تبحث فقط لمعرفة ما إذا كان بإمكانك تعيين قيم صحيحة وخاطئة لجميع المتغيرات بحيث تكون الصيغة بأكملها صحيحة ، وإذا كانت الإجابة بنعم ، فعندئذٍ تكون راضية ، وإذا لم يكن الأمر كذلك ، فلا ،" قال توماس هالز من جامعة بيتسبرغ.
مسألة إيجاد زمرة من 128 مكعبًا هي مشكلة مماثلة. يمكن أيضًا إعادة كتابتها كصيغة مقترحة وإعطاؤها لمحلل SAT. ابدأ بالكثير من المكعبات مع 7 نقاط لكل منها و 6 ألوان ممكنة. هل يمكن تلوين النقاط بحيث يتصل 128 مكعبًا ببعضها البعض وفق قواعد معينة؟ بمعنى آخر ، هل من الممكن تعيين الألوان بحيث تظهر النقرة؟
الصيغة المقترحة لسؤال النقر طويلة جدًا وتحتوي على 39000 متغير. يمكن تعيين قيمة من قيمتين ، 0 أو 1. نتيجة لذلك ، كان عدد الخيارات الممكنة لترتيب القيم ، أو طرق تعيين الألوان 2 39000 - وهو عدد كبير جدًا جدًا.
للعثور على إجابة السؤال حول فرضية كيلر في سبعة أبعاد ، سيتعين على الكمبيوتر التحقق من كل هذه المجموعات - وإما استبعادها جميعًا (مما يعني أن مجموعة الحجم 128 غير موجودة ، وفرضية كيلر في البعد السابع صحيحة) ، أو العثور على الأقل سيكون أحد خيارات العمل (دحض فرضية كيلر).
قال ماكي: "إذا قمت بتكرار بسيط لجميع الاحتمالات ، فستجد رقمًا مكونًا من 324 رقمًا". أسرع كمبيوتر في العالم سيعمل حتى نهاية الوقت ، يمر بجميع الاحتمالات.
ومع ذلك ، اكتشف مؤلفو العمل الجديد كيف يمكن للكمبيوتر تقديم إجابة محددة دون التحقق من كل الاحتمالات. مفتاح ذلك هو الكفاءة.
الكفاءة الخفية
يتذكر ماكي اليوم الذي بدأ فيه المشروع بالفعل من وجهة نظره. كان يقف أمام السبورة في مكتبه في جامعة كارنيجي ميلون ، يناقش قضية مع اثنين من المؤلفين المشاركين ، Hijul و Breikensik ، عندما اقترح Hijul طريقة لتنظيم البحث بحيث يمكن إكماله في فترة زمنية معقولة.
قال ماكي: "كان هناك عبقري بشري حقيقي يعمل في مكتبي في ذلك اليوم". - كنت أشاهد وين جريتسكي أو ليبرون جيمس في نهائيات الدوري الاميركي للمحترفين. أشعر بالقشعريرة من مجرد ذكرى ذلك ".
يمكنك تخصيص عمليات البحث عن رسم بياني معين لـ Keller بطرق مختلفة. تخيل أن لديك الكثير من المكعبات على المنضدة وتحاول حل 128 منها ، باتباع قواعد الكونت كيلر. لنفترض أنك حددت 12 بشكل صحيح ، لكن لا يمكنك معرفة كيفية إضافة التالي. في هذه المرحلة ، يمكنك تجاهل أي تكوين لـ 128 نردًا يتضمن هذا التكوين غير العامل البالغ 12.
قال شور ، الذي يعمل حاليًا في معهد ماساتشوستس للتكنولوجيا: "إذا كنت تعلم أن مهامك الخمسة الأولى لا تتطابق ، فلن تحتاج إلى البحث عن متغيرات أخرى ، وهذا عادة ما يؤدي إلى تقليص مجال البحث كثيرًا".
نوع آخر من الكفاءة يرتبط بالتناظر. الأشياء المتماثلة هي نفسها إلى حد ما. تسمح لنا الهوية بفهم الكائن بأكمله ، ودراسة جزء منه فقط - بالنظر إلى نصف وجه الشخص ، يمكنك استعادته بالكامل.
وبالمثل ، يمكنك قطع الزوايا في حالة الرسوم البيانية لـ Keller. تخيل مرة أخرى أنك تحاول ترتيب المكعبات على الطاولة. لنفترض أنك بدأت من منتصف الطاولة وتبني يدك على اليسار. تضع أربعة أحجار نرد ، وتصل إلى طريق مسدود. لقد ألغيت الآن مجموعة بداية واحدة وجميع التركيبات التي تستند إليها. ومع ذلك ، يمكنك استبعاد انعكاس هذه المجموعة الأولية - تكوين المكعبات التي تحصل عليها إذا وضعتها بنفس الطريقة ، فقط على اليمين.
قال هالز: "إذا توصلت إلى طريقة لحل المشكلات المرضية التي تأخذ في الاعتبار التماثل بذكاء ، فقد قمت بتبسيط المهمة إلى حد كبير".
استفاد أربعة زملاء من كفاءات هذا البحث بطريقة جديدة - على وجه الخصوص ، قاموا بأتمتة النظر في الحالات المتماثلة ، بينما عالجها علماء الرياضيات في السابق يدويًا تقريبًا.
نتيجة لذلك ، قاموا بتحسين بحثهم عن مجموعات بحجم 128 لدرجة أنه بدلاً من التحقق من 239000 تكوين ، كان على برنامجهم التحقق من حوالي مليار فقط ( 2،30 ). أدى هذا إلى إجراء بحث قد يستغرق وقتًا طويلاً في مهمة في صباح واحد. أخيرًا ، بعد نصف ساعة فقط من الحسابات ، تلقوا إجابة.
قال هيول: "قالت أجهزة الكمبيوتر لا ، لذلك نحن نعلم أن الفرضية تعمل". من المستحيل تلوين 128 مكعبًا حتى تندمج جميعًا مع بعضها البعض ، لذلك تأكدت فرضية كيلر للبعد السابع. لأي موضع للبلاط يغطي مساحة ، سيكون هناك حتمًا زوج من الحواف الملامسة تمامًا.
لم يقدم الكمبيوتر إجابة أحادية المقطع فقط. وقد أرفق به إثباتًا طويلاً يبلغ 200 جيجابايت يدعم هذا الاستنتاج.
الإثبات ليس مجرد حساب لجميع مجموعات المتغيرات التي تم التحقق منها بواسطة الكمبيوتر. هذه حجة منطقية تثبت أن الزمرة الضرورية لا يمكن أن توجد. قام الباحثون بإدخال الأدلة في برنامج يختبر الأدلة الرسمية من خلال تتبع منطق الحجة والتحقق من صحتها.
"لم نختبر جميع الخيارات ولم نعثر على أي شيء. لقد مررنا بجميع الخيارات وتمكنا من كتابة دليل على أن مثل هذا الشيء غير موجود ، - قال ماكي. "تمكنا من تدوين أدلة على عدم الرضا".