যে বৃহত্তম অঙ্ক পরিশোধ করা যায় না, এবার তা আঁটসাঁট সীমায় বাঁধা

এমন একটি ক্যাশ কাউন্টার কল্পনা করুন, যা কেবল কয়েক ধরনের মুদ্রা নেয়, যেগুলোর জোগান অফুরন্ত, আর যা কখনো খুচরো ফেরত দেয় না। কিছু অঙ্ক ঠিক ঠিক পরিশোধ করা যায়; কিছু কখনোই যায় না। গণিতবিদেরা এই মুদ্রা-মূল্যগুলোকে বলেন উৎপাদক-মৌল (generators), আর একটি আপাতসরল প্রশ্ন তোলেন: যে অঙ্ক পরিশোধ করা যায় না, তার মধ্যে বৃহত্তমটি কত?

যে অঙ্কগুলো কখনো পরিশোধ করা যায় না

এমন পূর্ণসংখ্যা a₁ < a₂ < … < aₙ নিন, যাদের সবার মধ্যে কোনো সাধারণ উৎপাদক নেই। এই সংখ্যাগুলোর প্রতিটিকে যতবার খুশি নিয়ে যোগ করলে যে মোট পাওয়া যায়, তাকে বলা হয় “প্রকাশযোগ্য”। কেবল সসীমসংখ্যক পূর্ণসংখ্যা প্রকাশযোগ্য নয়; তাদের মধ্যে বৃহত্তমটি হলো ফ্রোবেনিয়াস সংখ্যা, F। (মূল্যগুলোর একটি 1 হলে সবকিছুই পরিশোধ করা যায়, আর F-কে −1 ধরা হয়।)

একটি ছোট উদাহরণ: 3, 4 ও 6-এর মুদ্রা দিয়ে আপনি 3, 4, 6, 7, 8 এবং তারপরের প্রতিটি অঙ্ক পরিশোধ করতে পারেন, কিন্তু 1, 2 বা 5 কখনোই নয়। তাই F = 5। লক্ষ করুন, 3 ও 6-এর একটি সাধারণ উৎপাদক আছে; আসল কথা হলো, তিনটির সবার মধ্যে সাধারণ কোনো উৎপাদক নেই।

দুটি মুদ্রার জন্য একটি নির্ভুল উত্তর আছে, সিলভেস্টারের সূত্র: F(a₁, a₂) = a₁a₂ − a₁ − a₂। তিন বা তার বেশির ক্ষেত্রে কাজটি হলো F-কে সীমায় বাঁধা: প্রমাণ করা যে মুদ্রাগুলো থেকে হিসাব করা কোনো একটি মানকে এটি ছাড়াতে পারে না।

2-এর এক নাছোড় গুণক

পল এর্দোশ (Paul Erdős) ও রোনাল্ড গ্রাহাম (Ronald Graham) তিন বা তার বেশি উৎপাদক-মৌলের জন্য প্রমাণ করেছিলেন:

F ≤ 2aₙ₋₁⌊aₙ/n⌋ − aₙ

এখানে aₙ বৃহত্তম মূল্য, aₙ₋₁ দ্বিতীয় বৃহত্তম, n মূল্যের সংখ্যা, আর ⌊ ⌋ মানে নিচের দিকে পূর্ণসংখ্যায় নামানো। সিলভেস্টারের সূত্রের মতোই এতে বৃহত্তম দুটি মুদ্রা জড়িত।

তাঁরা সবচেয়ে খারাপ পরিস্থিতিরও একটি আনুমানিক হিসাব দিয়েছিলেন, অর্থাৎ n-টি মূল্যের সবগুলো বড়জোর t হলে F-এর সম্ভাব্য বৃহত্তম মান। তাঁদের অনুমানগুলোর মধ্যকার ফারাক, মোটামুটি 2-এর একটি গুণক, একটি অনুমিতির (কনজেকচার) জন্ম দেয়, যা এর্দোশ সমস্যা #433 (Erdős Problem #433) নামে নথিভুক্ত। জাক ডিক্সমিয়ে (Jacques Dixmier) সেটির সমাধান করেন, এবং প্রতিটি সমষ্টির জন্য প্রযোজ্য একটি সরলতর সীমাও প্রমাণ করেন: F ≤ aₙ²/(n − 1)। 2-এর গুণক বিদায় নিল, কিন্তু সঙ্গে দ্বিতীয় বৃহত্তম মুদ্রাটিও।

