"A-Team" ریاضی یک پیوند مهم بین جمع و مجموعه ها را اثبات می کند | مجله کوانتا

در مجموعه‌ای از اعداد که به‌طور تصادفی انتخاب شده‌اند، جمع می‌تواند بی‌خطر باشد.

هر جفت از چنین مجموعه‌ای را با هم جمع کنید، و در نهایت به لیست جدیدی خواهید رسید که احتمالاً تعداد آن‌ها بسیار بیشتر از چیزی است که با آن شروع کرده‌اید. با 10 عدد تصادفی شروع کنید، و این لیست جدید (به نام sumset) حدود 50 عنصر خواهد داشت. با 100 شروع کنید و sumset احتمالاً حدود 5,000 خواهد بود. 1,000 عدد اولیه تصادفی یک مجموع 500,000 عددی را می سازد.

اما اگر مجموعه اولیه شما دارای ساختار باشد، مجموع مجموعه می تواند با اعداد کمتر از این به پایان برسد. مجموعه 10 عددی دیگری را در نظر بگیرید: همه اعداد زوج از 2 تا 20. از آنجا که جفت های مختلف با یک عدد جمع می شوند - 10 + 12 همان 8 + 14 و 6 + 16 است - مجموع فقط 19 عدد دارد، نه 50. این تفاوت با بزرگتر شدن مجموعه ها بیشتر و عمیق تر می شود. یک لیست ساختاریافته از 1,000 عدد ممکن است دارای مجموعه ای باشد که فقط 2,000 عدد در آن باشد.

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

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

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

گرین به نیروهای گوورز پیوست، فردی منرز از دانشگاه کالیفرنیا، سن دیگو، و ترنس تائو، برنده مدال فیلدز در دانشگاه کالیفرنیا، لس آنجلس برای شکل دادن به آنچه ریاضیدان و وبلاگ نویس اسرائیلی است. گیل کلای به نام "یک تیم” از ریاضیدانان. آنها نسخه ای از حدس را در مقاله ای اثبات کردند به اشتراک گذاشته شده در 9 نوامبر.

نتز کاتزریاضیدانی در دانشگاه رایس که در این کار دخالتی نداشت، این اثبات را «به‌طور ساده» و «کم و بیش کاملاً غیرمعمول» توصیف می‌کند.

سپس تائو تلاشی را برای رسمی کردن اثبات در آن آغاز کرد ناب، یک زبان برنامه نویسی است که به ریاضیدانان کمک می کند تا قضایا را تأیید کنند. تنها در چند هفته، آن تلاش موفق شد. صبح سه شنبه 5 دسامبر، تائو اعلام کرد که Lean این حدس را بدون هیچ «با عرض پوزش» ثابت کرده است - عبارت استانداردی که زمانی ظاهر می شود که رایانه نتواند مرحله خاصی را تأیید کند. این پرکاربردترین استفاده از چنین مواردی است ابزارهای تأیید از سال 2021و یک نقطه عطف را در روش هایی که ریاضیدانان برهان ها را با عباراتی که کامپیوتر می تواند بفهمد می نویسند، نشان می دهد. گوورز گفت، اگر استفاده از این ابزارها به اندازه کافی برای ریاضیدانان آسان شود، ممکن است بتوانند جایگزین فرآیند بررسی همتایان طولانی و طاقت فرسا شوند.

مواد تشکیل دهنده اثبات ده ها سال در حال جوشیدن بود. Gowers اولین قدم های خود را در اوایل دهه 2000 تصور کرد. اما 20 سال طول کشید تا چیزی را که کالای "یک جام مقدس" میداند، ثابت کرد.

درون گروهی

برای درک حدس مارتون، آشنایی با مفهوم گروه، یک شیء ریاضی که از یک مجموعه و یک عملیات تشکیل شده است، کمک می کند. به اعداد صحیح - مجموعه ای بی نهایت از اعداد - و عمل جمع فکر کنید. هر بار که دو عدد صحیح را با هم جمع می کنید، یک عدد صحیح دیگر بدست می آورید. علاوه بر این، از چند قانون دیگر عملیات گروهی، مانند تداعی، پیروی می کند، که به شما امکان می دهد ترتیب عملیات را تغییر دهید: 3 + (5 + 2) = (3 + 5) + 2.

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

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

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

