Transformada de Fourier en grupos finitos

En matemáticas , la transformada de Fourier en grupos finitos es una generalización de la transformada de Fourier discreta de grupos finitos cíclicos a arbitrarios .

Definiciones

La transformada de Fourier de una función en una representación de es ${\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).}$$

Para cada representación de , es una matriz, donde es el grado de . ${\displaystyle \varrho }$ ${\displaystyle G}$ ${\displaystyle {\widehat {f}}(\varrho )}$ ${\displaystyle d_{\varrho }\times d_{\varrho }}$ ${\displaystyle d_{\varrho }}$ ${\displaystyle \varrho }$

Sea el conjunto completo de representaciones irreducibles no equivalentes de . Entonces la transformada inversa de Fourier en un elemento de viene dada por ${\displaystyle {\widehat {G}}}$ ${\displaystyle G}$ ${\displaystyle a}$ ${\displaystyle G}$

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

Propiedades

Transformada de una convolución

La convolución de dos funciones se define como ${\displaystyle f,g:G\to \mathbb {C} }$

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

La transformada de Fourier de una convolución en cualquier representación de está dada por ${\displaystyle \varrho }$ ${\displaystyle G}$

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

fórmula plancherel

Para funciones , la fórmula de Plancherel establece ${\displaystyle f,g:G\to \mathbb {C} }$

$${\displaystyle \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),}$$

¿Dónde están las representaciones irreductibles de ? ${\displaystyle \varrho _{i}}$ ${\displaystyle G}$

Transformada de Fourier para grupos abelianos finitos

Si el grupo G es un grupo abeliano finito , la situación se simplifica considerablemente:

• todas las representaciones irreducibles son de grado 1 y, por tanto, iguales a los caracteres irreducibles del grupo. Por lo tanto, la transformada de Fourier con valores matricial se vuelve escalar en este caso. ${\displaystyle \varrho _{i}}$

• El conjunto de representaciones G irreducibles tiene una estructura de grupo natural por derecho propio, que puede identificarse con el grupo de homomorfismos de grupo de G a . Este grupo se conoce como dual Pontryagin de G. ${\displaystyle {\widehat {G}}:=\mathrm {Hom} (G,S^{1})}$ ${\displaystyle S^{1}=\{z\in \mathbb {C} ,|z|=1\}}$

La transformada de Fourier de una función es la función dada por ${\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).}$$

La transformada inversa de Fourier viene dada por

$${\displaystyle f(a)={\frac {1}{|G|}}\sum _{\chi \in {\widehat {G}}}{\widehat {f}}(\chi )\chi (a).}$$Porque , la elección de una raíz primitiva n - ésima de la unidad produce un isomorfismo ${\displaystyle G=\mathbb {Z} /n}$ ${\displaystyle \zeta }$

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

dado por . En la literatura, la elección común es , lo que explica la fórmula dada en el artículo sobre la transformada discreta de Fourier . Sin embargo, tal isomorfismo no es canónico, similar a la situación en la que un espacio vectorial de dimensión finita es isomorfo a su dual , pero dar un isomorfismo requiere elegir una base. ${\displaystyle m\mapsto (r\mapsto \zeta ^{mr})}$ ${\displaystyle \zeta =e^{2\pi i/n}}$

Una propiedad que suele ser útil en probabilidad es que la transformada de Fourier de la distribución uniforme es simple , donde 0 es la identidad del grupo y es el delta de Kronecker . ${\displaystyle \delta _{a,0}}$ ${\displaystyle \delta _{i,j}}$

La transformada de Fourier también se puede realizar en clases laterales de un grupo.

Relación con la teoría de la representación

Existe una relación directa entre la transformada de Fourier sobre grupos finitos y la teoría de la representación de grupos finitos . El conjunto de funciones de valores complejos en un grupo finito, junto con las operaciones de suma puntual y convolución, forman un anillo que se identifica naturalmente con el anillo de grupo de sobre los números complejos . Los módulos de este anillo son lo mismo que las representaciones. El teorema de Maschke implica que es un anillo semisimple , por lo que según el teorema de Artin-Wedderburn se descompone como un producto directo de los anillos de la matriz . La transformada de Fourier en grupos finitos exhibe explícitamente esta descomposición, con un anillo matricial de dimensión para cada representación irreducible. Más específicamente, el teorema de Peter-Weyl (para grupos finitos) establece que existe un isomorfismo dado por El lado izquierdo es el álgebra de grupos de G. La suma directa se obtiene sobre un conjunto completo de representaciones G irreductibles y no equivalentes . ${\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)}$$ ${\displaystyle \varrho _{i}:G\to \mathrm {GL} (V_{i})}$

La transformada de Fourier para un grupo finito es precisamente este isomorfismo. La fórmula del producto mencionada anteriormente equivale a decir que este mapa es un isomorfismo de anillo .

Sobre otros campos

La descomposición teórica de representación anterior se puede generalizar a campos distintos del tiempo a través del teorema de Maschke . Es decir, el álgebra de grupos es semisimple. Se pueden usar las mismas fórmulas para la transformada de Fourier y su inversa, como se define de manera crucial en . ${\displaystyle k}$ ${\displaystyle \mathbb {C} }$ ${\displaystyle {\text{char}}(k)\nmid |G|}$ ${\displaystyle k[G]}$ ${\displaystyle {\frac {1}{|G|}}}$ ${\displaystyle k}$

