مساوات حل کرنے کی رفتار کی ایک حد جو 1974 میں پیش ہوئی، آخرکار ثابت

یہ معلوم کرنے کے لیے کہ کوئی فنکشن f کہاں صفر کو کاٹتا ہے، کمپیوٹر اکثر ایک تکرار (iteration) چلاتا ہے: ایک اندازے x سے شروع کریں، فنکشن سے چند سوال پوچھیں، ایک بہتر اندازہ نکالیں، اور یہی دہرائیں۔ یہ سوال قدر پیمائیاں (evaluations) ہیں: کسی نقطے پر f کی قدر، یا اس کی ڈھلان (مشتق، derivative) کی، یا کسی بلند تر مشتق کی۔

دگنے ہوتے ہندسے

ایسے طریقے کی رفتار اس کے درجے (order) سے ناپی جاتی ہے۔ اگر موجودہ غلطی ε ہو، تو درجہ p کی ایک تکرار تقریباً ε کی طاقت p کے برابر غلطی چھوڑتی ہے۔ درجہ 2 کا مطلب ہے کہ جواب کے قریب، درست ہندسوں کی تعداد ہر قدم پر دگنی ہو جاتی ہے؛ درجہ 4 کا مطلب کہ وہ چار گنا ہو جاتی ہے۔

نیوٹن کا طریقہ ہر قدم پر دو قدر پیمائیاں خرچ کرتا ہے — f(x) اور اس کی ڈھلان f′(x) — اور x − f(x)/f′(x) پر چلا جاتا ہے۔ اس کا درجہ 2 ہے۔ فی قدم زیادہ سوال پوچھنے سے زیادہ رفتار خریدی جا سکتی ہے۔ سوال یہ ہے کہ کتنی۔

1974 کا ایک حدسیہ

1974 میں H. T. Kung اور J. F. Traub نے Journal of the ACM کے ایک مقالے میں “Conjecture 8.1” کے طور پر ایک جواب تجویز کیا: بغیر حافظے والی ایک تکرار جو فی قدم n قدر پیمائیاں استعمال کرتی ہے، اس کا درجہ زیادہ سے زیادہ 2ⁿ⁻¹ ہوتا ہے۔ “بغیر حافظے” کا مطلب ہے کہ طریقہ اپنے موجودہ اندازے کے سوا پچھلے قدموں سے کچھ بھی محفوظ نہیں رکھتا۔

اس حد کو نیچے نہیں لایا جا سکتا تھا: Kung اور Traub نے خود ایسے “کثیر نقطی” (multipoint) طریقے بنائے تھے جو ہر n ≥ 2 کے لیے 2ⁿ⁻¹ تک پہنچتے تھے — تین قدر پیمائیوں کے ساتھ درجہ 4، چار کے ساتھ 8، پانچ کے ساتھ 16۔ جو کمی تھی وہ دوسرا نصف تھا: یہ ثبوت کہ کوئی بھی طریقہ اس سے بہتر نہیں کر سکتا۔ جزوی نتائج حدسیے کے ساتھ اور اس کے بعد سامنے آئے۔ یہ حد درون یابی (interpolation) پر مبنی طریقوں کے لیے، دو قدر پیمائیوں والے ناطق (rational) طریقوں کے لیے، اور مختلف اضافی شرائط کے تحت ثابت ہوئی؛ صرف فنکشن کی قدریں استعمال کرنے والے طریقوں کے لیے ایک کمزور تر حد، 2ⁿ، ثابت ہوئی۔ عمومی صورت کھلی رہی۔

الگورتھم کو دھوکا دینا

کیمبرج یونیورسٹی کے شعبۂ اطلاقی ریاضی و نظریاتی طبیعیات (Department of Applied Mathematics and Theoretical Physics) کے Matthew Colbrook نے اب اسے مکمل طور پر ثابت کر دیا ہے۔ یہ ماڈل جان بوجھ کر الگورتھم کے ساتھ فراخ دلی برتتا ہے۔ الگورتھم چلتے چلتے یہ چن سکتا ہے کہ کہاں قدر پیمائی کرے، اور کون سے مشتق لے۔ وہ جوابات کو کسی بھی متعین (deterministic) طریقے سے، جیسے چاہے، استعمال کر سکتا ہے، اور اس کے اصولوں سے کسی ہمواری کا تقاضا نہیں کیا جاتا۔

ثبوت الگورتھم کے اپنے متعین پن کو اسی کے خلاف استعمال کرتا ہے۔ دو ایسے فنکشن بنائیں جو اس کے تمام سوالوں کے بالکل ایک جیسے جواب دیں مگر جن کے صفر مختلف ہوں۔ الگورتھم کو دونوں کے لیے ایک ہی اندازہ لوٹانا پڑے گا، اس لیے ان میں سے ایک پر وہ کم از کم دونوں صفروں کے درمیانی فاصلے کے نصف سے چوک جائے گا۔

ایسے جوڑے ڈھونڈنے کے لیے، ثبوت میں ایک حوالہ جاتی فنکشن کو زیادہ سے زیادہ درجہ n کی ایک چھوٹی کثیر رقمی (polynomial) سے ذرا سا سرکایا جاتا ہے، جس کے n + 1 قابلِ تبدیل عددی سر (coefficients) ہوتے ہیں۔ ہر قدر پیمائی ان کے زیادہ سے زیادہ ایک مجموعے کو متعین کرتی ہے، اس لیے n سوالات کے بعد بھی کچھ تبدیلیاں الگورتھم کے لیے نظر نہیں آتیں۔ صرف یہ گنتی کافی نہیں: ایک نظر نہ آنے والی تبدیلی شاید صفر کو مشکل سے ہی ہلائے۔

