Arquivo mensais:outubro 2015

Os aluguéis de Berlim

Geek Hardcore

Minha namorada está buscando um apartamento para alugar em Paris começando no mês de novembro, e a busca tem sido uma tragédia em diversos atos. Cubículos pequenos, muita competição, preços altos e até imobiliárias que mais parecem esquema de pirâmide que um estabelecimento sério têm acompanhado a jornada dessa física teórica nas últimas duas semanas. Quanto aos preços, ao menos há um fator positivo, uma lei recente baixada inspirada na solução que Berlim tenta implementar para resolver seu problema de aluguéis: um teto de preço baseado no valor médio das redondezas.

A lei diz que o valor de um aluguel não pode ser superior à média do bairro de uma diferença maior que 10%. Ou seja, se a média do bairro é 22 euros o metro quadrado, um aluguel não pode ser mais alto que 24,2 euros o metro quadrado. Simples assim. Essa é uma ideia bem divertida, que me fez considerar a seguinte questão: o problema da Berlim gananciosa.

Nessa nova Berlim, a lei é um pouco mais rígida. Uma pessoa não pode impor um aluguel maior que a média de seus vizinhos cuja diferença entre a média e o aluguel seja maior que 10%. A pergunta é: é possível que exista uma cidade com essa lei em que todas as pessoas cobram o maior aluguel possível pela lei? Ou seja, obrigando as pessoas a cobrarem exatamente 110% da média de seus vizinhos, é possível haver uma cidade em que todas as pessoas conseguem cobrar essa quantia?

Para bem definir o problema, vamos estabelecer hipóteses fundamentadas na realidade. A primeira: minha cidade é unidimensional, parecida com Cuernavaca, porque quero uma noção de vizinhança bem definida e porque D=1 é meu número favorito de dimensões. Segunda: casas na periferia não têm esperança de ganhar dinheiro no aluguel em relação aos vizinhos e possuem preço fixo. Isso vem do fato, inspirado em minha experiência parisiense, de que morar longe do centro só é bom se for na direção de Versailles, e olhe lá. Isso fixa as condições de contorno do problema. Dado um preço fixo nas casas da periferia, é possível que o resto da cidade cobre um aluguel superior em \alpha porcento à média de seus vizinhos?

A resposta, e já mando com spoilers, é: depende do \alpha. Há valores em que isso é possível, mas existe um limite para a extorsão de seus inquilinos se você precisa respeitar a regra dos \alpha porcento. Para entender o que acontece, vamos começar com o caso de uma cidade pequena, a cidade de Berlim de três habitantes, chamada B_3. Vejamos a cara dessa cidade.

Cidade de Berlim 3A regra geral das casas de Berlim gananciosa é:

 x_n = \frac{(1+\alpha)}{2}(x_{n+1}+x_{n-1}).

Seja (1+\alpha)/2=\lambda, para simplificar nossa vida. A única exigência da primeira cidade de Berlim que vamos estudar, B_3, é que x_2=\lambda (1+1)=2\lambda, então o valor de \lambda pode ser qualquer coisa, não há limites para a ganância de B_3

O caso de B_4, no entanto, é diferente. Vejamos como é essa cidade:

Cidade de Berlim 4Neste caso, os valores de x_2 e x_3 serão fixos pelo sistema

 \begin{cases} x_2=\lambda(1+x_3) \\ x_3 = \lambda(1+x_2) \end{cases} .

Vocês sabem que eu gosto de matrizes, então vamos colocar isso em notação de gente grande. Os aluguéis de B_4 serão definidos pelo sistema

 \left(\begin{matrix} 1 & -\lambda \\ -\lambda & 1 \end{matrix}\right)\left(\begin{matrix} x_2 \\ x_3 \end{matrix}\right) = \left(\begin{matrix} \lambda \\ \lambda \end{matrix}\right).

Esse é um sistema linear bem bonito, mas vocês devem se lembrar das aulas do ensino que diziam, com razão, que a vida fica mais cinza, o mundo perde a cor e você perde a vontade de cantar uma bela canção quando o determinante da matriz que define o sistema linear se anula. Quando isso acontece, não há mais solução possível para o sistema. E note que o determinante que nossa querida matriz é

 \det \left(\begin{matrix} 1 & -\lambda \\ -\lambda & 1 \end{matrix}\right) = 1-\lambda^2.

