نظرية سيف

📅 آخر تحديث: ٣١ يوليو ٢٠٢٦
✍️ نُشر في: ٣١ يوليو ٢٠٢٦
📷 يحتوي على 72 صور
الموسوعة الحرة

نظرية الغربلة هي مجموعة من التقنيات العامة في نظرية الأعداد ، مصممة لحساب، أو بشكل أدق، لتقدير حجم، مجموعات الأعداد الصحيحة بعد غربلتها . المثال النموذجي لمجموعة مُغربلة هو مجموعة الأعداد الأولية حتى حد معين X. وبالمثل، المثال النموذجي للغربال هو غربال إراتوستينس ، أو غربال ليجندر الأكثر عمومية . سرعان ما يواجه الهجوم المباشر على الأعداد الأولية باستخدام هذه الطرق عقبات تبدو مستعصية، تتمثل في تراكم حدود الخطأ. في أحد الاتجاهات الرئيسية لنظرية الأعداد في القرن العشرين، تم التوصل إلى طرق لتجنب بعض صعوبات الهجوم المباشر بفكرة ساذجة عما ينبغي أن تكون عليه الغربلة.

تتمثل إحدى الطرق الناجحة في تقريب مجموعة محددة من الأعداد المُصفّاة (مثل مجموعة الأعداد الأولية) بمجموعة أخرى أبسط (مثل مجموعة الأعداد شبه الأولية )، والتي عادةً ما تكون أكبر قليلاً من المجموعة الأصلية، وأسهل في التحليل. كما أن المناخل الأكثر تطوراً لا تتعامل مباشرةً مع المجموعات بحد ذاتها ، بل تحسبها وفقاً لدوال ترجيح مختارة بعناية على هذه المجموعات (خيارات لإعطاء بعض عناصر هذه المجموعات "وزناً" أكبر من غيرها). علاوة على ذلك، في بعض التطبيقات الحديثة، لا تُستخدم المناخل لتقدير حجم المجموعة المُصفّاة، بل لإنتاج دالة كبيرة على المجموعة وصغيرة في الغالب خارجها، مع كونها أسهل في التحليل من الدالة المميزة للمجموعة.

استُخدم مصطلح "المنخل" لأول مرة من قِبل عالم الرياضيات النرويجي فيجو برون عام 1915. [ 1 ] استلهم برون عمله من أعمال عالم الرياضيات الفرنسي جان ميرلان . إلا أن ميرلان توفي في الحرب العالمية الأولى ، ولم يبقَ منه سوى مخطوطتين. [ 2 ]

نظرية المنخل الأساسية

للحصول على معلومات حول التدوين، انظر في النهاية. نتبع الصيغة الواردة في كتاب "أوبرا دي كريبرو" لجون فريدلاندر وهنريك إيوانيك . [ 3 ]

نبدأ بتسلسل قابل للعد من الأعداد غير السالبةأ=(أن){\displaystyle {\mathcal {A}}=(a_{n})}في أبسط الحالات، يكون هذا التسلسل مجرد دالة مؤشر .أن=1أ(ن){\displaystyle a_{n}=1_{A}(n)}من مجموعة ماأ={s:s≤x}{\displaystyle A=\{s:s\leq x\}}نريد غربلة. ومع ذلك، يسمح هذا التجريد بحالات أكثر عمومية. بعد ذلك، نقدم مجموعة عامة من الأعداد الأولية تسمى نطاق الغربلة.P⊆P{\displaystyle {\mathcal {P}}\subseteq \mathbb {P} }ومنتجاتهم حتىz{\displaystyle z}كوظيفةP(z)=∏ص∈P،ص<zص{\displaystyle P(z)=\prod \limits _{p\in {\mathcal {P}},p<z}p}.

يهدف علم الغربلة إلى تقدير دالة الغربلة

S(أ،P،z)=∑ن≤z،القاسم المشترك الأكبر(ن،P(z))=1أن.{\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=\sum \limits _{n\leq z,{\text{gcd}}(n,P(z))=1}a_{n}.}

في حالةأن=1أ(ن){\displaystyle a_{n}=1_{A}(n)}هذا ببساطة يحسب عدد عناصر مجموعة جزئيةأغربلة⊆أ{\displaystyle A_{\operatorname {sift} }\subseteq A}من الأعداد التي تكون أولية فيما بينها مع العوامل الأولية لـP(z){\displaystyle P(z)}.

مبدأ الإدراج والاستبعاد

لP{\displaystyle {\mathcal {P}}}يُعرِّف

