Harmonisk analyse af en begrænset abelsk gruppe

I matematik er den harmoniske analyse på en begrænset abelsk gruppe et specielt tilfælde af harmonisk analyse svarende til det tilfælde, hvor gruppen er abelsk og endelig .

Den harmoniske analyse gør det muligt at definere forestillingen om Fourier-transformation eller opløsningsprodukt . Det er rammen for mange sætninger som Plancherel , ligestillingen mellem Parseval eller dualiteten Pontryagin .

Det tilfælde, hvor gruppen er abel og endelig, er den enkleste af teorien, Fourier-transformationen er begrænset til en endelig sum, og den dobbelte gruppe er isomorf til den oprindelige gruppe.

Harmonisk analyse på en endelig abelsk gruppe har mange anvendelsesmuligheder, især i modulær aritmetik og i information teori .

Sammenhæng

I hele denne artikel betegner G en abelsk gruppe af orden g , betegnet additivt, og ℂ feltet med komplekse tal ; hvis z betegner et komplekst tal, betegner z dets konjugat .

Plads til anvendelser af G i ℂ

Sættet ℂ G på kortene over G i ℂ er forsynet med flere strukturer:

det er et komplekst vektorrum med dimension g med en kanonisk basis (δ s ) s ∈ G , hvor δ s betegner Kronecker-symbolet : δ s ( t ) er værd 1 for t = s og er værd 0 for de andre t ∈ G . Koordinaterne i denne base af et kort f er de komplekse tal f ( s ), også bemærket f s ;
dette vektorrum er kanonisk udstyret med et hermitisk produkt defineret af: $\ langle \ cdot | \ cdot \ rangle$ ${\ displaystyle \ forall f, h \ in \ mathbb {C} ^ {G}, \ quad \ langle f | h \ rangle = {\ frac {1} {g}} \ sum _ {s \ in G} { \ overline {f (s)}} h (s).}$ Dette Hermitian-produkt giver ℂ G en Hermitian-rumstruktur , bemærket ℓ 2 ( G );
dette vektorrum er også udstyret med kollisionsproduktet ∗, defineret af: ${\ displaystyle \ forall (a_ {s}) _ {s \ in G}, (b_ {t}) _ {t \ in G} \ in \ mathbb {C} ^ {G} \ quad \ left (\ sum _ {s \ i G} a_ {s} \ delta _ {s} \ højre) * \ venstre (\ sum _ {t \ i G} b_ {t} \ delta _ {t} \ højre) = \ sum _ {s, t \ in G} a_ {s} b_ {t} \ delta _ {s + t}}$ .Denne interne multiplikation udvider loven for gruppen G : δ s ∗ δ t = δ s + t . Det giver ℂ G en ℂ-algebrastruktur , kaldet den endelige gruppe algebra G og bemærkes ℂ [ G ]. Vi beviser (men det vil ikke blive brugt i denne artikel), at for enhver begrænset gruppe G (abelian eller ej) ℂ [ G ] er en semi-simpel ring .

Dobbelt gruppe

Den dobbelte gruppe af G , bemærket Ĝ , består af tegnene G , det vil sige morfismerne af G i den multiplikative gruppe ℂ *.

Det danner en multiplikativ gruppe isomorf (ikke canonically) til tilsætningsstoffet gruppe G .

Det er inkluderet i ℂ G og danne en ortonormalbasis af ℓ 2 ( G ), hvilket begrunder efterfølgende vælge hermitisk produktet på ℂ G .

Enhver begrænset abelsk gruppe er kanonisk isomorf til sin bidual (den dobbelte af sin dobbelte). Denne ejendom er generaliseret under navnet Pontryagin-dualitet .

Teori om harmonisk analyse

Bessel-Parseval lighed

Ligestillingssagen om Bessels ulighed i et hermitisk rum viser, at ethvert element

a = \ sum_ {s \ in G} a_s \ delta_s \ in \ ell ^ 2 (G)

