¿Cómo se oye el cubo de Rubik?

Hace algunos días encontré una charla TED-Ed muy interesante sobre como relacionar al cubo de Rubik con la música.

Describe un poco la matemática detrás de la resolución del cubo de Rubik presentando los conceptos de grupo, permutaciones, y de como esta estructura matemática puede recibir una interpretación musical.

Ciertas técnicas en teoría musical son precisamente transformaciones realizadas por elementos de un grupo, lo que en matemática se conoce como una acción. Con esta idea se puede poner en práctica lo sugerido por el video y establecer una acción sobre las notas musicales como melodía y acordes para general una representación auditiva de la resolución de un cubo de Rubik.

Para esto podemos comenzar con una configuración del cubo de Rubik como la de la figura. Primero establecemos una forma de codificar las notas musicales con colores

La acción del grupo de permutaciones del cubo sobre las notas musicales está dada por:

• En la cara superior, cada color representa una nota en la melodía en corcheas, comenzando en la esquina verde y en la dirección usual de lectura, izquierda a derecha, arriba a abajo.
• En la cara superior, cada color en las esquinas representa una nota que determina un acorde en la armonía.

Con esto, cada paso para resolver el cubo transforma las caras y por lo tanto define una nueva configuración de melodía y armonía. Así, siguiendo esta configuración inicial se obtienen 58 compases con los 58 pasos para resolver el cubo.  La resolución paso a paso del cubo puede seguirse acá.

El resultado es este:

Es posible variar la acción para añadir más melodía y armonía empleando todas las caras del cubo en vez de centrarse solo en una, pero eso será para otra ocasión.

An infinity between countable and uncountable

In my discrete math class we are talking about functions and cardinalities.

On of the outstanding results of formalizing set theory is the fact that there are different types of infinities,  that is, there is something bigger than infinity, or at least bigger than the usual infinity that we think about. 

One way of dealing with these infinities is by using cardinal numbers.  

These have arithmetic properties, that is, we can add, multiply, and even exponentiate. However, the way of understanding  these operations resort in set theoretical definitions. For example, adding two cardinals amounts to make the union of two disjoint sets, to multiply is to do the cartesian product, and exponentiation is related to finding all the functions from one set into the another. 

Since these operations are well behaved, that is, they satisfy the usual commutativity, associativity, and distributivity properties, we could think of mimicking the construction of rational numbers using cardinals.

Let $\mathcal{N}$ be the set of cardinals smaller than a given cardinal $\mathfrak{w}\geq 1$ and consider the equivalence relation $\sim$ on $\mathcal{N}\times\mathcal{N}$ given by:

$$(\mathfrak{a},\mathfrak{b})\sim(\mathfrak{c},\mathfrak{d}) \text{ iff } \mathfrak{a}\cdot\mathfrak{d}=\mathfrak{b}\cdot\mathfrak{c}\,.$$

We need to only consider the cardinals smaller than a given one since we cannot construct the set of all cardinals. Thus, with this, let $\mathcal{Q}=\mathcal{N}\times\mathcal{N}/\sim$ and define $+,\cdot$ as

$$[(\mathfrak{a},\mathfrak{b})]+[(\mathfrak{c},\mathfrak{d})]=[(\mathfrak{a}\cdot\mathfrak{d}+\mathfrak{b}\cdot\mathfrak{c},\mathfrak{b}\cdot\mathfrak{d})]$$

$$[(\mathfrak{a},\mathfrak{b})]\cdot[(\mathfrak{c},\mathfrak{d})]=[(\mathfrak{a}\cdot\mathfrak{c},\mathfrak{b}\cdot\mathfrak{d})]\,.$$

These are well defined, and $[(1,1)]$ and $[(0,1)]$ serve as the multiplicative and additive identities respectively. Thus $\mathcal{Q}$ is a (commutative) ring. The order provided on the cardinals gets lifted to the quotient:

$$[(\mathfrak{a},\mathfrak{b})]\leq[(\mathfrak{c},\mathfrak{d})]\text{ iff } \mathfrak{a}\cdot\mathfrak{d}\leq\mathfrak{c}\cdot\mathfrak{b}\,.$$

