AFF-4 Uniformidade — norma de Gowers


A uniformidade (ou norma de Gowers de ordem 1) de {A\subset G} é

\displaystyle  \Vert A \Vert_{u}  := \max \left\{ | \widehat{1_A}(\xi_b) | \colon {b\in G\setminus \{0\}}  \right\}. \ \ \ \ \ (33)

Por exemplo, do exemplo 5, se {I} é um intervalo no {{\mathbb Z}_N} então {\Vert 1_I \Vert_u \leq 1/2}

Exercício 17 Mostre que

\displaystyle \Vert A\Vert_u = \Vert -A\Vert_{u} = \Vert {A+a} \Vert_u = \Vert {G\setminus A}\Vert_u

para todo {A\subseteq G}. Mostre que {\Vert A\Vert_u =0} se e somente se {A=0} ou {A=G}. Mostre que vale

\displaystyle  \big| \Vert A \Vert_u - \Vert B \Vert_u \big| \leq  \Vert {A\cup B} \Vert_u  \leq  \Vert A \Vert_u + \Vert B \Vert_u .

Proposição 7 Para todo {A\subseteq G}

\displaystyle   \frac{\sqrt{{|A|}/{2}}}{|G|} \leq  \Vert A \Vert_u \leq  \frac{|A|}{|G|} \ \ \ \ \ (34)

Demonstração: Não é difícil verificar que {\Vert A \Vert_u\leq \mathop{\mathbb P}_G(A)}

\displaystyle  \begin{array}{rcl}  |\widehat{1_A}(\xi_g)| &= & \left| \frac 1{|G|}\sum_{a\in G} 1_A(a)\overline{\xi_g(a)} \right|\\ &\leq & \frac 1{|G|}\sum_{a\in G} \left| 1_A(a)\overline{\xi_g(a)} \right|\\ &=& \frac 1{|G|}\sum_{a\in G}  1_A(a)\left|\overline{\xi_g(a)} \right|\\ &=& \frac 1{|G|}\sum_{a\in G}  1_A(a)= \frac {|A|}{|G|}. \end{array}

Pelo exercício 17 podemos assumir {|A|\leq |G|/2}. Por Parseval–Plancherel, corolário 6

\displaystyle  \begin{array}{rcl}  \frac{1}{|G|}\sum_{a\in G}|1_A(a)|^2 &=&  \sum_{a\in {\widehat{G}}} |\widehat{1_A}(a)|^2 \\ &\leq & |\widehat{1_A}(e_0)|^2 + (|G|-1)\Vert A \Vert_u^2\\ &\leq & |\widehat{1_A}(e_0)|^2 + (|G|-1)\Vert A \Vert_u^2\\ &=& \left(\frac{|A|}{|G|}\right)^2 + (|G|-1)\Vert A \Vert_u^2 \end{array}

logo

\displaystyle  \Vert A \Vert_u \geq  \left( \frac{|A|/|G| - (|A|/|G|)^2}{|G|-1} \right)^{1/2} \geq  \sqrt{\frac{|A|}{2|G|^2}}. \ \ \ \ \ (35)

Isso prova a proposição. \Box

Exercício 18 Prove que {\Vert A \Vert_u=\mathop{\mathbb P}_G(A)} se e somente se {A\subseteq H+b}, para algum {b\in G} e para algum subgrupo próprio {H\subset G}.

Dado {\epsilon>0}, dizemos que {A\subset G} é {\epsilon}-uniforme se

\displaystyle   \Vert A \Vert_{u}  < \epsilon \ \ \ \ \ (36)

Exemplo 13 (Uniformidade e {3}-representação) Dados {A\subseteq G} e {x\in G} uma 3-representação de {x} em {A} é uma triplas de elementos em {A^3} que somam {x}. Se {A} é um subconjunto aleatório em que cada elemento é escolhido com probabilidade~{\delta = \mathop{\mathbb P}_{a\in G} (a\in A)} e de modo independente das outras escolhas, então uma determinada tripla está em {A} com probabilidade {\delta^3} e o número total de tais triplas é aproximadamente {|G|^2} assim o número esperado de triplas em {A} é aproximadamente {\delta^3 |G|^2}. Agora, seja {A} um subconjunto {\epsilon}-uniforme do grupo {G} com densidade {\mathop{\mathbb P}_G(A)=\delta}. Dado {a\in G} denotemos {T_A(a)=\left| \{(x,y,z)\in A^3\colon x+y+z=a\} \right|} e vamos mostrar que

