نظرية ديريشليه للتقريب

في نظرية الأعداد ، تنص نظرية ديريشليه حول التقريب الديوفانتي ، والتي تسمى أيضًا نظرية تقريب ديريشليه ، على أنه لأي أعداد حقيقية $\alpha$ و $N$ ، مع $1\leq N$ توجد أعداد صحيحة $p$ و $q$ بحيث $1\leq q\leq N$ و

\left|q\alpha -p\right|\leq {\frac {1}{\lfloor N\rfloor +1}}<{\frac {1}{N}}.

هنا $\lfloor N\rfloor$ يمثل الجزء الصحيح من $N$ هذه نتيجة أساسية في التقريب الديوفانتي ، تُظهر أن أي عدد حقيقي له سلسلة من التقريبات النسبية الجيدة: في الواقع، إحدى النتائج المباشرة هي أنه بالنسبة لعدد غير نسبي مُعطى α، فإن المتباينة

\left|\alpha -{\frac {p}{q}}\right|<{\frac {1}{q^{2}}}

يتحقق هذا الشرط بعدد لا نهائي من الأعداد الصحيحة p و q . وهذا يدل على أن أي عدد غير نسبي له أس لا نسبي لا يقل عن 2.

تنص نظرية ثو -سيجل-روث على أنه بالنسبة للأعداد الجبرية غير النسبية، فإن الأس 2 في نتيجة نظرية ديريشليه للتقريب هو أفضل ما يمكننا فعله: لا يمكن تقريب هذه الأعداد بأي أس أكبر من 2. تستخدم نظرية ثو-سيجل-روث تقنيات متقدمة في نظرية الأعداد، ولكن العديد من الأعداد الأبسط مثل النسبة الذهبية يمكن تقريبها أيضًا. $(1+{\sqrt {5}})/2$ يمكن التحقق بسهولة أكبر من عدم إمكانية تقريبها بعد الأس 2.

النسخة المتزامنة

تنص الصيغة المتزامنة لنظرية تقريب ديريشليه على أنه بالنظر إلى الأعداد الحقيقية $\alpha _{1},\ldots ,\alpha _{d}$ وعدد طبيعي $N$ ثم هناك الأعداد الصحيحة $p_{1},\ldots ,p_{d},q\in \mathbb {Z} ,1\leq q\leq N$ بحيث $\left|\alpha _{i}-{\frac {p_{i}}{q}}\right|\leq {\frac {1}{qN^{1/d}}}.$ ^{[ 1 ]}

طريقة الإثبات

البرهان بمبدأ خانة الحمام

تُعدّ هذه النظرية نتيجةً لمبدأ التوزيع . وقد استخدم بيتر غوستاف ليجون ديريشليه ، الذي أثبت هذه النتيجة، المبدأ نفسه في سياقات أخرى (على سبيل المثال، معادلة بيل )، وبإطلاقه اسمًا على المبدأ (بالألمانية) ساهم في نشره على نطاق واسع، على الرغم من أن مكانته في الكتب الدراسية لم تظهر إلا لاحقًا. ^{[ 2 ]} ويمكن توسيع نطاق هذه الطريقة لتشمل التقريب المتزامن. ^{[ 3 ]}

مخطط البرهان : ليكن $\alpha$ ليكن عددًا غير نسبي و $N$ ليكن عددًا صحيحًا. لكل $k=0,1,...,N$ يمكننا الكتابة $k\alpha =m_{k}+x_{k}$ بحيث $m_{k}$ هو عدد صحيح و $0\leq x_{k}<1$ يمكن تقسيم الفترة $[0,1)$ داخل $N$ فترات قياس أصغر ${\frac {1}{N}}$ الآن، لدينا $N+1$ أرقام $x_{0},x_{1},...,x_{N}$ و $N$ فترات. لذلك، وفقًا لمبدأ خانة الحمام، يوجد اثنان منها على الأقل في نفس الفترة. يمكننا أن نسميها فترات. $x_{i},x_{j}$ بحيث $i<j$ . الآن:

|(ji)\alpha -(m_{j}-m_{i})|=|j\alpha -m_{j}-(i\alpha -m_{i})|=|x_{j}-x_{i}|<{\frac {1}{N}}

