نُقدِّم ونُحلِّل عائلةً من دوالّ التجزئة والتصفية التي تُرجِّح حدوث تصادُمات لتكوينات صغيرة قابلة للاختزال من المتجهات. قد تُوفِّر هذه الدوال تحسيناتٍ عمليّةً لعمليات غربلة الشَبكات بحثاً عن متجهات قصيرة. وعلى وجه الخصوص، تُظهِر هذه العائلة، ضمن نظام تقارُبيّ بعينه، سلوكاً تقارُبياً يختلف على نحوٍ ملحوظ عن دوالّ التجزئة/التصفية المتداولة حالياً.
تعتمد خوارزميات ما بعد الكم مثل Kyber وDilithium وFALCON وFrodo وNTRU وغيرها على صعوبة إيجاد متجه قصير في شَبكة؛ لذا فإن فهم صعوبة هذه المسألة في الأبعاد الكبيرة مهمٌّ جدّاً لاختيار معاملات هذه الخوارزميات. ووفقاً للفهم الحالي، يُعتقَد أن الطريقة الأكثر فاعلية لإيجاد متجهات قصيرة في شَبكة ذات بُعد كبير \(d\) هي «الغربلة». طُرِح مفهوم غربلة متجهات الشَبكة القصيرة لأول مرة بواسطة أجتاي–كومار–سيفاكومار (AKS). في خوارزميات الغربلة هذه، تُنتَج أعداد كبيرة من المتجهات (بحجم أُسِّي في \(d\)) بطول متقارب، عن طريق أخذ تراكيب خطيّة صغيرة من متجهات الأساس. ثم تُقارَن أزواج المتجهات للتحقق ممّا إذا كان جمع أحدهما أو طرحه من الآخر يُنتج متجهاً أقصر. بعد ذلك يُستبدَل المتجه الأطول بمتجه أقصر داخل المجموعة، وتُكرَّر العملية حتى لا يعود بالإمكان العثور على متجه أقصر. وتُستخدم استدلالات هندسية لتبرير حجم العيّنة اللازم كي نضمن الاستمرار في إيجاد متجهات أقصر.
كانت الفكرة الأولى في (AKS) تعتمد على مقارنة كل الأزواج الممكنة من المتجهات، لكن التحسينات اللاحقة خفّضت زمن التشغيل عبر النظر فقط في الأزواج «القريبة»، إذ هي الأرجح في إنتاج متجهات أقصر. ما زال حساب المسافة بين كل زوج يستغرق زمناً تربيعياً في عدد المتجهات، لكن تجزئة كل متجه بدالّة تحتفظ بجزء من معلومات موقعه تتيح الفرز بحسب قيمة التجزئة لإيجاد أزواج قريبة. تُعرَف هذه الدوال بـ«التجزئة الحسّاسة للمسافة» (LSH)؛ انظر (polytope) مثالاً. نهجٌ مُشابِه (filter) هو عائلة دوالّ تصفية تُنتج مخرجاً ثنائياً لكل متجه، بحيث تعبر المتجهات القريبة سلسلةً من المعايير بنجاح.
تَمتدّ خوارزميات الغربلة لتشمل ليس فقط الأزواج، بل أيضاً الثلاثيات أو، بوجهٍ عام، مجموعات من الحجم \(k\) تُنتِج تركيبةً خطيّة أقصر (tuple). وإيجاد مثل هذه التركيبات أكثر تعقيداً من حالة الأزواج (التي تُناظِر خطوة خفض إقليدس)، غير أنّ هناك خوارزمياتٍ سريعةً مُخصَّصة لإيجاد أقصر تركيبة خطية من ثلاثة (semaev) أو أربعة (nguyen) متجهات. ونظراً لأنّ تعقيد الغربلة يتأثّر ضعيفاً جداً بخطوة الخفض، يمكن فحص مجموعات أكبر بحثاً عن تراكيب أقصر (مثل تعداد Schnorr–Euchner (schnorr) أو حتى غربلة على أبعادٍ أقلّ). وطالما وُجِدَت تركيبة أقصر بنسبةٍ موجبة، تَستمر الغربلة. تصير التكوينات القابلة للاختزال من مجموعات \(k\) أكثر شيوعاً كلما ازداد \(k\)، ما يُقلِّل عدد المتجهات الأولية المطلوبة ويُخفِّض تكلفة الذاكرة. في هذه الورقة ننظر في مسألة إيجاد التكوينات القابلة للاختزال لمجموعات \(k\)، مع التركيز على الحالة \(k=3\).
لتسريع الغربلة الحاسوبية لمجموعات \(k\)، نحتاج إلى دالّة تصفية تحدّد التكوينات القابلة للاختزال بكلفةٍ أقلّ من فحص كل مجموعة على حدة. يتطلّب ذلك توصيف عائلةٍ واسعة من الثلاثيات/المجموعات القابلة للاختزال، إضافةً إلى اختبارٍ رخيصٍ لكن قويّ لانتقاء هذه المجموعات ضمن عيّنة ضخمة. المناهج الحالية (klist, fast_tuple) تبني مجموعة \(k\) تدريجياً: من متجه إلى زوج إلى ثلاثي ... حتى مجموعة من الحجم \((k-1)\)، حيث يُختار كل متجه جديد إمّا من تصادمات تجزئة ثنائية أو عبر اجتياز تصفيةٍ ثنائية.
في هذه الورقة نستكشف نهجاً مباشراً يُحدِّد مجموعات \(k\) القابلة للاختزال عبر تصادمات \(k\)-طُرُق في دوالّ التجزئة، أو عبر عائلاتٍ من \(k\) ناجياتٍ من التصفية. نقترح تعميماً لـ«تجزئة الزاوية» (angular, polytope) يمكن استخدامه كاختبارٍ إحصائيّ لتعيين التكوينات القابلة للاختزال. يرتبط هذا التعريف بمشكلة إيجاد مجموعات من المتجهات تقع جميعُها قريباً من فضاءٍ جزئيّ ذي بُعد \((k-1)\). في هذه الحالة قد تصلح طرائقُنا أيضاً للتصنيف والتجميع في بياناتٍ عالية الأبعاد بوجهٍ عام. ويُقدّم تعميمُنا تجزئاتٍ حسّاسةً للمسافة لحالة \(k=2\)، تُظهِر سلوكاً تقارُبياً مختلفاً عن التجزئات الحالية وقد يكون مفيداً لتطبيقات الغربلة. تشير تحليلاتُنا كذلك إلى إمكان تكييف التصفية لعائلات ناجياتٍ من الحجم \(k\)، وإلى عائلةٍ جديدة من دوالّ التصفية تستحقّ مزيداً من البحث.
تُعرَّف دالّة التجزئة الخاصة بمُتعدّد السطوح المتصالِب (cross‑polytope LSH) كما في (polytope) باختيار \(d\) متجهات غاوسية مستقلّة \(\vv r_i\). لكل متجه \(\vv v\) نَحسب \(\pm\,\vv r_i\!\cdot\!\vv v\)، ثم نختار الفهرس غير الموقّع \(\pm i\) الذي يُحقِّق أكبر قيمةٍ مطلقة للجداء الداخلي. وقيمة التجزئة هي \[ H(\vv v)=(-1)^b\, i:\; b\in\{0,1\},\; (-1)^b\,\vv r_i\!\cdot\!\vv v\;\ge\;|\vv r_j\!\cdot\!\vv v|\quad \forall\,1\le j\le d. \] وبسبب الارتفاع في البُعد، يكون المتجه \(\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\)، ونَتوقّع أن تُحافِظ إسقاطاتُ الأزواج على القُرب (أو على «التعاكس»). هذا يُخفِّض كلفة التقييم، مع احتمال زيادة التصادمات لكلٍّ من الإيجابيات الحقيقية والخاطئة.
ثالثاً، يمكن اختيار أكثر من فهرسٍ واحد. فبجمع مجموعةٍ من \(a\) فهارس بأعلى إسقاطات نُحدِّد فضاءً جزئيّاً بُعدُه \(a\) يُحاكي توجّه المتجه. وبدلاً من ذلك، إذا كتبنا \(h=a+b\) أمكننا جمع \(b\) فهارس بأصغر إسقاطات لتحديد المُتمِّم المُتعامِد.
لهذه الأسباب، نُعرِّف عائلة «تجزئات الإسقاط العشوائي» كما يلي:
لتكن \(\mathcal R=\{\vv r_1,\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\)، التي تُعطي أعلى قيمٍ مطلقة للجداءات \(\vv r_i\!\cdot\!\vv v\): \[ H_{\mathcal R,a,b}(\vv v) =\Bigl\{A:\#A=a,\;|\vv r_i\!\cdot\!\vv v|\ge|\vv r_j\!\cdot\!\vv v|\;\forall\,i\in A,\;j\notin A\Bigr\}. \] ويُفضّ التعادل باختيار الفهرس الأصغر عند تساوي القيم.
نهتمّ بمُعدّل التصادم \(k\)-الطُرُقي لعائلة التجزئة هذه على أنماطٍ من \(k\) متجهات. عند عدم ترابُط القيم، نتوقّع مُعدّلاً بدائيّاً \(\binom{h}{a}^{-(k-1)}\). سنُبيّن لاحقاً ارتباط مُعدّل التصادم بالجداءات الداخلية الزوجيّة للأنماط. ونُجري في قسمٍ لاحق تحقيقاتٍ تجريبية للمُعدّل الثلاثي لتكويناتٍ قابلةٍ للاختزال وأخرى غير قابلة. كما نُقدّم تعابير تحليلية للحالات \(a=1\) أو \(b=1\) عبر تكاملٍ عدديّ في فضاءٍ ذي \(k+1\) أبعاد. وفي دراسة السلوك التقارُبي لمعدل التصادم حين \(b\to\infty\) مع ثبات \(a\)، نُثبِت تعميماً لنتائج (angular) حيث كان \(h=d\)، \(a=1\)، \(b=d-1\). في (angular) يُظهَر أن المعدّل السالب اللوغاريتمي للتصادم الثنائي التقارُبي هو \((\alpha-1)\log h\) مع \(\alpha(\tau)=\tfrac{4}{\,4-\tau^2\,}\) إذا كانت \(\tau\) مسافة المتجهين، ويمكن كتابتها أيضاً \(\alpha(\vv v_1\!\cdot\!\vv v_2)=\tfrac{2}{\,1-|\vv v_1\!\cdot\!\vv v_2|\,}\). في الحالة العامة نصل إلى \[ \log\frac{B\bigl((1+o(1))\,\alpha\,a,\;b\bigr)}{B(a,b)}, \] حيث \(B\) دالّة بيتا و\(\alpha\) دالّة في الجداءات الداخلية الزوجيّة للأنماط، ونُسمّي \(\alpha\) «القطرَ المُزْدَوِج الأقصر المُربَّع». كما ندرس سلوك التصادمات عند \(a\to\infty\) مع ثبات \(b\)، فنحصل على \[ \Delta^{-b}\,\binom{a+b}{b}^{-(k-1)}, \] حيث \(\Delta\) هو «الجيب القطبي» للأنماط. ونُقدِّم أيضاً مُعدّلات بقاء الأنماط تحت اختبار «تصفية الإسقاط العشوائي» فوق أو تحت حدود مطلقة كبيرة، ما يُمكِّن من تصميم مخططات تصفية مُلائمة للغربلة.
في هذا القسم نسعى لتوصيف عائلات من مجموعات المتجهات متساوية الطول حيث تُوفِّر بعض تراكيبها الخطيّة متجهاتٍ أقصر من الأصلية.
نَتصوّر ابتداءً تكويناً من \(k\) متجهاتٍ نموذجية على كرة ذات بُعد \((d-1)\). إذا كان \(k\) صغيراً مقارنةً بـ\(d\)، كانت الأزواج شبه متعامدة، فينشأ مكعّبٌ فائق تقريباً بأضلاعٍ طولُها يساوي قطر الكرة وموازيةٍ لمتجهات التكوين. نرغب في «ضغط» هذا المكعّب الفائق على طول قطرٍ رئيسي بحيث يقلّ طولُ ذلك القطر عن طول الأضلاع، الأمر الذي يضمن وجود تركيب خطيّ أقصر. إذا كانت رؤوس القطر الرئيسي هي \(\vv u_1,\ldots,\vv u_k\) (والرؤوس المقابلة هي نُظائرها السالبة)، فإن المتجه \[ \vv d=\vv u_1+\vv u_2+\cdots+\vv u_k \] يمثّل هذا القطر. وبمطابقة قانون التوزيع نجد \[ \|\vv d\|^2=\ell^2\Bigl(k+\sum_{i\neq j}\cos(\vv u_i,\vv u_j)\Bigr), \] حيث \(\ell\) طول ضلع متوازي السطوح و\(\cos(\vv u_i,\vv u_j)\) جيب تمام زاوية المتجهين. ولجعل \(\|\vv d\|^2<\ell^2\) يجب أن يكون \(\sum_{i\neq j}\cos(\vv u_i,\vv u_j)<-k+1\). يتحقّق أقلّ طولٍ للقطر عندما تتساوى كل الزوايا بحيث \(\cos(\vv u_i,\vv u_j)=-1/k\)؛ ومن ثمّ تتجمّع المتجهات حول تكوينٍ متناظر تكون فيه الزاوية بين كل زوج \(\arccos(-1/k)\). هذا هو التكوين الذي نركّز عليه وتهدف اختباراتُنا إلى التقاطه.
في الحالة \(k=3\) نهتمّ بالثلاثيات التي تُشكِّل متوازياتِ سطوحٍ مُسطَّحة، أي تكويناتٍ تقارب «متوازي أضلاع»، وهو ما يرتبط ارتباطاً وثيقاً بالتبعية الخطية الجزئية أو التسطّح. تُستهدَف هذه التكوينات بدوالّنا؛ إذ من المرجّح أن تُشارِك المتجهاتُ العشوائية التي تُحقِّق إسقاطاتٍ داخليةً كبيرةً على الفضاء الجزئي ثنائي الأبعاد الذي تولِّده الثلاثية، بينما تتّجه المتجهات الأخرى نحو المُتمِّم المُتعامِد، فيزداد احتمال التصادم \(k\)-الطُرُقي.
إذا اقتصرنا على التراكيب الخطيّة لمتجهاتنا \(k\) بمعاملات \(\pm1\)، فإن قابليّة اختزال تكوينٍ من متجهاتٍ وحدويّة تعتمد على مجموع الجداءات الزوجيّة: يكون التكوين قابلاً للاختزال إذا كان \(\sum_{i\neq j}\vv u_i\!\cdot\!\vv u_j<-k+1\). من المثالي أن يعتمد مُعدّل التصادم فقط على هذا المجموع، لكن تماثُل التجزئة تحت الدوران يجعلنا نتوقّع اعتمادَه على مجموعة الجداءات الداخلية الزوجيّة كاملةً، وهو ما سنراه تجريبياً.
لبُعدٍ مُعيّن \(d\)، يمكن توليد تكوينٍ عشوائي من الحجم \(k\) بجداءاتٍ داخليّةٍ زوجيّة مُحدَّدة عبر إنشاء ثلاثيٍّ عشوائي ثم تطبيق خوارزمية غرام–شميدت لإعادة التحجيم. يمكن تقدير مُعدّل التصادم الثلاثي التجريبي لعائلة التجزئة الإسقاطية العشوائية \(H_{\mathcal R,a,b}\). نظرياً نتوقّع مُعدّل تصادم تقريبي \(p\approx\binom{a+b}{b}^{-(k-1)}\)؛ ولعينةٍ حجمُها \(N\) نتوقّع توزيعاً ثنائي الحدّين \(\mathcal B(N,p)\). ولتقدير المتوسّط بدقة 1% عند ثقة 95% نحتاج تقريباً \(N\approx10^5 p^{-2}\)، ما يحدّ عمليّاً من دراسة الحالات التي يكون فيها \(p\) صغيراً للغاية. ومع ذلك، لعددٍ مُحدود من قيم \(k\) و\(h\) نستطيع تأكيد أن الاحتمالات تعتمد أساساً على الجداءات الداخلية الزوجية، وأن النتائج مُستقرّة عددياً. اخترنا بُعداً كبيراً كفايةً لعكس المبدأ دون إثقال الحوسبة.
نركِّز على \(k=3\) ونُمثِّل الجداء الداخلي بين أزواج الثلاثية بـ \(\alpha,\beta,\gamma\) بحيث \(\sigma=2(\alpha+\beta+\gamma)\). نعمل عند \(d=20\) (ولم تتغيّر الخلاصات بتغيير البُعد)، ونستخدم 100,000 تجربة للحصول على دقّة في حدود رقمين إلى ثلاثة. نعرض عائلة التجزئة \(H_{\mathcal R,1,2}\)، مع التركيز على الحالات ذات \(\alpha,\beta,\gamma<0\) (حيث يكون خفض الأزواج الثنائي أفضل من الثلاثي).
نُلاحِظ تماثُل مجموعة النقاط تحت زمرة \(S_3\) في البيانات، ويتحقّق توقّعُنا بارتفاع مُعدّل التصادم كلّما تناقصت \(\sigma\). القيَم الوسطى للتكوينات الثلاث هي تقريباً 0.125, 0.134, 0.144، أي أعلى بنحو 12.5% و20.5% و28.9% من المُعدّل الساذج \(1/9\). أمّا نِسَب اللوغاريتم لاحتمالات التصادم بين القيَم \(\sigma=-2.0\) و\(-2.4\) مثلاً فهي نحو \(1.034\)، وسواها كما يلي: \[ \rho(-2.0,-2.4)\approx1.034,\quad \rho(-2.0,-3.0)\approx1.035,\quad \rho(-2.4,-3.0)\approx1.070. \]
برفع عدد المتجهات العشوائية إلى 4 (أي استخدام \(H_{\mathcal R,1,3}\))، يُتوقَّع أن ينخفض المُعدّل الساذج من \(1/9\) إلى \(1/16\).
نرى سلوكاً مُشابهاً في هذه الحالة. القيَم الوسطى الآن تقريباً 0.0705, 0.0765, 0.0763 (تفوقٌ على السذاجة بنسبة 12.8% و22.4% و22% على التوالي). ونجد نِسَب اللوغاريتم: \[ \rho(-2.0,-2.4)\approx1.032,\quad \rho(-2.0,-3.0)\approx1.031,\quad \rho(-2.4,-3.0)\approx0.999. \]
يشير هذا إلى أنّ إبقاء \(h\) صغيراً لا يُقلِّل الكلفة فحسب، بل قد يُعزِّز التمييز، على الرغم من بعض الضوضاء العددية.
نختبر أيضاً تصادمات تجزئة «أصغر قيمةٍ مُطلقة» للفهارس (أي اختيار الفهارس ذات أصغر إسقاطاتٍ مُطلقة). لم يتغيّر نمط البيانات، لكن القيَم الوسطى أصبحت تقريباً 0.126, 0.141, 0.183، أي أعلى بـ 13.4% و12.7% و64.5% من المُعدّل الساذج، مع نِسَب لوغاريتم: \[ \rho(-2.0,-2.4)\approx1.058,\quad \rho(-2.0,-3.0)\approx1.219,\quad \rho(-2.4,-3.0)\approx1.152. \]
يبدو أنّ «تجزئة القيمة الدنيا» أكثر قوّة من اختيار القيم الكُبرى، ما يستحقّ تحقيقاً أعمق.
وعند استخدام 4 متجهات عشوائية في تجزئة القيمة الدنيا (أي \(H_{\mathcal R,3,1}\))، نجد القيَم الوسطى \(\approx 0.0727, 0.0848, 0.127\) (تفوقٌ على السذاجة بنسبة 16.3% و35.7% و103%) ونِسَب لوغاريتم: \[ \rho(-2.0,-2.4)\approx1.063,\quad \rho(-2.0,-3.0)\approx1.270,\quad \rho(-2.4,-3.0)\approx1.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 v_n\).
وبسبب التماثُل وتجاهُل الأحداث ذات الاحتمال الصفري، \[ \mathbb P\bigl(H(\vv v_1)=H(\vv v_2)=H(\vv v_3)\bigr) =h\,\mathbb P\bigl(H(\vv v_1)=H(\vv v_2)=H(\vv v_3)=1\bigr). \] نُعرِّف \(G(\vv w;\vv v_1,\vv v_2,\vv v_3)\) على أنّه احتمال أن يحقّق متجهٌ غاوسيّ عشوائي \(\vv r\) الشرط \(|\vv v_n\!\cdot\!\vv w|\le|\vv v_n\!\cdot\!\vv r|\) لكل \(1\le n\le3\). وبالاستقلالية، \[ \mathbb P\bigl(H(\vv v_1)=H(\vv v_2)=H(\vv v_3)=1\bigr) =\int_{\vv w}G(\vv w;\vv v_1,\vv v_2,\vv v_3)^{\,h-1}\,d\mu(\vv w), \] حيث \(d\mu\) هو القياس الغاوسي القياسي.
في الواقع، تعتمد \(G\) فقط على الجداءات الداخلية الزوجيّة لمتجهات الإدخال \(\vv v_n\). إذا كتبنا \(\lambda_n=\vv w\!\cdot\!\vv v_n\)، وكانت \(\mu_m\) ترمُز إلى الجداءات الداخلية بين أزواج \(\vv v_i\)، أمكننا ربط \(G\) بأحجام زوايا صلبة في متوازي سطوح تُحدِّده المعادلات \(\vv r\!\cdot\!\vv v_n=\pm\lambda_n\).
يمكن التعبير عن «كتلة» القياس الغاوسي ضمن الزوايا الصلبة المقابلة لرؤوس متوازي السطوح (المُعطاة بإحداثيات \(\vv w^{(c)}\)) على هيئة تكاملاتٍ على أَرْبعياتٍ من أنصاف الفضاءات. عمليّاً، نُحوِّل المسألة إلى جهاز إحداثياتٍ يكون فيه \(\{\vv v_1,\vv v_2,\vv v_3\}\) مُعيَّرةً، ثم نكتب \(\vv r\) توزيعاً غاوسيّاً معيارياً على \(\mathbb R^3\) مع مصفوفة تباينٍ هي المصفوفة الغرامية للثلاثية. عندئذٍ يصير \(G\) تكاملاً للاحتمال فوق مُتعددة مناطق مُعرَّفة بقيودٍ من الشكل \(|\lambda_n|\le|\vv v_n\!\cdot\!\vv r|\). هذا يُختزل عددياً إلى تكاملٍ على أَثمان الفضاء بحدودٍ تعتمد فقط على الجداءات الداخلية الزوجيّة، ويمكن تقديره بدقّةٍ عالية بمُربّعات غاوسيّة أو بالعينات المُهمّة. هذا الإطار يعمّم مباشرةً إلى \(k>3\) مع زيادةٍ بُعديّة محدودة.