\displaystyle  \left| T_A(a) - \delta^3 |G|^2 \right| \leq  \epsilon{\delta}|G|^2. \ \ \ \ \ (37)

Usaremos (31) a seguir. Do exemplo 9, eq. (22)

\displaystyle  1_A*1_A*1_A(a)=\frac{1}{|G|^{2}} T_A(a)

e escrevendo a expansão de Fourier da convolução

\displaystyle  \begin{array}{rcl}  1_A*1_A*1_A(a) &=& \sum_{b\in G}\widehat{1_A*1_A*1_A}(\xi_b)\xi_b(a)\\ &=& \widehat{1_A*1_A*1_A}(\xi_0) + \sum_{b\neq 0}\widehat{1_A*1_A*1_A}(\xi_b)\xi_b(a). \end{array}

Mas, { \widehat{1_A*1_A*1_A}(\xi_0) = \widehat{1_A}\widehat{1_A}\widehat{1_A}(\xi_0) = \delta^3}, pois {\widehat{1_A}(\xi_0)=\mathop{\mathbb P}_G(A)=\delta} logo

\displaystyle  \begin{array}{rcl}  \left| 1_A*1_A*1_A(a) - \delta^3 \right| = \left| \sum_{b\neq 0} \widehat{1_A}\widehat{1_A}\widehat{1_A}(\xi_b) \xi_b(a) \right|  \end{array}

e vamos estimar o lado direito, que é no máximo

\displaystyle  \begin{array}{rcl}  \sum_{b\neq 0} \left| \widehat{1_A}\widehat{1_A}\widehat{1_A}(\xi_b)\xi_b(a) \right| &= & \sum_{b\neq 0} |\widehat{1_A}(\xi_b)||\widehat{1_A}(\xi_b)||\widehat{1_A}(\xi_b)| |\xi_b(a)| \qquad\qquad [|\xi_b(a)|=1]\\ &\leq & \Vert A \Vert_u \sum_{b\neq 0} |\widehat{1_A}(\xi_b)||\widehat{1_A}(\xi_b)|\\ &\leq & \Vert A \Vert_u\|\widehat{1_A}\|_{\ell_2(\widehat G)}^2 = \Vert A \Vert_u \Vert 1_A \Vert_{L^2(G)}^2 \\ &=& \Vert A \Vert_u\;\mathop{\mathbb P}_G(A) \end{array}

na terceira linha usamos Parseval–Plencherel. Disso tudo, se {A} é {\epsilon}-uniforme de densidade {\delta} então

\displaystyle  \left| \frac{T_A(x)}{|G|^{2}} - \delta^3 \right|  \leq \delta \epsilon

donde segue (37).

Exercício 19 (Aleatoriedade e {3}-representação) Prove que se {A} é um subconjunto aleatório de {G}, obtido quando escolhemos cada {a\in G} para {A} independentemente com probabilidade {\delta}, então {|T_A(x) -\delta^3|G|^2| \leq \epsilon \delta |G|^2} com probabilidade maior que {1-6(\epsilon\delta |G|)^{-1}} para todo {\epsilon>0}

Exemplo 14 (Uniformidade e densidade relativa) Fixado {A\subseteq G} queremos estimar

\displaystyle   S_A(B) = \sum_{b\in B} | B \cap (A-b) | \ \ \ \ \ (38)

para {B \subseteq G}. Se {A} é um subconjunto aleatório em que cada elemento é escolhido com probabilidade {\delta = \mathop{\mathbb P}_{a\in G} (a\in A)} e de modo independente das outras escolhas então uma determinada dupla {(a,b)\in B^2} é tal que {a+b\in A} com probabilidade {\delta}, portanto, o número esperado dessas duplas é {\delta |B|^2}. Seja {A} um subconjunto {\epsilon}-uniforme de densidade {\mathop{\mathbb P}_G(A)=\delta} em {G}. Denotemos por {S_A(B)}, para todo {B} não-vazio, o conjunto {\{(a,b)\in B^2\colon a+b\in A\}}. Vamos mostrar

\displaystyle  \left|  S_A(B) - \delta |B|^2 \right|  <\  \epsilon |B| |G|. \ \ \ \ \ (39)

Do exemplo 10, {S_A(B) = |G|^2 1_B*1_B*1_{-A}(0)}. Escrevendo a expansão de Fourier de