Ou seja, algo muito errado acontece quando \lambda=1, que acontece no mesmo momento em que \alpha=1. Não apenas o sistema não tem solução, não há mais valor de alguel possível para satisfazer tanta ganância, mas se você tentar impor um \lambda mais alto que um, não encontrará a solução que deseja. Se \lambda > 1, a solução do sistema apresentará valores negativos de x_2 e x_3, e acho que é seguro acrescentar como hipótese baseada na realidade que preços de aluguel devem ser positivos.

Assim, percebemos que com quatro casas o valor máximo que a lei pode impor para a extorsão dos inquilinos é de \lambda=1, o que equivale a \alpha=1, ou o máximo que podemos impor é que uma casa cobre o dobro da média dos vizinhos. Vejamos o que acontece quando a cidade é maior, visitemos B_5.

Cidade de Berlim 5Nesse caso o sistema linear que define os valores de x_2, x_3 e x_4 será

 \left(\begin{matrix} 1 & -\lambda & 0 \\ -\lambda & 1 & -\lambda \\ 0 & -\lambda & 1 \end{matrix}\right)\left(\begin{matrix} x_2 \\ x_3 \\ x_4 \end{matrix}\right) = \left(\begin{matrix} \lambda \\ 0 \\ \lambda \end{matrix}\right).

Vamos chamar a matriz que define esse sistema 3 x 3 de A_3. A partir de agora, a matriz que define o sistema n \times n será A_n. O determinante dela pode ser calculado com aquela técnica que você aprendeu no segundo colegial e errava toda vez que tentava fazer de cabeça sem usar aquela técnica das duas colunas fantasmas que você copia ao lado da última.

 \det A_3 =1-2\lambda^2

E o determinante se anula no valor \lambda = \sqrt{2}/2, o que equivale ao valor de \alpha=\sqrt{2}-1\approx 0.71, que é menor que um. É fácil perceber a tendência desse problema: quanto maior a cidade, menor é a taxa de ganho extra que podemos cobrar e ainda exigir que todos cobrem mais aluguel que seus vizinhos. O valor de \alpha diminui com o número de casas N da cidade! Mas… diminui como?

E aqui vou descrever como foi meu processo para resolver esse problema. Eu queria achar a relação entre o \alpha máximo e N, o tamanho da cidade. Eu sabia que \alpha seria decrescente em N, mas não sabia como. Seria \alpha proporcional a 1/N? Ou a 1/N^2? Ou talvez uma exponencial negativa de N? A exponencial eu podia ignorar, vi matrizes vezes demais no olhos e sei que esse tipo de problema terá uma relação polinomial, mas não vou excluir a possibilidade. Para resolver esse problema, a primeira coisa que fiz foi pensar como físico, ou seja, trigger warning aos que gostam de um raciocínio matemático rigoroso. Vamos pegar uma cidade muito grande, grande o suficiente para ignorar as bordas, e vamos voltar à equação principal do modelo:

 x_n = \frac{(1+\alpha)}{2}(x_{n+1}+x_{n-1}).

E podemos jogar um pedaço para lá e outro para cá para obter uma outra forma dessa equação de recorrência:

 \alpha (x_{n+1}+x_{n-1}) = x_{n+1}+x_{n-1}-2x_n.

O termo à direita é um velho amigo nosso, é uma segunda derivada discreta do aluguel. Nós brincamos com algo parecido em um dos primeiros posts desse blog, sobre a interpretação física do Laplaciano, e chegou a hora de usá-la. Eu tenho que dividir esse termo da direita por um diferencial ao quadrado para obter uma derivada, e esse diferencial é o tamanho de meu grid na derivada discreta. Em termos do modelo, eu defino que a posição de cada casa é dada pela variável l e a distância entre duas casas é dada por \Delta l^2. Dividindo ambos os lados da equação por \Delta l eu obtenho:

 \frac{\alpha}{\Delta l^2}(x_{n+1}+x_{n-1}) = \frac{x_{n+1}+x_{n-1}-2x_n}{\Delta l^2}.

