Introdução à Teoria dos Números

(com ênfase em Aproximações Diofantinas)

Carlos Gustavo T. de A. Moreira

I M P A

Estrada Dona Castorina 110, Jardim Botânico

Rio de Janeiro-RJ CEP 22.460-320 - Brasil Correio eletrônico: gugu@impa.br Página na internet: www.impa.br/∼ gugu

Conteúdo

Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

PARTE I: CONGRUÊNCIAS E NÚMEROS PRIMOS

Capítulo 1: Divisibilidade e Congruências 7 1 Divisão euclidiana e o teorema fundamental da aritmética . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Congruências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10 3 A função de Euler e o pequeno teorema de Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14 4 A função de Möbius . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 5 Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 6 Corpos e polinômios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 7 Ordens e raízes primitivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 8 Raízes primitivas em ℤ/(n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .30 9 A lei da reciprocidade quadrática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 10 Extensões quadráticas de corpos finitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

Capítulo 2: Números Primos 37 1 Sobre a distribuição dos números primos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37 2 Outros resultados e conjecturas sobre primos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3 Fórmulas para primos e testes de primalidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4 Testes de primalidade baseados em fatorações de n − 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5 Primos de Mersenne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

PARTE II: APROXIMAÇÕES DIOFANTINAS

Capítulo 3: Frações Contínuas, Representações de Números e Aproximações 54 1 Reduzidas e boas aproximações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2 Boas aproximações são reduzidas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3 Frações contínuas periódicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

Aplicação: a equação de Pell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .64

Capítulo 4: Propriedades Estatísticas de Frações Contínuas e Aproximações

Dioantinas: O Teorema de Khintchine 66

1 O Teorema de Khintchine via frações contínuas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 2 O Teorema de Khintchine n-dimensional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .71

Apêndice: Aproximações diofantinas não-homogêneas . . . . . . . . . . . . . . . . . . . 75

Capítulo 5: Os Espectros de Markov e Lagrange 77 1 Definições e enunciados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .77 2 Dimensões de Hausdorff e somas aritméticas de conjuntos de Cantor

de frações contínuas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 3 Idéias das demonstrações dos resultados sobre os espectros . . . . . . . . . . . . . . . . . . . . . . . . . .81 4 Espectros de Markov e Langrange dinâmicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .83 Apêndice: Conjuntos de Cantos Regulares e Dimensões Fractais . . . . . . . . 85 1.0 Conjuntos de Cantor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 1.1 Conjuntos de Cantor regulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 1.2 Distorção limitada e geometrias limite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 1.3 Dimensões fractais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .91

Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .96

Introdução

Estas são as notas de um mini-curso que fui convidado a dar no IMCA em novembro de 2001. Boa parte do material aqui contido foi adaptado das notas dos cursos “Primos de Mersenne (e outros primos muito grandes)”, em colaboração com Nicolau Saldanha e “Conjuntos de Cantor, Dinâmica e Aritmética”, que dei no XXII Colóquio Brasileiro de Matemática, em 1999, e do artigo “Propriedades Estatísticas de Frações Contínuas e Aproximações Diofantinas”, publicado na Revista Matemática Universitária.

O objetivo dessas notas é ser uma referência introdutória sobre teoria dos números e aproximações diofantinas, destinada a alunos de graduação ou mestrado em matemática. Boa parte do material é totalmente elementar, sendo acessível a bons alunos do ensino médio (em particular aos olímpicos...). Agradeço aos Professores Cesar Camacho e Roger Metzger pelo convite e a oportunidade de visitar o Peru e dar aulas sobre esse assunto tão fascinante.

Rio de Janeiro, 26 de outubro de 2001.

4

PARTE I

CONGRUÊNCIAS E NÚMEROS PRIMOS

6

CAPÍTULO 1

Divisibilidade e Congruências

Neste primeiro capítulo veremos os tópicos básicos de teoria dos números, como divisibilidade, congruências e aritmética módulo n.

1 Divisão euclidiana e o teorema fundamental da

aritmética

A divisão euclidiana, ou divisão com resto, é uma das quatro operações que toda criança aprende na escola. Sua formulação precisa é: dados a ∈ ℤ, b ∈ ℤ^{∗} existem q, r ∈ ℤ com 0 ≤ r < |b| e a = bq + r. Tais q e r estão unicamente determinados e são chamados o quociente e resto da divisão de a por b. Se b > 0 podemos definir q = ⌊a/b⌋ e se b < 0, q = ⌈a/b⌉; em qualquer caso, r = a − bq. O resto r é às vezes denotado por a mod b; definimos a mod 0 = a. Lembramos que ⌊x⌋ denota o único inteiro k tal que k ≤ x < k + 1 e ⌈x⌉ o único inteiro k tal que k − 1 < x ≤ k.

Dados dois inteiros a e b (em geral com b ≠ 0) dizemos que b divide a, ou que a é um múltiplo de b, e escrevemos b|a, se existir q ∈ ℤ com a = qb. Se a ≠ 0, também dizemos que b é um divisor de a. Assim, b|a se e somente se a mod b = 0.

Proposição 1.1: Dados a, b ∈ ℤ existe um único d ∈ ℕ tal que d|a, d|b e, para todo c ∈ ℕ, se c|a e c|b então c|d. Além disso existem x, y ∈ ℤ com d = ax + by.

Esse natural d é chamado o máximo divisor comum, ou mdc, entre a e b. Escrevemos d = mdc(a, b) ou (se não houver possibilidade de confusão) d = (a, b).

Dem: O caso a = b = 0 é trivial (temos d = 0). Nos outros casos, seja I(a, b) = {ax+by; x, y ∈ ℤ} e seja d = ax_{0} + by_{0} o menor elemento positivo de I(a, b). Como d ∈ ℕ^{∗}, existem q, r ∈ ℤ com a = dq + r e 0 ≤ r < d. Temos r = a − dq = a(1 − qx_{0}) + b(−qy_{0}) ∈ I(a, b); como r < d e d é o menor elemento positivo de I(a, b), r = 0 e d|a. Analogamente, d|b. Suponha agora que c|a e c|b; temos c|ax + by para quaisquer valores de x e y donde, em particular, c|d. ■

O algoritmo de Euclides para calcular o mdc baseia-se nas seguintes observações simples. Se a = bq + r, 0 ≤ r < b, temos (com a notação da demonstração acima) I(a, b) = I(b, r), donde (a, b) = (b, r). Definindo a_{0} = a, a_{1} = b e a_{n} = a_{n+1}q_{n+2} + a_{n+2}, 0 ≤ a_{n+2} < a_{n+1} (ou seja, a_{n+2} é o resto da divisão de a_{n} por a_{n+1}) temos (a, b) = (a_{0}, a_{1}) = (a_{1}, a_{2}) = (a_{2}, a_{3}) = ⋯ = (a_{n}, a_{n+1}) para qualquer valor de n. Seja N o menor natural para o qual a_{N+1} = 0: temos (a, b) = (a_{N}, 0) = a_{N}.

Lema 1.2: Se (a, b) = 1 e a|bc então a|c.

Dem: Como (a, b) = 1, existem x, y ∈ ℤ com ax + by = 1, logo a|c = acx + bcy. ■

Quando (a, b) = 1 dizemos que a e b são primos entre si. Um natural p > 1 é chamado primo se os únicos divisores positivos de p são 1 e p. Um natural n > 1 é chamado composto se admite outros divisores além de 1 e n.

Claramente, se p é primo e p ∤ a temos (p, a) = 1. Usando o lema anterior e indução temos o seguinte resultado:

Corolário 1.3: Sejam p um número primo e sejam a_{1}, … a_{m} ∈ ℤ. Se p|a_{1} ⋯ a_{m} então p|a_{i} para algum i, 1 ≤ i ≤ n.

Estamos agora prontos para enunciar e provar o teorema que diz que todo inteiro admite fatoração única como produto de primos.

Teorema 1.4: (Teorema fundamental da aritmética) Seja n ≥ 2 um número natural. Podemos escrever n de uma única forma como um produto

n = p_{1} ⋯ p_{m}

onde m ≥ 1 é um natural e p_{1} ≤ … ≤ p_{m} são primos.

Dem: Mostramos a existencia da fatoração por indução. Se n é primo não há o que provar (escrevemos m = 1, p_{1} = n). Se n é composto podemos escrever n = ab, a, b ∈ ℕ, 1 < a < n, 1 < b < n. Por hipótese de indução, a e b se decompõem como produto de primos. Juntando as fatorações de a e b (e reordenando os fatores) obtemos uma fatoração de n.

Vamos agora mostrar a unicidade, também por indução. Suponha que

n = p_{1} ⋯ p_{m} = q_{1} ⋯ q_{m′},

com p_{1} ≤ … ≤ p_{m}, q_{1} ≤ … ≤ q_{m′}. Como p_{1}|q_{1} ⋯ q_{m′} temos p_{1}|q_{i} para algum valor de i, donde, como q_{i} é primo, p_{1} = q_{i} e p_{1} ≥ q_{1}. Analogamente temos q_{1} ≤ p_{1}, donde p_{1} = q_{1}. Mas por hipótese de indução

n/p_{1} = p_{2} ⋯ p_{m} = q_{2} ⋯ q_{m′}

admite uma única fatoração, donde m = m′ e p_{i} = q_{i} para todo i. ■ Outra forma de escrever a fatoração é

n = p_{1}^{e_{1}} ⋯ p_{m}^{e_{m}},

com p_{1} < ⋯ < p_{m}, e_{i} > 0. Ainda outra formulação é escrever

n = 2^{e_{2}}3^{e_{3}}5^{e_{5}} ⋯ p^{e_{p}} ⋯

onde o produto é tomado sobre todos os primos mas apenas um número finito de expoentes é maior do que zero.

Segue deste teorema o outro algoritmo comum para calcular o mdc de dois números: fatoramos os dois números e tomamos os fatores comuns com os menores expoentes. Este algoritmo é bem menos eficiente do que o de Euclides para inteiros grandes (que em geral não sabemos fatorar) mas é instrutivo saber que os dois algoritmos dão o mesmo resultado.

Corolário 1.5: Se (a, n) = (b, n) = 1 então (ab, n) = 1.

Dem: Evidente a partir do algoritmo descrito acima. ■

Teorema 1.6: (Euclides) Existem infinitos números primos.

Dem: Suponha por absurdo que p_{1}, p_{2}, ..., p_{m} fossem todos os primos. O número N = p_{1}·p_{2} ⋯ p_{m}+1 > 1 não seria divisível por nenhum primo, o que contradiz o teorema fundamental da aritmética. ■

Observe que não provamos que p_{1} · p_{2} ⋯ p_{m} + 1 é primo para algum conjunto finito de primos (por exemplo, os m primeiros primos). Aliás, 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30031 = 59 · 509, 2 · 3 · 5 · 7 − 1 = 209 = 11 · 19, 4! + 1 = 25 = 5^{2} e 8! − 1 = 40319 = 23 · 1753 não são primos. Não existe nenhuma fórmula simples conhecida que gere sempre números primos. Veja a seção 3.1.

2 Congruências

Sejam a, b, n ∈ ℤ. Dizemos que a é congruente a b módulo n, e escrevemos a ≡ b (mod n), se n|b − a. Como a congruência módulo 0 é a igualdade e quaisquer inteiros são côngruos módulo 1, em geral estamos interessados em n > 1.

Proposição 2.1: Para quaisquer a, a′, b, b′, c, n ∈ ℤ temos:

(a)

1. a ≡ a (mod n);

2. se a ≡ b (mod n) então b ≡ a (mod n);

3. se a ≡ b (mod n) e b ≡ c (mod n) então a ≡ c (mod n);

4. se a ≡ a′ (mod n) e b ≡ b′ (mod n) então a + b ≡ a′ + b′ (mod n);

5. se a ≡ a′ (mod n) então −a ≡ −a′ (mod n);

6. se a ≡ a′ (mod n) e b ≡ b′ (mod n) então a · b ≡ a′ · b′ (mod n).

Dem: Para o item (a) basta observar que n|a − a = 0. Em (b), se n|b − a então n|a − b = −(b−a). Em (c), se n|b−a e n|c−b então n|c−a = (c−b)+(b−a). Em (d), se n|a′−a e n|b′−b então n|(a′+b′)−(a+b) = (a′−a)+(b′−b). Em (e), se n|a′−a então n|(−a′)−(−a) = −(a′−a). Em (f), se n|a′ − a e n|b′ − b então n|a′b′ − ab = a′(b′ − b) + b(a′ − a). ■

Os itens (a), (b) e (c) da proposição acima dizem, nesta ordem, que a relação ≡ (mod n) (“ser côngruo módulo n”) é uma relação reflexiva, simétrica e transitiva. Relações satisfazendo estas três propriedades são chamadas relações de equivalência. Dada uma relação de equivalência ∼ sobre um conjunto X e um elemento x ∈ X definimos a classe de equivalência \overline{x} de x como

\overline{x} = \{y ∈ X|y ∼ x\};

observe que x ∼ y se e somente se \overline{x} = \overline{y}. As classes de equivalência formam uma partição de X, i.e., uma coleção de subconjuntos não vazios e disjuntos de X cuja união é X. O conjunto \{\overline{x}|x ∈ X\} das classes de equivalência é chamado o quociente de X pela relação de equivalência ∼ e é denotado por X/ ∼.

Aplicando esta construção geral ao nosso caso, definimos o quociente ℤ/(≡ (mod n)), chamado por simplicidade de notação de ℤ/(n), ℤ/nℤ ou às vezes ℤ_{n}. Dado a ∈ ℤ, a definição de \overline{a} como um subconjunto de ℤ raramente será importante: o importante é sabermos que \overline{a} = \overline{a′} se e somente se a ≡ a′ (mod n). Se n > 0, a divisão euclidiana diz que todo inteiro a é côngruo a um único inteiro a′ com 0 ≤ a′ < n; podemos reescrever este fato na nosso nova linguagem como

ℤ/(n) = \{\overline{0}, \overline{1}, …, \overline{n − 1}\}.

Quando não houver possibilidade de confusão omitiremos as barras e chamaremos os elementos de ℤ/(n) simplesmente de 0, 1, …, n − 1.

Os itens (d), (e) e (f) da proposição dizem que as operações de soma, diferença e produto são compatíveis com a relação de congruência. É esta propriedade que torna congruências tão úteis, nos possibilitando fazer contas módulo n. Podemos por exemplo escrever

196883 = 1 · 10^{5} + 9 · 10^{4} + 6 · 10^{3} + 8 · 10^{2} + 8 · 10^{1} + 3 · 10^{0}

≡ 1 · 1^{5} + 9 · 1^{4} + 6 · 1^{3} + 8 · 1^{2} + 8 · 1^{1} + 3 · 1^{0} = 1 + 9 + 6 + 8 + 8 + 3 = 35 ≡ 8 (mod 9), já que 10 ≡ 1 (mod 9) (mostrando assim porque funciona o conhecido critério de divisibilidade por 9). Uma formulação mais abstrata da mesma idéia é dizer que as operações + e · passam ao quociente, i.e., que podemos definir

+ : ℤ/(n) × ℤ/(n) → ℤ/(n), · : ℤ/(n) × ℤ/(n) → ℤ/(n)

por \overline{a} + \overline{b} = \overline{a + b} e \overline{a} · \overline{b} = \overline{a · b}. A dúvida à primeira vista seria se a escolha de a e b não afeta a resposta: afinal existem infinitos inteiros a′ e b′ com \overline{a} = \overline{a′} e \overline{b} = \overline{b′}. Os itens (d) e (f) da proposição são exatamente o que precisamos: eles nos dizem que nestas condições \overline{a + b} = \overline{a′ + b′} e \overline{a · b} = \overline{a′ · b′}.

Proposição 2.2: Sejam a, n ∈ ℤ, n > 0. Então existe b ∈ ℤ com ab ≡ 1 (mod n) se e somente se (a, n) = 1.

Dem: Se ab ≡ 1 (mod n) temos nk = 1 − ab para algum k, donde (a, n)|ab + nk = 1 e (a, n) = 1. Se (a, n) = 1 temos ax + ny = 1 para certos inteiros x e y, donde ax ≡ 1 (mod n).

■

Dizemos portanto que a é invertível ^{1} módulo n quando (a, n) = 1 e chamamos b com ab ≡ 1 (mod n) de inverso de a módulo n. O inverso é sempre único módulo n: se ab ≡ ab′ ≡ 1 (mod n) temos b ≡ ab^{2} ≡ abb′ ≡ b′ (mod n).

Corolário 2.3: Se (a, n) = 1 e ab ≡ ab′ (mod n) então b ≡ b′ (mod n).

Dem: Basta escrever b ≡ abc ≡ ab′c ≡ b′ (mod n) onde c é o inverso de a módulo n. ■ Definimos (ℤ/(n))^{∗} ⊂ ℤ/(n) por

(ℤ/(n))^{∗} = \{\overline{a}; (a, n) = 1\}.

Observe que o produto de elementos de (ℤ/(n))^{∗} é sempre um elemento de (ℤ/(n))^{∗} (corolário 1.5).

1Alguns autores preferem escrever inversível. Os interessados em discutir esta questão ortográfica devem escrever para o Prof. Zoroastro Azambuja, IMPA, Estr. D. Castorina 110, Rio de Janeiro, RJ

Teorema 2.4: (Teorema Chinês dos restos) Se (m, n) = 1 então

f : ℤ/(mn) → ℤ/(m) × ℤ/(n)
\overline{a} ↦ (\overline{a}, \overline{a})

é uma bijeção. Além disso, a imagem por f de (ℤ/(mn))^{∗} é (ℤ/(m))^{∗} × (ℤ/(n))^{∗}.

Note que cada \overline{a} na definição de f é tomado em relação a um módulo diferente. A função está bem definida pois a mod mn determina a mod m e a mod n.

Dem: Como ℤ/(mn) e ℤ/(m) × ℤ/(n) têm mn elementos cada, para provar que f é bijetiva basta verificar que f é injetiva. E, de fato, se a ≡ a′ (mod m) e a ≡ a′ (mod n) então m|(a − a′) e n|(a − a′), donde mn|(a − a′) e a ≡ a′ (mod mn). A imagem de (ℤ/(mn))^{∗} é (ℤ/(m))^{∗} × (ℤ/(n))^{∗} pois (a, mn) = 1 se e somente se (a, m) = (a, n) = 1. ■

Dados inteiros m_{1}, m_{2}, …, m_{r}, dizemos que estes inteiros são primos entre si se (m_{i}, m_{j}) = 1 para quaiquer i ≠ j.

Corolário 2.5: Se m_{1}, m_{2}, …, m_{r} são inteiros primos entre si. Então

f : ℤ/(m_{1}m_{2} ⋯ m_{r}) → ℤ/(m_{1}) × ℤ/(m_{2}) ⋯ ℤ/(m_{r})
\overline{a} ↦ (\overline{a}, \overline{a}, …, \overline{a})

é uma bijeção.

Dem: Basta aplicar o teorema anterior r vezes. ■

A aplicação mais comum deste teorema é para garantir que existe a com a ≡ a_{i} (mod m_{i}) onde a_{i} são inteiros dados quaisquer.

Problema resolvido: Prove que dado n ∈ ℕ existe um conjunto de n elementos A ⊂ ℕ tal que para todo B ⊂ A, B ≠ ∅, ∑_{x∈B} x é uma potência não trivial (isto é, um número da forma m^{k}, onde m, k são inteiros maiores ou iguais a 2), ou seja, A = {x_{1}, x_{2}, … x_{n}} tal que x_{1}, x_{2}, … x_{n}, x_{1} +x_{2}, x_{1} +x_{3}, …, x_{n−1} +x_{n}, …, x_{1} +x_{2} +… x_{n} são todos potências não triviais.

Solução: A = {4} é solução para n = 1, A = {9, 16} é solução para n = 2. Vamos provar a existência de um tal conjunto por indução em n. Suponha que A = {x_{1}, …, x_{n}} é um conjunto com n elementos e para todo B ⊂ A, B ≠ ∅, ∑_{x∈B} x = m_{B}^{k_{B}}. Vamos mostrar que existe c ∈ ℕ tal que o conjunto Ã = {cx_{1}, cx_{2}, …, cx_{n}, c} satisfaz o enunciado.

Seja ℓ = mmc{k_{b}, B ⊂ A, B ≠ ∅} o mínimo múltiplo comum de todos os exponentes k_{B}. Para cada B ⊂ A, B ≠ ∅ associamos um número primo p_{B} > ℓ, de forma que B_{1} ≠ B_{2} ⇒

p_{B_{1}} ≠ p_{B_{2}}, e associamos um natural r com r_{B} ≡ 0 (módulo p_{x}), ∀ X ≠ B, ℓr_{B} + 1 ≡ 0 (módulo p_{B}) (tal r_{B} existe pelo teorema chinês dos restos), e tomamos

c = ∏_{\begin{matrix}B⊂A \\ B≠∅ \end{matrix}}(1 + m_{B}^{k_{B}})^{ℓr_{B}}.

Como c é uma potência ℓ-ésima, c é uma potência k_{B}-ésima para todo B ⊂ A, B ≠ ∅, portanto, para B′ ⊂ {cx_{1}, cx_{2}, …, cx_{n}}, B′ ≠ ∅, teremos B′ = {cx | x ∈ B} para algum B ⊂ A, B ≠ ∅. Logo ∑_{x∈B′} x será uma potência k_{B}-ésima.

Além disso,

∑_{X∈B′U\{c\}} x = c(1 + m_{B}^{K_{B}}) = [ ∏_{\begin{matrix}X⊂A \\ X≠∅,B \end{matrix}}(1 + m_{X}^{K_{X}})^{ℓr_{X}} ] · (1 + m_{B}^{K_{B}})^{ℓr_{B}+1},

que é uma potência p_{B}-ésima, pois r_{X} é múltiplo de p_{B} para X ≠ B e ℓr_{B} + 1 é múltiplo de p_{B}. ■

3 A função de Euler e o pequeno teorema de Fermat

Definimos φ(n) = |(ℤ/(n))^{∗}| (onde |X| denota o número de elementos de X). A função φ é conhecida como a função de Euler. Temos φ(1) = φ(2) = 1, e, para n > 2, 1 < φ(n) < n. Se p é primo, φ(p) = p − 1; mais geralmente φ(p^{k}) = p^{k} − p^{k−1} pois (a, p^{k}) = 1 se e somente se a não é múltiplo de p e há p^{k−1} múltiplos de p no intervalo 0 ≤ a < p^{k}.

Dizemos que os n números inteiros a_{1}, a_{2}, …, a_{n} formam um sistema completo de resíduos (ou s.c.r.) módulo n se \{\overline{a_{1}}, \overline{a_{2}}, … \overline{a_{n}}\} = ℤ/(n), isto é, se os a_{i} representam todas as classes de congruência módulo n. Por exemplo, 0, 1, 2, … n − 1 formam um s.c.r. módulo n. Equivalentemente, podemos dizer que a_{1}, a_{2}, …, a_{n} formam um s.c.r. módulo n se e somente se a_{i} ≡ a_{j} (mod n) implicar i = j. Os φ(n) números inteiros b_{1}, b_{2}, …, b_{φ(n)} formam um sistema completo de invertíveis (s.c.i.) módulo n se

\{\overline{b_{1}}, \overline{b_{2}}, … \overline{b_{φ(n)}}\} = (ℤ/(n))^{∗},

isto é, se os b_{i} representam todas as classes de congruências invertíveis módulo n. Também equivalentemente, b_{1}, b_{2}, …, b_{φ(n)} formam um s.c.i. módulo n se e somente se (b_{i}, n) = 1 para todo i e a_{i} ≡ a_{j} (mod n) implicar i = j.

Proposição 3.1: Sejam q, r, n ∈ ℤ, n > 0, q invertível módulo n, a_{1}, a_{2}, …, a_{n} um s.c.r. módulo n e b_{1}, b_{2}, …, b_{φ(n)} um s.c.i. módulo n. Então qa_{1} + r, qa_{2} + r, …, qa_{n} + r formam um s.c.r. módulo n e qb_{1}, qb_{2}, ...qb_{φ(n)} formam um s.c.i. módulo n.

Dem: Se qa_{i} + r ≡ qa_{j} + r (mod n) então n|q(a_{i} − a_{j}) e a_{i} ≡ a_{j} (mod n), donde i = j; com isto provamos que qa_{1} + r, qa_{2} + r, …, qa_{n} + r formam um s.c.r..

Como (q, n) = (b_{i}, n) = 1, temos (qb_{i}, n) = 1. Por outro lado, se qb_{i} ≡ qb_{j} (mod n) temos b_{i} ≡ b_{j} (mod n) (como no parágrafo anterior) e i = j. Isto conclui a demonstração. ■

Teorema 3.2: (Euler) Sejam a, n ∈ ℤ, n > 0, tais que (a, n) = 1. Então a^{φ(n)} ≡ 1 (mod n).

Dem: Seja

b_{1}, b_{2}, ….b_{φ(n)}

um s.c.i. módulo n. Pela proposição anterior,

ab_{1}, ab_{2}, … ab_{φ(n)}

também formam um s.c.i. módulo n. Assim,

b_{1} · b_{2} ⋯ b_{φ(n)} ≡ ab_{1} · ab_{2} ⋯ ab_{φ(n)} (mod n)

pois módulo n os dois lados têm os mesmos fatores a menos de permutação. Mas isto pode ser reescrito como

a^{φ(n)}(b_{1} · b_{2} ⋯ b_{φ(n)}) ≡ 1 · (b_{1} · b_{2} ⋯ b_{φ(n)}) (mod n)

e pelo corolário 1.9 isto implica a^{φ(n)} ≡ 1 (mod n). ■

Corolário 3.3: (Pequeno Teorema de Fermat) Se p é primo então, para todo inteiro a, a^{p} ≡ a (mod p).

Dem: Se p|a, então a^{p} ≡ a ≡ 0 (mod p). Caso contrário, φ(p) = p − 1, a^{p−1} ≡ 1 (mod p) e novamente a^{p} ≡ a (mod p). ■

Outra demonstração do pequeno teorema de Fermat é por indução em a usando o binômio de Newton e algumas propriedades de números binomiais. Se 0 < i < p temos

\binom{p}{i} = \frac{p!}{i!(p − i)!} ≡ 0 (mod p)

pois há um fator p no numerador que não pode ser cancelado com nada que apareça no denominador. Os casos a = 0 e a = 1 do teorema são triviais. Supondo válido o teorema para a, temos

(a + 1)^{p} = a^{p} + \binom{p}{1}a^{p−1} + ⋯ + \binom{p}{p − 1}a + 1
≡ a^{p} + 1
≡ a + 1 (mod p)

e a indução está completa.

Corolário 3.4: Se (m, n) = 1 então φ(mn) = φ(m)φ(n).

Dem: Construimos uma bijeção entre (ℤ/(mn))^{∗} e (ℤ/(m))^{∗} × (ℤ/(n))^{∗}, o que garante que estes conjuntos têm o mesmo número de elementos. ■

Corolário 3.5: Se

n = p_{1}^{e_{1}}p_{2}^{e_{2}} ⋯ p_{m}^{e_{m}}

com p_{1} < p_{2} < … < p_{m} e e_{i} > 0 para todo i então

φ(n) = (p_{1}^{e_{1}} − p_{1}^{e_{1}−1})(p_{2}^{e_{2}} − p_{2}^{e_{2}−1}) ⋯ (p_{m}^{e_{m}} − p_{m}^{e_{m}−1})

= n (1 − \frac{1}{p_{1}} ) (1 − \frac{1}{p_{2}} ) ⋯ (1 − \frac{1}{p_{m}} ) .

Dem: Isto segue da fórmula que já vimos para φ(p^{e}) e do corolário anterior. ■

Em particular, se n > 2 então φ(n) é par.

Problema resolvido: Exiba n ∈ ℕ tal que 2^{n} tenha mais de duas mil casas decimais e tenha entre suas 2000 últimas casas decimais 1000 zeros consecutivos.

Solução: 2^{φ(5^{2000})} ≡ 1 (módulo 5^{2000}), pelo Teorema de Euler. Portanto, existe b ∈ ℕ com 2^{φ(5^{2000})} = 5^{2000}b + 1, e teremos 2^{2000+φ(5^{2000})} = 10^{2000}b + 2^{2000}, e portanto os 2000 últimos dígitos de 2^{2000+φ(5^{2000})} coincidem com a representação decimal de 2^{2000}, que tem no máximo 667 dígitos, pois 2^{3} < 10 ⇒ 2^{2000} < 2^{3.667} < 10^{667}. Desta forma, 2^{2000+φ(5^{2000})} tem pelo menos 2000 − 667 = 1333 zeros consecutivos dentre as 2000 últimas casas decimais, de modo que n = 4.5^{1999} + 2000 satisfaz as condições do enunciado (pois φ(5^{2000}) = 4.5^{1999}). ■

Mais adiante estudaremos equações do segundo grau em ℤ/(p); vejamos desde já um pequeno resultado deste tipo que garante que os únicos a que são seus próprios inversos módulo p são 1 e −1.

Lema 3.6: Se p é primo então as únicas soluções de x^{2} = 1 em ℤ/(p) são 1 e −1. Em particular,se x ∈ (ℤ/(p))^{∗} − {1, −1} então x^{−1} ≠ x em ℤ/(p).

Dem: Podemos reescrever a equação como (x − 1)(x + 1) = 0, o que torna o resultado trivial. ■

Teorema 3.7: (Wilson) Seja n > 4. Então (n − 1)! ≡ −1 (mod n) se n é primo e (n − 1)! ≡ 0 (mod n) se n é composto.

Dem: Se n é composto mas não é o quadrado de um primo podemos escrever n = ab com 1 < a < b < n: neste caso tanto a quanto b aparecem em (n − 1)! e (n − 1)! ≡ 0 (mod n). Se n = p^{2}, p > 2, então p e 2p aparecem em (n − 1)! e novamente (n − 1)! ≡ 0 (mod n); isto demonstra que para todo n composto, n > 4, temos (n − 1)! ≡ 0 (mod n).

Se n é primo podemos escrever (n − 1)! ≡ −(2 · 3 ⋯ n − 2) (mod n); mas pelo lema anterior podemos juntar os inversos aos pares no produto do lado direito, donde (n−1)! ≡ −1 (mod n).

■

4 A função de Möbius

Vejamos inicialmente uma propriedade da função φ.

Teorema 4.1: Para todo natural n,

∑_{d|n} φ(d) = n.

Este teorema segue facilmente da fórmula que provamos para φ(n) na seção anterior. Daremos entretanto uma demonstração bijetiva.

Dem: Considere as n frações

\frac{0}{n}, \frac{1}{n}, …, \frac{n − 1}{n}

e simplifique cada uma delas: obtemos assim, para cada d|n, φ(d) frações com denominador d, donde segue a identidade do enunciado.

Mais formalmente, dado \overline{a} ∈ ℤ/(n), sejam d = n/(n, a) e a′ = a/(n, a). Claramente \overline{a′} ∈ (ℤ/(d))^{∗} e definimos assim uma função de ℤ/(n) para a união disjunta dos conjuntos (ℤ/(d))^{∗}, onde d varia sobre os divisores de n. A inversa desta função leva \overline{a′} ∈ (ℤ/(d))^{∗} em \overline{a}, a = na′/d, donde a função é uma bijeção. ■

O processo de construir g a partir de f como

g(n) = ∑_{d|n} f(d)

é bastante comum em teoria dos números. Seria interessante poder inverter esta identidade para escrever f a partir de g. O teorema anterior nos mostra que se fazemos f = φ na equação acima temos g(n) = n; invertendo esta identidade teríamos uma fórmula para φ. O objetivo desta seção é mostrar como fazer este tipo de inversão.

Definimos a função de Möbius μ : ℕ^{∗} → ℤ por

μ(n) = \begin{cases}(−1)^{m}, & se n = p_{1}p_{2} ⋯ p_{m}, com p_{1}, p_{2}, ⋯, p_{m} primos distintos, \\ 0, & se n tem algum fator primo repetido em sua fatoração. \end{cases}

Assim, μ(1) = μ(6) = μ(10) = 1, μ(2) = μ(3) = μ(5) = μ(7) = −1 e μ(4) = μ(8) = μ(9) = 0. Lema 4.2: Para todo inteiro positivo n temos

∑_{d|n} μ(d) = \begin{cases}1, & se n = 1, \\ 0, & se n > 1. \end{cases}

Dem: O caso n = 1 é trivial. Se n > 1, seja p um divisor primo de n e seja n = p^{e}n′ com p ∤ n′. Temos

∑_{d|n} μ(d) = ∑_{d|n,p∤d}μ(d) + ∑_{d|n,p|d,p^{2}∤d}μ(d) + ∑_{d|n,p^{2}|d} μ(d)

= ∑_{d|n′} μ(d) + ∑_{d′|n′} μ(pd′) + 0

= ∑_{d|n′} μ(d) − ∑_{d′|n′} μ(d′)

= 0.

■

Teorema 4.3: (Fórmula de inversão de Möbius) Se para todo n > 0 temos

g(n) = ∑_{d|n} f(d)

então

f(n) = ∑_{d|n} μ(n/d)g(d).

Observe que a fórmula do corolário 1.16 para φ(n) segue facilmente dos dois teoremas acima. Dem: Basta provar que

f(n) = ∑_{d|n} μ(n/d) (∑_{d′|d} f(d′)) .

Mas, escrevendo d′′ = n/d e m = n/d′ temos

∑_{d|n} μ(n/d) (∑_{d′|d} f(d′)) = ∑_{m|n} (∑_{d′′|m} μ(d′′)) f(n/m) = f(n).

■

Teorema 4.4: (Segunda fórmula de inversão de Möbius) Sejam f e g funções reais com domínio (0, +∞) tais que f(t) = g(t) = 0 para todo t < 1. Se

g(x) = ∑_{k=1}^{∞} f (\frac{x}{k}) = ∑_{1=k}^{⌊x⌋} f (\frac{x}{k})

para todo x então então

f(x) = ∑_{k=1}^{∞} μ(k)g (\frac{x}{k}) = ∑_{1=k} ⌊x⌋μ(k)g (\frac{x}{k}) .

Dem: Basta provar que

f(x) = ∑_{k=1}^{∞} μ(k) (∑_{r=1}^{∞} f (\frac{x}{kr})) ,

mas, tomando m = kr a última soma é igual a

∑_{m=1}^{∞} ((∑_{k|m} μ(k)) f (\frac{x}{m}))

que pelo lema é igual a f(x). ■

Apesar de não estar relacionada com o resto da nossa discussão, não podemos deixar de mencionar a seguinte conjectura.

Conjectura 4.5: (Hipótese de Riemann) Se α > 1/2 então

lim_{n→∞} \frac{1}{n^{α}} ∑_{1≤m}^{n} μ(m) = 0.

Esta é uma das formulações da famosa hipótese de Riemann, um dos problemas em aberto mais importantes da matemática.

Podemos reenunciar esta conjectura assim: seja f : (0, +∞) → ℝ definida por f(t) = 0 se t < 1 e

∑_{k=1}^{∞} f(t/k) = 1, se t ≥ 1

então, para todo α > 1/2,

lim_{t→∞} \frac{f(t)}{t^{α}} = 0.

De fato, pela segunda fórmula de inversão de Möbius temos

f(t) = ∑_{m=1}^{⌊t⌋} μ(m).

5 Bases

A notação usual para naturais é a chamada base 10, com algarismos 0, …, 9. Isto significa, por exemplo, que

196883 = 1 · 10^{5} + 9 · 10^{4} + 6 · 10^{3} + 8 · 10^{2} + 8 · 10^{1} + 3 · 10^{0}.

O teorema abaixo mostra como escrever qualquer natural em qualquer base d.

Teorema 5.1: Seja n ≥ 0 e d > 1. Então existe uma única seqüência a_{0}, …, a_{k}, … com as seguintes propriedades:

(a)

1. para todo k, 0 ≤ a_{k} < d,

2. existe m tal que se k ≥ m então a_{k} = 0,

3. n = ∑_{k} a_{k}d^{k}.

Dem: Escrevemos n = n_{0} = n_{1}d + a_{0}, 0 ≤ a_{0} < d, n_{1} = n_{2}d + a_{1}, 0 ≤ a_{1} < d, e em geral n_{k} = n_{k+1}d + a_{k}, 0 ≤ a_{k} < d. Nossa primeira afirmação é que n_{k} = 0 para algum valor de k. De fato, se n_{0} < d^{m} então n_{1} < d^{m−1} e mais geralmente, por indução, n_{k} < d^{m−k}; fazendo k ≥ m temos n_{k} < 1 donde n_{k} = 0. Segue daí que a_{k} = 0 para k ≥ m. A identidade do item (c) é facilmente demonstrada por indução.

Para a unicidade, suponha ∑_{k} a_{k}d^{k} = ∑_{k} b_{k}d^{k}. Se as seqüências a_{k} e b_{k} são distintas existe um menor índice, digamos j, para o qual a_{j} ≠ b_{j}. Podemos escrever a_{j} + ∑_{k>j} a_{k}d^{k−j} = b_{j} + ∑_{k>j} b_{k}d^{k−j} donde a_{j} ≡ b_{j} (mod d), o que é uma contradição. ■

Às vezes é interessante considerar expansões não apenas em outras bases mas com outros conjuntos de algarismos (veremos um exemplo disso no último capítulo). Por exemplo, podemos preferir algarismos negativos pequenos a algarismos positivos grandes e assim um bom conjunto de algarismos na base 10 seria

−4, −3, −2, −1, 0, 1, 2, 3, 4, 5.

Desta forma, escrevemos 13 = 1 · 10 + 3 mas escrevemos 9 = 1 · 10 − 1 e 64 = 1 · 10^{2} − 4 · 10 + 4. Generalizando, os algarismos na base d seriam os inteiros a com −d/2 < a ≤ d/2, ou seja,

a = −⌊(d − 1)/2⌋, −⌊(d − 1)/2⌋ + 1, …, −1, 0, 1, …, ⌊d/2⌋ − 1, ⌊d/2⌋.

Este conjunto de algarismos nos permite enunciar um teorema análogo ao anterior, com a diferença que agora números negativos não precisam ser tratados em separado.

Teorema 5.2: Seja n ∈ ℤ e d > 2. Então existe uma única seqüência a_{0}, …, a_{k}, … com as seguintes propriedades:

(a)

1. para todo k, −d/2 < a_{k} ≤ d/2,

2. existe m tal que se k ≥ m então a_{k} = 0,

3. n = ∑_{k} a_{k}d^{k}.

Dem: Escrevemos n = n_{0} = n_{1}d + a_{0}, −d/2 < a_{0} ≤ d/2, n_{1} = n_{2}d + a_{1}, −d/2 < a_{1} ≤ d/2, e em geral n_{k} = n_{k+1}d + a_{k}, −d/2 < a_{k} ≤ d/2. Novamente, nossa primeira afirmação é que n_{k} = 0 para algum valor de k. De fato, se

−d^{m}/2 < n_{0} ≤ d^{m}/2

então, por indução,

−d^{m−k}/2 < n_{k} ≤ d^{m−k}/2;

fazendo k ≥ m temos n_{k} = 0. Segue daí que a_{k} = 0 para k ≥ m. A identidade do item (c) e a unicidade são demonstradas como no teorema anterior. ■

Pode-se estudar representações na base d com outros conjuntos X de algarismos. Algumas condições mínimas para que X seja um conjunto de algarismos interessante são que 0 ∈ X, que X seja um sistema completo de resíduos e que o mdc dos elementos de X seja 1.

6 Corpos e polinômios

Um grupo é um conjunto G munido de uma operação ∗ : G × G → G e um elemento e ∈ G com as seguintes propriedades:

1. para quaisquer a, b, c ∈ G, a ∗ (b ∗ c) = (a ∗ b) ∗ c.

2. para qualquer a ∈ G, a ∗ e = e ∗ a = a,

3. para qualquer a ∈ G existe b ∈ G com a ∗ b = b ∗ a = e.

Se além disso tivermos a ∗ b = b ∗ a para quaisquer a, b ∈ G dizemos que o grupo é comutativo ou abeliano. Quando a operação ∗ se chama + dizemos que G é um grupo aditivo e chamamos o elemento neutro e de 0. Se a operação se chama · chamamos G de grupo multiplicativo e denotamos o elemento neutro e por 1. Assim, ℤ/(n) é um grupo abeliano aditivo e (ℤ/(n))^{∗} é um grupo abeliano multiplicativo.

Um anel comutativo com unidade é um grupo abeliano aditivo A munido de uma segunda operação · : A × A → A satisfazendo a · (b · c) = (a · b) · c, a · (b + c) = (a · b) + (a · c), a · b = b · a para quaisquer a, b, c ∈ A e um elemento 1 ∈ A com 1 · a = a para todo a ∈ A. Assim, ℤ/(n) é um anel comutativo com unidade.

Um corpo é um anel comutativo com unidade onde para todo a ∈ K com a ≠ 0 existe b ∈ K com a · b = 1. Repetindo então, K é munido de duas operações + : K × K → K e · : K × K → K, de uma função − : K → K e dois elementos especiais distintos chamados 0 e 1 satisfazendo as seguintes propriedades:

a + (b + c) = (a + b) + c
a + 0 = a

a + (−a) = 0
a + b = b + a
a(b + c) = ab + ac
a(bc) = (ab)c
a1 = a
ab = ba

e onde para todo a ∈ K, a ≠ 0 existe b ∈ K com

ab = 1.

Os exemplos mais conhecidos de corpos são ℚ, ℝ e ℂ. Vimos no capítulo anterior que ℤ/(p) também é um corpo se p é primo; veremos a seguir outros exemplos de corpos finitos.

Dado um corpo K, definimos o anel comutativo com unidade K[x] como sendo o conjunto das expressões da forma P = a_{0} + a_{1}x + a_{2}x^{2} + ⋯ + a_{n}x^{n}, chamados de polinômios com coeficientes em K. Observe que x é um símbolo formal e não um elemento de K; apesar disso, cada polinômio define uma função polinomial

P : K → K
c ↦ P (c) = a_{0} + a_{1}c + a_{2}c^{2} + ⋯ + a_{n}c^{n}

também chamada de P. A distinção entre um polinômio e uma função polinomial é bem ilustrada pelo polinômio P = x^{p} − x ∈ (ℤ/(p))[x]: este polinômio é não nulo pois seus coeficientes são não nulos mas para todo x ∈ ℤ/(p) temos P (x) = 0 pelo pequeno teorema de Fermat.

Se P = ∑ a_{i}x^{i} e Q = ∑ b_{i}x^{i} são polinômios definimos P +Q = ∑(a_{i} +b_{i})x^{i} e P Q = ∑ c_{i}x^{i} onde c_{k} = ∑_{i+j=k} a_{i}b_{j}. Definimos o grau deg P de um polinômio P = a_{0}+a_{1}x+a_{2}x^{2}+⋯+a_{n}x^{n} como sendo n se a_{n} ≠ 0 mas a_{m} = 0 para m > n; definimos ainda o grau do polinômio 0 como sendo −∞.

Lema 6.1: Para quaisquer polinômios P e Q temos deg(P Q) = deg(P) + deg(Q) e deg(P + Q) ≤ max{deg(P), deg(Q)}.

Dem: Fácil. ■

Observe que definimos −∞ < n e (−∞) + (−∞) = −∞ + n = −∞ para todo n. Temos uma forma de divisão com resto em K[x].

Teorema 6.2: Sejam A, B ∈ K[x], B ≠ 0. Então existem únicos polinômios Q, R ∈ K[x] com A = QB + R e deg R < deg B.

Dem: A demonstração é feita por indução no grau de A. Se deg(A) < deg(B), tomamos Q = 0, R = A. Caso contrário, sejam n e m os graus de A e B e sejam a e b os coeficientes de mais alto grau destes polinômios. Podemos escrever A = (a/b)x^{n−m}B + A_{1}, com deg(A_{1}) < deg(A). Pela hipótese de indução, temos A_{1} = Q_{1}B + R, com deg(R) < deg(B). Fazendo Q = (a/b) + x^{n−m} + Q_{1} temos A = QB + R. A unicidade segue facilmente do lema anterior.

■

A demonstração acima nada mais é do que o algoritmo usual de divisão usual. Um polinômio P tem raiz a (i.e., P (a) = 0) se e somente se (x − a)|P. Mais geralmente, P (a) é o resto da divisão de P por x − a.

Proposição 6.3: Um polinômio P não nulo de grau n tem no máximo n raízes.

Dem: A demonstração é feita por indução em n = deg(P); os casos n = 0 e n = 1 são triviais. Se P tivesse n + 1 raízes distintas a_{1}, …, a_{n+1} então P seria múltiplo de (x − a_{n+1}); P/(x − a_{n+1}) teria grau n − 1 e raízes a_{1}, …, a_{n}, contradizendo a hipótese de indução. ■

A partir da divisão com resto podemos repetir muitas das construções feitas para ℤ no capítulo anterior; dizemos que K[x] (assim como ℤ) é um domínio euclidiano. Daremos um esboço desta teoria; estes resultados não serão necessários para acompanhar o resto do livro.

Definimos A|B se existe C com AC = B e dizemos que um polinômio P de grau maior que n > 0 é irredutível se seus divisores todos têm grau 0 ou n (assim generalizando o conceito de número primo). O conceito de mdc também se generaliza, como indicado na proposição abaixo.

Proposição 6.4: Dados polinômios não nulos A, B ∈ K[x] existe um único D ∈ K[x] (a menos de multiplicação por constante) tal que D|A, D|B e, para todo C ∈ K[x], se C|A e C|B então C|D. Além disso existem E, F ∈ ℤ com D = AE + BF.

Dem: Definimos I(A, B) = {AE +BF; E, F ∈ K[x]} e tomamos D de grau mínimo dentre os elementos não nulos de I(A, B); o resto da demonstração é análoga à da proposição 1.1. ■

Polinômios irredutíveis são como números primos: um produto de polinômios só é múltiplo de um polinômio irredutível se um dos fatores o for.

Proposição 6.5: Sejam P um polinômio irredutível e sejam A_{1}, … A_{m} ∈ K[x]. Se P |(A_{1} ⋯ A_{m}) então P |A_{i} para algum i, 1 ≤ i ≤ n.

Dem: Análoga à do corolário 1.3. ■ Temos também um teorema de fatoração única.

Teorema 6.6: Todo polinômio pode ser fatorado como um produto de polinômios irredutíveis; esta fatoração é única a menos da ordem dos fatores.

Dem: Análoga à do teorema fundamental da aritmética, usando a proposição acima e fazendo indução no grau do polinômio. ■

Os exemplos mais evidentes de polinômios irredutíveis são os da forma x − a, a ∈ K. Quando estes são os únicos polinômios irredutíveis dizemos que o corpo é algebricamente fechado. Polinômios de grau 2 e 3 são irredutíveis se e somente se não têm raízes.

O pequeno teorema de Fermat também admite uma formulação em termos de polinômios.

Teorema 6.7: Seja p primo; em (ℤ/(p))[x] temos

x^{p} − x = x(x − 1)(x − 2) ⋯ (x − (p − 1)).

Dem: Os dois polinômios dos dois lados da equação têm grau p e o coeficiente de x^{p} é 1 nos dois casos. Assim, a diferença tem grau menor do que p mas se anula em p pontos: 0, 1, … p − 1. Pelo corolário anterior, esta diferença deve ser o polinômio zero. ■

A partir do teorema acima temos uma nova prova do teorema de Wilson: x^{p−1} − 1 = (x − 1)(x − 2) ⋯ (x − (p − 1)) em (ℤ/(p))[x], mas o coeficiente independente é −1 do lado esquerdo e (p − 1)! do lado direito.

Podemos definir congruências em K[x]:

A ≡ B (mod P) ⟺ P |(B − A).

As propriedades básicas de congruências podem ser traduzidas para este novo contexto e podemos definir um quociente K[x]/(P) da mesma forma como definimos ℤ/(n); demonstra-se que K[x]/(P) é um corpo exatamente quando P é irredutível.

Prometemos que veríamos outros exemplos de corpos finitos além de ℤ/(p): o parágrafo acima ensina que podemos construir tais corpos como (ℤ/(p))[x]/(P) onde P ∈ (ℤ/(p))[x] é irredutível. Por exemplo, o polinômio x^{2} + x + 1 é irredutível em (ℤ/(2))[x] o que nos permite construir um corpo de 4 elementos: 0, 1, x e x+1. As operações em ℤ/(2) e a relação x^{2} = x+1 definem as operações neste corpo (denotamos x + 1 por x′):

De fato existem em (ℤ/(p))[x] polinômios irredutíveis de qualquer grau e todo corpo finito pode ser construido desta forma. Enunciaremos sem demonstração um teorema que classifica os corpos finitos.

Teorema 6.8: Existe um corpo finito com q elementos se e somente se q é da forma p^{n} para algum primo p e algum inteiro positivo n. Além disso, dados dois corpos finitos K_{1} e K_{2} com o mesmo número de elementos existe uma única bijeção f : K_{1} → K_{2} com f(a + b) = f(a) + f(b) e f(ab) = f(a)f(b) para quaisquer a, b ∈ K_{1}.

Uma bijeção como a descrita acima é chamada de isomorfismo e dois corpos são ditos isomorfos se existe entre eles um isomorfismo; a idéia é que corpos isomorfos são iguais a menos dos nomes dos elementos. Veremos mais tarde outras formas mais concretas de construir corpos finitos.

7 Ordens e raízes primitivas

Dados n, a ∈ ℤ com n > 0 e (a, n) = 1, definimos a ordem de a módulo n, denotada por ord_{n} a, como sendo o menor inteiro positivo t com a^{t} ≡ 1 (mod n). Analogamente, se K for um corpo finito e a ∈ K, a ≠ 0, definimos a ordem de a em K, denotada por ord_{K} a, como sendo o menor inteiro positivo t com a^{t} = 1 ∈ K; temos ord_{p} a = ord_{ℤ/(p)} a.

Claramente a^{e} ≡ a^{e′} (mod n) se e somente se e ≡ e′ (mod ord_{n} a); pelo teorema de Euler, ord_{n} a|φ(n).

Dizemos que a é uma raiz primitiva módulo n se ord_{n} a = φ(n). Analogamente, dizemos que a é uma raiz primitiva em K se ord_{K} a = q − 1, onde q = |K| é o número de elementos de K. Por exemplo, 2 é raiz primitiva módulo 5 mas 2 não é raiz primitiva módulo 7 (2^{3} ≡ 1 (mod 7)). Também é fácil verificar que não existe raiz primitiva módulo 8 pois se x é ímpar então x^{2} ≡ 1 (mod 8). Podemos também dizer que a é raiz primitiva se a função

ℤ/(φ(n)) → (ℤ/(n))^{∗}
r ↦ a^{r}

ou

ℤ/(q − 1) → K^{∗}
r ↦ a^{r}

é injetora. Como o domínio e contradomínio são conjuntos finitos com o mesmo número de elementos, a função é injetora se e somente se ela é sobrejetora. Podemos assim dizer que a é uma raiz primitiva módulo n se e somente se para todo b ∈ (ℤ/(n))^{∗} (ou para todo b ∈ K^{∗}) existe r com a^{r} = b.

Um corolário desta caracterização de raízes primitivas é que se a é raiz primitiva módulo n e m|n então a é raiz primitiva módulo m. O objetivo da próxima seção é caracterizar os valores de n para os quais existe uma raiz primitiva módulo n. Nesta seção mostraremos que todo corpo finito admite raiz primitiva; em particular existe raiz primitiva módulo p para qualquer primo p.

Precisamos primeiro de uma versão do pequeno teorema de Fermat para corpos finitos:

Teorema 7.1: Se K é um corpo finito e q = |K| então a^{q} − a = 0 para todo a ∈ K.

Dem: Se a = 0 o teorema vale; vamos supor a partir de agora a ≠ 0. Sejam b_{1}, … b_{q−1} os elementos não nulos de K. Os elementos ab_{1}, … ab_{q−1} são todos não nulos e distintos, logo são os próprios b_{1}, … b_{q−1}, apenas permutados. Assim

b_{1} · b_{2} ⋯ b_{q−1} = (ab_{1})(ab_{2}) ⋯ (ab_{q−1})
= a^{q−1}(b_{1} · b_{2} ⋯ b_{q−1})

e a^{q−1} = 1. ■

Segue deste teorema que ord_{K} a|q − 1, analogamente ao que já sabiamos para ℤ/(n). A partir do que vimos sobre polinômios temos também que

x^{q} − x = x(x − b_{1}) ⋯ (x − b_{q−1})

em K[x].

Teorema 7.2: Se K é um corpo finito então existe raiz primitiva em K.

Dem: Seja d um divisor de q − 1: definimos N(d) como o número de elementos de K^{∗} de ordem d. Claramente ∑_{d|q−1} N(d) = q − 1.

Se N(d) > 0, seja a_{d} um elemento de K com ord_{K} a_{d} = d: os elementos 1, a_{d}, a_{d}^{2}, … a_{d}^{d−1} são raízes do polinômio x^{d} − 1 = 0. Como este polinômio tem no máximo d raízes, estas são todas as raízes. Assim, os elementos de K de ordem d são precisamente a_{d}^{r}, r ∈ (ℤ/(d))^{∗}. Assim os únicos valores possíveis para N(d) são 0 e φ(d). Mas como ∑_{d|q−1} N(d) = ∑_{d|q−1} φ(d) = q − 1, temos N(d) = φ(d) para todo d|q − 1. Em particular N(q − 1) > 0 e existem raízes primitivas.

■

Apesar de existirem raízes primitivas módulo p para todo primo p não existe uma fórmula simples para obter uma raiz primitiva. Por outro lado, conjectura-se que todo inteiro que não é um quadrado é raiz primitiva para infinitos valores de p (conjectura de Artin).

Corolário 7.3: Dados x ∈ K^{∗} e um inteiro positivo k existe y ∈ K^{∗} com y^{k} = x se e somente se x^{(q−1)/ mdc(k,q−1)} = 1, onde q = |K|.

Dem: Se x = y^{k} então x^{(q−1)/ mdc(k,q−1)} = (y^{q−1})^{k/ mdc(k,q−1)} = 1 pois y^{q−1} = 1. Suponha agora que x^{(q−1)/ mdc(k,q−1)} = 1. Sejam a uma raiz primitiva de K e r ∈ ℤ com x = a^{r}. Temos (a^{r})^{(q−1)/ mdc(k,q−1)} = 1 donde mdc(k, q − 1) | r e portanto existem inteiros u, v com ku + (q − 1)v = r. Assim x = a^{r} = a^{ku+(q−1)v} = (a^{u})^{k} · (a^{q−1})^{v} = y^{k} onde y = a^{u}. ■

8 Raízes primitivas em ℤ/(n)

Nesta seção caracterizaremos os inteiros n para os quais existe raiz primitiva módulo n.

Lema 8.1: Sejam p um número primo e a ∈ ℤ uma raiz primitiva módulo p. Então a ou a′ = a + p é raiz primitiva módulo p^{2}.

Dem: Pelo binômio de Newton, a′^{p} = (a + p)^{p} ≡ a^{p} (mod p^{2}). Sem perda de generalidade, podemos supor a^{p} ≢ a (mod p^{2}) ou a^{p−1} ≢ 1 (mod p^{2}), donde ord_{p^{2}} a ≠ p − 1. Como p − 1 = ord_{p} a | ord_{p^{2}} a | φ(p^{2}) = p(p − 1) isto implica em ord_{p^{2}} a = p(p − 1). ■

Lema 8.2: Se p é um número primo ímpar e a é raiz primitiva módulo p^{2} então a é raiz primitiva módulo p^{k} para todo k > 2, k ∈ ℤ.

Dem: Temos a^{p−1} ≡ 1 (mod p), mas a^{p−1} ≢ 1 (mod p^{2}), donde a^{p−1} = 1 + b_{0}p com b_{0} ≢ 0 (mod p). Vamos mostrar por indução que a^{p^{j}(p−1)} = 1 + b_{j}p^{j+1} com b_{j} ≡ b_{0} (mod p). Podemos escrever

a^{p^{j+1}(p−1)} = (a^{p^{j}(p−1)})^{p}

= (1 + b_{j}p^{j+1})^{p}

= 1 + pb_{j}p^{j+1} + \binom{p}{2}b_{j}^{2}p^{2j+2} + ⋯ + b_{j}^{p}p^{pj+p}

= 1 + b_{j}(1 + \binom{p}{2}b_{j}p^{j} + ⋯ b_{j}^{p−1}p^{(p−1)j+p−2})p^{j+2}

= 1 + b_{j+1}p^{j+2}

com b_{j+1} ≡ b_{j} (mod p) pois o parêntesis na penúltima linha é da forma 1+ um múltiplo de p. Esta última afirmação segue da positividade dos expoentes de p exceto no caso j = 0; neste caso o expoente do primeiro termo não trivial é zero mas temos \binom{p}{2} ≡ 0 (mod p) pois p > 2 (é neste ponto que precisamos da hipótese de p ser ímpar). O lema segue de a^{(p−1)p^{k−2}} ≢ 1 (mod p^{k}) por indução, pois teremos (p − 1)p^{k−2} = ord_{p^{k−1}} a | ord_{p^{k}} a | φ(p^{k}) = (p − 1)p^{k−1}, donde ord_{p^{k}} a = (p − 1)p^{k−1}. ■

Exemplo: 2 é raiz primitiva módulo 5^{k}, ∀ k ∈ ℕ. De fato, 2 é raiz primitiva módulo 5, e, como 2^{4} = 16 ≠ 1 (módulo 25), 2 é raiz primitiva módulo 25 = 5^{2} (como no Lema 8.1). Portanto, pelo Lema 8.2, 2 é rais primitiva módulo 5^{k}, ∀ k ∈ ℕ.

Problema resolvido: Mostre que existe n natural tal que os mil últimos dígitos de 2^{n} pertencem a {1, 2}.

Solução: Observamos inicialmente que para todo k ∈ ℕ existe um número m_{k} de k algarismos, todos 1 ou 2, divisível por 2^{k}. De fato, m_{1} = 2 e m_{2} = 12 satisfazem o enunciado.

Seja m_{k} = 2^{k} · r_{k}, r_{k} ∈ ℕ. Se r_{k} é par, tome m_{k+1} = 2 · 10^{k} + m_{k} = 2^{k+1}(5^{k} + r_{k}/2), e se r_{k} é ímpar, tome m_{k+1} = 10^{k} + m_{k} = 2^{k+1}(5^{k} + r_{k})/2.

Como m_{1000} ≡ 2 (módulo 10), 5 não divide r_{1000} = m_{1000}/2^{1000}. Como 2 é raiz primitiva módulo 5^{1000}, existe k ∈ ℕ com 2^{k} ≡ r_{1000} (módulo 5^{1000}). Logo 2^{k} = b · 5^{1000} + r_{1000}, para algum b ∈ ℕ. Portanto, 2^{k+1000} = b · 10^{1000} + 2^{1000} · r_{1000} = b · 10^{1000} + m_{1000}, e as 1000 últimas casas de 2^{k+1000} são as 1000 casas de m_{1000}, que pertencem todas a {1, 2}. ■

Lema 8.3: Seja n > 1. O número de soluções para a congruência x^{2} ≡ 1 (mod n) é:

1. 1 se n = 2,

2. 2 se n = 4,

3. 4 se n = 2^{k}, k > 2,

4. 2 se n = p^{k}, p um primo ímpar,

5. 2^{m+i} se n = 2^{k}p_{1}^{e_{1}} ⋯ p_{m}^{e_{m}}, onde i = 0 se k ≤ 1, i = 1 se k = 2 e i = 2 se k > 2.

Dem: Os itens (a) e (b) são verificáveis diretamente. As quatro soluções no item (c) são 1, 2^{k−1} − 1, 2^{k−1} + 1 e 2^{k} − 1. De fato, é fácil verificar que estes quatro valores são soluções da congruência. Por outro lado, para que a seja solução da congruência devemos ter 2^{k}|(a + 1)(a − 1) = a^{2} − 1; portanto a deve ser ímpar. Um dentre a − 1 e a + 1 deve ser da forma 2b, b ímpar. Assim o outro deve ser múltiplo de 2^{k−1}, o que diz que a deve ter um dos quatro valores acima. Analogamente para o item (d), apenas um dentre a−1 e a+1 é múltiplo de p, o que só permite as soluções 1 e n − 1.

Para o item (e) usamos os itens anteriores e o teorema chinês dos restos: a é solução da congruência acima se e somente se a satisfaz a^{2} ≡ 1 (mod 2^{k}) e a^{2} ≡ 1 (mod p_{i}^{e_{i}}) para cada i. Assim, o número de soluções módulo n é o produto do número de soluções módulo 2^{k}, p_{1}^{e_{1}}, …, p_{m}^{e_{m}}, o que nos dá a fórmula do item (e). ■

Teorema 8.4: Um inteiro n > 1 admite raiz primitiva se e somente se n = 2, n = 4 ou n é da forma p^{k} ou 2p^{k}, onde p é um primo ímpar, admite raiz primitiva.

Dem: Os casos n = 2 e n = 4 podem ser verificados diretamente. A existência de uma raiz primitiva módulo p^{k} (p um primo ímpar) segue dos dois primeiros lemas desta seção. Para o caso 2p^{k}, seja a uma raiz primitiva módulo p^{k}: a ou a + p^{k}, aquele que for ímpar, será uma raiz primitiva módulo 2p^{k} pois φ(2p^{k}) = φ(p^{k}).

Se n não for de uma destas formas, o lema anterior garante que a congruência x^{2} ≡ 1 (mod n) admite mais de duas soluções. Por outro lado, a existência de uma raiz primitiva a módulo n garante que a congruência x^{2} ≡ 1 (mod n) só tem as soluções 1 e n − 1. De fato, qualquer solução pode ser escrita da forma a^{k} para algum k e nossa congruência torna-se a^{2k} ≡ 1 (mod n) ou 2k ≡ 0 (mod φ(n)), que só tem as soluções k = 0 (a^{k} = 1) e k = (φ(n))/2 (a^{k} ≡ n − 1 (mod n)).

Outra demonstração, sem usar o lema anterior, consiste em observar que se n não for de uma destas duas formas então n = n_{1}n_{2}, com n_{1}, n_{2} ≥ 3 e mdc(n_{1}, n_{2}) = 1. Temos então a^{φ(n)/2} ≡ 1 (mod n) para todo a inteiro com mdc(a, n) = 1, pois φ(n_{1}) | φ(n)/2 e φ(n_{2}) | φ(n)/2. ■

9 A lei da reciprocidade quadrática

A lei de Gauss de reciprocidade quadrática afirma que se p e q são primos há uma relação direta entre p ser quadrado módulo q e q ser quadrado módulo p. Este teorema fornece um rápido algoritmo para determinar se a é quadrado módulo p onde a é um inteiro e p um número primo.

Definição 9.1: Seja p um primo e a um inteiro. Definimos o símbolo de Lagrange (\frac{a}{p}) por

(\frac{a}{p}) = \begin{cases}0 & se p divide a \\ −1 & se a não é quadrado módulo p \\ 1 & se p ∤ a e a é quadrado módulo p. \end{cases}

Proposição 9.2: Seja p um primo ímpar e a ∈ ℤ tal que p ∤ a. Então (\frac{a}{p}) ≡ a^{\frac{p−1}{2}} (mod p).

Dem: Sabemos que se p ∤ a então a^{p−1} ≡ 1 (mod p), ou seja, X^{p−1} − 1 tem como raízes 1, 2, …, p − 1 em ℤ/(p). Por outro lado, X^{p−1} − 1 = (X^{\frac{p−1}{2}} − 1)(X^{\frac{p−1}{2}} + 1). Se existe b ∈ ℤ tal que a ≡ b^{2} (mod p) então a^{\frac{−1}{2}} ≡ b^{p−1} ≡ 1 (mod p); ou seja, (\frac{a}{p}) = 1 ≡ a^{\frac{p−1}{2}} (mod p). Como X^{2} ≡ Y^{2} (mod p) ⇔ X ≡ ±Y (mod p), há pelo menos \frac{p−1}{2} quadrados em (ℤ/(p))^{∗}, logo os quadrados são exatamente as raízes de X^{\frac{p−1}{2}} − 1 em ℤ/(p), donde os não quadrados são exatamente as raízes de X^{\frac{p−1}{2}} + 1, ou seja, se (\frac{b}{p}) = −1 então b^{\frac{p−1}{2}} ≡ −1 (mod p). ■

Corolário 9.3: Se p é primo ímpar então (\frac{−1}{p}) = (−1)^{\frac{p−1}{2}} .

Vamos agora reinterpretar a Proposição 1. Seja a ∈ (ℤ/(p))^{∗}. Para cada j = 1, 2, …, \frac{p−1}{2} escrevemos a · j como ε_{j}m_{j} com ε_{j} ∈ \{−1, 1\} e m_{j} ∈ \{1, 2, …, \frac{p−1}{2}\}. Se m_{i} ≠ m_{j} temos a · i = a · j ou a · i = −a · j; a primeira possibilidade implica i = j e a segunda é impossível. Assim, se i ≠ j temos m_{i} ≠ m_{j} donde \{m_{1}, m_{2}, …, m_{\frac{p−1}{2}} \} = \{1, 2, …, \frac{p−1}{2}\}. Assim

(\frac{a}{p}) ≡ a^{\frac{p−1}{2}}

= \frac{(a · 1)(a · 2) ⋯ (a · \frac{p−1}{2})}{1 · 2 ⋯ \frac{p−1}{2}}

≡ \frac{ε_{1}ε_{2} ⋯ ε_{\frac{p−1}{2}} m_{1}, m_{2}, …, m_{\frac{p−1}{2}}}{1 · 2 ⋯ \frac{p−1}{2}}

= ε_{1}ε_{2} ⋯ ε_{\frac{p−1}{2}} (mod p)  (1)

donde (\frac{a}{p}) = ε_{1}ε_{2} … ε_{\frac{p−1}{2}} , pois ambos pertencem a \{−1, 1\}. Assim, (\frac{a}{p}) = (−1)^{m} onde m é o número de elementos j de \{1, 2, …, \frac{p−1}{2}\} tais que ε_{j} = −1. Como primeira conseqüência deste fato temos o seguinte resultado.

Proposição 9.4: Se p é um primo ímpar então

(\frac{2}{p}) = (−1)^{\frac{p^{2}−1}{8}} = \begin{cases}1, & se p ≡ ±1 (mod 8), \\ −1, & se p ≡ ±3 (mod 8). \end{cases}

Dem: Se p ≡ 1 (mod 4), digamos p = 4k + 1, temos \frac{p−1}{2} = 2k. Como 1 ≤ 2j ≤ \frac{p−1}{2} para j ≤ k e \frac{p−1}{2} < 2j ≤ p − 1 para k + 1 ≤ j ≤ 2k, temos

(\frac{a}{p}) = (−1)^{k} = \begin{cases}1, & se p ≡ 1 (mod 8), \\ −1, & se p ≡ 5 (mod 8). \end{cases}

Se p ≡ 3 (mod 4), digamos p = 4k + 3, temos \frac{p−1}{2} = 2k + 1. Para 1 ≤ j ≤ k temos 1 ≤ 2j ≤ \frac{p−1}{2} e para k + 1 ≤ j ≤ 2k + 1 temos \frac{p−1}{2} < 2j ≤ p − 1, donde

(\frac{a}{p}) = (−1)^{k+1} = \begin{cases}−1, & se p ≡ 3 (mod 8), \\ 1, & se p ≡ 7 (mod 8). \end{cases}

■

Teorema 9.5: (Lei de reciprocidade quadrática) Sejam p e q primos ímpares. Então (\frac{p}{q}) = (−1)^{(p−1)(q−1)/4}(\frac{q}{p}).

Dem: Na notação acima, com a = q, para cada j ∈ P, onde

P = {1, 2, …, (p − 1)/2},

temos que ε_{j} = −1 se e só se existe y ∈ ℤ tal que −(p − 1)/2 ≤ qj − py < 0. Tal y deve pertencer a Q, onde

Q = {1, 2, …, (q − 1)/2}.

Assim, temos que (\frac{q}{p}) = (−1)^{m} onde m = |X| e

X = {(x, y) ∈ P × Q | −(p − 1)/2 ≤ qx − py < 0};

note que qx − py nunca assume o valor 0. Analogamente, (\frac{p}{q}) = (−1)^{n}, onde n = |Y | e

Y = {(x, y) ∈ P × Q | 0 < qx − py ≤ (q − 1)/2} .

Daí segue que (\frac{p}{q})(\frac{q}{p}) = (−1)^{k} onde k = m + n = |Z| onde

Z = {(x, y) ∈ P × Q | −(p − 1)/2 ≤ qx − py ≤ (q − 1)/2}

pois qx − py nunca assume o valor 0. Temos k = |C| − |A| − |B| onde C = P × Q,

A = {(x, y) ∈ C | qx − py < −(p − 1)/2},
B = {(x, y) ∈ C | qx − py > (q − 1)/2}.

Como |C| = (p − 1)(q − 1)/4, basta mostrar que |A| = |B|. Mas f : C → C definida por f(x, y) = (((p + 1)/2) − x, ((q + 1)/2) − y) define uma bijeção entre A e B. ■

10 Extensões quadráticas de corpos finitos

Sejam p primo e d um inteiro que não seja quadrado perfeito. O anel (ℤ/(p))[\sqrt{d}] é o conjunto

\{a + b\sqrt{d}, a, b ∈ ℤ/(p)\}

onde

(a + b\sqrt{d}) + (ã + b̃\sqrt{d}) = (a + ã) + (b + b̃)\sqrt{d}
(a + b\sqrt{d})(ã + b̃\sqrt{d}) = (aã + dbb̃) + (ab̃ + ãb)\sqrt{d}.

Por definição,

a + b\sqrt{d} = ã + b̃\sqrt{d} ⇔ a = ã, b = b̃.

Como grupo aditivo, (ℤ/(p))[\sqrt{d}] = ℤ/(p)×ℤ/(p). Vamos investigar a estrutura multiplicativa de (ℤ/(p))[\sqrt{d}]. Observemos inicialmente que, se d é um quadrado módulo p então (ℤ/(p))[\sqrt{d}] não pode ser um corpo, pois se a^{2} = d em ℤ/(p) então (a + \sqrt{d})(a − \sqrt{d}) = 0 em (ℤ/(p))[\sqrt{d}]. A próxima proposição é uma recíproca deste fato:

Proposição 10.1: Se (\frac{d}{p}) = −1 então (ℤ/(p))[\sqrt{d}] é um corpo. Dem: De fato, se (a, b) ≠ (0, 0), (a + b\sqrt{d})^{−1} = (a − b\sqrt{d})/(a^{2} − db^{2}). Temos que a^{2} − db^{2} ∈ (ℤ/(p))^{∗}, pois d não é quadrado mod p, logo, se b ≠ 0, a^{2} − db^{2} = 0, que equivale a d = (a/b)^{2} seria uma contradição e, se b = 0, a^{2} − db^{2} = a^{2} ≠ 0 pois (a, b) ≠ (0, 0) ⇒ a ≠ 0 ⇒ a^{2} ≠ 0.

■

Problemas:

1) Sejam a, n > 1 inteiros. Prove que i) Se a^{n} − 1 é primo então a = 2 e n é primo. ii) Se a^{n} + 1 é primo então n = 2^{k} para algum inteiro k.

