আগ্রাওয়ালের অনুমান

সংখ্যা তত্ত্বে, ২০০২ সালে মনীন্দ্র আগ্রাওয়ালের অনুমান সাইক্লোটমিক AKS পরীক্ষার ভিত্তি রূপে কাজ করে। আগ্রাওয়ালের অনুমান অনুযায়ী:

$n$ এবং $r$ দুটি সহমৌলিক ধনাত্মক পূর্ণসংখ্যা এবং

$(X-1{)}^n\equiv X^n-1(\mathrm{mod}n,X^r-1)$

হলে $n$ একটি মৌলিক সংখ্যা হবে অথবা $n^2\equiv 1(\mathrm{mod}r)$ হবে।

প্রভাব

যদি আগ্রাওয়াল অনুমান সঠিক হত, তবে এটি AKS মৌলিকতা পরীক্ষার রানটাইম জটিলতাকে $\tilde{O}\left({\log }^{6}n\right)$ থেকে $\tilde{O}\left({\log }^{3}n\right)$-এ হ্রাস করত।

সত্যতা বা মিথ্যা

এই অনুমানটি ২০০১ সালের থিসিসে রজত ভট্টাচার্য ও প্রশান্ত পাণ্ডে দ্বারা প্রণীত হয়েছিল। এটি $r<100$ এবং $n<10^{10}$ এর জন্য গণনাযোগ্যভাবে যাচাই করা হয়েছে, এবং $r=5,n<10^{11}$ এর ক্ষেত্রেও পরীক্ষা করা হয়েছে।

তবে, কার্ল পমেরান্স এবং হেনড্রিক ডব্লিউ. লেন্সট্রা-এর এক হিউরিস্টিক যুক্তি ইঙ্গিত দেয় যে অসংখ্য বিপরীত উদাহরণ বিদ্যমান। বিশেষ করে, এই যুক্তি দেখায় যে, এমন বিপরীত উদাহরণগুলির অসীম ঘনত্ব যেকোনো $\epsilon >0$ এর জন্য $\frac{1}{n^{\epsilon }}$ থেকে বেশি।

উপরের যুক্তি অনুযায়ী, যদি আগ্রাওয়াল অনুমানটি মিথ্যা প্রমাণিত হয়, তবে রোমান বি. পপোভিচ অনুমান করেন যে সংশোধিত একটি সংস্করণ তবুও সঠিক হতে পারে:

ধরা যাক, $n$ এবং $r$ এমন দুটি ধনাত্মক সংখ্যা, যাদের সর্বোচ্চ সাধারণ গুণনীয়ক ১। যদি

$(X-1{)}^n\equiv X^n-1(\mathrm{mod}n,,X^r-1)$

এবং

$(X+2{)}^n\equiv X^n+2(\mathrm{mod}n,,X^r-1)$

তাহলে $n$ একটি মৌলিক সংখ্যা, অথবা $n^2\equiv 1(\mathrm{mod}r)$ হবে।

ডিস্ট্রিবিউটেড কম্পিউটিং

উভয় আগ্রাওয়াল ও পপোভিচ অনুমান ডিস্ট্রিবিউটেড কম্পিউটিং পদ্ধতি Primaboinca Project দ্বারা পরীক্ষা করা হয়েছে, যা ২০১০ থেকে ২০২০ পর্যন্ত BOINC-ভিত্তিক ছিল। এই প্রোজেক্ট $10^{10}<n<10^{17}$ পরিসরে অনুসন্ধান করেও কোনো কাউন্টার এক্সাম্পল খুঁজে পাওয়া যায়নি।

বহিঃসংযোগ

Primaboinca Project