O lado direito dessa equação, quando a cidade é bem grande e as casas são bem próximas, converge para \frac{d^2x}{dl^2}, enquanto o termo da esquerda pode ser simplificado lembrando que a soma dos vizinhos é \frac{2x_n}{(1+\alpha)}. Isso tudo resulta na seguinte equação diferencial:

 \sigma.x(l) = \frac{d^2x}{dl^2}.

Sendo

 \sigma = \frac{2\alpha}{(1+\alpha)dl^2}.

Eu sei que esse diferencial no denominador é revoltante a seu espírito matemático, mas não é mais minha responsabilidade zelar por seu coração sensível. Esse dl é a distância entre duas casas. Suponhamos que a cidade toda tenha tamanho 1, em unidades de tamanho de cidade, então a distância média entre duas casas é dl=1/N. Para que essa equação diferencial faça algum sentido, eu preciso que \sigma não seja nem zero, nem infinito, então, como exigência, eu preciso que \alpha diminua conforme dl diminui, ou seja, preciso que:

 \sigma=\frac{2\alpha}{(1+\alpha)dl^2}\sim 1\Rightarrow\alpha\sim\frac{1}{N^2}

Sendo esse \sim o símbolo oficial de “tem o mesmo comportamento assimptótico de”, mas costumamos ler como: “se comporta como”, “é mais ou menos parecido em algum limite que eu espero que você tenha entendido” ou “não exatamente, mas tipo quase lá”.

Então o valor máximo da extorsão deve decrescer com o quadrado do número de casas. O problema está razoavelmente resolvido, mas o algebrista dentro de mim grita por uma solução melhor que essa. Vamos ver como seria aquela matriz A_n para uma cidade bem grande. Teremos algo da forma:

 A_n = \left(\begin{matrix} 1 & -\lambda & 0 & 0 & \cdots & 0 \\ -\lambda & 1 & -\lambda & 0 & \cdots & 0 \\ 0 & -\lambda & 1 & -\lambda & \cdots & 0\\ \vdots & \ddots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & -\lambda & 1 \end{matrix}\right).

A_n é uma matriz tridiagonal com diagonal repleta de 1’s e co-diagonais preenchidas por -\lambda. Eu não apenas quero o determinante dessa criatura, eu quero encontrar as raízes do determinante e, mais especificamente, a primeira raiz que seja maior que \frac{1}{2}. Eu sei que \lambda=\frac{1}{2} equivale ao caso \alpha=0, onde todos aluguéis são iguais à média dos vizinhos e, pelas condições nas bordas, isso representaria o caso em que todos os aluguéis são iguais a 1. Valores de \lambda menores que meio representariam alguém cobrar um aluguel menor que a média dos vizinhos e, por mais que esse seja o sonho de minha namorada, não serão considerados. A primeira raiz do determinante que é maior que meio equivale ao primeiro valor de \lambda que torna o sistema impossível, valores acima disso tornam alguns aluguéis negativos e não me interessam. Eu quero saber como a primeira raiz do determinante acima de meio se aproxima de meio quando o tamanho da matriz aumenta, e isso não é um problema muito fácil.

O determinante de uma matriz tridiagonal tem fórmula, e nesse caso essa fórmula é:

 \det A_n=\det A_{n-1}-\lambda^2\det A_{n-2} .

Isso não me ajuda muito, aliás, quase me desespera. Isso significa que o determinante será um polinômio de grau cada vez mais alto em \lambda e eu conheço minhas limitações, resolver um polinômio de grau maior que quatro exatamente quase nunca é possível e eu começo a perder a esperança quando escrevo os primeiros cinco casos desse polinômio, eles não parecem ter nenhum padrão reconhecível e minha busca parece vã. Eu vou atrás das raízes desses polinômios, e lá as coisas começam a ficar interessantes.

