Dissertação

dissertaçao vanessa_final.pdf
Documento PDF (572.3KB)
                    UNIVERSIDADE FEDERAL DE ALAGOAS
INSTITUTO DE MATEMÁTICA
PROGRAMA DE PÓS-GRADUAÇÃO EM MATEMÁTICA
DISSERTAÇÃO DE MESTRADO

Demonstração do Teorema de van der Waerden
Via Sistemas Dinâmicos

Vanessa Lúcia da Silva

Maceió, Brasil
Fevereiro de 2016

VANESSA LÚCIA DA SILVA

DEMONSTRAÇÃO DO TEOREMA DE VAN DER WAERDEN
VIA SISTEMAS DINÂMICOS

Dissertação de Mestrado, na área de concentração
de Sistemas Dinêmicos, submetida em 12 de Fevereiro de 2016 à banca examinadora, designada pelo
Programa de Mestrado em Matemática da Universidade Federal de Alagoas, como parte dos requisitos necessários à obtenção do grau de mestre em
Matemática.

Orientador: Prof. Dr. Krerley Irraciel Martins Oliveira.

Maceió, Brasil
Fevereiro de 2016

Catalogação na fonte
Universidade Federal de Alagoas
Biblioteca Central
Divisão de Tratamento Técnico
Bibliotecário Responsável: Valter dos Santos Andrade

S586

Silva, Vanessa Lúcia da.
Demonstração do teorema de van Waerden via Sistemas dinâmicos / Vanessa
Lúcia da Silva. - 2016.
32 f. : il.
Orientador: Krerley Irraciel Martins Oliveira.
Dissertação (Mestrado em Matemática) – Universidade Federal de Alagoas.
Instituto de Matemática. Programa de Pós-Graduação em Matemática. Maceió,
2016.
Bibliografia: f. 32.
1. Partição finita. 2. Progressão aritmética. 3. Teorema de van der Waerden.
I. Título.
CDU: 517.93

“Até aqui nos ajudou o Senhor”
(Ebenézer)

Agradecimentos
Agradeço primeiramente a minha famı́lia, que sempre me apoiou ao longo desta jornada
em especial para minha mãe Vera Lúcia, minha irmã Vânia Lúcia e meu irmão Ivan José.
Agradeço também aos meus amigos Eduardo Santana, Isnaldo Isaac, Dayane Dalysse,
Joselma Lins e Robson Silva pelos incentivos e auxı́lios ao trabalho.
Por fim, quero agradecer ao meu orientador, o professor Krerley Oliveira, especialmente
por sua atenção e grande paciência, mesmo diante das minhas faltas e de seus múltiplos
compromissos. Aproveito ainda para agradecer aos professores Ali Golmakani e Mohammad
Fanaee, membros da banca examinadora, pelas sugestões e apoio a respeito desta dissertação.

Resumo
Vamos apresentar uma demonstração alternativa ao âmbito da Aritmética Combinatória,
do Teorema van der Waerden. Este resultado, consiste na busca por progressões aritméticas
de tamanhos arbitrários dentro do conjunto dos números inteiros. Mais precisamente, mostraremos que ao particionarmos finitamente o conjunto dos números inteiros, uma dessas
partes finitas de Z, possui progressões aritméticas de qualquer comprimento. Para tal, faremos uso das ideias de Fustemberg com elementos da Dinâmica Simbólica.
Palavras-chave: Partição finita. Progressão Aritmética. Teorema de van der Waerden.

Abstract
We will present an alternative demonstration the scope of Arithmetic Combinatorics,
Theorem van der Waerden. This result is the search for arithmetic progressions of arbitrary
size within the set of integers. More precisely, we show the particionarmos the finitely set of
integers, one of these parts of finite Z , has arithmetic progressions of any length. To this
end, we will make use of Fustemberg ideas with elements of symbolic dynamics.
Keywords: Finite Partition. Arithmetic Progression. Van der Waerden Theorem.

Sumário
Introdução

7

1 Preliminares
1.1 Lema de Zorn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Espaço de Sequências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 A Transformação Shift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Medidas Invariantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2
2
3
4
5

2 Teoremas de Recorrência e Extensões Naturais
2.1 Teorema de Recorrência de Birkhoff . . . . . . . . . . . . . . . . . . . . . . .
2.2 Teorema de Recorrência Múltipla de Birkhoff . . . . . . . . . . . . . . . . . .
2.3 Teorema de Recorrência múltipla de Poincaré . . . . . . . . . . . . . . . . .
2.4 Extensões Naturais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10
10
11
15
15

3 Teorema de van der Waerden
3.1 Outras Formas do Teorema de van der Waerden . . . . . . . . . . . . . . . .
3.2 Polinômio de van der Waerden . . . . . . . . . . . . . . . . . . . . . . . . . .

19
21
25

4 Demonstração do Teorema de Szemerédi

27

5 Teorema de Green-Tao

31

Referências Bibliográficas

31

Introdução
A Teoria dos Números vem ganhando destaque ao longo dos tempos com seus diversos
problemas que desafiam gerações de matemáticos. Essa área da matemática estuda as propriedades dos números, dando maior atenção aos inteiros, com ênfase aos primos.
As engrenagens dessa ciência são questionamentos tais como o surgido em 300 a.C., cuja
conjectura fora atribuı́da a Euclides de Alexandria , ainda em aberto, conhecida como conjectura dos primos gêmeos, segundo a qual existem infinitos pares de primos tais que p é
primo e p + 2 também o é. Outra conjectura ,também em aberto, é a de Goldbach, o qual
afirma que todo número inteiro par maior ou igual a 4 é a soma de dois primos.
Mediante estes questionamentos, daremos ênfase a uma conjectura respondida por Van der
Waerden, atualmente classificada como Teorema de Van der Waerden que trata da existência
de progressões aritméticas de tamanhos arbitrários em subconjuntos de Z e é a esse resultado que atentaremos neste trabalho. Tal problema fora obtido originalmente numa versão
segundo elementos da teoria combinatória e, posteriormente, fora apresentado e resolvido por
Fustemberg fazendo uso de elementos da Teoria Ergódica.
O teorema de Van der Waerden foi obtido em 1927 pelo matemático Bartel Leendert Van
der Waerden (1903- 1996). Van der Waerden é oriundo dos Paı́ses Baixos, popularmente
conhecido como Holanda, estudou na Universidade de Amsterdam e de Gottingen no perı́odo
de 1919 a 1925. Apesar de ser mais conhecido no ramo da álgebra,também publicou trabalhos em geometria algébrica, topologia, teoria dos números, geometria, análise combinatória,
análise matemática, e teoria da probabilidade.
Seguindo a mesma linha do problema proposto e resolvido por Van der Waerden, encontramos resultados posteriores mais gerais tais como: o teorema de Szemerédi (1975) o qual
afirma que todo conjunto de inteiros positivos com densidade superior positiva possui progressões aritméticas de tamanhos arbitrários. Em 2004 fora demonstrada, por Ben Green e
Terence Tao, uma antiga conjectura sobre os primos. Fora mostrado que existem progressões
aritméticas arbitrariamente longas formada apenas por primos. Esse resultado, juntamente
com outros, levaram Tao a ganhar medalha Fields em 2006.
Desta forma, observa-se a relevante busca por números primos através das progressões aritméticas.
Então, iniciaremos este trabalho identificando conceitos e teoremas necessários para demonstrar o resultado devido a van der Waerden, sobre progressões aritméticas. Posteriormente,
serão abordadas outras formas do Teorema de van der Waerden e em sequência resultados
mais gerais ao mesmo.

1

Capı́tulo 1
Preliminares

1.1

Lema de Zorn

Para concluirmos a demonstração da versão simples do Teorema de Recorrência de
Birkhoff (Seção 2.1), faremos uso de um importante lema de caráter existencial, a qual trata
de famı́lias de infinitos conjuntos, é o denominado Lema de Zorn, devido a Max Zorn.
Definição 1.1 Uma ordenação parcial num conjunto M é uma relação binária ≺ em M que
é reflexiva (x ≺ x, ∀x ∈ M ), transitiva (x ≺ y e y ≺ z ⇒ x ≺ z ) e anti simétrica (x ≺ y e
y ≺ x ⇒ x = y). Neste caso, dizemos que (M, ≺) é um conjunto parcialmente ordenado.
O termo ”parcial”na definição dada aparece pois pode haver elementos que não são comparáveis de acordo com a ordenação ≺ dada.
Exemplo 1 Denotando P(X) o conjunto das partes de X. A inclusão de conjuntos, isto é,
A ≺ B se, e somente se, A ⊂ B, define uma ordenação parcial em P(X).
Definição 1.2 Um conjunto parcialmente ordenado é dito totalmente ordenado quando quaisquer dois elementos são comparáveis de acordo com a ordenação parcial dada.
Exemplo 2 O conjunto R dos números reais com a ordenação usual ≤ é totalmente ordenado.
Definição 1.3 Seja (M, ≺) um conjunto parcialmente ordenado. x ∈ M é um elemento
maximal (minimal) em M se para todo y ∈ M com x ≺ y (y ≺ x) segue-se x = y. Um
elemento x ∈ X é majorante (minorante) de Y ⊂ X se y ≺ x (x ≺ y) para todo y ∈ Y .
Exemplo 3 O conjunto P(X), do exemplo 1.1, possui como elemento maximal o próprio
X. Enquanto no Exemplo 1.2, R não possui elemento maximal, nem minimal.
2

Lema 1.1 (Lema de Zorn) Um conjunto não vazio parcialmente ordenado, no qual todo
subconjunto totalmente ordenado possui um majorante (minorante), possui elemento maximal
(minimal).
Este lema é muito útil, pois substitui cálculos técnicos envolvendo indução transfinita, que
trata de técnica matemática que permite provar propriedades para todos números ordinais
(ou, de forma mais geral, para qualquer conjunto (ou classe) bem ordenado) a partir de etapas
finitas. Trata de uma generalização da indução finita. Além disso, o mesmo dá suporte a
demonstração de importantes resultados tais como, para concluir que todo espaço vetorial
não trivial possui uma base de Hamel, que todo conjunto infinito M é equipotente ao conjunto
M × M , dentre outros, cujas demonstrações não serão expostas pois fogem ao objetivo do
trabalho.

