সূর্যমুখী অনুমানের পতন

1 থেকে n পর্যন্ত সংখ্যাগুলো নিন এবং তাদের কয়েকটি বাছাই করার সব উপায় দেখুন: এমন উপসেট আছে 2ⁿটি। এবার কয়েকটি উপসেট বাছুন, যাদের ঠিক একই সাধারণ অংশ আছে, আর কিছু নয়। গণিতবিদেরা একে বলেন সূর্যমুখী: সাধারণ অংশটি কেন্দ্র, আর প্রতিটি সেটের বাকি অংশ একটি পাপড়ি, যা অন্য কোনো পাপড়িকে ছোঁয় না।

সূর্যমুখী সমাবেশতত্ত্বের (কম্বিনেটোরিক্স) একটি মৌলিক হাতিয়ার। গবেষণাপত্রটি এর যোগসূত্র তালিকাভুক্ত করে কিছু যুক্তি-সার্কিটের সীমা, “ক্যাপ সেট” সমস্যা, দ্রুত ম্যাট্রিক্স গুণ এবং তথ্যতত্ত্বের সঙ্গে।

1970 সালের একটি প্রশ্ন

লেখকদের মতে, এদের নিয়ে সবচেয়ে স্বাভাবিক প্রশ্নটি ফিরে যায় Paul Erdős-এর 1970 সালের একটি গবেষণাপত্রে। {1, …, n}-এর উপসেটের একটি সংগ্রহ কত বড় হতে পারে, যদি তার কোনো k-টি সেট সূর্যমুখী তৈরি না করে?

1970-এর দশকে Erdős ও Endre Szemerédi অনুমান করেন যে এমন সংগ্রহ 2ⁿটি সম্ভাব্য উপসেটের চেয়ে সূচকীয়ভাবে ছোট হতেই হবে: সর্বোচ্চ cⁿ, এমন কোনো সংখ্যা c-এর জন্য যা কঠোরভাবে 2-এর কম।

কয়েক দশক ধরে সেরা সীমাগুলো কেবল সামান্য কমাতে পেরেছিল, কখনো এতটা নয় যে ভিত্তি 2-এর নিচে নামে। কেবল তিন-পাপড়ির ক্ষেত্রটি (k = 3) মীমাংসিত হয়েছিল 2016 সালে, ক্যাপ সেট সমস্যার যুগান্তকারী অগ্রগতি এবং Alon, Shpilka ও Umans-এর একটি রূপান্তরের (রিডাকশন) মাধ্যমে।

সীমা

Matija Bucić ও Fankang He (ভিয়েনা বিশ্ববিদ্যালয়) এবং Hyunwoo Lee (KAIST ও ইনস্টিটিউট ফর বেসিক সায়েন্স, দক্ষিণ কোরিয়া) অনুমানটি প্রমাণ করেছেন প্রতিটি k ≥ 3-এর জন্য। তাঁদের মূল উপপাদ্য: k-পাপড়ির সূর্যমুখীবিহীন একটি সংগ্রহে সদস্য থাকে সর্বোচ্চ

3 · (2 − 1/(16k³))ⁿ

টি। ভিত্তিটি 2-এর ঠিক নিচে, কিন্তু এটি 2-এর নিচের একটি নির্দিষ্ট সংখ্যা, আর ঠিক এটাই Erdős ও Szemerédi চেয়েছিলেন। 1997 সালের একটি নির্মাণ দেখায় যে বড় k-এর জন্য প্রকৃত মান এর চেয়ে খুব বেশি কম হতে পারে না।

সেট থেকে ভেক্টরে

প্রমাণটি এগোয় সমস্যাটির ভেক্টর-সংস্করণের মধ্য দিয়ে। সংখ্যাগুলোকে D উপাদানের n-টি খণ্ডে ভাগ করুন এবং প্রতিটি খণ্ড থেকে একটি উপাদান বাছুন: প্রতিটি বাছাই একটি ভেক্টর। কয়েকটি ভেক্টর সূর্যমুখী তৈরি করে, যখন প্রতিটি অবস্থানে তাদের উপাদানগুলো হয় সব সমান, নয় সব আলাদা।

এরপর লেখকেরা একটি “সূর্যমুখী-পরীক্ষক” তৈরি করেন: এমন একটি ফাংশন, যা সূর্যমুখীমুক্ত সংগ্রহে কেবল তখনই অশূন্য, যখন তার সব ইনপুট একই ভেক্টর। নতুন উপাদানটি হলো এই ফাংশনকে ধাপে ধাপে নিম্ন মাত্রার অন্তর্বেশন (ইন্টারপোলেশন) বহুপদী দিয়ে লেখা। সেই বহুপদীগুলো গুনলে সংগ্রহের আকারের সীমা পাওয়া যায় (তাঁদের উপপাদ্য 2)। একটি সম্ভাবনাভিত্তিক যুক্তি, অর্থাৎ সব সেট-আকারের ওপর গড় করা দৈব খণ্ড, সীমাটিকে আবার সাধারণ সেটে ফিরিয়ে আনে।

এক যন্ত্রের খোঁজ, আরেক যন্ত্রের যাচাই

AI নিয়ে গবেষণাপত্রের বিবৃতি অস্বাভাবিক রকম সরাসরি। উপপাদ্য 2-এর প্রমাণ খুঁজে পেয়েছে ChatGPT 6 Astra Pro, একটি ছোট আলোচনার পরে, যা শুরু হয়েছিল তাকে জানা তিন-পাপড়ির যুক্তিটি সাধারণীকরণ করতে বলে। লেখকদের এই ধাপটি দরকার ছিল অন্য একটি লক্ষ্যের জন্য: Szemerédi-র উত্থাপিত একটি গ্রাফ-সমস্যার একটি আরোপিত (induced) সংস্করণ, যা তাঁরা পরের একটি নোটে প্রকাশের ঘোষণা দিয়েছেন।

মডেলটি তার প্রমাণ লিখেছিল “স্লাইস র‍্যাঙ্ক”-এর ভাষায়। লেখকেরা সেটি বহুপদী পদ্ধতির ভাষায় নতুন করে লিখেছেন, যা তাঁদের মতে পাঠকের পক্ষে সহজ। তাঁরা জানান, প্রতিটি ফলাফল তাঁরা যাচাই করেছেন এবং পূর্ণ দায়িত্ব নিচ্ছেন, আর প্রমাণটি Lean 4.35-এ যাচাই করা হয়েছে, যা একটি প্রমাণ-যাচাই সফটওয়্যার, এবং যাচাইটি Palomar রিপোজিটরিতে প্রকাশ করা হবে।

যা এটি মীমাংসা করে না

লেখকেরা ভিত্তিটি অনুকূলিত করার চেষ্টা করেননি। তিন পাপড়ির ক্ষেত্রে এটি Naslund ও Sawin-এর 2017 সালের প্রায় 1.89-এর সীমাকে ছাড়িয়ে যায় না। আর আরও শক্তিশালী বোন-সমস্যাটি, Erdős–Rado সূর্যমুখী অনুমান, এখনও খোলা: তাঁদের সীমাগুলো এখনও খণ্ডের আকার D-এর ওপর অনেকটাই নির্ভরশীল, আর ঠিক এটাই সেই সমস্যা নিষেধ করে।