2) Prove que existem infinitos números primos congruentes a 3 módulo 4.

3) Determine todos os n naturais tais que (2^{n} − 1)/n é inteiro.

4) Determine todos os n naturais que (2^{n} + 1)/n^{2} é inteiro.

5) Prove que se a e b são naturais e (a^{2} + b^{2})/(ab + 1) é inteiro então (a^{2} + b^{2})/(ab + 1) é quadrado perfeito.

6) Sejam a, n ∈ ℕ^{∗}. Considere a seqüência (x_{n}) definida por x_{1} = a, x_{k+1} = a^{x_{k}}, ∀ k ∈ ℕ.

Mostre que existe N ∈ ℕ tal que x_{k+1} ≡ x_{k} (módulo n), para todo k ≥ N. Obs.: Os Problemas 4 e 5 foram propostos na 31\underline{a} e na 29\underline{a} Olimpíada Internacional de Matemática (1990 e 1988) respectivamente.

Números Primos

1 Sobre a distribuição dos números primos

Já vimos que existem infinitos primos; o teorema dos números primos dá uma estimativa de quantos primos existem até um inteiro x, ou seja, descreve a distribuição dos primos. Defina π(x) como sendo o número de primos p com 2 ≤ p ≤ x.

Teorema 1.1: (Teorema dos números primos)