1.2

Espaço de Sequências

Em matemática, dinâmica simbólica é a prática de modelagem de um sistema dinâmico
topológico por um espaço discreto que consiste em sequências infinitas de sı́mbolos abstratos,
cada um dos quais corresponde a um estado do sistema, com a dinâmica dadas pelo operador
de deslocamento a esquerda, o shift.
Considere, para cada l ≥ 2 o espaço
Σ = {1, 2, ..., l}Z = {α = (..., α−1 , α0 , α1 , ...) : αi ∈ {1, 2, ..., l}, i ∈ Z}
o espaço das sequências bilaterais com l sı́mbolos.
Definição 1.4 Sejam (X, TX ) e (Y, TY ) espaços topológicos. A topologia T em X ×Y gerada
pela base
B = {U × V ; U ∈ TX , V ∈ TY }
chama-se topologia produto de TX e TY . O espaço topológico (X × Y, T ) chama-se espaço
produto.
Teorema
Q 1.1 (Tychonof ) Seja {Xα } uma famı́lia de espaços topológicos compactos. Então,
X = Xα é compacto.
Definiremos uma topologia, observando que Σ é o produto direto, de uma quantidade
enumerável de cópias do conjunto finito {1, 2, ..., l}, com a topologia discreta, e usando a
topologia produto. Desta forma, segue-se pelo Teorema de Tychonoff que Σ é compacto.
Fixando inteiros n1 < n2 < ... < nk e números α1 , ..., αk ∈ {1, 2, ..., l} chamaremos o
subconjunto de Σ de cilindro o conjunto dado por:

,...,nk
Cαn11,...,α
=
β ∈ Σ : βni = αi ∀i = 1, ..., k .
k
O número k de dı́gitos fixados é chamado de categoria do cilindro.
3

Uma forma alternativa de definirmos uma topologia no espaço Σ e observando que todos
os cilindros são conjuntos abertos e que formam uma base da topologia. Então, todo cilindro
é fechado, pois o complementar de um cilindro é a união finita de cilindros.
Podemos também introduzir, em Σ, a métrica d(β, γ) = 2−N (β,γ) em Σ, onde
N (β, γ) = max {N ≥ 0 : βn = γn , ∀n ∈ Z, |n| < N }
. De fato,
• d(β, β) = 0, pois N (β, β) = ∞;
• d(β, γ) = d(γ, β) visto que N (β, γ) = N (γ, β);
• Dados α, β, γ ∈ Σ, N1 = N (β, α), N2 = N (β, γ), N3 = N (α, γ) e sem perda de
generalidade N2 ≤ N3 , temos que αn = βn para todo |n| ≤ N2 . Logo, N2 ≤ N1 e
1
≤ 2N1 2 ≤ 2N1 2 + 2N1 3
2N1

⇐⇒ d(α, β) ≤ d(α, γ) + d(γ, β).

Logo, d é distância.
Observe que a topologia gerada pela métrica é mais fina que a topologia produto, visto
que toda bola é um cilindro. De fato, se α e β pertencem a uma bola de centro em α e raio
r, então d(α, β) < r. Desta forma, βn = αn para todo |n| < r e se algumas coordenadas
coincidem temos um cilindro.
Por outro lado, a topologia produto é mais fina que a topologia gerada pela métrica.
De fato, todo cilindro é interseção de imagens de bolas pelo operador deslocamento, que é
um homeomorfismo como será demonstrado a seguir. Então, todo cilindro é a interseção de
abertos da métrica. Desta forma, temos que a topologia gerada pela métrica coincide com a
topologia produto.

1.3

A Transformação Shift

Nesta seção vamos introduzir uma dinâmica σ : Σ → Σ no espaço Σ, chamada deslocamento (ou shift) de Bernoulli, onde σ((xn )n ) = (xn+1 )n . Os teoremas a seguir asseguram que
a transformação shift é um homeomorfismo.
Teorema 1.2 O deslocamento,definido no espaço de sequências bilaterais, é contı́nuo.
Demonstração. Dado ε > 0, existe N > 0 suficientemente grande tal que ε > N1 . Seja n
tal que
1
1
< .
i
2
N
1
Tome 0 < δ < 2i . Assim, para quaisquer x, y ∈ Σ, se d(x, y) < δ, então xi = yi
para −n − 1 ≤ i ≤ n + 1, e portanto σ(x) e σ(y) coincidem nas n-ésimas coordenadas
centrais, implicando que:
d(σ(x), σ(y)) <
4

1
1
<
<ε
i
2
N


O deslocamento a esquerda, definido no espaço de sequências bilaterais, é uma bijeção e
o deslocamento a direita σ̃((xn )n ) = (xn−1 ) é a sua inversa. Note também que

