ریاضیدانان ساختار پنهان را در یک نوع فضای معمولی پیدا می کنند

در پاییز سال 2017 ، مهتاب ساوهنیاو که در آن زمان در انستیتوی فناوری ماساچوست فارغ التحصیل شد، به یک گروه مطالعه فارغ التحصیل پیوست که قصد داشتند یک مقاله را در طول یک ترم مطالعه کنند. اما ساهنی به یاد می‌آورد که در پایان ترم، آنها تصمیم گرفتند که به خاطر پیچیدگی اثبات، ادامه دهند. او گفت: "این واقعا شگفت انگیز بود." "به نظر می رسید کاملاً وجود دارد."

کاغذ توسط پیتر کیوش از دانشگاه آکسفورد. موضوع آن: اشیاء ریاضی به نام طرح.

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

به زودی، ریاضیدانان نسخه کلی تری از سوال کرکمن را مطرح کردند: اگر دارید n عناصر موجود در یک مجموعه (15 دختر دانش آموز ما)، می توانید همیشه آنها را در گروه های اندازه مرتب کنید k (ردیف های سه تایی) به طوری که هر مجموعه کوچکتر از اندازه t (هر جفت دختر) دقیقاً در یکی از آن گروه ها ظاهر می شود؟

چنین تنظیماتی که به عنوان (n, k, t) طرح‌ها از آن زمان برای کمک به توسعه کدهای تصحیح خطا، آزمایش‌های طراحی، نرم‌افزار تست و برنده شدن براکت‌های ورزشی و قرعه‌کشی‌ها استفاده شده‌اند.

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

حالا کیوش، ساهنی و اشوین سهیک دانشجوی فارغ التحصیل در MIT، نشان داده است که حتی اشیاء گریزان تر، به نام طرح های زیرفضا، همیشه نیز وجود دارد. گفت: "آنها وجود اشیایی را ثابت کرده اند که وجود آنها اصلاً واضح نیست." دیوید کانلون، ریاضیدان مؤسسه فناوری کالیفرنیا.

برای انجام این کار، آنها باید رویکرد اصلی Keevash را - که شامل ترکیبی تقریباً جادویی از تصادفی بودن و ساخت دقیق‌تر می‌شد - اصلاح می‌کردند تا آن را در یک محیط بسیار محدودتر به کار گیرند. و بنابراین Sawhney، که اکنون نیز در حال دنبال کردن دکترای خود در MIT است، خود را رو در رو با مقاله ای یافت که چند سال قبل او را گیج کرده بود. او گفت: "درک کامل تکنیک ها، و واقعاً رنج کشیدن و کار کردن از طریق آنها و توسعه آنها واقعاً لذت بخش بود."

فراتر از آنچه فراتر از تصور ماست

برای دهه‌ها، ریاضیدانان مسائل مربوط به مجموعه‌ها و زیرمجموعه‌ها را - مانند سؤال طراحی - به مسائلی درباره فضاها و زیرفضاهای به اصطلاح برداری ترجمه کرده‌اند.

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

اتاقی را که در آن هستید در نظر بگیرید. این اتاق شامل تعداد نامتناهی نقطه و تعداد نامتناهی بردار است - بردارهایی که از جایی که شما هستید تا هر نقطه در اتاق امتداد دارند. همه آن بردارها را می توان از سه بردار اساسی ساخت: یک بردار به صورت افقی در مقابل شما، دیگری به سمت راست شما و دیگری به سمت بالا. با اضافه کردن این بردارها، ضرب آنها در اعداد واقعی یا انجام ترکیبی از این دو، می توانید فضای برداری سه بعدی را که در آن زندگی می کنید ایجاد کنید. (تعداد بردارهای مورد نیاز برای تولید کل فضا، ابعاد فضای برداری است.)

زیرفضاهای مختلفی در داخل هر فضای برداری قرار دارند. فقط بردارهایی را که به سمت راست و روبروی شما اشاره می کنند، بردارید. اینها یک زیرفضای دو بعدی را تعریف می کنند - یک صفحه مسطح موازی با کف.

ریاضیدانان اغلب با فضاها و زیرفضاهای بردار محدود کار می کنند، جایی که بردارها نمی توانند به هر جهت ممکن اشاره کنند (و تصور یکسانی از طول ندارند). در این دنیا، هر فضای برداری فقط تعداد محدودی بردار دارد.

مسئله طراحی زیرفضا با آن سروکار دارد n-فضاهای برداری بعدی و زیرفضاهای آنها. در چنین فضاهای برداری - دوباره، تا زمانی که n به اندازه کافی بزرگ است و شرایط ساده را برآورده می کند - آیا می توانید مجموعه ای از آنها را پیدا کنید k-زیر فضاهای بعدی به گونه ای که هر کدام t-فضای فرعی بعدی دقیقاً در یکی از آنها وجود دارد؟ به چنین جسمی (n, k, t) طراحی زیرفضا. از نظر مفهومی شبیه به مشکل طرح های معمولی است، اما شامل ترتیباتی است که بسیار محدودتر هستند.

گفت: "این یک مشکل مهم است زیرا گوشه ای از یک قیاس بسیار عمیق بین مجموعه ها و زیرمجموعه ها از یک سو و فضاهای برداری و زیرفضاها از سوی دیگر است." پیتر کامرون از دانشگاه سنت اندروز در اسکاتلند.

