برای رنگ کردن فضا چند رنگ لازم است؟ برای یک خط‌کش معمولی، نه بیش از 2d
همهٔ نقاط یک صفحهٔ تخت را بردارید و به هر کدام رنگی بدهید. یک قاعده: دو نقطه که دقیقاً یک واحد از هم فاصله دارند هرگز نباید هم‌رنگ باشند. کمترین تعداد رنگی که جواب می‌دهد چیست؟
این مسئلهٔ هادویگر–نلسون است که به 1950 برمی‌گردد و به گفتهٔ نویسندگان، یکی از مشهورترین مسائل باز هندسهٔ گسسته است. مدت‌ها می‌دانستند پاسخ بین 4 و 7 است. یک پیشرفت اخیر کران پایین را به 5 رساند. پاسخ دقیق هنوز ناشناخته است.
عوض کردن خط‌کش
لازم نیست فاصله را با خط‌کش معمولی بسنجیم. ریاضی‌دانان نُرم‌های (norms) بسیار دیگری تعریف می‌کنند — شیوه‌هایی برای اندازه‌گیری طول — که هر کدام با «گوی واحد» خود توصیف می‌شود، یعنی مجموعهٔ نقاطی که فاصله‌شان از مرکز حداکثر 1 است. برای فاصلهٔ معمولی این یک گوی گرد است؛ برای نُرم‌های دیگر می‌تواند هر شکل محدبِ متقارن نسبت به مرکزش باشد.
برای هر نُرمی روی صفحه، پاسخ معمای رنگ‌آمیزی بین 4 و 7 است. در d بُعد، برای هر نُرمی حداکثر نمایی بر حسب d است، و برای بسیاری از نُرم‌های طبیعی — از جمله نُرم اقلیدسی معمولی — دست‌کم نمایی هم هست: تعداد رنگ‌ها با بالا رفتن بُعد منفجر می‌شود.
آیا این انفجار قاعده است؟ نوگا آلون (دانشگاه پرینستون و دانشگاه تل‌آویو)، ماتیا بوچیچ (دانشگاه وین) و جیمز دیویس (دانشگاه لایپزیگ) به یک نُرم معمولی (typical) نگاه کردند. هیچ راه طبیعی‌ای برای انتخاب «تصادفی» یک نُرم وجود ندارد، پس آن‌ها از مفهومی توپولوژیک استفاده می‌کنند: یک ویژگی برای نُرم معمولی برقرار است اگر استثناها مجموعه‌ای ناچیز («لاغر»، meagre) تشکیل دهند. کار پیشین آلون، بوچیچ و لیزا زاوئرمان نشان داده بود که یک نُرم معمولی حداکثر به 2ᵈ رنگ نیاز دارد، و پرسیده بود این چقدر به حقیقت نزدیک است.
خطی، نه نمایی
پاسخ: بسیار دور. مقالهٔ جدید ثابت می‌کند که
- برای یک نُرم معمولی روی فضای d بُعدی، 2d رنگ همیشه کافی است؛
- این بهترین حالت ممکن است: یک مجموعهٔ باز از نُرم‌ها دست‌کم 2d رنگ لازم دارد. پس برخی نُرم‌ها دقیقاً 2d رنگ نیاز دارند.
در ده بُعد، یک نُرم معمولی حداکثر بیست رنگ لازم دارد، در حالی که فاصلهٔ معمولی به تعدادی نیاز دارد که به‌صورت نمایی رشد می‌کند. به گفتهٔ نویسندگان، این همچنین نخستین بار است که عدد رنگ‌آمیزی برای یک نُرم «اکیداً محدب» در هر بُعد d دقیقاً تعیین می‌شود.
کران پایین از تلهٔ زیرکانه‌ای استفاده می‌کند. 2d نقطه پیدا کنید که همه دقیقاً یک واحد از یکدیگر فاصله دارند، جز دو نقطه، a و b، که نیم واحد از هم فاصله دارند. تصویر آینه‌ای کل این پیکربندی را نسبت به a اضافه کنید. با کمتر از 2d رنگ، هم b و هم تصویر آینه‌ای‌اش مجبور می‌شوند رنگ a را بگیرند — اما آن دو دقیقاً یک واحد از هم فاصله دارند. تناقض. یک لم پایداری نشان می‌دهد این پیکربندی از هر تغییر کوچک نُرم جان سالم به در می‌برد.
دوندهٔ تنها در ابعاد بالا
کران بالا هر نقطه را بر اساس جایی رنگ می‌کند که تصویرِ یک تابش (projection) خوش‌انتخاب از آن، در برش‌هایی به پهنای 1/(2d)، فرود می‌آید. برای کار کردنش به عنصری کلیدی نیاز است که نویسندگان آن را نسخه‌ای ماتریسی و با ابعاد بالا از حدس مشهور دوندهٔ تنها (lonely runner conjecture) توصیف می‌کنند:
sup over x of minᵢ ‖aᵢ · x − bᵢ‖ ≥ k / (2n)
که در آن ‖t‖ فاصلهٔ t تا نزدیک‌ترین عدد صحیح است، برای هر n بردار aᵢ در k بُعد که هر k تا از آن‌ها مستقل باشند. این گزاره همچنین حدس 1978 آی. جی. شونبرگ دربارهٔ «انسداد دید» (view obstruction) را حل می‌کند — پرسشی دربارهٔ اینکه تیغه‌های متناوب باید چقدر ضخیم باشند تا هر دیدی به بی‌نهایت را ببندند — که نویسندگان آن را یکی از کلاسیک‌ترین مسائل باز این حوزه می‌دانند، و نیز حدس مرتبطی از هنتسه و مالیکیوسیس را.
ماشین در بخش قدردانی
نویسندگان صریح‌اند: «ChatGPT 6 Pro اثبات آخرین عنصری را که در اثبات قضیهٔ 1 لازم داشتیم، یعنی اثبات لم 7، پس از گفت‌وگویی طولانی به ما ارائه داد»؛ گفت‌وگویی که در آن مشاهدات خودشان — از جمله ایدهٔ استقرا و راهبرد کلی — را در میان گذاشته بودند. «استدلال کران پایین نیز با کمک ChatGPT 6 Pro یافته شد.»
پرسش‌هایی باقی است. مقدار دقیق 2d روی یک مجموعهٔ باز از نُرم‌ها ثابت شده، نه برای همهٔ نُرم‌های معمولی. و برای فاصلهٔ اقلیدسی معمولی، نویسندگان انتظار دارند در هر بُعدی اکیداً بیش از 2d رنگ لازم باشد — چیزی که در ابعاد 2، 4، 7، 8 و 9 به بالا از پیش معلوم است، اما در ابعاد 3، 5 و 6 هنوز باز است.