,...,nk
)
=
ω ∈ Σ : ωni+1 = αi ∀i = 1, ..., n
σ(Cαn11,...,α
k
é um cilindro, isto é, σ leva cilindros em cilindros. De forma análoga, vemos que a pré
imagem de um cilindro é ainda um cilindro. Logo, σ é um homeomorfismo.
Observe que o operador deslocamento não é injetivo quando definido no espaço de sequências
unilaterais com l sı́mbolos, isto é, no espaço Σ̃ = {α = (α0 , α1 , ...) : αi ∈ {1, 2, ..., l}, i ∈ Z}
,como o mostra o exemplo a seguir.
Exemplo 4 Sendo α = (1, 2, 2, ...) e β = (2, 2, 2, ...), temos que
σ(α) = σ(β) = (2, 2, 2, ...)
A restrição de σ a algum subconjunto fechado e invariante de Σ, é chamado de Sistema
Dinâmico Simbólico.

1.4

Medidas Invariantes

A teoria da medida foi desenvolvida no final do século XIX e no inı́cio do século XX por
Emile Borel, Henri Lebesgue, Johan Radon e Maurice Fréchet. As principais aplicações são:
• na fundamentação da integral de Lebesgue, que generaliza (com vantagens) a integral
de Riemann;
• Na axiomatização da teoria de probabilidade feita por Andrey Kolmogorov;
• na definição mais geral de espaços não euclidianos.
Abordaremos nesta seção alguns dos conceitos e resultados relevantes da teoria da medida
necessários para a discussão do Teorema de Szemerédi.
Uma medida é uma função dos subconjuntos (ou partes) de algum conjunto X, que
associa ”massas”a cada uma dessas partes. Uma medida deve satisfazer certas propriedades
intuitivas que idealizamos para uma função ”massa”.
Definição 1.5 Seja X um conjunto qualquer. B ⊂ P(X) é uma σ−álgebra se
i. ∅ ∈ B
ii. A ∈ B implica Ac ∈ B
iii. Ai ∈ B, para todo i = 1, 2, ..., implica ∪∞
i=1 Ai ∈ B.
O par (X, B) é chamado de espaço mensurável, enquanto um elemento B ∈ B é referido
como um conjunto mensurável.
5

Exemplo 5 Seja X um conjunto qualquer. Então, {∅, X} e P(X) são exemplos triviais de
σ−álgebra. São a menor e maior σ−álgebra, respectivamente, de X.
Exemplo 6 Se X é um conjunto não enumerável, então
{E ⊂ X : E é enumerável ou E c é enumerável}
é uma σ−álgebra, chamada σ−álgebra dos conjuntos enumeráveis ou coenumeráveis.
Exemplo 7 A interseção de uma famı́lia de σ−álgebras é uma σ−álgebra. Segue-se que, se
C ⊂ P(X), então existe uma menor σ−álgebra M(C) que contém C; existe pelo menos uma
σ−álgebra que contém C, a σ−álgebra P(X). M(C) é chamada σ−álgebra gerada por C.
Definição 1.6 Uma medida em (X, B) é uma função µ : B → [0, ∞] que é contavelmente
aditiva, isto é, se {Bi }i∈N for uma coleção dois a dois disjunta de elementos de B então
∞

µ( ∪ Bi ) =
n=1

∞
X

µ(Bi ).

i=1

Exemplo 8 Se X é qualquer conjunto não vazio, M = P(X) e f : X → [0, ∞) é uma
função qualquer, então f induz uma medida µ em M definindo-se:


P
P
f (x) : F é finito
µ(E) = x∈E f (x) := sup
x∈F

Em particular, se f (x) = 1 para todo x então µ é chamada a medida de contagem; se
f (x0 ) = 1 e f (x) = 0 para todo x 6= x0 , então µ é chamada a medida de Dirac ou medida de
ponto de massa.
Exemplo 9 Se X é um conjunto não enumerável, e M é a σ−álgebra dos conjuntos enumeráveis ou coenumeráveis, então a função µ definida por

0, se E é enumerável,
µ(E) =
1, se E é coenumerável
é uma medida.
Particularmente, se houver um elemento B de medida finita, então
µ(B) = µ(B ∪ ∅) = µ(B) ∪ µ(∅) ⇒ µ(∅) = 0.
Se a medida tiver imagem em [0, ∞) então diz-se que ela é finita. Se for finita, pode ser
normalizada para que µ(X) = 1, e neste caso é chamada de medida de probabilidade, ou
simplesmente de probabilidade. A tripla (X, B, µ) é chamada de espaço de medida, ou de
espaço de probabilidade se µ(X) = 1.

6

Definição 1.7 Seja (X, B, µ) um espaço mensurável. Diz-se que f : X → R é mensurável
se para todo boreleano B de R valer f −1 (B) ∈ B.
A mensurabilidade pode ser testada com conjuntos (c, ∞), pois eles geram a σ−álgebra
dos boreleanos de R. Se X for espaço topológico e B for a σ−álgebra de Borel de X então
qualquer função contı́nua será mensurável.
Com o intuito de definirmos integração de uma função simples, que será definida logo
abaixo, denotaremos por XA a função caracterı́stica de A:

0, se x ∈
/A
XA =
1, se x ∈ A
Definição 1.8 Seja (X, B, µ) espaço de probabilidade. Diz-se que f : X → R é simples se
f=

n
X

ai X A i ,

i=1

onde os A0i s são elementos dois a dois disjuntos de B.
Definição 1.9 A integral de uma função simples f =

n
P

ai XAi é dada por

i=1

Z
f dµ =

n
X

ai µ(Ai )

i=1

Nesse caso também dizemos que f preserva µ. O conceito acima faz sentido, pois a préimagem de um conjunto mensurável por uma transformação mensurável ainda é um conjunto
mensurável.
É fácil ver que qualquer função mensurável não negativa pode ser aproximada, por baixo
e monotonamente, por uma sequência de funções simples. A integral de f é definida como
sendo o limite das integrais das funções
Z simples, provando-se que independe da sequência
escolhida. Diz-se que f é integrável se f dµ < ∞ .
Para funções reais, basta decompor f = f+ − f− e dizer que f é integrável se f+ e f−
forem integráveis. A função f será integrável se, e somente se, |f | for integrável.
Teorema 1.3 (da ConvergênciaZMonótona)
Considere a sequência {f1 ≤ f2 ≤ ...} de funções

reais integráveis em (X, B, µ). Se
fn dµ for sequência limitada, então lim fn existe em
n→∞
Z
Z
quase todo ponto e (lim fn )dµ = lim fn dµ. Se a sequência não for limitada, então ou
lim fn não existe num conjunto de medida positiva ou lim fn existe num conjunto de medida
total mas, não é integrável.

7

Teorema 1.4 (Lema de Fatou) Seja {fn }n sequência
Z de funções mensuráveis, limitadas
fn dµ < ∞, então lim inf n fn é in-

inferiormente por uma função integrável. Se lim inf n
tegrável e
Z

Z
(lim inf fn )dµ = lim inf
n

n

fn dµ

Um exemplo que ilustra um pouco esse teorema e mostra que não precisa haver igualdade é
dado pelas funções fn : [0, 1] → R com

, se 0 ≤ x ≤ 1/n
 n2 x
2
2n − nx , se 1/n ≤ x ≤ 2/n
fn (x) =

0
, se 2/n ≤ x ≤ 1
onde as integrais são sempre iguais a 1, as funções são limitadas inferiormente por qualquer
função integrável não positiva, e a função limite é a função nula (não precisa que exista o
limite das funções para que o Teorema seja verdadeiro).
Segue-se o seguinte corolário deste último :
Teorema 1.5 (da Convergência Dominada) Se g é integrável e {fn }n é sequência de
funções mensuráveis com |fn | ≤ g q.t.p. e lim fn = f q.t.p., então f é integrável e
Z
Z
fn dµ = f dµ.
Definição 1.10 Seja (M, B, µ) um espaço de medida e seja f : M → M uma transformação
mensurável. Dizemos que a medida µ é invariante por f se
µ(E) = µ(f −1 (E)) para todo conjunto mensurável E ⊂ M .
Teorema 1.6 Sejam f : M → M uma transformação mensurável e µ uma medida em M .
Então f preserva µ se, e somente se,
Z
Z
φdµ = φ ◦ f dµ
para toda função µ−integrável φ : M → R.
Demonstração. Suponhamos que a medida µ é invariante, isto é, µ(B) = µ(f −1 (B)) para
todo conjunto mensurável B.
Z
XB dµ = µ(B) e µ(f

8

−1

Z
(B)) =

(XB ◦ f )dµ

O que mostra a igualdade para as funções caracterı́sticas e por linearidade da integral
é válida para funções simples. Vamos concluir agora que vale para toda função integrável.Dada qualquer função integrável φ : M → R, considere uma sequência (sn )n
de funções simples convergindo para φ e tal que |sn | ≤ |φ| para todo n. Então,
Z
Z
Z
Z
φdµ = lim sn dµ = lim (sn ◦ f )dµ = (φ ◦ f )dµ.
n

Z
Reciprocamente, se

n

Z
φ ◦ f dµ é suficiente mostrar que µ é invariante para

φdµ =

um conjunto fechado C qualquer. Seja {Un }n uma sequência decrescente de abertos
−1
∞
(Un ) = f −1 (C). Tome φn contı́nua que
tal que ∩∞
n=1 Un = C. Isso implica que ∩n=1 f
valha 1 em C e zero fora de Un . Então, φn ◦ f vale 1 em f −1 (C) e zero fora de f −1 (Un ).
Como µ é probabilidade, µ(Un ) converge a µ(C) e µ(f −1 (Un )) converge a µ(f −1 (C)).
Além disso,
Z
µ(C) ≤

φn dµ ≤ µ(Un ).

Z
Segue que,

Z
φdµ converge para µ(C). Analogamente,

φn ◦ f dµ converge para

µ(f −1 (C)).
Por hipótese
Z

Z
φn dµ =

φn ◦ f dµ ⇒ µ(C) = µ(f −1 (C))


9

Capı́tulo 2
Teoremas de Recorrência e Extensões
Naturais
2.1

Teorema de Recorrência de Birkhoff

Nesta Seção demonstraremos o Teorema de Recorrência de Birkhoff e decorrente desse a
sua versão múltipla, crucial para a conclusão do Teorema de Van der Waerden. Além desses,
também faremos uma breve discussão sobre o Teorema de Recorrência Múltipla de Poincaré
, a fim de dar uma ideia da demonstração do Teorema de Szemerédi.
Definição 2.1 Considere M um espaço topológico. Dizemos que um ponto x ∈ M é recorrente para uma transformação f : M → M se existe uma sequência de naturais nj → ∞ tal
que f nj (x) → x.
A versão simples do Teorema de Birkhoff investiga a existência de pontos recorrentes,
mais precisamente:
Teorema 2.1 (Birkhoff ) Seja f : M → M uma transformação contı́nua num espaço
métrico compacto M , então existe algum ponto x ∈ M que é recorrente para f .
Para fazermos a demonstração deste resultado , consideremos o lema a seguir.

Lema 2.1 Seja M espaço métrico compacto, f : M → M uma transformação
 contı́nua e I a
famı́lia de conjuntos fechados não vazios de M invariantes por f , isto é, I = X ⊂ M |X = X, f (X) ⊂ X
Então, um elemento X ∈ I é minimal para a relação de inclusão se, e somente, a órbita de
qualquer elemento x ∈ X é densa em X.
Demonstração Observe que I é uma famı́lia não vazia, pois pelo menos M ∈ I. Considere
X ⊂ M elemento minimal de I e x ∈ X. Note que o fecho da órbita de x, O(x) =
{f n : n ∈ Z} é um elemento de I. De fato,O(x) é não vazio, já que M é compacto,
fechado e invariante, pois dado
y ∈ O(x) ⇒ y = lim f nk (x) ⇒ f (y) = lim f (f nk (x))
10

devido a continuidade da função f . Esta última igualdade pode ser reescrita da seguinte
forma f (y) = lim f nk +1 (x) e desta forma concluı́mos que f (y) ∈ O(x), isto é, f (O(x)) ⊂
O(x). Além disso,
O(x) ⊂ X ⇒ O(x) ⊂ X, pois X é fechado.
Pela minimalidade de X concluı́mos que O(x) = X. Reciprocamente, suponha que a
órbita de qualquer elemento x ∈ X é densa em X, isto é, que O(x) = X para todo
x ∈ X e considere Y ∈ I tal que Y ⊂ X. Temos que, y ∈ Y ⇒ f n (y) ∈ Y para todo n
natural. Logo,
O(y) ⊂ Y ⇒ X = O(y) ⊂ Y ⇒ X = Y.
Portanto, X é minimal.

Desta forma, de acordo com o lema, é suficiente verificarmos que, mediante as hipóteses
dadas, a famı́lia I de conjuntos fechados, não vazios de M e invariantes por f possui elemento
minimal. Pois, terı́amos desta forma que todo elemento x ∈ X é recorrente para f , já que
ele escreve-se como limite de uma sequência de f n (x).
Demonstração do Teorema de Birkhoff. Considere a famı́lia I de conjuntos fechados
não vazios de M invariantes por f , isto é f (X) ⊂ X e {Xα } ∈ I um subconjunto
qualquer de I totalmente ordenado. Vamos mostrar que {Xα } admite algum minorante.
De fato, tome X = ∩α Xα e observe que X ⊂ Xα para todo α, é fechado, não vazio pois
os Xα são compactos e constituem uma famı́lia encaixada. Além disso, X também é
invariante por f pois, dado
x ∈ X ⇒ x ∈ Xα , ∀α ⇒ f (x) ∈ Xα , ∀α ⇒ f (x) ∈ X.
Logo, X é um minorante de {Xα } e pelo Lema de Zorn (lema 4.1, apêndice) I admite
elemento minimal.


2.2

Teorema de Recorrência Múltipla de Birkhoff

Trataremos agora de uma versão mais geral do teorema de Birkhoff, onde são consideradas várias transformações. Para nossos fins, é suficiente que tais transformações sejam
homeomorfismos, todavia o teorema que segue também é válido se as transformações forem
apenas contı́nuas (Seção 2.4) .

11

Teorema 2.2 Seja M um espaço métrico compacto e f1 , ..., fq : M → M homeomorfismos
que comutam entre si, isto é,fi ◦ fj = fj ◦ fi , então existe a ∈ M e uma sequência (nk )k → ∞
tal que
limfink (a) = a
k

para todo i = 1, ..., q.
Para demonstrarmos este resultado, faremos inicialmente a seguinte construção: F :
M q → M q definida no espaço produto M q = M com F (x1 , ..., xn ) = (f1 (x1 ), ..., fn (xn )),
onde as fi ’s são homeomorfismos. Defina a diagonal ∆q de M q como o conjunto formado
pelos pontos x̃ = (x, ..., x) ∈ M q . Assim, a conclusão do Teorema de Recorrência Múltipla
de Birkhoff pode ser equivalentemente interpretado da seguinte forma: existe ã ∈ ∆q e
(nk )k → ∞ tal que
limF nk (ã) = ã.
k

Usaremos indução no número q de transformações. Para q = 1 o teorema resume-se ao
Teorema de Recorrência de Birkhoff. Suponha então que o teorema vale para um número
q − 1 de homeomorfismos que comutam entre si, com q ≥ 2. Vamos provar que vale para a
famı́lia f1 , ..., fq .
Denote por G o grupo abeliano gerado pelos homeomorfismos f1 , ..., fq , com a operação de
composição de funções. Dizemos que um conjunto X é G−invariante quando g(X) ⊂ X,
para toda função g ∈ G.
Lema 2.2 A famı́lia de subconjuntos não vazios, fechados, G-invariantes de um compacto
M admite elemento minimal.
Demonstração. Considere I a famı́lia de subconjuntos não-vazios, fechados, G−invariantes
do compacto M e ∈ I totalmente ordenado. Defina X = ∩α Xα . Temos que, X ⊂
Xα ∀α, é fechado e {Xα } ∈ I para todo α, visto que os Xα são compactos e constituem
uma famı́lia encaixada. Além disso, X é G−invariante pois para todo homeomorfismo
g ∈ G e x ∈ X temos que g(x) ∈ Xα , ∀α.
Logo g(∩α Xα ) ⊂ ∩α Xα para todo α, donde concluı́mos que X é um minorante de {Xα }
e, pelo Lema de Zorn, I admite elemento minimal.

Desta forma, não perdemos a generalidade se considerarmos o espaço M como sendo
minimal. Essa informação será de suma importância, para a sequência de lemas auxiliares a
conclusão do teorema de Recorrência Múltipla de Birkhoff.
Para tal, façamos a construção da seguinte função:
φ : ∆q → [0, ∞), φ(x̃) = inf {d(F n (x̃), x̃) : n ≥ 1)}.

