🔢 mathematics

Uncertainty Principles for the Number Theoretic Transform

पॉलीनोमियल आइडेंटिटी टेस्टिंग से प्रेरित होकर, यह शोधपत्र नंबर-थ्योरेटिक ट्रांसफॉर्म (NTT) के लिए सुदृढ़ स्पैरसिटी ट्रेडऑफ़्स स्थापित करता है और अभाज्य संख्याओं (primes) पर औसत निकाला गया एक संभाव्य अनिश्चितता सिद्धांत सिद्ध करता है, जो शून्य साउंडनेस एरर वाले विरल एक्सपोनेंशियल पॉलीनोमियल्स के लिए एक ब्लैक-बॉक्स आइडेंटिटी टेस्ट की ओर ले जाता है।

मूल लेखक: Giulio Malavolta, Alon Rosen

प्रकाशित 2026-06-09

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Giulio Malavolta, Alon Rosen

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आपके पास एक बहुत ही विशिष्ट कोड में लिखी गई एक गुप्त रेसिपी है। इस कोड में नियमित सामग्री (पॉलीनोमियल्स/बहुपद) को एक विशेष, जादुई सामग्री के साथ मिलाया जाता है: एक एक्सपोनेंशियल (जैसे $e^x$ )। कंप्यूटर विज्ञान की दुनिया में, यह जांचना कि क्या दो ऐसी रेसिपी वास्तव में एक ही हैं (या क्या उनमें से एक वास्तव में "शून्य" या खाली है) एक बहुत बड़ी चुनौती है।

यह शोध पत्र, जो जूलियो मालावोल्टा और एलन रोसेन द्वारा लिखा गया है, एक विशिष्ट समस्या पर काम करता है: हम कैसे सुनिश्चित कर सकते हैं कि एक्सपोनेंशियल (घातांक) वाली एक जटिल गणितीय अभिव्यक्ति वास्तव में शून्य नहीं है?

यहाँ उनके कार्य का सरल उपमाओं (analogies) का उपयोग करके विवरण दिया गया है:

1. समस्या: "घोस्ट" (भूतिया) रेसिपी

कल्पना कीजिए कि आपके पास एक मशीन है जो एक संख्या लेती है, कुछ गणित करती है, और परिणाम देती है। कभी-कभी, मशीन को कोई भी इनपुट मिलने पर "शून्य" आउटपुट देना होता है। लेकिन कभी-कभी, यह एक "ट्रिक मशीन" होती है जो केवल कुछ विशिष्ट संख्याओं के लिए गलती से शून्य आउटपुट देती है, लेकिन अन्य संख्याओं के लिए वास्तविक संख्या उत्पन्न करती है।

मानक गणित (पॉलीनोमियल्स) में, हमारे पास इन ट्रिक मशीनों को पकड़ने के लिए एक विश्वसनीय तरीका है: बस मशीन को एक यादृच्छिक (random) संख्या के लिए गणना करने के लिए कहें। यदि यह एक "जीरो" मशीन नहीं है, तो यह लगभग निश्चित रूप से एक गैर-शून्य उत्तर देगी। यह एक प्रसिद्ध नियम है जिसे श्वार्ट्ज-ज़िपेल लेम्मा (Schwartz-Zippel Lemma) कहा जाता है।

हालाँकि, जब हम इसमें एक्सपोनेंशियल (जादुई सामग्री) मिला देते हैं, तो यह पुराना तरीका काम करना बंद कर देता है। नियम बदल जाते हैं, और हमारे पास यह कहने का कोई विश्वसनीय तरीका नहीं होता कि, "यह मशीन निश्चित रूप से शून्य मशीन नहीं है।"

2. उपकरण: "नंबर-थ्योरेटिक ट्रांसफॉर्म" (NTT)

इस समस्या को हल करने के लिए, लेखक एक गणितीय उपकरण की ओर देखते हैं जिसे नंबर-थ्योरेटिक ट्रांसफॉर्म (NTT) कहा जाता है। सोचिए कि NTT एक विशेष अनुवादक (translator) या दर्पण (mirror) है।

