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

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

ہندسے جو دُگنے ہوندے نیں

اجیہے طریقے دی رفتار اوہدے آرڈر (order) نال ناپی جاندی اے۔ جے ہُن دی غلطی ε اے، تے p آرڈر والی دُہرائی لگ بھگ ε دی طاقت p جِنی غلطی چھڈدی اے۔ آرڈر 2 دا مطلب اے کہ، جواب دے نیڑے، صحیح ہندسیاں دی گنتی ہر قدم اُتے دُگنی ہو جاندی اے؛ آرڈر 4 دا، کہ چوگنی ہو جاندی اے۔

نیوٹن دا طریقہ (Newton’s method) ہر قدم اُتے دو قیمتاں کڈھدا اے — 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» دے طور تے، اک جواب پیش کیتا: یادداشت توں بنا (without memory) اک دُہرائی جو ہر قدم اُتے n قیمتاں کڈھدی اے، اوہدا آرڈر ودھ توں ودھ 2ⁿ⁻¹ ہوندا اے۔ «یادداشت توں بنا» دا مطلب اے کہ طریقہ پچھلے قدماں وچوں اپنی ہُن والی اٹکل توں سوا کجھ نہیں رکھدا۔

حد نوں تھلے نہیں کیتا جا سکدا سی: Kung تے Traub نے آپ «ملٹی پوائنٹ (multipoint)» طریقے بنائے سن جو ہر n ≥ 2 لئی 2ⁿ⁻¹ تیکر اپڑدے سن — تِن قیمتاں نال آرڈر 4، چار نال 8، پنج نال 16۔ جو گھاٹ سی اوہ دوجا اَدھ سی: ایہہ ثبوت کہ کوئی وی طریقہ ایس توں چنگا نہیں کر سکدا۔ اٹکل دے نال تے اوہدے بعد ادھورے نتیجے آئے۔ حد انٹرپولیشن (interpolation) اُتے بنے طریقیاں لئی، دو قیمتاں والے ریشنل (rational) طریقیاں لئی، تے کئی وادھو شرطاں تحت ثابت ہوئی؛ صرف فنکشن دیاں قیمتاں ورتن والے طریقیاں لئی، اک کمزور حد، 2ⁿ، پکی کیتی گئی۔ عام کیس کھلا رہیا۔

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

یونیورسٹی آف کیمبرج (University of Cambridge) دے ڈیپارٹمنٹ آف اپلائیڈ میتھمیٹکس اینڈ تھیوریٹیکل فزکس (Department of Applied Mathematics and Theoretical Physics) دے Matthew Colbrook نے ہُن ایہنوں پورا ثابت کر دتا اے۔ ماڈل جان بُجھ کے الگورتھم لئی کھلے دل والا اے۔ الگورتھم چلدے چلدے چُن سکدا اے کہ قیمت کتھے کڈھنی اے، تے کیہڑے ڈیریویٹو لینے نیں۔ اوہ جواباں نوں کسے وی پکے مقررہ (deterministic) طریقے نال، جیویں چاہے، ورت سکدا اے، تے اوہدے قاعدیاں توں کسے ہمواری (smoothness) دی منگ نہیں۔

ثبوت الگورتھم دی اپنی پکی مقررگی (determinism) نوں اوہدے خلاف ورتدا اے۔ دو اجیہے فنکشن بناؤ جو اوہدے سارے سوالاں دے بالکل اکو جیہے جواب دین پر جیہناں دے صفر وکھرے ہون۔ الگورتھم نوں دوہاں لئی اکو اٹکل دینی پوے گی، ایس لئی اوہناں وچوں اک اُتے اوہ دو صفراں وچکار فاصلے دے گھٹو گھٹ اَدھ جِنا خطا کر جاندا اے۔

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