12

Note que φ é semicontı́nua, isto é, dado qualquer ε > 0, todo ponto x̃ admite alguma
vizinhança V tal que φ(ỹ) < φ(x̃) + ε. De fato, basta notar que dado x̃ ∈ ∆q e ỹ ∈ V de tal
forma que d(x̃, ỹ) < ε/2 temos que
d(F n (x̃), x̃) ≤ d(F n (x̃), F n (ỹ)) + d(F n (ỹ), ỹ) + d(x̃, ỹ) < ε + d(F n (ỹ), ỹ).
Logo, φ admite algum ponto ã de continuidade. Construiremos agora uma sequência de
resultados que levarão a conclusão de que esse ponto ã de continuidade satisfaz a conclusão
do Teorema.
Lema 2.3 Se M é minimal, então para todo aberto não vazio U ⊂ M existe um subconjunto
finito H ⊂ G tal que
M = ∪ h−1 (U )
h∈H

Demonstração. Dado x ∈ M temos que o fecho da sua órbita, O(x) = {g(x) : g ∈ G}, é
um subconjunto não vazio de M , fechado e G-invariante. Então, da minimalidade de
M , concluı́-se que O(x) é densa em M . Em particular, existe g ∈ G tal que g(x) ∈ U .
Assim, provamos que {g −1 (U ) : g ∈ G} é uma cobertura aberta de M . Da compacidade
de M , segue-se que existe uma subcobertura finita.

Note que a aplicação M → ∆q , x7→x̃ = (x, ..., x) é um homeomorfismo, então todo
aberto U ⊂ M corresponde a um aberto Ũ ⊂ ∆q via esse homeomorfismo. Dado qualquer
g ∈ G, representaremos por g̃ : M q → M q o homeomorfismo definido por g̃(x1 , ..., xq ) =
(g(x1 ), ..., g(xn )). Sendo G abeliano, então F comuta com g̃. Além disso, g̃ preserva a
diagonal ∆q . Aplicando o lema anterior no espaço ∆q , temos que
∆q = ∪ h−1 (U )
h∈H

Lema 2.4 Dado ε > 0 existem x̃, ỹ ∈ ∆q e n ≥ 1 tais que d(F n (x̃), ỹ) < ε.
Demonstração. Defina gi = fi ◦ fq−1 para cada i = 1, ..., q − 1. Como as fi comutam
entre si, segue-se o mesmo para as gi . Então, pela hipótese de indução existe y ∈ M e
(nk )k → ∞ tal que
limgink (y) = y
k

para todo i = 1, ..., q − 1. Denote xk = fq−nk (y) e considere x̃k = (xk , ..., xk ) ∈ ∆q .
Então,
nk
F nk (x̃k ) = (f1nk (xk ), ..., fq−1
(xk ), fqnk (xk ))
nk
nk
= (f1nk fq−nk (y), ..., fq−1
fq−nk (y), y) = (g1nk (y), ..., gq−1
(y), y)

que converge para (y, ..., y) quando k → ∞. O que conclui o lema para x̃ = x̃k ,
ỹ = (y, ..., y) e n = nk , para k suficientemente grande.
13


Mostraremos agora que o ponto ỹ do lema anterior é arbitrário.
Lema 2.5 Dado ε > 0 e z̃ ∈ ∆q existem w̃ ∈ ∆q e m ≥ 1 satisfazendo d(F m (w̃), z̃) < ε.
Demonstração. Dado ε > 0 e w̃ ∈ ∆q considere Ũ a bola de centro em z̃ e raio ε/2.
Então, pela observação do lema 7 existe um subconjunto finito H ⊂ G tal que ∆q =
∪ h−1 (Ũ ). Como os elementos de G são uniformemente contı́nuos, pois tratam-se de
h∈H

funções contı́nuas em um domı́nio compacto, então existe δ > 0 tal que
d(x̃1 , x̃2 ) < δ ⇒ d(h̃(x̃1 ), h̃(x̃2 )) < ε/2
para todo h ∈ H. Pelo lema anterior existem x̃, ỹ ∈ ∆q e n ≥ 1 tais que d(F n (x̃), ỹ) < ε.
Fixe h ∈ H tal que ỹ ∈ h̃−1 (Ũ ), isto é, h̃(ỹ) ∈ Ũ . Então,
d(h̃(F n (x̃)), z̃) ≤ d(h̃(F n (x̃)), h̃(ỹ)) + d(h̃(ỹ), z̃) < ε/2 + ε/2.
Tomando w̃ = h̃(ỹ) e notando que F n comuta com h̃ segue-se o resultado d(F n (w̃), z̃) <
ε.

Mostraremos agora que é possı́vel tomar x̃ = ỹ no lema anterior.
Lema 2.6 (Bowen) Dado ε > 0 existem ṽ ∈ ∆q e k ≥ 1 tal que d(F k (ṽ), ṽ) < ε.
Demonstração. Dado ε > 0 e z̃0 ∈ ∆q , considere as sequências εj , mj e z̃j , j ≥ 1, definidas
da seguinte forma: dado ε1 = ε/2. Então, pelo lema anterior existem z̃1 ∈ ∆q e
m1 ≥ 1 tais que d(F m1 (z̃1 ), z̃0 ) < ε1 . Da continidade de F m1 , existe um ε2 < ε1 tal que
d(z̃, z̃1 ) < ε2 implica d(F m1 (z̃), z̃0 ) < ε1 .
Em geral, dado qualquer j ≥ 2 e z̃j−1 ∈ ∆q , temos pelo lema anterior que: existem
mj ≥ 1 e z̃j ∈ ∆q tal que d(F mj (z̃j ), z̃j−1 ) < εj . Pela continuidade de F mj , existe
εj+1 < εj tal que d(z̃, z̃j ) < εj+1 implica d(F mj (z̃), z̃j−1 ) < εj . Em particular, para
todo i < j temos
d(F mi+1 +...+mj (z̃j ), z̃i ) < εi+1 ≤ ε/2.
Sendo ∆q compacto podemos encontrar, i, j com i < j tais que d(z̃i , z̃j ) < ε/2. Tomando k = mi+1 + ... + mj , temos
d(F k (z̃j ), z̃j ) ≤ d(F k (z̃j ), z̃i ) + d(z̃j , z̃i ) < ε.


14

Estes resultados são suficientes para concluirmos que, de fato o ponto de continuidade ã
de φ, definida inicialmente satisfaz a conclusão do Teorema. Para isso, observe que φ(ã) = 0.
De fato, suponha que φ(ã) > 0. Então, por continuidade, existem β > 0 e uma vizinhança
V de ã tais que φ(ỹ) ≥ β > 0 para todo ỹ ∈ V . Logo,
d(F n (ỹ), ỹ) ≥ β para todo y ∈ V e todo n ≥ 1
Por outro lado, já vimos que para todo x̃ ∈ ∆q existe h ∈ H tal que h(x̃) ∈ V . Como as
transformações h são uniformemente contı́nuas, podemos fixar α > 0 tal que:
d(w̃, z̃) < α ⇒ d(h̃(w̃), h̃(z̃)) < β, para toda h ∈ H.
Então, pelo Lema de Bowen e lembrando que F n comuta com h̃, existe n ≥ 1 tal que
d(x̃, F n (x̃)) < α ⇒ d(h̃(x̃), F n (h̃(x̃))) < β.
Chegamos a uma contradição, concluı́ndo assim que φ(0) = 0. Logo, existe uma sequência
(nk )k → ∞ tal que d(F n (ã), ã) → 0. 

2.3

Teorema de Recorrência múltipla de Poincaré