بتقسيم كلا الجانبين على $ji$ سيؤدي ذلك إلى:

\left|\alpha -{\frac {m_{j}-m_{i}}{ji}}\right|<{\frac {1}{(ji)N}}\leq {\frac {1}{\left(ji\right)^{2}}}

وقد أثبتنا النظرية.

البرهان باستخدام نظرية مينكوفسكي

ثمة برهان بسيط آخر لنظرية تقريب ديريشليه يعتمد على نظرية مينكوفسكي المطبقة على المجموعة

S=\left\{(x,y)\in \mathbb {R} ^{2}:-N-{\frac {1}{2}}\leq x\leq N+{\frac {1}{2}},\vert \alpha x-y\vert \leq {\frac {1}{N}}\right\}.

نظراً لحجم $S$ أكبر من $4$ تُثبت نظرية مينكوفسكي وجود نقطة غير تافهة ذات إحداثيات صحيحة. ويمتد هذا البرهان بشكل طبيعي إلى التقريبات المتزامنة من خلال النظر في المجموعة

S=\left\{(x,y_{1},\dots ,y_{d})\in \mathbb {R} ^{1+d}:-N-{\frac {1}{2}}\leq x\leq N+{\frac {1}{2}},|\alpha _{i}x-y_{i}|\leq {\frac {1}{N^{1/d}}}\right\}.

النظريات ذات الصلة

نظرية ليجاندر حول الكسور المستمرة

في كتابه "مقال في نظرية الأعداد " (1798)، استنتج أدريان ماري ليجندر شرطًا ضروريًا وكافيًا لكي يكون العدد النسبي متقاربًا مع الكسر المستمر البسيط لعدد حقيقي مُعطى. ^{[ 4 ]} ومن نتائج هذا المعيار، والذي يُعرف غالبًا باسم نظرية ليجندر في دراسة الكسور المستمرة، ما يلي: ^{[ 5 ]}

نظرية . إذا كان α عددًا حقيقيًا و p و q عددين صحيحين موجبين بحيث $\left|\alpha -{\frac {p}{q}}\right|<{\frac {1}{2q^{2}}}$ ، إذن فإن p / q هو متقارب للكسر المستمر لـ α .

دليل

البرهان . نتبع البرهان الوارد في كتاب "مقدمة في نظرية الأعداد" لـ جي إتش هاردي وإي إم رايت . ^{[ 6 ]}

لنفترض أن α و p و q هي بحيث $\left|\alpha -{\frac {p}{q}}\right|<{\frac {1}{2q^{2}}}$ وبافتراض أن α > p / q ، يمكننا كتابة $\alpha -{\frac {p}{q}}={\frac {\theta }{q^{2}}}$ حيث 0 < θ < 1/2. نكتب p / q على شكل كسر مستمر محدود [ a ₀ ; a ₁ , ..., _an ] ، ونظرًا لأن لكل عدد نسبي تمثيلين مختلفين ككسور مستمرة محدودة يختلفان في الطول بمقدار واحد (أي أحدهما حيث an = 1 والآخر حيث an _≠ 1)، يمكننا اختيار n ليكون زوجيًا. (في حالة α < p / q ، نختار n ليكون فرديًا) _.

