একটি এআই রং করার ধাঁধার সমাধান করল

রেখা দিয়ে জোড়া বিন্দুর একটি জাল নিন — গণিতবিদেরা যাকে বলেন গ্রাফ। এবার বিন্দুগুলো এমনভাবে রং করুন যাতে একটি রেখায় যুক্ত দুটি বিন্দুর রং কখনো এক না হয়। যত কম রঙে এটা করা যায়, সেটিই গ্রাফের বর্ণসংখ্যা (chromatic number)। একটি বিখ্যাত বিশেষ ক্ষেত্র হলো চার-রঙের উপপাদ্য, যা ১৯৭৭ সালে প্রমাণিত হয়, আর যার শিরোনামই সব বলে দেয়: “Every planar map is four colorable” (প্রতিটি সমতল মানচিত্র চার রঙে রং করা যায়)।

হাডভিগারের ১৯৪৩ সালের বাজি

১৯৪৩ সালে হাডভিগার (Hadwiger) সব গ্রাফের জন্য একটি ব্যাপক নিয়ম প্রস্তাব করেন। বিন্দু বা রেখা মুছে, এবং দুটি যুক্ত বিন্দুকে একটিতে মিলিয়ে একটি গ্রাফকে ছোট করুন। ফলাফলটিকে বলে মাইনর (minor)। হাডভিগার এভাবে পাওয়া যায় এমন সবচেয়ে বড় সম্পূর্ণ গ্রাফের দিকে তাকিয়েছিলেন — এমন একটি গুচ্ছ যেখানে প্রতিটি বিন্দু বাকি সবগুলোর সঙ্গে যুক্ত — এবং অনুমান করেছিলেন যে প্রয়োজনীয় রঙের সংখ্যা কখনো সেই গুচ্ছের আকার ছাড়ায় না।

গবেষণাপত্রটি একে বলে “গ্রাফ তত্ত্বের সবচেয়ে পুরোনো ও সবচেয়ে মৌলিক সমস্যাগুলোর একটি”। এটি শুধু ছোট ক্ষেত্রগুলোর জন্য প্রমাণিত: পাঁচ পর্যন্ত গুচ্ছের জন্য, যেখানে এটি চার-রঙের উপপাদ্যের সমতুল্য বা তাতে রূপান্তরযোগ্য বলে দেখা যায়। ছয় থেকে শুরু করে এটি খোলা।

এক এক লগারিদম করে কাছে যাওয়া

যেহেতু সঠিক বক্তব্যটি ধরা দেয় না, গবেষকেরা গুচ্ছের আকারের এমন কোনো ফাংশন দিয়ে রঙের সংখ্যা সীমাবদ্ধ করার চেষ্টা করেছেন যা যতটা সম্ভব ধীরে বাড়ে। গবেষণাপত্রটি অগ্রগতির বিবরণ দেয়। কয়েক দশক ধরে, সেরা সীমা সমানুপাতের চেয়ে সামান্য দ্রুত বেড়েছে — একটি লগারিদমের বর্গমূলযুক্ত একটি গুণক দিয়ে। কয়েক বছর আগে, নরিন, পোস্টল ও সং (Norin, Postle, Song) সেই বাধা ভাঙেন। তারপর ডেলকুর ও পোস্টল (Delcourt, Postle) একে আরও উন্নত করেন এবং, সবচেয়ে গুরুত্বপূর্ণভাবে, দেখান যে বেশ ছোট গ্রাফ নিয়ে কাজ করাই যথেষ্ট। লিউ ও লুও (Liu, Luo) অতিরিক্ত গুণকটিকে ত্রিস্তর লগারিদমে নামিয়ে আনেন।

স্বাভাবিক গন্তব্য হলো রৈখিক হাডভিগার অনুমান (linear Hadwiger conjecture): গুচ্ছের আকারের একটি নির্দিষ্ট গুণিতক সবসময়ই যথেষ্ট। মন্ট্রিয়লের ম্যাকগিল বিশ্ববিদ্যালয়ের সের্গেই নরিন (Sergey Norin) এবং ইটিএইচ জুরিখের রাফায়েল স্টাইনার (Raphael Steiner) এখন ঠিক এটিই প্রমাণ করার দাবি করছেন।

যন্ত্রের ভূমিকা