\displaystyle  \begin{array}{rcl}  1_B*1_B*1_{-A}(0) &=& \sum_b \widehat{1_B*1_B*1_{-A}}(\xi_b) {\xi_b(0)}\\&=& \sum_b \widehat{1_B*1_B*1_{-A}}(\xi_b) \\&=& \sum_b \widehat{1_B}\widehat{1_B}\widehat{1_{-A}}(\xi_b) \\&=& \delta \mathop{\mathbb P}_G(B)^2 + \sum_{b\neq 0} \widehat{1_B}\widehat{1_B}\widehat{1_{-A}}(\xi_b) \end{array}

logo

\displaystyle  \begin{array}{rcl}  \left| \frac{S_A(B)}{|G|^2} - \delta \mathop{\mathbb P}_G(B)^2 \right| = \left|  \sum_{b\neq 0}\widehat{1_B}\widehat{1_B}\widehat{1_{-A}}(\xi_b) \right| &\leq& \sum_{b\neq 0}\left|  \widehat{1_B}\widehat{1_B}\widehat{1_{-A}}(\xi_b)  \right|\\ &\leq& \sum_{b\neq 0}  | \widehat{1_B}(\xi_b)|\, | \widehat{1_B}(\xi_b)|\, | \widehat{1_{-A}}(\xi_b) |\\ &\leq& \Vert -A\Vert_u \sum_{b\neq 0}  |\widehat{1_B}(\xi_b)| \, |\widehat{1_B}(\xi_b)|\\ &\leq& \Vert A \Vert_u \sum_{b\neq 0}  | \widehat{1_B}(\xi_b)|\,|\widehat{1_B}(\xi_b)|\\ &\leq& \Vert A \Vert_u \, \Vert \widehat{1_B} \Vert_{\ell^2(\widehat{G})}^2. \end{array}

De (31)

\displaystyle  \left| \frac{S_A(B)}{|G|^2} - \delta \mathop{\mathbb P}_G(B)^2 \right|  \leq \epsilon \mathop{\mathbb P}_G(B)

donde segue (39)

Exercício 20 (Aleatoriedade e densidade relativa) Seja {A} um subconjunto do {G} onde cada elemento está em {A} com probabilidade {\delta}, independentemente, e {B\subset G} não-vazio. Prove que { \left| |S_A(B)| - \delta{|B|^2} \right| <\ \epsilon |G|^2 } com probabilidade próxima de {1}, para todo {\epsilon>0}.

Notemos que se {|T_A(x)/|G|^2 -\delta^3| > \epsilon\delta} então {\Vert A\Vert_u > \epsilon} e se {|S_A(B)/|G|^2 -\delta\mathop{\mathbb P}(B)^2|> \epsilon \mathop{\mathbb P}(B)} então {\Vert A\Vert_u > \epsilon}.

Exercício 21 Seja {Q(A)} como no exemplo 12. Mostre que para {A} de densidade {\delta }

  1. se {\Vert A \Vert_u\leq \epsilon } então {Q(A)\leq (\delta^4+\epsilon^2\delta)n^3};
  2. se {Q(A)\leq (\delta^4+\epsilon)n^3} então {\Vert A \Vert_u\leq \epsilon^{1/4} };

Exemplo 15 (Uniformidade e progressões aritméticas) Sejam {A,B,C\subseteq G} com densidades {\alpha,\beta,\gamma}, respectivamente. O número de soluções da equação

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

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

\displaystyle  \begin{array}{rcl}  S  &= & |G|^2 1_A*1_B*1_C(0) \\ & =& |G|^2 \sum_{b} \widehat{1_A*1_B*1_C}(\xi_b)\xi_b(0)\\  & =& |G|^2 \sum_{b} \widehat{1_A}\widehat{1_B}\widehat{1_C}(\xi_b)\\ & =& |G|^2  \left( \alpha\beta\gamma + \sum_{b\neq 0} \widehat{1_A}\widehat{1_B}\widehat{1_C}(\xi_b) \right) \end{array}

portanto, o número de soluções satisfaz

