AFF-3 Convolução

A convolução das funções {f,g\in {\mathbb C}^Z} é a função

\begin{array}{rcl} \displaystyle f*g(a)&:=&\frac{1}{{|G|}} \sum_{b\in G}f(a-b)g(b) \\   &=& \displaystyle \frac 1{|G|} \sum_{x+y=a}f(x) g(y)\ \ \ \ \ (22)\\   &=& \displaystyle \frac{1}{{|G|}} \sum_{b\in G}T_b\,f(a)g (b), \end{array}

e muito da utilidade dessa operação é por causa da identidade

\displaystyle  \widehat{f*g} = \widehat{f}\cdot\widehat{g}; \ \ \ \ \ (23)

de fato, para todo caracter {\xi}

\displaystyle  \begin{array}{rcl} \displaystyle \widehat{f*g}(\xi)  &=&  \displaystyle\frac{1}{{|G|}} \sum_{a \in {G}} f*g(a)\;\overline{\xi(a)}\\ &=& \displaystyle\frac{1}{{|G|}}\sum_{a \in {G}} \sum_{b\in G}\frac{1}{{|G|}} f(a-b)g(b)\;\overline{\xi(a)}\\ &=& \displaystyle\sum_{a \in {G}}\sum_{b\in G}\frac{1}{{|G|}^2} f(a-b)g(b)\overline{\xi(a-b)}\;\overline{\xi(b)}\\ &=&\displaystyle \sum_{c \in {G}}f(c)\frac{1}{{|G|}}\;\overline{\xi(c)} \sum_{b\in G}g(b)\frac{1}{{|G|}}\;\overline{\xi(b)}\\&=& \displaystyle\widehat{f}(\xi)\;\widehat{g}(\xi). \end{array}

Exercício 13 A convolução de funções {f,\,g,\,h\colon Z \rightarrow {\mathbb C}} satisfaz

  1. {f*g=g*f};
  2. {f*(g*h)=(f*g)*h};
  3. {f*(\alpha g + h)= \alpha f*g  +f *h};
  4. {\mathrm{supp}(1_A*1_B) = A+B := \{  x+y\colon x\in A, ~y\in B\}}, supp denota suporte, que é o
    conjunto dos pontos do domínio onde a função é não-nula;
  5. {\Vert f*g \Vert_{L^\infty} \leq  \Vert f\Vert_{L^1}\Vert g  \Vert_{L^\infty}};
  6. {\Vert f*g \Vert_{L^\infty}  \leq  \Vert f\Vert_{L^p}\Vert g \Vert_{L^q}} {(1/p+1/q=1)};
  7. {\Vert f*g \Vert_{L^1} \leq   \Vert f\Vert_{L^1}\Vert g \Vert_{L^1}}.

Exercicio 14 Estenda a igualdade (22) acima para a convolução de {k>2} funções

\displaystyle  f_1*f_2*\cdots * f_k(a) = \frac{1}{|G|^{k-1}}\sum_{x_1+x_2+\cdots+x_k=a}f_1(x_1)f_2(x_2)\cdots f_k(x_k).

Exercicio 15 Seja {T_a} a transformação definida em (8) acima. Prove que {\delta_a*f=T_a\,f} para toda {f\in {\mathbb C}^G}.

A convolução {f*g(a)}, na forma (22), nos diz que é o valor médio de {f(x)f(y)} sobre todo par {(x,y)} tal que {x+y=a}. Isso é particularmente útil com subconjuntos de grupos aditivos. Sejam {A,~B \subset G} e denotemos por {1_A} e {1_B} suas funções características. Então, {1_A*1_B(a)} conta de quantas maneiras {a} pode ser escrito como soma de dois elementos, um de {A} e outro de {B}. A função {f*1_A} em {a} é o valor médio da função {f} no conjunto

\displaystyle  a-A := \{ a-b \colon b\in A\}.

