ترفندهای ریاضی رام کردن فاصله میانی | مجله کوانتا

تاکنون امسال ، کوانتوم سه پیشرفت عمده در نظریه رمزی را شرح داده است، مطالعه چگونگی جلوگیری از ایجاد الگوهای ریاضی. این اولین نتیجه برای اینکه مجموعه ای از اعداد صحیح بدون اینکه شامل سه عدد با فاصله مساوی مانند {2، 4، 6} یا {21، 31، 41} باشد، یک کلاه جدید بگذارید. این دوم و سوم به طور مشابه، محدوده‌های جدیدی را در اندازه شبکه‌ها بدون خوشه‌هایی از نقاط که همگی متصل هستند یا همگی جدا از یکدیگر قرار می‌دهند.

شواهد نشان می‌دهند که با افزایش بی‌نهایت اعداد درگیر چه اتفاقی می‌افتد. به طور متناقض، گاهی اوقات این می تواند آسان تر از رسیدگی به مقادیر آزاردهنده دنیای واقعی باشد.

به عنوان مثال، دو سوال در مورد کسری با مخرج واقعا بزرگ در نظر بگیرید. ممکن است بپرسید که بسط اعشاری مثلاً 1/42503312127361 چقدر است. یا می توانید بپرسید که آیا با افزایش مخرج، این عدد به صفر نزدیک می شود. سوال اول یک سوال خاص در مورد یک کمیت واقعی است و محاسبه آن سخت تر از سوال دوم است که می پرسد چگونه کمیت 1/n به صورت مجانبی تغییر خواهد کرد n رشد می کند. (به 0 نزدیک و نزدیکتر می شود.)

گفت: "این مشکلی است که همه نظریه رمزی را درگیر کرده است." ویلیام گاسارچ، دانشمند کامپیوتر در دانشگاه مریلند. نظریه رمزی به دلیل داشتن نتایج مجانبی بسیار خوب شناخته شده است. اما تجزیه و تحلیل اعدادی که کوچکتر از بی نهایت هستند نیاز به یک جعبه ابزار ریاضی کاملاً متفاوت دارد.

گاسارچ سوالاتی را در نظریه رمزی بررسی کرده است که شامل اعداد محدودی است که برای حل مسئله با نیروی بی رحم بسیار بزرگ هستند. در یکی از پروژه‌ها، او نسخه محدود اولین پیشرفت امسال را پذیرفت - مقاله فوریه توسط زندر کلی، دانشجوی کارشناسی ارشد در دانشگاه ایلینویز، اوربانا-شامپین، و راغو مکا از دانشگاه کالیفرنیا، لس آنجلس. کلی و مکا یک کران بالایی جدید برای تعداد اعداد صحیح بین 1 و پیدا کردند N می توانید در یک مجموعه قرار دهید در حالی که از پیشرفت های سه ترم یا الگوهای اعداد با فاصله مساوی اجتناب کنید.

اگرچه نتیجه کلی و مکا حتی اگر صدق می کند N نسبتا کوچک است، در این مورد محدودیت خاصی ارائه نمی دهد. برای مقادیر بسیار کوچک از N، بهتر است به روش های بسیار ساده پایبند باشید. اگر N مثلاً 5 است، فقط به تمام مجموعه های ممکن اعداد بین 1 و نگاه کنید N، و بزرگترین مورد بدون پیشرفت را انتخاب کنید: {1، 2، 4، 5}.

اما تعداد پاسخ های مختلف ممکن به سرعت افزایش می یابد و به کارگیری چنین استراتژی ساده ای را بسیار دشوار می کند. بیش از 1 میلیون مجموعه متشکل از اعداد بین 1 تا 20 وجود دارد. بیش از 10 عدد وجود دارد.⁶⁰ با استفاده از اعداد بین 1 تا 200. یافتن بهترین مجموعه بدون پیشرفت برای این موارد، حتی با استراتژی‌های بهبود کارایی، به قدرت محاسباتی زیادی نیاز دارد. گفت: "شما باید بتوانید عملکرد زیادی را از چیزها حذف کنید." جیمز گلن، دانشمند کامپیوتر در دانشگاه ییل. در سال 2008، گاسارچ، گلن و کلاید کروسکال از دانشگاه مریلند برنامه نوشت برای پیدا کردن بزرگترین مجموعه های بدون پیشرفت به یک N از 187. (کار قبلی تا 150 و همچنین برای 157 پاسخ دریافت کرده بود.) گلن گفت، علیرغم فهرستی از ترفندها، برنامه آنها ماه ها طول کشید تا به پایان برسد.

این تیم برای کاهش بار محاسباتی خود، از آزمایش‌های ساده‌ای استفاده کردند که برنامه‌شان را از پیگیری جستجوهای بن‌بست جلوگیری می‌کرد و مجموعه‌های آن‌ها را به بخش‌های کوچک‌تری تقسیم می‌کرد که به طور جداگانه تجزیه و تحلیل می‌کردند.