Thus, we can also abstract the construction of the real numbers using Dedekind cuts using these cardinal rationals. 

Consider Dedekind type cuts of $\mathcal{Q}$, that is, a partition $\mathcal{A}\cup\mathcal{B}=\mathcal{Q}$ such that 

$$\forall\mathfrak{a}\in A\text{ and } \forall\mathfrak{b}\in\mathcal{B},\mathfrak{a}<\mathfrak{b}\,.$$

By considering all possible Dedekin type cuts, we can form a new set that behaves like the real numbers, in the sense that it becomes totally ordered and complete.

This suggests that we could do some sort of infinite calculus, with limits and derivatives, which would be nice.

PS: The relation $\sim$ defined above is not an equivalence relation (it fails to be transitive) and hence making the construction not to be a partition of $\mathcal{N}\times\mathcal{N}$, so a good way to make the construction work is by defining a better $\sim$ that makes this posible. If you can find it, maybe we can truly have infinities that behave like the real numbers. 

¿Le creemos a las encuestas? FCN 56%, UNE 29%

Después de haber obtenido una muy buena proyección para la primera vuelta de las elecciones presidenciales en Guatemala, decidí realizar una última proyección para el balotaje del 25 de octubre.

Generalmente las encuestas generan desconfianza y escepticismo. Se piensa que son manipuladas para favorecen alguien en particular y presentar una realidad ficticia. En nuestras sociedades, lastimosamente, eso puede no estar muy alejado de la realidad, sin embargo, desde el punto de vista frío de los números, es posible entender el fenómeno de las encuestas.

"Son encuestas, no profecías." leía por allí en las redes sociales. Una encuesta la podemos pensar como una medición realizada en un momento, y para comprender un poco mejor lo que representan, hay que notar que la intención de voto en la población es un ente dinámico, es decir que cambia con el tiempo.

Si pensamos la intención de voto como la estatura de un niño, las encuestas serían las mediciones que el pediatra realiza a lo largo de la niñez. Las mediciones cambian, y estas individualmente, no pueden predecir la estatura que alcanzará en la edad adulta. Sin embargo,  el pediatra con dichas mediciones puede realizar un modelo (o seguir una curva normal) para predecir la estatura.

De igual manera, las encuestas, vistas aisladamente, no pueden ofrecer una visión clara de los fenómenos, resulta más rico el analizar las tendencias que estas presentan. Para esta segunda vuelta solamente encontré dos encuestas principales de instituciones. Estas fueron realizadas por la firma Felipe Noguera y por ProDatos.

Con estos datos se puede realizar una modelación utilizando cadenas de Markov como se realizó anteriormente.

Dado que la distancia entre ambas encuestas es muy corta, y que la segunda vuelta es muy próxima, es posible proyectar los datos obteniendo una matriz de transición $T$ de tal forma que

$$v_0=\text{ Felipe Noguera}$$

$$v_2=\text{ ProDatos }$$

$$v_3=\text{ Segunda Vuelta}$$

donde el índice cuenta el número de quincenas a partir de la primer encuesta. Entonces se tiene que 

$$T^2v_0=v_2\,,\text{ y } T^3v_0=v_3\,.$$

La matriz de transición $T$ es simétrica positiva y donde la suma de sus columnas (o filas) es 1. Es posible encontrar $T$ utilizando mínimos cuadrados. En este caso el error obtenido fue de $4.16334*10^{-17}$.

Con esto se obtienen los siguientes porcentajes 

El error reportado por las encuestas fue del 3.5% y del 2.8% respectivamente, y utilizando un análisis de propagación de errores, se obtiene un error de proyección del 7.7%.

The last digit of pi is 1

One of the most interesting Chuck Norris facts states that he knows the last digit of pi. The other day I was thinking that maybe I could join team Norris and find it too.