इनपुट: आप उसे संख्याओं की एक सूची देते हैं (एक स्पार्स सूची, जिसका अर्थ है कि अधिकांश शून्य हैं, जैसे कि केवल कुछ सामग्रियों वाली रेसिपी)।
आउटपुट: अनुवादक आपको संख्याओं की एक नई सूची (ट्रांसफॉर्म) देता है।

लेखक एक नियम में रुचि रखते हैं जिसे अनिश्चितता का सिद्धांत (Uncertainty Principle) कहा जाता है। वास्तविक दुनिया में, अनिश्चितता का सिद्धांत कहता है कि आप एक ही समय में यह सटीक रूप से नहीं जान सकते कि एक कण कहाँ है और उसकी गति कितनी है। गणित में, इसका अर्थ है कि आपके पास एक ऐसी सूची नहीं हो सकती जो मूल रूप में भी "छोटी" (sparse) हो और अनुवादित रूप में भी "छोटी" हो।

शोध पत्र की बड़ी खोज:
उन्होंने सिद्ध किया कि इस विशिष्ट अनुवादक (NTT) के लिए, यदि आपकी मूल सूची छोटी है, तो अनुवादित सूची निश्चित रूप से लंबी होगी। आप एक साथ दोनों जगहों पर जानकारी को छिपा नहीं सकते।

उपमा: यदि आप केवल 3 अक्षरों का उपयोग करके एक गुप्त संदेश लिखते हैं, और फिर उसे एक अलग भाषा में अनुवादित करते हैं, तो अनुवाद में कम से कम एक निश्चित संख्या में अक्षरों का उपयोग करना होगा। वह दोनों भाषाओं में छोटा नहीं रह सकता।

3. पेच: "प्राइम नंबर" (अभाज्य संख्या) की समस्या

लेखकों ने अपनी पहली खोज में एक समस्या पाई। नियम पूरी तरह से काम करता है, लेकिन केवल तभी जब "भाषा" (गणितीय क्षेत्र) बहुत विशाल हो—विशेष रूप से, यदि उपयोग किया जाने वाला अभाज्य संख्या (prime number) खगोलीय रूप से बड़ी हो (जैसे $q^{q^2}$ )।

वास्तविक दुनिया में (जैसे कंप्यूटर प्रोग्रामों में), हम इतनी बड़ी संख्याओं का उपयोग नहीं कर सकते; हमें ऐसी संख्याओं की आवश्यकता होती है जो इनपुट (पॉलीनोमियल आकार) से केवल कुछ गुना बड़ी हों। इन "छोटी" दुनिया में, सख्त नियम टूट जाता है। कभी-कभी, एक छोटी संदेश गलती से एक छोटी संदेश में अनुवादित हो सकती है।

4. समाधान: "पासे का खेल" (Roll of the Dice)

चूंकि वे यह गारंटी नहीं दे सकते कि नियम हर एक छोटे नंबर के लिए काम करेगा, इसलिए उन्होंने अपनी रणनीति बदल दी। एक विशिष्ट नंबर चुनने और उम्मीद करने के बजाय, उन्होंने पासे फेंकने (dice roll) का निर्णय लिया।

उन्होंने एक नई परीक्षण पद्धति प्रस्तावित की:

एक सुरक्षित रेंज से एक यादृच्छिक "प्राइम नंबर" (गणितीय दुनिया का आकार) चुनें।
परीक्षण चलाएं।

उन्होंने सिद्ध किया कि हालांकि यह नियम कुछ विशिष्ट प्राइम नंबरों के लिए विफल हो सकता है, लेकिन यदि आप प्राइम नंबर को यादृच्छिक रूप से चुनते हैं, तो यह लगभग हमेशा काम करता है।

उपमा: कल्पना कीजिए कि भूसे के ढेर में सुई खोजने की कोशिश की जा रही है। यदि आप एक ही विशिष्ट स्थान पर देखते हैं, तो आप इसे मिस कर सकते हैं। लेकिन यदि आप पूरे भूसे के ढेर में से यादृच्छिक स्थान चुनते हैं, तो आप लगभग निश्चित रूप से इसे ढूंढ लेंगे। लेखकों ने सिद्ध किया कि यदि आप अपनी "गणितीय दुनिया को यादृच्छिक रूप से चुनते हैं," तो "शॉर्ट-टू-शॉर्ट" वाला trick लगभग कभी नहीं होता।