lim_{x→∞} \frac{π(x)}{x/ log x} = 1.

Observe que aqui e em todo o livro log denota o logaritmo natural. Este resultado foi conjecturado por vários matemáticos, inclusive por Legendre e Gauss, mas a demonstração completa só foi encontrada em 1896, por de la Vallée Poussin e Hadamard (independentemante). Não demonstraremos este teorema: as demonstrações elementares conhecidas são todas bastante difíceis (lembramos que uma demonstração é dita elementar quando não usa ferramentas avançadas: muitas demonstrações elementares são longas e sofisticadas). Daremos uma demonstração da seguinte proposição (devida a Tchebycheff) que é claramente uma versão fraca do teorema dos números primos.

Proposição 1.2: Existem constantes positivas c < C tais que

c\frac{x}{log x} < π(x) < C \frac{x}{log x}

para todo x ≥ 2.

Dem: Observemos inicialmente que \binom{2n}{n} = \frac{(2n)!}{n!n!} é múltiplo de todos os primos p que satisfazem n < p ≤ 2n. Como

\binom{2n}{n} < ∑_{0≤k≤2n} \binom{2n}{k} = 2^{2n},

segue que o produto dos primos entre n e 2n é menor do que 2^{2n}. Como há π(2n)−π(n) primos como esses segue que n^{π(2n)−π(n)} < 2^{2n} (pois todos esses primos são maiores que n), donde (π(2n) − π(n)) log n < 2n log 2 e

π(2n) − π(n) < \frac{2n log 2}{log n}.

Isso implica facilmente, por indução, que

π(2^{k+1}) ≤ \frac{5 · 2^{k}}{k}

(começando com k = 5; até k = 5 segue de π(n) ≤ n/2). Daí segue que se 2^{k} < x ≤ 2^{k+1} então

π(x) ≤ \frac{5 · 2^{k}}{k} ≤ \frac{5x log 2}{log x}

pois f(x) = x log 2/ log x é uma função crescente para x ≥ 3.

Vamos agora provar a outra desigualdade. O expoente do primo p na fatoração de n! é

w_{p}(n) = ⌊\frac{n}{p}⌋ + ⌊\frac{n}{p^{2}} ⌋ + ⋯

= ∑_{k=1}^{∞} ⌊\frac{n}{p^{k}} ⌋

(esta é uma soma finita pois se k > log_{p} n = log n/ log p então ⌊\frac{n}{p^{k}} ⌋ = 0). De fato, ⌊\frac{n+1}{p^{j}}⌋ − ⌊\frac{n}{p^{k}} ⌋ é sempre 0 ou 1, e é igual a 1 se e só se p^{j} divide n + 1. Assim, w_{p}(n + 1) − w_{p}(n) é igual ao expoente de p na fatoração de n + 1, o que fornece uma prova por indução do fato acima.

Assim, o expoente de p em \binom{2n}{n} = (2n)!/n!^{2} é

∑_{k=1}^{∞} (⌊\frac{2n}{p^{k}}⌋ − 2 ⌊\frac{n}{p^{k}} ⌋) .

Temos agora que ⌊\frac{2n}{p^{k}}⌋ − 2⌊\frac{n}{p^{k}} ⌋ é sempre 0 ou 1 (pois 0 ≤ x − ⌊x⌋ < 1 para todo x), donde o expoente de p em \binom{2p}{p} é no máximor log_{p} n = log n/ log p para todo primo p. Por outro lado, se n < p ≤ 2n, o expoente de p em \binom{2p}{p} é 1. Assim, se \binom{2n}{n} = ∏_{p<2n} p^{α_{p}} é a fatoração de \binom{2n}{n} então

log \binom{2n}{n} = ∑_{p<2n} α_{p} log p

= ∑_{p≤n} α_{p} log p + ∑_{n<p≤2n} log p

≤ π(n) log n + (π(2n) − π(n)) log(2n) ≤ π(2n) log(2n)

donde

π(2n) ≥ log \binom{2n}{n}/ log(2n) ≥ n log 2/ log(2n)

pois

\binom{2n}{n} = \frac{2n}{n} · \frac{2n − 1}{n − 1} ⋯ \frac{n + 1}{1} ≥ 2^{n},

donde

π(x) ≥ \frac{x log 2}{log x}

para todo x par, o que implica na mesma estimativa para todo x inteiro, pois π(2k−1) = π(2k).

■

Corolário 1.3: Seja f : ℕ → [0, +∞) uma função decrescente. A série

∑_{p primo} f(p)

converge se e somente se a série

∑_{n=2}^{∞} \frac{f(n)}{log n}

converge. Em particular,

∑_{p primo} \frac{1}{p} = +∞.

Deixamos a demonstração deste corolário como exercício.

Uma aproximação mais precisa para π(x) é dada por

Li(x) = ∫_{0}^{x} \frac{dt}{log t},

onde tomamos o valor principal desta integral, ou seja,

Li(x) = lim_{ε→0} ∫_{ε}^{1−ε} \frac{dt}{log t} + ∫_{1+ε}^{x} \frac{dt}{log t};

claramente

lim_{x→∞} \frac{Li(x)}{log(x)/x} = 1.

Sabe-se entretanto que

|π(x) − Li(x)| ≤ Cxe^{−a(log x)^{3/5}(log log x)^{−1/5}}

para algum valor das constantes a e C (independente de x). Em particular, para qualquer k > 0 existe C > 0 tal que,para todo x,

|π(x) − Li(x)| ≤ C \frac{x}{(log x)^{k}} ,

o que mostra que Li(x) (e mesmo x/(log x − 1)) é uma aproximação de π(x) bem melhor do que x/ log x.

A hipótese de Riemann, já mencionada, equivale a dizer que para todo ε > 0 existe C com

|π(x) − Li(x)| ≤ Cx^{1/2+ε};

ninguém sabe demonstrar que esta estimativa seja correta sequer para algum valor de ε < 1/2. A hipótese de Riemann também implica que existe C com

|π(x) − Li(x)| ≤ Cx^{1/2} log x,

o que daria uma estimativa para o tamanho deste erro muito melhor de que as que se sabe demonstrar. Por outro lado, sabe-se demonstrar que não pode existir nenhuma estimativa muito melhor do que esta para |π(x) − Li(x)|: existe uma constante C > 0 e inteiros x_{1} e x_{2} arbitrariamente grandes com

π(x_{1}) − Li(x_{1}) < −C \frac{\sqrt{x_{1}} log log log x_{1}}{log x_{1}} ,
π(x_{2}) − Li(x_{2}) > C \frac{\sqrt{x_{2}} log log log x_{2}}{log x_{2}} .

2 Outros resultados e conjecturas sobre primos

Nesta seção veremos o enunciado de alguns resultados clássicos sobre números primos. Também veremos vários problemas em aberto famosos.

Teorema 2.1: (Dirichlet) Dados naturais a, d com mdc(a, d) = 1, existem infinitos primos da forma a + dn (com n natural).

A demonstração usual deste teorema usa variáveis complexas. Muitos casos particulares admitem demonstrações elementares mais ou menos simples. O leitor não deve ter dificuldade em demonstrar, por exemplo, que existem infinitos primos da forma 4n + 3 ou 6n + 5.

Existem vários refinamentos conhecidos do teorema de Dirichlet. Definimos π_{d,a}(x) como sendo o número de primos da forma a + dn no intervalo [2, x]. De la Vallée Poussin provou que

lim_{x→+∞} \frac{π_{d,a}(x)}{π(x)} = \frac{1}{φ(d)},

isto é, todas as possíveis classes módulo d têm aproximadamente a mesma proporção de primos.

Por outro lado, Tchebycheff observou que para valores pequenos de x π_{3,2}(x) − π_{3,1}(x) e π_{4,3}(x) − π_{4,1}(x) são positivos. Um teorema de Littlewood, entretanto, demonstra que estas funções mudam de sinal infinitas vezes. Em 1957, Leech demonstrou que o menor valor de x para o qual π_{4,3}(x) − π_{4,1}(x) = −1 é 26861 e em 1978 Bays e Hudson demonstraram que o menor valor de x para o qual π_{3,2}(x) − π_{3,1}(x) = −1 é 608981813029.

Seja p(d, a) o menor primo da forma a + dn, n inteiro e

p(d) = max{p(d, a) | 0 < a < d, mdc(a, d) = 1}.

Linnik (1944) provou que existe L > 1 com p(d) < d^{L} para todo d suficientemente grande. A melhor estimativa conhecida para L é L ≤ 5, 5, devida a Heath-Brown (1992), que também conjecturou que

p(d) ≤ Cd(log d)^{2}.

Por outro lado, não se sabe demonstrar que existam infinitos primos da forma n^{2} + 1; aliás, não existe nenhum polinômio P em uma variável e de grau maior que 1 para o qual se saiba demonstrar que existem infinitos primos da forma P (n), n ∈ ℤ. Por outro lado, existem muitos polinômios em mais de uma variável que assumem infinitos valores primos: por exemplo, provase facilmente que todo primo da forma 4n+1 pode ser escrito também na forma a^{2}+b^{2}, a, b ∈ ℤ. Por outro lado, Friedlander e Iwaniec provaram recentemente um resultado muito mais difícil: que existem infinitos primos da forma a^{2} + b^{4}.

Um dos problemas em aberto mais famosos da matemática é a conjectura de Goldbach: todo número par maior ou igual a 4 é a soma de dois primos. Chen demonstrou que todo número par suficientemente grande é a soma de um primo com um número com no máximo dois fatores primos. Vinogradov demonstrou que todo ímpar suficientemente grande (por exemplo, maior do que 3^{3^{15}}) é uma soma de três primos.

Quando p e p + 2 são ambos primos, dizemos que eles são primos gêmeos. Conjectura-se, mas não se sabe demonstrar, que existem infinitos primos gêmeos. Brun, por outro lado, provou que primos gêmeos são escassos no seguinte sentido: se π_{2}(x) é o número de pares de primos gêmeos até x então

π_{2}(x) < \frac{100x}{(log x)^{2}}

para x sufientemente grande. Em particular,

∑_{p primo gêmeo} \frac{1}{p} < +∞.

Acredita-se que π_{2}(x) seja assintótico a Cx/(log x)^{2} para alguma constante positiva C. Deixamos como exercício provar a seguinte caracterização de primos gêmeos devida a Clement. Seja n ≥ 2; os inteiros n e n + 2 são ambos primos se e somente se

4((n − 1)! + 1) + n ≡ 0 (mod n(n + 2)).

Seja p_{n} o n-ésimo número primo. O teorema dos números primos equivale a dizer que

lim_{n→∞} \frac{p_{n}}{n log n} = 1.

Por outro lado, sabe-se muito pouco sobre o comportamento da função d_{n} = p_{n+1} − p_{n}. Por exemplo, a conjectura de que existem infinitos primos gêmeos equivale a dizer que lim inf d_{n} = 2.

Não se sabe provar nem que

L = lim inf \frac{d_{n}}{log p_{n}} = 0;

Erdös provou que L < 1 e Maier que L ≤ 0, 248. Erdös também provou que o conjunto dos pontos de acumulação de d_{n}/ log p_{n} tem medida positiva. Por outro lado, é um teorema clássico, conhecido como postulado de Bertrand, que sempre existe pelo menos um primo entre m e 2m, ou seja, d_{n} < p_{n}. Em 1931, Westzynthius provou que

lim sup \frac{d_{n}}{log p_{n}} = ∞,

e em 1963 Rankin, completando um trabalho de Erdös, mostrou que

lim sup \frac{d_{n}(log log log p_{n})^{2}}{log p_{n} log log p_{n} log log log log p_{n}} ≥ e^{γ} ≈ 1, 78107

onde γ é a constante de Euler-Mascheroni,

γ = lim_{n→∞} (1 + \frac{1}{2} + ⋯ + \frac{1}{n} − log n) ≈ 0, 5772156649;

este resultado foi melhorado posteriormente por Pomerance e Pintz, que provou que o lado esquerdo é maior ou igual a 2e^{γ} ([Pintz]). Conjectura-se que

lim sup \frac{d_{n}}{(log p_{n})^{2}} = C

para alguma constante positiva C. Outra conjectura famosa é que sempre há pelo menos um primo entre n^{2} e (n + 1)^{2}. Observamos que a primeira vez que d_{n} > 1000 ocorre para p_{n} = 1693182318746371, quando d_{n} = 1132, o que foi descoberto recentemente por T. Nicely e D. Nyman.

