Sunday, November 29, 2015

¿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.


Tuesday, November 3, 2015

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. 

Thursday, October 22, 2015

¿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%.



Thursday, October 8, 2015

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$. 

Sunday, October 4, 2015

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.




Monday, September 21, 2015

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. 






Thursday, September 10, 2015

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. 



Sunday, August 16, 2015

Series de tiempo dan 20% de abstencionismo y 2% de votos blancos/nulos

Siguiendo con el análisis de datos para estas próximas elecciones en Guatemala, es posible dar un estimado de los porcentajes de abstencionismo y de los votos validos que ocurrirán en esta ocasión.

Utilizando un modelo de series de tiempo, es posible modelar los datos de todas las elecciones ocurridas en Guatemala desde 1985 hasta la fecha.  En base a los datos publicados por el Tribunal Supremo Electoral de Guatemala, se puede obtener una proyección del porcentaje de abstencionismo esperado para estas elecciones del 2015.

Siguiendo la metodología desarrollada en este post, se obtiene que el porcentaje esperado de abstencionismo es del $20%$, con una incerteza del $2%$.

Así mismo, es posible estimar el total de votos nulos/en blanco dentro del total de votos válidos. Al realizar esta proyección, se espera que solamente el $2%$ de los votos válidos son en blanco o nulos.

Esto quiere decir, que con un estimado de más de ocho millones $(8200000)$ habitantes empadronados, solamente seis millones y medio $(6560000)$ asistirán a votar, y de estos , ciento treinta mil $(131200)$ serán votos blancos o nulos.


Sunday, August 9, 2015

Elecciones 2015 Guatemala: Modelos de Markov dicen Morales y Baldizón

Estando a menos de un mes de las elecciones presidenciales en Guatemala, quise evaluar los datos existentes sobre las encuestas realizadas. 
Un primer reto fue el encontrar los datos de las encuestas, lastimosamente a pesar de la era tecnológica en la que vivimos, estos datos no están facilmente disponibles. Las referencias de los datos se encuentran al final.

Para poder realizar una proyección de los comicios de este 6 de Septiembre de 2015, es posible tratar los datos de las encuestas como una Cadena de Markov, en donde cada encuesta es un estado en el espacio de distribución de intensión de voto.

Si suponemos que hay $n$ partidos, la idea es utilizar un tipo de Modelo Oculto de Markov con una matriz de transición $T=(t_{ij})$ donde $t_{ij}$ es la probabilidad de que un votante que tenía intención de votar por el partido $i$ cambie de parecer y vote por el partido $j$. Acá, la matriz $T$ es desconocida. El objetivo es encontrar la matriz de transición para poder obtener el estado estable del sistema de Markov.

Para estimar estos datos, se puede definir el espacio de estados como los resultados de las encuestas, en order cronológico. De esta manera se ve la intención de voto como un sistema dinámico.

Con esto, se tiene que 
$$TE_n=E_{n+1}\,,$$
donde $E_n$ es la enésima encuesta considerada. En esta estimación fueron utilizadas 11 encuestas, $E_1,E_2,\dots,E_11$. Con estas encuestas, se obtienen 10 estimadores de la matriz $T$, 

$$T_n=\left(E_{n+1}E^t_{n}\right)\left(E_nE^t_n\right)^{-1}\,.$$

Para poder realizar una estimación de la matriz de transiciones a partir de las matrices $T_n$, es posible analizar la media y desviación de las componentes de las matrices $T_n$, 

$$M=E(T_n)\,,\qquad S^2=E(\left(T_n-T\right)^2)\,,$$

donde las operaciones se hacen componente por componente. Con estos datos, se pueden obtener los intervalos de confianza para los valores de la matriz de transición utilizando el teorema del limite central y la distribución t de student por tener un numero menor de 30 muestras con un $\alpha=5\%$.


En este cuadro están las diferentes proyecciones considerando las encuestas de internet, las impresas, y todas las encuestas, tomadas en orden aleatorio y en orden cronológico.

Con estos datos, se calculan las medias y desviaciones de las proyecciones, para poder calcular el margen de error del modelo. $LI$ y $LS$ denotan los límites inferior y superior respectivamente de las proyecciones realizadas. 

Los datos en verde muestran los candidatos con mayor intensión de voto proyectada, mientras que los datos en amarillo muestran los candidatos con la segunda intensión de voto proyectada. Es de notar que al considerar todos los datos, el porcentaje comprendido en otros resulta ser el segundo lugar. 

