Probabilidad de primos y la función mu de Möbius

Hace un par de días me puse a jugar un poco con la distribución de primos y con algo que he denominado primos de orden k, y me topé con una interpretación probabilistica de un resultado que involucra la función $\mu$ de Möbius.

Nunca en realidad he llevado un curso formal sobre teoría analítica de números, ni nada parecido con teoría de números avanzada, por lo tanto no había analizado la posible motivación detrás de la definición de la función $\mu$.

Para un natural $n$, $\mu(n)$ se define como 0 si $n$ tiene un factor primo cuyo exponente es mayor que 1, y $(-1)^k$ si $n$ tiene $k$ factores primos diferentes. Por lo tanto esta función es diferente de 0 únicamente para los números libres de cuadrado, -1 si el número posee un número impar de factores, y 1 si posee un número par.

Al principio, esta definición suena muy artificial, sin embargo, desde un contexto diferente, se puede tener una concepción un tanto más natural.

Supongamos por un momento que tenemos un entero cualquiera y queremos calcular la probabilidad que este sea compuesto. Bueno, si conocemos explicitamente dicho número podemos responder esta pregunta deterministicamente, sin embargo, si escogemos un número al azar, podemos hablar de la probabilidad de que sea compuesto.

Bueno, si un número es compuesto, esto significa que es producto de primos, así que podemos calcular dicha probabilidad $P$ encontrando cuál es la probabilidad que sea un multiplo de 2, 3, 5, 7, 11, etc.

Obviamente, la probabilidad que un número sea multiplo de 2 es $1/2$, puesto que la mitad de los numeros son pares, de igual manera, $1/3$ de los números son multiplos de 3 y así, la probabilidad de ser múltiplo de $p$ es $1/p$.

Por lo tanto, para calcular la probabilidad total, no es dificil convenserse que es necesario utilizar el principio de inclusión-exclusión para calcular la probabilidad de ser multiplo de algún primo, es decir, de ser compuesto.

Con esto, la probabilidad queda

$P=\frac{1}{2}+\frac{1}{3}+\frac{1}{5}\dots-\frac{1}{2\cdot 3}-\frac{1}{2\cdot 5}-\frac{1}{3\cdot 5}-\dots+\frac{1}{2\cdot 3\cdot 5}\dots$

Tratando de reescribir esta expresión, no es dificil concluir que esto se puede escribir como

$\sum_{n=2}^\infty \frac{a_n}{n}$

en donde $a_n$ es 0 si $n$ tiene factores primos repetidos, $1$ si $n$ es elproducto de un número impar de primos y $-1$ si $n$ es el producto de un número par de primos, lo cual puede escribirse jústamente usando $\mu$ como $a_n=-\mu(n)$.

Por otro lado, como es bien sabido, la mayoría de números son compuestos, de hecho el Teorema de los Números Primos establece que la razón entre el número de primos menores que $x$ y $x$ tiende a 0, por lo que la probabilidad de ser compuesto (razón entre "el número de compuestos y todos los números") es 1, así que $P=1$. Con esto tenemos que

$\sum_{n=2}^\infty -\frac{\mu(n)}{n}=1$

y como $\mu(1)=1$, podemos decir que

$\sum_{n=1}^\infty \frac{\mu(n)}{n}=0$

Es facinante como es posible interpretar la función $\mu$ simplemente como el principio de inclusión-exclusión para los números primos, y por medio de este mismo argumento, se puede mostrar facilmente que

$\sum_{n=1}^\infty \frac{\mu(n)}{n^s}=\frac{1}{\zeta(s)}$

donde $\zeta(s)$ es la función Zeta de Riemann. Justamente, para $s=1$, la función Zeta posee un polo de orcden 1 y por lo tanto $\frac{1}{\zeta(1)}=0$.

De esta manera, la función $\mu$ surge de una forma un tanto más natural y, al menos para mí, deja de ser un ente muy raro y misterioso.

Atractors for the Differential Operator

The other day, I was thinking about how you can find fixed points for some functions in an easy way, for example, for $f(t)=\cos(t)$, if you start with any initial point $t_0$ and iterate the function on it, you will reach a fixed point, i.e. $f^n(t_0)\to t_{fix}$ as $n\to \infty$ which is approximately $0.739085$.

Then I ask myself if you can mimic the same procedure for finding fixed points, and hence attractors when instead of treating numbers one uses functions. In this particular case, I picked the differential operator $T=\frac{d}{dt}$, so the idea was to study the behavior of $\{T^n(x_0)\}_{n=0}^\infty$ for $x_0$ a initial function.