Sierpinski provou que existem infinitos números naturais k tais que k·2^{n}+1 é composto para todo natural n e Riesel provou o mesmo resultado para k ·2^{n} −1. Conjectura-se que os menores valores de k com as propriedades acima são respectivamente 78557 e 509203. Há um projeto cooperativo, que consiste em procurar primos grandes, para demonstrar estas conjecturas (veja

http://vamri.xray.ufl.edu/proths/).

O leitor interessado em aprender mais sobre problemas em aberto em teoria dos números pode consultar [Guy].

3 Fórmulas para primos e testes de primalidade

Mencionamos na introdução deste capítulo que não se conhece nenhuma fórmula simples para gerar primos arbitrariamente grandes. Uma palavra imprecisa mas importante nesta frase é “simples”. Existem fórmulas que geram números primos, mas que são tão complicadas que não ajudam muito nem a gerar números primos explicitamente nem a responder perguntas teóricas sobre a distribuição dos primos. Um exemplo de fórmula para p_{n}, o n-ésimo primo, é

p_{n} = ⌊1 − \frac{1}{log 2} log (−\frac{1}{2} + ∑_{d|P_{n−1}} \frac{μ(d)}{2^{d} − 1})⌋ ,

onde P_{n−1} = p_{1}p_{2} ⋯ p_{n−1}; deixamos a demonstração a cargo do leitor. Outra fórmula é

p_{n} = ⌊10^{2^{n}}c⌋ − 10^{2^{n−1}}⌊10^{2^{n−1}}c⌋,

onde

c = ∑_{n=1}^{∞} \frac{p_{n}}{10^{2^{n}}} = 0.0203000500000007 ….

A inutilidade desta última fórmula vem do fato que para calcular c devemos encontrar todos os primos; a fórmula se tornaria mais interessante se existisse outra interpretação para o número real c, o que parece muito improvável. Por outro lado, existe um número real a > 1 tal que ⌊a^{3^{n}}⌋ é sempre primo.

Um tipo de fórmula para primos, de certa forma mais intrigante, são polinômios de coeficientes inteiros em S variáveis com a seguinte propriedade quase mágica: a interseção da imagem de ℕ^{S} com ℕ é exatamente o conjunto dos números primos. Note que se tomarmos um ponto de ℕ^{S} “ao acaso”, o valor do polinômio neste ponto quase certamente será negativo; assim, é difícil usar o polinômio para gerar primos. A título de curiosidade, vejamos um exemplo de polinômio com estas propriedades; aqui N = 26, o valor do polinômio é P, as variáveis chamam-se a, b, …, z e A, B, …, N são expressões auxiliares:

P = (k + 2)(1 − A^{2} − B^{2} − C^{2} − ⋯ − N^{2}),
A = wz + h + j − q,
B = (gk + 2g + k + 1)(h + j) + h − z,
C = 16(k + 1)^{3}(k + 2)(n + 1)^{2} + 1 − f^{2},
D = 2n + p + q + z − e,
E = e^{3}(e + 2)(a + 1)^{2} + 1 − o^{2},
F = (a^{2} − 1)y^{2} + 1 − x^{2},
G = 16r^{2}y^{4}(a^{2} − 1) + 1 − u^{2},
H = ((a + u^{2}(u^{2} − a))^{2} − 1)(n + 4dy)^{2} + 1 − (x + cu)^{2},
I = (a^{2} − 1)l^{2} + 1 − m^{2},
J = ai + k + 1 − l − i,
K = n + l + v − y,
L = p + l(a − n − 1) + b(2an + 2a − n^{2} − 2n − 2) − m,
M = q + y(a − p − 1) + s(2ap + 2a − p^{2} − 2p − 2) − x,
N = z + pl(a − p) + t(2ap − p^{2} − 1) − pm.

Algumas observações simples: a única forma de P ser positivo é se A = B = ⋯ = N = 0; neste caso seu valor será k + 2. Vemos assim que para produzir um número primo P com este polinômio devemos antes de mais nada tomar k = P − 2. As expressões auxiliares viram equações: como A = 0 temos q = wz + h + j. Assim, dado k para o qual k + 2 é primo, precisamos procurar valores para as outras letras que satisfaçam estas equações. Estes valores de certa forma encodificam uma demonstração de que P = k + 2 é primo.

4 Testes de primalidade baseados em fatorações de n − 1

Proposição 4.1: Seja n > 1. Se para cada fator primo q de n − 1 existe um inteiro a_{q} tal que a_{q}^{n−1} ≡ 1 (mod n) e a_{q}^{(n−1)/q} ≢ 1 (mod n) então n é primo.

Dem: Seja q^{k_{q}} a maior potência de q que divide n − 1. A ordem de a_{q} em (ℤ/(n))^{∗} é um múltiplo de q^{k_{q}}, donde φ(n) é um múltiplo de q^{k_{q}}. Como isto vale para todo fator primo q de n − 1, φ(n) é um múltiplo de n − 1 e n é primo. ■

Proposição 4.2: (Pocklington) Se n − 1 = q^{k}R onde q é primo e existe um inteiro a tal que a^{n−1} ≡ 1 (mod n) e mdc(a^{(n−1)/q} − 1, n) = 1 então qualquer fator primo de n é congruo a 1 módulo q^{k}.

Dem: Se p é um fator primo de n então a^{n−1} ≡ 1 (mod p) e p não divide a^{(n−1)/q} − 1, donde ord_{p} a, a ordem de a módulo p, divide n − 1 mas não divide (n − 1)/q. Assim, q^{k}| ord_{p} a|p − 1, donde p ≡ 1 (mod q)^{k}. ■

Corolário 4.3: Se n − 1 = F R, com F > R e para todo fator primo q de F existe a > 1 tal que a^{n−1} ≡ 1 (mod n) e mdc(a^{(n−1)/q} − 1, n) = 1 então n é primo.

Dem: Seja q um fator primo de F e q^{k} a maior potência de q que divide F; pela proposição anterior, todo fator primo de n deve ser côngruo a 1 módulo q^{k}. Como isto vale para qualquer fator primo de F, segue que qualquer fator primo de n deve ser côngruo a 1 módulo F. Como F > \sqrt{n}, isto implica que n é primo. ■

De fato, basta conhecer um conjunto de fatores primos cujo produto seja maior do que (n − 1)^{1/3} para, usando o resultado de Pocklington, tentar demonstrar a primalidade de n (o que deixamos como exercício). Os seguintes critérios clássicos são conseqüências diretas das proposições acima.

Fermat conjecturou que todo número da forma F_{n} = 2^{2^{n}} + 1 fosse primo e verificou a conjectura para n ≤ 4. Observe que 2^{n} + 1 (e em geral a^{n} + 1 com a ≥ 2) não é primo se n não é uma potência de 2: se p é um fator primo ímpar de n, podemos escrever a^{n} + 1 = b^{p} + 1 = (b + 1)(b^{p−1} − b^{p−2} + ⋯ + b^{2} − b + 1) onde b = a^{n/p}. Euler mostraria mais tarde que F_{5} não é primo (temos F_{5} = 4294967297 = 641 · 6700417) e já se demonstrou que F_{n} é composto para vários outros valores de n; nenhum outro primo da forma F_{n} = 2^{2^{n}} + 1 é conhecido, mas se conhecem muitos primos (alguns bastante grandes) da forma a^{2^{n}} + 1, que são conhecidos como primos de Fermat generalizados. O teste a seguir mostra como testar eficientemente a primalidade de F_{n}.

Corolário 4.4: (Teste de Pépin) Seja F_{n} = 2^{2^{n}} +1; F_{n} é primo se e somente se 3^{(F_{n}−1)/2} ≡ −1 (mod F_{n}).

Dem: Se 3^{(F_{n}−1)/2} ≡ −1 (mod F_{n}) então a primalidade de F_{n} segue da Proposição 4.1. Por outro lado, se F_{n} é primo então 3^{(F_{n}−1)/2} ≡ (\frac{3}{F_{n}}) = (\frac{F_{n}}{3} ) = (\frac{2}{3}) = −1 (mod F_{n}). ■

Corolário 4.5: (Teorema de Proth; 1878) Seja n = h · 2^{k} + 1 com 2^{k} > h. Então n é primo se e somente se existe um inteiro a com a^{(n−1)/2} ≡ −1 (mod n).

Dem: Se n é primo, podemos tomar a qualquer com (\frac{a}{n}) = −1; ou seja, metade dos inteiros entre 1 e n − 1 serve como a. A recíproca segue do Corolário 4.3 com F = 2^{k}. ■

Corolário 4.6: Se n = h · q^{k} + 1 com q primo e q^{k} > h. Então n é primo se e somente se existe um inteiro a com a^{n−1} ≡ 1 (mod n) e mdc(a^{(n−1)/q} − 1, n) = 1.

Dem: Se n é primo, podemos tomar a qualquer que não seja da forma x^{q} módulo n; ou seja, uma proporção de (q − 1)/q dentre inteiros entre 1 e n − 1 serve como a. A recíproca segue do Corolário 4.3 com F = q^{k}. ■

Uma expressiva maioria entre os 100 maiores primos conhecidos estão nas condições do teorema de Proth (ver tabelas). Isto se deve ao fato de primos desta forma serem freqüentes (mais freqüentes do que, por exemplo, primos de Mersenne) e que sua primalidade é facilmente demonstrada usando este resultado.

5 Primos de Mersenne

Um número de Mersenne é um número da forma M_{p} = 2^{p} − 1. Os 5 maiores números primos conhecidos atualmente são primos de Mersenne. O maior deles é 2^{13466917} − 1, descoberto em 14/11/2001. Este é um dos dois primos conhecidos com mais de um milhão de dígitos. O outro é 2^{6972593} − 1 (também primo de Mersenne). Ambos foram descobertos pelo GIMPS (veja www.mersenne.org). O critério de Lucas-Lehmer, que apresentaremos nesta seção, é um dos fatores para que isso ocorra pois fornece um teste de primalidade bastante rápido para números de Mersenne. Vejamos primeiramente que 2^{p} − 1 só tem chance de ser primo quando p é primo.

Proposição 5.1: Se 2^{n} − 1 é primo então n é primo.

Dem: Se n = ab com a, b ≥ 2 então 1 < 2^{a}−1 < 2^{n}−1 e 2^{n}−1 = 2^{ab}−1 = (2^{a})^{b}−1 ≡ 1^{b}−1 = 0 (mod 2^{a} − 1) e 2^{n} − 1 é composto. ■

Por outro lado, não se sabe demonstrar nem que existam infinitos primos de Mersenne nem que existem infinitos primos p para os quais M_{p} é composto. Conjectura-se, entretanto, que existam infinitos primos p para os quais M_{p} é primo e que, se p_{n} é o n-ésimo primo deste tipo, temos

0 < A < \frac{log p_{n}}{n} < B < +∞

para constantes A e B. Existem algumas conjecturas mais precisas quanto ao valor de

lim_{n→∞} \sqrt[n]{p_{n}};

Eberhart conjectura que este limite exista e seja igual a 3/2; Wagstaff por outro lado conjectura que o limite seja

2^{e^{−γ}} ≈ 1, 4757613971

onde γ é a já mencionada constante de Euler-Mascheroni.

Primos de Mersenne são interessantes também por causa de números perfeitos. Dado n ∈ ℕ^{∗}, definimos

σ(n) = ∑_{d|n} d,

a soma dos divisores (positivos) de n. Pelo teorema fundamental da aritmética demonstramos facilmente que se

n = p_{1}^{e_{1}}p_{2}^{e_{2}} ⋯ p_{m}^{e_{m}},

com p_{1} < p_{2} < ⋯ < p_{m} então

σ(n) = (1 + p_{1} + ⋯ + p_{1}^{e_{1}}) ⋯ (1 + p_{m} + ⋯ + p_{m}^{e_{m}})

= \frac{p_{1}^{e_{1}+1} − 1}{p_{1} − 1} ⋯ \frac{p_{m}^{e_{m}+1} − 1}{p_{m} − 1}.

Em particular, se (a, b) = 1 então σ(ab) = σ(a)σ(b). Um inteiro positivo n é dito perfeito se σ(n) = 2n; os primeiros números perfeitos são 6, 28 e 496. Nosso próximo resultado caracteriza os números perfeitos pares.

Proposição 5.2: Se M_{p} é um primo de Mersenne então 2^{p−1}M_{p} é perfeito. Além disso, todo número perfeito par é da 2^{p−1}M_{p} para algum primo p, sendo M_{p} um primo de Mersenne.

Dem: Se M_{p} é primo então

σ(2^{p−1}M_{p}) = (2^{p} − 1)(M_{p} + 1) = 2 · 2^{p−1}M_{p}.

Por outro lado seja n = 2^{k}b, com k > 0 e b ímpar, um número perfeito par. Temos σ(n) = 2n = σ(2^{k})σ(b) donde 2^{k+1}b = (2^{k+1} − 1)σ(b) ≥ (2^{k+1} − 1)(b + 1), valendo a igualdade apenas se b for primo. Desta desigualdade temos b ≤ 2^{k+1} − 1. Por outro lado, como (2^{k+1} − 1)|2^{k+1}b e (2^{k+1} − 1, 2^{k+1}) = 1, temos (2^{k+1} − 1)|b e 2^{k+1} − 1 ≤ b. Assim b = 2^{k+1} − 1 e 2^{k+1}b = (2^{k+1} − 1)(b + 1), donde b é primo. Pela proposição 3.9, p = k + 1 é primo, b = M_{p} e n = 2^{p−1}M_{p}. ■

Por outro lado, um dos problemas em aberto mais antigos da matemática é o da existência de números perfeitos ímpares. Sabe-se apenas que um número perfeito ímpar, se existir, deve ser muito grande (mais de 300 algarismos) e satisfazer simultaneamente várias condições complicadas.

Conjectura 5.3: Não existe nenhum número perfeito ímpar.

Nosso próximo resultado é o critério de Lucas-Lehmer, a base dos algoritmos que testam para grandes valores de p se 2^{p} − 1 é ou não primo:

Teorema 5.4: Seja S a seqüência definida por S_{0} = 4, S_{k+1} = S_{k}^{2} − 2 para todo natural k. Seja n > 2; M_{n} = 2^{n} − 1 é primo se e somente se S_{n−2} é múltiplo de M_{n}.

Dem: Observemos inicialmente que

S_{n} = (2 + \sqrt{3})^{2^{n}} + (2 − \sqrt{3})^{2^{n}}

para todo natural n. A demonstração por indução é simples: claramente S_{0} = 4 = (2+\sqrt{3})^{2^{0}} + (2 − \sqrt{3})^{2^{0}} e

S_{k+1} = S_{k}^{2} − 2 = ((2 + \sqrt{3})^{2^{k}} + (2 − \sqrt{3})^{2^{k}})^{2} − 2
= ((2 + \sqrt{3})^{2^{k}})^{2} + 2 · (2 + \sqrt{3})^{2^{k}} · (2 − \sqrt{3})^{2^{k}} + ((2 − \sqrt{3})^{2^{k}})^{2} − 2
= (2 + \sqrt{3})^{2^{k+1}} + (2 − \sqrt{3})^{2^{k+1}}.

Suponha por absurdo que M_{n}|(2 + \sqrt{3})^{2^{n−2}} + (2 − \sqrt{3})^{2^{n−2}} e que M_{n} seja composto, com um fator primo q com q^{2} < M_{n}. Teremos (2+\sqrt{3})^{2^{n−2}} +(2−\sqrt{3})^{2^{n−2}} ≡ 0 (mod q) donde, no grupo multiplicativo G = (ℤ/(q)[\sqrt{3}])^{∗}, temos (2+\sqrt{3})^{2^{n−2}} = −(2−\sqrt{3})^{2^{n−2}}. Como 2−\sqrt{3} = (2+\sqrt{3})^{−1} esta equação pode ser reescrita como (2 + \sqrt{3})^{2^{n−1}} = −1 (ainda em G), o que significa que a ordem de 2 + \sqrt{3} em G é exatamente 2^{n}. Isto é um absurdo, pois o número de elementos de G é apenas q^{2} − 1 < 2^{n}. Fica portanto demonstrado que se S_{n−2} é múltiplo de M_{n} então M_{n} é primo.

Suponha agora M_{n} primo, n > 2. Lembramos que n é um primo ímpar. Por reciprocidade quadrática temos (\frac{3}{M_{n}}) = −(\frac{M_{n}}{3} ) = −1, pois 3 ≡ M_{n} ≡ −1 (mod 4) e M_{n} ≡ 1 (mod 3). Assim, 3 não é um quadrado em ℤ/(M_{p}) e K = ℤ/(M_{p})[\sqrt{3}] é um corpo de ordem M_{n}^{2}. Além disso, 3^{\frac{mn−1}{2}} = (\frac{3}{M_{n}}) = −1 em K. Queremos provar que (2 + \sqrt{3})^{2^{n−2}} + (2 − \sqrt{3})^{2^{n−2}} ≡ 0 (mod M)_{p}, ou seja, que é igual a 0 em K. Isto equivale a demonstrarmos que temos (2 + \sqrt{3})^{2^{n−2}} = −(2 − \sqrt{3})^{2^{n−2}} em K, o que pode ser reescrito como (2 + \sqrt{3})^{2^{n−1}} = −1; devemos portanto provar que a ordem de 2 + \sqrt{3} é exatamente 2^{n}. Note que 2^{n} = M_{n} + 1 donde (2 + \sqrt{3})^{2^{n}} = (2 + \sqrt{3})^{M_{n}}(2 + \sqrt{3}) = (2 − \sqrt{3})(2 + \sqrt{3}) = 1 (note que, em K, (2 + \sqrt{3})^{M_{n}} = (2^{M_{n}} + \sqrt{3})^{M_{n}} = 2 + 3^{\frac{Mn−1}{2}} · \sqrt{3} = 2 − \sqrt{3}); assim é claro que a ordem de 2 + \sqrt{3} é um divisor de 2^{n}.

Como K^{∗} tem M_{n}^{2} − 1 = 2^{n+1}(2^{n−1} − 1) elementos, devemos provar que 2 + \sqrt{3} não é uma quarta potência em K. Note que (2 + \sqrt{3})^{2^{n}} = 1 demonstra que 2 + \sqrt{3} é um quadrado, o que aliás pode ser visto mais diretamente: 2 + \sqrt{3} = (1 + \sqrt{3})^{2}/2 e 2 = 2^{n+1} = 2^{(n+1)^{2}} é uma quarta potência em K. Resta-nos assim demonstrar que ±(1 + \sqrt{3}) não são quadrados em K. Suponha por absurdo que ϵ(1 + \sqrt{3}) = (a + b\sqrt{3})^{2}, com ϵ = ±1; temos ϵ(1 − \sqrt{3}) = (a − b\sqrt{3})^{2} e, multiplicando, −2 = (a^{2} − 3b^{2})^{2}, o que significa que −2 é um quadrado módulo M_{n} (pois a e b são inteiros). Isto, entretanto, é claramente falso: (\frac{−2}{M_{n}}) = (\frac{−1}{M_{n}})(\frac{2}{M_{n}}) = −1 · 1 = −1, pois M_{n} ≡ 3 (mod 4) e já vimos que 2 é um quadrado módulo M_{p}. Isto conclui a demonstração.

■

Mesmo quando M_{p} não é primo, podemos garantir que seus fatores primos serão de certas formas especiais. Isto é muito útil quando procuramos primos de Mersenne pois podemos eliminar alguns expoentes encontrando fatores primos de M_{p}. Isto também pode ser útil para conjecturarmos quanto à “probabilidade” de M_{p} ser primo, ou, mais precisamente, quanto à distribuição dos primos de Mersenne.

Proposição 5.5: Sejam p > 2 e q primos com q um divisor de M_{p}. Então q ≡ 1 (mod p) e q ≡ ±1 (mod 8).

Dem: Se q divide M_{p} então 2^{p} ≡ 1 (mod q), o que significa que a ordem de 2 módulo q é p (pois p é primo). Isto significa que p é um divisor de q − 1, ou seja, que q ≡ 1 (mod p). Por outro lado, 2 ≡ 2^{p+1} = (2^{(p+1)/2})^{2} (mod q), donde (\frac{2}{q}) = 1, o que significa que q ≡ ±1 (mod 8). ■

Os vários valores de p para os quais a primalidade de M_{p} foi testada sugerem que para a ampla maioria dos valores de p, M_{p} não é primo. Isto é apenas uma conjectura: não se sabe demonstrar sequer que existem infinitos primos p para os quais M_{p} seja composto. Vamos agora ver uma proposição que serve para garantir que para certos valores especiais de p, alguns muito grandes, M_{p} não é primo.

Proposição 5.6: Seja p primo, p ≡ 3 (mod 4). Então 2p + 1 é primo se e somente se 2p + 1 divide M_{p}.

Dem: Se q é primo então M_{p} = 2^{p} − 1 = 2^{(q−1)/2} − 1 ≡ (\frac{2}{q}) − 1 (mod q). Mas p ≡ 3 (mod 4) significa que q ≡ 7 (mod 8), donde (\frac{2}{q}) = 1. Assim, M_{p} ≡ 0 (mod q), o que demonstra uma das implicações da proposição.

Por outro lado, se 2p + 1 não é primo tem fatores primos r com r ≢ 1 (mod p) (pois r < p). Se 2p + 1 dividisse M_{p}, r seria um fator primo de M_{p}, contrariando a proposição anterior. ■

Os primos p para os quais 2p+1 é primo são chamados de primos de Sophie Germain. Alguns primos de Sophie Germain bastante grandes são conhecidos, como p_{0} = 18458709 · 2^{32611} − 1; assim, pela proposição anterior, M_{p_{0}} é composto. Sabe-se também que se π_{SG}(x) denota o número de primos de Sophie Germain menores do que x então existe C tal que para todo x

π_{SG}(x) < C \frac{x}{(log x)^{2}} .

Acredita-se que π_{SG}(x) seja assintótico a cx/(log x)^{2} para algum c > 0 mas não se sabe demonstrar sequer que existem infinitos primos de Sophie Germain.

PARTE II

APROXIMAÇÕES DIOFANTINAS

53

Frações Contínuas, Representações de Números e Aproximações

Introdução

A teoria de frações contínuas é um dos mais belos temas da matemática elementar, sendo ainda hoje assunto de pesquisa recente (incluindo a do autor destas linhas). O objetivo deste artigo é servir como referência didática em português a nível secundário sobre o assunto.

Nas inclusões ℕ ⊂ ℤ ⊂ ℚ ⊂ ℝ a passagem de ℚ para ℝ é sem dúvida a mais complicada conceitualmente, e a representação de um número real está diretamente ligada à própria noção de número real.

De fato, o conceito de número natural é quase um conceito primitivo no ensino secundário. Já um número inteiro é um número natural com um sinal que pode ser + ou −, e um número racional é a razão entre um número inteiro e um natural não nulo. Por outro lado, dizer o que é um número real é tarefa bem mais complicada, mas há coisas que podemos dizer sobre eles. Uma propriedade essencial de ℝ é que todo número real pode ser bem aproximado por números racionais. Efetivamente, dado x ∈ ℝ, existe k ∈ ℤ (k = [x]) tal que 0 ≤ x − k < 1. Podemos escrever a representação decimal de x−k = 0, a_{1}a_{2} … a_{n} …, a_{i} ∈ {0, 1, …, 9}, o que significa

que se r_{n} = a_{n} + 10 · a_{n−1} + 100 · a_{n−2} + ⋯ + 10^{n−1} · a_{1}, então \frac{r_{n}}{10^{n}} ≤ x − k < \frac{r_{n} + 1}{10^{n}} , e portanto

k + \frac{r_{n}}{10^{n}} é uma boa aproximação racional de x, no sentido que o erro |x − (k + \frac{r_{n}}{10^{n}} )| é menor que \frac{1}{10^{n}} , que é um número bem pequeno se n for grande. A representação decimal de um número real fornece pois uma seqüência de aproximações por racionais cujos denominadores são potências de 10.

Dado qualquer x ∈ ℝ e q natural não nulo existe p ∈ ℤ tal que \frac{p}{q} ≤ x < \frac{p + 1}{q} , e por-

tanto |x − \frac{p}{q}| < \frac{1}{q} e |x − \frac{p + 1}{q}| ≤ \frac{1}{q} . Em particular há aproximações de x por racionais com denominador q com erro menor que \frac{1}{q} . A representação decimal de x equivale a dar essas aproximações para os denominadores q que são potências de 10, e tem méritos como sua praticidade para efetuar cálculos que a fazem a mais popular das representações dos números reais. Por outro lado, envolve a escolha arbitrária da base 10, e oculta freqüentemente aproximações racionais de x muito mais eficientes do que as que exibe. Por exemplo,

|π − \frac{22}{7}| < \frac{1}{700} < |π − \frac{314}{100}| e |π − \frac{355}{113}| < \frac{1}{3000000} < |π − \frac{3141592}{1000000}|

mostram que \frac{22}{7} e \frac{355}{113} são melhores aproximações de π que aproximações decimais com denominadores muito maiores, e de fato são aproximações muito mais espetaculares do que se podia esperar.

O objetivo deste artigo é apresentar uma outra maneira de representar números reais, que sempre fornece aproximações racionais surpreendentemente boas, e de fato fornece todas essas aproximações excepcionalmente boas, além de ser natural e conceitualmente simples: a representação por frações contínuas.

Dado x ∈ ℝ, definimos [x] como o único inteiro tal que [x] ≤ x < [x] + 1. Definimos recursivamente

α_{0} = x, a_{n} = [α_{n}], e, se α_{n} ∈ Z, α_{n+1} = \frac{1}{α_{n} − a_{n}} , para todo n ∈ N.

Se, para algum n, α_{n} = a_{n} temos

x = α_{0} = a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2} + ⋯ + \frac{1}{a_{n}}}} =: [a_{0}; a_{1}, a_{2}, …, a_{n}].

Senão denotamos

x = a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2} + …}} =: [a_{0}; a_{1}, a_{2}, …].

O sentido dessa última notação ficará claro mais tarde. A representação acima se chama a representação por frações contínuas de x.

Curiosidade: O denominador da n-ésima aproximação em base B de um número real é B^{n}.

Já o denominador q_{n} da n-ésima aproximação por fração contínua de x depende de x. Apesar disso, para quase todo real x, \sqrt[n]{q_{n}} converge a e^{π^{2}/12 ln 2} = 3, 27582291872 … (meu número real preferido!) e \sqrt[n]{|x − \frac{p_{n}}{q_{n}} |} converge a e^{−π^{2}/6 ln 2} = 0, 093187822954 ….

Observação: Os α_{n} (como funções de x) são funções distintas do tipo \frac{ax + b}{cx + d} com a, b, c, d inteiros. Se a fração contínua de x é periódica, ou seja, se α_{n+k} = α_{n}, n ∈ ℕ, k ∈ ℕ^{∗}, então x será raiz de uma equação do segundo grau com coeficientes inteiros, ou seja, será um irracional da forma r + \sqrt{s}, r, s ∈ ℚ. A recíproca é verdadeira (de fato já foi enunciada no artigo de José Paulo Carneiro na RPN, ver referências), mas sua prova é mais difícil, e será apresentada no Apêndice.

Se x ∈ ℚ, sua representação será finita, e seus coeficientes a_{n} vêm do algoritmo de Euclides:

x = \frac{p}{q} , q > 0 p = a_{0}q + r_{0}  0 ≤ r_{0} < q
q = a_{1}r_{0} + r_{1} 0 ≤ r_{1} < r_{0}
r_{0} = a_{2}r_{1} + r_{2} 0 ≤ r_{2} < r_{1}
⋮ ⋮
r_{n−2} = a_{n}r_{n−1}

Isso já é uma vantagem da representação por frações contínuas (além de não depender de escolhas artificiais de base), pois o reconhecimento de racionais é mais simples que na representação decimal.

1 Reduzidas e boas aproximações

Seja x = [a_{0}; a_{1}, a_{2}, …]. Sejam p_{n} ∈ ℤ, q_{n} ∈ ℕ^{∗} primos entre si tais que \frac{p_{n}}{q_{n}} = [a_{0}; a_{1}, a_{2}, …, a_{n}], n ≥ 0. O seguinte resultado será fundamental no que seguirá.

Proposição 1.1: (p_{n}) e (q_{n}) satisfazem a recorrência p_{n+2} = a_{n+2}p_{n+1} + p_{n}, e q_{n+2} = a_{n+2}q_{n+1} + q_{n}, para todo n ≥ 0. Temos ainda p_{0} = a_{0} , p_{1} = a_{0}a_{1} + 1, q_{0} = 1, q_{1} = a_{1} .

Além disso, p_{n+1} q_{n} − p_{n} q_{n+1} = (−1)^{n}, ∀ n ≥ 0.

Dem: Por indução em n, provaremos que se t_{k} > 0, para k > 1 então [t_{0}; t_{1}, t_{2}, …, t_{n}] = \frac{x_{k}}{y_{k}} onde as seqüências (x_{m}) e (y_{m}) são definidas por x_{0} = t_{0} , y_{0} = 1, x_{1} = t_{0}t_{1} + 1, y_{1} = t_{0} x_{n+2} = t_{n+2} x_{n+1} + x_{n}, y_{n+2} = t_{n+2} y_{n+1} + y_{n}, ∀ n. Suponha que a afirmação seja válida para k = n. Para k = n + 1 temos

[t_{0}; t_{1}, t_{2}, …, t_{n}, t_{n+1}] = [t_{0}; t_{1}, t_{2}, …, t_{n} + \frac{1}{t_{n+1}} ] =

= \frac{(t_{n} + \frac{1}{t_{n+1}} )x_{n−1} + x_{n−2}}{(t_{n} + \frac{1}{t_{n+1}} )y_{n−1} + y_{n−2}} = \frac{t_{n+1}(t_{n}x_{n−1} + x_{n−2}) + x_{n−1}}{t_{n+1}(t_{n}y_{n−1} + y_{n−2}) + y_{n−1}} = \frac{t_{n+1}x_{n} + x_{n−1}}{t_{n+1}y_{n} + y_{n−1}} ·

Por outro lado as igualdades

• p_{1}q_{0} − p_{0}q_{1} = (a_{0}a_{1} + 1) − a_{0}a_{1} = 1

• p_{n+2}q_{n+1} − p_{n+1}q_{n+2} = (a_{n+2}p_{n+1} + p_{n})q_{n+1} −(a_{n+2} q_{n+1} + q_{n})p_{n+1} = −(p_{n+1}q_{n} − p_{n}q_{n+1})

mostram que p_{n+1} q_{n} − p_{n} q_{n+1} = (−1)^{n}, ∀ n ∈ ℕ, o que implica em particular que os p_{n}, q_{n} dados pelas recorrências acima são primos entre si. ■

Corolário 1.2: x = \frac{α_{n}p_{n−1} + p_{n−2}}{α_{n}q_{n−1} + q_{n−2}} e α_{n} = \frac{p_{n−2} − q_{n−2}α}{q_{n−1}α − p_{n−1}} , ∀ n ∈ ℕ.

Dem: A primeira igualdade é conseqüência direta da prova, e a segunda é conseqüência direta da primeira pois x = [a_{0}; a_{1}, a_{2}, …, a_{n−1}, α_{n}].

Note que as reduzidas de ordem par são menores e as de ordem ímpar maiores que x = [a_{0}; a_{1}, …].

Teorema 1.3: |x − \frac{p_{n}}{q_{n}} | ≤ \frac{1}{q_{n}q_{n+1}} < \frac{1}{q_{n}^{2}} , ∀ n ∈ ℕ.

Além disso, |x − \frac{p_{n}}{q_{n}} | < \frac{1}{2q_{n}^{2}} ou |x − \frac{p_{n+1}}{q_{n+1}} | < \frac{1}{2q_{n+1}^{2}} , ∀ n ∈ ℕ.

Dem: x sempre pertence ao segmento de extremos \frac{p_{n}}{q_{n}} e \frac{p_{n+1}}{q_{n+1}} cujo comprimento é

|\frac{p_{n+1}}{q_{n+1}} − \frac{p_{n}}{q_{n}} | = |\frac{(−1)^{n}}{q_{n}q_{n+1}} | = \frac{1}{q_{n}q_{n+1}} ⇒ |x − \frac{p_{n}}{q_{n}} | ≤ \frac{1}{q_{n}q_{n+1}} < \frac{1}{q_{n}^{2}} ·

Além disso, se

|x − \frac{p_{n}}{q_{n}} | ≥ \frac{1}{2q_{n}^{2}} e |x − \frac{p_{n+1}}{q_{n+1}} | > \frac{1}{2q_{n+1}^{2}} ,

então

\frac{1}{q_{n}q_{n+1}} = |x − \frac{p_{n}}{q_{n}} | + |x − \frac{p_{n+1}}{q_{n+1}} | ≥ \frac{1}{2q_{n}^{2}} + \frac{1}{2q_{n+1}^{2}} ⇒ q_{n+1} = q_{n} , absurdo.

■

Observação: De fato |x − \frac{p_{n}}{q_{n}} | < \frac{1}{q_{n}q_{n+1}} < \frac{1}{a_{n+1}q_{n}^{2}} . Quanto maior for a_{n+1} melhor será a aproximação \frac{p_{n}}{q_{n}} de x. O próximo resultado nos dá explicitamente o erro da aproximação de x

por \frac{p_{n}}{q_{n}} .

Proposição 1.4:

x − \frac{p_{n}}{q_{n}} = \frac{(−1)^{n}}{(α_{n+1} + β_{n+1})q_{n}^{2}} , onde β_{n+1} = \frac{q_{n−1}}{q_{n}} = [0; a_{n}, a_{n−1}, a_{n−2}, …, a_{1}].

Dem: Temos α_{n+1} = \frac{p_{n−1} − q_{n−1}x}{q_{n}x − p_{n}} . Portanto,

α_{n+1} + β_{n+1} = \frac{p_{n−1} − q_{n−1}x}{q_{n}x − p_{n}} + \frac{q_{n−1}}{q_{n}} = \frac{p_{n−1}q_{n} − p_{n}q_{n−1}}{q_{n}(q_{n}x − p_{n})} = \frac{(−1)^{n}}{q_{n}(q_{n}x − p_{n})} ⇒ x − \frac{p_{n}}{q_{n}} =

= \frac{q_{n}(q_{n}x − p_{n})}{q_{n}^{2}} = \frac{(−1)^{n}}{(α_{n+1} + β_{n+1})q_{n}^{2}} .

■

Como aplicação podemos provar o seguinte.

Teorema 1.5: (Hurwitz, Markov). Para todo α irracional, n ≥ 1 temos |α − \frac{p}{q}| < \frac{1}{\sqrt{5}q^{2}} para

pelo menos um racional \frac{p}{q} ∈ \{\frac{p_{n−1}}{q_{n−1}} , \frac{p_{n}}{q_{n}} , \frac{p_{n+1}}{q_{n+1}} \}. Em particular |α − \frac{p}{q}| < \frac{1}{\sqrt{5}q^{2}} tem infinitas soluções racionais p/q.

