Desigualdades y bolas de colores

Hace unos dias atras, mi profesor de entrenamientos para olimpiadas, Dorval Carias, publico un estatus en Facebook que me hizo sonreir de inmediato y me regreso a mis epocas de entrenos:

$(1+1/x)(1+1/y)(1+1/z) \geq 64 \quad \text{donde } x+y+z=1$

es una expresion bonita con la que se puede jugar un poco si no se tienen herramientas fuertes para demostrarla, y eventualmente es posible obtener una solucion elemental. Usando tecnicas un poco mas sofisticadas, es posible mostrarla utilizando la desigualdad de Jensen (posiblemente la forma mas elegante de mostralo), o bien, sumas simetricas y dominacion de una expresion sobre la otra. Incluso es posible utilizar algun argumento tipo AM-GM (como es usual en desigualdades) o tambien tecnicas como suavizamiento, entre otras. Sin embargo todas estas tecnicas prueban la desigualdad, mas no dan una explicacion del porque tiene esta forma, como diria Erdös, una bonita prueba deberia dar una manera de entender el problema, no solamente dar una demostracion.

A primera vista, el 64 con el cual se compara la expresion es un tanto misterioso, sin embargo luego de analizar por un poco de tiempo la desigualdad se puede observar que $64=4^3$ (algo impresionante la verdad) y es posible in un poco mas alla y notar que $64=(3+1)^3$, lo cual suena un poco mas razonable.

Luego de esta primera aproximacion al problema, es habitual tratar de simplificarlo un poco mas para entender lo que pasa. Resulta ser que el problema equivalente con dos variables es

$(1+1/x)(1+1/y)\geq 9$

con $x+y=1$, el cual no da muchas mas pistas que el problema original en tratar de buscar una razon para la desigualdad.

Si hacer el problema mas facil no funciona ¿porque no hacerlo mas dificil?

La forma general del problema seria

$\prod_{i=1}^n (1+1/x_i)\geq (n+1)^n$

con

$\sum_{i=1}^n x_i=1$

Algunas veces un cambio de notacion simplifica mucho un problema, y si no lo hace, al menos da un poco mas de intuicion sobre como atacarlo. Este puede ser uno de dichos casos. Usemos variables $p_i$ en lugar de $x_i$, entonces al mirar la condicion

$\sum_{i=1}^n p_i=1$

¿que es lo primero que viene a la mente? ¡Probabilidades!

Tal vez alguna interpretacion probabilistica o combinatorica pudiera resultar interesante.

Supongamos que tenemos $n$ cajas con bolas de $n$ colores distintos. Sea $p_i$ la probabilidad de sacar una bola de la caja $i$ luego de vaciar todas las cajas en un contenedor comun.

Teniendo las bolas en las $n$ cajas separadas, enumeremos las bolas en cada caja por separado. Consideremos ademas, una bola extra sin color y averiguemos el numero de formas de elegir $n$ bolas de la siguiente manera:

podemos elegir la $i$-esima bola de la $i$-esima caja o bien, elegir la bola comodín

Un pequeño problema con esta interpretacion es que no tenemos el numero total de bolas, sin embargo la probabilidad $p_i$ puede dar un indicio de esto.

Si la probabilidad de elejir una bola de la caja $i$ es $p_i$, eso significa que aproximadamente 1 de cada $\lfloor 1/p_i \rfloor$ bolas en total son de color $i$. Por lo tanto, para una bola de color $i$ en total existen solo $\lfloor 1/p_i \rfloor$ en total, por lo que podemos suponer que en la caja $i$ hay $\lfloor 1/p_i \rfloor$ bolas. (Notese que al hacer esto, las bolas se vuelven pesadas y no hay una probabilidad uniforme, sin embargo esto no es ningun problema)

Por lo tanto, el numero de formas de elegir las $n$ bolas de la manera descrita anteriormente

$\prod_{i=1}^n (1+\lfloor 1/p_i\rfloor)$