O Teorema de Recorrência Múltipla de Poincaré afirma, basicamente, que existe algum tempo
n tal que os iterados de um subconjunto com medida positiva de pontos de E retornam para
E, simultaneamente para todas as transformações fi , nesse momento n. Mais precisamente:
Teorema 2.3 Seja (M, B, µ) um espaço de probabilidade e sejam fi : M → M , i = 1, ..., q
transformações mensuráveis que preservam µ e que comutam entre si. Então, para qualquer
conjunto E ⊂ M com medida positiva, existe n ≥ 1 tal que
µ(E ∩ f1−n (E) ∩ ... ∩ fq−n (E)) > 0.
A demonstração deste teorema pode ser encontrada no livro de Fustenberg [5], e sua
apresentação não será feita neste trabalho. Vamos apenas mencioná-lo a fim de seu na prova
do teorema de Szemerédi sobre existência de progressões aritméticas em subconjuntos densos
dos números inteiros.

2.4

Extensões Naturais

Com o intuito de generalizar o Teorema de Recorrência Múltipla de Birkhoff, faremos
uma breve análise ao conceito de extensões naturais, que nos permite reduzir a demostração
de casos mais gerais de aplicações simplesmente contı́nuas, ao caso de funções inversı́veis.
Dada uma transformação sobrejetiva f : M → M é sempre possı́vel encontrar uma
extensão f˜ : M̃ → M̃ que é invertı́vel, isto é, existe uma aplicação sobrejetiva π : M̃ → M̃
tal que π ◦ f˜ = f ◦ π.
15

De fato, iniciaremos tomando M̃ como o conjunto de todas as pré órbitas de f , isto é,
o conjunto de todas as sequências (xn )n≤0 indexadas pelos números inteiros não positivos e
satisfazendo f (xn ) = xn+1 para todo n < 0. Considere a aplicação π : M̃ → M que associa
a cada sequência (xn )n≤0 o seu termo x0 . Claramente, π(M̃ ) = M , pois π(M̃ ) ⊂ M e todo
x ∈ M é o termo x0 de alguma sequência em M̃ . Por fim, definimos f˜ : M̃ → M̃ como sendo
o deslocamento a esquerda :
f˜(..., xn , ..., x0 ) = (..., xn , ..., x0 , f (x0 )).
De acordo com a construção acima, temos que
π ◦ f˜(..., xn , ..., x0 ) = f (x0 ) = f ◦ π(..., xn , ..., x0 ).
Além disso, f˜ é invertı́vel. Sua inversa é o deslocamento a direita:
(..., yn , ..., y−1 , y0 ) 7→ (..., yn , ..., y−2 , y−1 ).
A seguir serão demonstrados resultados com o intuito de discutir a noção de extensões naturais para transformações que comutam entre si. Para os três próximos lemas consideraremos
M um espaço compacto, f1 , ...., fq : M → M transformações contı́nuas, sobrejetivas que
comutam entre si e M̂ o conjunto das sequências (xn1 ,...,nq )n1 ,...,nq ≤0 , indexadas pelas q-uplas
de inteiros não positivos, tais que
fi (xn1 ,...,ni ,...,nq ) = xn1 ,...,ni+1 ,...,nq para todo i e todo (n1 , ..., nq ).
Lema 2.7 M̂ é um espaço métrico compacto. Além disso, M̂ é metrizável se M é metrizável.
q

