ColoquioMateusGuguAlexNew i 2007/6/29 page 1 iw3.impa.br/~gugu/Moreira_Matheus_Alexander.pdf · \ColoquioMateusGuguAlexNew" 2007/6/29 page 5 i i i i i i i i Sum¶ario 1 Propriedades

$Page 1: ColoquioMateusGuguAlexNew i 2007/6/29 page 1 iw3.impa.br/~gugu/Moreira_Matheus_Alexander.pdf · \ColoquioMateusGuguAlexNew" 2007/6/29 page 5 i i i i i i i i Sum¶ario 1 Propriedades$
“ColoquioMateusGuguAlexNew”2007/6/29page 1

i

i

i

i

i

i

i

i

Dedicamos este livro ao Ramiro Mendoza Sanchez,a Aline Gomes Cerqueira,

ao Carlos de Araujo Moreira Neto ea Raquel Tavares Scarpelli.


i

i

i

i

i

i

i

i


i

i

i

i

i

i

i

i

3

Prefacio

Problemas que envolvem simultaneamente as estruturas aditiva emultiplicativa dos numeros inteiros, em particular problemas aditivossobre numeros primos, costumam ser extremamente difıceis, apesarde muitas vezes terem enunciados bastante simples. Nao se sabe porexemplo se ha infinitos pares de primos gemeos, i.e., pares de primoscuja diferenca e 2. Tambem continua em aberto a famosa conjecturade Goldbach: todo inteiro par maior ou igual a 4 e soma de doisprimos.

Outra conjectura classica sobre primos que estava em aberto hamuito tempo e a de que existem progressoes aritmeticas arbitraria-mente longas formadas exclusivamente por primos. A maiordessas progressoes conhecida atualmente e 468395662504823+k · 45872132836530, 0 ≤ k ≤ 23, formada por 24 primos, descobertaem 18 de janeiro de 2007 por Jaroslaw Wroblewski. Esta conjecturafoi finalmente demonstrada por Ben Green e Terence Tao em 2004.Tao ganhou uma medalha Fields em 2006, principalmente por causadeste trabalho.

O objetivo principal deste texto e expor o trabalho de Green eTao da forma mais auto-contida possıvel. Sua demonstracao uti-liza o famoso Teorema de Szemeredi, segundo o qual qualquer con-junto de inteiros positivos com densidade (superior) positiva contemprogressoes aritmeticas arbitrariamente longas. O trabalho de Greene Tao usa ainda ideias de teoria ergodica, introduzidas por Fursten-berg para dar uma prova alternativa do Teorema de Szemeredi, alemde tecnicas introduzidas por Gowers para dar ainda outra demon-stracao deste Teorema de Szemeredi.

No capıtulo 1 apresentaremos diversos resultados sobre numerosprimos, incluindo a demonstracao do Teorema dos Numeros Primos,sobre sua distribuicao assintotica, durante a qual faremos estimativassobre a funcao ζ de Riemann que serao usadas na prova do Teoremade Green e Tao. Discutiremos tambem resultados ligados ao Teoremade Szemeredi e a prova ergodica de Furstenberg.


i

i

i

i

i

i

i

i

4

No capıtulo 2 apresentaremos a demonstracao do Teorema deGreen e Tao que generaliza o Teorema de Szemeredi via a introducaodas medidas pseudo aleatorias. Neste capıtulo aparecem as tecnicasergodicas e as tecnicas de Gowers que mencionamos.

No capıtulo 3 provamos que existem medidas pseudo-aleatoriasem relacao as quais os primos tem medida positiva, o que, pelosresultados do capıtulo 2, permite concluir a existencia de progressoesaritmeticas arbitrariamente longas formadas por primos.

Apesar de sofisticada, a prova do Teorema de Green-Tao nao re-quer muitos pre-requisitos que nao estejam contidos neste texto (emparticular nao usaremos diretamente resultados de teoria ergodicanem de teoria analıtica dos numeros que nao estejam demonstradosnestas notas; por outro lado, alguma experiencia previa com essesassuntos pode ajudar a compreender muitas das ideias da prova).


i

i

i

i

i

i

i

i

Sumario

1 Propriedades aditivas dos numeros primos 71.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . 71.2 Problemas classicos sobre propriedades aditivas . . . . 8

1.2.1 A conjectura dos primos gemeos . . . . . . . . 81.2.2 A conjectura de Goldbach . . . . . . . . . . . . 91.2.3 Primeiros Resultados sobre Progressoes

Aritmeticas e Numeros Primos . . . . . . . . . 91.3 Progressoes Aritmeticas em certos subconjuntos de Z . 10

1.3.1 O teorema de Van der Waerden . . . . . . . . . 111.3.2 Conjuntos com Densidade Positiva e o Teorema

de Szemeredi . . . . . . . . . . . . . . . . . . . 111.3.3 O teorema dos Numeros Primos e Progressoes

Aritmeticas formadas por Primos . . . . . . . . 121.3.4 A conjectura de Erdos-Turan . . . . . . . . . . 13

1.4 Prova do Teorema dos Numeros Primos . . . . . . . . 131.4.1 A funcao de Von Mangoldt . . . . . . . . . . . 141.4.2 A funcao zeta de Riemann . . . . . . . . . . . . 151.4.3 Prova Analıtica . . . . . . . . . . . . . . . . . . 17

1.5 O Teorema de Van der Waerden . . . . . . . . . . . . 181.5.1 Prova Combinatoria . . . . . . . . . . . . . . . 191.5.2 Prova via Sistemas Dinamicos . . . . . . . . . . 21

1.6 O Teorema de Furstenberg e suas aplicacoes . . . . . . 221.6.1 Breve Introducao a Teoria Ergodica . . . . . . 221.6.2 O teorema de Furstenberg . . . . . . . . . . . . 251.6.3 Prova do teorema de Szemeredi . . . . . . . . . 27

1.7 O Teorema de Szemeredi quantitativo . . . . . . . . . 28

5


i

i

i

i

i

i

i

i

6 SUMARIO

1.8 Outros resultados . . . . . . . . . . . . . . . . . . . . . 321.8.1 A funcao de Von Mangoldt e Reformulacoes de

algumas conjecturas . . . . . . . . . . . . . . . 321.8.2 Constelacoes de Primos e Progressoes Polinomiais 331.8.3 Buracos no conjunto dos numeros primos . . . 341.8.4 O tamanho do numero N0(k, δ) . . . . . . . . . 34

1.9 Apendice ao Capıtulo 1 . . . . . . . . . . . . . . . . . 351.9.1 Prova do Teorema de Dirichlet no caso a = 1 e

b qualquer . . . . . . . . . . . . . . . . . . . . . 351.9.2 Prova da proposicao 1.4.2 . . . . . . . . . . . . 361.9.3 Prova do teorema 1.4.2 . . . . . . . . . . . . . 421.9.4 Prova do teorema 1.5.3 . . . . . . . . . . . . . 451.9.5 O exemplo de F. Behrend . . . . . . . . . . . . 46

2 Teorema de Green-Tao-Szemeredi 492.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . 492.2 Estrategia da prova do teorema de Green e Tao . . . . 50

2.2.1 Prova do teorema de Green e Tao . . . . . . . 542.2.2 Alguns comentarios . . . . . . . . . . . . . . . 55

2.3 Prova do teorema de Roth . . . . . . . . . . . . . . . . 552.4 Demonstracao do teorema de Green-Tao-Szemeredi . . 64

2.4.1 Normas de Gowers . . . . . . . . . . . . . . . . 652.4.2 Anti-Uniformidade . . . . . . . . . . . . . . . . 732.4.3 Sigma-Algebras geradas por funcoes anti-uni-

formes basicas . . . . . . . . . . . . . . . . . . 792.4.4 O argumento de incremento na energia . . . . . 822.4.5 Fim da prova do teorema de

Green-Tao-Szemeredi . . . . . . . . . . . . . . . 88

3 Construcao da Medida Pseudo-Aleatoria 903.1 A Medida Pseudo-Aleatoria . . . . . . . . . . . . . . . 903.2 Condicao de formas lineares para ΛR . . . . . . . . . . 983.3 Correlacoes de ordem superior de ΛR . . . . . . . . . . 1063.4 Prova do Lema 3.2.4 . . . . . . . . . . . . . . . . . . . 1103.5 Apendice ao Capıtulo 3 . . . . . . . . . . . . . . . . . 119

Referencias Bibliograficas 123


i

i

i

i

i

i

i

i

Capıtulo 1

Propriedades aditivasdos numeros primos

1.1 Introducao

Um dos conceitos numericos mais antigos e a nocao de numero primo.Por definicao um numero p e primo se ele e divisıvel somente por 1 epor ele mesmo.

Os numeros primos aparecem em diversos resultados elementaresda teoria dos numeros, como o teorema de decomposicao unica emfatores primos ou como os numeros tais que Z/pZ e um corpo.

Obviamente como a definicao de numero primo e de carater mul-tiplicativo, podemos extrair diversas propriedades multiplicativas el-ementares. Por exemplo, o produto de dois primos nao e primo. Oumesmo, nao existem progressoes geometricas de comprimento maiorou igual a 3 formadas somente por primos.

Por outro lado, ao levantarmos perguntas de carater aditivo pode-mos nos deparar com algumas surpresas. Por exemplo, a soma dedois numeros primos e primo? A resposta e: depende. Por exemplo2+3=5 e primo, 2+5=7 e primo, mas 3+5=8 nao e primo e nem7+2=9. Por outro lado o postulado de Bertrand diz que para todonatural N existe um primo entre N e 2N . Ve-se entao que a seguintepergunta merece pelo menos um pouco de reflexao:

7


i

i

i

i

i

i

i

i

