Anàlisi harmònica sobre un grup abelià finit

En matemàtiques, l'anàlisi harmònica sobre un grup abelià finit és un cas particular d'anàlisi harmònica corresponent al cas que el grup és abelià i finit.

L'anàlisi harmònica permet definir la noció de transformada de Fourier o el producte de convolució. És el marc de nombrosos teoremes com al de Plancherel, la igualtat de Parseval o la dualitat de Pontryagin.

El cas on el grup és abelià i finit és el més senzill de la teoria, la transformada de Fourier es limita a una suma finita i el grup dual és isomorf al grup d'origen.

L'anàlisi harmònica sobre un grup abelià finit té nombroses aplicacions, particularment en aritmètica modular i en teoria de la informació.

Context

Àlgebra de grups

L'anàlisi harmònica constitueix una eina d'estudi de l'espai de les aplicacions C^G d'un conjunt, aquí un grup abelià finit G (notat a tot l'article de manera additiva), en el cos dels nombres complexos C. Aquest espai disposa de diverses estructures. Per començar, com que C és un cos, C^G és un espai vectorial complex de dimensió g on g designa l'ordre del grup G. De forma natural té un producte hermític $\langle \cdot |\cdot \rangle$ definit per:

$\forall f,h\in \mathbb {C} ^{G},\quad \langle f|h\rangle ={\frac {1}{g}}\sum _{s\in G}f(s)^{*}\cdot h(s)\;$

Aquí, i en la resta de l'article quan z designa un nombre complex, z^* designa el seu conjugat. Aquest producte hermític anomenat canònic, confereix a C^G una estructura d'espai de Hilbert, notat L²(G).

En tot l'article (e_s) on s recorre G, designa la base canònica de C^G, és a dir que e_s designa la funció que a l'element t de G li associa 0 excepte si t és igual a s i en aquest cas e_s(s) = 1.

L'espai vectorial engendrat per la família (e_s) té la multiplicació interna següent, perllongant la del grup G:

$\forall (a_{s})_{s\in G}\;,(b_{t})_{t\in G}\in \mathbb {C} ^{G},\quad \left(\sum _{s\in G}a_{s}\cdot e_{s}\right)\cdot \left(\sum _{t\in G}b_{t}\cdot e_{t}\right)=\sum _{s,t\in G}a_{s}b_{t}\cdot e_{st}\;$

Aquesta multiplicació confereix a L²(G) una estructura d'àlgebra semisimple, en general notada C[G].

La teoria de l'anàlisi harmònica sobre un grup abelià finit utilitza indiferentment les notacions L²(G) o C[G] per designar l'estructura de base de la teoria. En aquest article les notacions utilitzades són les de C[G]. Així, si a és un element de l'àlgebra, s'utilitza aquí la notació a_s per designar la coordenada de a a la base canònica, aquesta notació correspon a la igualtat a_s = a(s) si a es considera com un element de L²(G).

Grup dual

Article principal: caràcter d'un grup finit

El grup dual de G, notat aquí $\scriptstyle {\widehat {G}}$ està constituït pel conjunt de s caràcters de G. Forma un grup isomorf a G. Està constituït d'aplicacions de G en C, car està inclòs en L²(G) identificat aquí a C[G]. Forma de fet una base orthonormal de l'àlgebra.

L'àlgebra del grup dual és canònicament isomorfa al conjunt de les aplicacions del grup dual a C. Aquestes aplicacions es perllonguen per linearitat en una aplicació que a una combinació lineal de caràcters li associa un complex, és a dir en un element del dual de l'àlgebra C[G]. El dual de C[G] és doncs canònicament isomorf a l'àlgebra del grup dual de G.

Teoria de l'anàlisi harmònica

Transformada de Fourier

Article principal: Transformada de Fourier

La igualtat de Parseval en el cas d'un espai de dimensió finita mostra que tot element a de C[G] verifica la igualtat següent:

$a=\sum _{s\in G}a_{s}e_{s}=\sum _{\chi \in {\widehat {G}}}a_{\chi }\chi \quad amb\quad a_{\chi }=<a|\chi >={\frac {1}{g}}\sum _{s\in G}a_{s}^{*}.\chi (s)\quad et\quad <a|a>=\sum _{\chi \in {\widehat {G}}}|a_{\chi }|^{2}\;$

Aquí (a_s) designa les coordenades de a a la base canònica i (a_χ) les coordenades de a a la base dels caràcters.

• La transformada de Fourier d'un element a de C[G] correspon a la funció generalment notada $\scriptstyle {\widehat {a}}$ del grup dual de G en C, és a dir una funció que a un caràcter del grup li associa un complex, definida per:

${\widehat {a}}(\chi )={\frac {1}{\sqrt {g}}}\sum _{s\in G}a_{s}\chi (s)^{*}\;$

• La transformada de Fourier és una aplicació lineal de l'àlgebra de G en el seu dual.

Igualtat de Parseval

Article principal: Igualtat de Parseval

El producte hermític genera una isometria canònica entre l'àlgebra de G i el seu dual. Per tant és possible identificar-los, en aquest context, es verifica la següent propietat:

• La transformada de Fourier sobre el grup G és una isometria lineal de l'àlgebra del grup G en l'àlgebra del seu dual el que es tradueix en la igualtat següent, anomenada de Parseval:

$\forall a,b\in \mathbb {C} [G]\quad <a|b>_{\mathbb {C} [G]}=<{\hat {a}}|{\hat {b}}>_{\mathbb {C} [{\widehat {G}}]}$

Demostració

Si b és igual a a, llavors com que el grup dual és una base orthonormal de la seva àlgebra: $<{\hat {a}}|{\hat {a}}>_{\mathbb {C} [{\widehat {G}}]}={\frac {1}{g}}\sum _{\chi \in {\widehat {G}}}{\hat {a}}(\chi )^{*}.{\hat {a}}(\chi )={\frac {1}{g^{2}}}\sum _{\chi \in {\widehat {G}}}\sum _{s,t\in G}a_{s}^{*}\chi (s).a_{t}\chi (t)^{*}={\frac {1}{g^{2}}}\sum _{\chi \in {\widehat {G}}}\sum _{s\in G}|a_{s}|^{2}={\frac {1}{g}}\sum _{s\in G}|a_{s}|^{2}=<a|a>_{\mathbb {C} [G]}\;$

Finalment, en el cas general:

$<{\hat {a}}+{\hat {b}}|{\hat {a}}+{\hat {b}}>=<{\hat {a}}|{\hat {a}}>+<{\hat {b}}|{\hat {b}}>+2.Reel(<{\hat {a}}|{\hat {b}}>)\;$ $<a+b|a+b>=<a|a>+<b|b>+2.Reel(<a|b>)\;$

De on se'n dedueix:

$Reel(<{\hat {a}}|{\hat {b}}>)=Reel(<a|b>)\;$

El mateix càlcul sobre <a + b, i(a + b)> mostra que les parts imaginàries també són iguals. El que demostra el caràcter isomètric de la transformació.

L'aspecte injectiu de la transformació prové del fet que és una isometria, la exhaustivitat es demostra fixant-se que els dos espais de sortida i d'arribada tenen igual dimensió.

Fórmula de Plancherel

Article principal: Teorema de Plancherel

• Es verifica la fórmula següent, anomenada d'inversió de Plancherel.

$\forall a\in \mathbb {C} [G]\quad a={\frac {1}{\sqrt {g}}}\sum _{\chi \in {\widehat {G}}}{\widehat {a}}(\chi )\chi \;$

En efecte, els productes hermítics de cadascun dels dos membres de la igualtat per un mateix caràcter són iguals :

$\forall \zeta \in {\widehat {G}}\quad <{\frac {1}{\sqrt {g}}}\sum _{\chi \in {\widehat {G}}}{\widehat {a}}(\chi )\chi |\zeta >={\frac {1}{\sqrt {g}}}{\widehat {a}}(\zeta )^{*}={\frac {1}{g}}\sum _{s\in G}a_{s}^{*}\zeta (s)=<a|\zeta >$

Producte de convolució

Article principal: Producte de convolució

En aquest context el producte de convolució es defineix de manera simple:

• Siguin a i b dos elements de l'àlgebra del grup G que tenen per coordenades (a_s) i (b_s), el producte de convolució de a per b, notat a * b, és l'element de l'àlgebra que té les coordenades (c_s) definides per:

$c_{s}=\sum _{t\in G}a_{t}b_{s-t}\quad donc\quad a*b=\sum _{s\in G}c_{s}e_{s}=\sum _{s,t\in G}a_{t}b_{s-t}e_{s}\;$

Es té la següent proposició:

• Siguin a et b dos elements de l'àlgebra del grup G, la transformada de Fourier de a * b és el producte de les transformades de Fourier de a i de b..

$\forall a,b\in \mathbb {C} [G]\quad {\widehat {a*b}}\,(\chi )={\hat {a}}(\chi ).{\hat {b}}(\chi )\;$

En efecte, si χ és un caràcter del grup:

${\widehat {a*b}}(\chi )={\frac {1}{g}}\sum _{s,t\in G}a_{t}b_{s-t}\chi (s)^{*}\;$

Si es nota u el valor s - t, s'obté:

${\widehat {a*b}}(\chi )={\frac {1}{g}}\sum _{t,u\in G}a_{t}b_{u}\chi (t+u)^{*}={\Big (}{\frac {1}{\sqrt {g}}}\sum _{t\in G}a_{t}\chi (t)^{*}{\Big )}.{\Big (}{\frac {1}{\sqrt {g}}}\sum _{u\in G}b_{u}\chi (u)^{*}{\Big )}={\hat {a}}(\chi ).{\hat {b}}(\chi )\;$

Se'n dedueixen les propietats usuals del producte de convolució:

• El producte de convolució és una operació interna de l'àlgebra del grup commutativa, associativa, i distributiva respecte a l'addició

Aquestes propietats es poden expressar de la manera següent:

• L'estructura (C[G], +, *) és una àlgebra semisimple isomorfa a l'àlgebra del dual de G i per tant a C[G].

En efecte, n'hi ha prou amb fixar-se que G i el seu dual són isomorfs.

Dualitat de Pontryagin

Article principal: Dualitat de Pontryagin

• Sigui H un subgrup de G, s'anomena grup ortogonal de H, sovint notat $\scriptstyle H^{\perp }$, el subgrup del grup dual de G definit de la següent manera:

$H^{\perp }=\{\chi \in {\widehat {G}}\quad /\quad \forall h\in H\quad \chi (h)=1\}$

La dualitat de Pontryagin s'expressa a través de les tres propietats següents:

• G i el seu bidual són canònicament isomorfs.
• el dual del quocient G/H és isomorf a l'ortogonal de H.
• El dual de H és isomorf al quocient del dual de G per l'ortogonal de H.

Demostracions

* G i el seu bidual són canònicament isomorfs.

La demostració es dona en el paràgraf Bidual de l'article caràcter d'un grup finit.

• El dual del quocient G/H és isomorf a l'ortogonal de H.

Sigui S la suprajecció canònica de G en G/H, considerem l'aplicació φ del dual de G/H en el dual de G definida per:

$\forall s\in G\quad \forall \chi \in {\widehat {G/H}}\quad \varphi (\chi )(s)=\chi \circ S(s)\;$

Si χ és un caràcter de G/H, llavors φ(χ) és la composició de dos morfismes per tant és un morfisme i és amb valor en C^*, φ(χ) és per tant un caràcter de G. Fixeu-vos a més que és clarament un morfisme de grup.

El nucli de S és igual a H, φ posseeix per tant una imatge inclosa en l'ortogonal de H Per tant es demostra que tot element ζ de l'ortogonal de H té un antecedent per φ. Observant que és constant sobre totes les classes de G/H, en efecte:

$\forall {\bar {s}}\in G/H\quad \forall t\in {\bar {s}}\quad \exists h\in H\quad /\quad t=s+h\quad et\quad \zeta (t)=\zeta (s+h)=\zeta (s).\zeta (h)=\zeta (s)\;$

Sigui χ el caràcter del grup G/H definit per:

$\forall {\bar {s}}\in G/H\quad \chi ({\bar {s}})=\zeta (s)\;$

La funció χ està ben definida ja que és constant sobre totes les classes de G/H, defineix bé un morfisme i χ és un caràcter de G/H. La seva imatge per φ és clarament igual a ζ. L'aplicació φ posseeix doncs per a imatge l'ortogonal de H. El seu nucli està compost pel caràcter constant igual a un sobre totes les classes de G/H i l'aplicació és per tant injectiva, per tant és un isomorfisme entre el dual de G/H i el grup ortogonal de H, el que finalitza la demostració.

• El dual de H és isomorf al quocient del dual de G per l'ortogonal de H.

Sigui ψ l'aplicació del dual de G en el dual de H que a un caràcter del grup G li associa la seva restricció a H. L'aplicació és un morfisme de grup.

El seu nucli està compost pels caràcters constants iguals a 1 sobre H, és a dir a l'ortogonal de H. Per pas al quocient, s'obté un morfisme θ del quocient del dual de G per l'ortogonal de H amb valor en el dual de H. La proposició precedent mostra la igualtat entre els ordres dels conjunts de sortida i d'arribada de θ, i com que θ és injectiva, la proposició queda demostrada.

Fórmula del sumatori de Poisson

En aquest paràgraf H designa un subgrup de G, h el seu ordre i k l'ordre del grup ortogonal de H. Per tant es verifica la igualtat h.k = g. Es nota a un element de l'àlgebra de G i a_s les seves coordenades en la base canònica.

• Es verifica la següent igualtat anomenada fórmula de Poisson:

${\frac {1}{\sqrt {h}}}\sum _{t\in H}a_{t}={\frac {1}{\sqrt {k}}}\sum _{\chi \in H^{\perp }}{\hat {a}}(\chi )\;$

Demostració

Sigui b⁰ l'element de l'àlgebra de coordenades (b_s⁰) a la base canònica de C[G] definides per les igualtats següents: $\forall s\in G\quad b_{s}^{0}=\sum _{t\in H}a_{s+t}\quad i\quad b^{0}=\sum _{s\in G}b_{s}^{0}e_{s}\;$

Les coordenades de b⁰ són constants sobre cada classe de G/H, el que permet definir un element b de l'àlgebra del grup G/H les coordenades del qual en la base canònica indexada pels elements de G/H són:

$\forall {\bar {s}}\in G/H\quad b_{\bar {s}}=b_{s}^{0}\;$

S'aplica llavors la fórmula de Plancherel en l'element b al punt de coordenades l'element nul de G/H:

$b_{\bar {0}}={\frac {1}{\sqrt {k}}}\sum _{\zeta \in {\widehat {G/H}}}{\hat {b}}(\zeta )\zeta ({\bar {0}})={\frac {1}{\sqrt {k}}}\sum _{\zeta \in {\widehat {G/H}}}{\hat {b}}(\zeta )\quad amb\quad {\hat {b}}(\zeta )={\frac {1}{\sqrt {k}}}\sum _{{\bar {t}}\in G/H}b_{\bar {t}}\zeta ({\bar {t}})^{*}\;$

La dualitat de Pontryagin mostra que existeix un únic caràcter χ de G tal tal que si t és un element de $\scriptstyle {\bar {t}}$ una classe qualsevol de G/H, llavors χ (t) és igual a ζ($\scriptstyle {\bar {t}}$). Sigui (u_i) per a i variant de 1 a k una família de representants de les classes de G/H, els coeficients de Fourier verifiquen les igualtats següents:

${\hat {b}}(\zeta )={\frac {1}{\sqrt {k}}}\sum _{{\bar {t}}\in G/H}b_{\bar {t}}\zeta ({\bar {t}})^{*}={\frac {1}{\sqrt {k}}}\sum _{i=1}^{k}b_{{\bar {u}}_{i}}\chi (u_{i})^{*}={\frac {1}{\sqrt {k}}}\sum _{i=1}^{k}\sum _{t\in H}b_{u_{i}+h}^{0}\chi (u_{i})^{*}\;$

A més, el caràcter és constant sobre cada classe de G/H, se'n dedueix:

${\hat {b}}(\zeta )={\frac {1}{\sqrt {k}}}\sum _{i=1}^{k}\sum _{t\in H}b_{u_{i}+h}^{0}\chi (u_{i}+h)^{*}={\frac {1}{\sqrt {k}}}\sum _{s\in G}a_{s}\chi (s)^{*}={\sqrt {h}}.{\hat {a}}(\chi )\;$

La dualitat de Pontryagin indica que si ζ descriu els caràcters de G/H, llavors χ descriu el grup ortogonal de H, se'n dedueix:

$b_{\bar {0}}={\frac {1}{\sqrt {k}}}\sum _{\zeta \in {\widehat {G/H}}}{\hat {b}}(\zeta )={\sqrt {\frac {h}{k}}}\sum _{\chi \in h^{\perp }}{\hat {a}}(\chi )\;$ $b_{\bar {0}}=b_{0}^{0}=\sum _{t\in H}a_{t}={\sqrt {\frac {h}{k}}}\sum _{\chi \in h^{\perp }}{\hat {a}}(\chi )\quad et\quad {\frac {1}{\sqrt {h}}}\sum _{t\in H}a_{t}={\frac {1}{\sqrt {k}}}\sum _{\chi \in H^{\perp }}{\hat {a}}(\chi )\;$ El que finalitza la demostració.

Aplicacions

Aritmètica modular

Article principal: Aritmètica modular

Històricament les primeres aplicacions dels caràcters tenen per objectiu l'aritmètica. El símbol de Legendre és un exemple de caràcter sobre el grup multiplicatiu del cos finit Z/pZ où Z on Z designa l'anell dels nombres enters i p un nombre primer senar.

Es fa servir per al càlcul dels sumatoris de Gauss o dels períodes de Gauss. Aquest caràcter és a la base d'una demostració de la llei de reciprocitat quadràtica.

Símbol de Legendre

Article principal: Símbol de Legendre

En aquest paràgraf p designa un nombre primer senar (és a dir diferent de dos). G és aquí el grup Z/pZ. El símbol de Legendre designa la funció, que en un enter a, li associa 0 si a és un múltiple de p, 1 si la classe de a és un quadrat diferent de 0 en Z/pZ i -1 si no.

• La imatge de la funció símbol de Legendre sobre el grup multiplicatiu de Z/pZ correspon al caràcter amb valor en el conjunt {-1, 1}.

En efecte, el símbol de Legendre està definit sobre Z. Aquesta funció és constant sobre les classes d'enters mòdul p, per tant està definida sobre el grup multiplicatiu de Z/pZ. Sobre aquest grup, el símbol de Legendre pren els seus valors en el conjunt {-1, 1} i és un morfisme de grup, ja que el símbol de Legendre és un caràcter de Dirichlet.

Les demostracions són a l'article associat.

Sumatori de Gauss

Article principal: Sumatori de Gauss

En la resta de l'article, F_p designa el cos finit de cardinal p on p és un nombre primer senar.

• Sigui ψ un caràcter del grup additiu (F_p, +) i χ un caràcter del grup multiplicatiu (F_p^*, .), llavors el sumatori de Gauss associat a χ i ψ és el nombre complex, aquí notat G(χ, ψ) i definit per:

$G(\chi ,\psi )=\sum _{x\in F_{p}^{*}}\chi (x).\psi (x)\;$

En termes de transformada de Fourier, es pot considerar l'aplicació que a χ li associa G(χ, ψ^*) com la transformada de Fourier del prolongament de χ a F_p per la igualtat χ(0) = 0 al grup additiu del cos i l'aplicació que a ψ li associa G(χ^*, ψ) com la transformada de Fourier de la restricció de ψ a F_p^* en el grup multiplicatiu del cos.

Els sumatoris de Gauss es fan servir abastament en aritmètica, per exemple per al càlcul dels períodes de Gauss, permeten per exemple, determinar la suma dels valors del grup dels residus quadràtics de les arrels pèssimes de la unitat i més generalment permeten determinar les arrels del polinomi ciclotòmic d'índex p.

Llei de reciprocitat quadràtica

Article principal: Llei de reciprocitat quadràtica

Els sumatoris de Gauss tenen una aplicació històrica important, la llei de reciprocitat quadràtica, s'expressa de la manera següent:

• Siguin p i q dos nombres primeres senars diferents, es verifica la igualtat següent:

$\left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{\frac {(p-1)(q-1)}{4}}$

Aquest teorema es demostra a l'article Sumatori de Gauss.

Caràcter de Dirichlet

Article principal: Caràcter de Dirichlet

Per demostrar el teorema de la progressió aritmètica, que afirma que tota classe invertible de l'anell Z/nZ conté una infinitat de nombres primers, Dirichlet generalitza els treballs de Gauss i estudia sistemàticament el grup dels caràcters del grup de les unitats d'un quocient de Z.

La utilització de la transformada de Fourier és una etapa clau de la demostració. Els caràcters de Dirichlet tenen un paper important en la teoria analítica dels nombres particularment per analitzar les arrels de la funció ζ de Rieman.

Espai vectorial finit

Un cas particular és el dels espais vectorials sobre un cos finit. Les propietats dels cossos finits permeten establir els resultats de la teoria sota una forma lleugerament diferent. Aquest cas es fa servir per exemple en teoria de la informació a través de l'estudi de les funcions booleanes, que corresponen al cas en què el cos conté dos elements. La teoria es fa servir per resoldre qüestions de criptografia sobretot per a les caixes-S, així com per als xifratges per flux. L'anàlisi harmònica sobre un espai vectorial finit intervé també en el context de la teoria dels codis i particularment per als codis lineals, per exemple per establir la identitat de MacWilliams.

Referències

• Michel Demazure Cours d'algèbre. Primalité, divisibilité, codes Cassini 1997
• Serre, Jean-Pierre. Cours d'arithmétique (en francès). 
• A. Warusfel Structures algébriques finies Hachette 1971
• G. Peyré L'algèbre discrète de la transformée de Fourier Ellipses Marketing 2004

Enllaços externs

• (francès) Dual d'un groupe fini Arxivat 2006-10-11 a Wayback Machine. per G. Peyre
• (francès) Analyse harmonique sur les groupes finis commutatifs per A. Bechata
• (francès) Mathématiques discrètes de la transformée de Fourier C. Bachoc Université de Bordeaux I