Primjene Fourierove analize na konačnim komutativnim grupama

Vjekoslav Kovač2 Ljudevit Palle3

 


Sažetak. U ovom članku izlažu se osnove Fourierove analize na konačnim Abelovim grupama. Potom se dobiveni rezultati primjenjuju na raznovrsne zadatke u različitim matematičkim granama: (linearnoj) algebri, geometriji ravnine, elementarnoj teoriji brojeva i (aditivnoj) kombinatorici.


 

 



1Fourierova transformacija

Fourierova analiza je opsežna matematička disciplina koja se razvila iz razmatranja J.-B. J. Fouriera (1768–1830) o razvojima u redove sastavljene od trigonometrijskih funkcija, inicijalno u kontekstu proučavanja jednadžbe provođenja topline. Već oko dvije stotine godina njezina mnogobrojna pitanja intrigiraju poznate matematičare, a i danas se nalaze nove zanimljive primjene teorijskih rezultata. Svrha ovog članka je čitatelju približiti jedan aspekt Fourierove analize na konačnim strukturama, koji ne iziskuje neko posebno predznanje, za razliku od općenite teorije. Tako se već čitatelj sa znanjem srednjoškolske matematike može uvesti u ovo područje, a natjecatelji mogu naučiti poneki trik za rješavanje prilično teških zadataka.

Za prirodni broj d označimo sa d skup ostataka pri dijeljenju s d, tj.

 
d:={0,1,2,3,,d-2,d-1}.
 

Na skupu d se podrazumijevaju operacije zbrajanja i množenja modulo d, tj. nakon izvršenog zbrajanja ili množenja još podijelimo rezultat s d i uzmemo samo ostatak pri dijeljenju. Tako npr. na 4 imamo sljedeće tablice zbrajanja i množenja.
 



+ 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 2

0 1 2 3
0 0 0 0 0
1 0 1 2 3
2 0 2 0 2
3 0 3 2 1

Fiksirajmo sada n i brojeve d1,,dn{1}. Kada pišemo

 
(1)
A=d1d2dn,
 

tada smatramo da je A Kartezijev produkt skupova d1,,dn na kojem se promatra zbrajanje po koordinatama. Drugim riječima, elementi od A su n-torke x=(x1,x2,,xn) koje se zbrajaju kao:

 
(x1,x2,,xn)+(y1,y2,,yn):=(x1+y1,x2+y2,,xn+yn).
 

Često pišemo samo 0 umjesto n-torke samih nula, (0,0,,0). Tako je npr. operacija zbrajanja na 22 opisana sljedećom tablicom.
 



+ (0,0) (0,1) (1,0) (1,1)
(0,0) (0,0) (0,1) (1,0) (1,1)
(0,1) (0,1) (0,0) (1,1) (1,0)
(1,0) (1,0) (1,1) (0,0) (0,1)
(1,1) (1,1) (1,0) (0,1) (0,0)

Čitatelj upoznat s pojmom grupe odmah će prepoznati da je gore opisana struktura (A,+) primjer konačne komutativne (ili Abelove) grupe. Obratno, poznato je da svaka konačna komutativna grupa ima strukturu (1) za određene parametre n i d1,,dn. Zato mi i ne moramo raditi s općenitim grupama, veće upravo s grupama A danima formulom (1).

Definirajmo preslikavanje E:A×A formulom

 
E(x,ξ):=(e2πi/d1)x1ξ1(e2πi/d2)x2ξ2(e2πi/dn)xnξn
 

za svake n-torke x=(x1,x2,,xn) i ξ=(ξ1,ξ2,,ξn) iz A. Primijetimo da E poprima vrijednosti u kompleksnim brojevima modula 1. Jedini razlog zašto lijevi argument pišemo latiničnim slovom x, a desni grčkim slovom ξ, je kako bismo naglasili da se oni nalaze u dvije različite kopije od A, povezane preslikavanjem E.

Propozicija 1. Preslikavanje E ima sljedeća svojstva (za svaki izbor od x,y,ξ,ζA):
 
E(x+y,ξ)=E(x,ξ)E(y,ξ),   E(x,ξ+ζ)=E(x,ξ)E(x,ζ),
 
E(0,ξ)=1,   E(x,0)=1,   E(-x,ξ)=E(x,ξ)¯,   E(x,-ξ)=E(x,ξ)¯,
 
xAE(x,ξ)=|A|ako je ξ=0,0ako je ξ0,      ξAE(x,ξ)=|A|ako je x=0,0ako je x0.
 