bryder op på den ortonormale basis Ĝ i følgende form:

{\ displaystyle {\ text {noting}} \ quad a _ {\ chi} = \ langle \ chi \ mid a \ rangle = {\ frac {1} {g}} \ sum _ {s \ in G} {\ overline {\ chi (s)}} ~ a_ {s}, \ quad {\ text {på en}} \ quad a = \ sum _ {\ chi \ i {\ widehat {G}}} a _ {\ chi } \ chi \ quad {\ text {derfor}} \ quad \ | a \ | ^ {2} = \ sum _ {\ chi \ i {\ widehat {G}}} | a _ {\ chi} | ^ { 2}}

Fourier-transformation

Den Fouriertransformation af dette element af ℓ 2 ( G ) er kortet $på$

{\ displaystyle {\ widehat {a}}: {\ widehat {G}} \ til \ mathbb {C}}

defineret af:

{\ displaystyle {\ widehat {a}} (\ chi) = ga _ {\ chi} = \ sum _ {s \ in G} {\ overline {\ chi (s)}} a_ {s}}

Dette definerer et lineært kort, Fouriertransformationen ⌃: ℓ 2 ( G ) → ℂ Ĝ , hvis hovedegenskaber er beskrevet nedenfor, men som vi allerede kan bemærke, at den er bindende, da de to rum har dimensionen g, og at Bessel -Parseval lighed, omskrevet i følgende form kaldet Plancherel inversion , sikrer injektivitet:

{\ displaystyle \ forall a \ in \ ell ^ {2} (G) \ quad a = {\ frac {1} {g}} \ sum _ {\ chi \ in {\ widehat {G}}} {\ widehat {a}} (\ chi) \ chi}

Konvolutionsprodukt

Ovenstående valg om at multiplicere med i definitionen af Fourier-transformen sikrer dets kompatibilitet med sammenløbsproduktet defined, defineret i afsnittet " Kortrum af G i ℂ" ( se ovenfor ): $a_ \ chi$ $g$

Lad $a$ og $b være$ to elementer i algebraen i gruppe $G$ , Fouriertransformationen af $a * b$ er produktet af $a$ og $b$ :

{\ displaystyle \ forall a, b \ in \ mathbb {C} [G] \ quad {\ widehat {a * b}} = {\ hat {a}} \, {\ hat {b}}}

. Demonstration

${\ displaystyle {\ begin {align} \ forall \ chi \ i {\ widehat {G}} \ qquad {\ widehat {a * b}} (\ chi) & = \ sum _ {u \ in G} {\ overline {\ chi (u)}} (a * b) (u) \\ & = \ sum _ {u \ in G} {\ overline {\ chi (u)}} \ left (\ sum _ {s, t \ i G, s + t = u} a_ {s} b_ {t} \ højre) \\ & = \ sum _ {s, t \ i G} {\ overline {\ chi (s + t)}} a_ {s} b_ {t} \\ & = \ left (\ sum _ {s \ in G} {\ overline {\ chi (s)}} a_ {s} \ right) \ left (\ sum _ {t \ in G} {\ overline {\ chi (t)}} b_ {t} \ right) \\ & = {\ hat {a}} (\ chi) {\ hat {b}} (\ chi). \ slutning {justeret}}}$

Parseval lighed

Gør den lineære bijection ^: ℓ 2 ( G ) → ℂ GHG en isomorfi af hermitian rum udgør vælge om ℂ GHG den unikke Hermitisk produkt basis ( g o × ) χ∈ GHG (Fouriertransformation af det ortonormalbasis GHG ) er ortonormal. Vi spørger derfor:

{\ displaystyle \ forall f, h \ in \ mathbb {C} ^ {\ widehat {G}} \ quad \ langle f \ mid h \ rangle = {\ frac {1} {g ^ {2}}} \ sum _ {\ chi \ i {\ widehat {G}}} {\ overline {f (\ chi)}} h (\ chi)}