Demonstração. Observe que M̂ é um subconjunto fechado do compacto M Z− , portanto
compacto. Além disso, considere d uma distância em M . Então,
X
ˆ n )n , (yn )n ) =
2n1 +...+nq min {d((xn )n , (yn )n ), 1}
d((x
n1 ,...,nq ≤0

define uma distância em M̂ , onde n = (n1 , ..., nq ). De fato,
ˆ n )n , (xn )n ) = 0 , pois min {d((xn )n , (xn )n ), 1)} = 0 já que d é métrica.
• d((x
ˆ n )n , (yn )n ) = d((y
ˆ n )n , (xn )n ).
• Claramente, d((x
• Sendo d distância temos que d((xn )n , (yn )n ) ≤ d((xn )n , (zn )n ) + d((zn )n , (yn )n ) e
assim
X
ˆ n )n , (yn )n ) =
d((x
2n1 +...+nq min {d((xn )n , (yn )n ), 1}
n1 ,...,nq ≤0

≤

X

2n1 +...+nq min {d((xn )n , (zn )n ) + d((zn )n , (zn )n ), 1}

n1 ,...,nq ≤0

≤

X

2n1 +...+nq min {d((xn )n , (zn )n ), 1}

n1 ,...,nq ≤0

+

X

ˆ n )n , (zn )n ) + d((z
ˆ n )n , (yn )n )
2n1 +...+nq min {d((zn )n , (yn )n ), 1} = d((x

n1 ,...,nq ≤0

16


Lema 2.8 Seja π : M̂ → M a aplicação que envia (xn1 ,...,nq )n1 ,...,nq ≤0 no ponto x0,...,0 e, para
cada i, f̂i : M̂ → M̂ a aplicação que envia (xn1 ,...,ni ,...,nq )n1 ,...,nq ≤0 em (xn1 ,...,ni+1 ,...,nq )n1 ,...,nq ≤0 .
Cada f̂i é um homeomorfismo com π◦ f̂i = f̂i ◦π. Além disso, esses homeomorfismos comutam
entre si.
Demonstração. A inversa de f̂i envia (xn1 ,...,ni ,...,nq )n1 ,...,nq ≤0 no ponto (xn1 ,...,ni−1 ,...,nq )n1 ,...,nq ≤0 .
Além disso tanto f̂i quanto a sua inversa são contı́nuas, pois cada coordenada da imagem é função contı́nua de um número finito de coordenadas da variável. Temos também,
por definição:
π ◦ f̂i ((xn1 ,...,ni ,...,nq )n1 ,...,nq ≤0 ) = x0,...,1,...,0 = f̂i ◦ π((xn1 ,...,ni ,...,nq )n1 ,...,nq ≤0 ).
Por fim,
f̂i ◦ fˆj ((xn1 ,...,ni ,...,...,nj ,...,nq )n1 ,...,nq ≤0 ) = (xn1 ,...,ni+1 ,...,...,nj+1 ,...,nq )n1 ,...,nq ≤0
= fˆj ◦ f̂i ((xn1 ,...,ni ,...,...,nj ,...,nq )n1 ,...,nq ≤0 )

Lema 2.9 A aplicação π : M̂ → M a aplicação que envia (xn1 ,...,nq )n1 ,...,nq ≤0 no ponto x0,...,0
é contı́nua e sobrejetiva. Em particular, M̂ é não vazio.
Demonstração. A aplicação π é contı́nua para a topologia herdada do espaço produto.
Para mostrarmos a sobrejetividade, considere x ∈ M . Como supomos anteriormente as
f1 , ..., fq são sobrejetivas,contı́nuas e comutam entre si, então podemos encontrar uma
sequência (xn )n≤0 em M tal que x0 = 0 e f1 ...fn (xn ) = (xn+1 ) para cada n < 0. Defina
xn1 ,...,nq = f n1 −n ...f nq −n (xn ) para qualquer n ≤ min {n1 , ..., nq }.
Note que esta definição não depende do número n. De fato, seja m ≤ min {n1 , ..., nq }
temos que
f n1 −m ...f nq −m (xm ) = f n1 −m ...f nq−1 −m (xm,m,...,nq ) = f n1 −m (xm,...,nq ) = xn1 ,...,nq .
Além disso, π(xn1 ,...,nq ) = π(f n1 −n ...f nq −n (xn )) = x.

Teorema 2.4 Seja M espaço métrico compacto e g1 , ..., gq : M → M transformações contı́nuas
nq
n1
n
n
que comutam entre si. Defina Mg = ∩∞
n=1 g1 ...gq (M ). Então, Mg = ∩n1 ,...,nq g1 ...gq (M ),
onde a interseção é sobre todas as q-uplas (n1 , ..., nq ) com ni ≥ 1 para todo i. Além disso,
gi (Mg ) ⊂ Mg e a restrição fi = gi |Mg é sobrejetiva para todo i.
17

n

n
n
Demonstração. Claramente ∩n1 ,...,nq g1n1 ...gq q (M ) ⊂ ∩∞
n=1 g1 ...gq (M ), isto é,

∩n1 ,...,nq g1n1 ...gqnq (M ) ⊂ Mg .
Por outro lado, note que se tomarmos n = max {n1 , ..., nq }, então
∩n1 ,...,nq g1n ...gqn (M ) ⊂ ∩n1 ,...,nq g1n1 ...gqnq (M ).
De fato,sejam n = max {n1 , ..., nq } e y ∈ g1n ...gqn (M ). Então, existe x ∈ M tal que
y = g1n ...gqn (x) e podemos escrever gin = gimi gini ,onde mi + ni = n para todo i = 1, ..., q.
Daı́,
m

n

y = g1n ...gqn (x) = y = g1m1 g1n1 g2m2 g2n2 ...gq q gq q (x)
Usando o fato que as transformações gi comutam entre si, podemos reescrever a última
igualdade da seguinte forma:
n

m

n

n

y = (g1n1 g2n2 ...gq q )(g1m1 g2m2 ...gq q )(x) = g1n1 g2n2 ...gq q g1n1 g2n2 ...gq q (x̃)
m

onde x̃ = g1m1 g2m2 ...gq q (x) ∈ M .
Assim,
n

n

q
n1
n
n
y ∈ g1n1 ...gq q (M ) ⇒ ∩∞
n=1 g1 ...gq (M ) ⊂ ∩n1 ,...,nq g1 ...gq (M )

n

n

⇒ Mg ⊂ ∩n1 ,...,nq g1n1 ...gq q (M ) ⇒ Mg = ∩n1 ,...,nq g1n1 ...gq q (M ).
n

Desta forma, dado y ∈ Mg existe um xn ∈ M tal que y = g1n1 g2n2 ...gq q (xn ), para
cada q−upla (n1 , ..., nq ). Desta forma, gi (Mg ) ⊂ Mg . Por fim, para concluirmos a
sobrejetividade de fi = gi |Mg basta mostrar que Mg ⊂ gi (Mg ). Para tal, considere
y ∈ Mg . Então, de acordo com o que fora construı́do, para cada n ≥ 1 existem
zn ∈ M tal que y = gi (g1n g2n ...gqn (zn )). Seja z o ponto de acumulação da sequência
(g1n g2n ...gqn (zn ))n , temos que z ∈ Mg e z = gi−1 (y). Logo, y ∈ gi (Mg ).
Mediante estes resultados, podemos agora estender a demonstração do Teorema de Recorrência Múltipla de Birkhoff para o caso em que as transformações fi não são necessariamente invertı́veis. De fato, pelo teorema anterior não é restrição supor que as transformações
f1 , ..., fq são sobrejetivas. Sejam fˆ1 , ..., fˆq : M̂ → M̂ as extensões naturais, no sentido do
lema 2.7. Pelo caso invertı́vel do Teorema de Recorrência Múltipla de Birkhoff, existe algum
x̂ ∈ M̂ que é simultaneamente recorrente para fˆ1 , ..., fˆq , isto é, existe (nk )k → ∞ e x̂ ∈ M̂
tal que limfink (x̂) = x̂. Daı́,
k

limfink (π(x̂)) = limπfink (x̂) = π(x̂).
k

k

Portanto, x = π(x̂) é simultaneamente recorrente para f1 , ..., fq .
18

Capı́tulo 3
Teorema de van der Waerden
Vamos provar, nesta seção, um importante resultado da Aritmética Combinatória obtido
originalmente pelo matemático holandês Bartel van der Waerden. Para tal, faremos uso de
uma importante ferramenta de Sistemas Dinâmicos, a dinâmica simbólica.
Definição 3.1 Uma progressão aritmética finita é uma sequência da forma m + n, m +
2n, ..., m + qn, com m ∈ Z e n, q ≥ 1. O número q é chamado comprimento da progressão.
Definição 3.2 Chamamos de partição finita do conjunto dos números inteiros Z, a qualquer famı́lia finita de conjuntos S1 , ..., Sk ⊂ Z, dois a dois disjuntos, cuja união é todo o
Z.
Exemplo 10 Z = S1 ∪ S2 , onde S1 é o conjunto dos números inteiros pares e S2 os ı́mpares.
Observe que toda sequência α = (αn )n∈Z ∈ Σ determina uma partição finita de Z da
seguinte forma Si = {n ∈ Z : αn = i}. Bem como, toda partição de Z faz corresponder um
elemento α ∈ Σ da forma:
αn = i ⇒ n ∈ Si ,
onde Σ = {1, ..., l}Z .
Teorema 3.1 (Van der Waerden) Dada qualquer partição finita {S1 , S2 , ..., Sl } de Z existe
algum j ∈ 1, ..., l tal que Sj contém progressões aritméticas de todos os comprimentos,isto é,
para todo q ≥ 1 existem m ∈ Z e n ≥ 1 tais que m + in ∈ Sj para todo 1 ≤ i ≤ q.
Demonstração. Note que, com o dicionário exposto acima é suficiente mostrarmos que para
todo α ∈ Σ e todo q ≥ 1 existem n ≥ 1 e m ∈ Z tais que αm+n = ... = αm+qn = j, pois
desta forma terı́amos que m + n, ..., m + qn ∈ Sj .
Já vimos que , d(β, γ) = 2−N (β,γ) , onde N (β, γ) = max {N ≥ 0 : βn = γn , ∀n ∈ Z, |n| < N }
define uma métrica em Σ e, além disso, observe que d(β, γ) < 1 se e somente se β0 = γ0 .
Consideremos agora o fecho da órbita de α ∈ Σ: Z = {σ n (α) : n ∈ Z}. Temos então que
Z é compacto, pois é um subconjunto fechado do compacto Σ. Além disso, Z também
19

é invariante pelo deslocamento de Bernoulli. De fato, se β ∈ Z então β = σ n (α) para
algum n ∈ Z. Assim,
σ(β) = σ(σ n (αn )) = σ n+1 (αn ) ⇒ σ(β) ∈ Z.
Dado um número q arbitrário, construiremos as transformações f1 = σ, f2 = σ 2 ,...,fq =
σ q definidas de Z em Z. Claramente estas funções comutam entre si, pois fi ◦ fj =
σ i σ j = σ i+j = σ j+i = σ j σ i = fj ◦ fi . Logo, pelo Teorema de Recorrência Múltipla de
Birkhof, existe um θ ∈ Z e uma sequência (nk )k → ∞ tal que
limfink (θ) = θ para todo i = 1, ..., q
k

⇒ limσ ink (θ) = θ para todo i = 1, ..., q
k

Em particular fixando um n = nj tal que σ n (θ), σ 2n (θ),...,σ qn (θ) estão a uma distância
menor que 12 de θ, temos que:
d(σ in (θ), σ jn (θ)) ≤ d(σ in (θ), θ) + d(σ jn (θ), θ) = d(fin (θ), θ) + d(fjn (θ), θ) < 12 + 21 = 1
para todo 1 ≤ i, j ≤ q. Sendo θ ∈ Z podemos encontrar um m ∈ Z tal que σ m (α) está
muito próximo de θ e por continuidade da aplicação σ temos que
d(σ in (σ m (α)), σ jn (σ m (α))) < 1 ⇒ d(σ m+in (α), σ m+jn (α)) < 1
para todo 1 ≤ i, j ≤ q.
Segundo a observação feita no inı́cio desta demonstração, com respeito a distância, a
última desigualdade só ocorrerá se os elementos que ocupam a posição 0, das sequências
envolvidas, forem coincidentes.
Logo,
αm+n = ... = αm+qn = k ⇒ m + n, ..., m + qn ∈ Sk , para algum k = 1, ..., l.

Os teoremas do tipo Van der Waerden tem sido extensivamente estudados nos últimos
anos. Eles enquadram-se na classe de problemas conhecidos como extremais. Nestes tipos
de problemas, normalmente procura-se funções limiares para o tamanho de certas estruturas
de modo que sempre seja possı́vel encontrar nestas estruturas uma certa subestrutura. Uma
teoria mais geral desses tipos de problemas e encontrada nas literaturas que abordam a teoria
de Ramsey ergódica que, por sua vez, aborda questões bem mais gerais, adentrando no campo
da teoria dos grafos.
20

Posteriormente, os matemáticos húngaros Pal Erdos e Pal Turan formularam um resultado
mais forte que o Teorema de van der Waerden: todo conjunto S com densidade superior positiva contém sequências aritméticas de tamanho arbitrário. Essa conjectura foi demonstrada
pelo matemático húngaro, Endre Szemerédi, há quase quatro décadas. Tal demonstração
fora de natureza essencialmente combinatória. No entanto, em 1977, Fustenberg proporcionou um desenvolvimento muito importante para ramos da matemática, com a apresentação
de uma demonstração do Teorema de Szemerédi usando argumentos de Teoria Ergódica.

3.1

Outras Formas do Teorema de van der Waerden

Nesta seção, faremos breves abordagens a outras versões do teorema de van der Waerden
observando as analogias entre estas formas e a versão já comentada via sistemas dinâmicos.
Iniciaremos com a sua forma original, isto é, a sua primeira versão via combinatória através
do método de colorir, a começar explanando em que consiste tal método.
Imagine que dispomos de duas cores, azul(A) e vermelho(V), para colorir os números do
conjunto {1, ..., 9}. Temos, por exemplo:
1 2 3 4 5 6 7 8 9
V V A A V V A A V
Note que, nesta 2-coloração, há a aparição de uma sequência de três números com a mesma
cor e equidistantes, estes são: 1, 5, 9, todos vermelhos.
Outra 2-coloração de {1, ..., 9} pode ser dada por:
1 2 3 4 5 6 7 8 9
V A V A A V A A V
Novamente ressaltamos a aparição de uma sequência de 3 números com a mesma cor e
equidistantes: 2, 5, 8, todos azuis.
Observe que não conseguimos o mesmo feito de uma 2-coloração do conjunto {1, ..., 8},
como por exemplo:
1 2 3 4 5 6 7 8
V A V A A V A A
Generalizaremos a seguir estas observações.
Definição 3.3 Dada uma coloração de um subconjunto de N, chamaremos de progressão
aritmética monocromática, k − P A, a progressão aritmética de comprimento k tal que todos
os elementos tem a mesma cor.
Fazendo analogia as terminologias utilizadas na versão via sistemas dinâmicos, é fácil ver
que o método de colorir um subconjunto de Z em Combinatória é equivalente a construir
uma partição deste conjunto, isto é, consiste em considerar partes disjuntas do conjunto dado
e cuja união dessas partes resulta no original.
21

Observe que nas duas primeiras 2−coloração de {1, ..., 9} encontramos progressões aritméticas
de monocromáticas de comprimento k = 3, isto é, encontramos uma 3−PA. Já na coloração
de {1, ..., 8} não conseguimos encontrar uma 3−PA. Vamos formalizar estes resultados a
seguir e, para tal, faremos as seguintes convenções:
• N = {1, 2, 3, ...}, isto é, não incluiremos o 0 nesta lista.
• Se m ∈ N, então [m] = {1, ..., m}.
Mediante estes conceitos segue-se o Teorema de van der Waerden, provado pelo próprio
e cuja demonstração será omitida neste trabalho, pois foge do nosso objetivo.
Teorema 3.2 Sejam k ≥ 1 e c ≥ 1. Então, existe W tal que para cada c−coloração X :
[W ] → [c] existe uma k − P A monocromática, isto é, existem a, d ∈ N tal que:
X (a) = X (a + d) = ... = X (a + (k − 1)d).
Em suma, de todas as formas que partimos o conjunto [W ] em subconjuntos disjuntos
sempre existirá progressões aritméticas de comprimentos arbitrários em, pelo menos, um
dos subconjuntos que formam a partição. Nesta versão Combinatória as partições serão
obtidas por meio de colorações e a conclusão é que sempre existem progressões aritméticas
de comprimento arbitrários com todos os seus termos pintados de uma única cor e esse
resultado vale para partições ou colorações arbitrárias.
Obviamente o número W referido no teorema não é único, por exemplo se k = 3 e c = 2,
então qualquer W ≥ 9 satisfaz o teorema de van der Waerden. De fato, para obtermos uma
progressão aritmética monocromática de comprimento 3 devemos ter inicialmente W ≥ 3.
Note que para [W ] = [8] a seguinte coloração não apresenta 3 − P A monocromática:
1 2 3 4 5 6 7 8
V V A A V V A A
Desta forma, não haverá uma 3 − P A monocromática na mesma coloração restrita a [W ],
para W ≤ 7.
Se [W ] = [9] e na predisposição das cores tivermos até 3 A’s sempre aparecerá uma
sequência de 3 V ’s seguidos. Então, é suficiente analisar apenas os seguintes casos:
1. (3A e 6V ) Se os 3A’s estiverem juntos, em qualquer posição, esta sequência já caracteriza a 3 − P A monocromática.
1 2 3 4 5 6 7 8 9
A A A V V V V V V
Mantendo agora um bloco 2A sempre junto e em qualquer posição, há sempre a aparição
de 3 − P A’s de razão 1:

22

1 2 3 4 5 6 7 8 9
A A V V V A V V V
Se os 3A’s estiverem todos separados, há a aparição de Se os 3P A’s monocromáticas
de razões 1 e 2:
1 2 3 4 5 6 7 8 9
A V V V V A V A V
2. (4A e 5V ) Se tivermos 4A’s ou 3A’s juntos, esta predisposição já caracteriza a aparição
de 3P A’s da cor A. Em qualquer outro caso contrário ao sitado, há a aparição de 3P A’s
monocromáticas de razão 1 ou 2.
Todos os A’s separados:
1 2 3 4 5 6 7 8 9
A V A V V A V A V
Dois blocos de 2 A’s:
1 2 3 4 5 6 7 8 9
A A V V V A A V V
Apenas um bloco de 2 A’s:
1 2 3 4 5 6 7 8 9
A A V V V A V A V
Desta forma, concluı́mos que 9 é o menor número que satisfaz o teorema de van der
Waerden. Este menor número W que satisfaz o teorema recebe nomenclatura especial, como
segue na definição:
Definição 3.4 Sejam k, c ∈ N. O número W (k, c) é o menor valor W que satisfaz o Teorema
de van der Waerden e é denominado o número de van der Waerden.
Exemplo 11 Se c = 1, então W (k, c) = k, visto que com uma única cor a própria sequência
[k] forma uma k−PA.
Exemplo 12 Se k = 1, então W (k, c) = 1, visto que uma 1−PA é formada por qualquer
termo simples.
Exemplo 13 Se k = 2, então W (2, c) = c + 1 pelo princı́pio da casa dos pombos.
Inspecionar o número de van der Waerden consiste em um processo exaustivo, apesar de
simples, todavia o resultado a seguir estima limites inferiores para W (k, c).
23

Teorema 3.3 Para todo k e c, tem-se W (k, c) ≥

√

k − 1c(k−1)/2 .

Demonstração. Seja W o número em questão. Tentaremos encontrar uma c−coloração de
[W ] tal que não possua uma k − P A monocromática.
Considere o seguinte experimento: para cada i ∈ [W ] escolha aleatoriamente uma cor
de [c] para i. A distribuição é uniforme. Primeiro escolhemos a cor da k − P A formada.
Seja c a opção. Em seguida, escolhemos o primeiro valor da k − P A. Seja a o valor.
Existem, no máximo, W opções. Agora, escolha um valor que difere d do ponto a. Desta
forma, temos no máximo W/(k − 1) opções. Uma vez que estes estão determinados, k
números distintos de mesma cor serão determinados. A saber:
{a, a + d, a + 2d, ..., a + (k − 1)d} .
Temos W − k valores a esquerda. Então, o número de colorações é limitado por
cW 2 cW −k /k − 1. Desta forma, a probabilidade de uma c−coloração ser uma k − P A
monocromática é limitada por
W2
cW 2 cW −k
=
.
(k − 1)cW
(k − 1)ck−1
Este número é menor que 1, então a probabilidade de uma k − P A não monocromática
deve ser positiva, de modo que tal coloração deve existir. Temos então:
√
W 2 < (k − 1)ck−1 ⇒ W < c(k−1)/2 k − 1.
√
Portanto, existe uma c−coloração de√(c(k−1)/2 − 1) k − 1 sem uma k − P A monocromática. Então, W (k, c) ≥ c(k−1)/2 k − 1. Note que a prova deste teorema foi não
construtiva, uma vez que não foi construı́da uma coloração.

Uma vez clara a ideia central do Teorema de van der Waerden que consiste em colorir o
conjunto dos números naturais, poderı́amos tentar imaginar uma coloração de N × N ou de
N × N × N.
Definição 3.5 Sejam k, d ≥ 1 e (a0 , a1 ) ∈ Z × Z. Denotaremos por grade com canto (a0 , a1 )
e diferença d o conjunto de pontos:
k × k = {(a0 , a1 ) + (id, jd)|0 ≤ i, j ≤ k − 1}
Quando o canto não for especificado a grade será apenas referida como k × k.
O seguinte resultado trata da forma multidimensional do Teorema de van der Waerden:
Teorema 3.4 Para todo c ∈ N existe um inteiro G = G(c) tal que para toda c−coloração de
G(c) × G(c) existe um quadrado que possui os quatro lados com a mesma cor.
24

3.2

Polinômio de van der Waerden

Atentando novamente para a essência do teorema de van der Waerden, que consiste na
busca de progressões aritméticas de comprimentos k, arbitrários, é possı́vel visualizar uma
progressão aritmética com estrutura polinomial da seguinte forma:
a, a + p1 (d), ..., a + pk (d)
onde pi (x) = ix.
Denotaremos por Z o conjunto dos números inteiros e por Z[x] o conjunto dos polinômios
com coeficientes inteiros e mediante este modo de ver a progressão aritmética, na forma
polinomial, poderı́amos idealizar que a conclusão do teorema de van der Waerden poderia
ser equivalente a seguinte afirmação:
Afirmação: Para cada polinômio p1 (x), ..., pk (x) ∈ Z[x] e para cada número natural c,
existe um W tal que, para alguma c−coloração X : [W ] → [c] existem a, d ∈ N tais
que:
X (a) = X (a + p1 (d)) = X (a + p2 (d)) = ... = X (a + pk (d)).
Todavia, esta colocação é falsa, pois se considerarmos por exemplo k = 1, p1 (x) = 1 e
c = 2 em qualquer 2−coloração de [W ] há a aparição de pelo menos dois números consecutivos
com cores distintas. O fato é que a mesma só será válida se os termos constantes de todos
os polinômios forem nulos. Bergelson e Leibman foram os primeiros a provar esta afirmação.
Logo, teorema polinomial equivalente ao teorema de van der Waerden seria:
Teorema 3.5 (Teorema Polinomial de van der Waerden) Para cada polinômio
p1 (x), ..., pk (x) ∈ Z[x], com pi (0) = 0 para todo i = 1, ..., k
e para cada número natural c, existe um W tal que, para cada c−coloração X : [W ] → [c]
existem a, d ∈ N tais que:
X (a) = X (a + p1 (d)) = X (a + p2 (d)) = ... = X (a + pk (d)).
De forma análoga a versão combinatória do teorema de van der Waerden também definese o número de van der Waerden nesta versão, porém estes números agora dependem dos
polinômios p1 , ..., pk ∈ Z[x], como segue a definição:
Definição 3.6 Sejam p1 , ..., pk ∈ Z[x] e c ∈ N. W (p1 , ..., pk ; c) é o menor W que satisfaz o
Teorema Polinomial de van der Waerden, denominado: o número do polinômio de van der
Waerden.
O Teorema Polinomial de van der Waerden foi provado para k = 1 por Furstenberg (Ergodic
behavior of diagonal measures and a theorem of Szemerédi’s on arithmétic progressions) e
Sarkozy (On difference sets of sequences of integers), independentes. A prova original deste
resultado foi feita por Bergelson e Leibman usando métodos ergódicos. Também fora dada
uma prova usando técnicas de combinatória, feita por Walters.
A existência de infinitas progressões polinomiais formadas por primos foi demonstrada
por Tao e Ziegler, com a seguinte versão:
25

Teorema 3.6 Sejam p1 , ..., pk ∈ Z[x], onde pi (m) = (i − 1)m são polinômios com valores
inteiros. Dado ε > 0 existem infinitos inteiros x e m tais que 1 ≤ m ≤ x(ε) e x+p1 (m), ..., x+
pk (m) são primos.

26

Capı́tulo 4
Demonstração do Teorema de
Szemerédi
Nesta seção daremos uma prova do Teorema de Szemerédi, o qual afirma que todo subconjunto de Z com densidade superior positiva contém progressões aritméticas de tamanhos
arbitrários. Para tal, serão utilizados elementos da Teoria Ergódica, que segue a linha de
raciocı́nio da prova dinâmica do teorema de van der Waerden, inclusive faz uso do mesmo
dicionário entre partições de Z e sequências de inteiros.
Definição 4.1 Chamaremos de intervalo do conjunto dos números inteiros Z qualquer subconjunto I da forma {n ∈ Z : a ≤ n ≤ b} com a ≤ b. A cardinalidade do conjunto é o número
#I = b − a.
Para enunciarmos o teorema de Szemerédi daremos uma definição de densidade superior de
um subconjunto de Z, equivalente a dada em 3.5.
Definição 4.2 A densidade superior Ds (S) de um subconjunto S de Z é o número
#(S ∩ I)
#I
#I→∞

Ds (S) = lim sup
onde I representa qualquer intervalo de Z.

Em outras palavras, Ds (S) é o maior número D tal que existe uma sequência de intervalos
Ij ⊂ Z satisfazendo:
#I → ∞ e

#(S∩Ij )
→ D.
#Ij

Exemplo 14 Seja S = {n2 : n ∈ N} = {1, 4, 9, 16, 25, ...} e I um intervalo de Z com cardinalidade n. Temos que
Ds (S) = lim sup
n→∞

√
#{j 2 :1≤j 2 ≤n}
n
≤
→ 0, quando n → ∞.
n
n

Logo, Ds (S) = 0.
27

Exemplo 15 Considere S ={n ∈ N: n é primo} e I um intervalo de Z com cardinalidade
n. Temos que
Ds (S) = lim sup #{p−primo:1≤p≤n}
= lim sup π(n)
→0
n
n
n→∞

n→∞

onde, pelo Teorema Fundamental dos Números Primos, π(n) ∼
= logn n .
Exemplo 16 Seja S o conjunto dos números pares. Dado qualquer intervalo I de Z, temos
que #(S ∩ I) = #I/2 se o cardinal de I for par e #(S ∩ I) = (#I ± 1)/2 se o cardinal de I
for ı́mpar, onde o sinal ± é positivo se o menor elemento de I for um número par e negativo
caso contrário. Temos então Ds (S) = 1/2.
Exemplo 17 Seja S o seguinte subconjunto de Z:
S = {1, 3, 4, 7, 8, 9, 13, 14, 15, 16, 21, 22, 23, 24, 25, 31, 32, 33, 34, 35, 26, 43...} .
Isto é, para cada k ≥ 1 incluı́mos em S um bloco de k inteiros consecutivos e omitimos
os k inteiros seguintes. Este conjunto contém intervalos com comprimentos arbitrariamente
grandes . Logo, Ds (S) = 1.
Note que nos dois últimos exemplos o conjunto S contém progressões aritméticas de tamanhos
arbitrários , inclusive no exemplo 4.3 S contém progressões aritméticas de comprimento
infinito o que não ocorre com S no exemplo 4.4.
Teorema 4.1 (Teorema de Szemerédi) Se S é um subconjunto de Z com densidade superior positiva, então ele contém progressões aritmética
s de tamanho arbitrário.
Demonstração Considere S um conjunto com densidade superior positiva, isto é, tal que,
existe um c > 0 e intervalos Ij = [aj , bj ) de Z tais que
#S∩I

lim#Ij = ∞ e lim #Ij j ≥ c.
j

j

Associaremos a a S a sequência α = (αj )j∈Z ∈ Σ = {0, 1}Z definida por:
αj = 1 ⇔ j ∈ S.
Considere o deslocamento σ : Σ → Σ e o subconjunto A = {α ∈ Σ : α0 = 1} de Σ.
Note que A é aberto e fechado pois trata-se de um cilindro de Σ. Observe também que
, para qualquer j ∈ Z,
σ(α) ∈ A ⇔ αj = 1 ⇔ j ∈ S.
Logo, para mostrar o Teorema de Szemerédi é suficiente mostrar que para todo k ∈ N
existem m ∈ Z e n ≤ 1 tais que
σ m+n (α), σ m+2n (α), ..., σ m+kn (α) ∈ A
28

pois desta forma terı́amos
αm+n , αm+2n = ... = αm+kn = 1
e assim
m + n, m + 2n, ..., m + kn ∈ S.
Para tal, considere a sequência
µj =

1 X
δσi (α)
#Ij i∈I
j

Como o conjunto M1 (Σ) das probabilidades em Σ é compacto, a menos de substituir
(µj )j por uma subsequência, podemos supor que ela converge na topologia fraca* para
alguma probabilidade µ de Σ. Note que µ é uma probabilidade σ-invariante pois, para
toda função contı́nua ϕ : Σ → R, vale
Z
1
1 X
[ϕ(σ bj (α)) − ϕ(σ aj (α))]
(ϕ ◦ σ)dµj =
ϕ(σ i (α)) +
#Ij i∈I
#Ij
j

Z

1
[ϕ(σ bj (α)) − ϕ(σ aj (α))]
#Ij
Z
Z
e, passando o limite quando j → ∞, temos (ϕ ◦ σ)dµ =
ϕdµ. Observe também
=

ϕdµj +

que µ(A) > 0. De fato, como A é fechado temos que:
µ(A) ≥ lim supµj (A) = lim sup
j

j

#(S ∩ Ij )
≥c
#Ij

. Dado qualquer k ≥ 1, considere as transformações fi = σ i para i = 1, ..., k. Claramente estas transformações comutam entre si. Então, pelo Teorema de Recorrência
Múltipla de Poincaré, existe algum n ≥ 1 tal que
µ(A ∩ σ −n (A) ∩ ... ∩ σ −kn (A)) > 0.
Sendo A aberto temos que:
µl (A ∩ σ −n (A) ∩ ... ∩ σ −kn (A) > 0.
para qualquer l suficientemente grande. Pela definição de µl significa que existe algum
m ∈ Il tal que
σ m (α) ∈ A ∩ σ −n (A) ∩ ... ∩ σ −kn (A).
Em particular, σ m+in (α) ∈ (A) para todo i = 1, ..., k como querı́amos provar.

29

O teorema de van der Waerden é um caso particular do teorema de Szemerédi. De fato,
dada uma partição S1 , ..., Sl de Z e sequências (xni ) em Si , com i = 1, ..., l temos:
lim sup (xn1 + ... + xnl ) ≤ lim sup xn1 + ... + lim sup xnl .
Assim,
Ds (Z) ≤ Ds (S1 ) + ... + Ds (Sl ).
Como,
#(Z ∩ I)
#I
= lim sup
=1
#I
#I→∞
#I→∞ #I

Ds (Z) = lim sup

onde I ⊂ Z representa qualquer intervalo dos inteiros, segue -se que:
1 ≤ Ds (S1 ) + ... + Ds (Sl ).
Sabendo que a densidade superior é sempre um número maior ou igual a zero, segue-se
desta desigualdade que existe um j ∈ 1, ..., l tal que Ds (Sj ) > 0, o que implica pelo teorema
de Szemerédi que este Sj possui progressões aritméticas de tamanhos arbitrários.

30

Capı́tulo 5
Teorema de Green-Tao
O matemático inglês Ben Green e o matemático australiano Terence Tao formularam o
espetacular resultado: existem progressões aritméticas arbitrariamente longas formadas por
números primos [4]. O conjunto dos números primos não tem densidade superior positiva,
portanto o teorema de Green-Tao não é consequência do teorema de Szemerédi. Por outro
lado, o teorema de Green-Tao é um caso particular de outra conjectura devido a Erdos: se
S ⊂ N é tal que a soma dos inversos diverge, ou seja, tal que:
X1
= ∞,
n
n∈S
então S contém progressões aritméticas de qualquer comprimento. Este era um dos ”prize
money problems”de Paul Erdos pelo qual ele oferecia uma quantia em dinheiro para quem
conseguisse resolver. Esta afirmação mais geral ainda permanece em aberto.
Salientaremos a seguir os passos fundamentais que Green e Tao desenvolveram para demonstrar o Teorema citado acerca da existência de progressões aritméticas nos primos, evitando definições formais e questões técnicas não triviais.
Trata-se de uma interessante demonstração resultante da fusão de de métodos e resultados
de teoria dos números, teoria ergódica, análise harmônica, combinatória e geometria discreta.
O ponto de partida é a demonstração do teorema de Szemerédi comentado no capı́tulo anterior. Todavia, o conjunto dos números primos não tem densidade superior positiva, portanto
o teorema de Szemerédi não pode ser diretamente aplicado. Donde surge o segundo passo da
demonstração de Green e Tao, usar um princı́pio da transferência o qual permite o uso do
teorema de Szemerédi num contexto mais geral.
Assim, será possı́vel deduzir do teorema de Szemerédi que qualquer subconjunto de um
conjunto suficientemente k−pseudo-aleatório (que satisfazem uma condição de formas lineares e uma condição de correlação em termos do parâmetro k), de densidade relativa positiva
contém progressões aritméticas de comprimento arbitrariamente longo.
O último ponto, consiste no uso de propriedades especı́ficas dos números primos e da sua
distribuição, baseados em resultados recentes de Goldston e Yildirim sobre o tamanho das
lacunas nos primos [9], onde é mostrado que o Teorema de Szemerédi generalizado pode ser
aplicado ao conjunto dos números primos.
31

Referências Bibliográficas
[1] B. Hasselblatt and A. Katok , Introduction to the Modern Theory of Dynamical Systems,
volume 54 of Encyclopedia of Mathematics and its Applications, Cambridge University
Press (1995),Whit a supplementary chapter by Katok and Leonardo Mendonza.
[2] K. Oliveira and M. Viana, Foundations of Ergodic Theory, Cambridge studies in advanced (2015).
[3] W. Gasarch Kruskel and P. Andy, Van der Waerden’s Theorem: Variants and Aplications,210 (2012), no 1.
[4] B. Green and T. Tao, The primos contain arbitrarily long arithmetic progressions, Ann.
of Math., 167:481-547 (2008).
[5] H. Fustemberg, Ergodic behavior and a theorem of Szemerédi on arithmetic Progressions
. J. d’ Analyse Math, 31:204-256 (1977).
[6] A. Arbieto, C. Matheus, C. Gustavo Moreira Aspectos Ergódicos da Teoria dos Números,
IMPA, 26◦ Colóquio Brasileiro de Mtemática, 2007.
[7] P. Halmos, Measure Theory. D. Van Nostrand Company (1950).
[8] D. A. Goldston and C. Y. Yildirim, Higher Correlations of Divisor Sums Related to
primes, III. Small gaps between primes (2003).

32