Dem: Suponha que o teorema seja falso. Então existe α irracional, n ≥ 1 com α_{n} + β_{n} ≤ \sqrt{5}, α_{n+1} + β_{n+1} ≤ \sqrt{5} e α_{n+2} + β_{n+2} ≤ 5. Devemos portanto ter a_{n} = a_{n+1} = a_{n+2} = 1 (todos são claramente no máximo 2, e se algum a_{k} é igual a 2 com k ∈ {n, n + 1, n + 2}, teríamos

a_{k} + β_{k} ≥ 2 + \frac{1}{3} > \sqrt{5}, absurdo.)

Seja x = 1/α_{n+2} e y = β_{n+1} . As desigualdades acima se traduzem em

\frac{1}{1 + x} + \frac{1}{y} ≤ \sqrt{5}, 1 + x + y ≤ \sqrt{5} e e\frac{1}{x} + \frac{1}{1 + y} ≤ \sqrt{5}.

Temos

1 + x + y ≤ \sqrt{5} ⇒ 1 + x ≤ \sqrt{5} − y ⇒ \frac{1}{1 + x} + \frac{1}{y} ≥ \frac{1}{\sqrt{5} − y} + \frac{1}{y} = \frac{\sqrt{5}}{y(\sqrt{5} − y)}

e portanto y(\sqrt{5} − y) ≥ 1 ⇒ y ≥ \frac{\sqrt{5} − 1}{2} · Por outro lado temos

x ≤ \sqrt{5} − 1 − y ⇒ \frac{1}{x} + \frac{1}{1 + 4} ≥ \frac{1}{\sqrt{5} − 1 − y} + \frac{1}{1 + 4} = \frac{\sqrt{5}}{(1 + y)(\sqrt{5} − 1 − y)}

e portanto (1 + y)(\sqrt{5} − 1 − y) ≥ 1 ⇒ y ≤ \frac{\sqrt{5} − 1}{2} , e portanto devemos ter y = \frac{\sqrt{5} − 1}{2} , o que é absurdo pois y = β_{n+1} = \frac{q_{n−1}}{q_{n}} ∈ ℚ.

Observação: Em particular provamos que |α − \frac{p}{q}| < \frac{1}{\sqrt{5}q^{2}} tem infinitas soluções racionais \frac{p}{q} , para todo α irracional. \sqrt{5} é o maior número com essa propriedade. De fato, se

ε > 0, α = \frac{1 + \sqrt{5}}{2} e |α − \frac{p}{q}| < \frac{1}{(\sqrt{5} + ε)q^{2}} ,

temos

|q(\frac{1 + \sqrt{5}}{2}) − p| < \frac{1}{(\sqrt{5} + ε)q} ⇒ |q(\frac{1 + \sqrt{5}}{2}) − p| |q(\frac{1 − \sqrt{5}}{2}) − p| < \frac{|\frac{1−\sqrt{5}}{2} − \frac{p}{q} |}{\sqrt{5} + ε} ,

ou seja,

|p^{2} − pq − q^{2}| < |\frac{1 + \sqrt{5}}{2} − \frac{p}{q} − \sqrt{5}| /(\sqrt{5} + ε).

Se q é grande, 1/q^{2} é pequeno, e \frac{1 + \sqrt{5}}{2} − \frac{p}{q} é muito próximo de 0, donde

|\frac{1 + \sqrt{5}}{2} − \frac{p}{q} − \sqrt{5}| /(\sqrt{5} + ε) é muito próximo de \frac{\sqrt{5}}{\sqrt{5} + ε} < 1, absurdo, pois |p^{2} − pq − q^{2}| ≥ 1 (de fato p^{2} − pq − q^{2} é um inteiro não nulo, pois se p^{2} − pq − q^{2} = 0 teríamos

(\frac{p}{q})^{2} − (\frac{p}{q}) − 1 = 0 ⇒ \frac{p}{q} ∈ \{\frac{1 + \sqrt{5}}{2}, \frac{1 − \sqrt{5}}{2}\},

absurdo, pois \frac{p}{q} ∈ ℚ.) Outra maneira de ver que, para todo ε > 0, |\frac{1 + \sqrt{5}}{2} − \frac{p}{q}| < \frac{1}{(\sqrt{5} + ε)q^{2}} tem apenas um número finito de soluções \frac{p}{q} ∈ ℤ é observar que as melhores aproximações racionais de \frac{1 + \sqrt{5}}{2} são as reduzidas \frac{p_{n}}{q_{n}} de sua fração contínua [1, 1, 1, 1, …] (ver seção 2 e exemplos), para as quais temos |\frac{1 + \sqrt{5}}{2} − \frac{p_{n}}{q_{n}} | = \frac{1}{(α_{n+1} + β_{n+1})q_{n}^{2}} , com α_{n+1} + β_{n+1} se aproximando cada vez mais de

[1; 1, 1, 1, …] + [0; 1.1.1….] = \frac{1 + \sqrt{5}}{2} + \frac{\sqrt{5} − 1}{2} = \sqrt{5}.

Exemplos:

• π = [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, …], portanto

\frac{p_{0}}{q_{0}} = 3, \frac{p_{1}}{q_{1}} = \frac{22}{7} , \frac{p_{2}}{q_{2}} = \frac{333}{106} , \frac{p_{3}}{q_{3}} = \frac{355}{113} …

• e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, …, 1, 1, 2n, …] (isso não é fácil de provar.)

• \sqrt{2} = [1; 2, 2, 2, …] pois

\sqrt{2} = 1 + \frac{1}{\sqrt{2 + 1}} = 1 + \frac{1}{2} + \frac{1}{\sqrt{2 + 1}} = 1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{\sqrt{2 + 1}} = ⋯

\frac{1 + \sqrt{5}}{2} = [1; 1, 1, 1, …] pois \frac{1 + \sqrt{5}}{2} = 1 + \frac{1 + \sqrt{5}}{2} = 1 + \frac{1 + \sqrt{5}}{2} + \frac{1 + \sqrt{5}}{2} = ⋯

Isto prova em particular que \sqrt{2} e \frac{1 + \sqrt{5}}{2} são irracionais, pois sua fração contínua é infinita.

2 Boas aproximações são reduzidas

O próximo teorema (e seu Corolário 2) caracteriza as reduzidas em termo do erro reduzido da aproximação de x por p/q, o qual é, por definição, a razão entre |x − p/q| e o erro máximo da aproximação por falta com denominador q, que é 1/q. Assim, o erro reduzido da aproximação de x por p/q é |qx − p|.

Teorema 2.1: |q_{n}x − p_{n}| < |qx − p|, ∀ p, q ∈ ℤ, 0 < q < q_{n} \frac{p}{q} ≠ \frac{p_{n}}{q_{n}} ·. Além disso,

|q_{n}x − p_{n}| ≤ |qx − p|, ∀ p, q ∈ ℤ, 0 < q < q_{n+1} .

Dem: |\frac{p}{q} − \frac{p_{n}}{q_{n}} | ≥ \frac{1}{qq_{n}} > \frac{1}{q_{n}q_{n+1}} se q < q_{n+1} , e assim \frac{p}{q} está fora do intervalo (\frac{p_{n}}{q_{n}} , \frac{p_{n+1}}{q_{n+1}} ).

Portanto

|x − \frac{p}{q}| ≥ min \{ |\frac{p}{q} − \frac{p_{n}}{q_{n}} | , |\frac{p}{q} − \frac{p_{n+1}}{q_{n+1}} | \} ≥ \frac{1}{qq_{n+1}} ⇒ |qx − p|

≥ \frac{1}{q_{n+1}} ≥ |q_{n}x − p_{n}|.

Além disso, se vale a igualdade, então x = \frac{p_{n+1}}{q_{n+1}} , donde a_{n+1} ≥ 2, e q_{n+1} > 2q_{n}, pois numa fração contínua finita, como no algoritmo de Euclides, o último coeficiente a_{n} é sempre maior que 1. Nesse caso, se q < q_{n}, teremos

|x − \frac{p}{q}| ≥ |x − \frac{p_{n}}{q_{n}} | − |\frac{p_{n+1}}{q_{n+1}} − \frac{p_{n}}{q_{n}} | ≥ \frac{1}{qq_{n}} − \frac{1}{q_{n}q_{n+1}} = \frac{q_{n+1} − q}{qq_{n}q_{n+1}}

> \frac{1}{qq_{n+1}} ⇒ |qx − p| > \frac{1}{q_{n+1}} ≥ |q_{n}x − p_{n}|.

Corolário 2.2: |x − \frac{p_{n}}{q_{n}} | < |x − \frac{p}{q}|, ∀ q < q_{n}.

Corolário 2.3: Se |qx − p| < |q′x − p′|, ∀ q′ ≤ q, \frac{p}{q} ≠ \frac{q′}{q′} então p/q é uma reduzida da fração contínua de x.

Dem: Tome n tal que q_{n} ≤ q < q_{n+1} . Teremos |q_{n}x − p_{n}| ≤ |qx − p|, e portanto p/q = p_{n}/q_{n}. ■

Teorema 2.4: Se |x − \frac{p}{q}| < \frac{1}{2q^{2}} então \frac{p}{q} é uma reduzida da fração contínua de x.

Dem: Seja n tal que q_{n} < q ≤ q_{n+1} . Suponha que \frac{p}{q} ≠ \frac{p_{n+1}}{q_{n+1}} . Então, temos duas possibilidades:

a) q ≥ \frac{q_{n+1}}{2} ⇒ |x − \frac{p}{q}| ≥ \frac{1}{qq_{n+1}} ≥ \frac{1}{2q^{2}} .

b) q < \frac{q_{n+1}}{2} ⇒ q_{n+1} > 2q_{n} ⇒ |x − \frac{p}{q}| ≥ |\frac{p_{n}}{q_{n}} − \frac{p}{q}| − |\frac{p_{nm}}{q_{nm}} − \frac{p_{n}}{q_{n}} | ≥ \frac{1}{qq_{n}} − \frac{1}{q_{n}q_{n+1}} =

\frac{q_{n+1} − q}{qq_{n}q_{n+1}} > \frac{1}{2qq_{n}} > \frac{1}{2q^{2}} .

3 Frações contínuas periódicas

Nesta seção provaremos que os números reais com fração contínua periódica são exatamente as raízes de equações do segundo grau com coeficientes inteiros.

Lembramos que na representação de x por fração contínua, a_{n}, α_{n} são definidos por recursão por

α_{0} = x, a_{n} = [α_{n}], α_{n+1} = \frac{1}{α_{n} − a_{n}} ·

E temos

α_{n} = \frac{p_{n−2} − q_{n−2}x}{q_{n−1}x − p_{n−1}} , ∀ n ∈ ℕ.

Isso dá uma prova explícita do fato de que se a fração contínua de x é periódica, então x é raiz de uma equação do segundo grau com coeficientes inteiros. De fato, se α_{n+k} = α_{n}, n ∈ ℕ, k ∈ ℕ^{∗} então

\frac{p_{n−2} − q_{n−2}x}{q_{n−1}x − p_{n−1}} = \frac{p_{n+k−2} − q_{n+k−2}x}{q_{n+k−1}x − p_{n+k−1}} ⇒ (q_{n−1} q_{n+k−2} − q_{n−2} q_{n+k−1})x^{2}

+ (p_{n+k−1} q_{n−2} + p_{n−2} q_{n+k−1} − p_{n+k−2} q_{n−1} − p_{n−1} q_{n+k−2})x + p_{n−1} p_{n+k−2} − p_{n−2} p_{n+k−1} = 0.

Note que o coeficiente de x^{2} é não-nulo, pois \frac{q_{n−1}}{q_{n−2}} é uma fração irredutível (de fato p_{n−1}q_{n−2} − p_{n−2}q_{n−1} = (−1)^{n}) de denominador q_{n−2} e \frac{q_{n+k−1}}{q_{n+k−2}} é uma fração irredutivel de denominador

q_{n+k−2} > q_{n−2} , donde \frac{q_{n−1}}{q_{n−2}} ≠ \frac{q_{n+k−1}}{q_{n+k−2}} ⇒ q_{n−1} q_{n+k−2} − q_{n−2} q_{n+k−1} ≠ 0.

Vamos provar agora um resultado devido a Lagrange segundo o qual se x é uma irracionalidade quadrática, isto é, se x é um irracional do tipo r + \sqrt{s}, r, s ∈ ℚ, s > 0 então a fração contínua de x é periódica, i.e., existem n ∈ ℕ, k ∈ ℕ^{∗} com α_{n+k} = α_{n}. Neste caso, existem a, b, c inteiros tais que ax^{2} + bx + c = 0, com b^{2} − 4ac > 0 e \sqrt{b^{2} − 4ac} irracional. Como vimos na seção 1,

x = \frac{p_{n−1}α_{n} + p_{n−2}}{q_{n−1}α_{n} + q_{n−2}} ,

e portanto

ax^{2} + bx + c = 0 ⇒ a(\frac{p_{n−1}α_{n} + p_{n−2}}{q_{n−1}α_{n} + q_{n−2}} )^{2} + b(\frac{p_{n−1}α_{n} + p_{n−2}}{q_{n−1}α_{n} + q_{n−2}} ) + c = 0
⇒ A_{n}α_{n}^{2} + B_{n}α_{n} + C_{n} = 0,

onde

A_{n} = a p_{n−1}^{2} + b p_{n−1}q_{n−1} + c q_{n−1}^{2}
B_{n} = 2a p_{n−1}p_{n−2} + b(p_{n−1}q_{n−2} + p_{n−2}q_{n−1}) + 2c q_{n−1}q_{n−2}
C_{n} = a p_{n−2}^{2} + b p_{n−2}q_{n−2} + c q_{n−2}^{2} .

Note que C_{n} = A_{n−1} . Vamos provar que existe M > 0 tal que 0 < |A_{n}| ≤ M para todo n ∈ ℕ, e portanto 0 < |C_{n}| ≤ M, ∀ n ∈ ℕ:

A_{n} = a p_{n−1}^{2} + b p_{n−1}q_{n−1} + c q_{n−1}^{2} = a q_{n−1}^{2}(x − \frac{p_{n−1}}{q_{n−1}} )(x̄ − \frac{p_{n−1}}{q_{n−1}} ),

onde x e x̄ são as raízes de a, X^{2} + b X + c = 0, mas

|x − \frac{p_{n−1}}{q_{n−1}} | < \frac{1}{q_{n−1}^{2}} ≤ 1 ⇒ |A_{n}| = a q_{n−1}^{2} |x − \frac{p_{n−1}}{q_{n−1}} | |x̄ − \frac{p_{n−1}}{q_{n−1}} |

≤ a(|x̄ − x| + |x − \frac{p_{n−1}}{q_{n−1}} | ) ≤ a(|x̄ − x| + 1) =: M.

Notemos agora que B_{n}^{2} − 4A_{n}C_{n} = b^{2} − 4ac, ∀ n ∈ ℕ. De fato, B_{n}^{2} − 4A_{n}C_{n} = (p_{n−1}q_{n−2} − p_{n−2}q_{n−1})^{2}(b^{2} − 4ac) = b^{2} − 4ac. Portanto, B_{n}^{2} ≤ 4A_{n}C_{n} + b^{2} − 4ac = 4M^{2} + b^{2} − 4ac ⇒ B_{n} ≤ M′ = \sqrt{4M^{2} + b^{2} − 4ac}, ∀ n ∈ ℕ.

Provamos assim que A_{n}, B_{n} e C_{n} estão uniformemente limitados, donde há apenas um número finito de possíveis equações A_{n}X^{2} + B_{n}X + C_{n} = 0, e portanto de possíveis valores de α_{n}. Assim, necessariamente α_{n+k} = α_{n} para alguma escolha de n ∈ ℕ, k ∈ ℕ^{∗}.

Aplicação: A equação de Pell.

Seja A um inteiro positivo. Estamos interessados na equação x^{2}−Ay^{2} = 1, com x e y inteiros. Se A é um quadrado perfeito, digamos a = k^{2}, temos que x^{2} − Ay^{2} = (x − ky)(x + ky) = 0 admite apenas as soluções triviais y = 0, x = ±1, pois teríamos x − ky = x + ky = ±1. o caso itneressante é quando A não é um quadrado pergeito, e portanto \sqrt{A} é um irracional (de fato, se \sqrt{A} = \frac{p}{q}, com mdc(p, q) = 1 e q > 1, teríamos A = \frac{p^{2}}{q^{2}} o que é um absurdo, pois mdc(p, q) = 1 ⇒ mdc(p^{2}, q^{2}) = 1, donde p^{2}/q^{2} não pode ser inteiro). nesse caso, a equação x^{2} − Ay^{2} = 1 é conhecida como uma equação de Pell. Nosso resultado principal é o seguinte:

Teorema 3.1: A equação x^{2} − Ay^{2} = 1 tem infinitas soluções inteiras (x, y). Além disso, as soluções com x e y inteiros positivos podem ser enumeradas por (x_{n}, y_{n}), n ≥ 0 de modo que, para todo n, x_{n} + y_{n}\sqrt{A} = (x_{1} + y_{1}\sqrt{A})^{n}, e portanto

x_{n} = \frac{(x_{1} + y_{1}\sqrt{A})^{n} + (x_{1} − y_{1}\sqrt{A})^{n}}{2} e y_{n} = \frac{(x_{1} + y_{1}\sqrt{A})^{n} + (x_{1} − y_{1}\sqrt{A})^{n}}{2\sqrt{A}} .

Observação: As seqüências (x_{n}) e (y_{n}) acma satisfazem a recorrência u_{n+2} = 2x_{0}u_{n+1} − u_{n}, ∀ n ≥ 1.

Dem: Observemos inicialmente que, se D = \{x + y\sqrt{A} | x, y ∈ ℤ\} então N: D → D, N(x + y\sqrt{A}) = x^{2} − Ay^{2} é uma função multiplicativa, isto é,

N((x + y\sqrt{A})(u + v\sqrt{A})) = N(x + y\sqrt{A})N(u + v\sqrt{A}), ∀ x, y, u, v ∈ ℤ.

De fato,

N((x + y\sqrt{A})(u + v\sqrt{A})) = N((xu + ayv) + (xv + yu)\sqrt{A}) = (xu + Ayv)^{2} − A(xv + yu)^{2}
= x^{2}u^{2} + A^{2}y^{2}v^{2} − A(x^{2}v^{2} + y^{2}u^{2}) = (x^{2} − Ay^{2})(u^{2} − Av^{2}).

Usaremos agora o fato de que, como \sqrt{A} é irracional, a desigualdade |\sqrt{A}− \frac{p}{q}| < \frac{1}{q^{2}} tem infinitas soluções racionais p/q. Note que se |\sqrt{A} − \frac{p}{q}| < \frac{1}{q^{2}} então

|p^{2} − Aq^{2}| = |p − q\sqrt{A}||p + q\sqrt{A}| = q|\sqrt{A} − \frac{p}{q}||p + q\sqrt{A}| < q · \frac{1}{q^{2}} · |p + q\sqrt{A}|

= |\frac{p}{q} + \sqrt{A}| ≤ 2\sqrt{A} + |\sqrt{A} − \frac{p}{q}| < 2\sqrt{A} + 1.

Considerando infinitos pares de inteiros positivos (p_{n}, q_{n}) com |\sqrt{A} − \frac{p_{n}}{q_{n}} | < \frac{1}{q_{n}^{2}} , teremos sempre |p_{n} − Aq_{n}^{2}| < 2\sqrt{A} + 1, e portanto temos um número finito de possibilidades para o valor (inteiro) de p_{n} − Aq_{n}^{2}. consequentemente, existe um inteiro k ≠ 0 tal que p_{n} − Aq_{n}^{2} = k para infinitos valores de n. Obtemos portanto duas seqüências crescentes de pares de inteiros positivos u_{r}), (v_{r}), r ∈ ℕ tais que u_{r}^{2} − kv_{r}^{2} = k para todo r.

Como há apenas |k|^{2} possibilidades para os pares (\overline{u}_{r}(mod |k|), \overline{v}_{r}(mod |k|)), axistem inteiros a e b e infinitos valores de r tais que u_{r} ≡ a(mod |k|) e v_{r} ≡ b(mod |k|). Tomamos então r < s com as propriedades acima. Seja

x + y\sqrt{A} = \frac{u_{s} + v_{s}\sqrt{A}}{u_{r} + v_{r}\sqrt{A}} = \frac{(u_{s} + v_{s}\sqrt{A})(u_{r} − v_{r}\sqrt{A})}{u_{r}^{2} − Av_{r}^{2}}

= \frac{u_{s}u_{r} − Av_{s}v_{r}}{k} + (\frac{u_{r}v_{s} − u_{s}v_{r}}{k} ) \sqrt{A}.

Temos u_{s}u_{r} − Av_{s}V_{r} ≡ u_{r}^{2} − Av_{r}^{2} = k ≡ 0(mod |k|) e u_{r}v_{s} − u_{s}v_{r} ≡ ab − ab = 0(mod |k|), e portanto x = \frac{u_{s}u_{r}−Av_{s}v_{r}}{k} e y = \frac{u_{r}v_{s}−u_{s}v_{r}}{k} são inteiros. Por outro lado, (x + y\sqrt{A})(u_{r} + v_{r}\sqrt{A}) = u_{s} + v_{s}\sqrt{A}, donde N(x + y\sqrt{A})N(u_{r} + v_{r}\sqrt{A}) = N(u_{s} + v_{s}\sqrt{A}). Como N(u_{r} + v_{r}\sqrt{A}) = N(u_{s} + v_{s}\sqrt{A}) = k, segue que N(x + y\sqrt{A}) = x^{2} − Ay^{2} = 1. Além disso, como s > r, u_{s} + v_{s}\sqrt{A} > u_{r} + v_{r}\sqrt{A}, donde x + y\sqrt{A} = \frac{u_{s}+v_{s}\sqrt{A}}{u_{r}+v_{r}\sqrt{A}} > 1.

Sejam agora x_{1}, y_{1} ∈ ℤ tais que x_{1} + y_{1}\sqrt{A} > 1 e x_{1}^{2} − Ay_{1}^{2} = 1 com x_{1} + y_{1}\sqrt{A} mínimo. Temos então (x_{1} + y_{1}\sqrt{A})^{−1} = x_{1} − y_{1}\sqrt{A}. Vamos mostrar que, se x̃ + ỹ\sqrt{A} > 1 e x̃^{2} − Aỹ^{2} = 1 (com x̃ e ỹ inteiros) então x̃ + ỹ\sqrt{A} = (x_{1} + y_{1}\sqrt{A})^{n} para algum inteiro positivo n. Para isso, tome n ≥ 1 tal que (x_{1} + y_{1}\sqrt{A})^{n} ≤ x̃ + ỹ\sqrt{A} < (x_{1} + y_{1}\sqrt{A})^{n+1}. Temos então 1 ≤ (x̃ + ỹ\sqrt{A})(x_{1} − y_{1}\sqrt{A})^{n} < x_{1} + y_{1}\sqrt{A}. Se u + v\sqrt{A} = (x̃ + ỹ\sqrt{A})(x_{1} − y_{1}\sqrt{A})^{n}, com u e v inteiros, temos

u^{2} − Av^{2} = N(u + v\sqrt{A}) = N(x̃ + ỹ\sqrt{A})N(x_{1} − y_{1}\sqrt{A})^{n} = 1,

donde u + v\sqrt{A} = 1, pela minimalidade de x_{1} + y_{1}\sqrt{A}, pois 1 ≤ u + v\sqrt{A} < x_{1} + y_{1}\sqrt{A}. Note finalmente que se x e y são inteiros e x^{2} − Ay^{2} = 1 então x + y\sqrt{A} > 1 equivale a termos x e y positivos, pois temos 0 < (x + y\sqrt{A})^{−1} = x − y\sqrt{A} < 1, donde x = ^{\frac{(x+y\sqrt{A})+(x−y\sqrt{A})}{2}} e y = \frac{(x+y\sqrt{A})−(x−y\sqrt{A})}{2\sqrt{A}} são positivos. ■

Propriedades Estatísticas de Frações Contínuas e Aproximações Diofantinas: O Teorema de Khintchine

Introdução:

O problema básico da teoria de aproximações diofantinas é o de estudar boas aproximações de números reais por números racionais. Uma extensão natural desse problema é o estudo de aproximações simultâneas de n números reais por números racionais com o mesmo denominador.

Dado um número irracional α, um resultado clássico de Dirichlet (que já provamos usando frações contínuas) afirma que existem infinitos racionais \frac{p}{q} tais que |α − \frac{p}{q}| < \frac{1}{q^{2}} (vejamos outra prova simples: dado N ∈ ℕ, consideramos os N + 1 elementos de [0, 1) da forma jα − ⌊jα⌋, com 0 ≤ j ≤ N. Como [0, 1) = ⋃_{k=0}^{N−1} [\frac{k}{N} , \frac{k+1}{N}), existem dois desses elementos, digamos j_{1}α − ⌊j_{1}α⌋ e j_{2}α − ⌊j_{2}α⌋ num mesmo intervalo ⌊\frac{k}{N} , \frac{k+1}{N}), e portanto, se j_{1} < j_{2}, q = j_{2} − j_{1} e p = ⌊j_{2}α⌋ − ⌊j_{1}α⌋, temos 0 < |qα − p| < \frac{1}{N} ⇒ |α − \frac{p}{q}| < \frac{1}{qN} ≤ \frac{1}{q^{2}} ). Hurwitz e Markov provaram que de fato |α − \frac{p}{q}| < \frac{1}{\sqrt{5}q^{2}} tem infinitas soluções \frac{p}{q} ∈ ℚ, para todo irracional α, e que \sqrt{5} é a maior constante com essa propriedade. Markov ([Ma]) provou que, para todo c < 3, o conjunto dos α ∈ ℝ tais que |α − \frac{p}{q}| < \frac{1}{cq^{2}} tem apenas um número finito de soluções \frac{p}{q} ∈ ℚ é enumerável, mas o conjunto dos α ∈ ℝ tais que |α − \frac{p}{q}| < \frac{1}{3q^{2}} tem apenas um número finito de soluções tem o mesmo cardinal que ℝ.

Neste artigo, vamos estudar desigualdades do tipo

|α − \frac{p}{q}| < \frac{f(q)}{q},  (1)

onde f: ℕ → ℝ^{+} é uma função decrescente, do ponto de vista da teoria da medida. Vamos provar o teorema de Khintchine, segundo o qual, se ∑_{q=1}^{∞} f(q) = +∞ então (1) tem infinitas soluções \frac{p}{q} ∈ ℚ, para quase todo α ∈ ℝ, mas se ∑_{q=1}^{∞} f(q) < +∞ então (1) tem apenas um número finito de soluções \frac{p}{q} ∈ ℚ, para quase todo α ∈ ℝ.

Note que do ponto de vista topológico a situação é diferente: qualquer que seja a função positiva f, (1) tem infinitas soluções \frac{p}{q} ∈ ℚ para α ∈ R_{f}, onde R_{f} é um conjunto residual, i.e. contém (de fato é) uma interseção enumerável de abertos densos.

A principal técnica usada para estudar aproximações de números reais por números racionais são as frações contínuas, que fornecem todas as boas aproximações de um irracional α por racionais. As definições e provas dos resultados a seguir sobre frações contínuas podem ser encontradas em [Mo].

Dado α ∈ ℝ, definimos α_{0} = α, a_{n} = ⌊α_{n}⌋ e, se α_{n} ∉ ℤ, α_{n+1} = \frac{1}{α_{n}−a_{n}}, para todo n ∈ ℕ. Para cada n ∈ ℕ tomamos p_{n} ∈ ℤ e q_{n} ∈ ℕ^{∗} primos entre si tais que

\frac{p_{n}}{q_{n}} = [a_{0}; a_{1}, a_{2}, …, a_{n}] := a_{0} + \frac{1}{a_{1} + _{\frac{1}{a_{2}+_{...}_{+ \frac{1}{an}}}}} .

Temos

\frac{1}{(a_{n+1} + 2)q_{n}^{2}} < |α − \frac{p_{n}}{q_{n}} | < \frac{1}{a_{n+1}q_{n}^{2}} ≤ \frac{1}{q_{n}^{2}} , para todo n ∈ ℕ.

As seqüências p_{n} e q_{n} satisfazem p_{n+1}q_{n}−p_{n}q_{n+1} = (−1)^{n}, ∀ n ≥ 0. Se |α−\frac{p}{q}| < \frac{1}{2q^{2}} então \frac{p}{q} = \frac{p_{n}}{q_{n}}, para algum n ∈ ℕ. Por outro lado, para todo n ∈ ℕ vale |α − \frac{p_{n}}{q_{n}} | < \frac{1}{2q_{n}^{2}} ou |α − \frac{p_{n+1}}{q_{n+1}} | < \frac{1}{2q_{n+1}^{2}} .

Temos

p_{n+2} = a_{n+2}p_{n+1} + p_{n}, q_{n+2} = a_{n+2}q_{n+1} + q_{n} e α = \frac{α_{n+1}p_{n} + p_{n−1}}{α_{n+1}q_{n} + q_{n−1}} , para todo n ∈ ℕ.

A prova que apresentaremos na Seção 1, baseada no estudo de propriedades estatísticas de frações contínuas, é inspirada em conversas que tive há uns 9 anos com o Prof. Nicolau Corção Saldanha sobre o tema.

O problema básico de aproximações simultâneas é o seguinte: dado α_{1}, α_{2}, …, α_{n} ∈ ℝ queremos encontrar números racionais \frac{p_{1}}{q} , \frac{p_{2}}{q} , …, \frac{p_{n}}{q} tais que |α_{j} − \frac{p_{j}}{q} | seja pequeno para todo j ≤ n. Em geral sempre é possível encontrar racionais tais que |α_{j}−\frac{p_{j}}{q} | < \frac{1}{q^{1+1/n}}, o que estende o teorema de Dirichlet e pode ser provado de modo análogo: dado N ∈ ℕ consideramos os N^{n} + 1 pontos

