تحويل فورييه على المجموعات المنتهية

في الرياضيات ، يعتبر تحويل فورييه على المجموعات المنتهية تعميمًا لتحويل فورييه المنفصل من المجموعات الدورية إلى المجموعات المنتهية العشوائية .

تحويل فورييه للدالة${\displaystyle f:G\to \mathbb {C} }$في تمثيل${\displaystyle \varrho :G\to \mathrm {GL} _{d_{\varrho }}(\mathbb {C} )}$ل${\displaystyle G}$يكون

$${\displaystyle {\widehat {f}}(\varrho )=\sum _{a\in G}f(a)\varrho (a).}$$

لكل تمثيل${\displaystyle \varrho }$ل${\displaystyle G}$،${\displaystyle {\widehat {f}}(\varrho )}$هو${\displaystyle d_{\varrho }\times d_{\varrho }}$المصفوفة، حيث${\displaystyle d_{\varrho }}$هي درجة${\displaystyle \varrho }$.

يترك${\displaystyle {\widehat {G}}}$لتكن المجموعة الكاملة من التمثيلات غير المتكافئة وغير القابلة للاختزال لـ${\displaystyle G}$ثم يتم إجراء تحويل فورييه العكسي عند عنصر ما${\displaystyle a}$ل${\displaystyle G}$يُعطى بواسطة

$${\displaystyle f(a)={\frac {1}{|G|}}\sum _{\varrho \in {\widehat {G}}}d_{\varrho }\mathrm {Tr} \left(\varrho (a^{-1}){\widehat {f}}(\varrho )\right).}$$

إذا كانت المجموعة G مجموعة أبيلية منتهية ، فإن الوضع يتبسط بشكل كبير:

• جميع التمثيلات غير القابلة للاختزال${\displaystyle \varrho _{i}}$تكون هذه المصفوفات من الدرجة الأولى، وبالتالي تساوي الخصائص غير القابلة للاختزال للمجموعة. ومن ثم، يصبح تحويل فورييه ذو القيم المصفوفية ذا قيم قياسية في هذه الحالة.

• تتمتع مجموعة التمثيلات غير القابلة للاختزال G ببنية زمرة طبيعية في حد ذاتها، والتي يمكن تحديدها مع الزمرة${\displaystyle {\widehat {G}}:=\mathrm {Hom} (G,S^{1})}$من تماثلات المجموعة من G إلى${\displaystyle S^{1}=\{z\in \mathbb {C} ,|z|=1\}}$تُعرف هذه المجموعة باسم ثنائي بونترياجين لـ G.

تحويل فورييه للدالة${\displaystyle f:G\to \mathbb {C} }$هي الوظيفة${\displaystyle {\widehat {f}}:{\widehat {G}}\to \mathbb {C} }$مقدم من

$${\displaystyle {\widehat {f}}(\chi )=\sum _{a\in G}f(a){\bar {\chi }}(a).}$$

يُعطى التحويل العكسي لفورييه بالصيغة التالية:

$${\displaystyle f(a)={\frac {1}{|G|}}\sum _{\chi \in {\widehat {G}}}{\widehat {f}}(\chi )\chi (a).}$$ ل${\displaystyle G=\mathbb {Z} /n\mathbb {Z} }$، اختيار جذر أولي من الرتبة n للوحدة${\displaystyle \zeta }$ينتج عنه تماثل

$${\displaystyle G\to {\widehat {G}},}$$

مقدم من${\displaystyle m\mapsto (r\mapsto \zeta ^{mr})}$في الأدبيات، الخيار الشائع هو${\displaystyle \zeta =e^{2\pi i/n}}$وهذا ما يفسر الصيغة الواردة في المقال حول تحويل فورييه المنفصل . ومع ذلك، فإن هذا التشاكل ليس قياسيًا، على غرار حالة كون فضاء متجهي محدود الأبعاد متماثلًا مع فضاءه الثنائي ، ولكن إعطاء التشاكل يتطلب اختيار أساس.

من الخصائص المفيدة في الاحتمالات أن تحويل فورييه للتوزيع المنتظم هو ببساطة${\displaystyle \delta _{a,0}}$، حيث يمثل الصفر هوية المجموعة و${\displaystyle \delta _{i,j}}$هي دلتا كرونكر .