أغربلة:={أ∈أ|(أ،ص1⋯صك)=1}،ص1،...،صك∈P{\displaystyle A_{\operatorname {sift} }:=\{a\in A|(a,p_{1}\cdots p_{k})=1\},\quad p_{1},\dots ,p_{k}\in {\mathcal {P}}}

ولكل عدد أوليص∈P{\displaystyle p\in {\mathcal {P}}}يرمز إلى المجموعة الجزئيةهـص⊆أ{\displaystyle E_{p}\subseteq A}مضاعفاتهـص:={صن:ن∈شمال}{\displaystyle E_{p}:=\{pn:n\in \mathbb {N} \}}ودع|هـص|{\displaystyle |E_{p}|}كن العدد الأصلي.

نقدم الآن طريقة لحساب عدد عناصرأغربلة{\displaystyle A_{\operatorname {sift} }}لهذا الغرض نطاق الغربلةP{\displaystyle {\mathcal {P}}}سيكون مثالاً ملموساً للأعداد الأولية من الشكلP:={2،3،5،7،11،13...}{\displaystyle {\mathcal {P}}:=\{2,3,5,7,11,13\dots \}}.

إذا أراد المرء حساب عدد عناصرأغربلة{\displaystyle A_{\operatorname {sift} }}يمكن تطبيق مبدأ الإدراج والاستبعاد . تعمل هذه الخوارزمية على النحو التالي: أولاً، يتم إزالة عنصر من عدد عناصر المجموعة.|أ|{\displaystyle |A|}العددية|هـ2|{\displaystyle |E_{2}|}و|هـ3|{\displaystyle |E_{3}|}الآن بعد أن أزلنا الأعداد التي تقبل القسمة على2{\displaystyle 2}و3{\displaystyle 3}مرتين، يجب إضافة العدد الأصلي|هـ6|{\displaystyle |E_{6}|}في الخطوة التالية، يتم إزالة|هـ5|{\displaystyle |E_{5}|}ويضيف|هـ10|{\displaystyle |E_{10}|}و|هـ15|{\displaystyle |E_{15}|}مرة أخرى. بالإضافة إلى ذلك، يجب الآن إزالة|هـ30|{\displaystyle |E_{30}|}أي عدد جميع الأعداد التي تقبل القسمة على2،3{\displaystyle 2,3}و5{\displaystyle 5}وهذا يؤدي إلى مبدأ الإدراج والاستبعاد

|أغربلة|=|أ|-|هـ2|-|هـ3|+|هـ6|-|هـ5|+|هـ10|+|هـ15|-|هـ30|+⋯{\displaystyle |A_{\operatorname {sift} }|=|A|-|E_{2}|-|E_{3}|+|E_{6}|-|E_{5}|+|E_{10}|+|E_{15}|-|E_{30}|+\cdots }

لاحظ أنه يمكن كتابة هذا على النحو التالي:

|أغربلة|=∑د|Pμ(د)|هـد|{\displaystyle |A_{\operatorname {sift} }|=\sum \limits _{d|P}\mu (d)|E_{d}|}

أينμ{\displaystyle \mu }هي دالة موبيوس وP:=∏ص∈Pص{\displaystyle P:=\prod \limits _{p\in {\mathcal {P}}}p}حاصل ضرب جميع الأعداد الأولية فيP{\displaystyle {\mathcal {P}}}وهـ1:=أ{\displaystyle E_{1}:=A}.

هوية ليجندر

يمكننا إعادة كتابة دالة الفرز باستخدام متطابقة ليجندر

S(أ،P،z)=∑د|P(z)μ(د)أد(x){\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=\sum \limits _{d\mid P(z)}\mu (d)A_{d}(x)}

باستخدام دالة موبيوس وبعض الدوالأد(x){\displaystyle A_{d}(x)}ناتج عن عناصرP{\displaystyle {\mathcal {P}}}

أد(x)=∑ن≤x،ن≡0(مودد)أن.{\displaystyle A_{d}(x)=\sum \limits _{n\leq x,n\equiv 0{\pmod {d}}}a_{n}.}

مثال

يتركz=7{\displaystyle z=7}وP=P{\displaystyle {\mathcal {P}}=\mathbb {P} }تكون دالة موبيوس سالبة لكل عدد أولي، لذلك نحصل على

S(أ،P،7)=أ1(x)-أ2(x)-أ3(x)-أ5(x)+أ6(x)+أ10(x)+أ15(x)-أ30(x).{\displaystyle {\begin{aligned}S({\mathcal {A}},\mathbb {P} ,7)&=A_{1}(x)-A_{2}(x)-A_{3}(x)-A_{5}(x)+A_{6}(x)+A_{10}(x)+A_{15}(x)-A_{30}(x).\end{aligned}}}