Napomenimo da sa |S| označavamo broj elemenata konačnog skupa S.

Proof. Prvih šest formula su direktne posljedice definicije od E, dok su posljednje dvije ekvivalentne radi simetričnosti iste definicije obzirom na x i ξ. Dokažimo zadnju navedenu formulu.

Za fiksirani x=(x1,x2,,xn) sumiranjem po svim mogućnostima koordinata od ξ=(ξ1,ξ2,,ξn) dobivamo
 
(2)
ξAE(x,ξ)=(ξ1=0d1-1(e2πix1/d1)ξ1)(ξn=0dn-1(e2πixn/dn)ξn).
 
Preostaje primijetiti da za xj0 vrijedi e2πixj/dj1 pa formula za parcijalnu sumu geometrijskog reda daje
 
ξj=0dj-1(e2πixj/dj)ξj=1-e2πixj1-e2πixj/dj=1-11-e2πixj/dj=0,
 
dok za xj=0 imamo
 
ξj=0dj-1(e2πixj/dj)ξj=ξj=0dj-11=dj.
 
Produkt iz (2) nije jednak 0 samo kada je x1==xn=0 i tada je jednak d1dn=|A|.
     

Definicija 2. Fourierova transformacija funkcije f:A je nova funkcija fˆ:A definirana formulom
 
fˆ(ξ):=xAf(x)E(x,ξ)   za svaki ξA.
 

Primjer 3. (a) Ako je A=4 i ako funkcije na A pišemo kao uređene četvorke
 
f=(f0,f1,f2,f3),
 
tada je
 
fˆ=(f0+f1+f2+f3, f0+if1-f2-if3, f0-f1+f2-f3, f0-if1-f2+if3).
 
(b) Ako je A=22 i ako funkcije na A pišemo kao uređene četvorke
 
f=(f0,0,f0,1,f1,0,f1,1),
 
tada je
 
fˆ=(f0,0+f0,1+f1,0+f1,1, f0,0-f0,1+f1,0-f1,1, f0,0+f0,1-f1,0-f1,1, f0,0-f0,1-f1,0+f1,1).
 


Osnovna svojstva Fourierove transformacije dana su u sljedećem teoremu.

Teorem 4.
[(a)] Vrijedi tzv. formula inverzije:
 
f(x)=1|A|ξAfˆ(ξ)E(x,ξ)¯   za svaki xA.
 
Njom se polazna funkcija f:A može rekonstruirati iz svoje Fourierove transformacije. Posebno, Fourierova transformacija je injektivna, tj. fˆ=gˆ implicira f=g.
[(b)] Vrijedi Plancherelov identitet:
 
ξA|fˆ(ξ)|2=|A|xA|f(x)|2
 
i općenitije:
 
ξAfˆ(ξ)gˆ(ξ)¯=|A|xAf(x)g(x)¯
 
za proizvoljne funkcije f,g:A.
[(c)] Ako je funkcija h:A definirana kao tzv. konvolucija funkcija f,g:A,
 
h(x):=y,zAy+z=xf(y)g(z)   za svaki xA,
 
što pišemo h=f*g, tada vrijedi
 
hˆ(ξ)=fˆ(ξ)gˆ(ξ)   za svaki ξA.
 
Drugim riječima, Fourierova transformacija prevodi konvoluciju u obični produkt.
[(d)] Za funkciju f:A te za y,ζA definiramo nove funkcije Tyf,Mζf:A formulama
 
(Tyf)(x):=f(x-y),   (Mζf)(x):=E(x,ζ)f(x)   za svaki xA.
 
Njihove Fourierove transformacije su dane sa
 
(Tyfˆ)(ξ)=E(y,ξ)fˆ(ξ),   (Mζfˆ)(ξ)=fˆ(ξ+ζ)   za svaki ξA.
 
Slova T i M dolaze od riječi translacije i modulacije.
[(e)] Fourierova transformacija je linearna, tj.
 
αf+βgˆ=αfˆ+βgˆ.
 

Proof. (a) Navedena formula je naprosto posljedica zamjene poretka u dvostrukoj sumaciji i svojstava od E iz propozicije 1:
 
ξAfˆ(ξ)E(x,ξ)¯=ξAyAf(y)E(y,ξ)E(x,ξ)¯=yAf(y)ξAE(y-x,ξ)=|A|f(x).
 