يمكن أيضًا إجراء تحويل فورييه على المجموعات المشاركة لمجموعة ما.

توجد علاقة مباشرة بين تحويل فورييه على الزمر المنتهية ونظرية تمثيل الزمر المنتهية . مجموعة الدوال ذات القيم المركبة على زمرة منتهية،${\displaystyle G}$تشكل هذه العملية، بالإضافة إلى عمليتي الجمع النقطي والالتفاف، حلقةً تُعرَّف بشكل طبيعي بأنها حلقة المجموعة لـ${\displaystyle G}$على الأعداد المركبة،${\displaystyle \mathbb {C} [G]}$وحدات هذه الحلقة هي نفسها تمثيلاتها. تنص نظرية ماشكه على أن${\displaystyle \mathbb {C} [G]}$هي حلقة شبه بسيطة ، لذا، وفقًا لنظرية آرتين-ويدربورن، يمكن تحليلها إلى حاصل ضرب مباشر لحلقات المصفوفات . ويُظهر تحويل فورييه على المجموعات المنتهية هذا التحليل بشكل صريح، مع حلقة مصفوفات ذات بُعد${\displaystyle d_{\varrho }}$لكل تمثيل غير قابل للاختزال. وبشكل أكثر تحديدًا، تنص نظرية بيتر-ويل (للمجموعات المنتهية) على وجود تماثل. $${\displaystyle \mathbb {C} [G]\cong \bigoplus _{i}\mathrm {End} (V_{i})}$$ مقدم من $${\displaystyle \sum _{g\in G}a_{g}g\mapsto \left(\sum a_{g}\rho _{i}(g):V_{i}\to V_{i}\right)}$$ يمثل الجانب الأيسر جبر المجموعة G. ويتم الجمع المباشر على مجموعة كاملة من تمثيلات G غير المتكافئة وغير القابلة للاختزال.${\displaystyle \varrho _{i}:G\to \mathrm {GL} (V_{i})}$.

إن تحويل فورييه لمجموعة منتهية هو هذا التشاكل تحديدًا. صيغة الضرب المذكورة أعلاه تُكافئ القول بأن هذا التطبيق هو تشاكل حلقي .

يمكن تعميم التفكيك النظري للتمثيل المذكور أعلاه على الحقول${\displaystyle k}$بخلاف${\displaystyle \mathbb {C} }$طالما${\displaystyle {\text{char}}(k)\nmid |G|}$عن طريق نظرية ماشكه . أي، جبر المجموعة${\displaystyle k[G]}$هي شبه بسيطة. يمكن استخدام نفس الصيغ لتحويل فورييه ومعكوسه، كما هو مهم للغاية.${\displaystyle {\frac {1}{|G|}}}$يُعرَّف في${\displaystyle k}$.

متى${\displaystyle {\text{char}}(k)\mid |G|}$،${\displaystyle k[G]}$لم يعد الأمر شبه بسيط، ويجب على المرء أن يأخذ في الاعتبار نظرية التمثيل المعياري لـ${\displaystyle G}$زيادة${\displaystyle k}$لا يزال بإمكاننا تقسيم جبر المجموعة إلى كتل باستخدام تحليل بيرس باستخدام العناصر المتطابقة.

${\displaystyle k[G]\cong \bigoplus _{i}k[G]e_{i}}$

و${\displaystyle 1=\sum _{i}e_{i}}$هو تفكيك للهوية إلى عناصر مركزية، أولية، ومتعامدة متساوية القوة. اختيار أساس للكتل${\displaystyle {\text{span}}_{k}\{ge_{i}|g\in G\}}$وكتابة خرائط الإسقاط${\displaystyle v\mapsto ve_{i}}$^{[ 1 ]} حيث أن المصفوفة تعطي مصفوفة DFT المعيارية .

على سبيل المثال، بالنسبة للمجموعة المتناظرة، فإن العناصر المتساوية القوة لـ${\displaystyle F_{p}[S_{n}]}$يتم حسابها في مورفي ^{[ 2 ]} وبشكل صريح في SageMath. ^{[ 3 ]}

