aigner_capa_grafica_205x255.

pdf 1 26/01/2017 17:02:21

MARTIN AIGNER Esta obra, tradução da quinta edição revisada e ampliada MARTIN AIGNER & GÜNTER M. ZIEGLER

AIGNER & ZIEGLER

de Proofs from THE BOOK, possui quatro novos capítulos,
que contêm demonstrações muito originais e encantadoras
de alguns clássicos, como o teorema espectral da álgebra
É PhD pela Universidade de Viena e
linear, a impossibilidade dos anéis borromeanos como um Foi um matemático húngaro, extre-
professor de matemática na Universi-
destaque da geometria, a versão finita do problema de mamente prolífico, que trabalhou em
dade Livre de Berlim desde 1974. Kakeya, uma demonstração inspirada da conjectura sobre
Publicou em vários campos das áreas problemas de análise combinatória,
a permanente de Minc e muitas outras surpresas.
de combinatória e teoria dos grafos e teoria dos grafos, teoria dos números,
é autor de obras em matemática teoria dos conjuntos, análise mate-
discreta, entre as quais os livros Com- mática e teoria das probabilidades e
“Este livro de Aigner e Ziegler, agora em sua quinta edição, procura fazer uma publicou cerca de 1.500 artigos,
binatorial theory e A course on enumer- homenagem póstuma a Paul Erdó´s, em uma tentativa de se aproximar d’O Livro.
ation. Recebeu o prêmio Lester R. Ford grande parte deles em colaboração
[...] Ao longo do texto, são utilizadas ilustrações e figuras para apoiar os
de exposição matemática da Mathe- argumentos, o que contribui imensamente à leitura das demonstrações, com outros pesquisadores.

AS MAIS BELAS
especialmente para iniciantes como eu. [...] A obra é um projeto maravilhoso e
matical Association of America (MAA) Recebeu vários prêmios, incluindo o
esta nova edição fornece uma boa quantidade de material novo.”
em 1996. prêmio Wolf, de 1983, e o prêmio
— Harry Strange, Computing Reviews
C

“Martin Aigner e Günter M. Ziegler reuniram de maneira admirável um acervo

DEMONSTRAÇÕES MATEMÁTICAS Cole da American Mathematical
Society (AMS), em 1951, pelos seus
artigos em teoria dos números e em
M

de teoremas com suas respectivas demonstrações que estariam, sem dúvida,

Y
n’O Livro de Erdó´s. Os teoremas são tão fundamentais, suas demonstrações tão particular pelo artigo “On a new
elegantes e as questões deixadas em aberto tão intrigantes que todo

AS MAIS BELAS DEMONSTRAÇÕES MATEMÁTICAS

π
CM
method in elementary number theory
MY GÜNTER M. ZIEGLER matemático, independentemente de sua especialização, poderá se beneficiar da
leitura deste livro.” which leads to an elementary proof of
ção da the prime number theorem”, publica-
du
CY

— SIGACT News

ª
5
do nos Proceedings of the National

Tra
CMY

K É PhD pelo Instituto de Tecnologia de Academy of Sciences, em 1949.

Massachusetts (MIT) e professor de
matemática desde 1995 – inicialmen- O número de Erdó´s foi criado para
e diç ã

o
te na Universidade Técnica de Berlim homenageá-lo em razão de suas
e agora na Universidade Livre de parcerias com outros matemáticos e
Berlim. Suas publicações são em descreve o grau de separação entre
matemática discreta, geometria, um pesquisador e Erdó´s.
topologia e otimização, incluindo o
livro Lectures on polytopes e Do I
count?: stories from mathematics. Em
2006, recebeu o prêmio Chauvenet
da MAA, por sua escrita expositiva e,
em 2008, o prêmio Communicator da
German Science Foundation.
 Conteúdo 3

Martin Aigner
Universidade Livre de Berlim

Günter M. Ziegler
Universidade Livre de Berlim

Paul Erdős:
as mais belas demonstrações matemáticas

Tradução da 5ª edição