کلیدی اوزار رونسکیئن (Wronskian) ہے — کثیر رقمیوں کے ایک خاندان اور ان کے مشتقات سے بنایا گیا ایک مقطع (determinant)۔ ایک نیا لیما (lemma) کہتا ہے کہ اگر خاندان کی کسی کثیر رقمی کے بہت سے صفر ایک چھوٹی قرص میں ٹھنسے ہوں، تو خاندان کا رونسکیئن قریب ہی کہیں صفر ہونا چاہیے۔ الگورتھم کو ہمیشہ ایسے فنکشن کے ساتھ جواب دے کر جس کا صفر ان چند نقاط سے دور رہے، ثبوت صفر کو حرکت کے لیے آزاد رکھتا ہے۔

حساب کتاب سے قوت نما (exponent) نکلتا ہے۔ صفر سے ε کے فاصلے سے شروع کرنے پر، ممکنہ صفر کم از کم ε کی کسی طاقت ضرب ایک مستقل کے برابر وسعت پر پھیلے رہتے ہیں۔ مصنف کے الفاظ میں، “پہلے مشاہدے کے بعد قوت نما ایک رہتا ہے اور پھر دگنا ہوتا جاتا ہے، جس سے n مشاہدات کے بعد 2ⁿ⁻¹ حاصل ہوتا ہے۔”

ہر پیمانے کے لیے ایک فنکشن

ایک مشکل باقی رہ گئی تھی۔ درجے کی تعریف آگے والے مستقل کو فنکشن پر منحصر ہونے کی اجازت دیتی ہے، اس لیے ہر پیمانے پر ایک مختلف برا فنکشن کچھ ثابت نہیں کرتا۔ چنانچہ Colbrook نے ایک واحد فنکشن بنایا، جس میں ایک کے بعد ایک تصحیحات شامل کی گئیں، اور ہر تصحیح ان تمام نقاط پر صفر ہوتی ہے جن کے بارے میں الگورتھم پہلے ہی سوال کر چکا ہے، تاکہ پچھلے تمام جواب بالکل ویسے ہی رہیں۔

اس کی حد ایک کامل فنکشن (entire function) ہے — ہر جگہ ہموار، مختلط اعداد (complex numbers) پر بھی — جس کی ڈھلان حقیقی خط پر 3/4 اور 5/4 کے درمیان رہتی ہے: ایک مسلسل اٹھتا ہوا منحنی خط جس کا ایک ہی، اچھے رویے والا صفر ہے۔ 2ⁿ⁻¹ سے بڑے کسی بھی p کے لیے، طریقہ اس پر درجہ p تک نہیں پہنچ پاتا۔ لہٰذا بغیر حافظے کے بہترین درجہ n ≥ 2 کے لیے ٹھیک 2ⁿ⁻¹ ہے۔ مقالہ یہی حد اس صورت کے لیے بھی ثابت کرتا ہے جب قدر پیمائیاں مختلط اعداد ہوں۔

سب کچھ ایک ساتھ پوچھنے کی قیمت

ایک زیادہ باریک بیان ان قدر پیمائیوں کا احاطہ کرتا ہے جو گروہوں میں کی جائیں، جہاں کسی گروہ کا ہر سوال اس کے کسی بھی جواب کے آنے سے پہلے چنا جاتا ہے — متوازی طریقوں کی صورتِ حال۔ ℓ₁, …, ℓₖ سائز کے گروہوں کے ساتھ درجہ زیادہ سے زیادہ ℓ₁ × (ℓ₂ + 1) × … × (ℓₖ + 1) ہوتا ہے۔ تمام n سوالات ایک ساتھ پوچھنے سے درجہ n پر رک جاتا ہے؛ انہیں ایک ایک کر کے پوچھنے سے 2ⁿ⁻¹ ممکن ہوتا ہے۔ پانچ قدر پیمائیوں کے ساتھ، یہ 5 بمقابلہ 16 ہے۔

مشین سے جانچا ہوا

نتائج کی باضابطہ تصدیق Lean میں کی گئی ہے، جو ایک ثبوت معاون ہے اور ہر منطقی قدم کو جانچتا ہے۔ کوڈ عوامی ہے اور Palomar رجسٹری میں درج ہے۔ مصنف کے بیان کے مطابق Lean میں باضابطہ تشکیل ChatGPT 6 کی مدد سے کی گئی، پھر Lean 4 Comparator کے ذریعے مقالے کے مسئلوں (theorems) سے اس کا موازنہ کیا گیا، اور ہر دلیل کا جائزہ مصنف نے لیا، اور مواد کی پوری ذمہ داری مصنف پر ہے۔

یہ حد ان طریقوں سے متعلق ہے جو بھول جاتے ہیں۔ جن طریقوں کو اپنے پچھلے قدم دوبارہ استعمال کرنے کی اجازت ہو، وہ دوسری حدوں کے پابند ہیں، جنہیں یہ مقالہ ایک طرف رکھ دیتا ہے۔