Now, finding what is the last digit in the decimal expansion of a number is actually something that is not well defined. Even thought that we can say that the last digit of $1/2=0.5$ is 5 and we could argue that the last digit of $1/3=0.\bar{3}$ is 3, for example, for $13/99=0.\overline{13}$ the digits are periodic and hence 1 and 3 will keep repeating without reaching a limit. We of course could say that the last digit for this is the last digit appearing on the period, which gives 3 in base 10.

Likewise, if we define the sequence $d_n$ to be the $n$th digit of the decimal expansion of $\pi$, we have that 

$$\lim_{n\to\infty}d_n$$

does not exist. So maybe we can twist the question a little in order to make it more sound. 

A very nice approach is to use continued fraction representation of numbers,

$$x=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\ddots}}}\,.$$

Here the $a_i$ are integers. Usually this is abbreviated as 

$$x=[a_0;a_1,a_2,a_3,\dots]\,.$$

With this notation we get rid of the problem about the base expansion, as it is independent from the base in which the numbers are written. Here the problem about finding the last digit of rational numbers is straight forward, as rationals have a finite continued fraction expansion. For example $13/99=[0; 7, 1, 1, 1, 1, 2]$, that is

$$\frac{13}{99}=0+\cfrac{1}{7+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{2}}}}}}\,.$$

Then we can say that the last number on the expansion of $13/99$ is $2$. This even works for irrational numbers. For example $\sqrt{2}$ has an expansion as continued fraction $\sqrt{2}=[1;\bar{2}]$, that is

$$\sqrt{2}=1+\cfrac{1}{1+\cfrac{1}{2+\cfrac{1}{2+\ddots}}}\,.$$

Hence we can say that the last number of $\sqrt(2)$ is $2$. Still, not all irrationals have nice continued fraction representations. For instance 

$$\frac{1+\sqrt{3}}{2}=[1;\overline{2,1}]\,,$$ 

which throw us back to the original problem of periodic expansions. This time though, we have a nice ace under the sleeve. It is due to Galois and it establishes an outstanding result about quadratic surds.

It states that given a reduced surd $\alpha=[\overline{a_0;a_1,a_2,\dots,a_n}]$, its conjugate $\phi(\alpha)$ has a relation with the number obtained by reversing the order of the continued fraction expansion for $\alpha$.  This relation is given by

$$-\frac{1}{\phi(\alpha)}=[\overline{a_n;a_{n-1},a_{n-2},\dots, a_1,a_0}]\,.$$

The conjugate $\phi$ is pretty much like the more familiar complex conjugate, but in a more general setting. The conjugate of a quadratic surd simply changes the sign of the radical, 

$$\frac{P+\sqrt(D)}{Q}\mapsto\frac{P-\sqrt(D)}{Q}\,.$$

Thus in the case of 

$$\alpha=\frac{1+\sqrt{3}}{2}$$, we have that the inverse negative of its conjugate should have a reversed continued fraction expansion,

$$\frac{2}{\sqrt{3}-1}=[\overline{2,1}]\,.$$

Thus, is we follow the original idea as for periodic rationals, the last number of $(1+\sqrt{3})/2$ is  $2$, which is the first number of $2/(\sqrt{3}-1)$.

In order to understand how to use this in the general case,  the role of the discriminant is important. For example, for complex numbers we have that $D=-1$. This is called the discriminant and it is related to the quadratic equation that the number satisfy. That is, if $\alpha$ is a quadratic surd, it is the zero of a quadratic polynomial

$$p(\alpha)=a\alpha^2+b\alpha+c=0\,,$$

and $D=b^2-4ac$. The beauty of the conjugate function $\phi$ is that it permutes the roots of the polynomial $p(x)$. In the case of the complex numbers, $D=-1$ and the polynomial is 

$$p(x)=x^2+1\,.$$

We have then that the conjugation takes one root of this polynomial into the other $\bar{i}=-i$. In general, this can be done for any polynomial $p(x)$ of higher degrees. When we go to higher degrees, there is more than one involution that permutes the roots of $p$.  This is the area of study of Galois Theory (no wonder why is connected to the original thing!)