گفت: "شما می توانید وانمود کنید که همه چیز زیرمجموعه بزرگی از یک گروه است." تام ساندرز، یکی از شاگردان سابق گوورز که اکنون همکار گرین در آکسفورد است، یا می توانید، «هر چیزی را که می خواستید از وجود بسیاری از تصادفات افزایشی به دست آورید. هر دوی این دیدگاه ها مفید هستند.»

روزسا حدس مارتون را در سال 1999 منتشر کرد، به او اعتبار کامل می دهد. او گفت: «او مستقل از من و فریمن و احتمالاً قبل از ما به این حدس رسید. به همین دلیل، وقتی با او صحبت کردم، تصمیم گرفتم آن را حدس او بگذارم. با این حال، ریاضیدانان اکنون از آن به عنوان حدس چند جمله ای فریمن-روزا یا PFR یاد می کنند.

صفر و یک

گروه‌ها، مانند بسیاری از اشیاء ریاضی، اشکال مختلفی دارند. مارتون تصور می کرد که حدس او برای همه گروه ها صادق است. این هنوز باید نشان داده شود. مقاله جدید آن را برای نوع خاصی از گروه ثابت می کند، که به عنوان عناصر خود لیستی از اعداد باینری مانند (0، 1، 1، 1، 0) را در نظر می گیرد. از آنجایی که کامپیوترها به صورت باینری کار می کنند، این گروه در علوم کامپیوتر بسیار مهم است. اما در ترکیبات افزودنی نیز مفید بوده است. سندرز گفت: «مثل این محیط اسباب‌بازی است که می‌توانید در آن بازی کنید و چیزهایی را امتحان کنید. او افزود: "جبر بسیار بسیار زیباتر از کار با اعداد کامل است."

لیست ها دارای طول های ثابت هستند و هر بیت می تواند 0 یا 1 باشد. شما آنها را با اضافه کردن هر ورودی به همتای خود در لیستی دیگر، با این قانون که 1 + 1 = 0 است، با هم اضافه می کنید. بنابراین (0، 1، 1، 1) ، 0) + (1، 1، 1، 1، 1) = (1، 0، 0، 0، 1). PFR تلاشی است برای فهمیدن اینکه یک مجموعه اگر کاملاً یک زیرگروه نباشد، اما دارای برخی ویژگی‌های گروه مانند باشد، چگونه می‌تواند به نظر برسد.

برای اینکه PFR دقیق شود، تصور کنید مجموعه ای از لیست های دودویی به نام دارید A. حالا هر جفت عنصر را از آن بگیرید A و آنها را جمع کنید. مجموع حاصل جمع مجموعه را تشکیل می دهند A، به نام A + A. اگر عناصر از A به طور تصادفی انتخاب می شوند، سپس بیشتر مبالغ با یکدیگر متفاوت هستند. اگر وجود دارد k عناصر در A، این بدان معنی است که در اطراف وجود خواهد داشت k²/2 عنصر در مجموعه جمع. چه زمانی k بزرگ است - مثلاً 1,000 - k²/2 خیلی بزرگتر از k. اما اگر A یک زیر گروه است، هر عنصر از A + A هست در A، به این معنی که A + A هم اندازه است A خود.

PFR مجموعه هایی را در نظر می گیرد که تصادفی نیستند، اما زیر گروه نیز نیستند. در این مجموعه ها تعداد عناصر در A + A تا حدودی کوچک است - مثلاً 10kو یا 100k. "این واقعا مفید است زمانی که مفهوم شما از ساختار بسیار غنی تر از صرف یک ساختار جبری دقیق باشد." شاچار لاوت، دانشمند کامپیوتر در دانشگاه کالیفرنیا، سن دیگو.