Ahora, definamos una segunda manera de elegir bolas

elegir $n$ bolas de cualquiera de las $n$ cajas o la bola comodín, sin importar la numeración

claramente el numero de formas de hacer esto es

$(n+1)^n$

Por ultimo, al notar que la primera manera de elegir bolas incluye orden y la segunda no, se puede decir que la desigualad se cumple.

Puede ser que esta explicación no sea elegante ni corta ni ingeniosa, sin embargo ayuda a entender un poco mas la naturaleza de la desigualdad, su forma y su relevancia.

Hackers of Nature

Almost two years ago, my friend Antonio Juarez invited me to join him in his adventure of moving from Austin to Pittsburg. It had been so long time since I spent time with him since we were back home, and as usual, the trip was full of wierd things and crazy conversations ranging from philosophy to deeping cookies in various kinds of beverages.

About two weeks ago, I attended a conference about quantazation and I had a really nice talk with one of the participants, and part of it made me remember one of our many interesting conversations with Antonio.

As natural in a quantazation conference, discussion between mathematical and physical points of view arose everywhere, and here is when I remember what I once said to Antonio, that my appreciation of how a physicist views his job can be thought as follows:

Physicsts are like hackers. What he does is grab an already built software that does something (nature), starts playing around with the inputs and then analyzing the outputs. Then with this information, what he does is to make his own programs that emulates the original one, in other words, tries to figure out what was the original code for the original software.

Then the evolution of theories in physics is like upgrading the code, improving bugs, extending the range of the input variable, and sometimes, make it more user friendly. If God built up mathematica, physicists build sage.

No wonder lots of physicists like Linux.

And mathematicians? Probably they are like apple, they don't care about the other programmers, they only do stuff, even if no body is going to use it, but at the end, every body is got an iPhone.

Fractales: geodésicas caóticas

Hace un par de días estuve en una presentación donde tuvieron como atracción principal música hecha con bobinas de tesla.

Básicamente, lo que crea la ilusión de ver un rayo, es la ruptura de la rigidez dieléctrica del aire por medio de altos voltajes generados por la bobina. La música es producto de cambiar la frecuencia de la señal generada y ponerla en el rango audible. Uno de los principios básicos de la electricidad, como en muchas otras partes de la naturaleza, es que la electricidad siempre busca el camino de menor impedancia, en otras palabras, trata de minimizar el trabajo realizado.

Ejemplos de este tipo de minimizaciones son catenarias descritas por cables en suspensión, esferas dibujadas por burbujas, orbitas elípitcas de planetas, etc. Para los que conocen de fractales, no es nuevo también saber que muchos patrones fractales en la naturaleza emergen de problemas de optimización, así por ejemplo las conchas de caracoles son resultado de maximizar espacio minimizando material de una manera creciente en el tiempo. Otras estructuras fractales que aparecen en plantas son resultado de maximizar el aprovechamiento y obtención de recursos minimizando espacio ocupado y energía utilizada.

El espectáculo creado por las bobinas de tesla involucra propagación de ondas electromagnéticas en cierto medio, sin embargo, como es bien sabido, es posible pensar en propagación de ondas electromagnéticas como el otro lado de la moneda de la óptica, es decir, las ondas electromagnéticas se propagan minimizando el camino óptico del medio.

Como resultado, dichas trayectorias constituyen geodésicas sobre el espacio-tiempo dictaminadas principalmente por las ecuaciones de Maxwell, las cuales pueden ser resueltas explicitamente. Sin ir muy lejos, dichas geodésicas son trayectorias diferenciales (generadas por el espacio tangente), sin embargo claramente una bobina de tesla muestra patrones demasiado alejados de ser diferenciales, entonces ¿qué está mal con este razonamiento y porqué se difiere tanto de un resultado y el otro?