Exemplo 9 (3-representação) Para {A} subconjunto de {G} e {a\in G} denotamos

\displaystyle  T_A(a):=\left| \{(x,y,z)\in A^3\colon x+y+z=a\} \right|  \ \ \ \ \ (24)

Pelo exercício 14

\displaystyle   T_A(a) =|G|^2\,1_A*1_A*1_A(a) . \ \ \ \ \ (25)

Exemplo 10 (densidade relativa) Seja {A} um subconjunto fixo de {G}. Denotemos

\displaystyle   S_A(B):= \left| \{(a,b)\in B^2\colon a+b\in A\}\right|  =\sum_{b\in B}| (A-b) \cap B| \ \ \ \ \ (26)

e (abaixo {-A := \{-a\colon a\in A\}}). Pelo exercício 14

\displaystyle   S_A(B) = |G|^2 1_B*1_B*1_{-A}(0). \ \ \ \ \ (27)

Exemplo 11 (Progressões aritméticas) Sejam {A,B,C\subseteq G}. O número de soluções da equação

\displaystyle   x+y+z=0, \ \ \ \ \ (28)

onde {(x,y,z)\in A\times B\times C} é

\displaystyle   S = |G|^2 1_A*1_B*1_C(0)  \ \ \ \ \ (29)

Uma sequência {(a,b,c)} de três elementos de {G} é uma progressão aritmética ({3}-PA) em {G} se {a-2b+c =0}. O caso {a=b=c} é dito trivial e o caso {a=c} é dita sobreposta, como no caso {(2,5,2)} no {{\mathbb Z}_6} e {(1,6,1)} no {{\mathbb Z}_{10}}; senão dizamos PA própria. Quando {G} não tem elementos de ordem par não há PA sobreposta, em particular isso vale quando {G} tem ordem ímpar. Se {\mathrm{PA}_3(A)} é número de progressões aritméticas contidas no subconjunto {A} tal que {|2A|=|A|} (garante não sobreposição), onde {2A = \{2a\colon a\in A\}}, então

\displaystyle  \begin{array}{rcl}  \mathrm{PA}_3 (A) &:=& \{(a,b,c)\in A\times -2A\times A\colon a+b+c=0\}.\\ &=& |G|^2 1_A*1_{-2A} *1_A(0) . \end{array}

Se {A\subset G} só contém {3}-PA trivial então {|G|^21_A*1_{-2A}*1_A (0) = |A|}.

Exemplo 12 Denote por {Q(A)} o número de quádruplas {(a,b,c,d)\in A\times A\times A\times A \times A}, {A\subset G}, tais que {a+c=b+d}. A quantidade delas é a quantidade de quádruplas tais que {a-b+c-d=0}, que pelo exercício (14) e pela expansão de Fourier é

\displaystyle  \begin{array}{rcl}  |G|^3 1_A*1_{-A}*1_A*1_{-A}(0) &=&  |G|^3 \sum_{\xi\in G} \widehat{1_A*1_{-A}*1_A*1_{-A}}(\xi)\xi(0) \\ &=& |G|^3 \sum_{\xi\in G} \widehat{1_A} \widehat{1_{-A}} \widehat{1_A} \widehat{1_{-A}}(\xi) \end{array}

pois {\xi(0)=1}. Ainda, {\widehat{1_{-A}} = \overline{\widehat{1_A}}} logo

\displaystyle  \begin{array}{rcl}  |G|^3 1_A*1_{-A}*1_A*1_{-A}(0) &=&  |G|^3 \sum_{\xi\in G} |\widehat{1_A}(\xi)|^2|\widehat{1_A}(\xi)|^2 \\ &=& |G|^3 \Vert \widehat{1_A} \Vert_{\ell^4}^4. \end{array}

Exercicio 16 Denote por {Q(A,B)} o número de quádruplas {(a,b,c,d)\in A\times A\times A\times B \times B} tais que {a+c=b+d}. Mostre que {Q(A,B)=|G|^3 \|1_A*1_B\|_2^2}.