5. परिणाम: एक बेहतर "जीरो" डिटेक्टर

इस "रैंडम प्राइम" रणनीति को अपने अनिश्चितता नियम के साथ जोड़कर, उन्होंने एक नया आइडेंटिटी टेस्ट (Identity Test) बनाया।

पुराना तरीका: इसके मूर्ख बनने की उच्च संभावना थी (यह एक गैर-शून्य रेसिपी को शून्य कह सकता था)।
नया तरीका: प्राइम नंबर को यादृच्छिक बनाकर, उन्होंने मूर्ख बनने की संभावना को एक बहुत ही सूक्ष्म, स्थिर संख्या तक कम कर दिया।

यह क्यों मायने रखता है?
शोध पत्र में उल्लेख किया गया है कि यह कंप्यूटर प्रोग्रामों को अनुकूलित करने (विशेष रूप से "टेंसर प्रोग्राम" और मशीन लर्निंग से जुड़े प्रोग्रामों) के लिए उपयोगी है। ये प्रोग्राम अक्सर एक्सपोनेंशियल फंक्शन (जैसे AI में "सॉफ्टमैक्स") का उपयोग करते हैं। यदि एक कंपाइलर को यह जानना है कि क्या प्रोग्राम के दो हिस्से एक ही चीज़ करते हैं, तो उसे यह जांचने की आवश्यकता होती है कि क्या उनका अंतर शून्य है। यह नया परीक्षण उन्हें जटिल गणित से बिना डरे यह जांच करने का एक बहुत अधिक विश्वसनीय तरीका देता है।

सारांश

लेखकों ने एक नया गणितीय नियम सिद्ध किया है: आप एक ही समय में दो अलग-अलग भाषाओं में छोटे नहीं हो सकते। हालांकि यह नियम विशाल दुनिया में सख्त है, उन्होंने दिखाया कि दुनिया के आकार को यादृच्छिक रूप से चुनकर, आप इसे व्यावहारिक, छोटी दुनिया के लिए लगभग पूरी तरह से काम करने योग्य बना सकते हैं। यह कंप्यूटरों को जटिल गणितीय सूत्रों को बहुत अधिक विश्वसनीयता के साथ जांचने की अनुमति देता है।

तकनीकी सारांश: नंबर थ्योरेटिक ट्रांसफॉर्म के लिए अनिश्चितता सिद्धांत (Uncertainty Principles)

1. समस्या विवरण और प्रेरणा

यह शोध पत्र एक्सपोनेंशियल (exponentials) से जुड़े व्यंजकों के लिए पॉलीनोमियल आइडेंटिटी टेस्टिंग (PIT) की समस्या को संबोधित करता है, जो कि ली और वू [LW26] द्वारा हाल ही में औपचारिक रूप दिया गया एक क्षेत्र है। इस सेटिंग में, यह निर्धारित करना होता है कि क्या $P(x) = \sum_{j=1}^k f_j(x) \exp(g_j(x)/h_j(x))$ के रूप में दिया गया व्यंजक सर्वथा शून्य (identically zero) है।

फिनिट फील्ड्स (finite fields) पर ऐसे व्यंजकों के परीक्षण में मुख्य चुनौती एक सुदृढ़ मूल्यांकन मॉडल (evaluation model) को परिभाषित करने में निहित है। ली और वू ने दो अभाज्य संख्याओं (primes), $p$ और $q$ (जहाँ $p \equiv 1 \pmod q$ ) का उपयोग करते हुए एक मॉडल प्रस्तावित किया, जो $\mathbb{F}_p^*$ में क्रम $q$ के अद्वितीय उपसमूह (subgroup) के माध्यम से एक्सपोनेंशियल की व्याख्या करता है। हालाँकि, साउंडनेस एरर (soundness error - गैर-शून्य पॉलीनोमियल को स्वीकार करने की प्रायिकता) के उनके विश्लेषण ने $q^{-1/(k-1)} + O(dk^2/q)$ का एक बाउंड दिया। उस व्यावहारिक परिदृश्य में जहाँ $q = k^{O(1)}$ है, यह त्रुटि 1 के करीब पहुँच जाती है, जिससे परीक्षण अप्रभावी हो जाता है।