Galois reversing result works only for reduced quadratic numbers, but taking this idea, we can extend it for more general situations,

Let $\alpha$ be the zero of a function $f(x)$ and let $\phi$ be a function that

permutes the roots of $f(x)$. If $-1<\phi(\alpha)<0$ then define the last

number for $\alpha$ to be the first number on the continued fraction of 

$$-\frac{1}{\phi(\alpha))}\,.$$

In the case of $\pi$, we have that $f(x)=\sin(4x)$ is a possibility. Now we need an involution on the roots of $f$. Let $\phi$ be such that $\phi(\pi)=-\pi/4$. Then we can say that the last number of $\pi$ is the same as the first number of 

$$\frac{4}{\pi}=[1; 3, 1, 1, 1, 15, 2, 72, 1, 9, 1, 17, 1, 2, ...]$$

which is 1. 

A naive way of thinking about this is that we can regard $\pi$ as a number with an infinite period and thus the scheme could give something meaningful. But of course, this definition is not well defined as there are infinite possible involutions for the set or roots of $f(x)$. These involutions form a group known as the infinite dihedral group, $D_\infty$.

If there is anything like Galois theory for analytic functions maybe we could find the last number in $\pi$. 

Números analíticos y meromorfos

Hace unos días hablábamos con Vinicio sobre la naturaleza de los números reales. Tradicionalmente los reales se dividen en naturales, enteros, racionales e irracionales.

$$\mathbb{N}\subset\mathbb{Z}\subset\mathbb{Q}\,,\qquad\mathbb{Q}\cup\mathbb{I}=\mathbb{R}\,.$$

Históricamente esta clasificación de los números viene dada por las propiedades algebraicas que presentan.  Primero tenemos a los números naturales que surgen de la necesidad del hombre de contar sus bienes. Contar ovejas, alimentos, terreno, etc. Al iniciar las relaciones comerciales se ve la necesidad de "juntar" y "quitar" objetos, así como de representar deudas y créditos. Con esto surgen los números enteros. 

Hasta este punto, los números eran nada más utilizados para contar, ya sea lo que se tiene o lo que se debe, sin embargo con el desarrollo de la geometría, la construcción y la fabricación de objetos, aparece otra necesidad en el ser humano: medir.

Los racionales surgen de considerar mediciones y proporciones entre estas. Hubo que esperar muchos cientos de años hasta que se consideró un conjunto más completo de números. Los reales son obtenidos por medio de considerar la noción de límite. Esto viene de realizar el paso entre lo discreto y lo continuo. 

Algebraicamente se puede describir esto partiendo de $\mathbb{N}$ como el conjunto base dotado de suma. Luego $\mathbb{Z}$ se obtiene al considerar también la resta. Resulta ser que los enteros admiten multiplicación, y para obtener los racionales, se considera la división. Los reales aparecen con el cálculo integral y diferencial. 

Sin embargo, otra forma muy interesante de realizar esta clasificación de los números viene de estudiar sus propiedades por medio de analizar funciones sobre ellos.

Los enteros surgen de considerar ecuaciones del tipo

$$x+n=0\,,$$

donde $n$ es un natural. Esta ecuaciones tendrá soluciones enteras, mas no naturales (excepto $n=0$). Similarmente, al considerar las ecuaciones del tipo 

$$bx-a=0$$

con $a,b$ enteros y $b\neq0$, tenemos que las soluciones son racionales. 

Esta es la idea detrás de los números algebraicos, los cuales son soluciones de polinomios sobre enteros.  

Los algebraicos incluyen a los racionales, sin embargo números irracionales como $\sqrt{2}$ son algebraicos. También hay reales que no so algebraicos, tal es el caso de $e$ y $pi$. Estos se llaman trascendentes.

Una forma de seguir clasificando a los reales por características de este tipo es por medio de considerar soluciones reales a ecuaciones del tipo

$$f(x)=0\,.$$

Para $f$ un polinomio de grado $n$, se dice que $x$ es un algebraico de grado $n$. Es decir, si $f$ es de la forma

