Funciones generadoras y el infinito potencial

En esta entrada, quiero hacer una conexión entre 3 de mis intereses matemáticas:

• La combinatoria analítica, en la que se usa técnicas del análisis para analizar sucesiones que aparecen en las matemáticas discretas y la combinatoria
• El lenguaje de programación llamado Haskell, que es un lenguaje funcional de evaluación perezosa (acerca del cual estoy aprendiendo en mis clases actuales)
• El índole metafísico de los objetos matemáticos infinitos por lo general

En particular, me enfocaré en las funciones generadoras, que son una técnica poderosa de la combinatoria analítica. Solo voy a rascar la superficie de ese campo profundo, y al fin haré una sugerencia de lecturas si te ha interesado y quieres leer más.

La función generadora de la sucesión Fibonacci

En las matemáticas manejamos las sucesiones infinitas con mucha frecuencia. A mi parecer, una función generadora es, más o menos, una manera alternativa de representar los datos de una sucesión infinita. Si queremos considerar la sucesión de Fibonacci, en vez de escribirlo así: $$(F_n)=(1,1,2,3,5,8,13,\cdots)$$ lo escribimos así, con los elementos de la sucesión colgados sobre los términos de una serie de potencias: $$f(x)=1+x+2x^2+3x^3+5x^4+8x^5+13x^6+\cdots=\sum_{n=0}^\infty F_n x^n$$

Esa forma de representarla lleva consigo ventajas inesperadas. Por ejemplo, en el caso de los números Fibonacci, la función generadora otorga una manera alternativa para deducir la fórmula explícita para el término general de la sucesión de Fibonacci. Acuérdate de que los números Fibonacci satisfacen la siguiente relación de recurrencia: $$F_{n+1}=F_n+F_{n-1}$$ y ésta implica una cierta propiedad algebraica de su función generadora:

$$\begin{align*} f(x) &= \sum_{n=0}^\infty F_n x^n \\ &= 1+x+\sum_{n=2}^\infty (F_{n-1}+F_{n-2})x^n \\ &= 1+x\sum_{n=0}^\infty F_n x^n + x^2\sum_{n=0}^\infty F_nx^n \\ &= 1+(x+x^2)\sum_{n=0}^\infty F_n x^n \\ &= 1+(x+x^2)f(x) \end{align*}$$

y como consecuencia de la igualdad $f(x)=1+(x+x^2)f(x)$,

$$f(x)=\frac{1}{1-x-x^2}$$

Ya se han desaparecido los números Fibonacci de la vista y en su lugar tenemos una función que encierra todos sus datos. Es decir, si expandimos la función $f(x)$ en su serie de Taylor, recobraremos la sucesión. Pero sucede que hay ventajas de estudiar esa función en sí, y nuestra investigación revelará propiedades no obvias de la secuencia $(F_n)$. Por ejemplo, si factorizamos el polinomio cuadrático $1-x-x^2$ para descomponer la función $f(x)$ usando el método de fracciones parciales, obtenemos la igualdad

$$f(x)=\frac{1/\sqrt{5}}{\phi^{-1}-x}+\frac{1/\sqrt{5}}{\phi+x}=\frac{\phi/\sqrt{5}}{1-\phi x}+\frac{\phi^{-1}/\sqrt{5}}{1+\phi^{-1} x}$$

en la que $\phi=\tfrac{1+\sqrt{5}}{2}$ es el número áureo. Ahora reconocemos que podemos expandir las funciones $\tfrac{1}{1-\phi x}$ y $\tfrac{1}{1-\phi^{-1} x}$ como series geométricas:

$$\frac{\phi/\sqrt{5}}{1-\phi x}=\sum_{n=0}^\infty \frac{\phi^{n+1}}{\sqrt{5}}x^n$$

$$\frac{\phi^{-1}/\sqrt{5}}{1-\phi^{-1} x}=\sum_{n=0}^\infty \frac{1}{\phi^{n+1}\sqrt{5}}x^n$$

y entonces

$$f(x)=\sum_{n=0}^\infty F_n x^n = \sum_{n=0}^\infty \Big(\frac{\phi^{n+1}}{\sqrt{5}}+\frac{1}{\phi^{n+1}\sqrt{5}}\Big)x^n$$