— Notação (e, de brinde, uma interpretação) —

Emprestando a notação da probabilidade, para um grupo finito {G}

\displaystyle  {\mathbb P}_G(U) = \mathop{\mathbb P}_{a\in G}(a\in U) := \mu_G(U) = \frac{|U|}{|G|}.

e se {f\in L^2(G)} então

\displaystyle {\mathbb E}_G(f) = \mathop{\mathbb E}_{a\in G}\; f(a) :=  \int_G f\,\mathrm{d}{\mathbb P}_G = \frac 1{|G|}\sum_a f(a)

é o valor médio de {f}. Claramente, {P_G(U) = {\mathbb E}_G(1_U)}. Com essa notação, ortogonalidade dos caracteres pode ser escrita como

\displaystyle  \mathop{\mathbb E}_{a\in G}\; \xi_g(a) = \delta_g(0)

\displaystyle  \mathop{\mathbb E}_{a\in G}\; \xi_g(a)\overline{\xi_h(a)} = \delta_g(h)

e o produto interno

\displaystyle  \langle f,g \rangle_{L^2(G)} = {\mathbb E}_G( f\,\overline g)

portanto, a transformada de Fourier é

\displaystyle  \widehat f (\xi) = \mathop{\mathbb E}_{a\in G} \; \ f(a) \overline{\xi(a)} .

Um papel especial é reservado para para o caracter principal {\xi_0}

\displaystyle  \hat f(\xi_0) = \mathop{\mathbb E}_{a\in G} \; f(a) .

A fórmula de Poisson, exercício 11, com essa notação fica

\displaystyle   {\mathbb E}_H(f) = {\mathbb E}_{H^\perp}(\hat f) \ \ \ \ \ (30)

para todo subgrupo {H} de {G}.

Convolução é a distribuição da soma de variáveis aleatórias independentes: seja {X\colon \Omega\rightarrow G} uma variável aleatória que assume valores em {G} e {p_X} sua distribuição

\displaystyle  p_X(a) := \mathop{\mathbb P}[X=a] = \mathop{\mathbb P} \big(\{\omega\in \Omega \colon X(\omega)=a\}\big)\qquad (\forall a\in G).

Se {X} e {Y} são variáveis aleatórias independentes

\begin{array}{rcl}    \displaystyle  p_{X+Y}(a) &=& \sum_{\substack{u,v\\u+v=a}}    p_X(u)p_Y(v) \\  &=&\displaystyle  \sum_{u} p_X(u)p_Y(a-u) \\  &=&    \displaystyle  p_X*p_Y(a). \end{array}

Para a convolução valem as identidades

\displaystyle  f*g(x) = \mathop{\mathbb E}_{a\in G} \;f(x-a)g(a)= \mathop{\mathbb E}_{a\in G} \;T_a\,f(x)g(a)

\displaystyle  1_A*1_B (x) = {\mathbb P}_G(A\cap (x-B))

onde { x-B=\{x-b\colon b\in B\}.}

\displaystyle  {\mathbb E}_G(f*g) ={\mathbb E}_G (f){\mathbb E}_G( g).

Com relação as {p}-normas

\displaystyle  \Vert \widehat{1_A} \Vert_\infty = \sup_j |\widehat{1_A}(\xi_j)| =  \widehat{1_A}(\xi_0) = {\mathbb P}_G(A) = {\mathbb E}_G (1_A) = \sum_\xi |\widehat{1_A}(\xi)|^2 = \Vert \widehat{1_A}\Vert_{\ell^2{(\widehat G)}}^2. \ \ \ \ \ (31)

A desigualdade de Hölder é

\displaystyle  {\mathbb E}_G\, |fg| \leq \big({\mathbb E}_G\,|f|^p\big)^{1/p}\big({\mathbb E}_G\,|g|^q\big)^{1/q}. \ \ \ \ \ (32)

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s