(b) Slično kao i u prethodnom dijelu, zamjena redoslijeda sumiranja daje:
 
ξAfˆ(ξ)gˆ(ξ)¯=ξAx,yAf(x)g(y)¯E(x,ξ)E(y,ξ)¯=x,yAf(x)g(y)¯ξAE(x-y,ξ)=|A|xAf(x)g(x)¯.
 
(c) Sumiranjem po x i rastavljanjem E(x,ξ)=E(y,ξ)E(z,ξ) dobivamo:
 
hˆ(ξ)=xA(y,zAy+z=xf(y)g(z))E(x,ξ)=y,zAf(y)E(y,ξ) g(z)E(z,ξ)=(yAf(y)E(y,ξ))(zAg(z)E(z,ξ))=fˆ(ξ)gˆ(ξ).
 
(d) Ovo su također direktne posljedice definicija i propozicije 1:
 
(Tyfˆ)(ξ)=xAf(x-y)E(x,ξ)=xAf(x)E(x+y,ξ)=xAf(x)E(x,ξ)E(y,ξ)=E(y,ξ)fˆ(ξ),(Mζfˆ)(ξ)=xAf(x)E(x,ζ)E(x,ξ)=xAf(x)E(x,ζ+ξ)=fˆ(ζ+ξ).
 
(e) Ovdje jedino treba rastaviti konačnu sumu na dijelove koji se tiču funkcija f i g redom:
 
(αf+βgˆ)(ξ)=xA(αf(x)+βg(x))E(x,ξ)=αxAf(x)E(x,ξ)+βxAg(x)E(x,ξ)=αfˆ(ξ)+βgˆ(ξ). 
 

2Primjene u algebri

Već i dosad navedeni koncepti dovoljni su za maštovite primjene na raznolike probleme. Započinjemo s nekoliko jednostavnijih primjera iz linearne algebre ili algebre polinoma.

Zadatak 5. Koliko se najviše može odabrati međusobno ortogonalnih vektora iz 1024 čije su sve koordinate iz skupa {-1,1}?


Napomenimo da su vektori u,vn, u=(u1,,un), v=(v1,,vn) ortogonalni ili okomiti ako i samo ako je njihov skalarni produkt jednak 0, tj. vrijedi uv=j=1nujvj=0. Za kompleksne vektore u,vn definicija ortogonalnosti ostaje ista, osim što skalarni produkt postaje uv=j=1nujvj¯.

Rješenje.. U euklidskom prostoru n može postojati najviše n u parovima ortogonalnih ne-nul vektora. Zato će u našem zadatku odgovor biti 1024 ako još pronađemo primjer koji ima točno 1024 vektora.

Promotrimo grupu A=210=2210; ona očigledno ima 210=1024 elemenata. Za svaki xA promotrimo vektor
 
(3)
ux:=(E(x,ξ):ξA)
 
duljine |A|=1024. Kako se u formuli za E sada pojavljuju samo drugi korijeni iz jedinice (tj. samo potencije od -1), zaključujemo da sve koordinate tog vektora pripadaju skupu {-1,1}. Primjenom propozicije 1 odmah se vidi da su vektori ux međusobno ortogonalni:
 
(4)
uxuy=ξAE(x,ξ)E(y,ξ)¯=ξAE(x-y,ξ)=0
 
ako je xy.
     


Slika 1: Međusobno ortogonalni ±1 vektori iz 8.


Pogledajte sliku 1 za analogni primjer u 23-dimenzionalnom euklidskom prostoru; vektori su ovdje zapisani kao stupci. Naziru se fraktalni uzorci, koji nisu slučajni, već su posljedica rekurzivnih relacija što ih zadovoljava preslikavanje E za grupe A=2n.

Zadatak 6. Neka je v=(v0,v1,...,vm-1)m vektor kojeg možemo shvatiti kao funkciju na m i pretpostavimo da vrijedi vˆ(ξ)0 za svaki ξ=0,1,,m-1. Dokažite da je sistem cikličkih permutacija od v linearno nezavisan.


Pod cikličkim permutacijama od v smatramo vektore

 
(vj,vj+1,,vm-1,v0,v1,,vj-1)
 

za j=0,1,,m-1. Prisjetimo se i da je sistem vektora w1,w2,,wn linearno nezavisan ako činjenica k=1nαkwk=0 za neke skalare α1,α2,,αn implicira da svi ti skalari moraju biti jednaki 0. Pritom 0 označava nul-vektor u odgovarajućem vektorskom prostoru.