$$f(x)=\sum_{k=0}^na_kx^k\,,$$

con $a_k\in\mathbb{Z}$ (o equivalentemente $a_k\in\mathbb{Q}$).

Siguiendo con esta idea, podemos definir los números analíticos  como aquellos que son soluciones de funciones de la siguiente forma

$$\sum_{k=0}^\infty a_kx^k\,$$

para series con un radio de convergencia positivo. Con esto tenemos que $pi$ es analítico, ya que  para $$f(x)=\sin(x)=\sum_{k=0}^\infty \frac{(-1)^{k}}{(2k+1)!}x^{2k+1}$$

 tenemos que $f(\pi)=0$. De igual manera $\ln(2)$ es analítico, pues

$$f(x)=e^x-2=-2+\sum_{k=0}^\infty \frac{1}{k!}x^k$$

anula a $\ln(2)$. Sin embargo, parece ser que $e$ no es analítico, pero $e-1$ si lo es. Lo extraño de esto viene de que acá consideramos convergencia y ya no es posible en general reordenar términos en las series sin afectar la convergencia.

Aunque los analíticos parecieran cubrir una porción mucho más grande de los reales, estos son nada mas contables. Esto se puede ver dado que cada coeficiente $a_k$ es racional, y tenemos un numero contable de estos. Además, las funciones analíticas distintas de cero solo tienen un numero contable de ceros.

Otro tipo de números que pueden definirse siguiendo esta linea son los números meromorfos, los cuales vienen de encontrar los ceros de funciones de la forma

$$f(x)=\sum_{k=-\infty}^\infty a_kx^k\,,$$

con $a_k\in\mathbb{Q}$. Por la misma razón de antes, estos también seran solo un número contable, así que faltan muchos más por clasificar. Quizás esta linea pueda seguirse para poder ir abarcando poco a poco la totalidad de los reales.

The geometry of irrationals

Many years ago I remember reading about irrational numbers and the various surprising things they hide. One nice thing about irrationals is that even thought we think of them as being bad behaved and ugly, we can still classify them further. For example, we have irrationals that are also algebraic, that is, they are zeros of a polynomial with integer coefficients.

We can think that rationals are algebraic of degree 1, while algebraic of degree 2 include $\sqrt{2}, \sqrt{3} $, the golden ratio, etc.

Then we have numbers that are not algebraic, that is, they are not zeros of polynomials with integer coefficients. These are called Transcendental. Some of the famous ones in this category are $\pi, e$, Liouville's constant, etc.

Another way of studying irrational numbers is by measuring how irrational are they. This really means to study how well a number can be approximated with rational numbers, that is, loosely speaking, how fast the denominators of the fractions approximating the number have to grow to stay close to it.

We can think that this has to do with the representation of real numbers with approximations by rationals. In a more philosophical way, this irrationality measure can tell how well we can approximate numbers in the math world, with numbers in the real world.

Liouville was big into approximating irrationals with rationals trying to do it in the most efficient way, that is, controlling the size of the denominators. More recently, Roth made contributions into a deeper understanding of this, leading him to win the Fields Medal in 1958.

Looking at this Facebook post about the integer lattice in $\mathbb{R}^3$, I remember an attempt at defining another way of measuring the irrationality of a number.

First, consider the integer lattice in $\mathbb{R}^2$.  Given a real number $m$, graph the line $y=mx$.  Thus the line will hit the lattice if and only if $m$ is rational, so the idea is to analyze what happens when $m$ is irrational.

For this, consider the following: consider a radius $r>0$ and draw the biggest circular sector of radius $r$ that is symmetric around the line $y=mx$ and that does not contain any point of the lattice.

That is, the sector must not contain any of the blue points from the lattice.  Now, the idea is to measure this area and treat it as a function of the radius $A_m(r)$. I created a GeoGebra demonstration to show the idea of the sector.

Here you can see how the area of the sector changes when the radius changes, and also how the procedure varies when considering different values for $m$.