Tradução
Marcos Botelho
Departamento de Matemática do
Instituto Tecnológico de Aeronáutica

Tradução e revisão
Helena Castro
Instituto de Matemática e Estatística da
Universidade de São Paulo

Paul Erdos [Link] 3 26/01/2017 18:35:33

 4 Paul Erdős: as mais belas demonstrações matemáticas

Paul Erdős: as mais belas demonstrações matemáticas, tradução da 5.ª edição

Tradução da edição em língua inglesa:
Proofs from THE BOOK
de Martin Aigner e Günter M. Ziegler
Copyright © 2014 Springer Berlin Heidelberg
Springer Berlin Heidelberg é parte da Springer Science+Business Media
Todos os direitos reservados.

© 2017 Editora Edgard Blücher Ltda.

Dados Internacionais de Catalogação

na Publicação (CIP)
Angélica Ilacqua CRB-8/7057

Rua Pedroso Alvarenga, 1245, 4º andar Aigner, Martin

04531-934 - São Paulo - SP - Brasil Paul Erdo" s: as mais belas demonstrações
Tel.: 55 11 3078-5366 matemáticas / Martin Aigner, Günter
contato@[Link] M. Ziegler; tradução de Marcos Botelho;
[Link] tradução e revisão de Helena Castro. – São
Paulo: Blucher, 2017.
368 p.; il. color.
Segundo o Novo Acordo Ortográfico,
conforme 5. ed. do Vocabulário Ortográfico ISBN 978-85-212-1005-4
da Língua Portuguesa, Academia Brasileira de
Letras, março de 2009. Título original em inglês: Proofs from the book

1. Matemática I. Título II. Ziegler, Günter

É proibida a reprodução total ou parcial por M. III. Botelho, Marcos IV. Castro, Helena
quaisquer meios sem autorização escrita da
editora. 16-0114 CDD 510

Todos os direitos reservados pela Índices para catálogo sistemático:

Editora Edgard Blücher Ltda. 1. Matemática

Paul Erdos [Link] 4 27/01/2017 14:20:50

 Conteúdo 9

Conteúdo

Teoria dos números 11

1. Seis demonstrações da infinidade dos números primos............................. 13
2. Postulado de Bertrand............................................................................... 21
3. Coeficientes binomiais (quase) nunca são potências.................................. 29
4. Representando números como somas de dois quadrados......................... 33
5. Lei da reciprocidade quadrática................................................................. 41
6. Todo anel de divisão finito é um corpo....................................................... 51
7. Teorema espectral e problema do determinante de Hadamard................. 57
8. Alguns números irracionais........................................................................ 67
9. Três vezes p2/6........................................................................................... 75

Geometria 85
10. O terceiro problema de Hilbert: decompondo poliedros............................ 87
11. Retas no plano e decomposições de grafos................................................ 97
12. O problema da inclinação......................................................................... 105
13. Três aplicações da fórmula de Euler......................................................... 111
14. Teorema da rigidez de Cauchy.................................................................. 119
15. Anéis borromeanos não existem.............................................................. 125
16. Simplexos que se tocam........................................................................... 135
17. Todo conjunto grande de pontos tem um ângulo obtuso......................... 141
18. Conjectura de Borsuk............................................................................... 149

Análise 157
19. Conjuntos, funções e a hipótese do contínuo.......................................... 159
20. Em louvor às desigualdades..................................................................... 177
21. Teorema fundamental da álgebra............................................................. 187

Paul Erdos [Link] 9 13/01/2017 09:24:09

 10 Paul Erdős: as mais belas demonstrações matemáticas

22. Um quadrado e um número ímpar de triângulos..................................... 191

23. Um teorema de Pólya sobre polinômios.................................................. 201
24. Sobre um lema de Littlewood e Offord..................................................... 209
25. Cotangente e o truque de Herglotz.......................................................... 213
26. O problema da agulha de Buffon.............................................................. 219