تائو گفت، تمام مجموعه‌هایی که ریاضیدانان از این ویژگی می‌دانستند «بسیار نزدیک به زیرگروه‌های واقعی هستند». "این شهود بود، که هیچ نوع گروه جعلی دیگری در اطراف وجود نداشت." فریمن نسخه ای از این گفته را در کار اصلی خود ثابت کرده بود. در سال 1999، روسا قضیه فریمن را از اعداد صحیح به تنظیم لیست های دودویی گسترش داد. او ثابت کرد که وقتی تعداد عناصر در A + A مضرب ثابتی از اندازه است A, A در یک زیر گروه قرار دارد.

اما قضیه روزا مستلزم این بود که زیرگروه عظیم باشد. بینش مارتون این بود که به جای اینکه در یک زیرگروه غول پیکر قرار بگیرد، این موضوع را مطرح کرد. A می‌تواند در تعداد چند جمله‌ای از مجموعه‌های یک زیرگروه باشد که بزرگ‌تر از مجموعه اصلی نیست. A.

"من با دیدن یک ایده واقعی یک ایده واقعی می شناسم"

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

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

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

اما ایده های گورز در خاطرات و هارد دیسک های همکارانش ماندگار شد. گرین که همچنین شاگرد گورز بوده است، گفت: «یک ایده واقعی در آنجا وجود دارد. "من یک ایده واقعی را زمانی می شناسم که یک ایده واقعی می بینم." در تابستان امسال، گرین، منرز و تائو سرانجام ایده های گورز را از برزخ خود آزاد کردند.

گرین، تائو و منرز قبل از اینکه فکر کنند به ایده‌های 37 ساله گورز بازگردند، 20 صفحه عمیق با هم همکاری داشتند. در 23 ژوئن مقاله، آنها با موفقیت از مفهومی از نظریه احتمال به نام متغیرهای تصادفی برای بررسی ساختار مجموعه هایی با مجموعات کوچک استفاده کردند. با ایجاد این سوئیچ، گروه می توانست ست های خود را با ظرافت بیشتری دستکاری کند. Manners گفت: "برخورد با متغیرهای تصادفی به نوعی بسیار سخت تر از برخورد با مجموعه ها است." با یک متغیر تصادفی، "من می توانم یکی از احتمالات را با مقدار کمی تغییر دهم، و این ممکن است متغیر تصادفی بهتری به من بدهد."

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

همانطور که گروه نتایج جدید خود را جویدند، متوجه شدند که بالاخره محیطی را ساخته اند که ایده های خفته گورز در آن شکوفا شود. اگر آنها اندازه یک مجموعه را با استفاده از آنتروپی آن اندازه گیری کنند، به جای تعداد عناصر، جزئیات فنی ممکن است بسیار بهتر عمل کنند. تائو گفت: «در مقطعی متوجه شدیم که این ایده‌های قدیمی تیم ۲۰ سال پیش در واقع بیشتر از ایده‌هایی که ما تلاش می‌کردیم، کار می‌کردند. و بنابراین ما تیم را به پروژه بازگرداندیم. و سپس همه قطعات به طرز شگفت انگیزی به خوبی با هم قرار می گیرند."

با این حال، جزئیات زیادی وجود داشت که باید قبل از جمع‌آوری مدرک به آن پی برد. منرز گفت: «این احمقانه بود که هر چهار نفر ما به طرز باورنکردنی مشغول چیزهای دیگر بودیم. "شما می خواهید این نتیجه عالی را منتشر کنید و به دنیا بگویید، اما در واقع هنوز باید میان ترم های خود را بنویسید." در نهایت، گروه پیشروی کردند و در 9 نوامبر، آنها مقاله خود را پست کردند. آنها ثابت کردند که اگر A + A بزرگتر از k برابر اندازه A، و سپس A را می توان با بیش از حدود پوشش داد k¹² جابجایی های یک زیر گروه که بزرگتر از آن نیست A. این تعداد بالقوه بسیار زیادی از تغییرات است. اما این یک چند جمله ای است، بنابراین به طور نمایی سریعتر رشد نمی کند k بزرگتر می شود، همانطور که می شد k در نما بودند.

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

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

کوانتوم در حال انجام یک سری نظرسنجی برای ارائه خدمات بهتر به مخاطبانمان است. ما را بگیر نظرسنجی از خوانندگان ریاضی و شما برای برنده شدن رایگان وارد خواهید شد کوانتوم تجارت