Sum of digits

Almost a month ago I participated in the Ibero-American College Olympiad thats was held in Quito  as team leader of the Guatemalan team. It had been almost 4 years now since I last participated in any olympiad-related event and sure enough, I was out of shape.  It is well known that mathematics is like any other activity, it requires constant practice and training, even more to make it in a competing level. 

I had a really good time remembering my Olympic times, but it also reminded my how out of shape I was. I must be that the type of mathematics used to do research is a bit different as the kind of skills that are used in competitions, as their goals are a bit different. None the less, this feeling made me start a personal goal: do at least one olympiad-type problem each day. With that in mind, I start this blog, were I post a problem everyday (first in my twitter and then I post the solution of the problem in the blog). Last week, when looking at one of the problems of the day, I noticed a very interesting pattern in the sum of the digits of the powers of 16.

I found the curious relation that the sum of the digits of $16^n$ is $6n+1$. This was something that I had never noticed before and I found it quite charming. After a bit, I started wondering if this sort of property was satisfied with some other powers, but found nothing like the powers of 16. It intrigued me then what was so special about 16 that made it have this beautiful property. 

Talking about this with my friend Esteban, I decided to seek for an easy proof of this fact that could unravel the mystery behind the 16, as no direct explanation seemed to appear.. What would the equivalent power be in a different base $b$ rather than 10?

Surprisingly enough, the core of this pretty property is hidden in the number 9. If you have a number $m$  which does not end in 1, $m$ and $m+9$ will have the same sum of digits. And what is the relation with 9 and 16? Well, $16^n$ always ends with 6, and when you multiply it by 16 we have that

 $16^{n+1}=16^n\cdot 10+16^n\cdot 6$. 

The first summand will have the same sum as $16^n$. Now the magic happens with the second summand. As it ends with 6, when performing the multiplications as we all learned in elementary school, the first operator that we make is $6\times 6=36=3\times 10+6$, thus the 30 adds up with the tenths of the first summand and voilà, there appears the 9. Then to compute the new number $(16^{n+1})$, we only have to keep performing this algorithm as in elementary school, and we end up having that the new number is going to have the same sum of digits as the one before, except by the digit of the units, which is 6. Therefore by induction we have that the sum is to have the desired form. 

By looking at this, we can easily find other numbers that work, for example the powers of $10^k+6$ will do the job. Here we can notice then that the special duty is made by the number 6, as $6^2=36$ whose sum of digits equals 9 and ends also in 6. So hence, when looking at different bases other than 10, we can find something similar happening. We need to have then a base $b$ and a digit $d$ such that:

• $d^2$ ends in $d$
• the sum of the digits of $d^2$ is equal to $b-1$.

In other words, we need to find pairs $(b,d)$ such that

$d^2=(b-1-d)b+d$

i.e.

$d^2+d(b-1)-b(b-1)=0$

which will have integer solutions iff 

$(b-1)^2+4b(b-1)=5b^2-6b+1=(5b-1)(b-1)$

is a perfect square. This is a diophantine equation of order two, which have integer solutions. For instance another solutions are $(65,40), (442, 273), (3026, 1870)$. One way of analyzing this equation can be by the method I described earlier.

Thus, similar properties are satisfied by $65^k+40$, $442^k+273$ and $3026^k+1870$ in base $65, 442$ and $3026$ respectively and $k>0$. It is a neat property and special also because it happens to be the case that we use a base that satisfy this diophantine equation. 

Reordenando Cifras

Hace unos días me reencontré con unos viejos amigos de matemática que no veía hacía un par de años, y regresando en el tráfico pensaba sobre un pequeño comentario que hicimos con Jóse Carlos al intercambiar números telefónicos.

Unos años atrás, Jóse Carlos poseía algo que todo matemático codicia: un número telefónico que es primo. Sin embargo ahora años después cuenta con otro número. Al darle mi número, le recordé que es primo, y al particionarlo en orden ascendente en pares y tríos, los números resultantes también son primos. Para mencionarme una propiedad interesante de su número, él me dijo que al realizar una permutación de este y ordenarlo a pares se obtenían que los cuatro números obtenidos eran múltiplos dos a dos.

Pensando en propiedades de números que surgían al ser reordenados, una pregunta natural es

¿de cuántas maneras se pueden reordenar las cifras de un número para obtener números distintos?

Para un número en particular, esta pregunta es fácil de calcular, por ejemplo si vemos el número 122 podemos ver que solamente se pueden reordenar sus cifras de 3 formas diferentes

122

212

221

o para el número 524, se tienen 6 formas diferentes