বৃহত্তম দুটি মুদ্রাই রেখে দেওয়া

ঝেজিয়াং বিশ্ববিদ্যালয়ের কম্পিউটার বিজ্ঞান ও প্রযুক্তি কলেজের লিন চেন (Lin Chen), তিংওয়েই হু (Tingwei Hu), ইউচেন মাও (Yuchen Mao) ও গুওচুয়ান ঝাং (Guochuan Zhang) দুটোই চেয়েছিলেন: 2-এর গুণক থাকবে না, আর দ্বিতীয় বৃহত্তম মুদ্রাটি থেকে যাবে। তাঁদের উত্তর, যা দুই বা ততোধিক মূল্যের যেকোনো সমষ্টির জন্য প্রযোজ্য:

F ≤ aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ − 1

এখানে ⌈ ⌉ মানে ওপরের দিকে পূর্ণসংখ্যায় তোলা। এর্দোশ ও গ্রাহামের তুলনায় 2-এর গুণকটি উধাও হয়েছে, তার মূল্য হিসেবে n-এর বদলে n − 1 দিয়ে ভাগ করতে হয় এবং ওপরের দিকে পূর্ণসংখ্যায় তুলতে হয়। ডিক্সমিয়ের তুলনায়, দ্বিতীয় বৃহত্তম মুদ্রাটি বৃহত্তমটির পাশে ছোট হলে নতুন সীমাটি উল্লেখযোগ্যভাবে ছোট হতে পারে।

3, 4, 6-এর উদাহরণে এর্দোশ ও গ্রাহামের সীমা দেয় 10, ডিক্সমিয়ের দেয় 18, আর নতুনটি দেয় 4 × 3 − 6 − 1 = 5, ঠিক প্রকৃত মান। এতে অবাক হওয়ার কিছু নেই: এই সমষ্টিটি নিচে বর্ণিত চরম উদাহরণের পরিবারের অন্তর্ভুক্ত, যেগুলো ঠিক সীমায় পৌঁছানোর জন্যই গড়া; গবেষণাপত্রটি সাধারণ সমষ্টিগুলোর ওপর কোনো তুলনা দেয় না।

ভাগশেষ অনুযায়ী অঙ্ক সাজানো

প্রমাণটি এর্দোশ ও গ্রাহামের পথ ধরে চলে। প্রতিটি অঙ্ককে বৃহত্তম মুদ্রা aₙ দিয়ে ভাগ করার পর যে ভাগশেষ থাকে, সেই অনুযায়ী সাজান। ছোট মুদ্রাগুলোর কোনো যোগফল একবার কোনো নির্দিষ্ট ভাগশেষে পৌঁছালে, তাতে aₙ-এর কয়েকটি কপি যোগ করে সেই ভাগশেষের প্রতিটি বড় অঙ্কে পৌঁছানো যায়। কাজটি হলো দেখানো যে প্রতিটি ভাগশেষে কম খরচে পৌঁছানো যায়।

মূল হাতিয়ার হলো ক্নেজারের উপপাদ্য (Kneser’s theorem), যা বলে যোগফলের একটি সেট অন্তত কত বড় হতে হবে। এর্দোশ ও গ্রাহাম এটি ব্যবহার করে দেখিয়েছিলেন যে প্রায় aₙ/n-টি মুদ্রার যোগফল অর্ধেকের বেশি ভাগশেষ ঢেকে ফেলে, তারপর মুদ্রার সংখ্যা দ্বিগুণ করে সবগুলো ঢেকে দেন। এই যোগফলগুলোর প্রতিটি মুদ্রার মূল্য বড়জোর aₙ₋₁, তাই মুদ্রার সংখ্যা দ্বিগুণ করলে খরচও দ্বিগুণ হয়: সেখান থেকেই 2-এর গুণক।

নতুন প্রমাণটি ⌈aₙ/(n − 1)⌉-টি মুদ্রার যোগফল ব্যবহার করে। এই যোগফলগুলো কিছু ভাগশেষ বাদ দিয়ে ফেললে, ক্নেজারের উপপাদ্য বলে যে বাদ পড়াগুলো এলোমেলোভাবে ছড়ানো নয়: তারা নিয়মিত ব্যবধানে বিন্যস্ত ভাগশেষের পুরো পুরো পরিবার গঠন করে। যত বেশি পরিবার বাদ পড়ে, ছোট মুদ্রাগুলোকে ততই বেশি করে প্রতিটি নাগাল-পাওয়া পরিবারে ভিড় করতে হয়, ফলে ওই পরিবারগুলোর প্রতিটিতে কিছু ছোট মুদ্রা থাকে, আর বাদ পড়া পরিবারগুলোতে পৌঁছাতে যে অল্প কয়েকটি বাড়তি মুদ্রা লাগে, সেগুলো সস্তা পড়ে। মোট খরচ কখনো ⌈aₙ/(n − 1)⌉ × aₙ₋₁ ছাড়ায় না।

