نُقَدِّم وَنُحَلِّل عائِلَةِ مِن دَوال التَجْزِئَةِ وَالمُفاضَلَة الَّتِي مِن المُرَجِّحِ أَنَّ تُنْتِج تَصادُمات لَتَكْوِينات صَغِيرَةٌ قابِلَةٍ لِلتَخْفِيض مِن المُتَّجِهات. قَد تَقَدَّمَ هٰذِهِ تَحْسِيناتٍ عَمَلِيَّةِ لَغَرْبَلَة الشَبَكَةِ لِلمُتَّجِهات القَصِيرَةِ. بِشَكْلٍ خاصٍّ، فِي نِظامِ تَقارُبِي واحِدٍ، تُظْهِر العائِلَةِ سُلُوكِ تَقارُبٍ مُخْتَلِفِ بِشَكْلٍ مَلْحُوظٍ عَن دَوال التَجْزِئَةِ وَالمُفاضَلَة الحالِيَّةِ.
نُقَدِّم فِي هٰذا البَحْثِ عائِلَةِ مِن دَوال التَجْزِئَةِ وَالمُفاضَلَة الَّتِي تَزِيد مِن اِحْتِمالَيْهِ حُدُوثِ تَصادُمات لَتَكْوِينات المُتَّجِهات الصَغِيرَةِ القابِلَةِ لِلتَخْفِيض. هٰذِهِ الدوال قَد تُوَفِّر تَحْسِيناتٍ عَمَلِيَّةِ لِعَمَلِيّاتِ غَرْبَلَةِ الشَبَكَةِ لِلمُتَّجِهات القَصِيرَةِ. بِشَكْلٍ خاصٍّ، فِي نِظامِ تَقارُبِي مُعَيَّنٍ، تُظْهِر هٰذِهِ العائِلَةِ مِن الدوال سُلُوكِ تَقارُبٍ مُخْتَلِفِ بِشَكْلٍ كَبِيرٍ عَن دَوال التَجْزِئَةِ وَالمُفاضَلَة المُسْتَخْدَمَةِ حالِيّاً.
تَعْتَمِد خوارزميات ما بُعْدَ الكَمِّ مِثْلَ 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)}\) يُمْكِن التَعْبِيرِ عَنها كَتَكامُل لَكُتَله غاوس لِتُقاطَع الزاوِيَةِ الصُلْبَةِ مَعَ الكُراتِ ذاتِ نِصْفِ القَطَر \(\rho\) الَّذِي يَتَراوَح مِن \(||\vv w^{(c)}||\) إِلَى اللانِهايَة. نَظَراً لِأَنَّ كَثافَةُ غاوس ثابِتَةٍ عَلَى كُلِّ كُرَةِ، فَإِنَّنا نَحْتاج فَقَط إِلَى حِسابِ النِسْبَةِ \(\eta(\rho,\vv w^{(c)})\) مِن الكُرَةِ الَّتِي تَتَقاطَع مَعَ الزاوِيَةِ الصُلْبَةِ. نَكْتُب \(M^{(c)}\) لَكُتَله غاوس لِلزاوِيَة المُقابَلَةِ عِنْدَ الرَأْسِ لَدَينا \[G=\sum_c M^{(c)};\quad\quad M^{(c)}=\frac1{\Gamma(3/2)}\int_{||\vv w^{(c)}||}^\infty \eta(\rho,\vv w^{(c)})\rho^2\exp(-\rho^2/2)d\rho.\] يُمْكِن حِسابِ \(\eta\) كَمِساحَةِ تُقاطِع ثَلاثِ قُبْعات كُرَوِيّه عَلَى الكُرَةِ ذاتِ نِصْفِ القَطَر \(\rho\) مَقْسُومه عَلَى مِساحَةِ الكُرَةِ. سَتَكُون القُبْعاتِ الثَلاثِ مُرَكَّزَةً عَلَى \(\pm\rho\vv v_1\)، \(\pm\rho\vv v_2\) وَ \(\pm\rho\vv v_1\) مَعَ عَلاماتِ مُناسَبَةِ للمترافق المَعْنِيَّ وَلَها اِرْتِفاعِ \(\rho-|\lambda_1|\)، \(\rho-|\lambda_2|\) وَ \(\rho-|\lambda_3|\) عَلَى التَوالِي. يُمْكِن حِسابِ مِساحَةِ تُقاطِع القُبْعَة الثُلاثِيَّةِ بِطَرِيقَةٍ مُماثِلَةٍ لِمِساحَةِ تُقاطِع ثَلاثِ دَوائِرِ أُقْلِيدِيّه حَيْثُ يَعْرِف نِصْفِ القَطَر وَالمَسافَة بَيِّنَ مَراكِزِ الدَوائِرِ (الرَسْمُ التَخْطِيطِيّ 2). وَبِالتالِي، فَإِنَّ مِساحَةِ التَقاطُعِ هِيَ مِساحَةِ المُثَلَّثِ \(I_1I_2I_3\) بِالإِضافَةِ إِلَى مِساحَةِ قِطاعاتِ الدائِرَةِ \(I_1I_2\)، \(I_2I_3\) وَ \(I_3I_1\). عَلَى كُرَتنا، يَتَوافَق القِطَعِ المُسْتَقِيم \(C_1C_2\) مَعَ قَوْس كَبِيرٍ بِطُولِ \(\rho\arccos\mu_1\) وَيَتَوافَق نِصْفِ القَطَر \(r_1\) مَعَ المَسافَةِ \(\rho\arccos(\lambda_1/\rho)\) آلخ. بِالنِسْبَةِ لَمُثَلَّث (كُرَوِيّ بَدَلاً مِن أُقْلِيدِيّ) بِزَوايا \(A\)، \(B\) وَ \(C\) مُقابِلَ أَضْلاع بِطُولِ \(a\)، \(b\) وَ \(c\) عَلَى التَوالِي \[\cos A=\frac{\cos a-\cos b\cos c}{\sin b\sin c}\] وَ \[\mathrm{Area}(\triangle abc)=A+B+C-\pi\] بِاِسْتِخْدامِ صِيَغٍ مِن المُثَلَّثات الكُرَوِيَّةُ. هٰذا يَسْمَح لَنا بِحِساب الزَوايا \(\angle I_1C_2I_3=\angle I_1C_2C_3+\angle C_1C_2I_3-\angle C_1C_2C_3\) آلخ. وَمِن ثُمَّ أَطْوال \(I_1I_2\) آلخ. وَمِن ثُمَّ مِساحَةِ التَقاطُعِ وَمِن ثُمَّ \(\eta\).
الآنَ بُعْدَ أَنَّ أَصْبَحَ لَدَينا وَسِيلَةً لَتَقْيِيم \(G\) بِشَكْلٍ صَرِيحٍ مِن حَيْثُ \(\lambda_n\) وَ \(\mu_n\)، يَبْدُو مَنْطِقِيّاً إِعادَةِ كِتابَةِ المُعادَلَةَ ([eq:pr(h=1)]) كَتَكامُل عَلَى \(\lambda_n\). نَسْتَخْدِم الأَساسِ المُزْدَوِجِ \(\{\vv v_n\}\) كَأَساسٍ لَفَضائنا ثُلاثِيّ الأَبْعاد؛ بِشَكْلٍ خاصٍّ نَكْتُب \(\vv w=\lambda_1\vv u_1+\lambda_2\vv u_2+\lambda_3\vv u_3\) حَيْثُ \[\vv u_1=(\vv v_2\times\vv v_3)/V, \quad \vv u_2=(\vv v_3\times\vv v_1)/V,\quad \vv u_3=(\vv v_1\times\vv v_2)/V,\quad V=\vv v_1\cdot(\vv v_2\times\vv v_3),\] وَ\(V\) هُوَ المُنْتِجِ الثُلاثِيِّ القِياسِيَّ لِ \(\vv v_n\). هٰذا الأَساسِ لَيِسَ مُتَعامِدا وَيَحْتاج تَعْبِيرِ كَثافَةُ الاِحْتِمالِ الغاوسيه إِلَى تَعْدِيلِ حَتَّى نَتَمَكَّن مِن كِتابَته كَدالّه مِن \(\lambda_n\). إِذا كُتُبِنا \(\vv i\), \(\vv j\), \(\vv k\) لَأَساس مُتَعامِد عَشْوائِيٍّ لَفَضائنا ثُلاثِيّ الأَبْعاد وَ\(\vv w=x\vv i+y\vv j+z\vv k\)، فَإِنَّ مِقْياسِ كَثافَةُ الاِحْتِمالِ الغاوسي هُوَ \[d\mu(\vv w) =\frac1{(2\pi)^{3/2}}\exp(-(x^2+y^2+z^2)/2)dxdydz.\] الآنَ، بِخَصائِص الأُسُسِ المُزْدَوِجَةِ \[\begin{pmatrix}\lambda_1 \\ \lambda_2 \\ \lambda_3\end{pmatrix}=B\begin{pmatrix}x\\ y\\ z\end{pmatrix}\] حَيْثُ \(B\) هِيَ مَصْفُوفه تَغْيِيرٍ الأَساسِ الَّتِي تَحْتَوِي عَلَى الأَسْطُر الَّتِي هِيَ مُتَّجِهات \(\vv v_1\), \(\vv v_2\), \(\vv v_3\) مَكْتُوبه فِي الأَساسِ \(\vv i\), \(\vv j\), \(\vv k\) (بِحَيْثُ \(\mathrm{det} B=V\)). يَتْبَع ذٰلِكَ \[x^2+y^2+z^2=\begin{pmatrix}\lambda_1&\lambda_2&\lambda_3\end{pmatrix}(BB^T)^{-1}\begin{pmatrix}\lambda_1 \\ \lambda_2 \\ \lambda_3\end{pmatrix}\] هُنا \(BB^T\) هِيَ مَصْفُوفه جرام \(M\) حَيْثُ \(M_{ij}=\vv v_i\cdot\vv v_j\). بِشَكْلٍ خاصٍّ، التَعْبِيرِ مُسْتَقِلٍّ عَن اِخْتِيارِ \(\vv i\), \(\vv j\) وَ \(\vv k\). كِتابَةِ \(q_{M^{-1}}(\lambda_1,\lambda_2,\lambda_3)\) لِلشَكْل الثُلاثِيِّ التَرْبِيعِيّ أَعْلاه، لَدَينا بُعْدَ ذٰلِكَ \[d\mu(\vv w) =\frac1{V(2\pi)^{3/2}}\exp(-q_{M^{-1}}(\lambda_1,\lambda_2,\lambda_3)/2)d\lambda_1d\lambda_2d\lambda_3.\]
لَتَلْخِيص هٰذا القِسْمِ، لَقَد أَظْهَرَنا
[th:numerical] لِيَكُن \(\mathcal V=\{\vv v_1, \vv v_2, \vv v_3\}\) مَجْمُوعَةِ مِن ثَلاثَةِ مُتَّجِهات وَحْدَةِ مُسْتَقِلَّةٍ خَطِّيّا. ثُمَّ لَتَجْزِئَة الإِسْقاط العَشْوائِيِّ \(H_{\mathcal R,h-1,1}\) لِمَجْمُوعَةِ مِن \(h\) مُتَّجِهات \(\mathcal R\) المُخْتارَة بِشَكْلٍ مُسْتَقِلٍّ وَمُوَزَّعه بِشَكْلٍ غاوسي، يُمْكِن حِسابِ اِحْتِمالِ التَصادُمُ الثُلاثِيِّ \(H(\vv v_1)=H(\vv v_2)=H(\vv v_3)\) كَما يَلِي \[\frac h{V(2\pi)^{3/2}}\int_{-\infty}^\infty\int_{-\infty}^\infty\int_{-\infty}^\infty G_\mathcal V(\lambda_1,\lambda_2,\lambda_3)^{h-1}\exp(-q_{M^{-1}}(\lambda_1,\lambda_2,\lambda_3)/2)d\lambda_1d\lambda_2d\lambda_3\] حَيْثُ \(q_{M^{-1}}\) هُوَ الشَكْلِ التَرْبِيعِيّ الثُلاثِيِّ المُرْتَبِطُ بِعَكْسِ مَصْفُوفه جرام \(\mathcal V\), \(V\) هُوَ المُنْتِجِ الثُلاثِيِّ القِياسِيَّ لَمُتَّجِهات \(\mathcal V\) وَ\(G_{\mathcal V}\) هُوَ كُتْلَةِ الغاوس لِلزَوايا الخارِجِيَّةِ لِلمُتَوازِي المُسْتَطِيل الَّذِي تَكُون حَوافّه الأَساسِ المُزْدَوِجِ لِ \(\mathcal V\) المَضْرُوب بِشَكْلٍ مُتَنَوِّعِ بِواسِطَةِ \(\lambda_i\). بِشَكْلٍ خاصٍّ يُمْكِن حِسابِ \(G_{\mathcal V}\) كَتَكامُل واحِدٍ عَلَى مَسافَةِ نُقْطَةً مِن الأَصْلِ.
هٰذِهِ هِيَ الحالَةِ \(k=3\) لِلمُقْتَرَح التالِي، الَّذِي نَحْذِف الدَلِيلَ عَلَيهِ.
لِيَكُن \(\mathcal V\) مَجْمُوعَةِ مِن \(k\) مُتَّجِهات وَحْدَةِ مُسْتَقِلَّةٍ خَطِّيّا. ثُمَّ لَتَجْزِئَة الإِسْقاط العَشْوائِيِّ \(H_{\mathcal R,h-1,1}\) لِمَجْمُوعَةِ مِن \(h\) مُتَّجِهات \(\mathcal R\) المُخْتارَة بِشَكْلٍ مُسْتَقِلٍّ وَمُوَزَّعه بِشَكْلٍ غاوسي، يُمْكِن حِسابِ اِحْتِمالِ التَصادُمُ \(k\)-way عَلَى عَناصِرِ \(\mathcal V\) كَما يَلِي \[\frac h{V(2\pi)^{k/2}}\int_{-\infty}^\infty\cdots\int_{-\infty}^\infty G_\mathcal V(\lambda_1,\ldots,\lambda_k)^{h-1}\exp(-q_{M^{-1}}(\lambda_1,\ldots,\lambda_k)/2)d\lambda_1\ldots d\lambda_k\] حَيْثُ \(q_{M^{-1}}\) هُوَ الشَكْلِ التَرْبِيعِيّ \(k\)-ary المُرْتَبِطُ بِعَكْسِ مَصْفُوفه جرام \(\mathcal V\), \(V\) هُوَ الزائِف القِياسِيَّ لَمُتَّجِهات \(\mathcal V\) وَ\(G_{\mathcal V}\) هُوَ كُتْلَةِ الغاوس لِلزَوايا الخارِجِيَّةِ لِلمُتَوازِي المُسْتَطِيل الَّذِي تَكُون حَوافّه الأَساسِ المُزْدَوِجِ لِ \(\mathcal V\) المَضْرُوب بِشَكْلٍ مُتَنَوِّعِ بِواسِطَةِ \(\lambda_n\). بِشَكْلٍ خاصٍّ يُمْكِن حِسابِ \(G_{\mathcal V}\) كَتَكامُل واحِدٍ عَلَى مَسافَةِ نُقْطَةً مِن الأَصْلِ.
وَبِالمِثْل، نُلاحِظ المُقْتَرَحِ التالِي بِدُونِ دَلِيلٌ.
لِيَكُن \(\mathcal V\) مَجْمُوعَةِ مِن \(k\) مُتَّجِهات وَحْدَةِ مُسْتَقِلَّةٍ خَطِّيّا. ثُمَّ لَتَجْزِئَة الإِسْقاط العَشْوائِيِّ \(H_{\mathcal R,1,h-1}\) لِمَجْمُوعَةِ مِن \(h\) مُتَّجِهات \(\mathcal R\) المُخْتارَة بِشَكْلٍ مُسْتَقِلٍّ وَمُوَزَّعه بِشَكْلٍ غاوسي، يُمْكِن حِسابِ اِحْتِمالِ التَصادُمُ \(k\)-way عَلَى عَناصِرِ \(\mathcal V\) كَما يَلِي \[\frac h{V(2\pi)^{k/2}}\int_{-\infty}^\infty\cdots\int_{-\infty}^\infty F_\mathcal V(\lambda_1,\ldots,\lambda_k)^{h-1}\exp(-q_{M^{-1}}(\lambda_1,\ldots,\lambda_k)/2)d\lambda_1\ldots d\lambda_k\] حَيْثُ \(q_{M^{-1}}\) هُوَ الشَكْلِ التَرْبِيعِيّ \(k\)-ary المُرْتَبِطُ بِعَكْسِ مَصْفُوفه جرام \(\mathcal V\), \(V\) هُوَ الزائِف القِياسِيَّ لَمُتَّجِهات \(\mathcal V\) وَ\(F_{\mathcal V}\) هُوَ كُتْلَةِ الغاوس لِلداخِلِيَّةِ لِلمُتَوازِي المُسْتَطِيل الَّذِي تَكُون حَوافّه الأَساسِ المُزْدَوِجِ لِ \(\mathcal V\) المَضْرُوب بِشَكْلٍ مُتَنَوِّعِ بِواسِطَةِ \(\lambda_n\). بِشَكْلٍ خاصٍّ يُمْكِن حِسابِ \(F_{\mathcal V}\) كَتَكامُل واحِدٍ عَلَى مَسافَةِ نُقْطَةً مِن الأَصْلِ.
فَضِيلَة هٰذِهِ المُقْتَرَحاتِ هِيَ أَنَّها تُقَلِّل مِن تَكامُلٍ ذُو أَبْعادَ \(hk\) إِلَى تَكامُلٍ ذُو أَبْعادَ \(k+1\) وَالَّذِي يُمْكِن التَعامُلِ مَعَهُ بِشَكْلٍ أَفْضَلَ بِاِسْتِخْدامِ تَقْنِيّاتِ التَحْلِيلِ العَدَدِيِّ الَّتِي تُوَفِّر حُدُوداً بَدَلاً مِن قِيَمِ اِحْتِمالَيْهِ (يُمْكِن اِعْتِبارِ القِسْمِ [sec:empirical] كَتَكامُل مَوَّنْتُ كارْلُو لِمِثْلِ هٰذِهِ التَكامُلات). وَمَعَ ذٰلِكَ، عَلَى الرَغْمِ مِن إِمْكانِيَّةَ التَوازِي العالِيَةِ، فَإِنَّ هٰذِهِ الطُرُقِ لا تَزال بَطِيئَةٍ حَتَّى لَقِيَم \(k\) مُتَواضِعَةٍ. بِالنِسْبَةِ لِ \(k=3\)، فَمِن المُمْكِنِ تَأْكِيدِ صِحَّةِ بِعَضِّ التَقْدِيراتِ التَجْرِيبِيَّة لِلقِسَم [sec:empirical] عَلَى أَنَّها أَعْلَى مِن مُعَدَّلاتِ التَصادُمُ الساذِجَة بِالإِضافَةِ إِلَى التَحْقِيقِ فِي مُعَدَّلِ التَقارُبِ لِنَتائِجِ القِسْمِ التالِي فِي حالَةِ \(h\) الكَبِيرَةِ.
لِفَهْمِ تَأْثِيرِ التَجْزِئَةِ بِالإِسْقاط العَشْوائِيِّ عَلَى تَعْقِيدِ خوارزميات الغَرْبَلَة، سَنَحْتاج إِلَى تَقْدِيرٍ تَقارُبِي لَاِحْتِمالات التَصادُمات \(k\)-طَرِيقِ وَمَجْمُوعاتٍ \(k\)-الناجِينَ مِن اِخْتِبارِ الشَرْطُ بِالنَظَرِ إِلَى تَكْوِينِ المُتَّجِهات \(k\) قَيْدِ النَظَرِ. فِي هٰذا القِسْمِ، نُقَدِّم تَقْدِيراً لوغاريتميا تقاربيا لِحالَةِ \(H_{\mathcal R,a,b}\) مَعَ \(a\) ثابِتٌ وَ\(b\) يَمِيل إِلَى اللانِهايَة وَتَقْدِيرٍ تَقارُبِي لِحالَةِ \(H_{\mathcal R,a,b}\) مَعَ \(b\) ثابِتٌ وَ\(a\) يَمِيل إِلَى اللانِهايَة. لَبَيان النَتِيجَةُ الأُولَى، نَحْتاج إِلَى تَوْضِيحِ الاِعْتِمادِ عَلَى التَكْوِين (المُنْتَجاتِ القِياسِيَّةِ الزَوْجِيَّةَ) لَمَجْمُوعَتنا المتصادمه مِن المُتَّجِهات \(V\)، وَلِهٰذا الغَرَضِ نُقَدِّم التَعْرِيفِ التالِي.
بِالنَظَرِ إِلَى مَجْمُوعَةِ \(V\) مِن المُتَّجِهات الوَحْدَةِ المُسْتَقِلَّةِ خَطِّيّا، يُمْكِننا الإِشارَةُ إِلَيها كَأَساسٍ لَاِمْتِدادها. دَعْ \(U=\{\vv u_1,\ldots,\vv u_k\}\) يَكُون الأَساسِ المُزْدَوِجِ وَنَظَرَ فِي المُتَوازِي المُسْتَطِيلات الَّذِي زَواياه هِيَ \(\pm \vv u_1\pm\vv u_2\cdots\pm\vv u_k\). نَعْرِف مُرَبَّعٍ أَقْصَرُ قَطَرِ مُزْدَوِج \(\alpha(V)\) لِيَكُون مُرَبَّعٍ طُولِ أَقْصَرُ قَطَرِ لِهٰذا المُتَوازِي المُسْتَطِيلات.
نُلاحِظ أَنَّهُ يُمْكِن حِسابِ \(\alpha(V)\) بِشَكْلٍ صَرِيحٍ مِن هُوِيّاتِ حِسابِ المُتَّجِهات، عَلَى الرَغْمِ مِن أَنَّ شَكَّلا مُغْلَقاً بَسِيطا وَعاما غَيْرِ مُتَوَفِّر. نُلاحِظ أَيْضاً أَنَّهُ فِي حالَةِ \(k=2\) \(\alpha=4/(4-\tau^2)\) حَسَبَ النَظَرِيَّةِ 1 مِن (angular).
تُعَمِّم هٰذِهِ الفَقْرَةِ النَظَرِيَّةِ الأُولَى مِن (angular) الَّتِي تُغَطِّي الحالَةِ المُوَقَّعَةِ \(k=2\), \(h=d\), \(a=1\), \(b=d-1\). مِن المُفِيدِ قِراءَةٍ البُرْهانُ غَيْرِ الرَسْمِيِّ لِهٰذِهِ النَظَرِيَّةِ لِتَحْدِيدِ السِياقِ لَتَعْمِيمها عَلَى حالَةِ \(k\) العامَّةِ وَعَدَمِ التَحَيُّزِ لِلإِشارَة سَواءُ عِنْدَما يَكُون \(a\) ثابِتاً وَ\(b\) يَمِيل إِلَى اللانِهايَة وَالعَكْسُ صَحِيحٌ.
تَعْمِيمِ بُرْهان النَظَرِيَّةِ الأُولَى فِي (angular) لَقِيَم أَكْبَرَ مِن \(k\) هُوَ أَمْرٌ مُباشِرٍ نِسْبِيّاً، بِشَرْطِ أَنَّ نَتَمَكَّن مِن إِثْباتِ تَعْمِيمِ الليما 5 مِن (angular) المُلْحَقِ B. نَرْغَب فِي تَقْدِيرٍ كُتْلَةِ غاوسيه لِلزَوايا الخارِجِيَّةِ لَمُتَوازِي الأَضْلاع \(k\)-الأَبْعاد حَيْثُ المَسافَةِ بَيِّنَ أَزْواج الوُجُوهَ المُقابَلَةِ \(k\) هِيَ نَفْسِها. هٰذِهِ حالَةِ مِن تَقْدِيرٍ الذَيْل لِتَوْزِيعِ غاوسي مُتَعَدِّدِ المُتَغَيِّراتِ وَعَلَى الرَغْمِ مِن وُجُودِ أَدَبِيّاتِ بِالفِعْلِ حَوْلَ هٰذا المَوْضُوعِ، فَإِنَّنا نَكْتَفِي بِتَطْوِيرِ حَدّنا اللوغاريتمي التقاربي الخامِ.
خِلالَ هٰذِهِ الفَقْرَةِ نَكْتُب \(\Phi_k(t)\) لَدالّه التَوْزِيعِ التراكمي لَطُول مُتَّجِه غاوسي \(k\)-الأَبْعاد أَيّ \[\Phi_k(t)=\underset{\vv r\sim\mathcal N(0,1)^k}{\mathbb P}(|r|<t).\] سَنَسْتَخْدِم حَقِيقَةِ أَنَّهُ لِ \(k\) ثابِتَةٍ ك \(t\to\infty\) لَدَينا \(1-\Phi_k(t)=\exp(-(1+O(\log t)/t^2)t^2/2)\) وَبِالتالِي عَلَى وَجْهِ الخُصُوصِ \(1-\Phi_k(t)=(1-\Phi_1(t))^{1+O((\log t)/t^2)}\).
[lem:exterior] لِتَكُن \(G(w)\) كُتْلَةِ غاوسيه لِلزَوايا الخارِجِيَّةِ لَمُتَوازِي أَضْلاع \(k\)-الأَبْعاد مَرْكَزِهِ الأَصْلِ، حَيْثُ جَمِيعِ الوُجُوهَ المُقابَلَةِ عَلَى بُعْدَ \(2w\) وَأُقَصِّر قَطَرِ لَهُ طُولِ \(2\sqrt\alpha w\) \[(1-\Phi_k(w))^{\alpha +O((\log w)/w^2)}<G(w)<(1-\Phi_k(w))^{\alpha+O((\log w)/w^2)}\] ك \(w\to\infty\).
نُلاحِظ أَنَّ المِنْطَقَةِ الَّتِي نَرْغَب فِي حِسابِ كُتْلَتها الغاوسيه مُحْتَواه ضِمْنَ مكمل الكُرَةِ \(k\)-المُرَكَّزَةِ فِي الأَصْلِ بِنِصْفِ قَطَرِ \(\sqrt\alpha w\) بِحَيْثُ \(G(w)<1-\Phi_k(\alpha w)=(1-\Phi_k(w))^{\alpha+O((\log w)/w^2)}\).
لِلحَدِّ الأَعْلَى نَعْتَبِر مُتَوازِي أَضْلاع صَغِيرٍ ضِمْنَ مِنْطَقَتِنا يَقَع عِنْدَ الزاوِيَةِ المُتاخِمَةِ لِأُقَصِّر قَطَرِ. نَأْخُذ أَطْوال الجَوانِبِ \(\epsilon w\) بِحَيْثُ أَنَّ أَبْعَدَ مَسافَةِ لَنُقَطه فِي مُتَوازِي الأَضْلاع الصَغِيرِ مِن الأَصْلِ هِيَ \((1+\epsilon)\sqrt \alpha w\). وَبِالتالِي فَإِنَّ كَثافَةُ غاوسيه لِلنِقاط ضِمْنَ مُتَوازِي الأَضْلاع هِيَ عَلَى الأَكْثَرَ \(\exp(-(1+\epsilon^2)\alpha w^2)\) وَالحَجْم هُوَ \((\epsilon w/2)^kV\) حَيْثُ \(Vw^k\) هُوَ حَجْمِ مُتَوازِي الأَضْلاع لَدَينا. يَتْبَع ذٰلِكَ \[G(w) > (\epsilon w/2)^kV\exp(-(1+\epsilon^2)\alpha w^2).\] إِذا أَخَذْنا \(\epsilon=(\log w)/w\) لَدَينا \( (\epsilon w/2)^kV\exp(-(1+\epsilon^2)\alpha w^2)>(1-\Phi_k(w))^{\alpha+O((\log w)/w^2)}\) وَيَتَّبِع النَتِيجَةُ.
نَتَوَقَّف لِنُلاحَظ أَنَّ هٰذِهِ الليما تُوَفِّر تَقْدِيراً تقاربيا مُفِيداً لَمُعَدَّلات البَقاءَ لل \(k\)-أَنْماطُ عِنْدَ التَصْفِيَةِ حَسَبَ حَجْمِ إِسْقاطِ عَشْوائِيٍّ حَسَبَ (filter).
لِتَكُن \(P_{\vv r}(\vv v):\mathbb R^d\to\{0,1\}\) دالَّةٍ حُكْمِ (عَشْوائِيَّةٍ) تُعِيد 1 إِذا كانَ \(|\vv v\cdot\vv r|>C\) و0 خِلافٍ ذٰلِكَ لِبَعْضِ القِيمَةِ الكَبِيرَةِ \(C\) حَيْثُ \(r\sim\mathcal N(0,1)^d\). ثُمَّ بِالنَظَرِ إِلَى مَجْمُوعَةِ \(V\subset \mathbb R^d\) مِن \(k\) مُتَّجِهات وَحْدَةِ مُسْتَقِلَّةٍ خَطِّيّا \[\mathbb P_{\vv r\sim\mathcal N(0,1)^d}(P_{\vv r}(\vv v)=1\ \forall \vv v\in V)= (1-\Phi_k(C))^{\alpha(\mathcal V)+O((\log C)/C^2)}\] حَيْثُ \(\alpha(\mathcal V)\) هُوَ مُرَبَّعٍ أَقْصَرُ قَطَرِ مُزْدَوِج لِلمُتَّجِهات.
عائِدِينَ إِلَى مَوْضُوعنا الرَئِيسِيُّ، نَحْنُ الآنَ فِي وَضْعِ يُمْكِننا مِن تَقْدِيمِ وَإِثْباتِ نَتِيجَتنا التقاربيه
[th:asymptotic_B] أَفْتَرِض أَنَّ \(V:=\{\vv v_1, \ldots, \vv v_k\}\in S^{d-1}\) وَلِتَكُن \(\alpha(V)\) هِيَ مُرَبَّعٍ أَقْصَرُ قَطَرِ مُزْدَوِج لِ \(V\). لِتَكُن \(a\) عَدَدٍ صَحِيحٌ ثابِتٌ وَ\(b\) عَدَدٍ صَحِيحٌ يَمِيل إِلَى اللانِهايَة. لِتَكُن \(H_{\mathcal R,a,b}\) عائِلَةِ مِن تَجْزِئات الإِسْقاط العَشْوائِيِّ بِاِسْتِخْدامِ مَجْمُوعَةِ مِن \(a+b\) مُتَّجِهات عَشْوائِيَّةٍ الَّتِي مُكَوِّناتها \(d\) مُتَغَيِّراتِ \(\mathcal N(0,1)\) مُسْتَقِلَّةٍ وَمُتَطابِقه التَوْزِيعِ. ثُمَّ \[\mathbb P_{H\sim \mathcal H_{\mathcal R,a,b}}(H(\vv v_1)=\cdots=H(\vv v_k))=\frac {B((1+o(1))\alpha a,b)}{B(a,b)}\] ك \(b\to\infty\)
نُثْبِت مَجْمُوعَتنا مِن مُتَّجِهات الوَحْدَةِ \(V=\{\vv v_1,\ldots,\vv v_k\}\)، وَلِأَيّ مَجْمُوعَةِ مِن \(a\) مُتَّجِهات \(\mathcal R_a\subset R\) وَنَعْرِف \(s_{\min}(\mathcal R_a)\) لِتَكُون \(\min_{\vv r\in\mathcal R_a\atop1\le n\le k}|\vv v_n\cdot \vv r|\) وَ\(\vv v(\mathcal R_a)\) لِتَكُون أَيّ مُتَّجِه فِي \(V\) يَتَحَقَّق فِيهِ هٰذا الحَدِّ الأَدْنَى. بِالنَظَرِ إِلَى مُتَّجِه غاوسي عَشْوائِيٍّ \(\vv s\) نَرِي أَنَّ \[\mathbb P(|\vv s\cdot\vv v|< s_{\min}(\mathcal R_a))\le \mathbb P(|\vv s\cdot\vv v_n|<|\vv r\cdot \vv v_n|\ \forall \vv r\in\mathcal R_a,\ 1\le n\le k) \le \mathbb P(|\vv s|<s_{\min}).\] بِفَضْلِ التَماثُلِ الدَوَرانِيّ لِلتَوْزِيع الغاوسي، فَإِنَّ الإِسْقاط \(\vv s\) عَلَى \(\vv v\) يُوَزِّع \(\mathcal N(0,1)\) بِغَضِّ النَظَرِ عَن \(\vv v\) وَبِالتالِي \[\Phi_1(s_{\min}(\mathcal R_a))\le \mathbb P(|\vv s\cdot\vv v_n|<|\vv r\cdot \vv v_n|\ \forall \vv r\in\mathcal R_a,\ 1\le n\le k) \le \Phi_k(s_{\min}(\mathcal R_a)).\] عِلاوَةً عَلَى ذٰلِكَ، لِمَجْمُوعَةِ \(\mathcal S\) مِن \(b\) مُتَّجِهات غاوسيه مُسْتَقِلَّةٍ نَرِي أَنَّهُ بِالاِسْتِقْلالِ \[\Phi_1(s_{\min}(\mathcal R_a))^b\le \mathbb P(|\vv s\cdot\vv v_n|<|\vv r\cdot \vv v_n|\ \forall \vv s\in\mathcal S,\ \vv r\in\mathcal R_a,\ 1\le n\le k) \le \Phi_k(s_{\min}(\mathcal R))^b.\] وَبِالتالِي، إِذا كُتُبِنا \(F_s(t)\) لِتَكُون دالَّةٍ التَوْزِيعِ التراكمي لِ \(s_{\min}(\mathcal R_a)\) عِنْدَما يَتَكَوَّن \(R_a\) مِن \(a\) مُتَّجِهات غاوسيه مُسْتَقِلَّةٍ وَمُتَطابِقه التَوْزِيعِ، بِقانُونِ الاِحْتِمالِ الكُلِّيِّ نَرِي أَنَّ اِحْتِمالِ \(p\) لَتَصادُم \(k\) فِي دالَّةٍ التَجْزِئَةِ لَدَينا يُلَبِّي \[\binom{a+b}a\int_0^\infty \Phi_1(t)^bdF_s(t)\le p\le\binom{a+b}a\int_0^\infty \Phi_k(t)^b dF_s(t).\] التَكامُلِ بِالأَجْزاء يُخْبِرنا بُعْدَ ذٰلِكَ \[\binom{a+b}ab\int_0^\infty \Phi_1(t)^{b-1}(1-F_s(t))\Phi'_1(t)dt\le p\le\binom{a+b}ab\int_0^\infty \Phi_k(t)^{b-1}(1-F_s(t))\Phi'_k(t)dt.\] لَتَكْيِيف التَقْدِيراتِ التقاربيه، نَتَكَيَّف مَعَ الحُدُودِ الدُنْيا لَتَكامُلاتنا لِتَمِيل إِلَى اللانِهايَة: \[p\ge \binom{a+b}ab\int_{t_0}^\infty \Phi_1(t)^{b-1}(1-F_s(t))\Phi'_1(t)dt,\] \[p\le\binom{a+b}ab\int_{t_1}^\infty \Phi_k(t)^{b-1}(1-F_s(t))\Phi'_k(t)dt+\binom{a+b}a\Phi_k(t_1)^b.\]
الآنَ، بِالنَظَرِ إِلَى التَوْزِيعِ الذيلي لِ \(s_{\min}\) \[\begin{aligned} 1-F_s(t)&=&\underset{\mathcal R_a}{\mathbb P}(|\vv r\cdot\vv v_n|>t\ \forall \vv r\in\mathcal R_a,\ 1\le n\le k)\\ &=&\underset{\vv r\sim\mathcal N(0,1)^k}{\mathbb P}(|\vv r\cdot\vv v_n|>t\ ,\forall 1\le n\le k)^a \end{aligned}\] نَكْتُب \(G(V,t)\) لِ \(\mathbb P(|\vv r\cdot\vv v_n|>t\ ,\forall 1\le n\le k)\) وَنُلاحَظ أَنَّ هٰذِهِ هِيَ كُتْلَةِ غاوسيه لِلزَوايا الخارِجِيَّةِ لَمُتَوازِي الأَضْلاع المَرْكَزِ عَلَى الأَصْلِ الَّذِي حَوافّه هِيَ المُتَّجِهات \(2t\vv v^{n}\)، حَيْثُ \(\vv v^{n}\) هُوَ الأَساسِ المُزْدَوِجِ لِ \(V\) فِي الفَضاءِ المُتَّجِه \(\mathrm{Span}(V)\). بليمانا [lem:exterior] لَدَينا بُعْدَ ذٰلِكَ ك \(t\to\infty\) \[(1-\Phi_k(t))^{\alpha+O((\log t)/t^2)}<G(V,t)<(1-\Phi_k(t))^{\alpha+O((\log t)/t^2)}.\] وَبِالتالِي لَحَدّنا الأَعْلَى لَدَينا
\[\begin{aligned} p &\le& \binom{a+b}{a}b \int_{t_1}^\infty \Phi_k(t)^{b-1}(1-\Phi_k(t))^{\alpha a(1+O((\log t_1)/t_1^2))}\Phi'_k(t)dt + \binom{a+b}{a}\Phi_k(t_1)^b\\ &=& \binom{a+b}{a}b \int_{\Phi_k(t_1)}^1 u^{b-1}(1-u)^{\alpha a(1+O((\log t_1)/t_1^2))}du + \binom{a+b}{a}\Phi_k(t_1)^b\\ &\le& \binom{a+b}{a}\left(bB(1+\alpha a(1+O((\log t_1)/t_1^2)),b)+\Phi_k(t_1)^b\right)\end{aligned}\]
وَبِالنِسْبَةِ لِلحَدِّ الأَدْنَى لَدَينا \[\begin{aligned} p &\ge& \binom{a+b}{a}b \int_{t_0}^\infty \Phi_1(t)^{b-1}(1-\Phi_k(t))^{\alpha+O((\log t)/t^2)}\Phi'_1(t)dt\\ &\ge& \binom{a+b}{a}b \int_{t_0}^\infty \Phi_1(t)^{b-1}(1-\Phi_1(t))^{\alpha a(1+O((\log t_0)/t_0^2))}\Phi'_1(t)dt\\ &=& \binom{a+b}{a}b \int_{\Phi_k(t_0)}^1 u^{b-1}(1-u)^{\alpha a(1+O((\log t_0)/t_0^2))}du\\ &=& \binom{a+b}{a}bB(1+\alpha a(1+O((\log t_0)/t_0^2)),b)I_{\Phi_k(t_0)}(1+\alpha a(1+O((\log t_0)/t_0^2),b)\end{aligned}\] حَيْثُ نَسْتَخْدِم هُنا دالَّةٍ بَيْتا غَيْرِ مُكْتَمَلَةٍ مُعْتاده. بِعَضِّ هُوِيّاتِ دالَّةٍ بَيْتا تُعْطِي بِسُرْعَةٍ الشَكْلِ الأَكْثَرَ قابِلِيَّةِ لِلعَرْضِ \[\binom{a+b}{a}bB(1+\alpha a,b)=\frac{\alpha(a+b)}{\alpha a+b}\frac{B(\alpha a,b)}{B(a,b)}.\] اِخْتِيارِ \(t_0\) وَ \(t_1\) لِتَلْبِيَةِ، عَلَى سَبِيلِ المِثالِ، \(\Phi_k(t_0)=\Phi_k(t_1)=1-1/\sqrt{b}\) أَكْثَرَ مِن كافٍ لِلسَماحِ لَهُما بِالتَوَجُّهِ إِلَى اللانِهايَة، مَعَ اِسْتِيعابِ مُصْطَلَحاتنا المُساعَدَةِ فِي لُوغارِيتْمنا اللانِهائِيّ كَما \(b\to\infty\). \[p=\frac{B(\alpha a(1+o(1)),b)}{B(a,b)}.\]
نُلاحِظ أَنَّهُ لِ \(a\) ثابِتٌ، لَدَينا \(B(\alpha a(1+o(1)),b)/B(a,b)=b^{(1-\alpha)a(1+o(1))}\).
نُثْبِت الآنَ نُسْخَةً مِن نَظَرِيَّةَ asymptotic_B لِقِيمَةِ ثابِتَةٍ مِن \(b\) وَقِيمَةُ \(a\) تَمِيل إِلَى اللانِهايَة. يَنْشَأ التَقْدِيرِ الرَئِيسِيُّ لِهٰذا الاِحْتِمالِ مِن القُوَّةِ \(b\) لَكُتَله الغاوس لِلجُزْء الداخِلِيِّ مِن مُتَوازِي الأَضْلاع الصَغِيرِ المَرْكَزِ عَلَى الأَصْلِ مَضْرُوبا فِي القُوَّةِ \(a\) لَكُتَله الغاوس لَزَواياه الخارِجِيَّةِ. بِالقُرْبِ مِن الأَصْلِ، لا تُهَيْمِن كَثافَةُ الغاوس عَلَى الحَدِّ \(\exp(-t^2/2)\) الَّذِي كانَ مُفِيداً فِي إِلْغاءِ الحُدُودِ اللوغاريتميه التَقْرِيبِيَّة فِي بِرِهاننا السابِقِ، بَل هِيَ بَدَلاً مِن ذٰلِكَ تَتَناسَب مَعَ \(t^{k-1}+O(t^{k-3})\) (وَهٰذا هُوَ سَبَبُ الحاجَةِ إِلَى إِدْخالُ \(t_0\) وَ \(t_1\) فِي بِرِهاننا السابِقِ). لَبُرْهاننا التالِي، سَنَسْتَخْدِم حَدٍّ التَرْكِيزِ حَوْلَ الأَصْلِ. عَلَى وَجْهِ التَحْدِيدِ، نَكْتُب \(\erf\) لَدالّه الخَطَأ الغاوسيه وَنُلاحَظ أَنَّ \[\erf(t/\sqrt 2)=\frac1{\sqrt{2\pi}}\int_{-t}^te^{-x^2/2}dx=\sqrt{\frac2\pi}t+O(t^2)\] لَقِيَم صَغِيرَةٌ مِن \(t\).
[lem:interior_B] لِتَكُن \(F(\vv s)\) كُتْلَةِ الغاوس لِلجُزْء الداخِلِيِّ مِن مُتَوازِي أَضْلاع ذُو \(k\) بُعْدَ، مَرْكَزِ عَلَى الأَصْلِ، وَوُجُوهه عَمُودَيْهِ عَلَى مَجْمُوعَةِ ثابِتَةٍ مِن المُتَّجِهات \(\vv v_1,\ldots,\vv v_k\) وَتَبْعُد مَسافَةِ \(2|\vv s\cdot\vv v_n|\) لِكُلِّ \(1\le n\le k\). ثُمَّ \[\left(1+O(||\vv s||_\Lambda^2\right)\frac1\Delta\prod_n\frac{2|\vv s\cdot\vv v_n|}{\sqrt{2\pi}}<F(\vv s)<\frac1\Delta\prod_n\frac{2|\vv s\cdot\vv v_n|}{\sqrt{2\pi}}\] حَيْثُ \(||\vv s||_\Lambda=\max_n|\vv s\cdot\vv v_n|\) وَ \(\Delta\) هُوَ حَجْمِ المُتَوازِي الأَضْلاع الَّذِي يُوَلِّده \(\vv v_n\).
بِاِسْتِخْدامِ نَفْسِ نِظامِ الإِحْداثِيّات كَما فِي القِسْمِ [sub:cartesian]، يُمْكِن التَعْبِيرِ عَن كُتْلَتنا كَالتالِي \[F(\vv s)=\frac1{\Delta(2\pi)^{k/2}}\int_{-|\vv s\cdot\vv v_k|}^{+|\vv s\cdot\vv v_k|}\cdots\int_{-|\vv s\cdot\vv v_1|}^{+|\vv s\cdot\vv v_1|}\exp(-q_{M^{-1}}(\lambda_1,\ldots,\lambda_k)/2)d\lambda_1\ldots d\lambda_k.\] الآنَ إِذا كُتُبِنا \(q_0\) لِلقِيمَةِ القُصْوَى لِ \(q_{M^{-1}}(\lambda_1,\ldots,\lambda_k)\) عَلَى حُدُودِ المُكَعَّب الفائِق \([-1,1]^k\)، لَدَينا بِالتَجانُس أَنَّ \[0\le q_{M^{-1}}(\lambda_1,\ldots,\lambda_k)\le q_0||\vv s||_\Lambda^2\] فِي مِنْطَقَتِنا المُتَكامِلَةَ وَبِالتالِي \[1- \frac{q_0||\vv s||_\Lambda^2}2\le \exp(-q_{M^{-1}}(\lambda_1,\ldots,\lambda_k)/2)\le 1\] وَ \[\left(1+O(||\vv s||_\Lambda^2)\right)\frac1\Delta\prod_n\frac{2|\vv s\cdot\vv v_n|}{\sqrt{2\pi}}|\le F(\vv s)\le\frac1\Delta\prod_n\frac{2|\vv s\cdot\vv v_n|}{\sqrt{2\pi}}\] كَما هُوَ مَطْلُوبٌ.
مَرَّةً أُخْرَى، لِأَغْراضٍ التَصْفِيَةِ، نُلاحِظ ما يَلِي
لِتَكُن \(P_{\vv r}(\vv v):\mathbb R^d\to\{0,1\}\) دالَّةٍ حُكْمِ (عَشْوائِيَّةٍ) تُعِيد 1 إِذا كانَ \(|\vv v\cdot\vv r|<c\) و0 فِي غَيْرِ ذٰلِكَ لِقِيمَةِ صَغِيرَةٌ \(c\) حَيْثُ \(r\sim\mathcal N(0,1)^d\). ثُمَّ بِالنَظَرِ إِلَى مَجْمُوعَةِ \(V\subset \mathbb R^d\) مِن \(k\) مُتَّجِهات مُسْتَقِلَّةٍ خَطِّيّا \[\mathbb P_{\vv r\sim\mathcal N(0,1)^d}(P_{\vv r}(\vv v)=1\ \forall \vv v\in V)= \left(1+O(c^2)\right)\frac1\Delta\left(\frac{2c^2}\pi\right)^{k/2}\] حَيْثُ \(\Delta\) هُوَ حَجْمِ المُتَوازِي الأَضْلاع الَّذِي تُوَلِّده \(V\).
[lem:exterior_B] لِتَكُن \(G(\vv s)\) كُتْلَةِ الغاوس لِلزَوايا الخارِجِيَّةِ لَمُتَوازِي أَضْلاع ذُو \(k\) بُعْدَ، مَرْكَزِ عَلَى الأَصْلِ، وَوُجُوهه عَمُودَيْهِ عَلَى مَجْمُوعَةِ ثابِتَةٍ مِن المُتَّجِهات \(\vv v_1,\ldots,\vv v_k\) وَتَبْعُد مَسافَةِ \(2|\vv s\cdot\vv v_n|\) لِكُلِّ \(1\le n\le k\). ثُمَّ \[\left(1+O(||\vv s||_\Lambda^2\right)\prod_n\left(1-\frac{2|\vv s\cdot\vv v_n|}{\sqrt{2\pi}}\right)\le G(\vv s)\le\left(1+O(||\vv s||_\Lambda^2\right)\prod_n\left(1-\frac{2|\vv s\cdot\vv v_n|}{\sqrt{2\pi}}\right)\] كَما \(||\vv s||_\Lambda\to 0\) حَيْثُ \(||\vv s||_\Lambda=\max_n|\vv s\cdot\vv v_n|\).
بِاِسْتِخْدامِ الحَدِّ الأَعْلَى لِلاِتِّحادِ، كَما \(||\vv s||_\Lambda\to 0\) \[G(\vv s)\ge1- \sum_{n=1}^k(1-\erf(|\vv s\cdot\vv v_n|/\sqrt2))=1-\sum_{n=1}^k\sqrt{\frac2\pi}|\vv s\cdot\vv v_n|+O(||\vv s||_\Lambda^2).\] عِلاوَةً عَلَى ذٰلِكَ، \[1-\sum_{n=1}^k\sqrt{\frac2\pi}|\vv s\cdot\vv v_n|=\left(1+O(||\vv s||_\Lambda^2)\right)\prod_n\left(1-\frac{2\vv |\vv s\cdot\vv v_n|}{\sqrt{2\pi}}\right).\]
بِالمِثْلِ، لِلمُساواة اليُمْنَى، نُلاحِظ أَنَّ \[\mathbb P_{\vv r\sim\mathcal N(0,1)^k}(|\vv r\cdot\vv v_m|>|\vv s\cdot\vv v_m|,|\vv r\cdot\vv v_n|>|\vv s\cdot\vv v_n|)\le(1-\erf(|\vv s\cdot\vv v_m|/\sqrt 2))(1-\erf(|\vv s\cdot\vv v_n|/\sqrt 2))\] ثُمَّ نُطَبِّق الحَدِّ الثانِي لبونفيروني: \[G(\vv s)\le1- \sum_{n=1}^k(1-\erf(|\vv s\cdot\vv v_n|/\sqrt 2))+\sum_m\sum_{n\neq m}(1-\erf(|\vv s\cdot\vv v_m|/\sqrt 2))(1-\erf(|\vv s\cdot\vv v_n|/\sqrt 2))\] نَسْتَنْتِج أَنَّ \[G(\vv s)\le\left(1+O(||\vv s||_\Lambda^2)\right)\prod_n\left(1-\frac{2\vv |\vv s\cdot\vv v_n|}{\sqrt{2\pi}}\right)\] وَيَتَّبِع النَتِيجَةُ.
[th:asymptotic_A] أَفْتَرِض أَنَّ \(V:=\{\vv v_1, \ldots, \vv v_k\}\in S^{d-1}\). لِتَكُن \(b\) عَدَداً صَحِيحاً ثابِتاً وَ\(a\) عَدَداً صَحِيحاً يَمِيل إِلَى اللانِهايَة. لِتَكُن \(H_{\mathcal R,a,b}\) عائِلَةِ مِن التَجْزِئات العَشْوائِيَّةِ بِاِسْتِخْدامِ مَجْمُوعَةِ مِن \(a+b\) مُتَّجِهات عَشْوائِيَّةٍ الَّتِي تَكُون مُكَوِّناتها \(d\) مُتَغَيِّراتِ \(\mathcal N(0,1)\) مُسْتَقِلَّةٍ وَمُوَزَّعه بِشَكْلٍ مُتَطابِقٌ. ثُمَّ \[\mathbb P_{H\sim \mathcal H_{\mathcal R,a,b}}(H(\vv v_1)=\cdots=H(\vv v_k))=(1+o(1))\Delta^{-b}\binom{a+b}b^{-k+1}.\] كَما \(a\to\infty\)، حَيْثُ \(\Delta\) هُوَ حَجْمِ المُتَوازِي الأَضْلاع الَّذِي تُوَلِّده \(V\).
نُثْبِت مَجْمُوعَتنا مِن المُتَّجِهات ذاتِ الطُولَ الوَحْدَةِ \(V=\{\vv v_1,\ldots,\vv v_k\}\)، وَلِأَيّ مَجْمُوعَةِ مَحْدُودَةٍ مِن المُتَّجِهات \(\mathcal R_b\) وَنَعْرِف (حَتَّى الأَحْداثِ ذاتِ اِحْتِمالَيْهِ الصِفْرِ) المُتَّجِهات \(\hat{\vv r}_n\in\mathcal R_b\) بِحَيْثُ \(|\vv v_n\cdot\hat{\vv r}_n|=\min_{\vv r\in\mathcal R}|\vv v_n\cdot \vv r|\) لِكُلِّ \(1\le n\le k\). ثُمَّ نَعْرِف \(\vv r_{\min}(\mathcal R_b)\) لِيَكُون المُتَّجِه الفَرِيدِ بِحَيْثُ \(\vv v_n\cdot\vv r_{\min}=\vv v_n\cdot \hat{\vv r}_n\) لِكُلِّ \(1\le n\le k\). نُلاحِظ أَنَّ \(\vv r_{\min}\) لا يَقَع بِالضَرُورَةِ فِي \(\mathcal R_b\)، عَلَى الرَغْمِ مِن أَنَّهُ زاوِيَةِ أَصْغَرِ مُتَوازِي أَضْلاع تَكُون وُجُوهِهِ عَمُودَيْهِ عَلَى \(\vv v_n\) وَالَّتِي تَحْتَوِي عَلَى كُلِّ مِن \(\mathcal R_b\). لَتَصادُم مُعَيَّنٍ، سَنَحْتاج إِلَى \(a\) مُتَّجِهات أُخْرَى لِتَقَع فِي الزَوايا الخارِجِيَّةِ لِهٰذا المُتَوازِي الأَضْلاع. وَبِالتالِي مُشابِها لَبُرْهان النَظَرِيَّةِ [th:asymptotic_B]، إِذا كُتُبِنا \(p\) لِاِحْتِمالِ مِثْلَ هٰذا التَصادُمُ، فَإِنَّ \[p=\binom{a+b}a\int\cdots\int_{\mathbb R^k}G(\vv s)^adF_{\vv r_{\min}}(\vv s)\] حَيْثُ \(G(\vv s)\) هِيَ كُتْلَةِ الغاوس المَوْصُوفَة فِي الليما [lem:exterior_B]. نَتَوَقَّع أَنَّ يَتَرَكَّز مُعْظَمَ وَزْنِ هٰذا التَعْبِيرِ حَوْلَ الأَصْلِ. نُرَكِّز عَلَى دَمْجِ \(\vv s\) عَبْرَ مِنْطَقَةِ \(\mathcal L:=\{\vv s:-\Lambda\le\vv s\cdot\vv v_n\le\Lambda, 1\le n\le k\}\) وَالَّتِي تُعْطِي تِلْقائِيّا حَدا أَدَّنِي وَنُلاحَظ بِشَكْلٍ خَشُنَ أَنَّهُ لِ \(\vv s\) خارِجَ \(\mathcal L\)، فَإِنَّ الكُتْلَةِ \(G\) أَقَلَّ مِن كُتْلَةِ واحِدَةٍ مِن المَناطِقِ \(k\) \(\{\vv w:|\vv w\cdot\vv v_n|>\Lambda\}\) وَالَّتِي كُلِّ مِنها مِن الكُتْلَةِ \(1-\erf(\Lambda/\sqrt2)\). يَتْبَع ذٰلِكَ \[\idotsint_{\mathcal L}G(\vv s)^adF_{\vv r_{\min}}(\vv s)\le\frac p{\binom{a+b}a}\le\idotsint_{\mathcal L}G(\vv s)^adF_{\vv r_{\min}}(\vv s)+(1-\erf(\Lambda/\sqrt2)^a.\]
\[\begin{aligned} \frac p{\binom{a+b}a}&\ge&\idotsint_{\mathcal L}F_{\vv r_{\min}}(\vv s)dG^a(\vv s)\\ &\ge&\idotsint_{\mathcal L}F_L(\vv s)G_L^{a-1}dG(\vv s)\end{aligned}\]
وَبِالمِثْل \[\frac p{\binom{a+b}a}\le \idotsint_{\mathcal L}F_U(\vv s)G_U^{a-1}dG(\vv s)+(1-\erf(\Lambda/\sqrt2))^a\] مُماثِلا لِنَظَرِيَّةِ numerical نَقُوم بِتَغْيِيرِ المُتَغَيِّراتِ \(\lambda_n=\vv s\cdot\vv v_n\) لِ \(1\le n\le k\). بِالنِسْبَةِ لَمِنْطَقَتنا مِن التَكامُلِ، يُمْكِننا أَخَذَ \(dG=(1+O(\lambda^2))(2\pi)^{-k/2}\prod d_{\lambda_n}\) . نُلاحِظ أَنَّ \(F_{\vv r_{\min}}(\vv s)=F(\vv s)^b\) حَيْثُ \(F(\vv s)\) هِيَ الدالَّةِ فِي ليما interior_B. لُذّاً، عِنْدَ كِتابَةِ التَكامُلِ الخاصِّ بِنا مِن حَيْثُ المُتَغَيِّراتِ \(\lambda_n\)، بِناءَ عَلَى ليماتنا يُمْكِننا أَخَذَ \(G_L=(1+O(\Lambda^2)) \prod_n(1-2|\lambda_n|/\sqrt{2\pi})\), \(G_U=(1+O(\Lambda^2))\prod_n(1-2|\lambda_n|/\sqrt{2\pi})\), \(F_L=\Delta^{-b}(1+O(\Lambda^2))^b(\prod2|\lambda_n|/\sqrt{2\pi})^b\), \(F_U=\Delta^{-b}(1+O(\Lambda^2))^b(\prod2|\lambda_n|/\sqrt{2\pi})^b\). وَبِالتالِي \[\frac p{\binom{a+b}a}\ge\Delta^{-b}(1+O(\Lambda^2))^{k(a+b)}\left(2a(2\pi)^{k/2}\int_0^\Lambda(1-2\lambda/\sqrt{2\pi})^{a-1}(2\lambda/\sqrt{2\pi})^bd\lambda\right)^k\] \[\frac p{\binom{a+b}a}\ge\Delta^{-b}(1+O(\Lambda^2))^{k(a+b)}a^kB(a,b+1)^kI_{(\sqrt{2/\pi})\Lambda}(a,b+1)^k\] حَيْثُ \(I\) هِيَ مَرَّةً أُخْرَى الدالَّةِ البِيتا غَيْرِ المُكْتَمَلَة المعياريه. وَبِالمِثْل لَدَينا \[\frac p{\binom{a+b}a}\le\Delta^{-b}(1+O(\Lambda^2))^{k(a+b)}a^kB(a,b+1)^k+(1-\erf(\Lambda/\sqrt2))^a.\] أَخَذَ، عَلَى سَبِيلِ المِثالِ، \(\Lambda=a^{-2/3}\) يُعْطِي \((1+O(\Lambda^2))^{k(a+b)}=1+O(a^{-1/3})\), \((1-\erf(\Lambda/\sqrt2)^a=O(\exp(-a^{1/3}))\) آلخ. ثُمَّ يَتْبَع النَتِيجَةُ.
نَظَرِيّاتنا لا تُغَطِّي جَمِيعِ حالاتِ تَجْزِئَةِ الإِسْقاط العَشْوائِيِّ وَقَد تَكُون هُناكَ مُتَغَيِّراتِ أُخْرَى مُثِيرَةٍ لِلاِهْتِمامِ يُمْكِن دِراسَتَها مِن خِلالَ النَظَرِ فِي \(a\) وَ\(b\) الكَبِيرَيْنِ مَعَ \(a/b\) يَمِيل إِلَى ثابِتٌ (غَيْرِ صِفْرَيَّ).
لَقَد قَدَّمْنا تَعْمِيماً لِعائِلَةٍ التَجْزِئَةِ/المِفْتاحَ العائِدَةِ لِلمُضَلَّع المُتَقاطِعِ وَالَّتِي تَكُون عَمَلِيَّةِ وَمَرِنه فِي الفَضاءات ذاتِ الأَبْعاد العالِيَةِ. لَقَد أَظْهَرَنا أَنَّ هٰذِهِ العائِلَةِ مِن التَجْزِئات (عَلَى التَوالِي، المَفاتِيح) تُنْتِج تَعَدُّدِ التَصادُمات (عَلَى التَوالِي، تَعَدُّدِ الناجِينَ) عَلَى الأَزْواج القابِلَةِ لِلتَخْفِيض مِن المُتَّجِهات فَوْقَ مُعَدَّلِ التَصادُمُ المُتَعَدِّدِ الساذِج تَجْرِيبِيّا وتقاربيا مَعَ تَوْفِيرِ أَدَواتِ لِدِراسَةِ مُعَدَّلاتِ التَصادُمُ المُتَعَدِّدَةِ فِي حالاتِ خاصَّةٍ. يَنْبَغِي أَنَّ يُوَفِّر هٰذا الوَسائِلِ لِتَحْدِيدِ الأَزْواج القابِلَةِ لِلتَخْفِيض بِطَرِيقَةٍ غَيْرِ تَزايُدَيْهِ. يُظْهِر تَعْمِيمنا سُلُوكاً مُمَيَّزاً تَحْتَ نِظامَيْنِ تقاربيين مُخْتَلِفِينَ، حَيْثُ يُمْكِن مُقارَنَةً أَحَدُ الأَنْظِمَةِ بِالتَجْزِئات/المَفاتِيح الحالِيَّةِ فِي حالَةِ \(k=2\) (حَيْثُ يُوجَد تَبَعِيَّة لوغاريتميه تُقارِبِيهِ تَعْتَمِد عَلَى مُرَبَّعٍ أَقْصَرُ قَطَرِ مُزْدَوِج مُتَعامِد لِمَجْمُوعَةِ تَصادُمُ) وَالآخَرِ جَدِيدٍ (حَيْثُ يُوجَد تَبَعِيَّة تُقارِبِيهِ عَلَى جَيْب التَمام القُطْبِيّ لِمَجْمُوعَةِ تَصادُمُ).
يَتَطَلَّب الرَبْطِ بَيِّنَ القابِلِيَّةِ لِلتَخْفِيض وَمُرَبَّع أَقْصَرُ قَطَرِ مُزْدَوِج مُتَعامِد وَبَيِّنَ القابِلِيَّةِ لِلتَخْفِيض وَجَيْب التَمام القُطْبِيّ اِسْتِكْشافاً أَكْثَرَ لِتَطْوِيرِ تَقْدِيراتِ هٰذِهِ الوَرَقَةَ إِلَى تَعْقِيداتٌ لَنَهْج غَرْبَلَةِ الشَبَكَةِ، وَهٰذا هُوَ مِحْوَرِ العَمَلِ المُسْتَمِرِّ.
هُناكَ أَنْظِمَةِ تُقارِبِيهِ أُخْرَى، قَد تُظْهِر سُلُوكاً مُتَقارِبا آخَرِ لَمُعَدَّلات التَصادُمُ/النَجاة وَقَد تَسْتَحِقّ أَيْضاً دِراسَةٌ أَكْثَرَ.
نَشْكُر الكِتابِ داريل بِيرنْز، روبرتا فو وَصُوفِيّ ستيفنز عَلَى العَدِيدَ مِن المُناقَشاتِ المُفِيدَةَ.