লেখকেরা স্পষ্ট: প্রমাণটি খুঁজে পেয়েছে OpenAI-এর মডেল GPT-6 Astra, তাঁদের নির্দেশনা অনুসরণ করে। তাঁরা প্রথমে তাকে খুব ঘন গ্রাফের ক্ষেত্রটি প্রমাণ করতে বলেন, যেটিকে তাঁরা হারানো টুকরো বলে মনে করতেন। তাঁরা লেখেন, সে সফল হয়েছে “মাত্র কয়েক ঘণ্টা আর কিছুটা উৎসাহের পর”। একটি নির্ভরতাকে স্পষ্ট করতে বলা হলে, সে একটি নির্দিষ্ট আকার পর্যন্ত গ্রাফ কভার করেছে — কিন্তু প্রয়োজনীয় পরিসর পুরোপুরি নয়। তখন তাঁরা ফাঁকটি পূরণের জন্য তার কাছে একটি মৌলিক ধারণা চান, যা থেকে চূড়ান্ত প্রমাণের “বুটস্ট্র্যাপ” ধাপটি এসেছে। তাঁরা বলেন, সংকোচন (contractions) নিয়ে একটি পরামর্শ ছাড়া লেখকদের নিজস্ব নির্দিষ্ট প্রমাণ-ধারণার প্রায় কিছুই টেকেনি।

লেখাটি মানুষের। OpenAI-এর আরেকটি মডেল প্রুফরিডিং ও তথ্যসূত্র-তালিকায় সাহায্য করেছে। লেখকেরা জানান, OpenAI-এর Codex প্রমাণ-সহায়ক Lean-এ পুরো প্রমাণের একটি আনুষ্ঠানিক, যন্ত্রে যাচাইযোগ্য সংস্করণ তৈরি করেছে, যা এআই-এর লেখা একটি প্রাথমিক খসড়ার সঙ্গে অনলাইনে রাখা হয়েছে। গণিতের পূর্ণ দায়িত্ব তাঁরা নিজেরাই নেন।

প্রমাণের ভেতরে

যুক্তির দুটি অর্ধেক:

1. ছোট গ্রাফ, কম রং। গুচ্ছ-সীমার চেয়ে খুব বেশি বড় নয় এমন গ্রাফের জন্য, লেখকেরা দেখান যে গুচ্ছের আকারের প্রায় চার গুণ যথেষ্ট। সূচনাবিন্দু রিড ও সিমুরের (Reed, Seymour) ১৯৯৮ সালের একটি ফলাফল: রং করার একটি শিথিল, “ভগ্নাংশিক” রূপ ইতিমধ্যেই দুই গুণকসহ রৈখিক নিয়ম মেনে চলে। নতুন কাজটি গ্রাফে কয়েকটি অতিরিক্ত রেখা যোগ করে এবং একটি সহায়ক কাঠামোয় বিশাল মিলন (matchings) খুঁজে ভগ্নাংশিক রংকরণকে আসল রংকরণে রূপান্তর করে।
2. একটি বুটস্ট্র্যাপ। দ্বিতীয় একটি যুক্তি প্রতিটি ধাপে কভার করা গ্রাফ-আকারের পরিসর সূচকে চার-তৃতীয়াংশ গুণ বাড়ায়, বিনিময়ে ধ্রুবকটি বড় হয়। দশটি ধাপ পরিসরকে এক-তৃতীয়াংশ থেকে প্রায় ৫.৯২-এ নিয়ে যায়, যা ডেলকুর-পোস্টল রূপান্তরের জন্য প্রয়োজনীয় ৫-এর সীমা ছাড়িয়ে যায়। এই অর্ধেকটি গিয়ারফাশের (Gyárfás) একটি পুরোনো কৌশল ব্যবহার করে, যা লেখকদের মতে এই সমস্যায় আগে কখনো প্রয়োগ করা হয়নি।

লেখকেরা প্রমাণটিকে পরিচিত সরঞ্জাম দিয়ে তৈরি বলে বর্ণনা করেন — “বিদ্যমান ফলাফলগুলোর উত্তল আবরণের (convex hull) ভেতরে”, তবু তার কোনো স্পষ্ট প্রান্তে নয়।

যা খোলা থাকল

ধ্রুবকটি বিশাল: একটি মোটা হিসাবে প্রায় ১০¹⁰⁰। লেখকেরা এটিকে ১০¹⁰-এর নিচে নামানোর সুযোগ দেখেন, কিন্তু মনে করেন, ধরা যাক, ১০০-তে পৌঁছাতে নতুন ধারণা লাগবে। হাডভিগারের সঠিক অনুমান অক্ষত: “আমরা সিদ্ধান্তে পৌঁছাইনি,” তাঁরা লেখেন। গবেষণাপত্রটি একটি প্রিপ্রিন্ট; নতুন গণিতের ৪১ পৃষ্ঠা এখন অন্য বিশেষজ্ঞদের খুঁটিয়ে দেখার মুখোমুখি হবে।