Yoshiharu Kohayakawa
IME-USP
Sexta-feira, 4 de junho de 2004, 14:00
Sala 267, Bloco A, IME-USP
Resumo:
Mauduit e Sárközy introduziram e investigaram certos parâmetros numéricos associados a palavras binárias $w$ em $\{a,b\}^*$ para medir seu nível de "aleatoriedade". Um desses parâmetros, a medida de normalidade $\calN(w)$ de $w$, é definido com base no número de ocorrências de palavras curtas como fatores de $w$. Mauduit e Sárközy investigaram, entre outros, os valores típicos e mínimos de seus parâmetros. Nesta palestra, discutiremos alguns resultados nessa linha, e apresentaremos uma construção algébrica de uma palavra $w_0$ com normalidade $\calN(w_0)$ atipicamente pequena.
O método envolvido na estimativa da normalidade de $w_0$ é elementar; curiosamente, ele também fornece uma prova curta da desigualdade de Pólya e Vinogradov para somas incompletas de caracteres.
Trabalho conjunto com N. Alon (Tel Aviv), C. Mauduit (Marseille), C.G. Moreira (Rio de Janeiro), e V. Rödl (Atlanta).