Преобразование Фурье на конечных группах

В математике преобразование Фурье на конечных группах является обобщением дискретного преобразования Фурье от циклических к произвольным конечным группам .

Определения

Фурье Преобразование функции $f:G\to \mathbb {C}$ в представительстве $\varrho :G\to \mathrm {GL} _{d_{\varrho }}(\mathbb {C} )$ из $G$ является

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

Для каждого представления $\varrho$ из $G$ , ${\widehat {f}}(\varrho )$ это $d_{\varrho }\times d_{\varrho }$ матрица, где $d_{\varrho }$ это степень $\varrho$ .

Позволять ${\widehat {G}}$ — полный набор неэквивалентных неприводимых представлений $G$ . Тогда обратное преобразование Фурье на элементе $a$ из $G$ дается

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

Характеристики

Преобразование свертки

Свертка функций двух $f,g:G\to \mathbb {C}$ определяется как

$(f\ast g)(a)=\sum _{b\in G}f\!\left(ab^{-1}\right)g(b).$

Преобразование Фурье свертки в любом представлении $\varrho$ из $G$ дается

${\widehat {f\ast g}}(\varrho )={\hat {f}}(\varrho ){\hat {g}}(\varrho ).$

Формула Планшереля

Для функций $f,g:G\to \mathbb {C}$ , формула Планшереля гласит

$\sum _{a\in G}f(a^{-1})g(a)={\frac {1}{|G|}}\sum _{i}d_{\varrho _{i}}{\text{Tr}}\left({\hat {f}}(\varrho _{i}){\hat {g}}(\varrho _{i})\right),$

где $\varrho _{i}$ являются неприводимыми представлениями $G$ .

Преобразование Фурье для конечных абелевых групп

Если группа G — конечная абелева группа , то ситуация значительно упрощается:

все неприводимые представления $\varrho _{i}$ имеют степень 1 и, следовательно, равны неприводимым характерам группы. Таким образом, в этом случае матричное преобразование Фурье становится скалярным.

Множество неприводимых G -представлений имеет самостоятельную естественную групповую структуру, которую можно отождествить с группой ${\widehat {G}}:=\mathrm {Hom} (G,S^{1})$ групп гомоморфизмов из G в $S^{1}=\{z\in \mathbb {C} ,|z|=1\}$ . Эта группа известна как двойственная к G Понтрягину .

Преобразование Фурье функции $f:G\to \mathbb {C}$ это функция ${\widehat {f}}:{\widehat {G}}\to \mathbb {C}$ данный

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

Обратное преобразование Фурье тогда определяется выражением

$f(a)={\frac {1}{|G|}}\sum _{\chi \in {\widehat {G}}}{\widehat {f}}(\chi )\chi (a).$ Для $G=\mathbb {Z} /n$ , выбор примитивного корня n-й степени из единицы $\zeta$ дает изоморфизм

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

данный $m\mapsto (r\mapsto \zeta ^{mr})$ . В литературе чаще всего выбирают $\zeta =e^{2\pi i/n}$ , что объясняет формулу, приведенную в статье о дискретном преобразовании Фурье . Однако такой изоморфизм не является каноническим, аналогично ситуации, когда конечномерное векторное пространство изоморфно своему двойственному , но для установления изоморфизма требуется выбор базиса.

Свойство, которое часто полезно в теории вероятности, заключается в том, что преобразование Фурье равномерного распределения просто $\delta _{a,0}$ , где 0 — идентификатор группы и $\delta _{i,j}$ это дельта Кронекера .

Преобразование Фурье также можно выполнить на смежных классах группы.

Связь с теорией представлений

Существует прямая связь между преобразованием Фурье на конечных группах и теорией представлений конечных групп . Множество комплекснозначных функций на конечной группе $G$ , вместе с операциями поточечного сложения и свертки образуют кольцо, естественно отождествляемое с групповым кольцом $G$ над комплексными числами, $\mathbb {C} [G]$ . Модули этого кольца — то же самое, что и представления. Из теоремы Машке следует, что $\mathbb {C} [G]$ — полупростое кольцо , поэтому по теореме Артина–Веддерберна оно разлагается как прямое произведение матричных колец . Преобразование Фурье на конечных группах явно демонстрирует это разложение с матричным кольцом размерности $d_{\varrho }$ для каждого неприводимого представления.Более конкретно, теорема Петера-Вейля (для конечных групп) утверждает, что существует изоморфизм $\mathbb {C} [G]\cong \bigoplus _{i}\mathrm {End} (V_{i})$ данный $\sum _{g\in G}a_{g}g\mapsto \left(\sum a_{g}\rho _{i}(g):V_{i}\to V_{i}\right)$ Левая часть — это алгебра группы G. групповая Прямая сумма ведется по полному набору неэквивалентных неприводимых G -представлений. $\varrho _{i}:G\to \mathrm {GL} (V_{i})$ .

Преобразование Фурье для конечной группы и есть этот изоморфизм. Упомянутая выше формула произведения эквивалентна утверждению, что это отображение является кольцевым изоморфизмом .

Над другими полями

Приведенную выше теоретическую декомпозицию представлений можно обобщить на поля $k$ кроме $\mathbb {C}$ пока ${\text{char}}(k)\nmid |G|$ по теореме Машке . То есть групповая алгебра $k[G]$ является полупростым. Те же формулы можно использовать для преобразования Фурье и обратного ему, что особенно важно. ${\frac {1}{|G|}}$ определяется в $k$ .

Модульный корпус