Fundamentalmente la diferencia radica en algo que muchas veces pasamos por alto y que, como este caso, puede influir grandemente en cualquier tipo de análisis, y esto es que el aire no es un medio perfecto. Algunas veces cuando el medio es suficientemente homogéneo, es posible ver geodésicas como las esperadas, pero esto no ocurre a menudo.

Sin embargo, en general el aire resulta ser un medio muy heterogéneo, y realizar un análisis explícito de un problema como este resulta muy complicado. Es acá donde entra a jugar el caos. Visto como un sistema dinámico, este resulta ser un sistema altamente caótico, puesto que la rigidez dieléctrica es una propiedad que depende de muchos factores, como humedad, temperatura, composición del medio, etc.

Así como escribí anteriormente sobre como la geometría del medio puede influir en la formación de curvas de nivel, acá no solo la geometría, sino que las propiedades del medio determinan las geodésicas formadas.

Siendo un medio caótico, es natural obtener patrones fractales como curvas que minimicen cierta acción, en este caso, es el camino óptico de la onda electromagnética.

Al pensar un poco en el asunto, no resulta tan difícil de creer que este sea el caso, puesto que, por ejemplo, al considerar soluciones a problemas de conducción de calor y otros modelados por ecuaciones diferenciales elípticas, para pequeños tiempos es muy usual utilizar la aproximación dada por el kernel de calor $K(t,x,y)$, el cual puede interpretarse probabilísticamente como la probabilidad de que en un tiempo $t$, una partícula se desplace desde la posición $x$ hasta la posición $y$, es decir, puede verse tambien como un tipo de movimiento browniano, el cual es un tipo de fractal similar al generado por caminatas aleatorias.

Conocer la forma de las geodésicas de cierto fenómeno da mucha información sobre la geometría del ambiente, y en este caso dice mucho sobre la distribución aleatoria de propiedades eléctricas en el medio ambiente, en otras palabras, la aleatoricidad del aire.

Varieties defined by Boundaries

One of the uprising methods to study the scattering properties of set of points are spectral zeta functions. Applications have been found on distribution of prime numbers, energy states of quantum mechanical systems, eigenvalues of operators and because of this, several connection results and conjectures have been made among these apparently unrelated areas.

In general, it is often useful when study the properties of the distribution of a set of points $S$, to study the behavior of a the zeta function which is associated in some know way with the set of points under analysis. Maybe the most famous example of this fact is the study of the distribution of prime numbers by means of the Riemann Zeta function.

The main connection among this different points of view often is, or at least has being conjectured to be, the starting set of points can be realized as the spectrum of differential operators acting on the $L^2$ space of functions defined in some special kind of space, for example manifolds or graphs.

When talking about differential operators, it is capital to specify boundary conditions in order to have a well defined problem, whenever the notion of boundary makes sense.

Recently, most of the study of zeta functions has been made by defining it in an implicit way, that is, without knowing explicitly the values eigenvalues of such differential operators, and this can be made by applying a result that resembles the spectral theorem in functional analysis

$$\int_\gamma \lambda^{-2s} \frac{d}{d\lambda}\log(f(\lambda)) d\lambda$$

which is basically an application of Cauchy's Residue Theorem.

The role that plays this function $f$ that appears in the residue theorem is of great importance for analyzing properties of the zeta function. This function is a meromorphic function whose zeros are located $S$, and often can be found by imposing the boundary conditions.

Using this interpretation, we can say that the set $S$ is an analytic variety defined by $f$. This analytic variety is the intersection of the varieties defined by imposing one boundary condition at a time, i.e. we have that

$\displaystyle S=\bigcap_{\beta\in B} Z (f_\beta)$

where $B$ is the set of boundaries and $f_\beta$ is a function obtained when imposing the $\beta$ boundary condition, and $Z(g)$ is the zero set for the function $g$.

Each of the boundary conditions can define an analytic variety by means of $f_\beta$, and hence, the intersection of these varieties give the spectrum of the desired differential operator. Because of this reasoning, it is natural to think that the zeta function can be decomposed as the zeta functions of the corresponding boundary conditions that define the problem.