Combinatória 223
27. A casa de pombos e a contagem dupla.................................................... 225
28. Recobrimento por retângulos................................................................... 239
29. Três teoremas famosos sobre conjuntos finitos....................................... 245
30. Embaralhando cartas............................................................................... 251
31. Caminhos reticulados e determinantes.................................................... 263
32. Fórmula de Cayley para o número de árvores.......................................... 269
33. Identidades versus bijeções...................................................................... 277
34. O problema finito de Kakeya.................................................................... 283
35. Completando quadrados latinos.............................................................. 289

Teoria dos grafos 297

36. O problema de Dinitz............................................................................... 299
37. Permanentes e o poder da entropia......................................................... 307
38. Colorindo grafos planos com cinco cores................................................. 315
39. Como proteger um museu....................................................................... 321
40. Teorema do grafo de Turán...................................................................... 325
41. Comunicando sem erros........................................................................... 331
42. Número cromático dos grafos de Kneser.................................................. 343
43. De amigos e políticos............................................................................... 349
44. Probabilidade (às vezes) facilita o contar................................................. 353

Sobre as ilustrações .364

Índice remissivo . 365

Paul Erdos [Link] 10 26/01/2017 18:35:33

 Seis demonstrações da infinidade dos números primos 13

CAPÍTULO 1
SEIS DEMONSTRAÇÕES DA
INFINIDADE DOS NÚMEROS PRIMOS

Nada mais natural do que começarmos estas notas com provavelmente

a mais antiga demonstração d’O Livro, usualmente atribuída a Euclides (Os
Elementos, IX, 20). Ela mostra que a sequência de números primos nunca
termina.

Demonstração de Euclides. Para qualquer conjunto finito {p1,…, pr} de nú-

meros primos, considere o número n = p1p2 … pr + 1. Esse n tem um divisor
primo p. Mas p não é um dos pi: caso contrário, p seria um divisor de n e do
produto p1p2 … pr, e assim também da diferença n – p1p2 … pr =1, o que é
impossível. Portanto, um conjunto finito {p1,…, pr} não pode ser a coleção
de todos os números primos. n

Antes de continuar, vamos fixar algumas notações.  = {1, 2, 3,…} é o

conjunto dos números naturais,  = {…, –2, –1, 0, 1, 2,…}, o conjunto dos
intei­ros e  = {2, 3, 5, 7,…} o conjunto dos números primos.
No que segue, estaremos exibindo várias outras demonstrações (tiradas
de uma lista muito maior) as quais esperamos que o leitor aprecie tanto
quanto nós. Embora usem enfoques diferentes, a seguinte ideia básica é co-
mum a todas elas: os números naturais crescem além de qualquer limite, e
todo número natural n  2 tem um divisor primo. Esses dois fatos, juntos,
fazem com que  seja infinito. A próxima demonstração é devida a Christian
Glodbach (de uma carta de 1730 a Leonhard Euler), a terceira demonstração
F0 = 3
aparentemente faz parte do folclore, a quarta é do próprio Euler, a quinta F1 = 5
demonstração foi proposta por Harry Fürstenberg, enquanto a última é de- F2 = 17
vida a Paul Erdős. F3 = 257
F4 = 65537
F5 = 641 · 6700417
·
·
Segunda demonstração. Primeiramente, vamos olhar para os números de ·
n
Fermat Fn = 22 + 1, para n = 0, 1, 2,…. Mostraremos que quaisquer dois Os primeiros números de Fermat

Paul Erdos [Link] 13 13/01/2017 09:56:30

 14 Paul Erdős: as mais belas demonstrações matemáticas

números de Fermat são relativamente primos; consequentemente, deverão