يمكن تطبيع التعريف أعلاه للحصول على

${\displaystyle {\hat {f}}(\rho )={\sqrt {\frac {d_{\rho }}{|G|}}}\sum _{g\in G}f(g)\rho (g)}$

مع العكس

${\displaystyle f(g)={\frac {1}{\sqrt {|G|}}}\sum _{\rho \in {\widehat {G}}}{\sqrt {d_{\rho }}}\mathrm {Tr} ({\hat {f}}(\rho )\rho ^{-1}(g))}$[ ^{4 ]​}

يُعتبر تمثيلان متكافئين إذا أمكن الحصول على أحدهما من الآخر بتغيير الأساس. هذه علاقة تكافؤ، وتحتوي كل فئة تكافؤ على تمثيل وحدوي. يمكن الحصول على التمثيلات الوحدوية باستخدام حيلة فايل الوحدوية في خاصية الصفر.${\displaystyle {\widehat {G}}}$إذا كانت تتكون من تمثيلات وحدوية، فإن تحويل فورييه المنفصل المقابل سيكون وحدويًا.

على الحقول المنتهية${\displaystyle F_{q^{2}}}$من الممكن إيجاد تغيير في الأساس في حالات معينة، على سبيل المثال المجموعة المتناظرة، عن طريق تحليل المصفوفة${\displaystyle U}$مرتبط بـ${\displaystyle G}$الشكل الثنائي الخطي المتناظر الثابت كـ${\displaystyle U=AA^{*}}$، أين${\displaystyle ^{*}}$يشير إلى المرافق المنقول بالنسبة إلى${\displaystyle x\mapsto x^{q}}$الاقتران. يُعطى التمثيل الوحدوي بواسطة${\displaystyle A^{*}\rho (g)A^{*-1}}$للحصول على تحويل فورييه المنفصل الأحادي، لاحظ أنه كما هو مُعرّف أعلاه${\displaystyle DFT.DFT^{*}=S}$، أين${\displaystyle S}$هي مصفوفة قطرية تتكون من عناصر +1 و -1. يمكننا تحليلها إلى عوامل.${\displaystyle S=RR^{*}}$عن طريق تحليل كل إشارة${\displaystyle c_{i}=z_{i}z_{i}^{*}}$.${\displaystyle uDFT=R^{-1}.DFT}$هو نظام أحادي.

يُستخدم هذا التعميم لتحويل فورييه المتقطع في التحليل العددي . المصفوفة الدائرية هي مصفوفة يكون فيها كل عمود عبارة عن إزاحة دورية للعمود السابق. يمكن تحويل المصفوفات الدائرية إلى مصفوفات قطرية بسرعة باستخدام تحويل فورييه السريع ، مما يوفر طريقة سريعة لحل أنظمة المعادلات الخطية التي تحتوي على مصفوفات دائرية. وبالمثل، يمكن استخدام تحويل فورييه على أي زمر للحصول على خوارزميات سريعة للمصفوفات ذات التناظرات الأخرى ( Åhlander & Munthe-Kaas 2005 ) . يمكن استخدام هذه الخوارزميات لبناء طرق عددية لحل المعادلات التفاضلية الجزئية التي تحافظ على تناظرات المعادلات ( Munthe-Kaas 2006 ) .

عند تطبيقها على المجموعة المنطقية${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$التحويل الفورييه على هذه المجموعة هو تحويل هادامارد ، وهو شائع الاستخدام في الحوسبة الكمومية وغيرها من المجالات. تستخدم خوارزمية شور كلاً من تحويل هادامارد (بتطبيق بوابة هادامارد على كل كيوبت) وتحويل فورييه الكمومي . يعتبر الأول الكيوبتات مفهرسة حسب المجموعة.${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$ويعتبرها الأخير مفهرسة بواسطة${\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }$لغرض تحويل فورييه على المجموعات المنتهية. ^{[ 5 ]}

• تحويل فورييه
• تحليل الطيف باستخدام طريقة المربعات الصغرى
• نظرية تمثيل المجموعات المنتهية
• نظرية الشخصية