Rješenje.. Ovog puta radimo s kompleksnim funkcijama na grupi A=m. Uočimo da je gornji ciklički permutirani vektor upravo T-jv, pri čemu opet koristimo notaciju iz (d) dijela teorema 4. Prema tome, trebamo pokazati da su funkcije T0v, T1v, \ldots, Tm-1v linearno nezavisne. Pretpostavimo da su α0,α1,,αm-1 skalari takvi da je j=0m-1αjTjv=0. Zbog linearnosti Fourierove transformacije i (d) dijela teorema 4, za svaki ξ=0,1,,m-1 vrijedi
 
0=j=0m-1αj(Tjvˆ)(ξ)=(j=0m-1αjE(j,ξ))vˆ(ξ)
 
pa po pretpostavci mora biti
 
j=0m-1αjE(j,ξ)=0,   tj. xAαxux=0,
 
pri čemu su ux:A, ux(ξ):=E(x,ξ) funkcije koje poistovjećujemo s vektorima danima formulom (3). Istim računom (4) kao u prethodnom zadatku provjeri se da su ti vektori u parovima ortogonalni. Zato su oni pogotovo i linearno nezavisni pa je α0=α1==αm-1=0, čime je dokazana tražena tvrdnja.
     


Čitatelju ostavljamo dva zadatka za vježbu.

Zadatak 7. Promotrite sve matrice tipa 2n×2n (gdje je n prirodan broj) s elementima iz skupa {-1,1}. Pronađite najveću moguću vrijednost determinante jedne od takvih matrica.

Uputa.. Potražite Hadamardovu nejednakost [5], koja će vam dati gornju ogradu za takve matrice A reda N=2n:
 
detANN/2=2n2n-1.
 
Sada konstruirajte primjer kada se postiže jednakost koristeći račun iz zadatka 5.
Analogni problem je uvelike otvoren za matrice reda N koji nije potencija broja 2 i zove se Hadamardov problem.
     

Zadatak 8. Faktorizirajte polinom 5 varijabli,
 
P(x0,x1,x2,x3,x4)=j=04xj5+5j=04xj-1xjxj+1(xj-1xj+1-xj2)  +5j=04xj-2xjxj+2(xj-2xj+2-xj2)-5x0x1x2x3x4,
 
na faktore s koeficijentima iz prstena
 
[e2πi/5]={j=04αje2πij/5:α0,α1,α2,α3,α4}.
 


Napomenimo da se zbrajanje i oduzimanje indeksâ u formuli za P shvaćaju modulo 5.

Uputa.. Označite kratko ε=e2πi/5 i shvatite vektor varijabli x=(x0,x1,x2,x3,x4) kao funkciju na 5. Korištenjem formule inverzije nakon duljeg računa dobiva se
 
P(x0,x1,x2,x3,x4)=j=04xˆ(j)=j=04(x0+εjx1+ε2jx2+ε3jx3+ε4jx4).     
 

3Primjene u geometriji

U ovom odjeljku bavimo se primjenama u planimetriji, tj. geometriji ravnine. Autor sljedećeg zadatka je M. Roseman, a dolje opisano elegantno rješenje korištenjem Fourierove analize predložio je I. J. Schoenberg [8].

Zadatak 9. Neka je n, n3. Definiramo niz n-terokuta (Mk)k=0,
 
Mk=A0kA1kAn-1k,
 
u ravnini na sljedeći način. Neka je M0 proizvoljan. Za k1 vrhovi
 
A0k,A1k,,An-2k,An-1k
 
mnogokuta Mk rekurzivno su definirani kao polovišta stranica
 
A0k-1A1k-1¯, A1k-1A2k-1¯, , An-2k-1An-1k-1¯, An-1k-1A0k-1¯
 
mnogokuta Mk-1. Dokažite da se mnogokuti (Mk)k=0 “stišču” prema točki, tj. preciznije, da vrijedi
 
limkAjk=T
 
za j=0,1,,n-1, pri čemu je T težište od M0.


Slika 2: Niz peterokuta koji se stišče prema zajedničkom težištu.


Rješenje.. Pogledajte sliku 2 za ilustraciju nekoliko iteracija u slučaju n=5.

Uvedimo kompleksni koordinatni sustav u ravnini s ishodištem u točki T i neka je zj(k) koordinata točke Ajk. Shvatimo vektor
 