Когда ${\text{char}}(k)||G|$ , $k[G]$ больше не является полупростым, и необходимо рассмотреть модульную теорию представления $G$ над $k$ . Мы все еще можем разложить групповую алгебру на блоки с помощью разложения Пирса с использованием идемпотентов. То есть

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

и $1=\sum _{i}e_{i}$ представляет собой разложение единицы на центральные, примитивные, ортогональные идемпотенты. Выбор основы для блоков ${\text{span}}_{k}\{ge_{i}|g\in G\}$ и написание карт проекций $v\mapsto ve_{i}$ в качестве матрицы дает модульную матрицу ДПФ. ^[1]

Например, для симметричной группы идемпотенты $F_{p}[S_{n}]$ вычисляются в Мерфи ^[2] и явно в SageMath. ^[3]

Унитарность

Можно нормализовать приведенное выше определение, чтобы получить

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

с обратным

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

Два представления считаются эквивалентными, если одно можно получить из другого заменой базиса. Это отношение эквивалентности, и каждый класс эквивалентности содержит унитарное представление. Если ${\widehat {G}}$ состоит из унитарных представлений, то указанные преобразования унитарные.

Приложения

Это обобщение дискретного преобразования Фурье используется в численном анализе . Циркулянтная матрица — это матрица, каждый столбец которой представляет собой циклический сдвиг предыдущего. Циркулянтные матрицы можно диагонализировать быстро с помощью быстрого преобразования Фурье , что дает быстрый метод решения систем линейных уравнений с циркулянтными матрицами. Точно так же преобразование Фурье для произвольных групп можно использовать для создания быстрых алгоритмов для матриц с другими симметриями ( Åhlander & Munthe-Kaas 2005 ). Эти алгоритмы можно использовать для построения численных методов решения уравнений в частных производных , сохраняющих симметрию уравнений ( Munthe-Kaas 2006 ).

При применении к логической группе $(\mathbb {Z} /2\mathbb {Z} )^{n}$ Преобразование Фурье в этой группе — это преобразование Адамара , которое обычно используется в квантовых вычислениях и других областях. Алгоритм Шора использует как преобразование Адамара (путем применения вентиля Адамара к каждому кубиту), так и квантовое преобразование Фурье . Первый считает кубиты индексированными группой $(\mathbb {Z} /2\mathbb {Z} )^{n}$ и последний считает их проиндексированными $\mathbb {Z} /2^{n}\mathbb {Z}$ для целей преобразования Фурье на конечных группах. ^[5]

См. также

Ссылки

^ Уолтерс, Джексон (2024). «Что такое модульное преобразование Фурье?». arXiv : 2404.05796 .
^ Мерфи, Дж. Е. «Идемпотенты симметричной группы и гипотеза Накаямы» . Журнал алгебры . 81 (1): 258–265. дои : 10.1016/0021-8693(83)90219-3 .
^ SageMath, система математического программного обеспечения Sage (версия 10.4.0), The Sage Developers, 2024, https://www.sagemath.org .
^ Билз, Роберт (1997). «Квантовое вычисление преобразований Фурье над симметричными группами». Материалы двадцать девятого ежегодного симпозиума ACM по теории вычислений - STOC '97 . стр. 48–53. дои : 10.1145/258533.258548 . ISBN 0-89791-888-6 .
^ Лекция 5: Основные квантовые алгоритмы, Раджат Миттал, стр. 4-9.

Оландер, Кристер; Мунте-Каас, Ханс З. (2005), «Применение обобщенного преобразования Фурье в числовой линейной алгебре», BIT , 45 (4): 819–850, CiteSeerX 10.1.1.142.3122 , doi : 10.1007/s10543-005- 0030-3 , МР 2191479 .
Диаконис, Перси (1988), Представления групп в вероятности и статистике , Конспекты лекций - Серия монографий, том. 11, Институт математической статистики, Збл 0695.60012 .
Диаконис, Перси (12 декабря 1991 г.), «Конечные методы Фурье: доступ к инструментам» , в Боллобасе, Бела; Чунг, Фан Р.К. (ред.), Вероятностная комбинаторика и ее приложения , Труды симпозиумов по прикладной математике, том. 44, Американское математическое общество, стр. 171–194, ISBN. 978-0-8218-6749-5 .
Мунте-Каас, Ханс З. (2006), «О групповом анализе Фурье и сохраняющих симметрию дискретизациях УЧП», Journal of Physics A , 39 (19): 5563–84, CiteSeerX 10.1.1.329.9959 , doi : 10.1088/0305 -4470/39/19/С14 , МР 2220776 .
Террас, Одри (1999), Анализ Фурье конечных групп и приложения , издательство Кембриджского университета, стр. 251, ISBN 978-0-521-45718-7 , Збл 0928.43001 .

[1] Уолтерс, Джексон (2024). «Что такое модульное преобразование Фурье?». arXiv : 2404.05796 .

[2] Мерфи, Дж. Е. «Идемпотенты симметричной группы и гипотеза Накаямы» . Журнал алгебры . 81 (1): 258–265. дои : 10.1016/0021-8693(83)90219-3 .

[3] SageMath, система математического программного обеспечения Sage (версия 10.4.0), The Sage Developers, 2024, https://www.sagemath.org .

[4] Билз, Роберт (1997). «Квантовое вычисление преобразований Фурье над симметричными группами». Материалы двадцать девятого ежегодного симпозиума ACM по теории вычислений - STOC '97 . стр. 48–53. дои : 10.1145/258533.258548 . ISBN 0-89791-888-6 .

[5] Лекция 5: Основные квантовые алгоритмы, Раджат Миттал, стр. 4-9.

[1]

[2]

[3]

[4]

[5]