Bemærk, at dette Hermitian-produkt svarer til Haar-målet på Ĝ med masse 1 ⁄ g , mens det, der blev introduceret for at definere ℓ 2 ( G ), svarede til Haar-målet på G med masse 1. Vi bemærker dog ikke 2 ( Ĝ ) rummet ℂ Ĝ leveres med ovennævnte Hermitian-produkt. Vi opnår således:

Med ovenstående definition af ℓ 2 ( Ĝ ) transformerer Fourier

\ widehat {}: \ ell ^ 2 (G) \ to \ ell ^ 2 (\ widehat G)

er en isomorfisme af hermitiske rum. Især kontrollerer den følgende lighed, kendt som Parseval :

{\ displaystyle \ forall a, b \ in \ ell ^ {2} (G) \ quad \ langle {\ hat {a}} | {\ hat {b}} \ rangle _ {\ ell ^ {2} ({ \ hat {G}})} = \ langle a | b \ rangle _ {\ ell ^ {2} (G)}}

Orthogonal af en undergruppe

Er H en undergruppe af G , skal vi kalde ortogonale gruppe af H , og betegner H ⊥ , undergruppen af GHG , der består af tegn, hvis kerne indeholder H .

Ifølge isomorfismesætninger :

H ⊥ er isomorf til den dobbelte af kvotienten gruppe G / H .Faktisk H ⊥ er det sæt af karakterer af G , som er multipliceret med G / H , så dette er billedet af den kanoniske indlejring af den dobbelte af G / H i den for G . Dette tilvejebringer det første bevis, at H ⊥ er en undergruppe af GHG , og også viser, at kendelsen er lig med kvotienten af størrelsesordenen G ved den af H .
Kvotientgruppen Ĝ / H ⊥ er isomorf til Ĥ .Faktisk H ⊥ er kernen af den kanoniske restriktion morphism, fra GHG i H , som tilvejebringer en injektiv morphism fra G / H ⊥ i H , og dette morphism er også Surjective ved en kardinalitet argument.

De to udsagn ovenfor kan også udledes af rigtigheden af sekvensen på grund af injektionsevnen af den delbare gruppe ℂ * . ${\ displaystyle 0 \ til {\ widehat {G / H}} \ til {\ widehat {G}} \ til {\ widehat {H}} \ til 0}$

Poisson summeringsformel

Er H en undergruppe af orden h af G . Ethvert element i ℓ 2 ( G ) opfylder følgende Poisson-summeringsformel : $på$

{\ displaystyle g \ sum _ {t \ in H} a_ {t} = h \ sum _ {\ chi \ in H ^ {\ perp}} {\ hat {a}} (\ chi)}

. Demonstration

{\ displaystyle g \ sum _ {t \ in H} a_ {t} = g ^ {2} \ langle \ sum _ {t \ in H} \ delta _ {t} \ mid a \ rangle _ {\ ell ^ {2} (G)} = \ sum _ {t \ in H} g ^ {2} \ langle {\ widehat {\ delta _ {t}}} \ mid {\ hat {a}} \ rangle _ {\ ell ^ {2} ({\ hat {G}})} = \ sum _ {t \ i H, \ chi \ i {\ widehat {G}}} {\ overline {{\ widehat {\ delta _ {t }}} (\ chi)}} {\ hat {a}} (\ chi) = \ sum _ {\ chi \ i {\ widehat {G}}} c _ {\ chi} {\ hat {a}} (\ chi)}

med

{\ displaystyle c _ {\ chi} = \ sum _ {t \ in H} \ chi (t) = h \ langle 1 \ mid \ chi _ {| H} \ rangle _ {\ ell ^ {2} (H )} = {\ begin {cases} h \ quad {\ text {si}} \ quad \ chi _ {| H} = 1 \\ 0 \ quad {\ text {ellers.}} \ end {cases}}}