\displaystyle  \begin{array}{rcl}   \left|\frac {S}{|G|^2} - \alpha\beta\gamma\right|  & = &  \Big| \sum_{b\neq 0}  \widehat{1_A}(\xi_b)\widehat{1_B}(\xi_b)\widehat{1_C}(\xi_b) \Big| \\ & \leq & \sum_{b\neq 0} |\widehat{1_A}(\xi_b)|\, |\widehat{1_B}(\xi_b)| \, |\widehat{1_C}(\xi_b)| \\& \leq \sum_{b} |\widehat{1_A}(\xi_b)|\,  |\widehat{1_B}(\xi_b)| \end{array}

usando a desigualdade de Bunyakovsky–Cauchy–Schwarz

\displaystyle  \begin{array}{rcl}  \sum_{b} |\widehat{1_A}(\xi_b)||\widehat{1_B}(\xi_b)| &\leq & \left( \sum_{b} |\widehat{1_A}(\xi_b)|^2 \right)^{1/2} \left( \sum_{b} |\widehat{1_B}(\xi_b)|^2 \right)^{1/2} \\ &\leq& \Vert \widehat{1_A} \Vert_{\ell^2(\widehat G)} \; \Vert \widehat{1_B} \Vert_{\ell^2(\widehat G)}\\ &\leq& \Vert {1_A} \Vert_{L^2(G)} \; \Vert {1_B} \Vert_{L^2(G)}\\ &=&\sqrt{\alpha \beta}. \end{array}

Juntando tudo

\displaystyle   \left|\frac {S}{|G|^2} -\alpha\beta\gamma \right|  \leq  {\Vert C \Vert_u } \sqrt{\alpha \beta} \ \ \ \ \ (41)

que pode ser rescrito como

\displaystyle   \left| S-\frac{|A||B||C|}{|G|}  \right| \leq {\Vert C \Vert_u }\sqrt{|A||B|}\;|G| . \ \ \ \ \ (42)

Exercício 22 Mostre que a equação acima vale para o número de soluções de {x+y+z=a}, onde {(x,y,z)\in A\times B \times C} e {a\in G}. (Dica: {\Vert A \Vert_u=\Vert A+b\Vert_u}.)

De volta ao exemplo 11, uma sequência {(a,b,c)} de três elementos de {A\subset G} é uma 3-PA se {a-2b+c = 0}. Se {A} é tal que {\delta = \mathop{\mathbb P}_G(a\in A)} então o número esperado de 3-PA é ~{\mathop{\mathbb E} (\mathrm{PA}_3) \approx |G|^2\delta^3}. Quando {|A|=|2A|} ou, que é mais geral, {G} tem ordem ímpar só ocorrem 3-PA triviais e próprias. Consideremos {G} de ordem ímpar e {\mathrm{PA}_3(A)} o número de progressões aritméticas {G} contidas em {A}

\displaystyle  \mathrm{PA}_3 (A)= \{(a,b,c)\in A\times -2A\times A\colon a+b+c=0\}. \ \ \ \ \ (43)

se {A} é um subconjunto com densidade {\delta} e {\epsilon}-uniforme então por (41)

\displaystyle  \left| \frac{\mathrm{PA}_3(A)}{|G|^2} -\delta^3\right|  \leq \Vert A \Vert_u \delta = \epsilon\delta . \ \ \ \ \ (44)

Por outro lado, se {A} contém somente 3-PA triviais então {\mathrm{PA}_3 =|A|}, i.e.

\displaystyle  \frac{\mathrm{PA}_3(A)}{|G|^2} = \frac{\delta }{|G|} \ \ \ \ \ (45)

logo, por (44), se {G} tem ordem ímpar e o subconjunto {A\subset G} de densidade {\delta} contém somente 3-PA triviais, então

\displaystyle   \Vert A\Vert_u \geq \delta^2- \frac 1{|G|}. \ \ \ \ \ (46)

Exercício 23 (Aleatoriedade e progressões aritméticas) Estabeleça a versão probabilística de (44).

Uniformidade de subconjuntos aleatórios: Seja {A} escolhido aleatoriamente de maneira uniforme dentre os subconjuntos de {G} de cardinalidade {k}. Estimaremos {\Vert A \Vert_u}. Considere {A} dado da seguinte forma: seja {X} uma permutação de {\{0,1,\dots,N-1\}} escolhida uniformemente e tome {A:=\{g_{X_0},g_{X_1}, \dots ,g_{X_{k-1}}\}}. Dado {b\in G\setminus\{0\}} definimos a variável aleatória

\displaystyle  f_b(A) = \sum_{a\in G}1_A(a)\xi_b(a) = \sum_{i=0}^{k-1}\xi_b(g_{X_i})