En todas las proyecciones, salvo las realizadas con datos de internet solamente, se tiene que hay segunda vuelta entre FCN y LIDER, teniendo FCN un amplio margen sobre el segundo lugar, con un error promedio del $2.77\%$.

Considerando los posibles escenarios, es posible que haya una segunda vuelta entre FCN y UNE o entre FCN y FUERZA, siendo la segunda la más probable, sin embargo FCN y LIDER es la combinación esperada.






[Referencias de datos]



Wednesday, April 15, 2015

Seguridad, criptografía y grupos simétricos

Hoy en mi clase de matemática discreta hablamos sobre criptosistemas, y en especial, sobre el sistema RSA como un ejemplo de un sistema de llave pública.




Un ejemplo de un criptosistema sencillo es cuando en la escuela jugábamos a mandar mensajes o hablar un lenguaje inventado, el cual solo uno y su mejor amigo sabían hablar. Para esto, se tiene una llave que sirve para encriptar el mensaje,  y la misma llave sirve para descifrarlo. Esto puede ser muy sencillo de implementar, sin embargo cuenta con la desventaja de que debe haber una reunión previa para ponerse de acuerdo en la llave, es decir el cifrado. 





En el ámbito de la escuela, esto resulta suficiente, sin embargo para aplicaciones mas elaboradas, como transacciones por internet, resulta poco práctico. Si por ejemplo compro algo por internet, quiero enviar me manera segura mi numero de tarjeta de crédito, es decir, que solo el destinatario pueda leerla. Siguiendo el sistema anterior, para poder enviar mi mensaje, tendría que haberme reunido con el vendedor anteriormente y ponerme de acuerdo con el en una clave, pero si me hubiese reunido con el antes, le hubiera dado mi número de tarjeta en primera instancia y no me encontraría en este dilema.


La idea de los criptosistemas modernos (asimétricos) es prescindir de la necesidad de un acuerdo previo, y hacerlo todo remotamente. Suena como magia negra, y en cierto modo, lo es.


La magia negra utilizada es matemática, y en particular, algebra moderna. La idea es poder crear una forma de cifrar y descifrar mensajes que resulte difícil de hackear.  Ahora bien, el problema comienza con entender qué significa que algo sea difícil de hackear.


Primero, nuestro objetivo es poder mandar mensajes de una forma segura a través de un canal inseguro. Para esto tenemos un conjunto $M$ de mensajes que podemos mandar. Antes de cifrar un mensaje, es necesario codificarlo, lo que significa traducir la información y manejarla como un objeto matemático.


Para codificar un mensaje, tenemos un conjunto $G$ de códigos y una función codificadora
$$g:M\to G\,,$$
$$m\mapsto g(m)\in G\,.$$

Esto simplemente es una traducción y no contiene ningún aspecto de criptografía, al menos no algo relevante.

Luego, tenemos una función encriptadora,
$$E:G\to G\,,$$
la cual sirve para cifrar los mensajes. Nótese que no se tratan de los mensajes en si, sino de la codificación de los mismos.

Por último, se tiene una función desencriptadora,
$$D:G\to G\,,$$

tal que $D\circ E=\text{Id}$, la identidad en $G$. Con esto,  el proceso total para transmitir un mensaje $m$ resulta ser

$$g^{-1}\circ D \circ E\circ g(m)=m\,.$$

La parte relacionada con criptosistemas se enfoca en el medio, en $E$ y $D$, la cual es mas teórica. La parte de codificación tiene que ver mas con aspectos físicos del medio sobre el cual se realiza la transmisión.

Ahora bien, la magia de la criptografía recae en el conjunto $G$ y las funciones definidas sobre $G$. Desde un punto de vista computacional, $E$ y $D$ son algoritmos que poseen cierta complejidad computacional. Que nuestro sistema sea difícil de hackear significa que las funciones sean altamente complejas. Esto, a grandes rasgos, significa que es necesario invertir muchos recursos para poder obtener un resultado. Generalmente el recurso crítico resulta ser el tiempo.

Las funciones $E$ y $D$ son las que se conocen como las llaves del criptosistema, y es necesario entonces poder tener una forma de generar dichas llaves.

Una de las maneras de atacar esto es hacer que el conjunto $G$ tenga la estructura de grupo. Entonces, se pueden ver a las llaves como pertenecientes al conjunto de biyecciones de $G$ en si mismo, es decir, permutaciones.

