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 de Fourier inversa en un elemento de está 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 de Plancherel

Para las 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 irreducibles 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 lo tanto, iguales a los caracteres irreducibles del grupo. Por lo tanto, la transformada de Fourier con valores matriciales se convierte en una transformada 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 de 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 de Fourier inversa viene dada entonces por

$${\displaystyle f(a)={\frac {1}{|G|}}\sum _{\chi \in {\widehat {G}}}{\widehat {f}}(\chi )\chi (a).}$$Para , la elección de una raíz n -ésima primitiva 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 de Fourier discreta . Sin embargo, tal isomorfismo no es canónico, de manera 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 a menudo es útil en probabilidad es que la transformada de Fourier de la distribución uniforme es simplemente , 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 representación de grupos finitos . El conjunto de funciones de valor complejo sobre un grupo finito, , junto con las operaciones de adición 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 por el teorema de Artin-Wedderburn se descompone como un producto directo de anillos de matrices . La transformada de Fourier sobre grupos finitos exhibe explícitamente esta descomposición, con un anillo de matrices de dimensión para cada representación irreducible. Más específicamente, el teorema de Peter-Weyl (para grupos finitos) establece que hay un isomorfismo dado por El lado izquierdo es el álgebra de grupos de G . La suma directa es sobre un conjunto completo de G -representaciones irreducibles 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 justamente este isomorfismo. La fórmula del producto mencionada anteriormente equivale a decir que esta función es un isomorfismo de anillo .

Sobre otros campos

La descomposición teórica de la representación anterior se puede generalizar a otros campos además de siempre que se aplique el teorema de Maschke . Es decir, el álgebra de grupos es semisimple. Las mismas fórmulas se pueden utilizar 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 sobre . Todavía podemos descomponer el álgebra de grupos en bloques a través de la descomposición de Peirce utilizando idempotentes. Es decir ${\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 centrales, primitivos y ortogonales. Al elegir una base para los bloques y escribir los mapas de proyección como una matriz se obtiene 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 un 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 pueden obtenerse mediante el truco unitario de Weyl . ${\displaystyle {\widehat {G}}}$

Aplicaciones

Esta generalización de la transformada de Fourier discreta se utiliza en el análisis numérico . Una matriz circulante es una matriz en la que 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 , y esto 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 proporcionar 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 preservan 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 utiliza comúnmente en la computación cuántica y otros campos. El algoritmo de Shor utiliza tanto la transformada de Hadamard (aplicando una puerta de Hadamard a cada cúbit) como la transformada cuántica de Fourier . La primera considera los cúbits como indexados por el grupo y la segunda los considera como indexados por para el propósito 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} }$

Véase también

• Transformada de Fourier
• Análisis espectral de mínimos cuadrados
• Teoría de la representación de grupos finitos
• Teoría del carácter

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". Journal of Algebra . 81 (1): 258–265. doi :10.1016/0021-8693(83)90219-3.
3. SageMath, el sistema de software matemático Sage (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 la ACM sobre teoría de la computación - 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, MR  2191479.
• Diaconis, Persi (1988), Representaciones grupales en probabilidad y estadística, Notas de clase—Serie de monografías, 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 sobre matemáticas aplicadas, vol. 44, American Mathematical Society, págs. 171–194, ISBN 978-0-8218-6749-5.
• Munthe-Kaas, Hans Z. (2006), "Sobre el análisis de Fourier de grupo y las discretizaciones de ecuaciones diferenciales parciales que preservan la simetría", Journal of Physics A , 39 (19): 5563–84, CiteSeerX  10.1.1.329.9959 , doi :10.1088/0305-4470/39/19/S14, MR  2220776.
• Terras, Audrey (1999), Análisis de Fourier en grupos finitos y aplicaciones, Cambridge University Press, pág. 251, ISBN 978-0-521-45718-7, Zbl0928.43001 ​.