fk=(z0(k),z1(k),,zn-2(k),zn-1(k))
 
kao kompleksnu funkciju na grupi A=n. Rekurzivnu relaciju možemo zapisati
 
zj(k)=12zj(k-1)+12zj+1(k-1)    za j=0,1,,n-1,
 
pri čemu indekse zbrajamo modulo n, što se još kompaktnije zapisuje
 
fk=12fk-1+12T-1fk-1,
 
uz notaciju iz (d) dijela teorema 4. Korištenjem tog istog teorema dobivamo relaciju između Fourierovih transformacija:
 
fˆk(ξ)=12fˆk-1(ξ)+12E(-1,ξ)fˆk-1(ξ)=12(1+e-2πiξ/n)fˆk-1(ξ)=e-πiξ/n12(eπiξ/n+e-πiξ/n)fˆk-1(ξ)=e-πiξ/ncosπξnfˆk-1(ξ),
 
odakle je
 
|fˆk(ξ)|=|cosπξ||fˆk-1(ξ)|
 
pa iteriranjem dobivamo
 
(5)
|fˆk(ξ)|=|cosπξn|k|fˆ0(ξ)|.
 

Po konstrukciji je
 
fˆ0(0)=z0(0)+z1(0)++zn-2(0)+zn-1(0)=0
 
pa prema (5) slijedi fˆk(0)=0 za svaki k0. S druge strane, za ξ=1,2,,n-1 imamo |cosπξn|<1 te radi (5) postoji limes limk|fˆk(ξ)| i iznosi 0. Konačno, Plancherelov identitet iz teorema 4 daje
 
limkjn|zj(k)|2=1nlimkξn|fˆk(ξ)|2=0,
 
što znači limkzj(k)=0 za j=0,1,,n-1.
     


Zadatak kojeg ostavljamo za vježbu čitatelju prilično je težak pa dajemo i detaljnu uputu. Kao problem ga je postavio A. Björner, a riješili su ga D. Svrtan, D. Šterc i I. Urbiha u članku [9], odakle je zadatak i preuzet.

Zadatak 10. Neka su z0,z1,z2,z3,z4 kompleksni brojevi za koje vrijedi
[(i)] |z0|=|z1|=|z2|=|z3|=|z4|=1,
[(ii)] z0+z1+z2+z3+z4=0,
[(iii)] z0z1+z1z2+z2z3+z3z4+z4z0=0.
Dokažite da oni leže u vrhovima pravilnog peterokuta.

Uputa.. Petorku kompleksnih brojeva (z0,z1,z2,z3,z4) shvatite kao funkciju f na grupi 5 i neka je njena Fourierova transformacija fˆ=(w0,w1,w2,w3,w4). Iz drugog uvjeta zaključite w0=fˆ(0)=0 te potom iz prvog uvjeta i svojstava Fourierove transformacije izvedite
 
w2w1¯+w3w2¯+w4w3¯=0,      w3w1¯+w4w2¯+w1w4¯=0.
 
Treći uvjet u zadatku se pak primjenom formule inverzije i w0=0 transformira u
 
w1w4cos2π5+w2w3cos\textstyle4π5=0,   tj. (5-1)w1w4=(5+1)w2w3.
 
Iz dobivenih jednakosti lako slijedi
 
|w2|((5-1)|w1|2+(5+1)|w3|2)=(5-1)|w1||w2||w3|.
 
Diskutiranjem slučajeva zaključite da je najviše jedan od brojeva w1,w2,w3,w4 različit od 0. Preostat će iskoristiti formulu inverzije.
     

4Primjene u teoriji brojeva

Autor sljedećeg rezultata je J. Bourgain [1], a njegov dokaz je preuzet iz knjige [11].

Zadatak 11. Neka je p prost broj i S{1,2,3,,p-1} skup takav da je |S|>p3/4. Dokažite da za svaki cijeli broj m postoje a1,a2,b1,b2,c1,c2S takvi da vrijedi
 
ma1a2+b1b2+c1c2 (mod \(p\)).
 

Rješenje.. Koristeći operacije modulo p vidimo da zapravo treba svaki xp prikazati kao
 
x=a1a2+b1b2+c1c2
 
za neke a1,a2,b1,b2,c1,c2Sp. Zbog činjenice da je p prost, za svake s,yp, s0 jednadžba sx=y ima jedinstveno rješenje xp. Drugim riječima, za svaki sp{0} funkcija pp, xsx je bijekcija. Tu ćemo tvrdnju višestruko koristiti kod zamjene indeksa sumacije.