Teorema de Lagrange existir infinitos números primos. Para esse fim, vamos verificar a recursão
Se G é um grupo (multiplicativo)
finito e U é um subgrupo, então |U|
divide |G|.
Demonstração. Considere a relação
binária
da qual nossa afirmação segue imediatamente. De fato, se m é um divisor
a ~ b : ⇔ ba–1  U. de, digamos, Fk e Fn (k < n), então m divide 2 e, daí, m = 1 ou 2. Mas m = 2 é
Segue, dos axiomas de grupo, que impossível, uma vez que todos os números de Fermat são ímpares.
~ é uma relação de equivalência. A
classe de equivalência contendo um Para demonstrar a recursão, usamos indução em n. Para n = 1, temos
elemento a é precisamente a classe F0 = 3 e F1 – 2 = 3. Pela indução, concluímos que
lateral
U a = {xa : x  U}.
Uma vez que claramente |Ua| = |U|,
temos que G se decompõe em clas-
ses de equivalência, todas de tama-
nho |U| e, consequentemente, |U| n
divide |G|.
No caso especial em que U é um
subgrupo cíclico {a, a2,…, am}, te-
Terceira demonstração. Suponha que  seja fi nito e p seja o maior número
mos que m (o menor inteiro po-
sitivo tal que am = 1, chamado de primo. Consideremos o número 2p – 1, conhecido como número de Mersenne, e
ordem de a) divide a ordem |G| do mostremos que qualquer fator primo q de 2p – 1 é maior do que p, o que resulta-
grupo. rá na conclusão desejada. Seja q um primo que divide 2p – 1, de forma que temos
Em particular, temos que a|G| = 1. 2p  1 (mod q).
Já que p é primo, isso significa que o elemento 2 tem ordem p no grupo
multiplicativo q\{0} do corpo q. Esse grupo tem q – 1 elementos. Pelo
teorema de Lagrange (ver quadro), sabemos que a ordem de cada elemento
divide a ordem do grupo, ou seja, temos que p|q – 1, e daí p < q. n

Agora vamos ver uma demonstração que usa cálculo elementar.

Quarta demonstração. Seja p(x) := #{p  x : p  } o número de primos
que são menores que ou iguais ao número real x. Enumeremos os primos
 = {p1, p2, p3,…} em ordem crescente. Considere o logaritmo natural log x,
definido como

Agora, vamos comparar a área sob o gráfico de com uma função

degrau superior. (Para esse método, ver também o apêndice na página 15.)
1
Assim, para n  x  n + 1, temos

1 2 n n + 1 onde a soma se estende sobre todos os m   que têm somente divisores

Degraus acima da função f(t) = 1
t
p  x.

Paul Erdos [Link] 14 13/01/2017 09:56:31

 Seis demonstrações da infinidade dos números primos 15

Uma vez que cada um desses m pode ser escrito de um modo único como
um produto da forma  pkp, vemos que a última soma é igual a
px

A soma interior é uma série geométrica com razão de onde

Agora, claramente, pk  k + 1 e, assim,

Consequentemente,

É de conhecimento comum que log x não é limitado, donde concluímos

que p(x) também não é limitado e, portanto, existe um número infinito de
primos. n

Quinta demonstração. Depois de análise, agora é topologia! Considere a

curiosa topologia no conjunto  dos números inteiros a seguir. Para a, b 
, b > 0, façamos

Na,b = {a + nb : n  }.
Cada conjunto Na,b é uma progressão aritmética infinita nos dois sentidos.
Agora, dizemos que um conjunto O   é aberto se O é vazio ou se, para cada
a  O, existe algum b > 0 com Na,b  O. É claro que a união de conjuntos
abertos é também um conjunto aberto. Se O1, O2 são abertos, e a  O1  O2,
com Na,b1  O1 e Na,b2  O2, então a  Na,b1b2  O1  O2. Então, concluímos
que qualquer interseção finita de conjuntos abertos também é um conjun-
to aberto. Assim, essa família de conjuntos abertos induz uma topologia
em .

Convém observar dois fatos:

(A) Qualquer conjunto aberto não vazio é infinito.
“Jogando pedras chatas, infini-
(B) Qualquer conjunto Na,b também é fechado. tamente”

Paul Erdos [Link] 15 13/01/2017 09:56:31

 16 Paul Erdős: as mais belas demonstrações matemáticas

O primeiro fato decorre da definição. Quanto ao segundo, observamos

que

o que demonstra que Na,b é o complementar de um conjunto aberto e, por-

