سب سے بڑی ناقابلِ ادا رقم کی اب ایک بالکل کسی ہوئی حد

ایک ایسے کیش کاؤنٹر کا تصور کیجیے جو صرف چند قسم کے سکے قبول کرتا ہے، جو لامحدود تعداد میں دستیاب ہیں، اور کبھی ریزگاری واپس نہیں دیتا۔ کچھ رقمیں ٹھیک ٹھیک ادا ہو سکتی ہیں؛ کچھ کبھی نہیں۔ ریاضی دان سکوں کی قیمتوں کو مولِّد (generators) کہتے ہیں اور ایک بظاہر سادہ مگر دھوکا دینے والا سوال پوچھتے ہیں: وہ سب سے بڑی رقم کون سی ہے جو ادا نہیں کی جا سکتی؟

وہ رقمیں جو کبھی ادا نہیں ہو سکتیں

ایسے مکمل اعداد a₁ < a₂ < … < aₙ لیجیے جن سب میں کوئی مشترک جزوِ ضربی نہ ہو۔ ان اعداد کو جمع کر کے، ہر ایک کو جتنی بار چاہیں لے کر، جو کل حاصل ہو وہ “قابلِ اظہار” (representable) کہلاتا ہے۔ صرف محدود تعداد میں مکمل اعداد ایسے ہیں جو قابلِ اظہار نہیں؛ ان میں سب سے بڑا فروبینیس عدد، F، ہے۔ (اگر قیمتوں میں سے ایک 1 ہو تو ہر رقم ادا ہو سکتی ہے اور F کو −1 مقرر کیا جاتا ہے۔)

ایک چھوٹی سی مثال: 3، 4 اور 6 کے سکوں سے آپ 3، 4، 6، 7، 8 اور اس کے بعد کی ہر رقم ادا کر سکتے ہیں، لیکن 1، 2 یا 5 کبھی نہیں۔ لہٰذا F = 5۔ غور کیجیے کہ 3 اور 6 میں ایک مشترک جزوِ ضربی ہے؛ اہم بات یہ ہے کہ تینوں میں کوئی جزوِ ضربی مشترک نہ ہو۔

دو سکوں کے لیے ایک قطعی جواب موجود ہے، سلویسٹر (Sylvester) کا فارمولا: F(a₁, a₂) = a₁a₂ − a₁ − a₂۔ تین یا زیادہ کے لیے کام F کی حد بندی ہے: یہ ثابت کرنا کہ F سکوں سے نکالی گئی کسی قیمت سے تجاوز نہیں کر سکتا۔

2 کا ایک ضدی جزوِ ضربی

پال ایردوش (Paul Erdős) اور رونالڈ گراہم (Ronald Graham) نے تین یا زیادہ مولِّدوں کے لیے ثابت کیا:

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

یہاں aₙ سب سے بڑی قیمت ہے، aₙ₋₁ دوسری سب سے بڑی، n قیمتوں کی تعداد، اور ⌊ ⌋ کا مطلب ہے نیچے کی طرف پورا کرنا (rounding down)۔ سلویسٹر کے فارمولے کی طرح اس میں بھی دو سب سے بڑے سکے شامل ہیں۔

انہوں نے بدترین صورت کا اندازہ بھی لگایا، یعنی سب سے بڑا ممکنہ F جب تمام n قیمتیں زیادہ سے زیادہ t ہوں۔ ان کے اندازوں کے درمیان تقریباً 2 گنا کا فرق ایک قیاس (conjecture) کا سبب بنا جو ایردوش مسئلہ نمبر 433 (Erdős Problem #433) کے طور پر درج ہے۔ ژاک دکسمیئر (Jacques Dixmier) نے اسے حل کیا، اور ایک سادہ تر حد بھی ثابت کی جو ہر مجموعے پر لاگو ہوتی ہے: F ≤ aₙ²/(n − 1)۔ 2 کا جزوِ ضربی غائب ہو گیا، مگر دوسرا سب سے بڑا سکہ بھی۔

دونوں سب سے بڑے سکوں کو برقرار رکھنا

جےجیانگ یونیورسٹی (Zhejiang University) کے کالج آف کمپیوٹر سائنس اینڈ ٹیکنالوجی کے لِن چن، ٹنگوے ہو، یوچن ماؤ اور گوچوان ژانگ (Lin Chen, Tingwei Hu, Yuchen Mao, Guochuan Zhang) دونوں چیزیں چاہتے تھے: نہ 2 کا جزوِ ضربی ہو، اور دوسرا سب سے بڑا سکہ بھی برقرار رہے۔ ان کا جواب، جو دو یا زیادہ قیمتوں کے کسی بھی مجموعے کے لیے درست ہے:

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

یہاں ⌈ ⌉ کا مطلب ہے اوپر کی طرف پورا کرنا (rounding up)۔ ایردوش اور گراہم کے مقابلے میں 2 کا جزوِ ضربی غائب ہو گیا ہے، اس قیمت پر کہ n کے بجائے n − 1 سے تقسیم کیا جاتا ہے اور اوپر کی طرف پورا کیا جاتا ہے۔ دکسمیئر کے مقابلے میں نئی حد کافی چھوٹی ہو سکتی ہے جب دوسرا سب سے بڑا سکہ سب سے بڑے کے مقابلے میں چھوٹا ہو۔

3، 4، 6 والی مثال پر ایردوش اور گراہم کی حد 10 دیتی ہے، دکسمیئر کی 18، اور نئی حد 4 × 3 − 6 − 1 = 5، یعنی بالکل اصل قیمت۔ اس میں حیرت کی کوئی بات نہیں: یہ مجموعہ نیچے بیان کردہ انتہائی مثالوں کے اس خاندان سے تعلق رکھتا ہے جو حد تک بالکل ٹھیک پہنچنے کے لیے بنایا گیا ہے؛ مقالہ عام مجموعوں پر کوئی موازنہ پیش نہیں کرتا۔

رقموں کو باقی کے لحاظ سے چھانٹنا

ثبوت ایردوش اور گراہم کا راستہ اپناتا ہے۔ ہر رقم کو سب سے بڑے سکے، aₙ، سے تقسیم کرنے کے بعد بچنے والے باقی (remainder) کے لحاظ سے چھانٹیے۔ جب چھوٹے سکوں کا کوئی مجموعہ کسی خاص باقی تک پہنچ جائے تو 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ᵢ تک کے اعداد کو کتنی گھنی طرح بھرتی ہیں: سب سے گھنا گروہ جیت جاتا ہے۔ خاص طور پر، مصنفین نوٹ کرتے ہیں کہ جب بھی باقی سکوں میں اب بھی سب کا کوئی مشترک جزوِ ضربی نہ ہو، دوسرے سب سے بڑے سکے کو بس ایک طرف رکھا جا سکتا ہے۔

مقالہ خالصتاً نظریاتی رہتا ہے: یہ کوئی عدد نہیں دیتا کہ عام سکوں کے مجموعوں پر نئی حد کتنی چھوٹی ہے، اور اس کا قطعی ہونا (یعنی یہ کہ اسے نیچے نہیں لایا جا سکتا) صرف تین یا زیادہ قیمتوں کے لیے ثابت کیا گیا ہے۔