Por fin, si comparamos los coeficientes de esas series de potencias, obtenemos la fórmula

$$F_n = \frac{\phi^{n+1}}{\sqrt{5}}+\frac{1}{\phi^{n+1}\sqrt{5}}$$

la cual no es obvia para nada desde la definición recurrente de la sucesión de Fibonacci! Todo eso para demostrar que la representación de una sucesión como una serie de potencias no es simplemente una manera retorcida de organizar sus elementos, sino que nos puede proporcionar vislumbres únicas sobre el índole de la sucesión.

La función generadora de los números Catalan

Consideramos brevemente otra sucesión infinita y su función generadora. Esa sucesión se llama la sucesión de Catalan y se lo define combinatoriamente, de hecho hay muchas maneras distintas de definirlo porque aparece por casualidad en las soluciones de varios problemas combinatorios distintos. Yo lo defino así: el número Catalan $C_n$ representa el número de maneras distintas de poner paréntesis sobre una sucesión finita de $n$ variables, es decir, el número de maneras de asociarlos bajo una operación $\ast$ no asociativa. Por ejemplo, hay $2$ maneras de poner paréntesis sobre $3$ variables:

$$\begin{align*}& a\ast (b\ast c) \\ & (a\ast b)\ast c\end{align*}$$

y sobre $4$ variables hay $5$ maneras:

$$\begin{align*}& a\ast (b\ast (c\ast d)) \\ & a\ast ((b\ast c)\ast d) \\ & (a\ast b)\ast (c\ast d) \\ & (a\ast (b\ast c))\ast d \\ & ((a\ast b)\ast c)\ast d\end{align*}$$

y entonces tenemos los valores $C_3=2$ y $C_4=5$. La sucesión continua:

$$(1,1,2,5,14,42,132,429,\cdots)$$

No es muy difícil encontrar una relación de recurrencia para la sucesión de Catalan, pero es mucho más difícil sacar una fórmula explícita de ella. Si queremos enumerar las maneras de asociar $n$ variables, podemos reconocer que hay $n-1$ maneras distintas de poner el primer par de paréntesis: pueden envolver sólo el primer variable, o los dos primeros variables, o los tres primeros, y etcétera, hasta los $n-1$ primeros variables. (Realmente no pueden envolver los $n$ primeros variables, porque ya siempre quedan "asociados" todos los $n$ variables, es decir que tal paréntesis no tendría significancia porque no les separaría de nada.) Si el primer par de paréntesis reparte los variables en un grupo de $1$ y un grupo de $n-1$, entonces hay $C_1$ maneras de poner paréntesis en el primer grupo, y $C_{n-1}$ maneras de ponerlos en el segundo; si los reparte en un grupo de $2$ y un grupo de $n-2$, hay $C_2$ maneras de poner paréntesis en el primero grupo y $C_{n-2}$ maneras de ponerlos en el segundo; y etcétera. Esa observación sugiere la identidad

$$C_n = C_1 C_{n-1}+C_2 C_{n-2} + \cdots C_{n-1}C_1 = \sum_{k=1}^{n-1}C_k C_{n-k}$$

Ahora podemos aprovechar esta identidad de las funciones generadoras:

$$\bigg(\sum_{n=0}^\infty a_n x^n\bigg) \bigg(\sum_{n=0}^\infty b_n x^n\bigg)=\sum_{n=0}^\infty \Big(\sum_{k=0}^n a_k b_{n-k}\Big)x^n$$

que se puede demostrar a través de la distribución repetida. (Aviso: esa identidad vale para series de potencias formales, pero si quieres considerarlo como una serie de números reales o complejas, hay que prestar atención a su convergencia.) Si ponemos $C_0=0$ y definimos la función generadora de los números Catalan $$g(x)=\sum_{n=0}^\infty C_n x^n$$ obtenemos la identidad siguiente: $$g(x)=x+g(x)^2$$ tomando en cuenta que nuestra recurrencia para $C_n$ no tiene sentido para el valor $n=1$, y de allí sale el término $x$ de sobra en esta ecuación. Si aislamos $g(x)$ en esta igualdad, obtenemos la fórmula $$g(x) = \frac{1+\sqrt{1-4x}}{2}$$