Promotrimo funkciju f:p, f:=sSχsS, gdje χT označava karakterističnu funkciju skupa T te pišemo sS={sx:xS}. Najprije primijetimo da je
 
(f*f*f)(x)=a,b,cpa+b+c=xf(a)f(b)f(c)=a1,b1,c1Sa,b,cpa+b+c=xχa1S(a)χb1S(b)χc1S(c)=a=a1a2b=b1b2c=c1c2=a1,b1,c1Sa2,b2,c2Sa1a2+b1b2+c1c2=x1  = broj traženih prikaza od x
 
pa zapravo trebamo dokazati da je (f*f*f)(x)>0 za svaki xp.

Fourierova transformacija od f je
 
fˆ(ξ)=sSxpχsS(x)e2πixξ/p=[x=sy]=sSySe2πisyξ/p=sSχˆS(sξ).
 
Imamo fˆ(0)=|S|χˆS(0)=|S|2. Za ξ0 su elementi sξ svi međusobno različiti kako s varira pa aritmetičko-kvadratna nejednakost i Plancherelov identitet daju
 
|fˆ(ξ)||S|1/2(sS|χˆS(sξ)|2)1/2|S|1/2(ξp|χˆS(ξ)|2)1/2=|S|1/2(pxp|χS(x)|2)1/2=|S|1/2p1/2|S|1/2=p1/2|S|.
 
Zbog nejednakosti Minkowskog (tj. nejednakosti trokuta u euklidskom prostoru pp2p) imamo
 
(ξp|fˆ(ξ)|2)1/2sS(ξp|χˆsS(ξ)|2)1/2=sSp1/2(xp|χsS(x)|2)1/2=|S|p1/2|S|1/2=p1/2|S|3/2.
 
Posljednje dvije ocjene se mogu kombinirati u
 
(6)
ξp{0}|fˆ(ξ)|3p1/2|S|ξp{0}|fˆ(ξ)|2p1/2|S|(p1/2|S|3/2)2=p3/2|S|4.
 
Konačno, zbog (c) dijela teorema 4 imamo (f*f*fˆ)(ξ)=fˆ(ξ)3 pa formula inverzije i (6) daju {\allowdisplaybreaks
 
(f*f*f)(x)=p-1ξpfˆ(ξ)3e-2πixξ/pp-1fˆ(0)3-p-1ξp{0}|fˆ(ξ)|3p-1|S|6-p1/2|S|4=p-1|S|4(|S|2-p3/2).
 
} Preostaje iskoristiti pretpostavku zadatka |S|>p3/4, tj. |S|2-p3/2>0.
     


Postoje i složenije primjene Fourierove analize na konačnim grupama u teoriji brojeva. Zainteresirani čitatelj može pogledati dokaz tzv. Gaussovog zakona kvadratnog reciprociteta izložen u knjizi [2].

5Primjene u kombinatorici

Fourierova analiza svoje najzanimljivije primjene nalazi u kombinatorici i to posebno u području tzv. aditivne kombinatorike, koja se bavi kombinatornim aspektima operacije zbrajanja. O tome svjedoči cijelo jedno poglavlje opsežne knjige [11]. Kako bismo mogli riješiti neke zahtjevnije zadatke, trebamo naučiti još jedan rezultat, koji se popularno naziva princip neodređenosti, po uzoru na formalno slične rezultate iz kvantne mehanike.

Za funkciju f:A na konačnoj komutativnoj grupi A označimo

 
supp(f):={xA:f(x)0},
 

a promatrat ćemo i

 
supp(fˆ)={ξA:fˆ(ξ)0}.
 

Kratica “supp” dolazi od engleske riječi support, koja se na hrvatski prevodi kao nosač funkcije.

Teorem 12. [Princip neodređenosti]
[(a)] Neka je A grupa dana s (1). Za svaku funkciju f:A koja nije identički jednaka konstanti 0 vrijedi
 
|supp(f)||supp(fˆ)||A|.
 
[(b)] Za svaku funkciju f:p, gdje je p prost broj, koja nije identički jednaka konstanti 0 vrijedi
 
|supp(f)|+|supp(fˆ)|p+1.
 
Obratno, za svaka dva skupa A,Bp koji zadovoljavaju |A|+|B|p+1 postoji funkcija f:p takva da je supp(f)=A i supp(fˆ)=B.