p_{j} = (α_{1}j − ⌊α_{1}j⌋, α_{2}j − ⌊α_{2}j⌋, …, α_{n}j − ⌊α_{n}j⌋), 0 ≤ j ≤ N^{n}

no hipercubo [0, 1)^{n}. Dividimos [0, 1)^{n} como (⋃_{k=0}^{N−1} [\frac{k}{N} , \frac{k+1}{N}))^{n} em N^{n} cubos de lado \frac{1}{N}. Haverá necessariamente dois pontos p_{j_{1}} e p_{j_{2}} num mesmo cubo dessa decomposição, e, se j_{1} < j_{2}, q = j_{2} − j_{1}, p_{j} = ⌊j_{2}α_{j}⌋ − ⌊j_{1}α_{j}⌋, teremos |α_{j} − \frac{p_{j}}{q_{j}} | < \frac{1}{Nq_{j}} ≤ _{\frac{1}{q_{j}^{1+1/n}}}, para todo j ≤ n.

Infelizmente não há um substituto satisfatório para a teoria de frações contínuas em dimensão maior que um, mas é possível provar uma versão n-dimensional do Teorema de Khinchine (provada originalmente em [K]), o que faremos na Seção 2.

Para maiores informações sobre aproximações diofantinas, veja [C1] e [S].

1 O Teorema de Khintchine via frações contínuas

Teorema 1.1: (Khintchine) Seja f: ℕ → ℝ^{+} uma função decrescente tal que h(n) = nf(n): ℕ → ℝ^{+} também seja decrescente.

a) Se ∑_{n=1}^{∞} f(n) < +∞ então a equação |α − \frac{p}{q}| < \frac{f(q)}{q} tem apenas um número finito de soluções racionais p/q, para quase todo α ∈ ℝ/ℚ

b) Se ∑_{n=1}^{∞} f(n) = +∞ então a equação |α − \frac{p}{q}| < \frac{f(q)}{q} tem um número infinito de soluções racionais p/q, para quase todo α ∈ ℝ/ℚ.

Observação: A condição de nf(n) ser decrescente não é de fato necessária, como veremos na seção 2, mas simplifica a prova. Por outro lado, não podemos retirar a hipótese de f ser decrescente (veja [C2]).

Dem:

Lema 1.2: Sejam n, k ∈ ℕ, e seja [0, a_{1}, a_{2}, …] a fração contínua de um número α ∈ [0, 1]. A probabilidade de um termo a_{n+1} ser igual a k dado que a_{1} = k_{1}, a_{2} = k_{2}, …, a_{n} = k_{n} está entre 1/(k + 1)(k + 2) e 2/k(k + 1), ∀ k_{1}, k_{2}, …, k_{n} ∈ ℕ^{∗}.

Dem: Sejam p_{n−1}/q_{n−1} = [0; a_{1}, a_{2}, …, a_{n−1}] e p_{n}/q_{n} = [0; a_{1}, a_{2}, …, a_{n−1}, a_{n}]. Se α ∈ [0, 1], α = [0; a_{1}, a_{2}, …, a_{n}, α_{n+1}], α_{n+1} ∈ [1, +∞) então α ∈ [\frac{p_{n}+p_{n−1}}{q_{n}+q_{n−1}} , \frac{p_{n}}{q_{n}} ), e, se além disso a_{n+1} = k, temos α ∈ [\frac{kp_{n}+p_{n−1}}{kq_{n}+q_{n−1}} , \frac{(k+1)p_{n}+p_{n−1}}{(k+1)q_{n}+q_{n−1}} ], e valem as recíprocas (as ordens dos extremos dos intervalos podem estar trocadas). Os comprimentos dos referidos intervalos são, respectivamente, \frac{1}{q_{n}(q_{n}+q_{n−1})} e \frac{1}{(kq_{n}+q_{n−1})((k+1)q_{n}+q_{n−1})} (pois |p_{n}q_{n−1} − p_{n−1}q_{n}| = 1), e portanto a razão entre seus comprimentos é \frac{q_{n}(q_{n}+q_{n−1})}{(kq_{n}+q_{n−1})((k+1)q_{n}+q_{n−1})} = \frac{1+β}{(k+β)(k+1+β)}, onde β = q_{n−1}/q_{n} ∈ [0, 1]. Portanto, a razão pertence a [1/(k + 1)(k + 2), 2/k(k + 1)]. ■

Corolário 1.3: A probabilidade de a_{n+1} ≥ k, nos termos do Lema acima, pertence a [1/(k + 1), 2/k].

Lema 1.4: Para quase todo α ∈ ℝ existe c ∈ ℝ tal que q_{n} ≤ c^{n}, para todo n ∈ ℕ.

Antes de provar o Lema 1.4 vamos mostrar como termina a prova do Teorema de Khintchine. Suponhamos que Σf(n) < ∞. Seja γ = \frac{1+\sqrt{5}}{2}. Se a aproximação p_{n}/q_{n} de α é tal que |α − \frac{p_{n}}{q_{n}} | < \frac{f(q_{n})}{q_{n}} então a_{n+1} + 2 > \frac{1}{q_{n}f(q_{n})} > \frac{1}{γ^{n−1}f(γ^{n−1})} (pois para todo α ∈ ℝ \ ℚ vale q_{n} > γ^{n−1}, ∀ n ∈ ℕ). ⇒ a_{n+1} > \frac{1}{γ^{n−1}f(γ^{n+1})} − 2. A probabilidade de a_{n+1} ≤ \frac{1}{γ^{n−1}f(γ^{n−1})} − 2 =: A(n) é pelo menos 1 − \frac{2}{A(n)}, ∀ n ∈ ℕ (pelo corolário do Lema 1.2), e a hipótese de ∑_{n=1}^{∞} f(n) < ∞ implica que ∑_{n=1}^{∞} \frac{2}{A(n)} < ∞, por comparação com

∑_{k=1}^{∞} γ^{k}f(γ^{k}) < \frac{γ}{γ − 1} ∑_{k=0}^{∞}(γ^{k+1} − γ^{k})f(γ^{k+1}) < ∑_{n=1}^{∞} f(n) < +∞.

Temos portanto ∏_{n=1}^{∞}(1 − \frac{2}{A(n)}) > 0 ⇒ para cada ε > 0 existe n_{0} ∈ ℕ tal que ∏_{n=n_{0}}^{∞}(1 − \frac{2}{A_{n}}) > 1 − ε, donde com probabilidade total a_{n+1} ≤ A(n) para todo n suficientemente grande ⇒ |α − \frac{p}{q}| < \frac{f(q)}{q} tem apenas um número finito de soluções.

Suponhamos agora que Σf(n) = +∞, fixemos c > 0 e vamos nos restringir ao conjunto X_{c} dos α ∈ [0, 1] tais que q_{n} < c^{n} para todo n ∈ ℕ (a união dos conjuntos X_{c} para todo c ∈ ℕ tem probabilidade total em [0, 1], pelo Lema 1.4).

Se a_{n+1} > \frac{1}{q_{n}f(q_{n})} teremos |α − \frac{p_{n}}{q_{n}} | < \frac{f(q_{n})}{q_{n}}. Como q_{n} < c^{n}, \frac{1}{q_{n}f(q_{n})} < \frac{1}{c^{n}f(c^{n})}. Vamos mostrar que com probabilidade total temos a_{n+1} ≥ \frac{1}{c^{n}f(c^{n})} para infinitos valores de n ∈ ℕ. Isso segue de ∏_{n=1}^{∞} (1 − \frac{1}{B(n)+1}) = 0, onde B(n) = \frac{1}{c^{n}f(c^{n})}, que por sua vez segue de ∑_{n=1}^{∞} c^{n}f(c^{n}) ≥ c^{−1} ∑_{n=1}^{∞}(c^{n+1} − c^{n})f(c^{n}) = +∞. Portanto, para todo n_{0} ∈ ℕ temos ∏_{n=n_{0}}^{∞} (1 − \frac{1}{B(n)+1}) = 0, e, com probabilidade total, existe n ≥ n_{0} com a_{n+1} ≥ \frac{1}{c^{n}f(c^{n})}, donde a equação |α − \frac{p_{n}}{q_{n}} | < \frac{f(q_{n})}{q_{n}} é satisfeita com probabilidade total para infinitos valores de n ∈ ℕ. ■

Prova do Lema 1.4: Sejam n, k ∈ ℕ. A probabilidade de que k apareça pelo menos 4n/k(k+1) vezes entre a_{1}, a_{2}, …, a_{n} é limitada por ∑_{j=sn}^{n} C_{n}^{j}(\frac{s}{2})^{j}(1 − \frac{s}{2})^{n−j}, onde s = \frac{4}{k(k+1)}, que é menor que (\frac{3}{4})^{\frac{n}{k(k+1)}} para \frac{n}{k(k+1)} grande (de fato, \frac{C_{n}^{j+1}( \frac{s}{2} )^{j+1}(1− \frac{s}{2} )^{n−j−1}}{C_{n}^{j}( \frac{s}{2} )^{j}(1− \frac{s}{2} )^{n−j}} = \frac{n−j}{j+1} · \frac{s}{2−s} < \frac{4−3s}{3s} · \frac{s}{2−s} = \frac{4−3s}{6−3s} < \frac{2}{3}, se j ≥ \frac{3sn}{4}, logo, como ∑_{j=0}^{n} C_{n}^{j}(\frac{s}{2})^{j}(1 − \frac{s}{2})^{n−j} = 1, para j = \frac{3sn}{4}, C_{n}^{j}(\frac{s}{2})^{j}(1 − \frac{s}{2})^{n−j} ≤ 1, donde C_{n}^{sn}(\frac{s}{2})^{sn}(1 − \frac{s}{2})^{(1−s)n} ≤ (\frac{2}{3})^{sn/4} e ∑_{j=sn}^{n} C_{n}^{j}(\frac{s}{2})^{j}(1 − \frac{s}{2})^{n−j} ≤ (\frac{2}{3})^{sn/4} ∑_{k=0}^{∞}(\frac{2}{3})^{k} = 3(\frac{2}{3})^{sn/4} = 3(\frac{2}{3})^{n/k(k+1)} < (\frac{3}{4})^{n/k(k+1)}, se n/k(k + 1) é suficientemente grande). A probabilidade disso acontecer pra algum k < [\sqrt[3]{n}] é no máximo \sqrt[3]{n} · (\frac{3}{4})^{\sqrt[3]{n}}, que converge a zero quando n → +∞. Por outro lado, com probabilidade total, a_{n} < n^{2} para todo n suficientemente grande ⇒ q_{n} < ∏_{k=1}^{n}(a_{k} + 1) < (∏_{r=1}^{^{3} \sqrt{n}}(r + 1)^{\frac{4n}{r(r+1)}} ) · (n^{2})^{4n/ \sqrt[3]{n}} com probabilidade total para todo n grande, pois também com probabilidade total o número de termos maiores ou iguais a \sqrt[3]{n} entre a_{1}, a_{2}, …, a_{n} é no máximo 4n/\sqrt[3]{n}, para n suficientemente grande.

Como lim_{n→∞} 8 log n/\sqrt[3]{n} = 0, temos com probabilidade total

lim sup_{n→∞} \sqrt[n]{q_{n}} ≤ exp (∑_{r=1}^{∞} \frac{4 log(r + 1)}{r(r + 1)}) < +∞.

■

Observação: Pode-se provar com métodos de teoria ergódica que para quase todo α ∈ ℝ vale

lim_{n→∞} \sqrt[n]{q_{n}} = e^{π^{2}/12 ln 2} ≃ 3, 2758229 …

Pretendemos discutir este e outros resultados finos ligados a propriedade estatísticas de frações contínuas num próximo artigo.

Corolários do Teorema de Khintchine:

i) Para quase todo α ∈ ℝ, |α− \frac{p}{q}| < \frac{1}{q^{2} log^{2} q} tem apenas um número finito de soluções \frac{p}{q} ∈ ℚ, e portanto |α − \frac{p}{q}| < \frac{1}{q^{2+ε}} tem apenas um número finito de soluções racionais \frac{p}{q}, para todo ε > 0. Em particular ord α = 2 para quase todo α ∈ ℝ (onde ord α := inf{ν > 0||α − \frac{p}{q}| < \frac{1}{q^{ν}} tem infinitas soluções \frac{p}{q} ∈ ℚ\}).

ii) Para quase todo α ∈ ℝ, |α − \frac{p}{q}| < \frac{1}{q^{2} log q} tem infinitas soluções racionais p/q, e portanto, para todo k ∈ ℝ, |α − \frac{p}{q}| < \frac{1}{kq^{2}} tem infinitas soluções \frac{p}{q} ∈ ℚ.

2 O Teorema de Khintchine n-dimensional

Teorema 2.1: Sejam f_{1}, f_{2}, …, f_{n}: ℕ → ℝ^{+} funções decrescentes e F: ℕ → ℝ^{+} dada por F (k) = f_{1}(k)f_{2}(k) … f_{n}(k). Seja α = (α_{1}, …, α_{2}, …, α_{n}) ∈ ℝ^{n}. O sistema de aproximação simultâneas

|α − \frac{p_{i}}{q} | < \frac{f_{i}(q)}{q}, 1 ≤ i ≤ n é tal que  (∗)

a) Se ∑_{q=1}^{∞} F (q) < +∞ então (*) tem apenas um número finito de soluções (\frac{p_{1}}{q} , \frac{p_{2}}{q} , …, \frac{p_{n}}{q} ) ∈ ℚ^{n}, para quase todo α ∈ ℝ^{n}

b) Se ∑_{q=1}^{∞} F (q) = +∞ então (*) tem infinitas soluções (\frac{p_{1}}{q} , …, \frac{p_{n}}{q} ) ∈ ℚ^{n} para quase todo α ∈ ℝ^{n}.

Dem: Dem. de a): Dado q_{0} ∈ ℕ, consideremos o conjunto

S(q_{0}) = ⋃_{q≥q_{0}} ⋃_{0≤p_{1},...,p_{n}<q} ∏_{i=1}^{n} (\frac{p_{i}}{q} − \frac{f_{i}(q)}{q}, \frac{p_{i}}{q} + \frac{f_{i}(q)}{q}) ,

que é o conjunto dos α ∈ [0, 1)^{n} tais que a desigualdade (*) do enunciado do Teorema tem alguma solução com q ≥ q_{0} (e logo ⋂_{q_{0}∈ℕ} S(q_{0}) é o conjunto dos α ∈ ℝ^{n} tais que (*) tem infinitas soluções (\frac{p_{i}}{q} , …, \frac{p_{n}}{q}) ∈ ℚ^{n}). Temos m(S(q_{0})) ≤ ∑_{q=q_{0}}^{∞} q^{n}(\frac{2^{n}F (q)}{q^{n}}) = 2^{n} ∑_{q=q_{0}}^{∞} F (q), que tende a 0 quando q tende a ∞, pois ∑_{q=1}^{∞} F (q) converge. Portanto, m(⋂_{q_{0}∈ℕ} S(q_{0})) = 0.

Dem. de b): Primeiro obtemos funções decrescentes g_{1}, g_{2}, …, g_{n}: ℕ → ℝ^{+} tais que lim_{q→s_{0}} \frac{g_{i}(q)}{f_{i}(q)} = 0 e G = g_{1}, g_{2}, …, g_{n}: ℕ → ℝ^{+} satisfaz lim_{q→∞} qG(q) = 0 e ∑_{q=1}^{∞} G(q) = +∞ (podemos tomar G_{1}(k) = (F (1) + F (2) + ⋯ + F (k))^{−1} · F (k) e G(k) = (G_{1}(1) + G_{1}(2) + ⋯ + G_{1}(k))^{−1}G_{1}(k), ∀ k ∈ ℕ. Teremos G_{1} e G decrescentes, G_{1}(k) ≤ 1/k, kG(k) → 0, ΣG_{1}(k) = ∞, ΣG(k) = ∞, e definimos g_{i}(q) = f_{i}(q) · (G(q)/F (q))^{1/n}).

Fixemos agora q_{0} ∈ ℕ grande e definimos s_{0} = s_{0}(q_{0}) = min{s ∈ ℕ|G(q_{0}) + G(q_{0} + 1) + ⋯ + G(s) ≥ c̃\}, onde c̃ é uma constante que escolheremos posteriormente. Note que lim_{q→∞} \frac{s_{0}(q)}{q} = +∞.

Para cada s com q_{0} ≤ s ≤ s_{0} vamos estimar o número de (\frac{r_{1}}{s} , \frac{r_{2}}{s} , …, \frac{r_{n}}{s} ) ∈ ℚ^{n} com r_{i} ∈ ℤ, 1 ≤ i ≤ n, 0 ≤ r_{i} < s tais que existem q com q_{0} ≤ q < s, p_{1}, p_{2}, …, p_{n} ∈ ℤ, 0 ≤ p_{i} < q satisfazendo

|\frac{r_{i}}{s} − \frac{p_{i}}{q} | < \frac{g_{i}(q)}{q} + \frac{g_{i}(s)}{s}, ∀ i = 1, 2, …, n.  (∗∗)

Temos que, como cada g_{i} é decrescente, (**) implica

|r_{i}q − p_{i}s| < 2qs\frac{g_{i}(q)}{q} = 2sg_{i}(q), i = 1, 2, …, n.

Para um tal (\frac{r_{1}}{s} , …, \frac{r_{n}}{s} ) que não satisfaz (**) para nenhum q com q_{0} ≤ q < s, p_{1}, …, p_{n} o bloco ∏_{i=1}^{n} (\frac{r_{i}}{s} − \frac{g_{i}(s)}{s}, \frac{r_{i}}{s} + \frac{g_{i}(s)}{s}) será disjunto de todos os blocos associados a (\frac{p_{1}}{q} , …, \frac{p_{n}}{q} ), ∀ q com q_{0} ≤ q < s, ∀ p_{1}, …, p_{n} ∈ ℤ com 0 ≤ p_{i} < q.

Lema 2.2: Para todo k ∈ ℕ existe c_{k} > 0 tal que ∑_{j=1}^{n} (\frac{φ(j)}{j})^{k} ≥ c_{k}n.

Dem: Para k = 1 segue de

lim_{n→∞} \frac{1}{n} ∑_{j=1}^{n} \frac{φ(j)}{j} = lim_{n→∞} \frac{1}{n} ∑_{q=1}^{n} ∑_{d|q} \frac{μ(d)}{d}

= lim_{n→∞} \frac{1}{n} ∑_{d=1}^{n}⌈\frac{n}{d}⌉\frac{μ(d)}{d}

= ∑_{d=1}^{∞} \frac{μ(d)}{d^{2}}

= \frac{6}{π^{2}}

pois ∑_{r=1}^{∞} \frac{μ(m)}{m^{2}} ∑_{k=1}^{∞} \frac{1}{k^{2}} = ∑_{n=1}^{∞} ^{\frac{∑_{m|n} μ(m)}{n^{2}}} = 1, e ∑_{k=1}^{∞} \frac{1}{k^{2}} = \frac{π^{2}}{6} . Como h(x) = x^{k} é convexa para k ≥ 1, temos \frac{1}{n} ∑_{j=1}^{n} (\frac{φ(j)}{j})^{k} ≥ (\frac{1}{n} ∑_{j=1}^{n} \frac{φ(j)}{j})^{k}, donde segue o resultado (com C_{k} = (\frac{6}{π^{2}} )^{k}).

■

Se q_{0} ≤ q < s, o número de soluções de |r_{i}q − p_{i}s| < 2sg_{i}(q) com 0 ≤ p_{i} < q, 0 ≤ r_{i} < s é no máximo 4sg_{i}(q) desde que mdc(r_{i}, s) = 1. De fato, nessas condições r_{i}q − p_{i}s não se anula, senão teríamos \frac{p_{i}}{q} = \frac{r_{i}}{s}, que é uma fração irredutível de denominador s > q, absurdo. Seja d = mdc(s, q). Dado k ∈ ℤ, a equação diofantina rq − ps = k só tem solução de d|k, quando tem d soluções com 0 ≤ r < s. Portanto, 0 < rq − ps < x (resp. −x < rq − ps < 0) tem no máximo d⌊\frac{x}{d}⌋ ≤ x soluções (p, r) com 0 ≤ r < s, o que claramente implica a afirmação.

Portanto, o número de soluções da desigualdade acima para todo i com 1 ≤ i ≤ n é no máximo 4^{n}s^{n}G(q). Por outro lado há φ(s)^{n} pontos (\frac{r_{i}}{s} , …, \frac{r_{n}}{s} ), 0 ≤ r_{i} < s, mdc(r_{i}, s) = 1, 1 ≤ i ≤ n. Isso nos dá a estimativa do número de novos blocos disjuntos dos anteriormente considerados que têm denominador s de pelo menos φ(s)^{n} − 4^{n}s^{n} ∑_{q=q_{0}}^{s−1} G(q), e para o volume da união dos blocos disjuntos adicionados até o denominador s_{0} de pelo menos

∑_{s=q_{0}}^{s_{0}}(φ(s)^{n} − 4^{n}s^{n} ∑_{q=q_{0}}^{s−1} G(q))\frac{2^{n}G(s)}{s^{n}}

= 2^{k} ∑_{s=q_{0}}^{s_{0}} (\frac{φ(s)}{s})^{n} G(s) − 8^{n} ∑_{s=q_{0}}^{s_{0}} (∑_{q=q_{0}}^{s−1} G(q)) G(s).

Por outro lado, com s_{0} = min{s ≥ q_{o}| ∑_{q=q_{0}}^{s} G(q) ≥ c̃}, temos

∑_{s=q_{0}}^{s_{0}} (\frac{φ(s)}{s})^{n} G(s) = ∑_{s=q_{0}}^{s_{0}−1}(G(s) − G(s + 1)) ∑_{j=q_{0}}^{s} (\frac{φ(j)}{j})^{n} + G(s_{0}) ∑_{j=q_{0}}^{s_{0}} (\frac{φ(j)}{j})^{n}

≥ ∑_{s=q_{0}}^{s_{0}−1}(G(s) − G(s + 1))(c_{n}s − q_{0}) + G(s_{0})(c_{n}s_{0} − q_{0})

= c_{n} ∑_{s=q_{0}+1}^{s_{0}} G(s) − (1 − c_{n})q_{0}G(q_{0})

= c_{n}c̃ + ε_{1} onde ε_{1} → 0 quando q_{0} → ∞

(pois lim_{q_{0}→∞} q_{0}G(q_{0}) = 0).

Por outro lado, 8^{n} ∑_{s=q_{0}}^{s_{0}} (∑_{q=q_{0}}^{s−1} G(q)) G(s) ≤ 8^{n}c̃∑_{s=q_{0}}^{s_{0}} G(s) ≤ 8^{n}c̃(c̃ + ε_{2}) onde ε_{2} = G(s_{0}) → 0 quando q_{0} → ∞. Assim, nosso volume é, pelo menos, 2^{n}(c_{n}c̃ + ε_{1}) − 8^{n}c̃(c̃ + ε_{2}). Tomando c̃ = \frac{c_{n}}{4^{n+1}} temos que, se q_{0} é suficientemente grande (e logo ε_{1} e ε_{2} suficientemente pequenos), o volume de A(q_{0}) é pelo menos c_{n}^{2}/2^{n+3}, onde

A(q_{0}) = ⋃_{q≥q_{0}} ⋃_{0≤p_{1},...,p_{n}<q} ∏_{i=1}^{n} (\frac{p_{i}}{q} − \frac{g_{i}(q)}{q}, \frac{p_{i}}{q} + \frac{g_{i}(q)}{q}) .

Como A(q) ⊃ A(q + 1), ∀ q ∈ ℕ, temos m(A_{∞}) ≥ \frac{1}{15·2^{n}} > 0, onde A_{∞} = ⋂_{q∈ℕ} A(q). Se β = (β_{1}, β_{2}, …, β_{n}) ∈ A_{∞}, |β_{i}−\frac{p_{i}}{q} | < \frac{g_{i}(q)}{q}, i = 1, 2, …, n tem infinitas soluções (\frac{p_{1}}{q} , \frac{p_{1}}{q} , …, \frac{p_{n}}{q}) ∈ ℚ^{n}. Como m(A_{∞}) > 0, dado ε > 0 existe cubo Q = ∏_{i=1}^{n}[\frac{b_{i}}{C} , \frac{b_{i}+1}{C}], C ∈ ℕ, b_{i} ∈ ℤ, 0 ≤ b_{i} < C tal que m(A_{∞} ∩ Q) ≥ (1 − ε)m(Q). Se T: ℝ^{n} → ℝ^{n} é dada por

T (X_{1}, …, X_{n}) = (CX_{1} − b_{1}, CX_{2} − b_{2}, …, CX_{n} − b_{n}),

temos T (Q) = [0, 1]^{n} e m(T (Q∩A_{∞})) ≥ 1−ε. Além disso, se α = (α_{1}, α_{2}, …, α_{n}) ∈ T (Q∩A_{∞}), α = T (β), β = (β_{1}, …, β_{n}) ∈ A_{∞} ∩ Q, e portanto |β_{i} − \frac{p_{i}}{q} | < \frac{g_{i}(q)}{q}, para todo i = 1, 2, …, n tem infinitas soluções (\frac{p_{1}}{q} , \frac{p_{2}}{q} , …, \frac{p_{n}}{q}) ∈ ℚ^{n}, donde |α_{i} − \frac{r_{i}}{q} | < \frac{Cg_{i}(q)}{q} (e logo |α_{i} − \frac{r_{i}}{q} | < \frac{f_{i}(q)}{q}) tem infinitas soluções

(\frac{r_{1}}{q} , \frac{r_{2}}{q} , …, \frac{r_{n}}{q} ) = (\frac{Cp_{1} − b_{1}}{q} , \frac{Cp_{1} − b_{2}}{q} , …, \frac{Cp_{n} − b_{n}}{q} ) ∈ ℚ^{n},

e como ε > 0 pode ser feito arbitrariamente pequeno está provado o item b). ■

Apêndice: Aproximações diofantinas não-homogêneas

Proposição A.1: Se α ∈ ℝ \ ℚ então X = {m + nα|m, n ∈ ℤ} é denso em ℝ.

Dem: Dado ε > 0 existem p, q inteiros com > 1/ε tais que |α− \frac{p}{q}| < \frac{1}{q^{2}} ⇒ 0 < |qα−p| < \frac{1}{q} < ε. Dado x ∈ ℝ existe k ∈ ℤ tal que x está entre k(qα−p) e (k+1)(qα−p), donde |x−k(qα−p)| ≤ ε. Como k(qα − p) = −pk + qkα ∈ X, o resultado está provado. ■

O próximo resultado, devido a Kronecker, estende a Proposição A.1 para dimensão qualquer.

Proposição A.2: Seja α = (α_{1}, α_{2}, …, α_{n}) ∈ ℝ^{n}. Suponha que 1, α_{1}, …, α_{n} sejam linearmente inependentes sobre ℚ (isto é, k+m_{1}α_{1}+m_{2}α_{2}+⋯+m_{n}α_{n} = 0 com k, m_{1}, …, m_{n} ∈ ℤ implica k = m_{1} = ⋯ = m_{n} = 0). Então X = {kα+m_{1}e_{1} +m_{2}e_{2} +⋯+m_{n}e_{n}|k, m_{1}, …, m_{n} ∈ ℤ} é denso em ℝ^{n}, onde e_{1} = (1, 0, …, 0), …, e_{n} = (0, …, 0, 1) são os elementos da base canônica de ℝ^{n}.

Dem: Seja \overline{X} ⊂ ℝ^{n} o fecho de X, e V ⊂ \overline{X} um subespaço vetorial maximal de ℝ^{n} contido em \overline{X}. Suponhamos por absudo que V ≠ ℝ^{n}. Seja f um funcional linear não nulo de ℝ^{n}.

Seja V^{⊥} o complemento ortogonal de V, e seja π: ℝ^{n} → V^{⊥} a projeção ortogonal sobre V^{⊥}. Para todo x ∈ \overline{X}, π(x) ∈ \overline{X}, pois π(x) = x + (π(x) − x), π(x) − x ∈ C ⊂ \overline{X} e \overline{X} é invariante por adição (pois X também é).

Seja k = dim V^{⊥}. Escolhemos vetores e_{i_{1}}, e_{i_{2}}, …, e_{i_{k}} tais que π(e_{i_{1}}), π(e_{i_{2}}), …, π(e_{i_{k}}) geram V^{⊥}. Se fizermos e_{0} = α, para todo i = 0, 1, …, n escrevemos π(e_{i}) = ∑_{j=1}^{k} λ_{ij}π(e_{i_{j}}). Não podemos ter λ_{i1} ∈ ℚ para todo i, senão podemos definir um funcional linear f da seguinte forma: dado x ∈ ℝ^{n} escrevemos π(x) como ∑_{j=1}^{k} β_{j}π(e_{i_{j}}), e tomamos f(x) = β_{1}. Se λ_{i1} = f(e_{i}) ∈ ℚ para todo i, teríamos λ_{01} = f(α) = ∑_{i=1}^{n} α_{i}f(e_{i}) = ∑_{i=1}^{n} λ_{i1}α_{i} ∈ ℚ, contradizendo a hipótese da proposição.

Seja então i_{0} tal que λ_{i_{0}1} ∉ ℚ. Tomamos γ = (λ_{i_{0}1}, …, λ_{i_{0}k}) ∈ ℝ^{k}. Como observamos na introdução deste artigo, existem x_{n} = q_{n}γ − (p_{1n}, p_{2n}, …, p_{kn}) ≠ 0, com q_{n}, p_{1n}, …, p_{kn} ∈ ℤ

e lim_{n→∞} |x_{n}| ≤ lim_{n→∞} |q_{n}|^{−1/k} = 0, e portanto, se w_{n} = q_{n}π(e_{i_{0})} − ∑_{j=1}^{k} p_{jn}π(e_{i_{j}}), lim_{n→∞} w_{n} = 0 (e

w_{n} ≠ 0, ∀ n). Passando a uma subseqüência, se necessário, podemos supor que lim_{n→∞} \frac{w_{n}}{|w_{n}|} = w̃ ∈ S^{n−1} ∩ V^{⊥}. Para todo t ∈ ℝ, temos que tw̃ = lim_{n→∞}⌊\frac{t}{w_{n}} ⌋w_{n} ∈ \overline{X}, ∀ n ∈ ℕ. Portanto, como \overline{X} é invariante por adição, o subespaço Ṽ = \{v + tw̃|v ∈ V, t ∈ ℝ\} é tal que Ṽ ⊂ \overline{X} e Ṽ contém propriamente V, absurdo. ■