در 50 سالی که ریاضیدانان شروع به فکر کردن در مورد این مشکل کردند، آنها به این مسئله پی بردند فقط یک مثال بی اهمیت (اگرچه آنها می دانند که انواع کلی تری از طرح های زیرفضا وجود دارد): در یک فضای برداری 13 بعدی، می توان دقیقا یک بار زیرفضاهای دو بعدی را با فضاهای سه بعدی پوشاند. نتیجه نیاز به اثبات عظیم مبتنی بر رایانه داشت، زیرا حتی برای چنین مقادیر کوچکی از n, k و t، در نهایت با میلیون ها زیرفضا کار می کنید. پیچیدگی چنین سیستم هایی «فقط فراتر از تصور ما نیست. این فراتر از تصور ماست.» تووی اتزیون از تکنیون در اسرائیل، که به کشف نمونه کمک کرد.

اما آیا طرح‌های زیرفضایی همیشه وجود دارند، برای هر کدام k و t? برخی از ریاضیدانان حدس زدند که به طور کلی، چنین اجسامی غیرممکن هستند. کیواش گفت، دیگران، که از کار انجام شده در طول سال ها بر روی طرح ها دلگرم شده بودند، دریافتند که "ممکن است اثبات آن سخت باشد، اما اگر دلیل واضحی برای وجود نداشتن آنها وجود نداشته باشد، پس باید وجود داشته باشند."

ساح گفت: در مقایسه با قلمرو طرح‌ها، «برای این مشکل، چیزی وجود نداشت». "من حدس می زنم که هر زمان که این اتفاق می افتد کمی کنجکاوی را برانگیزد."

اسفنجی برای خطاها

ساه و ساهنی در سال 2017 در مقطع کارشناسی ملاقات کرد در MIT (و در نهایت در همان گروه خواندن شرکت کردم). کانلون گفت: چند ماه بعد، "آنها با هم کار کردند و هرگز متوقف نشدند." آنها در حال تولید تحقیقات با کیفیت بالا با سرعتی هستند که من حتی نمی توانم پلک بزنم.

دو ریاضیدان جوان از این که نوشتن تنها یک مثال صریح از طراحی زیرفضا بسیار سخت بوده است، کنجکاو شده بودند و آن ها این مسئله را راهی عالی برای کشف مرزهای تکنیک های مهم در ترکیب شناسی می دانستند.

در همین حال، کیوش از زمان نتیجه‌اش در سال 2014 این سوال را در ذهن خود نگه داشته بود. هنگامی که ساه و ساهنی در کنفرانسی در سال گذشته به او مراجعه کردند، هر سه تصمیم گرفتند آن را دنبال کنند.

آنها از همان استراتژی کلی پیروی کردند که کیوش در کار طراحی خود ترسیم کرده بود - اما به دلیل محدودیت های سخت تر، "در عمل، تمام مراحل در اجرای خود بسیار متفاوت بودند." اول، آنها مجموعه ای از فضاهای فرعی را که به دقت انتخاب شده اند، کنار می گذارند. این الگو بعداً به عنوان جزیره ای از ساختار در اقیانوسی از تصادف عمل می کند.

سپس یک نسخه اصلاح شده از یک فرآیند اساسا تصادفی به نام Rödl nibble را برای پوشش بیشتر زیرفضاهای باقیمانده اعمال کردند. این امر باعث شد تا حجم کمی از زیرفضاها باقی بماند که هنوز باید با آن دست و پنجه نرم می کردند. در ظاهر، آن زیرفضاها کاملاً بدون ساختار به نظر می رسیدند. به نظر غیرممکن به نظر می رسید که آنها را در خوشه هایی مرتب کنیم که به درستی پوشش داده شوند.

آن‌ها الگو را تکه‌تکه کردند و برخی از فضاهای فرعی آن را با زیرفضاهای موجود در hodgepodge ترکیب کردند - آن‌ها را به‌خوبی در آرایش‌های بزرگ‌تری قرار دادند که می‌توانستند به درستی پوشش داده شوند. آنها باید به دقت پیگیری می کردند که چگونه این کار را انجام می دهند تا مطمئن شوند که هر حرکتی که انجام می دهند به سمت آن ساختار جهانی تر منتهی می شود. اما در نهایت، آنها توانستند از الگو برای پر کردن تمام سوراخ هایی که نیبل رودل قادر به پوشاندن آنها نبود استفاده کنند. مانند یک اسفنج، الگو تمام خطاهای طراحی را خیس کرد. (در نتیجه، این تکنیک کلی «جذب» نامیده می‌شود.) ساونی گفت: «تقریباً مثل این است که می‌خواهید فرشی را در گوشه‌ای بگذارید. "در جای دیگری ظاهر می شود، و شما آن را فشار می دهید، و به نوعی، پس از 20 فشار، فرش فقط صاف است."

این اثبات را تکمیل کرد. توجه به این نکته مهم است که، مانند کار طراحی، این نتیجه حداقل از نظر تئوری می تواند برای ساخت این اشیاء مورد استفاده قرار گیرد - اما فقط برای بسیار بزرگ n. یافتن نمونه های عینی و عملی یک کار برای آینده باقی می ماند.

در پایان کار به تصویر کشیده شد یک راه غیر منطقی دیگر که ریاضیدانان می توانند نیروهای تصادفی را برای جستجوی ساختار پنهان مهار کنند. گفت: «همه انواع ساختارهای غیرمنتظره امکان پذیر است شریل پراگر، ریاضیدان دانشگاه استرالیای غربی.

کامرون گفت: «شواهد نشان می‌دهد که تکنیک‌های کی‌وش در زمینه‌های وسیع‌تری نسبت به آنچه برای آن طراحی شده بودند، کار می‌کنند. این نشان می دهد که سایر مشکلات دشوار ممکن است با ترکیب تصادفی و جذب به روش های هوشمندانه حل شوند.

زمانی که Sawhney برای اولین بار در مقاله Keevash در مقطع کارشناسی درباره آنها خواند، این تکنیک ها برای Sawhney جادویی بود. حتی اکنون که او درک بسیار عمیق تری از آنها به دست آورده است، "این تصور از بین نمی رود."