اصل اوزار ورونسکین (Wronskian) اے — پولی نومیئلاں دے اک ٹبر تے اوہناں دے ڈیریویٹواں توں بنیا اک ڈیٹرمیننٹ (determinant)۔ اک نواں لیما (lemma) آکھدا اے کہ جے ٹبر دے کسے پولی نومیئل دے بہت سارے صفر اک نکی ڈسک (disc) وچ گھُسڑے ہون، تے ٹبر دا ورونسکین نیڑے ای کِتے صفر ہونا لازمی اے۔ اک ورونسکین دے صفر گنتی دے ای ہوندے نیں۔ الگورتھم نوں ہمیشہ اجیہے فنکشن نال جواب دے کے جیہدا صفر اوہناں توں دُور رہندا اے، ثبوت صفر نوں ہلن لئی آزاد رکھدا اے۔

حساب کتاب توں ای ایکسپوننٹ (exponent) نکلدا اے۔ صفر توں ε فاصلے توں شروع کر کے، ممکنہ صفر گھٹو گھٹ ε دی کسے طاقت دے کسے مستقل (constant) گُنا جِنی رینج وچ کھلرے رہندے نیں۔ لکھاری دے لفظاں وچ، «پہلے مشاہدے توں بعد ایکسپوننٹ اک ای رہندا اے تے فیر دُگنا ہوندا اے، تے n مشاہدیاں بعد 2ⁿ⁻¹ دیندا اے۔» کیونکہ الگورتھم ایہناں صفراں نوں وکھ وکھ نہیں پچھان سکدا، اوہدی غلطی ہر واری ε دی طاقت 2ⁿ⁻¹ دے کسے مستقل گُنا توں تھلے نہیں جا سکدی: 2ⁿ⁻¹ توں اُتے کوئی آرڈر نہیں۔

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

اک اوکھ باقی سی۔ آرڈر دی تعریف صرف ایہہ منگدی اے کہ غلطی ε دی طاقت p دے کسے مستقل گُنا توں تھلے رہوے، تے اوہ مستقل فنکشن اُتے منحصر ہو سکدا اے، ایس لئی ہر پیمانے (scale) اُتے وکھرا ماڑا فنکشن کجھ ثابت نہیں کردا۔ ایس لئی Colbrook نے اک اکلا فنکشن بنایا اے، اک توں بعد اک سدھائیاں (corrections) جوڑ کے، ہر سدھائی اوہناں سارے نقطیاں اُتے صفر ہوندی اے جتھے الگورتھم پہلاں ای سوال پچھ چکیا اے، تاں جو سارے پچھلے جواب بالکل اوہی رہن۔

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

سارے سوال اکٹھے پچھن دی قیمت

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

مشین دی جانچ

نتیجیاں دی Lean وچ رسمی جانچ (formal verification) ہوئی اے، جو اک ثبوت جانچن والا پروگرام (proof assistant) اے تے ہر منطقی قدم جانچدا اے۔ کوڈ سب لئی کھلا اے تے رسمی ثبوتاں دی اک عوامی رجسٹری (Palomar) وچ درج اے۔ لکھاری دے بیان مطابق، Lean والی رسمی شکل (formalisation) ChatGPT 6 دی مدد نال تیار کیتی گئی، فیر Lean 4 Comparator نال پیپر دے تھیورماں دے ٹاکرے وچ جانچی گئی، تے ہر دلیل لکھاری نے آپ پرکھی؛ مواد دی پوری ذمہ داری لکھاری دی اپنی اے۔

ایہہ حد اوہناں طریقیاں بارے اے جو بھُل جاندے نیں۔ جیہناں طریقیاں نوں اپنے پچھلے قدم دوبارہ ورتن دی اجازت اے، اوہ ہور حداں دے پابند نیں، جیہناں نوں ایہہ پیپر پاسے رکھدا اے۔ تے حد سب توں ماڑے کیس (worst case) دی اے: کجھ خاص فنکشناں اُتے، کوئی طریقہ فیر وی ودھ تیز چل سکدا اے۔