For instance, looking for the fixed points of this operator is a rather easy task, since it is the same as solving the differential equation $\frac{d}{dt}f(t)=f(t)$, which has general solution given by $f(t)=Ae^t$.

This approach give us more than just the fixed points for this operator, but also tells us that the space of functions in which we are interested for this operator to act, is the space of smooth funtions, i.e functions which have infinite number of derivates. Then we can formalize our discussion as studying the dinamics of the differential operator $T:C^\infty\to C^\infty$.

The natural question would be what happens to a general function when iterate $T$ to it? Is it going to be atracter by one of the fixed points? Or is it going to be blown up to "infinity"?

For example, if our initial function $x_0$ is a polynomial with degree $n$, we have that $T^{n+1}x_0=0$, so all polynomials are in the basin of atraction of 0, that is, after aplying many finite times the operator $T$, every polynomials will get map to 0.

On the other hand, if we start with $x_0=\cos(t)$ or $x_0=\sin(t)$, we have that this leads to a periodic orbit, namely $T^2x_0=x_0$, so the sequence $\{T^nx_0\}$ does not converge, but rather stays in a cycle.

In general, for having a periodic orbit when starting at a function $x$, one has to have that $T^mx=x$ for some $m\in\mathbb{N}$. Solving the differential equation gives that $x=\sum_{k=0}^{m-1}A_k e^{\lambda_m^k t}$, where $\lambda_m$ is the primitive $m$-root of unity in the complex numbers, and $A_k$ are constants.

Here we looked at some examples where the sequence converges or stays in a cycle, but it can also happen that the sequence diverges, for instance if we let $x_0=e^{cx}$, with $c\neq 1$, we will have that $\{T^nx_0\}$ diverges.

Now, if we try to analyze what the behaviour would be for a general smooth $x_0$ function, in order to stablish wheter the orbit of $x_0$ is attracted to a fixed point, it is periodic or it diverges, we need te notion of a distance in between functions or a norm. $C^\infty$ is a vector space, since the linear combination of smooth functions is again a smooth function, but it lacks the structure of a Banach space, which is that there doesn't exist any norm such that the space is complete. This doesn't help too much in pursue of a simple way of finding these attractors like we did with real and complex numbers via a analityc function. So the idea of finding these orbits for $T$ requires a little bit of more effort.

Trying to fix this impediment, I found that $C^\infty$ has the structure of a Fréchet space, with is endowed not with a norm, but instead with a family of seminorms. This way we can talk about being close to a fixed point and the notion of being attracted to.

I'm still reading at this point what can be done to generate this sets that are being attracted or repeled by this fixed points, which would be somehow equivalent to the notion of a Julia and Fatou sets for $T$. The idea of finding these fractals of functions seems to me really interesting and I haden't tought of it until I was actually writing this post, so it was somehow related to the previous post just by chance and it wasn't made on purpouse.

Antenas Fractales

Muchos de nosotros hemos oído las palabras antena y fractal en algunos lugares por separado, y apuesto a que pensamos que son cosas que no pudieran tener nada en común.

Por un lado, una antena es un dispositivo pasivo que se utiliza para radiar ondas electromagnéticas y así poder transmitir información o energía a través de largas distancias sin la necesidad de cables.

Por el otro lado, muchas veces asociamos la palabra fractal con descanzadores de pantalla, gráficas y obras de arte con patrones de espirales y picos, y los más conocedores en el tema saben que un fractal es un objeto matemático asociado con funciones de variable compleja y recurrencia.

¿Cómo es posible conectar estos dos conceptos? Bueno, la respuesta la poseen muchos en los bolsillos de sus pantalones en estos momentos: un celular.

Al estudiar sobre telecomunicaciones, uno aprende que es posible diseñar una antena para un tipo de señal moduladora dependiendo de la frecuencia de la misma. Así, generalmente para transmitir una onda que esta siendo modulada a una frecuencia $f$, la antena se diseña típicamente para que tenga una longitud de $\frac{c}{2f}$, donde $c$ es la velocidad de la luz ( o la velocidad de propagación de onda en un medio más general ). Así que la longitud de la antena está determinada por la frecuencia a la que se transmite, algo no muy difícil de creer, por esa razón vemos en las calles antenas grandes, generalmente con partes rojas y blancas, para las transmisiones de radio AM, y antenas pequeñas que parecen bocinas de computadora, para las transmisiones de celulares e internet.