Observação: A hipótese da Proposição A.2 é necessária, pois se existem inteiros k, m_{1}, …, m_{n} não todos nulos tais que k + m_{1}α_{1} + ⋯ + m_{n}α_{n} = 0 então \overline{X} ⊂ \{(x_{1}, …, x_{n}) ∈ ℝ^{n}|m_{1}x_{1} + m_{2}x_{2} + ⋯ + m_{n}x_{n} ∈ ℤ}, que é um fechado com interior vazio.

Deixamos para o leitor a prova do seguinte fato: Dado α = (α_{1}, …, α_{n}) ∈ ℝ^{n} satisfazendo a condição da Proposição 2, e m ∈ ℕ, definimos {mα} = (mα_{1} − ⌊mα_{1}⌋, …, mα_{n} − ⌊mα_{n}⌋) ∈ [0, 1)^{n}. A seqüência {mα} é uniformemente distribuida, isto é, para todo aberto A ⊂ [0, 1)^{n}, se f_{A}(k) = #{m ≤ k|{mα} ∈ A}, então lim_{k→∞} f_{A}(k)/k = m(A), onde m(A) é a medida de Lebesgue de A. (Sugestão: sejam C_{1}, C_{2} ⊂ [0, 1)^{n} dois cubos abertos tais que \overline{C}_{2} está contido em um transladado de C_{1} (\overline{C}_{2} ⊂ C_{1} + v, v ∈ ℝ^{n}). Use o fato de que existem vetores ṽ arbitrariamente próximos de v, com ṽ = (qα_{1} + p_{1}, …, qα_{n} + p_{n}), q, p_{1}, …, p_{n} ∈ ℤ, e que {mα} ∈ C_{2} ⇒ {(m − q)α} ∈ C_{2} − ṽ ⊂ C_{1}, se ṽ está suficientemente próximo de v, donde

f_{C_{2}}(k) ≤ f_{C_{1}}(k) + |q| ⇒ lim sup_{k→∞} f_{C_{2}}(k)/k ≤ lim inf_{k→∞} f_{C_{1}}(k)/k).

Os Espectros de Markov e Lagrange

1 Definições e enunciados

Seja α um número irracional. De acordo com o teorema de Dirichlet, a desigualdade |α − \frac{p}{q}| < \frac{1}{q^{2}} tem uma infinidade de soluções racionais p/q. Markov e Hurwitz melhoraram este resultado,

provando que, para todo irracional α, a desigualdade |α − \frac{p}{q}| < \frac{1}{\sqrt{5} · q^{2}} tem uma infinidade de

soluções racionais, e que \sqrt{5} é a melhor constante com esta propriedade: para α = \frac{1 + \sqrt{5}}{2} , e para qualquer ε > 0, a desigualdade |α − \frac{p}{q}| < \frac{1}{(\sqrt{5} + ε)q^{2}} tem apenas um número finito de soluções (ver apêndice). Entretanto, fixado α irracional, pode-se esperar resultados melhores, o que nos leva a associar a cada α a sua constante de melhor aproximação k(α) = sup{k > 0 | |α − \frac{p}{q}| < \frac{1}{kq^{2}} tem uma infinidade de soluções racionais p/q\} = lim sup_{p,q∈ℤ} (|q(qα − p)|^{−1}) ∈

ℝ∪\{+∞\}. Nossa discussão inicial mostra que k(α) ≥ \sqrt{5} para todo α ∈ ℝ, e k(\frac{1 + \sqrt{5}}{2}) = \sqrt{5}. Não é difícil provar que k(α) = +∞ para quase todo α ∈ ℝ. Estaremos interessados nos α ∈ ℝ tais que k(α) < +∞, e, mais particularmente, na imagem da função k, isto é, no conjunto L = {k(α) | α ∈ ℝ\ℤ e k(α) < +∞}. Este conjunto é conhecido como o espectro de Lagrange.

Provamos no apêndice uma fórmula para k(α): escrevemos α em fração contínua, α = [a_{0}, a_{1}, a_{2}, …] e definimos, para n ∈ ℕ, α_{n} = [a_{n}, a_{n+1}, a_{n+2}, …] e β_{n} = [0, a_{n−1}, a_{n−2}, …]. Temos então k(α) = lim sup_{n→∞} (α_{n} + β_{n}). Isto segue dos resultados do Capítulo 3.

É interessante observar que se mudássemos um pouco as funções envolvidas na definição do espectro de Lagrange ele seria um conjunto bastante trivial: se para f: ℝ → ℝ_{+} considerarmos o conjunto k_{f}(α) := sup \{k > 0 | |α − \frac{p}{q}| < \frac{f(q)}{k} tem infinitas soluções racionais p/q} então, caso tenhamos lim_{q→+∞} q^{2} f(q) = 0 então a imagem de k_{f} seria (0, +∞] (ou [0, +∞], se consideramos sup(∅) = 0 neste contexto) e, caso lim_{q→+∞} q^{2} f(q) = +∞, então a imagem de k_{f} seria {+∞}.

O conjunto L encodifica uma série de propriedades diofantinas de números reais, e vem sendo estudado há bastante tempo. Talvez o primeiro resultado não-trivial sobre ele se deva a Markov, que provou em 1879 (ver [Ma]) que L ∩ (−∞, 3) = \{k_{1} = \sqrt{5} < k_{2} = 2\sqrt{2} < k_{3} = \frac{\sqrt{221}}{5} < ⋯ \}, onde (k_{n}) é uma seqüência convergente a 3 tal que k_{n}^{2} ∈ ℚ para todo n. Assim, o “começo” do espectro de Lagrange é discreto. Essa afirmação não é verdadeira para todo o conjunto L. Marshall Hall prova em 1947 ([H]) que L contém toda uma semi-reta (por exemplo [6, +∞)), e G. Freiman determinou em 1975 a maior semi-reta que está contida em L, que é [4 + \frac{253589820 + 283748\sqrt{462}}{491993569} , +∞). Estes dois últimos resulados baseam-se fortemente no estudo de somas de conjuntos de Cantor regulares, cuja relação com o espectro de Lagrange tem origem na fórmula que apresentamos para k(α), e é o tema principal deste capítulo. Por exemplo, o resultado que M. Hall enuncia em seu artigo [H] é o seguinte: se C(4) é o conjunto de Cantor regular dos reais de [0, 1] em cuja fração contínua aparecem apenas os coeficientes 1, 2, 3 e 4 então C(4) + C(4) = [\sqrt{2} − 1, 4(\sqrt{2} − 1)], do qual não é difícil deduzir que L ⊃ [6, +∞) via a fórmula para k(α).

De k(α) = lim sup_{n→∞} (α_{n} + β_{n}) podemos obter a seguinte caracterização do espectro de Lagrange: seja Σ = (ℕ^{∗})^{ℕ}, o conjunto das seqüências bi-infinitas de inteiros positivos, e σ: Σ → Σ o shift definido por σ((a_{n})_{n∈ℤ}) = (a_{n+1})_{n∈ℤ}. Se f: Σ → ℝ é definida por f((a_{n})_{n∈ℤ}) = α_{0} + β_{0} = [a_{0}, a_{1}, a_{2}, …] + [0; a_{−1}, a_{−2}, …] então L = \{lim sup_{n→+∞} f(σ^{n}\underline{θ}), \underline{θ} ∈ Σ\}. Outro conjunto de números reais que será de nosso interesse é o espectro de Markov M, que é igual a \{sup_{n→∞} f(σ^{n}\underline{θ}), \underline{θ} ∈ Σ\}. O espectro de Markov tem a seguinte interpretação aritmética: M = {(inf_{(x,y)∈ℤ^{2}\(0,0)} |f(x, y)|)^{−1}; f(x, y) = ax^{2}+bxy+cy^{2}, b^{2}−4ac = 1}. São fatos conhecidos que L e M são subconjuntos fechados da reta e que L ⊂ M. Provamos em [M2] os seguintes resultados, que pretendemos discutir neste capítulo:

Teorema 1.1: Para todo t ∈ ℝ, as dimensões de Hausdorff de L ∩ (−∞, t) e de M ∩ (−∞, t) são iguais. Se denotarmos essas dimensões por d(t), temos os seguintes fatos:

i) d: ℝ → [0, 1] é contínua e sobrejetiva. ii) d(t) = min{1, 2 · HD(k^{−1}(−∞, t))}

iii) max{t ∈ ℝ | d(t) = 0} = 3

iv) d(\sqrt{12}) = 1

(As afirmações iii) e iv) são conseqüências simples de ii)).

Teorema 1.2: O conjunto dos pontos de acumulação de L é perfeito, isto é, L′ = L′′.

Teorema 1.3: 0 < HD(M\L) < 1.

Estes teoremas são baseados na idéia de aproximar partes de M e de L por dentro e por fora por somas de conjuntos de Cantor regulares de dimensões próximas. A prova do Teorema 1.1 depende de modo essencial de um resultado sobre dimensões de Hausdorff de somas aritméticas de conjuntos de Cantor regulares, que será discutido na próxima seção, e cuja prova depende do lema de recorrência de escala de [MY].

2 Dimensões de Hausdorff e somas aritméticas de con-

juntos de Cantor de frações contínuas

Vimos no capítulo anterior que, se K_{1} e K_{2} são conjuntos de Cantor C^{2} que satisfazem as hipóteses do lema de recorrência de escalas, então vale a fórmula HD(K_{1}+K_{2}) = min{1, HD(K_{1})+ HD(K_{2})}.

Iremos aplicar este resultado a conjuntos de Cantor regulares definidos por restrições da função de Gauss g: (0, 1] → (0, 1] definida por g(x) = \frac{1}{x} − ⌊\frac{1}{x}⌋ (cuja relação com frações contínuas é evidente) a determinados domínios de Markov (que serão uniões finitas de intervalos cujos extremos serão irracionalidades quadráticas). Para isso, precisamos provar que tais conjuntos de Cantor satisfazem as hipóteses do lema de recorrência de escalas, isto é, que não são essencialmente afins.

Observemos inicialmente que qualquer conjunto de Cantor regular de Gauss (nome que atribuiremos aos conjuntos de Cantor descritos no parágrafo anterior) contém um conjunto de Cantor completo de Gauss, nome que atribuímos ao seguinte tipo de conjunto de Cantor: A cada conjunto finito de seqüências finitas de inteiros positivos B associamos o conjunto K(B) = {[0; β_{1}, β_{2}, …] | β_{i} ∈ B, ∀ i ∈ ℕ}, que, excetuando os casos triviais onde K(B) é um ponto, é um conjunto de Cantor regular completo de Gauss. Este fato pode ser provado do seguinte mod: tomamos duas palavras finitas admissíveis γ_{1} = b_{1}b_{2} … b_{n}b_{1} e γ_{2} = b_{1}b̃_{2}b̃_{3} … b̃_{m}b_{1} começando e terminado em b_{1} que não sejam ambas cópias múltiplas do mesmo bloco de símbolos (aqui os símbolos b_{i} são inteiros positivos corespondentes a ramos \frac{1}{x} − b_{i} da função de Gauss g, que aparecem na construção do Cantor regular de Gauss em questão K). Se γ̃_{1} = b_{1}b_{2} … b_{n} e γ̃_{2} = b_{1}b̃_{2} … b̃_{m} então o Cantor completo de Gauss K({γ̃_{1}, γ̃_{2}}) está contido em K.

Basta provar agora que nenhum Cantor completo de Gauss é essencialmente afim. Observemos que K(B) é definido por ψ: ⋃_{β∈B} I_{β} → I, onde I = [0, 1] e, para cada β ∈ B, I_{β} = {[0; β, α], α ≥ 1} e ψ_{β} = ψ|_{I_{β}} é o iterado de g definido por ψ_{β}([0; β, α]) = 1/α.

Seja x_{β} = [0; β, β, β, …] o ponto fixo de ψ_{β}. Se β = (b_{1}, b_{2}, …, b_{n}) e p_{k}/q_{k} = [0; b_{1}, b_{2}, …, b_{k}] são as reduzidas de [0; β], então ψ_{β}(x) = \frac{q_{n−1}x − p_{n−1}}{p_{n} − q_{n}x} , e os pontos fixos de ψ_{β} (estendido à reta pela sua fórmula) são as raízes de q_{n}x^{2} +(q_{n−1} −p_{n})x−p_{n−1} = 0 (ver Seção 3 do Apêndice).

Existe um difeomorfismo α_{β}: I → I tal que α_{β}(x_{β}) = x_{β} α′_{β}(x_{β}) = 1 e α_{β} ∘ ψ_{β} ∘ α_{β}^{−1} é afim. Além disso, podemos tomar um tal α_{β} da forma α_{β}(x) = \frac{a_{β}x + b_{β}}{c_{β}x + d_{β}} (isto é um exercício sobre triangularização de matrizes...). Não há perda de generalidade em supor que B contém dois elementos β de γ do mesmo tamanho (i.e., com o mesmo número de símbolos), pois, se não for esse o caso, podemos considerar etapas mais avançada da construção de K(B) onde hja tais elementos. É suficiente agora mostrar que se α_{β} ∘ α_{ε}^{−1} é afim e γ tem o mesmo número de elementos que β então γ = β, pois isso implicaria que α_{β} ∘ ψ_{γ} ∘ α_{β}^{−1} não é afim, donde é uma transformação da forma \frac{Ax + B}{Cx + D} , cuja derivada segunda é zero apenas num conjunto finito, ou seja, α_{β}∘ψ∘α_{β}^{−1} tem uma componente afim (a de ψ_{β}), e outra componente cuja derivada segunda é não-nula em muitos pontos de K(B) (a de ψ_{γ}), o que implica que K(B) não é essencialmente afim. Se α_{β} ∘ ψ_{γ} ∘ α_{β}^{−1} é afim então ∞ é um ponto fixo comum de α_{β} ∘ α_{β}^{−1} e α_{β} ∘ ψ_{β} ∘ α_{β}^{−1} , e

portanto α_{β}^{−1}(∞) é ponto fixo comum de ψ_{β}(x) = \frac{q_{n−1}x − p_{n−1}}{p_{n} − q_{n}x} e ψ_{γ} = \frac{q̃_{n−1}x − p̃_{n−1}}{p̃_{n} − q̃_{n}x} , donde é

raiz comum dos polinômios q_{n}x^{2} + (q_{n−1} − p_{n})x − p_{n−1} e q̃_{n}x^{2} + (q̃_{n−1} − p̃_{n})x − p̃_{n−1} , donde esses dois polinômios são iguais (pois são irredutíveis em ℤ[x]), donde suas outras raízes coincidem, ou seja, x_{β} = x_{γ} e portanto β = γ.

Provamos assim o seguinte resultado:

Proposição 2.1: Se K_{1} e K_{2} são conjuntos de Cantor regulares de Gauss então HD(K_{1}+K_{2}) = min{1, HD(K_{1}) + HD(K_{2})}. ■

Outro fato importante na prova de nossos resultados sobre dimensões de Hausdorff de partes dos espectros de Markov e Lagrange será discutido a seguir:

Definição 2.2: Se β = (b_{1}, b_{2}, …, b_{n}) então β^{t} = (b_{n}, b_{n−1}, …, b_{2}, b_{1}), e se B é um conjunto de seqüências finitas então B^{t} = {β^{t}, β ∈ B}.

Se q_{n}(β) é o denominador da fração contínua [0; β] = [0, b_{1}, …, b_{n}] então q_{n}(β) = q_{n}(β^{t}). Este é um fator já conhecido por Euler, e uma boa referência sobre sua prova (que também pode ser considerada como um exercício para o leitor) está no apêndice 2 de [CF]. Como conseqüência deste restulado e do fato de que os comprimentos dos intervalos da construção de um conjunto de Cantor completo de Gauss dependerem essencialmente dos denominadores das frações contínuas finitas envolvidas, prova-se a seguinte

Proposição 2.3: HD(K(B)) = HD(K(B^{t})) para todo conjunto finito B de seqüências finitas de inteiros positivos. ■

Corolário 2.4: HD(K(B) + K(B^{t})) = min{1, 2 · HD(K(B))}. ■

3 Idéias das demonstrações dos resultados sobre os es-

pectros

Seja Σ = ℤ_{+}^{ℤ}, ℓ: Σ → ℝ definida por ℓ(\underline{θ}) = lim sup_{n→∞} (α_{n} + β_{n}), onde, se \underline{θ} = (a_{k})_{k∈ℤ} então α_{n} = [a_{n}; a_{n+1}, a_{n+2}, …] e β_{n} = [0; a_{n−1}, a_{n−2}, …] e m: Σ → ℝ definida por m(\underline{θ}) = sup_{n∈ℤ}(α_{n} + β_{n}). Então, como observamos no início deste capítulo, o espectro de Lagrange é o conjunto L = \{ℓ(\underline{θ}), \underline{θ} ∈ Σ\} e o espectro de Markov é o conjunto M = \{m(\underline{θ}), \underline{θ} ∈ Σ\}.

A prova dos resultados sobre a função d(t) baseia-se, como mencionamos no início deste capítulo, no fato de que podemos aproximar por dentro e por fora pedaços dos espectros de Markov e Lagrange por somas de conjuntos de Cantor regulares de Gauss com dimensões de Hausdorff próximas (em geral essas somas serão do tipo K(B) + K(B^{t}), e usaremos a proposição acima). A principal ferramenta que usaremos na construção de tais aproximações será o seguinte lema técnico, cuja prova (assim como os detalhes da prova dos teoremas deste capítulo) se encontra em [M2]:

Lema 3.1: Para cada t > 0 e ε > 0, seja Σ(t) = \{\underline{θ} ∈ Σ | m(\underline{θ}) ≤ t\}, e seja N_{ε}(t) o número de seqüências finitas α tais que o intervalo I(α) = {x ∈ [0, 1] | x = [0; α, y], y ≥ 1} tem comprimento maior ou igual a ε e α aparece como subseqüência de algum elemento de Σ(t). Definimos D(t) = lim_{ε→0} −\frac{log N_{ε}(t)}{log ε} (o limite existe pois existe C > 0 tal que N_{εδ}(t) ≤ C N_{ε}(t)N_{δ}(t), ∀ ε, δ > 0). Então, dado τ > 0 existe δ > 0 e um shift completo Σ̃ ⊂ Σ(t − δ) com HD(Σ̃_{+}, d) ≥ D(t) − τ, onde Σ_{+} = ℤ_{+}^{ℤ}, Σ̃_{+} = Σ̃ ∩ Σ_{+} , e d: Σ_{+} × Σ_{+} → ℝ é a distância definida por d(\underline{θ}, \underline{θ}′) = |I(\underline{θ} ∧ \underline{θ}′)|. ■

A idéia da prova de que L′ = L′′ é criar conjuntos de Cantor regulares de Gauss usando seq”uências finits que aparecem infinitas vezes nas frações contínuas das preimagem por k de uma seqüência convergente de pontos de L. A imagem por k do Cantor de Gauss gerado por, digamos, duas seqüências dessas fornecerá um conjunto de Cantor contido em L próximo ao limiteda tal seqüência. Aumentando o comprimento das seqüências finitas consideradas obtemos o resultado.

Para estudar o complementar do espectro de Lagrange em relação ao espectro de Markov, primeiro mostramos que M\L contém conjuntos de Cantor regulares próximos a α_{∞} = [2; \overline{1, 1, 2, 2, 2, 1, 2}] + [0; 1, 2, 2, 2, 1, 1, 2, 1, \overline{2}] ≅ 3, 293044265 …, que Freiman provou ser um ponto de acumulação de M\L (ver Capítulo 3 de [CF]) (as barras superiores indicam período nas frações contínuas pré-periódicas acima), com um argumento semelhante à prova de L′ = L′′. A prova de HD(M\L) < 1 é mais técnica e delicada, e depende da análise de restrições à seqüências finitas que podem aparecer nas frações contínuas de elementos de conjuntos de Cantor cuja imagem por k esteja contida em M\L. Veja [M2] para detalhes.

4 Espectros de Markov e Lagrange dinâmicos

As caracterizações em termos de shift Σ e das funções ℓ e m dos espectros de Markov e Lagrange admitem uma generalização natural no contexto de dinâmica hiperbólica: seja φ: M^{2} → M^{2} um difeomorfismo, Λ ⊂ M^{2} um conjunto hiperbólico para φ e f: M^{2} → ℝ uma função real de classe C^{2}. Podemos definir espectros de Markov e Lagrange dinâmicos associados ao par (f, Λ) como segue: L(f, Λ) = {lim sup_{n→+∞} f(φ^{n}(x)), x ∈ Λ} e M(f, Λ) = {sup_{n∈ℤ} f(φ^{n}(x)), x ∈ Λ}. É possível provar de um modo análogo ao que descrevemos neste capítulo que para conjuntos abertos de (f, φ) (que contém abertos densos de {(f, φ) | φ preserva área } a função d(t) = d_{f,Λ}(t) = HD(L(f, Λ)∩(−∞, t)) coincide com HD(M(f, Λ)∩(−∞, t)), é contínua e sua imagem é o intervalo [0, min{1, HD(Λ)}]. Genericamente, nesses casos, o ponto t_{1} = inf{t ∈ ℝ | d(t) = 1} pertence ao fecho do interior de L(f, Λ) ⊂ M(f, Λ).

Vale notar que o resultado não é verdade em geral para φ dissipativo, pois há conjuntos abertos de contraexemplos onde d(t) tem um número finito de descontinuidades, e sua imagem é uma união finita de intervalos não-degenerados.

As demonstrações desses últimos resultados aparecerão em [M3].

84 Apêndice: Conjuntos de Cantor Regulares e Dimensões Fractais

1.0 Conjuntos de Cantor

Normalmente as pessoas ouvem falar no “Conjunto de Cantor” antes de ouvir falar em “conjuntos de Cantor” em geral. O conjunto de Cantor é um engenhoso exemplo de um subconjunto da reta que é compacto, não-enumerável e totalmente desconexo, que serve como fonte de exemplos interessantes em análise e topologia. O Conjunto de Cantor, que denotaremos por K, pode ser definido de várias maneiras. Por exemplo, K é o conjunto de todos os números do intervalo [0, 1] que podem ser escritos em base 3 utilizando apenas os algarismos 0 e 2, ou seja, K = \{ ∑_{n−1}^{∞} \frac{σ_{n}}{3^{n}} , σ_{n} ∈ \{0, 2\}, ∀ n ∈ ℕ\}. Outra maneira de descrever o conjunto K é descrevendo explicitamente seu complementar: tomamos o intervalo [0, 1], retiramos seu terço central (\frac{1}{3}, \frac{2}{3}) e obtemos dois intervalos fechados: [0, \frac{1}{3}] e [\frac{2}{3}, 1]. Retiramos os terços cen-

trais desses intervalos e obtemos quatro intervalos fechados: [0, \frac{1}{9}], [\frac{2}{9}, \frac{1}{3}], [\frac{2}{3}, \frac{7}{9}] e [\frac{8}{9}, 1]. Continuamos o processo, sempre retirando os terços centrais dos intervalos restantes. Os pontos do intervalo [0, 1] que não pertencem a nenhum dos intervalos retirados formam o conjunto de Cantor K. Notemos que, na n-ésima etapa da construção de K sobram 2^{n} intervalos de comprimento 1/3^{n} cada, cuja união contém K. Isso implica que K tem medida nula.

A terceira construção do conjunto K que mostraremos a seguir é de particular importância para nós, pois será generalizada para definir conjuntos de Cantor regulares ou dinamicamente definidos. Consideremos a função ψ: [0, \frac{1}{3}] ∪ [\frac{2}{3}, 1] → [0, 1] definida por ψ(x) =

\begin{cases}3x se [0, \frac{1}{3}] \\ 3x − 2 se x ∈ [\frac{2}{3}, 1] \end{cases} . O domínio da função ψ é a primeira etapa da construção anterior do

conjunto K. Se denotarmos \underbrace{ψ ∘ ψ ∘ ⋯ ∘ ψ}_{n vezes} por ψ^{n}, temos que ψ^{n} não está definida para todo x. Por exemplo, se n = 2

e x = 0, 2, temos que ψ(x) = 3x = 0, 6, que não pertence ao domínio de ψ, donde ψ^{2}(0, 2) não está definido. Podemos caracterizar o Conjunto de Cantor K como o conjunto dos x ∈ [0, 1] tais que ψ^{n}(x) está definido para todo natural n, ou seja, K = ⋃_{n=0}^{∞} ψ^{−n}([0, 1]). Podemos observar que ψ^{−n}([0, 1]), ou seja, o domínio de ψ^{n} coincide com o conjunto obtido na n-ésima etapa da construção anterior.

K é claramente compacto, pois pela segunda construção, por exemplo, seu complementar é aberto. Além disso, K é não-enumerável, o que segue do fato de que a primeira construção fornece uma bijeção entre K e {0, 2}^{ℕ}, que de fato é um homeomorfismo, se dotarmos {0, 2}^{ℕ} da topologia produto.

Em geral dizemos que um conjunto de Cantor é um espaço topológico homeomorfo a K. Nosso principal interesse será nos conjuntos de Cantor contidos na reta real, que podem ser caracterizados como os compactos de interior vazio sem pontos isolados.

Em geral, espaços métricos (ou metrizáveis) compactos, totalmente desconexos (i.e., cujas componentes conexas são os pontos) e sem pontos isolados são conjuntos de Cantor (i.e., são homeomorfos a K). Deixamos a prova deste fato como exercício para o leitor. (Sugestão: dado um conjunto como acima, tente decompô-lo como uma união disjunta de abertos e fechados com diâmetro menor que a metade do diâmetro original, repetir o processo e usar isso para reduzir o problema ao caso de subconjuntos da reta. no qual é possível construir homeomorfismos monótonos razoavelmente explícitos).

1.1 Conjuntos de Cantor regulares

Mencionamos que a terceira construção que exibimos para o conjunto K, que o caracteriza como o maximal invariante pela função ψ no intervalo [0, 1] é de particular interesse, pois caracteriza K como um conjunto de Cantor dinamicamente definido. Vamos discutir informalmente algumas propriedades dos conjuntos de Cantor dinamicamente definidos, ou regulares (que serão nosso assunto principal) antes de defini-los mais precisamente. Uma propriedade fundamental do conjunto de Cantor K é a sua auto-semelhança: pequenas partes de K são cópias reduzidas de todo o conjunto K. De fato, dado x ∈ K e ε > 0 existe um subconjunto aberto e fechado de K contendo x e de diâmetro menor que ε que é semelhante ao conjunto K (por exemplo uma peça de uma etapa avançada da construção de K que contenha o ponto x). Esta semelhança será dada por um certo iterado da função afim expansora ψ.

Os conjuntos de Cantor dinamicamente definidos, ou regulares, sempre apresentam um certo tipo de auto-semelhança: pequenas partes deles são difeomorfas ao conjunto todo, ou a partes grandes dele, com distorção uniformemente limitada. Assim, aspectos locais desses conjuntos não diferem muito de aspectos globais. Este tipo de propriedade é a principal característica dos conjuntos de Cantor regulares, e está ligada ao fato desses conjuntos, por definição, serem caracterizados como maximais invariantes de funções diferenciáveis expansoras (as quais suporemos de classe pelo menos C^{1+ε}).

Vamos passar a definições mais precisas:

Sejam I, I_{1}, I_{2}, …, I_{k} ⊂ ℝ intervalos fechados tais que os intervalos I_{j}, 1 ≤ j ≤ k são disjuntos e I é o fecho convexo de I_{1} ∪ I_{2} ∪ ⋯ ∪ I_{k}, e seja ψ: I_{1} ∪ I_{2} ∪ ⋯ ∪ I_{k} → I uma função expansora de classe C^{1+ε} para um certo ε > 0, isto é, ψ é de classe C^{1}, |ψ′(x)| > 1 para todo x ∈ I_{1} ∪ I_{2} ∪ ⋯ ∪ I_{k} e existe C > 0 tal que |ψ′(x) − ψ′(y)| ≤ C|x − y|^{ε} ∀ x, y ∈ I_{1} ∪ I_{2} ∪ ⋯ ∪ I_{k}. Suponhamos ainda que para todo j com 1 ≤ j ≤ k, ψ(I_{j}) é o fecho convexo de uma união de intervalos I_{i}, e que, para n ∈ ℕ suficientemente grande, ψ^{n}(I_{j}) ⊃ I_{1} ∪ I_{2} ∪ ⋯ ∪ I_{k}.

Dizemos que o conjunto de Cantor regular K = K_{ψ} associado à função ψ e à partição de Markov (I_{1}, I_{2}, …, I_{k}) é o conjunto dos x ∈ I tais que ψ^{n}(x) está definido para todo n ∈ ℕ, isto é K_{ψ} = ⋂_{n∈ℕ} ψ^{−n}(I_{1} ∪ ⋯ ∪ I_{k}). Se ψ é de classe C^{r}, com 1 < r ≤ ∞, dizemos que K é um (conjunto de) Cantor regular de classe C^{r}.

Como indicamos na definição acima, o conjunto dos intervalos I_{j} com 1 ≤ j ≤ k é denominado a partição de Markov de K. O conjuntos I_{1} ∪ I_{2} ∪ ⋯ ∪ I_{k} será chamado de domínio de Markov de K, e pode ser visto como a etapa inicial da construção de K.

Para entender melhor a estrutura do conjunto K podemos considerar a matriz de transição B = (b_{ij})_{k×k} associada a uma partição de Markov (I_{1}, …, I_{k}) e a uma função ψ como acima

definida por b_{ij} = \begin{cases}1, se ψ(I_{i}) ⊃ I_{j} \\ 0, se ψ(I_{i}) ∩ I_{j} = ∅ \end{cases} . A condição diz que ψ^{n}(I_{j}) ⊃ I_{1} ∪ ⋯ ∪ I_{k} para

todo n grande equivale a todos os termos de B^{n} serem estritamente positivos se n é grande. A uma tal matriz B podemos associar um shift de Markov mixing de tipo finito, isto é, o conjunto Σ_{B} = \{\underline{θ} = (θ_{1}, θ_{2}, …) ⊂ \{1, 2, …, k\}^{ℕ} | b_{θ_{i}θ_{i+1}} = 1, ∀ i ∈ ℕ\}, no qual está definida a função shift unilateral σ: Σ_{B} → Σ_{B}, por σ((θ_{1}, θ_{2}, θ_{3}, …)) = (θ_{2}, θ_{3}, …), isto é, σ((θ_{i})_{i∈ℕ}) = (θ_{i+1})_{i∈ℕ}.

Veremos que há uma identificação natural entre o par (K, ψ) e o par (Σ_{B}, σ) (de fato um homeomorfismo que conjuga as dinâmicas). Para cada palavra finita \underline{a} = (a_{1}, a_{2}, …, a_{n}) ∈ \{1, 2, …, k\}^{n} dizemos que \underline{a} é uma palavra de Σ_{B} se existe algum elemento de Σ_{B} que começa por \underline{a}, ou, equivalentemente, se b_{a_{i}a_{i+1}} = 1 para i = 1, 2, …, n − 1. A uma tal palavra \underline{a} associamos o intervalo I\underline{a} = I_{a_{1}} ∩ ψ^{−1}(I_{a_{2}}) ∩ ψ^{−2}(I_{a_{3}}) ∩ ⋯ ∩ ψ^{−(n−1)}(I_{a_{n}}), e a condição \underline{a} ser uma palavra de Σ_{B} equivale a I\underline{a} ser não-vazio. Por outro lado, a expansividade de ψ faz com que o comprimento |I\underline{a}| do intervalo I\underline{a} seja exponencialmente pequeno se n é grande, isto é, existe λ < 1 tal que para todo \underline{a} ∈ \{1, 2, …, k\}^{n} que é uma palavra de Σ_{B} (de tamanho n), |I\underline{a}| < λ^{n}|I|.

Dado \underline{θ} = (θ_{1}, θ_{2}, …) ∈ Σ_{B}, para cada n definimos \underline{θ}^{(n)} = (θ_{1}, θ_{2}, …, θ_{n}). Note que \underline{θ}^{(n)} é sempre uma palavra de Σ_{B}. Podemos definir uma função h: Σ_{B} → K definida por \{h(\underline{θ})\} = ⋂_{n∈ℕ} I\underline{θ}_{(n)}, isto é, h(\underline{θ}) é o único ponto que pertence a I\underline{θ}_{(n)} para todo n ∈ ℕ. Não é difícil verificar que h é um homeomorfismo, e que ψ ∘ h = h ∘ σ, isto é, h é uma conjugação entre σ e ψ. Se x = h(\underline{θ}), dizemos que \underline{θ} é o endereço do ponto x.

1.2 Distorção limitada e geometrias limite

Vamos agora provar uma proposição de grande importância, segundo a qual conjuntos de Cantor regulares têm a propriedade de distorção limitada:

Proposição A.1: Seja K ⊂ ℝ um conjunto de Cantor regular, definido por uma função expansora ψ ∈ C^{1+ε} como acima. Dado δ > 0 existe C(δ) > 0 função decrescente de δ com lim_{δ→0} C(δ) = 0 tal que para todo x, y ∈ K satisfazendo

i) |ψ^{n}(x) − ψ^{n}(y)| ≤ δ