ली और वू ने अनुमान लगाया था कि यह खराब साउंडनेस नंबर-थ्योरेटिक ट्रांसफॉर्म (NTT) के लिए अनिश्चितता सिद्धांतों (uncertainty principles) की कमी से संबंधित है। विशेष रूप से, उन्होंने अनुमान लगाया था कि कम गैर-शून्य गुणांकों वाले एक स्पार्स (sparse) पॉलीनोमियल के पास उपसमूह $G$ में बहुत अधिक जड़ें (roots) नहीं हो सकतीं। इस शोध पत्र के लेखक ऐसे अनिश्चितता सिद्धांतों को सिद्ध करने का लक्ष्य रखते हैं ताकि आइडेंटिटी टेस्टिंग की साउंडनेस में सुधार किया जा सके।

2. कार्यप्रणाली और तकनीकी दृष्टिकोण

लेखक एक वेक्टर $f$ की स्पर्सिटी (sparsity) और उसके NTT, $\hat{f}$ , की स्पर्सिटी के बीच संबंध की जांच करते हैं। वे सपोर्ट साइज $|\text{Supp}(f)|$ को गैर-शून्य निर्देशांकों की संख्या के रूप में परिभाषित करते हैं। लक्ष्य $|\text{Supp}(f)| + |\text{Supp}(\hat{f})|$ पर निचला बाउंड (lower bounds) स्थापित करना है।

2.1 हाइपरइनवर्टिबिलिटी (Hyperinvertibility) के माध्यम से एडिटिव अनिश्चितता

पहला दृष्टिकोण कॉम्प्लेक्स डिस्क्रीट फूरियर ट्रांसफॉर्म (DFT) के लिए ताओ [Tao05] की रणनीति को अपनाता है। कॉम्प्लेक्स सेटिंग में, DFT मैट्रिक्स "हाइपरइनवर्टिबल" (प्रत्येक वर्ग उपमैट्रिक्स (square submatrix) व्युत्क्रमणीय है) होता है, जो एक मजबूत एडिटिव अनिश्चितता सिद्धांत को दर्शाता है: $|\text{Supp}(f)| + |\text{Supp}(\hat{f})| \ge q + 1$ ।

लेखक नोट करते हैं कि यह गुण सामान्यतः फिनिट फील्ड्स के लिए विफल हो जाता है (जैसा कि झांग [Zha19] द्वारा दिखाया गया है)। हालाँकि, वे सिद्ध करते हैं कि एक निश्चित अभाज्य $q$ के लिए, NTT मैट्रिक्स की हाइपरइनवर्टिबिलिटी सभी लेकिन सीमित संख्या में अभाज्य $p \equiv 1 \pmod q$ के लिए सत्य होती है।

प्रूफ तकनीक: वे बहुपदों के रिजल्टेंट (resultant) का उपयोग करते हैं। फूरियर मैट्रिक्स के किसी भी वर्ग उपमैट्रिक्स के लिए, वे एक बहुपद $D_{R,C}(z)$ का निर्माण करते जिसका डिटर्मिनेंट (determinant) प्रिमिटिव $q$ -वें रूट्स ऑफ यूनिटी पर गैर-शून्य होता है (कॉम्प्लेक्स परिणाम द्वारा)। वे दिखाते हैं कि यदि कोई उपमैट्रिक्स मोड्यूलो $p$ सिंगुलर हो जाता है, तो $p$ को साइक्लोटोमिक बहुपद $\Phi_q(z)$ और $D_{R,C}(z)$ के रिजल्टेंट को विभाजित करना चाहिए। चूँकि रिजल्टेंट एक गैर-शून्य पूर्णांक है, इसके केवल सीमित अभाज्य विभाजक होते हैं, जो "बुरे" अभाज्य $p$ को सीमित करते हैं।