tanto, fechado.
Até agora, os números primos ainda não entraram em cena – mas ei-los
aqui. Uma vez que qualquer número n  1, –1 tem um divisor primo p e,
consequentemente, está contido em N0,p, concluímos que

Agora, se  fosse finito, então p N0,p seria uma união finita de con-
juntos fechados devido a (B), e portanto fechado. Consequentemente, {1, –1}
seria um conjunto aberto, o que contradiz (A). n

Sexta demonstração. Nossa demonstração final dá um considerável passo

adiante e mostra não somente que há infinitos números primos, mas tam-
bém que a série diverge. A primeira demonstração desse resultado
importante foi dada por Euler (e é interessante em si mesma), mas nossa
demonstração, concebida por Erdős, é de uma beleza irresistível.
Seja p1, p2, p3, … a sequência dos números primos em ordem crescente,
e suponha que converge. Então deve existir um número natural k tal
que Vamos chamar p1, …, pk de primos pequenos, e pk+1, pk+2, …
de primos grandes. Para um número natural arbitrário N, por conseguinte,
temos

(1)

Seja Nb o número de inteiros positivos n  N que são divisíveis por pelo

menos um número primo grande, e Ns o número de inteiros positivos n  N
que têm somente divisores primos pequenos. Vamos mostrar que, para um
N conveniente,

Nb + Ns < N,
o que será nossa contradição desejada, uma vez que, por definição, Nb + Ns
teria que ser igual a N.

Para estimar Nb observe que [ ] é o número de inteiros positivos n  N

que são múltiplos de pi.

Paul Erdos [Link] 16 13/01/2017 09:56:31

 Seis demonstrações da infinidade dos números primos 17

Portanto, de (1), obtemos

(2)

Vamos agora olhar para Ns. Escrevemos todo n  N que tem apenas di-
visores primos pequenos na forma n = anbn2, onde an é a parte sem nenhum
quadrado. Todo an é, portanto, um produto de primos pequenos diferentes, e
concluímos que existem precisamente 2k partes sem nenhum quadrado dife-
rentes. Além disso, como bn   n   N, vemos que existem no máximo
 N partes quadradas diferentes e, daí,
Ns  2k 
N.
Uma vez que (2) vale para qualquer N, resta achar um número N com
ou 2k+1   N e, para isso, N = 22k+2 serve. n

Apêndice: outras infinitas demonstrações

Nossa coleção de demonstrações para a infinidade dos primos contém di-

versos outros tesouros, antigos e novos, mas existe um especial, muito recen-
te, que é bem diferente e merece uma menção especial. Vamos tentar identi-
ficar sequências de inteiros S tais que o conjunto S dos primos que dividem
algum membro de S seja infinito. Toda sequência dessa forneceria então sua
própria demonstração para a infinidade dos primos. Os números de Fermat
Fn estudados na segunda demonstração formam uma destas sequências, en-
quanto que as potências de dois não formam. Muitos outros exemplos são
fornecidos por um teorema de Issai Schur, que mostrou em 1912 que, para
todo polinômio não constante p(x) com coeficientes inteiros, o conjunto de
todos os valores não nulos {p(n)  0 : n  } é uma dessas sequências. Para
o polinômio p(x) = x, o resultado de Schur nos dá o teorema de Euclides.
Como outro exemplo, para p(x) = x2 + 1 obtemos que o “quadrado mais um”
contém um número infinito de fatores primos.
Issai Schur
O resultado a seguir, devido a Christian Elsholtz, é realmente notável: ele
generaliza o teorema de Schur, a demonstração é simplesmente uma conta-
gem inteligente e é, em certo sentido, a melhor possível.
Seja S = (s1, s2, s3, …) uma sequência de inteiros. Dizemos que:
• S é quase injetiva se todo valor ocorre no máximo c vezes, para algu-
ma constante c.
f(n)
No lugar de 2, poderíamos usar
• S é de crescimento subexponencial se |sn|  22 para todo n, em que qualquer outra base maior que
f(n)
1; por exemplo, |sn|  ee leva
f :  → + é uma função com à mesma classe de sequências.