Imidlertid er begrænsningen af χ til H lig med tegnet 1 over H, hvis og kun hvis χ hører til det ortogonale af H , som afslutter beviset.

Ansøgninger

Modulær aritmetik

De første historiske anvendelser af tegn var til aritmetik. Den Legendre symbolet er et eksempel på et tegn på det multiplikative gruppe af finite felt F p = ℤ / p ℤ hvor ℤ betegner ringen af relative heltal og p et ulige primtal .

Det bruges til beregning af Gaussiske summer eller Gaussiske perioder . Denne karakter er grundlaget for et bevis på loven om kvadratisk gensidighed .

Legendre symbol

I dette afsnit betegner p et ulige primtal. G er her gruppen ℤ / p ℤ. Legendre-symbolet angiver den funktion, som til et heltal a associerer 0, hvis a er et multiplum af p , associerer 1, hvis klassen a i F p er et ikke-nul kvadrat, og associerer -1 ellers.

Billedet af Legendre-symbolfunktionen på multiplikationsgruppen F p svarer til tegnet med værdier i sættet {-1, 1}.

Faktisk er Legendre-symbolet defineret på ℤ. Denne funktion er konstant på heltalsklasserne modulo p ; det er derfor defineret på det multiplikative gruppe af F s . På denne gruppe tager symbolet for Legendre sine værdier i sættet {-1, 1} og er en morfisme af grupper, fordi symbolet for Legendre er en karakter af Dirichlet .

Demonstrationer er givet i den tilknyttede artikel.

Gaussisk sum

I den resterende del af artiklen er p et ulige primtal.

Lad ψ være et tegn på additivgruppen ( F p , +) og χ et tegn på den multiplikative gruppe ( F p * ,. ), Så er Gauss-summen forbundet med associated og ψ det komplekse tal, her bemærket G (χ , ψ) og defineret af:

{\ displaystyle G (\ chi, \ psi) = \ sum _ {x \ i F_ {p} ^ {*}} \ chi (x) \ psi (x)}

Med hensyn til Fourier-transformationen kan vi overveje det kort, som χ forbinder G (χ, ψ ) som Fourier-transformationen af forlængelsen af χ til F p med ligestillingen χ (0) = 0 i den additive feltgruppe og kortet, som til ψ forbinder G ( χ , ψ) som Fourier-transformation af begrænsningen fra ψ til F p * i feltets multiplikative gruppe.

Gaussiske summer bruges i vid udstrækning i aritmetik, for eksempel til beregning af gaussiske perioder . De gør det især muligt at bestemme summen af værdierne for gruppen af kvadratiske rester af enhedens p- th rødder og mere generelt at bestemme rødderne til det cyklotomiske polynom af indeks p .

Kvadratisk gensidighedslov

Gaussiske summer har en vigtig historisk anvendelse: den kvadratiske gensidighedslov, som udtrykkes som følger:

Hvis p og q er to forskellige ulige primtal, så

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

Denne sætning er demonstreret i artiklen Gaussian Sum .

Dirichlet karakter

For at demonstrere sætningen af aritmetisk progression , hævder, at enhver inverterbar klasse af ringen ℤ / n ℤ indeholder en uendelighed af primtal, generaliserer Dirichlet Gauss 'arbejde og systematisk studerer gruppen af tegn i gruppen af invertibler i en sådan ring.

Brugen af Fourier-transformationen er et nøgletrin i beviset. De tegn af Dirichlet har en vigtig rolle i den analytiske teori af tallene især at analysere rødderne i funktion ζ af Riemann .

Specielt tilfælde: begrænset vektorplads