2.2 पॉलीनोमियल रिजीम के लिए अनुमानित अनिश्चितता (Approximate Uncertainty)

उपरोक्त एडिटिव अनिश्चितता परिणाम के लिए $p$ का अत्यंत बड़ा होना आवश्यक है (लगभग $p \approx q^{q^2}$ ), जो अनुप्रयोगों के लिए अव्यवहारिक है जहाँ $p = q^{O(1)}$ है। इसे संबोधित करने के लिए, लेखक एक संभाव्यता (अनुमानित) अनिश्चितता सिद्धांत को सिद्ध करते हैं।

रिजीम: वे $p$ को अंतराल $P(q) = \{p \le q^4 : p \text{ अभाज्य है}, p \equiv 1 \pmod q\}$ से समान रूप से सैंपल किए गए $p$ के रूप में देखते हैं।
प्रूफ तकनीक: वे एक स्पार्स इंटीजर पॉलीनोमियल $f$ $f$ को स्थिर करते हैं और इस बात का विश्लेषण करते है कि एक रैंडम अभाज्य $p$ $p$ के लिए $f$ $f$ एक प्रिमिटिव $q$ $q$ -वें रूट ऑफ यूनिटी पर शून्य होने की प्रायिकता क्या है।
- यदि $f$ ऐसे रूट पर शून्य होता है, तो $p$ को रिजल्टेंट $\text{Res}(f, \Phi_q)$ को विभाजित करना होगा।
- पॉइसन के प्रोडक्ट फॉर्मूला का उपयोग करते हुए, वे इस रिजल्टेंट के परिमाण को $\|f\|_1^{q-1}$ द्वारा बाउंड करते हैं।
- यह दर्शाता है कि "बुरे" अभाज्य $p$ की संख्या अधिकतम $(q-1)\log_2 \|f\|_1$ है जहाँ अनिश्चितता सिद्धांत विफल हो जाता है।
- बोम्बिएरी-विनोग्राड (Bombieri–Vinogradov) प्रमेय का आह्वान करके, वे दिखाते हैं कि अनंत रूप से कई $q$ के लिए, $P(q)$ का सेट पर्याप्त बड़ा है ( $|P(q)| \ge q^3 / (32 \log q)$ ), जिससे बुरे अभाज्य की डेंसिटी नगण्य हो जाती है।

3. प्रमुख योगदान और परिणाम

3.1 स्ट्रॉन्ग एडिटिव अनिश्चितता (Theorem 1.1 / Theorem 3.1)

प्रत्येक निश्चित अभाज्य $q$ के लिए, और सभी लेकिन सीमित अभाज्य $p \equiv 1 \pmod q$ के लिए, प्रत्येक गैर-शून्य $f \in \mathbb{F}_p^{\mathbb{Z}_q}$ संतुष्ट करता है:
$|\text{Supp}(f)| + |\text{Supp}(\hat{f})| \ge q + 1$
यह दर्शाता है कि एक $k$ -स्पार्स फंक्शन का ट्रांसफॉर्म सपोर्ट कम से कम $q - k + 1$ होता है। यह परिणाम ली-वू अनुमान का एक नॉन-यूनिफॉर्म संस्करण प्रदान करता है, जो तब मान्य होता है जब $p$ को $q$ के साथ पर्याप्त तेजी से बढ़ने की अनुमति दी जाती है।

3.2 एप्रोक्सिमेट अनसर्टेन्टी (Theorem 1.2 / Theorem 3.6)

अनंत रूप से कई अभाज्य $q$ के लिए, और किसी भी गैर-शून्य इंटीजर वेक्टर $c$ के लिए जिसका $|\text{Supp}(c)| < q$ और $\ell_1$ -नॉर्म $W$ है, एक रैंडम अभाज्य $p \in P(q)$ के ऊपर इनवर्स NTT के अपेक्षित सपोर्ट साइज का मान है:
$\mathbb{E}_p [|\text{Supp}(\hat{c})|] \ge q - 1 - \frac{32(q-1)\log q}{q^2} \log_2 W$
यह परिणाम उस व्यावहारिक परिदृश्य में भी मान्य है जहाँ $p$ , $q$ के बहुपद (polynomially) के रूप में सीमित है।