245

254

425

452

524

542

Sin embargo, si llamamos

$\nu(n)=$número de números distintos obtenidos al permutar las cifras de $n$

una expresión general de $\nu(n)$ resulta muy complicada de escribir, si no es que imposible, puesto que la aparición de dígitos en la expansión decimal de $n$ no es algo fácil de controlar.

Por ejemplo se tiene que la función no es monótona y alcanza valores bajos infinitamente, e.g. $\nu(11\dots 1)=1$ para cualquier cantidad de 1´s.

Como es cosa usual con funciones número-teoréticas, un segundo paso después de buscar expresiones exactas, es buscar comportamientos asintóticos.

Una forma de encontrar esta aproximación es por medio de hallar una expresión semi-explícita para $\nu(n)$.

Sea $n_i$ es número de dígitos $i$ que aparecen en la representación decimal de $n$ y $N$ el número de dígitos de $n$. Entonces

$\nu(n)=\binom{N}{n_0}\binom{N-n_0}{n_1}\binom{N-n_0-n_1}{n_2}\dots \binom{N-n_0-n_1-\dots -n_8}{n_9}$

$=\binom{N}{n_0\, n_1\, n_2\, \dots\, n_9}$

donde el término anterior es el coeficiente multinomial del número de dígitos.

Para calcular una expresión asintótica, podemos decir que para valores grandes de $n$ genéricamente se tiene que $n$ posee sus dígitos uniformemente distribuidos, por lo tanto

$N\sim \log n$

y

$n_i\sim \frac{N}{10}=\frac{\log n}{10}$

por lo tanto tenemos que $\nu(n)$ se comporta como

$\nu(n)\sim \binom{\lfloor\log n\rfloor}{\left\lfloor\frac{\log n}{10}\right\rfloor\, \left\lfloor\frac{\log n}{10}\right\rfloor\,\dots \, \left\lfloor\frac{\log n}{10}\right\rfloor}$

$=\frac{\lfloor\log n\rfloor!}{\left[\left\lfloor\frac{\log n}{10}\right\rfloor!\right]^{10}}$

Aca está la gráfica de la asíntota para $n\leq 100000$

y como se puede ver, asíntoticamente la función crece muy rápido, por lo que para valores grandes de $n$, es posible reordenar sus cifras y encontrar números con propiedades interesantes relacionadas con $n$ dada la gran cantidad de opciones disponibles.

Hearing the string, not the shape

Last week I went to a very interesting summer school about algebraic and topological methods in quantum mechanics. It was a very eclectic crowd between mathematicians and physicists and undergrads, grads, postdocs and professors.

There were lectures, talks and something really interesting called short communications. The idea of these was to encourage participants to present some interesting facts that came from the main lectures. In one of these communications, a group presented the famous topic about hearing the shape of a drum, and their presentation made me think about the mathematical formulation of what does it mean to hear a a sound, and moreover why do we hear certain type of sound and not another.

Suppose we are listening to a string sound, like a guitar. The most basic model of this is the wave equation

$\partial_{tt}\psi=\Delta \psi$

subject to the initial conditions $\psi(0,x)=f(x)$ and $\partial_t \psi(0,x)=g(x)$.

Solving this equation models the behavior of the vibrating string. This PDE can be solved using separation of variables and fourier analysis for the initial conditions, and by these means, the associated wave frequency, can be thought as the separation constant, i.e. when supposing a solution of the form $\psi(t,x)=T(t)X(x)$, the above equation takes the form

$\frac{T''(t)}{T(t)}=\frac{X''(x)}{X(x)}$

Since the RHS is a function of $t$ and the LHS is a function of $x$, the only possible case is that they are equal to a constant (the separation constant) $\lambda$. When applying the initial conditions, the equation in $x$ is easier to solve,as it takes the form of an eigenvalue problem

$X''(x)=\lambda X(x)$

with $X(0)=0$. Notice that this equation does not have a time dependence anymore, and the $\lambda$ parameter is what at the end determines the frequency (frequencies) at which the string resonates. Moreover, the initial position $f(x)$ and initial velocity $g(x)$ do not play a role with the solution of this part of the wave equation, and hence, do not affect with the value of the frequencies $\lambda$. This is the main reason why it really doesn't matter how hard or where to pinch a guitar string, it will always sound the same, maybe a little louder or softer, but the same type of sound. An E string will always sound E, no matter where or how you pinch it.

This means that the sound is an intrinsic characteristic of a material, is not really dependent on the force applied to it but to its shape and physical characteristics.

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.