Studying this decomposition would be of great importance for finding the general behavior of a spectral zeta function when changing boundary conditions and see what is the net affect that these play in the overall result.

Irracionalidad de armonías

Hace poco estaba viendo un documental sobre el último teorema de Fermat, grabado cuando recién se había anunciado la prueba de Andrew Wiles. El documental es muy interesante y abarca una muy buena introducción histórica y matemática del teorema, así como de la teoría empleada en su demostración.

En una parte del documental, Robert Osserman hace una muy bonita conección entre la naturaleza de los números y armonías entre sonidos. Muestra un par de triángulos rectángulos, uno pitagórico y otro un triágulo isóceles, tales que cada uno de los lados era una cuerda con la misma tensión.

Al final de la demostración, resulta que el triángulo pitagórico resuena armoniosamente, mientras que el isóceles es uno de los ejemplos de sonidos menos armoniosos que pueden haber.

Me pareció muy interesante la conección existente entre armonía musical y la relación pitagórica de los números, la cual resulta muy coherente luego de analizarla.

No hay mejor manera de analizar sonidos creados por cuerdas que utilizar la ecuación de la cuerda vibrante, la cual es la ecuación de onda con condiciones Dirichlet a la frontera:

$\Delta \phi(x) =\lambda \phi(x)$

donde $\lambda$ es un armónico del sonido producido por la cuerda. Como bien es sabido, la solución general al problema de la cuerda vibrante es una superposición de todos los armónicos posibles, que puede ser escrito como serie de Fourier como

$\phi(x)=\sum_{n=0}^\infty a_n\sin(\sqrt{\lambda_n}x)$

donde $\lambda_n=\frac{n\pi}{L}$ debido a las condiciones de frontera $\phi(0)=\phi(L)=0$, con $L$ el largo de la cuerda.

Por otra parte, desde Pitágoras con el monocordio, es sabido que al dividir una cuerda en partes iguales, se producen sonidos armoniosos, por lo que pudiéramos decir que el grado en que dos sonidos resuenan armoniósamente está relacionado con la relación que guardan sus frecuencias fundamentales. Si una frecuencia divide exactamente a la otra, el sonido es muy armonioso, tal es el caso de las octavas, en donde una frecuencia es el doble de la otra (o una potencia de 2). Luego, el grado de armonía puede medirse por medio de que tan grande sea el minimo común multiplo de ambas frecuencias, el cual puede interpretarse como que tanto hay que esperar para que los dos sonidos lleguen a producir un armónico en común.

Por esta razón, las octavas suenan muy armoniosas mientras que una nota y su sostenido no tanto. En el caso de tener dos cuerdas con logitudes cuya razón es un número racional, es posible obtener sonidos armoniosos, dependiendo del tipo de número obtenido, mientras que si la razón es un número irracional, eso quiere decir que hay que nunca es posible obtener un armónico en común, y por lo tanto el sonido obtenido es lo menos armonioso posible.

Strings of digits and prime numbers

This weekend, I attended a conference about geometry and topology. Last night was the conference banquet and there I was sitting in a table at dinner time with a bunch of mathematicians. After some egg rolls and a wonton soup, and obvious topic made its appearance: prime numbers.

My friend Brian Streit was sitting next to me, and in the middle of the dinner he proposed this interesting and rather old question:

Given any string of digits, can one find a prime number ending in such a string? How about beginning in it?

My immediate reaction was to answer yes to both questions, as I recall seen them before in my early olympic training days.

That also made me remember a conjecture that was given to me few months ago by one of my friends back home, Rafa Martinez, who was claiming the following:

Given any string of digits, there exists a digit such that you can insert it in at a position in the original string such that the resulting number is prime.

This statement is in a sense much stronger than the previous one, and as strong as it seems, it turns out to be false, but thinking about it can make you discover some interesting properties about prime numbers and base representation of numbers.