En nuestros días, la gran mayoría de servicios de telefonía móvil utilizan un tipo de transmisión a base de SDH, que significa que no se transmite en una sola frecuencia, sino que se tiene un rango de frecuencias en el que se transmite, alrededor de unas 75 frecuencias diferentes. Entonces, según la forma tradicional de diseño de antenas, deberíamos tener unas 75 antenas en nuestros teléfonos móviles, sin embargo esto no sucede así, puesto que resultaría demasiado ineficiente.

Pero entonces ¿cómo solucionar el problema de recibir 75 frecuencias diferentes usando la misma antena? Bueno, los fractales saltan al rescate. Una de las propiedades que poseen los fractales, es que tienen patrones de autosimilitud, es decir, la forma básica del fractal se repite una y otra vez en diferentes escalas.


Por medio de un diseño fractal de antena como el anterior, es posible lograr recibir una frecuencia fundamental $f$, la mitad de esta $f/2$, las cuartas partes $f/4$ y $3f/4$ y las octavas partes $f/8$, $3f/8$, $5f/8$ y $7f/8$.




De esta manera es posible utilizar la autosimilitud para recibir ondas similares transmitidas en diferentes frecuencias fundamentales. El tipo de fractal utilizado depende de otros parámetros como tipo de modulación, rango de transmisión, tipo de transmisión, etc.

Roots of unity and quadratic residues modulo p

Yesterday, I attended to a talk of Brian Conrey while his visit to Baylor, and among other things of his talk, I found this fact really interesting.

He was talking about prime numbers, their distribution and the connection with the Riemann Zeta function, in other words, some kind of connection with complex numbers.

He showed that when taking the unit circle and diving it into $p$ equal slices, one can enumerate each edge from 0 to $p-1$ and then take the quadratic residues modulo $p$ and the sum of the correspondent vectors has norm equal to $\sqrt{p}$.

Here is the picture for $p=5$. After doing this, I found out that, I didn't remember the fact way it was, since if we calculate this resultant vector, it has norm equal to 1.61803, which is not $\sqrt{5}$, so I tried to figure what the statement was. After a little of work, I found that I was not able to remember the statement at all, but I came with something that was pretty close to it, if instead of summing along the quadratic residues, we sum along the residues squared, we have the desired result, that is, instead of summing the 0,1,4 vectors, we sum $0^2,1^2,2^2,3^2,4^2$, that is $0,1,4,4,1$, we'll have that the norm of the resultant is in fact $\sqrt{5}$.


So I thought that maybe for the general case, if we add the vectors corresponding to squares of the residues, we would have the same result. For proving this, we can write the problem as follows:

Let $p$ be a prime, then $z=\sum_{k=0}^{p-1} e^{\frac{2 \pi i}{p}k^2}$ has norm $\sqrt{p}$.

The proof of this fact is quite simple. This is the same as $z\bar{z}=p$, so calculating that gives

$|z|^2=\left(\sum_{k=0}^{p-1} e^{\frac{2 \pi i}{p}k^2}\right)$ $\left(\sum_{k=0}^{p-1} e^{-\frac{2 \pi i}{p}k^2}\right) $ $=\sum_{n,m}^{p-1} e^{\frac{2 \pi i}{p}(n+m)(n-m)}$

Since $p$ is prime, we can rearrange terms, and write the previous expression as $\sum_{r=0}^{p-1}\sum_{s=0}^{p-1}\left(e^{\frac{2\pi i}{p}r}\right)^s$, which is just a bunch of geometric sums added up. Each sum is easily calculated for $r\neq 0$ as $\frac{\left(e^{\frac{2\pi i}{p}r}\right)^p-1}{e^{\frac{2\pi i}{p}r}-1}$ which is equal to 0 for $r\neq0$. When $r=0$, the sum is exactly $p$, so in the end, $z\bar{z}=p$.

Then after, I tried the same kind of result with a general natural number, and it seems to work also with the odd numbers, but with the evens the pattern is a little different. For some, the norm is the square root of twice the number and for others it is zero. It is a really interesting question what happens for the general case, in particular for the even numbers, since it seems to depend if the number is multiple of 4.

The reason why the previous procedure does not work in general is that for a composite number, the double summation cannot be rearranged as we did, because $\mathbb{Z}_n$ is not a multiplicative group and $k \mathbb{Z}_n\neq \mathbb{Z}_n$ for all non-zero $k\in\mathbb{Z}_n$.

Probabilidad de obtener un triángulo