3.3 बेहतर आइडेंटिटी टेस्टिंग (Theorem 1.3 / Theorem 4.3)

लेखक इन सिद्धांतों को $k$ -स्पार्स एक्सपोनेंशियल पॉलीनोमियल्स (डिग्री $d$ और कोएफिशिएंट हाइट $w$ ) के लिए एक संशोधित ब्लैक-बॉक्स आइडेंटिटी टेस्ट बनाने के लिए लागू करते हैं।

संशोधन: टेस्ट मानक रैंडम इवैल्यूएशन पॉइंट्स के साथ-साथ अंतराल $P(q)$ में अभाज्य $p$ को रैंडमली सैंपल करता है।
साउंडनेस बाउंड: यदि $P \not\equiv 0$ , तो स्वीकृति की प्रायिकता इस प्रकार बाउंड की गई है:
$O\left(\frac{dk^2}{q}\right) + O\left(\frac{1}{q}\right) + O\left(\frac{\log(kw)\log q}{q^2}\right)$
महत्व: यदि $q = k^C$ है जहाँ $C > 2$ और $kw $पॉलीनोमियल रूप से बाउंड है, तो साउंडनेस एरर$ o(1) $हो जाता है (विशेष रूप से, यह$ q $के बढ़ने के साथ 0 की ओर जाता है)। यह ली-वू बाउंड$ q^{-1/(k-1)}$ की तुलना में एक सीधा सुधार है, जो समान परिदृश्य में 1 के करीब पहुँच जाता है।

4. महत्व और दावे

लेखक दावा करते हैं कि उनका प्राथमिक योगदान NTT के लिए एडिटिव अनिश्चितता सिद्धांत (additive uncertainty principles) स्थापित करना है, जो आइडेंटिटी टेस्टिंग के लिए साउंडनेस सिद्ध करने के लिए आवश्यक हैं। लेखक स्पष्ट रूप से कहते हैं कि मानक मल्टीप्लिकेटिव अनसर्टेन्टी प्रिंसिपल (Donoho–Stark) इस उद्देश्य के लिए अपर्याप्त है।

इस कार्य का महत्व निम्नलिखित में निहित है:

एक अनुमान का समाधान: NTT के लिए एक मजबूत अनिश्चितता सिद्धांत के लिए औपचारिक प्रमाण प्रदान करना, जो ली और वू के अनुमान के पीछे की अंतर्दृष्टि को मान्य करता है।
एल्गोरिद्मिक सुधार: यह प्रदर्शित करना कि अभाज्य मॉड्यूल $p$ के चयन को रैंडमाइज करके, एक व्यक्ति एक्सपोनेंशियल पॉलीनोमियल्स की आइडेंटिटी टेस्टिंग के लिए निरंतर साउंडनेस एरर प्राप्त कर सकता है, जिसे पहले उच्च एरर रेट वाले व्यावहारिक पैरामीटर सेटिंग्स में माना जाता था।
सैद्धांतिक सेतु (Theoretical Bridge): रिजल्टेंट्स और साइक्लोटोमिक पॉलीनोमियल्स के बीजगणितीय गुणों को फिनिट फील्ड्स पर ट्रांसफॉर्म की स्पर्सिटी गुणों से जोड़ना।

लेखक अपने सबसे मजबूत परिणाम (Theorem 3.1) की "नॉन-यूनिफॉर्म" प्रकृति के प्रति विनम्र रहते हैं, यह नोट करते हुए कि यह "सभी लेकिन सीमित" अभाज्य पर लागू होता है, और व्यावहारिक अनुप्रयोग के लिए (जहाँ $p$ छोटा है) संभाव्यता आधारित परिणाम (Theorem 3.6) पर निर्भर करते हैं। वे यह दावा नहीं करते हैं कि उन्होंने सभी एक्सपोनेंशियल एक्सप्रेशंस के लिए सामान्य PIT समस्या को हल कर दिया है, बल्कि विशेष रूप से उनके अनुप्रयोग अनुभाग में परिभाषित स्पार्स, कंडेंस्ड केस के लिए।