Proof. Dokažimo samo (a) dio teorema. Korištenjem nejednakosti trokuta, aritmetičko-kvadratne nejednakosti i Plancherelovog identiteta redom dobivamo {\allowdisplaybreaks
 
maxξA|fˆ(ξ)|=maxξA|xAf(x)E(x,ξ)|xA|f(x)|=xsupp(f)|f(x)||supp(f)|1/2(xsupp(f)|f(x)|2)1/2=|supp(f)|1/2(|A|-1ξA|fˆ(ξ)|2)1/2=|A|-1/2|supp(f)|1/2(ξsupp(fˆ)|fˆ(ξ)|2)1/2|A|-1/2|supp(f)|1/2|supp(fˆ)|1/2maxξA|fˆ(ξ)|.
 
} Ako f nije identički jednaka 0, tada ni fˆ nije identički jednaka 0 pa je maxξA|fˆ(ξ)|>0. Dijeljenjem s tim faktorom dobivamo traženu nejednakost.

Dio (b) je mnogo složeniji i zasniva se na teoremu Čebotareva o korijenima iz jedinice, koji govori da za 1mp, za različite x1,,xmp i za različite ξ1,,ξmp vrijedi
 
det[e2πixjξk/p]j=1,,mk=1,,m0.
 
Jedan elementaran (ali još uvijek prilično tehnički) dokaz dao je T. Tao [10].
     


Dio (a) teorema 12 daje ocjenu za proizvoljnu konačnu komutativnu grupu A, dok njegov (b) dio govori o pojačanju te ocjene u slučaju grupe p. R. Meshulam je u članku [6] dao analogno pojačanje i za općenitu grupu A, koje ovdje nećemo diskutirati.

Zadatak 13. Neka je n prirodan broj. Označimo s n familiju svih 2n podskupova skupa {1,2,,n}. Za svaki Sn dan je realni broj aS i pretpostavimo da je točno k1 od tih brojeva aS različito od 0. Dokažite da jednadžba
 
SnaSjSxj=0
 
ima najviše 2n(1-1/k) rješenja u skupu {-1,1}n, tj. ima najviše toliko n-torki (x1,x2,,xn) koje zadovoljavaju jednadžbu i za svaki indeks j je ili xj=-1 ili xj=1.


Napomenimo da za S= produkt jSxj uvijek interpretiramo kao broj 1. Naprimjer, za n=2 jednadžba glasi

 
a+a{1}x1+a{2}x2+a{1,2}x1x2=0.
 

Rješenje.. Promotrimo grupu
 
A=2n=22n={0,1}n
 
i uspostavimo bijektivnu korespondenciju
 
nA,   Skarakteristična funkcija skupa S
 
s inverzom
 
An,   (z1,,zn){j{1,2,,n}:zj=1}.
 
Dakle, skupu Sn odgovara n-torka z=(z1,,zn) takva da je zj=1 za jS i zj=0 za jSc. Tada umjesto aS pišemo az.

Definiramo funkciju f:A,
 
f(y1,,yn):=SnaSjS(-1)yj=z=(z1,,zn)Aazj=1n(-1)yjzj,
 
tj.
 
f(y):=zAazE(y,z).
 
Primijetimo da zapravo želimo pobrojati rješenja (y1,,yn)A jednadžbe f(y1,,yn)=0, jer su ona putem xj=(-1)yj u korespondenciji s rješenjima (x1,,xn){-1,1}n polazne jednadžbe. Trebamo dokazati da je |supp(f)|2n/k, jer će tada broj rješenja biti najviše 2n-2n/k.

Zbog E(y,z){-1,1} i propozicije 1 imamo
 
fˆ(ξ)=yA(zAazE(y,z)¯)E(y,ξ)=zAazyAE(y,ξ-z)=2naξ.
 
Po pretpostavci zadatka je |supp(fˆ)|=k. Zato (a) dio teorema 12 primijenjen na grupu A daje
 
|supp(f)||A||supp(fˆ)|=2nk.     
 


Naredni rezultat zove se Cauchy-Davenportov teorem. Elegantni dokaz koji slijedi osmislio je R. Chapman, a mi ga preuzimamo iz članka [10].

Zadatak 14. Ako je p prost broj i ako su A,Bp neprazni, dokažite da tada vrijedi
 
|A+B|min{|A|+|B|-1,p},
 
pri čemu označavamo
 
A+B:={a+b:aA,bB}.
 