Paul Erdos [Link] 17 13/01/2017 09:56:32

 18 Paul Erdős: as mais belas demonstrações matemáticas

Teorema. Se a sequência S = (s1, s2, s3, …) for quase injetiva e de crescimento

subexponencial, então o conjunto S dos primos que dividem algum membro
de S é infinito.

Demonstração. Podemos supor que f (n) é monotonamente crescente. Caso

contrário, substitua f (n) por maxin f (i); você pode verificar facilmente que
com esta F(n) a sequência S também satisfaz a condição de crescimento sub-
exponencial.
Vamos supor, por absurdo, que S = {p1, …, pk} seja finito. Para n  ,
faça
sn = np1 1 … pk k, com n  {1, 0, –1}, a  0,
em que i = i(n) depende de n. (Para sn = 0 podemos tomar i = 0 para todo i.)
Então,
f(n)
2 1+ … + k  | s n |  2 2 para sn  0,
e, portanto, tomando o logaritmo binário,
0  i  1 + … + k  2f (n) para 1  i  k.
Logo, não existem mais do que 2f (n) + 1 valores diferentes possíveis para
cada i = i(n). Já que f é monótona, isto nos dá uma primeira estimativa.
#{distintos |sn|  0 para n  N}  (2 f(N) + 1)k  2 (f(N)+1)k.
Por outro lado, uma vez que S é quase injetiva, somente c termos na se-
quência podem ser iguais a 0, e cada valor absoluto não nulo pode ocorrer
no máximo 2c vezes. Assim, obtemos a estimativa inferior

Juntando tudo, obtemos

Tomando novamente o logaritmo na base 2 em ambos os lados, obtemos

log2(N – c) – log2(2c)  k(f (N) + 1) para todo N.
Isso, entretanto, é claramente falso para valores grandes de N, já que k e c
são constantes, e tende a 1 para N → ∞, enquanto que tende a
0. n

Seria possível relaxar as condições? Pelo menos, nenhuma das duas é su-
pérflua.

Paul Erdos [Link] 18 13/01/2017 09:56:32

 Seis demonstrações da infinidade dos números primos 19

Que precisamos da condição “quase injetiva” pode ser visto a partir de

sequências como (2, 2, 2, …) ou (1, 2, 2, 4, 4, 4, 4, 8, …), que satisfazem a
condição de crescimento, enquanto que S = {2} é finito.
Quanto à condição de crescimento subexponencial, salientamos que ela não
pode ser enfraquecida a uma exigência da forma para um  > 0 fixo.
Para ver isso, basta analisar a sequência de todos os números da forma p1 1 … pk k,
arrumados na ordem crescente, em que p1, …, pk são primos fixos e k é gran-
f(n)
de. Esta sequência S cresce aproximadamente como 22 , com , en-
quanto S é finito por construção.

Referências

[1] B. ARTMANN: Euclid – The Creation of Mathematics, Springer-Verlag,

New York, 1999.
[2] C. ELSHOLTZ: Prime divisors of thin sequences, Amer. Math. Monthly
119 (2012), 331-333.

[3] P. ERDŐS : Über die Reihe Mathematica, Zutphen B 7 (1938), 1-2.

[4] L. EULER: Introductio in Analysin Infinitorum,Tomus Primus, Lausan-
ne 1748; Opera Omnia, Ser. 1, Vol. 8.
[5] H. FÜRSTENBERG: On the infinitude of primes, Amer. Math. Monthly 62
(1955), 353.
[6] I. SCHUR: Über die Existenz unendlich vieler Primzahlen in einigen spe-
ziellen arithmeetischen Progressionen, Sitzungsberichte der Berliner
Math. Gesellschaft 11 (1912), 40-50.

Paul Erdos [Link] 19 13/01/2017 09:56:32

 Clique aqui e:
Veja na loja

Paul Erdős
As mais belas demonstrações matemáticas

Martin Aigner e Gunter M. Ziegler

ISBN: 9788521210054
Páginas: 368
Formato: 20,5x25,5 cm
Ano de Publicação: 2017
Peso: 0.779 kg