No caso de A_2, encontramos \lambda=\pm 1 como raízes. Para A_3, temos as raízes \lambda=\pm\frac{\sqrt{2}}{2}. O determinante A_4 ainda tem raízes, é um polinômio de grau 4 que pode ser reduzido a um polinômio de grau 2 (a origem dessa redução é a simetria do problema, a segunda casa, por simetria, deve ter o mesmo valor da penúltima, por exemplo). As raízes são \lambda=\pm \frac{1\pm\sqrt{5}}{2}, que, aliás, são a razão áurea e sua inversa.

Espera… 1, \frac{\sqrt{2}}{2} e razão áurea… eu conheço esses valores. Eles são todos cossenos de alguém (ou quase)! Isso não pode ser coincidência. O determinante de A_n é um polinômio cujas raízes possuem uma ligação com cossenos. E quando eu percebi isso, fechei os punhos e soprei por entre os dentes cerrados a palavra Chebyshev

Eu e você nos lembramos da aula de Física-Matemática II, quando Domingos Marchetti mandou aquela lista de exercícios que pedia para provar propriedades dos polinômios de Chebyshev. Entre elas, o fato de que polinômios de Chebyshev possuem \cos(\frac{k\pi}{n+1}) como raízes. Se eu quero um polinômio com essas raízes, preciso torturar Chebyshev. E eu devia ter desconfiado, veja a relação de recorrência que gera esses polinômios. Seja T_n(x) o polinômio de Chebyshev (de segundo tipo) de grau n, teremos:

 T_{n}(x) = 2xT_{n-1}(x)-T_{n-2}(x)

E me diz se isso não é muito parecido com minha relação de recorrência dos determinantes de A_n! O determinante de A_n não é exatamente T_n(x), mas eu consigo ligar os dois com algumas manobras. O post já está longo e vou escrever direto a relação, é fácil chegar nela operando a relação de recorrência. Teremos

 \det A_n=(2\lambda)^nT_n\left(\frac{1}{2\lambda}\right).

Ou seja, se queremos as raízes do determinante de A_n, basta tomar o inverso das raízes do polinômio de Chebyshev! Sabemos que essas raízes são x_k=\cos(\frac{k\pi}{n+1}). Assim, as raízes de nosso determinante tridiagonal são dadas por:

 \lambda_k=\frac{1}{2\cos\left(\frac{k\pi}{n+1}\right)}

Sem surpresas, esses valores coincidem exatamente com 1, \frac{\sqrt{2}}{2} e razão áurea. Queremos a primeira raiz acima de meio, ela é dada quando calculamos o valor k=1. Dessa forma, o maior valor possível da Berlim gananciosa será

 \lambda_{\text{max}}=\frac{1}{2\cos\left(\frac{\pi}{n+1}\right)}\sim\frac{1}{2}+\frac{\pi^2}{4N^2},

onde expandi para grandes valores de N para ver o comportamento assimptótico de uma cidade grande. Como \lambda=\frac{1}{2}+\frac{\alpha}{2}, confirmamos que, para que esse sistema tenha soluções positivas, existe um limite máximo no lucro dos proprietários que diminui conforme o tamanho da cidade aumenta, e é dado por:

 \alpha<\frac{\pi^2}{2N^2}

Confirmando o que nossa intuição física já sabia naquele cálculo sem rigor acima, a dependência ocorre com o inverso do quadrado do número de habitantes na cidade unidimensional.

E no caso da cidade bidimensional? Não consegui resolver a matriz dessa, não houve Chebyshev que salvasse, mas o cálculo não rigoroso, que deu certo uma vez, parece indicar uma dependência no inverso de N, considerando uma cidade quadrada cujas bordas contém \sqrt{N} casas enfileiradas.

Eu imagino que esse problema tenha sido um pouco mais difícil que o problema médio que apresento aqui, mas é fascinante. Nunca antes eu tinha encontrado polinômios de Chebyshev in the wild, tampouco com uma motivação tão interessante. Vou guardar esse na manga, esperando algum dia algum aluno preguiçoso, como eu era, perguntar-me de que servem esses tais polinômios cujo nome eu tenho que dar ctrl-c ctrl-v para não errar.

E uma nota final: minha namorada encontrou um apartamento finalmente. Fica em uma cidade simpática ao sul de Paris, com acesso ao metrô, mas não tão perto, com alguns metros quadrados, mas não tantos. Foi difícil achar, então comemoramos; mas confesso que, se perguntasse um pouco pelos corredores do prédio, provavelmente ficaria estarrecido em descobrir que o \alpha desse lugar não respeita nenhum majorante.