Las propiedades de ésta como una función analítica $g:\mathbb C\to\mathbb C$ nos da información nueva de inmediato sobre los propiedades de la sucesión $C_n$. Por ejemplo, la función $g(x)$ es analítico en un círculo abierto de radio $r=1/4$ con el punto central $x=0$. Eso significa que la serie de potencias $g$ converge cuando $|x|<1/4$ y diverge cuando $|x|>1/4$, y debido al criterio de la raíz podemos deducir que $\sqrt[n]{C_n}$ se acerca a $4$ mientras que $n\to\infty$, o $C_n\approx 4^n$ (multiplicado por algunos otros factores menos significantes), hecho que sería difícil averiguar de la definición o de la recurrencia. La función generadora de $(C_n)$ también nos deja deducir una fórmula explícita para ellos, pero eso dejo como un ejercicio para el lector fanático.

Series de potencias en Haskell

Sucede que el lenguaje de programación llamado "Haskell" tiene una función que nos deja implementar la aritmética de los series de potencias: la "evaluación perezosa". En particular, Haskell puede manejar listas infinitas. Por ejemplo, la expresión [1..] representa una lista infinita de todos los números naturales, y si pides que Haskell te lo muestra, seguirá imprimiendo números naturales hasta que pides que pare. Otro ejemplo más sencillo: la expresión repeat 0 representa una lista que contiene una sucesión infinita de 0s.

Pues, claro que Haskell realmente no puede crear una lista infinita verdadera, puesto que una computadora es un aparato finito. Pero Haskell usa "evaluación perezosa", es decir que no calcula el valor de una expresión antes de que lo necesite para cumplir la pedida del usuario. Por ejemplo, aún cuando creas una lista finita como [1..100], Haskell no almacena los valores entre $1$ y $100$ en la memoria, pero si pides que imprima los números de la lista o que los use para cualquier otra computación, los calculará cuando surge la necesidad. Por eso se lo llama "perezoso" - sólo hace lo que necesita hacer. Y de esa manera puede hacer manipulaciones con listas infinitas también, pues el usuario nunca usará más que un número finito de términos a la vez. Por eso, el término "lista infinita" es un nombre un poco inapropiado - en la realidad es más bien como un generador que produce un valor más cuando se lo solicita.

Si interpretamos una lista infinita de Haskell como una sucesion de coeficientes de un serie de potencias, podemos escribir funciones recursivas para cumplir computaciones algebraicas con ellas. Por ejemplo, si representamos una serie de potencias $$f(x)=\sum_{n=0}^\infty a_n x^n$$ como una lista infinita [a_0,a_1,a_2,...], la operación head de Haskell, que devuelve el término primero de una lista, nos deja extraer el coeficiente $a_0$ de la serie: $$\mathtt{head}(f)=a_0$$ mientras que la operación tail, que elimina el primer elemento de una lista, nos deja truncar la serie: $$\mathtt{tail}(f) = \sum_{n=0}^\infty a_{n+1}x^n = \frac{f(x)-a_0}{x}$$ y por fin, la operación :, que agrega un término a principios de una lista, interactua así con la serie de potencias: $$\mathtt{1 : } ~ f = 1+\sum_{n=0}^\infty a_n x^{n+1}=1+xf(x)$$

A través de esas operaciones podemos escribir funciones propias para cumplir manipulaciones deseadas con series de potencias. Por ejemplo, lo más básico es multiplicar una serie por un número escalar: $$\alpha\cdot \sum_{n=0}^\infty a_n x^n = \sum_{n=0}^\infty (\alpha a_n) x^n$$ En Haskell podemos escribir una función que multiplica los términos de una serie de potencias (o sea, los elementos de una lista) por un escalar:

scaleGF :: Int -> [Int] -> [Int] 
scaleGF c gf = (c * (head gf)) : (scaleGF c (tail gf))

Esa es una función recursiva: multiplica la cabeza de la lista por el escalar, y luego se llama a sí mismo para multiplicar el resto de los términos por el mismo escalar. En vez de multiplicar el escalar por todos los términos a la vez, nuestra función lo hace un término a la vez, así:

$$\alpha\cdot \sum_{n=0}^\infty a_n x^n = \alpha a_0 + \alpha\cdot x\sum_{n=0}^\infty a_{n+1} x^n$$

Parece una llamada recursiva que nunca se terminará, pero Haskell determina el número necesario de iteraciones para cada llamada. Podemos probar nuestra función así:

take 10 (scaleGF 3 [1..])
-> [3,6,9,12,15,18,21,24,27,30]

Además podemos escribir una función que suma dos series de potencias. Acuérdate de que $$\sum_{n=0}^\infty (a_n+b_n)x^n = \sum_{n=0}^\infty a_n x^n + \sum_{n=0}^\infty b_n x^n$$ pero tendremos que formular esta ley de otra manera, porque Haskell no puede acceder a todos los términos de una serie infinita a la vez. La formulación siguiente nos resultará más ventajosa: $$\sum_{n=0}^\infty (a_n+b_n)x^n = (a_0+b_0) + x\sum_{n=0}^\infty (a_{n+1}+b_{n+1}) x^n$$ que sugiere que, para empezar, sólo tenemos que formar la suma de los primeros términos de cada serie, y retrasar el resto del trabajo hasta que se lo necesite. Así escribimos la función:

addGF :: [Int] -> [Int] -> [Int]
addGF gf1 gf2 = ((head gf1) + (head gf2)) :
                (addGF (tail gf1) (tail gf2))   

y aquí está otra prueba:

take 10 (addGF [1..] (repeat 1))
-> [2,3,4,5,6,7,8,9,10,11]

Ya estamos dispuestos a definir, por ejemplo, la serie de potencias de los números Fibonacci. Si nos acordamos de la identidad $$f(x)=1+(x+x^2)f(x)$$ esa basta para calcular los $(F_n)$ en Haskell usando la definición recursiva siguiente:

fiboList :: [Int]
fiboList = 1 : (addGF fiboList (0 : fiboList)) 

que devuelve

take 10 fiboList
-> [1,1,2,3,5,8,13,21,34,55] 

¡Increíble! También podemos definir los números Catalan recursivamente, pero primero tenemos que escribir una función para calcular el producto de dos series de potencias. La identidad siguiente sugiera una manera de implementarlo recursivamente en Haskell:

$$\bigg(\sum_{n=0}^\infty a_n x^n\bigg)\bigg(\sum_{n=0}^\infty b_n x^n\bigg) = a_0 b_0 + a_0\cdot \sum_{n=0}^\infty b_{n+1} x^n + x\bigg(\sum_{n=0}^\infty b_n x^n\bigg) \bigg(\sum_{n=0}^\infty a_{n+1} x^n\bigg)$$

así que, usando nuestras funciones addGF y scaleGF, podemos implementarlo así:

mulGF :: [Int] -> [Int] -> [Int]
mulGF gf1 gf2 = ((head gf1) * (head gf2)) :
                 (addGF (scaleGF (head gf1) (tail gf2))
                        (mulGF gf2 (tail gf1)))

Y ahora para calcular la sucesión de Catalan, podemos usar la identidad algebraica de su función generadora:

$$g(x)=1+xg(x)^2$$

que se puede traducir a Haskell así:

catalanList :: [Int]
catalanList = 1 : (mulGF catalanList catalanList) 

y aquí está una prueba:

take 10 catalanList
-> [1,1,2,5,14,42,132,429,1430,4862] 

Seguro que hay muchas diversiones más que perseguir con las funciones generadoras en Haskell, pero lo dejo aquí. Tú puedes seguir jugueteando con código propio, o tal vez yo seguiré en una entrada próxima. Pero para concluir, tengo un rompecabezas para ti: ¿puedes escribir una función en Haskell que calcula la composición de dos series de potencias $f(x)$ y $g(x)$, es decir, la serie de potencias $f(g(x))$? (Ese problema no es tan sencillo como parece...)

El infinito potencial

Ahora ponte a pensar en el índole de las sucesiones infinitas en las matemáticas, cómo la de Fibonacci:

$$(1,1,2,3,5,7,13,\cdots)$$