¿Quién al ir a un restaurante no ha hecho trocitos los palillos de dientes mientras espera la comida? A pesar que partir palillos en muchos pedazos suena una alternativa para matar el tiempo de espera, una pregunta un poco mas interesante es calcular la probabilidad que al quebrar dos veces el palillo, los 3 segmentos resultantes constituyan los lados de un triángulo.

A primera vista parece que esto siempre se puede hacer, sin embargo al probar unas cuantas veces, uno se da cuenta que pocas veces se logra constuir un triángulo con los pedazos.

Para lograr calcular exactamente cual es la probabilidad de que esto ocurra, podemos hacer un modelo de que es lo que pasa al quebrar un palillo dos veces,

Para tener que dichos pedazos logren formar un triángulo, debemos tener que las longitudes cumplan la desigualdad del tríangulo.

Si tenemos un triángulo con lados $a,b,c$, la desigualdad del triángulo dice que $a\leq b+c$ $b\leq c+a$ y $c\leq a+b$. Aún más, si se tienen 3 reales que satisfacen dichas desigualdades, es posible construir un triángulo cuyos lados seas dichos reales. Asi que si $x,y$ y $1-x-y$ satisfacen dichas desigualdades, tendremos que es posible construir un triángulo a partir de los pedazos.

Para lograr encontrar la probabilidad, primero debemos hallar el total de casos posibles, y para eso encontramos los posibles resultados al quebrar el palillo, es decir, la región donde $0\leq x$, $0\leq y$ y $0\leq 1-x-y$. Dicha región está dada por




Así que el área total del espacio muestral es $1/2$. Para calcular el total de casos favorables, debemos tener que se satisfagan las desigualdades del triángulo, es decir, $x\leq 1-x-y+y$, $y\leq 1-x-y+x$ y $1-x-y\leq x+y$, lo cual da la región

cuya área es $1/8$, por lo que la probabilidad de lograr construir un triángulo está dada por

$\frac{\text{casos en los que se forma un triangulo}}{\text{casos totales}}=\frac{1/8}{1/2}=1/4$
Así que en un 25% de los casos, es posible construir un triángulo con dichos pedazos, lo cual resulta ser mucho menos de lo esperado, asi que la proxima vez que vaya a un restaurante, intentelo al menos 4 veces.

Why a melody one octave higher feels the same?

A couple of weeks ago, while a road trip to Pittsburgh with my good friend Antonio, one topic jumped to the conversation, and it was why do we feel like a melody played in different octaves is the same.

The answer was not so difficult to find: Because we are hearing the same fundamental frequencies and their harmonics, but that is the mathematical point of view and unless the ear is good with Fourier series, this answer is not so obvious.

In fact, it happens to be that the ear is a good mathematician, or at least designed by a great one.

First of all, what is an octave. When you rise or decrease a note by an octave, it means you are multiplying or dividing the frequency by 2, therefore, an octave higher of a central A note (440Hz) has a frequency of 880Hz, and an octave lower, 220Hz. So there is an easy way to know if two melodies are alike, if their ratio is a power of 2, they must be the same!

Now our good ear has a pretty concrete task, still a little uncertain how can it be achieved though. Well the answer lies within would a Dream Theater song say, if we look at the process of how hearing is made, we can go deeper into the inner ear or labyrinth and find our answers. Here, after a mechanical process of sound transmission, there are located two chambers, each filled by liquids of different electronegativity.

These two chambers are separated by a thin layer that has several valves that can allow the two fluid to be mixed. Each of these valves are opened by a thin filament that, when excited, opens the valve. When the liquids mix, this produce an impulse that triggers a neuron and sends the sound information to the brain.

Now, here magic happens, one of these chambers is connected to the mechanical system that transmits the incoming sound wave, and it produces a standing wave in this chamber. The little filaments are arranged in such a way that the smaller ones are in front and the bigger ones in the back of the chamber. All the detection work is done by these little filaments, that have lengths growing exponentially, and moreover, each one is twice or half as long as its neighbors.

Hence, for a fixed frequency, any octave of it would excite the same filaments inside our inner ear, and therefore the same neurons are triggered and that makes us feel like is the same sound or melody we played a different octave, just with a little different flavor.

Bloggeando con Latex

Buenas noticias para los bloggeros, es posible postear $\LaTeX$ en la mayoría de los Blogs que nativamente no lo soportan. Simplemente es cuestión de añadir un JavaScript al Blog y voilà, $\LaTeX$ en la página.

Aca está el link para que lo vean

http://watchmath.com/vlog/?p=438