Et særligt tilfælde er vektorrum på et begrænset felt . Egenskaberne ved begrænsede felter gør det muligt at etablere resultaterne af teorien i en lidt anden form. Dette tilfælde anvendes for eksempel i information teori gennem studiet af Boolske funktioner , svarende til det tilfælde, hvor kroppen indeholder to elementer. Teorien bruges til at løse kryptologispørgsmål , især for S-bokse såvel som til streamkodere . Harmonisk analyse på et endeligt vektorrum griber også ind i sammenhængen med kodeteori og især for lineære koder , for eksempel for at fastslå identiteten af MacWilliams .

Dualitet af Pontryagin

For enhver lokalt kompakt abelsk gruppe G er den kanoniske injektionsmorfisme af G i dens bidual bijektiv. Hvis G er en endelig abelsk gruppe, er der endda (ikke-kanoniske) isomorfier af G i dens dobbelte . I det særlige tilfælde hvor G er additivgruppen i et begrænset vektorrum, det vil sige en elementær abelisk gruppe (en) , kan nogle af disse isomorfier konstrueres som følger.

Grundlæggende isomorfisme

På ethvert endeligt dimensionelt vektorrum V , en bilinær form〈| 〉 Er ikke degenereret, hvis og kun hvis Model: Bilinær form af V i sit dobbelte rum V *.

I denne artikel betegner V et vektorrum med begrænset dimension n over et endeligt felt F q i kardinal q . Symbolet betegner den dobbelte gruppe af V , χ 0 en ikke-triviel karakter af additivgruppen F q og 〈| > Bilineær degenereret form på V . ${\ displaystyle {\ hat {V}}}$

Ved kun at overveje dets additive gruppe af vektorrummet V * har vi:

Den morphism af grupper er en isomorfi . ${\ displaystyle V ^ {*} \ til {\ hat {V}}, f \ mapsto \ chi _ {0} \ circ f}$

Denne morfisme er faktisk injektiv, fordi den har en triviel kerne , da hvis f er en ikke-nul lineær form og derfor surjectiv , så er tegnet χ 0 ∘ f ligesom χ 0 , ikke-trivielt. De to grupper har samme rækkefølge q n , denne injektionsmorfisme er bijektiv .

Efter sammensætning udleder vi:

Morfismen af grupper defineret af ${\ displaystyle U: V \ til {\ hat {V}}}$

{\ displaystyle \ forall x, y \ i V \ quad U_ {x} (y) = \ chi _ {0} (\ langle x \ mid y \ rangle)}

er en isomorfisme.

Orthogonalitet i forhold til Pontryagin-dualitet

Lad S en delmængde af V . Som i det generelle tilfælde af et finit abelsk gruppe , den vinkelrette S er undergruppen S ⊥ af bestående af tegn, hvis kernen indeholder S . Vi definerer også den ortogonale af S relativt til den Pontryagin dobbelthed forbundet med (χ 0 , <|>) som undergruppe S °: = U -1 ( S ⊥ ) af V : ${\ displaystyle {\ hat {V}}}$

{\ displaystyle S ^ {\ circ} = \ {x \ i V \ mid \ forall y \ i S \ quad \ chi _ {0} (\ langle x \ mid y \ rangle) = 1 \}}

Vi bemærker, at:

det ortogonale til venstre for S i forhold til den bilineære form er et vektors underrum af V inkluderet i undergruppen S °. Det er lig med det, så snart χ 0 er injektionsdygtig - det vil sige så snart q er prime - men også så snart S er et vektorunderrum;
hvis den bilineære form 〈| 〉 Er symmetrisk eller antisymmetrisk, S ° ° er undergruppen genereret af S ; faktisk er denne undergruppe H inkluderet i H °°, men rækkefølgen | H ° | = | H ⊥ | af H ° er lig med | V | / | H | og tilsvarende | H °° | er lig med | V | / | H ° | derfor til | H | så H = H ° ° = S °°.

Fourier-transformation