Caja modular

Cuando , ya no es semisimple y se debe considerar la teoría de representación modular de over . Todavía podemos descomponer el álgebra de grupos en bloques mediante la descomposición de Peirce usando idempotentes. Eso es ${\displaystyle {\text{char}}(k)||G|}$ ${\displaystyle k[G]}$ ${\displaystyle G}$ ${\displaystyle k}$

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

y es una descomposición de la identidad en idempotentes ortogonales, primitivos y centrales. Elegir una base para los bloques y escribir los mapas de proyección como una matriz produce la matriz DFT modular. ^[1] ${\displaystyle 1=\sum _{i}e_{i}}$ ${\displaystyle {\text{span}}_{k}\{ge_{i}|g\in G\}}$ ${\displaystyle v\mapsto ve_{i}}$

Por ejemplo, para el grupo simétrico los idempotentes de se calculan en Murphy ^[2] y explícitamente en SageMath. ^[3] ${\displaystyle F_{p}[S_{n}]}$

Unitaridad

Se puede normalizar la definición anterior para obtener

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

con inversa

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

Dos representaciones se consideran equivalentes si una puede obtenerse de la otra mediante cambio de base. Esta es una relación de equivalencia y cada clase de equivalencia contiene una representación unitaria. Si consta de representaciones unitarias, entonces las transformaciones anteriores son unitarias. Las representaciones unitarias se pueden obtener mediante el truco unitario de Weyl . ${\displaystyle {\widehat {G}}}$

Aplicaciones

Esta generalización de la transformada discreta de Fourier se utiliza en análisis numérico . Una matriz circulante es una matriz donde cada columna es un desplazamiento cíclico de la anterior. Las matrices circulantes se pueden diagonalizar rápidamente utilizando la transformada rápida de Fourier , lo que produce un método rápido para resolver sistemas de ecuaciones lineales con matrices circulantes. De manera similar, la transformada de Fourier en grupos arbitrarios se puede utilizar para generar algoritmos rápidos para matrices con otras simetrías (Åhlander y Munthe-Kaas 2005). Estos algoritmos se pueden utilizar para la construcción de métodos numéricos para resolver ecuaciones diferenciales parciales que preserven las simetrías de las ecuaciones (Munthe-Kaas 2006).

Cuando se aplica al grupo booleano , la transformada de Fourier en este grupo es la transformada de Hadamard , que se usa comúnmente en computación cuántica y otros campos. El algoritmo de Shor utiliza tanto la transformada de Hadamard (aplicando una puerta de Hadamard a cada qubit) como la transformada cuántica de Fourier . El primero considera que los qubits están indexados por el grupo y el segundo los considera indexados por a los efectos de la transformada de Fourier en grupos finitos. ^[5] ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$ ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$ ${\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }$

Ver también

• transformada de Fourier
• Análisis espectral de mínimos cuadrados
• Teoría de la representación de grupos finitos.
• Teoría del personaje

Referencias

1. Walters, Jackson (2024). "¿Qué es la transformada modular de Fourier?". arXiv : 2404.05796 .
2. Murphy, GE "Los idempotentes del grupo simétrico y la conjetura de Nakayama". Revista de Álgebra . 81 (1): 258–265. doi :10.1016/0021-8693(83)90219-3.
3. SageMath, el sistema de software Sage Mathematics (versión 10.4.0), The Sage Developers, 2024, https://www.sagemath.org.
4. Beals, Robert (1997). "Cálculo cuántico de transformadas de Fourier sobre grupos simétricos". Actas del vigésimo noveno simposio anual de ACM sobre teoría de la informática - STOC '97 . págs. 48–53. doi :10.1145/258533.258548. ISBN 0-89791-888-6.
5. Conferencia 5: Algoritmos cuánticos básicos, Rajat Mittal, págs. 4-9

• Åhlander, Krister; Munthe-Kaas, Hans Z. (2005), "Aplicaciones de la transformada de Fourier generalizada en álgebra lineal numérica", BIT , 45 (4): 819–850, CiteSeerX  10.1.1.142.3122 , doi :10.1007/s10543-005- 0030-3, SEÑOR  2191479.
• Diaconis, Persi (1988), Representaciones grupales en probabilidad y estadística, Lecture Notes—Monograph Series, vol. 11, Instituto de Estadística Matemática, Zbl  0695.60012.
• Diaconis, Persi (12 de diciembre de 1991), "Métodos finitos de Fourier: acceso a herramientas", en Bollobás, Béla; Chung, Fan RK (eds.), Combinatoria probabilística y sus aplicaciones , Actas de simposios en matemáticas aplicadas, vol. 44, Sociedad Estadounidense de Matemáticas, págs. 171-194, ISBN 978-0-8218-6749-5.
• Munthe-Kaas, Hans Z. (2006), "Sobre el análisis de grupo de Fourier y la simetría que preserva las discretizaciones de PDE", Journal of Physics A , 39 (19): 5563–84, CiteSeerX  10.1.1.329.9959 , doi :10.1088/0305 -4470/39/19/S14, SEÑOR  2220776.
• Terras, Audrey (1999), Análisis de Fourier sobre aplicaciones y grupos finitos, Cambridge University Press, p. 251, ISBN 978-0-521-45718-7, Zbl  0928.43001.