Rješenje.. Najprije tvrdimo da možemo naći skupove X,Yp takve da je
 
|X|=p+1-|A|,   |Y|=p+1-|B|,   |XY|=max{p+2-|A|-|B|,1}.
 
Razlikujemo dva slučaja. Ako je |A|+|B|p+1, tada možemo uzeti
 
X={0,1,,p-|A|},  Y={|B|-1,|B|,,p-1}.
 
Ako je pak |A|+|B|p+2, tada možemo uzeti
 
X={0,1,,p-|A|},  Y={p-|A|,p-|A|+1,,2p-|A|-|B|}.
 

Prema (b) dijelu principa neodređenosti postoje funkcije f,g:p takve da je
 
supp(f)=A,  supp(fˆ)=X,  supp(g)=B,  supp(gˆ)=Y.
 
Promotrimo funkciju f*g. Iz definicije konvolucije odmah se vidi
 
supp(f*g)supp(f)+supp(g)=A+B,
 
dok iz svojstva
 
(f*gˆ)(ξ)=fˆ(ξ)gˆ(ξ)
 
slijedi
 
supp(f*gˆ)=supp(fˆ)supp(gˆ)=XY.
 
Konačno, ponovnim korištenjem (b) dijela teorema 12 dobivamo
 
|A+B|+|XY||supp(f*g)|+|supp(f*gˆ)|p+1,
 
što je upravo
 
|A+B|p+1-max{p+2-|A|-|B|,1}=min{|A|+|B|-1,p}.     
 


Za vježbu ostavljamo još jedan zadatak iz članka [10].

Zadatak 15. Neka je p prost broj i neka je S:={z:zp=1} skup p-tih korijena iz jedinice. Nadalje, neka su c0,c1,c2,,cp-1, među kojima je točno k1 brojeva različito od 0. Dokažite da je moguće odabrati podskup TS koji ima |T|=p-k+1 elemenata i takav je da za svaki zT vrijedi j=0p-1cjzj0.

Uputa.. Promotrite funkciju
 
f:p,   f(x):=j=0p-1cje-2πijx/p,
 
tako da treba pokazati |supp(f)|p-k+1. Primijetite da je fˆ(ξ)=pcξ i |supp(fˆ)|=k pa se pozovite na (b) dio teorema 12.
     


U ovom radu odlučili smo promatrati samo konačne komutativne grupe. Naravno da se bogatija teorija dobiva razmatrajući općenitije komutativne grupe i njih proučava tzv. harmonijska analiza, čije osnove zainteresirani čitatelj može naučiti iz knjige [3] ili diplomskog rada [7]. Nekomutativnim grupama bavi se teorija reprezentacija i opet je najelementarnije krenuti od konačnih grupa, kao npr. u knjizi [4]. {10}

Bibliografija
[1] J. Bourgain, Mordell's exponential sum estimate revisited, J. Amer. Math. Soc. 18 (2005), 477–499.
[2] H. Dym, H. P. McKean, Fourier Series and Integrals, Probability and Mathematical Statistics 14, Academic Press, New York-London, 1972.
[3] G. B. Folland, A Course in Abstract Harmonic Analysis, drugo izdanje, Textbooks in Mathematics, CRC Press, Boca Raton, 2016.
[4] W. Fulton, J. Harris, Representation Theory: A First Course, Graduate Texts in Mathematics 129, Springer-Verlag, New York, 1991.
[5] S. Kurepa, Konačno dimenzionalni vektorski prostori i primjene, Tehnička knjiga, Zagreb, 1967.
[6] R. Meshulam, An uncertainty inequality for finite abelian groups, European J. Combin. 27 (2006), 63–67.
[7] Lj. Palle, Fourierova analiza na lokalno kompaktnim, Abelovim grupama i neke primjene, diplomski rad, Sveučilište u Zagrebu, 2015.
[8] I. J. Schoenberg, The finite Fourier series and elementary geometry, Amer. Math. Monthly 57 (1950), 390–404.
[9] D. Svrtan, D. Šterc, I. Urbiha, On cyclic characterizations of regular pentagons and heptagons: two approaches, Math. Commun. 7 (2002), 71–89.
[10] T. Tao, An uncertainty principle for cyclic groups of prime order, Math. Res. Lett. 12 (2005), 121–127.
[11] T. Tao, V. Vu, Additive Combinatorics, Cambridge Studies in Advanced Mathematics 105, Cambridge University Press, Cambridge, 2006.
 


 

Share this