Nobel 2015: Oscilações de caráter

Rookie

Edição 06 de outubro de 2015: Esse tópico foi recompensado com o prêmio nobel da física de 2015 aos cientistas Arthur B. McDonald e Takaaki Kajita, absolutamente merecido. Reaproveito esse post de 2012, em um foreshadowing exemplar de minha parte, e mando-o para o dia de hoje. Parabéns à física de partículas, vocês ganham esse round.

A predição e descoberta dos neutrinos na segunda metade do século XX foi uma das grandes conquistas da física de partículas e da astrofísica. Pequenos, rápidos e quase indetectáveis, esses pequenos diabos roubam a energia das explosões de supernovas e bombardeiam outras galáxias, atravessando o espaço em uma velocidade próxima à da luz. A Terra é bombardeada o tempo todo por uma quantidade colossal de neutrinos, felizmente eles interagem muito pouco com a matéria e, até tentando, é difícil detectar um. Os caçadores de neutrinos, em especial o Super Kamiokande – um detector de neutrinos com nome de herói japonês que, não por menos, é parte da Universidade de Tóquio – possuem um trabalho duro. Em 1987, ano da explosão de uma supernova próxima à Terra, nosso planeta foi atingido pela maior onda de neutrinos da era da ciência moderna, detectamos 24.

Interior do Super Kamiokande

E medidas mais precisas do número de neutrinos quase levaram a comunidade física à loucura no final do século XX. A física teórica, aliada a alguns experimentos na Terra, nos dizia exatamente a probabilidade de medir neutrinos, a astrofísica nos dizia a quantidade de neutrinos produzida pelo Sol, era só multiplicar um pelo outro para estimar a quantidade de neutrinos que seríamos capazes de medir na Terra a cada ano. O problema: medíamos muito menos do que deveríamos.

Diversas hipóteses foram levantadas: neutrinos perdidos na atmosfera, detectores que funcionavam mal, nada era o suficiente para explicar a diferença. Claro, a diferença era entre medir 12 e 24, mas, por menor que fossem esses números, um ainda era o dobro do outro; e a física é bem intolerante com teorias que “quase funcionam”.

Pior, essa diferença variava com o ano. Havia uma grande diferença entre o número de neutrinos medidos em julho e em janeiro, mas entre dois janeiros consecutivos a taxa de captação de neutrinos era quase equivalente. Ainda, nos dois casos, o número era praticamente metade do esperado, e isso aumentava o mistério. Coloco um gráfico para entender a diferença entre o recebido e o esperado. As barras em azul escuro são as medidas, as mais coloridas são as esperadas (as cores nas barras teóricas representam o processo pelo qual os neutrinos são emitidos). A parte hachurada representa o erro experimental.

Antes de solucionar o mistério, precisamos entender um pouco sobre o neutrino e sobre as partículas. A maior parte das partículas elementares (os férmions, para ser exato) vêm em três tipos, ou três sabores: leve, médio e pesado. O elétron, por exemplo, é o membro leve da sua família, seus irmãos maiores são o múon (médio) e o tau (pesado). Não ouvimos falar muito dos membros mais pesados da família porque a formação deles é mais rara no universo, sendo mais pesados, eles são mais difíceis de serem “fabricados”. Neutrinos vêm em três tipos, nós definimos esses tipos através do método de formação deles, porque neutrinos sempre se formam em uma reação que envolve alguém da família do elétron. Os neutrinos que saem de uma reação com o elétron são chamados, por falta de criatividade, de “neutrino do elétron”, sendo os outros “neutrino do múon” e “neutrino do tau”. Retirei do site particlezoo uma representação dessas partículas elementares em pelúcia:

No começo dos anos 2000, os físicos decidiram tentar algo diferente. Eles tentariam captar todos os tipos de neutrino, não apenas o do elétron, como vinham fazendo até então. A experiência parecia fadada ao fracasso, porque o Sol só produz neutrinos do elétron, os demais que apareceriam seriam raros demais, vindos de processos exóticos em estrelas longínquas. Para o espanto da comunidade científica, a quantidade de neutrinos do múon que atinge a Terra é quase igual a dos neutrinos do elétron. Usando a soma de todos os tipos de neutrino, aquelas barras “esperado” e “medido” coincidiam!