Gasarch، Glenn و Kruskal چندین استراتژی دیگر را نیز امتحان کردند. یک ایده امیدوارکننده بر تصادفی بودن تکیه داشت. یک راه ساده برای دستیابی به یک مجموعه بدون پیشرفت این است که 1 را در مجموعه خود قرار دهید، سپس همیشه عدد بعدی را اضافه کنید که پیشرفت حسابی ایجاد نمی کند. این روش را دنبال کنید تا عدد 10 را بزنید و مجموعه {1، 2، 4، 5، 10} را دریافت کنید. اما معلوم شد که به طور کلی این بهترین استراتژی نیست. "اگر از 1 شروع نکنیم چه؟" گسارچ گفت. "اگر از یک مکان تصادفی شروع کنید، در واقع بهتر عمل می کنید." او افزود که محققان نمی دانند چرا تصادفی بودن تا این حد مفید است.

محاسبه نسخه‌های محدود دو نتیجه جدید نظریه رمزی حتی از تعیین اندازه مجموعه‌های بدون پیشروی آزاردهنده‌تر است. این نتایج مربوط به شبکه های ریاضی (به نام نمودار) است که از گره هایی به هم متصل شده اند که با خطوطی به نام لبه ها به هم متصل شده اند. شماره رمزی r(s, t) کوچکترین تعداد گره هایی است که یک گراف باید داشته باشد تا اجتناب از گنجاندن گروهی از آنها غیرممکن شود s گره های متصل یا t قطع شده ها عدد رمزی برای محاسبه حتی یک سردرد است r(5، 5) ناشناخته است - جایی بین 43 و 48 است.

در 1981، برندن مک کیکه اکنون یک دانشمند کامپیوتر در دانشگاه ملی استرالیا است، یک برنامه نرم افزاری به نام nauty نوشت که قرار بود محاسبه اعداد رمزی را ساده تر کند. Nauty تضمین می‌کند که محققان وقت خود را برای بررسی دو نمودار که فقط نسخه‌های برگردان یا چرخانده شده‌اند، تلف نمی‌کنند. "اگر کسی در منطقه باشد و از ناوتی استفاده نکند، بازی تمام شده است. شما باید از آن استفاده کنید.» استانیسلاو رادزیزوفسکی، ریاضیدان مؤسسه فناوری روچستر. با این حال، مقدار محاسبات درگیر تقریباً غیرقابل درک است. در سال 2013، Radziszowski و یان گوگبر ثابت کرد که r(3، 10) حداکثر 42 است. Goedgebeur، دانشمند کامپیوتر در دانشگاه KU Leuven در بلژیک گفت: "من فکر می کنم تقریبا 50 سال CPU طول کشید."

اگر نمی توانید عدد رمزی دقیقی را محاسبه کنید، می توانید مقدار آن را با مثال هایی محدود کنید. اگر یک گراف 45 گرهی بدون پنج گره که همه به هم متصل بودند و بدون پنج گره که همه قطع شده بودند پیدا کنید، ثابت می کند که r(5، 5) بزرگتر از 45 است. رادزیزوسکی گفت، ریاضیدانانی که اعداد رمزی را مطالعه می کردند، فکر می کردند که یافتن آن نمونه هایی که نمودار رمزی نامیده می شود، ساده است. اما اینطور نبود. او گفت: "این انتظار وجود داشت که ساختارهای ریاضی زیبا و جالب بهترین ساختار ممکن را ارائه دهند، و ما فقط به افراد بیشتری نیاز داریم که روی آن کار کنند." "احساس من بیشتر و بیشتر این است که هرج و مرج است."

تصادفی بودن هم مانعی برای درک و هم یک ابزار مفید است. جفری اگزویک دانشمند کامپیوتر در دانشگاه ایالتی ایندیانا، سال‌ها را صرف اصلاح روش‌های تصادفی برای تولید نمودارهای رمزی کرده است. که در یک مقاله 2015 Exoo و Milos Tatarevic با اعلام ده ها نمودار جدید و رکورددار رمزی، نمودارهای تصادفی تولید کردند و سپس به تدریج آنها را با حذف یا اضافه کردن یال هایی تغییر دادند که تعداد خوشه های ناخواسته را کاهش داد تا زمانی که گراف رمزی را پیدا کردند. Radziszowski گفت که تکنیک های Exoo به اندازه هر چیز دیگری هنر هستند. آنها گاهی اوقات از او می خواهند که چندین روش را ترکیب کند، یا از قضاوت در مورد نوع نمودارها استفاده کند. Radziszowski گفت: "بسیاری، بسیاری از مردم آن را امتحان می کنند، و نمی توانند آن را انجام دهند."

Goedgebeur گفت: تکنیک‌های توسعه‌یافته برای تولید نمودارهای رمزی می‌توانند روزی به طور گسترده‌تر مفید باشند. کار کرد تولید انواع دیگر نمودارها، مانند نمودارهایی که ترکیبات شیمیایی را نشان می دهند. او در ایمیلی نوشت: «بعید نیست که این تکنیک‌ها نیز قابل انتقال و تنظیم برای کمک به تولید کلاس‌های دیگر نمودارها با کارآمدتر (و بالعکس) باشند.

با این حال، برای Radziszowski، دلیل مطالعه اعداد رمزی کوچک بسیار ساده تر است. او گفت: "چون باز است، زیرا هیچ کس نمی داند پاسخ چیست." «موارد بی اهمیتی که با دست انجام می دهیم. کمی بزرگتر، به یک کامپیوتر نیاز دارید، و کمی بزرگتر، حتی کامپیوتر به اندازه کافی خوب نیست. و بنابراین چالش ظاهر می شود."