تقريب مجموع التطابق

يفترض المرء إذن أنأد(x){\displaystyle A_{d}(x)}يمكن كتابتها على النحو التالي

أد(x)=ز(د)X+رد(x){\displaystyle A_{d}(x)=g(d)X+r_{d}(x)}

أينز(د){\displaystyle g(d)}هي دالة كثافة ، أي دالة ضربية بحيث

ز(1)=1،0≤ز(ص)<1ص∈P{\displaystyle g(1)=1,\qquad 0\leq g(p)<1\qquad p\in \mathbb {P} }

وX{\displaystyle X}هو تقريب لـأ1(x){\displaystyle A_{1}(x)}ورد(x){\displaystyle r_{d}(x)}هو حد الباقي. تصبح دالة الغربلة

S(أ،P،z)=X∑د|P(z)μ(د)ز(د)+∑د|P(z)μ(د)رد(x){\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=X\sum \limits _{d\mid P(z)}\mu (d)g(d)+\sum \limits _{d\mid P(z)}\mu (d)r_{d}(x)}

أو باختصار

S(أ،P،z)=Xجي(x،z)+R(x،z).{\displaystyle S({\mathcal {A}},{\mathcal {P}},z)=XG(x,z)+R(x,z).}

ثم يحاول المرء تقدير دالة التصفية من خلال إيجاد حدود عليا وسفلى لـS{\displaystyle S}على التوالىجي{\displaystyle G}وR{\displaystyle R}.

يؤدي المجموع الجزئي لدالة الفرز إلى زيادة أو نقصان في العد بالتناوب، لذا سيكون حد الباقي ضخمًا. وكانت فكرة برون لتحسين ذلك هي استبدالμ(د){\displaystyle \mu (d)}في دالة الفرز باستخدام تسلسل الأوزان(λد){\displaystyle (\lambda _{d})}يتألف من دوال موبيوس مقيدة. اختيار سلسلتين مناسبتين(λد-){\displaystyle (\lambda _{d}^{-})}و(λد+){\displaystyle (\lambda _{d}^{+})}ورمزنا لوظائف الفرز بـS-{\displaystyle S^{-}}وS+{\displaystyle S^{+}}يمكن الحصول على حدود دنيا وعليا لوظائف الفرز الأصلية

S-≤S≤S+.{\displaystyle S^{-}\leq S\leq S^{+}.}[ 4 ]

منذز{\displaystyle g}بما أنه ضربي، يمكن للمرء أيضًا العمل مع العنصر المحايد

∑د|نμ(د)ز(د)=∏ص|ن؛ص∈P(1-ز(ص))،∀ن∈شمال.{\displaystyle \sum \limits _{d\mid n}\mu (d)g(d)=\prod \limits _{\begin{array}{c}p|n;\;p\in \mathbb {P} \end{array}}(1-g(p)),\quad \forall \;n\in \mathbb {N} .}

ملاحظة هامة بخصوص الترميز: في الأدبيات، غالباً ما يتم تحديد مجموعة المتتالياتأ{\displaystyle {\mathcal {A}}}مع المجموعةأ{\displaystyle A}نفسه. وهذا يعني أن المرء يكتبأ={s:s≤x}{\displaystyle {\mathcal {A}}=\{s:s\leq x\}}لتحديد تسلسلأ=(أن){\displaystyle {\mathcal {A}}=(a_{n})}كما ورد في الأدبيات المجموعأد(x){\displaystyle A_{d}(x)}يُشار إليه أحيانًا بالعددية|أد(x)|{\displaystyle |A_{d}(x)|}من مجموعة ماأد(x){\displaystyle A_{d}(x)}بينما قمنا بتعريفأد(x){\displaystyle A_{d}(x)}أن تكون بالفعل عدد عناصر هذه المجموعة. لقد استخدمنا P{\displaystyle \mathbb {P} }للدلالة على مجموعة الأعداد الأولية و(أ،ب){\displaystyle (a,b)}لأكبر قاسم مشترك لـأ{\displaystyle a}وب{\displaystyle b}.

أنواع الغربلة