ليكن p₀ _/q₀ ، ...، _pₙ/ _qₙ = p / qₙ _{متقاربات} هذا التوسع الكسري المستمر . ${\displaystyle \omega$ ، بحيث $\theta ={\frac {q_{n}}{q_{n-1}+\omega q_{n}}}$ وبالتالي، $\alpha ={\frac {p}{q}}+{\frac {\theta }{q^{2}}}={\frac {p_{n}}{q_{n}}}+{\frac {1}{q_{n}(q_{n-1}+\omega q_{n})}}={\frac {(p_{n}q_{n-1}+1)+\omega p_{n}q_{n}}{q_{n}(q_{n-1}+\omega q_{n})}}={\frac {p_{n-1}q_{n}+\omega p_{n}q_{n}}{q_{n}(q_{n-1}+\omega q_{n})}}={\frac {p_{n-1}+\omega p_{n}}{q_{n-1}+\omega q_{n}}},$ حيث استخدمنا حقيقة أن p _n₋₁q _n - p _n q _n₋₁ = (-1) ⁿ وأن n عدد زوجي.

الآن، تشير هذه المعادلة إلى أن α = [ a ₀ ; a ₁ , ..., an _, ω ]. وبما أن 0 < θ < 1/2 يعني أن ω > 1، نستنتج أن متسلسلة الكسور المستمرة لـ α يجب أن تكون [ a ₀ ; a ₁ , ..., an _, b ₀ , b ₁ , ...]، حيث [ b ₀ ; b ₁ , ...] هي متسلسلة الكسور المستمرة لـ ω ، وبالتالي فإن p _n / q _n = p / q هي دالة متقاربة لمتسلسلة الكسور المستمرة لـ α .

تشكل هذه النظرية أساس هجوم وينر ، وهو استغلال لبروتوكول التشفير RSA في وقت متعدد الحدود، ويمكن أن يحدث نتيجة لاختيار غير موفق للمفاتيح العامة والخاصة (على وجه التحديد، ينجح هذا الهجوم إذا كانت العوامل الأولية للمفتاح العام n = pq تحقق الشرط p < q < 2p وكان المفتاح الخاص d أقل من (1/3) n ^1/4 ). ^{[ 7 ]}

انظر أيضاً

ملحوظات

↑ شميدت، ص 27، النظرية 1ب
↑ http://jeff560.tripod.com/p.html للاطلاع على عدد من المراجع التاريخية.
↑ "نظرية ديريشليه" ، موسوعة الرياضيات ، دار نشر EMS ، 2001 [1994]
^ ليجيندر ، أدريان ماري (1798). Essai sur la théorie des nombres (بالفرنسية). باريس: دوبرات. ص 27 – 29.
^ باربولوسي، دومينيك. جاجر، هندريك (1994). "على نظرية ليجيندر في نظرية الكسور المستمرة" . جورنال دي Théorie des Nombres de Bordeaux . 6 (1): 81-94 . دوى : 10.5802/jtnb.106 . جستور 26273940 .
↑ هاردي، جي إتش ؛ رايت، إي إم (1938). مقدمة في نظرية الأعداد . لندن: مطبعة جامعة أكسفورد . الصفحات 140-141 ، 153.
↑ وينر، مايكل ج. (1990). "تحليل تشفير الأسس السرية القصيرة لـ RSA". معاملات IEEE في نظرية المعلومات . 36 (3): 553-558 . doi : 10.1109/18.54902 .

مراجع

شميدت، وولفغانغ م. (1980). التقريب الديوفانتي . سلسلة محاضرات في الرياضيات. المجلد 785. سبرينغر. doi : 10.1007/978-3-540-38645-2 . ISBN 978-3-540-38645-2.
شميدت، وولفغانغ م. (1991). التقريبات الديوفانتية والمعادلات الديوفانتية . سلسلة محاضرات في الرياضيات. المجلد 1467. سبرينغر. doi : 10.1007/BFb0098246 . ISBN 978-3-540-47374-9. S2CID 118143570 .

روابط خارجية

نظرية ديريشليه التقريبية في موقع PlanetMath .

[1] شميدت، ص 27، النظرية 1ب

[2] ttp://jeff560.tripod.com/p.html للاطلاع على عدد من المراجع التاريخية.

[3] "نظرية ديريشليه" ، موسوعة الرياضيات ، دار نشر EMS ، 2001 [1994]

[4] ليجيندر ، أدريان ماري (1798). Essai sur la théorie des nombres (بالفرنسية). باريس: دوبرات. ص 27 – 29.

[5] باربولوسي، دومينيك. جاجر، هندريك (1994). "على نظرية ليجيندر في نظرية الكسور المستمرة" . جورنال دي Théorie des Nombres de Bordeaux . 6 (1): 81-94 . دوى : 10.5802/jtnb.106 . جستور 26273940 .

[6] هاردي، جي إتش ؛ رايت، إي إم (1938). مقدمة في نظرية الأعداد . لندن: مطبعة جامعة أكسفورد . الصفحات 140-141 ، 153.

[7] وينر، مايكل ج. (1990). "تحليل تشفير الأسس السرية القصيرة لـ RSA". معاملات IEEE في نظرية المعلومات . 36 (3): 553-558 . doi : 10.1109/18.54902 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]