نقدم ونحلل عائلة من دوال التجزئة والمفاضلة التي من المرجح أن تنتج تصادمات لتكوينات صغيرة قابلة للتخفيض من المتجهات. قد تقدم هذه الدوال تحسينات عملية لغربلة الشبكة للمتجهات القصيرة. بشكل خاص، في نظام تقاربي واحد، تظهر العائلة سلوك تقاربي مختلف بشكل ملحوظ عن دوال التجزئة والمفاضلة الحالية.
نقدم في هذا البحث عائلة من دوال التجزئة والمفاضلة التي تزيد من احتمال حدوث تصادمات لتكوينات المتجهات الصغيرة القابلة للتخفيض. هذه الدوال قد توفر تحسينات عملية لعمليات غربلة الشبكة للمتجهات القصيرة. بشكل خاص، في نظام تقاربي معين، تظهر هذه العائلة من الدوال سلوك تقاربي مختلف بشكل كبير عن دوال التجزئة والمفاضلة المستخدمة حالياً.
تعتمد خوارزميات ما بعد الكم مثل Kyber وDilithium وFALCON وFrodo وNTRU وغيرها على صعوبة إيجاد متجه قصير في شبكة، ولذلك فإن فهم صعوبة هذه المسألة الرياضية في الأبعاد الكبيرة مهم جداً لاختيار المعاملات لهذه الخوارزميات. وفقاً للفهم الحالي، يُعتقد أن الطريقة الأكثر فعالية لإيجاد متجهات قصيرة في شبكة ذات بعد كبير \(d\) هي "الغربلة". تم تقديم غربلة المتجهات القصيرة في شبكة لأول مرة بواسطة أجتاي وكومار وسيفاكومار (AKS). في خوارزميات الغربلة هذه، يتم إنتاج عدد كبير من المتجهات (أسي في \(d\)) بأطوال متقاربة من خلال أخذ مجموعات خطية صغيرة من متجهات الأساس. ثم تتم مقارنة أزواج المتجهات لمعرفة ما إذا كان جمع أو طرح أحدهما من الآخر يؤدي إلى متجه أقصر من أحد المتجهين في الزوج. بعد ذلك يتم استبدال المتجه الأطول بالمتجه الأقصر في المجموعة وتكرار العملية. يُفترض أن العملية تستمر حتى تنتهي عندما لا يمكن العثور على متجهات أقصر لأن المتجه الأقصر قد تم الوصول إليه. تُستخدم الاستدلالات لتبرير عدد المتجهات المطلوبة للثقة في العثور المستمر على متجهات جديدة أقصر.
كانت فكرة (AKS) الأولية تعتبر جميع الأزواج الممكنة من المتجهات، ولكن الأفكار اللاحقة قدمت تحسينات على وقت التشغيل من خلال النظر فقط في أزواج المتجهات التي كانت "قريبة" حيث كانت هذه هي الأكثر احتمالاً لإنتاج متجهات أقصر. لا يزال حساب المسافة بين كل زوج يستغرق وقتاً تربيعياً في عدد المتجهات، ولكن تجزئة كل متجه بوظيفة من المحتمل أن تحتفظ ببعض المعلومات حول الموقع ستسمح بالفرز حسب قيمة التجزئة للعثور على أزواج قريبة. تسمى مثل هذه الوظيفة بتجزئة حساسة للموقع (LSH)؛ انظر (polytope) لمثال على هذا النهج. نهج مماثل (filter) هو عائلة من وظائف التصفية التي تنتج مخرجاً ثنائياً لكل متجه مدخل، حيث من المرجح أن تمر المتجهات القريبة مجموعة من المعايير.
إحدى توسعات نهج الغربلة هي النظر ليس فقط في أزواج المتجهات، ولكن أيضاً في ثلاثيات، أو بشكل عام مجموعات من المتجهات التي يمكن العثور على مجموعة خطية أقصر لها (tuple). إيجاد مثل هذه المجموعة الخطية أكثر تعقيداً من حالة زوج المتجهات حيث تكون العملية في الأساس هي الخطوة الأولى في خوارزمية إقليدس. ومع ذلك، هناك خوارزميات سريعة ومحددة لإيجاد أقصر مجموعة خطية من ثلاثة (semaev) أو أربعة (nguyen) متجهات. في الواقع، نظراً لأن تعقيد الغربلة يعتمد بشكل ضعيف جداً على خطوة الخفض، يمكن فحص مجموعات أكبر لمجموعة خطية أقصر (على سبيل المثال، من خلال تعداد Schnorr-Euchner (schnorr)، أو حتى نهج غربلة ذو بعد أقل). في هذه الحالة، طالما تم العثور على مجموعة خطية أقصر بنسبة إيجابية من الوقت، فإن عملية الغربلة ستظل تعمل. تكون التكوينات القابلة للخفض من مجموعات \(k\) أكثر شيوعاً مع زيادة حجم \(k\)، وبالتالي تتطلب غربلة المجموعات عدداً أقل من المتجهات الأولية، مما يقلل بدوره من تعقيد الذاكرة للغربلة. في هذه الورقة، سننظر في مشكلة إيجاد تكوينات قابلة للخفض من مجموعات \(k\)، مع التركيز بشكل خاص على الحالة \(k=3\).
مرة أخرى، لجعل غربلة المجموعات أكثر كفاءة من الناحية الحسابية، يلزم وجود عملية تصفية يمكنها تحديد المجموعات القابلة للخفض بجهد أقل من النظر في كل مجموعة ممكنة. يتطلب ذلك توصيفاً لعائلة كبيرة من الثلاثيات/المجموعات القابلة للخفض بالإضافة إلى عملية رخيصة ولكنها قوية لتحديد هذه الثلاثيات/المجموعات بين مجموعة كبيرة من المتجهات استناداً إلى هذا التوصيف. تقوم النهج الحالية (klist, fast_tuple) ببناء مجموعة \(k\) من المتجهات تدريجياً من متجه إلى زوج، ثلاثي، ...، \((k-1)\)-مجموعة من المتجهات حيث يتم تحديد كل متجه جديد من تصادمات التجزئة الزوجية أو بقاء التصفية الزوجية.
في هذه الورقة، نحن نستكشف نهجاً أكثر مباشرة حيث يتم تحديد مجموعات \(k\) القابلة للخفض من خلال تصادمات \(k\)-طريق على وظائف التجزئة أو عائلة من \(k\) الناجين من التصفية. نقترح أيضاً تعميماً للتجزئة الحساسة للزاوية المستخدمة في (angular, polytope) والتي يمكن استخدامها كاختبار إحصائي لتحديد التكوينات القابلة للخفض الشائعة. يرتبط التعريف بمشكلة إيجاد مجموعات من المتجهات التي تقع جميعها بالقرب من نفس الفضاء الفرعي ذو \((k-1)\) بعد. في هذه الحالة، قد تكون طرقنا قابلة للتطبيق على التصنيف/التجميع في مجموعات بيانات أخرى ذات أبعاد عالية. يقدم تعميمنا أيضاً تجزئات حساسة للموقع لحالة \(k=2\)، والتي تقدم سلوكاً تقاربياً مختلفاً عن التجزئات الحالية وقد تكون مفيدة عملياً لتطبيقات الغربلة الحالية. تشير تحليلاتنا أيضاً إلى أنه يمكن تكييف التصفية لعائلات من \(k\) الناجين وعائلة جديدة من وظيفة التصفية التي قد تستحق مزيداً من البحث.
تُعرّف دالة التجزئة للشبكة المتقاطعة كما هو موضح في (polytope) بأنها تُنشأ من خلال اختيار \(d\) متجهات موزعة غاوسياً مستقلة ومتطابقة التوزيع \(\vv r_i\). ثم لكل متجه \(\vv v\) يدخل إلى دالة التجزئة نحسب \(\pm\vv r_i\cdot \vv v\). نلاحظ الفهرس الموقع \(\pm i\) للـ \(\pm\vv r_i\) الذي أنتج أكبر جداء قياسي ونأخذ هذا ليكون قيمة التجزئة أي \[H(\vv v)=(-1)^b i: b\in\{0,1\}, (-1)^b\vv r_i\cdot\vv v\ge |\vv r_j\vv v |\ \forall 1\le j\le d\] (تكون تساويات الجداءات القياسية نادرة الحدوث، ولكن إذا كان من الضروري استخدام معيار للتعادل يمكن اختيار أقل \(i\)). بشكل تقريبي، قد نفكر في \(\pm\vv r_i\) كتقريبات لمحاور شبكة متقاطعة عشوائية نظراً لأن البعد يعني أن \(\vv r_i\) تكون تقريباً متعامدة وبنفس الطول. من المحتمل أن تقترب التجزئة من أقرب رأس للشبكة المتقاطعة إلى المتجه وبشكل حدسي نتوقع أن المتجهات القريبة سيكون لها رأس قريب مشترك وبالتالي تنتج تصادماً في التجزئة.
نلاحظ بعض الملاحظات حول تجزئة الشبكة المتقاطعة التي تعطي رؤية حول اختيارنا لتجزئة تعمل كاختبار إحصائي للأنماط \(k\)-القابلة للتقليص.
أولاً، نلاحظ أن تجزئة الشبكة المتقاطعة تختبر الأزواج \(\vv v_1,\vv v_2\) التي تكون قريبة بحيث يكون \(\vv v_1-\vv v_2\) على الأرجح أقصر. سيكون من المناسب تحديد الأزواج التي تكون قريبة من كونها متعاكسة قطرياً بحيث يكون \(\vv v_1+\vv v_2\) على الأرجح أقصر. تشير حدسنا إلى أننا يجب أن نختار الفهرس غير الموقع بأكبر قيمة مطلقة بحيث تكون تجزئتنا متطابقة على \(\pm\vv v\).
ثانياً، نقترح أنه يجب أن يكون من الممكن استخدام عدد أقل من المتجهات العشوائية ومع ذلك يكون لديها اختبار بقوة تمييز. مجموعة من \(h\) متجهات عشوائية ستمتد/تحدد فضاء فرعياً ببعد \(h\) ونتوقع أن يحافظ إسقاط زوجنا من المتجهات في هذا الفضاء تقريباً على القرب/المعاكسة القطرية. بالطبع، ستكون هذه التجزئة أرخص في التقييم، مما قد يعوض عن أي فقدان في القوة. مع وجود قيم خرج ممكنة أقل، ستزيد معدلات التصادم لكل من الاختبارات الإيجابية الصحيحة والخاطئة. هذا يعني أنه لقيم \(h\) أصغر، فإن عائلة التجزئات أكثر قابلية للاختبار التجريبي، حتى في الأبعاد الكبيرة.
ثالثاً، قد نختار اختيار أكثر من فهرس واحد. إذا جمعنا مجموعة من \(a\) فهارس بأكبر قيمة مطلقة، فإننا نحدد بشكل فعال الفضاء الفرعي \(a\)-البعدي الذي يولد بواسطة المتجهات في قاعدتنا العشوائية التي تحتوي على أكبر إسقاط لـ \(\vv v\). مرة أخرى، نتوقع أن الأزواج القابلة للتقليص من المتجهات من المرجح أن تشترك في فضاء فرعي يحتوي على أكبر إسقاط. بدلاً من ذلك، إذا كتبنا \(h=a+b\) فإن اختباراً مكافئاً هو جمع \(b\) فهارس بأقل قيمة مطلقة والتي تحدد الفضاء الفرعي \(b\)-البعدي بأصغر إسقاط. سيكون هذا الفضاء الفرعي الأكثر تعامداً مع \(\vv v\) ومرة أخرى نتوقع أن تكون المتجهات القابلة للتقليص أكثر عرضة لمشاركة هذا الفضاء الفرعي الأكثر تعامداً.
لهذه الأسباب، نحدد عائلة عامة من "تجزئات الإسقاط العشوائي" على النحو التالي:
لتكن \(\mathcal R=\{\vv r_1,\vv r_2,\ldots,\vv r_h\}\subset\mathbb R^d\) مجموعة من المتجهات المولدة بشكل مستقل والتي تكون مكوناتها بالنسبة لبعض القواعد المتعامدة موزعة \(\mathcal N(0,1)\). لـ \((a,b)\) حيث \(a+b=h\)، نعرف عائلة دوال التجزئة الإسقاطية العشوائية \(H_{\mathcal R,a,b}(\vv v)\) وفقاً لمجموعة \(A\) من \(a\) فهارس \(i\) من \(\vv r_i\) التي تنتج أكبر جداء قياسي مطلق مع \(\vv v\) من حيث الحجم المطلق (بدلاً من ذلك يمكننا تسجيل مجموعة \(B\) بحجم \(b\) حيث \(B=\{1,\ldots,h\}\backslash A\)) أي \[H_{\mathcal R,a,b}=\left\{A:\# A= a, |\vv r_i\cdot\vv v|\ge|\vv r_j\cdot\vv v|\ \ \forall i\in A,j\in \{1,\ldots,h\}\backslash A\right\}\] يمكن كسر التعادلات لجداءات النقاط بنفس الحجم المطلق من خلال اختيار أقل فهرس.
نحن مهتمون بمعدل التصادم \(k\)-الطريق للدوال في هذه العائلة على مختلف الأنماط \(k\) من المتجهات المدخلة. إذا كانت قيم التجزئة لأنماطنا \(k\) غير مرتبطة، نتوقع معدل تصادم ساذج يساوي \(\binom ha^{-(k-1)}\). سنرى أن معدل التصادم الفعلي هو دالة للجداءات القياسية الزوجية لأنماطنا \(k\). في القسم [sec:reducible]، سنوضح أن قابلية تقليص أنماط \(k\) مرتبطة أيضاً بهذه الجداءات القياسية الزوجية. في القسم [sec:empirical]، نحقق في معدل التصادم الثلاثي تجريبياً لمختلف التكوينات من الثلاثيات التي يمكن تقليصها أو التي لا يمكن تقليصها تماماً. هذه الحسابات التجريبية ممكنة فقط لقيم نسبياً صغيرة من \(\binom ha^{k-1}\). في القسم [sec:n_analysis]، نقدم تعبيراً تحليلياً لمعدل التصادم في الحالات التي \(a=1\) أو \(b=1\) يمكن تقريبها عددياً عبر تكامل عددي \((k+1)\)-الأبعاد. هذا كافٍ لإثبات الارتباط بين معدلات التصادم والجداءات القياسية الزوجية لقيم صغيرة من \(k\) و\(\min(a,b)=1\). في القسم [sec:asymptotic]، ننظر في السلوك التقاربي لمعدل التصادم لقيم كبيرة من \(b\) مع ثبات \(a\) ونثبت تعميماً للنظرية 1 من (angular)، حيث ينظر في معدل التصادم الثنائي الحالة \(h=d\), \(a=1\), \(b=d-1\). في (angular)، يظهر أن معدل التصادم السلبي اللوغاريتمي التقاربي للنسخة الموقعة من التجزئة يساوي \((\alpha-1)\log h\) حيث \(\alpha(\tau):=4/(4-\tau^2)\) حيث \(\tau\) هو المسافة بين المتجهين. قد نلاحظ أن هذا يمكن أن يُكتب أيضاً \(\alpha(\vv v_1\cdot\vv v_2):=2/(1-|\vv v_1\cdot\vv v_2|)\)، إذا أردنا الربط بالجداءات القياسية الزوجية. في الحالة الأوسع نجد أن معدل التصادم السلبي اللوغاريتمي التقاربي كما \(b\to\infty\) يمكن التعبير عنه كـ \[\log\frac {B((1+o(1))\alpha a,b)}{B(a,b)}\] حيث \(B\) هي دالة بيتا و\(\alpha\) هي دالة فقط من الجداءات القياسية الزوجية للأنماط \(k\). نشير إلى \(\alpha\) باسم "القطر المزدوج الأقصر المربع" لمجموعة من المتجهات ونعطي تعريفاً رياضياً في القسم [sec:asymptotic]. نحلل أيضاً السلوك التقاربي لمعدل التصادم لقيم كبيرة من \(a\) مع ثبات \(b\) ونجد سلوكاً مختلفاً. على وجه التحديد نثبت معدل تصادم تقاربي يساوي \[\Delta^{-b}\binom{a+b}b^{-k+1}\] حيث \(\Delta\) هو جيب القطب لأنماطنا \(k\). نقدم أيضاً مرور معدلات البقاء لأنماط \(k\) تحت الشروط المبنية على تجزئة الإسقاط العشوائي التي تكون فوق حد كبير أو تحت حد صغير من حيث القيمة المطلقة. يمكن استخدام هذه التقديرات لتطوير مخططات تصفية للغربلة.
في هذا القسم، نحاول توصيف عائلات من أزواج المتجهات ذات الطول المتساوي حيث تكون بعض الجمعيات الخطية للمتجهات أقصر من المتجهات الأصلية.
عند النظر فيما يرجح أن يكون فئة أكثر شيوعاً من أزواج المتجهات القابلة للتخفيض، نتخيل أولاً \(k\)-زوجاً نموذجياً من المتجهات الموجودة على كرة ذات بعد \((d-1)\). بالنسبة لـ \(k\) صغيرة مقارنة بـ \(d\)، من المرجح أن يكون \(k\)-زوجنا قريباً من العمودية وبالتالي يمكننا تصور \(2^k\) من مجموع/الفروق لـ \(k\)-زوجنا كرؤوس لمكعب فائق تقريبي بأطوال جوانب مساوية لقطر كرتنا ذات البعد \((d-1)\) وموازية لمتجهاتنا. نود تحويل هذا المكعب الفائق بأقل قدر من الاضطراب، مع الحفاظ على طول الجانب التقريبي، والذي من شأنه أن يضمن جمعية خطية من متجهاتنا أقصر من المتجهات نفسها. الغريزة الطبيعية هي ضغط المكعب الفائق على طول قطر رئيسي لتشكيل متوازي مستطيلات معين. إذا قمنا بالضغط إلى حد أن القطر الرئيسي أقل من طول الجوانب، فإن هذا القطر هو جمعية خطية أقصر. على وجه التحديد، إذا كانت المتجهات الناشئة من رأس واحد من القطر الرئيسي هي \(\vv u_1,\vv u_2,\ldots,\vv u_k\) (وكذلك نفي هذه المتجهات يتقارب على الرأس المقابل) فإن القطر يمثل المتجه \[\vv d=\vv u_1+\vv u_2+\vv+\vv u_k.\] كل متجه \(\vv u_i\) إما متجه من زوجنا أو نفيه. من خلال توسيع \(\vv d\cdot\vv d\) باستخدام قانون التوزيع، يمكننا رؤية تعميم قاعدة الجيب التمام \[||\vv d||^2=\ell^2\left(k+\sum_{i\neq j}\cos(\vv u_i,\vv u_j)\right)\] حيث \(\ell\) هو طول جانب متوازي المستطيلات المعيني و\(\cos(\mathbf u_i,\mathbf u_j)\) هو جيب تمام الزاوية بين المتجهات \(\mathbf u_i\) و\(\mathbf u_j\). لجعل \(||\mathbf d||^2\) أقل من \(\ell^2\) يجب أن نجعل مجموع مصطلحات جيب التمام \(2\binom k2\) أقل من \(-k+1\). الطريقة الأقل تشويهاً للقيام بذلك هي جعل كل مصطلح أقل قليلاً من \(-1/k\). هذا يحدد تكويناً من \(k\)-متجهات التي ستكون حدوداً لفئتنا الكبيرة من أزواج \(k\) القابلة للتخفيض حيث تشكل المتجهات متوازي مستطيلات معين بتناظر دوراني \(k\) مرات حول قطره الأقصر الذي يساوي طول الجانب. الزاوية بين كل زوج من المتجهات المتميزة في هذه الحالة هي \(\arccos(-1/k)\). بما يتفق مع تحليل (tuple, klist, fast_tuple)، تتركز كثافة الأزواج العشوائية القابلة للتخفيض بالقرب من هذا التكوين ونهدف إلى تصميم تجزئة قادرة على اختبار مثل هذه التكوينات.
عند النظر في حالة \(k=3\)، يتم جذب اهتمامنا إلى ثلاثيات المتجهات التي تحدد متوازيات مستطيلات مسطحة، وهو ما يشبه ثلاثيات المتجهات التي تقترب من كونها متوازية الأضلاع. مرة أخرى، هذا يتناسب مع حدسنا: التوازي يعادل التبعية الخطية في فضاء المتجهات والتي قد نعتقد أنها مرتبطة ارتباطاً وثيقاً بجمعية خطية صغيرة في الشبكة المقابلة. بشكل عام، يمكننا أن نرى أننا مهتمون بمتوازيات المستطيلات ذات الأبعاد \(k\) التي لها قطر قصير بحيث تكون المتجهات \(k\) قريبة من الاستلقاء في فضاء فرعي ذو أبعاد \(k-1\). هذا يوحي بأن التصادمات في عائلتنا من تجزئات الإسقاط العشوائية يمكن استخدامها للكشف عن أزواجنا: يجب أن تحتوي المتجهات العشوائية \(a\) ذات الجداءات القياسية الكبيرة مع متجهات زوجنا على مكون كبير في الفضاء الفرعي ذو الأبعاد \((k-1)\) ويجب أن تحتوي المتجهات \(b\) الأخرى على مكون كبير في المتمم العمودي. وبالتالي، فإن اعتقادنا هو أنه من المرجح أن نلاحظ تصادماً بين \(k\) طرق لدالة التجزئة الإسقاطية العشوائية \(H\) أكثر من \(k\)-زوج عام.
إذا اقتصرنا على الجمع الخطي لمتجهاتنا \(k\) حيث أن المعاملات هي \(\pm 1\)، لاحظنا في القسم [sec:reducible] أن قابلية تقليل تكوين \(k\) من المتجهات الوحدوية تعتمد على الجداء النقطي الزوجي بينها: بشكل خاص، هي قابلة للتقليل إذا كان \(\sum_{i\neq j}\vv u_i\vv u_j<-k-1\) لمجموعة معينة \(\vv u_i\) من \(\vv v_i\) الموقعة. من المثالي أن يعتمد معدل التصادم فقط على هذا المجموع، ولكن الأمر ليس كذلك. تؤدي التماثل الدوراني للتجزئة إلى جعلنا نعتقد أن معدل التصادم يجب أن يعتمد على الأكثر على مجموعة الجداءات القياسية الزوجية وسنرى أن هذا هو الحال تحت جميع طرق التحقيق الثلاثة.
لبعد معين \(d\)، يمكننا توليد \(k\)-مجموعة عشوائية من المتجهات بجداءات قياسية زوجية محددة مسبقاً من خلال توليد ثلاثي عشوائي تعسفي، حساب قاعدة جرام-شميدت للفضاء \(k\)-البعدي الذي تمتد به هذه ومن ثم إعادة تحجيم مكونات كل من متجهاتنا العشوائية في قاعدة جرام-شميدت. لمثل هذه الثلاثيات يمكننا تقدير معدل التصادم الثلاثي التجريبي لعائلة تجزئة الإسقاط العشوائي لدينا. بشكل ساذج نتوقع أن تجزئة \(H_{\mathcal R,a,b}\) لديها معدل تصادم يقارب \(p\approx\binom{a+b}b^{-k+1}\) وإذا قمنا بأخذ عينة من \(N\) تجزئات، نتوقع أن يكون عدد التصادمات موزعاً \(\mathcal B(N,p)\). لتقدير معدل التصادم المتوسط إلى ضمن \(\pm 1\%\) بثقة 95% قد نأخذ \(N\approx -\log 0.025\times3\times 10^4\times p^{-2}\approx 10^5p^{-2}\) لكل حد تشيرنوف ذو الجانبين. هذا يستبعد التحقيق المكثف في التصادمات ذات \(p\) الصغير، ولكن لعدد قليل من قيم \(k\) و \(h\)، يمكن تأكيد أن الاحتمالات تبدو أنها تعتمد على الأكثر على الجداءات القياسية الزوجية وتستقر التقديرات كما قد نتوقع. نود أيضاً التجربة في بعد كبير بما يكفي لإظهار المبدأ العام دون أن نثقل كاهل حساباتنا.
نحقق في الحالة \(k=3\) وننظر في الثلاثيات التي يتم تمثيل الجداء القياسي بين أزواجها بـ \(\alpha\)، \(\beta\) و \(\gamma\) ومجموع الأزواج الستة الممكنة هو \(2\alpha+2\beta+2\gamma=\sigma\). لهذا، نعمل مع \(d=20\) ثابتة (كانت التجارب مستقرة نسبياً بالنسبة للأبعاد المتغيرة)، ونستخدم 100,000 تجربة للحصول على حوالي 2-3 أرقام دقيقة. نرسم البيانات لعائلة التجزئة \(H_{\mathcal R,1,2}\) (أي حيث يتم الاحتفاظ بمؤشر أكبر ثلاث جداءات قياسية عشوائية). نقتصر على البيانات حيث \(\alpha,\beta,\gamma<0\) (في مثل هذه الحالات ستكون الناقلات أفضل إذا تم تقليصها زوجياً بدلاً من ثلاثياً).
نرى تماثل \(S_3\) الذي نتوقعه في رسمنا وتتحقق توقعاتنا بمعدل تصادم أعلى مع انخفاض \(\sigma\). احتمال التصادم يزداد كلما انتقلنا من التكوين الأكثر شيوعاً الذي يقع في مركز رسمنا. للإشارة، قيم المركز في الحالات الثلاث هي \(\approx 0.125, 0.134, 0.144\)، كل منها بعيد بشكل مريح عن معدل السذاجة \(1/9\) (بحوالي 12.5%، 20.5% و 28.9% على التوالي). مقارنة جيدة لقوة التمييز لتصادم التجزئة كاختبار هو نسبة السجل للاحتمالات. إذا كتبنا \(\rho(x,y)\) لنسبة السجل لمعدلات التصادم عندما \(\sigma=x\) و \(\sigma=y\) لدينا \[\rho(-2.0,-2.4)\approx 1.034,\quad \rho(-2.0,-3.0)\approx 1.035,\quad \rho(-2.0,-2.4)\approx 1.070.\]
بزيادة عدد الناقلات العشوائية إلى 4، نتوقع أن تنخفض معدلات التصادم بما يتناسب مع الانخفاض الساذج من \(1/9\) إلى \(1/16\).
نرى شكل بيانات مماثل لحالة \(H_{\mathcal R, 1,2}\). الآن القيم المركزية هي تقريباً \(0.0705, 0.0765, 0.0763\) (التي تتفوق على معدل السذاجة بحوالي 12.8%، 22.4% و 22% على التوالي). بالنظر إلى نسب السجل لدينا \[\rho(-2.0,-2.4)\approx 1.032,\quad \rho(-2.0,-3.0)\approx 1.031,\quad \rho(-2.0,-2.4)\approx 0.999.\] قد يشير هذا إلى أن الاحتفاظ بـ \(h\) صغير لا يوفر فقط تجزئة أرخص، ولكن أيضاً أقوى. ومع ذلك، هناك بوضوح عدم دقة عددية كبيرة.
نحن ننظر أيضاً في معدل التصادم عندما نأخذ أصغر جداء قياسي.
شكل بياناتنا لا يتغير، ولكن إذا نظرنا إلى القيم المركزية نرى أنها تقريباً \(0.126, 0.141, 0.183\)، تتجاوز معدل السذاجة بـ 13.4%، 12.7% و 64.5% على التوالي. علاوة على ذلك، بالنظر إلى نسب السجل لدينا \[\rho(-2.0,-2.4)\approx 1.058,\quad \rho(-2.0,-3.0)\approx 1.219,\quad \rho(-2.0,-2.4)\approx 1.152.\] هذا يشير إلى أن تجزئة القيمة الدنيا أقوى بكثير من تجزئة القيمة الكبرى وقد تستفيد من تحقيق أعمق.
بمزيد من التحقيق في تجزئة القيمة الدنيا مع 4 ناقلات عشوائية نحصل على
القيم المركزية تقريباً \(\approx 0.0727, 0.0848, 0.127\)، تتجاوز معدل السذاجة بـ 16.3%، 35.7% و 103% على التوالي. علاوة على ذلك، بالنظر إلى نسب السجل لدينا \[\rho(-2.0,-2.4)\approx 1.063,\quad \rho(-2.0,-3.0)\approx 1.270,\quad \rho(-2.0,-2.4)\approx 1.196\] حيث يبدو أن عائلة التجزئة \(H_{\mathcal R,3,1}\) أقوى من عائلة \(H_{\mathcal R,2,1}\). مرة أخرى، يبدو أن التحقيق الأعمق مبرر.
في هذا القسم، نطور تعبيراً تكاملياً لاحتمالية التصادم الثلاثي في حالة \(b=1\). يمكن تعميم القيم الأعلى لـ \(k\) بسهولة وسيتم ذكرها دون إثبات. بالنظر إلى ثلاثية متجهات مستقلة خطياً \((\vv v_1, \vv v_2, \vv v_3)\)، نقوم بالإسقاط في الفضاء الفرعي ثلاثي الأبعاد الذي تمتد به هذه المتجهات. بسبب تماثل التوزيع الكروي، يمكن اعتبار إسقاطات المتجهات \(\vv r_i\) مستقلة وموزعة بشكل مطابق مع مكونات موزعة \(\mathcal N(0,1)\) بالنسبة لقاعدة متعامدة تعسفية \(\vv i, \vv j, \vv k\) لهذا الفضاء الفرعي. بتجاوز الدقة في التعبير، سنكتب أيضاً \(\vv r_i\) للإشارة إلى إسقاط \(\vv r_i\) في هذا الفضاء الفرعي في النقاش أدناه، مع الإشارة إلى أن الجداءات القياسية بين \(\vv v\)s و \(\vv r\)s محفوظة.
بالاعتماد على التماثل، وتجاهل الأحداث ذات الاحتمالية 0، \[\mathbb P(H(\vv v_1)=H(\vv v_2)=H(\vv v_3))=h\mathbb P(H(\vv v_1)=H(\vv v_2)=H(\vv v_3)=1).\] نكتب \(G(\vv w; \vv v_1, \vv v_2, \vv v_3)\) للاحتمال أنه بالنسبة لمتجه ثابت \(\vv w\)، يحقق متجه غاوسي عشوائي \(\vv r\) الشرط \(|\vv v_n\cdot\vv w|\le |\vv v_n\cdot\vv r|\) لـ \(1\le n\le 3\). ثم بالاستقلالية، \[\mathbb P(H(\vv v_1)=H(\vv v_2)=H(\vv v_3)=1)=\int_{\vv w}G(\vv w; \vv v_1, \vv v_2, \vv v_3)^{h-1}d\mu(\vv w),\label{eq:pr(h=1)}\] حيث \(\mu\) هي مقياس كثافة الاحتمال الغاوسي الذي يأخذ في الحسبان احتمال أن \(\vv r_1=\vv w\).
في الواقع، \(G\) هي فقط دالة للجداءات القياسية الزوجية للمتجهات \(\vv v_n\). إذا كتبنا \(\lambda_n=\vv w\cdot \vv v_n\), \(\mu_1=\vv v_2\cdot\vv v_3\), \(\mu_2=\vv v_3\cdot\vv v_1\), \(\mu_3=\vv v_1\cdot\vv v_2\), فإننا نستطيع أن نربط بـ \(\vv w\) مجموعة من 8 متجهات مترافقة \(\{\vv w^{(c)}:\vv w^{(c)}\cdot\vv v_n=\pm \lambda_n\}\). هذه المتجهات تتوافق مع زوايا متوازي الأضلاع الذي تكون وجوهه الثلاثة أزواج من الأسطح المتوازية \(\{\vv r:\vv r\cdot\vv v_n=\pm\lambda_n\}\) وحوافه موازية مع المتجهات \(\vv v_m\times\vv v_n\). مجموعة المتجهات \(\vv r\) التي تحقق \(|\vv v_n\cdot\vv w|\le |\vv v_n\cdot\vv r|\) لـ \(1\le n\le 3\) هي ثم الحجم الذي يتشكل بواسطة الزوايا الصلبة المقابلة في كل من الرؤوس الثمانية لهذا المتوازي الأضلاع و\(G\) هي كتلة الغاوس لهذا الحجم.
كتلة غاوس للزوايا المقابلة المرتبطة بالنقطة \(\vv w^{(c)}\) يمكن التعبير عنها كتكا...