تشمل المناخل الحديثة منخل برون ، ومنخل سيلبرغ ، ومنخل توران ، والمنخل الكبير ، والمنخل الأكبر ، ومنخل غولدستون-بينتز-يلدريم . كان أحد الأهداف الأصلية لنظرية المناخل محاولة إثبات فرضيات في نظرية الأعداد، مثل فرضية الأعداد الأولية التوأم . ورغم أن الأهداف العامة الأصلية لنظرية المناخل لم تتحقق بالكامل بعد، فقد تحققت بعض النجاحات الجزئية، لا سيما عند دمجها مع أدوات أخرى في نظرية الأعداد. ومن أبرز هذه النجاحات:

  1. نظرية برون ، التي توضح أن مجموع مقلوبات الأعداد الأولية التوأم يتقارب (بينما مجموع مقلوبات جميع الأعداد الأولية يتباعد)؛
  2. تنص نظرية تشين على وجود عدد لا نهائي من الأعداد الأولية p بحيث يكون p + 2 إما عددًا أوليًا أو شبه أولي (حاصل ضرب عددين أوليين).وتؤكد نظرية أخرى وثيقة الصلة لتشين جينغران أن كل عدد زوجي كبير بما فيه الكفاية هو مجموع عدد أولي وعدد آخر إما أولي أو شبه أولي. ويمكن اعتبار هاتين النظريتين بمثابة اقتراب من حدسية الأعداد الأولية التوأم وحدسية غولدباخ علىالتوالي.
  3. تنصّ اللمة الأساسية لنظرية الغربال على أنه إذا كان المرء يقوم بغربلة مجموعة من N عددًا، فإنه يستطيع تقدير عدد العناصر المتبقية في الغربال بدقة بعدشمالε{\displaystyle N^{\varepsilon }}وقد وفرت التكرارات ذلكε{\displaystyle \varepsilon }صغير بما فيه الكفاية (الكسور مثل 1/10 شائعة جدًا هنا). عادةً ما تكون هذه اللمة ضعيفة جدًا بحيث لا تسمح باستبعاد الأعداد الأولية (والتي تتطلب عمومًا شيئًا مثلشمال1/2{\displaystyle N^{1/2}}(التكرارات)، ولكن يمكن أن يكون ذلك كافياً للحصول على نتائج تتعلق بالأعداد الأولية تقريبًا.
  4. تنص نظرية فريدلاندر-إيوانيك على وجود عدد لا نهائي من الأعداد الأولية من الشكلأ2+ب4{\displaystyle a^{2}+b^{4}}.
  5. تنص نظرية تشانغ ( تشانغ 2014 ) على وجود عدد لا نهائي من أزواج الأعداد الأولية ضمن مسافة محدودة . وتُعمم نظرية ماينارد-تاو ( ماينارد 2015 ) نظرية تشانغ لتشمل متواليات الأعداد الأولية ذات الأطوال العشوائية.

تقنيات نظرية الغربال

تُعدّ تقنيات نظرية الغربلة فعّالة للغاية، لكنها تبدو محدودة بسبب مشكلة تُعرف بمشكلة التكافؤ ، والتي تنصّ باختصار على أن أساليب نظرية الغربلة تواجه صعوبة بالغة في التمييز بين الأعداد التي تحتوي على عدد فردي من العوامل الأولية والأعداد التي تحتوي على عدد زوجي من العوامل الأولية. ولا تزال هذه المشكلة غير مفهومة تمامًا.

Compared with other methods in number theory, sieve theory is comparatively elementary, in the sense that it does not necessarily require sophisticated concepts from either algebraic number theory or analytic number theory. Nevertheless, the more advanced sieves can still get very intricate and delicate (especially when combined with other deep techniques in number theory), and entire textbooks have been devoted to this single subfield of number theory; a classic reference is (Halberstam & Richert 1974) and a more modern text is (Iwaniec & Friedlander 2010).

The sieve methods discussed in this article are not closely related to the integer factorization sieve methods such as the quadratic sieve and the general number field sieve. Those factorization methods use the idea of the sieve of Eratosthenes to determine efficiently which members of a list of numbers can be completely factored into small primes.

See also

Literature

مراجع

  1. ^ برون ، فيجو (1915). "Über das Goldbachsche Gesetz und die Anzahl der Primzahlpaare". أرشيف للرياضيات. ناتورفيدنسكاب . 34 .
  2. ↑ كوجوكارو، ألينا كارمن؛ مورتي، إم. رام (2005). مقدمة في طرق الغربلة وتطبيقاتها . مطبعة جامعة كامبريدج. doi : 10.1017/CBO9780511615993 . ISBN 978-0-521-84816-9.
  3. ↑ فريدلاندر، جون؛ إيوانيك، هنريك (2010). أعمال كريبرو . منشورات ندوة الجمعية الرياضية الأمريكية. المجلد 57. الجمعية الرياضية الأمريكية. ISBN  978-0-8218-4970-5.
  4. ↑ فريدلاندر، جون؛ إيوانيك، هنريك (2010). أعمال كريبرو . منشورات ندوة الجمعية الرياضية الأمريكية. المجلد 57. الجمعية الرياضية الأمريكية. ISBN  978-0-8218-4970-5.