Mas como explicar isso? A única forma de explicar foi compreender o fenômeno de oscilação de neutrinos. Lembro que as partículas elementares não são como aquelas pelúcias fofinhas, elas não precisam obedecer às regras da física “convencional” e não o fazem. Um neutrino, quando é produzido em uma reação com um elétron, é um neutrino do elétron, mas só naquele momento. Durante seu “voo” até a Terra, ele não é nem neutrino do elétron, nem do múon, nem do tau, ele é um neutrino. Quando nós o capturamos, ele tem uma certa probabilidade de reagir com um elétron e uma certa probabilidade de reagir com um múon, e nisso damos o nome para ele. Mas note que ele não é nenhuma dessas categorias, mas um estágio intermediário entre elas que, quando medimos, “escolhe” qual estado será.

Isso é bem confuso e analogias são difíceis. Qualquer analogia que explica bem a mecânica quântica está errada, mas vou tentar assim mesmo. O neutrino, nesse sentido, é como um cilindro, mas somos apenas capazes de medir objetos de um jeito estranho: imagine que conseguimos pintar o cilindro com tinta e, em um dado momento, colocá-lo em um papel e medirmos a figura que ele “pinta” com a tinta. Em seguida, tentaríamos entender o que é esse objeto através de nossos conhecimentos de figuras planas. Imagine que o cilindro está girando, rodando no ar de forma aleatória. Quando batemos o cilindro no chão e estudando sua mancha, ela tanto poderá ser retangular (a marca do “lado” do cilindro) quanto poderá ser circular (a marca da base do cilindro), tudo depende da posição em que ele estiver rodando. Os neutrinos agem de forma parecida, eles são uma mistura dos três estados (elétron, múon e tau) e, quando os medimos, eles se manifestam de uma forma na experiência. Porque nossa compreensão do neutrino é apenas o que medimos quando ele é produzido ou aniquilado, damos a ele esses nomes; assim como se só fôssemos capazes de medir a mancha diríamos que o cilindro é um objeto que está no estado círculo e no estado retângulo ao mesmo tempo, “escolhendo” um desses estados quando vamos medir sua marca de tinta.

Com isso, o mistério da variação no ano está resolvido. A probabilidade de encontrar um neutrino no estado elétron ou múon varia de acordo com seu tempo de voo, há pontos de sua trajetória em que ser do elétron é mais provável que ser do múon. Mas a Terra gira em torno do Sol e a distância entre nós e o astro rei varia com o ano (estamos mais próximos do Sol em janeiro e mais afastados em julho), não o suficiente para afetar muito o clima, mas essa diferença na distância dá mais tempo de voo aos neutrinos e afeta suas probabilidades, tornando a repartição elétron-múon diferente em cada momento do ano mas, entre um janeiro e outro, o  comportamento deve ser o mesmo.

Vale notar que os experimentos para medir neutrinos, essa “partícula-fantasma”, acontecem desde os anos 60, e dou destaque especial às experiências de Raymond Davis, prêmio Nobel de 2002 por seus experimentos. Davis transformou uma antiga mina de ouro em South Dakota em um grande detector de neutrinos. A medição era feita usando colisões de neutrinos com átomos de cloro, a mina era necessária para isolar o experimento de raios cósmicos que podiam parecer neutrinos, e todo ele era cercado por água, o que garantiria que só neutrinos atingiriam o cloro. A mina podia ficar bem quente em algumas épocas do ano, por isso coloco aqui uma foto de Davis nadando na água de seu experimento.

Raymond Davis Jr. Nobel da física de 2002.

E isso soluciona o mistério dos neutrinos desaparecidos e abre um capítulo interessante para entender a natureza das partículas elementares e esse tal fenômeno de oscilação. Nem tudo é o que parece, em especial os neutrinos, que são, na verdade, uma mistura de tudo o que deles podemos medir.

Continue lendo