Para efectos prácticos, $G$ es un grupo finito, digamos con cardinalidad $n$. Entonces se tiene que las posibles llaves son elementos del grupo de permutaciones $S_n$, el cual tiene $n!$ elementos.

Puesto que una llave $A$ es un elementos del grupo $S_n$, sabemos que su inverso $A^{-1}$ es otro elemento de $S_n$, es decir, es otra llave.  Por lo tanto $(A,A^{-1})$ sirven para encriptar y desencriptar mensajes, y vice versa.

La idea con sistemas de llave pública es que se hacen públicos el grupo $G$ y la función $A$ y se mantiene la función $A^{-1}$ en secreto. La magia del asunto es que nada más teniendo $G$ y $A$, calcular $A^{-1}$ resulta ser difícil computacionalmente hablando. Sin embargo, teniendo toda la información, sobre $G$, es fácil generar $A$ y $A^{-1}$.

Generalmente la generación de pares de llaves se realiza en base a parámetros aleatorios. Esto es, la llave $A$ depende de parámetros que uno puede escoger, es decir,  $A(P)$. Conociendo estos parámetros, es fácil generar $A^{-1}(P)$, sin embargo, sin los parámetros $P$, esto resulta difícil.


Al no tener los parámetros $P$, alguien puede encontrar $A^{-1}$ nada mas por prueba y error, tratando de encontrar el inverso de $A$ en $S_n$, multiplicando $A$ con cada elemento hasta encontrar la identidad. Para valores pequeños de $n$ esto resulta no ser tan tedioso, sin embargo ya para $n=60$ tenemos que $S_n$ tiene más elementos que el número de átomos en el universo visible.


Al final, lo crucial es el algoritmo $A(P)$, el cual toma parámetros y devuelve un elemento de $S_n$, es decir

$$A:\mathcal{P}\to S_n\,,$$

donde $\mathcal{P}$ es el espacio de parámetros, el cual suele ser un producto cartesiano del tipo $\mathbb{F}^k$.


Por lo tanto, se puede decir que el cuadro completo es

$$g^{-1}\circ A^{-1}(P)\circ A(P)\circ g(m)\,,$$





Cuando $G=\mathbb{Z}_{pq}$ tenemos el caso de encriptación RSA. Al considerar $G$ como puntos en una curva elíptica, se obtiene la criptografia de curva elíptica, y así con cualquier grupo $G$.

Siguiendo la misma idea, es posible considerar criptografía con matrices, nudos, simetrías, cohomologías y cualquier grupo que se pueda imaginar. Acá hay una lista de grupos no tradicionales con los cuales sería posible realizar criptosistemas. 




Monday, April 13, 2015

4=2 right?

Long time ago I was intrigued by a particular equation that I found in my Real Analysis book. It was not the traditional equation of a complicated polynomial expression equal to a number, rather it involved the idea of having a never ending expression:

$$x^{x^{x^{\dots}}}=2$$

I think the first challenge is to understand what the infinite exponents really mean. Actually, understanding that is the ket to find the solution of the equation.

It is surprising that such a weird looking expression has a very nice solution: $x=\sqrt{2}$.

As I said before, the mystery disappears when we actually understand what the equations really mean. In order to define an infinite exponential, we must use the language of limits.

First, lets define the sequence $a_n$ as follows:

$$a_1=x\,,$$
$$a_n=x^{a_{n-1}}\,.$$

Then, the equation really means to have

$$\lim_{n\to\infty}a_n=2\,.$$

Notice that defining the recurrence equation in the opposite order leads just to $a_n=x^{x^n}$.

Hence, if we know that the limit of the sequence is 2, we should have then

$$2=\lim_{n\to\infty}a_n=\lim_{n\to\infty}x^{a_{n-1}}=x^2\,,$$

which gives the desired solution.

We can notice that there was noting special about 2, thus we are able to reproduce this argument for any initial value, that is, if

$$x^{x^{x^{\dots}}}=r\,,$$

then this will have solution $$x=r^{1/r}$$.


Now, an interesting fact happens when we play a bit with this reasoning and consider the cases $r=2$ and $r=4$. The solution for $r=2$ as discussed above, is $x=\sqrt{2}$, and the solution for $r=4$ is $x=4^{1/4}=\sqrt{2}$... it seems we just proved that $2=4$.

If you pay close attention to this argument, we didn't divide by zero, like most of the mundane "proofs" that $1=0$ that you can find on the internet. We didn't take any wrong step, everything is well defined, everything exists, or does it?