When Rafa gave me this problem, he was so convinced of its validity and I was so convinced of its falsity, that I started looking for a counterexample. First, I started with a single digit prime number, then I start looking for two digit prime numbers that contained the first one. Then I looked for 3-digit prime numbers that contained the previous one and so on.

The first counterexample that I found by this method was 612113, but thinking of this led me to state the same question but in a different base, say $b$. Of course, the statement will still be false, but now, depending on $b$, the length of the counterexample would be different. For instance, if we are in base 2, a counterexample would be 1 (which is not prime), in base 3 we have for example 212, etc.

Basically, this phenomenon is due to the rate of growth of the prime numbers and how that can be related with the base in which numbers are written in.

Broadly speaking, we can make use of the prime number theorem to establish the rate of growth of prime numbers. It basically says, in simple words, that prime numbers grow in a logarithmic way, notice I'm not talking about the density of the primes, but about the size of a prime itself.

Hence, there is a high probability that if a number $p$ is prime, then "$ep$" is also a prime number, which, in some sense says that the most natural "base" to write prime numbers in is un "base $e$".

Of course $ep$ is not a prime number, as it is irrational, even more, what does "base $e$" mean anyway? The idea is to use this approach to find some appropriate bases for writing prime numbers. An appropriate base would be one such $b$ is close to a power of $e$. The first of these such powers is

$b=20\sim e^3=20.085536923187667740928529654581717896987907838554150144...$

The next one is

$b\sim e^8=2980.9579870417282747435920994528886737559679391328357022089...$

and so on.

Of course, changing base representation wont make the behavior of prime numbers different or anything like that, but maybe using this representations could lead to nice patterns on its representations.

After this little digression, I was then left with the original question of Brian, which I didn't think until today in the morning when I was discussing it about with other participant of the conference.

About the question that if you could find a prime number starting with a given string of digits (not ending in even or 5,0 of course) the simplest solution I could think was using Dirichlet's theorem on arithmetic progressions. Given a string of digits $a$, we look at the sequence

$a+k10^n$

with $k$ running over the positive integers and $n$ been the length of $a$. Hence Dirichlet's theorem asserts that there are in fact, infinitely many primes in this sequence, and hence, infinitely many numbers answering positively the question posed.

For the remaining question, my proof didn't come as quickly as the previous one, and it took me the entire last talk (which sadly I didn't pay attention to) to come up with a proof, aided with my good old friend Wikipedia.

I found this interesting fact about prime gaps due to Hoheisel, that states that

$p_{n+1}-p_n \leq p_n^\theta$ for $\theta$ less than 1

where $p_n$ is the $n$th prime number.

With the help of this, proving the statement is not really hard. Proceeding by contradiction, suppose that $a$ is a given string of digits, and that there is no prime number in between $a10^m$ and $(a+1)10^m$ for all $m$, hence this would imply that the relative gap of prime numbers would be of at least

$\frac{ a 10^m- (a+1) 10^m}{a 10^m}=\frac{1}{a} $

but by Hoheisel's result, as $n\to\infty$

$ \frac{p_{n+1}-p_n}{p_n}\to 0$

which leads to a contradiction.

I particularly find really interesting this connections between prime distributions and base representations, it seems that we don't completely understand yet the interaction of these two, but definitely there is an intimate relation among them.

Ecuaciones cónicas y extensiones algebráicas

Hace un par de meses discutiamos con mi amigo José Carlos sobre ecuaciones diofantinas y de posibles métodos para poder resolverlas completamente sobre los enteros.

Este tipo de ecuaciones han sido sujeto de estudio intenso a través de la historia, siendo uno de los ejemplos más famosos el del último teorema de Fermat, dado un natural $n$, determinar las soluciones enteras de la ecuación

$x^n+y^n=z^n$

Como es bien sabido, gracias a Andrew Wiles, dicha ecuación no posee soluciones enteras a menos que $n=1$ o $n=2$.

Proponiendo una meta menos ambisiosa, consideremos una ecuación diofantina de segundo grado

