Algebra, Geometry and Topology of the Riordan Group Luis Felipe Prieto Martínez Universidad Autónoma de Madrid Madrid, Abril 2015 Dirigida por Manuel Alonso Morón y Ana María Luzón Cordero Tutor: José Pedro Moreno Díaz a mi abuelo, a Jimena y a toda mi familia Agradecimientos/Acknowledgements Este trabajo es el final de un camino muy largo. Y dicen que para crear algo (aunque sea algo muy pequeño) hay que sufrir, o por lo menos sudar. Así que al terminar esta etapa tengo que dar las gracias a mucha gente que me ha ido acompañando todo este tiempo. Con lo que acabo de decir no quiero que parezca que ha sido una experiencia desagradable para mí. Yo siempre he disfrutado de las Matemáticas, para mí tienen algo especial, y cuando elegí hacer esto fue porque quería sentir qué era investigar, hacer algo nuevo. Y lo volvería a hacer. Una compañera del Departamento de Matemáticas de la UAM (no diremos nombres) siem- pre bromeaba con que ella se matriculó en el doctorado para escribir los agradecimientos de la tesis. Bueno, yo lo que tengo claro es que sin la gente que aparece en estos agradecimientos, desde luego no habría sido capaz de completar este trabajo. ¡Muchas gracias a todos! En lo no académico... Si el camino ha sido duro en media, los últimos meses han sido de auténtica locura. Y si todavía no estoy loco (del todo) ha sido gracias a tres personas principalmente: mi hermano, que siempre intenta contagiarme su buen humor cuando el mío es malo; Jimena, que me ha aguantado todos los años que ha durado esto, me ha escuchado y me ha apoyado de muchas maneras y Fran que ha estado todo el rato a mi lado como un auténtico amigo. Mi familia me ha arropado mucho mientras hacía este trabajo. Me han aguantado cuando estaba de mal humor, me han ayudado en todo lo que han podido y me han sostenido sin quejarse ni una vez porque dedicara tantos años a una tarea lamentablemente ingrata en lo económico. Les debo mucho. Y gracias también a mi abuelo José Luis, que era el que más ilusión tenía en que acabara este trabajo. Tengo que dar las gracias a mis amigos no doctorandos, por aguantarme: Pedri, Carmen, Isaac, Cesar, Lanzas, Isma... El Departamento de Matemáticas ha sido un sitio estupendo para pasar estos años. Todo empezóconlosSiempreDensos,dondetuvemiprimercontactoconalgunosdemiscompañeros (María Medina y José Conde). Y después he pasado todos estos años en lo que ha sido mi casa (por otros referida como destierro): el despacho 103, en el que yo he pasado muy, muy buenos momentos. Desde mis primeros compañeros (María Medina, Juan, David, Carlos), pasando por muchos otros que por allí recalaron después, hasta llegar a los actuales ocupantes. Tengo que agradecérselo especialmente a estos últimos. Alessandro, eres un tío genial y siempre estás contento, da gusto trabajar contigo. Bea, te digo lo mismo y te aprecio y admiro un montón (matemáticamente y en lo demás). Daniel, eres una persona realmente interesante, he i ii aprendido mucho de ti (no sólo matemáticas) y me alegra que hayamos coincidido. Raquel, eres la persona con la que más he cotilleado en toda la Universidad y tu tesis es la más bonita de todas. Además me has ayudado mil millones de veces a hacer trámites cuando tenía que hacerlos a distancia. Vales un montón, te deseo muchísima suerte. Julio, pese a ser incorporación tardía, eres un tío genial, me alegra que se cumpla un principio de conservación de topólogos en el 103, lástima que no hayamos coincidido más tiempo. Muchas gracias a los cinco. Por resumir lo a cómodo que me habéis hecho sentir este tiempo diré que, pudiendo trabajar desde casa, he cruzado muchas veces la comunidad de Madrid entera (¡dos veces!) para ir al despacho y lo he hecho con mucho gusto. Ha sido un auténtico placer trabajar con vosotros. Haymuchamásgenteentrelosdoctorandosydoctoresjóvenesalosquetengoqueagradecer que me haya hecho estos años muy agradables. No quiero hacer una lista, para no olvidar a nadie, peroporlomenostengoquedarleslasgracias(apartedealosanteriores)aBeaPascual, Marcos, Irina (y sus operadores de composición ponderada), Javi, Marta (las dos), Mari Luz, Iason, Jesús, Álvaro... Porúltimo,sedalacircunstanciadequeelúltimoañodeestatesissehadesarrolladomien- tras trabajaba en un sitio no universitario pero en el que también había muchos matemáticos (entre otras personas) que saben mucho y de los que he aprendido también mucho: el IES Domenico Scarlatti. Muchas gracias a mis compañeros de allí, porque me han facilitado tanto mi vida laboral que ha sido posible terminar esta tesis en plazo, además de haber conseguido que me sintiera super cómodo. Gracias a mi jefe Chema (que es el jefe y matemático-profesor perfecto), a Toñi (que me ayudo un montón con el LATEX), Sara (que me ha sobreprotegido con su capa de superheroína en mi primer año en las aulas), Olga y Francisco (que habéis sido encantadores con una persona a la que acabábais de conocer y eso se es muy de agradecer)... Y, por supuesto, a Magdalena, porque (lo consiga o no) es una de esas personas que intenta porque sí que las personas que están a su alrededor sean más felices (y por mucha más cosas que no caben aquí) y a la que deseo la mejor de las suertes. En lo académico... En primer lugar tengo que agradecerle fuertemente a mis dos directores su paciencia. Ana, Manuel, muchas gracias por las Matemáticas que me habéis enseñado y por la paciencia que habéis tenido con lo mal que escribo. Gracias también porque os habéis preocupado por mí más allá de las Matemáticas en muchas ocasiones. Y gracias también al proyecto en el que participamos MINECO MTM2012-30719 que me ha permitido ir de congresos. Muchísimas, muchísimas gracias al lector, por su disponibilidad y eficacia. A la UAM tengo que agradecerle una financiación parcial (becas de máster y doctorado y contrato de Gestor) de estos años de tesis, que sin duda es lo que me ha permitido acometerla. También tengo mucho que agradecer a algunos profesores en concreto. Adolfo, muchas gracias por todo (donde todo son muchas cosas, como por ejemplo mi TFM del máster de profesorado) pero sobre todo gracias por tu consejo constante en todos los años que llevo aquí. Lo mismo (hablando de consejos) para José Pedro Moreno, mi tutor, gran jugador de baloncesto (bueno, ¡Adolfo también lo es!) y el que me puso en contacto con mis directores entre otras muchas cosas. Yolanda, muchas gracias por las Matemáticas tan bonitas que has intentado enseñarme, iii y que fueron mi primer contacto contacto con la investigación. A mis tres jefes de la Gestión de Posgrado: Antonio Cuevas, Fernando Soria y Dragan Vukotic, por su paciencia. A los dos primeros(comoalumno)lestengoqueagradecerademásmuchosueficaciacomocoordinadores, quemehafacilitadomuchísimolascosas. Dagustoencontrarseprofesionalesasí,queteayudan. Y por último a los profesores que daban la teoría de mi docencia, por acompañarme en mis primeros pasitos como profesor: Magdalena Walias, Ramón Flores y Yolanda Fuertes (otra vez) Finally I want to thank Anders Björner, as my advisor of my 3 months in KTH, and also to the whole Department of Mathematics. It was a really nice place to be, full of wonderful people. Contents Agradecimientos/Acknowledgements i Introducción/Introduction ix 0 Basics 1 0.1 Inverse Limits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 0.2 Formal Power Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 0.2.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 0.2.2 The group F (K) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 0 0.2.3 The group F . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1 0.2.4 Power Series in one variable over Rings . . . . . . . . . . . . . . . . . . 8 0.3 The Riordan Group (Infinite Representation) . . . . . . . . . . . . . . . . . . . 9 0.3.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 0.3.2 The natural action of a infinite Riordan matrix on K[[x]]. The Riordan group R(K) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 0.3.3 A-sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 0.3.4 Alternative notation for Riordan matrices. The g-sequence. . . . . . . . 15 0.3.5 The subgroups T(K);A(K) . . . . . . . . . . . . . . . . . . . . . . . . . 16 0.3.6 Riordan matrices with entries in a unitary ring . . . . . . . . . . . . . . 17 0.3.7 Other relevant subgroups of the Riordan group . . . . . . . . . . . . . . 18 0.4 Final Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 0.4.1 Lie groups over Frechet spaces . . . . . . . . . . . . . . . . . . . . . . . 19 0.4.2 Simplicial Complexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1 Some Inverse Limit Approaches to R(K) 1 1.1 Partial Riordan matrices and groups . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Riordan matrices with the same n-th projection . . . . . . . . . . . . . . . . . . 4 1.3 Extending Involutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.4 R(K) as an inverse limit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.5 Finite matrices and metrics in R(K) . . . . . . . . . . . . . . . . . . . . . . . . 9 1.6 Reflection of Finite Riordan Matrices . . . . . . . . . . . . . . . . . . . . . . . . 10 1.7 Bi-infinite Representation. Complem. and Dual Matrices . . . . . . . . . . . . 12 1.8 Reflections and complementary and dual Riordan matrices . . . . . . . . . . . . 16 1.9 R11 as an inverse limit I: from R(K) to R11(K) . . . . . . . . . . . . . . . . 18 1.10 R11 as an inverse limit II: from Rn to R11 . . . . . . . . . . . . . . . . . . . 20 v vi CONTENTS 1.11 Symmetries in bi-infinite Riordan matrices . . . . . . . . . . . . . . . . . . . . . 23 1.12 Solution of (Problem 1) and (Problem 2) . . . . . . . . . . . . . . . . . . . . . . 24 1.13 Relation to Functional Equations in Power Series . . . . . . . . . . . . . . . . . 28 1.14 Application: Schröder and weighted Schröder equations . . . . . . . . . . . . . 29 2 Some aspects of the algebraic structure 37 2.1 Derived Series of F . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 1 2.2 Again the weighted Schröder equation . . . . . . . . . . . . . . . . . . . . . . . 44 2.3 Derived Series of R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.4 The Conjugacy Problem in A′ (or F′), R′ . . . . . . . . . . . . . . . . . . . . . 49 1 2.5 Some words on the general Conjugacy Problem in A, R . . . . . . . . . . . . . 55 2.6 Example: the Conjugacy Class of the Pascal Triangle . . . . . . . . . . . . . . . 57 2.7 Application of Conjugacy I: centralizers . . . . . . . . . . . . . . . . . . . . . . 58 2.8 Application of Conjugacy II: powers of Riordan matrices . . . . . . . . . . . . . 61 2.9 The abelianized of R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 n 3 Involutions and elements of finite order 1 3.1 Basics about involutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 3.2 Finite and infinite non-trivial involutions. . . . . . . . . . . . . . . . . . . . . . 3 3.3 Examples and Related Aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.4 Elements of finite order in R(K) . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.5 More about the A-sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.6 The Group generated by the Involutions I . . . . . . . . . . . . . . . . . . . . . 20 3.7 The Group generated by the Involutions II . . . . . . . . . . . . . . . . . . . . 21 3.8 Some Consequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4 Lie Group Structure for R(K) 1 4.1 Some Basic Definitions: classical Lie groups . . . . . . . . . . . . . . . . . . . . 2 4.2 Lie Groups Modelled over Frechet Spaces . . . . . . . . . . . . . . . . . . . . . 5 4.3 R (K) as a manifold. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 n 4.4 The Lie group structure of R (K). . . . . . . . . . . . . . . . . . . . . . . . . . 9 n 4.5 The Lie Algebra of R (K) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 n 4.6 Bonding maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.7 R(K) as a Lie group I: Frechet Lie Group Structure . . . . . . . . . . . . . . . 15 4.8 R(K) as a Lie group II: Lie group structure as a pro-Lie group . . . . . . . . . 17 4.9 Curves and One-parameter subgroups in R . . . . . . . . . . . . . . . . . . . . 19 4.10 The Lie Algebra of R(K) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.11 The exponential map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.12 Lie group structure for R11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.13 Multplication of L((cid:31);(cid:11)) by a column vector on KN . . . . . . . . . . . . . . . . 26 4.14 Initial Value Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.15 Conjugation in L(R) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.16 The Tangent Bundle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.17 Toeplitz-Lagrange Decomposition in L(R) . . . . . . . . . . . . . . . . . . . . . 33 4.18 Stabilizers in R(K) and the corresponding Lie algebras . . . . . . . . . . . . . . 35 CONTENTS vii 5 Riordan Matrices and Simplicial Complexes 1 5.1 Simplicial Complexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 5.2 The f-vector Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5.3 f-, h-, g- and (cid:13)-vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 5.4 Dehn-Sommervile Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 5.5 Iterated Join of Simplicial Complexes as a Riordan pattern . . . . . . . . . . . 12 5.6 Subdivision methods and matrices in ILT1 . . . . . . . . . . . . . . . . . . . . 18 5.7 Application: Linear Arithmetic Relations . . . . . . . . . . . . . . . . . . . . . 21 5.8 Betti numbers of the m;q-cones . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.9 New building blocks: q-simplices . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Open Questions 35 Bibliography 40 Introducción/Introduction Español El protagonista de este trabajo es el grupo de Riordan, que denotaremos por R(K). El grupo de Riordan fue nombrado así en honor de J. Riordan, 1903-1988 y nació (aparece por primera vez con este nombre) en el trabajo de L. Shapiro, S. Getu, W. J. Woan y L. C. Woodson en [105] (aunque la definición ha variado ligeramente: el grupo que se definió en ese artículo es de hecho un subgrupo del grupo que se considera actualmente) y fue utilizado posteriormente (por ejemplo en los trabajos de R. Sprugnoli [107] y [108]) como herramienta adecuada para problemas de naturaleza combinatoria como la demostración de identidades. Los directores de este trabajo también participaron en este desarrollo, cuando se encontraron con el grupo de Riordan desde una aproximación bastante diferente (véase [66]). Los elementos del grupo de Riordan suelen describirse como matrices triangulares infinitas invertibles, esto es, de la forma: 2 3 a 00 6 7 6a10 a11 7 (aij)0(cid:20)i;j<1 = 64a20 a21 a22 75 ... ... ... ... (inicialmente con entradas en C, aunque pueden considerarse con entradas en cualquier cuerpo K) asociadas a un par de series formales de potencias d(x);h(x) 2 K[[x]] donde: d(x) = d +d x+d x2+::: h(x) = h x+h x2+h x3+::: con f ;g ̸= 0 0 1 2 1 2 3 0 1 con la propiedad de que la función generatriz de las entradas de la columna i-ésima es: d(x)(cid:1)(h(x))i; esto es: d(x)(cid:1)(h(x))i = a xi+a xi+1+a xi+2+::: ii i+1;i i+2;i En este caso dicha matriz se denota por R(d(x);h(x)). Gracias a esta estructura, hay una interpretaciónentérminosdeseriesformalesdepotenciasdelamultiplicacióndeestasmatrices por un vector columna (el llamado Primer Teorema Fundamental de las Matrices de Riordan o simplemente 1FTRM) y de la multiplicación de dos de estas matrices entre sí (véase la subsección 0.3.2 para más detalles). Por lo anteriormente expuesto, el grupo de Riordan podría clasificarse en el área de Com- binatoria. Pero por otra parte, como cualquier objeto matemático de interés, el grupo de ix x CONTENTS Riordan tiene aspectos que pueden llamar la atención de expertos de otros ramas del desar- rollo matemático. Al exponer al grupo de Riordan a distintas lupas, y buscando diferentes características se aumenta el conocimiento sobre dicho objeto y, por lo tanto, las posibilidades de su uso en problemas de distinta índole. Por eso en esta tesis vamos a tratar fundamental- mente tres tipos de aspectos: 1. Estudio de la estructura de grupo de R(K), que se realiza en los capítulos 1, 2 y 3, y al que hemos dedicado más trabajo. Contiene una fundamentación importante para el resto del trabajo relacionada con la estructura como límite inverso del grupo de Riordan. La correspondiente sucesión inversa involucra unos grupos de matrices de dimensión finita que llamaremos grupos parciales de Riordan. Además, en esta parte se estudia la serie derivada del grupo (con varias aplicaciones), las clases de conjugación desdediferentespuntosdevistayloselementosdeordenfinito,haciendoespecialhincapié en las involuciones y encontrando el grupo generado por las involuciones. También se estudia la relación entre problemas algebraicos en el grupo de Riordan y ecuaciones y sistemas de ecuaciones funcionales en series formales de potencias. 2. Estudio de una estructura de grupo de Lie infinito-dimensional de R(K) para K = R;C, que se realiza en el capítulo 4, como ejemplo de grupo de Lie sobre un espacio de Frechet, que además es un pro-grupo de Lie (límite inverso de grupos de Lie clásicos). Se estudian también parametrizaciones globales de los grupos parciales y del grupo de Riordan infinito. 3. Aplicaciones a problemas de Topología Combinatoria de Complejos Simpli- ciales, que se realiza en el capítulo 5. Se aplican las técnicas algebraicas desarrolladas en el resto del trabajo al estudio del problema del f-vector. Se pretende también mostrar la presencia de objetos con patrones del tipo Riordan en este campo. Un procedimiento común en los resultados conseguidos es considerar el grupo de Riordan R(K) como límite inverso de una sucesión inversa: f(R (K);P )g1 n n n=0 donde los grupos R (K) son unos grupos de matrices triangulares inferiores de tamaño (n+ n 1)(cid:2)(n+1) que llamaremos los grupos parciales, estudiar primero qué ocurre en las proyec- ciones finitas y la posibilidad de elevación de propiedades al grupo de matrices infinitas (esta construcción de límite inverso será presentada con detalle en la sección 1.4). También hay que tener en cuenta que la identificación de las matrices de Riordan y la in- terpretación del producto de las mismas en términos de series formales de potencias establece una forma de traducir problemas algebraicos en el grupo (conjugación, serie derivada, carac- terización de elementos de orden finito, etc.) a sistemas de ecuaciones funcionales (en series formales de potencias) y viceversa. Existen diferentes maneras de construir matrices de Riordan. Tenemos por ejemplo la construcciónhorizontal(queinvolucraalaA-sequence)ylaconstrucciónvertical(queinvolucra alag-sequenceyesunodelosmotivosdelusodelanotaciónT(f j g)porpartedelosdirectores de este trabajo introducida en [66] y utilizada en sus trabajos siguientes, como por ejemplo