We can pose this question in a slightly different manner, we have the equation

$$g(x)=r\,,$$

and we solved it by finding the inverse of $g$ to be

$$x=f(r)=r^{1/r}\,.$$

Going back to our basics in set theory (or precalculus), we know that a function has an inverse where it is bijective, so $f^{-1}=g$ or $g^{-1}=f$ only when these functions are bijective. Here is the graph of $f(r)$,





when $r$ goes to infinity, the graph keeps decreasing, with horizontal asymptote 1.

I graphed $f(r)$ since it is easier to look at this rather than plotting $g(x)$ (the computer would have hated me), but I remember that in my precalculus years, they told me that the graph of an inverse is really the reflection with respect to the line $y=x$, so we do have the graph of $g(x)$





Therefore we can see that the function $g(x)$ is actually a function up to the tip of the "nose", which is the maximum of $f(r)$. Using the first derivative test on $f(r)$ we have that this happens for $r=e$ and $x=e^{1/e}$. This means that $g(x)=r$ does not have any solutions for $r

Hence out false proof has a more elegant reason for failing: injectivity.





Monday, March 30, 2015

Sumas de potencias con Cauchy

Viendo mi TL en Twitter, me encontré con un resultado de matemática discreta que es un ejemplo clásico:

$$\sum_{i=1}^ni^3=\left(\sum_{i=1}^n i\right)^2\,.$$

Recuerdo la primer vez que vi esto. Me pareció muy interesante el hecho de que las sumas cubos fuera simplemente el cuadrado de la suma de naturales. Este resultado se conoce como el Teorema de Nicómaco.

Para tratar de mostrar esto, se pueden definir las funciones generatrices de las sumas de potencias, con lo que aparecen polinomios de Bernoulli y Polinomios de Faulhaber, sin embargo, otra manera de describir estas sumas de potencias es por medio del análisis complejo.

Podemos analizar la función

$$f_0(z)=\frac{1}{1-z}=\sum_{i=0}^\infty z^i\,,$$

dentro del círculo unidad. Definamos $f_n$ de manera recursiva como

$$f_n(z)=z f_{n-1}'(z)\,.$$

$f_n(z)$ es la función generatriz de las $n$-potencias. Entonces tenemos que si $s_n^k$ es la suma de las primeras $k$ potencias de grado $n$, $s_n^k$ es la suma de los primeros $k$ coeficientes de $f_n(z)$. Estos los podemos recobrar utilizando el teorema del residuo de Cauchy,

$$s_n^k=\frac{1}{2\pi i}\int_\gamma f_n(z)\left(\frac{1}{z}+\frac{1}{z^2}+\dots+\frac{1}{z^{k+1}}\right)\,dz$$
$$=\frac{1}{2\pi i}\int_\gamma f_n(z)\left(\frac{1-\frac{1}{z^{k+1}}}{z-1}\right)\,dz\,.$$

Para evaluar la integral anterior, debemos considerar $\gamma$ como un contorno al rededor de $z=0$ que esté estrictamente contenido dentro del círculo unidad.

Al calcular las funciones $f_n$ se obtienen los Números Eulerianos, los cuales obedecen una ecuación de recurrencia al estilo del triángulo de Pascal. No es difícil de observar que $f_n(z)$ será una función racional cuyo denominador es $(1-z)^{n+1}$.  Por lo tanto, es posible escribir

$$f_n(z)=\frac{g_n(z)}{(z-1)^{n+1}}\,,$$

donde $g_n$ es un polinomio cuyos coeficientes son los números Eulerianos.  Por lo tanto tenemos que las sumas de potencias pueden escribirse como

$$s_n^k=\frac{1}{2\pi i}\int_\gamma \frac{g_n(z)\left(1-\frac{1}{z^{k+1}}\right)}{(z-1)^{k+2}}\,dz\,.$$

Con esta representación, es posible utilizar la fórmula integral de Cauchy para reescribir esta expresión como una derivada,

$$s_n^k=-\frac{1}{(k+1)!}\frac{d^{k+1}}{dz^{k+1}}g_n(z)\left(1-\frac{1}{z^{k+1}}\right)\Big|_{z=1}\,,$$


Donde el signo menos viene de tomar el punto $z=1$ como interior a $\gamma$ al orientar la curva en sentido negativo.

Sustituyendo $n=1$ y $n=3$ se obtiene de forma inmediata el Teorema de Nicómaco.