O amigo dos números.

Feliz Natal!

Pensei em publicar um post sobre o tão celebrado teorema de Natal de Fermat (Fermat's Christmas Theorem, aquele sobre primos que se escrevem como somas de quadrados). Mas esse é um teorema muito bonito e merece uma preparação de minha parte. Em troca, irei postar aqui uma entrevista da revista Ciência Hoje com o especialista em teoria dos números, Paulo Ribenboim (foto abaixo), matemático brasileiro de maior renome internacional.

Teorema de Toeplitz e aplicações.

Considere o seguinte clássico problema sobre sequências:

Problema 1. Seja $\{z_n\}$ uma sequência convergente de números reais com $\lim_{n\to\infty} z_n = z$. Mostre que $$\lim_{n\to\infty} \frac{z_1 + z_2 + \ldots + z_n}{n} = z.$$

Neste post, mostraremos um resultado mais geral do que o do Problema 1 devido a Otto Toeplitz (figura abaixo), um matemático alemão que viveu entre as décadas de 1880 e 1940.

Teorema 1. (Toeplitz) Sejam $\{\alpha_{mn}\}$ uma sequência dupla de números complexos e $A>0$ um número real positivo tais que

1. $\displaystyle{\sum_{n=1}^{\infty} |\alpha_{mn}| \leq A}$, para todo $m\geq1$.
2. $\displaystyle{\lim_{m\to\infty} \sum_{n=1}^{\infty} \alpha_{mn} = 1}$.
3. $\displaystyle{\lim_{m\to\infty} \alpha_{mn} = 0}$, para todo $n\geq1$.

Se a sequência de números complexos $\{z_n\}$ converge para $z$, então a série $$\sum_{n=1}^{\infty} \alpha_{mn} z_n$$ converge para todo $m\geq1$ e temos que
$$\lim_{m\to\infty} \sum_{n=1}^{\infty} \alpha_{mn} z_n = z.$$

Teorema da Aproximação de Weierstrass.

Neste post, apresentarei uma prova do Teorema da Aproximação de Weierstrass usando um argumento probabilístico. Mais precisamente, tal argumento será embasado no seguinte

Lema. (Desigualdade de Chebyshev) Sejam $X$ uma variável aleatória, $\mu = \mathbf{E}[X]$ o valor esperado de $X$ e $\sigma^2 = \mathbf{Var}[X]$ a variância de $X$. Então, para $\lambda > 0$,

$$ \mathbf{Pr}[| X - \mu | \geq \lambda] \leq \frac{\sigma^2}{\lambda^2}.$$

Observe que se  $X$ possui distribuição binomial $\mathbf{Bin}(n,p)$, então $\mu = np$ e $\sigma = np(1-p)$. Se tomarmos $\lambda = n^{2/3}$ na desigualdade de Chebyshev, obtemos 

$$ \mathbf{Pr}[| X - np | \geq n^{2/3}] \leq \frac{np(1-p)}{n^{4/3}} \leq n^{-1/3},$$

que tende para zero, quando $n \to \infty$. Esta observação será crucial para a prova do

Teorema da aproximação de Weierstrass. Seja $f:[a,b] \rightarrow \mathbb{R}$ uma função contínua. Para todo $\epsilon >0$, existe um polinômio $p(x)$ tal que $$|f(x) - p(x)|<\epsilon, \quad \forall x \in [a,b].$$ 

Outra maneira de enunciar o teorema acima é a seguinte: para qualquer função contínua  $f:[a,b] \rightarrow \mathbb{R}$, existe uma sequência de polinômios $(p_n)$ que convergem uniformemente para $f$.

O teorema é originalmente atribuído a Karl Weierstrass (imagem abaixo), quem deu uma primeira demonstração em 1885 usando o que hoje chamamos de transformações de Weierstrass. Mais tarde, Marshall Stone generalizou o teorema e apresentou uma versão simplificada da prova de Weierstrass. Assim, o teorema é também conhecido como Teorema de Stone-Weierstrass. Hoje, podemos encontrar diversas provas deste resultado. Eu, pelo menos, conheço cinco versões essencialmente distintas: uma versão utilizando as transformações de Weierstras [2]; outra usando o teorema de Fejér [3]; outra usando os núcleos de Landau [4]; uma totalmente elementar [5]; e uma usando argumentos probabilísticos (que pode ser encontrada em [1]) , que é a que será dada aqui (e a que dentre as cinco citadas, é a minha preferida).

Três massas e três molas sobre um aro.

Neste post, veremos um problema que pode ser encontrado na referência [1]. Trata-se de uma aplicação da equação de Euler-Lagrange.

Problema. (Columbia, Stony Brook, MIT) Três esferas, cada uma de massa $m$, estão conectadas por molas idênticas de massas desprezíveis e de constante de elasticidade $k$ e postas sobre um aro circular como na figura abaixo. O aro está fixado no espaço. Despreze a gravidade e a fricção. Este sistema deve sofrer uma pertubação. Determine a frequência de oscilação do sistema.

Aplicações da Equação de Euler-Lagrange: pêndulo com suporte livre.

O formalismo Lagrangiano tem permitido a determinação da equação do movimento de muitos sistemas físicos de maneira menos trabalhosa do que o formalismo Newtoniano. Neste post veremos mais uma aplicação da equação de Euler-Lagrange.

Considere o sistema constituído de um pêndulo simples de massa $m$ e corda de comprimento $l$ pendurada em um suporte com massa $M$ e que é livre de se mover ao longo do eixo horizontal (veja figura abaixo). O ângulo $\theta$ entre a corda e o eixo vertical junto da posição $x$ do suporte ao longo do eixo horizontal determinam completamente a posição do sistema, de modo que o par $(\theta,x)$ é uma coordenada generalizada adequada para o sistema.

Aplicações da Equação de Euler-Lagrange: sistema barra-mola.

No último post falei sobre a Equação de Euler-Lagrange. Neste post darei um exemplo onde aplicamos a equação de Euler-Lagrange para determinar a equação do movimento de um sistema físico.

No esquema da figura abaixo, vemos uma barra homogênea de massa $m$ e comprimento $l$ pendurada numa mola suspensa de constante de elasticidade $k$. A mola está no interior de uma calha de altura $l_0$ de modo a evitar qualquer movimento que não seja vertical. A barra pode oscilar em torno do ponto $A$.

Sobre Mecânica Lagrangiana e a Equação de Euler-Lagrange.

Mecânica Lagrangiana é uma reformulação da mecânica clássica baseado no princípio da ação estacionária de Hamilton. Tal formalismo tem se mostrado mais adequado do que o formalismo Newtoniano quando aplicado em problemas mais complexos, uma vez que ele não exige a identificação das forças envolvidas no sistema.

Neste post veremos como o método Lagrangiano pode se aplicado de modo a determinar a equação do movimento de sistemas físicos. 

Um sistema de coordenadas generalizadas é um conjunto de parâmetros $q_1,q_2,\ldots,q_s$ pelos os quais é possível determinar completamente a posição de um sistema. Dizemos que $s$ é o grau de liberdade do sistema. Por exemplo, uma partícula se movendo ao longo de um toro pode ter sua posição determinada por dois parâmetros (como?). Um pêndulo pode ser determinado por um único parâmetro, o ângulo com o qual ele faz com um eixo fixo.

Compartilhando segredos com Alice e Bob.

Alice e Bob querem compartilhar segredos entre eles. Como poderão fazer isto de maneira segura? Neste post veremos um pouco sobre criptografia e mostraremos como Teoria dos Números pode nos ajudar nessa história.

Criptografia é o campo de estudo dos métodos de transmissão de informações com segurança. Ou seja, estamos interessados em enviar mensagens de maneira segura. Dizemos que uma informação é transmitida com segurança se toda fonte não autorizada é incapazes de obter acesso à informação transmitida.

Para fins técnicos, assumiremos que uma mensagem é uma sequência numérica. Emissor é aquele que está interessado em compartilhar uma mensagem e receptor é aquele que está autorizado a ter acesso ao conteúdo da mensagem. Um interlocutor é um emissor ou um receptor. No nosso caso, Alice quer enviar uma mensagem para Bob. Portanto, iremos nos referir ao emissor como Alice e ao receptor como Bob.

Um método de encriptação é uma maneira de codificar (ou criptografar) a mensagem de tal modo que seja possível reobter a mensagem original por um processo de decodificação. Num método de encriptação, o responsável pela codificação é o emissor, o qual se usa de uma chave de codificação para codificar a mensagem; enquanto o responsável pela decodificação é o receptor, o qual usa uma chave de decodificação para decodificar a mensagem. De modo geral, tal processo se dá por meio de um algoritmo, o qual chamamos de algoritmo de encriptação ou cifra. Classicamente, existem dois tipos de cifra: o de chave simétrica (ou chave privada) e o de chave assimétrica (ou chave pública).

Sobre primos em progressões aritméticas.

É um fato bem conhecido que existem infinitos números primos. Contudo, os primos parecem possuir uma distribuição bastante aleatória. Talvez por isso é que este conjunto de números tenha se tornado tão interessante, sendo fonte de diversos problemas em teoria dos números.

Um dos problemas mais celebrados sobre os números primos é o de determinar progressões aritméticas (P.A.) contendo uma infinidade de números primos. Por exemplo, a progressão aritmética dos números ímpares, i.e., o conjunto $\{2n+1;n\in\mathbb{N}\}$, contém uma infinidade de números primos. Na verdade, apenas um único número primo não pertence a esta P.A., o número 2. Uma P.A. talvez mais interessante é aquela formada por números do tipo $4n+3$, i.e., o conjunto dos números

$$\textbf{3},\textbf{7},\textbf{11},15,\textbf{19},\textbf{23},27,\textbf{31},35,39,\textbf{43}\ldots.$$

De fato, podemos provar que este conjunto possui uma infinidade de números primos:

Proposição 1. Existem infinitos primos da forma $4n+3$, onde $n$ é um número natural.

Sobre o número cromático do plano.

Com quantas cores podemos pintar o plano de maneira tal que pontos com a mesma cor não estejam a distância unitária?

Dado um conjunto $X$ e um número natural $r$, uma $r$-coloração é uma função $c: X \rightarrow \{1,\ldots ,r \} $. Dado $x \in X$, dizemos que $c(x)$ é a cor de $x$. Coloração é um dos conceitos mais importantes em combinatória, uma vez que diversos problemas podem ser expressados como um problema de colorações. Coloração em grafos, por exemplo, tem se destacado em aplicações práticas como escalonamento de tarefas e alocação de frequências. Neste post, estaremos interessados em colorir o plano (ou $\mathbb{R}^2$, se preferir).

Este é considerado por muitos matemáticos como um dos problemas mais difíceis em geometria plana (para um ensaio histórico sobre este problema e seus correlatos, indico o livro [1]). Quanto a sua origem, Erdös, por exemplo, disse uma vez "I cannot trace the origin of this problem", num artigo de 1961.

Bem, o problema já foi enunciado no início deste post, mas por educação, irei citá-lo mais uma vez:

Qual é o menor número de cores necessárias para colorir o plano de tal maneira que nenhum par de pontos de mesma cor estejam a distância unitária?

Este menor número de cores é o que chamamos de número cromático do plano, e denotamos por  $\chi(\mathbb{R}^2)$, ou somente por $\chi$.

Teorema de Turán.

Paul Turán (foto abaixo) foi um matemático húngaro especialista em teoria dos números e combinatória. Neste post, veremos um dos resultados que iniciou a teoria extremal dos grafos: o Teorema de Turán.

Seja $G$ um grafo simples com $n$ vértices. Qual é o maior números de aresta que $G$ pode ter de modo que não tenhamos em $G$ uma $p$-clique?

The Princeton Companion to Mathematics.

Este é o segundo post da série "livros que não só enfeitam a estante, mas que são matematicamente úteis (seja lá o que isso significa)".

Como dito num post anterior, a cada semana, irei indicar e comentar um livro que seja interessante para qualquer pessoa que usa matemática no seu dia-a-dia. Vamos ao segundo:

The Princeton Companion to Mathematics. Timothy Gowers, June Barrow-Green, Imre Leader.

Este livro de mais de 1000 páginas fala sobre quase tudo em matemática. Os problemas mais famosos e a áreas mais badaladas da matemática são descritas neste livro como uma daquelas enciclopédias que descrevem inúmeras coisas que você provavelmente não conhecerá por si só. 

Apesar de parecer uma enciclopédia matemática, este livro procura apresentar os tópicos numa sequência lógica. É claro que ele não é um livro para ser lido de pé-à-cabeça sequencialmente. É mais interessante você tê-lo como uma espécie de consultor. Qualquer assunto, atual ou não atual, tem um espaço reservado neste livro, desde que este assunto, em algum momento da história, tenha sido interessante.

Teorema da Recorrência de Poincaré.

Jules Henri Poincaré foi um dos mais brilhantes matemático do século XIX (e início do século XX). Considerado por muitos como o último universalista da matemática, devido a sua proeza de conseguir estudar "quase toda" área da matemática. Deixou inúmeros legados em diversas áreas tanto da matemática pura quanto da matemática aplicada.

O teorema que veremos neste post é um dos resultados clássicos em Teoria Ergódica conhecido como Teorema da Recorrência de Poincaré. Minha principal referência é o livro [1], mas indico o livro [2] para um aprofundamento na teoria. Indico também o texto [3] de Ricardo Mañé para algumas aplicações interessantes do teorema.

Considere um espaço de medida finita $(M,\Sigma, \mu)$. Dada uma aplicação mensurável $f:M\rightarrow M$, dizemos que $\mu$ é invariante pela aplicação $f$ se para todo $E\in \Sigma$ mensurável vale que

$$\mu(E) = \mu(f^{-1}(E)). $$

Dada uma propriedade sobre os elementos de $M$, por exemplo "beleza", dizemos que " $\mu$-quase todo" elementos de $M$ possuem esta propriedade quando o conjunto dos elementos que não possuem esta propriedade possuem medida nula, i.e., quando $\mu(\{x \in M: \text{ $x$ não é belo}\}) = 0$.

Vale ressaltar que dado $\{ E_k \}_{k\in \mathbb{N}}$ uma família enumerável de conjuntos mensuráveis disjuntos dois-a-dois, sendo $(M,\Sigma, \mu)$ um espaço de medida, temos que
$$ \mu \left( \bigcup_{k=1}^{\infty} E_k \right) = \sum_{k=1}^{\infty} \mu(E_k).$$


Com isso, já podemos enunciar e provar o 

Teorema (da Recorrência de Poincaré). Seja $f: M \rightarrow M$ uma transformação mensurável e $\mu$ uma medida invariante e finita. Seja $E\subseteq M$ qualquer conjunto mensurável com $\mu(E)>0$. Então, $\mu$-quase todo ponto $x\in E$ tem algum iterado $f^n (x)$, com $n\geq 1$, que também está em $E$.

Em outras palavras, o teorema afirma que quase todo ponto de $E$ regressa a $E$ no futuro. A prova deste teorema até que é simples.

Média aritmética-geométrica e a curva lemniscata.

Considere o seguinte problema que pode ser encontrado na maioria dos livros introdutórios de Análise Real: 

Seja $0 < a < b$ dois números reais. Defina as sequências $(a_n)_{n\in\mathbb{N}}$ e $(b_n)_{n\in\mathbb{N}}$ por $a_1 = a$, $b_1 = b$ e 

$$ a_{n+1} = \sqrt{a_n b_n} \quad \text{ e }\quad b_{n+1} = \frac{a_n + b_n}{2}, \quad (n = 1,2,3, \ldots).$$

Prove que estas duas sequências são convergentes e que elas convergem para o mesmo valor.

Este limite comum é o que chamamos de média aritmética-geométrica de $a$ e $b$ e é denotado por $M(a,b)$. Dados $a$ e $b$ quaisquer, em geral, não é fácil calcular $M(a,b)$. Em 30 de Maio de 1799, na idade de vinte e dois anos, Gauss (foto abaixo) escreveu em seu diário, que tinha verificado que a aproximação

$$\frac{1}{M(1,\sqrt{2})} \approx \frac{2}{\pi} \int_0^1 \frac{1}{\sqrt{1-t^4}} \;dt $$

é precisa, pelo menos até a décima primeira casa decimal.

Considere $\omega$ como o valor da integral na equação acima, i.e.,

$$\omega =  \int_0^1 \frac{1}{\sqrt{1-t^4}} \;dt.$$

Então, o que o Gauss conjecturou foi que 

$$ M(1,\sqrt{2}) = \frac{\pi}{2\omega}.$$

Aparentemente, fora o fato de envolver o $\pi$ e a $\sqrt{2}$, esta última equação não tem nada de mais. Mas ela esconde uma relação geométrica intrigante relacionada com duas curvas famosas.

Sobre uma identidade de Ramanujan.

O matemático indiano, Srinivasa Ramanujan (foto abaixo), propôs uma vez, no Journal of Indian Mathematical Society, o seguinte problema:

Determinar o valor de $$\sqrt{ 1 + 2\sqrt{ 1 + 3\sqrt{1 + 4\sqrt{ 1 + 5\sqrt{1 + \cdots}}}}}.$$

Ele esperou por seis meses que alguém lhe enviasse uma solução. Como ninguém enviou, ele publicou a sua própria solução [1].

Neste post, daremos uma prova analítica de que  $$\sqrt{ 1 + 2\sqrt{ 1 + 3\sqrt{1 + 4\sqrt{ 1 + 5\sqrt{1 + \cdots}}}}} = 3.$$

Um Guia de Estudante para o Estudo, Prática e Ferramentas de Matemática Moderna.

Este é um post da série "livros que não só enfeitam a estante, mas que são matematicamente úteis (seja lá o que isso significa)".

A cada semana, irei indicar e comentar um livro que seja interessante para qualquer pessoa que usa matemática no seu dia-a-dia. Vamos ao primeiro:

A Student's Guide to the Study, Practice and Tools of Modern Mathematics. Donald Bindner & Martin Erickson.

( Um Guia de Estudante para o Estudo, Prática e Ferramentas de Matemática Moderna.)

Este é um ótimo livro para quem está se engajando na matemática. Vale para alunos de matemática, de física, de engenharia e de qualquer outra área das Ciências Exatas.

Sobre o teorema de Ceva e o de Menelau.

Neste post, provarei dois teoremas importantes em geometria: o de Ceva e o de Menelau. Os dois teoremas  possuem similaridades, mas um fala de concorrência, enquanto o outro fala de colinearidade. 

Teorema de Ceva. Seja ABC um triângulo qualquer e D, E e F pontos sobre os lados BC, CA e BC, respectivamente. Os seguimentos AD, BE e CF são concorrentes se, e somente se, $$\frac{AF}{FB}\frac{BD}{DC}\frac{CE}{EA} = 1.$$

Pode GLOBALHELLFRY ser um número primo?

No livro Magic for Dummies contém a seguinte passagem:

Se você trocar cada uma das letras distintas de GLOBALHELLFRY por dígitos distintos e você obtiver um número primo, então o mundo irá sofrer uma terrível onda de calor. 

 É possível usar isto para criar uma onda de calor?

Nota: "Global hell fry" significa algo como "inferno global fritante", ou pelo menos assim tento traduzir.

Relação de Euler (prova combinatória)

Nos dois últimos posts, provamos a relação de Euler usando grafos e geometria elementar. Neste post, provaremos usando contagem dupla.

Teorema (da relação de Euler). Se $P$ é um poliedro convexo com $V$ vértices, $E$ arestas e $F$ faces, então vale que $$V-E+F = 2.$$

Demonstração. Primeiro "abra" o poliedro de modo que todas as faces esteja sobre um plano. Fazemos uma contagem dupla da soma S de todo os ângulos internos do poliedro resultante. Sejam $N_1,N_2,\ldots,N_F$ a quantidade de arestas (e de vértices) de cada uma das faces, sendo $N_1$ a da face que delimita todas as outras. Uma vez que a soma dos ângulos interno de um polígono de $n$ lado é $(n-2)\cdot 180º$, temos que

$$ S = (N_2-2) 180º + (N_3-2)180º + \cdots + (N_F-2)180º\\=(N_2 + N_3 + \cdots + N_F)180º - 2(F-1)180º. $$

Fazendo, agora, a contagem através dos vértices, temos que

$$ S = (V-N_1)360º + (N_1-2)180º.$$

Igualando as duas somas, obtemos que

$$ (N_2 + N_3 + \cdots + N_F)180º - 2(F-1)180º = (V-N_1)360º + (N_1-2)180º,$$

que é equivalente a

$$2V -  (N_1 + N_2 + \cdots + N_F) + 2F = 4$$

Observe que a soma $N_1 + N_2 + \cdots + N_F$ é igual a $2E$, pois cada aresta aparece em exatas duas faces distintas. Portanto, $V-E+F = 2$. Isto conclui a demonstração.

Relação de Euler (prova geométrica).

No último post (confira), provamos a relação de Euler usando grafos. Neste post, provaremos usando geometria.

Teorema (da relação de Euler). Se $P$ é um poliedro com $V$ vértices, $E$ arestas e $F$ faces, então vale que $$V-E+F = 2.$$

Para a prova do teorema, iremos usar o seguinte

Lema. Todo poliedro pode ser triangularizado de maneira tal que $V - E + F$ se mantenha constante.

Demonstração. Seja $P$ um poliedro qualquer. Suponha que $P$ não seja triangularizado. Seja $f$ uma face não-triangular e suponha que o número de arestas em $f$ é $n$.

Considere um vértice $v$ de $f$. Para cada vértice de $f$ diferente de $v$ e não-adjacente a $v$, trace uma nova aresta ligando $v$ a tal vértice. Como existem $n-3$ tais vértices, adicionaremos $n-3$ arestas. Isto nos dá uma triangularização de $f$. Além disso, $n-3$ faces foram adicionadas, pois cada vez adicionamos uma aresta, uma face existente é repartida em duas.

Como o processo acima não adiciona nenhum vértice e a quantidade de arestas adicionadas é igual a quantidade de faces adicionadas, temos que $V-E+F$ não se altera. Uma vez que fazemos isto para qualquer face não-triangular de $P$, podemos triangularizar todas as faces não-triangulares de $P$ de modo que $V - E + F$ não se altera. Isto conclui a prova do lema.

$\square$

O lema acima nos permite provar o teorema somente para a classe dos poliedros triangularizados. Sim, pois se $P$ é um poliedro qualquer, se tivermos que a relação de Euler é valida para uma triangularização de $P$, teremos ela também é válida para $P$, já que o lema nos assegura que $V-E+F$ não se altera na triangularização $P$. Então, iremos provar o teorema apenas para poliedros triangularizados.

Agora podemos partir para a prova do teorema.

Relação de Euler (prova com grafos).

Num post anterior, Sólidos Platônicos, usamos a famosa relação de Euler para poliedros, que é dada por:

$$ V - E + F = 2, $$

onde $V$ é o número de vértices de um poliedro convexo, $E$ é o número de arestas e $F$ é o número de faces.

A relação de Euler para poliedros é equivalente a relação de Euler para grafos planares conexos. Afinal, existe uma maneira natural de levar uma instância do primeiro problema para uma instância do segundo: sobre uma face do poliedro, "abra" o poliedro de modo que todas as faces esteja sobre um plano.  Iremos prová-la para grafos planares conexos.

Dado um grafo planar, isto é, um grafo desenhado sobre o plano e sem interseções entre arestas, chamamos de faces internas aquelas regiões internas limitadas pelas arestas do grafo que formam um ciclo. A face externa é a (única) região ilimitada. No que segue, consideramos como face tanto a interna quanto a externa.

Teorema (da relação de Euler). Se $G$ é um grafo planar conexo com $n$ vértices, $m$ arestas e $f$ faces, então vale que $$n - m + f = 2.$$

Conjectura de Erdös-Faber-Lovász

Lendo o texto do Béla Bollobás (veja aqui) e parei para pensar em qual problema seria um "sonho" para mim, isto é, um grande problema que eu amaria resolver. Depois de um tempo de reflexão, cheguei a escolha de uma conjectura em Teoria dos Grafos:

Conjectura de Erdös-Faber-Lovász. Se $k$ grafos completos, cada um tendo exatamente $k$ vértices, têm a propriedade de que cada par de grafos compartilham no máximo um vértice, então a união desses grafos pode ser colorida com $k$ cores.

Esta conjectura é de 1972 e pode ser encontrada num artigo do Erdös onde ele fala quais são os problemas que ele gostaria de ver resolvido (veja aqui o artigo).

O seu enunciado não é difícil de entender e esta conjectura tem tentado muitos combinatoristas. E este foi um dos motivos pela qual me interessei por esta conjectura.

A primeira vez que a vi foi num seminário do grupo de pesquisa da qual faço parte, o ParGO (link). Lá, vi a conjectura sendo relacionada com algo sobre b-coloração (um tema para um futuro post), do qual não lembro muito bem como isto era feito.

Confesso que já tentei resolver a conjectura algumas vezes (mais precisamente, cinco vezes). Infelizmente, meus conhecimentos em teoria dos grafos é ainda muito elementar, e o que pude aplicar na conjectura não me retornou nada muito surpreendente (mas ainda sim obtive algumas conclusões).

Cada vez que tentei resolvê-la, esta conjectura me encantava ainda mais. Sim, pois quando eu aprendia algum método novo (como o método probabilístico e o Lema da Regularidade), logo tentava aplicar na conjectura. O interessante é que tais ferramentas eram aplicáveis, em sua maioria, mas o que eu conseguia concluir não era o suficiente para provar a conjectura. É como se a conjectura fosse a prova de métodos fodásticos. Ou até mesmo, eu ainda não sou capaz de aplicá-los de maneira eficiente. Mas também acredito que muitos já devem ter tentado aplicá-los a esta conjectura.

No fim, tentar resolver a conjectura foi um bom exercício para mim. Pretendo mantê-la como um "sonho", e seguindo os conselhos do Bollobás, estudando problemas mais ao meu nível atual.

$\sqrt{2}$ é irracional.

Todo mundo já deve conhecer a prova de que $\sqrt{2}$ é irracional. Se não, deixe eu fazê-la: suponha que $\sqrt{2}$ é racional. Então existem $a$ e $b>0$ inteiros primos entre si com $$\sqrt{2}=\frac{a}{b}.$$ Elevando esta última identidade ao quadrado e multiplicando por $b^2$, temos que $$2b^2 = a^2.$$ Logo $a^2$ é par. Como a raiz quadrada de um número par ainda é par, temos que $a$ é par. Então podemos escrever $a$ como $a = 2c$. Substituindo isto na última equação destacada, temos $$2b^2= 4c^2,$$ logo $b^2 = 2c^2$. E portanto, $b^2$ é par, logo $b$ também é. Neste ponto, chegamos num absurdo! Sim, pois concluímos que se $\sqrt{2}=\frac{a}{b}$ é de fato um número racional, então $a$ e $b$ são pares, logo 2 divide tanto $a$ quanto $b$, contradizendo o fato de $a$ e $b$ serem primos entre si.

Neste post queremos dar uma outra prova de que $\sqrt{2}$ é irracional. Mas para isto iremos provar um resultado mais forte:

Teorema. Se um número real $x$ satisfaz a equação

$$x^n + c_1x^{n-1} + \cdots + c_n = 0$$

com coeficientes inteiros, então ou $x$ é inteiro ou $x$ é irracional.

Em outras palavras, não existe racional não-inteiro que seja raiz de um polinômio mônico com coeficientes inteiros.

$e$ é irracional.

Neste post, daremos um prova rápida de que $e$ é um número irracional.

Da fórmula da expansão em séries de Taylor da função $f(x) = e^x$, sabemos que

$$ e = \sum_{k = 0}^{\infty} \frac{1}{k!} = 1 + 1 + \frac{1}{2} + \frac{1}{6} + \frac{1}{24} + \ldots$$

Suponha que $e$ seja racional, i.e., existem $a$ e $b>0$ inteiros tais que $e = \frac{a}{b}$. Seja $n\geq b$ e considere

$$ N:= n!\left(e - \sum_{k = 0}^{n} \frac{1}{k!} \right).$$

Uma vez que $n!e$ e $\frac{n!}{k!}$ (para $0 \leq k \leq n$) são inteiros, temos que $N$ é um número inteiro positivo. Por outro lado,

$$N = n!\left(e - \sum_{k = 0}^{n} \frac{1}{k!} \right) = n!\left(\sum_{k = n+1}^{\infty} \frac{1}{k!} \right) = \sum_{k = n+1}^{\infty} \frac{n!}{k!}.$$

Dado $k>n$, seja $r = n-k$. Temos que

$$\frac{n!}{k!} = \frac{n!}{(n+r)!} = \frac{n!}{n!(n+1)(n+2)\ldots (n+r)} = \frac{1}{(n+1)(n+2)\ldots (n+r)} \leq \frac{1}{(n+1)^{r}}.$$

Daí,

$$N = \sum_{r = 1}^{\infty} \frac{n!}{(n+r)!} \leq \sum_{r=1}^{\infty} \frac{1}{(n+1)^{r}}.$$

Mas sendo o somatório no lado direito da desigualdade acima uma série geométrica, temos que

$$ \sum_{r=1}^{\infty} \frac{1}{(n+1)^{r}} = \frac{1}{n}.$$

Portanto, $N \leq \frac{1}{n}$, para todo $n\geq b \geq 1$, contradizendo o fato de $N$ ser inteiro positivo.

$\square$

Referências:

[1] Martin Aigner, Günter M. Ziegler; As porvas estão n'O LIVRO. Editora Edgard Blücher, 2002.

Conjecturas de Goldbach.

Um dos problemas mais antigos da matemática é a Conjectura de Goldbach. Talvez esta conjectura recebeu fama pela sua simplicidade. Algo parecido ocorreu com o Último Teorema de Fermat, que foi considerado uma conjectura por 359 anos, até que em 1994, o matemático britânico Andrew Wiles publicou uma prova para tal.

O que hoje chamamos de conjectura de Goldbach surgiu numa das cartas do matemático alemão Christian Goldbach (original de Brandenburg-Prussia) endereçada ao matemático Leonhard Euler, a carta XLIII, datada de 7 de Junho de 1742 (clique na imagem abaixo para ver a carta) [1].

Teorema da Bandeira Britânica

Neste post, quero apresentar um belo teorema em Geometria Euclidiana Plana que recebe o nome de Teorema da Bandeira Britânica. Este teorema nos diz que a soma das áreas dos quadrados vermelhos da figura abaixo é igual a soma das áreas dos quadrados azuis e isto continuaria valendo se movêssemos o pontinho preto no interior do retângulo para qualquer outro lugar ainda dentro do retângulo.

Teorema (da Bandeira Britânica). Seja $ABCD$ um retângulo. Dado um ponto $P$ qualquer dentro de $ABCD$, temos que

$${AP}^2+{CP}^2={BP}^2+{DP}^2.$$

Um texto de Béla Bollobás

Béla Bollobás é um matemático húngaro (sim, esse é um nome de menino, pelo menos na Hungria) da Universidade da Memphis e da Universidade de Cambridge. Nasceu em Budapeste em 3 de agosto de 1943, hoje tem 69 anos. Desde muito jovem se interessou por matemática e foi um dos primeiros medalhistas da IMO ( International Mathematical Olympiads), condecorado com duas medalhas de ouro e uma de bronze (veja). Conheceu Paul Erdös graças ao seu desempenho na IMO e aos 19 anos publicou o seu primeiro artigo junto com o Erdös.

Tem publicado artigos, livros e teses em Análise Funcional, Combinatória, Teoria dos Grafos e Percolação. É, atualmente, uma das principais referências em Percolação e em Combinatória Extremal.

Neste post irei publicar um texto de Béla Bollobás (foto abaixo) que pode ser encontrado no livro The Princeton Companion to Mathematics.

Sólidos Platônicos.

Com certeza, todo mundo já se deparou com os sólidos Platônicos. Pra refrescar a sua memória, temos abaixo tais sólidos. Um sólido Platônico é um poliedro cujas as suas faces são congruentes dois a dois e cada vértice contém o mesmo número de arestas incidentes. O leitor pode verificar rapidamente que em cada um dos poliedros abaixo, cada um de seus vértices contém o mesmo número de arestas incidentes. Já a afirmação de que suas faces são congruentes dois a dois exige um pouco mais, mas podemos ao menos verificar que o número de arestas são iguais em cada face de cada poliedro.

Desde os tempos dos gregos antigos já se sabiam que os únicos poliedros platônicos são aqueles da figura. No livro Elementos de Euclides já se encontrava uma descrição matemática das propriedades destes sólidos (Livro XIII, proposições 13 – 18). 

Neste post, daremos uma demonstração de que os únicos sólidos Platônicos são estes cinco. Para tal prova, iremos assumir a fórmula de Euler: $V – E + F = 2$, onde $V$ é o número de vértices de um poliedro conexo, $E$ é o número de arestas e $F$ é o número de faces. Eu prometo que logo publicarei uma demonstração desta fórmula.

Abaixo, temos uma tabela com os valores de $A$, $V$ e $F$ para os sólidos Platônicos.

Vamos agora a o teorema.

Teorema (da classificação dos sólidos Platônicos). Os únicos sólidos Platônicos são aqueles listados anteriormente.

Partições em Conjuntos Fechados.

Pode o plano ser particionado em uma quantidade enumerável de conjuntos fechados? E o $\mathbb{R}^{n}$?

Grafos: definições, nomenclaturas e notações

Neste texto, irei dar algumas noções elementares sobre grafos baseadas no livro Graph Theory [1].

Um grafo $G$ é um par ordenado $G = (V,E)$, onde $V$ é um conjunto qualquer e $E$ é uma coleção de pares de elementos de $V$, i.e., $E = \{\; \{x,y\} \; | \; x,y \in V, x\neq y\}$. Os elementos de $V$ são chamados de vértices do grafo e os elementos de $E$ são chamados de arestas. Uma aresta $e$, formalmente, é um par $e = \{x,y\}$, onde $x,y$ são vértices do grafo, mas por comodidade iremos representar a aresta $e$ apenas por $xy$, de modo que não haverá confusão ao identificarmos $e=xy=yx$.

Segundo a nossa definição de grafo, não há possibilidade de duas arestas distintas conectarem o mesmo par de vértice. Também não há chance alguma de existir uma aresta que conecte um vértice $x$ a ele mesmo (arestas deste tipo recebem o nome de laços ou loops). Assim, segundo a definição de alguns livros, o nosso grafo é um grafo simples. Mas como este é principal tipo de grafo que nos interessa por enquanto, não iremos nos preocupar em dizer que os nossos grafos são simples. Existem outros tipos de grafos tão interessante quanto os simples: grafos orientados, múltiplos, com fluxos, labelados, entre outros (ver [1]). Outra coisa, não esteremos, por enquanto, interessados em grafo cujo o conjunto dos vértices é infinito. Logo, assumiremos desde já que $|V| < \infty$. Consequentemente, o conjunto das arestas é finito também.

É muito comum e conveniente representar um grafo $G$ por um desenho sobre um plano onde os vértices são representados por pontos no plano e arestas que conectam dois vértices $x$ e $y$ são representados por linhas (retas ou curvilíneas) que contêm os pontos que representam os vértices $x$ e $y$ como extremidades. Claramente, um grafo pode ser desenhado de inúmeras maneiras distintas, logo não devemos nos apegar ao desenho do grafo, mas utilizá-lo para visualizar rapidamente algumas afirmações. Muitas vezes iremos verificar algo através de um desenho, mas isso deve ser feito de modo que fique claro que esta verificação é independente da maneira que desenhamos.

Primeira postagem e o primeiro teorema sobre grafos.

Esta é a primeira postagem do blog Tiorema! Pretendo, neste espaço, postar algumas coisitas matemáticas que acho interessante. Tem tanta coisa que nem sei bem por onde começar. Como gosto muito de combinatória, decidi começar por um dos primeiros teoremas em Teoria dos Grafos: o Teorema de Euler. O leitor que não conhece ainda a Teoria dos Grafos ou que não está muito familiarizado com as definições e notações poderá ler um post que preparei com as principais noções que usarei ao falar de grafos [link], apesar de que neste post a principal definição será feita logo no próximo parágrafo de modo que um conhecimento básico de grafos já é suficiente para uma boa leitura deste texto.

Dado um grafo $G=(V,E)$, um passeio (de tamanho $k$) em $G$ é uma sequência alternada de vértices e arestas

$$P = v_0 e_1 v_1 e_2 v_2 \ldots  v_{k-1} e_{k} v_k, $$

com $v_0, v_i\in V$ e $e_i = \{v_{i-1},v_{i}\} \in E$, pra todo $1 \leq i \leq n$. Os vértices $v_i$ não precisam todos serem distintos; quando são, $P$ é chamado de caminho. Quando as aresta $e_i$ são todas distintas, dizemos que $P$ é uma trilha. Quando $v_0 = v_k$, dizemos que $P$ é um passeio fechado; se $P$ for uma trilha, dizemos que ele é uma trilha fechada. Uma trilha fechada cujos os vértices $v_i$, para $i \geq 1$, são distintos é chamado de ciclo.

Uma trilha fechada $P$ é um circuito Euleriano do grafo $G$ se todas as arestas de $G$ estiverem em $P$. Em outras palavras, queremos percorrer todo o grafo através das arestas começando de um vértice e voltando, no fim, para o mesmo vértice, mas sem passar pela mesma aresta duas vezes. Um grafo que contém um circuito Euleriano é dito ser um grafo Euleriano.

Euler se interessou por esse tipo de passeio quando se questionou se era possível visitar todas as quatro regiões da cidade Königsberg (território da Prússia até 1945, atual Kaliningrado). Estas quatro regiões eram conectadas por sete pontes (ver figura abaixo). Mas Euler não queria visitá-las de qualquer maneira, ele queria passar por cada ponte exatamente um vez.