En endelig gruppes algebra betegnes ℂ [ G ]. The Fourier transformation , af ℂ [ G ] i ℂ [ GHG ] er den lineære bijection defineret ved: . Den Plancherel formel er , og hvis (,) G betegner hermitian kanoniske produkt af den komplekse vektorrum ℂ [ G ], den parsevals identitet kan skrives . ${\ displaystyle {\ widehat {a}} (\ chi): = \ sum _ {y \ i G} {\ overline {\ chi (y)}} a (y)}$ ${\ displaystyle a = {\ frac {1} {g}} \ sum _ {\ chi \ i {\ widehat {G}}} {\ widehat {a}} (\ chi) \ chi}$ ${\ displaystyle ({\ hat {a}} | {\ hat {b}}) _ {\ widehat {G}} = | G | ~ (a | b) _ {G}}$

I tilfældet G = V gør isomorfismen U ovenfor af V i sin dobbelte gruppe det muligt at transportere denne Fourier-transformation til et kort over of [ V ] i ℂ [ V ], også kaldet Fourier-transformation og igen bemærket ^ :

{\ displaystyle \ forall a \ in \ mathbb {C} [V] \ quad \ forall x \ in V \ quad {\ hat {a}} (x): = {\ hat {a}} (U (x) ) = \ sum _ {y \ i V} a (y) \ chi _ {0} (- \ langle x \ mid y \ rangle)}

Parsevals lighed omskrives derefter:

{\ displaystyle \ forall a, b \ in \ mathbb {C} [V] \ quad ({\ hat {a}} \ mid {\ hat {b}}) = q ^ {n} (a \ mid b) }

og Plancherels formel:

{\ displaystyle \ forall a \ in \ mathbb {C} [V] \ quad \ forall y \ in V \ quad a (y) = {\ frac {1} {q ^ {n}}} \ sum _ {x \ in V} {\ widehat {a}} (x) \ chi _ {0} (\ langle x \ mid y \ rangle)}

Poisson summeringsformel

Hvis W er en undergruppe af V og et element af ℂ [ V ], tager Poissons summeringsformel følgende form: $på$

{\ displaystyle \ sum _ {w \ in W} a (w) = {\ frac {1} {| W ^ {\ circ} |}} \ sum _ {w ^ {\ circ} \ in W ^ {\ cirk}} {\ hat {a}} (w ^ {\ circ})}

Ansøgninger

Boolsk funktion

Der er et særligt tilfælde, at når vektorrummet er binær, dvs. på banen med to elementer F 2 . I denne sammenhæng er der kun en ikke-triviel karakter, den der forbinder –1 med enhed. Fourier-transformeringen tager derefter en enkel form og bærer navnet Walsh-transform .

Det har mange anvendelser inden for kodeteori . Det bruges for eksempel i kryptografi for at sikre sikkerheden af en besked med en S-boks i tilfælde af algoritmer til kryptering symmetrisk .

MacWilliams identitet

Harmonisk analyse af endelige vektorrum bruges også til korrektionskoder , især i sammenhæng med lineære koder .

MacWilliams 'identitet er et eksempel; den forbinder tællerpolynomet af vægte, det vil sige fordelingen af Hamming-vægte , af en lineær kode og dens dobbelte. Det bruges til undersøgelse af koder som Hamming .

Se også

Denne artikel er helt eller delvist taget fra artiklen " Harmonisk analyse på et endeligt vektorrum " (se listen over forfattere ) .

Relaterede artikler

Eksternt link

C. Bachoc, Discrete Mathematics of the Fourier Transform , University of Bordeaux I
A. Bechata, " Harmonisk analyse af kommutative endelige grupper " , s. 10-11
Anthony Carbery, " Harmonic Analysis on Vector Spaces over Endite Fields " , s. 4-5.

Arbejder

Michel Demazure , Algebra forløb: primality, divisibility, codes [ detail of editions ]
André Warusfel , Endelige algebraiske strukturer , Hachette, 1971
Gabriel Peyré, Fourier-transformets diskrete algebra , Ellipses , 2004