এই প্রথম ধাপটি সীমা দেয় তার শেষ “− 1” ছাড়া। শেষ এককটি আসে একটি আলাদা যুক্তি থেকে, যা শার্ক (Scherk) ও কেম্পারম্যানের (Kemperman) একটি উপপাদ্যের ওপর দাঁড়িয়ে, যে উপপাদ্য এমন যোগফল নিয়ে যা কেবল একভাবেই গঠন করা যায়: এটি দেখায় যে সীমান্তবর্তী অঙ্ক aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ নিজেও সবসময় পরিশোধ করা যায়। কৃতজ্ঞতা-স্বীকার অংশ অনুযায়ী, লেখকেরা প্রথমে দুর্বলতর সীমাটি প্রমাণ করেছিলেন; তারপর GPT-6 সেটিকে এক কমানোর যুক্তি খুঁজে পেতে সাহায্য করে, এবং সীমাটি যে আর নামানো যায় না তার প্রমাণে ও ইংরেজি সম্পাদনাতেও সহায়তা করে। লেখকেরা জানিয়েছেন, চূড়ান্ত পাণ্ডুলিপির দায় তাঁরা নিজেরাই নিচ্ছেন।

যে উদাহরণগুলো ঠিক সীমা ছোঁয়

এই সীমা আর নামানো যায় না: প্রতিটি n ≥ 3-এর জন্য লেখকেরা অসীমসংখ্যক এমন সমষ্টি গড়েছেন যেখানে F ঠিক এর সমান। যেকোনো q ≥ 2 নিন এবং মূল্যগুলো q, 2q, …, (n − 1)q, সঙ্গে (n − 2)q + 1। একটি বাদে সবগুলোই q-এর গুণিতক, তাই এরা এমন কিছু পরিশোধ করে না যা একা q পারে না। সমষ্টিটি দুটি মুদ্রা, q ও (n − 2)q + 1-এর মতো আচরণ করে, আর সিলভেস্টারের সূত্র এমন একটি F দেয় যা নতুন সীমার সঙ্গে হুবহু মেলে। n = 3 ও q = 3 নিলে এই প্রণালী ঠিক ওপরের 3, 4, 6-এর উদাহরণটিই তৈরি করে।

কম মুদ্রা, নিচু ছাদ

সীমাটিকে ঘনত্বের ভাষাতেও পড়া যায়। এটি i-টি ক্ষুদ্রতম মূল্য আর বৃহত্তমটি নিয়ে গঠিত যেকোনো ছাঁটা সমষ্টির ক্ষেত্রে প্রযোজ্য, যতক্ষণ সেগুলোর মধ্যে তখনও কোনো সাধারণ উৎপাদক না থাকে। মুদ্রা সরালে পরিশোধ করা কেবল কঠিনই হতে পারে, তাই ছাঁটা সমষ্টির জন্য প্রমাণিত ছাদ পূর্ণ সমষ্টির জন্যও খাটে। ফলাফল নিয়ন্ত্রণ করে মোটামুটি aᵢ/i, অর্থাৎ প্রথম i-টি মূল্য 1 থেকে aᵢ পর্যন্ত সংখ্যাগুলো কতটা ঘনভাবে ভরায়, তার বিপরীত: সবচেয়ে ঘন দলটিই জেতে। লেখকেরা বিশেষভাবে উল্লেখ করেছেন, বাকি মুদ্রাগুলোর সবার মধ্যে কোনো সাধারণ উৎপাদক না থাকলেই দ্বিতীয় বৃহত্তম মুদ্রাটিকে সরাসরি সরিয়ে রাখা যায়।

গবেষণাপত্রটি সম্পূর্ণ তাত্ত্বিক: সাধারণ মুদ্রা-সমষ্টিতে নতুন সীমা কতটা ছোট, তার কোনো সংখ্যা এটি দেয় না, আর এর নিখুঁততা (sharpness) প্রমাণিত হয়েছে কেবল তিন বা তার বেশি মুদ্রা-মূল্যের ক্ষেত্রে।