Pregúntate: ¿es éste un objeto infinito, o finito? Yo sé que esta pregunta realmente no tiene mucho sentido, puesto que el sentido de "infinito" queda ambiguo, pero no lo propongo como una pregunta matemática sino como una pregunta intuitiva o filosófica. Por un lado, parece obvio que sí, que es infinito, puesto que contiene un número infinito de elementos; que, dado todo el papel en el mundo, no se puede escribir toda la sucesión nunca. Se puede empezar con esta tarea, pero no se puede acabarlo.

Por otro lado, seguramente hay maneras de describir la sucesión de Fibonacci finitamente. El sencillo hecho de que podemos definirlo aunque nuestro idioma matemático tiene un abecedario finito indica eso. Además podemos manifestar la sucesión infinita de Fibonacci en Haskell usando muy pocas líneas de código:

   
fiboList :: [Int]
fiboList = 1 : (addGF fiboList (0 : fiboList)) 

Pues, la habilidad de Haskell de representar "listas infinitas" se puede interpretar como un abuso de terminología y un truco. Pero si llamas fiboList, tú no podrás distinguir entre lo que devuelve Haskell y la "verdadera" sucesión de Fibonacci, puesto que tú eres un ser finito y sólo puedes chequear un número finito de términos a la vez. ¿Es éste realmente tan distinta de la sucesión "infinita" que manipulas en las matemáticas puras?

No debe ser una sorpresa que esa dicotomía se remonta a los tiempos de Platón y Aristóteles. La perspectiva platónica sería que la sucesión de Fibonacci existe en su totalidad infinita en algún universo matemático, y que nosotros, por causa de nuestra imperfección y nuestro índole físico, sólo podemos accederlo un elemento a la vez. Por otro lado, Aristóteles diría que aunque el proceso de generar los números Fibonacci no tiene fin, es decir que después de cada término se puede calcular uno más, la sucesión de Fibonacci no existe en una forma completada. Por lo general, Aristóteles no creía en el infinito actual, o el infinito completado, pero sí creía en el infinito potencial, que se caracteriza por un proceso que no termina.

Tengo que confesar que aunque me encantan las identidades algebraicas de las funciones generadoras, el propósito verdadero de esta entrada era explorar esas dos paradigmas, de los infinitos actuales y potenciales. Me parece que se suele pensar en algunos campos de las matemáticas en términos del infinito actual, por ejemplo la teoría de los conjuntos y el análisis, mientras que otros se pueden conformar con el infinito potencial, tal vez la lógica o la informática matemática. Las funciones generadoras quedan misteriosamente en la frontera entre esas dos paradigmas. Por un lado, una función $\mathbb R\to\mathbb R$ o $\mathbb C\to\mathbb C$ es una cosa continua e infinita, y estudiarla así revela a veces novedades sobre la sucesión discreta que representa. Por otro lado, tal función se define como una composición finita de otras operaciones y funciones, y el acto de calcular sus derivadas para recobrar los elementos de la sucesión es un proceso algorítmico que sólo requiere un número finito de manipulaciones algebraicos.

No propongo una respuesta fija a este dilema, pero sólo quiero presentar explícitamente las dos maneras de percibir una sucesión infinita: como un infinito completado platónico que existe en su totalidad, o como un algoritmo finito para generar números arbitrarios de términos. Ya te dejo con algunas sugerencias:

• Si te ha interesado más lo algebraico de esta entrada, echa un vistazo al libro Analytic Combinatorics por Flajolet y Sedgewick. Es una verdadera enciclopedia de problemas combinatorias y trucos algebraicos/analíticos para atacarlos.
• Si te interesaría una exploración más profunda y rigurosa del índole de los objetos "infinitos" de las matemáticas y las dificultades de tratarlos con un lenguaje finito, tal vez te gustaría el libro Model Theory por Chang y Kiesler. Es un libro difícil (yo pasaba casi toda la vacación de navidad pasada estudiándolo y apenas terminé con el primer capítulo) pero muy saturado de significancia filosófica.
• Si ya conoces los problemas que aparecen en la teoría de conjuntos por causa de lo infinito, tal vez te interesaría un fundamento alternativo de las matemáticas que adopta una perspectiva más computacional y menos platónica. Por eso te recomendaría el libro Homotopy Type Theory, aunque yo todavía no lo entiendo bien yo mismo...