cuja esperança é

\displaystyle  \mathop{\mathbb E} f_b(A) = \sum_{a\in G} \frac{ \binom{|G|-1}{t-1}}{\binom{|G|}{t}}  {\xi_b(a)} = 0.

Vamos mostrar que

\displaystyle  \max_{b\in G\setminus \{0\}} |f_b(A)|  < {3} \sqrt{(1+\epsilon) t \ln N}, \ \ \ \ \ (47)

onde {t=\min\{k,N-k\}}. Primeiro, notemos que { f_b(G\setminus A) =\sum_{a\not \in A}\xi_b(a) =\sum_{a \in G}\xi_b(a) - \sum_{a \in A}\xi_b(a) = -f_b( A) } portanto, podemos assumir {t=k\leq N/2}. Definimos {Z_0(A):=\mathop{\mathbb E}\,f_b(A)} e para todo {1\leq i\leq k}

\displaystyle  Z_i (A):= \mathop{\mathbb E}{ \left( f_b(A) | X_0, X_1, \dots, X_{i-1} \right)}

e note que {Z_k=f_b(A)}.

Exercício 24 {Z_0,Z_1,\dots,Z_k} é um martingal, i.e., {\mathop{\mathbb E} (|Z_i|) < \infty} e {\mathop{\mathbb E} (Z_{i+1} ~|~ Z_0,\dots,Z_i) =Z_i}.

O valor de {X_{i+1}} pode afetar o valor de {f_b(A)} por no máximo {2} desde que a troca de {g} por {h} no conjunto {A} muda o valor de {f_b(A)} por {|\xi_b(g)-\xi_b(h)|\leq 2}, para quaisquer {g,h\in G}, portanto, {|Z_i-Z_{i-1}|\leq 2} e da desiguladade de Azuma-Hoeffding

\displaystyle   \mathop{\mathbb P} \big[ |Z_k|\geq a\big]  <  2\exp \left( -\frac{a^2}{9k}  \right), \ \ \ \ \ (48)

para todo {a>0}. Tomando {a=3\sqrt{(1+\epsilon )k\ln N}} temos

\displaystyle  \begin{array}{rcl}   \mathop{\mathbb P} \big[ \max_{b\neq 0} |f_b(A)| \geq 3 \sqrt{(1+\epsilon )k\ln N} \big]  &\leq & N \mathop{\mathbb P}\big[ |Z_k| \geq 3\sqrt{(1+\epsilon )k\ln N}\big] \\ &< &  2 N \exp \left( -(1+\epsilon )\ln N \right) \\ &= &  O(N^{-\epsilon}).  \end{array}

Teorema 8 Para todo {\epsilon>0}, com probabilidade {1-O(N^{-\epsilon})} o subconjunto {A\subseteq G} escolhido de modo uniforme dentre todos os subconjuntos de cardinalidade {k} satisfaz

\displaystyle  \Vert A \Vert_u < 3 \frac{\sqrt{(1+\epsilon) t \ln N}}{N}

onde {t=\min\{k,N-k\}}.

Exercício 25 Seja {a} um elemento de {G} escolhido uniformemente. Mostre que as variáveis aleatórias

\displaystyle \{\chi_b(a)\colon b\in G\}

são 2-a-2 independentes. Mostre que para {b=0} (caracter principal) a variância é {0} e o valor esperado {1}. Determine a variância e o valor esperado nos outros casos.

Exercício 26 Seja {A\subseteq G} um subconjunto aleatório obtido escolhendo-se cada elemento de {G=\{g_0,\dots,g_{n-1}\}} com probabilidade {1/2}. Tome {\iota_i}, {0\leq i\leq n-1}, a variável aleatória com valores em {\{-1,1\}} onde {1} significa que {g_i} foi escolhido. Defina

\displaystyle  \xi(\chi):=\sum_{i=0}^{n-1}\frac{\iota_i+1}{2}\chi(g_i)= \frac{1}{2}\sum_{i=0}^{n-1}\iota_i\chi(g_i).

Use a Desigualdade de Chernoff na parte real e na parte imaginaria de {\xi} para mostrar que

\displaystyle \Vert A \Vert_u < \frac{\sqrt{(1+\epsilon)n \log n}}{n}

com probabilidade {1-O(n^{-\epsilon})}, para todo {\epsilon>0}.

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