8 [CAP. 1: PROPRIEDADES ADITIVAS DOS NUMEROS PRIMOS

Existem progressoes aritmeticas de comprimento maior ou igual a 3formadas somente por primos? E quantas existem uma vez que o

comprimento for fixado?

Veremos nestas notas como tal pergunta foi respondida por BenGreen e Terence Tao. Mas, antes disso, iremos passear pelo mundodos numeros primos, vendo solucoes parciais a esta pergunta e anal-isando outras questoes de carater aditivo envolvendo os numeros pri-mos.

1.2 Problemas classicos sobre proprieda-des aditivas de Numeros Primos

1.2.1 A conjectura dos primos gemeos

Observando o exemplo da introducao, sabemos que nem sempre asoma de um numero primo com 2 e primo; mas, sera que existeminfinitos primos com essa propriedade? Dizemos que p e p+2 saoprimos gemeos se ambos sao primos. Exemplos de primos gemeossao: (3 e 5), (5 e 7), (11 e 13), (17 e 19), (29 e 31), (41 e 43). Umdos problemas em aberto mais famosos da teoria dos numeros e aconjectura dos primos gemeos:

Existem infinitos primos gemeos?

Um resultado importante devido a Brun [2] mostra que mesmo que ex-istam infinitos primos gemeos, eles se tornam muito escassos quandoolhamos para numeros muito grandes, o que torna a conjectura maisdifıcil. De fato o teorema de Brun diz que a serie dos inversos dosprimos gemeos ımpares converge (para um numero conhecido comoa constante de Brun):

(13

+15) + (

15

+17) + (

111

+113

) + (117

+119

) + ... < +∞.

Mais tarde reformularemos a conjectura dos primos gemeos em umalinguagem mais analıtica.


i

i

i

i

i

i

i

i

[SEC. 1.2: PROBLEMAS CLASSICOS SOBRE PROPRIEDADES ADITIVAS 9

1.2.2 A conjectura de Goldbach

Em uma carta a Euler, em 1742, Goldbach perguntava se todo numeromaior que 2 e soma de 3 primos. Goldbach assumia que 1 era primo,o que nao e mais usado. Portanto uma conjectura equivalente e afamosa conjectura de Goldbach e:

Todo inteiro par n ≥ 4 pode ser escrito como soma de dois primos?

Mesmo sendo facil de enunciar, a conjectura de Goldbach ainda eum dos maiores desafios da teoria dos numeros. Diversos resultadosparciais foram obtidos, mas nenhuma das provas parece se estendera uma demonstracao da conjectura de Goldbach.

Por exemplo, Schnirelman [8] mostrou que todo numero primopode ser escrito como uma soma de primos, porem o numero deparcelas e maior que 300000, um pouco longe de 2, nao?

Outra conjectura relacionada e chamada de conjectura fraca deGoldbach:

Todo numero ımpar n ≥ 9 pode ser escrito como soma de 3 primos?

Com respeito a este problema, temos o famoso teorema de Vino-gradov [15], onde ele resolve a conjectura fraca de Goldbach paranumeros ımpares suficientemente grandes (maiores que 3315

).Outro resultado interessante e o teorema de Chen [3], onde ele

mostra que um numero par suficientemente grande e soma de umprimo com um quase-primo (um numero com no maximo 2 fatoresprimos).

Uma versao mais forte da conjectura fraca de Goldbach e con-hecida como a conjectura de Levy:

Todo numero ımpar n ≥ 7 pode ser escrito como soma de um primomais o dobro de outro primo?

Mais adiante, reformularemos estas conjecturas de maneiraanalıtica.

1.2.3 Primeiros Resultados sobre ProgressoesAritmeticas e Numeros Primos

Um dos resultados mais classicos neste assunto e o teorema de Dirich-let que diz:


i

i

i

i

i

i

i

i


Se a e b sao primos entre si entao a progressao aritmetica a + nbcontem infinitos primos.

A prova deste resultado utiliza o conceito de L-series (uma definicaomais avancada) devido a Dirichlet. No apendice sera dado um esbocoda prova em um caso particular.

O teorema de Dirichlet nao diz que a progressao aritmetica e for-mada inteiramente de primos. Uma pergunta natural e se existe umaprogressao aritmetica de tamanho infinito formada somente de pri-mos. A resposta e negativa segundo o teorema de Lagrange-Waring:

Considere uma progressao aritmetica formada somente de primos decomprimento k e de razao d. Entao necessariamente d e divisıvelpor todos os primos menores que k. Em particular nao existem

progressoes aritmeticas de comprimento infinito formadas somentede primos.

1.3 Progressoes Aritmeticas em certossubconjuntos de Z

A questao da existencia de progressoes aritmeticas de tamanho finitoformadas de primos pode ser estendida da seguinte maneira:

Seja A ⊂ Z. Existem progressoes aritmeticas de comprimentoarbitrariamente grande formadas somente por numeros que

pertencem a A?

De certa forma, veremos que o conjunto P de numeros primos emuito “magro”. Podemos entao tentar atacar o problema primeira-mente para conjuntos A “gordos”, onde as chances de se encontrarprogressoes aritmeticas sao maiores, e tentar adaptar os metodos deprova para o caso de conjuntos “magros”. Obviamente um problemacentral e a definicao do que e um conjunto “magro” e o que e um con-junto “gordo”. Nesta secao veremos certos resultados nesta direcao.Observe que nao aplicaremos a ordem cronologica na exposicao dosresultados.


i

i

i

i

i

i

i

i

[SEC. 1.3: PROGRESSOES ARITMETICAS EM CERTOS SUBCONJUNTOS DE Z 11

1.3.1 O teorema de Van der Waerden

Suponha que voce possui uma quantidade finita, digamos k, de cores euse-as para pintar os numeros inteiros. Entao, voce obtem k subcon-juntos disjuntos que formam uma particao dos inteiros. O teoremade Van der Waerden diz que:

Pelo menos um destes subconjuntos e tao “gordo” que possuiprogressoes aritmeticas de comprimento arbitrariamente grande.

Em particular, se tomamos duas cores e pintamos os primos deuma cor e os nao-primos de outra, obtemos:

O conjunto de numeros primos ou o conjunto de numerosnao-primos possuem progressoes aritmeticas de comprimento

arbitrario.

Mais adiante veremos provas do teorema de Van der Waerden.

1.3.2 Conjuntos com Densidade Positiva e o Teo-rema de Szemeredi

Obviamente, o conjunto dos numeros pares possuem progressoesaritmeticas de comprimento arbitrario (com razao 2, por exemplo).Observe que num intervalo [1, N ] := n ∈ Z; 1 ≤ n ≤ N essencial-mente os pares ocupam 1/2 deste conjunto. Da mesma maneira, osnumeros ımpares tambem tem essa propriedade e possuem progressoesaritmeticas de comprimento arbitrario. Mais geralmente, escolhidoum numero k qualquer se voce olha para o conjunto de multiplos de k,este conjunto essencialmente ocupa 1/k de [1, N ] e possui progressoesaritmeticas de comprimento arbitrario.

Com base nisto, podemos tentar dizer que um conjunto e “gordo”se ele ocupa uma fracao positiva do intervalo [1, N ]. Por outro lado,como queremos progressoes de comprimento grande, iremos pedir queessa fracao seja vista assintoticamente.

Definicao 1.3.1. Seja A ⊂ N a densidade de A e:

d(A) = lim supN→∞

|[1, N ] ∩A|N

.

Aqui, dado B ⊂ N, denotamos por |B| a cardinalidade de B.


i

i

i

i

i

i

i

i


Obviamente a definicao se estende naturalmente para subconjun-tos dos inteiros. O primeiro teorema que lida com conjuntos “gordos”ou melhor com densidade positiva e o teorema de Roth [7] de 1956:

Se A ⊂ Z tem densidade positiva entao A possui infinitasprogressoes aritmeticas de comprimento 3.

O problema da existencia de progressoes aritmeticas de compri-mento arbitrario somente foi resolvido gracas aos trabalhos de Sze-meredi [9] em 1975:

Teorema 1.3.1 (Szemeredi). Se A ⊂ Z tem densidade positiva entaoA possui infinitas progressoes aritmeticas de comprimento arbitrari-amente grande.

Adaptacoes da prova do teorema de Szemeredi serao objeto deestudo nos capıtulos posteriores, pois veremos a seguir que nao sepode aplicar o teorema nesta forma ao conjunto dos numeros primos.Nas secoes seguintes, daremos provas do teorema de Szemeredi.

1.3.3 O teorema dos Numeros Primos e ProgressoesAritmeticas formadas por Primos

O motivo pelo qual nao podemos aplicar o teorema de Szemeredi aoconjunto de numeros primos se deve ao famoso teorema dos numerosprimos:

Teorema 1.3.2 (O Teorema dos Numeros Primos). Vale a seguinteestimativa assintotica:

|P ∩ [1, N ]|N

=1

log N+ o(1).

Aqui P e o conjunto de numeros primos e o(1) e uma quantidade quevai a zero quando N →∞. Em particular d(P ) = 0.

Mesmo que os primos tenham densidade zero, a existencia deinfinitas progressoes aritmeticas de comprimento 3 formada de primosfoi obtida em 1939 por Van der Corput (antes do teorema de Roth):

Existem infinitas progressoes artimeticas de comprimento 3formadas somente de primos.


i

i

i

i

i

i

i

i

[SEC. 1.4: PROVA DO TEOREMA DOS NUMEROS PRIMOS 13

Finalmente, em 2004, Ben Green e Terence Tao [5] obtiveram oresultado geral. Tal teorema e objeto central de estudo deste livro:

Teorema 1.3.3 (Green-Tao). Existem infinitas progressoes aritme-ticas de comprimento arbitrario formadas somente de primos.

1.3.4 A conjectura de Erdos-Turan

Sabe-se que a serie∑

1n2 converge, porem, em 1737, Euler mostrou

que a serie dos inversos dos primos diverge:

∑

p primo

1p

= +∞.

Isto mostra que os numeros primos nao sao tao esparsos quanto osquadrados de numeros naturais.

A conjectura de Erdos-Turan diz que conjuntos com tal propriedadedevem conter progressoes aritmeticas de comprimento arbitrario. Oteorema de Green-Tao e portanto um caso particular desta conjec-tura:

Conjectura 1 (Erdos-Turan). Seja A ⊂ N tal que:

∑

n∈A

1n

= +∞.

Entao existem infinitas progressoes aritmeticas de comprimento ar-bitrario formada somente por elementos de A.

Esta conjectura esta completamente em aberto: nao se sabe nemse tais conjuntos devem conter progressoes aritmeticas de compri-mento 3.

1.4 Prova do Teorema dos Numeros Pri-mos

Nesta secao daremos um esboco da prova do teorema dos numerosprimos. Veremos suas relacoes com a funcao de Von Mangoldt e coma funcao zeta de Riemann.


i

i

i

i

i

i

i

i


1.4.1 A funcao de Von Mangoldt

Em primeiro lugar, reformularemos o teorema numa linguagem inte-gral e veremos suas relacoes com a funcao de Von Mangoldt.

Definicao 1.4.1. A funcao de Von Mangoldt Λ : Z → R+ e dadapor Λ(n) = log p se n = pr, onde r ≥ 1 e Λ(n) = 0 caso contrario.

Observe que o teorema da decomposicao unica em fatores primospode ser expresso por:

log n =∑

d|nΛ(d). (1.4.1)

Definicao 1.4.2. Dada f : X → R e A ⊂ X um conjunto finito,definimos a esperanca de f com respeito a A como:

E(f(n)|n ∈ A) = E(f |A) =1|A|

∑

n∈A

f(n).

Nesta linguagem o teorema dos numeros primos pode ser vistocomo uma estimativa para a esperanca da funcao de von Mangoldt:

Teorema 1.4.1. O Teorema dos Numeros Primos e equivalente a:

E(Λ|[1, N ]) = 1 + o(1).

Demonstracao. Pela definicao da funcao de von Mangoldt temosque:

NE(Λ|[1, N ]) =∑

p≤N

[log N

log p] log p ≤ log N

∑

p≤N

1

= log N · (|primos entre 1 e N |).Isto da uma das desigualdades desejadas (dividindo por N).

Por outro lado, se 1 < M < N entao:

|primos entre 1 e N | = |primos entre 1 e M |+∑

M<p≤N

1

≤ |primos entre 1 e M |+∑

M<p≤N

log p

log M

< M +1

log MNE(Λ|[1, N ]).


i

i

i

i

i

i

i

i


Agora se N e muito grande entao temos que 1 < M = Nlog2 N

< N .Substituindo na inequacao acima obtemos que:

|primos entre 1 e N | < N

log2 N+

NE(Λ|[1, N ])log N − 2 log log N

.

Portanto:

|primos entre 1 e n|N

< E(Λ|[1, N ])(1

log N − 2 log log N) +

1log2 N

.

Isto conclui a demonstracao porque log xlog x−2 log log x → 1 quando

x →∞.

1.4.2 A funcao zeta de Riemann

Uma das funcoes mais famosas na Matematica e a funcao zeta de Rie-mann. Ela desempenha um papel fundamental na teoria dos numerose tambem aparece em diversas outras areas (p.ex., analise complexa,sistemas dinamicos, etc.). Em particular, ela tem estreita relacaocom a distribuicao dos numeros primos devido a formula de Euler.Nesta secao iremos estudar algumas propriedades desta funcao.

Definicao 1.4.3. A funcao zeta de Riemann e dada pela unicaextensao meromorfa da seguinte funcao analıtica no domınioRe(s) > 1:

ζ(s) =∑

n≥1

1ns

.

Proposicao 1.4.1 (Formula de Euler). Se s > 1 e real, entao aseguinte identidade de Euler e verdadeira:

ζ(s) =∏p

11− p−s

.

Para provar esta formula precisamos de falar de funcoes multi-plicativas. Dizemos que uma funcao f : Z → R e multiplicativa sef(mn) = f(m)f(n) quando (m,n) = 1, e ela e estritamente multi-plicativa quando esta relacao vale sem restricao.


i

i

i

i

i

i

i

i


Demonstracao. Suponha que f e multiplicativa e limitada, entaoem Re(s) > 1 podemos escrever:

∑ f(n)ns

=∏p

(∑m

f(pm)pms).

De fato, em Re(s) ≥ δ > 1 temos que∑

k≥1f(k)ks converge uniforme-

mente, por outro lado, seja P (n) =∏

p≤n(∑

m≥0 f(pm)p−ms), ondes esta fixo. Ora, P (n) e um produto finito de series convergentes epodemos entao escreve-lo como

∑m∈An

f(m)ms , onde

An = r ∈ N; os fatores primos de r sao menores ou iguais a n.

Por exemplo se n = 3 temos que:

P (3) = (∑m

f(2m)2−ms)(∑

j

f(3j)3−js)

=∑

m,j

f(2m)f(3j)2−ms3−js

=∑

m,j

f(2m3j)(2m3j)−s =∑

m∈An

f(m)m−s.

Agora, obviamente 1, . . . , n ⊂ An. Logo |P (n) − ∑k≥1

f(k)ks | ≤∑

k>nf(k)ks , donde o resultado segue pela convergencia absoluta da

serie.Alem disso, se f e estritamente multiplicativa, temos que f(pm) =

(f(p))m. Isto implica que∑

m≥0 f(pm)p−ms =∑

m≥0(f(p)p−s)m =1

1−f(p)p−s , pela formula da serie geometrica.A formula de Euler segue entao observando que a funcao f ≡ 1 e

estritamente multiplicativa.

Para nossos propositos, estaremos interessados em conhecer regioesonde a funcao zeta nao se anula. De fato, isso faz parte de um prob-lema importante a respeito da funcao zeta conhecido como a Hipotesede Riemann: e sabido que os pares negativos −2,−4, . . . sao zerosda funcao zeta, chamados de zeros triviais, e outros zeros conhecidos


i

i

i

i

i

i

i

i


sao da forma 12 + iα onde α e um zero da funcao

ξ(t) =12s(s− 1)π−s/2Γ(

s

2)ζ(s), onde s =

12

+ it.

A Hipotese de Riemann afirma que

Os zeros nao triviais da funcao zeta de Riemann tem parte realigual a 1

2 .

Este e um problema muito difıcil e tem posto a prova os esforcosde muitos matematicos famosos. Neste livro iremos encontrar umaregiao livre de zeros de forma elementar (usando analise complexa).A prova do seguinte fato sera dada no apendice deste capıtulo:

Proposicao 1.4.2. ζ(s) 6= 0 em Re(s) ≥ 1.

Para isso iremos estudar a analiticidade da funcao zeta de Rie-mann e provaremos o seguinte fato: 1 e o unico polo da funcao zetade Riemann em Re(s) > 0, ele e simples e tem resıduo 1. De fato,se [x] denota a funcao maior inteiro menor do que x entao na regiaoRe(s) > 0 temos a expansao:

ζ(s) =1

s− 1+ 1 + s

∫ ∞

1

([x]− x)x1+s

dx.

1.4.3 Prova Analıtica

A principal ferramenta nesta demonstracao e o seguinte teorema, cujaprova sera dada no apendice:

Teorema 1.4.2. Seja f : [1,∞] → R, tal que f(x) = O(x), naodescrescente e f ∈ L1

loc. Dado s um parametro complexo, seja ga transformada de Mellin de f , isto e, g(s) := s

∫∞1

f(x)x−1−sdx.Entao, em Re(s) > 1, g e uma funcao analıtica. Alem disso, seexiste uma constante c tal que g(s)− c

s−1 tem continuacao analıticaem Re(s) = 1 entao:

limx→∞

f(x)x

= c.


i

i

i

i

i

i

i

i


Em vista do teorema 1.4.2 e das propriedades da funcao zeta,vistas acima, resta provar que xE(Λ|[1, x]) = O(x). Podemos provaristo da seguinte maneira: observe que

∏

n<p≤2n

p ≤ 2n(2n− 1) . . . (n + 1) =(

2n

n

)< 22n.

Assim, temos∑

n<p≤2n

log p < 2n log 2. Tomando n = 22k−1 (uma

especie de decomposicao diadica) vemos que∑

2k−1<p≤2k

log p ≤ 2k log 2.

Somando estas desigualdades temos que:

∑

p≤2k

log p ≤k∑1

2i log 2 < 2k+1 log 2.

Logo, tomando 2k−1 < N ≤ 2k segue que∑

p≤N

log p ≤ 2k+1 log 2 = (4 log 2)2k−1 < 4N log 2.

Portanto∑

pm≤N

log p < (4 log 2)N1/m. Agora, lembrando que

E(Λ|[1, N ]) = 1N (

∑p≤N

log p+∑

m≥2

∑pm≤N

log p) e definindo α−1 = [ log Nlog 2 ],

obtemos:

E(Λ|[1, N ]) ≤ 4 log 2N

(N +1/α∑m=2

N1/2)

≤ 4 log 2(1 +1

α√

N).

Isto mostra a limitacao desejada.Estamos entao nas hipotese do teorema 1.4.2, o qual diz que

E(Λ|[1, N ]) = 1+o(1). Mas isto e equivalente ao teorema dos numerosprimos pelo teorema 1.4.1, o que conclui o argumento.

1.5 O Teorema de Van der Waerden

Nesta secao daremos duas provas do teorema de Van der Waerden:


i

i

i

i

i

i

i

i

[SEC. 1.5: O TEOREMA DE VAN DER WAERDEN 19

Teorema 1.5.1 (Van der Waerden). Se colorirmos os inteiros pos-itivos com um numero k de cores, podemos achar progressoes ar-itmeticas de comprimento arbitrario formadas por somente uma cor.

1.5.1 Prova Combinatoria

Nesta secao, iremos provar o teorema de Van der Waerden atravesdo metodo de colorir em Combinatoria. Para nao carregar muitanotacao, vamos denotar a progessao aritmetica a, a+r, . . . , a+(k−1)rpor a+[0, k)r, e vamos supor que temos m cores com as quais iremoscolorir os numeros naturais de 1 ate N .

Definicao 1.5.1. Seja c : 1, . . . , N → 1, . . . , m uma maneira decolorir. Dados k ≥ 1, d ≥ 0 e a ∈ 1 . . . , N, um ventilador de raiok, grau d com ponto base a e uma d-upla de progressoes aritmeticas(a + [0, k)r1, . . . , a + [0, k)rd) onde r1, . . . , rd > 0. Para cada 1 ≤i ≤ d as progressoes a + [1, k)ri sao chamadas de pas do ventilador.Dizemos que o ventilador e policromatico se seu ponto base e suaspas sao monocromaticas. Isto e, existem cores c0, c1, . . . , cd distintastais que c(a) = c0 e c(a + jri) = ci para j = 1, . . . k e i = 1, . . . d.

Observe que pela distincao das cores, se temos m cores, e im-possıvel termos um ventilador policromatico com grau maior ou iguala m.

E claro que o teorema de van der Waerden segue do seguinteresultado:

Teorema 1.5.2. Sejam k, m ≥ 1. Entao existe N tal que qual-quer coloracao com m cores de 1, . . . , N contem uma progressaoaritmetica de comprimento k monocromatica.

Demonstracao. A prova sera feita em dois passos indutivos. Primeiro,faremos inducao em k: observe que o caso k = 1 e trivial; tomemosk ≥ 2 e vamos supor que o teorema e verdade para k − 1.

Em seguida faremos inducao em d. Isto e, afirmamos que dadod, existe N tal que qualquer coloracao com m cores de 1, . . . , Ncontem ou uma progressao aritmetica monocromatica ou um venti-lador policromatico de raio k e grau d. Note que o caso d = 0 e triviale se provarmos que isso vale para d = m entao pela observacao feitaanteriormente, obtemos a progressao monocromatica.


i

i

i

i

i

i

i

i


Vamos tomar d ≥ 1 e supor que a afirmacao vale para d − 1.Seja N = 4kN1N2, onde N1 e N2 serao escolhidos depois e A =1, . . . , N. Seja entao c : 1, . . . , N → 1, . . . , m a coloracao.Obviamente bkN1 + 1, . . . , bkN1 + N1 e um subconjunto de A comN1 elementos para b = 1, . . . N2. Pela hipotese de inducao em k ed se N1 e muito grande, existe este conjunto possui uma progressaomonocromatica de comprimento k ou um ventilador policromaticode raio k e grau d − 1. Se para algum b encontramos a progressaomonocromatica, acabou. Portanto, vamos supor que para todo b =1, . . . N2 sempre encontramos um ventilador policromatico.

Logo, para cada b = 1, . . . , N2 encontramos a(b), r1(b), . . . , rd−1(b) ∈1, . . . , N1 e cores distintas c0(b), c1(b), . . . , cd−1(b) ∈ 1, . . .m taisque c(bkN1 + a(b)) = c0(b) e c(bkN1 + a(b) + jri(b)) = ci(b) paraj = 1, . . . , k − 1 e i = 1, . . . , d − 1. Chamaremos estas condicoes deprimeira e segunda propriedades do ventilador gerado por b. Emparticular, o mapa b → (a(b), r1(b), . . . , rd−1(b), c0(b), . . . , cd−1(b))e uma coloracao com mdNd

1 cores do conjunto 1, . . . , N2. Nova-mente pela hipotese de inducao em k, se N2 e muito grande, existeuma progressao monocromatica b + [0, k − 1)s nesta nova coloracaocom alguma cor da forma (a, r1, . . . , rd−1, c1, . . . , cd−1). Revertendoa posicao da progressao, podemos assumir que s e negativo, se fornecessario.

A ideia agora e transformar uma progressao de ventiladores iden-ticos em um novo ventilador com um grau a mais, para completaro passo de inducao. Seja entao b0 = (b − s)kN1 + a ∈ 1, . . . , N econsidere o ventilador:

(b0 + [0, k)skN1, b0 + [0, k)(skN1 + r1), . . . , b0 + [0, k)(skN1 + rd−1))

de raio k, grau d e ponto base b0.Vamos verificar que as pas sao monocromatica. Na primeira pa

temos c(b0 +jskN1) = c((b+(j−1)s)kN1 +a) por substituicao. Pelaprimeira propriedade do ventilador gerado por b + (j− 1)s segue quec((b + (j − 1)s)kN1 + a) = c0(b + (j − 1)s) = c0(b) (pois a progressaob + [0, k− 1)s e monocromatica se 1 ≤ j ≤ k− 1). Da mesma forma,em uma pa arbitraria, usando a segunda propriedade do ventilador,temos que se 1 ≤ j ≤ k − 1 e 1 ≤ t ≤ d entao:

c(b0+j(skN1+rt)) = c((b+(j−1)s)kN1+a+jrt) = ct(b+(j−1)s) = ct.


i

i

i

i

i

i

i

i

[SEC. 1.5: O TEOREMA DE VAN DER WAERDEN 21

Se o ponto base b0 tem a mesma cor de uma pa, entao encon-tramos uma progressao monocromatica de tamanho k, caso contrarioo ponto base tem cor distinta de suas pas e portanto encontramosum ventilador policromatico de raio k e grau d. Isto termina o passoindutivo e a prova do teorema.

1.5.2 Prova via Sistemas Dinamicos

Uma das grandes ferramentas em sistemas dinamicos e a chamadadinamica simbolica, a qual consiste em estudar uma transformacaochamada shift. A seguir daremos a definicao de shift e veremos comoFurstenberg usou tal maquinaria para dar uma prova do teorema devan der Waerden.

Seja A = a1, . . . , ak um alfabeto finito. Considere todas aspalavras infinitas compostas por letras deste alfabeto:

Ω = (x1, x2, . . . , xn, . . . ) ; xi ∈ A.

Este conjunto pode ser visto como um espaco metrico, atraves daseguinte distancia: dados x = (x1, x2, . . . ) e y = (y1, y2, . . . ), defina

d(x, y) :=1l

se l e o menor inteiro tal que xl 6= yl.

O shift e a transformacao T : Ω → Ω definida por:

T (x1, x2, x3, . . . ) = (x2, x3, x4, . . . ).

E simples mostrar que o shift e uma aplicacao contınua com respeitoa metrica definida acima.

Com estes conceitos, Furstenberg usou o seguinte teorema dedinamica topologica (cuja prova sera dada no apendice) para demon-strar o teorema de Van der Waerden.

Teorema 1.5.3 (Recorrencia Multipla Topologica - Furstenberg eWeiss). Seja T : X → X contınua e X um espaco metrico compacto.Para todo k ∈ N e ε > 0 existe x ∈ X e n ∈ N tal que d(T in(x), x) < εpara todo i = 1, . . . , k. Mais ainda, dado Z ⊂ X denso, podemosescolher x ∈ Z.


i

i

i

i

i

i

i

i


Vejamos como podemos provar o teorema de Van der Waerdena partir deste resultado. Seja A = c1, . . . , ck o conjunto de corese z = (z1, z2, z3, . . . ) uma maneira de colorir N onde zi ∈ A indicaa cor do numero i. Consideremos entao z ∈ AN e T : AN → AN oshift. Lembrando a definicao da distancia, temos que, para x, y ∈ AN

e m, l ∈ N, vale d(Tm(x), T l(y)) < 1 se e so se xm+1 = yl+1.Em particular, se z ∈ AN entao a progressao aritmetica m,m +

n, . . . , m + kn e monocromatica se zm = zm+n = · · · = zm+kn, ouseja, se:

d(Tm−1(z), Tm−1+in(z)) = d(Tm−1(z), T in(Tm−1(z)))< 1, para i = 1, . . . k.

Tomando X = Tm(z)∞m=0, temos que X e compacto, T e contınuaem X e o conjunto Z = Tm(z)∞m=0 e denso em X. O teorema deVan der Waerden segue entao do teorema 1.5.3.

1.6 O Teorema de Furstenberg e suas apli-cacoes no teorema de Szemeredi

Nesta secao daremos uma prova do teorema de Szemeredi baseada emelementos de teoria ergodica (mais ou menos inspirados pela “provadinamica” do teorema de van der Waerden). Primeiramente faremosuma introducao aos conceitos basicos de teoria ergodica, em seguidaenunciaremos o teorema de recorrencia multipla ergodica de Fursten-berg e, como corolario, obteremos o teorema de Szemeredi.

1.6.1 Breve Introducao a Teoria Ergodica

A teoria ergodica estuda iteracoes de uma transformacao T : X → X,onde X e um espaco de medida, do ponto de vista de uma medidaµ invariante pela transformacao T (i.e., para todo subconjunto men-suravel A temos que µ(A) = µ(T−1(A))).

A presenca da medida invariante da muita informacao estatısticasobre a estrutura de orbitas da transformacao T , isto e, dos conjuntosTn(x)∞n=0, para quase todo x ∈ X com respeito a medida µ. Porexemplo, o teorema de Poincare diz que “se T : X → X e µ-invariante


i

i

i

i

i

i

i

i

[SEC. 1.6: O TEOREMA DE FURSTENBERG E SUAS APLICACOES 23

e µ(A) > 0 entao para µ-qtp x em A temos que existe um n(x) ≥ 1tal que Tn(x)(x) ∈ A”. Portanto existe um N tal que:

µ(A ∩ T−N (A)) > 0.

Em particular, vemos que, por menor que seja um conjunto con-tendo um ponto x, se ele tem medida positiva entao existem muitasorbitas que comecam dentro desse conjunto e voltam infinitas vezespara este conjunto. Se o espaco de medida for topologico, entaopodemos reformular o teorema de Poincare da seguinte maneira:

Sejam T : X → X um espaco de medida e metrico (com respeito auma metrica d) e µ uma medida invariante por T . Entao quasetodo ponto com respeito a µ e recorrente, isto e para quase todo

ponto x existe uma sequencia nk →∞ de naturais tais qued(Tnk(x), x)) → 0 quando k →∞.

Uma pergunta natural e se existem sempre medidas invariantespara alguma tranformacao T dada. Quando o espaco X e compactoe a transformacao e contınua, a resposta e sim. A ideia da provadeste fato e muito simples: tomemos uma medida qualquer arbitrariae vejamos como essa medida muda pela acao da transformacao, oumelhor pela acao de iterados da transformacao. Faca uma mediadessas medidas ate o iterado N ; conforme N cresce, essa nova medidatende a ficar menos sensıvel a acao de T . O ponto e tomar estudar olimite quando N → ∞ e torcer para que uma medida limite exista;de acordo com nosso argumento (informal) tal limite sera invariantepor T .

Facamos agora a construcao com mais detalhes. Como vimosno paragrafo anterior, iremos tomar um certo limite de medidas, demaneira que precisamos de um conceito de convergencia de medi-das. Como o espaco de medidas de Radon e o dual do espaco defuncoes contınuas e natural usarmos a topologia fraca, uma vez quepela Analise Funcional teremos de graca resultados de compacidade(ajudando na questao da existencia de um “limite”).

Definicao 1.6.1. Dizemos que uma sequencia de medidas µk em Xconverge fracamente para µ se para toda funcao contınua f : X → Rvale: ∫

X

fdµk →∫

X

fdµ.


i

i

i

i

i

i

i

i


Como esta topologia e a topologia fraca, temos pelo teorema deBanach-Alaoglu que:

O espaco de probabilidades em X (isto e, o conjunto de medidas µtais que µ(X) = 1) e compacto com respeito a convergencia fraca.

Voltemos agora para a questao da existencia de medidas invari-antes. Seja η uma probabilidade qualquer. A acao dos iterados deT na medida η sera dada pelo push-forward, isto e, ((Tn)∗η)(A) :=η(T−n(A)) para todo conjunto mensuravel A. Uma observacao im-portante e que a propriedade de uma medida η ser invariante podeser traduzida na equacao T ∗η = η.

Vamos considerar a seguinte sequencia de probalidades:

µk =1k

k−1∑

i=0

(T i)∗η.

Em suma, estamos tomando medias temporais das medidas obti-das por push-forward. Por compacidade, vemos que existe uma sub-sequencia µnk

que converge fracamente para alguma probabilidade µ.Afirmamos que µ e invariante. De fato, temos as seguintes igualdadesque serao explicadas logo em seguida:

T ∗µ = T ∗(limµnk)

= lim(T ∗(µnk))

= lim(1nk

nk−1∑

i=0

(T i+1)∗(η))

= lim(1nk

(nk∑

i=0

(T i)∗(η)− η + (Tnk)∗η))

= lim1nk

nk∑

i=0

(T i)∗(η)

= µ.

Na segunda igualdade usamos o fato que o operador T ∗ e contınuona topologia fraca, pois T e contınua. Com efeito, suponha que


i

i

i

i

i

i

i

i


µk → µ fracamente e fixe f : X → R contınua. Entao temos quef T tambem e contınua e portanto:

∫

X

fd(T ∗µk) =∫

X

f Tdµk →∫

X

f Tdµ =∫

X

fd(T ∗µ).

Para a quinta igualdade, observamos que, para toda f : X → Rcontınua, temos, por compacidade de X:

1nk

∫

X

fdµ → 0 e1nk

∫

X

fd((Tnk)∗µ) =1nk

∫

X

f Tnkdµ → 0.

Logo as duas ultimas parcelas convergem a zero fracamente.Um exemplo concreto interessante para nossos propositos futuros

e X = 0, 1N e T o shift. Considerando a medida de Dirac de umponto x ∈ X, ou seja, δx(A) = 0 se x /∈ A e µ(A) = 1 se x ∈ A, entaoa sequencia µk = 1

k

∑k−1j=0 δT j(x) possui um ponto de acumulacao na

topologia fraca e este ponto e uma medida invariante pelo shift.

1.6.2 O teorema de Furstenberg

Uma pergunta natural a respeito do teorema de Poincare e se dado oconjunto A com medida positiva existe uma certa estrutura no con-junto de iterados que retornam a A; mais precisamente, sabemos queo conjunto e infinito, mas sera que existe uma estrutura aritmeticaneste conjunto? Esta pergunta foi resolvida por Furstenberg e sua re-sposta e conhecida como o teorema de Recorrencia Multipla Ergodicade Furstenberg.

Teorema 1.6.1 (Recorrencia Multipla Ergodica de Furstenberg).Seja T : X → X µ-invariante, k ≥ 3 e µ(A) > 0 entao existe Ntal que:

µ(A ∩ T−N (A) ∩ · · · ∩ T−(k−1)N (A)) > 0.

Este teorema e o coracao da prova do teorema de Szemerediatraves de metodos da Teoria Ergodica. Para indicar ao leitor a na-tureza deste resultado, veremos agora a prova do teorema de Fursten-berg em certos casos particulares importantes.

O primeiro exemplo e tomar um sistema de Bernoulli. Novamente,seja A um conjunto finito com r elementos, X = AN e T o shift neste


i

i

i

i

i

i

i

i


espaco. Sejam p1, . . . , pr numeros nao-negativos tais que∑

pi = 1.Isto da uma probabilidade em A e tomando a medida produto temosuma probabilidade em X.

A σ-algebra produto e gerada pelos cilindros com um numerofinito n de coordenadas, isto e conjuntos da forma C = w ∈ Z; wi1 =j1, . . . wjn

= jn e a medida de Bernoulli e dada por µ(C) = pj1 . . . pjn

sendo depois estendida para a σ-algebra gerada. E simples mostrarque esta medida e invariante pelo shift (de fato basta mostrar queµ(B) = µ(T−1(B)) apenas quando B e um cilindro).

Da mesma maneira, como os cilindros geram a σ-algebra, bastaprovar o teorema de Furstenberg para tais conjuntos. Sejam entaoC0, C1, . . . , Ck cilindros e observe que se n e muito grande entao ascoordenadas que definem os cilindros T−nl(Cl) sao todas disjuntas.Portanto, temos:

µ(C0 ∩ T−n(C1) ∩ · · · ∩ T−kn(Ck)) = µ(C0)µ(C1) . . . µ(Ck)) > 0.

Isto prova o teorema neste exemplo.Outro exemplo seria um sistema periodico, isto e, uma dinamica

tal que T p = T para algum p. Neste caso, o resultado e totalmentetrivial; uma dinamica (menos trivial) nesta linha de raciocınio e oseguinte exemplo quase-periodico: X = S1 = R/Z, µ a medida deLebesgue no cırculo e T (x) = x + α(mod 1) para algum α.

Dado A um conjunto mensuravel tal que µ(A) > 0, note que afuncao

∫1A(x + y)dµ(x) e contınua em y. Logo, para todo ε > 0

existe δ tal que se |y| < δ entao µ(A∩ (A−y)) > µ(A)− ε. Portanto:

µ(A ∩ (A− y) ∩ (A− 2y) ∩ · · · ∩ (A− ky)) > µ(A)− (k + 1)ε.

Escolhendo ε < µ(A)k+1 , tomando o δ correspondente e definindo o con-

junto Dδ = n ≥ 1; nα ∈ (−δ, δ)(mod 1), entao, se n ∈ Dδ temosque:

µ(A ∩ T−n(A) ∩ · · · ∩ T−nk(A)) > µ(A)− (k + 1)ε > 0.

Notemos que o primeiro exemplo e um caso particular de sis-temas fracamente misturadores (“weak-mixing”), isto e sistemas quesatisfazem a seguinte igualdade, para todo A e B subconjuntos men-


i

i

i

i

i

i

i

i


suraveis:

limN→∞

1N

N∑n=1

(µ(A ∩ T−nB)− µ(A)µ(B))2 = 0.

Adaptando a ideia do caso Bernoulli, prova-se que o teorema deFurstenberg vale para sistemas fracamente misturadores (que pode-mos chamar tambem de caso “pseudo-aleatorio”) .

O segundo exemplo e um caso particular de sistemas compactos,isto e sistemas tais que, para toda funcao f ∈ L2(µ), o fecho doconjunto f, Tf, T 2f, . . . , Tnf, . . . e compacto. Adaptando a ideiausada para rotacoes, prova-se o teorema de Furstenberg para sistemascompactos (que podemos chamar tambem de caso “estruturado”).

No contexto geral, o teorema de Furstenberg segue entao de umadecomposicao em varios nıveis do sistema em partes fracamente mis-turadoras e compacta, que nao tem muita correlacao entre si ao longode uma torre de extensoes. Cabe ressaltar que a existencia destatorre de extensoes e um fato altamente nao-trivial (conhecido comoteorema de estrutura) e foge ao escopo deste livro. Entretanto, umaversao desta ideia num contexto finitario sera exposta no capıtulo 2do livro.

1.6.3 Prova do teorema de Szemeredi

Uma vez com o teorema de recorrencia multipla podemos dar umaprova rapida do teorema de Szemeredi usando o shift.

Sejam X = 0, 1N e T : X → X o shift. Tome (xn) =1A(n), onde 1A(x) e a funcao caracterıstica de A, e considere µk =1k

∑k−1j=0 δT j(x). Entao, como vimos anteriormente, a menos de passar

a uma subsequencia, podemos supor que µ = lim µk e uma medidainvariante para T .

Defina Y = (yn); y1 = 1. Temos µ(Y ) = lim µk(Y ) = lim 1k |A ∩

[1, k]| > 0 por hipotese. Logo, pelo teorema de Furstenberg, segueque existe um N tal que µ(Y ∩T−N (Y )∩· · ·∩T−(k−1)N (Y )) > 0. Emparticular existem (infinitos) z ∈ Y ∩ T−N (Y ) ∩ · · · ∩ T−(k−1)N (Y ).Isto e, existe x tal que x, x + N, . . . , x + (k − 1)N ∈ A. Isto prova oteorema de Szemeredi.


i

i

i

i

i

i

i

i


1.7 O Teorema de Szemeredi quantitativo

Nesta secao veremos algumas reformulacoes do teorema 1.3.1 de Sze-meredi (muito uteis para os nossos propositos futuros).

Comecaremos por observar que o teorema de Szemeredi e equiva-lente a seguinte afirmacao:

Para todo k ≥ 1 e 0 < δ ≤ 1, existe um inteiro NSZ(k, δ) ≥ 1 talque, para qualquer N ≥ NSZ , todo conjunto A ⊂ 1, . . . , N com

cardinalidade |A| ≥ δN contem pelo menos uma progressaoaritmetica de comprimento k.

Logicamente, a afirmacao acima implica diretamente o teoremade Szemeredi.

Na outra direcao, mostraremos agora que, se a afirmacao e falsapara um certo par (k, δ) entao existe um conjunto Y ⊂ N∗ com|Y ∩ 1, 2, . . . , n| ≥ δr, ∀ r ∈ N∗ tal que Y nao contem nenhumaprogressao aritmetica de comprimento k.

Para isso, provaremos inicialmente que, se nao existe NSZ(k, δ),entao, para cada n ∈ N∗, existe um conjunto Xn ⊂ 1, 2, . . . , n com|Xn ∩ 1, 2, . . . , k| ≥ δk para 1 ≤ k ≤ n tal que Xn nao contemnenhuma progressao aritmetica de tamanho k. Com efeito, seja εn =max

1≤k≤n((dδke − 1)/k) < δ. Afirmamos que, se N e suficientemente

grande e A ⊂ 1, 2, . . . , N tem pelo menos δN elementos, entaoexiste m ≤ N − n tal que |A ∩ m + 1, . . . , m + k| ≥ δk, para1 ≤ k ≤ n. De fato, se nao for o caso, existem s ∈ N∗, k1, k2, . . . , ks ∈1, 2, . . . , n tais que N ≥ k1 + k2 + · · · + ks > N − n e, para 1 ≤r ≤ s, |A ∩ (∑

j<r

kj ,∑j≤r

kj

]| < δkr,, donde1kr|A ∩ (∑

j<r

kj ,∑j≤r

kj

]| ≤εn < δ, e logo δN ≤ |A| ≤ n + εn · N , o que e absurdo para N >

n

δ − εn· Logo, basta tomar um conjunto A ⊂ 1, 2, . . . , N com pelo

menos δN elementos que nao contem nenhuma progressao aritmeticade tamanho k para concluir a existencia de Xn.

Agora, para cada r ∈ N∗, seja πr : 2N → 21,2,...,r dada porπr(A) = A ∩ 1, 2, . . . , r. Construımos indutivamente conjuntosY1, Y2, Y3, . . . com Yr⊂1,2,. . ., r para cada r ∈ N∗ tais que Yr+1 ∩1, 2, . . . , r = Yr , ∀ r ∈ N∗ da seguinte forma: Y1 := 1 ⊂ Xn , para


i

i

i

i

i

i

i

i

[SEC. 1.7: O TEOREMA DE SZEMEREDI QUANTITATIVO 29

todo n ∈ N∗. Dado Yr, r ∈ N∗ tal que Yr = πr(Xn) para infinitosn ∈ N, existe Yr+1 ⊂ 1, 2, . . . , r+1 com Yr+1∩1, 2, . . . , r = Yr talque Yr+1 = πr+1(Xn) para infinitos n ∈ N (de fato, se πr(Xn) = Yr ,existem apenas duas possibilidades para πr+1(Xn)). Agora, e facilver que Y =

⋃n∈N∗

Yn satisfaz πr(Y ) = Yr , ∀ r ∈ N∗, donde πr(Y ) =

πr(Xn) para infinitos n ∈ N. Em particular, |Y ∩ 1, 2, . . . , r| ≥ δr,∀ r ∈ N∗ e Y nao contem nenhuma progressao aritmetica de tamanhok.

Em seguida, vamos introduzir uma linguagem mais analıtica efinitaria para obter uma outra reformulacao do teorema 1.3.1. Comeste intuito, relembremos a seguinte definicao:

Definicao 1.7.1. Seja f : A → C onde A e um conjunto finito.Entao:

E(f) = E(f(n); n ∈ A) =1|A|

∑

n∈A

f(n).

Dada f : (Z/NZ) → R uma funcao, podemos definir Tnf :(Z/NZ) → R os shifts da funcao por numeros naturais n ∈ Z/NZ (oun ∈ Z) atraves da formula: Tnf(x) := f(x + n). Diremos tambemque uma funcao f : Z/NZ→ C e limitada se ‖f‖L∞ ≤ 1.

Com esta notacao, podemos reformular o teorema de Szemeredido seguinte jeito:

Teorema 1.7.1 (Szemeredi – versao quantitativa). Para todo k ≥ 1inteiro e 0 < δ ≤ 1 real, existem N0(k, δ) inteiro e c(k, δ) > 0 realtais que, para todo N ≥ N0(k, δ) um numero primo grande, qualquerf : Z/NZ→ R+ uma funcao limitada com E(f |Z/NZ) ≥ δ verifica

E(k−1∏

j=0

T jrf(x)|x, r ∈ Z/NZ) ≥ c(k, δ).

Observacao 1.7.1. Com relacao a versao quantitativa do teoremade Szemeredi enunciada acima, iremos construir (no apendice destecapıtulo) alguns exemplos devidos a F. Behrend de subconjuntos S

do intervalo [1, N ] tais que |S| ≥ N1− 2

√2 log 2+ε√log N e S nao contem

progressoes aritmeticas de tamanho 3. Mais ainda, modificando o


i

i

i

i

i

i

i

i


esquema do argumento de Behrend, veremos que, acerca do comporta-mento de c(k, δ) acima em termos de δ, nao podemos esperar em geralque c(k, δ) tenha comportamento polinomial em δ (i.e., c(k, δ) ≥ δCk

para algum Ck > 0): com efeito, provaremos que c(3, δ) ≤ δc log(1/δ).

Observe que o enunciado do teorema 1.7.1 fornece (a prıncipio)uma conclusao muito mais poderosa que o teorema de Szemerediusual. Com efeito, enquanto o teorema de Szemeredi permite con-cluir apenas a existencia de uma k-PA, a versao quantitativa permiteinferir a existencia de c(k, δ)N2 k-PAs (ao menos). Entretanto, ape-sar do teorema quantitativo de Szemeredi aparentar ter um enunciadomais forte, afirmamos que os teoremas 1.3.1 e 1.7.1 sao equivalentes.

Iniciaremos vendo porque o teorema de Szemeredi segue da versaoquantitativa: fixe k, δ e tome N um primo bem grande. Vamos su-por que A ⊂ 1, . . . , N tem cardinalidade |A| ≥ δN , pois A temdensidade positiva. Seja N ′ um primo entre kN e 2kN (cuja ex-istencia e assegurada pelo postulado de Bertrand). Vamos considerar1, . . . , N como subconjunto de Z/N ′Z e A′ o conjunto respectivode Z/N ′Z.

Ora, nossas escolhas implicam E(1A′ |Z/NZ) ≥ δ/2k. Pelo teo-rema de Szemeredi quantitativo segue que:

E(k−1∏

j=0

T jr1A′(x)|x, r ∈ Z/N ′Z) ≥ c(k, δ/2k).

Reescrevendo, temos que:

|(x, r) ∈ (Z/N ′Z)2;x, x+r, . . . , x+(k−1)r ∈ A′| ≥ c(k, δ/2k)(N ′)2.

Como N ′ ≥ kN e A′ ⊂ 1, . . . , N temos que 1 ≤ x ≤ N e −N ≤r ≤ N . Observe as progressoes com r = 0 contribuem apenas comno maximo N elementos. Removendo estas progressoes e tomandoN grande, o lado direito da estimativa ainda e positivo e portanto Acontem a progressao x, x + r, . . . , x + (k− 1)r. Vamos ver agora que,de fato, a versao quantitativa do teorema de Szemeredi e equivalentea sua versao original. Ja sabemos que a versao original e equivalentea versao finita, i.e., a existencia de NSZ(k, δ), ∀ k ∈ N∗, δ > 0. Logo,para concluir a equivalencia entres as duas formulacoes do teoremade Szemeredi, basta mostrar a seguinte


i

i

i

i

i

i

i

i

[SEC. 1.7: O TEOREMA DE SZEMEREDI QUANTITATIVO 31

Proposicao 1.7.1. Suponha que existe NSZ

(k,

δ

2). Entao existem

N0 ∈ N e α(k, δ) > 0 tais que, se N ≥ N0 para todo A ⊂ 1, 2, . . . , Ncom |A| ≥ δN , existem pelo menos α(k, δ)N2 progressoes aritmeticasde comprimento k contidas em A.

Demonstracao. Seja m0 = NSZ(k, δ/2). Entao, para todo m ≥m0 , todo subconjunto de 1, 2, . . . , m com pelo menos δm/2 ele-mentos contem uma progressao aritmetica de comprimento k. SejaN grande. Para cada r com 1 ≤ r ≤ bN/m0c, dividimos 1, 2, . . . , Nem r progressoes aritmeticas de razao r, do tipo 1 ≤ n ≤ N | n ≡a(mod r), para cada a com 0 ≤ a ≤ r−1. Cada uma dessas PA’s tempelo menos bN/rc elementos, e portanto pode ser decomposta comoa uniao de bbN/rc/m0c progressoes aritmeticas disjuntas de razoesiguais a r, comprimentos ≥ m0 (e quase iguais) e portanto diametrosentre r(m0−1) e r(2m0−1). Se A ⊂ 1, 2, . . . , N satisfaz |A| ≥ δN ,para cada r, #0 ≤ a ≤ r− 1 | #A∩ 1 ≤ n ≤ N | n ≡ a(mod r) ≥3δ

4bN/rc ≥ δr

4− 3δ(pois t <

δ

4− 3δ⇒ t +

3δ

4(1 − t) < δ), e

(como t <δ

4− 2δ⇒ t +

δ

2(1 − t) <

3δ

4) se #A ∩ 1 ≤ n ≤ N |

A ≡ a(mod r) ≥ 3δ

4bN/rc, pelo menos

δ

4− 2δ· bbN/rc/m0c das

progressoes de comprimento ≥ m0 que criamos tem intersecao com Acom proporcao relativa pelo menos δ/2, e logo contem uma k-PA. Isto

fornece pelo menosbN/m0c∑

r=1

δr

4− 3δ· δ

4− 2δbbN/rc/m0c > β(δ,m0)N2

k-PA’s contidas em A para N grande, onde β(δ,m0) = δ2/64m20 .

Cada uma dessas PA’s pode estar sendo contada algumas vezes, paradiferentes escolhas de r, mas se d e seu diametro, r deve ser um

divisor de d entred

2m0 − 1e

d

k − 1, i.e., r =

d

r′, onde k − 1 ≤

r′ ≤ 2m0 − 1. Temos assim no maximo 2m0 − k + 1 possibili-dades para r′, e logo para r, i.e., cada PA e contada no maximo2m0 − k + 1 vezes. Assim, A contem pelo menos α(k, δ)N2 k−PA’s,

onde α(k, δ) =δ2

64m20(2m0 − k + 1)

·


i

i

i

i

i

i

i

i


Observacao 1.7.2. A diferenca da prova do Teorema de Szemerediquantitativo para as provas anteriores e que, devida a natureza finitariados argumentos, podemos obter cotas explıcitas para o numero NSZ .As outras provas, como sao de carater “infinito” (usam de certamaneira o Axioma da Escolha) somente mostram a existencia de talnumero e nao dizem nada sobre a ordem de grandeza do mesmo. Aestrategia da prova deste teorema foi usada no resultado de Green-Tao e sera estudada no capıtulo 2. Recomendamos tambem a leiturade [11].

1.8 Outros resultados

Nesta secao indicaremos, sem provas, outras maneiras de enunciaralgumas das conjecturas citadas acima. Em seguida apresentaremosalguns resultados posteriores ao teorema de Green-Tao. Finalmente,faremos alguns comentarios sobre a natureza do numero N0(k, δ).

1.8.1 A funcao de Von Mangoldt e Reformulacoesde algumas conjecturas

Vimos nas secoes anteriores, que o teorema dos numeros primos podeser enunciado em termos da funcao de Von Mangold como:

1N

N∑n=1

Λ(n) = 1 + o(1).

Na verdade, melhorar as cotas para a esperanca da funcao de vonMangoldt1 implica em diversas conjecturas. Vamos listar algumasdelas sem provas:

• A Hipotese de Riemann e equivalente a seguinte afirmacao:

E(Λ(n)|[1, N ]) = 1 + O(N−1/2 log2 N).

• A conjectura dos primos gemeos seguiria da seguinte afirmacao:

lim infN→∞

E(Λ(n)Λ(n + 2) : 1 ≤ n ≤ N) > 0.

1Isto e, explicitar a velocidade de convergencia para zero do termo o(1).


i

i

i

i

i

i

i

i

[SEC. 1.8: OUTROS RESULTADOS 33

• A conjectura de Goldbach e equivalente a:

E(Λ(n1)Λ(n2)|n1, n2 ∈ [1, N ] e n1 + n2 = N) > 0 ∀ N par.

• E, finalmente, a conjectura fraca de Goldbach e equivalente a:

E(Λ(n1)Λ(n2)Λ(n3)|n1, n2, n3 ∈ [1, N ] e n1+n2+n3 = N) > 0∀ N ımpar.

1.8.2 Constelacoes de Primos e Progressoes Poli-nomiais

Um outro conjunto onde a nocao de primalidade existe sao os inteirosGaussianos Z[i] := a + bi; a, b ∈ Z. Neste caso, p e um primoGaussiano se ele so e divisıvel por ±1,±i,±p e ±ip.

Uma forma em Z[i] e um conjunto finito (vj)j∈J ∈ (Z[i])J deinteiros Gaussianos distintos. Uma constelacao em Z[i] com estaforma e qualquer J-upla (a + rvj)j∈J ∈ (Z[i])J (onde a ∈ Z[i] er ∈ Z[i]) de inteiros Gaussianos distintos.

A nocao de constelacao estende a nocao de progressoes aritmeticaspara inteiros Gaussianos. A existencia de muitas constelacoes for-madas por primos Gaussianos foi demonstrada por Tao [12]:

Seja (vj)j∈J uma forma qualquer de inteiros Gaussianos. Entao osprimos Gaussianos contem inifinitas constelacoes com esta forma.

Por outro lado, uma maneira alternativa de generalizar o conceitode progressao aritmetica e: como uma progressao aritmetica toma aforma x + P1(m), . . . , x + Pk(m) onde Pi(m) = (i − 1)m, podemosestender esta definicao permitindo que Pi ∈ Z[m] sejam polinomioscom valores inteiros tais que Pi(0) = 0 (para i = 1 . . . k). Estasprogressoes generalizadas sao ditas progressoes polinomiais.

A existencia de infinitas progressoes polinomiais formadas por pri-mos foi demonstrada recentemente por Tao e Ziegler [13]:

Sejam P1, . . . Pk polinomios como acima; dado ε > 0 existeminfinitos inteiros x e m tais que 1 ≤ m ≤ xε e x + Pi(m) sao primos

para i = 1 . . . k.


i

i

i

i

i

i

i

i


1.8.3 Buracos no conjunto dos numeros primos

De certa forma, todos os teoremas e resultados que apresentamos aquitem em comum a busca de certos padroes no conjunto dos numerosprimos. Neste sentido, uma pergunta natural e quao esparsos sao osprimos.

Seja entao pn o n-esimo primo, de modo que o tamanho do n-esimoburaco do conjunto dos primos e pn+1 − pn. O teorema dos numerosprimos diz que a media do tamanho destes buracos e essencialmentelog pn. Vamos definir ∆ como o menor numero tal que existem in-finitos buracos de tamanho menor que (∆ + ε) vezes a media dostamanhos. Isto e:

∆ = lim infn→∞

(pn+1 − pn

log pn

).

Conjecturava-se que ∆ = 0 e isto foi provado em trabalhos recentes:primeiro Goldston e Yıldırım [6]2 mostraram que ∆ < 1

4 e, emseguida, Goldston, Motohachi, Pintz e Yıldırım [4] demonstrarama conjectura. Nestes trabalhos, eles propoe um metodo para mostrara existencia de numeros primos grandes muito proximos3.

Observacao 1.8.1. Somente para ressaltar a dificuldade da conjec-tura dos primos gemeos, observe que a conjectura dos primos gemeose uma afirmacao muito mais forte do que o resultado ∆ = 0 de Gold-ston, Motohachi, Pintz e Yıldırım (o qual nao e nada simples de seprovar!).

1.8.4 O tamanho do numero N0(k, δ)

Sobre a magnitude do numero N0(k, δ) no teorema de Szemerediquantitativo, temos os seguintes resultados:

• T. Gowers provou que N0(k, δ) ≤ 22δ−ck

, onde ck = 22k+9;

• R. Rankin provou que N0(k, δ) ≥ exp(C(log 1δ )1+blog2(k−1)c);

2Os pingos nos i´s nao existem no nome de Yıldırım!3De fato, eles mostram que estes primos estao realmente bem proximos assu-

mindo uma conjectura de Elliot-Halberstam.


i

i

i

i

i

i

i

i

[SEC. 1.9: APENDICE AO CAPITULO 1 35

• J. Bourgain provou que N0(3, δ) ≤ 2Cδ−2 log(1/δ);

• Espera-se que N0(k, δ) ≤ 2ckδ−1, mas isto e um problema em

aberto (relacionado a conjectura de Erdos-Turan).

1.9 Apendice ao Capıtulo 1

1.9.1 Prova do Teorema de Dirichlet no caso a = 1e b qualquer

Nesta secao daremos uma prova deste caso particular usando polinomiosciclotomicos.

Sejam ζn = cos( 2πn ) + i sin( 2π

n ). Entao, temos que ζkn 6= 1 para

todo k = 1, . . . , n−1 e ζkn 6= ζj

n para todo 1 ≤ k < j ≤ n−1. Podemosescrever entao:

Xn − 1 =n−1∏

j=0

(X − ζjn).

Observe que ε = ζkn e uma raiz primitiva da unidade se, e so se,

(k, n) = 1. Alem disso o numero de raızes n-esimas primitivas daunidade e dado por ϕ(n) onde ϕ e a funcao de Euler. Portanto oseguinte polinomio e o polinomio de menor grau que possui todas asraızes n-esimas primitivas da unidade:

Φn(X) =∏

1≤k≤n−1 , (k,n)=1

(X − ζkn).

Mais ainda, temos que Xn − 1 =∏

m|nΦm(X).

E um exercıcio mostrar que se p e primo e r ≥ 1 entao:

Φp(X) = Xp−1X−1 = Xp−1 + Xp−2 + · · ·+ X + 1

Φpr (X) = Xpr−1

Xpr−1−1= Xpr−1(p−1) + Xpr−1(p−2) + · · ·+ Xpr−1

+ 1.

Observe que para todo k ≥ 1, Φk(X) e monico com coeficientesinteiros e que se k > 1 temos que Φk(0) = 1. Tambem pode-se provarque Φk(1) e igual a p se k e uma potencia de p e e igual a 1 caso


i

i

i

i

i

i

i

i


contrario. Finalmente pode-se mostrar que |Φk(a)| > 1 para todoa > 1.

Iremos usar as seguintes identidades. Se p e primo e divide nentao Φpm(X) = Φm(Xp) e se p nao divide m e r ≥ 1 entao:

Φmpr (X) =Φm(Xpr

)Φm(Xpr−1)

.

Alem disso, utilizaremos um resultado devido a Legendre que dizque os seguintes conjuntos formados por primos sao iguais:

E1 = p ; p|an − 1 ,mas p - am − 1, ∀1 ≤ m ≤ n− 1E2 = p ; p|Φn(a) e p ≡ 1 (mod n)E3 = p ; p - n e p|Φn(a).

Com este resultado, podemos provar o teorema de Dirichlet nocaso em que a = 1. Sejam pi ≡ 1 (mod b) primos com i = 1, . . . , r edefina N = bp1 . . . pr. Temos entao que |Φb(N)| > 1.

Tome p um primo que divide Φb(N). Pelas identidades acimacitadas, vemos que Φb(N) ≡ Φb(0) ≡ 1 (mod N). Portanto p naodivide N , logo p nao divide b. Pelo resultado de Legendre, segue quep ≡ 1 (mod b) e p 6= pi com i = 1, . . . , r. Repetindo o processo,encontramos infinitos primos na progressao aritmetica 1 + kb comk ≥ 1.

1.9.2 Prova da proposicao 1.4.2

Primeiramente, iremos estudar a analiticidade da funcao zeta.

Proposicao 1.9.1. 1 e o unico polo da funcao zeta de Riemann emRe(s) > 0, ele e simples e tem resıduo 1. De fato, em Re(s) > 0temos a expansao:

ζ(s) =1

s− 1+ 1 + s

∫ ∞

1

([x]− x)x1+s

dx.

Demonstracao. Seja P (x) = [x]. Entao, em Re(s) > 2, temos que∑n≥1

P (n)ns e

∑n≥1

P (n−1)ns convergem e, obviamente,

∫∞1

P (x)x−1−sdx e

analıtica em Re(s) > 1. Invocamos entao o seguinte lema:


i

i

i

i

i

i

i

i


Lema 1.9.1. Sejam f(s) =∑n≥0

an

ns , em Re(s) > a, uma funcao

meromorfa e P (x) =∑

n≤x

an tal que∑ P (n)

ns e∑ P (n−1)

ns convergem

em Re(s) > b e∫∞1

P (x)x−1−sdx e analıtica em Re(s) > c. Entao:

f(s) = s

∫ ∞

1

P (x)x−1−sdx.

Assim temos que ζ(s) = s∫∞1

[x]x−1−sdx em Re(s) > 1 (onde [x]e a funcao maior inteiro menor que x). Por outro lado:

s

∫ ∞

1

x.x−1−sdx = s

∫ ∞

1

1xs

dx =s

1− s(x−s+1)|∞1 = 1 +

1s− 1

.

Em particular ζ(s) = 1s−1 + 1 + s

∫∞1

([x]− x)x−1−sdx, e o resultadosegue pois a integral converge em Re(s) > 0.

A prova do lema segue das seguintes igualdades em Re(s) >maxa, b:

f(s) =∑ an

ns=

∑ P (n)− P (n− 1)ns

=∑

P (n)(1ns− 1

(n + 1)s)

=∑

sP (n)∫ n+1

n

x−1−sdx = s

∫ ∞

1

P (x)x−1−s.

Agora e usar continuacao analıtica.

A seguir iremos obter uma regiao livre de zeros para a funcao zeta.Esta regiao e relativamente simples de obter com as representacoesanteriores:

Proposicao 1.9.2. ζ(s) 6= 0 em Re(s) ≥ 1.

Demonstracao. Vamos considerar primeiro o caso em que Re(s) ≥σ > 1. Entao pela formula de Euler temos:

1|ζ(s)| =

∏p

|1− p−s| ≤∏p

(1 +1|ps| ) ≤

∏p

(1 +1pσ

).


i

i

i

i

i

i

i

i


Agora este ultimo produtorio e convergente pois:

logpn∏p1

(1 +1pσ

) =pn∑p1

log(1 +1pσ

) =pn∑p1

∑

m≥1

(−1)m+1p−mσ

m

≤pn∑p1

p−σ +pn∑p1

∑

m≥2

p−σm

≤pn∑p1

p−σ +pn∑p1

p−2σ

1− p−σ

≤ 2pn∑p1

p−σ < ∞.

De fato, o mesmo argumento prova que se ai ≥ 0 e∑

ai < ∞ entao∏(1 + ai) < ∞. Portanto ζ(s) 6= 0 em Re(s) > 1.Na reta Re(s) = 1 iremos usar a seguinte identidade trigonometrica:

3 + 4 cos θ + cos 2θ = 2(1 + cos θ)2 ≥ 0. Vamos supor por absurdoque existe um b tal que ζ(1 + ib) = 0. Considere a funcao φ(s) =ζ3(s)ζ4(s+ ib)ζ(s+2ib). Note que s = 1 e um zero de φ (a ordem dopolo cancela com a ordem do zero), portanto lim

s→1log |φ(s)| = −∞.

Por outro lado, se s > 1 e real, temos que, para alguma sequenciaan, vale

log |ζ(s + it)| = Re(log ζ(s + it)) = Re log(∏p

(1− p−s−it)−1) =

= −Re(∑

log(1− p−s−it)) = Re(∑ p(−s−it)m

m)

=: Re(∑

ann−s−it).

Logo:

log |φ| = 3Re(∑

ann−s) + 4Re(∑

ann−s−ib) + Re(∑

ann−s−2ib)

= Re(∑

ann−s(3 + 4n−ib + n−2ib))

= Re(∑

ann−s(3 + 4e−ib log n + e−2ib log n))

=∑

ann−s(3 + 4 cos(b log n) + cos(2b log n)) ≥ 0.


i

i

i

i

i

i

i

i


Esta contradicao finaliza a prova.

Vemos tambem que o argumento acima implica que a funcao− ζ′(s)

ζ(s) tem um polo em s = 1 do tipo 1s−1 (o qual e unico em

Re(s) ≥ 1).Outra maneira de achar uma regiao livre de zeros e a seguinte:

usando a expansao do logaritmo em (1.4.1), temos que (pela mudancade variavel n = dm) em Re(s) > 1 vale:

∑n

log n

ns=

∑n

∑

d|n

Λ(d)ds

=∑

n

∑

d|n

Λ(d)(dm)s

=∑ Λ(d)

ds

∑m

1ms

=∑ Λ(d)

ds.ζ(s)

Por outro lado:

d

dsζ(s) =

∑ d

dsm−s =

∑ d

ds(e−s log m) =

=∑

m−s(− log m) = −∑ log m

ms,

donde temos a equacao:

∑ Λ(d)ds

= −ζ ′(s)ζ(s)

.

Agora somando por partes temos que:

N∑1

1ns

≈ n

ns|N1 +

N∑1

s

ns,

(1− s)N∑1

1ns

≈ 1Ns−1

− 1,

∑ 1ns

=1

s− 1+ O(1).


i

i

i

i

i

i

i

i


Novamente somando por partes:

N∑1

log n

ns≈ log n

ns−1|N1 −

N∑1

ns − sns log n

n2s,

(1− s)N∑1

log n

ns≈ log N

Ns−1− 1

s− 1+ O(1),

∑ log n

ns=

1(s− 1)2

+ O(1).

Em particular nao existem zeros em Re(s) > 1 com s ≈ 1 etambem obtemos:

∑ Λ(d)ds

=1

s− 1+ O(1).

Veremos agora algumas estimativas sobre ζ que serao uteis no

Capıtulo 3. Ja sabemos que ζ(s) =1

s− 1+

∞∑n=1

( 1ns−

∫ 1

0

dx

(n + x)s

)

em Re s > 0, e Re(log(ζ(σ + 2it)ζ(σ + it)4ζ(σ)3)) ≥ 0, donde|ζ(σ + 2it)ζ(σ + it)4ζ(σ)3| ≥ 1, para σ ≥ 1, t ∈ R. Derivando aexpressao para ζ(s), obtemos

ζ ′(s) = − 1(s− 1)2

+∞∑

n=1

(∫ 1

0

log(n + x)dx

(n + x)s− log n

ns

)em Re s > 0.

Suponha que 10 ≥ Re s ≥ 1− b

log(|t|+ 2), onde t = Im s e b e

uma constante com 0 < b < 1/2. Temos entao

∣∣ζ(s)− 1s− 1

∣∣ ≤∞∑

n=1

∣∣ 1ns−

∫ 1

0

dx

(n + x)s

∣∣

=∑

1≤n≤|t|

∣∣ 1ns−

∫ 1

0

dx

(n + x)s

∣∣ +∑

n>|t|

∣∣ 1ns−

∫ 1

0

dx

(n + x)s

∣∣

≤ 2∑

1≤n≤|t|

1nRes

+∑

n>|t|

|s|nRe s+1

,


i

i

i

i

i

i

i

i


pois1ns− 1

(n + x)s= f(0)−f(x) = −f ′(d) ·x, para algum d ∈ (0, x),

onde f(y) = (n + y)−s satisfaz f ′(y) = −s(n + y)−s−1 ⇒ |f ′(y)| ≤|s|

nRes+1, ∀ y ∈ (0, 1). Assim,

∣∣ζ(s)− 1s− 1

∣∣ ≤ 2∑

1≤n≤|t|

1n1−b/ log(|t|+2)

+|s|

|t|1−b/ log(|t|+2)

≤ 2|t|b/ log(|t|+2)∑

1≤n≤|t|

1n

+|s| · |t|b/ log(|t|+2)

|t|= O(log(|t|+ 2)).

Temos tambem

∣∣ζ ′(s) +1

(s− 1)2∣∣ ≤

∑

1≤n≤|t|

∣∣∫ 1

0

log(n + x)dx

(n + x)s− log n

ns

∣∣

+∑

n>|t|

∣∣∫ 1

0

log(n + x)dx

(n + x)s− 1

ns

∣∣

≤ 2∑

1≤n≤|t|

log n

nRe s+

∑

n>|t|

|s| log n

nRe s+1

= O(| log t|2 +|s| log |t||t|Re s

)

= O((log(|t|+ 2))2).

Seja agora Z =z ∈ C | 10 ≥ Re z ≥ 1 − β

(log(|Im z|+ 2))9,

onde β e uma constante pequena. Temos |ζ(σ+2it)ζ(σ+it)4ζ(σ)3| ≥1 para σ ≥ 1, donde, como |ζ(σ + 2it)| = O(log(|t| + 2)), paraσ + it ∈ Z, escolhendo σ = 1 + c

/(log(|t| + 2))9, onde c > 0

e uma constante pequena, |ζ(σ)| = O(c−1(log(|t| + 2))9), dondetemos |ζ(σ + it)−4| ≤ |ζ(σ)|3|ζ(σ + 2it)| = O(c−3(log(|t| + 2))28),e portanto |ζ(σ + it)−1| = O(c−3/4(log(|t| + 2))7). Como |ζ ′(x +it)| = O((log(|t| + 2))2) para x ∈ [1, σ], segue que |ζ(1 + it)−1| =O((log(|t| + 2))7), se tomarmos a constante c > 0 suficientementepequena. De fato, ζ(σ + it) ≥ Ac3/4(log(|t| + 2))−7 para uma certa


i

i

i

i

i

i

i

i


constante positiva A independente de c. Assim, para

1− c

(log(|t|+ 2))9≤ a ≤ 1 +

c

(log(|t|+ 2))9

temos

|ζ(a + it)− ζ(σ + it)| ≤ |a− σ| ·max|ζ ′(x + it)|, a ≤ x ≤ σ= O(

c

(log(|t|+ 2))9)· (log(|t|+ 2))2)

= O(c(log(|t|+ 2))−7),

donde

|ζ(a + it)| ≥ Ac3/4(log(|t|+ 2))−7 −O(c(log(|t|+ 2))−7)

>12Ac3/4(log(|t|+ 2))−7,

para c suficientemente pequeno. Se, por outro lado, σ < d ≤ 10, de|ζ(d+2it)ζ(d+ it)4ζ(d)3| ≥ 1, segue que |ζ(d+ it)−4| ≤ |ζ(d)|3|ζ(d+2it)| ≤ |ζ(σ)|3|ζ(d + 2it)| = O((log(|t| + 2))28), pois |ζ(d + 2it)| =O(log(|t|+ 2)). Assim, |ζ(d + it)−1| = O((log(|t|+ 2))7), e segue quea estimativa para |ζ−1| vale em toda a regiao Z.

Finalmente, se 0 < λ < 1 e σ ≥ λ, temos, como antes, paras = σ + it,

∣∣ζ(s)− 1s−1

∣∣ ≤ ∑∞n=1

∣∣ 1ns −

∫ 1

0dx

(n+x)s

∣∣ ≤ 2∑

1≤n≤|t|1

nσ +∑

n>|t||s|

nσ+1 ≤ 2∑

1≤n≤|t|1

nλ +O(|s||t|σ) = O(|t|1−λ) +O(|t|1−σ) =O(|t|1−λ). Em particular, se Re s ≥ 3/4,

∣∣ζ(s)− 1s−1

∣∣ = O(|t|1/4).

1.9.3 Prova do teorema 1.4.2

Nesta secao, iremos fixar uma f ∈ L1loc([1,∞)), f ≥ 0, nao decres-

cente com f(x) = O(x) e denotaremos por g sua transformada deMellin. Primeiramente vamos provar que g e analıtica em Re(s) > 1.De fato, fixe s tal que Re(s) > σ > 1 e tome um A grande tal que sex > A entao |f(x)| ≤ C|x|. Temos que:

|∫ ∞

λ

f(x)x−1−s| ≤∫ ∞

λ

Cx−σ ≤ C

σ − 1λ1−σ.

Isto diz que limλ→∞

∫ λ

1f(x)x−1−s =

∫∞1

f(x)x−1−s. Logo g e analıtica

em Re(s) > 1.


i

i

i

i

i

i

i

i


Lembramos que se F ∈ L1loc(0,∞) e limitada, entao a transfor-

mada de Laplace L(z) =∫∞0

F (t)e−ztdt e analıtica em Re(z) > 0.Agora, um ponto importante e que se ela se estende para Re(z) = 0entao L(0) =

∫∞0

F (t)dt. Provaremos isto mais tarde.Vamos usar este fato para a funcao F (t) = e−tf(et) − c, com

t > 0. Ora, as hipoteses sobre f garantem que ela e limitada e estaem L1

loc(0,∞). Por outro lado, a mudanca de variavel x = et diz quea transformada de Laplace de f e:

L(z) =∫ ∞

0

(e−tf(et)− c)e−ztdt =∫ ∞

1

x−2−zf(x)dx− (cx−z

−z)|∞1

=g(z + 1)z + 1

− c

z=

1z + 1

(g(z + 1)− c

z− c).

Logo, pela hipotese de extensao de f , temos que L se estende aRe(z) = 0 e portanto L(0) =

∫∞1

f(x)−cxx2 dx. Como consequencia,

temos que c > 0 (do contrario a integral seria infinita pois f ≥ 0).Vamos supor, por absurdo, que existe um δ > 0 tal que lim sup f(x)

x −c > 2δ > 0. Tome ρ = c+2δ

c+δ > 1 e yn → ∞ uma sequencia tal quef(yn) > (c + 2δ)yn. Como f e nao decrescente, entao para todoyn < x < ρyn vale:

f(x) ≥ f(yn) > (c + 2δ)yn > (c + δ)x.

Portanto, temos que ψ(x) := f(x)−cxx2 > δ

x . Isto implica que:

∫ ρyn

yn

ψ(x)dx ≥∫ ρyn

yn

δ

xdx = δ log ρ > 0.

Fixando ε < δ2 log ρ, segue que se a e grande temos (por convergencia

da integral) que: | ∫∞a

ψ(x)| < ε. Podemos tomar a ≥ yn0 para algumn0, daı temos que:

δ log ρ < |∫ ρyn0

yn0

ψ(x)dx| ≤ |∫ ∞

yn0

ψ(x)−∫ ∞

ρyn0

ψ(x)| < 2ε < δ log ρ.

Este absurdo implica lim sup f(x)x ≤ c. Um argumento analogo da a

desigualdade desejada para o lim inf.


i

i

i

i

i

i

i

i


Faltou entao provar a afirmacao sobre a transformada de Laplace,isto e que a integral

∫∞0

F (t) converge e e igual a L(0) se a transfor-mada de Laplace se estende analiticamente para Re(z) = 0. Usandoum reescalonamento, podemos supor que |F | ≤ 1. Vamos consideraras integrais truncadas Lλ(z) =

∫ λ

0F (t)etz, as quais definem funcoes

analıticas em todo o plano complexo, e provar que limλ→∞

Lλ(0) = L(0).

Seja entao ε > 0 pequeno e tome R = ε−1. Por hipotese, e claroque L tem continuacao analıtica em uma vizinhanca de Re(z) ≥ 0,logo existe um δ > 0 tal que L e analıtica em B = D(0, R)∩Re(z) ≥−δ. Se W = ∂B, a formula de Cauchy diz que:

L(0)− Lλ(0) =1

2πi

∫

W

L(z)− Lλ(z)z

dz.

Agora usamos o seguinte truque: se ψ e analıtica entao a formulade Cauchy diz que 2πiψ(0) =

∫W

ψ(z)eλz

z dz e 0 =∫

Wψ(z)eλzz2

R2z dz.Somando as duas igualdades e aplicando-as a funcao L − Lλ temosque:

L(0)− Lλ(0) =∫

W

(L(z)− Lλ(z))eλz(1z

+z

R2)dz. (1.9.1)

Vamos denotar por Iφ(z) = φ(z)eλz( 1z + z

R2 ).Agora, vamos separar essa integral em regioes. Seja W+ := W ∩

Re(z) > 0 e W− := W ∩ Re(z) < 0. Como IL e analıticaem W , ela e limitada por uma constante C em W . Alem disso,existe um γ < δ tal que em W−

2 := W ∩ −γ ≤ Re(z) < 0 temos∫W−

2|dz| < 2πε

C . Considere entao W−1 := W ∩ Re(z) < γ e W−

∗ :=Re(z) < 0∩|z| = R. Observe que pela analiticidade de Lλ temosque

∫W− ILλ

=∫

W−∗

ILλ.

Podemos decompor a integral (1.9.1) como:

2πi(L(0)−Lλ(0)) =∫

W+IL−Lλ

(z)+∫

W−1

IL(z)+∫

W−2

IL(z)−∫

W−∗

ILλ.

Passando o modulo nessa igualdade e usando a notacao x = Re(z) e|z| = R temos que:

• A primeira integral e dominada por∫

W+ eλx e−λx

x2xR2 |dz| = 1

R =2πε.


i

i

i

i

i

i

i

i


• A segunda integral e dominada por 2πBe−λδ1∫

W−1|dz|.

• A terceira integral e dominada por∫

W−2

eλxB|dz| < 2πε.

• A quarta integral e dominada por∫

W−∗

eλx eλx

|x|2|x|R2 |dz| = 1

R =2πε.

Logo |L(0)−Lλ(0)| ≤ 3ε+ B2π

∫W−

1|dz|e−λδ1 , como querıamos demon-

strar.

1.9.4 Prova do teorema 1.5.3

A primeira observacao e que se para algum k e ε a primeira parte doteorema vale para x entao ela vale para uma vizinhanca inteira de xe portanto para algum ponto de Z.

Em seguida, usando o lema de Zorn, podemos supor que X e min-imal, isto e X nao possui nenhum subconjunto Y proprio fechado talque T (Y ) ⊂ Y . Em particular, os conjuntos Tm(x)∞m=0 sao densosem X, o que mostra a afirmacao para k = 1 (pois, por densidade,existe um n ∈ N tal que d(Tn(x), x) < ε).

A prova seguira por inducao. Suponha que o teorema vale paraalgum k ≥ 1, isto e, para todo ε > 0 existe x ∈ X e n ∈ N tal qued(T in(x), x) < ε para i = 1, . . . , k. Afirmamos que o conjunto de taispontos e denso em X.

De fato, seja U ⊂ X um aberto e B ⊂ U uma bola de raiomenor que ε. Vamos definir Bm = (Tm)−1(B) de modo que estesconjuntos formam uma cobertura de X (pela minimalidade de X).Por compacidade temos uma subcobertura finita Bm1 , . . . , Bmr.Seja δ > 0 um numero de Lebesgue desta cobertura, ou seja, umnumero tal que toda bola de raio δ esta contida em algum aberto destacobertura. Tome x e n tais que d(T in(x), x) < δ para i = 1, . . . , k eD a bola de centro x e raio δ. Entao existe j tal que D ⊂ Bmj , emparticular Tmj (D) ⊂ B. Ou seja que Tmj (T in(x)) pertencem a bolade raio ε centrada em Tmj (x) ∈ U . Isto prova a densidade.

Vamos voltar agora a prova do teorema. Fixe ε > 0. Pela hipotesede inducao existem x e n0 tais que d(T in0x0, x0) < ε/2 para i =1, . . . , k. Tomando x1 tal que Tn0(x1) = x0, temos d(T (i+1)n0x1, x0) <ε/2 para i = 1, . . . , k. Portanto segue que d(T in0(x1), x0) < ε/2 parai = 1, . . . , k + 1.


i

i

i

i

i

i

i

i


Por continuidade, existe ε1 < ε tal que se d(y, x) < ε1 entaod(T in0(y), x) < ε/2 para i = 1, . . . , k+1. Pela hipotese de inducao no-vamente, existe y1 tal que d(y1, x1) < ε1 e n1 tal que d(T in1(y1), y1) <ε1/2 para i = 1, . . . , k. Por desigualdade triangular temos que:

d(T in0(T (i−1)n1(y1)), x0) < ε2 para i = 1, . . . , k + 1.

Procedendo desta maneira (tomando x2 tal que Tn1(x2) = y1)encontramos pontos x2, x3, · · · ∈ X e naturais n2, n3, . . . tais quepara todo l temos:

d(T inl−1(xl), xl−1) < ε/2d(T i(nl−1+nl−2)(xl), xl−2) < ε/2

. . .

d(T i(nl−1+···+n0)(xl), x0) < ε/2 para i = 1, . . . , k + 1.

Por compacidade, existem l > m tal que d(xl, xm) < ε/2. Pordesigualdade triangular temos que:

d(T i(nl+1+···+nm)(xl), xl) < ε , para i = 1, . . . , k + 1.

Logo, basta tomar x = xl e n = nl−1 + · · ·+nm para finalizar a provado teorema.

1.9.5 O exemplo de F. Behrend

Conforme anunciamos na observacao 1.7.1, primeiramente vamos cons-truir exemplos de subconjuntos S do conjunto dos inteiros nao-negati-vos ≤ N sem nenhuma progressao aritmetica de tamanho 3 e com car-

dinalidade |S| ≥ N1− 2

√2 log 2+ε√log N ; em seguida, adaptaremos esta tecnica

para estudar o comportamento da funcao c(3, δ).Dados d ≥ 2, n ≥ 2 e k ≤ n(d−1)2, considere Sk(n, d) o conjunto

de todos os numeros inteiros da forma

x = a1 + a2(2d− 1) + · · ·+ an(2d− 1)n−1

cujos dıgitos ai na base (2d− 1) estao sujeitos as restricoes

0 ≤ ai < d e ‖x‖2 := a21 + · · ·+ a2

n = k.


i

i

i

i

i

i

i

i


Note que Sk(n, d) nao contem progressoes aritmeticas de tamanho3: com efeito, caso existissem x, x′, x′′ ∈ Sk(n, d) tais que x + x′ =2x′′, entao

‖x + x′‖ = ‖2x′′‖ = 2√

k

e‖x‖+ ‖x′‖ = 2

√k.

Logo, como a igualdade na desigualdade triangular ‖x + x′‖ ≤ ‖x‖+‖x′‖ so pode ocorrer quando os vetores (a1, . . . , an) e (a′1, . . . , a

′n) sao

proporcionais, vemos que x = x′ = x′′ (porque estes vetores temnormas iguais por hipotese).

Por outro lado, existem dn vetores (a1, . . . , an) satisfazendo a re-stricao 0 ≤ ai < d e n(d − 1)2 + 1 valores possıveis para k. Conse-quentemente, para algum k = K0, Sk(n, d) deve ter cardinalidade aomenos

dn

n(d− 1)2 + 1>

dn−2

n.

Como todos os elementos de Sk(n, d) possuem modulo < (2d − 1)n,se definirmos

ν(N) := max|S| ; S ⊂ [1, N ], S sem nenhuma 3-PA,

obtemos queν((2d− 1)n) > dn−2/n.

Agora, fixado ε > 0 e dado N grande, escolhemos n = b√

2 log Nlog 2 c

e d satisfazendo(2d− 1)n ≤ N < (2d + 1)n,

de maneira que

ν(N) ≥ ν((2d− 1)n) >dn−2

n>

(N1/n − 1)n−2

2n−2n

=N1−(2/n)

2n−2n(1−N−1/n)n−2

>N1−(2/n)

2n−1n= N1−(2/n)− log n

log N− (n−1) log 2log N

> N1− 2

√2 log 2+ε√log N .


i

i

i

i

i

i

i

i


Agora pretendemos modificar ligeiramente o raciocınio anteriorpara estudar o comportamento da funcao c(3, δ): fixamos d, n ≥ 1inteiros (a serem escolhidos mais tarde) e definimos φ : 1, . . . , N →0, . . . , 2d− 1n por

φ(x) := (bx/(2d− 1)icmod(2d− 1))n−1i=0 .

Para cada k entre 1 e n(d− 1)2, considere novamente os conjuntos

Sk(n, d) := (x1, . . . , xn) ∈ 0, . . . , d− 1n : x21 + · · ·+ x2

n = k

e defina Ak(n, d) := φ−1(Sk(n, d)). Conforme ja sabemos, Sk(n, d)e livre de 3-PA (exceto as 3-PAs triviais x, x, x). Isto implica queAk(n, d) so pode conter progressoes aritmeticas (n, n+r, n+2r) onder e um multiplo de (2d − 1)n. Em particular, o numero maximo de3-PAs em Ak(n, d) e N2/(2d − 1)n. Por outro lado, quando φ(x) ∈0, . . . , d−1n, a probabilidade de x pertencer a Ak(n, d) e 1

n(d−1)2+1 .Logo, temos a seguinte cota inferior para a cardinalidade de Ak(n, d):

|Ak(n, d)| ≥ c

nd22−nN.

Tomando n = c log(1/δ) e d = δ−c, obtemos que, para algum k,o conjunto Ak(n, d) satisfaz |Ak(n, d)| ≥ δcN e o numero maximode 3-PAs em Ak(n, d) e δc log(1/δ)N2. Em outras palavras, c(3, δ) ≤δc log(1/δ).


i

i

i

i

i

i

i

i

Capıtulo 2

Teorema deGreen-Tao-Szemeredi

2.1 Introducao

O principal objetivo deste capıtulo e apresentar as ideias da prova doteorema de Green e Tao.

Grosseiramente falando, a prova deste teorema consiste em doispassos:

• generaliza-se o teorema de Szemeredi para o contexto de me-didas pseudo-aleatorias obtendo-se assim o teorema de Green-Tao-Szemeredi (veja a secao 2.2 para mais detalhes);

• prova-se a existencia de medidas pseudo-aleatorias nosprimos (ao longo das linhas dos recentes resultados de Goldston-Yıldırım).

Uma vez que estes dois fatos ja estejam provados, veremos que oteorema de Green e Tao segue diretamente (veja a secao 2.2).

Porem, antes de entrar (na secao 2.4) nos detalhes do esboco de-lineado acima , pretendemos motivar os conceitos e taticas da provado teorema de Green-Tao-Szemeredi atraves do esquema de provado teorema de Roth (o qual corresponde ao caso particular k = 3

49


i

i

i

i

i

i

i

i

50 [CAP. 2: TEOREMA DE GREEN-TAO-SZEMEREDI

no teorema de Szemeredi) na secao 2.3 (enquanto que iremos deixaras discussoes relativas aos resultados de Goldston-Yıldırım para ocapıtulo 3).

A organizacao deste capıtulo sera assim:

• na secao 2.2 apresentaremos mais detalhadamente o esboco daprova do teorema de Green-Tao; em particular, iremos enunciarprecisamente os teoremas de Green-Tao-Szemeredi e Goldston-Yıldırım; finalmente, demonstraremos o teorema de Green-Taoassumindo estes dois resultados.

• na secao 2.3 esbocaremos a prova do teorema de Roth sobre aexistencia de uma quantidade infinita de progressoes aritmeticasde tamanho 3 (i.e., 3-PA) em conjuntos de densidade positiva,o qual servira de motivacao para a prova do teorema de Green-Tao-Szemeredi.

• finalizando este capıtulo, na secao 2.4, faremos a demonstracaodo teorema de Green-Tao-Szemeredi.

Fechando esta introducao, observamos que ao fim deste capıtulo oteorema de Green e Tao estara demonstrado exceto pelos resultadosde Goldston e Yıldırım, os quais deixaremos para discutir apenas noproximo capıtulo.

2.2 Estrategia da prova do teorema deGreen e Tao

Durante o resto deste capıtulo, nos iremos fixar k ≥ 3 o tamanhoda progressao aritmetica (PA) de primos que desejamos encontrar eN := |ZN | sera um numero primo (grande) de modo que os elementos1, . . . , N − 1 podem ser invertidos em ZN . Escreveremos o(1) paradenotar quantidades que tendem a zero quando N →∞ e O(1) paradenotar quantidades que ficam limitadas quando N → ∞. Em cer-tos lugares do texto, as quantidades o(1) (resp., O(1)) tendem a zero(resp., permanecem limitadas) dependendo de certos parametros (p.ex., j, ε). Quando isto ocorrer, colocaremos os parametros subscritos


i

i

i

i

i

i

i

i

[SEC. 2.2: ESTRATEGIA DA PROVA DO TEOREMA DE GREEN E TAO 51

nas quantidades (p. ex., oj,ε(1)). Alem disso, abreviaremos quanti-dades da forma O(1)X (resp., o(1)X) como O(X) (resp., o(X)).

Com estas notacoes em maos, podemos iniciar a contextualizacaodo teorema de Green e Tao. Lembre que este teorema diz que paratodo k ≥ 3, existem infinitas k-PA (i.e., progressoes aritmeticas detamanho k) formadas (apenas) por numeros primos. Alem disso,sabemos que o teorema de Szemeredi garante a existencia de muitas k-PA em subconjuntos de inteiros com densidade positiva. Mais ainda,ja sabemos tambem que o teorema de Szemeredi nao implica o teo-rema de Green e Tao porque os primos possuem densidade zero. En-tretanto, a ideia de Green e Tao e :

• apesar do teorema de Szemeredi nao se aplicar diretamente,podemos modifica-lo para que ele funcione em subconjuntoscom comportamento (aditivo) fracamente aleatorio1 (ou maisprecisamente pseudo-aleatorio); este resultado sera chamadoneste livro de teorema de Green-Tao-Szemeredi ;

• isto reduz o teorema de Green-Tao a provar que o conjunto dosnumeros primos e pseudo-aleatorio, um fato que segue mais oumenos diretamente dos trabalhos de Goldston e Yıldırım.

Daqui em diante, iremos detalhar os itens discutidos acima. Paraisso, comecaremos com a definicao de pseudo-aleatoriedade:

Definicao 2.2.1. • Dizemos que ν : ZN → R+ e uma medidase E(ν) = 1 + o(1).

• Uma medida ν : ZN → R+ satisfaz a (m0, t0, L0)-condicao deformas lineares se, para toda famılia de m ≤ m0 formas linearesψi : Zt

N → ZN , t ≤ t0, digamos ψi(x) =∑

Lijxj + bi, onde Lij

sao racionais com numeradores e denominadores menores queL0, as t-uplas (Lij)1≤j≤t nao sao multiplas racionais entre si ebi ∈ Z quaisquer, entao:

E(ν(ψi(x)) . . . ν(ψm(x))|x ∈ ZtN ) = 1 + om0,t0,L0(1).

1O ponto de pedir aleatoriedade fraca e que desejamos depois usar o resultadopara os primos.


i

i

i

i

i

i

i

i


• Uma medida ν : ZN → R+ satisfaz a m0-condicao de correlacaose para todo m ≤ m0 existem pesos τm : ZN → R+ tais queE(τ q

m) = Om,q(1) (condicao de momentos) para todo 1 ≤ q < ∞e

E(ν(x + h1) . . . ν(x + hm)|x ∈ Z) ≤∑

i<j≤m

τm(hi − hj).

para quaisquer hi ∈ ZN (nao necessariamente distintos).

• Uma medida ν : ZN → R+ e k-pseudo-aleatoria se ν : ZN →R+ satisfaz a (k · 2k−1, 3k− 4, k) condicao de formas lineares ea 2k−1 condicao de correlacao.

A definicao pode parecer estranha no inıcio, porem ela e baseadaem trabalhos de Goldston-Yıldırım, onde estuda-se majorantes parafuncoes modificadas de von Mangoldt (que por sua vez estao inti-mamente ligadas aos numeros primos). Intuitivamente, as condicoesacima falam que o conjunto de inteiros no suporte de ν tem pro-priedades aritmeticas (aditivas) fracamente aleatorias. A principalvantagem destas condicoes e que elas sao suficientemente fracas paraincluir o caso dos primos (apesar deste fato estar longe de ser triv-ial) e permitir o uso de uma versao do teorema de Szemeredi para osuporte destas medidas (veja o teorema 2.2.1 logo abaixo).

Munidos do conceito de pseudo-aleatoriedade, estamos aptos paraenunciar um dos resultados principais do trabalho de Green e Tao [5,Theorem 3.5]:

Teorema 2.2.1 (Green-Tao-Szemeredi). Se k ≥ 3, 0 < δ ≤ 1 e ν ek-pseudo-aleatoria entao para toda f : ZN → R+ tal que 0 ≤ f(n) ≤ν(n) e E(f) ≥ δ temos que:

E(f(n)f(n + r) . . . f(n + (k − 1)r)|n, r ∈ ZN ) ≥ c(k, δ)− ok,δ(1).

Observacao 2.2.1. Note que fazendo ν ≡ νconst ≡ 1 no teoremaacima obtemos automaticamente o teorema de Szemeredi como corolario.

A prova do teorema 2.2.1 e baseada nas ideias de Furstenberg (derecorrencia multipla em teoria ergodica) e nas normas de Gowers.Por enquanto, adiaremos a demonstracao do teorema 2.2.1 para asecao 2.4.


i

i

i

i

i

i

i

i

[SEC. 2.2: ESTRATEGIA DA PROVA DO TEOREMA DE GREEN E TAO 53

Visando aplicar o teorema 2.2.1 para finalizar a prova do teoremade Green e Tao, agora vamos ver como construir medidas (pseudo)aleatorias relacionadas aos primos. Iniciamos por relembrar a definicao:

Definicao 2.2.2. A funcao de von Mangoldt e

Λ(n) :=

log p se n = pm

0 caso contrario .

Lembre que esta funcao esta (essencialmente) suportada nos pri-mos (pois a contribuicao de potencias de primos e pequena), de modoque ela funciona como uma “funcao caracterıstica” dos primos. Emtermos dela, sabemos que o teorema de numeros primos pode ser re-formulado como E(Λ(n)) = 1 + o(1). Para usar o teorema de Green-Tao-Szemeredi no contexto dos numeros primos, precisamos acharuma medida k-pseudoaleatoria tal que ν(n) ≥ c(k)Λ(n). Porem esabido que tais medidas nao existem!2

Para contornar esse problema usa-se o “W-trick”. Seja w =w(N) → ∞ um parametro que pode crescer com N porem lenta-mente (i.e., 1

w(N) = o(1)) e seja W = Πp≤w(N); p e primop. A funcaode von Mangoldt modificada e:

Λ(n) =

φ(W )

W log(Wn + 1) se Wn + 1 e primo0 caso contrario .

Agora temos uma funcao que ainda ve os primos porem deixamosde ver potencias e certas nao-uniformidades vindas de produtos defatores pequenos. Considere w(n) com crescimento lento3, digamosw(n) << log log log n, de maneira que o teorema de Dirichlet diz que:

1N

∑

n≤N

Λ(n) = 1 + o(1).

2Basicamente porque os primos e a funcao de van Mangoldt estao concentra-dos, para todo q > 1 inteiro, nas φ(q) classes residuais a(mod q) tais que (a, q) = 1(onde φ(q) e a funcao de Euler), enquanto que medidas pseudo-aleatorias devemestar equidistribuıdas em todas as classes de congruencias modulo q; como oquociente φ(q)/q pode ser feito arbitrariamente pequeno, vemos que nao existemmajorantes pseudo-aleatorios da funcao de van Mangoldt.

3Apesar de pedirmos crescimento lento para w(n), pode-se constatar que, aorevisar os argumentos do capıtulo 3, basta tomar w(n) uma constante bem grande(dependendo apenas de k mas nao de N).


i

i

i

i

i

i

i

i


Em outras palavras, Λ e uma medida. Nesta situacao, o segundo re-sultado chave do trabalho de Green-Tao [5, Proposition 9.1] (baseadonos trabalhos de Goldston-Yıldırım) e:

Teorema 2.2.2. Se εk = 1/(k +4)!2k e N e um primo grande entaoexiste ν uma medida k-pseudoaleatoria tal que ν(n) ≥ 2−k−5k−1Λ(n)para εkN ≤ n ≤ 2εkN .

Assim como boa parte dos resultados importantes sobre os numerosprimos, a prova do teorema 2.2.2 passa pelo uso de certas regioes livrede zeros da funcao zeta de Riemann. Porem, para nao interromper-mos o fluxo de ideias, deixaremos para o capıtulo 3 deste livro ademonstracao completa do teorema 2.2.2.

Finalmente, assumindo momentaneamente os teoremas 2.2.1 e 2.2.2,demonstraremos o teorema de Green e Tao.

2.2.1 Prova do teorema de Green e Tao

Suponha que os teoremas 2.2.1 e 2.2.2 sejam validos.Se

f(n) =1

k2k+5Λ(n)1[εkN,2εkN ]

entao:

E(f) =1

Nk2k+5

∑

εkN≤n≤2εkN

Λ(n) =1

k2k+5εk(1 + o(1)).

Como o teorema 2.2.2 garante a existencia de uma medida k-pseudo-aleatoria majorando 2−k−5k−1Λ em [εkN, 2εkN ], podemos aplicar oteorema 2.2.1 de Green-Tao-Szemeredi para concluir que:

E(f(n) . . . f(n + (k − 1)r)|n, r ∈ ZN ) ≥ c(k, k−12−k−3εk)− o(1).

Como o caso r = 0 contribui com um fator O( 1N logk N) = o(1) na

expressao, obtemos a existencia de uma P.A. em ZN (tomando Ngrande). Mais ainda, sendo εk < 1/k e k ≥ 3 temos que essa P.A. euma P.A. legıtima de inteiros (e nao apenas uma k-PA em ZN ).


i

i

i

i

i

i

i

i

[SEC. 2.3: PROVA DO TEOREMA DE ROTH 55

2.2.2 Alguns comentarios

Uma vez que ja reduzimos o teorema de Green e Tao aos teore-mas 2.2.1 e 2.2.2, dedicaremos o resto deste capıtulo a prova doteorema 2.2.1 de Green-Tao-Szemeredi (enquanto que a prova do teo-rema 2.2.2 ficara para o capıtulo 3).

Entrentanto, para ilustrar as ideias por tras da prova do teoremade Green-Tao-Szemeredi (as quais podem ser tecnicas e duras numaprimeira leitura), faremos a prova do teorema de Roth (ou seja, doteorema de Szemeredi no caso k = 3). Em seguida, passaremos ademonstracao propriamente dita do teorema de Green-Tao-Szemeredie assim encerraremos o presente capıtulo.

2.3 Prova do teorema de Roth

Conforme dissemos na introducao, para sentir o sabor da prova doteorema de Green-Tao-Szemeredi, vamos ver um pequeno argumentopara encontrar 3-PA em conjuntos de densidade positiva, o qual, ape-sar de ser bem particular e especıfico, contem boa parte das ideiasque iremos estudar em seguida.

Definimos Λ3(f, g, h) = E(f(n)g(n + r)h(n + 2r) : n, r ∈ ZN ). Oteorema de Roth pode ser reformulado assim:

Teorema 2.3.1. Para toda f : ZN → R nao-negativa com

0 < δ ≤ ‖f‖L1(ZN ) ≤ ‖f‖L∞(ZN ) ≤ 1

tem-seΛ3(f, f, f) ≥ c(3, δ)− oδ(1).

Em outras palavras, queremos cotas inferiores para Λ3(f, f, f).Comecamos com a observacao simples de que cotas superiores saobem “faceis” de se obter: por exemplo, pela desigualdade de Young,

|Λ3(f, g, h)| ≤ ‖f‖Lp‖g‖Lq‖h‖Lr ,

se 1 ≤ p, q, r ≤ ∞ e 1p + 1

q + 1r ≤ 2.

Por outro lado, estamos interessados apenas em cotas inferiorespara Λ3 e, a priori, as estimativas superiores nao parecem ser uteis


i

i

i

i

i

i

i

i


para provar cotas inferiores. Entretanto, podemos decompor f comouma parte “boa” g = E(f) e outra parte “ruim” b = f − E(f).Usando a multilinearidade de Λ3, podemos decompor Λ3(f, f, f) emoito pedacos:

Λ3(f, f, f) = Λ3(g, g, g) + · · ·+ Λ3(b, b, b).

Por hipotese, E(f) ≥ δ, donde o primeiro termo e Λ3(g, g, g) ≥ δ3.Logo, boas cotas superiores dos outros termos (p.ex., a soma dos setetermos restantes sao de magnitude menor que δ3) nos levariam aconcluir o teorema de Roth.

Porem, a estimativa acima (via desigualdade de Young) nao e boao suficiente, a menos que δ esteja proximo a 1 (digamos δ > 2/3).Mas, podemos refinar nosso argumento de cotas superiores usando atransformada de Fourier :

f(ξ) := E(f(x)eN (−xξ) : x ∈ ZN ),

onde eN (x) := exp(2πix/N). Da formula de inversao

f(x) =∑

ξ∈ZN

f(ξ)eN (xξ)

obtemos que

Λ3(f, g, h) =∑

ξ1,ξ2,ξ3

f(ξ1)g(ξ2)h(ξ3)×

E(eN (nξ1 + (n + r)ξ2 + (n + 2r)ξ3) : n, r ∈ ZN ).

As esperancas no lado direito acima sao 1 se ξ1 = ξ3 e ξ2 = −2ξ1

e 0 caso contrario. Em particular,

Λ3(f, g, h) =∑

ξ∈ZN

f(ξ)g(−2ξ)h(ξ).

Da formula de Plancherel ‖f‖L2(ZN ) = ‖f‖l2(ZN ) e da desigual-dade de Holder, segue que

|Λ3(f, g, h)| ≤ ‖f‖L2(ZN )‖g‖l4(ZN )‖h‖l4(ZN ). (2.3.1)

Usando esta estimativa, podemos provar que:


i

i

i

i

i

i

i

i


Proposicao 2.3.1. Seja f com uma decomposicao f = g + b onde

‖g‖L∞(ZN ), ‖b‖L∞(ZN ) = O(1)

e‖g‖L1(ZN ), ‖b‖L1(ZN ) = O(δ).

EntaoΛ3(f, f, f) = Λ3(g, g, g) + O(δ5/4‖b‖l4(ZN ))

eΛ3(f, f, f) = Λ3(g, g, g) + O(δ‖b‖l∞(ZN )).

Demonstracao. Por hipotese, ‖g‖L2(ZN ), ‖b‖L2(ZN ) = O(δ1/2), dondeuma aplicacao de Plancherel nos diz que

‖g‖l2(ZN ), ‖b‖l2(ZN ) = O(δ1/2).

Alem disso, as cotas L1 de g e b implicam

‖g‖l∞(ZN ), ‖b‖l∞(ZN ) = O(δ).

Logo, a desigualdade de Holder nos conduz a

‖g‖l4(ZN ), ‖b‖l4(ZN ) = O(δ3/4).

A proposicao segue decompondo Λ3(f, f, f) em oito partes eusando (2.3.1).

Esta proposicao sugere que uma estrategia para conseguir cotasinferiores nao-triviais de Λ3(f, f, f) passa por decompor f = g+b emuma funcao boa g tendo o valor Λ3(g, g, g) “alto” e uma funcao ruimb com norma l4 da sua transformada de Fourier pequena.

O leitor atento percebeu que ja indicamos uma possibilidade dedecomposicao: g = E(f) e b = f − E(f). Note que temos a cotaΛ3(g, g, g) ≥ δ3, uma estimativa relativamente boa, mas nao temosboas cotas para ‖b‖l4(ZN ); as nossas melhores cotas ate o momentosao O(δ3/4), o que e ruim pois permite que o erro domine o termoprincipal.4

4Com efeito, f = χ[1,δN ] tem Λ3(f, f, f) ∼ δ2 e Λ3(g, g, g) = δ3, por exemplo.


i

i

i

i

i

i

i

i


Entretanto, podemos eliminar o caso de b = f −E(f) linearmenteuniforme, i.e., ‖b‖l∞ ≤ δ2/100. O problema e o que fazer se b naoe linearmente uniforme. Neste caso, adota-se a ideia de usar umargumento de incremento na energia, i.e.,

• Argumento de incremento de energia: uma vez que b naoe uniforme, trocamos g por uma funcao com norma L2 maior.Ao final de um numero finito de passos, espera-se chegar a umafuncao b uniforme (ja que a energia e finita).

Logicamente, esta ideia tem que ser trabalhada em detalhes para verque ela conduz ao fim da prova do teorema de Roth. Para isto, vamosintroduzir a definicao:

Definicao 2.3.1. Dado K inteiro positivo, chamaremos as funcoesf : ZN → C da forma

f(x) =K∑

j=1

cj exp(2πiξjx/N),

onde |cj | ≤ 1 e ξj ∈ ZN de funcoes K-quase-periodicas. Alem disso,fixado σ > 0, dizemos que uma funcao f e (σ,K)-quase-periodica se‖f − fqp‖L2(ZN ) ≤ σ para alguma funcao K-quase-periodica fqp.

Observacao 2.3.1. Note que se f e g sao funcoes (σ,K)-quase-periodicas entao fg e (2σ,K2)-quase-periodica.

O ponto importante no conceito de funcoes f quase-periodicas eque podemos obter boas cotas inferiores de Λ3(f, f, f) neste caso:

Lema 2.3.1 (“Multipla Recorrencia” de funcoes quase-periodicas).Dados 0 < δ < 1, M ≥ 1, 0 < σ ≤ δ3/100M e 0 ≤ f ≤ M umafuncao nao-negativa limitada (σ,K)-quase-periodica com E(f) ≥ δ,entao

Λ3(f, f, f) ≥ c(K, M, δ)− oK,M,δ(1),

para algum c(K, M, δ) > 0.

Demonstracao. Seja fqp(x) =∑K

j=1 cj exp(2πixξj/N) uma funcaoK-quase-periodica aproximando f e tome ε = ε(K, δ) > 0 uma con-stante pequena. Pelo teorema de aproximacao simultanea de Dirichlet


i

i

i

i

i

i

i

i


(o qual decorre do prıncipio da casa de pombos), temos

E(‖rξj‖ ≤ ε para todo j ; r ∈ ZN ) ≥ c(ε,K). (2.3.2)

Aqui e fundamental ressaltar que a constante c(ε,K) > 0 nao dependede N . Por outro lado, considerando a dinamica T (x) := x + 1 efixando r tal que ‖rξj‖ ≤ ε (onde 1 ≤ j ≤ K), temos:

‖fqp T r − fqp‖L2(ZN ) ≤ C(K)ε,

Isto combinado com a desigualdade triangular implica:

‖f T r − f‖L2(ZN ) ≤ δ3/50M + C(K)ε.

Aplicando T r novamente na estimativa acima obtemos tambem

‖f T 2r − f T r‖L2(ZN ) ≤ δ3/50M + C(K)ε.

Como a funcao f e limitada, destas estimativas decorre que:

‖f · (f T r) · (f T 2r)− f3‖L1(ZN ) ≤ δ3/2 + C(K)Mε.

Entretanto, sendo f ≥ 0, usando nossa hipotese E(f) ≥ δ e a de-sigualdade de Holder, obtemos

‖f3‖L1(ZN ) ≥ ‖f‖3L1(ZN ) ≥ δ3.

Logo, E(f · (f T r) · (f T 2r)) ≥ δ3/2−C(K)Mε. Escolhendo ε > 0pequeno dependendo de δ,K e M , segue que

E(f · (f T r) · (f T 2r)) ≥ δ3/4.

Como f ≥ 0, tomando a media em r e usando (2.3.2), podemosconcluir

E(f(n) · (f T r)(n) · (f T 2r)(n) |n, r ∈ ZN ) ≥ δ3c(ε,K)/4.

Sendo Λ3(f, f, f) = E(f(n) · (f T r)(n) · (f T 2r)(n) |n, r ∈ ZN ),terminamos a demonstracao do lema.

Visando a utilizacao deste lema, estaremos interessados em de-compor funcoes arbitrarias em uma soma de uma funcao quase-perio-dica e uma funcao linearmente uniforme. Com este intuito, veremoscomo construir sigma-algebras cujas funcoes mensuraveis sejam todasquase-periodicas:


i

i

i

i

i

i

i

i


Lema 2.3.2. Sejam 0 < ε ¿ 1 e χ uma funcao da forma χ(x) :=exp(2πixξ/N). Entao, existe uma sigma-algebra Bε,χ tal que ‖χ −E(χ|Bε,χ)‖L∞(ZN ) ≤ Cε e, para todo σ > 0 existe K = K(σ, ε) > 0com a seguinte propriedade: toda f funcao Bε,χ-mensuravel satis-fazendo a estimativa ‖f‖L∞(ZN ) ≤ 1 e (σ,K)-quase-periodica.

Demonstracao. Seguiremos um processo randomico para obter asigma-algebra desejada: tome α um numero complexo no quadradounitario e seja Bε,χ a sigma-algebra cujos atomos tem a forma χ−1(Q),onde Q e um quadrado tal que os vertices de Q − εα estao sobreεZ2. Note que esta sigma-algebra possui O(1/ε) atomos e ‖χ −E(χ|Bε,χ)‖L∞(ZN ) ≤ Cε. Em particular, resta apenas verificar asegunda parte do lema para finalizar a prova. Observe que bastaverificar o fato desejado para σ = 2−n (onde n À 1) com proba-bilidade 1 − O(σ) em α. Como Bε,χ possui O(1/ε) atomos, e su-ficiente considerar o caso de f igual a funcao caracterıstica de umatomo A de Bε,χ e provar a propriedade desejada com probabilidade1 − O(c(ε)σ). Note que nesta situacao podemos reescrever f comof(x) = 1Q(χ(x) − εα). Aplicando o teorema de aproximacao deWeierstrass no disco |z| ≤ O(1/ε), encontramos um polinomio P (z, z)com C(σ, ε) termos e coeficientes limitados por C(σ, ε) tal que |P | ≤ 1no disco |z| ≤ O(1/ε) e |1Q(z)−P (z, z)| = O(c(ε)σ) para todo z nestedisco exceto por um conjunto de medida O(c(ε)2σ2). Isto implica que

‖1Q(χ(x)− εα)− P (χ(x)− εα, χ(x)− εα)‖L2(ZN ) ≤ c(ε)σ

com probabilidade 1−O(c(ε)σ) em α. Porem P (χ(x)−εα, χ(x)−εα)e uma combinacao linear de C(ε, σ) funcoes da forma exp(2πixξ/N)com coeficientes limitados por C(ε). Ou seja, P (χ(x)−εα, χ(x)−εα)e uma funcao K-quase-periodica (onde K = C(ε, σ)). Em particular,f e uma funcao (σ,K)-quase-periodica. Isto conclui a prova destelema.


i

i

i

i

i

i

i

i


Um corolario util deste lema e:

Corolario 2.3.1. Sejam 0 < εj ¿ 1 e χj(x) = exp(2πixξj/N), ondej = 1, . . . , n. Denote por Bεj ,χj

as sigma-algebras fornecidas pelolema acima. Entao, para todo σ > 0, existe K = K(n, σ, ε1, . . . , εn)tal que toda f funcao Bε1,χ1 ∨ · · · ∨ Bεn,χn-mensuravel satisfazendo aestimativa ‖f‖L∞(ZN ) ≤ 1 e (σ,K)-quase-periodica.

Demonstracao. Como o numero de atomos na sigma-algebra Bε1,χ1∨· · · ∨ Bεn,χn e C(n, ε1, . . . , εn), basta provar o corolario no caso emque f e a funcao caracterıstica de um atomo de Bε1,χ1 ∨ · · · ∨ Bεn,χn

.Porem, nesta situacao f e o produto de n funcoes de caracterısticasde atomos das sigma-algebras Bεj ,χj

. Logo, o corolario segue direta-mente da combinacao do lema anterior com a observacao 2.3.1.

Outra propriedade interessante destas sigma-algebras (alem deconter funcoes quase-periodicas) e a identificacao de obstrucoes paraa uniformidade linear :

Lema 2.3.3. Sejam b uma funcao limitada com ‖b‖l∞(ZN ) ≥ σ > 0 e0 < ε ¿ σ. Entao, existe uma funcao da forma χ(x) = exp(2πixξ/N)tal que a sigma-algebra Bε,χ associada satisfaz

‖E(b|Bε,χ)‖L2(ZN ) ≥ σ/2.

Demonstracao. Por definicao, existe uma frequencia ξ tal que|b(ξ)| ≥ σ, i.e.,

|E(b(n) exp(−2πinξ/N)|n ∈ ZN )| ≥ σ.

Definimos χ(x) := exp(2πixξ/N) e reescrevemos a desigualdade acimacomo

|〈b, χ〉L2(ZN )| ≥ σ.

Pelo lema anterior, sabemos que existe uma sigma-algebra Bε,χ talque

‖χ− E(χ|Bε,χ)‖L∞(ZN ) ≤ Cε.

Por outro lado, sendo b limitado e a esperanca condicional auto-adjunta, podemos combinar as duas estimativas acima para concluirque

〈E(b|Bε,χ), χ〉 = 〈b,E(χ|Bε,χ)〉 ≥ σ − Cε.


i

i

i

i

i

i

i

i


Isto implica que ‖E(b|Bε,χ)‖L2(ZN ) ≥ σ − Cε ≥ σ/2, o que finaliza aprova do lema.

O ultimo ingrediente para a prova completa do teorema de Rothe a seguinte proposicao de estrutura:

Proposicao 2.3.2 (“teorema quantitativo de Koopman-von Neu-mann”). Sejam F : R+×R+ → R+ uma funcao qualquer, 0 < δ ≤ 1,f uma funcao nao-negativa limitada satisfazendo E(f) ≥ δ e σ :=δ3/100. Entao, existem uma constante 0 < K ≤ C(δ, F ) e uma de-composicao f = g+b tais que g e limitada nao-negativa, E(g) = E(f),g e (σ,K)-quase-periodica e b verifica

‖b‖l∞(ZN ) ≤ F (δ,K). (2.3.3)

Demonstracao. A ideia sera utilizar o argumento de incremento deenergia para construir g e b. Para esta construcao, necessitaremosde duas sigma-algebras B e B as quais sempre terao a forma Bε1,χ1 ∨· · · ∨ Bεn,χn durante todo o argumento. Mais ainda, iremos quererestimativas do tipo

‖E(f |B)‖2L2(ZN ) ≤ ‖E(f |B)‖2L2(ZN ) + σ2/4. (2.3.4)

Observe que, pelo teorema de Pitagoras, a estimativa acima equivalea

‖E(f |B)− E(f |B)‖2L2(ZN ) ≤ σ/2.

A prova desta proposicao utilizara o seguinte algoritmo:

• Estagio 0 : Comecamos com B e B iguais a sigma-algebra trivial0,ZN. Note que a desigualdade (2.3.4) e satisfeita automati-camente neste estagio.

• Estagio 1 : Considere B uma sigma-algebra da forma Bε1,χ1 ∨· · · ∨ Bεn,χn , onde χj(x) = exp(2πixξj/N). Sendo a funcaoE(f |B) uma funcao limitada e B-mensuravel, o corolario 2.3.1diz que podemos encontrar K dependendo de δ, n, ε1, . . . , εn talque E(f |B) e (σ/2,K)-quase-periodica.

• Estagio 2 : Fazemos g = E(f |B) e b = f−E(f |B). Se ‖b‖l∞(ZN ) ≤F (δ,K), encerramos o algoritmo. Caso contrario, vamos parao estagio 3;


i

i

i

i

i

i

i

i


• Estagio 3 : Como nao terminamos o algoritmo no estagio 2,temos ‖b‖l∞ > F (δ,K). Pelo lema 2.3.3, podemos encontrarε ¿ F (δ,K) e uma funcao χ da forma χ(x) = exp(2πixξ/N)com uma sigma-algebra associada Bε,χ tal que

‖E(b|Bε,χ)‖L2(ZN ) ≥ F (δ,K)/2.

Da identidade

E(b|Bε,χ) = E(E(f |B ∨ Bε,χ)− E(f |B)|Bε,χ)

e do teorema de Pitagoras tiramos tambem que

‖E(f |B ∨ Bε,χ)− E(f |B)‖L2(ZN ) ≥ F (δ,K)/2.

Aplicando o teorema de Pitagoras novamente, obtemos a esti-mativa de incremento de energia:

‖E(f |B ∨ Bε,χ)‖2L2(ZN ) ≥ ‖E(f |B)‖2L2(ZN ) − F (δ,K)2/4.

• Estagio 4 : Trocamos B por B ∨ Bε,χ. Caso ainda tenhamos aestimativa (2.3.4), retornamos para o estagio 2; caso contrario,trocamos B por B e vamos para o estagio 1.

Afirmo que este algoritmo termina. Com efeito, fixado B (e con-sequentemente K), cada vez que passamos pelo estagio 4 a ener-gia ‖E(f |B)‖2L2(ZN ) aumenta de F (δ,K)2/4. Logo, o algoritmo ter-mina ou a estimativa (2.3.4) e violada em C(δ,K, F ) = Cσ2/F (δ,K)2

passos. No segundo caso, trocamos B pela sigma-algebra associadaas C(δ,K, F ) funcoes χ e parametros ε ≥ C(δ, F, K)−1 aparecendoneste processo. Isto implica que a quantidade K associada a estanova sigma-algebra B sera trocada por uma quantidade da formaC(δ,K, F ) e a energia ‖E(f |B)‖2L2(ZN ) cresceu pelo menos σ2/4 gracasa violacao de (2.3.4). Por outro lado, o fato de f ser limitada garanteque esta energia nao pode ser maior que O(1). Logo, estas trocas deB descritas acima so podem ser feitas no maximo O(σ−2) vezes. Jun-tando estas informacoes vemos que o algoritmo inteiro termina emC(δ, F ) passos (e a quantidade K nunca ultrapassa C(δ, F ) durantetodo o processo). Isto conclui a prova da proposicao.


i

i

i

i

i

i

i

i


Finalmente, vejamos como encerrar a demonstracao do teoremade Roth: seja F : R+ × R+ → R+ uma funcao que escolheremosem alguns instantes e apliquemos a proposicao acima para decomporf = g + b. Pelo lema 2.3.1, sabemos que

Λ3(g, g, g) ≥ c(δ,K)− oδ,K(1).

Combinando esta desigualdade com (2.3.3) e a proposicao 2.3.1, temos

Λ3(f, f, f) ≥ c(δ,K) + O(δ · F (δ,K))− oδ,K(1).

Tomando F “suficientemente pequena”, podemos absorver a segundaparcela do lado direito pela primeira parcela, de maneira que

Λ3(g, g, g) ≥ c(δ,K)/2− oδ,K(1).

Como K ≤ C(δ, F ) = C(δ), o teorema de Roth esta provado.Encerrando esta secao, recapitularemos abaixo os dois passos prin-

cipais da prova do teorema de Roth (o qual inspirara a demonstracaodo teorema de Green-Tao-Szemeredi):

• primeiro passo: definir uma classe de normas (ditas normasde Gowers ‖.‖Uk−1) para controlar a esperanca de uma k-PAestar no suporte de f ; note que, pela proposicao 2.3.1, no casok = 3, a norma l4 da transformada de Fourier e um bom can-didato;5

• segundo passo: generalizar o processo de incremento na en-ergia acima discutido.

2.4 Demonstracao do teorema de Green-Tao-Szemeredi

Nesta ultima secao do presente capıtulo, provaremos ao longo devarias subsecoes os resultados que nos ajudarao a formalizar as ideiasacima. Entretanto, como as demonstracoes sao tecnicas, o leitor pode

5De fato, no caso k = 3, a norma de Gowers ‖.‖U2 e a norma l4 da transfor-mada de Fourier; veja a observacao 2.4.1 na proxima subsecao.


i

i

i

i

i

i

i

i

[SEC. 2.4: DEMONSTRACAO DO TEOREMA DE GREEN-TAO-SZEMEREDI 65

se perder um pouco dos nossos objetivos finais. Por isso, daqui emdiante, ao final de cada subsecao, faremos um “resumo” dos resulta-dos provados e como eles se encaixam na estrategia de incremento deenergia acima tracada.

2.4.1 Normas de Gowers

Seja 0, 1d o cubo discreto d-dimensional, e w = (w1, . . . , wd) ∈0, 1d. Se h ∈ Zd

N entao w.h := w1.h1 + . . . wd.hd. Se fww∈0,1d

o produto interno de Gowers e:

〈(fw)〉Ud := E(Πwfw(n + w.h)|n ∈ ZN , h ∈ ZdN ).

A primeira observacao e que se fw = f para todo w entao 〈(fw)〉Ud ≥0. Assim podemos definir as normas de Gowers (usando fw = f):

‖f‖Ud := 〈(f)〉12d

Ud .

Uma ferramenta basilar para a analise das normas de Gowers e adesigualdade de Gowers-Cauchy-Schwarz :

|〈(fw)〉Ud | ≤ Πw‖fw‖Ud .

A prova desta desigualdade segue do fato de que, quando fw naodepende de wd, vale a igualdade

〈(fw)〉Ud = E(E(∏

w′∈0,1d−1

fw′,0(y + w′.h′) : y ∈ ZN )×

E(∏

w′∈0,1d−1

fw′,1(y + w′.h′) : y ∈ ZN |h′ ∈ (ZN )d−1)).

Logo, por Cauchy-Schwarz, temos

|〈(fw)〉Ud | ≤ 〈(fw′,0)〉1/2

Ud 〈(fw′,1)〉1/2

Ud .

Como podemos trocar wd por qualquer outro dıgito, aplicando a de-sigualdade acima d vezes, obtemos a desigualdade de Gowers-Cauchy-Schwarz.


i

i

i

i

i

i

i

i


Alem disso, a formula binomial e a multilinearidade do produtointerno nos levam a desigualdade triangular de Gowers:

‖f + g‖Ud ≤ ‖f‖Ud + ‖g‖Ud .

Finalmente, temos a relacao de monotonicidade:

‖f‖Ud−1 ≤ ‖f‖Ud ,

a qual e uma consequencia de Gowers-Cauchy-Schwarz aplicado afw := 1 quando wd = 1 e fw := f quando wd = 0.

Observacao 2.4.1. Como ‖.‖Ud sao homogeneas, acabamos de mostrarque ‖.‖Ud sao semi-normas. Entretanto, ‖.‖U1 nao e norma pois‖f‖U1 = E(f). Porem, pode-se provar (por calculo direto) que:

‖f‖U2 = (∑

f(ξ)4)14 ,

onde f(ξ) = E(f(x)e−2πiξ/N ; x ∈ ZN ) e vale a formula de inversaof(x) =

∑f(ξ)e2πixξ/N . Consequentemente, as normas de Gowers

para d ≥ 2 sao normas genuınas.

Com esta notacao, a generalizacao natural da proposicao 2.3.1 e:

Teorema 2.4.1 (von Neumann generalizado). Se ν e uma medidak-pseudoaleatoria e f0, . . . , fk−1 ∈ L1(ZN ) sao tais que |fj(x)| ≤1 + ν(x) entao se c0, . . . , ck−1 ∈ ZN sao distintos, temos que:

E(Πjfj(n + cjr)|n, r ∈ ZN ) = O(inf ‖fj‖Uk−1) + o(1).

Demonstracao. Comecemos com algumas simplificacoes: a menosde trocar ν por (ν + 1)/2, rearranjar fj , cj e transladar x por c0r,podemos assumir que

|fj(x)| ≤ ν(x), ∀ x ∈ ZN , j = 0, . . . , k − 1,

inf0≤j≤k−1

‖fj‖Uk−1 = ‖f0‖Uk−1

ec0 = 0.


i

i

i

i

i

i

i

i


Isto reduz o problema a provar que

E

k−1∏

j=0

fj(x + cjr)|x, r ∈ ZN

= O(‖f0‖Uk−1) + o(1).

Dividiremos a demonstracao desta igualdade em duas partes: naprimeira provaremos uma desigualdade de Cauchy-Schwarz e a apli-caremos k − 1 vezes ao lado esquerdo da igualdade acima, obtendoassim uma estimativa de E

(∏k−1j=0 fj(x + cjr)|x, r ∈ ZN

)por uma

soma com pesos de f0 sobre cubos (k − 1)-dimensionais; na segundamostraremos que a condicao de formas lineares implica que estes pe-sos sao iguais a 1 em media, o que nos permitira que deduzir o resul-tado desejado.

Para enunciar a desigualdade de Cauchy-Schwarz de modo razoavel,introduziremos um pouco de notacao. Dados 0 ≤ d ≤ k − 1, dois ve-tores y = (y1, . . . , yk−1) ∈ (ZN )k−1 e y = (y′k−d, . . . , y

′k−1) ∈ (ZN )d,

e um conjunto S ⊂ k − d, . . . , k − 1, definimos o vetor y(S) =(y(S)

1 , . . . , y(S)k−1) ∈ (ZN )k−1 por

y(S)i :=

yi se i /∈ Sy′i se i ∈ S.

Em outras palavras, S indica quais componentes de y(S) provem dey′ ao inves de y.

Lema 2.4.1. Sejam ν : ZN → R+ uma medida e φ0, . . . , φk−1 :(ZN )k−1 → ZN funcoes das k−1 variaveis yi tais que φi nao dependede yi para 1 ≤ i ≤ k − 1. Suponha que f0, . . . , fk−1 ∈ L1(ZN ) saofuncoes com |fi(x)| ≤ ν(x) para todo x ∈ ZN e 0 ≤ i ≤ k − 1. Paracada 0 ≤ d ≤ k − 1 e 1 ≤ i ≤ k − 1, defina

Jd :=E

∏

S⊂k−d,...,k−1(k−d−1∏

i=0

fi(φi(y(S)))×

×k−1∏

i=k−d

ν1/2(φi(y(S)))∣∣∣y ∈ (ZN )k−1, y′ ∈ (ZN )d

),


i

i

i

i

i

i

i

i


e

Pd := E

∏

S⊂k−d,...,k−1ν(φk−d−1(y(S)))|y ∈ (ZN )k−1, y′ ∈ (ZN )d

.

Entao para todo 0 ≤ d ≤ k − 2, temos a desigualdade

|Jd|2 ≤ PdJd+1.

Prova do lema 2.4.1. Considere Jd. Como φk−d−1 nao depende deyk−d−1, podemos tirar as quantidades dependentes de φk−d−1 damedia em yk−d−1, o que nos permite escrever

Jd = E(G(y, y′)H(y, y′)|y1, . . . , yk−d−2, yk−d, . . . , yk−1,

y′k−d, . . . , y′k−1 ∈ ZN ),

onde

G(y, y′) :=∏

S⊂k−d,...,k−1fk−d−1(φk−d−1(y(S)))ν−1/2(φk−d−1(y(S)))

e

H(y, y′) := E(∏

S⊂k−d,...,k−1

k−d−2∏

i=0

fi(φi(y(S)))

×k−1∏

i=k−d−1

ν1/2(φi(y(S)))|yk−d−1 ∈ ZN ).

Usando Cauchy-Schwarz,

|Jd|2 ≤ E(|G(y, y′)|2|y1, . . . , yk−d−2, yk−d, . . . , yk−1,

y′k−d, . . . , y′k−1 ∈ ZN )×

× E(|H(y, y′)|2|y1, . . . , yk−d−2, yk−d, . . . , yk−1,

y′k−d, . . . , y′k−1 ∈ ZN ).

Por outro lado, como |fk−d−1(x)| ≤ ν(x) para todo x,

E(|G(y, y′)|2|y1, . . . , yk−d−2, yk−d, . . . , yk−1, y′k−d, . . . , y

′k−1 ∈ ZN ) ≤ Pd.


i

i

i

i

i

i

i

i


Mais ainda, escrevendo a definicao de H(y, y′) e expandindo os quadra-dos trocando a variavel yk−d−1 pelas novas variaveis yk−d−1, y

′k−d−1,

vemos que

E(|H(y, y′)|2|y1, . . . , yk−d−2, yk−d, . . . , yk−1, y′k−d, . . . , y

′k−1 ∈ ZN )= Jd+1.

Isto completa a prova.

Aplicando este lema (k − 1) vezes, obtemos

|J0|2k−1 ≤ Jk−1

k−2∏

d=0

P 2k−2−d

d .

Observe que, por definicao,

J0 = E

(k−1∏

i=0

fi(φi(y))|y ∈ (ZN )k−1

).

Para provar a desigualdade desejada, escolhemos6

φi(y) :=k−1∑

j=1

(1− ci

cj

)yj

de modo que φ0(y) = y1 + · · · + yk−1, φi(y) nao dependem de yi e,para todo y, φ(y) = x + cir onde

r = −k−1∑

i=1

yi

ci.

Agora a transformacao sobrejetiva Φ : (ZN )k−1 → (ZN )2 definidapor

Φ(y) := (y1 + · · ·+ yk−1,y1

c1+ · · ·+ yk−1

ck−1)

6Estamos utilizando aqui que os numeros cj sao distintos.


i

i

i

i

i

i

i

i


tem numero constante de pre-imagens, donde uma conta simplesmostra que

E

k−1∏

j=0

fj(x + cjr)|x, r ∈ ZN

= E

(k−1∏

i=0

fi(φi(y))|y ∈ (ZN )k−1

)= J0.

Entretanto, Pd = 1+o(1) para cada 0 ≤ d ≤ k−2, pois ν satisfaza (2d, k − 1 + d, k)-condicao de formas lineares. Em particular, dasestimativas anteriores obtemos

J2k−1

0 ≤ (1 + o(1))Jk−1.

Fixe y. Quando S varia sobre os subconjuntos de 1, . . . , k − 1,φ0(y(S)) varia no cubo (k−1)-dimensional x+w ·h : w ∈ 0, 1k−1,onde x = y1 + · · ·+ yk−1 e hi = y′i − yi, i = 1, . . . , k − 1. Logo,

Jk−1 = E

W (x, h)

∏

w∈0,1k−1

f0(x + w · h)|x ∈ ZN , h ∈ (ZN )k−1

,

com o peso W (x, h) dado por

W (x, h) = E(k−1∏

w∈0,1

k−2∏

i=1

ν1/2(φi(y + wh))×

ν1/2(φk−1(y + wh))|y1, . . . , yk−2 ∈ ZN )

= E(k−2∏

i=1

∏

w∈0,1k−1,wi=0

ν(φi(y + wh))×∏

w∈0,1k−1,wk−1=0

ν(φk−1(y + wh))|y1, . . . , yk−2 ∈ ZN ),

onde wh ∈ (ZN )k−1 e o vetor com coordenadas (wh)j := wjhj ey ∈ (ZN )k−1 e o vetor com componentes yj para 1 ≤ k− 2 e yk−1 :=x − y1 − · · · − yk−2. Porem, a definicao da norma de Gowers dizemque

E

∏

w∈0,1k−1

f0(x + w · h)|x ∈ ZN , h ∈ (ZN )k−1

= ‖f0‖2

k−1

Uk−1 .


i

i

i

i

i

i

i

i


Portanto, basta provar que

E

(W (x, h)− 1)

∏

w∈0,1k−1

f0(x + w · h)|x ∈ ZN , h ∈ (ZN )k−1

= o(1).

Como |fj(x)| ≤ ν(x), segue que e suficiente mostrar

E

|W (x, h)− 1|

∏

w∈0,1k−1

ν(x + w · h)|x ∈ ZN , h ∈ (ZN )k−1

= o(1).

Por Cauchy-Schwarz, isto decorre imediatamente do seguinte lema:

Lema 2.4.2 (ν cobre uniformemente seus cubos). Para n = 0, 2,vale

E

|W (x, h)− 1|n

∏

w∈0,1k−1

ν(x + w · h)|x ∈ ZN , h ∈ (ZN )k−1

= o(1).

Demonstracao. Expandindo o quadrado, vemos que basta provarque, para q = 0, 1, 2, vale

E

W (x, h)q

∏

w∈0,1k−1

ν(x + w · h)|x ∈ ZN , h ∈ (ZN )k−1

= o(1).

Porem, isto e uma consequencia da condicao de formas lineares:

• no caso q = 0, aplique a (2k−1, k, 1)-condicao de formas linearescom variaveis x, h1, . . . , hk−1 e formas lineares x + w · h, w ∈0, 1k−1;

• no caso q = 1, aplique a (2k−2(k+1), 2k−2, k)-condicao de for-mas lineares com variaveis x, h1, . . . , hk−1, y1, . . . , yk−2 e formaslineares

φi(y + w · h), w ∈ 0, 1k−1, wi = 0 para 1 ≤ i ≤ k − 1x + w · h, w ∈ 0, 1k−1;


i

i

i

i

i

i

i

i


• no caso q = 2, aplique a (k2k−1, 3k − 4, k)-condicao de formaslineares com variaveis

x, h1, . . . , hk−1, y1, . . . , yk−2, y′1, . . . , y

′k−2

e formas lineares

φi(y + w · h), w ∈ 0, 1k−1, wi = 0 para 1 ≤ i ≤ k − 1φi(y′ + w · h), w ∈ 0, 1k−1, wi = 0 para 1 ≤ i ≤ k − 1x + w · h, w ∈ 0, 1k−1;

Aqui estamos adotando as convencoes yk−1 = x − y1 − · · · − yk−2 ey′k−1 = x − y′1 − · · · − y′k−2. Claramente isto completa a prova dolema.

Como dissemos antes, isto encerra a prova do teorema 2.4.1 devon Neumann generalizado.

Observacao 2.4.2. Note que so utilizamos a condicao de formaslineares na prova do teorema 2.4.1

Encerrando o estudo das normas de Gowers desta subsecao, enun-ciaremos um lema simples e util sobre a distancia de Gowers ‖.‖Uk−1

entre as medidas k-pseudo-aleatorias ν e νconst ≡ 1:

Lema 2.4.3. Suponha que ν e uma medida k-pseudo-aleatoria. Entao,

‖ν − 1‖Ud = o(1),

para todo d ≤ k − 1.

Demonstracao. Observe que a condicao de formas lineares para νimplicam facilmente que ‖ν‖Uk−1 = 1 + o(1). Entretanto, podemosrefinar um pouco mais este raciocınio. Com efeito, note que, pelamonotonicidade das normas de Gowers, basta ver que ‖ν − 1‖Uk−1 =o(1). Multiplicando por 2k−1, reduzindo nosso problema a provar que

E

∏

w∈0,1k−1

ν(x + w · h)∣∣x ∈ ZN , h ∈ Zk−1

N

= o(1).


i

i

i

i

i

i

i

i


O lado esquerdo da identidade acima pode ser expandido como

∑

A⊂0,1k−1

(−1)|A|E

( ∏

w∈A

ν(x + w · h)∣∣x ∈ ZN , h ∈ Zk−1

N

).

Olhando para a expressao

E

( ∏

w∈A

ν(x + w · h)∣∣x ∈ ZN , h ∈ Zk−1

N

)

para um A ⊂ 0, 1k−1 fixado, vemos que ela toma a forma

E(ν(φ1(x)) . . . ν(φ|A|(x))

∣∣x ∈ ZkN

),

onde x := (x, h1, . . . , hk−1) e φ1, . . . , φ|A| sao uma ordenacao das |A|formas lineares x 7→ x + w · h com w ∈ A. Obviamente estas formaslineares nao sao multiplas racionais entre si, donde a (2k−1, k, 1)-condicao de formas lineares pode ser aplicada para concluir a provado lema.

Facamos agora um resumo da discussao acima.

Resumo da subsecao “Normas de Gowers”:

Nesta subsecao identificamos normas naturalmente associadas ao prob-lema de contar progressoes cujos elementos pertencem ao suporte deuma famılia dada de funcoes, a saber as normas de Gowers, e prova-mos o teorema 2.4.1, o qual diz que as normas de Gowers majoramo numero de progressoes no suporte de uma sequencia de funcoes, amenos de um erro negligenciavel. Como vimos no caso do teorema deRoth, esta majoracao e importante para obter boas cotas por baixo,o nosso objetivo inicial. O proximo estagio sera a introducao do con-ceito de anti-uniformidade, o qual desempenhara papel importanteno momento de decompor nossas funcoes nas partes boa e ruim.

2.4.2 Anti-Uniformidade

Como as normas de Gowers para d ≥ 2 sao normas genuınas podemostomar as normas duais:

‖g‖(Uk−1)∗ := sup‖f‖

Uk−1≤1

|〈f, g〉|,


i

i

i

i

i

i

i

i


onde 〈f, g〉 denota o produto L2. Dizemos que g e anti-uniforme se‖g‖(Uk−1)∗ = O(1) e ‖g‖L∞ = O(1).

Observacao 2.4.3. Apesar de nao pretendermos utilizar, note queno caso k = 3, a observacao 2.4.1 nos da a formula:

‖g‖(U2)∗ =

∑

ξ∈ZN

|g(ξ)|4/3

3/4

.

Observe que se g e anti-uniforme e |〈f, g〉| e grande entao f naopode ser uniforme pois |〈f, g〉| ≤ ‖f‖Uk−1‖g‖(Uk−1)∗ . Logo temosuma obstrucao para uniformidade.

Alem disso temos uma maneira canonica de construir funcoes anti-uniformes: dada F ∈ L1(ZN ), definimos a funcao dual de F como:

DF (x) := E(Πw 6=0F (x + w.h)|h ∈ Zk−1N ).

Dentre as varias propriedades elementares destas funcoes, podemoscitar:

Lema 2.4.4. Seja ν uma medida k-pseudo-aleatoria e F ∈ L1(ZN)uma funcao qualquer. Tem-se:

• 〈F, DF 〉 = ‖F‖2k−1

Uk−1 ,

• ‖DF‖(Uk−1)∗ = ‖F‖2k−1−1Uk−1 e

• se |F | ≤ 1 + ν, entao ‖DF‖L∞ ≤ 22k−1−1 + o(1).

Demonstracao. A identidade 〈F,DF 〉 = ‖F‖2k−1

Uk−1 segue direta-mente das definicoes da norma de Gowers e DF , e deixamos comoexercıcio para o leitor. Para provar a segunda identidade, considereF 6= 0 (ja que o caso F = 0 e trivial) e note que a definicao das nor-mas duais combinadas com a identidade 〈F, DF 〉 = ‖F‖2k−1

Uk−1 dizemque basta provar que uma funcao f qualquer vale

|〈f, DF 〉| ≤ ‖f‖Uk−1‖F‖2k−1−1Uk−1 .

Porem, a definicao de DF mostra que 〈f,DF 〉 e o produto interno deGowers 〈(fw)w∈0,1k−1〉Uk−1 onde fw := f quando w = 0 e fw := F


i

i

i

i

i

i

i

i


caso contrario, donde a desigualdade acima segue da desigualdade deGowers-Cauchy-Schwarz.

Finalmente, o ultimo item segue da condicao de formas lineares.De fato, como F e limitada por 2(1+ ν)/2 := 2ν1/2, vemos que bastaprovar

Dν1/2(x) ≤ 1 + o(1)

uniformemente para todo x ∈ ZN . Por outro lado, a definicao defuncao dual diz que Dν1/2 pode ser expandido como

E

∏

w∈0,1k−1−0ν1/2(x + w · h)

∣∣∣∣∣ h ∈ Zk−1N

.

Como ν1/2 e uma medida k-pseudo-aleatoria, segue da condicao deformas lineares que este termo e 1 + o(1).

Observacao 2.4.4. Este e o unico ponto onde a condicao de formaslineares com termos nao-homogeneos bi 6= 0 e aplicada; com efeito,na demonstracao acima, todos os bi sao iguais a x.

Chamaremos as funcoes DF , onde F e limitada (pontualmente)por 1 + ν, de funcoes anti-uniformes basicas; uma propriedade rele-vante destas funcoes e sua boa distribuicao com respeito a ν:

Proposicao 2.4.1. Se ν e k-pseudoaletoria, Φ : IK → R e contınuae DF1, . . . , DFK funcoes anti-uniformes basicas, defina

Ψ(x) = Φ(DF1(x), . . . , DFK(x)).

Entao, 〈ν−1, Ψ〉 = ok,Φ(1). Alem disso, a quantidade da direita podeser tomada uniforme sobre um conjunto compacto de Φ’s.

Demonstracao. A ideia sera usar o teorema de aproximacao deWeierstrass e o fato de ν ser uma medida para reduzir nosso prob-lema a provar esta proposicao no caso mais “simples” de Φ ser umpolinomio.

Como de costume, podemos trocar ν por (ν + 1)/2 de modo que|Fj(x)| ≤ ν(x) para todo x ∈ ZN , 1 ≤ j ≤ K.


i

i

i

i

i

i

i

i


Lema 2.4.5. Seja d ≥ 1. Para todo polinomio P de grau d comcoeficientes reais (independentes de N) vale

‖P (DF1, . . . , DFK)‖(Uk−1)∗ = OK,d,P (1).

Demonstracao. Por linearidade e aumentando K para dK se neces-sario, basta provar o resultado para P (x1, . . . , xK) = x1 . . . xK . Ouseja, queremos ver que

〈f,

K∏

j=1

DFj〉 = OK(1)

para todo f : ZN → R satisfazendo ‖f‖Uk−1 ≤ 1. Expandimos o ladoesquerdo como

E

f(x)

K∏

j=1

E(∏

w∈0,1k−1:w 6=0

Fj(x + w · h(j))|h(j) ∈ (ZN )k−1)

∣∣∣∣∣x ∈ ZN

Fazendo a mudanca h(j) = h+H(j) para todo h ∈ (ZN )k−1, tomandoa media em h, expandindo os produtos em j e intercambiando asesperancas, podemos reescrever isso em termos do produto internode Gowers

E(〈(fw,H)w∈0,1k−1〉Uk−1 |H ∈ ((ZN )k−1)K),

onde H = (H(1), . . . , H(K)), f0,H := f , fw,H := gw·H para w 6= 0com w ·H = (w ·H(1), . . . , w ·H(K)) e

gu(1),...,u(K)(x) :=K∏

j=1

Fj(x + u(j)) para todo u(1), . . . , u(K) ∈ ZN .

Em particular, a desigualdade de Gowers-Cauchy-Schwarz e‖f‖Uk−1 ≤ 1 reduzem o lema a prova da estimativa

E

∏

w∈0,1k−1:w 6=0

‖gw·H‖Uk−1 |H ∈ ((ZN )k−1)K

= OK(1).


i

i

i

i

i

i

i

i


Por Holder, basta ver que

E(‖gw·H‖2k−1−1

Uk−1 |H ∈ ((ZN )k−1)K)) = OK(1),

para cada w ∈ 0, 1k−1 − 0.Fixe w. Como 2k−1 − 1 ≤ 2k−1 e estamos em espacos de proba-

bilidade, basta provar

E(‖gw·H‖2k−1

Uk−1 |H ∈ ((ZN )k−1)K)) = OK(1).

Esta ultima estimativa e verdadeira por um argumento assim:w 6= 0 implica que a transformacao w → w · H e recobrimento;isto permite usa-la para mudar as variaveis de maneira que o ladoesquerdo da identidade acima e

E(‖gu(1),...,u(K)‖2k−1

Uk−1 |u(1), . . . , u(K) ∈ ZN ).

Usando as definicoes de norma de Gowers e gu(1),...,u(K) , podemosexpandir este termo como

E

0@ Yew∈0,1k−1

KYj=1

Fj(x + u(j) + h · ew)

x, u(1), . . . , u(K) ∈ ZN , h ∈ Zk−1N

1A .

Fatorando, chegamos na expressao

E

K∏

j=1

E(Fj(x + u(j) + h · w) |u(j) ∈ ZN )

∣∣∣∣∣ x ∈ ZN , h ∈ Zk−1N

.

Usando a hipotese |Fj(x)| ≤ ν(x), nossa tarefa fica reduzida a estimar

E

(E(ν(x + u + h · w) |u ∈ ZN )K

∣∣∣∣∣ x ∈ ZN , h ∈ Zk−1N

).

Fazendo a mudanca de variaveis y = x + u e tomando a media sobrex, nosso objetivo e provar que

E

(E(ν(y + h · w) | y ∈ ZN )K

∣∣∣∣∣ h ∈ Zk−1N

)= OK(1).


i

i

i

i

i

i

i

i


Neste ponto, estamos prontos para usar a condicao de correlacao, aqual nos diz que

E

(ν(y + h · w)

∣∣∣∣∣ y ∈ ZN

)≤

∑

ew, ew′∈0,1k−1, ew 6= ew′ τ(h · (w − w′)),

onde τ e uma funcao peso satisfazendo E(τ q) = Oq(1). Usando a de-sigualdade triangular em LK(Zk−1

N ), vemos que basta provar apenasque

E

(τ(h · (w − w′))K

∣∣∣∣∣ h ∈ Zk−1N

)= OK(1),

para todos w, w′ ∈ 0, 1k−1 distintos entre si. Mas, sendo a trans-formacao h 7→ h · (w − w′) um recobrimento, o lado esquerdo acimae E(τK) = OK(1).

Voltemos agora a prova da proposicao. Lembre que o lema 2.4.4diz que as funcoes basicas anti-uniformes tomam valores no intervaloI = [−22k−1

, 22k−1]. Pelo teorema de aproximacao de Weierstrass,

dado ε > 0, podemos encontrar um polinomio P aproximando afuncao contınua Φ de modo que

‖Φ(DF1, . . . , DFK)− P (DF1, . . . , DFK)‖L∞ ≤ ε.

Como ν e uma medida (i.e., E(ν) = 1 + o(1)), temos

|〈ν − 1, Φ(DF1, . . . , DFK)− P (DF1, . . . , DFK)〉| ≤ (2 + o(1))ε.

Por outro lado, combinando os lemas 2.4.3, 2.4.5, obtemos que

|〈ν − 1, P (DF1, . . . , DFK)〉| = oK,ε(1)

porque P depende apenas de K e ε. Fazendo N grande (dependendode K, ε), vemos que

|〈ν − 1, Φ(DF1, . . . , DFK)〉| ≤ 4ε.

Isto finaliza a prova da proposicao 2.4.1.

Observacao 2.4.5. A unica vez em todo livro em que aplicamos acondicao de correlacoes foi no final da prova do lema 2.4.5.


i

i

i

i

i

i

i

i


Resumo da subsecao “Anti-Uniformidade”:

Nesta subsecao introduzimos o conceito de anti-uniformidade, o qualserve para identificar funcoes nao uniformes (ou melhor, obstrucoespara a uniformidade). Com efeito, vimos que toda funcao F gera nat-uralmente uma funcao DF anti-uniforme basica tal que a correlacao〈F, DF 〉 sera grande sempre que F nao for uniforme; alem disso,vimos um resultado mostrando que a medida pseudo-aleatoria se dis-tribui bem com relacao a algebra gerada pelas funcoes anti-uniformesbasicas.

A seguir, estudaremos as sigmas-algebras geradas pelos conjuntosde nıvel de funcoes anti-uniforme, as quais sao as pecas basicas dasigma-algebra com respeito a qual tomaremos esperancas de modo aobter funcoes boas (= uniformes).

2.4.3 Sigma-Algebras geradas por funcoes anti-uni-formes basicas

Veremos agora como funcoes anti-uniformes basicas geram natural-mente sigma-algebras onde elas sao bem comportadas (i.e. permitemo uso do teorema de Szemeredi na sua forma original).

Proposicao 2.4.2. Se ν e k-pseudoaleatoria e DF1, . . . , DFK saofuncoes anti-uniformes basicas. Para todo ε < 1 e σ < 1/2 existeuma sigma-algebra B tal que se N e um primo grande entao:

• ‖DFj − E(DFj |B)‖L∞ ≤ ε ∀j.• Existe um Ω ⊂ B (conjunto excepcional) tal que E((ν +1)1Ω) =

OK,ε(σ1/2).

• ‖(1− 1Ω)E(ν − 1|B)‖L∞ = OK,ε(σ1/2).

Demonstracao. O ponto de partida da prova desta proposicao e oseguinte lema garantindo que cada funcao gera uma sigma-algebra:

Lema 2.4.6. Seja ν uma medida k-pseudo-aleatoria, 0 < ε < 1e 0 < σ < 1/2 parametros, e G ∈ L∞(ZN ) uma funcao tomandovalores no intervalo I := [−22k−1

, 22k−1]. Entao, existe Bε,σ(G) uma

sigma-algebra tal que


i

i

i

i

i

i

i

i


• (G pertence a sua propria σ-algebra) Para toda B σ-algebra,

‖G− E(G|B ∨ Bε,σ(G))‖L∞(ZN ) ≤ ε.

• (Complexidade limitada) Bε,σ(G) tem O(1/ε) atomos.

• (Boa aproximacao por funcoes contınuas de G) Se A e umatomo de Bε,σ(G), entao existe ΨA : I → [0, 1] tal que

‖(1A −ΨA(G))(ν + 1)‖L1(ZN ) = O(σ).

Mais ainda, ΨA pertence a um compacto E ⊂ C0(I) que inde-pende de G, ν, N e A.

Prova do lema 2.4.6. Juntando o fato de ν ser uma medida com oteorema de Fubini, temos

∫ 1

0

∑

n∈ZE(1G(x)∈[ε(n−σ+α),ε(n+σ+α)](ν(x) + 1)|x ∈ ZN )dα

= 2σE(1 + ν(x)|x ∈ ZN ) = O(σ).

Portanto, podemos fixar α tal que∑

n∈ZE(1G(x)∈[ε(n−σ+α),ε(n+σ+α)](ν(x) + 1)|x ∈ ZN ) = O(σ). (2.4.1)

Definimos Bε,σ(G) como a σ-algebra cujos atomos sao G−1([ε(n +α), ε(n + α + 1)]) para n ∈ Z. Isto esta bem-definido porque osintervalos [ε(n + α), ε(n + α + 1)] particionam a reta.

Claramente se B e uma σ-algebra, entao a funcao G restrita aum atomo de B ∨ Bε,σ(G) toma valores num intervalo de diametroε, o que nos da o primeiro item do lema (G pertence a sua propriaσ-algebra). Agora, seja A := G−1([ε(n + α), ε(n + α + 1)]) um atomode Bε,σ(G). Como G toma valores em I, temos que n = O(1/ε) (casocontrario, A = ∅). Isto prova o segundo item do lema (complexidadelimitada). Finalmente, seja ψσ : R → [0, 1] uma funcao corte fixadatal que ψσ = 1 em [σ, 1 − σ] e ψσ = 0 em [−σ, 1 + σ], e definaΨA(x) := ψσ(x

ε −n−α). Obviamente, ΨA varia num compacto Eε,σ

de C0(I) (pois n e α sao limitados) e a igualdade (2.4.1) implicao terceiro item do lema (boa aproximacao por funcoes contınuas deG).


i

i

i

i

i

i

i

i


Agora voltamos a prova da proposicao 2.4.2. Tomamos o seguinteB := Bε,σ(DF1)∨· · ·∨Bε,σ(DFK), onde Bε,σ(DFj) e a sigma-algebrado lema 2.4.6. Claramente o primeiro item da proposicao 2.4.2 seguedo primeiro item do lema 2.4.6. Por outro lado, como cada Bε,σ(DFj)tem O(1/ε) atomos, B e gerada por OK,ε(1) atomos. Diremos queum atomo A de B e pequeno se E((ν + 1)1A) ≤ σ1/2. Denote por Ωa uniao de todos os atomos pequenos. Entao Ω ∈ B e vale o segundoitem da proposicao 2.4.2. Para provar o ultimo item, basta provarque

E((ν − 1)1A)E(1A)

= E(ν − 1|A) = oK,ε,σ(1) + OK,ε(σ1/2)

para todo atomo A nao pequeno. Da definicao de pequenez, temosque

E((ν − 1)1A) + 2E(1A) = E((ν + 1)1A) ≥ σ1/2

para A nao pequeno. Logo, como σ e pequeno e N e grande, esuficiente verificar que

E((ν − 1)1A) = oK,ε,σ(1) + OK,ε(σ1/2).

Por outro lado, sendo A a intersecao de K atomos Aj ∈ Bε,σ(DFj),j = 1, . . . , K, o lema 2.4.6 e a desigualdade de Holder mostram queexiste ΨA : IK → [0, 1] tal que

‖(ν + 1)(1A −ΨA(DF1, . . . , DFK))‖L1(ZN ) = OK(σ),

donde

‖(ν − 1)(1A −ΨA(DF1, . . . , DFK))‖L1(ZN ) = OK(σ).

Alem disso, ΨA esta num compacto Eε,K,σ de C0(IK). Isto e aproposicao 2.4.1 (de distribuicao uniforme com respeito a funcoesanti-uniformes basicas) implicam

E((ν − 1)ΨA(DF1, . . . , DFK)) = oK,ε,σ(1) = OK,ε(σ1/2),

pois N e grande dependendo de K, ε, σ. Esta estimativa e a desigual-dade triangular concluem a prova.


i

i

i

i

i

i

i

i


Resumo da subsecao “Sigma-Algebras geradas por funcoesanti-uniformes basicas”:

Nesta subsecao associamos a cada funcao anti-uniforme basica DFuma sigma-algebra B com respeito a qual a esperenca E(DF |B) deDF aproxima DF (ou seja, DF e quase constante nos atomos de B)e a medida pseudo-aleatoria ν tem valores proximos a 1 em media(com relacao a B).

No estagio seguinte, usaremos esta maquinaria de funcoes anti-uniformes basicas e suas sigma-algebras para formalizar o processode decomposicao em partes boas (uniformes) e ruins (anti-uniformes)atraves de uma inducao. Um ponto fundamental sera garantir queeste procedimento para com um numero finito de iteracoes. Istoseguira do argumento de incremento de energia.

2.4.4 O argumento de incremento na energia

Usando as sigma-algebras de funcoes anti-uniformes basicas, podemosobter a decomposicao desejada em partes uniformes e partes anti-uniformes:

Teorema 2.4.2 (Koopman-von Neumann generalizado). Seja ν k-pseudoaleatoria e f ∈ L1 tal que 0 ≤ f ≤ ν, ε << 1 e N e um primogrande. Entao existe uma sigma-algebra B e um conjunto excepcionalΩ ∈ B tal que:

• E(ν · 1Ω) = oε(1) (o conjunto excepcional e pequeno).

• ‖(1 − 1Ω)E(ν − 1|B)‖L∞ = oε(1) (boa distribuicao da funcaofora do conjunto excepcional).

• ‖(1− 1Ω)(f − E(f |B)‖Uk−1 ≤ ε1/2k

(uniformidade em B)

Demonstracao. A estrategia basica e a mesma do teorema de es-trutura ergodica de Furstenberg7: comecamos com a sigma-algebraB = ∅,ZN e olhamos para a funcao f − E(f |B). Se ela for uni-forme (i.e., vale o terceiro item acima), acabamos. Caso contrario,usamos os resultados sobre anti-uniformidade para achar uma G1

7Este teorema diz que podemos decompor qualquer sistema como uma ex-tensao weak-mixing de uma torre de extensoes compactas.


i

i

i

i

i

i

i

i


anti-uniforme com correlacao nao-trivial com f e adicionamos os con-juntos de nıvel de G1 a sigma-algebra B. A propriedade de correlacaonao-trivial ira garantir que a norma L2 de E(f |B) aumentara por umaquantidade nao-trivial8, enquanto que a pseudo-aleatoriedade de νmostra que E(f |B) fica uniformemente limitado. Neste ponto, repeti-mos este procedimento ate f−E(f |B) ficar suficientemente uniforme;note que o algoritmo ira parar em um numero limitado de passo (daordem de 22k

/ε) devido ao incremento de energia a cada passo.Agora vamos escrever esta estrategia de modo um pouco mais

organizado. Fixe ε e seja K0 o menor inteiro maior que 1 + 22k

/ε.Precisaremos de um parametro 0 < σ ¿ ε e tomaremos N grandedependendo de ε e σ. Construiremos B e Ω atraves de uma sequenciade funcoes anti-uniformes basicas DF1, . . . , DFK em ZN , conjuntosexcepcionais Ω0 ⊂ · · · ⊂ ΩK ⊂ ZN e sigma-algebras B0 ⊂ · · · ⊂ BK

para algum 0 ≤ K ≤ K0 assim:

• Passo 0: Iniciamos com K=0, B0 := ∅,ZN e Ω0 := ∅.• Passo 1: Fazemos FK+1 := (1− 1ΩK

)(f − E(f |BK)). Se

‖FK+1‖Uk−1 ≤ ε1/2k

definimos Ω := ΩK , B = BK e terminamos com sucesso o algo-ritmo.

• Passo 2: Caso‖FK+1‖Uk−1 > ε1/2k

definimos BK+1 := BK ∨ Bε,σ(DFK+1).

• Passo 3: Procuramos por conjunto excepcional ΩK+1 ⊃ ΩK emBK+1 com

E((ν + 1)1ΩK+1) = OK,ε(σ1/2) (2.4.2)

e‖(1− 1ΩK+1)E(ν − 1|BK+1)‖L∞ = OK,ε(σ1/2).

Se tal conjunto excepcional nao puder ser achado, terminamoso algoritmo com erro. Caso contrario, vamos para o passo 4.

8A ideia de usar uma correlacao nao-trivial para aumentar a norma L2 eprecisamente o argumento de incremento da energia.


i

i

i

i

i

i

i

i


• Passo 4: Aumentamos K para K + 1. Se K > K0, terminamoso algoritmo com erro. Caso contrario, voltamos ao passo 1.

Assuma por enquanto que o algoritmo termina sem erro no passo 3ou 4. Entao e claro que apos no maximo K0 + 1 iteracoes, teremosconstruıdo uma σ-algebra B e um conjunto excepcional Ω com aspropriedades desejadas, exceto pelo fato de que os termos de erro saoOK,ε(σ1/2) ao inves de oε(1), para N grande dependendo de σ,K, ε.Entretanto, isto pode ser remediado fazendo σ tender a zero bemdevagar.

Ou seja, reduzimos a prova deste teorema a mostrar que o al-goritmo termina sem erro. A demonstracao e por inducao: comohipotese para inducao em 0 ≤ K1 ≤ K0, suponha que o algoritmoou termina sem erro ou atinge o passo 2 da K1-esima iteracao semretornar um erro. Note que isto e obvio para K1 = 0. Assumindoisto provado para algum K1 < K0, desejamos provar o mesmo paraK1 + 1. Observe que podemos supor que o algoritmo nao terminouate o passo 2 do K1-esima iteracao. Neste estagio, temos σ-algebrasB0, . . . ,BK1+1, funcoes anti-uniformes basicas DF1, . . . , DFK1+1 econjuntos excepcionais Ω0, . . . , ΩK1 ja construıdos. Afirmamos que

‖DFj‖L∞ ≤ 22k−1+ Oj,ε(σ1/2), (2.4.3)

para todo 1 ≤ j ≤ K1 + 1. Isto segue do passo 3 das iteracoesanteriores (ou do passo 0 quando j = 1), os quais dizem que

‖(1− 1Ωj−1)E(ν − 1|Bj−1)‖L∞ = Oj,ε(σ1/2),

dondeE(ν|Bj−1)(x) = 1 + Oj−1,ε(σ1/2),

para todo x /∈ Ωj−1. Como 0 ≤ f(x) ≤ ν(x), concluımos as estimati-vas pontuais

0 ≤ (1− 1Ωj−1(x))E(f |Bj−1)(x) ≤ 1 + Oj,ε(σ1/2), (2.4.4)

das quais seguem, por definicao de Fj ,

|Fj(x)| ≤ (1 + Oj,ε(σ1/2))(ν(x) + 1). (2.4.5)


i

i

i

i

i

i

i

i


Em particular, uma simples aplicacao do lema 2.4.4 prova a nossaafirmacao acima.

Por outro lado, como BK1+1 e a σ-algebra gerada por

Bε,α1(DF1), . . . ,Bε,αK1+1(DFK1+1),

a proposicao 2.4.2 permite encontrar Ω tal que

E((ν + 1)1Ω) = OK1,ε(σ1/2)

e‖(1− 1Ω)E(ν − 1|BK1+1)‖L∞ = OK1,ε(σ1/2).

Definimos ΩK1+1 := Ω ∪ ΩK1 . Obviamente, ΩK1+1 tem as pro-priedades necessarias para se executar o passo 3 sem erro, e portantopodemos ir ate o passo 2 da K1 + 1-esima iteracao (ou terminar semerro), como querıamos provar.

Em outras palavras, o que provamos ate agora foi que temos ape-nas duas possibilidades para o algoritmo: ou ele termina sem erro oupercorre todo o caminho ate a K0-esima iteracao. Para finalizar ademonstracao, a propriedade-chave e que no caso do algoritmo atin-gir o passo 3 do K0 iterado, entao vale a estimativa de incremento deenergia

‖(1− 1Ωj )E(f |Bj)‖2L2

≥ ‖(1− 1Ωj−1)E(f |Bj−1)‖2L2

+ 22k−2ε−Oj,ε(σ1/2)−O(ε2),

(2.4.6)

para todo 1 ≤ j ≤ K0 (se N e grande dependendo de K0 e ε).Esta propriedade e suficiente para concluir a prova porque a desigual-dade (2.4.4) nos da

0 ≤ ‖(1− 1Ωj )E(f |Bj)‖2L2 ≤ 1 + Oj,ε(σ1/2), (2.4.7)

para todo 0 ≤ j ≤ K0. Como K0 e o menor inteiro maior que22k

/ε + 1, o prıncipio da casa de pombos gera uma contradicao paraε pequeno, σ pequeno e N grande dependendo de ε, σ.

Finalmente, resta apenas saber mostrar a estimativa de incre-mento na energia. A ideia e explorar o fato do algoritmo nao pararno segundo passo da (j − 1)-esima iteracao, o qual implica

‖Fj‖Uk−1 ≥ ε1/2k


i

i

i

i

i

i

i

i


Isto combinado com a definicao de Fj e o lema 2.4.4 diz que

|〈(1− 1Ωj−1)(f − E(f |Bj−1)), DFj〉| = ‖Fj‖2k−1

Uk−1 ≥ ε1/2.

Por outro lado, as estimativas pontuais (2.4.3), (2.4.5), (2.4.2) acimamostram que

〈(1Ωj− 1Ωj−1)(f − E(f |Bj−1), DFj)〉 = Oj,ε(σ1/2),

enquanto que o lema 2.4.6 e a estimativa (2.4.5) falam que

〈(1− 1Ωj)(f − E(f |Bj−1), DFj − E(DFj |Bj))〉 = O(ε).

Em particular, pela desigualdade triangular, ganhamos a cota infe-rior:

|〈(1− 1Ωj )(f − E(f |Bj−1)),E(DFj |Bj)〉| ≥ ε1/2 −Oj,ε(σ1/2)−O(ε).

Como as funcoes (1 − 1Ωj ), E(DFj |Bj) e E(f |Bj−1) sao todas Bj-mensuraveis, podemos trocar f por E(f |Bj), de modo que obtemos

|〈(1−1Ωj )(E(f |Bj)−E(f |Bj−1)),E(DFj |Bj)〉| ≥ ε1/2−Oj,ε(σ1/2)−O(ε).

Usando Cauchy-Schwarz e a estimativa (2.4.3) concluımos:

‖(1−1Ωj )(E(f |Bj)−E(f |Bj−1))‖L2 ≥ 2−2k−1+1ε1/2−Oj,ε(σ1/2)−O(ε).(2.4.8)

Esta estimativa moralmente implica, pelo teorema de Pitagoras, aestimativa de incremento de energia, o unico problema sendo a pre-senca dos conjuntos excepcionais Ωj−1, Ωj , os quais precisam de umpouco de cuidado para serem tratados, ja que nao temos boas cotasL2 para ν. Para resolver este pequeno contra-tempo, comecamos pornotar que (2.4.2) e (2.4.4) implicam

‖(1Ωj − 1Ωj−1)E(f |Bj−1)‖L2 = Oj,ε(σ1/2).

Logo, a desigualdade triangular e (2.4.7) mostram que a estimativade incremento de energia (2.4.6) segue de

‖(1− 1Ωj )E(f |Bj)‖2L2

≥ ‖(1− 1Ωj−1)E(f |Bj−1)‖2L2 + ε1/2 −Oj,ε(σ1/2)−O(ε).


i

i

i

i

i

i

i

i


Entretanto, o lado esquerdo acima pode ser expandido pela lei doscossenos como

‖(1− 1Ωj )E(f |Bj−1)‖2L2 + ‖(1− 1Ωj )(E(f |Bj)− E(f |Bj−1))‖2L2

+ 2〈(1− 1Ωj)E(f |Bj−1), (1− 1Ωj

)(E(f |Bj)− E(f |Bj−1))〉.

Portanto, por (2.4.8), vemos que e suficiente provar a seguinte relacaode quase-ortogonalidade:

〈(1− 1Ωj)E(f |Bj−1), (1− 1Ωj

)(E(f |Bj)− E(f |Bj−1))〉 = Oj,ε(σ1/2).

Como (1− 1Ωj )2 = (1− 1Ωj ), podemos reescrever a identidade acima

como

〈(1− 1Ωj )E(f |Bj−1),E(f |Bj)− E(f |Bj−1)〉 = Oj,ε(σ1/2).

Agora observemos que sendo a funcao (1 − 1Ωj−1)E(f |Bj−1) men-suravel com relacao a Bj−1, ela deve ser ortogonal a funcao E(f |Bj)−E(f |Bj−1) porque Bj−1 e uma sub-sigma-algebra de Bj por con-strucao. Em particular, podemos mais uma vez reescrever a expressaoacima como

〈(1Ωj − 1Ωj−1)E(f |Bj−1),E(f |Bj)− E(f |Bj−1)〉 = Oj,ε(σ1/2).

Usando novamente o fato de (1Ωj − 1Ωj−1)E(f |Bj−1) ser uma funcaoBj-mensuravel (donde segue que ela deve ser ortogonal a f−E(f |Bj)),vemos que a identidade acima equivale a

〈(1Ωj − 1Ωj−1)E(f |Bj−1), f − E(f |Bj−1)〉 = Oj,ε(σ1/2).

Porem esta igualdade certamente e verdadeira porque 0 ≤ f ≤ νe valem as estimativas (2.4.2), (2.4.4). Isto completa a prova daestimativa de incremento de energia (2.4.6) e, consequentemente, ademonstracao do teorema 2.4.2.

Resumo da subsecao “O argumento de incremento deenergia”:

Nesta subsecao usamos toda a maquinaria de sigma-algebras associ-adas a funcoes anti-uniformes para exibir um algoritmo de construcao


i

i

i

i

i

i

i

i


de conjuntos excepcionais pequenos e uma sigma-algebra (para umadensidade f majorada por uma medida pseudo-aleatoria) tais queque a funcao f possui um comportamento uniforme fora do conjuntoexcepcional. Em particular, isto nos mostra como decompor a funcaof em parte uniforme e parte nao-uniforme. Este foi o conteudo doteorema de Koopman-von Neumann generalizado 2.4.2. Mais ainda,o algoritmo levando a prova do teorema de Koopman-von Neumanngeneralizado era finito (i.e., ele parava em tempo finito) gracas a umargumento de incremento de energia a cada passo (de fato, como aenergia sempre crescia a cada passo e ela devia permanecer limitadadurante todo processo, isto levava rapidamente a conclusao desejada).

O ultimo passo sera aplicar a decomposicao fornecida pelo teo-rema 2.4.2 para finalizar a demonstracao do teorema de Green-Tao-Szemeredi.

2.4.5 Fim da prova do teorema deGreen-Tao-Szemeredi

Uma vez que ja formalizamos (e quantificamos) toda a maquinaria deuniformidade, anti-uniformidade e decomposicao em partes uniformee nao-uniforme, a tarefa de imitar o esquema proposto na secao 2.3para a prova do teorema de Roth visando demonstrar o teorema 2.2.1de Green-Tao-Szemeredi e simples:

Sejam f , ν e δ como enunciado do teorema 2.2.1. Tome ε << δe considere B a sigma-algebra do teorema 2.4.2 de Koopman-vonNeumann generalizado. Defina as funcoes:

• fU = (1− 1Ω)(f − E(f |B))

• fAU = (1− 1Ω)E(f |B).

Lembre que, por hipotese, 0 ≤ f ≤ ν (pontualmente) e E(f) ≥ δ.Portanto, o teorema 2.4.2 garante que

E(fAU ) = E((1− 1Ω)f) ≥ E(f)− E(ν1Ω) ≥ δ − oε(1).

Alem disso, temos que fAU ≤ 1 + oε(1), de modo que podemos usar


i

i

i

i

i

i

i

i


o teorema de Szemeredi9. Em particular:

E(fAU (n) . . . fAU (n + (k − 1)r)|n, r ∈ ZN ) ≥ c(k, δ)− oε(1).

Por outro lado, sabemos que ‖fU‖Uk−1 ≤ ε1/2k

. Logo, pelo teo-rema 2.4.1 de von Neumann generalizado, temos que:

E(f∗1(n) . . . f∗k(n + (k − 1)r)|n, r ∈ ZN ) = O(ε1/2k

)

onde ∗j = U ou AU , e ∗j = U para pelo menos um j.Assim obtemos que:

E(f(n) . . . f(n + (k − 1)r)|n, r ∈ ZN ) ≥ c(k, δ)−O(ε1/2k

)− oε(1).

Como ε e arbitrario, o teorema de Green-Tao-Szemeredi esta provado!

Observacao 2.4.6. O leitor mais atento percebeu a analogia evi-dente entre as estimativas acima e a estimativas da proposicao 2.3.1.De fato, como nao podia deixar de ser, em ambos os argumentos, nosseparamos o termo “bom” (no caso do Roth era Λ3(g, g, g) e no casodo Green-Tao era E(fAU (n) . . . fAU (n+(k−1)r)|n, r ∈ ZN )) o qual erelativamente grande (no caso do Roth era δ3 e no caso de Green-Taoe c(k, δ) − oε(1)) e ficamos por estimar os termos “ruins” (no casodo Roth eram Λ3(., ., .) onde alguma das entradas tinha a funcao b eno caso de Green-Tao era E(f∗1(n) . . . f∗k

(n + (k − 1)r)|n, r ∈ ZN )onde alguma das entradas tinha a funcao fU ). Para cumprir estatarefa, usamos Holder no caso do Roth e o teorema de von Neumanngeneralizado no caso de Green-Tao para reduzir o problema ao “fato”(nao-trivial) de que b no caso de Roth e fU no caso de Green-Taopodiam ser escolhidas uniformes. Logicamente, este fato e obtidodo enunciado do teorema de Koopman-von Neumann generalizado, oqual usa em sua prova o argumento de incremento de energia, con-forme havıamos dito bem no ınicio.

9Estamos fazendo uma pequena trapaca “inocula” aqui: como fAU nao e lim-itada por 1 exatamente e E(fAU ) nao e minorado por δ exatamente, o teorema deSzemeredi nao pode ser usado diretamente. Porem, isso e facilmente contornadose aplicarmos Szemeredi a uma funcao e igual a f modulo um termo da formaoε(1), o qual pode ser trivialmente controlado nesse caso.


i

i

i

i

i

i

i

i

Capıtulo 3

Construcao da MedidaPseudo-Aleatoria

3.1 A Medida Pseudo-Aleatoria

Pretendemos provar neste capıtulo o teorema 2.2.2, que recapitulamosa seguir (sob o nome de teorema 3.1.1):

Seja Λ a funcao de von Mangoldt modificada, dada por

Λ(n) =

φ(W )W

log(Wn + 1) se Wn + 1 e primo

0 caso contrario

(onde W = W (n) =∏

p≤w(n)p primo

p; aqui w(n) e uma funcao que tende

lentamente a +∞, mas observaremos no fim da prova que podemostomar w(n) uma constante grande).

Teorema 3.1.1. Se εk = 2−k/(k+4)! e N e um primo grande, entao

existe uma medida k-pseudo-aleatoria ν tal que ν(n) ≥ 2−k−5 k−1 Λ(n)para εkN ≤ n ≤ 2εkN .

Vamos a seguir construir a medida ν. Sua construcao e a provade que realmente e uma medida pseudo-aleatoria estao fortementeinspirados em resultados de Goldston e Yıldırım, principalmente [6].

90


i

i

i

i

i

i

i

i

[SEC. 3.1: A MEDIDA PSEUDO-ALEATORIA 91

A funcao Λ e uma modificacao da classica funcao de von Mangoldt

dada por Λ(n) =

log p se n = pk, p primo, k ≥ 10 caso contrario

. Essa modi-

ficacao e feita para superar a falta de aleatoriedade do conjunto dosprimos provocada por razoes locais, i.e., pelo seu comportamentomodulo primos pequenos.

Observamos agora que, se n = pα11 pα2

2 . . . pαk

k , p1 < p2 < · · · < pk

primos, temos

∑

d|nΛ(d) =

k∑

j=1

αj∑r=1

Λ(prj) =

k∑

j=1

αj∑r=1

log pj =k∑

j=1

αj log pj = log n,

e logo, pela formula da inversao de Mobius (ver apendice), Λ(n) =∑d|n

µ(d) log(n/d) =∑d|n

µ(d) log+(n/d), onde µ e a funcao de Mobius

e log+(x) = maxlog x, 0, para x > 0. Isto motiva a seguintedefinicao, de Goldston e Yıldırım:

Definicao 3.1.1 (Soma truncada sobre divisores de Goldston eYıldırım). Seja R > 0 um parametro (nas aplicacoes sera uma po-tencia pequena de N).

Definimos ΛR(n) =∑d|n

d≤R

µ(d) log(R/d) =∑d|n

µ(d) log+(R/d).

Podemos agora definir a medida ν:

Definicao 3.1.2. Seja R = Nk−12−k−4, e seja εk = 2−k

/(k + 4)!.

Definimos a funcao ν : ZN → R+ por

ν(n) =

φ(W )W

ΛR(Wn + 1)2

log Rse εkN ≤ n ≤ 2εkN

1, caso contrario

Provar que ν e de fato uma medida pseudo-aleatoria (ou mesmouma medida) dara um certo trabalho. Entretanto e bastante simplesmostrar que ν majora Λ como queremos:

Lema 3.1.1. ν(n) ≥ k−12−k−5 Λ(n) para εkN ≤ n ≤ 2εkN .


i

i

i

i

i

i

i

i

92 [CAP. 3: CONSTRUCAO DA MEDIDA PSEUDO-ALEATORIA

Demonstracao. Isso e trivial se Wn+1 nao e primo, pois nesse casoΛ(n) = 0. Por outro lado, se Wn+1 e primo, os divisores de Wn+1sao apenas 1 e Wn + 1 e, como W e grande, Wn + 1 > WεkN > R(assumindo, como sempre fazemos implicitamente, que N e sufi-cientemente grande), e logo ΛR(Wn + 1) =

∑d|Wn+1

d≤R

µ(d) log(R/d) =

µ(1) log R = log R, donde ν(n) =φ(W )

Wlog R. Como

Λ(n) =φ(W )

Wlog(Wn + 1), e ν(n) =

φ(W )W

log R =φ(W )

W· k−1 ·

2−k−4 log N , nossa afirmacao equivale a log N ≥ log(Wn + 1)2

para

εkN ≤ n ≤ 2εkN , mas isso segue de log N ≥ log(WN + 1)2

, o quecertamente e verdade se o crescimento de W e suficientemente lento(W ≤ N − 1 basta).

Precisaremos de dois resultados seguintes, que provaremos poste-riormente, os quais sao essencialmente devidos a Goldston e Yıldırım,e que serao usados para provar que ν e uma medida pseudo-aleatoria.

Proposicao 3.1.1. Sejam m e t inteiros positivos. Para cada 1 ≤i ≤ m, sejam ψi(x) =

t∑j=1

Lijxj + bi formas lineares com coeficientes

inteiros Lij tais que |Lij | ≤√

w(N)/2 para 1 ≤ i ≤ m e 1 ≤ j ≤ t.

Assumimos que as t-uplas (Lij)1≤j≤t nunca sao identicamente nulas,nem ha duas dessas t-uplas que sao multiplos racionais uma da outra.

Seja θi := Wψi + 1. Suponha que B e um produtot∏

i=1

Ii ⊂ Rt de t

intervalos Ii , cada um tendo comprimento pelo menos R10m. Entao(desde que o crescimento da funcao w(N) seja suficientemente lento)

E(ΛR(θ1(x))2 . . . ΛR(θm(x))2 | x ∈ B) = (1 + om,t(1))(

W log R

φ(W )

)m

.

Proposicao 3.1.2. Seja m ≥ 1 um inteiro, e seja B um intervalode comprimento pelo menos R10m. Suponha que h1, . . . , hm sejaminteiros distintos tais que |hi| ≤ m2 para 1 ≤ i ≤ m e seja ∆ :=


i

i

i

i

i

i

i

i


∏1≤i<j≤m

|hi−hj |. Entao (para N suficientemente grande dependendo

de m, e supondo que o crescimento de w(N) e suficientemente lento)

E(ΛR(W (x1 + h1) + 1)2 . . . ΛR(W (xm + hm) + 1)2 | x ∈ B) ≤

≤ (1 + om(1))(

W log R

φ(W )

)m ∏

p|∆p primo

(1 + Om(p−1/2)).

Em geral, no que segue, usaremos a letra p sempre para denotarprimos, como aqui.

Vamos inicialmente mostrar como concluir a prova do Teorema 3.1.1a partir das Proposicoes 3.1.1 e 3.1.2 para depois demonstrar asproposicoes. Comecaremos mostrando que ν e de fato uma medida.

Lema 3.1.2. A medida ν construıda na Definicao 3.1.2 satisfaz aestimativa E(ν) = 1 + o(1).

Demonstracao. Aplicamos a Proposicao 3.1.1 com m = t = 1,ψ1(x1) = x1 e B = [εkN, 2εkN ]. Comparando com a Definicao 3.1.2temos E(ν(x) | x ∈ [εkN, 2εkN ]) = 1 + o(1), pois a Proposicao 3.1.1

fornece E(ΛR(Wx + 1)2 | x ∈ B) = (1 + o(1)) · W log R

φ(W )· Por outro

lado, obviamente temos E(ν(x) | x ∈ ZN\[εkN, 2εkN ]) = 1, pelamesma Definicao 3.1.2.

Combinando os dois resultados concluımos a prova do lema.

Proposicao 3.1.3. A funcao ν satisfaz a (k · 2k−1, 3k − 4, k) –condicao de formas lineares.

Demonstracao. Sejam ψi(x) =t∑

j=1

Lij +bi formas lineares como na

Definicao 2.2.1, isto e, temos m ≤ k · 2k−1, t ≤ 3k − 4, e os Lij saonumeros racionais com numerador e denominador de valor absolutono maximo k de modo que nenhuma das t-uplas (Lij)1≤j≤t e nula oumultiplo racional de alguma outra. Queremos mostrar que

E(ν(ψ1(x)) . . . ν(ψm(x)) | x ∈ ZmN ) = 1 + o(1). (*)


i

i

i

i

i

i

i

i


Podemos supor que os Lij sao inteiros, compondo ψ1, ψ2, . . . , ψm

com a multiplicacao por k! dada por M : ZmM → Zm

N , M(x) =k!x(mod N), ∀x ∈ Zm

N . Como mdc(k!, N) = 1, para N grande, M euma bijecao, e o valor esperado nao muda. Com isso, a cota superiorpara os |Lij | muda para k · k! < (k + 1)!. Como w(N) tende a in-finito quando N cresce, podemos supor que (k + 1)! <

√w(N)

/2,

tomando N grande. Precisamos deste fato para poder aplicar aProposicao 3.1.1.

Como a definicao de ν tem duas partes, nao e possıvel aplicar di-retamente a Proposicao 3.1.1. Vamos entao dividir Zm

N em Qt blocosde lados quase iguais, onde Q = Q(N) e uma funcao de crescimentolento em N a ser escolhida posteriormente. Sejam entao os blocos

Bu1 u2...ut = x ∈ ZmN ; xj ∈ [LujN/Q,L(uj + 1)N/Q]), 1 ≤ j ≤ t

onde u1, u2, . . . , ut ∈ ZQ , e identificamos ZQ com 0, 1, 2, . . . , Q−1.Note que modulo um erro multiplicativo de 1 + o(1), podemos

escrever o lado esquerdo de (*) como

E(E(ν(ψ1(x)) . . . ν(ψm(x)) | x ∈ Bu1 u2...ut) | u1, . . . , ut ∈ ZQ).

Chamamos uma t-upla (u1, u2, . . . , ut) ∈ ZtQ boa se para 1 ≤ i ≤ m,

cada conjunto ψi(Bu1u2...ut) esta completamente contido no intervalo[εkN, 2εkN ] ou e completamente disjunto deste intervalo.Tomando a Proposicao 3.1.1 e a Definicao 3.1.2, observamos queE(ν(ψ1(x)) . . . ν(ψm(x)) | x ∈ Bu1u2...uk

) = 1 + om,t(1), sempre que(u1, u2, . . . , ut) for boa, pois podemos substituir cada fator ν(ψi(x))

porφ(W )

W log RΛ2

R(θi(x)) ou por 1, e, se o crescimento de Q e suficien-

temente lento, N/Q > R10m, pela definicao de R e pela limitacao dem.

Se (u1, u2, . . . , ut) nao e boa, podemos majorar ν por 1+φ(W )

W log RΛ2

R(θi(x)), multiplicar, expandir e aplicar a Proposicao 3.1.1

a cada termo para obter uma cota do tipo

E(ν(ψ1(x)) . . . ν(ψm(x)) | x ∈ Bu1u2...uk) = Om,t(1).

Veremos agora que a proporcao de t-uplas (u1, u2, . . . , ut) ∈ ZtQ

que nao sao boas e no maximo Om,t(1/Q), e logo o lado direito de (*)


i

i

i

i

i

i

i

i


e 1+om,t(1)+Om,t(1/Q) = 1+om,t(1), o que conclui a demonstracao.Para isso, suponha que (u1, u2, . . . , ut) nao e boa. Entao existem i ≤m e x, x′ ∈ Bu1u2...ut

tais que ψi(x) pertence ao intervalo [εkN, 2εkN ]mas ψi(x′) nao. Pela definicao de Bu1u2...ut

(e pela limitacao dos Lij),

temos ψi(x), ψi(x′) =t∑

j=1

LijbNuj/Qc+ bi +Om,t(N/Q). Portanto,

para algum a ∈ 1, 2, a εkN =t∑

j=1

LijbNuj/Qc + bi + Om,t(N/Q).

Dividindo por N/Q, obtemost∑

j=1

Lijuj = a εkQ + bi Q/N +Om,t(1)

(mod Q). Como (Lij)1≤j≤t e nao-nulo, o numero de t-uplas(u1, u2, . . . , ut) que safisfazem esta equacao e no maximo Om,t(Qt−1).Fazendo a e i variarem, concluımos que a proporcao de t-uplas quenao sao boas e no maximo Om,t(1/Q), como querıamos.

Veremos a seguir como usar a Proposicao 3.1.2 para mostrar queν satisfaz a condicao de correlacoes. Para isso, vamos incialmenteestimar o fator

∏p|∆

p primo

(1 +Om(p−1/2)) que aparece na proposicao:

Lema 3.1.3. Seja m ≥ 1 um parametro. Existe uma funcao peso τ =τm : Z→ R+ tal que τ(n) ≥ 1, ∀n 6= 0 e, para cada h1, h2, . . . , hm ∈[εkN, 2εkN ] distintos, temos

∏

p|∆p primo

(1 +Om(p−1/2)) ≤∑

1≤i<j≤m

τ(hi − hj),

onde ∆ foi definido na Proposicao 3.1.2, de modo que E(τ q(n) | 0 <|n| ≤ N) = Om,q(1), para 0 < q < ∞.

Demonstracao. Note que

∏

p|∆p primo

(1 +Om(p−1/2)) ≤∏

1≤i<j≤m

∏

p|hi−hj

p primo

(1 + p−1/2)

Om(1)

.


i

i

i

i

i

i

i

i


Podemos entao, usando a desigualdade entre as medias aritmeticae geometrica (e absorvendo as constantes no fator e no expoenteOm(1)), tomar τm(n) = Om(1)

∏p|n

p primo

(1+Om(p−1/2))Om(1) para cada

n 6= 0 (o valor de τ em 0 e irrelevante para o lema, pois estamostomando os hj distintos).

Para concluir a prova do lema, basta mostrar que

E( ∏

p|np primo

(1+p1/2)On(1) | 0 < |n| ≤ N

)= Om,q(1), para 0 < q < ∞.

Como (1 + p−1/2)Om(q) ≤ 1 + p−1/4 para todos os primos p, comexcecao de no maximo Om,q(1) primos, temos

E( ∏

p|np primo

(1 + p−1/2)Om(q) | 0 < |n| ≤ N

)

= Om,q(1) · E( ∏

p|np primo

(1 + p−1/4) | 0 < n ≤ N

).

Por outro lado,∏p|n

p primo

(1 + p−1/4) ≤ ∑d|n

d−1/4, e logo

E( ∏

p|np primo

(1 + p−1/2)Om(q) | 0 < |n| ≤ N

)

≤ Om,q(1) · 1N

∑

1≤n≤N

∑

d|nd−1/4

≤ Om,q(1) · 1N

N∑

d=1

N

d· d−1/4 = Om,q(1),

pois∞∑

d=1

d−5/4 < ∞.

Podemos agora provar a condicao de correlacoes.


i

i

i

i

i

i

i

i


Proposicao 3.1.4. A medida ν satisfaz a 2k−1-condicao de cor-relacoes.

Demonstracao. Queremos mostrar que, para 1 ≤ m ≤ 2k−1 eh1, . . . , hm ∈ ZN temos E(ν(x + h1) . . . ν(x + hm) | x ∈ ZN ) ≤∑1≤i<j≤m

τ(hi − hj), onde a funcao peso τ = τm e limitada em Lq

para todo q.Fixemos m, h1, . . . , hm . Vamos tomar a funcao peso construıda

no Lema 3.1.3 (identificando ZN com os inteiros entre −N/2 e N/2)multiplicada por um fator constante Om(1) conveniente e definirτ(0) = exp(Cm log N/ log log N), para alguma constante absolutagrande C. Pelo lema anterior concluımos que E(τ q) = Om,q(1) paratodo q, pois τ(0) so contribui com om,q(1) para o valor de E(τ q).Trataremos inicialmente do caso em que dois dos hi sao iguais. Nesse

caso, podemos usar a estimativa grosseira ||ν||L∞ ≤ exp(

2 log N

log log N

),

que segue da definicao de ν (na verdade obtemos facilmente da definicaoque |ν(n)| ≤ log N · d(n)2, onde d(n) e o numero de divisores de n;

temos, por outro lado, d(n) = O(

exp(

3 log N

4 log log N

))– ver apendice,

donde segue nosssa estimativa), e a afirmacao nesse caso segue da es-colha de τ(0).

Suponhamos agora que os hi sao todos distintos. Seja

g(n) :=φ(W )

W· Λ2

R(Wn + 1)log R

· 1[εkN,2εkN ](n).

Pela construcao de ν, temos

E(ν(x + h1) . . . ν(x + hm) | x ∈ ZN )

≤ E((1 + g(x + h1)) . . . (1 + g(x + hm)) | x ∈ ZN ).

O lado direito acima pode ser reescrito como

∑

A⊂1,...,mE

( ∏

i∈A

g(x + hi) | x ∈ ZN

).


i

i

i

i

i

i

i

i


Note que para i, j ∈ A podemos supor que |hi − hj | ≤ εkN(pois, caso contrario, a esperanca correspondente se anula). PelaProposicao 3.1.2 e pelo Lema 3.1.3 obtemos portanto

E( ∏

i∈A

g(x + hi) | x ∈ ZN

)≤ (1 +Om(1))

∑

1≤i<j≤m

τm(hi − hj),

e somando sobre todos os A, obtemos o resultado, apos multiplicarτm por uma constante adequada.

Os Lemas 3.1.1 e 3.1.2, e as Proposicoes 3.1.3 e 3.1.4 concluem aprova de que ν e uma medida pseudo-aleatoria e do Teorema 3.1.1.

Vamos agora nos dedicar a provar as Proposicoes 3.1.1 e 3.1.2.

3.2 Condicao de formas lineares para ΛR

Vamos provar a Proposicao 3.1.1. Lembramos que temos, para cada

i com 1 ≤ i ≤ m, uma forma linear ψi(x) =t∑

j=1

Lij xj + bi em t

variaveis x1, . . . , xt . Os coeficientes Lij satisfazem |Lij | ≤√

w(N)/2,onde w(N) e uma funcao com crescimento lento em N . Supomosque nenhum t-upla (Lij)1≤j≤t e nula ou multiplo de alguma outra.

Definimos θi = Wψi + 1. Seja B =t∏

j=1

Ij um produto de intervalos

Ij , cada um com comprimento maior ou igual a R10m. Queremosprovar a estimativa

E(ΛR(θ1(x))2 . . . ΛR(θn(x))2 | x ∈ B) = (1 + o(1))(

W log R

φ(W )

)m

.

A primeira etapa da prova sera eliminar o papel do bloco B. Pode-mos usar a definicao de ΛR para expandir o lado esquerdo como

E( m∏

i=1

∑

di,d′i≤R

di,d′i|θi(x)

µ(di)µ(d′i) logR

dilog

R

d′i| x ∈ B

),


i

i

i

i

i

i

i

i

[SEC. 3.2: CONDICAO DE FORMAS LINEARES PARA ΛR 99

o que pode ser reescrito como

∑

d1,...,dm,d′1,...,d′m≤R

( m∏

i=1


dilog

R

d′i

)×

× E( m∏

i=1

1di,d′i|θi(x) | x ∈ B

).

(3.1)

Devido a presenca da funcao µ de Mobius podemos supor que os di,d′i sao livres de quadrados. Seja D = mmc(d1, . . . , dm, d′1, . . . , d

′m)

o mınimo multiplo comum dos di e dos d′i ; temos D ≤ R2m. Note

que a expressaom∏

i=1

1di,d′i|θi(x) e periodica com perıodo D em cada

coordenada de x, e portanto pode ser definido com domınio ZtD .

Como B e um produto de intervalos de comprimento maior ou iguala R10m, temos

E( m∏

i=1

1di,d′i|θi(x) | x ∈ B

)

= E( m∏

i=1

1di,d′i|θi(x) | x ∈ ZtD

)+Om,t(R−8m).

A contribuicao dos termos de erro Om,t(R−8m) para (3.1) podeser majorada grosseiramente por R2m(log R)2m · Om,t(R−8m) =Om,t(R−6m(log R)2m). Basta mostrar, portanto, que

∑

d1,...,dm,d′1,...,d′m≤R

( m∏

i=1


dilog

R

d′i

)×

× E( m∏

i=1


)

= (1 + o(1))(

W log R

φ(W )

)m

. (3.2)

Para provar isso, escreveremos o lado esquerdo como uma integralde linha de um produto de Euler, que por sua vez pode ser escritoem termos da funcao ζ de Riemann e outros fatores simples.


i

i

i

i

i

i

i

i


Comecamos usando o teorema chines dos restos (e o fato dos di,d′i serem livres de quadrados) para reescrever

E( m∏

i=1


)

=∏

p|Dp primo

E( ∏

i,p|did′i

1θi(x)≡0(mod p) | x ∈ Ztp

)

(o lado esquerdo e a probabilidade de que θi(x) seja multiplo de di ede d′i , para todo i ≤ m, o que equivale a θi ser multiplo de p sempreque p for um primo que divide di ou d′i , pois os di, d′i sao livresde quadrados). Note que a restricao p|D no lado direito pode serremovida, pois, se p - D, p nunca dividira did

′i , donde o multiplicando

nesse caso e 1. Assim, escrevendo Xd1,...,dm(p) := 1 ≤ i ≤ m; p | die

ωX(p) := E( ∏

i∈X

1θi(x)≡0(mod p) | x ∈ Ztp

),

para cada X ⊂ 1, 2, . . . , m, temos

E( m∏

i=1


)=

∏

p primo

ωXd1,...,dm(p)∪Xd′1,...,d′m(p)(p).

Podemos entao escrever o lado esquerdo de (3.2) como

∑

d1,...,dm,d′1,...,d′m∈Z+

( m∏

i=1

µ(di)µ(di) log+

(E

d′i

)log+

(E

d′i

))×

×∏

p primo

ωXd1,...,dm(p)∪Xd′1,...,d′m(p)(p).

A seguir, vamos expressar os logaritmos em termos de funcoes multi-plicativas dos di, d′i por meio de integrais de linha. Para isso, usare-mos o seguinte resultado:

Lema 3.2.1. Dado ε > 0, seja Γ(t) a reta vertical parametrizada porΓ(t) = ε + it, −∞ < t < +∞. Temos entao, para cada x > 0 real,1

2πi

∫

Γ

xz

z2dz = log+(x).


i

i

i

i

i

i

i

i


Demonstracao. Dado M > ε, seja Γ(M) a restricao de Γ ao inter-valo

[ − √M2 − ε2,√

M2 − ε2]. Se 0 < x < 1 considere o caminho

fechado Γ(M) formado por ΓM seguido do caminho

γ(M) : [− cos−1(ε/M), cos−1(ε/M)] → C, γ(M)(t) = Me−it.

Como a funcao xz/z2 nao tem singularidades no interior de Γ(M),

temos∫eΓ(M)

xz

z2dz = 0. Por outro lado, como 0 < x < 1,

∣∣∫

eγ(M)

xz

z2dz

∣∣ =

O( 1M

), donde, nesse caso,

12πi

∫

Γ

xz

z2dz = lim

M→∞1

2πi

∫

Γ(M)

xz

z2dz

= − limM→∞

12πi

∫

eγ(M)

xz

z2dz = 0 = log+(x).

Se x ≥ 1, considere o caminho fechado Γ(M) formado por Γ(M)

seguido do caminho γ(M) : [cos−1(ε/M), 2π−cos−1(ε/M)] → C, γ(M)(t) =Meit. A unica singularidade de xz/z2 no interior de Γ(M) e z =

0, e xz/z2 = ez log x/z2 =

1 + z log x + z2 log2 x/2 + . . .

z2= z−2 +

z−1 log x +log2 x

2+ . . . tem resıduo log x em z = 0, donde

12πi

∫

bΓ(M)

xz/z2 dz = log x.

Como x ≥ 1 e Re z ≤ ε em γ(M),∣∣∣∣

∫

γ(M)

xz/z2 dz

∣∣∣∣ = O( 1M

), donde,

nesse caso,

12πi

∫

Γ

xz

z2dz = lim

M→∞1

2πi

∫

Γ(M)

xz

z2dz =

= log x− limM→∞

∫

γ(M)

xz

z2dz = log x = log+(x).


i

i

i

i

i

i

i

i


A seguir, Γ1(t) denotara a reta vertical Γ(t) correspondente a

ε =1

log R, isto e, Γ1(t) :=

1log R

+ it, −∞ < t < ∞. Temos, pelo

lema anterior,1

2πi

∫

Γ1

xz

z2dz = log+(x).

Note que Rz e limitado em Γ1 :∣∣RΓ1(t)

∣∣ = R1/ log R = e, ∀ t ∈ R.Podemos, usando a identidade acima, reescrever o lado esquerdo de(3.2) como

(2πi)−2m

∫

Γ1

. . .

∫

Γ1

F (z, z′)m∏

j=1

Rzj+z′j

z2j z′2j

dzj dz′j ,

onde ha 2m integrais de linha nas variaveis z1, . . . , zm, z′1, . . . , z′m em

Γ1 , z := (z1, . . . , zm), z′ := (z′1, . . . , z′m) e

F (z, z′) :=∑

d1,...,dm,d′1,...,dm′∈Z+

( m∏

j=1

µ(dj)µ(d′j)

dzj

j d′z′jj

)×

×∏

p primo

ωXd1,...,dm (p)∪Xd′1,...,d′m (p)(p).(3.3)

Observe que o somando em (3.3) e uma funcao multiplicativa dos dj ,d′j , e portanto temos (pelo menos formalmente) uma representacaoem produto de Euler F (z, z′) =

∏p primo

Ep(z, z′), onde

Ep(z, z′) :=∑

X,X′⊂1,...,m

(−1)|X|+|X′| ωX∪X′(p)

p

Pj∈X

zj+P

j∈X′z′j

·

Da definicao de ωX(p) temos ωφ(p) = 1 e ωX(p) ≤ 1, donde Ep(z, z′) =1+Oσ(1/pσ) quando Re(zj), Re(z′j) > σ. Portanto o produto de Eu-ler acima e absolutamente convergente (e vale a igualdade em (3.3))no domınio Re(zj), Re(z′j) ≥ 1, pelo menos.

Vamos agora explorar a hipotese sobre as partes lineares deψ1, . . . , ψm serem nao-nulas e nao serem multiplos racionais de nen-huma outra.


i

i

i

i

i

i

i

i


Lema 3.2.2 (Estimativa do fator local). Se p ≤ w(N), entao ωX(p) =0 para todo conjunto nao-vazio X. Em particular, Ep = 1 se p ≤w(N). Se p > w(N), entao ωX(p) = p−1 quando |X| = 1 e ωX(p) ≤p−2 quando |X| ≥ 2.

Demonstracao. A primeira afirmacao e imediata, pois as funcoesθj : Zt

p → Zp sao identicamente 1 quando p ≤ w(N). Para a se-gunda afirmacao, observe que se p > w(N) e X = j, cada el-emento de Zp e imagem por θj de pt−1 elementos de Zt

p , dondeωX(p) = E(1θj(x)≡0(mod p) | x ∈ Zt

p) = 1/p.Suponhamos agora que p > w(N) e |X| = 2. Vamos ver que

nenhuma das formas lineares puras W (ψi − bi) e multiplo de nen-huma outra modulo p. De fato, se fosse o caso, terıamos Lij ≡λLi′j(mod p) para um certo λ e todo j ≤ t, mas, se a/q e a′/q′ saodois racionais na forma simplificada com |a|, |a′|, q, q′ <

√w(N)

/2 e

a/q = a′/q′(mod p) entao a = a′, q = q′. Portanto, todos os racionaisLij/Li′j , 1 ≤ j ≤ t sao iguais, e logo as formas lineares puras ψi − bi

e ψi′−bi′ sao multiplos racionais uma da outra, absurdo. Portanto, oconjunto dos x ∈ (Z/pZ)t para os quais θi(x) ≡ 0(mod p) para todoi ∈ X esta contido na intersecao de dois subespacos afins de (Z/pZ)t,e portanto tem no maximo pt−2 elementos, donde ωX(p) ≤ p−2.

O lema acima implica, comparando com a definicao de Ep(z, z′)que

Ep(z, z′) = 1− 1p>w(N)

m∑

j=1

(p−1−zj + p−1−z′j − p−1−zj−z′j

)+ (3.4)

+ 1p>w(N)

∑

X,X′⊂1,...,m|X∪X′|≥2

O(1/p2)

p

Pj∈X

zj+P

j∈X′z′j

,

onde o numerador O(1/p2) nao depende de z, z′.Vamos agora fatorar Ep como Ep = E

(1)p E

(2)p E

(3)p , onde

E(1)p (z, z′) :=

Ep(z, z′)mQ

j=1

1− 1p>w(N)p

−1−zj

1− 1p>w(N)p−1−z′j

1− 1p>w(N)p

−1−zj−z′j−1


i

i

i

i

i

i

i

i


E(2)p (z, z′) :=

mYj=1

1− 1p≤w(N)p

−1−zj−1

1− 1p≤w(N)p−1−z′j

−1×

× 1− 1p≤w(N)p−1−zj−z′j

E(3)p (z, z′) :=

mYj=1

1− p−1−zj

1− p−1−z′j

1− p−1−zj−z′j

−1.

Definindo Gj :=∏

p primo

E(j)p para j = 1, 2, 3 temos F = G1G2G3

(pelo menos para Re(zj), Re(z′j) suficientemente grandes). Em ter-

mos da funcao ζ de Riemann, ζ(s) =∏

p primo

(1 − 1/ps

)−1, temos

G3(z, z′) =m∏

j=1

ζ(1 + zj + z′j)ζ(1 + zj)ζ(1 + z′j)

, e em particular G3 e holomorfa

em (Re z > 0)2m, e se estende de forma meromofa a uma vizinhancado fecho deste domınio (na verdade a todo o C2m).

Para os outros fatores, faremos estimativas que permitem con-tinua-los analiticamente um pouco a esquerda dos eixos imaginarios.

Definicao 3.2.1. Para cada σ > 0, seja Dmσ ⊂ C2m o domınio

Dmσ =

zj , z

′j | −σ < Re(zj),Re(z′j) < 100, 1 ≤ j ≤ m

.

Se G = G(z, z′) e uma funcao analıtica de 2m variaveis complexasem Dm

σ , definimos a norma de G em Ck(Dmσ ) para cada k ∈ N como

||G||Ck(Dmσ ) = sup

a1+···+am+a′1+···+a′m≤k

∥∥( ∂

∂z1

)a1. . .

( ∂

∂zm

)am( ∂

∂z′1

)a′1 . . .( ∂

∂z′m

)a′m G∥∥

L∞(Dmσ )

onde a1, . . . , am, a′1, . . . , a′m percorrem os inteiros nao negativos com

soma menor ou igual a k.


i

i

i

i

i

i

i

i


Lema 3.2.3. Os produtos de Euler∏

p primo

E(j)p para j = 1, 2 sao ab-

solutamente convergentes no domınio Dm1/30m . Em particular, G1,

G2 podem ser continuadas analiticamente a esse domınio. Alemdisso, temos as estimativas

||G1||Cm(Dm1/30m

) ≤ Om(1),

||G2||Cm(Dm1/30m

) ≤ Om,w(N)(1),

G1(0, 0) = 1 + om(1) e G2(0, 0) = (W/φ(W ))m.

Nota: Os resultados do Capıtulo 1 sobre a funcao ζ mostram queG3 se estende meromorficamente a Dm

1/2 ⊃ Dm1/30m . A escolha de

σ = 1/30m no lema acima nao e a melhor possıvel, mas qualquerσ positivo dependendo so de m seria suficiente. A dependencia dotermo Om,w(N)(1) em w(N) nao e importante, mas e possıvel obtersem muita dificuldade cotas do tipo w(N)Om(w(N)).

Demonstracao. Vamos considerar inicialmente o caso j = 1. De(3.4) e da expansao em serie de Taylor das funcoes envolvidas, temosa estimativa grosseira E

(1)p (z, z′) = 1+Om

(p−2+2/30m

)em Dm

1/30m , oque da a convergencia do produto e a estimativa de G1 em Cm(Dm

1/30m).A estimativa para G1(0, 0) tambem segue daı, pois os fatores do pro-duto sao identicamente iguais a 1 para p ≤ w(N).

A estimativa para G2 e facil pois G2 e um produto finito de nomaximo w(N) termos, e a formula para G2(0, 0) segue diretamente

de∏

p primop≤w(N)

(p− 1p

)=

φ(W )W

·

Para estimar o lado esquerdo de (3.2), que escrevemos sob formade integral, precisamos do seguinte lema devido a Goldston e Yıldırım,que provaremos posteriormente, o qual estima integrais de contornocomo as que aparecem nesse contexto:

Lema 3.2.4. Seja R um real positivo e seja G = G(z, z′) uma funcaoanalıtica em 2m variaveis complexas no domınio Dm

σ para algum σ >


i

i

i

i

i

i

i

i


0. Suponha que

||G||Cm(Dmσ ) = exp

(Om,σ((log R)1/15)).

Entao

1(2πi)2m

∫

Γ1

. . .

∫

Γ1

G(z, z′)m∏

j=1

ζ(1 + zj + z′j)ζ(1 + zj)ζ(1 + z′j)

Rzj+z′j

z2j z′2j

dzj dz′j

= G(0, . . . , 0)(log R)m +m∑

j=1

Om,σ

(||G||Cj(Dmσ )(log R)m−j

)

+Om,σ

(e−δ(log R)1/10)

,

para um certo δ = δ(m) > 0.

Vamos aplicar este lema com G = G1G2 e σ = 1/30m. PeloLema 3.2.3 e pela regra de Leibnitz, obtemos as estimativas

||G||Cj(Dm1/30m

) ≤ Oj,m,w(N)(1), para todo j ≤ m.

Em particular, obtemos ||G||Cm(Dmσ ) = exp

(Om,σ(log R)1/15))

desdeque o crescimento de w(N) seja suficientemente lento. O Lema 3.2.3tambem nos da G(0, 0) = (1 + om(1))(W/φ(W ))m. Concluımosque, se o crescimento de w(N) e suficientemente lento, nossa ex-pressao integral para o lado esquerdo de (3.2) e, pelo Lema 3.2.4, (1+om(1)

(W log R/φ(W )

)m, o que conclui a prova da Proposicao 3.1.1.

3.3 Correlacoes de ordem superior de ΛR

Vamos agora adaptar os argumentos acima para provar a Proposicao3.1.2. Temos agora apenas uma variavel, mas nao podemos usar oLema 3.2.2, pois as formas lineares so podem diferir pelos termos con-stantes nesse caso. Contudo, os argumentos anteriores a este lemacontinuam funcionando. Em particular, podemos escrever o lado es-querdo da desigualdade do enunciado da Proposicao 3.1.2 como

(2πi)−2m

∫

Γ1

. . .

∫

Γ1

F (z, z′)m∏

j=1

Rzj+z′j

z2j z′2j

dzj dz′j ,


i

i

i

i

i

i

i

i

[SEC. 3.3: CORRELACOES DE ORDEM SUPERIOR DE ΛR 107

onde F e definido como em (3.3), com a diferenca de que agora ωX(p)deve ser definido como

ωX(p) := E(∏

i∈X

1W (x+hi)+1≡0(mod p) | x ∈ Zp

).

Temos ainda ωφ(p) = 1 para todo p. O analogo do Lema 3.2.2 e oseguinte:

Lema 3.3.1. Se p ≤ w(N), entao ωX(p) = 0 para todo X 6= ∅.Em particular, Ep = 1 quando p ≤ w(N). Se p > w(N), entaoωX(p) = p−1 quando |X| = 1 e ωX(p) ≤ p−1 quando |X| ≥ 2. Alemdisso, quando |X| ≥ 2, temos ωX(p) = 0 sempre que p nao divide∆ :=

∏1≤i<j≤s

|hi − hj |.

Demonstracao. Quando p ≤ w(N), temos W (x+hi)+1 ≡ 1 (modp), donde segue nossa afirmacao. Quando p > w(N), e |X| ≥ 1,ωX(p) = 1/p quando todas as classes de congruencia hi(mod p), i ∈X sao iguais, e ωX(p) = 0 caso contrario, e daı segue o resultado.

Aplicando o lema acima, obtemos o seguinte analogo de (3.4):

Ep(z, z′) = 1− 1p>w(N)

m∑

j=1

(p−1−zj + p−1−z′j − p−1−zj−z′j

)

+ 1p>w(N),p|∆ λp(z, z′)

onde λp(z, z′) e uma expressao da forma

λp(z, z′) =∑

X,X′⊂1,...,m|X∪X′|≥2

O(1/p)

p

Pj∈X

zj+P

j∈X′z′j

na qual a quantidade O(1/p) nao depende de z, z′. Podemos entao


i

i

i

i

i

i

i

i


fatorar Ep = E(0)p E

(1)p E

(2)p E

(3)p , onde

E(0)p = 1 + 1p>w(N),p|∆ · λp(z, z′)

E(1)p =

Ep

E(0)p

mQj=1

(1− 1p>w(N) p−1−zj )(1− 1p>w(N)p−1−z′j )(1− 1p>w(N) p

−1−zj−z′j )−1

E(2)p =

mYj=1

(1− 1p≤w(N) p−1−zj )−1(1− 1p≤w(N)p−1−z′j )−1(1− 1p≤W (N) p−1−zj−z′j )

E(3)p =

mYj=1

(1− p−1−zj )(1− p−1−z′j )(1− p−1−zj−z′j )−1.

Seja Gj =∏

p primo

E(j)p . Entao, como antes, F = G0G1G2G3 , e G3

e dado porm∏

j=1

ζ(1 + zj + z′j)ζ(1 + zj)ζ(1 + z′j)

, como antes. Para G0, G1 e G2,

temos o seguinte analogo ao Lema 3.2.3:

Lema 3.3.2. Seja 0 < σ ≤ 1/30m. Os produtos de Euler∏

p primo

E(`)p

para ` = 0, 1, 2 sao absolutamente convergentes no domınio Dmσ . Em

particular, G0, G1 e G2 podem ser continuados analiticamente a essedomınio. Alem disso, temos as estimativas seguintes:

||G0||Cr(Dmσ ) ≤ Om(1) · ( log R

log log R

)r ∏

p|∆p primo

(1 +Om(p2mσ−1)

)

||G0||Cm(Dmσ ) ≤ exp

(Om((log R)1/15))

||G1||Cm(Dmσ ) ≤ Om(1)

||G2||Cm(Dmσ ) ≤ Om,w(N) (1)

G0(0, 0) =∏

p|∆p primo

(1 +Om(p−1/2)

)

G1(0, 0) = 1 +Om(1)G2(0, 0) = (W/φ(W ))m.


i

i

i

i

i

i

i

i

[SEC. 3.3: CORRELACOES DE ORDEM SUPERIOR DE ΛR 109

Demonstracao. As estimativas para G1 e G2 podem ser provadasexatamente como no Lema 3.2.3 (os fatores adicionais λp(z, z′) queaparecem no numerador e no denominador de E

(1)p se cancelam em

primeira ordem, e portanto nao criam dificuldades adicionais); vamosportanto nos dedicar as estimativas sobre G0 .

Temos G0 =∏p|∆

p primo

E(0)p . O numero de primos que dividem ∆ e

no maximo O(log ∆/ log log ∆) (ver apendice). Usando a estimativagrosseira

∆ =∏

1≤i<j≤m

|hi − hj | ≤ Nm2 ≤ ROm(1),

vemos que o numero de fatores no produto de Euler eO(log R/ log log R). Diferenciando r vezes para 0 ≤ r ≤ m por meioda regra de Leibnitz, obtemos uma soma de Om((log R/ log log R)r)termos, cada um dos quais consistindo de Om(log R/ log log R) fa-tores, os quais sao iguais a alguma derivada de 1+λp(z, z′), de algumaordem entre 0 e r. Em Dm

σ , cada fator e limitado por 1+Om(p2mσ−1)(na verdade, os termos que contem um numero positivo de derivadasserao muito menores, pois o termo constante 1 e eliminado). Isso nosda a primeira estimativa sobre ||G0||Cr(Dm

σ ).Para provar a estimativa seguinte, basta mostrar que

∏

p|∆p primo

(1 +Om(p2mσ−1)

) ≤ exp(Om((log R)1/15)

).

Tomando logaritmos e usando a hipotese σ ≤ 1/30m, e suficienteprovar que

∑p|∆

p−14/15 ≤ O((log ∆)1/15), pois ∆ ≤ ROm(1). Para

isso, como ∆ tem no maximo O(log ∆/ log log ∆) fatores primos (verapendice), temos

∑

p|∆p−14/15 ≤

∑

1≤n≤O(log ∆/ log log ∆)

n−14/15 = O((log ∆)1/15),

como querıamos.A estimativa para G0(0, 0) segue da estimativa grosseira

E(0)p (z, z′) = 1 +Om(p−1/2).


i

i

i

i

i

i

i

i


Aplicamos agora o Lema 3.2.4 com σ := 1/30m e G := G0G1G2 .Ainda pela regra de Leibnitz, temos

||G||Cm(Dmσ ) = exp

(Om,σ((log R)1/15)),

donde, pelo lema,

12πi

∫

Γ1

. . .

∫

Γ1

F (z, z′)m∏

j=1

Rzj+z′j

z2j z′2j

dzj dz′j ≤

≤ Om(1)( W

φ(W ))m(log R)m

∏

p|∆

(1 +Om(p−1/2))+

+Om,w(N)

( (log R)m

log log R

) ∏

p|∆

(1 +Om(p−1/2)

)+Om

(e−δ(log R)1/10)

,

e, escolhendo w(N) que cresca de modo suficientemente lento emrelacao a N (e logo tambem em relacao a R), o primeiro termo dom-inara os demais, o que conclui a prova da Proposicao 3.1.2.

Nota: De fato o argumento acima pode ser usado para dar uma esti-mativa assintotica para o lado esquerdo da desigualdade no enunciadoda Proposicao 3.1.2, em vez de fornecer apenas uma cota superior.Para isso, basta estimar G0(0, 0) mais cuidadosamente. Isto foi feitoem detalhes por Goldston e Yıldırım no caso W = 1.

3.4 Prova do Lema 3.2.4

Provaremos agora o Lema 3.2.4. No que segue, R ≥ 2, m ≥ 1 eσ > 0 serao fixados. Usaremos δ > 0 para denotar diversas constantespequenas, que podem variar de acordo com as retas verticais ondefaremos integracao.

Vamos recordar a regiao livre de zeros para a funcao ζ de Riemannobtida no (apendice ao) Capıtulo 1:

Z :=z ∈ C | 10 ≥ Re z ≥ 1− β

(log(|Im z|+ 2))9,


i

i

i

i

i

i

i

i

[SEC. 3.4: PROVA DO LEMA 3.2.4 111

para um certo β ∈ (0, 1) pequeno e uma regiao tal que ζ e nao-nulae meromorfa em Z com um unico polo simples em 1. Alem disso,temos as seguintes estimativas, validas para todo s ∈ Z:

ζ(s)− 1s− 1

= O(|Im s|+ 2);1

ζ(s)= O((|Im s|+ 2)7).

Temos ainda que, se Re s ≥ 3/4, entao ζ(s) − 1s−1 = O((|Im s| +

2)1/4).Podemos escolher β pequeno de modo que Z esta contido na regiao

onde max1 − σ, 7/8 < Re s < 101. As constantes envolvidas nanotacao O( ) podem depender de β e σ, sem necessidade de mencaoexplıcita.

Alem do caminho Γ1 dado por Γ1(t) = 1/ log R+it, −∞ < t < ∞,definiremos dois outros caminhos:

Γ0(t) :=β

(log(|t|+ 2))9+ it, −∞ < t < ∞

e Γ2(t) := 1 + it, −∞ < t < ∞.

Assim, Γ0 e a fronteira esquerda de Z − 1, situada a esquerdada origem, enquanto Γ1 e Γ2 estao situadas a direita da origem. Autilidade de Γ2 vem do fato de que ζ(1 + z + z′) nao tem nenhumpolo quando z ∈ Z − 1 e z′ ∈ Γ2 (mas nao estimaremos integrais emΓ2).

O proximo lema fornece estimativas para as integrais seguintes:

Lema 3.4.1. Seja B uma constante fixada. Temos as seguintes es-timativas:

∫

Γ0

∣∣Rz dz

z3/2

∣∣ ≤ O(e−δ(log R)1/10)

∫

Γ1

(log(|z|+ 2))B∣∣Rz dz

z2

∣∣ ≤ OB(log R)

onde δ = δ(β) > 0 e uma constante independente de R.

Demonstracao. Como |Γ′0(t)| = O(1) e |z| ≥ c(|t|+ β) em Γ0 para


i

i

i

i

i

i

i

i


uma certa constante c > 0, temos, para cada T ≥ 2,

∫

Γ0

∣∣Rzdz

z3/2

∣∣ ≤ O(1)∫ ∞

0

R−β/(log(|t|+2))9

(|t|+ β)3/2dt ≤

≤ O(1)(∫ T

0

R−β/(log(|t|+2))9 dt +∫ ∞

T

dt

t3/2

) ≤

≤ O(1)(T exp(−β log R/2(log T )9

)+ T−1/2

).

Escolhendo T = exp((β log R/3)1/10), os dois termos da soma saoiguais, e da ordem deO(1) exp(− 1

2 (β log R/3)1/10) = O(e−δ(log R)1/10)

,o que demonstra a primeira estimativa do lema.

Para a segunda estimativa, basta usar o fato de Rz ser limitado emΓ1 , donde, dividindo o intervalo de parametros em |t| ≤ 1/ log R e|t| > 1/ log R, obtemos a estimativa desejada, pois |t| ≤ 1/ log Re um intervalo de tamanho 2/ log R onde o integrando tem moduloO((log R)2), enquanto

∫ ∞

1/ log R

(log(t + 2)

)B · dt

t2

=∫ 1

1/ log R

(log(t + 2)

)B · dt

t2

+∫ ∞

1

(log(t + 2)

)B · dt

t2

= OB

(∫ 1

1/ log R

dt

t2)

+OB(1)

= OB(log R) +OB(1) = OB(log R).

O proximo lema esta relacionado com o caso m = 1 do Lema3.2.4:

Lema 3.4.2. Seja f(z, z′) analıtica em D1σ e suponha que

|f(z, z′)| ≤ exp(Om(log R)1/15

)


i

i

i

i

i

i

i

i


uniformemente nesse domınio. Entao a integral

I :=1

(2πi)2

∫

Γ1

∫

Γ1

f(z, z′)ζ(1 + z + z′)

ζ(1 + z)ζ(1 + z′)Rz+z′

z2z′2dzdz′

satisfaz a estimativa

I = f(0, 0) log R +∂f

∂z′(0, 0) +

12πi

∫

Γ0

f(z,−z)dz

ζ(1 + z)ζ(1− z)z4

+Om

(e−δ(log R)1/10)

,

para um certo δ = δ(σ, β) > 0 independente de R.

Demonstracao. Observamos que temos decaimento suficiente no in-tegrando para trocar a ordem de integracao, e para mover caminhosde integracao em cada variavel z, z′ mantendo a outra fixa, sem di-ficuldades quando Im(z), Im(z′) → ∞, pelas estimativas sobre ζ naregiao livre de zeros Z. Devemos apenas levar em conta o efeito demover caminhos de integracao atraves de um polo do integrando. Emparticular podemos mover o caminho de z′ de Γ1 para Γ2 , pois naopassamos por nenhum polo do integrando nesse processo. Considere-mos o integrando para cada z′ ∈ Γ2 como uma funcao analıtica de z,e vamos tentar mover o caminho de integracao em z para Γ0 . Nesseprocesso passamos por um unico polo em z = 0. O resıduo nesse polo

e1

(2πi)2

∫

Γ2

f(0, z′)Rz′

z′2dz′, e portanto temos I = I1 + I2 , onde

I1 :=1

2πi

∫

Γ2

f(0, z′)Rz′

z′2dz′ e

I2 :=1

(2πi)2

∫

Γ2

∫

Γ0

f(z, z′)ζ(1 + z + z′)Rz+z′

ζ(1 + z)ζ(1 + z′)z2z′2dzdz′.

Para estimar I1 , movemos o caminho de integracao para Γ0 .Como antes, ha apenas um polo, duplo, em z′ = 0. O resıduo nesse

polo e1

2πi

(f(0, 0) log R +

∂f

∂z′(0, 0)

), e portanto

I1 = f(0, 0) log R +∂f

∂z′(0, 0) +

12πi

∫

Γ0

f(0, z′)Rz′

z′2dz′ =

= f(0, 0) log R +∂f

∂z′(0, 0) +Om

(e−δ(log R)1/10)


i

i

i

i

i

i

i

i


para um certo δ > 0. A ultima igualdade e consequencia da primeiraestimativa para f no Lema 3.4.1 (com B = 0).

Para estimar I2 , olhamos o integrando como uma funcao analıticade z′. Movemos o caminho de integracao em z′ de Γ2 para Γ0 , o queesta autorizado pelo decaimento em faixas verticais quando |Im z′| →∞ do integrando. Fazendo isso, atravessamos exatamente dois polossimples, em z′ = −z e em z′ = 0. O resıduo no primeiro e

1(2πi)2

∫

Γ0

f(z,−z)dz

ζ(1 + z)ζ(1− z)z4,

o que fornece um dos termos em nossa formula para I.

O resıduo em z′ = 0 e1

(2πi)2

∫

Γ0

f(z, 0)Rz

z2dz, que e

O(e−δ(log R)1/10) · exp

(O((log R)1/15)) = O(e−δ(log R)1/10)

,

com δ = δ/2.O valor de I2 e a soma dessas duas quantidades com a integral

sobre o novo caminho de integracao Γ0 , que e

∫

Γ0

∫

Γ0

f(z, z′)ζ(1 + z + z′)Rz+z′

ζ(1 + z)ζ(1 + z′)z2z′2dzdz′.

Nesse integrando temos |f | = exp(Om((log R)1/15)). Por outro lado,temos

∣∣ 1ζ(1 + z)

∣∣ = O((log(|Im z|+2))7),∣∣ 1ζ(1 + z′)

∣∣ = O((log(|Im z′|+2))7)

e, como Re z, Re z′ ≥ −1/8 em Γ0 , Re (z + z′) ≥ 3/4, donde |ζ(1 +z + z′)| = O((|Im(z + z′)|+ 2)1/4), e portanto

∣∣ ζ(1 + z + z′)ζ(1 + z)ζ(1 + z′)

∣∣ =

= O((log(|Im z|+ 2))7)(log(|Im z′|+ 2))7)×× (|Im z|+ 2)1/4(|Im z′|+ 2)1/4) =

= O((|Im z|+ 2)1/2(|Im z′|+ 2)1/2) = O(|z|1/2|z′|1/2),


i

i

i

i

i

i

i

i


pelas estimativas sobre a funcao ζ descritas anteriormente. Assim,usando duas vezes (para z e z′) a primeira estimativa do Lema 3.4.1,obtemos que a integral em questao e Om

(e−δ(log R)1/10)

, para umcerto δ > 0.

Obtemos assim estimativas para I1 e I2 com erros que saoO(

e−δ(log R)1/10). Somando essas estimativas, completamos a prova

do lema.

Prova do Lema 3.2.4. Seja G = G(z, z′) uma funcao analıtica de2m variaveis complexas no domınio Dm

σ satisfazendo a hipotese

||G||Cm(Dmσ ) = exp(Om,σ((log R)1/15)).

No que segue permitiremos que as constantes implıcitas no notacaoO( ) dependam de m, β, σ. Queremos provar que a integral

I(G,m) :=1

(2πi)2m

∫

Γ1

. . .

∫

Γ1

G(z, z′)×

×m∏

j=1

ζ(1 + zj + z′j)ζ(1 + zj)ζ(1 + z′j)

Rzj+z′j

z2j z′2j

dzjdz′j ,

satisfaz a estimativa

I(G,m) = G(0, . . . , 0)(log R)m +m∑

i=1

O(||G||Cj(Dmσ )(log R)m−j)

+O(e−δ(log R)1/10).

A prova e por inducao em m. O caso m = 1 segue do Lema 3.4.2,pois ∣∣ ∂f

∂z′1(0, 0)

∣∣ = O(||G||C1(D1σ))

e

∣∣ 12πi

∫

Γ0

G(z1,−z1)dz1

ζ(1 + z1)ζ(1− z1)z41

∣∣

= O(||G||C0(D1σ)) = O(||G||C1(D1

σ)),


i

i

i

i

i

i

i

i


o que, por sua vez, segue de

∫

Γ0

∣∣ dz1

ζ(1 + z1)ζ(1− z1)z41

∣∣ = O(1).

A ultima estimativa e uma consequencia simples de nossas estimativaspara ζ em Z.

Suponhamos agora que vale o resultado para um certo m ≥ 1.Queremos prova-lo para m+1. Aplicando o Lema 3.4.2 nas variaveiszm+1, z′m+1 , obtemos

I(G,m + 1) =

=log R

(2πi)2m

∫

Γ1

. . .

∫

Γ1

G(z1, . . . , zm, 0, z′1, . . . , z′m, 0)×

×m∏

j=1

ζ(1 + zj + z′j)ζ(1 + zj)ζ(1 + z′j)

Rzj+z′j

z2j z′2j

dzjdz′j+

+1

(2πi)2m

∫

Γ1

. . .

∫

Γ1

(H(z1, . . . , zm, z′1, . . . , z′m)

+ r(z1, . . . , zm, z′1, . . . , z′m))

m∏

j=1

ζ(1 + zj + z′j)ζ(1 + zj)ζ(1 + z′j)

Rzj+z′j

z2j z′2j

dzjdz′j =

= I(G(z1, . . . , zm, 0, z′1, . . . , z′m, 0),m) log R + I(H,m),

onde δ > 0, H : Dmσ → C e a funcao definida por

H(z1, . . . , zm, z′1, . . . , z′m) :=

∂G

∂z′m+1

(z1, . . . , zm, 0, z′1, . . . , z′m, 0) +

+1

2πi

∫

Γ0

G(z1, . . . , zm, zm+1, z′1, . . . , z

′m, . . . ,−zm+1)×

× dzm+1

ζ(1 + zm+1)ζ(1− zm+1)z4m+1


i

i

i

i

i

i

i

i


e

r(z1, . . . , zm, z′1, . . . , z′m)

:=1

(2πi)2

∫

Γ1

∫

Γ1

G(z1, . . . , zm+1, z′1, . . . , z

′m+1)×

× ζ(1 + zm+1 + z′m+1)ζ(1 + zm+1)ζ(1 + z′m+1)

Rzm+1+z′m+1

z2m+1z

′2m+1

dzm+1dz′m+1

−H(z1, . . . , zm, z′1, . . . , z′m).

As funcoes G(z1, . . . , zm, 0, z′1, . . . , z′m, 0) e H(z1, . . . , zm, z′1, . . . , z

′m)

sao analıticas em Dmσ e, como

∫

Γ0

∣∣ dz

ζ(1 + z)ζ(1− z)z4

∣∣ = O(1), temos

||H||Cj(Dmσ ) = Om(||G||Cj+1(Dm+1

σ )), para 0 ≤ j ≤ m,

donde (usando tambem o caso m = 1) ||r||Cj(Dmσ ) =

Om(||G||Cj+1(Dm+1σ )). Alem disso, |r| = O(e−δ(log R)1/10

), pelo Lema3.4.2. Temos portanto, usando a hipotese de inducao,

I(G,m + 1) = G(0, . . . , 0)(log R)m+1+

+m∑

j=1

Om(||G(·, 0, ·, 0)||Cj(Dmσ )(log R)m+1−j)+

+ H(0, . . . , 0)(log R)m +m∑

j=1

Om(||H||Cj(Dmσ )(log R)m−j)+

+ r(0, . . . , 0)(log R)m +m∑

j=1

Om(||r||Cj(Dmσ )(log R)m−j) =

= G(0, . . . , 0)(log R)m+1 +m∑

j=1

Om(||G||Cj(Dm+1σ )(log R)m+1−j)+

+ H(0, . . . , 0)(log R)m +m∑

j=1

Om(||G||Cj+1(Dm+1σ )(log R)m−j)+

+O(e−δ(log R)1/10) +

m∑

j=1

Om(||G||Cj+1(Dm+1σ )(log R)m−j) =


i

i

i

i

i

i

i

i


= G(0, . . . , 0)(log R)m+1 +m+1∑

j=1

Om(||G||Cj(Dm+1σ )(log R)m+1−j)

+O(e−δ(log R)1/10),

que e o que querıamos provar.

Comentarios: Podemos evitar o uso do teorema de Dirichlet tro-cando Wn + 1 por Wn + b na definicao de Λ(n), onde b satisfazmdc (b,W ) = 1, 1 ≤ b < W e e tal que #1 ≤ n ≤ N | Wn +b e primo e maximo, pois, de fato, so precisamos da estimativa∑εkN≤n≤2εkN

Λ(n) ≥ c · εk N , para alguma constante positiva c. Esse

mesmo truque deve ser usado na prova da generalizacao do teoremaprincipal para a existencia de progressoes aritmeticas arbitrariamentelongas em conjuntos de primos com densidade positiva (tais conjuntosnao necessariamente conterao primos congruentes a 1 modulo W ). Oresto do argumento nao precisa de modificacoes substanciais.

Olhando retroativamente para a prova, vemos que o termo de errono teorema principal nao precisa ser o(1), mas basta ser, por exem-

plo,12

c(k, δ)+o(1), o que permite tomar w(N) uma constante grandedependendo apenas de k. Isto faz com que a perda na proporcao deprimos devida a passagem de n para Wn+1 seja uniformemente lim-itada em N , o que permite provar que existe uma constante γ(k) > 0tal que o numero de progressoes aritmeticas formadas por k numeros

primos entre 1 e N e pelo menos (γ(k) + o(1))N2

(log N)k· Por outro

lado, argumentos da teoria do crivo mostram que o numero de taisprogressoes aritmeticas e Ok(N2/(log N)k), e logo a estimativa infe-rior obtida difere do numero correto apenas por um fator limitado.


i

i

i

i

i

i

i

i


3.5 Apendice ao Capıtulo 3: dois resulta-dos elementares de teoria dos numeros.

I) A formula da inversao de Mobius.Definimos a funcao de Mobius como a funcao µ : N∗ → Z dada por

µ(n) =

0 se existe p primo tal que p2 | n(−1)k se n = p1p2 . . . pk , com p1 < p2 < · · · < pk primos

Em particular, µ(1) = 1 (1 e o produto de 0 fatores primos).

Obs.: A funcao µ e multiplicativa, i.e., mdc(mn) = 1 ⇒ µ(mn) =µ(m) · µ(n).

E bastante comum associar a uma funcao f : N∗ → C outra funcaog : N∗ → C dada por g(n) =

∑d|n

f(d). A formula da inversao de

Mobius permite recuperar f a partir de g. Provaremos inicialmenteo seguinte

Lema 3.5.1.∑d|n

µ(d) =

0, se n > 11, se n = 1

Demonstracao. Temos∑d|1

µ(d) = µ(1) = 1. Suponha agora que

n > 1. Seja p um fator primo de n. Temos X = d ≥ 1; q2|m ⇒ q = 1e d|n = Y ∪ Z, onde Y = d ∈ X; p - d e Z = d ∈ X; p|d =p · d, d ∈ Y . Se d|n e µ(d) 6= 0 entao d ∈ X. Por outro lado, sed ∈ Y , µ(p · d) = −µ(d), pois as paridades dos numeros de fatoresprimos de d e de p · d sao distintas. Portanto,

∑

d|nµ(d) =

∑

d∈X

µ(d) =∑

d∈Y

µ(d) +∑

d∈Z

µ(d)

=∑

d∈Y

(µ(d) + µ(p · d)) =∑

d∈Y

0 = 0.


i

i

i

i

i

i

i

i


Teorema A.2 (Formula da inversao de Mobius): Sejam f, g : N∗ →C funcoes tais que g(n) =

∑d|n

f(d), para todo n ∈ N∗. Entao temos

f(n) =∑d|n

µ(n

d

)g(d), para todo n ∈ N∗.

Demonstracao. Queremos provar que

f(n) =∑

d|nµ(n

d

)g(d) =

∑

d|nµ(n

d

)( ∑

d′|df(d′)

),

mas∑

d|nµ(n

d

)( ∑

d′|df(d′)

)=

∑

d′|nf(d′) · (

∑

d′|d|nµ(n

d

))

=∑

d′|nf(d′)

( ∑

d| nd′

µ(d))

= f(n),

pois∑

d| nd′

µ(d) =

0, se n/d′ > 1, i.e., se d′ < n

1, se n/d′ = 1, i.e., se d′ = n.

II) A ordem maxima de d(n).Seja d(n), para cada n ∈ N∗, o numero de divisores (positivos) de

n. Temos entao o seguinte

Teorema A.3: Para todo ε > 0 existe n0 ∈ N tal que n > n0 ⇒d(n) < 2(1+ε) log n/ log log n.

Demonstracao. Seja n = pα11 pα2

2 . . . pαk

k , p1 < p2 < · · · < pk

primos a fatoracao prima de n. Temos entao

d(n) =k∏

j=1

(1 + αj) =∏

pj≤(log n)1−δ

(1 + αj)×

×∏

pj>(log n)1−δ

(1 + αj), onde δ = ε/2(1 + ε).


i

i

i

i

i

i

i

i


Para todo j, 1 + αj ≤ 2αj , donde

∏

pj>(log n)1−δ

(1 + αj) ≤ 2

Ppj>(log n)1−δ

αj

≤ 2log n/ log((log n)1−δ)

= 2log n/(1−δ) log log n

(de fato, n ≥ ∏pj>(log n)1−δ

pαj

j ≥ ((log n)1−δ)

Ppj>(log n)1−δ

αj

).

Por outro lado, para todo j, 1 + αj ≤ 1 +log n

log 2, pois n ≥ p

αj

j ≥2αj ⇒ log n ≥ αj log 2. Assim,

∏

pj≤(log n)1−δ

(1 + αj) ≤(

1 +log n

log 2

)(log n)1−δ

= 2O(log log n·(log n)1−δ).

Temos entao

d(n) =k∏

j=1

(1 + αj) ≤ 2log n/(1−δ) log log n+O(log n/ log log n)

< 2(1+ε) log n/ log log n

se n e suficientemente grande, pois1

1− δ<

11− 2δ

= 1 + ε.

Corolario. Para todo ε > 0 existe n0 ∈ N tal que n > n0 ⇒#p primo, p|n < (1 + ε) log n/ log log n.

(De fato, temos 2#p primo,p|n ≤ d(n), para todo inteiro positivon.)

Nota: E possıvel provar que, se p1 < p2 < · · · < pk sao os k primeiros

numeros primos e Nk =k∏

j=1

pj entao d(Nk) > 2log Nk

log log Nk , para k su-

ficientemente grande. De fato, pr < 2r log r, para todo r grande,

donde log Nk =k∑

j=1

log pj < O(1) +k∑

j=2

(log 2 + log j + log log j) =


i

i

i

i

i

i

i

i


O(1) + k log 2 + k log k − k + o(k) + k log log k + o(k) = k(log k +log log k − (1− log 2)) + o(k), donde

log Nk/ log log Nk < k(log k + log log k)/ log(k(log k + log log k))< k = log d(Nk)/ log 2,

para todo k suficientemente grande.


i

i

i

i

i

i

i

i

ReferenciasBibliograficas

[1] Aarao, J. O teorema dos numeros primos. Tese de Mestrado.IMPA. 1988.

[2] Brun, V. La serie 1/5 + 1/7 + 1/11 + 1/13 + 1/17 + 1/19 +1/29+1/31+1/41+1/43+1/59+1/61+ ..., les denominateurssont nombres premiers jumeaux est convergente ou finie. Bull.Sci. Math. 43, 124-128, 1919.

[3] Chen, J. On the representation of a larger even integer as thesum of a prime and the product of at most two primes. Sci.Sinica 16, 157-176, 1973.

[4] Goldston, A., Motohashi Y., Pintz, J. eYildirim, Y. Small Gaps between Primes Exist.http://front.math.ucdavis.edu/math.NT/0505300.

[5] Green, B. e Tao, T. The primes contain arbitrarilylong arithmetic progressions. To appear, Annals of Math.http://front.math.ucdavis.edu/math.NT/0404188 (2004).

[6] Goldston, A. e Yıldırım, Y. Small Gaps Between Primes I.http://front.math.ucdavis.edu/math.NT/0504336.

[7] Roth, K. On certain sets of integers. J. London Math. Soc. 28245-252. 1953.

[8] Schnirelman, L. G. Uspekhi Math. Nauk 6, 3-8, 1939.

123


i

i

i

i

i

i

i

i

124 REFERENCIAS BIBLIOGRAFICAS

[9] Szemeredi, E. On sets of integers containing no k elements inarithmetic progression. Acta Arith. 27 299-345, 1975.

[10] T. Tao. Arithmetic Progressions and the Primes - El EscorialLectures. Lecture Notes, 2005.

[11] Tao, T. The ergodic and combinatorial approaches toSzemeredi’s theorem. Intended for proceedings of the Mon-treal workshop on additive combinatorics and number theory.http://front.math.ucdavis.edu/math.CO/0604456.

[12] Tao, T. The Gaussian primes contain arbitrarily shaped con-stellations. J. d´Analyse Mathematique 99, 109-176 2006.

[13] Tao, T. e Ziegler, T. The primes contain arbitrar-ily long polynomial progressions. To appear, Acta Math.http://arxiv.org/abs/math.NT/0610050.

[14] Van der Corput, J. Uber Summen von Primzahlen undPrimzahlquadraten. Math. Ann. 116, 1-50, 1939.

[15] Vinogradov, I. Representation of an odd prime as a sum ofthree primes. Comptes Rendus (Doklady) de l´Academie des Sci-ences de PURSS 15 291-294. 1937.

Documents

ColoquioMateusGuguAlexNew i 2007/6/29 page 1 iw3.impa.br/~gugu/Moreira_Matheus_Alexander.pdf · \ColoquioMateusGuguAlexNew" 2007/6/29 page 5 i i i i i i i i Sum¶ario 1 Propriedades