Effectively what happens is that we are looking for the best approximation of the number $m$ using a fraction $p/q$ with $p^2+q^2\leq r^2$. This way we control the size of both numbers for the approximation of $m$.

Thus we have that

$$A_m(r)=r^2\big|\arctan(m)-\arctan(f_m(r))\big|\,,$$

where $f_m(r)$ is the best approximation to $m$ with a rational inside the circle of radius $r$, that is

$$f_m(r)=\min \big|m-\frac{p}{q}\big|\,,\quad \text{ where }p^2+q^2\leq r^2\,.$$

Now, the trick is to analyze $A_m(r)$ as $r\to\infty$. One might think that this is trivially zero, since any irrational can be written as the limit of a sequence of rationals, but we also have the radius growing up to infinity, hence becoming an indeterminate form.

That is, it might be possible to propose another irrationality measure as

$$\nu(m)=\lim_{r\to\infty} \sup A_m(r)\,.$$

The $\sup$ just ensures the existence of $\nu(m)$, we don't even know if there is a limit!

If $m$ is rational, this is exactly zero, but the question would be what happens for $m$ irrational. I did some numerics to have an idea of this measure for a couple of cases. Of course this is no evidence, as a limit like this cannot be trivially calculated using numerical methods, but at least gives a bit of insight.

For example, for $m=\sqrt{2}$ we have that the graph of $A_{\sqrt{2}}(r)$ seems to oscillate between 0.2 and 1.4. We can see here that the peaks happen when a new rational approximation is found. Naively speaking, $\sqrt{2}$ is not hard to approximate with rationals, and hence we don't have to increase too much in $r$ to find a new approximation.

On the other hand, for $m=\pi$ we have a different behavior. We have a series of good approximations, but then suddenly we cannot find any more good approximations. Even though it looks like $A_\pi(r)$ went to 0 around $r=400$, if we zoom in we can see that it is slowly rising finding a new approximation. 

I believe this is a very interesting topic and I think there is something nice waiting to be discovered here. Even if it leads to the same notion as the Liouville-Roth exponent, this would provide a more geometric interpretation of the behavior of irrational numbers. 

Con matemáticas no hay sorpresas

Para muchos, las recientes elecciones en Guatemala han resultado en una gran sorpresa debido a sus resultados. Sin embargo, con matemáticas no hay sorpresas.

Hace mas de un mes hice varias proyecciones utilizando los resultados de varias encuestas, tanto las principales, como las diversas encuestas encontradas en internet. Los resultados de las proyecciones en base a las principales encuestas publicadas en medios impresos arrojaron que

Comparación entre proyecciones y resultados actuales

en donde se tenía un error de aproximadamente 3%. Al analizar las proyecciones que incluían las encuestas realizadas por internet se encuentra que estas estaban muy sesgadas, aunque igualmente la tendencia de FCN al primer lugar y a una diferencia muy estrecha entre UNE y LIDER seguía observándose (menos de un 3%).

Participación en elecciones pasadas para 1era y 2nda vuelta

Otra de las grandes sorpresas fue la participación ciudadana. Al momento se calcula que ha sido del 71.32%, algo que no se había dado en la historia política de Guatemala. Sin embargo, al analizar la historia de todas las elecciones desde 1985 se puede observar una tendencia interesante.

Los datos en azul representan los porcentajes de participación en primera vuelta (incluyendo la del 2015) y los datos en rojo la participación en segunda vuelta. A partir de 1995 se nota que la tendencia a la participación ha ido en aumento casi constante, por lo que se puede realizar un análisis de valores atípicos para poder encontrar un modelo de regresión lineal que pueda describir los datos. Al realizar esto, se obtiene que los datos están correlacionados en 98.49% para la primera vuelta, y 95.98% en la segunda vuelta.

Comparación entre proyecciones y valores actuales

Con esto, se tenía que la proyección daba una participación del 72.39%, lo cual difiere en 1.07% del valor actualmente registrado. Así mismo, se espera que en segunda vuelta haya una participación de al rededor del 63.4%. 

Al analizar datos de una forma sistemática y formal, no existen sorpresas.