$ax^2+bxy+cy^2=z$

La idea era caracterizar todos los enteros $z$ que pueden ser escritos de la forma $ax^2+bxy+cy^2$, y en el mejor de los casos, dar la forma de los enteros $x$ y $y$ que cumplen con el trabajo.

Con un poco de ejemplos numericos para ciertos valores de $a,b,c$, José Carlos conjeturó que las soluciones $x,y$ de la ecuación son multiplicativas, es decir, si

$ax_1^2+bx_1y_1+cy_1^2=z_1$

$ax_2^2+bx_2y_2+cy_2^2=z_2$

con $x_1,y_1$ y $x_2,y_2$ primos relativos, entonces existen $x_3,y_3$ tales que

$a(x_3)^2+b(x_3)(y_3)+c(y_3)^2=(z_1z_2)$

con afán de simplificar un poco la notacion, podemos denotar la ecuación como

$p(x,y)=z$

y si reescribimos la propiedad multiplicativa como

$p(x_1,y_1)\cdot p(x_2,y_2)=p(x_3,y_3)=z_1z_2$

Esto da una noción de un cierto tipo de norma en $Z^2$. Esto no es más que una extensión de la idea de los enteros gaussianos, en donde se hacen corresponder a los pares $(x,y)$ con $x+iy$, ahora, en este caso, es necesario trabajar con otra extensión algebraica de segundo orden distinta de $\mathbb{Z}\oplus i\mathbb{Z}$.

En pocas palabras, la idea es hacer corresponderle a cada par de enteros $(x,y)$ un numero $x+\alpha y$, donde $\alpha$ es un numero algebraico sobre $\mathbb{Z}$ de grado 2, y de tal manera que $p(x,y)$ sea una norma en dicha extensión algebráica.

Para esto, consideremos el conjunto $G_\alpha=\mathbb{Z}\oplus\alpha\mathbb{Z}$, con $\alpha$ un número algebráico de segundo orden con polinomio mínimo $p(x)=x^2+ex+f$. La idea es convertir $G_\alpha$ en algo que posea una estructura muy parecida a la de los numeros complejos, digamos, un anillo junto con una operación de conjugación.

En primer lugar, la multiplicación de dos elementos se puede hallar utilizando el hecho que $\alpha^2=-b-a\alpha$, lo cual da

$(x,y)(w,z)=(xw-byz,yw+xz-ayz)$

Ahora, es necesario tener un cirto tipo de $\alpha$-conjugado, es decir, un homomorfismo involutivo en $G_\alpha$. Esta conjugación queda totalmente determinada por su valor en $\alpha$. Si tenemos que $\overline{\alpha}=k+d\alpha$, utilizando la propiedad involutiva y la de ser homomorfismo, llegamos a que la única conjugación no trivial es $k=-e$ y $d=-1$.

Ahora, podemos definir la norma en $G_\alpha$ como

$|(x,y)|^2=(x,y)\overline{(x,y)}$

lo cual, por puede escribirse como

$|(x,y)|^2=x^2-exy+fy^2$

con esto tenemos que es inmediata la observación dada por José Carlos, puesto que si $p(x,y)=x^2-exy+fy^2$, y si $p(x_1,y_1)=z_1$ y $p(x_2,y_2)=z_2$, entonces $p(x_3,y_3)=z_1z_2$, donde $x_3,y_3$ están dados por la multiplicación en $G_\alpha$

$(x_1,y_1)(x_2,y_2)=(x_3,y_3)$

Así, el problema inicial de resolver $p(x,y)=z$ se reduce a encontrar puntos con coordenadas enteras en el círculo de radio $z$ centrado en el origen en $G_\alpha$, donde $\alpha$ es una de las raices de $p(x,1)$.

Es importante observar que cualquier polinomio $ax^2+bxy+cy^2$ sustituirse por un polinomio de la forma $x^2-exy+fy^2$ sin afectar el problema inicial.