ii) O intervalo [ψ^{j}(x), ψ^{j}(y)] está contido no domínio de Markov I_{1} ∪ ⋯ ∪ I_{k} para 0 ≤ j ≤ n temos log |(ψ^{n})′(y)| − log |(ψ^{n})′(x)| ≤ C(δ).

Dem: Se σ > 1 é tal que |ψ′(t)| > σ para todo t no domínio de Markov, teremos |ψ^{j}(y) − ψ^{j}(x)| ≤ σ^{1−n} · δ para 0 ≤ j ≤ n, donde

| log |(ψ^{n})′(y)| − log |(ψ^{n})′(x)| ≤ ∑_{j=0}^{n−1} | log |ψ′(ψ^{j}(y))| − log |ψ′(ψ^{j}(x))||,

e, como ψ′ (e também log |ψ′|) é de classe C^{ε}, existe C > 0 tal que | log |ψ′(s)| − log |ψ′(t)| ≤ C|s − t|^{ε} para s, t no domínio de Markov, donde as expressões acima são majoradas por

c ∑_{j=0}^{n−1}(σ^{j−n} · δ)^{ε} < cδ̇^{ε} · ∑_{m=1}^{∞} σ^{−mε} = cδ^{ε} · \frac{σ^{−ε}}{1 − σ^{−ε}} ·

■

Uma maneira de reformular a proposição acima com significado geométrico mais evidente é dizer que se x, y e z pertencem a um mesmo intervalo I\underline{θ}_{(n)} da n-ésima etapa da construção de K então

e^{−c} \frac{|z − x|}{|y − x|} ≤ \frac{|ψ^{n}(z) − ψ^{n}(x)|}{|ψ^{n}(y) − ψ^{n}(x)|} ≤ e^{c} \frac{|z − x|}{|y − x|}

onde c = c(|I|) é uma constante. Além disso, se ψ^{n}(x), ψ^{n}(y) e ψ^{n}(z) estão próximos, c pode ser tomada pequena. Isto significa que distâncias relativas numa escala microscópica são no máximo distorcidas por um fator constante em relação a distâncias relativas correspondentes numa escala maior, e cada vez menos distorcidas se diminuimos o tamanho da escala maior.

Vamos agora introduzir o conceito de geometrias limite de um conjunto de Cantor regular, que dão informações mais precisas sobre a estrutura local de um conjunto de Cantor regular.

Para isto, seja K um conjunto de Cantor regular e Σ_{B} seu shift de Markov associado. Vamos considerar o shift dual associado a Σ_{B}, denotado por Σ_{B}^{−}, dado por Σ_{B}^{−} −\{\underline{θ} = (θ_{n})_{n≤0}, f_{θ_{i}θ_{i+1}} = 1, ∀ i < 0} ⊂ {1, 2, …, k}^{ℤ^{−}}.

Dados \underline{θ} ≠ \underline{θ̃} em Σ_{B}^{−}, definimos \underline{θ} ∧ \underline{θ̃} como (θ_{−n}, θ_{1−n}, …, θ_{0}) ∈ \{1, 2, …, k\}^{n+1}, onde n é tal que θ̃_{−j} = θ_{−j} para 0 ≤ j ≤ n e θ̃_{−n−1} ≠ θ_{−n−1} , e equipamos Σ_{B}^{−} com a seguinte distância:

d(\underline{θ}, \underline{θ̃}) = \begin{cases}1 se θ_{0} ≠ θ̃_{0} \\ |I_{\underline{θ}∧\underline{θ̃}}|, caso contrário \end{cases}

Dado \underline{θ} ∈ Σ_{B}^{−} e n > 0, definimos \underline{θ}^{n} = (θ_{−n}, …, θ_{0}), e B(\underline{θ}^{n}) como sendo a função afim que leva I\underline{θ}^{n} em I_{θ_{0}} tal que o difeomorfismo k\underline{θ} ; n = B(\underline{θ}^{n}) ∘ f\underline{θ}^{n} preserva orientação, onde f\underline{θ}^{n} := (ψ^{n}|_{I\underline{θ}^{n}})^{−1}.

Com essas definições, k\underline{θ} ; n é um difeomorfismo de I_{θ_{0}} em I_{θ_{0}} , e a imagem de K ∩ I_{θ_{0}} por k\underline{θ} ; n é uma cópia ampliada de K ∩ I\underline{θ}^{n}.

Com essas notações, temos o seguinte resultado, que caracteriza as geometrias limite de um Cantor regular (ver [Su]):

Proposição A.2: Seja r ∈ (1, +∞), e K um conjunto de Cantor regular de classe C^{r} como acima, então:

i) Para cda \underline{θ} ∈ Σ_{B}^{−} existe um difeomorfismo de classe C^{r} que preserva orientação k\underline{θ} = I_{θ_{0}} → I_{θ_{0}} tal que k\underline{θ} ; n converge a k\underline{θ} na topologia C^{α} para todo α < r. A convergência é uniforme numa C^{r}-vizinhança de ψ.

ii) Se r ≥ 2 é um inteiro então k\underline{θ} ; n converge a k\underline{θ} em Diff_{+}^{r}(I_{θ_{0}}). Além disso, existe C > 0 tal

que ||k\underline{θ} ; n − k\underline{θ}||_{C^{r−1}} ≤ C|I\underline{θ}^{n}|.

Do item ii) segue que \underline{θ} → k\underline{θ} é Lipschitziana: ||k\underline{θ} − k\underline{θ̃}||_{C^{r−1}} ≤ C · d(\underline{θ}, \underline{θ̃}), ∀ \underline{θ}, \underline{θ̃} ∈ Σ_{B}^{−}. Além disso, se r = 1 + α, com 0 < α < 1, então, para

||k\underline{θ} − k\underline{θ̃}||_{C^{1}} ≤ C · d(\underline{θ}, \underline{θ̃})^{β}, ∀ \underline{θ}, \underline{θ̃} ∈ Σ_{B}^{−} .

Esta proposição diz que conjuntos de Cantor regulares têm a seguinte propriedade: se ampliarmos a interseção de um conjunto de Cantor regular K com intervalos pequenos de sua construção, obtemos conjuntos de Cantor difeomorfos a partes fixas de todo o conjunto K (as interseções K ∩ I_{a}, com a ∈ {1, 2, …, k}), estando esses difeomorfismos muito próximos da família compacta \{k\underline{θ}, \underline{θ} ∈ Σ_{B}^{−}\} que tem dimensão de Hausdorff finita por exemplo na métrica C^{1} (ver a próxima seção sobre dimensão de Hausdorff).

Definimos, para \underline{θ} ∈ Σ_{B}^{−}, o conjunto de Cantor K\underline{θ} := k\underline{θ}(K). Os conjuntos K\underline{θ} são conjuntos de Cantor regulares tão diferenciáveis quanto K, e são conhecidos como as geometrias limite de K.

Dem: A prova da Proposição A.2 não é muito difícil. De fato, k\underline{θ} ; n = B(\underline{θ}^{n}) ∘ f\underline{θ}^{n}, onde f\underline{θ}^{n} =

(ψ|_{I\underline{θ}^{n}})^{−1} pode ser escrito como g_{n} ∘ g_{n−1} ∘ ⋯ ∘ g_{1} , onde, para 1 ≤ k ≤ n, g_{k} = g\underline{θ} ; k: I_{θ_{0}} → I_{θ_{0}}

é dada por g_{k} = A_{k} ∘ (ψ|_{Ik ; \underline{θ}})^{−1} ∘ A_{k−1}^{−1} , e os A_{k}: I\underline{θ}_{k} → I_{θ_{0}} são difeomorfismos afins tais que A_{0} é a identidade e g_{k} preserva orientação para todo K.

O resultado segue do fato de que os difeomorfismos g_{k}, para K grande, estão exponencialmente perto da identidade (de modo uniforme em \underline{θ}), nas topologias indicadas no enunciado da proposição, e portanto a composição deles converge exponencialmente nessas topologias. Os detalhes ficam como exercício para o leitor. ■

1.3 Dimensões fractais

1.3.1 - A dimensão de Hausdorff

Quase todos os conjuntos de Cantor que consideramos neste livro têm medida de Lebesgue nula. Entretanto, há medidas mais finas do tamanho de subconjuntos da reta (e, em geral, de um espaço métrico). Começaremos pelo conceito que será mais importante para nós: a dimensão de Hausdorff:

Se X é um espaço métrico compacto e U = {U_{1}, U_{2}, …, U_{n}} é uma cobertura finita de X, definimos a medida de Hausdorff de dimensão α > 0 associada à cobertura U por m_{α}(U) = ∑_{i=1}^{n} diam(U_{i})^{α}, onde

diam(U_{i}) = sup_{x,y∈U_{i}} d(x, y) é o diâmetro de U_{i} ,

e definimos a medida de Hausdorff de dimensão α de X por m_{α}(X) = lim inf_{||U||→0} m_{α}(U), onde U denota uma cobertura finita de X e ||U|| = max_{U∈U} (diam U) é a norma da partição U. É fácil mostrar que existe um único h em [0, +∞] tal que se α < h então m_{α}(X) = +∞ e se α > h então m_{α}(X) = 0. Esse número h é, por definição, a dimensão de Hausdorff de X. A dimensão de Hausdorff tem algumas propriedades importantes. Uma delas é que, se f: X → X é Lipschitziana e K ⊂ X tem dimensão de Hausdorff d então f(K) tem dimensão de Hausdorff menor ou igual a d. Em particular, se X e Y são intervalos fechados e f é um difeomorfismo então as dimensões de Hausdorff de K e f(K) são iguais. Outra observação simples é que se K ⊂ ℝ^{n} tem dimensão de Hausdorff menor que n então tem medida de Lebesgue nula.

É possível provar que a dimensão de Hausdorff de conjuntos de Cantor regulares da reta depende continuamente da dinâmica que os define (mesmo na topologia C^{1}), e, no caso da dinâmica ser pelo menos C^{1+ε}, está sempre estritamente entre 0 e 1, e a medida de Hausdorff correspondente é finita e positiva no conjunto de Cantor (ver [PT2]).

Podemos definir outra dimensão fractal, a capacidade limite, como segue: Se K é um espa co métrico compacto, definimos N_{ε}(K) como sendo o número mínimo de conjuntos de Diâmetro menor ou igual a ε necessários para cobrir K. A capacidade limite de K é, por definição, d(K) = lim sup_{ε→0} −\frac{log N_{ε}(K)}{log ε} · É possível provar que, se K é um conjunto de Cantor regular (mesmo que apenas de classe C^{1}) então sua dimensão de Hausdorff coincide com sua capacidade limite (ver [PT2]). Também é verdade que, se f: X → Y é Lipschitziana e K ⊂ X então d(f(K)) ≤ d(K) e que d(K_{1} × K_{2}) ≤ d(K_{1}) + d(K_{2}). Além disso, em geral a dimensão de Hausdorff de K é sempre menor ou igual a d(K) (às vezes a desigualdade é estrita, como por exemplo se K = {0}∪{1/n, n inteiro positivo}, que tem dimensão de Hausdorff 0 e capacidade limite 1/2).

Deixamos a prova destas últimas afirmações como exercício para o leitor.

1.3.2 - Espessuras

Definição A.3: Um gap de um conjunto de Cantor é uma componente conexa de seu complementar.

Dado um gap U de um conjunto de Cantor K, associamos a ele os intervalos E_{U} e D_{U}, que são os intervalos à sua esquerda e à sua direita que o separam dos gaps maiores que ele mais próximos:

Definimos

τ_{D}(U) = \frac{|D_{U}|}{|U|}, τ_{E}(U) = \frac{|E_{U}|}{|U|},

τ_{D}(K) = inf{τ_{D}(U)|U gap limitado de K}, a espessura direita de K;

τ_{E}(K) = inf{τ_{E}(U)|U gap limitado de K}, a espessura esquerda de K, e

τ(K) = min{τ_{D}(K), τ_{E}(K)}, a espessura de K.

Observação: Dado um conjunto de Cantor K, uma apresentação de K é uma enumeração {U_{1}, U_{2}, … } de seus gaps limitados. Podemos definir os intervalos E_{U} e D_{U} como sendo os intervalos entre U e os gaps de índice menor que o de U mais próximos. No nosso caso estamos usando a apresentação pela ordem de tamanho dos gaps, o que maximiza a espessura τ(K). Veja [PT2].

A importância das espessuras reside no seguinte resultado, que é uma adaptação do “gap lemma”.

Afirmação: Dados K_{1} e K_{2} conjuntos de Cantor, se τ_{D}(K_{1})·τ_{E}(K_{2}) > 1 e τ_{E}(K_{1})·τ_{D}(K_{2}) > 1, então ou K_{1} está contido num gap de K_{2} ou K_{2} está contido num gap de K_{1} ou K_{1} ∩ K_{2} ≠ ∅.

Observação: Isso vale em particular se τ(K_{1}) · τ(K_{2}) > 1, que é a hipótese do “gap lemma” clássico. O gap lemma tal como enunciado aqui fornece mais informação, como veremos adiante.

Dem: Considere o caso em que nenhum dos K_{i}’s está contido num gap do outro. Então existe um par de gaps encaixados, como nas figuras abaixo (dizemos nesse caso que K_{1} e K_{2} estão intercalados) a)

Como τ_{D}(U_{1})τ_{E}(U_{2}) > 1, ou |D_{U_{1}}| > |U_{2}| ou |E_{U_{2}}| > |U_{1}| ⇒ existe novo par de gaps como em b) menor que o par (U_{1}, U_{2})

b)

Como τ_{E}(U_{1})τ_{D}(U_{2}) > 1, ou |E_{U_{1}}| > |U_{2}| ou |D_{U_{2}}| > |U_{1}| ⇒ existe novo par de gaps como em a) menor que o par (U_{1}, U_{2}).

Em qualquer caso obtemos um par de gaps menor, por exemplo no sentido de que a soma dos comprimentos dos gaps dos pares decresce, e reaplicando o argumento obtemos uma seqüência de pares de gaps convergindo a um ponto que necessariamente pertence a K_{1} ∩ K_{2}. ■

Podemos definir, para p ∈ K, τ_{loc}(K, p) = lim sup_{ε→0} τ(\overline{K ∩ (p − ε, p + ε)}), e analogamente (τ_{D})_{loc}(K, p) e (τ_{E})_{loc}(K, p). Para conjuntos de Cantor dinamicamente definidos, τ_{loc}(K, p) não depende de p (ver [PT2]), e a mesma prova mostra que (τ_{D})_{loc}(K, p) e (τ_{E})_{loc}(K, p) também não dependem de p. Vamos, portanto, denotá-los por τ_{loc}(K), (τ_{D})_{loc}(K) e (τ_{E})_{loc}(K) (as espessuras locais de K).

A afirmação acima implica que se (τ_{D})(K_{1}) · (τ_{E})(K_{2}) ≥ 1 e se (τ_{E})(K_{1}) · (τ_{D})(K_{2}) ≥ 1 então K_{1} − K_{2} contém intervalo.

Como conseqüência, se (τ_{D})_{loc}(K_{1}) · (τ_{E})_{loc}(K_{2}) > 1 e (τ_{E})_{loc}(K_{1}) · (τ_{D})_{loc}(K_{2}) > 1 então K_{1} − K_{2} contém intervalo. Para este último resultado necessitamos desigualdades estritas.

De fato, no exemplo de Sannami de um conjunto de Cantor dinamicamente definido K com λ(K − K) > 0 e int(K − K) = ∅ temos τ_{loc}(K) = 1.

Referências

[AGP] W. R. Alford, A. Granville e C. Pomerance, There are infinitely many Carmichael numbers, Ann. of Math., 140 (1994) 703-722.

[APR] L. M. Adleman, C. Pomerance e R. S. Rumely, On distinguishing prime numbers from composite numbers, Ann. Math. (2) 117 (1983) 173-206.

[B] N. Beskin, Frações contínuas - Iniciação à Matemática - Editora Mir.

[Bach] Eric Bach, Explicit bounds for primality testing and related problems, Math. of Comp. 55, (1990), pp. 355-380.

[BCR] R. P. Brent, G. L. Cohen e H. J. J. te Riele, Improved techniques for lower bounds for odd perfect numbers, Math. Comp., 57 (1991) 857-868 (MR 92c:11004).

[BLS] J. Brillhart, D. H. Lehmer e J. L. Selfridge, New primality criteria and factorizations of 2m ± 1, Math. Comp., 29 (1975) 620-647.

[BPMV] R. Bamón, S. Plaza, C.G. Moreira and J. Vera, Differentiable structures of central Cantor sets, Ergod. Th. and Dynam. Syst. 17 (1997), pp. 1027–1042.

[BPV] R. Bamón, S. Plaza and J. Vera, On Central Cantor Sets with self-arithmetic difference of positive Lebesgue measure, J. London Math. Soc. 51 (1995), pp. 137–146.

[Br] J. W. Bruce, A really trivial proof of the Lucas-Lehmer test, Amer. Math. Monthly, April (1993) 370-371.

[C] José Paulo Q. Carneiro, Um processo finito para a raiz quadrada, RPM 34, (1997), pp. 36–44.

[Ca1] J.W.S. Cassels, An introduction to diophantine approximation, Cambridge Univ. Pres, (1957).

[Ca2] J.W.S. Cassels, Some metrical theorems in Diophantine approximation I, Proc. Camb. Phil. Soc. 46 (1950), 209–218.

[CB] M. Clausen e U. Baum, Fast Fourier Transforms, BI-Wiss.-Verl., (1993).

[Cipolla] M. Cipolla, Sui numeri composti P, che verificano la congruenza di Fermat a^{P −1} ≡ 1 (mod P), Annali di Matematica, (3), 9, (1904), 139-160.

[CF] R. Crandall e B. Fagin, Discrete weighted transforms and large-integer arithmetic, Math. Comp., 62:205 (1994) 305-324.

[CF] T.W. Cusick and M.E. Flahive, The Markoff and Lagrange spectra, Math. Surveys and Monographs, no. 30, A.M.S. (1989).

[E] P. Erdös, On a new method in elementary number theory which leads to an elementary proof of the prime number theorem, Proc. Nat. Acad. Sci. (Washington) 35 (1949) 374-384.

[EP] P. Erdös e Carl Pomerance, On the number of false witnesses for a composite number, Math. Comp., 46 (1986) 259-279.

[F] G.A. Freiman, Diophantine approximation and geometry of numbers (The Markoff spectrum), Kalininskii Gosudarstvennyi Universitet, Moscow, (1975).

[GK] S. Goldwasser e J. Kilian, Almost all primes can be quickly certified, Proc. 18th STOC (Berkeley, May 28-30, 1986), ACM, New York, (1986), 316-329.

[Guy] R. K. Guy, Unsolved Problems in Number Theory, Springer-Verlag, New York, (1994) (QA241.G87, ISBN 3-540-94289-0).

[H] M. Hall, On the sum and product of continued fractions, Annals of Math., Vol. 48, (1947), pp. 966–993.

[HW] G. H. Hardy e E. M. Wright, An Introduction to the Theory of Numbers 5e, Oxford University Press, (1979).

[K] A. Khintchine: Zur metrischen Theorie der diophantischen Approximationen, Math. Z. 24 (1926), 706–714.

[KP] Su Hee Kim e Carl Pomerance, The probability that a random probable prime is composite, Math. Comp., 53:188 (1989) 721-741.

[Per] L., Per, L’ensemble difference de deux ensembles de Cantor aleatoires, C.R. Acad. Sci. Paris Sér. I Math. 310 (1990), no. 10, 735–738.

[Le] D. H. Lehmer, An extended theory of Lucas’ functions, Ann. Math. 31 (1930) 419-448. Reprinted in Selected Papers (ed. D. McCarthy), Vol 1, Ch. Babbage Res. Center, St. Pierre, Manitoba Canada, 11-48, (1981).

[Lu] E. Lucas, Théorie des fonctions numériques simplement périodiques, Amer. J. Math., 1, (1878), 184-240 e 289-321.

[M1] C.G. Moreira, Stable intersections of Cantor sets and homoclinic bifurcations, Ann. Inst. H. Poincaré Anal. Non Linéaire 13 (1996), no. 6, pp. 741–781.

[M2] C.G. Moreira, Geometric properties of the Markov and Lagrange spectra. Preprint-IMPA.

[M3] C.G. Moreira, Geometric properties of dynamical spectra. To appear

[M4] C.G. Moreira, Conjuntos de Cantor,bifurcações dinâmicas e aproximações diofantinas, 22.o Colóquio Brasileiro de Matemática.

[M5] C.G. Moreira, Propriedades estatísticas de frações contínuas e aproximações diofantinas:o teorema de Khintchine, Revista Matemática Universitária número 29, pp. 125-137

[M6] C.G. Moreira, Frações contínuas, representações de números e aproximações, Eureka 3 (1998), 44–55.

[Mai] H. Maier, Primes in short intervals, Michigan math. J., 32 (1985) 221-225.

[Mar1] A. Markoff, A new sequence of minima in the geometry of numbers, Math. Ann. 15 (1879), 381–406.

[Mar2] A. Markov, Sur les formes quadratiques binaires indéfinies, Math. Ann. 15 (1879), 381–406.

[Mi] W. H. Mills, A prime representing function, Bull. Amer. Math. Soc., 53 604.

[MN] C.G. Moreira e Nicolau Saldanha, Primos de Mersenne (e outros primos muito grandes), 22.o Colóquio Brasileiro de Matemática

[Mo] , R. A. Mollin, Prime-producing polynomials, Amer. Math. Monthly 104 (June-July 1997) 529-544.

[MO] P. Mendes and F. Oliveira, On the topological structure of the arithmetic sum of two Cantor sets, Nonlinearity, Vol. 7, (1994), pp. 329–343.

[MY] C.G. Moreira and J.-C. Yoccoz, Stable intersections of regular Cantor sets with large Hausdorff dimensions. Preprint - IMPA, (1998).

[MY2] C.G. Moreira and J.-C. Yoccoz, Tangences homoclines stables pour les ensembles hyper-

boliques de grande dimension fractale. To appear.

[N1] S. Newhouse, Non density of Axiom A(a) on S^{2}, Proc. A.M.S. Symp. Pure Math., Vol. 14, (1970), pp. 191–202.

[N2] S. Newhouse, Diffeomorphisms with infinitely many sinks, Topology, Vol. 13, (1974), pp. 9–18.

[N3] S. Newhouse, The abundance of wild hyperbolic sets and nonsmooth stable sets for diffeomorphisms, Publ. Math. IHES, Vol. 50, (1979), pp. 101–151.

[O] C.D. Olds, Continued Fractions, New Mathematical Library, Random House.

[P] J. Palis, Homoclinic orbits, hyperbolic dynamics and fractional dimension of Cantor sets, Contemporary Mathematics 58, (1987), pp. 203–216.

[P1] J. Palis, Homoclinic bifurcations, sensitive chaotic dynamics and strange attractors, Dynamical Syst. and Related Topics. World Scientific, (1991), pp. 466-473.

[Pi] J. Pintz, Very large gaps between consecutive primes, J. Number Theory 63 (1997), no. 2, 286-301.

[Po] C. Pomerance, A new lower bound for the pseudoprimes counting function, Illinois J. Math, 26, (1982), 4-9.

[PSW] C. Pomerance, J. L. Selfridge e S. S. Wagstaff Jr., The pseudoprimes to 25.109, Math. Comp., 35 (1980) 1003-1026.

[PT] J. Palis and F. Takens, Cycles and measure of bifurcation sets for two-dimensional diffeomorphisms, Invent. Math., Vol. 82, (1985), pp. 379–442.

[PT1] J. Palis and F. Takens, Hyperbolicity and the creation of homoclinic orbits, Annals of Math., Vol. 125, (1987), pp. 337–374.

[PT2] J. Palis and F. Takens, Hyperbolicity and sensitive chaotic dynamics at homoclinic bifurcations: fractal dimensions and infinitely many attractors, Cambridge Univ. Press, (1992).

[PY] J. Palis and J.C. Yoccoz, Homoclinic Tangencies for Hyperbolic sets of large Hausdorff Dimension Bifurcations, Acta Mathematica, Vol. 172, (1994), pp. 91–136.

[PY1] J. Palis and J.C. Yoccoz, On the arithmetic sum of regular Cantor sets, Ann. Inst. H. Poincaré Anal. Non Linéaire 14 (1997), pp. 439–456.

[R] A.M. Rockett, P. Szüsz, Continued Fractions, World Scientific.

[Ri1] P. Ribenboim, The New Book of Prime Number Records, 3ed., Springer-Verlag, New York, (1995) (QA246 .R47 ISBN 0-387-94457-5).

[Ri2] P. Ribenboim, Vendendo primos, Rev. Mat. Univ., 22/23, 1997, 1-13 (tradução de Selling primes, Math. Mag., 68 (1995) 175-182).

[Rie1] H. Riesel, Naagra stora primtal (Sueco: Alguns primos grandes), Elementa 39 (1956) 258-260.

[Rie2] H. Riesel, Prime Numbers and Computer Methods for Factorization, Progress in Mathematics, Birkhauser Boston, vol. 57, (1985); and vol. 126, 1994.

[S] A. Sannami, An example of a regular Cantor set whose difference set is a Cantor set with positive measure, Hokkaido Math. Journal, Vol. XXI (I), (1992), pp. 7–23.

[Sc] W.M. Schmidt: Diophantine approximations, Lecture Notes in Mathematics 785, Springer Verlag, (1980).

[Se] A. Selberg, An elementary proof of the prime number theorem, Annals of Math. 50 (1949) 305-13.

[Si] W. Sierpinski, Sur un problème concernant les nombres k ·2n+1, Elem. Math., 15 (1960) 73-74. Corrigendum: Elem. Math., 17 (1963) 85.

[Su] D. Sullivan, Differentiable structures on fractal-like sets, determined by intrinsic scaling functions on dual Cantor sets, The mathematical heritage of Hermann Weyl (Durham, NC, 1987), 15–223, Proc. Sympos. Pure Math. 48, Amer. Math. Soc., Providence, RI, (1988).

[WD] H. C. Williams e H. Dubner, The primality of R1031, Math. Comp., 47 (1986) 703-711.

[We] E. Westzynthius, Über die Verteilung der Zahlen die zu den n ersten Primzahlen teilerfremd sind, Comm. Phys. math. Helsingfors, 5:5 (1931) 1-37.

[Wi] H. Wilf, What is an answer? Am. Math. Monthly, 89 (1982), 289-292.

[YP] J. Young e A. Potler, First occurence of primes gaps, Math. Comp., 52 (1989) 221-224.